Method and apparatus for register allocation in presence of hardware constraints

A method of code optimization in presence of hardware constraints, the method comprising:

• generating graph coloring of nodes of a program to identify a plurality of virtual registers;
• scheduling the program using a reverse look-ahead scheduler having a hardware model to reduce a number of live virtual registers while tending to minimize a number of processor passes;
• annotating the virtual registers with vector component preferences;
• allocating the virtual registers to physical registers using a plurality of register allocation orders to generate a corresponding plurality of register allocations;
• selecting a register allocation from the plurality of register allocations based on a conflict metric;
• and
• rescheduling the program in a forward scheduler to optimize the code by further reducing conflicts.

An apparatus configured to optimize code in the presence of hardware constraints;

• the apparatus comprising:
• a reverse look-ahead scheduler configured to schedule a program using a plurality of virtual vector registers in a manner that tends to minimize live virtual registers while minimizing processing passes;
• a register annotator coupled to the reverse look-ahead scheduler and configured to annotate each of the plurality of virtual vector registers with vector component preferences;
• a register allocator coupled to the register annotator and configured to generate a plurality of register allocations corresponding to a plurality of allocation orders by allocating virtual vector registers to physical vector registers based in part on an allocation order;
• and
• a forward scheduler coupled to the register allocator and configured to select a register allocation from the plurality of register allocations and reschedule the program with the physical vector registers to optimize the code by reducing schedule conflicts identified during register allocation.