Transcript Project management - St. Francis Xavier University

CSCI-365
Computer Organization
Lecture 4
Note: Some slides and/or pictures in the following are adapted from:
Computer Organization and Design, Patterson & Hennessy, ©2005
Some slides and/or pictures in the following are adapted from:
slides ©2008 UCB
Loops in C/Assembly
• Compile into MIPS; A[] is an array of ints
do {
g = g + A[i];
i = i + j;
} while (i != h);
• Use this mapping:
g,
h,
i,
j, base of A
$s1, $s2, $s3, $s4, $s5
(done in class)
Loops in C/Assembly
• There are three types of loops in C:
– while
– do… while
– for
• Each can be rewritten as either of the other two, so the
method used in the previous example can be applied to
while and for loops as well
• Key Concept: Though there are multiple ways of writing
a loop in MIPS, the key to decision making is conditional
branch
Inequalities in MIPS
• Until now, we’ve only tested equalities
(== and != in C). General programs need to test < and > as well
• Create a MIPS Inequality Instruction:
– “Set on Less Than”
– Syntax: slt reg1,reg2,reg3
– Meaning:
reg1 = (reg2 < reg3);
if (reg2 < reg3)
reg1 = 1;
else reg1 = 0;
– “set” means “set to 1”,
“reset” means “set to 0”
Same thing…
Register Zero
• The number zero (0), appears very often in code
• MIPS defines register zero ($0 or $zero) to always
have the value 0; eg
add $s0,$s1,$zero (in MIPS)
f = g (in C)
where MIPS registers $s0,$s1 are associated with C variables
f, g
Immediates
• Immediates are numerical constants
• They appear often in code, so there are special
instructions for them
• Add Immediate:
addi $s0,$s1,10 (in MIPS)
f = g + 10 (in C)
where MIPS registers $s0,$s1 are associated with C variables
f, g
• Syntax similar to add instruction, except that last
argument is a number instead of a register
Immediates
• There is no Subtract Immediate in MIPS: Why?
• Limit types of operations that can be done to absolute
minimum
– if an operation can be decomposed into a simpler operation,
don’t include it
– addi …, -X = subi …, X => so no subi
• addi $s0,$s1,-10 (in MIPS)
f = g - 10 (in C)
where MIPS registers $s0,$s1 are associated with C variables
f, g
Inequalities in MIPS
• How do we use this? Compile by hand:
if (g < h) goto Less; #g:$s0, h:$s1
• Answer: compiled MIPS code…
slt $t0,$s0,$s1 #
bne $t0,$0,Less #
#
#
$t0 = 1 if g<h
goto Less
if $t0!=0
(if (g<h)) Less:
• Branch if $t0 != 0  (g < h)
• Register $0 always contains the value 0, so bne and beq often use
it for comparison after an slt instruction.
• A slt  bne pair means if(… < …)goto…
Inequalities in MIPS
• Now, we can implement <, but how do we
implement >, ≤ and ≥ ?
• We could add 3 more instructions, but:
– MIPS goal: Simpler is Better
• Can we implement ≤ in one or more instructions
using just slt and the branches? (done in class)
• What about >? (done in class)
• What about ≥? (done in class)
Immediates in Inequalities
• There is also an immediate version of slt to test against constants:
slti
– Helpful in for loops
C
if (g >= 1) goto Loop
Loop:
M
I
P
S
. . .
slti $t0,$s0,1
beq
$t0,$0,Loop
#
#
#
#
#
$t0 = 1 if
$s0<1 (g<1)
goto Loop
if $t0==0
(if (g>=1))
The For Example
for (i = 0; i < size; i += 1)
array[i] = 0;
// i:$t0, array starts at $a0, size:$a1
addi $t0,$zero,0 # i = 0
loop1: sll $t1,$t0,2
# $t1 = i * 4
add $t2,$a0,$t1 # $t2 = &array[i]
sw $zero, 0($t2) # array[i] = 0
addi $t0,$t0,1
# i = i + 1
slt $t3,$t0,$a1 # $t3 = (i < size)
bne $t3,$zero,loop1 # if (…) goto loop1
Compiling if-then-else Statements
Show a sequence of MIPS instructions corresponding to:
if (i<=j) x = x+1; z = 1; else y = y–1; z = 2*z
// j: $s2, i:$s1, x:$t1, z:$t3, y:$t2,
Solution
Similar to the “if-then” statement, but we need instructions for the
“else” part and a way of skipping the “else” part after the “then” part.
slt
bne
addi
addi
j
else: addi
add
endif:...
$t0,$s2,$s1
$t0,$zero,else
$t1,$t1,1
$t3,$zero,1
endif
$t2,$t2,-1
$t3,$t3,$t3
#
#
#
#
#
#
#
j<i? (inverse condition)
if j<i goto else part
begin then part: x = x+1
z = 1
skip the else part
begin else part: y = y–1
z = z+z
Example: The C Switch Statement
• Choose among four alternatives depending on
whether k has the value 0, 1, 2 or 3. Compile
this C code:
switch (k) {
case 0: f=i+j;
case 1: f=g+h;
case 2: f=g–h;
case 3: f=i–j;
}
break;
break;
break;
break;
/*
/*
/*
/*
k=0
k=1
k=2
k=3
*/
*/
*/
*/
Example: The C Switch Statement
• This is complicated, so simplify
• Rewrite it as a chain of if-else statements, which we
already know how to compile:
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;
• Use this mapping:
f:$s0, g:$s1, h:$s2,
i:$s3, j:$s4, k:$s5
Example: The C Switch Statement
•
Final compiled MIPS code:
bne
add
j
L1:
L2:
L3:
Exit:
$s5,$0,L1
# branch k!=0
$s0,$s3,$s4 # k==0 so f=i+j
Exit
# end of case so Exit
# $t0=k-1
# branch k!=1
# k==1 so f=g+h
# end of case so Exit
# $t0=k-2
# branch k!=2
# k==2 so f=g-h
# end of case so Exit
# $t0=k-3
# branch k!=3
#k==3 so f=i-j
Example: The C Switch Statement
•
Final compiled MIPS code:
bne
add
j
L1: addi
bne
add
j
L2: addi
bne
sub
j
L3: addi
bne
sub
Exit:
$s5,$0,L1
$s0,$s3,$s4
Exit
$t0,$s5,-1
$t0,$0,L2
$s0,$s1,$s2
Exit
$t0,$s5,-2
$t0,$0,L3
$s0,$s1,$s2
Exit
$t0,$s5,-3
$t0,$0,Exit
$s0,$s3,$s4
# branch k!=0
# k==0 so f=i+j
# end of case so Exit
# $t0=k-1
# branch k!=1
# k==1 so f=g+h
# end of case so Exit
# $t0=k-2
# branch k!=2
# k==2 so f=g-h
# end of case so Exit
# $t0=k-3
# branch k!=3
#k==3 so f=i-j
Finding the Maximum Value in a List of Integers
List A is stored in memory beginning at the address given in $s1.
List length is given in $s2.
Find the largest integer in the list and copy it into $t0.
Solution
Scan the list, holding the largest element identified thus far in $t0.
loop:
done: ...
#
#
#
#
#
#
#
#
#
#
#
#
#
initialize maximum to A[0]
initialize index i to 0
increment index i by 1
if all elements examined, quit
compute 2i in $t2
compute 4i in $t2
form address of A[i] in $t2
load value of A[i] into $t3
maximum < A[i]?
if not, repeat with no change
if so, A[i] is the new maximum
change completed; now repeat
continuation of the program
Finding the Maximum Value in a List of Integers
List A is stored in memory beginning at the address given in $s1.
List length is given in $s2.
Find the largest integer in the list and copy it into $t0.
Solution
Scan the list, holding the largest element identified thus far in $t0.
lw
$t0,0($s1)
# initialize maximum to A[0]
addi $t1,$zero,0
# initialize index i to 0
loop: add
$t1,$t1,1
# increment index i by 1
beq
$t1,$s2,done
# if all elements examined, quit
add
$t2,$t1,$t1
# compute 2i in $t2
add
$t2,$t2,$t2
# compute 4i in $t2
add
$t2,$t2,$s1
# form address of A[i] in $t2
lw
$t3,0($t2)
# load value of A[i] into $t3
slt
$t4,$t0,$t3
# maximum < A[i]?
beq $t4,$zero,loop
# if not, repeat with no change
addi $t0,$t3,0
# if so, A[i] is the new maximum
j
loop
# change completed; now repeat
done: ...
# continuation of the program