Institution: Stanford University, Department of Computer Science

Title: Combining Register Allocation and Instruction Scheduling

Author: Motwani, Rajeev

Author: Palem, Krishna V.

Author: Sarkar, Vivek

Author: Reyen, Salem

Date: August 1995

Abstract: We formulate combined register allocation and instruction scheduling within a basic block as a single optimization problem, with an objective cost function that more directly captures the primary measure of interest in code optimization --- the completion time of the last instruction. We show that although a simple instance of the combined problem is NP-hard, the combined problem is much easier to solve approximately than graph coloring, which is a common formulation used for the register allocation phase in phase-ordered solutions. Using our framework, we devise a simple and effective heuristic algorithm for the combined problem. This algorithm is called the (alpha,beta)-Combined Heuristic; parameters alpha and beta provide relative weightages for controlling register pressure and instruction parallelism considerations in the combined heuristic. Preliminary experiments indicate that the combined heuristic yields improvements in the range of 16-21% compared to the phase-ordered solutions, when the input graphs contain balanced amount of register pressure and instruction-level parallelism.

http://i.stanford.edu/pub/cstr/reports/cs/tn/95/22/CS-TN-95-22.pdf