An interesting and powerful data-flow-analysis framework is obtained by imagining the domain V to be all possible partitions of expressions, so that two expressions are in the same class if and only if they are certain to have the same value along any path to the point in question. To avoid having to list an infinity of expressions, we can represent V by listing only the minimal pairs of equivalent expressions. For example, if we execute the statements
then the minimal set of equivalences . From these follow other equivalences, such as and , but there is no need to list these explicitly.
a) What is the appropriate meet operator for this framework?
b) Give a data structure to represent domain values and an algorithm toimplement the meet operator.
c) What are the appropriate functions to associate with statements? Explain the effect that a statement such as a = b + c should have on a partition of expressions (i.e., on a value in V) .
d) Is this framework monotone? Distributive?