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

• US 4,656,583 A
• Filed: 08/13/1984
• Issued: 04/07/1987
• Est. Priority Date: 08/13/1984
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Auslander, Marc A., Cocke, John, Markstein, Peter W.
• Primary Examiner(s): NOT, DEFINED
• Application Number:
  US06/640,283
• Time in Patent Office: 967 Days
• Field of Search: 364/300
• US Class Current: 717/153
• CPC Class Codes: G06F 8/443 Optimisation

Abstract

A method for use during the optimizatin phase of an optimizing compiler for performing global common subexpression elimination and code motion which comprises:

Determining the code `basis` for the object program which includes examining each basic block of code and determining the `basis` items on which each computation depends wherein `basis` items are defined as operands which are referenced in a basic block before being computed. The method next determines the "kill set" for each `basis` item. Following this UEX, DEX, and THRU are determined for each basic block using the previously determined `basis` and "kill set" information. AVAIL and INSERT are computed from UEX, DEX, and THRU, and appropriate code insertions are made at those locations indicated by the preceding step, and finally redundant code is removed using the AVAIL set.

Claims

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.

2. A method operable within an optimizing compiler as set forth in claim 1, further including creating a list of Kill Sets for each `basis` items which specifies each non `basis` items which depends on the `basis` items for its value.

3. A method operable within an optimizing compiler as set forth in claim 2 including computing the sets UEX, DEX and THRU using the claimed `Basis` and Kill Set data.

4. A method operable within an optimizing compiler as set forth in claim 3 wherein UEX, DEX and THRU are computed by:

initializing DEX and UEX to the empty set, initializing THRU to the set of all computations of interest,

remaining the kill set of recomputed `basis` items 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.

5. A method operable within an optimizing compiler as set forth in claim 4 wherein UEX, is computed by:

initializing UEX to the empty set,

examining the instructions in 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.

6. 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.

7. 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.

8. A method operable within an optimizing compiler 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, adding 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.