Concurrent static single assignment for general barrier synchronized parallel programs

1. A method for generating concurrent static single assignment (CSSA), wherein the method comprises:

generating a clocked control flow graph of a program;

for each thread of the program created through async instruction, determining each part of the program that can execute concurrently with each thread to create a pair comprising a thread and a parallel program part;

for each pair that can execute concurrently, using one or more flow equations to perform node-by-node matching via:

computing a closest common ancestor for each node in the thread of the pair and a node in the parallel program part, wherein said closest common ancestor comprises a node that it is closest to both the node in the thread and the node in the parallel program part;

generating a graph for the thread and a graph for the parallel program part of the pair, wherein the graph for the thread comprises all paths from the closest common ancestor to the node in the thread and from the node in the thread to a conclusion point, and wherein the graph for the parallel program part comprises all paths from the closest common ancestor to the node in the parallel program part and from the node in the parallel program part to a conclusion point;

matching nodes in the graph for the thread and the graph for the parallel program part; and

using the node-by-node matching to generate CSSA form for the program, wherein said CSSA form improves (i) precision of intermediate representation for computing global value numbering and (ii) at least one of (a) partial redundancy elimination, (b) common sub-expression elimination and (c) loop invariant detection.

2. The method of claim 1 , wherein generating a clocked control flow graph of a program comprises generating a clocked control flow graph for one or more general barrier operations within a program.

3. The method of claim 2 , wherein generating a clocked control flow graph for one or more general barrier operations within a program comprises using clock and finish operations.

4. The method of claim 1 , further comprising computing May-Happen-in-Parallel (MHP) analysis for the program, wherein computing May-Happen-in-Parallel (MHP) analysis for the program comprises performing node-by-node matching to compute node-level MHP information that accounts for one or more barriers.

5. The method of claim 1 , wherein performing node-by-node matching comprises for each node n taken from an async, using the dataflow analysis to compute a Parallel(n) set of nodes belonging to the a parallel program part such that each of one or more nodes of the parallel program part excluded from Parallel(n) either precede or succeed n in time and cannot occur in parallel with n.

6. The method of claim 1 , wherein each node has attribute sets in, parallel and next that increase monotonically as dataflow analysis proceeds to reaching a fix-point once all sets stop increasing.

7. The method of claim 6 , wherein when the dataflow analysis reaches a fix-point once all sets stop increasing, node-by-node matching halts with a parallel attribute for each node n being an answer Parallel(n) for the node.

8. The method of claim 1 , further comprising at least one of discovering one or more potential data races and analyzing one or more systolic techniques.

9. A computer program product comprising a tangible non-transitory computer readable recordable storage device including computer useable program code for generating concurrent static single assignment (CSSA), the computer program product including:

computer useable program code for generating a clocked control flow graph of a program;

computer useable program code for, for each thread of the program created through async instruction, determining each part of the program that can execute concurrently with each thread to create a pair comprising a thread and a parallel program part;

computer useable program code for, for each pair that can execute concurrently, using one or more flow equations to perform node-by-node matching via:

computing a closest common ancestor for each node in the thread of the pair and a node in the parallel program part, wherein said closest common ancestor comprises a node that it is closest to both the node in the thread and the node in the parallel program part;

generating a graph for the thread and a graph for the parallel program part of the pair, wherein the graph for the thread comprises all paths from the closest common ancestor to the node in the thread and from the node in the thread to a conclusion point, and wherein the graph for the parallel program part comprises all paths from the closest common ancestor to the node in the parallel program part and from the node in the parallel program part to a conclusion point;

matching nodes in the graph for the thread and the graph for the parallel program part; and

computer useable program code for using the node-by-node matching to generate CSSA form for the program, wherein said CSSA form improves (i) precision of intermediate representation for computing global value numbering and (ii) at least one of (a) partial redundancy elimination, (b) common sub-expression elimination and (c) loop invariant detection.

10. The computer program product comprising a tangible non-transitory computer readable recordable storage device of claim 9 , wherein the computer useable program code for generating a clocked control flow graph of a program comprises computer useable program code for generating a clocked control flow graph for one or more general barrier operations within a program.

11. The computer program product comprising a tangible non-transitory computer readable recordable storage device of claim 10 , wherein the computer useable program code for generating a clocked control flow graph for one or more general barrier operations within a program comprises computer useable program code for using clock and finish operations.

12. The computer program product comprising a tangible non-transitory computer readable recordable storage device of claim 9 , further comprising:

computer useable program code for computing May-Happen-in-Parallel (MHP) analysis for the program, wherein the computer useable program code for computing May-Happen-in-Parallel (MHP) analysis for the program comprises computer useable program code for performing node-by-node matching to compute node-level MHP information that accounts for one or more barriers.

13. The computer program product comprising a tangible non-transitory computer readable recordable storage device of claim 9 , wherein the computer useable program code for performing node-by-node matching comprises computer useable program code for, for each node n taken from an async, using the dataflow analysis to compute a Parallel(n) set of nodes belonging to the a parallel program part such that each of one or more nodes of the parallel program part excluded from Parallel(n) either precede or succeed n in time and cannot occur in parallel with n.

14. A system for generating concurrent static single assignment (CSSA), comprising:

a memory; and

at least one processor coupled to the memory and operative to:

generate a clocked control flow graph of a program;

for each thread of the program created through async instruction, determine each part of the program that can execute concurrently with each thread to create a pair comprising a thread and a parallel program part;

for each pair that can execute concurrently, use one or more flow equations to perform node-by-node matching via:

computing a closest common ancestor for each node in the thread of the pair and a node in the parallel program part, wherein said closest common ancestor comprises a node that it is closest to both the node in the thread and the node in the parallel program part;

generating a graph for the thread and a graph for the parallel program part of the pair, wherein the graph for the thread comprises all paths from the closest common ancestor to the node in the thread and from the node in the thread to a conclusion point, and wherein the graph for the parallel program part comprises all paths from the closest common ancestor to the node in the parallel program part and from the node in the parallel program part to a conclusion point;

matching nodes in the graph for the thread and the graph for the parallel program part; and

use the node-by-node matching to generate CSSA form for the program, wherein said CSSA form improves (i) precision of intermediate representation for computing global value numbering and (ii) at least one of (a) partial redundancy elimination, (b) common sub-expression elimination and (c) loop invariant detection.

15. The system of claim 14 , wherein the at least one processor coupled to the memory operative to generate a clocked control flow graph of a program is further operative to generate a clocked control flow graph for one or more general barrier operations within a program.

16. The system of claim 15 , wherein the at least one processor coupled to the memory operative to generate a clocked control flow graph for one or more general barrier operations within a program is further operative to use clock and finish operations.

17. The system of claim 14 , wherein the at least one processor coupled to the memory is further operative to:

compute May-Happen-in-Parallel (MHP) analysis for the program, wherein computing May-Happen-in-Parallel (MHP) analysis for the program comprises performing node-by-node matching to compute node-level MHP information that accounts for one or more barriers.

18. The system of claim 14 , wherein the at least one processor coupled to the memory operative to perform node-by-node matching is further operative to for each node n taken from an async, use the dataflow analysis to compute a Parallel(n) set of nodes belonging to the a parallel program part such that each of one or more nodes of the parallel program part excluded from Parallel(n) either precede or succeed n in time and cannot occur in parallel with n.