Module shorten 

Writing the same answer in fewer bytes, once the registers are the real ones.

Design: spec/optimizer/37-machine-level-optimization.md section 37.4, which calls these the size directed peepholes and puts them after register allocation. tamnd/rucc#741 is the issue about the back end never learning what it is compiling for, and names three of these as free before any of that is settled and one as waiting for it.

Five rewrites. A move of zero into a register becomes an exclusive or of the register with itself: movl $0, %eax spells the zero out in four bytes of zero bits and is five bytes, xorl %eax, %eax says it without spelling it and is two. The processor knows the idiom, so the shorter one is no slower, and this is not a trade of speed for size and does not wait for a size goal to arrive.

And a move of a number into a sixty-four bit register becomes the thirty-two bit move where the number is one that fits, because the narrow instruction clears the half of the register it does not write rather than leaving it alone. movq $7, %rax is seven bytes and movl $7, %eax is five, and for a number above two to the thirty-first it is ten against five, since the wide move cannot reach one by sign extending and writes all eight bytes of it out.

The two meet on a zero, and the order they are asked in is the order they are worth: a zero whose condition state is free becomes the exclusive or, and a zero whose state is not becomes the narrow move, which is two bytes off rather than five but costs nothing to say.

And a comparison of a register against zero becomes a test of the register against itself. cmpl $0, %eax is three bytes and testl %eax, %eax is two, the byte being the zero the first one writes out. That one is asked of every instruction whatever the walk has seen, because the test writes the condition state exactly as the comparison does: both leave the sign, the zero and the parity of what is in the register and both clear the carry and the overflow, so every condition this machine jumps on reads the same answer behind either of them.

And an addition of one to a register becomes the instruction that adds one and says so in its opcode. addl $1, %eax is three bytes, one for the opcode, one saying which register and one for the number, and incl %eax is two. A subtraction of one becomes the instruction that takes one away, and each of the two is also what the other one written against minus one becomes.

And an address computation whose address is a register becomes a move of that register. leaq (%rsp), %rax works out an address that is a base and nothing else, which is what is already in the base, and movq %rsp, %rax puts the same number in the same place in three bytes rather than four. The byte is the one an address counted from the stack pointer has to spend saying it has no index, and the stack pointer is the register this turns up on, because what makes it is taking the address of whichever local sits at the bottom of the frame.

That fifth one is the only one here worth taking for something other than bytes. A move between registers is a thing the machine can do by renaming, so it is off the critical path, and an address computation is an addition however small the numbers in it are. gcc writes no address computation of that shape anywhere in the SQLite amalgamation and rucc wrote 444 of them.

That fourth one is the only one here that is not free, and it is the only one that reads the goal. An addition writes the carry and an increment leaves the carry as it found it, so the machine has to merge what was left with what the next instruction writes, which costs a little where the code is hot and is worth a byte where the goal is size. gcc writes the addition at -O2 and the increment at -Os, and so does this. The goal arriving here at all is the first half of tamnd/rucc#741: before it, -Os was a shorter list of middle end passes and the back end compiled what came out of it exactly as -O2 would have.

The numbers over the corpus at -Os before this pass existed: rucc wrote a move of zero into a register 21,304 times and GCC 16 wrote it 9 times, and GCC wrote the exclusive or 23,729 times against rucc’s 965. So this is not a case the selector catches most of and misses at the edges. It is one it does not do. Afterwards rucc writes the move 1,232 times and the exclusive or 21,037, and the two moved by the same number, which is what says every one that went became one of these and none of them came from anywhere else.

Why it is not something the encoder does

Because the two are not the same instruction. The exclusive or writes the condition state and the move does not, so an encoder that quietly swapped one for the other would change what the instruction behind it reads. Whether anything reads it is a question about the instructions that follow rather than about this one, which is what makes this a pass. rucc_target::FlagInsts is where the answer comes from, the same description crate::compare asks, and it answers that a name it does not know writes the state, so an opcode added to a rule set and not to that table makes this find less rather than making it wrong.

The narrower move and the test are a different answer to the same question. Those two an encoder could do without asking anything, since the narrower move leaves the same number in the same register and the test leaves the same condition state the comparison left. They are not done there because an encoder handed a sixty-four bit move and writing the bytes of a thirty-two bit one would be writing bytes the listing beside them does not say, and the listing and the bytes agreeing is worth more than the two bytes. Choosing the instruction is this pass and spelling the one it chose is the encoder.

Why it runs last

After crate::compare, because that pass takes comparisons out and a comparison that is gone is one whose write of the condition state is gone with it. Running before it would see a state written where the output has none and would refuse rewrites that are allowed. After the layout for the reason compare is: the layout writes the jump that reads a comparison into the same block as the comparison, and this is the other pass that has to see that pair whole.

Nothing here moves an instruction, removes one or changes a block, so running after the freeze costs nothing. The rewrite is one instruction becoming one instruction in the same place.

What a block boundary is

The end of everything this knows, which is the same sentence crate::compare uses and the same reason: the condition state is not a register, nothing in this back end carries one from a block to its successors, and the only place a comparison is read is the block it was made in.

That is an invariant of the passes in front rather than of this one, so it is checked instead of believed. carried walks every block and asks whether any of them reads the condition state before writing it, which is what a block reading a predecessor’s state would look like from here, and one that does turns the whole function down. What it buys is that if some later pass starts writing that shape, this pass stops rather than starts being wrong.

Reads it rather than mentions it. A comparison that keeps a byte makes the comparison and reads the answer in the one instruction, so a block opening with one is not a block reading anything a predecessor left, and the description is asked which of the two kinds of read it is rather than being taken at the word. tamnd/rucc#1432 is what that cost before it was asked: 456 functions in the SQLite amalgamation were turned down and every one of them was turned down by this, which is most of the functions in it that have anything for this pass to do.

Down for the exclusive or and the increment. The narrower move reads no condition state and writes none, the test writes the same state the comparison it replaces wrote, and neither an address computation nor a move touches any state at all, so where a state is alive is not a question those three have to ask, and a function this turns down still gets all of them.

What the walk carries for the increment is a second answer beside the first, which is whether anything behind reads the carry rather than whether anything behind reads the state. The two are not the same question and neither implies the other: a jump on whether a value was zero reads the state and not the carry, and an increment already in the code writes the state and not the carry and so ends the life of neither. That last case is the reason the walk and the check above both ask the target which instructions leave the carry alone rather than stopping at the flag saying the state was written.

A template a program wrote

An asm statement is not opaque to this. rucc_target::x86_64::read turns the text of a template into the opcodes this back end already has, so by the time this runs a template is ordinary instructions carrying ordinary names, and the ones in it that read the condition state are seen the same way any other instruction’s read is. A move of zero in front of a template is rewritten when nothing in that template reads a state it did not write itself, which is the same rule as everywhere else and not a rule about templates.

Nothing weaker is being assumed there than what a program could already rely on. On this machine GCC has every asm clobber the condition state whether the statement said so or not, so a template reading one set before it was never something to hold on to.

What it will not do

Turn a move into the exclusive or when anything reads its condition state before anything writes. That is the rule and what it costs is now a small number: the zero going into a register right before a comparison of something else stays a move, and the most the other rewrite can do for it is make it a narrower one. Of the 215 moves of zero left over the corpus at -Os, 146 are this and the other 69 are the eight bit rule below. Not one of them is sixty-four bits wide.

It was 1,232 until the whole function check stopped counting a comparison that keeps a byte as a state read from in front of it, which is tamnd/rucc#1432 and was most of what this pass was leaving alone rather than anything about the instructions it was looking at.

Eight bits. movb $0, %al and xorb %al, %al are both two bytes, so the exchange buys nothing and would spend the condition state on it. The target’s table is where that is written down.

Write an increment at a level that asked for fast code. That is the goal doing its job rather than a limit, and it is why the same corpus compiled at -O2 and at -Os now differs by something other than which middle end passes ran.

Add or take away anything but one. The machine has an opcode for one and for nothing else, so a constant of two is already as short as it is going to be written.

Turn an address computation into a move when the address is anything more than a register. An index is a multiplication, a constant is an addition and a symbol is an address the assembler fills in, and a move does none of those. That is what most address computations are for, so this last rewrite is about the ones that were not computing anything rather than about address computation in general.

Functions

shorter

Rewrites every instruction that has a shorter spelling nothing would notice.