CSCE 434 Lecture 40

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

End Exam 2 content

Data Flow Framework

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

Partial ordering $\leq$ such that $u\leq v\iff u\wedge v=u$ for $u,v\in L$.

Semilattice

Pair $\left\langle L,\wedge \right\rangle$, 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 $\top$, such that for all $x\in V$, $\top \wedge x=x$.

Optionally a bottom element $\bot$, such that for all $x\in V$, $\bot \wedge x=\bot$.

Example: Reaching Definitions

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

$F=\left\{f(x)~\mid ~A\cup (X\setminus B)\right\}$, 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=\left\{f(x)~\mid ~A\cup (X\setminus B)\right\}$, 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=\left\{\psi :vars\to \mathbb {R} \cup \left\{\mathrm {nonconstant} ,\mathrm {undefined} \right\}\right\}$

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 $\left\langle L,F,\wedge \right\rangle$ is monotone if and only if

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

$\left\langle L,F,\wedge \right\rangle$ 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.