Patent ID: 8566801

Claim:
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.