1993. Interprocedural Optimization – Eliminating Unnecessary Recompilation (1157408), страница 4
Текст из файла (страница 4)
Thus, adeletion cannot invalidatethe correctness of previous compilations,althoughit can create a new opportunityfor optimization.This principlemotivatestests (a), (b), and (c).On the other hand, the CONSTANTS(p) set contains facts that are true onevery path leading to an invocationof p. Thus, if a pair (x, u) is in CoNSTANTS(p ), the compiler can rely on x having value u on entry to p and canreplace references to x, on paths where x is unmodified,with the constantvalue u. If a subsequent editing change removes (x, u) from CONSTANTS(p),this forward substitutionby the constant value is invalidated.Thus, removing a fact from CONSTANTS(p) may mandate a recompilation.An addition toCONSTANTS(p) cannot invalidatea previous compilation,but it can open upnew opportunitiesfor optimization.This provides the rationale for test (d).Consider once again the impact of deleting the assignment statement fromprocedure b in our example, assuming that annotationsets have been generated using informationfrom the most recent compilation.The analyzerlist berepeats the steps described earlier, placing b on the recompilationcause of the editing change and applying the test to procedure a because ofchanges to MOD( /3) and REF( ~).
The test indicates that procedure a need notACM TransactIonson ProgrammmgLanguagesand Systems,Vol. 15,No 3, .July 1993Interprocedural Optimization: Eliminating Unnecessary Recompilation..377be recompiled, since both of the changes are deletions from flow-insensitivesummary sets. Thus, with these annotationsets, the same testing procedurelimits the recompilationlist to procedure b.4.2APPEARSInformationAlthoughthe direct use of informationfrom the most recent compilationyields a recompilationtest that is significantlybetter than the naive approach, it fails to take full advantage of the informationthat the compilercould make available.
For example, the test from Section 4.1 will recompile aprocedure whenever a variable is added to its MOD set, even if that variabledoes not appear in any executable statement in the procedure. Determiningwhich variablesactually appear in the procedure leads immediatelyto animproved test.
The compiler can easily produce the additionalinformationneeded to support such a scheme. The sets must be computed anyway as partof the initial informationfor computing the MOD and REF sets.To describe the annotationsets for this improved test, we define threeadditionalsets. For a procedure p, APPEARS(p) is the set of variables eitherused or modified inside p. If the only occurrence of a variable inside p is asan actual parameterat some call site in p, then the variable need not beincluded in APPEARS(p). APPEARS’(p) is defined to be the set of all variableseither used or modifiedin p or some procedure invoked as a result ofexecuting p. Both APPEARS(p) and APPEARS+(p) can be computed triviallyfrom informationproduced in the summarycomputation.Finally,the setALIASAPPEARS( p ) describes pairs of variables, where one element of the pairappears locally in p and the other element appears in p or one of theprocedures that can be executed as a result of invoking p.3 This set is definedasALIASAPPEARS(p)= {(x,y)l XGAPPEARS(p)Given these sets, the annotationfollows:(1) MayBeAlias(p)(2) MayMod(e)= ALIASOLD(p)sets at compileand y ~AP1’EARS+(P)}.timecan be computedasu ALIASAPPEARS( p),= MODoLD(e) U APPEARS(p), for each e in p,3Note that when dealing with aliased pairs of variables, it is important to consider aliasesthatcan arise between a variable in p and a variable in a procedure q invoked either directly orindirectly by p.
ALIASAPPEARS( p ) accounts for all such aliases that could arise in futurecompilations.However, in most compilersthat employ interprocedural information, the recompilation test for ALIAS information would be used in conjunction with the recompilation tests forMOD and REF information. In this case,the AIJAS test could simply determine whether or notboth members of the alias pair were in APPEARS(p) and avoid computing the more complexALIASAPPEARS( p ) information. The resulting tests would correctly detect the necessaryrecompiand y G APPEARS(9)would cause x tolation becauseadding an alias between x G APPEARS(p)be added to the MOD and/or REF sets for the call invoking q from p.
The MOD and REFrecompilation tests would then determine that p should be recompiled.ACM Transactionson ProgrammingLanguages and Systems, Vol. 15, No. 3, July 1993.378M, Burke and L. Torczon.(3) MczyRe~(e) = REFo~~(e)(4) ~~stBeCOnstalLt(Up)={(~,APPEARS(p), for each e in p, andz~)~CONsT~TSo.~(p)l~~APPEA@P)}.Substitutingthese annotationsets into the recompilationyields the following recompilationtests:tests in Section4(a) (ALIASNEW( p ) – ALIASoLD(p )) n ALIASAPPEARS(P) + 0,(b) (MoDNEw(e)(c)– MODOLD(e)) n ApPEMs(p)# 0, for any call site e inp,(REFN~w(e) – REFoLD(e)) n APPEARS(p) + @, for any call site e in p, and(d) {(n, U)●(CONSTANTSo~.(p)– CONSTANTS~~W(p ))In●APPEARS(p)} + 0.Note that the tests have been refactoredto avoid instantiatingsets likeemployed in theAPPEARS(p) and ALIASAPPEARS( p ).
These tests are currentlyR” programmingenvironment[18]. In practice, they have proven to be bothefficient and effective.Computingthe annotationsets from these definitionseliminatesspuriousrecompilationthat arise from informationabout irrelevantvariables.Inpractice, this is important—proceduresoften contain declarationsfor globalvariablesthat they never reference. FORTRANcodes often contain largeCOMMON blocks that define many global variables; a given procedure mayonly use a subset.
In other languages, widespread use of include files causesthe same phenomenon. In fact, this is one of the phenomena that motivatesTichy and Baker’s work with include files-theirsystem avoids recompilingprocedures that rely on a changed include file if the change only involvesdeclarationsthat are actually irrelevantto the procedure [30].To see this more graphically,consider adding the statementx=p4*17procedure c in the example from Figure 2. This changes MOD(Y) to {p 1, x}test, this wouldand MOD( /3) to {vI, V2, x}. Under the most recent compilationthehave required recompilationof both a and b. Using APPEARS information,but b does not, since x does nottest determines that a requires recompilation,appear in b.A word of caution is required at this point.
There are optimizationsthat, onfirst consideration,appear to be limitedto a single procedure but are, inreality, inherentlyinterprocedural.A prime example is converting a sequential loop into a parallel loop. If the loop contains no call sites, the transformation’s scope is limited strictly to the single procedure. If, however, the loopcontains a call site, the transformationis really interproceduralin its scopebecause it changes the dynamic call graph of the program.If the calledprocedure contains a local, static variablex with an upwards-exposeduse,followed by an assignment to x, the dependence between the definitionof xin one iterationand the use of x in the subsequentiterationmust bepreserved.
Burke and Cytron refer to such variables as “hidden variables” [7].As we have formulatedthem, the recompilationtests determinewhen anintraproceduraloptimizationcan be invalidatedby a subsequent change inan interproceduralset. If x is a local, static variable in the called procedure,toACM Transact]cms on ProgrammingLanguages and Systems, Vol 15, No 3, July 1993InterproceduralOptimization:EliminatingUnnecessaryRecompilation..379x will not appear in the MOD or REF sets for the call site and the recompilation tests will not be able to detect when it is necessary to recompile thecalling procedure.
Even if x is a global variable, the APPEARS test will onlyhandle recompilationcorrectly if x appears in the calling procedure. Interprocedural optimizationsrequire a more complex treatment;we describe onesuch method in Section 7.5. COMPILERCOOPERATIONThe techniques presented in Section 4 compute approximateannotationsets.While the best of these techniques can eliminatemany spurious recompilation,the question remains, can we compute more precise annotationsets?Spurious recompilationarise from a simple fact—the compiler cannot capitalize on every interproceduralfact presented to it.
Thus, the APPEARS test ofSection 4.2 may judge that some change in an interproceduralset mandates arecompilation,even though the fact is actually irrelevant,simply because thecompiler had no opportunityto exploit the fact during the previous compilation. This section explores a methodology for computing more precise annotation sets by relying on the compiler to record those interproceduralfacts thatit actually uses.To illustratehow such a method would work, consider constructingtheMustBeConstantsets to be used in determiningwhich proceduresneedrecompilationdue to changes in CONSTANTS sets.
Understandinghow thecompiler actually uses CONSTANTSinformationis crucial. For a procedure p,CONSTANTS(p) describes facts known to hold on entry to a procedure. Thecompiler capitalizeson this informationby using it to initializethe globalconstant propagationphase. Informationfrom CONSTANTS(p) then percolatesinto other optimizationsfrom folded constants.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
