Analyse de durées de vie dans les programmes explicitement parallèles

Corresponding publication at IMPACT'16 (http://impact.gforge.inria.fr/impact2016)In this report, we revisit scalar and array element-wise liveness analysis forprograms with parallel specifications. In earlier work on memoryallocation/contraction (register allocation or intra- and inter-array reusein the polyhedral model), a notion of ``time'' or a total order among theiteration points was used to compute the liveness of values. In general, theexecution of parallel programs is not a total order, and hence the notion oftime is not applicable.We first revise how conflicts are computed by using ideas from livenessanalysis for register allocation, studying the structure of the correspondingconflict/interference graphs. Instead of considering the conflict betweentwo live ranges, we only consider the conflict between a live rangeand a write. This simplifies the formulation from having four instancesinvolved in the test down to three, and also improves the precision of theanalysis in the general case.Then we extend the liveness analysis to work with partial orders sothat it can be applied to many different parallellanguages/specifications with different forms of parallelism. Animportant result is that the complement of the conflict graph withpartial orders is directly connected to memory reuse, even inpresence of races. However, programs with conditionals do not always definea partial order, and our next step will be to handle such caseswith more accuracy.Dans ce rapport, nous revisitons l'analyse de durée de vie(vivacité) des scalaires et des éléments de tableaux pour desprogrammes comportant des spécifications parallèles. Les précédentstravaux sur l'allocation/contraction mémoire (allocation deregistres ou réutilisation de tableaux dans le modèle polyédrique)utilisaient une notion de ``temps'' ou d'ordre total entre lesitérations pour calculer la vivacité des valeurs. En général,l'exécution de programmes parallèles n'est pas un ordre total, etdonc la notion de temps est mal définie. Nous révisons tout d'abord le calcul des conflits entre élémentsmémoire en utilisant des idées provenant de l'analyse de durée devie pour l'allocation de registres. Plutôt que de considérer leconflit entre deux intervalles de vie, nous considérons le conflitentre un intervalle de vie et une écriture. Ceci simplifie laformulation en n'impliquant plus, dans le test, que trois instancesau lieu de quatre, et également améliore la précision de l'analysedans le cas général. Nous étendons ensuite l'analyse de vivacité pour prendre en compte desordres partiels de sorte qu'elle puisse s'appliquer à différentslangages ou spécifications parallèles, avec des formes différentesd'expression du parallélisme. Un résultat important est que lecomplémentaire du graphe de conflits, dans le cas des ordrespartiels, est directement lié à la formulation de la réutilisationmémoire, même en cas d'accès concurrents (races). Néanmoins, lesprogrammes comportant des conditionnelles ne définissent pastoujours d'ordre partiel, et l'étape suivante sera de traiter cescas avec plus de précision