Subroutines and Run-Time Storage Administration (November 13-15, 2007) Reading: chapter 8 A5 due day before Thanksgiving. Next (and last) assignment will be concurrency. -------- Recall allocation strategies: Static code globals "own" variables explicit constants (including strings, sets, other aggregates) small scalars may be stored in the instructions themselves stack parameters local variables temporaries bookkeeping information Heap dynamic allocation Maintaining the Run-Time stack Contents of a stack frame bookkeeping: return PC (dynamic link), saved registers, static link or saved display entries, (rarely) alignment or interrupt mask information arguments and return value(s) local variables temporaries Maintenance of stack is responsibility of "calling sequence" and subroutine "prolog" and "epilog". space is saved by putting as much in the prolog and epilog as possible time *may* be saved by putting stuff in the caller instead, where more information may be known. E.g. there may be fewer registers IN USE at the point of call than are used SOMEWHERE in the callee. common strategy is to divide registers into "caller-saves" and "callee-saves" sets. Caller uses the "callee-saves" registers first; "caller-saves" registers if necessary. Local variables, parameters, and temporaries are assigned fixed OFFSETS from the frame pointer or stack pointer at compile time Variable-length locals and parameters are handled with descriptors (dope vectors). The descriptors are at known offsets. For locals, they are accompanied by a pointer to space higher up in the frame. For value arguments, the pointer points down in the frame. --------------------- Stack layout varies significantly from machine to machine. typical CISC compiler - special subroutine-calling instructions that do things like save and update the frame pointers, save registers, branch, and allocate space for the frame all in one or two instructions. - special push and pop operations that load/store and update sp in one instruction - (usually) all arguments passed on the stack - (usually) real frame pointer - (usually) sp moves up and down as arguments are pushed and popped. Convenient for function calls embedded in argument lists. No longer standard on x86 typical RISC compiler - no special instructions - most arguments passed through registers (but space reserved on stack) - often skip frame pointer - relatively stable sp (arg build area) - simple leaf routines make no use of memory at all ---------------------------------- Case studies PLP 1e has GNU C for 32-bit MIPS and MetroWerks Pascal for MC68K PLP 2e has SGI C for 64-bit MIPS and GNU Pascal for x86 252 textbook has GNU C for x86 (basically Pascal minus support for static link and closures) ---------------------------------- GPC on x86 many of you saw most of this (all but static link) in 252 register usage 8 32-bit integer registers, 8 80-bit FP registers, 8 128-bit SSE streaming registers (on recent models) esp stack pointer ebp frame pointer ebx, esi, edi callee-saves temporaries eax, ecx, edx caller-saves temporaries eax used to return function value ecx used to pass static link (in languages that use one) eax and edx written by division operation several other similar special cases -- very non-orthogonal architecture | -- 32 bits -- | ----------------- SP -> | space | constant-sized space; must hold largest | to build | list passed to any callee | arg lists | ----------------- | | | TEMPORARIES | ^ | AND | DOWN | | LOCALS | ^ | | ----------------- | static link | ----------------- (SL) -> | other saved | | regs | ----------------- FP -> | saved FP | ----------------- | return addr | ----------------- | 1 | | ARGUMENTS | | n | ----------------- Note: SP points to last used location. On some machines/OSes, it points to first *unused* location. This inconsistency is a major pain in the butt -- right up there with endianness. BEWARE! Caller 1) saves caller-saves registers into temporary locations in current frame, if necessary 2) puts args into the build area at the top of the current frame 3) puts static link in ecx (skipped for C, or for level-0 callees) 4) executes call In prologue, Callee 1) pushes fp (decrementing sp by 4) 2) copies sp into fp, creating new fp 3) pushes callee-saves regs, if necessary 4) subtracts rest of frame size from sp In epilogue, Callee 1) sets return value, if any 2) restores callee-saved regs, if any 3) copies fp into sp, deallocating frame 4) pops fp off stack 5) returns steps 3) and 4) can be combined into a one-byte 'leave' instruction After call, Caller 1) moves return value from register to wherever it's needed (if appropriate) 2) restores caller-saves registers lazily over time, as their values are needed Closures (for languages that have them) leverage the ability of the x86 to execute code that resides in the stack. (Most machines forbid that, to avoid L1I/L1D cache consistency problems.) This allows the closure to be a single address -- address of two-instruction sequence in stack that loads ecx with SL and branches. ---------------------------------- | GCC on 32-bit MIPS | | register usage | | 32 integer registers, 16 floating-point registers | two integer registers are special in the hardware: | $0 0 | $31 return address for jal (jump-and-link) | several others are special by convention: | $1 assembler temp (at) | $2 static chain (during procedure prologue -- not in C), | 1st half of scalar function return (v0) | $3 2nd half of scalar function return (v1) | $28 global pointer (gp) | $29 stack pointer (sp) | $30 frame pointer (fp) (if needed) | other registers fall into (statically-defined) classes (by convention): | caller-saves temporaries (t0-t9 = $8-$15,$24,$25) | callee-saves temporaries (s0-s7 = $16-$23) | arguments (a0-a3 = $4-$7) | reserved; kernel may trash at any time (k0-k1 = $26-$27) | | | -- 32 bits -- | | | ----------------- | SP,FP -> | space | constant-sized space; must hold largest | | to build | list passed to any callee | | arg lists | | ----------------- | | | | | TEMPORARIES | ^ | | AND | DOWN | | | LOCALS | ^ | | | | ----------------- | | saved | (including $31, if necessary) | | registers | | ----------------- | | 1 | | | ARGUMENTS | | | n | | ----------------- | | Caller | 1) saves into the temporaries and locals area any caller-saves | registers whose values will be needed after the call | 2) puts up to 4 small arguments into registers $4-$7 (a0-a3). | Exactly which args is complicated; it depends on the types | of the parameters and the order in which they appear in the | argument list. | 3) puts the rest of the arguments into the arg build area at the | top of the stack frame. | 4) does jal, which puts return address into register ra and branches | (note that jal, like all branches, has a delay slot) | In prolog, Callee | 1) subtracts framesize from sp | 2) saves callee-saves registers used anywhere inside callee | (one instruction per). This includes ra if this routine is | not a leaf. | 3) copies sp to fp | In epilog, Callee | 1) puts return value into registers (or memory if large) | 2) copies fp into sp (see below for rationale) | 3) restores saved registers, including ra, using sp as base | 4) adds to sp to deallocate frame | 5) does j ra | After call, Caller | 1) moves return value from register to wherever it's needed (if | appropriate) | 2) restores caller-saves registers lazily over time, as their values | are needed | | All arguments have space in the stack, whether passed in registers or not. | The subroutine just begins with some of the arguments already cached in | registers, and 'stale' values in memory. This is a normal state of | affairs; optimizing compilers keep things in registers whenever possible, | flushing to memory only when they run out of registers, or when code may | attempt to access the data through a pointer or from an inner scope. | | Scalar function returns use registers $2 (v0) or $f0, depending on type. | For struct returns, the caller passes an extra (hidden) first | argument that is the address of the location in which it wants | the return value stored. This could be in the build area (if to | be passed to another function) or in the locals or even globals | (for assignment) or among the temporaries (for immediate use). | | Everything could be accessed off the sp, so long as it stays put. | Problem arises with C's alloca mechanism, which can move sp. In this | case fp stays put. Arg build area is always accessed relative to sp; | rest of frame is accessed relative to fp. (This is why the epilog | copies the fp into the sp.) | | Many parts of the calling sequence, prologue, and/or epilogue can | be omitted in common cases, particularly LEAF routines (those that | don't call other routines). Leaving things out saves time. Simple | leaf routines don't use the stack -- don't even use memory -- and | are exceptionally fast. | | Debugging is facilitated by a number of assembler pseudo-ops that put | information into the object file symbol table. This info includes | starting and ending addresses of the routine | frame size | which reg. is base for locals (usually fp) | which reg. contains return address | which regs. were saved | --------------------- Register windows The Berkeley RISC, and its offspring, the SPARC, use register windows in an attempt to reduce the amount of register saving and restoring, and the number of register-register moves. Unfortunately, these also dramatically complicate context switching (both for kernel and for thread packages), and introduce the problem of window overflow/underflow, partially or entirely negating their performance advantage. ---------------------------------- Access to non-local variables STATIC LINKS Each frame points to the frame of the (correct instance of) the routine inside which it was declared. In the absense of formal subroutines, "correct" means closest to the top of the stack. you access a variable in a scope k levels out by following k static links and then using the known offset within the frame thus found. you set up static links as follows: case 1: callee is nested (directly) inside you callee's static link is pointer to your frame case 2: callee is k scopes out (k may be 0) callee's static link is found by indirecting off your own static link k times procedures as parameters: when you form the closure, you figure out a static link just as if you were going to call the routine directly; the closure consists of the routine's address and the static link -------------------------- Parameter passing mechanisms three basic implementations: value, value/result (copying) reference (aliasing) closure Closures used not only for formal subroutines, but also *name* parameters and label parameters (Algol 60, 68) many languages (e.g. Pascal) provide val and ref directly problem: pass big thing by val or ref? solution? (Modula-2): 'const' mode that is read-only but passed by reference but then val and const for small things are ~semantically redundant Ada goes for semantics: who can do what in formal initialized; actual not modified out formal not initialized; actual modified in out formal initialized; actual modified Ada in/out is always implemented as value/result for scalars, and either value/result or reference for structured objects. The language manual says your program is "erroneous" if it can tell the difference. In a language with a reference model of variables (Lisp, Clu, etc.), pass by reference ("sharing") is the obvious approach. It's also the only option in Fortran. If you pass a constant, the compiler creates a temporary location to hold it. If you modify the temporary, who cares? Call-by-name is an old Algol technique. Think of it as call by textual substitution (procedure with all name parameters works like macro). What you pass are hidden procedures called THUNKS. Jensen's device example: function sum (expr, index : name real; low, high : const integer) returns answer : real; begin answer := 0; for i in low..high loop index := i; answer +:= expr; end loop; end sum; S := sum (A[2*i-1], i, 1, 10); Amazing truth: it doesn't seem to be possible to write a general-purpose swap routine with name parameters. Call-by-name is a naive implementation of normal-order evaluation. Call-by-need does memoization. It's used in Haskell, which is purely functional, and in R, which is not. Both call-by-name and call-by-need are considered "lazy evaluation" by the FP community (some inconsistency of nomenclature here -- compiler people sometimes use "lazy" only for call-by-need). In a pure functional language the two are semantically indistinguishable. With side effects they aren't. Note that passing dynamic arrays by value is tricky. The actual parameter list on the stack contains a fixed-size dope vector and a pointer, but where does the data go? One option is below the arguments. Another is to let the callee copy the data into the new stack frame immediately after the prologue. Other parameter issues conformant arrays default (optional) parameters -- don't avoid cost named parameters -- great for long param. lists variable number of parameters -- typesafe? -------------------------- Function returns Pascal returns values from functions by assigning to the function identifier. Consider this: function F; ... function F; ... end {F}; ... begin {outer F} ... F := 10; {illegal!} User cannot re-use the name of a function inside. Later languages fix this by having an explicit 'return' statement (as in C or Ada), or a named return value. Another advantage of the fix is that you can use the name you eventually want to return inside expressions: -- Ada function max (A : array of integer) return integer is declare rtn : integer := integer'min; begin for i in A'low .. A'high loop if A(i) > rtn then rtn := A(i); end if; end loop return rtn; end max -------------------------- Exception Handling What is an exception? - an unusual condition detected at run time - Examples: - arithmetic overflow - end-of-file on input - wrong type for input data - user-defined conditions (not necessarily errors) - error v. nonlocal return -- different mechanisms? (Common Lisp) What is an exception handler? - code executed when exception occurs - may need a different handler for each type of exception Why design in exception handling facilities? - allow user to explicitly handle errors in a uniform manner - allow user to handle errors without having to check these conditions explicitly in the program everywhere they might occur Consider handling of errors in a recursive-descent compiler. It's a real pain in languages without exceptions: need extra parameters and checks in every procedure. Much nicer to be able to back out to exactly where you want to. Approaches Built-in Dynamically scoped Statically scoped User-Defined MacScheme, Common Lisp C setjmp/longjmp Pioneers: PL/I dynamically scoped CLU statically scoped, procedure/abstraction oriented (can't handle locally) Convergence in modern languages on built-in, statically scoped, "replacement" model: Ada, C++/Java/C#, Modula-3, ML, Common Lisp, python/php/ruby (poorer substitutes in perl, tcl) Discussion here is for C++/Java. Handlers local to code in which exception is raised try { ... // throw obj; ... } catch (end_of_file) { ... } catch (io_error e) { ... } catch (...) { ... // catch-all } Handlers must be at the end of a block of code (but can put blocks around any statement) Notion of *matching* an exception. Arguments as members of object. (Ada has no arguments; Modula-3 and ML make them look like parameters.) Static (nested) binding within subroutine, then propagate up dynamic chain. All functions that the exception propagated out of are terminated. C++ executes destructors as appropriate on the way out. Execution continues after handler code (which is always at the end of a block) ------------------------------ Implementation of statically-scoped exceptions (1) Push handler address when entering a protected block, pop when leave. Often implemented this way in C++, probably to minimize size and complexity of the run-time library. (2) Do everything via lookup in tables produced by the compiler. This is the "right" way to do it. (3) Can sort of fake it in C with setjmp() and longjmp(). These take state snapshot and restore on throw. Doesn't work right for non-volatile local variables. Very expensive. -------------------------- Implementation of (true) iterators. (1) threads -- easy but overkill (2) static conversion to iterator objects code becomes an automaton. (3) single-stack, with iterator frame on top of for loop frame