reveal.js

# Procedures

---

CS 130 // 2024-09-19

# Procedures

### Compile a Simple Leaf Procedure

```python
def func(x,y):
    return x + y
```

---

```mips
func: add $v0, $a0, $a1
      jr  $ra
```

* the first argument to the procedure is in `$a0`
* the second argument to the procedure is in `$a1`
* the return value of the procedure goes in `$v0`
* `jr`: jump to the instruction whose address is in register `$ra`

```mips
func: add $v0, $a0, $a1
      jr  $ra
```

When you call this function, you must
* put the first argument in `$a0`
* put the second argument in `$a1`
* put the **return address** in `$ra`
* jump to the function

### Calling Our Leaf Procedure

```python
def func(x,y):
    return x + y

def main():
    func(1, 2)
```

---

```mips
func:
    add $v0, $a0, $a1
    jr $ra

main:
    li  $a0, 1 #load the first argument
    li  $a1, 2 #load the second argument
    jal func
```
`jal`: **jump and link** - put the next instruction's address in `$ra` and jump to the procedure

### Nested Procedure Calls

```python
def main():
    func(1, func(2, func(3, 4)))
```

---

```mips
main:
    li  $a0, 3
    li  $a1, 4
    jal func

li   $a0, 2
    move $a1, $v0
    jal  func

li   $a0, 1
    move $a1, $v0
    jal  func
```
**remember:** `$v0` is where we find the returned value

## Calling a Procedure

1. Put parameters in appropriate registers
  + `$a0`, `$a1`, `$a2`, `$a3`
2. Transfer control to the procedure: *jump and link*
  + `jal ProcedureLabel`
    - puts the current instruction's address into `$ra`
3. Perform task
4. Place result in a location the callee can find
  + `$v0`, `$v1`
5. Return control to the caller: *jump to addr. in register*
  + `jr $ra`

## Exercise
- Convert the following Python code into MIPS
- Make sure to create two functions
    - make sure the print happens in `main`, not `double_it`

```python
def double_it(e):
    return e + e

def main():
    print( double_it(21) )
```

## Non-Leaf Procedures
- Life would be easy if all procedures were "leaves"
- In reality, a procedure might call another procedure which may call another procedure ...
	- could even be *recursive*
- 
 We need a way to preserve the state of each partially completed call so that they all return properly

# Stack

## Stack
- MIPS provides a register `$sp` that stores a memory address
- 
 Addresses **above** `$sp` is memory that is already being used by other parts of the program
- 
 Addresses **below** `$sp` is free memory

## Stack
- The **called** procedure is responsible for restoring any saved registers `$s0`, ..., `$s7` as well as the stack pointer `$sp` register before returning
- 
 Any other register may be used without restoration, so the **calling** procedure is responsible for saving any data before making the call

## Memory Structure
![MIPS memory structure](/Fall2024/CS130/assets/images/COD/mips-memory.png)

## Stack Frames
![Procedure frame](/Fall2024/CS130/assets/images/COD/stack-frame.png)

## Exercise
- Convert the following C code into MIPS

```python
def double_it(e):
    return e + e

def calc(c):
    d = double_it(7)
    return c + d

def main():
    a = 5
    b = calc(a)
```

## Exercise Solution: Compute

```python
def double_it(e):
    return e + e
```

```mips
double_it: add $v0, $a0, $a0    # returns e + e
         jr $ra
```

## Exercise Solution: Calc - Take 1

```python
def calc(c):
    d = double_it(7)
    return c + d
```

```mips
calc: li  $a0, 7          # puts 7 in a0
      jal double_it         # calls compute(7)
      add $v0, $v0, $a0   # adds argument to result
      jr  $ra
```

- 
 Unfortunately this will fail. Why?
    + 
 Both `$a0` and `$ra` will be erased!

## Exercise Solution: Calc - Take 2

```python
def calc(c):
    d = double_it(7)
    return c + d
```

```mips
calc: addi $sp, $sp, -8    # allocates space
      sw   $a0, 0($sp)     # stores c on the stack
      sw   $ra, 4($sp)     # stores $ra on the stack
      li   $a0, 7          # puts 7 in a0
      jal  double_it       # calls double_it(7)
      lw   $ra, 4($sp)     # restores $ra
      lw   $a0, 0($sp)     # restores argument
      addi $sp, $sp, 8     # deallocates space
      add  $v0, $v0, $a0   # adds argument to result
      jr   $ra
```

## Exercise Solution: Main

```python
def main():
    a = 5
    b = calc(a)
```

```mips
main:    li   $s0, 5          # a = 5
         move $a0, $s0        # loads a into argument
         jal  calc            # calls calc(5)
         move $s1, $v0        # b = result
```

## Assignment

- [Assignment 4](../../assignments/assignment-4/)
  - Translate a Python program that has functions and Arrays
  - 8 points
  - Part of it has been done - you'll do a "middle" function.