Reducing pipeline delays in compilers by code hoisting

• US 5,450,588 A
• Filed: 07/12/1993
• Issued: 09/12/1995
• Est. Priority Date: 02/14/1990
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Hoxey, Steven M.
• Primary Examiner(s): Kriess, Kevin A.
• Assistant Examiner(s): BUTLER, DENNIS
• Application Number:
  US08/090,984
• Time in Patent Office: 792 Days
• Field of Search: 395/650, 395/700, 364/280.5, 364/281.3, 364/280.4
• US Class Current: 717/156
• CPC Class Codes: G06F 8/445 Exploiting fine grain parallelism, i.e. parallelism at instruction level run-time instruction scheduling G06F9/3836
• CPC Class Codes: G06F 8/4451 Avoiding pipeline stalls

Abstract

This invention permits an optimizing compiler to minimize the effect of pipeline delays, which are typically introduced by branching code. This invention employs code hoisting to introduce computations from lower regions of the flowgraph, into regions where pipeline delays are known to occur.

Claims

1. A method in a data processing system for improving utilization of clock cycles for a sequence of computer instructions, comprising:

a. representing, by said data processing system, said computer instructions in a control flowgraph, said control flowgraph comprising at least one subgraph, said at least one subgraph comprising at least one parent texture, said at least one parent texture having at least one child node related thereto;

b. searching, by said data processing system, said control flowgraph to identify subgraphs which are textures of order at least two;

c. for any identified subgraph;

i. examining, by said data processing system, instructions in at least one child node of said identified subgraph;

ii. determining, by said data processing system, whether each instruction is hoistable; and

iii. if said instruction is hoistable, merging, by said data processing system, said instruction from said child node to its parent texture.

2. A method as claimed in claim 1, further comprising the step of determining, by said data processing system, whether all instructions in a child node have been moved into a parent texture, and if so, then collapsing said child node into said parent texture.

3. A method as claimed in claim 1, in which said texture comprises a parent texture having two child nodes, and one of said child nodes has an entering edge from the other of said child nodes.

7. A method as claimed in any of claims 1 to 6, wherein said step of determining, by said data processing system, whether an instruction is hoistable comprises the steps of selecting a lookup table for a specific machine on which said improvement is to be performed, said lookup table including a list of instructions hoistable on said machine, and determining whether said instruction is found in said lookup table.

4. A method in a data processing system for improving utilization of clock cycles for a sequence of computer instructions, comprising:

a. representing, by said data processing system, said computer instructions in a control flowgraph, said control flowgraph comprising at least one subgraph, said at least one subgraph comprising at least one parent texture, said at least one parent texture having at least one child node related thereto;

b. searching, by said data processing system, said flowgraph to identify subgraphs which are textures of order at least two;

c. for any identified subgraph;

i. examining, by said data processing system, instructions in at least one child node of said identified subgraph;

ii. dletermining, by said data processing system, whether each instruction is hoistable; and

iii. if said instruction is hoistable, merging, by said data processing system, said instruction from said child node to its parent texture;

d. continuing steps i) through iii) for each child node until either all candidate instructions from child nodes are exhausted or all delay inherent in said parent is eliminated.

5. A method as claimed in claim 4, further comprising the step of determining, by said data processing system, whether all instructions in a child node have been moved into a parent texture, and if so, then collapsing said child node into said parent texture.

6. A method as claimed in claim 4, in which said texture comprises a parent texture having two child nodes, and one of said child nodes has an entering edge from the other of said child nodes.