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
a+b be computed at the beginning of?
Course web site: http://www.gac.edu/~max/courses/S2005/MCS-388/
Instructor: Max Hailperin <email@example.com>