Abstract | ||
---|---|---|
Just-in-time compilers are becoming ubiquitous, spurring the design of more efficient algorithms and more elaborate intermediate representations. They rely on continuous, feedback-directed (re-)compilation frameworks to adaptively select a limited set of hot functions for aggressive optimization. To date, (quasi-)linear complexity has remained a driving force in the design of just-in-time optimizers. This paper describes a split register allocator showing that linear complexity does not imply reduced code quality. We present a split compiler design, where more expensive ahead-of-time analyses guide lightweight just-in-time optimizations. A split register allocator can be very aggressive in its offline stage, producing a semantic summary through bytecode annotations that can be processed by a lightweight online stage. The challenges are fourfold: (sub-)linear-size annotation, linear-time online processing, minimal loss of code quality, and portability of the annotation. We propose a split register allocator meeting these challenges. A compact annotation derived from an optimal integer linear program (ILP) formulation of register allocation drives a linear-time algorithm near optimality. We study the robustness of this algorithm to variations in the number of physical registers. Our method is implemented in JikesRVM and evaluated on standard benchmarks. |
Year | DOI | Venue |
---|---|---|
2010 | 10.1007/978-3-642-11515-8_7 | HiPEAC |
Keywords | Field | DocType |
register allocation,linear complexity,split register allocator,performance penalty,bytecode annotation,split register allocation,optimal integer linear program,code quality,split compiler design,physical register,linear-size annotation,compact annotation,linear time,just in time compiler,intermediate representation,limit set | Register allocation,Computer science,Instruction selection,Parallel computing,Real-time computing,Compiler,Compiler construction,Software portability,Linear programming,Allocator,Bytecode | Conference |
Volume | ISSN | ISBN |
5952 | 0302-9743 | 3-642-11514-4 |
Citations | PageRank | References |
2 | 0.38 | 15 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Boubacar Diouf | 1 | 6 | 1.46 |
Albert Cohen | 2 | 1002 | 72.30 |
Fabrice Rastello | 3 | 482 | 38.30 |
John Cavazos | 4 | 240 | 14.01 |