Demand-driven computation of interprocedural data flow

ABSTRACT

This paper presents a general framework for deriving demand-driven algorithms for interprocedural data flow analysis of imperative programs. The goal of demand-driven analysis is to reduce the time and/or space overhead of conventional exhaustive analysis by avoiding the collection of information that is not needed. In our framework, a demand for data flow information is modeled as a set of date flow queries. The derived demand-driven algorithms find responses to these queries through a partial reversal of the respective data flow analysis. Depending on whether minimizing time or space is of primary concern, result caching may be incorporated in the derived algorithm. Our framework is applicable to interprocedural data flow problems with a finite domain set. If the problem's flow functions are distributive, the derived demand algorithms provide as precise information as the corresponding exhaustive analysis. For problems with monotone but non-distributive flow functions the provided data flow solutions are only approximate. We demonstrate our approach using the example of interprocedural copy constant propagation.

REFERENCES

• Bir84: G. Birkhoff. Lattice theory, volume 25. American Mathematical Society, Colloquium Publication, Washington, DC, 3rd edition, '84.
• BJ78: W.A. Babich and M. Jazayeri. The method of attributes for data flow analysis: Part II. Demand analysis. Acta Informatica, 10(3), Oct. '78.
• Bou93: François Bourdoncle, Abstract debugging of higher-order imperative languages, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.46-55, June 21-25, 1993, Albuquerque, New Mexico, United States
• CC77: P. Cousot and R. Cousot. Static determination of dynamic properties of recursive procedures. In E.J. Neuhold, editor, IFIP Conf. on Formal Description of Programming Concepts, pases 237--277. North- Hollan Pub. Co., '77.
• CCF90: Jong-Deok Choi , Ron Cytron , Jeanne Ferrante, Automatic construction of sparse data flow evaluation graphs, Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.55-66, January 21-23, 1991, Orlando, Florida, United States [doi>10.1145/99583.99594]
• CCF92: Jong-Deok Choi , R. Cytron , J. Ferrante, On the Efficient Engineering of Ambitious Program Analysis, IEEE Transactions on Software Engineering, v.20 n.2, p.105-114, February 1994 [doi>10.1109/32.265631]
• CG93: Ron Cytron , Reid Gershbein, Efficient accommodation of may-alias information in SSA form, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.36-45, June 21-25, 1993, Albuquerque, New Mexico, United States
• CHK92: K. Cooper, M. Hall, and K. Kennedy. Procedure cloning. In IEEE 1992 Int. Conf. on Computer Languages, pages 96-105, San Francisco, CA, April 1992.
• CK88: K. D. Cooper , K. Kennedy, Interprocedural side-effect analysis in linear time, ACM SIGPLAN Notices, v.23 n.7, p.57-66, July 1988
• Coo85: Keith D. Cooper, Analyzing aliases of reference formal parameters, Proceedings of the 12th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.281-290, January 14-16, 1985, New Orleans, Louisiana, United States [doi>10.1145/318593.318658]
• Cou81: P. Cousot. Semantic foundations of program analysis. In S. Muchnick and N.D. Jones, editors, Program Flow Analysis: Theory and Apphcations, pages 303- 342. Prentice-Hall, '81.
• DGS94: Evelyn Duesterwald , Rajiv Gupta , Mary Lou Soffa, Reducing the Cost of Data Flow Analysis By Congruence Partitioning, Proceedings of the 5th International Conference on Compiler Construction, p.357-373, April 07-09, 1994
• DRZ92: Dhananjay M. Dhamdhere , Barry K. Rosen , F. Kenneth Zadeck, How to analyze large programs efficiently and informatively, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.212-223, June 15-19, 1992, San Francisco, California, United States
• GT93: Dan Grove , Linda Torczon, Interprocedural constant propagation: a study of jump function implementation, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.90-99, June 21-25, 1993, Albuquerque, New Mexico, United States
• HL92: John Hughes , John Launchbury, Reversing abstract interpretations, Symposium proceedings on 4th European symposium on programming, p.269-286, January 1992, Rennes, France
• JM73: Neil D. Jones , Alan Mycroft, Data flow analysis of applicative programs using minimal function graphs, Proceedings of the 13th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.296-306, January 01, 1986, St. Petersburg Beach, Florida [doi>10.1145/512644.512672]
• JM82: Neil D. Jones , Steven S. Muchnick, A flexible approach to interprocedural data flow analysis and programs with recursive data structures, Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.66-74, January 25-27, 1982, Albuquerque, Mexico [doi>10.1145/582153.582161]
• JP93: Richard Johnson , Keshav Pingali, Dependence-based program analysis, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.78-89, June 21-25, 1993, Albuquerque, New Mexico, United States
• Kil73: 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]
• KS92: Jens Knoop , Bernhard Steffen, The Interprocedural Coincidence Theorem, Proceedings of the 4th International Conference on Compiler Construction, p.125-140, October 05-07, 1992
• KU77: J.B. Kam and J.D. Ullman. Monotone data flow analysis frameworks. Acta Informatica, 7(3):305-317, Jul. '77.
• Mas94: Vadim Maslov, Lazy array data-flow dependence analysis, Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.311-325, January 16-19, 1994, Portland, Oregon, United States [doi>10.1145/174675.177911]
• Mye81: 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]
• PS89: L. L. Pollock , M. L. Soffa, An Incremental Version of Iterative Data Flow Analysis, IEEE Transactions on Software Engineering, v.15 n.12, p.1537-1549, December 1989 [doi>10.1109/32.58766]
• Rep94: Thomas W. Reps, Solving Demand Versions of Interprocedural Analysis Problems, Proceedings of the 5th International Conference on Compiler Construction, p.389-403, April 07-09, 1994
• Ros79: 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]
• Ros81: Barry K. Rosen, Linear cost is sometimes quadratic, Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.117-124, January 26-28, 1981, Williamsburg, Virginia [doi>10.1145/567532.567545]
• RP88: Barbara G. Ryder , Marvin C. Paull, Incremental data-flow analysis algorithms, ACM Transactions on Programming Languages and Systems (TOPLAS), v.10 n.1, p.1-50, Jan. 1988 [doi>10.1145/42192.42193]
• RSH94: T. Reps, M. Sagiv, and S. Horwitz. Interprocedural datatiow analysis via graph reachability. Technical Report 94-14, Datalogisk Institut, University of Copenhagen, Copenhagen, Denmark, '94.
• RT82: J. Reif and R.E. Tarjan. Symbolic program analysis in almost linear time. SIAM Journal of Computing, 11 (1):81-93, Feb. '82.
• RWZ88: B. K. Rosen , M. N. Wegman , F. K. Zadeck, Global value numbers and redundant computations, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.12-27, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73562]
• SMHY93: A.D. Stoyenko, T.J. Marlowe, W.A. Halang, and M. Younis. Enabling efficient schedulability analysis through conditional linking and program transformations. Control Engineering Practice, 1(1):85-105, '93.
• SP81: M. Sharir and A. Pnueli. Two approaches to interprocedural data flow analysis. In S. Muchnick and N.D. Jones, editors, Program Flow Analysis: Theory and Applications, pages 189-234. Prentice-Hall, '81.
• SY93: R. E. Strom , D. M. Yellin, Extending Typestate Checking Using Conditional Liveness Analysis, IEEE Transactions on Software Engineering, v.19 n.5, p.478-485, May 1993 [doi>10.1109/32.232013]
• WZ85: Mark N. Wegman , Frank Kenneth Zadeck, Constant propagation with conditional branches, Proceedings of the 12th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.291-299, January 14-16, 1985, New Orleans, Louisiana, United States [doi>10.1145/318593.318659]
• Zad84: 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:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques
          Subjects: Flow charts

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS

General Terms:
Algorithms, Performance