ITEC 460 - Chapter 9 Notes
MIPS - A RISC Architecture
- RISC: Reduced Instruction Set
- All instructions 32 bits
- Simple instructions
- Simple addressing modes
- Limited memory access instructions
- Many registers
- Many instructions use registers
- vs CISC: Complex Instruction Set
- Instructions different sizes
- Complex instructions
- Many addressing modes
- Many instructions access memory
- Few registers
- Many instructions use registers or memory
Registers
- Special purpose memory pointers:
- Book Mnemonic name = spim name
- $FP = $fp = frame pointer - points to top of current call frame
- $SP = $sp = stack pointer - points to top (ie next open spot) of stack
- $ESP = $t4 = expression stack pointer - points to top (ie next open
spot) of expression stack - used in expression evaluation - Mnemonic not
available in spim
- Other Special Purpose:
- $result = $v0 - result of a function is stored here prior to return and
retrieved after return
$return = $ra - jal loads return address here, jr $ra
used to return from a method call - must be preserved across a method call
- $zero = $zero - special register that holds 32 bit 0
- $ACC = $t0 - General purpose register used to simulate an accumulator
register (ie keep top of expression stack in $ACC)
- General Purpose: $t1, $t2, $t3
SPIM Instructions - From Text
- Memory Access
- lw rt, offset($reg) - eg
lw $t1, -4($sp)
- sw rt, offset($reg) - eg
sw $t1, 4($fp)
- Register always first
- memory address specified with offset($reg)
- Only way to access memory
- Arithmetic - 3 register
- add rd, rs, rt
- sub rd, rs, rt
- Arithmetic - immediate
- addi rd, rs, imm
- example: addi $t1, $t2, 4
- example: addi $sp, $sp, -16
- Immediate values are specified in the asm instruction (and stored
directly in the machine language instruction)
- Arithmetic - Multiply and Divide
- mult rs, rt
- 32 bit operands give 64 bit result in special registers HI and LO
- mflo rd - moves 32 bit result from LO into destination register rd
- If result HI is not zero, an overflow has occurred (who checks?)
- div rs, rt - Divide rs by rt and put quotient in LO and remainder in HI
Jump Instructions (from text)
- j target - jump to target
- target is a label
- numeric value of target is calculated by the assembler (or simulator)
- jal target - like jump, and return address is loaded into $ra
- return address is the current value of $pc
- jr rs - jump to the address found in register rs - typically used to
return from a method (eg
jr $ra
SLT (from text)
- slt rd, rs, rt --- rd = rs < rt - true=1, false=0
- loads sign bit of (rs - rt) into rd
Conditional Branches: beq and bne (from text)
- beq rs, rt, target --- branch to label target if rs == rt
- bne rs, rt, target --- branch to label target if rs /= rt
- Offset from branch to target calculated by assembler and stored in instruction
- Typically used with slt and $zero
- Example:
blt $1, $2, t
slt $3, $1, $2 # $3 := $1 < $2
bne $3, $0, t # if $1 < $2 /= false goto t
Example: bgt $1, $2, t
slt $3, $2, $1 # $3 := $2 < $1
bne $3, $0, t # if $2 < $1 /= false goto t
Example: bge $1, $2, t
slt $3, $1, $2 # $3 := $1 < $2
beq $3, $0, t # if $1 < $2 == false goto t
Or use synthetic versions!
Conditional Branch: bltz and bgez (from text)
- bltz rs, target --- branch to target if rs < 0
- bgez rs, target --- branch to target if rs ≥ 0
- Offset from branch to target calculated by assembler
and stored in instruction
Relational Operators
- eq --- beq rd, rs, rt
- ne --- bne rd, rs, rt
- lt - blt is a synthetic instruction
- le - ble is a synthetic instruction
- gt - bgt is a synthetic instruction
- ge - bge is a synthetic instruction
Other Instructions (Not in book)
- Some additional instructions you can use
and rd, rs, rt
andi rd, rs, immed
or rd, rs, rt
ori rd, rs, immed
slti rt, rs, immed
mfhi rd
mfhi rd - for mult - check for overflow; for div - not needed
since we don't have a remainder operator
Synthetic Instructions (Not in book)
- Some synthetic instructions you can use
li $t1, 5 # load value 5 into register t1
ble rs, rt, target
blt rs, rt, target
bge rs, rt, target
bge rs, rt, target
move rd, rs
Load Address: Loads the address of a memory location into a register
- Presumably the location is specified using a label
- Example:
.data # Part of asm program that contains data
newline: .asciiz "\n"
.text # part of asm program that contains code
la $a0, newline # load address of string newline into $a0
li $v0, 4
syscall
Synthetic instructions are not available on the processor, but they are provided by the assembler or the interpreter
They are provided by translating them into equivalent instructions that the processor has
AKA pseudo instructions
Simple Tiling: Constants
-
AAT node: constant(5)
- Equivalent asm code:
li $t1, 5
sw $t1, 0($ESP)
addi $ESP, $ESP, -4
Simple Tiling: Arithmetic Operation
li $t1, 3 # Store first operand
sw $t1, 0($ESP)
addi $ESP, $ESP, -4
li $t1, 6 # Store second operand
sw $t1, 0($ESP)
addi $ESP, $ESP, -4
lw $t1, 8($sp) # Get first operand
lw $t2, 4($sp) # Get second operand
add $t1, $t1, $t2 # Do the op
sw $t1, 8($sp) # Store result
addi $ESP, $ESP, 4 # Book has add here
What happens with the stack:
sp4=sp1: 3 (replaced by 9 after operations)
sp2: 6
sp3: open
Sequence of changes:
put 3 at sp1, move to sp2
put 6 at sp2, move to sp3
get 3 and 6 from stack, add, put 9 on stack
move $sp to sp4
We allow writing to the second stack element and then adjusting
the stack pointer in order to shorten the generated assembly code
Later we will minimize use of the stack by keeping the top of the
stack in $ACC, something like this:
load 3 into ACC
store 3 on stack, $sp := $sp - 4
load 6 into ACC
get 3 from stack into $t1
add ACC, ACC, $t1
$sp := $sp + 4 -- to remove the second element (ie the 3)
Simple Tiling: Registers
- AAT Node: Register(FP)
- Action: Push current contents of FP onto the expression stack
- Code:
sw $fp, 0($esp)
addi $esp, $esp, -4
Another Example AAT:
operation: -
Register(fp)
constant 8
Resulting Asm:
sw $fp, 0($esp) # push $fp
addi $esp, $esp, -4
li $t1, 8 # push 8
sw $t1, 0($esp)
addi $esp, $esp, -4
lw $t1, 8($esp) # get and add top 2 stack values
lw $t2, 4($esp)
sub $t1, $t1, $t2
lw $t1, 8($esp) # store result
addi $esp, $esp, 4 # adjust stack pointer (remove one value)
# Book has add
Simple Tiling: Relational Operations (relops)
Operator: >
Constant(3)
Constant(5)
Generate code to test (5 < 3)
Assume stack is:
3 <<< top + 8
5 <<< top + 4
<<< top
Resulting Asm Code:
lw $t1, 8($esp) # get 3 from stack
lw $t2, 4($esp) # get 5 from stack
slt $t1, $t2, $t1 # $t1 := $t2 < $t1 (ie 5 < 3)
sw $t1, 8($sp)
addi $esp, $esp, 4 # adjust stack pointer (remove one value)
Common use of stack!
Simple Tiling: Relops continued
Operator: ==
Constant(3)
Constant(5)
Equivalent to: (5 ≤ 3) && (3 ≤ 5)
Generate code to test: !( (5 > 3) || (3 > 5) )
Generate code to test: !( (3 < 5) || (5 < 3) )
Assume stack is:
3 <<< top + 8
5 <<< top + 4
<<< top
Resulting Asm Code:
lw $t1, 8($esp) # get 3 from stack
lw $t2, 4($esp) # get 5 from stack
slt $t3, $t2, $t1 # $t3 := $t2 < $t1 (ie 5 < 3)
slt $t2, $t1, $t2 # $t2 := $t1 < $t2 (ie 3 < 5)
add $t1, $t2, $t3 # What values can this take? (BOOK ERROR)
sub $t1, $0, $t1 # $t1 := 1 - $t1
addi $t1, $t1, 1
sw $t1, 8($sp) # Result goes on stack
addi $esp, $esp, 4 # adjust stack pointer (remove one value)
Or use subtraction and branch
Remember: when x ∈ {0, 1}, 1-x = !x
Simple Tiling: Boolean Operations
- Books Solution:
- Remember: boolean values are 0 and 1
- and: x and y == (x+y > 1)
- or: x or y == (x+y > 0)
- not: !x == (1 - x)
- Alternate solution: and, andi, or, ori,
Simple Tiling: Memory Access
Memory
-
Register(FP)
Constant(12)
Resulting Assembly Code:
sw $fp, 0($esp) # push $fp
addi $esp, $esp, -4
li $t1, 12 # push 12
sw $t1, 0($esp)
addi $esp, $esp, -4
lw $t1, 8($esp) # $t1 := $fp from stack ERROR IN BOOK
1w $t2, 4($esp) # $t2 := 12 from stack ERROR IN BOOK
sub $t1, $t1, $t2 # calculate $fp - 12
sw $t1, 8($esp) # put address $fp - 12 on stack
addi $esp, $esp, 4 # set top back one spot
lw $t1, 4($esp) # $t1 := address
lw $t1, 0($t1) # load from specified address
sw $t1, 4($esp) # put memory contents onto stack
# replacing address on top
Simple Tiling: Function Calls
Call("foo")
constant(3)
constant(9)
Resulting Assembly Code
li $t1, 9 # push 9 on expr stk
sw $t1, 0($esp)
addi $esp, $esp, -4
li $t1, 3 # push 3 on expr stk
sw $t1, 0($esp)
addi $esp, $esp, -4
lw $t1, 4($esp) # copy 3 (param 1) from expr stk to call stack
sw $t1, 0($sp)
lw $t1, 8($esp) # copy 9 (param 2) from expr stk to call stack
sw $t1, -4($sp)
addi $sp, $sp, -8 # update top of $sp (to include 2 values)
addi $esp, $esp, 8 # update top of $esp (to remove 2 values)
jal foo
addi $sp, $sp, 8 # remove the params from call stack
sw $result, 0($esp) # push result on expr stack
addi $esp, $esp, -4
Remember that the return value needs to be placed on the stack (since they
will be use in expressions, such as in i := 2 * f(x);
Simple Tiling: Label Trees
- Example AAT: Label("label1")
- Resulting Assembly Code:
label1:
Simple Tiling: Move Trees - Move Into a Register
- Join two tiles
- Example AAT 1 - load constant into a register:
Move
Register($r1) # r1 represents any register
constant(5)
Tile move and register together
Resulting Asm code:
li $t1, 5 # push value onto stack
sw $t1, 0($esp)
addi $esp, $esp, -4
lw $r1, 4($esp) # load value into register
addi $esp, $esp, 4 # update esp to remove value from stack
Example AAT 2 - load from memory into a register:
Move
Register($r1) # r1 represents any register
memory
register($fp)
Resulting Asm code:
sw $fp, 0($esp) # push address from $fp
addi $esp, $esp, -4
lw $t1, 4($esp) # get destination address for move
lw $r1, 4($t1) # load value from memory into register
addi $esp, $esp, 4 # update esp to remove value from stack
Example AAT 3 - load value in a register into a register:
Move
Register($r1) # r1 and r2 represent any registers
Register($r2)
Resulting Asm code: ...
Simple Tiling: Move Trees - move to memory
Move
memory
register($fp)
constant(5)
Tile move and memory together
Resulting Asm code:
sw $fp, 0($esp) # push address from $fp
addi $esp, $esp, -4
li $t1, 5 # push value to move
sw $t1, 0($esp)
addi $esp, $esp, -4
lw $t1, 8($esp) # get destination address for move
lw $t2, 4($esp) # get value to move
sw $t2, 0($t1) # store the value
addi $esp, $esp, 8 # remove both values from stack
Simple Tiling: Jump Trees
Jump("label")
Resulting Assembly Code:
j label
Simple Tiling: Conditional Jump Trees
CondJump("jumpLab")
lt Operator <
constant(3)
constant(5)
Resulting Assembly Code:
li $t1, 3 # push first expression value
sw $t1, 0($esp)
addi $esp, $esp, -4
li $t1, 5 # push second expression value
sw $t1, 0($esp)
addi $esp, $esp, -4
lw $t1, 8($esp) # get expression values from stack
lw $t2, 4($esp)
slt $t1, $t1, $t2 # compare expression values
sw $t1, 8($esp) # store boolean result on stack
addi $esp, $esp, 4 # remove one expression value from stack
lw $t1, 4($esp) # get boolean result from stack
addi $esp, $esp, 4 # and update stack
bgtz $t1, jumplab # branch if boolean result was true
Simple Tiling: Sequential Trees
- What ASM code needed for sequential trees???
Simple Tiling: Call Statements
- What ASM code needed for Call Statements ???
- No return value!
Procedure Calls (Code for Caller and Called)
- A java version of the program: subs.java
(and prettified)
- Check out this program: subs.s
(and prettified)
- A textual description of the stack while in method b: subsStk.txt
- Procedure call actions:
- In caller:
- put params on stack
- Adjust stack pointer to include params
- jal method
- Adjust stack pointer to remove params
- Do something to return value
- In called method:
- Save $ra, $fp, $sp on stack - storage locations must allow
space for the locals in the called routine
- Adjust stack pointer to include saved registers and space
for saved registers
- For any return statement in the program:
- move return value (if there is one) into $v0
- Branch to routine end label
- At end of called method
- Allocate label to jump to
- Restore values of $sp, $ra, $fp (don't modify the $fp until
you are done with it!)
More Complex Tiling: Using the Accumulator Register
- The ACC will serve as the top of the stack!
- The stack serves as an buffer for values calculated by the code for
a tree
- If a node has one subtree, the value for that subtree is stored on the top
of the stack and then the node retrieves the value from the stack
- If a node has two subtrees, the values for those subtrees are stored on the top
of the stack and then the node retrieves the two values from the stack
- When the accumulator is used,
- If a node has one subtree, the code for the subtree saves the value for that
subtree in the accumulator and the code for the node gets it out of the
accumulator
- If a node has two subtree, the code for the left subtree saves the
value for that subtree in the accumulator and the code for the node gets it out of the
accumulator and saves it on the stack, then the code for the right subtree
saves the value for that subtree in the accumulator. Then
the value for the left subtree is retrieved from the stack into a temporary, and
then both values (ie the accumulator and the temporary) are used by the node
Constants with Accumulator
li $ACC, 5
Register Expressions with Accumulator
move $ACC, $r1 # synthetic instruction
Binary Operators with Accumulator
Operator +
Constant(3)
Constant(7)
Resulting Assembly code
li $ACC, 3 # Get value of left operand into ACC
sw $ACC, 0($esp) # Store ACC on stack (to use ACC for right op)
addi $esp, $esp, -4
li $ACC, 7 # Get value of right operand into ACC
lw $t1, 4($esp) # Get value of left operand from stack
addi $esp, $esp, 4 # Remove left op from stack
add $ACC, $t1, $ACC # Add and keep result in ACC
Memory Access with Accumulator
- Without the Accumulator, the address that is to be accessed
is the result value from an AST. This result value
is stored on top value on the stack
- With the Accumulator, the address to access is the result value from an AST.
This result value is stored in the Accumulator
- Example:
lw $t1, 0($ACC)
Move into a Register using the Accumulator
Move
Register(r1)
...
Resulting Code:
# Code to load value into ACC
move $r1, $ACC # Synthetic instruction
Move into Memory using the Accumulator
Move
memory
register($fp)
constant(5)
Tile move and memory together
Resulting Asm code:
move $ACC, $fp # push address from $fp
sw $ACC, 0($esp)
addi $esp, $esp, -4
li $ACC, 5
lw $t1, 4($esp) # get destination address for move
addi $esp, $esp, 4 # remove address from stack
sw $ACC, 0($t1) # store the value
Procedure and Function Calls
- Differences from previous version:
- In previous version, each argument was calculated and then stored
on the expression stack, after which all of the arguments were moved from the
expression stack to the call stack. When using the accumulator, each value is
calculated into the accumulator and the accumulator is immediately
stored on the call stack
- The result of a function call is stored in the accumulator rather than on
the expression stack
- Example:
foo(3, 9);
- AAT:
Call("foo")
constant(3)
constant(9)
Resulting Assembly Code
li $ACC, 3 # push first operand on call stk
sw $ACC, 0($sp)
li $ACC, 9 # push second operand on call stk
sw $ACC, -4($sp)
addi $sp, $sp, -8 # update top of call stack (to include 2 args)
jal foo
addi $sp, $sp, 8 # remove the params from call stack
move $ACC, $result # push result on expr stack
In general, the code looks like this:
# code for first argument
sw $ACC, 0($sp)
# code for second argument
sw $ACC, -4($sp)
# code for nth argument
sw $ACC, -[4n-4]($sp)
addi $sp, $sp, -[4n] # update top of call stack (to include n args)
jal foo
addi $sp, $sp, [4n] # remove the n args from call stack
move $ACC, $result # load result into ACC
Conditional Jumps with Accumulator
- Conditional jumps simply examine the accumulator
- Example:
# Code for conditional expression
bgtz $ACC, target # jump if ACC contains true
New Expressions, using the Accumulator
- Implement
ASTExpression allocate(AATExpression size)
page 213
- Use function
allocate as defined in the code for the library
defined in the file Codegenerator.java
- The code generated for this library is listed here
- In this code, the number of bytes is passed as a parameter to
allocate.
- The variable
HEAPPTR contains a pointer to the top of the
heap.
- The structure of memory is as follows (assume stack size is 4 * 1000
bytes):
Definition from class CodeGenerator:
private final int STACKSIZE = 1000;
Memory structure:
$esp >>> Expression Stack top (Original stack top)
... 4000 bytes for expr stk ...
$sp >>>> Stack top
... 4000 bytes for call stk ...
HEAPPTR >>> Heap bottom
... Remaining space is available for the heap
>>>> Data section - data allocations, using .data
... program data, including:
cr: .asciiz "\n"
sp: .asciiz " "
HEAPPTR: .word 0
>>>> Text section - code defined using .text
... program machine code
We are doing no garbage collection
The following notes are not needed since we can use the author's code
Use register $t8 as a pointer to next open heap space
We will call $t8 the "heap pointer"
Initialize: move $t8, 4($gp) # 4 past the global pointer
Example: new int[n]
Generated code:
# Assume n is in $ACC
li $t1, 4 # assume 4 byte ints
mult $ACC, $t1
mflo $t1 # size of array
move $ACC, $t8 # value of expression is current heap pointer
add $t8, $t8, $t1 # update heap pointer
The value of the expression (ie $ACC) will be saved in the stack as a local
variable
We treat that heap like a stack that is never popped (ie no garbage
collection)
To allocate an instance of a class, the size of the class, in words,
must be in $ACC. The size of a class object will have to be calculated
Read, Print, Println, using the Accumulator
li $v0, 1 # Specify that syscall is to print an int
move $a0, $ACC # int to print
syscall
Println
.data
newline: .asciiz "\n"
.text
li $v0, 4 # Specify that syscall is to print a string
la $a0, newline # load address of string newline into $a0
syscall
Other Statements
- Other Statements are unchanged when using the Accumulator
Larger Tiles
- All previous examples (except one) have used one tile per AST node
- Special cases can be coded that recognize larger tiles
- See examples of move on page 237, 329
- See examples of conditional jump on pages 238, 240
- Recursively tile rest of tree after choosing largest to tile
- Always possible to complete tree, regardless of first choice
Using Constants for the Stack
- It's possible to minimize updating the stack pointer
- Use offsets from the stack pointer
- Update offsets, but NOT stack pointer
- and don't adjust stack pointer
- See examples on pages 241, 242
- Stack pointer must be adjusted across call statements
- See examples on pages 241 - 243
Using More Registers
- Assume you are using stack pointer offsets
- Initialize offset to wordsize * numberOfRegisters
- When doing a push or pop,
- when offset is negative, use the stack
- when offset is positive, use a register. Use offset to find register
index
- See example pages 243 and 244
Using a Single Stack
- The Expression Stack is not needed
- See diagram page 244
Extended Example
Topic
Topic
Topic
Topic
Last modified on