Interprocedural definition-use chains of dynamic pointer-linked data structures

摘要

This paper presents a flow-sensitive algorithm to compute interprocedural definition-use chains of dynamic pointer-linked data structures. The goal is to relate the statements that construct links of dynamic pointer-linked data structures (i.e. definitions) to the statements that might traverse the structures through the links (i.e. uses). Specifically, for each statement S that defines links of pointer-linked data structures, the algorithm finds the set of statements that traverse the links which are defined by S. This algorithm solves the definition-use chaining problem by performing backward iterative data flow analysis to compute the set of upward exposed uses at each statement. The results of this algorithm can be used to identify parallelism in programs even with cyclic pointer-linked data structures.