Module copies 

Taking out a move the allocator wrote that puts a value where the machine has it already.

Design: spec/optimizer/37-machine-level-optimization.md sections 37.4 and 37.6, the group of passes that run after allocation and clean up what the allocator could not.

The allocator decides one value at a time. It writes a value out when the range it was given a register for ends, it reads a value back in front of the instruction that wants it, and neither decision looks at the other. So a value written by one instruction and wanted by the next comes out as a store and then the load of the same slot on the very next line:

  movq %r10, 16(%rsp)
  movq 16(%rsp), %r10

The load reads a word the store has just written, into the register the store read it out of, so the register already holds what the load would put in it. It is a memory access that cannot change anything, on the two instructions of the pair that are the expensive one.

The same thing happens with instructions in between. A value spilled once and read back at three places in a block is three loads of one slot into one scratch register, and the second and the third are reads of a word that register still holds. A value read back and then written out again unchanged is a store of a word the slot still holds. A copy into a register that already holds what it is being given is a copy of nothing. All of them are the same mistake seen from different sides, which is why they are one pass rather than four: a move is dead when what it writes to and what it reads from hold the same value already.

The near miss of the same thing is a load of a slot into a register while a different register holds that word. Nothing can be removed there, since the word does have to arrive in the register the load names, but it can come out of the register that has it rather than out of the frame. That is the second thing this does and the rest of the same knowledge answers it.

Why it is not a rule over the instructions

A store followed by a load of the same address is not on its own a dead load. The same pair of instructions is what a write to a local variable and a read of it back look like, and when that variable is volatile the read is one the program insisted on and the standard says happens. Machine IR does not carry that word, and by the time the pass runs it could not: a volatile access and an ordinary one are the same instruction with the same operands.

So this does not look for the pattern. crate::finish records which instruction each of the allocator’s moves became, and this pass only ever takes out one of those. A spill slot belongs to the allocator, nothing else reads it or writes it, and no part of the program said anything about it, which is what makes removing a read of one safe when removing a read of a variable is not.

A slot can end up sharing its bytes with a local, which crate::slots arranges, and that does not change the argument. Two things share a run of the frame only where they are never both wanted, and a slot between a spill and the read back of it is wanted the whole way, so a store to the local it shares with cannot fall in that stretch.

Why after the whole allocator rather than inside it

The edits are decided in different places for different reasons, so no one of the decisions is wrong on its own and there is no place inside the allocator that sees them together. What ends up between two of them is settled by crate::finish writing every edit into the function, which is after the allocator has finished. They are all visible at once here and nowhere earlier.

What a block is walked with

One map from a place to a number standing for a value, where a place is a register of a class or a slot of one. Two places with the same number hold the same bits, and that is the whole of what the pass knows: nothing here has to know what the value is, only that a move of one place into another with the same number would write what is there.

The map starts empty at the top of every block, because what a register holds on the way in is whatever the block before it left, and which block that is depends on the path. A map carried across edges would be worth something on a straight line of blocks and is a dataflow problem rather than a walk, which is section 37.4’s own answer for why this is the cheap half.

What clears it

A write to a place clears what was there, which is every definition in an operand vector and the destination of every move.

A call clears everything. The registers a convention does not preserve are gone across one, and the ones the arguments travelled in are written down as reads rather than as writes, so the operand vector of a call does not say what it destroys. That is why the machine description is asked which instructions are calls rather than the operands being trusted.

An instruction the description does not name clears everything too, on the same reasoning backwards: what a pass cannot look up it cannot claim to have read.

An instruction that writes the stack pointer or the frame pointer clears everything, because a slot is named by an offset from one of those and a slot at a new address is not the slot the value was written to. A prologue and an epilogue do this, which costs nothing since neither is in the middle of anything, and so does the instruction that takes room for an array whose size is not known until it runs.

When a load becomes a copy

A slot read into a register while no register holds that word is a load and has to stay one. A slot read into one register while another register holds the same word is a load a copy would do instead, and a copy is the cheaper of the two on every machine here: it is fewer bytes, it does not go near the memory unit, and on a machine that renames its registers it often costs nothing to run at all.

Which instruction that copy is is the target’s answer and not this pass’s, and it is the same answer crate::finish read to write the load. A class of registers is moved between two registers by one named instruction and between a register and the frame by two others, and the three are named together for that class, so asking for the one is asking the description that produced the other.

Being named together is also what makes the widths agree. Every entry in the map was put there by one of the allocator’s own moves and every one of those moves a whole register of its class, so two places holding one value hold it in all of their bytes rather than in a low part that a wider copy would read past.

Where several registers hold the word, the lowest numbered of them is the one written. Any of them would be correct, and the map is a hash map, so writing whichever came out of it first would make the assembly depend on where the addresses happened to land. A compiler whose output moves between two runs of one input is one nobody can compare anything against, which is a worse thing to be than one that picks the second best register.

Why it does not go through the change framework

Because the one question crate::changes would answer about a removal is one that cannot be answered here. The framework refuses to take an instruction out while anything still reads a register it wrote, and it knows that from a count of the reads in the function, which is the whole answer while every register is written once and is not the answer at all afterwards: the register a reload writes is physical by the time this runs, the same one is written and read all over the function about other values, and the count says so. Every removal here would be turned down.

What makes these safe is not a count but where the instruction came from. It is one of the allocator’s own moves, crate::finish wrote it, and the value is in the register already because an earlier move of the allocator’s put it there. That is a reason the framework has no way to be told, and section 37.2’s framework is about the machine’s description of itself rather than about the allocator’s, so this keeps its own.

The framework’s own question, whether the target has an instruction of the shape a pass proposes, is one the rewrite does not have to ask either. The copy it writes is the instruction the description names for moving a register of that class, so it is an instruction the target has by where the name came from rather than by a lookup afterwards.

What it does not do

Nothing is propagated. A read of a register that another register is known to equal stays a read of the register it names. The two things this does are both to one of the allocator’s own moves and to nothing else, for the reason the rest of this is built on: what makes an edit here safe is that the allocator wrote the instruction and owns the slot, and an instruction a lowering rule wrote is neither.

Nothing crosses a block, on either half.

Structs

Cleaned

What one function came to.

Functions

clean

Takes out every move of the allocator’s that puts a value where it is already, and reads the rest out of a register wherever one has the word the frame does.