Winter 2001 Midterm Solutions

Problem 1: True/False

(b) (3 points) If a node n₁ dominates a node n₂, n₁ is always visited before n₂ in a reverse post ordering.
TRUE. Justification is essentially identical to the "False" answer for 1(a) -- if a post-ordering must list n₂ first, then a reverse post-ordering must list n₁ first.

(c) (3 points) Given a monotone data flow framework, had all the interior points of the data flow solver been initialized with the "bottom" of the semi-lattice, the answer at every point in every program would have been "bottom."
FALSE. Even though any element met with bottom is itself bottom, this makes no assumption about the results of the transfer function. Suppose the transfer function returns a single constant value (not bottom). This is definitely monotone (no matter the values of x and y, f(x) ≤ f(y)), and the values once the solution stabilizes will definitely not all be bottom.

(d) (4 points) Given a machine with 5 registers, Chaitin's register coloring algorithm (the one presented in class) will succeed in coloring any program that has no more than 4 active live ranges at any point in the program.
FALSE. Unfortunately, the number of live ranges at any given point has nothing to do with the interference graph. Consider the following set of merged live ranges:

Problem 2: Dominators, loops, and reducibility

(a) (3 points) Show the dominator tree for this flowgraph.
1 dominates everything, 2 dominates everything but 1, and nothing else dominates anything but itself. The dominator tree looks like this:

               1
               |
               2
               |
          +-+-+++-+-+
          3 4 5 6 7 8

(b) (2 points) What are the back edges of this flowgraph?
The back edges are 4->1 and 6->2.

(c) (4 points) Find the natural loop associated with each of the back edges.
4->1: {1 2 3 4 6}
6->2: {2 3 4 6}

(d) (3 points) Is the flow graph reducible?
No. The edge 7->5 is a retreating edge that is not a back edge. The graph is not reducible.

Problem 3: Optimization

• Constant propagation. No expressions may be removed, but we must at least note that g is 10 at the bottom of the loop. If we actually do the substitutions, we'll get to do some common subexpression elimination later, as well.
• (8 pts) Loop invariants. w = a+b could be hoisted out of the loop, since both a and b are defined outside of the loop. g = 10 and x = 15 can not, since they do not dominate the exit. (If you transformed the while loop into a repeat loop, then you could hoist those assignments. This is fine.) c = f() cannot be hoisted because it may have side effects (like a printf() command or some such).
• (6 pts) Strength reduction. The basic induction variable is d, which has derived variables j and e (g is a loop invariant, recall). Variables j' and e' should be introduced, and they should only be updated when the basic induction variable, d, is updated. Nothing happens to j' or e' at the location of the command j = d + 2.
• (2 pts) Induction variable elimination. After strength reduction, none of the induction variables compute anything other than their own values. We may move d out of the loop, adding a statement d = j'-2 after leaving the loop. (Actually, since j also doesn't compute anything inside the loop, and its assignment dominates the exit, we may kick it out too; however, this was not required. e may not be kicked out because its assignment does not dominate the loop exit, so e may preserve its original value by the time of loop exit.)
• (4 pts) Miscellaneous. If you actually folded the constants into the expressions, then the expression 10 * c became targetable by common subexpression elimination. Or, one could have hoisted very busy expressions and hoisted 10 * c or g * c up above the g = 10 branch. Or, one could be exceptionally tricky and perform partial redunancy elimination and pre-compute g * c on each branch in the loop.

Problem 4: Dataflow analysis

For simplicity assume one statement per basic block. Composition is trivial. Once the dataflow problems have been solved, printing of the Warnings is done using the content of the block and the result of the analysis at the block.

I. Lock -> Lock

• Forward
• {NoLock, Lock}
• NoLock -> Lock
• All points (including boundary) are NoLock.
• Transfer function = Lock if stmt is LOCK; NoLock if stmt is UNLOCK; and simply propagates the input if the stmt is something else.
• Monotone, Distributive, and convergent (monotone & finite descending chains).

II. Unlock -> Unlock

• Forward
• {NoUnlock, Unlock}
• NoUnlock -> Unlock
• All points (including boundary) are NoUnlock.
• Transfer function = Unlock if stmt is UNLOCK; NoUnlock if stmt is LOCK; and simply propagates the input if the stmt is something else.
• Monotone, Distributive, and convergent (monotone & finite descending chains).

III. Lock -> exit

• Backward
• {Exits, CannotExit}
• CannotExit -> Exits
• Interior points are CannotExit.
• in[exit] is Exits.
• Transfer function = CannotExit if the stmt is LOCK or UNLOCK and propagates its output otherwise.
• Monotone, Distributive, and convergent (monotone & finite descending chains).

IV. entry -> Unlock

• Forward
• {Enters, CannotEnter}
• CannotEnter -> Enters
• Interior points are CannotEnter.
• out[entry] is Enters.
• Transfer function = CannotEnter if the stmt is LOCK or UNLOCK and propagates its input otherwise.
• Monotone, Distributive, and convergent (monotone & finite descending chains).

Wow! That's massively inefficient!