Generalize the proof from Exercise 17 to prove or disprove that all four bitvectoring data flow problems in Exercise 12 are distributive.
Exercise 17
A data flow problem is distributive if the following formula holds for every transfer function f and lattice values a and b.
Prove or disprove that available expressions (Exercise 8) is a distributive data flow problem.
Exercise 12
Four of the data flow problems presented in Section 16.2 and in Exercises 10 and 11 are:
. Available expressions
. Live variables
. Very busy expressions
. Reaching definitions
These problems are known as the bit-vectoring data flow problems. Summarize these problems by entering each into its proper position in the following table.
The columns refer to whether information is pushed forward or backward to achieve a solution to the problem. The rows refer to whether information should hold on all paths or any path.
Exercises 10
Live ness shows that a variable is potentially of future use in a program. The very busy expressions problem if an expression's value is certainly of future use.
(a) Is this a forward or backward problem?
(b) What is the best solution?
(c) Describe the effects of a node on an expression.
(d) How are solutions summarized at common control flow points?
(e) How would you determine live ness for a set of expressions?
Exercises 11
Reaching defs
Exercises 14
A data flow framework is rapid if defines rapid ... then prove that available expressions is rapid.