| 摘要 |
Register allocation during computer program code compilation is accomplished by determining a set of spill candidates, by evaluating a cost function for each spill candidate using a plurality of spill strategies, and by selecting the spill candidate having the lowest cost function value. Preferably, the set of possible spill candidates is determined by the Chaitin method of constructing an interference graph of all live ranges of symbolic registers, and iteratively removing nodes and placing them on a stack. Preferably, multiple spill strategies are represented as varying numbers of deaths N of live ranges of other symbolic registers, a spill strategy N signifying that spill code is introduced whenever the number of deaths occurring between two successive uses of a symbolic register equals or exceeds N. In the preferred embodiment, the cost is a function of the number, type and frequency of each operation introduced by the spill, and is divided by a benefit factor represented as the degree of the node.
|
