Birth of x86

Intel's first 16bit processors (but not world-first):

1978: 8086

16-bit processor with 16-bit data bus & 20-bit address bus (1MB RAM/Mapped IO)

1979: 8088 (1st IBM PC)

As above except 8-bit data bus

1982: 80186

Intended for embedded devices

1982: 80286

24-bit addressing (16MB RAM), memory protection & multi tasking

x86

1985: 80386

32-bit w/ paging, used in 1st notable non-IBM PC-compatible, 32-bit addressing (4GB)

1989: i486

pipelined design, onchip cache, onchip FPU

1989: P5 microarchitecture (Pentium, i586 etc)

superscalar architecture

x86

1995: P6 microarchitecture

Pentium Pro — Pentium III
Speculative execution, out-of-order execution, register renaming. 36-bit (64GB) physical memory, CMOV, etc.

2000: Netburst microarchitecture

Pentium 4 etc
Hyper-threading, pipeline "improvements".

2003: AMD Opteron

AMD64 (aka x86-64, aka Intel 64, IA-64, x64), 48-bit (256TB) virtual memory.

What is a CPU really?

What do CPUs do?

8d 0c ff          lea    (%rdi,%rdi,8),%ecx
ba 67 66 66 66    mov    $0x66666667,%edx
89 c8             mov    %ecx,%eax
f7 ea             imul   %edx
d1 fa             sar    %edx
c1 f9 1f          sar    $0x1f,%ecx
29 ca             sub    %ecx,%edx
8d 42 20          lea    0x20(%rdx),%eax
c3                retq

AT&T syntax

Huh?

32-bit x86 can add 1 to the value at a 32-bit address:

addl   $1, (0xABCDEF08)

addq   $1, (0xABCDEF08ABCDEF01)

addq   $0xABCDEF08ABCDEF08, %rax

movq   $0xABCDEF08ABCEEF08, %rbx
addq   $1, (%rbx)

Hypothetical instruction encoding

Understanding a CPU

8086 Instruction encoding

Mode:

Meaning of operand 2

Reg:

Operand 1

R/M:

Operand 2, register or memory pointed to by register with optional displacement

This allows memory operands of the form:

address = base + index + displacement

Good for looking up a field in a struct or an array, or a struct in an array.

80386 instruction encoding

If R/M = 100 then the SIB byte is used to specify more addressing forms

address = base + index × scale + displacement
scale = 1, 2, 4 or 8

x86-64 instruction encoding

x86-64 adds 8 new registers. But register fields are only 3 bits long, how will we solve this?

Instruction prefixes!

Instruction prefix with SIB byte

I need two instructions on x86-64 to do the job of one on x86.

// 32-bit.
addl $1, disp32

The $1 is the immediate value in this instruction, and disp32 is a 32-bit address.

// 64-bit
movq imm64,  %r11
addl $1,     (%r11)

On x86-64 the pointer is too big to fit in a memory displacement. It must now be in imm64.

Processor modes

• Real mode (16-bit)
• Protected mode (16-bit with protection on segments, multi-tasking)
• 32-bit protected mode (paging)
• Virtual 8086 mode (16-bit dosbox running in host OS)
• Unreal mode (weird unofficial hack)
• 64-bit
• 64-bit features with 32-bit address (I forget the name)

Real mode segments

Why have a colon in a memory address?

The 8086 can address 20-bits of memory, with only 16-bit registers.

1234:0023
segment:address

Segment size and alignment

Segments are 64k large and align on 16 bit boundaries

This means segments can overlap

Wrapping

With 16 bit segment bases, shifted up four bits, plus another 16 bit address, we can generate addresses such as:

0xFFFF << 4 + 0x0011
= 0xFFFF0 + 0x0011
= 0x100001

But 0x100001 needs more than the 20 bits that 8086 supported!

It gets truncated
= 0x1

Some software relied on this "feature".

Backwards compatibility

286 supports 24-bit physical addresses, but wants to run software made for 8086 even software that abuses the 20-bit physical address space.

A20 gate

At boot wrapping is enabled and an x86 can only access half its memory

A20 gate

A20 gate

• BIOS-based PCs needed to handle this until recently
• I suspect that if you boot DOS then you'll still get the older wrapping behaviour
• IBM's fault, not Intel's

Guess what else the keyboard controller does?

Intel didn't include a way to switch from one of its protected modes back to real mode. This made systems that used both, eg: calls into a real-mode BIOS routine really slow.

The "hack" was to triple-fault the CPU to reset it, get it to execute the BIOS code, then switch back into protected mode.

Later a faster method was created that used the keyboard controller to hard-reset the CPU, avoiding the triple-fault.

Instruction delays (then)

• Instructions take varying numbers of cycles.
• mul/div could take varying numbers of cycles.
• Each new processor generation changed the cycles required for many instructions.

Optimising compute-bound tasks meant counting cycles. Reference manuals included tables showing the number of cycles for each instruction on each processor.

This is not (as) useful on modern processors. Two other effects dominate performance...

Memory access

CPU performance increased but memory latency and bandwidth lagged. Caches gave CPUs access to recently used data sooner.

Pipelines

Used earlier but saw slightly heavier usage with the 486

Like a factory assembly line, While one instruction is executed the next one is already being decoded.

Deep pipelines

Super-scalar (P5)

Stalls

A delay in the pipeline can occur for:

• Cache miss
• Unknown branch
• Fetch and decode related delay

Optimising for modern machines means reducing mostly the first two types of stalls.

Out-of-order (P6)

Speculative (P6)

CPUs guess which branch might be taken and start processing instructions along the most likely branch.

Instructions are only committed (retired) when we know that branch is taken.

A miss-predicted branch means a pipeline flush. The longer the pipeline, the bigger the flush.

The Spectre in the room

A CPU must not give private/kernel information to userspace processes.

It will issue a General Protection Fault before divulging secrets!

if ...:
    array[secret]
else:
    // see which parts of array are in cache

Modern pipeline (Skylake)

Common opcodes

• Arithmetic and logic: add, subtract, multiply, divide, and, or, xor, shift, etc.
• Loads: load, store, push, pop, exchange, (kinda: in, out).
• Control flow: jump, conditional jump, call, return.
• System: sti, lgdt (etc, very architecture-specific).

Opcodes often encode the type of data to work with. (8-bit, 16-bit etc).

Registers

x86 has 8 kinda-general purpose registers, kinda because most have special powers.

Registers

String operations: An instruction can be repeated advancing a counter (cx) until some condition is met.

The CPU also has an instruction pointer (ip) and a flags word and some segment registers.

Opcodes and mnemonics

In machine code the what to do is called the opcode, but in assembler it is called a mnemonic. They don't map 1-to-1.

Sometimes opcodes encode the data type to work on, which is not always part of the mnemonic.

32-bit register file

eax is the Extended AX register on 32-bit x86 processors. Its low 16 bits are shared with ax.

rax is the Register A eXtended on x86-64 processors. Its low 32 bits are shard with eax.

Example of mnemonics

What does it mean to exchange the contents of a register with itself?

// assembles to opcode 90 (x86-64)
xchg rax, rax

CPUs also recognise other instructions

What does this do?

xor eax, eax

Favourite instructions

// Swap two values
xchg eax, ebx
xchg eax, [edx]

// population count (count the number of bits
// set to 1).
popcnt ecx, eax

// strcpy, copy ecx bytes from ds:[esi]
// to es:[edi]
rep movsl