An interesting and powerful data-flow analysis framework is obtained by imagining tila[ the “values” to be propagated are all the possible partitions of expressions so that two expressions are in the same class only if they have the same value. To avoid having 10 list all of the infinity of possible expressions, we can represent such values by listing only the min imal expressions that are equivalent to .. some other expression . For example, if we execute the statements
then we have the following minimal equivalences: A '”'” B, andC “” A +D. From these follow other equivalences, such as c:= B+ D and A+E == B +E, but there is no need 10 list these explicitly.
a) What is the appropriate meet, or confluence, operator for this. framework?
b) Give a data structure to represent values and an algorithm to implement the meet operator.
c) What are the appropriate functions to associate with statements? Explain the effect that the function associated with assignments such as A: =B+-C should have on a partition.
d) Is this framework. distributive? Monotone?