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 an instruction reads the register a lea wrote 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 question is asked of the readers together rather than one at a time, which is what section 37.4 says the pass is really for. One address read at several offsets is what a structure written field by field comes out as, and what a loop the unroller took apart comes out as, and in neither of those does any one reader own the address. If every reader can take it then nothing reads the lea any more and it goes, and the arithmetic moved into addressing modes that were doing an addition anyway. If one reader cannot, folding into the rest buys nothing: the lea stays where it is for the one that refused, the address is worked out twice rather than once, and the registers it reads are now live across every reader as well. So it is all of them or none of them, and that is a property of the set rather than of a pair.

What it will not do

A set with a reader in it that cannot take the address. Each of the refusals below is one reader’s, and any one of them turns down the whole set it belongs to.

An address relative to a symbol, with more than one reader. A reader that reads through a register has room in it for a register and a displacement, and an address made of registers and a displacement goes into that room whoever takes it. A symbol does not: the reader has to name the symbol, which is a whole address word rather than a register number, so each reader that takes one grows by the difference and several readers pay it several times while the lea is saved once. Taking those as well loses 2643 bytes over the corpus at -O2 and gains 386, and the loss is almost all soft float and bit counting expansions, which read one global thirty or forty times each. One reader keeps the old answer, since there the address word is written once either way and what goes is the whole lea.

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 between the address and the last of its readers. 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. The last reader rather than the first is what makes this the set’s question too, since a write after the first reader and before the second is a write the one at a time version would never have seen.

The addresses into the frame

A local’s place in the frame and an argument’s place in the caller’s area 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.

This used to refuse them for that reason, and refusing was expensive: it is the shape of every access to a local that has to go through its address, and of every argument that arrives in the caller’s area. What it takes to fold one is that the entry moves. The instruction the list names goes away and the ones that took the address arrive, so Pending rewrites the list as the fold is applied, and finish adds the frame’s offset to the displacement rather than assigning it, because the reader brought a displacement of its own and the field it is reading is some way past where the object starts. tamnd/rucc#784.

What they do not get is the whole of the set rule above. An address into the frame is off the stack pointer and a memory operand based on the stack pointer needs an index byte on this machine whether or not anything is indexed, so a reader that takes one grows by more than a reader that takes an address in an ordinary register does. Past three of them the bytes the readers put on are more than the whole lea was, which is the same arithmetic as the symbol above and comes out at a different number. FRAME_READERS below has the measurement.

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.

Structs

Pending

The addresses crate::finish has still to write a displacement into.

Functions

addresses

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