Microsoft PowerPoint – CSE220 Unit04 MIPS Assembly – Branches and Loops.pptx
1
1Kevin McDonnell Stony Brook University – CSE 220
CSE 220:
Systems Fundamentals I
Unit 4:
MIPS Assembly:
Branches and Loops
2Kevin McDonnell Stony Brook University – CSE 220
Branches
• There are no if-statements or loops in MIPS
• Instead there are different kind of branch statements that
direct the CPU to execute instructions out of sequential
order
• In addition to the 32 registers we can use as programmers,
there is also the program counter (PC), which holds the
address of the next instruction to execute
• After an instruction is fetched (the address of which is in
the PC), the value in the PC is incremented by 4 (i.e., 4
bytes)
• The assumption is that the next instruction to execute is in
the neighboring memory cell
• Branch instructions provide a different value to the PC
3Kevin McDonnell Stony Brook University – CSE 220
Types of Branches
• Conditional branches
• The PC is updated if a condition is true
• branch on equal (beq)
• branch on not equal (bne)
• branch on less than zero (bltz)
• many others…
• Unconditional branches
• The PC is changed directly
• jump (j)
• jump register (jr)
• jump and link (jal)
4Kevin McDonnell Stony Brook University – CSE 220
Conditional Branching
• Used for implementing if-statements, switch-statements
and loops
• beq: if two registers have the same data, jump to the
instruction at a provided memory address
• bne: if two registers have different data, jump to the
instruction at a provided memory address
• Example usage:
• beq $a0, $s1, Equal_Case
2
5Kevin McDonnell Stony Brook University – CSE 220
beq Example
addi $s0, $0, 4 # $s0 = 0 + 4 = 4
addi $s1, $0, 1 # $s1 = 0 + 1 = 1
sll $s1, $s1, 2 # $s1 = 1 << 2 = 4 beq $s0, $s1, target # branch is taken addi $s1, $s1, 1 # not executed sub $s1, $s1, $s0 # not executed target: add $s1, $s1, $s0 # $s1 = 4 + 4 = 8 6Kevin McDonnell Stony Brook University – CSE 220 bne Example addi $s0, $0, 4 # $s0 = 0 + 4 = 4 addi $s1, $0, 1 # $s1 = 0 + 1 = 1 sll $s1, $s1, 2 # $s1 = 1 << 2 = 4 bne $s0, $s1, target # branch not taken addi $s1, $s1, 1 # $s1 = 4 + 1 = 5 sub $s1, $s1, $s0 # $s1 = 5 – 4 = 1 target: add $s1, $s1, $s0 # $s1 = 1 + 4 = 5 7Kevin McDonnell Stony Brook University – CSE 220 Conditional Branching • Other conditional branching instructions: • bgez: branch to label if register contains a value greater than or equal to zero • Example: bgez $a0, target • bgtz: branch on greater than zero • blez: branch on less than or equal to zero • bltz: branch on less than zero • bge: branch on greater than or equal to • Example: bge rs, rt, label • Branch to label if rs ≥ rt 8Kevin McDonnell Stony Brook University – CSE 220 Conditional Branching • The four relational operators <,>,≤,≥ are actually
pseudoinstructions
• They can be implemented with the help of the R-type slt
instruction: set on less than
• slt rd, rs, rt
• Set rd to 1 if rs < rt; otherwise, set rd to 0
3
9Kevin McDonnell Stony Brook University – CSE 220
If-statement Example
• Java code: MIPS code:
if (i == j)
f = g + h;
f = f – i;
• Note that the MIPS assembly code tests the opposite case
( ≠ ). You will see this convention used a lot.
# $s0 = f, $s1 = g,
# $s2 = h, $s3 = i,
# $s4 = j
bne $s3, $s4, L1
add $s0, $s1, $s2
L1: sub $s0, $s0, $s3
10Kevin McDonnell Stony Brook University – CSE 220
Unconditional Branching
• An unconditional branch is akin to a “go to” statement
• I’ll show you how to use one in a loop in a few minutes
addi $s0, $0, 4 # $s0 = 4
addi $s1, $0, 1 # $s1 = 1
j target # jump to target
sra $s1, $s1, 2 # not executed
addi $s1, $s1, 1 # not executed
sub $s1, $s1, $s0 # not executed
target:
add $s1, $s1, $s0 # $s1 = 1 + 4 = 5
11Kevin McDonnell Stony Brook University – CSE 220
Unconditional Branching
• The j instruction simply takes an immediate value that
gives part of the address (26 bits) to jump to
• The 32-bit target address is formed by concatenating the
first 4 bits of the PC to the 26-bit immediate after
shifting them 2 bits to the left
• The jr instruction is an R-type instruction that jumps to
the address given in a register
• Example: jr $s0
• Used when returning from function calls
• The jal instruction is used when making a function call
• More on jr and jal in a later Unit
12Kevin McDonnell Stony Brook University – CSE 220
MIPS Program: Find
• Given a in $s0, b in $s1 and c in $s2, find the maximum of
the three and store the maximum in $s3
• Java code: if (a > b)
if (a > c)
max = a;
else
max = c;
else
if (b > c)
max = b;
else
max = c;
4
13Kevin McDonnell Stony Brook University – CSE 220
MIPS Program: Find
# s0 = a, $s1 = b, $s2 = c, $s3 = max
li $s0, 255 # a
li $s1, 11 # b
li $s2, 9 # c
ble $s0, $s1, a_LTE_b # a <= b, so either b or c is max’m
ble $s0, $s2, maxC # a > b but a <= c, so max = c
move $s3, $s0 # a > b and a > c, so max = a
j done
a_LTE_b:
ble $s1, $s2, maxC # a <= b and b <= c, so max = c
move $s3, $s1 # a <= b and b > c, so max = b
j done
maxC:
move $s3, $s2 # max = c
done:
14Kevin McDonnell Stony Brook University – CSE 220
while-loop Example
• Let’ see how to write a while-loop in MIPS
• Java code: MIPS code:
// determines the power
// of n such that 2n = 128
int pow = 1;
int n = 0;
while (pow != 128) {
pow = pow * 2;
n = n + 1;
}
# $s0 = pow, $s1 = n
addi $s0, $0, 1
add $s1, $0, $0
addi $t0, $0, 128
while:
beq $s0, $t0, done
sll $s0, $s0, 1
addi $s1, $s1, 1
j while
done:
15Kevin McDonnell Stony Brook University – CSE 220
for-loop Example #1
• Recall that we typically use for-loops when we know the
exact number of iterations
• Java code: MIPS code:
// add the numbers
// from 0 to 9
int sum = 0;
int i;
for (i=0; i!=10; i++) {
sum = sum + i;
}
# $s0 = i, $s1 = sum
add $s1, $0, $0
add $s0, $0, $0
addi $t0, $0, 10
for: beq $s0, $t0, done
add $s1, $s1, $s0
addi $s0, $s0, 1
j for
done:
16Kevin McDonnell Stony Brook University – CSE 220
for-loop Example #2
Java code: MIPS code:
// sums the powers of
// 2 from 1 to 256
int sum = 0;
int i;
for (i=1; i < 257; i=i*2) { sum = sum + i; } # $s0 = i, $s1 = sum add $s1, $0, $0 addi $s0, $0, 1 addi $t0, $0, 257 loop: slt $t1, $s0, $t0 beq $t1, $0, done add $s1, $s1, $s0 sll $s0, $s0, 1 j loop done: 5 17Kevin McDonnell Stony Brook University – CSE 220 switch-statement Example • Java code: MIPS code: switch (amount) { case 20: fee = 2; break; case 50: fee = 3; break; case 100: fee = 5; break; default: fee = 7; } case20: li $t0, 20 bne $s0, $t0, case50 li $s1, 2 j done case50: li $t0, 50 bne $s0, $t0, case100 li $s1, 3 j done case100: li $t0, 100 bne $s0, $t0, default li $s1, 5 j done default: li $s1, 7 done: 18Kevin McDonnell Stony Brook University – CSE 220 Example: Count # of Ones • Let’s write a MIPS program that counts the number of binary 1s in a 32-bit word num • Java code: counter = 0; position = 1; for (i = 0; i < 32; i++) { bit = num & position; if (bit != 0) counter++; position = position << 1; } 19Kevin McDonnell Stony Brook University – CSE 220 Example: Print First N Primes • Let’s write a program to print the first N prime numbers, where N is hard-coded • It’s helpful first to look a Java implementation and then turn it into MIPS 20Kevin McDonnell Stony Brook University – CSE 220 Example: Leap Year • A year after 1582 is a leap year if it is divisible by 4 with the exception of centenary years (years ending in 00) that are not divisible by 400 • 2015 was not a leap year because 2015 is not divisible by 4 • 1900 was not a leap year because although 1900 is divisible by 100, it is not divisible by 400 • 2000 was a leap year because 2000 is divisible by 400 if (year % 4 != 0) then ordinary_year else if (year%100 == 0) and (year%400 != 0) then ordinary_year else leap_year