Consider generalizing the problem of constant propagation to that of range analysis. For each variable, we wish to associate a minimum and maximum value, such that the actual value of the variable (at that site in the program) at runtime is guaranteed to fall between the two values. For example, consider
the following program.
![](https://test.transtutors.com/qimg/99a6098a-539c-4664-8125-9f9527fd95db.png)
After their assignment, variable x has range 5 _ _ _5 and variable y has range 3 _ _ _ 3. The effect of Step 14 gives z the range 8 _ _ _ 8. The effect of Step 15 gives z the range 2 _ _ _ 2. The assignment for w therefore gets the range 2 _ _ _ 8.
(a) Sketch the data flow lattice for a single variable. Be specific about the values for
or
.
(b) Is this a forwards or backwards propagation problem?
(c) If the variable v could have range r1 or r2, describe how to compute the meet of these two ranges.