Interprocedural slicing using dependence graphs

ABSTRACT

A slice of a program with respect to a program point p and variable x consists of all statements of the program that might affect the value of x at point p. This paper concerns the problem of interprocedural slicing -- generating a slice of an entire program, where the slice crosses the boundaries of procedure calls. To solve this problem, we introduce a new kind of graph to represent programs, called a system dependence graph, which extends previous dependence representations to incorporate collections of procedures (with procedure calls) rather than just monolithic programs. Our main result is an algorithm for interprocedural slicing that uses the new representation.The chief difficulty in interprocedural slicing is correctly accounting for the calling context of a called procedure. To handle this problem, system dependence graphs include some data-dependence edges that represent transitive dependencies due to the effects of procedure calls, in addition to the conventional direct-dependence edges. These edges are constructed with the aid of an auxiliary structure that represents calling and parameter-linkage relationships. This structure takes the form of an attribute grammar. The step of computing the required transitive-dependence edges is reduced to the construction of the subordinate characteristic graphs for the grammar's nonterminals.

REFERENCES

• 1: Hiralal Agrawal, On slicing programs with jump statements, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.302-312, June 20-24, 1994, Orlando, Florida, United States
• 2: Thomas Ball , Susan Horwitz, Slicing Programs with Arbitrary Control-flow, Proceedings of the First International Workshop on Automated and Algorithmic Debugging, p.206-222, May 03-05, 1993
• 3: Thomas Ball , Sriram K. Rajamani, Bebop: a path-sensitive interprocedural dataflow engine, Proceedings of the 2001 ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, p.97-103, June 2001, Snowbird, Utah, United States [doi>10.1145/379605.379690]
• 4: Utpal Banerjee, Speedup of ordinary programs, 1979
• 5: Michael Benedikt , Patrice Godefroid , Thomas W. Reps, Model Checking of Unrestricted Hierarchical State Machines, Proceedings of the 28th International Colloquium on Automata, Languages and Programming,, p.652-666, July 08-12, 2001
• 6: David Wendell Binkley, Multi-procedure program integration, University of Wisconsin at Madison, Madison, WI, 1992
• 7: David Binkley, Precise executable interprocedural slices, ACM Letters on Programming Languages and Systems (LOPLAS), v.2 n.1-4, p.31-45, March–Dec. 1993 [doi>10.1145/176454.176473]
• 8: D. Callahan, The program summary graph and flow-sensitive interprocedual data flow analysis, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.47-56, June 20-24, 1988, Atlanta, Georgia, United States
• 9: David Callahan , Keith D. Cooper , Ken Kennedy , Linda Torczon, Interprocedural constant propagation, Proceedings of the 1986 SIGPLAN symposium on Compiler construction, p.152-161, June 25-27, 1986, Palo Alto, California, United States
• 10: David R. Chase , Mark Wegman , F. Kenneth Zadeck, Analysis of pointers and structures, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.296-310, June 1990, White Plains, New York, United States
• 11: Jong-Deok Choi , Jeanne Ferrante, Static slicing in the presence of goto statements, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.4, p.1097-1113, July 1994 [doi>10.1145/183432.183438]
• 12: 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
• 13: P. Cousot and R. Cousot. Static determination of dynamic properties of recursive procedures. In E. J. Neuhold, editor, Formal Descriptions of Programming Concepts, (IFIP WG 2.2, St. Andrews, Canada, August 1977), pages 237--277. North-Holland, 1978.
• 14: Manuvir Das , Sorin Lerner , Mark Seigle, ESP: path-sensitive program verification in polynomial time, Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, June 17-19, 2002, Berlin, Germany
• 15: M. B. Dwyer, J. C. Corbett, J. Hatcliff, S. Sokolowski, and H. Zheng. Slicing multi-threaded Java programs: A case study. Tech. Rep. 99-7, Dept. of Comp. and Inf. Sci., Kansas State Univ., Manhattan, KS, February 1999.
• 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: Jeanne Ferrante , Karl J. Ottenstein , Joe D. Warren, The program dependence graph and its use in optimization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.3, p.319-349, July 1987 [doi>10.1145/24039.24041]
• 18: Gina Goff , Ken Kennedy , Chau-Wen Tseng, Practical dependence testing, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.15-29, June 24-28, 1991, Toronto, Ontario, Canada
• 19: S. Horwitz , P. Pfeiffer , T. Reps, Dependence analysis for pointer variables, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.28-40, June 19-23, 1989, Portland, Oregon, United States
• 20: Susan Horwitz , Thomas Reps , David Binkley, Interprocedural slicing using dependence graphs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.1, p.26-60, Jan. 1990 [doi>10.1145/77606.77608]
• 21: 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
• 22: S. Horwitz, T. Reps, and M. Sagiv. Demand interprocedural dataflow analysis. report TR-1283, Comp. Sci. Dept., Univ. of Wisconsin, August 1995. Available at "http://www.cs.wisc.edu/wpis/papers/tr1283r.ps".
• 23: Thomas Reps , Susan Horwitz , Mooly Sagiv , Genevieve Rosay, Speeding up slicing, Proceedings of the 2nd ACM SIGSOFT symposium on Foundations of software engineering, p.11-20, December 06-09, 1994, New Orleans, Louisiana, United States
• 24: U. Kastens. Ordered attribute grammars. Acta Inf., 13(3):229--256, 1980.
• 25: D.E. Knuth. Semantics of context-free languages. Math. Syst. Theory, 2:127--145, 1968.
• 26: Jens Krinke, Static slicing of threaded programs, Proceedings of the 1998 ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, p.35-42, June 16-16, 1998, Montreal, Quebec, Canada
• 27: Sumit Kumar , Susan Horwitz, Better Slicing of Programs with Jumps and Switches, Proceedings of the 5th International Conference on Fundamental Approaches to Software Engineering, p.96-112, April 08-12, 2002
• 28: J. R. Larus , P. N. Hilfinger, Detecting conflicts between structure accesses, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.24-31, June 20-24, 1988, Atlanta, Georgia, United States
• 29: Dror E. Maydan , John L. Hennessy , Monica S. Lam, Efficient and exact data dependence analysis, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.1-14, June 24-28, 1991, Toronto, Ontario, Canada
• 30: Mangala Gowri Nanda , S. Ramesh, Slicing concurrent programs, Proceedings of the 2000 ACM SIGSOFT international symposium on Software testing and analysis, p.180-190, August 21-24, 2000, Portland, Oregon, United States
• 31: Karl J. Ottenstein , Linda M. Ottenstein, The program dependence graph in a software development environment, Proceedings of the first ACM SIGSOFT/SIGPLAN software engineering symposium on Practical software development environments, p.177-184, April 1984
• 32: William Pugh , David Wonnacott, Eliminating false data dependences using the Omega test, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.140-151, June 15-19, 1992, San Francisco, California, United States
• 33: G. Ramalingam, Context-sensitive synchronization-sensitive analysis is undecidable, ACM Transactions on Programming Languages and Systems (TOPLAS), v.22 n.2, p.416-430, March 2000 [doi>10.1145/349214.349241]
• 34: Jakob Rehof , Manuel Fähndrich, Type-base flow analysis: from polymorphic subtyping to CFL-reachability, Proceedings of the 28th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.54-66, January 2001, London, United Kingdom
• 35: T. Reps. Demand interprocedural program analysis using logic databases. In R. Ramakrishnan, editor, Applications of Logic Databases. Kluwer Academic Publishers, 1994.
• 36: Thomas Reps, Shape analysis as a generalized path problem, Proceedings of the 1995 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.1-11, June 21-23, 1995, La Jolla, California, United States [doi>10.1145/215465.215466]
• 37: T. Reps. On the sequential nature of interprocedural program-analysis problems. Acta Inf., 33:739--757, 1996.
• 38: T. Reps. Program analysis via graph reachability. Inf. and Softw. Tech., 40(11--12):701--726, November 1998.
• 39: Thomas Reps, Undecidability of context-sensitive data-independence analysis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.22 n.1, p.162-186, Jan. 2000 [doi>10.1145/345099.345137]
• 40: T. Reps, S. Horwitz, and D. Binkley, U.S. Patent Number 5,161,216, Interprocedural slicing of computer programs using dependence graphs, November 1992.
• 41: 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]
• 42: Thomas Reps , Genevieve Rosay, Precise interprocedural chopping, Proceedings of the 3rd ACM SIGSOFT symposium on Foundations of software engineering, p.41-52, October 12-15, 1995, Washington, D.C., United States
• 43: T. Reps, M. Sagiv, and S. Horwitz. Interprocedural dataflow analysis via graph reachability. Tech. Rep. TR 94-14, Datalogisk Institut, Univ. of Copenhagen, 1994. Available at "http://www.cs.wisc.edu/wpis/papers/diku-tr94-14.ps".
• 44: Mooly Sagiv , Thomas Reps , Susan Horwitz, Precise interprocedural dataflow analysis with applications to constant propagation, Theoretical Computer Science, v.167 n.1-2, p.131-170, Oct. 30, 1996
• 45: M. Sharir and A. Pnueli. Two approaches to interprocedural data flow analysis. In S. S. Muchnick and N. D. Jones, editors, Program Flow Analysis: Theory and Applications, chapter 7, pages 189--234. Prentice-Hall, Englewood Cliffs, NJ, 1981.
• 46: Saurabh Sinha , Mary Jean Harrold , Gregg Rothermel, System-dependence-graph-based slicing of programs with arbitrary interprocedural control flow, Proceedings of the 21st international conference on Software engineering, p.432-441, May 16-22, 1999, Los Angeles, California, United States [doi>10.1145/302405.302675]
• 47: Mark Weiser, Program slicing, Proceedings of the 5th international conference on Software engineering, p.439-449, March 09-12, 1981, San Diego, California, United States
• 48: M. Weiser. Program slicing. Trans. on Softw. Eng., SE-10(4):352--357, July 1984.
• 49: 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
• 50: Michael Joseph Wolfe, Optimizing supercompilers for supercomputers, 1982
• 51: Mihalis Yannakakis, Graph-theoretic methods in database theory, Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.230-242, April 02-04, 1990, Nashville, Tennessee, United States [doi>10.1145/298514.298576]
• 52: Babich78. Babich, W. A. and Jazayeri, M., "The method of attributes for data flow analysis: Part II. Demand analysis," Acta Informatica 10(3) pp. 265--272 (October 1978).
• 53: 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]
• 54: D. Callahan, The program summary graph and flow-sensitive interprocedual data flow analysis, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.47-56, June 20-24, 1988, Atlanta, Georgia, United States
• 55: 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
• 56: Jeanne Ferrante , Karl J. Ottenstein , Joe D. Warren, The program dependence graph and its use in optimization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.3, p.319-349, July 1987 [doi>10.1145/24039.24041]
• 57: Horwitz87. Horwitz, S., Prins, J., and Reps, T., "Integrating non-interfering versions of programs," TR-690, Computer Sciences Department, University of Wisconsin, Madison, WI (March 1987).
• 58: S. Horwitz , J. Prins , T. Reps, Integrating non-intering versions of programs, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.133-145, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73572]
• 59: Horwitz88a. Horwitz, S., Reps, T., and Binkley, D., "Interprocedural slicing using dependence graphs," TR-756, Computer Sciences Department, University of Wisconsin, Madison, WI (March 1988).
• 60: Kastens80. Kastens, U., "Ordered attribute grammars," Acta Inf. 13(3) pp. 229--256 (1980).
• 61: Knuth68. Knuth, D. E., "Semantics of context-free languages," Math. Syst. Theory 2(2) pp. 127--145 (June 1968).
• 62: Lawrence T. Kou, On Live-Dead Analysis for Global Data Flow Problems, Journal of the ACM (JACM), v.24 n.3, p.473-483, July 1977 [doi>10.1145/322017.322027]
• 63: Kuck72. Kuck, D. J., Muraoka, Y., and Chen, S. C., "On the number of operations simultaneously executable in FORTRAN-like programs and their resulting speed-up," IEEE Trans. on Computers C-21(12) pp. 1293--1310 (December 1972).
• 64: 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]
• 65: Karl J. Ottenstein , Linda M. Ottenstein, The program dependence graph in a software development environment, ACM SIGPLAN Notices, v.19 n.5, p.177-184, May 1984
• 66: Reps88. Reps, T. and Yang, W., "The semantics of program slicing," Tech. Rep. in preparation, Computer Sciences Department, University of Wisconsin, Madison, WI (Spring 1988).
• 67: Waite83. Waite, W. M. and Goos, G., Compiler Construction, Springer-Verlag, New York (1983).
• 68: Weiser84. Weiser, M., "Program slicing," IEEE Transactions on Software Engineering SE-10(4) pp. 352--357 (July 1984).