http:^^www.cs.wisc.edu^~cs354-2^cs354^lec.notes^procedures.html

This data set contains WWW-pages collected from computer science departments of various universities

                2. same procedure could be used to decrement the value
		   in other registers -- just copy the value to register $4
		   first, and copy it out afterwards.


historically more significant mechanism:  parameters on stack
					 ---------------------

place the parameters to a procedure (function) in the activation
record for the procedure.

    sub $sp, $sp, 8   # allocate space for parameters
    sw  $9, 8($sp)    # place parameter 1 into AR of proc
    sw  $18, 4($sp)   # place parameter 2 into AR of proc
    jal proc
    .
    .
    .
    proc:
    sub $sp, $sp, 12  # allocate remainder of AR for proc
		      # assume fixed size (too big) activation record
    lw  $10, 20($sp)  # retrieve parameter 1 for use
    lw  $11, 16($sp)  # retrieve parameter 2

                      # use parameters in procedure calculations

    add $sp, $sp, 20  # remove AR of proc
    jr  $ra




calling program:  allocates space for parameters
		  places parameters into stack
		  calls procedure
		  deallocates remainder of AR of procedure

procedure:        allocates AR (or remainder of AR)
		  deallocates AR of procedure (or at least most of it)



MIPS convention -- when passing parameters in registers,
the first 4 parameters are passed in registers $4-7.
  Then, ANY and ALL procedures use those registers for their parameters.


If there are nested subroutine calls, and registers $4-7 are
used for parameters, the values would be lost (just like the
return address would be lost for  'jal' if not saved).  There are
2 possible solutions.

  1.  For non-recursive nested calls, each procedure has associated
  with it a section of memory.  Before a nested call is made,
  the current parameters are stored in that memory.  After the return
  from the nested call, the current values are restored.

  2.  For recursive calls, current parameters are stored on the stack before
  a nested call.   After the return from the nested call, the
  current parameters are restored.


  here's a general layout of how this second option is used
  (with 4 or fewer parameters):

	procedure layout:
	    allocate remainder of AR
	    put return address on stack into AR of procedure

	    procedure calculations

	    to set up a call to proc2,
	       place current parameters (in $4-7) into AR of procedure
	       allocate AR for proc2
	       set up parameters to proc2 in $4-7
	       call proc2 (jal proc2)
	       copy any return values out of $2-3, $4-7
	       pop current parameters from stack back to $4-7

	    more procedure calculations (presumably using procedure's
	      parameters which are now back in $4-7)

	    get procedure's return address from AR
	    return (jr $ra)


	       

more about parameter passing.

  a trivial example that contains nested calls, so saves
  current parameters on the stack:

  # a set of procedures that do the following,
  # if a < b, then switch a with b and decrement both


  # a is in register 20
  # b is in register 21

  .text

            sub $8, $20, $21
	    bgtz $8, othercode
	    move $a0, $20           # place parameters in registers
	    move $a1, $21    
	    jal s_and_d
	    move $20, $a0           # copy out return values
	    move $21, $a1    
 othercode: 

	    done

 # switch is a procedure to switch its 2 parameters, and then
 #   decrement each of the 2 parameters
 #   $a0 ($4) -- first parameter
 #   $a1 ($5) -- second parameter
 #   $8 -- temporary for switching
 s_and_d:   sub  $sp, $sp, 20     # allocate frame for switch
	    sw   $ra, 20($sp)     # save return address on stack

	    move $t0, $a0         # switch the 2 parameters
	    move $a0, $a1         # $t0 is register 8 ($8)
	    move $a1, $t0

	    jal decrement         # the value to decrement is already
				  # in $4.
	    sw $a0, 16($sp)       # place current parameter in frame
	    add $a0, $a1, $0      # set up parameter in $4
	    jal decrement
	    add $a1, $a0, $0      # copy return value
	    lw $a0, 16($sp)       # restore current parameter

	    lw $ra, 20($sp)       # get return address
	    jr $ra

# procedure decrement subtracts 1 from its parameter
#   $4 -- parameter to be decremented
decrement:  addi $a0, $a0, -1
	    jr $ra



Summary and other ideas:
 1.  use registers 
     + easy, and don't have to store data in memory (faster)
     - limited number of registers
     - doesn't work for recursion, and must be careful when 
       using it where there are nested subroutines
 2. use some registers, and place the rest on the stack
     + since many procedures have few parameters, get the advantages
       of (1) most of the time.
     - lots of "data shuffling"
 3. put all parameters on the stack (an unsophisticated compiler might
    do this)
     + simple, clean method (easy to implement)
     - lots of stack operations (meaning slow, since the stack is in
       memory)
 4. put parameters in memory set aside for them
     + simple, clean method
     - lots of memory operations (slow)
     - doesn't work for recursion

Note: whatever you do, try to be consistant.  Don't use all 4 methods
      in the same program.  (Its poor style.)





about frame pointers
      --------------


The stack gets used for more than just pushing/popping stack frames.
During the execution of a procedure, there may be a need for temporary
storage of variables.  The common example of this is in expression
evaluation.
 Example:      high level language statement
		 Z = (X * Y) + (A/2) - 100
   The intermediate values of X*Y and A/2 must be stored somewhere.
On older machines, register space was at a premium.  There just weren't
enough registers to be used for this sort of thing.  So, intermediate
results (local variables) were stored on the stack.

They don't go in the stack frame of the executing procedure; they
are pushed/popped onto the stack as needed.


So, at one point in a procedure, parameter 6 might be at 16($sp)


  |       |
  ---------
  |       |<- $sp
  ---------
  |       | ---
  ---------   |
  |       |   |
  ---------   |
  |       |   |--- procedure's frame
  ---------   |
  |param 6|   |
  ---------   |
  |       |   |
  --------- ---
  |       |
  ---------


and, at another point within the same procedure, parameter 6 might be
at 20($sp)

  ---------
  |       |<- $sp
  ---------
  | temp2 |
  ---------
  | temp1 |
  ---------
  |       | ---
  ---------   |
  |       |   |
  ---------   |
  |       |   |--- procedure's frame
  ---------   |
  |param 6|   |
  ---------   |
  |       |   |
  --------- ---
  |       |
  ---------



All this is motivation for keeping an extra pointer around that does
not move with respect to the current stack frame.  

Call it a FRAME POINTER.  Make it point to the base of the current
frame:

  ---------
  |       |<- $sp
  ---------
  | temp2 |
  ---------
  | temp1 |
  ---------
  |       | ---
  ---------   |
  |       |   |
  ---------   |
  |       |   |--- procedure's frame
  ---------   |
  |param 6|   |
  ---------   |
  |       |<- frame pointer 
  --------- ---
  |       |
  ---------

Now items within the frame can be accessed with offsets from the
frame pointer, AND the offsets do not change within the procedure.


parameter 6 will be at -4(frame pointer)
A new register is needed for this frame pointer.  Pick one.
(The chapter arbitrarily chooses $16, but it could be any register.)

parameter 6 is at -4($16)


NOTE:  

 -- The frame pointer must be initialized at the start of
every procedure, and restored at the end of every procedure.
 -- The MIPS architecture doesn't really allocate a register for a
frame pointer.  It has something else that it calls a "virtual frame
pointer," but it isn't really the same as described here.  On the
MIPS, all data with a stack frame is accessed via the stack pointer, $sp.




New problem:
  What happens if you've got lots of variables, and your procedure
  runs out of registers to put them in.  This occurs when you are
  following the conventions for register usage, and you shouldn't
  overwrite the values in certain registers.

  Most common solution:  store register values temporarily on the
                         stack in AR.


Two types:

CALLEE SAVED
   a procedure clears out some registers for its own use

   register values are preserved across procedure calls

   MIPS calls these SAVED registers, and designates $s0-s8 for this
   useage.

   $s0-$s8 are aliases for $16-$23, $30

   the called procedure saves register values in its AR,
     uses the registers for local variables,
       restores register values before it returns.


CALLER SAVED
   the calling program saves the registers that it does not want a
    called procedure to overwrite

   register values are NOT preserved across procedure calls

   MIPS calls these TEMPORARY registers, and designates $t0-t9 for this
   useage.

   $t0-$t8 are aliases for $8-15, $24-$25

   procedures use these registers for local variables, because
     the values do not need to be preserved outside the scope
     of the procedure.






what the mechanisms should look like from the compiler's
point of view:


THE CODE:

   call setup
   procedure call
   return cleanup
   .
   .
   .
procedure:  prologue

            calculations

            epilogue




CALL SETUP
  place current parameters into current stack frame
  save any temporary registers that need to be preserved across the
     procedure call
  allocate space for ALL parameters frame (AR) for procedure to be called
     (move $sp to give enough space for the procedure's parameters)
  place first 4 parameters to procedure into $a0-$a3
  place remainder of parameters to procedure into newly allocated space




PROLOGUE
  allocate space for remainder of stack frame
  save return address in stack frame
  copy needed parameters from stack frame into registers
  save any needed saved registers into current stack frame


EPILOGUE
  restore (copy) return address from stack frame into $ra
  restore from stack frame any saved registers (saved in prologue)
  de-allocate stack frame (or most of it)
     (move $sp so the space for the procedure's frame is gone)


RETURN CLEANUP
  copy needed return values and parameters from $v0-v1, $a0-a3, or stack
     frame to correct places
  de-allocate remainder of procedure's stack frame
     (move $sp so the space for the procedure's frame is gone)
  restore any temporary registers from stack frame (saved in call setup)





REVISITING PROCEDURES.


What needs to be done depends on HLL.
The order is fairly consistent.
What is done by caller/callee varies from implementation to implementation.


Needed:
 --> items to go in activation record.

   return address
   frame pointer
   parameters
   local variables  --|  may be some overlap here
   saved registers  --|


 --> mechanism

 before procedure CALL
 1.  caller gets parameters into correct location
 2.  space is allocated for part of activation record
 then
 3.  control is transfered to procedure

 before procedure RETURN
 1.  put return values into correct location
 2.  restore anything that needs to be restored (return address, callee
     saved registers, frame pointer)
 3.  remove activation record
 then
 4.  jump to return location


some guidelines:

 -- if parameters passed on stack, want them "between" caller and
    callees activation records.

 -- use of frame pointer reduces amount of code.  It gives a better
    level of abstraction.

 -- depending on conventions and implementations, the amount of
    space allocated for activation record may be different then
    the amount of space removed.
	
	If callee allocates space, and parameters are on stack.

	If caller and callee each allocate some of the space.

 -- MIPS:
      always allocate space in activation record for all parameters,
      even if there are less than 4.

</pre>