Conflict-free register allocation

摘要

One embodiment of the present invention sets forth a technique for using a multi-bank register file that reduces the size of or eliminates a switch and/or staging registers that are used to gather input operands for instructions. Each function unit input may be directly connected to one bank of the multi-bank register file with neither a switch nor a staging register. A compiler or register allocation unit ensures that the register file accesses for each instruction are conflict-free (no instruction can access the same bank more than once in the same cycle). The compiler or register allocation unit may also ensure that the register file accesses for each instruction are also aligned (each input of a function unit can only come from the bank connected to that input).

主权项

1. A method for assigning variables to physical registers stored in a multi-bank register file, comprising:
computing a Register Conflict Graph (RCG) for an input program that includes variables represented as nodes in the RCG; assigning at least three banks of the multi-bank register file to the nodes in the RCG; allocating physical registers for each of the at least three banks enabling input operands to be read from the multi-bank register file in a single access cycle for each instruction that specifies the input operands to produce a conflict-free register allocation, wherein a first physical register of the physical registers is allocated to a first bank of the multi-bank registers file and is configured to store a first operand to be received at a first input of a function unit configured to perform an operation specified by the instruction; determining that the first bank of the multi-bank register file is not coupled to the first input of the function unit; inserting a copy instruction to align the first operand to a second bank of the multi-bank register file, the second bank being coupled to the first input of the function unit; and generating an output program corresponding to the input program that uses the conflict-free register allocation.