System and method for assigning basic blocks to computer control flow paths

A method for selecting a basic block to a control flow path in a computer program by use of a compiler optimizer in a computer, the method comprising:

• providing, the computer, a computer program including an entry basic block and a plurality of basic blocks forming control flow paths;
• determining that immediate subsets of the control flow paths commencing with the entry basic block are essentially unbiased subsets, wherein the unbiased subsets comprises predictive ratios that do not differ above a threshold value, wherein a predictive ratio is a probability that the computer will execute instructions of a control flow path;
• and
• selecting a basic block with a shortest height to produce a selected basic block, wherein a height comprises a number of cycles that a computer system takes to execute the instructions in each basic block on a control flow path or takes into account any latency among instructions of a basic block or instructions from another basic block.

A method for selecting a basic block to a control flow path in a computer program by use of a compiler optimizer in a computer, the method comprising:

• providing, the computer, a computer program including an entry basic block and a plurality of basic blocks forming control flow paths;
• determining that immediate subsets of the control flow paths commencing with the entry basic block are essentially unbiased subsets, wherein the unbiased subsets comprises predictive ratios that do not differ above a threshold value, wherein a predictive ratio is a probability that the computer will execute instructions of a control flow path;
• determining that the basic blocks in the immediate subsets of the flow control paths have essentially a same height, wherein a height comprises a number of cycles that a computer system takes to execute the instructions in each basic block on a control flow path or takes into account any latency among instructions of a basic block or instructions from another basic block;
• and
• selecting any one of the basic blocks in the immediate subsets of the flow control flow paths.

A method for selecting a basic block to a control flow path in a computer program by use of a compiler optimizer in a computer, the method comprising:

• providing, the computer, a computer program including an entry basic block and a plurality of basic blocks forming control flow paths;
• and
• selecting a basic block from the entry basic block in accordance with an if-instruction selected from a group of if-instructions consisting of:
• (i) if immediate subsets of control flow paths commencing with the entry basic block are biased subsets, wherein the biased subsets comprises predictive ratios that differ by more than a threshold value, wherein a predictive ratio is a probability that the computer will execute instructions of a control flow path, then selecting a most frequent successive basic block in a most biased subset of the control flow paths to produce a selected basic block, wherein the most biased subset is a first subset having a higher probability of execution than a second subset in the immediate subsets,
• (ii) if immediate subsets of control flow paths commencing from the entry basic block are essentially unbiased subsets, wherein the unbiased subsets comprises predictive ratios that do not differ above a threshold value, wherein a predictive ratio is a probability that the computer will execute instructions of a control flow path, then selecting a basic block with a shortest height to produce a selected basic block, wherein a height comprises a number of cycles that a computer system takes to execute the instructions in each basic block on a control flow path or takes into account any latency among instructions of a basic block or instructions from another basic block,
• (iii) if immediate subsets of control flow paths commencing from the entry basic block are essentially unbiased subsets, and if the basic blocks in the immediate subsets of flow control flow paths have essentially the same height, then selecting any one of the basic blocks in the immediate subsets of the flow control flow paths, and
• (iv) if immediate subsets of control flow paths commencing from the entry basic block contain no basic block selected in accordance with the if-instruction of subparagraph (i) or the if-instruction of subparagraph (ii) or the if-instruction of subparagraph (iii), then selecting a basic block not assigned in any immediate subset of the control flow paths to produce a selected basic block.

A method for forming a computer control flow path in a computer program by use of a compiler optimizer in a computer, the method comprising the steps:

• (a) providing, in a computer, a computer program having a plurality of basic blocks forming control flow paths;
• (b) selecting a basic block in accordance with an if-instruction selected from a group of if-instructions consisting of:
• (i) if immediate subsets of control flow paths are biased subsets, wherein the biased subsets comprises predictive ratios that differ by more than a threshold value, wherein a predictive ratio is a probability that the computer will execute instructions of a control flow path, then selecting a most frequent successive basic block in a most biased subset of the control flow paths to produce a selected basic block, wherein the most biased subset is a first subset having a higher probability of execution than a second subset in the immediate subsets,
• (ii) if immediate subsets of control flow paths are essentially unbiased subsets, wherein the unbiased subsets comprises predictive ratios that do not differ above a threshold value, wherein a predictive ratio is a probability that the computer will execute instructions of a control flow path, then selecting a basic block with a shortest height to produce a selected basic block, wherein a height comprises a number of cycles that a computer system takes to execute the instructions in each basic block on a control flow path or takes into account any latency among instructions of a basic block or instructions from another basic block,
• (iii) if immediate subsets of control flow paths commencing are essentially unbiased subsets, and if the basic blocks in the immediate subsets of flow control flow paths have essentially the same height, select any one of the basic blocks in the immediate subsets of the flow control flow paths, and
• (iv) if immediate subsets of control flow paths contain no basic block selected in accordance with the if-instruction of subparagraph (i) or the if-instruction of subparagraph (ii) or the if-instruction of subparagraph (iii), select a basic block not assigned in any immediate subset of the control flow paths.

An article of manufacture comprising:

• a computer-readable storage medium having instructions for selecting, in a computer program having control flow paths in a computer, a basic block from an entry basic block in accordance with an if-instruction selected from a group of if-instructions consisting of:
• (i) if immediate subsets of control flow paths commencing with the entry basic block are biased subsets, wherein the biased subsets comprises predictive ratios that differ by more than a threshold value, wherein a predictive ratio is a probability that the computer will execute instructions of a control flow path, then selecting a most frequent successive basic block in a most biased subset of the control flow paths to produce a selected basic block, wherein the most biased subset is a first subset having a higher probability of execution than a second subset in the immediate subsets,
• (ii) if immediate subsets of control flow paths commencing from the entry basic block are essentially unbiased subsets, wherein the unbiased subsets comprises predictive ratios that do not differ above a threshold value, wherein a predictive ratio is a probability that the computer will execute instructions of a control flow path, select a basic block with a shortest height to produce a selected basic block,
• (iii) if immediate subsets of control flow paths commencing from the entry basic block are essentially unbiased subsets, and if the basic blocks in the immediate subsets of flow control flow paths have essentially the same height, select any one of the basic blocks in the immediate subsets of the flow control flow paths, wherein a height comprises a number of cycles that a computer system takes to execute the instructions in each basic block on a control flow path or takes into account any latency among instructions of a basic block or instructions from another basic block, and
• (iv) if immediate subsets of control flow paths commencing from the entry basic block contain no basic block selected in accordance with the if-instruction of subparagraph (i) or the if-instruction of subparagraph (ii) or the if-instruction of subparagraph (iii), select a basic block not assigned in any immediate subset of the control flow paths to produce a selected basic block.

An article of manufacture comprising:

• a computer-readable storage medium having instructions for
• (a) selecting, from a computer program having a plurality of basic blocks forming control flow paths in a computer, a basic block in accordance with an if-instruction selected from a group of if-instructions consisting of:
• i) if immediate subsets of control flow paths are biased subsets, wherein the biased subsets comprises predictive ratios that differ by more than a threshold value, wherein a predictive ratio is a probability that the computer will execute instructions of a control flow path, then selecting a most frequent successive basic block in a most biased subset of the control flow paths to produce a selected basic block, wherein the most biased subset is a first subset having a higher probability of execution than a second subset in the immediate subsets,
• (ii) if immediate subsets of control flow paths are essentially unbiased subsets, wherein the unbiased subsets comprises predictive ratios that do not differ above a threshold value, wherein a predictive ratio is a probability that the computer will execute instructions of a control flow path, select a basic block with a shortest height to produce a selected basic block, wherein a height comprises a number of cycles that a computer system takes to execute the instructions in each basic block on a control flow path or takes into account any latency among instructions of a basic block or instructions from another basic block,
• (iii) if immediate subsets of control flow paths commencing are essentially unbiased subsets, and if the basic blocks in the immediate subsets of flow control flow paths have essentially the same height, select any one of the basic blocks in the immediate subsets of the flow control flow paths, and
• (iv) if immediate subsets of control flow paths contain no basic block selected in accordance with the if-instruction of subparagraph (i) or the if-instruction of subparagraph (ii) or the if-instruction of subparagraph (iii), select a basic block not assigned in any immediate subset of the control flow paths;
• (b) repeating said selecting step of paragraph (a) to produce a plurality of selected basic blocks and form a computer flow control path.

A computer system comprising a computer executing a computer program having flow control paths and a selected basic block selected from an entry basic block in accordance with an if-instruction selected from a group of if-instructions consisting of:

• (i) if immediate subsets of control flow paths commencing with the entry basic block are biased subsets, wherein the biased subsets comprises predictive ratios that differ by more than a threshold value, wherein a predictive ratio is a probability that the computer will execute instructions of a control flow path, then selecting a most frequent successive basic block in a most biased subset of the control flow paths to produce a selected basic block, wherein the most biased subset is a first subset having a higher probability of execution than a second subset in the immediate subsets,
• (ii) if immediate subsets of control flow paths commencing from the entry basic block are essentially unbiased subsets, wherein the unbiased subsets comprises predictive ratios that do not differ above a threshold value, wherein a predictive ratio is a probability that the computer will execute instructions of a control flow path, select a basic block with a shortest height to produce a selected basic block, wherein a height comprises a number of cycles that a computer system takes to execute the instructions in each basic block on a control flow path or takes into account any latency among instructions of a basic block or instructions from another basic block,
• (iii) if immediate subsets of control flow paths commencing from the entry basic block are essentially unbiased subsets, and if the basic blocks in the immediate subsets of flow control flow paths have essentially the same height, select any one of the basic blocks in the immediate subsets of the flow control flow paths, and
• (iv) if immediate subsets of control flow paths commencing from the entry basic block contain no basic block selected in accordance with the if-instruction of subparagraph (i) or the if-instruction of subparagraph (ii) or the if-instruction of subparagraph (iii), select a basic block not assigned in any immediate subset of the control flow paths to produce a selected basic block.

A computer system comprising a computer executing a computer program including a computer flow control path formed from a plurality of selected basic blocks having been selected in accordance with an if-instruction selected from a group of if-instructions consisting of:

• (i) if immediate subsets of control flow paths are biased subsets, wherein the biased subsets comprises predictive ratios that differ by more than a threshold value, wherein a predictive ratio is a probability that the computer will execute instructions of a control flow path, select a most frequent successive basic block in a most biased subset of the control flow paths to produce a selected basic block, wherein the most biased subset is a first subset having a higher probability of execution than a second subset in the immediate subsets,
• (ii) if immediate subsets of control flow paths are essentially unbiased subsets, wherein the unbiased subsets comprises predictive ratios that do not differ above a threshold value, wherein a predictive ratio is a probability that the computer will execute instructions of a control flow path, select a basic block with a shortest height to produce a selected basic block, wherein a height comprises a number of cycles that a computer system takes to execute the instructions in each basic block on a control flow path or takes into account any latency among instructions of a basic block or instructions from another basic block,
• (iii) if immediate subsets of control flow paths commencing are essentially unbiased subsets, and if the basic blocks in the immediate subsets of flow control flow paths have essentially the same height, select any one of the basic blocks in the immediate subsets of the flow control flow paths, and
• (iv) if immediate subsets of control flow paths contain no basic block selected in accordance with the if-instruction of subparagraph (i) or the if-instruction of subparagraph (ii) or the if-instruction of subparagraph (iii), select a basic block not assigned in any immediate subset of the control flow paths.