Skip to Main content Skip to Navigation
New interface
Reports (Research report)

Liveness Analysis in Explicitly-Parallel Programs

Alain Darte 1 Alexandre Isoard 1 Tomofumi Yuki 1 
1 COMPSYS - Compilation and embedded computing systems
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : In this report, we revisit scalar and array element-wise liveness analysis for programs with parallel specifications. In earlier work on memory allocation/contraction (register allocation or intra- and inter-array reuse in the polyhedral model), a notion of ``time'' or a total order among the iteration points was used to compute the liveness of values. In general, the execution of parallel programs is not a total order, and hence the notion of time is not applicable. We first revise how conflicts are computed by using ideas from liveness analysis for register allocation, studying the structure of the corresponding conflict/interference graphs. Instead of considering the conflict between two live ranges, we only consider the conflict between a live range and a write. This simplifies the formulation from having four instances involved in the test down to three, and also improves the precision of the analysis in the general case. Then we extend the liveness analysis to work with partial orders so that it can be applied to many different parallel languages/specifications with different forms of parallelism. An important result is that the complement of the conflict graph with partial orders is directly connected to memory reuse, even in presence of races. However, programs with conditionals do not always define a partial order, and our next step will be to handle such cases with more accuracy.
Complete list of metadata

Cited literature [26 references]  Display  Hide  Download
Contributor : Alain Darte Connect in order to contact the contributor
Submitted on : Wednesday, January 6, 2016 - 2:00:00 PM
Last modification on : Wednesday, October 26, 2022 - 8:15:05 AM
Long-term archiving on: : Thursday, April 7, 2016 - 4:01:13 PM


Files produced by the author(s)


  • HAL Id : hal-01251579, version 1


Alain Darte, Alexandre Isoard, Tomofumi Yuki. Liveness Analysis in Explicitly-Parallel Programs. [Research Report] RR-8839, CNRS; Inria; ENS Lyon. 2016, pp.25. ⟨hal-01251579⟩



Record views


Files downloads