# Liveness Analysis in Explicitly-Parallel Programs

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.
Keywords :
Document type :
Reports
Domain :
Complete list of metadatas

Cited literature [26 references]

https://hal.inria.fr/hal-01251579
Contributor : Alain Darte <>
Submitted on : Wednesday, January 6, 2016 - 2:00:00 PM
Last modification on : Wednesday, November 20, 2019 - 3:01:47 AM
Long-term archiving on: Thursday, April 7, 2016 - 4:01:13 PM

### File

RR-8839.pdf
Files produced by the author(s)

### Identifiers

• HAL Id : hal-01251579, version 1

### Citation

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