50.002 Computation Structures
Information Systems Technology and Design
Singapore University of Technology and Design

Stack and Procedures

Each topic’s questions are grouped into three categories: basic, intermediate, and challenging. You are recommended to do all basic problem set before advancing further.

The Remainder (Basic)

Refer to the C-code below:

int f(int a, int b){
	 if (a<b) return [6];
	 else return f(a-b, b);
	} 

The above C-code compiles to the following Beta assembly code:

F:	PUSH(LP)
	PUSH(BP)
	MOVE(SP, BP)
	PUSH(R1)
	PUSH(R2)
	LD(BP, -12, R0)			| #1
	LD(BP, -16, R1)
	CMPLT([4A], [4B], R2)	

LL01: BNE(R2, LL02)			| #2
	  SUB(R0, R1, R0)
	  PUSH(R1)
	  PUSH(R0)
	  BR(F, LP)			| #3
	  DEALLOCATE(2)

LL02: POP([5a])
      POP([5b])
      MOVE(BP, SP)
      POP(BP)
      POP(LP)
      JMP(LP)

You are given a C function code and its equivalent compiled beta assembly code above. What is the 32-bit binary instruction code of LD(BP,-12,R0) (instruction #1)?
Show Answer

0110 0000 0001 1011 1111 1111 1111 0100
What is the 32-bit binary instruction code of BNE(R2,LL02)(instruction #2)?
Show Answer

0111 1011 1110 0010 0000 0000 0000 0111
What is the 32-bit binary instruction code of BR(F,LP) (instruction #3)?
Show Answer

0111 0111 1001 1111 1111 1111 1110 1101
Complete the assembly code line CMPLT([4a],[4b],R2).
Show Answer

CMPLT(R0,R1,R2).
Complete the assembly code lines POP([5a]) and POP([5b]).
Show Answer

POP(R2), POP(R1)
What is the return value marked by the placeholder [6] in the C code?
Show Answer

The content of variable a.
What is the result of the (potentially recursive) function call f(7,4)?
Show Answer

The result is 3.
If the stack pointer register SP contains the address 0x00001004 before the function f is called (e.g. here, by the instruction BR(F,LP), then what is value of SP before the subsequent instruction in the code is executed (e.g. here, the instruction “DEALLOCATE(2)”).
Show Answer

Reg[SP] = 0x00001004

The GCD (Intermediate)

Consider the following implementation of an algorithm for finding the greatest common divisor of two integers recursively:

int gcd(int a,int b) { 
	if (a == b) return a; 
	if (a > b) return gcd(a-b,b); 
	return gcd(a,b-a); 
} 

The C compiler has compiled this procedure into the following code for an unpipelined Beta processor:

gcd: PUSH (LP) 
PUSH (BP) 
MOVE (SP, BP) 

PUSH (R1) 
PUSH (R2) 
LD (BP, -12, R0) 
LD (BP, -16, R1) 

CMPEQ (R0, R1, R2) 
BT (R2, L1) 
CMPLE (R0, R1, R2) 
BT (R2, L2) 
PUSH (R1) 
SUB (R0, R1, R2)
PUSH (R2) 
BR (gcd, LP) 
DEALLOCATE (2) 
BR (L1) 

L2: SUB (R1, R0, R2) 
PUSH (R2) 
PUSH (R0) 
BR (gcd, LP) 
DEALLOCATE (2)

L1: POP (R2) 
POP (R1) 
MOVE (BP, SP) 
POP (BP) 
POP (LP) 
JMP (LP)

Answer the following questions. For convenience sake, although all data is in 32-bit format we omit writing the leading zeroes.

The program above contains the instruction LD(BP,-16,R1). Explain what the compiler was trying to do when it generated this instruction.
Show Answer

Recall that `BP - 12` is always the first argument of the function. Hence one word / one line above `(BP - 12)`, i.e: `BP - 16` is the second argument of the function. The compiler is loading the value of the second argument (”b”) so it could compute `a == b` later on.
What are the contents of the memory location holding the instruction BR(L1)?
Show Answer
`L1` is a label. Recall that to quickly compute literal you can count the number of instruction lines between `BR` (the instruction that uses "label") and the "label" instruction, and subtract it by 1, then convert it to 16 bits.

Remember that `PUSH` is actually a macro that expands into two Beta instructions, so there are 7 instructions between `L1` and `L2`:
- The location of `L1`, from the assembly code above, is located 1 (from `SUB(R1, R0,R2)` + 2 (from `PUSH(R2)`) + 2 (from `PUSH(R0)`) + 1 (from `BR(gcd, LP)`) + 1 (from `DEALLOCATE(2)`) + 1 (from the **first** instruction in `POP(R2)`, which is the location of `L1`) = **8 words** away from the instruction `BR(L1)`.
- Therefore the 16-bit ’literal’ value for the 32-bit instruction of `BR(L1)` is 8 - 1 = 7, which is 0000 0000 0000 0111.
- The `OPCODE` for `BR` : `BEQ(R31, L1, R31)` is `011101`. `Ra` is `R31`: `111111`, and `Rc` is also `R31`: `111111`.
- Hence the 32-bit instruction of `BR(L1)` is : 011101 11111 11111 0000 0000 0000 0111 = 0x77FF 0007
When the instruction labeled L1 is executed, what is the best characterization of the contents of R0?
Show Answer

`R0` is a reserved register for return value in Beta function linkage procedure. Since `L1` is just at the beginning of the procedure return sequence, so at that point `R0` should contain the value to be returned to the caller.
Looking at the code, a student suggests that both DEALLOCATE instructions could be eliminated since deallocation is performed implicitly by the MOVE(BP,SP) instruction in the exit sequence. After calling gcd, would it be possible to tell if the DEALLOCATE instructions had been removed?

Show Answer

Yes, it would be possible to tell. Even though the stack is reset correctly by the `MOVE(BP,SP)` instruction, that happens after the `POP(R1)` and `POP(R2)` instructions, so they will not restore the values of `R1` and `R2` from the values pushed onto the stack during the entry sequence.
How many words of stack are needed to execute gcd(24,16)? Don’t forget to include the stack space occupied by the arguments in the initial call.

Show Answer

The recursive calls are: gcd(24,16) ---> gcd(8,16) ---> gcd(8,8), at which point no more recursive calls are made. So three nested procedure calls are executed, each with a 6-word stack frame (2 args, `LP`, `BP`, saved `R1`, saved `R2`), for a total of **18 words** of stack space.

During execution of gcd(28,70), the Beta processor is halted and the contents of portions of the stack are found to contain the following:

What is the value of the second argument (b) to the current call to gcd?
Show Answer

The second argument is located at Mem[Reg[BP] - 16] = 0xE.
What is the value in the BP register at the time the stack snapshot was taken?
Show Answer

0x1264. This is computed from the value of old `BP` stored in Mem[Reg[BP] -4] + the size of one stack frame. Mem[Reg[BP] -4] = 0x124C. The size of 1 stack frame is 6 words = 24 bytes = 0x18 bytes. Therefore, 0x1264 = 0x124C + 0x18.
Also, what is the correct value for “???” above in the snapshot of the stack?

Show Answer

The recursive call is: gcd(28,70) ---> gcd(28,42) ---> gcd(28,14), at which point the snapshot was taken. So ”???” is the first argument to the latest preceding call, i.e., 28.
What is the address of the POP(R2) instruction?

Show Answer

All calls in the execution of `gcd(28,70)` have a < b, so all the recursive calls are from the second BR(gcd,LP). Using the value of `LP` stored at `Mem[Reg[BP] - 8]` which points at the `DEALLOCATE` instruction, the `POP(R2)` is stored at location 0x594 + 4 = 0x598.
At the time the stack snapshot was taken, what is the significance of the value 0x1254 in the location at SP?
Show Answer

Since `SP` points to the first unused location on the stack, the value in the location SP points to has no significance to the process, it’s just unused stack space.
The stack snapshot was taken just after the execution of a particular instruction. Could the snapshot have been taken just after the execution of the PUSH(R1) instruction near the beginning of the gcd procedure?
Show Answer

No. Given the values of `BP` and `SP`, the `PUSH(R2)` instruction must have already been executed.

Beta Assembly Exercise (Intermediate)

Part 1:

As a warm-up, hand assemble the following instructions:

ADDC(R1,128,R7)
LD(R11,-4,R0)
ST(R0,-4,R11)
BEQ(R9,0x1C,R27) | this code is written at memory address 0x10

Show Answer

ADDC(R1,128,R7): 0xC0E10080
LD(R11,-4,R0): 0x600BFFFC
ST(R0,-4,R11): 0x640BFFFC
BEQ(R9,0x1C,R27): 0x77690002

Part 2:

The following C code is compiled into byte code:

int f(int x, int *y){
	static int a=0;
	int b=0;
	while(b<x){
		 a=a+y[b];
		 b=b+1;
	}
	return a;
}


int main(int argc, char **argv){
	int z[5]={1,2,3,4,5};
	int r1, r2;
	r1 = f(3,z);
	r2 = f(1, z+1); // z+1 is the address of the second element of z
}  

Refering to the C code in Part 2, state whether each of the following is stored in the: stack, data, or code part of the memory.

Disclaimer

This question is a legacy question, you will not be tested how C compiles as this is not part of our current syllabus. In short, data is a space in the memory dedicated for global variables, static variables (initialized and uninitialized). Dynamically allocated variables are stored in another segment called the heap. Memory management is also language specific, but the general idea is pretty much the same. We will learn more about this in the next term.

Where is z stored?
Where is x stored?
Where is a stored?
Where is b stored?
Where is f stored?
Where is r1 stored?

Finally, what is the value of r1 and r2 after the program finishes?

Show Answer

`z`: stack
`x`: stack
`a`: data
`b`: stack
`f`: code
`R1`: stack

Value of `R1` = 6 and `R2`= 8 after the program finishes.

Part 3:

When the above C code is compiled into byte code, it is equivalent to the following assembly code:

f: 
 PUSH(LP)  
 PUSH(BP)  
 MOVE(SP,BP)  
 PUSH(R1)  
 PUSH(R2)  
 PUSH( <I> ) | you need to fill in what <I> is  
 CMOVE(0,R0)  
 PUSH(R0)  
 
while001:  
 LD(SP,-4,R1)  
 LD(BP,-12,R2)  
 CMPLT(R1,R2,R5) 
 <CD1>(R5,endwhile001) | you need to fill in what <CD1> is  
 LD(BP,-16,R1)  
 LD(SP,-4,R2)  
 MULC(R2,4,R2)  
 ADD(R1,R2,R1)  
 
label1:  
 LD(R1,0,R5)  
 LD(R31,stcvar_001,R1)  
 ADD(R1,R5,R2)  
 ST(R2,stcvar_001,R31)  
 LD(SP,-4,R2)  
 
label2:  
 <CD2>(R2,1,R2)  
 ST(R2,-4,SP)  
 BR(while001)  
 
endwhile001:  
 LDR(stcvar_001,R0)  
 DEALLOCATE(1)  
 POP(<I>) | you need to fill in what <I> is
 POP(<II>) | you need to fill in what <II> is
 POP(<III>) | you need to fill in what <III> is

 POP(BP)  
 POP(LP)  
 JMP(LP)

After executing the assembly code in Part 3 at while001, i.e. LD(SP,-4,R1), what does R1’s content represent in the C code’s variables in Part 2?
Show Answer

`Reg[R1]` represents `b`.
After executing the assembly code in Part 3 at line AFTER while001, i.e. LD(BP,-12,R2), what does R2’s content represent in the C code’s variables in Part 2?
Show Answer

`Reg[R2]` represents x.
What should <I> be in that line of assembly code?
Show Answer

`R5`.
What does R5’s content represent at memory location label1? Look at Part 2 to find the variable name.
Show Answer

`y[b]`.
Which variable in Part 2 correspond to stcvar_001?
Show Answer

`a`.
What should <CD1> be in the assembly code?
Show Answer

`BEQ`.
What should <CD2> be in the assembly code?
Show Answer

`ADDC`.
What should <II> be in the assembly code?
Show Answer

`R2`.
What should <III> be in the assembly code?
Show Answer

`R1`.