Parallelizing Compilers

We have recently developed a flow-sensitive algorithm to compute the interprocedural definition-use chains of dynamic pointer-linked data structures. This algorithm relates the statements that construct links of dynamic pointer-linked data structures (i.e. definitions) to the statements that might traverse the structures via the links (i.e. uses). The outcome of this computation provides the essential information for program transformations and communication generations of data-parallel programs or optimizations and parallelization of sequential programs with dynamic pointer-linked data structures on parallel and distributed systems.

We have proposed a traversal-pattern-sensitive shape analysis approach to take advantage of the availability of the definition-use information. It gathers the traversal patterns of programs on dynamic pointer-linked data structures and then estimates the possible shapes and connections of structures specified by traversal patterns. This approach can simplify dependence analysis by using the knowledge of traversal patterns to avoid gathering unnecessary alias and connection information. Furthermore, it can facilitate dependence analysis algorithm to detect parallelism in programs even with cyclic data structures. The dependence test algorithm presented in my dissertation first performs conflict analysis by assuming that each unique path leads to a distinct storage location, and then validates the result by taking the effects of aliases and connections into account using traversal-pattern-sensitive shape analysis.