Method and apparatus for instruction scheduling to reduce negative effects of compensation code

Claim 3

The method of claim 1, wherein the necessary compensation code is acceptable if none of the bottom-most basic blocks in the control flow path and the wavefront is a dummy block.

Claim 4

The method of claim 1, wherein the compensation code is acceptable if insertion of the compensation code into one of the bottom-most basic blocks in the control flow path and the wavefront does not increase a critical path for one of the basic blocks.

Claim 5

The method as set forth in claim 1, wherein the compensation code is acceptable if insertion of the compensation into one of the bottom-most basic blocks in the control flow path and the wavefront does not use a resource that is scarce in one of the basic blocks.

Claim 6

The method as set forth in claim 1, further comprising: removing the active block from the wavefront in response to the active block closing; adding to the wavefront all successor basic blocks of the active block; and identifying a new active block.

Claim 7

A program storage device readable by a general purpose computer, the program storage device encoding statements for performing a method of scheduling an instruction of a computer program, the method comprising scheduling the instruction into a region of the computer program by: identifying a plurality of basic blocks of the computer program, wherein a plurality of edges interconnect the basic blocks to form a control flow path; removing all edges from a split block to a join block within the region by the insertion of empty compensation blocks; determining whether the compensation blocks impede the control flow path, and if they do, the compensation blocks being deemed dummy blocks; identifying at least one of the basic blocks as a wavefront, wherein any control flow path from an entry point of the region to an exit point of the region passes through the wavefront and the wavefront is strongly independent; identifying a basic block on the wavefront as an active block; consulting the basic blocks on the wavefront to determine whether the insertion of compensation code into the basic blocks will produce a harmful effect on the control flow path, and if it will, the compensation code being deemed unacceptable; scheduling the instruction into the active block if the compensation code is acceptable; updating the wavefront when the active block closes; and repeating the scheduling step until all the instructions in the region have been scheduled.

Claim 8

A program storage device readable by a general purpose computer, the program storage device encoding statements for performing a method of scheduling an instruction of a computer program, the method comprising scheduling the instruction into a region of the computer program by: identifying a plurality of basic blocks of the computer program, wherein a plurality of edges interconnect the basic blocks to form a control flow path; removing all edges from a split block to a join block within the region by the insertion of empty compensation blocks; determining whether the compensation blocks impede the control flow path, and if they do, the compensation blocks being deemed dummy blocks; identifying at least one of the basic blocks as a wavefront, wherein any control flow path from an entry point of the region to an exit point of the region passes through the wavefront and the wavefront is strongly independent; identifying a basic block on the wavefront as an active block; consulting the basic blocks on the wavefront to determine whether the insertion of compensation code into the basic blocks will produce a harmful effect on the control flow path, and if it will, the compensation code being deemed unacceptable; scheduling the instruction into the active block if the compensation code is acceptable; updating the wavefront when the active block closes; and repeating the scheduling step until all the instructions in the region have been scheduled.

Claim 9

The program storage device as set forth in claim 6, wherein the compensation code is acceptable if none of the bottom-most basic blocks in the control flow path and the wavefront is a dummy block.

Claim 10

The program storage device as set forth in claim 6, wherein the compensation code is acceptable if insertion of the compensation code into one of the bottom-most basic blocks in the control flow path and the wavefront does not increase a critical path for one of the basic blocks.

Claim 11

The program storage device as set forth in claim 6, wherein the compensation code is acceptable if insertion of the compensation into one of the bottom-most basic blocks in the control flow path and the wavefront does not use a resource that is scarce in one of the basic blocks.

Claim 12

The program storage device as set forth in claim 6, the method further comprising: removing the active block from the wavefront in response to the active block closing; adding to the wavefront all successor basic blocks of the active block; and identifying a new active block.

Claim 13

A computer programmed with a first program, the first program including statements for a method, the method comprising scheduling an instruction of a second program into a region of the second program by: identifying a plurality of basic blocks of the computer program, wherein a plurality of edges interconnect the basic blocks to form a control flow path; removing all edges from a split block to a join block within the region by the insertion of empty compensation blocks; determining whether the compensation blocks impede the control flow path, and if they do, the compensation blocks being deemed dummy blocks; identifying at least one of the basic blocks as a wavefront, wherein any control flow path from an entry point of the region to an exit point of the region passes through the wavefront and the wavefront is strongly independent; identifying a basic block on the wavefront as an active block; consulting the basic blocks on the wavefront to determine whether the insertion of compensation code into the basic blocks will produce a harmful effect on the control flow path, and if it will, the compensation code being deemed unacceptable; scheduling the instruction into the active block if the compensation code is acceptable; updating the wavefront when the active block closes; and repeating the scheduling step until all the instructions in the region have been scheduled.

Claim 14

A computer programmed with a first program, the first program including statements for a method, the method comprising scheduling an instruction of a second program into a region of the second program by: identifying a plurality of basic blocks of the computer program, wherein a plurality of edges interconnect the basic blocks to form a control flow path; removing all edges from a split block to a join block within the region by the insertion of empty compensation blocks; determining whether the compensation blocks impede the control flow path, and if they do, the compensation blocks being deemed dummy blocks; identifying at least one of the basic blocks as a wavefront, wherein any control flow path from an entry point of the region to an exit point of the region passes through the wavefront and the wavefront is strongly independent; identifying a basic block on the wavefront as an active block; consulting the basic blocks on the wavefront to determine whether the insertion of compensation code into the basic blocks will produce a harmful effect on the control flow path, and if it will, the compensation code being deemed unacceptable; scheduling the instruction into the active block if the compensation code is acceptable; updating the wavefront when the active block closes; and repeating the scheduling step until all the instructions in the region have been scheduled.

Claim 15

The computer as set forth in claim 11, wherein the compensation code is acceptable if none of the bottom-most basic blocks in the control flow path and the wavefront is a dummy block.

Claim 16

The computer as set forth in claim 11, wherein the compensation code is acceptable if insertion of the compensation code into one of the bottom-most basic blocks in the control flow path and the wavefront does not increase a critical path for one of the basic blocks.

Claim 17

The computer as set forth in claim 11, wherein the compensation code is acceptable if insertion of the compensation into one of the bottom-most basic blocks in the control flow path and the wavefront does not use a resource that is scarce in one of the basic blocks.

Claim 18

The computer as set forth in claim 11, wherein the method further comprises: removing the active block from the wavefront in response to the active block closing; adding to the wavefront all successor basic blocks of the active block; and identifying a new active block.