09 November 2016

Dominance

In a CFG, node \(b_i\) dominates \(b_j\) denoted by \(b_i \underline{>>} b_j\) iff \(b_i\) lies on every path from \(b_0\) to \(b_j\) and \(b_i \underline{>>} b_i\).

Initial

\(DOM(n_0) = \{ n_0 \}, \forall n \not= n_0\) and \( DOM(n) = N\)

Fixed-Point

\(DOM(b_i) = \{ n \} \cup \left( \bigcap_{m \in preds(n)} DOM(m) \right)\) contains the names of all nodes that dominate \(b_i\).

  • A reverse postodrder (RPO) traversal is effective for a forward data-flow analysis

  • RPO on a reverse CFG works best for a backward data-flow analysis

LiveOut

Initial

\(LiveOut(n)=\emptyset, \forall n\)

Fixed-Point

\(LiveOut = \bigcup_{m \in succ(n)} (UEVar(m) \cap \overline{VarKill(m)})\)

Limits on Data-Flow Analysis

Imprecise information

  • Array access

  • Pointer aliases with type boundedness constrain register allocation

    • Pointer disambigulation

  • Procedure side effects

Available Expressions

An expression e is available at point p in a procedure iff on every path from the procedure’s entry to p, e is evaluated and none of its consituent subexpressions are redefined betwen that evaluation and p.

\(DEFExpr(n)\)

the set of downward exposed expressions in n. \(e \in DEFExpr(n)\) iff block n evaluates e and none of e's operands is defined between the last evaluation of e in n and the end of n.

\(ExprKill(n)\)

all those expression that are killed by a definition in n.

Initial
  • \(AvailIn(n_0) = \emptyset\)

  • \(AvailIn(n) = \{ all\ expressions \}, \forall n\)

Fixed-Point
\(AvailIn(n) = \bigcap_{m \in preds(n)} (DEFExpr(m) \cup (AvailIn(m) \cap \overline{ExprKill(m)}))\)

contains the set of expressions available in block n.

Reaching Definitions

A definition d of some variable v reaches operation i iff i reads the value of v and there exists a path from d to i that does not define v.

Initial

\(REACHES(n) = \emptyset, \forall n\)

Fixed-Point

\(REACHES = \bigcup_{m \in preds(n)} (DEDef(m) \cup (REACHES(m) \cap \overline{DEFKill(m)}))\) contains the set of definitions as the domain and the corresponding definition points in the procedure.

Anticipable Expressions

An expression e is anticipable, or very busy, on exit from block b iff

  • every path that leaves b ealuates and subsequently uses e, and

  • ealuating e at the end of b would produce the same result as the first evaluation of e along each of thoes paths

Initial
  • \(AntOut(n_f) = \emptyset\)

  • \(AntOut(n) = \{ all\ expressions \}, \forall n \not= n_f\)

Fixed-Point

\(AntOut(n) = \bigcap_{m \in succ(n)} (UEExpr(m) \cup (AntOut(m) \cap _overline{ExprKill(m)}))\)

Interprocedural May Modify

Initial

\(MayMod(p) = LocalMod(p)\) contains all the names modified locally in procedure p that are visible outside p.

Fixed-Point

\(MayMod(p) = LocalMod(p) \cup \left(\bigcup_{e=(p,q)} unbind_e(MayMod(q))\right)\) computes the set of variables at call site p that might be modified by callee q.

Interprocedural May Reference

Initial

\(MayRef(p) = LocalRef(p)\) contains all the names referenced locally in procedure p that are visible outside p.

Fixed-Point

\(MayRef(p) = LocalRef(p) \cup \left(\bigcup_{e=(p,q)} unbind_e(MayRef(q))\right)\) computes the set of variables at call site p that might be referenced by callee q.