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

. .v2).subroutine c (p3, p4)integer x,y,z,p3,p4common/global/x,y,z...p2)p2=pl*3V2 = 17a:Unnecessaryv2)V2 = V2 * x...endFig.2.Example program fragment.Data-flowproblemTypeGlobal commonsubexpressionsAVAILICode hoistingVERYBUSYFlowtypeall-pathforwardIall-pathbackwardforwardbackwardGlobal constantpropagationREACHIaugmentedany-pathRegister storeeliminationLNEIIany–pathFig.3.FlowDirectionSummary of examples.V2 asan actualata and p; y simply passes thec. The summary sets for the program fragmentthe constant valued variablevalue through to procedurewould be:CallsiteMODREFa{x}{V2}P{V1,V2}{V1,V2}Y{pi}{p2}.The only statements that either modify oruse the value ofa variable are thethree assignments.The MOD and REF informationarises from the assignments in procedures b and c, along with parameter bindings at the variouscall sites.4.

THE GENERALFRAMEWORKWe have formulatedour techniques for recompilationanalysis as a test thatdetermines when a procedure must be recompiled. All of our techniques applythe same test; they compare the current interproceduralinformationfor aACM Transactionson ProgrammingLanguages and Systems, Vol. 15, No 3, July 1993.374M. Burke.andL, Torczonprocedure against previouslyrecorded annotationsets. The annotationsetscontain those interproceduralfacts that can be true without invalidatingtheprocedure’sprevious compilation.Our specific implementationtechniquesdiffer in the precision with which they assign values to these annotationsets.We attach the following sets to the program’s call graph:(1)for each procedure p—theset of alias pairs that arewithoutforcing a recompilation.If a change adds a pair tothat is not in MayBeAlias(p ), recompilationis required.MayBeAlias(p),allowedALIAS(p)for each call graph edge e—the set of variables that maybe(2) MayMod(e),modified as a side effect of the call without forcing a recompilation.If achange adds a variable to MOD(e) that is not in MayMod( e), recompilation is required.for each call graph edge e—the set of variables that may be(3) MayRef(e),used as a side effect of the call withoutforcing a recompilation.If arecompilationchange adds a variable to REF(e ) that is not in MayRef(e),is required.p), for each procedure p—the set of constant pairs that(4) MustBeConstant(is to be avoided.

Ifmust hold on entry to procedure p if recompilationp ) that is not in CONSTANTS(p), recompilationM x, v) = MustBeCorzstant(is required.Given these sets, the recompilationtest can be expressed quite simply. Aprocedure p must be recompiled if either p changed or the interproceduralinformationassociated with p changed and any of the following are true:(a) ALIAS(p)(b) Mode)(c)REF(e)– MayBeAlias(– MayRef(e)(d) MustBeConstant(p) # 0,+ 0, for any call site e in p,– MayMod(e)+ 0, for any call site e in p, andp) - CONSTANTS(p) # D.Set subtractionis defined so that a G (X-Y) if and only if a is a member of Xand not Y.To construct a list of procedures needing recompilation,the recompilationtool first initializesthe list to include every procedure where a nontrivialediting change has been made.

Trivial changes do not alter the code generated for the procedure; this includes format changes or changes to comments.Next, it updates the program’s ALIAS, MOD, REF, and CONSTANTS sets. (Ideally,incrementaltechniquesshould be used to update these sets [6, 11, 12].)Whenever this update changes the value of one of these sets, the compilerapplies the appropriatetest. If the test indicates that recompilationis necessary, the correspondingprocedure is added to the recompilationlist. Becausethe analyzer only tests sets that change during the incrementalupdate, thetest requires a number of set operations proportionalto the size of the regionof changed data-flow information.ACM TransactIonson ProgrammmgLanguages and Systems, Vol 15, No 3, July 1993,Interprocedural Optimization: Eliminating Unnecessary Recompilation.As an example, consider the followingtion sets.

For each procedure p letMayBeAlias(p)375of values to the annota-andp ) = 0Mz@BeConstant(assignment.= {(x,Q ), for all x declaredwhere x ranges over the parametersconstant value that appears nowhereMayMod(e)MayRef(e)in the program},and global variables of p and Q is ain the program. For each call site e let= 0and= 0.With these annotationsets, the compiler will recompileevery procedurewhere either the source text or some associated interproceduralset haschanged. It will not recompile procedures for which the informationis unchanged because the test is not applied at those procedures.

Hence, this testis a slight improvementover the naive approach of recompilingevery procedure.Consider the impact of deleting the assignment statement from procedureb in the example program. To determine which procedures must be recompiled, the analyzer begins with b, the changed procedure. After updating theinterproceduralinformation,it discovers that only two sets have changed:MOD( /3) = {vI} and REF( ~ ) = {v2}. Because sets associated with procedure ahave changed, it applies the test to a and slates it for recompilation.Sincenone of the sets associated with c have changed, the analyzer ignores c.Thus, it determines that only a and b must be recompiled.The effectiveness of the testing procedure used by the recompilationtoolMayMod,MayRef,depends entirely on the values assigned to MayBeAlias,and MustBeConstant.To improve the precision of the test involves expandingMayBeAlias,MayMod,and MayRefto include more allowed facts, or shrinkto exclude more facts.

Three instantiationsof thising MustBeConstantgeneral frameworkare presented in the following sections. The methods arepresented in increasingorder of complexity;each successive method givesrise to a recompilationanalysis of improved precision. Two simple methodsfor constructingconservativeapproximationsto precise annotationsets aredescribed in the next two subsections. They rely on informationthat thecompiler produces when computinginterproceduralinformation.Sections 5MayBeAlias,MayMod,and 6 discuss a technique for precisely computingand MustBeConstant.This technique is substantiallymore complexMayRef,than the other methods described; it requires that the compiler produceannotation sets that indicate which interproceduralfacts it relied upon whenperformingoptimizations.4.1 Most Recent CompilationOur first approach to computing the annotationsets simply remembers thevalues of ALIAS, MOD, REF and CONSTANTSused in the most recent compilaACMTransactionsonProgrammingLanguagesandSystems,Vol.

15, No 3, July 1993.376.M, Burke and L, Torczontion of the procedure.In other words, wheneverwe compilea procedurep, weset(1)p ) = ALIASOLD( P),MayZ3eAlias((2) Mciyllod(e)(3)Mayl?ef(e)= MODOLD(e), for each call site e in p,= REFOLD(e), for each call site e in p, and(4) MustBeConstant(These annotationp) = CONSTANTSOLD(P).sets yield the followingrecompilationtests:(a) ALIAS~~W( p) – ALIASOLD(P) = 0,(b) MOD~~W( e) – MoDo~~(e)+ 0, for any call site e in p,(c) REFNEW(e) – REFoLD(e) + @, for any call site e in p, and(d) CONSTANTSOLD(p) – CONSTANTSNEW(P)# @where OLD indicates interproceduralinformationassociated with the procedure when it was last compiled and NEW indicates interproceduralinformation that has been updated for the current compilationof the procedure.This set of assignments reveals the principles underlyingthe recompilationtests.

The summaryand aliasingsets identifyevents whose occurrencecannot be ruled out by the analysis. For example, if a variable is in the MODset for a given call site, the compiler must assume that it may be modified,but if a variable is absent from the same set, the compiler may safely assumethat the value of that variable will be unchanged upon return from the call.In other words, in considering the ALIAS, MOD, and REF sets, the compiler canis safe when aonly depend on what is not in the sets. If an optimizationvariable is present in one of these sets, that optimizationwill still be safe ifthe variable is removed because the compiler must have already consideredthe possibilitythat the associated event might not occur. Hence, changes inthese sets necessitate recompilationonly when they expand the sets.