METHOD AND APPARATUS TO SCHEDULE STORE INSTRUCTIONS ACROSS ATOMIC REGIONS IN BINARY TRANSLATION

• US 20140282437A1
• Filed: 09/27/2012
• Published: 09/18/2014
• Est. Priority Date: 09/27/2012
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Ma, Guokai, Jin, Yihua, Li, Jianhui, Lavery, Daniel M.
• Granted Patent: US 9,141,362 B2
• Time in Patent Office: Days
• US Class Current: 717/136
• CPC Class Codes: G06F 8/52 Binary to binary
• CPC Class Codes: G06F 9/30 Arrangements for executing machine instructions, e.g. instruction decode for executing microinstructions G06F9/22
• CPC Class Codes: G06F 9/30065 Loop control instructions; iterative instructions, e.g. LOOP, REPEAT
• CPC Class Codes: G06F 9/3834 Maintaining memory consistency
• CPC Class Codes: G06F 9/3858 Result writeback, i.e. updating the architectural state or memory

Abstract

A method and system to support scheduling of memory store instructions across atomic regions in binary translation in a processing unit or processor. In one embodiment of the invention, the processing unit has a store buffer that allows store instructions to be issued in different order than the source binary program order but still retire in source binary program order. This facilitates a small atomic region that maps to each iteration of a source binary code and these atomic regions are joined together into a pipelined region. In one embodiment of the invention, the processing unit executes commit instruction(s) once every loop iteration instead of executing the commit instruction(s) once after the loop exit.

Claims

1. An apparatus comprising:

logic to perform binary translation of a code having a source binary program order, wherein one or more store instructions of the binary translated code are to be issued in a different order from the source binary program order of the one or more store instructions of the code, and wherein the one or more store instructions of the binary translated code are to be retired in the source binary program order.

2. The apparatus of claim 1, wherein each store instruction has a store offset indicator to indicate the source binary program order.

3. The apparatus of claim 2, wherein the code comprises one or more load instructions, wherein each load instruction has a load offset indicator, and wherein each store instruction is only visible to each load instruction if the store offset indicator of the store instruction is smaller or equal to the load offset indicator.

4. The apparatus of claim 3, wherein the code comprises one or more commit instructions, wherein each commit instruction has a count, and wherein each store instruction is only visible externally if the store offset indicator of the store instruction is smaller or equal to the count of an executed commit instruction.

5. The apparatus of claim 4, wherein the logic is further to execute the binary translated code by performing the following steps:

in response to the executed commit instruction, subtract the store offset indictor of each store instruction by the count if the store offset indicator is bigger than the count; and

in response to the executed commit instruction, subtract the load offset indictor of each load instruction by the count if the load offset indicator is bigger than the count.

6. The apparatus of claim 4, wherein the logic to perform the binary translation of the code having the source binary program order is to:

initialize a current store offset indicator to zero;

for each store instruction in the code,

increment the current store offset indicator by one; and

generate a corresponding store instruction with the current store offset indicator in the binary translated code;

for each load instruction in the code, generate a corresponding load instruction with the current store offset indicator in the binary translated code;

for each commit instruction in the code, generate a corresponding commit instruction with the count in the binary translated code, wherein the count is the number of store instructions between the corresponding commit instruction and a prior commit instruction of the corresponding commit instruction or between the corresponding commit instruction and a beginning of the code if the corresponding commit instruction is a first commit instruction in the code; and

for each other instruction that is not a store, load or commit instruction, generate the other instruction.

7. The apparatus of claim 6, wherein the logic to perform the binary translation of the code having the source binary program order is further to:

for all store and load instructions in the code that are reordered backwards from a first location in the source binary program order to a second location in the binary translated code,

increment the store offset indicator of each store instruction with a sum of the counts of all commit instructions that are located between the first location in the source binary program order and the second location in the binary translated code; and

increment the load offset indicator of each load instruction with a sum of the counts of all commit instructions that are located between the first location in the source binary program order and the second location in the binary translated code.

8. The apparatus of claim 6, wherein the logic to perform the binary translation of the code having the source binary program order is further to:

for all store and load instructions in the code that are reordered forwards from a first location in the source binary program order to a second location in the binary translated code,

decrement the store offset indicator of each store instruction with a sum of the counts of all commit instructions that are located between the first location in the source binary program order and the second location in the binary translated code;

decrement the load offset indicator of each load instruction with a sum of the counts of all commit instructions that are located between the first location in the source binary program order and the second location in the binary translated code; and

return an error in response to the decremented store offset indicator being less than or equal to zero and in response to the decremented load offset indicator being less than zero.

9. The apparatus of claim 4, wherein for a first and a second store instruction that are to be made visible externally based on the executed commit instruction, the first and the second store instructions are to be made visible externally at the same time as an atomic event or are to be made visible based on their respective store offset indicators.

10. A system comprising:

a memory; and

a processor having logic to perform binary translation of a code having a source binary program order, wherein one or more store instructions of the binary translated code are to be issued in a different order from the source binary program order of the one or more store instructions of the code, and wherein the one or more store instructions of the binary translated code are to be retired in the source binary program order.

11. The system of claim 10, wherein each store instruction has a store offset indicator to indicate the source binary program order.

12. The system of claim 11, wherein the code comprises one or more load instructions, wherein each load instruction has a load offset indicator, and wherein each store instruction is only visible to each load instruction if the store offset indicator of the store instruction is smaller or equal to the load offset indicator.

13. The system of claim 12, wherein the code comprises one or more commit instructions, wherein each commit instruction has a count, and wherein each store instruction is only visible externally if the store offset indicator of the store instruction is smaller or equal to the count of an executed commit instruction.

14. The system of claim 13, wherein the logic is further to execute the binary translated code by performing the following steps:

in response to the executed commit instruction, subtract the store offset indictor of each store instruction by the count if the store offset indicator is bigger than the count; and

in response to the executed commit instruction, subtract the load offset indictor of each load instruction by the count if the load offset indicator is bigger than the count.

15. The system of claim 13, wherein the logic to perform the binary translation of the code having the source binary program order is to:

initialize a current store offset indicator to zero;

for each store instruction in the code,

increment the current store offset indicator by one; and

generate a corresponding store instruction with the current store offset indicator in the binary translated code;

for each load instruction in the code, generate a corresponding load instruction with the current store offset indicator in the binary translated code;

for each commit instruction in the code, generate a corresponding commit instruction with the count in the binary translated code, wherein the count is the number of store instructions between the corresponding commit instruction and a prior commit instruction of the corresponding commit instruction or between the corresponding commit instruction and a beginning of the code if the corresponding commit instruction is a first commit instruction in the code; and

for each other instruction that is not a store, load or commit instruction, generate the other instruction.

16. The system of claim 15, wherein the logic to perform the binary translation of the code having the source binary program order is further to:

for all store and load instructions in the code that are reordered backwards from a first location in the source binary program order to a second location in the binary translated code,

increment the store offset indicator of each store instruction with a sum of the counts of all commit instructions that are located between the first location in the source binary program order and the second location in the binary translated code; and

increment the load offset indicator of each load instruction with a sum of the counts of all commit instructions that are located between the first location in the source binary program order and the second location in the binary translated code.

17. The system of claim 16, wherein the logic to perform the binary translation of the code having the source binary program order is further to:

for all store and load instructions in the code that are reordered forwards from a first location in the source binary program order to a second location in the binary translated code,

decrement the store offset indicator of each store instruction with a sum of the counts of all commit instructions that are located between the first location in the source binary program order and the second location in the binary translated code;

decrement the load offset indicator of each load instruction with a sum of the counts of all commit instructions that are located between the first location in the source binary program order and the second location in the binary translated code; and

return an error in response to the decremented store offset indicator being less than or equal to zero and in response to the decremented load offset indicator being less than zero.

18. The system of claim 13, wherein for a first and a second store instruction that are to be made visible externally based on the executed commit instruction, the first and the second store instructions are to be made visible externally at the same time as an atomic event or are to be made visible based on their respective store offset indicators.

19. A method comprising:

performing binary translation of a code having a source binary program order, wherein one or more store instructions of the binary translated code are to be issued in a different order from the source binary program order of the one or more store instructions of the code, and wherein the one or more store instructions of the binary translated code are to be retired in the source binary program order.

20. The method of claim 19, wherein each store instruction has a store offset indicator to indicate the source binary program order.

21. The method of claim 20, wherein the code comprises one or more load instructions, wherein each load instruction has a load offset indicator, and wherein each store instruction is only visible to each load instruction if the store offset indicator of the store instruction is smaller or equal to the load offset indicator.

22. The method of claim 21, wherein the code comprises one or more commit instructions, wherein each commit instruction has a count, and wherein each store instruction is only visible externally if the store offset indicator of the store instruction is smaller or equal to the count of an executed commit instruction.

24. The method of claim 22, wherein performing the binary translation of the code having the source binary program order comprises:

initializing a current store offset indicator to zero;

for each store instruction in the code,

incrementing the current store offset indicator by one; and

generating a corresponding store instruction with the current store offset indicator in the binary translated code;

for each load instruction in the code, generating a corresponding load instruction with the current store offset indicator in the binary translated code;

for each commit instruction in the code, generating a corresponding commit instruction with the count in the binary translated code, wherein the count is the number of store instructions between the corresponding commit instruction and a prior commit instruction of the corresponding commit instruction or between the corresponding commit instruction and a beginning of the code if the corresponding commit instruction is a first commit instruction in the code; and

for each other instruction that is not a store, load or commit instruction, generating the other instruction.

25. The method of claim 24, wherein performing the binary translation of the code having the source binary program order comprises:

for all store and load instructions in the code that are reordered backwards from a first location in the source binary program order to a second location in the binary translated code,

incrementing the store offset indicator of each store instruction with a sum of the counts of all commit instructions that are located between the first location in the source binary program order and the second location in the binary translated code; and

incrementing the load offset indicator of each load instruction with a sum of the counts of all commit instructions that are located between the first location in the source binary program order and the second location in the binary translated code.

26. The method of claim 25, wherein performing the binary translation of the code having the source binary program order comprises:

for all store and load instructions in the code that are reordered forwards from a first location in the source binary program order to a second location in the binary translated code,

decrementing the store offset indicator of each store instruction with a sum of the counts of all commit instructions that are located between the first location in the source binary program order and the second location in the binary translated code;

decrementing the load offset indicator of each load instruction with a sum of the counts of all commit instructions that are located between the first location in the source binary program order and the second location in the binary translated code; and

returning an error in response to the decremented store offset indicator being less than or equal to zero and in response to the decremented load offset indicator being less than zero.

27. The method of claim 22, wherein for a first and a second store instruction that are to be made visible externally based on the executed commit instruction, the first and the second store instructions are to be made visible externally at the same time as an atomic event or are to be made visible based on their respective store offset indicators.

23. The method of 22, wherein the method further comprises executing the binary translated code by performing the following steps:

subtracting the store offset indictor of each store instruction by the count if the store offset indicator is bigger than the count in response to the executed commit instruction; and

subtracting the load offset indictor of each load instruction by the count if the load offset indicator is bigger than the count in response to the executed commit instruction.