1Chapter1IntroductionComputerprogramsrarelyperformtheirintendedfunctionthefirsttimetheyarepresentedtothecomputer.Asignificantfractionofaprogram'sdevelopmenttimeisnormallyspentdebuggingit.Conventionalinteractivesource-leveldebuggersareinadequatefordebuggingoptimizedprogramsbecausetheeffectsofoptimizationsdisturbthecorrespondencebetweentheprogram'ssourcetextanditsobjectcode.Nevertheless,theabilitytoapplyaninteractivesource-leveldebuggertoanoptimizedprogramisimportant.Interactivesource-leveldebuggersallowforamarkedincreaseinprogrammerproductivity[Evans+66],andcompilersthatperformoptimizationsarebecomingincreasinglycommon.Somereasonsforthetrendtowardoptimizingcompilersaretheemphasisonportabilityandmodularityincurrentcompilerconstructionpractices,theincreasedspeedandreliabilityofoptimizingtransformations,andthecontinuingneedforefficientuseofacomputer'stimeandspaceresources[Harrison81].Thisdissertationdemonstratesthateffectiveinteractivesource-leveldebuggingcanbeprovidedforoptimizedprograms.Itinvestigatesthepreviouslyunstudiedinteractionsbetweenoptimizingtransformationsanddebuggingcapabilities,identifiesgeneraltechniquesthatcanbeusedtosolvetheseproblems,anddemonstratesthepracticalityofthesetechniquesbyimplementingselectedonesinaprototypedebuggingsystemcalledNavigator.pg/NqV'A0P4% rIDk"j'+/068;?$BGDF) #)J+P,3 ;?nA'GDD@~  ! )03H :=`D= ?!" +t0<2 <BD:sld$ -+/4F66:B '* 07( >D !Yc" ) /4[ ;8>@BEGq $q& .&03 :< 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,suchasreplacinganrg&s'gg'r,)gsg,r.gsg. pgNtaG r]Z#wn"g&0' /5;O>1CHZ"=$i&+-25 ;AuCE`sX rXXz !B'*,-:3*6 =BDUQ m.W!#$+,-1}3 ;b=@<GIR %"&(.05N739@UFHO *&)f,]/2*48 9=?EjM 0>s >"'&,02d 8;>wBEJKol %,*16=?DG| #%**+ 2 8B;< BCF%DZp!V%(/ uD7 rD?|AGIB,K#$'>,/18i;2ALHC?D N R!'-3X5;N<BDLF< !#f)>+X.36<;ADI@9 AA~ &J6+ ! )(/1 8>7AOBF3jj X&'-< 47 ;BfD 0a u!00"r0( /N2Y 9<|>B -H !5"%Q(* -d/57;8W< CrG+%k L#&). 8vs;+%+%< BUrGD+%+%I(d O  &(/1 7] =@B}Fs%=.h!,,06N =@DCzDH!""%j*25)9) D 8"$).946="B#DI5] p %(+3W7[9C;AGV  S"-0#279;lAGCCIE 0 ).1/6:?B S>#%&)+5 <?E`k "9')+} 3{ :=c>BD_I* S" #&/,{ 468>AFBH 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,becauseitcannotrg&s'gg'r,)gsg,r.gsg. pgNrasbf5ra U" (+ 2474j__>rD=__EU\V !'M 169E?DF1YVv $ -/e17}:<>D V nt#M%i&+D-68r:ACyGT [,&J/155N =A!EFsQOrQOQO77 "#M ^! %u', .4P :=?DEJ#%]+ /57t9@TCFHH6#&',C/)0608=CDEuY $')/ 8;>mDaFBaa %'+<0?3 #'-0f 7H ? F<\ c&! ()-0367<?AFG9  #%*n 179<>DF6 ^\ '-/J49;L@1CE3 4<@?* "U')\-/92 9_=rC'Eu1Ue$?%( -1 457<AD ._!#),<-14P9?<BEH+  %*b,179?Da )Zd  F ' +-, 3x8>BE&OA "J&\%F& .15 7 ?E*HN!&()/*0607=o?F$6 "&%+-25<8G: ADt  #,)]/ 7;?AD  "Y# ) 257:! B;G5 ! $&(R.35; < Cd 0F#(,.F/]257u<AZG[n U&)[/{37<>DH  K 7T$(G*036/8?:$<?EFr 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.rg&s'gg'r,)gsg,r.gsg. pgNrb)"$%+159o=ACn _g!?%)O+2/36H;=[<!)#&(s /M0l59W:@GC E`Y/#% -1B36;@MBE2VO"(-.2Y6 8 9=g?AmGSsESSrMSS"H &&)*@ 2V8[:?BAGIHPN5!#% .z147 =D)vM7KrN  W "$C&4)-Z02OvJuKrKI !H$X&_)vGKrH  &J)+>-4 :>tAr=?t "%([*"0:37L;>8BTCsH==Hr;o %<( 0 3O8Y:]<?B<Cd 8E  !$ ,14 6rs:8E8E;=N C]EGa5E. #v$ ++,?-e/^35Q7:r5:@B~ wI52r2#kX &)(6*025*8u;*22;>Wr2B 0fO $ w(E00)+r0,147<B+D->)2 &Iw'->r->)_+/<35|:@C!EI5w*}r*}Q"#&!)p-/;0 7p9<[?FEHu'[ 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!"8o!!"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/!/"80I!0I"80!1s!*1s"82!2"83X!o3X"83!c3"84*!4*"84!4"85!60!60"87D!7!7"88!8"895!95"89!9"8:!;%!;%"8;!o;"8<!<"8!>"8?'!c?'"8?!c?"8?!*?"8A!cA"8Az!Az"8BA!BA"8B!oB"8CU!cCU"8C!C"8Dt!Dt"8"8"8w+B*,.P+;!*.P028o -x Lc-xy*[ " *,.4K79:+ EHGE8E 7k!"{' (*0C6 "[',4. 38];AG& P h#|'s(.p046=>mACXH#Rh( #P')/K4:?BLE i " )Z.26:U?)E2j^!5$)A+V15t;k=AC   (y),2J39?BEjLC t$k *A-/T178<?BI*ds,r"$)'*$/16Q79?@BFHCb w&)X/46D8>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.rg&s'gg'r,)gsg,r.gsg. pgNrb)rW#$%P'-1=3 9 A_BG[_g1[ "&?)+R-F 4$ ;?5CFG\2l#%b+.P168>@7 H7Y  Q&x)9 0U6-;o=@mB;D@ W# YN!,3"8}<?A H7Ta %M*/b3p6H9o ? HcQ$'!k$V'*K 1 4 <?FwHMN :#(*1f4!79>J FLSO &w(/n5H !%q') 0 8*9?1@QF\H=p"').2 ;qAG: _? #$(*0a2% 8> EjHC7  s|77" (m, r37756:DrG.5<<v $(.26 >AD 2{@ 3 $,s)2{2{)r-y2{2{.03 : $&'*0+ 2 :R;> F#Y6h!@"(l-y/a39@lA 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.rg&s'gg'r,)gsg,r.gsg. pgNza~%Br]g [  ( )- 35z9 ADAE`[ NsWubI "$&+.03- :@DI5T i#%f*,>. 6r8*:@CCEH IQ#:"$)[-2/s6@QQ6r;QQ;<>XAUCEO0RL KM !$*,/U24b6-8/:=CEdGHR  #$') 1EBR "$p'*-/0 7>!?B BP  !K#& -0 5J7$;=CHc? "$*-S3A8=BC <s<<kr<5 =@} H4:V $(*/16^<'?DG1A^h !&'*-<348;=cB{D /6C)!#3%+%/1H25z9 >DG,t[l"&%!)+o 3 <8 DF)z $h +-K16ADF0 J{}#!z%)d*-/469>BHFZ &^*z-637)9?EHNuX*$&A(.Y468=>@FJGUf"%[(+ 258:;7< D B &),q.bw #&G),+1 9<?D<2"M *,'0T2D6[8 9<>BhEI@ {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.rg&s'gg'r,)gsg,r.gsg. pgNza!o)/0r]" #&?,l/246<*AD@ [  e%.+:/4 7;y= @XJ Hr"(+D1F3479 ?E(UQ~!(j /803+6< D5O1" "%& ,}/ 7 AXG}Lp V !!r&(/1L79>CF%IQK" )y*,. 56:rAEF9T $*,/k58 G{D+k~"$9'T+-14"8:@C AjJ3!$Z'*A-= , %, 46;Z<CqGxH; ^)"b )0,u."3n79t?D H8Q %B)+05K8<8BCF<5: h )+ 3l9e;f B]Ge2 g $(]*,27 >A FH0  "\(3*/4::<>E-K{ $6'=)0+1"4K6<>?EG|*!>#'&  (.d06+9<AEI$3 ~ %']-10e14X E('C`# +,/1 9|<?cA,B Q6%$'+K,/M 79b?B.G- #'.(/18:?2DjG9k<Y} ,&4),2K56<CE Cs &( 146:AH7 ! &j(-{1TVm$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],canrg&s'gg'r,)gsg,r.gsg. pgNta "K)r] ~  g%*V,I24:sC Rv u#4&+u.0m58;B>?EFTH O}~, %')/1>3 L9I#& -/E05;;>c?FHIxM "$'.s3IxIx4 r:,IxIx;>DF'dr&" -04'9=+BDGOC >N m *A 13c7>BFA3^ &? -0l2%4!9 G>q/# ,N.0 6 =?CF~s; r0;;8  $s*x 1Y3 ;AC5Y@U#$*d,M3 7S=H@Fs2 r(220p'! '--/17i;<=@cAGE/R{m! (-/h18 ;>@CI-V7# *[-Q157:=J EH*SI!$) 048:>@HBG'@ %3')0*4/ :>LBE$Hy$ k $ !:R8 " , 4^6<BXEGy> # + - 58>>A^E 'r),0 98AD t` " (g).0f 7:;?Ej4 7C!n"%r(-6. 57O:;? GsT '$)P 1M4 6;>C}E$G k I %(;,1{4@ ;=(?FHs  rw !|& -:/ sB( BwrGe HATVm$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,hasbeendevelopedintheCedarrg%s&gg'r+gsg,vr-gsg./ pgMrb)t m"& ',.H2~6`DFYe"p&}*1-)0N28>?5 FVO&mV! )6-` 4w7?:T=@FHSS&@(,; 418H; BH Pv, %#'-K/1|4*7:? H7N F!%+/4"7=@KHftDl l"&r@r` "$G%)i,.1 8M ?F|H=m&* 157>iA8DFt; p!#&(f* 157:R?CF\8C! #~ -r 4c78<@BE5 ' !a%'^),1| !%a.Veu.V.V " *y0 79AXD+e r++ "$*-04|8m: >)D(e '[ .57W =CF&e7. $ -G24<:=@ H7#Peb";(C+ 3 79 eu)! (D+,-/247;r@A I@eq#,*-06>CE7e8z %V( .71~eu ]! (*h-4U r:< Eea_ & / 46.;u<B+Ge "u) 0)149;Q=B?D ]e 5 'K-0, 9:A e|d "$>)-m 47[;B DFTVm$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.rg%s&gg'r+gsg,vr-gsg./ pgMrb)e  %&)%-R0u39?DWE_ge\3 $* +E133 <ADeI\e" !'+)+~.14 ;>hDLYe VO  #), 47=9?CdHS`G o ')1-X 48; < D5PE $*6,2\4+:<AE^G#N A ! (:*x 0 Ju D9% ,: 48;F?BFGx= ##%k ,02m4: s@GGA7FYDrfDD( "%]*.38<9?BDIB1> J #y +.t17>;>pBH7?o Y #)C.z465:K=>CCH<^ "+(,.{2D7d=?AG|9,t!1#&,-3 658D7*3P (@+ 25C9p @C 0FF4#&+O,. 8r:6?EJF."%(*|.X56 > ?EF+P ;s"& ,;01W69;J?#E}HC(&"$: #M,/*39{<>@B-ET"8 "#)&n*+.L436 :9=@Gw I .!# * 28y:=DH s"&*>TVm$ TIMESROMANY TIMESROMANLAURELGACHAMATH TIMESROMAN TIMESROMAN TIMESROMAN TIMESROMAN TIMESROMAN HELVETICA  z !g(08@H OVj/Y WI []<>NewChap1 Tuesday, May 8, 1984 1:37 am PDT