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

AVAIL(b)entry to b. These sets can be derived by solving a forward data-flow analysisproblem. The following system of equations describes the problem:AvAIL(b)=Aa6P(b)(DEF(a)U (AVAIL(a)f’ NKILL(a)))where P(b) is the set of predecessors of b. DEF( a) contains those expressionscomputed in a and not subsequentlyredefined in a. NKILL( a’) is the set ofexpressions not redefined in a.

This system of data-flow equations is rapidin the sense of Kam and Unman [21], so it can be solved efficientlyusingiterative techniques.Expressions remain available as long as they are included in NKILL( b). Fora variablekilleda block b, NKILL( b ) excludes any expression containingACM Transactions on ProgrammingLanguages and Systems, Vol.

15, No 3, July 1993.InterproceduralOptimization:EliminatingUnnecessaryRecompllatlon..383locally in b. In the absence of summary informationabout call sites in b, theAVAIL analysis must assume that a procedure call kills every variable it canaccess. Thus, if b contains a call site, NKILL( b ) must exclude all expressionscontainingactual parametersand global variables that can be modified as aside effect of the call. If summary informationis available, this exclusion canbe reduced to the set of expressions involving variables contained in MOD(e)for the call site e. REF(e) plays no role in the AVAIL computation.When a variable u = Mor)(e), no expression containingv can be in NKILL(b)for the block b containing call site e, because v maybe modified by executionof the procedure call. Thus, if an expression a = AVAIL(b) for some block b,its constituent variables cannot be in the MOD set of any call site between a‘smost recent evaluationand b, on each path leading to b.

If the compilereliminatesa reevaluationof a, the correctness of that decision relies on thevalues of the MOD sets for the appropriatecall sites. The procedure will needto be recompiled if any of the variables used in a are added to one of theseMOD sets.To capture this informationin the annotationsets, the compilercancompute CALLSBETWEEN sets along with the AVAIL informationand use theme).

The CALLSBETWEEN sets are computed as describedto compute Mayillode(is CALLSBETWEEN( a, b). Thein Section 5.1. For each a ● AVAIL(b), a.callsfollowing definitionsare used for the local sets.—For aof a!.—For●DEF(b), a callsa @ NKrLL(b),a.callsis the set of call sites in b afterthe lastis the set of all call sites in b.definition/The operations used are those described in Section 5.1. In this case, the meetoperator is intersection.Using these definitions, for each a E AVAIL(b), a callscorresponds to the set CALLSBETWEEN( a, b). Even with the changes in theoperators and local sets in the AVAIL computation,calculationof the newAVAIL and CALLSBETWEEN informationis still rapid in the sense of Kam andUnman [21].can be constructedfor commonGiven CALLSBETWEEN( a, b), MayMod(e)subexpression eliminationas follows:let MayMod(e)= ALLVARS, the set of all actual(1) Initially,global variables, for each call site e in p.parametersand(2) Whenever an evaluationb, the compiler removesof an available expression a is replaced in blockall constituentva~iables of a from MayMod( e),for each call site e in CALLSBETWEEN( a, b) and each call site e inside boccurring before the optimization.5MayModsets model the recompilationThe resultingby applying this optimization.dependenceintroduced5The optimizer has assumedthat these variables are not in MoI)(e) at each of these call sites.ACM TransactionsonProgrammmgLanguagesandSystems,Vol.

15,No 3, July 1993.384.M. Burke and L. Torczonis very busy at a point p in a programprior toif, along every path leading from p, the expression is evaluatedredefinitionof any of its constituentvariables. When the compiler discoversthat an expression is very busy at p, it can evaluate the expression at p, savethe result of this evaluation,and replace the subsequent evaluationswith asimple reference to the saved value. This transformation,called code hoistfor the procedure [4]. To locateing, reduces the total code space requiredopportunitiesfor code hoisting, the compiler must know which expressionsare very busy at various points in the procedure.

To represent this information, we associate with each block b a set VERYBUSY( b) that contains allexpressions that are very busy upon exit from b.To find opportunitiesfor code hoisting, the optimizer can compute the setsThese sets can be derived by solving a backwardof very busy expressions.data-flow analysis problem. The following system of equations describes theproblem:5.2.2Code Hoisting.VERYBUSY( b) =An expressionA(USED(CL) u (VERYBUSY( a) n NKILL(cz))).a~s(b)Here, USED(a) contains those expressions computed in a prior to redefinitionin a of any of its constituentvariables. NKILL( a) is the set of expressions notredefined in a.When a variable u ● MOD(e), no expressions containing v can be in NKILL,(b)e.

Thus, if an expressiona = vERYBuSY(b~forfor the block b containingvariables cannot be in the MOD set of any callsome block b, its constituentof a on each path leadingsite betweenthe end of b and the first evaluationoptimization,the compiler would move thefrom b. To apply the hoistingand replaceevaluationof a to the end of b, store the result in a temporary,each of the subsequent evaluationswith a reference to the temporary.Thecorrectness of the decision to hoist a relies on the values of the MOD sets forThe procedurethe call sites between b and each of the replaced evaluations.will need to be recompiled if any of the variables used in a are added to oneof these MOD sets.To capture this informationin the annotationsets, the compilercancompute auxiliaryinformationin the form of CALLSBETWEEN sets as described in Section 5.1.

For each a ● VERYBUSY( b), a.calls represents the setCALLSBETWEEN( b, a). The local sets for the auxiliaryproblem are defined as:—For a = USED(b),definitionof a.a.calls—Fora callsa E NKmL(b),istheset of callsitesinb beforethefirstis the set of all call sites in b.The operations used are those described in Section 5.1. The meet operator isin the sense of Kam andintersection.The dataflow problem is still rapidUnman, even after the addition of the auxiliaryproblem [21].( b, a), MayMod(e)can be updated for code hoistingGiven CALLSBETWEENin the following manner:= ALLVARS, the set of all actual(1) Initially,let MayMod(e)global variables, for each call site e in p.ACM Transactionson ProgrammingparametersLanguages and Systems, Vol. 15, No.

3, July 1993andInterproceduralOptimization:EliminatingUnnecessaryRecompilation.(2) wheneverthe optimizermoves averybusy expressionblock b,thecompilershould remove each of theconstituentfrom MczyMocl(e) for each a in CALLSEIETWEEN(b, a).sets describe the compilationMayModThe resultingby code hoisting..385a totheend ofvariables of adependenceintroduced5.2.3 GlobalConstantPropagation.In globalconstantpropagation,theoptimizerreplaces an expression with a constant value if the value can bedefinicomputed at compile time .6 This optimizationis based on reachingA definitionreaches a particularpoint p in a program iftions information.there exists a path between it and p along which the defined variable is notredefined. To represent this information,we associate a set REACH(b) withcontains all definitionsthat reach the entry toeach basic block b.

REACH(b)block b. These sets can be derived by solving the following forward data-flowproblem.REAcH(b)=A(DEF(a)U (REACH(a)f’ NKILL(a))).a EP(b)Here, DEF(a) contains those definitionsin a of variables that are not subsequently redefined in a. NKILL(a) is the set of definitions for which the definedvariable is not redefined in a.When constant propagationis performed,a use of a variablex can bereplaced by a constant c only if all definitionsof x that reach the use havebeen recognized as having the value c. For a use of x that is replaced by c ata point p, any call sites that can be executed prior to p can potentiallyinvalidatethe optimization.If x is subsequentlyadded to the MOD set ofsome such call site, that change represents a potential change in x‘s value. Inthe absence of better interproceduralinformation,this new definitioninvalidates the forward substitutionof c for x at p.To account for this interactionbetween interproceduralMOD sets and theglobal REACH sets, we can compute auxiliaryCALLSBETWEEN sets in themanner described in Section 5.1.

For each a ● REACH(b), a calls representsforthe set CALLSBETWEEN( a, b). In this case, we use the following definitionsthe local sets.—For a = Din?(b),of a.—Fora E NKH,L(b),a.callsa.callsis the set of call sites in b afterthe lastdefinitionis the set of all call sites in b.The operations used are those described in Section 5.1. The meet operator isset union.

With these definitions,the revised REACH equations will computeboth reaches informationand the CALLSBETWEEN sets.7 The revised computation is still rapid in the sense of Kam and Unman [21].sets are used as6Where interprocedural constant propagation is performed, the CONSTANTSinitial imfm-mati.n in the && ~.o.edu.e, o. ~lobal, computation.7Note that in this case, X n Y is the empty set, where X = DEF(CZ) and Y = (REAcH(a) nNKILL(a)). So, we could use X u Y instead of X @Y. Howeverj it is correct as defined here and itfits the proposedframework.ACM TransactIons on ProgrammmgLanguages and Systems, Vol.