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. 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. 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. 3.AGESEN, O. Concrete Type Inference: Delivering Object-Oriented Applications. PhD thesis, Stanford University, December 1995. Appeared as Sun Microsystems Laboratories Technical Report SMLI TR- 96-52.
4. 4.AGESEN, O., AND UNGAR, D. Sifting out the gold: Delivering compact applications from an exploratory object-oriented programming environment. In Proceedings of the Ninth Annual Conference on Object-Oriented Programming Systems, Languages, and Applications (OOPSLA '94) (Portland, OR, 1994), pp. 355-370. SIGPLAN Notices 29(10).
5. 5.AGr~WAL, H. On slicing programs with jump statements. In Proceedings of the ACM SIGPLAN'94 Conference on Programming Language Design and Implementation (Orlando, Florida, 1994), pp. 302-312. SIGPLAN Notices 29(6).
6. 6.AGRAWAL, H., DEMILLO, R., AND SPAFVORD, E. Dynamic slicing in the presence of unconstrained pointers. In Proceedings of the A CM Fourth Symposium on Testing, Analysis, and Verification (TA V4) (1991), pp. 60-73. Also Purdue University technical report SERC-TR-93-P.
7. 7.BACON, D. F., AND SWEENE~, P. F. Fast static analysis of C++ virtual function calls. In this proceedings.
8. 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. 9.BALL, T., AND HORWITZ, S. Slicing programs with arbitrary control-flow, in Proceedings of the First International Workshop on Automated and Algorithmic Debugging (1993), P. Fritzson, Ed., vol. 749 of Lecture Notes in Computer Science, Springer-Verlag, pp. 206- 222.
10. 10.CALDER, B., AND GRUNWALD, D. Reducing indirect function call overhead in C++ programs. Conference Record of the Twenty-First A CM Symposium on Principles of Programming Languages (January 1994), 397- 408.
11. 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. 12.Cnol, J.-D., AND FERRANTE, J. Static slicing in the presence ofgoto statements. A CM Transactions on Programming Languages and Systems 16, 4 (July 1994), 1097-1113.
13. 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. 14.ELLIS, M. A., AND STROUSTRUP, B. The Annotated C+ + Reference Manual. Addison-Wesley, 1990.
15. 15.ERNST, M. Practical fine-grained static slicing of optimized code. Tech. Rep. MSR-TR-94-14, Microsoft Research, Redmond, WA, 1994.
16. 16.FERNANDEZ, M. F. Simple and effective link-time optimization of modula-3 programs. Proceedings of the A CM SIGPLAN '95 Conference on Programming Language Design and Implementation (June 1995), 103- 115.
17. 17.FIELD, J., RAMALINGAM, G., AND TIP, F. Parametric program slicing. In Conference Record of the Twenty- Second ACM Symposium on Principles of Programming Languages (San Francisco, CA, 1995), pp. 379- 392.
18. 18.HORWITZ, S., REPS, T., AND BINKLEY, D. Interprocedural slicing using dependence graphs. ACM Transactions on Programming Languages and Systems 12, 1 (1990), 26-61.
19. 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. 20.LARSEN, L., AND HARROLD, M.J. Slicing objectoriented software. In Proceedings of the 1996 International Conference on Software Engineering (ICSE-18) (Berlin, March 1996).
21. 21.LIVADAS, P. E., AND CROLL, S. Program slicing. Report serc-tr-6 l-f, Computer Sciences Department, University of Florida, 1992.
22. 22.PALSBERG, J., AND SCHWARTZBACH, M. I. Objectoriented type inference. Proceedings of the ACM 1991 Conference on Object-Oriented Programming Systems, Languages, and Applications (OOPSLA "91) (October 1991), 146-161. ACM SIGPLAN Notices 26(11).
23. 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. 24.PLEVYAK, J., AND CHIEN, A.A. Precise concrete type inference for object-oriented languages. Proceedings of the A CA{ 1994 Conference on Object-Oriented Programming Systems, Languages, and Applications (00PSLA '94) (October 1994), 324-340. ACM SIG- PLAN Notices 29(10).
25. 25.REPS, T., HORWITZ, S., SAGIV, M., AND ROSAY, G. Speeding up slicing. In Proceedings of the Second A CM SIGSOFT Conference on Foundations of Software Engineering (New Orleans, LA, December 1994), pp. 11-20.
26. 26.ROSSIE, J. G., AND FRIEDMAN, D. P. An algebraic semantics of subobjects. In Proceedings of the Tenth Annual Conference on Object-Oriented Programming Systems, Languages, and Applications (OOPSLA'95) (Austin, TX, 1995), pp. 187-199. SIGPLAN Notices 30(10).
27. 27.SAKKINEN, M. A critique of the inheritance principles of C++. Computing Systems 5, I (1992), 69--I I0.
28. 28.SRIVASTAVA, A. Unreachable procedures in object oriented programming. A CM Letters on Programming Languages and Systems 1, 4 (December 1992), 355- 364.
29. 29.TIP, F. A survey of program slicing techniques. Journal of Programming Languages 3, 3 (1995), 121-189.
30. 30.WEISER, M. Program slices: formal, psychological, and practical investigations of an automatic program abstraction method. Phi) thesis, University of Michigan, Ann Arbor, 1979.

Index Terms

• Software and its engineering

  • Software notations and tools

    • General programming languages

      • Language features

        • Data types and structures

      • Language types

        • Object oriented languages

• Theory of computation

  • Semantics and reasoning

    • Program constructs

      • Type structures