BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TN-95-22
       ENTRY:: August 09, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: Combining Register Allocation and Instruction Scheduling
        TYPE:: Technical Note
      AUTHOR:: Motwani, Rajeev
      AUTHOR:: Palem, Krishna V.
      AUTHOR:: Sarkar, Vivek
      AUTHOR:: Reyen, Salem
        DATE:: August 1995
       PAGES:: 17
    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.
       NOTES:: [Adminitrivia V1/Prg/19950809]
         END:: STAN//CS-TN-95-22