Skip to main content
SpringerLink
Log in

The complexity of type analysis of object oriented programs

  • Conference paper
  • First Online:
ECOOP’98 — Object-Oriented Programming (ECOOP 1998)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 1445))

Included in the following conference series:

Abstract

One of the price tags attached to the blessings that OO brings about is a drop in efficiency due to dynamic method dispatch. Much research effort is being spent on the problem of eliminating it, by applying static analysis to predict the set of dynamic types which a variable might store at any given program location. It was previously shown that the problem is NP-hard even if the program under analysis has no multi-level pointers. In this work, we show that under similar conditions, the problem is P-SPACE complete, provided that the program is not recursive. In the presence of recursion, the problem becomes EXP-TIME complete. (These two results also give an exponential time algorithm for a family of type analysis problems.) If multi-level pointers are allowed then the problem becomes EXP-SPACE complete without recursion and DEXP-TIME with it. Further, if the program under analysis may use recursive data structures then the problem becomes undedicable. Despite these, somewhat discouraging, results, we can prove that the type analysis becomes tractable, as evident from past practical experience, if the program under analysis obeys some few simple software engineering rules, while the analysis algorithm makes a corresponding simplifying assumption.

on Sabbatical leave from the Technion

contact author

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. Barth J., A Practical Interprocedural Data Flow Analysis Algorithm, CACM 21(9):724–736, 1978.

    Google Scholar 

  2. Bacon, D. F., and P. F. Sweeney, Fast Static Analysis of Virtual Function Calls in C++, OOPSLA'96, pp. 324–341.

    Google Scholar 

  3. Cook S. A., Characterizations of Pushdown Machines in Terms of Time-Bounded Computers, JACM 18(1):4–18, Jan. 1971.

    Article  MATH  Google Scholar 

  4. Carini P. R. and M. Hind, Flow-sensitive interprocedural constant propagation, PLDI'95, pp. 23–31.

    Google Scholar 

  5. Chambers C., Grove D., DeFouw G., and J. Dean, Call Graph Construction in Object-Oriented Languages, OOPSLA'97, pp. 108–124.

    Google Scholar 

  6. Dean J., Grove D. and C. Chambers, Optimization of Object-Oriented Programs Using Static Class Hierachy Analysis, ECOOP'95, pp. 77–101.

    Google Scholar 

  7. Diwan, A., Moss J. E. B. and K. S. McKinley, Simple and Effective Analysis of Statically-Typed Object-Oriented Programmes., OOPSLA'96, pp. 292–305.

    Google Scholar 

  8. Johnson, D.S., A Catalog of Complexity Classes, in Handbook of Theoretical Computer Science, ed. J.van Leuuwen, MIT Press 1990.

    Google Scholar 

  9. Golubski W., Data-Flow Analysis in Object-Oriented Programs, TOOLS USA'97.

    Google Scholar 

  10. Golubski W. and B. Pohlers, SOLAT — A Simple Object-Oriented Language Analysing Tool, TOOLS USA'97.

    Google Scholar 

  11. Harrison, T. H., Levine D. L., and D. C. Schimdt., The Design and Performance of a Real-Time COBRA Event Service, OOPSLA'97, pp. 184–200.

    Google Scholar 

  12. Horwitz S., Precise Flow-Insensitive May-Alias Analysis is NP-Hard, TOPLAS Jan. 1997.

    Google Scholar 

  13. Holzle U., Chambers C. and D. Ungar., Optimizing Dynamically-Typed Object-Oriented Languages with Polymorphic Inline Caches. ECOOP'91.

    Google Scholar 

  14. Hopcroft, J.E., and J. D. Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley 1979.

    Google Scholar 

  15. Landi W., Undecidability of Static Analysis, LOPLAS 1(4):323–337, Dec. 1992.

    Article  Google Scholar 

  16. Meyer B., Eiffel-The Language, Prentice-Hall, 1992.

    Google Scholar 

  17. Meyer B., Beware of Polymorphic Catcalls, White paper, Interactive Software Engineering, 1995. In http://www.eiffel.com/doc/manuals/technology/typing/cat.html

    Google Scholar 

  18. Muchnick S. S., and N. D. Jones eds., Program Flow Analysis: Theory and Applications, Prentice Hall 1981.

    Google Scholar 

  19. Nygaard K. and O-J Dahl, Simula 1967, In History of Prog. Lang., ed. R. W. Wexelblat, 1981.

    Google Scholar 

  20. Porat S., Bernstein D., Fedrov Y., and J. Rodrigue, Compiler Optimization of C++ Virtual Function Call, COOTS'96, pp. 3–14.

    Google Scholar 

  21. Pande H. D. and B. G. Ryder, Static Type Determination for C++, Usenix C++ Conf. 1994, pp. 85–97.

    Google Scholar 

  22. Palsberg J. and M. Schwartzbach, Object-Oriented Type Inference, OOSPLA'91,pp. 146–161.

    Google Scholar 

  23. Stroustrup B., The C++ Programming Language. 3rd ed. Addison Wesley, 1997.

    Google Scholar 

  24. Sharir M. and A. Pnueli, Two Approaches to Interprocedural Data Flow Analysis, in [MJ81].

    Google Scholar 

  25. Verbrugge, C., Phong C., and L. Hendren. Generalized Constant Propagation—A Study in C. In Proc. of the 6th International Conference on Compiler Construction (CC'96), pages 74–90, Link• ping, Sweden, Springer LNCS 1060, 1996.

    Google Scholar 

  26. Wegman, M. N. and F. K. Zadek, Constant Propagation with Conditional Branches, ACM TOPLAS 13(2):181–210, Apr. 1991.

    Article  Google Scholar 

  27. Zendra O., Colnet C, and S. Collin, Efficient Dynamic Dispatch without Virtual Function Tables: The Small Eiffel Compiler, OOPSLA'97, pp. 125–141.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. IBM T.J. Watson Research Center, P.O. Box 704, 10598, Yorktown Heights, NY, USA

    Joseph (Yossi) Gil

  2. Department of Computer Science, Technion-Israel Institute of Technology, 32000, Haifa, Israel

    Alon Itai

Authors
  1. Joseph (Yossi) Gil
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Alon Itai
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Eric Jul

Rights and permissions

Reprints and permissions

Copyright information

© 1998 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Gil, J.(., Itai, A. (1998). The complexity of type analysis of object oriented programs. In: Jul, E. (eds) ECOOP’98 — Object-Oriented Programming. ECOOP 1998. Lecture Notes in Computer Science, vol 1445. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0054109

Download citation

  • DOI: https://doi.org/10.1007/BFb0054109

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-64737-9

  • Online ISBN: 978-3-540-69064-1

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation