Lecture #16: Introduction to Runtime OrganizationStatusRun-time environmentsCode Generation Goals and ConsiderationsSubgoals and ConstraintsActivations and Lifetimes (Extents)Memory LayoutActivation RecordsCalling ConventionsStatic StorageHeap StorageAchieving Runtime Effects---Functions1: No recursion, no nesting, fixed-sized data1: Calling conventions2: Add recursion2: Calling Sequence when Frame Size is Fixed2: Calling sequence from ia323: Add Variable-Sized Unboxed DataOther Uses of the Dynamic Link3: Calling sequence for the ia324: Allow Nesting of Functions, Up-Level AddressingStatic LinksThe Global Display5: Allow Function Values, Properly Nested AccessFunction Value Representation6: General ClosuresRepresenting Closures7: ContinuationsSummaryLecture #16: Introduction to Runtime OrganizationAdministrivia• Homework for next Friday will be posted tomorrow.Last modified: Wed Apr 15 19:41:01 2009 CS164: Lecture #16 1Status• Lexical analysis– Produces tokens– Detects & eliminates illegal tokens• Parsing– Produces trees– Detects & eliminates ill-formed parse trees• Static semantic analysis– Producesdecorated treewith additional information attached– Detects & eliminates remaining static errors• Next are the dynamic “back-end” phases: ⇐=we are here– Code generation (at various semantic levels)– OptimizationLast modified: Wed Apr 15 19:41:01 2009 CS164: Lecture #16 2Run-time environmentsBefore discussing code generation, we need to understand what we aretrying to generate.• We’ll use the termvirtual machineto refer to the compiler’s target.• Can be just a bare hardware architecture (small embedded systems).• Can be an interpreter, as for Java, or an interpreter that does ad-ditional compilation at execution, as in modern Java JITs• For now, we’ll stick to hardware + conventions for using it (theAPI:application programmer’s interface) + someruntime-support library.Last modified: Wed Apr 15 19:41:01 2009 CS164: Lecture #16 3Code Generation Goals and Considerations•Correctness:execution of generated code must be consistent withthe programs’ specified dynamic semantics.• In general, however, these semantics do not completely specify be-havior, often to allow compiler to accomplish other goals, such as. . .•Speed:produce code that executes as quickly as possible, or reliablymeets certain timing constraints (as in real-time systems).•Size:minimize size of generated program or of runtime data struc-tures.• Speed and size optimization can be conflicting goals. Why?•Compilation speed:especially during development or when using JITs.• Most complications in code generation come from trying to be fastas well as correct, because this requires attention to special cases.Last modified: Wed Apr 15 19:41:01 2009 CS164: Lecture #16 4Subgoals and Constraints• Subgoals for improving speed and size:– Minimize instruction counts.– Keep data structure static, known at compilation (e.g., known con-stant offsets to fields). Contrast Java and Python.– Maximize use of registers (“top of the memory hierarchy”).• Subgoals for improving compilation speed:– Try to keep analyses aslocalas possible (single statement, block,procedure), because their compilation-time cost tends to be non-linear.– Simplify assumptions about control flow: procedure calls “always”return, statements generally execute in sequence. (Where arethese violated?)Last modified: Wed Apr 15 19:41:01 2009 CS164: Lecture #16 5Activations and Lifetimes (Extents)• An invocation of procedure P is anactivationof P .• Thelifetime of an activationof P is all the steps to execute P ,including all the steps in procedures P calls.• Thelifetime (extent) of a variableis the portion of execution dur-ing which that variable exists (whether or not the code currentlyexecuting can reference it).• Lifetime is a dynamic (run-time) concept, as opposed to scope, whichis static.• Lifetimes of procedure activations and local variables properly nest(in a single thread), suggesting astackdata structure for maintain-ing their runtime state.• Other variables have extents that are not coordinated with proce-dure calls and returns.Last modified: Wed Apr 15 19:41:01 2009 CS164: Lecture #16 6Memory LayoutCharacteristics of procedure activations and variables give rise to thefollowing typical data layout for a (single-threaded) program:Instructions(“text segment(s)”)Static data(“data segment(s)”)Dynamic data(“heap”)Execution stack(“stack segment”)Lowest memory addressHighest memory addressLast modified: Wed Apr 15 19:41:01 2009 CS164: Lecture #16 7Activation Records• The information needed to manage one procedure activation is calledanactivation record (AR)or(stack) frame.• If procedure F (thecaller) calls G (thecallee,typically G’s activa-tion record contains a mix of data about F and G:–Return addressto instructions in F .–Dynamic linkto the AR for F .– Space to save registers needed by F .– Space for G’s local variables.– Information needed to find non-local variables needed by G.– Temporary space for intermediate results, arguments to and re-turn values from functions that G calls.– Assorted machine status needed to restore F ’s context (signalmasks, floating-point unit parameters).• Depending on architecture and compiler, registers typically hold partof AR (at times), especially parameters, return values, locals, andpointers to the current stack top and frame.Last modified: Wed Apr 15 19:41:01 2009 CS164: Lecture #16 8Calling Conventions• Many variations are possible:– Can rearrange order of frame elements.– Can divide caller/callee responsibilities differently.– Don’t need to use an array-like implementation of the stack: canuse a linked list of ARs.• An organization is better if it improves execution speed or simplifiescode generation• The compiler must determine, at compile-time, the layout of activa-tion records and generate code that correctly accesses locations inthe activation record.• Furthermore, it is common to compile procedures separately andwithout access of each other’s details, which motivates the the im-position ofcalling conventions.Last modified: Wed Apr 15 19:41:01 2009 CS164: Lecture #16 9Static Storage• Here, “static storage” refers to variables whose extent is an entireexecution and whose size is typically fixed before execution.• Not generally stored in an activation record, but
View Full Document
Unlocking...