MCS-388 Homework 6 (Spring 2005)

Due: May 6, 2005

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?