MCS-388 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
up-safe, 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
up-safe, then use that to show that no node that is delay is
up-safe (see below), and then finally use that to (trivially)
show that no node that is latest is up-safe. Note: in
showing that no delay node is up-safe, 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 down-safe? Up-safe? Earliest? Delay? Latest? Which
nodes should a+b
be computed at the beginning of?
Course web site: http://www.gac.edu/~max/courses/S2005/MCS-388/
Instructor: Max Hailperin <max@gustavus.edu>