Method for increasing the speed of speculative execution

Patent metadata

Field	Value
Publication number	US-10061582-B2
Application number	US-201314143926-A
Country	US
Kind code	B2
Filing date	Dec 30, 2013
Priority date	Oct 20, 1999
Publication date	Aug 28, 2018
Grant date	Aug 28, 2018

Abstract

A method for increasing the speed of execution by a processor including the steps of selecting a sequence of instructions to optimize, optimizing the sequence of instructions, creating a duplicate of instructions from the sequence of instructions which has been selected to optimize, executing the optimized sequence of instructions, and responding to an error during the execution of the optimized sequence of instructions by rolling back to the duplicate of instructions from the sequence of instructions.

First claim

What is claimed is:

1. A method comprising:
storing, by a processor, a copy of original loop instructions that are in an original sequence order;
modifying, by the processor, the original sequence order to form modified loop instructions that are in a speculative execution sequence order in which it is unknown whether execution without error will occur, wherein said modifying includes:
before an initial instruction of the original loop instructions, causing the processor to release results of most recently completed loop to memory;
inserting, by the processor, a plurality of branch instructions that are taken to indicate a branch misprediction and cause the processor to exit and to end execution of a current loop; and
inserting, by the processor, a plurality of copies of a portion of the original loop instructions;

speculatively executing in the speculative execution sequence order, by using the processor, the modified loop instructions that are executable with fewer processor operations than execution of the original loop instructions, wherein the modified loop instructions are free of renaming at least one of the original loop instructions to prevent or correct errors and are free of compensation instructions comprising a duplicate of at least one of the original loop instructions to prevent or correct errors; and
if a branch instruction of the modified loop instructions is taken to indicate the branch misprediction and to cause the processor to exit and to end execution of the modified loop instructions, discarding results and state changes of an exited current uncompleted loop, and accessing and executing, from beginning of the initial instruction of and in the original sequence order, the copy of the original loop instructions by using the processor.

2. The method of claim 1 , wherein said modifying further comprises:
removing, by the processor, from the modified loop instructions an invariant comprising an operation that occurs in a same manner each time the original loop instructions are executed.

3. The method of claim 2 , wherein said modifying further comprises:
inserting, by the processor, the invariant in a prologue before the modified loop instructions.

4. A method comprising:
storing, by a processor, a copy of original loop instructions that are in an original sequence order;
modifying, by the processor, the original sequence order to form modified loop instructions that are in a speculative execution sequence order in which it is unknown whether execution without error will occur, wherein said modifying includes:
before an initial instruction of the original loop instructions, causing the processor to release results of most recently completed loop to memory; and
inserting, by the processor, a plurality of branch instructions that are taken to indicate a branch misprediction and cause the processor to exit and to end execution of a current loop;

speculatively executing in the speculative execution sequence order, by using the processor, the modified loop instructions that are executable with fewer processor operations than execution of the original loop instructions, wherein the modified loop instructions are free of renaming at least one of the original loop instructions to prevent or correct errors and are free of compensation instructions comprising a duplicate of at least one of the original loop instructions to prevent or correct errors; and
if a branch instruction of the modified loop instructions is taken to indicate the branch misprediction and to cause the processor to exit and to end execution of the modified loop instructions, discarding results and state changes of an exited current uncompleted loop, and accessing and executing, from beginning of the initial instruction of and in the original sequence order, the copy of the original loop instructions by using the processor.

5. The method of claim 4 , wherein said modifying further comprises:
removing, by the processor, from the modified loop instructions an invariant comprising an operation that occurs in a same manner each time the original loop instructions are executed.

6. The method of claim 5 , wherein said modifying further comprises:
inserting, by the processor, the invariant in a prologue before the modified loop instructions.

7. The method of claim 4 , wherein the processor comprises a VLIW (very long instruction word) processor.

8. A method comprising:
storing, by a processor, a copy of original loop instructions that are in an original sequence order;
modifying, by the processor, the original sequence order to form modified loop instructions that are in a speculative execution sequence order in which it is unknown whether execution without error will occur, wherein said modifying includes:
before an initial instruction of the original loop instructions, causing the processor to release results of most recently completed loop to memory;
inserting, by the processor, a plurality of branch instructions that are taken to indicate a branch misprediction and cause the processor to exit and to end execution of a current loop; and
deleting, by the processor, an instruction from the original loop instructions;

speculatively executing in the speculative execution sequence order, by using the processor, the modified loop instructions that are executable with fewer processor operations than execution of the original loop instructions, wherein the modified loop instructions are free of renaming at least one of the original loop instructions to prevent or correct errors and are free of compensation instructions comprising a duplicate of at least one of the original loop instructions to prevent or correct errors; and
if a branch instruction of the modified loop instructions is taken to indicate the branch misprediction and to cause the processor to exit and to end execution of the modified loop instructions, discarding results and state changes of an exited current uncompleted loop, and accessing and executing, from beginning of the initial instruction of and in the original sequence order, the copy of the original loop instructions by using the processor.

9. The method of claim 8 , wherein said modifying further comprises:
removing, by the processor, from the modified loop instructions an invariant comprising an operation that occurs in a same manner each time the original loop instructions are executed.

10. The method of claim 9 , wherein said modifying further comprises:
inserting, by the processor, the invariant in a prologue before the modified loop instructions.

11. The method of claim 8 , wherein the processor comprises a VLIW (very long instruction word) processor.

Assignees

• Intellectual Ventures Holding 81 Llc

Inventors

• Johnson Richard
• Rozas Guillermo

Classifications

• G06F9/30065 Primary

  Loop control instructions; iterative instructions, e.g. LOOP, REPEAT · CPC title

• G06F8/4441 Primary

  Reducing the execution time required by the program code · CPC title