Activation Record Length

Question

I get 6,4,3 for the first 3 questions respectively, but I don't know how to figure out the last one. However, the solution manual indicated 7,5,4,18 as the answers.

int sum(int x[], int N) {
  int k = 0;
  int s = 0;
  while (k < N) {
    s = s + x[k];
    k = k + 1;
  }
  return s; // the activation record for sum will be ____________ locations
}

int fred(int a, int b) {
  return a + b;  // (2) the activation record for fred will be ____________ locations
}

void barney(int x) {
  x = fred(x, x);//(2) the activation record for barney will be ____________ locations
}

void main(void) {
  int a[4];
  int x = sum(a, 4);
  barney(x); 
} // (3) the stack must have at least _____________ locations to run this program

Answer 1

I dont know what is the convention of your book, but I assume, there is always a place for return address, address of return value and intermediate results

a)return address, address of return result, x, N, k, s, intermediate result for s + x[k] = total 7

b)ret. addr, addr of ret result, a, b, int. res. a+b = total 5

c)ret. addr, addr of ret result, x, space for return result of fred = total 4

d)last one is not asking the activation record max required stack size at any given point. It calls sum, It calls barney and barney calls fred that is 7+5+4 = 16. And 16 + a + x = total 18 locations to run this program.

Note that, this calculations are based on my wild guess about your books convention.

Answer 2

My guess is that the one location you are missing in each of the first three assignments is the saved frame pointer, i.e. the pointer to the current stack location before local variables are allocated. The frame pointer needs to be restored on exit of the function so that the return address is indeed at the top of stack before the function returns.

The solution to the last task is just the maximum of the sums of the allocation record lengths arl of nested calls. So, in this example

arl(program) = max(arl(main)+arl(sum), arl(main)+arl(barney)+arl(fred))

sum and barney are not called at the same time, so they don't need to be added, as the allocation record for sum is already freed when the one for barney is allocated.

As arl(main) is 7 (return address, saved frame pointer, array of 4 ints, int), the second sum gives the bigger value of 16. However, this is two less than the indicated answer.Maybe your book gives you an indication what the other two locations are supposed to be.