System and method to efficiently represent aliases and indirect memory operations in static single assignment form during compilation

• US 6,131,189 A
• Filed: 11/26/1997
• Issued: 10/10/2000
• Est. Priority Date: 04/23/1996
• Status: Expired due to Term

• Current Assignee: RPX Corporation
• Original Assignee: Silicon Graphics Incorporated (Graphics Properties Holdings, Inc.)
• Inventors: Streich, Mark, Chow, Frederick, Chan, Sun, Liu, Shin-Ming, Lo, Raymond
• Primary Examiner(s): Chaki, Kakali
• Application Number:
  US08/979,939
• Time in Patent Office: 1,049 Days
• Field of Search: 395/705, 395/706, 395/707, 395/708, 395/709
• US Class Current: 717/141
• CPC Class Codes: G06F 8/443 Optimisation

Abstract

A system and method for an optimizer of a compilation suite for representing aliases and indirect memory operations in static single assignment (SSA) during compilation of a program having one or more basic blocks of source code. The optimizer converts all scalar variables of said program to SSA form, wherein said SSA form includes a plurality of variable versions, zero or more occurrences of a χ function, zero or more occurences of a φ function, and zero or more occurrences of a μ function. The χ function, φ function, and μ function are inserted for the variable versions. The optimizer also determines whether a variable version can be renamed to a zero version, and upon such a determination, the optimizer renames the variable version to a zero version. The optimizer further converts all indirect variables of a program to SSA form, wherein the SSA form includes a plurality of virtual variable versions such that a virtual variable is assigned to an indirect variable, zero or more occurrences of a χ function, zero or more occurences of a φ function, and zero or more occurrences of a μ function. The χ function, φ function, and μ function are inserted for the virtual variables. The optimizer hashes a unique value number and creates a corresponding hash table entry for each variable version and each virtual variable remaining after renaming all zero versions. The optimizer also applies global value numbering to each basic block of the program.

Claims

1. A method for representing aliases in single static assignment (SSA) during compilation of a program, comprising the steps of:

(a) converting scalar variables of said program to SSA form, said SSA form including a plurality of variable versions, zero or more occurrences of a χ

function, zero or more occurrences of a φ

function, and a zero or more occurrences of a μ

function, wherein said χ

function, said φ

function, and said μ

function are inserted for one or more of said variable versions;

(b) determining whether each one of said variable versions can be renamed to a zero version; and

(c) renaming one or more of said variable versions to said zero version.

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

renaming said one or more of said variable versions to said zero version if said variable versions that are defined by said χ

function have a real occurrence in said program.

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

renaming said one or more of said variable versions to said zero version if said variable versions that are defined by said φ

function have at least one operand of said φ

function that is zero version.

4. The method of claim 1, further comprising the following steps to be performed before step (a):

assigning virtual variables to one or more indirect variables of the program;

inserting at least one of said μ

functions and said χ

functions for each of said scalar variables and each of one or more virtual variables based on alias analysis;

inserting one or more φ

functions including at least one of said χ

functions as assignments;

renaming said scalar variables; and

renaming said virtual variables.

5. The method of claim 4, further comprising the following steps:

(d) generating a unique hash table entry in a hash table for each of said scalar variables and said virtual variables, wherein said hash table entry is either an operand or a node; and

(e) applying global value numbering.

6. The method of claim 4, wherein step (e) further comprises the steps of:

searching for existing matching hash table entries;

making one or more assignment statements point to a corresponding one of said generated nodes, wherein said assignment statements are created during conversion to SSA form; and

updating each of said χ

functions, said φ

functions, and said μ

functions so they refer to a corresponding one of said hash table entries in said hash table.

7. An optimizer for representing aliases in single static assignment (SSA) during compilation of a program, comprising:

SSA scalar means for converting scalar variables of the program to SSA form, said SSA form including a plurality of variable versions; and

zero version generating means for generating zero versions for non-real occurrences of said variable versions.

8. The optimizer of claim 7, wherein said zero version generating means comprises:

first zero version generating means that generates said zero version for said variable versions if said variable version that are defined by a χ

function have a real occurrence in said program; and

second zero version generating means that generates said zero version for said variable versions if said variable versions that are defined by a φ

function have at least one operand of said φ

function that is zero version.

9. The optimizer of claim 7, further comprising:

SSA virtual means for converting indirect variables of the program to SSA form, said SSA form including a plurality of virtual versions such that each of said plurality of virtual versions is assigned to one or more indirect variables.

10. The optimizer of claim 7, further comprising:

value numbering means for mapping a unique value number to each of said variable versions, wherein said unique value number is part of a global value number scheme in the form of one or more expression trees; and

hashing means for creating a corresponding hash table entry in a hash table for each of said variable versions, wherein said hash table entry is either an operand or a node.

11. The optimizer of claim 10, wherein said value number means further comprises:

directed acylic graph linking means for linking said node to a defining statement.

12. A computer, comprising:

a processor; and

SSA scalar means for enabling said processor to convert scalar variables of a program residing within memory of the computer to SSA form, said SSA form including a plurality of variable versions; and

zero version generating means for enabling said processor to generate zero versions for non-real occurrences of said variable versions.

13. The computer of claim 12, wherein said zero version generating means comprises:

first zero version generating means that generates said zero version for said variable versions if said variable versions that are defined by a χ

function have a real occurrence in said program; and

second zero version generating means that generates said zero version for said variable versions if said variable versions that are defined by a φ

function have at least one operand of said φ

function that is zero version.

14. The computer of claim 12, further comprising:

SSA virtual means for enabling said processor to convert indirect variables of a program to SSA form, said SSA form including a plurality of virtual versions such that each of said plurality of virtual versions is assigned to one or more indirect variables.

15. The computer of claim 12, further comprising:

value numbering means for enabling said processor to map a unique value number to each of said variable versions, wherein said unique value number is part of a global value number scheme in the form of one or more expression trees; and

hashing means for enabling said processor to create a corresponding hash table entry in a hash table for each of said variable versions, wherein said hash table entry is either an operand or a node.

16. The computer of claim 15, wherein said value number means further comprises:

directed acylic graph linking means for enabling said processor to link said node to a defining statement.