article

Free access

Fast static analysis of C++ virtual function calls

Authors:

David F. Bacon,

Peter F. SweeneyAuthors Info & Claims

ACM SIGPLAN Notices, Volume 31, Issue 10

Pages 324 - 341

https://doi.org/10.1145/236338.236371

Published: 01 October 1996 Publication History

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.

References

[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.]]

[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]]

Digital 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.]]

Digital 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.]]

[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.]]

Digital 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.]]

Digital 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.]]

[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.]]

Digital 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.]]

Digital 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.]]

Digital 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.]]

Digital 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.]]

Digital 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.]]

Digital 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. "]]

Digital 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.]]

Digital 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.]]

[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.]]

Digital 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.]]

Digital 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]]

Digital 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.]]

Digital 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.]]

Digital Library

[22]

SRrVASTAVA, A. Unreachable procedures in objectoriented programming. ACM Letters on Programming Languages and Systems I, 4 (December 1992), 355-364.]]

Digital Library

[23]

TIP, F., CHOI, J.-D., FIELD, J., AND R AMA- LINGAM, G. Slicing class hierarchies in C-~-~ Pubfished in these proceedings, 1996.]]

Digital 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.]]

Digital Library

Cited By

Zhang HPei YLiang SXing ZTan SChristakis MPradel M(2024)Characterizing and Detecting Program Representation Faults of Static Analysis FrameworksProceedings of the 33rd ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3650212.3680398(1772-1784)Online publication date: 11-Sep-2024
https://dl.acm.org/doi/10.1145/3650212.3680398
Cao YChen LChen ZZhong JZhang XWang L(2024)Efficient Construction of Practical Python Call Graphs with Entity Knowledge BaseInternational Journal of Software Engineering and Knowledge Engineering10.1142/S021819402450010434:07(999-1024)Online publication date: 22-May-2024
https://doi.org/10.1142/S0218194024500104
Kozak DJovanovic VStancu CVojnar TWimmer CBruno RMoss E(2023)Comparing Rapid Type Analysis with Points-To Analysis in GraalVM Native ImageProceedings of the 20th ACM SIGPLAN International Conference on Managed Programming Languages and Runtimes10.1145/3617651.3622980(129-142)Online publication date: 19-Oct-2023
https://dl.acm.org/doi/10.1145/3617651.3622980
Show More Cited By

Index Terms

Fast static analysis of C++ virtual function calls
1. Software and its engineering
  1. Software notations and tools
    1. Compilers
    2. General programming languages
      1. Language features
      2. Language types
        Object oriented languages
2. Theory of computation
  1. Semantics and reasoning
    1. Program constructs
      1. Type structures

Recommendations

Fast static analysis of C++ virtual function calls
OOPSLA '96: Proceedings of the 11th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications

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 ...
C++: The Design and Evolution of C++
Control-flow analysis of function calls and returns by abstract interpretation

Abstract interpretation techniques are used to derive a control-flow analysis for a simple higher-order functional language. The analysis approximates the interprocedural control-flow of both function calls and returns in the presence of first-class ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices

ACM SIGPLAN Notices Volume 31, Issue 10

Oct. 1996

443 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/236338

Chairmen:
Mary Loomis
Hewlett-Packard Labs.
,
Lougie Anderson
Sequent computer Systems
,
James Coplien
Bell Labs.

Issue’s Table of Contents

OOPSLA '96: Proceedings of the 11th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications
October 1996
458 pages
ISBN:089791788X
DOI:10.1145/236337
Chairmen:
Lougie Anderson
Sequent Computer Systems
,
James Coplien
Bell Labs.

Copyright © 1996 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 October 1996

Published in SIGPLAN Volume 31, Issue 10

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

411
Total Citations
View Citations
3,265
Total Downloads

Downloads (Last 12 months)464
Downloads (Last 6 weeks)69

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhang HPei YLiang SXing ZTan SChristakis MPradel M(2024)Characterizing and Detecting Program Representation Faults of Static Analysis FrameworksProceedings of the 33rd ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3650212.3680398(1772-1784)Online publication date: 11-Sep-2024
https://dl.acm.org/doi/10.1145/3650212.3680398
Cao YChen LChen ZZhong JZhang XWang L(2024)Efficient Construction of Practical Python Call Graphs with Entity Knowledge BaseInternational Journal of Software Engineering and Knowledge Engineering10.1142/S021819402450010434:07(999-1024)Online publication date: 22-May-2024
https://doi.org/10.1142/S0218194024500104
Kozak DJovanovic VStancu CVojnar TWimmer CBruno RMoss E(2023)Comparing Rapid Type Analysis with Points-To Analysis in GraalVM Native ImageProceedings of the 20th ACM SIGPLAN International Conference on Managed Programming Languages and Runtimes10.1145/3617651.3622980(129-142)Online publication date: 19-Oct-2023
https://dl.acm.org/doi/10.1145/3617651.3622980
Schoepe DSeekatz DStoilkovska IStucki STattersall DBolignano PRaimondi FChang B(2023)Lifting On-Demand Analysis to Higher-Order LanguagesStatic Analysis10.1007/978-3-031-44245-2_20(460-484)Online publication date: 24-Oct-2023
https://doi.org/10.1007/978-3-031-44245-2_20
Abadi AMakovitzki BShemer RTyszberowicz SHong JBures MPark JCerny T(2022)A lightweight approach for sound call graph approximationProceedings of the 37th ACM/SIGAPP Symposium on Applied Computing10.1145/3477314.3507126(1837-1844)Online publication date: 25-Apr-2022
https://dl.acm.org/doi/10.1145/3477314.3507126
Sagodi ZPengo EJasz JSiket IFerenc R(2022)Static Call Graph Combination to Simulate Dynamic Call Graph BehaviorIEEE Access10.1109/ACCESS.2022.322918210(131829-131840)Online publication date: 2022
https://doi.org/10.1109/ACCESS.2022.3229182
Kummita SPiskachev GSpath JBodden E(2021)Qualitative and Quantitative Analysis of Callgraph Algorithms for Python2021 International Conference on Code Quality (ICCQ)10.1109/ICCQ51190.2021.9392986(1-15)Online publication date: 27-Mar-2021
https://doi.org/10.1109/ICCQ51190.2021.9392986
Helm DKübler FReif MEichberg MMezini MDevanbu PCohen MZimmermann T(2020)Modular collaborative program analysis in OPALProceedings of the 28th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3368089.3409765(184-196)Online publication date: 8-Nov-2020
https://dl.acm.org/doi/10.1145/3368089.3409765
Bruce BZhang TArora JXu GKim MDevanbu PCohen MZimmermann T(2020)JShrink: in-depth investigation into debloating modern Java applicationsProceedings of the 28th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3368089.3409738(135-146)Online publication date: 8-Nov-2020
https://dl.acm.org/doi/10.1145/3368089.3409738
Xue YMa MLin YSui YYe JPeng TGrundy JLe Goues CLo D(2020)Cross-contract static analysis for detecting practical reentrancy vulnerabilities in smart contractsProceedings of the 35th IEEE/ACM International Conference on Automated Software Engineering10.1145/3324884.3416553(1029-1040)Online publication date: 21-Dec-2020
https://dl.acm.org/doi/10.1145/3324884.3416553
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents