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

15, No. 3, July 1993.386.M. Burke and L. TorczonGiven the CALLSBETWEEN sets, we can compute MczyMocl sets that aremore precise than those derived using APPEARS information.To updateMayMod(e):(1) Initially,let MayMod(e) = ALLVARS, the set of all actualglobal variables, for each call site e in p.parametersand(2) Whenevera variablex is replaced by a constant, the compiler mustsets for any call site that lies on a path between aupdate the MayModdefinitionof x and the replacementsite. These are the call sites in thesets CALLSBETWEEN( a, b) for each definitiona of x in REACH(6), where bis the block containingthe replacement.Additionally,x should be re) for each call site inside block b occurring beforemoved from MayMod(ethe replaced reference.8sets computed this way, however, are still approximate.WhenThe MayModan assignment is added in some other procedure, causing x to appear in theMOD set of some call site e, we do not know the value that x receives.

It ispossible that x receives the value c at the new assignment,too. If theinterproceduralanalysis finds constant values returnedby procedures, theMayModsets can be computed in a more precise manner to account for thosereturned constants [9].5.3 Type II OptimizationsWhere type I optimizationsdepend on the presence of a fact in the set out[ b ],type II optimizationsdepend on the absence of a fact from o.ut[ b ]. As anexample, we consider register store elimination,which depends on the absence of a variable from LIVE sets to remove the last store of a value. Thischanges the CALLSBETWEEN informationthat we are interested in computingin two importantways.(1) The informationof interest is associated with facts not in the set. In thetype I optimizations,it was associated with facts in the set. Thus, we areinterestedin the a calls fields of facts that would correspond to thezeroes in a bit-vector implementation.(2) The set CALLSBETWEEN(b, a ) now describes a region between b and apoint at which the optimizer decided that some event involvinga did notoccur.

In the case of register store elimination,if a is not LIVE at b,CALLSBETWEENcontainsall call sites betweenblockb and a redefinitionof a (or an exit from the procedure if no redefinitionexists) along everypath leaving b.We wouldliketo use the frameworkdescribed in Section 5.1 to computefor type II optimizations.For this frameworktothat thebe applicable, we must compute out[ b ], the data-flow informationcompiler actually uses when it performs type II optimizations.Thus, whenCALLSBETWEENinformation8 If an expressionis replaced,rather than a simple variable, the IVfayModsets(at the sameset ofcall sites) must be updated to remove each of the expression’s constituent variables,ACM TransactIonson Pro~ammmgLanguages and Systems, Vol 15, No 3, July 1993Interprocedural Optimization: Eliminating Unnecessary Recompilation..387the optimizerrelies on the absence of a fact from some data-flowset, werecast the problem to compute the complementof that set, so that thetransformationcan be based on the presence of a fact in the complement.This insures that the CALLSBETWEEN informationfor the facts that theoptimizer uses will be accumulated.To determine how to transformthe data-flow equations associated with atype II optimizationinto the form needed to compute CALLSBETWEEN information using the method described in Section 5.1, we recast our generalformulation,Eq.

(1) from Section 5, as follows.Outo[b]=A.(geno[a]n rkllo[a])).u (outo[a]a= f(b)Using DeMorgan’s law, we compute the equation for Out. [ b ]. Note thatthe complement of AO , where u and n are considered complements.outo[bl=A(geno[czln (outo[alA isu rzkillo[al)).a= f(b)Distributethe intersectionsozdo[b]=Aover the union((geno[cz]to constructn rddlo[cz])ua new equation:(outo[a]ngeno[a])).a=f(b)We can redefinethis equationout[b]=Ato look like Eq. (l):(gen[a]u(out[aln nhill[al))a= f(b)out[b]= outo[bl,gen[ct] = ge~o[~]withthe followingassignments:n nkillo [ a ], and nkill[ a] = geno [ a ].

Again, CALLSBETWEEN can be computedas described in Section 5.1. The next subsection shows an example based onthe use of LIVE information.Register Stores.If the compiler discovers a point where5.3.1 Eliminatingthe value of a local variable of a procedure exists in a register and that valuecannot be used later in the procedure, it need not store the value back intounnecessarystores,memory.

To perform this optimization,called eliminatingthe compiler must recognize the last use of a variable in a procedure.A variable is live at a point in a procedure if there exists a control flowpath from that point to some use of the variable and that path contains noassignments to the variable. Live analysis associates a set LIVE(b) with eachblock b. L1~(b ) contains all the variables that are live upon exit from blockb. LIVE sets can be computed by solving a backwarddata-flow problem. Thefollowing equation is a slightly modified version of the equation given by Ahoet al.

[1]Lnm(b)=A(IN(a)U(LIvE(a)nNDEF(a))).cz~S(b)Here,LIVE(b)is thethe set of variablesset of variableslive immediatelyafter blockwhose values may be used in a priorACM Transactionson Programmingb, IN(a)to any definitionkofLanguages and Systems, Vol. 15, No. 3, July 1993.388.M. Burke and L. Torczonthat variablein a, and NDEF(a)is the set of variablesnot assigned values ina.Without summary informationfor call sites, the compiler must assume thata call references any variables visible to it.

This assumption extends the liveranges of variables, inhibitingthe applicationof register store elimination.InterproceduralREF sets can reduce the set of variablesassumed LIVEbecause of a call site. Because MOD(e) says nothing about uses, MOD information is not pertinentto the computationof LIVE information.Register store optimizationsare invalidatedwhen the life of a variable isextended by addition of a variable use after the current last use. Thus, anycall sites between the eliminatedstore and the end of the procedure canpotentiallyinvalidatea register store optimization.Assume that the optimizer has eliminatedthe last store of a variable x.

If a subsequent change tosome other procedure adds x to the REF set of a call site that occurs after theeliminatedstore, the procedure must be recompiled, since the change possiblymakes the eliminatedstore necessary for correct execution of the program.sets that reflect this dependence on interproceduralTo construct MayRefREF informationin the LIVE sets, we would like to compute auxiliaryCALLSBETWEEN sets in the manner described in Section 5.1. Because this is a typeH optimization,computing the auxiliaryinformationis more complex. First,we must reformulatethe data-flowequations as described in the previoussubsection. We recast the equations in terms of LIVE( b ). Let out[ b ] = LIVE(b),and ru%ll[ a] = IN(cz).

Let the meet operation begen[ a] = IN(CZ) n NDIW(a),set intersection.Now the general equation we gave in Section 5 can be usedto compute LIVE.It is interestingto note how similar the LIVE computationis to the otherdata-flow equations that we have considered. Given this reformulation,wecan derive the necessary CALLSBETWEEN sets as auxiliaryinformationduringthe LIVE computation.For each a = out[ b ], a.calls represents the set CALLSBETWEEN(b, a).

The following definitionswork within the general frameworkdescribed in Section 5.1.—For a = gen[ b ], a.callsof a.—Fora = nkill[b ], a callsis the set of call sites in b before the firstdefinitionis the set of all call sites in b.The operations used are those described in Section 5.1. The meet operator isintersection.After all this manipulation,the final data-flow frameworkforLIVE with its auxiliaryinformationremains rapid in the sense of Kam andUnman [21].To construct a recompilationtest that precisely characterizesthe use ofinterproceduralinformationin the register store optimization,we want toset. Given this set, MayRef( e) can be computed asenlarge the MayRef(e)follows:= &LV&w,the set of all actual(1) Initially,let MayRef(e)global variables, for each call site e in p.ACM Transactionson ProgrammingparametersLanguages and Systems, Vol 15, No 3, July 1993andInterprocedural Optimlzatlon: Eliminating Unnecessary Recompilation,.389(2) Whenevera store of a variable v is eliminated,the optimizer removes vfrom illczylle~(e) for each call site e in CALLSBETWEEN(b, a) and each callsite inside b occurring after the optimization.This results in iWayRef sets thatdence for this optimization.preciselycapturethe recompilationdepen-5.4 RationaleIn each of the four examples, we were able to construct more precise annotation sets by using CALLSBETWEEN sets computed as an auxiliarydata-flowproblem.

The CALLSBETWEEN informationassociated with a fact follows thepath that the fact takes through the procedure during the data-flow computation. When a fact is generated in a basic block, the set a.calls associated withit takes into account the call sites between the point where it was generatedand that end of the block where the data-flowcomputationexits.

In abackward flow computation,this is the beginning of the block; for a forwardflow computation,it is the end of the block. When a fact a passes through ablock unchanged, all of the call sites in the block are added to a calls becausethe block is an a-clear path.The operationsused in solving the auxiliarydata-flowproblemsarestraightforward.Whenevermultiplepaths come together,some data-flowfacts are invalidatedand some are not. Any fact that is not invalidatedhas ana calls set that contains the natural union of a calls sets from the individualfacts that made the new fact valid.The only operator that is unusual is the X @ Y operator.

The reason forthis operator is somewhatsubtle. The standarddata-flowequationsusebinary information.In extending the underlyingdata-flow equations to correctly compute CALLSBETWEEN sets, we expanded each bit in the originalbit-vector to include both the bit and a set that we designate that bit’s callsset. We designate the original bit as the fact’s name. The set operations onthese expanded objects are based on the presence or absence of the name, i.e,the value of its original bit. In this framework,the result of X U Y andX @ Y are not the same. (Recall the definition in Section 5.1.) Furthermore,itis clear that the data-flowevents that are of interest to an optimizerarethose computed with the X @ Y operation because these are the events thathappened nearest to the point of optimization.For example, consider a basicof expression e.

The terms el and ezblock b that contains two computationsrefer to the first and the second instantiationof e, respectively. Assume thatapplies common subexpressione = AVAIL(b) n NKILL( b). If the optimizereliminationto ez, the optimizationis safe as long as none of the variables in eare redefined between el and ez. The fact that e was also available on allbecause all of the paths to ez pass throughpaths leading to b is immaterialel.