Partial method compilation using dynamic profile information

ABSTRACT

The traditional tradeoff when performing dynamic compilation is that of fast compilation time versus fast code performance. Most dynamic compilation systems for Java perform selective compilation and/or optimization at a method granularity. This is the not the optimal granularity level. However, compiling at a sub-method granularity is thought to be too complicated to be practical. This paper describes a straightforward technique for performing compilation and optimizations at a finer, sub-method granularity. We utilize dynamic profile data to determine intra-method code regions that are rarely or never executed, and compile and optimize the code without those regions. If a branch that was predicted to be rare is actually taken at run time, we fall back to the interpreter or dynamically compile another version of the code. By avoiding compiling and optimizing code that is rarely executed, we are able to decrease compile time significantly, with little to no degradation in performance. Futhermore, ignoring rarely-executed code can open up more optimization opportunities on the common paths. We present two optimizations---partial dead code elimination and rare-path-sensitive pointer and escape analysis---that take advantage of rare path information. Using these optimizations, our technique is able to improve performance beyond the compile time improvements

REFERENCES

• 1: Glenn Ammons , James R. Larus, Improving data-flow analysis with path profiles, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.72-84, June 17-19, 1998, Montreal, Quebec, Canada
• 2: C. S. Ananian. FLEX compiler infrastructure. http://www.flex-compiler.lcs.mit .edu, 2001.
• 3: Matthew Arnold , Stephen Fink , David Grove , Michael Hind , Peter F. Sweeney, Adaptive optimization in the Jalapeño JVM, ACM SIGPLAN Notices, v.35 n.10, p.47-65, Oct. 2000
• 4: Matthew Arnold , Stephen Fink , Vivek Sarkar , Peter F. Sweeney, A comparative study of static and profile-based heuristics for inlining, Proceedings of the ACM SIGPLAN workshop on Dynamic and adaptive compilation and optimization, p.52-64, January 2000
• 5: Vasanth Bala , Evelyn Duesterwald , Sanjeev Banerjia, Dynamo: a transparent dynamic optimization system, ACM SIGPLAN Notices, v.35 n.5, p.1-12, May 2000
• 6: Thomas Ball , James R. Larus, Optimally profiling and tracing programs, Proceedings of the 19th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.59-70, January 19-22, 1992, Albuquerque, New Mexico, United States [doi>10.1145/143165.143180]
• 7: Thomas Ball , James R. Larus, Efficient path profiling, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.46-57, December 02-04, 1996, Paris, France
• 8: D. Bruening and E. Duesterwald. Exploring optimal compilation unit shapes for an embedded just-in-time compiler. In Proceedings of the 2000 A CM Workshop on Feedback-Directed and Dynamic Optimization FDDO-3, Dec. 2000.
• 9: 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]
• 10: Steve Carr , Ken Kennedy, Scalar replacement in the presence of conditional control flow, Software—Practice & Experience, v.24 n.1, p.51-77, Jan. 1994 [doi>10.1002/spe.4380240104]
• 11: Craig Chambers , David Ungar, Making pure object-oriented languages practical, Conference proceedings on Object-oriented programming systems, languages, and applications, p.1-15, October 06-11, 1991, Phoenix, Arizona, United States
• 12: P. P. Chang, D. M. Lavery, and W. M. Hwu. The effect of code expanding optimizations of instruction cache design. Technical Report CRHC-91-18, Coordinated Science Lab, University of Illinois, Jan. 1992.
• 13: Pohua P. Chang , Scott A. Mahlke , William Y. Chen , Nancy J. Warter , Wen-mei W. Hwu, IMPACT: an architectural framework for multiple-instruction-issue processors, Proceedings of the 18th annual international symposium on Computer architecture, p.266-275, May 27-30, 1991, Toronto, Ontario, Canada
• 14: J. B. Chen and B. D. D. Leupen. Improving instruction locality with just-in-time code layout. In USENIX, editor, The USENIX Windows NT Workshop 1997, August 11-13, 1997. Seattle, Washington, pages 25-32, Berkeley, CA, USA, Aug. 1997. USENIX.
• 15: Michał Cierniak , Guei-Yuan Lueh , James M. Stichnoth, Practicing JUDO: Java under dynamic optimizations, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.13-26, June 18-21, 2000, Vancouver, British Columbia, Canada
• 16: M. Dahm. Byte code engineering library. http://bcel.sourceforge.net, 2000.
• 17: M. Anton Ertl , Andreas Krall, Delayed Exceptions - Speculative Execution of Trapping Instructions, Proceedings of the 5th International Conference on Compiler Construction, p.158-171, April 07-09, 1994
• 18: J. A. Fisher. Trace scheduling : A technique for global microcode compaction. IEEE Transactions on Computers, C-30(7):478-490, 1981.
• 19: Manish Gupta , Jong-Deok Choi , Michael Hind, Optimizing Java Programs in the Presence of Exceptions, Proceedings of the 14th European Conference on Object-Oriented Programming, p.422-446, June 12-16, 2000
• 20: Rajiv Gupta , David A. Berson , Jesse Z. Fang, Resource-sensitive profile-directed data flow analysis for code optimization, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.358-368, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 21: Richard E. Hank , Wen-Mei W. Hwu , B. Ramakrishna Rau, Region-based compilation: an introduction and motivation, Proceedings of the 28th annual international symposium on Microarchitecture, p.158-168, November 29-December 01, 1995, Ann Arbor, Michigan, United States
• 22: L. H. Holley and B. K. Rosen. Qualified data flow problems. IEEE Transactions on Software Engineering, 7(1):60-78, Jan. 1981.
• 23: R. Nigel Horspool , H. C. Ho, Partial Redundancy Elimination Driven by a Cost-Benefit Analysis, Proceedings of the 8th Israeli Conference on Computer-Based Systems and Software Engineering, p.111, June 18-19, 1997
• 24: Wen-Mei W. Hwu , Scott A. Mahlke , William Y. Chen , Pohua P. Chang , Nancy J. Warter , Roger A. Bringmann , Roland G. Ouellette , Richard E. Hank , Tokuzo Kiyohara , Grant E. Haab , John G. Holm , Daniel M. Lavery, The superblock: an effective technique for VLIW and superscalar compilation, The Journal of Supercomputing, v.7 n.1-2, p.229-248, May 1993 [doi>10.1007/BF01205185]
• 25: International Business Machines. IBM Developer Kit, Java(tm) Technology Edition, 2001. http: //www.ibm.com/j ava/jdk/index.html.
• 26: Kazuaki Ishizaki , Motohiro Kawahito , Toshiaki Yasue , Hideaki Komatsu , Toshio Nakatani, A study of devirtualization techniques for a Java Just-In-Time compiler, Proceedings of the 15th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.294-310, October 2000, Minneapolis, Minnesota, United States
• 27: 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]
• 28: Motohiro Kawahito , Hideaki Komatsu , Toshio Nakatani, Effective null pointer check elimination utilizing hardware trap, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.139-149, November 2000, Cambridge, Massachusetts, United States
• 29: K. Kennedy. A Survey of data flow analysis techniques. In S. S. Muchnick and N. D. Jones, editors, Program Flow Analysis: Theory and Applications, chapter 1, pages 5-54. Prentice-Hall, 1981.
• 30: Jens Knoop , Oliver Rüthing , Bernhard Steffen, Partial dead code elimination, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.147-158, June 20-24, 1994, Orlando, Florida, United States
• 31: David Kranz , Norman Adams , Richard Kelsey , Jonathan Rees , Paul Hudak , James Philbin, ORBIT: an optimizing compiler for scheme, Proceedings of the 1986 SIGPLAN symposium on Compiler construction, p.219-233, June 25-27, 1986, Palo Alto, California, United States
• 32: Tim Lindholm , Frank Yellin, Java Virtual Machine Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 33: P. Geoffrey Lowney , Stefan M. Freudenberger , Thomas J. Karzes , W. D. Lichtenstein , Robert P. Nix , John S. O'Donnell , John Ruttenberg, The multiflow trace scheduling compiler, The Journal of Supercomputing, v.7 n.1-2, p.51-142, May 1993 [doi>10.1007/BF01205182]
• 34: Scott A. Mahlke , William Y. Chen , Roger A. Bringmann , Richard E. Hank , Wen-Mei W. Hwu , B. Ramakrishna Rau , Michael S. Schlansker, Sentinel scheduling: a model for compiler-controlled speculative execution, ACM Transactions on Computer Systems (TOCS), v.11 n.4, p.376-408, Nov. 1993 [doi>10.1145/161541.159765]
• 35: S. Microsystems. Java virtual machine debug interface reference. http: / /java.sun.com /'products/ jdk/1.3 / docs/ guide/ jpda/jvmdi-spec.html.
• 36: Steven S. Muchnick, Advanced compiler design and implementation, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 37: Takeshi Ogasawara , Hideaki Komatsu , Toshio Nakatani, A study of exception handling and its dynamic optimization in Java, Proceedings of the 16th ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, p.83-95, October 14-18, 2001, Tampa Bay, FL, USA
• 38: M. Paleczny, C. Vick, and C. Click. The Java HotSpot(TM) server compiler. In USENIX Java Virtual Machine Research and Technology Symposium (JVM'01), 2001.
• 39: Karl Pettis , Robert C. Hansen, Profile guided code positioning, ACM SIGPLAN Notices, v.25 n.6, p.16-27, Jun. 1990
• 40: M. Poletto. Path splitting: a technique for improving data flow analysis. Master's thesis, Massachusetts Institute of Technology, May 1995.
• 41: Michael D. Smith , Monica S. Lam , Mark A. Horowitz, Boosting beyond static scheduling in a superscalar processor, Proceedings of the 17th annual international symposium on Computer Architecture, p.344-354, May 28-31, 1990, Seattle, Washington, United States
• 42: T. Suganuma , T. Ogasawara , M. Takeuchi , T. Yasue , M. Kawahito , K. Ishizaki , H. Komatsu , T. Nakatani, Overview of the IBM Java just-in-time compiler, IBM Systems Journal, v.39 n.1, p.175-193, January 2000
• 43: Toshio Suganuma , Toshiaki Yasue , Motohiro Kawahito , Hideaki Komatsu , Toshio Nakatani, A dynamic optimization framework for a Java just-in-time compiler, Proceedings of the 16th ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, p.180-195, October 14-18, 2001, Tampa Bay, FL, USA
• 44: The Standard Performance Evaluation Corporation. SPEC JVM98 Benchmarks, 1998. http://www.spec.org/osg/jvm98/.
• 45: J. Whaley. joeq virtual machine. http://joeq.sourceforge.net, 2001.
• 46: 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.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Applicative (functional) languages

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization; Compilers

General Terms:
Algorithms, Languages, Performance