Objective: You are going to convert a simple program (on the next page, you can copy paste) into a simple leaf procedure (leaf means it doesn’t call anything else).
You can achieve this with labels – label your program above something useful (say, multiply), read in two integers from the user, and “jal multiply”.
In a real program you may have numerous procedures (functions or methods) being called, sometimes many layers deep, these are called nested procedures and we’re getting there. The goal here is to think from the perspective of the method being called (that is the ‘callee’)– you want to provide a service to a caller without mucking up its data.
So what we need to do is to push the caller data onto a stack (and keep track of what is on the stack) execute our procedure, and then restore the stack.
Conceptually think of a fairly simple problem
So what happens to “a” and “b” in the previous example? Broadly speaking this is also the problem of scope, and differently languages behave differently in terms of how nested functions can see caller variables and so on (and if it can see them, how you access them).
We are working closer to the “metal” than that. We have a piece of data in a specific memory location, but what if some called function wants to use the same memory location but to store something else, after all, if I’m the callee I can’t account for all possible memory states when I get called.
The convention for MIPS $s registers are caller saved, $t registers are callee saved.
some Background Terminology:
program counter: the memory location of the instruction being executed. After executing an instruction you go to current program counter + 4 since instructions are 4 bytes long. (You never work with the PC number directly, but it is stored in the return address).
$ra : is the return address. It’s where you jump to, to return to a previous state (e.g. when you are done your procedure you jr $ra and you are back at the calling function). You need to keep track of what is in the $ra if you want to have many procedures chained together though. Technically jal to a label saves the current program counter (the location of the instruction being executed)
$sp : the stack pointer. When you push things (whatever they are) onto the stack you need to pop them back off when you are done and put them back where they belong.
How do we do this? We want to Push variables onto the stack to save them, and then pop them off when we’re done.
$sp is the stack pointer, it’s supposed to be the memory address that is the top of the stack. The custom is to push onto the stack from larger memory addresses to smaller. You do this by copying something to the next available memory address, and then adjusting the stack pointer.
So to push something onto the stack you save it at memory location $sp-4, then you set
$sp=$sp-4
To Pop something off the top of the stack is $sp (the top element) and then $sp=$sp+4
Simple Example:
Push the contents of register 15 (r15) into the stack
The reason there aren’t ‘push’ and ‘pop’ instructions is because this is a RISC architecture (Reduced Instruction Set) not a CISC (Complex Instruction Set) architecture like your modern computers.
Or perhaps usefully, and this is what allows us to make a nested procedure
Make sure you do not copy and paste the code above you could run into encoding issues because of word.
Combine that program with a labelled procedure that will store a value $s0 into the stack, and that puts in a new line (that’s the program below)
Pay attention to what this does, inside the procedure we save any $s register we want to use by pushing it onto the stack, then we can do whatever we want with that register, and when we finish we pop them back to where they were.
Using what you just learned from saving one variable convert the following program into a called leaf procedure. This program reads two numbers and adds them together.
Notice that this program uses 3 $s variables, you need to make sure each one is preserved, to test that set them to something unique like $s0 =1, $s1 = 2 $s2 =3, call the procedure, the procedure should push the old values on to the stack, run, then pop the values back off. The calling main procedure should receive a value back which it should print to the consoe.
Recursion:
Now we’re going to make a recursive procedure (a procedure that calls itself). This is conceptually very similar to the previous example except the program can have a fairly large stack.
Let’s say we have 3 programs. A calls B, B calls C, C calls D.
A{ B()}; B{C()}; C{D()}; D{something}. The way this actually works is D finishes first, gets popped off the execution stack then C gets the result of D, finishes what it was doing, gets popped off, B gets the result of C, finishes, pops off the stack, then A gets the result of B and finishes.
Recursion is essentially the same, except it’s the same function, just with different parameters at each step. Well, hopefully. If you keep giving it the same parameters, you’ll get an infinite loop.
We will make a simple recursive function, given two integers (s and f) we will have a recursive function that adds all of the integers from s to f
Example in C#:
int mySum (int s, int f){ if (s==f){
return f;
}
else{
return s+mySum(s+1, f);
}
}
CS 340 Milestone One Guidelines and Rubric Overview: For this assignment, you will implement the fundamental operations of create, read, update,
Retail Transaction Programming Project Project Requirements: Develop a program to emulate a purchase transaction at a retail store. This
7COM1028 Secure Systems Programming Referral Coursework: Secure
Create a GUI program that:Accepts the following from a user:Item NameItem QuantityItem PriceAllows the user to create a file to store the sales receip
CS 340 Final Project Guidelines and Rubric Overview The final project will encompass developing a web service using a software stack and impleme
