The Procedure Abstraction Part III: Allocating Storage & Establishing AddressabilityPlacing Run-time Data Structures Classic Organization • Code, static, & global data have known size  Use symbolic labels in the code • Heap & stack both grow & shrink over time • This is a virtual address space • Better utilization if stack & heap grow toward each other • Very old result (Knuth) • Code & data separate or interleaved • Uses address space, not allocated memory C o d e S G t l a & o t b i a c l H e a p S t a c k Single Logical Address Space 0 highHow Does This Really Work? The Big Picture C o d e S G t l a & o t b i a c l H e a p S t a c k C o d e S G t l a & o t b i a c l H e a p S t a c k C o d e S G t l a & o t b i a c l H e a p S t a c k ... ... Hardware’s view Compiler’s view OS’s view Physical address space_ virtual address spaces 0 high C o d e S G t l a & o t b i a c l H e a p S t a c kWhere Do Local Variables Live? A Simplistic model • Allocate a data area for each distinct scope • One data area per “sheaf” in scoped table What about recursion? • Need a data area per invocation (or activation) of a scope • We call this the scope’s activation record • The compiler can also store control information there ! More complex scheme • One activation record (AR) per procedure instance • All the procedure’s scopes share a single AR (may share space) • Static relationship between scopes in single procedure Used this way, “static” means knowable at compile time (and, therefore, fixed).Translating Local Names How does the compiler represent a specific instance of x ? • Name is translated into a static coordinate → < level,offset > pair → “level” is lexical nesting level of the procedure → “offset” is unique within that scope • Subsequent code will use the static coordinate to generate addresses and references • “level” is a function of the table in which x is found → Stored in the entry for each x • “offset” must be assigned and stored in the symbol table → Assigned at compile time → Known at compile time → Used to generate code that executes at run-timeStorage for Blocks within a Single Procedure • Fixed length data can always be at a constant offset from the beginning of a procedure → In our example, the a declared at level 0 will always be the first data element, stored at byte 0 in the fixed-length data area → The x declared at level 1 will always be the sixth data item, stored at byte 20 in the fixed data area → The x declared at level 2 will always be the eighth data item, stored at byte 28 in the fixed data area → But what about the a declared in the second block at level 2? B0: { int a, b, c B1: { int v, b, x, w B2: { int x, y, z …. } B3: { int x, a, v … } … } … }Variable-length Data Arrays → If size is fixed at compile time, store in fixed-length data area → If size is variable, store descriptor in fixed length area, with pointer to variable length area → Variable-length data area is assigned at the end of the fixed length area for block in which it is allocated B0: { int a, b … assign value to a B1: { int v(a), b, x B2: { int x, y(8) …. } a b v b x x y(8) v(a) Variable-length data Includes variable length data for all blocks in the procedure …Activation Record Basics parameters register save area return value return address addressability caller’s ARP local variables ARP Space for parameters to the current routine Saved register contents If function, space for return value Address to resume caller Help with non-local access To restore caller’s AR on a return Space for local values & variables (including spills) One AR for each invocation of a procedureActivation Record Details How does the compiler find the variables? • They are at known offsets from the AR pointer • The static coordinate leads to a “loadAI” operation → Level specifies an ARP, offset is the constant Variable-length data • If AR can be extended, put it after local variables • Leave a pointer at a known offset from ARP • Otherwise, put variable-length data on the heap Initializing local variables • Must generate explicit code to store the values • Among the procedure’s first actionsActivation Record Details Where do activation records live? • If lifetime of AR matches lifetime of invocation, AND • If code normally executes a “return” ⇒ Keep ARs on a stack • If a procedure can outlive its caller, OR • If it can return an object that can reference its execution state ⇒ ARs must be kept in the heap • If a procedure makes no calls ⇒ AR can be allocated statically Efficiency prefers static, stack, then heap C o d e S G t l a & o t b i a c l H e a p S t a c k Yes! This stack.Communicating Between Procedures Most languages provide a parameter passing mechanism ⇒ Expression used at “call site” becomes variable in callee Two common binding mechanisms • Call-by-reference passes a pointer to actual parameter → Requires slot in the AR (for address of parameter) → Multiple names with the same address? • Call-by-value passes a copy of its value at time of call → Requires slot in the AR → Each name gets a unique location (may have same value) → Arrays are mostly passed by reference, not value • Can always use global variables … call fee(x,x,x);Establishing Addressability Must create base addresses • Global & static variables → Construct a label by mangling names (i.e., &_fee) • Local variables → Convert to static data coordinate and use ARP + offset • Local variables of other procedures → Convert to static coordinates → Find appropriate ARP → Use that ARP + offset { Must find the right AR Need links to nameable ARsEstablishing Addressability Using access links • Each AR has a pointer to AR of lexical ancestor • Lexical ancestor need not be the caller • Reference to <p,16> runs up access link chain to p • Cost of access is