Zero overhead looping by a decoder generating and enqueuing a branch instruction

• US 9,798,542 B2
• Filed: 10/31/2014
• Issued: 10/24/2017
• Est. Priority Date: 04/25/2014
• Status: Active Grant

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: Avago Technologies General IP PTE Limited (Broadcom, Inc.)
• Inventors: Kurd, Tariq, Redford, John, Barrett, Geoffrey
• Primary Examiner(s): Caldwell, Andrew
• Assistant Examiner(s): Mehta, Jyoti
• Application Number:
  US14/530,029
• Publication Number:
  US 20150309795A1
• Time in Patent Office: 1,089 Days
• CPC Class Codes: G06F 9/30065 Loop control instructions; iterative instructions, e.g. LOOP, REPEAT
• CPC Class Codes: G06F 9/30145 Instruction analysis, e.g. decoding, instruction word fields
• CPC Class Codes: G06F 9/325 for loops, e.g. loop detection or loop counter
• CPC Class Codes: G06F 9/3802 Instruction prefetching
• CPC Class Codes: G06F 9/3836 Instruction issuing, e.g. dynamic instruction scheduling or out of order instruction execution

Abstract

A method and apparatus for zero overheard loops is provided herein. The method includes the steps of identifying, by a decoder, a loop instruction and identifying, by the decoder, a last instruction in a loop body that corresponds to the loop instruction. The method further includes the steps of generating, by the decoder, a branch instruction that returns execution to a beginning of the loop body, and enqueing, by the decoder, the branch instruction into a branch reservation queue concurrently with an enqueing of the last instruction in a reservation queue.

Claims

1. A method in a processor, comprising:

identifying, by a decoder, a loop instruction;

identifying, by the decoder, a last instruction in a loop body that corresponds to the loop instruction;

generating, by the decoder, a branch instruction that returns execution to a beginning of the loop body; and

enqueuing, by the decoder, the branch instruction into a branch reservation queue concurrently with an enqueuing of the last instruction in a reservation queue.

2. The method of claim 1, further comprising maintaining a count of a number of times iterations of the loop body are fetched.

3. The method of claim 2, wherein the count is maintained in a register in an instruction fetch unit.

4. The method of claim 1, wherein the last instruction is not a branch instruction.

5. The method of claim 1, further comprising executing the loop body speculatively until a loop count is resolved, wherein the loop count is a number of times the loop body is to be executed.

6. The method of claim 5, wherein resolving the loop count includes determining the number of times the loop body is to be executed.

7. The method of claim 6, further comprising canceling instructions associated with excessively fetched iterations of the loop body responsive to the number of times the loop body is to be executed being less than a number of fetched iterations of the loop body.

8. The method of claim 1, wherein the loop instruction does not include an encoded immediate value of a number of times the loop instruction is to be executed.

9. The method of claim 1, further comprising fetching a number of iterations of the loop body equal to an immediate value encoded in the loop instruction.

10. The method of claim 1, wherein the identifying the loop instruction further comprises using an opcode to identify the loop instruction.

11. An apparatus, comprising:

a decoder configured to identify a loop instruction, identify a last instruction in a loop body corresponding to the loop instruction, generate a branch instruction that returns execution to a beginning of the loop body, and enqueue the branch instruction into a branch reservation queue concurrently with an enqueuing of the last instruction in the loop body in a reservation queue.

12. The apparatus of claim 11, further comprising:

an instruction fetch unit including a first register configured to store a count of a number of times iterations of the loop body are fetched, a second register configured to store a start address of the loop body, and a third register configured to store an address that identifies the last instruction in the loop body in response to a signal received from the decoder that indicates the loop instruction has been decoded.

13. The apparatus of claim 12, wherein the instruction fetch unit is configured to assert a signal that directs the decoder to generate the branch instruction in response to fetching the last instruction based on the address that identifies the last instruction in the loop body.

14. The apparatus of claim 11, wherein the last instruction is not a branch instruction.

15. The apparatus of claim 11, wherein the decoder is configured to identify the loop instruction based on an opcode of the loop instruction.

16. The apparatus of claim 11, wherein the loop instruction does not include an encoded immediate value of a number of times the loop instruction is to be executed.

17. The apparatus of claim 11, wherein the decoder is configured to cancel instructions associated with excessively fetched iterations of the loop body responsive to a number of times the loop body is to be executed being less than a number of fetched iterations of the loop body.