Transcript branch on not equal

Computer Architecture CSE 3322
Lecture 3
crystal.uta.edu/~jpatters
Assignment: 3.1, 3.2, 3.3, 3.4, 3.10
Due Mon 9/8/03
Read 3:8 – 3.10
Computer Architecture CSE 3322
Graduate Teaching Assistant
Pramod Kumar
Office Hours: Tues – Thurs 10 – 1 pm
114 Engr Annex West
pxk [email protected]
MIPS Assembly Instructions
Instruction Example
add
subtract
Meaning
add $s1, $s2, $s3 $s1 = $s2 + $s3
sub $s1, $s2, $s3 $s1 = $s2 - $s3
$s1, $s2, $s3, … are registers. The $ indicates a Register
in the MIPS Assembly Language
MIPS Assembly Instructions
Instruction Example
Meaning
load word
lw $s1, 300 ($s2) $s1 = Mem[$s2+300]
store word
sw $s1, 300 ($s2) Mem[$s2+300] = $s1
$s1, $s2, $s3, … are registers
300 is a constant
Instructions for Making Decisions
if – then – else Construct
if ( i = = j ) a = b; else a = c;
Yes
No
i = =j
a=b
a= c
Exit:
Instructions for Making Decisions
if – then – else Construct
if ( i = = j ) a=b; else a=c;
beq
Yes
branch on
equal
a=b
No
i = =j
a= c
Exit:
Instructions for Making Decisions
if – then – else Construct
if ( i = = j ) a=b; else a=c;
beq
Yes
branch on
equal
a=b
No
i = =j
branch on not equal
a= c
Exit:
bne
Instructions for Making Decisions
if – then – else Construct
if ( i = = j ) a=b; else a=c;
beq
Yes
branch on
equal
a=b
No
i = =j
branch on not equal
a= c
Exit:
j jump
bne
branch on equal
beq rs, rt, Label
means
if (rs = =rt) go to Label
I type format
op = 4
Instr Format op rs rt
beq
I
4 reg reg
bits
6
5
5
address
“Label”
16
Label is the target statement label. It is an address
that is calculated by the assembler.
branch on equal
means
I type format
beq rs, rt, Label
if (rs = =rt) go to Label
op = 4
branch on not equal bne rs, rt, Label
means
if (rs != rt) go to Label
I type format
op = 5
Label is the target statement label. It is an address
that is calculated by the assembler.
branch on equal
means
I type format
beq rs, rt, Label
if (rs = =rt) go to Label
op = 4
branch on not equal bne rs, rt, Label
means
if (rs != rt) go to Label
I type format
op = 5
jump
means
J type format
j Label
go to Label
op = 2
Label is the target statement label. It is an address
that is calculated by the assembler.
if ( i = = j ) a=b; else a=c;
beq
Yes
No
bne
i = =j
branch on
equal
branch on not equal
a=b
a= c
Exit:
j jump
branch Else
statement 1
j Exit
Else: statement 2
Exit:
#go to Else if ?
#go to Exit
if ( i = = j ) a=b; else a=c;
beq
Yes
No
i = =j
branch on
equal
bne
branch on not equal
a=b
a= c
Exit:
j jump
branch Else
statement 1
j Exit
Else: statement 2
Exit:
#go to Else if ? Most Likely
Case
#go to Exit
if ( i = = j ) a=b; else a=c;
beq
Yes
No
i = =j
branch on
equal
a=b
Exit:
j jump
bne
branch on not equal
a ~ $s1
b ~ $s2
a= c
c ~ $s3
i ~ $s4
j ~ $s5
if ( i = = j ) a=b; else a=c;
beq
Yes
No
i = =j
branch on
equal
a=b
Exit:
j jump
bne $s4, $s5, Else
Else: add $s1, $s3, $zero
Exit:
bne
branch on not equal
a ~ $s1
b ~ $s2
a= c
c ~ $s3
i ~ $s4
j ~ $s5
# go to Else if i!=j
# a=c , Note: $zero is 0
if ( i = = j ) a=b; else a=c;
beq
Yes
No
i = =j
branch on
equal
a=b
Exit:
j jump
bne $s4, $s5, Else
add $s1, $s2, $zero
j Exit
Else: add $s1, $s3, $zero
Exit:
bne
branch on not equal
a ~ $s1
b ~ $s2
a= c
c ~ $s3
i ~ $s4
j ~ $s5
# go to Else if i!=j
# a=b
# go to Exit
# a=c
while ( A[i] >= 0)
i=i+j
MIPS assembly code is:
i ~ $s1
j ~ $s2
base of A ~ $s3
while ( A[i] >= 0)
i=i+j
i ~ $s1
j ~ $s2
base of A ~ $s3
MIPS assembly code is:
Words in an Array A[i]
in memory are 4
•
bytes apart, so the
•
Address increments
•
by 4.
A[3]
A[2]
A[1]
A[0]
Base + 4 * i
Base + 12
Base + 8
Base + 4
Base
while ( A[i] >= 0)
i=i+j
i ~ $s1
j ~ $s2
base of A ~ $s3
MIPS assembly code is:
Loop:
add $t1, $s1, $s1
add $t1, $t1, $t1
# $t1 = 2 * i
# $t1 = 4 * i
while ( A[i] >= 0) i ~ $s1
j ~ $s2
i=i+j
base of A ~ $s3
MIPS assembly code is:
Loop:
add $t1, $s1, $s1
add $t1, $t1, $t1
add $t1, $t1, $s3
# $t1 = 2 * i
# $t1 = 4 * i
# $t1 = addr of A[i]
while ( A[i] >= 0)
i=i+j
i ~ $s1
j ~ $s2
base of A ~ $s3
MIPS assembly code is:
Loop:
add
add
add
lw
$t1, $s1, $s1
$t1, $t1, $t1
$t1, $t1, $s3
$t0, 0 ($t1)
# $t1 = 2 * i
# $t1 = 4 * i
# $t1 = addr of A[i]
# $t0 = A[i]
while ( A[i] >= 0)
i=i+j
i ~ $s1
j ~ $s2
base of A ~ $s3
MIPS assembly code is:
Loop:
slt
add
add
add
lw
$t1, $s1, $s1
$t1, $t1, $t1
$t1, $t1, $s3
$t0, 0 ($t1)
set on less than
# $t1 = 2 * i
# $t1 = 4 * i
# $t1 = addr of A[i]
# $t0 = A[i]
slt rd, rs, rt
means if rs < rt, rd = 1, else rd=0
i ~ $s1
while ( A[i] >= 0) j ~ $s2
i=i+j
base of A ~ $s3
MIPS assembly code is:
Loop:
Exit:
add
add
add
lw
slt
$t1, $s1, $s1
$t1, $t1, $t1
$t1, $t1, $s3
$t0, 0($t1)
$t2, $t0, $zero
# $t1 = 2 * i
# $t1 = 4 * i
# $t1 = addr of A[i]
# $t0 = A[i]
# $t2 = 1 if $t0 < 0
i ~ $s1
while ( A[i] >= 0) j ~ $s2
i=i+j
base of A ~ $s3
MIPS assembly code is:
Loop:
Exit:
add
add
add
lw
slt
bne
$t1, $s1, $s1
$t1, $t1, $t1
$t1, $t1, $s3
$t0, 0 ($t1)
$t2, $t0, $zero
$t2, $zero, Exit
# $t1 = 2 * i
# $t1 = 4 * i
# $t1 = addr of A[i]
# $t0 = A[i]
# $t2 = 1 if $t0 < 0
# if A[i]<0 goto Exit
i ~ $s1
while ( A[i] >= 0)
j ~ $s2
i=i+j
base of A ~ $s3
MIPS assembly code is:
Loop:
Exit:
add
add
add
lw
slt
bne
add
j
$t1, $s1, $s1
$t1, $t1, $t1
$t1, $t1, $s3
$t0, 0 ($t1)
$t2, $t0, $zero
$t2, $zero, Exit
$s1, $s1, $s2
Loop
# $t1 = 2 * i
# $t1 = 4 * i
# $t1 = addr of A[i]
# $t0 = A[i]
# $t2 = 1 if $t0 < 0
# if A[i]<0 goto Exit
#i=i+j
# goto Loop
Case / Switch Statement
switch ( k ) {
case 0: statement 0; break
case 1: statement 1; break
case 2: statement 2; break}
Case / Switch Statement
switch ( k ) {
case 0: statement 0; break
case 1: statement 1; break
case 2: statement 2; break }
if k < 0, then Exit
slt set on less than slt rd, rs, rt
means if rs < rt, rd = 1, else rd=0
Case / Switch Statement
switch ( k ) {
case 0: statement 0; break
case 1: statement 1; break
case 2: statement 2; break }
if k < 0, then Exit
slt set on less than slt rd, rs, rt
means if rs < rt, rd = 1, else rd=0
So, if k ~ $s0
slt $t0, $s0, $zero
# $t0 = 1 if k < 0
bne $t0, $zero, Exit
# goto Exit if k < 0
Case / Switch Statement
switch ( k ) {
case 0: statement 0; break
case 1: statement 1; break
case 2: statement 2; break }
if k < 0, then Exit
slt set on less than slt rd, rs, rt
means if rs < rt, rd = 1, else rd=0
So, if k ~ $s0
slt $t0, $s0, $zero
# $t0 = 1 if k < 0
bne $t0, $zero, Exit
# goto Exit if k < 0
And the test for k > 2 is, assuming $s1 = 3
slt $t0, $s0, $s1
# $t0 = 1 if k < 3
beq $t0, $zero, Exit
# goto Exit if k >=3
Case / Switch Statement
switch ( k ) {
case 0: statement 0; break
case 1: statement 1; break
case 2: statement 2; break }
JumpTable[ k ]
addr of statement 2
addr of statement 1
addr of statement 0
For a given k, place JumpTable[ k ] in register $t0 using
lw instruction
Case / Switch Statement
switch ( k ) {
case 0: statement 0; break
case 1: statement 1; break
case 2: statement 2; break }
JumpTable[ k ]
addr of statement 2
addr of statement 1
addr of statement 0
load JumpTable[ k ] in a register and jump to it
jr jump register jr rs
means go to address in register rs
Case / Switch Statement
switch ( k ) {
case 0: statement 0; break
k is in $s0,
case 1: statement 1; break
Start of JumpTable is
case 2: statement 2; break }
in $t1
slt $t0, $s0, $zero
# $t0 = 1 if k < 0
bne $t0, $zero, Exit
# goto Exit if k < 0
slt $t0, $s0, $s1
# $t0 = 1 if k < 3
beq $t0, $zero, Exit
# goto Exit if k >=3
add $t0, $s0, $s0
# $t0 = 2 * k
add $t0, $t0, $t0
# $t0 = 4 * k
add $t0, $t0, $t1
# $t0 = addr of JumpTable[k]
lw $t2, 0( $t0)
# $t2 = JumpTable[k]
jr $t2
# jump to addr in $t2
Exit:
MIPS Assembly Instructions
add
add $s1, $s2, $s3
$s1 = $s2 + $s3
op
rs
rt
rd
shamt
0
18
19
17
0
subtract
sub $s1, $s2, $s3
op
0
rs
18
funct
32
$s1 = $s2 - $s3
rt
19
rd
17
shamt
0
funct
34
MIPS Assembly Instructions
load word
lw $s1, 300 ($s2)
op
35
rs
rt
address
18
17
300
store word
sw $s1, 300 ($s2)
op
43
$s1 = Mem[$s2+300]
rs
rt
18
17
Mem[$s2+300] = $s1
address
300
MIPS Assembly Instructions
branch on equal
beq $s1, $s2, Label
if ($s1 = =$s2) go to Label
op
rs
rt
address
4
17
18
address
branch on not equal
bne $s1, $s2, Label
op
rs
rt
5
17
18
if ($s1 != $s2) go to Label
address
address
MIPS Assembly Instructions
jump
j Label
go to Label
op
address
2
address
set on less than
slt $s1, $s2, $s3
if $s2 < $s3, $s1 = 1, else $s1=0
op
rs
rt
rd
shamt
funct
0
18
19
17
0
42
MIPS Assembly Instructions
jump register
jr $s1
go to address in register $s1
op
rs
rt
rd
shamt
0
17
0
0
0
funct
8
MIPS Assembly Instructions
Pseudo instructions
Instructions supported by the Assembler but
not implemented in hardware.
Ex: move
multiply
branch less than, less than or equal,
greater than, greater than or equal
MIPS Immediate Addressing
Very common to use a constant in arithmetic operations.
Examples?
Make it faster to access small constants. Keep the
constant in the instruction.
add immediate
addi $s1, $s2, constant
op
rs
rt
$s1 = $s2 + constant
immediate
8
18
17
constant
6
5
5
16
I type of format
The constant can be negative!
MIPS Immediate Addressing
Very common to use a constant in comparison operations.
Examples?
Make it faster to do comparisons. Keep the
constant in the instruction
slt immediate
slti $t0, $s2, constant
rt
$t0 = 1 if $s2 < constant
else $t0 = 0
op
rs
10
18
8
constant
6
5
5
16
I type of format
immediate
Procedure Calls
1. Place parameters where the procedure can access them
Procedure Calls
1. Place parameters where the procedure can access them
2. Transfer control to the procedure
Procedure Calls
1. Place parameters where the procedure can access them
2. Transfer control to the procedure
3. Perform the task of the procedure
Procedure Calls
1.
2.
3.
4.
Place parameters where the procedure can access them
Transfer control to the procedure
Perform the task of the procedure
Place the results where the calling program can access
them
Procedure Calls
1.
2.
3.
4.
Place parameters where the procedure can access them
Transfer control to the procedure
Perform the task of the procedure
Place the results where the calling program can access
them
5. Return control to the point of the call
Procedure Calls
1.
2.
3.
4.
Place parameters where the procedure can access them
Transfer control to the procedure
Perform the task of the procedure
Place the results where the calling program can access
them
5. Return control to the point of the call
Allocate registers to hold data for procedure calls
$a0 - $a3 : four registers to pass parameters
$v0 - $v1 : two registers to return values
$ra
: one return address register
Procedure Calls
1.
2.
3.
4.
Place parameters where the procedure can access them
Transfer control to the procedure
Perform the task of the procedure
Place the results where the calling program can access
them
5. Return control to the point of the call
Allocate registers to hold data for procedure calls
$a0 - $a3 : four registers to pass parameters
$v0 - $v1 : two registers to return values
$ra
: one return address register
Need jump-and-link instruction :
jal ProcedureAddress means :save return address in $ra
and jumps to ProcedureAddress
Procedure Calls
1.
2.
3.
4.
Place parameters where the procedure can access them
Transfer control to the procedure
Perform the task of the procedure
Place the results where the calling program can access
them
5. Return control to the point of the call
Allocate registers to hold data for procedure calls
$a0 - $a3 : four registers to pass parameters
$v0 - $v1 : two registers to return values
$ra
: one return address register
Need jump-and-link instruction :
jal ProcedureAddress means :save return address in $ra
and jumps to ProcedureAddress
How do you return?
Compiling a “leaf” Procedure
(Does not Call another Procedure)
int leaf_example ( int g, int h, int i, int j)
{
int f ;
f=(g+h)–(i+j);
return f ;}
Compiling a “leaf” Procedure
(Does not Call another Procedure)
int leaf_example ( int g, int h, int i, int j)
{
int f ;
f=(g+h)–(i+j);
return f ;}
Assign g to $a0, h to $a1, i to $a2, j to $a3 and f to $v0.
Compiling a “leaf” Procedure
(Does not Call another Procedure)
int leaf_example ( int g, int h, int i, int j)
{
int f ;
f=(g+h)–(i+j);
return f ;}
Assign g to $a0, h to $a1, i to $a2, j to $a3 and f to $v0.
Leaf_example:
add $t0, $a0, $a1 # Temp $t0 = g + h
add $t1, $a2, $a3 # Temp $t1 = i + j
sub $v0, $t0 , $t1 # $v0 = (g+h) – (i+j)
jr $ra
# jump back to calling routine
Compiling a “leaf” Procedure
(Does not Call another Procedure)
int leaf_example ( int g, int h, int i, int j)
{
int f ;
f=(g+h)–(i+j);
return f ;}
Assign g to $a0, h to $a1, i to $a2, j to $a3 and f to $v0.
Leaf_example:
add $t0, $a0, $a1 # Temp $t0 = g + h
add $t1, $a2, $a3 # Temp $t1 = i + j
sub $vo, $t0 , $t1 # $v0 = (g+h) – (i+j)
jr $ra
# jump back to calling routine
What if the calling procedure uses $t0 and $t1?