Consider generalizing the problem of constant propagation

Question

As defined in Exercise 20, prove or disprove that range analysis is a rapid data flow problem.

Exercise 20

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.

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 r₁ or r₂, describe how to compute the meet of these two ranges.