Name
Abstract | ||
|---|---|---|
This paper presents an algorithm that allocates registers optimally for straight-line code running on a generic multi-issue computer. On such a machine, an optimal register allocation is one that minimizes the number of issue slots that the code requires. Optimal spill selection and load/store placement are used to minimize the number of additional issue slots needed, given a schedule for the non-memory reference instructions and a fixed number of available physical registers. The generic multi-issue machine model closely models the operation of vector and VLIW processors, and could be extended to model super-scalar processors. The algorithm uses dynamic programming to search the state space of feasible register allocations; implicit and explicit state pruning are used to make the problem tractable without sacrificing optimality. The optimal allocation produced by the algorithm for a substantial example is presented. |
Year | DOI | Venue |
|---|---|---|
1994 | 10.1145/181181.181318 | International Conference on Supercomputing 2006 |
Keywords | Field | DocType |
feasible register allocation,generic multi-issue computer,multiple-issue machine,generic multi-issue machine model,additional issue slot,available physical register,fixed number,optimal local register allocation,explicit state pruning,optimal spill selection,optimal allocation,optimal register allocation,register allocation,state space,program analysis | Dynamic programming,Register allocation,Computer science,Abstract interpretation,Very long instruction word,Parallel computing,Real-time computing,Program analysis,Processor register,State space | Conference |
ISBN | Citations | PageRank |
0-89791-665-4 | 2 | 0.38 |
References | Authors | |
6 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Waleed M. Meleis | 1 | 66 | 6.65 |
| Edward S. Davidson | 2 | 922 | 171.30 |