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

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 χ 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.

Inventors

• 👤 Frederick Chow
• 👤 Sun Chan
• 👤 Shin-Ming Liu
• 👤 Raymond Lo
• 👤 Mark Streich

Bibliographic Details