A practical framework for demand-driven interprocedural data flow analysis

ABSTRACT

The high cost and growing importance of interprocedural data flow analysis have led to an increased interest in demand-driven algorithms. In this article, we present a general framework for developing demand-driven interprocedural data flow analyzers and report our experience in evaluating the performance of this approach. A demand for data flow information is modeled as a set of queries. The framework includes a generic demand-driven algorithm that determines the response to query by iteratively applying a system of query propagation rules. The propagation rules yield precise responses for the class of distributive finite data flow problems. We also describe a two-phase framework variation to accurately handle nondistributive problems. A performance evaluation of our demand-driven approach is presented for two data flow problems, namely, reaching-definitions and copy constant propagation. Our experiments show that demand-driven analysis performs well in practice, reducing both time and space requirements when compared with exhaustive analysis.

REFERENCES

• 1: BABICH, W. AND JAZAYERI, ik/{. 1978. The method of attributes for data flow analysis: Part II. Demand analysis. Acta Inf. 10, 3 (Oct.), 265-272.
• 2: William Blume , Rudolf Eigenmann, Demand-Driven, Symbolic Range Propagation, Proceedings of the 8th International Workshop on Languages and Compilers for Parallel Computing, p.141-160, August 10-12, 1995
• 3: 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
• 4: BURKE, M. 1987. An interval analysis approach toward exhaustive and incremental data flow analysis. Tech. Rep. RC 12702, IBM Thomas J. Watson Research Center, Yorktown Heights, N.Y.
• 5: 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]
• 6: Jong-Deok Choi , Michael Burke , Paul Carini, Efficient flow-sensitive interprocedural computation of pointer-induced aliases and side effects, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.232-245, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158639]
• 7: 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]
• 8: COOPER, K., HALL, M., AND KENNEDY, K. 1992. Procedure cloning. In Proceedings of the IEEE 1992 International Conference on Computer Languages. IEEE, New York, 96-105.
• 9: K. D. Cooper , K. Kennedy, Interprocedural side-effect analysis in linear time, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.57-66, June 20-24, 1988, Atlanta, Georgia, United States
• 10: COUSOT, P. 1981. Semantic foundations of program analysis. In Program Flow Analysis: Theory and Applications, S. Muchnick and N. Jones, Eds. Prentice-Hall, Englewood Cliffs, N.J., 303- 342.
• 11: COUSOT, P. AND COUSOT, R. 1978. Static determination of dynamic properties of recursive procedures. In Proceedings of the IFIP Conference on Programming Concepts, E. Neuhold, Ed. North-Holland, Amsterdam, 237-277.
• 12: 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
• 13: Evelyn Duesterwald , Mary Lou Soffa , Rajiv Gupta, A demand-driven approach for efficient interprocedural data flow analysis, 1996
• 14: DUESTERWALD, E., GUPTA, R., AND SOFFA, M. 1992. Rigorous data flow testing through output influences. In Proceedings of the 2rid Irvine Software Symposium. 131-145.
• 15: Evelyn Duesterwald , Rajiv Gupta , Mary Lou Soffa, Demand-driven computation of interprocedural data flow, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.37-48, January 23-25, 1995, San Francisco, California, United States [doi>10.1145/199448.199461]
• 16: Maryam Emami , Rakesh Ghiya , Laurie J. Hendren, Context-sensitive interprocedural points-to analysis in the presence of function pointers, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.242-256, June 20-24, 1994, Orlando, Florida, United States
• 17: P. G. Frankl , E. J. Weyuker, An Applicable Family of Data Flow Testing Criteria, IEEE Transactions on Software Engineering, v.14 n.10, p.1483-1498, October 1988 [doi>10.1109/32.6194]
• 18: William G. Griswold , David Notkin, Automated assistance for program restructuring, ACM Transactions on Software Engineering and Methodology (TOSEM), v.2 n.3, p.228-269, July 1993 [doi>10.1145/152388.152389]
• 19: HANKIN, C. AND LEMETAYER, D. 1994. A type-based framework for program analysis. In Proceedings of the 1st International Static Analysis Symposium. 380-394.
• 20: Susan Horwitz , Thomas Reps , Mooly Sagiv, Demand interprocedural dataflow analysis, Proceedings of the 3rd ACM SIGSOFT symposium on Foundations of software engineering, p.104-115, October 12-15, 1995, Washington, D.C., United States
• 21: HORWlTZ, S., REPS, T., AND SAGIV, M. 1995b. Demand interprocedural dataflow analysis. Tech. Rep. 1283, Computer Science Dept., Univ. of Wisconsin, Madison, Wisc. Aug.
• 22: John Hughes , John Launchbury, Reversing abstract interpretations, Symposium proceedings on 4th European symposium on programming, p.269-286, January 1992, Rennes, France
• 23: 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]
• 24: KAM, J. AND ULLMAN, J. 1977. Monotone data flow analysis frameworks. Acta Inf. 7, 3 (July), 305-317.
• 25: Jens Knoop , Bernhard Steffen, The Interprocedural Coincidence Theorem, Proceedings of the 4th International Conference on Compiler Construction, p.125-140, October 05-07, 1992
• 26: William Landi , Barbara G. Ryder, A safe approximate algorithm for interprocedural aliasing, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.235-248, June 15-19, 1992, San Francisco, California, United States
• 27: Thomas J. Marlowe , Barbara G. Ryder, An efficient hybrid algorithm for incremental data flow analysis, Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.184-196, December 1989, San Francisco, California, United States [doi>10.1145/96709.96728]
• 28: T. J. Marlowe , B. G. Ryder, Properties of data flow frameworks: a unified model, Acta Informatica, v.28 n.2, p.121-163, Dec. 1990 [doi>10.1007/BF01237234]
• 29: 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]
• 30: 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
• 31: Thomas Reps , Susan Horwitz , Mooly Sagiv, Precise interprocedural dataflow analysis via graph reachability, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.49-61, January 23-25, 1995, San Francisco, California, United States [doi>10.1145/199448.199462]
• 32: Thomas Reps , Tim Teitelbaum , Alan Demers, Incremental Context-Dependent Analysis for Language-Based Editors, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.3, p.449-477, July 1983 [doi>10.1145/2166.357218]
• 33: 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]
• 34: Barbara G. Ryder, Incremental data flow analysis, Proceedings of the 10th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.167-176, January 24-26, 1983, Austin, Texas [doi>10.1145/567067.567084]
• 35: Shmuel Sagiv , Thomas W. Reps , Susan Horwitz, Precise Interprocedural Dataflow Analysis with Applications to Constant Propagation, Proceedings of the 6th International Joint Conference CAAP/FASE on Theory and Practice of Software Development, p.651-665, May 22-26, 1995
• 36: SHARIR, M. AND PNUELI, t. 1981. Two approaches to interprocedural data flow analysis. In Program Flow Analysis: Theory and Applications, S. Muchnick and N. Jones, Eds. Prentice- Hall, Englewood Cliffs, N.J., 189-234.
• 37: Bjarne Steensgaard, Points-to analysis in almost linear time, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.32-41, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237727]
• 38: STOYENKO, A., MARLOWE, T., HALANG, W., AND YOUNIS, M. 1993. Enabling efficient schedulability analysis through conditional linking and program transformations. Control Eng. Pract. 1, 1, 85-105.
• 39: 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]
• 40: WEISER, M. 1984. Program slicing. IEEE Trans. Softw. Eng. Methodol. 10, 4 (July), 352-357.
• 41: Robert P. Wilson , Monica S. Lam, Efficient context-sensitive pointer analysis for C programs, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.1-12, June 18-21, 1995, La Jolla, California, United States
• 42: 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: Compilers

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software
          Subjects: Question-answering (fact retrieval) systems**

General Terms:
Algorithms, Experimentation, Performance

Keywords:
copy constant propagation, data flow analysis, def-use chains, demand-driven algorithms, distributive data flow frameworks, interprocedural data flow analysis, program optimizations