Lectures

on
MIPS Instruction Set Architecture
We are going to learn

• MIPS Instruction Set

– Types of Instructions

• Register Set
• Memory Organization
– Big Endian Vs Little Endian

• Instruction Formats
• Design Principles
Instructions: Overview
• Language of the machine
• More primitive than higher level languages, e.g., no sophisticated
control flow such as while or for loops
• Very restrictive
– e.g., MIPS arithmetic instructions
• We’ll be working with the MIPS instruction set architecture
– inspired most architectures developed since the 80's
– used by NEC, Nintendo, Silicon Graphics, Sony
– the name is not related to millions of instructions per second !
– it stands for microcomputer without interlocked pipeline
stages !
• Design goals: Maximize performance and minimize
cost and reduce design time
Types of Instructions

• Arithmetic Instructions
– Use only register operand

• Data Transfer Instructions

• Logical Instructions
• Branch Instructions
– Conditional/Unconditional jump instructions
 MIPS Arithmetic
• All MIPS arithmetic instructions have 3 operands
• Operand order is fixed (e.g., destination first)

• Example:

C code: A = B + C

• MIPS code: add $s0, $s1, $s2 compiler’s job to associate

variables with registers
MIPS Arithmetic
• Design Principle 1: simplicity favors regularity.
• Translation: Regular instructions makes the hardware simple!

• Simpler hardware reduces design time and manufacturing cost.

Allowing variable
• Of course this complicates some things... number
of operands would
simplify the assembly
C code: A = B + C + D; code but complicate the
E = F - A; hardware.

MIPS code add $t0, $s1, $s2

(arithmetic): add $s0, $t0, $s3
sub $s4, $s5, $s0

• Performance penalty: high-level code translates to denser

machine code.
 MIPS Arithmetic
• Operands must be in registers – only 32 registers provided
(which require 5 bits to select one register). Reason for small
number of registers:

• Design Principle 2: Smaller is faster. Why?

– Very large number of registers increase the clock cycle time simply
because it takes electronic signals longer when they must travel
farther.
– Smaller is also cheaper!
 Registers vs. Memory
• Arithmetic instructions operands must be in registers
– MIPS has 32 registers
• Compiler associates variables with registers
• What about programs with lots of variables (arrays, structures etc.)?
• Use memory, load/store operations to transfer data from memory to register
• MIPS is a load/store architecture

Control Input
Memory
Datapath Output

Processor I/O
 Memory Organization
• Viewed as a large single-dimension array with access by address
• A memory address is an index into the memory array
• Byte addressing means that the index points to a byte of memory,
and that the unit of memory accessed by a load/store is a byte

0 8 bits of data
1 8 bits of data

2 8 bits of data

3 8 bits of data

4 8 bits of data

5 8 bits of data
6 8 bits of data

...
 Memory Organization
• Bytes are load/store units, but most data items use larger words
• For MIPS, a word is 32 bits or 4 bytes.

0 32 bits of data
4 32 bits of data Registers correspondingly hold 32 bits of data
8 32 bits of data
12 32 bits of data

...

• 232 bytes with byte addresses from 0 to 232-1

• 230 words with byte addresses 0, 4, 8, ... 232-4
– i.e., words are aligned
– Word addresses are multiple of four
Load/Store Instructions
• Load and Store instructions
• Example:

C code: A[8] = h + A[8];

value offset address

MIPS code (load): lw $t0, 32($s3)

(arithmetic): add $t0, $s2, $t0

(store): sw $t0, 32($s3)

• Load word has destination first, store has destination last

• Remember MIPS arithmetic operands are registers, not memory locations
– therefore, words must first be moved from memory to registers using loads
before they can be operated on; then result can be stored back to memory
 Memory Organization:
Big/Little Endian Byte Order
• Computers are divided into two categories based on
the way they address memory locations:
• Big Endian
• Most significant byte is stored in lower address.
• Little Endian
• Least significant byte is stored in lower address.
• E.g. (09AB12CD)hex
•
• Big Endian Little Endian
Address Value Address Value
0 09 0 CD
4 AB 4 12
8 12 8 AB
12 CD 12 09

26/11/2024 12
 So far we’ve learned:

• MIPS
– loading words but addressing bytes
– arithmetic on registers only

• Instruction Meaning

add $s1, $s2, $s3 $s1 = $s2 + $s3

sub $s1, $s2, $s3 $s1 = $s2 – $s3
lw $s1, 100($s2) $s1 = Memory[$s2+100]
sw $s1, 100($s2) Memory[$s2+100]= $s1
 Machine Language
• Instructions, like registers and words of data, are also 32 bits long
– Example: add $t0, $s1, $s2
– registers are numbered, e.g., $t0 is 8, $s1 is 17, $s2 is 18

• Instruction Format R-type (“R” for aRithmetic):

000000 1000 10010 01000 00000 100000

op 1rs rt rd shamt funct
opcode – first second register shift function field -
operation register register destin- amount selects variant
source source ation of operation
operand operand operand

6 bits 5 bits 5 bits 5 bits 5 bits 6 bits

op rs rt rd shamt
funct
MIPS Encoding: R-Type

31 26 25 21 20 1615 11 10 6 5 0

opcode rs rt rd shamt funct

rd

rt
add $4, $3, $2

rs

31 26 25 21 20 1615 11 10 6 5 0
00000000011000100010000000100000
opcode rs rt rd shamt funct

00000000011000100010000000100000

Encoding = 0x00622020
15
 Machine Language

• Consider the load-word and store-word instructions,

– what would the regularity principle allow us to do?
• we would have only 5 or 6 bits to determine the offset from a base register -
too little…

• Design Principle 3: Good design demands a compromise

• Introduce a new type of instruction format
– I-type (“I” for Immediate) for data transfer instructions
– Example: lw $t0, 1004($s2)

100011 10010 01000 0011 1110 1100

6 bits 5 bits 5 bits 16 bits
op rs rt 16 bit offset
 MIPS Encoding: I-Type

31 26 25 21 20 1615 0

opcode rs rt Immediate Value

rt
Immediate
lw $5, 3000($2)

rs

31 26 25 21 20 1615 0
10001100010001010000101110111000
opcode rs rt Immediate Value

10001100010001010000101110111000

Encoding = 0x8C450BB8
17
 MIPS Encoding: I-Type

31 26 25 21 20 1615 0

opcode rs rt Immediate Value

rt
Immediate
sw $5, 3000($2)
rs

31 26 25 21 20 1615 0
10101100010001010000101110111000
opcode rs rt Immediate Value

10101100010001010000101110111000

Encoding = 0xAC450BB8
18
The immediate value is signed
Immediate Operands
• Make operand part of instruction itself!

• Design Principle 4: Make the common case fast

• Example: addi $sp, $sp, 4 # $sp = $sp + 4

001000 1110 1110 000000000000010

1 1 0
6 bits 5 bits 5 bits 16 bits

op r rt 16 bit number
s
 Logical Instructions
• Along with operating on full words there is a
need to process data at the bit level.
• Logical Operations
Shift Logical Left (SLL $S1,$S2,10)
Shift Logical Right (SRL $S1,$S2,10)
AND (AND $S1,$S2,$S3)
OR (OR $S1,$S2,$S3)
NOR (NOR $S1,$S2,$S3)
ANDI (ANDI $S1,$S2,100)
ORI (ORI $S1,$S2,100)
 Shift Operations: shamt: how many positions to shift

op rs rt rd shamt funct
6 bits 5 bits 5 bits 5 bits 5 bits 6 bits
•Shift left logical (SLL $S1,$S2,10) • Shift right logical (SRL $S1,$S2,10)
– Shift left and fill with 0 bits – Shift right and fill with 0 bits
– sll by i bits multiplies by 2i – srl by i bits divides by 2i
(unsigned only)
 AND Operations
• Useful to mask bits in a word
– Select some bits, clear others to 0

• and $t0, $t1, $t2

$t2 0000 0000 0000 0000 0000 1101 1100 0000

$t1 0000 0000 0000 0000 0011 1100 0000 0000

$t0 0000 0000 0000 0000 0000 1100 0000 0000

 OR Operations
• Useful to include bits in a word
– Set some bits to 1, leave others unchanged

or $t0, $t1, $t2

$t2 0000 0000 0000 0000 0000 1101 1100 0000

$t1 0000 0000 0000 0000 0011 1100 0000 0000

$t0 0000 0000 0000 0000 0011 1101 1100 0000

Stored Program Concept
• Instructions are bit sequences, just like data
• Programs are stored in memory
– to be read or written just like data

memory for data, programs,

Processor Memory compilers, editors, etc.

• Fetch & Execute Cycle

– instructions are fetched and put into a special register
– bits in the register control the subsequent actions (= execution)
– fetch the next instruction and repeat
 Control: Conditional Branch
• Decision making instructions
– alter the control flow,
• i.e., change the next instruction to be executed

• MIPS conditional branch instructions:

bne $t0, $t1, LabelI-type

beq $t0, $t1, Labelinstructions

000100 01000 01001 beq $t0, $t1, Label

0000000000011001 (= addr.100)

• Example: if (i==j) h = i + j;
word-relative addressing:
25 words = 100 bytes;
bne $s0, $s1, Label also PC-relative (more…)
add $s3, $s0, $s1
Label: ....
 Addresses in Branch
• Instructions:
bne $t4,$t5,Label Next instruction is at Label if $t4 != $t5
beq $t4,$t5,Label Next instruction is at Label if $t4 = $t5
• I Type Instruction Format:
op rs rt 16 bit offset

• Solution: specify a register (as for lw and sw) and add it to

offset
– use PC (= program counter), called PC-relative addressing, based
on principle of locality: most branches are near current instruction
(e.g., loops and if statements)
 Addresses in Branch

• Further extend reach of branch by observing all MIPS

instructions are a word (= 4 bytes), therefore word-relative
addressing:
• MIPS branch destination address = (PC + 4) + (4 * offset)

Because hardware typically increments

PC early
– so offset = (branch in execute cycle to point to next
destination address – PC – 4)/4
instruction
BEQ/BNE uses I-Type

31 26 25 21 20 1615 0

opcode rs rt Signed Offset Value

(encoded in words, e.g. 4-bytes)
rs
Offset
beq $0, $9, 40 Encoded
by 40/4 =
rt 10

31 26 25 21 20 1615 0
00010000000010010000000000001010
opcode rs rt Immediate Value

00010000000010010000000000001010

Encoding = 0x1009000A
30
MIPS assemble code and corresponding machine
instruction

26/11/2024 Computer Architecture CS F342 31

Control: Unconditional Branch (Jump)

• MIPS unconditional branch instructions:

j Label
• Example:
if (i!=j) beq $s4, $s5, else
h=i+j; add $s3, $s4, $s5
else j exit
h=i-j; else: sub $s3, $s4, $s5
exit: ...
• J-type (“J” for Jump) instruction format
– Example: j Label # addr. Label = 100 word-relative
addressing:
25 words = 100 bytes
000010 00000000000000000000011001
6 bits 26 bits
op 26 bit number
Addresses in Jump
• Word-relative addressing also for jump instructions

J op 26 bit address

• MIPS jump j instruction replaces lower 28 bits of the PC with

A00 where A is the 26 bit address; it never changes upper 4 bits
– Example: if PC = 1011X (where X = 28 bits), it is replaced with
1011A00
– there are 16(=24) partitions of the 232 size address space, each
partition of size 256 MB (=228), such that, in each partition the upper 4
bits of the address is same.
– if a program crosses an address partition, then a j that reaches a
different partition has to be replaced by jr with a full 32-bit address
first loaded into the jump register
– therefore, OS should always try to load a program inside a single
partition
 So far
• Instruction Format Meaning
add $s1,$s2,$s3 R $s1 = $s2 + $s3
sub $s1,$s2,$s3 R $s1 = $s2 – $s3
lw $s1,100($s2) I $s1 = Memory[$s2+100]
sw $s1,100($s2) I Memory[$s2+100] = $s1
bne $s4,$s5,Lab1 I Next instr. is at Lab1 if $s4 !=
$s5
beq $s4,$s5,Lab2 I Next instr. is at Lab2 if $s4 =
$s5
j Exit J Next instr. is at Lab3

• Formats:
R op rs rt rd shamt funct
I op rs rt 16 bit address
J op 26 bit address
 Control Flow

• We have: beq, bne. What about branch-if-less-than?

• New instruction:
if $s1 < $s2 then
$t0 = 1
(1) slt $t0, $s1, $s2 else
$t0 = 0

(2) slti $t0, $s0, 10 # $t0 = 1, if $s0 < 10

• MIPS use beq, bne, slt, slti and a fixed value of 0 in

register $zero to perform all the relative conditions: =, !=, <,
<=, >, >=
• For example (if $a0 >= 1, goto L1),
• slti $t0, $a0, 1 # $t0 = 1 , if $a0 <
1
• beq $t0, $zero, L1 # if $a0 >= 1, goto
L1
 Policy-of-Use Convention for Registers
Name Register number Usage
$zero 0 the constant value 0
$v0-$v1 2-3 values for results and expression evaluation
$a0-$a3 4-7 arguments
$t0-$t7 8-15 temporaries
$s0-$s7 16-23 saved
$t8-$t9 24-25 more temporaries
$gp 28 global pointer
$sp 29 stack pointer
$fp 30 frame pointer
$ra 31 return address

Register 1, called $at, is reserved for the assembler; registers 26-27,

called $k0 and $k1 are reserved for the operating system.
Procedure Calling
• Steps required
1. Place parameters in registers
2. Transfer control to procedure
3. Acquire storage for procedure
4. Perform procedure’s operations
5. Place result in register for caller
6. Return to the place of call
Procedure Call Instructions
• Procedure call: jump and link
jal ProcedureLabel
– Puts the Address of following instruction in $ra
– Jumps to target address

• Procedure return: jump register

jr $ra
– Copies $ra to program counter
– Can also be used for computed jumps
• e.g., for case/switch statements
Procedures

• Example C code:

// procedure adds 10 to input parameter

int main()
{ int i, j;
i = 5;
j = add10(i);
i = j;
return 0;}

int add10(int i)
{ return (i + 10);}
Procedures
• Translated MIPS assembly
• Note more efficient use of registers possible! save register
.text in stack, see
.globl main figure below
add10:
addi $sp, $sp, -4
main: sw $s0, 0($sp)
addi $s0, $0, 5
add $a0, $s0, $0 addi $s0, $a0, 10
argument add $v0, $s0, $0
to callee jal add10 result
control returns here to caller lw $s0, 0($sp)
jump and link restore
add $s1, $v0, $0 addi $sp, $sp, 4
add $s0, $s1, $0 values

jr $ra
li $v0, 10 return
system code
syscall & call to MEMO High address
exit $sp RY
Content of $s0
Low address
MIPS Addressing Modes
1. Immediate addressing
op rs rt Immediate

2. Register addressing
op rs rt rd ... funct Registers
Register

3. Base addressing
op rs rt Address Memor y

Register + Byte Halfword Word

4. PC-relative addressing
op rs rt Address Memor y

PC + Word

5. Pseudodirect addressing
op Address Memor y

PC Word
MIPS Instruction Formats

• Simple instructions – all 32 bits wide

• Very structured – no unnecessary baggage
• Only three instruction formats

R op rs rt rd shamt funct

I op rs rt 16 bit address

J op 26 bit address
 MIPS assembly language
Category Instruction Example Meaning Comments
add add $s1, $s2, $s3 $s1 = $s2 + $s3 Three operands; data in registers

Arithmetic subtract sub $s1, $s2, $s3 $s1 = $s2 - $s3 Three operands; data in registers

add immediate addi $s1, $s2, 100 $s1 = $s2 + 100 Used to add constants
load word lw $s1, 100($s2) $s1 = Memory[$s2 + 100] Word from memory to register
store word sw $s1, 100($s2) Memory[$s2 + 100] = $s1 Word from register to memory
Data transfer load byte lb $s1, 100($s2) $s1 = Memory[$s2 + 100] Byte from memory to register
store byte sb $s1, 100($s2) Memory[$s2 + 100] = $s1 Byte from register to memory
load upper immediate lui $s1, 100 $s1 = 100 * 2
16 Loads constant in upper 16 bits

branch on equal beq $s1, $s2, 25 if ($s1 == $s2) go to Equal test; PC-relative branch
PC + 4 + 100

branch on not equal bne $s1, $s2, 25 if ($s1 != $s2) go to Not equal test; PC-relative
PC + 4 + 100
Conditional
branch set on less than slt $s1, $s2, $s3 if ($s2 < $s3) $s1 = 1; Compare less than; for beq, bne
else $s1 = 0

set less than slti $s1, $s2, 100 if ($s2 < 100) $s1 = 1; Compare less than constant
immediate else $s1 = 0

jump j 2500 go to 10000 Jump to target address

Uncondi- jump register jr $ra go to $ra For switch, procedure return
tional jump jump and link jal 2500 $ra = PC + 4; go to 10000 For procedure call

26/11/2024 Computer Architecture CS F342 45

 • Questions?

26/11/2024 Computer Architecture CS F342 46