Post is in these categories:
An expression e is very busy at a point p if for every path from p, the expression is used before any of the constituent parts of e are redefined. For example:
a = 0
b = 0
t = a + b // a + b is very busy, because it is used on the only path (to the definition of w) without being redefined
u = a - b
v = a * b
w = (a + b) * 2
a = 0
b = 0
t = a + b // a + b is not very busy, because we redefine a (= 0) before we use the value
u = a - b
v = a * b
a = 0
w = (a + b) * 2
How can this be computed as a dataflow analysis? We start at the use-sites, and propagate this information backwards through the control-flow graph. Consider a single node in the control-flow graph. There are two cases that we can consider
- The base case: if we def…
Post is in these categories:
An expression e is very busy at a point p if for every path from p, the expression is used before any of the constituent parts of e are redefined. For example:
a = 0
b = 0
t = a + b // a + b is very busy, because it is used on the only path (to the definition of w) without being redefined
u = a - b
v = a * b
w = (a + b) * 2
a = 0
b = 0
t = a + b // a + b is not very busy, because we redefine a (= 0) before we use the value
u = a - b
v = a * b
a = 0
w = (a + b) * 2
How can this be computed as a dataflow analysis? We start at the use-sites, and propagate this information backwards through the control-flow graph. Consider a single node in the control-flow graph. There are two cases that we can consider
- The base case: if we define an expression at this node, then we should pass this backwards to earlier nodes (the node has been used at our location, so it is very-busy on entry to this node). In equational form, this is just \text{def}[n].
- The “recursive” case: suppose that the expression e is live on exit from this expression1. When is it live on entry to this node? As per the definition, it remains live, unless one of its constituent parts is redefined. The set of nodes which are live on exit is \text{out}[n], and the set of expressions which we redefine part of at this node is \text{kill}[n]. Thus the set of expressions which are live on exit and are no part of which is redefined by the current node is \text{out}[n] – \text{kill}[n] Combining these two parts for the exit is just a question of taking the union.
\begin{align}
\text{out}[n] &= \bigcap_{s\in \text{succ}(n)} \text{in}[s] \\
\text{in}[n] &= (\text{out}[n] - \text{kill}[n]) \cup \text{def}[n]
\end{align}
- e.g. because it is live on entry to all of the successors of this node ↩︎