Procedure

Learning this in the context of CS241E. They are essentially functions.

A procedure is an abstraction that encapsulates a reusable unit of code.

Process:

1. The code that calls a procedure (i.e. caller) transfers control to the code of the procedure (i.e. callee) by modifying the Program Counter. Arguments can be passed as parameters.
2. At the end of execution of procedure, control is transferred back to caller. It can return a value.

To implement this functionality, the implementations of the calling code and of the procedure must agree on conventions :

• Where in memory or in which registers will the arguments and the return value be stored?
• Does the calling code or the procedure allocate and free memory needed for the call?
• Which registers may change their value during a procedure call?
  • These are called caller-save registers. If the caller needs their value, it needs to save it elsewhere before the call.
• Which registers must keep their original value after a procedure call?
  • These are called callee-save registers. If the procedure (callee) modifies them, it must change them back to their original values before returning to the caller

Caller-Save vs Callee-Save (this is very confusing)

• Caller-Save registers: Values may be modified by a procedure call.
  • Almost ALL registers are caller-save, by default.
• Callee-Save Registers: Register values are preserved by a procedure call.
  • The Stack Pointer (register 30) and Frame Pointer (register 29) are callee-save. This is super important because of the way we designed our Variable to be accessed, which requires the value of Reg.framePointer

Control Transfer

Achieved through the following code

# Caller Code
LIS(Reg.targetPC(8)) 
Use(proc) 
JALR(Reg.targetPC(8)) # Saves the return address in Reg.link (31)
 
# Callee Code
Define(proc)
.. (Body of procedure) ...
JR(Reg.link (31)) # Jump back to caller code
 

Other Terminology

• Prologue: The code before the body of the procedure, which prepares the procedure for execution
• Epilogue: The code after the body of the procedure, which cleans up the memory that was being used by the procedure and prepares to return to the calling code

Allocating a Procedure Frame

For the variables of the procedure, we should be allocating those on the Stack Frame using Stack Frame using Chunks, which is done with Stack.allocate(frame). This sets Reg.result and Reg.stackPointer to the memory address.

We also want to set this as the Reg.framePointer. However, we would not be able to restore this value afterwards, when control goes back to the caller. The caller would not be able to access its variables, which are accessed using Reg.framepointer.

To fix this, we design the frame pointer as callee-saved

• i.e. the Frame Pointer value needs to be the same at the prologue and epilogue in the callee. We save this frame pointer value in a variable called Dynamic Link, which will hold the address of the frame of its caller.
  • There is also a thing called static link, which I will learn about soon to implement Nested Procedures and Nested Procedures and Closures

title: Declaring the [[Stack Frame|Frame Pointer]] as caller-save would not work
Remember, variables are abstractions. At the Assembly level, reading a variable value is done with an offset of `Reg.framePointer` through `LW(register, variableToOffset(variable), baseRegister)`.
 
Caller-save means the callees can modify the register values and not restore it. It is the responsability of the caller to save it somewhere else.
However, if the frame pointer is overwritten after calling the procedure with a different value, the caller, after storing this variable, can't access this variable which stored the framepointer address anymore since that depends on the original frame pointer value.
 
Instead, we make the `Reg.framePointer` callee-save, we force the callees to restore the original value of the `Reg.framePointer`.

Implementation: Inside the callee, when you call Stack.allocate(frame), this will update Reg.result. When you store the frame pointer value in the dynamic link, store it at an offset from Reg.result, NOT Reg.framePointer.

Saving the Link Register

The same issue that we face with the Reg.framepointer value being overwritten happens with the Reg.link value, if multiple procedures are called. We fix it the same way, storing it in the variable savedPC in the prologue. and loading that afterwards.

However, we don’t run into the same issue with the Reg.framePointer, so we can just make it caller-save.

title: `Reg.link` is NOT Callee-Save
I AM NOT CONVINCED
 
One might mistakenly think that Reg.link is also callee-save, just like `Reg.framePointer`. But this is not the case: `Reg.link` is caller-save because executing the code to call a procedure can modify its value, such as when we call JALR.
 
In the case of the frame pointer, executing the code to call a procedure preserves the value of the callee-save frame pointer.
 

Passing Arguments

Since the arguments might not fit into Registers, we pass them into Memory.

The arguments can be expressions/procedures themselves, so we need to evaluate these arguments first before calling the procedure.

The caller will run Stack.allocate(parameters), and so by convention, the callee will expect the params to be stored in Reg.result. Remember that the callee will also need to call Stack.allocate(frame), which will overwrite Reg.result, so we store the value into the variable paramPtr that holds the address of the parameters of the procedure.

Final Code for the procedure

# Caller Code
evaluate arguments into temporary variables
Stack.allocate(parameters)
parameter 1 := temporary 1 
...
parameter n := temporary n
LIS(Reg.targetPC (8))
Use(proc)
JALR(Reg.targetPC (8))
 
# Callee Code
Define(proc)
Reg.savedParamPtr (5) := Reg.result (3)
Stack.allocate(frame)
dynamicLink := Reg.framePointer (29) # Use frame.store with reference to Reg.result
Reg.framePointer (29) := Reg.result (3)
savedPC := Reg.link (31)
paramPtr := Reg.savedParamPtr (5)
... (body of procedure) ...
Reg.link (31) := savedPC
Reg.framePointer (29) := dynamicLink
Stack.pop // frame
Stack.pop // parameters
JR(Reg.link (31))

Objects

We can actually convert an object into a procedure. Ahh, this is the paradigm with Procedural Programming.

In Scala, the original Scala, the original Object-Oriented Programming code:

class Counter {
	var value = 0
	def get () = value
	def incrementBy ( amount : Int ) = {
		value = value + amount
	}
}
 
val c = new Counter
c.incrementBy (42)
c.incrementBy ( -5)
c.get ()

Can be converted into a procedure:

The counter made out of closures is going to behave the same as the counter object.

def newCounter : (()= >Int , ( Int )=> Unit ) = {
	var value = 0
	def get () = value
	def incrementBy ( amount : Int ) = {
		value = value + amount
	}
	(get , incrementBy)
}
 
val c2 = newCounter
c2 ._2 (42) // This is just scala syntax for getting out the first or second component of a pair. 
c2 ._2 ( -5)
c2 ._1 ()

Related

• Tail Call
• First-Class Function / Function Values
• Nested Procedure
• Closure