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 = 4beq $s0, $s1, target # branch is takenaddi $s1, $s1, 1# not executedsub$s1, $s1, $s0 # not executedtarget:add$s1, $s1, $s0# $s1 = 4 + 4 = 86Kevin McDonnell Stony Brook University – CSE 220bne Exampleaddi $s0, $0, 4# $s0 = 0 + 4 = 4addi $s1, $0, 1# $s1 = 0 + 1 = 1sll $s1, $s1, 2 # $s1 = 1 << 2 = 4bne $s0, $s1, target # branch not takenaddi $s1, $s1, 1# $s1 = 4 + 1 = 5sub$s1, $s1, $s0# $s1 = 5 – 4 = 1target:add$s1, $s1, $s0# $s1 = 1 + 4 = 57Kevin McDonnell Stony Brook University – CSE 220Conditional 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 ≥ rt8Kevin McDonnell Stony Brook University – CSE 220Conditional 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 039Kevin McDonnell Stony Brook University – CSE 220If-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 = jbne $s3, $s4, L1add $s0, $s1, $s2L1: sub $s0, $s0, $s310Kevin McDonnell Stony Brook University – CSE 220Unconditional 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 minutesaddi $s0, $0, 4 # $s0 = 4addi $s1, $0, 1# $s1 = 1j target# jump to targetsra $s1, $s1, 2 # not executedaddi $s1, $s1, 1 # not executedsub $s1, $s1, $s0# not executedtarget:add $s1, $s1, $s0# $s1 = 1 + 4 = 511Kevin McDonnell Stony Brook University – CSE 220Unconditional 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 Unit12Kevin McDonnell Stony Brook University – CSE 220MIPS 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’mble $s0, $s2, maxC # a > b but a <= c, so max = cmove $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 = cmove $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
jwhile
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
jfor
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 = sumadd$s1, $0, $0addi $s0, $0, 1addi $t0, $0, 257loop: slt $t1, $s0, $t0beq $t1, $0, doneadd$s1, $s1, $s0sll $s0, $s0, 1jloopdone:517Kevin McDonnell Stony Brook University – CSE 220switch-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, 20bne $s0, $t0, case50li $s1, 2j donecase50:li $t0, 50bne $s0, $t0, case100li $s1, 3j donecase100:li $t0, 100bne $s0, $t0, defaultli $s1, 5j donedefault:li $s1, 7done:18Kevin McDonnell Stony Brook University – CSE 220Example: 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 220Example: 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 MIPS20Kevin McDonnell Stony Brook University – CSE 220Example: 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 400if (year % 4 != 0) then ordinary_yearelse if (year%100 == 0) and (year%400 != 0) thenordinary_yearelse leap_year
Reviews
There are no reviews yet.