Homework 2 Due Jan 28^th, 1998

1. From Muchnick, Question 8.3
2. The iterative data-flow algorithm in class is simpler than the one in the text (Figure 8.6). Explain and illustrate (using any data-flow problem of your choice) why the algorithm in text may be better.
3. Let?s suppose you want to write a compiler analysis that generates a warning every time a program tries to use an unitialized variable. For example:

main() {
  int i;
  j := i + 1;
  <program-point-1>
}
main() {
     int i;
    if (pred()) i := 1
    else i := 2
    j := i + 1
    <program-point-2>
}
main() {
    int i;
    if (pred()) i := 1
    j := i + 1
    <program-point-3>
}
At program-point-1, both i and j are unitialized. At program-point-2, both i and j are initialized. Finally, at program-point-3 both i and j may be unitialized.
Design a data-flow analysis that determines for each program point, which variables may contain unitialized values.
4. Consider the following code:

i := 0
do {
    j := 0
    do {
        a[i,j] := i + j
        j := j + 1
    while (j < n)
    i := i + 1
} while (i < n)
Build a flow graph for this code, compute the iterated dominance fronter for it (showing all steps), and finally, convert it into SSA form.