SPIM

SPIM: MIPS emulator.

• Executes assembly source programs.
• Doesn’t execute binaries.
• Not an IDE, write your assembly in an IDE and execute with SPIM.
• Link: https://spimsimulator.sourceforge.net/

Tip: Vim Configuration for Assembly

" Show tabs
set list
" Never expand tabs to spaces
set noexpandtab
" Make tabs take up 8 spaces
set tabstop=8
set shiftwidth=8

MIPS Instructions / Reference

Note: In this class we’ll be learning 32-bit MIPS, not 64-bit MIPS.

MIPS Instructions:

• Instructions are encoded as 32-bit words
• Small number of formats encoding operation code, register numbers, …
• Regularity
• Three types of instructions (R, J, I)
  • Each type is encoded differently.

Note: MIPS Instruction Set

• Stanford MIPS commercialised by MIPS Technologies
• Similar ISAs have a large share of embedded core market
  • e.g., consumer electronics, network/storage, equipment, cameras, printers, vacuums, etc.
  • Embedded: When the CPU is inside the system.
• Remember: MIPS is a 3-register instruction machine
• (When we use an instruction that doesn’t use 3 operands, we’re actually looking at a pseudo-instruction.)

Register Set

Notes:

• $zero is a read-only register.
• $at stands for “assembler temporary”.
  • In general, we can’t/won’t be using $at
• Note how we can only return two values from a function ($v0—$v1)

Registers:

• $t0—$t7: Reg’s 8—15
• $t8—$t9: Reg’s 24—25
• $s0—$s7: Reg’s 16—23

Instructions

Note: Using mult

• Multiplying two number with mult requires two instructions, one to multiply (mult) and another to read the multiplication result from the HI or LO register (mfhi or mflo).
• If the resulting number doesn’t overflow (is less than 32-bits), you can use mflo to get it from the LO register.

What hi and lo contain:

• lo: Contains rs / rt
• hi: Contains rs % rt

Example :

    li  $t1, 2
    # A: Multiplies t0 and t1
    mult  $t0, $t1
    mflo  $t0
    # B: Same thing, using mul
    mul $t0, $t0, $t1

Pseudo-Instructions

Note: move v.s. li

• move moves the value of one register into another, li puts an immediate value directly into a register.

Pseudo-Instructions: Instructions that don’t have a direct hardware implementation.

• Assembler translates them into equivalent real instructions.
• Provided for the convenience of the programmer.

Example: This pseudo-instruction move $t0, $s0 is translated into this real instruction: addu $t0, $zero, $s0

Instruction Formats

R-Format

• op: Opcode
• rs: First source register number
• rt: Second source register number
• rd: Destination register number
• shamt: Shift amount
  • 00000 for now
• funct: Function code
  • extends opcode

J-Format

• op: Opcode
• rs: First source register number
• rt: Second source register number
• imm: Immediate value

I-Format

• op: Opcode
• addr: Address (of a label).
  • The 26 bits are achieved by dropping the high-order 4 bits of the address and the low-order 2 bits (which would always be 00, since addresses are always divisible by 4).

Encoding & Decoding Instructions

Related Notes: Hexadecimal, Number Systems (CS2640)

Example: Encoding an assembly instruction into hexadecimal

add $t0, $t1, $t2

Converting Registers to Binary: $t0: 01000 (rd)

• (Register 8) $t1: 01001 (rs)
• (Register 9) $t2: 01010 (rt)
• (Register 10)

According to the reference table, opcode and func is 0/32, therefore:

• The opcode is 000000
• The func is 100000

As this isn’t a shift instruction, shamt is 000000.

Putting it all together: \begin{aligned} \text{R-Format: }& \text{op $+$ rs $+$ rt $+$ rd $+$ shamt $+$ funct} \\ \text{Binary: }& 0000 0001 0010 1010 0100 0000 0010 0000 \\ \text{Hexadecimal: }& 012A4020 \end{aligned}

Example: Decoding hexadecimal into an assembly instruction \begin{aligned} \text{Hexadecimal: }& 012A4020 \\ \text{First Six Binary Digits: }& 0000 00 \\ \text{Last Six Binary Digits: }& 10 0000 \\ \end{aligned}

• So we know op is 0
• So we know funct is 32

Now that we know the op/fn, we know the type and command, and can convert the rest of the hexadecimal into binary and convert the rest.

More on MIPS Assembly

Assembly Line Format: [ label: ] opcode [ operand(s) ]

• Every instruction must be in a single line.
• You can comment with #

Arithmetic Operations

Design Principle 1: Simplicity favors regularity.

1. Regularity makes implementation simpler
2. Simplicity enables higher performance at lower cost.

Arithmetic Operations: Have three operands.

• Two sources and one destination
• All arithmetic operations have this form.

Example: Arithmetic Operations

# a <- b + c
add a,b,c 

Example: Arithmetic in C and MIPS

f = (g + h) - (i + j)

# t0 <- g + h
add $t0,$s1,$s2
# t1 <- i + j
add $t1,$s3,$s4
# f <- t0 - t1
sub f,$t0,$t1

• Note how we have to handle the order of operations ourselves and split equations into smaller terms.

Register Operands

Design Principle 2: Smaller is faster

Anchor Link: Register Set Reference

Arithmetic instructions use register operands.

MIPS has a 32 \times 32-bit register file.

• Used for frequently-accessed data.
• Numbered 0—31
• Word: Group of 32 bits (4 bytes)
  • Beginning of the word must be a multiple of four.

Assembler Names:

• \$t0—\$t9: Temporary Values
• \$s0—\$s7: Saved variables

Labels and Main

Label: Symbolic name for a memory address. Can be an instruction or data.

• Program execution begins at the location label main.

      .text
main: add $t2,$t0,$t1

Segments and Linker Directives

Segment: Logical part of code that translates to a specific memory location.

Directives: Tell the assembler how to organize data.

Example: Using a label.

count:  .word 0
# end

Example: Using .text

       .text
main:  li  $t0,10
       li  $t1,20
       add $a0,$t0,$t1
# end

• li: Load immediate. Is a pseudo-instruction.
  • The assembler will turn li $t0,10 into addi $t0,$zero,$t0

      .data
      .word n # 32-bit
      .byte nn  # 8 bit
      .ascii  '?' # ASCII string
      .asciiz "$$$" # zero-terminated ASCII string
      .half n # 16-bit
      .space  n # n bytes

More on Using .word

Use the lw (load word) command to load a value from a word into a register.

Use the sw (store word) command to load a value from a register back into a word.

Example: Loading a word into a register

        .data
sumIs:  .asciiz "The sum is "
value1: .word 15
value2: .word 25
sum:    .word 0
        .text
main:
        lw  $t0, value1
        lw  $t1, value2
        # Print string
        la  $a0, sumIs
        li  $v0, 4
        syscall
        # Add integers and store in sum
        add $t2, $t0, $t1
        sw  $t2, sum
        # Print result
        lw  $v0, sum
        li  $v0, 1
        syscall
        # Exit
        li  $v0, 10
        syscall
# End of program

Data Directives

Syscalls

Syscall: Special instruction that interfaces with the I/O subsystem.

• MIPS provides a small set of operating-system-like services through the system call instruction.

Note: More on some syscalls

• print_int: Passes an integer and prints it on the console.
• print_float: Prints a single floating point number.
• print_double: Prints a double precision number.
• print_string: Passes a pointer to a null-terminated string.
• read_int, read_float, read_double: Read an entire line of input up to and including a newline.
• read_string: Same semantics as the UNIX library routine fgets.
  • Reads up to n-1 characters into a buffer and terminates the string with a null byte. If there are fewer characters on the current line, it reads through the newline and again null-terminates the string.
• sbrk: returns a pointer to a block of memory containing n additional bytes
• exit: stops program execution

Example: Using some syscalls

      .data
str:  .asciiz "Enter an integer to double: "

      .text
main:
      # Print a string (syscall 4)
      la  $a0, str # Put address to the string in $a0
      li  $v0, 4
      syscall
      # Read an integer (syscall 5)
      li  $v0, 5
      syscall
      move  $t0, $v0 # Now move the number from $v0 to $t0 
      # Double user's integer
      li  $t1, 2
      mult  $t0, $t1
      mflo  $t0
      # Print the resulting integer (syscall 5)
      move  $a0, $t0
      li  $v0, 1
      syscall
      # Exit Program
      li  $v0, 10
      syscall
# End of program

Template

# This program does nothing and exits gracefully.
  .text
main:
  li  $v0, 10
  syscall
# The end

Example: Adding two numbers

  .data
sumIs:  .asciiz "The sum is "
  .text
main:
  li  $t0, 15
  li  $t1, 25
  # Print string
  la  $a0, sumIs
  li  $v0, 4
  syscall
  # Add integers and print to console
  add $a0, $t0, $t1
  li  $v0, 1
  syscall
# Print newline
  li  $a0, '\n'
  li  $v0, 11
  syscall
  # Exit
  li  $v0, 10
  syscall

Important: Don’t forget to print a newline character before exiting the program!

Branched Statements

beq rt, r, label
bne rd, rs, label

• Branching to a non-existent label will result in a runtime error.
• To turn an if statement into a branched statement, we need to flip the condition.
  • Besides reducing the number of jumps necessary for a simple if statement, it also maintains the order of if and else in the code.

Important: We will not be using the jump instruction.

Example: Basic if in C v.s. MIPS

1. C

if (a != o) {
  // Do output
}

2. MIPS

      # If zero, jump to the endif label
      beqz      $t0, endif
      # Do output
endif:

Example: Basic if in C v.s. MIPS

1. C

if (t0 < 10) {
  // Do output
}

2. MIPS

  # If zero, jump to the endif label
  bge $t0, 10, endif
  # Do output
endif:

Guideline: To work with multiple endif labels, will just add a number to the end (e.g., endif0:, endif1:, etc.)

Example: Branched if in C v.s. MIPS

1. C

if (t0 < 10) {
  // output 1
} else {
  // output 2
}

2. MIPS

      bge      $t0, 10, else
      # output 1
      b endif
else:
      # output 2
endif:

Example: Else-if in C v.s. MIPS

1. C

if (t0 == 0) {
  t0++;
} else {
  t1++;
}

2. MIPS

if: bnez  $0, else
  addi  $t0, 1
  b endif
else: addi  $t1, 1
endif:

While Loop

To loop, we’ll use a register to control the loop

Example: A while statement

       .data
hello: .asciiz "hello\n"
       .text
main:
       li      $t0, 1 # Initialize loop control register
while: bgt     $t0, 10, endw # While loop
       la      $a0, hello
       li      $v0, 4
       syscall
       addi    $t0, 1 # increment loop control register
       b       while
endw:  li      $v0, 10 # End of while loop
       syscall
# end of program

Example: Nesting an if statement inside a while statement

       .data
hello: .asciiz "hello\n"
       .text
main:
       li      $t0, 1 # Initialize loop control register
while: bgt     $t0, 10, endw # While loop
       
       # Print loop counter variable if it is less than 5
       bge     $t0, 5, endif
       move    $a0, $t0
       li      $v0, 1
       syscall
endif:
       
       la      $a0, hello
       li      $v0, 4
       syscall
       addi    $t0, 1 # increment loop control register
       b       while
endw:  li      $v0, 10 # End of while loop
       syscall
# end of program

Example: While-loop in C v.s. MIPS

1. C

int t1=0;
int t0=1;
while (t0 <= 100) {
  t1 += t0;
  t0++;
}

2. MIPS

  li  $t1, 0
  li  $t0, 1
while:  bgt $t0, 100, endw
  addi  $t1, $t1, $t0
  addi  $t0, 1
  b while
endw:

More on Less-Than or Greater-Than

These commands are used by bge, bgt, ble, and blt

• seq
• sne
• sge
• sgt
• sle
• slt

Masking Bits

Relevant Notes:

Example: Checking if a number is even using a mask

  li  $t1, 1    # Mask the LSBIT
  and $t2, $t0, $t1
  # If $t2 is zero, then t0 is even
  bnez  $t2, endif
  # t0 is even, do whatever.
endif: 

Example: Checking if a number is divisible by four

  li  $t1, 3    # Mask last two LSBITS (this is 11 in binary)
  and $t2, $t0, $t1
  # If $t2 is zero, then t0 is divisible by four
  bnez  $t2, endif
  # t0 is divisble by 4 (continue calculations here)
endif: 

• (If you list out every possible value for 4 bits, you’ll be able to verify this.)

Note: MSBIT Mask: 0x8000000

• (Use this to check if a signed integer is negatie)

Signed Integers

By default, integers are signed,

• To use an unsigned integer, use the unsigned instruction variants.

Beware: Unsigned operations don’t generate traps on overflow, while signed operations will generate traps on overflow.

Example: Converting a C Program to MIPS

Example: Translating C to MIPS

1. C

#include <stdio.h>
int sum;
int n = 100;
int main()
{
  register int i = 1;
  sum = 0;
  while (i <= n) {
    sum += i;
    i++;
  }
  printf("%d\n", sum);
}

2. One-to-one conversion to MIPS

  .data
sum:  .word 0
n:  .word 100
  .text
main:
  li  $t0, 1  # t0: i
  sw  $zero, sum
  lw  $t1, n
while:  bgt $t0, $t1, endw
  # sum += i
  lw  $t2, sum
  add $t2, $t2, $t0
  sw  $t2, sum
  # i++
  addi  $t0, $t0, 1
  b while
endw: lw  $a0, sum
  li  $v0, 1
  syscall
  # Exit
  li  $v0, 10
  syscall
# End of program

• This code is very inefficient, it reads and writes to memory excessively.

3. MIPS (Better)

  .data
sum:  .word 0
n:  .word 100
  .text
main:
  li  $t0, 0
  lw  $t1, n
  li  $t2, 1
while:  bgt $t2, $t1, endw
  add $t0, $t0, $t2
  addi  $t2, $t2, 1
  b while
endw: sw  $t0, sum
  lw  $a0, sum
  li  $v0, 1
  syscall
  # Exit
  li  $v0, 10
  syscall
# End of program

• This is not a one-to-one translation of the C code, but it only writes to memory once, making it much more efficient.

4. Or, you could use the explicit form: n(n+1)/2 so that the program is O(1) instead of O(n)

  .data
sum:  .word 0
n:  .word 100
  .text
main:
  # t0 <- n(n+1)/2
  lw  $t0, n
  addi  $t1, $t0, 1 # n + 1
  mul $t0, $t0, $t1 # * (n + 1)
  sra $t0, $t0, 1 # / 2
  # Print and exit
  sw  $t0, sum
  lw  $a0, sum
    li  $v0, 1
    syscall
    li  $v0, 10
  syscall
# End of program