David F. Bacon
Peter F. Sweeney
ABSTRACT
Virtual functions make code easier for programmers to reuse but also make it harder for compilers to analyze. We investigate the ability of three static analysis algorithms to improve C++ programs by resolving virtual function calls, thereby reducing compiled code size and reducing program complexity so as to improve both human and automated program understanding and analysis. In measurements of seven programs of significant size (5000 to 20000 lines of code each) we found that on average the most precise of the three algorithms resolved 71% of the virtual function calls and reduced compiled code size by 25%. This algorithm is very fast: it analyzes 3300 source lines per second on an 80 MHz PowerPC 601. Because of its accuracy and speed, this algorithm is an excellent candidate for inclusion in production C++ compilers.
- 1.AGESEN, O. Constraint-based type inference and parametric polymorphism. In Proceedings of the First International Static Analysis Symposium (Namur, Belgium, Sept. 1994), B. Le Charlier, Ed., Springer-Verlag, pp. 78-100.]]Google Scholar
Cross Ref
- 2.AGESEN, O., AND H6LZLE, U. Type feedback vs. concrete type inference: A comparison of optimization techniques for object-oriented languages. In Proceedings of the 1995 A CM Conference on Object Oriented Programming Systems, Languages, and Applications (OOPSI, A) (Austin, Texas, Oct. 1995), ACM Press, New York, New York, pp. 91- 107]] Google ScholarDigital Library
- 3.AIGNER, G., AND H6LZLE, U. Eliminating virtual function calls in C++ programs. In Proceedings of the Tenth European Conference on Object-Oriented Programming- ECOOP'96 (Linz, Austria, July 1996), vol. 1098 of Lecture No~es in Computer Science, Springer-Verlag, pp. 142-166.]] Google ScholarDigital Library
- 4.BACON, D. F., WEGMAN, M., AND ZADECK, K. Rapid type analysis for C++. Tech. Rep. RC number pending, IBM Thomas J. Watson Research Center, 1996.]]Google Scholar
- 5.BURKE, M., CArUNI, P., CHOI, J.-D., AND HIND, M. Flow-insensitive interprocedural alias analysis in the presence of pointers, in Proceedings of the Seventh International Workshop on Languages and Compilers for Parallel Computing (Ithaca, New York, Aug. 1994), K. Pingali, U. Banerjee, D. Gelernter, A. Nicolau, and D. Padua, Eds., vol. 892 of Lecture No~es in Computer Science, Springer- Verlag, Berlin, Germany, pp. 234-250.]] Google ScholarDigital Library
- 6.CALDER, B., AND GKUNWALD, D. Reducing indirect function call overhead in C++ programs. In Conference Record of the Twenty-First A CM Symposium on Pmnciples of Programmzn# Languages (POPL} (Portland, Oregon, Jan. 1994), ACM Press, New York, New York~ pp. 397-408.]] Google ScholarDigital Library
- 7.CARINI, P., HIND, M., AND SRINIVASAN, H. Type analysis algorithm for C++. Tech. Rep. RC 20267, IBM Thomas J. Watson Research Center, 1995.]]Google Scholar
- 8.CHAMBERS, C., AND U NGAR, D. Iterative type analysis and extended message splitting: opti,nizing dynamically-typed object-oriented programs. LISP and Symbolic Computation 4, 3 (July 1991), 283-310.]] Google ScholarDigital Library
- 9.CHAMBERS, C., UNGAR, D., AND LEE, E. An efficient implementation of SELF, a dynamicallytyped object-oriented language based on prototypes. LISP and Symbolic Computation 4, 3 (July 1991), 243-281.]] Google ScholarDigital Library
- 10.CHOI, J.-D., BURKE, M., AND CARINI, P. Efficient flow-sensitive interprocedural computation of pointer-induced aliases and side effects. In Conference Record of the Twentieth ACM Symposium on Principles of Programming Languages ~POPL) (Charleston, South Carolina, Jan. 1993), ACM Press, New York, New York, pp. 232-245.]] Google ScholarDigital Library
- 11.DEAN, J., GROVE, D., AND CHAMBERS, C. Optimization of object-oriented programs using static class hierarchy analysis. In Proceedings of the Ninth European Conference on Object-Oriented Programming - ECOOP'95 (Aarhus, Denmark, Aug. 1995), W. Olthoff, Ed., Springer-Verlag, pp. 77-101.]] Google ScholarDigital Library
- 12.DIWAN, A., Moss, J. E. B., AND MCKINLEY, K. S. Simple and effective analysis of staticallytyped object-oriented programs. Published in these proceedings, 1996.]] Google ScholarDigital Library
- 13.FERNANDEZ, M. F. Simple and effective link-time optimization of Modula-3 programs. In Proceedings of $he SIGPLAN Conference on Programming Language. Des~gn and lmplementahon (PLDI) (La Joila, California, June 1995), ACM Press, New York, New York, pp. 103-115.]] Google ScholarDigital Library
- 14.H()LZLE, U., CHAMBERS, C., AND UNGAR, D. Optimizing dynamically-types object-oriented {an~ guages with polymorpflic inline caches. In Proceedings of the European Conference on Object- Omented Programming - ECOOP '91 (Geneva, Switzerland, July 1991), P. America, Ed., Springer- Verlag, pp. 21-38. "]] Google ScholarDigital Library
- 15.LANDI, W., RYDER, B~ G., AND ZHANG, S. Interprocedural modification side effect analysis with pointer aliasing. In Proceedings of the SIGPLAN Conference on Programming Language Deszgn and Implementation {PLDI) (Albuquerque, New Mexico, June 1993)~ ACM Press, New York, New York, pp. 56-67.]] Google ScholarDigital Library
- 16.LEE, Y., AND SERRANO, M. J. Dynamic measurements of C++ program characteristics. Tech. Rep. ADTI-1995-001, IBM Santa Teresa Laboratory, Jan. 1995.]]Google Scholar
- 17.OXHOJ, N., PALSBERG, jr., AND SCHWARTZBACH, M. I. Making type inference practical. In Proceedings of the European Conference on Object- Oriented Programming - ECOOP'92 (Utrecht, Netherlands, June 1992), O. L. Madsen, Ed., Springer-Verlag, pp. 329-349.]] Google ScholarDigital Library
- 18.PANDE, H. D., AND RYDER, B. G. Static type determination for C++. In Proceedings of the Sixth Useniz C-t-+ Technical Conference (Apr. 1994), pp. 85-97.]] Google ScholarDigital Library
- 19.PANDE, H. D., AND RYDER, S. G. Data-flowbased virtual function resolution. In Proceedings of the International Static Analysis Symposium (1996), Lecture Notes in Computer Science, Springer-Verlag]] Google ScholarDigital Library
- 20.PLEVYAK, j., AND CHIEN, A. A. Precise concrete type inference for object-oriented languages. In Proceedings of the 1994 A CM Conference on Object Oriented Programming Systems, Languages, and Applications (OOPSLA) (Portland, OR, Oct. 1994), ACM Press, New York, New York, pp. 324- 340.]] Google ScholarDigital Library
- 21.PORAT, S., BERNSTEIN, D., FEDOROV, Y., AND RODRIGUE, J. Compiler optimizations of C+~ virtual function calls. In Proceedings of the Second Conference on Object-Oriented Technologies and Systems (Toronto, Canada, June 1996), Usenix Association, pp. 3-14.]] Google ScholarDigital Library
- 22.SRrVASTAVA, A. Unreachable procedures in objectoriented programming. ACM Letters on Programming Languages and Systems I, 4 (December 1992), 355-364.]] Google ScholarDigital Library
- 23.TIP, F., CHOI, J.-D., FIELD, J., AND R AMA- LINGAM, G. Slicing class hierarchies in C-~-~ Pubfished in these proceedings, 1996.]] Google ScholarDigital Library
- 24.UNGAR, D., SMITH, R. B.~ CHAMBERS, C., AND HOLZLE, U. Object, message, and performance: how they coexist in Self. Computer 25, 10 (()ct. 1992), 53-64.]] Google ScholarDigital Library
Index Terms
- Fast static analysis of C++ virtual function calls
Recommendations
Fast static analysis of C++ virtual function calls
Virtual functions make code easier for programmers to reuse but also make it harder for compilers to analyze. We investigate the ability of three static analysis algorithms to improve C++ programs by resolving virtual function calls, thereby reducing ...
Comments