Call-Cost Directed Register Allocation

G. Y. Lueh and T. Gross Proc. ACM SIGPLAN Symp. on Programming Language Design and Implementation, June, 1997, pp. 296--307.


Choosing the right kind of register for live ranges plays a major role in eliminating the register-allocation overhead when the compiled function is frequently executed (i.e., resulting in high callee-save cost) or function calls are on the most frequently executed paths (i.e., causing high caller-save cost). Picking the wrong kind of register for a live range incurs a high penalty that may dominate the total overhead of register allocation. In this paper, we present three improvements, storage-class analysis, benefit-driven simplification, and preference decision, that are effective on selecting the right kind of register for a live range. The influence of the three improvements to graph coloring is evaluated. Comparisons of various register-allocation approaches are discussed as well.