Path speculating instruction scheduler

A method comprising:

• placing a plurality of instructions into a control flow graph comprising a plurality of blocks of the instructions, the control flow graph defining a plurality of paths of control flow through the blocks of instructions;
• classifying a selected instruction in the control flow graph according to a readiness criteria for a target block in the control flow graph comprising:
• classifying the selected instruction as M-ready in the target block if the selected instruction does not have an unscheduled data predecessor in any path passing through the target block;
• and
• classifying the selected instruction as P-ready in the target block if the selected instruction is not M-ready in the target block and there is at least one path passing through the target block on which there is no unscheduled data predecessor for the selected instruction;
• and
• scheduling the selected instruction into the target block in the control flow graph for execution based on the readiness of the selected instruction.

A computer-readable medium having computer-readable instructions for performing a method comprising:

• placing a plurality of instructions into a control flow graph comprising a plurality of blocks of the instructions, the control flow graph defining a plurality of paths of control flow through the blocks of instructions;
• building a list of candidate instructions to be scheduled into a target block in the control flow graph for execution comprising:
• classifying a candidate instruction as M-ready in the target block if the candidate instruction does not have an unscheduled data predecessor in any path passing through the target block;
• and
• classifying the candidate instruction as P-ready in the target block if the candidate instruction is not M-ready in the target block and there is at least one path passing through the target block on which there is no unscheduled data predecessor for the candidate instruction;
• and
• selecting one of the candidate instructions to be scheduled into the target block based on the readiness of the candidate instruction in the target block and on whether a single copy on a path property for the selected instruction in the target block will be maintained or terminated on one or more paths through the target block.

A computer-readable medium having computer-readable instructions for performing a method comprising:

• placing a plurality of instructions into a control flow graph comprising a plurality or blocks of the instructions, the control flow graph defining a plurality of paths of control flow through the blocks of instructions;
• classifying a selected instruction in the control flow graph according to a readiness criteria for a target block in the control flow graph comprising:
• classifying the selected instruction as M-ready in the target block if the selected instruction does not have an unscheduled data predecessor in any path passing through the target block;
• and
• classifying the selected instruction as P-ready in the target block if the selected instruction is not M-ready in the target block and there is at least one path passing through the target block on which there is no unscheduled data predecessor for the selected instruction;
• and
• scheduling the selected instruction into the target block in the control flow graph for execution based on the readiness of the selected instruction.

A processor system comprising elements to:

• place a plurality of instructions into a control flow graph comprising a plurality of blocks of the instructions the control flow graph defining a plurality of paths of control flow through the blocks of instructions;
• build a list of candidate instructions to be scheduled into a target block in the control flow graph for execution comprising:
• classify a candidate instruction as M-ready in the target block if the candidate instruction does not have an unscheduled data predecessor in any path passing through the target block;
• and
• classify the candidate instruction as P-ready in the target block if the candidate instruction is not M-ready in the target block and there is at least one path passing through the target block on which there is no unscheduled data predecessor for the candidate instruction;
• and
• select one of the candidate instructions to be scheduled into the target block based on the readiness of the candidate instruction in the target block and on whether a single copy on a path property for the selected instruction in the target block will be maintained or terminated on one or more paths through the target block.