Use-define chain - Wikipedia

A Use-Definition Chain (UD Chain) is a data structure that consists of a use, U, of a variable, and all the definitions, D, of that variable that can reach ... Use-definechain FromWikipedia,thefreeencyclopedia Jumptonavigation Jumptosearch Datastructurethattracksvariableuseanddefinitions AUse-DefinitionChain(UDChain)isadatastructurethatconsistsofause,U,ofavariable,andallthedefinitions,D,ofthatvariablethatcanreachthatusewithoutanyotherinterveningdefinitions.AUDChaingenerallymeanstheassignmentofsomevaluetoavariable. AcounterpartofaUDChainisaDefinition-UseChain(DUChain),whichconsistsofadefinition,D,ofavariableandalltheuses,U,reachablefromthatdefinitionwithoutanyotherinterveningdefinitions. BothUDandDUchainsarecreatedbyusingaformofstaticcodeanalysisknownasdataflowanalysis.Knowingtheuse-defanddef-usechainsforaprogramorsubprogramisaprerequisiteformanycompileroptimizations,includingconstantpropagationandcommonsubexpressionelimination. Contents 1Purpose 2Setup 2.1DefinitionofaVariable 2.2UseofaVariable 3Execution 4Executionexamplefordef-use-chain 5Methodofbuildingause-def(orud)chain Purpose[edit] Makingtheuse-defineordefine-usechainsisastepinlivenessanalysis,sothatlogicalrepresentationsofallthevariablescanbeidentifiedandtrackedthroughthecode. Considerthefollowingsnippetofcode: intx=0;/*A*/ x=x+y;/*B*/ /*1,someusesofx*/ x=35;/*C*/ /*2,somemoreusesofx*/ Noticethatxisassignedavalueatthreepoints(markedA,B,andC).However,atthepointmarked"1",theuse-defchainforxshouldindicatethatitscurrentvaluemusthavecomefromlineB(anditsvalueatlineBmusthavecomefromlineA).Contrariwise,atthepointmarked"2",theuse-defchainforxindicatesthatitscurrentvaluemusthavecomefromlineC.Sincethevalueofthexinblock2doesnotdependonanydefinitionsinblock1orearlier,xmightaswellbeadifferentvariablethere;practicallyspeaking,itisadifferentvariable—callitx2. intx=0;/*A*/ x=x+y;/*B*/ /*1,someusesofx*/ intx2=35;/*C*/ /*2,someusesofx2*/ Theprocessofsplittingxintotwoseparatevariablesiscalledliverangesplitting.Seealsostaticsingleassignmentform. Setup[edit] Thelistofstatementsdeterminesastrongorderamongstatements. Statementsarelabeledusingthefollowingconventions: s ( i ) {\displaystyles(i)} ,whereiisanintegerin [ 1 , n ] {\displaystyle[1,n]} ;andnisthenumberofstatementsinthebasicblock Variablesareidentifiedinitalic(e.g.,v,uandt) Everyvariableisassumedtohaveadefinitioninthecontextorscope.(Instaticsingleassignmentform,use-definechainsareexplicitbecauseeachchaincontainsasingleelement.) Foravariable,suchasv,itsdeclarationisidentifiedasV(italiccapitalletter),andforshort,itsdeclarationisidentifiedas s ( 0 ) {\displaystyles(0)} .Ingeneral,adeclarationofavariablecanbeinanouterscope(e.g.,aglobalvariable). DefinitionofaVariable[edit] Whenavariable,v,isontheLHSofanassignmentstatement,suchas s ( j ) {\displaystyles(j)} ,then s ( j ) {\displaystyles(j)} isadefinitionofv.Everyvariable(v)hasatleastonedefinitionbyitsdeclaration(V)(orinitialization). UseofaVariable[edit] Ifvariable,v,isontheRHSofstatement s ( j ) {\displaystyles(j)} ,thereisastatement, s ( i ) {\displaystyles(i)} withid) c=c-d; else d=d-c; } returnc; } Tofindoutalldef-use-chainsforvariabled,dothefollowingsteps: Searchforthefirsttimethevariableisdefined(writeaccess). Inthiscaseitis"d=b"(l.7) Searchforthefirsttimethevariableisread. Inthiscaseitis"returnd" Writedownthisinformationinthefollowingstyle:[nameofthevariableyouarecreatingadef-use-chainfor,theconcretewriteaccess,theconcretereadaccess] Inthiscaseitis:[d,d=b,returnd] Repeatthesestepsinthefollowingstyle:combineeachwriteaccesswitheachreadaccess(butNOTtheotherwayround). Theresultshouldbe: [d,d=b,returnd] [d,d=b,while(d!=0)] [d,d=b,if(c>d)] [d,d=b,c=c-d] [d,d=b,d=d-c] [d,d=d-c,while(d!=0)] [d,d=d-c,if(c>d)] [d,d=d-c,c=c-d] [d,d=d-c,d=d-c] Youhavetotakecare,ifthevariableischangedbythetime. Forexample:Fromline7downtoline13inthesourcecode,disnotredefined/changed. Atline14,dcouldberedefined.Thisiswhyyouhavetorecombinethiswriteaccessondwithallpossiblereadaccesseswhichcouldbereached. Inthiscase,onlythecodebeyondline10isrelevant.Line7,forexample,cannotbereachedagain.Foryourunderstanding,youcanimagine2differentvariablesd: [d1,d1=b,returnd1] [d1,d1=b,while(d1!=0)] [d1,d1=b,if(c>d1)] [d1,d1=b,c=c-d1] [d1,d1=b,d1=d1-c] [d2,d2=d2-c,while(d2!=0)] [d2,d2=d2-c,if(c>d2)] [d2,d2=d2-c,c=c-d2] [d2,d2=d2-c,d2=d2-c] Asaresult,youcouldgetsomethinglikethis.Thevariabled1wouldbereplacedbyb /** *@param(a,b)Thevaluesusedtocalculatethedivisor. *@returnThegreatestcommondivisorofaandb. **/ intgcd(inta,intb){ intc=a; intd; if(c==0) returnb; if(b!=0){ if(c>b){ c=c-b; d=b; } else d=b-c; while(d!=0){ if(c>d) c=c-d; else d=d-c; } } returnc; } Methodofbuildingause-def(orud)chain[edit] Thissectionmaybeconfusingoruncleartoreaders.Pleasehelpclarifythesection.Theremightbeadiscussionaboutthisonthetalkpage.(January2007)(Learnhowandwhentoremovethistemplatemessage) Setdefinitionsinstatement s ( 0 ) {\displaystyles(0)} Foreachiin [ 1 , n ] {\displaystyle[1,n]} ,findlivedefinitionsthathaveuseinstatement s ( i ) {\displaystyles(i)} Makealinkamongdefinitionsanduses Setthestatement s ( i ) {\displaystyles(i)} ,asdefinitionstatement Killpreviousdefinitions Withthisalgorithm,twothingsareaccomplished: Adirectedacyclicgraph(DAG)iscreatedonthevariableusesanddefinitions.TheDAGspecifiesadatadependencyamongassignmentstatements,aswellasapartialorder(thereforeparallelismamongstatements). Whenstatement s ( i ) {\displaystyles(i)} isreached,thereisalistoflivevariableassignments.Ifonlyoneassignmentislive,forexample,constantpropagationmightbeused. vteCompileroptimizationsBasicblock Peepholeoptimization Loopoptimization Inductionvariable Strengthreduction Loopfusion Loopinversion Loopinterchange Loop-invariantcodemotion Loopnestoptimization Loopunrolling Loopsplitting Loopunswitching Softwarepipelining Automaticparallelization Data-flowanalysis Commonsubexpressionelimination Constantfolding Inductionvariablerecognitionandelimination Deadstoreelimination Use-definechain Livevariableanalysis Availableexpression SSA-based Globalvaluenumbering Sparseconditionalconstantpropagation Codegeneration Registerallocation Instructionselection Instructionscheduling Rematerialization Functional Tailcallelimination Deforestation Global Interproceduraloptimization Other Bounds-checkingelimination Compile-timefunctionexecution Deadcodeelimination Inlineexpansion Jumpthreading Profile-guidedoptimization Staticanalysis Aliasanalysis Pointeranalysis Shapeanalysis Escapeanalysis Arrayaccessanalysis Dependenceanalysis Controlflowanalysis Data-flowanalysis Retrievedfrom"https://en.wikipedia.org/w/index.php?title=Use-define_chain&oldid=1029984363" Categories:CompileroptimizationsProgramanalysisHiddencategories:ArticleswithshortdescriptionShortdescriptionmatchesWikidataWikipediaarticlesneedingclarificationfromJanuary2007AllWikipediaarticlesneedingclarification Navigationmenu Personaltools NotloggedinTalkContributionsCreateaccountLogin Namespaces ArticleTalk Variants expanded collapsed Views ReadEditViewhistory More expanded collapsed Search Navigation MainpageContentsCurrenteventsRandomarticleAboutWikipediaContactusDonate Contribute HelpLearntoeditCommunityportalRecentchangesUploadfile Tools WhatlinkshereRelatedchangesUploadfileSpecialpagesPermanentlinkPageinformationCitethispageWikidataitem Print/export DownloadasPDFPrintableversion Languages DeutschفارسیРусский Editlinks