Software pipelining a hyperblock loop

A machine-readable medium having stored thereon sequences of instructions that when executed by a processor cause the processor to:

• a) compute a minimum initiation interval of a program loop having a single control flow entry and at least one control flow exit;
• b) save the program loop as a recorded program loop;
• c) apply instruction level parallelism transformations on the program loop to produce a revised program loop;
• d) apply single iteration scheduling on the revised program loop;
• e) determine a single iteration schedule length, SL, of the revised program loop;
• f) restore the recorded program loop as the revised program loop, if a previous length is not greater than SL;
• g) perform the following if the previous length is greater than or equal to SL and SL is greater than the minimum initiation interval:
• i) equate the previous length to SL;
• and
• ii) percolate selected instructions of the revised program loop to a prior iteration of the revised program loop;
• h) repeat b) through g) as long as the previous length is greater than or equal to SL and SL is greater than the minimum initiation interval;
• i) generate a loop prologue for the revised program loop;
• and
• j) generate a loop epilogue for the revised program loop.

A machine-readable medium having stored thereon sequences of instructions that when executed cause the processor to:

• a) compute a minimum initiation interval of a current loop having a single control flow entry and at least one control flow exit;
• b) apply instruction level parallelism transformations on the current loop to generate a transformed loop, wherein the current loop becomes a previous loop and the transformed loop becomes the current loop;
• c) apply single iteration scheduling on the current loop;
• d) percolate selected instructions of the current loop to a prior iteration of the current loop to generate a new instruction order for the current loop;
• and
• e) repeat b) through d) as long as a previous loop single iteration schedule length is greater than or equal to a current loop single iteration schedule length and the current loop single iteration schedule length exceeds the minimum iteration interval.

An apparatus comprising:

• a) means for computing a minimum initiation interval of a program loop having a single control flow entry and at least one control flow exit;
• b) means for applying instruction level parallelism transformations on the program loop;
• c) means for applying single iteration scheduling on the program loop;
• d) means for percolating selected instructions to a prior iteration of the program loop to generate a new instruction order for the program loop;
• e) means for repeating b) through d) as long as a previous single iteration length of the program loop is greater than or equal to a current single iteration schedule length of the program loop and the current single iteration schedule length exceeds the minimum initiation interval.

An apparatus comprising:

• a) means for computing a minimum initiation interval of a program loop having a single control flow entry and at least one control flow exit;
• b) means for saving the program loop as a recorded program loop;
• c) means for applying instruction level parallelism transformations on the program loop to produce a revised program loop;
• d) means for applying single iteration scheduling on the revised program loop;
• e) means for determining a single iteration schedule length, SL, of the revised program loop;
• f) means for restoring the recorded program loop as the revised program loop, if a previous length is not greater than SL;
• g) means for performing the following if the previous length is greater than or equal to SL and SL is greater than the minimum initiation interval:
• i) equating the previous length to SL;
• and
• ii) percolating selected instructions of the revised program loop to a prior iteration of the revised program loop;
• h) means for repeating b) through g) as long as the previous length is greater than or equal to SL and SL is greater than the minimum initiation interval;
• i) generate a loop prologue for the revised program loop;
• and
• j) generate a loop epilogue for the revised program loop.

An apparatus comprising:

• a) means for computing a minimum initiation interval of a current loop having a single control flow entry and at least one control flow exit;
• b) means for applying instruction level parallelism transformations on the current loop to generate a transformed loop, wherein the current loop becomes a previous loop and the transformed loop becomes the current loop;
• c) means for applying single iteration scheduling on the current loop;
• d) means for percolating selected instructions of the current loop to a prior iteration of the current loop to generate a new instruction order for the current loop;
• and
• e) means for repeating b) through d) as long as a previous loop single iteration schedule length is greater than or equal to a current loop single iteration schedule length and the current loop single iteration schedule length exceeds the minimum iteration interval.

A system comprising:

• a memory to store a sequence of instructions;
• a processor coupled to the memory, the processor scheduling the sequence of instructions within a loop by
• a) computing a minimum initiation interval of a program loop having a single control flow entry and at least one control flow exit;
• b) applying instruction level parallelism transformations on the program loop;
• c) applying single iteration scheduling on the program loop;
• d) percolating selected instructions to a prior iteration of the program loop to generate a new instruction order for the program loop;
• e) repeating b) through d) as long as a previous single iteration length of the program loop is greater than or equal to a current single iteration schedule length of the program loop and the current single iteration schedule length exceeds the minimum initiation interval.

A system comprising:

• a memory to store a sequence of instructions;
• a processor coupled to the memory, the processor scheduling the sequence of instructions within a loop by
• a) computing a minimum initiation interval of a program loop having a single control flow entry and at least one control flow exit;
• b) saving the program loop as a recorded program loop;
• c) applying instruction level parallelism transformations on the program loop to produce a revised program loop;
• d) applying single iteration scheduling on the revised program loop;
• e) determining a single iteration schedule length, SL, of the revised program loop;
• f) restoring the recorded program loop as the revised program loop, if a previous length is not greater than SL;
• g) performing the following if the previous length is greater than or equal to SL and SL is greater than the minimum initiation interval:
• i) equating the previous length to SL;
• and
• ii) percolating selected instructions of the revised program loop to a prior iteration of the revised program loop;
• h) repeating b) through g) as long as the previous length is greater than or equal to SL and SL is greater than the minimum initiation interval;
• i) generating a loop prologue for the revised program loop;
• and
• j) generating a loop epilogue for the revised program loop.

A system comprising:

• a memory to store a sequence of instructions;
• a processor coupled to the memory, the processor scheduling the sequence of instructions within a loop by
• a) computing a minimum initiation interval of a current loop having a single control flow entry and at least one control flow exit;
• b) applying instruction level parallelism transformations on the current loop to generate a transformed loop, wherein the current loop becomes a previous loop and the transformed loop becomes the current loop;
• c) applying single iteration scheduling on the current loop;
• d) percolating selected instructions of the current loop to a prior iteration of the current loop to generate a new instruction order for the current loop;
• and
• e) repeating b) through d) as long as a previous loop single iteration schedule length is greater than or equal to a current loop single iteration schedule length and the current loop single iteration schedule length exceeds the minimum iteration interval.