[SOLVED] CS compiler assembly Java mips COMP273 McGill

COMP273 McGill
1
Decisions in MIPS Assembly Language

All instructions weve 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=gh;
}
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=gh;
}
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=gh(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=gh; break ; case 3: f=ij; 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-whileint i = 1 ; int N = 5 ; int sum = 0 ;do {sum += i ; i++ ;} while (i<=N) ; // whileint i = 1 ; int N = 5 ; int sum = 0 ;while ( i<=N ) { sum += i ;i++ ;}COMP273 McGill13 From do-while to goto Example: Sum of Seriessum = 1 + 2 + 3 + 4 + 5 int i = 1 ; int N = 5 ; int sum = 0 ;// Rewrite it with goto in CLoop: sum = sum + i ; i=i+1;if ( i != N )goto Loop ; int i = 1 ;int N = 5 ;int sum = 0 ;// do-while loop in Cdo {sum = sum + i ; i=i+1;} while ( i != N ) ; COMP273 McGill14do-while to goto From do-while to MIPS assembly do-while to goto // Rewrite it with goto in CLoop: sum = sum + i ; i=i+1;if ( i != N ) goto Loop ; // do-while loop in Cdo {sum = sum + i ; i=i+1;} while ( i != N ) ;# MIPS codeLoop:add $s3,$s3,$s1 #sum=sum+iaddi$s1,$s1,1 #i=i+1bne $s1,$s2,Loop#gotoLoopifi!=N Registers$s1i$s2N$s3sumCOMP273 McGill15 InequalitiesSo far, we only test equalities. What about inequalities?16 Inequalities in MIPS beq and bne only tested equalitiesC 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 ;elsereg1 = 0 ;COMP273 McGillRemember Set on Less Than From ALU? 18 Inequalities in MIPS: from goto to MIPS// Cif ( g < h ) goto Less ; Registers$s0g$s1h$t0 # MIPS: branch to Less if $s0 < $s1slt $t0, $s0, $s1 # if $s0<$s1 (g , <= and >= ?
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 =h)
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 McGill21 Pseudo-instructions for InequalitiesToo complicated? Good News!MARS translates pseudo-instructions into MIPS instructions COMP273 McGill22 Inequalities with Imediates23Immediates in Inequalities Syntax:slti Result Source ImmediateResult = 1 if Source < Immediate, or 0 otherwise slti is the immediate version of slt // Cif ( g >= 1 ) goto Loop ;
# MIPS
slti$t0,$s0,1 #$t0=1if$s0<1 beq $t0, $0, Loop # goto Loop if $t0 == 0OMP273 McGill24C Unsigned Immediates in Inequalities Syntax:sltu Result Source1 Source2 sltui Result Source Immediate Set result to 1 or 0 depending on unsigned comparisons # MIPSslti $t0,$s0,$s1 #$t0=1if$s0<$s1 sltui$t0,$s0, 5 #$t0=1if$s0<5COMP273 McGill 25 Immediates in InequalitiesAssume$s0 = 0xFFFF FFFA $s1 = 0x 0000 FFFAWhat is value of $t0, $t1?slt $t0, $s0, $s1 sltu $t1, $s0, $s1COMP273 McGill26 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 McGill27