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 paper considers the computation of definition-use and use-definition chains that extend across procedure boundaries at call and return sites. Intraprocedural definition and use information is abstracted for each procedure and is used to construct an interprocedural flow graph. This intraprocedural data-flow information is then propagated throughout the program via the interprocedural flow graph to obtain sets of reaching definitions and/or reachable uses for reach 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 data flow 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.

REFERENCES

• 1: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 2: F. Allen , M. Burke , P. Charles , R. Cytron , J. Ferrante, An overview of the PTRAN analysis system for multiprocessing, Proceedings of the 1st International Conference on Supercomputing, p.194-211, March 1988, Athens, Greece
• 3: John P. Banning, An efficient way to find the side effects of procedure calls and the aliases of variables, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.29-41, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567756]
• 4: Jeffrey M. Barth, A practical interprocedural data flow analysis algorithm, Communications of the ACM, v.21 n.9, p.724-736, Sept. 1978 [doi>10.1145/359588.359596]
• 5: Michael Burke, An interval-based approach to exhaustive and incremental interprocedural data-flow analysis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.3, p.341-395, July 1990 [doi>10.1145/78969.78963]
• 6: D. Callahan, The program summary graph and flow-sensitive interprocedual data flow analysis, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.47-56, June 20-24, 1988, Atlanta, Georgia, United States
• 7: K. D. Cooper , K. Kennedy, Interprocedural side-effect analysis in linear time, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.57-66, June 20-24, 1988, Atlanta, Georgia, United States
• 8: Keith D. Cooper , Ken Kennedy , Linda Torczon, The impact of interprocedural analysis and optimization in the Rⁿ programming environment, ACM Transactions on Programming Languages and Systems (TOPLAS), v.8 n.4, p.491-523, Oct. 1986 [doi>10.1145/6465.6489]
• 9: Keith D. Cooper , Ken Kennedy , Linda Lorczon, Interprocedural optimization: eliminating unnecessary recompilation, ACM SIGPLAN Notices, v.21 n.7, p.58-67, July 1986
• 10: Phyllis G. Frankl , Elaine J. Weyuker, A data flow testing tool, Proceedings of the second conference on Software development tools, techniques, and alternatives, p.46-53, December 1985, San Francisco, California, United States
• 11: P. G. Frankl , E. J. Weyuker, An Applicable Family of Data Flow Testing Criteria, IEEE Transactions on Software Engineering, v.14 n.10, p.1483-1498, October 1988 [doi>10.1109/32.6194]
• 12: ~HARROLD, M. J., AND SOFFA, M.L. 1989. An incremental data flow testing tool. In Proceedings ~of the 6th International Conference on Testing Computer Software (Washington D.C., May).
• 13: Mary Jean Harrold , Mary Lou Soffa, Selecting and Using Data for Integration Testing, IEEE Software, v.8 n.2, p.58-65, March 1991 [doi>10.1109/52.73750]
• 14: Susan Horwitz , Thomas Reps , David Binkley, Interprocedural slicing using dependence graphs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.1, p.26-60, Jan. 1990 [doi>10.1145/77606.77608]
• 15: John B. Kam , Jeffrey D. Ullman, Global Data Flow Analysis and Iterative Algorithms, Journal of the ACM (JACM), v.23 n.1, p.158-171, Jan. 1976 [doi>10.1145/321921.321938]
• 16: Gary A. Kildall, A unified approach to global program optimization, Proceedings of the 1st annual ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.194-206, October 01-03, 1973, Boston, Massachusetts [doi>10.1145/512927.512945]
• 17: B. Korel , J. Laski, A tool for data flow oriented program testing, Proceedings of the second conference on Software development tools, techniques, and alternatives, p.34-37, December 1985, San Francisco, California, United States
• 18: ~LASKI, J. W., AND KOREL, B. 1983. A data flow oriented program testing strategy. IEEE Trans. ~Softw. Eng. SE-9, 3 (May), 347-354.
• 19: LOMET, D.B. 1977. Data flow analysis in the presence of procedure calls. IBM J. Res. Dev. 21, ~6 (Nov.), 559-571.
• 20: Eugene M. Myers, A precise inter-procedural data flow algorithm, Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.219-230, January 26-28, 1981, Williamsburg, Virginia [doi>10.1145/567532.567556]
• 21: Simeon C. Ntafos, An evaluation of required element testing strategies, Proceedings of the 7th international conference on Software engineering, p.250-256, March 26-29, 1984, Orlando, Florida, United States
• 22: ~TAHA, A. M., THEBUT, S. M., AND LIU, S.S. 1989. An approach to software fault localization ~and revalidation based on incremental data flow analysis. In Proceedings of COMPSAC 89 ~(Sept.). IEEE, New York, 527-534.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

General Terms:
Algorithms, Languages

Keywords:
dataflow testing, interprocedural dataflow analysis, interprocedural definition-use chains, interprocedural reachable uses, interprocedural reaching definitions