Loop code processor optimizations

• US 10,459,727 B2
• Filed: 12/31/2015
• Issued: 10/29/2019
• Est. Priority Date: 12/31/2015
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Chilimbi, Trishul A, Ruwase, Olatunji, Seshadri, Vivek
• Primary Examiner(s): Faherty, Corey S
• Application Number:
  US14/986,465
• Publication Number:
  US 20170192787A1
• Time in Patent Office: 1,398 Days
• Field of Search: None
• CPC Class Codes: G06F 12/0875 with dedicated cache, e.g. instruction or stack
• CPC Class Codes: G06F 2212/452 Instruction code
• CPC Class Codes: G06F 9/3017 Runtime instruction translation, e.g. macros
• CPC Class Codes: G06F 9/30181 Instruction operation extension or modification
• CPC Class Codes: G06F 9/30192 according to data descriptor, e.g. dynamic data typing
• CPC Class Codes: G06F 9/30196 using decoder, e.g. decoder per instruction set, adaptable or programmable decoders
• 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/381 Loop buffering
• CPC Class Codes: G06F 9/3812 with instruction modification, e.g. store into instruction stream
• CPC Class Codes: G06F 9/3826 Bypassing or forwarding of data results, e.g. locally between pipeline stages or within a pipeline stage
• CPC Class Codes: G06F 9/3867 using instruction pipelines
• CPC Class Codes: G06F 9/3873 Variable length pipelines, e.g. elastic pipeline
• CPC Class Codes: G06N 3/02 Neural networks
• CPC Class Codes: G06N 3/08 Learning methods

Abstract

Loop code processor optimizations are implemented as a loop optimizer extension to a processor pipeline. The loop optimizer generates optimized code associated with code loops that include at least one zero-optimizable instruction. The loop optimizer may generate multiple versions of optimized code associated with a particular code loop, where each of the multiple version of optimized code has a different associated condition under which the optimized code can be safely executed.

Claims

1. A method comprising:

detecting, within a processor, a code loop that includes one or more zero-optimizable instructions;

generating, based on a first condition that a first input has a value of zero and is stored in a cache line that includes at least one non-zero value, a first optimized code corresponding to the code loop; and

generating, based on a second condition that a second input has a value of zero and is clustered with other zero values in a cache line, a second optimized code corresponding to the code loop.

2. A method as recited in claim 1, wherein:

the code loop includes a plurality of instructions; and

the first and second optimized versions of the code loop do not include one or more of the plurality of instructions that are unnecessary.

3. A method as recited in claim 1, wherein generating the optimized version of the code loop includes storing to a cache:

the first and second optimized version of the code loop; and

the first and second conditions.

4. A method as recited in claim 3, wherein generating the first and second optimized versions of the code loop further includes maintaining in the cache, a mapping between the code loop and the first and second optimized versions of the code loop.

5. A method as recited in claim 1, wherein generating the first optimized version of the code loop includes optimizing the code loop based on a standalone loop-invariant anchor input having a value of zero.

6. A method as recited in claim 1, wherein generating the second optimized version of the code loop includes optimizing the code loop based on a clustered loop-invariant anchor input having a value of zero.

7. A method as recited in claim 1, wherein generating the second optimized version of the code loop includes optimizing the code loop based on a clustered loop-variant anchor input having a value of zero.

8. A method as recited in claim 1, further comprising:

generating code annotations based on a standalone loop-variant anchor input having a value of zero, wherein the processor is configured to process instructions within the code loop according to the code annotations.

9. A method as recited in claim 8, wherein the code annotations direct the processor to skip execution of at least one instruction of the plurality of instructions when the loop-variant anchor input has a value of zero.

10. A method as recited in claim 8, wherein generating the code annotations includes storing to a cache:

the code annotations; and

an indication of conditions under which the instructions within the code loop can be safely processed according to the code annotations.

11. A method as recited in claim 10, wherein generating the code annotations further includes maintaining in the cache, a mapping between the code loop and the code annotations.

12. A device comprising:

a processor, wherein the processor includes a loop optimizer, the loop optimizer configured to;

identify a code loop being processed by the processor; and

generate, based on a condition that a first input has a value of zero and is stored in a cache line that includes at least one non-zero value,

a first optimized code corresponding to the code loop;

generate, based on a condition that a second input has a value of zero and is clustered with other zero values in a cache line, a second optimized code corresponding to the code loop;

a cache system communicatively coupled to the processor, the cache system including;

an instruction cache for storing the code loop; and

a zero optimized cache for storing the first and second optimized code.

13. A device as recited in claim 12, wherein:

the first input is a loop-invariant input; and

the second input is a loop-variant input.

14. A device as recited in claim 12, wherein the cache system further includes a zero-optimized table for storing:

a mapping between the code loop and the first and second optimized code; and

an indication of the condition.

15. A device as recited in claim 14, wherein the processor is further configured to:

fetch an instruction from the instruction cache;

examine the zero-optimized table to determine that the instruction is mapped to the first or second optimized code;

examine the zero-optimized table to determine that the condition is met; and

in response to determining that the instruction is mapped to the first or second optimized code and the condition is met, execute the first or second optimized code.

16. A processor configured to process instructions according to a processor pipeline, wherein the processor pipeline comprises:

a stage to fetch an instruction from a memory;

a stage to execute the instruction; and

a loop optimizer configured to;

detect a code loop that includes a zero-optimizable instruction;

generate, based on a first condition that a first input has a value of zero and is stored in a cache line that includes at least one non-zero value, a first optimized code corresponding to the code loop; and

generate, based on a second condition that a second input has a value of zero and is clustered with other zero values in a cache line, a second optimized code corresponding to the code loop.

17. A processor as recited in claim 16, wherein the processor pipeline further comprises:

an optimized code fetcher to fetch the first or second optimized code loop when an instruction to be fetched corresponds to the code loop and the first or second condition is met, respectively.