Data dependences, which relate statements that compute data values to statements that use those values, are useful for automating a variety of program-comprehension-related activities, such as reverse engineering, impact analysis, and debugging. Unfortunat

1.2.3.4.5.6.7.8.9.10.11.

algorithmComputeReachingDefsinputCFGcontrol- owgraphforprogram

GEN(n)setofde nitionsthataregeneratedatnodenKILL(n)setofde nitionsthatarekilledatnoden

outputIN(n)setofde nitionsthatreachnoden

OUT(n)setofde nitionsthatreachtheendofnoden

declarechange agtoindicateifthevalueofanOUT(n)changedfromapreviousiteration

oldoutvalueofOUT(n)fromthepreviousiteration

beginComputeReachingDefs

foreachnoden∈CFGdoOUT(n)=GEN(n)endforchange=truewhilechangedo

change=falseforeachnoden∈CFGdo

OUT(p),wherepisapredecessorofnintheCFGIN(n)=

oldout=OUT(n)

OUT(n)=GEN(n)∪(IN(n) KILL(n))

ifoldout=OUT(n)thenchange=trueendifendforendwhile

endComputeReachingDefs

Figure2:Thealgorithmforcomputingreachingde nitions.