Constant propagation in a hierarchical intermediate program representation

A crucial problem in parallelizing compiler design is the choice of a suita ble Intermediate Representation (IR) to make parallelism detection and extr action easy and possible. Dependence graphs have long been recognized as us eful tools for this aim. Several versions were proposed [1,4,6,20], which e ncapsulate relations of data dependence, control dependence or both. They w ere also used in conventional optimizations, but always coupled with the tr aditional Control Flow Graph (CFG). However, it would be preferable to appl y both conventional and parallelizing optimizations to the same IR. Recentl y, some attempts were made to use dependence graphs as a unifying framework on which all types of optimization [4] are applied. This is one of the aim s of our work in this research area. We started working on the well known H ierarchical Task Graph (HTG) of Polychronopoulos and Girkar [6,7,8]. The HT G, by definition, is an acyclic and then a reducible graph. In fact it is b uilt from a CFG arranged hierarchically around loops with all loop back edg es removed. This CFG is then enriched with control and data dependence info rmation (edges). Our proposal is an extension of the HTG, named Extended Hi erarchical Task Graph (EHTG), that is a HTG where data dependence edges are annotated with a boolean branch path expression indicating the CFG paths t hrough which the data dependences are established. We developed two algorit hms of constant propagation (used for dead code elimination) running direct ly on our EHTG without using the traditional CFG. The two algorithms can be applied only to sequential programs whose parallelism is represented by th e HTG structure. They are not suited to perform constant propagation on exp licitly parallel programs [12]. Complexity and correctness of the algorithm s are analyzed and we also prove that one of them has the same complexity a nd finds the same class of constants as the well known Wegman & Zadeck cons tant propagation algorithm [20], that uses a hybrid sparse representation.