Method for improving global common subexpression elimination and code motion in an optimizing compiler

Claim 1

A method in an electronic computing system within the code optimization phase of an optimizing compiler resident therein for doing global common subexpression elimination and code motion procedures, said method operating on an intermediate language representation of a program in which the basic blocks have been identified, separately identifying in said system `basis` items in each basic block for subsequent processing in said system wherein each `basis` item comprises an operand which has not been previously defined within that block.

Claim 2

A method in an electronic computing system within the code optimization phase of an optimizing compiler resident therein for doing global common subexpression elimination and code motion procedures, said method operating on an intermediate language representation of a program in which the basic blocks have been identified, separately identifying in said system `basis` items in each basic block for subsequent processing in said system wherein each `basis` item comprises an operand which has not been previously defined within that block.

Claim 7

A method in an electronic computing system during the optimization phase of an optimizing compiler resident therein for performing global common subexpression elimination an code motion which comprises: determining in said system the `basis` for the intermediate language representation of the program being compiled, determining in said system the `basis` items on which each computation depends, determining in said system the "kill set" for each `basis` item, determining in said system UEX, DEX, and THRU for each basis block using the previously determined `basis` and "kill set" information, computing in said system AVAIL and INSERT from UEX, DEX, and THRU, making in said system appropriate code insertions at those locations indicated by said preceding step, and removing in said system redundant code using the AVAIL set.

Claim 8

A method in an electronic computing system during the optimization phase of an optimizing compiler resident therein for performing global common subexpression elimination an code motion which comprises: determining in said system the `basis` for the intermediate language representation of the program being compiled, determining in said system the `basis` items on which each computation depends, determining in said system the "kill set" for each `basis` item, determining in said system UEX, DEX, and THRU for each basis block using the previously determined `basis` and "kill set" information, computing in said system AVAIL and INSERT from UEX, DEX, and THRU, making in said system appropriate code insertions at those locations indicated by said preceding step, and removing in said system redundant code using the AVAIL set.

Claim 9

A method in an electronic computing system within an optimizing compiler resident therein during the global common subexpression elimination and code motion phase which provides a mechanism for allowing larger sets to be recognized for UEX, DEX and/or THRU, said method comprising: examining and identifying in said system in each basic block `basis` items which are used as operands without having been previously defined within that basic block, determining in said system for each non `basis` item the subset of `basis` items on which it depends, replacing in said system each non `basis` item by the `basis` items on which that operand depends, using in said system the sets formed above locating and identifying the collection of non `basis` items, called the "kill set" of the `basis` item, forming in said system the sets DEX, UEX, and THRU for each basic block comprising: initializing in said system DEX and UEX to the empty set, initializing in said system THRU to the set of all computations of interest, examining in said system the instructions in the basic block in execution order, adding in said system to DEX every non `basis` computation encountered, adding in said system to UEX every non `basis` computation encountered, providing it is also in THRU, removing from DEX and remove from THRU in said system any members, which are also members of the basis item's "kill set" whenever a `basis` item is computed.

Claim 10

A method in an electronic computing system within an optimizing compiler resident therein during the global common subexpression elimination and code motion phase which provides a mechanism for allowing larger sets to be recognized for UEX, DEX and/or THRU, said method comprising: examining and identifying in said system in each basic block `basis` items which are used as operands without having been previously defined within that basic block, determining in said system for each non `basis` item the subset of `basis` items on which it depends, replacing in said system each non `basis` item by the `basis` items on which that operand depends, using in said system the sets formed above locating and identifying the collection of non `basis` items, called the "kill set" of the `basis` item, forming in said system the sets DEX, UEX, and THRU for each basic block comprising: initializing in said system DEX and UEX to the empty set, initializing in said system THRU to the set of all computations of interest, examining in said system the instructions in the basic block in execution order, adding in said system to DEX every non `basis` computation encountered, adding in said system to UEX every non `basis` computation encountered, providing it is also in THRU, removing from DEX and remove from THRU in said system any members, which are also members of the basis item's "kill set" whenever a `basis` item is computed.