Data Flow Analysis Applications III
What is Available Expression Analysis
An expression x op y is available at a program point p if
- all paths from the entry to p must pass through the evaluation of x op y, and
- after the last evaluation of x op y, there is no redefinition of x or y
Note that this is a must analysis.
What we can do with this definition
- This definition means at program p, we can replace expression x op y by the result of its last evaluation
- The information of available expressions can be used for detecting global common subexpressions.
Safe-Approximation
$$
OUT[B] = gen_B \cup (IN[B] - kill_B)
$$
$$
IN[B] = \cap \space OUT[p]
$$
- For the safety of the analysis, it may report an expression as unavailable even if it is truly available at runtime. ( must analysis->under approximation )
Method:
- OUT[exit] = empty set
- for each basic block B\entry
- while changes to any OUT occur
- for each basic block B\entry
- End for
- End while
Analysis Comparison
|
Reaching Definition |
Live Variables |
Available Expressions |
| Domain |
set of definition |
set of variables |
set of expressions |
| Direction |
forward |
backward |
forward |
| May/Must |
may |
may |
must |
| Boundary |
OUT[entry]=empty |
IN[exit]=empty |
OUT[entry]=empty |
| Initialization |
out=empty |
in=empty |
out=full |
| Transfer Function |
- |
- |
- |
| Meet |
union |
union |
intersection |
Reviewing:
After this lecture, you should:
- Understand the three data flow analyses
- Can tell the differences and similarities of the three data flow analyses
- Understand the iterative algorithm and can tell why it is able to terminate