1994. Compiler Transformations for High-Perforamce Computing, страница 2

Baconet al.However,in Section5 we introducedependenceanalysistechniquesthatareused for decidinguponand verifyingmany loop transformations.Step (1) is the most difficultand poorlyunderstood;consequentlycompilerdesign is in manyways a blackart. Because analysisis expensive,engineeringissues oftenconstrainthe optimizationstrategiesthat the compilercan perform.Evenforrelativelystraightforwarduniprocessortargetarchitectures,it ispossiblefor a sequenceof optimizationsto slow a programdown. For example,anattemptto reduce the numberof instructions executed may actuallydegrade performanceby makingless efficientuse ofthe cache.Asprocessorarchitecturesbecomemore complex,(1) the numberof dimensions in whichoptimizationis possibleincreasesand (2) the decisionprocess isgreatlycomplicated.Some progresshasbeen made in systematizingthe applicationof certainfamiliesof transformations, as discussed in Section 8.

However,all optimizingcompilersembody a set ofheuristicdecisionsas to the transformation orderingslikely to work best for thetarget machine(s).2.1CorrectnessWhen a programis transformedby thecompiler,the meaningof the programshouldremainunchanged.The easiestway to achieve this is to requirethat thetransformedprogramperformexactly thesame operationsas the original,in exactly the order imposed by the semanticsof the language.However,such a strictinterpretationleaves littleroom for improvement.Thefollowingis a morepracticaldefinition.Definition2.1.1A transformationislegalif the originaland the transformedprogramsproduceexactlythe same outexecutions.put for all identicalTwo executionsof a programare identicalexecutionsif they are suppliedwiththe same inputdata and if every correspondingpair of nondeterministicopera-ACMComputmgSurveys,Vol26,No4, December1994tions in thesame result.twoexecutionsproducestheNondeterminismcan be introducedbylanguageconstructs(such as Ada’s select statement),or by calls to system orlibraryroutinesthat returninformationabout the state externalto the program(such as Unix time( ) or read()).In some cases it is straightforwardtocause executionsto be identical,for instance by enteringthe same inputs,Inother cases there may be supportfor determinismin the programmingenvironment—forinstance,a compilationoptionthat forces selectstatementsto evaluatetheir guards in a deterministicorder.

Asa last resort, the programmermay haveto replacenondeterministicsystem callstemporarilywithdeterministicoperations in order to compare two versions.To illustratemanyof thecommonproblemsencounteredwhen tryingto optimizea programand yet maintaincorrectness,Figurel(a) shows a subroutine,Figurel(b) is a transformedversion of it.The new versionmay seem to have thesame semanticsas the original,but itviolatesDefinition2.1.1 in the followingways:a Overflow.If b[k] is a very large number, and a[l ] is negative,then changing the order of the additionsso thatC = b [k] + 100000.0is executedbeforethe loop body could cause an overflowto occur in the transformedprogramthat did not occur in the original.Evenif the originalprogramwouldhaveoverflowed,the transformationcausesthe exceptionto happenat a differentpoint.Thissituationcomplicatesdebugging,notvisiblesincetothethetransformationprogrammer.isFinally,if therehadbeena print statementbeand use of C,tweenthe assignmentthetransformationwouldactuallychange the outputof the program.Evenif nooverflow* Differentresults.occurs, the values that are left in thea may be slightlydifferentbearraycause the orderof the additionshasbeen changed.

The reason is that float-Compilersubroutinetrickyintegerrealn,m,a[m],(a,b,n,m,k)b[m]doi=l,na[i]end= b[k]+ a[i]+ 100000.0doreturn(a) originalsubroutinen,realm,a[m],=programtricky(a,b,n,m,k)integerCb[k]kb[m],+doi=n,C100000.0i,-1a[i]=enda[i]+Cdoreturn(b)k=●ktransformedprogramm+ln=Ocalltricky(a,b,n,m,k)(c)equivalencepossiblecallto(a[l],b[n])trickytricky(a,b,n,m,k)(d)Figure 1.Incorrectpossibleprogramcall●349Memoryfault.If k > m but n < 1, theThe referreferenceto b[k] is illegal.ence wouldnot be evaluatedin theoriginalprogrambecause the loop bodyis never executed, butitwould occurinthe call shownin Figurel(c) to thetransformedcode in Figurel(b).e Differentresults.

a and b may be completelyor partiallyaliasedto one another, changingthe values assignedtoa in the transformedprogram.Figurel(d) shows how this might occur: If theb[k]call is to the originalsubroutine,is changed when i = 1, since k = n andb [n] is aliasedto a[l ]. In the transformed version,the old value of b [k] isused for all i, since it is read before theloop. Even if the referenceto b[k] weremoved back inside the loop, the transformedversionwouldstill give different resultsbecause the loop traversalorder has been reversed.As a resultof these problems,slightlydifferentdefinitionsare used in practice.Whenbitwiseidenticalresultsare desired, the followingdefinitionis used:Definition2.1.2A transformationislegal if, for all semanticallycorrect programexecutions,the originaland thetransformedprogramsproduceexactlythe same outputfor identicalexecutions.k=ncallTransformationsto trickytransformations.ing-pointnumbersare approximationsofrealnumbers,andtheorderinwhichthe approximationsare applied(rounding) can affect the result.

However,fora sequenceof commutativeand associativeintegeroperations,if no orderof evaluationcan cause an exception,then all evaluationorders are equivalent. We call operationsthat are algebraicallybutnotcomputationallycommutative(or associative)semicommutative(or semiassociative)operations. These issues do not arise withBooleanoperations,since they do notcause exceptionsor computeapproximate values.Languagestypicallyhave many rulesthat are stated but not enforced;for instance in Fortran,array subscriptsmustremainwithinthe declaredbounds,butthisruleis generallynot enforcedatcompileor run-time.A programexecution is correctif it does not violatetherules of the language.Note that correctness is a propertyof a programexecution, not of the programitself,since thesame programmay execute correctlyunder some inputsand incorrectlyunderothers.Fortransolves the problemof parameter aliasingby declaringcalls that aliasscalarsor parts of arraysillegal,as inFigurel(d).

In practice,many programsmake use of aliasinganyway.While thismay improveperformance,it sometimesleads to very obscure bugs.ACMComputingSurveys,Vol.26,No.4, December1994350David“F. Baconet al.For languagesand standardsthat define a specificsemanticsfor exceptions,meetingDefinition2.1.2tightlyconstrainsthepermissibletransformations. If the compilermay assumethatexceptionsare only generatedwhen theincorrect,aprogramis semanticallytransformedprogramcan producedifferent results when an exceptionoccurs andstillbe legal. Whenexceptionshave awell-definedsemantics,as in the IEEEfloating-pointstandard[AmericanNationalStandardsInstitute1987], manytransformationswill not be legal underthis definition.However,demandingbitwiseidenticalresults may not be necessary.

An alternative correctnesscriterionis:Definitionlegal if, forallsemanticallyecutionsoftheoriginaloriginalandperformequivalentcal2.1.3Atheexecutions.forPerfect loop nest. A loop nest is a set ofloops one inside the next. The nest iscalled a perfect nest if the body of every loop other than the innermostconsists of only the next loop in the nest.Becausea perfectnest is more easilysummarizedand reorganized,severaltransformationsapply only to perfectnests.eGeneralloop nest.perfect or not.●Procedure.Some optimizations,memory access transformationsin particular, yield betterimprovementsif theyare appliedto an entireprocedureatonce. The compilermustbe able tomanagethe interactionsof all the basic blocks and controltransferswithinthe procedure.The standardand ratherconfusingterm for procedure-leveloptimizationin the literatureis globaloptimization.0InterProcedural.Consideringseveralproc~durestogetheroften exp~ses moreopportunitiesfor optimization;in particular,procedurecall overheadis often significant,and can sometimesbereducedoreliminatedwithinterproceduralanalysis.identiofare0theprogramspermutationsoperationsloop.

To targethigh-performancearchitectureseffectively,compilersneed to focus on loops. Most ofthe transformationsdiscussedin thissurvey are based on loop manipulation.Manyof themhave been studiedorwidelyappliedonly in the contextofthe innermostloop.ex-program,operations* InnermostiscorrecttransformedAllcommutativetransformationniques.The advantagefor analysisisthat there is only one entry point,socontrol transferneed not be consideredin trackingthe behaviorof the code.semi-consideredequivalent.Since we cannot predictthe degree towhichtransformationsof semicommutative operationschangethe output,wemust use an operationalratherthan anobservationaldefinitionof equivalence.Generally,in practice,programmersobserve whetherthe numericresultsdifferby more than a certaintolerance,and iftheydo, force the compilerto employDefinition2.1.2.2.2ScopeOptimizationsgramatcandifferentAs the scope of thelarged,thecreases.complexitycostbe appliedlevel~ofSomeoftotransformationanalysisusefula pro-granularity.isgenerallygradationsinofare:0 Basic block (straight-linecode).

This isthe focus of earlyoptimizationtech-In thissurveytechniquesforSurveys,Vol.26,No4, Decembernesting,We will generallyconfineour attentionto optimizationsbeyondthe basic blocklevel.3. TARGETComputmgloopen-* Statement.Arithmeticexpressionsarethe main source of potentialoptimization withina statement.ACMAny1994ARCHITECTURESwe discusscompilationhigh-performancearchi-CompilerTransformations●351tectures,which for our purposesare superscalar,vector, SIMD,shared-memorymultiprocessor,and distributed-memorymultiprocessormachines.These architectures have in commonthat they all useparallelismin some formto improveperformance.The structureof an architecturedictateshow the compilermustoptimizealong a numberof different(and sometimes competing)axes.

The compilermustattemptto:ware detects that the resultof a vectormultiplyis used by a vectoradd, anduses a strategycalled chainingin whichthe resultsfrom the multiplier’spipelineare fed directlyintothe adder.Othercompoundoperationsaresometimesimplementedas well.Use of such compoundoperationsmayallow an applicationto run up to twice asfast. It is thereforeimportantto organizethe code so as to use multiply-addswherever possible.e maximizeuse ofsources(processors,vector units),3.1 Characterizingcomputationalfunctionalreunits,.

minimizethenumberof operationsperformed,●minimizeuse of memorybandwidth(register,cache, network),and- minimizerequired.thesizeoftotalmemoryWhile optimizationfor scalar CPUS hasconcentratedon minimizingthe dynamicinstructioncount (or more precisely,thenumberof machinecyclesrequired),CPU-intensiveapplicationsare often atleast as dependentupon the performanceof the memorysystem as they are on theperformanceof the functionalunits.In particular,the distancein memorybetweenconsecutivelyaccessed elementsof an arraycan have a majorperformance impact. This distanceis called thestride. If a loop is accessing every fourthelementof an array, it is a stride-4loop.If every elementis accessed in order, it isa stride-1loop. Stride-1access is desirable because it maximizesmemorylocality and thereforethe efficiencyof thecache, translationlookasidebuffer (TLB),and pagingsystems;it also eliminatesbank conflictson vector machines.Anotherkey to achievingpeak performance is the paired use of multiplyandadd operationsin which the resultfromthe multipliercan be fed into the adder.For instance,the IBMRS/6000has amultiply-addinstructionthatuses themultiplierand adder in a pipelinedfashion; one multiply-addcan be issued eachcycle.

The Cray Y-MP C90 does not havea singleinstruction;insteadthe hard-PerformanceThere are a numberof variablesthat wehave used to help describethe performanceof the compiledcode quantitatively:eS is the hardwarespeed of a singleprocessorin operationspersecond.Typically,speed is measuredeitherinmillionsof instructionspersecond(MIPS)or in millionsof floating-pointoperationsper second (megaflops).eP is the numberof processors.0F is the numberby a program.of operations0T is the timegram.eU = F/STis the utilizationof the machine by a program;a utilizationof 1 isideal, but real programstypicallyhavesignificantlylowerutilizations.A superscalarmachinecan issue several instructionsper cycle, but if the programdoes not containa mixtureof operations that matches the mixtureof functionalunits,utilizationwill be lower.Similarly,a vector machinecannot beutilizedfully unless the sizes of all ofthe arrays in the programare an exactmultipleof the vector length.0Q measuresreuse of operandsthat arestored in memory.It ii the ratio of thenumberof times the operandis referenced duringcomputationto the number of times it is loaded into a register.As the value of Q rises, more reuse isbeing achieved,and less memory bandwidthis consumed.Values of Q belowACMComputingSurveys,in secondsVol.26,No.executedto run4, Decembera pro-1994352e1 indicateoccurring.DavidF.