9/9/2020
CSC 252:
MIPS Assembly Language
Dr. Jonathan Misurda
jmisurda@arizona.edu
MIPS Operations and Operands
Operation specifies what function to perform by the instruction. Operand specifies what quantity (data) to use with the instruction.
MIPS operations
• Arithmetic (integer/floating-point)
• Logical (AND, OR, etc)
• Shift (moves bits around)
• Compare (equality test)
• Load/store (get/put stuff in memory)
• Branch/jump (make decisions)
• System control and coprocessor
MIPS operands
• Registers (one of 32 general-purpose registers)
• Fixed registers (e.g., HI/LO)
• Memory location (place in memory)
• Immediate value (constant)
addi $t0,$t1,10
Operation (add immediate)
Destination Operand
Source Operands
12
MIPS Arithmetic
All arithmetic instructions have 3 operands:
• Operand order in notation is fixed; target (destination) first
• Two source registers and one target (destination) register
• Operands are either 2 registers or 1 register + 1 immediate (constant)
• Destination is always a register
Examples
– add$s1,$s2,$s3 #$s1$s2+$s3
– sub $s4, $s5, $s6 # $s4 $s5 – $s6
MIPS Registers
32 bits $zero r0
$at r1
$v0 r2
$v1 r3
$a0 r4
$a1 r5
$a2 r6
$a3 r7
$t0 r8
$t1 r9
$t2 r10
$t3 r11
$t4 r12
$t5 r13
$t6 r14
$t7 r15
32 bits
r16 $s0
r17 $s1 r18 $s2 r19 $s3 r20 $s4 r21 $s5 r22 $s6 r23 $s7 r24 $t8 r25 $t9 r26 $k0 r27 $k1 r28 $gp r29 $sp r30 $fp r31 $ra
32 bits
HI LO
PC
Special-Purpose Registers
General-Purpose Registers
34
General-Purpose Registers
The name GPR implies that all these registers can be used as operands in instructions.
Still, conventions and limitations exist to keep GPRs from being used arbitrarily (from the manual)
• $0, termed $zero, always has a value of 0
• $31, termed $ra (return address), is reserved for storing the return address for subroutine call/return
• Register usage and related software conventions are typically summarized in the application binary interface (ABI) – important when writing system software such as an assembler or a compiler
Special-Purpose Registers
HI/LO registers used to store result from multiplication.
PC register (program counter)
• Always keeps the address of the current program execution point; The next
instruction fetched to execute lives at the address in $PC
• Not directly visible and manipulated by programmers in MIPS
Other instruction set architectures:
• May not have HI/LO; use GPRs to store the result of multiplication
• May allow storing to PC to make a jump
56
1
9/9/2020
Instruction encoding
Instructions are encoded in binary numbers
• Assembler translates assembly programs into binary numbers
• Machine (processor) decodes binary numbers to figure out what the original
instruction is
• MIPS has a fixed, 32-bit instruction encoding
Encoding should be done in a way that decoding is easy.
MIPS instruction formats:
• R-format: arithmetic instructions
• I-format: data transfer/arithmetic/branch instructions (immediates)
• J-format: jump instruction format (changes program counter)
• (FI-/FR-format: floating-point instruction format)
MIPS instruction formats
Name
bit 31
Fields
bit 0
Comments
Field Size
6 bits
5 bits
5 bits
5 bits
5 bits
6 bits
All MIPS instructions are 32 bits
R-format
op (opcode)
rs
rt
rd
shamt
funct
Arithmetic/logic instruction format
I-format
op (opcode)
rs
rt
Immediate/address
Data transfer, branch, immediate format
J-format
op (opcode)
target address
Jump instruction format
78
Instruction Encoding Example
add $t0,$t1,$t8
operation is “addition” opcode = 000000 (6 bits) funct = 100000 (6 bits)
Resulting encoded instruction:
$t0 is register 8
rd = 01000 (5 bits)
$t1 is register 9
rs = 01001 (5 bits)
$t8 is register 24 rt = 11000 (5 bits)
shamt is unused
shamt = 00000 (5 bits)
Op
rs
rt
rd
shamt
funct
000000
01001
11000
01000
00000
100000
Logic Instructions
Name
Fields
Comments
R-format
op
rs
rt
rd
shamt
funct
Logic instruction format
Bit-wise logic operations Examples:
and $s3, $s2, $s1
$s3 $s2 & $s1
or $t3, $t2, $t1
$t3 $t2 | $t1
nor $s3, $t2, $s1
$s3 ~($t2 | $s1)
nor $s3, $t2, $0
$s3 !($t2)
xor $s3, $s2, $s1
$s3 $s2 ^ $s1
• note: xor produces 1 iff one of the operands is 1
9 10
Immediates
Many operations involve small “immediate” value • a=a+1
• b=b–4
• c=d|0x04
Some frequently used arithmetic/logic instructions have an immediate version:
There is no “subi”; why?
Name
Fields
Comments
I-format
op
rs
rt
16-bit immediate
Transfer, branch, immediate format
addi $s3, $s2, 16
$s3 $s2 + 16
andi $s5, $s4, 0xfffe
$s5 $s4 & 1111111111111110b
ori $t4, $t4, 4
$t4 $t4 | 0000000000000100b
xori $s7, $s6, 16
$s7 $s6 ^ 0000000000010000b
Long Immediates
Sometimes we need a long immediate value, e.g., 32 bits
• Do we need an instruction to load a 32-bit constant value to a register?
MIPS requires that we use two instructions • lui $s3, 1010101001010101b
$s3
Then we fill the low-order 16 bits
• ori $s3, $s3, 1100110000110011b
$s3
1010101001010101
0000000000000000
1010101001010101
1100110000110011
11 12
2
9/9/2020
Pseudo-ops
Assemblers do more than just convert mnemonic opcodes into machine instructions.
They can implement instructions that are not directly implemented in hardware. These operations are referred to as pseudo-ops.
The assembler implements pseudo-ops the same way a high-level language works: by replacing the pseudo-op with one or more real machine instructions at assemble time.
Examples:
li – load immediate (16 or 32-bits)
la – load address (32-bits)
move – move the value in one register into another
Interacting with the OS
We need the OS’s help.
• How to print a number? (output)
• How to read a number? (input)
• How to terminate (halt) a program?
• How to open, close, read, write a file?
• These are operating system “services”
Special instruction: syscall
• A “software interrupt” to invoke OS for an action (to do a service)
• Need to indicate the service to perform (e.g., print vs. terminate)
• May also need to pass an argument value (e.g., number to print)
13 14
A Few Useful syscalls
syscall takes a service ID (number) sent to OS in $v0
•
•
• Syscall
Print integer
• $v0=1, $a0=integer to print
Read integer
• $v0=5, after syscall, $v0 holds the integer read from keyboard
Print string
• $v0=4, $a0=memory address of string to print (null terminated)
Exit (halt)
• $v0=10, no argument See MARS docs for more.
Example: Print an Integer
Java:
int a;
a = 10 + 8; System.out.print(a);
Let’s try it in MARS. (mips1.asm)
MIPS:
# $t0 is a, $t0=10
li $t0, 10
# $t0=10+8
addi $t0, $t0, 8
# print service
li $v0, 1
# pass value in $t0 to service
add $a0, $t0, $0
# invoke OS to do service
syscall
# terminate program service
li $v0, 10
# invoke OS to do service
syscall
15 16
Example: String Output
.data
msg: .asciiz “Sum of 10 + 8 is ” .text
# print with a string: “Sum of 10 + 8 is 18”
# message to print before the number
li $t0, 10
addi $t0, $t0, 8 li $v0, 4
la $a0, msg syscall
li $v0, 1
add $a0, $t0, $0 syscall
li $v0, 10 syscall
# put 10 into a
# do the add with 8
# print string service # load string
# print integer service # move idiom
# terminate program
Let’s try it in MARS.(mips2.asm)
Example: Add 10 + x
.data .text
move
x_msg: msg:
li
la syscall li syscall move addi
li
la syscall li
syscall li syscall
.asciiz .asciiz
“Number x to add?\n” “Sum of 10 + x is\n”
$v0,4 # print prompt $a0,x_msg
$v0,5 # read integer service
$t0,$v0 # number read in $v0 $t0,$t0,10 # add number with 10 $v0,4 # print result prompt $a0,msg
$v0,1 # print the sum $a0,$t0
$v0,10 # terminate program
Let’s try it in MARS. (mips3.asm)
17 18
3
9/9/2020
Memory Transfer Instructions
How to get values to/from memory?
• Also called memory access instructions
Only two types of instructions:
• Load: move data from memory to register (“load the register”)
• e.g., lw $s5, 4($t6) # $s5 memory[$t6 + 4]
• Store: move data from register to memory (“save the register”)
• e.g., sw $s7, 16($t3) # memory[$t3+16] $s7
In MIPS (32-bit architecture) there are memory transfer instructions for:
• 32-bit word: “int” type in Java (lw, sw)
• 16-bit half-word: “short” type in Java (lh, sh; also unsigned lhu)
• 8-bit byte: “byte” type in Java (lb, sb; also unsigned lbu)
Memory View
Memory is a large, single-dimension 8-bit (byte) array with an address to each 8-bit item (“byte address”)
A memory address is just an index into the array. 0
1 2 3 4 5
Address 4 gets this byte
li $t0, 4
BYTE #0
BYTE #1
BYTE #2
BYTE #3
BYTE #4
BYTE #5
BYTE #6
BYTE #7
BYTE #8
7 8
Loads and stores give the index (address) to access
$t1,0($t0) sb $t2,0($t0)
6 lb
19 20
Memory View
Memory is a large, single-dimension 8-bit (byte) array with an address to each 8-bit item (“byte address”)
A memory address is just an index into the array. 0
1 2 3 4 5
Address 4 gets this halfword
li $t0, 4
BYTE #0
BYTE #1
BYTE #2
BYTE #3
BYTE #4
BYTE #5
BYTE #6
BYTE #7
BYTE #8
7 8
Loads and stores give the index (address) to access
$t1,0($t0) sh $t2,0($t0)
6 lh
Memory View
Memory is a large, single-dimension 8-bit (byte) array with an address to each 8-bit item (“byte address”)
A memory address is just an index into the array. 0
1 2 3 4 5
Address 4 gets this word
li $t0, 4
BYTE #0
BYTE #1
BYTE #2
BYTE #3
BYTE #4
BYTE #5
BYTE #6
BYTE #7
BYTE #8
7 8
Loads and stores give the index (address) to access
$t1,0($t0) sw $t2,0($t0)
6 lw
21 22
Effective Address calculation
Effective memory address specified as immediate($register)
• Register to keep the base address
• Immediate to determine an offset from the base address
• Thus, address is contents of register + immediate
• The offset can be positive or negative, 16-bit value (uses I-format)
Suppose base register $t0=64, then:
lw $t0, 12($t1) address = 64 + 12 = 76
lw $t0, -12($t1) address = 64 – 12 = 52
MIPS uses this simple address calculation; other architectures such as PowerPC and x86 support different methods.
Load Address
Often, you need to reference a particular variable.
.data
var: .word 1000
How to reference var?
la $t0,var
lw $t1,0($t0)
la is a pseudo-instruction. It is turned into a sequence to put a large address constant into $t0.
lui $at, upperbitsofaddres
ori $t0, $1, lowerbitsofaddress
23 24
4
9/9/2020
In-class Exercise
Create a word (integer) variable “myVar”
Give the variable the value 20
Print the value to the console (Run I/O window) Terminate the program
Extension: Add 10 to the value, store it to myVar, print it
To do this, we’ll need to use:
• Data segment declaration with a word variable type
• Instruction segment declaration
• Load word instruction
• Syscall instruction
• Assorted la and li instructions
In-class Example (2)
Consider the Java program and rewrite as MIPS
void fun(void) {
int a=10,b=20,c=30;
a=a+10; b=0; c=a+b;
}
25 26
Machine Code Example
void swap(int v[], int k) {
swap:
}
int temp;
temp = v[k]; v[k] = v[k+1]; v[k+1] = temp;
sll $t0, $a1, 2 add $t1, $a0, $t0 lw $t3, 0($t1) lw $t4, 4($t1) sw $t4, 0($t1) sw $t3, 4($t1) jr $ra
Let’s try it in MARS. (mips4.asm)
Memory Organization
32-bit byte address:
• 232 bytes with byte addresses from 0 to 232-1
• 230 words with byte addresses 0, 4, 8, …, 232-4
0 4 8
WORD #0
WORD #1
WORD #2
WORD #3
WORD #4
WORD #5
Words are aligned 12
• 2 least significant bits (LSBs) of an address are 0s Half words are aligned
• LSB of an address is 0
Addressing within a word:
• Which byte appears first and which byte the last?
• Big-endian vs. little-endian
• Little end (LSB) comes first (at low address)
• Big end (MSB) comes first (at low address)
Let’s try it in MARS. (mips5.asm)
16 20
0
Low High
Address 0
Address
0
1
2
3
Little Endian
Big Endian
3
2
1
0
27 28
Alignment
A misaligned access
• Assume $t0=0, then lw $s4, 3($t0)
How do we define a word at an address? • Datainbyte0,1,2,3
• If you meant this, use the address 0, not 3.
0 4 8
0
1
2
3
4
5
6
7
8
9
10
1 1
• Datainbyte3,4,5,6
• If you meant this, it is indeed misaligned!
• Certain hardware implementation may support this; usually not.
• If you still want to obtain a word starting from the address 3 – get a byte
from address 3, a word from address 4 and manipulate the two data to get what you want
Alignment issue does not exist for byte access.
Shift Instructions
Bits change their positions inside a word.
Name
Fields
Comments
R-format
op
NOT USED
rt
rd
shamt
funct
shamt is “shift amount”
Shift amount can be in a register (shamt is not used) Shift right arithmetic (sra) keeps the sign of a number
• sra $s7, $s5, 4
Let’s try it in MARS. (mips6.asm)
29 30
5
9/9/2020
Control
Instruction can change the flow of program execution by manipulating $PC. MIPS conditional branch instructions
• bne $s4, $s3, LABEL • beq $s4, $s3, LABEL
# goto LABEL if $s4 != $s3 # goto LABEL if $s4 == $s3
Java:
if (i == h) { h = i + j;
}
MIPS:
bne $s5, $s6, LABEL
add $s6, $s5, $s7 LABEL: …
Example: yes
i==h?
LABEL
no
h = i + j;
Control
MIPS also has an unconditional branch instruction (i.e., jump or goto)
• j LABEL Example:
yes no i==h?
EXIT
•
i, f, g, and h are in registers $s4, $s5, $s6, $s7
f = g + h;
f = g – h;
Java:
if (i == h) { f = g + h;
}
else {
MIPS:
}
f = g – h;
bne $s4, $s7, ELSE add $s5, $s6, $s7 j EXIT
ELSE:
sub $s5, $s6, $s7
EXIT: …
31 32
Control
We have beq and bne; what about branch-if-less-than?
•
We have slt (set less than)
MIPS:
slt $t0, $s1, $s2
Can you make a psuedo-instruction “blt $s1, $s2, LABEL”?
Assembler needs a temporary register to do this.
• $at is reserved for this purpose
• slt $at,$s1,$s2 # $at==1 when $s1<$s2
• bne $at,$0,LABEL # $at!=0 implies $at==1
Java:
if (s1
= low16(0x10 >> 2) # 16/ 4
= 0x4 # forward 4+1 instructions
35 36
6
9/9/2020
Example of Addresses in Branches
Branch address is “PC relative”
• The target is RELATIVE to address of the branch instruction itself
• NextPC = PC + 4 + sign-extend(16-bit immediate << 2)
0x00400000 0x00400004 0x00400008 0x0040000c 0x00400010 0x00400014
LABEL: andi
srl $s0,$s0,2
lui $s1,0xFF00
ori $s1,$s0,$s1
beq $s0,$s1,LABEL# what’s LABEL??? ...
$s0,$s0,0xFF
PC when branch taken=0x00400010 + 4 + sign-extend(LABEL << 2) LABEL = low16((0x00400000 - (0x00400010 + 4))) >> 2)
= low16((0xFFFFFFEC) >> 2) # -20 / 4
= 0xFFFB # backward -4-1 instructions
J-format
The address of next instruction is obtained from PC and the immediate value
• Next address = PC[31:28] IMM[25:0] 00
• is concatenation
• Address boundaries of 256MB
Example
• j 10000
Jump
op
26-bit immediate
2
2500
37 38
Control
What about comparisons against constant? • Can we use “beqi”??? Why not? Comparison variants with an immediate
• slti $s0,$s1,16
• addi $s0,$s1,-20
Java:
if(a > 20){
a = a + 2;
}
MIPS:
#($s0==0 when $s1==20)
# $at==1 when a<=20
# $at!=0 implies $at==1, skip
# target when a<=20
LAB: ...
slti $at,$s0,21 bne $at,$0,LAB addi $s0,$s0,2
While Loop
while (condition == true) { some work; }
Use comparison, branch to exit, and jump to continue looping.
Generally written as:
loop: check condition
branch if condition is false to exit some work
j loop
exit:
39 40
While Loop
Java:
byte[] a = {1, 2, 3, 4, 5, 0};
int i = 0;
while (a[i] != 0) { System.out.print(a[i]); i = i + 1; }
MIPS:
.data
a: .byte 1,2,3,4,5,0
.text
la $t0, a
loop:
exit:
lb $a0, 0($t0)
beq $a0, $0, exit
li $v0,1 # print integer syscall
addi $t0, $t0, 1
j loop
See mips12.asm
Do While Loop
do { some work; } while (condition == true);
Use comparison, branch to exit, and jump to continue loop.
Generally written as:
loop: some work
check condition
branch if condition is true to loop exit:
41 42
7
9/9/2020
Do While Loop
Java:
byte[] a = {1, 2, 3, 4, 5, 0};
int i = 0;
do { System.out.print(a[i]); i = i + 1; } while (a[i] != 0);
MIPS:
.data
a: .byte 1,2,3,4,5,0
.text
la $t0, a
lb $a0, 0($t0)
loop: li syscall
addi $t0,$t0,1 lb $a0,0($t0) bne $a0,$0,loop
# start the loop # print integer
See mips11.asm
$v0,1
Procedures
int len(byte[] s) { int l = 0;
for (int i=0; s[i]!=0 ; i++) l++; return l;
}
void reverse(byte[] s, byte[] t) {
int l = len(s);
t[l] = 0;
for(int i=0;i