# Winter 2001 Midterm Solutions

## Problem 1: True/False

(a) (3 points) If a node n1 dominates a node n2, then n1 is always visited before n2 in a depth-first search.
TRUE. By the definition of domination, all paths that lead to n2 go through n1 first. So, a depth-first search must reach n1 first.
- OR -

FALSE. A post-order depth-first search visits all children of a node before visiting the node itself. By the definition of domination, n2 must be visited first, since it is a child.

(b) (3 points) If a node n1 dominates a node n2, n1 is always visited before n2 in a reverse post ordering.
TRUE. Justification is essentially identical to the "False" answer for 1(a) -- if a post-ordering must list n2 first, then a reverse post-ordering must list n1 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:

 # A B C D E F 1 X X X X 2 X X X X 3 X X X X 4 X X X 5 X X X 6 X X X 7 X X X

This graph only has four live ranges at any given point, but every variable interferes with every other one, and so this cannot be 5-colored.

## 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

We were looking for the following sets of optimizations. Some of these are mutually exclusive.
• 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

Note that warning I is emitted on the second 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).
Issue Warning I on any LOCK stmt that has an in value of Lock.

### II. Unlock -> Unlock

Warning II, like warning I, is emitted on the second instruction. The problem is very similar to I:
• 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).
Issue Warning II on any UNLOCK stmt whose in statement is Unlock.

### III. Lock -> exit

The question asks you to issue a warning "on a LOCK operation if..." . Thus it has to either be a backward problem, or it has to be a forward problem that tags each LOCK statement and treats them like reaching definitions (issuing the warning if any LOCK operation reaches the exit block).
• 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).
Issue Warning III on any LOCK statement whose OUT value is Exits.

### IV. entry -> Unlock

This is very similar to Warning III, except that it runs forward.
• 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).
Issue Warning IV on any UNLOCK statement whose IN value is Enters.

## Wow! That's massively inefficient!

Well, yes. We can actually combine the analyses for warnings I, II, and IV (our lattice now contains the power set of {Enters, Lock, Unlock}, with union as our meet operator) and the analysis functions pretty much as stated before. However, Warning III still requires either a backwards analysis, or a forward analysis of an entirely different nature. You'll need at least two lattices to do it right.