Slicing class hierarchies in C++

ABSTRACT

This paper describes an algorithm for slicing class hierarchies in C++ programs. Given a C++ class hierarchy (a collection of C++ classes and inheritance relations among them) and a program P that uses the hierarchy, the algorithm eliminates from the hierarchy those data members, member functions, classes, and inheritance relations that are unnecessary for ensuring that the semantics of P is maintained.Class slicing is especially useful when the program P is generated from a larger program P' by a statement slicing algorithm. Such an algorithm eliminates statements that are irrelevant to a set of slicing criteria---program points of particular interest. There has been considerable previous work on statement slicing, and it will not be the concern of this paper. However, the combination of statement slicing and class slicing for C++ has two principal applications: First, class slicing can enhance statement slicing's utility in program debugging and understanding applications, by eliminating both executable and declarative program components irrelevant to the slicing criteria. Second, the combination of the two slicing algorithms can be used to decrease the space requirements of programs that do not use all the components of a class hierarchy. Such a situation is particularly common in programs that use class libraries.

REFERENCES

• 1: ACCREDITED STANDARDS COMMITTEE X3, I. P. S. Working paper for draft proposed international standard for information systems---programming language C++. Draft of 26 september 1995.
• 2: AGESEN, O. Constraint-based type inference and parametric polymorphism. Proceedings of the First International Static Analysis Symposium (SAS'94) (September 1994), 78--I00. Springer-Verlag LNCS vol. 864.
• 3: Ole Agesen, Concrete type inference: delivering object-oriented applications, Stanford University, Stanford, CA, 1996
• 4: Ole Agesen , David Ungar, Sifting out the gold: delivering compact applications from an exploratory object-oriented programming environment, ACM SIGPLAN Notices, v.29 n.10, p.355-370, Oct. 1994
• 5: 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
• 6: Hiralal Agrawal , Richard A. DeMillo , Eugene H. Spafford, Dynamic slicing in the presence of unconstrained pointers, Proceedings of the symposium on Testing, analysis, and verification, p.60-73, October 08-10, 1991, Victoria, British Columbia, Canada [doi>10.1145/120807.120813]
• 7: David F. Bacon , Peter F. Sweeney, Fast static analysis of C++ virtual function calls, Proceedings of the 11th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.324-341, October 06-10, 1996, San Jose, California, United States
• 8: BACON, D. F., WEGMAN, M., AND ZADECK, F. K. Rapid type inference for C++. Tech. Rep. RC 1234, IBM Thomas J. Watson Research Center, 1995.
• 9: 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
• 10: Brad Calder , Dirk Grunwald, Reducing indirect function call overhead in C++ programs, Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.397-408, January 16-19, 1994, Portland, Oregon, United States [doi>10.1145/174675.177973]
• 11: CARINI, P. R., HIND, M., AND SRINIVASAN, H. Flowsensitive type analysis for C++. Tech. Rep. RC 20267, IBM T.J. Watson Research Center, 1995.
• 12: 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]
• 13: DEAN, j., AND CHAMBERS, C. Optimization of objectoriented programs using static class hierarchy analysis. Tech. Rep. 94-12-01, Department of Computer Science, University of Washington at Seattle, December 1994.
• 14: Margaret A. Ellis , Bjarne Stroustrup, The annotated C++ reference manual, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 15: ERNST, M. Practical fine-grained static slicing of optimized code. Tech. Rep. MSR-TR-94-14, Microsoft Research, Redmond, WA, 1994.
• 16: Mary F. Fernández, Simple and effective link-time optimization of Modula-3 programs, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.103-115, June 18-21, 1995, La Jolla, California, United States
• 17: John Field , G. Ramalingam , Frank Tip, Parametric program slicing, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.379-392, January 23-25, 1995, San Francisco, California, United States [doi>10.1145/199448.199534]
• 18: 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]
• 19: KRISHNASWAM~, A. Program slicing: An application of object-oriented program dependency graphs. Technical report TR94-108, Dept. of Computer Science, Clemson University, 1994.
• 20: Loren Larsen , Mary Jean Harrold, Slicing object-oriented software, Proceedings of the 18th international conference on Software engineering, p.495-505, March 25-29, 1996, Berlin, Germany
• 21: LIVADAS, P. E., AND CROLL, S. Program slicing. Report serc-tr-6 l-f, Computer Sciences Department, University of Florida, 1992.
• 22: Jens Palsberg , Michael I. Schwartzbach, Object-oriented type inference, ACM SIGPLAN Notices, v.26 n.11, p.146-161, Nov. 1991
• 23: PANDE, H. D., AND RYOER, B. G. Static type determination and aliasing for C++. Report LCSR-TR-250-A, Rutgers University, October 1995.
• 24: John Plevyak , Andrew A. Chien, Precise concrete type inference for object-oriented languages, ACM SIGPLAN Notices, v.29 n.10, p.324-340, Oct. 1994
• 25: 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
• 26: Jonathan G. Rossie, Jr. , Daniel P. Friedman, An algebraic semantics of subobjects, ACM SIGPLAN Notices, v.30 n.10, p.187-199, Oct. 17, 1995
• 27: SAKKINEN, M. A critique of the inheritance principles of C++. Computing Systems 5, I (1992), 69--I I0.
• 28: Amitabh Srivastava, Unreachable procedures in object-oriented programming, ACM Letters on Programming Languages and Systems (LOPLAS), v.1 n.4, p.355-364, Dec. 1992 [doi>10.1145/161494.161517]
• 29: TIP, F. A survey of program slicing techniques. Journal of Programming Languages 3, 3 (1995), 121-189.
• 30: Mark David Weiser, Program slices: formal, psychological, and practical investigations of an automatic program abstraction method, 1979

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: C++
      D.3.3 Language Constructs and Features
          Subjects: Data types and structures

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.3 Studies of Program Constructs
          Subjects: Type structure

General Terms:
Algorithms, Languages, Performance, Theory