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