Computer Organization and Architecture

Chapter 3: MIPS Assembly Language

 Overview of the MIPS Architecture

...

4 bytes per word Memory

Up to 232 bytes = 230 words
...

EIU $0 Execution & FPU F0 Floating

32 General $1 Integer Unit F1 Point Unit
Purpose $2 (Main proc) F2 (Coproc 1) 32 Floating-Point
Registers Registers
$31 F31
Arithmetic & Integer FP
ALU
Logic Unit mul/div Arith
Floating-Point
Arithmetic Unit
Hi Lo
TMU BadVaddr Trap &
Status Memory Unit
Cause (Coproc 0)
Integer EPC
Multiplier/Divider
 MIPS General-Purpose Registers
 32 General Purpose Registers (GPRs)
 All registers are 32-bit wide in the MIPS 32-bit architecture
 Software defines names for registers to standardize their use
 Assembler can refer to registers by name or by number ($ notation)
Name Register Usage
$zero $0 Always 0 (forced by hardware)
$at $1 Reserved for assembler use
$v0 – $v1 $2 – $3 Result values of a function
$a0 – $a3 $4 – $7 Arguments of a function
$t0 – $t7 $8 – $15 Temporary Values
$s0 – $s7 $16 – $23 Saved registers (preserved across call)
$t8 – $t9 $24 – $25 More temporaries
$k0 – $k1 $26 – $27 Reserved for OS kernel
$gp $28 Global pointer (points to global data)
$sp $29 Stack pointer (points to top of stack)
$fp $30 Frame pointer (points to stack frame)
$ra $31 Return address (used by jal for function call)
 What is Assembly Language?

 Low-level programming language for a computer

 One-to-one correspondence with the machine instructions

 Assembly language is specific to a given processor

 Assembler: converts assembly program into machine code

 Assembly language uses:

 Mnemonics: to represent the names of low-level machine instructions

 Labels: to represent the names of variables or memory addresses

 Directives: to define data and constants

 Macros: to facilitate the inline expansion of text into other code

 Assembly Language Statements
 Three types of statements in assembly language
 Typically, one statement should appear on a line
1. Executable Instructions
 Generate machine code for the processor to execute at runtime
 Instructions tell the processor what to do
2. Pseudo-Instructions and Macros
 Translated by the assembler into real instructions
 Simplify the programmer task
3. Assembler Directives
 Provide information to the assembler while translating a program
 Used to define segments, allocate memory variables, etc.
 Non-executable: directives are not part of the instruction set
 Assembly Language Instructions
 Assembly language instructions have the format:
[label:] mnemonic [operands] [#comment]
 Label: (optional)
 Marks the address of a memory location, must have a colon
 Typically appear in data and text segments
 Mnemonic
 Identifies the operation (e.g. add, sub, etc.)
 Operands
 Specify the data required by the operation
 Operands can be registers, memory variables, or constants
 Most instructions have three operands
L1: addiu $t0, $t0, 1 #increment $t0
 Comments
 Single-line comment
 Begins with a hash symbol # and terminates at end of line

 Comments are very important!

 Explain the program's purpose

 When it was written, revised, and by whom

 Explain data used in the program, input, and output

 Explain instruction sequences and algorithms used

 Comments are also required at the beginning of every procedure

 Indicate input parameters and results of a procedure

 Describe what the procedure does

 Program Template
# Title: Filename:
# Author: Date:
# Description:
# Input:
# Output:
################# Data segment #####################
.data
. . .
################# Code segment #####################
.text
.globl main
main: # main program entry
. . .
li $v0, 10 # Exit program
syscall
 .DATA, .TEXT, & .GLOBL Directives
 .DATA directive
 Defines the data segment of a program containing data

 The program's variables should be defined under this directive

 Assembler will allocate and initialize the storage of variables

 .TEXT directive
 Defines the code segment of a program containing instructions

 .GLOBL directive
 Declares a symbol as global

 Global symbols can be referenced from other files

 We use this directive to declare main function of a program

 Layout of a Program in Memory

0x7FFFFFFF
Stack Segment Stack Grows
Downwards

Memory
Addresses
in Hex
Dynamic Area (Heap) Data Segment
Static data
Static Area
0x10000000 appear here

Text Segment Instructions

0x04000000 appear here

Reserved
0
 Data Definition Statement
 The assembler uses directives to define data
 It allocates storage in the static data segment for a variable

 May optionally assign a name (label) to the data

 Syntax:

[name:] directive initializer [, initializer] . . .

var1: .WORD 10
 All initializers become binary data in memory
 Data Directives
 .BYTE Directive
 Stores the list of values as 8-bit bytes

 .HALF Directive
 Stores the list as 16-bit values aligned on half-word boundary

 .WORD Directive
 Stores the list as 32-bit values aligned on a word boundary

 .FLOAT Directive
 Stores the listed values as single-precision floating point

 .DOUBLE Directive
 Stores the listed values as double-precision floating point
 String Directives

 .ASCII Directive
 Allocates a sequence of bytes for an ASCII string

 .ASCIIZ Directive

 Same as .ASCII directive, but adds a NULL char at end of string \0

 Strings are null-terminated, as in the C programming language

 .SPACE Directive

 Allocates space of n uninitialized bytes in the data segment

 Examples of Data Definitions
.DATA

var1: .BYTE 'A', 'E', 127, -1, '\n'

var2: .HALF -10, 0xffff

Array of 100 words
var3: .WORD 0x12345678:100 Initialized with
the same value
var4: .FLOAT 12.3, -0.1

var5: .DOUBLE 1.5e-10

str1: .ASCII "A String\n"

str2: .ASCIIZ "NULL Terminated String"

array: .SPACE 100 100 bytes (not initialized)

 Memory Alignment
 Memory is viewed as an addressable array of bytes
 Byte Addressing: address points to a byte in memory
 However, words occupy 4 consecutive bytes in memory
 MIPS instructions and integers occupy 4 bytes
Memory
 Memory Alignment:

address
...
 Address must be multiple of size aligned word

 Word address should be a multiple of 4 12 not aligned

8
 Double-word address should be a multiple of 8 4
0 not aligned

 .ALIGN n directive
 Aligns the next data definition on a 2n byte boundary
 Forces the address of next data definition to be multiple of 2n
 System Calls
 Programs do input/output through system calls
 The MIPS architecture provides a syscall instruction
 To obtain services from the operating system

 The operating system handles all system calls requested by program

 Since MARS is a simulator, it simulates the syscall services

 To use the syscall services:

 Load the service number in register $v0

 Load argument values, if any, in registers $a0, $a1, etc.

 Issue the syscall instruction

 Retrieve return values, if any, from result registers

 Syscall Services
Service $v0 Arguments / Result
Print Integer 1 $a0 = integer value to print
Print Float 2 $f12 = float value to print
Print Double 3 $f12 = double value to print
Print String 4 $a0 = address of null-terminated string
Read Integer 5 Return integer value in $v0
Read Float 6 Return float value in $f0
Read Double 7 Return double value in $f0
$a0 = address of input buffer
Read String 8
$a1 = maximum number of characters to read
Allocate Heap $a0 = number of bytes to allocate
9
memory Return address of allocated memory in $v0
Exit Program 10
 Syscall Services
Print Char 11 $a0 = character to print
Read Char 12 Return character read in $v0
$a0 = address of null-terminated filename string $a1
= flags (0 = read-only, 1 = write-only)
Open File 13
$a2 = mode (ignored)
Return file descriptor in $v0 (negative if error)
$a0 = File descriptor
Read $a1 = address of input buffer
14
from File $a2 = maximum number of characters to read
Return number of characters read in $v0
$a0 = File descriptor
$a1 = address of buffer
Write to File 15
$a2 = number of characters to write
Return number of characters written in $v0
Close File 16 $a0 = File descriptor
 Reading and Printing an Integer
################# Code segment #####################
.text
.globl main
main: # main program entry
li $v0, 5 # Read integer
syscall # $v0 = value read

move $a0, $v0 # $a0 = value to print

li $v0, 1 # Print integer
syscall

li $v0, 10 # Exit program

syscall
 Reading and Printing a String
################# Data segment #####################
.data
str: .space 10 # array of 10 bytes
################# Code segment #####################
.text
.globl main
main: # main program entry
la $a0, str # $a0 = address of str
li $a1, 10 # $a1 = max string length
li $v0, 8 # read string
syscall
li $v0, 4 # Print string str
syscall
li $v0, 10 # Exit program
syscall
 Sum of Three Integers
# Sum of three integers
# Objective: Computes the sum of three integers.
# Input: Requests three numbers, Output: sum
################### Data segment ###################
.data
prompt: .asciiz "Please enter three numbers: \n"
sum_msg: .asciiz "The sum is: "
################### Code segment ###################
.text
.globl main
main:
la $a0,prompt # display prompt string
li $v0,4
syscall
li $v0,5 # read 1st integer into $t0
syscall
move $t0,$v0
 Sum of Three Integers – (cont'd)
li $v0,5 # read 2nd integer into $t1
syscall
move $t1,$v0
li $v0,5 # read 3rd integer into $t2
syscall
move $t2,$v0
addu $t0,$t0,$t1 # accumulate the sum
addu $t0,$t0,$t2
la $a0,sum_msg # write sum message
li $v0,4
syscall
move $a0,$t0 # output sum
li $v0,1
syscall
li $v0,10 # exit
syscall
 Instruction Categories
 Integer Arithmetic
 Arithmetic, logic, and shift instructions
 Data Transfer
 Load and store instructions that access memory
 Data movement and conversions
 Jump and Branch
 Flow-control instructions that alter the sequential sequence
 Floating Point Arithmetic
 Instructions that operate on floating-point registers
 Miscellaneous
 Instructions that transfer control to/from exception handlers
 Memory management instructions
 R-Type Instruction Format
Op6 Rs5 Rt5 Rd5 sa5 funct6

 Op: operation code (opcode)

 Specifies the operation of the instruction
 Also specifies the format of the instruction

 funct: function code – extends the opcode

 Up to 26 = 64 functions can be defined for the same opcode
 MIPS uses opcode 0 to define many R-type instructions

 Three Register Operands (common to many instructions)

 Rs, Rt: first and second source operands
 Rd: destination operand
 sa: the shift amount used by shift instructions
 R-Type Integer Add and Subtract
Instruction Meaning Op Rs Rt Rd sa func
add $t1, $t2, $t3 $t1 = $t2 + $t3 0 $t2 $t3 $t1 0 0x20
addu $t1, $t2, $t3 $t1 = $t2 + $t3 0 $t2 $t3 $t1 0 0x21
sub $t1, $t2, $t3 $t1 = $t2 – $t3 0 $t2 $t3 $t1 0 0x22
subu $t1, $t2, $t3 $t1 = $t2 – $t3 0 $t2 $t3 $t1 0 0x23

 add, sub: arithmetic overflow causes an exception

 In case of overflow, result is not written to destination register

 addu, subu: arithmetic overflow is ignored

 addu, subu: compute the same result as add, sub
 Many programming languages ignore overflow
 The + operator is translated into addu
 The – operator is translated into subu
 Using Add / Subtract Instructions
 Consider the translation of: f = (g+h)–(i+j)
 Programmer / Compiler allocates registers to variables
 Given that: $t0=f, $t1=g, $t2=h, $t3=i, and $t4=j
 Called temporary registers: $t0=$8, $t1=$9, …
 Translation of: f = (g+h)–(i+j)
addu $t5, $t1, $t2 # $t5 = g + h
addu $t6, $t3, $t4 # $t6 = i + j
subu $t0, $t5, $t6 # f = (g+h)–(i+j)
 Assembler translates addu $t5,$t1,$t2 into binary code
Op $t1 $t2 $t5 sa addu
000000 01001 01010 01101 00000 100001
 Logic Bitwise Operations
 Logic bitwise operations: and, or, xor, nor

x y x and y x y x or y x y x xor y x y x nor y

0 0 0 0 0 0 0 0 0 0 0 1
0 1 0 0 1 1 0 1 1 0 1 0
1 0 0 1 0 1 1 0 1 1 0 0
1 1 1 1 1 1 1 1 0 1 1 0

 AND instruction is used to clear bits: x and 0  0

 OR instruction is used to set bits: x or 1  1
 XOR instruction is used to toggle bits: x xor 1  not x
 NOT instruction is not needed, why?
not $t1, $t2 is equivalent to: nor $t1, $t2, $t2
 Logic Bitwise Instructions
Instruction Meaning Op Rs Rt Rd sa func
and $t1, $t2, $t3 $t1 = $t2 & $t3 0 $t2 $t3 $t1 0 0x24
or $t1, $t2, $t3 $t1 = $t2 | $t3 0 $t2 $t3 $t1 0 0x25
xor $t1, $t2, $t3 $t1 = $t2 ^ $t3 0 $t2 $t3 $t1 0 0x26
nor $t1, $t2, $t3 $t1 = ~($t2|$t3) 0 $t2 $t3 $t1 0 0x27

 Examples:
Given: $t1 = 0xabcd1234 and $t2 = 0xffff0000

and $t0, $t1, $t2 # $t0 = 0xabcd0000

or $t0, $t1, $t2 # $t0 = 0xffff1234
xor $t0, $t1, $t2 # $t0 = 0x54321234
nor $t0, $t1, $t2 # $t0 = 0x0000edcb
 Shift Operations
 Shifting is to move the 32 bits of a number left or right
 sll means shift left logical (insert zero from the right)
 srl means shift right logical (insert zero from the left)
 sra means shift right arithmetic (insert sign-bit)
 The 5-bit shift amount field is used by these instructions

sll 32-bit value

shift-out ... shift-in 0

srl
shift-in 0 ... shift-out

sra
shift-in sign-bit ... shift-out
 Shift Instructions

Instruction Meaning Op Rs Rt Rd sa func

sll $t1,$t2,10 $t1 = $t2 << 10 0 0 $t2 $t1 10 0
srl $t1,$t2,10 $t1 = $t2 >>> 10 0 0 $t2 $t1 10 2
sra $t1,$t2,10 $t1 = $t2 >> 10 0 0 $t2 $t1 10 3
sllv $t1,$t2,$t3 $t1 = $t2 << $t3 0 $t3 $t2 $t1 0 4

 sll, srl, sra: shift by a constant amount

 The shift amount (sa) field specifies a number between 0 and 31

 sllv, srlv, srav: shift by a variable amount

 A source register specifies the variable shift amount between 0 and 31
 Only the lower 5 bits of the source register is used as the shift amount
 Shift Instruction Examples
 Given that: $t2 = 0xabcd1234 and $t3 = 16

sll $t1, $t2, 8 $t1 = 0xcd123400

srl $t1, $t2, 4 $t1 = 0x0abcd123

sra $t1, $t2, 4 $t1 = 0xfabcd123

srlv $t1, $t2, $t3 $t1 = 0x0000abcd

Op Rs = $t3 Rt = $t2 Rd = $t1 sa srlv

000000 01011 01010 01001 00000 000110
 Binary Multiplication

 Shift Left Instruction (sll) can perform multiplication

 When the multiplier is a power of 2

 You can factor any binary number into powers of 2

 Example: multiply $t0 by 36
$t0*36 = $t0*(4 + 32) = $t0*4 + $t0*32

sll $t1, $t0, 2 # $t1 = $t0 * 4

sll $t2, $t0, 5 # $t2 = $t0 * 32

addu $t3, $t1, $t2 # $t3 = $t0 * 36

 Examples
Multiply $t0 by 26, using shift and add instructions
Hint: 26 = 2 + 8 + 16

sll $t1, $t0, 1 # $t1 = $t0 * 2

sll $t2, $t0, 3 # $t2 = $t0 * 8
sll $t3, $t0, 4 # $t3 = $t0 * 16
addu $t4, $t1, $t2 # $t4 = $t0 * 10
addu $t5, $t4, $t3 # $t5 = $t0 * 26

Multiply $t0 by 31, Hint: 31 = 32 – 1

sll $t1, $t0, 5 # $t1 = $t0 * 32

subu $t2, $t1, $t0 # $t2 = $t0 * 31
 I-Type Instruction Format
 Constants are used quite frequently in programs
 The R-type shift instructions have a 5-bit shift amount constant
 What about other instructions that need a constant?

 I-Type: Instructions with Immediate Operands

Op6 Rs5 Rt5 immediate16

 16-bit immediate constant is stored inside the instruction

 Rs is the source register number
 Rt is now the destination register number (for R-type it was Rd)

 Examples of I-Type ALU Instructions:

 Add immediate: addi $t1, $t2, 5 # $t1 = $t2 + 5
 OR immediate: ori $t1, $t2, 5 # $t1 = $t2 | 5
 I-Type ALU Instructions
Instruction Meaning Op Rs Rt Immediate
addi $t1, $t2, 25 $t1 = $t2 + 25 0x8 $t2 $t1 25
addiu $t1, $t2, 25 $t1 = $t2 + 25 0x9 $t2 $t1 25
andi $t1, $t2, 25 $t1 = $t2 & 25 0xc $t2 $t1 25
ori $t1, $t2, 25 $t1 = $t2 | 25 0xd $t2 $t1 25
xori $t1, $t2, 25 $t1 = $t2 ^ 25 0xe $t2 $t1 25
lui $t1, 25 $t1 = 25 << 16 0xf 0 $t1 25

 addi: overflow causes an arithmetic exception

 In case of overflow, result is not written to destination register

 addiu: same operation as addi but overflow is ignored

 Immediate constant for addi and addiu is signed
 No need for subi or subiu instructions

 Immediate constant for andi, ori, xori is unsigned

 Examples of I-Type ALU Instructions
 Given that registers $t0, $t1, $t2 are used for A, B, C

Expression Equivalent MIPS Instruction

A = B + 5; addiu $t0, $t1, 5
C = B – 1; addiu $t2, $t1, -1
A = B & 0xf; andi $t0, $t1, 0xf
C = B | 0xf; ori $t2, $t1, 0xf
C = 5; addiu $t2, $zero, 5
A = B; addiu $t0, $t1, 0
Op = addiu Rs = $t1 Rt = $t2 -1 = 0b1111111111111111

No need for subiu, because addiu has signed immediate

Register $zero has always the value 0
 32-bit Constants
 I-Type instructions can have only 16-bit constants
Op6 Rs5 Rt5 immediate16

 What if we want to load a 32-bit constant into a register?

 Can’t have a 32-bit constant in I-Type instructions 
 The sizes of all instructions are fixed to 32 bits

 Solution: use two instructions instead of one 

 Suppose we want: $t1 = 0xAC5165D9 (32-bit constant)
lui: load upper immediate Upper Lower
16 bits 16 bits
lui $t1, 0xAC51 $t1 0xAC51 0x0000
ori $t1, $t1, 0x65D9 $t1 0xAC51 0x65D9
 Pseudo-Instructions
 Introduced by the assembler as if they were real instructions
 Facilitate assembly language programming

Pseudo-Instruction Equivalent MIPS Instruction

move $t1, $t2 addu $t1, $t2, $zero
not $t1, $t2 nor $t1, $t2, $zero
neg $t1, $t2 sub $t1, $zero, $t2
li $t1, -5 addiu $t1, $zero, -5
lui $t1, 0xabcd
li $t1, 0xabcd1234
ori $t1, $t1, 0x1234

The MARS tool has a long list of pseudo-instructions

 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

 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.
 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
 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

 The upper 4 bits of the PC are unchanged multiple

of 4
 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: . . .
 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:
 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:
 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:
 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
 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
 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
 Using Pseudo-Branch Instructions
 Translate the IF statement to assembly language
 $t1 and $t2 values are unsigned

if($t1 <= $t2) { bgtu $t1, $t2, L1

$t3 = $t4; move $t3, $t4
} L1:

 $t3, $t4, and $t5 values are signed

if (($t3 <= $t4) && bgt $t3, $t4, L1

($t4 >= $t5)) { blt $t4, $t5, L1
$t3 = $t4 + $t5; addu $t3, $t4, $t5
} L1:
 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

 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

 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"
 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
. . .
Allocating Dynamic Memory on the Heap
0x7fffffff
Stack Segment

Heap Area
Data Segment
0x10040000
Static Area
0x10000000

Text Segment
0x00400000

Reserved
0x00000000
 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
 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

 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 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

 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
 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
. . .
 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
 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)
 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: . . .
 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