41Chapter3OptimizationandtheProblemsItCausesforDebuggingThischapterexaminestheconflictbetweenoptimizationanddebugging.Thefirstsectionbrieflyreviewsprogramoptimization.Thesecondsectiondescribestheeffectsofcommonoptimizationsontheoperationofaconventionaldebugger.Thethirdsectionsurveysthepreviousworkondebuggingoptimizedprograms.Thenextchapterwilldiscussgeneralsolutionmethodsfortheproblemsdescribedhere.3.1ProgramoptimizationManycurrentcompilertextbooksincludedetaileddescriptionsofoptimizationtechniques[Aho+77,Barrett+79].Therearealsoseveralbooksthatdescribespecificoptimizingcompilers[Wulf+75,Anklam83,Chow83].Asaresult,thisdissertationassumesabasicfamiliaritywithoptimizationtopics.Thissectionservesasabriefreminderofsomeofthemajorideas.Programoptimizationsaretransformationsthatareappliedtoaprogram,usuallybyacompiler,todecreaseitsexecutiontimeand/orspaceconsumption.Anoptimizedprogramexhibitsthesameinput/outputbehaviorasitsunoptimizedcounterpartbutisfasterorsmallerorboth.Classicaloptimizationsaremechanicaltransformationsthatdonotalterthebasicalgorithmimplementedbyaprogram.Optimizationscanhaveavarietyofeffects.Forexample,optimizationscanmoveordeletestatements.Variablesmaybeassignedvaluesatdifferentrelativelocationsinthecomputationspecifiedbytheoptimizedprogramthaninthecomputationspecifiedbythesourceprogram,orpïg/îMÓqïVÑî'Aî0ÍïP4î î#î'õî,:î7)î9ÍîBïLåî&ÀrïFHî¤îèîþî %î"¯î'Äî-] î5€î8b î@LîCOîFRïC†îâî£îéîÔ î(aî+•î0„î5}î;Áî>}îC)îE>ï@Åîâ îUîQî§î!Æî#uî$• î,¥î3vî6Dî9£î>5îC îE_ï>îâîmî�îHî!Âî(Íî+³î.Ðî3Éî6ƒî;.î@îE^ï;Aîâîîî‡î²sï4¤îâîîê rï0‚î¤îÞîëî éî'bî,…î2 î9Úî;Ö îD tï-Àîârînï-Àï-Àtî—ï-Àï-ÀîP rîaï-Àï-ÀîYî §î#Fî&_î+<î/‰î2£î8Sî=‰ îD¯tï*ÿîârîÐï*ÿï*ÿtî‹ï*ÿï*ÿî^îrî9ï*ÿï*ÿîVî!Eî"Mî&Oî(Ï î/öî5"î6*î9{ î?üîBõ ï(=îâîµîÐîlîyî!'î"Qî%¢î+”î-Mî0àî2™î4ùî8ïï$¨î¤î îzî!®î+Vî.î08î5î6‘î7›î=bîAõîCÑîDÛï!æîâî}îîîµî×î éî%|î) î2î4Dî:œî@îE%îGqï%îâ îGîîÜî Ò î(ç î0cî3î4‡î8cî:Bî?&îAîEUïcîâ îTî� î ºî*wî-:î/6î1 î4»î7î:wî@¬ îHóï¢îâî ï î¤ î‹î(î €î!¼î&Tî(î-nî0+î6 î>�îA:îE îFáïKîâ îÅîóî î"5î'Ôî,(î-çî3³î8¸î>šî@nîBô ï‰îâîžîšîùîeî$ôî(î)Èî,' î4"î9Ýî;Ùî>9îBˆîHoÿ)TVm$CHAPTER3:OPTIMIZATIONANDTHEPROBLEMSITCAUSESFORDEBUGGING42theprogram'sflowofcontrolmaybealtered.Therelativeorderingofexecutionevents(suchascallingaprocedure)maybechanged.Optimizationscanalsoeliminateoroverlayvariablesorallocatethemtoregistersinsomeprogramregions.Optimizationscanbeappliedatanumberofdifferentlevels.Source-to-sourcetransformationsareperformeduponthesourcetext;sourcetransformationsystemshavegenerallybeenimplementedasinteractivesystems,sothatthesystemcanrelyupontheprogrammertoverifythemorecomplexenablingconditionsforagiventransformation[Loveman77,Standish76,Arsac79,Gilbert82].Anexampleofasource-to-sourcetransformationisloopjamming[Loveman77],whichcombinesthebodiesofloopsthathavethesamenumberofiterations.Itsenablingconditionis:foralli>j,theresultscomputediniterationiofloopAarenotneededtocomputeinterationjofloopB,whereloopAprecedesloopB.Inthisdissertation,interactivesource-to-sourcetransformationsareconsideredtobepartoftheprogramdevelopmentprocess;theresultingtransformedprogramisthesourceprogram.Nevertheless,thecategoryofoptimizationsdiscussedheredoesincludesource-to-sourcetransformationsthatareperformedcompletelyautomatically.Interproceduraloptimizationsareappliedacrossprocedureboundariesandrequireinterproceduralanalysis[Barth78,Banning79].Acommonexampleiscommonsubexpressioneliminationacrossaprocedurecall,forwhichthecallingproceduremustbecertainthatthecalledproceduredoesnotmodifyanyvariablethatparticipatesinthecommonsubexpression.Abasicblockisamaximalstraight-linesectionofcodewithasingleentry,asingleexit,andnointernalcontrolflow.Globaloptimizationsareappliedacrossbasicblocksandrequireprogramflowanalysis[Aho+77].Localoptimizationsareappliedwithinabasicblock.Intra-statementoptimizationsareappliedwithinasinglesourcestatement,whichusuallycorrespondstoasubsetofabasicblock.However,astatementthatincludesconditionalexpressionscomprisesmultiplebasicblocks.Optimizationscanbeperformedonavarietyofrepresentationsoftheprogram:thesourcetext,anabstractsyntaxtree,aflowgraphrepresentation,alinearintermediateform(suchastriplesorquads[Aho+77]),orthe(linear)objectcode.Localandglobaloptimizationsareoftenappliedtoanintermediateformoftheprogram,frequentlyaflowgraphorquads.Objectcodeoptimizationsrïgî—tî•ïgïgî{rî¦ïgtïgîWrîŒïgtïgîŸ ïgî'Þî*érïgî-Ætî.˜ïgïgî/lrïgî4¨tî5-ïgrïgî6jtî7hïgïgî8;ïgî;œrïgî>Štî?©ïgïgî@bpïgîMÓrïb!îâîKî¿îâî¥î!`î$nî&hî+èî.Éî3±î9Iî; îAJîEŒîI@ï__îâîlîº îÛîî!î'® î0¨î3Xî6IîSîCKîI*ï\žîâîâîkîî|î *î#½î)LïYî¤ îyîîõî#ßî%xî&¡î+Îî-‡î3,uïUsî¤rïUsî î%òî(eî/Iî2üî5|î9ëî=;îA« ïR²îâîåî/îî y î(Îî* î11î6Œî8Tî;%î=ˆîBîD•îGZïOðîâî™ îÓîÚî î"Ôî&¿î,›î2� î9ˆî<î=žîA« tïM.îâ rî½ïM.ïM.tîÃïM.ïM.îbrîðïM.ïM.tîõïM.ïM.îÈî ‡ rî%dïM.ïM.î'î)’î/3î1î2hî<È îF5îGÉïJmîâtî™ïJmïJmîé rîÄïJmïJmîžî©î%Äî(!î,xî..î1Ôî4 î7ãî:@î=ºîBãîD™ ïG«îâîËîSî`î3î ^vî"<ïG«rïG«î#†vî$¨ïG«rïG«î%€î&Kî(˜î,Õî30î4Ìvî:3ïG«rïG«î;}î=$vî@7ïG«rïG«îA�îCÂîF%ïDêîâî“î< vî~ïDêrïDêîÝî™vî"ÁïDêrïDêî#˜î$xî(’vî+ºïDêrïDêî-î2Ávî5éïDêrïDêî6Áî8&î9øî<œ îD@ ïB(îâî5î#î%‡ î,ˆî.Qî0]î3\î51î7«î=U îE¡ï?gîâîÇîñ î .î&Bî(3î+î/ìî7b î@RîC7îI5ï<¥îâ î¥îõî!Uî$Ëî)ñî4nî>|îA‘îD*ï9äîâ îÞ uï6Nî¤rï6Nî î%fî(•î.\î3Eî:¤ îB’îF%ï3�îâîtî°ï3�ï3�îî#× rî)7ï3�ï3�î+¨î-½î3õî9÷î;ëîB$ ï0Ëîâ îîîAî!¾î$šî&Ðî*Øî-0î1�î8 î;lî=VîA×îDžîF÷ï. îâîeî•î îÇî"hî'Ÿî*m î1·î3eî5Äî;t ï*tî¤uî6ï*tï*tîæî£rï*tîRîÄîóî"’ î*-î.Ðî0Žî3Ûî6ûî8*î<î@ îA<îE-îH7ï'³îâîÝîçî�uîmï'³ï'³îkrï'³î"» î+-î-uî2Tî6Vî9½î=öî@¢îE`ï$ñîâî7tî‡ï$ñï$ñîÖrîcï$ñï$ñuî9ï$ñï$ñî,rï$ñî"J î+î-‘î2·î77î8œîî ‰î!Èî(î*öî0o î7¬ î>ÿîEuï­îâîUïî¤ î–î>îLî&.î(Qî)˜î.;î0î9ªî;€î=ýîD"îFŸïVîâîìîÖîçî%î 9î!]î'Øî1"î2Eî6 î>îAtîEîFÀï”îâî¶tîÉï”ï”îrî¤ï”ï”îî îÞîMî$0î(Yî,›î0vî3=î7p î?ýîB`îFïÓîâîrîC îîfîî!Aî' î-Žî.™î4üî6¡uî;CïÓïÓîŠtî?©ïgïgî@bpïgîMÓrïb)îâîXî>îfîèî#Uî)Sî+9î0àî4Iî7"î:Hî<[î?ÄîAªîFìï_gîâ îøîäî'¼î+ î-øî2$î7ÿî:Fuî<Œï_gï_gî==îB« tï\¦îâ rî)ï\¦ï\¦ïYî¤îî~îFî« î&.î*7 î3 î9¥î=4î@îD“îH7ïVOîâîîQ îºî"šî%±î*Vî/¶î2uî5ïî;ôî=µîA‡îCHîFÙîH�ïS�îâîÄî‹ îsîÈî$&î'È î/yî5 î<»î>‚îB ïPÌîâî=îë îúî!Å î+¸ î2�î5/î73î;Tî=î?Š tîE†ïPÌïPÌîEÕrîJïPÌtïN îâî\uîJïN rïN îâïHªþÀî¢ïHªþÀîcïHªþÀî&#ïHªþÀî-äïHªþÀî5¤ïHªþÀî=dïHªþÀîE%ïHªþ`îE…ïHªþ`îEåïHªþ`îFFïHªþ`îF¦ïHªþ`îGïHªþ`îGgïHªþ`îGÇïHªþ`îH(ïHªþ`îHˆïHªþ`îHèïHªþ`îIIïHªþ`îI©ïHªþ`îJ ïHªþ`ïIïIïF˜îâî~ ïC×î¢îLïAéî¢îLï?ûî¢îtï> î¢ît ï<î¢îW ï:0î¢îXî´ ï8Bî¢îXîŽ ï6Tî¢î>î î î)¹ ï4fî¢î>î  ï2xî¢îîî"% ï0Šî¢î¤î!'ï.œî¢îLï,®î¢î— ï(Eîâî¬ ï%ƒî¢îL ï#•î¢ î¨ï!§î¢îmîK ï>îâîSîš ï|î¢î#D ïŽî¢î·ï î¢î`ï²î¢ ïÄî¢ îŸ î$zî'‡ î.b ïÖî¢ îŸ wï @î%Sî)­î,Ý îâï \þÀî¢ï \þÀîcï \þÀî&#ï \þÀî-äï \þÀî5¤ï \þÀî=dï \þÀîE%ï \þ`îE…ï \þ`îEåï \þ`îFFï \þ`îF¦ï \þ`îGï \þ`îGgï \þ`îGÇï \þ`îH(ï \þ`îHˆï \þ`îHèï \þ`îIIï \þ`îI©ï \þ`îJ ï \þ`rï Åï ÅjTVm$ÄCHAPTER3:OPTIMIZATIONANDTHEPROBLEMSITCAUSESFORDEBUGGING443.2ProblemsoptimizationcausesfordebuggingAswementionedinChapter1,theeffectsofoptimizationscauseproblemsforinteractivesource-leveldebuggers.Whenoptimizationsmoveordeletestatements,orwhentheyaltertheprogram'sflowofcontrol,itmaybedifficultfortheprogrammertospecifybreakpointlocationsorforthedebuggertoreportexceptionlocations.Whenoptimizationseliminateoroverlayvariablesorallocatethemtoregisters,thedebuggermaybeunabletodisplaythevaluesofthosevariables.Whenvariablesareassignedvaluesatdifferentrelativelocationsinthecompiledcodethaninthesourceprogram,thedebugger'sabilitytodisplaythevaluesofthevariablesandtoreportthecurrentexecutionpointmaybothbecompromised.Whenoptimizationschangetherelativeorderingofexecutionevents(includingarrivingatabreakpoint),thedebugger'sreportsofsuccessiveprogramexecutionpointsmayconfusetheprogrammer.AccordingtoGaines,thefirststepindiagnosingaprogramerroristheknowledgethattheprogramreachesanincorrectstateduringitsexecution.Therearetwopossiblecausesfortheincorrectstate:somevariablescouldhaveincorrectvalues,ortherecouldbeanerrorintheprogram'sflowofcontrol[Gaines69].Ifaprogrammerusesaconventionaldebuggertomonitorthebehaviorofanoptimizedprogram,theeffectsoftheoptimizationscancausethedebugger'sresponsesto:9givetheappearanceofanerrorwhenthereisnone,9maskerrorswhentheydoexist,or9atbest,giveaninaccurateviewoftheprogram'sexecutionbehavior.Thissectioncategorizesanddescribestheproblemsthatoptimizationcreatesforaconventionaldebugger.Theproblemsaredividedintoproblemswithdata,code,andhistoryelementsoftheprogramexecution.Optimizationsthatcancauseeachproblemarelisted.Anexamplewillbegivenforeachdifficulty.Intheseexamples,theoriginalunoptimizedsourcetextisshownontheleft,andcorrespondingoptimizedtextisshownontheright.Sincetheoptimizationsinquestionarenotalwaysexpressibleinthesourcelanguage,thecorrespondingtextmaynotbealegalsourceprogramfragment.Thesourcelanguageisextendedasnecessarytoshowtheresultofanoptimization.Forinstance,anoptimizedversionmayincluderegistervalues,addresscomputationsforaccessingcomponentsofstructureddata,orexpressioncomputations.ThechosendemonstrationlanguageisCedar,whichisarelativeofMesa[Mitchell79,Geschke+77].ReadersfamiliarwithAlgolorPascalshouldhavenotroublewiththeexamples.Onerïgî—tî•ïgïgî{rî¦ïgtïgîWrîŒïgtïgîŸ ïgî'Þî*érïgî-Ætî.˜ïgïgî/lrïgî4¨tî5-ïgrïgî6jtî7hïgïgî8;ïgî;œrïgî>Štî?©ïgïgî@bpïgîMÓsïa¸îâîîu î%|î+“î.¦rï]–î¤îÞî0î4î î$ƒî&:î(Ãî-=î/ î7Çî;¦îAÙîD@ ïZÔîâ î� îAî"} î+î/î0éî5 î9îBîEEîH�ïXîâî\î„îKîeî Éî#Üî%Ûî+!î-mî/Û î7Ìî9‰î>4 îE3ïUQîâî„îŸîÜîÃîOî Pî&c î,¶î0¬ î9î>áî@ƒîE3ïR�îâî§î©î4îä î  î#î) î,î.î2Œî4<î8ðî;Qî?�îA;îDÜ ïOÎîâîøî±îî yî$¥î&<î+ßî0»î6uî8!î:~î@zîC¿îFãîH�ïM îâî_îtî î#î'{î)Wî.8î0Åî5 î7î9”î?}îBbîD>îH�ïJKîâîóîqîWî!£î%'î'` î1Tî5´ î>yîCiîFïG‰îâîKîÞîíî î&hî+bî,Ôî-Ø î5tî7® î>mîBïîD‚ ïDÈîâîqî¦îÉî!Íî&Øî)8 ïA2î¤î\î î5î!ªî$˜î'‘î)U î0Oî1Žî73î:ºî<<î>±îE«îH�ï>qîâî˜îžî¶î!™î$ñî)‰î+Š î2êî7î9�îœî@ÉîBöîF¤îH�ï8îîâîFîXî tîµï8îï8îîrî#½ï8îï8îî%î&ˆî'« î/…î2wî3š î;¬îA®îCUîH�ï6,îâîÙîØîîÂî%ïî(•î-,î/+î1Ñ î:•î=gîAcîD ï3jîâî xï/ÕîKrï0©î î÷îW î"Šî$Cî&4î)¥î-Zî0äî2Oxï-îKrï-çî î�î“î!Hî$Xî&_î)çxï*QîKrï+%î î¢îÞîÌî¼ î&Jî)…î+>î-žî4 î:>ï'�î¤î¤î' îþî"œî(jî*°î0Ÿî3T î;3î? îAÄîBÔ ï$ÎîâîæîÎîæî!Iî&Nî)6î/Nî2xî5åî9“îZî@sîBåîG9ïôîâî@ î¼îhî ÷î#Iî%¼î* î1$î2Ñî5/î9}î?™îA÷ ï2îâî¨îºî=î<îtîÈî"%î'Âî.–î1}î5Úî;®î=(îCîDÛïqîâî²î\îÝîÉî¤î¶ î'Íî*šî0aî2sî9î=êîAîFï¯îâîî� î"®î%Šî, î4\î6´ î=×îAÓîD6 ï íîâ î+îûî„ î(‰î.Fî/ªî4î8î9zî:›î?qîA"tîDÂï íï íîE ï ,îâ rîwï ,ï ,î¸îõî!î$î'¾î)rî-…î1ñî5(î7î;×î>âîA1îGêóTVm$ÚCHAPTER3:OPTIMIZATIONANDTHEPROBLEMSITCAUSESFORDEBUGGING45minornoteregardingsyntax:Cedarusesbraces({})andBEGIN-ENDpairsinterchangeably;acommentisprecededbytwodashes(--).ThediscussionfirstfocusesonasimpledebuggerwiththebasicexaminationandcontrolfunctionsdescribedinSection2.2.1.1.Recallthatthesefunctionsare:1.Reportthecurrentexecutionlocationinsource-levelterms.2.Displayvaluesofvisiblevariablesintheappropriateformatfortheirdeclaredtypes.Avariable'senvironmentisnormallydeterminedbythecurrentexecutionlocation.3.Displaythecurrentproceduretraceback.4.Setthevariableenvironmenttosomeotherprogramstatement.5.Signalauserinterrupt.6.Setandremovelocationbreakpoints.Alocationbreakpointcanbeplacedatanysourcestatement,anditisreachedimmediatelypriortotheexecutionofthatstatement.7.Resumethecomputation.Latersectionsconsiderdebuggersthatallowmodifyingthevaluesofvariablesanddebuggerswithadvancedcapabilities.3.2.1DataproblemsThissectiondiscusseswaysinwhichvaluesofvariablesmightbereportedincorrectlywhenaconventionaldebuggerisappliedtoanoptimizedprogram.Hennessyhasconsideredthisprobleminsomedetail[Hennessy79].Supposethatadebuggerdoesnotreportthevaluepredictedbytheexecutionmodelforvariablexatsomearrivalatprogramlocationp.Fromthesystem'spointofview,theincorrectreportcanhaveseveralunderlyingcauses:1.Thevariablexhasbeenremovedbytheoptimizer,i.e.,thereisnostoragelocationforxatp.2.Thecorrectvalueofxatpisavailable,butthedebuggerislookinginthewrongplaceforit.Thevalueofxcanbeinanunexpectedlocationeitherbecausetheoptimizerchosetokeepthevalueofxtemporarilysomewhereotherthanwherethesymboltablereports,orbecausethedebuggercan'tfindthecorrectsymboltableinformationforpointp.rïgî—tî•ïgïgî{rî¦ïgtïgîWrîŒïgtïgîŸ ïgî'Þî*érïgî-Ætî.˜ïgïgî/lrïgî4¨tî5-ïgrïgî6jtî7hïgïgî8;ïgî;œrïgî>Štî?©ïgïgî@bpïgîMÓrïb!îâîî\îªî!Œî%Èî(æî-Dvî-½ïb!ïb!î.•rî/mïb!ïb!î0�tî3jïb!ïb!î4#î7¤î8Œrïb!î;¼î?=îIÅï__îâîëîWî?î;î çî%Mvî%Æï__ï__î&žrî'vï__ï__î'ïï[Êî¤î® îbîmî#hî% î&ýî+”î1Ïî5î7®î;S îCRîF<ïYîâîàî î¹î!˜î&Àî*úî-Èî1Qî7OïVGîKïVGî î²îî!Ûî(î-Gî.õ î6ïS…îKïS…î î+îoî!?î%¤î+uî-9î/¯ î7%î;·î> îAgîGïQQî î– î© î%¸î'$î,ô î4=î69î8˜î=bîC—ïN�îKïN�î îîtî">î(Á ïKÎîKïKÎî îiîÉîÿ î(î)¼î-Pî0ïî6} ïI îKïI î î8îbî[ ïFKîKïFKî îœî‡î £î& î.Äî0„î5î î=î?ÐîAôîF‚îHNïDî îB î ¸î#Wî$•î%éî*ó î2³î6î7¤î9ìî@ îA«îDa ïAUîKïAUî îWî¶ ï=¿î¤îPîtîñî&�î)Sî,ÿî3™î5ûî:-î;éîA¦îDaï:þîâîýî yï54îâîÏîòrï1î¤î¼îXîî"xî$%î(1î,^î.î3Ïî7Åî9´î?C îFîIÅï.Pîâ îðîîîNî#-î$Ïî&´î-î3gî9‘î;ú îBÔîEjï+�îâî�î#tîîï+�ï+�î> rî5ï+�ï+�ï'ùî¤î]î_î½î!úî%^î(î,^î.ñî2Ïî9î;Hî=ÛîDDîH±ï%8îâvï%8îlrîï%8ï%8îÁî²îBîŽî!$î&°vï%8î,;rî-ï%8ï%8î.nî2@î4�î9òî=�î?EîBÕîE2ï"vîâîî‘î×îh î$XïµîKïµî î÷vïµî�rî 1ïµïµî øî"»î&-î+òî.î0w î7 î9¶î=Tî>Õî@ðîE·ï€î vï€î›rîJï€ï€îðvï€î7rîï€ï€ï¿îKï¿î îî±î!xvï¿î#…rî%5ï¿ï¿î%Úvï¿î'!rî(Ñï¿ï¿î)4î*[ î0Œî3+î5©î;Ðî=ZîBlîD8îF¶ïŠî îÎî:îËî!Óî%¬vïŠî'¹rî)iïŠïŠî*î,$î.Dî0!î2A î9»î?"îC>îH�ïVî î<î î!Æî% î'ˆî+:vïVî-Grî.÷ïVïVî/f î6iî=˜îA@îDnîH�ï!î îî»î#ûî%ÿî+aî.î4Jî7Ýî; î=«îB~îG†ïíî î”îÑvïíî#Ärî$œïíïí~TVm$yCHAPTER3:OPTIMIZATIONANDTHEPROBLEMSITCAUSESFORDEBUGGING463.Thecorrectvalueofxatpisnotavailable:eitherthecorrectvaluehasnotbeenassignedtox(orevencomputed)yet(Hennessycallsthisaroll-forwardvariable);orsomeothervaluehasbeenassignedtoxearly,destroyingthecorrectvalue(Hennessycallsthisaroll-backvariable).Fromtheuser'spointofview,theincorrectreportcanmanifestitselfintwodifferentways:1.Thevariablexisunknowntothedebuggeratp.2.Thevalueofxatthisarrivalatpointpisnotwhatthesource-levelexecutionmodelpredictsfromthesourceprogram.3.2.1.1VariableisunknowntodebuggerThreeoftheoptimizationsunderconsiderationcancauseavariabletohavenostoragelocationataprogramlocation:constantpropagation,copypropagation,andinductionvariableelimination.Theseareglobaloptimizations.Anexampleofcopypropagationappearsinthenextsection.ConstantpropagationThefirstexampleshowsacaseofconstantpropagation.Thevariabledebugisconstantthroughouttheprogram,sotheoptimizerhasreplacedalloccurrencesofdebugbyFALSE.Thusatanysourcestatementintheprogram,aconventionaldebuggerwouldreportdebugasanunknownvariable.10debug_FALSE;......30IFdebugORa>bTHEN30IFa>bTHEN31Print[a];31Print[a];InductionvariableeliminationThenextexampleshowsaninstanceofinductionvariableelimination.Thevariableiandthecomputations2*iandi+1havebeenreplacedbythecheapert1andt1+2.Again,atanysourcestatementintheprogram,aconventionaldebuggerwouldrespondtoarequesttodisplaythevalueofiwithan`unknownvariable'message(assumingthattherearenootherusesofiintheprogram).Iftherewereotherusesofiintheprogram,theoptimizermightinsertthestatementi_t1div2afterstatement14.Theniwouldbeknowntothedebugger,butitwouldhaveanincorrectvaluebetweenstatement10andstatement15.rïgî—tî•ïgïgî{rî¦ïgtïgîWrîŒïgtïgîŸ ïgî'Þî*érïgî-Ætî.˜ïgïgî/lrïgî4¨tî5-ïgrïgî6jtî7hïgïgî8;ïgî;œrïgî>Štî?©ïgïgî@bpïgîMÓrïb)îKïb)î î÷îžî!]vïb)î#irî%ïb)ïb)î%¿vïb)î'rî(µïb)ïb)î)î*6î,À î3¢î7£î:î>¿îB~îEîG’ï_õî î†vï_õîˆrî8ï_õï_õî±î!yî$Ãî+­î-úî4¬î7¿î:duî;‘ï_õï_õî< rï_õîBý îI*ï]Àî î�îî ·î#î&jî+Óvï]Àî-Õrî/…ï]Àï]Àî0*î35 î9Óî<#î@¦îD@ï[Œî îîºuîäï[Œï[Œîhrï[Œî"Ÿ ïWöî¤îyîØî®îMî!î$™î&ùî,´î0Øî3cî8òî+îCZ ïA£îâîäî7îZ î"³î%î*î,8î/Š î7+î<6î=äî@CîCSuï=�îâî¦ rï9ìî¤î­î¶îaî!Ÿî"úî&î(î-¤ î6„î9�vî>õï9ìï9ìî?Írï9ìîCâîEï7*îâ îîWî4îîî"Cî(bî*Íî0Hî2. î9švî;Iï7*ï7*î…îAuvîFÃï£rï£îH7ïáîâî" vïáîôrîSïáïáîùvïáî ^î"î#¾rî%nïáïáî&5î(•î+Ñî17î3î5Rvïáî:Çrî=Oïáïáî=õvïáî@ZîBâîD’rîEjïáïáîFŠï îâî�îFî«îöî¹î".î(+î)j î1™î7¸î;ûîASîCîDVîI@ï^îâî—îøî£vî^ï^rï^î¼îÙî!Ëî(9î-Êî3#î9›î î?ÃîBîHmïîâî8îgî­î�îYî#î(rî.§î0Œî3Dî9y„TVm$õCHAPTER3:OPTIMIZATIONANDTHEPROBLEMSITCAUSESFORDEBUGGING4710i_1;10t1_2;11WHILEi<=10DO11WHILEt1<=20DO12a[2*i]_5;12a[t1]_5;13i_i+1;13t1_t1+2;14ENDLOOP;14ENDLOOP;3.2.1.2ReportedvariablevalueisincorrectThevalueofavariablecanbeincorrectataprogramlocationinseveralways.Thevaluecanbeincorrectbecauseanassignmenttothevariablewasdelayed(assignmentremovalisaspecialcaseofthis)orbecauseanassignmenttothevariablewashoisted.Anassignmentishoistedwhenitismovedtoapointthatisearlierintheprogram'scontrolflow.Avariable'svaluecanalsobeincorrectbecauseofstorageallocation.Thevaluecanbeincorrecteverytimethattheprogramlocationisreached,orthevaluecanbeincorrectonlysometimesthatitisreached.Thefirsttwoexamplesdemonstratecasesinwhichavariable'svalueisalwaysincorrectataprogramlocation;theremainingexamplesillustratecasesinwhichthevalueissometimesincorrectthere.StorageoverlayingInthefollowingexample,storageoverlayinghasbeenperformed.Theprogramneverusesiandjsimultaneously,sothestorageallocatorhasassignedthesamememorylocationforbothvariables.Therefore,ifthevalueofiisrequestedatanyprogrampointafterstatement30,aconventionaldebuggercannotrespondwiththecorrectvalue.Anaivedebuggermightdisplayj'svalueinstead.10FORiIN[1..n]DO10FORiIN[1..n]DO11IFa[i]=keyTHEN11IFa[i]=keyTHEN12{found_TRUE;12{found_TRUE;13EXIT};13EXIT};ENDLOOP;ENDLOOP;......30FORjIN[1..m]DO30FORiIN[1..m]DO31b[j]_2*j;31b[i]_2*i;ENDLOOP;ENDLOOP;CopypropagationThisexampleshowsacaseofcopypropagation.Thevariablexhasthesamevalueasvariabley,sotheoptimizerhasreplacedtheuseofxbyauseofyinstatement11.Thereforexhasanincorrectvaluebetweenstatement10andstatement30.Bothformsofpropagation(thatis,rïgî—tî•ïgïgî{rî¦ïgtïgîWrîŒïgtïgîŸ ïgî'Þî*érïgî-Ætî.˜ïgïgî/lrïgî4¨tî5-ïgrïgî6jtî7hïgïgî8;ïgî;œrïgî>Štî?©ïgïgî@bpïgîMÓzïbjî¤îªîî]ïbjî%áî'çî)íî+Gï`Âî¤îªî¶îîîï`Âî%áî'çî+ôî-úî0î2ï_î¤î°îiîÂï_î%áî)íî-úî/Sï]sî¤î°î îcî¼îï]sî%áî)íî+ôî-Mî/Sî0­ï[Ëî¤î°ï[Ëî%áî)íwïVÕîâî0îî7î!Êî#ArïR²î¤îsîîÆîçî î"™î$�î*5î+Åî,çî2mî7œî9Bî=ÊîAòîDÂîHcïOðîâîëî¾îøî î%)î&ðî)gî.¶î1yî6§ î>IîC­îE1îFsïM/îâîÌî€î—îVîtî` î&lî(î*qî/£î2Kî7çî:6 îABuîB©ïM/ïM/îCfrïM/îG9ïJmîâî:î§î.îÞî îªîzî çî%,î&Ûî)<î/©î4]î8Uî9ã î?øîC£îF0îHþïG¬îâî¸îõîÈî • î'åî*Øî.œî1Bî3Muî9$ïG¬ïG¬î9¿rïG¬î<½î?ýîBæîE`ïDêîâîî€îøî¹îî"¾î%Fî'5î,îuïDêî0rî3mïDêïDêî3Üî7î9áî;4î<žîB—îElîHBïB(îâîë îÃî Aî!ûî&î'I î-gî1î2”î7î<Ëî>oî?¤îE>ï?gîâîAîÃîÀ î#eî&Øî(†î,”î.óî2�î4 î:Áî@}uï;Dîâîã rï7®î¤îjîÁîÊî!’î&< î,àî/Lî2  î:.î<þîB„îFEvï7®îI’rï4ìîâvï4ìîírî�ï4ìï4ìî! îjîIî!Äî&’î,Gî.×î4kî6æî:î@îEYîG²ï2+îâ î² î†îî €î$Fvï2+î&Rrî(ï2+ï2+î(eî)Šî/èî1�î4Zî:î=ÁîAîGkîIÅï/iîâ îîHî!åî'Hî*„î-î1¸î6€î8.î;ùîB#îF<vï,¨îârîºï,¨ï,¨îîîÄzï)Ÿî¤îªî]î¶î¼îuï)Ÿî%áî'çî*šî+ôî-úî2³ï'øî¤î°î¶îîoî"ï'øî%áî)íî+ôî/Sî0­î3`ï&Pî¤î¶îoîÉï&Pî%áî+ôî0­î2ï$¨î¤îcï$¨î%áî, ï#î°ï#î)íï!Yî°ï!Yî)íï²î°ï²î)íï î°ï î)íïbî¤îªî]î¶î¼îuïbî%áî'çî*šî+ôî-úî2³ï»î¤î°îîiï»î%áî)íî-Mî.§ïî°ïî)íuïðîâîj rïZî¤î«îî î"î!ýî#¤î&ã î/:î1ÿvî7#ïZrïZî8lî:Ïî=î@†îDîE¸vï™îârîºï™ï™î¢îqîÜîî’î#"î%�î( vï™î*rî+Êï™ï™î,‘î-Ñî/î1‡vï™î3“rî5Cï™ï™î5¦î6ýî=>î@vï™îFÉrîHyï™ï™îI@ï ×îâîñîÌî•î #î&wî(|î+Rî1§î4¦î8!î<,î> îEÄîI*ZTVm$ÞCHAPTER3:OPTIMIZATIONANDTHEPROBLEMSITCAUSESFORDEBUGGING48constantorcopypropagation)cancauseeitheranincorrectvalueoranunknownvariable.10x_y;11z_x+3;11z_y+3;......30x_39;30x_39;LocalcodereorderingLocalcodereorderingcanalsocausethevalueofavariabletobereportedincorrectly.Inthiscodefragment,localcommonsubexpressioneliminationhasmadeitdesirabletostorethenewvalueoffbeforestatement11ratherthanafterit.Thusthevalueoffisalwaysincorrectatstatement11.[Ofcourse,thepreviousvalueoffmighthavebeenb+c.]10a_b+c;10R1_b+c;a_R1;f_R1;11d_5;11d_5;12f_b+c;13g_x;13g_x;GlobalregisterallocationThefollowingexampleshowstheeffectofglobalregisterallocation.TheoptimizernoticedthatthevariableremxyisusedfrequentlyintheWHILEloop,andthereforeplacedremxyinmachineregister1forthedurationoftheloop.Supposethattheuserplacesabreakpointatstatement13andrequeststhevalueofremxywhenthebreakpointisreached.Aconventionaldebuggerwouldreportthevaluecontainedinthenormalstoragelocationforremxy,ratherthanthevaluecontainedinregister1.Therefore,thereportedvalueiscorrectthefirsttimethatstatement13isreached,butonsubsequentloopiterations,thereportedvaluedoesnotreflectthesubtraction(s)ofy.10remxy_x;10remxy_x;11y_F[z];11y_F[z];R1_remxy;12WHILEremxy>0DO12WHILER1>0DO13remxy_remxy-y;13R1_R1-y;ENDLOOP;ENDLOOP;remxy_R1;......30Print[x,y,remxy];30Print[x,y,remxy];rïgî—tî•ïgïgî{rî¦ïgtïgîWrîŒïgtïgîŸ ïgî'Þî*érïgî-Ætî.˜ïgïgî/lrïgî4¨tî5-ïgrïgî6jtî7hïgïgî8;ïgî;œrïgî>Štî?©ïgïgî@bpïgîMÓrïb!îâîQîîg î!�î$ î'Âî+®î-žî3Zî7î8Èî:¸î@Ìzï_î¤îªîî]ï]pî¤îªîî]î¶îï]pî%áî'çî)Aî*šî+ôî-Mï[Èî°ï[Èî)íïZ î°ïZ î)íïXyî°ïXyî)íïVÑî¤îªîî]ïVÑî%áî'çî)Aî*šuïR­îâî¸îÓ rïOî¤î‰îê î½î"cî%Jî)î+“î/Xî1+î2oî7Àî9‰î;•îA? îIïLVîâîvî®îÕî î#¯ î,l î3›î6î9´î:üî@ÀîB`îE¯îHïI”îâî vïI”î­rî]ïI”ïI”î#îÀî! î#î'&î*`î-°î0 î3žî6î9ÐvïI”î;Ürî=ŒïI”ïI”î=ïî? îC…îIVïFÒîâîtîØïFÒïFÒî(îÏîˆînî#áî&ÏzïFÒî(stî)ÌïFÒïFÒî*ºî,øî/—zïFÒî2‹î3äî5>tî5êïFÒïFÒî60zïCÊî¤îªîî]î¶îïCÊî%áî'çî)íî+Gî, î-úïB"î'çî)Aî*šï@zî'çî)Aî*šï>Òî¤îªîî]ï>Òî%áî'çî)Aî*šï=+î¤îªîî]î¶îï;ƒî¤îªîî]ï;ƒî%áî'çî)Aî*šuï7_îâî;î rï3Éî¤î�î´î @î$`î&Óî*²î,~î0´î5¥ î<çî?ÒîFï1îâîØî_vî½ï1ï1î•rï1î î 4î#— î*bî,8tî.¿ï1ï1î/Ùrï1î3Gî6ìî9Ëî?ÚvîD]ï1ï1îE5rï1îI@ï.Fîâî�î—îôîZîãî%œî'}î*î.Xî4î6þî9†î<¨î@êîB< îIVï+„îâî.î)î÷îfî!Üî%œvî'kï+„ï+„î(Crï+„î,=î0 î2~ î9…î;îA1îBÔ ï(ÃîâîîîîEî§î#Sî)¡î+Rî-´î2sî7(î¢ï(Ãï(Ãî?yrîBÙï(Ãï(ÃîC¸îGÈï&îâî{î_îåîÍî"åuï&rî%jï&ï&î&Qî,\î.öî4¿î8£î:Iî?îA®îDÁîH ï#@îâîîþîjîåî gî"m î)—î,½ î3î5sî;î>®îAßîDUîH�ï ~îâ îwvî0ï ~rï ~îzïuî¤îªî¶îïuî%áî'çî+ôî-MïÍî¤îªîî]ïÍî%áî'çî)Aî*šï&î'çî)íî+Gï~î¤îªî¶îÂîîuï~î%áî'çî+ôî-úî/Sî0­ïÖî¤î°î¼îî"î {ïÖî%áî)íî+ôî-Mî/Sî0­ï.î°ï.î)Aï‡î'çî+ôî-Mïßî°ïßî)íï7î°ï7î)íï�î°ï�î)íï èî¤îªï èî%áî'çÿ#TVm$šCHAPTER3:OPTIMIZATIONANDTHEPROBLEMSITCAUSESFORDEBUGGING49Localregisterallocationholdstheresultofacomputationinaregisterandusesitforothercomputationswithinasinglebasicblock.Itcausesthevariable'svalueinmemorytobeincorrectateveryarrivalateveryprogramlocationbetweenthecomputationandthestoreofthevalue.Ofcourse,ifthecomputedvalueisnotusedoutsidethebasicblock,thestoremaybedeletedaltogether.CodemotionAstheexampleshowninFigure1-1andFigure2-2hasillustrated,codemotionoutofloopsalsocausesavariabletohaveanincorrectvalueonsomearrivalsatcertainprogramlocations.Thecodemotionoptimizationcanonlybeappliedwhenaloop-constantpieceofcodewillalwaysbeexecutedbeforetheloopexits.Intheexecutionoftheunoptimizedversionoftheprogram,iftheloop'sexecutionbeginsatexecutionstates1,andanassignment(movedintheoptimizedversion)isexecutedatstates2,thentheassignedvariablewillhaveanincorrectvalueateverystatetbetweens1ands2.Inthefollowingexample,x'svalueisincorrectonlythefirsttimethatstatement11isreached.x_4*c;10FORiIN[1..10]DO10FORiIN[1..10]DO11a[i]_i;11a[i]_i;12x_4*c;13b[2*i]_a[i]+x;13b[2*i]_a[i]+x;ENDLOOP;ENDLOOP;Acombinationofoptimizations:globaldeadstoreeliminationandcodehoistingThefollowingexampleisfairlycomplex.Thevalueofvariablejdefinedinstatement15isneverused,soglobaldeadstoreeliminationremovesstatement15.Theexpressionb+cisaverybusyexpression(itisusedonmultipleflowgraphpathsbeforevariablesborcareredefined),soitscomputationishoistedtoprecedestatement10.Afterstatement15isremoved,thevalueofthatexpressioncansafelybeassigneddirectlytoj.Considerthebehaviorofaconventionaldebuggerontheoptimizedprogramfragment.Atstatements10and14,thereportedvalueofjisalwaysincorrect,becausethenewstoretojprecedesthosestatementsoneverypossibleexecutionpathtothem,whereastheoldstorefollowedthosestatementsoneverypathtothem.Atstatement12,thereportedvalueofjisalwayscorrect.Atstatement16,thereportedvalueofjisalwaysincorrect,bothbecausethedeadstoreat15wasremovedandbecausethestorefrom18washoisted.Atstatement17,thereportedvalueofjmayormaynotbecorrect.IfexecutioncamethroughtheTHENclause,thevalueofjiscorrect.However,ifexecutioncamerïgî—tî•ïgïgî{rî¦ïgtïgîWrîŒïgtïgîŸ ïgî'Þî*érïgî-Ætî.˜ïgïgî/lrïgî4¨tî5-ïgrïgî6jtî7hïgïgî8;ïgî;œrïgî>Štî?©ïgïgî@bpïgîMÓrïb)î¤îîn î ¾î$„î&ôî*Ðî,šî-Õ î5àî7žî8Ùî=Èî@�îCšîEîGOï_gîâ î_î¡îÉî ³î$$î(¼î*1î.iî0Ç î6Øî:€î<,îA—îCDîE2ï\¦îâîrîîdîõî¡î#'î(Vî-¼î0 î8î:µî= î@`îBîDhîHÝïYäîâîÍîqîîÅî"²î$bî'î*šî/¦î2Iî6î:[î<þî@žîCæîFïW#îâ uïSîâî`rïOkî¤î´îîŒîÛî!ˆî%øî(Vî+ î/}î1Ûî4O î;î>ZîCîEŒîGEïL©îâî�îÅîÜîîžî Óî"±î([î+óî-èî1iî6*î7±î<&îA£ îHïIèîâî3îú îüî!‘î$µî&¯î+£î/bî0– î9)î<Çî>‰îAÚîD�îHþïG&îâî–îÝî4îQî"Lî$î&jî,—î.Hî0Ÿ î8�î=Pî?îAXîG6îH�ïDeîâîÞîîXîëî%vî(FïDeïDzïDî)rïDeî)Ëî*¢î-Tî/> î6Jî;Dî<íî?GîE­ïA£îâîrîRîvîdïA£ïA\zïA\î;rïA£îèîéî!3î#¶î)Sî.­î1|î4çî6ûî<Ûî@©îBeîF=vîI’ïA£rï>áîâvî…ï>áï>›zï>›î]rï>áîÂvî®ï>áï>›zï>›î†rï>áî2îûîþî!’î'Ùvï>áî-ýrî.Õï>áï>áî/-î0jî4Hî5èî;Øî?&îAºîDÆîH ï< îâîîýîhzï9î'çî)Aî*šï7pî¤îªî]î¶î¼î"ï7pî%áî'çî*šî+ôî-úî3`ï5Éî¤î°îîiï5Éî%áî)íî-Mî.§ï4!î¤î°î îcï2zî¤î°îiîÂî"î {ï2zî%áî)íî.§î0î3`î4¹ï0Óî°ï0Óî)íuï,°îâîd îî² î"nî&zî)«î,ó î4î6¦î9Árï)î¤îyîˆîþî!fî%î+[î.0î1Öî3Œvï)î9rî:Æï)ï)î;�î?ÃîAnîG¡îIƒï&YîâîÆîsîPîŒî î#x î*Îî0Tî6£ï&Yî93î<$ vï&YîC0îDàîF�rîH@ï&Yï&YîH£îIÅï#—îâî^î î8îuî!Nî$÷î'kî-Rî4Aî8Yî=vï#—îC$rîDÓï#—ï#—îE�vï#—îFërîH›ï#—ï#—îI@ï Öîâ îãî¬îŒ î!‹î"üî'Ëî)î.¦î4áî7¬î;PîA‹îCuîDæïîâîqîIî1î/ î!î#Ðî'àî)ÿî/§î4Ìvïî6Îrî7¦ïïî9dî?oîAýîGÝîIÅïSîâ îðîìîæî!9î'™î-î3»î5© î0î@ÛîC îE^ï‘îâî­vï‘î¹rîiï‘ï‘îÌîöî{ î"°î'óî*sî-‚î0ÿvï‘î3rî4±ï‘ï‘î5xî:xî>8 îEîG:ïÐîâî"îVî{î(î#î(Iî*§î-î0jî6 î9« î@cîBhîFîI@ïîâîPîPîŠîÌî 0î%Äî)rvïî+rî-/ïïî-’î.Ÿî3î8î:î@¹îBúîE^ïMîâî¡vïMî­rî]ïMïMîÀîÞîW î"€î%Ñî+î-|î0îî4_î6 î8î:Çî@ŒîCXîH�ï ‹îâîBî¬î”îCîîî!ìî(%î*eî,Èî2[î6vï ‹î8rî9Äï ‹ï ‹î:îî<Ëî>’îA™îDîFï ÉîâîYî‚î î7tî!‹ï Éï Éî"Erï Éî%Eî)«î+ÿî/�vï Éî1ªrï Éî2úî4[î9²î?ÛîA1îGZÿ/TVm$žCHAPTER3:OPTIMIZATIONANDTHEPROBLEMSITCAUSESFORDEBUGGING50throughtheELSEclause,thenthesituationofstatement16holds,andthevalueofjisincorrect.valueofjbeforestmtj_b+c;10IFcondTHEN10IFcondTHENalwaysincorrect11{j_b+c;12w_j}12{w_j}alwayscorrect13ELSE13ELSE14{w_b;14{w_b;alwaysincorrect15j_1;16y_c};16y_c};alwaysincorrect17z_w+3;17z_w+3;sometimesincorrect18j_b+c;19x_j-17;19x_j-17;alwayscorrect3.2.2LocationproblemsTheprecedingexampleswerecarefullyconstructedtorequireonlyastraightforwardmappingbetweensourcetextandobjectcode.Thissectiondescribesdifficultieswiththeprogramlocation:displayingthecurrentlocation,displayingthecurrentproceduretraceback,settingthevariablecontext,andsettingandfieldingbreakpoints.Recallthatthedebuggerusesthemappingfromprogramstatementstoobjectcodelocationstosetbreakpoints.Itusesthemappingfromobjectcodelocationstoprogramstatementstofieldbreakpointsanddisplaythecurrentexecutionlocation.Obviously,ifeitherofthesemappingsdonotcorrectlyreflectthecorrespondencebetweenthesourcetextandtheobjectcode,therewillbeproblemswiththeassociateddebuggerfunctions.Howshouldthesemappingsbedefined?Aconventionalnonoptimizingcompilergeneratesseparateobjectcodeforeachstatement,intheorderthattheprogramstatementsappearinthesourcetext.Inthiscase,thebeginning(orend)oftheobjectcodeforasourcestatementisunique,andeachobjectcodeinstructionispartofthecodeforexactlyoneexecutableprogramstatement.Somepiecesofsourcetext,suchasENDsorcomments,maynotgenerateanyobjectcode.Forotherpiecesofsourcetext,theremaybeseveralpossibleinterpretationsofwhatthecorrespondingobjectcodeis.Forexample,ifabreakpointisrequestedonaFORstatement,thebreakpointcouldrefertotheinitialentrytothestatementortotheentrytoeachiteration.Similarly,ifexecutionisinterruptedinsideloopcontrolcodeattheendofaFORloop,thesourcelocationcouldbereportedasinsidethelaststatementintheloop,asinsidetheENDLOOP,orasinsidetheFORloopheader.Nevertheless,foragivenlanguageordebugger,onceaninterpretationforthesecasesisdefined,themappingbetweensourcetextandobjectcodeisstraightforward.rïgî—tî•ïgïgî{rî¦ïgtïgîWrîŒïgtïgîŸ ïgî'Þî*érïgî-Ætî.˜ïgïgî/lrïgî4¨tî5-ïgrïgî6jtî7hïgïgî8;ïgî;œrïgî>Štî?©ïgïgî@bpïgîMÓrïb)îâîtîyïb)ïb)î3rïb)îÈî9î!_î#¿î)Yî+î1Hî3-î7:î9ñîï^·þjî>nï^·þOî>nï_!î>½ï^·þjî?'ï^·þŸî?'ï_!î?Æï^·þ„î?Æï_!î@Jï^·þaî@Jï_!î@«ï^·þ–î@«ï_!îAAï^·þjîAAï_!îA«ï^·þ„îA«ï_!îB/ï^·þjîB™ï^·þjîB™ï_!îCï^·þYîCï_!îC\ï^·þîîC\ï_!îDJï^·þYîDJï_!ï_!ï_!zï]zî'çî)Aî*šî+ôî-Mï[Òî¤îªî°îï[Òî%áî'çî)íî-Mtï[Òî:î=¢zïZ+î¤îî îcî¼îïXƒî¤î°î îcïXƒî%áî)Aî+Gî, tïXƒî:î=¢zïVÜî¤îªïVÜïVÜî%áî'çïU5î¤îî îcïU5î%áî)Aî+Gî, tïU5î:î=¢zïS�î¤î°î îcïQæî¤î°î îcïQæî%áî)íî+Gî, tïQæî:î=¢zïP?î¤îªîî]î¶îïP?î%áî'çî)Aî*šî+ôî-MtïP?î:î?zïN—î¤îªîî]î¶îïLðî¤îªîî]î¶îïLðî%áî'çî)Aî*šî+ôî-MtïLðî:î=¢yïG&îâîÏîÉrïCî¤îwîÈî Áî$ î)® î0þî2¨î7lî:�î;¦îE3ï@CîâîHî�î>îìî!ýî&î)î-³î3“ î:Oî=aî?¸îE>ï=�îâ î î0î+î"ë î)©î,9î14î7è î>‘îC'îE¸ï:¿îâîîÆî,îãî"î ï7*î¤îãî·îî!+î$+î&�î,Rî/¿î5S î<î=ÇîAæîE3ï4iîâî‘î¯ îîyîsî!Ôî'�î*øî/î2Yî8î9Äî?T îFîG¾ï1§îâ îWîîÁî !î$ëî+ î13 î8î9yî=eî?îB¨îHèï.æîâîSîõî+î† î'Lî,¶î/î3^î6î8Åî;!î?5îBÑîFVîHþï,$îâîêîîe î Ñî&Ú ï(�î¤îî¯îRî#«î%¶î+üî-¢ î5Ö î?îDæï%ÍîâîUîˆîéîAî!Œ î(4î)ýî,vî0Eî3.î5¨î;Q îB%îFÆîH�ï# îâîî…î>îÊîûî Fî&œî(Ãî+ßî-‚î/Ìî3Ðî7î9)î:=î>wîD—îEîï Jîâî–îÄîÚî î"öî$_î'@î(öî+Rî.–î0Ñî5jî8 î>ÕîDa ï‰îâîÍîûîÉî.î Sî#™tî%\ï‰ï‰î&rî'äï‰ï‰î)î*Ûî1Õî4îî7yî=î?ÈîCöîHCïÇîâîuî‚î/îsîwî"õî%íî'Òî,Wî1�î:¥î†îB„tîDßïÁïÁîE™rïÁîGÉï ÿîâî^ îÖîî Vî$î)éî+ºî2(î5{î7x î@$îBnîFîIƒï >îâî:îšîUî!Äî&î(Ëî+ƒî/›î2âî4NëTVm$âCHAPTER3:OPTIMIZATIONANDTHEPROBLEMSITCAUSESFORDEBUGGING51Optimizationcancomplicatethesemappingsinseveralways.First,anoptimizingcompilermaynotemitanyobjectcodeforanexecutablestatement.Second,optimizationsmaypreservetheorderofexecutionofinstructionsthataremeaningfultotheprogrammer,whilecreatingcorrespondencesbetweenthesourcetextandtheobjectcodethatarenolongermonotonic.Finally,optimizationsmayrearrangetheorderofexecutionofprogrammer-specifiedinstructions,causingseveraladditionalproblems.Thesecomplicationswillbediscussedinorderoftheircomplexity.3.2.2.1NocorrespondingobjectcodeIfanoptimizingcompilerfailstoemitanyobjectcodeforanexecutablesourcestatement,itmakesitdifficultforthedebuggertoplaceabreakpointonthatstatement.Notethatitdoesnotpreventdisplayingthecurrentexecutionlocationproperly,becauseexecutioncanneverreachanonexistentlocation.Twooptimizationscancausethissituation:unreachablecodeelimination,whichremovesprogramstatementsthatcontrolwillneverreach(giventhevaluesofthevariablesknownatcompile-time),anddeadcodeelimination,whichremovesprogramstatementsthatcomputevaluesthatareneverused.Iftheremovaloptimizationalsoremovesthestatementmarker,andthestatementmapusescharacterpositionsorlinenumbers,thestatementwilllooklikeacommenttoaconventionaldebugger.Therefore,thedebuggerwillplacethebreakpointatthestaticallyprecedingstatement,whichmayormaynotdynamicallyprecedethedesiredstatement.Ifthestatementmapusesstatementnumbers,thedebuggercanatleastdeterminethatthereisnoentryforthatstatement,andgiveawarningmessage.Iftheremovaloptimizationleavesthestatementmarkerinplace,thebreakpointwillbeplacedatthefollowingstatement,whichmayormaynotdynamicallyfollowthestatement.Nowarningwillbegiventotheuser,becauseitwilllooktothedebuggerasifthestatementwereastatementthatdoesnotordinarilygeneratecode.TheproblemsassociatedwithalteringvariablesfromthedebuggersoastodirectprogramflowintoareasthathavenocorrespondingobjectcodearediscussedinSection3.2.4.Asimilarproblemisthatacorrespondingstoppingplacemaybemissing,eventhoughcodehasbeengeneratedtoperformthespecifiedoperation(s).Suchoptimizationsaretypicallymachine-dependentoptimizations.Forexample,inthefollowingprogramfragment,theoptimizerhasgeneratedasingleinstructiontoincrementandtestthevalueofi.Therefore,thereisnoplaceforabreakpointcorrespondingtostatement11.Thisproblemoccurswheneverasourcestatementboundaryisembeddedwithinamachineinstruction.Entireloopscanbeeliminatedinrïgî—tî•ïgïgî{rî¦ïgtïgîWrîŒïgtïgîŸ ïgî'Þî*érïgî-Ætî.˜ïgïgî/lrïgî4¨tî5-ïgrïgî6jtî7hïgïgî8;ïgî;œrïgî>Štî?©ïgïgî@bpïgîMÓrïb)î¤ î î± î#¯î'Qî-©î/oî4î8�î<8î>A îE3ï_gîâîýî‰îÅî}î­î" î$_î&g î-C î4ƒî9Æ îBZîEuï\¦îâî„î{îvîîîé î'‹î*›î-1 î4±î6¡î9C îAÀîE·ïYäîâîîcî ¦î$Øî'rî* î,Nî0Jî3sî6$î8Zî:Cî>i îEåïW#îâ îlî|î §î#î&Ôî(™î.Ûî0 î>@ îFïTaîâîs îêî Îî$Ð î-zî0%î2î8 î9Îî=‚î?;îB‚ wïOkîâî0î„ îKî"crïKIî¤î,î" îî!Ãî$·î&kî)—î,>î0]î3ªî5íî7ã î>¯îC îI˜ïH‡îâîîtî­îìîMî$Xî&î)žî*É î1»î3Ãî6“ î=¨îA îCðîEGîHyïEÆîâî î­î,î"î(jî-Àî3Æî9î?\îBîEðîIÅïCîâ îXî°î÷ î(–î+Dî/î1ß î8 î?ðîCY ï@Cîâîñî_îï î$ªî'yî,-î.Ùî2¥î6[î:‰î<êîAîBÓîE3ï=�îâî´î™ î î" î%¶î)I î1+î5…î;?îA îH ï:¿îâîÄî-î7îÅî"Ëî'Zî)î+²î19 î9mîÎîEîGÕï5<îâîŽî¹îÃîrî� î#¸î*ž î1Xî3¸î9Âîî1–î3+î5‡î;– îB îF*îI*ï'uîâîñîq î(î kî"Ö î)ýî,kî1Âî4yî6uî:4î;îî>XîAµîFâîHCï$³îâîî½î'î:îñî\î!Åî(î+_î,“î2Òî5ªî8äî;c îAÂîGPï\î¤îŸîÊ î!Zî$˜î)ºî/˜î3"î5¥î;Ñî=¸î?‰îA[îE`ï›îâîüîÔîQîîfî l î)cî-|î0Ãî3î9 î:Îî?­ïî¤î<îÎî^îÖî!°î"æ î+éî1�î50î8@î:=î?•îBèîG§ïDîâî¸îuî!î0î#èî&©î,Å î6î9Ø îB¶îEjï‚îâî î$Zî&ûî,Âî.eî0ºî6ÂîùîEQîFŸï >îâîîOî»î#vî'¼î(æî.l î6$î:Sî=þî@ŠîB{ îI@ rTVm$ÝCHAPTER3:OPTIMIZATIONANDTHEPROBLEMSITCAUSESFORDEBUGGING52thiswayonmachineswithvector[Russell78]orstringmanipulationinstructions[Morgan+82].10i_i+1;10IF(i_i+1)#0THEN--oneinstruction11IFi#0THEN12x_y/i;12x_y/i;Optimizationcanalsocausetheflowofcontroltobypassalocationthatwouldnotbebypassedintheunoptimizedversionoftheprogram.Thefollowingprogramfragmentsearchesalinkedlistforadesiredrecord.Iftherecordisnotinthelist,itisconsideredanerror.Thebranch-chainingoptimization(oftenamachine-dependentoptimization)hasbeenappliedtothefragment,eliminatingthesecondtestofthevariablefound.Iftheprogrammerwishestoexaminethedesiredrecordattheloopexit,anaturalplacetoplaceabreakpointisatstatement15.However,theoptimizedversionofthefragmentarrivesatstatement15onlywhenthelistisexhaustedwithoutfindingthedesiredrecord.10found_FALSE;10found_FALSE;11WHILEptr#NILAND~foundDO11WHILEptr#NILDOIFfoundTHENGOTO1712IFptr.key=desiredTHEN12IFptr.key=desiredTHEN13found_TRUE13found_TRUEELSEELSE14ptr_ptr.next;14ptr_ptr.next;ENDLOOP;ENDLOOP;15IF~foundTHEN15IF~foundTHEN16ERROR['Notinlist'];16ERROR['Notinlist'];17--nextstatement17--nextstatement3.2.2.2Control-flowoptimizations:one-to-manyandmany-to-onesource-to-objectcorrespondencesAsomewhatmorecomplexsituationariseswhenoptimizationspreservetheorderofexecutionofinstructionsthataremeaningfultotheprogrammer,butcreatecorrespondencesbetweensourcetextandobjectcodethatarenolongermonotonic.Icalltheseoptimizationscontrol-flowoptimizations;theyrearrangetheobjectcodeforaprogrameitherbymergingidenticalcodesequences,therebymakingtheprogramsmaller,orbycopyingcodesequences,therebymakingtheprogramfaster.MergingoptimizationsExamplesofmergingoptimizationsincludeprocedurediscoveryandcross-jumping.Procedurediscoverylocatesidenticalsequencesofinstructionsandformsasinglenewprocedurethatiscalledfromeachoriginallocation.Cross-jumpingisaspecialcaseofprocedurediscoverythatexaminescodepathsthatjoin.Ifthetailportionsofanytwoofthepathsarethesame,cross-jumpingmovesrïgî—tî•ïgïgî{rî¦ïgtïgîWrîŒïgtïgîŸ ïgî'Þî*érïgî-Ætî.˜ïgïgî/lrïgî4¨tî5-ïgrïgî6jtî7hïgïgî8;ïgî;œrïgî>Štî?©ïgïgî@bpïgîMÓrïb)îâîƒî[îaîjî…tî#¨ïb)ïb)î#ø rïb)î)Oî+î.é î7Q tî>°ïb)ïb)î>ÿ rîEEïb)ïb)zï_!î¤îªîî]î¶îï_!î%áî'çî)íî+ôî-Mî0­î2î3`{î6¿ï_!ï_!î7 î7ëî9ö zï]yî¤îªî°î îcî¼ï[Òî¤î°î îcï[Òî%áî)íî+Gî, rïX=î¤ îÙîIîúî"”î$Øî'Öî)tî. î/žî3óî5î:î<Ðî@âîC<îEïU{îâî…îÚ îÉî†î!5î#Šî)ßî,­î2´î89î> îCcîD‚îH±ïRºîâîî2îðîî{îÏî$î%sî'Ýî)€î+Ôî.^î/©î1 î7äî9Éî>î@ÌïOøîâ î_îñîŸî*c î3Yî6Sî:4î?£îAÖîDºïM6îâ îBîÏîŽî Gî".î$»vïM6î*Erî.}ïM6ïM6î08î1èî4u î<…îA îBéîH�ïJuîâî¨îöîŒîéî î" î#5î'åî+wî-#î0µî1Ü î8Ëî:4î;ÊîAýîD¹ïG³îâîwîîîî!—î'©î,Nî.î4†î6 î9ïî=Ùî@nîBàîD�ïDòîâîîî¶îîßzïAêî¤îªî¶îïAêî)Aî+Gî/Sî0­ï@Bî¤îªî¶îiîÂîuî!(î"‚î&Žî)Aî+Gî/Sî2î3`î6ï>›î-Mî/Sî3`î6¿î8Åî:Ëï<óî¤î°î¶îîuî#Ûî)Aî-Mî/Sî4¹î6î;xï;Lî¤î¶îÂîï;Lî)Aî/Sî3`î4¹ï9¥î°ï9¥î-Mï7ýî¤î¶îiîÂï7ýî)Aî/Sî2î3`ï6Vî°ï6Vî-Mï4¯î¤îªî°î îï4¯î)Aî+Gî-Mî.§î2³ï3î¤î° îî"ï3î)Aî-M î4¹î6¿ï1`î¤|îªï1`ï1`îVî¯î ï1`zî)5ï1`ï1`î)á|î+;ï1`ï1`î+çî-@î0žwï,jîâî0 î î#ü î+Òî.r î6Iî@Hrï(Gî¤îîzîüî"oî'ùî+§î/K î7·î=î?mîCîD¹ï%†îâî• îïî¸î î$>î%æî(@ î0uî2ñî6îîA6îFŸï"Äîâîöî î~î!î Kî"ûî%]î)ý î2kî3Ðî6·î:œ uîCuï"Äï"ÄîD rï îâ îºîùî"Eî$Ôî)î,‘î.ýî0Uî6î:.îŠtî?©ïgïgî@bpïgîMÓrïb)îâî8îûî�îÄîZîüî#žî&ûî(Ìî-Ìî2úî9%î:Êî= îAÉîGOï_gîâî™î+î×î)îâî Aî%Ñï[Òî¤î# î�î#ƒî$ž î,� î6Wî9®î;þî@>îBæîD…îFÕïYîâî8îÞ îî'! î1î5¤î;Æî>úîCy ïVNîâî½ îmîðîÝî&6î)øî+´î- î4î5ýî;¯ îCîD¬îEúïS�îâî%î‰î³î 5î#î$oî&úî)Æî-|î3„î6Ÿî7Éî>L ïO÷î¤îuî€îòî#øî%âî+(î,Ú î6~î9eî; îAÊîC¨îFYîH7ïM6îâîàî§ îoîbî'î î"| î(rî*Dî,²î1î4cî6æî:Qî?äîAíîC%îFÒîH�ïJtîâî î@îî? î!]î&4î(ãî* î-î1ûî6Æî;Õî=†î?éîF"îI@ïG²îâî·î/îÆîEî ´ î'î(aî-Wî/¶î1 î8î:<î;ˆî?ùîFPîH ïDñîâîî¿î�î&îG î#/î%,î&M î+êî1P î8Pî:î<®î?ìîBCîHCïB/îâîuîž îŽîËî#î$äî&êî-î/î3á î<Íî?xîCBîE2ï?nîâî$îaî©îˆî$˜î(Íî.¥î3·î9�î=xîA—îCþ ï<¬îâî²îíîÅîkî¹î"×î'*î*=î+· î2‹î4î6©î=î>áî@öîG‡ï9ëîâîHîq îbîûî Xî%cî'î)î*, î0úï6Uî¤î0 î!î bî$eî&Äî*dî/Yî3œî5®î;äî>"î@_îFRîHþï3“îâîJ î^îîòî!¸î$%î(û î/•î1;î5Wî;™î@ÈîD_îEØï0ÒîâîîÎîvîCîoî!Éî$î&�î+•î0Dî2· î9¼îîC´îGZï.îâîøî=î©î‰î î1î!gî$ëî&ˆî+Pî.Çî1ýî6  î?: îG¨ï+OîâîbîÊ îºî}î"¶î$zî*@î,Ÿî/î2õî6î7Õîpî@%îC‡vï/îF³rîJï/ïnîâî_îâî½îtîÚî!ƒî%Tî'¯î-Oî2Ùî9 î;°î=›îC&îDÏï¬îâîòî5î€îÔî#•î&î)ºvï¬î+Ærî-vï¬ï¬î-Ùî.ïî3-î6T î=S îE³îH�ïëîâîžîîî!Ùî#ˆî'× î.‘î1ùî5@î6jî9» î@·îCÝîF<ï )îâîöîhî’ î!¬î'µî*Aî/æî3zî4¤ î;•î=›îCÑÿ ‡TVm$fCHAPTER3:OPTIMIZATIONANDTHEPROBLEMSITCAUSESFORDEBUGGING5410FORiIN[1..6]DO10FORiIN[1..6]DO11IFEven[i]THEN11IFEven[i]THEN12{x[i]_i;12{;GOTOL;13filled[i]_TRUE}13}ELSEELSE14{x[i]_2*i;14{;L:;15filled[i]_TRUE};15filled[i]_TRUE};ENDLOOP;ENDLOOP;Thereisalsoaconnectionbetweenreportingthecorrectsourcelocationanddisplayingthevaluesofvariables.SupposethattheTHENarmoftheIFstatementdeclaredalocalvariabley,whiletheELSEarmdeclaredalocalvariablez.Ifthedebuggeralwaysthoughtthattheexecutionoffilled[i]_TRUEcorrespondedtosourcestatement15,thenitwouldneverallowtheusertodisplaythevalueofythere,becauseyisnotinstatement15'scontext.CopyingoptimizationsExamplesofcopyingoptimizationsincludeloop-unrollingandinlineprocedureexpansion[Allen+72].Loop-unrollingmakesmultiplecopiesofthestatementsinsideashortloopinordertoreducetheeffectsofloopoverhead.Inlineprocedureexpansion,alsoknownasprocedureintegration,replacesacalltoaprocedurebyaninstanceoftheactualcodeoftheprocedureinordertosavetheexecutiontimeassociatedwithprocedurelinkage(suchasmovingparameters,savingandrestoringregisters,andallocatinganewactivationframe).Inlineprocedureexpansionmayalsoprovideopportunitiesforfurtheroptimizations.Copyingoptimizationscreateaone-to-manycorrespondencefromthesourcetexttotheobjectcode.Suchacorrespondencemakesitdifficulttosetbreakpointsandtoprovideproceduretracebacks.Inlineprocedureexpansionisillustratedinthefollowingexample.ProcedureP1hasbeenexpandedatbothofthecallstoitfromP3.SincetheprogramcontainsnoothercallstoP1,nofreestandingcodehasbeengeneratedforit.Therefore,anybreakpointrequestedinsideP1willbeplacedonstatement14.Inordertoachieveaneffectivebreakpointatstatement11,theusermustbeawareoftheoptimizationandplacetwobreakpoints:oneonstatement31,andoneonstatement33.Aneffectivebreakpointonstatement12cannotbeobtained.Ifaprogramexceptionoccursinsideanexpandedprocedure,itwillbereportedatitstop-levelinvocationpoint,causingtheusertothinkthatsomethinghasgoneawryintheprocedurelinkage.Finally,procedurerïgî—tî•ïgïgî{rî¦ïgtïgîWrîŒïgtïgîŸ ïgî'Þî*érïgî-Ætî.˜ïgïgî/lrïgî4¨tî5-ïgrïgî6jtî7hïgïgî8;ïgî;œrïgî>Štî?©ïgïgî@bpïgîMÓzïbjî¤îªî]î¶î¼îuïbjî%áî'çî*šî+ôî-úî2³ï`Âî¤î°î¶îï`Âî%áî)íî+ôî1Yï_î¤î¶îÂîï_î%áî+ô|î, ï_ï_î-Mî0«zî2ï_ï_ï]sî, î.§î0­ï[Ëî¤îcî"î {ï[Ëî%áî+ôïZ#î°ïZ#î)íïX{î¤î¶îÂîïX{î%áî+ô|î, ïX{ïX{î-Mî0«zî3\ïX{ïX{ïVÔî)í|î, ïVÔïVÔî-Mî1WzïU,î¤îcî"î {ïU,î%áî, î3`î4¹ïS„î°ïS„î)írïOîî¤îÁîHî0îu î"Œî(î./î0ªî5Wî9Âî?îAç îH�ïM-îâî%îó îµî!Oî$3tî&§ïM-ïM-î'arïM-î*‚î-oî/=tî1²ïM-ïM-î2rïM-î3oî9¹î?Tî@“îCîvîI:ïM-rïM-îJïJkîâî‘tîêïJkïJkî£rïJkî3îî ƒî!§î$çvî*ïJkrïJkî*ðî,Dî-Àî0î6î:{î?—îB`îD¹ïGªîâvîŸïGªïGªîvrî6ïGªvïGªîærî¾ïGªvïGªînrïGªîV î&ãî(•î,èî3!î5bî8‹î9åî>îAåîE’îGõïDèîâî�îCî¢îLvîïDèrïDèîaî"Cvî'eïDèrïDèî(Áî*,î,¡î.Oî4…î7Guï@Åîâî< rï=/î¤î!îî� î(<î-Z î6¤î9™î=·îDxtï:mîâ rîJï:mï:mî¯ îAî#|î(øî-(î.äî1E î8î<î=1î@²îCÙîE‰îI@ï7«îâî´îjîîî šî(î,kî3D î:iî=ŒîBgîDkï4êîâ îBî›îÜîî!Dî"…î) î+3î-:î2Ÿî4pî6æî;î>_î@/îB¦îI@ï2(îâî³î}î�îî jî#¬ î*4î-kî4 î8îî<µî>€îC� ï/gîâîîÖî“ î!Pî$ î*@î+lî.] î4Ÿî9ïî=óîDxï,¥îâîæî²î½ î"%î$cî) ï)î¤î# î�î#„î$ž î,� î6Wî9®î;þî@>îBçîD…îFÕï&Nîâî†î;î¥ î"¯î'(î(¿î.7î0&î2„ î:9î=1î? îDkï#Œîâ ïöî¤î·îLî"Õî$S î*Òî,’î/î5(î;¢vïöîBƒrîE ïöïöîEÑîG’ï5îâîî²îêîŸîúî!î"®î$vï5î'»rî)kï5ï5î*Âî.sî0Îî6Xî;·î=¹îASîD^vï5îF`rîHï5ï5îHèïsîâ î¶îî�îåî&8î(}î*½ î1}î4% î;îAfvïsîE»rîHCïsïsîIAï±îâîàîHî[îžî yî"Uî&î'Òî,Éî.Çî4X î;Vî<ûîC>îEˆîGõïðîâî^îbîlî8î« î$¸î'‚î+*î-ê î5ëî8ªî:ÄîA îC^îF)îHèï.îâîî�îÜîM î&*î(î.>î0î4xî6Uî<ºî>(î?>îD¹ïmîâî0î<î6î€ î&dî'Äî*yî,sî2 î3®î5’î;L îBîFï «îâîuî¢î„îWîYî$0î&Øî*hî-øî/Ùî2mî9#î?.îDkÓTVm$ CHAPTER3:OPTIMIZATIONANDTHEPROBLEMSITCAUSESFORDEBUGGING55tracebackinformationwillneverincludeanexpandedprocedure.Ifaninlineprocedurecallsanotherprocedure(whichmayormaynotalsobeexpanded),anexpandedprocedurecouldlogicallyappearanywhereintheprocedurecallchain,andinlinecallscouldbenested.InthefirstcalltoP1,theparameter(1)issufficientlysimplethatthecompilersubstituteditdirectlyfortheuseofi.Thisoptimizationiscalledsubsumption;itissimilartocopypropagation.ThissubstitutionwouldcreateproblemsfordisplayingthevalueofiifabreakpointcouldbemadetooccurwithinthatexpansionofP1,orifaprogramexceptionoccurredthere.10P1:PROC[i:INT]=11{a_i;12count_count+1};13P2:PROC=14{x_5};14{x_5};......30P3:PROC=31{P1[1];31{a_1;count_count+1;32b_2;32b_2;33P1[5-b];33i_5-b;a_i;count_count+1;34x_a+b};34x_a+b};3.2.2.3Coderearrangement:problematicalcorrespondencesbetweensourceandobjectTheuserwhomonitorsacomputationneedrarelybeconcernedwhencompiler-introducedcomputationsforaddressing,subexpressioncomputations,andsoonaremovedoreliminated;thesecompilertemporariesareoutsidethesource-levelmodelofexecutionanyhow.[Asdiscussedbelow,suchmovementcancausehistoryproblemsforamonitoringdebuggerorproblemswithmodifyingthevaluesofvariablesformoresophisticateddebuggers.]However,iftheoptimizerrearrangestheorderofexecutionofprogrammer-specifiedinstructions,severalnewproblemsarise.ConventionaldebuggerbehaviorwhenentirestatementmovesasaunitLetusfirstconsiderthecaseinwhichoptimizationsmoveanentirestatementasaunit.Supposethatcodemotionhasmovedanassignmentstatementwithaloop-constantexpressionoutofaloop,asshownbelow.Iftheoptimizerleavesthestatementmarkerinitsoriginalposition,thismovementwilllookthesameinthestatementmapsasadeletedstatement.Thereforearïgî—tî•ïgïgî{rî¦ïgtïgîWrîŒïgtïgîŸ ïgî'Þî*érïgî-Ætî.˜ïgïgî/lrïgî4¨tî5-ïgrïgî6jtî7hïgïgî8;ïgî;œrïgî>Štî?©ïgïgî@bpïgîMÓrïb)îâî5 îòîÑî#Îî(áî+î1x î9=î:òî=îA)îGßï_gîâî0îöîÀî#î%î(Uî+ î.î0Q î7¦î9Ùî@]îG#ï\¦îâîOîÖî î ¹î#î)›î,&î03î2ëî6Ëî9Úî=¦î?—ïYî¤îsîÓî«î6vïYî8rîèïYïYîÄî"$î(¦î*Îî,: î3Lî7±î:î<ßîBš îI˜ïVNîâî¾îâî(î„vïVNî�rîhïVNïVNî–î!— î)vî*Èî.¦ î7-î8jî9¼î>(î?½îBö ïS�îâî î­îøî"î(>î*˜ î1Bî3¿î7†vïS�î9’rî;BïS�ïS�î;¥î<Àî> îEîHþïPËîâî¢îPîîUî$î%švïPËî'§rî)WïPËïPËî*3î+÷î-Xî.‚î4î:Fî?÷zïMÃî¤îªî]îÂî"ïLî¤îî îcïJsî¤î°î¼îî"î {ïG$î¤îªî]î¼ïE|î¤îî îcïE|î%áî)Aî+Gî, ïCÔî°ïCÔî)íïB-î°ïB-î)íï@…î°ï@…î)íï>Ýî¤îªî]î¼ï=6î¤îï=6î%áî)Aî+Gî, ï;Žî)íî-úî/Sî3`î4¹ï9æî¤î°î îcï9æî%áî)íî+Gî, ï8?î¤î°îîiï8?î%áî)íî+Gî, î-úî/Sï6—î)íî+Gî, ï4ïî)íî-úî/Sî3`î4¹ï3Hî¤î°î îcî¼îï3Hî%áî)íî+Gî, î-úî/Swï.Qîâî0î¹ î = î(Äî2øî89î<’î?2rï*.î¤îœî¶îÚî Àî" î*%î-¢î1­î3¾î:wî>Lï'lîâ î”î î!U î*S î3]î6Hî8?î:yî=îA¹îC± ï$ªîâî„îW îïî"[î'=î)µ î1Xî5©î7zî=ÈtîCõï$ªï$ªîDEîEÿï!éîâîwîî�îªî³î#kî(Pî*+î++ î0ëî5Ðî7Kî¼îDîF îIsï'îâîˆîdîQ îç rï'î%ƒî+Íî-Cî/·î5ö î<­î?!îBëîD¹ïfîâî›î. î%æî*vî-dî3muïCîâ îîÙî"Iî%Ëî)›î/®î3³î5lî6¡rï¬î¤î[îbîqî"î!¹î$ßî&Äî+ î3¾î7´î9Üî=ÿîDlîFRîG³ïëîâî^î#î`îî!€î%ýî'ä î.ìî5î8*î9J îAÊ îHyï)îâî­îéîxî8î™î ¥î"9î$«î*æî/î1vî7½î<Œî>Lî@9îETï hîâî±î£î|îÃî!Pî$ûî&×î)dî/Èî3”î5pî6Çî;Ê îC6îIůTVm$„CHAPTER3:OPTIMIZATIONANDTHEPROBLEMSITCAUSESFORDEBUGGING56breakpointrequestedonstatement32willbeplacedatthesamespotasabreakpointonstatement33.Todecidewhetherthisplacementcausesaproblem,thequestionsthattheprogrammerwishestoanswerviathisbreakpoint(asdiscussedinSection2.2.2)mustbeconsidered.Whenthebreakpointatstatement32isreached,theprogrammerhasseveralexpectationsconcerningtheprogramexecutionstate.Theseexpectationsareadirectreflectionoftheunoptimizedprogram'sexpectedbehavior,i.e.,theprogramexecutionmodel.First,sheexpectsthattheassignmenttoxwillnothavebeenexecutedyet,soxshouldhaveitspreviousvalue,1.Second,ifabreakpointisalsoplacedonstatement33,sheexpectsthatx'svaluewillchangebetweenthefirstandsecondbreakpointsonthefirsttimethroughtheloop.Third,ifthedebuggerallowsvariablemodification,theuserexpectsthatchangingthevalueofcatthebreakpointwillbereflectedinachangeinthevalueofx.Thereisalsoamoresubtleexpectationinthisparticularexample:ifabreakpointisalsoplacedinsidethefunctionFun,thebreakpointonstatement32shouldprecedethatbreakpoint.Noneoftheseexpectationswillbevalid,andconsiderableconfusioncouldresult.Supposethatrange-checkingisenabledandFun[c]returnsavaluethatisoutsidex'srange.Aruntimeexceptionwillbetriggered,andthedebuggerwillreportthatthecurrentexecutionpointisinsidestatement29.Thisreportwillleadtheusertothinkthatcomputingd+1hascausedtheillegalvalue.10x_1;10x_1;......29c_d+1;29c_d+1;x_Fun[c];30FORiIN[1..10]DO30FORiIN[1..10]DO31a[i]_i;31a[i]_i;32x_Fun[c];3233b[2*i]_a[i]+x;33b[2*i]_a[i]+x;ENDLOOP;ENDLOOP;Codehoistingandcodereorderingcancausesimilarproblems.Meaningofmappingbetweensourceandobject:semanticandsyntacticmappingsItmaybedifficulttodecidewhatobjectcodecorrespondstoagivenprogramstatement.Forsimplicity,wefirstconsiderthecaseinwhichoptimizationsmoveanentirestatementasaunit.Inthiscase,theobjectcodelocationcorrespondingtothestatementcanbedefinedintwodistinctways.rïgî—tî•ïgïgî{rî¦ïgtïgîWrîŒïgtïgîŸ ïgî'Þî*érïgî-Ætî.˜ïgïgî/lrïgî4¨tî5-ïgrïgî6jtî7hïgïgî8;ïgî;œrïgî>Štî?©ïgïgî@bpïgîMÓrïb)îâ îÈîýîùî$#î%ýî(žî*ƒî.Óî0aî2µî6(î9î:¹î;Ø îB½îD¹ï_gîâï[Òî¤îºîîAîÑî&Yî*�î+šî1fî3´î9·îà îF”ïYîâîÓî±î1î î"Hî$²î*þî,îî2î6î9»î;î îD4îH�ïVOîâ îþîÂî#î 3î!Êî'oî)ú î2î4¨î9d îA] îH�ïS�îâîyî·îÖî"à î*·î-î.Eî20 î8Wî:î<� îDƒïPÌîâîžî¦î9î˜î%&î+Zî0nî4 î6€î;Sî>!î@€ îG�vïPÌîI’rïN îâî‘î îTîµî uî#vïN î%2rî&âïN ïN î'fî+aî.¬î0Šî6î:#î<;îAlîBÐîCþ ïKIîâîEîîZîWî„î!¸î$$î(ðvïKIî,rî,éïKIïKIî-Bî.Aî1âî4„î9#î>‰î@ßîC®îF\ïH‡îâ îCî6î‚îFî Xî%|î'Èî+¡î/Çî1î3`î9Uî=oîB’ ïEÆîâîSî^îCî#î"î$‚î(=vïEÆî*Jrî+ùïEÆïEÆî,Ÿî-£î0 î7î9Óî;ÕîAŒîCLîD‡îI@ïCîâî:îÜvïCîèrîÀïCïCîî îoî!4î"Vî%âî)è î1*î2Ðî5j î;˜îA‚îBÜîCþ ï@Cîâî�î¹îdîµîdvï@Cî%2rî'¹ï@Cï@Cî(åî+” î2Ôî5*î;¯î=ãîB¯îH ï=�îâ î®î}î6î¿ î'�î*8î,)î/èî2  î:Žî@ÙîD¤ï9ìî¤î î¼ î#î$hî)vvï9ìî,�rî2hï9ìï9ìî2íî6þî8 î;–î>Fî?”vï9ìîD±rîE‰ï9ìï9ìîEáîFÌï7*îâî—îöîTî'î!@ î'’î*qî,ùî3*î5þî:Iî=@î?ÇîD¹ï4iîâî—îî2î}î!kî$›î(Õî+—î.¦î1î4,î5ðî9¦î<Švï4iîC¹rîD‘ï4ivï4iîEArîFï4ivï4iîFÉrîHyï4iï4iîI@ï1§îâî^î¾îÊzï.Ÿî¤îªîî]ï.Ÿî%áî'çî)Aî*šï,÷î°ï,÷î)íï+Pî°ï+Pî)íï)©î°ï)©î)íï(î¤îªîî]î¶îï(î%áî'çî)Aî*šî+ôî-Mï&Zî'çî)Aî*šï$²î¤îªî]î¶î¼î"ï$²î%áî'çî*šî+ôî-úî3`ï# î¤î°îîiï# î%áî)íî-Mî.§ï!dî¤î°î îcï!dî%áï¼î¤î°îiîÂî"î {ï¼î%áî)íî.§î0î3`î4¹ïî°ïî)írï€î¤îMî„î;î ‚ î';î)Æî-{î2uï]îâî–î:î·î Óî%î'¦î,î1¤î4Hî9ÞrïÈî¤îî îóî!îÆî#î&kî*{î-¸ î5Pî6ôî8î;¿îAE îHCïîâ îoîŠîWîÅî"î$üî&žî*¡ î3î6Æî8«î<ŒîB¶îDXîEvîIï Eîâî™îöîkîšî÷î$D î-Pî/î1Šî7Öî:wî<}îA”îCWîFï ƒîâÿbTVm$ CHAPTER3:OPTIMIZATIONANDTHEPROBLEMSITCAUSESFORDEBUGGING57Onenaturaldefinitionyieldsasemanticmapping:namely,thecorrespondingobjectcodeistheobjectcodethatperformstheoperationsspecifiedbytheprogramstatement.Supposethatcodemotionmovesaninvariantassignmentstatementsoutofaloop.Then,ifexecutionofscausesaprogramexception,thatexceptionshouldbereportedasoccurringwithins.(Reportingthelocationofanexceptionutilizestheobject-to-sourcemapping.)However,theinformationthatauserwantstodiscoveraboutherprogramasaresultofalocationbreakpointmaynotbediscernablefromanyversionofsemanticmapping.Forexample,thesemanticmappingofaloop-invariantassignmentstatementisexecutedonlyonceperentireloopexecution.Therefore,abreakpointbasedonasemanticmappingcannotbeusedtoexaminevariableseachtimearoundaloopifitisunknowinglyplacedonaninvariantstatement.Thesyntacticmappinghasquitedifferentproperties.Itpreservesthepositionofastatementwithrespecttoitsneighboringstatements;itcanalsobeviewedasanindicatorof"howfarintothesourceprogram"thestatementis.Noticethatsourceandobjectentriesincreasemonotonicallytogetherinthesyntacticmappingforcomputation-reorderingoptimizations,asinstatementmappingsforconventionalcompilers.Incontrast,thesemanticmappingcanbeorderedeitherbysourcelocationorbyobjectlocation,notbothatonce.SemanticmappingwhenentirestatementmovesasaunitWhenoptimizationsrearrangestatements,theobjectlocationcorrespondingtotheendofonesourcestatementisnolongerequivalenttotheobjectlocationcorrespondingtothebeginningofthenextsourcestatement.Therefore,forthesource-to-objectmapping(i.e.,settinglocationbreakpoints),wemustagainconsidertheinformationthattheuserisattemptingtogatherwiththebreakpoint.Iftheuserwantstoexaminethevariablestatebeforetheexecutionofastatement,eithertoseethevalueofavariablebeforeanassignmenttoit,ortosee(andpossiblymodify)valuesofvariablesthatwillbeusedtoevaluatethestatement,thebreakpointshouldbeplacedbeforethenewlocationoftheobjectcode.Iftheuserwantstoseetheeffectsofexecutingastatement,thebreakpointshouldbeplacedafterthenewlocationoftheobjectcode.Withaconventionaldebugger,asemantic-afterbreakpointistypicallyplacedonthefollowingstatement(s),orisperformedbyplacingabreakpointonthedesiredstatementandexecutingasingle-stepcommanduponarrivalatthebreakpoint.rïgî—tî•ïgïgî{rî¦ïgtïgîWrîŒïgtïgîŸ ïgî'Þî*érïgî-Ætî.˜ïgïgî/lrïgî4¨tî5-ïgrïgî6jtî7hïgïgî8;ïgî;œrïgî>Štî?©ïgïgî@bpïgîMÓrïb)î¤î¿îŠ îìî#ïuî%1ïb)ïb)î%µrïb)î*ßî1+î6nî8å îAôîF$îIƒï_gîâî^î“îöîàî!Øî$T î+î0öî3î5Šî;5 îBîH ï\¦îâî?îîkîqî#L î*svî0¾ï\¦rï\¦î20î4»î6Šî7Éî;õî@îAyîGÃvîI’ï\¦rïYäîâî!îPîã î vî#Iî)„î.î/ûî5�î7Cî=gvîA±ïYärïYäîBˆîCó ïW#îâîAîxî1î"î Wî$þî'^î1_ïSŽî¤îöît î"î%î&Oî)fî-eî/1î4²î8²î;Eî@ñîB½îDîGîîIÅïPÌîâî î î î �î"q î)¤î- î/«î4sî6+î;ÜîBrîEïN îâî[î%îûîÍî  î) î05î6„î8 î=àîAîDtîGïKIîâî î î½î â î'Íî+ªî-«î.Ðî4|î:2î>©î@•îCÌîEvïH‡îâîÆî înî Uî!¨î$öî&€î'ÿî)” î1÷î6{î8ªî:Äî@³ îHuïEÆîârïEÆî¥îŽî1î èî&» î.hî0 î67î8Äî>3î@îAqîGÓïCîâî¡îfîX î î&dî'Ñî*sî-Wî/^î4î5áî7éî=Æî?–îCbîE îH�ï@Cîâî1îqîÐî"ï<­î¤î îÐîîÀî#Íî(2î-i î6Sî;¬î=Nî?£îE3ï9ìîâîî¤ î(hî*î+¡î1Åî7óî: îB' îIï7*îâîdîÀînî"'î$¯î&�î+»î/¤î1�î5êî;î<ßî>×îBíîHyï4iîâîî·uï0FîâîÑîNîÐî! î'´î+¹î-rî.¦rï,±î¤îµ î,î$D î+Pî-©î1¼î6í î?ÝîA…îCßîF�îHCï)ðîâî=î}îôîî!T î(î)Èî,2î0Vî5˜ î>šî@TîB¿îI5ï'.îâîŒîæî� î!( î(+î*³î-]î7©î=¯îAîE·ï$mîâ îî8î”î 2î%Ÿî'ó î/qî24î4‡î7uî8Õ î?¯îARîE€îH�ï!«îâ î×îmîàîîî!ãî#¥î)2î+¦î0ðî45î8™î; îAVîC#îD` ïéîâîèî±îî˜î\î/î rî%Ãî*,î,6 î3bî5*î6òî8Ðî:™î=î@QîE¸ï(îâî-îîÚîÅî Œî"šî%òî'½î-=î/º î6dî8à î?íîD†îF“ïfîâîRîÒîàî8î î"‘î&Ëî+/î,Ñî/Qî2kî6mî8<î:°î=0îA îCzîIÅï¥îâ îšî% î@î#çî&î*ˆî-îî0xî3‘î8óî:Öî=`îA¤îFîIÅïãîâ îàî&î3 î&ù î-Íî/î4†î8Åî:¯î<óîBé ï"îâîÝî€î|î¯î ¯î" î)8î+uî. î3 î9yîŠtî?©ïgïgî@bpïgîMÓrïb)î¤î{î�î  î&/î+ßî.–î41î:pî<­î=ÖîCdîI@ï_gîâîîƒîfîî!„î'–î.4vî0—ï_gï_gî2Gî3÷rî6ï_gï_gî7�î9 îBîD÷îG’ï\¦îâîhîî8î˜|ïZ#î%á}î2¬ïZ#ïYOzïYOî4›î5õî7NïWˆî¤îªî]î¶î¼î"ïWˆ|ïX[î&Ž}î2­ïX[ïWˆzïWˆî4œî7Nî8¨î:®î@ïUàî¤î°îîiïUàî6î9rî:ËïT8î¤î°î îcïRqî¤î°îiîÂî"î {|ïRqzïSE|ïSEî)ì }î2­ïSEïRqzïRqî5õî:®î<î?gî@ÁïPÉî°ïPÉî6uïL¦îâîÑîNîÐî#äî%OrïIî¤î)îþîî†î ëî&Œî(?î,S î4Õî9+î;�îAËîC‰îD¹ïFNîâî1 îéî³ î"Êî(î-î1©î3t î:æî=ÇîAWîCßîFRïC�îâîëîüîq î ­î#š î)ûî+Éî.>î4î9Õî<'î?nî@­îFøîHyï@Ëîâîî¿î®î î"uî'9î+eî.&î/Çî0ä î8ñî=·î>ÔîCþ ï> îâîúîþîî”î/î"Xî$’î*¢î,6î.±î2¤î5Åî7Ýî: î@ÝîC� ï;Hîâîî îÞî î!Îî"øî(¨ î/™ï7²î¤wîœï7²ï7²î�îî î% rî+%ï7²ï7²î,î-æî/ýî2lî5U î<@î? îFÐîH�ï4ðî¤ î‚îvîR î&Èî(¼î+W î2Þî64î7Ûî:vî?² îF�îIƒï2/î¤î�îåî*î î!Òî#gî&rî*‡î-;î/Íî1¤î4Çî6©î8ï î?ÍîA5îE>ï/mî¤ î^ î!‹î"æî(î+9î,S î33î6'î8îiîAÖîE-îG½ï,¬î¤îÙ îNî rî"Ú î)ýî- î0-î3öî6Íî9Kî;DîAîFŠîH�ï)êî¤îÙî îiî Åî$zî&Ùî*ƒî-Qî/üî1íî5)î7%î9„ ï&Tî¤wîYï&Tï&TîLî§îÀ î$’ uî*¤ï&Tï&Trî+Àï&Tï&Tî,ßî2Aî3ùî6bî81î=÷î?„îBöîCþ ï#“î¤î©îîß îºuî!rï#“ï#“î" rï#“î$ð î-æî1çî3  î;Ùî?Mî@v îFÀï Ñî¤îîî¼ î%î(‡î)®î-— î4†î6Šî7±î=åî@±îBîGÕïî¤îîî îîsî%­î)|î-6î1 î8}î::î<�îBˆîE îH›ïNî¤îzî�îÿî¹î"Lî$ î)î+¿î-M î5×î:uîAîGÓïŒî¤î1î#­î%ªî(Nî-\î3;ïŒî8·î;²î>¹î@¶ îH7ïËî¤ îdî]îÎî#Vî)«î-=î/,î2î4î:sî=—î?îCîF'îG|ï î¤îLîîeîµî n î(fî*mî,Ì ïsî¤wîõïsïsîèîtîfîÒrî"ôïsïsî#àî%³î'Éî*8î- î4 î6è î>™î@WîC îI5ï ²î¤ îÞîî"?î'ùî)òî,O î3[î5¬ î;Èî=~ îD¹ÿ8TVm$CHAPTER3:OPTIMIZATIONANDTHEPROBLEMSITCAUSESFORDEBUGGING59stateincludesfunctionactivationsandchangestouser-declaredvariablesvisiblefromthestatement'sscope.Itisimportanttoprecedefunctionactivationsbecausethefunctionmayhaveside-effects,ortheusermayhaveplacedabreakpointinsidethefunctionoroneofitscallees(andthisbreakpointshouldbereachedbeforethatinnerbreakpoint).Itisimportanttoprecedechangestovisiblevariablessothatembeddedassignments,suchasFORloopvariableassignments,assignmentexpressions,orassignmentstovisiblevariablescausedbyfunctioncalls,willnotyethaveoccurred.Definition2attemptstobringalocationbreakpointclosertothestate-changingportionoftheobjectcodeforastatement.Itrelaxesthenecessitytoplacealocationbreakpointforastatementthatincludestheevaluationofasimplecommonsubexpression(thatdoesnotinvolvefunctioncalls)ontheobjectcodethatevaluatesthatsubexpression.Forexample,thesubexpression'scodemayhavebeenmovedoutsidealoop.However,thisdefinitioncancauseunexpectedbehaviorforvariablemodificationfromthedebugger:ifasubexpressionhasalreadybeenevaluated,thenusingthedebuggertomodifyitscomponentscannolongeraffectitsvalue.However,relaxingthisconstraintcouldcauseconfusionevenifthedebuggerdoesnotallowmodifyingthevaluesofvariables.Supposethatasimplecommonsubexpressioncausesaprogramexception,suchaszerodivideoroverflow.Thentheexceptionwilloccurbeforethebreakpoint,ratherthanafterthebreakpoint,asitwouldinaconventionalsystem.TheIBMFDSsystem's"nosourcechange"modewouldallowonlysimplercommonsubexpressionstoappearbeforethebreakpointforastatementnamely,thosecommonsubexpressionsthatinvolveonlycompilertemporaries.Thismodecouldstillcreateanexceptionbeforethebreakpoint,unlesstheoptimizerrestrictedcommonsubexpressionsevenfurther,tothosecommonsubexpressionsthatcouldbeguaranteednottocauseexceptions.3)Beforefirstvariablestatechange,oronthefirstinstructionthatcorrespondstoanyalterationofuser-visiblevariablestatespecifiedbythestatement.Analterationofuser-visiblevariablestateisanychangetoauser-declaredvariablevisiblefromthestatement'sscope.Thusembeddedassignmentswillnothaveoccurredyet,butsomebreakpointsorexceptionscorrespondingtosubcomponentsofthestatementmayalreadyhaveoccurred,asnotedinthepreviouscase.4)Beforekeystatementeffect,oronthefirstinstructionthatcorrespondstothecoresemanticeffectofthestatement.Thedefinitionofthekeystatementeffectforeachstatementwouldrïgî—tî•ïgïgî{rî¦ïgtïgîWrîŒïgtïgîŸ ïgî'Þî*érïgî-Ætî.˜ïgïgî/lrïgî4¨tî5-ïgrïgî6jtî7hïgïgî8;ïgî;œrïgî>Štî?©ïgïgî@bpïgîMÓrïb)î¤îî³î j î'lî*`î/Êî1¶ î:fî@^îDëîH�ï_gî¤ îÎî¦î6î »î'5î(üî.6î3È î:¥î?àîBXîGêï\¦î¤î÷ îzîKî ¸î#¾î&Ïî*#î.Œî/à î6Àî:Ðî=<îBÃîD•îGNîIïYäî¤îî;îã î"Úî'\î)Sî.|î2Ñî5¦î9K îA�îCîD�ïW#î¤î1î2î=îËî"ùî(“î*6î,ãî3| î;Iî>Ztî?çïW#ïW#î@ rïW#îB´îE¸ïTaî¤ î½ î ù î(ºî*© î2jî4Dî8¿î>¥îCMîEtïQ î¤î î¶î+îtî»ïN î¤ î9îaîäî …î$!î%>î*g î1Kî5)î6Êî9 îBîFãîH�ïKHîâîùî>îyî¡ î ¯î"%î&³î)î.Ëî0wî4 î52î:g îAUîC‘îD¹ïH‡îâîÕî]îá î ©î"†î#Õî(^î.3 î7"î:Žî=ãî@}îEtïEÅîâîgîiîÅîÚîî çî&Ëî)• î34î5Ûî;¨î>îG§ïCîâîÚîîfîáî!žî"½î&¦î,Ïî/e î5¤î8$î;Î îC îH±ï@Bîâî îþîVî!§î(î)lî*‡ î3Bî5¨î:lî=º îD.îGEï=€îâîAîKîùî¶î‘ î'=î)Èî+Îî0î3Þî5¸ï9ëî¤îæî5îä î&Iî*"î-åî4>î7’î9î;mîA„îDÃîGEï7)îâîlî¿îàî‹ î$î)€î,Aî-^î1¶î7Y î@îDCîE`ï4hîâ îyî³îjîwî!®î#{î*î-Àî0(î6gî9î<åîA=îC¦ ï1¦îâî îLî£î î#�î%Jî&¼î+î,Îî. î6Hî;Õî>ÉîB*îE—ï.äîâî›îìîGîî#Oî&úî*î/î4³ î>î?µîD>îH�ï,#îâ îîŠîñî&lî*Hî05 î9Áî<ÌîAÜîE3ï)aîâ î,î>î î!Îî$gî(aî*Iî0uî4¼î7 î>SîBnîDÅï& îâ îîë î$gî'Úî-î.äî2°î8� îB îEîHþï#Þîâ îôîiîîÍ ï Hî¤wîTï Hï HîGîî$î!ƒî%rî)@ï Hï Hî*[î,^î.£î1Bî4Y î;sî>€ îF`îHNï‡î¤ î³î] î Œî%³î(Õî.‚î0oî2À î9³î;÷ îBîC± ïÅî¤î îiîîÔî#«î%ˆî&á î/ƒî4èî9fî<üî?‹ îFÌïî¤î1îû î# î&\î(àî,7î1øî4©î79î:Ü îBaîD5 ïBî¤ î—îB î%ýî'³î*î0Aî3Bî8î;UîA[îCîFäîH�ï�î¤î3ïëî¤wîªïëïëî�îîyî ­rî#óïëïëî$¹î&gî(Xî*¢î-d î4)î6â î>mî@îBOîE>ï )î¤î{î@î« î Ôî#¸ î*î+Óî.?î0àî7!î:ùî=Bî@îFÀÿ 5TVm$ØCHAPTER3:OPTIMIZATIONANDTHEPROBLEMSITCAUSESFORDEBUGGING60begiven,ideallyasapartofthelanguagedefinition.Forexample,thekeystatementeffectofanassignmentstatementistheassignment,andthekeystatementeffectofaGOTOstatementisthecontroltransfer.Thesepossiblebreakpointdefinitionscanbeextendedintheobviouswaytohandleend-of-statementlocationbreakpoints.3.2.3HistoryproblemsTheprecedingsectionshaveshowntheproblemsthatoptimizationscausefordisplayingvaluesofvariablesanddisplayingcurrentexecutionlocations.Thehistoryelementofacomputationreflectssequencesofvariablevaluesand/orexecutionlocations,sonaturallyitwillbeaffectedaswell.However,optimizationscanchangethehistorycomponentofacomputationwithoutchangingtheothercomponents.Forexample,theeffectsofalteringtheorderofevaluationofexpressionscanbevisibleeveninadebuggerwithstatementgranularity.Supposethatregisterschedulinghasinterchangedtwofunctioncallsinsideasourcestatementsothatfewerregisterswillbeneededtoperformthecomputation,asshownbelow.Iftheusertracesthecomputationatmediumorfinegranularity,theexecutionorderingoftheoptimizedprogramwillbedifferentthantheusermightexpect.Similarchangeswouldbeseeniftheuserrequeststwobreakpoints:oneinsideFandanotherinsideG.10v_F[a-b]+G[c+d]/(c*e);10v_G[c+d]/(c*e)+F[a-b];Manylanguagesrefusetospecifytheorderofevaluationofexpressionssothattheoptimizercanperformsuchrearrangementfreely.Nevertheless,similarproblemswithbreakpointortraceorderingariseifanyexpressioncontainingafunctioncallismoved,eithertoanearlierorlaterprogrampoint.Forinstance,ifacommonsubexpressioncontainsacalltothefunctionH,hoistingitsevaluationcouldcausebreakpointsinsideHtooccurbeforeotherbreakpoints.Whensuchacommonsubexpressionisstoredtoacompilertemporary,onlythesehistoryaspectsofthecomputationareaffected.Incontrast,hoistinganentireassignmentstatementcausesincorrectvariablevalues[asdiscussedinSection3.2.1].rïgî—tî•ïgïgî{rî¦ïgtïgîWrîŒïgtïgîŸ ïgî'Þî*érïgî-Ætî.˜ïgïgî/lrïgî4¨tî5-ïgrïgî6jtî7hïgïgî8;ïgî;œrïgî>Štî?©ïgïgî@bpïgîMÓrïb)î¤îŸî¶î1îéîî" î#Ðî&:î, î3Gî5ýî;Øî>Bî@âîG#ï_gî¤îCî îî",î#~î%Ä î-î/°î1öî4rî:�î>?î?Þtî@îï_gï_gîAÜrï_gîD¹ï\¦î¤îîoî!ïYî¤îîÙ î#B î*Šî-�î/÷î6Xî8~î;Wî@ðîD@îFgïVOîâîrî© yïP…îâîÏîÎrïLcî¤îgî¨î´î"æî' î)kî/^î2 î:€î> î@H îFÀïI¢îâîÇî¯î’ î Kî%Aî+£ î2“î5—î:Uî?¹îAžîBô ïFàîâî¨îîÞî!î%Sî*î0? î6[î8'î=öî?TîBîDîI@ïDîâîpîˆ î çî#Uî'ßî*!î.•î5Ÿî7;î8G î@#îEïA]îâîAîá ï=Èî¤îNîî|î Ëî"ƒî'�î)àî-“î/K î5íî7¥ î>áîAkîCZîG¨ï;îâî�îÓîéîî!S î)Cî.Õî1°î6› î=ƒî@ îHBï8Eîâî”îÛîîwî!þî(lî*hî-nî1qî7 î9ïî<îAîBÿîH�ï5ƒîâ îCîÿî\î"aî#ñî&^î)fî-Uî/à î7Ëî9rî>îî@ÀîC› ï2ÁîâînîÑî�îrî!ÿî(˜î.Tî1,î3Jî9îüîB"îFGï0îâîÓî(î€î™î"Üî$fî&îî*î/’î2g î:~î=SvîA~ï0rï0îCîEãï->îâvîäï->rï->î¼zï*6î¤îªîî]îîo ï*6î0î2î3`î4¹ î=~î>Ørï&¡î¤î�îêî î!¶î&Uî(·î,oî.* î4Ðî6Œ î=Ëî?’îBcîDÅï#ßîâî‚îîî3 î#jî(O î0Îî5hî;…î>´ îE¹îG‘ï!îâî‹îàîZî î"ç î)ºî*þî0’î37î4¼î9µî=»î?ƒîAŽîEëîGÉï\îâîcîÂî_î ÷î"Jî#fî) î1Åî7î86î:³î¥vîDï\rï\îDéîE·ï›îâîÏ î…îcî, î&³vî*Èï›rï›î,7î-øî1Ëî6-î9ß îBUîF€îIÅïÙîâîê îîÒî$Nî&Uî'×î-ë î5>î8±î<’îA|îF}îH�ïîâ îî†îñî!ëî'›î,ýî/î30 î:mî@ÍîE2ïVîâîtîGïVïVî–îîîÂî î$rî&ƒïVïV@TVm$<CHAPTER3:OPTIMIZATIONANDTHEPROBLEMSITCAUSESFORDEBUGGING613.2.4AllowingthedebuggertomodifyvaluesofvariablesAdditionalcomplicationsariseifthedebuggerallowsthevaluesofvariablestobemodified.Recallthataroll-backvariableisonewhoseassignmenthasbeenperformedearly,andaroll-forwardvariableisonewhoseassignmenthasbeendelayed.Ifavalueisassignedtoaroll-backvariablefromthedebugger,thenthevariablewillfailtotakeonthenewvalueattheappropriatespot.Ifavalueisassignedtoaroll-forwardvariablefromthedebugger,thevaluewilllaterbeoverwrittenwiththedelayedstore.Ininductionvariableelimination,usingthedebuggertoassignavaluetotheoriginalinductionvariablewillhavenoeffectonthederivedinductionvariable.Incommonsubexpressioneliminationandhoistedstores,assigningtoacomponentoftheexpressionfromthedebuggerwillnotaffectthecomputedresult(becauseithasalreadybeenperformed).Similarly,usingthedebuggertoassignavaluetoacomponentofanexpressionwhosecomputationisdelayedwillcauseadifferentvaluetobecomputed.Usingthedebuggertoassignavaluetoavariablewhosecurrentvalueisinaregister(orotherfastermemory)willhavenoeffect.Usingthedebuggertoassignavaluetoavariablethathasparticipatedinstorageoverlayingcanhaveverystrangeresults:thedesiredvariable'svalueisnotaltered,andsomeothervariable'svalueischanged.Ifthevariablebeingassignedfromthedebuggerhadaconstantvalueinthatareaoftheoriginalsource,itsvaluemayhavebeenpropagatedtootherstatementsviaconstantpropagation.Assigningavaluetoitfromthedebuggerwillhavenoeffect;thissituationisaspecialcaseofroll-backvariables,inwhichtheassignmentisperformedatcompiletime.Ifanyofthesevaluesislaterusedtoaffectcontrol-flow,evenodderresultsmaybeseen.Thesesituationscanbeevenworseiftheprogrammercomputesthenewvaluetobeassignedfromthedebuggerbyconstructingexpressionsthatusevariableswhosevaluesareincorrect.Asimilarproblemiscreatedwhenthevalueofavariablethatremainsconstantthroughouttheprogramcausesdifferentcodetobegenerated.Supposethatavariablehasaconstantvalueatcompile-time,implyingaparticularcontrol-flow.Thencodetoperformtestsmaybeskippedover,orworse,deleted.Theworstcaseoccurswhenadebuggingvariableissettofalseinthebeginningofaprogramandisusedthroughouttheprogramtocontroldebuggingoutput.Anoptimizingcompilerwouldtypicallyremoveallofthestatementsthatproducedebuggingoutputasunreachablecode;therefore,usingthedebuggertosetthedebuggingvariabletotruecannothavethedesiredeffect.Specialdebuggingroutinesforprintingorcheckingtheintegrityofdatastructuresmayalsoberemovedbythistransformation,andwillhencenotbeavailablefromtherïgî—tî•ïgïgî{rî¦ïgtïgîWrîŒïgtïgîŸ ïgî'Þî*érïgî-Ætî.˜ïgïgî/lrïgî4¨tî5-ïgrïgî6jtî7hïgïgî8;ïgî;œrïgî>Štî?©ïgïgî@bpïgîMÓyïaïîâîÏî¡îyî#sî%„î*äî/Úî1Ýrï]Ìî¤ îŒ î!Eî$�î%ÿî(mî.…î2Áî5/î9lî;4î@þîB»îDºï[ îâîóî™î›î9î!Hî"‹î%î) î/þî2Kî5î<î?³îBBîCC ïXIîâî#î™îNî‡ î#¢î&!î)ˆî/Žî1î2Nî6î7xî<ûî>´î?çîE¸ïU‡îâîFî¢îî"î î%²î(Zî*Àî,kî/aî1cî3Àî6ªî:Pî;æî>B îEžîIlïRÆîâîî¡îîrîî6 î$×î*î-`î/¶î6 î8cî<î>¤îA¿îC¦ ïPîâîîbî{î¹îŒî%¹î*ó î2‹î67î8šî>¦î@WîDgîE“îI@ïMCîâîHîYî‹î!Èî$zî'Èî)Õî-§î/´î2î7î=HîChîE>ïJ�îâ î© îâî!•î&Zî*�î0rî2î3Bî:fî<î>w îE,îH�ïGÀîâîöî­î-îî nî&çî*½î0cî1Äî4Eî9#î<‹ îDº ïDþîâîrî·î¦î;î -î!=î$Ìî&aî'qî.î0î1ô î8’î<¦ îD†îEØïB=îâîŸîgî¢îZî î!Öî#Ùî+Fî/Yî1Êî7æî9¦î=Äî?îB¼îD|îE¸ï?{îâîIîKî.îÒî¹î!î&3î(©î,�î0zî6™î9}î<üî?;îDTîH�ï<¹îâîöî¯îÆîúî®î!gî"›î'Üî*µî-5 î4Ìî6„î;A îAùîDŽîGßï9øîâî}î$îaî î$øî(€î)Éî,î0äî3yî6éî:f î@WîCÞîE(ï76îâîiîÍîîØî!Uî$Áî'%î-3î/ïî1î6‘î:@î;òî>ÅîAÃîC€îEåï4uîâîpî1îÁî«î×î" î))î*¾î.C î4ãî7î<\ îD¥ï1³îâî.îúîËîDîÍîOî#{î&Iî)²î+Ûî0Bî3î8Ãî:Rî;žî@<îCMîE(ï.òîâ îîÕîüît î$žî&#î-î.²î4î85î9Ïî<‰î>[îAýîFDîGÉï,0îâîîÌî˜ î²î"øî&ïî+?î.Bî03ï(šî¤îŸ î¸î=î 'î#gî'Lî(¦î*ÿ î2Ûî8ÿî;Xî>@îAãîC‹îEuï%ÙîâîIî¨î²î­ î$q î+­î.|î0ñî6«î:Ùî?îA[ ï"Cî¤îDîÝîuîõî#Òî'›î*î-Ìî/™î0×î6!î9î>BîCÅ ï�îâîNîéî/î áî$5î%ïî'ì î/,î4¾î7˜î8Ïî>î@“îAÉîGEïÀîâîŒ îGîî Z î&¡ î/bî3î6jî8*î=”î@µîCËîEÍïþîâîoîMî«î‘î!„î%Sî(\î,»î0‹î1Ïî8¤î=õî?{îA²îC|îFÆîH�ï=îâîpîJî–îGî! î"®î& î-Wî/Øî5‰î7Yî<.îC îH›ï{îâ îÌî˜î×î%lî*eî,fî./î0Ÿ î7jî:Hî?²îF|ïºîâîª î|îV î"°î&sî(íî/î0Øî3î5ˆî<\îA¬îCuîFrïøîâî3î�îpî,î"õî)¸î/î1Xî6¤î8rî>9î@¢îF&îGéï 6îâ î2îEî î î"ßî$éî'šî1Eî4 î6Åî:Ìî=Pî?OîEîH�ÿ ËTVm$OCHAPTER3:OPTIMIZATIONANDTHEPROBLEMSITCAUSESFORDEBUGGING62debugger.Thecompoundedeffectsofconstantpropagationorotherassumptionscanalsotriggerdifferentinstructionselectionduringcodegenerationorpeepholeoptimization.Ifavariable'svalueisknowntobe1,thenanincrementinstructionmaybeused.Obviouslytherealproblemhereisthatthevariable'svaluewasfrozenatcompile-time.Similarly,ifavariable'svalueisknownatcompile-timetofitinonebyte,thenthecompilerwillallocatestorageandgenerateinstructionsaccordingly,withdisastrousresultsifavaluesetfromthedebuggerexceedstheone-bytesizelimit.Thisbringsupthesubjectofruntimechecking.Checksmaybemovedoutsideofloopsorremovedaltogetherbasedonthestructureofthewrittenprogram.Alteringthevaluesofvariablesfromthedebuggermaywellinvalidatethoseassumptions,andtheprotectionofthechecksmaybesubverted.Itisdifficult(perhapsevenimpossible)todetectthesesecond-ordereffects.3.2.5EffectsofoptimizationonadvanceddebuggercapabilitiesThissectionconsiderstheeffectsofoptimizationonseveralmorecomplicateddebuggercapabilities:single-stepping,databreakpoints,andassertion-drivenbreakpoints.Italsoconsiderstheuseofadebuggerasaperformancemonitoringtool.3.2.5.1Single-steppingAmajorassumptionofsingle-steppingisthatthechangeinexecutionstate(andtheactionsperformed)betweentwodebuggeractivationsreflectthesemanticsoftheprogramstatementatthefirstactivation.Thechangeinexecutionstateincludesbothdatachangesandcontrol-flowchanges.Optimizationscaneasilyvoidthisassumption.Branchchainingorcombiningsimplesourcestatementsintopowerfulmachineinstructionscancausestatementstobeskippedduringsingle-stepping.Code-reorderingoptimizationscausecontrol-flow(i.e.,statementordering)anomaliesandproblemswithvaluesofothervariablesifasemanticmappingmethodischosen;theycausestatementsemanticsanomaliesandproblemswiththevaluesofspecifiedvariablesifasyntacticmappingmethodisused.Forfine-grainedstepping,inwhichcalledfunctionsarealsosingle-stepped,theorderofarrivalatfunctionapplicationsisanadditionalproblem.rïgî—tî•ïgïgî{rî¦ïgtïgîWrîŒïgtïgîŸ ïgî'Þî*érïgî-Ætî.˜ïgïgî/lrïgî4¨tî5-ïgrïgî6jtî7hïgïgî8;ïgî;œrïgî>Štî?©ïgïgî@bpïgîMÓrïb)îâîÉî¢ î ëî%;î&õî,e î4î5Ìî9l îA0îC¼îF‰ï_gîâî¶ î¿î!“î&2î)§ î0™î2‹î8¢ îAÓîCƒîDÛ ï\¦îâî–î î›îSîNîåî!î#î)‘ î0vî3ƒî5~î9ªî@@îBªîEjïYäîâîæî:îòî: î6î!Éî$^î(Šî* î3 î9(î:rî;… îA�îEîFhïW#îâîu îÀîiî3îÛî �î#ãî'î)]î/î1¸î6²î;_î>îC� ïTaîâ îîŠ îÑî$î%cî&}î*î,%î/}î1Íî7Çî<Ãî?îDµîGQïN î¤îÐîî6î©î"dî$0î)zî07î5î8*î:-î>ÆîC¢îEnîI*ïKIîâî† îçî½î ¸î# î(½î*jî,¾î1fî7¹î=î?dîC†îE3ïH‡îâî^îÒîïîî! î'iî+ î3Lî6î8Œ î?.î@üîCpîGêïEÆîâîÓ îúîrîÝî î%»î) î0Jî1øî6î9� îAËyï?üîâîÏîWîZ î#Îî&.î-Cî4= rï;Úî¤î îõî Aî"îî'‹î)’ î1Øî4,î9 î<ë îDåï9îâ î‰î Xî#m î+Kî.î8 î@‹îBîDñï6WîâîAî¶îoî™î¢îPîz î'~ î.šwï1aîâî0rï->î¤îAîH î–î `î)Öî+Rî.1î0¡î5Zî7î=^î@ îCáîFRï*}îâ îîqîî$ î*¿î.ëî1;î7bî9 î;]î@ÞîGîH�ï'»îâî£ î�îPîàî!wî'”î*®î/úî3î6 î;!î=Á îEjï$úîâ îîÖîëî"Oî%: î-èî2ïî8Éî:×îAðîFŸï"8îâ îîyîÌî%Ó î-µî0Âî4ú î<6î>gî@ÚîF~ïwîâî0î% î.î2N î:–î>*îDæïµîâî`î+îFî!tî%µî'‚î+4î1î2vî3³î9wî?EîDdîEãïóîâîøî³îîî"(î(™î+Vî1dî4…î6êî;î<ÜîBžîH^îIÅï2îâî‘îaî€î!î%?î'þ î/Éî5ºî7{î;�î?¨îEºîH"ïpîâî2î‘îFîÿî$Mî%æî+` î2öî4bî6R î<ɸTVm$ CHAPTER3:OPTIMIZATIONANDTHEPROBLEMSITCAUSESFORDEBUGGING633.2.5.2Assertion-drivenbreakpointsBynow,thereadermayhavebeguntosuspectthatsettinglocationbreakpointsanddisplayingthevaluesofvariablesareoverlyprimitiveoperationsfordebuggingoptimizedprograms,andthathigher-levelfacilitiessuchasassertion-drivenbreakpointsmightmapmorecleanlyfromtheunoptimizedprogram'sexecutiontotheoptimizedversion.Unfortunately,thisdoesnotappeartobethecase.Itiseasytoconstructexamplesinwhichtheunoptimizedversionofacomputationwillsatisfyanassertionthatwillneverbesatisfiedbytheoptimizedversionandviceversa.Theremayalsobedifficultieswiththeprogramlocationatwhichtheassertionissatisfied,withthevaluesofotherprogramvariableswhentheassertionissatisfied,andwiththenumberoftimesthattheassertionissatisfied.Inthefollowingexample,theoptimizerhasnoticedthatthevariablefinishedisalwayssettoTRUEbeforetheloopexit,socodemotionanddeadstoreeliminationcombinetosetfinishedtoTRUEdirectlyattheloopentrance.29count_0;29count_0;30finished_FALSE;30finished_TRUE;DODO31Read[char];31Read[char];32count_count+1;32count_count+1;33IFchar=BLANKTHEN33IFchar=BLANKTHEN34finished_TRUE;35EXIT;35EXIT;36word_Append[word,char];36word_Append[word,char];..--processword--processword..ENDLOOP;ENDLOOP;Supposetheuserrequestsabreakpointwhentheassertion(count=10)AND(finished=FALSE)holds,inordertoexaminewordslongerthantencharacters.Thisassertionwillbesatisfiedintheunoptimizedprogram,butnotintheoptimizedversion.Wenowturnourattentiontowhatpreviousresearchershavedonetosolvetheproblemsthatoptimizationcreatesfordebugging.rïgî—tî•ïgïgî{rî¦ïgtïgîWrîŒïgtïgîŸ ïgî'Þî*érïgî-Ætî.˜ïgïgî/lrïgî4¨tî5-ïgrïgî6jtî7hïgïgî8;ïgî;œrïgî>Štî?©ïgïgî@bpïgîMÓwïb&îâî0îD rï^î¤î¯îûîJî~î qî#§î'Åî)cî.î0Ûî50î:V îA»îDb ï[Bîâî:îaîîÆîî#8î) î/¿î1õî8§î? îEpîH ïX�îâ îÄ îî î" î,Y î4&î8tî;çî?ÑîDÐîH�ïU¿îâ îÓî6î#cî% î'aî-Äî3W î<“î?-îBUîDÁîI@ïRýîâîÞîHî)î«î"î1îêî$ßî*çî, î0¹î3$ î;(î?ûîA¿îBô ïP<îâîŠî´î îLî uî"¾ïP<ïP<î#}rïP<î&Rî(?î-‰î/€î1Üî8Dî=î?¼îB�îFìïMzîâîÓî�îk îî &î"sî'ïî-î.šî2•î4âî:î;Ø îAkîDsîFÀïJ¹îâî¥îOîèî­î#mî%×î+‘î- î2·î5yî8žî;î@?îBîE¶îH�ïG÷îâî’îþ ïDbî¤î�î î;î")î$¥î*ëî-}î2yî5dî7àvïDbî=jrîEïDbïDbîEdîFŠïA îâî6vïA î8rîoïA ïA î6îöîŒî!èî%#î'î*œî/‘î2î6î9§ îAîFìîHÑvï>ßîârîyï>ßï>ßîèvï>ßî{rî³ï>ßï>ßîzî!¨î#@î% î(Åzï;×î¤îªî¶îï;×î%áî'çî+ôî-Mï:/î¤îªî¼îï:/î%áî'çî-úî/Sï8ˆîªï8ˆî'çï6áî¤î ï6áî%áî)A ï59î¤îîîiîuîÏï59î%áî)Aî-Mî.§î2³î4 ï3’î¤îî îiîÂîÏï3’î%áî)Aî+Gî.§î0î4 ï1ëî¤î¶îÉî"ï0Cî¤î¶ï0Cî%áî+ôï.œî¤îîcî¼î)Aî, î-úï,õî°ï,õî)íï+Mî|ï+Mî îlzï+Mî)A|î+Gï+Mï+Mî+óî0ªzï)¦îcï)¦î)íï'ÿîï'ÿî)Arï$jî¤î)îˆî‚î!Úî# î)õî-ªî0 zï!aî¤î]î¶îiîî#Ûî%4rïÌîâîéî‘î?îçîZî#`î'žî*¾î- î4Sî7gî=î?¶îA îFçîH�ï îâ îÜîÂîCî!¸î#gî%Æî,2ïuî¤î(î%î#î¨î"iî$î'gî,ð î3ûî7;î:§îŠtî?©ïgïgî@bpïgîMÓsïa¸îâîîZî³î"<rï]–î¤î–îüîIîIî!jî&êî*Wî,Nî2ùî9Uî@%îEdîF‰ïZÕîâîë îÛî7î! î'‡î)Åî-Ñî/hî5î7î=hîCYîEïïXîâî™ îÂîÀî$Éî'î-ryïRIîâîÏî:î5î!´î,’rïN'î¤îœî î#°î(Žî,óî/Àî1Ñ î:, îBà ïKeîâîAîbî"î#×î'?tî-×ïKeïKeî.& rî4@ïKeïKeî5ä î?¬îCîGôîIÅïH¤îâîðîïî§îøî!|î& î/óî67î8yî9é îCGîE“îGïEâîâînî/ îûî#4î%�î0 î8åî<@ îC/îH±ïC!îâî( î‰ î#Aî&Ý î/Vî33î6k î?=î@Ò îG[ï@_îâîùîEîî$ˆî*ªî-qî//î1.î5èî8Ïî<0î@ºîCuîI@ï=žîâî½î†îýîÒî(à î0î2 î5c î>)îBtîDðï:ÜîâîçîîTî ªî&åî)Aî,™î.Cî2L î:Åî=yîB­îEï8îâîdî› î»î Šî#%î&õî+î.]î2,î5£î7Vî=�îB îIï5Yîâî´îî‘îÚ î(rî,Yî1Fî4{îA8 îI*ï2—îâîæîàî2î¯î  î'”î)œî,vî0Ýî3uî7î=BîAFîEãï/Öîâî�î%î!n î*!î,× î4­î8Úî<î?zîEîF´ï-îâîIîõîÊîyîØï)î¤îûîÌîÇî$î&0î-•î/>î3î7Xî9‘ îBåîFÌï&½îâ î¢î”î¶ î%9î'*î+†î/ î8)î:î=Lî?=î@ªîFÕîI5ï#üîâîÀ îZî#“ î+… î27î5î;Ïî@!îAÿ îH7ï!:îâîìîÍî lî#Jî%Úî'mî*l î1ó î:>î@ îD‚ïyîâîîrî¼î"Ïî$Eî'î)C î0S î7…î9hî<åî>½ îEïîI@ï·îâî.îöîÆî!êî(Žî*–î/Øî5ãî7žî>cîDÛïöîâî“îGîî“ î"%î#úî'; î/éî4î6�î<°î@äîE9îFhï4îâîv î)îñî!>î"ô î*Èî/aî2nî3øî5Äî<±îA?îD5 ïrîâî£î\îîÉî î#6î(lî*î-5î1„ î8”î:cî=îAhîFÀï±îâîAîkî™îî"^î&Ú ï î¤îrî»î»î"ÿî$¤î)¦î/Yî5î8î9µî;‡ îAÿîC¤îIVï Zîâ îÖî†îëî$î(¼î,4î.šî4©î8Ýî<* îD£ ÎTVm$kCHAPTER3:OPTIMIZATIONANDTHEPROBLEMSITCAUSESFORDEBUGGING65areferencetoavariableintoanaccessofitscurrentstoragelocation(s).Forotheruserinteractions,thedebuggerwouldhaveprovidedonlysemi-truthfulbehavior.Thedebuggerusedonlyasyntacticstatementmapping,sothatexecutionwouldappeartoprogressintheexpectedwaythroughthesourceprogramratherthanjumpingaboutrandomly[seeSection3.2.2.3].Tohandlecode-reorderingoptimizations,thecompilerwouldhaverecordedthemovementofvariableassignmentsanduses(bynumberonly)thatcouldaffectorbeaffectedbythevaluesofvariablesatagivensourcestatement.Whentheuseraskedtodisplayormodifythevalueofanaffectedvariable,thedebuggerwouldhavelistedallrelevantassignmentsandusesthattheoptimizerhadinsertedordeleted.Thistechniquewasastepintherightdirection,butitwashamperedbythedebugger'ssoleuseofthesyntacticstatementmapping,aswellassomeskimpinessandinefficiencyinitspre-computedtables.Noattemptwasmadetoreconstructvariablevalues.Furthermore,theFDSsystemmadenoprovisionfordescribingthestateofacomputationthatwassuspendedbetweenstatementboundaries(forexample,duetoaprogramexception),eitherinstatementmappingorinvariablestoragemapping.Optimizationsthatcreateone-to-manyand/ormany-to-onecorrespondencesfromsourcestatementstoobjectcodelocations,suchasinlineprocedureexpansionandcross-jumping,wouldnothavebeenhandledwelleither.Unfortunately,theFDSdebuggerprojectlastedonlylongenoughtoproduceadesigndocument,sonoinformationisavailableregardingitsperformanceoritseffectiveness[Warren82].3.3.2Hennessy:displayingexpectedvaluesofvariablesHennessyconsideredamorerestrictedproblem:providingthemostcriticaldebuggingfeatures(displayingvariablevalues,settingbreakpoints,andreportingerrorlocations)inthepresenceofsomeselectedlocalandglobaloptimizations[Hennessy79].Thelocaloptimizationsincludecommonsubexpressionelimination,redundantstoreelimination,andcodereordering.Theglobaloptimizationsincludecodemotion,inductionvariableelimination,anddeadstoreelimination.Theseoptimizationsaresufficienttocauselargedifferencesincodeorderingbetweenthesourcetextandtheoptimizedobjectcode.Becauseofthemorecomplexproblemsassociatedwithmodifyingthevaluesofvariablesfromthedebugger,Hennessydisallowedthatfeature.Ratherthanpre-computingavarietyoftablesthatmightbeusefulatruntime,astheFDSsystemdid,Hennessyassumedthatthecompilerwouldrecordtheaugmentedglobalflowgraphusedduringtheoptimizationprocessandthedebuggerwouldprocesstheflowgraphasneeded.rïgî—tî•ïgïgî{rî¦ïgtïgîWrîŒïgtïgîŸ ïgî'Þî*érïgî-Ætî.˜ïgïgî/lrïgî4¨tî5-ïgrïgî6jtî7hïgïgî8;ïgî;œrïgî>Štî?©ïgïgî@bpïgîMÓrïb!îâîôîÚîpî‚î¡î bî":î&0î'Ñî)”î.Fî2à î:;î<Îî@VîC7 ï__îâî%îî$îNî$î' î/,î5€î8<î>(îAHîDEîESï\žîâî)îNî#î î&Iî*ˆî/ î0àî6_î8î:�î@]îCFîH�ïYÜîâî2îÀîÎîôî%nî)Ptî/„ïYÜïYÜî/Óî1°î5–rî8ëïYÜïYÜî:LîuîCÕîEÂïLîâî îoî(î_îQî! î#yî&Ù î-î/”î0÷î3±î:6î¬ îEŸîHyïISîâî…îÏîTîtî$rî& î(áî*yî-÷ î4Ðî7r î>ºî@RîB ïF‘îâîªî îîÄî!„î#2 î*Eî/{î4… î=î?aîB³îG.ïCÐîâî!îbîØ î ©î#Aî&«î(�î)ÿ î23î5:î8î?îD¹ïAîâ îöî®î�î!:î"ëî$î)§ î0¯î4žî6Mî<…îBBîDîE¸ï>LîâîÎîÚ î#éî&ñî+. î3wî8X î@¡ï;‹îâîÊîš îÕî!î%žî)e î/úî3¬î5Ûî:<îA@îH7ï8Éîâ îî>î³î!úî%Wî*¤î-’ï53î¤ î@îøî!¢î(î,ùî1>î4°î8"î=eî?lîEîFŸï2rîâî§îkîq î ûî"gî("î.Kî0& î8*î9îî;È tîCÁï2rï2rîDrîIï2rï2ryï,§îâîÏîÄ î"jî)<î.2î05rï(„î¤îÄ î•î©î#( î)î.úî5$î7oî:¶î?îEÂï%Ãîâ îîWîùî$z î,cî/7î5Pî8Þ î?.î@øîCtîI5ï#îâîrîœîßî”î!´ tî*.ï#ï#î*} rî0tï#ï#î1Ïî4¤î7è î@bîE>ï @îâ î: î ]î'�î+z î3œî6áî:¶ îCfîFÌï~îâ î›î·î 9î%‹î+òî1d î95î<(î?ÂîCZ ï½îâîô î‚îå î#ôî%³î)xî,ð î3ûî5ºî9î>°îD/îFŸïûîâîÛîÔîuî"î"}î'"î,¦î.¡î1Aî5î:ÜîA& îGÓï9îâîyîÙîîÀî#{î&âî)Aî/¢î5Ø î<œî?jï¤î¤îRî” î"õî$:î(Üî*±î.¹î1£î5·î7Ãî;÷î=¬îCWîE!îGœïâîâî}îkîÁî"pî%_î'Þî-ºî2î6xî8÷î@*îDlï !îâî9îÅî@ î!Tî&Cî)î+�î1´î5þî:íî=gîDîEÎÿ lTVm$ÓCHAPTER3:OPTIMIZATIONANDTHEPROBLEMSITCAUSESFORDEBUGGING66Eachnodeoftheaugmentedflowgraphwasadirectedacyclicgraph,representingonebasicblockofboththeunoptimizedandtheoptimizedprograms.Hennessydevelopedalgorithmsforprocessingtheflowgraphatruntimethatcanusuallydetectwhenavariable'svalueisincorrectintermsofthesourceprogram.Furthermore,hisalgorithmscansometimescorrectsuchvaluestodisplaytheexpectedvalue.Hedidnotdirectlyaddresstheproblemoffindingthecorrectstoragelocationforavariable'scurrentvalue.IncontrasttotheFDSsystem,Hennessyusedonlyasemanticstatementmapping.Asaresult,theusercouldsetabreakpointtoviewtheoldvalueofavariablebeforeanassignmentwithoutanyconcernabouttheeffectsofoptimizations.Also,whenreportingthelocationofasynchronousprogramexception,thesemanticmappingindicatesthestatementresponsiblefortheexception.However,theuseofthesemanticmappingrestrictedbreakpointplacementforsomecommonsubexpressionevaluations:whenthestartofmultiplesourcestatementscorrespondedtothesameobjectcode,abreakpointwaspermittedonlyonthelexicallyfirstsuchstatement.Hennessy'salgorithmswereimplementedandtestedonasmallgroupofprogramstodemonstratetheircorrectnessandfeasibility,buttheyhavenotyetbeenincorporatedintoanyprogramdevelopmentsystem.3.3.3TeepleandAnderson:statementmappingforcross-jumpingInanunpublishedmanuscript,TeepleandAndersonbrieflydiscussedanevenmorerestrictedproblem:howtosetbreakpointsinthepresenceofthecross-jumpingoptimization[Teeple+80].AsdescribedinSection3.2.2.2,thisoptimizationmergesidenticaltailsofjoiningcodepaths,therebycausingoneobjectcodeinstructiontocorrespondtomultiplesourcestatements.Atabreakpointinthecommoncode,thedebuggerneedshelptodeterminewhichsourcestatementisexecuting.TeepleandAndersonsketchedanalgorithmtoidentify"disambiguatorpoints"foroneofthetwopathstoeachmergedregionduringtheapplicationofcross-jumping.Theyalsonotedflowgraphconditionsunderwhichnodisambiguatorpointsexist.Finally,theysuggestedawaythatthedebuggercouldusethedisambiguatorpointsatruntimetodeterminewhichstatementisreallyexecuting.Theirschemewasbasedupontracingandbreakpointsthatareinvisibletotheuser.Iftherewerenodisambiguatorpoints,thedebuggerwouldreplywithalistofthepossibilities.ThisworkprovidedtheinitialideaforthewaythatNavigatorhandlescross-jumping,whichisexplainedinthesecondpartofthisdissertation.Sincetheirtechniquewasneverfullydesignedorrïgî—tî•ïgïgî{rî¦ïgtïgîWrîŒïgtïgîŸ ïgî'Þî*érïgî-Ætî.˜ïgïgî/lrïgî4¨tî5-ïgrïgî6jtî7hïgïgî8;ïgî;œrïgî>Štî?©ïgïgî@bpïgîMÓrïb)îâîSîÅî|îÚî ëî'kî*î+=î0Šî4ùî9< îAîC½îG.ï_gîâîpî�îµ î„î î"Eî(…î/î5(î;– îB.îD@ ï\¦îâîVîíîšîæî!Éî$iî)0î-Tî1î2\ î8„îîB?îCåîH�ïW#îâî’îÿî<î¥î î$÷î)Ôî,'î1Ÿî3Lî8î:[î>áîC‡îH±ïTaîâî îîèïPËî¤î¡îûî×îdî äî%åî,Hî/²î2úî4Qî:0î@“îG†îIÅïN îâî îšî¯î•îÌî  î'î(æî,;î.¶î1:î4ÿî6Òî8î=hîAÒîCÝ ïKHîâîîÎîî î"›î' î(ä î2|î6$î9øî@îB•îGìîIÅïH‡îâ îÓîe î"õî%Xî+ î0Êî6~î8áî? îFOîH�ïEÅîâ îîhîÝî!gî#5î%ªî+pî1A î7U î>[îE îG[ïCîâîš îm î%î(Óî+:î.Rî0î5•î9í î@¯ îI@ï@BîâîAî¿îØîwî  î$‘î'=î-ˆî0¢î2¨î5î:_î=7î@i ï<¬î¤ î î Hî$ î,¹î/Øî47î6¥î86î<<î@¥îBÅîI@ï9ëîâ îÚîK î!|î$^ î+ î-Ìî1î4wî7î9Šî= îEKîHNï7)îâîq î¡yï1_îâîÏî1îWî#%î*°î1@î3â rï-;î¤îgîL î$ î$Žî) î+´î1òî6Lî.îAhîDð ï*zîâîÚîÙîƒîš î# î$³î' î,®î.bî0¼ î9Œ tîA€ï*zï*zîAÏ rîGˆï*zï*zîHÝï'¸îâîîÆîªî Tî"û î*ùî/±î5Fî8/î9íî>™îAåîEîï$÷îâîÒîƒî¡îî î$Îî&‚ î-¥î/Xî4Øî9- î@ÎîBÎîCþ ï"5îâî›îîÀîkîÕî$éî(Õî+ûî-µî4Bî8[î<µîBöîDl ïtîâîdîî\î!þî#êî*%î+Ïî0à î:ƒî?SîAŒîD3îEçîHBï²îâî’îEî{îuî ½î%3î'— î.®î0l î:'î=µî@†îDlïñîâ î¶îêî)î ` î)ˆî-Üî2Jî7…î:ÆîA,îB‡îE�îH�ï/îâîîþî—î î'4î+{î-8î2’î4dî; î?<îE•îG$ïmîâ îÚî“îkî!î$êî(wî-î/² î7 î9çî<4îA¥îCMîE¥îIlï¬îâîfî²î³ î ¤î%î'uî-yî1¢î5%î8:î9_î;—î=Kî?¥ îGÔïêîâîJîîRî)î!î#7î%‚î(Eî*ÿî1Nî6E î?^îCWîD®ï )îâîîî¬îœîÞîõî õ î)Öî-êî1�î8Dî;Nî?wîCîI*ÿ $TVm$ÅCHAPTER3:OPTIMIZATIONANDTHEPROBLEMSITCAUSESFORDEBUGGING67implemented[Teeple81],itsdescriptionisincomplete.Amongotherthings,theydidnotrealizethatmerginglessthananentirestatementstillrequirespathdetermination,andtheydidnotdiscoverthatrepeatedcross-jumpingcancausenesteddeterminers.3.3.4Feiler:localrecompilation,optimization,anddebuggingAsintheFDSsystemdescribedearlier,Feileralsosuggestedthatdebuggingforoptimizedprogramsshouldbeprovidedbyusingmultiplelevelsofoptimization[Feiler82].Foreachprocedureormodule,theuserwouldselectoneoffouroptimizationlevels.Themoreoptimizedaregionoftheprogram,thelessdebuggingsupportitwouldreceive.WhiletheFDSenvironmentisreasonablyconventional,Feiler'senvironment,calledLOIPE,hassomenovelfeatures:itaddsdebugstatementstothesourcelanguageandisbasedentirelyuponincrementalcompilation.Thedebuggerhasnospecialaccesstothecompiledobjectcode.LOIPEisaninteractiveprogrammingenvironmentforincrementalprogramconstructionbasedoncompilation.Itprovidesauniformviewofallsystemactionsthroughasyntax-directededitortheuserneverseesthetraditionaledit-compile-execute-debugcycle.Theusermakesadebuggingrequestbyeditingadebugstatement,suchasBREAKorTRACE,intothesourceprogram.Inresponse,thesystemautomaticallyrecompilesandrelinksthatportionoftheprogramandthenresumesprogramexecution.Similarly,theusercanmodifytheexecutingprogramtoinsertnewdeclarationsorarbitraryprogramstatements.Themodifiedprogramcanberesumedfromthepointofsuspensionaslongasnoactiveprocedurehasbeenchangedinasemantically-inconsistentway.Whenthisfails,theprocedurecallchaincansometimesbeunwoundtotheearliestcallofamodifiedprocedure.Otherwise,theprogrammustberestartedfromthebeginning.Notethattheabilitytoresumeexecutionafterinsertingadebugstatementandrecompilingtheenclosingprocedureiscentraltothisdebuggingapproach.Thesystemdoesnotpermituserinterrupts.Procedurescompiledwithoutoptimizationwouldhavefulldebuggingsupportforprogrammodificationandresumption,asdescribedabove.Programexecutioncanalwaysberesumedafterdebugstatementsareaddedorremoved.Incontrast,anoptimizedprocedurewouldreceiverestricteddebuggingsupport.Noattemptwouldbemadetouseinformationcollectedbytheoptimizertohidetheeffectsoftheoptimizationsortopresentalternatives.Nevertheless,Feilerclaimsthatthedebuggerwouldprovidealimitedformoftruthfulbehavior:itwouldonlyreportvariablevaluesandcurrentexecutionlocationsthatrïgî—tî•ïgïgî{rî¦ïgtïgîWrîŒïgtïgîŸ ïgî'Þî*érïgî-Ætî.˜ïgïgî/lrïgî4¨tî5-ïgrïgî6jtî7hïgïgî8;ïgî;œrïgî>Štî?©ïgïgî@bpïgîMÓrïb)îâ tî,ïb)ïb)î{rîïb)ïb)îîîÀ î%Êî'. î/ î3ìî7„î;ìî>ôîAbîCÏîH ï_gîâîNîíîîî î&Kî(õî.Lî1| î:´î=tî@ŽîC îE‹ï\¦îâî°îK î !î"¬î&bî*± yïVÜîâîÏîî î&Ü î0ºî3àrïR¹î¤îÐî™îî‚î î&^î+î/2î2î8kî;UîB*îD‚ïO÷îâîàîGî#î àî"Çî&\î+Áî/wî1 tî8ÿïO÷ïO÷î9Nrî=‚ïO÷ïO÷î>¹îAOîDkïM6îâî îóîMîAîjî#%î%Ëî'î*} î2qî7 î9ßî=lîCÓîD÷îI5ïJtîâîîáîîŽî"$î' î(>î,Iî1„î5xî7´î:â îBÍîD ïG³îâ î2îí î$1î(î,øî/Jî2»î6Xî;Ûî=î@(îD4 ïDñîâî‘îòîBî îÁî!.î%î*î-¦ î5' î=�î@hîFrîHèïB0îâî^îkîîyî!wî%�ï>šî¤îDî”îh îú î(q î0cî2… î9èî?[ îG ï;Øîâî5 î5îùî!Õî#Kî(ðî,xî.}î0ºî5‚î:lî?ðîAgï9îâ îDîaîPî Lî"Ï î)–î:¸î?OîBKîEhîIÅï6Uîâî…îBî'î ­î!Àî%Ø î,Oî/itî1ï6Uï6Uî1ºrï6Uî5ntî7ï6Uï6Uî7Õrî;ï6Uï6Uî;Æî>‡î@ÏîEï3”îâî«î¢îûîp î%Ý î,¼î/mî3âî6ªî;‚î=5î?ŽîEîGÈï0Òîâî=îÛ î! î'Kî)¹î,Áî/Zî4&î6”î<ÍîBjîD'îHï.îâ îœî„îMî$ î+Ýî.Úî4Úî:�î=<î?PîEîH�ï+Oîâîxî( îî³îÄî!hî#eî'Iî-Âî0.î3�î8çî:Œî;¬ï(Žîâî�î¡î>î€îÜî%Zî'áî+’î.î4Îî6ºî<Õî>€î@ÛîE‰îHîIÅï%Ìîâî³ îû î"Êî%î*¢î-ÿî/äî5î8Ûî;/ îB`îEÌîH�ï# îâîqîuî“î!î$¯î*ªî,)î0®î79î:F îB1îDæï IîâîeîÑîWîî§î&aî-;î0î4�î7¿î:4î>¥îAž ï³î¤ îßîî$= î,`î0¹î4)î6Þî=ÂîBøîE`ïòîâ îÝî‹ î!î"½î(ßî-ªî3;î9gî;éî@EîB,îG³ï0îâî îËîî Cî"ï›î¤îwîîõî!eî'ìî,î0Ë î6Íî=‹îC{îEâïÙîâîóîÇîjîüîT î#Áî)`î+?î-�î3Žî5î8î:`î>“î@/îBq ïîâî³îoîP î„ î'ýî, î0Rî3-î5šî;±î?ìîEîF<ï Vîâî<îçîòîî Wî$xî'„î+šî0Ãî4äî7ŽîŠtî?©ïgïgî@bpïgîMÓrïb)îâîŠî˜î tî ƒïb)ïb)î Òî"¾î%bî'pî+×î.Xî0Uî5@î8°î=üîAQîDVîF[îH¹ï_gîârï_gî­î^î4îSî$î(Fî-î1Gî3 î6î7Íî=5î?ÅîA» îH7ï\¦îâî‚îŒîî âî%î'Ïî*î/Ñî6éî:î>¾îC-îEâïYäîâîîËînî à î(y î0àî2*î4s î<>î@`îBê ïW#îâî†îlîOî°î#) î)¬î.4î/îî6î:& îA§îDkïTaîâî&î- îkî!Œ î*xî-Eî/»î6Sî8ôî<ÀîAîC îI@ïQ îâî‹ îÉî0î�î#ô ïN î¤î­ îŠ î$hî(î,)î1Zî3žî8wî<«î>–îE4 ïKIîâîàî î‹î+î!Žî'¹î+êî.bî2î4± î<­î>^îAÈîDkïH‡îâîzîJî† î°î ¸î']î,Íî0xî2äî9î=Uî?ÖîC¯îFÀïEÆîâî¢îî4î Èî#éî%¾î)ÿ î1¸î3Úî5î9Jî=Šî?TîE!îHþïCîâîþî9î'î î$î%«î&Ò î.™î4Ëî7jî:­î=Ûî@NîE5îG’ï@Cîâî›îWî…î *î#‘î29 ï<­î¤îìîšî1 î¨ î% î)dî-Pî/¥î5Û î?®îA]îFîHyï9ìîâîÁî¬î¸îõî&®î-sï3Oîâîrï/,î¤îªî‚îäî"î#'î' î*Âî,hî2Qî3÷î7@î8Úî<ÕîBq ï,kîâîwî6îi îŒî$Ÿî&Wî+£î-Zî2î4€î:Fî<Úî@)îB’ ï)©îâîüîçîaîÙî ¨î&|î(Þî.oî1ïî3øî:´îA"îHï&èîâîòîÝî£î!w î(Rî*�î0®î6ãî<ìõTVm$| ÿMATHþæ ÿGACHAþæ ÿ TIMESROMANþæ ÿGACHAþæ ÿ TIMESROMANþYÿMATHþÿ TIMESROMANþŸÿGACHAþŸÿ TIMESROMANþŸÿ TIMESROMANþæÿ TIMESROMANþÿ TIMESROMANþŸÿ TIMESROMANý…ÿ HELVETICAþŸb ¯ «G#È+ô3Ó: IC 'L iUJ] Õg õp#wD Ȉ â‘ Œš#¡ Ê«²̹-Á vÊ ¨Ó šÜˆâj/åãœÇOÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿ []<>NewChap3Monday, May 7, 1984 8:41 pm PDT