Patent ID: 8615748

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