1Chapter1IntroductionComputerprogramsrarelyperformtheirintendedfunctionthefirsttimetheyarepresentedtothecomputer.Asignificantfractionofaprogram'sdevelopmenttimeisnormallyspentdebuggingit.Conventionalinteractivesource-leveldebuggersareinadequatefordebuggingoptimizedprogramsbecausetheeffectsofoptimizationsdisturbthecorrespondencebetweentheprogram'ssourcetextanditsobjectcode.Nevertheless,theabilitytoapplyaninteractivesource-leveldebuggertoanoptimizedprogramisimportant.Interactivesource-leveldebuggersallowforamarkedincreaseinprogrammerproductivity[Evans+66],andcompilersthatperformoptimizationsarebecomingincreasinglycommon.Somereasonsforthetrendtowardoptimizingcompilersaretheemphasisonportabilityandmodularityincurrentcompilerconstructionpractices,theincreasedspeedandreliabilityofoptimizingtransformations,andthecontinuingneedforefficientuseofacomputer'stimeandspaceresources[Harrison81].Thisdissertationdemonstratesthateffectiveinteractivesource-leveldebuggingcanbeprovidedforoptimizedprograms.Itinvestigatesthepreviouslyunstudiedinteractionsbetweenoptimizingtransformationsanddebuggingcapabilities,identifiesgeneraltechniquesthatcanbeusedtosolvetheseproblems,anddemonstratesthepracticalityofthesetechniquesbyimplementingselectedonesinaprototypedebuggingsystemcalledNavigator.pïg/îNšqïVÑî'Aî0ÍïP4î%ï rïI–î¤îDîkî"jî'Õî+/î0ÿî6Œî8ÿî;ëî?$îBGîD®ïFÕîâîÝî‰î)î î#èî)Jî+Pî,Çî3 î;üî?nîA'îGDïDîâîœï@~î¤ îŠ î!¡ î)•î0Œî3H î:¹î=`îD‚ï=¼îâî î?î²î!î"ã î+tî0<î2° î<�îBîDƒï:ûîâîsîlîdî€îÚî$ î-+î/Ìî4Fî66î:Bî î'–î* î0·î7( î>—îD ï!Yîâî«îcî" î)” î/‡î4[ î;8î>î@”îB…îEÂîGqï˜îâî’îîø î$qî&÷ î.&î0î3¶ î:¹î<Û îEÂïÖîâîîÀîêî*î!äî&_î*V ÿTVm$ÆCHAPTER1:INTRODUCTION21.1DebuggingandoptimizationsAdebuggerisatoolthathelpsaprogrammerexamine,monitor,andpossiblymodifytheexecutionofaprogram,usuallyforthepurposeofisolatingandcorrectingmistakesintheprogram[Johnson82a].Inaninteractivedebugger,theuserperformstheseoperationsduringtheprogram'sexecution,sothattheresponsetoacommandcanguidetheformulationoflatercommands.Inasource-leveldebugger,theuserreferstofeaturesandeventsoftheprogram'sexecutioninthefamiliartermsofthesourceprogram.Theuserneednotbeawareofpiecesoflow-levelmachinestatethatdonotappearinthesourceprogram(suchasregisters,conditioncodes,andnumericcodeanddataaddresses).Typicaldebuggerfeaturesincludereportingthecurrentexecutionlocation,displayingormodifyingthevaluesofvariables,executingnewstatementsinthecurrentcontextoftheprogram,andsettingandremovingbreakpoints.Breakpointsarelocationsinaprogramatwhichtheexecutionoftheprogramwillbesuspendedanddebuggercommandswillbeperformed.Breakpointandprogramexceptionlocationsarespecifiedaspositionsinthesourcetext.Theprogrammerreferstovariablesbytheirnames;thedebuggerdisplaystheirvaluesinappropriateformatsfortheirdeclaredtypes.Thisdissertationconsiderssource-leveldebuggersforhigh-levellanguagessuchasAlgol,ratherthandebuggersforlow-levelassemblyormachinelanguages.Source-leveldebuggersforhigh-levellanguagesaresometimescalledhigh-leveldebuggers.Thisdissertationusestheterm"source-level"becausetheterm"high-level"isalsousedtorefertodebuggingatahigherconceptuallevel,closertotheproblemspecificationlevelthantheprogramimplementationlevel[Gramlich83,Hamlet83].Inparticular,thisdissertationconcentratesondebuggersforAlgol-likelanguages,suchasAlgol,Pascal,andAda.Theselanguagesareblock-structured,permitrecursiveprocedures,andhaveafairlyrichtypestructureincludingpointersandrecords.FORTRANandBASICcanbeconsideredmembersofthisfamily,butaresimplerinseveralways.ExamplesoflanguagesoutsidethefamilyofAlgol-likelanguagesincludeLISP,APL,andSNOBOL.Someoftheconceptsdiscussedherewouldalsoapplytosuchlanguages.Programoptimizationsaretransformationsthatareappliedtoaprogramtodecreaseitsexecutiontimeand/orspaceconsumption.Typicallythecompileritselfperformstheoptimizations,butsometimestheyareperformedbyapre-orpost-compilationprocessor.Anoptimizedprogramexhibitsthesameinput/outputbehaviorasitsunoptimizedcounterpartbutisfasterorsmallerorboth.However,basicchangestothealgorithmimplementedbyaprogram,suchasreplacinganrïgî&sî'ïgïgî'þrî,)ïgsïgî,Ùrî.ïgsïgî.’ pïgîNštïa¸îâîîšîG rï]•î¤îZîŽî#îwînî"gî&0î'„ î/�î5‹î;Oî>1îC§îH�ïZÔîâîî­îÆî›î"=î$iî&·î+èî-�î2÷î5œ î;÷îAuîCîE`sïXîâ rîïXïXî—îzî î!Bî'¸î*,î-:î3*î6È î=ŠîBîDƒïUQîâ îmî.îúîWî!úî#¦î$Íî+,î-´î1}î3Ú î;bî=î@<îGøîIÅïR�îâ î˜î%î°î"Ôî&Õî(¯î.î0êî5Nî73î9¾î@UîFµîH�ïOÎîâîîÈîîÜî *î&�î)fî,]î/·î2*î4î8 î9Äî=Úî?‘îEjïM îâî0îî>îÐîsî >î"ºî'&î,Òî0™î2d î8;î>wîB·îE‹ïJKîâîoîlî· î «î%Ûî,*î1œî6Áî=î?ªîD¹ïG‰îâî| îîäî#†î%ñî**î+î î2 î8Bî;< îBîCºîF%ïDÇîâîåîÌîZîpî!Vî%êî(Ðî/ uïDÇî7É rïDÇî?|îAþîGèîIÅïBîâî‚î,îKî¼î#î$Íî'>î,Þî/›î1�î8iî;2îALîHCï?DîâîÆ îN îRî!ýî'€î-©î3Xî5Ÿî;Nî<ðîBªîDLîFŸï<ƒîâî±î§ î§î!šî#fî)>î+Xî.¼î3—î6î<;îA�îDõîI@ï9Áîâ îAîAî~î Åî&Jï6+î¤î¤ îÓî!· î)(î/œî1À î8î>7îAOîBäîFáï3jîâîóîjî’î Xî&î'Íî-< î47 î;îîBfîDŽ ï0¨îâîîaî uî!òï0¨ï0¨î"¯rï0¨î( î/Nî2Y î9’î<|î>ÌîB ï-çîâîöîHî� î!5î"“î%Qî(€î* î-dî/î5°î7;î8Wî<™ îCrîGï+%îâî�îêîk î Lî#�î&²î)î.š î8vsî;¹ï+%ï+%î< îBUrîGDï+%ï+%îIï(dîâ îOîÐ îø î&°î(–î/î1 î7] î=ßî@ðîB}îFsï%¢îâî‰î=î.îhî!¬î,,î0�î6N î=�î@DîCzîD“îH!ï"áîâîßî‰î‹î"Åî%jî*ôî2„î5)î9Óî) îDüï îâîÓî¬îî8îÃî"äî$Éî)’î.9î4°î6 î="îB#îDºîI5ï]îâ îpîéî ÷î%î(Óî+¹î3Wî7[î9Cî;ÑîAœîGÔïœîâîîÝî¨îVîˆ ïî¤îŠ î Sî"ôî-î0#î2Ãî7ûî9öî;lîAGîCCîIïEîâîýîî•î 0 î)î.êî1/î6Ðî:î?ÔîB ïƒîâîSîûîûî>î#òî%Ýî&÷î)Õî+‰î5ò î<Áî?îE`ïÁîâîîkîì î"9î'íî)Ÿî+} î3{ î:ßî=cî>ÓîB—îD_îI*ï îâîîSîÒî" î#Äî&/î,{ î4Øî6àî8î>îAFîBÿîHþÿ gTVm$²CHAPTER1:INTRODUCTION3O(n2)algorithmbyanO(n)algorithm,areconsideredtobeoutsidetherealmofprogramoptimization.Thestudyofsuchbasicchangesiscalledautomaticprogramming[Green+79].Programoptimizationshouldbecalledprogram"improvement",becausetheresultingprogramisseldomoptimalinanysense;nevertheless,"optimization"istheacceptedterminthecompilerliterature.Optimizationscanbeperformedonavarietyofrepresentationsoftheprogram:thesourcetext,anabstractsyntaxtree,aflowgraphrepresentation,alinearintermediateform(suchasquads[Aho+77]),orthe(linear)objectcode.Optimizationscanhaveavarietyofeffects.Forexample,statementsmaybemovedordeleted.Variablesmaybeassignedvaluesatdifferentrelativelocationsintheoptimizedcodethaninthesourceprogram,ortheprogram'sflowofcontrolmaybealtered.Therelativeorderingofexecutionevents(suchascallingaprocedure)maybechanged.Optimizationsmayalsoeliminateoroverlayvariablesorallocatethemtoregistersinsomeprogramregions.Theeffectsofoptimizationscauseproblemsforinteractivesource-leveldebuggers.Whenoptimizationsmoveordeletestatements,orwhentheyaltertheprogram'sflowofcontrol,itmaybedifficultfortheprogrammertospecifybreakpointlocationsorforthedebuggertoreportexceptionlocations.Whenoptimizationseliminateoroverlayvariablesorallocatethemtoregisters,thedebuggermaybeunabletodisplaythevaluesofthosevariables.Whenvariablesareassignedvaluesatdifferentrelativelocationsinthecompiledcodethaninthesourceprogram,thedebugger'sabilitytodisplaythevaluesofthevariablesandtoreportthecurrentexecutionpointmaybothbecompromised.Whenoptimizationschangetherelativeorderingofexecutionevents(includingarrivingatabreakpoint),thedebugger'sreportsofsuccessiveprogramexecutionpointsmayconfusetheprogrammer.Infact,thebasicpresuppositionsofoptimizationandinteractivesource-leveldebuggingconflict.Anoptimizerassumesthatthepurposeofaprogramispreciselytocomputetheprogram'soutput,andthattheexactintermediatestepsrequiredtoachievethisgoalareirrelevant.Theoptimizerrearrangesandrestructurestheprogram,removinginformationaboutmanyoftheprogram'sintermediatesteps.Therefore,aparticularintermediatepointintheunoptimizedprogrammaynotdirectlycorrespondtoanypointintheoptimizedversion.Incontrast,aninteractivesource-leveldebuggerallowsaccess,insourceprogramterms,toalargeclassofprogrampoints,includingsomethattheoptimizermayhavechanged.Theoptimizercannotavoidalteringallprogrampointsthattheprogrammerwishestoexaminefromthedebuggerandstilldoitsjobwell,becauseitcannotrïgî&sî'ïgïgî'þrî,)ïgsïgî,Ùrî.ïgsïgî.’ pïgîNšrïaÙîâsïbfî5rïaÙîÃîî´î îUî" î(óî+  î2àî4éî74îjï_ï_î>ºrîD=ï_ï_îEUï\Vîâ îôîŠî”î!¤î'M î1‘î6Ìî9Eî?îD¬îF1ïY”îâîöî¬îVîv î$Ž î-ðî/eî1Íî7}î:Ìî<ƒî>ëîD¯ ïVÒîâ îÍînîtî#Mî%iî&¨î+Dî-î6£î8rî:çîAîCyîGÞïTîâî î[îÙî,î�î&Jî/Òî15î5N î=�îA!îEîFësïQOîârî½ïQOïQOî7îî×î7î î"#ïM¹î¤ î^îÏîúî! î%uî'î, î.™î4P î:ïî=Øî?®îDîEÂïJøîâîõîîþî�î#ºî%]î+ î/öî5¼î7tî9Þî@TîC¦îFÖîH�ïH6îâîîÞî…îÇî#î&î'­î,Cî/)î0ýî60î8ëî=¬îCîD¹ïEuîâîî´îYî´îÕ î$Èî'Ãî)ªî/ã î8¯î;ªî>mîDaîFïB³îâî�îaîaîêî ˜î%ûî'©î+<î0Ëï?î¤î¯î3î î#Ðî'¹î-õî0f î7H î? îFÖï<\îâ îcî&îîî! î(î)Þî-—î0«î3Ôî67î<§î?ÄîA�îF�îGêï9šîâî î€î÷î‘ î#®î%—î*n î1™î7�î9�î<î>žîDâîFËï6Øîâîý î^î\ î'¾î-¡î/Jî4î9£î;Lî@1îC îE3 ï4îâî<î@î?î*î ¬î"Uî'î)\î-…î/9î2Ó î9_î=rîC'îEuï1Uîâîîîeîéî¥î$?î%Ëî( î-åî1 î4î5šî7Øî<îAËîD ï.”îâîî¶î_îµîÙî!ˆî#Þî)�î,<î-áî1ûî4Pî9î?<îBÑîEËîHþï+Òîâ îŸîä î%�î*bî,îî1ùî7´î9™î?ûîDa ï)îâîâîZîd îî F î' î+“î-, î3xî8çî>üîBÿîEãï&OîâîA ï"¹î¤îJî&î\î¦î%Fî&Ö î.¦î15 î7º î?îE¬ïøîâî*îHîŠîNî!¢î&Úî(ˆî)§î/*î0‹î60î7Ôî=oî?ÄîF$ï6îâî­îŽîî� î"ªî&%î+Èî-Šî2‡î5<î8Gî:® îAÚîDÅïtîâ îÎîÏ î ƒî#,î)]î/Ä î7˜î;Ãî?×îAÚîDƒï³îâ îüî� î"Yî#¤ î)ú î2î5Óî7¡î:! îB;îGêïñîâî5î îîŽî! î$‰î&î(Rî.›î3úî5§î; î<Ø îCd ï0îâîØîóîFîáî#î(šî,ªî.Fî/]î2±î5Ïî7uî<ñîAZîG[ïnîâî§îýîîî Uî&�î)[î/{î3îî7¤î<šî>�îDîH ï ­îâîK î7î›îTî$Öî(Gî*°î0Ãî3„î6/î8?î:$î<—î?çîEîFrÿ �TVm$ÄCHAPTER1:INTRODUCTION4knowwhichpointstheseare.Mostprogramsexecuteseveraltimesbeforetheyarerecompiled,andthepointsofinterestcanchangefromoneexecutionoftheprogramtoanother.AccordingtoGaines,thefirststepindiagnosingaprogramerrorisknowingthattheprogramreachesanincorrectstateduringitsexecution.Therearetwopossiblecausesfortheincorrectstate:somevariablescouldhaveincorrectvalues,ortherecouldbeanerrorintheprogram'sflowofcontrol[Gaines69].Ifaprogrammerusesaconventionaldebuggertomonitorthebehaviorofanoptimizedprogram,theeffectsoftheoptimizationscancausethedebugger'sresponsesto:9givetheappearanceofanerrorwhenthereisnone,9maskerrorswhentheydoexist,or9atbest,giveaninaccurateviewoftheprogram'sexecutionbehavior.1.2ExampleAsmallexampleillustratesthekindofproblemsthatarise.Figure1-1showsasimpleFORloopthatreadsitemsintoanarray.Theunoptimizedcodeappearsontheleft,andasource-levelrepresentationoftheprogramafteroptimizationappearsontheright.[Thesource-levelviewofeffectsoftheoptimizationsappearsforpurposesofexplanation;itisnotavailabletotheuser.]Becausetheassignmentx_1(atstatement18)isnotaffectedbytheexecutionoftheloop,thecodemotionoptimizationcanbeapplied.Thisoptimizationmovesx_1outsidetheloop,therebyreducingtheprogram'sexecutiontime.Aftertheassignmenttoxhasbeenmovedtoprecedestatement16,thevalueofxassignedinstatement15(0)isnotusedbeforeitisreassigned(to1).Theoptimizerusesthedeadstoreeliminationoptimizationtodeletestatement15.sourceprogramfragmentaftercodemotion&deadstoreelimination15x_0;x_1;16FORiIN[1..3]DOFORiIN[1..3]DO17Read[a[i]];Read[a[i]];18x_1;19ENDLOOP;ENDLOOP;Figure1-1.Effectsofoptimizationonthereportedvalueofxatstatement17.rïgî&sî'ïgïgî'þrî,)ïgsïgî,Ùrî.ïgsïgî.’ pïgîNšrïb)îâî»îâîîÂî"$î%Æî+óî1î5¬î9oî=ØîAîCn ï_gîâî™îùîîÕî´î!?î%èî)Oî+úî2/î3èî6Hî;×î=…ï[Òî¤î<îàîÔî!)î#öî&Ðî(s î/Mî0lî5ðî9Wî:¸î@GîC îE`ïYîâîåîúîÚî/î#Äî% î-î1Bî3¹î6Šî;ðî@MîB¯îE2ïVOîâîˆîîÏî–î"Ùî(‘î-î.Óî2Yî6 î8 î9ùî=gî?îAmîGÕïSŽîâî—sîEïSŽïSŽî”rîMïSŽïSŽî¤î"îH î&&î)î*@ î2Vî8[î:î?BîA�îGIîHþïPÌîâîNî5î”î!äî#�î%ý î.zî1î4ºî7 î=ÿîD)vïM7îKrïN î î÷îW î"Šî$Cî&4î)¥î-Zî0äî2OvïJuîKrïKIî î�î“î!Hî$Xî&_î)çvïG´îKrïH‡î î¢îÞîÌî¼ î&Jî)…î+>î-žî4 î:>tïAêîâîrï=Èî¤î?îìît î"­î%î([î*"î0:î3î7Lî;Ëî>8îBTîC�sîHï=Èï=ÈîHºrï;îâîîÒîoîîíî Üî%<î( î0 î3Oî8Yî:]î<»î?†îB<îCd ï8Eîâ îâî£î î!¢î$ç î,èî1üî4 î6rsî:±ï8Eï8Eî;î=N îC]îEùîGaï5ƒîâîEî. îûîîÔî#vî$Ù î++î,?î-eî/^î3öî5Qî7:rï5ƒî:Öî@îB~ wîI’ï5ƒï2Áîâî’rï2Áîî#îkîÛîXî ßî&)î(6î*§î0îî2¹î5*î8¹uî;*ï2Áï2Áî;Åî>Wrï2ÁîBõ ï0îâîfîOîî î$ wî(Eï0ï0î)õî+¥rï0î,úî1»î4î7‰î<‚îB+îDƒï->îâîî)îÍî2 î&Iwî'ýï->rï->î)_î+Ùî/<î3Èî5|î:£î@ÞîC!îE†îI5wï*}îârï*}îQîÝîžîçîßî"î#™î&!î)pî-Òî/;î0º î7pî9«î<[î?FîE‚îH�uï'»îâîî[ rï'»îj î$cî&î*î0Uîâï$×þÀî¢ï$×þÀîcï$×þÀî&#ï$×þÀî-äï$×þÀî5¤ï$×þÀî=dï$×þÀîE%ï$×þ`îE…ï$×þ`îEåï$×þ`îFFï$×þ`îF¦ï$×þ`îGï$×þ`îGgï$×þ`îGÇï$×þ`îH(ï$×þ`îHˆï$×þ`îHèï$×þ`îIIï$×þ`îI©ï$×þ`îJ ï$×þ`ï%@ï%@î¤ï!Ïþ„xî¤ï"8î(ï!Ïþ»î(ï"8îãï!ÏþÇîãï"8îªï!Ïþ„îªï"8î.ï!Ïþ›î.ï"8îÉï!Ïþ¥îÉï"8îoï!Ïþ„îóï!ÏþÇîóï"8îºï!Ïþ„îºï"8î>ï!Ïþ»î>ï"8îúï!Ïþ°îúï"8îªï!Ïþ„îªï"8î.ï!Ïþ¥î.ï"8îÔï!Ïþ*îÔï"8îþï!Ïþ„î‚ï!Ïþyî‚ï"8îûï!Ïþ„îûï"8îï!Ïþ¥îï"8î%ï!Ïþ°î%ï"8îÕï!Ïþ*îÕï"8îÿï!Ïþ¥îÿï"8î¤ï!ÏþÇî¤ï"8î kï!Ïþoî kï"8ï"8î*ñï!Ïþ¥rî*ñï"8î+–ï!Ïþyî+–ï"8î,ï!Ïþoî,ï"8î,~ï!Ïþ¥î,~ï"8î-$ï!Ïþ„î-$ï"8î-¨ï!Ïþ„î.,ï!Ïþ›î.,ï"8î.Çï!Ïþ»î.Çï"8î/‚ï!ÏþÇî/‚ï"8î0Iï!Ïþ¥î0Iï"8î0ïï!Ïþ„î1sï!Ïþ*î1sï"8î2�ï!Ïþ»î2�ï"8î3Xï!Ïþoî3Xï"8î3Çï!Ïþcî3Çï"8î4*ï!Ïþ»î4*ï"8î4åï!ÏþÇî4åï"8î5¬ï!Ïþ„î60ï!Ïþî60ï"8î7Dï!Ïþ„î7Èï!ÏþÇî7Èï"8î8�ï!Ïþ¥î8�ï"8î95ï!Ïþ¥î95ï"8î9Úï!ÏþÇî9Úï"8î:¡ï!Ïþ„î;%ï!Ïþ„î;%ï"8î;ªï!Ïþoî;ªï"8î<ï!Ïþ»î<ï"8î<Ôï!Ïþ„î<Ôï"8î=Xï!Ïþ¥î=Xï"8î=ýï!Ïþ„î>‚ï!Ïþ¥î>‚ï"8î?'ï!Ïþcî?'ï"8î?Šï!Ïþcî?Šï"8î?íï!Ïþ*î?íï"8îAï!ÏþcîAï"8îAzï!ÏþÇîAzï"8îBAï!Ïþ¥îBAï"8îBæï!ÏþoîBæï"8îCUï!ÏþcîCUï"8îC¸ï!Ïþ»îC¸ï"8îDtï!ÏþÇîDtï"8ï"8ï"8wïéî¤î+îÛî‹ïBî*ñî, î.Pï›î¤î+î‹î;îÂî!ªï›î*ñî.Pî0î2ˆî8oïóî¤î³ ïóî-x ïLî¤î³îcîï¥î¤î³ï¥î-xyïîÑî*î[î öî"¤ î*„î,î.Ýî4Kî7Þî9‹î:Ëî+ îEHîGEï8Eîâ îåî7îkî!î"{î' î(Äî*Àî0Cî6�îîÊîá î"[î'Çî,4î. î3¢î8]î;îAÇîGï&îâî îˆîPî îhî#|î'sî(�î.pî04î6îî=î>mîA©îCXîH�ï#RîâîhîÑî( î#Pî'üî)€î/Kî4ýî:þî?îBLîEï ‘îâîîiî î‘î"ø î)Zî.ÿî2î6Øî:Uî?)îE2ïÏîâîëî†îjî^îÃî!5î$Áî)Aî+Vî1î5tî;kî=ãîAîC ïîâ îîÂîˆîÐ î(yî)®î,�î2Jî3áî9¿î?…îB“îEjïLîâîCî îtîî$k î*Aî-Œî/Tî1Íî7î8åî<©î?‘îBÛîI*ï‹îâîdsîÜï‹ï‹î,rî"Ëï‹ï‹î$)î'Æî*$î/²î1î6Qî7þî9íî?‡î@ÜîBFîHCïÉîâîbîàîú î wî&€î)Xî/Äî4‹î6Dî8¤î>3î?žîBÚ #TVm$CHAPTER1:INTRODUCTION6Therearetwomajorreasonsforthisstrategy.First,anoptimizingcompilationisusuallymoreexpensivethananonoptimizingone.Thatis,anoptimizingcompilationtakeslonger,anditmayalsousemorespace.Thisreasonisbecominglessvalidbecauseofadvancesinoptimizationandcompilertechnology,asthefollowingtwoparagraphsexplain.Second,theuseofaninteractivesource-leveldebuggerrequirescompiler-providedmappingsbetweensourcelinesorstatementsandmachinecodelocationsandamongvariablenames,types,anddatalocations;optimizationscanalterthesemappingsinwaysthathavenotpreviouslybeenunderstood.Theremainderofthisdissertationdisputesthesecondreasonbyanalyzingthewaysinwhichoptimizationaffectsdebuggingandbydescribingmethodsfordebuggingoptimizedprograms.Oneargumentsupportingmoreuseofoptimizingcompilationisthatsomeoptimizationsarenotexpensivetoapply.Extensiveresearchinbothpracticalandtheoreticalaspectsofoptimization[Allen+72,Lowry+69]hasmadesomeoptimizationsfastandreliabletoperform.Amongtheseoptimizationsaretransformationsperformedonthemachinecodeproducedbyacompiler,aswellastransformationsperformedbeforeorduringcodegeneration.Efficientmachinecodeoptimizationsincluderetargetingbranchestobranchesorcollapsingmultipleinstructionsintoonespecializedinstruction[Wulf+75,Zellweger80,Lamb80,Davidson+80].Efficienttransformationsthatoccurearlierinthecompilationprocessincludedelayingstoreswithinstraight-linecodeandallocatingimportantquantitiestohigh-speedregisters[Sites78].Infact,applicationoftheseoptimizationscandecreaseratherthanincreasecompilationtimebecauselessintermediatecodeisprocessedforregisterallocation,lesspseudo-objectcodeparticipatesinfinaladdressassignment,andlessobjectcodeiswrittentotheoutputfile[Cocke+80].Anotherargumentsupportingmoreuseofoptimizingcompilationisthatoptimizationphasesaresometimesusedtomakeacompilersimplerormoreportable.Forexample,somecurrentcompilationenvironmentscontainmachine-independentcodegenerators[Glanville+78,Cattell80]orsourcecodepre-processors[Kernighan+76]thatgeneratefairlynaiveandinefficientcode.Inthesesituations,theunoptimizedprogramwouldbesufficientlylargeorslowthatitisworthwhiletospendtheextracompilationtimeforoptimization.rïgî&sî'ïgïgî'þrî,)ïgsïgî,Ùrî.ïgsïgî.’ pïgîNšrïb)î¤î”î×îrîWî#$î%Pî'àî-°î1=î3 î9å îA_îBºîG[ï_gîâî1î[î‰ î"¯î&?î)Šî+Rî-F î4$ î;³î?5îCÕîF�îGêï\¦îâî¶î2îÌîlîŽî#ïî%bî+´î.Pî1¿î6èî8¨î>‚î@7 îH7ïYäîâî² îîÝî Qî&xî)9 î0Uî6-î;oî=ãî@mîB;îD@ ïW#îâ îYîNî!ˆî,öî3"î8}î<¹î?àîA‘ îH7ïTaîâîˆîðîÍî ¥î%Mî*¥î/bî3pî6Hî9o î?Å îHcïQ îâî$îÊî'îòî!kî$Vî'ºî*K î1 î4… î<Íî?ÂîFwîHMïNÞîâ î†î:îõî#âî(—î*îî1fî4!î7Øî9áî>J îFžïLîâîœîSîO î çî&wî(´î/nî5ÚïH‡î¤î±îå î!Ôî%qî'ðî)² î0– î8*î9Ÿîî?1î@QîF\îHï=�îâîîpî"Àî'›î)êî.çî2º î;qîA—îG§ï:Àîâ î_î? î#$î(ìî*šî0aî2% î8‘î> îEjîHCï7þîâ î´ sî|ï7þï7þîÌî" î(mî,ô rî3üï7þï7þî56î:½îDrîG.ï5<îâî<îîv îî$î(÷î.‘î2ˆî6ã î>�îAìîDº ï2{îâî@ îˆî3 î$,sî)‹ï2{ï2{î)Úrî-yï2{ï2{î.Òî0žî3  î:®î î$&î'ºî*0î+ë î2Æ î:Rî;¿î>Ž îF‰ï#ßîâîYî6î•îhî!@î"�î(lî-yî/aî3î9ªîõî@lîAø îI@ïÙîâîåîDî· î Aî#gî%¤ oTVm$8CHAPTER1:INTRODUCTION71.3.2Whydebuganoptimizedprogram?Insomesituations,itisinconvenientorevenimpossibletodelayoptimizationuntilaprogramisknowntobecorrect:1)Someoptimizationsmaybeanintegralpartofthecompilationprocess,eitherbecauseoftheirhighpayoff/speedratioorbecauseoftheorganizationofthecompiler(suchasuseofalocalcodegeneratorbasedondirectedacyclicgraphs(dags)[Aho+77]).Itmaynotbepossibletoinhibittheseoptimizations.2)Withoutoptimization,someprogramsaretoolargetofitonthehostcomputerortooslowtotesteffectively,especiallyinthelatedevelopmentstages.3)Errorscanbediscoveredatanytime,eveninaproductionprogram.Infact,optimizationcanindirectlycontributetotheirdiscovery:optimizationofrangeandsubscriptcheckscanallowproductionprogramstoexecutewithcheckingenabledwithoutpayingaprohibitiveprice[Sites78,Markstein+82].Whenanoptimizedprogramhaltswithanerror,itisdesirabletocollectasmuchinformationaspossibleabouttheerrorwhileitscontextisstillavailable.Beingabletouseadebuggerimmediately,ratherthanrecompilingandre-executingtheprogramtothepointoferror,wouldbehelpfulforseveralreasons.Theprogrammayhaveexecutedforasubstantialamountoftime,thesequenceofinputsmaybedifficultorimpossibletoduplicate(forexample,inanoperatingsystemorinanyotherprogramacceptingdatafromtherealworld),orthebugmaysimplybeintermittent.Furthermore,recompilationtoenabledebuggingmaybeexpensive,particularlyifotherprogrammodulesmustberecompiledorreloadedasaresult.4)Incompatibilitiesbetweenthecheckoutandtheoptimizingcompilersmaymakeitpainfultoswitchfromonetotheother.Evenifthetwoversionsofthecompileracceptpreciselythesameinputlanguage,aprogrammightruncorrectlyunderthecheckoutcompiler,yetstillcontainanerror.Forexample,ifthecheckoutcompilersetsthevaluesofallvariablestozerobeforebeginningexecutionanddoesnotspecificallycheckforusesofuninitializedvariables,auseofanuninitializedvariablemightnotbecaught.5)Debuggersarefrequentlythebasisforprogrammonitoringtoolsthatprovidestatementexecutioncountsortiminginformation.Itwouldbeusefultobeabletoapplythesetoolstooptimizedprograms.rïgî&sî'ïgïgî'þrî,)ïgsïgî,Ùrî.ïgsïgî.’ pïgîNšzïaïîâîÏî½î~îÑî%Brï]Ìî¤îgîï î[î¦î  î( î)Ùî- î3×î5zî9 îAîDAîE`ï[ îâîNîÔî‚îsïWuî¤îbîI î×î"ìî$íî&îî+ÿî.óî0½î3- î:Éî@îDîI5ïT³î¤îéî î iî#£î%fî*‡î,>î.� î6rî8*î:‰î@CîCìîE™îH îIÅïQñî¤îãî#î:î"î$î)[î-Åî2/sî6@ïQñïQñî6�rî;ïQñïQñî;•î<çî>XîAUîCÃîE¬ïO0î¤îRîÃîL ïKšî¤îMî¸ î!î$“î*¡î,ðî/Uî2¸î4bî6-î8/î:Šî=îC¥îEdîGÊïHØî¤îRîÞ îÎ î#î$°î'î)± î1áïEBî¤îRîŠîî î"×î$pî'î*�î-Õî/„î0® î7µî>!î?ðîBõ ïB�î¤îP î� î!Kî#î&‚ î-0 î5Jî7$î;î=èîCÜîHcï?¿î¤î î¸î"þî$Þî*î-Sî3Aî8 î=ÞîBŒîCç ï<þî¤sîï<þï<þîkrî»ï<þï<þsîœï<þï<þî® rî êï<þï<þî"Uî&rî(gî.Ùî4lî7¸î:Øî<Îî@�îAøîCiîI@ï:<î¤î&îî î#Íî%®î+#î/7î1Éî5nî9Vî;cî@jîBîDÜ ï7{î¤îÓîîî¼î*î%x î-ìî2>î5¨ î=‚î@} îH�ï4¹î¤î:îïîVîýî ½î$Žî(Äî*¼î/‚î1Æî6^î<'î?îD�îG¨ï1øî¤îAî^îh î!î&î'žî*üî-<î3î4žî8­î;’î=cîB{îD ï/6î¤îCî)îÑî!”î#3î%î+%î/’î1Hî2çî5zî9 î>ŠîD‘îG‡ï,tî¤îúî§î[îîlî"&î%!î)‡î+o î3Ä î<8 îDäîF‰ï)³î¤îzî›î¨ î$h î+Îî-Kî1î6³îîAîDÏîF0ï šî¤îJî{îÚî}î#î!zî%äî)dî*¼î-î/·î4úî6«î9î>µîBçîH�ïØî¤îFîîZî ©î&^î*zî-6î3î7)î9®î?¦îEßîHNïî¤îuîXîŒî*î$îî&Aî(“î.Yî4î6›î8íî=î>¹î@œîFJîGëïUî¤î÷îfî" î%[î(�î+ î2î5ùî8:î;7î<ô îDÛ ï”î¤îÍîBîûîì î Ïî&î)üî,qî.bïþî¤îwî�îú î#Ãî&Gî)Éî,+î1ß î9î<–î?‰îD¹ï<î¤îØî2îôî"M î*±î,'î0Tî2Dî6[î8 î9øî<ðî>žîBhîEðîI@ï {î¤îÿñTVm${CHAPTER1:INTRODUCTION81.3.3CurrentsupportfordebuggingoptimizedprogramsWhenoptimizationscannotbedisabled,theabsenceofspecificsupportforinteractivesource-leveldebuggingofoptimizedprogramsforcesprogrammerseithertoinsertsource-languagedebuggingstatements(andthenrecompiletheprogram)ortouseaninteractivemachinelanguagedebugger.Insertingsource-languagedebuggingstatementsisthemostprimitivesource-leveldebuggingfacility:thenewstatementscanverifyassertions,printintermediateresults,ortraceexecutionflow.Becausetheprogrammermustmodifyandrecompiletheprogram,thismethoddestroysthecurrentcontextoftheerror.Evenmoreimportant,itisnotinteractive:ifsomedebuggingoutputpromptsanewquestionabouttheinternalworkingsoftheprogram,themodify/compile/executecyclemustbeenteredagain,makingittakelongertolocatetheerror.Inaddition,theprogrammermustremovethechangesaftertheerrorhasbeenfound.Fromtheoptimizer'sviewpoint,requiringrecompilationtoansweradebuggingqueryisanadvantage.Becausetheaddedstatementsexistatcompiletime,theoptimizerknowsduringtheoptimizationprocesswhichvariablevaluesaredesiredwhere,andwhichlocationsinthecontrolflowareofinteresttotheprogrammer.Byreferencingvariablesorgeneratingoutput,thesestatementschangetheintermediatestepsintheprogram,possiblyinhibitingoptimizationsinthesurroundingareasothatthosevariablesorlocationsappearproperlyintheoptimizedprogram.However,therecompiledprogrammaybelessefficientthantheprogramthatexhibitedtheerrorandmaytakelongertoreachtheerrorpoint.Usinganinteractivemachine-leveldebuggerisprobablyevenlessinvitingthaninsertingdebuggingstatements.Thismethodisavailableonlyiftheprogrammerunderstandsbasiccodegenerationtechniquesandthehostmachinelanguage,whicharedetailsthatthehigh-levellanguageisintendedtosuppress.Astrongerrequirementisthattheprogrammermustalsobeanoptimizationexpert:shemustbeabletounraveltheeffectsoftheoptimizationstodeterminethemachinecodelocationcorrespondingtoagivensourcestatementortodeterminethestoragelocationthatholdsthecurrentvalueofagivenvariable.Evensuchminimalaidsassymbolicprocedureandvariablenametranslationsmaybeinvalidatedbyoptimizationssuchasinlineprocedureexpansionandallocationoffrequently-usedvariablestoregistersduringloops.rïgî&sî'ïgïgî'þrî,)ïgsïgî,Ùrî.ïgsïgî.’ pïgîNšzïaïîâîÏîéîÍî!oî)/î0 rï]Íî¤î" îî#èî&?î,lî/2î4ºî6Ùî<*îAœîD@ ï[ îâ îeîîÉî%.î+:î/4 î7”î;yî= î@äïXJîâî• îHîrî"‘î(ëî+Dî1Fî3î4ªî7î9 î?ªîE(ïUˆîâïQóî¤î~î!œî(j î/8î0·î3+î6›î<– îD5ïO1îâîÒî"î îªî"%î& î,}î/Õ î7¿î îAXîG}ïLpîâî îV î!î!rî&î(¹î/î1Lî7î9¦î>›îCÜîF%ïI®îâî§îQî¢îÒîKî"Ï î)yî*Áî,î.ƒ î5œî6îî:rîAîE€ïFíîâî9îTîî î­î$ðî*øî,ßî/kî5î8 îG{ïD+îâîkî~î”î·î"Áî$9î'Tî+¹î-ˆî1¡î4"î8²î:£î@‹îC ïAjîâîJî3î’î¿î!úî$Zî'Ìî*Aî-žï=Ôî¤î“î î, î%õî, î4Ûî6¤î;Zî<žîCqîGxîHþï;îâ î^îµî)î"b î)0î,uî."î3nî7î9tî?²îD îH�ï8Qîâ îïîÖîøî%Bî)„î+ëî0Çî5Kî8î<8îBîCÈîF<ï5�îâî:îËîÂîßîËî h î)¢î+ü î3lî9eî;f îB]îGeï2Îîâ î­îgîØ î$ãî(]î*î,�î2†î7ä î>A îFÏîH�ï0 îâ îÀîÖî¶î¡î"\î(3î*î/ëî4Žî::î<î>€îEï-Kîâîî{ î¥î$6î'=î)0î+Èî1"î4Kî6­î<>î?îEîG|ï*Šîâî™î�î–îÚîˆî!>î#�î'ï&ôî¤îêî î î(î.dî0î6+î9µî<�îAßîEIï$3îâîµ î~î ²î%×î']î-1î0eî1ßî4X îá îE(ï°îâî'î¼îCî`îÆî#÷ î+�î,âî/‰î1Á î9|î<½î?cîA,îBõ ïîîâîŠîôîQî6î%îÈî$²î'î+Kî,ùî/M î7¿î9bî?ÚîB.îG§ï-îâî îîÁîëî#¡î'ñî.(î/ìî1œî8î:î?2îDjîG9ïkîâî<îî¥îYî}î ,î&4î)·î,ãî2Kî5î6Çî<ˆîCîE¸ï©îâîÎ îCîsî� î&Îî(ö î1 î4þî6Øî:åîA”îH7ïèîâ î!îÚî ¯î&jî(î-{î1ì„TVm$8CHAPTER1:INTRODUCTION91.4BriefdiscussionofpreviousworkResearchershaveonlyrecentlybeguntoconsidertheproblemofinteractivesource-leveldebuggingofoptimizedprograms,eitherinstudyingtheinteractionsbetweenoptimizationanddebuggingorindesigningandimplementingdebuggingsystemsforoptimizedprograms.Asof1981,onlytwopapersexplicitlydiscusseddebuggingoptimizedprograms.AdetaileddescriptionandcritiqueofthesepapersandotherrelatedworkisdelayeduntiltheendofChapter3sothatconceptsdefinedinthisdissertationcanbeexploitedinthedescription.Thefirstpaper,byWarrenandSchlaeppi,isadesigndocumentforadebuggerfortheFirmwareDevelopmentSystematIBMYorktownHeights[Warren+78].Theproposeddebuggerwastohaveafullrangeofdebuggingcapabilities,butwouldprobablyhaveconfusedallbutthoseprogrammerswithoptimizerimplementationexperience.Aseconddebuggingmode,whichwouldinhibitoptimizationsacrossstatementboundaries,wastobeprovidedforlesssophisticatedusers.Thisdebuggingsystemwasneverimplemented,sonoexperienceconcerningitsutilitywasgained[Warren82].Intheotherpaper,Hennessydescribesalgorithmsforinteractivelyexploringanaugmentedglobalflowgraphofaprogramatruntimetodeterminewhichvariableshaveincorrectvalues[Hennessy79].Avariableinanoptimizedprogramhasanincorrectvalueifithasadifferentvaluethanitwouldhavehadinanunoptimizedversionoftheprogram.Eachnodeoftheflowgraphisadirectedacyclicgraph,whichrepresentsonebasicblockofboththeunoptimizedandtheoptimizedprogram.Hennessyalsopresentsconditionsunderwhichthevalueofthevariablewithrespecttotheunoptimizedprogramcanbereported.Thesealgorithmsweretested,butwerenotincorporatedintoanyprogrammingenvironment.Inadditiontothelackofimplementationexperience,thepreviousresearchdidnotfullyexploretheinteractionsbetweenoptimizationanddebugging.Forexample,bothpapersclaimedthatmachine-dependentoptimizationsdonotaffectdebugging.Thisisnottrue:statementboundariescanberemovedbycollapsinganumberofinstructionsintoasinglepowerfulmachineinstruction,causingproblemsiftheuserdesiresabreakpointatoneoftheseboundaries.Thisproblemisexacerbatedbyso-called"exoticinstructions"thatcanperformthefunctionofanentireloopinoneinstruction(forexample,theSearchLinkedListinstructionontheBurroughsB4800)[Morgan+82].Branchchaining,anotherwell-knownmachine-dependentoptimization[Wulf+75],canrïgî&sî'ïgïgî'þrî,)ïgsïgî,Ùrî.ïgsïgî.’ pïgîNštïa¸îâîîØ îñî"Kî)Ôrï]–î¤ î~î î gî%ãî*Vî,Iî2î4«î:sîœîCÜ ïR�îâî¡îµîvîî uî#4î&Ûî+uî.úî0mî5‹î8Úî;Bî>î?ÂîEîFTîH ïOÎîâî}î~î,îÍ î%î'¡î)’î/�î1>î3� ïL9î¤îºîÑîIî„î#Âî&¸ î-›î/Eî0­î5;î;çî>cî?ËîFîH�ïIxîâîM îöî"Õî$Žî'õî.‹sî3ÃïIxïIxî4 rî:,ïIxïIxî;Îî>ÆîDåïF¶îâîƒî'îdîƒîîÄîrî&" î-�î0î4'î9ïî=+îBóîDÙîGOïCôîâ î>îNî m î*A î1áî3cî7êî>™îB½îFÀïA3îâî^ îçîÿî&? î-µî0lî2%î4!î9þîç îGï>qîâîüîµî/îÛî#¤ î,Nî.î0 î6ñ î=÷î?ÑîCÓîF~sï;°îâ rî0ï;°ï;°ï8î¤î�î îÉî î$sî*x î1Yî3´ î;“îAÏîCÜï5Yîâî@îüîðîUî#î$ñî*dî,Mî3 î7Sî=Hî@ÊîFÀsï2—îâ rî(ï2—ï2—î›î0îpî'î! î'•î--î/«î1¤î7iî;î<†î=åî@cîA–îGEï/ÖîâîîRî{î»îmîî! î(óî-µî/hî1Âî8 î;�î>úî@­îCîIƒï-îâîVîîî©î7î#� î*[î-Qî1î5î7î:¡î=J îEŽîH�ï*SîâîIî¨î!Øî$Ÿî)ò î0�î4Žî8–î:ðî>•î@HîB¢îGÓï'‘îâîŽî@î£ î¡î%3î'Âî)·î0*î4/ î:÷î>LîB îE$îHyï$Ðîâ îòîÊîk î$ý ï!:î¤î«îRî8îÐî ëî"Ü î,ó î4^î6öî<½îBXîEîG³ïyîâîÕî> î¦î# î+ î-á î5‰î8>î>îA^îEÍï·îâîîž î'rî)Ðî,�î0À î9î8îAîD¹ïöîâ îîîtî`î î" î(gî)Œî.³î0f î7Àî:“î;¸î?žîEjï4îâ î7îCî!nî"ñî%rî(�î-6î.� î5”î7Oî:î;÷î?£ îGÔïsîâîTî® î'îî$¯î)P î1Mî4 î6‚î;Èî>îC}îE$îGï±îâî î¼îk îIî î%Øî(;î,ºî1{î4@ î;î=(î?‹îFHsï ðîâ rîwï ðï ðî×î•î!|î&‡ î-ðî:/ sîB(ï ðï ðîBwrîGeï ðï ðîHAÿÏTVm$„CHAPTER1:INTRODUCTION10alsomakebreakpointinsertiondifficult,becauseitallowssomeexecutioncontrolpathstobypassaprogrampoint.Anotherkeyissuethatthesepapersignoredishowtomaplocationsbetweenthesourceprogramtextandtheoptimizedobjectcode:howdoesthedebuggertranslateabreakpointrequestatasourcestatementintotheappropriateobjectlocation(s),andhowdoesthedebuggertelltheuserwhereintheprogramexecutionhasbeensuspended?Theseearlyresearchersthoughtthatsomesimplepartialsolutionswouldbeadequate,butinfacttherearecommonoptimizationsanddebuggingrequestsforwhichthesesolutionsfail.Section3.2.2discussesthelocation-mappingproblemfurther.1.5ScopeandgoalsofthisworkThegoalofthisdissertationistoshowthateffectiveinteractivesource-leveldebuggingcanbeprovidedforoptimizedprograms.Sincedebuggingoptimizedprogramshasbeenalargelyunexploredresearcharea,thefirstpartofthedissertationmapsouttheproblemarea.Thesecondpartofthedissertationdescribesimplementationexperiencewithasmallsubsetoftheproblem,supportingthediscussionanddesigninthefirstpart.Thedissertationaddressesthreesubgoals:1)toinvestigatetheinteractionsbetweenoptimizingtransformationsanddebuggingcapabilities,delineatingtheproblemsthatarisewhentryingtodebugoptimizedprograms.Chapter2discussesinteractivesource-leveldebuggingofAlgol-likeprogramsandarrivesatanotionof"effectivedebugging".Chapter3discussesprogramoptimizationandexaminesindetailtheproblemsthatoptimizationcreatesfordebugging.2)toexploregeneraltechniquesthatcanbeusedtosolvetheseproblems,culminatinginthedesignofeffectivedebuggingtoolsforoptimizedprograms.Chapter4describesgeneralsolutiontechniquesandillustratestheiruse.3)todemonstratethepracticalityofthesedebuggingtechniquesbyimplementingselectedonesinarealprogrammingenvironment.Chapters5through7describeefficientwaystoprovidesource-leveldebuggingcapabilitiesinthepresenceoftwosimplebutnontrivialoptimizations:inlineprocedureexpansionandcross-jumping.Aprototypeimplementationofthesemethods,inasystemcalledNavigator,hasbeendevelopedintheCedarrïgî%¶sî&´ïgïgî'šrî+Åïgsïgî,vrî-«ïgsïgî./ pïgîMÓrïb)îâî·ît îmî"& î'¿î,éî.Hî2~î6î`îDîFŸïYîâîeîî¼îî"pî&}î*1î-)î0Nî2¡î8Ÿî>î?5 îFïVOîâî‹îÆî&îmîVî!Æ î)6î-` î4wî7?î:Tî=•î@îFîH�ïS�îâîðîîßîSîöî&@î(Éî,; î41î8Hî;à îBéîH ïPÌîâîvîÜî,î óî%#î'î-Kî/Íî1|î4*î7´î:î?¹ îH7ïN îâîÄîFî¬î!âî%”î+ƒî/î4"î7�î=î@ïKHîâîftïD«îâîî¿îlî lî"Æî&ƒrï@ˆî¤îrî`îî¦ î"åî$Gî%ëî)iî,.î1¨ î8M î?ÍîF|îHþï=Æîâîî¦îmî&î* î15î7ûî>iîA8îDïîFtï;îâ îîpî¸î!î#Üî&¶î(fî*¼ î1ûî5�î7üî:Rî?ÌîCŽîF\ï8CîâîÜî«î! î€î#~ î-r î4cî7”î8Ôî<ˆî@ÍîBœîEï5�îâ îÈî' îªî!aî%°î'^î)¾î,–ï1ìî¤î| îÄî!Øî%aï.Vîeuî–ï.Vï.Vîî¾ îàî"¯ î*yî0 î79îAXîDï+•îe rîÝï+•ï+•î© î"ªî$øî*ðî-­î0Øî4|î8mî: î>)îD„ï(Óîeî²îçî ­ î'[ î.åî5žî7W î=µîCÈîFï&îeî7îšî.î î$Ž î-Gî2Îî4<î:=î@ îH7ï#PîeîbîîÛî";î(Cî+ î3 î7‘î9Î ïºîeuî)ïºïºî™îäîÃî!™ î(Dî+,î-Ðî/µî2Üî4–î7þî;rî@­ïºïºîAŸ îI@ïùîeîûî�îqî#,î*î-¤î0î6ºî>îC›îEï7îeî8îz î%Vî( î.7î1~ï¡îeuîï¡ï¡î�îË î]î!³ î(»î*hî-Üî4U rï¡î:ôî<ù îEÂïàîeî¤îaîšî_ î& î/ î4êî6.î;uî<¸îB+îG’ïîeîîü î"uî) î0)î1Æî4î9©î;Qî=ìîB?îD¯ ï]îe î5î ïî'Kî-›î0, î9�î:öîA ï ›îeî|îdî ªî"¶î$>î)î-m î4ˆî7[î;îB îDîFÖÃTVm$CHAPTER1:INTRODUCTION11programmingenvironmentattheXeroxPaloAltoResearchCenter.Chapter5presentsanoverviewofNavigator,Chapter6describesitsimplementationdetails,andChapter7presentsatheoreticalanalysisofthekeyNavigatoralgorithmsanddiscussesimprovingthealgorithms.Thedissertationemphasizesdebuggingoveroptimizationfortworeasons.First,becausethetheoryandphilosophyofoptimizationisbetterunderstoodthanthatofdebugging,debuggingrequiresmoreattention.Second,exploringthemeaningofdebuggingingeneralhelpstoguidetheselectionofanappropriatedefinitionfor"effectivedebugging".Manydissertationsondebuggingcategorizeprogrammingerrorsanddiscusstherelativeutilityofvariousdebuggingtechniquesfordiscoveringerrorsinthedifferentcategories[Gaines69,Davis75,Model79].Thisdissertationdoesnotconsiderthesetopics;instead,itdiscusseswaystoachieveasensibleinteractionbetweentheprogrammerandthedebuggerduringtheerrordetectionandcorrectionprocess.Forexample,althoughruntimecheckingtoensurethataprogramfollowsthelanguagesemanticsduringitsexecution(suchasarrayboundschecking)isaneffectiveerrordetectionmethod,whetherornotsuchcheckingisenableddoesnotaffecttheproblemsdescribedhere.Anoteonterminology:throughoutthisdissertation,thewords"debugger"and"compiler"alwaysrefertoprograms.Peoplearereferredtoas"programmers"or"users"(intendedtoevoke"debuggerusers"),eventhoughtheymaybedoingdebuggingorcompiling.Inaddition,Iintendnodistinctionbetweenapersonwhooriginallywroteaprogramthatisbeingdebuggedandonewhomaintainsorexaminesthatprogram.Ialsoassumethatoptimizingtransformationsareappliedcorrectlyandthatalloftheirenablingconditionshavebeenchecked.Thisworkisnotintendedtocreatetoolsfordebuggingfaultyoptimizers,exceptinsofarasadditionalinformationsuppliedbythedebuggerallowstheprogrammertonoticeoptimizererrorsmoreeasily.rïgî%¶sî&´ïgïgî'šrî+Åïgsïgî,vrî-«ïgsïgî./ pïgîMÓrïb)îe î î%î&¼î)%î-Rî0uî3™î9Šî?îDWîE–ï_gîeî\î3îò î$µî* î+Eî13î3 î<ùîA§îDeîIºï\¦îeîÛî" î!ùî'+î)î+~î.1î4² î;“î>hîDLïYäîeîÅ ïVOî¤î„ îÖ î#î)Óî,ö î4÷î7=î9òî?½îCdîH�ïSŽîâî`îG î‡îo î'—î)1î-X î4ºî8î; î<ô îD5ïPÌîâîEîï î¿î$î*6î,¬î2\î4+î:ûî<¿îA©îE^îG#ïN îâîAîçî î� î!ð î(:î*x î0¬ ïJuî¤î‰ îDî9î%à î,: î4»î8 î;Fî?ÑîBîFìïG´îâî¦îxî= î##î%k î,³î0´î2mî4×î:‡ sî@çïG´ïG´îA7îFYïDòîârîfïDòïDòîöî( îˆî"Ðî%]î*îî.�î3î8<î9ªî?ˆîBüîDÃîIÅïB1îâî> îJî éî#y î+Œî.tî1î7>î;àî>pîBîH7ï?oîâ îYî îµî#†î)Cî.zî46î5åî:Kî=î>CîCÒîH�ï<­îâîéî^î î"+î(¡î,Œî.{î2Dî7dî=Úî?†îA·îG|ï9ìîâîÏî,îtî!1î# î&Ëî,€î-åî3 î65î8¤îÂîDÄï7*îâï3•î¤îPî‹î² î ÷ î(@î+ î2Ãî5Cî9p î@ûîCÒ ï0ÔîâîFî—îFî4î#ºî&î+Oî,ýî.« î8rî:6î?îEJîFøï.îâî—î“îÕî"„î%�î(�î*|î.Xî5î6Î î> î?×îEšîFžï+Pîâîö î¿î;îsî"ýî& î,;î0î1Wî6ôî9Ðî;Jî?#îE}îHCï(�îâîæî&îêîæî"µï$úî¤î�î:îãî’ î#Mî,õî/*î3õî9{î<î>Âî@“îB-îETï"8îâ î°î"î©î#)î&nî*î+¬î.Lî43î6 î:9î=µî@îGïwîâ îIîúî î.î!¶î#Å î*� î2ˆî8yî:Öî=–îDîH�ïµîâ îÄîsî‹î"´î&«î*>ÿóTVm$³ ÿ TIMESROMANþY ÿ TIMESROMANþŸÿLAURELþŸÿGACHAþŸÿMATHþÿ TIMESROMANþŸÿ TIMESROMANþÿ TIMESROMANþæÿ TIMESROMANþŸÿ TIMESROMANý…ÿ HELVETICAþŸ¸ ™ z ‹!g(�0‹8…@H OÒVj/Y WœÇI¼ÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿ []<>NewChap1 Tuesday, May 8, 1984 1:37 am PDT