Instruction decoding when instructions are length-variable

Question

Here are some instructions and their corresponding encodings:

55                      push   %ebp
89 e5                   mov    %esp,%ebp
83 ec 18                sub    $0x18,%esp
a1 0c 9f 04 08          mov    0x8049f0c,%eax
85 c0                   test   %eax,%eax
74 12                   je     80484b1 <frame_dummy+0x21>
b8 00 00 00 00          mov    $0x0,%eax
85 c0                   test   %eax,%eax
74 09                   je     80484b1 <frame_dummy+0x21>
c7 04 24 0c 9f 04 08    movl   $0x8049f0c,(%esp)

Today's microprocessors are often 32- or 64-bit and I guess that they usually read data from memory in 4 byte or 8 byte chunks. However, instructions can have variable length. How does a microprocessor decode these instructions and why are they not of constant length to ease implementation?

Answer 1

There are very good reasons to have a fixed instruction length, implementation simplicity being the most important. That's why many processors do indeed have a fixed instruction length, like RISC processors and many early computers.

CISC instruction sets like x86 are desinged to be decoded sequentially (step by step) by microcode. (you can think of microcode as a kind of interpreter for CISC instructions) That was the state of the art in the early 80s when x86 was designed.

Nowadays this is a problem, because microcode is dead. x86 instructions are now broken into smaller µ-ops, not unlike RISC instructions. But to do so, the x86 instructions have to be decoded first. And current CPUs decode up to 4 instructions each cycle. Because there is no time to decode sequentially one instruction after another, this works simply by brute force. When a line is brought in from the instruction cache, many decoders decode the line in parallel. One instruction decoder at each possible byte offset. After the deocoding, the length of each instruction is known, and the processor decides which decoders actually provide valid instructions. This is wasteful, but very fast.

Variable instruction sizes introduce more headakes, e.g. an instruction can span two cache lines or even two pages in memory. So your observation is spot on. Today nobody would design a CISC instruction set like x86. However, some RISCs have recently introduced a second instruction size to get more compact code: MIPS16, ARM-Thumb, etc.