** update - problem #2 - Activation Record for B must provide space for the declared vars i,j (along wiht ba) ## 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 ** Solutions ** Exam Wed 30April2008 Run time stack (RTS) grows down from "high memory" and is referenced using the value of the SPIM stack pointer register, sp (*RTS*) ## High Memory ## ---------- $sp-> | | | \|/ run-time stack grows from high-memory * | | | globals| $s0-> |--------| | static | | data | |(strings| |--------| | | | code | ---------- ## Low Memory ## 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 ### all variables allocated space in alphabetical order ### 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 ==================================================================== ------------------- | cb storage | offset 12 ------------------- | ca storage | offset 8 ------------------- | old level3 displ| offset 4 ------------------- | return address | offset 0 ------------------- ==================================================================== b) Give the register offset you would construct in translating code referring to the following variables: =================================================================== +8($s3) ca ______________ +8($s2) ba ______________ +8($s0) [+0 = i; +4 = j; +8 = ma; +12 = mb] ma ______________ ## "show your work" ## +16($s1) local to a i (visible to procedure c) ______________ +12($s2) local to b i (visible to procedure b) ______________ +16($s1) local to a i (visible to procedure a) ______________ +0($s0) global var i (visible to main) ______________ ===================================================================== c) Fill in the following diagram for representing the information of the display for the sequence (in the style of Fig. 9.9 p. 295 text) main calls a a calls a a calls b b calls b b calls c no returns have occurred yet ================================================================== calls | a a b b c ----------------------------------------------- d[3] | ? ? ? ? c ----------------------------------------------- d[2] | ? ? b b' b' ----------------------------------------------- d[1] | a a' a' a' a' ----------------------------------------------- save | a b ================================================================= d) draw the run-time-stack 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 ** Note: the purpose of problem #4 on this exam is to provide a framework for several of the answers *** ================================================================== ## when drawing activation records, give the full description, including the variables ## ## "old L1" = Old Level 1 address pointer ## retaddr = return address |--------| | j | AR(a) $s3 -->? (never set) | i | | ab | | aa | | old L1-|----------> ? (never set) |retaddr | |--------|<-----* | j | | | i | | | ba |AR(b) | | old L2-|----------> ? (never set) |retaddr | | |--------|<-* | | j | | | | i | | | | ba | | | | old L2-|--* | |retaddr |AR(b')| $s2-> |--------| | | j | | | i | | | ab | | | aa | | | old L1-|------* $sp->$s1->|retaddr |AR(a') |--------| | | | RTS growing down \|/ * ... | mb | | ma | | j | | i | $s0-> |--------| | static | | data | |(strings| |--------| | | | code | ---------- ========================================================== Using the Visibility Rules (Text Section 8.3), we have: e) can "procedure a" call "procedure c"? ** no - procedure c is hidden inside scope of procedure b can "procedure c" reference the local variables of "procedure a"? ** yes - aa,ab,i,j are visible since a's scope is open can procedure b call procedure c? ** yes - proc is defined within the scope of proc b can procedure b reference the local variables of procedure c? ** no - procedure c's scope is closed to procedure b can procedure c reference the local variables of procedure b? ** some of them - procedure b's scope is still open when translating proc c so that ba:integer is visible to proc c. but i,j: boolean; is declared after the proc c is defined and therefore will not be visible to proc c Justify your answers. ** justification included with answer above ============================================================== 2. Given: Activation Record using Static/Dynamic Links is ------------------ ^ | 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 +12($FP) ba t0:= $FP+4; (addr to AR(b'); +12($t0) follow 1 level of static link ma +8($s0) global i (visible to proc c) t1:=$FP+4; (AR(b')) [assume translating body proc c] t2:=+4($t1) (AR(a)) +20($t2) local var i in proc a (follow 2 levels of static links) i (visible to proc b) +16($FP) i (visible to proc a) +20($FP) i (visible to main) +0($s0) 2c: main calls a a calls a a calls b b calls b b calls c Missing from each of these Activation Record is the Return Address at Offset 0 to help focus on the Static and Dynamic Links ------------------ Activation Records grow from high memory offset 24:| j | ------------------ offset 20:| i | ------------------ offset 16:| ab | ------------------ offset 12:| aa | ------------------ offset 8: | dynamic link --|----------------------------- > globals(caller=main) ------------------ offset 4: | static link ---|----------------------------- > globals ================== AR(a) <-------------------- offset 24:| j | | ------------------ | offset 20:| i | | ------------------ | offset 16:| ab | | ------------------ | offset 12:| aa | | ------------------ | offset 8: | dynamic link --|-----------------------------| ------------------ offset 4: | static link ---|-------------------------------> globals ================== AR(a') [a=caller & a'=callee] <--| <-|<---| offset 20:| j | | | ------------------ | | offset 16:| i | | | ------------------ | | offset 12:| ba | | | | ------------------ | | | offset 8: | dynamic link --|-----------------------------------| | | ------------------ | | offset 4: | static link ---|---------------------------------------| | ================== AR(b) [a=caller & b=callee] <-----------| | offset 20:| j | | | ------------------ | | offset 16:| i | | | ------------------ | | offset 12:| ba | | | ------------------ | | offset 8: | dynamic link --|------------------------------------------| | ------------------ | offset 4: | static link ---|--------------------------------------------| ================== AR(b') [b=caller & b'=callee]<--|<-| offset 16:| cb | | | ------------------ | | offset 12:| ca | | | ------------------ | | offset 8: | dynamic link --|----------------------------------| | ------------------ | offset 4: | static link ---|-------------------------------------| $FP -> ================== AR(c) [b=caller & c=callee] $SP -> | | ============================================================== 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) =============================================================== at (**), we have the following: ----------- | level 2 | ----------------------------> --------------- ----------- | symtab with | | level 1 | -----------> --------------- | ba | ----------- | symtab with | --------------- | level 0 | -------\ | aa,ab,i,j,b | ----------- \ --------------- \ ---------------- Scope_Stack | symtab with | |ma,mb,i,j,a | ---------------- at (***), we have ----------- | level 2 | ----------------------------> --------------- ----------- | symtab with | | level 1 | -----------> --------------- | ba, c, i, j | ----------- | symtab with | --------------- | level 0 | -------\ | aa,ab,i,j,b | ----------- \ --------------- \ ---------------- Scope_Stack | symtab with | |ma, mb, i,j,a | ---------------- ============================================================== 4. Repeat question 2) using a single hash table to control the symbol table definitions. For question 3 assume the following 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 ================================================================= NOTE: name(level#) for variables and procedure names at (**) index ----------- 1 | *---- | ------> i(1) -> aa(1) -> i(0) -> ma(0) -> NULL ----------- 2 | *---- | ------> a(0) -> mb(0) -> NULL ----------- 3 | *---- | ------> b(1) -> j(1) -> ab(1) -> j(0) -> NULL ----------- 4 | *---- | ------> ba(2) -> NULL ----------- hash table at (***) ----------- 1 | | ------> i(2) -> i(1) -> aa(1) -> i(0) -> ma(0) -> NULL ----------- 2 | | ------> c(2) -> a(0) -> mb(0) -> NULL ----------- 3 | | ------> j(2) -> b(1) -> j(1) -> ab(1) -> j(0) -> NULL ----------- 4 | | ------> ba(2) -> NULL ----------- hash table ================================================================= *** Note problem 4 is similar to problem 1d, and simply provides the framework to present your solutions in. It's important to have a standard format so that the instructor can see how you develop your solution. 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 body of main end; -- main a) Show the run-time-stack after the following sequence of calls: main calls q pointers not set are indicated by --> ? q call p p calls r r calls p ----------- | b |AR(q) | a | | Old L1 --->? | retaddr | *-> ----------- -------- | | b |AR(p) ?<-| d[3] | (s3) | | a | -------- *---|-Old L1 | *---| d[2] | (s2) | retaddr | | -------- *->----------- | *-| d[1] | (s1) | | d |AR(r) | | -------- | | c | | | ? <------Old L2 | | | Display | | retaddr | | | | ----------- <----* | | | b |AR(p') | | | a | | *--|-Old L1 | | | retaddr | | sp-> ----------- <------* | | | | | | ----------- | j | s0->| i | ----------- | | | spim | | code for| | main & | | procs | ----------- b) Consider the following calling sequence main calls p p calls r ----------- | b | AR(p) | a | | Old L1 | | retaddr | -----------<----* | d | | -------- | c | |?<-| d[3] | (s3) ?<-| Old L2 | | -------- | retaddr | | |-| d[2] | (s2) ++ sp-> -----------<----|-* |-------- | | *---| d[1] | (s1) | | -------- | | | | Display | | ----------- | j | s0->| i | ----------- | | | spim | | code for| | main & | | procs | ----------- Give the register offset value for the following variables at that time ##(in the body of proc r)##: +8 ($s2) c _____________________________________________ +8 ($s1) a _____________________________________________ +0 ($s0) i _____________________________________________ ===================================================================== use the following construction outline for drawing your run-time stack: ----------- 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 construction outline for drawing your scope stack during the translation phase ----------- | | ----------- | | ----------- | | ----------- | | ----------- | ---------------Root -- | globals | \ ----------- Scope Stack whatever is appropriate use the following construction outline for drawing your global hash table - give the hash function above, all names hash to one of four locations ------- | 4 | --> ------- | 3 | --> ------- | 2 | --> ------- | 1 | --> ------- ------- where each name is represent by |id|l#| l# = level number -------