US 7,681,187 B2Granted

Method and apparatus for register allocation in presence of hardware constraints

AssigneeNVIDIA Corporation

InventorsMichael G. Ludwig, Jayant B. Kolhe, Robert Steven Glanville, Geoffrey C. Berry, Boris Beylin, Michael T. Bunnell

Life of this patent

Estimating the term…

patentgrep

Loading patent…

Abstract

A method and apparatus for optimizing register allocation during scheduling and execution of program code in a hardware environment. The program code can be compiled to optimize execution given predetermined hardware constraints. The hardware constraints can include the number of register read and write operations that can be performed in a given processor pass. The optimizer can initially schedule the program using virtual registers and a goal of minimizing the amount of active registers at any time. The optimizer reschedules the program to assign the virtual registers to actual physical registers in a manner that minimizes the number of processor passes used to execute the program.

Claims19

Dependent claims

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

scheduling instruction codes using virtual registers in a manner that tends to minimize simultaneous active registers while minimizing a number of passes of a processing unit;
allocating the virtual registers to physical registers according to a plurality of register allocation orders to produce a corresponding plurality of physical register allocations;
determining a conflict value for each register allocation from the plurality of physical register allocations, wherein the conflict value is determined based on a number of times a read or a write bandwidth constraint of the processing unit is exceeded, the read and write bandwidth constraints corresponding to a maximum number of register read or write operations, respectively, that the processing unit can perform in a given pass;
determining a physical register allocation corresponding to a least conflict value;
and
rescheduling the instruction codes using the physical register allocation to optimize the code by further reducing a number of conflicts.

3 more elements

A computer implemented 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, at least one virtual register of the plurality of virtual registers comprising a virtual vector register having a plurality of vector components;
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 of a processing unit;
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, wherein the conflict metric is determined based on a number of times a read or a write bandwidth constraint of the processing unit is exceeded, the read and write bandwidth constraints corresponding to a maximum number of register read or write operations, respectively, that the processing unit can perform in a given processor pass;
and
rescheduling the program in a forward scheduler to optimize the code by further reducing conflicts based on the conflict metric.

4 more elements

An apparatus configured to optimize code in presence of hardware constraints, the apparatus comprising:

a processor;
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, each virtual vector register having a plurality of vector components;
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 wherein a conflict value is determined for each register allocation from the plurality of register allocations, wherein the conflict value is determined based on a number of times a read or a write bandwidth constraint of the processor is exceeded, the read and write bandwidth constraints corresponding to a maximum number of register read or write operations, respectively, that the processor can perform in a given pass;
and
a forward scheduler coupled to the register allocator and configured to select a register allocation from the plurality of register allocations based on the conflict value and reschedule the program with the physical vector registers to optimize the code by reducing schedule conflicts identified during register allocation.

3 more elements

Dependencies are inferred from the claim text.