Method of, system for, and computer program product for providing extended global value numbering

Abstract

A fast and efficient way of performing extended global value numbering beyond basic blocks and extended basic blocks on a complete topological ordering of basic blocks in a program. Global value numbering is further extended with a Value Number List, an ordered list of value numbers of an expression, and iterative processing of a worklist containing expressions which are recursively defined. A hash table is used to reduce storage and processing time.

Claims

I claim:

1. A method of performing redundancy optimization of a computer program, said method comprising the steps of:

determining a complete topological order of a plurality of basic blocks comprising expressions from a flow graph of the computer program; and

processing the plurality of basic blocks in the topological order, wherein the processing comprises:

assigning a value number to each expression of a first subset of the expressions, wherein the value number is a symbolic execution of a basic block of the computer program, in which each variable entering the basic block is given a distinct symbolic value comprising the value number;

assigning a value of unknown to at least one value number corresponding to each expression of a second subset of the expressions, the second subset comprising .phi.-functions having an operand whose value number is assigned a value of unknown, and op-codes having an operand whose value number is assigned a value of unknown; and

assigning a value number list to each expression of a third subset of the expressions, wherein the value number list comprises an ordered list of value numbers assigned to the expression, and wherein the value number list does not contain a value number assigned a value of unknown.

2. The method of claim 1 wherein the processing step further comprises the steps of:

placing each of the second subset on a worklist;

removing from the worklist an expression of the second subset if the expression does not have at least one corresponding value number assigned a value of unknown after assigning a value number to the expression of the second subset; and

repeating the processing for the second subset until the worklist is empty or until a number of expressions on the worklist is equal to a number of expressions on the worklist during a prior processing of the worklist.

3. The method of claim 2 wherein the repeating step further comprises the steps of:

reassigning different value numbers to operands of expressions on the worklist having assigned value numbers, if the number of expressions on the worklist is equal to the number of expressions on the worklist during a prior processing of the worklist; and

repeating the processing for the second subset until the worklist is empty or until a number of expressions on the worklist is equal to a number of expressions on the worklist during a prior processing of the worklist.

4. The method of claim 1:

wherein the assigning for the first subset further comprises the steps of:

if all value numbers of all operands of a .phi.-function are equal, then assigning a value number of the .phi.-function to the equal value numbers; and

if all value numbers of all operands of a .phi.-function are not equal and the operands are recursively defined, then assigning a new unique value number to the value number of the .phi.-function;

wherein the assigning for the second subset further comprises the step of:

if any value number of any operand of a .phi.-function is unknown, then assigning an unknown value number to the value number of the .phi.-function;

and wherein the assigning for the third subset further comprises the step of:

if all value numbers of all operands of a .phi.-function are not equal and the operands are not recursively defined, then assigning a value number list to the .phi.-function comprising all value numbers of all operands of a .phi.-function.

5. The method of claim 1 further comprising the steps of:

identifying a redundancy if two expressions of the third subset have identical value number lists; and

identifying a partial redundancy if two expressions of the third subset have a common value number in the value number lists of the two expressions.

6. A computer system for performing redundancy optimization of a computer program, said computer system comprising:

means for determining a complete topological order of a plurality of basic blocks comprising expressions from a flow graph of the computer program; and

means for processing the plurality of basic blocks in the topological order, wherein the processing means comprises:

means for assigning a value number to each expression of a first subset of the expressions, wherein the value number is a symbolic execution of a basic block of the computer program, in which each variable entering the basic block is given a distinct symbolic value comprising the value number;

means for assigning a value of unknown to at least one value number corresponding to each expression of a second subset of the expressions, the second subset comprising .phi.-functions having an operand whose value number is assigned a value of unknown, and op-codes having an operand whose value number is assigned a value of unknown; and

means for assigning a value number list to each expression of a third subset of the expressions, wherein the value number list comprises an ordered list of value numbers assigned to the expression, and wherein the value number list does not contain a value number assigned a value of unknown.

7. The computer system of claim 6 wherein the processing means further comprises:

means for placing each of the second subset on a worklist;

means for removing from the worklist an expression of the second subset if the expression does not have at least one corresponding value number assigned a value of unknown after assigning a value number to the expression of the second subset; and

means for repeating the processing for the second subset until the worklist is empty or until a number of expressions on the worklist is equal to a number of expressions on the worklist during a prior processing of the worklist.

8. The computer system of claim 7 wherein the repeating means further comprises:

means for reassigning different value numbers to operands of expressions on the worklist having assigned value numbers, if the number of expressions on the worklist is equal to the number of expressions on the worklist during a prior processing of the worklist; and

means for repeating the processing for the second subset until the worklist is empty or until a number of expressions on the worklist is equal to a number of expressions on the worklist during a prior processing of the worklist.

9. The computer system of claim 6:

wherein the assigning means for the first subset further comprises:

means for assigning a value number of the .phi.-function to the equal value numbers if all value numbers of all operands of a .phi.-function are equal; and

means for assigning a new unique value number to the value number of the .phi.-function if all value numbers of all operands of a .phi.-function are not equal and the operands are recursively defined;

wherein the assigning means for the second subset further comprises:

means for assigning an unknown value number to the value number of the .phi.-function if any value number of any operand of a .phi.-function is unknown;

and wherein the assigning means for the third subset further comprises:

means for assigning a value number list to the .phi.-function comprising all value numbers of all operands of a .phi.-function if all value numbers of all operands of a .phi.-function are not equal and the operands are not recursively defined.

10. The computer system of claim 6 further comprising:

means for identifying a redundancy if two expressions of the third subset have identical value number lists; and

means for identifying a partial redundancy if two expressions of the third subset have a common value number in the value number lists of the two expressions.

11. An article of manufacture for use in a computer system for performing redundancy optimization of a computer program, said article of manufacture comprising a computer-readable storage medium having a computer program embodied in said medium which may cause the computer system to:

determine a complete topological order of a plurality of basic blocks comprising expressions from a flow graph of the computer program; and

process the plurality of basic blocks in the topological order, wherein the processing may further cause the computer system to:

assign a value number to each expression of a first subset of the expressions, wherein the value number is a symbolic execution of a basic block of the computer program, in which each variable entering the basic block is given a distinct symbolic value comprising the value number;

assign a value of unknown to at least one value number corresponding to each expression of a second subset of the expressions, the second subset comprising .phi.-functions having an operand whose value number is assigned a value of unknown, and op-codes having an operand whose value number is assigned a value of unknown; and

assign a value number list to each expression of a third subset of the expressions, wherein the value number list comprises an ordered list of value numbers assigned to the expression, and wherein the value number list does not contain a value number assigned a value of unknown.

12. The article of manufacture of claim 11 wherein the processing may further cause the computer system to:

place each of the second subset on a worklist;

remove from the worklist an expression of the second subset if the expression does not have at least one corresponding value number assigned a value of unknown after assigning a value number to the expression of the second subset; and

repeat the processing for the second subset until the worklist is empty or until a number of expressions on the worklist is equal to a number of expressions on the worklist during a prior processing of the worklist.

13. The article of manufacture of claim 12 wherein the repeating may further cause the computer system to:

reassign different value numbers to operands of expressions on the worklist having assigned value numbers, if the number of expressions on the worklist is equal to the number of expressions on the worklist during a prior processing of the worklist; and

repeat the processing for the second subset until the worklist is empty or until a number of expressions on the worklist is equal to a number of expressions on the worklist during a prior processing of the worklist.

14. The article of manufacture of claim 11:

wherein the assigning for the first subset may further cause the computer system to:

if all value numbers of all operands of a .phi.-function are equal, then assign a value number of the .phi.-function to the equal value numbers; and

if all value numbers of all operands of a .phi.-function are not equal and the operands are recursively defined, then assign a new unique value number to the value number of the .phi.-function;

wherein the assigning for the second subset may further cause the computer system to:

if any value number of any operand of a .phi.-function is unknown, then assign an unknown value number to the value number of the .phi.-function;

and wherein the assigning for the third subset may further cause the computer system to:

if all value numbers of all operands of a .phi.-function are not equal and the operands are not recursively defined, then assign a value number list to the .phi.-function comprising all value numbers of all operands of a .phi.-function.

15. The article of manufacture of claim 11 wherein the embodied computer program may further cause the computer system to:

identify a redundancy if two expressions of the third subset have identical value number lists; and

identify a partial redundancy if two expressions of the third subset have a common value number in the value number lists of the two expressions.

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 document or the patent disclosure, as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.

BACKGROUND OF THE INVENTION

1. Field of the Invention

This invention relates generally to optimizing compilers for development of computer programs for use on a computer, and more particularly to value numbering.

2. Description of the Related Art

A problem addressed by the optimizing compiler prior art is redundancy. Redundancy may take two forms. An expression is redundant, also known as full redundancy, if the expression has been evaluated before in a program on all paths leading to the expression. An expression is partially redundancy if the expression has been evaluated before in a program on some, but not all paths, leading to the expression. An objective of an optimizing compiler relative to redundancy is to remove the redundant expression so that it is not executed, thus saving memory which would otherwise store the redundant expression and saving execution time which would otherwise be used to execute the redundant expression. The objective relative to a partial redundancy is to move the expression so that it is no longer partially redundant.

Redundancy optimization may be understood by reference to the optimizing compiler art. FIG. 1 illustrates a procedure for translating a program to create an executable binary object program 12. A lexical/syntax analysis is conducted to transform source program to a first intermediate language program 16. First intermediate language program 16 is then processed by an optimization routine 18 to create a second intermediate language program 20, which is then directly interpreted by the code generation routine 22 to create object program 12.

Optimization routine 18 is illustrated in FIG. 2 as it is understood in the art. Optimization processing is achieved by first performing a control flow analysis in routine 27 of first intermediate language 16. Control flow analysis routine 24 provides the control flow data 26, which are then passed to a data-flow analysis routine 28 wherein first intermediate language program 16 is analyzed for data flow. Data-flow analysis routine 28 produces the data-flow data 30. Finally, a program transformation procedure 32 accepts control flow data 26, data-flow data 30, and first intermediate language program 16 to produce second intermediate language program 20. Optimization routine 18 may include prior techniques for redundancy optimization using the control flow data 26 and the data-flow data 30 to enable the program transformation procedure 32 to perform redundancy optimization.

Many methods for redundancy optimization are known in the art. For instance, in Morel et al. (E. Morel and C. Renvoise, "Global Optimization by Suppression of Partial Redundancies", Communications of the ACM, vol. 22, no. 2, February 1979, p. 96-103) redundancy suppression and moving is accomplished by iteratively solving simultaneous Boolean systems in which each basic block and each expression within a basic block are assigned Boolean properties. Intra-basic block or local Boolean assigned properties include transparency, local availability, and local anticipability. Corresponding inter-basic block or global Boolean properties are also assigned. Morel et al. suggests that the average number of iterations to solve such simultaneous Boolean systems is 4.75 iterations, and as low as three iterations for well-structured programs. However, the teachings of Morel et al. only suppress and move redundancies that are lexically the same.

In Rosen et al. (B. Rosen, M. Wegman, and K. Zadeck, "Global Value Numbers and Redundant Computations", Fifteenth ACM Principles of Programming Languages Symposium, Jan. 12-27, 1988, San Diego, Calif.), a program is translated into Static Single Assignment Form (SSA). See Cytron et al. (R. Cytron and J. Ferrante, "An Efficient Method for Computing Static Single Assignment Form", Sixteenth Annual ACM Symposium on Principles of Programming Languages Symposium, Jan. 25-35, 1989). All expressions are attempted to be moved upwards. Value numbering is then performed locally in basic blocks. Redundancy or partial redundancy is discovered after expressions are attempted to be moved. Although the technique of Rosen et al. may identify redundancies based on the same value number in addition to those that are lexically the same, it does so by attempting to move and scanning all expressions.

Alpern et al. (B. Alpern, N. Wegman, and F. Zadeck, "Detecting Equality of Values in Programs", Conf. Rec. Fifteenth ACM Symposium on Principles of Programming Languages Symposium, Jan. 1-11, 1988) teach representing the symbolic execution of a program as a finite state machine and applying a partitioning technique to minimize the finite state machine in order to detect an equivalence of variables in the program. Although this technique is computational intensive, Alpern et al. suggest that the problem of detecting the equivalence of variables in the program is undecidable.

Thus, practitioners in the art generally employ computationally intensive techniques for code motion and code redundancy removal, and there is an accordingly clearly-felt need in the art for more efficient compiling procedures providing code motion and code redundancy removal at a reasonable compile-time cost.

SUMMARY OF THE INVENTION

The invention disclosed herein comprises a method of, system for, and computer program product for providing a fast and efficient way of performing extended global value numbering beyond basic blocks and extended basic blocks on a complete topological ordering of basic blocks in a program. Global value numbering is further extended with a Value Number List, an ordered list of value numbers of an expression, and iterative processing of a worklist containing expressions which are recursively defined. A hash table is used to reduce storage and processing time.

In one aspect of the present invention, a fast and efficient technique for performing global value numbering based on Static Single Assignment Form (SSA) is provided.

In yet another aspect of the present invention, a new technique for performing code motion and redundancy removal is provided.

The present invention has the advantage of providing improved compilation optimization.

The present invention has the further advantage of improved optimization of redundancy.

The present invention has the further advantage of improved optimization of partial redundancy.

The present invention has the further advantage of improved optimization of loop invariants.

The present invention has the further advantage of improved optimization with reduced compilation time.

The present invention has the further advantage of improved optimization with reduced storage.

BRIEF DESCRIPTION OF THE DRAWINGS

For a more complete understanding of the present invention and the advantages thereof, reference is now made to the Detailed Description in conjunction with the attached Drawings, in which:

FIG. 1 shows a functional block diagram of an exemplary compiling method from the prior art;

FIG. 2 shows a functional block diagram of an exemplary compiling optimization method from the prior art;

FIG. 3 a flowchart illustrating the operations preferred in carrying out Code Motion and Redundancy Removal in accordance with the present invention;

FIG. 4 and FIG. 5 are flowcharts illustrating the operations preferred in carrying out Extended Global Value Numbering in accordance with the present invention;

FIG. 6 is a functional block diagram of a Hash Table and associated tables in accordance with the present invention;

FIG. 7 is a flowchart illustrating the operations preferred in carrying out Determining Redundancy in accordance with the present invention;

FIG. 8 is a flowchart illustrating the operations preferred in carrying out Moving Invariants in accordance with the present invention;

FIG. 9 is a flowchart illustrating the operations preferred in carrying out Moving Partial Redundancies in accordance with the present invention; and

FIG. 10 is a block diagram of a computer system used in performing the method of the present invention, forming part of the apparatus of the present invention, and which may use the article of manufacture comprising a computer-readable storage medium having a computer program embodied in said medium which may cause the computer system to practice the present invention.

DESCRIPTION OF THE PREFERRED EMBODIMENT

Referring now to FIG. 3 through FIG. 9, flowcharts illustrating operations preferred in carrying out the present invention are shown. In the flowcharts, the graphical conventions of a diamond for a test or decision and a rectangle for a process or function are used. These conventions are well understood by those skilled in the art, and the flowcharts are sufficient to enable one of ordinary skill to write code in any suitable computer programming language.

Code Motion and Redundancy Removal

Code motion and redundancy removal by the present invention may be performed by the following steps:

Identify invariants per loop level. This may be performed as a part of induction variable analysis using techniques well known by those skilled in the art, such as the technique of finding invariants by using Static Single Assignment (SSA) definition links and propagating invariant properties of each variable in a loop nest.

Perform extended value numbering to identify expressions that are candidates for redundancy removal. This is discussed in greater detail below in the Section entitled "Extended Global Value Numbering".

Mark expressions as redundant or partially redundant. This is discussed in greater detail below in the Section entitled "Determining Redundancy".

Process each basic block in topological order Walk all expressions within the basic block,

a. if an expression is redundant, delete it and do text substitution.

b. If it is marked as invariant, then in general, for t=b+c, it may be moved to the loop preheader if a "safe" optimization option is used and the block dominates the loop-exit or it exists on all paths. This safe condition is relaxed for "unsafe" optimization. This is discussed in greater detail below in the Section entitled "Moving Invariants". The renaming in SSA form makes code motion easier. If the expression is moved to the loop preheader, it is checked to determine if the same expression exists within the loop. If it does, then it is deleted.

c. If an expression is marked as partially redundant, then it is checked to determine if it may be moved. Some searches are needed to find this out. If it can be moved, the expression is moved upwards and links are updated. This is discussed in greater detail below in the Section entitled "Moving Partial Redundancies".

d. Perform subsumption.

e. Perform store motion. Although both subsumption and store motion may be performed by techniques well known to those skilled in the art, these steps are included here to fully disclose the type and order of various optimizations of the inventor's complete preferred embodiment of the present invention.

Referring now to FIG. 3, the operations preferred in carrying out Code Motion and Redundancy Removal 300 in accordance with the present invention are illustrated. The process begins at process block 305. Thereafter, process block 310 identifies invariants per loop level. Thereafter, process block 315 performs value numbering to identify expressions that are candidate for redundancy removal. Thereafter, process block 320 marks expressions as redundant or partially redundant. Thereafter, process block 325 begins a loop for each basic block in topological order. Thereafter, process block 330 begins a loop for each expression within the basic block. Thereafter, decision block 335 determines if the expression is redundant. If the expression is redundant, then process block 340 deletes the expression and performs text substitution. Thereafter, process block 345 performs subsumption. Thereafter, process block 350 performs store motion. Thereafter, decision block 355 determines if there are remaining expressions in the basic block. If there are remaining expressions in the basic block, then processing loops back to process block 330, the start of the loop for each expression within the basic block, to process the next expression within the basic block.

Returning now to decision block 335, if the expression is not redundant, then decision block 360 determines if the expression is marked as invariant. If the expression is marked as invariant, then process block 365 processes the invariant expression. Thereafter, processing continues to process block 345 for the performance of subsumption.

Returning now to decision block 360, if the expression is not marked as invariant, then decision block 370 determines if the expression is marked as partially redundant. If the expression is marked as partially redundant, then process block 375 processes the partially redundant expression. Thereafter, processing continues to process block 345 for the performance of subsumption.

Returning now to decision block 370, if the expression is not marked as partially redundant, then processing continues to process block 345 for the performance of subsumption.

Returning now to decision block 355, if there are no remaining expressions in the basic block, then decision block 380 determines if there is a remaining basic block to be processed by the loop. If there is a remaining basic block, then processing loops back to process block 325, the start of the loop for each basic block, to process the next basic block.

Returning now to decision block 380, if there is no remaining basic block to be processed by the loop, then the process ends at process block 385.

Extended Global Value Numbering

In order to perform the optimization that removes redundant expressions, the concept of value numbers and the method for value numbering are extended. A value number in the prior art is a symbolic execution of a basic block of code, in which all variables entering that basic block of code (straight line code) are given distinct symbolic values or value numbers. The technique of value numbering is used for common subexpression elimination within a basic block, where if a symbolic value is computed twice within the same basic block, then it may be eliminated the second time. However, use of the prior art value number techniques are limited to a single basic block or an extended basic block (two adjacent basic blocks). The prior art techniques do not provide optimizations such as common subexpression elimination or redundancy removal beyond basic blocks and extended basic blocks to an entire program consisting of multiple extended basic blocks.

The Extended Global Value Numbering of the present invention is performed by walking the basic blocks of the program in topological order and assigning value numbers to expressions. With the back edges ignored in the flow-graph, the postorder (left-right-root) traversal gives reverse topological order.

A hash table, illustrated in FIG. 6 and described below in the section entitled "Hash Table", is used for fast access in Extended Global Value Numbering. This hash table reduces the search time and space needed later for redundancy removal. This hash table also enables the searches to be done with "context" and in a predictive manner, as opposed to conventional methods in which all expressions were attempted to be moved upwards.

In order to properly handle redundancies, .phi.-functions need special handling. A .phi.-function (phi-function) is a pseudo-assignment resulting from a translation to Static Single Assignment (SSA) form. This translation to SSA form separates each variable, x, in a program into several variables x.sub.i (i.e., x0, x1, x2, . . . ) where each x.sub.i has only one assignment, hence the name Static Single Assignment. These pseudo-assignments are of the form x=.phi.(y,z) meaning that if the control flow of the program reaches the .phi.-function by a first control path, then x is assigned the value y, and if by a second control path, then x is assigned the value z. The target of a .phi.-function assumes the value numbers of its operands. In particular, the following Table A shows an Example (a) in which the target, x2, of the .phi.-function, .phi.(x0,x1), assumes both values, 9 or 11, of its operands, x0 and x1. Later hashing for x2+y0 obtains two different values for x0+y0 and x1+y0, respectively.

                  TABLE A
    ______________________________________
    Value Numbering
    An expression may receive more than one value number.
    ______________________________________
    Example a:
    = x0 + y0;     VN for x0+y0= 10,VN for x0 = 9
    if( )then
    = x0 + y0;     VN for x0+y0 = 10
    else do;
    x =            VN for x1 = 11
    = x1 + y0;     VN for x1+y0: 12
    end;
    x2 = .phi.(x0,x1);
                   VN for x2 = 9 or 11
    = x2 + y0;     VN for x2+y0 = 10 or 12
    x2+y0 is redundant here since it receives both VN 10 & 12.
    Example b:
    if( )then      VN for x0 = 9
    = x0 + y0;     VN for x0+y0: 10
    else do;
    = x0 + y0;     VN for x0+y0: 10
    x1 =           VN for x1: 11
    end;
    x2 = .phi.(x0,x1);
                   VN for x2 = 9,11
    = x2 + y0;     VN for x2+y0: 10,12
    x2+y0 is partially redundant since it receives just VN 10
    Example c:
    if( )then      VN for p0,q0 =9,10
    p0 =; q0 =;    VN for p0+q0: 11
    = p0 + q0;
    else do;
    pl =; q1 =;    VN for p1,q1 =12,13
           = pl + q1;
                   VN for p1+q1: 14
    end;
    p2 = .phi.(p0,p1);
                   VN for p2 = 9,12
    q2 = .phi.(q0,q1);
                   VN for q2 =10,13
    = p2 + q2;     VN for p2+q2=p0+q0 (left path) 11
                      p1+q1 (right path) 14
    p2+q2 is redundant since it receives both VN 11,14
    ______________________________________

                  TABLE B
    ______________________________________
                   Value Number
                             Value Number
                   Initial Pass
                             Subsequent Pass
    ______________________________________
    do i = 1,10
    x1 = .phi.(x0,x2)
                     10,undefined
                                 10,11
    = x1 + y0        9,12        9,12
    x2 =             11          11
    = x2 + y0        12          12
    end
    ______________________________________

    ______________________________________
    any .andgate..sub. ==>.sub.
    If any operand of the .phi.-function has an unknown
    value number, then set the value number of the
    .phi.-function to unknown.
    VN.sub.i .andgate. VN.sub.j ==> VN.sub.k
    If VN.sub.i not equal to VN.sub.j, then a new value number
    is formed when the operands are involved in a recursive
    definition, else VNList for VN.sub.i and VN.sub.j is formed.
    VN.sub.i .andgate. VN.sub.j ==> VN.sub.i if i = j
    If all value numbers of .phi.-function operands are equal, then set
    .phi.-function value number to operand value number.
    for other op-codes:
    any .andgate..sub. ==>.sub.
    If any operand of has unknown value number, then set the value
    number to unknown.
    VN.sub.i .andgate. VN.sub.j ==> VN.sub.k
    ______________________________________

                  TABLE C
    ______________________________________
    Redundancy discovered after code is moved
    ______________________________________
    do while ()
    if( ) then
    do;
           if () then z1=x + y;
    end;
    else z2 = x + y;
    z3 = x + y;
    end;
    ______________________________________

                  TABLE D
    ______________________________________
    Construct .phi.-functions for expressions
    ______________________________________
    if () then a = x + y + z;
    d = x + y;
    Construct .phi.-functions. For expressions that have the same value
    numbers,
    treat it as a "Use followed by a Set". The "use" does not
    form a new text. It exists just as a special operand
    in RHS.
    ==>
    if() then do;
    = t;
    t = x + y
    end;
    = t;
    t = x + y
    d = t3;
    ______________________________________

                  TABLE E
    ______________________________________
    Rename operands of .phi.-functions
    ______________________________________
    After .phi.-functions are built, do renaming.
    ==>
    if () then do;
    = t0
    t1 = x + y
    = t1 + z
    end;
    s1: t2 = .phi.(t0,t1)
    = t2
    s2: t3 = x + y
    d = t3
    ______________________________________

                  TABLE F
    ______________________________________
    Removing Redundancy During Renaming
    ______________________________________
    = x + y + z
               ==>     t1 = x + y ==>   tl = x + y
    = x + y            = t1             = tl
    = x + y            = t1
    ______________________________________

                  TABLE G
    ______________________________________
    Temporary only defined in certain paths in a loop
    ______________________________________
    t0 = x0 + y0
                ==>     t0 = x0 + y0
    do i = 1,10        do i = 1,10
    t2 = .phi.(t3,t0)
    if() then t1 = x0 + y0
                         if() = . . t0
    . . .
    t3 = .phi.(t2,t1)
    end                end
                       VN for t in this path consists of
                       one element
    ______________________________________

                                      TABLE H
    __________________________________________________________________________
    Determination of redundancy
    __________________________________________________________________________
    Case (a):
    t1 = x0 + y0 vn = 10
    . . .
     = t1 "fake use"
    t2 = x0 + y0 vn = 10 .fwdarw. redundant
    Case (b):
     ##STR1##            VN = 12, 13                 VN = 9, 10  VNList =
                      (12, 13)  "fake use" 12, 13  VNList = (12, 13) .fwdarw.
                      redundant
    Case (c):
     ##STR2##            VN = 20, 21                 VN = 20, 21  "fake use"
                    20, 21  Vn = x0 + y0, x1 + y1 = 20, 21 .fwdarw. redundant
                     Notice that Vn for w4 is constructed of just two
                    combinations  instead of four; the values can either come
                    in from the left or  from the right, so x0 + y1 is an
                    invalid combination.
    Case (d):
     ##STR3##
    __________________________________________________________________________


              TABLE I
    ______________________________________
    Determination of partial redundancy
    ______________________________________
     ##STR4##        VN = 12, 13  VN = 15                 VN = 9, 15  VN =
                     12, 13  "fake use" 12, 13  VNL for x0 + y0, x3 + y0; 12,
                     16  only 12 matches .fwdarw. partial  redundancy
    The following case shows no redundancy:
     ##STR5##        VN = 12, 13  VN for x2, x3: 14, 15              VN = 14,
                     15  VN = 12, 13  "fake use" 12, 13  VNL for x2 + y0, x3
                     + y0: 16, 17  nothing matches .fwdarw. no
    ______________________________________
                     redundancy

                  TABLE J
    ______________________________________
    Moving invariants
    Since t0 = t3 and assuming t4 resides in block that dominates the loop
    exit,
    then all x + y can be moved.
    ______________________________________
     ##STR6##
    ______________________________________

                  TABLE K
    ______________________________________
    Variant with upwardly exposed usage
    ______________________________________
    do while
      = t
    t =
    end
    ______________________________________

                  TABLE L
    ______________________________________
    Invariant without upwardly exposed usage
    SSA Form
    ______________________________________
    i = 1         il = 1
    do while ()
               do while ()
    if ( ) then     i2 <== .phi.(i4,i1)
    i = 2           if() then
                    i3 = 2
    end               i4 <== .phi.(i3, i2)
     = i          end
                  i5 <== .phi.(i4, i1)
                  = i5
    ______________________________________

                  TABLE M
    ______________________________________
    Redundancy discover after code is moved
    ______________________________________
    do while ()
    if ( ) then
       do;
            if () then z1 = x + y; -
       end; - else z2 = x + y;
    end;
    ______________________________________

                                      TABLE N
    __________________________________________________________________________
    Examples of partial redundancy
    __________________________________________________________________________
    Example (a):
    if ( ) then     .fwdarw. if ( ) then
            t1 = p .fwdarw. q .fwdarw. x;
                                t1 = p .fwdarw. q .fwdarw. x;
    else . . . ;        else t3 = p .fwdarw. q .fwdarw. x;
    t2 = .phi.(t0, t1)  t2 = .phi.(t3, t1)y
    t3 = p .fwdarw. q .fwdarw. x;
                              = t2;
    Example (b):
     ##STR7##
    Example (c):
    if ( ) t = x + y;
    if ( ) z = x + y;
    else w = x + y;
    This partial redundancy cannot be removed
    Example (d):
    if ( ) then
        = p .fwdarw. q .fwdarw. x;
    if ( ) then
        = p .fwdarw. q .fwdarw. x;
    __________________________________________________________________________

                  TABLE P
    ______________________________________
    An example identifying and removing a redundant expression
    ______________________________________
    a. Input in SSA form: ==>
                   b. Assign value number ==>
                                    Value
                                    Number
      = x0 + y0      = x0 + y0      9
     do i = 1, 10   do i = 1, 10
      x1 = .phi.(x0, x2)
                     x1 = .phi.(x0, x2)
                                    10, 11
      = x1 + y0      = x1 + y0      9, 12
      x2 =            x2 =          11
      x2 + y0      = x2 + y0        12
     end             end
    c. Insert .phi.-functions for ==>
                   d. Rename variables  ==>
     expressions in same value
     number set {9, 12}
      = t           = t0
     t = x0 + y0     t1 = x0 + y0
     do i = 1, 10    do i = 1, 10
      t = .phi.(t, t)
                     t2 = .phi.(t1, t4)
      x1 = .phi.(x0, x2)
                     x1 = .phi.(x0, x2)
      = t            = t2
      t = x1 + y0     t3 = x1 + y0
      x2 =            x2 =
      = t            = t3
      t = x2 + y0     t4 = x2 + y0
     end             end
    e. Determines full and  =>
                   f. Clean up links
    partial redundancy              ! removed
      = t0
    t2 = x0 + y0   t1 = x0 + y0
    do i = 1, 10     do i = 1, 10
      t2 = .phi.(t1, t4)
                     t2 = .phi.(t1, t4)
      x1 = .phi.(x0, x2)
                     x1 = .phi.(x0, x2)
      = t2
      t3 = x1 + y0 ! Redundant
                   = t2
      x2 =            x2 =
      = t3
      t4 = x2 + y0   t4 = x2 + y0
     end             end
    ______________________________________


              TABLE Q
    ______________________________________
    An example identifying and moving a partially redundant
    ______________________________________
    expression
    a. Input in SSA form:  ==>
                    b. Assign value number ==>
                                     Value
                                     Number
      do i = 1, 10    do i = 1, 10
       x1 = .phi.(x0, x2)
                       x1 = .phi.(x0, x2)
                                     10, 11
       = x1 + y0       = x1 + y0     9, 12
       x2 =             x2 =         11
       = x2 + y0       = x2 + y0     12
      end              end
    c. Insert .phi.-fcns for   ==>
                    d. Rename variables
                                      ==>
    expressions in same value
    number set {9, 12}
      do i = 1, 10     do i = 1, 10
       t = .phi.(t, t)
                       t2 = .phi.(t1, t4)
       x1 = .phi.(x0, x2)
                       x1 = .phi.(x0, x2)
       = t             = t2
       t = x1 + y0      t3 = x1 + y0
       x2 =             x2 =
       = t             = t3
       t = x2 + y0      t4 = x2 + y0
      end              end
    e. Determines full and  ==>
                    f. Clean up links
    partial redundancy
                       t5 = x1 + y0
      do i = 1, 10     do i = 1, 10
       t2 = .phi.(t1, t4)
                       t2 = .phi.(t5, t4)
       x1 = .phi.(x0, x2)
                       x1 = .phi.(x0, x2)
       = t2
       t3 = x1 + y0 ! Partial
                      = t2
       Redundancy
       x2 =             x2 =
       = t3
       t4 = x2 + y0    t4 = x2 + y0
      end              end
    ______________________________________


              TABLE R
    ______________________________________
    An example identifying and moving a partially redundant
    ______________________________________
    expression
    a. Input in SSA form:
                   .fwdarw.
                         b. Assign value number
                                         .fwdarw.
                                     Value
                                     Number
     ##STR8##
                    ##STR9##            10, 10  11        9, 11  10, 12
    c. Insert .phi.-fcns for
                   .fwdarw.
                         d. Rename variables
                                         .fwdarw.
     expressions in same value
     number set {10, 12}
     ##STR10##
                    ##STR11##
    e. Determines full and
                   .fwdarw.
                         f. Move code up.
     partial redundancy
     ##STR12##
                    ##STR13##
    x2 + y0 is not redundant since
    only value number 10 reaches it.
    x2 + y0 has value numbers 10 and 12
    and therefore it is partially redundant.
    ______________________________________


              TABLE S
    ______________________________________
    An example identifying and moving a partially redundant expression up
    one basic block, after which the expression is still partially redundant
    at
    the moved location, and after which the expression is moved up one
    additional basic block
    ______________________________________
    a. Input in SSA form:
                   .fwdarw.
                         b. Assign value number
                                        .fwdarw.
                                    Value
                                    Number
     ##STR14##
                     ##STR15##            10        10           10
    c. Insert .phi.-fcns for
                   .fwdarw.
                         d. Rename variables
                                        .fwdarw.
     expressions in same value
     number set {10}
     ##STR16##
                     ##STR17##
    e. Determines full and
                .fwdarw.
                      f. Shuffles t5 = x0 + y0 up one block .fwdarw.
     partial redundancy
     ##STR18##
                     ##STR19##
    g. It is determined from the .phi.-function which dominates t6 that t6
    is
    still partially redundant; moves t6 one more block up.
     ##STR20##
    ______________________________________


              TABLE T
    ______________________________________
    An example in which the prior art fails to handle redundancies and
    partial
    redundancies, but in which the present invention identifies and moves a
    partial redundancy, and further identifies and removes a
    ______________________________________
    redundancy
    a. Input in SSA form: ==>
                   b. Assign value number ==>
                                    Value
                                    Number
      = a0 * b0    = a0 * b0        10
      = c0 * b0      = c0 * b0      11
     if ( ) a1 = c0
                    if ( ) a1 = c0  12
     a2 = .phi.(a0, a1)
                    a2 = .phi.(a0, a1)
                                    9, 12
      = a2 * b0      = a2 * b0      10, 11
    c. Insert .phi.-fcns for  ==>
                   d. Rename variables  ==>
    expressions in same value
    number set {10, 11}
     t = a0 * b0     t1 = a0 * b0   10
     t = c0 * b0    t2 = c0 * b0    11
     if ( ) a1 = c0
                    if ( ) a1 = c0  12
     a2 = .phi.(a0, a1)
                   a2 = .phi.(a0, a1)
                                    9, 12
      = t             = t2
     t = a2 * b0     t3 = a2 * b0   10, 11
    e. Determines full and ==>
                   f. Move code up  ==>
    partial redundancy
      t1 = a0 * b0   = a0 * b0
      t2 = c0 * b0  t2 = c0 * b0
      if ( ) a1 = c0
                    if ( ) a1 = c0
                    else t3 = a0 * b0 ! redundant
      a2 = .phi.(a0, a1)
                    a2 = .phi.(a0, a1)
       = t2           t4 = .phi.(t3, t2)
      t3 = a2 * b0 ! Partially
                   = t4
    redundant
    g. Checks redundancy for
    moved code
      q1 = a0 * b0
      t2 = c0 * b0
      if ( ) a1 = c0
      else t3 = q1
      a2 = .phi.(a0, a1)
      t4 = .phi.(t3, t2)
       = t4
    ______________________________________
     Notice that a different temp (q) is created in the last step.


              TABLE U
    ______________________________________
    The sample program of Rosen et al.
    ______________________________________
    a. Source program
    Invariants are identified, and uses that are upwardly
    exposed in a loop are treated as variants.
                           Invariants
    do forever
                           yes
      if ( ) { L = C * B   yes
       M = L + 4           no
       A = C }             no
      else { D = C         yes
       L = D * B           yes
       S = A * B           no
       T = S + 1 }         no
       X = A * B           no
      Y = X + 1            no
    enddo
    b. Input in SSA form
    do forever
      A2 = .phi.(A1, A4)
      D2 = .phi.(D1, D4)
      L2 = .phi.(L1, L5)
      M2 = .phi.(M1, M4)
      S2 = .phi.(S1, S4)
      T2 = .phi.(T1, T4)
      if ( ) { L3 = C1 * B1
       M3 = L3 + 4
       A3 = C1}
      else { D3 = C1
       L4 = D3 * B1
       S3 = A2 * B1
       T3 = S3 + 1 }
      A4 = .phi.(A3, A2)
      D4 = .phi.(D2, D3)
      L5 = .phi.(L3, L4)
      M4 = .phi.(M3, M2)
      S4 = .phi.(S2, S3)
      T4 = .phi.(T2, T3)
      X1 = A4 * B1
      Y1 = X1 + 1
    enddo
    ______________________________________

    ______________________________________
    do forever         Value Numbers
      A2 = .phi.(A1, A4)
                       14 = 1, 15
      D2 = .phi.(D1, D4)
                       19 = 4, 18
      L2 = .phi.(L1, L5)
                        (5, 10)
      M2 = .phi.(M1, M4)
                       13 = 6, 14
      S2 = .phi.(S1, S4)
                       21 = 7, 22
      T2 = .phi.(T1, T4)
                       23 = 8, 25
      if ( ) { L3 = C1 * B1
                       10 = 3*2      *1
       M3 = L3 + 4     11 = 10*94
       A3 = C1}        3 = 3
      else { D3 = C1   3 = 3
       L4 = D3 * B1    10 = 3*2      *1
       S3 = A2 * B1    20 = 14*2
       T3 = S3 + 1 }   24 = 20 + 91
      A4 = .phi.(A3, A2)
                       15 = 3, 14
      D4 = .phi.(D2, D3)
                       18 = 19, 3
      L5 = .phi.(L3, L4)
                       10 = 10, 10
      M4 = .phi.(M3, M2)
                       14 = 11, 13
      S4 = .phi.(S2, S3)
                       22 = 21, 20
      T4 = .phi.(T2, T3)
                       25 = 23, 24
      X1 = A4 * B1     16 = 15*2
      Y1 = X1 + 1      17 = +91
    enddo
    ______________________________________

• Inventors
  Ng, John Shek-Luen;
• Assignee
  International Business Machines Corporation (Armonk, NY)
• Published
  Mar-7-2000
• Current US Classes:
  717/146
  717/151
  717/156
  717/159
• Application #
  568216
• International Classes
  G06F 009/45
• Field of Search
  395/709 395/708
• Examiner
  Toplu; Lucien U.
• Agent
  Johnson; Prentiss W.
• US Patent References:
  4642764
  4802091
  5327561
  5448737