Method and apparatus for loop-invariant instruction detection and elimination

1. A method implemented in a hardware processor, the method comprising:

setting a loop-invariant bit for each entry in a register alias table in response to detecting a loop start, wherein each entry in the register alias table corresponds to a register;

executing first N iterations of the loop and for any register that is modified during the first N iterations of the loop, responsively clearing the loop-invariant bit of the modified register's corresponding entry in the register alias table;

identifying one or more loop-invariant registers, wherein a given register is loop-invariant if the given register's corresponding entry in the register alias table has the loop-invariant bit still set after the first N iterations of the loop.

2. The method of claim 1 , further comprises

tracking accesses to a plurality of cache addresses in a processor cache;

maintaining a counter for each of the plurality of cache addresses accessed by one or more load instructions and responsively incrementing the counter of an accessed cache address each time the accessed cache address is accessed by the one or more load instructions;

locking the counter of any cache address that is modified by a first store instruction or a first remote snoop;

determining whether a given cache address is loop-invariant based on the counter.

3. The method of claim 2 , wherein the given cache address is loop-invariant if the counter of the given cache address is equal to or greater than a predetermined threshold and not loop-invariant if the counter of the given cache address is locked.

4. The method of claim 3 , further comprises identifying one or more loop-invariant instructions inside the loop, wherein a given loop instruction loop-invariant if the given loop instruction is an arithmetic instruction comprised of only operands that are from loop-invariant registers, or if the given loop instruction is a load instruction that comprises of only operands stored in loop-invariant registers and is accessing only loop-invariant cache addresses.

5. The method of claim 4 , further comprises identifying a destination register for each of the one or more identified loop-invariant instructions inside the loop and responsively setting the loop-invariant bit for each identified destination register's entry in the register alias table.

6. The method of claim 3 , further comprises initiating corrective actions responsive to detecting a loop-invariant cache address being modified by a second store instruction or a second remote snoop.

7. The method of claim 6 , wherein the corrective actions comprise flushing an instruction pipeline.

8. The method of claim 6 , wherein the corrective actions comprise terminating the loop.

9. An apparatus comprising:

a loop-detecting circuit to detect loops and upon detecting a loop start, responsively cause the setting of loop-invariant bit for each entry in a register alias table, wherein each entry in the register alias table corresponds to a register;

an execution circuit to execute first N iterations of a detected loop and for any register that is modified during the first N iterations of the detected loop, responsively cause the clearing of the loop-invariant bit of the modified register's corresponding entry in the register alias table;

a loop-invariant register detecting circuit to identify one or more loop-invariant registers, wherein a given register is loop-invariant if the given register's corresponding entry in the register alias table has the loop-invariant bit still set after the first N iterations of the detected loop.

10. The apparatus of claim 9 , further comprises:

a memory guard circuit to:

track accesses to a plurality of cache addresses in a processor cache;

maintain a counter for each of the plurality of cache addresses accessed by one or more load instructions and responsively incrementing the counter of an accessed cache address each time the accessed cache address is accessed by the one or more load instructions;

lock the counter of any cache address that is modified by a first store instruction or a first remote snoop; and

determine whether a given cache address is loop-invariant based on the counter.

11. The apparatus of claim 10 , wherein the given cache address is loop-invariant if the counter of the given cache address is equal to or greater than a predetermined threshold and not loop-invariant if the counter of the given cache address is locked.

12. The apparatus of claim 11 , further comprises a loop-invariant instruction detection circuit to identify one or more loop-invariant instructions inside the loop, wherein a given loop instruction is a loop invariant if the given loop instruction is an arithmetic instruction comprised of only operands that are from the loop-invariant registers, or if the given loop instruction is a load instruction that comprises of only operands stored in loop-invariant registers and is accessing only loop-invariant cache addresses.

13. The apparatus of claim 12 , further comprises a loop-invariant instruction propagation circuit to identify a destination register for each of the one or more identified loop-invariant instructions inside the loop and responsively setting the loop-invariant bit for each identified destination register's entry in the register alias table.

14. The apparatus of claim 11 , wherein the memory guard circuit to initiate corrective actions responsive to detecting a loop-invariant cache address being modified by a second store instruction or second remote snoop.

15. The apparatus of claim 14 , wherein the corrective actions comprise flushing an instruction pipeline.

16. The apparatus of claim 14 , wherein the corrective actions comprise terminating the loop.