Skip to Main content Skip to Navigation
New interface
Conference papers

Liveness Analysis in Explicitly-Parallel Programs

Alain Darte 1 Alexandre Isoard 2, 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 paper, 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
Contributor : Alain Darte Connect in order to contact the contributor
Submitted on : Wednesday, January 6, 2016 - 6:18:11 PM
Last modification on : Tuesday, October 25, 2022 - 4:21:50 PM


  • HAL Id : hal-01251843, version 1



Alain Darte, Alexandre Isoard, Tomofumi Yuki. Liveness Analysis in Explicitly-Parallel Programs. 6th International Workshop on Polyhedral Compilation Techniques (IMPACT'16), held with HIPEAC'16, Michelle Strout and Tomofumi Yuki, Jan 2016, Prague, Czech Republic. ⟨hal-01251843⟩



Record views