1993. Interprocedural Optimization – Eliminating Unnecessary Recompilation, страница 9

Computingannotationsets that actuallyreflect compile-timedecisions will probablyincrease the compile times for individualmodules. However, it will also makewhat needs to beit possible for the compiler to more precisely determinerecompiled when an editing change is made—potentiallyleading to a reduction in the numberof proceduresthat need to be recompiled.Under ascenario where either editing changes are expected to be frequent or compilation is expensive due to the aggressive analysis and optimizationemployed bythe compiler, the additionalcompile time cost associated with using preciserecompilationanalysis may be offset by the reductionin the number ofrecompilation.6. DIRECT USE OF INTERPROCEDURALFACTSSo far, our discussion has concentratedon finding the recompilationdependence that arise from the contributionof interproceduraldata-flow information to global data-flowinformation.Once interproceduralinformationismade available to the compiler, it is reasonable to expect that the optimizerwill make direct use of the facts where appropriate.To preserve correctnessin compiled code, our methods of computing annotation sets must account forsuch direct use.As an example, consider the code that gets generated for a procedure call ina language with call-by-referenceparameter passing.

For simplicity,assumethat all registers that are preserved across the call are saved in the callingroutine. If the compiler ambitiouslykeeps values in registers, then it is likelythat one or more of the actual parametersat the call site will not have acurrent copy in storage—thatis, in memory rather than in a register.l”Thus,before the call, the compiler must generate code to store each of the actualparameters and global variables for which the store is not current. Similarly,10The optimizingcompiler for R“ tries to keep all scalar values in registers.

Nonaliased globalscalars are assumed to have a correct and consistent storage representationonly at call sites andonly in theprocedure entry and exit. A local scalar v is assumed to have a storage representationneighborhood of a call where it is passed as an actual parameter. It is stored immediatelyprior tothe call and restored afterward.The other mechanism hy which a local scalar variable getsmoved from a register to storage is when the register allocator decides that it must spill thevariable.ACM Transactionson ProgrammingLanguages and Systems, Vol. 15, No. 3, July 1993,394.M. Burke and L. Torczonafter the call, it may need to refresh the register copies of such values fromthe store, to ensure that they are current.If the optimizer has interproceduralMOD and REF sets for the call site, itcan do better.

Any parameter or global variable that is in a register before thecall site and is not contained in the set (MOD(e) U REF(e)) need not be storedbefore the call. Thus, the compiler need not generate either the addresscomputationor the store instruction.Similarly,any parameterthat is notcontainedin MOD(e) need not be refreshedafter the call, allowingthecompiler to eliminate both the address computationand the load instruction.The APPEARS test presented in Section 4.2 will correctly model the recompilation dependenceintroducedby such optimizations.In fact, eliminatingstores before the call has the effect of making the APPEARS test for MOD andREF informationprecise for global variables.

If a global variable that appearsin the calling procedure is added to either the MOD or REF set at some callsite, recompilationwill be needed to insert the store for that parameter beforethe call site. Otherwise, either a reference inside the called procedure or therestore after the call can receive an incorrect value.If a more precise annotationset is being computed, in the manner described in Section 5, the compiler will need to record such direct use of factsin the appropriateannotationsets.

Thus, for each store eliminatedbefore thecall site e, the compiler would need to remove the variable from MayMod(e)and MayRef(e).Similarly,for each refresh eliminatedafter e, it would needto remove the variable from MayMoci( e).When the compiler directly uses ALIAS informationin its compilation,it isdifficultto produce precise recompilationinformation.This is due to themanner in which the compiler employs ALIAS information.When two variables are potential aliases, the compiler must preserve the relative orderingof their loads and stores. Doing this requires either that the compiler track,pairwise, all uses and definitionsof each alias pair, or that it simply treatpotential aliases extremely conservatively.Because of the expense and complication involved in the former approach, all compilers with which we arefamiliaradopt the latter strategy. Since the compiler does not track situations where it reorders loads and stores for variables that are not potentialaliases, it is difficultto determinewhen the compiler has relied upon theabsence of a particularalias pair from ALIAS(p).

This informationis necesp ) sets. Thus, when ALIAS informasary for computing precise MayBeAlias(tion is used directly in a compiler, efficiency may dictate that the APPEARStest discussed in Section 4.2 be employed.7. LARGERCOMPILATIONOPTIMIZATIONUNITS AND INTERPROCEDURALOur compilationmodel assumes that each procedure is a distinct compilationunit. Many compilers treat multiple procedures as an indivisiblecompilationunit, producinga single object file for all the procedures in the unit. Thepresence of multipleprocedures in a single unit slightlycomplicatestheACM TransactIonson ProgrammingLanguages and Systems, Vol.

15, No. 3, July 1993Interprocedural Optimization: Eliminating Unnecessary Recompilation..395recompilationanalysis. When analyzing a unit that contains multipleprocedures, the compiler must recognize that the procedures are related.To handle this situation,the compiler can build a pair of maps: one fromprocedures into compilationunits and the other from compilationunits intoprocedures. Using these maps, the analyzer can mark all of the procedures ina unit for recompilationwhenever any of its constituentprocedures needsrecompilation.This can decrease the total amount of analysis required, sinceit need not test any procedures in a unit already marked for recompilation.This mechanismalso provides a natural way of handling interproceduraloptimizations.For our purposes, an interproceduraloptimizationis an optimization that(1) moves code across a call site,(2) changes the program’sstatic(3) changes the program’sdynamiccall graph,orcall graph.Examples of these are inline substitution,procedure cloning, and parallelizing a loop containing a call site, respectively.Clearly, such transformationsintroduce new compilationdependencebetween the involved procedures.

We can use the maps required for multipleprocedure compilationunits to take account of such transformationsin ourtesting procedure. The idea is simple; whenever the compiler applies aninterproceduraloptimizationto a pair of procedures that belong to distinctcompilationunits, these units are treated as if they were a single unit.

Thisstrategy requiresa straightforwardadjustmentto each of the two mapsdescribed above.To apply the recompilationtest, the analyzer follows the algorithm sketchedin Section 4. First, it marks each procedure that has been changed by editing,along with all procedures belonging to the same unit.

Next, it updates all ofthe interproceduralsets. Then, it applies the recompilationtest to eachprocedure where an interproceduralset has changed. Of course, if the procedure is already marked for recompilation,the analyzer need not apply thetest. If the test indicates recompilation,the procedure is marked, along withevery procedure indicated by the entries in the procedure-to-unitmap.The maps represent the presence of multipleprocedures in a compilationunit and express the compilationdependenceintroduced by interproceduraloptimizations.They ensure that the test behaves correctly and efficiently.Each procedure is analyzed independently.When the tests indicate that someprocedure must be recompiled, the analyzer marks all procedures in the unitfor recompilation.Using the maps can decrease the number of test applications that the analyzer must make.It is importantto recognize the difference between this approach and ahierarchicalapproach like that found in structuraldata-flow algorithms.Ourapproach maintainsseparate data-flowinformationfor each of the procedures, but accounts for the textual relationshipsbetween them.

A hierarchical test would merge graph nodes in some structured way. Merging the nodesACM Transactionson ProgrammingLanguages and Systems, Vol. 15. No. 3, July 1993.396.M, Burke and L. Torczonfor the procedure would simplify the graph, but would result in merging theinformationused in the recompilationtest and losing some precision in thetest information.A fact allowed on entry to one procedure might be disallowed on entry to another; if the procedures are both represented by a singlenode and a single annotationset, the test must indicate recompilationwhenthe fact is added to either path.8. IMPROVEDOPTIMIZATIONWe have seen that changes in interproceduralinformationcan invalidatethesafety of optimizationsapplied in previous compilation.For the MOD, REF,and ALIAS sets, adding facts to a set associated with a procedure possiblymandated recompilingit, while deleting facts did not.

Deletions can, however,open up new possibilitiesfor applying optimizations.Recall that optimization based on MOD, REF, or ALIAS informationrely on the absence of a factfrom the data-flowset ratherthan its presence.Similarly,addinga(name, value) pair to a procedure’s CONSTANTSset can open up opportunitiesfor new optimizationsbased on knowledge of the constant value.As stated, our recompilationtests detect when a procedure must be recompiled to ensure consistency with the program in which it will execute. They donot address the issue of detecting potentialimprovements,although analogous tests can be constructed.For each correctnesstest in the generalframework,a dual test that detects opportunitiesfor improved optimizationcan be constructed.

We introduce four annotationsets for the improvementWereRef,WereAliased,and WereConstant.For each newtest: WereMod,annotationset, we can formulatea test to predict when recompilationmaylead to improved optimization:(a) WereAliased((b) WereMod(e)(c) WereRef(e)p) – ALIAS NEW(P) +0,– MOD NEW( e) + 0, for any call site e in p,– REF NEw(e)+ @, for any call site e in p, and(d) CONSTANTINEW(p) – WereConstant(p ) # @.Again, set subtractionis defined so that a E (X – Y) if and only if a is amember of X and not Y. The next subsection describes one possible formulation of these annotationsets and shows how to compute the resultingrecompilationtests.8.1 Defining the AnnotationSetsIn Section 4.2, we described the approximateannotationsets for the correctness test based purely on static information.Approximateannotationsets forthe improvementtest can be defined in a similar manner.

At each compilaused totion of a procedure p, the compiler can compute the informationconstruct the four annotationsets, based on the interproceduraldata-flowsets described in Section 3 and the APPEARS sets described in Section 4.2.Specifically,the sets can be described as:(1) WereAliased((2) WereMod(e)ACM TransactIonsp) = ALIAS OLD(P) n ALIASAPPEARS(p),= MODoLD(e) n Appears,on Programmingforeachcallsitee inLanguages and Systems, Vol 15, No 3, July 1993p,Interprocedural(3) WereRef(e)Optimization:EliminatingUnnecessaryRecompilation..397= REFo~~(e) n APPEARS(P), for each call site e in p, and(4) WereConstant(p)= {(n, v) @ CONSTANTSO..(P)I n ~ APPEARS(P)}.The rationalefor these assignmentsis analogous to that underlyingcorrectness test in Section 4.2.

Substitutingthese annotationsets intorecompilationtests in Section 8 and refactoringthe equations yieldsfollowing recompilationtests:(a) (ALIASO.D(P)– ALIAS~EW(p))thethethen ALIASAPPEARS(P) # 0,(b) (MODo~~(e) – MOD~EW(e)) n APPEARS(P) # 0, for any call site e in p,(c)(REFoLD(e)– REFNEW(e)) f’ APPEARS(P) # 0, for any call site e in p, and(d) {(n, v) G (CONSTANTS~EW(p) – CONSTANTSo.~(p)) I n●APPEARS(p)} # 0.Note that refactoringeliminates the need to instantiateWereconstcmt( p).It does not seem reasonable to examine techniques for constructingmoreprecise versions of these sets. That would require the compiler to considereach interproceduralfact and determinewhetheror not there existed anoptimizingtransformationthat the fact prevented. We believe that this typeof analysis would be both difficult to implementand expensive to execute.8.2 Practical ApplicationWhenever recompilationanalysis indicates that a procedure must be recompiled for correctness, the compilationsystem will recompile it.