Subroutines and Run-Time Storage Administration (Nov. 27 - Dec. 6, 2012) Reading: chapter 8 A5 due W. Nov. 28 Next (and last) assignment will be on C++ templates. -------- 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 modern RISC compiler - no special instructions other than jsr - 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 older CISC compiler - special subroutine-calling instructions to save and update the frame pointer, save registers, branch, and allocate space for the frame all in one or two instructions. - special push and pop operations to 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 done this way on x86, however -- x86-64 esp., makes more use of (now more numerous) registers. ---------------------------------- Case studies PLP 1e has GNU C for 32-bit MIPS and MetroWerks Pascal for MC68K PLP 2e and 3e (CD) have SGI C for 64-bit MIPS and GNU Pascal for 32-bit x86 252 textbook has GNU C for x86 (basically Pascal minus support for static link and closures) ---------------------------------- GPC on x86-32 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) (MMX shares the FP registers -- no state of its own) 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 (x86-64 is quite a bit more complicated; not covered here. Among other things, it has 16 general-purpose registers, rather than 8, and its linkage conventions pass many arguments in registers.) | -- 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. It's never been entirely clear to me why compilers sometimes generate it and sometimes don't -- perhaps details of timing on particular processor implementations. 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. --------------------- 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. The Itanium (x64) also has register windows, of variable size. ---------------------------------- 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 absence 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. Call by reference is 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? In a language with a reference model of variables (Lisp, Clu, etc.), the obvious approach is to make the formal parameter refer to the same thing as the actual parameter. I like the name "call by sharing" because it isn't clear whether to think of it as value (formal param is a copy of the actual) or reference (formal param is a reference, and can change from caller's perspective). Note that with call by sharing you can change the value of the referred-to thing (assuming it isn't immutable), but you can't change which thing is referred to. 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 -- variable-size array parameters in a language that otherwise doesn't support variable-size arrays default (optional) parameters -- don't avoid cost named parameters -- great for long param. lists variable number of parameters -- typesafe? -------------------------- Function returns Pascal and Fortran return values from functions by assigning to the function identifier. Consider this: function F; { Pascal } ... 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. 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). ML and Common Lisp allow handlers on arbitrary _experssions_. 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) ---------------------------------------- Interesting question: would it make sense to have the handler replace the _entire_ protected block, rather than the suffix? A group at MSR proposed this a few years back, and called it "try-all" (I don't like the name). It would require a roll-back mechanism, at least in general. That has a natural connection to transactional memory... ------------------------------ 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 ======================================== Events We've seen these in Java in the current assignment. class PauseListener implements ActionListener { public void actionPerformed(ActionEvent e) { // do whatever needs doing } } ... JButton pauseButton = new JButton("pause"); pauseButton.addActionListener(new PauseListener()); Or, with anonymous inner classes: pauseButton.addActionListener(new ActionListener() { public void actionPerformed(ActionEvent e) { // do whatever needs doing } }); This is a little ugly because Java insists on making everything a class. In C# you have OBJECT CLOSURES, which the language calls _delegates_. void Paused(object sender, EventArgs a) { // do whatever needs doing when the pause button is pushed } ... Button pauseButton = new Button("pause"); pauseButton.Clicked += new EventHandler(Paused); /Paused/ matches the pattern established by a delegate declaration in the library. Can be a static method or a method of a particular object -- even a nested object. In the latter case C# (like C++) allows access to static members of the surrounding class only. Java allows access to nonstatic members, but doesn't have delegate sugar. or pauseButton.Clicked += delegate(object sender, EventArgs a) { // do whatever needs doing } Note the connection to Runnables in Java, and to subroutine closures in languages with nested subroutines. ---------------------------------------- Sequential handlers In Swing, as in many GUI packages, events are handled by separate threads, managed by the runtime. If they access data for which consistency is an issue, you have to use explicit synchronization. In other languages, can be sequential: trampoline main program | '-----------------------------------------> kernel | event signal <-------------' handler trampoline rti | <----------' | '--------->, | ,<------------------------' |