Lecture 3

Instructions: Language
of the Computer
 §2.1 Introduction
Instruction Set
n The repertoire of instructions of a
computer
n Different computers have different
instruction sets
n But with many aspects in common
n Early computers had very simple
instruction sets
n Simplified implementation
n Many modern computers also have simple
instruction sets

Lecture 3 — Instructions: Language of the Computer — 2

The MIPS Instruction Set
n Used as the example throughout the book
n Stanford MIPS commercialized by MIPS
Technologies (www.mips.com)
n Large share of embedded core market
n Applications in consumer electronics, network/storage
equipment, cameras, printers, …
n Typical of many modern ISAs

Lecture 3 — Instructions: Language of the Computer — 3

 §2.2 Operations of the Computer Hardware
Arithmetic Operations
n Add and subtract, three operands
n Two sources and one destination
add a, b, c # a gets b + c
n All arithmetic operations have this form
n Design Principle 1: Simplicity favours
regularity
n Regularity makes implementation simpler
n Simplicity enables higher performance at
lower cost

Lecture 3 — Instructions: Language of the Computer — 4

Arithmetic Example
n High-level language code:
f = (g + h) - (i + j);

n 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

Lecture 3 — Instructions: Language of the Computer — 5

 §2.3 Operands of the Computer Hardware
Register Operands
n Arithmetic instructions use register
operands
n MIPS has a 32 × 32-bit register file
n Use for frequently accessed data
n Numbered 0 to 31
n 32-bit data called a “word”
n Assembler names
n $t0, $t1, …, $t9 for temporary values
n $s0, $s1, …, $s7 for saved variables
n Design Principle 2: Smaller is faster
n c.f. main memory: millions of locations

Lecture 3 — Instructions: Language of the Computer — 6

Register Operand Example
n C code:
f = (g + h) - (i + j);
n f, …, j in $s0, …, $s4

n Compiled MIPS code:

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

Lecture 3 — Instructions: Language of the Computer — 7

Memory Operands
n Main memory used for composite data
n Arrays, structures, dynamic data
n To apply arithmetic operations
n Load values from memory into registers
n Store result from register to memory
n Memory is byte addressed
n Each address identifies an 8-bit byte
n Words are aligned in memory
n Address must be a multiple of 4
n MIPS is Big Endian
n Most-significant byte at least address of a word
n c.f. Little Endian: least-significant byte at least address

Lecture 3 — Instructions: Language of the Computer — 8

Memory Operand Example 1
n High-level language code:
g = h + A[8];
n g in $s1, h in $s2, base address of A in $s3

n Compiled MIPS code:

n Index 8 requires offset of 32
n 4 bytes per word
lw $t0, 32($s3) # load word
add $s1, $s2, $t0
offset base register

Lecture 3 — Instructions: Language of the Computer — 9

Memory Operand Example 2
n High-level language code:
A[12] = h + A[8];
n h in $s2, base address of A in $s3

n Compiled MIPS code:

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

Lecture 3 — Instructions: Language of the Computer — 10

Registers vs. Memory
n Registers are faster to access than
memory
n Operating on memory data requires loads
and stores
n More instructions to be executed
n Compiler must use registers for variables
as much as possible
n Only spill to memory for less frequently used
variables
n Register optimization is important!

Lecture 3 — Instructions: Language of the Computer — 11

Immediate Operands
n Constant data specified in an instruction
addi $s3, $s3, 4
n No subtract immediate instruction
n Just use a negative constant
addi $s2, $s1, -1
n Design Principle 3: Make the common
case fast
n Small constants are common
n Immediate operand avoids a load instruction

Lecture 3 — Instructions: Language of the Computer — 12

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

Lecture 3 — Instructions: Language of the Computer — 13

Unsigned Binary Integers
n Given an n-bit number
n -1 n-2
x = x n-1 2 + x n-2 2 + ! + x1 2 + x 0 2
1 0

n Range: 0 to +2n – 1
n Example
n 0000 0000 0000 0000 0000 0000 0000 10112
= 0 + … + 1×23 + 0×22 +1×21 +1×20
= 0 + … + 8 + 0 + 2 + 1 = 1110
n Using 32 bits
n 0 to +4,294,967,295

Lecture 3 — Instructions: Language of the Computer — 14

2s-Complement Signed Integers
n Given an n-bit number
n -1 n-2
x = - x n-1 2 + x n-2 2 + ! + x1 2 + x 0 2
1 0

n Range: –2n – 1 to +2n – 1 – 1

n Example
n 1111 1111 1111 1111 1111 1111 1111 11002
= –1×231 + 1×230 + … + 1×22 +0×21 +0×20
= –2,147,483,648 + 2,147,483,644 = –410
n Using 32 bits
n –2,147,483,648 to +2,147,483,647

Lecture 3 — Instructions: Language of the Computer — 15

2s-Complement Signed Integers
n Bit 31 is sign bit
n 1 for negative numbers
n 0 for non-negative numbers
n –(–2n – 1) can’t be represented
n Non-negative numbers have the same unsigned
and 2s-complement representation
n Some specific numbers
n 0: 0000 0000 … 0000
n –1: 1111 1111 … 1111
n Most-negative: 1000 0000 … 0000
n Most-positive: 0111 1111 … 1111

Lecture 3 — Instructions: Language of the Computer — 16

Signed Negation
n Complement and add 1
n Complement means 1 → 0, 0 → 1

x + x = 1111...1112 = -1

x + 1 = -x

n Example: negate +2
n +2 = 0000 0000 … 00102
n –2 = 1111 1111 … 11012 + 1
= 1111 1111 … 11102

Lecture 3 — Instructions: Language of the Computer — 17

Sign Extension
n Representing a number using more bits
n Preserve the numeric value
n In MIPS instruction set
n addi: extend immediate value
n lb, lh: extend loaded byte/halfword
n beq, bne: extend the displacement
n Replicate the sign bit to the left
n c.f. unsigned values: extend with 0s
n Examples: 8-bit to 16-bit
n +2: 0000 0010 => 0000 0000 0000 0010
n –2: 1111 1110 => 1111 1111 1111 1110

Lecture 3 — Instructions: Language of the Computer — 18

Representing Instructions
n Instructions are encoded in binary
n Called machine code
n MIPS instructions
n Encoded as 32-bit instruction words
n Small number of formats encoding operation code
(opcode), register numbers, …
n Regularity!
n Register numbers
n $t0 – $t7 are reg’s 8 – 15
n $t8 – $t9 are reg’s 24 – 25
n $s0 – $s7 are reg’s 16 – 23

Lecture 3 — Instructions: Language of the Computer — 19

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

n Instruction fields
n op: operation code (opcode)
n rs: first source register number
n rt: second source register number
n rd: destination register number
n shamt: shift amount (00000 for now)
n funct: function code (extends opcode)

Lecture 3 — Instructions: Language of the Computer — 20

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

Lecture 3 — Instructions: Language of the Computer — 21

Hexadecimal
n Base 16
n Compact representation of bit strings
n 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

n Example: eca8 6420

n 1110 1100 1010 1000 0110 0100 0010 0000

Lecture 3 — Instructions: Language of the Computer — 22

MIPS I-format Instructions
op rs rt constant or address
6 bits 5 bits 5 bits 16 bits

n Immediate arithmetic and load/store instructions

n rt: destination or source register number
n Constant: –215 to +215 – 1
n Address: offset added to base address in rs
n Design Principle 4: Good design demands good
compromises
n Different formats complicate decoding, but allow 32-bit
instructions uniformly
n Keep formats as similar as possible

Lecture 3 — Instructions: Language of the Computer — 23

Shift Operations

op rs rt rd shamt funct
6 bits 5 bits 5 bits 5 bits 5 bits 6 bits

n shamt: how many positions to shift

n Shift left logical
n Shift left and fill with 0 bits
n sll by i bits multiplies by 2i
n Shift right logical
n Shift right and fill with 0 bits
n srl by i bits divides by 2i (unsigned only)

Lecture 3 — Instructions: Language of the Computer — 24

AND Operations
n Useful to mask bits in a word
n Select some bits, clear others to 0
and $t0, $t1, $t2

$t2 0000 0000 0000 0000 0000 1101 1100 0000

$t1 0000 0000 0000 0000 0011 1100 0000 0000

$t0 0000 0000 0000 0000 0000 1100 0000 0000

Lecture 3 — Instructions: Language of the Computer — 25

OR Operations
n Useful to include bits in a word
n Set some bits to 1, leave others unchanged
or $t0, $t1, $t2

$t2 0000 0000 0000 0000 0000 1101 1100 0000

$t1 0000 0000 0000 0000 0011 1100 0000 0000

$t0 0000 0000 0000 0000 0011 1101 1100 0000

Lecture 3 — Instructions: Language of the Computer — 26

NOT Operations
n Useful to invert bits in a word
n Change 0 to 1, and 1 to 0
n MIPS has NOR 3-operand instruction
n a NOR b == NOT ( a OR b )
nor $t0, $t1, $zero Register 0: always
read as zero

$t1 0000 0000 0000 0000 0011 1100 0000 0000

$t0 1111 1111 1111 1111 1100 0011 1111 1111

Lecture 3 — Instructions: Language of the Computer — 27

Conditional Operations
n Branch to a labeled instruction if a
condition is true
n Otherwise, continue sequentially
n beq rs, rt, L1
n if (rs == rt) branch to instruction labeled L1;
n bne rs, rt, L1
n if (rs != rt) branch to instruction labeled L1;
n j L1
n unconditional jump to instruction labeled L1

Lecture 3 — Instructions: Language of the Computer — 28