Transcript Computer ArchitectureII

CMPE 325 Computer
Architecture II
Cem Ergün
Eastern Mediterranean
University
Assembly Language (cont)
Loop Example

Consider the code where array A is an integer
array with 100 elements
Loop:
g = g + A[i]
i = i + j;
if (i != h) goto Loop:
g:
h:
i:
j:
A:
$s0
$s1
$s2
$s3
$s4
CMPE 325 CH #3
Slide #2
Loop Solution

Use a conditional test
Loop:

add $t0, $s2, $s2
add $t0, $t0, $t0
add $t1, $t0, $s4
lw $t2, 0($t1)
add $s0, $s0, $t2
add $s2, $s2, $s3
bne $s2, $s1, Loop
#
#
#
#
#
#
#
$t0 = 2 * i
$t0 = 4 * i
$t1 = &(A[i])
$t2 = A[i]
g = g + A[i]
i = i + j
goto Loop if i!=h
This sequence is known as a basic block since it
has one entrance and one exit
CMPE 325 CH #3
Slide #3
Loops in C

Consider a very similar case with while
while (A[i] == k)
i = i + j;

Use a similar loop as before
Loop:
add $t0, $s0, $s0
add $t0, $t0, $t0
add $t1, $t0, $s3
lw $t2, 0($t1)
bne $t2, $s2, Exit
add $s0, $s0, $s1
j Loop
#
#
#
#
#
#
#
$t0 = 2 * i
$t0 = 4 * i
$t1 = &(A[i])
$t2 = A[i]
goto Exit if !=
i = i + j
goto Loop
Exit:

What is wrong with this approach?
CMPE 325 CH #3
Slide #4
Loop Efficiency

Code uses two
branches/iteration:

Better structure:
Cond?
Body of loop
Body of loop
Cond?
CMPE 325 CH #3
Slide #5
Improved Loop Solution

Remove extra branch
Loop:
Cond:
j Cond
add $s0, $s0, $s1
add $t0, $s0, $s0
add $t0, $t0, $t0
add $t1, $t0, $s3
lw $t2, 0($t1)
beq $t2, $s2, Loop
#
#
#
#
#
#
#
goto Cond
i = i + j
$t0 = 2 * i
$t0 = 4 * i
$t1 = &(A[i])
$t2 = A[i]
goto Loop if ==
Exit:

Reduced loop from 7 to 6 instructions

Even small improvements important if loop executes many
times
CMPE 325 CH #3
Slide #6
Other Comparisons




Other conditional arithmetic operators are useful
in evaluating conditional expressions using <, >,
<=, >=
Conditional expressions also useful in signed vs.
unsigned integers (to be discussed later)
Register is “set” to 1 when condition is met
Consider the following code
if (f < g) goto Less;

Solution
slt $t0, $s0, $s1
bne $t0, $zero, Less
# $t0 = 1 if $s0 < $s1
# Goto Less if $t0 != 0
CMPE 325 CH #3
Slide #7
MIPS Comparisons
Instruction
Example
Meaning
Comments
set less than
slt $1, $2, $3
$1 = ($2 < $3)
comp less than signed
set less than imm slti $1, $2, 100
$1 = ($2 < 100)
comp w/const signed
set less than uns
sltu $1, $2, $3
$1 = ($2 < $3)
comp < unsigned
set l.t. imm. uns
sltiu $1, $2, 100
$1 = ($2 < 100) comp < const unsigned
CMPE 325 CH #3
Slide #8
MIPS Jumps & Branches
Instruction
Example
Meaning
jump
jump register
jump and link
jump and link register
branch equal
branch not eq
branch l.t. 0
branch l.t./eq 0
branch g.t. 0
branch g.t./eq 0
jL
jr $1
jal L
jalr $1
beq $1, $2, L
bne $1, $2, L
bltz $1, L
blez $1, L
bgtz $1, L
bgez $1, L
goto L
goto value in $1
goto L and set $ra
goto $1 and set $ra
if ($1 == $s2) goto L
if ($1 != $2) goto L
if ($1 < 0) goto L
if ($1 <= 0) goto L
if ($1 > 0) goto L
if ($1 >= 0) goto L
CMPE 325 CH #3
Slide #9
Simplicity




Notice that there was no branch less than
instruction for comparing two registers?
The reason is that such an instruction would be
too complicated and would force a longer clock
cycle time
Therefore, conditionals that are not comparing
against zero take at least two instructions where
the first is a set and the second is a conditional
branch
The MIPS assembler supports pseudoinstructions
for such operators and automatically converts
them to the appropriate sequence of MIPS
instructions
CMPE 325 CH #3
Slide #10
Pseudoinstructions


Assembler expands pseudoinstructions
move $t0, $t1
# Copy $t1 to $t0
add $t0, $zero, $t1
# Actual instruction
Some pseudoinstructions need a temporary
register


Cannot use $t, $s, etc. since they may be in use
The $at register is reserved for the assembler
blt $t0, $t1, L1
# Goto L1 if $t0 < $t1
slt $at, $t0, $t1
bne $at, $zero, L1
# Set $at = 1 if $t0 < $t1
# Goto L1 if $at != 0
CMPE 325 CH #3
Slide #11
Pseudoinstructions (cont)

The pseudoinstruction load immediate (li)
provides transfer of a 16-bit constant value to reg
li $t0, imm
# Copy 16bit imm. value to $t0
addi $t0, $zero, imm# Actual instruction

Example: Write a MIPS code to load 076543210h
lui $s0, 07654
# $s0 is set to 076540000 h
addi $s0, $s0,03210 # After addition 076543210 h
CMPE 325 CH #3
Slide #12
Logical Operators


Bitwise operators often useful for converting &&,
||, and ! symbols into assembly
Always operate unsigned (more later)
CMPE 325 CH #3
Slide #13
MIPS Logical Instructions
Instruction
and
or
xor
nor
and immediate
or immediate
xor immediate
shift left log
shift right log
shift right arith
shift left log var
shift right log var
shift right arith
load upper imm
Example
and $1, $2, $3
or $1, $2, $3
xor $1, $2, $3
nor $1, $2, $3
andi $1, $2, 10
ori $1, $2, 10
xori $1, $2, 10
sll $1, $2, 10
srl $1, $2, 10
sra $1, $2, 10
sllv $1, $2, $3
srlv $1, $2, $3
srav $1, $2, $3
lui $1, 40
Meaning
$1 = $2 & $3
$1 = $2 | $3
$1 = $2 $3
$1 = ~($2 | $3)
$1 = $2 & 10
$1 = $2 | 10
$1 = ~$2 & ~10
$1 = $2 << 10
$1 = $2 >> 10
$1 = $2 >> 10
$1 = $2 << $3
$1 = $2 >> $3
$1 = $2 >> $3
$1 = 40 << 16
CMPE 325 CH #3
Comments
Logical AND
Logical OR
Logical XOR
Logical NOR
Logical AND w. constant
Logical OR w. constant
Logical XOR w. constant
Shift left by constant
Shift right by constant
Shift right (sign extend)
Shift left by variable
Shift right by variable
Shift right arith. by var
Places imm in upper 16b
Slide #14
Handling Procedures


Procedures are useful for decomposing
applications into smaller units
Implementing procedures in assembly requires
several things to be done



Space must be set aside for local variables
Arguments must be passed in and return values
passed out
Execution must continue after the call
CMPE 325 CH #3
Slide #15
Procedure Steps
1.
2.
3.
4.
5.
6.
Place parameters in a place where the
procedure can access them
Transfer control to the procedure
Acquire the storage resources needed for the
procedure
Perform the desired task
Place the result value in a place where the
calling program can access it
Return control to the point of origin
CMPE 325 CH #3
Slide #16
Stacks



Stacks are a natural way to temporarily store
data for procedures (as well as call/return
information) since they have a LIFO behavior
Data is pushed onto the stack to store it and
popped from the stack when not longer needed
Implementation


Common rules across procedures required
Recent machines are set by software convention and
earlier machines by hardware instructions
CMPE 325 CH #3
Slide #17
Using Stacks



Stacks can grown up or down
Stack grows down in MIPS
Entire stack frame is pushed and popped, rather
than single elements
CMPE 325 CH #3
Slide #18
Calling a Procedure

To jump to a procedure, use the jal jump-andlink instruction
jal tartget


# Jump and link to label
Saves the address of the next location into to
register-31 and
Jumps to the specified 26-bit local word address
CMPE 325 CH #3
Slide #19
jal and jr Instructions

jal Prod_Addr (J-Type)




first increments the program counter
3
Prod_Addr/4
(PCPC+4),
so that it points to the next location,
then it stores that value into $ra (= $31).
jr $ra


(R-Type)
0 31
copies $ra into PC,
PC$ra causes to jump back
to the stored return address.
CMPE 325 CH #3
0
0
0
8
Slide #20
Who saves the register?

Caller save
All values that have to be kept must be
saved before a procedure is called.

Callee save
Within the procedure all used registers
are saved and afterwards restored.
CMPE 325 CH #3
Slide #21
Argument Passing Convention




Return value is transferred in $v0…$v1.
($v0 and $v1) corresponds to ($2 and $3)
Integer arguments up to four are passed in
registers $a0 … $a3. (= $4 … $7).
Any higher data structure is passed by a pointer.
If there are more than 4 parameters,
 first four parameters are passed in registers,
 the others are transferred in the stack
CMPE 325 CH #3
Slide #22
Register Saving Conventions

Save the registers
saved-registers s0…s7,
 arguments a0 … a3, and
 system registers $gp, $sp, $fp and $ra

before they are corrupted in a call.
 Restore them before the start of calling
code .
CMPE 325 CH #3
Slide #23
Procedure Coding Example
The C code for swap procedure is:
swap(int v[ ], int k)
{
int temp;
temp = v[k];
v[k] = v[k+1];
v[k+1] = temp;
}
Code it in MIPS Assembly.
CMPE 325 CH #3
Slide #24
Coding Example -swap

Allocate registers to procedure variables.

swap(int v[], int k)  two arguments
• pointer v[ ] in $a0 , integer k in $a1.
• $t0, $t1, … for temp. values and addresses

Write MIPS code for the procedure body.
swap(int v[ ], int k)
{
int temp;
temp = v[k];
v[k] = v[k+1];
v[k+1] = temp;
}
 Nothing to save

sll
add
lw
lw
sw
sw
$t1, $a1, 2
$t1, $a0, $t1
$t0, 0($t1)
$t2, 4($t1)
$t2, 0($t1)
$t0, 4($t1)
# $t1  k 4
# $t1  v+(k  4)
# $t0 = v[k]
# $t2 = v[k+1]
# v[k]  $t2 ( = v[k+1] )
# v[k+1]  $t0 (= v[k] )
since only temp.regs corrupted.
none of {$s0…$s7, $a0 …$a3, $sp, $ra} is corrupted
CMPE 325 CH #3
Slide #25
Swap in Final Form

Final form of the procedure
swap:
sll $t1, $a1, 2
add $t1, $a0, $t1
lw $t0, 0($t1)
lw $t2, 4($t1)
sw $t2, 0($t1)
sw $t0, 4($t1)
jr
Label to call the
procedure
# $t1  k 4
# $t1  v+(k  4)
# $t0 = v[k]
# $t2 = v[k+1]
# v[k]  $t2 ( = v[k+1] )
# v[k+1]  $t0 (= v[k] )
return to
caller code
$ra
CMPE 325 CH #3
Slide #26
Nested Calls
A call in another call corrupts $ra.
 $ra must be saved on the stack before
the second call
 and then restored after the return
from the inner call.
CMPE 325 CH #3
Slide #27
Nested Stacks

The stack grows and shrinks downward
A
A:
CALL B
A
B
B:
CALL C
A
B
C
C:
RET
A
B
RET
A
CMPE 325 CH #3
Slide #28
Coding Example: Procedures


Assume x[ ] starts from 10000 and y[ ] starts from
20000.
Code the following program in MIPS Assembler
starting main from address 300, and f from 400.
Main pocedure
.....
j=5
f(j,x);
x[3]+=5;
.....
f procedure
void f(int j, int x[])
{
if (j= =7)
x[2]=6*x[1]–x[0];
else g(y);
}
CMPE 325 CH #3
g procedure
int g(int y[])
{
int i;
for (i=2;i<12;i++) y[i]*=2;
y[2] – = 4;
}
Slide #29
Coding Example –Main Body
Main pocedure
.....
j=5
f(j,x);
x[3]+=5;
.....


allocate registers
• two arguments in f(),  use $a0, $a1
one argument in g()  use $a0
• j and x are saved variables
• in g(), i is local, temporary variable.
• address calculations in temp.registers.
Code for Main
Main:
...
li $a0,5
li $a1,10000
jal f
lw $t0,12($a1)
addi $t0,$t0,5
sw $t0,12($a1)
…
# $t0  x[3]
# $10  x[3] + 5
# x[3]  x[3] + 5
CMPE 325 CH #3
Slide #30
Coding Example Procedure f()
f procedure
void f(int j, int x[])
{
if (j= =7)
x[2]=6*x[1]–x[0];
else g(y);
}
2-words = 8 bytes
$a0 is corrupted
$ra is corrupted
label of
procedure
f:
addi $sp,$sp, -8
sw $a0, 0($sp)
sw $ra, 4($sp)
li $t0,7
bne $a0, $t0, Else
li $t1, 6
lw $t2, 4($a1)
mult $t2, $t1
mflo $t2
lw $t1, 0($a1)
sub $t1, $t2, $t1
sw $t1, 8($a1)
j ExitIf
Else:
li $a0, 20000
jal g
ExitIf:
lw $a0, 0($sp)
lw $ra, 4($sp)
addi $sp,$sp, 8
jr $ra
CMPE 325 CH #3
Callee saves
the registers
# if (j !=7 )
# go to Else.
# $t1 6,
# $t2  x[1]
# LO 6  x[1]
# $t2  6  x[1]
# $t1  x[0]
# $t1  6x[1] – x[0];
# x[2] 6x[1] – x[0];
Callee restores
the registers
return of
procedure f()
Slide #31
Coding Example –
Procedure g()
g() procedure
g:
void g(int y[])
li $t0, 2
Loop:
{
slti $t1, $t0, 12
int i;
beq $t1,$0, ExitF
$t2, $t0, 2
for (i=2;i<12;i++) sll
add $t2, $a0, $t2
lw $t3, 0($t2)
y[i]*=2;
add $t3, $t3,$t3
sw $t3, 0($t2)
y[2] – = 4;
addi $t0, $t0, 1
}
j Loop
Only temporary
registers are used
No registers need
to be saved.
ExitF:
lw $t3, 8($a0)
addi $t3, $t3,–4
sw $t3, 8($a0)
#
$10= i  2 for loop
#
#
#
#
#
#
#
#
#
#
#
#
#
if ( i < 12) then $t11
if ($t1=0) exit for-loop.
$t2  4  i
$t2  y[] + 4  i
$t3  y[i]
$t3  2 y[i]
y[i]  2  y[i]
$t0 = i  i+1
loop again
end of for loop
$t3  y[2]
$t3  y[2] – 4
y[2]  y[2] – 4
jr $31
CMPE 325 CH #3
Slide #32
Decimal Coding of a Program
• coding starts from memory address 300ten.
address
300:
304:
308:
312:
316:
320:
….
F: 400:
404:
408:
412:
416:
420:
424:
428:
432:
436:
440:
444:
448:
Else: 452:
456:
ExitIf: 460:
464:
468:
472:
memory word contents (instruction fields)
opc
rs
rt
rd
sa
fn
8
0
4
5
8
0
5
10000
3
100
35
5
8
12
8
8
8
5
43
5
8
12
…
…
…
…
8
29
29
–8
43
29
4
0
43
29
31
20
8
0
8
7
5
4
8
8
8
0
9
6
35
5
10
4
0
10
9
0
0
35
0
0
0
10
0
18
35
5
9
0
0
10
9
9
0
34
43
5
9
8
2
115
8
0
4
20000
3
119
35
29
4
0
35
29
31
4
8
29
29
8
0
31
0
0
0
8
assembly with
pseudocode
li $a0,5
li $a1,10000
jal f
lw $t0,12($a1)
addi $t0,$t0,5
sw $t0,12($a1)
…
addi $sp,$sp,–8
sw $a0,0($sp)
sw $ra,4($sp)
li $t0,7
bne $4,$t0,Else
li $t1,6
lw $t2,4($a1)
mult $t2,$t1
mflo $t2
lw $t1,0($a1)
sub $t1,$t2,$t1
sw $t1,8($a1)
j ExitIf
li $a0,20000
jal G
lw $a0,0($sp)
lw $ra,4($sp)
addi $sp,$sp,8
jr $ra
CMPE 325 CH #3
assembly without
pseudocode
add $4,$0,5
add $5,$0,10000
jal f
lw $8,12($5)
addi $8,$8,5
sw $8,12($5)
…
addi $29,$29,–8
sw $4,0($29)
sw $31,4($29)
addi $8,7
bne $4,$8,Else
addi $9,$0,6
lw $10,4($5)
mult $10,$9
mflo $10
lw $9,0($5)
sub $9,$10,$9
sw $9,8($5)
j ExitIf
addi $4,$0,20000
jal G
lw $4,0($29)
lw $31,4($29)
addi $29,$29,24
jr $31
100= 400/4
8= (392–360)/4
115= 460/4
119= 476/4
Slide #33
Decimal Coding of a Program-2
• continuation of coding
address
g:
476:
Loop: 480:
484:
488:
492:
496:
500:
504:
508:
512:
ExitF: 516:
520:
524:
528:
...
memory word contents (instruction fields)
opc
rs
rt
rd
sa
fn
8
0
8
2
10
8
9
12
4
0
9
7
0
0
8
10
2
0
0
10
4
10
0
32
35
12
11
0
0
11
11
11
0
32
43
10
11
0
8
8
8
1
2
120
35
4
13
8
8
11
11
–4
43
4
11
8
0
31
0
0
0
8
..
..
..
..
..
..
assembly with
pseudocode
li $t0,2
slti $t1,$t0,12
beq $t1,$0, ExitF
sll $t2,$t0,2
add $t2,$t2,$a0
lw $t3,0($t2)
add $t3,$t3,$t3
sw $t3,0($t2)
addi $t0,$t0,1
j Loop
lw $t3, 8($a0)
addi $t3,$t3,–4
sw $t3, 8($a0)
jr $ra
...
CMPE 325 CH #3
assembly without
pseudocode
addi $8,$0, 2
slti $9,$8,12
beq $9,$0, ExitF
sll $10,$8,2
add $t2,$t2,$4
lw $11,0($10)
add $11,$11,$11
sw $11,0($10)
addi $8,$8,1
j Loop
lw $11, 8($4)
addi $11,$11,–4
sw $11, 8($4)
jr $31
...
7 =(516-488)/4
120 =480/4
Slide #34