Lecture 6: Instruction Set Architectures III

Last Time
Machine state (memory, computation, control)
Design principles
Instruction formats
Representing and addressing data
Today
Take QUIZ 3 before 11:59pm today over Chapter 2
readings
Quiz 2: 100% - 19; 75% - 19; 50% - 13; 25% - 3
ISA III
In/out of Memory and Registers
Program counter (PC) control
MIPS assembly connected to high-level programming
UTCS 352 Lecture 6 1

ISA Design Principles

1. Simplicity favors regularity

e.g., instruction size, instruction formats, data formats
eases implementation by simplifying hardware
2. Smaller is faster
fewer bits to read, move, & write
use/reuse the register file instead of memory
3. Make the common case fast
e.g., small constants are common, thus immediate fields
can be small
4. Good design demands compromise
special formats for important exceptions
e.g., a jump far away (beyond a small constant)

UTCS 352 Lecture 6 2

1
 ISA Specifies
How the Computer Changes State

Instruction formats
instruction
Instruction types
Addressing modes Op Mode Ra Rb

Memory Memory
Byte Addr Byte Addr
Little Endian R0-R31 Little Endian R0-R31
32-bit addr 32 bit 32-bit addr 32 bit

PC PC
Before State After State
Machine state includes
PC, memory state register state

UTCS 352 Lecture 6 3

Design Considerations:
Changes to Machine State Imply Instruction Classes & Design

Changes to Memory State

Data representation
ALU Operations
arithmetic (add, sub, mult, div)
logical (and, or, xor, srl, sra)
data type conversions(cvtf2d,cvtf2i) Memory
Data movement Byte Addr
Little Endian R0-R31
memory reference (lb, lw, sb, sw) 32-bit addr 32 bit
register to register (movi2fp, movf)
Control: what instruction to do next
PC = ??
tests/compare (slt, seq) PC
branches and jumps (beq, bne, j, jr) Machine State
procedure calls (jal, jalr)
operating system entry (trap)

UTCS 352 Lecture 6 4

2
 High Level Program in C
xFFFF
int x [10] ; Memory
void foo(int a) {
stack
int j ;
Stack
for(j=1; j<10; j++) a
j
x[j] = a * x [j-1]; SP
bar(a);
}
Data movement in/out registers and memory heap
memory reference (lb, lw, sb, sw)
register to register (movi2fp, movf) x

Control bar
What instruction does the machine do next?
foo

x0000
UTCS 352 Lecture 6 5

Registers

Registers are faster Memory Hierarchy

than cache & memory
ALU
Level 1 cache is faster
than level 2, & so on Registers
Memory hierarchies
are effective because L1 Cache
programs have locality
& regularity
Temporal locality: reuse
L2 Cache
of same location
Spatial locality: reuse of Memory
nearby locations
UTCS 352 Lecture 6 6

3
 General Registers
Any register may hold values or
addresses FFF
simpler PC
more orthogonal (opcode
independent of register usage) Memory Rn-1

More fast local storage

but.addresses and data must R1
be same size (32 bits) 0
R0

How many?
More - fewer loads and stores
But - more instruction bits Machine State

MIPS: 32 registers
ISA Register conventions Op i j k
All ALU/Control instructions
3-address Instruction Format
operate on registers
Must load from memory!
UTCS 352 Lecture 6 7

MIPS Register Conventions

$zero: holds constant 0 (register 0)

$at: assembler temporary (1)
$v0, $v1: result values (2, 3)
$a0 $a3: arguments (47)
$t0 $t9: temporaries (8-15, 24, 25)
All the above can be overwritten by callee
$s0 $s7: saved (16-23)
Callee must save/restore all these registers
$gp: global pointer for static data (28)
$sp: stack pointer (29)
$fp: frame pointer (30)
$ra: return address (31)
UTCS 352 Lecture 6 8

4
 In/out of Memory and Registers on MIPS
(lw, lbu, sw, sb, lhu, llui, ll)
Uses I format instructions
Example Load Word
lw $t1, 4($t2) means t1 = value at address(t2 + 4)

op rs rt constant or address
6 bits 5 bits 5 bits 16 bits

UTCS 352 Lecture 6 9

In/out of Memory and Registers on MIPS

(lw, lbu, sw, sb, lhu, llui, ll)

// j = j+1 xFFFF
Memory
lw $t0, 0($sp) // $t0 = j
stack
addi $t0, $t0, 1 // j++ Stack
sw $t0, 0($sp) // store on stack a
j
SP
// a = x [j] * a
sll $t1, $t0, 2 // $t1 = j * 4
heap
lw $t3, 0(&x)
add $t3, $t1, &t3 // $t3 = addr (x[j]) x
lw $t4, 0($t3) // $t4 = value x[j]
bar
lw $t2, 4($sp) // $t2 = a
mul $t2, $t4, $t2 // $t2 = $t1 * $t2 foo
sw $t2, 4($sp) // a = $t2
x0000
UTCS 352 Lecture 6 10

5
 Control Instructions

Given 32 bit instructions (MIPS)

Implicit control on each instruction
PC PC + 4
Unconditional jumps // basic loop control
PC X (direct)
// while (j < 100)
PC PC + X (PC relative)
X can be constant or register
Conditional jumps (branches) LOOP: ..
PC PC + ((cond) ? X : 4) LW $t0, 0($sp)
Conditions ADDI $t0, $t0, 1
flags SLTI $t1, $t0, 100
BNE $t1, $zero, LOOP
in a register
fused compare and branch
Other architectures
Predicated instructions

UTCS 352 Lecture 6 11

Branch Instructions & Addressing

(beq, bne, j, jal, jr)
Opcode, two registers, // basic loop: while (j < 100)
target address
beq: branch equal LOOP: ..

if ($rs = $rt) PC = label LW $t0, 0($sp)

ADDI $t0, $t0, 1
bne: branch not equal SLTI $t1, $t0, 100
BNE $t1, $zero, LOOP
if ($rs != $rt) PC = label

op rs rt constant or address
6 bits 5 bits 5 bits 16 bits
Most branch targets are near branch
Forward or backward
PC- relative addressing
Target address = PC + offset * 4
PC implicitly incremented by 4 after every instruction! 12

6
 Branch Pseudo-instructions
(blt, bgt, ble, bge)
blt: branch less than // loop control: while (j < a)

if ($rs < $rt) PC = label

LOOP: ..
bgt: branch greater than
LW $t0, 0($sp)
if ($rs > $rt) PC = label
LW $t1, -4($sp)
ble: branch less than or equal BLT $t0, $t1, LOOP
if ($rs <= $rt) PC = label
bge: branch greater than or equal
if ($rs >= $rt) PC = label
ELSE PC = PC + 4 // Implicit

op rs rt constant or address
6 bits 5 bits 5 bits 16 bits
13

Branch Pseudo-instructions
(blt, bgt, ble, bge)
You write // loop control: while (j < a)

LOOP: ..
LW $t0, 0($sp)
LW $t1, -4($sp)
BLT $t0, $t1, LOOP

You get from the assembler

LOOP: ..
LW $t0, 0($sp)
LW $t1, -4($sp)
SLT $t3, $t0, $t1
BNE $t3, $zero, LOOP
14

7
 Jump Addressing

Jump (j and jal) targets could be anywhere in text

segment
Encode full address in instruction

op address
6 bits 26 bits

Direct jump addressing

Target address = PC3128 : (address 4)

Lecture352
UTCS 6 15

Target Addressing Example

Simple Loop code

Assume Loop at location 80000

Loop: sll $t1, $s3, 2 80000 0 0 19 9 4 0

add $t1, $t1, $s6 80004 0 9 22 9 0 32
lw $t0, 0($t1) 80008 35 9 8 0
bne $t0, $s5, Exit 80012 5 8 21 2
addi $s3, $s3, 1 80016 8 19 19 1
j Loop 80020 2 20000
Exit: 80024

Lecture352
UTCS 6 16

8
 Branching Far Away

If branch target is too far to encode with 16-bit

offset, assembler rewrites the code
Example
beq $s0,$s1, L1

bne $s0,$s1, L2
j L1
L2:

Lecture352
UTCS 6 17

MIPS Addressing Modes

Lecture352
UTCS 6 18

9
 Summary

ISA III
Registers, Memory, Control
MIPS assembly for control, arrays, basic blocks
registers
Next Time
Homework #2 is due 2/9
Procedures & more about MIPS assembly
Other ISAs
Reading: P&H 2.16-19

UTCS 352 Lecture 6 19

10