### CSE 331. Computer Organization

```Head’s Up

This week’s material

MIPS control flow operations (for, while, if-the-else, …)
- Reading assignment - PH 3.5
Reminders


HW2 is due THIS Friday, September 19th (by 5:00pm).
Please hand in the homework to my office (Core 518).
Next week’s material

- Reading assignment - PH 3.6, A.6 and 3.8
331 Week 3. 1
Fall 2003
Review: MIPS Organization

Arithmetic instructions – to/from the register file

Load/store word and byte instructions – from/to memory
Memory
Processor
1…1100
Register File
5
5
write data
src1
data
32
5
32
registers
(\$zero - \$ra)
32
src2
data
32
32
32 bits
write data
Fetch
32 ALU
Exec
230
words
32
Decode
32
32
32
4
0
(big Endian)
331 Week 3. 2
5
1
6
2
32 bits
7
3
0…1100
0…1000
0…0100
0…0000
(binary)
Fall 2003
Review: MIPS Instructions, so far
Category
Arithmetic
(R format)
Instr
Op Code
Example
Meaning
0 and 32
\$s1 = \$s2 + \$s3
subtract
0 and 34
sub \$s1, \$s2, \$s3
\$s1 = \$s2 - \$s3
Data
35
lw
\$s1, 100(\$s2)
\$s1 = Memory(\$s2+100)
transfer
store word
43
sw \$s1, 100(\$s2)
Memory(\$s2+100) = \$s1
(I format)
32
lb
\$s1, 101(\$s2)
\$s1 = Memory(\$s2+101)
store byte
40
sb \$s1, 101(\$s2)
Memory(\$s2+101) = \$s1
331 Week 3. 3
Fall 2003
Instructions for Making Decisions

Decision making instructions



alter the control flow
i.e., change the "next" instruction to be executed
Why do we need decision making instructions?
if (i==j) h = i + j;

MIPS conditional branch instructions:
bne \$s0, \$s1, Label
beq \$s0, \$s1, Label

#go to Label if \$s0\$s1
#go to Label if \$s0=\$s1
Example: if (i==j) h = i + j;
331 Week 3. 4
Fall 2003
Assembling Branches

Instructions:
bne \$s0, \$s1, Label
beq \$s0, \$s1, Label


#go to Label if \$s0\$s1
#go to Label if \$s0=\$s1
Machine Formats:
6 bits
5 bits
5 bits
op
rs
rt
5
16
17
????
4
16
17
????
16 bit number
I format
How is the branch destination address specified?
331 Week 3. 5
Fall 2003
Specifying Branch Destinations
bne \$s0,\$s1,Lab1


but that would require a 32 bit field
Lab1:
...
331 Week 3. 6
Fall 2003
Specifying Branch Destinations

Could use a register (like lw and sw) and add to
it the 16-bit offset

which register?
- Instruction Address Register (PC = program
counter)
- its use is automatically implied by instruction
- PC gets updated (PC+4) during the fetch cycle so
that it holds the address of the next instruction
bne \$s0,\$s1,Lab1
PC
Lab1+PC:
...

limits the offset to -215 to +215-1 from the
(instruction after the) branch instruction, but
- most branches are local anyway (principle of
locality)

One optimization
- Each instruction is 4 bytes long, and only word
address is necessary (multiple of 4)
- We can right shift the offset by 2 bits (divided by
4), and store the value
- Essentially, it can cover -217 to +217-1 offset
331 Week 3. 7
Fall 2003
Disassembling Branch Destinations

The contents of the updated PC (PC+4) is added to
the low order 16 bits of the branch instruction which
is converted into a 32 bit value by



concatenating two low-order zeros to create an 18 bit
number Why??
sign-extending those 18 bits
The result is written into the PC if the branch
condition is true prior to the next Fetch cycle
from the low order 16 bits of the branch instruction
16
offset
sign-extend
00
32
PC
32
331 Week 3. 8
32
4
32
32
branch dst
32
?
Fall 2003
Assembling Branches Example

Assembly code
bne \$s0, \$s1, Lab1
...
Lab1:

Machine Format of bne:

op
rs
rt
5
16
17
16 bit offset
I format
Remember

After the bne instruction is fetched, the PC is updated to

Two low-order zeros are concatenated to the offset number and
that value sign-extended is added to the (updated) PC
331 Week 3. 9
Fall 2003
MIPS Organization
Processor
Memory
Register File
5
5
write data
5
1…1100
src1
data
32
32
registers
(\$zero - \$ra)
src2
32 data
32
32
32 bits
br offset
32
Fetch
PC = PC+4
Exec
PC
4
32
32
32
write data
32
Decode
230
words
32
32 ALU
32
32
4
0
5
1
6
2
32 bits
7
3
0…1100
0…1000
0…0100
0…0000
(binary)
(big Endian)
331 Week 3. 10
Fall 2003
Another Instruction for Changing Flow

MIPS also has an unconditional branch instruction or
jump instruction:
j

label
Example:
331 Week 3. 11
#go to label
if (i!=j)
h=i+j;
else
h=i-j;
Fall 2003
Assembling Jumps


Instruction:
j label
Machine Format:
op
2

#go to label
J format
????
How is the jump destination address specified?

As an absolute address formed by
- concatenating the upper 4 bits of the current PC (now PC+4) to
- concatenating 00 as the 2 low-order bits
331 Week 3. 12
Fall 2003
Disassembling Jump Destinations

to create a 32 bit instruction address that is placed
into the PC prior to the next Fetch cycle
from the low order 26 bits of the jump instruction
26
00
32
32
PC
331 Week 3. 13
32
Fall 2003
Assembling Branches and Jumps

Assemble the MIPS machine code (in decimal is fine) for the
following code sequence. Assume that the address of the beq
Lab1:
Lab2:
331 Week 3. 14
beq
j
sub
...
\$s0, \$s1, Lab1
\$s3, \$s0, \$s1
Lab2
\$s3, \$s0, \$s1
Fall 2003
Compiling While Loops

Compile the assembly code for the C while loop
where i is in \$s0, j is in \$s1, and k is in \$s2
while (i!=k)
i=i+j;
331 Week 3. 15
Fall 2003
More Instructions for Making Decisions

We have beq, bne, but what about branch-if-lessthan?

New instruction:
slt \$t0, \$s0, \$s1

# if \$s0 < \$s1
#
then
# \$t0 = 1
#
else
# \$t0 = 0
Machine format:
op
0
331 Week 3. 16
rs
rt
16
17
rd
8
funct
0
42 = 0x2a
Fall 2003
2
Other Branch Instructions

Can use slt, beq, bne, and the fixed value of 0 in
register \$zero to create all relative conditions

less than
blt \$s1, \$s2, Label

less than or equal to
greater than
great than or equal to
ble \$s1, \$s2, Label
bgt \$s1, \$s2, Label
bge \$s1, \$s2, Label



As pseudo instructions (get to practice with some of
them in HW#2) - recognized (and expanded) by the
assembler

The assembler needs a reserved register (\$at)

331 Week 3. 17
there are policy of use conventions for registers
Fall 2003
Another Instruction for Changing Flow

Most higher level languages have case or switch
statements allowing the code to select one of many
alternatives depending on a single value.

Instruction:
jr

\$t1
Machine format:
331 Week 3. 18
op
rs
0
9
funct
0
0
0
8 = 0x08
Fall 2003
2
Compiling a Case (Switch) Statement
switch (k) {
case 0: h=i+j;
case 1: h=i+h;
case 2: h=i-j;
331 Week 3. 19
break; /*k=0*/
break; /*k=1*/
break; /*k=2*/
Fall 2003
Instructions, so far
Category
Instr
Op Code
Example
Meaning
Arithmetic
0 and 32
\$s1 = \$s2 + \$s3
(R format)
subtract
0 and 34
sub \$s1, \$s2, \$s3
\$s1 = \$s2 - \$s3
Data
35
lw
\$s1, 100(\$s2)
\$s1 = Memory(\$s2+100)
transfer
store word
43
sw \$s1, 100(\$s2)
Memory(\$s2+100) = \$s1
(I format)
32
lb
\$s1, 101(\$s2)
\$s1 = Memory(\$s2+101)
store byte
40
sb
\$s1, 101(\$s2)
Memory(\$s2+101) = \$s1
br on equal
4
beq \$s1, \$s2, L
if (\$s1==\$s2) go to L
br on not equal
5
bne \$s1, \$s2, L
if (\$s1 !=\$s2) go to L
set on less than
0 and 42
slt
\$s1, \$s2, \$s3
if (\$s2<\$s3) \$s1=1 else
\$s1=0
2
j
2500
go to 10000
jump register
0 and 8
jr
\$t1
go to \$t1
3
jal
2500
go to 10000; \$ra=PC+4
Cond.
Branch
Uncond.
Jump
331 Week 3. 20
jump
Fall 2003
Procedures
int leaf_example (int g, int h, int i, int j) {
int
f;
f = (g+h) – (i+j);
return f;
}
CALLEE
void main(){
int
f;
f = leaf_example(1, 2, 3, 4);
f ++;
}
331 Week 3. 21
CALLER
Fall 2003
Six Steps in Execution of a Procedure

Main routine (caller) places actual parameters in a
place where the procedure (callee) can access
them

\$a0 - \$a3: four argument registers

Caller transfers control to the callee

Callee acquires the storage resources needed


Callee places the result value in a place where the
caller can access it


\$v0 - \$v1: two value registers for result values
Callee returns control to the caller

331 Week 3. 22
origin
Fall 2003
Instruction for Calling a Procedure

MIPS procedure call instruction (caller):
jal



Saves PC+4 in register \$ra
Then (callee) can do procedure return with just
jr
331 Week 3. 23
\$ra
#return
Fall 2003
Compiling a Procedure
int leaf_example (int g, int h, int i, int j) {
int
f;
f = (g+h) – (i+j);
return f;}
331 Week 3. 24
Fall 2003
MIPS Register Convention
Name
Register
Number
\$zero
\$v0 - \$v1
\$a0 - \$a3
\$t0 - \$t7
\$s0 - \$s7
\$t8 - \$t9
\$gp
\$sp
\$fp
\$ra
0
2-3
4-7
8-15
16-23
24-25
28
29
30
31
331 Week 3. 25
Usage
the constant 0
returned values
arguments
temporaries
saved values
temporaries
global pointer
stack pointer
frame pointer
Should
preserve on
call?
no
no
yes
no
yes
no
yes
yes
yes
yes
Fall 2003
Spilling Registers

Where does the callee save those registers?

it uses a stack – a last-in-first-out queue

top of stack
\$sp
One of the general registers,
\$sp, is used to address the
stack (which “grows” from

add data onto the stack – push
\$sp = \$sp – 4
data on stack at new \$sp

331 Week 3. 26
remove data from the stack – pop
data from stack at \$sp
\$sp = \$sp + 4
Fall 2003
A Quick Aside

MIPS instruction for adding immediate values:
#\$sp = \$sp + 4
#\$sp = \$sp - 4

Another version of add in which one operand is a
constant where the constant is kept inside the
instruction itself

MIPS pseudoinstruction for multiplying:
mul

\$v0, \$a0, \$v0
#\$v0 = \$a0 * \$v0
We will look at the machine representations for these
instructions in the next lecture
331 Week 3. 27
Fall 2003
Nested Procedures

What happens to return addresses with nested
procedures?
int rt_1 (int i) {
if (i == 0) return 0;
else return rt_2(i-1); }
caller: jal rt_1
next:
. . .
rt_1:
to_2:
rt_2:
331 Week 3. 28
bne
jr
jal
jr
\$a0, \$zero, to_2
\$v0, \$zero, \$zero
\$ra
\$a0, \$a0, -1
rt_2
\$ra
. . .
Fall 2003
Nested Procedures Outcome
caller: jal rt_1
next:
. . .
rt_1:
to_2:
rt_2:

bne
jr
jal
jr
\$a0, \$zero, to_2
\$v0, \$zero, \$zero
\$ra
\$a0, \$a0, -1
rt_2
\$ra
. . .
On the call to rt_1, the return address (next in the
caller routine) gets stored in \$ra. What happens to
the value in \$ra (when i != 0) when rt_1 makes
a call to rt_2?
331 Week 3. 29
Fall 2003

Nested procedures (i passed in \$a0, return value in
\$v0)
old TOS
 \$sp
\$ra

rt_1: bne
\$a0, \$zero, to_2
jr
sw
sw
jal
bk_2: lw
lw
jr
\$v0,
\$ra
\$sp,
\$ra,
\$a0,
\$a0,
rt_2
\$a0,
\$ra,
\$sp,
\$ra
\$zero, \$zero
\$sp, -8
4(\$sp)
0(\$sp)
\$a0, -1
0(\$sp)
4(\$sp)
\$sp, 8
Save the return address (and arguments) on the stack
331 Week 3. 30
Fall 2003
Compiling a Recursive Procedure

Calculating factorial:
int fact (int n) {
if (n < 1) return 1;
else return (n * fact (n-1)); }

Recursive procedure (one that calls itself!)
fact (0) = 1
fact (1) = 1 * 1 = 1
fact (2) = 2 * 1 * 1 = 2
fact (3) = 3 * 2 * 1 * 1 = 6
fact (4) = 4 * 3 * 2 * 1 * 1 = 24
...

Assume n is passed in \$a0; result returned in \$v0
331 Week 3. 31
Fall 2003
Compiling a Recursive Procedure
sw
sw
slt
beq
jr
\$sp,
\$ra,
\$a0,
\$t0,
\$t0,
\$v0,
\$sp,
\$ra
L1:
\$a0, \$a0, -1
#n >=1, so decrement n
fact
#call fact with (n-1)
is where fact returns
\$a0, 0(\$sp)
#restore argument n
\$ra, 4(\$sp)
\$sp, \$sp, 8
\$v0, \$a0, \$v0
#\$v0 = n * fact(n-1)
\$ra
jal
#this
bk_f: lw
lw
mul
jr
331 Week 3. 32
\$sp, -8
4(\$sp)
0(\$sp)
\$a0, 1
\$zero, L1
\$zero, 1
\$sp, 8
#save argument n
#test for n < 1
#if n >=1, go to L1
#else return 1 in \$v0
Fall 2003
A Look at the Stack for \$a0 = 2
old TOS
 \$sp
\$ra
\$a0
\$v0
331 Week 3. 33
Fall 2003
Review: MIPS Instructions, so far
Category
Instr
Op Code
Example
Meaning
Arithmetic
0 and 32
\$s1 = \$s2 + \$s3
(R format)
subtract
0 and 34
sub \$s1, \$s2, \$s3
\$s1 = \$s2 - \$s3
Data
35
lw
\$s1, 100(\$s2)
\$s1 = Memory(\$s2+100)
transfer
store word
43
sw \$s1, 100(\$s2)
Memory(\$s2+100) = \$s1
(I format)
32
lb
\$s1, 101(\$s2)
\$s1 = Memory(\$s2+101)
store byte
40
sb
\$s1, 101(\$s2)
Memory(\$s2+101) = \$s1
br on equal
4
beq \$s1, \$s2, L
if (\$s1==\$s2) go to L
br on not equal
5
bne \$s1, \$s2, L
if (\$s1 !=\$s2) go to L
set on less than
0 and 42
slt
\$s1, \$s2, \$s3
if (\$s2<\$s3) \$s1=1 else
\$s1=0
2
j
2500
go to 10000
jump register
0 and 8
jr
\$t1
go to \$t1
3
jal
2500
go to 10000; \$ra=PC+4
Cond.
Branch
Uncond.
Jump
331 Week 3. 34
jump
Fall 2003
```