The Activation Record (AR)The Frame PointerLayout of FrameBasic Tools for CallingCode Generation Strategy for CallCode Generation for Function Prologue and EpilogueIA32 Version of Function Prologue and EpilogueCode Generation for Local VariablesPassing Static Links (I)Accessing Non-Local VariablesPassing Static Links (II)The Activation Record (AR)[Notes adapted from R. Bodik; updated 5/2/ 2 0 05]• Code for function calls an d function definitions depends on the lay-out of the activation record• Very simple AR suffices for this language:– The result is always in the accumulator; no need to store theresult in the AR .– The activation re cord of the caller holds actual parameters justbelow callee ’s AR.∗ For f(x1,. . . ,xn), push xn,. . . ,x1 on the stack∗ These are the only variables in this la nguage– AR must also save return address.Last modified: Mon May 2 18:55:30 2005 CS164: Lecture #33 1The Frame Pointer• The stack discipline guarantees that on function exit $sp is the sa meas it was on function entr y.• No need to save $sp• But it’s handy to have a pointer to start of the current AR.– Lives in register $fp (frame pointe r)– Useful for giving addresses of variables and parameters fixedoffsets while manipula ti ng $sp.Last modified: Mon May 2 18:55:30 2005 CS164: Lecture #33 2Layout of Frame• For our simple langua g e, if h calls g, which calls f(x,y), then– g’s AR will contain x and y,– f’s AR will contain return address (back to g) and g’s frame pointer.RA to hh’s FPSP, FPRA to hh’s FPFPyxSPRA to hh’s FPyxRA to gg’s FPSP, FPg’sframef’sframeBefore f(x,y) &After f(x,y)Before call f &After returnDuring call⇐⇒ ⇐⇒Last modified: Mon May 2 18:55:30 2005 CS164: Lecture #33 3Basic Tools for Calling• Thecalling sequenceis th e instructions to set up a function invoca-tion and restore state on return.• Thefunction prologueis the code in the function definition thatsets up the AR.• Thefunction epilogueis the code in the function that re turns an ddeletes the activation record.• Most machines have special ins tructions for calls:– On MIPS, jalLABEL, jumps toLABELand saves address of nextinstruction after the jal in $ra.– On ia32, the return address is stored on the stack by thecallLABELinstruction• And returns:– On MIPS, jrREGjumps to addre ss inREG.– On ia32, ret pops return address from stack and goes there.Last modified: Mon May 2 18:55:30 2005 CS164: Lecture #33 4Code Generation Strategy for Callcgen (f(e1, . . . , en)):cgen (en) # Evaluate and pushpush $acc # parame te rs in reverse. . .cgen (e1)push $accjal f # Jump to f and save returnaddiu $sp, $sp, 4*n # Pop parameter s from stackLast modified: Mon May 2 18:55:30 2005 CS164: Lecture #33 5Code Generation for Function Prologue and Epiloguecgen (def f(x1, . . . , xn) = e) =push $ra # Save return addresspush $fp # Save frame pointermove $fp , $sp # Set new frame pointercgen (e)lw $ra, 8 ( $fp) # Restore return addresslw $fp, 4($fp) # Restore frame poin teraddiu $sp, $fp, 8 # Restore the stack pointe rjr $ra # And return to callerLast modified: Mon May 2 18:55:30 2005 CS164: Lecture #33 6IA32 Version of Function Prologue and EpilogueThe last slide not a typical MIPS sequence: biased to look like the ia32:cgen (def f(x1, . . . , xn) = e) =# (Call instr uction has already# pushed return address. )pushl %ebp # Save frame pointermovl %e sp,%ebp # Set new frame pointercgen (e)leave # Pop frame pointer from stack.ret # Pop return address and returnLast modified: Mon May 2 18:55:30 2005 CS164: Lecture #33 7Code Generation for Local Variables• Local variables are stored on the stack (thus not a t fixe d location ) .• One possibi l ity: access rela ti ve to the stack p oi nter.– Problem: stack pointer changes in strategy we’ve been using forcgen.• Solution: use frame poi nter, which is constant over execution offunction.• For simple language, use fact that parameter i is at locati on$fp + 4(i + 2):– cgen (xi) = lw $a0, K($fp), whe re K = 4(i + 2).• If we had local variables other than parameters, they would be atnegative offsets from $fp.Last modified: Mon May 2 18:55:30 2005 CS164: Lecture #33 8Passing Static Links (I)• When using static links, the link can be tr eated as a pa rameter.• In the Pyth runtime, for exampl e, a function value consists of a codeaddress fol l owed by a static li nk.• So, if we have a function-valued variable at, say, offset -8 fr omframe pointer, can call it withlw $t1, -8($fp) # Fetch address of codelw $t2, -4($fp) # Fetch static l i nkpush $t2 # And pass as first parame terjalr $t1 # Jump to address in $t1.Last modified: Mon May 2 18:55:30 2005 CS164: Lecture #33 9Accessing Non-Local Variables• In progr a m on l eft, how does f3 access x1?• f3 will have been pass ed a static link as its firs t parameter.• The static l i nk passed to f3 will be f2’s fra me poi nterdef f1 (x1):def f2 (x2):def f3 ( x3):... x1 . .....f3 (12)...f2 (9)lw $t, 8($fp) # Fetch FP for f2lw $t, 8($t) # Fetch FP for f1lw $a0, 1 2 ( $t) # Fetch x1• In general, for a function at nesting level n to access a varia bl e atnesting level m < n, perfor m n − m l oa ds of static links.Last modified: Mon May 2 18:55:30 2005 CS164: Lecture #33 10Passing Static Links (II)• In previous example, how do we cal l f2 from f3? f3 fr om f2? f2from f3?def f1 (x1):def f2 (x2):def f3 ( x3):... f2 ( 9) ......f3 (12)f2 (10) # (rec ursive ly)...To g et stati c link for f2(9) :lw $t 8($fp) # Fetch FP for f2lw $t 8($t) # Fetch FP for f1push $t # Push static linkTo g et stati c link for f3 (12):push $fp # f2’s FP is static linkTo g et stati c link for f2(1 0 ) :lw $t 8($fp)push $t• Could create a function value, and call as in previous s l ide.• Can do better. Function s and the i r n esting le vels are known.• If i n a function at nesting level n, calling a nother at known nestinglevel m ≤ n + 1, g et corr ect stati c link in $t with:– Set $t to $fp.– Perfor m ‘lw $t, 8( $t)’ n − m + 1 times.Last modified: Mon May 2 18:55:30 2005 CS164: Lecture #33
View Full Document
Unlocking...