Instruction combining
Definition
Instruction combining refers to the process of collapsing two or more consecutive instructions into a single instruction (or, more generally, a shorter sequence) that has the same semantic effect on program state. It is the inverse transformation of instruction decomposition and is closely related to the broader notion of equivalent instruction sequences.
In practical terms, an instruction combiner recognizes a pattern such as
mov r3, r0
str r3, [fp, #-8]
and replaces it with an instruction that performs the same effect without the intermediate move:
str r0, [fp, #-8]
The two programs differ in edit distance and instruction count, but produce identical observable behavior.
Motivating use cases
Chip verification (SEPE-SQED)
Symbolic Quick Error Detection (SQED) checks processor correctness by executing a program together with a semantically equivalent program and comparing their effects. A core limitation of SQED is that it struggles to detect single-instruction bugs because the self-consistency comparison does not differentiate the impact of a fault in the original instruction. SEPE-SQED addresses this by using program synthesis to construct semantically equivalent programs from instruction combinations that are shorter than the original. Comparing the original program against its combined equivalent makes single-instruction faults observable. SEPE-SQED notes that this approach yields a wider variety of instruction combinations than prior methods and can produce shorter traces that still expose bugs. (Source: SEPE-SQED paper, arXiv:2404.03172)
CISC-to-RISC transpilation
In CISC-to-RISC transpilation (e.g., the "Guaranteed Guess" system), one of the recurring edit transformations between ground-truth and predicted translations is exactly multiple instructions combined into a single equivalent instruction. The table of transpilation edit patterns explicitly lists this case (program P135), with the canonical example of merging a register-move followed by a store into a direct store using the original register. The same source documents several adjacent transformations that interact with combining — register renaming for temporaries, stack-slot reordering, literal-pool vs. immediate constants, and alternative multi-instruction encodings of the same logical operation (P103). (Source: Guaranteed Guess, arXiv:2506.14606)
Properties
- Semantic equivalence. The combined form must produce identical observable state on the target ISA. Two programs whose only difference is an instruction-combining transformation are valid members of a set of equivalent instruction sequences.
- Shortening. Combining typically reduces static instruction count, though it may increase code complexity or require a register that is free at that program point.
- Context sensitivity. Whether a pattern can be combined depends on liveness of the intermediate register, available addressing modes, and constant-pool constraints.
Examples (from transpilation edit-distance analysis)
| Pattern | Ground truth | Predicted (combined) |
|---|---|---|
| Move + store fusion (P135) | mov r3, r0; str r3, [fp, #-8] |
str r0, [fp, #-8] |
| Equivalent logical operation (P103) | cmp r3, #0; and r3, r3, #1; rsblt r3, r3, #0 |
rsbs r2, r3, #0; and r3, r3, #1; and r2, r2, #1; rsbpl r3, r2, #0 |
These illustrate two flavors of combining: (a) replacing a short sequence with a single fused instruction, and (b) replacing a sequence with a different but equivalent sequence of comparable length that still qualifies as a combining/simplification pass.
Relationship to other techniques
Instruction combining is a specific instance of working with equivalent instruction sequences, in which multiple syntactically distinct programs are accepted as semantically equivalent for the purposes of verification or transformation.
Targets
- ARM — concrete examples and transpilation patterns shown above target the ARM ISA.