Abstract | ||
---|---|---|
The register allocation phase of a compiler maps live ranges of a program to registers. If there are more candidates than there are physical registers, the register allocator must spill a live range (the home location is in memory) or split a live range (the live range occupies multiple locations). One of the challenges for a register allocator is to deal with spilling and splitting together. Fusion-based register allocation uses the structure of the program to make splitting and spilling decisions, with the goal to move overhead operations to infrequently executed parts of a program. The basic idea of fusion-based register allocation is to build up the interference graph. Starting with some base region (e.g., a basic block, a loop), the register allocator adds basic blocks to the region and incrementallly builds the interference graph. When there are more live ranges than registers, the register allocator selects live ranges to split; these live ranges are split along the edge that was most recently added to the region. This article describes fusion-based register allocation in detail and compares it with other approaches to register allocation. For programs from the SPEC92 suite, fusion-based register allocation can improve the execution time (of optimized programs, for the MIPS architecture) by up to 8.4% over Chaitin-style register allocation. |
Year | DOI | Venue |
---|---|---|
2000 | 10.1145/353926.353929 | Fusion-based register allocation |
Keywords | Field | DocType |
register allocation,Fusion-based register allocation,basic idea,interference graph,performance evaluation,basic block,register allocation phase,register allocator,physical register,live range,base region,Chaitin-style register allocation | Programming language,Status register,Register allocation,Computer science,Memory data register,Control register,Stack register,Register window,Register renaming,Processor register | Journal |
Volume | Issue | ISSN |
22 | 3 | 0164-0925 |
Citations | PageRank | References |
26 | 1.35 | 21 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Guei-Yuan Lueh | 1 | 401 | 37.41 |
Thomas Gross | 2 | 26 | 1.35 |
Ali-Reza Adl-Tabatabai | 3 | 971 | 62.68 |