System and method for merging control flow paths
AssigneeHewlett-Packard Company
InventorRichard Eugene Hank
Life of this patent
Estimating the term…
Abstract
A method for eliminating a branch instruction in a control flow path of a computer program. The method includes providing a computer program having a plurality of basic blocks forming control flow paths, determining a cost of executing a branch instruction terminating a basic block in one of the control flow paths, determining a cost of combining basic blocks when merging the control flow paths, and eliminating the branch instruction from the basic block whose cost of execution is greater than the cost of combining the basic blocks in merging the control flow paths.
Claims55
A method for eliminating a branch instruction in a control flow path of a computer program, comprising:
- providing a computer program having a plurality of basic blocks forming control flow paths;
- determining a cost of executing a branch instruction in one of the control flow paths;
- determining a cost of combining basic blocks in merging the control flow paths;
- and
- eliminating the branch instruction from one control flow path whose cost of execution is greater than the cost of combining basic blocks in merging the control flow paths.
A method for producing a computer control flow path comprising:
- providing a computer program having a plurality of basic blocks forming control flow paths;
- selecting a first control flow path having at least one first basic block, leaving a second control flow path having at least one second basic block;
- determining a cost of executing the first basic block in the first control path and a cost of executing the second basic block in the second control flow path;
- determining that a cost of combining the first basic block and the second basic block is less than a cost of executing a branch instruction of the first control flow path;
- combining the first basic block and the second basic block to merge at least part of the second control flow path with the first control flow path to produce a computer control flow path having at least one combined basic block.
A method for merging control flow paths in a computer program, comprising:
- providing a computer program having a plurality of basic blocks forming control flow paths;
- determining an increase in height of the basic blocks when merged;
- determining that a cost of a branch instruction is more than the increase in height of the basic blocks when merged;
- and
- combining contents of the basic blocks to merge control flow paths.
An article of manufacture comprising a computer-readable medium having instructions for:
- determining a cost of executing a branch instruction in one of a plurality of control flow paths of a computer program;
- determining a cost of combining basic blocks in merging the control flow paths of the computer program;
- and
- eliminating the branch instruction from the control flow path whose cost of execution is greater than the cost of combining basic blocks in merging the control flow paths.
An article of manufacture comprising:
- a computer-readable medium having instructions for selecting from a computer program a first control flow path having at least one first basic block, leaving a second control flow path having at least one second basic block;
- determining a cost of executing the first basic block in the first control path and a cost of executing the second basic block in the second control flow path;
- determining that a cost of combining the first basic block and the second basic block is less than a cost of executing a branch instruction of the first control flow path;
- combining the first basic block and the second basic block to merge at least part of the second control flow path with the first control flow path to produce a computer control flow path having at least one combined basic block.
An article of manufacture comprising:
- a computer-readable medium having instructions for determining from basic blocks of control flow paths of a computer program an increase in height of the basic blocks when merged;
- determining that a cost of a branch instruction is more than the increase in height of the basic blocks when merged;
- and
- combining contents of the basic blocks to merge control flow paths.
A computer system comprising a computer program including combined basic blocks having a combined cost less than a cost of executing a branch instruction when the basic blocks are uncombined.
A computer system comprising a computer program including merged basic blocks having an increase in height from being merged which is less than a cost of a branch instruction when the basic blocks are unmerged.
A computer system for eliminating a branch instruction in a control flow path of a computer program, comprising:
- a computer program having a plurality of basic blocks forming control flow paths;
- means for determining a cost of executing a branch instruction in one of the control flow paths;
- means for determining a cost of combining basic blocks in merging the control flow paths;
- and
- means for eliminating the branch instruction from one control flow path whose cost of execution is greater than the cost of combining basic blocks in merging the control flow paths.
A computer system for producing a computer control flow path in a computer program, comprising:
- a compilation means for:
- selecting in a computer program a first control flow path having a branch instruction and at least one first basic block, leaving a second control flow path having at least one second basic block;
- determining a cost of executing the first basic block in the first control path and a cost of executing the second basic block in the second control flow path;
- determining that a cost of combining the first basic block and the second basic block is less than a cost of executing the branch instruction of the first control flow path;
- combining the first basic block and the second basic block to merge at least part of the second control flow path with the first control flow path to produce a computer control flow path having at least one combined basic block.
A computer system for merging control flow paths in a computer program, comprising a computer program having a plurality of basic blocks forming control flow paths;
- and scheduling means for determining an increase in height of the basic blocks when merged, for determining that a cost of a branch instruction is more than the increase in height of the basic blocks when merged, and for combining contents of the basic blocks to merge control flow paths.
Dependencies are inferred from the claim text.