Efficient Computation of Interprocedural Definition-Use chains

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.


Related research categories:
(1) Pointer Analysis
(2) Data Flow

Go To Publications