Name
Title | ||
|---|---|---|
Register allocation and promotion through combined instruction scheduling and loop unrolling |
Abstract | ||
|---|---|---|
Register allocation is a much studied problem. A particularly important context for optimizing register allocation is within loops, since a significant fraction of the execution time of programs is often inside loop code. A variety of algorithms have been proposed in the past for register allocation, but the complexity of the problem has resulted in a decoupling of several important aspects, including loop unrolling, register promotion, and instruction reordering. In this paper, we develop an approach to register allocation and promotion in a unified optimization framework that simultaneously considers the impact of loop unrolling and instruction scheduling. This is done via a novel instruction tiling approach where instructions within a loop are represented along one dimension and innermost loop iterations along the other dimension. By exploiting the regularity along the loop dimension, and imposing essential dependence based constraints on intra-tile execution order, the problem of optimizing register pressure is cast in a constraint programming formalism. Experimental results are provided from thousands of innermost loops extracted from the SPEC benchmarks, demonstrating improvements over the current state-of-the-art. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1145/2892208.2892219 | Proceedings of the 25th International Conference on Compiler Construction |
Keywords | Field | DocType |
Register allocation, spilling, scheduling, register promotion, contraint programming, loop transformations, loop unrolling, loop splitting | Register allocation,Instruction scheduling,Computer science,Constraint programming,Parallel computing,Loop inversion,Loop tiling,Loop unrolling,Processor register,Loop scheduling | Conference |
ISBN | Citations | PageRank |
978-1-4503-4241-4 | 3 | 0.37 |
References | Authors | |
20 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Łukasz Domagała | 1 | 3 | 1.05 |
| Duco van Amstel | 2 | 26 | 1.95 |
| Fabrice Rastello | 3 | 482 | 38.30 |
| P. Sadayappan | 4 | 4821 | 344.32 |