Machine-Independent Optimizations II CS308 Compiler Theory 1
Machine-Independent Optimizations Ⅱ CS308 Compiler Theory 1
Foundations of Data-Flow Analysis A data-flow analysis framework (D,V,A,F)consists of 1.A direction of the data flow D,which is either FORWARDS or BACKWARDS. 2.A semilattice (see Section 9.3.1 for the definition),which includes a do- main of values V and a meet operator A. 3.A family F of transfer functions from V to V.This family must include functions suitable for the boundary conditions,which are constant transfer functions for the special nodes ENTRY and EXIT in any flow graph. CS308 Compiler Theory
Foundations of Data-Flow Analysis CS308 Compiler Theory 2
Semilattices A semilattice is a set V and a binary meet operator A such that for all a,y, and z in V: 1.xAx =x (meet is idempotent). 2.x∧y=y∧x(meet is commutative). 3.x∧(y∧z)=(x∧y∧z(meet is associative). A semilattice has a top element,denoted T,such that for all a in v,T∧x=x. Optionally,a semilattice may have a bottom element,denoted L,such that for all a in V,⊥∧x=⊥. CS308 Compiler Theory 3
Semilattices CS308 Compiler Theory 3
Semilattices The partial order for a semilattice (V,A)for all x and y in V, x≤y if and only if x∧y=x. Greatest low bound of domain elements x and y is an element g such that 1.9≤x, 2.g≤y,and 3.If z is any element such that z≤and z≤y,then之≤g. The meet of x and y,g=x A y,is their only greatest lower bound CS308 Compiler Theory
Semilattices • The partial order for a semilattice (V, ∧) for all x and y in V, • Greatest low bound of domain elements x and y is an element g such that • The meet of x and y, g=x ∧ y, is their only greatest lower bound CS308 Compiler Theory 4
Semilattices Lattice Diagrams for 3 definitions (T) {d) (d) td,d) d:} {4,) 4,} (L) The set of data-flow values is the power set of the definitions,which contains 2n elements if there are n definitions in the program. CS308 Compiler Theory 5
Semilattices • Lattice Diagrams for 3 definitions ⊇ • The set of data-flow values is the power set of the definitions, which contains 2n elements if there are n definitions in the program. CS308 Compiler Theory 5
Product Lattices for only one definition d,the lattice would have two element:and {d} Suppose(A,AA)and(B,AB)are lattices,the product lattice is: 1.The domain of the product lattice is A x B. 2.The meet A for the product lattice is defined as follows.If (a,b)and (a',b')are domain elements of the product lattice,then (a,b)(a',b')=(ana',6nb'). partial orders≤Aand≤3 for A and B (a,b)≤(a',b')if and only if a≤4a'andb≤Bb'. CS308 Compiler Theory 6
Product Lattices • for only one definition d, the lattice would have two element: {} and {d} • Suppose (A, ∧A ) and (B, ∧B ) are lattices, the product lattice is: CS308 Compiler Theory 6
Transfer Functions Closed under composition For any two functions f and g in F,h(x)=g(f(x))is in F ·Monotone frameworks A data-flow framework (D,F,V,A)is monotone if for all x and y in V and f in F,x<=y implies f(x)<=f(y) Distributive frameworks -fx∧y)=fx)∧fy)for all x and y in V and f in F. CS308 Compiler Theory 7
Transfer Functions • Closed under composition – For any two functions f and g in F, h(x)=g(f(x)) is in F • Monotone frameworks Monotone frameworks – A data-flow framework (D, F, V, ∧) is monotone if for all x and y in V and f in F, x<=y implies f(x)<=f(y) • Distributive frameworks – f(x ∧ y) f( ) = x ) ∧f( ) f ll d i V d f i F f( y ) for all x an d y in V an d f in F. CS308 Compiler Theory 7
The Iterative Algorithm for General Frameworks Algorithm 9.25:Iterative solution to general data-flow frameworks. INPUT:A data-flow framework with the following components: 1.A data-flow graph,with specially labeled ENTRY and EXIT nodes, 2.A direction of the data-flow D, 3.A set of values V, 4.A meet operator∧， 5.A set of functions F,where fB in F is the transfer function for block B, and 6.A constant value vENTRY or vExm in V,representing the boundary condition for forward and backward frameworks,respectively. OUTPUT:Values in V for IN[B]and OUT[B]for each block B in the data-flow graph. CS308 Compiler Theory 8
The Iterative Algorithm for General Frameworks CS308 Compiler Theory 8
The Iterative Algorithm for General Frameworks 1) OUTENTRY=VENTRY; 2) for (each basic block B other than ENTRY)OUT[B]=T; 3) while (changes to any OUT occur) 4) for (each basic block B other than ENTRY){ 5) IN[B]=AP a predecessor of B OUT[P]; 6) OUT[B]=fB(IN[B]); (a)Iterative algorithm for a forward data-flow problem. CS308 Compiler Theory 9
The Iterative Algorithm for General Frameworks CS308 Compiler Theory 9
Constant Propagation The set of data-flow values is a product lattice The lattice for a single variable consists of the following: -All constants appropriate for the type of the variable The value NAC,which stands for not-a-constant. The value UNDEF,which stands for undefined. UNDEF The semilattice for a typical integer- -3 valued variable The semilattice of data-flow values is simply the product of the semilattices like the Figure. NAC A data-flow value for this framework is a map from each variable in the program to one of the values in the constant semilattice.The value of a variable v in a map m is denoted by m(v). CS308 Compiler Theory 10
Constant Propagation • The set of data-flow values is a product lattice • The lattice for a single variable consists of the following: – All constants appropriate for the type of the variable – The al e NAC hich stands for not The val u e NAC, which stands for not - a -constant constant. – The value UNDEF, which stands for undefined. The semilattice for a typical integervalued variable The semilattice of data-flow values is simply the product of the semilattices like the Figure. CS308 Compiler Theory 10