198:516 Homework 2 Spring 2006 Selected Answers 1.(Dataflow) The intraprocedural must-be-modified problem is a backward data flow problem solvable by fixed point iteration. A variable is in the must-be-modified set on exit of a cfg node, if it is modified unconditionally on all paths from this node to program exit. a. Define the data flow framework for this problem (i.e, give the lattice, its partial order operator, its meet and the functions describing how the code at each node affects the lattice elements. (Hint: define the base lattice and then build the cross product lattice from it.) b. Are the functions for this problem or monotone? Explain briefly. ******************************* #1 gone over in class. showed functions were actually distributive and therefore monotone ****************************** 2. (Loops and Dominators) Use the following two control flow graphs to answer these questions on reducibility and domination. Graph I: (1,2) (2,3) (3,4) (3,6) (4,2) (4,5) (5,2) (5,6) (6,5) (6,6) 1 is entry node; 6 is exit node Graph II: (1,2) (2,3) (3,2) (3,4) (3,7) (4,5) (5,6) (6,2) (6,5) 1 is entry node; 2 is exit node a. What are the natural loops in these graphs? b. Are the graphs reducible or irreducible? c. Draw the dominator and postdominator trees for I and II. ******************************* #2 discussed for graph number I during class. For graph II, the natural loops are {5,6}, {2,3,4,5,6}; the dominator tree of graph II is: (1,2) (2,3) (3,4) (3,7) (4,5) (5,6); Graph II is reducible since all loops are single entry node; the postdominator tree of graph II is: (2,1) (2,3) (2,6) (6,5) (5,4) 7 (Note: 7 is an odd node here since (2,exit) edge in graph means that 7 does not postdominate anything. ) the postdominator tree of graph I is: (6,3) (6,4) (6,5) (3,2) (2,1) ********************************* 3. In proving how the fixed point theorem insures that our worklist algorithm will converge to a solution, I outlined a step to show that F_min(0) (the minimal fixed point of F) is the same as Redefmin (the minimal fixed point of the worklist algorithm starting from 0). Show the details of the induction that proves this point (note: you can use the earlier proved parts of the theorem as necessary) ************************* Gone over in class. ************************* 4. (VTA and call graph construction) Think of a call graph for an object-oriented program on which VTA will derive a better call graph than RTA. Explain why this is so. ******************* Redo this problem for HW #3 *******************