Interprocedural side-effect analysis in linear time

ABSTRACT

We present a new method for solving Banning's alias-free flow-insensitive side-effect analysis problem. The algorithm employs a new data structure, called the binding multi-graph, along with depth-first search to achieve a running time that is linear in the size of the call multi-graph of the program. This method can be extended to produce fast algorithms for data-flow problems with more complex lattice structures.

REFERENCES

• Alle 74: F.E. Allen, "Interprocedural data flow analysis", Proc. of the 197d IFIP$ Congress, 1974.
• Bann 79: 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]
• Bart 78: 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]
• Burk 84: M. Burke, "An interval analysis approach toward interprocedural data flow", Report RC 10640, IBM T.J. Watson Research Center, Yorktown Heights, N.Y., July, 1984.
• BuCy 86: Michael Burke , Ron Cytron, Interprocedural dependence analysis and parallelization, ACM SIGPLAN Notices, v.21 n.7, p.162-175, July 1986
• CCKT 86: David Callahan , Keith D. Cooper , Ken Kennedy , Linda Torczon, Interprocedural constant propagation, ACM SIGPLAN Notices, v.21 n.7, p.152-161, July 1986
• CaKe 87: D. Callahan , K. Kennedy, Analysis of interprocedural side effects in a parallel programming environment, Proceedings of the 1st International Conference on Supercomputing, p.138-171, March 1988, Athens, Greece
• CaRy 86: Martin Carroll , Barbara G Ryder, An incremental algorithm for software analysis, Proceedings of the second ACM SIGSOFT/SIGPLAN software engineering symposium on Practical software development environments, p.171-179, December 09-11, 1986, Palo Alto, California, United States
• Carr 87: M.D. Carroll, "Datafiow update via attribute and dominator update," Ph.D. Dissertation, Rutgers University, 1987.
• Coop 83: Keith Daniel Cooper, Interprocedural data flow analysis in a programming environment, 1983
• CoKe 84: Keith D. Cooper , Ken Kennedy, Efficient computation of flow insensitive interprocedural summary information, Proceedings of the 1984 SIGPLAN symposium on Compiler construction, p.247-258, June 17-22, 1984, Montreal, Canada
• CoKe 87a: K.D. Cooper and K. Kennedy, "Efficient computation of flow-insensitive interprocedural summary information -- a correction", TR87-60, Department of Computer Science, Rice University, Oct., 1987.
• CoKe 87b: K.D. Cooper and K. Kennedy, "Complexity of interprocedural side-effect analysis", TR87-61, Department of Computer Science, Rice University, Oct., 1987.
• GrWe 76: Susan L. Graham , Mark Wegman, A Fast and Usually Linear Algorithm for Global Flow Analysis, Journal of the ACM (JACM), v.23 n.1, p.172-202, Jan. 1976 [doi>10.1145/321921.321939]
• KaUl 76: 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]
• Myer 80: E. Myers, "A precise and efficient algorithm for determining existential summary data flow information'', Technical Report CU-CS- 175-80, Department of Computer Science, University of Colorado, March, 1980.
• Rose 79: Barry K. Rosen, Data Flow Analysis for Procedural Languages, Journal of the ACM (JACM), v.26 n.2, p.322-344, April 1979 [doi>10.1145/322123.322135]
• Ryde 87: B. Ryder, private communication, July 31, 1987.
• Spil 71: T.C. Spillman, "Exposing side-effects in a PL/I optimizing compiler", Proc. of the 1971 IFIPS Con#re,s, 1971.
• Tarj 72: R.E. Tarian, "Depth-first search and linear graph algorithms", SIAM J. Computing 1(2), 1972.
• Tarj 81a: Robert Endre Tarjan, A Unified Approach to Path Problems, Journal of the ACM (JACM), v.28 n.3, p.577-593, July 1981 [doi>10.1145/322261.322272]
• Tarj 81b: Robert Endre Tarjan, Fast Algorithms for Solving Path Problems, Journal of the ACM (JACM), v.28 n.3, p.594-614, July 1981 [doi>10.1145/322261.322273]
• TrIF 86: Rémi Triolet , Francois Irigoin , Paul Feautrier, Direct parallelization of call statements, ACM SIGPLAN Notices, v.21 n.7, p.176-185, July 1986
• Torc 85: Linda Marie Torczon, Compilation dependences in an ambitious optimizing compiler (interprocedural, recompilation), 1985
• Zade 84: Frank Kenneth Zadeck, Incremental data flow analysis in a structured program editor, Proceedings of the 1984 SIGPLAN symposium on Compiler construction, p.132-143, June 17-22, 1984, Montreal, Canada

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Graphs and networks

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: FORTRAN
      D.3.3 Language Constructs and Features
          Subjects: Procedures, functions, and subroutines
      D.3.4 Processors
          Subjects: Compilers

General Terms:
Algorithms, Languages