CMOVE (1024, R0)
PUSH (R0)
CMOVE (-256, R0)
PUSH (R0)
BR (foo, LP)
DEALLOCATE (2)

a) CMPLTC (R1, 0, R0)
b) CMPLEC (R1, -1, R0)
c) SRAC (R1, 31, R0)
d) SHRC (R1, 31, R0)
e) All of the above
f) None of the above

R0 = 0            Mem[0x1000] = 0x00001024
R1 = 0xbba00000   Mem[0x1004] = 0x000000e0
                  Mem[0x1008] = 0x00000001
                  Mem[0x100c] = 0x800000cc
      .           Mem[0x1010] = 0x00001004
      .           Mem[0x1014] = 0x00001000
      .           Mem[0x1018] = 0x00001774
                  Mem[0x101c] = 0x80000084
                  Mem[0x1020] = 0x00001014
BP = 0x00001024   Mem[0x1024] = 0x00001000
LP = 0x80000084   Mem[0x1028] = 0xafadcafe
SP = 0x00001028   Mem[0x102c] = 0xabadcafe

What is the value of the label foo? You can't determine the value of the label foo since the procedure doesn't call any subroutines iteself and leave a PC somewhere we can examine. What argument was the function foo called with in this instance? First argument is stored at Mem[Reg[BP] - 12] = 0x00001774. Assuming that foo was itself called from some other function, what was the first argument to that function? The BP for the function that called foo is at Mem[Reg[BP] - 4] = 0x1014. The first argument for that function is at Mem[0x1014 - 12] = 0x00000001. Consider yet another C function for computing the greatest common denominator between two numbers, x and y:

int gcd(int x, int y)
 {
   if (x == y) return x;
   if (y > x)
     y = y - x;
   else
     x = x - y;
   return gcd(x, y);
 }

gcd:    PUSH (LP)
        PUSH (BP)
        MOVE (SP, BP)
        PUSH (R1)
        PUSH (R2)
        LD (BP, -12, R1)
        LD (BP, -16, R2)
        CMPEQ (R2, R1, R0)
        BF (R0, ifxgty)
        MOVE (R1, R0)
        BR (done)
ifxgty: CMPLE (R2, R1, R0)
        BT (R0, else)
        SUB (R2, R1, R2)
        BR (call)
else:   SUB (R1, R2, R1)
call:   PUSH (R2)
        PUSH (R1)
        BR (gcd, LP)
        DEALLOCATE (2)
done:   POP (R2)
        POP (R1)
        POP (BP)
        POP (LP)
        JMP (LP)

The contents of the blank table entries are unknown. Fill in as many blank spaces as possible in the table above and indicate those locations whose contents cannot be determined from the supplied information. The table below shows what we can deduce about the contents of the stack from what we have been given. Here are some notes on how we did this:

• By looking at the code, we can tell that each stack frame would be 6 words long. Tracing the frames from the beginning, we can mark out the stack frames and thus know what purpose each memory location serves (e.g., holding LP, etc.)
• Since all but the first stack frame belongs to a recursive call from gcd to itself, and since there is only one place in gcd where it calls itself, we know that, except in the first frame, the saved LP should have the same value in all the frames: 0x80000068. Similarly, knowing the stack frame structure allows us to know where BP will be pointing in each stack frame. This lets us know the value of BP that will be saved in the next stack frame. This way we can determine the BP values saved in all the frames except the first.
• To determine the arguments, we need to work backwards. First, we note that the values of R1 and R2 when the program was stopped tell us the arguments x and y, respectively, of the current invocation of gcd. This is because the previous invocation used R1 and R2 for pushing the arguments to the recursive call. Thus, we know 0x8060 contains y=3, and 0x8064 contains x=6. We further know that the arguments to the previous invocation were y=9 and x=6 because the fact that R0 was 0 when we stopped the program tells us that in the previous invocation, y was greater than x and that the new y (i.e., 3) was the difference between the old y (i.e., 9) and the old x (i.e., 6).
• Unfortunately, knowing that the third invocation to gcd was gcd(x=6,y=9) does not tell us for sure what the arguments to the invocation before that one were. They could have been (6,15) or (15,9). Fortunately, it is not too hard to draw a binary tree of the possible arguments for each call to gcd. If we do this, we will find that of the 8 possible argument pairs for the top-level call to gcd, only (x=24,y=33) has 24 as its first argument.
• Finally, after filling-in the arguments, we can trace through the code and determine the values in the R1 and R2 slots. We can do this more quickly by noticing the relation between the pushed R1 and R2 values and the arguments before them. Note however, that this pattern is not a general rule, but just occurs because gcd uses R1 and R2 when PUSHing arguments.
• We cannot know the values in memory locations 0x800C to 0x8014 because we don't know exactly what main (gcd's original caller) was doing with BP, R1 and R2 before it called gcd. For example, main does not have to use R1 and R2 to PUSH the arguments, so we cannot determine R1 and R2 as we did for the recursive calls.

Mem. Loc.    Contents    Comments

0x8000       33          initial y
0x8004       24          initial x
0x8008       0x800000B0  main's return addr
0x800C       unknown     main's BP
0x8010       unknown     main's R1
0x8014       unknown     main's R2
------------------------------------------
0x8018       9           y
0x801C       24          x
0x8020       0x80000068  gcd's return addr
0x8024       0x8010      previous gcd's BP
0x8028       24          previous gcd's R1
0x802C       9           previous gcd's R2
------------------------------------------
0x8030       9           y
0x8034       15          x
0x8038       0x80000068  gcd's return addr
0x803C       0x8028      previous gcd's BP
0x8040       15          previous gcd's R1
0x8044       9           previous gcd's R2
------------------------------------------
0x8048       9           y
0x804C       6           x
0x8050       0x80000068  gcd's return addr
0x8054       0x8040      previous gcd's BP
0x8058       6           previous gcd's R1
0x805C       9           previous gcd's R2
------------------------------------------
0x8060       3           y
0x8064       6           x
0x8068       0x80000068  gcd's return addr
0x806C       0x8058      previous gcd's BP
0x8070       0xC0FFEE    free
0x8074       0xC0FFEE	 free
0x8078       0xC0FFEE    free
0x807C       0xC0FFEE    free

To be concrete, consider the following procedure and its call:

int F(int a, int b)
 { int x;
   x = a*b;
   return (x + x*b)
 }
...
z = F(23, 41);
...

The natural place to return the value of the procedure is on the stack, but it is awkward to allocate this location in the caller because it blocks access to the return value. How does your proposed convention deal with this problem? We have to make sure the return value on the stack is accessible to the callee as well as placed before the return value on the stack. If the callee always knows how many values it has pushed onto the stack, and it knows the last two things on the stack before it was called is the return value followed by the return address, then it can use STORE-SP to store the value onto the return value. Diagram the layout of the stack using your conventions. Show the location of stacked arguments, local variables, the return value, and any temporaries used by the caller. STACK layout:

argn
argn-1

arg1
return location
return value
local argn
local argn-1

local arg1
temporaries