System, method, and computer program product for partial redundancy elimination based on static single assignment form during compilation

Abstract

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.

Claims

What is claimed is:

1. An optimizer for optimizing a computer program, comprising:

accessing means for accessing a static single assignment (SSA) representation of a computer program; and

partial redundancy elimination (PRE) means for processing said SSA representation of said computer program to eliminate partially redundant expressions in said computer program, wherein said PRE means comprises .PHI.-insertion means for inserting .PHI. functions for expressions where different values of said expressions reach common points in said computer program, a result of each of said .PHI. functions being stored in a hypothetical variable h.

2. The optimizer of claim 1, wherein said hypothetical variable h is associated with each expression in said computer program.

3. The optimizer of claim 1, wherein said PRE means comprises:

renaming means for assigning a SSA version to each hypothetical variable h in said computer program.

4. The optimizer of claim 3, wherein said PRE means further comprises:

down safety means for determining whether each .PHI. function in said computer program is down safe; and

will be available means for determining whether each expression in said computer program will be available at each .PHI. function associated with said each expression following eventual insertion of code into said computer program for purposes of partial redundancy elimination.

5. The optimizer of claim 4, wherein said PRE means further comprises:

finalize means for transforming said SSA representation of said computer program having hypothetical variables h to a SSA graph that includes some insertion information reflecting eventual insertions of code into said computer program for purposes of partial redundancy elimination; and

code motion means for updating said SSA graph based on said insertion information to introduce real temporary variables t for said hypothetical variables h.

6. The optimizer of claim 5, wherein said PRE means further comprises:

collect occurrences means for scanning said SSA representation of said computer program to create a work list of first order expressions in said computer program that need to be considered during optimization.

7. The optimizer of claim 3, wherein said renaming means utilizes a delayed renaming approach.

8. A method for optimizing a computer program, comprising the steps of:

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

(2) processing said SSA representation of said computer program to eliminate partially redundant expressions in said computer program, wherein said processing step comprises the steps of inserting .PHI. functions for expressions where different values of said expressions reach common points in said computer program, a result of each of said .PHI. functions being stored in a hypothetical variable h.

9. The method of claim 8, wherein said hypothetical variable h is associated with each expression in said computer program.

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

assigning a SSA version to each hypothetical variable h in said computer program.

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

(c) determining whether each .PHI. function in said computer program is down safe; and

(d) determining whether each expression in said computer program will be available at each .PHI. function associated with said each expression following eventual insertion of code into said computer program for purposes of partial redundancy elimination.

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

(e) transforming said SSA representation of said computer program having hypothetical variables h to a SSA graph that includes some insertion information reflecting eventual insertions of code into said 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 said hypothetical variables h.

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

(g) scanning said SSA representation of said computer program to create a work list of first order expressions in said computer program that need to be considered during optimization.

14. The method of claim 10, wherein step (b) utilizes a delayed renaming approach.

15. A computer program product comprising a computer useable medium having computer program logic recorded thereon, said computer program logic comprising:

accessing means for enabling a processor to access a static single assignment (SSA) representation of a computer program; and

partial redundancy elimination (PRE) means for enabling the processor to process said SSA representation of said computer program to eliminate partially redundant expressions in said computer program, wherein said PRE means comprises .PHI.-insertion means for enabling the processor to insert .PHI. functions for expressions where different values of said expressions reach common points in said computer program, a result of each of said .PHI. functions being stored in a hypothetical variable h.

16. The computer program product of claim 15, wherein said hypothetical variable h is associated with each expression in said computer program.

17. The computer program product of claim 15, wherein said PRE means comprises:

renaming means for enabling the processor to assign a SSA version to each hypothetical variable h in said computer program.

18. The computer program product of claim 17, wherein said PRE means further comprises:

down safety means for enabling the processor to determine whether each .PHI. function in said computer program is down safe; and

will be available means for enabling the processor to determine whether each expression in said computer program will be available at each .PHI. function associated with said each expression following eventual insertion of code into said computer program for purposes of partial redundancy elimination.

19. The computer program product of claim 18, wherein said PRE means further comprises:

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

code motion means for enabling the processor to update said SSA graph based on said insertion information to introduce real temporary variables t for said hypothetical variables h.

20. The computer program product of claim 19, wherein said PRE means further comprises:

collect occurrences means for enabling the processor to scan said SSA representation of said computer program to create a work list of first order expressions in said computer program that need to be considered during optimization.

21. The computer program product of claim 17, wherein said renaming means enables the processor to utilize a delayed renaming approach.

Description

A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent disclosure, as it appears in the Patent and Trademark Office patent files or records, but otherwise reserves all copyright rights whatsoever.

BACKGROUND OF THE INVENTION

1. Field of the Invention

This invention generally relates to computer software compilers, and more particularly to optimizers in computer software compilers that perform an opimization called partial redundancy elimination (PRE).

2. Related Art

The Static Single Assignment Form (SSA) has become a popular program representation in optimizing compilers, because it provides accurate use-definition (use-def) relationships among the program variables in a concise form. Before proceeding further, it may be useful to briefly describe SSA.

In SSA form, each definition of a variable is given a unique version, and different versions of the same variable can be regarded as different program variables. Each use of a variable version can only refer to a single reaching definition. When several definitions of a variable, a.sub.1, a.sub.2, . . . , a.sub.m, reach a common node (called a merging node) in the control flow graph of the program, a .phi. function assignment statement, a.sub.n =.phi.(a.sub.1, a.sub.2, . . . , a.sub.m), is inserted to merge the variables into the definition of a new variable version a.sub.n. Thus, the semantics of single reaching definitions are maintained.

Many efficient global optimization algorithms have been developed based on SSA. Among these optimizations are dead store elimination, constant propagation, value numbering, induction variable analysis, live range computation, and global code motion. However, all these uses of SSA have been restricted to solving problems based on program variables, since the concept of use-def does not readily apply to expressions. Noticeably missing among SSA-based optimizations is partial redundancy elimination.

Partial redundancy elimination (PRE) is a powerful optimization algorithm. PRE was first described in E. Morel and C. Renvoise, "Global optimization by suppression of partial redundancies," Comm ACM, 22(2):96-103, February 1979. PRE targets partially redundant computations in a program, and removes global common subexpressions and moves invariant computations out of loops. PRE has since become the most important component in many global optimizers.

PRE shall now be generally described with reference to FIGS. 10A and 10B. FIG. 10A illustrates a program control flow graph having basic blocks 1002, 1004, 1006. Basic blocks 1004 and 1006 contain an expression a+b. There are two paths through this control flow graph: basic block 1002 to basic block 1006, and basic block 1004 to basic block 1006. When the path from basic block 1102 to basic block 1006 is taken, the expression a+b is performed only once. However, when the path from basic block 1004 to basic block 1006 is taken, the expression a+b is redundantly performed twice. Accordingly, the scenario shown in FIG. 10A is an example of partial redundancy of the expression a+b.

For performance purposes, it would be desirable to eliminate the expression a+b in basic block 1006, since its performance in basic block 1006 is redundant to its performance in basic block 1004. However, the expression a+b is not performed in basic block 1002. Accordingly, without additional modification, the expression a+b cannot be eliminated from basic block 1006.

PRE works as shown in FIG. 10B. According to PRE, the results of expression a+b is stored in a variable t in basic block 1004. This expression from basic block 1004 is inserted in basic block 1002, thereby making the expression fully redundant. Then, the expression a+b is eliminated from basic block 1006, and all references to it are replaced by the variable t.

Knoop et al. formulated an alternative placement strategy called lazy code motion that improves on Morel and Renvoise's results by avoiding unnecessary code movements, and by removing the bidirectional nature of the original PRE data flow equations. The result of lazy code motion is optima: the number of computations cannot be further reduced by safe code motion, and the lifetimes of the temporaries introduced are minimized. See J. Knoop, O. Ruthing, and B. Steffen, "Lazy code motion," Proceedings of the ACM SIGPLAN '92 Conference on Programming Language Design and Implementation, pages 224-234, June 1992; J. Knoop, O. Ruthing, and B. Steffen, "Optimal code motion: Theory and practice," ACM Trans. on Programming Languages and Systems 16(4):1117-1155, October 1994.

Drechsler and Stadel gave a simpler version of the lazy code motion algorithm that inserts computations on edges rather than in nodes. See K. Drechsler and M. Stadel, "A variation of Knoop, Ruthing and Steffen's lazy code motion," SIGPLAN Notices, 28(5):29-38, May 1993. It should be noted that the above published algorithms do not utilize SSA.

Optimizations based on SSA all share the common characteristic that they do not require traditional iterative data flow analysis in their solutions. They all take advantage of the sparse representation of SSA.

In a sparse form, information associated with an object is represented only at places where it changes, or when the object actually occurs in the program. Because it does not replicate information over the entire program, a sparse representation conserves memory space. Information can be propagated through the sparse representation in a smaller number of steps, speeding up most algorithms.

To get the full benefit of sparseness, one must typically give up operating on all elements in the program in parallel, as in traditional bit-vector-based data flow analysis. But operating on each element separately allows optimization decisions to be customized for each object.

There is another advantage of using SSA to perform global optimization. Traditional non-SSA optimization techniques often implement two separate versions of the same optimization: a global version that uses bit vectors in each basic block, and a simpler and faster local version that performs the same optimization within a basic block. SSA-based optimization algorithms do not need to distinguish between global and local optimizations. The same algorithm can handle both global and local versions of an optimization simultaneously. The amount of effort required to implement each optimization can be correspondingly reduced.

Prior to the present invention, a PRE algorithm based on SSA did not exist. As was hinted in D. Dhamdhere, B. Rosen, and K. Zadeck, "How to analyze large programs efficiently and informatively," Proceedings of the ACM SIGPLAN '92 Conference on Programming Language Design and Implementation, pages 212-223, June 1992, any attempt at developing a PRE algorithm based on SSA is difficult because an expression E can be redundant as the result of many different computations at different places of the same expression E', E", . . . whose operands have different SSA versions from the operands of E. This is illustrated in FIG. 3A, where the expression E is generally represented by a+b.

In such a situation, the use-def chain of SSA does little to help in recognizing that E is partially redundant (see basic blocks 302 and 308). It also does not help in effecting the movement of computations. Lacking an SSA-based PRE algorithm, optimizers that use SSA have to switch to bit-vector algorithms in performing PRE. To apply subsequent SSA-based optimizations, it is necessary to convert the results of PRE back into SSA form, and such incremental updates based on arbitrary modifications to the program are expensive.

Accordingly, what is required is a compiler that performs partial redundancy elimination (PRE) using the SSA form.

Before proceeding further, it may be useful to consider work aimed at improving the efficiency of data flow analysis and PRE.

By generalizing SSA form, Choi et al. derived Sparse Evaluation Graphs as reduced forms of the original flow graph for monotone data flow problems related to variables. The technique must construct a separate sparse graph per variable for each data flow problem, before solving the data flow problem for the variable based on the sparse graph. Thus, it cannot practically be applied to PRE, which requires the solution of several different data flow problems. See J. Choi, R. Cytron, and J. Ferrante, "Automatic construction of sparse data flow evaluation graphs," Conference Record of the Eighteenth ACW Symposium on Principles of Programming Languages, pages 55-66, January 1991.

Dhamdhere et al. observed that in solving for a monotone data flow problem, it suffices to examine only the places in the problem where the answer might be different from the trivial default answer .perp.. There are only three possible transfer functions for a node: raise to , lower to .perp., or identity (propagate unchanged). They proposed slotwise analysis. For nodes with the identity transfer function, those that are reached by any node whose answer is .perp. will have .perp. as their answer. By performing the propagation slotwise, the method can arrive at the solution for each variable in one pass over the control flow graph. Slotwise analysis is not sparse, because it still performs the propagation with respect to the control flow graph of the program. The approach can be used in place of the iterative solution of a monotone data flow problem as formulated. It can be used to speed up the data flow analyses in PRE. See D. Dhamdhere, B. Rosen, and K. Zadeck, "How to analyze large programs efficiently and informatively," Proceedings of the ACM SIGPLAN '92 Conference on Programming Language Design and Implementation, pages 212-223, June 1992.

Johnson proposed the use of Dependence Flow Graphs (DFG) as a sparse approach to speed up data flow analysis. The DFG of a variable can be viewed as its SSA graph with additional "merge" operators imposed to identify single-entry single-exit (SESE) regions for the variable. By identifying SESE regions with the identity transfer function, the technique can short-circuit propagation through them. Johnson showed how to apply his techniques to the data flow systems in Drechsler and Stadel's variation of Knoop et al.'s lazy code motion. See R. Johnson, "Efficient program analysis using dependence flow graphs," Technical Report (PhD Thesis), Dept. of Computer Science, Cornell University, August 1994.

Researches at Rice University have done worked aimed at improving the effectiveness of PRE. The work involves the application of some SSA-based transformation techniques to prepare the program for optimization by PRE. Their techniques enhance the results of PRE. Their implementation of PRE was based on Drechsler and Stadel's variation of Knoop et al.'s lazy code motion, and was unrelated to SSA. See P. Briggs and K. Cooper, "Effective partial redundancy elimination," Proceedings of the ACM SIGPLAN '94 Conference on Programming Language Design and Implementation, pages 159-170, June 1994; and K. Cooper and T. Simpson, "Value-driven code motion," Technical Report CRPC-TR95637-S, Dept. of Computer Science, Rice University, October 1995.

All prior work related to PRE (including those described above) has modeled the problem as systems of data flow equations. Regardless of how efficiently the systems of data flow equations can be solved, a substantial amount of time needs to be spent in scanning the contents of each basic block in the program to initialize the local data flow attributes that serve as input to the data flow equations. Experience has shown that this often takes more time than the solution of the data flow equations, so a fundamentally new approach to PRE that does not require the dense initialization of data flow information is highly desirable. A PRE algorithm based on SSA would solve this problem, since SSA is sparse. However, prior to the present invention, a PRE algorithm based on SSA did not exist.

SUMMARY OF THE INVENTION

The present invention is directed to a system, method, and computer program product that performs PRE directly on an SSA representation of the computer program. The approach of the invention is called Static Single Assignment Partial Redundancy Elimination (SSAPRE).

SSAPRE is sparse because it does not require collecting traditional local data flow attributes over the program and it does not require any form of iterative data flow analysis to arrive at its solution. SSAPRE works by constructing the SSA form of a hypothetical temporary h that could be used to store the result of each computation (expression) in the program. In the resulting SSA form of h, a def (definition) corresponds to a computation whose result may need to be saved, and a use corresponds to a redundant computation that may be replaced by a load of h.

Based on this SSA form of h, SSAPRE then applies the analyses corresponding to PRE. The analyses allow the identification of additional defs of h, with accompanying computations, that need to be inserted to achieve optimal code motion. The final output is generated according to the updated SSA graph of h: temporaries t are introduced into the program to save and reuse the values of computations.

Since the algorithm works by modeling the SSA forms of the hypothetical temporaries h, the real temporaries t introduced are maintained with SSA properties. The results of the SSAPRE approach of the present invention are shown in the example of FIG. 3B (corresponding to FIG. 3A).

More particularly, the present invention is directed to a system, method, and computer program product for performing PRE optimization of a computer program. The invention operates using a static single assignment (SSA) representation of a computer program. The invention processes the SSA representation of the computer program to eliminate partially redundant expressions in the computer program.

This processing of the invention 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 invention also performs a renaming step where SSA versions are assigned to hypothetical variables h in the computer program. In an embodiment of the invention, the renaming step involves a delayed renaming approach.

The invention further performs 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 invention additionally performs 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.

The invention optionally performs a collect-occurrences step of scanning the SSA representation of the computer program to create a work list of expressions in the computer program that need to be considered during optimization.

Further features and advantages of the invention, as well as the structure and operation of various embodiments of the invention, are described in detail below with reference to the accompanying drawings. In the drawings, like reference numbers generally indicate identical, functionally similar, and/or structurally similar elements. The drawing in which an element first appears is indicated by the leftmost digit(s) in the corresponding reference number.

BRIEF DESCRIPTION OF THE FIGURES

The present invention will be described with reference to the accompanying drawings, wherein:

FIG. 1 is a block diagram and a data flow diagram of a compiler according to an embodiment of the invention;

FIG. 2 is a block diagram illustrating an exemplary computer system useful for implementing components of the invention;

FIG. 3A is used to describe partial redundancy elimination;

FIG. 3B illustrates the results of the SSAPRE approach of the present invention;

FIGS. 4-8 illustrate phases of an example program used to illustrate the operation of the present invention;

FIG. 9 is a flowchart representing the operation of an optimizer according to an embodiment of the invention;

FIGS. 10A and 10B are used to further describe partial redundancy elimination;

FIGS. 11-13 are used to describe dominance, dominator trees, and dominance frontiers;

FIG. 14 is a flowchart representing the operation of a .PHI.-Insertion step according to an embodiment of the invention;

FIG. 15 is used to describe down safety;

FIG. 16 is a flowchart representing the operation of a Down Safety step according to an embodiment of the invention;

FIG. 17 is a flowchart representing the operation of a Will Be Available step according to an embodiment of the invention;

FIG. 18 is a flowchart representing the operation of a Finalize step according to an embodiment of the invention; and

FIG. 19 is a flowchart representing the operation of a Code Motion step according to an embodiment of the invention.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

1.0 Overview of the Invention

The present invention is directed to a computer software compiler 100. FIG. 1 illustrates the components of a compiler 100, and the flow of data between the compiler components. The components of a compiler 100 include: a front end 104, optimizer 106, and code generator 108.

In operation, a user 102 submits source code 103 to the compiler 100. The front end 104 component of the compiler 100 receives the source code 103 and produces a first internal representation, called internal representation A 105 for convenience purpose only. The optimizer 106 inputs and analyzes the internal representation A 105. Based on its analysis, the optimizer 106 restructures and otherwise modifies portions of the internal representation A 105, thereby making it more efficient code. The resulting efficient code is called internal representation B 107 for convenience purpose only.

The code generator 108 inputs the internal representation B 107 and generates object code 109. The object code 109 is then available to the user to link and load, thereby creating an executable image of the source code 103 for running on a computer system.

Compiler technology is described in a number of publicly available documents, such as Aho et al., Compilers: Principles, Techniques, and Tools, Addison Wesley, 1986, which is herein incorporated by reference in its entirety.

A preferred embodiment of the present invention is directed to the optimizer 106. The SSAPRE approach of the invention is performed by the optimizer 106.

2.0 Host System of the Preferred Embodiment

An embodiment of the present invention is computer software executing within a computer system. FIG. 2 shows an exemplary computer system 202. The compiler 100 of the present invention may execute in the computer system 202. Also, code generated by the compiler 100 may execute in the computer system 202.

The computer system 202 includes one or more processors, such as a processor 204. The processor 204 is connected to a communication bus 206.

The computer system 202 also includes a main memory 208, preferably random access memory (RAM), and a secondary memory 210. The secondary memory 210 includes, for example, a hard disk drive 212 and/or a removable storage drive 214, representing a floppy disk drive, a magnetic tape drive, a compact disk drive, a compact disk drive, an optical drive, a ZIP drive, a JAZZ drive, etc. The removable storage drive 214 reads from and writes to a removable storage unit 216.

Removable storage unit 216, also called a program storage device or a computer program product, represents a floppy disk, magnetic tape, compact disk, ZIP disk, JAZZ disk, optical disk, etc. As will be appreciated, the removable storage unit 216 includes a computer usable storage medium having stored therein computer software and/or data. The removable storage drive 214 reads from and/or writes to the removable storage unit 116 in a well known manner.

The computer system 202 may also include a communications interface 218, such as a network card, and one or more input devices (such as a keyboard, mouse, trackball, etc.). The computer system 202 also includes one or more display units 222.

In an embodiment where the invention is implemented using software, the software (also called control logic) may be stored in main memory 208, in secondary memory 210, and/or in a removable storage unit 216. The software, when executed by the processor 204, causes the processor 204 to perform the functions of the invention as described herein.

In another embodiment, the invention is implemented primarily in hardware using, for example, a hardware state machine. Implementation of the hardware state machine so as to perform the functions described herein will be apparent to persons skilled in the relevant arts.

The preferred embodiment of the present invention is directed to execute on a computer system 202 in which the processor 204 is any processor, including but not limited to a MIPS, Intel, AMD, Digital, etc., processor. The preferred embodiment of the present invention is implemented in software, and more specifically, is written in the programming language C++. The preferred embodiment is described in these terms for convenience purpose only. The invention is not limited to these specific embodiments. Other computer systems 202, other processors 204, and other programming languages capable of performing the functions described herein could alternatively be used.

3.0 Overview of the SSAPRE Approach

The input to SSAPRE is an SSA representation of the program (i.e., source code 103). In SSA, each definition of a variable is given a unique version, and different versions of the same variable can be regarded as different program variables. Each use of a variable version can only refer to a single reaching definition. By virtue of the versioning, use-def information is built into the representation. Where several definitions of a variable, a.sub.1, a.sub.2, . . . , a.sub.m, reach a confluence point (also called a merging node, or a confluence node) in the control flow graph of the program, a .phi. function assignment statement, a.sub.n .rarw..phi.(a.sub.1, a.sub.2, . . . , a.sub.m), is inserted to merge them into the definition of a new variable version a.sub.n Thus the semantics of single reaching definitions are maintained. This introduction of a new variable version as the result of .phi. factors the set of use-def edges over confluence nodes, reducing the number of use-def edges required to represent the program. In SSA, the use-def chain for each variable can be provided by making each version point to its single definition. One important property of SSA form is that each definition must dominate all its uses in the control flow graph of the program if the uses at .phi. operands are regarded as occurring at the predecessor nodes of their corresponding edges.

It is assumed that all expression are represented as trees with leaves that are either constants or SSA-renamed variables. SSAPRE can be applied to program expressions independently, regardless of subexpression relationships. In Section 6, below, there is described a strategy according to the invention that exploits the nesting relationship in expression trees to obtain greater optimization efficiency under SSAPRE. Indirect loads are also candidates for SSAPRE, but since they reference memory and can have aliases, the indirect variables have to be in SSA form in order for SSAPRE to handle them.

In an embodiment of the invention, the optimizer 106 processes a computer program in a HSSA (Hashed SSA) form. The HSSA form represents a uniform SSA representation of all the scalar and indirect memory operations of the program based on global value. Use of the HSSA form allows SSAPRE to uniformly handle indirect loads together with other expressions in the program. The HSSA form is described in pending U.S. application Ser. No. 08/636,605 filed Apr. 23, 1996, now U.S. Pat. No. 5,768,596, titled "A System and Method to Efficiently Represent Aliases and Indirect Memory Operations in Static Single Assignment Form During Compilation," incorporated by reference herein in its entirety. The HSSA form is also described in F. Chow, S. Chan, S. Liu, R. Lo, and M. Streich, "Effective representation of aliases and indirect memory operations in SSA form," Proceedings of the Sixth International Conference on Compiler Construction, pages 253-267, April 1996, incorporated by reference herein in its entirety. In an alternate embodiment, the optimizer 106 processes a computer program in SSA form.

FIG. 9 illustrates a flowchart 902 representing the operation of the optimizer 106 when performing SSAPRE. The performance of SSAPRE includes six steps: (1) .PHI.-Insertion (step 912), (2) Rename (step 914), (3) DownSafety (step 918), (4) WillBeAvail (step 920), (5) Finalize (922), and (6) CodeMotion (step 926). Some embodiments also include the performance of a Collect-Occurrences function (step 906).

SSAPRE works by conducting a round of SSA construction on the lexically identical expressions in the program whose variables are already in SSA form. Expressions are lexically identical if they apply exactly the same operator to exactly the same operands; the SSA versions of the variables are ignored in matching expressions. For example, a.sub.1 +b.sub.1 and a.sub.2 +b.sub.2 are lexically identical expressions.

Since the term SSA cannot be meaningfully applied to expressions, SSAPRE defines it to refer to the hypothetical temporary h that could be used to store the result of the expression. The symbol .PHI. is used herein to refer to an expression or function assignment statement. This is in contrast to the symbol .phi., which is used to refer to a variable assignment statement.

The .PHI.-Insertion step 912 and the Rename step 914 are the initial SSA construction steps for expressions. This round of SSA construction can use an approach that works on all expressions in the program simultaneously. Such an approach is generally described in R. Cytron, J. Ferrante, B. K. Rosen, M. N. Wegman, and F. K. Zadeck, "Efficiently computing static single assignment form and the control dependence graph," ACM Trans. on Programming Languages and Systems, 13(4):451-490, October 1991, which is herein incorporated by reference in its entirety. Alternatively, an implementation may choose to work on each lexically identical expression in sequence. Such an approach, which is a sparse implementation, is described in Section 6.

Assume that we are working on the expression a+b, whose hypothetical temporary is h. After the Rename step 914, occurrences of a+b corresponding to the same version of h must compute to the same value. At this stage, the points of defs and uses of h have not yet been identified. Many .PHI.'s inserted for h are also unnecessary. Later steps in SSAPRE correct this. Some .PHI. operands can be determined to be undefined (.perp.) after the Rename step 914 because there is no available computation of a+b. These .perp.-valued .PHI. operands play a key role in the later steps of SSAPRE, because insertions are performed only because of them. We call the SSA graph 916 for h after the Rename step 914 a dense SSA graph because it contains more .PHI.'s than in the minimal SSA form, which is defined in R. Cytron, J. Ferrante, B. K. Rosen, M. N. Wegman, and F. K. Zadeck, "Efficiently computing static single assignment form and the control dependence graph," ACM Trans. on Programming Languages and Systems, 13(4):451-490, October 1991.

The sparse computation of global data flow attributes for a+b can be performed on the dense SSA graph for h. Two separate phases are involved. The first phase, the Down-Safety step 918, performs backward propagation to determine the .PHI.'s whose results are not fully anticipated with respect to a+b. The second phase is the WillBeAvail step 920, which performs forward propagation to determine the .PHI.'s where the computation of a+b will be available assuming PRE insertions have been performed at the appropriate incoming edges of the .PHI.'s.

Using the results of the WillBeAvail step 920, the optimizer 106 is ready to finalize the effects of PRE. The Finalize step 922 inserts computation of a+b at the incoming edges of .PHI. to ensure that the computation is available at the merge point. For each occurrence of a+b in the program, it determines if it is a def or use of h. It also links the uses of h to their defs to form its precise SSA graph. Extraneous .PHI.'s are removed so that h is in minimal SSA form.

The last step is to update the program to effect the code motion for a+b as determined by SSAPRE. The CodeMotion step 926 introduces the real temporary t to eliminate the redundant computations of a+b. It walks over the precise SSA graph of h and generates saves of the computation a+b into t, giving each t its unique SSA version. Redundant computations of a+b are replaced by t. The .PHI.'s for h are translated into .phi.'s for t in the native program representation.

The SSAPRE algorithm performed by the optimizer 106 is described in greater detail below.

4.0 Operation of the SSAPRE Approach

In this section, the SSAPRE algorithm performed by the optimizer 106 is described. In an embodiment, it is assumed that all critical edges in the control flow graph have been removed by inserting empty basic blocks at such edges. See J. Knoop, O. Ruthing, and B. Steffen, "Lazy code motion," Proceedings of the ACM SIGPLAN '92 Conference on Programming Language Design and Implementation, pages 224-234, June 1992; and K. Drechsler and M. Stadel, "A variation of Knoop, Ruthing and Steffen's lazy code motion," SIGPLAN Notices, 28(5):29-38, May 1993, which are herein incorporated by reference in their entireties. This allows insertions to be modeled as edge placements, even though insertions are only done at the ends of the predecessor blocks.

It is also assumed that the dominator tree (DT) and dominance frontiers (DF's) with respect to the control flow graph of the program being compiled have been previously computed. These data must have already been computed and used when the program was first put into SSA form.

It will be useful at this point to briefly describe dominance, dominator trees, and dominance frontiers, which are all well known concepts.

A basic block d of a control flow graph dominates basic block n, written d dom n, if every path from the initial basic block of the control flow graph to n goes through d. Under this definition, every basic block dominates itself, and the entry of a loop dominates all basic blocks in the loop.

Consider the example control flow graph 1102 with initial basic block 1 shown in FIG. 11. The initial basic block 1 dominates every basic block. Basic block 2 dominates only itself, since control can reach any other basic block along a path that begins 1.fwdarw.3. Basic block 3 dominates all but 1 and 2. Basic block 4 dominates all but 1, 2 and 3. Basic blocks 5 and 6 dominate only themselves, since flow of control can skip around either by going through the other. Finally, basic block 7 dominates 7, 8, 9, 10; basic block 8 dominates 8, 9, 10; 9 and 10 dominate only themselves.

A useful way of presenting dominator information is in a tree, called the dominator tree, in which the initial basic block is the root, and each basic block d dominates only its descendants in the tree. For example, FIG. 12 shows the dominator tree for the control flow graph of FIG. 11.

Dominance frontier is another useful concept. Dominance frontiers of a basic block A are the basic blocks that are not dominated by basic block A, but that are adjacent (linked) to basic blocks dominated by basic block A. Consider the example control flow graph 1302 in FIG. 13. Basic block 1 dominates basic blocks 2, 3, and 4. Basic blocks 5 and 6 are not dominated by basic block 1, but are adjacent to basic blocks 2 and 4, which are dominated by basic block 1. Accordingly, the dominance frontiers of basic block 1 are basic blocks 5 and 6.

These compiler concepts are described in Aho et al., Compilers: Principles, Techniques, and Tools, Addison Wesley, 1986. Dominance frontiers are described in R. Cytron, J. Ferrante, B. K. Rosen, M. N. Wegman, and F. K. Zadeck, "Efficiently computing static single assignment form and the control dependence graph," ACM Trans. on Programming Languages and Systems, 13(4):451-490, October 1991, incorporated herein by reference.

The following discussion is based on the expression a+b whose hypothetical temporary is h. An example program 402 shown in FIG. 4 is used to illustrate the various steps. Based on the algorithms described, the sections below also state and prove various lemmas, which are used in establishing the theorems about SSAPRE in Section 5.

4.1 The .PHI. -Insertion Step

A .PHI. for an expression must be inserted whenever different values of the same expression reach a common point in the program. .PHI.'s are inserted during step 912 (FIG. 9). The operation of the optimizer 106 when performing step 912 is represented by a flowchart 1402 in FIG. 14.

In step 1406, a hypothetical temporary h is associated with each expression or function in the control flow graph. For example, in FIG. 4, a hypothetical temporary h is associated with the expression a.sub.1 +b.sub.1 in basic block There are two different situations that cause .PHI.'s for expressions to be inserted:

First, when an expression appears in a basic block, the optimizer 106 must insert a .PHI. in the basic block's iterated dominance frontiers (DF.sup.+), because the occurrence may correspond to a definition of h. This operation is represented by step 1408. For example, in FIG. 5 (that corresponds to the example control flow graph in FIG. 4), a .PHI. is inserted at block 3 due to a+b in block 1.

The second situation that causes insertion of .PHI.'s is when there is a .phi. for a variable contained in the expression, because that indicates an alteration of the expression when it reaches a merge point. The optimizer 106 only inserts a .PHI. at a merge point when it reaches a later occurrence of the expression, because otherwise the .PHI. will not contribute to any optimization in PRE. Each inserted .PHI. function is assigned to a hypothetical variable h (this is consistent with the operation of step 1406, since .PHI. represents a function or expression). This operation is represented by step 1410. For example, in FIG. 5, the .PHI. for h inserted in block 8 is caused by the .phi. for a in the same block. It is not necessary to insert any .PHI. at block 10 even though it is a merge point, because there is no later occurrence of a+b after block 10.

Preferably, both types of .PHI. insertions (steps 1408 and 1410) are performed together in one pass over the program, with the second type of .PHI. insertion (step 1410) performed in a demand-driven way. Preferably, the optimizer 106 uses a set DF.sub.-- phis[i] to keep track of the .PHI.'s inserted due to DF.sup.+ of the occurrences of expression E.sub.i (step 1408). The optimizer 106 uses a set Var.sub.-- phis[i][j] to keep track of the .PHI.'s inserted due to the occurrence of .phi.'s for the j.sup.th variable in expression E.sub.i (step 1410). When the optimizer 106 encounters an occurrence of expression E.sub.i, the optimizer 106 updates DF-phis[i]. For each variable .nu..sub.j in the occurrence, the optimizer 106 checks if it is defined by a .phi.. If it is, the optimizer 106 updates Var-phis[i][j], because a .PHI. at the block that contains the .phi. for .nu..sub.j may contribute to optimization of the current occurrence of E.sub.i. The same may apply to earlier points in the program as well, so it is necessary to recursively check for updates to Var-phis[i][j] for each operand in the .phi. for .nu..sub.j. After all occurrences in the program have been processed, the places to insert .PHI.'s for E.sub.i are given by the union of DF-phis[i] with the Var-phis[i][j]'s.

By using this demand-driven technique, the invention takes advantage of the SSA representation in the input program.

The algorithm for the .PHI.-Insertion step 912 is alternatively represented using the following high level pseudocode:

    ______________________________________
    procedure .PHI.-Insertion
    for each expression E.sub.i do {
    DF.sub.-- phis[i] .rarw. empty-set
    for each variable j in E.sub.i do
    Var.sub.-- phis[i][j] .rarw. { }
    for each occurrence X of E.sub.i in program do {
    DF.sub.-- phis[i].rarw. DF.sub.-- phis[i] .orgate. DF.sup.+  (X)
    for each variable occurence V in X do
    if (V is defined by .phi.) {
            j .rarw. index of V in X
            Set.sub.-- var.sub.-- phis(Phi(V), i, j)
    }
    }
    for each expression E.sub.i do {
    for each variable j in E.sub.i do
    DF.sub.-- phis[i].rarw. DF.sub.-- phis[i].orgate. Var.sub.-- phis[i][j]
    insert .PHI.'s for E.sub.i according to DF.sub.-- phis[i]
    }
    end .PHI.-Insertion
    procedure Set.sub.-- var.sub.-- phis(phi, i, j)
    if (phi .epsilon slash. Var.sub.-- phis[i][j]) {
    Var.sub.-- phis[i][j] .rarw. Var.sub.-- phis[i][j] .orgate. {phi}
    for each operand V in phi do
    if (V is defined by .phi.)
            Set.sub.-- var.sub.-- phis(Phi(V), i, j)
    }
    end Set.sub.-- var.sub.-- phis
    ______________________________________
     Copyright, Silicon Graphics, Inc., 1997

    ______________________________________
    procedure DownSafety
    for each expr-.PHI. F in program do
            if (not down.sub.-- safe (F))
              for each operand opnd of F do
                Reset.sub.-- downsafe (opnd)
    end DownSafety
    procedure Reset.sub.-- downsafe(X)
    if (has.sub.-- real.sub.-- use(X) or X not defined by .PHI.)
            return
    F .rarw. .PHI. that defines X
    if (not down.sub.-- safe(F))
            return
    down.sub.-- safe(F) .rarw. false
    for each operand opnd of F do
            Reset.sub.-- downsafe(opnd)
    end Reset.sub.-- downsafe
    ______________________________________
     Copyright, Silicon Graphics, Inc., 1997

    ______________________________________
    procedure Compute.sub.-- can.sub.-- be.sub.-- avail
    for each expr-.PHI. F in program do
    if (not down.sub.-- safe(F) and
            can.sub.-- be.sub.-- avail (F) and
            .E-backward. an operand of F that is .perp.)
            Reset.sub.-- can.sub.-- be.sub.-- avail(F)
    end Computer.sub.-- can.sub.-- be.sub.-- avail
    procedure Reset.sub.-- can.sub.-- be.sub.-- avail(G)
    can.sub.-- be.sub.-- avail(G) .rarw. false
    for each expr-.PHI. F with operand opnd defined by G do
    if (not has.sub.-- real.sub.-- use(opnd)) {
            set that .PHI. operand to .perp.
            if (not down.sub.-- safe (F) and can.sub.-- be.sub.-- avail (F))
              Reset.sub.-- can.sub.-- be.sub.-- avail (F)
    end Reset.sub.-- can.sub.-- be.sub.-- avail
    procedure Compute.sub.-- later
    for each expr-.PHI. F in program do
    later (F) .rarw. can.sub.-- be.sub.-- avail (F)
    for each expr-.PHI. F in program do
    if (later (F)) and
            .E-backward. an operand opnd of F such that
              (opnd .noteq. .perp. and has.sub.-- reach.sub.-- use (opnd)))
            Reset.sub.-- later (F)
    end Computer.sub.-- later
    procedure Reset.sub.-- later (G)
    later (G) .rarw. false
    for each expr-.PHI. F with operand opnd defined by G do
    if (later (F))
            Reset.sub.-- later (F)
    end Reset.sub.-- later
    procedure Will Be Avail
    Compute.sub.-- can.sub.-- be.sub.-- avail
    Compute.sub.-- later
    end Will Be Avail
    ______________________________________
     Copyright, Silicon Graphics, Inc., 1997

    ______________________________________
    procedure Finalize.sub.-- visit (block)
    for each occurrence X of E.sub.i in block do {
    save (X) .rarw. false
    reload (X) .rarw. false
    x .rarw. version (X)
    if (X is .PHI.) {
    if (will.sub.-- be.sub.-- avail (X))
            Avail.sub.-- def[i][x] .rarw. X
    else if (Avail.sub.-- def[i][x] is .perp. or
    Avail.sub.-- def[i][x] does not dominate X)
    Avail.sub.-- def[i][x] .rarw. X
    else if (Avail.sub.-- def[i][x] is real) {
    save (Avail.sub.-- def[i][x]) .rarw. true
    reload (X) .rarw. true
    }
    }
    for each S in Succ (block) do {
    j .rarw. WhichPred (S, block)
    for each expr-.PHI. F in S do
    if (will.sub.-- be.sub.-- avail (F)) {
            i .rarw. Which Expr (F)
            if (j.sup.th operand of F satisfies insert) {
              insert E.sub.i at the exit of block
              set (j.sup.th operand of F to inserted occurrence
            }
            else {
              x .rarw. version (j.sup.th operand of F)
              if (Avail.sub.-- def[i][x] is real) {
                save (Avail.sub.-- def[i][x]) .rarw. true
                set j.sup.th operand of F to Avail.sub.-- def[i][x]
              }
            }
    }
    }
    for each K in Children (DT, block) do
    Finalize.sub.-- visit (K)
    end Finalize.sub.-- visit
    procedure Finalize
    for each version x of E.sub.i in program do
    Avail.sub.-- def[i][x] .rarw. .perp.
    Finalize.sub.-- visit (Root (DT))
    end Finalize
    ______________________________________
     Copyright, Silicon Graphics, Inc., 1997

                  TABLE 1
    ______________________________________
    Assigning h-versions in Delayed Renaming
                   current  condition for
         def at top
                   occurrence
                            identical
    Rule of stack  X        h-version
    ______________________________________
    1    real      real     all corresponding variables have
    2    real      .PHI. operand
                            same versions
    3    .PHI.     real     defs of all variables in X dominate
    4    .PHI.     .PHI. operand
                            the .PHI.
    ______________________________________

• Inventors
  Chow, Frederick; Chan, Sun; Kennedy, Robert; Liu, Shin-Ming; Lo, Raymond; Tu, Peng;
• Assignee
  Silicon Graphics, Inc. (Mountain View, CA)
• Published
  Feb-15-2000
• Current US Classes:
  717/152
• Application #
  873895
• International Classes
  G06F 009/45
• Field of Search
  395/705 395/706 395/707 395/708 395/709
• Examiner
  Hafiz; Tariq R.
• Agent
  Sterne, Kessler, Goldstein & Fox P.L.L.C.
• US Patent References:
  5274818
  5293631
  5327561
  5448737
  5659754
  5768596
  5842017