Module simplify 

Peephole rewrites: a small pattern of instructions becomes a smaller one.

The third pass, and the one that will eventually not exist. Section 9.3 of spec/09-optimizer.md says the value level optimizer is an acyclic e-graph, and that an e-graph replaces what would otherwise be a folding pass, a peephole pass, a GVN pass, a reassociation pass and an instcombine pass, all with a pass ordering problem between them. This is the peephole pass, written now because the e-graph is a milestone away and because there is a rewrite that unblocks twelve lowering rules today.

Every rewrite here has to survive being moved into the rule set later, so each one is stated as a pattern and a replacement in its own function and nothing shares state with anything.

The rewrites

Two kinds. The rules of rules/, one file per tier, which are matched against every instruction and are where anything new goes, and one rewrite written out by hand below them.

The rules

Three tiers of spec/optimizer/13-rewrite-rules.md section 13.4 so far, tried in the order they are numbered.

Tier one is the identities. Adding nothing, multiplying by one, and’ing a value with itself. None of them needs anything known about the operands and each leaves a term strictly smaller than the one it replaced.

Tier two is the strength reductions, which swap an operation for a cheaper one rather than taking one away: multiplying by two is an addition, and multiplying or dividing by minus one is a subtraction from nothing. Tier one is tried first because losing an operation beats swapping one.

Tier three is the canonicalisations, which put the constant of a commutative operation on the right. They make nothing smaller and nothing faster. What they do is halve how many ways a term can be written, so that every rule above them needs one variant where it needs two today, and so that hash consing can see two spellings of one expression as one. They are tried last, because rearranging a term is only worth doing when no rule that improves it fires.

Every rule in all three has been proved against crates/rucc-ir/rules/ir.model by rucc-verify before it may be used.

Which plans a tier is matched under belongs to the tier. Tiers one and two are matched with either operand offered as a number, since a rule about a constant should fire whichever side it was written on. Tier three is matched with the left operand offered as a number and the right one refused if it is one, which is what makes a rule that moves the constant across fire once rather than forever.

What a rule leaves behind is one of three things. (value.iN x) means the result is a value the function already has, so every use of the result is pointed at that value and the instruction is left for crate::dce. (iconst.iN k) means the result is a constant, and the instruction becomes that constant where it stands, which keeps the result value and is why nothing else has to be rewritten for that half. An instruction means this one becomes that one where it stands, which keeps the result value for the same reason, and an operand of it the rule wrote as a number gets an iconst in front of the instruction to hold it.

The one written by hand

An exclusive or of a comparison with an i1 of all ones is that comparison with the opposite predicate. That is issue 379, and it is worth more than the instruction it saves.

C spells eight of the sixteen floating point predicates. The six relational and equality operators give the six ordered ones, != gives une, and __builtin_isunordered gives uno. The other eight are what the negation of one of those means, and the front end writes a negation as an exclusive or rather than as a flipped predicate, so !(x < y) lowers to an fcmp olt and an xor where the machine has an fcmp uge. Twelve rules in the x86-64 rule set are written on those predicates and none of them has ever fired, over the whole torture suite at every optimization level, because no IR that reaches selection contains one.

The integer case comes with it. !(a < b) on integers is the same shape, the same rewrite and the same saving, and leaving it out because the coverage report did not complain about it would be picking the rewrite by what measures it rather than by what it does.

Why it needs dead code elimination after it

The rewrite turns the xor into the comparison and leaves the original comparison where it was, used by nothing when the negation was its only reader. Rewriting in place keeps the result value, so every use of it is already correct and there is nothing to rewrite, and what is left over is exactly what crate::dce takes out. That is why the pipeline runs the two in this order, and it is why the pass before the dead code eliminator was written first.

An identity that produces a value leaves the same kind of litter for the same reason. The instruction it fired on reads what it always read and nothing reads it, so it is dead, and taking it out here would mean deciding whether its operands are still read by anything, which is the question the dead code eliminator answers for the whole function at once.

Structs

Simplify

The pass. It holds nothing, because a peephole needs to know nothing beyond the pattern.