Run time environment - Control Stack - Ch 7 - Lecture 1 of 2
09April08

This lecture covers on the run-time-environment - Control Stack - when we are examining nested definitions of procedures and who-calls-who... and such. In lecture Monday, we saw some examples of using a Display (7.3.8) which we go into more depth about today. We will cover the Static/Dynamic link (7.3.5) on Monday.

This is important since SPIM will expect to have the Control Stack growing from the top of memory.

                                       ---------------
                                       |  space      |
                                       |   for       |
                                       |   vars      |
                                       ---------------
                                       | old level ? | control
  Activation record for a procedure    | return addr |  info
                                       ---------------

Figure 7.14 Maintaining the display will be useful for our discussion. This shows using d[1], d[2], d[3] ... for the display.

The size of the activation record is known at compile time, so we can setut the appropriate pushes/pops of the Control Stack.

In lecture I will use s0 for globals, s1 for level 1, s2 for level 2, s3 for level 3 and top_sp for top of stack [TOS]


main
   proc A is
        proc B is
             proc C is
             ... A; ...
             end C;

             ... C; ...             -- B calls C

        end B;

        ... B; ...                  -- A calls B

   end A;

end; -- main

Assume:

Main calls A calls B calls C calls A (A') calls B (B') calls C (C')

The Display:

---------------------------------------------
| calls    A    B    C    A'    B'     C'   |
|--------------------------------------------
| d[3]     ?    ?    C    C     C      C'   |
---------------------------------------------
| d[2]     ?    B    B    B     B'     B'   |
---------------------------------------------
| d[1]     A    A    A    A'    A'     A'   |
---------------------------------------------
| saved:   ?    ?    ?    A     B      C    |
---------------------------------------------

The Display Picture of the RTS

     $top_sp -> -----------------
                |local vars (C) |
                |     : old d[3]|-----------------------------------*
                |AR(C): return  |                                   |
         $s3 -> -----------------                                   |
                |local vars (B) |                                   |
                |     : old d[2]|--------------------------------*  |
                |AR(B): return  |                                |  |
         $s2 -> -----------------                                |  |
                |local vars (A) |                                |  |
                |     : old d[1]|-----------------------------*  |  |
                |AR(A): return  |                             |  |  |
         $s1 -> -----------------                             |  |  |
                |local vars (C) |                             |  |  |
                |     : old d[3]|----> (old $s3 never set)    |  |  |
                |AR(C): return  |                             |  |  |
                ----------------- <---------------------------|--|--*
                |local vars (B) |                             |  |
                |     : old d[2]|----> (old $s2 never set)    |  |
                |AR(B): return  |                             |  |
                ----------------- <---------------------------|--*
                |local vars (A) |                             |
                |     : old d[1]|----> (old $s1 never set)    |
                |AR(A): return  |                             |
                ----------------- <---------------------------*
                |               |
                |  global vars  |
         $s0 -> -----------------
                |   code A,B,C  |
                |               |
                |   code main   |
                -----------------

return to Ch7 Run Time Environment lecture