I am new to MIPS programming and have been struggling to understand
the MIPS program and how it flows.
Preface
If you want to learn much more deeply about this material and how computer processors work (how they retrieve data, use it with the ALU, and store the data), I advise taking a Computer Organization course (prerequisite being Digital Design which covers basic transistor, logic gate, and single-bit memory components).
I am not very knowledgeable about floating point details in relation to MIPS. We glazed over it in my Computer Organization class.
Binary Review
If you aren't familiar with how to do binary addition, it is similar to regular addition - binary addition uses carry digits (but in binary they are called 'carry' for short). It is crucial to realize that only bits OF THE SAME PLACE VALUE can be added together. Just like lining up decimal points to add numbers in scientific notation, or how adding 33dec+7dec isn't the same as adding 33dec+700dec , 11bin+110bin isn't the same as 11bin+11bin.
Note that 000001bin, for positive integers (negative integers are treated differently in Two's Complement), is the exact same as 1bin. This is similar to how 876dec is the same as 0000000000876dec.
'Carry' is a fancy way of saying 'the next highest place value'; carry is never displayed except sometimes as either the most significant bit of the final result or in bug-testing each place value's full adder. Adding two bits (where both have the same place value and...) where they are both '1' gives an output of 0 for the same place value as both inputs, but a 'carry' (next higher place value) of 1 (which together is 10bin , which is 2dec): 1+1=2, or in binary, 1+1=10bin. Here is a chart of what I mean:
1 0 1 0
+1 +1 +0 +0
-- -- -- --
10 1 1 0
^ ^ ^ ^
carry=1 carry=0 carry=0
These 4 examples above show the basic rules of binary addition and hold
true for each and every place value.
If you include a carry value into each of the additions, remember that
you can split one addition into multiple operations: Instead of trying
to compute 1+10+111, try (1+10)+111; this way you'll only ever deal
with a maximum of two bits at a time, meaning you can use the above
rules.
Note that all the bits being added (at least, looking at any single
example of the four examples) are of the same place value.
If you want more-complicated rules, the result's place value
(as long as it is the same place value as the input bits') will be an
XOR of all the inputs' same place values. Example (where each input
bit has the same place value and the result bit has that same place value):
1
1
+1 1 XOR 1 XOR 1
-- -------------
X1 (the X is a 'don't care'/irrelevant) 1
I don't know how to explain the more-complicated carry rule in words so
I will leave you to examine Full Adder (and as a prerequisite - Half Adder)
circuits and figure that out for yourself.
The rightmost bit is always place value 1, the bit to the left of that being 2,
the bit to the left of place value 2 being place value 4, then 8,
then 16, then 32, etc. You can figure out further place values by
powers: 2n+...+23+22+21+20 = 2n+...+8+4+2+1. The entire binary number itself (e.g. 11001)(not its place values) tells you which place values to add together and which to ignore (which place values to not add).
Two's Complement is used to convert between positive and negative numbers using only binary instead of having +- signs in the final binary representation. E.g. 11bin instead of -1bin. Numbers that use 2's Complement are called signed numbers. Numbers that are always positive are called unsigned numbers.
Overview of MIPS
Anything with a '$' in front of numbers or letters is a register, which is a group of consecutive bits. In MIPS, which is a 32-bit system, each and every register is made of 32 consecutive bits, even including the weird lo and hi registers designed for use with multiplication. In a 32-bit system, you can think of each register as a 32-bit array or as a house with 32 family members, each of whom has their own place in the house.
Adding two registers (e.g. $a0 + $a1) really means adding ('adding' in the grade school sense, no extra fanciness) the two values in each register. If register $a0 has bits representing the number -5 and register $a1 has bits representing the number 9, then $a0+$a1 = (-5)+(9) = 4. In MIPS, the literal (face-value number) '4' would be 'inserted' into a destination register where it can be stored and not just disappear after calculation.
The stack is a subsection of memory. The stack, as well as nearly every other type of memory, isn't made of registers. Registers are very fast. Accessing non-register memory is in the top two slowest instructions that can be done (division, retrieving from memory [i.e. reading] are the slowest).
stackPointer = addressOf"Top"OfStack. Top is in double quotes because the stack grows downward in memory when adding to the stack, making both adding to and removing from the stack confusing at first. This is discussed in code comments below.
The stack is used when you have to overwrite registers that already have important values you don't want to lose.
framePointer = addressOf1stWordOfFrame, where a frame is nearly all the info a single function will need. In a program with nested functions, there will be more than one frame. A single frame could contain all the argument registers and saved variable registers along with a return address, or it could simply contain a return address and nothing else.
Remember that memory is always byte-addressable in MIPS. This means that you can access every single individual byte in memory (and anything larger), but you won't be able to access an exact bit without accessing everything else in its 'housing' byte (the byte in which it exists).
In MIPS, size ('width') of a single register = 1 word = 32 bits = 4 bytes
- The definitions of a 'bit' and a 'byte' never change, but the definition of a 'word' depends on your computer architecture. A 64-bit Operating System will have a word be 64-bits long ('wide').
$0 (specifically for MIPS, not guaranteed in other ISAs, where an ISA is a specific way of interpreting and running machine code, 1s and 0s, on hardware) is ALWAYS guaranteed to have the value 0 (all 32 bits are 0s). Even if you try to write to this register and somehow succeed, the register is electrically connected to 'ground', so register zero will always be hardware 0 unless you have MAJOR issues in your computer that permit nothing else to work. Logic gates don't work correctly when 'ground' retains too much voltage.
$ra = return address register. Think of this as the 'pick up where I left off' or 'temporary home address to return to' register.
$v0 = special function register. Typically, the result of a just-completed function are placed in this specific register. If the result is a longer value like a 64-bit multiplication result, use $v1 as well. When a function 'returns', the function's output is expected to be in this register (or 'these two registers' if the result is 64 bits instead of 32 bits).
- When 'syscall' (giving the Operating System control) happens IMMEDIATELY AFTER $v0, $v0 is checked for having a value between 1 and 16. Each number from 1-16 has a specific purpose: Code 1 is 'print int to console', 2 is 'print float to console', 3 is 'print double to console'
, 4 is 'print string', 5 is 'read int', 6 is ..., 9 is 'sbrk/allocate memory', 10 is 'exit program', 11 is 'print char', 12 is 'read char', 13 is 'open file', 14 is 'read file', 15 is 'write to file', and 16 is 'close file'.
- What happens when syscall happens after $v0 when $v0 DOESN'T have a number between 1 and 16? "Syscall [X] not supported" from the assembler. Idk what else happens.
With the exception of store instructions, MIPS uses the first operand of an instruction as a destination register (where the result is stored - the final step).
Though registers ARE a form of memory, people nearly always mean "non-register memory" when they use the word "memory". "Memory" includes data in the stack.
Common Instructions
sw = store word (INTO memory) = store 4 consecutive bytes into memory. The 1st operand is the data to store INTO memory.
lw = load word (FROM memory) = load 4 consecutive bytes from memoryAddress to memoryAddress+3. The 1st operand is the recipient register for whatever data is selected from memory.
sh = store halfword = store lower half (lower 2 consecutive bytes) of a register into memory (memoryAddress to memoryAddress+1). MemoryAddressByte => Lowest byte in register, memoryAddress+1 => 2ndLowestByteInRegister. Preserves upper half of the word in memory. Same as sw but for the LOWER half of the register's data.
lh = load halfword = load memoryAddressByte and byte above it into lower half of register. (lowest byte in register => stored in memory address byte, 2ndLowestByteInRegister => memoryAddress+1). Preserves upper half of the word in the register.
- There are many other instructions that use halfwords ("h" in the instruction name) and bytes ("b" in the instruction name). They also use lower halves and lower quarters respectively.
la = load (memory) address (of label). 1st operand is recipient register for the memory address of the label (the address being wherever the assembler decided to put it). 2nd operand is the label. E.g. la $t0, FUNC1
- If you know the exact memory address for something (or you have it in a register), there is no need to use this instruction (la).
add = add values from two registers (operands 2 and 3), store result in a possibly different register (operand 1). E.g. add $s0, $s1, $s2 in C code is $s0 = $s1+$s2;
addi = add immediate (value) = add data from a register (2nd operand) together with a literal value (3rd operand), then store it into a register (1st operand).
subi = subtract immediate (value) = subtract data from a register (2nd operand) together with a literal value (3rd operand), then store it into a register (1st operand). Software instruction, not hardware - called a pseudoinstruction. Pseudoinstruction for addi with a negative immediate value.
li = load immediate (value) = Copies your literal value (2nd operand) into a register (1st operand). Pseudoinstruction for either addi $dest, $0, $input or addi $dest, $input, $0 where you choose destination and input.
bne = branch on not equal = if(1stTwoOperandsAreNotEqual){BranchToThirdOperand;}
bgt = branch on greater than = if(1stOperand > 2ndOperand){BranchToThirdOperand;}. Pseudoinstruction (I can't explain how the hardware on this works, but Peter Cordes in the comments probably can).
j = jump (to the provided label)
jal = jump and link = store the next instruction's address into $ra, then jump to the provided label
jr = jump (to 32-bit address provided by) register. MUCH wider jump range than branching and even other jumping instructions.
BE AWARE OF signed vs unsigned instructions like using add instead of addu. Unsigned instructions (e.g. addu) do NOT throw exceptions (i.e. they don't halt the entire program and tell the Operating System 'something's wrong because a number overflowed'). Afaik, programming languages ALWAYS use unsigned instructions (when converted down to assembly) because it's the programmer's responsibility to determine when there's overflow. Why is it left up to the programmer? Because there are enough cases where overflow is actually a feature and not a bug, like using Two's Complement to switch between positive and negative numbers in binary.
Here is a 2-page summary of instructions that I found extremely useful.
Another thing to be aware of that I don't see/hear many people talk of is that MIPS instructions (e.g. addi $sp, $sp, -12) must be word-aligned. Note that this rule doesn't necessarily exist in other ISAs that have much-more-complicated instructions (called CISC ISAs). Remember how I said memory is byte-addressed? A word is 4x bigger than a byte, meaning you don't necessarily have to store/load a word at some byte address that is a multiple of 4. Word-alignment is having imaginary blocks of 4 bytes per block, starting at byte address 0-3, classified as a word. As soon as you cross over into a different 4-byte "block", you occupy more than one word, even if you aren't technically using all 8 bytes. Ensuring ALL instructions are word-aligned lets the computer allow for less accounting for weird jumps (jump exactly +4 bytes. no more. no less.), and hence, faster switching from the current instruction to the next instruction.
- As an example of mandatory word-alignment, I could do "store[orLoad]Word byteAddress1", which would store 4 bytes of data into byte addresses 1, 2, 3, and 4. Afaik, this is fine (there should be a warning) AS LONG AS that data won't be used for an instruction. Proper word-alignment would be "store[orLoad]Word byteAddress0" (stores into 0,1,2,3) or "store[orLoad]Word byteAddress4" (stores into 4,5,6,7).
addi $sp, $sp, -12 #stackPointer = stackPointer-12;
#12 is # of bytes.
#-12 indicates adding 12 bytes of space onto the stack.
#+12 indicates removing ("popping") 12 bytes from the stack.
sw $ra, 8($sp) #Memory[stackPointer+8] = returnAddress;
#Store 4 bytes (i.e. 1 word) of $ra into
# memoryAddressOfItemOn'Top'OfStack (bytes 8-11 away from $sp)
sw $s0, 4($sp) #Memory[stackPointer+4] = saved0;
#Store 4 bytes (i.e. 1 word) of $s0
# into memoryAddressBytes4To7OfStack
sw $a0, 0($sp) #Memory[stackPointer+0] = argument0;
#Store 4 bytes (i.e. 1 word) of $a0
# into memoryAddressBytes0To3OfStack
bgt $a0, $0, L1 #if($a0 > 0){goto labelL1;} else{GoToNextInstructionBelow();}
add $v0, $0, $0 #$v0 = 0+0;
j RTN #jump to instruction at label RTN
L1: #Label L1
addi $t0, $0, 1 #$t0 = 0+1;
#The '1' above is an immediate value (face-value value)
#, not data in a register.
bne $t0, $a0, L2 #if($t0 != $a0){goto labelL2;}
add $v0, $0, $t0 #$v0 = 0+$t0;
#Copies value in $t0 INTO $v0,
# overwriting whatever $v0 originally had.
#$v0 is a special function register that
# the Operating System uses when combined
# with a 'syscall' afterward.
j RTN #jump to instruction at label RTN
L2:
subi $a0, $a0,1 #$a0 = $a0 - +1;
#'+1' is an immediate value.
jal f #Store the address of the instruction below this
# (the next instruction disregarding jumping) into
# $ra, then jump to instruction at label f
add $s0, $v0, $0 #$s0 = $v0+0;
sub $a0, $a0,1 #$a0 = $a0-1;
#I don't think this is legal since '1' is an immediate value...
#However, '$1' would be legal since it's register 1.
jal f #Store the address of the instruction below this
# (the next instruction disregarding jumping) into
# $ra, then jump to instruction at label f
add $v0, $v0, $s0 #$v0 = $v0 + $s0;
RTN:
lw $a0, 0($sp) #$a0 = Memory[stackPointer+0bytes];
#Copy data FROM the stackPointer address TO register $a0
lw $s0, 4($sp) #$s0 = Memory[stackPointer+4bytes];
lw $ra, 8($sp) #$ra = Memory[stackPointer+8bytes];
addi $sp, $sp, 12 #$sp = $sp+12;
#Deallocate (remove) 12 Bytes from stack.
#Doesn't actually erase data in memory.
#$sp is just a marker of available memory for
# the stack to use.
jr $ra #Jump to instruction at (address that's stored in $ra)
#Since $ra was most recently modified by being loaded from memory,
# that's the instruction address that is jumped to.
#Okay it was loaded from memory but what's that value?
# The value was stored at the beginning of label 'f'.
#In which function iteration was it stored and with what value?
# You need to know the original values in the registers.
#NOTE: $ra can be modified by either the jal or lw instructions.
#I THINK $ra is a protected register, meaning you can't simply
#add or subtract or multiply etc to it.
