41Chapter3OptimizationandtheProblemsItCausesforDebuggingThischapterexaminestheconflictbetweenoptimizationanddebugging.Thefirstsectionbrieflyreviewsprogramoptimization.Thesecondsectiondescribestheeffectsofcommonoptimizationsontheoperationofaconventionaldebugger.Thethirdsectionsurveysthepreviousworkondebuggingoptimizedprograms.Thenextchapterwilldiscussgeneralsolutionmethodsfortheproblemsdescribedhere.3.1ProgramoptimizationManycurrentcompilertextbooksincludedetaileddescriptionsofoptimizationtechniques[Aho+77,Barrett+79].Therearealsoseveralbooksthatdescribespecificoptimizingcompilers[Wulf+75,Anklam83,Chow83].Asaresult,thisdissertationassumesabasicfamiliaritywithoptimizationtopics.Thissectionservesasabriefreminderofsomeofthemajorideas.Programoptimizationsaretransformationsthatareappliedtoaprogram,usuallybyacompiler,todecreaseitsexecutiontimeand/orspaceconsumption.Anoptimizedprogramexhibitsthesameinput/outputbehaviorasitsunoptimizedcounterpartbutisfasterorsmallerorboth.Classicaloptimizationsaremechanicaltransformationsthatdonotalterthebasicalgorithmimplementedbyaprogram.Optimizationscanhaveavarietyofeffects.Forexample,optimizationscanmoveordeletestatements.Variablesmaybeassignedvaluesatdifferentrelativelocationsinthecomputationspecifiedbytheoptimizedprogramthaninthecomputationspecifiedbythesourceprogram,orpg/MqV'A0P4 #',:7)9BL&rFH %"'-] 58b @LCOFRC (a+05};>}C)E>@ UQ!#u$ ,3v6D9>5C E_>mH!(+.36;.@E^;As4 r0 'b,2 9; D t-rn--t--P ra--Y #F&_+</28S= Dt*r**t**^r9**V!E"M&O( /5"6*9{ ?B (=ly!'"Q%+-M0248$ z!+V.08567=bACD!} %|) 24D:@E%Gq% G ( 0c348c:B?&AEUc T *w-:/6147:w@ H   ( !&T(-n0+6 >A:E FK  "5',(-38>@nB e$(),' 4"9;>9BHo)TVm$CHAPTER3:OPTIMIZATIONANDTHEPROBLEMSITCAUSESFORDEBUGGING42theprogram'sflowofcontrolmaybealtered.Therelativeorderingofexecutionevents(suchascallingaprocedure)maybechanged.Optimizationscanalsoeliminateoroverlayvariablesorallocatethemtoregistersinsomeprogramregions.Optimizationscanbeappliedatanumberofdifferentlevels.Source-to-sourcetransformationsareperformeduponthesourcetext;sourcetransformationsystemshavegenerallybeenimplementedasinteractivesystems,sothatthesystemcanrelyupontheprogrammertoverifythemorecomplexenablingconditionsforagiventransformation[Loveman77,Standish76,Arsac79,Gilbert82].Anexampleofasource-to-sourcetransformationisloopjamming[Loveman77],whichcombinesthebodiesofloopsthathavethesamenumberofiterations.Itsenablingconditionis:foralli>j,theresultscomputediniterationiofloopAarenotneededtocomputeinterationjofloopB,whereloopAprecedesloopB.Inthisdissertation,interactivesource-to-sourcetransformationsareconsideredtobepartoftheprogramdevelopmentprocess;theresultingtransformedprogramisthesourceprogram.Nevertheless,thecategoryofoptimizationsdiscussedheredoesincludesource-to-sourcetransformationsthatareperformedcompletelyautomatically.Interproceduraloptimizationsareappliedacrossprocedureboundariesandrequireinterproceduralanalysis[Barth78,Banning79].Acommonexampleiscommonsubexpressioneliminationacrossaprocedurecall,forwhichthecallingproceduremustbecertainthatthecalledproceduredoesnotmodifyanyvariablethatparticipatesinthecommonsubexpression.Abasicblockisamaximalstraight-linesectionofcodewithasingleentry,asingleexit,andnointernalcontrolflow.Globaloptimizationsareappliedacrossbasicblocksandrequireprogramflowanalysis[Aho+77].Localoptimizationsareappliedwithinabasicblock.Intra-statementoptimizationsareappliedwithinasinglesourcestatement,whichusuallycorrespondstoasubsetofabasicblock.However,astatementthatincludesconditionalexpressionscomprisesmultiplebasicblocks.Optimizationscanbeperformedonavarietyofrepresentationsoftheprogram:thesourcetext,anabstractsyntaxtree,aflowgraphrepresentation,alinearintermediateform(suchastriplesorquads[Aho+77]),orthe(linear)objectcode.Localandglobaloptimizationsareoftenappliedtoanintermediateformoftheprogram,frequentlyaflowgraphorquads.Objectcodeoptimizationsrgtgg{rgtgWrgtg g'*rg-t.gg/lrg4t5-grg6jt7hgg8;g;rg>t?gg@bpgMrb!K!`$n&h+.39I; AJEI@__l !' 03X6ISCKI*\k| *#)LY y#%x&+-3,uUsrUs %(e/I25|9=;A R/ y (* 1168T;%=BDGZO  "&,2 9<=A tM. rM.M.tM.M.brM.M.tM.M. r%dM.M.')/312h< F5GJmtJmJm rJmJm%(!,x..147:@=BD GS`3 ^v"|AD*9  u6Nr6N %f(.\3E: BF%3t33# r)733+-39;B$ 0 A!$&*-018 ;l=VADF. e "h'*m 13e5;t *tu6*t*tr*tR" *-.0368*<@ A<E-H7'um''kr'" +--u2T6V9=@E`$7t$$rc$$u9$$,r$"J +-2778 !(*0o 7 >EuU >L&.(Q).;09;=D"FV% 9!]'1"2E6 >AtEFtr M$0(Y,0v3=7p ?B`FrC f!A' -.46u;Ct?gg@bpgMrb)X>f#U)S+904I7":H<[?AF_g '+ -2$7:Fu<_g_g==B t\ r)\\Y~F &.*7 3 9=4@DH7VOQ "%*V/2u5;=ACHFHS s$&' /y5 <>B P= ! + 25/73;T=? tEPPErJPtN \uJN rN HHcH&#H-H5H=dHE%H`EH`EH`FFH`FH`GH`GgH`GH`H(H`HH`HH`IIH`IH`J H`IIF~ CLAL?t> t <W :0X 8BX 6T> ) 4f>  2x"% 0!'.L, (E %L # !mK >S |#D `   $z' .b   w @%S),  \ \c \&# \- \5 \=d \E% \`E \`E \`FF \`F \`G \`Gg \`G \`H( \`H \`H \`II \`I \`J \`r jTVm$CHAPTER3:OPTIMIZATIONANDTHEPROBLEMSITCAUSESFORDEBUGGING443.2ProblemsoptimizationcausesfordebuggingAswementionedinChapter1,theeffectsofoptimizationscauseproblemsforinteractivesource-leveldebuggers.Whenoptimizationsmoveordeletestatements,orwhentheyaltertheprogram'sflowofcontrol,itmaybedifficultfortheprogrammertospecifybreakpointlocationsorforthedebuggertoreportexceptionlocations.Whenoptimizationseliminateoroverlayvariablesorallocatethemtoregisters,thedebuggermaybeunabletodisplaythevaluesofthosevariables.Whenvariablesareassignedvaluesatdifferentrelativelocationsinthecompiledcodethaninthesourceprogram,thedebugger'sabilitytodisplaythevaluesofthevariablesandtoreportthecurrentexecutionpointmaybothbecompromised.Whenoptimizationschangetherelativeorderingofexecutionevents(includingarrivingatabreakpoint),thedebugger'sreportsofsuccessiveprogramexecutionpointsmayconfusetheprogrammer.AccordingtoGaines,thefirststepindiagnosingaprogramerroristheknowledgethattheprogramreachesanincorrectstateduringitsexecution.Therearetwopossiblecausesfortheincorrectstate:somevariablescouldhaveincorrectvalues,ortherecouldbeanerrorintheprogram'sflowofcontrol[Gaines69].Ifaprogrammerusesaconventionaldebuggertomonitorthebehaviorofanoptimizedprogram,theeffectsoftheoptimizationscancausethedebugger'sresponsesto:9givetheappearanceofanerrorwhenthereisnone,9maskerrorswhentheydoexist,or9atbest,giveaninaccurateviewoftheprogram'sexecutionbehavior.Thissectioncategorizesanddescribestheproblemsthatoptimizationcreatesforaconventionaldebugger.Theproblemsaredividedintoproblemswithdata,code,andhistoryelementsoftheprogramexecution.Optimizationsthatcancauseeachproblemarelisted.Anexamplewillbegivenforeachdifficulty.Intheseexamples,theoriginalunoptimizedsourcetextisshownontheleft,andcorrespondingoptimizedtextisshownontheright.Sincetheoptimizationsinquestionarenotalwaysexpressibleinthesourcelanguage,thecorrespondingtextmaynotbealegalsourceprogramfragment.Thesourcelanguageisextendedasnecessarytoshowtheresultofanoptimization.Forinstance,anoptimizedversionmayincluderegistervalues,addresscomputationsforaccessingcomponentsofstructureddata,orexpressioncomputations.ThechosendemonstrationlanguageisCedar,whichisarelativeofMesa[Mitchell79,Geschke+77].ReadersfamiliarwithAlgolorPascalshouldhavenotroublewiththeexamples.Onergtgg{rgtgWrgtg g'*rg-t.gg/lrg4t5-grg6jt7hgg8;g;rg>t?gg@bpgMsau %|+.r]04 $&:(-=/ 7;AD@ Z  A"} +/05 9BEEHX\Ke #%+!-m/ 79>4 E3UQO P&c ,0 9>@E3R4 #) ,.24<8;Q?A;D O y$&<+06u8!:~@zCFHM _t #'{)W.805 79?}BbD>HJKqW!%''` 1T5 >yCiFGK &h+b,- 5t7 >mBD Dq!&)8 A2\ 5!$')U 0O173:<<>EH>q!$)+ 279@BFH8FX t88r#88%&' /2w3 ;ACUH6,%(-,/+1 :=gAcD 3j x/Kr0 W "$C&4)-Z02Ox-Kr- !H$X&_)x*QKr+%  &J)+>-4 :>'' "(j*03T ;3?AB $!I&N)6/N2x59Z@sBG9@ h #I%* 1$25/9}?A 2=<t"%'.1}5;=(CDq\ '*0a2s9=AF "%, 4\6 =AD6  + (.F/489z:?qA"tD E , rw , ,!$')r-15(7;>A1GTVm$CHAPTER3:OPTIMIZATIONANDTHEPROBLEMSITCAUSESFORDEBUGGING45minornoteregardingsyntax:Cedarusesbraces({})andBEGIN-ENDpairsinterchangeably;acommentisprecededbytwodashes(--).ThediscussionfirstfocusesonasimpledebuggerwiththebasicexaminationandcontrolfunctionsdescribedinSection2.2.1.1.Recallthatthesefunctionsare:1.Reportthecurrentexecutionlocationinsource-levelterms.2.Displayvaluesofvisiblevariablesintheappropriateformatfortheirdeclaredtypes.Avariable'senvironmentisnormallydeterminedbythecurrentexecutionlocation.3.Displaythecurrentproceduretraceback.4.Setthevariableenvironmenttosomeotherprogramstatement.5.Signalauserinterrupt.6.Setandremovelocationbreakpoints.Alocationbreakpointcanbeplacedatanysourcestatement,anditisreachedimmediatelypriortotheexecutionofthatstatement.7.Resumethecomputation.Latersectionsconsiderdebuggersthatallowmodifyingthevaluesofvariablesanddebuggerswithadvancedcapabilities.3.2.1DataproblemsThissectiondiscusseswaysinwhichvaluesofvariablesmightbereportedincorrectlywhenaconventionaldebuggerisappliedtoanoptimizedprogram.Hennessyhasconsideredthisprobleminsomedetail[Hennessy79].Supposethatadebuggerdoesnotreportthevaluepredictedbytheexecutionmodelforvariablexatsomearrivalatprogramlocationp.Fromthesystem'spointofview,theincorrectreportcanhaveseveralunderlyingcauses:1.Thevariablexhasbeenremovedbytheoptimizer,i.e.,thereisnostoragelocationforxatp.2.Thecorrectvalueofxatpisavailable,butthedebuggerislookinginthewrongplaceforit.Thevalueofxcanbeinanunexpectedlocationeitherbecausetheoptimizerchosetokeepthevalueofxtemporarilysomewhereotherthanwherethesymboltablereports,orbecausethedebuggercan'tfindthecorrectsymboltableinformationforpointp.rgtgg{rgtgWrgtg g'*rg-t.gg/lrg4t5-grg6jt7hgg8;g;rg>t?gg@bpgMrb!\!%(-Dv-b!b!.r/mb!b!0t3jb!b!4#78rb!;?=I__W?; %Mv%____&r'v____'[ bm#h%&+157;S CRF<Y !&*-1Q7OVGKVG !(-G. 6SKS +o!?%+u-9/ 7%;> AgGQQ   %'$, 4=698=bCNKN t">( KKK i ()-P06} I KI  8b[ FKKFK  & .05 =?AFHND B #W$%* 2679@ ADa AUKAU W =Pt&)S,35:-;ADa: y54r1X"x$%(1,^.379?C FI.P N#-$&-3g9; BEj+#t++> r5++']_!%^(,^.29;H=DDH%8v%8lr%8%8B!$&v%8,;r-%8%8.n2@49=?EBE2"vh $XK vr 1 "&-+.0w 7 9=T>@E vrJv7rK !xv#r%5%v'!r()4*[ 03+5;=ZBlD8F :!%v'r)i*,$.D0!2A 9?"C>HV < !% '+:vV-Gr.VV/f 6i=A@DnH! #%+a.4J7; =B~G v#r$~TVm$yCHAPTER3:OPTIMIZATIONANDTHEPROBLEMSITCAUSESFORDEBUGGING463.Thecorrectvalueofxatpisnotavailable:eitherthecorrectvaluehasnotbeenassignedtox(orevencomputed)yet(Hennessycallsthisaroll-forwardvariable);orsomeothervaluehasbeenassignedtoxearly,destroyingthecorrectvalue(Hennessycallsthisaroll-backvariable).Fromtheuser'spointofview,theincorrectreportcanmanifestitselfintwodifferentways:1.Thevariablexisunknowntothedebuggeratp.2.Thevalueofxatthisarrivalatpointpisnotwhatthesource-levelexecutionmodelpredictsfromthesourceprogram.3.2.1.1VariableisunknowntodebuggerThreeoftheoptimizationsunderconsiderationcancauseavariabletohavenostoragelocationataprogramlocation:constantpropagation,copypropagation,andinductionvariableelimination.Theseareglobaloptimizations.Anexampleofcopypropagationappearsinthenextsection.ConstantpropagationThefirstexampleshowsacaseofconstantpropagation.Thevariabledebugisconstantthroughouttheprogram,sotheoptimizerhasreplacedalloccurrencesofdebugbyFALSE.Thusatanysourcestatementintheprogram,aconventionaldebuggerwouldreportdebugasanunknownvariable.10debug_FALSE;......30IFdebugORa>bTHEN30IFa>bTHEN31Print[a];31Print[a];InductionvariableeliminationThenextexampleshowsaninstanceofinductionvariableelimination.Thevariableiandthecomputations2*iandi+1havebeenreplacedbythecheapert1andt1+2.Again,atanysourcestatementintheprogram,aconventionaldebuggerwouldrespondtoarequesttodisplaythevalueofiwithan`unknownvariable'message(assumingthattherearenootherusesofiintheprogram).Iftherewereotherusesofiintheprogram,theoptimizermightinsertthestatementi_t1div2afterstatement14.Theniwouldbeknowntothedebugger,butitwouldhaveanincorrectvaluebetweenstatement10andstatement15.rgtgg{rgtgWrgtg g'*rg-t.gg/lrg4t5-grg6jt7hgg8;g;rg>t?gg@bpgMrb)Kb) !]vb)#ir%b)b)%vb)'r(b)b))*6, 37:>B~EG_ v_r8__!y$+-47:du;__< r_B I*]  #&j+v]-r/]]0*35 9<#@D@[ u[[hr[" WyM!$&,03c8+CZ A7Z "%*,8/ 7+<6=@CCSu= r9a!"&(- 69v>99?r9CE7* W4"C(b*0H2. 9v;I7*7*AuvFrH7" vrSv ^"#r%n&5(+1735Rv:r=O=v@ZBDrEjF F".(+)j 17;ASCDVI@^v^^r^!(9-3#9 ?BHm8gY#(r.03D9yTVm$CHAPTER3:OPTIMIZATIONANDTHEPROBLEMSITCAUSESFORDEBUGGING4710i_1;10t1_2;11WHILEi<=10DO11WHILEt1<=20DO12a[2*i]_5;12a[t1]_5;13i_i+1;13t1_t1+2;14ENDLOOP;14ENDLOOP;3.2.1.2ReportedvariablevalueisincorrectThevalueofavariablecanbeincorrectataprogramlocationinseveralways.Thevaluecanbeincorrectbecauseanassignmenttothevariablewasdelayed(assignmentremovalisaspecialcaseofthis)orbecauseanassignmenttothevariablewashoisted.Anassignmentishoistedwhenitismovedtoapointthatisearlierintheprogram'scontrolflow.Avariable'svaluecanalsobeincorrectbecauseofstorageallocation.Thevaluecanbeincorrecteverytimethattheprogramlocationisreached,orthevaluecanbeincorrectonlysometimesthatitisreached.Thefirsttwoexamplesdemonstratecasesinwhichavariable'svalueisalwaysincorrectataprogramlocation;theremainingexamplesillustratecasesinwhichthevalueissometimesincorrectthere.StorageoverlayingInthefollowingexample,storageoverlayinghasbeenperformed.Theprogramneverusesiandjsimultaneously,sothestorageallocatorhasassignedthesamememorylocationforbothvariables.Therefore,ifthevalueofiisrequestedatanyprogrampointafterstatement30,aconventionaldebuggercannotrespondwiththecorrectvalue.Anaivedebuggermightdisplayj'svalueinstead.10FORiIN[1..n]DO10FORiIN[1..n]DO11IFa[i]=keyTHEN11IFa[i]=keyTHEN12{found_TRUE;12{found_TRUE;13EXIT};13EXIT};ENDLOOP;ENDLOOP;......30FORjIN[1..m]DO30FORiIN[1..m]DO31b[j]_2*j;31b[i]_2*i;ENDLOOP;ENDLOOP;CopypropagationThisexampleshowsacaseofcopypropagation.Thevariablexhasthesamevalueasvariabley,sotheoptimizerhasreplacedtheuseofxbyauseofyinstatement11.Thereforexhasanincorrectvaluebetweenstatement10andstatement30.Bothformsofpropagation(thatis,rgtgg{rgtgWrgtg g'*rg-t.gg/lrg4t5-grg6jt7hgg8;g;rg>t?gg@bpgMzbj]bj%')+G``%'+-02_i_%)-/S]s c]s%)+-M/S0[[%)wV07!#ArRs "$*5+,2m79B=ADHcO %)&)g.1y6 >ICE1FsM/Vt` &l(*q/2K7:6 ABuBM/M/CfrM/G9Jm:. z %,&)</4]8U9 ?CF0HG '*.1B3Mu9$GG9rG<?BE`D"%F'5,uD0r3mDD379;4<BElHBB(  A!&'I -g127<>o?E>?gA #e&(,.24 :@}u;D r7j!&< ,/L2 :.<BFEv7Ir4v4r44! jI!&,G.4k6:@EYG2+   $Fv2+&Rr(2+2+(e)/14Z:=AGkI/i H!'H*-168.;B#F<v,r,,z)]u)%'*+-2'o"'%)+/S03`&Po&P%+02$c$%,##)!Y!Y))  )b]ub%'*+-2i%)-M.)uj rZ "!#& /:1v7#ZrZ8l:=@DEvrq#"%( v*r+,-/1v3r5C56=>@vFrHyI@  #&w(|+R148!<,> EI*ZTVm$CHAPTER3:OPTIMIZATIONANDTHEPROBLEMSITCAUSESFORDEBUGGING48constantorcopypropagation)cancauseeitheranincorrectvalueoranunknownvariable.10x_y;11z_x+3;11z_y+3;......30x_39;30x_39;LocalcodereorderingLocalcodereorderingcanalsocausethevalueofavariabletobereportedincorrectly.Inthiscodefragment,localcommonsubexpressioneliminationhasmadeitdesirabletostorethenewvalueoffbeforestatement11ratherthanafterit.Thusthevalueoffisalwaysincorrectatstatement11.[Ofcourse,thepreviousvalueoffmighthavebeenb+c.]10a_b+c;10R1_b+c;a_R1;f_R1;11d_5;11d_5;12f_b+c;13g_x;13g_x;GlobalregisterallocationThefollowingexampleshowstheeffectofglobalregisterallocation.TheoptimizernoticedthatthevariableremxyisusedfrequentlyintheWHILEloop,andthereforeplacedremxyinmachineregister1forthedurationoftheloop.Supposethattheuserplacesabreakpointatstatement13andrequeststhevalueofremxywhenthebreakpointisreached.Aconventionaldebuggerwouldreportthevaluecontainedinthenormalstoragelocationforremxy,ratherthanthevaluecontainedinregister1.Therefore,thereportedvalueiscorrectthefirsttimethatstatement13isreached,butonsubsequentloopiterations,thereportedvaluedoesnotreflectthesubtraction(s)ofy.10remxy_x;10remxy_x;11y_F[z];11y_F[z];R1_remxy;12WHILEremxy>0DO12WHILER1>0DO13remxy_remxy-y;13R1_R1-y;ENDLOOP;ENDLOOP;remxy_R1;......30Print[x,y,remxy];30Print[x,y,remxy];rgtgg{rgtgWrgtg g'*rg-t.gg/lrg4t5-grg6jt7hgg8;g;rg>t?gg@bpgMrb!Qg !$ '+-3Z78:@z_]]p]]p%')A*+-M[[)Z Z )XyXy)V]V%')A*uR rO "c%J)+/X1+2o79;A? ILVv # ,l 369:@B`EHIvIr]II#! #'&*`-0 369vI;r=II=? CIVFtFF(n#&zF(st)FF*,/zF235>t5FF60zC]C%')+G,-B"')A*@z')A*>]>%')A*=+];];%')A*u7_; r3 @$`&*,~05 <?F1_v11r1 4# *b,8t.11/r13G69?vD]11E5r1I@.FZ%'}*.X469<@B< IV+.)f!%v'k++(Cr+,=0 2~ 9;A1B (E#S)+R-2s7(((?yrB((CG&{_"u&r%j&&&Q,\.48:I?ADH #@j g"m ), 35s;>ADUH ~ wv0 ~r ~zuu%'+-M]%')A*&')+G~u~%'+-/S0" {%)+-M/S0..)A'+-M)77))  %'#TVm$CHAPTER3:OPTIMIZATIONANDTHEPROBLEMSITCAUSESFORDEBUGGING49Localregisterallocationholdstheresultofacomputationinaregisterandusesitforothercomputationswithinasinglebasicblock.Itcausesthevariable'svalueinmemorytobeincorrectateveryarrivalateveryprogramlocationbetweenthecomputationandthestoreofthevalue.Ofcourse,ifthecomputedvalueisnotusedoutsidethebasicblock,thestoremaybedeletedaltogether.CodemotionAstheexampleshowninFigure1-1andFigure2-2hasillustrated,codemotionoutofloopsalsocausesavariabletohaveanincorrectvalueonsomearrivalsatcertainprogramlocations.Thecodemotionoptimizationcanonlybeappliedwhenaloop-constantpieceofcodewillalwaysbeexecutedbeforetheloopexits.Intheexecutionoftheunoptimizedversionoftheprogram,iftheloop'sexecutionbeginsatexecutionstates1,andanassignment(movedintheoptimizedversion)isexecutedatstates2,thentheassignedvariablewillhaveanincorrectvalueateverystatetbetweens1ands2.Inthefollowingexample,x'svalueisincorrectonlythefirsttimethatstatement11isreached.x_4*c;10FORiIN[1..10]DO10FORiIN[1..10]DO11a[i]_i;11a[i]_i;12x_4*c;13b[2*i]_a[i]+x;13b[2*i]_a[i]+x;ENDLOOP;ENDLOOP;Acombinationofoptimizations:globaldeadstoreeliminationandcodehoistingThefollowingexampleisfairlycomplex.Thevalueofvariablejdefinedinstatement15isneverused,soglobaldeadstoreeliminationremovesstatement15.Theexpressionb+cisaverybusyexpression(itisusedonmultipleflowgraphpathsbeforevariablesborcareredefined),soitscomputationishoistedtoprecedestatement10.Afterstatement15isremoved,thevalueofthatexpressioncansafelybeassigneddirectlytoj.Considerthebehaviorofaconventionaldebuggerontheoptimizedprogramfragment.Atstatements10and14,thereportedvalueofjisalwaysincorrect,becausethenewstoretojprecedesthosestatementsoneverypossibleexecutionpathtothem,whereastheoldstorefollowedthosestatementsoneverypathtothem.Atstatement12,thereportedvalueofjisalwayscorrect.Atstatement16,thereportedvalueofjisalwaysincorrect,bothbecausethedeadstoreat15wasremovedandbecausethestorefrom18washoisted.Atstatement17,thereportedvalueofjmayormaynotbecorrect.IfexecutioncamethroughtheTHENclause,thevalueofjiscorrect.However,ifexecutioncamergtgg{rgtgWrgtg g'*rg-t.gg/lrg4t5-grg6jt7hgg8;g;rg>t?gg@bpgMrb)n $&*,- 578=@CEGO_g _ $$(*1.i0 6:<,ACDE2\rd#'(V-0 8:= @`BDhHYq"$b'*/2I6:[<@CFW# uS`rOk!%(V+ /}14O ;>ZCEGEL "([+-1i6*7<&A HI3 !$&+/b0 9)<>ADHG&4Q"L$&j,.H0 8=P?AXG6HDeX%v(FDeDzD)rDe)*-T/> 6J;D<?GEArRvdAA\zA\;rA!3#)S.1|46<@BeF=vIAr>v>>z>]r>v>>z>r>2!'v>-r.>>/-0j4H5;?&ADH < hz9')A*7p]"7p%'*+-3`5i5%)-M.4! c2zi" {2z%).03`400)u,d  "n&z), 469r)y!f%+[.013v)9r:));?AnGI&YsP #x *0T6&Y93<$ v&YC0DFrH@&Y&YHI#^ 8u!N$'k-R4A8Y=v#C$rD##Ev#FrH##I@   !"').47;PACuDqI1/ !#')/4v6r79d?oAGIS !9'-35 0@C E^vri{ "'*s-0v3r45x:x>8 EG:"V{(#(I*-0j6 9 @cBhFI@PP 0%)rv+r-/-.38:@BE^MvMr]MMW "%+-|04_6 8:@CXH BC!(%*e,2[6v 8r9 :<>ADF Y 7t! "Er %E)+/v 1r 24[9?A1GZ/TVm$CHAPTER3:OPTIMIZATIONANDTHEPROBLEMSITCAUSESFORDEBUGGING50throughtheELSEclause,thenthesituationofstatement16holds,andthevalueofjisincorrect.valueofjbeforestmtj_b+c;10IFcondTHEN10IFcondTHENalwaysincorrect11{j_b+c;12w_j}12{w_j}alwayscorrect13ELSE13ELSE14{w_b;14{w_b;alwaysincorrect15j_1;16y_c};16y_c};alwaysincorrect17z_w+3;17z_w+3;sometimesincorrect18j_b+c;19x_j-17;19x_j-17;alwayscorrect3.2.2LocationproblemsTheprecedingexampleswerecarefullyconstructedtorequireonlyastraightforwardmappingbetweensourcetextandobjectcode.Thissectiondescribesdifficultieswiththeprogramlocation:displayingthecurrentlocation,displayingthecurrentproceduretraceback,settingthevariablecontext,andsettingandfieldingbreakpoints.Recallthatthedebuggerusesthemappingfromprogramstatementstoobjectcodelocationstosetbreakpoints.Itusesthemappingfromobjectcodelocationstoprogramstatementstofieldbreakpointsanddisplaythecurrentexecutionlocation.Obviously,ifeitherofthesemappingsdonotcorrectlyreflectthecorrespondencebetweenthesourcetextandtheobjectcode,therewillbeproblemswiththeassociateddebuggerfunctions.Howshouldthesemappingsbedefined?Aconventionalnonoptimizingcompilergeneratesseparateobjectcodeforeachstatement,intheorderthattheprogramstatementsappearinthesourcetext.Inthiscase,thebeginning(orend)oftheobjectcodeforasourcestatementisunique,andeachobjectcodeinstructionispartofthecodeforexactlyoneexecutableprogramstatement.Somepiecesofsourcetext,suchasENDsorcomments,maynotgenerateanyobjectcode.Forotherpiecesofsourcetext,theremaybeseveralpossibleinterpretationsofwhatthecorrespondingobjectcodeis.Forexample,ifabreakpointisrequestedonaFORstatement,thebreakpointcouldrefertotheinitialentrytothestatementortotheentrytoeachiteration.Similarly,ifexecutionisinterruptedinsideloopcontrolcodeattheendofaFORloop,thesourcelocationcouldbereportedasinsidethelaststatementintheloop,asinsidetheENDLOOP,orasinsidetheFORloopheader.Nevertheless,foragivenlanguageordebugger,onceaninterpretationforthesecasesisdefined,themappingbetweensourcetextandobjectcodeisstraightforward.rgtgg{rgtgWrgtg g'*rg-t.gg/lrg4t5-grg6jt7hgg8;g;rg>t?gg@bpgMrb)tyb)b)3rb)9!_#)Y+1H3-7:9^j>n^O>n_!>^j?'^?'_!?^?_!@J^a@J_!@^@_!AA^jAA_!A^A_!B/^jB^jB_!C^YC_!C\^C\_!DJ^YDJ_!_!_!z]z')A*+-M[[%')-Mt[:=zZ+ cX cX%)A+G,tX:=zVVV%'U5 cU5%)A+G,tU5:=zS cQ cQ%)+G,tQ:=zP?]P?%')A*+-MtP?:?zN]L]L%')A*+-MtL:=yG&rCw $ ) 027l:;E3@CH>!&)-3 :O=a?E>= 0+" ),9147 >C'E:," 7*!+$+&,R/5S <=AE34i ys!'*/2Y89?T FG1 W !$+ 13 89y=e?BH.S+ 'L,/3^68;!?5BFVH,$e & (R#%+- 5 ?D%UA! (4),v0E3.5;Q B%FH# > F&(+-/379):=>wDE J "$_'@(+R.05j8 >Da . S#t%\&r')*147y=?CHCu/sw"%',W1:BtDErG ^  V$)+2(5{7x @$BnFI >:U!&(+/24NTVm$CHAPTER3:OPTIMIZATIONANDTHEPROBLEMSITCAUSESFORDEBUGGING51Optimizationcancomplicatethesemappingsinseveralways.First,anoptimizingcompilermaynotemitanyobjectcodeforanexecutablestatement.Second,optimizationsmaypreservetheorderofexecutionofinstructionsthataremeaningfultotheprogrammer,whilecreatingcorrespondencesbetweenthesourcetextandtheobjectcodethatarenolongermonotonic.Finally,optimizationsmayrearrangetheorderofexecutionofprogrammer-specifiedinstructions,causingseveraladditionalproblems.Thesecomplicationswillbediscussedinorderoftheircomplexity.3.2.2.1NocorrespondingobjectcodeIfanoptimizingcompilerfailstoemitanyobjectcodeforanexecutablesourcestatement,itmakesitdifficultforthedebuggertoplaceabreakpointonthatstatement.Notethatitdoesnotpreventdisplayingthecurrentexecutionlocationproperly,becauseexecutioncanneverreachanonexistentlocation.Twooptimizationscancausethissituation:unreachablecodeelimination,whichremovesprogramstatementsthatcontrolwillneverreach(giventhevaluesofthevariablesknownatcompile-time),anddeadcodeelimination,whichremovesprogramstatementsthatcomputevaluesthatareneverused.Iftheremovaloptimizationalsoremovesthestatementmarker,andthestatementmapusescharacterpositionsorlinenumbers,thestatementwilllooklikeacommenttoaconventionaldebugger.Therefore,thedebuggerwillplacethebreakpointatthestaticallyprecedingstatement,whichmayormaynotdynamicallyprecedethedesiredstatement.Ifthestatementmapusesstatementnumbers,thedebuggercanatleastdeterminethatthereisnoentryforthatstatement,andgiveawarningmessage.Iftheremovaloptimizationleavesthestatementmarkerinplace,thebreakpointwillbeplacedatthefollowingstatement,whichmayormaynotdynamicallyfollowthestatement.Nowarningwillbegiventotheuser,becauseitwilllooktothedebuggerasifthestatementwereastatementthatdoesnotordinarilygeneratecode.TheproblemsassociatedwithalteringvariablesfromthedebuggersoastodirectprogramflowintoareasthathavenocorrespondingobjectcodearediscussedinSection3.2.4.Asimilarproblemisthatacorrespondingstoppingplacemaybemissing,eventhoughcodehasbeengeneratedtoperformthespecifiedoperation(s).Suchoptimizationsaretypicallymachine-dependentoptimizations.Forexample,inthefollowingprogramfragment,theoptimizerhasgeneratedasingleinstructiontoincrementandtestthevalueofi.Therefore,thereisnoplaceforabreakpointcorrespondingtostatement11.Thisproblemoccurswheneverasourcestatementboundaryisembeddedwithinamachineinstruction.Entireloopscanbeeliminatedinrgtgg{rgtgWrgtg g'*rg-t.gg/lrg4t5-grg6jt7hgg8;g;rg>t?gg@bpgMrb)   #'Q-/o48<8>A E3_g}" $_&g -C 49 BZEu\{v '*-1 469C AEYc $'r* ,N0J3s6$8Z:C>i EW# l| #&(.0>@ FTas  $ -z0%28 9=?;B wOk0 K"crKI," !$&k),>0]357 >C IHtM$X&)* 136 =A CEGHyE ,"(j-39?\BEIC X (+D/1 8 ?CY @C_ $'y,-.26[:<ABE3=  " %)I 1+5;?A H :-7"'Z)+19 9mEG5<r #* 1X3913+5; B F*I*'uq ( k" ),k14y6u:4;>XAFHC$':\!(+_,258;c AGP\ !Z$)/3"5;=?A[E`Qf l )c-|039 :?<^!" +1508@:=?BGDu!0#&, 69 BEj $Z&,.e06EQF >O#v'(.l 6$:S=@B{ I@ rTVm$CHAPTER3:OPTIMIZATIONANDTHEPROBLEMSITCAUSESFORDEBUGGING52thiswayonmachineswithvector[Russell78]orstringmanipulationinstructions[Morgan+82].10i_i+1;10IF(i_i+1)#0THEN--oneinstruction11IFi#0THEN12x_y/i;12x_y/i;Optimizationcanalsocausetheflowofcontroltobypassalocationthatwouldnotbebypassedintheunoptimizedversionoftheprogram.Thefollowingprogramfragmentsearchesalinkedlistforadesiredrecord.Iftherecordisnotinthelist,itisconsideredanerror.Thebranch-chainingoptimization(oftenamachine-dependentoptimization)hasbeenappliedtothefragment,eliminatingthesecondtestofthevariablefound.Iftheprogrammerwishestoexaminethedesiredrecordattheloopexit,anaturalplacetoplaceabreakpointisatstatement15.However,theoptimizedversionofthefragmentarrivesatstatement15onlywhenthelistisexhaustedwithoutfindingthedesiredrecord.10found_FALSE;10found_FALSE;11WHILEptr#NILAND~foundDO11WHILEptr#NILDOIFfoundTHENGOTO1712IFptr.key=desiredTHEN12IFptr.key=desiredTHEN13found_TRUE13found_TRUEELSEELSE14ptr_ptr.next;14ptr_ptr.next;ENDLOOP;ENDLOOP;15IF~foundTHEN15IF~foundTHEN16ERROR['Notinlist'];16ERROR['Notinlist'];17--nextstatement17--nextstatement3.2.2.2Control-flowoptimizations:one-to-manyandmany-to-onesource-to-objectcorrespondencesAsomewhatmorecomplexsituationariseswhenoptimizationspreservetheorderofexecutionofinstructionsthataremeaningfultotheprogrammer,butcreatecorrespondencesbetweensourcetextandobjectcodethatarenolongermonotonic.Icalltheseoptimizationscontrol-flowoptimizations;theyrearrangetheobjectcodeforaprogrameitherbymergingidenticalcodesequences,therebymakingtheprogramsmaller,orbycopyingcodesequences,therebymakingtheprogramfaster.MergingoptimizationsExamplesofmergingoptimizationsincludeprocedurediscoveryandcross-jumping.Procedurediscoverylocatesidenticalsequencesofinstructionsandformsasinglenewprocedurethatiscalledfromeachoriginallocation.Cross-jumpingisaspecialcaseofprocedurediscoverythatexaminescodepathsthatjoin.Ifthetailportionsofanytwoofthepathsarethesame,cross-jumpingmovesrgtgg{rgtgWrgtg g'*rg-t.gg/lrg4t5-grg6jt7hgg8;g;rg>t?gg@bpgMrb)[ajt#b)b)# rb))O+. 7Q t>b)b)> rEEb)b)z_!]_!%')+-M023`{6_!_!7 79 z]y c[ c[%)+G,rX= I"$')t. /35:<@C<EU{ !5#),289> CcDHR2{$%s')+.^/1 79>@O _*c 3Y6S:4?ADM6 B G".$vM6*Er.}M6M60814u <A BHJu " #5'+w-#01 8:4;ADGw!',N.469=@nBDDzAA)A+G/S0@Biu!("&)A+G/S23`6>-M/S3`68:<u#)A-M/S46;x;L;L)A/S3`499-M7i7)A/S23`6V6V-M4 4)A+G-M.23 "3)A-M 461`|1`1`V 1`z)51`1`)|+;1`1`+-@0w,j0  # +.r 6I@Hr(Gz"o'+/K 7=?mCD%  $>%(@ 0u26A6F" ~! K"%]) 2k36: uCu""D r  "E$),.0U6:.t?gg@bpgMrb)8Z#&(-29%:= AGO_g+) A%[# #$ , 6W9;@>BDFY8 '! 15;>Cy VN m&6)+- 45; CDES% 5#$o&)-|367>L Ou#%+(, 6~9e; ACFYH7M6 ob' "| (r*D,14c6:Q?AC%FHJt @? !]&4(*-16;=?F"I@G/E '(a-W/1 8:<;?FPH D&G #/%,&M +1P 8P:<?BCHCB/u #$&-/3 <?xCBE2?n$a$(.39=xAC <k"'**=+ 246=>@G9Hq b X%c')*, 06U0 ! b$e&*d/Y35;>"@_FRH3J ^!$%( /1;5W;@D_E0vCo!$&+0D2 9CGZ.=1!g$&+P.16 ?: G+Ob }"$z*@,/267p@%Cv/FrJ/n_t!%T'-O29 ;=C&D5#&)v+r-v-.3-6T =S EH!#' .15@6j9 @CF< )h !'*A/3z4 ;=C TVm$fCHAPTER3:OPTIMIZATIONANDTHEPROBLEMSITCAUSESFORDEBUGGING5410FORiIN[1..6]DO10FORiIN[1..6]DO11IFEven[i]THEN11IFEven[i]THEN12{x[i]_i;12{;GOTOL;13filled[i]_TRUE}13}ELSEELSE14{x[i]_2*i;14{;L:;15filled[i]_TRUE};15filled[i]_TRUE};ENDLOOP;ENDLOOP;Thereisalsoaconnectionbetweenreportingthecorrectsourcelocationanddisplayingthevaluesofvariables.SupposethattheTHENarmoftheIFstatementdeclaredalocalvariabley,whiletheELSEarmdeclaredalocalvariablez.Ifthedebuggeralwaysthoughtthattheexecutionoffilled[i]_TRUEcorrespondedtosourcestatement15,thenitwouldneverallowtheusertodisplaythevalueofythere,becauseyisnotinstatement15'scontext.CopyingoptimizationsExamplesofcopyingoptimizationsincludeloop-unrollingandinlineprocedureexpansion[Allen+72].Loop-unrollingmakesmultiplecopiesofthestatementsinsideashortloopinordertoreducetheeffectsofloopoverhead.Inlineprocedureexpansion,alsoknownasprocedureintegration,replacesacalltoaprocedurebyaninstanceoftheactualcodeoftheprocedureinordertosavetheexecutiontimeassociatedwithprocedurelinkage(suchasmovingparameters,savingandrestoringregisters,andallocatinganewactivationframe).Inlineprocedureexpansionmayalsoprovideopportunitiesforfurtheroptimizations.Copyingoptimizationscreateaone-to-manycorrespondencefromthesourcetexttotheobjectcode.Suchacorrespondencemakesitdifficulttosetbreakpointsandtoprovideproceduretracebacks.Inlineprocedureexpansionisillustratedinthefollowingexample.ProcedureP1hasbeenexpandedatbothofthecallstoitfromP3.SincetheprogramcontainsnoothercallstoP1,nofreestandingcodehasbeengeneratedforit.Therefore,anybreakpointrequestedinsideP1willbeplacedonstatement14.Inordertoachieveaneffectivebreakpointatstatement11,theusermustbeawareoftheoptimizationandplacetwobreakpoints:oneonstatement31,andoneonstatement33.Aneffectivebreakpointonstatement12cannotbeobtained.Ifaprogramexceptionoccursinsideanexpandedprocedure,itwillbereportedatitstop-levelinvocationpoint,causingtheusertothinkthatsomethinghasgoneawryintheprocedurelinkage.Finally,procedurergtgg{rgtgWrgtg g'*rg-t.gg/lrg4t5-grg6jt7hgg8;g;rg>t?gg@bpgMzbj]ubj%'*+-2``%)+1Y__%+|,__-M0z2__]s,.0[c" {[%+Z#Z#)X{X{%+|,X{X{-M0z3\X{X{V)|,VV-M1WzU,c" {U,%,3`4SS)rOH0u "(./05W9?A HM-% !O$3t&M-M-'arM-*-o/=t1M-M-2rM-3o9?T@CvI:M-rM-JJktJkJkrJk3 !$v*JkrJk*,D-06:{?B`DGvGGvr6GvGrGvGnrGV &(,3!5b89>AEGDCLvDrDa"Cv'eDrD(*,,.O47Gu@< r=/! (<-Z 69=Dxt:m rJ:m:m A#|(-(.1E 8<=1@CEI@7j (,k3D :i=BgDk4 B!D") +3-:24p6;>_@/BI@2(} j# *4-k4 8<>C /g !P$ *@+l.] 49=Dx, "%$c) )# #$ , 6W9;@>BDF&N; "'((.70&2 :9=1? Dk# L"$S *,/5(;vBrE EG5!"$v5'r)k55*.s06X;=ASD^v5F`rH55Hs &8(}* 1}4% ;AfvsErHCssIAH[ y"U&',.4X ;V<C>EG^bl8 $'+*- 58:A C^F)H.M &*(.>04x6U<>(?>Dm0<6 &d'*y,s2 35;L BF uWY$0&*h-/2m9#?.DkTVm$ CHAPTER3:OPTIMIZATIONANDTHEPROBLEMSITCAUSESFORDEBUGGING55tracebackinformationwillneverincludeanexpandedprocedure.Ifaninlineprocedurecallsanotherprocedure(whichmayormaynotalsobeexpanded),anexpandedprocedurecouldlogicallyappearanywhereintheprocedurecallchain,andinlinecallscouldbenested.InthefirstcalltoP1,theparameter(1)issufficientlysimplethatthecompilersubstituteditdirectlyfortheuseofi.Thisoptimizationiscalledsubsumption;itissimilartocopypropagation.ThissubstitutionwouldcreateproblemsfordisplayingthevalueofiifabreakpointcouldbemadetooccurwithinthatexpansionofP1,orifaprogramexceptionoccurredthere.10P1:PROC[i:INT]=11{a_i;12count_count+1};13P2:PROC=14{x_5};14{x_5};......30P3:PROC=31{P1[1];31{a_1;count_count+1;32b_2;32b_2;33P1[5-b];33i_5-b;a_i;count_count+1;34x_a+b};34x_a+b};3.2.2.3Coderearrangement:problematicalcorrespondencesbetweensourceandobjectTheuserwhomonitorsacomputationneedrarelybeconcernedwhencompiler-introducedcomputationsforaddressing,subexpressioncomputations,andsoonaremovedoreliminated;thesecompilertemporariesareoutsidethesource-levelmodelofexecutionanyhow.[Asdiscussedbelow,suchmovementcancausehistoryproblemsforamonitoringdebuggerorproblemswithmodifyingthevaluesofvariablesformoresophisticateddebuggers.]However,iftheoptimizerrearrangestheorderofexecutionofprogrammer-specifiedinstructions,severalnewproblemsarise.ConventionaldebuggerbehaviorwhenentirestatementmovesasaunitLetusfirstconsiderthecaseinwhichoptimizationsmoveanentirestatementasaunit.Supposethatcodemotionhasmovedanassignmentstatementwithaloop-constantexpressionoutofaloop,asshownbelow.Iftheoptimizerleavesthestatementmarkerinitsoriginalposition,thismovementwilllookthesameinthestatementmapsasadeletedstatement.Thereforeargtgg{rgtgWrgtg g'*rg-t.gg/lrg4t5-grg6jt7hgg8;g;rg>t?gg@bpgMrb)5 #(+1x 9=:=A)G_g0#%(U+ .0Q 79@]G#\O  #),&03269=?Ys6vY8rYY"$(*,: 3L7:<B IVN(vVNrhVNVN! )v*. 7-8j9>(?B S "(>* 1B37vS9r;BSS;<> EHPPU$%vP'r)WPP*3+-X.4:F?zM]"L cJs" {G$]E| cE|%)A+G,CC)B-B-)@@)>]=6=6%)A+G,;)-/S3`49 c9%)+G,8?i8?%)+G,-/S6)+G,4)-/S3`43H c3H%)+G,-/Sw.Q0 = (289<?2r*. " *%-13:w>L'l  !U *S 3]6H8?:y=AC $W "['=) 1X57z=tC$$DEE!w#k(P*+++ 057KDF Is'dQ  r'%+-C/5 <?!BDf. %*v-d3muC "I%)/35l6r[bq"!$&+ 379=DlFRG^#`!%' .58*9J A Hy)x8 "9$*/1v7<>L@9ET h|!P$&)d/35p6; C6ITVm$CHAPTER3:OPTIMIZATIONANDTHEPROBLEMSITCAUSESFORDEBUGGING56breakpointrequestedonstatement32willbeplacedatthesamespotasabreakpointonstatement33.Todecidewhetherthisplacementcausesaproblem,thequestionsthattheprogrammerwishestoanswerviathisbreakpoint(asdiscussedinSection2.2.2)mustbeconsidered.Whenthebreakpointatstatement32isreached,theprogrammerhasseveralexpectationsconcerningtheprogramexecutionstate.Theseexpectationsareadirectreflectionoftheunoptimizedprogram'sexpectedbehavior,i.e.,theprogramexecutionmodel.First,sheexpectsthattheassignmenttoxwillnothavebeenexecutedyet,soxshouldhaveitspreviousvalue,1.Second,ifabreakpointisalsoplacedonstatement33,sheexpectsthatx'svaluewillchangebetweenthefirstandsecondbreakpointsonthefirsttimethroughtheloop.Third,ifthedebuggerallowsvariablemodification,theuserexpectsthatchangingthevalueofcatthebreakpointwillbereflectedinachangeinthevalueofx.Thereisalsoamoresubtleexpectationinthisparticularexample:ifabreakpointisalsoplacedinsidethefunctionFun,thebreakpointonstatement32shouldprecedethatbreakpoint.Noneoftheseexpectationswillbevalid,andconsiderableconfusioncouldresult.Supposethatrange-checkingisenabledandFun[c]returnsavaluethatisoutsidex'srange.Aruntimeexceptionwillbetriggered,andthedebuggerwillreportthatthecurrentexecutionpointisinsidestatement29.Thisreportwillleadtheusertothinkthatcomputingd+1hascausedtheillegalvalue.10x_1;10x_1;......29c_d+1;29c_d+1;x_Fun[c];30FORiIN[1..10]DO30FORiIN[1..10]DO31a[i]_i;31a[i]_i;32x_Fun[c];3233b[2*i]_a[i]+x;33b[2*i]_a[i]+x;ENDLOOP;ENDLOOP;Codehoistingandcodereorderingcancausesimilarproblems.Meaningofmappingbetweensourceandobject:semanticandsyntacticmappingsItmaybedifficulttodecidewhatobjectcodecorrespondstoagivenprogramstatement.Forsimplicity,wefirstconsiderthecaseinwhichoptimizationsmoveanentirestatementasaunit.Inthiscase,theobjectcodelocationcorrespondingtothestatementcanbedefinedintwodistinctways.rgtgg{rgtgWrgtg g'*rg-t.gg/lrg4t5-grg6jt7hgg8;g;rg>t?gg@bpgMrb) $#%(*.0a26(9:; BD_g[A&Y*+1f39 FY1 "H$*,269; D4HVO # 3!'o) 249d A] HSy" *-.E20 8W:< DP9%&+Z0n4 6;S>!@ GvPIrN  T u#vN %2r&N N 'f+a.06:#<;AlBC KIEZW!$$(vKI,r,KIKI-B.A149#>@CF\H C6F X%|'+/13`9U=oB ES^C#"$(=vE*Jr+EE,-0 79;ACLDI@C:vCrCC o!4"V%) 1*25j ;ABC @Cddv@C%2r'@C@C(+ 25*;=BH = }6 '*8,)/2 :@D9  #$h)vv9,r2h99268 ;>F?v9DrE99EF7*T'!@ '*q,3*5:I=@?D4i2}!k$(+.14,59<v4iCrD4iv4iEArF4iv4iFrHy4i4iI@1^z.].%')A*,,)+P+P))))(](%')A*+-M&Z')A*$]"$%'*+-3`# i# %)-M.!d c!d%i" {%).03`4)rM; ';)-{2u]: %',14H9r !#&k*{- 5P68;AE HC oW"$&* 368<BDXEvI Ek$D -P/17:w<}ACWF bTVm$ CHAPTER3:OPTIMIZATIONANDTHEPROBLEMSITCAUSESFORDEBUGGING57Onenaturaldefinitionyieldsasemanticmapping:namely,thecorrespondingobjectcodeistheobjectcodethatperformstheoperationsspecifiedbytheprogramstatement.Supposethatcodemotionmovesaninvariantassignmentstatementsoutofaloop.Then,ifexecutionofscausesaprogramexception,thatexceptionshouldbereportedasoccurringwithins.(Reportingthelocationofanexceptionutilizestheobject-to-sourcemapping.)However,theinformationthatauserwantstodiscoveraboutherprogramasaresultofalocationbreakpointmaynotbediscernablefromanyversionofsemanticmapping.Forexample,thesemanticmappingofaloop-invariantassignmentstatementisexecutedonlyonceperentireloopexecution.Therefore,abreakpointbasedonasemanticmappingcannotbeusedtoexaminevariableseachtimearoundaloopifitisunknowinglyplacedonaninvariantstatement.Thesyntacticmappinghasquitedifferentproperties.Itpreservesthepositionofastatementwithrespecttoitsneighboringstatements;itcanalsobeviewedasanindicatorof"howfarintothesourceprogram"thestatementis.Noticethatsourceandobjectentriesincreasemonotonicallytogetherinthesyntacticmappingforcomputation-reorderingoptimizations,asinstatementmappingsforconventionalcompilers.Incontrast,thesemanticmappingcanbeorderedeitherbysourcelocationorbyobjectlocation,notbothatonce.SemanticmappingwhenentirestatementmovesasaunitWhenoptimizationsrearrangestatements,theobjectlocationcorrespondingtotheendofonesourcestatementisnolongerequivalenttotheobjectlocationcorrespondingtothebeginningofthenextsourcestatement.Therefore,forthesource-to-objectmapping(i.e.,settinglocationbreakpoints),wemustagainconsidertheinformationthattheuserisattemptingtogatherwiththebreakpoint.Iftheuserwantstoexaminethevariablestatebeforetheexecutionofastatement,eithertoseethevalueofavariablebeforeanassignmenttoit,ortosee(andpossiblymodify)valuesofvariablesthatwillbeusedtoevaluatethestatement,thebreakpointshouldbeplacedbeforethenewlocationoftheobjectcode.Iftheuserwantstoseetheeffectsofexecutingastatement,thebreakpointshouldbeplacedafterthenewlocationoftheobjectcode.Withaconventionaldebugger,asemantic-afterbreakpointistypicallyplacedonthefollowingstatement(s),orisperformedbyplacingabreakpointonthedesiredstatementandexecutingasingle-stepcommanduponarrivalatthebreakpoint.rgtgg{rgtgWrgtg g'*rg-t.gg/lrg4t5-grg6jt7hgg8;g;rg>t?gg@bpgMrb) #u%1b)b)%rb)*1+6n8 AF$I_g^!$T +035;5 BH \?kq#L *sv0\r\20467;@AyGvI\rY!P v#I)./57C=gvAYrYBC W#Ax1" W$'^1_St "%&O)f-e/148;E@BDGIP    "q )- /4s6+;BrEN [%  ) 0568 =ADtGKI   '+-.4|:2>@CEvH n U!$&') 16{8:@ HuErE1 & .h0 678>3@AqGCfX  &d'*s-W/^457=?CbEH@C1q"< #(2-i 6S;=N?E39 (h*+17: B' I7*dn"'$&+/15;<>BHy4iu0FN!'+-r.r, ,$D +P-16 ?ACFHC)=}!T (),20V5 >@TBI5'. !( (+*-]7=AE$m 8 2%' /q2447u8 ?AREH! m!#)2+0458; AVC#D` \/ r%*,,6 3b5*68:=@QE(- "%'-=/ 6d8 ?DFfR8 "&+/,/Q2k6m8<:=0ACzI % @#&*-0x38:=`AFI &3 & -/48:<B "| " )8+u. 3 9yt?gg@bpgMrb){  &/+.41:p<=CdI@_gf!'.4v0_g_g2G3r6_g_g79 BDG\h8|Z#%}2Z#YOzYO457NW]"W|X[&}2X[WzW47N8:@UiU69r:T8 cRqi" {|RqzSE|SE) }2SERqzRq5:<?g@PP6uLN#%OrI) &(?,S 49+;ACDFN1  "(-13t :=AWCFRCq # )+.>49<'?n@FHy@ "u'9+e.&/0 8=>C > /"X$*,6.257: @C ;H  !"( /7w77 % r+%77,-/2l5U <@? FH4 vR &(+W 2647:v? FI2/* !#g&r*-;/1468 ?A5E>/m ^ !"(+9,S 336'8iAE-G, N r" )- 0-369K;DAFH) i $z&*-Q/15)7%9 &TwY&T&TL $ u*&T&Tr+&T&T,2A36b81=?BC # u!r##" r#$ -13 ;?M@v F  %()- 467=@BGs%)|-61 8}::<BE HNz"L$)+-M 5:uAG1#%(N-\3;8;>@ H7 d]#V)-=/,24:s=?CF'G| Le n (f*m, swsstfr"ss#%'*8- 4 6 >@WC I5  "?'),O 3[5 ;=~ D8TVm$CHAPTER3:OPTIMIZATIONANDTHEPROBLEMSITCAUSESFORDEBUGGING59stateincludesfunctionactivationsandchangestouser-declaredvariablesvisiblefromthestatement'sscope.Itisimportanttoprecedefunctionactivationsbecausethefunctionmayhaveside-effects,ortheusermayhaveplacedabreakpointinsidethefunctionoroneofitscallees(andthisbreakpointshouldbereachedbeforethatinnerbreakpoint).Itisimportanttoprecedechangestovisiblevariablessothatembeddedassignments,suchasFORloopvariableassignments,assignmentexpressions,orassignmentstovisiblevariablescausedbyfunctioncalls,willnotyethaveoccurred.Definition2attemptstobringalocationbreakpointclosertothestate-changingportionoftheobjectcodeforastatement.Itrelaxesthenecessitytoplacealocationbreakpointforastatementthatincludestheevaluationofasimplecommonsubexpression(thatdoesnotinvolvefunctioncalls)ontheobjectcodethatevaluatesthatsubexpression.Forexample,thesubexpression'scodemayhavebeenmovedoutsidealoop.However,thisdefinitioncancauseunexpectedbehaviorforvariablemodificationfromthedebugger:ifasubexpressionhasalreadybeenevaluated,thenusingthedebuggertomodifyitscomponentscannolongeraffectitsvalue.However,relaxingthisconstraintcouldcauseconfusionevenifthedebuggerdoesnotallowmodifyingthevaluesofvariables.Supposethatasimplecommonsubexpressioncausesaprogramexception,suchaszerodivideoroverflow.Thentheexceptionwilloccurbeforethebreakpoint,ratherthanafterthebreakpoint,asitwouldinaconventionalsystem.TheIBMFDSsystem's"nosourcechange"modewouldallowonlysimplercommonsubexpressionstoappearbeforethebreakpointforastatementnamely,thosecommonsubexpressionsthatinvolveonlycompilertemporaries.Thismodecouldstillcreateanexceptionbeforethebreakpoint,unlesstheoptimizerrestrictedcommonsubexpressionsevenfurther,tothosecommonsubexpressionsthatcouldbeguaranteednottocauseexceptions.3)Beforefirstvariablestatechange,oronthefirstinstructionthatcorrespondstoanyalterationofuser-visiblevariablestatespecifiedbythestatement.Analterationofuser-visiblevariablestateisanychangetoauser-declaredvariablevisiblefromthestatement'sscope.Thusembeddedassignmentswillnothaveoccurredyet,butsomebreakpointsorexceptionscorrespondingtosubcomponentsofthestatementmayalreadyhaveoccurred,asnotedinthepreviouscase.4)Beforekeystatementeffect,oronthefirstinstructionthatcorrespondstothecoresemanticeffectofthestatement.Thedefinitionofthekeystatementeffectforeachstatementwouldrgtgg{rgtgWrgtg g'*rg-t.gg/lrg4t5-grg6jt7hgg8;g;rg>t?gg@bpgMrb) j 'l*`/1 :f@^DH_g 6 '5(.63 :?BXG\ zK #&*#./ 6:=<BDGNIY; "'\)S.|259K ACDW#12="(*6,3| ;I>Zt?W#W#@rW#BETa  (* 2j4D8>CMEtQ +tN  9a $!%>*g 1K5)69 BFHKH>y "%&).0w4 52:g AUCDH] "#(^.3 7":=@}EtEgi &) 345;>GCf!"&,/e 58$; C H@B V!()l* 3B5:l= D.GE=AK '=)+03595 &I*"-4>79;mADGE7)l $),A-^17Y @DCE`4h yjw!#{*-0(6g9<A=C 1 L #%J&+,. 6H;>B*E.G#O&*/4 >?D>H,# &l*H05 9<AE3)a ,> !$g(a*I0u47 >SBnD&  $g'-.28 B EH# i HwT H HG$!%r)@ H H*[,^.1B4Y ;s> F`HN ] %(.0o2 9; BC  i#%& /49f<? F1 #&\(,71479: BaD5 B B %'*0A3B8;UA[CFH3wy r#$&g(X*-d 4)6 >m@BOE> ){@ # *+.?07!:=B@F 5TVm$CHAPTER3:OPTIMIZATIONANDTHEPROBLEMSITCAUSESFORDEBUGGING60begiven,ideallyasapartofthelanguagedefinition.Forexample,thekeystatementeffectofanassignmentstatementistheassignment,andthekeystatementeffectofaGOTOstatementisthecontroltransfer.Thesepossiblebreakpointdefinitionscanbeextendedintheobviouswaytohandleend-of-statementlocationbreakpoints.3.2.3HistoryproblemsTheprecedingsectionshaveshowntheproblemsthatoptimizationscausefordisplayingvaluesofvariablesanddisplayingcurrentexecutionlocations.Thehistoryelementofacomputationreflectssequencesofvariablevaluesand/orexecutionlocations,sonaturallyitwillbeaffectedaswell.However,optimizationscanchangethehistorycomponentofacomputationwithoutchangingtheothercomponents.Forexample,theeffectsofalteringtheorderofevaluationofexpressionscanbevisibleeveninadebuggerwithstatementgranularity.Supposethatregisterschedulinghasinterchangedtwofunctioncallsinsideasourcestatementsothatfewerregisterswillbeneededtoperformthecomputation,asshownbelow.Iftheusertracesthecomputationatmediumorfinegranularity,theexecutionorderingoftheoptimizedprogramwillbedifferentthantheusermightexpect.Similarchangeswouldbeseeniftheuserrequeststwobreakpoints:oneinsideFandanotherinsideG.10v_F[a-b]+G[c+d]/(c*e);10v_G[c+d]/(c*e)+F[a-b];Manylanguagesrefusetospecifytheorderofevaluationofexpressionssothattheoptimizercanperformsuchrearrangementfreely.Nevertheless,similarproblemswithbreakpointortraceorderingariseifanyexpressioncontainingafunctioncallismoved,eithertoanearlierorlaterprogrampoint.Forinstance,ifacommonsubexpressioncontainsacalltothefunctionH,hoistingitsevaluationcouldcausebreakpointsinsideHtooccurbeforeotherbreakpoints.Whensuchacommonsubexpressionisstoredtoacompilertemporary,onlythesehistoryaspectsofthecomputationareaffected.Incontrast,hoistinganentireassignmentstatementcausesincorrectvariablevalues[asdiscussedinSection3.2.1].rgtgg{rgtgWrgtg g'*rg-t.gg/lrg4t5-grg6jt7hgg8;g;rg>t?gg@bpgMrb)1" #&:, 3G5;>B@G#_gC ",#~% -/14r:>??t@_g_gAr_gD\o!Y #B *-/6X8~;W@D@FgVOr yPrLcg"' )k/^2 :> @H FI K%A+ 25:U?AB F!%S*0? 6[8'=?TBDI@Dp #U'*!.57;8G @#EA]A =N| "')-/K 57 >AkCZG;!S )C.16 =@ HB8Ew!(l*h-n1q7 9<ABH5 C\"a#&^)f-U/ 79r>@C 2nr!(.T1,3J9B"FG0("$f&*/2g :~=SvA~0r0CE->v->r->z*6]o *6023`4 =~>r& !&U(,o.* 46 =?BcD#3 #j(O 05h;> EG!Z " )*03749=?AEG\c_ "J#f) 1786:vD\r\DE c, &v*r,7-16-9 BUFI $N&U'- 5>8<A|F}H !',/30 :m@E2VtGVV $r&VV@TVm$<CHAPTER3:OPTIMIZATIONANDTHEPROBLEMSITCAUSESFORDEBUGGING613.2.4AllowingthedebuggertomodifyvaluesofvariablesAdditionalcomplicationsariseifthedebuggerallowsthevaluesofvariablestobemodified.Recallthataroll-backvariableisonewhoseassignmenthasbeenperformedearly,andaroll-forwardvariableisonewhoseassignmenthasbeendelayed.Ifavalueisassignedtoaroll-backvariablefromthedebugger,thenthevariablewillfailtotakeonthenewvalueattheappropriatespot.Ifavalueisassignedtoaroll-forwardvariablefromthedebugger,thevaluewilllaterbeoverwrittenwiththedelayedstore.Ininductionvariableelimination,usingthedebuggertoassignavaluetotheoriginalinductionvariablewillhavenoeffectonthederivedinductionvariable.Incommonsubexpressioneliminationandhoistedstores,assigningtoacomponentoftheexpressionfromthedebuggerwillnotaffectthecomputedresult(becauseithasalreadybeenperformed).Similarly,usingthedebuggertoassignavaluetoacomponentofanexpressionwhosecomputationisdelayedwillcauseadifferentvaluetobecomputed.Usingthedebuggertoassignavaluetoavariablewhosecurrentvalueisinaregister(orotherfastermemory)willhavenoeffect.Usingthedebuggertoassignavaluetoavariablethathasparticipatedinstorageoverlayingcanhaveverystrangeresults:thedesiredvariable'svalueisnotaltered,andsomeothervariable'svalueischanged.Ifthevariablebeingassignedfromthedebuggerhadaconstantvalueinthatareaoftheoriginalsource,itsvaluemayhavebeenpropagatedtootherstatementsviaconstantpropagation.Assigningavaluetoitfromthedebuggerwillhavenoeffect;thissituationisaspecialcaseofroll-backvariables,inwhichtheassignmentisperformedatcompiletime.Ifanyofthesevaluesislaterusedtoaffectcontrol-flow,evenodderresultsmaybeseen.Thesesituationscanbeevenworseiftheprogrammercomputesthenewvaluetobeassignedfromthedebuggerbyconstructingexpressionsthatusevariableswhosevaluesareincorrect.Asimilarproblemiscreatedwhenthevalueofavariablethatremainsconstantthroughouttheprogramcausesdifferentcodetobegenerated.Supposethatavariablehasaconstantvalueatcompile-time,implyingaparticularcontrol-flow.Thencodetoperformtestsmaybeskippedover,orworse,deleted.Theworstcaseoccurswhenadebuggingvariableissettofalseinthebeginningofaprogramandisusedthroughouttheprogramtocontroldebuggingoutput.Anoptimizingcompilerwouldtypicallyremoveallofthestatementsthatproducedebuggingoutputasunreachablecode;therefore,usingthedebuggertosetthedebuggingvariabletotruecannothavethedesiredeffect.Specialdebuggingroutinesforprintingorcheckingtheintegrityofdatastructuresmayalsoberemovedbythistransformation,andwillhencenotbeavailablefromthergtgg{rgtgWrgtg g'*rg-t.gg/lrg4t5-grg6jt7hgg8;g;rg>t?gg@bpgMyay#s%*/1r]  !E$%(m.25/9l;4@BD[ 9!H"%) /2K5<?BBCC XI#N #&!)/12N67x<>?EUF" %(Z*,k/a1c36:P;>B EIlRr6 $*-`/6 8c<>AC Pb{%* 2678>@WDgEI@MCHY!$z')-/27=HChE>J  !&Z*0r23B:f<>w E,HG- n&*0c14E9#< D Dr; -!=$&a'q.01 8< DEB=gZ !#+F/Y179=?BD|E?{IK.!&3(,0z69}<?;DTH<!g"'*-5 46;A ADG9}$a $(),03y6:f @WCE(76i!U$'%-3/16:@;>ACE4up1" ))*.C 47<\ D1.DO#{&I)+0B38:R;@<CME(. t $&#-.4859<>[AFDG,0 "&+?.B03( = '#g'L(* 28;X>@ACEu%I $q +.|06:?A[ "CDu#'*-/06!9>BC N/ $5%' /,478>@AGE G Z & /b36j8*=@CEoM!%S(\,018=?{AC|FH=pJG! "& -W/57Y<.C H{ %l*e,f./0 7j:H?F| |V "&s(/035<\ACuFr3p,")/1X68r>9@F&G 6 2E  "$'1E4 6:=P?OEH TVm$OCHAPTER3:OPTIMIZATIONANDTHEPROBLEMSITCAUSESFORDEBUGGING62debugger.Thecompoundedeffectsofconstantpropagationorotherassumptionscanalsotriggerdifferentinstructionselectionduringcodegenerationorpeepholeoptimization.Ifavariable'svalueisknowntobe1,thenanincrementinstructionmaybeused.Obviouslytherealproblemhereisthatthevariable'svaluewasfrozenatcompile-time.Similarly,ifavariable'svalueisknownatcompile-timetofitinonebyte,thenthecompilerwillallocatestorageandgenerateinstructionsaccordingly,withdisastrousresultsifavaluesetfromthedebuggerexceedstheone-bytesizelimit.Thisbringsupthesubjectofruntimechecking.Checksmaybemovedoutsideofloopsorremovedaltogetherbasedonthestructureofthewrittenprogram.Alteringthevaluesofvariablesfromthedebuggermaywellinvalidatethoseassumptions,andtheprotectionofthechecksmaybesubverted.Itisdifficult(perhapsevenimpossible)todetectthesesecond-ordereffects.3.2.5EffectsofoptimizationonadvanceddebuggercapabilitiesThissectionconsiderstheeffectsofoptimizationonseveralmorecomplicateddebuggercapabilities:single-stepping,databreakpoints,andassertion-drivenbreakpoints.Italsoconsiderstheuseofadebuggerasaperformancemonitoringtool.3.2.5.1Single-steppingAmajorassumptionofsingle-steppingisthatthechangeinexecutionstate(andtheactionsperformed)betweentwodebuggeractivationsreflectthesemanticsoftheprogramstatementatthefirstactivation.Thechangeinexecutionstateincludesbothdatachangesandcontrol-flowchanges.Optimizationscaneasilyvoidthisassumption.Branchchainingorcombiningsimplesourcestatementsintopowerfulmachineinstructionscancausestatementstobeskippedduringsingle-stepping.Code-reorderingoptimizationscausecontrol-flow(i.e.,statementordering)anomaliesandproblemswithvaluesofothervariablesifasemanticmappingmethodischosen;theycausestatementsemanticsanomaliesandproblemswiththevaluesofspecifiedvariablesifasyntacticmappingmethodisused.Forfine-grainedstepping,inwhichcalledfunctionsarealsosingle-stepped,theorderofarrivalatfunctionapplicationsisanadditionalproblem.rgtgg{rgtgWrgtg g'*rg-t.gg/lrg4t5-grg6jt7hgg8;g;rg>t?gg@bpgMrb) %;&,e 459l A0CF_g !&2) 028 ACD \ SN!#) 0v35~9@@BEjY:: 6!$^(* 3 9(:r; AEFhW#u i3 #')]/16;_>C Ta  $%c&}*,%/}17<?DGQN 6"d$0)z0758*:->CEnI*KI  # (*j,1f7=?dCE3H^! 'i+ 3L68 ?.@CpGE r %) 0J169 Ay?WZ #&.-C4= r;  A"') 14,9 < D9  X#m +K.8 @BD6WAoPz '~ .w1a0r->AH  `)+R.105Z7=^@CFR*} q$ *.1;7b9 ;]@GH' P!w'*/36 ;!= Ej$ "O%: -28:AF"8 y% -04 <6>g@F~w0% .2N :>*D`+F!t%'+412v39w?EDdE"((+V1d46;<BH^I2a!%?' /57{;?EH"p2F$M%+` 24b6R <TVm$ CHAPTER3:OPTIMIZATIONANDTHEPROBLEMSITCAUSESFORDEBUGGING633.2.5.2Assertion-drivenbreakpointsBynow,thereadermayhavebeguntosuspectthatsettinglocationbreakpointsanddisplayingthevaluesofvariablesareoverlyprimitiveoperationsfordebuggingoptimizedprograms,andthathigher-levelfacilitiessuchasassertion-drivenbreakpointsmightmapmorecleanlyfromtheunoptimizedprogram'sexecutiontotheoptimizedversion.Unfortunately,thisdoesnotappeartobethecase.Itiseasytoconstructexamplesinwhichtheunoptimizedversionofacomputationwillsatisfyanassertionthatwillneverbesatisfiedbytheoptimizedversionandviceversa.Theremayalsobedifficultieswiththeprogramlocationatwhichtheassertionissatisfied,withthevaluesofotherprogramvariableswhentheassertionissatisfied,andwiththenumberoftimesthattheassertionissatisfied.Inthefollowingexample,theoptimizerhasnoticedthatthevariablefinishedisalwayssettoTRUEbeforetheloopexit,socodemotionanddeadstoreeliminationcombinetosetfinishedtoTRUEdirectlyattheloopentrance.29count_0;29count_0;30finished_FALSE;30finished_TRUE;DODO31Read[char];31Read[char];32count_count+1;32count_count+1;33IFchar=BLANKTHEN33IFchar=BLANKTHEN34finished_TRUE;35EXIT;35EXIT;36word_Append[word,char];36word_Append[word,char];..--processword--processword..ENDLOOP;ENDLOOP;Supposetheuserrequestsabreakpointwhentheassertion(count=10)AND(finished=FALSE)holds,inordertoexaminewordslongerthantencharacters.Thisassertionwillbesatisfiedintheunoptimizedprogram,butnotintheoptimizedversion.Wenowturnourattentiontowhatpreviousresearchershavedonetosolvetheproblemsthatoptimizationcreatesfordebugging.rgtgg{rgtgWrgtg g'*rg-t.gg/lrg4t5-grg6jt7hgg8;g;rg>t?gg@bpgMwb&0D r^J~ q#')c.050:V ADb [B:a#8) /18? EpH X   " ,Y 4&8t;?DHU 6#c% 'a-3W <?-BUDI@RH)"1$*,03$ ;(?AB P<L u"P<P<#}rP<&R(?-/18D=?BFMzk  &"s'-.24:; AkDsFJO#m%+- 25y8;@?BEHG Db ;")$*-}2y5d7vDb=jrEDbDbEdFA6vA8roAA6!%#'*/269 AFHv>ry>>v>{r>>z!#@%(z;;%'+-M:/:/%'-/S88'6 6%)A 59iu59%)A-M.24 3 i3%)A+G.04 1"0C0C%+.c)A,-,,)+M|+M lz+M)A|+G+M+M+0z)c))'')Ar$j)!# )-0 z!a]i#%4r?Z#`'*- 4S7g=?AFH  C!#g%,2u(%#"i$'g, 37;:t?gg@bpgMsaZ"<r]II!j&*W,N29U@%EdFZ 7! ')-/h57=hCYEX $'-ryRI:5!,rN' #(,/1 :, B KeAb"#'?t-KeKe.& r4@KeKe5 ?CGIH!|& /678y9 CGEGEn/ #4%0 8<@ C/HC!(  #A& /V336k ?=@ G[@_E$*-q//1.58<0@CuI@=( 02 5c >)BtD:T &)A,.C2L :=yBE8d  #%&+.]2,57V=BI5Y (r,Y1F4{A8 I*22  '),v03u7=BAFE/%!n *!, 48<?zEF-Iy)$&0-/>37X9 BF&  %9'*+/ 8):=L?=@FI5# Z# + 275;@!A H7!: l#J%'m*l 1 :>@ Dyr"$E')C 0S 79h<> EI@.!(*/57>cDG "%#'; /46<@E9Fh4v )!>" */a2n35<A?D5 r\ #6(l*-51 8:c=AhFAk"^& r"$)/Y589; ACIV Z $(,4.48<* D TVm$kCHAPTER3:OPTIMIZATIONANDTHEPROBLEMSITCAUSESFORDEBUGGING65areferencetoavariableintoanaccessofitscurrentstoragelocation(s).Forotheruserinteractions,thedebuggerwouldhaveprovidedonlysemi-truthfulbehavior.Thedebuggerusedonlyasyntacticstatementmapping,sothatexecutionwouldappeartoprogressintheexpectedwaythroughthesourceprogramratherthanjumpingaboutrandomly[seeSection3.2.2.3].Tohandlecode-reorderingoptimizations,thecompilerwouldhaverecordedthemovementofvariableassignmentsanduses(bynumberonly)thatcouldaffectorbeaffectedbythevaluesofvariablesatagivensourcestatement.Whentheuseraskedtodisplayormodifythevalueofanaffectedvariable,thedebuggerwouldhavelistedallrelevantassignmentsandusesthattheoptimizerhadinsertedordeleted.Thistechniquewasastepintherightdirection,butitwashamperedbythedebugger'ssoleuseofthesyntacticstatementmapping,aswellassomeskimpinessandinefficiencyinitspre-computedtables.Noattemptwasmadetoreconstructvariablevalues.Furthermore,theFDSsystemmadenoprovisionfordescribingthestateofacomputationthatwassuspendedbetweenstatementboundaries(forexample,duetoaprogramexception),eitherinstatementmappingorinvariablestoragemapping.Optimizationsthatcreateone-to-manyand/ormany-to-onecorrespondencesfromsourcestatementstoobjectcodelocations,suchasinlineprocedureexpansionandcross-jumping,wouldnothavebeenhandledwelleither.Unfortunately,theFDSdebuggerprojectlastedonlylongenoughtoproduceadesigndocument,sonoinformationisavailableregardingitsperformanceoritseffectiveness[Warren82].3.3.2Hennessy:displayingexpectedvaluesofvariablesHennessyconsideredamorerestrictedproblem:providingthemostcriticaldebuggingfeatures(displayingvariablevalues,settingbreakpoints,andreportingerrorlocations)inthepresenceofsomeselectedlocalandglobaloptimizations[Hennessy79].Thelocaloptimizationsincludecommonsubexpressionelimination,redundantstoreelimination,andcodereordering.Theglobaloptimizationsincludecodemotion,inductionvariableelimination,anddeadstoreelimination.Theseoptimizationsaresufficienttocauselargedifferencesincodeorderingbetweenthesourcetextandtheoptimizedobjectcode.Becauseofthemorecomplexproblemsassociatedwithmodifyingthevaluesofvariablesfromthedebugger,Hennessydisallowedthatfeature.Ratherthanpre-computingavarietyoftablesthatmightbeusefulatruntime,astheFDSsystemdid,Hennessyassumedthatthecompilerwouldrecordtheaugmentedglobalflowgraphusedduringtheoptimizationprocessandthedebuggerwouldprocesstheflowgraphasneeded.rgtgg{rgtgWrgtg g'*rg-t.gg/lrg4t5-grg6jt7hgg8;g;rg>t?gg@bpgMrb!p b":&0').F2 :;<@VC7 __%$N$' /,58<>(AHDEES\)N# &I*/ 06_8:@]CFHY2%n)Pt/YY/15r8YY:LuCEL o(_Q! #y& -/03:6 EHyISTt$r& (*y- 47r >@RB F !#2 *E/{4 =?aBG.C!b #A&() 235:8?DA !:"$) 046M<BBDE>L #&+. 3w8X @; !%)e /35:<A@H78 >!%W*-53 @!(,1>48"=e?lEF2rkq "g(".K0& 8*9; tC2r2rDrI2r2ry, "j)<.205r( #( ).5$7o:?E% W$z ,c/75P8 ?.@CtI5#r! t*.##*} r0t##147 @bE> @ : ]'+z 36: CfF~  9%+1d 95<(?CZ   #%)x, 359>D/Fu""}'",.1A5:A& G9y#{&)A/5 <?jR "$:(*.157;=CWE!G}k"p%_'-26x8@*Dl !9@ !T&C)+15:=gDE lTVm$CHAPTER3:OPTIMIZATIONANDTHEPROBLEMSITCAUSESFORDEBUGGING66Eachnodeoftheaugmentedflowgraphwasadirectedacyclicgraph,representingonebasicblockofboththeunoptimizedandtheoptimizedprograms.Hennessydevelopedalgorithmsforprocessingtheflowgraphatruntimethatcanusuallydetectwhenavariable'svalueisincorrectintermsofthesourceprogram.Furthermore,hisalgorithmscansometimescorrectsuchvaluestodisplaytheexpectedvalue.Hedidnotdirectlyaddresstheproblemoffindingthecorrectstoragelocationforavariable'scurrentvalue.IncontrasttotheFDSsystem,Hennessyusedonlyasemanticstatementmapping.Asaresult,theusercouldsetabreakpointtoviewtheoldvalueofavariablebeforeanassignmentwithoutanyconcernabouttheeffectsofoptimizations.Also,whenreportingthelocationofasynchronousprogramexception,thesemanticmappingindicatesthestatementresponsiblefortheexception.However,theuseofthesemanticmappingrestrictedbreakpointplacementforsomecommonsubexpressionevaluations:whenthestartofmultiplesourcestatementscorrespondedtothesameobjectcode,abreakpointwaspermittedonlyonthelexicallyfirstsuchstatement.Hennessy'salgorithmswereimplementedandtestedonasmallgroupofprogramstodemonstratetheircorrectnessandfeasibility,buttheyhavenotyetbeenincorporatedintoanyprogramdevelopmentsystem.3.3.3TeepleandAnderson:statementmappingforcross-jumpingInanunpublishedmanuscript,TeepleandAndersonbrieflydiscussedanevenmorerestrictedproblem:howtosetbreakpointsinthepresenceofthecross-jumpingoptimization[Teeple+80].AsdescribedinSection3.2.2.2,thisoptimizationmergesidenticaltailsofjoiningcodepaths,therebycausingoneobjectcodeinstructiontocorrespondtomultiplesourcestatements.Atabreakpointinthecommoncode,thedebuggerneedshelptodeterminewhichsourcestatementisexecuting.TeepleandAndersonsketchedanalgorithmtoidentify"disambiguatorpoints"foroneofthetwopathstoeachmergedregionduringtheapplicationofcross-jumping.Theyalsonotedflowgraphconditionsunderwhichnodisambiguatorpointsexist.Finally,theysuggestedawaythatthedebuggercouldusethedisambiguatorpointsatruntimetodeterminewhichstatementisreallyexecuting.Theirschemewasbasedupontracingandbreakpointsthatareinvisibletotheuser.Iftherewerenodisambiguatorpoints,thedebuggerwouldreplywithalistofthepossibilities.ThisworkprovidedtheinitialideaforthewaythatNavigatorhandlescross-jumping,whichisexplainedinthesecondpartofthisdissertation.Sincetheirtechniquewasneverfullydesignedorrgtgg{rgtgWrgtg g'*rg-t.gg/lrg4t5-grg6jt7hgg8;g;rg>t?gg@bpgMrb)S| 'k*+=049< ACG._gp  "E(/5(; B.D@ \V!$i)0-T12\ 8B?CHW#< $),'13L8:[>CHTa Pd %,H/24Q:0@GIN    '(,;.1:468=hAC KH "' ( 2|6$9@BGIH e "%X+ 06~8? FOHE h!g#5%+p1A 7U >[E G[C m %(+:.R059 @ I@@BAw $'=-025:_=7@i <  H$ ,/47686<<@BI@9 K !|$^ + -14w79= EKHN7)q y1_1W#%*1@3 r-;gL $ $) +16L.AhD *z # $' ,.b0 9 tA*z*zA rG*z*zH' T" */5F8/9>AE$ $& -/X49- @BC "5k$(+-4B8[<BDl td\!#*%+0 :?SAD3EHBE{u %3' .0l :'=@Dl ) ` )-2J7:A,BEH/ '4+{-824d; ?<EG$m k!$(w-/ 7 9<4ACMEIlf %'u-y15%8:9_;=K? GJR)!#7%(E*1N6E ?^CWD ) )-18D;N?wCI* $TVm$CHAPTER3:OPTIMIZATIONANDTHEPROBLEMSITCAUSESFORDEBUGGING67implemented[Teeple81],itsdescriptionisincomplete.Amongotherthings,theydidnotrealizethatmerginglessthananentirestatementstillrequirespathdetermination,andtheydidnotdiscoverthatrepeatedcross-jumpingcancausenesteddeterminers.3.3.4Feiler:localrecompilation,optimization,anddebuggingAsintheFDSsystemdescribedearlier,Feileralsosuggestedthatdebuggingforoptimizedprogramsshouldbeprovidedbyusingmultiplelevelsofoptimization[Feiler82].Foreachprocedureormodule,theuserwouldselectoneoffouroptimizationlevels.Themoreoptimizedaregionoftheprogram,thelessdebuggingsupportitwouldreceive.WhiletheFDSenvironmentisreasonablyconventional,Feiler'senvironment,calledLOIPE,hassomenovelfeatures:itaddsdebugstatementstothesourcelanguageandisbasedentirelyuponincrementalcompilation.Thedebuggerhasnospecialaccesstothecompiledobjectcode.LOIPEisaninteractiveprogrammingenvironmentforincrementalprogramconstructionbasedoncompilation.Itprovidesauniformviewofallsystemactionsthroughasyntax-directededitortheuserneverseesthetraditionaledit-compile-execute-debugcycle.Theusermakesadebuggingrequestbyeditingadebugstatement,suchasBREAKorTRACE,intothesourceprogram.Inresponse,thesystemautomaticallyrecompilesandrelinksthatportionoftheprogramandthenresumesprogramexecution.Similarly,theusercanmodifytheexecutingprogramtoinsertnewdeclarationsorarbitraryprogramstatements.Themodifiedprogramcanberesumedfromthepointofsuspensionaslongasnoactiveprocedurehasbeenchangedinasemantically-inconsistentway.Whenthisfails,theprocedurecallchaincansometimesbeunwoundtotheearliestcallofamodifiedprocedure.Otherwise,theprogrammustberestartedfromthebeginning.Notethattheabilitytoresumeexecutionafterinsertingadebugstatementandrecompilingtheenclosingprocedureiscentraltothisdebuggingapproach.Thesystemdoesnotpermituserinterrupts.Procedurescompiledwithoutoptimizationwouldhavefulldebuggingsupportforprogrammodificationandresumption,asdescribedabove.Programexecutioncanalwaysberesumedafterdebugstatementsareaddedorremoved.Incontrast,anoptimizedprocedurewouldreceiverestricteddebuggingsupport.Noattemptwouldbemadetouseinformationcollectedbytheoptimizertohidetheeffectsoftheoptimizationsortopresentalternatives.Nevertheless,Feilerclaimsthatthedebuggerwouldprovidealimitedformoftruthfulbehavior:itwouldonlyreportvariablevaluesandcurrentexecutionlocationsthatrgtgg{rgtgWrgtg g'*rg-t.gg/lrg4t5-grg6jt7hgg8;g;rg>t?gg@bpgMrb) t,b)b){rb)b) %'. / 37;>AbCH _gN &K(.L1| :=t@C E\K !"&b* yV & 03rR &^+/228k;UB*DOG# "&\+/w1 t8OO9Nr=OO>AODkM6MAj#%%'*} 2q7 9=lCDI5Jt"$' (>,I15x7: BD G 2 $1(,/J26X;=@(D4 DB !.%*- 5' =@hFrHB0^ky!w%>Dh  (q 0c2 9?[ G ;5 5!#K(,x.}05:l?Ag9 DaP L" ):?OBKEhI6UB' !% ,O/it16U6U1r6U5nt76U6U7r;6U6U;>@E3p % ,/m36;=5?EG0= ! 'K),/Z4&6<BjD'H. M$ +.4:=<?PEH+Ox( !h#e'I-0.38:;(>%Z'+.46<>@EHI%  "%*-/58;/ B`EH# qu!$*,)079:F B1D IeW&a-;047:4>A  $= ,`04)6=BE`  !"(-3;9g;@EB,G0  C"w!e',0 6=C{EjT #)`+?-358:`>@/Bq oP  ', 0R3-5;?EF< V< W$x'+047t?gg@bpgMrb) t b)b) "%b'p+.X0U5@8=AQDVF[H_gr_g^4S$(F-1G367=5?A H7\ %'*/6:>C-EYn (y 02*4s <>@`B W#lO#) ).4/6:& ADkTa&- k! *x-E/6S8<AC I@Q 0# N   $h(,)1Z38w<>E4 KI +!'+.b24 <>^ADkHzJ  '],0x29=U?CFE4 #%) 1359J=?TE!HC9' $%& .47j:=@NE5G@CW *#29 <1  % )d-P/5 ?A]FHy9&-s3Or/,"#'' *,h2Q37@8<Bq ,kw6i $&W+-Z24:F<@)B )a &|(.o13:A"H&!w (R*06<TVm$| MATH GACHA TIMESROMAN GACHA TIMESROMANYMATH TIMESROMANGACHA TIMESROMAN TIMESROMAN TIMESROMAN TIMESROMAN TIMESROMAN HELVETICAb  G#+3: IC 'L iUJ] g p#wD # - v j/O []<>NewChap3Monday, May 7, 1984 8:41 pm PDT