程序代写代做代考 assembly Java mips Microsoft PowerPoint – CSE220 Unit04 MIPS Assembly – Branches and Loops.pptx

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