CSCE 434 Lecture 40

« previous | Monday, December 2, 2013 | next »

End Exam 2 content

Data Flow Framework

1. Semilattice $⟨L,\wedge ⟩$ that includes a domain of values $V$ and a meet (confluence) operator
2. Family of functions $F=\{f\mid f:V\to V\}$ closed under composition
3. Direction (forward or backward)

Partial ordering $\le$ such that $u\le v⟺u\wedge v=u$ for $u,v\in L$.

Semilattice

Pair $⟨L,\wedge ⟩$, where

• $L$ is a nonempty set of values $V$
• $\wedge$ is a binary meet operator on $L$ such that for all $x,y,z\in L$,
  • $x\wedge x=x$ (idempotent)
  • $x\wedge y=y\wedge x$ (commutative)
  • $x\wedge (y\wedge z)=(x\wedge y)\wedge z$ (associative)

Top element $\mathrm{\top }$, such that for all $x\in V$, $\mathrm{\top }\wedge x=x$.

Optionally a bottom element $\mathrm{\perp }$, such that for all $x\in V$, $\mathrm{\perp }\wedge x=\mathrm{\perp }$.

Example: Reaching Definitions

$L=\{x\mid x=\text{values at top of nodes in a flow graph}\}=2^D$, where $D$ is the set of all defs in the program.

$F=\{f(x)\mid A\cup (X\setminus B)\}$, where $A$ and $B$ are sets of defs in $L$ representing GEN and KILL sets, respectively.

Meet operator $\wedge$ is union ($\cup$).

Example: Available Expressions

$\left|L\right|=2^D$, where $D$ is the set of all expressions computed by program.

$F=\{f(x)\mid A\cup (X\setminus B)\}$, where $A$ and $B$ are sets of defs in $L$ representing GEN and KILL sets, respectively.

Meet operator $\wedge$ is intersection ($\cap$).

Example: Constant Propagation

$L=\{\psi :vars\to \mathbb{ℝ}\cup \{\mathrm{n}\mathrm{o}\mathrm{n}\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{n}\mathrm{t},\mathrm{u}\mathrm{n}\mathrm{d}\mathrm{e}\mathrm{f}\mathrm{i}\mathrm{n}\mathrm{e}\mathrm{d}\}\}$

Variables in a program can be one of undefined, nonconstant, or constant.

Transfer functions are quite complicated, but here's the gist:

$\wedge$	const val $d$	nonconst	unknown
const val $c$	c == d ? c : nonconst	nonconst	$c$
nonconst	nonconst	nonconst	nonconst
unknown	$d$	nonconst	unknown

Monotonicity and Distributivity

A framework $⟨L,F,\wedge ⟩$ is monotone if and only if

• $u\le v$ implies $f(u)\le f(v)$ for all $u,v\in L$ and all $f\in F$, or equivalently
• $f(u\wedge v)\le f(u)\wedge f(v)$ for all $u,v\in L$ and all $f\in F$.

$⟨L,F,\wedge ⟩$ is distributive if and only if

$f(u\wedge v)=f(u)\wedge f(v)$ for all $u,v\in L$ and $f\in F$

Distributivity implies monotonicity.