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;addingpïg/îMÓqïVÑî'Aî0ÍïP3î!�î+| rïI–î¤î£î!î 3 î(ïî,á î3Íî7î=ðîD„ïFÔîâî îîú î#äî&0î*ðî.‘î0Yî3ð î;=î>#î@‘îD ïDîâî²îî"îÒî î$î)î*âî0 î6«î9Óî<4 îCîEâïAQîâîüîîîÓî$î&v î-Rî0 î5,î8Fî>ï=»î¤î îïî–î î$ùî'Tî* î2oî6 î>€îCd ï:úîâîRî» î½î"Uî$ î)Lî+µî2*î7ßî; îB•îE*îG#ï88îâîp îîù î#£î'­î)xî.jî0æî3ýî75î9±î>î?õîBq ï5wîâî“îÝîÁî� î%Ãî'Ó î/íî3Hî5"î7¡î>.îD¹ï2µîâî î î!0 î)§î+eî2î4�î6‡î;3î<Ûî@hîC9îDáîH�ï/ôîâ î¯îs î!kî#Õï,^î¤îŒ îxîVî#rî(šî.Zî1…î3õî6ÿî8½ î?öîBfîFÆîH�ï)�îâ î}îQî î#cî%àî,i î4�î6Lî:4î< î>ˆ îFŸï&Ûîâî¼î®îVîÙ î#Øî&Éî+øî1Øî7«î:éî=lîC˜îEjï$îâîQî°î†îÁîzî!Ù î)Óî/bî2î4xî8{î>ç ï „î¤î¥îwî¶îÇî"ÿî&°î(Pî+µî.S î5lî7�î>1îD„ïÃîâîpîîÎîYîÙî,î#&î$Öî'7î-� î7~î=ªî?ZîA¼îFPîI5ïîâî� îÊî­î#Pî&¢î)#î,‹î1î4¦î7 î=²î?wîCîI@ï@îâîq îxî1î#êî*Vî0Áî4vî8™î:íî=Ûî?‰îB+sï¢îâîîD rï î¤î²î[ îÅî$ î&Êî(ñî,cî.Hî3‰î7«î<ùî>óîDæï ¾îâtîÏï ¾ï ¾î€îEîê rî"¸ï ¾ï ¾î#¢î'¾î*+î/ôî4Öî7œî;Íî=‰î?ötîF‡ï ¾ï ¾î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,byrïgî#*uî$(ïgïgî%rî)9ïguïgî)êrî+ïguïgî+ærïgî1Íuî2´ïgïgî3mpïgîMÓtïb&îâî— rîeïb&ïb&îšî!î#¸î*î/Fî4î6Çî=‹ tîD’ïb&ïb&îE ï_dîâ rï_dî±îoî(îË î&© tî-ìï_dï_dî.p î4Xî:Ø rï_dîAäîC¢îG[ï\£îâîÔ îFtîþï\£ï\£î ‚ î'Kî+Óî1î2¦î4òrï\£î:Wî<î? îA< vïVÙîâîÏîdîã rïR¶î¤î¡ î[îøî$åî'î)¡î/�î4/î6¿î;¸î?P îG§ïOôîâ î îÌ î Ðî%Aî(î)zî-Qî/™î2 î8õî<%î?�îCd ïM3îâîƒî™îîìî!¶î%Èî)úî-Fî/î1�î5Ûî9Gî=!î? îAþîD‚ïJqîâî¢î^î…îOî%î)î+ýî2„î6jî9âî@ÍîBjîHÜïG°îâïDî¤î•î î• î$9î&�î(™ î/a î7î='î>¬îA% ïAYîâîqîÈî-î$ î%×î(Wî,Çî2wî5Nî:!î?ýîE–îGeï>—îâîÑî³îFî“î#®î%�î(±î*“î-& î7#î<ÆîAI îH7ï;Öîâîîn î1tî"¶ï;Öï;Öî#Qrï;Öî'J î.êî0¹î3qî7î;3î=ÔîAîC îHóï9îâî�î î î&ûî.î/× î7{î=$î?CîBîC˜îIƒï6Rîâ îÞî@î�î ˆî#5î%sî*î+öî. î3wî5sî<.î@ªîB¦îD¹ï3‘îâî§îZîd î%j î-*î1Cî3Ùî::îAîBÔ ï0Ïîâî¶î@î¸î Ùî%Wî*7î.<î1 î: î@©îF÷ï.îâîUî±îîîOî#qî%¹ î,ˆî28î5•î;tî??îBÈ ï+Lîâîªî–îNî ƒï'·î¤î<îZî}îÿîÖî!œî%î'½ î/^î4>î8Æî;< îCLîH�ï$õîâîÚîD î!¦ î(nî+xî-Æ î5—î9gî;µîAÎîHï"4îâîøîüîPîcî"Êî$�î+ î,ñî24î6Ýî8ñ î?·îE3ïrîâ î}îQîf î"•î%hî'Šî.‹î0`î6±î9 îñ îF“îHBï4iîâî“îÔî�î&`î*î,jî0Åî7î9î=PîA”îBöîDl ï1§îâîAî(î î"Lî'6 î.ùî2üî5%î9¹î;Ÿî=îB’îG|ï.æîâîh îfî™î ûî&î(Tî-üî0%î2³ î9Ó î?ÞîA!îByîDÛï,$îâî%îT î|î"î$Îî*¥î- î1^î3î5‚î8Ùî?˜îDîIÅï)bîâîTî-î…îÀî#î$¤tî'ßï)bï)bî(crï)bî,î2Yî4î5Eî7�î9Pî> îCÒîEuîGÞï&¡îâî›îi ï# î¤î¤îæ î#|î'÷î+jî0Sî3î7Ô î>îA“îC�îI@ï JîâîZî<î½îšî eî$�î'Qî-î.Šî3� î9Úî>Yî?›îB®îGýîIÅï‰îâîÙî.î¦îNî î!aî'üî)Ùî-nî/æî4Æî8Gî;Çî@îBÓ îI*ïÇîâî²îîî©î!]î#¾î(‰î,4î-îî0Oî5‡î9Šî4îAÊ îI@ïÁîâ î�îîáî?î"ïî(# î0…î2ªî6µî;êî@îE¹îGOï ÿîâî îE î[î!qî#Ôî'wî)4î*bî/ô î6†î:úî<(îB¯ îI*ï >îâî/îÇî¸ î K î&äî*+î-¾ î5Hî8°î:¡ÿ 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.rïgî#*uî$(ïgïgî%rî)9ïguïgî)êrî+ïguïgî+ærïgî1Íuî2´ïgïgî3mpïgîMÓrïb)î¤îaîõîÉî bî#ë î,Rî.Èî1~î3Yî7žî97î;€îB|îG/ï_gîâî®î? îYî!Úî&Ãî*Lî,øî0Jî2Ëî8[î<& îB³îEïîG:ï\¦îâî îDî¬î"~î%ïî(ƒî+½î.&î3eî7. î=£î@ÇîAúîE¸ïYäîâî6îŸ îJî î&Oî+œ î3Iî5¿î:ˆî@ÊîF[îHþïW#îâîîÔîCî»î_î ¬î# î)ðî0+î5rî7Fî:$î<“îB­îEHïTaîâî*î¼î^î¦ îSî$rî'Âî* î0ðî6”î8‚î>}î@5îEIïQ îâîx î&î²îÆ î&Vî)•î.äî4)î6î8‰î>;îAîG îH�ïNÞîâîTînî-îŽî¾îaî €î&î,9î1eî3—î9î=í îEîF&ïLîâî€îJî.îîî Ôî#Öî'‰î)üî.Kî1È î:Óî>:î@îFRïI[îâ îÏîîØî 1î#íî(-î*ìî-<î2éî6„î8-î:~î?¥îADîB^îFÕïF™îâî)îlîØî˜îGî¦î#©î'Sî*Mî+vî12ïCî¤î'îˆî’îÀî$ø î-Vî/·î4€î7éî;¶î>„îCd ï@Bîâîî× îî$9î&î(dî+Êî/\î1—î2¿î5¶î;Cî=¡îCÈîG’ï=€îâ îrîXîÇîoî$/î)Íî-Èî0®î5þî:î>·îBéîFHï:¿îâîªîkîçî -î$@î'£î*ûî-wî0@î3*î5¦î9lî;Aî=½xîCï:¿rï:¿îDˆîGPï7ýîâî¡îêîiîLxî ï7ýrï7ýî õî!õî$¢î&sî(ö î1(î3ˆî4Õî8 îA8îEsîGõï5<îâîøîBîÖxîyï5<rï5<î¿î î"Zî(¦î*ïî0âî4˜î7¨î;tî=ÿ îDw ï2zîâxîJï2zrï2zîÑî©î¢î\î!Êî#£î(3î+,î-¶î3†î9@î:Öî@îCd ï/¸îâîîmîî î0 î$ôî&¢î*+î+— î2fî3�î7î9üî;µwï*Áîâî0îWî  rï&žî¤ îuîIîî$ùî*Žî/ î5ãî8Àî<ÿî@kîFLîHþï#Üîâîî³î¤î¶î#ìï Fî¤î– îu î&î)ªî,rî0ßî72î8ýîîçîïî&î!pî%@î+³ î3 î7î:Œî?õîD4 ïÃîâî‘îØî„ î{î%èî'¢î+»î/î2^î<‰î@ŒîDñïîâîyîWî›îIî"Àî$¿î'Çî)…î/‘ î7¯î:u îB“ ï@îâ îyî¶îú î$Î î+#î16î4³î:Ýî<· îD¯ï~îâîXîï î î@î î"�î%Ÿî'ÿî,éî1Pî7-î:¶î>ñîDÎîFŸï½îâ î·îwî+î äî$%î*v î1¢î4tî:`î<î>�îBGîDîE`ï ûîâ î‘îÞî¬î òî$… î,î.ÿü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,encodedboththeoptimizedandtheunoptimizedformsoftherïgî#*uî$(ïgïgî%rî)9ïguïgî)êrî+ïguïgî+ærïgî1Íuî2´ïgïgî3mpïgîMÓrïb)î¤î(î‰îµî!“î+‰ î4aî7”î9Dî<�îALîCÄîEîI*ï_gîâî1î‡î¶î"î(]î+�î.òî3Kî6�î<4î>õîD®ï\¦îâî î{ îçî! î$]î)'î-_î0î2bî7éî=�î?3î@HîD¹ïYäîâîUî7îIîjî Œî%Rî'4î,}î/Ÿî4Oî6î9¬ îAv îH7ïW#îâî î½îwîâî^î!#î&œî+àî.Kî2C î;0î>îC»îIƒïTaîâî<î»îsî"Èî%µî*î.î1üî5nî;åî?ÛîB¾îFŸîH�ïQ îâuî´ïQ ïQ îîîrïQ îÛî"=î$¡î(Dî,î.‚î46î9öî;³î<àîAkîG¤îIïNÞîâî¿î±î»îhî!·î&èî(‘î*àî.Ò î7@î<ìî>×îA& îHïLîâî�îcîÙîüî"Dî(Lî*µî0ÿî7?î8âî:î?°îEïîH±ïI[îâî�î×î·î#]î$þî'“î+qî-`xïI[î2êrî4šïI[ïI[î5aî9î;õ îC;xïI[îE=rîFïI[ïI[îF¤îHÇïF™îâî°îAîî ¤î"Aî$Òî(®î*˜xïF™î0"tî1ÒïF™ïF™î2ƒrïF™î56î8 î?LxîA,ïF™rïF™îBîCùîFhïCØîâ î)î½îî"¸î%¹î)Úî._î/½ î8Óî=!îBŒîD…îIÅïAîâî“îZîîs î&­ ï=�î¤î îvîîßî"Iî( î.ßî0£î6ãî<ªî?îC¥îHcï:ÀîâîÁî¥îûîIî¡î$Òî'Úî*(î-î/Šî4î8î=¼î@ îDíîF2ï7þîâî’î�îˆîåî!Ò î(¯î.Mî3ßî5çî8(î;¨î=C îD ï5<îâî:îâî“îµ î!Çî%î1Sî7Íî:î@îD4 ï2{îâî1î— îÏî Ï î'éî+9î-¶î1 î4 î:Ëî@CîBÖîE>ï/¹îâîwîÃî[îîî$î)¸î/üî6vî<ÏîB¸îD îFìï,øîâî¡îÖîGî‘î[î"û î)Æ î/Õî5¸î8ãî;SîAîG:ï*6îâîAî‘îJî©îûî#î(ªî+Äî.$î3¿wï%@îâî0î3îò rï!î¤îÀ îpî cî"èî(Èî,¹î1.î3‘î6 î=!î@kîCîH�ï\îâîHîf î ;î"•î&ßî(“î+¨î1Sî5Éî9°î;è îB ï›îâî™î©îæîv î$ ïî;î%îóîÒî"Aî$³î+1î/0î3e î:èî<}î>ïîD½îGÉïDîâîLîÀî4 î}î" î%[î)·î.kî0Fî3æî7Óî;÷î=Òî@^ îHï‚îâîlî£îxî!`î'žî-b î4õî7µî<…î?öîF0ïÁîâîÛ îŽî¬î$oî&¾î-0î.¸î3ßî5}î:®îîâîîiî³ î#©î)6î,†î.ùî5yî8Cî:¶ îBÄîFÂîH� 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.rïgî#*uî$(ïgïgî%rî)9ïguïgî)êrî+ïguïgî+ærïgî1Íuî2´ïgïgî3mpïgîMÓrïb)îâîžîrî÷îe î( î*ëî.§î2òî6£î9+î?\îCPîHMï_gîâîVîöîJî!Šî#?î%¦î'÷î+“î-=î.Yî3�î6î;§îB”îDåï\¦îâîÄ îîîdî! î$Îî&�î)î.aî1ßî4U î;àî=Æ îE]îH�ïYäîâîîî°î—î$¼î)Qî,} î3}î7Cî;Äî?Q îGÈïW#îâîš uîïW#ïW#îQî•î#ãrî&fïW#ïW#î'Åî+xî-©î3š î;½î>÷îDW ïTaîâ î"î~îþî!² î)†î+áî0-î1âî5î9î³ïKIïKIî@uîBvîGÓïH‡îâîbî±î/î! î$G î*äî,)î.î3\î4ãî:bî<ó îDl ïEÆîâîZ îÎî"î#Çî)ñî,Ôî.î1"î5/î7­î:"îA2îCÒîH�ïCîâî©î�îéî “î$î'òî)Ùî,§î.lî3¯î8mî>4î?îîBZîG.ï@Cîâî5îyîèî(îÊî"2î&Hî*(î+Ôî.à î6]î7þî9Ìî=µîDb ï=�îâîØ îWîãî$Ìî)(î-¤î01î7"î9w î?ÙîB½ îI5ï:Àîâ îxî/î)îâ î$yî%ñî*î-Fî3§î6I î=ÔîB’îDlï7þîâîŽîŽîMî î –î#Kî&Aî'øî-°î0{î5�î7;î:iî?�îA3îDa yï5<îâuî�ï5<ï5<îbîp îîiî\yî�ï5<uï5î41î6¼î9zî;e î@øyîB]ï5<uï5<îCyyîDÖï5<uï5<îEòîG°ï2{îâ îðî<î×îÜyî'ï2{uï2{îÔyîï2{rï2{î ñî%rî'âî,î.pî4jî6¸î8ƒî<€î?_îAÐîE3ï/¹îâî/îÞî.îkîEï,$î¤îÔîèî î"1î&Ùî0äî5)î70î;îB#îD¹ ï)cîâ îMîî Ûî#!î' î-– î4mî6Öî<šî@nîDÆîG/ï&¡îâî›îÌîîŒîPî!î#}î)†î-Rî2Fî3œî6tî8Oî<Êî@^îB îDkï#ßîâîúî§ î†î"Vî(²î-}î3 î5Fî7�î<'î?î@´îCM ï!îâîï‰î¤î£î÷î¨î"iî&­î)³î+åî.: î4dî6î;— îCçîGÞïÇîâîî‚îêîýî!cî(&î,øî1}î5ì î= îC½îE_ïîâî? îÈîvî î"Ôî&‰î)@î-Wî/î3Tî5…î8Ÿ î@)îBÓîDÄïDîâîŒî=îžî°î -î#î)mî/*î4î74î:žtî>˜ïDïDî?HîA¬ rîHaïDïDîI@ï‚îâî{ îëîïî!Íî'Åî,“ î4Oî7œî;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.rïgî#*uî$(ïgïgî%rî)9ïguïgî)êrî+ïguïgî+ærïgî1Íuî2´ïgïgî3mpïgîMÓîâïbÏþÀî¢ïbÏþÀîcïbÏþÀî&#ïbÏþÀî-äïbÏþÀî5¤ïbÏþÀî=dïbÏþÀîE%ïbÏþ`îE…ïbÏþ`îEåïbÏþ`îFFïbÏþ`îF¦ïbÏþ`îGïbÏþ`îGgïbÏþ`îGÇïbÏþ`îH(ïbÏþ`îHˆïbÏþ`îHèïbÏþ`îIIïbÏþ`îI©ïbÏþ`îJ ïbÏþ`rïc8ïc8wï_¢î#½ î+î.­ rï]'îcî$Û{î*ï]'rï]'î,î0�î3ÖïZ¬îcî$Û{î*ïZ¬rïZ¬î,î2—î5ÿïX0îcî$Û{î*ïX0rïX0î,î.àî0™î7^ wïT›î$]î)öî. rïRîcî$?î*·{î/ãïRrïRî1ûî4¼î6uî;(ïO¤îc{î#çïO¤rïO¤î%þî)† wïLî% î-W rïI“îcî$?î*·{î/ãïI“rïI“î1ûî5Lî8 î?˜îC¼ïGëî5¤î:Rî<úî@‰îBîD¹ïEpîcî$?î*·{î/ãïEprïEpî1ûî7”î9MïBôîc{î$ðïBôrïBôî'î)Éî+‚ î3: wï?_î­îî7î$Åî+:î/0î4¨î6‚î8áî<2îâïL îFïîH�ï!™îâî îŸîèî*î#Ëî%®î*î+õî/.î4bî78î8®î;šî@�îF<ï×îâî îùî]îöî"hî(øî,»î/(î3dî5*î:óî=TîCîFFïîâî‘îð îêî!Uî$î)Òî/î1äî5+î9èî<^î@äîB ïTîâ îøî«îxîJïTrïTî «î%yî&§î*±î,8î.œî1Æî4@î7¡î=bî@úîD%îGÈxï“îârï“îWîäî\îîÊî î"˜î)Hî+î-‘î1¬î6Ž î=Ðî?ùîEïÑîâîî²î´îðî!, î(Hî*�î0,î15î4qî5ÿî8>xî=TïÑrïÑî>�îB.îD¹ïîâîLîîÉîÌî":î$yî%æî+¹î13î6æî9‰î>¡îBAîE<îGßïNîâ î xîÑïNrïNî©î�îî�î"zî&Êî-î0Vî2ãî6Wîî3æî6Uî;.îAsîE"îHþïQ îâîªîAîwî$î`î!xî% î,ªî0hî2Æî6!î;VîA=îGpïN î¤îsîsîõî¸î"$î'«î,Tî/e î6æî8‹î;�î>¯îDÛïKIîâî“î>î¤ î" î*~î/5î1šî5¹î9î;Iî?ßîD4 ïH‡îâîÁî˜î|îÇî"ûî(dî.î2� î9{îÕîA–îG’ï@Bîâîlî?îŸî#£î&˜î)4î.;î/åî4ëî:¢î@NîB† ï=�îâï9ëî¤î´ îgî#qî&î*Zî,<î/^î5Aî7õî:êî=îBIîEï7*îâî2îîbî¶ î$|î&ÿî+“î-‘ î4¯î6kî8Øxî>ï7*rï7*î?†îCØîE“îG{ï4hîâîâî–î'îcî#hî%úî(–î,qxî.\ï4hrï4hî/ëî4lî5ôî7’ î?eî@íîCªîH�ï1¦îâî©î\xîï1¦rï1¦î†î(î"Áî(†î-ÿî0iî3aî7®î<ïî>²îA îH7ï.åîâî×îúîAî+î" î( î+î1=î4î6éî:`î<)î@’îF<ï,#îâî î¤îaî!!î$åî&£î)'î+•î/oî3(î5tî8}î=Ãî@‰îDMîF îH�ï)bîâîþîÀî‡îÿ î!+î%öî,:î/mî5Þî9øî?©îAÿîE_ï& îâî?îœ î1îèî#.î'à ï# î¤î;îÈî9î(î Ø î(ƒî+.î.×î0¦î7€î> îD˜îG9ï Iîâî™îžî)îîpî , ï´î¤î&î‡î�îýî ²î"£î$]î&½î*G î1Òî7Üî9‹î;ëîBBîFàîI˜ïòîâîŸîcî³îŒ î&î*ˆî,2î/Ö î8î:iî@cîD ï0îâîüî‚îøîÖî Y î)uî,µ î5Xî8Lî<1 îDÕîHïoîâî¿îêî›î!Nî#‰î&vî,“î1œî4î:ôî>œîDçï­îâ îâîÜîð î(šî-Äî1»î3×î9Pî;w îC"îE¬ïìîâîÁîzîÙ î7î#² î,1î.„ î5–î8 î9ºî=î?Øï Vî¤ îî!tî$î("î,äî.Îî2´î9î;î=&îCÃîIƒ ?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).rïgî#*uî$(ïgïgî%rî)9ïguïgî)êrî+ïguïgî+ærïgî1Íuî2´ïgïgî3mpïgîMÓrïb)îâî‡îäîî£ î%�î(î-¡î/aî1Óî4½î9Qî<<îBWîF5îI@ï_gîâî´îåî2î™î!™î$î(@î)qî01î6ñî9yî<Çî?oîD¹ ï\¦îâîSîîËî î!Ç î)Vî,î-Çî/½ î6²î:¾î="î?‡îC+îGîHcïYäîâîQîîî Ôî% î,î0%î3® î:Àî?=î@ÀîBô ïW#îâîîÙî~î ¤ î(?î,Hî0\î2î4�î9~î;Hî=ºîB]îE=ïTaîâî1î[îÀîî"Gî$¼î+î0Ãî7}ïPÌî¤î¢î… îÙî!cî'uî,1î.î1o î9ìîEîD¹ïH‡îâîƒ îîyî Kî"ìî%Uî),î*Ûî/*î1&î6&î9mî=Ý ïDòî¤îâîAî¸î_ î'î)ºî.Òî1Jî7kî;Nî?¶îBçîE_ïB1îâ î¢î¦îGî•î"î$�î*°î.Òî5Áî’ îDüîHþï?oîâî# î îîhî"bî&êî+î- î2" î8¤î:iî<ÉîBÒîFžï<­îâî‚ î–î±î!öî(ùî.›î0“î7Hî= îB2îE2ï9ìîâ î†î�î ' î'î*„î1�î8>î<» îCÚîH�ï7*îâ î=îîÖî î&Ðî(¥î*»î.î/òî1ò î9Èî=eî@ZîC! ï4iîâî¿îûîãîyî!å î)K î/<î1šî3î5Kî8¥î;ÿî=2îB%îDa ï1§îâîÒîi î*î î$†î+vî0wî3Èî7Gî9B î@îîBêîGõï.æîâ îE îPî*î&4î++î1b î8¢ îAd îH7ï,$îâî® îmî î&s î.Fî2¾î8Ùî;—î?'îBÍîI*ï)cîâîÃî¡î!vî%fî(î* î2Lî4‚î9Nî:Óî? îG¨ï&¡îâî;î@î¬ î"Òî$¿î)Æî-lî.Ôî1F î8î9äî<‚î?lî@¿îC¿îE¬ï#ßîâîøî¶î} î!Þî#Þî& î+‘î1/î4Mî7Ûî<’î>ÓîC^îFFï!îâ î_îcîªî";î&iî(-î*ûî-�î2î4 ï‰î¤îìîfîlî!î"ëî%e î-Òî0Lî6pî9òî;ýî?î@ÚîCãîF]ïÇîâ îpî·îiî—î"Pî)î.Çî0Mî7 î;Øî=Hî>ûîCd ïîâ î¶î]î­î"\î$”î'Õî)Êî.mî2î9î>"îBåîG‘ïDîâ î_ îVî !î%Ïî(Mî,�î0 î3î5?î7Ó î>^î@îBgîHcï‚îâîóîöî¾îo î%"î&ùî+Oî-×î1î3>î9· îB]îDåïÁîâî;îîî¨îî_î# î*ˆî0`î4>î5Þî8½îîâÿ Ï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.Thedebuggerinsertsaninvisiblerïgî#*uî$(ïgïgî%rî)9ïguïgî)êrî+ïguïgî+ærïgî1Íuî2´ïgïgî3mpïgîMÓrïb)î¤îtîû î!}î%@î')î,Ýî.ƒ î5Jî<—î?QîAîF<ï_gîâîñîžî˜ îî!)î$² î+kî-î0î2sî5Äî9Þî>›î@IîC ï\¦îâîÅî-î\î/î"2î$.î)î*¼î0Vî5)î:lîî?¶ îE¬ï@Cîâî¾î î:î½î%’î(î+‹î0Lî5‘î7Üxî=¥ï@Crï@Cî?xîAÕï@Crï@CîB­îC˜îH�ï=�îâîŽîJxîƒï=�rï=�îâ î"Oî$î'–î-'î2Lî6gî8Éî;ÅîA îBM îI@ï:Àîâîâî¢îoî÷î#î%¢ î,wî1F î7¬î9–î<'î@xîAíï:Àrï:ÀîCzîGûîIƒï7þîâ î%xîï7þrï7þîóîHîî6î"¿î&ýî)Åî,5î/Œî4D î;î<&î@ îF÷ï5<îâîMî}îêîûîºî$P î+à î2ýî5*î9­î î@€îDJï,$îâîGîVîØî"î'Zî+°î1E î8Õî;õî>îD6 ï)cîâîcî@îÞîuî$î(Vî+¿î-�î2î4‚ î<.î=þîAîBÞîE`ï&¡îâîZî” î+î!î#'î(î)éî-"î.ðî1pî7ûî=ªî@åîCd ï#ßîâ î6îÁî€ î!Kî&‹î)Ðî,O î4guî;ï#ßï#ßî;_î=Šî?ˆîDQîG ï!îâ îCî2îŠîpî"Krï‰î¤î îbî!î&“ î. î4:î7I î>.î?ÑîC�îIVïÇîâî›î� î!n î)Cî,î2Šî5kî;|î?PîAÍîE^ïîâ î·îÍî"³î%î( î,ôî/Ìî26î59î9;î;˜î<ÌîCîD¹ïDîâîÚîb îžî"aî'ðî,ñî/hî5ˆî9jî<Þî?UîERîIVï‚îâî?î‹îÏî�î%î‚ î%[î(öî/î1yî6@ î> îA·îFÀïÁîâîéîîî"mî$Qî&æî+& î1�î4%î:dî>eîD@îFÕï ÿîâî—îBî �î'}î)î-œî0dî4¹î8Ÿî:¶î>#îC›îFšîI5ï >îâîƒ î îÔî íî"?î&?î)úî/{î5³î8´î>åî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,itcouldforcetheoptimizedrïgî#*uî$(ïgïgî%rî)9ïguïgî)êrî+ïguïgî+ærïgî1Íuî2´ïgïgî3mpïgîMÓrïb)îâ îÍî¹î î!]î#î'Pî+üî/î0Îî3Í î<'î>úîE`ï_gîâîî î0îîŠ î%Åî*Îî1`î4ïî6`î7�î<ËîB?îD¤ï\¦îâî« îðî#îëî Zî$î%Ýî(wî,i î3 î9Kî:¼ îB@îD¤ïYäîâîzîþî� î"àî&•î(pî.Bî/Úî5=î;;î=…îCxîG-ïW#îâî�î×î…îÕî4 î$î%Úî)!î*Ïî.šî0ùî5Î î>L ïS�î¤îrîuîþî´î"B î)Ëî-• î4¯î7Yî=)î>ÖîBhîEÙîG‘ïPÌîâî` îî— î"Ëî&–î(Pî)›î-qî3!î8yî;&î=8îCÇîGOïN îâî îÙî*îÈî €î$àî(õî+Rî1Yî3áî:aî=î@dîBÁ îI˜ïKIîâî?î´îîcî î Æî#”î)#î.Eî/›î2&î7Ìî:,î=Õî?6î@ŒîAø vïEîâîÏ î; rïA]î¤îrîìî›î"Jî(¬î+éî.kî1-î3î8yî:k î@Í îI@ï>›îâîvîOîÍî‡îgî"ñî%% î,þî0î5%î6’î9î:¶î@‰îB8îD˜ï;Ùîâî³î`î îîßî!î$î'¦ î.î1yî4î9’ îAîDîF~ï9îâî½îäîÆî šî# î*Àî,Jî.Óî5;î7î;wî>LîDzîH›ï6Vîâîsîµîî¿î"Q ï2Áî¤î� îî"î#þî'î-gî/ î66î9óî=îAåîH�ï/ÿîâîî©îKî!“î'Îî+¹ î4î7Òî9¬î?DîB”îDÜï->îâîoî°î)î•îòî#O ï)©î¤îù îšîíî ƒî$Ûî(V î0ºî4¤î9 îBsîE3ï&çîâîðîŽî î"Ñî'î(ƒî-Ñî0¶î7‡î:IîuîBâîE—ï¢îâîY îîÎî#Eî( î*î-ª î3Åî8 î;ïîAîCíîE¸îH�ïáîâîøî¡îãî`î«î �î$'î)ÿî.� î6]î9RîÌîA›îD‹îHþï^îâî îìî»îu î"Æ î)cî,ûî/Œî5Lî92î;'î>'î@¸îE½îG§ïœîâîcîîsî$®î&ôî+Ðî-[î.üî1Æî7Ìî9¯î>¬îAAîDnîFRïÛîâîÇ î;î!¶ î)lî,½î.�î4]î6èî: î=<î?ÝîCÇîE¡ïîâîúîZîèîàï „î¤înîîÚî ™î#Òî&$î)àî+Œ î4Êî8î9ºî;î>ÀîB0îD‚àTVm$›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"nosourcerïgî#*uî$(ïgïgî%rî)9ïguïgî)êrî+ïguïgî+ærïgî1Íuî2´ïgïgî3mpïgîMÓrïb)îâî´ îÉî0î!î#~î)'î*ñ î2(î3Ûî8$î=kîA”îEzîIVï_gîâîlî0îâ îÁî!Sî'‚ î.åî0wî3ãî7� î?îA±îCB ï\¦îâî¤î& îî#î'ùî.î1gî3V î::îÉî@ŸîC&îFËïM6îâîFî1î6î#î&‘î(Šî.e î5Âî8™î<¥î>‰î?ÿîCœ ïJtîâ îu îãî"þî%íî(î.oî0+î1wî4ë îIî@ËîF÷ïG³îâîƒî³îõîî"’î&,î'’î-†î3µî6öî8Rî:¬î@„îDkïDñîâîtîkî,îLîëî"oî&ñî)Wî/áî2rî6.î8àî=Å îDÓîG¨ïB0îâîoîZîùî"§î'Sî+¦ î4Tî8Oî;æîBšîGßï?nîâî2 îN î#`î%”î&àî+'î.Ýî4"î7­î:qî<„î@[îB,îH�ï<­îâîîåî®îCî#Iî%Hî' î,îî/³î1pî7{î9éî>ÀîEîH±ï9ëîâîjî+î”î" î&ý î-ûî02î5Cî;Eî=žîC îGï7*îâî¤îïî_î^î²î#8î)¢î+½î1¸î4Nî:î@HîEÌîH�ï4hîâî§î6î‡î Ãî#›î(Òî*Šî,ô î4ùî84î;™î?ýîCÈîFìîH�ï1§îâî™îRî| îŽî§ï.î¤î¿î"D î)¦î-€î/Sî5�î8Êî; î>¹ îEkï+OîâîVîïîJî&î#î&²î*& î2Mî6¨î8nî9Åî=oîBEîEï(Žîâîz î±î!dî#=î'Hî(Þî)ðî/“î6î8Cî: î>•îCîFsï%Ìîâî?îzî_î/î"A î*xî,õî3”î5ûî9Œî?oîC» ï# îâî^îØîœîpî´îŠî&Hî'Îî.Vî1Øî3î61î;Úî>TîAhîEOîH�ï IîâîŒîEîîIî!¸î$ î+— î2¨î5_î7:ï´î¤î¥îZîHî Wî# î)åî+ô î4Bî8c î?ˆîBîFŠîH�ïòîâ î îÙî î$ÿ ï\î¤îÊî7înî"•î& î*Rî+øî/»î5þî<šî>® îE3ï›îâî‹îyî)îzî )î!¼î&Œî,-î2Ìî8bî=î?3îAwîDæïÙîâî<îñ î#öî&yî)·î/î1íî3Õî6dî:‰î@Ö îIƒïîâî« î� î$åî'<î*Zî00î5úî;‚î@YîC)îFÕï VîâîD îÛîIî 1 î'�î*€î.êî0¾î38î6¤î<ÈîB‰îCÎîFŸ 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,sothattheoptimizationrïgî#*uî$(ïgïgî%rî)9ïguïgî)êrî+ïguïgî+ærïgî1Íuî2´ïgïgî3mpïgîMÓrïb)îâî+îñîšî,îÆî!½î'î)¸î-hî/î1aî4Ûî; î=¢îB: ï_gîâîÊ îÔî3î!«î%9î+}î-]î2 î4Ûî8âî:tî<•î@8îC ï\¦îâîSî|î¸ î aî$7 ïYî¤î²îî'î"5î%©î)Ãî+Qî.üî2eî6î<žî@( îH›ïVNîâ î�îÊîûîJî$ î,Ø î4vî7Åî; îB0îEïS�îâî¶î$ î:îî"î#Øî(î+q î5 î=Šî@îCîDÛïPËîâî†î’î½îëî#Åî&n î-/î/€î3Âî5mî7¾ î@-îCöîGÈïN îâîCî‰ î( î&^ î.8î3Pî6B î=wîBÑîG#ïKHîâîGî7î²îðî 6 î) î+Âî0Uî4ƒî8Nî;âî=Ó ïG²î¤îuî îÆî (î#:î'–î*|î+êî.L î5*î7­î9  îAœîDäîG[ïDñîâîµî×îýî#uî'ñî+Óî/Ÿî4î5÷î8¥î<†îBdîDkïB/îâ î"îî"Yî&gî- î4Ñî7·î;™î=­î?‰îAœ îH…ï?nîâîãî%Üî*âî-î3­ î<îA»îDçï<¬îâîƒ î¨îî šî%î'šî+»î-fî0”uî4Bï<¬ï<¬î4‘î7Ä î=Oî>Úî@½îDIîFï9ëîâî{îß îîYî#µ î)¦î,Õî5fî7|î:î<<î>îCMîEæ rï7)îâîªîîžîõî [î#÷î'¨î*“î/¥î3+î6ýî;Iî<ÈîCžîI@ï4hîâî îîwî{ î"Tî%Cî(Öî.î2ˆ î;Sî>XîAì ï1¦îâ ï.î¤î³î/îPîã î%5î'› î/!î1õî4/î8Óî;|î>öîD ï+OîâîDî-îÒîqî î#›î&ƒî-6 î3ôî5œ î<¨î@ÐîB‚ îH�ï(�îâîZîwî·îî!7î"êî(Ÿî+gî-ìî1-î6ãî; î<�î=ÁîAoîFøï%Ëîâî÷îmîîXî¥î!ãî#‰î%Ö î.™î0æî4Qî8bî;–î=ãîBýîD¤ï# îâî›î. î®î!fî%î'qî)þî.Bî1iî4èî8ˆî:8î<™î@#îAÓîCÅîHîIÅï HîâîÞî(îüîSî!]î#”î'-î,Î î4h î;î=vîAîE8îH�ï‡îâîDî& î¹î"Xî$]î)Oî+'î. î/sî0óî4šî8mî;Oî<�îCZîHCïÅîâî›îãî2î–îùî“î :î$‚î&Úî,æ î5=î7]î:Þî?‰ îH�ïîâîBîGîî# î ßî$)î'Ÿî)0î-Lî2�î4ßî;-î=Æ îE¢ïBîâî—î½ îµî•îî#.î'"î*Þî-ôî1Ûî3†î4«î7ãî>KîD­îH ï�îâî§ îBîåî Ú î(É î/dî2�î7™ î@³îEÁîI@ï¿îâ î îÚï )î¤î�î' î"î#áî%ã î-íî0‰î3gî5h î;Ðî=¥î@…î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.rïgî#*uî$(ïgïgî%rî)9ïguïgî)êrî+ïguïgî+ærïgî1Íuî2´ïgïgî3mpïgîMÓrïb)îâîfîBî îJî:î !î!¥î$Sî*µî,| î4Bî7î<îîBIîE0îG§ï_gîâî³ îÀî@î!æî'î(óî+Õî.Iî3&î8qî<êî@†îBúîExîI5ï\¦îâîGî‚î6îeî%î%Íî*! î1Xî3½î6°î:óî>îAiîDîG’ïYäîâî²îvîî½î#\î&Žî*î, î.Æî2%î4�î8îî> îDÎîHïW#îâî;îæî8îpî î& î'hî)ûî-w î3Eî8Yî:« îB—îE@îG’ïTaîâîî9î™îèî{î´î#hî' î-•î/Îî5±î6÷î9öî<Êî>RîC6 ïQ îâîî¹îYîŠî" î(]î*(î, î2hî3Æî6Yî9éî=-î?”îDeîG#ïNÞîâîî¯îîùîî$î)Àî/¼î2î8 î<+î?{îAîE_ïLîâîŒî� îîÄî%kî*°î-Iî.¬î1î3Òî6ïî<î>uîBd îH�ïI[îâîîìî[î Áî%•î+O î4©î6aî<& îC°îGÈïF™îâî�î‰ vï@ÎîâîÏ î;î"û rï<ªî¤î©î” î1 î'[î);î-Ýî1¢ î8¢ î?åîBvîG#ï9éîâîtî. î!Kî"ùî'jî*ýî0ï ï6Rî¤î`îNîÿ î$ßî'ÿî,kî2Nî5î79î:-î?Jî@ÝîEIï3‘îâî%î—î’î $î$,î*hî,î.Ãî4Cî5´î:ñ îCÝ ï0Ïîâ î¦îî�îî$7 ï-9î¤îÁîî î"1î'î)( î0^ î7öî=ˆî?{îE/îH�ï*wîâ îî î Bî#þî){î+Ëî.G î6î:ˆ îA—îD5 ï'¶îâ î,îCî qî$3î(A î/¡î2§ î:¡î<´îC… ï$ôîâîÿî˜îªî!óî(G î.¦î0” î7m î>gîBîDK ï"2îâî‘î±îX î î"»î%î'ßî+îî/+î1_î2 î9î;Yî>Iî@ëîG-îHÑïqîâî îüîî¯îî æî' î-Õî0£î6S ïÛî¤ î‚î) î&3î)Qî+³î/`î2î4iî:`î;¹î@¼îBWîE2ïîâîîàîzî"Fî'œî,ºî.#î2zî6zî9[î;Îî>Úî@YîBáîI@ïWîâî¡îTî î&î"Üî$tî&Oî+õî1Ýî3Œî6Dî8Žî>‚îAßîFáï–îâî/îîbî 7î#ñî*sî,iî.kî4�î7ñ î@ÁîEîGœïÔîâî.î îXî eî#ïî)î,c î3vî5”î<î?•îBAîG î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,hoistedcomputationsthatrïgî#*uî$(ïgïgî%rî)9ïguïgî)êrî+ïguïgî+ærïgî1Íuî2´ïgïgî3mpïgîMÓvïaïîâîÏ îDî¶î" î'Éî)Ìî,¤rï]Ìî¤î] î!î"Ëî#õî)…î. î3„î6  î=î@H îHcï[ îâî|î«î/î î%ýî*úî0éî6Í î? îF`îH�tïXIîâ rïXIî"îÛîî"ÌïT´î¤îˆîð îõ î&xî(Âî)÷î-¸î4}î9^î:Öî=A îCÄîFŸïQòîâîîõîÕîÃî$Õî(&î+4î0ùî7"î9Sî<¤îCZîGOïO1îâî«îzî0î!�î&fî(î* î2¦î4ú î;µî>aîD3îE•îGõïLoîâîCî«î]îîPî"�î$0î%bî) î.Jî0Nî3´î7 î>¶îAîD‚ïI®îâî�îxî îHî!Äî%‹î(î,Öî/Áî2‰î6î;<î>1îD5ïFìîâîÞîˆîî9î’î%¸î(Tî-Pî/ãî5„î;î=`î@­îCJîE°îG‘ïD*îâî‘îñ îî´î"6î#Ïî&/î(þî*¸ î2Nî5 î<Ôî?5îC!îH±ïAiîâîî´î‡ î#6î%è î-¥î3øî5^î7Iî=Ýî?‘îB-îEyîH�ï>§îâî�îFî¦ îÍî!î&Tî) î,<î.î0 ï;î¤îËî9îAî ©î'rî,Jî.î/@î4Ýî9ˆî:Áî?®îAvîCåîIƒï8Pîâ îu îî# î&[î'¤î+Žî.ôî0Ì î8åî:Éî>î?MîBêuîF©ï8Pï8PîFøîHîï5�îâîrï5�îHîî€î!iî(Cî.–î1Žî6*î9pî>ÒîARï2ÍîâîËî¤î“î“î¯î!ª î*Âî/ªî1yî3ùî:Dî@ðîCéîFµîH�ï0 îâî´îtîvîÑîîî"Íî(÷î."î/@î2§î6Zî8î>‰î@+îBîEîï-Jîâî4îrîíuî�ï-Jï-JîÐî î#&î&Ìî)åî,ãî0›î38î4±î8aî9_î<’î? îAªîCîE rï*ˆîâî8î¨î¸î·î\ î#¼î%,î( î0sî6Âî9“î>ãîDåï'Çîâî{îZ î #î&î+cî,“î0î3½î5\î7=î=¯î@mîC+îDßîH�ï%îâîøîcî9îÿîî"Wî$Yî&ëî,Þî/Ýî3Lî9’î=… îE"îG:ï"Dîâ îÂîvîìî!jî#î&­î+#î-©î18 î8î<îAîEoîH�ï‚îâîîÊïíî¤îÃî!î'î"Gî$Š î+Îî2�î7´î:ëî<Ÿ îDîEãï+îâî'î�îå îî$î ¬î&) î,Ñî.„î0°î7Lî9šî<ºî>bïiîâ îÙîvîÅî 7î"±î'!î)¼î,Ýî3§î8¸î;îAbîG†ï¨îâîÜ îo îõî!_î#Çî(šî.Øî2€î3ôî7ÿî:gî?¨îDMîFµïæîâî‡î¬î.î>î%î!î#[î&aî)|î.«î1î6 î:î>ÄîA/îEùï%îâîPî–î@î¥î·î!¶ î(“î*Pî.˜î2î8Gî:´îD_îI5ï cîâîWî…îáî¤î äî#Y î,dî22î4óî:®î?Œ î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.rïgî#*uî$(ïgïgî%rî)9ïguïgî)êrî+ïguïgî+ærïgî1Íuî2´ïgïgî3mpïgîMÓrïb)îâîbî�î)î‚ î#rî(3î+1î/ýî3>î6”î=Qî>ùîARï_gîâîlîb î Ôî#Ëî&4î( î.¯î1½î4î7�î;@î>Þxî@ï_grï_gxîAÏï_grï_gxîCï_gï_gîC÷rîE¦ï_gï_gîF îGgï\¦îâî2î«îîî˜î# î*,î.Jî4nî7ýî9Xî=Jî?™îD$îFsïYäîâî_îÆî;î!íî&Êî(˜î+ î0Cî3Ÿî6Ïî:òî<¶îBrîDb ïW#îâîyî«î$îîFî!Îî#3î%–î*î/ö î8wî<ˆî>{îEîHmïTaîâî°îîFî ïPÌî¤î î î'4î*xî1¿î7 î<ÂîBõ ïN îâ uîùïN ïN îHrî|ïN ïN îÐîî!jî$î&î*oî,"î/šî3·î6;î7îî=aîAŠîC=îGOïKIîâîcî4îîè î&Äî(“î)Þî0‚î4�î:åî<´î?5îAáîE·îI˜ïH‡îâ îî î(î#²î%Áî(vî/‹î2û î9Çî=èî@.îE°îHBïEÆîâ îàî°îmî" î*xî,Ýî3zî8âî<-îAÁîC¶îFÀïCîâî©î²îîîµîî#î'…î+íî.¦î5Aî7åî9Áî@“ îG:ï@Cîâî¦îF îî ¿ î'Ý î0¿î50î86î?îB îD5ï=�îâ ï9ìî¤î’ îË î#nî'ÿî,Ýî/Ÿî4î6î9#î?ÜîAíîI*ï7*îâ î~î`îî!~î%Êî'¡î)°î, î.Ëî4Ò î;0îA îC|îIVï4iîâîg î�îðî$&î%àî(@î.(î1Zî3 î4¢î;&î?—îA[îBôîFsï1§îâî…îÏîoîtî$Õî&˜î) î+  î3 î5~î:Êî?"îAÂîCÇ ï.æîâî’îhîîŸî%Íî(Qî-æî0·î5+î9Qî<î?lîAîE[îGDï,$îâî¢îîéîÀîîôî!íî(tî*Žî/?î18î7— î@w îFÀï)cîâîçî†îåîZîÅî!+î%¤î*–î0ßî3Tî9rî=RîBFîI@ï&¡îâîGîž î"uî$9î%çî*7î+`î/L ï# î¤î^îöî9î*î ì î(®î.� î4î î=Úî@žîC£îEÌîI@ï JîâîûîhîÍî”î#3î&Ê î/Jî20î8Gî<‚îA îCwîI@ï‰îâî4îÉ îUî"9î#eî(Qî,—î/¿î1-î6ÿî=7î?åîE¸ïÇîâî²îŠîsî‚î%[î'î(Æî/fî1Hî4Šî8î;´î>îCd ïîâîîr îÇî¼î%5î)èî+Tî0� î7Qî9óî?îDðîHþïDîâî=î]î×î@î î!ïî$hî+î,×î/Pî4î7:î9´î=¹îAîBÌîFÇîH�ï‚îâîÛî�î4î M î(wî+4î/0î4˜î9{ î?ÀîCîDžîHþïÁîâîõî¤îoîÎî ºî$î* î+Îî..ÿÙ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,theprogrammermustunderstandanewprogramthatsolvesherrïgî#*uî$(ïgïgî%rî)9ïguïgî)êrî+ïguïgî+ærïgî1Íuî2´ïgïgî3mpïgîMÓsïa¸îâî î&î�î%oî,mrï]•î¤î7î7î(î!pî'aî)Õî-ªî/Aî1ˆî4jî7!î9iî>àîA=îD‚ïZÔîâîÊî…î_îïîî÷î%Íî)‘î+zî. î6­î8– î?•îB%îF¥îH�ïXîâ îe îÏî!’î&´î+àî2¯î8ttî=iïXïXî=íîB­îEîIKïUQîâîJ rî ïUQïUQîîáîËî!Fî$[î'î+Lî-Èî3rî6\î7ãî= îC´tîF‡ïUQïUQîG7ïR�îâî¹î: rïR�îI î%�î+\î-î1µî4'î:Aî=!î@nîD5ïOÎîâîNvïJîâîÏîyîQî!‰î#Œ rïEàî¤îKî[îâî!½î%Œî,`î2çî6Hî7Ïî:¸î=2 îE.îHyïCîâî°îîŠ î Oî%íî)™î->î0Êî3Nî6`î;Cî=²îCÉîE†îH�ï@]îâîŠî;î~îÌî ³î#+î)nî+ûî0éî6#î7’î:W îB îDîGÉï=›îâî–îõî`î!•î# î*î,‡î/Šî1óî4/î6Žî:8î;ðî=îBOîEîG’ï:Úîâî¡î«î) î#Øî%«î'µî-îî34 î;iî?î@½îE×ï8îâîêîJîSî »î$ î,( ï4‚î¤îuîoîÃîVî# î%ãî)`î,¥î.‰î4Ôî?+îAîîE­îH�ï1Áîâ îèî5îGî 3î"î$“î)î.¸î1ªî6Ãî9Fî=ºî?–îB ï.ÿîâî!îªî šî#Œî(¼î+Aî1oî4¯î73î:øîD®ï,>îâî3î¿î—îHîëî 5î$oî'î(©î,¬î/Üî2~î5mî;î<ªî>ôîEï)|îâî�îÿ î�îI î(î*²î1{î7Ÿî;�î=ÿîC�îE[îI5ï&ºîâîAîlî4îÿî!ðî&wî(%î*… ï#%î¤îªîUî î"!î$î)� î2Ôî7Çî:‰î=îB(îCEîF'ï cîâî†îÑî î†î¯î ùî#Þî%xî*Ûî,_î.ëî2vî4î6Z î?‰uîDHï cï cîD— ï¡îârîþï¡ï¡î?î1î!î#äî&Iî'dî,ï î5¡î;ÑîAîCîE`ïàîâîî îÞî� î%Eî*î+ÿî.¢ î7yî:øî<éîFhuïîâ îÌrî #ïïî!’ î*eî/kî66î9„ î?sîB•îI5ï]îâîèîwî%?î'Êî*äî-œî/Jî2ÔïÇî¤îQîÜîWî: î'.î)åî,î/Ëî3À î;5î=\î?ç îHMïîâîîî¹î:î$ßî&¹î-”î4"î8‡î>ÝîBq ï Dîâî|îîMî»î"°î% î-î0… î7¼î8ôî;ðîA�îDjîHyNTVm$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.rïgî#*uî$(ïgïgî%rî)9ïguïgî)êrî+ïguïgî+ærïgî1Íuî2´ïgïgî3mpïgîMÓrïb)îâî­î¢îžî“îD î&Èî-È î5Fî88î>PîDªîHþï_gîâîuîö î"èî(žî+“î-&î1#î6ðî:~î<îA°îF'uï\¦îâ rî ï\¦ï\¦ïYî¤î,îËî î"½î(×î*]î-Fî/À î7¾î:Üî>>î@îC<îH�ïVOîâîÙîÒî-îðî©î ¥î#ªî%cî+¹î,îî3³î8’î<î@îCÇîFËîH�ïSŽîâîî©îßî †î%Œî'Uî(›î,‚î.Vî2Rî8ñ î?ÛîBVîI5ïPÌîâî¢ îîˆî!;î%6î*ž î2‘î5Bî8ÚîCqîFoîI@ïN îâî[îáîæîOîúî$‘ î+Gî,òî/Nî29î6…î99î

 ïB1î¤î|î îî!sî#i î*Tî,î2Lî3{î6nî;;î<ùî?^îC²îGPï?oîâî›îîî‡î!÷î%^î(6î-Ûî1ºî5Cî8î;î?ƒîB\îDmîI@ï<­îâî’î<îàîî?îîî!î"»î)p î1˜î4kî8·î:kî=ú îFrï9ìîâî´îåîpîkî¬î!Ýî(Bî+ª î2r î9éî;xîAîB¤îDåï7*îâîAî|îWî¯îæ î&Þî* î,zî1>î3 î7Hî9 î?7îDj ï4iîâî î0îˆîiî#¦î'Kî-Oî/’î4î8î>7 îFï1§îâîJ î4î¸î 5î".î'ƒî):î+ãî/~î3Õî7î9kî>}îDï.æîâî­î“îWîËî·î!š î'ñî)³î,( î2�î8xî:àî?îAå îHÝï,$îâîgîÛîU î!. î)Âî,bî.hî3Ëî8ì î?ŽîHóï)cîâî—îDî†î£î$ý î/Yî5€î<3î?ËîD‚ï&¡îâ îrîîNîüî%uî'Ôî+;î0Gî1ÿ î8w î@îBÏîD; ï# î¤îÈîzî î!¡î%2 î,Vî-ªî03î2! î8¨î<$î@ÊîBvîC�îGOï Jîâî¯î.î�î£î "î&Jî*5î-Ýî2 î:¨î=–îB<îG³ï‰îâî¼îgî!îŒî¡î!eî$·î)–î,ÿ î4'î6êî; îC�îFgïÇîâîCî›îrîî"jî$èî(N î0î2”î7Eî9ðî?FîA® îHîIÅïîâ îÛî|î,îŽî%üî,ä î3ø î:¾î=KîCîEïDîâî"îšîKîðî©î$î!£î#—î(Ûî*�î.Ôî2 î36î7\î;Aîyï?îVî°î îcî¼ï?ï?|î+Gï?ï?î+ó yï?î4´|î6ï?ï?î6º î?{î@ÔyîA€ï?ï?ï=u|ï=uyï=u|î+;ï=uï=uî+çî/Eî0ž î: ï;Îï;Îî+:î/Dî0� î: yï:&îª|ï:&yï:&î*Žï8ï6×î¤îýîVï50î¤î°î îîï3‰îªî¶îîoîÉï1áîVî°î îcî¼ï1áï1áï0:îªï.“î¤|ï.“yî(ˆï.“ï.“î)5wï*ýîàî:îjîøî Vî$¯î&] î.>î/ìî1!î4Qî9eî;—î@· îâï(þÀî¢ï(þÀîcï(þÀî&#ï(þÀî-äï(þÀî5¤ï(þÀî=dï(þÀîE%ï(þ`îE…ï(þ`îEåï(þ`îFFï(þ`îF¦ï(þ`îGï(þ`îGgï(þ`îGÇï(þ`îH(ï(þ`îHˆï(þ`îHèï(þ`îIIï(þ`îI©ï(þ`îJ ï(þ`rï(‚ï(‚ï$íî¤îäîõî‹î1 î$Ìî'î+Vî,üî/I î7³î9Oî;› îCkîE€ï"+îâîíîÍ î\î $î#Oî&Mî)˜î.Dî1Ûî5<î9B îB1îF„îH�ïjîâ î… îñî €î&5î(yî-«î/Hî1 î8î>,îC2îEuï¨îâîî°îq î"¤î%Öî)_î/î2éî4 î8Yî;Áî={î>š îG%vïÞîâîÏîdîÀî# rï¼î¤î¤îÖîÊî#ýî(¡î/¯î1†î57î7 î=ïîD„ïúîâî�î]î¼îÄî#�î*tî-î2Äî6Xî8 î?þîB©îF‰îH�ï 9îâî…îÁî „î#Cî(Uî,>î.Kî0²î6jî<§îBÁîF;ï wîâîî î!îî ™ î&Äî(Ÿî-gî/ƒî4!î;îAîD „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Àž@¼@CÀCà¼@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À¼@¼ CÀ6ž@¼@CÀCà¼@Figure4-3.Localexplanationandnewbreakpointtypes.rïgî#*uî$(ïgïgî%rî)9ïguïgî)êrî+ïguïgî+ærïgî1Íuî2´ïgïgî3mpïgîMÓrïb)îâ îHî°î „î"ã î)�î/ î1kî4ï^”î¤îÛî€îBî$ü î,{î/î1 î7wî:œî@îBrîFÌîH�ï[Òîâ îbîî"îPî#kî*Wî.Êî1,î5<î6iî;ûîB3îCaîG³ïYîâî›îuîáî¡îXî ‚î%)î(" ïU{î¤îXîvîkî#–î&< î-<î2ñî8Óî;ÐîAÇ îIƒïRºîâî]îî‹ î Uî%Óî, î3ž î9ãî;ïîA¤îDkïOøîâî²î²î› îL î%½î'õî,jî.T î6« î>Œî@U îG‚îIÅïM7îâî7î”î!î"Bî$Êî*¢î1Šî3> î:Wî>�î?ÒîD­ ïJuîâî+îñî3îpîLî|î î%Èî'Ü î.£uî0«ïJuïJuî1rïJuî5A îhî@ß îGÔïG´îâ îÁîñîfî#[î'Ìî*+î-|î2/î3èî6Hî;ã îâïDÏþÀî¢ïDÏþÀîcïDÏþÀî&#ïDÏþÀî-äïDÏþÀî5¤ïDÏþÀî=dïDÏþÀîE%ïDÏþ`îE…ïDÏþ`îEåïDÏþ`îFFïDÏþ`îF¦ïDÏþ`îGïDÏþ`îGgïDÏþ`îGÇïDÏþ`îH(ïDÏþ`îHˆïDÏþ`îHèïDÏþ`îIIïDÏþ`îI©ïDÏþ`îJ ïDÏþ`ïE9ïE9îžï=Öîžï;Öîžï9Öîžï7Öîžï5Öîžï3Öîžï1Öîžï/Öî3žï=Öî3žï;Öî3žï7Öî3žï5Ö î3žï3Ö î3žï1Ö î3žï/Ö î3žï-ÖÒTVm$ûpî6lï@Öî—ï@Öû#Ò\TVm$î3žï9Öîžï%Öîžï#Öîžï!ÖîžïÖð(îžïÖî žïÖî žïÖî žïÖû#wï2îsîÌî"ýî&Ý î.Cî0ãî3° î:}îâïNþÀî¢ïNþÀîcïNþÀî&#ïNþÀî-äïNþÀî5¤ïNþÀî=dïNþÀîE%ïNþ`îE…ïNþ`îEåïNþ`îFFïNþ`îF¦ïNþ`îGïNþ`îGgïNþ`îGÇïNþ`îH(ïNþ`îHˆïNþ`îHèïNþ`îIIïNþ`îI©ïNþ`î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,thisinformationmightbeusedtotriggerthecollectionrïgî#*uî$(ïgïgî%rî)9ïguïgî)êrî+ïguïgî+ærïgî1Íuî2´ïgïgî3mpïgîMÓrïb)î¤î¼îîî‰î„î!dî#î'©î*î5ÿî;ãî>KîALîE îIÅï_gîâî8î îUîŸuîeï_gï_gî 9rï_gî#Õî*#uï_!î*§rï_gî+4uî,)ï_gï_gî,ârï_gî1[î7©uï_!î8-rï_gî8ºî9¯uî;Œï_gï_gî;õrï_gî@#îF$uï_!îF¿rï_gîGLîHÝï\¦îâîŠî³îH îPî @î!ùî%‚ î,]î0Tî2Éî5ùî7§î:î@sïYî¤îjî®î¶ î#Eî)î/î4ðî8õî;üîAAîB¥îI@ïVNîâîžîÑîÉîšî\î Åî%î'eî(˜î,åî.§î1î7…î>î@äîF÷ïS�îâîºîoîÛîàîšîúî"¥î&:î( î-¥ î5;î9)î:_î>îCºîG½ïPËîâî˜îsî îr î#Œî&Kî*wî/1î36î5Nî9æ î@ÿîDNîH�ïN îâî‚ î"îôî"î$ î*Lî,íî3¼î7qî9ü îB¥uîF±ïN ïN îGïKHîâ îû rîeïKHïKHî^î!Vî'tî(êî,”î2î5hî9 î=Ùî?OîCõîG´îIÅïH‡îâ î|îÕî ­î&B î.xî3}î5÷î8ž î@.îAâîEYîHÜïEÅîâ î­îfî¨ î':uî+0ïEÅïEÅî+€ rî0ÏïEÅïEÅuî1«ïEÅïEÅî2~ rî7ðïEÅïEÅïB/î¤î«î„î²î î$Cî(î*î+Yî1k î8’î:ùî>IîA@îC.îE ï?nîâî2î­ î " î&Bî'Ûî*µî+Êî1Cî7dî;ìî>£î@øîB‘îEï<¬îâîîŸîaîfî!çî&¹î+«î0|î5 î9Nî:Œî=šî?\îBuîDóîI5ï9êîâîÈî0îÐî© î"J î)î,^î.7î1‡ î8Tî:.îîDw ï!aîâîlî#î² î"•î'•î+¸î.î1î2:î7êî;%î<Þî?>îEsvï—îâîÏîdîÀî"º rïsî¤îÉîÒî�î Pî#”î(ªî.Yî1¾ î84î;¼î=~îC ï²îâîîóî0îØî ²î#_î)F î/Þ î6Vî;üî>êîCÓ ïðîâî{î:î‰î×î îî&4î(‚î.yî1‚î2™î8 î>ÞîA,îG#ï/îâî5î£î2îîî#~î'™î-bî1gî4»î:…î>Àî@fîAžîE`ï mîâîyîŸîÖ îÕî!O î'öî*¥ î2=î6Bî8Aî;‹î=GîBLîD¹ ÿ†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-incorrectinformationcouldbepropagatedthroughforksandrïgî#*uî$(ïgïgî%rî)9ïguïgî)êrî+ïguïgî+ærïgî1Íuî2´ïgïgî3mpïgîMÓrïb)îâî±î0îtîBî÷î"Èî'…î)ú î0Dî2î7¸ î?� îG/ï_gîâîáîÃî‰î"@î$ î+šî-¦î3¿î6¾î=gîB5îHNï\¦îâî=îIî  î'Ü î/mî2+î5ýî7Zî:¨î<]î>ÄîEMîI@ïYäîâîZîÒîäî²îõ î"!î%äî*xî,‚î2Aî7éî9Æî;Ž îB¹îE2ïW#îâîŒîEîïSŽî¤î÷ îjî,­ î3�î5[î8hî:åî= î>÷îDÛ ïPÌîâîïîAîûîÈî! î$iî)àî+ î-öî1žî5àî9î<î@AîC†îFâîH�ïN îâ î îîñî ‚î&›î)„î,î.cî0N î8* î>oîB®îE3ïKIîâî& îÒî/î!¢î'Àî)¦î,î1Øî3§î7à î@ÌîDkîG#ïH‡îâîWîH îq î!–î'Ëî+—î2O î9bî;ÂîA~îE(îH�ïEÆîâ îlîîz ïB1î¤îWî›îäî œ î'qî-î/uî3¾î6 î<î=¹îC- ï?oîâ î:î î î&î(] î0 î7šî9Bî=–îBîFŸï<­îâ îîÎî÷ î!_ï9î¤î¤îŸîî°î$î* î1 î7$î=Iî?ÃîBÎîDlï6Wîâîîgîüî î¶î!Øî#/î'î,Uî2ú î8ùî:©î>ùîD¡îF%îG:ï3•îâîî­îG xî" ï3•rï3•î$ î%Ðî'xî,Lï3•rï3•tî-¶ï3•ï3•î.:rï3•î2�î3Æî9cxî>§ï3•rï3•î@îA€îEîF�îGÈï0Ôîâî�î î˜xî ï0Ôrï0Ôîuxî 0ï0Ôrï0Ôî!™î$tî'±î*3xî/£ï0Ôrï0Ôî0{î1õ tî8ºï0Ôï0Ôî9>î>D rï0ÔîDÛï.îâîîùî8îiî#ùxî)0ï.rï.î*î*æî.ô xî5Äï.rï.î7!î;î>`îC+îE‹îI5ï+Pîâî4xî“ï+Prï+PîxîÙï+Prï+Pî±îcî!Ÿ î(—î.Óî51î7­î=¦îB˜îD½îH�ï(�îâîúîŸîoî òî"= î(¨î*æî0@î1‹î8.î;Áî>±îAGîDûîHCï%Íîâ uîAï%Íï%Íî�rîï%Íï%Íîeîbî î"‚î%tî(sï%Íï%Íî)‰î.ø rî4þï%Íï%Íî6Gî8 tî=„ï%Íï%Íî>šï%ÍîDe rï# îâî9îîîî kî$fî)îî- î/pî4îî:vî<(î>ŒîD ï JîâîîîÒî!’ î(Óî.ëuî5%ï Jï Jî5urî:ï Jï Jî:zî;ãîAmîD@ï‰îâî� î” îWî!Ÿî(î*1î,… î4s î;Aî@vîF ïÇîâî»îçîÀî4î"î%±î(î*�î1 î8î=|îCÒîH7ïîâîWîûîî¤xî"Ôïrïî$(î&Øî'û xî.>ïrïî/“î1Dî2gxî7–ïrïî8nî9Cî;›îA¦îEïDîâîV îî&xî IïDrïDî!ºî$zî'Õî)Úî/«î3jxî5ïDrïDî6ˆî8Kî:¿îA@îGÔï‚îâ îQîî²î‡î$î(ëî,Ýî/èî1Èî8|î=)î?ÅïÁîâ î‹ îrî!$î+4 î2¹î6î8j î?�îD¿îH7 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.rïgî#*uî$(ïgïgî%rî)9ïguïgî)êrî+ïguïgî+ærïgî1Íuî2´ïgïgî3mpïgîMÓrïb)îâîöîÂî¾î~î!æî$9 î+·î-Yî2Wî7cî=î?7 îE¸ï_gîâî=xîï_grï_gîÛî•îêî"î% î*éî,¯î. î5|î8 î?ÀîC¹îE×îI@ï\¦îâîdîr î Aî!úî&î+Ãî/+î1îâïYÁþÀî¢ïYÁþÀîcïYÁþÀî&#ïYÁþÀî-äïYÁþÀî5¤ïYÁþÀî=dïYÁþÀîE%ïYÁþ`îE…ïYÁþ`îEåïYÁþ`îFFïYÁþ`îF¦ïYÁþ`îGïYÁþ`îGgïYÁþ`îGÇïYÁþ`îH(ïYÁþ`îHˆïYÁþ`îHèïYÁþ`îIIïYÁþ`îI©ïYÁþ`îJ ïYÁþ`ïZ+ïZ+xïW°îºrïW°îîÒxîkïW°rïW°îBxïW°î |ÿTVm$qî!TïW°TVm$rïW°î"xî&¼ïW°rïW°î'“xïW°î+l TVm$qî,DïW°TVm$rïW°î-xî1HïW°rïW°î2 xïW°î5ùTVm$qî6ÑïW°TVm$rïW°î7œxî îDðïAîâîî¹îÃîîÞ î$>î'‡î-ø î4öî7oî;î>´îA,îD–îI5ï>Uîâ î¨îî‰îêîÈî%f î-¦î2µî6!î8¦î>îA8îD‚ï;“îâîîIîlî!B î(|î*Ÿî-î/ãî3~î6R î=j îDÛï8Òîâîî îî*î “î%"î(î-´î/vî0ªî5Ëî9î:Ýî=\î?£îBÞîI@ï6îâîÖîîî¾î` î'Cî)ãî0† î7Œî<¡î>{îA×îG#ï2{î¤îŸîZî6îú î'fî-P î4/î5|î;. îC‚îH ï/¹îâî‹îîÃî%sî+î-Nî/ð î7¨ î@•îDkï,øîâîYî ÿ&êTVm$½ÿMATHþæÿ TIMESROMAN ÿGACHA ÿGACHAþæ ÿGACHAþæ ÿGACHAþæ ÿMATHþŸ ÿ TIMESROMANþæ ÿGACHAþæÿGACHAþŸÿ TIMESROMANþŸÿ TIMESROMANþYÿ TIMESROMANþæÿ TIMESROMANþŸÿ TIMESROMANþÿ TIMESROMANþŸÿ TIMESROMANý…ÿ HELVETICAþŸq( ž Ï †) ¸2×: ©C KL U ô^ ¸g �p|x s� ߊh’ ›Ø£•© ܲ v»‰Áj/ÅÜǕÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿ []<>NewChap4 Monday, May 7, 1984 10:03 pm PDT