Register allocation technique in a program translating apparatus

• US 5,367,696 A
• Filed: 10/01/1991
• Issued: 11/22/1994
• Est. Priority Date: 12/07/1990
• Status: Expired due to Fees

• Current Assignee: Fuji Xerox Company Limited (Xerox Holdings Corp.)
• Original Assignee: Fuji Xerox Company Limited (Xerox Holdings Corp.)
• Inventors: Abe, Hitoshi
• Primary Examiner(s): Coleman, Eric
• Application Number:
  US07/769,446
• Time in Patent Office: 1,148 Days
• Field of Search: 395/500, 395/800, 395/425, 395/650, 395/700
• US Class Current: 717/153
• CPC Class Codes: G06F 8/441 Register allocation; Assignment of physical memory space to logical memory space
• CPC Class Codes: G06F 8/445 Exploiting fine grain parallelism, i.e. parallelism at instruction level run-time instruction scheduling G06F9/3836

Abstract

A program translating apparatus includes a detection portion, a separation portion, a register allocation portion, and a register assignment portion. All ranges of existence of variables are separated at starting points and ending points, profits are calculated in cases where split regions of the ranges of existence are respectively allocated to registers, and a priority for register allocation of the respective split regions is calculated. The register allocation/assignment is performed on the basis of the obtained priority.

Claims

1. A program translating apparatus comprising:

detection means for detecting variable starting points and variable ending points in ranges of existence of variables in a same period of time, said detection means examining said ranges of existence of said variables one by one;

separation means for separating said ranges of existence of said variables at said variable starting points and variable ending points detected by said detection means;

register allocation means for selecting candidatures for split regions permanently allocated to registers by determining profits when the split regions obtained by separating said ranges of existence of said variables, being different and existing in the same period of time, are respectively allocated to the registers; and

register assignment means for permanently assigning registers for said candidatures for the split regions selected by said register allocation means.

2. A program translating apparatus comprising:

a detection portion for detecting variable starting points and variable ending points in ranges of existence of variables in a same period of time, said detection portion examining said ranges of existence of said variables one by one;

a separation portion for separating said ranges of existence of said variables at said variable starting points and variable ending points detected by said detection portion;

a register allocation portion for selecting candidatures for split regions permanently allocated to registers by determining profits when the split regions obtained by separating said ranges of existence of said variables, being different and existing in the same period of time, are respectively allocated to the registers and by determining a priority for the register allocation of the split regions; and

a register assignment portion for permanently assigning registers for said candidatures for the split regions selected by said register allocation portion.

3. A program translating apparatus according to claim 2, wherein said register allocation portion includes a priority calculation portion for calculating the priority for the register allocation of the split regions, and an allocation candidature selection portion for selecting the candidatures for the split regions permanently allocated to the registers.

4. A program translating apparatus comprising:

a detection portion for detecting variable starting points and variable ending points in ranges of existence of variables in a same period of time, said detection portion examining said ranges of existence of said variables one by one;

a separation portion for separating said ranges of existence of said variables at said variable starting points and variable ending points detected by said detection portion;

a register allocation portion for selecting candidatures for split regions permanently allocated to registers by determining profits when the split regions obtained by separating said ranges of existence of said variables, being different and existing in the same period of time, are respectively allocated to the registers and by determining a priority for the register allocation of the split regions;

a register assignment portion for permanently assigning registers for said candidatures for the split regions selected by said register allocation portion; and

a register allocation and assignment retry control portion for retrying said register allocation portion and said register assignment portion.

5. A program translating apparatus according to claim 4, wherein said register allocation portion includes a priority calculation portion for calculating the priority for the register allocation of the split regions, and an allocation candidature selection portion for selecting the candidatures for the split regions permanently allocated to the registers.