Main People Publications Research Tools

Selected publications by date

Selected publications by category

 

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

Abstract

The dependencies that exist among definitions and uses of variables in a program are required by many language processing tools. 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 global variables, while preserving the calling context of called procedures. Additionally, recursion, aliasing and separate compilation are handled. The technique 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.


Georgia Tech | College of Computing | Software Engineering | Aristotle Home
Updated November 14, 2005 by Jim Jones