MCS-388 Homework 4 (Spring 2006)

Due: April 11, 2006

Draw a DAG for the expression a-a-a-(a-a)-(a-a-a-a).
Translate the following assignment statement into three address code:
```
a[i] = b[a[i], j] + c[i+j];
```
Assume that all array indexes start at zero, that the starting addresses of the three arrays are available as base_a, base_b, and base_c, that array b is 10 by 20 and stored in row-major order, and that all array elements are 8 bytes in size.
(This problem is a modified version of one from the forthcoming edition of the dragon book.) Consider the following C/C++/Java procedure for computing Fibonacci numbers using tree recusion:
```
int f(int n){
  int t, s;
  if (n<2) return 1;
  s = f(n-1);
  t = f(n-2);
  return s+t;
}
```
Suppose the initial call is f(5).
1. Draw the complete activation tree.
2. Draw the stack of activation records the first time f(1) is about to return. For each activation record, show the following values in this order: n, s, t. Ignore other items that would realistically need to be in the activation records and assume that all variables are in the activation records, not registers. For any variable that has not yet been assigned a value, show a blank slot within the activation record.
3. Draw the stack of activation records again, following the same conventions, but as it exists at the time when f(1) is about to return the fifth time.