Homework # 5
due February 27

UD versus ud

Do problem 1 of Mini Project 2.1: prove that ud and UD compute the same information. You may modify the definition of clear so that it doesn't include the conjunct ``use'', as long as then this conjunct is added in the definitions of ud and du.

A technique to use in the proof is to define a function rd that uses the same definitions as for ud and then show that rd and RD are the same sets.

Modified Analyses

Do Exercises 2.3 and 2.4, defining modifications of available expression and live variable analyses. Note that Strongly Live Variable Analysis SLVA (the modification of live variable analysis) cannot be expressed using KILL and GEN sets, but rather must specify a transfer function. Also SLVA requires that you initialize the set of strongly live variables at the end of the program to include a special ``return''' variable.

Here are some examples of SLVA:

• r := r + 1;
  Here r is strongly live before the assignment.
• x := 1;
  y := x + 1;
  z := y + 1;
  a := z + 1;
  r := x;
  Note that the assignments to y, z and a are all to faint variables.
• a := 1;
  r := 100;
  while b > 0 do
        a := a + 1;
        r := r - 1;
        b := b - 1;
  end;
  r := r + 1;
  Here b is strongly live until the loop is done; a is faint everywhere and r is strongly live after its first assignment.

Submission

As with all homeworks, please turn in your homework on paper at the beginning of lecture.

About this document