Two-Address Instructions and Destructive Operands

An instruction that computes d = a + b and leaves a and b unchanged is a three-address instruction, and it is the natural form for a compiler’s intermediate representation because it matches the way expressions are written. Many real instruction sets do not provide it. They provide a = a + b, where the destination is also the first source, and the encoding has room for two register fields rather than three.

That difference is not cosmetic. It means the selector cannot simply map each IR instruction onto a machine instruction; it must ensure that the value it wants to destroy is no longer needed, or insert a copy to preserve it. The copies are real instructions, they consume issue slots, and they extend live ranges. Managing them is a distinct part of code generation, and it interacts with register allocation in ways that shape the whole back-end pipeline.

Why Destructive Forms Exist

The encoding argument is the original one. An instruction with three register operands needs three register fields plus an opcode. Fitting that into a fixed-width instruction word competes with everything else the word must hold — immediate fields, addressing mode bits, condition codes. Two-operand forms free bits, and the freed bits buy larger immediates or more opcodes. This is why x86 is fundamentally a two-operand machine: add %ebx, %eax computes %eax = %eax + %ebx, and the destination is also a source even when the other operand comes from memory.

The second argument is datapath reuse. A two-operand ALU reads one operand into an accumulator-like register, combines it with the other, and writes back to the same register file port. Three-operand designs need either an extra read port or a bypass network that can forward the result to a third location. Both cost area, and on small embedded cores the two-operand form is the one that fits.

The third argument is code density, on the architectures where it applies. With a variable-length encoding, every register field costs bits, so dropping one field from an arithmetic instruction shortens its encoding, and shorter encodings mean more instructions fit in a cache line. On a fixed-width RISC encoding the instruction word is the same size either way and the argument does not apply, which is part of why the load-store RISC designs chose three-operand forms. On architectures where code size dominates — microcontrollers with narrow instruction memories, bytecode formats — the density gain outweighs the extra copies.

The counter-argument is that the compiler pays for the encoding saving. Every destructive instruction is a constraint on the register allocator, and constraints that are not satisfied become copies. The trade is between bits in the instruction word and instructions in the stream, and the right point depends on whether the program is fetch-bound or issue-bound.

The Constraint in the Selector

The constraint is not a property of the IR, which is why it appears as an annotation on the pattern rather than as a change to the intermediate form described in Instruction Selection as Tree Tiling. A machine description records it as a property of the pattern. The pattern for the two-operand add says that its destination register must be the same as its first source register, and that the second source is free. Some descriptions express this as a tied operand: operand 0 and operand 1 are the same location, and the description states the tie explicitly so the generator knows to enforce it.

Given a three-address IR instruction t3 = add t1, t2, the selector has three legal strategies.

The first is to pick the destination as t1 and arrange that t1’s current register holds the value and is dead afterwards. If t1 is dead after this instruction, nothing needs to be preserved, and the destructive form is free. If t1 is live afterwards, the value must be copied to a fresh register first, and the copy precedes the add.

The second strategy is to pick the destination as t2 and mirror the analysis. Which of the two is cheaper depends on which source dies, and a selector that tracks use counts can choose per instruction.

The third is to avoid the destructive instruction entirely by using a three-operand form when the target has one for that operation. Many targets are mixed: integer adds are two-operand, but multiply-add and some vector operations are three-operand. The description’s pattern set reflects this, and the selector’s cost model must price the copy so that it prefers the three-operand form only when the copy would actually be needed.

The copies inserted at this stage are not the same as the copies the register allocator inserts for spills. Selection-time copies exist because of an instruction encoding constraint and are usually removable by coalescing; spill copies exist because of a shortage of registers and are not. Keeping the two kinds distinguishable — by marking them, or by keeping them in a separate pseudo-instruction that survives until allocation — is what allows the later pass to remove the first kind without disturbing the second.

Copy Propagation and Coalescing

A copy inserted before a destructive instruction has an obvious intended victim: the allocator should assign the copy’s source and destination the same register whenever possible, which makes the copy a no-op that can be deleted. This is coalescing, and it is the standard repair for selection-induced copies.

Coalescing is not free. Merging two live ranges means the merged range is live wherever either was live, so the merged range may conflict with more ranges and may not fit in the available registers. An aggressive coalescing pass can turn a program that allocated cleanly into one that spills. The classical formulation therefore coalesces conservatively: merge only when the result is known not to make the graph uncolorable, which for a graph-colouring allocator means applying the Briggs test — the merged node may be coalesced only if it has fewer than K neighbours of significant degree, where K is the number of colours. Conservative coalescing leaves some copies behind, which is the price of guaranteeing no new spills.

The interaction with selection is direct. A selector that inserts many copies because it chose destructive forms freely creates a coalescing problem for the allocator. A selector that prefers non-destructive forms where they exist creates fewer copies and leaves the allocator more freedom, at the cost of possibly longer encodings. There is no setting of either pass that is right for every function, which is why the split between them is a design decision rather than a derived one.

Two-address constraints also interact with the register class hierarchy. On x86, some operations require their operands in specific registers: shifts by a variable count use the count register, multiplies and divides use fixed accumulator pairs, and string operations use fixed index registers. These are not ties between operands but ties between an operand and an architectural register, and they are stronger constraints because the allocator cannot coalesce them away. The usual handling is to insert a copy to the fixed register before the instruction and a copy out afterwards, and to keep the fixed register out of the allocator’s pool for the duration of the live range. This is why a function with many divisions on such a target shows a distinctive pattern of moves around the divide.

The Copy Is Not Always Cheap

On an out-of-order core, a register-to-register move is often eliminated at rename: the move is recognized as an identity and the destination is mapped to the source’s physical register, so the move occupies a decode slot but no execution unit and no writeback bandwidth. On an in-order core without renaming, the move is a real instruction that takes an issue slot and a cycle. On a core with limited move elimination, some moves are eliminated and others are not, depending on whether the source is available at rename time.

This makes the cost of a copy target-specific in a way that a static instruction count cannot express. A selector that counts a move as one instruction overestimates its cost on a renaming core and underestimates it on an in-order core with a narrow issue width. The usual compromise is to price a move below a general ALU operation but above zero, and to let the scheduler and allocator do what they can.

There is a correctness issue hiding in the same place. A copy that is inserted to satisfy a two-address constraint must not be moved after the instruction it feeds, and must not be deleted if the instruction reads its destination as an input. In AT&T syntax, mov %eax, %ebx followed by add %ecx, %ebx computes %ebx = %ebx + %ecx, so the add reads the register the move wrote; deleting the move would make the add read whatever %ebx held before. The rule is that a copy into a register that is subsequently read before being written is not dead, and the dead-code pass must model the destructive read as a use. A pass that treats the add’s destination as write-only will delete the move and change the result, and because the allocator’s coalescing decisions vary with the rest of the function, the resulting miscompile can appear on one build of a function and not another.

Mixed Targets and the Cost of Generality

A compiler that targets both three-address and two-address machines cannot hard-code either assumption. The machine description carries the constraint, and the selector’s output is a sequence that may contain copies wherever a constraint could not be met. The same IR therefore produces different code on different targets without any target-specific pass, which is the point of describing constraints declaratively.

The cost of that generality is that the selector must reason about copies it has not yet inserted. A pattern’s nominal cost is one instruction; the effective cost is one instruction plus the copies needed to satisfy its ties plus the pressure those copies create. The last term is unknowable at selection time, so the first two are approximated and the third is left to the allocator. This is the same layering that appears in scheduling and in tiling, and it produces the same symptom: a locally optimal choice that is globally mediocre. The interaction is examined at length in Scheduling Before Allocation and the Pressure Trade.

Some compilers reduce the problem by running a copy-elimination pass immediately after selection and before scheduling, so that the scheduler sees the stream the allocator will see rather than one padded with moves that will vanish. Others defer and rely on the allocator’s coalescing. Both work; the first makes the scheduler’s job easier and the second makes the allocator’s job harder, and which is preferable depends on whether the target’s issue width or its register file is the scarcer resource.