The MIPS Instruction Set Architecture
The MIPS Register Structure
◼ Thirty-two, 32-bit, registers.
◼ Each register has a unique identifier.
◼ Registers are grouped logically to support specific functions.
Name Number Use
$zero 0 The constant value 0
$at 1 Assembler temporary (reserved by
Assembler to handle large constants)
$v0 - $v1 2-3 Function results and expression
evaluation
$a0 - $a3 4-7 Arguments (function parameters)
$t0 - $t7 8 - 15 Temporary values
$s0 - $s7 16 - 23 Saved temporary values
$t8 - $t9 24 - 25 Temporary values
$k0 - $k1 26 - 27 Reserved for OS Kernel
$gp 28 Global pointer
$sp 29 Stack pointer
$fp 30 Frame pointer
$ra 31 Return address
Instruction Execution
◼ All instructions are executed in two phases:
◼ Fetch.
◼ Execute.
◼ Instruction fetch.
◼ IR Memory [PC].
◼ Increment PC.
◼ Instruction execute.
◼ Decode instruction.
◼ Fetch operand(s).
◼ Execute operation.
◼ Store the result if the instruction generates one.
The instruction register (IR) is used to hold the instruction that is currently being
executed.
A program counter (PC) is a register in a computer processor that contains the
address (location) of the instruction being executed
Representing Instructions Inside the
Computer
◼ Instructions are represented as sequences of binary code.
◼ In the MIPS architecture, each instruction is stored as a single 32-bit
word. This simplifies the memory interface and the instruction decode
logic.
◼ Some processors (e.g. MC68000, IA-32) support variable-length
instructions.
◼ Instructions are divided into fields, each encoding a part of the
instruction.
◼ Opcode
◼ Source registers
◼ Destination registers
◼ Immediate operands
◼ Etc…
MIPS Instruction Formats
◼ The MIPS uses three instruction formats R-Type, I-Type, and J-Type.
◼ Different formats are needed to encode different types of instructions
(e.g. arithmetic, logical, memory access, branch, …).
Opcode rs rt rd shamt funct R-Type
6 bits 5 bits 5 bits 5 bits 5 bits 6 bits
Opcode rs rt address I-Type
6 bits 5 bits 5 bits 16 bits
Opcode address J-Type
6 bits 26 bits
Translating MIPs language into
Machine language (Binary)
Opcode rs rt rd shamt funct R-Type
6 bits 5 bits 5 bits 5 bits 5 bits 6 bits
◼ op: Basic operation of the instruction, traditionally called the
opcode (0 for R-Type).
◼ rs: The first register source operand.
◼ rt: The second register source operand.
◼ rd: The register destination operand. It gets the result of the
operation.
◼ shamt: Shift amount. The field contains zero except for shift
instructions.
◼ funct: Function. This field, often called the function code,
selects the specific variant of the operation in the op field.
Encoding a MIPS Instruction
Encoding: Given the instruction in machine code, write it in assembly code.
add
Opcode rs rt rd shamt funct
000000 10001 10010 01000 00000 100000 R-Type
6 bits 5 bits 5 bits 5 bits 5 bits 6 bits
◼ add $t0,$s1,$s2 # add rd, rs, rt
◼ opcode = 0x0
◼ rs = 0x11 = 1710 = $s1
◼ rt = 0x12 = 1810 = $s2
◼ rd = 0x08 = 810 = $t0
◼ shamt = 0x0 = not used
◼ funct = 0x20 = 3210
◼ The MIPS processor uses the opcode field to identify
instructions and distinguish between different instruction
formats.
Translating MIPs language into
Machine language (Binary)
From Assembly to Machine language
Key MIPS R2000 Instructions
◼ Arithmetic
◼ ADD, SUB, ADDI, MULT, MULTU, DIV, DIVU (U:unsigned)
◼ Logical
◼ AND, OR, NOR, ANDI, ORI, SLL, SRL
◼ Data Transfer
◼ LW, SW, LH, SH, LB, SB, LUI, MFHI, MFLO
◼ Compare
◼ SLT, SLTI
◼ Control Flow
◼ BEQ, BNE, J, JR, JAL
Basic Arithmetic Instructions
◼ We already know about ADD and SUB instructions (R-Type).
◼ ADD $TO,$T1,$T2 # $T0 $T1 + $T2
◼ SUB $S3,$S4,$S5 # $S3 $S4 - $S5
◼ The ADDI instruction (I-Type) is used to add a signed constant
to the contents of a register.
◼ ADDI $S1,$S2,100 # $S1 $S2 + 100
◼ ADDI $SP,$SP,-4 # $SP $SP - 4
Note: addi $t0, $t0, -1 #decrement $t0 (no subi)
Compiling a Complex Assignment
◼ Consider the following assignment from a C (or C++) program:
◼ f = (g + h) – (i + j)
◼ Keeping in mind that MIPS instructions can only perform a single
operation at a time, what would a MIPS compiler produce?
◼ Assume f, g, h, i, and j are associated with registers $s0, $s1, $s2,
$s3, $s4.
ADD $T0,$S3,$S4 # $T0 $S3 + $S4
ADD $T1,$S1,$S2 # $T1 $S1 + $S2
SUB $S0,$T1,$T0 # $S0 $T1 – $T0
Multiplication and Division
◼ Multiplication (R-type)
◼ MULT $S2,$S3 # Hi,Lo = $S2 * $S3
◼ MULTU $S2,$S3 # Hi,Lo = $S2 * $S3 (unsigned)
◼ The 64-bit product is stored in two, 32-bit registers called Hi and Lo.
The Hi and Lo registers are accessed through special instructions (MFHI
and MFLO) that move the contents of the Hi/Lo registers to a
destination register, respectively.
Multiplication and Division
◼ Division (R-type)
◼ DIV $S2,$S3 # Hi = remainder; Lo = quotient
◼ DIVU $S2,$S3 # Hi = remainder; Lo = quotient
◼ Overflow and divide-by-zero conditions must be computed in software.
Logical Instructions
◼ AND (R-Type)
◼ AND $S1,$S2,$S3 # $S1 = $S2 & $S3
◼ OR (R-Type)
◼ OR $S1,$S2,$S3 # $S1 = $S2 | $S3
◼ NOR (R-Type)
◼ NOR $S1,$S2,$S3 # $S1 = ~($S2 | $S3)
◼ ANDI (I-Type)
◼ ANDI $S1,$S2,100 # $S1 = $S2 & 100
◼ ORI (I-Type)
◼ ORI $S1,$S2,100 # $S1 = $S2 | 100
Logical Instructions (2)
Shift Instructions
◼ Shift Left Logical (R-Type)
◼ SLL $S1,$S2,16 # $S1 = $S2 << 16
◼ Vacated bits are filled with zeros. shamt: how many positions to shift
10110101011011100100011110101011 $S2 Before
01000111101010110000000000000000 $S1 After
◼ Shift Right Logical (R-Type)
◼ SRL $S1,$S2,23 # $S1 = $S2 >> 23
◼ Vacated bits are filled with zeros.
10110101011011100100011110101011 $S2 Before
00000000000000000000000101101010 $S1 After
Data Transfer Instructions
◼ The load word (LW) and store word (SW) instructions (I-
Type) are used to transfer 32-bit words between the
processor and memory.
◼ Addresses are specified as an offset/base register
pair. The address is formed by adding the constant
offset (sign extended) to the contents of the base
register.
◼ LW $T1,32($T3) # $T1 Mem[$T3 + 32]
◼ SW $T5,-16($SP) # Mem[$SP – 16] $T5
Data Transfer Instructions
◼ Load and store half-word instructions (I-Type) are used to transfer
16-bit half words between the processor and memory.
LH $T2,16($GP) # $T2[15..0] Mem[$GP + 16]
# The halfword is sign-extended
SH $S4,-32($SP) # Mem[$SP–32] $S4[15..0]
◼ Load and store byte instructions (I-Type) are used to transfer 8-bit
bytes between the processor and memory.
LB $T2,-8($GP) # $T2[7..0] Mem[$GP - 8]
# The byte is sign-extended.
SB $S4,24($SP) # Mem[$SP+24] $S4[7..0]
Data Transfer Instructions
◼ The Load Upper Immediate (I-Type) instruction is used to initialize
the upper 16 bits of a register with a constant.
◼ Lower 16 bits of the register are set to zero.
◼ LUI $S4, 255 # $S4[31..16] = 255;
# $S4[15..0] = 0
◼ How can we use the LUI instruction to initialize a register with a
32-bit constant?
◼ Example: Initialize $T3 with 0xFAFAFBFB.
LUI $T3,0xFAFA # $T3 = 0xFAFA0000
ORI $T3,$T3,0xFBFB # ORI zero-extend the constant
# $T3 = 0xFAFAFBFB
Data Transfer Instructions
◼ The MFHI and MFLO instruction (R-Type) are used to move the
contents of the HI and LO registers to a destination register,
respectively.
◼ The HI and LO registers are set by the multiply and divide
instructions.
◼ MFHI $T5 # $T5 HI
◼ MFLO $T2 # $T2 LO
Compiling an Assignment With a
Memory Operand
◼ Consider the following assignment: g = h + A[7].
◼ Assume g and h are stored in registers $S1 and $S2, and the starting
(base) address of array A is stored in register $S3.
◼ What will the compiler generate?
LW $T0,28($S3) # $T0 Mem[$S3+28]
ADD $S1,$S2,$T0 # $S1 $S2 + $T0
◼ Why is the offset = 28?
◼ Memory is byte-addressable, but is organized as 32-bit words. That is
why the offset = 7 × 4 = 28.
◼ All memory addresses (of word-sized data) must be word aligned
(multiple of 4).
More Memory Assignments
◼ Assuming variable h is stored in register $S2 and the base address
of array A is in $S3, what is the MIPS assembly code for the
following assignment: A[12] = h + A[8]?
LW $T0,32($S3) # $T0 Mem[$S3+32]
ADD $T0,$S2,$T0 # $T0 $S2 + $T0
SW $T0,48($S3) # Mem[$S3+48] $T0
Control-Flow Instructions
◼ The MIPS instruction set includes a number of conditional and
unconditional branch instructions for changing program control-flow.
◼ Conditional branch instructions.
◼ BEQ reg1,reg2,label # I f reg1 == reg2,goto label
◼ BNE reg1,reg2,label # if reg1 != reg2, goto label
◼ Unconditional branch (jump) instructions.
◼ J label # goto label
◼ JR reg # goto address stored in reg
Compiling if-then-else Statements
◼ In the following C++ conditional statement, assume variables f, g,
h, i, and j, are associated with registers $S0, $S1, $S2, $S3, and
$S4, respectively. What is the corresponding assembly code?
if (i == j) {
f = g + h;
}
else {
f = g – h;
}
BEQ $S3,$S4,TRUE BNE $S3,$S4,ELSE
SUB $S0,$S1,$S2 ADD $S0,$S1,$S2
J EXIT J EXIT
TRUE: ADD $S0,$S1,$S2 ELSE: SUB $S0,$S1,$S2
EXIT: EXIT:
The Compare Instruction
◼ The MIPS instruction set includes a compare instruction
(R-Type) that is commonly used in conjunction with conditional
branch instructions.
◼ SLT $T0,$S3,$S4 # if ($S3 < $S4) $T0 = 1
# else $T0 = 0
◼ The result (1 or 0) substitutes for a condition code flag.
◼ A compare-immediate instruction (I-Type) is also part of the
MIPS instruction set.
◼ SLTI $T0,$S3,68 # if ($S3 < 68) $T0 = 1
# else $T0 = 0
◼ Since comparisons are frequently made with the number zero,
register $ZERO is commonly used for this purpose.
Compiling if-then-else Statements (2)
◼ If variables a, b, f, g and h are associated with registers $S0, $S1,
$S2, $S3 and $S4, respectively, what is the assembly code that
gets generated for the following C++ statement:
if (a < b) { SLT $T0,$S0,$S1
f = g + h; BEQ $T0,$ZERO,ELSE
} ADD $S2,$S3,$S4
else { J EXIT
f = g – h; ELSE: SUB $S2,$S3,$S4
} EXIT:
Branch instructions are commonly
used to implement loops
C Code
//Add the numbers from 0 to 9
Int sum=0;
Int i;
For(i=0;i<10;i++) { MIPS assembly code
Sum=sum+i; #$s0=i, $s1=sum
} addi $s1, $0, 0
add $s0, $0, $0
addi $t0, $0, 10
For: BEQ $s0,$t0,exit
ADD $S1,$S1,$S0
ADDi $S0,$S0,1
J For
exit:
Branch instructions are commonly
used to implement loops
Branch instructions are commonly
used to implement loops
Branch instructions are commonly
used to implement loops
To place the int sum, coeffs[100];
address of
an array or sum = 0;
a variable in for (i = 0; i < 100; i++) {
a register sum = sum + coeffs[i];
}
ADDI $R1,$ZERO,coeffs # $R1 &(coeffs[0])
ADDI $R2,$ZERO,sum # $R2 &sum
ADDI $R3,$ZERO,100 # $R3 100
ADD $R4,$ZERO,$ZERO # $R4 i; initialize to zero
ADD $R5,$ZERO,$ZERO # $R5 temp; initialize to zero
LOOP: BEQ $R3,$R4,EXIT # if (i = = 100) exit the loop
LW $R6,0($R1) # $R6 coeffs[i]
ADD $R5,$R5,$R6 # temp temp + coeffs[i]
ADDI $R1,$R1,4 # increment $R1
ADDI $R4,$R4,1 # increment i
J LOOP # goto LOOP
EXIT: SW $R5,0($R2) # sum temp
Compiling while Loops
◼ In the following C++ while loop, assume variables i, j, and k are
associated with registers $S3, $S4, and $S5, respectively; and
that the base address of array SAVE is stored in register $S6. What
is the corresponding assembly code?
while (SAVE[i] == k) {
i = i + j; 4*i +save
}
LOOP: ADD $T1,$S3,$S3
LOOP: SLL $T1,$S3,2
ADD $T1,$T1,$T1
ADD $T1,$T1,$S6
ADD $T1,$T1,$S6
LW $T0,0($T1)
LW $T0,0($T1)
BNE $T0,$S5,EXIT
BNE $T0,$S5,EXIT
ADD $S3,$S3,$S4
ADD $S3,$S3,$S4
J LOOP
J LOOP
EXIT:
EXIT:
Comparison Instructions
MIPS Addressing Modes
◼ Immediate Addressing Opcode rs rt address
6 bits 5 bits 5 bits 16 bits
◼ Operand is a 16-bit constant.
◼ Used with I-type instructions.
◼ ADDI $S0,$V0,525 # ADDI rt, rs, const
Opcode rs rt rd shamt funct R-Type
◼ Register Addressing
6 bits 5 bits 5 bits 5 bits 5 bits 6 bits
◼ Operand is a register
◼ Used with R-type and I-type instructions.
◼ ADD $T0,$S0,$S1 # ADD rd, rs, rt
◼ Base or Displacement Addressing
◼ Operand is at a memory location whose address is the sum of a
base register and a constant, 16-bit, offset.
◼ Used with I-type instructions.
◼ LW $T0,32($SP) # LW rt, const(rs)
MIPS Addressing Modes
◼ PC-Relative Addressing
◼ Branch address is the sum of the PC (actually PC+4) and a 16-bit constant
in the instruction.
◼ Constant represents a word offset. When computing the target address,
the offset should first be multiplied by four.
◼ Used with I-type instructions.
◼ BNE $T0,$T1,LABEL # if($T0 != $T1) $PC = $PC +4+ (LABEL<<2)
Opcode rs rt address
6 bits 5 bits 5 bits 16 bits
◼ Pseudo-direct Addressing
◼ Jump address is the 26 bits (representing a word address) of the
instruction concatenated with the upper bits of the PC (after being
multiplied by four).
◼ Used with J-type instructions.
◼ JAL my_sub # $PC = $PC:(my_sub << 2)
Opcode address J-Type
6 bits 26 bits
PC-Relative Addressing
◼ Example:
Assume this beq instruction resides at memory address
10080000 (hex), and the address of the label Exit is 10080010 (hex).
◼ beq $s1,$s2, Exit
◼ distance in bytes = address of label Exit – (PC+4) = 10080010 –
(10080000 +4) = 12
◼ distance in words = 12 / 4 = 3 (this is what is put into the 16-bit
field)
◼ If the branch is not taken the next value of PC is PC+4. If it is taken,
the next value of PC will be 3x4 + (PC+4) = 10080010 (hex) which is
the address of the label Exit.
Design Principles (covered implicitly)
◼ Simplicity flavors regularity Hardware for a variable number of
operands is more complicated than hardware for fixed number
of operands. Requiring every instruction to have exactly three
operands conforms to the philosophy of keeping hardware
simple.
◼ Smaller is Faster Larger number of register increases clock
cycle time because it takes more time for electronic signals to
travel farther
◼ Make the common case fast Constant Operands occur
frequently, and by including constants inside arithmetic
instructions, they are much faster then if constants were
loaded from memory.
◼ Good Design needs compromise The compromise between
providing for larger addresses and constants in instructions and
keeping all instructions the same length.
Using a Variable Index Array
◼ Assuming variables g, h, and i are associated with registers
$S1, $S2, and $S4, respectively, and that the base address for
array A is stored in register $S3, what is the MIPS assembly
code for the following assignment: g = h + A[i]?
ADD $T1,$S4,$S4 # $T1 = 2 * i
ADD $T1,$T1,$T1 # $T1 = 4 * i
ADD $T1,$T1,$S3 # $T1 = 4*i + $S3
LW $T0,0($T1) # $T0 = A[i]
ADD $S1,$S2,$T0 # g = h + A[i]
Condition Codes
◼ A collection of flags that track the results of previous instruction
for use by subsequent conditional branch instructions.
◼ Typically stored in a special condition code register or a status
register.
◼ Common condition code flags
◼ N (negative) = 1 if result is negative; 0 otherwise.
◼ Z (zero) = 1 if result is zero; 0 otherwise.
◼ V (overflow) = 1 if arithmetic overflow occurs; 0 otherwise.
◼ C (carry) = 1 if operation results in carry-out; 0 otherwise.
◼ Branch>0 instruction tests N and Z flags.
◼ TRUE if (N=0 AND Z=0); branch is said to be “taken”.
◼ FALSE if (N=1 OR Z=1); branch is said to be “not taken”.