Control Flow and Arrays

lecture 12
 Presentation Outline
 Control Flow: Branch and Jump Instructions

 Translating If Statements and Boolean Expressions

 Arrays

 Load and Store Instructions

 Translating Loops and Traversing Arrays

 Addressing Modes

Control Flow and Arrays COE 301 – KFUPM slide 2

 Control Flow
 High-level programming languages provide constructs:
 To make decisions in a program: IF-ELSE

 To repeat the execution of a sequence of instructions: LOOP

 The ability to make decisions and repeat a sequence of

instructions distinguishes a computer from a calculator

 All computer architectures provide control flow instructions

 Essential for making decisions and repetitions

 These are the conditional branch and jump instructions

Control Flow and Arrays COE 301 – KFUPM slide 3

 MIPS Conditional Branch Instructions
 MIPS compare and branch instructions:
beq Rs, Rt, label if (Rs == Rt) branch to label
bne Rs, Rt, label if (Rs != Rt) branch to label
 MIPS compare to zero & branch instructions:
Compare to zero is used frequently and implemented efficiently

bltz Rs, label if (Rs < 0) branch to label

bgtz Rs, label if (Rs > 0) branch to label
blez Rs, label if (Rs <= 0) branch to label
bgez Rs, label if (Rs >= 0) branch to label
 beqz and bnez are defined as pseudo-instructions.
Control Flow and Arrays COE 301 – KFUPM slide 4
 Branch Instruction Format
 Branch Instructions are of the I-type Format:
Op6 Rs5 Rt5 16-bit offset

Instruction I-Type Format

beq Rs, Rt, label Op = 4 Rs Rt 16-bit Offset
bne Rs, Rt, label Op = 5 Rs Rt 16-bit Offset
blez Rs, label Op = 6 Rs 0 16-bit Offset
bgtz Rs, label Op = 7 Rs 0 16-bit Offset
bltz Rs, label Op = 1 Rs 0 16-bit Offset
bgez Rs, label Op = 1 Rs 1 16-bit Offset

 The branch instructions modify the PC register only

 PC-Relative addressing:
If (branch is taken) PC = PC + 4 + 4×offset else PC = PC+4
Control Flow and Arrays COE 301 – KFUPM slide 5
 Unconditional Jump Instruction
 The unconditional Jump instruction has the following syntax:
j label # jump to label
. . .
label:
 The jump instruction is always taken
 The Jump instruction is of the J-type format:
Op6 = 2 26-bit address

 The jump instruction modifies the program counter PC:

PC4 26-bit address 00

multiple
 The upper 4 bits of the PC are unchanged of 4
Control Flow and Arrays COE 301 – KFUPM slide 6
 Translating an IF Statement
 Consider the following IF statement:

if (a == b) c = d + e; else c = d – e;
Given that a, b, c, d, e are in $t0 … $t4 respectively

 How to translate the above IF statement?

bne $t0, $t1, else

addu $t2, $t3, $t4
j next
else: subu $t2, $t3, $t4
next: . . .

Control Flow and Arrays COE 301 – KFUPM slide 7

 Logical AND Expression
 Programming languages use short-circuit evaluation
 If first condition is false, second condition is skipped

if (($t1 > 0) && ($t2 < 0)) {$t3++;}

# One Possible Translation ...

bgtz $t1, L1 # first condition
j next # skip if false
L1: bltz $t2, L2 # second condition
j next # skip if false
L2: addiu $t3, $t3, 1 # both are true
next:
Control Flow and Arrays COE 301 – KFUPM slide 8
 Better Translation of Logical AND
if (($t1 > 0) && ($t2 < 0)) {$t3++;}

Allow the program to fall through to second condition

!($t1 > 0) is equivalent to ($t1 <= 0)
!($t2 < 0) is equivalent to ($t2 >= 0)
Number of instructions is reduced from 5 to 3

# Better Translation ...

blez $t1, next # 1st condition false?
bgez $t2, next # 2nd condition false?
addiu $t3, $t3, 1 # both are true
next:
Control Flow and Arrays COE 301 – KFUPM slide 9
 Logical OR Expression
 Short-circuit evaluation for logical OR
 If first condition is true, second condition is skipped

if (($t1 > 0) || ($t2 < 0)) {$t3++;}

 Use fall-through to keep the code as short as possible

bgtz $t1, L1 # 1st condition true?

bgez $t2, next # 2nd condition false?
L1: addiu $t3, $t3, 1 # increment $t3
next:

Control Flow and Arrays COE 301 – KFUPM slide 10

 Compare Instructions
 MIPS also provides set less than instructions

slt Rd, Rs, Rt if (Rs < Rt) Rd = 1 else Rd = 0

sltu Rd, Rs, Rt unsigned <
slti Rt, Rs, imm if (Rs < imm) Rt = 1 else Rt = 0
sltiu Rt, Rs, imm unsigned <

 Signed / Unsigned comparisons compute different results

Given that: $t0 = 1 and $t1 = -1 = 0xffffffff

slt $t2, $t0, $t1 computes $t2 = 0
sltu $t2, $t0, $t1 computes $t2 = 1

Control Flow and Arrays COE 301 – KFUPM slide 11

 Compare Instruction Formats
Instruction Meaning Format
slt Rd, Rs, Rt Rd=(Rs <s Rt)?1:0 Op=0 Rs Rt Rd 0 0x2a
sltu Rd, Rs, Rt Rd=(Rs <u Rt)?1:0 Op=0 Rs Rt Rd 0 0x2b
slti Rt, Rs, im Rt=(Rs <s im)?1:0 0xa Rs Rt 16-bit immediate
sltiu Rt, Rs, im Rt=(Rs <u im)?1:0 0xb Rs Rt 16-bit immediate

 The other comparisons are defined as pseudo-instructions:

seq, sne, sgt, sgtu, sle, sleu, sge, sgeu

Pseudo-Instruction Equivalent MIPS Instructions

sgt $t2, $t0, $t1 slt $t2, $t1, $t0

subu $t2, $t0, $t1
seq $t2, $t0, $t1
sltiu $t2, $t2, 1
Control Flow and Arrays COE 301 – KFUPM slide 12
 Pseudo-Branch Instructions
 MIPS hardware does NOT provide the following instructions:
blt, bltu branch if less than (signed / unsigned)
ble, bleu branch if less or equal (signed / unsigned)
bgt, bgtu branch if greater than (signed / unsigned)
bge, bgeu branch if greater or equal (signed / unsigned)
 MIPS assembler defines them as pseudo-instructions:

Pseudo-Instruction Equivalent MIPS Instructions

slt $at, $t0, $t1
blt $t0, $t1, label
bne $at, $zero, label
slt $at, $t1, $t0
ble $t0, $t1, label
beq $at, $zero, label
$at ($1) is the assembler temporary register
Control Flow and Arrays COE 301 – KFUPM slide 13
 Using Pseudo-Branch Instructions
 Translate the IF statement to assembly language
 $t1 and $t2 values are unsigned

bgtu $t1, $t2, L1

if($t1 <= $t2) {
move $t3, $t4
$t3 = $t4;
L1:
}
 $t3, $t4, and $t5 values are signed

bgt $t3, $t4, L1

if (($t3 <= $t4) &&
blt $t4, $t5, L1
($t4 >= $t5)) {
$t3 = $t4 + $t5; addu $t3, $t4, $t5
} L1:

Control Flow and Arrays COE 301 – KFUPM slide 14

 Conditional Move Instructions
Instruction Meaning R-Type Format
movz Rd, Rs, Rt if (Rt==0) Rd=Rs Op=0 Rs Rt Rd 0 0xa

movn Rd, Rs, Rt if (Rt!=0) Rd=Rs Op=0 Rs Rt Rd 0 0xb

if ($t0 == 0) {$t1=$t2+$t3;} else {$t1=$t2-$t3;}

bne $t0, $0, L1 addu $t1, $t2, $t3

addu $t1, $t2, $t3 subu $t4, $t2, $t3
j L2 movn $t1, $t4, $t0
L1: subu $t1, $t2, $t3 . . .
L2: . . .
 Conditional move can eliminate branch & jump instructions
Control Flow and Arrays COE 301 – KFUPM slide 15
 Next . . .
 Control Flow: Branch and Jump Instructions

 Translating If Statements and Boolean Expressions

 Arrays

 Load and Store Instructions

 Translating Loops and Traversing Arrays

 Addressing Modes

Control Flow and Arrays COE 301 – KFUPM slide 16

 Arrays
 In a high-level programming language, an array is a
homogeneous data structure with the following properties:
 All array elements are of the same type and size
 Once an array is allocated, its size cannot be modified
 The base address is the address of the first array element
 The array elements can be indexed
 The address of any array element can be computed

 In assembly language, an array is just a block of memory

 In fact, all objects are simply blocks of memory

 The memory block can be allocated statically or dynamically

Control Flow and Arrays COE 301 – KFUPM slide 17
 Static Array Allocation
 An array can be allocated statically in the data segment
 A data definition statement allocates static memory:
label: .type value0 [, value1 ...]
label: is the name of the array
.type directive specifies the size of each array element
value0, value1 ... specify a list of initial values
 Examples of static array definitions:
arr1: .half 20, -1 # array of 2 half words
arr2: .word 1:5 # array of 5 words (value=1)
arr3: .space 20 # array of 20 bytes
str1: .asciiz "Null-terminated string"

Control Flow and Arrays COE 301 – KFUPM slide 18

 Watching Values in the Data Segment

 The labels window is the symbol table

 Shows labels and corresponding addresses

 The la pseudo-instruction loads the address

of any label into a register
Control Flow and Arrays COE 301 – KFUPM slide 19
 Dynamic Memory Allocation
 One of the functions of the OS is to manage memory
 A program can allocate memory on the heap at runtime
 The heap is part of the data segment that can grow at runtime
 The program makes a system call ($v0=9) to allocate memory

.text
. . .
li $a0, 100 # $a0 = number of bytes to allocate
li $v0, 9 # system call 9
syscall # allocate 100 bytes on the heap
move $t0, $v0 # $t0 = address of allocated block
. . .

Control Flow and Arrays COE 301 – KFUPM slide 20

 Allocating Dynamic Memory on the Heap
0x7ffffff
f
Stack Segment

0x1004000 Heap Area

Data Segment
0
0x1000000 Static Area
0

0x0040000 Text Segment

0
0x0000000 Reserved
0
Control Flow and Arrays COE 301 – KFUPM slide 21
 Computing the Addresses of Elements
 In a high-level programming language, an array is indexed
array[0] is the first element in the array
array[i] is the element at index i
&array[i] is the address of the element at index i
&array[i] = &array + i × element_size
 For a 2D array, the array is stored linearly in memory
matrix[Rows][Cols] has (Rows × Cols) elements
&matrix[i][j] = &matrix + (i×Cols + j) × element_size
 For example, to allocate a matrix[10][20] of integers:
matrix: .word 0:200 # 200 words (initialized to 0)
&matrix[1][5] = &matrix + (1×20 + 5)×4 = &matrix + 100

Control Flow and Arrays COE 301 – KFUPM slide 22

 Element Addresses in a 2D Array
Address calculation is essential when programming in assembly

COLS

0 1 … j … COLS-1
0
1
…
ROWS

i
…
ROWS-1

&matrix[i][j] = &matrix + (i×COLS + j) × Element_size

Control Flow and Arrays COE 301 – KFUPM slide 23

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

 Programs include variables such as arrays and objects

 These variables are stored in memory

load
 Load Instruction:
Registers Memory
 Transfers data from memory to a register
store
 Store Instruction:

 Transfers data from a register to memory

 Memory address must be specified by load and store

Control Flow and Arrays COE 301 – KFUPM slide 24
 Load and Store Word
 Load Word Instruction (Word = 4 bytes in MIPS)
lw Rt, imm(Rs) # Rt  MEMORY[Rs+imm]
 Store Word Instruction
sw Rt, imm(Rs) # Rt  MEMORY[Rs+imm]
 Base / Displacement addressing is used
 Memory Address = Rs (base) + Immediate (displacement)
 Immediate16 is sign-extended to have a signed displacement

Base or Displacement Addressing

Op6 Rs5 Rt5 immediate16
+ Memory Word
Base address

Control Flow and Arrays COE 301 – KFUPM slide 25

 Example on Load & Store
 Translate: A[1] = A[2] + 5 (A is an array of words)
 Given that the address of array A is stored in register $t0
lw $t1, 8($t0) # $t1 = A[2]
addiu $t2, $t1, 5 # $t2 = A[2] + 5
sw $t2, 4($t0) # A[1] = $t2
 Index of A[2] and A[1] should be multiplied by 4. Why?
Memory
Registers
. . . . . .

$t0 &A A[3] &A + 12

lw
$t1 A[2] A[2] &A + 8
$t2 A[2] + 5 A[1] &A + 4
sw
. . . A[0] &A
. . .

Control Flow and Arrays COE 301 – KFUPM slide 26

 Load and Store Byte and Halfword
 The MIPS processor supports the following data formats:
 Byte = 8 bits, Half word = 16 bits, Word = 32 bits

 Load & store instructions for bytes and half words

 lb = load byte, lbu = load byte unsigned, sb = store byte
 lh = load half, lhu = load half unsigned, sh = store halfword
 Load expands a memory value to fit into a 32-bit register
 Store reduces a 32-bit register value 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

Control Flow and Arrays COE 301 – KFUPM slide 27

 Load and Store Instructions
Instruction Meaning I-Type Format
lb Rt, imm(Rs) Rt 1 MEM[Rs+imm] 0x20 Rs Rt 16-bit immediate
lh Rt, imm(Rs) Rt 2 MEM[Rs+imm] 0x21 Rs Rt 16-bit immediate
lw Rt, imm(Rs) Rt 4 MEM[Rs+imm] 0x23 Rs Rt 16-bit immediate
lbu Rt, imm(Rs) Rt 1 MEM[Rs+imm] 0x24 Rs Rt 16-bit immediate
lhu Rt, imm(Rs) Rt 2 MEM[Rs+imm] 0x25 Rs Rt 16-bit immediate
sb Rt, imm(Rs) Rt 1 MEM[Rs+imm] 0x28 Rs Rt 16-bit immediate
sh Rt, imm(Rs) Rt 2 MEM[Rs+imm] 0x29 Rs Rt 16-bit immediate
sw Rt, imm(Rs) Rt 4 MEM[Rs+imm] 0x2b Rs Rt 16-bit immediate

 Base / Displacement Addressing is used

 Memory Address = Rs (Base) + Immediate (displacement)
 If Rs is $zero then Address = Immediate (absolute)
 If Immediate is 0 then Address = Rs (register indirect)

Control Flow and Arrays COE 301 – KFUPM slide 28

 Next . . .
 Control Flow: Branch and Jump Instructions

 Translating If Statements and Boolean Expressions

 Arrays

 Load and Store Instructions

 Translating Loops and Traversing Arrays

 Addressing Modes

Control Flow and Arrays COE 301 – KFUPM slide 29

 Translating a WHILE Loop
 Consider the following WHILE loop:
i = 0; while (A[i] != value && i<n) i++;
Where A is an array of integers (4 bytes per element)
 Translate WHILE loop: $a0 = &A, $a1 = n, and $a2 = value
&A[i] = &A + i*4 = &A[i-1] + 4
li $t0, 0 # $t0 = i = 0
loop: lw $t1, 0($a0) # $t1 = A[i]
beq $t1, $a2, done # (A[i] == value)?
beq $t0, $a1, done # (i == n)?
addiu $t0, $t0, 1 # i++
addiu $a0, $a0, 4 # $a0 = &A[i]
j loop # jump backwards to loop
done: . . .
Control Flow and Arrays COE 301 – KFUPM slide 30
 Copying a String
A string in C is an array of chars terminated with null char

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

Given that: $a0 = &target and $a1 = &source

loop:
lb $t0, 0($a1) # load byte: $t0 = source[i]
sb $t0, 0($a0) # store byte: target[i]= $t0
addiu $a0, $a0, 1 # $a0 = &target[i]
addiu $a1, $a1, 1 # $a1 = &source[i]
bnez $t0, loop # loop until NULL char
Control Flow and Arrays COE 301 – KFUPM slide 31
 Initializing a Column of a Matrix
M = new int[10][5]; // allocate M on the heap
int i;
for (i=0; i<10; i++) { M[i][3] = i; }

# &M[i][3] = &M + (i*5 + 3) * 4 = &M + i*20 + 12

li $a0, 200 # $a0 = 10*5*4 = 200 bytes
li $v0, 9 # system call 9
syscall # allocate 200 bytes
move $t0, $v0 # $t0 = &M
li $t1, 0 # $t1 = i = 0
li $t2, 10 # $t2 = 10
L: sw $t1, 12($t0) # store M[i][3] = i
addiu $t1, $t1, 1 # i++
addiu $t0, $t0, 20 # $t0 = &M[i][3]
bne $t1, $t2, L # if (i != 10) loop back
Control Flow and Arrays COE 301 – KFUPM slide 32
 Addressing Modes
 Where are the operands?
 How memory addresses are computed?

Immediate Addressing
Op6 Rs5 Rt5 16-bit immediate One Operand is a constant

Register Addressing
Op6 Rs5 Rt5 Rd5 sa5 funct6 Operands are in registers
Register

Base / Displacement Addressing Memory Addressing (load/store)

Op6 Rs5 Rt5 16-bit immediate
+ Byte Halfword Word
Register = Base address

Control Flow and Arrays COE 301 – KFUPM slide 33

 Branch / Jump Addressing Modes
Used by branch (beq, bne, …)
PC-Relative Addressing
Op6 Rs5 Rt5 16-bit Offset
+1 Word = Target Instruction
PC30 00

Branch Target Address

PC30 + Offset16 + 1 00
PC = PC + 4 × (1 + Offset)

Used by jump instruction

Pseudo-direct Addressing
Op6 26-bit address
: Word = Target Instruction
PC30 00

Jump Target Address PC4 26-bit address 00

Control Flow and Arrays COE 301 – KFUPM slide 34

 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))/4, where PC
contains address of current instruction

Control Flow and Arrays COE 301 – KFUPM slide 35

 Jump and Branch Limits
 During execution, PC contains the address of current instruction (thus we add 1
to immediate16).
 Maximum branch limit is -215 to +215-1 instructions.
 If immediate is positive => Forward Jump
 If immediate is negative => Backward Jump

 Example
Forward Jump
During assembly:
0 Immediate=(Next-(PC+4))/4=(20-12)/4=2
Again:4 During execution:
8 beq $s1,$s2,Next PC=PC+4*(immediate+1)=8+4*(3)=20
12
16 bne $s1,$zero,Again Backward Jump
During assembly:
Next: 20
Immediate=(Again-(PC+4))/4=(4-20)/4=-4
During execution:
PC=PC+4*(immediate+1)=16+4*(-3)=4

Control Flow and Arrays COE 301 – KFUPM slide 36

 Summary of RISC Design
 All instructions are of the same size

 Few instruction formats

 General purpose registers for data and memory addresses

 Memory access only via load and store instructions

 Load and store: bytes, half words, and words

 Few simple addressing modes

Control Flow and Arrays COE 301 – KFUPM slide 37