COMP 411: Computer Organization Procedures and Stacks Don Porter 1

COMP 411: Computer Organization Procedures and Stacks Don Porter 1

COMP 411: Computer Organization Today Procedures – – – – What are procedures? Why use them? How is call/return implemented in assembly? Recursion Stacks – Push and pop – How useful for implementing procedures? 2

COMP 411: Computer Organization What are Procedures? Also called: – functions – methods – subroutines Key Idea: – main routine M calls a procedure P – P does some work, then returns to M execution in M picks up where left off i.e., the instruction in M right after the one that called P 3

COMP 411: Computer Organization Why Use Procedures? Readability – divide up long program into smaller procedures Reusability – call same procedure from many parts of code – programmers can use each others’ code Parameterizability – same function can be called with different arguments/parameters at runtime Polymorphism (in OOP) – in C /Java, behavior can be determined at runtime as opposed to compile time Any other reason ? 4

COMP 411: Computer Organization Why Use Procedures? Examples: – Reusable code fragments (modular design) clear screen(); # code to draw a bunch of lines clear screen(); – Parameterized functions (variable behaviors) line(x1, y1, x2, y2, color); line(x2,y2,x3,y3, color); # Draw a polygon for (i 0; i N-1; i ) line(x[i],y[i],x[i 1],y[i 1],color); line(x[i],y[i],x[0],y[0],color); 5

COMP 411: Computer Organization Another Reason: Scope of Variables Local scope (Independence) int x 9; These are different “x”s int fee(int x) { return x x-1; } This is yet another “x” int foo(int i) { int x 0; while (i 0) { x x fee(i); i i - 1; } return x; } main() { fee(foo(x)); } Removes need to keep track of all of the variable names! 6

COMP 411: Computer Organization Using Procedures A “calling” program (Caller) must: – Provide procedure “parameters” / “arguments” put the arguments in a place where the procedure can access them – Transfer control to the procedure jump to it A “called” procedure (Callee) must: – – – – Acquire the resources needed to perform the function Perform the function Place results in a place where the Caller can find them Return control back to the Caller Solution (at least a partial one): – Allocate registers for these specific functions 7

COMP 411: Computer Organization MIPS Register Usage Conventions designate registers for procedure arguments ( 4- 7) and return values ( 2 3). The ISA designates a “linkage register” for calling procedures ( 31) – allows Callee to go back to Caller once done Transfer control to Callee using the jal instruction Return to Caller with the jr 31 or jr ra instruction Name zero at v0- v1 a0- a3 t0- t7 s0- s7 t8- t9 k0- k1 gp sp fp ra Register number 0 1 2-3 4-7 8-15 16-23 24-25 26-27 28 29 30 31 Usage the constant value 0 assembler temporary procedure return values procedure arguments temporaries saved by callee more temporaries reserved for operating system global pointer stack pointer frame pointer 8 return address

COMP 411: Computer Organization And It “Sort Of” Works Works for special cases Example: .data x: .word 9 Callee .text main: lw jal . But there are lots of unaddressed issues: a0, x fee fee: add addi jr v0, a0, a0 v0, v0,-1 ra (fee computes 2*x - 1) – where the Callee is a “LEAF” function – Callee doesn’t call anybody, and needs few resources Caller – how can fee call another? – how can we have more than 4 arguments? – where are local variables stored? Let’s consider the worst case: recursion – Callee is also a Caller 9

COMP 411: Computer Organization Writing Procedures int sqr(int x) { if (x 1) x sqr(x-1) x x-1; return x; } main() { sqr(10); } How do we go about writing callable procedures? We’d like to support not only LEAF procedures, but also procedures that call other procedures, ad infinitum (e.g. a recursive function). sqr(10) sqr(9) 10 10-1 100 sqr(9) sqr(8) 9 9-1 81 sqr(8) sqr(7) 8 8-1 64 sqr(7) sqr(6) 7 7-1 49 sqr(6) sqr(5) 6 6-1 36 sqr(5) sqr(4) 5 5-1 25 sqr(4) sqr(3) 4 4-1 16 sqr(3) sqr(2) 3 3-1 9 sqr(2) sqr(1) 2 2-1 4 sqr(1) 1 sqr(0) 0 10

COMP 411: Computer Organization Procedure Linkage: First Try Callee/Caller int sqr(int x) { if (x 1) x sqr(x-1) x x-1; return x; } OOPS! Caller main() { sqr(10); } t0 is clobbered on successive calls. Will saving “x” in some register or at some fixed location in memory help? MIPS MIPSConvention: Convention: st pass pass11starg argxxin in a0 a0 save savereturn returnaddr addrin in ra ra return returnresult resultin in v0 v0 use usetemp tempregisters registers for forscratch scratchwork work sqr: slti t0, a0,2 beq t0, 0,then #!(x 2) add v0, 0, a0 j rtn then: add t0, 0, a0 addi a0, a0,-1 jal sqr add v0, v0, t0 add v0, v0, t0 addi v0, v0,-1 rtn: jr ra We also clobber our return address, so there’s no way back! 11

COMP 411: Computer Organization A Procedure’s Storage Needs Basic Overhead for Procedures/Functions: – Caller sets up ARGUMENTs for callee f(x,y,z) or even. sin(a b) – Caller invokes Callee while saving the Return Address to get back – Callee saves stuff that Caller expects to remain unchanged – Callee executes – Callee passes results back to Caller. Local variables of Callee: In C it’s the caller’s job to evaluate its arguments as expressions, and pass the resulting values to the callee Therefore, the CALLEE has to save arguments if it wants access to them after calling some other procedure, because they might not be around in any variable, to look up later. . { int x, y; . x . y .; } Each of these is specific to a “particular” invocation or activation of the Callee. Collectively, the arguments passed in, the return address, and the callee’s local variables are its activation record, or call frame. 12

COMP 411: Computer Organization Lives of Activation Records int sqr(int x) { if (x 1) x sqr(x-1) x x-1; return x; } sqr(3) Where do we store activation records? TIME sqr(3) sqr(3) sqr(3) sqr(2) sqr(2) sqr(2) sqr(3) sqr(1) A procedure call creates a new activation record. Caller’s record is preserved because we’ll need it when call finally returns. Return to previous activation record when procedure finishes, permanently discarding activation record created by call we are returning from. 13

COMP 411: Computer Organization We Need Dynamic Storage! What we need is a SCRATCH memory for holding temporary variables. We’d like for this memory to grow and shrink as needed. And, we’d like it to have an easy management policy. One possibility is a STACK A last-in-first-out (LIFO) data structure. Some interesting properties of stacks: SMALL OVERHEAD. Only the top is directly visible, the so-called “top-of-stack” Add things by PUSHING new values on top. Remove things by POPPING off values. 14

COMP 411: Computer Organization MIPS Stack Convention Waste a register for the Stack Pointer ( sp 29). Stack grows DOWN (towards lower addresses) on pushes and allocates sp points to the TOP *used* location. Place stack far away from our program and its data Higher addresses 800000016 “stack” segment sp 1000800016 Data Humm Why is that the TOP of the stack? CONVENTIONS: 1000000016 0040000016 “text” segment (Program) Reserved Lower addresses Other Otherpossible possibleimplementations implementations include: include: 1) 1)stacks stacksthat thatgrow grow“UP” “UP” 15 2) 2)SP SPpoints pointsto tofirst firstUNUSED UNUSED

COMP 411: Computer Organization Stack Management Primitives ALLOCATE k: reserve k WORDS of stack Reg[SP] Reg[SP] - 4*k addi addi sp, sp,-4*k sp, sp,-4*k DEALLOCATE k: release k WORDS of stack Reg[SP] Reg[SP] 4*k addi addi sp, sp,4*k sp, sp,4*k PUSH rx: push Reg[x] onto stack Reg[SP] Reg[SP] - 4 Mem[Reg[SP]] Reg[x] POP addi addi sp, sp,-4 sp, sp,-4 sw sw rx, rx,0( sp) 0( sp) rx: pop the value on the top of the stack into Reg[x] Reg[x] Mem[Reg[SP]] lw lw rx, rx,0( sp) 0( sp) Reg[SP] Reg[SP] 4; addi addi sp, sp,4 sp, sp,4 16

COMP 411: Computer Organization Solving Procedure Linkage “Problems” In case you forgot, a reminder of our problems – – – – We need a way to pass arguments into procedures Procedures need storage for their LOCAL variables Procedures need to call other procedures Procedures might call themselves (Recursion) But first: Let’s “waste” some more registers: – 30 fp (frame pointer) points to the start of callee’s activation record on the stack we also use it to access extra args ( 4) – 29 sp (stack pointer, points to TOP of stack) points to the and of callee’s activation record on the stack – Together: 29 and 30 are bookends to activation record – 31 ra (return address back to caller) 17

COMP 411: Computer Organization More MIPS Procedure Conventions What needs to be saved? – CHOICE 1 anything that a Callee touches except the return value registers – CHOICE 2 Give the Callee access to everything Caller saves those registers it expects to remain unchanged – CHOICE 3 Something in between Give the Callee some “scratch” registers to play with – If the Caller cares about these, it must preserve them ( t registers) Give the Caller some registers that the Callee won’t clobber – If the Callee touches them, it must restore them ( s registers) MIPS designers chose #3 18

COMP 411: Computer Organization Stack Frame or Activation Record The STACK FRAME contains storage for the CALLER’s volatile state that it wants preserved after the invocation of CALLEEs. CALLER’s Stack Frame FP: In addition, the CALLEE will use the stack for the following: 1) Accessing the arguments that the CALLER passes to it (specifically, the 5th and greater) 2) Saving non-temporary registers that it wishes to modify 3) Accessing its own local variables The boundary between stack frames falls at the first word of state saved by the CALLEE, and just after the extra arguments ( 4, if used) passed in from the CALLER. The FRAME POINTER keeps track of this boundary between stack frames. Args 4 Saved regs Local variables CALLEE’s Stack Frame SP: (unused) ItItisispossible possibletotouse useonly onlythe theSP SPtoto access accessaastack stackframe, frame,but butoffsets offsetsmay may change changedue duetotoALLOCATEs ALLOCATEsand and DEALLOCATEs. DEALLOCATEs. For Forconvenience convenienceaa fp fpisis used usedtotoprovide provideCONSTANT CONSTANToffsets offsetstoto 19 local localvariables variablesand andarguments arguments

COMP 411: Computer Organization Procedure Stack Usage ADDITIONAL space must be allocated in the stack frame for: 1. 2. 3. 4. 5. Any SAVED registers the procedure uses ( s0- s7) Any TEMPORARY registers that the procedure wants preserved IF it calls other procedures ( t0- t9) Any LOCAL variables declared within the procedure Other TEMP space IF the procedure runs out of registers (RARE) Enough “outgoing” arguments to satisfy the worse case ARGUMENT SPILL of ANY procedure it calls. (SPILL is the number of arguments greater than 4). Each procedure has keep track of how many SAVED and TEMPORARY registers are on the stack in order to calculate the offsets to LOCAL VARIABLES. 20

COMP 411: Computer Organization More MIPS Register Usage The registers s0- s7, sp, ra, gp, fp, and the stack above the memory above the stack pointer must be preserved by the CALLEE The CALLEE is free to use t0- t9, a0- a3, and v0- v1, and the memory below the stack pointer. No “user” program can use k0- k1, or at Name zero at v0- v1 a0- a3 t0- t7 s0- s7 t8- t9 k0- k1 gp sp fp ra Register number 0 1 2-3 4-7 8-15 16-23 24-25 26-27 28 29 30 31 Usage the constant value 0 assembler temporary procedure return values procedure arguments temporaries saved by callee more temporaries reserved for operating system global pointer stack pointer frame pointer return address 21

COMP 411: Computer Organization Stack Snap Shot: A typical procedure fp A typical “activation record” or “stack frame” ra – save ra and fp first – save values of “saved regs” modified by this proc fp s0 e.g.: s0, s1, s2, s3 – save values of “temp regs” that must survive calls to other procs from this proc e.g.: t0, t1 should be saved immediately before calling other proc; restored immediately after – any local variables needed (that are not in regs) reside on the stack s1 s2 s3 t0 t1 e.g.: locals var1 varn – any spillover args for calling other procs [in reverse order] e.g.: arg[4], arg[5] why reverse order? local var1 local varn arg[5] sp arg[4] 22

COMP 411: Computer Organization Stack Snap Shot: Caller Callee CALLER’s fp ra fp s0 s1 s2 proc A calls proc B s3 – B has less stuff that needs to be saved on stack t0 t1 local var1 – Can you tell the number of args for B? NOPE! – Can you tell the max number of args needed by any procedure called by A? CALLER A’S FRAME local varn Arg[5] sp (prior to call) CALLEE’s fp Arg[4] ra fp Yes, 6 local var1 – Where in CALLEE’s stack frame might one find CALLER’s fp? local var2 CALLEE B’S FRAME Arg[6] At -4( fp) Arg[5] sp (after call) Arg[4] 23

COMP 411: Computer Organization Back to Reality Now let’s make our example work, using a minimal stack frame sqr: addi sp, sp,-8 int sqr(int x) { if (x 1) x sqr(x-1) x x-1; return x; } main() { sqr(10); } Q: Why didn’t we save and update fp? A: Don’t have local variables or spilled args. Save registers that must survive the call. sw ra,4( sp) sw a0,0( sp) slti t0, a0,2 beq t0, 0,then add v0, 0, a0 j rtn then: addi a0, a0,-1 jal sqr Pass lw a0,0( sp) arguments add v0, v0, a0 add v0, v0, a0 addi v0, v0,-1 rtn: lw ra,4( sp) addi sp, sp,8 jr ra Restore saved registers . ALLOCATE minimum stack frame. With room for the return address and the passed in argument. DEALLOCATE stack frame. 24

COMP 411: Computer Organization Testing Reality’s Boundaries Now let’s take a look at the active stack frames at some point during the procedure’s execution. ra 0x00400018 a0 1010 ra 0x00400074 a0 910 ra 0x00400074 sp a0 810 sqr: addi sp, sp,-8 sw ra,4( sp) sw a0,0( sp) slti t0, a0,2 beq t0, 0,then Return Address to original caller move v0, a0 j rtn then: addi a0, a0,-1 jal sqr lw a0,0( sp) PC add v0, v0, a0 add v0, v0, a0 addi v0, v0,-1 rtn: lw ra,4( sp) addi sp, sp,8 jr ra 25

COMP 411: Computer Organization Procedure Linkage is Nontrivial The details can be overwhelming. How do we manage this complexity? – Abstraction: High-level languages hide the details There are great many implementation choices: – which variables are saved – who saves them – where are arguments stored? Solution: CONTRACTS! – Caller and Callee must agree on the details 26

COMP 411: Computer Organization Procedure Linkage: Caller Contract The CALLER will: Save all temp registers that it wants to survive subsequent calls in its stack frame (t0- t9, a0- a3, and v0- v1) Pass the first 4 arguments in registers a0- a3, and save subsequent arguments on stack, in *reverse* order. Why? Call procedure, using a jal instruction (places return address in ra). Access procedure’s return values in v0- v1 27

COMP 411: Computer Organization Code Lawyer Our running example is a CALLER. Let’s make sure it obeys its contractual obligations int sqr(int x) { if (x 1) x sqr(x-1) x x-1; return x; } sqr: addiu sp, sp,-8 sw ra,4( sp) sw a0,0( sp) slti t0, a0,2 beq t0, 0,then add v0, 0, a0 j rtn then: addi a0, a0,-1 jal sqr lw a0,0( sp) add v0, v0, a0 add v0, v0, a0 addi v0, v0,-1 rtn: lw ra,4( sp) addiu sp, sp,8 jr ra 28

COMP 411: Computer Organization Procedure Linkage: Callee Contract If needed the CALLEE will: 1) Allocate a stack frame with space for saved registers, local variables, and spilled args 2) Save any “preserved” registers used: ( ra, sp, fp, gp, s0- s7) 3) If CALLEE has local variables -or- needs access to args on the stack, save CALLER’s frame pointer and set fp to 1st entry of CALLEE’s stack 4) EXECUTE procedure 5) Place return values in v0- v1 6) Restore saved registers 7) Fix sp to its original value 8) Return to CALLER with jr ra 29

COMP 411: Computer Organization More Legalese Our running example is also a CALLEE. Are these contractual obligations satisfied? int sqr(int x) { if (x 1) x sqr(x-1) x x-1; return x; } sqr: addiu sp, sp,-8 sw ra,4( sp) sw a0,0( sp) slti t0, a0,2 beq t0, 0,then add v0, 0, a0 j rtn then: addi a0, a0,-1 jal sqr lw a0,0( sp) add v0, v0, a0 add v0, v0, a0 addi v0, v0,-1 rtn: lw ra,4( sp) addiu sp, sp,8 jr ra 30

COMP 411: Computer Organization Conclusions Need a convention (contract) between caller and callee Implement stack for storing each procedure’s variables Procedure calls can now be arbitrarily nested – Recursion possible too FOLLOW the convention meticulously! 31

COMP 411: Computer Organization A few procedure templates

COMP 411: Computer Organization Ex1: simple leaf proc (w/o stack frame) main: – doesn’t need to preserve any temporary registers proc1: – is a leaf proc (doesn’t call any other proc) – doesn’t touch any saved regs main: jal proc1 . stuff proc1: . jr ra # call proc1 # other main # do the task # return stack frame ne no ed! d nee 33

COMP 411: Computer Organization Ex2: leaf proc with stack frame main: – doesn’t need to preserve any temporary registers proc1: – is leaf; doesn’t touch any saved regs – creates minimal stack frame (but doesn’t really need it) main: jal proc1 # call proc1 . # other main stuff proc1: addi sp, sp, -8 sw ra, 4( sp) # Save ra sw fp, 0( sp) # Save fp addi fp, sp, 4 # Set fp . fp ra sp fp # do the task addi sp, fp, 4 lw ra, 0( fp) lw fp, -4( fp) jr ra # Return # Restore sp # Restore ra # Restore fp

COMP 411: Computer Organization Ex3: minimal non-leaf proc proc1: – calls proc2 – doesn’t need to preserve any data values in regs – creates minimal stack frame (and needs it for saving return address) fp sp ra fp proc1: addi sp, sp, -8 sw ra, 4( sp) # Save ra sw fp, 0( sp) # Save fp addi fp, sp, 4 # Set fp . jal proc2 . # call another addi sp, fp, 4 # Restore lw ra, 0( fp) # Restore lw fp, -4( fp) # Restore sp ra fp jr ra # Return

COMP 411: Computer Organization Ex4: leaf proc that saves regs proc1: – is leaf – needs to save/restore s2- s3 – creates more of a stack frame proc1: addi sp, sp, -8 sw ra, 4( sp) # Save ra sw fp, 0( sp) # Save fp addi fp, sp, 4 # Set fp addi sp, sp, -8 # room for s2 s3 sw s2, 4( sp) sw s3, 0( sp) fp ra fp s2 sp s3 . # Save s2 # Save s3 # do the task lw s2, -8( fp) lw s3, -12( fp) # restore s2 # restore s3 addi sp, fp, 4 lw ra, 0( fp) lw fp, -4( fp) jr ra # Return # Restore sp # Restore ra # Restore fp

COMP 411: Computer Organization Ex4: more general non-leaf proc proc1: – calls proc2 – needs to save/restore s2- s3 – creates more of a stack frame proc1: addi sp, sp, -8 sw ra, 4( sp) # Save ra sw fp, 0( sp) # Save fp addi fp, sp, 4 # Set fp addi sp, sp, -8 # room for s2- s3 sw s2, 4( sp) # Save s2 sw s3, 0( sp) # Save s3 fp ra fp s2 sp s3 . jal proc2 # call another . lw s2, -8( fp) # restore s2 lw s3, -12( fp) # restore s3 addi sp, fp, 4 # Restore sp lw ra, 0( fp) # Restore ra lw fp, -4( fp) # Restore fp jr ra # Return

COMP 411: Computer Organization Ex5: proc that needs to protect temporaries proc1: – calls proc2 – needs to protect t0- t1 from proc2 fp ra fp s2 s3 t0 sp t1 proc1: addi sp, sp, -8 sw ra, 4( sp) # Save ra sw fp, 0( sp) # Save fp addi fp, sp, 4 # Set fp addi sp, sp, -8 # room for s2- s3 sw s2, 4( sp) # Save s2 sw s3, 0( sp) # Save s3 addi sp, sp, -8 # room for t0- t1 . sw t0, -16( fp) # Save t0 sw t1, -20( fp) # Save t1 jal proc2 # call another lw t0, -16( fp) # Restore t0 lw t1, -20( fp) # Restore t1 . lw s2, -8( fp) # restore s2 lw s3, -12( fp) # restore s3 addi sp, fp, 4 # Restore sp lw ra, 0( fp) # Restore ra lw fp, -4( fp) # Restore fp jr ra # Return

COMP 411: Computer Organization Ex5: proc that needs to protect temporaries proc1: proc1: – calls proc2 – has a local var i fp ra fp s2 s3 t0 t1 sp local var “i” addi sp, sp, -8 sw ra, 4( sp) # Save ra sw fp, 0( sp) # Save fp addi fp, sp, 4 # Set fp addi sp, sp, -8 # room for s2- s3 sw s2, 4( sp) # Save s2 sw s3, 0( sp) # Save s3 addi sp, sp, -4 # local var i sw 0, 0( sp) # Set i 0, e.g. addi sp, sp, -8 # room for t0- t1 . sw t0, -16( fp) # Save t0 sw t1, -20( fp) # Save t1 jal proc2 # call another lw t0, -16( fp) # Restore t0 lw t1, -20( fp) # Restore t1 . lw s2, -8( fp) # restore s2 lw s3, -12( fp) # restore s3 addi sp, fp, 4 # Restore sp lw ra, 0( fp) # Restore ra lw fp, -4( fp) # Restore fp

COMP 411: Computer Organization Ex6: call proc2 with more than 4 args proc1: proc1: – calls proc2 – with more than 4 args proc1’s stack frame fp ra fp s2 . addi sp, sp, -4 # space for arg[4] . ori a0, 0, 40 # Put 40 in . sw a0, 0( sp) # . arg[4] t0 ori ori ori ori t1 jal proc2 s3 local var “i” sp addi sp, sp, -8 sw ra, 4( sp) # Save ra sw fp, 0( sp) # Save fp addi fp, sp, 4 # Set fp arg[4] a0, a1, a2, a3, 0, 0 0, 10 0, 20 0, 30 # # # # Put 0 in a0 Put 10 in a1 Put 20 in a2 Put 30 in a3 addi sp, fp, 4 # Restore sp lw ra, 0( fp) # Restore ra lw fp, -4( fp) # Restore fp jr ra # Return