Silicon Graphics, Incorporated

Mips Computer Systems, Inc.

Frederick Chow

Raymond W Lo

Sun C Chan

Shin-Ming Liu

Mark Streich

Peng Tu

Robert Kennedy

Peter Dahl

Suneel Jain

Sin S Lew

A method and computer program product, within an optimizing compiler, for the global minimization of sign-extension and zero-extension operations in generated code during compilation. The method and computer program product allows, for example, 64-bit compilers targeting the Intel IA64 architecture to improve their SPECint benchmarks by reducing the number of sign-extension and zero-extension operations in the global and intra-procedural scope, thus, speeding up the execution of the compiled program.

Method and computer program product for global minimization of sign-extension and zero-extension operations

A method, system, and computer product uses a hashed static single assignment (SSA) form as a program representation and a medium for performing global scalar optimization. A compiler, after expressing the computer program in SSA form, can perform one or more static single assignment (SSA)-based, SSA-preserving global scalar optimization procedures on the SSA representation. Such a procedure modifies, (i.e., optimizes) the SSA representation of the program while preserving the utility of its embedded use-deprogram information for purposes of subsequent SSA-based, SSA-preserving global scalar optimizations. This saves the overhead expense of having to explicitly regenerate use-def program information for successive SSA-based, SSA-preserving global scalar optimizations.

Method, system, and computer program product for using static single assignment form as a program representation and a medium for performing global scalar optimization

A method, system, and computer program product for performing speculative code motion within a sparse partial redundancy elimination (PRE) framework. Speculative code motion (i.e., speculation) refers to the placement of computations by a compiler in positions in the program that results in some paths being executed more efficiently and some being executed less efficiently. A net speed-up is thus achieved when the improved paths are those executed more frequently during the program's execution. Two embodiments for performing speculative code motion within the PRE framework are presented: (1) a conservative speculation method used in the absence of profile data; and (2) a profile-driven speculation method used when profile data are available. In a preferred embodiment, the two methods may be performed within static single assignment PRE (SSAPRE) resulting in better optimized code.

Method, system, and computer program product for extending sparse

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.

System and method to efficiently represent aliases and indirect memory

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.

Method, system, and computer program product for performing register

Partial redundancy elimination of a computer program is described that operates using a static single assignment (SSA) representation of a computer program. The SSA representation of the computer program is processed to eliminate partially redundant expressions in the computer program. This processing involves inserting .PHI. functions for expressions where different values of the expressions reach common points in the computer program. A result of each of the .PHI. functions is stored in a hypothetical variable h. The processing also involves a renaming step where SSA versions are assigned to hypothetical variables h in the computer program, a down safety step of determining whether each .PHI. function in the computer program is down safe, and a will be available step of determining whether each expression in the computer program will be available at each .PHI. function following eventual insertion of code into the computer program for purposes of partial redundancy elimination. The processing also includes a finalize step of transforming the SSA representation of the computer program having hypothetical variables h to a SSA graph that includes some insertion information reflecting eventual insertions of code into the computer program for purposes of partial redundancy elimination, and a code motion step of updating the SSA graph based on the insertion information to introduce real temporary variables t for the hypothetical variables h.

System, method, and computer program product for partial redundancy

A system and method for optimizing a source code representation comprising a plurality of basic blocks are described. The optimized source code representation is to be executed in a target machine. The system operates by selecting from the source code representation a basic block pair comprising a source basic block and one or more target basic blocks. An instruction in the source basic block is identified that can be moved from the source basic block to the target basic block(s) while preserving program semantics. Either the instruction or a representation of the instruction is moved from the source basic block to the target basic block(s) as a function of resource utilization of the target machine that would result from this movement.

System and method for optimizing a source code representation as a

A procedure which is a particular type of software pipelining is provided which increases the efficiency with which code is executed by reducing or eliminating stalls such as by filling delay slots. The process includes moving instructions in a loop from one loop iteration to another. The moving of instructions provides the scheduler with additional independent instructions in a given basic block so the scheduler has greater freedom to move instructions into unfilled delay slots. The procedure includes changing the entry point into the loop, thus effectively moving an instruction from near the top of the loop to near the bottom of the loop, while changing the iteration number of the moved instruction.

Growing community of inventors

Fremont, CA, United States of America

Frederick Chow