Class Notes on Function Calls

Introduction

This document is intended as a backup to the lectures on the implementation of function calls in C. After discussing in general the minimal functionality necessary to support function calls in our compiler, we present a set of attribute rules which generate the appropriate IC code statements.

We shall present a simple view of code generation for functions based on the uniform width of 4 bytes for all parameters and for the return value of a function; the general idea presented here can be easily modified for the more complex case.

Function Declarations and Invocations

Consider a simple recursive function such as the following: 
int A; 

int fact(int x) {         // This is the Callee 
   int t;
   if(x<2)
     return(1);
   else {
     t = x * fact(x-1);
     return(t); 
   }
}

main(){
   .
   .
   .   
   A = 4;
   B = fact(A+1);      // This is the Caller 
   .
   .
   .   
}
What is necessary in order to generate IC code to translate this program? Basically, there are two issues: control flow and data access.

It should be obvious to you by now that our compiler generates code as it encounters the instructions in the source file; thus, the code for each function definition will be added to the IC code array as it is parsed and translated. The IC code array will thus consist of separate regions of code, one for each function in the source program. In order to call a function, the caller must jump to the starting location of the appropriate region of IC code where the callee lives, and when the function call is ended, a jump must be made back to the instruction following the jump in R.

The way this is typically implemented in assembly language is that the jump to a function also saves the address of the following instruction (i.e., the program counter (PC) plus 4) in a special register (in MIPS, this is called $ra) and then the return can be effected by jumping to the location in this register. For now, we will assume that we have a special memory location called (RA) for storing this value. We will thus add two instructions to our IC code language:

  1. (call, -, -, loc) -- This saves the value (PC+4) in (RA) and jumps to the location loc in the IC code array.
  2. (return, -, -, -) -- This jumps to the address in (RA).
The second issue to be discussed in the use of memory for parameters, local data, and other information needed by the function call. Such data is stored at the high end of the virtual memory space in the Run-Time Stack (RTS); data for each function call is allocated on the stack in Stack Frames, and there is a special register, called the Stack Pointer, denoted "$sp", which points to the top byte in the top stack frame. If the function fact had been called by main and then called itself recursively once the RTS would look like this: 
      |               |
$sp ->|---------------|
      | SF for fact   |
      |               |
      |---------------|
      | SF for fact   |
      |               |
      |---------------|
      | SF for main   |
      |               |
      |---------------| FFFF FFFF  (last byte in 32bit VM space)

All data in the stack frame must be referenced as an offset from the stack pointer. Thus there are two kinds of data which a function may refer to: global data which is declared in file scope, laid out on the lowest ST on the stack, and referred to by name ("A", "B[4]"); and local data which is declared as a parameter or local variable in the function, laid out (generally) on a ST which is just above the lowest level on the stack of symbol tables, and referred to as offsets from the stack pointer ("$sp[0]", "$sp[4]"). Therefore, it will be necessary in generating variable references to have some way of determining which category a variable belongs to. We will assume in what follows that we have available to us the following function:

IsStatic(id.lexval) -- Returns 1 if, when looking up the name id.lexval, it is found on the lowest-level ST on the stack; returns 0 if the variable is not found, or if it is found on ST not on the lowest level.

This must be integrated into the Data Layout rules presented in a previous set of notes, and will be explained further below.

Stack Frame and Data Access

For the simple case we consider here, the stack frame of each function has a fixed size, and so a frame can be pushed on the stack by subtracting this size from $sp. Suppose that fact has a frame of 16 bytes; then when a call to fact is made, its frame is allocated by executing: 
      (sub $sp, $sp, 16)
which has the effect of adding the frame on top: 
      |               |
$sp ->|---------------|
      | SF for fact   |
      |               |
      |---------------|
      | SF for fact   |
      |               |
      |---------------|
      | SF for fact   |
      |               |
      |---------------|
      | SF for main   |
      |               |
      |---------------| FFFF FFFF  (last byte in 32bit VM space)
When the call is ended, we would pop the frame by executing: 
      (add $sp, $sp, 16)
As mentioned above, ALL access to parameters and local data for a function is done by taking an offset from the stack pointer. This can be before the call is made (a negative offset into the frame about to be pushed) or during the call (a positive offset into the top frame). This is how caller and callee communicate parameters and return value. For now we do not consider access to any other frames.

The stack contains the following information:

  1. Parameter values -- values of parameter expressions ("actual parameters") in the function call, which are "assigned" to the parameter variables ("formal parameters") in the function definitions.
  2. Local variables -- variables in local declarations inside the function definition.
  3. Saved state of the caller -- When the caller invokes a function, it is in a sense suspended and will be awoken when the function call returns; hence, it is useful to be able to save local state (essentially, register values) to be restored after the call; for now, the only state we save is the return address, as discussed above.
  4. Return value of the function.
We will assume the following organization of the stack frame: 

$sp-> |---------------|+                  |---------------|
      | Parameters    ||                  |Frame defined  |
      |---------------||  <= same as =>   |by offsets in  |
      | Temporaries   ||                  |ST for function|
      |---------------|+                  |---------------|
      | Return Address|
      |---------------|
      | Return Value  |
      |---------------|
The return value for our compiler is always 4 bytes long, and so is the return address; the length of the other two fields may vary. Since the parameters and temporaries are always in a single ST, in which the offsets for each item, and the global length and alignment, have already been calculated, we will simply use this frame as the shape of the top two fields of the stack frame, and add the RA and the RV below.

In more general settings than our project, the alignment of a stack frame is a delicate issue, since we can not predict very well what frames will be stacked on top of each other, this being due to the dynamic behavior of the program. Therefore it is hard to know the alignment restriction that must be placed on the position of the stack pointer. For this reason, it is usual to observe the worst-case alignment when moving the stack pointer. For many machines, this would mean the stack pointer is always double-word aligned, but for our project, word alignment suffices. We will use word alignment in what follows.

In the example which started this document, we would have the following ST: 

 Name    Type    Offset
 ----    ----    ------
   x      Int      0
   t      Int      4
 ----------------------
 Alignment: 4  Length: 8
The return value and return address would both be 4 bytes long, which gives us a 16 byte frame: 

$sp-> |---------------|
      |      x        |
      |---------------|
      |      t        |
      |---------------|
      | Return Address|
      |---------------|
      | Return Value  |
      |---------------|
If we take account of the position before and after the call, we have the following offsets: 
      |               |                       |               |           
      |---------------|      call       $sp-->|---------------|
      |      x        | (sub $sp, $sp, 16)    |      x        |
      |---------------|        ===>           |---------------|
      |      t        |                       |      t        |
      |---------------|                       |---------------|
      | Return Address|      return           | Return Address|
      |---------------|  (add $sp, $sp, 16)   |---------------|
      | Return Value  |      <===             | Return Value  |
$sp-->|---------------|                       |---------------|
      |               |                       |               |
      |               |                       |               |
      |               |                       |               |
      |               |                       |               |

Variable  Before & after call   During call
--------  -------------------   -----------
   x       $sp[-16]             $sp[0]                    
   t       $sp[-12]             $sp[4]                    
   RA      $sp[-8]              $sp[8]                    
   RV      $sp[-4]              $sp[12]
In general, if we assume that RA and RV are both 4 bytes long, and if a particular function f has a fixed stack frame size of S, then these references to RA, RV, or an arbitrary parameter or local variable X with offset(X) inside the ST for f can be expressed as: 
Variable  Before & after call   During call
--------  -------------------   --------------
   X      $sp[offset(X)-S]      $sp[offset(X)]                                       
   RA     $sp[-8]               $sp[S-8]                    
   RV     $sp[-4]               $sp[S-4]

In fact, we will always do the call before pushing the stack frame, and the return after popping the frame, so RA can always be found at $sp[-8].

Layout of instructions for caller and callee

The caller and callee must between them implement the calling sequence (evaluating parameters and placing them on the stack frame about to be pushed, saving the return address, jumping to the new location, and decrementing the stack pointer) and the return sequence (saving the return value on the stack, incrementing the stack pointer, jumping back to the saved return address, and retrieving the return value), as well as make proper references to local and static data. In general, we put as much of the burden of this activity on the callee, as a function is defined only once, but may be called many times, and this avoids repeating the same instructions over and over for each call. We may diagram the various duties of the caller and callee as follows: 
 
    |                 |
    |-----------------|
    |  Eval e0 and    |   Caller: use of expression  f(e0, e1, ..., en)
    |  put in $sp[-S] |   S is frame size for f
    |-----------------|
    |  Eval e1 and    |   
    |  put in $sp[4-S]|   
    |-----------------|
    |  Eval rest of   |
    |  ei and put in  |
    |  $sp[4*i-S]     |
    |-----------------|
    | call, -, -, L   |   Jump to start of callee and save RA in $sp[-8]
    |-----------------|
 RA:| move T, $sp[-4] |   Move RV to some variable and use it as value of expression
    |-----------------|
    |       .         |
            .
            .
    |-----------------|
  L:| sub $sp,$sp, S  |    Callee 
    |-----------------|
    | Code for callee |
    | Reference to    |
    | local var/param |
    | X is translated |
    | as $sp[off(X)]. |
    | Reference to    |
    | static A is just|
    | A.              |
    |                 |
    |-----------------|+
    | E evaluated and ||    When  return(E) is encountered, 
    | value placed in ||    put value of E on stack
    | $sp[S-4]        ||    and then do return sequence.  
    |-----------------||
    | add $sp,$sp, S  ||
    |-----------------||
    | return          ||
    |-----------------|+
    |                 |
    |                 |
    |                 |
    |-----------------|
    | add $sp,$sp, S  |     At end of code for function, do 
    |-----------------|     return sequence anyway (even if value
    | return          |     has not be calculated)
    |-----------------|     Return will jump to location in $sp[-8]
    |                 |

Attribute Rules for Function Definitions and Function Calls

The main issues in performing this translation with attribute rules is to enter the appropriate information into the symbol, and then to generate the correct offsets during the generation of code for the function calls. The information that needs to be saved in the symbol table for each function declaration is:
  1. The starting location for the code for this function; and
  2. The frame size for the function.
These will be manipulated with the following functions:
  1. LookupStart(id.lexval) -- Get the starting location in the IC code array for this function name;
  2. LookupFrameSize(id.lexval) -- Get the frame size for this function;
  3. AddFunctionEntry(id.lexval, type, start, framesize) -- Adds this entry to the symbol table at the bottom of the stack (since functions are declared at the global level).
  4. Length(tos) -- This returns the length of the top ST on the stack.
We now present our attribute rules for translating function declarations and function calls. 
D  ->  T id "("            PushST(); 
                           tempName = id.lexval;
     
       L  ")"  "{" Ds      AddFunctionEntry(id.lexval, Append(T.type, L.type), nextQuad, 
                                            (Length(tos) + 8));
                           AQ("sub", "$sp", "$sp", (Length(tos) + 8)); 

       Ss  "}"             AQ("add", "$sp", "$sp", (Length(tos) + 8)); 
                           AQ("return", "-", "-", "-"); 
                           Pop(); 
       
L  -> T id                 L.type = T.type;

L  -> L "," T id           L.type = Append(L1.type, T.type); 


S  -> "return" "("  E   ")" 
                           AQ("move", "$sp[" + itoa(LookupFrameSize(tempName)-4) + "]", "-", $3.place);
                           AQ("add", "$sp", "$sp", itoa(LookupFrameSize(tempName)));
                           AQ("return", "-", "-", "-"); 

E  -> id  "(" Es  ")" 
                           AQ("call", "-", "-", itoa(LookupStart(id.lexval))); 
                           E.place = NewTemp(); 
                           AQ("move", E.place, "-", "$sp[-4]"); 

Es  -> E
           E.offset = 0; 
           E.framesize = LookupFrameSize($-1.lexval);    // Go down stack to grab name of function!
           AQ("move", "$sp[" + itoa(-(E.framesize)) + "]", "-", $1.place); 

Es  -> Es "," E

           Es.offset = Es1.offset + 4;           // For simplicity, all types have size 4
           Es.framesize = Es1.framesize; 
           AQ("move", "$sp[" + itoa(E.offset-Es.framesize) + "]", "-", E.place); 


E  -> id  
                  if(IsStatic(id.lexval)      // This is how to start the placename for
                     E.place = id.lexval;     // a variable reference
                  else
                     E.place = "$sp";
NOTES:
  1. The main function is implemented similarly, except that it does not have parameters, return value, or return address. However, it is a function like any other, and its local variables are allocated on the RTS just like any other. It is probably best for simplicity to just treat it identically to a normal function, and allocate space for a RV and RA even if it is not used.
  2. The parsing of the parameter lists and expression lists is done left-recursively, to facilitate working from the front of the list to the back; depending on your symbol table organization, it will be easier to insert from the front forwards (calculating offsets from front to back). The alternative is to use right recursion and process lists (and offsets) in reverse.
  3. As usual, for simplicity we have left out some details. For example, each of the moves when passing parameters in the translation above is essentially an assignment statement, and we must check for types and insert coercions as necessary ("int-to-fp", "fp-to-int").
  4. Simplicity has its costs: the grammar given above does not actually handle complex function calls such as "g(z,h(y,f(z)), x)" because it starts to load the parameters onto the stack before checking if there are any other function calls in the parameter list. The correct way to do it is to build up a list of places for the expression list, and then load them all at once before the call. I think it is best to live with this situation in this project, and the test cases are quite simple and do not need this generality. Please go ahead and implement it the right way if you have the time!

Example: The factorial function

We conclude by giving the translation of the factorial function from the beginning of this document, and the listing of the static symbol table. 
Intermediate Code Program:

  0: (sub, $sp, $sp, 16)
  1: (move, t1, -, 0)
  2: (blt, $sp[t1], 2, 4)
  3: (jump, -, -, 8)
  4: (move, $sp[12], -, 1)
  5: (add, $sp, $sp, 16)
  6: (return, -, -, -)
  7: (jump, -, -, 21)
  8: (move, t2, -, 4)
  9: (move, t3, -, 0)
 10: (move, t4, -, 0)
 11: (sub, t5, $sp[t4], 1)
 12: (move, $sp[-16], -, t5)
 13: (call, -, -, 0)	# fact
 14: (move, t6, -, $sp[-4])
 15: (mult, t7, $sp[t3], t6)
 16: (move, $sp[t2], -, t7)
 17: (move, t8, -, 4)
 18: (move, $sp[12], -, $sp[t8])
 19: (add, $sp, $sp, 16)
 20: (return, -, -, -)
 21: (add, $sp, $sp, 16)
 22: (return, -, -, -)

 23: (sub, $sp, $sp, 8)
 24: (move, A, -, 2)
 25: (add, t9, A, 1)
 26: (move, $sp[-16], -, t9)
 27: (call, -, -, 0)	# fact
 28: (move, t10, -, $sp[-4])
 29: (move, A, -, t10)
 30: (add, $sp, $sp, 8)
 31: (halt, -, -, -)	# End of main
 32: (end-of-program, -, -, -)


Symbol Table:

Addr	Name	Type
----	----	----
0:	A	Int
0:	fact	Int <- (Int)
23:	main	Void <- (Void)