Assignment 1

Handed out: January 22, 2008

Due date: January 31, 2008

1. (Control flow analysis) Given the following control flow graph: (a) compute the dominator sets and construct the dominator tree; (b) identify the loops using the dominator information; (c) is this control flow graph reducible?; and (d) if the graph is reducible, compute the reverse postordering of the nodes and use it to identify the loops.
   
   
2. (Data flow analysis) For each of the problems listed below provide the following: the lattice values, meet operator, top and bottom elements, the partial order relation, pictorial representation of the partial order, the transfer functions, and the data flow equations.
   • reachable uses -- for each definition identify the set of uses reachable by the definition (used for computing def-use chains);
   • reaching uses -- given a definition of variable x, identify the set of uses of x that are encountered prior to reaching the definition and there is no other definitions of x that intervene the use and the definition (used for computing antidependences);
   • postdominator set of a node is the set of nodes that are encountered along all paths from the node to the end node of the control flow graph; and
   • classify the value of each program variable at each program point into one of the following categories: (a) the value is a unique constant -- you must also identify this constant value; (b) the value is one-of-many constants -- you are not actually compute the identities of these constants as part of your solution; and (c) the value is not-a-constant, that is, it is neither a unique constant nor a one-of-many constants.