Folding Address Computation into Memory Operands

A load in a three-address intermediate representation names one address. The same load in machine code can name an address that is the sum of a base register, an index register shifted by a constant, and a displacement. The gap between those two statements is a free instruction: on a machine with full addressing modes, x = a[i] costs one load, and on a machine without them it costs a multiply, an add, and a load. Instruction selection is largely the business of closing that gap, and the closing is called addressing-mode folding.

The fold is not a peephole trick applied after the fact. It is a pattern in the selector, and it works only because the selector is allowed to look at a small tree of IR nodes rather than at one instruction at a time, as described in Instruction Selection as Tree Tiling. The tree load(add(base, mul(index, 8))) is one pattern on a target that provides scaled indexing; the flat instruction list that produced it has already separated the multiply from the add, so the selector must first undo that separation by folding single-use definitions into their consumers.

What the Hardware Actually Encodes

The variety of addressing modes across architectures is the reason the fold has to be target-specific rather than universal. Three families cover most of the space.

Complex addressing, as on x86-64, allows an effective address of base plus index times a scale of 1, 2, 4, or 8 plus a displacement, with the displacement encoded as 8, 16, or 32 bits depending on the instruction form. The scale factors correspond to the element sizes that matter for arrays of bytes, 16-bit values, 32-bit values, and 64-bit values, which is why a scaled index folds an array subscript’s multiplication at no cost. Segment override and RIP-relative forms extend the model, and the latter is how position-independent code reaches globals without an absolute address.

Scaled and unscaled immediate offsets, as on AArch64 and RISC-V, allow a base register plus an immediate. AArch64’s unsigned-offset load and store forms scale the 12-bit field by the access size, so the field reaches 4095 times 8 bytes on a 64-bit access but only 4095 bytes on a byte access; a byte offset that is not a multiple of the access size cannot be encoded in that form at all, and the selector must either use the separate unscaled form with its 9-bit signed field or compute the address in a register. RISC-V’s base load and store instructions take a signed 12-bit byte offset, so the reach is a fixed -2048 to 2047 bytes regardless of access width, and larger offsets need a separate add. AArch64 also provides pre-indexed and post-indexed forms that update the base register as part of the access, which folds a pointer increment into the load.

Minimal addressing, as on many DSPs and some embedded cores, allows a base register plus a small immediate, or base plus index without scaling. On such targets the fold is limited to constant offsets and the array index’s multiply survives as a separate instruction. The selector’s pattern set is correspondingly smaller, and the cost of the missing mode is paid on every array access in the program.

The general lesson is that the addressing mode is a small arithmetic unit embedded in the memory instruction. It can add, shift, and sometimes update a register, and it can do so without occupying the main ALU or an extra instruction slot. Anything the addressing unit can compute is free; anything it cannot must be computed explicitly.

The Fold as a Pattern Match

Mechanically, folding is a pattern with a nested structure. The pattern for a scaled-index load matches a load node whose address child is an add node, whose children are a base and a multiply, whose multiply has an index and a constant that is one of the legal scales. The selector emits one instruction and marks all the matched nodes as covered, so they are not emitted separately.

The constraint that makes this work is single use. If the address computation’s result is used by two loads, folding it into one of them leaves the other needing the value in a register, so the computation must be emitted anyway and the fold saves nothing. Worse, it saves nothing while making the code larger, because the folded load has a longer encoding than a register-indirect load. Selectors therefore test the use count of the address node before folding, and the count must be computed before selection begins rather than during it, since selection itself destroys the information by covering nodes.

There is a subtler constraint on the multiply. The IR’s multiply by 8 might have other uses, or might be a multiply by a value the selector cannot prove is 8. Only a constant multiplier whose value is in the legal scale set can fold. If the multiplier is a variable, the target must have a base-plus-unscaled-index mode or the multiply stays. This is why loop strength reduction, which rewrites a[i] into a pointer increment, is valuable on targets with weak addressing modes: it removes the multiply that the addressing mode could not absorb.

Constants interact with the fold in a second way. A global variable access is an address that is a link-time constant plus an offset, and the constant part cannot be known at compile time when the object is in a shared library. Position-independent code handles this by loading the address from a global offset table or by using a PC-relative displacement with a relocation the linker fills in. A selector that folds an absolute address into a displacement has to know whether the target’s relocation model permits it, which is a decision made outside the selector and communicated to it as a flag.

When the Fold Changes Behaviour

Folding an address computation into a load moves the arithmetic to the point of the memory access. That movement is observable in two situations.

The first is faulting. A load whose address is invalid traps, and the trap reports the faulting address. If the address computation was previously a separate instruction, a debugger or a signal handler observing the state at the trap sees a register holding the computed address. After the fold, no such register exists; the handler must reconstruct the address from the base, index, and displacement encoded in the faulting instruction, which is the same reconstruction a debugger performs for a variable the compiler never gave a location. This is a small but real cost of the optimization, and it is the reason debug information that describes combined address expressions matters more on targets with rich addressing modes.

The second is ordering with respect to other memory operations. An address computation that is a separate instruction touches no memory, so the scheduler can hoist it above stores and start it early, keeping the address ready before the load issues. Once the arithmetic is part of the load, it can no longer be separated from the access: the load still may not move above a store that may alias it, so the distance the scheduler can create between the address computation and the data’s arrival shrinks. The fold therefore removes scheduling freedom. On an in-order machine, where the address has to be ready before the load issues, this matters, and it is one of the cases where a selector’s local cost model gives the wrong answer.

A third case is the volatile access. A load from a volatile object must occur exactly where the source says it does, and folding an address computation into it is fine, but folding the load itself into a larger pattern that includes a subsequent arithmetic operation is not, because the combined instruction might be reordered or eliminated. Volatile semantics constrain the selector in the same way they constrain every later pass, and the usual implementation is a flag on the load that blocks all but the address fold.

Strength Reduction and the Address Mode

The relationship between addressing modes and induction-variable optimization runs in both directions. A machine with scaled indexing makes the naive array subscript cheap, so strength reduction to pointer increments buys little and may even hurt by keeping a second induction variable live. A machine without scaled indexing makes the multiply expensive, so strength reduction is essential, and the resulting pointer increment folds into the addressing mode as a displacement of zero with a post-increment update.

This is why induction-variable rewriting is target-aware in industrial compilers rather than a canonical transformation applied everywhere, and why the peephole rules that recover a missed fold, described in Peephole Optimization and the Sliding Window, are mostly about recognizing an address computation that selection failed to absorb. The pass needs to know whether the target has a scaled index, whether it has writeback forms, and how large a displacement the encoding allows. A displacement that exceeds the immediate field forces the selector to materialize the offset in a register, which converts a free fold into an extra instruction plus a live value.

Large frames expose the same limit from the other end. A stack access at an offset beyond the immediate range needs the offset in a register or a separate add. Compilers handle this by keeping a frame pointer when frames can be large, so that the displacement from the frame pointer stays small, or by using a scratch register for the large offset. The choice is made once per function, and it interacts with the register allocator because the frame pointer consumes a register that would otherwise be available.

Measuring the Result

The fold’s benefit is easy to state in instruction counts. An array access with a scaled index goes from three instructions to one on a target with the mode, and an access to a structure field goes from two to one. On a target with a 12-bit scaled offset, an access beyond the range stays at two or three, so the benefit is uneven across a large array and depends on how the loop was strength-reduced.

The cost is in encoding size and in the loss of scheduling freedom described above. Complex addressing modes also have microarchitectural costs that the instruction count does not show: on some implementations an access using base plus index plus displacement takes longer in the address-generation stage than a simple base-plus-displacement access. None of this is visible to a selector working from a table of pattern costs.