MC97 Homework 6 (Spring 1997)

Due: May 16, 1997

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 suppression of partial redundancies. 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 suppression of partial redundancies, 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/S97/MC97/
Instructor: Max Hailperin <max@gac.edu>