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

During global constant foldseting, the compilercan easily constructa precise MustBeConstantp ) wheneverit folds v into aby adding a pair (x, v) to MustBeConstant(use of X.4Computing precise sets for interproceduralsummary and aliasing information is not as simple. The compiler can use summary and aliasing informationin two very different ways. It can use a fact directly to justify the safety of anintraproceduraloptimizationat some call site, or it can fold the informationinto global data-flow information.The results of that global data-flow information can then be used to justify the safety of an intraproceduraloptimization.

We call this latter kind of use an indirect use. The remainderof thissection describes how to compute annotationsets for interproceduralsummary and aliasing informationthat is indirectlyused by the compiler. Section~The interprocedural constant analysis can also produce sets describing constant values returned by procedures through global variables and call-by-reference formal parameters [9].Producing exact A4usfBeCon stant sets for each call site under such a schemeis more difficult.The optimizer must know which call sites contributed returned values to each folded constant.Obtaining this information requires solving an auxiliary problem similar to those describedforAVAIL and VERYBUSY in Section 5.2.ACM Transactionson ProgrammmgLanguages and Systems, Vol.

15, No 3, July 1993.380.M. Burke and L. Torczon6 discusses constructingannotationsets when the interproceduralsummaryand aliasing informationis used directly.In order to compute precise annotationsets for indirect uses of interprocedural summary information,the compiler must be able to associate interprocedural informationwith the intraproceduraldata-flow informationto whichit contributed.This association enables the optimizer to produce a precise listof the interproceduralsummary facts actually used to justifythe safety ofeach transformationthat it applies. To compute this mapping, the compilermust augment the intraproceduraldataflowinformationthat it computeswith lists of the call sites whose summaryinformationcontributedto thevarious sets.

Using this map from intraproceduraldata-flow facts to call sites,the compilercan constructprecise annotationsets. It can determine,atoptimizationtime, precisely which interproceduralfacts must be preserved toguarantee the correctness of a particularapplicationof some optimization.Placing these facts in the appropriateannotationsets ensures that theprocedure will be recompiled and reoptimizedif one of these facts changes.To demonstratehow this approach would work, we will consider a set offour optimizationsand the global data-flow informationrequired to supportthem. The optimizationsare common subexpressionelimination,code hoisting, global constant propagation,and eliminatingregister stores.

We willclassify each optimizationas being one of two types with respect to recompilation analysis. Throughoutthis discussion, a procedure p will be representedby its control-flowgraph, G = (IV, IZ, no). The nodes of this graph representwith no control flow branches. Procebasic blocks, sequences of statementsdure invocationscan appear in expressionsand as part of a sequence ofstatements in a basic block. The edges e = (m, n) G E represent control flowbetween two basic blocks. Control enters the procedure throughits entrynode nO.To unify the data-flow equations that we are considering, we will use termssimilar to those presented in Aho et al.

[I]. Consider equations of the form:out[b]=A(gen[cz]U(out[a]mnkzlz[a]))(1)u= f(b)where out[ b ] contains the meet over all paths solution for block b, gen[ a]contains local informationgenerated in block a, and nkill[ a ] contains thosefacts not invalidatedin block a. Here, A is the appropriatemeet operator, (Jof b in the flow graph andor f). Finally, let F’[ b ] be the set of predecessorsS[ b] be the set of successors of b in the flow graph.

Then, f[ b] is either P[ b ]or S[ b ], depending on whether the problem is a forward or backward flowproblem. Note that equations of this form correspond to putting the data-flowfunctions on the edges of the flow graph.5.1CALLSBETWEENSetsTo capture the informationneeded to compute more precise annotationsets,the compiler will need to compute some auxiliaryinformationduring itsstandard global flow analysis. Assume that we have a data-flow fact a and aACM Transactions on ProgrammingLanguages and Systems, Vol 15, No 3. July 1993lnterproceduralOptimization:EliminatingUnnecessaryRecompilation..381block b in the control-flowgraph where the presence of a is used to justify anthe impact that a specificoptimizationin block b.

Then, to understandinterproceduralfact has on the values of the sets produced by forwarddata-flow analysis, the compiler will need to determine the set of call sitesbetween the last occurrence of data-flow fact a and block b, along all pathsleading from a to b. We will call that set CALLSBETWEEN( a, b). For backwarddata-flow problems, the compiler will need to determinethe set of all callb and the firstoccurrenceof dataflowfacta,sites betweenblockalongallpathsleadingfrombtoa. Wewillcallthatsetwe will refer to both types ofCALLSBETWEEN (b, a). For the sake of simplicity,informationas CALLSBETWEEN sets and assume that the difference is clearfrom the order and type of the subscripts.Thus, for our purposes, thedirection of the data-flow equation affects the way that gerz(a) is defined,f(b)is P(b) or S(b), and the region of interestconsidered forwhetherCALLSBETWEEN.To compute CALLSBETWEEN sets, we will expand the domainof theequations that define the global data-flowproblems used to support theoptimization.We refer to this process as solving an auxiliarydata-flowproblem.

In the original formulations,the elements of the various sets, out,gen, and nkill, are names of data-flow facts. Thus, the presence of an elementa in out[ b ] still denotes that a is a data-flow fact holding at b, but it is nowwhere a namerepresentsrepresented in terms of a pair ( a.name, a calls),the literal name of the data-flow fact and a.calls is CALLSBETWEEN. To solvesetsthis auxiliaryproblem, we expand the domain of the gen and nkillaccordingly:problem, a.calls is—For a = gen[ b ], if the data-flow problem is a forwardthe set of call sites in b after the last occurrence of a; if it is a backwardproblem, a calls is the set of call sites in b before the first occurrence of a.—Fora ~ nkill[b ], a.callsis the set of all call sites in b.We must also extend the definitionsof the operatorsexpanded domain. The new interpretationsare:to workovertheX n YTo compute X n Y, for each element x = X such that =y ● Y withadd (x.

name, x.calls U y.calls)to the result. Notex. name = y.name,that Eq. (1) includes the term (out[ a] n nkill[ a]) rather than thestandard, equivalentterm (out[ a] – kill[ a]) because it is necessaryto accumulate call-site informationabout the nkill[ al sets, which donot appear when the term is written in its standard form.X U YeveryTo compute X U Y, first determine the set Yonly, containingelement of Y whose name does not appear in X. Then the desiredresult is the naturalunion of X and Yonly.

Note that X U Y asdefined here is not a commutativeoperation. For this scheme to workcorrectly, X must represent gen[ a] and Y must represent (out[ a] nnkill[ a]). To avoid overloading the meaning of the U operator, X @ Ythewill representthe naturalunion of X and Yonly throughoutremainder of this paper.ACM Transactions on ProgrammingLanguages and Systems, Vol. 15, No. 3, July 1993.382XA.YM Burke and L. TorczonTo compute X A Y, if the appropriatemeet operation is U, then foraddeach element x E X such that Ely = Y with x.narne = y.name,( x.name, x.calls U y.calls) to the result. For each x ● X (and y = Y)where there is no y = Y(x ● X) with x.name = y.nczme, add x (y) tothe result.

If the appropriatemeet operationis (l, perform theintersectionas defined for X f’ Y above. Note that in both cases,a calls is computed as the natural union of the call sites from all theappropriatepaths.Once we have reformulatedthe problem in this manner, we can solve it usingtraditionalglobal dataflowtechniques.The solutionto the reformulatedproblem contains both the solution to the original problem, encoded as thename fields of set elements, and the additionalCALLSBETWEEN sets, encodedas the calls fields of set elements. We will use this technique in each of ourfour examples.5.2 Type I OptlmizationsThe type I optimizationsrely on the presence of a fact in the set out[ b] tojustify the safety of applying the transformation.The three problems that weconsider, global common subexpression elimination,code hoisting, and globalconstant propagation,are each formulatedas a data-flow computationfollowed by selective applicationof a transformation.The decision to apply thetransformationis based on the results of the data-flow analysis.Elimination.When the compiler discovers5.2.1 Corn mon Subexpressiontwo or more instances of a single expression separated by code that does notredefine any of the variables used in the expression, it can save the result ofthe first evaluationand replace the subsequent evaluationswith a simplereference to the saved value.

To locate opportunitiesfor this optimization,elimination,the compiler must knowknown as global common subexpressionat various points in the procedure. Anwhich expressionsare availableexpression is available on entry to a basic block b if, along every path leadingofto b, the expression has been evaluated since the most recent redefinitionits constituentvariables [1]. To represent this information,we associate a setcontains all expressions available onAVAIL(b) with each block b.