Homework 1

Handed out: April 14, 2009

Due date: April 23, 2009

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; and (c) is this control flow graph reducible? Explain.
   
   
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.