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.