US6131189A
Expired / Lapsed
US
⏱️ 0.0 years remaining
System and method to efficiently represent aliases and indirect memory operations in static single assignment form during compilation
Assignee: RPX Corp
•
Filing: 1997-11-26
•
Granted: 2000-10-10
•
Expires: 2017-11-26
Abstract
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 chi function, zero or more occurences of a phi function, and zero or more occurrences of a mu function. The chi function, phi function, and mu 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 chi function, zero or more occurences of a phi function, and zero or more occurrences of a mu function. The chi function, phi function, and mu 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.
Inventors
- 👤 Frederick Chow
- 👤 Sun Chan
- 👤 Shin-Ming Liu
- 👤 Raymond Lo
- 👤 Mark Streich
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-04 08:30
CPC Classifications
G; G06; G06F; G06F8/00; G06F8/40; G06F8/41; G06F8/44; G06F8/443
Claims Analysis
Total Claims: 19
Claim 1
Independent Claim
115 words
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.
Claim 2
Independent Claim
115 words
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.
Claim 3
Dependent Claim
40 words
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.
Claim 4
Dependent Claim
46 words
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.
Claim 5
Dependent Claim
83 words
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.
Claim 6
Dependent Claim
49 words
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.
Claim 7
Dependent Claim
76 words
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.
Claim 8
Dependent Claim
54 words
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.
Claim 9
Dependent Claim
54 words
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.
Claim 10
Dependent Claim
83 words
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.
Claim 11
Dependent Claim
46 words
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.
Claim 12
Dependent Claim
76 words
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.
Claim 13
Dependent Claim
25 words
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.
Claim 14
Dependent Claim
58 words
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.
Claim 15
Dependent Claim
58 words
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.
Claim 16
Dependent Claim
83 words
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.
Claim 17
Dependent Claim
50 words
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.
Claim 18
Dependent Claim
84 words
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.
Claim 19
Dependent Claim
29 words
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.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-10-10 | 2004-04-10 | 2004-10-10 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-10-10 | 2008-04-10 | 2008-10-10 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-10-10 | 2012-04-10 | 2012-10-10 | $7700.00 | Window Closed / Lapsed |