Available Expressions
Why do we want to study Available Expression
- Global Common Subexpressions
1 2 3 4 5 6 7
if (...) { x = m + n; } else{ y = m + n; } z = m + n; // m + n has alredy been computed, there it is redundant
- What happens if m + n is NOT computed in the else branch?
-
Need a rigorous way for arguing about “redundancy”
- In Available Expressions, we care about expressions
- Domain: Sets of Expressions
Terminologies
-
An expression $x \oplus y$ is available at a point p if every path from the entry node to p evaluates $x \oplus y$
-
A block generates expression $x \oplus y$ if it definitely evaluates $x \oplus y$ and does not subsequently define x or y.
-
A block kills expression $x \oplus y$ if it assigns (or may assign) x or y and does not subsequently recompute $x \oplus y$
- E.g.
1 2
x = y + 1; // generates y + 1 y = m + n; // generates m + n also kills y + 1
- Transfer Function: $f_B := gen_B \cup (x - kill_B)$
Set Up
- What should be the Direction of analysis?
- In Available Expressions, we eliminate an expression because it has been computed in the past
- In Live Variables, we eliminate a variable because it is not going to be used in the future
- Available Expression is Forward while Live Variables is Backward.
- What should be the Initial Condition and Boundary Condition?
- Boundary Condition OUT[Entry] = $\emptyset$
- Initial Condition: OUT[B] = $\mathbb U$
-
Direction: Forward
-
OUT Equation: OUT[B] = $f_B(IN[B])$
-
IN Equation: IN[B] = $\wedge_{p \in pred(B)} OUT[p]$
- MEET Operator $\cap$
Sum Up
| Domain | Sets of Expressions |
| Direction | Forward |
| Transfer Function | $f_B := gen_B \cup (x - kill_B)$ |
| Meet Operator | $\cap$ |
| OUT Equation | OUT[B] = $f_B(IN[B])$ |
| IN Equation | IN[B] = $\wedge_{p \in pred(B)} OUT[p]$ |
| Boundary Condition | OUT[Entry] = $\emptyset$ |
| Initial Condition | OUT[B] = $\mathbb U$ |