Method for managing branch instructions and a device having branch instruction management capabilities
View Patent ↗A method for managing branch instructions, the method includes: providing, to pipeline stages of a processor, multiple variable length groups of instructions; wherein each pipeline stage executes a group of instruction during a single execution cycle; receiving, at a certain execution cycle, multiple instruction fetch requests from multiple pipeline stages, each pipeline stage that generates an instruction fetch request stores a variable length group of instructions that comprises a branch instruction; sending to the fetch unit an instruction fetch command that is responsive to a first in order branch instruction in the pipeline stages; wherein if the first in order fetch command is a conditional fetch command then the instruction fetch command comprises a resolved target address; wherein the sending of the instruction fetch command is restricted to a single instruction fetch command per a single execution cycle.
1. A method for managing branch instructions, the method comprising:
providing, to pipeline stages of a processor, multiple variable length groups of instructions; wherein each pipeline stage executes a group of instructions during a single execution cycle;
receiving, at a controller during a certain execution cycle, multiple instruction fetch requests from multiple pipeline stages, each pipeline stage of the multiple pipeline stages that provides an instruction fetch request to the controller stores a variable length group of instructions that comprises a branch instruction;
updating status information indicative of an order of branch instructions stored in the multiple pipeline stages based on an executed branch instruction of an immediately preceding execution cycle, wherein the status information for each of the multiple branch instructions includes a bit set for each branch instruction that precedes that branch instruction;
determining a first in order branch instruction based on the status information wherein the first in order branch instruction has zero bits set in the status information; and
sending, from the controller, to a fetch unit a certain instruction fetch command that is responsive to the first in order branch instruction of the multiple instruction fetch requests from the multiple pipeline stages, wherein the controller will always send an instruction fetch command responsive to the first in order branch instruction of the multiple instruction fetch requests for a cycle during which the controller receives the multiple instruction fetch requests.
2. The method according to claim 1 comprising sending to the fetch unit a resolved target address and a branch prediction indication that is indicative of a correctness of a predicted target address that was generated by a branch prediction unit.
3. The method according to claim 2 comprising:
receiving, at a certain execution cycle, a plurality of instruction fetch requests from a plurality of pipeline stages that store a plurality of branch requests; wherein the plurality of branch instruction fetch requests are associated with the same condition; and
storing a resolved condition indication until all branch instructions exit the pipeline stages.
4. The method according to claim 2 comprising associating with each branch instruction in the pipeline stages a number of preceding branch instructions that are stored in the branch prediction unit.
5. The method according to claim 2 comprising restricting each variable length group of instructions to include less than two branch instructions.
6. The method according to claim 1 comprising sending the certain instruction fetch command to the fetch unit if a predicted target address associated with the first in order branch command was erroneous.
7. The method according to claim 6 comprising:
receiving, at a certain execution cycle, a plurality of instruction fetch requests from a plurality of pipeline stages that store a plurality of branch requests; wherein the plurality of branch instruction fetch requests are associated with the same condition; and
storing a resolved condition indication until all branch instructions exit the pipeline stages.
8. The method according to claim 1 comprising associating with each branch instruction in the pipeline stages a number of preceding branch instructions that are stored in the branch prediction unit.
9. The method according to claim 1 comprising restricting each variable length group of instructions to include less than two branch instructions.
10. The method according to claim 1 comprising:
receiving, at a certain execution cycle, a plurality of instruction fetch requests from a plurality of pipeline stages that store a plurality of branch requests; wherein the plurality of branch instruction fetch requests are associated with the same condition; and
storing a resolved condition indication until all branch instructions exit the pipeline stages.
11. The method according to claim 1 wherein the first in order branch instruction is determined by monitoring and updating status vectors that indicate a number of branch instructions that precede each branch instruction.
12. The method according to claim 1 further comprising:
determining that the first in order branch instruction is a mispredicted branch instruction;
flushing instructions in the pipeline stages that follow the mispredicted branch instruction; and
storing results of the execution of the flushed instructions that follow the mispredicted branch instruction for later use when the flushed instructions are later retrieved by the fetch unit.
13. A system for managing branch instructions, the system comprising:
multiple pipeline stages of a processor, each adapted to execute a single variable length group of instructions per execution cycle;
a fetch unit adapted to fetch groups of variable length instructions from a memory unit; and
a controller, configured to:
receive, at a certain execution cycle, multiple instruction fetch requests from multiple pipeline stages, each pipeline stage of the multiple pipeline stages that provides an instruction fetch request to the controller stores a variable length group of instructions that comprises a branch instruction;
update status information indicative of an order of branch instructions stored in the multiple pipeline stages based on an executed branch instruction of an immediately preceding execution cycle, wherein the status information for each of the multiple branch instructions includes a bit set for each branch instruction that precedes that branch instruction;
determine a first in order branch instruction based on the status information, wherein the first in order branch instruction has zero bits set in the status information; and
send to the fetch unit an instruction fetch command that is responsive to the first in order branch instruction of the multiple instruction fetch requests from the pipeline stages, wherein the controller always executes the first in order branch instruction during each execution cycle;
wherein only if the first in order fetch command is a conditional fetch command then the instruction fetch command comprises a resolved target address;
wherein the controller is restricted to send up to a single instruction fetch command per a single execution cycle.
14. The system according to claim 13 wherein the controller is adapted to send to the fetch unit the resolved target address and a branch prediction indication that is indicative of a correctness of a predicted target address that was generated by a branch prediction unit.
15. The system according to claim 13 wherein the controller is adapted to send the instruction fetch command to the fetch unit if a predicted target address associated with the first in order branch command was erroneous.
16. The system according to claim 13 wherein the controller is adapted to associate with each branch instruction in the pipeline stages a number of preceding branch instructions that are stored in the branch prediction unit.
17. The system according to claim 13 wherein each variable length group of instructions is restricted to include less than two branch instructions.
18. The system according to claim 13 wherein the pipeline stages are adapted to be flushed of instructions that followed a mispredicted conditional branch command while send to storage intermediate results of executions of the flushed groups of instructions.
19. The system according to claim 13 wherein the controller is adapted to:
receive, at a certain execution cycle, a plurality of instruction fetch requests from a plurality of pipeline stages that store a plurality of branch requests; wherein the plurality of branch instruction fetch requests are associated with the same condition; and
store a resolved condition indication until all branch instructions exit the pipeline stages.
20. A method for managing branch instructions, the method comprising:
providing, to pipeline stages of a processor, multiple variable length groups of instructions; wherein each pipeline stage executes a group of instructions during a single execution cycle;
receiving, at a controller during a certain execution cycle, multiple instruction fetch requests from multiple pipeline stages, each pipeline stage of the multiple pipeline stages that provides an instruction fetch request to the controller stores a variable length group of instructions that comprises a branch instruction;
updating status information indicative of an order of branch instructions stored in the multiple pipeline stages based on an executed branch instruction of an immediately preceding execution cycle, wherein the status information for each of the multiple branch instructions includes a bit set for each branch instruction that precedes that branch instruction;
determining a first in order branch instruction based on the status information, wherein the first in order branch instruction has zero bits set in the status information;
sending, from the controller, to the fetch unit an instruction fetch command that is responsive to the first in order branch instruction in the pipeline stages;
determining that the first in order branch instruction is a mispredicted branch instruction;
flushing instructions in the pipeline stages that follow the mispredicted branch instruction; and
storing results of the execution of the flushed instructions that follow the mispredicted branch instruction for later use when the flushed instructions are later retrieved by the fetch unit.