COMP273 McGill
1
Decisions in MIPS Assembly Language
• •
All instructions we’ve seen so far allowusto manipulatedata.
To build a computer we must have the ability to make decisions.
COMP273 McGill 2
Decisions in High-Level Languages
• ConditionalStatements:if,if-else,switch • Loops:while,dowhile,for
• Equality and Inequalities: == != < > <= >=
COMP273 McGill 3
Branches
From if-else/switch to assembly
4
Conditional Statement in HLL
// if-else in C/Java
if (condition) clause if (condition) {
clause1 }
else {
clause2
}
// C: Rewrite with goto
if (condition) goto L1 clause2
goto L2
L1: clause1 L2:
COMP273 McGill
5
Same meaning in C No goto in Java
Conditional Branches in MIPS Branch if (registers are) equal: beq reg1, reg2, label
C to MIPS
Branch if (registers are) not equal: bne reg1, reg2, label C to MIPS
// C
if (reg1 == reg2)
goto label1 ;
# MIPS:
# go to label1 if $s1 == $s2 beq $s1 $s2 label1
// C
if (reg1 != reg2)
goto label1 ;
# MIPS
# go to label1 if $s1 != $s2
bne $s1 $s2 label1
COMP273 McGill
6
Unconditional Branch • Jump Instruction: Jump directly to a label
C to MIPS
COMP273 McGill
// C goto
goto label ;
Technically, the following instruction is the same.
There is an important difference. We will see in MIPS representation!
# MIPS jump
j label
# beq version
beq $0, $0, label
Conditional Statement in HLL
// C and Java
if ( i == j ) { f=g+h;
} else { f=g–h;
}
COMP273 McGill
8
Compiling if-else into MIPS
compiler automatically creates labels to handle decisions (branches).
// C and Java
if ( i == j ) { f=g+h;
} else { f=g–h;
}
Registers
$s0
f
$s1
g
$s2
h
$s3
i
l $s4
j
# MIPS
beq $s3 $s4 True # branch i == j sub$s0,$s1,$s2 #f=g–h(false) j Exit # jump to Exit
True:add$s0,$s1,$s2 #f=g+h(true) Exit:
COMP273 McGil
9
The Switch Statement in HLL
Choose among four alternatives
depending on whether k has the value 0, 1, 2 or 3.
// Switch Statement
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 ;
}
// Rewrite it with if-else
if (k==0) f = i + j ; else if (k==1) f = g + h ; else if (k==2) f = g – h ; else if (k==3) f = i – j ;
COMP273 McGill
10
Loops
Q: How did the programmer die in the shower?
A: He read the shampoo bottle instructions: Lather. Rinse. Repeat.
11
Loops in C and Assembly
HLL has three types of
loops: while, do-while, for. Each can be rewritten as the other
MIPS: There are multiple ways to write a loop with conditional branch
COMP273 McGill 12
Loops in HHL: 3 ways
Example: Sum of Series sum = 1 + 2 + 3 + 4 + 5
// for
int i = 1 ; int N = 5 ; int sum = 0 ;
for (i=1 ; i<=N ; i++)
sum += i ;
// do-while
int i = 1 ; int N = 5 ; int sum = 0 ;
do {
sum += i ; i++ ;
} while (i<=N) ;
// while
int i = 1 ; int N = 5 ; int sum = 0 ;
while ( i<=N ) { sum += i ;
i++ ;
}
COMP273 McGill
13
From do-while to goto Example: Sum of Series
sum = 1 + 2 + 3 + 4 + 5
int i = 1 ; int N = 5 ; int sum = 0 ;
// Rewrite it with goto in C
Loop: sum = sum + i ; i=i+1;
if ( i != N )
goto Loop ;
int i = 1 ;
int N = 5 ;
int sum = 0 ;
// do-while loop in C
do {
sum = sum + i ; i=i+1;
} while ( i != N ) ;
COMP273 McGill
14
do-while to goto
From do-while to MIPS assembly do-while to goto
// Rewrite it with goto in C
Loop: sum = sum + i ; i=i+1;
if ( i != N ) goto Loop ;
// do-while loop in C
do {
sum = sum + i ; i=i+1;
} while ( i != N ) ;
# MIPS code
Loop:add $s3,$s3,$s1 #sum=sum+i
addi$s1,$s1,1 #i=i+1
bne $s1,$s2,Loop#gotoLoopifi!=N
Registers
$s1
i
$s2
N
$s3
sum
COMP273 McGill
15
Inequalities
So far, we only test equalities. What about inequalities?
16
Inequalities in MIPS • beq and bne only tested equalities
C to MIPS
• Weneedtotest<,<=,>,>=
C to MIPS
beq $s1 $s2 label1 bne $s1 $s2 label1
if(i< j) if ( i <= j ) if(i> j) if ( i >= j )
COMP273 McGill
17
if ( i == j ) if ( i != j )
• Syntax:
Inequalities in MIPS: slt
slt reg1, reg2, reg3 – Compare reg2 and reg3
– Place the result in reg1
// HLL style
if ( reg2 < reg3 ) reg1 = 1 ;
else
reg1 = 0 ;
COMP273 McGill
Remember “Set on Less Than” From ALU? 18
Inequalities in MIPS: from goto to MIPS
// C
if ( g < h )
goto Less ;
Registers
$s0
g
$s1
h
$t0
# MIPS: branch to Less if $s0 < $s1
slt $t0, $s0, $s1 # if $s0<$s1 (g
MIPS philosophy: Simpler is Better! Can we implement them using just slt and beq/bne
20
Four Combinations of slt and beq/bne
slt$t0,$s0,$s1 #$t0=1if$s0<$s1(g
slt$t0,$s1,$s0 #$t0=1if$s1<$s0(h>g) bne$t0,$0,Gtr #if$t0!=0gotoGtr(g>h)
slt$t0,$s1,$s0 #$t0=1if$s1<$s0(g>h) beq$t0,$0,Leq #if$t0==0,gotoLeq(g<=h)
COMP273 McGill
21
Pseudo-instructions for Inequalities
Too complicated? Good News!
MARS translates pseudo-instructions into MIPS instructions
COMP273 McGill
22
Inequalities with Imediates
23
Immediates in Inequalities
• Syntax:
slti Result Source Immediate
•
•
Result = 1 if Source < Immediate, or 0 otherwise slti is the immediate version of slt
// C
if ( g >= 1 ) goto Loop ;
# MIPS
slti$t0,$s0,1 #$t0=1if$s0<1 beq $t0, $0, Loop # goto Loop if $t0 == 0
OMP273 McGill
24
C
Unsigned Immediates in Inequalities • Syntax:
sltu Result Source1 Source2 sltui Result Source Immediate
• Set result to 1 or 0 depending on unsigned comparisons
# MIPS
slti $t0,$s0,$s1 #$t0=1if$s0<$s1 sltui$t0,$s0, 5 #$t0=1if$s0<5
COMP273 McGill 25
Immediates in Inequalities
Assume
$s0 = 0xFFFF FFFA $s1 = 0x 0000 FFFA
What is value of $t0, $t1?
slt $t0, $s0, $s1 sltu $t1, $s0, $s1
COMP273 McGill
26
Review and More Information
• High-level languages
– Conditional statement: if-else, switch – Loop: while, do-while, for
• MIPSusesconditionalbranches:
– Equality: beq, bne
– Inequality: slt, slti, sltu, sltiu – Jump: j
• Textbook Section 2.7
• TryitoutinMARS COMP273 McGill
27