Efficient call graph analysis

ABSTRACT

We present an efficient algorithm for computing the procedure call graph, the program representation underlying most interprocedural optimization techniques. The algorithm computes the possible bindings of procedure variables in languages where such variables only receive their values through parameter passing, such as Fortran. We extend the algorithm to accommodate a limited form of assignments to procedure variables. The resulting algorithm can also be used in analysis of functional programs that have been converted to Continuation-Passing-Style. We discuss the algorithm in relationship to other call graph analysis approaches. Many less efficient techniques produce essentially the same call graph. A few algorithms are more precise, but they may be prohibitively expensive depending on language features.

REFERENCES

• 1: BURKE, M. An interval-based approach to exhaustive and incremental interprocedural analysis. Res. Rep. RC 12702, IBM, Yorktown Heights, N.Y., 1987.
• 2: David Callahan , Alan Carle , Mary Wolcott Hall , Ken Kennedy, Constructing the Procedure Call Multigraph, IEEE Transactions on Software Engineering, v.16 n.4, p.483-487, April 1990 [doi>10.1109/32.54302]
• 3: CALLAHAN, C. D., COOPER, K. D., HOOD, R. T., KENNEDY, K., AND TORCZON, L. ParaScope: A parallel programming environment. Int. J. Supercomput. Appl. 2, 4 (1988), 84-89.
• 4: C. Chambers , D. Ungar, Customization: optimizing compiler technology for SELF, a dynamically-typed object-oriented programming language, ACM SIGPLAN Notices, v.24 n.7, p.146-160, July 1989
• 5: K. D. Cooper , K. Kennedy, Fast interprocedual alias analysis, Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.49-59, January 11-13, 1989, Austin, Texas, United States [doi>10.1145/75277.75282]
• 6: K. D. Cooper , K. Kennedy, Interprocedural side-effect analysis in linear time, ACM SIGPLAN Notices, v.23 n.7, p.57-66, July 1988
• 7: EIGENMANN, R., AND PLUME, W. An effectiveness study of parallelizing compiler techniques. In Proceedings of the 1991 International Conference on Parallel Processing (Boca Raton, Fla., Aug. 1991). CRC Press, II-17-II-24.
• 8: Michael J. Fischer, Lambda calculus schemata, ACM SIGPLAN Notices, v.7 n.1, p.104-109, January 1972
• 9: Mary Wolcott Hall, Managing interprocedural optimization, Rice University, Houston, TX, 1992
• 10: M. W. Hall , S. Hiranandani , K. Kennedy , C.-W. Tseng, Interprocedural compilation of Fortran D for MIMD distributed-memory machines, Proceedings of the 1992 ACM/IEEE conference on Supercomputing, p.522-534, November 16-20, 1992, Minneapolis, Minnesota, United States
• 11: Mary W. Hall , Ken Kennedy , Kathryn S. McKinley, Interprocedural transformations for parallel code generation, Proceedings of the 1991 ACM/IEEE conference on Supercomputing, p.424-434, November 18-22, 1991, Albuquerque, New Mexico, United States [doi>10.1145/125826.126055]
• 12: P. Havlak , K. Kennedy, An Implementation of Interprocedural Bounded Regular Section Analysis, IEEE Transactions on Parallel and Distributed Systems, v.2 n.3, p.350-360, July 1991 [doi>10.1109/71.86110]
• 13: 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]
• 14: Zhiyuan Li , Pen-Chung Yew, Efficient interprocedural analysis for program parallelization and restructuring, ACM SIGPLAN Notices, v.23 n.9, p.85-99, Sept. 1988
• 15: Jon Loeliger , Robert Metzger , Mark Seligman , Sean Stroud, Pointer target tracking—an empirical study, Proceedings of the 1991 ACM/IEEE conference on Supercomputing, p.14-23, November 18-22, 1991, Albuquerque, New Mexico, United States [doi>10.1145/125826.125856]
• 16: John C. Reynolds, Definitional interpreters for higher-order programming languages, Proceedings of the ACM annual conference, p.717-740, August 01-01, 1972, Boston, Massachusetts, United States [doi>10.1145/800194.805852]
• 17: RYDER, B. Constructing the call graph of a program. IEEE Trans. Softw. Eng. SE-5, 3 (1979), 216-225.
• 18: Olin Shivers, The semantics of Scheme control-flow analysis, ACM SIGPLAN Notices, v.26 n.9, p.190-198, Sept. 1991
• 19: Olin Grigsby Shivers, Control-flow analysis of higher-order languages of taming lambda, Carnegie Mellon University, Pittsburgh, PA, 1991
• 20: O. Shivers, Control flow analysis in scheme, ACM SIGPLAN Notices, v.23 n.7, p.164-174, July 1988
• 21: SPmLM~, T.C. Exposing side-effects in a PL/I optimizing compiler. In Proceedings of the IFIP Congress 1971. North Holland, Amsterdam, 376-381.
• 22: Rémi Triolet , Francois Irigoin , Paul Feautrier, Direct parallelization of call statements, ACM SIGPLAN Notices, v.21 n.7, p.176-185, July 1986
• 23: Kenneth G. Walter, Recursion analysis for compiler optimization, Communications of the ACM, v.19 n.9, p.514-516, Sept. 1976 [doi>10.1145/360336.360341]
• 24: William E. Weihl, Interprocedural data flow analysis in the presence of pointers, procedure variables, and label variables, Proceedings of the 7th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.83-94, January 28-30, 1980, Las Vegas, Nevada [doi>10.1145/567446.567455]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Procedures, functions, and subroutines

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization; Compilers