Chapter 17Chapter 17Recursion2Wright State University, College of EngineeringDr. Doom, Computer Science & EngineeringCEG 320/520Comp. Org. & AssemblyImplementing a Function Call: OverviewImplementing a Function Call: OverviewCalling functionallocate memory for activation record (push)copy arguments into stackargumentscall functionget result from stack (pop)deallocate memory for activation record (pop)Called functionallocate space for return value[bookkeeping] (push)store mandatory callee save registers [bookkeeping] (push)set frame pointerallocate local variables (push)execute codeput result in return value spacedeallocatelocal variables (pop) load callee save registers (pop)return3Wright State University, College of EngineeringDr. Doom, Computer Science & EngineeringCEG 320/520Comp. Org. & AssemblyActivation RecordActivation Record int funName(int a, int b){int w, x, y;...return y;}Name Type Offset Scopeabwxyintintintintint450-1-2funNamefunNamefunNamefunNamefunNameyxwdynamic linkreturn addressreturn valueabbookkeepinglocalsargsR5R64Wright State University, College of EngineeringDr. Doom, Computer Science & EngineeringCEG 320/520Comp. Org. & AssemblySummary of LCSummary of LC--3 Function Call 3 Function Call ImplementationImplementation1. Caller pushes arguments (last to first).2. Caller invokes subroutine (JSR).3. Callee allocates return value, pushes R7 and R5.4. Callee allocates space for local variables (first to last).5. Callee executes function code.6. Callee stores result into return value slot.7. Callee pops local vars, pops R5, pops R7.8. Callee returns (RET/JMP R7).9. Caller loads return value and pops arguments.10. Caller resumes computation…5Wright State University, College of EngineeringDr. Doom, Computer Science & EngineeringCEG 320/520Comp. Org. & AssemblyWhat is Recursion?What is Recursion? A recursive function is one that solves its task by calling itself on smaller pieces of data.– Similar to recurrence function in mathematics.– Like iteration -- can be used interchangeably;sometimes recursion results in a simpler solution. Standard example: Fibonacci numbers– The n-th Fibonacci number is the sum of the previous two Fibonacci numbers.– F(n) = F(n – 1) + F(n – 2) where F(1) = F(0) = 1int Fibonacci(int n){if ((n == 0) || (n == 1))return 1;else return Fibonacci(n-1) + Fibonacci(n-2);}6Wright State University, College of EngineeringDr. Doom, Computer Science & EngineeringCEG 320/520Comp. Org. & AssemblyActivation RecordsActivation Records Whenever Fibonacci is invoked, a new activation record is pushed onto the stack.Fib(1)R6Fib(2)Fib(3)mainmain calls Fibonacci(3)Fibonacci(3) calls Fibonacci(2)Fibonacci(2) calls Fibonacci(1)R6Fib(3)mainR6Fib(2)Fib(3)main7Wright State University, College of EngineeringDr. Doom, Computer Science & EngineeringCEG 320/520Comp. Org. & AssemblyActivation Records (cont.)Activation Records (cont.)Fibonacci(1) returns,Fibonacci(2) calls Fibonacci(0)Fibonacci(2) returns,Fibonacci(3) calls Fibonacci(1)Fibonacci(3)returnsR6mainR6Fib(1)Fib(3)mainFib(0)R6Fib(2)Fib(3)main8Wright State University, College of EngineeringDr. Doom, Computer Science & EngineeringCEG 320/520Comp. Org. & AssemblyTracing the Function CallsTracing the Function Calls If we are debugging this program, we might want to trace all the calls of Fibonacci.– Note: A trace will also contain the argumentspassed into the function. For Fibonacci(3), a trace looks like: Fibonacci(3)Fibonacci(2)Fibonacci(1)Fibonacci(0)Fibonacci(1) What would trace of Fibonacci(4) look like?9Wright State University, College of EngineeringDr. Doom, Computer Science & EngineeringCEG 320/520Comp. Org. & AssemblyFibonacci: LCFibonacci: LC--3 Code3 Code Activation Recordtempdynamic linkreturn addressreturn valuenbookkeepingargCompiler generatesanonymous variable to holdresult of first Fibonacci call.local10Wright State University, College of EngineeringDr. Doom, Computer Science & EngineeringCEG 320/520Comp. Org. & AssemblyIn Summary: The StackIn Summary: The Stack Since our program usually starts at a low memory address and grows upward, we start the stack at a high memory address and work downward. Purposes– Temporary storage of variables– Temporary storage of program addresses– Communication with subroutines Push variables on stack Jump to subroutine Clean stack Return11Wright State University, College of EngineeringDr. Doom, Computer Science & EngineeringCEG 320/520Comp. Org. & AssemblyParameter passing on the stackParameter passing on the stack If we use registers to pass our parameters:– Limit of 8 parameters to/from any subroutine.– We use up registers so they are not available to our program. So, instead we push the parameters onto the stack.– Parameters are passed on the stack– Return values can be provided in registers (such as R0) or on the stack.– Generally, only R6 should be changed by a subroutine.  Other registers that are changed should must be callee saved/restored. Subroutines should be transparent Both the subroutine and the main program must know how many parameters are being passed!– In C we would use a prototype: int power (int number, int exponent); In assembly, you must take care of this yourself. After you return from a subroutine, you must also clear the stack.– Clean up your mess!12Wright State University, College of EngineeringDr. Doom, Computer Science & EngineeringCEG 320/520Comp. Org. & AssemblyCharacteristics of good subroutinesCharacteristics of good subroutines Readability – well documented. Generality – can be easily reused elsewhere– Passing arguments on the stack does this. Transparency – you have to leave the registers like you found them, except R6.– Registers must be callee saved. Re-entrant – subroutine can call itself if necessary– Store all information relevant to specific execution to non-fixed memory locations The stack!– This includes temporary callee storage of register values! Secure – No unexpected side effects on the stack / memory.13Wright State University, College of EngineeringDr. Doom, Computer Science & EngineeringCEG 320/520Comp. Org. & AssemblyKnow how to…Know how to… Push parameters onto the stack Access parameters on the stack using base + offset addressing mode Draw the stack to keep track of subroutine execution– Parameters– Return address Clean the stack after a subroutine call14Wright