MCS388 Homework 6 (Spring 2005)
Due: May 6, 2005
Do one, and only one, of the following problems; you may choose either:

For the theorist:

Prove that no node that is latest is
upsafe, using the definitions of those terms given in the
handout on partial redundancy elimination. You will presumably
want to first show that no node that is earliest is
upsafe, then use that to show that no node that is delay is
upsafe (see below), and then finally use that to (trivially)
show that no node that is latest is upsafe. Note: in
showing that no delay node is upsafe, you may assume that
all nodes are reachable from the start node.
 For the practitioner:
 Subject the flow graph shown below
to the dataflow analyses described in the handout on
partial redundancy elimination, using
a+b
as the expression in question.
Which nodes are downsafe? Upsafe? Earliest? Delay? Latest? Which
nodes should a+b
be computed at the beginning of?
Course web site: http://www.gac.edu/~max/courses/S2005/MCS388/
Instructor: Max Hailperin <max@gustavus.edu>