Method for software pipelining of irregular conditional control loops

• US 20020120923A1
• Filed: 12/08/2000
• Published: 08/29/2002
• Est. Priority Date: 12/30/1999
• Status: Active Grant

• Current Assignee: Texas Instruments, Inc.
• Original Assignee: Texas Instruments, Inc.
• Inventors: Stotzer, Eric J., Granston, Elana D., Zbiciak, Joseph
• Granted Patent: US 6,892,380 B2
• Time in Patent Office: Days
• US Class Current: 717/160
• CPC Class Codes: G06F 8/4452 Software pipelining
• CPC Class Codes: G06F 8/452 Loops

Abstract

A method for software pipelining of irregular conditional control loops including pre-processing the loops so they can be safely software pipelined. The pre-processing step ensures that each original instruction in the loop body can be over-executed as many times as necessary. During the pre-processing stage, each instruction in the loop body is processing in turn (N4). If the instruction can be safely speculatively executed, it is left alone (N6). If it could be safely speculatively executed except that it modifies registers that are live out of the loop, then the instruction can be pre-processed using predication or register copying (N7, N8, N9). Otherwise, predication must be applied (N10). Predication is the process of guarding an instruction. When the guard condition is true, the instruction executes as though it were unguarded. When the guard condition is false, the instruction is nullified.

Claims

1. A method of pipelining program loops having irregular loop control comprises the steps of:

determining which instructions in loop code in a memory may be speculatively executed,

storing in a computer memory a set of registers that are modified by an instruction and are alive out of the loop, and

modifying the program code so that the values of those registers are saved to a temporary register during all proper iterations, and

copying back to the register the value of the temporary register once the loop is completed.

2. The method of claim 1, applied to any program loops wherein a minimum trip count is reduced to one.

3. The method of claim 1, applied to any program loops wherein a need for a multiversion code is eliminated.

4. A method for software pipelining of irregular conditional control loops includes pre-processing the loops so they can be safely software pipelined, comprising the steps of:

pre-processing each instruction in the loop in turn;

if the instruction can be safely speculatively executed, leaving the instruction alone;

if it could be safely speculatively executed except that it modifies registers that are live out of the loop, pre-processing the instruction using predication or register copying.

5. The method of claim 4, including the step of pre-processing the instruction by predication if it could not be safely speculatively executed.

6. The method of claim 4, wherein if it could be safely speculatively executed except that it modifies registers that are live out of the loop, pre-processing the instruction by register copying.