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,