Title: Optimal Spilling for CISC Machines with Few
Abstract: Register allocation based on graph coloring performs poorly for machines with few registers, if each temporary is held either in machine registers or memory over its entire lifetime. With the exception of short-lived temporaries, most temporaries must spill ‐ including long lived temporaries that are used within inner loops. Liverange splitting before or during register allocation helps to alleviate the problem but prior techniques are sometimes complex, make no guarantees about subsequent colorability and thus require further iterations of splitting, pay no attention to addressing modes, and make no claim to optimality. We formulate the register allocation problem for CISC architectures with few registers in two parts: an integer linear program that determines the optimal location to break up the implementation of a live range between registers and memory, and a register assignment phase that we guarantee to complete without further spill code insertion. Our linear programming model considers the various addressing modes available to an instruction and finds an optimal solution quickly. The second phase will complete without spilling, but at the expense of register-register copies remaining in the program. The task of coloring while leaving behind the minimum number of splits (optimal coalescing ) is left as an open problem; we discuss two unsatisfactory solutions (one fast and suboptimal, the other optimal but far too slow).
Publication Year: 2000
Publication Date: 2000-01-01
Language: en
Type: article
Access and Citation
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot