Transcript slides in ppt

CS 161
Lecture 4
Prof. L.N. Bhuyan
http://www.cs.ucr.edu/~bhuyan/cs161/index
.html
.1
1999©UCB
While in C/Assembly: Summary
C
while (save[i]==k)
i = i + j;
(i,j,k: $s3,$s4,$s5: base of save[]:$s6)
Loop: add
add
M
add
lw
I
bne
P
S
add
j
$t1,$s3,$s3 #$t1 = 2*i
$t1,$t1,$t1 #$t1 = 4*i
$t1,$t1,$s6 #$t1=Addr
$t1,0($t1) #$t1=save[i]
$t1,$s5,Exit#goto Exit
#if save[i]!=k
$s3,$s3,$s4 # i = i + j
Loop
# goto Loop
Exit:
.2
1999©UCB
If less in C/Assembly
C if (g < h) go to Less
slt $t0,$s0,$s1 # $t0 = 1 if
M
# $s0<$s1 (g<h)
I
# goto Less
P bne $t0,$zero, Less #
if $t0!=0
S
. . .
# (if (g<h))
Less:
A branch if $t0 != 0 branches if g < h.
• Register $zero always 0, so use bne
comparing register $t0 to register $zero
.3
°How test if (g >= h)?
1999©UCB
C case/switch statement
°Choose among four alternatives
depending on whether k has the value
0, 1, 2, or 3
switch (k) {
case 0: f=i+j; break; /* k=0*/
case 1: f=g+h; break; /* k=1*/
case 2: f=g–h; break; /* k=2*/
case 3: f=i–j; break; /* k=3*/
}
.4
1999©UCB
Case/Switch via Jump Address Table
° Notice that last case must wait for n-1 tests
before executing, making it slow
° Alternative tries to go to all cases equally
fast: jump address table for scale-ability
• Idea: encode alternatives as a table of
addresses of the cases
- Table is an array of words with
addresses corresponding to case
labels
• Program indexes into table and jumps
° MIPS instruction “jump register” (jr)
unconditionally branches to address in
register; use load to get address
.5
1999©UCB
Jump Address Table: Summary
slti $t3,$s5,0
#Test if k < 0
bne $t3,$zero,Exit #if k<0,goto Exit
slti $t3,$s5,4
# Test if k < 4
beq $t3,$zero,Exit #if k>=4,goto Exit
add $t1,$s5,$s5
# Temp reg $t1 = 2*k
add $t1,$t1,$t1
# Temp reg $t1 = 4*k
add $t1,$t1,$t2 #$t1=addr JumpTable[k]
lw $t1,0($t1)
# $t1 = JumpTable[k]
jr $t1
# jump based on $t1
L0: add $s0,$s3,$s4 # k=0 so f = i + j
j
Exit
# end case, goto Exit
L1: add $s0,$s1,$s2 # k=1 so f = g + h
j
Exit
# end case, goto Exit
L2: sub $s0,$s1,$s2 # k=2 so f = g – h
j
Exit
# end case, goto Exit
L3: sub $s0,$s3,$s4 # k=3 so f = i – j
Exit:
# end of switch statement
.6
1999©UCB
MIPS Instruction Set Revealed So Far
°MIPS Instructions:
• arithmetic: add, sub, addi, slt, slti
• data transfer: lw, sw
• conditional branch: beq, bne
• unconditional branch: j, jr
°Machine Language Formats:
• R-Register
• I-Immediate
• J- Jump
.7
1999©UCB
2.7 Functions and procedures
• Place parameters in argument registers –
where the procedure can access them
• Transfer control to the procedure
• Acquire storage needed for procedure
• Perform desired task
• Place the result in value registers – where
the calling program can access them
• Return control to the main program by
using jra instruction
.8
1999©UCB
Function Call Bookkeeping
Must consider:
Registers used:
Parameters (arguments) $a0, $a1, $a2, $a3
Return address
$ra
Return value
$v0, $v1
Local variables
$s0, $s1, …, $s7;
Jr $ra – Jump to the address contained in
the return register ra.
.9
1999©UCB
Passing Parameters and Return
C
M
I
P
S
... sum(a,b);... /* a,b:$s0,$s1 */
}
int sum(int x, int y) {
return x+y;
}
Caller Program
Pass up to four parameters in the argument registers: $a0,
$a1, $a2, $a3, and jump to procedure Sum.
1000
1004
1008
1012
1016
add $a0,$s0,$zero # x = a
add $a1,$s1,$zero # y = b
addi $ra,$zero,1016 #$ra=1016
j sum
#jump to sum
... <- Return address
2000 sum: ...
20xx jr $ra
.10
1999©UCB
Instruction Support for Functions
° Want single instruction to jump and save return
address: jump and link (jal):
° Before:
1008 addi $ra,$zero,1016 #$ra=1016
1012 j sum
#go to sum
1016 ...
° After:
1008 jal sum
1012 ...
.11
# $ra=1012,go to sum
1999©UCB
Saving the Register Contents
°
The procedure may use the same registers
that were used by the main (caller) and will
be later needed by the main,so these must be
saved in the stack by the procedure before
using them
°After the procedure completes, load these
values from the stack back to the registers.
Then return to the main by using jr.
°To limit the register spilling, MIPS uses
the following convention.
1. $t0-$t9: 10 temporary registers, not
preserved by the procedure (callee)
2. $s0-s7: 8 saved registers that must be
preserved if used by the procedure.
.12
1999©UCB
Exceeding limits of registers
° Recall: assembly language has fixed number of
operands, HLL doesn’t
° Local variables: $s0, ..., $s7,$t0, …, $t9
• What if more than 18 words of local variables?
° Arguments; $a0, ..., $a3
• What if more than 4 words of arguments?
• More argument registers needed for nested
loops
• More return addresses (Ra) needed for nested
loops
° Place extra local variables and extra arguments
onto stack
.13
1999©UCB
Convert to a Procedure
° Compile by hand using registers:
f = (g + h) - (i + j);
Register Allocations: f: $s0,
$s1, h: $s2, i: $s3, j: $s4
g:
° MIPS Instructions:
add $s0,$s1,$s2
add $t1,$s3,$s4
sub $s0,$s0,$t1
# $s0 = g+h
# $t1 = i+j
# f=(g+h)-(i+j)
If it’s a procedure, g,h,i,j will be passed
through $a0,$a1,$a2,$a3. Registers $s0,and
$t1 need to be saved in the stack.
addi $sp,$sp, -8 # Adjust stack for 2 items
sw $t1, 4($sp) # save register $t1
sw $s0, 0($sp)
add $s0,$a0,$a1
add $t1,$a2,$a3
sub $s0,$s0,$t1
# $s0 = g+h
# $t1 = i+j
# f=(g+h)-(i+j)
Body
add $v0,$s0,$zero # Return value of f
.14
1999©UCB
Restore Registers
Before returning, restore the old values in the
registers
lw $s0, 0($sp)
lw $t1, 4($sp)
addi $sp, $sp, 8 # adjust stack pointer
jr $ra # Jump back to main
.15
1999©UCB
MIPS: Software conventions for Registers
0
zero constant 0
16 s0 callee saves
1
at
. . . (caller can clobber)
2
v0 expression evaluation &
23 s7
3
v1 function results
24 t8
4
a0 arguments
25 t9
5
a1
26 k0 reserved for OS kernel
6
a2
27 k1
7
a3
28 gp Pointer to global area
8
t0
...
reserved for assembler
temporary (cont’d)
temporary: caller saves
29 sp Stack pointer
(callee can clobber)
30 fp
frame pointer
31 ra
Return Address (HW)
15 t7
Plus a 3-deep stack of mode bits.
.16
1999©UCB
Nested Procedures
Call Procedure within procedure.
How to pass arguments?
How to store return address?
The conflicts are solved by pushing all these
registers into the stack.
.17
1999©UCB
The Stack
Before procedure call
$sp
Stack
Stack
$FP
1
2
$sp
$sp
3
4
Stack
During procedure call
stack grows down
1 Saved argument registers (if any, addressed by FP)
2. Saved return address
3. Saved saved registers (if any from nested loops)
4 Local arrays and structures
After procedure Call
$sp always points to “top” stack element and $FP (Frame
Pointer) points to the first word of procedure frame
.18
1999©UCB
2.8 Instruction Support for Characters
°MIPS (and most other instruction sets)
include 2 instructions to move bytes:
• Load byte (lb) loads a byte from memory,
placing it in rightmost 8 bits of a register
• Store byte (sb) takes a byte from rightmost 8
bits of register and writes it to memory
°Declare byte variables in C as “char”
°Assume x, y are declared char, y in
memory at 0($gp) and x at 1($gp).
What is MIPS code for x = y; ?
lb $t0,0($gp)
sb $t0,1($gp)
.19
# Read byte y
# Write byte x
1999©UCB
2.9 What if constant bigger than 16 bits?
°Must keep instructions same size, but
immediate field (addi) only 16 bits
°Add instruction to load upper 16 bits,
then later instruction gives lower 16 bits
• load upper immediate (lui) sets the
upper 16 bits of a constant in a register
• Machine language version of lui $s0,15
001111 00000 10000 0000 0000 0000 1111
op
rs
rt
• Contents of $s0 after executing lui $s0,15
0000 0000 0000 11110000 0000 0000 0000
.20
1999©UCB
Big Constant Example
°C: i = 80000; /* i:$s1 */
°MIPS Asm:
• 80000ten =
0000 0000 0000 0001 0011 1000 1000 0000two
•lui $s1, 1
addi $s1,$s1,14464# 0011 1000 1000 0000
°MIPS Machine Language
001111 00000 10001 0000 0000 0000 0001
001000 10001 10001 0011 1000 1000 0000
$s1:
0000 0000 0000 00010011 1000 1000 0000
.21
1999©UCB