Sealed calls in Java packages

ABSTRACT

Determining the potential targets of virtual method invocations is essential for inter-procedural optimizations of object-oriented programs. It is generally hard to determine such targets accurately. The problem is especially difficult for dynamic languages such as Java, because additional targets of virtual calls may appear at runtime. Current mechanisms that enable inter-procedural optimizations for dynamic languages, repeatedly validate the optimizations at runtime. This paper addresses this predicament by proposing a novel technique for conservative devirtualization analysis, which applies to a significant number of virtual calls in Java programs. Unlike previous work, our technique requires neither whole program analysis nor runtime information, and incurs no runtime overhead. Our solution is very efficient to compute and is based on a newly introduced, seemingly unrelated security feature of Java file archives. On average, our analysis "seals" (safely devirtualizes) about 39% of the virtual calls (to non-final methods) that appear in SPECjvm98 programs, and about 29% of the calls invoked while executing these programs. In the runtime library rt.jar, about 10% of the packages contain a significant percentage (20--60%) of sealed calls, with a total average of about 8.5%. Most of these calls are also shown to be monomorphic, a fact which can be safely exploited by aggressive inter-procedural optimizations such as direct inlining. These results indicate that our technique has a strong potential for enhancing the analysis and optimization of Java programs.

REFERENCES

• 1: Ole Agesen , Urs Hölzle, Type feedback vs. concrete type inference: a comparison of optimization techniques for object-oriented languages, Proceedings of the tenth annual conference on Object-oriented programming systems, languages, and applications, p.91-107, October 15-19, 1995, Austin, Texas, United States
• 2: Gerald Aigner , Urs Hölzle, Eliminating Virtual Function Calls in C++ Programs, Proceedings of the 10th European Conference on Object-Oriented Programming, p.142-166, July 08-12, 1996
• 3: Ana Azevedo , Alex Nicolau , Joe Hummel, Java annotation-aware just-in-time (AJIT) complilation system, Proceedings of the ACM 1999 conference on Java Grande, p.142-151, June 12-14, 1999, San Francisco, California, United States [doi>10.1145/304065.304115]
• 4: 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
• 5: S. J. Baylor , M. Devarakonda , S. J. Fink , E. Gluzberg , M. Kalantar , P. Muttineni , E. Barsness , R. Arora , R. Dimpsey , S. J. Munroe, Java server benchmarks, IBM Systems Journal, v.39 n.1, p.57-81, January 2000
• 6: Bruno Blanchet, Escape analysis for object-oriented languages: application to Java, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.20-34, November 01-05, 1999, Denver, Colorado, United States
• 7: Z. Budimlic and K. Kennedy. Prospects for scientific computing in polymorphic, object-oriented style. In Proceedings of the 9th SIAM Conference on Parallel Processing for Scientific Computing, March 1999.
• 8: Michael G. Burke , Jong-Deok Choi , Stephen Fink , David Grove , Michael Hind , Vivek Sarkar , Mauricio J. Serrano , V. C. Sreedhar , Harini Srinivasan , John Whaley, The Jalapeño dynamic optimizing compiler for Java, Proceedings of the ACM 1999 conference on Java Grande, p.129-141, June 12-14, 1999, San Francisco, California, United States [doi>10.1145/304065.304113]
• 9: 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]
• 10: Jong-Deok Choi , Manish Gupta , Mauricio Serrano , Vugranam C. Sreedhar , Sam Midkiff, Escape analysis for Java, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.1-19, November 01-05, 1999, Denver, Colorado, United States
• 11: Jeffrey Dean , David Grove , Craig Chambers, Optimization of Object-Oriented Programs Using Static Class Hierarchy Analysis, Proceedings of the 9th European Conference on Object-Oriented Programming, p.77-101, August 07-11, 1995
• 12: Greg DeFouw , David Grove , Craig Chambers, Fast interprocedural class analysis, Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.222-236, January 19-21, 1998, San Diego, California, United States [doi>10.1145/268946.268965]
• 13: David Detlefs , Ole Agesen, Inlining of Virtual Methods, Proceedings of the 13th European Conference on Object-Oriented Programming, p.258-278, June 14-18, 1999
• 14: Julian Dolby, Automatic inline allocation of objects, Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation, p.7-17, June 16-18, 1997, Las Vegas, Nevada, United States
• 15: Karel Driesen , Urs Hölzle, The direct cost of virtual function calls in C++, Proceedings of the 11th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.306-323, October 06-10, 1996, San Jose, California, United States
• 16: N. Feinberg, S. E. Keene, R. O. Mathews, and P. T. Withington. The Dylan Programming Book. Addison-Wesley, 1997.
• 17: E. Gagnon and L. Hendren. Intra-procedural inference of static types for java bytecode. Technical Report 1999-1, Sable Research Group, McGill University, March 1999.
• 18: Joseph Gil , Alon Itai, The Complexity of Type Analysis of Object Oriented Programs, Proceedings of the 12th European Conference on Object-Oriented Programming, p.601-634, July 20-24, 1998
• 19: James Gosling , Bill Joy , Guy L. Steele, The Java Language Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1996
• 20: David Grove , Greg DeFouw , Jeffrey Dean , Craig Chambers, Call graph construction in object-oriented languages, Proceedings of the 12th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.108-124, October 05-09, 1997, Atlanta, Georgia, United States
• 21: David Paul Grove , Craig Chambers, Effective interprocedural optimization of object-oriented languages, 1998
• 22: Urs Hölzle , Craig Chambers , David Ungar, Debugging optimized code with dynamic deoptimization, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.32-43, June 15-19, 1992, San Francisco, California, United States
• 23: The java hotspot performance engine architecture. Available at http://-www. javasoft.com/products/hotspot/whitepaper.html, April 1999.
• 24: Kazuaki Ishizaki , Motohiro Kawahito , Toshiaki Yasue , Mikio Takeuchi , Takeshi Ogasawara , Toshio Suganuma , Tamiya Onodera , Hideaki Komatsu , Toshio Nakatani, Design, implementation, and evaluation of optimizations in a just-in-time compiler, Proceedings of the ACM 1999 conference on Java Grande, p.119-128, June 12-14, 1999, San Francisco, California, United States [doi>10.1145/304065.304111]
• 25: Jigsaw - the w3c's web server. Available at http://www.w3c.org/Jigsaw.
• 26: Jove super optimizing deployment environment for java. Available at http://www.instantiations.com/jove/jovereport.htm.
• 27: Steven S. Muchnick, Advanced compiler design and implementation, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 28: Patrick D. O'Brien , Daniel C. Halbert , Michael F. Kilian, The Trellis programming environment, Conference proceedings on Object-oriented programming systems, languages and applications, p.91-102, October 04-08, 1987, Orlando, Florida, United States
• 29: H. D. Pande and B. G. Ryder. Static type determination for c++. In Proceedings of the Sixth Usenix C++ Technical Conference, pages 85-97, April 1994.
• 30: S. Porat, D. Bernstein, Y. Fedorov, J. Rodrigue, and E. Yahav. Compiler optimization of c++ virtual function calls. In Proceedings of the Second Conference on Object-Oriented Technologies and Systems (COOTS), pages 3-14, Jun 1996.
• 31: Sara Porat , Bilha Mendelson , Irina Shapira, Sharpening global static analysis to cope with Java, Proceedings of the 1998 conference of the Centre for Advanced Studies on Collaborative research, p.19, November 30-December 03, 1998, Toronto, Ontario, Canada
• 32: Spec jvm98 benchmarks. Available at http://www.spec.org/osg/jvm98, August 1998.
• 33: Vugranam C. Sreedhar , Michael Burke , Jong-Deok Choi, A framework for interprocedural optimization in the presence of dynamic class loading, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.196-207, June 18-21, 2000, Vancouver, British Columbia, Canada
• 34: Sun Microsystems. Java 2 Software Development Kit version 1.2.2, July 1999. Available at http://java.sun.com/products/jdk/1.2/, See there docs/guide/extensions/spec.html#sealing.
• 35: V. Sundaresan, L. Hendren, C. Razafimahefa, R. Valle-Rai, P. Lam, E. Gagnon, and C. Godin. Practical virtual method call resolution for java. Technical Report 1999-4, Sable Research Group, McGill University, Nov 1999.
• 36: Frank Tip , Chris Laffra , Peter F. Sweeney , David Streeter, Practical experience with an application extractor for Java, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.292-305, November 01-05, 1999, Denver, Colorado, United States
• 37: Towerj3 - a new generation native java compiler and runtime environment. Available at http://www.towerj.com/products/- whitepapergnj.shtml and also whitepapers3.shtml.
• 38: Raja Vallée-Rai , Phong Co , Etienne Gagnon , Laurie Hendren , Patrick Lam , Vijay Sundaresan, Soot - a Java bytecode optimization framework, Proceedings of the 1999 conference of the Centre for Advanced Studies on Collaborative research, p.13, November 08-11, 1999, Mississauga, Ontario, Canada
• 39: John Whaley , Martin Rinard, Compositional pointer and escape analysis for Java programs, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.187-206, November 01-05, 1999, Denver, Colorado, United States

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Object-oriented languages
          Nouns: Java
      D.3.4 Processors
          Subjects: Optimization; Run-time environments; Compilers

General Terms:
Algorithms, Design, Experimentation, Languages, Measurement, Performance, Theory

Keywords:
Java, call devirtualization, call graph, class hierarchy graph, inter-procedural analysis, method inlining, object-oriented programming, sealed package