Transcript Instruction Set

Goal: Implement Functions in Assembly
When executing a procedure (function in C) the
program must follow the next 6 steps:
1. Place parameters in a place the procedure can
access them.
2. Jump to the procedure code.
3. Allocate storage needed for the procedure.
4. Perform the task.
5. Place the result(s) in a place the calling program
can access.
6. Return to the point of origin.
Computer
Structure - The Instruction Set (2)
1/17
Registers for Procedures
MIPS software allocates the following of its
32 registers for procedure calling:
$a0 - $a3: 4 argument registers
$v0 - $v1: 2 return value registers
$ra: return address register to return to point of origin.
2 new instructions that support procedures are:
jal ProcedureAddress
Jump and link, jump to the procedure and save the
address of the following instruction in $ra.
jr register
Jump register, jump to the address in the register.
Computer
Structure - The Instruction Set (2)
2/17
Using More Registers
If the compiler needs more than the 4 input
and 2 output registers, it can use other registers.
But it must restore the values in those registers to
the values before the procedure was called.
This is a case of register spill, register values are
saved in memory.
The ideal structure for saving registers is the stack,
values are pushed onto the stack before the
procedure call and poped out after.
A register called the stack pointer ($sp) points to
the address in memory where the stack resides.
Computer
Structure - The Instruction Set (2)
3/17
Compiling a Leaf Procedure
int leaf(int g,int h,int i,int j){
int f;// the arguments are in $a0-$a3,
f=(g+h) - (i+j); //f is in $s0
return f;
}
Before continuing we will introduce a new instruction:
addi $t0,$t0,10# $t0=$t0+10
add immediate (addi) has as one of its operands an
immediate value. addi is of the I-type instructions
and in fact gives the format its name.
Computer
Structure - The Instruction Set (2)
4/17
The Assembly Version
subi $sp,$sp,12#make room for 3 items on stack
sw
$t1,8($sp) #save $t1
sw
$t0,4($sp) #save $t0
sw
$s0,0($sp) #save $s0
add $t0,$a0,$a1 # $t0=g+h
add $t1,$a2,$a3 # $t1=i+j
sub $s0,$t0,$t1 # f=$t0+$t1
add $v0,$s0,$zero # $v0=$s0
lw
$s0,0($sp) #restore $s0
lw
$t0,4($sp) #restore $t0
lw
$t1,8($sp) #restore $t1
addi $sp,$sp,12#remove the room on the stack
jr
$ra
#jump back to point of origin
Computer Structure - The Instruction Set (2)
Picture of Stack
High address
$sp
$sp
Contents of register $t1
Contents of register $t0
$sp
Low address
a.
Contents of register $s0
b.
c.
MIPS software offers 2 classes of registers:
$t0-$t9: 10 temporary registers, not saved by the
procedure.
$s0-$s7: 8 saved registers, saved by the
procedure.
Computer
Structure - The Instruction Set (2)
6/17
Procedures
that don't call others are called leaf
Nested Procedures
procedures, procedures that call others are called
nested procedures.
Problems may arise now, for example the main
program calls procedure A with the argument 3 in
$a0 and the return address in $ra. Procedure A
then calls procedure B with the argument 7 in $a0
and with its return address in $ra. The previous
address saved in $ra is destroyed.
We must, somehow, preserve these values across
calls.
Lets look at a translation of the recursive factorial
function in C++.
Computer
Structure - The Instruction Set (2)
Factorial in C++
int fact(int n)
{
if(n < 1)
return (1);
else
return (n * fact(n -1));
}
The function calls itself multiple times.
The argument n is in register $a0, which is saved
on the stack along with $ra.
Computer
Structure - The Instruction Set (2)
7/17
Factorial in Assembly
fact: subi $sp,$sp,8 # make room for 2 items
sw
$ra,4($sp)# push the return address
sw
$a0,0($sp)# push the argument n
slt $t0,$a0,1 # test for n<1
beq $t0,$zero,L1 # if n>=1 goto L1
li
$v0,1 # pseudoinstruction $v0=1
addi $sp,$sp,8 # pop 2 items off stack
jr
$ra
The following is the recursive call to fact(n-1)
L1:
subi $a0,$a0,1 # n-jal fact # call fact(n-1)
lw
$a0,0($sp) # return from fact(n-1)
lw
$ra,4($sp) # pop n and return address
addi $sp,$sp,8 # pop 2 items off stack
mult $v0,$a0,$v0 # return n * fact(n-1)
jr
$ra
Computer
Structure
- The Instruction Set (2)
The
stack above
$sp is preserved ( ‫ ) נשמר‬by
Procedure
Frame
making sure that the callee ( ‫ ) פונקציה נקראת‬doesn't
write above $sp.
$sp is preserved by adding exactly the amount
subtracted from it.
All other registers are preserved by being saved on
the stack.
The stack also contains local variables that don't fit
into registers.
The segment of the stack containing the saved
registers and local variables is called the procedure
frame or activation record.
Computer
Structure - The Instruction Set (2)
Frame Pointer
Some MIPS software use the register $fp to
point to the first word of the
procedure frame or activation record.
High address
$fp
$fp
$sp
$sp
$fp
Saved argument
registers (if any)
Saved return address
Saved saved
registers (if any)
Local arrays and
structures (if any)
$sp
Low address
Computer
Structure
- The Instruction
b. Set (2)
a.
c.
9/17
Static and Automatic Variables
C++ has two storage classes for variables
automatic and static.
Automatic variables are local to a function and are
deleted when the function exits.
Static variables exist across function calls. Global
C++ variables are static, as well as any variables
defined with the keyword static. All other
variables are automatic.
MIPS software reserves a register called the global
pointer or $gp. Static variables are accessed
through this register.
Computer
Structure - The Instruction Set (2)
10/17

As mentioned before
the I-format instruction contains a 16 bit
Immediate
Operands
constant called an immediate. Using I-type instructions
avoids loading values from memory into a register. Examples
of instructions which use immediate values are:
multi $s0,$s1,4 # $s0=$s1*4
slti $t0,$s2,10 # $t0=1 if $s2<10
 But if a constant is larger than 16 bits? MIPS provides an
instruction lui that loads a 16 bit constant into the upper
half of an register.
In order to load the value:
0000 0000 0011 1101 0000 1001 0000 0000
into $s0 we must perform:
lui
$s0,61 #61d = 0000 0000 0011 1101
addi $s0,$s0,2304 # 2304d = 0000100100000000
Computer
Structure - The Instruction Set (2)
Addressing in Branches and Jumps
j 10000 # go to location 10000
Jumps to the address 10000 in memory.
2
10000
6 bits (opcode)
26 bits (address)
bne $s0,$s1,Exit # branch if $s0!=$s1
5
16
17
Exit
6 bits 5 bits 5 bits
16 bits (address)
Problem: Addresses have to fit into a 16-bit field, no
program could be larger than 64KByte.
Solution: Specify a register which would be added
to the branch address. But which register?
Computer
Structure - The Instruction Set (2)
11/17
PC-Relative Addressing
The Program Counter (PC) is a register that
always contains the address of the current
instruction being executed.
By using the PC as the register to add to the branch
address we can always branch within a range of
-215 to 215-1 bytes of the current instruction.
This is enough for most loops and if statements.
This is called PC-relative addressing.
Procedures are not usually within a short range of
the current instruction and thus jal is a J-type
instruction.
Computer
Structure - The Instruction Set (2)
12/17
Branch Offset in Machine Language
 Lets look at a loop in assembly:
Loop: .
.
bne $t0,$t1,Exit
subi $t0,$t0,1
j
Loop
Exit:
 The machine code of the bne instruction is:
5
8
9
8
 The branch instruction adds 8 bytes to the PC and not 12 because
the PC is automatically incremented by 4 when an instruction is
executed.
 In fact the branch offset is 2 not 8. All MIPS instructions are 4 bytes
long thus the offset is in words not bytes. The range of a branch
has been multiplied by 4.
Computer
Structure - The Instruction Set (2)
13/17
Branch Offset Example
48
subi $t0,$t1,1035
52
bne $zero,$t0,L1
. . .
76 L1: jr
$ra
What is the machine code translation of bne?
opcode: 5, the opcode of bne.
rs: 0, $zero is register #0.
rt: 9, $t0 is register #9.
address: (L1 - PC)/4 = (76 - 56)/4 = 20/4 = 5
And if L1 is at address 28?
address: (L1 - PC)/4 = (28 - 56)/4 = -28/4 = -7
Computer
Structure - The Instruction Set (2)
14/17
Pseudodirect Addressing
The 26-bit field in the jump instruction is
also a word address. Thus it is a 28-bit
address. But the PC holds 32-bits?
The MIPS jump instruction replaces only the lower
28 bits of the PC, leaving the 4 highest bits of the
PC unchanged.
 48
. . .
334500
j
L2
L2: add …
What is the machine code translation of j?
opcode: 2, the opcode of j.
address: PC32-29 || 83625
Computer
Structure - The Instruction Set (2)
15/17
Addressing Mode Summary
Immediate addressing - the Operand is a constant
Register addressing - the Operand is a register
Base or displacement addressing - the operand is
at the memory location whose address is the sum of
a register and a constant in the instruction.
PC-relative addressing - the address is the sum of
the PC and a constant in the instruction.
Pseudodirect addressing - the jump address is the
26 bits of the instruction concatenated ( ‫ ) מצורף‬to
the upper bits of the PC.
Computer
Structure - The Instruction Set (2)
16/17
 Immediate addressing - the Operand is a constant
addi $t0,$t1,102 # $t0=$t1 + 10
andi $s0,$s0,16 # $s0=$s0 & 16
 Register addressing - the Operand is a register
addi $t0,$t1,102
andi $s0,$s0,16
jr
$s4
# jump to the address in $s4
 Base or displacement addressing - the operand is at the memory location
whose address is the sum of a register and a constant in the instruction.
lw $t0,20($gp) # $t0 = $gp[5]
lb $t1,7($s5) # $t0 = $s5[7]
 PC-relative addressing - the address is the sum of the PC and a constant
in the instruction.
beg $s0,$s1,Label # if $s0<$s1 jump to Label
 Pseudodirect addressing - the jump address is the 26 bits of the
instruction concatenated ( ‫ ) מצורף‬to the upper bits of the PC.
j
L37
jal strcmp
Addressing Modes (picture)
1. Immediate addressing
op
rs
rt
Immediate
2. Register addressing
op
rs
rt
rd
...
funct
Registers
Register
3. Base addressing
op
rs
rt
Memor y
Address
+
Register
Byte
Halfword
Word
4. PC-relative addressing
op
rs
rt
Memor y
Address
PC
+
Word
5. Pseudodirect addressing
op
Address
PC
Computer
Structure - The Instruction Set (2)
Memor y
Word
17/17