Register allocation system adaptive for pipelining

• US 5,261,062 A
• Filed: 10/31/1990
• Issued: 11/09/1993
• Est. Priority Date: 11/08/1989
• Status: Expired due to Term

• Current Assignee: OKI Electric Industry Company Limited
• Original Assignee: OKI Electric Industry Company Limited
• Inventors: Sato, Yoshikazu
• Primary Examiner(s): Harrell, Robert B.
• Assistant Examiner(s): SHAH, ALPESH
• Application Number:
  US07/607,062
• Time in Patent Office: 1,105 Days
• Field of Search: 395/375, 395/400, 395/700, 395/425
• US Class Current: 717/153
• CPC Class Codes: G06F 8/441 Register allocation; Assignment of physical memory space to logical memory space

Abstract

A computer implemented register allocation for use in preprocessing a program for a system using pipelining, in which real registers are allocated to instructions included in the program, after the allocation of registers, relocation of the plurality of instructions is performed, the plurality of instructions being subsequently executed in parallel to perform an arithmetic operation processing. The register allocation includes determining a number of interferences, which indicates the number of registers simultaneously used by the instructions during the arithmetic operation processing, determining whether the number of interferences exceeds the total number of registers, and if the number of interferences does not exceed the total number of registers, then allocating the instructions to the registers.

Claims

1. In a computer implemented compiler, for use in a pipelined parallel processing system having a plurality of real registers, a method for allocating virtual registers associated with sequential instructions of a program to respective real registers of the system, wherein the method comprises:

determining an occupational state for the virtual registers;

performing a live analysis to determine a living period for each of the virtual registers;

determining if the living period of any virtual register overlaps with the living period of any other virtual register indicating an interference;

determining, for each of the respective virtual registers, if the number of interferences exceeds the number of real registers in the system;

if the number of interferences for the virtual register is less than the number of real registers in the system, then eliminating each such virtual register from further interference processing;

if the number of interferences for the virtual register is not less than the number of real registers in the system, then for each such remaining virtual register, reducing the living period of the virtual register by inserting a spill code instructing the saving of the contents of the virtual register to memory, inserting a return instruction, and proceeding to the step of determining an occupational state for the virtual registers to continue the processing with the remaining virtual registers; and

when the number of interferences for each virtual register is less than the number of real registers in the system, then allocating the virtual registers to respective real registers, wherein the allocating of the virtual registers to respective real registers comprises;

selecting the virtual register;

selecting a proposed real register;

determining whether allocation of the selected virtual register to the proposed real register is possible;

if allocation of the selected virtual register to the proposed real register is possible, then allocating the virtual register to the proposed real register;

if allocation of the selected virtual register to the proposed real register is not possible, then selecting another real register as the proposed real register and returning to the step of determining whether allocation of the selected virtual register to the proposed real register is possible;

determining if there are any more virtual registers unallocated;

if there are any more virtual registers unallocated, then returning to the step of selecting the virtual register and repeating the allocating of virtual registers to respective real registers until completed.

2. The method for allocating virtual registers associated with sequential instructions of a program to respective real registers of the system according to claim 1, further comprising relocating the plurality of instructions in the program to form a new instruction sequence optimized for parallel pipelined execution based on the allocation of registers.

3. A system for allocating virtual registers to respective real registers, the virtual registers being associated with sequential instructions of a program to be executed in a pipelined parallel processing system having a plurality of real registers, the system comprising:

means for determining an occupational state for the virtual registers;

means for performing a live analysis to determine a living period for each of the virtual registers;

means for determining if the living period of any virtual register overlaps with the living period of any other virtual register indicating an interference;

means for determining, for each of the respective virtual registers, if the number of interferences exceeds the number of real registers in the system;

means for eliminating the virtual register from further interference processing, if the number of interferences for the virtual register is less than the number of real registers in the system;

means for reducing the living period of the virtual register by inserting a spill code instructing the saving of the contents of the virtual register to memory, inserting a return instruction, if the number of interferences for the virtual register is not less than the number of real registers in the system; and

means for allocating the virtual registers to respective real registers when the number of interferences for each virtual register is less than the number of real registers in the system, wherein the means for allocating of the virtual registers to respective real registers comprises;

means for selecting the virtual register;

means for selecting a proposed real register;

means for determining whether allocation of the selected virtual register to the proposed real register is possible;

means for allocating the virtual register to the proposed real register, if allocation of the selected virtual register to the proposed real register is possible;

means for selecting another real register as the proposed real register, if allocation of the selected virtual register to the proposed real register is not possible;

means for determining if there are any more virtual registers unallocated, wherein allocating of virtual registers to respective real registers continues until all virtual registers are allocated.