Claims Analysis
Total Claims: 9
Claim 1
Independent Claim
71 words
A method for performing global common subexpression elimination and code motion within the code optimization phase of an optimizing compiter, said method operating on an intermediate language representation of a progrm in which basic program blocks have been identified, characterized by separately identifying basis items in each basic block for subsequent processing wherein a basis item is defined as an operand which is referenced in a basic block before being computed.
Claim 2
Independent Claim
71 words
A method for performing global common subexpression elimination and code motion within the code optimization phase of an optimizing compiter, said method operating on an intermediate language representation of a progrm in which basic program blocks have been identified, characterized by separately identifying basis items in each basic block for subsequent processing wherein a basis item is defined as an operand which is referenced in a basic block before being computed.
Claim 3
Dependent Claim
41 words
A method as set forth in claim 1, further including creating a list of kill sets for the basis items, a kill set for one basis item comprising each non basis item which depends on said one basis for its value.
Claim 4
Dependent Claim
100 words
A method as set forth in claim 2 including computing the sets UEX, DEX and THRU using said bases item and kill set data, wherein UEX is defined as a set of upward exposed computations, the set of computations which if executed at the beginning of a basic block give the same result as when executed in the original place in the block, wherein DEX is defined as a similar set of downward expressions and wherein THRU is defined as a set of computations which if computed at the beginning or end of the basic block give the same result.
Claim 5
Dependent Claim
107 words
A method as set forth in claim 3 wherein UEX, DEX and THRU are computed: initializing DEX and UEX to the empty set, initializing THRU to the set of all computations of interest, removing the kill set of recomputed basis item from DEX, and THRU as basis items are computed, examining the instructions in the basic block in execution order, adding to DEX every non basis computation encountered, adding to UEX every non basis computation encountered, providing it is also in THRU, removing from DEX and removing from THRU any members, which are also members of the basis item's kill set whenever a basis item is computed.
Claim 6
Dependent Claim
59 words
A method as set forth in claim 3 wherein UEX, is computed by: initializing UEX to the empty set, examining the instructions ir the basic block in reverse execution order, adding to UEX every non basis computation encountered, removing from UEX any members, which are also members of the basis item's kill set whenever a basis item is computed.
Claim 7
Independent Claim
113 words
A method as set forth in any proceeding claim, comprising determining the basis item on which each computation depends, determining the kill set for each basis item, determining UEX, DEX, and THRU for each basis block using the previously determined basis and kill set information, computing AVAIL and INSERT from UEX, DEX, and THRU, wherein AVAIL is defined as the set of computations, whose results are valid when the basic block is entered and INSERT is defined as the set of computations which will be inserted at the end of the basic block, making appropriate code insertions at those locations indicated by AVAIL and INSERT, and removing redundant code using the AVAIL set.
Claim 8
Independent Claim
163 words
A method as set forth in any proceeding claim for allowing larger sets to be recognized for UEX, DEX and/or THRU, said method comprising: determining for each non basis item the subset of basis items on which it depends and replacing each non basis item by the basis items on which that operand depends, using the sets formed above locating and identifying the collection of non basis item, called the kill set of the basis item, forming the sets DEX, UEX, and THRU for each basic block comprising: initializing DEX and UEX to the empty set, initializing THRU to the set of all computations of interest, examining the instructions in the basic block in execution order, adding to DEX every non basis computation encountered, adding to UEX every non basis computation encountered, providing it is also in THRU, removing from DEX and removing from THRU any members, which are also members of the basis item's kill set whenever a basis item is computed.
Claim 9
Dependent Claim
98 words
A method as set forth in claim 7 including deriving the set of available computations (AVAIL) from UEX, DEX and THRU, examining each instruction of a basic block in execution order, discarding a computation as redundant if it is in AVAIL, if a computation of a non basis item is not in AVAIL addinq the non basis item to the set of available computations, AVAIL if the instruction computes a non basis items for the computation of a basis item, removing from AVAIL the members of the basis item's kill set which are currently also members of AVAIL.