Chapter 2

Instructions: Language of the Computer

2.1 Introduction

Instruction Set

The repertoire of instructions of a computer Different computers have different instruction sets

But with many aspects in common

Early computers had very simple instruction sets

Simplified implementation

Many modern computers also have simple instruction sets

Chapter 2 Instructions: Language of the Computer 2

The MIPS Instruction Set

Used as the example throughout the book Stanford MIPS commercialized by MIPS Technologies (www.mips.com) Large share of embedded core market

Applications in consumer electronics, network/storage equipment, cameras, printers, See MIPS Reference Data tear-out card, and Appendixes B and E

Typical of many modern ISAs

Chapter 2 Instructions: Language of the Computer 3

2.2 Operations of the Computer Hardware

Arithmetic Operations

Add and subtract, three operands

Two sources and one destination

add a, b, c # a gets b + c All arithmetic operations have this form Design Principle 1: Simplicity favours regularity

Regularity makes implementation simpler Simplicity enables higher performance at lower cost
Chapter 2 Instructions: Language of the Computer 4

Arithmetic Example

C code:
f = (g + h) - (i + j);

Compiled MIPS code:

add t0, g, h add t1, i, j sub f, t0, t1 # temp t0 = g + h # temp t1 = i + j # f = t0 - t1

Chapter 2 Instructions: Language of the Computer 5

2.3 Operands of the Computer Hardware

Register Operands

Arithmetic instructions use register operands MIPS has a 32 32-bit register file

Use for frequently accessed data Numbered 0 to 31 32-bit data called a word
$t0, $t1, , $t9 for temporary values $s0, $s1, , $s7 for saved variables

Assembler names

Design Principle 2: Smaller is faster

c.f. main memory: millions of locations

Chapter 2 Instructions: Language of the Computer 6

Register Operand Example

C code:
f = (g + h) - (i + j); f, , j in $s0, , $s4

Compiled MIPS code:

add $t0, $s1, $s2 add $t1, $s3, $s4 sub $s0, $t0, $t1

Chapter 2 Instructions: Language of the Computer 7

Memory Operands

Main memory used for composite data

Arrays, structures, dynamic data

To apply arithmetic operations

Load values from memory into registers Store result from register to memory
Each address identifies an 8-bit byte Address must be a multiple of 4 Most-significant byte at least address of a word c.f. Little Endian: least-significant byte at least address
Chapter 2 Instructions: Language of the Computer 8

Memory is byte addressed

Words are aligned in memory

MIPS is Big Endian

For example, suppose we have a 32 bit quantity, written as 90AB12CD16, which is hexadecimal. Since each hex digit is 4 bits, we need 8 hex digits to represent the 32 bit value. So, the 4 bytes are: 90, AB, 12, CD where each byte requires 2 hex digits. It turns out there are two ways to store this in memory.

Big Endian In big endian, you store the most significant byte in the smallest address. Here's how it would look:

Address 1000 1001 1002 1003

Value 90 AB 12 CD

Chapter 2 Instructions: Language of the Computer 9

Little Endian In little endian, you store the least significant byte in the smallest address. Here's how it would look:
Address 1000 1001 1002 1003 Value CD 12 AB 90

Notice that this is in the reverse order compared to big endian. To remember which is which, recall whether the least significant byte is stored first (thus, little endian) or the most significant byte is stored first (thus, big endian).

Chapter 2 Instructions: Language of the Computer 10

Memory Operand Example 1

C code:
g = h + A[8]; g in $s1, h in $s2, base address of A in $s3

Compiled MIPS code:

Index 8 requires offset of 32

4 bytes per word

lw $t0, 32($s3) add $s1, $s2, $t0

offset

# load word

base register

Chapter 2 Instructions: Language of the Computer 11

Memory Operand Example 2

C code:
A[12] = h + A[8]; h in $s2, base address of A in $s3

Compiled MIPS code:

Index 8 requires offset of 32 lw $t0, 32($s3) # load word add $t0, $s2, $t0 sw $t0, 48($s3) # store word

Chapter 2 Instructions: Language of the Computer 12

Registers vs. Memory

Registers are faster to access than memory Operating on memory data requires loads and stores

More instructions to be executed

Compiler must use registers for variables as much as possible

Only spill to memory for less frequently used variables Register optimization is important!
Chapter 2 Instructions: Language of the Computer 13

Immediate Operands

Constant data specified in an instruction

addi $s3, $s3, 4

No subtract immediate instruction

Just use a negative constant

addi $s2, $s1, -1

Design Principle 3: Make the common case fast

Small constants are common Immediate operand avoids a load instruction

Chapter 2 Instructions: Language of the Computer 14

The Constant Zero

MIPS register 0 ($zero) is the constant 0

Cannot be overwritten E.g., move between registers add $t2, $s1, $zero

Useful for common operations

Chapter 2 Instructions: Language of the Computer 15

2.4 Signed and Unsigned Numbers

Unsigned Binary Integers

Given an n-bit number

x x n1 2n1 x n2 2n2 x1 21 x 0 20

Range: 0 to +2n 1 Example

0000 0000 0000 0000 0000 0000 0000 10112 = 0 + + 123 + 022 +121 +120 = 0 + + 8 + 0 + 2 + 1 = 1110

Using 32 bits

0 to +4,294,967,295
Chapter 2 Instructions: Language of the Computer 16

2s-Complement Signed Integers

Given an n-bit number

x x n1 2n1 x n2 2n2 x1 21 x 0 20

Range: 2n 1 to +2n 1 1 Example

1111 1111 1111 1111 1111 1111 1111 11002 = 1231 + 1230 + + 122 +021 +020 = 2,147,483,648 + 2,147,483,644 = 410

Using 32 bits

2,147,483,648 to +2,147,483,647
Chapter 2 Instructions: Language of the Computer 17

2s-Complement Signed Integers

Bit 31 is sign bit

1 for negative numbers 0 for non-negative numbers

(2n 1) cant be represented Non-negative numbers have the same unsigned and 2s-complement representation Some specific numbers

0: 0000 0000 0000 1: 1111 1111 1111 Most-negative: 1000 0000 0000 Most-positive: 0111 1111 1111
Chapter 2 Instructions: Language of the Computer 18

Signed Negation

Complement and add 1

Complement means 1 0, 0 1
x x 1111...111 2 1 x 1 x

Example: negate +2

+2 = 0000 0000 00102 2 = 1111 1111 11012 + 1 = 1111 1111 11102

Chapter 2 Instructions: Language of the Computer 19

Sign Extension

Representing a number using more bits

Preserve the numeric value

In MIPS instruction set

addi: extend immediate value lb, lh: extend loaded byte/halfword beq, bne: extend the displacement
c.f. unsigned values: extend with 0s +2: 0000 0010 => 0000 0000 0000 0010 2: 1111 1110 => 1111 1111 1111 1110
Chapter 2 Instructions: Language of the Computer 20

Replicate the sign bit to the left

Examples: 8-bit to 16-bit

2.5 Representing Instructions in the Computer

Representing Instructions

Instructions are encoded in binary

Called machine code

MIPS instructions

Encoded as 32-bit instruction words Small number of formats encoding operation code (opcode), register numbers, Regularity!
$t0 $t7 are regs 8 15 $t8 $t9 are regs 24 25 $s0 $s7 are regs 16 23

Register numbers

Chapter 2 Instructions: Language of the Computer 21

MIPS R-format Instructions

op
6 bits

rs
5 bits

rt
5 bits

rd
5 bits

shamt
5 bits

funct
6 bits

Instruction fields

op: operation code (opcode) rs: first source register number rt: second source register number rd: destination register number shamt: shift amount (00000 for now) funct: function code (extends opcode)
Chapter 2 Instructions: Language of the Computer 22

R-format Example
op
6 bits

rs
5 bits

rt
5 bits

rd
5 bits

shamt
5 bits

funct
6 bits

add $t0, $s1, $s2

special
0 000000

$s1
17 10001

$s2
18 10010

$t0
8 01000

0
0 00000

add
32 100000

000000100011001001000000001000002 = 0232402016
Chapter 2 Instructions: Language of the Computer 23

Hexadecimal

Base 16

Compact representation of bit strings 4 bits per hex digit

0000 0001 0010 0011 4 5 6 7 0100 0101 0110 0111 8 9 a b 1000 1001 1010 1011 c d e f 1100 1101 1110 1111

0 1 2 3

Example: eca8 6420

1110 1100 1010 1000 0110 0100 0010 0000

Chapter 2 Instructions: Language of the Computer 24

MIPS I-format Instructions

op
6 bits

rs
5 bits

rt
5 bits

constant or address
16 bits

Immediate arithmetic and load/store instructions

rt: destination or source register number Constant: 215 to +215 1 Address: offset added to base address in rs

Design Principle 4: Good design demands good compromises

Different formats complicate decoding, but allow 32-bit instructions uniformly Keep formats as similar as possible
Chapter 2 Instructions: Language of the Computer 25

Stored Program Computers

The BIG Picture

Instructions represented in binary, just like data Instructions and data stored in memory Programs can operate on programs

e.g., compilers, linkers,

Binary compatibility allows compiled programs to work on different computers

Standardized ISAs

Chapter 2 Instructions: Language of the Computer 26

2.6 Logical Operations

Logical Operations

Instructions for bitwise manipulation

Operation Shift left Shift right Bitwise AND Bitwise OR Bitwise NOT C << >> & | ~ Java << >>> & | ~ MIPS sll srl and, andi or, ori nor

Useful for extracting and inserting groups of bits in a word

Chapter 2 Instructions: Language of the Computer 27

Shift Operations
op
6 bits

rs
5 bits

rt
5 bits

rd
5 bits

shamt
5 bits

funct
6 bits

shamt: how many positions to shift Shift left logical

Shift left and fill with 0 bits sll by i bits multiplies by 2i Shift right and fill with 0 bits srl by i bits divides by 2i (unsigned only)
Chapter 2 Instructions: Language of the Computer 28

Shift right logical

AND Operations

Useful to mask bits in a word

Select some bits, clear others to 0

and $t0, $t1, $t2

$t2 $t1 0000 0000 0000 0000 0000 1101 1100 0000 0000 0000 0000 0000 0011 1100 0000 0000

$t0

0000 0000 0000 0000 0000 1100 0000 0000

Chapter 2 Instructions: Language of the Computer 29

OR Operations

Useful to include bits in a word

Set some bits to 1, leave others unchanged

or $t0, $t1, $t2

$t2 $t1 0000 0000 0000 0000 0000 1101 1100 0000 0000 0000 0000 0000 0011 1100 0000 0000

$t0

0000 0000 0000 0000 0011 1101 1100 0000

Chapter 2 Instructions: Language of the Computer 30

NOT Operations

Useful to invert bits in a word

Change 0 to 1, and 1 to 0 a NOR b == NOT ( a OR b )

Register 0: always read as zero

MIPS has NOR 3-operand instruction

nor $t0, $t1, $zero

$t1 $t0

0000 0000 0000 0000 0011 1100 0000 0000 1111 1111 1111 1111 1100 0011 1111 1111

Chapter 2 Instructions: Language of the Computer 31

2.7 Instructions for Making Decisions

Conditional Operations

Branch to a labeled instruction if a condition is true

Otherwise, continue sequentially if (rs == rt) branch to instruction labeled L1; if (rs != rt) branch to instruction labeled L1; unconditional jump to instruction labeled L1

beq rs, rt, L1

bne rs, rt, L1

j L1

Chapter 2 Instructions: Language of the Computer 32

Compiling If Statements

C code:
if (i==j) f = g+h; else f = g-h;

f, g, in $s0, $s1, $s3, $s4, Else $s0, $s1, $s2 Exit $s0, $s1, $s2
Assembler calculates addresses
Chapter 2 Instructions: Language of the Computer 33

Compiled MIPS code:

bne add j Else: sub Exit:

Compiling Loop Statements

C code:
while (save[i] == k) i += 1;

i in $s3, k in $s5, address of save in $s6 $t1, $t1, $t0, $t0, $s3, Loop $s3, 2 $t1, $s6 0($t1) $s5, Exit $s3, 1

Compiled MIPS code:

Loop: sll add lw bne addi j Exit:

Chapter 2 Instructions: Language of the Computer 34

Basic Blocks

A basic block is a sequence of instructions with

No embedded branches (except at end) No branch targets (except at beginning)

A compiler identifies basic blocks for optimization An advanced processor can accelerate execution of basic blocks

Chapter 2 Instructions: Language of the Computer 35

More Conditional Operations

Set result to 1 if a condition is true

Otherwise, set to 0 if (rs < rt) rd = 1; else rd = 0;

slt rd, rs, rt

slti rt, rs, constant

if (rs < constant) rt = 1; else rt = 0;

slt $t0, $s1, $s2 bne $t0, $zero, L # if ($s1 < $s2) # branch to L

Use in combination with beq, bne

Chapter 2 Instructions: Language of the Computer 36

Branch Instruction Design

Why not blt, bge, etc? Hardware for <, , slower than =,

Combining with branch involves more work per instruction, requiring a slower clock All instructions penalized!

beq and bne are the common case This is a good design compromise

Chapter 2 Instructions: Language of the Computer 37

Signed vs. Unsigned

Signed comparison: slt, slti Unsigned comparison: sltu, sltui Example

$s0 = 1111 1111 1111 1111 1111 1111 1111 1111 $s1 = 0000 0000 0000 0000 0000 0000 0000 0001 slt $t0, $s0, $s1 # signed

1 < +1 $t0 = 1

sltu $t0, $s0, $s1

# unsigned

+4,294,967,295 > +1 $t0 = 0

Chapter 2 Instructions: Language of the Computer 38

2.8 Supporting Procedures in Computer Hardware

Procedure Calling

Steps required
1. 2. 3. 4. 5. 6. Place parameters in registers Transfer control to procedure Acquire storage for procedure Perform procedures operations Place result in register for caller Return to place of call

Chapter 2 Instructions: Language of the Computer 39

Register Usage

$a0 $a3: arguments (regs 4 7) $v0, $v1: result values (regs 2 and 3) $t0 $t9: temporaries

Can be overwritten by callee

Must be saved/restored by callee

$s0 $s7: saved

$gp: global pointer for static data (reg 28) $sp: stack pointer (reg 29) $fp: frame pointer (reg 30) $ra: return address (reg 31)
Chapter 2 Instructions: Language of the Computer 40

Procedure Call Instructions

Procedure call: jump and link

jal ProcedureLabel Address of following instruction put in $ra Jumps to target address

Procedure return: jump register

jr $ra Copies $ra to program counter Can also be used for computed jumps

e.g., for case/switch statements

Chapter 2 Instructions: Language of the Computer 41

Leaf Procedure Example

C code:
int leaf_example (int g, h, i, j) { int f; f = (g + h) - (i + j); return f; } Arguments g, , j in $a0, , $a3 f in $s0 (hence, need to save $s0 on stack) Result in $v0

Chapter 2 Instructions: Language of the Computer 42

Leaf Procedure Example

MIPS code:
leaf_example: addi $sp, $sp, -4 sw $s0, 0($sp) add $t0, $a0, $a1 add $t1, $a2, $a3 sub $s0, $t0, $t1 add $v0, $s0, $zero lw $s0, 0($sp) addi $sp, $sp, 4 jr $ra
Save $s0 on stack

Procedure body

Result Restore $s0 Return

Chapter 2 Instructions: Language of the Computer 43

Non-Leaf Procedures

Procedures that call other procedures For nested call, caller needs to save on the stack:

Its return address Any arguments and temporaries needed after the call

Restore from the stack after the call

Chapter 2 Instructions: Language of the Computer 44

Non-Leaf Procedure Example

C code:
int fact (int n) { if (n < 1) return f; else return n * fact(n - 1); } Argument n in $a0 Result in $v0

Chapter 2 Instructions: Language of the Computer 45

Non-Leaf Procedure Example

MIPS code:
fact: addi sw sw slti beq addi addi jr L1: addi jal lw lw addi mul jr $sp, $ra, $a0, $t0, $t0, $v0, $sp, $ra $a0, fact $a0, $ra, $sp, $v0, $ra $sp, -8 4($sp) 0($sp) $a0, 1 $zero, L1 $zero, 1 $sp, 8 $a0, -1 0($sp) 4($sp) $sp, 8 $a0, $v0 # # # # # # # # # # # # # # adjust stack for 2 items save return address save argument test for n < 1 if so, result is 1 pop 2 items from stack and return else decrement n recursive call restore original n and return address pop 2 items from stack multiply to get result and return

Chapter 2 Instructions: Language of the Computer 46

Local Data on the Stack

Local data allocated by callee

e.g., C automatic variables Used by some compilers to manage stack storage

Chapter 2 Instructions: Language of the Computer 47

Procedure frame (activation record)

Memory Layout

Text: program code Static data: global variables

e.g., static variables in C, constant arrays and strings $gp initialized to address allowing offsets into this segment
E.g., malloc in C, new in Java

Dynamic data: heap

Stack: automatic storage

Chapter 2 Instructions: Language of the Computer 48

2.9 Communicating with People

Character Data

Byte-encoded character sets

ASCII: 128 characters

95 graphic, 33 control ASCII, +96 more graphic characters

Latin-1: 256 characters

Unicode: 32-bit character set

Used in Java, C++ wide characters, Most of the worlds alphabets, plus symbols UTF-8, UTF-16: variable-length encodings
Chapter 2 Instructions: Language of the Computer 49

Byte/Halfword Operations

Could use bitwise operations MIPS byte/halfword load/store

String processing is a common case

lh rt, offset(rs)

lb rt, offset(rs)

Sign extend to 32 bits in rt

lhu rt, offset(rs)
sh rt, offset(rs)

lbu rt, offset(rs)

Zero extend to 32 bits in rt

sb rt, offset(rs)

Store just rightmost byte/halfword

Chapter 2 Instructions: Language of the Computer 50

String Copy Example

C code (nave):
Null-terminated string void strcpy (char x[], char y[]) { int i; i = 0; while ((x[i]=y[i])!='\0') i += 1; } Addresses of x, y in $a0, $a1 i in $s0

Chapter 2 Instructions: Language of the Computer 51

String Copy Example

MIPS code:
strcpy: addi sw add L1: add lbu add sb beq addi j L2: lw addi jr $sp, $s0, $s0, $t1, $t2, $t3, $t2, $t2, $s0, L1 $s0, $sp, $ra $sp, -4 0($sp) $zero, $zero $s0, $a1 0($t1) $s0, $a0 0($t3) $zero, L2 $s0, 1 0($sp) $sp, 4 # # # # # # # # # # # # # adjust stack for 1 item save $s0 i = 0 addr of y[i] in $t1 $t2 = y[i] addr of x[i] in $t3 x[i] = y[i] exit loop if y[i] == 0 i = i + 1 next iteration of loop restore saved $s0 pop 1 item from stack and return

Chapter 2 Instructions: Language of the Computer 52

2.10 MIPS Addressing for 32-Bit Immediates and Addresses

32-bit Constants

Most constants are small

16-bit immediate is sufficient

For the occasional 32-bit constant lui rt, constant

Copies 16-bit constant to left 16 bits of rt Clears right 16 bits of rt to 0

0000 0000 0111 1101 0000 0000 0000 0000

lhi $s0, 61

ori $s0, $s0, 2304 0000 0000 0111 1101 0000 1001 0000 0000

Chapter 2 Instructions: Language of the Computer 53

Branch Addressing

Branch instructions specify

Opcode, two registers, target address Forward or backward

op
6 bits

Most branch targets are near branch

rs
5 bits

rt
5 bits

constant or address
16 bits

PC-relative addressing

Target address = PC + offset 4 PC already incremented by 4 by this time

Chapter 2 Instructions: Language of the Computer 54

Jump Addressing

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

Encode full address in instruction

op
6 bits

address
26 bits

(Pseudo)Direct jump addressing

Target address = PC3128 : (address 4)

Chapter 2 Instructions: Language of the Computer 55

Target Addressing Example

Loop code from earlier example

Assume Loop at location 80000

$t1, $s3, 2 $t1, $t1, $s6 $t0, 0($t1) 80000 80004 80008 0 0 35 5 8 2 0 9 9 8 19 19 22 8 21 19 20000 9 9 4 0 0 2 1 0 32

Loop: sll add lw bne

$t0, $s5, Exit 80012 80016 80020 80024

addi $s3, $s3, 1 j Exit: Loop

Chapter 2 Instructions: Language of the Computer 56

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:

Chapter 2 Instructions: Language of the Computer 57

Addressing Mode Summary

Chapter 2 Instructions: Language of the Computer 58

2.11 Parallelism and Instructions: Synchronization

Synchronization

Two processors sharing an area of memory

P1 writes, then P2 reads Data race if P1 and P2 dont synchronize

Result depends of order of accesses

Hardware support required

Atomic read/write memory operation No other access to the location allowed between the read and write E.g., atomic swap of register memory Or an atomic pair of instructions

Could be a single instruction

Chapter 2 Instructions: Language of the Computer 59

Synchronization in MIPS

Load linked: ll rt, offset(rs) Store conditional: sc rt, offset(rs)

Succeeds if location not changed since the ll

Returns 1 in rt
Returns 0 in rt

Fails if location is changed

Example: atomic swap (to test/set lock variable)

try: add ll sc beq add $t0,$zero,$s4 $t1,0($s1) $t0,0($s1) $t0,$zero,try $s4,$zero,$t1 ;copy exchange value ;load linked ;store conditional ;branch store fails ;put load value in $s4

Chapter 2 Instructions: Language of the Computer 60

2.12 Translating and Starting a Program

Translation and Startup

Many compilers produce object modules directly

Static linking

Chapter 2 Instructions: Language of the Computer 61

Assembler Pseudoinstructions

Most assembler instructions represent machine instructions one-to-one Pseudoinstructions: figments of the assemblers imagination
add $t0, $zero, $t1 blt $t0, $t1, L slt $at, $t0, $t1
move $t0, $t1 bne $at, $zero, L

$at (register 1): assembler temporary

Chapter 2 Instructions: Language of the Computer 62

Producing an Object Module

Assembler (or compiler) translates program into machine instructions Provides information for building a complete program from the pieces

Header: described contents of object module Text segment: translated instructions Static data segment: data allocated for the life of the program Relocation info: for contents that depend on absolute location of loaded program Symbol table: global definitions and external refs Debug info: for associating with source code
Chapter 2 Instructions: Language of the Computer 63

Linking Object Modules

Produces an executable image

1. Merges segments 2. Resolve labels (determine their addresses) 3. Patch location-dependent and external refs

Could leave location dependencies for fixing by a relocating loader

But with virtual memory, no need to do this Program can be loaded into absolute location in virtual memory space
Chapter 2 Instructions: Language of the Computer 64

Loading a Program

Load from image file on disk into memory

1. Read header to determine segment sizes 2. Create virtual address space 3. Copy text and initialized data into memory

Or set page table entries so they can be faulted in

4. Set up arguments on stack 5. Initialize registers (including $sp, $fp, $gp) 6. Jump to startup routine

Copies arguments to $a0, and calls main When main returns, do exit syscall
Chapter 2 Instructions: Language of the Computer 65

Dynamic Linking

Only link/load library procedure when it is called

Requires procedure code to be relocatable Avoids image bloat caused by static linking of all (transitively) referenced libraries Automatically picks up new library versions

Chapter 2 Instructions: Language of the Computer 66

Lazy Linkage

Indirection table

Stub: Loads routine ID, Jump to linker/loader

Linker/loader code

Dynamically mapped code

Chapter 2 Instructions: Language of the Computer 67

Starting Java Applications

Simple portable instruction set for the JVM

Compiles bytecodes of hot methods into native code for host machine

Interprets bytecodes

Chapter 2 Instructions: Language of the Computer 68

2.13 A C Sort Example to Put It All Together

C Sort Example

Illustrates use of assembly instructions for a C bubble sort function Swap procedure (leaf)
void swap(int v[], int k) { int temp; temp = v[k]; v[k] = v[k+1]; v[k+1] = temp; } v in $a0, k in $a1, temp in $t0

Chapter 2 Instructions: Language of the Computer 69

The Procedure Swap

swap: sll $t1, $a1, 2 # $t1 = k * 4 add $t1, $a0, $t1 # $t1 = v+(k*4) # (address of v[k]) lw $t0, 0($t1) # $t0 (temp) = v[k] lw $t2, 4($t1) # $t2 = v[k+1] sw $t2, 0($t1) # v[k] = $t2 (v[k+1]) sw $t0, 4($t1) # v[k+1] = $t0 (temp) jr $ra # return to calling routine

Chapter 2 Instructions: Language of the Computer 70

The Sort Procedure in C

Non-leaf (calls swap)

void sort (int v[], int n) { int i, j; for (i = 0; i < n; i += 1) { for (j = i 1; j >= 0 && v[j] > v[j + 1]; j -= 1) { swap(v,j); } } } v in $a0, k in $a1, i in $s0, j in $s1
Chapter 2 Instructions: Language of the Computer 71

The Procedure Body

move move move for1tst: slt beq addi for2tst: slti bne sll add lw lw slt beq move move jal addi j exit2: addi j $s2, $a0 $s3, $a1 $s0, $zero $t0, $s0, $s3 $t0, $zero, exit1 $s1, $s0, 1 $t0, $s1, 0 $t0, $zero, exit2 $t1, $s1, 2 $t2, $s2, $t1 $t3, 0($t2) $t4, 4($t2) $t0, $t4, $t3 $t0, $zero, exit2 $a0, $s2 $a1, $s1 swap $s1, $s1, 1 for2tst $s0, $s0, 1 for1tst # # # # # # # # # # # # # # # # # # # # # save $a0 into $s2 save $a1 into $s3 i = 0 $t0 = 0 if $s0 $s3 (i n) go to exit1 if $s0 $s3 (i n) j = i 1 $t0 = 1 if $s1 < 0 (j < 0) go to exit2 if $s1 < 0 (j < 0) $t1 = j * 4 $t2 = v + (j * 4) $t3 = v[j] $t4 = v[j + 1] $t0 = 0 if $t4 $t3 go to exit2 if $t4 $t3 1st param of swap is v (old $a0) 2nd param of swap is j call swap procedure j = 1 jump to test of inner loop i += 1 jump to test of outer loop Move params Outer loop

Inner loop

Pass params & call Inner loop Outer loop

Chapter 2 Instructions: Language of the Computer 72

The Full Procedure

sort: addi $sp,$sp, 20 sw $ra, 16($sp) sw $s3,12($sp) sw $s2, 8($sp) sw $s1, 4($sp) sw $s0, 0($sp) exit1: lw $s0, 0($sp) lw $s1, 4($sp) lw $s2, 8($sp) lw $s3,12($sp) lw $ra,16($sp) addi $sp,$sp, 20 jr $ra # # # # # # # # # # # # # # make room on stack for 5 registers save $ra on stack save $s3 on stack save $s2 on stack save $s1 on stack save $s0 on stack procedure body restore $s0 from stack restore $s1 from stack restore $s2 from stack restore $s3 from stack restore $ra from stack restore stack pointer return to calling routine

Chapter 2 Instructions: Language of the Computer 73

Effect of Compiler Optimization

Compiled with gcc for Pentium 4 under Linux
3 2.5 2 1.5 1 0.5 0 none 180000 160000 140000 120000 100000 80000 60000 40000 20000 0 none O1 O2 O3 2 1.5 1 0.5 0 O1 O2 O3 none O1 O2 O3

Relative Performance

140000 120000 100000 80000 60000 40000 20000 0 none

Instruction count

O1

O2

O3

Clock Cycles

CPI

Chapter 2 Instructions: Language of the Computer 74

Effect of Language and Algorithm

3 2.5 2 1.5 1 0.5 0 C/none C/O1 C/O2 C/O3 Java/int Java/JIT

Bubblesort Relative Performance

2.5 2 1.5 1 0.5 0 C/none

Quicksort Relative Performance

C/O1

C/O2

C/O3

Java/int

Java/JIT

3000 2500 2000 1500 1000 500 0 C/none

Quicksort vs. Bubblesort Speedup

C/O1

C/O2

C/O3

Java/int

Java/JIT

Chapter 2 Instructions: Language of the Computer 75

Lessons Learnt

Instruction count and CPI are not good performance indicators in isolation Compiler optimizations are sensitive to the algorithm Java/JIT compiled code is significantly faster than JVM interpreted

Comparable to optimized C in some cases

Nothing can fix a dumb algorithm!

Chapter 2 Instructions: Language of the Computer 76

2.14 Arrays versus Pointers

Arrays vs. Pointers

Array indexing involves

Multiplying index by element size Adding to array base address

Pointers correspond directly to memory addresses

Can avoid indexing complexity

Chapter 2 Instructions: Language of the Computer 77

Example: Clearing and Array

clear1(int array[], int size) { int i; for (i = 0; i < size; i += 1) array[i] = 0; } move $t0,$zero loop1: sll $t1,$t0,2 add $t2,$a0,$t1 # i = 0 # $t1 = i * 4 # $t2 = # &array[i] sw $zero, 0($t2) # array[i] = 0 addi $t0,$t0,1 # i = i + 1 slt $t3,$t0,$a1 # $t3 = # (i < size) bne $t3,$zero,loop1 # if () # goto loop1 clear2(int *array, int size) { int *p; for (p = &array[0]; p < &array[size]; p = p + 1) *p = 0; } move $t0,$a0 # p = & array[0] sll $t1,$a1,2 # $t1 = size * 4 add $t2,$a0,$t1 # $t2 = # &array[size] loop2: sw $zero,0($t0) # Memory[p] = 0 addi $t0,$t0,4 # p = p + 4 slt $t3,$t0,$t2 # $t3 = #(p<&array[size]) bne $t3,$zero,loop2 # if () # goto loop2

Chapter 2 Instructions: Language of the Computer 78

Comparison of Array vs. Ptr

Multiply strength reduced to shift Array version requires shift to be inside loop

Part of index calculation for incremented i c.f. incrementing pointer

Compiler can achieve same effect as manual use of pointers

Induction variable elimination Better to make program clearer and safer

Chapter 2 Instructions: Language of the Computer 79

2.16 Real Stuff: ARM Instructions

ARM & MIPS Similarities

ARM: the most popular embedded core Similar basic set of instructions to MIPS
ARM MIPS 1985 32 bits 32-bit flat Aligned 3 31 32-bit Memory mapped 1985 32 bits 32-bit flat Aligned 9 15 32-bit Memory mapped

Date announced Instruction size Address space Data alignment Data addressing modes Registers Input/output

Chapter 2 Instructions: Language of the Computer 80

Compare and Branch in ARM

Uses condition codes for result of an arithmetic/logical instruction

Negative, zero, carry, overflow Compare instructions to set condition codes without keeping the result Top 4 bits of instruction word: condition value Can avoid branches over single instructions

Each instruction can be conditional

Chapter 2 Instructions: Language of the Computer 81

Instruction Encoding

Chapter 2 Instructions: Language of the Computer 82

2.17 Real Stuff: x86 Instructions

The Intel x86 ISA

Evolution with backward compatibility

8080 (1974): 8-bit microprocessor

Accumulator, plus 3 index-register pairs Complex instruction set (CISC) Adds FP instructions and register stack Segmented memory mapping and protection Additional addressing modes and operations Paged memory mapping as well as segments

8086 (1978): 16-bit extension to 8080

8087 (1980): floating-point coprocessor

80286 (1982): 24-bit addresses, MMU

80386 (1985): 32-bit extension (now IA-32)

Chapter 2 Instructions: Language of the Computer 83

The Intel x86 ISA

Further evolution

i486 (1989): pipelined, on-chip caches and FPU

Compatible competitors: AMD, Cyrix,

Pentium (1993): superscalar, 64-bit datapath

Later versions added MMX (Multi-Media eXtension) instructions The infamous FDIV bug
New microarchitecture (see Colwell, The Pentium Chronicles) Added SSE (Streaming SIMD Extensions) and associated registers

Pentium Pro (1995), Pentium II (1997)

Pentium III (1999)

Pentium 4 (2001)

New microarchitecture Added SSE2 instructions

Chapter 2 Instructions: Language of the Computer 84

The Intel x86 ISA

And further

AMD64 (2003): extended architecture to 64 bits EM64T Extended Memory 64 Technology (2004)

AMD64 adopted by Intel (with refinements) Added SSE3 instructions Added SSE4 instructions, virtual machine support

Intel Core (2006)

AMD64 (announced 2007): SSE5 instructions

Intel declined to follow, instead

Longer SSE registers, more instructions

Advanced Vector Extension (announced 2008)

If Intel didnt extend with compatibility, its competitors would!

Technical elegance market success

Chapter 2 Instructions: Language of the Computer 85

Basic x86 Registers

Chapter 2 Instructions: Language of the Computer 86

Basic x86 Addressing Modes

Two operands per instruction

Source/dest operand Second source operand

Register
Register Register Memory Memory

Register
Immediate Memory Register Immediate

Memory addressing modes

Address in register Address = Rbase + displacement Address = Rbase + 2scale Rindex (scale = 0, 1, 2, or 3) Address = Rbase + 2scale Rindex + displacement
Chapter 2 Instructions: Language of the Computer 87

x86 Instruction Encoding

Variable length encoding

Postfix bytes specify addressing mode Prefix bytes modify operation

Operand length, repetition, locking,

Chapter 2 Instructions: Language of the Computer 88

Implementing IA-32

Complex instruction set makes implementation difficult

Hardware translates instructions to simpler microoperations

Simple instructions: 11 Complex instructions: 1many

Microengine similar to RISC Market share makes this economically viable

Compilers avoid complex instructions
Chapter 2 Instructions: Language of the Computer 89

Comparable performance to RISC

2.18 Fallacies and Pitfalls

Fallacies

Powerful instruction higher performance

Fewer instructions required But complex instructions are hard to implement

May slow down all instructions, including simple ones

Compilers are good at making fast code from simple instructions But modern compilers are better at dealing with modern processors More lines of code more errors and less productivity
Chapter 2 Instructions: Language of the Computer 90

Use assembly code for high performance

Fallacies

Backward compatibility instruction set doesnt change

But they do accrete more instructions

x86 instruction set

Chapter 2 Instructions: Language of the Computer 91

Pitfalls

Sequential words are not at sequential addresses

Increment by 4, not by 1!

Keeping a pointer to an automatic variable after procedure returns

e.g., passing pointer back via an argument Pointer becomes invalid when stack popped

Chapter 2 Instructions: Language of the Computer 92

2.19 Concluding Remarks

Concluding Remarks

Design principles
1. 2. 3. 4. Simplicity favors regularity Smaller is faster Make the common case fast Good design demands good compromises

Layers of software/hardware

Compiler, assembler, hardware c.f. x86

MIPS: typical of RISC ISAs

Chapter 2 Instructions: Language of the Computer 93

Concluding Remarks

Measure MIPS instruction executions in benchmark programs

Consider making the common case fast Consider compromises

MIPS examples add, sub, addi lw, sw, lb, lbu, lh, lhu, sb, lui and, or, nor, andi, ori, sll, srl beq, bne, slt, slti, sltiu j, jr, jal SPEC2006 Int 16% 35% 12% 34% 2% SPEC2006 FP 48% 36% 4% 8% 0%

Instruction class Arithmetic Data transfer Logical Cond. Branch Jump

Chapter 2 Instructions: Language of the Computer 94