ARM instruction encoding

Overview

An ARM instruction encoding is the binary pattern that defines a category of ARM machine instructions. Each encoding partitions the bits of an instruction word into fields that are fixed (constant) and fields that vary. The variable fields are called encoding symbols and determine operands such as registers, addressing modes, and immediate values ^[1]. A given functional instruction (e.g., STR (immediate)) typically corresponds to one or more of these encoding patterns, and the ARM architecture as a whole specifies 1,998 instruction encodings distributed across four instruction sets: A64, A32, T32, and T16 ^[2].

Structure of an encoding

An instruction encoding is represented as a bit-level diagram. Bits whose value does not change across all instructions of that category are written as constant 0/1 values in the diagram, while the remaining fields are labeled with symbol names that the decoder interprets.

In the STR (immediate) example from the literature, the 32-bit word is divided as follows ^[3]:

Bits [31:20] and bit [7] hold fixed values (111110000100 and 1, respectively).
The remaining six fields are encoding symbols: Rn (base register), Rt (source register), P (indexing), U (add/subtract offset), W (write-back), and Imm8 (immediate offset).

Filling in concrete values for these six symbols produces a syntactically valid encoding that, if it also satisfies the constraints embedded in the instruction's semantics, is a valid instance of the instruction.

Decoding and execution (ASL)

Every ARM instruction encoding is paired with decoding and execution logic written in ARM's Architecture Specific Language (ASL) ^[1]. The decoding ASL maps raw bit fields to architectural operands, and the execution ASL describes the architectural effect when the instruction runs. ASL code is constraint-driven: it contains conditions on the encoding symbols (for example, the constraint Rt == 15 in the STR (immediate) semantics), and an instruction is only well-formed when its concrete bit pattern satisfies those constraints ^[3]. Different execution paths inside the ASL code correspond to different instruction behaviors, so a comprehensive test of an encoding must cover both syntactic variation of the symbols and the semantic constraints that govern the ASL branches.

Instruction sets and architectural variants

The ARM architecture exposes multiple instruction-set variants whose encodings differ in width and in how the bit fields are interpreted ^[1]:

A64 — 64-bit encodings used in the AArch64 execution state.
A32 — 32-bit encodings used in the AArch32 ARM mode.
T32 — 32-bit encodings used in the Thumb-2 mode.
T16 — 16-bit encodings used in the original Thumb mode.

These encodings coexist with several architecture revisions (ARMv5, ARMv6, ARMv7, ARMv8) and with both 16-bit and 32-bit register widths, which together account for the breadth of the encoding space ^[2].

Enumerating the encoding space

Because an ARM instruction word is 32 bits wide, naive enumeration of every possible bit pattern would require 2^32 candidate streams, which is infeasible to evaluate ^[1]. An encoding-aware enumeration instead:

Walks the set of 1,998 declared instruction encodings.
For each encoding, mutates only the encoding symbols (using a fixed rule set for symbols such as immediates — typically covering a maximum, a minimum, and a number of random values) to produce syntactically valid instances ^[3]^[1].
Uses a symbolic-execution engine over the ASL to solve (and negate) the constraints on the symbols, so that the chosen concrete values additionally satisfy the semantic conditions in the decoding and execution code ^[3].

This encoding-aware approach has been shown to reach the full set of 1,998 ARM instruction encodings with about 2.77 million generated instruction streams, whereas a comparable number of randomly generated streams covered only about 54.5% of the encodings ^[2].