Effects of Pointers on Data Dependences

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

TechnicalReportGIT-CC-00-33,December2000

E ectsofPointersonDataDependences

AlessandroOrso,SaurabhSinha,andMaryJeanHarrold

CollegeofComputing

GeorgiaInstituteofTechnology

801AtlanticDriveAtlanta,GA30332

{orso,sinha,harrold}@cc.gatech.edu

Abstract

Datadependences,whichrelatestatementsthatcomputedatavaluestostatementsthatusethosevalues,areusefulforautomatingavarietyofprogram-comprehension-relatedactivities,suchasreverseengineering,impactanalysis,anddebugging.Unfortunately,datadependencesaredi culttocomputeandunderstandinthepresenceofcommonly-usedlanguagefeaturessuchaspointers,arrays,andstruc-tures.Tofacilitatethecomprehensionofdatadependencesinprogramsthatusesuchfeatures,wede neatechniqueforcomputingandclassifyingdatadependencesthattakesintoaccountthecomplexitiesintroducedbyspeci clanguageconstructs.Theclassi cationthatwepresentis ner-grainedthanprevi-ouslyproposedclassi cation.Moreover,unlikepreviouswork,wepresentempiricalresultsthatillustratethedistributionofdatadependencesforasetofCsubjects.Wealsopresentapotentialapplicationfortheproposedclassi cation:programslicing.Weproposeatechniquethatallowsforcomputingslicesbasedondata-dependencetypes.Thistechniquefacilitatestheuseofslicingforunderstandingapro-grambecauseausercaneitherincrementallyaugmentaslicebyincorporatingdatadependencesbasedontheirrelevance,orfocusonspeci ckindsofdependences.Finally,wepresentacasestudythatshowshowtheincrementalcomputationofslicescan(1)highlightsubtledatadependenceswithinaprogram,and(2)provideusefulinformationaboutthosedependences.

Keywords:Datadependences,pointeranalysis,programslicing,programcomprehension.

1Introduction

Understandingdatadependenceswithinprogramsisaprerequisitetoseveralprogram-comprehensionre-latedactivities,suchasmaintenance,reuse,reengineering,anddebugging.Inparticular,slicingtechniques,whichareoftenusedinthecontextofprogramunderstanding,highlydependontheavailabilityofreliableinformationaboutdependencesamongprogramvariables.Suchdependencescanbeidenti edbycomputingde nition-use(def-use)associations,whichrelatestatementsthatassignvaluestovariablestostatementsthatusethosevalues.Theproblemofcomputingdef-useassociationsintheabsenceofpointersisrelativelystraightforward.Insuchacase,de nitionsandusesofvariablescanbeidenti edbyusingonlysyntacticinformation.Oncede nitionsandusesareknown,def-useassociationscanbecomputedusingatraditionaldata- owanalysisalgorithm[2].

Unfortunately,traditionalapproachesforcomputingdef-useassociationsareinadequateinthepresenceofprogramminglanguageconstructssuchaspointers,arrays,andstructures.Thepossibilityofdirectlyaccessingmemorylocations,inlanguagessuchasC,complicatestheidenti cationofde nitionsandusesinthecode.Forexample,avariablemaybeaccessedatagivenstatementwithoutsyntacticallyappearinginit,iftheaccessoccursthroughapointerdereference.Therefore,syntacticinformationisnotsu cientinthepresenceofpointers,andthesetofmemorylocationsthatcanbeaccessedthroughadereference

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

mustbedeterminedpriortothecomputationofdef-useassociations.Moreover,becauseanassignmentorusethroughthedereferenceofapointercanpotentiallyassignavalueto,orusethevalueof,oneofseveralvariables,theseindirectassignmentsandusesmustbetreateddi erentlyfromdirect(i.e.,syntactic)assignments.

Mostofthepreviousresearchthathasuseddef-useassociationsmakesconservative(safe)approximationsthataretoosimplisticand,therefore,canbeveryimprecise.Inthe rstpartofthispaper,weextendpreviouslypresentedclassi cationschemestoallowforamore ne-grainedtaxonomyofdef-useassociations.Inourscheme,adef-useassociationisclassi edintooneof24categories.Thisclassi cationisbasedonthekindofde nitionanduse—eitherde niteorpossible—inthedef-useassociation,andonthetypesofthepathsoccurringbetweensuchde nitionanduse.Inthisway,eachdef-useassociationcorrespondstoaspeci ckindofdatadependence.Weextendthetraditionalreaching-de nition-basedalgorithmtocomputeandclassifydef-useassociationsaccordingtoourclassi cationscheme.Wealsopresentanddiscussempiricalresults,forasetofCsubjects,aboutthedistributionofdef-useassociationsintothevariouscategories.Inthesecondpartofthepaper,wepresentsomepossibleapplicationsoftheproposedclassi cation.Inparticular,weevaluatethee ectsofclassifyingdatadependencesonprogramslicing:weintroduceaslicingparadigminwhichslicesarecomputedbyfollowingonlyspeci edtypesofdatadependences.Basedonthisparadigm,wepresentanincrementalslicingtechnique.Thetechniquecanstarttheanalysisofaprogrambycomputingslicesthatconsideronly“strong”(i.e.,de nite)datadependences,andthenaugmenttheslicesincrementallybyincorporatingadditional,“weaker,”datadependencesinane cientway.Thisslicingapproachletstheuser rstfocusonasmaller,andthuseasiertounderstand,subsetoftheprogram,andthenconsiderincreasinglybiggerpartsofthecode.Thetechniquealsoprovidesawaytoisolatethedatadependencesthatarecausedbythepresenceofpointers.Inthisway,itispossibletohighlightsubtledatadependencesthatcana ectthebehavioroftheprograminpossiblyunforeseenways,andprovideusefulinformationaboutthosedependences.Finally,thetechniqueo ersawayofcontrollingthesizeofaslicebyeliminatingcertaindatadependencesfromtheslices.Wealsopresentacasestudythatweperformedtoinvestigatethepracticalusabilityofthepresentedtechnique.Themaincontributionsofthepaperare:

A ne-grainedclassi cationofdata-dependencesforlanguages,suchasC,thatlettheprogrammerdirectlymanipulatememory.

Empiricalresultsthatillustratethedistributionofdatadependencesintovariouscategories. Anewslicingtechniquethatallowsforbuildingslicesbyconsideringonlyasubsetofdatadependences,basedontheirrelevance.

Acasestudythatshowstheresultsoftheapplicationoftheslicingtechniquetoarealexample.

2Background

Data- owanalysistechniquesrequirethecontrol- owrelationoftheprogrambeinganalyzed.This

Inthissection,wede nedatadependences.Wealsobrie ydescribealiasanalysesandprogramslicing.relationcanberepresentedasacontrol- owgraph.Acontrol- owgraph(CFG)containsnodes,whichrepresentstatements,andedges,whichrepresentpotential owofcontrolamongthestatements.Inaddition,

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

12

def={x} use={}def={y} use={}def={} use={x,y}

7

def={} use={y}

1 begin M2 read x3 read y

4 if x > y then5 read x6 print x else

8 print y endif9 end M

34

def={x} use={}def={} use={x}

56

8

Figure1:Sampleprogramtoillustratede nitions,uses,anddatadependences(above);control- owgraphfortheprogramannotatedwithdefandusesets(below).

CFGcanalsobebuiltatthebasic-blocklevel;insuchaCFG,eachnoderepresentsasequenceofsingle-entry,single-exit

statements.

1A

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.

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.

inti;main(){

int*p;

intj,sum1,sum2;sum1=0;sum2=0;readi,j;

while(i<10){

if(j<0){

p=&sum1;}

else{

p=&sum2;}

*p=add(j,*p);readj;}

sum1=add(j,sum1);printsum1,sum2;}

12.13.14.15.16.17.18.19.20.21.

intadd(intval,intsum){

int*q,k;readk;

if(sum>100){

i=9;}

sum=sum+i;if(i<k){

q=&val;}

else{

q=&k;}

sum=sum+*q;i=i+1;returnsum;}

Figure3:ProgramSum.

slicecanalsobecomputedintheforwarddirection:aforwardsliceincludesthosestatementsinPthatarein uenced

bythevaluesofthevariablesinVats.

2A

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

Figure4:Control- owgraphsforprogramSum(Figure2)withde niteandpossiblede nitionandusesetsateachnode.

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

Table1:Def-usetypesbasedonthetypesofde nitionsanduses.

De nitede nition

def-usetype3def-usetype4

Table2:Classi cationofΠ—pathsfromde nitionstouses—afterincorporatingtheoccurrencesofde nitekillingpaths.

BasetypeofΠallde nitedef-clear

π∈Π:πisde nitekilling

somede nitedef-clear

π∈Π:πisde nitekilling

allpossibledef-clear

π∈Π:πisde nitekilling

PRD-KDPRD-KExtendedtypeofΠ

DRD-K

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

Table3:Classi cationofdef-useassociations:24typesthatresultfromacrossproductofdef-usetypes(Table1)andthesecondalternativeforpathclassi cation(column3ofTable2).

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

valueofOUTk(n)fromthepreviousiterationoldoutk

beginComputeReachingDefs

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

change=false

foreachnoden∈CFGdo

/*compute INd(n),saveOUTd(n),andrecomputeOUTd(n)*/INd(n)=OUTd(p),wherepisapredecessorofnintheCFGoldoutd=OUTd(n)

OUTd(n)=GEN(n)∪(INd(n) KILLd(n) KILLp(n))/*compute INp(n),saveOUTp(n),andrecomputeOUTp(n)*/INp(n)=OUTp(p),wherepisapredecessorofnintheCFGoldoutp=OUTp(n)

OUTp(n)=(INp(n) KILLd(n))∪(INd(n)∩KILLp(n))/*computeINk(n),saveOUTk(n),andrecomputeOUTk(n)*/ INk(n)=OUTk(p),wherepisapredecessorofnintheCFGoldoutk=OUTk(n)

OUTk(n)=INk(n)∪(INd(n)∪INp(n)∩KILLd(n))

ifoldout=OUT(n)oroldout=OUT(n)oroldout=OUT(n)then

change=trueendifendforendwhile

endComputeReachingDefs

Figure5:Thealgorithmforcomputingreachingde nitionstoidentifydef-useassociationsofdi erenttypes.

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

Table5:Programsusedfortheempiricalstudiesreportedinthepaper.

Subjectansitape

Benchmarkprogram

di

Compress/extractutility

replacetotunzip

Antenna-arrayspeci cationparserStatisticalinformationcombiner

2906

5511530LOC1106

100percentage of total def useassociations

806040200Figure6:Distributionofdatadependencesusingourclassi cationandOstrandandWeyuker’sclassi cation.

3In

twoofthesubjects,twocallsinvolvingfunctionpointershavebeensubstitutedwithcallshavingthesamedata- ow

e ect.

ty 1pety 3pe ty5pe ty6pe ty7pety 9pe ty10pe ty13pe ty14pety 15pety 17pe ty19pe ty20pe ty22pe st23rongwveeryak weak

ty

pe

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

correspondstoadata-dependencetypeandrepresentsthepercentageofdata-dependencesforthattype.Thedatainthe gureillustratesthatdatadependencesfallpredominantlyintoonlythreetypes.Duatype1,duatype3,andduatype20occurmostfrequently:togetherthesetypesaccountforover98%ofthetotaldatadependences.Oftheremaining21typesofdatadependences,12typesoccurinmarginalnumbersandaccountfortheremaining2%ofthedatadependences.Theremaining9typesofdatadependencesdonotoccurinthesubjects;suchtypesarenotlistedalongthehorizontalaxisinFigure6.

Theresultsofthisstudyarepreliminaryinnature.AlthoughthedatainFigure6showstrendsinthedistributionofdata-dependencetypes,thescarcityofthedatapoints,preventsusfromdrawinganyconclu-sionsaboutthedistribution.Furtherexperimentationwithmoreandpersesubjectswillhelpdetermineiftrends,suchasthefrequentoccurrenceofduatype20,persist.Thedatainthe gureshowsthatforover30%ofthedatadependences,nopathfromthede nitiontotheusecontainsarede nitionoftherelevantvariable.Thisresultisimportantbecauseitmeansthat,forthesedatadependences,statementcoverageguaranteesthecoverageofthecorrespondentdef-useassociations.

ThelastthreebarsinFigure6showthedistributionofdata-dependencetypesaccordingtoOstrandandWeyuker’sclassi cation[19].Accordingtotheirclassi cation,over88%ofthedatadependencesarestrong,andover11%ofthedatadependencesareveryweak.Theremaining1%ofthedatadependencesareweak;nodatadependenceis rm.

4ApplicationsoftheData-DependenceClassi cation

Theabilitytoclassifydatadependencescanbeexploitedfordi erentapplications.Forexample,datadependencesthatareorderedbasedontheir“strength”canguideadata- owtestingstrategy[9],canbeusedtoperformimpactanalysesfocusedondi erentkindsofdependences,andcanbeanalyzedtoidentifypartsofthecodewherepossiblyunforeseendatadependencesrequirecarefulsoftwareinspections.Inshort,allactivitiesthatdependondata-dependenceinformationcanutilizesuchaclassi cation.Inthispaper,wefocusonanapplicationthatisrelatedtoprogramunderstanding—programslicing.Inthefollowingsection,wede neaslicingtechniquethatletsuscomputeslicesbasedondata-dependencetypes;wealsoillustrateacasestudyinwhichweapplythetechnique.

4.1Programslicing

Traditionalslicingtechniques(e.g.[12,14,27])includeinthesliceallstatementsthata ecttheslicingcriteriathroughdirectortransitivecontrolanddatadependences.Suchtechniquescomputetheslicebycomputingthetransitiveclosureofallcontrolandalldatadependencesstartingattheslicingcriterion.Theclassi cationofdatadependencesintodi erenttypesleadstoanewparadigmforslicing,inwhichthetransitiveclosureisperformedoveronlythespeci edtypesofdatadependences,ratherthanoveralldatadependences.Inthisslicingparadigm,aslicingcriterionisatriple<s,V,T>,wheresisaprogrampoint,Visasetofprogramvariablesreferencedats,andTidenti esoneormoretypesofdatadependences.Thesliceincludesthosestatementsthatmaya ectthevalueofthevariablesinVatsthroughtransitivecontrolorspeci edtypesofdatadependences.

Usingthenewslicingparadigm,wede neaslicingtechniquethatincreasesthescopeofasliceincre-mentallybyincludingdatadependencesofdi erenttypes.Thetechniquestartsbyconsideringthestronger

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

percentage of slices

percent ofstatements

in slice

(0, 20](20, 40]

(40, 60]

1

2

e

e

ic

ic

sl

sl

slice 3

Figure7:Increaseinthesizesoftheslicesforunzipbyincorporatingdi erenttypesofdatadependencesintotheslices.

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

Althoughthedi erencesintheslicesizesbetweenthe rsttwosetsarenotcausedbecauseofthepresenceofpointers4,thedi erencesthemselvesaresigni cant.Thus,theincrementalslicingapproachappearspromisinginreducingthesizesofslices.Thedi erencesinthesizesoftheslicesbetweenthesecondandthirdsetsarenotsigni cant.However,thesedi erencesarecausedbecauseofthee ectsofpointers.Weexaminedmanuallythedi erencesinsomeoftheslicesandfoundthattheslicesinthethirdsetincludedstatementsthatwererelatedbysubtle,hard-to-detectpointer-relateddatadependences.Thetechnique,thus,appearstobeusefulinisolatingandfocusingattentiononsuchdependences.Infuturework,weintendconductmoreextensiveempiricalstudiestoevaluatethee ectivenessoftheslicingtechnique.

5RelatedWork

OstrandandWeyuker[19]extendthetraditionaldata- owtestingtechniques[9,21]toprogramsthatcontainpointersandaliasing.Tode netestingcriteriathatadequatelytestthedata- owrelationshipsinprogramswithpointers,theyconsiderthee ectsofpointersandaliasingonde nitionsanduses.Theyclassifyde nitions,uses,anddef-clearpathsdependingontheoccurrencesofpointerdereferencesinthoseentities.Basedontheseclassi cations,theyidentifyfourtypesofdef-useassociations:strong, rm,weak,andveryweak.Thestrongdef-useassociationcorrespondstoduatypes1and3inourclassi cation;the rmdef-useassociationcorrespondstoduatypes2and4;theweakdef-useassociationcorrespondstoduatypes5and6;and nally,theveryweakdef-useassociationcorrespondstotheremaining18typesofdef-useassociationsinourscheme.Ourclassi cationis nergrained.OstrandandWeyuker’sclassi cationgroupsseveraltypesofdependencestogetherand,therefore,maymissthedistinctionsamongsuchdependences.Pande,Landi,andRyder[20]describeanalgorithmforcomputinginterproceduralreachingde nitionsinthepresenceofpointers.Theyusethemay-holdaliasrelationtogeneratede nitionsthatoccurthroughpointerdereferences;theyusethemust-holdaliasrelationtotogeneratekillsthatoccurthroughpointerdereferences.Theyde neconditionalreachingde nitionasareachingde nitionthatholdsundersomeassumedconditionsforaliasing,andpresentanalgorithmforcomputingconditionalreachingde nitions.Intheirwork,Pande,Landi,andRyderdonotconsiderclassi cationsofde nitionsanduses.Theyalsodonotincorporatethemay-aliasinformationingeneratingthekillinformation;therefore,theyalsodonotconsiderclassi cationofpathsfromde nitionstouses.

MerloandAntoniol[18]presenttechniquestoidentifydominancerelationsamongdef-useassociationsinthepresenceofpointers.Theyalsodistinguishde niteandpossiblede nitionsanduses.Basedonthesedistinctions,theyde netwotypesofdef-useassociations:(1)thede nitedef-useassociation,whichcorrespondstoduatypes1,2,3,and4inourclassi cation,and(2)thepossibledef-useassociation,whichcorrespondstotheremaining20typesofdef-useassociationsinourclassi cation.MerloandAntoniolusethetypesofdef-useassociationstode nedominancerelationsamongdef-useassociations.Thegoaloftheirwork,hovewer,isnottoclassifydef-useassociationsandinvestigatethesigni canceandimplicationsoftheclassi cation.

Severalresearchershaveconsideredthee ectsofpointersonprogramslicingandhavepresentedresultstoperformslicingmoree ectivelyinthepresenceofpointers(e.g.[1,4,6,7,17]).Someresearchershavealso

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

evaluatedthee ectsoftheprecisionofthepointeranalysisonsubsequentanalyses,suchasthecomputationofdef-useassociations(e.g.[25])andprogramslicing(e.g.[5,16,22]).Noneofthatresearch,however,distinguishesdef-useassociationsbasedonthetypesofde nitions,uses,anddef-useassociations—theyviewuniformlyeachdef-useassociationthatarisesinthepresenceofpointers.

Tonellaandcolleagues[26]analyzethee ectsoftheprecisionofthereaching-de nitioncomputationondef-useassociations,buttheydonotconsiderhowsuchprecisiona ectstheclassi cationofdef-useassociations.

Otherresearchers(e.g.[8,11])haveinvestigatedvariouswaystoreducethesizeofslices.However,theyhavenotconsideredclassifyingdatadependencesandcomputingslicesbasedondi erenttypesofdatadependencesasameansofreducingthesizeofslices.

6SummaryandFutureWork

Inthispaper,wepresentedatechniqueforcomputingandclassifyingdatadependencesinprogramsthatusepointers.Theclassi cationthatweproposeis nergrainedwithrespecttopreviouslypresentedclassi- cations,andallowsforapartitioningofdatadependencesinto24sets,basedontheir“strength.”Wealsopresentedthe rstsetofexperimentalresultsthatillustratesthedistributionofdatadependencesforasetofCsubjects.Althoughwecannotdrawanyconclusiveinference,thedatagatheredsofarshowtrendsthatareworthfurtherinvestigation.

Weillustratedapotentialapplicationoftheproposedclassi cationforprogramslicing.Ourslicingtechniqueletstheuser rstfocusonasmaller,thuseasiertounderstand,subsetoftheprogram,andthenconsiderincreasinglybiggerpartsofthecode.Wehavealsopresentedacasestudy,forwhichtheadditionof“weak”datadependencescausedonlyasmallgrowthofthesizeoftheslices,butisolatedandidenti edsubtledatadependenceswithintheprogram.

Wewillconductfurtherempiricalstudiestoevaluateboththedistributionofthedatadependencesandthee ectivenessoftheincrementalslicingtechnique.Ourfutureworkalsoincludestheextensionsofourprototypetouseadi erent,moree cient,kindofaliasanalysis.Thisimprovementwillallowus(1)toperformexperimentsonsubjectsofbiggersize,and(2)tostudytherelationbetweenthedistributionofdatadependencesandtheprecisionoftheunderlyingaliasanalysis.Wealsoplantoperformastudyofthesourcecodeofthesubjectstryingtoidentifypatternsinthatcodethatcancausespeci ctypesofdatadependences.Weareconvincedthatsuchpatternscouldbeofgreathelptotuneanalysisalgorithmsandprovideguidelinesfortheprogrammers.

Acknowledgments

ThisworkwassupportedinpartbyagrantfromBoeingCommercialAirplanestoGeorgiaTech,byNationalScienceFoundationawardsCCR-9707792,CCR-9988294,andCCR-0096321toGeorgiaTech,andbytheStateofGeorgiatoGeorgiaTechundertheYamacrawMission.

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

References

[1]H.Agrawal,R.A.DeMillo,andE.H.Spa ord.Dynamicslicinginthepresenceofunconstrained

pointers.InProceedingsofthesymposiumonTesting,Analysis,andVeri cation,pages60–73,Oct.1991.[2]A.V.Aho,R.Sethi,pilers,Principles,Techniques,andTools.Addison-Wesley

PublishingCompany,Reading,MA,1986.[3]L.O.Andersen.ProgramanalysisandspecializationfortheCprogramminglanguage.TechnicalReport

94-19,UniversityofCopenhagen,1994.[4]D.C.AtkinsonandW.G.Griswold.E ectivewhole-programanalysisinthepresenceofpointers.In

ProceedingsofACMSIGSOFTSixthInternationalSymposiumontheFoundationsofSoftwareEngi-neering,pages46–55,Nov.1998.[5]L.Bent,D.C.Atkinson,andW.G.Griswold.Acomparativestudyoftwowhole-programslicersfor

C.TechnicalReportUCSDTRCS2000-0643,UniversityofCaliforniaatSanDiego,May2000.[6]D.W.Binkley.Slicinginthepresenceofparameteraliasing.InSoftwareEngineeringResearchForum,

pages261–268,Nov.1993.[7]D.W.BinkleyandJ.R.Lyle.Applicationofthepointerstatesubgraphtostaticprogramslicing.The

JournalofSystemsandSoftware,40(1):17–27,Jan.1998.[8]G.Canfora,A.Cimitile,rmationandSoftware

Technology,40(11-12):595–608,November1998.Specialissueonprogramslicing.[9]P.G.FranklandE.J.Weyuker.Anapplicablefamilyofdata owtestingcriteria.IEEETrans.Softw.

Eng.,14(10):1483–1498,Oct.1988.[10]P.L.R.Group.PROLANGSAnalysisFramework.http://www.prolangs.rutgers.edu/,RutgersUni-versity,1998.[11]M.HarmanandS.Danicic.Amorphousprogramslicing.InProceedingsoftheFifthInternational

WorkshoponProgramComprehension.IEEEComputerSocietyPress,1997.[12]M.J.HarroldandN.Ci.Reuse-driveninterproceduralslicing.InProceedingsofthe20thInternational

ConferenceonSoftwareEngineering,pages74–83,Apr.1998.[13]M.J.HarroldandG.Rothermel.Aristotle:Asystemforresearchonanddevelopmentofprogram-analysis-basedtools.TechnicalReportOSU-CISRC-3/97-TR17,TheOhioStateUniversity,Mar.1997.[14]S.Horwitz,T.Reps,andD.Binkley.Interproceduralslicingusingdependencegraphs.ACMTrans.

ng.Syst.,12(1):26–60,Jan.1990.[15]ndiandB.G.Ryder.Asafeapproximatealgorithmforinterproceduralpointeraliasing.InPro-ceedingsoftheACMSIGPLAN’92ConferenceonProgrammingLanguageDesignandImplementation,pages235–248,June1992.[16]D.LiangandM.J.Harrold.E cientpoints-toanalysisforwhole-programanalysis.InProceedings

ofESEC/FSE’997thEuropeanSoftwareEngineeringConferenceand7thACMSIGSOFTSymposiumontheFoundationsofSoftwareEngineering,volume1687ofLectureNotesinComputerScience,pages199–215.Springer-Verlag,Sept.1999.[17]D.LiangandM.J.Harrold.Reuse-driveninterproceduralslicinginthepresenceofpointersand

recursion.InProceedingsoftheInternationalConferenceonSoftwareMaintenance,pages421–432,August–September1999.[18]E.MerloandG.Altoniol.Pointersensitivedef-usepre-dominance,post-dominanceandsyn-chronousdominancerelationsforunconstraineddef-useintraproceduralcomputation.TechnicalReportEPM/RT-00/01,EcolePolytechniqueofMontreal,Mar.2000.[19]T.J.OstrandandE.J.Weyuker.Data ow-basedtestadequacyanalysisforlanguageswithpointers.

InProceedingsoftheSymposiumonTesting,Analysis,andVeri cation,pages74–86,Oct.1991.

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

[20]H.Pande,ndi,andB.G.Ryder.Interproceduraldef-useassociationsforCsystemswithsingle

levelpointers.IEEETrans.Softw.Eng.,20(5):385–403,May1994.[21]S.RappsandE.J.Weyuker.Selectingsoftwaretestdatausingdata owinformation.IEEETrans.

Softw.Eng.,SE-11(4):367–375,Apr.1985.[22]M.ShapiroandS.Horwitz.Thee ectsoftheprecisionofpointeranalysis.In4thInternationalStatic

AnalysisSymposium,volume1302ofLectureNotesinComputerScience,pages16–34,Sept.1997.[23]S.Sinha,M.J.Harrold,andG.Rothermel.System-dependence-graph-basedslicingofprogramswith

arbitraryinterproceduralcontrol ow.InProceedingsofthe21stInternationalConferenceonSoftwareEngineering,pages432–441,May1999.[24]B.Steensgaard.Points-toanalysisinalmostlineartime.InConferenceRecordofthe23rdACM

SymposiumonPrinciplesofProgrammingLanguages,pages32–41,Jan.1996.[25]P.Tonella.E ectsofdi erent owinsensitivepoints-toanalysesonDEF/USEsets.InProceedingsof

the3rdEuropeanConferenceonSoftwareMaintenanceandReengineering,pages62–69,Mar.1999.[26]P.Tonella,G.Antoniol,R.Fiutem,andE.Merlo.Variableprecisionreachingde nitionsanalysis.

JournalofSoftwareMaintenance:ResearchandPractice,11(2):117–142,March–April1999.[27]M.Weiser.Programslicing.IEEETrans.Softw.Eng.,10(4):352–357,July1984.

本文来源：https://www.bwwdw.com/article/t7iq.html