Module fold 

Folding an address computation into the memory operand of whatever reads it.

Design: spec/10-backend.md section 10.9, and spec/optimizer/37-machine-level-optimization.md section 37.4.

The selector matches one instruction at a time and offers it its operands’ operands, which is two levels of term and is exactly what an address needs to become a lea: a + i * 4 is an add at the root with a multiply under it. Put that same address under a load and everything moves down a level, the multiply is at level two, and no plan the selector has reaches it. So an array read comes out of selection as two instructions, the lea that works the address out and the mov that reads through it, and the second one’s addressing mode holds nothing but a base.

Which is a pair a peephole can see. When the register a lea writes is read by exactly one instruction, and that instruction reads it as the base of its memory operand, the two addresses compose: the reader’s displacement is a constant added to an address the lea already worked out, so adding the two displacements together gives the address the reader wanted in the mode the lea was using. The lea then has no reader at all and goes.

What it will not do

Two indexes. The reader having an index of its own means the composed address wants two scaled registers and this machine, like every machine, has one. Nothing looks for a way to put them together because there is not one.

A displacement that does not fit. The two are added as i64 and the answer has to be an i32, which is what the field holds. It is not a case that comes up in a program anybody wrote, and the check is there because the alternative to checking is wrapping.

A reader in another block. Folding moves the work from where the lea is to where the reader is, and across a block boundary that can mean moving it into a loop. The same rule and the same reason as crate::lower::Lowering::foldable, which is the selector’s version of this question.

A register that something writes in between. Machine IR is in SSA form until the allocator has run, so a virtual register cannot be, but a physical one can: the frame pointer and the stack pointer are already physical here, and a call in between writes every register it is allowed to. Rather than ask which registers are the exceptions, the walk below drops a candidate the moment anything writes a register its address reads.

An address whose displacement is not settled. A local’s place in the frame and an argument’s place in the caller’s is a distance from the stack pointer, and there is no frame until the allocator has finished, so crate::lower leaves those instructions with a zero in the displacement and crate::finish writes the number in later against a list of which instruction is which. Folding one of them away would leave that number being written into an instruction nothing runs, and the fold itself would have composed a displacement that was not there yet. So the caller says which instructions those are and this leaves them alone. What it costs is the fold on a local whose address is taken, which is worth having and is not worth having at the price of finish and this pass sharing a secret.

Where it runs

After selection and before the allocator, which is the one window where both instructions exist and the registers are still virtual. Running it after allocation would work on the arithmetic and would be reading a register file where the reader’s base may have been reused for something else in between.

Functions

addresses

Folds every address computation that one memory operand reads, and gives back how many.