def-usetype1
DUAtype7DUAtype8DUAtype9DUAtype10DUAtype11DUAtype12
def-usetype3
DUADUADUADUADUADUA
typetypetypetypetypetype
192021222324
Table4:Def-useassociations,withtheirtypes,thatoccurinprogramSum.
Def-useassociation(1,8a,sum1)
type2
(3,8a,j)
type3
(8a,8a,sum2)
type3
(12,16,k)
type1
(17,19,q)
(14,20,i)
type1
(19,21,sum)
(9,10a,j)
type7
(14,15,i)
type1
(8a,8a,sum1)
type14
(9,5,j)
type1
(3,4,i)
type3
(6,8a,p)
type14
Typetype2
Def-useassociation(2,8a,sum2)
type3
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
ninetypes—inwhicheitherthede nitionortheuseisnotde nite—intoonetype,whichtheycallveryweakdef-useassociation.
3.4Computationofdef-useassociations
Tocomputethedi erenttypesofdef-useassociationsidenti edintheprevioussection,wemodifybothstepsofthetraditionalalgorithmforcomputingdef-useassociations:(1)thecomputationofreachingde nitionsusingdata- owequations,and(2)thecomputationofthedef-useassociationsusingthereachingde nitions.Topropagateadditionalinformationandcomputesolutionsateachnodethatfacilitatetheidenti cationofeachofthe24typesofdef-useassociations,weextendthereaching-de nitioncomputationintwoways.First,unlikethetraditionalalgorithm,themodi edalgorithmcomputestwosetsofreachingde nitionsateachnode—oneforthosede nitionsthatde nitelyreachthenode,andtheotherforthosede nitionsthatpossiblyreachthenode.Second,unlikethetraditionalalgorithm,whichdoesnotpropagatekilledde nitions,themodi edalgorithmalsopropagatesthekilledde nitionsandcomputes,ateachnode,thesetofde nitionsthatarekilledalongapathtothatnode.Thus,ateachnode,themodi edalgorithmcomputesasolutionthatcomprisesthreesetsofreachingde nitions:thede nitereachingde nitions,thepossiblereachingde nitions,andthekilledreachingde nitions.
Figure5presentsthemodi edalgorithmforcomputingreachingde nitions.Theoverallstructureofthemodi edalgorithmisthethesameasthatofthetraditionalalgorithm.Thealgorithmevaluatesasetofdata- owequationsateachnode,andpropagatesthesolutionsoftheequationstothesuccessorsofthenodeintheCFG;thealgorithmperformsthesestepsiterativelyuntilthesolutionsateachnodeconverge.Todistinguishde nitereachingde nitionsfrompossiblereachingde nitions,thealgorithmreceivesasinputtwotypesofkillinformationforeachnode:KILLd(n)containsthede nitionsthatarede nitelykilledatnoden,whereasKILLp(n)containsthosede nitionsthatarepossiblykilledatnoden.ThealgorithmalsoassociatesthreeseparateINandOUTsetswitheachnode,oneseteachforde nitereachingde nitions,possiblereachingde nitions,andkilledreachingde nitions.Thealgorithmmanipulateseachofthesesetsinasimilarway.First,algorithmcomputestheINsetsatanodenbymergingtherespectiveOUTsetsofallpredecessorsofn(lines6,9,and12).Next,thealgorithmsavesthecurrentvaluesoftheOUTsetsatnodenpriortocomputingthenewvaluesforthosesets(lines7,10,and13).Finally,thealgorithmcomputesnewvaluesfortheOUTsetsatnodenusingthefollowingequations:
OUTd(n)=GEN(n)∪(INd(n) KILLd(n) KILLp(n))(line8);itcontainsthosede nitionsthateitheraregeneratedatnoden,orde nitelyreachtheentryofnodenandareneitherde nitelykillednorpossiblykilledatnoden.
OUTp(n)=(INp(n) KILLd(n))∪(INd(n)∩KILLp(n))(line11);itcontains(1)de nitionsthatei-therpossiblyreachtheentryofnandarenotde nitelykilledatn,and(2)de nitionsthatde nitelyreachtheentryofnandarepossiblykilledatn.
OUTk(n)=INk(n)∪(INd(n)∪INp(n)∩KILLd(n))(line14);itcontains(1)thosekilledde nitionsthatreachtheentryofn,and(2)thosede nitionsthatde nitelyorpossiblyreachtheentryofnandarede nitelykilledatn.
IfthevalueofanyOUTsetatnodenchanges,thealgorithmsetsthe agchange(lines15–16),whichcausesthenodesintheCFGtobeprocessedagain.ThealgorithmterminateswhentheOUTsetsateach
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.12.13.14.15.16.17.18.19.
algorithmComputeReachingDefsinputCFGcontrol- owgraphforprogram
GEN(n)setofde nitionsthataregeneratedatnoden
setofde nitionsthatarede nitelykilledatnodenKILLd(n)
KILLp(n)setofde nitionsthatarepossiblykilledatnoden
outputINd(n)setofde nitionsthatde nitelyreachnoden
setofde nitionsthatde nitelyreachtheendofnodenOUTd(n)
INp(n)setofde nitionsthatpossiblyreachnodenOUTp(n)setofde nitionsthatpossiblyreachtheendofnodenINk(n)setofkilledde nitionsthatreachnoden
setofkilledde nitionsthatreachtheendofnodenOUTk(n)
declarechange agtoindicateifthevalueofanOUTd(n),OUTp(n),orOUTk(n)changedfrom
apreviousiteration
oldoutdvalueofOUTd(n)fromthepreviousiterationoldoutpvalueofOUTp(n)fromthepreviousiteration