Method, system, and computer program product for performing register promotion via load and store placement optimization within an optimizing compiler

• US 6,128,775 A
• Filed: 06/16/1998
• Issued: 10/03/2000
• Est. Priority Date: 06/16/1998
• Status: Expired due to Term

• Current Assignee: RPX Corporation
• Original Assignee: Silicon Graphics Incorporated (Graphics Properties Holdings, Inc.)
• Inventors: Chow, Frederick, Kennedy, Robert, Liu, Shin-Ming, Lo, Raymond, Tu, Peng, Chan, Sun C.
• Primary Examiner(s): Hafiz, Tariq R.
• Assistant Examiner(s): ZHEN, WEI Y
• Application Number:
  US09/097,713
• Time in Patent Office: 840 Days
• Field of Search: 395/709, 717/9
• US Class Current: 717/156
• CPC Class Codes: G06F 8/441 Register allocation; Assignment of physical memory space to logical memory space
• CPC Class Codes: G06F 8/443 Optimisation

Abstract

A method, system, and computer program product for performing register promotion, that optimizes placement of load and store operations of a computer program within a compiler. Based on the observation that the circumstances for promoting a memory location'"'"'s value to register coincide with situations where the program exhibits partial redundancy between accesses to the memory location, the system is an approach to register promotion that models the optimization as two separate problems: (1) the partial redundancy elimination (PRE) of loads and (2) the PRE of stores. Both of these problems are solved through a sparse approach to PRE. The static single assignment PRE (SSAPRE) method for eliminating partial redundancy using a sparse SSA representation representations the foundation in eliminating redundancy among memory accesses, enabling the achievement of both computational and live range optimality in register promotion results. A static single use (SSU) representation is defined allowing the dual of the SSAPRE algorithm, called SSUPRE, to perform the partial redundancy elimination of stores. SSUPRE is performed after the PRE of loads, taking advantage of the loads'"'"' having been converted into pseudo-register references so that there are fewer barriers to the movement of stores. Consequently, the compiler produces more efficient, register-promoted executable program code from the SSA representation.

Claims

1. A method for performing register promotion, that optimizes placement of load and store operations of a computer program, within a compiler, comprising the steps of:

(1) accessing a static single assignment (SSA) representation of the computer program;

(2) performing static single assignment partial redundancy elimination (SSAPRE) on said SSA representation to remove at least one redundant load operation, comprising the steps of;

(a) inserting Φ

functions at iterated post-dominance frontiers of loads and their left occurrences, where different values of said loads assigned values of left occurrences reach common points in the computer program, a result of each of said Φ

functions being stored in a hypothetical variable h;

(b) assigning an SSA version to each said hypothetical variable h in the computer program;

(c) determining whether each of said Φ

functions in the computer program is down safe;

(d) determining whether each of said loads or their assigned values will be available at each of said Φ

functions following eventual insertion of code into the computer program for purposes of partial redundancy elimination;

(e) transforming said SSA representation of the computer program having said hypothetical variables h to an SSA graph that includes some insertion information reflecting eventual insertions of code into the computer program for purposes of partial redundancy elimination; and

(f) updating said SSA graph based on said insertion information to introduce real temporary variables t for each of said hypothetical variables h;

thereby obtaining a first optimized SSA representation; and

(3) performing static single use partial redundancy elimination (SSUPRE) on said first optimized SSA representation, said SSUPRE internally using a single static use (SSU) representation to remove at least one redundant store operation, thereby obtaining a second optimized SSA representation;

whereby the compiler can produce more efficient, register-promoted executable program code from said second optimized SSA representation.

2. The method of claim 1, wherein step (3) comprises the step of:

processing said SSA representation of the computer program to eliminate partially redundant stores, wherein said processing comprises the steps of;

(a) inserting Λ

functions at iterated post-dominance frontiers of each store and iterated post-dominance frontiers of each load, the use of each of said Λ

functions being represented by a hypothetical variable h; and

(b) assigning a SSU version to each said hypothetical variable h in the computer program;

whereby a SSU representation of the computer program is obtained.

3. The method of claim 2, wherein step (3) further comprises the steps of:

(c) determining whether each of said Λ

functions in the computer program is up safe;

(d) determining whether each of said stores will be anticipated at each of said Λ

functions following eventual insertion of code into the computer program for purposes of partial redundancy elimination;

(e) identifying, through traversal in a pre-order walk of the computer program'"'"'s post-dominator tree of said SSU representation, the stores that will be fully redundant following eventual insertions of code into the computer program for purposes of partial redundancy elimination; and

(f) updating said SSU representation based on said insertion information to insert and delete stores for said hypothetical variables h.

4. A method for representing a computer program within a compiler in a static single use (SSU) representation, comprising the steps of:

(1) accessing a static single assignment (SSA) representation of the computer program;

(2) inserting Λ

functions in said SSA representation at iterated post-dominance frontiers of each store and iterated post-dominance frontiers of each load, the use of each of said Λ

functions being represented by a hypothetical variable h; and

(3) assigning a SSU version to each of said hypothetical variable h in the computer program;

whereby the SSU representation allows the compiler to eliminate partial redundancy among stores within the computer program.

5. A computer program product comprising a computer usable medium having computer readable program code means embodied in said medium for causing an application program to execute on a computer that optimizes placement of load and store operations of a computer program, within a compiler, said computer readable program code means comprising:

a first computer readable program code means for causing the computer to access a static single assignment (SSA) representation of the computer program;

a second computer readable program code means for causing the computer to perform static single assignment partial redundancy elimination (SSAPRE) on said SSA representation to remove at least one redundant load operation, comprising;

a third computer readable program code means for causing the computer to process said SSA representation of the computer program to eliminate partially redundant loads, wherein said third computer readable program code means comprises;

a fourth computer readable program code means for causing the computer to insert Φ

functions at iterated post-dominance frontiers of loads and their left occurrences, where different values of said loads assigned values of left occurrences reach common points in the computer program, a result of each of said Φ

functions being stored in a hypothetical variable h;

a fifth computer readable program code means for causing the computer to assign an SSA version to each said hypothetical variable h in the computer program;

a sixth computer readable program code means for causing the computer to determine whether each of said Φ

functions in the computer program is down safe;

a seventh computer readable program code means for causing the computer to determine whether each of said loads or their assigned values will be available at each of said Φ

functions following eventual insertion of code into the computer program for purposes of partial redundancy elimination;

an eighth computer readable program code means for causing the computer to transform said SSA representation of the computer program having said hypothetical variables h to an SSA graph that includes some insertion information reflecting eventual insertions of code into the computer program for purposes of partial redundancy elimination; and

a ninth computer readable program code means for causing the computer to update said SSA graph based on said insertion information to introduce real temporary variables t for each of said hypothetical variables h;

thereby obtaining a first optimized SSA representation; and

a tenth computer readable program code means for causing the computer to perform static single use partial redundancy elimination (SSUPRE) on said first optimized SSA representation, said SSUPRE internally using a single static use (SSU) representation to remove at least one redundant store operation, thereby obtaining a second optimized SSA representation;

wherein the compiler produces more efficient, register-promoted executable program code from said second optimized SSA representation.

6. The computer program product of claim 5, wherein said third computer readable program code means comprises:

an eleventh computer readable program code means for causing the computer to process said SSA representation of the computer program to eliminate partially redundant stores, wherein said eleventh computer readable program code means comprises;

a twelfth computer readable program code means for causing the computer to inserting Λ

functions at iterated post-dominance frontiers of each store and iterated post-dominance frontiers of each load, the use of each of said Λ

functions being represented by a hypothetical variable h; and

a thirteenth computer readable program code means for causing the computer to assigning a SSU version to each of said hypothetical variable h in the computer program;

whereby a SSU representation of the computer program is obtained.

7. The computer program product of claim 6, wherein said third computer readable program code means further comprises:

a fourteenth computer readable program code means for causing the computer to determine whether each of said Λ

functions in the computer program is up safe;

a fifteenth computer readable program code means for causing the computer to determine whether each of said stores will be anticipated at each of said Λ

functions following eventual insertion of code into the computer program for purposes of partial redundancy elimination;

a sixteenth computer readable program code means for causing the computer to identify, through traversal in a pre-order walk of the computer program'"'"'s post-dominator tree of said SSU representation, the stores that will be fully redundant following eventual insertions of code into the computer program for purposes of partial redundancy elimination; and

a seventeenth computer readable program code means for causing the computer to update said SSU representation based on said insertion information to insert and delete stores for said hypothetical variables h.

8. A computer program product comprising a computer usable medium having computer readable program code means embodied in said medium for causing an application program to execute on a computer that represents a computer program within a compiler in a static single use (SSU) representation, said computer readable program code means comprising:

a first computer readable program code means for causing the computer to access a static single assignment (SSA) representation of the computer program;

a second computer readable program code means for causing the computer to insert Λ

functions in said SSA representation at iterated post-dominance frontiers of each store and iterated post-dominance frontiers of each load, the use of each of said Λ

functions being represented by a hypothetical variable h; and

a third computer readable program code means for causing the computer to assign a SSU version to each of said hypothetical variable h in the computer program;

whereby the SSU representation allows the compiler to eliminate partial redundancy among stores within the computer program.