Christian Wimmer
Michael Franz
ABSTRACT
The linear scan algorithm for register allocation provides a good register assignment with a low compilation overhead and is thus frequently used for just-in-time compilers. Although most of these compilers use static single assignment (SSA) form, the algorithm has not yet been applied on SSA form, i.e., SSA form is usually deconstructed before register allocation. However, the structural properties of SSA form can be used to simplify the algorithm.
With only one definition per variable, lifetime intervals (the main data structure) can be constructed without data flow analysis. During allocation, some tests of interval intersection can be skipped because SSA form guarantees non-intersection. Finally, deconstruction of SSA form after register allocation can be integrated into the resolution phase of the register allocator without much additional code.
We modified the linear scan register allocator of the Java HotSpot client compiler so that it operates on SSA form. The evaluation shows that our simpler and faster version generates equally good or slightly better machine code.
- B. Alpern, C. R. Attanasio, J. J. Barton, M. G. Burke, P.Cheng, J.-D. Choi, A. Cocchi, S. J. Fink, D. Grove, M. Hind, S. F. Hummel, D. Lieber, V. Litvinov, M. F. Mergen, T. Ngo, J. R. Russell, V. Sarkar, M. J. Serrano, J. C. Shepherd, S. E. Smith, V. C. Sreedhar, H. Srinivasan, and J. Whaley. The Jalapeno virtual machine. IBM Systems Journal, 39(1):211--238, 2000. Google Scholar
Digital Library
- S. M. Blackburn, R. Garner, C. Hoffman, A. M. Khan, K. S. McKinley, R. Bentzur, A. Diwan, D. Feinberg, D. Frampton, S. Z. Guyer, M. Hirzel, A. Hosking, M. Jump, H. Lee, J. E. B. Moss, A. Phansalkar, D. Stefanovic, T. VanDrunen, D. von Dincklage, and B. Wiedermann. The DaCapo benchmarks: Java benchmarking development and analysis. In Proceedings of the ACM SIGPLAN Conference on Object-Oriented Programming Systems, Languages, and Applications, pages 169--190. ACM Press, 2006. Google ScholarDigital Library
- B. Boissinot, A. Darte, F. Rastello, B. D. de Dinechin, and C. Guillon. Revisiting out-of-SSA translation for correctness, code quality and efficiency. In Proceedings of the International Symposium on Code Generation and Optimization, pages 114--125. IEEE Computer Society, 2009. Google ScholarDigital Library
- B. Boissinot, S. Hack, D. Grund, B. Dupont de Dinechin, and F. Rastello. Fast liveness checking for SSA-form programs. In Proceedings of the International Symposium on Code Generation and Optimization, pages 35--44. ACM Press, 2008. Google ScholarDigital Library
- P. Briggs, K. D. Cooper, and L. Torczon. Improvements to graph coloring register allocation. ACM Transactions on Programming Languages and Systems, 16(3):428--455, 1994. Google ScholarDigital Library
- P. Brisk, F. Dabiri, R. Jafari, and M. Sarrafzadeh. Optimal register sharing for high-level synthesis of SSA form programs. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 25(5):772--779, 2006. Google ScholarDigital Library
- Z. Budimlic, K. D. Cooper, T. J. Harvey, K. Kennedy, T. S. Oberg, and S. W. Reeves. Fast copy coalescing and live-range identification. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 25--32. ACM Press, 2002. Google ScholarDigital Library
- 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, 1981.Google ScholarDigital Library
- R. Cytron, J. Ferrante, B. K. Rosen, M. N. Wegman, and F. K. Zadeck. Efficiently computing static single assignment form and the control dependence graph. ACM Transactions on Programming Languages and Systems, 13(4):451--490, 1991. Google ScholarDigital Library
- S. J. Fink and F. Qian. Design, implementation and evaluation of adaptive recompilation with on-stack replacement. In Proceedings of the International Symposium on Code Generation and Optimization, pages 241--252. IEEE Computer Society, 2003. Google ScholarDigital Library
- R. Griesemer and S. Mitrovic. A compiler for the Java HotSpot virtual machine. In The School of Niklaus Wirth: The Art of Simplicity, pages 133--152. dpunkt.verlag, 2000. Google ScholarDigital Library
- S. Hack and G. Goos. Optimal register allocation for SSA-form programs in polynomial time. Information Processing Letters, 98(4):150--155, 2006. Google ScholarDigital Library
- S. Hack and G. Goos. Copy coalescing by graph recoloring. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 227--237. ACM Press, 2008. Google ScholarDigital Library
- S. Hack, D. Grund, and G. Goos. Register allocation for programs in SSA-form. In Proceedings of the International Conference on Compiler Construction, pages 247--262. LNCS 3923, Springer Verlag, 2006. Google ScholarDigital Library
- U. Hölzle and D. Ungar. Optimizing dynamically-dispatched calls with run-time type feedback. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 326--336. ACM Press, 1994. Google ScholarDigital Library
- T. Kotzmann, C. Wimmer, H. Mössenböck, T. Rodriguez, K. Russell, and D. Cox. Design of the Java HotSpot client compiler for Java 6. ACM Transactions on Architecture and Code Optimization, 5(1):Article 7, 2008. Google ScholarDigital Library
- C. Lattner and V. Adve. LLVM: A compilation framework for lifelong program analysis & transformation. In Proceedings of the International Symposium on Code Generation and Optimization, pages 75--88. IEEE Computer Society, 2004. Google ScholarDigital Library
- T. Lindholm and F. Yellin. The Java Virtual Machine Specification. Addison-Wesley, 2nd edition, 1999. Google ScholarDigital Library
- H. Mössenböck and M. Pfeiffer. Linear scan register allocation in the context of SSA form and register constraints. In Proceedings of the International Conference on Compiler Construction, pages 229--246. LNCS 2304, Springer-Verlag, 2002. Google ScholarDigital Library
- F. M. Q. Pereira and J. Palsberg. Register allocation by puzzle solving. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 216--226. ACM Press, 2008. Google ScholarDigital Library
- F. M. Q. Pereira and J. Palsberg. SSA elimination after register allocation. In Proceedings of the International Conference on Compiler Construction, pages 158--173. LNCS 5501, Springer Verlag, 2009. Google ScholarDigital Library
- M. Poletto and V. Sarkar. Linear scan register allocation. ACM Transactions on Programming Languages and Systems, 21(5):895--913, 1999. Google ScholarDigital Library
- R. Pozo and B. Miller. SciMark 2.0, 1999. http://math.nist.gov/scimark2/.Google Scholar
- V. Sarkar and R. Barik. Extended linear scan: An alternate foundation for global register allocation. In Proceedings of the International Conference on Compiler Construction, pages 141--155. LNCS 4420, Springer Verlag, 2007. Google ScholarDigital Library
- Standard Performance Evaluation Corporation. SPECjbb2005, 2005. http://www.spec.org/jbb2005/.Google Scholar
- Standard Performance Evaluation Corporation. SPECjvm2008, 2008. http://www.spec.org/jvm2008/.Google Scholar
- Sun Microsystems, Inc. OpenJDK, 2009. http://openjdk.java.net/.Google Scholar
- O. Traub, G. Holloway, and M. D. Smith. Quality and speed in linear-scan register allocation. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 142--151. ACM Press, 1998. Google ScholarDigital Library
- C. Wimmer. Linear scan register allocation for the Java HotSpot client compiler. Master's thesis, Johannes Kepler University Linz, 2004.Google Scholar
- C. Wimmer and H. Mössenböck. Optimized interval splitting in a linear scan register allocator. In Proceedings of the ACM/USENIX International Conference on Virtual Execution Environments, pages 132--141. ACM Press, 2005. Google ScholarDigital Library
Index Terms
- Linear scan register allocation on SSA form
Recommendations
Optimized interval splitting in a linear scan register allocator
VEE '05: Proceedings of the 1st ACM/USENIX international conference on Virtual execution environmentsWe present an optimized implementation of the linear scan register allocation algorithm for Sun Microsystems' Java HotSpot™ client compiler. Linear scan register allocation is especially suitable for just-in-time compilers because it is faster than the ...
Quality and speed in linear-scan register allocation
A linear-scan algorithm directs the global allocation of register candidates to registers based on a simple linear sweep over the program being compiled. This approach to register allocation makes sense for systems, such as those for dynamic compilation,...
Improving on Linear Scan Register Allocation
Register allocation is a major step for all compilers. Various register allocation algorithms have been developed over the decades. This work describes a new class of rapid register allocation algorithms and presents experimental data on their behavior. ...
Comments