69Chapter4SolutionTechniquesTheprecedingchapterdemonstratedmanydifficultieswithdebuggingoptimizedprograms.Thischapterdescribestechniquesforsolvingsomeofthesedifficulties:firstthebasictechniquesthatareusefulinprovidingeithertruthfulorexpectedbehavior,thenthetechniquesthatsupportonlytruthfulbehavior,andfinallythetechniquesthatsupportonlyexpectedbehavior.Therearetwoideasunderlyingthebasictechniques.First,optimizationsremoveinformationfromtheunoptimizedprogramincreatingtheoptimizedversion.Thisinformationcanbesavedduringcompilationorexecution,eithertopresenttheuserwiththeeffectsoftheoptimizations(truthfulbehavior)ortoreconstructanunoptimizedviewoftheoptimizedprogram'sexecution(expectedbehavior).Second,optimizationsordebuggingcanbelimitedinsomewaytomakethepresentationorreconstructionjobeasier.Thetechniquesthatsupporttruthfulbehaviorhelptheusertounderstandtheeffectsoftheoptimizationsandtomanipulatetheoptimizedcomputationintermsoftheunoptimizedsourcetext.Incontrast,thetechniquesthatsupportexpectedbehaviorhelpthedebuggertotranslatebetweentheuser'sviewoftheunoptimizedprogramandtheactualoptimizedcomputation.Thischapterpresentsawiderangeofideasandsuggestionsfordebuggingoptimizedprograms.AfewoftheseideasweretestedintheNavigatorimplementationdescribedinthesecondpartofthisdissertation.Theremainderhavenotbeentested;someareextensionsofideassuggestedinpreviousdiscussionsofdebuggingoptimizedprograms,whileothersarenewtothiswork.4.1BasictechniquesThebasictechniques,whichcanbeusedtoprovideeithertruthfulorexpectedbehavior,includeaddingstaticinformation,whichthecompilercollectsandpassestothedebugger;addingpg/MqV'A0P3!+| rI! 3 (, 37=DF  #&0*.0Y3 ;=>#@D D" $)*069<4 CEAQ$&v -R0 5,8F>= $'T* 2o6 >Cd :R "U$ )L+2*7; BE*G#88p  #')x.j03759>?Bq 5w %' /3H5"7>.D2  !0 )+e246;3<@hC9DH/ s !k#,^ xV#r(.Z1368 ?BfFH) }Q #c%,i 46L:4< > F&V #&+17:=lCEj$Qz! )/b24x8{> w"&(P+.S 5l7>1DpY,#&$'7- 7~=?ZAFPI5 #P&)#,147 =?wCI@@q x1#*V04v8:=?B+sD r [ $ &(,c.H37<>D t E r" #'*+/47;=?tF G7ITVm$iCHAPTER4:SOLUTIONTECHNIQUES70dynamicinformation,whichthedebuggercollectsduringtheprogram'sexecution;restrictingoptimizationtoallowmoreintelligibledebugging;restrictingdebuggingcapabilitiestoallowmoreextensiveoptimization;andrecompiling(small)portionsoftheprogramtoturnoffoptimizations.4.1.1AddingstaticinformationStaticinformationiscollectedbythecompilerduringthesymboltableconstruction,codegeneration,andoptimizationphasesandissavedforthedebugger'slateruse.Staticinformationshouldbeplacedinauxiliarytablesratherthanintheobjectcodeitself,sothattheoptimizedprogramcanexecuteatmaximumspeedandminimumspaceuntildebuggingisrequested(atruntime).Themostcrucialinformationforaninteractivesource-leveldebuggeristhecorrespondencebetweenvariablenamesspecifiedinthesourceprogramandstoragelocationsassignedtothesevariablesintheobjectprogram,aswellasthecorrespondencebetweensourcestatementsandobjectcodelocations.Withoutcorrectinformationofthiskind,whichcanonlybeprovidedbythecompiler,interactivesource-leveldebuggingisimpossible:whetherornotaprogramisoptimized,adebuggerthathasnonotionofitsvariableorprocedurenamesoritsstatementorderingcannotpresentintelligibleinformationabouttheexecutingprogram.Aconventionalcompilergivesthedebuggersimplesymboltablesandmonotonicallyincreasingstatementmaps,asidefromtheobjectcodeitself.Anoptimizingcompilermustconstructmuchmoresophisticatedsymboltablesandstatementmaps.Ifnoattemptismadetokeepthisinformationcurrentduringtheoptimizationprocess,thedebuggercannotcommunicateintelligiblywiththeprogrammerabouttheexecutingprogram.Thedebuggermighthavenonotionofprocedureorvariablenames,nodistinctionbetweencompilertemporariesanduservariables,andnoknowledgeofstatement(orevenprocedure)boundaries.Atbest,thedebuggercoulddisassembletheprogramintosomecorrespondingsource-levelrepresentationwitharbitrarychoicesofvariablenames.Giventheeffectsoftheoptimizationsandthevariablerenamingtogether,thiswouldbeaformidablepuzzle.Awidevarietyofstaticinformationcanbeusefultoadebugger.Fromsimplertomorecomplex,thisinformationincludessymboltables,statementmaps,globalflowgraphsandlocaldags,resultsofflowanalyses,andspecialtablesofinformationspecifictocertainoptimizations.Thecompilercanalsolaythegroundworkforthenexttechnique,addingdynamicinformation,byrg#*u$(gg%r)9gug)r+gug+rg1u2gg3mpgMtb& reb&b&!#*/F46= tDb&b&E _d r_do( & t-_d_d.p 4X: r_dACG[\ Ft\\ 'K+124r\:W<? A< vVd rR [$')/4/6;?P GO   %A()z-Q/2 8<%?Cd M3!%)-F/159G=!? ADJq^O%)+26j9@BjHGD  $9&( /a 7='>A% AYq-$ %(W,2w5N:!?EGe>F#%(*-& 7#<AI H7;n 1t";;#Qr;'J .03q7;3=AC H9  &./ 7{=$?CBCI6R @ #5%s*+. 3w5s<.@BD3Zd %j -*1C3::AB 0@ %W*7.<1 : @F.UO#q% ,285;t??B +LN '<Z}!%' /^4>8;< CLH$D ! (n+x- 59g;AH"4Pc"$+ ,2468 ?E3r }Qf "%h'.0`69  FHB4i&`*,j079=PABDl 1A( "L'6 .25%9;=BG|.h f &(T-0%2 9 ?A!ByD,$%T |"$*- 1^358?DI)bT-#$t')b)b(cr)b,2Y45E79P> CEuG&i #  #|'+j0S37 >ACI@ JZ< e$'Q-.3 9>Y?BGI.N !a')-n/48G;@B I*!]#(,4-0O594A I@ ?"(# 026;@EGO  E [!q#'w)4*b/ 6:<(B I* >/ K &*+- 5H8: 2TVm$CHAPTER4:SOLUTIONTECHNIQUES72Severalitemsspecifictootheroptimizationscanalsobeplacedintheaugmentedsymboltable.Forconstantpropagation,thesymboltablecanholdtheconstantvalueassociatedwithagivenvariable.Similarly,thesymboltablecanholdthevariablenameassociatedwithagivenvariableforcopypropagation.Forinductionvariableelimination,theinverseinductionfunctioncanbestoredinthetableentryfortheeliminatedinductionvariablesothatthedebuggercancomputethevalueoftheeliminatedvariablefromthesubstitutedvariablesondemand.Ingeneral,differentextrainformationmustbeassociatedwithdiferentsectionsoftheprogram(forexample,ifthesameloopindexisusedasadifferentinductionvariableformultipleloops)."Advising"asymboltableentryinthiswaycanalsoworkforobjectcodeoptimizations,suchascollapsedintegerarithmetic:thesymboltablecouldrecordthattheexpectedvalueofthevariableinacertainobjectcoderegionisequaltotheactualvalueplusarecordedconstant.Ifthedebuggerallowsvariablemodification,thesymboltablecouldalsocontaininformationforcheckingsecond-ordereffects.Inthetableentryforauservariable,theoptimizercouldstorepropertiesthatitassumedand/ordeducedaboutthatvariableinsidecertainobjectcoderanges.Forinstance,theoptimizermighthaveusedthefactthatthevalueofthevariablexwaseven,greaterthanzero,equaltoy,etc.asthepreconditionforalateroptimization.Whentheuserchangesthevalueofxfromthedebugger,thedebuggercouldthencheckanyapplicablepropertiesforxinthatprogramregiontoensurethattheresultingprogramissound.Thisinformationwouldneedtobestoredefficiently,asthereispotentiallyagreatdealofit.4.1.1.2AugmentedstatementmapsInformationtoallowmappingbetweensourcestatementsandobjectcodelocationscanbestoredinanaugmentedstatementmap.Somecontrol-flowoptimizationsforceonesourcestatementtohavemultiplecorrespondingsequencesofobjectcode(e.g.,inlineprocedureexpansion);othersforcemultiplesourcestatementstohaveonecorrespondingsequencesofobjectcode(e.g.,cross-jumping).Thesesimpleexamplesshowthatstatementmapsmustbeabletorepresentmany-to-oneandone-to-manyrelationships.Therefore,thesimplemonotonicallyincreasingstatementmapsgeneratedbyconventionalcompilersarenotsufficient.Aswasthecaseforsymboltables,mappingfromobjectlocationstosourcestatementscorrectlyatotherthanstatementboundaries(forexample,atthepointofaprogramexception)requiresthatevenmoreinformationbesaved.rg#*u$(gg%r)9gug)r+gug+rg1u2gg3mpgMrb)a b# ,R.1~3Y797;B|G/_g? Y!&*L,0J28[<& BEG:\ D"~%(+.&3e7. =@AEY6 J &O+ 3I5:@F[HW#C_ # )0+5r7F:$<BEHTa*^ S$r'* 068>}@5EIQx & &V).4)68>;AG HNTn-a &,91e39= EF&LJ. #').K1 :>:@FRI[  1#(-*-<268-:~?ADB^FF)lG#'S*M+v12C'$ -V/47;>Cd @B $9&(d+/\125;C=CG= rXo$/)-05:>BFH:k -$@'*-w0@3*59l;A=xC:r:DGP7iLx 7r7 !$&s( 1(348 A8EsG5<Bxy5<r5< "Z(*047;t= Dw 2zxJ2zr2z\!#(3+,-39@:@Cd /m 0 $&*++ 2f379;w*0W r& uI$*/ 58<@kFLH## F u &),r0728&!p%@+ 3 7:?D4  {%'+/2^<@DyWI"$')/ 7:u B @ y $ +#164:< D~X  @ "%',1P7-:>DF w+ $%*v 14t:`<>BGDE`   $ ,.TVm$CHAPTER4:SOLUTIONTECHNIQUES73Iftheoptimizerperformscode-reorderingoptimizations,suchascodemotionoutofloopsorlocalcode-reordering,thenthestatementmapmustrecordbothsyntacticandsemanticmappingsformovedstatements.RecallfromSection3.2.2.3thatthesyntacticmappingofamovedstatementisitsoriginallocation.Thisreflectsitspositionwithrespecttoothersurroundingstatementsandwithrespecttothedegreeofprogressthroughtheentirecomputation.Thesyntacticmappingisusefulforansweringquestionslike"Howmanytimesdoesexecutionreachthispointintheprogram?"[SeeSection2.2.2.]Ontheotherhand,thesemanticmappingofamovedstatementisitsnewlocation.Thisreflectsthepositionoftheactualcomputationsspecifiedbythestatement.Thesemanticmappingisusefulforreportingtheoffendingstatementataprogramexceptionandforansweringquestionslike"Whatisthevalueofvariablexbeforethisassignmenttox?"Toanswerthequestion"Whatisthevalueofvariablexafterthisassignmenttox?"formovedstatements,theoptimizermustalsoeitherrecordasemantic-afterobjectlocationorprovideasemanticversionofthenext-statementprimitive.Boththesyntacticandthesemanticdefinitionsofstatementmappingareuseful;neithercanbederivedfromtheother.Becauseonlytheusercanspecifywhichmappingshedesires,itfollowsthatadebuggercannotprovidecompletelyexpectedbehavior(inthesenseofcompletelymimickingthebehaviorofaconventionalcodebreakpoint-orienteddebugger)forprogramswhosestatementshavebeenreordered.Otherresearchershavenotnotedthedistinctionbetweennortherationalebehindthetwodifferentstatementmappingmethods.Hennessy,motivatedprimarilybythedesiretoreportthecausesofprogramexceptionscorrectly,providedonlythesemanticmapping,whilethedesignoftheFDSdebuggerincludedonlythesyntacticmapping.4.1.1.3OtherstaticinformationOtherinformationthatthecompilercouldcollectforthedebugger'slateruseincludestheprogram'sglobalflowgraph,theresultsofflowanalyses,specialtablesforparticularoptimizations,andcuesfordynamicinformationcollection.Thecompilercouldstoretheprogram'sentireglobalflowgraph.Ifthecompilerusesdagsforlocalcodegeneration,thedagswouldappearasbasicblocknodesintheflowgraph.Theflowgraphwouldalsocontainstatementmappinginformationandsymboltablepointers.Specialdebuggeralgorithmswouldprocesstheflowgraphatruntimetorespondtouserqueries.Hennessyusedaschemeofthissort.Hisaugmentedflowgraphanddagrepresentations,whichincludedobjectcodelocationinformation,encodedboththeoptimizedandtheunoptimizedformsoftherg#*u$(gg%r)9gug)r+gug+rg1u2gg3mpgMrb)(!+ 4a79D<ALCEI*_g1"(]+.3K6<4>D\ { ! $])'-_02b7=?3@HDYU7Ij %R'4,}/4O69 Av H7W# w^!#&+.K2C ;0>CITa<s"%*.15n;?BFHQuQQrQ"=$(D,.469;<AkGINh!&(*. 7@<>A& HLc"D(L*07?8:?EHI[#]$'+q-`xI[2r4I[I[5a9; C;xI[E=rFI[I[FHFA "A$(*xF0"t1FF2rF568 ?LxA,FrFBCFhC )"%)._/ 8=!BDIAZs & = v"I( .06<?CHc:I$'*(-/48=@ DF27! (.M358(;=C D 5<: !%1S7:@D4 2{1  '+9-14 :@CBE>/w[$)/6v<BDF,G[" ) /58;SAG:*6AJ#(+.$3w%@03 r! p c"(,1.36 =!@kCH\Hf ;"&(+1S59; B v $ ;%"A$+1/03e :<}>DGDL4 }" %[).k0F37;=@^ Hlx!`'-b 47<?F0 $o&-0.35}:i #)6,.5y8C: BFH PTVm$CHAPTER4:SOLUTIONTECHNIQUES74program.Formostlocaloptimizationsandsomeglobalones,thedebuggercouldprocessthisflowgraphtodiscoverwhetherornotthevalueofavariablewascurrent.Sometimesthedebuggercouldreconstructthecorrectvalueofthevariablefromtheflowgraph.Inconjunctionwiththeaugmentedsymboltablesdescribedearlier,suchflowgraphscouldhandlemoreoptimizationsthanHennessyconsidered[seeSection3.3.2],suchasconstantpropagationandregisterallocation.Unfortunately,theproblemofrepresentingtheeffectsoflaterobjectcodeoptimizationsbackintosuchflowgraphsremainsanopenresearcharea.Thecompilercouldrecordtheresultsofseveralkindsofprogramflowanalysis,suchasreachingdefinitions,availableexpressions,livevariables,andsoon[Aho+77].Incontrastwithstoringtheprogramflowgraphandprocessingitondemandatruntime,thisinformationrepresentspartiallyprecomputedanswerstoquestionsthatausermightaskthedebugger.(Ofcourse,thecompilercouldstoreboth.)Asidefromitslistsofvariablestoragelocationsinthesymboltable,theFDSsystemplannedtousestoredtablesofflowinformationasitsmajordebuggingassistance.Duringoptimization,thecompilerwouldrecordthemovement(asinsertionsanddeletions)ofassignmentsandusesofvariables.Itwouldthenpropagatethisinformationarounditsflowgraphtocreatelistsofassignmentsandusesofvariablesthat"chain"toeachvariableateachstatement.[Anoccurrenceofavariablevchainstoaprogramlocationpifthereisapathfromtheoccurrenceofvtop(ineitherdirection)thatdoesnotassignv.]Figure4-1showsthecompletelistoftablesthattheFDScompilerplannedtocollectforitsdebugger.Thecompilercouldalsorecordspecial-purposetablestoassistdebuggingforparticularoptimizations.Forexample,forinlineprocedureexpansion,thecompilercouldrecordthenameofeach"deleted"callsothatthedebuggercouldreinsertitintoitsproperplaceintheproceduretracebackwhennecessary.TheNavigatorsystem,describedinthesecondpartofthisdissertation,doesthis.Finally,thecompilercouldrecordcuesforthecollectionofdynamicinformation.Thesecueswouldtellthedebuggerwhatdebuggingactivityshouldtriggerinformationcollectionatruntime,whatinformationtocollect,andwhenandwheretocollectit.Thisinformationwillbedescribedfurtherinthenextsection.TheNavigatorcompilercollectssuchcues,calledpathdeterminers,tohelpdistinguishamongthemultiplesourcealternativesthatarisefromthecross-jumpingoptimization.rg#*u$(gg%r)9gug)r+gug+rg1u2gg3mpgMrb)re ( *.269+?\CPHM_gVJ!#?%'+-=.Y36;BD\ d! $&).a14U ;= E]HY$)Q,} 3}7C;?Q GW# uW#W#Q#r&fW#W#'+x-3 ;>DW Ta "~! )+0-159KIKI@uBvGHb/!$G *,).3\4:b< Dl EZ "#),.1"5/7:"A2CHC $'),.l38m>4?BZG.@C5y("2&H*(+. 6]79=Db = W$)(-017"9w ?B I5: x/) $y%*-F36I =BDl7M #K&A'-0{57;:i?A3Da y5<u5<5<bp i\y5<u54169z;e @yB]5<u5DD?HA rHaDDI@{ !', 4O7;U?;B  TVm$CHAPTER4:SOLUTIONTECHNIQUES75"Statementmap"informationStatementnumber_ObjectcodelocationStatementnumber_Statementtype,VariableStatementnumber_Listofimmediatesuccessors"Symboltable"informationVariable,Statementnumber_ListofstoragelocationsVariable_TypeinformationOptimizationinformationVariable,Statementnumber_UsesandassignmentsaddedordeletedthatchaintothatstatementVariable,Statementnumber_LivenessofvariableProcedure_ListofunreachablestatementsFigure4-1.RuntimedebuggingtablesprovidedbytheFDScompiler.4.1.2AddingdynamicinformationDynamicinformationiscollectedbythedebuggerduringtheprogram'sexecution.Thedebuggercancollectinformationabouttheorderinwhichthecomputationhastraversedcontrolflowpaths,oritcansaveoldvaluesofvariables.Thedebuggermightalsocollectstatementexecutioncountsordatausecounts,eitherselectivelyorwholesale,butthisinformationdoesnotaddressanyspecialproblemsofdebuggingoptimizedprograms.Dynamiccontrolflowinformationcanbeapowerfuladditiontostaticinformation.Ifthedebuggerhasaglobalflowgraphorresultsofflowanalysisanditalsocollectsdynamiccontrolflowinformation,itcanalwaysdeterminewhenthevaluesofvariablesareincorrectwithrespecttotheunoptimizedprogram.Forexample,supposethatcodemotionhasmovedaloop-invariantassignmenttothevariablexoutsidealoop.Iftheloophasbeenexecutedmorethanonce,thenxhasthecorrectvaluefortheremainderoftheloop'scurrentexecution.Asanotherexample,supposethatglobaldeadstoreeliminationhasremovedastoretothevariableyalongoneexecutionpathbutnotalonganother.Ataprogramlocationbetweenthedeletedstoreandthenextassignmenttoy,ifthedeletedstore'sexecutionpathhasbeentraversedmorerecentlythantheotherpath,thenthevalueofyisincorrect;otherwiseitisnot.rg#*u$(gg%r)9gug)r+gug+rg1u2gg3mpgMbbcb&#b-b5b=dbE%b`Eb`Eb`FFb`Fb`Gb`Ggb`Gb`H(b`Hb`Hb`IIb`Ib`J b`rc8c8w_# +. r]'c${*]'r]',03Zc${*ZrZ,25X0c${*X0rX0,.07^ wT$]). rRc$?*{/RrR146u;(Oc{#OrO%) wL% -W rIc$?*{/IrI15L8 ?CG5:R<@BDEpc$?*{/EprEp179MBc{$BrB')+ 3: w?_7$+:/0468<2L FH! *#%*+/.4b788;@F< ]"h(,/(3d5*:=TCFF !U$)/15+9<^@B T xJTrT %y&*,8.14@7=b@D%GxrW\ ")H+-16 =?E!, (H*0,154q58>x=Tr>B.DL":$y%+1369>BAE<GN  xNrN"z&-0V26W36U;.AsE"HQAw$`!x% ,0h26!;VA=GpN ss"$',T/e 68;>DKI> " *~/5159;I?D4 H|"(d.2 9{AG@Bl?#&)4.;/4:@NB =9 g#q&*Z,</^5A7:=BIE7*2b $|&+- 46k8x>7*r7*?CEG{4h'c#h%(,qx.\4hr4h/4l57 ?e@CH1\x1r1("(-0i3a7<>A H7.A+" (+1=46:`<)@F<,# a!!$&)'+/o3(5t8}=@DMF H)b !+%,:/m59?AE_&? 1#.' # ;9( (+..07> DG9 I)p , & "$]&*G 179;BBFIc &*,2/ 8:i@cD 0 Y )u, 5X8L<1 DHo!N#&v,14:>D  (-139P;w C"Ez 7# ,1. 58 9=? V !t$(",.29;=&CI ?TVm$CHAPTER4:SOLUTIONTECHNIQUES77moreexpensivethannotoptimizingtheprograminthefirstplace.Thedebuggercouldwaittobeginrecordinguntiltheuserhasissuedadebuggingcommand,buteventhisreducedcollectionislikelytorecordunnecessaryinformationandtobeexcessivelyslow.Ontheotherhand,itcancertainlybedescribedsimply:duringdebugging,collecteveryuser-visiblechangetothecomputationstate.Sincesomenecessaryinformationmightresideintheportionofthehistorythatoccurredbeforerecordingbegan,itdoesnotguaranteeexpecteddebuggingbehavior.Insteadofcollectingthecompletehistoryofeachcomputation,thedebuggercouldcollectonlyselectedinformation.Atmost,thecontrolflowthroughbranchesandtheoldvaluesofvariableswhoseassignmentshavebeenmoved,deleted,oroverlaidneedtoberecorded.However,thisinformationisprobablystilltoomuchtorecordbydefault,evenduringdebugging.Tolimitthedynamicinformationstillfurther,thedebuggercouldcollectonlythedynamicinformationthatisusefulforthecurrentlyactivedebuggingrequests.Itscollectioncouldberequestedexplicitlybytheuser(whichwouldbetruthfulbehavior),orthedebuggercouldcollectitautomatically,triggeredbydebuggingrequestsinoptimizedprogramregions(forexpectedbehavior).Forautomaticcollection,eachdebuggingcommandwouldpotentiallytriggerthecollectionofsomefutureinformationtobeusedinitsprocessing.Notethatthisdramaticallyreducestheamountofdynamicinformationcollected,butatthesametime,itrestrictstheusefulnessoftheinformationtopreplanneddebuggingactivityonly(thatis,breakpointsorexplicitusercollectionrequests).Forunplannedactivity(programexceptions,asynchronousinterrupts,andproceduretracebacks),thenecessaryinformationwouldprobablynothavebeenrecorded,soexpecteddebuggingbehaviorcouldnotbeguaranteed.Ofcourse,ifwholecomputationshavebeenremoved,simplycollectinganexistingvalueisnotsufficient.Inthiscaseitmaybepossibletoperformthecomputationatitsoriginallocationandthencollectitsresult,butfurtheroptimizationsmayhavealteredvaluessothatthiscannotbedone.Giventheentirehistoryofthecomputation,thedebuggermustbeabletofindthehistoryinformationrelevanttoagivendebuggingrequest.Ifdebuggingactivityistotriggerinformationcollection,thedebuggermustbeabletodecidewhatdebuggingactivityshouldtriggerwhatinformationcollection.Thecompilercanrecordstaticcuesforthistriggering,orthedebuggercananalyzeitsotherstaticinformationtoderivethecuesondemand.Furthermore,thedebuggermustbeabletousetherecordedinformationproperly,eithertogivemoretruthfulbehavior(exactknowledgeofnoncurrentvariablevalues)ortogiveexpectedbehavior(reconstructingthecorrectvalues).rg#*u$(gg%r)9gug)r+gug+rg1u2gg3mpgMrb) %(-/a149Q<<BWF5I@_g2!$(@)q0169y<?oD \S ! )V,-/ 6:="?C+GHcYQ % ,0%3 :?=@B W#~ (?,H0\249~;H=B]E=Ta1["G$+07}P !c'u,1.1o 9EDH y K"%U),*/*1&6&9m= DA_ ').1J7k;N?BE_B1 G"$*.5 DH?o#  h"b&+- 2" 8:i<BF< !(.07H= B2E29  ' '*18>< CH7* = &(*./1 9=e@ZC! 4iy! )K /<135K8;=2B%Da 1i * $+v0w37G9B @BG. E P*&4++1b 8 Ad H7,$ m &s .F28;?'BI*)c!v%f(* 2L49N:? G&;@ "$)-l.1F 89<?l@CE#} !#& +1/4M7<>C^FF! _c";&i(-*-24 fl!"%e -0L6p9;?@CF] pi"P).0M7 ;=H>Cd  ]"\$').m29>"BGD _ V !%(M,0 35?7 >^@BgHco %"&+O-13>9 B]D;_# *0`4>58 TVm$CHAPTER4:SOLUTIONTECHNIQUES78Thedynamicinformationcouldbecollectedaspotentiallyunboundedlistsofrelevantcontrolflowanddatainformationor,moreefficiently,asonlythemostrecent"layer"ofthatinformation.Themostrecent"layer"mightbeneededinprogramregionsaffectedbymultipleoptimizations;itincludesallvariablevaluesthatarepossibilitiesforanyfuturedisplayrequestandallcontrolflowinformationthatcanstillbeusedtoanswerfuturedebuggingqueries.Forinstance,supposethattwoassignmentstothesamevariablewerehoistedacrossagivenprogramlocation.Thenbotholdvalueswouldneedtobesaved:thefirsttodisplaythecorrectvalueatthatprogramlocation,andthesecondtodisplaythecorrectvaluebetweenthefirstassignmentandthesecond.Similarly,inprogramregionsthathavebeencross-jumpedrepeatedly,itmaybenecessarytoknowthedirectionofseveralearlierbranches.(Furthermore,thesearenotnecessarilythenmostrecentbranches).Asanexampleofdebuggingactivitytriggeringthecollectionofoldvaluesofvariables,supposethatstorageoverlayinghasallocatedthesamestoragelocationforvariablesvandw,makingthevalueofvariablevinaccessibleinsomeprogramregion.Whentheuserrequestsabreakpointinthatprogramregion,ittriggersthe(hopefullyfuture)collectionofthevalueofvbeforeitisoverwrittenbyw.Inaprogramregionthathasbeenheavilyoptimized,asinglebreakpointmighttriggeralargeamountofdynamicinformationcollection.Toreducethisamount,theusercouldspecifyinadvancewhichvariablesshewishestoexamineatthebreakpoint.Toavoiddecreasingtheexecutionspeedofoptimizedprogramsthatarenotbeingdebugged,thedebuggershouldwheneverpossiblecollectdynamicinformationonlyondemand.Therefore,thecompilershouldnotgenerateobjectcodetocollecttheinformationaspartoftheprogramitself.Thisrestrictioncouldberelaxedaslongastheoptimizedprogramwiththeinformationcollectionisstillsignificantlycheaperthantheunoptimizedprogram.[Seethemodifiedcodemotionoptimizationdescribedinthefollowingsection.]Fourimplementationsofdynamicinformationcollectionlendthemselvestobeingtriggeredatruntime:tracing,interpreting,breakpoints,andpatching.Thedebuggercouldusethesemethodsautomatically,withoutnotifyingtheuser(exceptthattheusermightseeareductioninexecutionspeedduringdebugging).Forinvisibletracing,thedebuggercouldtracetheprogram,eitheratthesourcelevelorattheinstructionlevel,recordingthedesiredinformation.Thismethodwouldprobablybepainfullyobvioustotheuser.Similarly,thedebuggercouldinterprettheobjectprograminvisiblywheneverdebuggingisactive;thiswouldlikelybeevenslower.Theuseofinvisiblebreakpointscanbeamuchmoreefficientmethod.Thedebuggerinsertsaninvisiblerg#*u$(gg%r)9gug)r+gug+rg1u2gg3mpgMrb)t !}%@'),. 5J<?QAF<_g !)$ +k-02s59>@IC \-\/"2$.)*0V5):l? E@C :%(+0L57x=@Cr@C?xA@Cr@CBCH=Jx=r= "O$'-'2L6g8;A BM I@:o#% ,w1F 79<'@xA:r:CzGI7 %x7r7H6"&),5/4D ;<&@ F5<M}$P + 25*9 @DJ,$GV"'Z+1E 8;>D6 )cc@u$(V+-24 <.=ABE`&Z +!#'()-".1p7=@Cd # 6 !K&),O 4gu;##;_=?DQG ! C2p"Kr b!& . 4:7I >.?CIV !n )C,25k;|?PAE^ "%( ,/26599;;<CDDb "a',/h59j<?UERIV?% %[(/1y6@ >AF"m$Q&+& 14%:d>eD@F B '})-0d48:>#CFI5 >   "?&?)/{58>C]Ev TVm$ CHAPTER4:SOLUTIONTECHNIQUES79breakpointwhereveritwishestocollectcontrolflowordatainformation.Theoptimizedprogramrunsatfullspeedbetweencollectionpoints.Obviouslythereisatradeoffbetweentheproximityofcollectionpointsandthevalueoffullspeedexecution,especiallyifbreakpointsareexpensivetoprocess.Invisiblebreakpointscouldbeextendedtoinvisiblepatching:thedebuggercouldpatchincodetorecordtheinformation,oreventoinsertthedeletedcomputationsthemselves.Infact,staticanddynamicinformationcouldcooperate.Forexample,insomecasesofdeadstoreelimination,thevariable'svalueatagivenprogramlocationcanbecomputedfromothervaluesthatarestillavailablethere.Whenthedebuggercandeterminethisfromtheflowgraph,itneednotcollectthevalueofthatvariable,becauseitcancomputethevalueifitisrequested.4.1.3RestrictingoptimizationTheproblemofdebuggingoptimizedcodecanalsobeattackedbyrestrictingoptimizationsinsomewayshortofturningthemoffcompletely.Thismethodisnotasdesirableastheprecedingmethods,soitshouldbeusedonlywhenadditionalstaticanddynamicinformationdoesnotpermitexpectedbehavior,orwhentheinformationistooexpensivetocollectandmanage.Thereareseveralpossiblewaystorestrictoptimizations.Someoptimizationsmightbeverydamagingtodebugging,whileonlyslightlyimprovingtheexecutioncharacteristicsoftheprogram.Theseoptimizationscouldberemovedfromthecompiler.Apossibleexampleisdeadstoreelimination.Anotheralternativeistoinhibitsomeoptimizationsundercertaincircumstances.Thecompilermightchoosethecircumstances(whenitbelievesthatdebuggingwillbesubstantiallyimpaired),ortheusermightexplicitlyrequestrestrictedoptimization.Forexample,theusermightspecifythatcertainvariablesaredebuggingvariables.Asaresult,theoptimizerwouldnotperformconstantpropagationorconstantfoldingonthesevariables,overlaytheirstorage,etc.,sothattheusercanalterthevaluesofthesevariablesduringdebugging.Theusermightalsospecifythatcertainprogramregionsmustbeabletobedebuggedwithexpectedbehavior.Theusershouldbeabletospecifythesedirectivesseparatelyfromtheprogramitself,sothattheprocessoftheirremovalcannotintroduceerrors.Ofcourse,itislessdesirabletorequiretheusertospecifydebuggingpreferencesbeforecompilationthanatruntime:theusermaynotknowinadvancewheretheprogrammightfail.Thecompilercouldalsolimittherangeofoptimizations.Thatis,itcouldforcetheoptimizedrg#*u$(gg%r)9gug)r+gug+rg1u2gg3mpgMrb)  !]#'P+/03 <'>E`_g0 %*1`46`7<B?D\ # Z$%(w,i 3 9K: B@DYz "&(p.B/5=;;=CxG-W#4 $%)!*.05 >L Sru"B )- 47Y=)>BhEGP`  "&(P)-q3!8y;&=8CGON  * $(+R1Y3:a=@dB IKI?c  #)#.E/2&7:,=?6@A vE ; rA]r"J(+.k1-38y:k @ I@>vOg"%% ,05%69:@B8D;`!$' .1y49 ADF~9 # *,J.5;7;w>LDzH6Vs"Q 2 "#'-g/ 669=AH/K!'+ 479?DBD->o)#O )  $(V 049 BsE3& "'(-07:IuBEY #E( *- 38;ACEH` $'). 6]9RADH^ u " )c,/5L92;'>'@EGcs$&+-[.179>AADnFR ;! )l,.4]6: =<?CEZ n #&$)+ 489;>B0DTVm$CHAPTER4:SOLUTIONTECHNIQUES80andunoptimizedversionsoftheprogramtocorrespondat"fixedpoints",whichcouldoccuratseverallevelsoffrequency:atstatementboundaries,atbasicblockboundaries,andatscreen/pageorprocedureboundaries.Threespecificproblemsmustbeconsideredforthisrestrictionmethod.First,whatevermethodisusedtoimplementtherestrictionsintheoptimizermustlimitobjectcodeoptimizationsaswell,includinginstructioncollapsing(whichmightcrossafixedpoint),branchchaining,andcross-jumping.Second,evenifbreakpointsareonlypermittedatthesamegranularityasthefixedpointsoccur,otherdebuggingevents,suchasprogramexceptions,canoccuratafinergranularity.(Asynchronousinterruptsmightalsobepermittedatafinergranularity,orthedebuggermightcontinueexecutionuntilafixedpointisreached.However,evenifthecurrentlyactiveprocedurecanbesuspendedonlyatfixedpoints,theprocedurecallchainwillcontainproceduresthathavebeensuspendedbetweenfixedpoints,unlessoptimizationsnevercrossprocedurecallsaverysevereoptimizationrestriction.)Asaresult,somethoughtmuststillbegiventoprovidingthevaluesofvariables(whichmightbeinregisters)andtoreportingthecurrentexecutionpointforprogramregionsbetweenfixedpoints.Minimally,fortruthfulbehavior,thedebuggermustadmitthatitcannotprovidethecorrectresponse.Tominimizethisproblem,Hennessyrequiredthatthecompilergeneratecodesuchthatchangestothecomputationstate(e.g.,stores)occuronlyattheendofastatement'sobjectcode.Third,compiler-introducedtemporariesmightbeexemptedfromtherangerestriction,allowingtheiroptimizedvaluestodifferfromtheirunoptimizedvaluesatafixedpoint.Forexample,commonsubexpressionscouldbestoredinacompilertemporaryforuseacrossseveralfixedpoints.Ifthedebuggerpermitsvariablemodification,thisexemptioncancauseproblemsduringdebugging:ifthevalueofacompilertemporaryiscomputedfromauservariable,theusercouldalterthevalueofthatvariablebetweenthetemporary'sassignmentanditsuse.Fortheremainderofthediscussionofoptimizationrangerestriction,wereturntotheassumptionofstatementbreakpointgranularity.Whentheoptimizerplacesfixedpointsateverystatementboundary,noadditionalcompilerordebuggereffortisneededtoachieveexpecteddebuggingbehavior(exceptforthethreeproblemsdescribedabove).Optimizationsareverylimited:oneofthemajorallowableoptimizationsiscommonsubexpressioneliminationfordatastructureaccesses;constantfoldingandsomeobjectcodeoptimizationsarealsopermitted.ThedesignoftheFDSdebuggerincludeda"nosourcerg#*u$(gg%r)9gug)r+gug+rg1u2gg3mpgMrb) 0!#~)'* 2(38$=kAEzIV_gl0 !S' .0w37 ?ACB \& #'.1g3V ::@C&FM6F16#&(.e 58<>?C Jt u "%(.o0+1w4 I@FG"&,'-368R:@DkDtk,L"o&)W/2r6.8= DGB0oZ"'S+ 4T8O;BG?n2 N #`%&+'.4"7:q<@[B,H<C#I%H' ,/1p7{9>EH9j+" & -025C;E=CG7*_^#8)+14N:@HEH4h6 #(*, 484;?CFH1R| ."D )-/S58; > Ek+OVJ&#&*& 2M68n9=oBEE(z !d#='H()/68C:>CFs%?z_/"A *x,359?oC # ^p&H'.V1361;>TAhEOH IEI!$ + 25_7:ZH W# )+ 4B8c ?BFH   $ \7n"& *R+/5<> E3y)z )!&,-28b=?3AwD< #&y)/136d:@ I  $'<*Z005;@YC)F VD I 1 '*.0386<BCF UTVm$CHAPTER4:SOLUTIONTECHNIQUES81change"modeofthiskind;nomentionwasmadeofthethreeproblems.Ofcourse,recompilationandre-executionwouldhavebeennecessarytoinvokethismodeifanerrorwasencounteredduringa"fulloptimization"modeexecution.Whentheoptimizerplacesfixedpointsateverybasicblockboundary,moreoptimizationsarepermitted,suchas:localcommonsubexpressionelimination,localcodereordering,localconstantandcopypropagation,aswellasobjectcodeoptimizations.Nevertheless,thelackofunknowncontrolflowmakesbothdetectingandunravelingtheeffectsoftheoptimizationsmucheasierthanforglobaloptimizations.Hennessy'sexperimentsshowedthatnoncurrentvariablevaluescouldalwaysbedetectedforlocaloptimizations,andcorrectvaluescouldoftenbereconstructed.Inthisprogression,thenextlogicalstepistheprocedure,butanintermediatelevelhassomepracticalvalue.Theoptimizerwouldplacefixedpointsatthemorefrequentofprocedureboundaries(possiblyincludinginlineprocedureboundaries)andevery15to50statements(anexperimentally-determinednumber,chosentomaximizeoptimizationbenefitsandminimizedebuggingdifficulties;nottoexceedonescreenorpagefull).[Whenproceduresdonotexceedtheone-pagelimitcommonlyrecommendedinsoftwareengineeringbooks[Kernighan+74],thislevelandtheprocedurelevelcoincide.]Sincemostbasicblocksarequitesmall(theaveragebasicblocklengthiscommonlyreportedtobelessthanfivestatements),thislevelpermitsglobaloptimizationsandtheiraccompanyingdifficulties.However,thislevelofrestrictioncansignificantlyeasetheburdenthatothersolutiontechniquesmustbear.Forinstance,toassistnewdebuggingalgorithmstoreconstructvaluesofvariables,thefixedpointslimitthenumberofvariablesthatcanhaveincorrectvaluesatagivenprogrampoint.Toassistinshowingtheeffectsoftheoptimizations,thefixedpointslimitthenumberofreorderedandalteredcomputationsandallowthefullregion(onefixedpointtothenext)tobeshowninasinglescreenorpageimage.Toassistdynamicinformationcollection,thefixedpointslimitthedistancethatcomputationscanbemoved,sothatitismorelikelythatadebuggingrequestwilloccurbeforeitistoolatetorecordthenecessaryinformation.Toassistlimitedrecompilation,thefixedpointsgiveareasonablycloseplacetoswitchbetweentheoptimizedandunoptimizedversionsofaprocedure;truefixedpointsmightoccuronlyrarelyinafullyoptimizedprogram.Notethattheassistancefordynamicinformationcollectionandlimitedrecompilationappliesonlytopreplanneddebuggingactivity.Theexactimplementationofanoptimizationcanalsoberestricted,sothattheoptimizationrg#*u$(gg%r)9gug)r+gug+rg1u2gg3mpgMrb)+,!')-h/1a4;=B: _g 3!%9+}-]2 48:t<@8C \S| a$7 Y'"5%)+Q.2e6<@( HVN J$ , 4v7; B0ES$ :"#(+q 5 =@CDP#&n -//35m7 @-CGN C ( &^ .83P6B =wBG#KHG7 6 ) +0U48N;= Gu  (#:'*|+.L 5*79 ADG[D#u'+/458<BdDkB/ ""Y&g- 47;=?A H?n%*-3 <AD<  %'+-f0u4B<<47 =O>@DIF9{ Y# ),5f7|:<<>CME r7) [#'*/3+6;I<CI@4h w{ "T%C(.2 ;S>XA 1 ./P %5' /!14/8;|>D +OD-q #&-6 35 <@B H(Zw!7"(+g-1-6; <=AoF%mX!#% .04Q8b;=BD# . !f%'q).B1i48:8<@#ACHI H(S!]#'-, 4h ;=vAE8HD& "X$])O+'. /s048m;O<CZHC2 :$&, 5=7]:? HBG# $)')0-L24;-= EB #.'"*-1347>KDH  B ( /d27 @EI@   )' "#% -03g5h ;=@B  tTVm$CHAPTER4:SOLUTIONTECHNIQUES82isperformedinawaythatislessdamagingtodebugging.Forexample,supposethatthecodemotionoptimizationisalteredslightly,sothatthehoistedlocationalwayssavestheoldvalueofthevariableinacompilertemporarybeforeperformingthenewstore.Thiscostsoneextrastoreandoneextratemporary(whichonlyneedbeliveuntilthestore'soriginallocation).Thisnewformofthecodemotionoptimizationisstillquiteeffective,becausethecomputationandthestorehavebeenmovedoutoftheloop.Moreimportant,thedebuggeristhenabletoprovidehigh-qualitytruthfulbehaviorataprogramexceptionoraninterrupt:itcanshowboththecurrentandsavedvaluesofthevariable.Toprovideexpectedbehavior,thedebuggerwouldneedtocollectdynamiccontrolflowinformationtoascertainwhetherthisisthefirsttimethroughtheloop.Similarly,theoptimizercouldalwaysstorehoistedcommonsubexpressionsincompilertemporariesratherthaninuservariables.4.1.4RestrictingdebuggingcapabilitiesInsteadofrestrictingoptimizationtopermitmoreintelligibledebugging,thesystemcouldrestrictdebuggingcapabilitiestopermitmoreextensiveoptimization.Thedebuggercouldcompletelyomitcertainfunctionsthatareverydifficulttohandlecorrectlyforoptimizedprograms.Aprimecandidateinthiscategoryisvariablemodification.Hennessy'salgorithmsdidnotpermitvariablemodification.Thedebuggercouldalsorestrictitsbreakpointgranularity,possiblytocoincidewiththeoccurrenceofoptimizationfixedpoints.Asforoptimizationrangerestriction,theinterestinggranularitychoicesincludebasicblockboundariesandscreen/pageorprocedureboundaries.Hennessyenforceda"semanticmapping"restrictiononbreakpointplacement:whentheevaluationofacommonsubexpressionwasthefirstobjectcodeforastatement,theuserwaspermittedtosetabreakpointonlyatthefirststatementcontainingthatcommonsubexpression.Restrictingdebuggingcapabilitiesdoesnotmeanthatthedebuggerisallowedtogiveincorrectresponsestocertaindebuggingqueries;instead,itmeanseitherthattheuserisnotpermittedtopresentqueriesthatwouldresultinanincorrectresponse,orthatthedebuggergivestruthfulratherthanexpectedresponsestomorerequests.Initsproposed"fulloptimization"mode,theFDSdebuggerwouldnotreallyhavesatisfiedthisconstraint:itsresponsesweretoocryptictobeunderstoodreadily.rg#*u$(gg%r)9gug)r+gug+rg1u2gg3mpgMrb)fB J: !!$S*,| 4B7<BIE0G_g @!'(+.I3&8q<@BExI5\G6e%%*! 1X36:>AiDGYv#\&*, .2%48> DHW#;8p & 'h)-w 3E8Y: BE@GTa9{#h' -/569<>RC6 QY" (]*(, 2h36Y9=-?DeG#N$)/28 <+?{AE_L %k*-I.136<>uBd HI[[ %+O 46a<& CGF v@ ;" r< 1 '[);-1 8 ?BvG#9t. !K"'j*0 6R`N $',k2N579:-?J@EI3% $$,*h,.4C5: C 0 $7 -9 "1')( 0^ 7=?{E/H*w  B#){+.G 6: AD5 ' ,C q$3(A /2 :<C $!(G .0 7m >gBDK "2X "%'+/+1_2 9;Y>I@G-Hq  ' -06S  ) &3)Q+/`24i:`;@BWE2z"F',.#2z6z9[;>@YBI@WT &"$t&O+136D8>AF/b 7#*s,i.k47 @EG.X e#),c 3v5<?BAG H mTVm$LCHAPTER4:SOLUTIONTECHNIQUES834.1.5RecompilingasmallportionoftheprogramAutomaticrecompilationofaprogramregion,togetherwithon-the-flycodereplacement,canallowformoreextensiveoptimizationwithoutrequiringelaboratecompile-timepreparationforthepossibilityofruntimedebuggingrequests.Theidealoptimizationrestrictionforagivendebuggingrequestistherestrictionthatresultsinthemostoptimizedprogramthatcanrespondcorrectlytothatrequest.Onlythosetransformationsthatcausetherequesttobeunanswerableareinhibited.Forexample,iftheuserrequeststhevalueofavariableatapointaffectedbydeadstoreelimination,themostoptimizedprogramthatcanprovidethevaluehasexactlythatonestoreadded.Theprimitivedebuggingmethodofinsertingaprintstatementwillprovidethisbehavior(becausethestorewillnotbedeadintherecompiledversion),butatthecostofrecompilingandre-executingtheentireprogramforeachrequest.Therecompilationandreplacementtechniqueisanoutgrowthofthisidea,withthesizeoftherecompiledregionreducedandlittleornore-execution.Whentheuserrequestsdebuggingactivityinaprogramregion,aportionoftheprogramisautomaticallyrecompiled,eitherwithalowerlevelofoptimizationorwithafixedpoint[seetheprecedingsection]atthedesireddebugginglocation.Thesystemthenreplacesthefully-optimizedversionofthatportionbyitsless-optimizedversionintheexecutingprogram.Thesizeoftheportioncouldvaryfromasinglestatementthroughabasicblockorproceduretoanentiremoduleforalargeprogram.[Aparticularsystemcouldallowseveralsizesorchooseasingleone,suchastheprocedure.]Asaresultofthereplacement,alesssophisticateddebuggercanprovideexpecteddebuggerbehavior.Thereplacementgenerallyrequiresafixedpointatitsbeginningandendtoallowthenewregiontomeshwellwithitsoldversion.Thecodegeneratorcouldconceivablybegivenconstraintstopermitmeshingatotherplaces,buttheseconstraintsmightinteractpoorlywiththeabilitytodebug.Thistechniqueworksonlyforpreplanneddebuggingactivity,suchasbreakpointsortracing;itisnotparticularlyusefulatprogramexceptionsorforexaminingthestateofcurrently-suspendedproceduresintheprocedurecallchain.Forsuchunplannedactivity,theprogram'sexecutionmustberestarted.Furthermore,ifthecurrentexecutionpointisinsidetheaffectedregion,theabilitytodebugcanonlybeassuredthenexttimethroughtheregion.Whencontrolhasalreadyenteredtheaffectedregion,itmaybeimpossibletoswitchfromexecutingthefully-optimizedversionoftheobjectcodetoexecutingtheless-optimizedversion.Forinstance,hoistedcomputationsthatrg#*u$(gg%r)9gug)r+gug+rg1u2gg3mpgMva D" '),r]] !"#). 36 =@H Hc[ |/ %*06 ? F`HtXI rXI""T  &x()-4}9^:=A CFQ$(&+407"9S<CZGOO1z0!&f(* 24 ;>aD3EGLoC]P"$0%b) .J0N37 >ADIx H!%(,/26;<>1D5F9%(T-P/5;=`@CJEGD* "6#&/(* 2N5 <?5C!HAi #6% -35^7I=?B-EyH>F !&T) ,<.0 ;9A 'r,J./@49:?AvCI8P u # &['+.0 8:>?MBuF8P8PFH5r5H!i(C.16*9p>AR2! */1y3:D@CFH0 tv"(."/@26Z8>@+BE-J4ru-J-J #&&),03848a9_<? ACE r*8\ #%,( 0s69>D'{Z #&+c,035\7==@mC+DH%c9"W$Y&,/3L9= E"G:"D v!j#&+#-18 8<AEoH!'"G$ +27:< DE+' $ &) ,.07L9<>bi v 7"'!),38;AbG o !_#(.237:g?DMF.>%!#[&a)|.16 :>A/E%P@! (*P.28G:D_I5 cW #Y ,d224:? H  ^TVm$CHAPTER4:SOLUTIONTECHNIQUES84appearlaterintheless-optimizedversionmayalreadyhavebeenperformedinthefully-optimizedversion.Thesecomputationsmaynotberepeatablewiththesameeffect(suchasx_x+1).Also,iftherearesuspendedprocedureinvocationswhoseexecutionpointisinsidetheregion,thesystemmustkeepthefully-optimizedversionoftheregion'scodewithwhichtocontinueitsexecution.(Thiswouldnotbeaproblemifthesysteminhibitedoptimizationsacrossallprocedurecalls,butthatisaharshrestriction.)Feiler'sincrementalcompilationanddebuggingsystem,LOIPE,includedoptimizationcapabilities[Feiler82].Sincehehadnonotionoffixedpointsnorofmultiplecopiesofobjectcode,theinsertionofdebuggingstatementsinaprocedureactiveanywhereinthecallchainmadeitimpossibletoresumeexecutionoftheprogram.Thisrestrictioncouldbeavoidedfortwointermediatelevelsofprogramoptimization:the"completedisplay"levelrequiredalldatavaluestobestoredintheirpermanenthomesbeforeanyprocedurecallordebuggingstatement,whilethe"fulldebugging"levelprohibitedoptimizationsacrossanyprocedurecallordebuggingstatement.Acheckpointingcapabilitywouldextendtheutilityofthistechniquetounplannedorsemi-plannedactivity.Ifthevaluesofall(orjustchanged)accessiblevariablesarerecordedatintervalsthroughouttheexecutionoftheprogram,suchasatprocedureentriesoratfixedpoints,programexecutioncanberestoredtothelastcheckpoint,theaffectedregioncanberecompiledandreplaced,andprogramexecutioncanresume.Thesystemwouldalsoneedtorecordallinputandoutputsothatitcouldbereplayed.Ofcourse,anautomaticcheckpointingcapabilitywouldbequiteexpensiveifitwerealwaysactive.However,thedebuggercouldincludecommandstoenableautomaticcheckpointingortorecordasinglecheckpoint.Iftheamountofstaticinformationbecomesexcessive,recompilationcanalsobeusedtosupportthetechniqueofaddingstaticinformation.Thedebuggerwouldinvokethecompilertocollectmoreinformationaboutaspecificregionthanisnormallyretained.Forexample,variablestoragelocationscouldberecordedonaprocedureorloopbasisonly;fordetailedinformationaboutavariable'sstoragelocationduringaspecificstatement,theregisterallocatorcouldbeinvokedonthesourcetextortheflowgraphoftheregion,withtheinitialstateasnotedinthesymboltable.Ifpeepholeoptimizationcanaffectvariablestoragelocations,thenitwouldbenecessarytoapplytheentirecodegeneratortotheregion.rg#*u$(gg%r)9gug)r+gug+rg1u2gg3mpgMrb)b) #r(3+1/3>6=Q>AR_glb #&4( .147;@>x@_gr_gxA_gr_gxC_g_gCrE_g_gF Gg\2# *,.J4n79X=J?D$FsY_;!&(+ 0C36:<BrDb W#y$F!#3%*/ 8w<>{EHmTaF P  '4*x17 <B N  uN N Hr|N N !j$&*o,"/36;7=aAC=GOKIc4 &()04:<?5AEIH  (#%(v/2 9=@.EHBE m" *x,3z8<-ACFC#'+.5A79@ G:@CF  ' 05086?B D5= 9  #n',/469#?AI*7* ~`!~%'), .4 ;0A C|IV4ig $&%(@.(1Z3 4;&?A[BFs1ot$&) + 3 5~:?"AC .h%(Q-05+9Q<?lAE[GD,$!(t*/?187 @w F)cZ!+%*03T9r=RBFI@&G "u$9%*7+`/L # ^9* (. 4 =@CEI@ Jh#3& /J208G<A CwI@4 U"9#e(Q,/1-6=7?Es%['(/f1H48;>Cd r %5)+T0 7Q9?DHD=]@ !$h+,/P47:9=ABFH4 M (w+4/049{ ?CDHo $* +..TVm$CHAPTER4:SOLUTIONTECHNIQUES854.2TechniquestosupporttruthfulbehaviorFortruthfulbehavior,thedebuggercanadmittotheuserthattheprogramhasbeenoptimizedandcanallowtheusertoshouldersomeoftheresponsibilityofunravelingtheeffectsoftheoptimizations.Techniquestosupporttruthfuldebuggingbehaviorincludeshowingtheeffectsoftheoptimizations,sothattheusercandebugtheprogramthatisactuallyexecuting,andaddingnewdebuggingcapabilitiesespeciallydesignedtohandletheproblemsthatarisewhendebuggingoptimizedprograms.4.2.1ShowingtheeffectsofoptimizationsAmajorstumblingblockwhendebuggingoptimizedcodeisthattheprogrammerdoesnotknowwhatthetransformedprogramlookslike.Thusshemayrequestthedebuggertostoptheprogramatastatementthattheoptimizerhasdeletedbecauseitwasredundant.Atsometimewhentheprogram'sexecutionissuspended,shemayaskforthevalueofavariablethathasbeenremovedbyconstantpropagationorbyinductionvariableelimination.Eventoprovidetruthfulbehavior,thedebuggermusthavesophisticatedcapabilities.Suppose,ontheotherhand,thattherewereanautomaticsource-translatorthatcouldgivetheprogrammeranewversionofthesourceprogramthatshowedtheeffectsoftheoptimizations.Thissource-translatorcouldalsoprovidethedebuggerwiththeusualstraightforwardmappingsfromthisnewversionofthesourcetexttoobjectcodeanddatalocationsintheexecutingprogram.Thentheresponsibilityofreformulatinganydebuggingquestionsabouttheprogramintermsoftheexecutingversioncouldbeshiftedtotheprogrammer.LovemanandKuckreportonprogramtransformationsystemsthatcanrecreateanewversionofthesourceprogramfortheusertoexamineatanypointinthetransformationprocess[Loveman77,Kuck+81].Thesesystemsprobablyuseastandardprettyprintingalgorithmworkingontheprogramgraphgeneratedbytheoptimizer,similartotheprettyprintersusedintree-structurededitors[Teitelman78,Donzeau-Gouge+75].Prettyprintingsystemscommonlyhavedifficultywithplacementofcomments;programtransformationscanonlyaddtotheseproblems.Ifthesourcetextcorrespondencecanbefairlyeasilydeterminedbytheprogrammer,thisapproachmightsolvetheproblemofdebuggingoptimizedcode.However,sinceoptimizationscanradicallyaltertheprogram,theprogrammermustunderstandanewprogramthatsolvesherrg#*u$(gg%r)9gug)r+gug+rg1u2gg3mpgMsa &%o,mr]77(!p'a)-/A14j7!9i>A=DZ_%)+z. 68 ?B%FHX e !&+28tt=iXX=BEIKUQJ r UQUQ!F$['+L-3r6\7= CtFUQUQG7R: rRI %+\-14':A=!@nD5ONvJyQ!# rEK[!%,`26H7:=2 E.HyC O%)->03N6`;C=CEH@];~ #+)n+06#7:W B DG=`!# *,/14/6:8;=BOEG:) #%'-34 ;i?@E8JS $ ,( 4uoV# %)`,.4?+AEH1 5G 3"$).169F=?B .! #(+A1o473:D,>3H 5$o'(,/2~5m;<>E)| I (*1{7;=CE[I5&Al4!&w(%* #%U "!$) 27:=B(CEF' c  #%x*,_.2v46Z ?uDH c cD r?1!#&I'd, 5;ACE` %E*+. 7y:<Fhu r #! *e/k669 ?sBI5]w%?'*-/J2QW: '.),/3 ;5=\? HM:$&-4"8>Bq D|M"% -0 78;ADjHyNTVm$pCHAPTER4:SOLUTIONTECHNIQUES86probleminordertoaskmeaningfuldebuggingquestions.Forexample,Lovemanshowsanoptimizedmatrixmultiplicationprogramthatismuchdifferentfromitsoriginalsourceversion[Loveman77].Anotherproblemwiththisapproachisthattheprogrammermayhavetoreadthroughtheentirenewsourcetexttobeabletoformulateadebuggingrequestaboutsomesmallareaoftheoriginalprogram.Thiscanhappenasaresultofinlineprocedureexpansion,themovementofinvariantcomputationsoutofloops,constantpropagation,andothertransformations.Onewaytosolvetheseproblemsistoannotatestatementsinthenewsourcetextwithreferencestotheplacesintheoriginalprogramtowhichtheycorrespond,andwithdescriptionsoftheoptimizationsperformed.However,thiscanresultinanenormousamountofinformationforevenareasonablysmallprogram.Furthermore,thissolutionwouldprobablyoverwhelmnaiveprogrammers.Severalotherissuesmustbeconsideredinprovidinganewversionofthesourcetext.First,atwhatlevel(betweensourcelevelandmachinelevel)mustthisnewsourcetextbewritteninordertoallowforagivensetofdebuggingcapabilities?Theeffectsofsomeoptimizationscannotbeshownusingonlythesourcelanguage.Also,supportingassignmentstovariablesinthedebuggerrequiresalowerlevelthansupportingonlythedisplayofvaluesofvariables,becausestructuredvariableaccessesmustbeexposedwhenaddressesarecachedacrossstatementboundaries.Ideally,theprogrammershouldnotbeexposedtoanymoredetailsthantheoriginalprogrammentioned(forexample,tothewaythatstructuresinthehigh-levellanguagearestoredandaccessed).AsFigure4-2shows,addressingcomputationscanbeexposedwithoutdisplayingmultiplicationsbyelementsizesorotherlow-levelimplementationdetails.However,onlyhighlymotivatedprogrammmerswillwishtoexaminethelargeamountofadditionalinformationthatisdisplayed.Tomakethisinformationmoreintelligible,itcanbelocalized.Withrespecttoagivenpointinthesourceprogram,thedebuggercouldshowwhichcomputationsthatappearlexicallyafterthatpointintheoriginaltexthavealreadybeenperformed,andwhichcomputationsthatappearlexicallybeforethatpointhavenotbeenperformed.(Ofcourse,thisrequiresthedefinitionofacorrespondingpointintheoptimizedprogram.)Hennessy'salgorithmscanprobablybemodifiedforuseinthisway.Itshouldbepossibletoobtainsuchareportaboutaprogramsectionbeforeplacinganybreakpointsinthatarea,sothattheuserwouldnotarriveatabreakpointanddiscoverthattheeventshewishedtomonitorhadalreadyoccurred.Thenextsectionshowsanexampleoflocalizedinformationpresentation.rg#*u$(gg%r)9gug)r+gug+rg1u2gg3mpgMrb)D &- 5F88>PDH_gu "(+-&1#6:~<AF'u\ r \\Y, "(*]-F/ 7:>>@C<HVO- #%c+,38<@CFHS %'U(,.V2R8 ?BVI5P !;%6* 25B8CqFoI@N [O$ +G,/N29699

 B1| !s#i *T,2L3{6n;;<?^CGP?o!%^(6-15C8;?B\DmI@<<?!")p 14k8:k= Fr9pk!(B+ 2r 9;xABD7*A|W &* ,z1>3 7H9 ?7Dj 4i 0i#'K-O/48>7 F1J 4 5".'):+/~379k>}D.W! '),( 28x:?A H,$gU !. ),b.h38 ?H)cD$ /Y5<3?D& rN%u'+;0G1 8w @BD; # z !%2 ,V-032! 8<$@BvCGO J. "&J*5-2 :=B<Gg!!e$), 4'6; CFgCr"j$(N 027E9?FA HI |,%, 3 :=KCED"K$!#(*.2 367\;Ay?V c??|+G??+ y?4|6??6 ?{@yA??=u|=uy=u|+;=u=u+/E0 : ;;+:/D0 : y:&|:&y:&*86V50 3o1V c110:.|.y(..)5w*:j V$&] .>/1!4Q9e;@ ((c(&#(-(5(=d(E%(`E(`E(`FF(`F(`G(`Gg(`G(`H((`H(`H(`II(`I(`J (`r(($1 $'+V,/I 79O; CkE"+ \ $#O&M).D15<9B B1FHj   &5(y-/H1 8>,C2Euq "%)_/24 8Y;={> G%vd# r#(/1577 =D]#*t-26X8 ?BFH 9 #C(U,>.K06j<BF; w ! &(-g/4!;AD TVm$eCHAPTER4:SOLUTIONTECHNIQUES88documentationmustexplainthedistinctionbetweenthetwotypes.Distinctsyntacticandsemanticbreakpointscanbecombinedwithshowingtheeffectsoftheoptimizationstoprovideausefuldebugger.Figure4-3showsaprogramfragment,asourceviewofitsoptimizedform,andasampleuserinteraction.Anotherwaytoimplementthedistinctionbetweensyntacticandsemanticbreakpointsisanalogoustothedistinctionbetweenstatementbreakpoints(specifiedbynumber)andprocedureentryorexitbreakpoints(specifiedbyname)inconventionaldebuggers.Abreakpointonaselectedstatementalwaysusesthesemanticmapping.Abreakpointinsideacontrolconstruct,suchasalooporblock,isobtainedbyrequestinganINSIDEbreakpointontheconstruct.Thisimplementationdoesnotdirectlypermitthefinercontrolofthesyntacticbreakpoint.21 y _ 5;22 FOR i IN [1..n] DO23 a _ b+c;24 b _ y/i;25 c _ d*2;26 a _ i-3;27 e _ y/i;28 ENDLOOP;c _ d*2;R1 _ i; temp _ 5/R1; b _ temp; a _ R1-3; e _ temp; ENDLOOP;i _ R1;Optimized sourceSource@#@#C@ C@@CC@FOR R1 IN [1..n] DO> SET SEMANTIC BREAK AT 5> STARTsemantic breakpoint reached at 5syntactic location is 2 (loop invariant)not yet computed:i _ 1;a _ b+c;b _ y/i;6@#@@#C@ C6@@CC@Figure4-3.Localexplanationandnewbreakpointtypes.rg#*u$(gg%r)9gug)r+gug+rg1u2gg3mpgMrb) H " )/ 1k4^B$ ,{/1 7w:@BrFH[ b"P#k*W.1,5<6i;B3CaGYuX %)(" U{Xvk#&< -<28;A IR] U%, 3 9;ADkO L %',j.T 6 >@U GIM77!"B$*13> :W>?D Ju+3pL| %' .u0JuJu1rJu5A h@ GG f#['*+-|2/36H; DDcD&#D-D5D=dDE%D`ED`ED`FFD`FD`GD`GgD`GD`H(D`HD`HD`IID`ID`J D`E9E9=;97531/3=3;3735 33 31 3/ 3-TVm$p6l@@#\TVm$39%#!(   #w2s"& .C03 :}NNcN&#N-N5N=dNE%N`EN`EN`FFN`FN`GN`GgN`GN`H(N`HN`HN`IIN`IN`J N`r.TVm$CHAPTER4:SOLUTIONTECHNIQUES89Asamoreelaboratewaytohandlethestatement-mappingproblem,theusercouldspecifyalistofconstraints,suchasAFTERstatements1,BEFOREstatements2,orINSIDEconstructc1.Ofcourse,aplacesatisfyingalloftheseconstraintsmightnotexistintheoptimizedprogram.Adebuggerthatordinarilyprovidesexpectedbehaviorcouldalsoprovideacommandtodisplayanewversionofthesourceforaregionoftheoptimizedprogram.Thedebuggermightalsoallowtheusertoseeotherstaticordynamicinformationaboutagivenprogrampoint,suchasuse-defchains,deadvariables,andrecentcontrolflow.Asseveralresearchershavenoted,thestaticinformationcollectedbyanoptimizercansometimespointoutprogrammingerrors[Lew74,Ferrante83,Ottenstein+83].Forexample,adeadvariablemaysignaleitheralogicalerrororatypographicalerror.Severalprogramdevelopmentsystemsusethisinformationtowarnusers(atcompile-time)ofpossibleprogrammingerrors[Masinter78,Alberga+81].Requeststosaveavariable'svalueoracompletecheckpointforlateruse,ortoexplicitlyenabledynamicinformationcollectionincaseaprogramexceptionoccurs,alsofallinthiscategory.Althoughnotinanoptimizedsetting,Feiler'sLOIPEsystemallowsausertosaveoldvaluesofvariablesforuseinspecifyingassertions,suchasloopinvariants,tobecheckedbythesystem[Feiler82].LOIPEalsoallowstheusertoexplicitlyrequestthatanexecutionimagebekeptsothatexecutioncanlaterberestoredtothatpoint.NavigatorhasaSUSPECTcommandthatenablesthecollectionofdynamiccontrol-flowinformationforagivenprocedure.[SeeSection5.8.]4.3TechniquestosupportexpectedbehaviorForexpectedbehavior,thedebuggermusthidetheeffectsoftheoptimizationsfromtheuser.Thusthemajortechniqueinthiscategoryisaddingnewdebuggeralgorithmstoprocesstheadditionalstaticanddynamicinformation,therebygivingtheuserasanitizedviewoftheexecutionstate.4.3.1AddingnewdebuggeralgorithmsToprovideexpectedoreventruthfulbehaviorfromadditionalstaticordynamicinformation,thedebuggermustprocessit.Thenecessaryalgorithmsfrequentlyresembleflowanalysisalgorithms.Forexample,iftheoptimizerpresentsthedebuggerwithaprogramflowgraph,thedebuggercouldwalktheflowgraphtodeterminewhichvariablesmighthaveincorrectvaluesatagivenprogrampoint.Whenabreakpointisrequested,thisinformationmightbeusedtotriggerthecollectionrg#*u$(gg%r)9gug)r+gug+rg1u2gg3mpgMrb)!d#'*5;>KALE I_g8 Uue_g_g 9r_g#*#u_!*r_g+4u,)_g_g,r_g1[7u_!8-r_g89u;_g_g;r_g@#F$u_!Fr_gGLH\H P @!% ,]0T257:@sYj #E)/48;AABI@VN\ %'e(,.17>@FSo"&:( - 5;9):_>CGPs r #&K*w/1365N9 @DNHN  ""$ *L,37q9 BuFN N GKH  reKHKH^!V't(,25h9=?OCGIH | &B .x3}58 @.AEYHE f ':u+0EE+ r0EEu1EE2~ r7EEB/ $C(*+Y1k 8:>IA@C.E ?n2 " &B'*+1C7d;>@BE<af!&+0|5 9N:=?\BuDI590 "J ),^.71 8T:.Dw !al# "'+.12:7;%<?>Esvd" rs P#(.Y1 84;=~C 0 #_)F / 6V;>C {: &4(.y128 >A,G#/52#~'-b1g4:>@fAE` my !O '* 2=6B8A;=GBLD TVm$CHAPTER4:SOLUTIONTECHNIQUES90ofoldvaluesofthosevariablesand/orthecollectionofdynamiccontrol-flowinformationalongtherelevantpaths.Whenabreakpointisreached,thedebuggerwouldexamineanypreviously-collecteddataorcontrol-flowinformationandrelateitbacktotheflowgrapheithertotelltheuserwhenavariable'svaluecannotbecorrectlyreportedortoreconstructtheexpectedvalueofthatvariable.Hennessyconstructedflowgraph-processingalgorithmstofindthesetofroll-backvariables,whicharevariablesthathavebeenassignedanewvalueearlierthantheywouldhavebeenintheunoptimizedversionoftheprogram,andthesetofroll-forwardvariables,whicharevariableswhoseassignmentshavebeendelayed.Inthepresenceofglobaloptimizations,thesesetscouldnotbepositivelydetermined.Hennessycouldsometimesreconstructtheexpectedvaluefromtheinformationintheflowgraph.IntheNavigatorsystem,breakpointinsertioncantriggerthecollectionofdynamiccontrol-flowinformation.Thedebuggerprocessesthecontrol-flowinformationtodecideamongseveralsourcealternativesinacross-jumpedregion.Asanotherexampleofspecialdebuggeralgorithms,data-flowequationscanhelptodeterminewhetherthevalueofavariableisalwayscorrect,sometimesincorrect,oralwaysincorrectatagivenprogramlocation.Adefinitiondofavariablevreachesaprogramlocationpifthereisapathintheflowgraphfromdtopthatdoesnotredefinev.Therefore,reachingdefinitionsdata-flowequationsshow,foreachprogramlocationp,whichdefinitionsdmighthavecreatedthevalueofavariablevatp.Reachingdefinitionsdata-flowequationsarenormallycreatedbyusingtheunionoperatortopropagateadefinitionsetthroughaflowgraphnodethathasmorethanonepredecessor[Aho+77].Iwillcallthisformmay-reachdefinitions.Incontrast,must-reachdefinitionsareformedbyreplacingtheunionoperatorwiththeintersectoperatorinthereachingdefinitionsequations(similartoavailableexpressionsdata-flowequations[Aho+77]).Supposethatmay-reachandmust-reachdefinitionsarecomputedfortheunoptimizedflowgraph,yieldingequationsUMayandUMust,andarealsocomputedfortheoptimizedflowgraph,yieldingequationsOMayandOMust.Foraprogramlocationpandadefinitiondofavariablev,thefollowingtabledescribestheconditionsunderwhichvwillhaveanincorrectvalueatpintheoptimizedprogram.Thisinformationcouldalsobegathereddirectlyratherthanbycomparingbefore-andafter-optimizationequations:always-correctandalways-incorrectinformationcouldbepropagatedthroughforksandrg#*u$(gg%r)9gug)r+gug+rg1u2gg3mpgMrb)0tB"') 0D27 ? G/_g"@$ +-36=gB5HN\=I  ' /m2+57Z:<]>EMI@YZ "!%*x,2A79; BE2W#ES j, 35[8h:= >D PA! $i)+ -159<@ACFHN    &),.c0N 8* >oBE3KI& /!'),137 @DkG#HWH q !'+2O 9b;A~E(HE lz B1W 'q-/u36 <=C- ?o :  &(] 0 79B=BF<  !_9$* 1 7$=I?BDl6Wg!#/',U2 8:>DF%G:3G x"3r3$ %'x,L3r3t-33.:r3239cx>3r3@AEFG0 x 0r0ux 00r0!$t'*3x/0r00{1 t8009>>D r0D.8i#x)0.r.**. x5.r.7!;>`C+EI5+P4x+Pr+Px+Pr+Pc! (.517=BDH(o "= (*0@18.;>AGDHC% uA%%r%%eb "%t(s%%). r4%%6G8 t=%%>%De r# 9 k$f)- /p4:v<(>D J! (.u5% J J5ur: J J:z;AmD@  W!(*1, 4s ;A@vF4"%(*1 8=|CH7Wx"r$(&' x.>r/1D2gx7r8n9C;AEDV &x IDrD!$z')/3jx5DrD68K:A@G Q$(,/18|=)?  r!$+4 268j ?DH7 TVm$CHAPTER4:SOLUTIONTECHNIQUES91joins.Thedebuggercouldusetheinformationtoprovidetruthfulbehaviorfordisplayingvariablevaluesatp.Toprovideexpectedbehavioratabreakpoint,theinformationcouldbeusedtodeterminewhichdefinitionsofwhichvariablesmustbesaved.vincorrectatp?dBOMust(p)dBOMay(p)dBUMust(p)dBUMay(p)alwaysyesyesnonosometimesyesyesnoyessometimesnoyesnono4.4SummaryAsmanysectionsofthischapterhavementioned,thedifferentsolutiontechniquesproposedherecanbeusedincombination,eachtechniquesupportingtherest.Withthewidevarietyofpossibilities,itisclearthatprogramdevelopmentsystemsneednotproduceonlyfullyoptimizedprogramswithnodebuggingcapabilitiesontheonehandandcompletelydebuggableprogramswithnooptimizationontheother.Theselectionofasuitablelevelofuseforeachtechniquetoprovidetheoptimalmixofoptimizationanddebuggingcapabilitiesremainsanopenresearchtopic.TheremainderofthisdissertationdiscussesNavigator,aprogramdevelopmentsystemthatusuallyprovidesexpecteddebuggingbehaviorfortwocontrol-flowoptimizations:inlineprocedureexpansionandcross-jumping.rg#*u$(gg%r)9gug)r+gug+rg1u2gg3mpgMrb)~!$9 +-Y2W7c=?7 E_g=x_gr_g"% *,. 5|8 ?CEI@\dr A!&+/+1YYcY&#Y-Y5Y=dYE%Y`EY`EY`FFY`FY`GY`GgY`GY`H(Y`HY`HY`IIY`IY`J Y`Z+Z+xWrWxkWrWBxW |TVm$q!TWTVm$rW"x&WrW'xW+l TVm$q,DWTVm$rW-x1HWrW2 xW5TVm$q6WTVm$rW7x DA $>'- 47o;>A,DI5>U %f -26!8>A8D;Il!B (|*-/3~6R =j D8 * %"(-/v059:=\?BI@6` 'C)0 7<>{AG#2{Z6 'f-P 4/5|;. CH /%s+-N/ 7 @Dk,Y &TVm$MATH TIMESROMAN GACHA GACHA GACHA GACHA MATH TIMESROMAN GACHAGACHA TIMESROMAN TIMESROMANY TIMESROMAN TIMESROMAN TIMESROMAN TIMESROMAN TIMESROMAN HELVETICAq(  ) 2: C KL U ^ g p|x s h  vj/ []<>NewChap4 Monday, May 7, 1984 10:03 pm PDT