Interprocedural slicing using dependence graphs

ABSTRACT

The notion of a program slice, originally introduced by Mark Weiser, is useful in program debugging, automatic parallelization, and program integration. A slice of a program is taken with respect to a program point p and a variable x; the slice 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. (It should be noted that our work concerns a somewhat restricted kind of slice: rather than permitting a program to b e sliced with respect to program point p and an arbitrary variable, a slice must be taken with respect to a variable that is defined or used at p.) 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 dependences 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: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 2: BAmCH, W. A., AND JAZAYERI, M. The method of attributes for data flow analysis: Part II. Demand analysis. Acta Inf. 10, 3 (Oct. 1978), 265-272.
• 3: BADGER, L., AND WEISER, M. Minimizing communication for synchronizing parallel dataflow programs. In Proceedings of the 1988 International Conference on Parallel Processing (St. Charles, IL, Aug. 15-19, 1988). Pennsylvania State University Press, University Park, PA, 1988.
• 4: 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]
• 5: 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
• 6: 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
• 7: 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]
• 8: HORWITZ, S., PRINS, J., AND REPS, T. Integrating non-interfering versions of programs. TR-690, Computer Sciences Dept., Univ. of Wisconsin, Madison, March 1987.
• 9: S. Horwitz , J. Prins , T. Reps, On the adequacy of program dependence graphs for representing programs, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.146-157, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73573]
• 10: S. Horwitz , T. Reps , D. Binkley, Interprocedural slicing using dependence graphs, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.35-46, June 20-24, 1988, Atlanta, Georgia, United States
• 11: Susan Horwitz , Jan Prins , Thomas Reps, Integrating noninterfering versions of programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.11 n.3, p.345-387, July 1989 [doi>10.1145/65979.65980]
• 12: HWANG, J. C., nu, M. W., AND CHOU, C.a. Finding program slices for recursive procedures. In Proceedings of the IEEE COMPSAC 88 (Chicago, Oct. 3-7, 1988). IEEE Computer Society, Washington, D.C., 1988.
• 13: KASTENS, U. Ordered attribute grammars. Acta Inf. 13, 3 (1980), 229-256.
• 14: KNUTH, D. E. Semantics of context-free languages. Math. Syst. Theor. 2, 2 (June 1968), 127-145.
• 15: 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]
• 16: 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. Comput. C-21, 12 (Dec. 1972), 1293-1310.
• 17: Mark Weiser , Jim Lyle, Experiments on slicing-based debugging aids, Papers presented at the first workshop on empirical studies of programmers on Empirical studies of programmers, p.187-197, June 1986, Washington, D.C., United States
• 18: 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]
• 19: 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
• 20: REPS, T., AND YANG, W. The semantics of program slicing. TR-777, Computer Sciences Dept., Univ. of Wisconsin, Madison, June 1988.
• 21: WEISER, M. Reconstructing sequential behavior from parallel behavior projections. Inf. Process. Lett. 17 (Oct. 1983), 129-135.
• 22: WEmER, M. Program slicing. IEEE Trans. Softw. Eng. SE-IO, 4 (July 1984), 352-357.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.3 Studies of Program Constructs
          Subjects: Program and recursion schemes

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.2 Grammars and Other Rewriting Systems
          Subjects: Grammar types (e.g., context-free, context-sensitive)

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Design