CSC362.L02 2004S, Class 37: Translating Procedure Calls

Admin
* Sorry about yesterday.
* Deal with the groups.
* Questions on translation?
  * Where should variables go on the stack?  See today's lecture for answers.
  * Do we have to deal with nested procedure declarations?  No
  * See more questions and answers in the other eBoard.
  * Should we have to implement all the built-in procedures?  No.
  * Read and Write?  Yes.
  * Multi-parameter Read and Write?  No.
  * Output formatting?  No.  write(x:5)
  * How do we deal with string literals?  Use the SWRITE
  * What about string variables?  Don't worry about them
   

Overview:
* Format of stack frames.
* Allocating space for locals and parameters.
* Division of responsibilities between caller and callee.
  * Function/procedure initialization.
  * Function/procedure cleanup.

Warning!  There are dozens of different ways to solve these problems.  We will discuss one of them (with some notes on variants)

What goes in the stack frame?
* the caller's frame pointer
* the local variables
* temporaries
* the frame pointer of the most recent invocation of the parent procedure
  * all ancestor's frame pointers
* return value
* parameters
* label to return to

Detour: Parent and ancestor variables

procedure oof;
  int y;
  procedure foo;
    int x;
    procedure bar;
    begin
      x := y;
    end
    procedure baz;
      procedure taz;
      begin
        bar;
      end;
    ...
    
END OF DETOUR

Our goals:
* Decide how "these things" (the parts of the frame) are arranged on the stack
* Decide how they get on and off the stack
* Decide who is responsible for putting them on teh stack and removing them

Pictures:
* Before call
	+--------+
    FP	| Caller |
        | Frame  |
    SP  | ...    |  ; Note stack pointer points to top thing in stack
        +--------+
* During call
	+--------+
    	| Caller |
        | Frame  |
        | ...    |  ; Note stack pointer points to top thing in stack
	+--------+
    FP	| Callee |
        | Frame  |
    SP  | ...    |  ; Note stack pointer points to top thing in stack
* After call
	+--------+
    FP	| Caller |
        | Frame  |
    SP  | ...    |  ; Note stack pointer points to top thing in stack
        +--------+

How do we make that transition?
* During call
	+--------+
    	| Caller |
        | Frame  |
        | ...    |  ; Note stack pointer points to top thing in stack
	+--------+
    FP	| old fp |
        | Callee |
        | Frame  |
    SP  | ...    |  ; Note stack pointer points to top thing in stack

Setup:
	+--------+
    FP	| Caller |
        | Frame  |
    SP  | ...    |  ; Note stack pointer points to top thing in stack
        +--------+
* push fp
	+--------+
    FP	| Caller |
        | Frame  |
        | ...    |  ; Note stack pointer points to top thing in stack
        +--------+
    SP	| old fp |
* MOVE SP into FP
	+--------+
      	| Caller |
        | Frame  |
        | ...    |  ; Note stack pointer points to top thing in stack
        +--------+
 FP,SP	| old fp |

Other stuff gets put on the stack
	+--------+
      	| Caller |
        | Frame  |
        | ...    |  ; Note stack pointer points to top thing in stack
        +--------+
    FP	| old fp |
        |        |
    SP  | ...    |

Summary of initialization:
* PUSH FP
* MOVE SP FP

How do we clean up after ourselves?
* MOVE FP SP 
* POP INTO FP
	+--------+
    FP	| Caller |
        | Frame  |
    SP  | ...    |  ; Note stack pointer points to top thing in stack
        +--------+

Yay!

Question: Who should be responsible for these steps?  Caller or callee?
* Callee ... easier to follow.  The callee sets up and cleans up
* Callee ... less code: Lots of procedure calls, only one body
* Caller ... may make other aspects of setup easier
* Note: Should be symmetrical: Whomever puts stuff on the stack is responsible for removing it from the stack.

Where should the return label go?
	+--------+
    FP	| Caller |
        | Frame  |
        | ...    |  
    SP  | rlabel |  
        +--------+

Where should the parameters and return value go?
	+--------+
      	| Caller |
        | Frame  |
        | paramn |  vs. param0  
        |  ...   |      param1
        | param1 |      ...
        | param0 |      paramn
        | rval   |  
        | rlabel |  
        +--------+
     FP | old fp |  
      	| Callee |
        | Frame  |
     SP | ...    |  

Callee refers to parameters as MEM[FP-12], MEM[FP-16], ...

Where should the local variables go?
     FP | old fp |  
      	| local1 |
        | local2 |
     SP | ...    |  

Observation:
* As you traverse the declarations for a block you need to keep track of the amount of stack space you have allocated (offset) and, at each variable, store that offset in the symbol table (for references to that variable) and increment the offset by an appropriate amount.

CALLEE SETUP
* PUSH FP
* MOVE SP FP
* PUSH SPACE FOR LOCALS

CALLEE CLEANUP
* MOVE FP SP 
* POP INTO FP
* JUMP MEM[SP] ; On the top of the stack is a label for where the procedure should return to

CALLER SETUP
* PUSH PARAM_N
* PUSH PARAM_N-1
  ..
* PUSH PARAM_2
* PUSH PARAM_1
* PUSH ... ; Room for return value
* PUSH RETURN_HERE
* JUMP START_OF_CALLEE

CALLER CLEANUP
* LABEL RETURN_HERE
* POP AND THROW AWAY ; return label
* POP AND SAVE ; return value
* POP AND THROW AWAY ; all the other stuff we put on the stack

Side note:
* When we are done with the callee, we should execute JUMP (wherever the return label resides on the stack): It may make sense for that to be at a convenient to reach point when we want to execute the JUMP (e.g., at the start of the frame or the top of the stack)

Detour (alternate view of SP):
	+--------+
    FP	| Caller |
        | Frame  |
        | ...    |  
        | return |  
        +--------+
    SP  | ...    |  

JUMP MEM[SP-4]

Side note: On many architectures (at least i86), RETURN is "POP and JUMP"

3 * (x - y)