Control flow analysis using deductive reaching definitions

1. A computer-implemented process for deductive reaching definition analysis, the computer-implemented process comprising:

a computer receiving a control flow graph to form a set of received blocks and edges;

the computer performing traditional reaching definitions to produce bit-vectors OUT(b), GEN(b) and KILL(b) for each block in the set of received blocks;

the computer receiving impossibility indicators for a set of definitions that are impossible on specific edges;

the computer performing deduction operations using a combination of the bit-vectors and impossibility indicators to deduce that additional definitions cannot reach certain blocks to create resulting reachability information;

wherein combining the bit-vectors with the impossibility indicators further comprises:

producing bit-matrices composed of bits representing reachability implications between pairs of definitions;

performing a dataflow analysis operation that modifies the bit-matrices using the bit-vectors and impossibility indicators;

computing a main diagonal of each of the bit-matrices to form the resulting reachability information; and

the computer providing the resulting reachability information as a result to a requestor.

2. The computer-implemented process of claim 1 , wherein the dataflow analysis operation further comprises:

initializing a bit-matrix for each block, wherein, for each block b, a matrix OUT.sub.d(b) is initialized to OUT(b) ; and

analyzing each bit-matrix by performing a modification of the bit-matrices until a determination is made that the analysis has completed.

3. The computer-implemented process of claim 2 , wherein the dataflow analysis operation further comprises a deduction operation comprising:

identifying two variables R and C such that a row of OUT d (b) corresponding to R contains no bits set for any definition of C corresponding to a column of OUT d (b); and

clearing a row and column of OUT d (b) corresponding to R.

4. The computer-implemented process of claim 2 , wherein the dataflow analysis operation further comprises a generator operation comprising:

computing SURV d (b) as the main diagonal of IN d (b)−KILL(b) ⊕ ; and

updating OUT d (b) by a union operation to include all bits from GEN(b) GEN(b), GEN(b) SURV(b), and SURV(b) GEN(b).

5. The computer-implemented process of claim 2 , wherein the modification comprises:

computing IN d (b) as a union of OUT d (p) matrices from all predecessor blocks p of blocks b with rows and columns cleared in accordance with received impossibility indicators for an edge from all predecessor blocks p of blocks b; and

computing OUT d (b) as IN d (b)−KILL(b) ⊕ , clearing additional bits of OUT d (b) by a deduction operation, and setting additional bits for any pair of definitions that could be simultaneously active at an end of the block.

6. The computer-implemented process of claim 5 , wherein the deduction operation comprises:

identifying definitions whose corresponding columns in IN d (b)−KILL(b) ⊕ have no bits set in a row; and

clearing all bits in the row and a corresponding column.

7. A computer program product for deductive reaching definition analysis, the computer program product comprising:

a computer readable recordable-type storage media containing computer executable program code stored thereon, the computer executable program code comprising:

computer executable program code for receiving a control flow graph to form a set of received blocks and edges;

computer executable program code for performing traditional reaching definitions to produce bit-vectors OUT(b), GEN(b) and KILL(b) for each block in the set of received blocks;

computer executable program code for receiving impossibility indicators for a set of definitions that are impossible on specific edges;

computer executable program code for performing deduction operations using a combination of the bit-vectors and impossibility indicators to deduce that additional definitions cannot reach certain blocks to create resulting reachability information;

wherein computer executable program code for combining the bit-vectors with the impossibility indicators further comprises:

computer executable program code for producing bit-matrices composed of bits representing reachability implications between pairs of definitions;

computer executable program code for performing a dataflow analysis operation that modifies the bit-matrices using the bit-vectors and impossibility indicators;

computer executable program code for computing a main diagonal of each of the bit-matrices to form the resulting reachability information; and

computer executable program code for providing the resulting reachability information as a result to a requestor.

8. The computer program product of claim 7 , wherein computer executable program code for performing the dataflow analysis operation further comprises:

computer executable program code for initializing a bit-matrix for each block, wherein, for each block b, a matrix OUT.sub.d(b) is initialized to OUT(b) , and computer executable program code for analyzing each bit-matrix by performing a modification of the bit-matrices until a determination is made that the analysis has completed.

9. The computer program product of claim 8 , wherein computer executable program code for the dataflow analysis operation further comprises a deduction operation comprising:

computer executable program code for identifying two variables R and C such that a row of OUT d (b) corresponding to R contains no bits set for any definition of C corresponding to a column of OUT d (b); and

computer executable program code for clearing a row and column of OUT d (b) corresponding to R.

10. The computer program product of claim 8 , wherein computer executable program code for the dataflow analysis operation further comprises computer executable program code for a generator operation comprising:

computer executable program code for computing SURV d (b) as the main diagonal of IN d (b)−KILL(b) ⊕ ; and

computer executable program code for updating OUT d (b) by a union operation to include all bits from GEN(b) GEN(b), GEN(b) SURV(b), and SURV(b) GEN(b).

11. The computer program product of claim 8 , wherein computer executable program code for the modification comprises:

computer executable program code for computing IN d (b) as a union of OUT d (p) matrices from all predecessor blocks p of blocks b with rows and columns cleared in accordance with received impossibility indicators for the edge from all predecessor blocks p of blocks b; and

computer executable program code for computing OUT d (b) as IN d (b)−KILL(b) ⊕ , clearing additional bits of OUT d (b) by a deduction operation, and setting additional bits for any pair of definitions that could be simultaneously active at the end of the block.

12. The computer program product of claim 11 , wherein computer executable program code for the deduction operation comprises:

computer executable program code for identifying definitions whose corresponding columns in IN d (b)−KILL(b) ⊕ have no bits set in a row; and

computer executable program code for clearing all bits in the row and a corresponding column.

13. An apparatus for deductive reaching definition analysis, the apparatus comprising:

a communications fabric;

a memory connected to the communications fabric, wherein the memory contains computer executable program code;

a communications unit connected to the communications fabric; an input/output unit connected to the communications fabric; a display connected to the communications fabric; and

a processor unit connected to the communications fabric, wherein the processor unit executes the computer executable program code to direct the apparatus to: receive a control flow graph to form a set of received blocks and edges;

perform traditional reaching definitions to produce bit-vectors OUT(b), GEN(b) and KILL(b) for each block in the set of received blocks;

receive impossibility indicators for a set of definitions that are impossible on specific edges;

perform deduction operations using a combination of the bit-vectors and impossibility indicators to deduce that additional definitions cannot reach certain blocks to create resulting reachability information;

wherein the processor unit further executes the computer executable program code to combine the bit-vectors with the impossibility indicators to direct the apparatus to:

produce bit-matrices composed of bits representing reachability implications between pairs of definitions;

perform a dataflow analysis operation that modifies the bit-matrices using the bit-vectors and impossibility indicators;

compute a main diagonal of each of the bit-matrices to form the resulting reachability information; and

provide the resulting reachability information as a result to a requestor.

14. The apparatus of claim 13 , wherein the processor unit further executes the computer executable program code to perform the dataflow analysis operation to direct the apparatus to:

initialize a bit-matrix for each block, wherein, for each block b, a matrix OUT.sub.d(b) is initialized to OUT(b) ; and

analyze each bit-matrix by performing a modification of the bit-matrices until a determination is made that the analysis has completed.

15. The apparatus of claim 14 , wherein the processor unit further executes the computer executable program code to perform the dataflow analysis operation further comprising a deduction operation to direct the apparatus to:

identify two variables R and C such that a row of OUT d (b) corresponding to R contains no bits set for any definition of C corresponding to a column of OUT d (b); and

clear a row and column of OUT d (b) corresponding to R.

16. The apparatus of claim 14 , wherein the processor unit further executes the computer executable program code to perform the dataflow analysis operation further comprising a generator operation to direct the apparatus to:

compute SURV d (b) as the main diagonal of IN d (b)−KILL(b) ⊕ ; and

update OUT d (b) by a union operation to include all bits from GEN(b) GEN(b), GEN(b) SURV(b), and SURV(b) GEN(b).

17. The apparatus of claim 13 , wherein the processor unit further executes the computer executable program code to perform the data flow analysis operation comprising a modification to direct the apparatus to:

compute IN d (b) as a union of OUT d (p) matrices from all predecessor blocks p of blocks b with rows and columns cleared in accordance with received impossibility indicators for an edge from all predecessor blocks p of blocks b; and

compute OUT d (b) as IN d (b)−KILL(b) ⊕ , clearing additional bits of OUT d (b) by a deduction operation, and setting additional bits for any pair of definitions that could be simultaneously active at an end of the block.