K. D. Cooper
K. Kennedy
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.
- Alle 74 F.E. Allen, "Interprocedural data flow analysis", Proc. of the 197d IFIP$ Congress, 1974.Google Scholar
- Bann 79 J.P. Banning, "An efficient way to find the side effects of procedure calls and the aliases of variables'', Proc. of the Sixth POPL, Jan., 1979. Google ScholarDigital Library
- Bart 78 J.M. Barth, "A practical interprocedural data flow analysis algorithm", CA CM 21(9), Sept., 1978. Google ScholarDigital Library
- 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.Google Scholar
- BuCy 86 M. Burke and R. Cytron, "Interprocedural dependence analysis and parallelization", Proc. of the $IGPI, AN 86 Symposium on Compiler Construction, $IGPLAN Notice$, 21(7), July, 1986. Google ScholarDigital Library
- CCKT 86 D. Callahan, K.D. Cooper, K. Kennedy, and L. Torczon, "Interprocedural constant propagation", Proc. of the $IGPLAN 86 Symposium on Compiler Construction, SIGPLAN Notices, 21(7), July, 1986. Google ScholarDigital Library
- CaKe 87 D. Callahan and K. Kennedy, "Analysis of interprocedural side effects in a parallel programming environment", Proc, of First Int'l Conference on Supercomputing, Athens, Greece, June, 1987. Google ScholarDigital Library
- CaRy 86 M.D. Carroll and B.C. Ryder, "An incremental algorithm for software analysis", Proc. of the SIGSOFT/SIGPLAN Software Engineering Symposium on Practical Software Development Environments, $IGPLAN Notices 22(1), Jan., 1987. Google ScholarDigital Library
- Carr 87 M.D. Carroll, "Datafiow update via attribute and dominator update," Ph.D. Dissertation, Rutgers University, 1987.Google Scholar
- Coop 83 K.D. Cooper, "Interprocedura{ data flow analysis in a programming environment", Ph.D. dissertation Department of Mathematical Sciences, Rice University, April, 1983. Google ScholarDigital Library
- CoKe 84 K.D. Cooper and K. Kennedy, "Efficient computation of flow insensitive interprocedural summary information", Proc. of the SIGPLAN 8d Symposium on Compiler Construction, $16PLAN Notices 19(6), June, 1984. Google ScholarDigital Library
- 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.Google Scholar
- CoKe 87b K.D. Cooper and K. Kennedy, "Complexity of interprocedural side-effect analysis", TR87-61, Department of Computer Science, Rice University, Oct., 1987.Google Scholar
- GrWe 76 S. Graham and M. Wegman, "A fast and usually linear algorithm for global flow analysis", JA CM, Jan., 1976. Google ScholarDigital Library
- KaUl 76 J. Karn and J. Ullman, "Global data flow analysis and iterative algorithms", JACM, Jan., 1976. Google ScholarDigital Library
- 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.Google Scholar
- Rose 79 B. Rosen, "Data flow analysis for procedural languages", JA CM 26(2), April, 1079. Google ScholarDigital Library
- Ryde 87 B. Ryder, private communication, July 31, 1987.Google Scholar
- Spil 71 T.C. Spillman, "Exposing side-effects in a PL/I optimizing compiler", Proc. of the 1971 IFIPS Con#re,s, 1971.Google Scholar
- Tarj 72 R.E. Tarian, "Depth-first search and linear graph algorithms", SIAM J. Computing 1(2), 1972.Google Scholar
- Tarj 81a R.E. Tarjan, "A unified approach to path prot> Iems", JACM 28(3), July, 1981. Google ScholarDigital Library
- Tarj 81b R.E. Tarjan, "Fast algorithms for solving path problems", JACM28(3), July, 1981. Google ScholarDigital Library
- TrIF 86 R. Triolet, F. Irgoin, and P. Feautrier, "Direct parallelization of call statements", Proc. of the $IGPLAN $8 Symposium on Compiler Construction, $IGPLAN Notices, 21(7), July, 1986. Google ScholarDigital Library
- Torc 85 L. Torczon, "Compilation dependences in an ambitious optimizing compiler", Ph.D. dissertation, Department, of Computer Science, Rice University, May, 1985. Google ScholarDigital Library
- Zade 84 F.K. Zadeck, "Incremental data flow analysis in a structured program editor", Proc. of the SIGPLAN '8d Symposium on Compiler Construction, SIC- PLAN Notices, 19(6), June 1984. Google ScholarDigital Library
Index Terms
- Interprocedural side-effect analysis in linear time
Recommendations
Interprocedural pointer alias analysis
We present practical approximation methods for computing and representing interprocedural aliases for a program written in a language that includes pointers, reference parameters, and recursion. We present the following contributions: (1) a framework ...
Interprocedural side-effect analysis for incomplete object-oriented software modules
We introduce a new approach to computing interprocedural modification side effects for part of an object-oriented program (e.g., components, libraries or client modules). Our approach consists of first performing a whole-program points-to analysis to ...
Side-effect analysis with fast escape filter
SOAP '12: Proceedings of the ACM SIGPLAN International Workshop on State of the Art in Java Program analysisSide-effect analysis is a fundamental static analysis used to determine the memory locations modified or used by each program entity. For the programs with pointers, the analysis can be very imprecise. To improve the precision of side-effect analysis, ...
Comments