**(b)** (3 points) If a node n_{1} dominates a node
n_{2}, n_{1} is always visited before n_{2} in a
reverse post ordering.

*TRUE. Justification is essentially identical to the "False" answer
for 1(a) -- if a post-ordering must list n _{2} first, then a
reverse post-ordering must list n_{1} 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 |

**(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.*

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

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.

- 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).

- 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).

- 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).

- 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).