CS274: Computer Architecture - The MIPS Assembly Language and Instructions

Activity Goals

The goals of this activity are:
  1. To write a simple program using the instructions of the MIPS Assembly Language
  2. To identify the three instruction formats of the MIPS Assembly Language
  3. To relate the relatively few instructions and formats to the regularlity of the language design
  4. To explain the function of a system call
  5. To differentiate between registers and memory

Supplemental Reading

Feel free to visit these resources for supplemental background reading material.

The Activity

Directions

Consider the activity models and answer the questions provided. First reflect on these questions on your own briefly, before discussing and comparing your thoughts with your group. Appoint one member of your group to discuss your findings with the class, and the rest of the group should help that member prepare their response. Answer each question individually from the activity, and compare with your group to prepare for our whole-class discussion. After class, think about the questions in the reflective prompt and respond to those individually in your notebook. Report out on areas of disagreement or items for which you and your group identified alternative approaches. Write down and report out questions you encountered along the way for group discussion.

Model 1: A First Program

A = 5 + 10

Questions

  1. Using your best guess, write comments for each line of code. What do you think they do?
  2. Save and import this program into the MIPS Simulator and run it. What happens?

Model 2: Instructions of the MIPS Instruction Set

Instruction Note Type Example Effect
add Add two registers R add $t1, $t2, $t3 t1 = t2 + t3
subtract Subtract two registers R sub $t1, $t2, $t3 t1 = t2 - t3
add immediate (constant) Add a register and a 16-bit value I addi $t1, $t2, 10 t1 = t2 + 10
load word Load from memory at address register + immediate into a register I lw $s0, 4($sp) s0 = *(sp + 4)
store word Store a register to memory at address register + immediate I sw $s0, 4($sp) *(sp + 4) = s0
load immediate Store a 16-bit value in the lower half of a 32-bit register I li $t0, 100 t0 = 100
load upper immediate Store a 16-bit value in the upper half of a 32-bit register I lui $t0, 100 t0 = (100 << 16)
and Bitwise and two registers R and $t1, $t2, $t3 t1 = t2 & t3
or Bitwise or two registers R or $t1, $t2, $t3 t1 = t2 | t3
nor Bitwise nor two registers R nor $t1, $t2, $t3 t1 = ~(t2 | t3)
and immediate Bitwise and a register and a value I andi $t1, $t2, 4 t1 = the value at the third least significant bit of t2
or immediate Bitwise or a register and a value I ori $t1, $t2, 7 t1 = the value of t2 but the least three significant bits are set to 1
shift left logical Shift the bits of a register left R sll $t1, $t2, 1 t1 = t2 << 1 = t2 * 2
shift right logical Shift the bits of a register right R srl $t1, $t2, 1 t1 = t2 >> 1 = t2 / 2
not ??? ??? ??? ???
branch if equal Move the program counter to its current location (the next instruction to execute) plus the immediate (can be specified as a label) if the registers are equal I beq $t1, $t2, 8 t1 == t2? PC = PC + 4 + 8 : PC = PC + 4
branch if not equal Move the program counter to its current location (the next instruction to execute) plus the immediate (can be specified as a label) if the registers are NOT equal I bne $t1, $t2, 8 t1 != t2? PC = PC + 4 + 8 : PC = PC + 4
set if less than Set the result to 1 if the source register is less than the target register, 0 otherwise R slt $t1, $t2, $t3 t2 < t3 ? t1 = 1: t1 = 0
set if less than immediate Set the result to 1 if the source register is less than the immediate, 0 otherwise I slti $t1, $t2, 1 t2 < 1 ? t1 = 1: t1 = 0
branch if less than ??? ??? ??? ???
jump Set the program counter to the jump target (augmented by the first 4 bits of the current program counter, and assuming the last two bits are 0 for word alignment) J j loop Set PC to the address of loop
jump and link (function call) Same as jump, but set the jr register to the current program counter (the next instruction to execute) to enable a return J jal factorial Set PC to the address of factorial, set $ra to PC+4
jump register (return) Set the program counter to the value in the register R jr $ra Set the PC to the value of $ra

Questions

  1. Why do you think there are three different types of instructions? Why couldn't they all use the same format?
  2. The not instruction does not exist in the language set. What other bitwise instruction could you use to re-create a not behavior?
  3. Similarly, the "branch if less than" instruction blt is a pseudoinstruction, and does not exist as a machine level language. Instead, it translates to other existing MIPS instructions. How could you implement this using two MIPS instructions?
  4. Suppose you have two values in memory, and you wish to add them together. How do you do it?

Model 3: Registers

Register Number Type
$zero 0 0
$at 1 Assembler Temporary
$v0 - $v1 2 - 3 Return Values
$a0 - $a3 4 - 7 Procedure Arguments
$t0 - $t7 8 - 15 Temporary Registers
$s0 - $s7 16 - 23 Saved Registers (procedures must restore these values before returning)
$t8 - $t9 24 - 25 Temporary Registers
$k0 - $k1 26 - 27 Kernel Reigsters
$gp 28 Global Pointer (procedures must restore)
$sp 29 Stack Pointer (procedures must restore)
$fp 30 Frame Pointer (procedures must restore)
$ra 31 Return Address

Questions

  1. What do you think is the difference between the t registers and the s registers?
  2. When might you use a t register as opposed to an s register in your program?

Model 4: Practice: Translating and Encoding Instructions

Every MIPS instruction, no matter what it does, is exactly 32 bits long. Those 32 bits are chopped up into fields, and each field always lives at the same bit positions within its format. Here is where each field sits (bit 31 is the leftmost/most significant bit, and bit 0 is the rightmost):

R Format Field opcode rs rt rd shamt funct
Bit positions 31-26 25-21 20-16 15-11 10-6 5-0
Width (bits) 6 5 5 5 5 6
Meaning always 0 for R type first source register second source register destination register shift amount (0 unless shifting) which R operation (add, sub, ...)

I Format Field opcode rs rt immediate
Bit positions 31-26 25-21 20-16 15-0
Width (bits) 6 5 5 16
Meaning which I instruction source register destination register (usually!) 16-bit constant or offset (sign-extended)

J Format Field opcode address
Bit positions 31-26 25-0
Width (bits) 6 26
Meaning 2 for j, 3 for jal 26-bit word address of the jump target

Worked Example 1 (encode an R type): add $t0, $s1, $s2

  1. Identify the format: add is an R type instruction, so we need opcode, rs, rt, rd, shamt, and funct.
  2. Look up the register numbers: $t0 = 8, $s1 = 17, $s2 = 18 (from the register table above).
  3. Match assembly positions to fields. In assembly, the destination comes first: add rd, rs, rt. So rd = $t0 = 8, rs = $s1 = 17, rt = $s2 = 18.
  4. Look up opcode and funct: R type instructions have opcode = 0, and add has funct = 0x20 = 32.
  5. Convert each field to binary at its required width: opcode = 000000 (6 bits), rs = 17 = 10001 (5 bits), rt = 18 = 10010 (5 bits), rd = 8 = 01000 (5 bits), shamt = 0 = 00000 (5 bits), funct = 32 = 100000 (6 bits).
  6. Concatenate the fields left to right: 000000 10001 10010 01000 00000 100000.
  7. Regroup the 32 bits into groups of 4 for hex: 0000 0010 0011 0010 0100 0000 0010 0000.
  8. Convert each group of 4 to a hex digit: 0x02324020. Done!

Worked Example 2 (encode an I type): lw $t0, 8($sp)

  1. Identify the format: lw is an I type instruction, so we need opcode, rs, rt, and a 16-bit immediate.
  2. Look up the register numbers: $t0 = 8 and $sp = 29.
  3. Match assembly positions to fields: for loads and stores, the register in parentheses is the base address register rs, and the register being loaded is rt. So rs = $sp = 29, rt = $t0 = 8, immediate = 8.
  4. Look up the opcode: lw has opcode 0x23 = 35.
  5. Convert each field to binary: opcode = 35 = 100011 (6 bits), rs = 29 = 11101 (5 bits), rt = 8 = 01000 (5 bits), immediate = 8 = 0000000000001000 (16 bits).
  6. Concatenate: 100011 11101 01000 0000000000001000.
  7. Regroup into fours: 1000 1111 1010 1000 0000 0000 0000 1000.
  8. Convert to hex: 0x8FA80008.

Worked Example 3 (decode): what instruction is 0x012A4022?

  1. Convert each hex digit to 4 bits: 0000 0001 0010 1010 0100 0000 0010 0010.
  2. Take the top 6 bits as the opcode: 000000 = 0. An opcode of 0 means this is an R type instruction, so slice the rest using the R field widths.
  3. Slice the fields: rs = bits 25-21 = 01001 = 9, rt = bits 20-16 = 01010 = 10, rd = bits 15-11 = 01000 = 8, shamt = bits 10-6 = 00000 = 0, funct = bits 5-0 = 100010 = 0x22.
  4. Look up funct 0x22 on your reference sheet: it is sub.
  5. Translate register numbers back to names: 9 = $t1, 10 = $t2, 8 = $t0.
  6. Write the assembly with the destination first: sub $t0, $t1, $t2.

Now you try! These are ordered from easier to harder. Work each one on paper before peeking at the solution.

Problem 1 (easy): Encode addi $t0, $t0, 1 to binary and hex.

Solution
  1. addi is I type with opcode 0x8 = 001000.
  2. rs = source = $t0 = 8 = 01000; rt = destination = $t0 = 8 = 01000 (I type destinations go in rt!).
  3. immediate = 1 = 0000000000000001.
  4. Concatenate: 001000 01000 01000 0000000000000001 = 0010 0001 0000 1000 0000 0000 0000 0001 = 0x21080001.

Problem 2 (easy-medium): Encode and $s0, $t1, $t2 to binary and hex. (and has funct 0x24.)

Solution
  1. R type: opcode = 000000, funct = 0x24 = 100100.
  2. rd = $s0 = 16 = 10000, rs = $t1 = 9 = 01001, rt = $t2 = 10 = 01010, shamt = 00000.
  3. Concatenate in field order (rd is third-from-left in machine code, even though it is first in assembly): 000000 01001 01010 10000 00000 100100.
  4. Regroup: 0000 0001 0010 1010 1000 0000 0010 0100 = 0x012A8024.

Problem 3 (medium): Encode sll $t0, $t1, 4. Careful: shifts are R type, but they use the shamt field, and rs is unused (0).

Solution
  1. opcode = 000000, funct for sll = 0 = 000000.
  2. rs = 0 = 00000 (unused), rt = source = $t1 = 9 = 01001, rd = destination = $t0 = 8 = 01000, shamt = 4 = 00100.
  3. Concatenate: 000000 00000 01001 01000 00100 000000 = 0000 0000 0000 1001 0100 0001 0000 0000 = 0x00094100.

Problem 4 (medium): Suppose $t1 holds the address 0x10010020. What memory address does sw $s0, -12($t1) write to, and what is the machine encoding? (sw has opcode 0x2B.)

Solution
  1. Effective address = base + offset = 0x10010020 + (-12).
  2. -12 in hex is -0xC, so 0x10010020 - 0xC = 0x10010014. That is the address written.
  3. Encoding: opcode = 0x2B = 101011, rs = $t1 = 9 = 01001, rt = $s0 = 16 = 10000.
  4. immediate = -12 as 16-bit two's complement: 12 = 0000000000001100; invert to 1111111111110011; add 1 to get 1111111111110100 = 0xFFF4.
  5. Concatenate: 101011 01001 10000 1111111111110100 = 1010 1101 0011 0000 1111 1111 1111 0100 = 0xAD30FFF4.

Problem 5 (medium-hard): Decode 0x8D0B0004 back into a MIPS assembly instruction.

Solution
  1. Binary: 1000 1101 0000 1011 0000 0000 0000 0100.
  2. opcode = 100011 = 0x23 = lw, so this is I type.
  3. rs = 01000 = 8 = $t0, rt = 01011 = 11 = $t3, immediate = 0000000000000100 = 4.
  4. Assembly: lw $t3, 4($t0).

Problem 6 (challenge): Decode 0x0810000A. What kind of instruction is it, and (assuming the upper 4 bits of PC+4 are 0) what address does it transfer control to?

Solution
  1. Binary: 0000 1000 0001 0000 0000 0000 0000 1010.
  2. opcode = 000010 = 2 = j, so this is J type.
  3. Take the remaining 26 bits (bits 25-0): 00 0001 0000 0000 0000 0000 1010 = 0x10000A.
  4. Multiply by 4 (shift left 2) to restore the byte address: 0x10000A × 4 = 0x400028.
  5. Prepend the upper 4 bits of PC+4 (0000): the target is 0x00400028. So this is j 0x00400028.

Common Pitfalls
  • The destination moves! In assembly, the destination register is written first, but in R type machine code the destination (rd) is the third register field. In I type instructions, the destination is rt, the second register field.
  • Register names are not register numbers. $t0 is register 8, not register 0. Always translate through the register table.
  • Immediates are sign-extended for addi, lw, sw, and branches, so 0xFFF4 means -12, not 65524. (The logical instructions andi and ori zero-extend instead.)
  • Shift amounts go in shamt, not in an immediate field: sll and srl are R type even though they contain a constant.
  • Every instruction is exactly 32 bits. If your concatenation doesn't have exactly 32 bits, one of your fields has the wrong width; pad each field with leading zeros to its full width.

Questions

  1. In Problem 1, the same register $t0 appeared in two different fields. Why is that not a problem for the hardware?
  2. Make up an R type instruction of your own, encode it, and trade with a neighbor to decode each other's work.

Model 5: System Calls

printf("Hello, world!");

Questions

  1. What do you think system call number 4 does, and what do you think system call number 10 does?
  2. Save and import this program into the MIPS Simulator and run it. What happens?

Model 6: Key Formulas and Concepts Recap

Here is a one-page summary of the big ideas from this activity. Keep it handy as a reference!

Key rules of the MIPS instruction set:

Rule Micro-example
Every instruction is exactly 32 bits (one word), in one of just three formats: R, I, or J. add is R, addi/lw/beq are I, j/jal are J
Arithmetic happens only between registers (or a register and an immediate); memory is touched only by loads and stores. To add two values in memory: lw, lw, add, then maybe sw
There are 32 registers, numbered 0-31; $zero (register 0) is always 0. add $t0, $t1, $zero copies $t1 into $t0
The destination register is written first in assembly. sub $t0, $t1, $t2 means t0 = t1 - t2
Loads and stores compute their address as register + constant offset. lw $s0, 4($sp) reads the word at address sp + 4
Immediates are 16 bits, so building a full 32-bit constant takes two instructions. lui $t0, 0xABCD then ori $t0, $t0, 0x5678
Some "instructions" are pseudoinstructions the assembler expands for you. blt $t0, $t1, L becomes slt $at, $t0, $t1 + bne $at, $zero, L
System calls request services from the OS: put the call number in $v0, arguments in $a0, then syscall. li $v0, 1 + syscall prints the integer in $a0; call 10 exits

Instruction formats at a glance:

R:  | opcode(6)=0 | rs(5) | rt(5) | rd(5) | shamt(5) | funct(6) |   e.g. add, sub, and, or, slt, sll, jr
I:  | opcode(6)   | rs(5) | rt(5) |      immediate(16)         |   e.g. addi, lw, sw, beq, bne, li (pseudo)
J:  | opcode(6)   |              address(26)                   |   e.g. j, jal

Glossary:

Term One-line definition
Register A 32-bit storage location inside the processor; MIPS has 32 of them.
Immediate A constant value baked directly into an instruction (16 bits in MIPS I types).
Opcode The top 6 bits of every instruction, telling the processor which operation (or format) it is.
Program Counter (PC) The register holding the address of the instruction being fetched; normally advances by 4.
Word 4 bytes (32 bits): the size of a MIPS register, instruction, and lw/sw transfer.
Pseudoinstruction A convenience instruction (like li, blt, move) the assembler translates into real instructions.
System call A request to the operating system (print, read, exit) made with the syscall instruction.
Label A name for an address in your program, used as a branch or jump target or a data location.
Saved vs. temporary registers $s registers must be preserved across procedure calls; $t registers may be overwritten.

Submission

I encourage you to submit your answers to the questions (and ask your own questions!) using the Class Activity Questions discussion board. You may also respond to questions or comments made by others, or ask follow-up questions there. Answer any reflective prompt questions in the Reflective Journal section of your OneNote Classroom personal section. You can find the link to the class notebook on the syllabus.