编译原理与实践（中英双语版）课件 Chapter 10 Code Optimization

Chapter10Code

Optimization

Asweimagined,thetargetcodemadebycompilershouldrunfasterortakelessspace,orboth..Infact,thisgoalisdifficulttobeachievedoronlycanbereachedinlimitedcases.Inordertoobtainthegoal,weusecodeimprovingtransformationswhichiscalledoptimizing.Ofcourse,codeoptimizationcanonlyguaranteethepossibilitythatthecodeisbest..

2Therearetwotypesofcodeoptimization,thefirstoneismachine-independentoptimizationswhichmeanstheoptimizationhasnorelationshipwithpropertiesofthetargetmachine,optimizationsofthistypeisonthelevelofintermediatecodeorsourceprogram.Thesecondoneistheoptimizationwhichisrelatedwithtargetmachine,namely,theoptimizationisbasedontheleveloftargetcode.Thepositionofcodeoptimizationincompilerisshownbelow..

3

4Asweallknow,acompilerisaprogramthatreadsthesourceprograminahigh-levellanguageandtranslatesitinto(typically)machinelanguage.Thisisacomplicatedprocessinvolvinganumberofstages.Ifthecompilerisanoptimizingcompiler,oneofthesestages"optimizes"themachinelanguagecodesothatiteithertakeslesstimetorunoroccupieslessmemoryorsometimesboth..5Ofcourse,whateveroptimizationsthecompilerdoes,itmustnotaffectthelogicoftheprogrami.e.theoptimizationmustpreservethemeaningoftheprogram.Onemightwonderwhattypeofoptimizationsthecompilerusestoproduceefficientmachinecode?Sinceinnocasethemeaningoftheprogrambeingcompiledshouldbechanged,thecompilermustinspecttheprogramverythoroughlyandfindoutthesuitableoptimizationsthatcanbeapplied..610.1Classificationsofoptimizations

Optimizationsthatareperformedautomaticallybyacompilerormanuallybytheprogrammer,canbeclassifiedbyvariouscharacteristicsThescopeoftheoptimization:(1)Localoptimizations-Performedinapartofoneprocedure.1)Commonsub-expressionelimination.

72)Usingregistersfortemporaryresults,andifpossibleforvariables.3)Replacingmultiplicationanddivisionbyshiftandaddoperations.(2)Globaloptimizations-Performedwiththehelpofdataflowanalysis.1)Codemotion(hoisting)outsideofloops.2)Constantpropagation.3)Strengthreductions.8Theimprovementinoptimization:(1)Spaceoptimizations-Reducesthesizeoftheexecutable/object.1)Constantfolding.2)Dead-codeelimination.3)RedundantCodeElimination.4)UnreachableCodeElimination.

9(2)Speedoptimizations-MostoptimizationsbelongtothiscategoryThecodetypesofoptimization:(1)Sourceprogramoptimization.(2)Threeaddresscodeoptimization.(3)Quadruplescodeoptimization.(4)

targetcodeoptimizations.1010.2SourceprogramoptimizationsSourceprogramoptimizationisthatoptimizationsworkregardlessofprocessororcompilerandtheobjectissourceprogram..1.Eliminatingcommonsub-expressionsRegisteroperationsaremuchfasterthanmemoryoperations,soallcompilerstrytoputinregistersdatathatissupposedtobeheavilyused,liketemporaryvariablesandarrayindexes.11Tofacilitatesuchregisterscheduling,thelargestsub-expressionsmaybecomputedbeforethesmallerones.Thisisanoldoptimizationtrickthatcompilersareabletoperformquitewell:.Example1:X=A*LOG(Y)+(LOG(Y)**2)

t=LOG(Y)X=A*t+(t**2)Optimize12Example2:

/*Sumneighborsofi,j*/up=val[(i-1)*n+j];down=val[(i+1)*n+j];left=val[i*n+j-1];right=val[i*n+j+1];sum=up+down+left+right;intinj=i*n+j;up=val[inj-n];down=val[inj+n];left=val[inj-1];right=val[inj+1];sum=up+down+left+right;Optimize132.RedundantCodeEliminationi:=m-1j:=nt:=4*nv:=a[t]s:=m-1u:=a[s]i:=i+1i:=m-1j:=nt:=4*nv:=a[t]u:=a[i]i:=i+1Optimize143.UnreachableCodeElimination

Acommonexampleofunreachablecodeeliminationisanifstatement.Ifthecompilerfindsoutthattheconditioninsidetheifisnevergoingtobetrue,thenthebodyoftheifstatementwillneverbeexecuted.Inthatcase,thecompilercancompletelyeliminatethisunreachablecode,thussavingthememoryspaceoccupiedbythecode..15i:=m-1if(j>0)gotoL1j:=nt:=4*nv:=a[t]L1:v:=a[i]i:=i+1……..i:=m-1v:=a[i]i:=i+1……..

Optimize164.DeadCodeEliminationDeadcodeisthecodeintheprogramthatwillneverbeexecutedforanyinputorotherconditions.Thedeadcodeexampleisanconstantthatithasneverbeenused,itisshownbelow.i:=m-1j:=nt:=4*nv:=a[t]i:=v+1……..i:=m-1j:=nt:=4*nv:=a[t]i:=v+1……..Optimize175.StrengthReductionToreplaceanequivalentbutcheaper(shorter)sequence.Onetypeofcodeoptimizationisstrengthreductioninwhicha"costly"operationisreplacedbyalessexpensiveone.Forexample,theevaluationofx2ismuchmoreefficientifwemultiplyxbyxratherthancalltheexponentiationroutine.Oneplacewherethisoptimizationcanbeappliedisinloops.18Replacecostlyoperationwithsimplerone.Shift,addinsteadofmultiplyordivide16*xx<<4Utilityofthisoptimizationismachinedependent.Dependsoncostofmultiplyordivideinstruction,shiftoraddisusuallyasinglecycleoperation.Recognizesequenceofproductsturnthemintoasequenceofadds.19Example1

i:=m-1j:=ii:=i+ii:=j+i……..i:=m-1j:=ii:=3*i……..Optimize20Example2

r1:=r2*2r1:=r2+r2r1:=r2<<1r1:=r2/2r1:=r2>>1r1:=0Optimizer1:=r2*0OptimizeOptimizeOptimize216.Constantfolding:Constantfoldingisthesimplestcodeoptimizationtounderstand.Letussupposethatyouwritethestatementx=45*88;inyourCprogram.Anon-optimizingcompilerwillgeneratecodetomultiply45by88andstorethevalueinx.Anoptimizingcompilerwilldetectthatboth45and88areconstants,sotheirproductwillalsobeaconstant.Henceitwillfind45*88=3960andgeneratecodethatsimplycopies3960intox.Thisisconstantfolding,andmeansthecalculationisdonejustonceatcompiletime,ratherthaneverytimetheprogramisrun.22r2:=3*2r2:=6OptimizeEliminationofredundantloadsandstores.

r2:=6i:=r2r3:=ir4:=r3*3r2:=6i:=r2r4:=r2*3Optimize23Constantpropagation:r2:=4r3:=r1+r2r2:=….r2:=4r3:=r1+4r2:=….r3:=r1+4r2:=….OptimizeOptimizer1:=3r2:=r1*2r1:=3r2:=3*2r1:=3r2:=6OptimizeOptimize24Copypropagation:Eliminationofuselessinstructionsr1:=r1+0r1:=r1*1r2:=r1r3:=r1+r2r2:=5r2:=r1r3:=r1+r1r2:=5r3:=r1+r1r2:=5OptimizeOptimize257.Loopoptimizations

Averyimportantpartforoptimizationisloops.Ifwemakethenumberofinstructionsinaloopdecreased,therunningtimeofaprogramwillbeimproved,thoughsometimes,itmaybecausethenumberofcodeoutsidetheloopincreased..26Therearethreewaysforloopoptimization:codemotion,induction-variableeliminationandreductioninstrength.Codemotionistomovecodeoutsidealoop;induction-variableeliminationmeanstoeliminateextravariablefromaloop;reductioninstrengthcanreplaceacomplicatedoperationbyasimpleone.Reducefrequencywithwhichcomputationperformed，ifitwillalwaysproducesameresult,somovingcodeoutofloop..

27Example1Example2

J=2*4While(i<=j)

While(i<=2*4)……OptimizeOptimizefor(i=0;i<n;i++)for(j=0;j<n;j++)a[n*i+j]=b[j];for(i=0;i<n;i++){intni=n*i;for(j=0;j<n;j++)a[ni+j]=b[j];}28Example3Movingasmuchaspossiblecomputationsoutsideloops,savescomputingtime.Inthefollowingexample(2.0*PI)isaninvariantexpressionthatthereisnoreasontorecomputeit100times..

DOI=1,100ARRAY(I)=2.0*PI*IENDDOt=2.0*PIDOI=1,100ARRAY(I)=t*IENDDOOptimize29Sowecanconcludethatthetransformationofloopoptimizationis(1)Takeanexpressiontransformationtogetthesameresultwiththetransformationbeforeandtoobtainindependentofthetimenumber.(2)Placetheexpressionbeforetheloop.3010.3Optimizationsofthree-

addresscode

Actually,thereareseveralblocksinoneprogram,namely,blockmeansapartofprogramwithoneentranceandoneexit,furthermore,blockrunningisinsequence.Forexample,figure10.2aisablock,ontheotherhandfigure10.2bisnotablock,becausetherearetwoexitsinit,soitisonlyapartofprogram..3132Combiningtheresultsoftwoexpressionsthattheyshouldbeinoneblock.Theprocedureofcombiningisfirstlytocalculatetheresultofconstantsinoneexpressionandthenusethenewresulttoreplaceallthecalculationwhichisrelatedwiththeconstants.Sothestepofcombiningindetailisasfollows..

33Step1recognizeconstantexpression.Step2replaceconstantexpressionbytheresultofconstantscomputingStep3generatetargetcodeaccordingtothecombineresults.34Example10.1

35Becausethevalueof“a”isknownatcompiling,wecancomputetheknownvaluesandreplacethembytheirresulttoobtaintheoptimizedthreeaddresscode..Beforecombiningconstant,weshouldfirstcreateasymboltable“Tab”whichhastwofields,fieldNstoresvariablename,fieldVdepositsthevariablevalue.Theformatofthreeaddresscodeisshownbelow,thefirstpartisoperatorω;secondoneisoperand1,wenameitP1;thethirdpartisoperand2,wecallitP2..36operatoroperand1operand2

ω

P1

P2

Wecombineconstantsfromtopofthreeaddresscodetotheendofthreeaddresscodeinblock,thepointerofthreeaddresscodeis“i”.37Thealgorithmofcombiningconstantsis:1Ifoperatordoesnotequalto“：=”:P1orP2isthevariablenameinsymboltable“Tab”,wecanusethevalueVofP1orP2toreplaceP1orP2inthreeaddresscode.Ifoperatorequalsto“：=”.(1)P1isvariablein“Tab”,wecanreplaceP1inthreeaddresscodebyitsvalueVin“Tab”..38(2)P1isconstant,wecanfindP2in“Tab”,ifP2isin“Tab”,wereplacevalueofP2byvalueofP1,ifP2isnotin“Tab”,store（P2，P1）to“Tab”,add1topointeriof“Tab”..(3)P1isnotconstantandthereisP2in“Tab”,deleteP2anditsvaluefrom“Tab”..392.IfbothP1andP2areconstant,wecancombinethem,namely,replace（ω，P1，P2）by（α，P1ωP2，0）,formatofP1inthreeaddresscodeequalsP1ωP2here,formatP2inthreeaddresscodeequals0,αpresentstheresultofP1ωP2..3.IfP1orP2isthenumberofthreeaddresscode,andtheoperatorinthreeaddresscodebelongstothisnumberequaltoα,thenweuseP1inthreeaddresscodewhichbelongstothisnumberreplaceP1orP2inpresentthreeaddresscode.404.Ifiistheendnumberofthreeaddresscode,thenexit;ontheotherhand,ifiisnottheendnumberofthreeaddresscode,theni：=i+1,andreturntostep1.5.Thethreeaddresscodeswhichtheiroperatordoesnotequaltoαareoptimizedthreeaddresscodes.41WecanoptimizeExample10.1bytheoptimizationalgorithmabove.（1）（：=，10，a）（2）（+，a，20）（3）（：=，（2），b）（4）（/，b，a）（5）（：=，（4），c）（1）（：=，10，a）（2）（α，30，0）

(3)（：=，30，b）（4）（α=，3，0）（5）（：=，3，c）（1）（a,10）（2）（a,10）（3）（a,10）（b,30）（4）（a,10）（b,30）（5）（a,10）（b,30）（c,3）threeaddresscode

optimizing

symboltableofit42Theoptimizedthreeaddresscodeis（1）（：=，10，a）（3）（：=，30，b）（5）（：=，3，c）4310.4Optimizationsofquadruples

Actually,deadcodeeliminationisdoneinablock.Weshalltakeablockofquadruplesforexampletointroducewhichinstructionisextracodeandshouldbeeliminated..

44Example10.2

a：=b*c+a；d：=b*c+a;c：=b*c+a（1）（*，b，c，T1）（2）（+，T1，a，T2）（3）（：=，T2，，a）（4）（*，b，c，T3）（5）（+，T3，a，T4）（6）（：=，T4，，d）（7）（*，b，c，T5）（8）（+，T5，a，T6）（9）（：=，T6，，c）

Ablockfouraddresscodeoftheblock45Fromthecodeabove,weknowthatinstruction4and7aresamewithinstruction1,inaddition,theyhavethesameresults.Instruction8doesthesamewithcalculationofinstruction5.Inordertooptimizethecode,instruction4,7and8shouldnotbecomputed,becausetheycanbereplacedbyothers..Howtojudgetheextrainstructionsautomatically?Wecanusethedependingalgorithmtorecognizeit.46Dependingalgorithm

(1)Atfirst,wedefinethatdependingnumberforeveryinstructionis0,namely,dep(X)=0.(2)Iftheformatoffouraddresscodeis（ω，A，B，Ti）,thendep（Ti）=max（dep（A），dep（B））+1(3)Ifvariable“a”isendowedvaluebyinstructioni,thatis（：=，b，，a）,thendep（a）=i(4)Iftwoinstructioniandj(i<j)havethesameformatlike（ω,P1,P2,),andtheirdependingnumberissameaswell,wecanjudgethatinstructionjisextraandwouldnotbecomputedanymore,theinstructioncanbechanged

（Same，Ti，Tj，0）47especially,ifωisaoperatorwhichpositionofoperandscanbeexchanged,wecansay（ω,P1,P2,)havesameformatwith（ω,P2,P1,）.

Withthehelpofdependingalgorithm,theoptimizedcodeofexample10.2isshownbytable10.1..484910.5Optimizationsoftargetcode

Theaimofoptimizedcodeistogenerateitstargetcode,sothissection,wewilltakeexpressionforexampletoexplainhowtooptimizetargetcode.Example10.3

Anexpression:a*b+c/d+a*(a*b+c/d)-a*(c/d+b*a)/dThetargetcodeoftheexpressionis:50CLAa/*push“a”tostack*/MULb/*“a”fromstackmultiple“b”,andthenpushthecomputingresulttostack*/STOT1/*storetheresultofstacktoT1*/CLAc/*push“c”tostack*/DIVd/*value“c”fromstackdividedby“d”,andthenpushthecomputingresulttostack*/ADDT1/*valuefromstackaddT1,andthenpushthecomputingresulttostack*/STOT1CLAaMULbSTOT2/*storetheresultofstacktoT2*/CLAcDIVdADDT2MULa/*valuefromstackmultiple“a”,andthenpushthecomputingresulttostack*/ADDT1STOT1CLAcDIVdSTOT2CLAbMULaADDT2/*valuefromstackaddT2,andthenpushthecomputingresulttostack*/MULaDIVd/*valuefromstackdividedby“d”,andthenpushthecomputingresulttostack*/RUBT1/*T1minusthevaluefromstack,andthenpushthe