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.
Type de document :
Communication dans un congrès
6th International Workshop on Polyhedral Compilation Techniques (IMPACT'16), held with HIPEAC'16, Jan 2016, Prague, Czech Republic. Available as http://impact.gforge.inria.fr/impact2016/papers/impact2016-darte.pdf, Proceedings of the IMPACT series. 〈 http://impact.gforge.inria.fr/impact2016/〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01251843
Contributeur : Alain Darte <>
Soumis le : mercredi 6 janvier 2016 - 18:18:11
Dernière modification le : mardi 16 janvier 2018 - 15:42:45

Identifiants

  • HAL Id : hal-01251843, version 1

Collections

Citation

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, Jan 2016, Prague, Czech Republic. Available as http://impact.gforge.inria.fr/impact2016/papers/impact2016-darte.pdf, Proceedings of the IMPACT series. 〈 http://impact.gforge.inria.fr/impact2016/〉. 〈hal-01251843〉

Partager

Métriques

Consultations de la notice

170