Method and apparatus for efficient code generation for modulo scheduled uncounted loops

• US 20030233643A1
• Filed: 06/18/2002
• Published: 12/18/2003
• Est. Priority Date: 06/18/2002
• Status: Active Grant

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Morris, Dale, Srinivasan, Uma, Thompson, Carol L., Hank, Richard E.
• Granted Patent: US 6,986,131 B2
• Time in Patent Office: Days
• US Class Current: 717/161
• CPC Class Codes: G06F 8/4452 Software pipelining
• CPC Class Codes: G06F 9/30072 to perform conditional operations, e.g. using predicates or guards
• CPC Class Codes: G06F 9/325 for loops, e.g. loop detection or loop counter
• CPC Class Codes: G06F 9/3842 Speculative instruction execution

Abstract

A method of efficient code generation for modulo scheduled uncounted loops includes: assigning a given stage predicate to each instruction in each stage, including assigning a given stage predicate to each instruction in each speculative stage; and using the stage predicate to conditionally enable or disable the execution of an instruction during the prologue and epilogue execution.

Claims

1. A method of efficient code generation for modulo scheduled uncounted loops, the method comprising:

assigning a given stage predicate to each instruction in each stage, including assigning a given stage predicate to each instruction in each speculative stage; and

using the stage predicate to conditionally enable or disable the execution of an instruction during the prologue and epilogue execution.

2. The method of claim 1, wherein an instruction executes if a stage predicate has first value, and the instruction does not execute if the stage predicate has a second value.

3. The method of claim 1, wherein a compare instruction or test instruction inside the loop determines the value of a stage predicate.

4. The method of claim 1, further comprising:

using rotating registers to hold the value of the stage predicates.

5. The method of claim 1, further comprising:

using a static predicate to turn off non-speculative stages in the epilogue while using the loop control compare to turn on and off speculative stages.

6. The method of claim 1, wherein a stage predicate assigned to instructions in a speculative stage permits the speculative scheduling of instructions that define values that are live out of the loop.

7. The method of claim 1, wherein the use of stage predicates prevents the flow of unnecessary data into the data cache.

8. The method of claim 5, wherein the use of the static predicate prevents the flow of unnecessary data into the data cache.

9. A method of processing counted loops with early exits, the method comprising:

receiving an intermediate representation that includes multiple exit branches including an exit branch in the middle of the loop; and

performing an if-conversion on the intermediate representation, including converting the multiple exit branches into a single exit branch; and

performing a compare operation to set values of predicates that determine the path from the single exit branch.

10. A method of processing fully if-converted loops, the method comprising:

receiving an intermediate representation for a while loop, where an if-conversion has not been performed on multiple branches;

performing an if-conversion on the intermediate representation, including removing some of the multiple branches, placing a first compare operation to guard multiple predicated instructions, and placing a second compare operation to guard an exit branch.

11. A method of processing uncounted loops with explicit branches of control flow, the method comprising:

receiving an intermediate representation, where a code is not modulo scheduled and branches internal to the loop are not if-converted

12. An apparatus for modulo scheduling, the apparatus comprising:

a modulo scheduler configured to assign a given stage predicate to each instruction in each stage including assigning a given stage predicate to each instruction in each speculative stage, the modulo scheduler configured to use the stage predicate to conditionally enable or disable the execution of an instruction during the prologue and epilogue execution.

13. The apparatus of claim 12, wherein the modulo scheduled is further configured to use a static predicate to turn off stages in the epilogue while using the loop control compare to turn on and off speculative stages.

14. An article of manufacture, comprising:

a machine-readable medium having stored thereon instructions to;

assign a given stage predicate to each instruction in each stage, including assigning a given stage predicate to each instruction in each speculative stage; and

use the stage predicate to conditionally enable or disable the execution of an instruction during the prologue and epilogue execution.

15. An apparatus for efficient code generation for modulo scheduled uncounted loops, the apparatus comprising:

means for assigning a given stage predicate to each instruction in each stage, including means for assigning a given stage predicate to each instruction in each speculative stage; and

coupled to the means for assigning the given stage predicate, means for using the stage predicate to conditionally enable or disable the execution of an instruction during the prologue and epilogue execution.