What Is an Instruction?

Did you ever think about how your CPU executes the code that you wrote? The compiler takes your code and turns it into an executable binary. This binary is loaded into memory. CPU reads instructions from the memory one-by-one and executes them. Let's look closely at the example:

Open this example in Compiler Explorer

With all optimizations enabled in GCC it's just three lines of assembly

imul edi, edi # multiply 1st argument by itself and store result back to edi
mov eax, edi  # move contents of edi to eax
ret           # return control back to caller

The first puzzling thing we meet in the piece above is edi. What is that? CPU instructions operate on registers. x86_64 provides 16 general-purpose 64-bit registers, up to 32 vector registers (256 or 512 bits long depending on extension support) and recently even 8 tile registers of up to 1KB size. Registers hold state. They can either be explicit like in the example above or implicit. Consider this example.

Open this example in Compiler Explorer

The cmovns instruction performs a conditional move. Specifically, it copies contents of edi into eax if condition is met. But there's only two arguments. How does cmov know when to actually perform the move? The test instruction just above it writes to a special EFLAGS register and cmov reads from it. You never see the register name in assembly, but it's always there.

Collectively we refer to a set of instructions, register files and other states as Instruction Set Architecture (ISA).

Now, why do we read specifically from edi? In most modern architectures registers a truly general purpose. You can use them however you want. But to make programs and libraries interact with each other platforms usually come up with conventions. For example, on x86_64 under Linux integer function arguments are placed into registers in the following order: rdi, rsi, rdx, rcx, r8, and r9. If there are more integer arguments, they will be spilled into stack. These rules are known as Application Binary Interface (ABI). Linux usually follows System V ABI rules: https://wiki.osdev.org/System_V_ABI.

ABI and ISA are two of the most important hardware-software contracts when building a compiler.

Formalizing ISA descriptions

This was a short primer on assembly programming for those who are unfamiliar with it. This topic is usually referred to as extremely complicated but in practice it is not. It's more of a cognitive load issue when writing big applications rather than complexity of the concept. Unless you try to make sense of all of it.

ISA usually comes in a form of a huge manual. For example, RISC-V is around 700 pages. How do you compress all that knowledge into a compiler? Usually, with a ton of sweat, blood, tears and some elbow grease. But a couple of years ago a colleague introduced me to the concept of Architecture Description Languages and a wonderful blog of Alastair Reid.

ADLs try to express human wisdom about computers in a machine-readable format. They describe assembly syntax, encoding rules, and semantics of the instruction. Sail is probably the biggest one of those. There's also Arm Architecture Specification Language that is specific to Arm and a few other commercial options.

My biggest problems with them is usually these languages are developed by hardware people and the languages usually lack the structure required to actually build a compiler from them. Which is why for TIR I decided to create a new ADL tailored for its need.

Requirements for this new language a roughly this:

• Have a rigid structure for compilers to rely on;
• Easy to understand, no steep learning curve;
• Semantics should be accurate (even precise) for formal verification of both compiler and hardware;
• Capture performance details of the target devices.

To understand the requirements better we first must understand what we're dealing with.

RISC-V

Let's start with the new kid on the block - RISC-V. Developed at the University of California in 2010, it quickly gained popularity with big firms like Google, IBM and Qualcomm being actively involved in its development. The specification is open source and royalty free. RISC-V promise is to liberate us from bloatware of past architecture and make both hardware and compiler development much easier.

RISC-V is built around the idea of extensions. It's like walking into a restaurant and ordering off the menu. I'll have floats, doubles and vector instructions, please. Or you can just order coffee basic integer extension. Each extension can define a set of instructions and architectural states (registers, etc). Base ISA defines 32 registers with one of them being a hardwired-zero. It also defines 40 instructions (for 32 bit variant) split into 7 instruction formats.

Sounds good, right? But let's look closer at some of the instructions, specifically slli (shift left logical immediate):

Technically, this instruction is supposed to be I-type. In practice it does not make sense to shift a value to more than XLEN bits - a value that only requires five or six bits out of the available twelve. The spec shows the other bits are used to distinguish between logical and arithmetic right shift. So, technically, we have at least one more instruction format, because the meaning of those bits is different from what's described by I-type. Just a few pages into the spec and we're already breaking rules and making exceptions.

Here's another one. Look at the example below. Normally, this is a two-instruction function: we add two numbers and return. Maybe three if you need to move to another register. With RISC-V you don't really have instructions to operate on 16 bit (or 8 bit) values. So you have to do this shit trick to get an expected value. This really complicates our otherwise beautiful instruction selection logic (seriously, sometimes I think these architecture guys genuinely hate us).

Open this example in Compiler Explorer

And don't get me started on RVV vector extension. It ruins all the claimed benefits entirely. I will do a separate piece on vector instruction sets but here's a short list of complaints. vtype register is an implicit state we so desperately tried to escape so far. It complicates literally every piece of the stack: hardware, software, compilers. LMUL (grouping multiple registers into one big register) is marketed as free performance. Well, it's not. The hardware pipeline does not magically get wider. Instead, it would split your wide instruction into multiple micro operations and execute sequentially. The only worthy application here is hardware-assisted loop interleaving, but is it worth all the effort? The extension written in a way that assumes CPUs would grow wider indefinitely. Bloody physics constraints us though. Most modern processors have 64 byte cache lines. This perfectly translates to 512-bit registers. Growing beyond that requires changes down the entire stack: memory controller, cache port width, etc. This is too much. And the tasks that benefit from this kind of change are also perfect for specialized accelerators like GPUs or NPUs, which on top of better performance give you far better power efficiency.

“Extrapolating,” xkcd #605, licensed under CC BY-NC 2.5.

ARM

ARM is arguably the most used ISA today. Your phone runs on ARM. In the recent years it got real traction in the data center space and on laptops. Apple's M series chips proved that powerful compute is not limited to x86 and ARM can be just as good and even better.

But there are a lot of misconceptions about ARM. For starters, ARM is not a single ISA. Modern 64-bit ARM processors use A64 instruction set in the AArch64 execution state. Older ARM processors also used A32 and T32 instruction sets. They have different encodings and pursuite different goals. For the rest of this section I exclusively talk about A64.

A64 has 32-bit instruction words, 31 general-purpose integer registers, and a load-store architecture. Arithmetic instructions operate on registers; memory is accessed through explicit load and store instructions. Very similar where RISC-V landed. But I'd say this is where similarities end.

First, let's look at the register file map. Unlike RISC-V, AArch64 exposes multiple views of its integer and SIMD registers. The SIMD and floating-point views overlap, and SVE extends the same low 128 bits. There's a very good reason to do this. Register files can be huge - I've seen vector register files exceeding die area of the actual compute core. Saving that precious space makes your chips either cheaper or more powerful by fitting more cores into the same area. But it comes at the expense of compiler complexity - we now need to take into account multiple register classes and we overall have less architectural space to work with which forces more frequent spills. A quite reasonable trade off, if you ask me.

AArch64 register aliases

Encoding 31 means XZR or SP depending on the operand position. The same five encoded bits therefore name either the zero register or stack pointer.

For comparison, a RISC-V xN register has XLEN bits and no narrower aliases.

But shennanigans don't end with just aliasing. See in the map above that register number 31? Depending on the instruction and operand position, the five-bit value 11111 can mean either the stack pointer or the hard-wired zero register. Reading xzr produces zero and writing it discards the result. Reading or writing sp, unsurprisingly, accesses the stack pointer. So, in practice we have two registers with overlapping encodings.

Immediate values have their own surprises. An add immediate contains a 12-bit value that can optionally be shifted left by twelve bits. Logical instructions use a stranger scheme: they encode repeated, rotated bit patterns rather than a conventional integer. Consequently, this is encodable in one instruction:

and x0, x1, #0x00ff00ff00ff00ff

while many seemingly simpler 64-bit constants are not.

From a compiler's perspective, an immediate operand therefore cannot be described merely as “an integer between X and Y.” It may need an encodability predicate and transformations between the value seen by the programmer and the bits stored in the instruction.

Now let's look at a piece of code:

ldr w8, [x0, x1, lsl #2]
add w0, w8, w2
ret

The ldr instruction takes the address in x0, adds x1 multiplied by four, and loads a 32-bit value from the resulting address. The add then adds the third argument and places result into the return register. Quite a lot in just three instructions. And this is another major difference between ARM and RISC-V.

RISC-V tried to be true to its reduced instruction set motto. A similar load on RISC-V would require a shift and an add before we get to load. The benefit of this is that you can implement a fully working RISC-V chip RTL in just one weekend (probably faster if you know what you're doing). Downsides? You see, real programs have those nasty things called arrays. And the way arrays work is you have some base pointer and you add an index multiplied by element size to it to get the destination. Exactly the thing ldr computes for you. x86 similarly have multiple complex addressing modes for the same reason. RISC-V later responded with Zba extension that adds shNadd (N=1,2,3) instructions and they also propose macro-op fusion with ld instruction to achieve parity with x86. Frankly, I think this came too late and the mechanism should have been opt-out style (similar to rv32e 16 register reduced ISA) for microcontrollers rather then coming as an optional extension.

ARM also has a few flag registers (which RISC-V lacks completely in the base ISA). Unlike x86, most integer arithmetic instructions do not update condition flags unless you explicitly ask them to:

add  x0, x1, x2   // do not update flags
adds x0, x1, x2   // update N, Z, C and V

This avoids creating an implicit dependency on the flags register when the result is not going to be used by a conditional instruction. But it introduces aliases. For example:

cmp x1, x2

is not really a separate operation. It is an alias for:

subs xzr, x1, x2

The subtraction is performed, the flags are retained, and the numeric result is thrown away by writing it to the zero register.

Aliases matter when describing an ISA. Does cmp exist as an instruction? To an assembly programmer, yes. To the decoder, no: it is one particular use of subs. A machine description needs to represent both views without duplicating the instruction semantics.

There are some nice things about recent ARM decisions, though. Thumb32 is mostly dead. All instructions are 32 bits length (unlike RISC-V where they can be 2-16 bytes and compressed 2-byte instructions are mandatory in RVA23 profile, or x86 where they are 1-15 bytes). Such uniformity means instruction decoder (hardware or software for that matter) is extremely simple and the code is always aligned at instruction size. This is exactly what allowed Apple introduce an 8-issue beast in 2020.

x86

If RISC-V was designed and Arm was carefully engineered, x86 mostly happened.

That is not an insult. The architecture survived because every generation preserved an enormous body of existing software while adding whatever the next generation needed. The result is extraordinarily capable, remarkably compatible, and deeply inconvenient to describe.

Much like A64, registers in x86 can overlap. But they do so in a much more chaotic way. The original 8086 had fourteen 16-bit registers, but only four of them were general-purpose. You could also access low and high parts of those via AH/AL style aliases. 80386 upgraded registers to 32-bits. Old AX, BX, CX, DX are now the lower part of EAX, EBX, ECX, EDX, but you can't access high part. AMD Opteron introduced x86-64 architecture, which did another upgrade to 64-bit registers and added eight additional GPRs r8-r15.

x86-64 register aliases

Legacy, VEX, and EVEX encodings differ in what a write to YMM0 or XMM0 does to the upper bits.

Unlike A64, x86 instructions have variable length. An instruction can contain legacy prefixes, a REX or vector prefix, one or more opcode bytes, a ModR/M byte, an optional SIB byte, a displacement, and an immediate. The complete instruction may be anywhere from one to fifteen bytes long.

Consider the following instruction:

add eax, DWORD PTR [rbx + rcx*4 + 8]

It reads a 32-bit integer from memory, adds it to eax, writes the result back to eax, and updates the condition flags. The address is calculated from a base register, a scaled index register, and a displacement—all in one instruction.

One possible encoding is:

03 44 8b 08

The first byte selects a form of add. The next byte says that the source is a memory operand, the destination is eax, and a SIB byte follows. The SIB byte chooses rbx as the base, rcx as the index, and four as its scale. The final byte is the displacement.

This is not a row of independent fields like a RISC-V instruction format. One field determines whether another field exists, and that field can in turn change the interpretation of values elsewhere in the instruction. Prefixes may change operand size, address size, available registers, or even the instruction selected by an opcode.

The same assembly instruction can also have more than one valid encoding. Conversely, almost identical encodings can acquire different meanings depending on the execution mode and prefixes preceding them. Decoding x86 is closer to walking through a decision tree than extracting fields from a bit structure.

x86 also makes extensive use of implicit state. Ordinary integer arithmetic normally updates several flags whether the program needs them or not. Multiplication and division have forms with implicit input and output registers. String instructions implicitly use source and destination pointers, a counter, and the direction flag. An instruction that appears to have no operands in assembly may therefore read and modify half a dozen pieces of architectural state.

There are no scalar floats in x86 instruction set. At all. The old way of doing things was something called x87. To process floats you had to acquire a separate co-processor, like 8087. Floats were 80 bit long. The architecture itself was stack-based as opposed to register based architecture we use and love today. Only with introduction of x86-64 we gained true floating point instructions. What we didn't get is separate float registers. Instead, SSE re-uses vector registers for float calculations. So, conceptually, each float operation just rides on a single lane of a wider SIMD engine. And I like that decision a lot. SIMD is a great way to extract more parallelism in the program and float subroutines tend to be compute heavy and parallelization friendly most of the time. I really wish RISC-V had adopted this decision (it still can for OoO cores with register renaming).

TMDL

TIR Machine Description Language. One specification to generate selection rules, usable ISA simulators, assembly and object parsers/emitters and more.

Let's start with registers.

isa RV32I {
    param XLEN: Integer = 32;
}

isa RV64I {
    param XLEN: Integer = 64;
}

register_class GPR for [RV32I, RV64I] {
    param ENCODING_LEN: Integer = 5;
    param WIDTH: Integer = self.XLEN;

    registers {
        x0("zero") => { traits = [hardwired_zero] },
        x1("ra") => {},
        x2("sp") => {},
        x10..x17("a{}") => {},
        x28..x31("t{}") => {},
    }
}

An isa is a feature and a bag of parameters. In this case both base ISAs define XLEN, so the same register class can use self.XLEN and become 32 or 64 bits wide depending on the selected target. Extensions are ISAs too. They can say requires RV64I, or even requires [RV32I | RV64I] when either base will do. This makes the dependency graph explicit instead of hiding it in a Rust if that nobody remembers to update.

Registers have an encoding width and a value width. Those are not the same thing. A RISC-V register holds 64 bits on RV64, but its name still occupies five bits in an instruction. Aliases go in parentheses. Ranges are expanded by the compiler, and {} in "a{}" is replaced with a number. Finally, hardwired_zero is a trait rather than a special case in the simulator. Reading x0 produces zero. Writing it goes into the same black hole where my expectations for RVV went.

The backend also describes the ABI separately. This one is used by the RV64 and vector definitions:

abi LP64("lp64") for [RV64I, RVV] {
    stack { align = 16; grows = down; red_zone = 0; slot_size = 8; }
    sp = GPR::x2;
    ra = GPR::x1;
    fp = GPR::x8;
    args int -> [GPR::x10..GPR::x17], then stack;
    args vector -> [VR::v8..VR::v23], then stack;
    rets int -> [GPR::x10, GPR::x11];
    rets vector -> [VR::v8, VR::v9];
    callee_saved = [GPR::x2, GPR::x8..GPR::x9, GPR::x18..GPR::x27];
    reserved = [GPR::x0, GPR::x3, GPR::x4];
    classifier = riscv;
}

Remember our edi question at the beginning? This is where its answer belongs. An ISA says which registers exist. An ABI says that the first argument lives in one of them. Mixing the two is tempting and wrong. The same x86 instruction set is used by System V and Windows, yet they pass arguments in different registers.

Register classes can inherit from one another and describe overlapping files. The x86 backend defines 64-bit GPR, then derives GPR32, GPR16 and GPR8 from it. eax and rax have the same index, therefore the allocator knows they are views of the same physical register. High-byte registers are even more entertaining:

register_class GPR8H for [X86] {
    file = GPR;
    param ENCODING_LEN: Integer = 4;
    param WIDTH: Integer = 8;
    param WRITE_POLICY: String = "merge";
    param BIT_OFFSET: Integer = 8;

    registers {
        ah => { index = 0 },
        ch => { index = 1 },
        dh => { index = 2 },
        bh => { index = 3 },
    }
}

ah shares the GPR file but starts at bit eight. It also cannot be used with a REX prefix, because x86 is a museum where exhibits are still load-bearing. AArch64's register 31 trick is described using the same mechanism. One class names slot 31 xzr, another inherits the file and names that slot sp. Operand position chooses the class and therefore the meaning. No handwritten exception in the assembly parser is required.

Now let's define an instruction. TMDL splits the repetitive shape into a template and keeps the interesting part in the instruction itself. Here is the RISC-V R-type template, shortened only by removing comments:

template RType for [RV32I, RV64I] {
    param MNEMONIC: String;
    param FUNCT7: bits<7>;
    param FUNCT3: bits<3>;
    param OPCODE: bits<7>;

    operands {
        rd: GPR,
        rs1: GPR,
        rs2: GPR,
    }

    encoding {
        0..6 => OPCODE,
        7..11 => rd,
        12..14 => FUNCT3,
        15..19 => rs1,
        20..24 => rs2,
        25..31 => FUNCT7,
    }

    asm { "{self.MNEMONIC} {rd}, {rs1}, {rs2}" }
}

Integer is an unbounded value used while compiling the specification. bits<N> is an N-bit value that exists in the described machine. This distinction catches a surprising number of mistakes. Accidentally stuffing eight bits into a seven-bit opcode should fail here, not become a broken instruction three code generators later.

Bit zero in an encoding block is the least significant bit. Ranges are inclusive, so 0..6 really is seven bits. Operands may be sliced too. The RISC-V store immediate is split across two distant fields with imm[0..4] and imm[5..11]. In x86, r8 through r15 are even sillier. The low three bits go into ModR/M while the fourth bit goes into REX. The real mov load definition says exactly that:

encoding {
    rex!({ base[3] }, { dst[3] }, 0b1)
    8..15 => 0x8B,
    16..18 => base[0..2],
    19..21 => dst[0..2],
    22..23 => 0b00,
}

There is no requirement that an instruction looks like a neat table. TMDL describes the bits that exist, even when one of them has escaped into a prefix several bytes away.

Concrete instructions inherit the structure and fill the holes:

instruction Add for [RV32I, RV64I] : ALUOp {
    param MNEMONIC: String = "add";
    param FUNCT3: bits<3> = 0b000;

    behavior {
        rd = rs1 + rs2;
    }
}

ALUOp itself inherits RType and supplies the common opcode, function bits and scheduling class. This is deliberately boring. Adding an instruction should mostly mean naming its odd bits and stating what it does.

The behavior block is executable semantics. It is used by the interpreter, but it is not merely simulator code. TIR can translate the expression into symbolic form and ask an SMT solver whether an instruction-selection rule preserves the same value. Arithmetic operates on fixed-width bitvectors, so overflow behaves like hardware overflow. Helpers such as sext, zext, extract, load and store make width changes and memory effects explicit.

Real instructions get less cute. This is lw:

instruction LoadWord for [RV32I, RV64I] : LoadInst {
    param MNEMONIC: String = "lw";
    param FUNCT3: bits<3> = 0b010;

    behavior {
        try {
            rd = sext(load(rs1 + sext(imm, self.XLEN), 4, 0b1), self.XLEN);
        } except misaligned_load(addr) {
            trap(4, addr);
        }
    }
}

It calculates the address, loads four bytes, sign-extends the result, and describes the misaligned-access trap. That last part matters. A simulator that quietly accepts every unaligned load is pleasant right until somebody uses it to validate a compiler.

The earlier slli exception also falls out naturally. Its operand is bits<log2Ceil(self.XLEN)>, which is five bits on RV32 and six on RV64. The supposedly generic twelve-bit I-type immediate never enters the picture. We describe the instruction that exists, not the aesthetically pleasing table printed a few pages earlier in the manual.

Implicit state is written by its qualified name. An x86 arithmetic instruction assigns EFLAGS::zf, EFLAGS::sf and friends. A conditional jump reads them in its guard. A call modifies GPR::rsp, stores the return address, then changes PC::pc. This is a small detail with a large consequence: an instruction with zero assembly operands can still expose every state dependency to the compiler and verifier.

Assembly is just another view:

asm { "{self.MNEMONIC} {rd}, {imm}({rs1})" }

The same template drives printing and parsing. Placeholders are typed operands, not a regular expression assembled with hope. Multiple instruction definitions may share a mnemonic when their operand classes or encodings differ. The AArch64 backend has several ldr definitions for integer, float, vector and scaled-offset forms. This is correct. ldr is a spelling, not an instruction identity.

Templates stop being convenient on x86 because changing operand width may add a prefix, move every following field and switch the legal register class. TMDL therefore has Rust-like declarative macros. They rewrite tokens before parsing and can expand at the top level, inside a behavior or even inside an encoding block. The x86 backend uses a tiny rex! macro above, and larger macros generate whole families of ALU and atomic instructions. I did not want to turn the language into a general-purpose metaprogramming swamp, so macro arguments are deliberately limited to identifiers, literals and token trees. Enough rope to remove boilerplate, not enough to establish a consultancy around it.

Finally, an instruction has performance properties. The ISA assigns it to a machine-independent scheduling class:

sched_class WriteIALU { latency = 1; }
sched_class WriteLoad { latency = 3; }

template LoadInst for [RV32I, RV64I] : IType {
    schedule { units = [WriteLoad]; }
}

A concrete machine then binds those classes to real resources:

machine OutOfOrderCore ("rv64-ooo") for [RV64I] {
    issue_width = 4;

    buffers { rob = 128; lsq = 32; iq = 64; }
    unit ALU { count = 4; }
    unit LSU { count = 2; }

    bind WriteIALU { latency = 1; uses = [ALU]; }
    bind WriteLoad { latency = 4; uses = [LSU]; }
    override Add { latency = 2; uses = [ALU]; }
}

This separation is important. add means the same thing on every compliant RISC-V core, but it certainly does not cost the same. A machine can define issue width, pipeline stages, functional units, buffers, forwarding paths, register-file sizes, micro-ops, macro-fusion and dependency-breaking idioms. The compiler cost model and the tir sched analyzer consume the same description. At least when they disagree, they have to find a more interesting excuse.

So an instruction in TMDL is not one record with an opcode glued to it. It is the intersection of several contracts: where it exists, which operands it accepts, how those operands become bits and text, what architectural state changes, and how a particular machine executes it. The syntax stays rigid because every consumer needs to agree on those facts. There is still plenty of room for architectural nonsense. It is simply written down once.

Outro

I think we covered a lot today. Instruction sets appear to be easy. Untill they are not. These complications are a byproduct of their time, or rather constraints engineers faced at that time - expensive memory, power walls, process nodes, even programs people were writing and using. I think TMDL finds a good balance between capturing enough detail about the instructions and leaving old baggage behind. In the next post I will dive deeper into how the DSL compiler itself is built and what kinds of outputs it can produce.

Originally published on cache-miss.dev.