Module compare 

Taking out a comparison the machine has already made.

Design: spec/optimizer/37-machine-level-optimization.md section 37.4.

A comparison produces no value. It sets a few bits nobody named and the instruction behind it reads them, so a comparison that sets the bits that are already there is one nothing could tell had run. There are two ways for that to happen, and both of them are about an instruction a little way in front rather than about a dataflow the whole function takes part in.

The same comparison twice. if (x == y) ... else if (x != y) and every expression that asks a question and then asks its negation come out as two comparisons of the same two registers with nothing between them but the bytes each one kept. The second asks what the first asked and the answer has not moved.

A comparison against zero of something arithmetic has just worked out. if (a & MASK) is an and and then a comparison of its result against zero, and the and set the bits that comparison would have set on its way past. This is the common one by a long way: at -O2 over the SQLite amalgamation there are 2250 of these and 0 of the other shape.

Why it runs after the layout rather than before

Because this is the second pass to work on a pair of instructions whose middle has to stay empty, and the first is the block layout. A branch on a comparison is written there as the comparison with its byte taken off and a jump that reads the condition state, and what is between those two is live and is not a register, so anything that ran afterwards and put an instruction between them would be wrong. Running last is the whole of what makes this safe, which is the sentence section 37.4 uses about the layout itself.

It also makes the two shapes one shape. A comparison the layout folded a branch into is a comparison that keeps nothing, one whose byte something else wanted is a comparison that keeps a byte, and after the layout both are sitting in a block to be looked at the same way. Before the layout the first kind does not exist yet, so a pass that ran earlier would have to either leave every branch alone or undo the fusion to get at one.

What a block boundary is

The end of everything this knows. The state a comparison leaves is not a register and nothing in this back end carries one from a block to its successors: the layout writes the jump that reads a comparison into the same block as the comparison, which is the only place one is read at all. So the walk starts each block knowing nothing, which is what makes it a walk rather than a dataflow.

What it will not do

A comparison with anything between it and the instruction that already made it that writes the condition state. The target says which instructions those are and says it about every name it does not recognise, so an opcode added to a rule set and not to that description makes this find less rather than making it wrong.

A comparison of a register something wrote in between. The bits are still the bits the earlier instruction left, but they are about what the register held then and the comparison is about what it holds now. Every definition between the two is checked against the registers the earlier one was about, which are physical by the time this runs and so are the ones the machine will really read.

A comparison against zero after arithmetic whose condition reads a part of the condition state the arithmetic did not leave the way a comparison would have. subl says whether its answer was zero and a comparison of that answer against zero would agree, and it says whether the subtraction overflowed where the comparison would have said it did not, so a signed < after one reads a sign and an overflow that no longer belong together. rucc_target::Zeroing is where each instruction says which conditions it is good for, and every condition that ends up reading what the arithmetic left has to be one of them, including the ones behind the comparison rather than on it.

A comparison against zero after arithmetic that wrote a different number of bits. andl leaves a statement about thirty two bits and cmpq $0 asks about sixty four, and on this machine the upper half is then zero and the two disagree about the sign.

A comparison against zero after arithmetic whose condition state nothing is found to read. That is a comparison that is dead rather than redundant, and taking a dead one out is a different question: it needs no earlier instruction at all, so answering it here would mean answering it only where an earlier instruction happened to be.

Functions

redundant

Takes out every comparison whose condition state the instruction in front of it already left.