Efficient Computation of Interprocedural Definition-Use Chains
ACM Transactions on Programming Languages and Systems
vol. 16, no. 2, March 1994, pp. 175-204
Mary Jean Harrold and Mary Lou Soffa
The dependencies that exist among definitions and uses
of variables in a program are required by many language processing
This work considers the computation of definition-use
and use-definition chains that
extend across procedure boundaries at both
call and return sites.
Intraprocedural data flow
information is abstracted for each procedure
and used to construct an interprocedural flow graph.
The intraprocedural definition and use
information is then propagated throughout the
program via the interprocedural flow graph to
obtain sets of
reaching definitions and/or
reachable uses for each interprocedural
control point, including procedure entry, exit,
call and return.
Interprocedural definition-use and/or use-definition
chains are computed from this reaching information.
The technique handles the interprocedural
effects of the flow
of data caused by both reference parameters and
while preserving the calling context of called procedures.
aliasing and separate compilation
has been implemented using a Sun-4 Workstation and
incorporated into an interprocedural data flow tester.
Results from experiments indicate the practicality of the
technique both in terms of the size of the interprocedural
flow graph and the size of the data flow sets.