Transcript MIPS code - Department of Electrical Engineering & Computer

COSC 2021: Computer Organization
Instructor: Dr. Amir Asif
Department of Computer Science
York University
Handout # 3: MIPS Instruction Set I
Topics:
1. Arithmetic Instructions
2. Registers, Memory, and Addressing
3. Load/Save, Logical Operation Instructions
4. Representing MIPS as binary code
5. Instructions for making decisions
Patterson: Sections 2.1 – 2.7.
Levels of
Programming
1.
2.
3.
4.
5.
Recall that a CPU can only
understand binary machine
language program
Writing binary machine
language program is
cumbersome
An intermediate solution is to
write assembly language
program that can easily be
translated (assembled) to binary
language programs
In this course we will cover
MIPS ISA used by NEC,
Nintendo, Silicon Graphics,
and Sony
MIPS is more primitive than
higher level languages with a
very restrictive set of
instructions
High-level
language
program
(in C)
swap(int v[], int k)
{int temp;
temp = v[k];
v[k] = v[k+1];
v[k+1] = temp;
}
C compiler
Assembly
language
program
(for MIPS)
swap:
muli $2, $5,4
add $2, $4,$2
lw $15, 0($2)
lw $16, 4($2)
sw $16, 0($2)
sw $15, 4($2)
jr $31
Assembler
Binary machine
language
program
(for MIPS)
00000000101000010000000000011000
00000000100011100001100000100001
10001100011000100000000000000000
10001100111100100000000000000100
10101100111100100000000000000000
10101100011000100000000000000100
00000011111000000000000000001000
2
Fetch and Execute
1.
2.
Instructions are stored in the form of bits
Programs are stored in memory and are read or written just like data
Processor
3.
Memory
memory for data, programs,
compilers, editors, etc.
Fetch & Execute Cycle
— Instructions are fetched and put into a special register
— Bits in the register "control" the subsequent actions
— Data if required is fetched from the memory and placed in other registers
— Fetch the “next” instruction and continue
3
Registers
1.
2.
3.
4.
Registers are memory cells
In MIPS, data must be in registers before arithmetic operations can be performed
Size of each register is 32 bits, referred to as a word (1 word = 4 bytes = 32 bits)
MIPS has a total of 32 registers
Name Register number
$zero
0
$v0-$v1
2-3
$a0-$a3
4-7
$t0-$t7
8 - 15
$s0-$s7
16 - 23
$t8-$t9
24 - 25
$gp
28
$sp
29
$fp
30
$ra
31
Usage
Constant value of 0
Values for results and expression evaluation
Input arguments to a procedure
Not preserved across procedures (temp)
Preserved across procedure calls
More temporary registers
Global pointer
Stack pointer, points to last location of stack
Frame pointer
Return address from a procedure call
4
Addition & Subtraction
Category
Arithmetic
Instruction
Example
Meaning
Comments
add
add $s1,$s2,$s3
$s1 ← $s2+$s3
overflow detected
subtract
sub $s1,$s2,$s3
$s1 ← $s2-$s3
overflow detected
Example:
C:
f = (g + h) – (i + j);
MIPS Code:
Step 1: Specify registers
containing variables
Step 2: Express instruction in
MIPS
$s0 $s1 $s2 $s3 $s4 $s5 $s6 $s7
$s0 - $s7
$t0 - $t7
MIPS code:
add $t0,$s1,$s2
add $t1,$s3,$s4
sub $t2,$t0,$t1
$t0
$t1
$t2
g+h
i+j
final
# $t0 ← $s1 + $s2
# $t1 ← $s3 + $s4
# $t2 ← $t0 - $t1
g
h
i
j
$t3
$t4
$t5
$t6
$t7
$t8
$t9
5
Memory Organization
1. Memory can be viewed as a large one dimensional
array of cells
2. To access a cell, its address is required
(Addresses are indices to the array)
3. In MIPS, each cell is 1 word (4 bytes) long
4. Each word in a memory has an address, which is a
multiple of 4
5. Length of an address is 32 bits, hence
minimum value of address = 0
maximum value of address = (232 – 1)
6. Data is transferred from memory into registers using
data transfer instructions
Category
Instruction
Processor
12
100
8
10
4
101
0
1
Address
Data
Memory
Example
Meaning
Comments
load word
lw $s1,100($s2)
$s1 ←
memory[$s2+100]
Memory to Register
store word
sw $s1,100($s2)
memory[$s2+100]
← $s1
Register to memory
Data transfer
6
Data Transfer Instructions
Category
Instruction
Example
Meaning
Comments
load word
lw $s1,100($s2)
$s1 ←
Memory to Register
memory[$s2+100]
store word
sw $s1,100($s2)
memory[$s2+100]
Register to memory
← $s2
Data transfer
Example: C instruction: g = h + A[k]
Register Allocation:
A[k]
Address + 4xk
$s1 contains computed value of g; $s2 contains value of h
…
…
$s3 contains base address of array (address of A[0])
A[1]
$s4 contains value of k;
address + 4
MIPS Code:
A[0]
address
add $t1,$s4,$s4
# $t1 = 2 x k
Array
add $t1,$t1,$t1
# $t1 = 4 x k
add $t1,$t1,$s3
# $t1 = address of A[0] + 4 x k
lw $t0,0($t1)
# $t0 = A[k]
Add $s1,$s2,$t0
# $s3 = h + A[k]
100
10
101
1
Data
7
So far we have learned …
MIPS
— loading words but addressing bytes
— addition and subtraction operations on registers only
Instructions
add $s1,$s2,$s3
sub $s1,$s2,$s3
lw $s1,100($s2)
sw $s1,100($s2)
Meaning
#
#
#
#
$s1 = $s2 + $s3 (arithmetic)
$s1 = $s2 – $s3 (arithmetic)
$s1 = Memory[$s2+100] (data transfer)
Memory[$s2+100] = $s1 (data transfer)
Activity 1: Write the MIPS assembly code for the following C assignment instruction
A[12] = h + A[8]
assuming that the variable h is stored in $s2 and the base address of the array A is in $s3.
8
Binary Representation
1.
2.
3.
A computer can only process bits.
Characters, integers, and real numbers must be represented in bits.
Different representation are labeled with a subscript.
— A decimal number is represented by subscript <ten>.
— Binary numbers are represented by subscript <two>.
— Hexadecimal numbers are represented by subscript <hex>.
Examples: 987ten, 1011010two, and 987hex
Case 1: Decimal to Binary Conversion
Example: Convert 445ten into 32-bit binary
Binary Representation:
445ten = 0000 0000 0000 0000 0000 0001 1011 1101two
Case 2: Binary to Decimal Conversion

Example: Convert 0000 0000 0000 0000 0000 0001 1011 1101two to decimal
2 445
2 222 1
2 111 0
2 55 1
2 27 1
2 13 1
2 6 1
2 3 0
1 1
112 23  112 23  10 2 23  112 23  112 23  112 23  112 23  10 2 23  112 23 
8
256
 445 ten
7
128
6
0
5
32
4
16
3
8
2
4
1
0
0
1
9
Hexadecimal Representation (1)
Case 3: Decimal to Hexadecimal Conversion
Example: Convert 445ten into hexadecimal
16 445
16 27 d
1
b
445ten = 000001bdhex in 1 word
Case 4: Hexadecimal to Decimal 
Conversion
Example: Convert 000001bdhex to decimal
1116
 b 16  d 16 
4 2 43 14 2 43 14 2 43
2
256
 445 ten

1
176
0
13
Hexa
0
1
2
3
4
5
6
7
8
9
a
b
c
d
e
f
Decimal
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
10
Hexadecimal Representation (2)
Case 5: Hexadecimal to Binary Conversion
Example: Convert 000001bdhex into binary
{0
 0  0  0  0  0  1  b  d
{
{
{
{
{
{
{
{
0000two
0000two
0000two
0000two
0000two
0000two
0001two
1011two
1101two
Case 6: Binary to Hexadecimal Conversion

Example: Convert 0000 0000 0000 0000 0000 0001 1011 1101two to hexadecimal
 0000  0000  0000  0000  0000  0001  1011  1101
10000
2 3  1 2 3  1 2 3  1 2 3  1 2 3  1 2 3  1 2 3  1 2 3  1 2 3 
0 hex
0 hex
0 hex
0 hex
0 hex
0 hex
1hex
b hex
d hex
Activity 1: Convert 1998ten into binary using the hexadecimal shortcut.

11
2’s Complement (1)
1.
MIPS uses 2’s complement to represent signed numbers
2.
In 2’s complement, a positive number is represented using a 31-bit binary number
— Example: +2ten is represented as 0000 0000 0000 0000 0000 0000 0000 0010two
or 00000002hex
3.
In 2’s complement, a negative number -Xtwo is represented by taking the complement of its
magnitude Xtwo plus 1.
— Example: -2ten
Represent the magnitude in binary format
2ten is represented as
0000 0000 0000 0000 0000 0000 0000 0010two
Take the complement of each digit
The results is
1111 1111 1111 1111 1111 1111 1111 1101two
Add 1 to the LSB
-2ten is represented as 1111 1111 1111 1111 1111 1111 1111 1110two
or fffffffehex
12
2’s Complement (2)
4.
5.
The MSB (32nd bit) is in indication of sign.
To convert a 32-bit number in 2’s complement to decimal
b31 -2  b30  2  b29  2 K  b1 2  b0  2 
31
30
29
1
0
— Example:
0000 0000 0000 0000 0000 0000 0000 0010two is represented by 2
1111 1111 1111 1111 1111 1111 1111 1110two is represented by
1 -2  1 2  1 2 K  1 2  1 2  -2
31
30
29
1
0

13
Unsigned and Signed Arithmetic
MIPS has a separate format for unsigned and signed integers
1. Unsigned integers
— are saved as 32-bit words
— Example: Smallest unsigned integer is 00000000hex = 0ten
Largest unsigned integer is ffffffffhex = 4,294,967,295ten
2. Signed integers
— are saved as 32-bit words in 2’s complement with the MSB reserved for sign
— If MSB = 1, then the number is negative
— If MSB = 0, then the number is positive
— Example:
Smallest signed integer:
1000 0000 0000 0000 0000 0000 0000 0000two
= -(231)10= -2,147,483,64810
Largest signed integer:
0111 1111 1111 1111 1111 1111 1111 1111two
= (231 - 1)10= 2,147,483,64710
14
MIPS to Binary Machine Language (1)
Example: add $t0,$s1,$s2
Binary Machine Language Equivalent:
000000
10001
10010
01000
00000
100000
Can we derive the binary machine language code from the MIPS instruction?
MIPS field for arithmetic instructions:
op
rs
rt
rd
shamt
funct
6 bits
5 bits
5 bits
5 bits
5 bits
6 bits
opcode
1st operand
2nd operand
destination
shift
function
15
MIPS Fields for Arithmetic Operations
op
rs
rt
rd
shamt
funct
6 bits
5 bits
5 bits
5 bits
5 bits
6 bits
opcode
1st operand
2nd operand
destination
shift
function
For arithmetic operations (R):
— Opcode (op) = 0
— Function (funct) = 32 (0x20) for add, 34 (0x22) for sub
Example: add $t0,$s1,$s2 (Values of Registers: $t0 = 8, $s1 = 17, $s2 = 18)
op = 010 = (000000)2
rs = 1710 = (10001)2
rt = 1810 = (10010)2
rd = 810 = (01000)2
shamt is not used = (00000)2
funct = 3210 = (100000)2
leads to the binary machine language code: 000000 10001 10010 01000 00000 100000
16
MIPS Fields for Data Transfer Operations
op
rs
rt
address
6 bits
5 bits
5 bits
16 bits
opcode
1st operand
2nd operand
Memory address (offset)
For data transfer operations (I):
— Opcode (op) = 35 for load (lw) and 43 for save (sw)
Example: lw $t0,32($s3) # (Values of Registers: $t0 = 9, $s3 = 19)
op = 3510 = (100011)2
rs = 1910 = (10011)2
rt = 810 = (01000)2
address = 3210 = (0000 0000 0010 0000)2
leads to the binary machine language code: 100011 10011 01000 0000000000100000
17
Example
Activity 2: Consider the C instruction
A[300] = h + A[300]
A. Write the equivalent MIPS code for the above C instruction assuming $t1 contains the base
address of array A (i.e., address of A[0]) and $s2 contains the value of h
B. Write the binary machine language code for the result in part A.
18
MIPS Branch Instructions for if (1)
1.
2.
3.
Branch if equal to:
beq $s1,$s2,L1
# if $s1 == $s2, go to L1
Branch if not equal to:
bne $s1,$s2,L2
# if $s1 != $s2, go to L2
Unconditional jump:
j L3
# go to L3
Example:
if (i == j) go to L1;
f = g + h;
L1:
f=f–i
Assume that the five variables f, g, h, i, and j are stored in the registers: $s0 to $s4
MIPS Code:
beq $s3,$s4,L1
add $s0,$s1,$s2
L1:
sub $s0,$s0,$s3
# go to L1 if i == j
# f = g + h
# f = f - i
19
MIPS Branch Instructions for if (2)
Example: C instructions
if (i == j)
f = g + h;
else
f = g - h;
Assume that the five variables f, g, h, i, and j are stored in the registers: $s0 to $s4
MIPS Code:
bne $s3,$s4,L1
add $s0,$s1,$s2
j L2
L1:
sub $s0,$s1,$s2
L2:
# go to L1 if i == j
# f = g + h
#
# f = g - h
Activity 3: Write the above code using “branch if equal to” statement?
20
Loops (for)
Example: C instructions
Loop:
g = g + A[i]
i = i + j;
if (i != h) goto Loop;
Assume A is an array of 100 elements and that the compiler associates the variables g, h, i, and j
are stored in the registers: $s1 to $s4. The base address of the array is contained in $s5.
MIPS Code:
Loop:
add $t1,$s3,$s3
add $t1,$t1,$t1
add $t1,$t1,$s5
lw $t0,0($t1)
add $s3,$s3,$s4
bne $s3,$s2,Loop
#$t1 =
#$t1 =
#$t1 =
#$t0 =
#$s3 =
#go to
2 × i
4 × i
address of A[i]
A[i]
i + j
Loop if (i!=h)
21
Loops (while)
Example: C instructions
while (save[i] == k)
i = i + j;
Assume that the variables i, j, and k are stored in the registers: $s3, $s4, and $s5. The base address
of the array (save) is contained in $s6. What is the MIPS code?
MIPS Code:
Loop:
add $t1,$s3,$s3
add $t1,$t1,$t1
add $t1,$t1,$s6
lw $t0,0($t1)
bne $t0,$s5,Exit
add $s3,$s3,$s4
j Loop
#$t1 =
#$t1 =
#$t1 =
#$t0 =
#go to
#$s3 =
#go to
2 x i
4 x i
address of save[i]
save[i]
Exit if save[i]!=k
i + j
Loop
Exit:
22
Loops (case/switch)
Example: C instructions
switch (k) {
case 0: f = i + j; break;
case 1: f = g + h; break;
case 2: f = g – h; break;
case 3: f = I – j; break;
}
Assume that the variables f through k are stored in the registers: $s0 to $s5. The register $t2
contains 4. What is the MIPS code?
To write the MIPS Code for the above code, 2 additional MIPS instructions are introduced
1. Set it less than:
slt $t0,$s3,$s4
# if ($s3<$s4) $t0=1; else $t0=0;
2. Jump register
jr $s3
# jump to address contained in $s3
23
Loops (case/switch)
switch (k) {
case 0: f = i + j; break
case 1: f = g + h; break
case 2: f = g – h; break;
case 3: f = i – j; break;
}
1.
2.
3.
f to k stored $s0 to $s5
$t2 = 4
$t4 contains address
of an array, jumptable
jumbtable[3]
Address of L3
jumptable[2]
Address of L2
jumptable[1]
Address of L1
jumptable[0]
Address of L0
slt $t3,$s5,$zero
bne $t3,$zero,Exit
slt $t3,$s5,$t2
beq $t3,$zero,Exit
add $t1,$s5,$s5
add $t1,$t1,$t1
add $t1,$t1,$t4
lw $t0,0($t1)
jr $t0
L0: add $s0,$s3,$s4
j Exit
L1: add $s0,$s1,$s2
j Exit
L2: sub $s0,$s1,$s2
j Exit
L3: add $s0,$s3,$s4
j Exit
Exit:
#test if k<0
#if k<0, go to Exit
#test if k<4
#if k >=4, go to Exit
#$t1 = 2 * k
#$t1 = 4 * k
#$t1 = &jumptable[k]
#$t0 = jumbtable[k]
#$s0 = (i + j)
#$s0 = (g + h)
#$s0 = (g - h)
#$s0 = (i - j)
24
Summary
Name
Example
32 Registers
$s0,$s1,…$s7, $zero
$t0,$t1,…$t9
$s0-$s7 are preserved across procedures,
$t0-$t9 are not preserved
Memory w/ 230 words
Memory[0], Memory[4], …
Memory[4294967292]
Memory is accessed one word at a time
Category
Arithmetic
Data Transfer
Conditional
branch
Unconditional
jump
Instruction
Comments
Example
Meaning
add
add $s1,$s2,$s3
$s1 ← $s2+$s3
subtract
sub $s1,$s2,$s3
$s1 ← $s2-$s3
load word
lw $s1,100($s2)
$s1 ← Mem[$s2+100]
store word
lw $s1,100($s2)
Mem[$s2+100] ← $s1
branch on equal
beq $s1,$s2,L
if($s1==$s2) go to L
branch not equal
bne $s1,$s2,L
if($s1!=$s2) go to L
set on less than
slt $s1,$s2,$s3
if($s2<$s3) $s1 = 1
else $s1 = 0
jump
j 2500
go to (4 x 2500)
Jump register
jr $ra
go to $ra
Comments
25