Interprocedural data flow analysis in the presence of pointers, procedure variables, and label variables

ABSTRACT

Interprocedural data flow analysis is complicated by the use of procedure and label variables in programs and by the presence of aliasing among variables. In this paper we present an algorithm for computing possible values for procedure and label variables, thus providing a call graph and a control flow graph. The algorithm also computes the possible aliasing relationships in the program being analyzed.We assume that control flow information is not available to the algorithm; hence, this type of analysis may be termed "flow-free analysis." Given this assumption, we demonstrate the correctness of the algorithm, in the sense that the information it produces is conservative, and show that it is as precise as possible in certain cases. We also show that the problem of determining possible values for procedure variables is P-space hard. This fact indicates that any algorithm which is precise in all cases must also run very slowly for some programs.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: Alfred V. Aho , Jeffrey D. Ullman, Principles of Compiler Design (Addison-Wesley series in computer science and information processing), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1977
• 3: Allen, F. E. Interprocedural Data Flow Analysis. Proceedings IFIP Congress 74, North Holland Publishing Company, Amsterdam, 398-402.
• 4: F. E. Allen , J. Cocke, A program data flow analysis procedure, Communications of the ACM, v.19 n.3, p.137, March 1976 [doi>10.1145/360018.360025]
• 5: Allen, F. E., et. al. The Experimental Compiling Systems Project. IBM Research Report RC6718, T.J. Watson Research Center, Yorktown Heights, N.Y. September 1977.
• 6: John Phineas Banning, A method for determining the side effects of procedure calls., 1978
• 7: Barth, J. Interprocedural Data Flow Analysis Based on Transitive Closure. Univ. of California at Berkeley, Computer Science Dept., Tech. Rep. UCB-CS-76-44, September 1976.
• 8: Carter, J. L. Private Communication.
• 9: 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]
• 10: 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]
• 11: Ryder, B. G. Constructing the Call Graph of a Program. IEEE Transactions on Software Engineering SE-5, 3 (May 1979), 216-226.
• 12: Spillman, T. C. Exposing Side-Effects in a PL/I Optimizing Compiler. Proceedings IFIP Conference 1971, North Holland Publishing Company, Amsterdam, 376-381.
• 13: 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]
• 14: Wegman, M. N., and Carter, J. L. New Classes and Applications of Hash Functions. Proceedings 20th Annual Symposium on Foundations of Computer Science (October 1979), 175-182.
• 15: Weihl, W. E. Interprocedural Data Flow Analysis in the Presence of Pointers, Procedure Variables, and Label Variables. S.M. Thesis, Massachusetts Institute of Technology (to be published).
• 16: Karl Andreas Winklmann, A theoretical study of some aspects of parameter passing in algol60 and in similar programming languages., 1977