Fast, effective code generation in a just-in-time Java compiler

ABSTRACT

A "Just-In-Time" (JIT) Java compiler produces native code from Java byte code instructions during program execution. As such, compilation speed is more important in a Java JIT compiler than in a traditional compiler, requiring optimization algorithms to be lightweight and effective. We present the structure of a Java JIT compiler for the Intel Architecture, describe the lightweight implementation of JIT compiler optimizations (e.g., common subexpression elimination, register allocation, and elimination of array bounds checking), and evaluate the performance benefits and tradeoffs of the optimizations. This JIT compiler has been shipped with version 2.5 of Intel's VTune for Java product.

REFERENCES

• 1: Huw Evans , Peter Dickman, Garbage collection and memory management, Addendum to the 1997 ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications (Addendum), p.138-143, October 05-09, 1997, Atlanta, Georgia, United States [doi>10.1145/274567.274605]
• 2: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 3: D. Bernstein , M. Golumbic , y. Mansour , R. Pinter , D. Goldin , H. Krawczyk , I. Nahshon, Spill code minimization techniques for optimizing compliers, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.258-263, June 19-23, 1989, Portland, Oregon, United States
• 4: P. Briggs , K. D. Cooper , K. Kennedy , L. Torczon, Coloring heuristics for register allocation, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.275-284, June 19-23, 1989, Portland, Oregon, United States
• 5: David Callahan , Brian Koblenz, Register allocation via hierarchical graph coloring, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.192-203, June 24-28, 1991, Toronto, Ontario, Canada
• 6: G.J. Chaitin, M. A. Auslander, A. K. Chandra, J. Cocke, M. E. Hopkins, and P. W. Markstein. Register allocation via coloring. Computer Languages, 6:47-57, January 1981.
• 7: Frederick Chi-Tak Chow, A portable machine-independent global optimizer--design and measurements, 1984
• 8: Fred C. Chow , John L. Hennessy, The priority-based coloring approach to register allocation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.4, p.501-536, Oct. 1990 [doi>10.1145/88616.88621]
• 9: David W. Goodwin , Kent D. Wilken, Optimal and near-optimal global register allocations using 0–1 integer programming, Software—Practice & Experience, v.26 n.8, p.929-965, Aug. 1996 [doi>10.1002/(SICI)1097-024X(199608)26:8<929::AID-SPE40>3.3.CO;2-K]
• 10: James Gosling , Bill Joy , Guy L. Steele, The Java Language Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1996
• 11: Intel Corp. Intel Architecture Software Developer's Manual, order number 243192. 1997.
• 12: Intel Corp. Pentium Pro Family Developer's Manual, order number 000900-001. 1996.
• 13: Intel Corp. VTune: Visual Tuning Environment. Available at ht{p;//deve!ol~er,intel.congdesi~n/peffiool/vtune
• 14: R. Jones and R. Lins. Garbage Collection. John Wiley & Sons, 1996.
• 15: Jens Knoop , Oliver Rüthing , Bernhard Steffen, Lazy code motion, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.224-234, June 15-19, 1992, San Francisco, California, United States
• 16: A. Krall and R. Graft. CACAO---A 64-bit Java VM Justin-Time Compiler. In Proceedings of the ACM PPoPP97 Workshop on Java for Science and Engineering Computation.
• 17: Tim Lindholm , Frank Yellin, Java Virtual Machine Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 18: Guei-Yuan Lueh , Thomas Gross, Call-cost directed register allocation, Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation, p.296-307, June 16-18, 1997, Las Vegas, Nevada, United States
• 19: Guei-Yuan Lueh , Thomas Gross , Ali-Reza Adl-Tabatabai, Global Register Allocation Based on Graph Fusion, Proceedings of the 9th International Workshop on Languages and Compilers for Parallel Computing, p.246-265, August 08-10, 1996
• 20: Microsoft Corp. MS SDK 1.5.1. Available at h ttp.://ww.w ,micro so ft. co ~ av a
• 21: Microsoft Corp. MS SDK 1.5.1 JIT Structure. Available at htt~://www,microsoft, co m/iava/sdlc/l 51/ vendor/vm015.htm
• 22: Cindy Norris , Lori L. Pollock, Register allocation over the program dependence graph, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.266-277, June 20-24, 1994, Orlando, Florida, United States
• 23: Massimiliano Poletto , Dawson R. Engler , M. Frans Kaashoek, tcc: a system for fast, flexible, and high-level dynamic code generation, Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation, p.109-121, June 16-18, 1997, Las Vegas, Nevada, United States

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Code generation

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: Java
      D.3.4 Processors
          Subjects: Compilers

General Terms:
Algorithms, Experimentation, Languages, Performance