System, method, and computer program product for removing a synchronization statement

• US 8,438,554 B1
• Filed: 12/11/2008
• Issued: 05/07/2013
• Est. Priority Date: 12/11/2008
• Status: Active Grant

• Current Assignee: NVIDIA Corporation
• Original Assignee: NVIDIA Corporation
• Inventors: Grover, Vinod Kumar, Stratton, John
• Primary Examiner(s): Dao, Thuy
• Assistant Examiner(s): Chowdhury, Ziaul A
• Application Number:
  US12/333,241
• Time in Patent Office: 1,608 Days
• Field of Search: None
• US Class Current: 717/154
• CPC Class Codes: G06F 8/4441 Reducing the execution time required by the program code
• CPC Class Codes: G06F 8/458 Synchronisation, e.g. post-wait, barriers, locks synchronisation among tasks G06F9/52

Abstract

A system, method, and computer program product are provided for removing a synchronization statement. In use, synchronization statements are identified. Additionally, the synchronization statements are analyzed. Furthermore, the synchronization statements are removed based on the analysis.

Claims

1. A method executed by a processor, the method comprising:

identifying a first synchronization statement included in program code;

traversing backwards from the first synchronization statement toward a beginning of the program code;

pushing each traversed statement of the program code onto a stack until a first occurrence of;

a second synchronization statement included in the program code is reached, and

the beginning of the program code is reached;

pushing the second synchronization statement onto the stack when the second synchronization statement is reached;

analyzing the stack; and

removing the first synchronization statement from the computer program based on the analysis of the stack, including;

removing first synchronization statement from the program code when;

it is determined that the second synchronization statement is included in the stack and it is determined that the first synchronization statement is redundant to the second synchronization statement.

2. A system, comprising:

a processor for;

identifying a first synchronization statement included in program code;

traversing backwards from the first synchronization statement toward a beginning of the program code;

pushing each traversed statement of the program code onto a stack until a first occurrence of;

a second synchronization statement included in the program code is reached, and

the beginning of the program code is reached;

pushing the second synchronization statement onto the stack when the second synchronization statement is reached;

analyzing the stack; and

removing the first synchronization statement from the computer program based on the analysis of the stack, including;

removing the first synchronization statement from the program code when;

it is determined that the second synchronization statement is included in the stack and it is determined that the first synchronization statement is redundant to the second synchronization statement.

3. The system of claim 2, wherein the processor remains in communication with memory and a display via a bus.

4. A computer program product embodied on a non-transitory computer readable medium, comprising:

computer code for identifying a first synchronization statement included in program code;

computer code for traversing backwards from the first synchronization statement toward a beginning of the program code;

computer code for pushing each traversed statement of the program code onto a stack until a first occurrence of;

a second synchronization statement included in the program code is reached, and

the beginning of the program code is reached;

computer code for pushing the second synchronization statement onto the stack when the second synchronization statement is reached;

computer code for analyzing the stack; and

computer code for removing the first synchronization statement from the computer program based on the analysis of the stack, including;

removing the first synchronization statement from the program code when;

it is determined that the second synchronization statement is included in the stack and it is determined that the first synchronization statement is redundant to the second synchronization statement.

5. The computer program product of claim 4, wherein the first and second synchronization statements constrain an ordering of operations in a multithreaded portion of the computer program.

6. The computer program product of claim 4, wherein identifying the first synchronization statement includes determining a plurality of properties of the first synchronization statement.

7. The computer program product of claim 6, wherein identifying the first synchronization statement further includes matching the plurality of properties of the first synchronization statement to properties predetermined to be indicative of synchronization statements.

8. The computer program product of claim 4, further including computer code for determining whether each of the first and second synchronization statements constrains a plurality of shared memory accesses.

9. The computer program product of claim 8, wherein determining whether each of the first and second synchronization statements constrains a plurality of shared memory accesses includes determining whether a first shared memory access exists prior to the synchronization statement and whether a second shared memory access exists after the synchronization statement.

10. The computer program product of claim 8, wherein determining whether each of the first and second synchronization statements constrains a plurality of shared memory accesses includes determining whether a program path exists with a first shared memory access before the synchronization statement and a second shared memory access after the synchronization statement, and without another synchronization statement between the first shared memory access and the second shared memory access.

11. The computer program product of claim 4, wherein the first synchronization statement is redundant with respect to the second synchronization statement if the first synchronization statement does not add any additional constraints on shared memory accesses beyond constraints on the shared memory accesses provided by the second synchronization statement.

12. The computer program product of claim 4, wherein traversing backwards from the first synchronization statement toward the beginning of the program code includes traversing backwards through a basic block of code immediately preceding the first synchronization statement to identify the second synchronization statement.

13. The computer program product of claim 12, further comprising determining and storing a state of the basic block of code.

14. The computer program product of claim 13, wherein the state stored for the basic block of code indicates whether a synchronization statement that constrains the basic block of code is redundant.

15. The computer program product of claim 4, wherein the first synchronization statement is redundant to the second synchronization statement and removed if it is determined that the first synchronization statement does not add any additional constraints on shared memory accesses beyond constraints on the shared memory accesses provided by the second synchronization statement.

16. The computer program product of claim 4, wherein each of the first and second synchronization statements is removed if it is determined that a first shared memory access does not exist immediately prior to the synchronization statement or a second shared memory access does not exist immediately after the synchronization statement.

17. The computer program product of claim 4, further comprising flagging the first synchronization statement based on the analysis.

18. The computer program product of claim 17, wherein the flag indicates whether to remove the first synchronization statement.

19. The computer program product of claim 4, the analyzing and the removing are performed by a compiler.

20. The computer program product of claim 4, wherein the second synchronization statement is a last statement pushed onto the stack.

21. The computer program product of claim 4, further including:

popping the second synchronization statement from the stack;

marking the second synchronization statement as visited;

after popping the second synchronization statement from the stack, determining that the stack is empty; and

in response to determining that the stack is empty, determining that the first synchronization statement is redundant with respect to the second synchronization statement.