Affiliations: Department of Computer Science, National Taiwan Ocean
University, Keelung 20224, Taiwan. E-mail: shin@cs.ntou.edu.tw | Department of Biomedical Informatics, The Ohio State
University, Columbus, OH 43210, USA. E-mail: saltz-@medctr.osu.edu
Note: [] Corresponding author: Yuan-Shin Hwang, Department of Computer
Science, National Taiwan Ocean University, Keelung 20224, Taiwan. Tel.: +886 2
24622192, ext.6602; Fax: +886 2 24623249; E-mail: shin@cs.ntou.edu.tw
Abstract: 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.
Keywords: definition-use chains, pointer-linked data structures, data flow analysis, interprocedural analysis, pointer analysis, dependence analysis
