Critical path optimization—unload hard extended scalar block

A method, performed by a compiler, of reducing the execution time of a program including a number of blocks in control flow order, said method comprising the acts of:

• assigning a hardness parameter to each block indicating the amount of resources required to execute the block;
• comparing each assigned hardness parameter to an external boundary parameter to identify target blocks that require excessive resources to execute;
• for each target block with a plurality of predecessor blocks, comparing the hardness parameter of target block to the hardness parameter of each of the target block's predecessors;
• and
• if the hardness parameter of the target block is greater than the hardness parameter of each of the predecessor blocks, migrating critical operations out of the target block to be executed in parallel inside each predecessor block.

A method for unloading operations from a scheduled extended scalar block of operations with the extended scalar block having a scheduled time of execution longer than optimal;

• with the extended scalar block preceded by other control flow predecessor operations, said method comprising the acts of:
• identifying as critical operations those operation in the scheduled extended scalar block with the longest execution time;
• iteratively migrating critical operations from said critical extended scalar block to a control flow predecessor block of scheduled operations;
• and
• replacing migrated critical operations with non-critical operations to reduce scheduled execution time of the extended scalar block.

A computer program product comprising:

• a computer readable medium having program code for implementing compiler operations to balance Extended Scalar Blocks (ESBs) in a control flow, said program code comprising:
• program code for causing a computer to identify critical operations in a source ESB;
• program code for causing a computer to recursively pass an argument tree for each identified critical block and copy and insert each operation in the argument tree into each control flow predecessor of the source ESB and to get a virtual register needed for inserted operations;
• program code for causing a computer to for insert write operations after each copied critical operation in the control flow predecessor for setting the result operand in a virtual register;
• program code for causing a computer to critical operations and operations in the argument tree with a read operation that reads the result of critical operations migrated to the control flow predecessor from the virtual registers so that the height of the source ESB is reduced.

A method, performed by a compiler, of reducing the execution time of a program including a number of blocks in control flow order, said method comprising the acts of:

• assigning a hardness parameter to each block indicating the amount of resources required to execute the block, the hardness parameter being equal to a combination of an execution counter parameter of the block and number of operations parameter;
• comparing each assigned hardness parameter to an external boundary parameter to identify target blocks that require excessive resources to execute;
• for each target block with a plurality of predecessor blocks, comparing the hardness parameter of target block to the hardness parameter of each of the target block's predecessors;
• if the hardness parameter of the target block is greater than the hardness parameter of each of the predecessor blocks, migrating critical operations out of the target block to be executed in parallel inside each predecessor block;
• and
• wherein said act of comparing comprises migrating operations from the target block if (C(B)≧C(Bpred) and (W(B)−W(Bpred)>Wdiff0)) is true, where C(B) is the execution counter of the target block, C(Bpred) is the execution counter of the predecessor block, W(B) is the number of operations parameter of the target block, W(Bpred) is the number of operations parameter of the predecessor block, and Wdiff0 is an external boundary parameter.

A method of compiling a computer program given as a predicated intermediate representation including a number of extended scalar blocks in control flow order to reduce execution time of the program, the method including the steps of:

• assigning a hardness parameter to each extended scalar block that is equal to a combination of an execution counter parameter C of such extended scalar block, obtained from profile data, and a weight parameter W calculated from a division of a number of operations of such extended scalar block by a value equal to a product of such extended scalar block critical path length in processor cycles and number of processor arithmetic channels;
• identifying target blocks from all hard extended scalar blocks having an assigned hardness to unload said target blocks;
• and
• migrating critical operations out of each target hard extended scalar block to be executed in parallel inside each control flow predecessor block of said block.

A method, performed by a compiler, of reducing the execution time of a program including a number of blocks in control flow order, said method comprising the acts of:

• assigning a hardness parameter to each block indicating the amount of resources required to execute the block, including setting the hardness parameter equal to a combination of an execution counter parameter of the block and number of operations parameter;
• comparing each assigned hardness parameter to an external boundary parameter to identify target blocks that require excessive resources to execute, including migrating operations from the target block if (C(B)≧C(Bpred) and (W(B)−W(Bpred)>Wdiff0)) is true, where C(B) is the execution counter of the target block, C(Bpred) is the execution counter of the predecessor block, W(B) is the number of operations parameter of the target block, W(Bpred) is the number of operations parameter of the predecessor block, and Wdiff0 is an external boundary parameter;
• for each target block, comparing the hardness parameter of such target block to the hardness parameter a target blocks predecessor;
• and
• if the hardness parameter of the target block is greater than the hardness parameter of the predecessor block, migrating critical operations out of the target block to be executed in parallel inside the predecessor block.