MIT 25 Reaching defnitions_ webs_ SSA (798430), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Along thesetwo paths, a is defined only at x and y.This rule implies that z must be a node with multiple predecessors, because otherwise two paths wouldhave to share the single predecessor and therefore would not be disjoint. It similarly implies that z can alsoappear in the middle of one of the paths from x and y to z, but cannot be in the middle of both.Although path convergence gives us a clear criterion for when to insert a φ-function, it is expensive toevaluate directly. SSA conversion is therefore usually done using control flow analysis, which we will talkabout shortly.4 Conditional constant propagationConstant propagation and constant folding together form an important optimization that moves computations to compile time rather than run time, that allows deletion of code that is never executed, and thatsimplifies the programs enabling further optimizations.

Conditional constant propagation is a version ofconstant propagation that takes advantage of different information along different exit edges from conditional nodes. Sparse conditional constant propagation, introduced by Wegman and Zadeck, takes advantageof SSA to keep track of less information about each node.

Although constant propagation, copy propagation, constant folding, and unreachable code elimination can achieve similar effects when used together,conditional constant propagation enables strictly more optimization.The goal of conditional constant propagation is to simplify code like the following:x = 1if (x<2) {y = 5+x} else {y = f(x)}z = y*yinto code that uses constants:x=1y=6z=364⊤...

-2-1012...⊥Figure 2: Conditional constant propagation latticeThe assignments to x and y may also be dead code at this point. Notice that we have removed theconditional entirely because its guard expression is constant, and this facilitates the optimization of theassignment to z.The analysis is a forward analysis. For each variable in the program, we keep track of its possible valuesusing the lattice in Figure 2, due to Killdall. The value > represents an undefined variable, or one that wehave not yet seen a definition for. The value ⊥ represents an “overdefined” variable, one that has more thanone possible value and that therefore cannot be predicted at compile time.

Therefore, for a given constantc, merging a path where no definition has been seen yet with one on which a constant value c has been seenyields c u > = c since it’s safe to replace an undefined value with c. Two different constant values combineto yield ⊥ (that is, c1 u c2 = ⊥), and once a variable is non-constant, it remains so: ⊥ u c = ⊥.We can keep track of the possible values of a whole set of k variables x1 , . . . , xk in a tuple of elementsof this lattice, which we will write (v1 , . . .

, vk ). The tuple of elements is of course itself a lattice with topelement (>, . . . , >).In the non-SSA representation, we need to keep track of this tuple of elements at every point in the code.In the SSA representation, there is only one definition of each variable, so a variable is either constant ornot; we can keep track of a single tuple (v1 , . . . , vk ) for the entire analysis.In either representation, we want to keep track of one more piece of information for each node: whetherthe node is unreachable. We will let u represent unreachability of a node, with u = > meaning the nodeis unreachable, and u = ⊥ meaning it may be reachable.

Treating > as “true” and ⊥ as “false”, the meetoperation is conjunction: u1 u u2 = u1 ∧ u2 . For the non-SSA representation, the dataflow values will betuples (u, (v1 , . . . , vk )), with the usual componentwise lattice ordering lifted from the orderings on u and vi .The transfer functions Fn (u, (~v )) are defined as follows:~ because we need not consider definitions made by unreachable code.• F (>, (~v )) = (>, (>))• F (⊥, (v1 , .

. . , vk ))) = (v10 , . . . , vk0 ) where for all i, vi0 = vi unless n defines xi . In this case the assignmentxi = e is interpreted abstractly using the current values for the variables occurring in e. For example,2 + 2 = 4, but 2 + ⊥ = ⊥, and 2 + > = >, and f (x) = ⊥.• One exception to the previous case is conditionals. For a conditional node containing if e, the analysis interprets e abstractly as in the previous case. If the result is ⊥, the same information is propagatedon both exiting edges.

But if the result is true or false, the information propagated on the edge not~ because that code is unreachable from this if.taken is (>, (>)),For example, applying this (non-sparse) analysis to the example from earlier, we obtain the result shownin Figure 3.Notice that the assignment y = f (x) is marked as unreachable, so it can be removed along with theconditional. Once the analysis completes, all definitions xi = e for which vi = c on the outgoing edge canbe replaced with x = c. Dead code removal can then be used to remove unnecessary assignments.When the analysis is done in SSA form, we keep track of just one tuple of values (v1 , . . . , vk ), and onlyunreachability is propagated through the CFG.

Dead code removal can then be performed easily in themanner outlined earlier, assuming that use sets are updated as we rewrite definitions to use constants.5x=1(⊥,(1,⊤,⊤))if x<2(⊥,(1,⊤,⊤))(⊤,(⊤,⊤,⊤))y=5+xy=f(x)(⊥,(1,6,⊤))(⊤,(⊤,⊤,⊤))z=y*y(⊥,(1,6,36))Figure 3: Example of conditional constant propagationx=2y=1x=1y=2(2,1,⊤)x=2y=1(2,1,⊤)(1,2,⊤)⊓(⊥,⊥,⊤)x=1y=2z = x + y(1,2,⊤)z = x + y(2,1,3)(1,2,3)⊓z = x + y(⊥,⊥,⊥)(⊥,⊥,3)Figure 4: Conditional constant propagation does not give the meet-over-paths solution4.1Solution qualityIn contrast to the analyses we’ve seen earlier, conditional constant propagation does not achieve a MOPsolution.

The reason is that the transfer functions are not distributive. To see this, consider Figure 4, inwhich the meet is taken both before a join point in control flow (corresponding to the way that dataflowanalysis works) and after (corresponding to the meet-over-paths criterion). Nevertheless, it’s an importantand effective optimizaton.6.

Характеристики

Список файлов статьи