Chapter 2

Instructions: Language
of the Computer
 2.1 Introduction
Instruction Set Architecture
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
Microprocessor without Interlocked Pipeline
Stages
Stanford MIPS commercialized by MIPS
Technologies (www.mips.com)
Large share of embedded core market
Applications in consumer electronics, network/storage
equipment, cameras, printers,
Typical of many modern ISAs
See MIPS Reference Data tear-out card, and
Appendix B

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 favors 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 # temp t0 = g + h
add t1, i, j # temp t1 = i + j
sub f, t0, t1 # 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
Assembler names
$t0, $t1, , $t9 for temporary values
$s0, $s1, , $s7 for saved variables
Design Principle 2: Smaller is faster
c.f. main memory: millions of locations

Chapter 2 Instructions: Language of the Computer 6

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
Memory is byte addressed
Each address identifies an 8-bit byte
Words are aligned in memory
Address must be a multiple of 4
MIPS is Big Endian
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 7

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 8

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 9

The Constant Zero
MIPS register 0 ($zero) is the constant 0
Cannot be overwritten
Useful for common operations
E.g., move between registers
add $t2, $s1, $zero

Chapter 2 Instructions: Language of the Computer 10

 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!

Chapter 2 Instructions: Language of the Computer 11

 2.5 Representing Instructions in the Computer
Representing Instructions

Chapter 2 Instructions: Language of the Computer 12

 2.5 Representing Instructions in the Computer
MIPS ISA Formats

Chapter 2 Instructions: Language of the Computer 13

MIPS R-format Instructions
op rs rt rd shamt funct
6 bits 5 bits 5 bits 5 bits 5 bits 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 14

R-format Example
op rs rt rd shamt funct
6 bits 5 bits 5 bits 5 bits 5 bits 6 bits

add $t0, $s1, $s2

special $s1 $s2 $t0 0 add

0 17 18 8 0 32

000000 10001 10010 01000 00000 100000

000000100011001001000000001000002 = 0232402016

Chapter 2 Instructions: Language of the Computer 15

Hexadecimal
Base 16
Compact representation of bit strings
4 bits per hex digit

0 0000 4 0100 8 1000 c 1100

1 0001 5 0101 9 1001 d 1101
2 0010 6 0110 a 1010 e 1110
3 0011 7 0111 b 1011 f 1111

Example: eca8 6420

1110 1100 1010 1000 0110 0100 0010 0000

Chapter 2 Instructions: Language of the Computer 16

MIPS I-format Instructions
op rs rt constant or address
6 bits 5 bits 5 bits 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 17

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 18

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

Chapter 2 Instructions: Language of the Computer 19

Register Usage
$a0 $a3: arguments (regs 4 7)
$v0, $v1: result values (regs 2 and 3)
$t0 $t9: temporaries
Can be overwritten by callee
$s0 $s7: saved
Must be saved/restored by callee
$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 20

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 21

Local Data on the Stack

Local data allocated by callee

e.g., C automatic variables
Procedure frame (activation record)
Used by some compilers to manage stack storage
Chapter 2 Instructions: Language of the Computer 22
Branch Addressing
Branch instructions specify
Opcode, two registers, target address
Most branch targets are near branch
Forward or backward

op rs rt constant or address
6 bits 5 bits 5 bits 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 23
Jump Addressing
Jump (j and jal) targets could be
anywhere in text segment
Encode full address in instruction

op address
6 bits 26 bits

(Pseudo)Direct jump addressing

Target address = PC3128 : (address 4)

Chapter 2 Instructions: Language of the Computer 24

Addressing Mode Summary

Chapter 2 Instructions: Language of the Computer 25

 2.16 Real Stuff: ARM Instructions
ARM & MIPS Similarities
ARM: the most popular embedded core
Similar basic set of instructions to MIPS
ARM MIPS
Date announced 1985 1985
Instruction size 32 bits 32 bits
Address space 32-bit flat 32-bit flat
Data alignment Aligned Aligned
Data addressing modes 9 3
Registers 15 32-bit 31 32-bit
Input/output Memory Memory
mapped mapped

Chapter 2 Instructions: Language of the Computer 26

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
Each instruction can be conditional
Top 4 bits of instruction word: condition value
Can avoid branches over single instructions

Chapter 2 Instructions: Language of the Computer 27

Instruction Encoding

Chapter 2 Instructions: Language of the Computer 28

 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
8086 (1978): 16-bit extension to 8080
Complex instruction set (CISC)
8087 (1980): floating-point coprocessor
Adds FP instructions and register stack
80286 (1982): 24-bit addresses, MMU
Segmented memory mapping and protection
80386 (1985): 32-bit extension (now IA-32)
Additional addressing modes and operations
Paged memory mapping as well as segments

Chapter 2 Instructions: Language of the Computer 29

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
Pentium Pro (1995), Pentium II (1997)
New microarchitecture (see Colwell, The Pentium Chronicles)
Pentium III (1999)
Added SSE (Streaming SIMD Extensions) and associated
registers
Pentium 4 (2001)
New microarchitecture
Added SSE2 instructions

Chapter 2 Instructions: Language of the Computer 30

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
Intel Core (2006)
Added SSE4 instructions, virtual machine support
AMD64 (2007): SSE5 instructions
Intel declined to follow, instead
Advanced Vector Extension (2008)
Longer SSE registers, more instructions
If Intel didnt extend with compatibility, its
competitors would!
Technical elegance market success

Chapter 2 Instructions: Language of the Computer 31

 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
Use assembly code for high performance
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 32

Fallacies
Backward compatibility instruction set
doesnt change
But they do accrete more instructions

x86 instruction set

Chapter 2 Instructions: Language of the Computer 33

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 34

 2.19 Concluding Remarks
Concluding Remarks
Design principles
1. Simplicity favors regularity
2. Smaller is faster
3. Make the common case fast
4. Good design demands good compromises
Layers of software/hardware
Compiler, assembler, hardware
MIPS: typical of RISC ISAs
c.f. x86

Chapter 2 Instructions: Language of the Computer 35

Concluding Remarks
Measure MIPS instruction executions in
benchmark programs
Consider making the common case fast
Consider compromises

Chapter 2 Instructions: Language of the Computer 36