## Stipulate that all variables are allocated storage (whether in globals or on the run-time stack) in alphabetical order ## ## When drawing Activation Records, be complete and include space for the return address, the appropriate "old display level ptr, and storage for all local variables ## -------------------------------------------- Practice Midterm 2 CS 524 - Spring 2008 Exam 30 April 2008 Run time stack grows down from "high memory" and is referenced using the value of the SPIM stack pointer register, sp (*RTS*) ---------- $sp-> | | | \|/ run-time stack grows from high-memory | | | globals| $s0-> |--------| | static | | data | |(strings| |--------| | | | code | ---------- 1. Consider the following fragment of source code: package main is body ma,mb: integer; i,j: boolean; procedure a is aa,ab: integer; i,j: boolean; procedure b is ba: integer; <------------- (**) procedure c is ca,cb: integer; begin -- c ... end; -- c i,j: boolean; begin -- b ... <-------------------(***) end; -- b begin -- a ... end; -- a begin -- main; ... end; -- main; Given: The activation record for a procedure contains the following information offset 0: return address of the caller offset 4: old display value offset 8: space (4 bytes per variable) for local vars Display will use $s1 for level 1 display $s2 for level 2 display $s3 for level 3 display $sp for top of stack $s0 for global variables a) draw the activation record for procedure c b) Give the register offset you would construct in translating code referring to the following variables: ca ______________ ba ______________ ma ______________ i (visible to procedure c) ______________ i (visible to procedure b) ______________ i (visible to procedure a) ______________ i (visible to main) ______________ c) Fill in the following diagram for representing the information of the display for the sequence, as we used in lecture main calls a a calls a a calls b b calls b b calls c no returns have occurred yet calls | ----------------------------------------------- d[3] | ----------------------------------------------- d[2] | ----------------------------------------------- d[1] | ----------------------------------------------- save | d) draw the run-time-stack using (*RTS*) which occurs after the following sequence of procedure calls (using displays and the registers indicated above) main call a a calls b b calls b b calls a e) can procedure a call procedure c? can procedure c reference the local variables of procedure a? can procedure b call procedure c? can procedure b reference the local variables of procedure c? can procedure c reference the local variables of procedure b? Justify your answers. 2. Repeat question 1a, 1b, 1d using Static and Dynamic Links to maintain the Run-Time storage. Question 2 Given: Activation Record using Static/Dynamic Links is represented ^ | offset 12:| local vars - as needed ------------------ offset 8: | dynamic link | ------------------ offset 4: | static link | ------------------ offset 0: | return address | ------------------ 2b: Give the address computation for NOTE: since we are using static/dynamic links and the FP (frame pointer) to access the currently active Activation Record, we need to construct addresses using FP and follow the static chain the appropriate number of links. ca ba ma i (visible to proc c) i (visible to proc b) i (visible to proc a) i (visible to main) 2c: main calls a a calls a a calls b b calls b b calls c 3. Using the same program fragment above, draw the configuration of the compile-time structure of the symbol table information using a scope stack and binary search trees when we are at location (**), and at (***). (Two pictures please) 4. Repeat question 3) using a single hash table, with chaining to resolve collisions, to control the symbol table definitions. For question 4 assume the following simple hash function: ma, aa, i hash to 1 mb, a, c hash to 2 j, ab, b hash to 3 ba, ca, cb hash to 4 5. Using the following program fragment: package main is i,j: boolean; procedure p is a,b: integer; procedure r is c,d: boolean; begin body of r end; -- r begin body of p end; -- p procedure q is a,b: boolean; begin body of q end; -- q begin -- main q; end; -- main a) Show the run-time-stack (using *RTS*) after the following sequence of calls: main calls q q call p p calls r r calls p b) Consider the following calling sequence main calls p p calls r Give the register offset value for the following variables at that time: c _____________________________________________ a _____________________________________________ i _____________________________________________ ===================================================================== Use the following construction outline for drawing your run-time stack for Question #1: ----------- SP-> | | (top of | | runtime | | stack) | | | | -------- | | | d[3] | (s3) | | -------- | | | d[2] | (s2) | | -------- | | | d[1] | (s1) | | -------- | | | | Display | | | | | | | | | | ----------- | | s0->| globals | ----------- | | | spim | | code for| | main & | | procs | ----------- =============================================================================== Use the following diagram for your Activation Record with Static/Dynamic Links in Question #2 | ^ | | | | | Local Vars | -------------------- | Dynamic Link | -------------------- | Static Link | -------------------- | Return Address | -------------------- ============================================================================== Use the following construction outline for drawing your scope stack during the translation phase for Question #3 ----------- | | ----------- | | ----------- | | ----------- | | ----------- TOS-> | ---------------Root -- | globals | \ ----------- Scope Stack whatever is appropriate ============================================================================== Use the following construction outline for drawing your global hash table with Chaining to resolve collision - given the hash function above, all names hash to one of four locations for Question #4 ------- | 4 | --> ------- | 3 | --> ------- | 2 | --> ------- | 1 | --> ------- ------- where each name is represent by |id|l#| l# = level number -------