AI 302

Embedded Systems
SPRING 2023

Lecture 04 - Instruction Encoding II

Instructor: Dr. Tarek Abdul Hamid
Translating an IF Statement
 Consider the following IF statement:
if (a == b) c = d + e; else c = d – e;
Assume that a, b, c, d, e are in $s0, …, $s4 respectively

 How to translate the above IF statement?

bne $s0, $s1, else

addu $s2, $s3, $s4
j exit
else: subu $s2, $s3, $s4
exit: ...
2 Embedded Systems Dr. Tarek Abdul Hamid
Compound Expression with AND
 Programming languages use short-circuit evaluation

 If first expression is false, second expression is skipped

if (($s1 > 0) && ($s2 < 0)) {$s3++;}

# One Possible Implementation ...

bgtz $s1, L1 # first expression
j next # skip if false
L1: bltz $s2, L2 # second expression
j next # skip if false
L2: addiu $s3,$s3,1 # both are true
next:

3 Embedded Systems Dr. Tarek Abdul Hamid

Better Implementation for AND
if (($s1 > 0) && ($s2 < 0)) {$s3++;}

The following implementation uses less code

Reverse the relational operator
Allow the program to fall through to the second expression
Number of instructions is reduced from 5 to 3
# Better Implementation ...
blez $s1, next # skip if false
bgez $s2, next # skip if false
addiu $s3,$s3,1 # both are true
next:

4 Embedded Systems Dr. Tarek Abdul Hamid

Your Turn . . .
 Translate the IF statement to assembly language

 $s1 and $s2 values are unsigned

bgtu $s1, $s2, next
if( $s1 <= $s2 ) {
move $s3, $s4
$s3 = $s4
next:
}

 $s3, $s4, and $s5 values are signed

bgt $s3, $s4, next
if (($s3 <= $s4) &&
ble $s4, $s5, next
($s4 > $s5)) {
addu $s3, $s4, $s5
$s3 = $s4 + $s5
} next:

5 Embedded Systems Dr. Tarek Abdul Hamid

Load and Store Instructions
 Instructions that transfer data between memory & registers

 Programs include variables such as arrays and objects

 Such variables are stored in memory

 Load Instruction: load

 Transfers data from memory to a register Registers Memory

store

 Store Instruction:

 Transfers data from a register to memory

 Memory address must be specified by load and store

6 Embedded Systems Dr. Tarek Abdul Hamid
Load and Store Word
 Load Word Instruction (Word = 4 bytes in MIPS)

lw Rt, imm16(Rs) # Rt = MEMORY[Rs+imm16]

 Store Word Instruction

sw Rt, imm16(Rs) # MEMORY[Rs+imm16] = Rt

 Base or Displacement addressing is used
 Memory Address = Rs (base) + Immediate16 (displacement)

 Immediate16 is sign-extended to have a signed displacement

Base or Displacement Addressing
Op6 Rs5 Rt5 immediate16
+ Memory Word
Base address

7 Embedded Systems Dr. Tarek Abdul Hamid

Example on Load & Store
 Translate A[1] = A[2] + 5 (A is an array of words)
 Assume that address of array A is stored in register $s0

lw $s1, 8($s0) # $s1 = A[2]

addiu $s2, $s1, 5 # $s2 = A[2] + 5
sw $s2, 4($s0) # A[1] = $s2
 Index of A[2] and A[1] should be multiplied by 4. Why?
Memory
Registers
... ...

$s0 = $16 address of A A[3] A+12

lw
$s1 = $17 value of A[2] A[2] A+8
$s2 = $18 A[2] + 5 A[1] A+4
sw
... A[0] A

...

8 Embedded Systems Dr. Tarek Abdul Hamid

Load and Store Byte and Halfword
 The MIPS processor supports the following data formats:
 Byte = 8 bits, Halfword = 16 bits, Word = 32 bits
 Load & store instructions for bytes and halfwords
 lb = load byte, lbu = load byte unsigned, sb = store byte
 lh = load half, lhu = load half unsigned, sh = store halfword
 Load expands a memory data to fit into a 32-bit register
 Store reduces a 32-bit register to fit in memory

32-bit Register
s sign – extend s s b
0 zero – extend 0 bu
s sign – extend s s h
0 zero – extend 0 hu
9 Embedded Systems Dr. Tarek Abdul Hamid
Load and Store Instructions
Instruction Meaning I-Type Format
lb rt, imm16(rs) rt = MEM[rs+imm16] 0x20 rs5 rt5 imm16
lh rt, imm16(rs) rt = MEM[rs+imm16] 0x21 rs5 rt5 imm16
lw rt, imm16(rs) rt = MEM[rs+imm16] 0x23 rs5 rt5 imm16
lbu rt, imm16(rs) rt = MEM[rs+imm16] 0x24 rs5 rt5 imm16
lhu rt, imm16(rs) rt = MEM[rs+imm16] 0x25 rs5 rt5 imm16
sb rt, imm16(rs) MEM[rs+imm16] = rt 0x28 rs5 rt5 imm16
sh rt, imm16(rs) MEM[rs+imm16] = rt 0x29 rs5 rt5 imm16
sw rt, imm16(rs) MEM[rs+imm16] = rt 0x2b rs5 rt5 imm16

 Base or Displacement Addressing is used

 Memory Address = Rs (base) + Immediate16 (displacement)
 Two variations on base addressing
 If Rs = $zero = 0 then Address = Immediate16 (absolute)
 If Immediate16 = 0 then Address = Rs (register indirect)
Translating a WHILE Loop
 Consider the following WHILE statement:
Memory
i = 0; while (A[i] != k) i = i+1; ...
A[i] A+4×i
Where A is an array of integers (4 bytes per element) ...
A[2] A+8
Assume address A, i, k in $s0, $s1, $s2, respectively A[1] A+4
A[0] A
 How to translate above WHILE statement? ...

xor $s1, $s1, $s1 #i=0

move $t0, $s0 # $t0 = address A
loop: lw $t1, 0($t0) # $t1 = A[i]
beq $t1, $s2, exit # exit if (A[i]== k)
addiu $s1, $s1, 1 # i = i+1
sll $t0, $s1, 2 # $t0 = 4*i
addu $t0, $s0, $t0 # $t0 = address A[i]
j loop
exit: ...
11 Embedded Systems Dr. Tarek Abdul Hamid
Using Pointers to Traverse Arrays
 Consider the same WHILE loop:
i = 0; while (A[i] != k) i = i+1;
Where address of A, i, k are in $s0, $s1, $s2, respectively
 We can use a pointer to traverse array A
Pointer is incremented by 4 (faster than indexing)
move $t0, $s0 # $t0 = $s0 = addr A
j cond # test condition
loop: addiu $s1, $s1, 1 # i = i+1
addiu $t0, $t0, 4 # point to next
cond: lw $t1, 0($t0) # $t1 = A[i]
bne $t1, $s2, loop # loop if A[i]!= k
 Only 4 instructions (rather than 6) in loop body

12 Embedded Systems Dr. Tarek Abdul Hamid

Copying a String
The following code copies source string to target string
Address of source in $s0 and address of target in $s1
Strings are terminated with a null character (C strings)

i = 0;
do {target[i]=source[i]; i++;} while (source[i]!=0);

move $t0, $s0 # $t0 = pointer to source

move $t1, $s1 # $t1 = pointer to target
L1: lb $t2, 0($t0) # load byte into $t2
sb $t2, 0($t1) # store byte into target
addiu $t0, $t0, 1 # increment source pointer
addiu $t1, $t1, 1 # increment target pointer
bne $t2, $zero, L1 # loop until NULL char

13 Embedded Systems Dr. Tarek Abdul Hamid

Summing an Integer Array
sum = 0;
for (i=0; i<n; i++) sum = sum + A[i];

Assume $s0 = array address, $s1 = array length = n

move $t0, $s0 # $t0 = address A[i]

xor $t1, $t1, $t1 # $t1 = i = 0
xor $s2, $s2, $s2 # $s2 = sum = 0
L1: lw $t2, 0($t0) # $t2 = A[i]
addu $s2, $s2, $t2 # sum = sum + A[i]
addiu $t0, $t0, 4 # point to next A[i]
addiu $t1, $t1, 1 # i++
bne $t1, $s1, L1 # loop if (i != n)

14 Embedded Systems Dr. Tarek Abdul Hamid

Addressing Modes
 Where are the operands?
 How memory addresses are computed?
Immediate Addressing
Op6 Rs5 Rt5 immediate16 Operand is a constant

Register Addressing
Op6 Rs5 Rt5 Rd5 sa5 funct6 Operand is in a register
Register

Operand is in memory (load/store)

Base or Displacement Addressing
Op6 Rs5 Rt5 immediate16
+ Byte Halfword Word
Register = Base address

15 Embedded Systems Dr. Tarek Abdul Hamid

Branch / Jump Addressing Modes
Used for branching (beq, bne, …)
PC-Relative Addressing
Op6 Rs5 Rt5 immediate16
+1 Word = Target Instruction
PC30 00

Target Instruction Address

PC30 + immediate16 + 1 00
PC = PC + 4 × (1 + immediate16)

Used by jump instruction

Pseudo-direct Addressing
Op6 immediate26
: Word = Target Instruction
PC4 PC26 00

Target Instruction Address PC4 immediate26 00

16 Embedded Systems Dr. Tarek Abdul Hamid

Jump and Branch Limits
 Jump Address Boundary = 226 instructions = 256 MB
 Text segment cannot exceed 226 instructions or 256 MB
 Upper 4 bits of PC are unchanged
Target Instruction Address PC4 immediate26 00

 Branch Address Boundary

 Branch instructions use I-Type format (16-bit immediate constant)
 PC-relative addressing: PC30 + immediate16 + 1 00

 Target instruction address = PC + 4×(1 + immediate16)

 During assembly: immediate=(Target address – PC)/4, where PC contains

address of next instruction