12Chapter2DebuggersforAlgol-likeLanguagesThischapterdiscussesdebugginginmoredetail,layingthegroundworkfortheremainderofthedissertation.Thefirstsectionpresentsaprogramexecutionmodelthatcanformtheconceptualbasisforbuildingsource-leveldebuggersforAlgol-likelanguages.Thesecondsectionisauser-orientedoverviewofabroadrangeofpopulardebuggingfeatures;italsoshowshowaprogrammerusesthesefeaturestoanswersometypicaldebuggingquestions.ThisoverviewpreparesthereaderforChapter3,whichdescribestheeffectsofcommonoptimizationsonaconventionaldebugger'soperation.Inacompilation-basedenvironment,thecompilermusttellthedebuggerhowtotranslatethelow-levelmachinestateintosource-levelterms;thedebuggermustperformtheindicatedtranslations,interactwiththeuser,anddosomebookkeeping.Thethirdsectiondiscussesconventionalcompileranddebuggerimplementations,focusingonafewbasicdebuggingoperationsthatwillplayamajorroleintheimplementationportionofthisdissertation.ThissectionprovidesusefulbackgroundandcontrastforthedescriptionofNavigator'scompileranddebuggerimplementations.Thefourthsectiondescribesthepropertiesthatasource-leveldebuggerforoptimizedprogramsmusthavetobeconsideredeffective,anditdefinestwokeytermsforevaluatingadebugger'sresponses:"expected"and"truthful".Thechaptercloseswithabriefsurveyofthehistoryofdebuggersandrecentresearchdirectionsindebugging.Previousworkondebuggingoptimizedprogramsisdiscussedattheendofthenextchapter.pg/MqV'A0P4%r)z 4rI}&;'+/36- =@5BI5F+ $#/(q).59@;>mAD D- "),_ 3 :> C HIAR  %6)C+>07=?B.F~I> W-#%*.j3':. AE;@0#%y)/2t68> GI9    5xl (J*0W368i>lAiCH2:;"= *D/18f3N5 " ,13-5 =@E_'x $^') 13 ;xAD$!Y]y"% +\. / 6Dp &)+30259; BD   Y Al"D#'G+-05Z7W>(A#E - r$ ')0I6<>5D>EH7 TVm$CHAPTER2:DEBUGGERSFORALGOL-LIKELANGUAGES132.1Source-levelmodelofexecutionforAlgol-likelanguagesAprogramisastaticentity,whileitsexecutionisadynamicone.Thesemanticsofaprogramminglanguagedefinesasource-levelmodelofcomputationforprogramswritteninthatlanguage.Inhisproposalforadoptingafunctionalstyleofprogramming,Backuscharacterizedconventionalprogramminglanguagesquitesuccinctly[Backus78]:"VonNeumannprogramminglanguagesusevariablestoimitatethecomputer'sstoragecells;controlstatementselaborateitsjumpandtestinstructions;andassignmentstatementsimitateitsfetching,storing,andarithmetic....[AvonNeumannprogram]isdynamicandrepetitive.Onemustmentallyexecuteittounderstandit....Itsstatementsoperateonaninvisible`state'accordingtocomplexrules."Thesource-levelmodelofcomputationisacombinationofthat`state'anditscomplexrules.2.1.1Thesource-levelmodelOnewaytodefinethebehaviorofaprogramisviaasetofinput/outputpairs:theprogramtransformsagiveninputintoitscorrespondingoutput.Thisdefinitionisadequateforaprogram'suser,whowishesonlytoseetheprogram'sresult.However,aviewofthecomputation'sinternalstateisessentialforaprogram'simplementorormaintainer,whomustlocatetheproblemwhentheprogramfailstoproducethedesiredresult.Ontheotherhand,thismodelisnotintendedtocapturetheparticularsofamachine-levelviewofaprogram'scomputationalbehavior.Amachine-levelmodelwouldincludemanydetailsaboutanindividualimplementation,suchasthemachine'sinstructionset,thatdonotappearinandarenotspecifiedbyahigh-levellanguage.Thepurposeofthemodelistodefinetheviewofexecutionthatshouldbepresentedtoauserbyasource-leveldebugger.Thedebuggertypicallyconstructsitssource-levelviewofacomputationfromalower-levelrepresentationthatishiddenfromtheprogrammer.ThemodeldevelopedinthissectionwillbeusedinChapter3todeterminewhatthedebugger'sresponsetoagivencommandshouldbeatagivenpointinacomputation.ThismodelwasproducedbycombiningHorningandRandell'sviewofsequentialprocesses[Horning73]andthestandardsemanticsofAlgol-likelanguages.AlthoughtheresultingmodelisneitherasgeneralnoraspreciseasHorningandRandell's,itiswell-suitedfordescribingtheexpectedbehaviorofasource-leveldebugger.Amoreformaltreatmentofmuchofthematerialinthissection,thoughwithasomewhatdifferentemphasis,appearsinChapters3and4ofSatterthwaite'sdissertation[Satterthwaite75].rgPsNgg4r#_gsg$r%Egsg&d-.r0gsg1 r7gsg8pgMta "$-0 9rr]sEa .$(*1924T:'>5APGIZ ^".#i +/P1 9';vAF`H X!') /24 =B UQ  %)c s/UQUQ/r4UQUQS[ #*,2m498;q BGfQu1 !#')),U 4"6 = DIOFG %(*1h7p8>Ah GN&Y0g (),s 379;@DL8H E}6 '1() 13m6<:<>D3uC: +r><z%'Q(./1256 ?!BE`<: h " +03 :;eA6CfD9x7>i #").>4v58:< E6%/#9 +p-F 47;'?1AG93Bl #%',.1S48;j?ACI@14+  ! *.S0j18 BIb.r  $(-02 9pCFH+C !a#h%*d,.139N;I` Ds rD! e&( /! 6<?ZE%Ia?$ %+. 5688 ?YA H:a#V $+-v15;=AlC.Ey!O")o/Z5;:=.CEDGI5  sO r'? TVm$CHAPTER2:DEBUGGERSFORALGOL-LIKELANGUAGES14Programmersoftenenvisionaprogram'sexecutionbehaviorintermsofaprocessorinterpretingthesourcestatementsoftheprogram.Thisprocessorhasasetofstatevariables,whichholdvaluesofuser-definedvariablesandauxiliaryvariables(usedbytheprocessortoexecutetheprogram).Theprogram'sexecutioncanbedescribedintermsofasequenceofvaluesofthesestatevariables.Thissequenceiscalledacomputation.Anactionspecifiesthetransitionfromonestatetothenext:itassignsnewvaluestosomestatevariables;theremainingstatevariableskeeptheiroldvalues.Thefinalstateofafinitecomputationisastateforwhichnoactionisdefined.Acomputation'sactionsequenceisthesequenceofactionsperformedtogeneratethecomputation.Ingeneral,agivenactionsequencedoesnotcompletelyspecifyacomputation,becauseitcouldbeappliedtoseveralinitialstates.Aprogramisacompactdescriptionofthesestatetransitionsandtheirsequencing.Aprogramisexecutedbyaprocessor.Thestatevariablesofaprocessorinclude:9theprogramstatements,9theuser-definedvariables,and9asetofauxiliaryvariables,usedbytheprocessorforthebookkeepingnecessarytoexecutetheprogram.Theseauxiliaries,whichincludetheprogramcounter,theprocedurecallchain,anddatafromcurrently-activeprocedures,arediscussedbelow.InanAlgol-likelanguage,thetransitionfromonestatetothenextinvolveschangestoonlythevariablesandtheauxiliaries;thestatementsareconstantovertheprogram'sexecution.Thatis,theprogramcannotcreatenewstatementsandexecutethem.(ThisisnottrueofLISP,forexample.)Themostimportantauxiliaryvariableistheprogramcounter,whichidentifiesaprogram"portion"thatisabouttobeexecuted.Ingeneral,thegranularity,orlevelofdetail,atwhichaprogram'sexecutioncanbeviewedisdependentonthelanguagedefinition.Foralanguagethatspecifiestheexecutionorderwithinastatement,orforanexpressionlanguage(suchasBliss[Wulf+71]),itmightbeanexpression.Foralanguagethatdoesnotspecifytheexecutionorderofexpressionswithinastatement,thegranularitymustbestatementlevelorhigher;inthetypicallanguageastatementisareasonableprogram"portion".(MostAlgol-likelanguagesdefine"statement"recursively.Thereforetheexecutionofacompositestatement,suchasaloop,generallyimpliestheexecutionofseveralnestedstatements.AmorecompletecomputationalmodelforAlgol-likelanguagescouldalsomarktheendofexecutionofeachcompositestatement.)Theremainderofthediscussionassumesstatementgranularityunlessotherwisenoted.rgPsNgg4r#_gsg$r%Egsg&d-.r0gsg1 r7gsg8pgMrb) f"#*0573:_g_g?CF\ !N',025%;M=BDY 6 "(*Z./068l<>:AD W#PGvqW#W# r%W#W#SvSSrSB U &*,0+14s89>:AEEG[PF @!%X+F.2D4:Q=\@D#FvGkPPGrN  Q#&&*j,243 vex?or?o?o|v ?o?or$?o?ow;ex?CEI S  $&6-/1t7@ >sA$BTH 3!&'| .F0F24 ;AEGs r  u &;(*/258M<?JEI5K < "% ,%/18 ;n=OB5DF}{ C 'f-I 5 9c @F [ $#&d,|./#5 ;? @AEX#M' /1]5;' DQH E m"&)+-4E6)9@4 H z3 %a+ 26< "TVm$BCHAPTER2:DEBUGGERSFORALGOL-LIKELANGUAGES15Withtheexceptionofdynamically-allocatedvariables(whichcanbehandledbyasimpleextension),auser-definedvariablecanbethoughtofashavingaconceptuallifetimethatextendsovertheentirecomputation.Eachvariablehasatype,whichspecifiestherangeofvaluesitcanassume.However,asinglevariableidentifiercanrefertodifferentvariablesatdifferentpointsinacomputation.Anenvironmentisamappingfromidentifierstoasubsetofthevariables.Ifagivenenvironmentassociatesapreviously-usedidentifierwithanewvariable,theoldvariableisinaccessibleinthatenvironment.Algol-likelanguagesarestaticallyscoped,meaningthattheenvironmentisafunctionofapointintheprogramtext(i.e.,theprogramcounter).Incontrast,mostdialectsofLISParedynamicallyscoped,meaningthattheenvironmentisafunctionofthepointinthecomputation.Variablebindingisarelatedconceptforthehandlingofdynamically-allocatedvariables.Algol-likelanguagespermitrecursion,implyingthatmultipleinstancesofaparticularvariablecanexistatthesametime.Foragivenidentifier,thecorrectinstanceofitsvariable(i.e.,thebindingoftheidentifier)isafunctionofthehistoryofthecurrentlyactiveprocedurecalls,thatis,theorderoftheiroccurrenceandtheirdata.Atagivenpointinacomputation,statementsinanAlgol-likelanguagecannotrefertoadifferentinstanceofavariablethanthatspecifiedbythebindingrule.Toimplementthebindingofnon-localvariables,theprocessorkeepsahistoryofthecurrentlyactiveprocedurecalls,calledtheprocedurecallchain,aspartoftheauxiliaries.Atprocedureentryandexit,theprocessormanipulatestheseauxiliariestomaintaintheproperbinding.Therefore,thesource-levelviewofacomputationinanAlgol-likelanguagecanbecompletelydescribedbytheconstantprogramtext(T)togetherwiththesequenceofvaluesoftheuser-definedvariables(V),theprogramcounter(PC),andtheprocedurecallchain(C).Thesearetheitemsthattheuserwillwanttoobserveviathedebuggertomonitortheprogram'sbehavior.Thefirstlineofthefollowingfigureshowsafully-specifiedfinitecomputation.Thesecondlineshowsthatthetransformationfromstatesitoitssuccessorsi+1iscausedbytheexecutionofthepieceofprogramtextatPCi.<<{T,V0,PC0,C0},{T,V1,PC1,C1},...,{T,Vn,PCn,Cn}>>T(PCi)[{T,Vi,PCi,Ci}]={T,Vi+1,PCi+1,Ci+1}Notethatthelocationofthestatementthatisabouttobeexecuted(i.e.,theprogramcounter)isanexplicitelementofthecomputationalstate.Therefore,acomputationthatexecutesthesameactionsonthesamedata,butthatusesdifferentcopiesofthoseactions(i.e.,actionsatsomeotherrgPsNgg4r#_gsg$r%Egsg&d-.r0gsg1 r7gsg8pgMrb!WW E-38;P=vBE*F__  $=&(-/1f57 >CE\tl v\r![\\"B$*,v-\\.Er06\\159:=*ABGHcYv%YY%rY*-e02l8=?pEI@W! !vWW$ rW#L$& +/X 578=*>Am H.ITY  ! "H,0 265e69?GAD8IQ v $ +24 :?EHN j " %'f)/b2 547=0CEiLI> &+1A46 >@AGFHIS/ EvqEE!rEG$),|/$5)7+D B > &H, .4N:;< C/Hc@:  6!`% +`-2R79Y;4@kCxE=x9 O"0$ &+8-/59@8CFH: !!%l)+- 0467 @I G*H7 fQ#h%;&,U134:O=@FnH53 $!#(*0 69@?hCRDI52rO:4!%9)>v+2r2r,[14r72r2r8:V=G?A{ H/EP4 s&f -1\ 79K>A%E, O "%L&( 013 9?BC )Y+#&x')Yr)Y'(.-133~9R:?@C &x&r&'x#x$d&&%<r&&&&'[*,U25F8x9g&r&:>;?B4DH #KMh !4#{%+-25a;BuEVH8!  !">+). 7:p?AEHS \xbS y :rS!#%x+S y ,rS/[057:y@BEjI5q(xyKqrxyBx`yBxyBDxxyB"x#yB& x&yB(ix)+.0yB4 x4yB7Ax7yB9x:J9Syx9`yox9yx9 Py"x9"%4&y*Dx9,Jy.x90y2x94r "L #K)t,5-1i3 4:=?EtE,& - )'-" 34 <?EGq z{M!!#&,02\5:=B.CGO ZTVm$CHAPTER2:DEBUGGERSFORALGOL-LIKELANGUAGES16locationintheprogramtext),isadifferentcomputation.Foreaseoflaterreference,weinformallypartitionthemodelintothreeparts:locations,data,andhistory.Thelocationelementsofacomputationaretheprogramcounterandtheactionabouttobeexecutedatsomestateinthecomputation.Thedataelementsofacomputationarethevariablesandtheirvaluesatsomestateinthecomputation.Thehistoryelementsofacomputationrefertothesequencingofcodeordataelements,suchastheprocedurecallchainorthenumberoftimesthatagivenactionwasexecuted.Thissource-levelmodeliseasilyextendedtohandlemultipleprocesses.Eachprocesscreatesaseparatecomputation,withitsownprogramcounterandprocedurecallchain.Variablesandprogramtextcanbesharedamongmorethanoneprocess.[Wearenotinterestedinmethodsforinterprocesscommunicationhere.]2.1.2Behindthesource-levelmodelThissource-levelcomputationalmodelisanabstraction;anexecutingprogramdemonstratesobservablebehaviorthatisoutsidethemodel.Furthermore,theactualsequenceofstepsrequiredtoexecuteaprogramonacomputerismuchmoredetailedthanthismodelsuggests.Topresentasource-levelviewofacomputation,adebuggermustmapthesedetailsintoacorrectsourceviewanditmusthidethepartsoftheimplementationthatareextraneoustothesourceview.Aprogram'scomputationalbehaviordoesnotincludeanyencodingofprogramoroutputtiming,dataorprogramstorageparticularsthattheusermightbeabletodeducefromtheprogram'sphysicalbehavior,oraudiblecuesfromspecifichardware(suchasdisks).Theseandothersimilaritemsarenotdirectlyspecifiedbythehigh-levelspecificationoftheprogram;rathertheyareimpliedbythelow-levelimplementationoftheprogramminglanguage,theoperatingsystem,thehardware,andsoon.Thedefinitionofcomputationalbehaviorconstructedhereexpresslyavoidsdefiningallsuchbehaviorsoastoavoidconstrainingthelow-levelimplementation.AcomputercoulddirectlyexecuteaprogramwritteninanAlgol-likelanguage,eitherbyinterpretingitorbyhavinganinstructionsetthatimplementedthelanguage.Forefficiencyandflexibility,ahigh-levelprogramisusuallytranslatedintoalower-levelrepresentationthatismoresuitedtotheparticularmachine,frequentlythenativeinstructionsetofthemachine.Thistranslationisperformedbyacompiler.Ofcourse,aprogram'sexecutiononanactualcomputercanbeviewedatmanydifferentlevels:thesequenceofprogramstatements,thesequenceofrgPsNgg4r#_gsg$r%Egsg&d-.r0gsg1 r7gsg8pgMrb!&!>"#)z ^J= "b$ +,037P:#=A G[$j&'* /1U39!>@CG Y`!i#9% .14:<= FHVG1f #&(E* 3F6 :@5AB S9R u4"$J'U-n02Y4;G=AC]EPE= "M. G !%+-J17I >"AFgJm) !F#>&_, 1)3:=FBH7G^{X$'*-Js2bGG246x8` =Z>CD D u? d< $-r: h %z)+>-> 46<B 8< ]#$H&+ 46r:m@MAE^5zGO{%'*.369=CF2 ~Yv %&,033A6;=>CpG/Xr: #R -1/2S 98:=FA,b\ ##),].4 6<>DF|)sWh! (+?-}0U4,58:a>BED&)+ #'7,257i<$@BFi$C"%+' .O 6d8O:AEYH!\dI (1),] 4;!=CHF %' 06K =@FP@q" "$B( /2#7C`"()Z/357 >DH h " (+ - 678?KA H7 h "$( /13 : CEG[=9 h$ +./2 9<'>-@G = * !8'*./6e<>@D {xy$U(+e13s98 @CI5TVm$CHAPTER2:DEBUGGERSFORALGOL-LIKELANGUAGES17machineinstructions,thesequenceofstepstoperformeachmachineinstruction(oftenintheformofmicrocode),thephysicalbehaviorofthecircuitsinthemachine,etc.Thesource-levelviewisthusonlyoneofseveralpossibilities;ithastheadvantageofbeingtheviewformulatedbytheprogrammer.Acompilertranslateseachsourcestatementintoasequenceoflower-levelinstructionsthatcarryouttheactionsspecifiedbythestatement.Thereareusuallymanydistinctwaystoaccomplishthesesameactions;whichonethecompilerchoosesdoesnotaffectthedefinitionofprogrambehaviorwehavealreadyconstructed.Thecompilerfrequentlyusestemporarystoragetoholdintermediateresults;whereandhowmanyofthesetemporariesexistisimmaterialtotheuser.Thecompileralsoselectsparticulararrangementsofstoragetoholdvaluesofuser-definedvariables.Forexample,mostusersarenotconcernedwithwhetherarrayelementsarestoredbyroworbycolumn.2.2OverviewofdebuggingfeaturesAninteractivesource-leveldebuggercanbeusedformanydifferentpurposes,dependinguponitscapabilities:debugging,development,testing,andperformanceanalysis.Debuggingistheprocessoffindingandfixingprogramerrors.Programdevelopmentistheprocessofaddingnewfunctionalitytoaprogram.Programtestinginvolvesmoreorlesssystematicexaminationofexternalprogrambehaviorusingvariousinputs;performanceanalysisexaminesinternalprogrambehaviorusingvariousinputs.2.2.1MonitoringacomputationAsinglesourceprogramrepresentsapossiblyinfinitenumberofcomputations,correspondingtodifferentinitialstates(i.e.,differentinputs).Iftheprogramtextcontainsnobranchesorprocedurecalls,thenitspecifiesexactlyoneactionsequence,whichcontainsthesamenumberofactionsinpreciselythesameorderastheprogram.Butevenasingleactionsequencecanrepresentmultiplecomputationsfordifferentinput.Iftheprogramtextcontainsconditionalbranches,theprogramspecifiesmanydifferentactionsequences,dependingontheprogram'sinput.Iftheprogramcontainsloopsorprocedurecalls,thesequenceofactionsexecutedforagiveninputcanbelongerthanthetotalnumberofactionsintheprogram.Whenaprogramfailstospecifyaterminationcondition,theresultingcomputationsareinfinitelylong.AnalyticallydeterminingthergPsNgg4r#_gsg$r%Egsg&d-.r0gsg1 r7gsg8pgMrb!Z X$3%);*0(3L8 ?CE4G__ .%'l).0U28;> F>I\?  &'*-359j;?C FtHY VGO( P"' -a0X179 @ H SB[ "% +/2 6:K?B@C PJ"%>+*0f36m:i< CvE`NZK '*0 7I:`A!EGK@  -# &3*#,/ 7T:<; CEEGH; $) ,.%24K7^;o= D Euf #E)-2h5;>!BPDWG#HBt<^Y%r8< t !'*I,!/D1i5:@GZ5z  4 ).1 9Kv?5z5z@r5zFH2V! &+v10221 r28:Y<ACdH/ U^v%//%rr/)7.n135 *tTu$  r $H 'B(`-2^79, A "&( ./2r8A;9@C#I*kb"'*6.U48>@DI5Ch I#%'.0348<B|De 3$){+-o35;5 BfHUU$1( /y6t8;EAFHrH%)5+13:7=?ADHc =O P#%n*'+.m59E:@7CAE I { H $ -4/ 5\9J @ H:TVm$XCHAPTER2:DEBUGGERSFORALGOL-LIKELANGUAGES18sequenceofactionsandstatesthatarisefromagiveninputisatbesttedious(forsimpleprograms)andatworstvirtuallyimpossible(forcomplexones).Infact,themajoruseofadebuggeristohelpprogrammersmonitorprogrambehavior,topinpointwhereinacomputationaprogrambeginstostrayfromitsintendedbehavior.Adebuggerthatcanmonitoracomputationcanhelpauserwithdebugging,testing,andperformanceanalysisactivities.Theimportantfeaturesfordebuggingarethefollowingbasicoperations:reportingthecurrentexecutionpoint,displayingthevaluesofvariables,settingandfieldingbreakpoints,anddisplayingtheprocedurecallchain.Fortesting,adebuggercancollectinformationforstatementexecutioncountsordatausecounts,toensurethatallcontrolpathsanddataconfigurationshavebeentested.Executionsummariescanalsoisolateprogramareasthatmightprofitfromtuning.2.2.1.1BasicmonitoringfunctionsThebasicmonitoringfunctionsofadebuggerincludeexaminationcommands,whichdisplayinformationaboutasinglestateofthecomputation,andcontrolcommands,whichspecifythesetofstatestobeexamined.Foraninteractivedebugger,thecontrollingcommandssuspendandresumethecomputation,sothatthesingle(current)stateisusuallythelaststatethathasbeengeneratedsofarinthecomputation.Thesearethebasicexaminationcommands:1.Reportthevalueofthecurrentstate'sprogramcounterinsource-levelterms.Thisfunctionreportswhichsourceprogramstatementinwhichprocedureiseitherexecutingorabouttoexecute.2.Displaythevalueofavariablevinthecurrentstate,intheappropriateformatforthedeclaredtypeofvinthatenvironment.InanAlgol-likelanguage,thecurrentprogramcounteruniquelydefinesanenvironment,orasetofvisiblevariables.Theeffectofthisfunctionisasiftheprogrammerhadincludedastatementtoprintthevalueofvintheoriginalsourceprogramatthevalueofthecurrentstate'sprogramcounter.Withtheaidofanexpressionparserand/orinterpreter,adebuggercanusethisbasicfunctiontodisplaythevaluesofexpressions.3.Displaythevalueoftheprocedurecallchaininthecurrentstate(alsocalledtheproceduretraceback).Thisfunctionreportsalist,usuallyinreverseorderofinvocation,ofthenamesofthecurrentlyactiveprocedures,theirpointsofsuspension(i.e.thecallingstatement),andpossiblytheirargumentsandlocalvariables.4.Setthevariableenvironmenttosomeotherprogramstatement.ThisfunctionisdefinedrgPsNgg4r#_gsg$r%Egsg&d-.r0gsg1 r7gsg8pgMrb!g!F$'3*+/M24H58=c@ Db__Z" #&Q+02y58<>@fAGI@\ )M$*,:15788E @!A.FYI#VG_M$& .>04A58< CKH7S #u #q&-$25;>A,G{P *I#* .$ 47R;=| CH7N  %!'.05K7<=D FK@ f$)R+.0~5+6;3=?DH7H &"',-47t:d>DH Ez@0 r<  %&&(.'3 :B'F<9 nSl"$[& /16=AFpH7!l"$ +2#4 ;BH74`I  #& */3C49<>BDG1-& . X %+Ge]!(#%*n.4M9o;? BG)e"',248?T@D&e) $eH "#x($r$*E+.E3682: AFXH!e x!r! 5!$ -/1 7>$@E`eg$#% .<01,3J59T ?BFHMeUm (+u1!2O8:==@CxE{rFHKef#1$'*,f.3}7=BFDHeU| k#( 01a7:b=?CI@ew!^  e+p !#&{-8/358n=r@D]Hver 6 "%A*/r03A79>kB'C efL &r*S 148: AD5F e l$#p&-f03c e\w 'j(,s/5i CF%]e;!$X -21+248:=1BDHF[eWX"~U5e % -2$v3NU5U54 62r;EU5U5;Rse %'t+048v9RsRs:lr?RsRs@CFOe> L  & / 3~5;?AfGI[| h &(D.\2> :?1CE_FC4 (!#-(.026A8>B'FH@C4p!'7,$0U38=B DW=  #&K .3/64:q<BDF:F!#' )"0 7;BG7\%y s,77-> r2774i  $,C15+9l;9=COHc1 #!#&V) 2l85<@@AmGI5.- &<*Y.03w7<?B5 I5,$s . "c'*j,047c AsC^D )b -r%!*0 28:=>AG& %;(+/4:2 A$ H #jO (I),M0492< CG!= "?%'*- 0F5&6[ =X?jAD\I #")z-2 4}86;`@ GI  '$v', .'1W38;:=?ABC  $'*C.38v >cAmB  , "% ,s/0pr23s4r7z"0 r  &)~+/258 ? G > &K,u 369 @'C! qTVm$CHAPTER2:DEBUGGERSFORALGOL-LIKELANGUAGES20assertion-drivenbreakpoints,andconditionalbreakpoints.Adumpisalistingofprogramvariablesandtheirvalues.Afulldumpshowsallofthevariables(includingdynamically-allocatedvariables)andtheirvalues,andislikelytocontainmoreinformationthantheusereitherwishestoseeorcanreasonablyabsorb.Afulldumpismostcommonlyprovidedafteracomputationhasterminatedabnormally,whenitiscalledapostmortemdump.Aselectivedumpshowsaspecified(andtypicallysmall)subsetofthevariables.Atraceshowsthecompletesequenceofstatesofsomefinitecomputationorsubcomputation.Itcanshowavaryingamountofinformationabouteachstate.Anactiontraceshowsthesequenceofactionsthatareabouttobeexecuted(i.e.,thevalueoftheprogramcounter,eitheraloneorwithitstext)ineachstate.Aresulttraceshowsthesequenceofactionstogetherwiththeirresults.Afulltraceshowsthesequenceofactions,includingthevaluesofvariablesthatarereferencedineachactionandtheresultsoftheaction'sexecution.Anotheraxisuponwhichtheamountoftraceinformationcanvaryisthegranularityofthetrace.Tracingwithfinegranularityshowstheexecutionofeveryactioninthesource-levelcomputation.Tracingwithmediumgranularityshowstheexecutionofeverybranchpoint,whichisanactionthatchangestheprogramcountertosomethingotherthanthelexicallyfollowingstatement.Tracingwithcoarsegranularityshowsonlyprocedurecallsandreturns.Afulltracewithfinegranularityofanentirenontrivialcomputationgeneratesmuchmoreinformationthanafulldump,andisthereforelikelytobehardertouse.Satterthwaite'sideaofthek-limitedtrace,implementedintheAlgolWdebugger,limitstheamountofinformationproducedbysuchatraceto(approximately)ktimesthesizeoftheprogramsource.Ittracesthefirstkexecutionsofastatement,exceptthataprocedureistracedthefirstktimesthatitisinvokedfromeachseparatecalllocation.Whenkisgreaterthanone,theintuitivebasisforthisideacomesfrommathematicalinduction:thefirsttimeastatementistracedformsthebasisstep,andthesecond(orkth)timeshowstheapplicationoftheinductionsteptothefirst(ork-1st)time.Tosingle-stepacomputationmeanstowatchitexecute.Thedebuggerstopsthecomputationbefore(orpossiblyafter)everystatementisexecutedsothattheusercanexaminefeaturesofthesequenceofstatesindetail.Itcanbethoughtofasenablingabreakpointateverypossiblesuccessortothecurrentstatement;whensomesuccessorisreached,allofthebreakpointsareremoved.Sincethe"statement"unitisrecursivelydefinedinthesourceprogram,thenotionof"successor"hasseveralpossiblemeanings.Forsingle-steppingwithfinegranularity,thesuccessorrgPsNgg4r#_gsg$r%Egsg&d-.r0gsg1 r7gsg8pgMrb) #[ * ^vb^^r^KD x&9,%/27v9^^:!IB)vC Ov)OOrO"(*U./3B6 >@M6I<U.!(" *J.1<5(v7kM6M68;lrM6>BEJtpZ "(w+.1362;AREZI*Gv!+GG!$rG(-,/.4a6:?C FGDvnDDrDCP"$P)E/Y157=Z@(B| I@B/ A #8( /4k7:>@EG?n vo! (I*A,v1?n?n26:= r?nDCH<u 1" * v2<<37:? r>DI@7){-#) v07)7)158< r7)CG4het+0Q| &(*. 5 =9CcG[. vn!$& +/1}3w79=F2I5+Ov+O+OJr`+O+O~ $&(,.5n9{<AiCd (1[ hv*](r(+/S14_68y>C5DH%v%r% ~"6 "&)*1#2y68v;%r%<@]CDWE# 7V#v' # r# (B).%194+6x;?AJCF Hp  !$['[*+2T382BNEHtvrx"= )O+-h36v8%:=\v?@`rABC{vH rOr #f')K-<.4P7!=$@B /5u~"6(o)/1f4869<&AFHn!#&E(m-/17k8 ?AEsm %L)1,34:]<}>f@ HR #g&Z' .358AYb y%(*/d4=79i;@OFHW "#V$* 2^58; CEIT^T L=!U$&K) Pt # ),6 =@ H7NQJ $ +m. 5J <AUCI@KF G>%v GG!e'rG+j/168<?BI*D;O!$(r 0B1#?AE<S RG%(e,-3:!< D49 U#o(B,9v.*99.4E73rABHC3P[{("%&)q.X/25E:>/@DF0M!#&C,90_5@@G9'j r&&)/24 =1@| H7$ !#$% . 58v:{> A2E"5* $'+/2+8R= Ds"~v#ss$ ( r/ssv4= rn"$& -48:m=Bc I5 "P%$'-1579<C EI5[Q1!0$&})+/2J 8l<%=BBCDI5u"7& )n+/.46:j?BDT$B&*K,.d35 Bvs B B  r B!#^%+-/\47W; BLD>H _!"$'*2/46f;=@'E^F ]TVm$CHAPTER2:DEBUGGERSFORALGOL-LIKELANGUAGES22oraccessed)andtheexecutionstateoftheprogramsatisfiesaspecifiedcondition.Thevaluesofvariables,theprogramlocation,andsomeelementsoftheexecutionhistory(suchasvaluesintheprocedurecallchain,statementexecutioncounters,ordatausecounters)maybelegalcomponentsofthiscondition.Anassertion-drivenbreakpointcausesthedebuggertogivecontroltotheuserwhenevertheexecutionstateoftheprogramsatisfiesaspecifiedcondition.Itdiffersfromaconditionalbreakpointinthatitsconditionisevaluatedateverystate,whileaconditionalbreakpoint'sconditionisevaluatedonlyinthestatesspecifiedbytheprogramcounterorvariable.Notethatifanassertion-drivenbreakpoint'sconditioncanrefertothevalueoftheprogramcounterortheaccessofavariable,thenalltypesofbreakpointsarespecialcasesofassertion-drivenbreakpoint.Anyofthesebreakpointscanbeextendedbyallowingtheusertoassociateadebuggingprocedurewiththebreakpoint,toexamineanddisplayelementsoftheexecutionstate.Thesebreakpointsarecalledprogrammablebreakpoints.Ideally,anycommandthatcouldbeenteredinteractivelytothedebuggercouldalsobespecifiedinadebuggingprocedure.Thusaprogrammercouldconstructaspecialtraceroutine,forinstance.Finally,thedebuggercouldrecordsomeorallofthedataandlocationchangesinacomputationforlateraccessbyvarioushistorycommands.Forexample,ahistoricdisplayoftheexecutionpathofaprogramiscalledaretrospectivetrace[Johnson82a].Thisinformationcanberecordedatvaryinggranularities.Possiblegranularitiesforretrospectivetracesinclude:alistofrecently-executedstatements,alistofrecently-executedbranches,andalistofrecently-executedprocedurecalls.Foratypicaldebugger,theprimaryformofretrospectivetraceistheproceduretraceback,whichliststheactiveprocedurecalls.Notethattherecently-executedprocedurecallsandtheactiveprocedurecallsareincommensurate:somerecentcallsmayhavecompleted,whilesomeactivecallsmaynotbeatallrecent.Itisrarerforadebuggertorecordoldvaluesofvariables.Itisimportanttonotetwobasicfacetsofdebuggerusehere.Somedebuggingactivityispreplanned.Thatis,theuserspecifiesinterestinagiveneventbeforeitoccurs.Forexample,breakpointsandtracesrepresentpreplanneddebuggingactivity.Incontrast,otherdebuggingactivityisunplanned.Programexceptions,userinterrupts,andproceduretracebacksfallinthiscategory.Inmanydebuggerimplementations,thedebuggercangivemoreinformationaboutpreplannedeventsbecauseitknowsaheadoftimetocollectrelevantinformation.Similarly,preplanneddebuggingactivitynecessarilyoccursatthedebugger'simplementationgranularity,rgPsNgg4r#_gsg$r%Egsg&d-.r0gsg1 r7gsg8pgMrb!vb!b!]rb!Z"%<&)h/45H; BDI5__ U"s%+(.y0228=YABFH\\" (9. /25/;$>@CB Y< VFv VFVF rVF$(+X1u386:;<?8BFHS!&& ' , 3H48;< C P n$&m*f.52/3 ; CIN\p!u'),y2W79@kD1GNHK@ &);,.104158@=BDFH~Szj! ),+/3m5&? D "B%'0-Q/5B7; <BD5B'S "$*7-179<6BF?e v?e?e & r,?e?e.36j<?CE< c R$&(.-/07o >AC 9<!&(6M"=&c)+g-..036^;l@oAB 3,.v33#@r)[33*-B34%8=?KAG0%jv00 %0s0( r.00/2 :r<>D|F.  %(* 0w4:-;>@+F #%+.P/g138>D~HC(W"&' /3947= DH,%)h#"%7'~2O8;>P@Dk#G"&),0$ 7-:>wBdEtHy @k[[>!#) */1r57Y @X, l#=&*,25y9=DIv r>B%!'U,S. /i3<7;~<BSE' # +h2a8:@VD5fvUffr\ff" ), 36=5 CFHM!,/f58c;?N G  ^ 4!&H*,/16Z; D ! \R"W )m-/2^ 9 C  TVm$CHAPTER2:DEBUGGERSFORALGOL-LIKELANGUAGES23becausetheusercannotspecifyotherwise.Incontrast,unplanneddebuggingeventsmayfrequentlyoccuratprogramlocationsthatarebelowthelevelofthesource-levelmodel.Thedebuggermustreporttheselocationsintelligibly.2.2.2SampleusesofsomemonitoringfeaturesToconstructaprogramthatembodiessomefunction,theprogrammerconstructsaseriesofstepsthatareintendedtotransformtheinputintotheoutput,littlebylittle.Inthepopulartop-downprogrammingmethodology,theprogrammerdecomposesthedesiredfunctionintoaseriesoflargesteps,thendecomposeseachofthesestepsintoaseriesofsmallersteps,andsoon,untileachstepisalegalstatementinthechosenprogramminglanguage.Asaresult,theprogrammerisfamiliarwiththeprogram'sstepsanditsdatastructuresastheyappearintheprogramtext.Itisadebugger'sresponsibilitytocommunicatewiththeprogrammerinpreciselytheseterms.Forexample,theprogrammerfrequentlyassociatesassertionswithspecificprogramsections,suchas"thevalueofyisnon-negativehere",or"thevalueofxismonotonicallyincreasinginsuccessiveiterationsofthisloop".Theseassertionsmaybeexplicitlystatedintheprogram(asspecialassertionstatements[Sites72]orsimplyasteststhatprintawarningmessage)ortheymaybeimplicit,appearingonlyincommentsorintheprogrammer'smind.Adebuggermustreportthecurrentexecutionlocationandthevaluesofvariablescorrectlytohelptheprogrammerverifyimplicitassertionsofthiskindduringtheprogramcheckoutprocess.Aprogrammerformulatesquestionsaboutthecomputationalbehaviorofaprogramandthentranslatesthequestionsintotheavailabledebuggingcommands.Thefollowingexamplesshowspecificquestionsthataprogrammermightwantanswered,asopposedtogeneralquestions(suchas,"WhydoesthevalueofxdifferfromthevaluethatIexpectedatthisprogrampoint?").Asophisticateddebuggermightbeabletoanswerthesegeneralquestionsdirectly.Questionscorrespondingtolocationbreakpoints:1.Whatisthevalueofvariablexbeforeaparticularassignmenttox?Toanswerthisquestion,aprogrammerusuallyplacesalocationbreakpointontheassigningstatement.2.Whatarethevaluesofvariablesusedtocomputethenewvalueofx?Again,thelocationbreakpointisusuallyplacedontheassigningstatement.3.Whatisthevalueofvariablexafteraparticularassignmenttox?Inthiscase,aprogrammerusuallyplacesalocationbreakpointonthestatementfollowingtheassigningstatement,becausemostcurrentdebuggersdonotallowausertospecifythatabreakpointistooccuraftertheexecutionofastatement.rgPsNgg4r#_gsg$r%Egsg&d-.r0gsg1 r7gsg8pgMrb)/o! (*w/6=BAaDK _g.j"2$~(*./2' 9>AG\J uVDH" *rR #)-i3L5 = D,EfI5O{y&D(,/2H7B:<A=C=EM6N  &) 1 9q<AFIJuX~ &C)s++.2469;@WDFHGz0h&(+40 8@>BDHD !B#*x.136N <>AFHB047q #g +- 6*9U; CvEuB0B0F%?o^r?o?o" * 0 6 =:@eE`<W!Dx#@<r<$& /3g5n8<x><r<@IA 9 p5  #%(U-51N 7:< BFH7*m  s'l7*7*'r7*+-2369<>C]I*4h"S%[&-s/%03 ;@AG1b* ^%(I*.06D;=@C .  "g%*,h17+P*  !'+. 7<>k?EG(  #K)*08;ADGf% %)-3~5-:/4:C 9% AKx$r&>'*+ 1 8x:r<K1W!|" */:3R4|9 @BE1 p) p&+)g+036 9xp;r=opp;1+ %&+:/139 AKx$r&>&)y* 0 7x9r; 1.o #i(3,c-2 9<>D +1 !+&Z).547G9=>ACvH  1Z Kev!& !r $Y&,./  ,TVm$ CHAPTER2:DEBUGGERSFORALGOL-LIKELANGUAGES244.Whatarethevaluesofsomevariables(otherthanvariablesassignedorusedinthisstatement)atthispointintheprogram?5.Howmanytimesdoesexecutionreachthispointintheprogram?6.Bywhatcontrolpathdidexecutionreachthispointintheprogram?Theresponsetothisquestiondependsonthegranularityofthedebugger'slocation-orientedhistorycommands.Theproceduretracebackrepresentsthecanonicalgranularity.Questionscorrespondingtodatabreakpoints:1.Whereinthiscomputationisthevalueofvariablexaltered?2.Howmanytimesisthevalueofvariablexaltered?3.Whatarethevaluesofsomeothervariableswhenthevalueofvariablexisaltered?4.Whereisthevalueofvariablexused?5.Howmanytimesisthevalueofvariablexused?Questionscorrespondingtoassertion-drivenbreakpoints:1.Whereinthiscomputationdoestheprogram'sexecutionstatesatisfythegivencondition?2.Howmanytimesdoestheprogram'sexecutionstatesatisfythegivencondition(whenthepreviousstatedidnot)?Aquestioncorrespondingtotracingorsingle-stepping:1.Whatcontrolpathdoestheprogramfollowforthegiveninput?Thisquestioncanalsobeansweredwithlocationbreakpoints,butthatmethodismoreworkfortheuser.2.2.3ModifyingacomputationManydebuggerspermittheusertomodifyaswellasmonitoracomputation.Thissectionbrieflydescribestherangeofmodificationfunctionsandtheiruses.Thesefunctionsarediscussedinlessdetailthanthemonitoringfunctionsbecausetheyaresomewhatlessimportant,bothfordebuggingandforthisdissertation.AlthoughChapters3and4considertheeffectsofoptimizationonsomemodificationfunctions,theimplementationportionofthisdissertationconcentratesonthebasicmonitoringfunctions.Adebuggerthatcanmodifyacomputationcanhelpauserwithdebugging,development,andtestingactivities.Theabilitytoassignavaluetoaprogramvariableorreturntoapointintheprocedurecallchainwithareturnvaluecanacceleratedebugging,allowingaprogrammertogetaprogram'sexecutionbacktoitsintendedstatesothatfurtherprogrammingerrorscanbediscoveredduringtherestofthatcomputation.Adebuggercanbeusedforinteractiveprogramdevelopmentifitallowsausertoassignvaluestovariables,callprocedures,orcreatenewvariables,statements,orprocedureswhenevertheexecutionoftheprogramissuspended.AdebuggerthatrgPsNgg4r#_gsg$r%Egsg&d-.r0gsg1 r7gsg8pgMrb!9S#w)-"045;@<@AD? `y"bp^Es= &L*,0B14P\2Ah!(+.i236Y1Z$)+.] 5X79o @TX41!['- 46< TC 9" Rk? "$F&*O,xRk1r3BRkRk3P6s=S $\&xP6+r-OP6P6-N) p$'-]13q78xN>^r@NN@qAzK\xK%Ir&KK'Is=S $\&xI+r-OII.FC 9) C? "& (j.5 8<B~ A5d #3)03c7:/>DAH?I<]o  %5&:) #?(-/C15W71G[ $"(+-0` 8*:=rBzCGq6M1nu0) r,aT #Q&a(&,.138: C!FR)A#|@ (.148<BD&bK $F*b/25B;> EWH$&L $*014Q5o:=ASB ![   #_% /469 @ HA  #]# $) ,.1258 ? H7B[ !<"'(Z,-/4:;@ACFHr  -$i(!* 1 82=> FHZ!,#(%Q+[.04 8 AF$H 8O!# ,.p479<]> E` < B!#'+&, 25) BD z  % 's-/n17i8 @~BH UTVm$CHAPTER2:DEBUGGERSFORALGOL-LIKELANGUAGES25allowsprocedurecallsandtheassignmentofvaluestovariablesaidstheprogramtestingprocessbyallowingeasycheckoutofindividualprogramcomponents.Thebasicmodificationcommandsare:1.One-timedatachange.Assignavaluetoavisiblevariable.2.One-timecodechange.Executesomestatementintheprogramminglanguage,includingabranch,anarbitraryprocedurecall,orareturn.3.Alterthedata.Declarenewvariables,eitherforthecurrentenvironmentorforsomeotherenvironment.4.Altertheprogram.Insertnewstatementsintheprogram,eitheratthecurrentprogramcounteroratsomeotherpoint.5.Alterthecomputation.Restorethestateofthecomputationtosomepreviousstate,sometimescalledreverseexecution.Whenadebuggerallowscomputationmodification,itsprogrammablebreakpointscanbemorepowerful.Aprogrammablebreakpointthatmodifiestheexecutionstateandthenresumesprogramexecutionwithoutuserinterventionactsasaruntimeprogrampatch,andissometimescalledadvisingaprocedure,programpoint,orvariable.2.3ConventionalcompileranddebuggerimplementationsTosupportinteractivesource-leveldebugginginacompilationenvironment,aconventionalnonoptimizingcompilersuppliesthedebuggerwithmappingsbetweensourcestatementsandobjectcodelocations,andamongvariableidentifiers,types,anddatastoragelocations.Assumingtheexistenceofthesetwoabstractmappings,Section2.3.1brieflydescribeshowthedebuggerimplementsthebasicmonitoringfunctions.Section2.3.2ismoreconcrete:itdiscussesseveralwaysthatacompilermightsupplythestatementandvariablemappingsanddescribeshoweachformofmappingisused.ReaderswillfinditinstructivetocomparetheconventionalimplementationdescribedherewiththeversionforoptimizedprogramspresentedinChapters5and6.Thissectiondoesnotconsidermachinearchitecturerequirementstosupportinteractivesource-leveldebugging;Johnsonpresentsagoodtreatmentofthatissue[Johnson82b].rgPsNgg4r#_gsg$r%Egsg&d-.r0gsg1 r7gsg8pgMrb)" )$*/*069<AF_gae7 's- [| &Ye{YY` rY"'(E+-.3VOe{VOVOlZrVO"(++236 >DTeu"(+-D.nQYe{QYQYLrQY#& -/1836: C EG[O%e Lce{LcLc.\rLc $' .b028~@E`J/ef* U#Gme{2GmGm  rGm#(+.03 ;=AGeE9evE9E9#r)(E9E9A ( 02 ; CEG[>`  &){.1E7c:|=@*E`< O %(*+1[7";s>c@Fv9_r9_E  !%'jt2 %|))1Mr.  '.U01e 9 AB + "%*-49f= D9F)K [ %\ ,M0\356\;1 B H&Z#@.>#*/38l>B!D# u # + 0358>@nF^ P1l: C$'8-0I5;>DG=)"A(+9.0} 79?B T "C%r',/5;BCI {&S,7 4 <>D@ < l #(f)-3847s;<<;k rAb<< TVm$CHAPTER2:DEBUGGERSFORALGOL-LIKELANGUAGES262.3.1AbstractimplementationofbasicmonitoringfunctionsThebasicdebuggingoperationsaretoseta(location)breakpoint,todeterminethecurrentexecutionpoint,todisplaythevalueofavariable,andtodisplaytheproceduretraceback.Tosetabreakpoint,thedebuggerusesthemappingfromsourcestatementstoobjectcodelocationstodeterminetheobjectlocationcorrespondingtoagivensourcestatement.Itplacesabreakpointthere(i.e.,itensuresthattheprogramexecutionwillstoptheresothatthedebuggerandpossiblytheusercangaincontrolofthecomputation).Italsorecordstheexistenceofthebreakpointatthesourcestatementinaninternaldatabase,sothattheusercanlistorremovethebreakpointlater.Todeterminethecurrentexecutionpoint,thedebuggerusesthemappingfromobjectcodelocationstosourcestatements,applyingittothecurrentprogramcounter.Thismappingusuallyhasmultiplelevels,suchasamappingfromabsoluteobjectlocationstomodulenames,amappingfrommodule-relativeobjectlocationstoprocedurenames,andamappingfromprocedure-relativeobjectlocationstosourcestatements.[Note:theselevelscorrespondroughlytoloading,linking,andcompiling,respectively.]Thedebuggercanthenreportthesourcestatement,procedurename,andmodulenametotheuser.Somedebuggersusethisfunctiontofieldabreakpoint:thedebuggerdeterminesthecurrentexecutionpointandsearchesitsbreakpointdatabasetoseewhethertheuserhasrequestedabreakpointatthatsourcestatement.Becauseunplanneddebuggeractivitymayoccuratanobjectcodelocationrepresentingthemiddleoftheexecutionofsomeprogramportion,thedebuggermayneedtorecordmoreinformationtopermitmappingobjectlocationstosourcestatementsthanitneedstopermitmappingintheoppositedirection.Todisplaythevalueofavariable,thedebuggermustknowwhatsourcestatementdefinesthevariableenvironmenttobeused.Bydefault,thedebuggersetstheenvironmentfromthecurrentprogramcounter,determiningthecurrentexecutionpointasdescribedabove.Givenasourcestatement,thedebuggerusesthemappingfromidentifierstouser-definedvariablestogetthetypeinformationforthevariableandfinditsstoragelocation.Foranon-localvariable,thisoperationinvolvesaccessingtheprocedurecallchaininexactlythesamewaythatacompiledvariablereferencemight.Thedebuggerthenprintsthecontentsofthestoragelocationformattedaccordingtothetype.Todisplaytheproceduretraceback,thedebuggeraccessesthecurrentprocedurecallchain,whichtypicallyrecordsobjectcodereturnaddresses.Foreachobjectcodelocationinthischain,rgPsNgg4r#_gsg$r%Egsg&d-.r0gsg1 r7gsg8pgMuan %'+3 3r]* %(?* ,F- 3 ;;=CF%[ p!%y'2([-02P79b? Wv"i !K'r*-26b: ACqGThf#( 1348< DEIQ # %(b.4N7 :=?BrDO1C"_')(+r 469e>Q@FHLp r'$`&(-347:= ?ACHI Fu!(,.47:/?CzGCW] !'~(*,17g=T@wF<@L &l)/,3:8:?DE3=E *%'. 25W6}<5?;x s&p;;&),/ 59:?5C9Ej 8Q r8Q "&*k,1l 8">CE5#k$I&)2.0-3F4Y ;=C 2 #)s+ 28:=BEAHy0 'U J!& -&2l9K?XD&G.-Ku &)^. /2.8h:&=CSH*#_"c&. -/4:t>DF' $)+-3f $2i^ !,&)/2c69k=CH!q %#%*-N3V58T @aCF% !$)v/35s;@ELF e "(, 2r4 ;ACLEG, o M#%',25U6<B Dky@$&*,14-7;>?zEu9"-%?)+b02a49J>lD R)! (W*06D8=D<F Z!y$( /259=IBD9F ETVm$CHAPTER2:DEBUGGERSFORALGOL-LIKELANGUAGES27thedebuggerreportsthecorrespondingsourceinformation,asdescribedintheparagraphondeterminingthecurrentexecutionpoint.Thedebuggercanalsoreportthevaluesoflocalvariablesorparametersbyusingthesourceinformationtodeterminethecorrectenvironment.2.3.2ConcreteversionsofmappingsandcorrespondingdebuggeruseThecompilerisresponsibleforconstructingmappingsthatallowadebuggertocommunicatewiththeprogrammeraboutacomputationinsourcelanguageterms.Thesemappingsincludeinformationabouttheuser-definedvariables,theprocedurehistory,andprogramlocations.Someofthisinformationisneededwhetherornotadebuggerispresent.Thecompilerneedsthevariableinformationtogeneratecodecorrectly;mostlanguagesupportsystemsdonotneedthisinformationduringexecution.Thelanguagesupportsystemneedstheprocedurecallhistoryinformationduringexecutiontomanagetheprogram'scontrolflowandtobindvariablesproperly.Useofthisinformationiscompiledintotheprogram'sobjectcode.Locationinformationisneededbythedebuggeronly.Debuggerimplementationscanbecategorizedbytheamountofextraobjectcodetheyrequirespecificallyfordebuggingsupport,inadditiontotheobjectcodeneededtocomputethestatementsspecifiedinthesourceprogram.Invasivedebuggerimplementationsincludeexplicitcallstothedebuggerintheobjectcodegeneratedfortheprogram.Semi-invasivedebuggersrequireextraobjectcode,butdonotexplicitlycallthedebugger.Asaresult,forinvasiveandsemi-invasivedebuggerimplementations,theusermustspecifyadesiretodebugaprogrambeforecompilingit.Tosupportanon-invasivedebugger,acompilerplacesalldebugginginformationinauxiliarytables,keepingtheobjectcodeassmallandasfastaswhennotdebugging.Theauxiliarytablescanbekeptinsecondarystorageuntiladebuggingrequestisissued.Acompilersupportinganon-invasivedebuggercanmakethegenerationoftheauxiliarydebuggingtablesoptional,therebydecreasingcompilationsizeandspeedwhennodebuggingisdesired,oritcancreatethemduringeverycompilation.Ifthecompileralwaysgeneratestheauxiliarytables,nospecialcompilationdirectivesareneededtoallowlaterdebuggingactivity.Thisdissertationemphasizesnon-invasivedebuggersbecausetheyaremoreinkeepingwiththephilosophyofoptimization:theextraobjectcodegeneratedforinvasivedebuggerscanconsumeasignificantamountofexecutiontimeandspace,evenwhennospecificdebuggingrequests(suchasabreakpointrequest)areactive.Althoughadvanceddebuggingcapabilities,suchasrgPsNgg4r#_gsg$r%Egsg&d-.r0gsg1 r7gsg8pgMrb)S (- 5=7,=?B%H_g #'*03-59 rR}9 "% ,359:@B{ O'  " *?,06;z?FM5 gC $ *,3l8Q;@ GJt d"')},'-35c;}>DyHG- #'& ,0(6;#@7BRDHMD \ "&, 1U6:1<CF]B/ ] "')0847:CFH0o!'),}v36004 r0;BG|.h $&)70O2z37:Q?B} +N!$(P,.2 379>BIA(v(( r($%+/1q8 ?AF%|#F&'*X,/2G 9<BwFkH# tZ!")2-/;45s; AB H] $&k(.5[9X?$D5  {d w$]&-/4o6e7:>BG: ' $*--268=U D 5V{%5n 9 # +2I7:=@BG&  "$W'+.57*@G_g#   #p%a -0 8 zZq0rVM[b "{%)C*/Y35< ?BHS TX%)O+306Y;> F~P i"|%P - 1 5 =(BDqGN P &$)+1=28;?'E<HKGX  6"[$*-2k36K:!;>NCEHHW"(#),u 26W8;A_CWHE. %1(F.14\79=7BGHC 6S"%!)+ 257:@AD @A }J #(>+E 26S;>2? F= )#f'*.0<27uBmDj 7 ua!>#),V/18I:?BD5;   %t+c/1`39| @~DH2yUn. P#'*X//16 <ANC ," i$a(+X, 4;=h@FOI5)` y "]#%L ! "$O ,2n8<>D # "' #F(#+-L037:> F^H G $)a+/4c6 =5?@JE1"Z$%:(-2 8!:@BCF&YP"%)*.0 8w:?CA I5 ["$ +t-?/3? 9D;A@EAtJX!& -E.257D8n=6@"N$%+-04w6=N CF" D"$ ,/58=AMDI (? 6$I'*]+o/"46v5 ( (6Hr (78=@ETVm$CHAPTER2:DEBUGGERSFORALGOL-LIKELANGUAGES29manydifferentscopeshavethesamenestinglevel.Aseparatetabledescribesthetreeofscopenumbers.Atruntime,thedebuggermustbeabletodeterminethescopecorrespondingtoanygivenprogramlocation.Thescopetreecanincluderangesofsourcestatementsduringwhicheachscopeistheinnermost.Anotherpossibledatastructureforthescopenestingandstatementinformationisalistofscopeswithrangesofapplicablesourcestatements.Inthisstructure,thescopenestingisimplicitinthenestingofthestatementranges.Thedebuggermustsearchscopesfrominnertooutertofindtheproperdefinitionofmultiply-definedidentifiers.Symboltablesgeneratedbyconventionalcompilersgenerallyequatesourcestatementrangesandobjectlocationranges,sincethesetworepresentationsareinlock-stepforstraightforwardcompilation.Thesesymboltablesfrequentlyrepresentscopeinformationdirectly,asobjectcodeaddresses,sothatthedebuggercanomittheextratranslationfromobjectcodelocationtosourcestatementwhenaccessinginformationaboutvariables.Furthermore,thesecompilersassumethateachvariablehasasingleuniquestoragelocationthatisvalidfortheentirescope.Asweshallsee,neitheroftheseassumptionsholdforoptimizedprograms.2.3.2.2StatementmappingAdebuggerusesamappingfromsourcestatementstocorrespondingobjectcodelocationstosetlocationbreakpoints.Amappingfromobjectcodelocationstocorrespondingsourcestatementsisusedtoreportthesourcelocationwhenacomputationissuspendedforanyreason.Indirectly,thissecondmappingisalsousedtofindthecorrectvariableenvironment.Inaninvasivedebugger,thegeneratedcodeforeachsourcestatementbeginswithacalltothedebugger,providingthenumberorsomeotheridentificationofthesourcestatementasanargument.Thusthemappingbetweensourceandobjectlocationsisembeddedintheobjectcodeitself.Sincethesedebuggersareactivatedateachstatementboundary,theycanimplementalltypesofbreakpointsorsingle-steppingeasily.Thedebuggerkeepslistsofeventsofwhichtheuserwishestobenotified.Eachtimethedebuggeriscalled,itcheckstoseewhetheranyoftheseeventshaveoccurred.Forexample,itcandeterminewhetheragivenstatementisabouttobeexecuted,whetherthevalueofasetofvariableshaschangedsincethelaststatement,orwhetheracertainconditionnowholds.Implementingdataaccessbreakpointsisalittlemoredifficult:thecompilergeneratesalldataaccessesindirectly,ascallstoadata-accessingprocedureinthedebuggertowhichthedesiredvariableisaparameter.Tosingle-step,thedebuggersimplygivescontroltotheusereachtimeitiscalled.IncaseaprogramexceptionoccursduringtheexecutionofthergPsNgg4r#_gsg$r%Egsg&d-.r0gsg1 r7gsg8pgMrb) D"&O+#/s16:@BzESG#_gf&)+.0s79=r FHN\ $'7).24p8 ?\CGY? $*J-368<ADW# :V!$)G+ 16 =?Bg HTaj!&(a*068>BfFQI5"1& ,.9* N !# +?17;@\FKI! n$'*4n68>A]H cr G$@ *04 CWEzG=A #E&v(/z80r4i/81Z#&{* 131 <'@?CI@1 2%Q(,/57 ?D4 .N8\ %B(*! 23:B<? DV ,$= #E$'*A.4 (3  U!$,*-03Y7=BOEuFI@%eM & (+/ 89<`@G,H# O!\&+ -178?A>CG Ja:!$)+/ 5c<?GAHp 'p,X/P5z9q-BD`H&#&.(./4459;=CEGe8c ,&'*506@7;XAC3G2HDP d""#Q%t'2,/m48Y:=D CE "5 +.2 9:<"?PB HrH3$P *,A/701 :A BD !"n# *-! 4>6<ADI@ >Zlb"$').59n=@oFH TVm$CHAPTER2:DEBUGGERSFORALGOL-LIKELANGUAGES30objectcodeassociatedwithastatement,thedebuggeralsostoresthecurrentstatementnumberinternally.Althoughinvasivedebuggersaresimpleandpowerful,theytendtobeveryslow.Semi-invasivedebuggersexistprimarilytoovercomedifficultiesinthemachinearchitecturewithrespecttodebugging.Ifthemachinecannotdetermineanexceptionlocationafteranexceptionhandlerhasbeeninvoked,theobjectcodecorrespondingtoagivensourcestatementbeginswithinstructionstostorethestatementnumberinaknownlocation.Ifthemachine'strapinstructionrequiresmorethantheminimumnumberofinstructionbytes,orifitwouldbedifficulttoexecutetheoriginalinstructionincontextwhenresumingtheprogram'sexecution,theobjectcodecorrespondingtoagivensourcestatementbeginswithanullinstruction.Inanon-invasivedebuggerimplementation,thecompilercreatesaseparatetablethatshowstherelativeprogramoffsetofthestartofthegeneratedobjectcodeforeachsourcestatement.Thistableiscalledastatementmap.Theinformationforastatementmapistypicallycollectedinthreemajorsteps.Thefirststeptakesplacewhilethecompilerisscanningandparsingthesourcetext:thecompilerrecordsastatement(orline)numberwiththesubtreeforeachstatementintheresultingabstractsyntaxtree.Thesecondstepoccurswhilethecompilerisgeneratingtheabstractcodestream(bywalkingthetree):thecompilerassociatesastatementnumberwiththefirstinstructiongeneratedforeachstatement.Thethirdsteptakesplacewhilethecompileriswritingthecompletedobjectcode(afterfinalobjectinstructionselectionandaddressassignment)totheoutputfile:foreachsourcereferenceintheobjectcode,thecompilerrecordsthecurrentrelativeprogramoffsetandthestatementnumberinthestatementmap.Nosourceinformationappearsintheexecutableobjectcodeoutputbythecompiler.[Theproceduredescribedherewouldobviouslybesimplifiedforaone-passcompiler.]Anon-invasivedebuggerusesastatementmapinastraightforwardmanner.Tosetabreakpointatagivensourcelocation,thedebuggersearchesthemap,findsthesourcelocation,andplacesthebreakpointatthecorrespondingobjectlocation,usuallybyreplacingtheexistinginstructionbyatrapinstruction.[Themachinearchitecturecanpermitothermethods:forinstance,somemachineshaveaspecialtrapbitineachinstructionoreachword.Thelatterallowsforefficientdatabreakpoints.]Ifthedebuggerreplacesanobjectlocationwithatrapinstruction,thedebuggermustsavetheoriginalinstructionandexecuteitwhentheuserresumesexecutionfromthebreakpoint.ToreportthecurrentrgPsNgg4r#_gsg$r%Egsg&d-.r0gsg1 r7gsg8pgMrb)  W! (U*137:|?iE_g !G'*(.1E7n:~=?RACDR[ s!$i*,L2 9;Q=Cm Y] 5 "(/,24:?BDVOpu!%)J 2H35.8=@C}GS Ib$):*,!068Y:A(D P"#\({*' 04679(=I?,DWEN  E S%)/29 @pC/GKI e"(-90T1~4V G "-%/5\9;)@DFDhl! !$x'),26:1<?Da B1dvB1B1u"r${B1B1>t +M%z()/m5!6:H>6BjE:H ;K+"$4*,14|8DI9 7Yv"$)+.569>CG6WYD!J#)r* 14 9(ELG0 FG#'J+'-35):<CeG. &x)4." 57e9>@A'CiF+P!$A*1/:16;AEH(Mc$(+/W 6;=@ F%nSs!%%!U#(-/3:89 >@cA@E r"8 "3%&-024m>QDGUIw !&)C/g47`:>{@E_^ h!# ,06~;J=_CkE  s##a%) /15b8:=>C2F2kCP "$ &),.237:H r2A;BDp&2j"#& -0-689<?D  &@,u/2; :BEIP=!z" )+, 46f:=CDN "#z%*X-0o2K CG?o  #%&+)+03D :?`B)G<,ie!~')B,2 9O<=?AEH9BxQ#U'> /69=< >BDH7*3Y!%)'*.3f56:V<BE4i"u )9-G 4-8O>BPD1z"<$.YO"(*> 04d6c9=f@GI+P  &2(* 2-8b;}>4BTVm$hCHAPTER2:DEBUGGERSFORALGOL-LIKELANGUAGES32nametypestorage loc1102111222118231222412825130261342714028objectsource21 y _ 5;22 FOR i IN [1..n] DO23 a _ b+c;24 b _ y/i;25 c _ d*2;26 a _ i-3;27 e _ y/i;28 ENDLOOP;110 y _ 5112 i _ 1114 top: if i>n goto out118 a _ b+c122 b _ y/i128 c _ d*2130 a _ i-3134 e _ y/i140 i _ i+1142 goto top144 out:ObjectSourceWWC@ CW@CC@7W;WC@ C7W@CC@Statement mapabcdeinINTEGERINTEGERINTEGERINTEGERINTEGERINTEGERINTEGER024681012environment 3: object loc 100-150outer environment ptr: 1inner environment ptr: 4Symbol table9!9C@ C9@CC@!9!'@ CC!9CC@@!''@CC@!'C@ C'9CC@@'@ CC8o!8oC@ C8O@CC@9'@ CC9CC@@/2E2C@ C/2@CC@/1oE1oC@ C/1O@CC@INTEGERy14/9/ @ CC/9CC@@/ E C@ C/ @CC@E E9CC@@E @ CCE9/9@CC@E9C@ C626 @ CC62CC@@>2> @ CC>2CC@@Figure2-1.Unoptimizedcodegenerationwithmonotonicallyincreasingstatementmapandsimplesymboltable.rgPsNgg4r#_gsg$r%Egsg&d-.r0gsg1 r7gsg8pgM|1v191@A1 }66442200..,,**((|R8=8}USQOMKIG1U 1S 1Q1O1M1K1I1G1E1C1A~7XX##P: }2/2-2+2)2'2%2#7/7-7+7)7'7%7#A/A-A+A)A'A%A#~07!45435: ########}7!2!A!######z \ # *- 6l <C5F. ;&*/xTVm$sCHAPTER2:DEBUGGERSFORALGOL-LIKELANGUAGES332.4PropertiesforeffectivedebuggingofoptimizedprogramsThissectiondelineatesthepropertiesofaprogrammingenvironmentthatareessentialforeffectivedebuggingofoptimizedprograms,thepropertiesthataredesirable,andthepropertiesthatarerelativelyunimportantinthiscontext.2.4.1EssentialpropertiesTheprimaryobjectiveofthisresearchistoprovideeffectivedebuggingtoolsforoptimizedprograms.Anessentialpropertyofanyeffectivedebuggingtoolisthatitmustbeintelligibletoarelativelynaiveuser.Atoolthatcanonlybeunderstoodbycompilerandoptimizerexpertsisnotsufficient.Auserwillfinditeasiesttodebuganoptimizedprogramifthedebuggeralwaysrespondsexactlyasitwouldforanunoptimizedversionofthesameprogram.Icallthispropertyexpectedbehaviorforagivenoptimization.Adebuggerwithexpectedbehaviormustpresentarestructuredviewoftheactualstateoftheoptimizedprogramaviewthatconformstothesource-levelcomputationalmodel.Ithidesthechangescausedbytheoptimizationsfromtheuser,muchasasource-leveldebuggerhidesthedetailsofalower-levelimplementationofanexecutingprogram.Alessdesirablebutstillacceptablealternativeistoprovidetruthfulbehaviorforanoptimization.Thismeansthatthedebuggeravoidsmisleadingtheuser:eitheritdisplays(insourceprogramterms)howoptimizationshavechangedtheprogramportionunderconsideration,oritadmitsthatitcannotgiveacorrectresponse.Thusadebuggerwithtruthfulbehavioracknowledgesthatoptimizationshavealteredtheprogramanditscomputationalbehavior.Theusermustparticipateintherestructuringoftheprogramstate.Adebuggerthathasneitherexpectednortruthfulbehaviorislikelytogiveincorrectand/orconfusingresponsestoqueriesaboutanoptimizedprogram.Anexamplewillhelptocharacterizethedistinctionbetweenexpectedandtruthfulbehavior.Figure2-2isarepetitionofFigure1-1,inwhichthecodemotionoptimizationmovestheassignmentx_1atstatement18outsidetheloop,therebyreducingtheprogram'sexecutiontime.Thedeadstoreeliminationoptimizationthenremovestheunnecessaryassignmentx_0atstatement15.AsnotedinChapter1,iftheoptimizedprogramisstoppedatstatement17onthefirsttimethroughtheloop,aconventionaldebuggerwouldreportthatthevalueofxis1.Accordingtotheunoptimizedprogram,x'svalueatthatpointwouldbe0.Therefore,adebuggerwithexpectedrgPsNgg4r#_gsg$r%Egsg&d-.r0gsg1 r7gsg8pgMta >Q%.1M9r] ;" )h+K, 5] =@C HZb=#*V, 3o6^8 ?ADw X  !#&4uRI rN'!$_)+b-*2O7>B+DKe#%$'x,36x7:;?bAO HIH m2 {#A%(* 139@Cd 7G "!$).4032 ;>@D9HI4 { ?"' (* 1 ; <>E1x~) $ +-.v3114X18r1>\@B /!{"-& -0"379E>@E`,@ !'7)/37 @BhCH )o#Gr%a)*w04 9X?@ H & X#!|')+ 4;=@D) #_  :&*},B2585= CE!:ws^%*d07G92>7BUDy4W! (+ 17B=?D".h f#&D'+-15 =AC x`r`x`jrB`x`r``H)M!!$'',2!4o:@DGC  !$*!, 4+ x<r<x=r>yx?*r@ABwH"3J"j).0^57=?B2DG ( X #)-247N;x =r>  ?%x@; r ABI@ Z' x ZAr  Z Z q!`$&m)!,0x2 Zr Z3i4 ;3(xb)+r,b)b),.:2#x3b)rb)459Gxb)>Nr?&b)b)?~@E_gx[_gr_g3K/ &+,25Q7;x_g=r?B_g_g?@C8FH\Z #%+.23(8?AqGY&*xYrzYY &x)}./16.;=?BEW#W w!#)),/2xW#4r6W#W#7;>CITah' ")U+b035/6j;?@DQNT\f # +.n1~459f:=aBWEH INFs!$'q-3478=CEnI5L Y#)*/6 wHerI[)xI[rI[I[ wEerF\xFir FF |!$&)N+xF2e45r7uFF89;?ADI@Deew@erA)xArAA $&';;c;&#;-;5;=d;E%;`E;`E;`FF;`F;`G;`Gg;`G;`H(;`H;`H;`II;`I;`J ;`< < 89(8(98989.8.989o88989>8>98989.8.98*988y98989%8%98*98989 k8o k99*8r*9+8y+9,8o,9,~8,~9-$8-$9-8.,8.,9.8.9/8/90I80I9081s8*1s928293X8o3X938c394*84*94849586086097D8787988899589599899:8;%8;%9;8o;9<8<9<8<9=X8=X9=8>8>9?'8c?'9?8c?9?8*?9A8cA9Az8Az9BA8BA9B8oB9CU8cCU9C8C9Dt8Dt999x5+4"*,.P2{+;!2{*.P028o0 0-x /,c---xz)& TVm$p#+))#'<(,TVm$z)/(35r8' ' c' &#' -' 5' =d' E%' `E' `E' `FF' `F' `G' `Gg' `G' `H(' `H' `H' `II' `I' `J ' `r'u'u Jm !# +-3:d@BDZI5 ?!k ),{03586= GP! ) 24A ;sBB rH-!D$&,/5 7s;>BH</ # &+{0(146;A.BFHDJvkDDrD$')f/'03G7d<>@E9 "'u*. 47 @BH x  !% - 3669;g@BHMNw} TVm$CHAPTER2:DEBUGGERSFORALGOL-LIKELANGUAGES35Apracticalimplementationofasystemforprovidingexpecteddebuggingofoptimizedprogramsmusthavetwoadditionalproperties.First,anoptimizedprogramthatiscapableofbeingdebuggedshouldnotbelargerorslowerthananunoptimizedversionofthesameprogram(althoughlargerbutfastermightbetolerableonalargemachine,andslowerbutsmallermightbetolerableonasmallmachine).Ideally,addingdebuggingcapabilitiesforoptimizedprogramsshouldnotcostanyextraexecutiontimeorspaceunlessthedebuggerisactivelyrespondingtoauserrequest.Second,themodifiedcompileranddebuggershouldstillbereasonablyefficientintheiruseoftimeandspace.2.4.2DesirablepropertiesTobeabletoexploitthecontextofaprogramexception,asdiscussedinChapter1,thedebuggermustbeavailableatanytimeduringanyexecutionofaprogram.Therefore,ifaprogramexceptionissignalled,oriftheusersimplydecidestomonitortheprogressofthecomputation,thedebuggercandisplayinformationaboutanypieceoftheexecutingprogram.Thisphilosophyisparticularlyimportantinanexperimentalprogrammingenvironment(suchastheCedarprogrammingenvironmentatXeroxPARC),inwhichausertypicallycallsuponseveralpackagesdevelopedbyotherprogrammers.Suchpackagesfailfrequentlyenoughtowarrantinstantavailabilityofthedebuggertoexploretheprogramstate,butinfrequentlyenoughthatimplementorswouldnotenableexpensiveprearrangeddebuggingfeatures.Usingthedebuggertomonitoraprogram'suseofsuchapackagecanalsobeavaluabletoolforlearningaboutthepackage.2.4.3UnimportantpropertiesTheprimaryconcernofthisresearchistheachievementofcertainlevelsofdebuggerfunctionalityinanoptimizedsetting.Severalfeaturesofthedebuggingenvironmentarerelativelyunimportanttothiswork;theymayaffecttheimplementationofadebuggerforoptimizedprograms,buttheydonotaffectthebasicconceptsdiscussedhere:9thephilosophyoftheprogrammingenvironment(suchaswhetherthecomponentsarehighlyintegrated[Teitelbaum79,Alberga+81]),9theparticularuserinterfacetothedebugger(suchaswhetheraprogramstatementisspecifiedtothedebuggerbypointingatitinthesourcetextwithamouseorbytypinginastatementnumber),andrgPsNgg4r#_gsg$r%Egsg&d-.r0gsg1 r7gsg8pgMrb)k #%'<,.5C;[BoD_g $ % -F13*9?zBsD I5\z!%'+/1 8=?AE`Yg# $*,-169=@REHW# lB#(-y4k ;>7DTaf`%(D*-14_:p;@ HIQL%2*-38S:< CI@N)W|4uI& rD L-"')u*0 7R93?oAOFHB0! #&*-w35.6<T@%B <@H & ),0143:\@C 9 p>!Y# ,] 5] =AD F7* w !"%G*,/0?1k4g9<@E(4i)! &)02 9?AFr1 Op %'-g03* :?BE .3T (/m59BDv m vvr&vv&*/13: BD  ## ]#'+2- 8:;ADMZ#%%(.4wr^A &! * 268>@ H sT r#(s$$ r*J*w3rJ b%'v*0b4O6?;=:C I Ef!#)*,-0.47C:e;?ACHI TVm$nCHAPTER2:DEBUGGERSFORALGOL-LIKELANGUAGES369thelow-leveldebuggerimplementation(suchaswhetherthedebuggerresidesinthesameaddressspaceastheexecutingprogram).2.5HistoricalconnectionsThissectionconnectsthepresentworktootherdebuggingresearchbypresentingabriefhistoryofdebuggersanddiscussingrecentresearchdirectionsindebugging.2.5.1BriefhistoryofdebuggersProgrammershavelongrealizedthebenefitsofdebuggingaprograminteractivelyusingthelanguageinwhichitwaswritten.However,partiallybecauseofexcessiveoptimismabouterrorrates,debuggershavetendedtotrailbehindadvancesinotherpartsofprogrammingenvironments.Interactivesource-leveldebuggersformachinelanguages.Thefirstprogrammersdebuggedtheirprogramsattheconsoleofthecomputer.Theywatchedconsolelightsforabinaryrepresentationofthecurrentprogramcounterandregistercontents,andtheysetconsoleswitchestoexaminememorylocationsortoalterregisterormemorycontents.Theycouldstart,stop,orsingle-stepthemachinedirectly.Non-interactivelow-leveldebuggersforassemblylanguages.Afteratime,programmerswerebannedfromthemachineroom.Bythistime,programswerecommonlywritteninanassemblylanguage.Ifaprogramhaltedwithanerror,theprogrammerwasgivenanoctaldumpofregistersandmemorytoporeoverinsolitude.(Infact,thisdebuggingmethodhassurviveduntiltodayonsomemachines,evenfordebugginghigh-levellanguageslikeFortranorC[Thompson+75].)Interactivesource-leveldebuggersforassemblylanguages.Withtheadventoftime-sharingmachines,userscouldagaindebugtheirprograms(writteninassemblylanguage)interactively.TwoimportantdebuggingfeatureswereintroducedwiththeFLITdebuggeratMITin1959:theuser-controlledbreakpoint,andsymbolicvariableandprocedurenames[Evans+66].Contentsofregistersandmemorycouldbeprintedinavarietyofformats:instructionformat,characters,andoctalanddecimalnumericrepresentations;afterselectingtheproperformat,theprogrammercouldexamineprograminstructionsordatainthesameformastheyappearedinthesourceprogram.Userscouldalsomodifyvaluesofvariablesandpatchtheprogram.Tomaintainthecorrespondencebetweenthesourceandobjectversionsoftheprogram,advanceddebuggersofthistimecopiedrgPsNgg4r#_gsg$r%Egsg&d-.r0gsg1 r7gsg8pgMwaMrb!h!~ +i/!0668>CJEGq__CP${tX  rT"+'5*,07=(?Z F=GQs,q $) .p 46i uLlprG ' %(N-/W6#7_< DHE.$*0]57f=YCG|Bln "9% )/_0479 B v>  &(.l r>58< D<"%'/3e9&>mB~EF9T  &R+U.28;p>@E6(!p#C%(6-$.4t:>vBQEI*3 v0;A 'B)/A r0;6:G;? G-yMK#&(,L2l5<AZCE*k!$&*Q, 4y7:<?CE' |&s(+.I49#?CDHZw "(.07s;ZZ8@ET=!#!(+M.1(7M9Q>A% hD"B')u+18>@CAF}TVm$BCHAPTER2:DEBUGGERSFORALGOL-LIKELANGUAGES37patchescreatedduringthedebuggingprocessintothesourcerepresentationoftheprogram[Lampson65].Non-interactivesource-levelorinteractivelow-leveldebuggingforhigh-levellanguages.Withthedevelopmentofhigh-levellanguages,thereweremorealternatives.Theeasiestmethodwastoinsertstatementstoprintvaluesofvariablesorindicationsofcontrolflow.Thismethodrequirednoknowledgeofdebuggercommands(indeed,itworksevenwhenthereisnodebugger),butwasnotinteractive.Anothernon-interactivemethodwasexemplifiedbytheAlgolWdebugger.Whenaruntimeerrorwasencountered,thisdebuggershowedtheprogramstatementinwhichtheerroroccurredandprovidedasymbolicmemorydump:variableswereidentifiedbynameandtheirvalueswereformattedaccordingtotheirdeclaredtypes.TheAlgolWdebuggeralsoallowedcontextualtracingofsourcestatementexecutions,anideabasedonproofbyinduction[Satterthwaite75].[Note:Satterthwaite'sdissertationiswellworthreading.Itgivesanextraordinarilycarefulexplanationofhisimplementationanditstheoreticalandhistoricalunderpinnings.]Userswhoinsistedoninteractivedebuggingcapabilitieswereforcedtouseamachine-languagedebugger.Theseadventuroususershadtounderstandcompilationtechniquestolocatestatementboundariesortoaccessarrayelementsorfieldswithinrecords.Interactivesource-leveldebuggersforhigh-levellanguages.Ashigh-levellanguagesmatured,interactivesource-leveldebuggersforhigh-levellanguagesbecameavailable.Bysuppressingextraneousdetailsandbyinterpretinglow-levelinformationfromthehigh-levelviewpoint,thesedebuggerstranslatedtheusefultechniquesthatwereavailableinearlierassemblylanguagedebuggersintohigh-levellanguageterms.Thesetechniquesincludebreakpoints,displaysofvariablevalues,single-stepping,andtraces.Therearenowmanyexamplesofinteractivesource-leveldebuggersforhigh-levellanguages,suchasBAIL(adebuggerfortheSAILlanguage)[Reiser75],andpdx(adebuggerforPascal)[Linton81].2.5.2RecentdebuggingresearchMuchofdebuggingresearchoverthepastfifteenyearshasaddressedthefollowingfundamentaldebuggingproblem:anerrormaybedetectedmuchlaterintheprogram'sexecutionthanthetimeatwhichtheprogrambegantodivergefromitsintendedbehavior.Thisresearchcenteredonprovidingsophisticatedmonitoringcapabilitiesandreverseexecution.Severalsystemswerebasedontheideaofcollectingatotalhistoryofasinglecomputation;rgPsNgg4r#_gsg$r%Egsg&d-.r0gsg1 r7gsg8pgMrb): ',027[ @BE`s_g r_g_gv[L "$ +707|9 @ r[GpY< f !t (+.2l :y=KAFI@VO g~"$f*!+ 249B=8@SE^S{&c+- 1 4K7;<> EHCPD 'c,\. 6b8K:>D@FN  Ed #&8,B1839(?^A EG|KI$*e/48c >@DGH@I#%).36:<BEE _\% ,}.G146:K< sB#EEBsrJEsC@y 5 A"%*+"-/B6:$ ?ADB @B$ -o >r@B'+/462 <C =^E(/>3j ;b? AC : q Q#): 0P237;iA)BF7v4h  &8({ . r4h68: >E1  $'3 -49 AC . @  &, 4>7:. @ Ge,# Q# +.I28$::>E()b %*/< 6f; CI5&R!$y(,.15s;I< Cd # n %1(*Q.P06=8;>sEY##ErJ#!\Es"!!#1v'!!uSd $r0~"%(*.2O4:=B o}_ #%+ .135<8B_EwG[!D#(+-3:g=C1H! H $d +.82 V"$'i*q,9 2r36;=H>B{ TVm$bCHAPTER2:DEBUGGERSFORALGOL-LIKELANGUAGES38insuchasystem,thedebuggerisapost-processorthatmanipulatesthecompleted"historytape".Thesesystemsfreedusersfromexaminingacomputationcloselyjustincaseanerrormightoccur.However,thisapproachdoeshavedrawbacks:apost-processingdebuggerisnecessarilyread-only;itcannotmodifyacomputation.Balzer'sEXDAMSsystemworkedbymodifyingsourceprogramstocollecthistoryinformation[Balzer69].Executingtheprogramcreatedahistorytape,whichrecordedstatementexecutionsandchangestovariablevalues(similartoourcomputationalmodel).Thedebuggeranswereduserqueriesbyexaminingthecompletedhistorytape.Becauseitdealtonlywiththehistorytape,theEXDAMSdebuggerwaslanguage-independentandextendable.Thehistorytapecouldbeplayedbackwardandforwardatwill.Asaresult,thedebuggercouldperformcomplexanalysesthatwereimpossibleforaconventionaldebugger,suchasperformingflowbackanalysistodeterminewhatstatementgaveavariableitsvalue.Itcouldalsopresentthesuccessionofvaluesofagivenvariable.Pattisproposedamoreambitioushistory-basedsystem[Pattis81].Itincludedatime-orientedlangaugeforconstructingcomplexqueriesaboutacompletedcomputation,suchas:"IsClearLineevercalledtwiceinarowwithoutaninterveningcalltoFillLine?"Italsoproposedanefficientwaytogatherandmanagethelargeamountsofhistorydata,includingbackgroundprocessingduringuserinteractionsandlazyevaluation.TheHELPERsystemcouldlistthelastseveral(50)assignmentstatementsexecuted[Kulsrud69].TheAIDSsystemallowedretreatingsomenumberofinstructionsinacomputation;acommonuseofthissystemwastospecifythatwhenevertheprogramterminatedabnormally,thedebuggershouldretreatandthentraceforwardtotheerrorpoint[Grishman70].Zelkowitzextendedtheseideas,providinganon-interactivesystemforreversibleexecutioninCornell'sPL/Cenvironment[Zelkowitz71].Thesystemstoredthelast200source-levelstepsofthecomputationtoallowforreverseexecution.TheprogramminglanguagewasextendedtoincludeaRETRACEstatement,whichcouldreversetheprogram'sexecution1)toaspecifiedlabel,2)foracertainnumberofsteps,or3)untilsomeconditionheld.TheRETRACEstatementalsospecifiedanewstatementtoexecuteatthatpoint;thestatementcouldtrytogetthecomputationbackontrackoritcouldenabletracingorotherdebuggingactions.ThecomputationwouldthencontinuergPsNgg4r#_gsg$r%Egsg&d-.r0gsg1 r7gsg8pgMrb)="M#$ -0 8~:AF_gb"9(* 16i9:=?{BF\ $ +J,p6 <=v DL Y8q VOD!&|(a.39:>Cd sS rSSp#k(:)j.1e5y;;Aw H7P8q$&) 28;AGN ^%s*-3647;>6@E.HKIE+. 6e99=@DF~HO!#$(+-1%4:&?DGE U !'+>- v4GEE4: rE?8@GCM~!&~(+,,/.486 =?CEG:@C<{ |& /hs3<<4Jr8J<<9;gA%Bf 9 7#(9+,3 ;>@xB99Cr7*>#% ,/%x07*7*1r77*7*89;=CE4i$ H"&e, .26J< D@ 1SL  b#: .p"$'K).D1 8 >sDr..D rJ.+P &)/0 8U: ;g CE>(V '~#%,.w4 : BD%^p &'*--s1>%%1 r7%%"8!h%=+|,6:< C I@w s ww! r'*ww(+04369&; CZFH L#K *l-L 5;>hDXFsr  $W)+b179;Q B-EHTVm$CHAPTER2:DEBUGGERSFORALGOL-LIKELANGUAGES39forwardfromthatpoint.Incasetheerroroccurredagaininthere-executionofthecomputation,theRETRACEstatementcouldincludeseveralreversalconditionsandnewstatements;eachwouldbetriedinturn.Davisimplementedaknowledge-baseddebuggerforthePLATOsystemattheUniversityofIllinois[Davis75].Targetedatintroductorycomputersciencestudents,thesystemexecutedprogramsinterpretively.Whenaprogramexceptionwasencountered,thesystemusedreversibleexecutionandadatabaseofcommonprogrammingmisconceptionstodiagnosethesourceoftheerrorandsuggestacorrection.Flowbackanalysiswasamajorpartofthissystemalso.Severalresearchersbuiltsystemstodisplaythevaluesofvariablesgraphically.Earlierdisplay-basedsystems,suchastheRAIDsystematStanford[Petit75],hadbeenabletomonitorthevaluesofasetofvariablescontinuouslywithoutchangingtheirlocationsonthedisplayscreen.Yarwood'snon-interactivesystemdrewpicturesofarraysassequencesofvaluesinabox.Variablesusedasarrayindiceswereshownasflagsmarkingtheircurrentpositioninthearray[Yarwood77].TheIncensesystem,implementedbyMyersatXeroxPARC[Myers80],coulddisplaycomplexstructuresbuiltupofrecordswithembeddedpointers.TheusercouldalsoprogramIncensetodisplaythevaluesofcertainvariabletypesanalogically,suchasbyapiechartorbarchart.Forinstance,avariableoftypeTimecouldbedisplayedasthefaceofaclock.Otherrecentdebuggingresearchhasattemptedtoprovidedebuggingcapabilitiesinnewenvironments,suchasprogrammingenvironmentsforrobotarmsandmultiprocessorenvironments.Theseprojectshavegenerallyfocuseduponprovidingtheconventionaldebuggingcapabilities.MitchellL.Modeladdressedtheproblemofprovidinginteractivesource-leveldebuggingforsophisticatedartificialintelligencelanguages[Model79].Asanexampleofthekindofnewproblemstheselanguagesraise,displayingthechanginglocusofcontrolisdifficultforsuchlanguagesbecausecontrolisde-centralized.TheproblemfacedbyModelisquitesimilartotheoneaddressedinthisdissertation:howtopresentahigh-levelviewofaprogram'sexecutionthatisnotasimplemappingfromitsactualimplementation.Thefirsthalfofhisdissertation,inwhichhestronglymotivatestheneedforanexpectedhigh-levelview,isbothinterestingandenjoyabletoread.Goldmanimplementedadebuggingenvironmentforprogrammingrobotarms[Goldman82].Itincludedspecial-purposedatadisplays,suchasagraphicalpresentationoftheforcesexperiencedbyagivenjointduringamotion.rgPsNgg4r#_gsg$r%Egsg&d-.r0gsg1 r7gsg8pgMrb) sA #w%)G.24N6 >@=B _gsI_g_gr_gF!U&;*/ 69Xs@B~ I5VOskVOVOrVOVO H (.228|:?1DS>\#")^, 4I6;1>s DPK  ( 2E49<*@BLDH7N  ("r'*3+]/S2736; Ju A!'A)L.[157= FiG i!#(,,.;s3GG4-r7GG8;S>ACPHD0Rg B (|-37 <? AF^B1#N&+-X1J291:>@xAD?o2C$ %).16D+I@7* F  %) 1b46Y8a9;?APCHC4i#O') /*0386780I!H&)0h2\7> F H. \ $ -L/n36I8 B +PL!2&>)02q :AE '$Y#&+-e3 :` AH$  R #s)$$*r.$$/1397:=5@YBD"8N| "a$*d-/k45P:k<?Ew4" '+m-237*;=@ BI@ y_#M$ + .`021v7>JA2BEFF3$>)',/136 =?CE2 k$ +.03N :<BD !B' 02A :>sAB. rHIwU!g'*A+-232 ; <?>CM h TVm$CHAPTER2:DEBUGGERSFORALGOL-LIKELANGUAGES40Researchershaverecentlybeguntotackletheproblemsinvolvedindebuggingmultipleprocessesanddistributedsystems,suchasnondeterministicchoices(thatdependuponinterprocesscommunication)andtheinabilitytodiscovertherelativeexecutionorderofstatementsinseparateprocessors[Baiardi+83,Bates+83,Smith83].Severalproposedsolutionsinvolverecordinginterprocessevents.Anotherareaofrecentresearchinvolvesunifiedprogramdevelopmentenvironmentsthathavenoseparable"debugger"[Archer81,Feiler82].Instead,debuggingcommandsareaddedtothesourcelanguage.Theseenvironmentstypicallysupportincrementalprogramconstructionwiththeabilitytomodifyaprogramandresumeitsexecution.Afewresearchershaveconsideredtheproblemofdebuggingoptimizedprograms.TheirworkissurveyedinSection3.4.2.6SummaryThischapterhasdiscusseddebuggingfeaturesandtheirimplementation.Ithasalsodefinedasource-levelmodeloftheexecutionofaprogramandhastiedtheexpectedbehaviorofasource-leveldebuggertothatmodel.Thenextchapterpresentsabroadrangeofexamplesofwaysinwhichcommonoptimizationscancauseadebuggertorespondinneithertheexpectednortheless-desirabletruthfulmanner.rgPsNgg4r#_gsg$r%Egsg&d-.r0gsg1 r7gsg8pgMrb) #"',),-t0%6jEu_g j#&(27:?CX \ #q%*v,17;=: CEY sYY 6!r%YY'n,S2b89=CX W#S$*,.4Q pBD@FN vq !'{, 39 AHD\FKINw#%` G  &(.a06=CGqDNt>Ur:27"J) .A14P?@CE7qH y!'){*036P9O;AGI4 ]V %(q+q0M56:>R?EG1_ "%t)/*^0m2"7j9=@<EH/, >UhTVm$ TIMESROMANLAUREL TIMESROMAN  GACHA  TIMESROMAN TIMESROMAN TIMESROMAN GACHAGACHAMATH TIMESROMAN TIMESROMANY TIMESROMAN TIMESROMAN TIMESROMAN TIMESROMAN HELVETICA/  , ! *2 ;3C M 6V &_ Ihpw S  + j/[]<>NewerChap2Monday, May 7, 1984 9:33 pm PDT