University of Technology – VNU-HCM 12 August 2021

Representing Instructions
Computer Architecture
• Instructions are encoded in binary
Chapter 2: MIPS – part 2 – Called machine code
• MIPS instructions
– Encoded as 32-bit instruction words
– Small number of formats encoding operation code (opcode),
register numbers, …
– Regularity!
• Register numbers
– $t0 – $t7 are reg’s 8 – 15
– $t8 – $t9 are reg’s 24 – 25
– $s0 – $s7 are reg’s 16 – 23
Adapted from Computer Organization the Hardware/Software Interface – 5th

Computer Engineering – CSE – HCMUT 1 Chapter 2. MIPS - ISA 2

MIPS R-format Instructions R-format Example

op rs rt rd shamt funct
6 bits 5 bits 5 bits 5 bits 5 bits 6 bits op rs rt rd shamt funct
• Instruction fields 6 bits 5 bits 5 bits 5 bits 5 bits 6 bits

– op: operation code (opcode) add $t0, $s1, $s2

– rs: first source register number special $s1 $s2 $t0 0 add
– rt: second source register number
0 17 18 8 0 32
– rd: destination register number
000000 10001 10010 01000 00000 100000
– shamt: shift amount (00000 for now)
– funct: function code (extends opcode) 000000100011001001000000001000002 = 0232402016

Chapter 2. MIPS - ISA 3 Chapter 2. MIPS - ISA 4

Chapter 2 – MIPS Instruction Set Architecture 1

University of Technology – VNU-HCM 12 August 2021

Hexadecimal MIPS I-format Instructions

• Base 16 op rs rt constant or address
– Compact representation of bit strings 6 bits 5 bits 5 bits 16 bits

– 4 bits per hex digit • Immediate arithmetic and load/store instructions

0 0000 4 0100 8 1000 c 1100 – rt: destination or source register number
– Constant: –215 to +215 – 1
1 0001 5 0101 9 1001 d 1101
– Address: offset added to base address in rs
2 0010 6 0110 a 1010 e 1110
• Example: lw $t0, 32($s3)
3 0011 7 0111 b 1011 f 1111
• Example: eca8 6420 35d 19d 8 32
– 1110 1100 1010 1000 0110 0100 0010 0000 opcode $s3 $t0 address

Chapter 2. MIPS - ISA 5 Chapter 2. MIPS - ISA 6

Design Principle MIPS Instructions Format Summary

• Design Principle 4: Good design demands good Instr. Type op rs rt rd shamt function address

compromises add R 0 reg reg reg 0 32d n.a.

– Different formats complicate decoding, but allow 32-bit sub R 0 reg reg reg 0 34d n.a.
instructions uniformly addi I 8d reg reg n.a. n.a. n.a. constant
– Keep formats as similar as possible lw I 35d reg reg n.a. n.a. n.a. address
sw I 43d reg reg n.a. n.a. n.a. address

• R-format: arithmetic instructions

• I-format: data transfer instructions

Chapter 2. MIPS - ISA 7 Chapter 2. MIPS - ISA 8

Chapter 2 – MIPS Instruction Set Architecture 2

University of Technology – VNU-HCM 12 August 2021

Example Stored Program Computers

• Write MIPS code for the following C code, The BIG Picture • Instructions represented
in binary, just like data
then translate the MIPS code to machine code • Instructions and data
stored in memory
A[300] = h + A[300] - 2; • Programs can operate on
• Assume that $t1 stores the base of array programs
– e.g., compilers, linkers, …
A and $s2 stores h • Binary compatibility
allows compiled programs
to work on different
computers
– Standardized ISAs

Chapter 2. MIPS - ISA 9 Chapter 2. MIPS - ISA 10

Logical Operations Shift Operations

• Instructions for bitwise manipulation • shamt: how many positions to shift
• Shift left logical
Operation C Java MIPS – Shift left and fill with 0 bits
Shift left << << sll – sll by i bits multiplies by 2i
Shift right >> >>> srl • Shift right logical
Bitwise AND & & and, andi – Shift right and fill with 0 bits
– srl by i bits divides by 2i (unsigned only)
Bitwise OR | | or, ori
• Example: sll $t2, $s0, 4 # $t2 = $s0 << 4
Bitwise NOT ~ ~ nor
• Useful for extracting and inserting groups of bits 0 0 16 10 4 0
in a word 6 bits 5 bits 5 bits 5 bits 5 bits 6 bits

Chapter 2. MIPS - ISA 11 Chapter 2. MIPS - ISA 12

Chapter 2 – MIPS Instruction Set Architecture 3

University of Technology – VNU-HCM 12 August 2021

AND Operations OR Operations

• Useful to mask bits in a word • Useful to include bits in a word
– Select some bits, clear others to 0 – Set some bits to 1, leave others unchanged
and $t0, $t1, $t2 or $t0, $t1, $t2

$t2 0000 0000 0000 0000 0000 1101 1100 0000 $t2 0000 0000 0000 0000 0000 1101 1100 0000
$t1 0000 0000 0000 0000 0011 1100 0000 0000 $t1 0000 0000 0000 0000 0011 1100 0000 0000

$t0 0000 0000 0000 0000 0000 1100 0000 0000 $t0 0000 0000 0000 0000 0011 1101 1100 0000

Chapter 2. MIPS - ISA 13 Chapter 2. MIPS - ISA 14

NOT Operations Example

• Useful to invert bits in a word • The data table below contains the values for
– Change 0 to 1, and 1 to 0
register $t0 and $t1
a $t0 = 0xAAAAAAAA, $t1 = 0x12345678
• MIPS has NOR 3-operand instruction b $t0 = 0xF00DD00D, $t1 = 0x11111111
– a NOR b == NOT ( a OR b )
• Find the value for $t2 after the following
Register 0: always
nor $t0, $t1, $zero read as zero
sequence of instruction?

$t1 0000 0000 0000 0000 0011 1100 0000 0000 sll $t2, $t0, 44 sll $t2, $t0, 4 srl $t2, $t0, 3
or $t2, $t2, $t1 andi $t2, $t2, -2 andi $t2, $t2, 0xFFEF
$t0 1111 1111 1111 1111 1100 0011 1111 1111

Chapter 2. MIPS - ISA 15 Chapter 2. MIPS - ISA 16

Chapter 2 – MIPS Instruction Set Architecture 4

University of Technology – VNU-HCM 12 August 2021

Conditional Operations Compiling If Statements

• Branch to a labeled instruction if a condition is • C code:
true if (i==j) f = g+h;
– Otherwise, continue sequentially else f = g-h;
• beq rs, rt, L1 – f, g, … in $s0, $s1, …
– if (rs == rt) branch to instruction labeled L1; • Compiled MIPS code:
• bne rs, rt, L1 bne $s3, $s4, Else
– if (rs != rt) branch to instruction labeled L1; add $s0, $s1, $s2
j Exit
• j L1 Else: sub $s0, $s1, $s2
– unconditional jump to instruction labeled L1 Exit: …
Assembler calculates addresses
Chapter 2. MIPS - ISA 17 Chapter 2. MIPS - ISA 18

Compiling Loop Statements Basic Blocks

• C code: • A basic block is a sequence of instructions
while (save[i] == k) i += 1; with
– i in $s3, k in $s5, base address of save in $s6 – No embedded branches (except at end)
• Compiled MIPS code: – No branch targets (except at beginning)
Loop: sll $t1, $s3, 2
add $t1, $t1, $s6 • A compiler identifies basic
lw $t0, 0($t1) blocks for optimization
bne $t0, $s5, Exit
addi $s3, $s3, 1 • An advanced processor can
j Loop accelerate execution of
Exit: …
basic blocks
Chapter 2. MIPS - ISA 19 Chapter 2. MIPS - ISA 20

Chapter 2 – MIPS Instruction Set Architecture 5

University of Technology – VNU-HCM 12 August 2021

More Conditional Operations Branch Instruction Design

• Set result to 1 if a condition is true • Why not blt, bge, etc?
– Otherwise, set to 0 • Hardware for <, ≥, … slower than =, ≠
• slt rd, rs, rt – Combining with branch involves more work per
– if (rs < rt) rd = 1; else rd = 0; instruction, requiring a slower clock
• slti rt, rs, constant – All instructions penalized!
– if (rs < constant) rt = 1; else rt = 0; • beq and bne are the common case
• Use in combination with beq, bne
slt $t0, $s1, $s2 # if ($s1 < $s2)
• This is a good design compromise
bne $t0, $zero, L # branch to L

Chapter 2. MIPS - ISA 21 Chapter 2. MIPS - ISA 22

Signed vs. Unsigned Procedure Calling

• Signed comparison: slt, slti • Steps required
• Unsigned comparison: sltu, sltui – Place parameters in registers
• Example – Transfer control to procedure
– $s0 = 1111 1111 1111 1111 1111 1111 1111 1111 – Acquire storage for procedure
– $s1 = 0000 0000 0000 0000 0000 0000 0000 0001 – Perform procedure’s operations
– slt $t0, $s0, $s1 # signed – Place result in register for caller
• –1 < +1  $t0 = 1
– Return to place of call
– sltu $t0, $s0, $s1 # unsigned
• +4,294,967,295 > +1  $t0 = 0

Chapter 2. MIPS - ISA 23 Chapter 2. MIPS - ISA 24

Chapter 2 – MIPS Instruction Set Architecture 6

University of Technology – VNU-HCM 12 August 2021

Register Usage Procedure Call Instructions

• $a0 – $a3: arguments (reg’s 4 – 7) • Procedure call: jump and link
• $v0, $v1: result values (reg’s 2 and 3) jal ProcedureLabel
• $t0 – $t9: temporaries – Address of following instruction put in $ra
– Can be overwritten by callee
• $s0 – $s7: saved – Jumps to target address
– Must be saved/restored by callee • Procedure return: jump register
• $gp: global pointer for static data (reg 28) jr $ra
• $sp: stack pointer (reg 29) – Copies $ra to program counter
• $fp: frame pointer (reg 30) – Can also be used for computed jumps
• $ra: return address (reg 31) • e.g., for case/switch statements

Chapter 2. MIPS - ISA 25 Chapter 2. MIPS - ISA 26

Stack Address Model Leaf Procedure Example

High address
• C code:
$sp $sp int leaf_example (int g, h, i, j)
{ int f;
$sp f = (g + h) - (i + j);
return f;
}
– Arguments g, …, j in $a0, …, $a3
Low address
– f in $s0 (hence, need to save $s0 on stack)
Empty stack Three elements stack Empty stack – Result in $v0
Chapter 2. MIPS - ISA 27 Chapter 2. MIPS - ISA 28

Chapter 2 – MIPS Instruction Set Architecture 7

University of Technology – VNU-HCM 12 August 2021

Leaf Procedure Example Non-Leaf Procedures

• MIPS code: • Procedures that call other procedures
leaf_example: • For nested call, caller needs to save on the
addi $sp, $sp, -4
sw $s0, 0($sp) Save $s0 on stack stack:
add $t0, $a0, $a1 – Its return address
add $t1, $a2, $a3 Procedure body – Any arguments and temporaries needed after the
sub $s0, $t0, $t1 call
add $v0, $s0, $zero Result
lw $s0, 0($sp) • Restore from the stack after the call
Restore $s0
addi $sp, $sp, 4
jr $ra Return

Chapter 2. MIPS - ISA 29 Chapter 2. MIPS - ISA 30

Non-Leaf Procedure Example Non-Leaf Procedure Example

• C code: • MIPS code:
fact:
int fact (int n) addi $sp, $sp, -8 # adjust stack for 2 items
{ sw $ra, 4($sp) # save return address
sw $a0, 0($sp) # save argument
if (n < 1) return 1; slti $t0, $a0, 1 # test for n < 1
else return n * fact(n - 1); beq $t0, $zero, L1
addi $v0, $zero, 1 # if so, result is 1
} addi $sp, $sp, 8 # pop 2 items from stack
jr $ra # and return
– Argument n in $a0 L1: addi $a0, $a0, -1 # else decrement n
jal fact # recursive call
– Result in $v0 lw $a0, 0($sp) # restore original n
lw $ra, 4($sp) # and return address
addi $sp, $sp, 8 # pop 2 items from stack
mul $v0, $a0, $v0 # multiply to get result
Chapter 2. MIPS - ISA 31 jr $ra #MIPS
Chapter 2. and- ISA return 32

Chapter 2 – MIPS Instruction Set Architecture 8

University of Technology – VNU-HCM 12 August 2021

Local Data on the Stack Memory Layout

• Text: program code
• Static data: global
variables
– e.g., static variables in C,
constant arrays and strings
– $gp initialized to address
allowing ±offsets into this
segment

• Local data allocated by callee • Dynamic data: heap

– e.g., C automatic variables – E.g., malloc in C, new in
Java
• Procedure frame (activation record)
– Used by some compilers to manage stack storage • Stack: automatic storage
Chapter 2. MIPS - ISA 33 Chapter 2. MIPS - ISA 34

Chapter 2 – MIPS Instruction Set Architecture 9