Report Number: CS-TN-95-22
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