Expand description
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 three rewrites written out by hand below them.
§The rules
Four tiers of spec/optimizer/13-rewrite-rules.md section 13.4 so far.
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 four is the width rules, the algebra of truncation and extension. Truncating an extension
back to the width it came from is the value that was there before either of them, and an
extension of an extension is one extension. This is the tier
the specification says pays on real C, and the reason is C rather than anything about this
compiler: the integer promotions widen nearly every operand of nearly every expression, and
most of those widenings compute something the instruction after them throws away. The widest
of those promotions starts at one bit, because a comparison answers in one and everything done
with the answer is done at the width of an int or wider, so the tier is written over that
source as well as over the four a machine computes in.
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 rather than third, because rearranging a term is only worth doing when no rule that improves it fires.
Every rule in all four 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. Tier four is matched with the operand expanded into the instruction that computed it, which is what a rule about two instructions at once needs and what none of the others wants.
What a rule leaves behind is one of four 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. A conversion is
that same rewrite in place with one operand instead of two, and it is its own case because a
conversion is the one instruction whose operand is not the width of its result.
§The three written by hand
All three are about comparisons, and all three are here rather than in rules/ for the same
reason: what each one is, is one statement quantified over the predicates, and the rule language
has no way to say that, so writing any of them as rules would mean writing out every predicate,
every operand order and every width by hand and keeping the enumeration in step with the two
predicate sets forever.
§A negation of a comparison
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.
§Two comparisons over one pair of operands
An and or an or of two comparisons about the same two values is one comparison, or it is a
constant. (x == y) && (x != y) is false whatever x and y are, (x >= y) || (x < y) is
true, and (x < y) || (x == y) is x <= y, which is one instruction where there were three.
The way to see all of that at once is to stop reading a predicate as a question and read it as
the set of answers it accepts. Two values are below, equal to or above one another, and two
floating point values can also be neither, so there are four cases, exactly one of them holds,
and a predicate is the subset it says yes to. && is then the intersection of two subsets and
|| is the union, an empty result is false, a full one is true, and anything else is whichever
predicate spells that subset. That is the whole rewrite, and the reason it is a paragraph
rather than a table is that the sixteen floating point predicates are the sixteen subsets of
the four cases, so the map back from a subset is total and has nothing to special case.
Integers have three cases rather than four, and a complication the floating point side does not
have: < is two different questions depending on whether the operands are read signed or
unsigned, and a subset built out of one of each would be a subset about no reading in
particular. So each integer predicate carries which reading it wants, two that disagree refuse
to combine, and == and != want neither and go with whatever the other one wanted.
Nesting falls out of rewriting in place. A three way condition arrives as an or of an or and
a comparison, the walk reaches the inner one first and leaves a single comparison where it was,
and by the time the outer one is looked at it has a pair of comparisons under it rather than an
or and a comparison. That is what gcc.c-torture/execute/ieee/compare-fp-3.c needs and it
costs nothing to get.
§A comparison one operand’s sign bit settles
fabs (x) < 0.0 is false whatever x holds. That is gcc.c-torture/execute/20020720-1.c, and
it asserts it the way the two above do, by calling a function it never defines.
The same buckets answer it. A magnitude is a positive zero, a positive number, a positive
infinity or a NaN, so a pair made of one and a constant that is not positive is never in the
bucket where the magnitude is below, and against a negative constant it is never in the one
where the two are equal either. Narrow the predicate’s set by the buckets the pair can be in and
read the answer back: nothing left is false, and anything left is a shorter question than the
one that was asked. fabs (x) <= 0.0 comes out as fabs (x) == 0.0 that way, which is not a
constant and is still worth having.
What it does not come out as is true. The narrowing only ever takes buckets away and always
takes at least one, so fabs (x) >= 0.0 is left exactly as it was written, which is the right
answer rather than a missed one: a NaN has its sign bit cleared like anything else and is not
above, below or equal to anything at all.
fabs is not a call by the time this runs. The front end knows the plain library name as well
as the prefixed one and lowers both to the bits, because the magnitude of a value is that value
with its sign bit cleared and there is nothing to call. So what the pattern looks for is a
bitcast of an and against a mask whose top bit is clear, which is what that lowering leaves.
§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.
The composite rewrite leaves two of them rather than one, and in the case that comes out constant it leaves both comparisons and computes nothing at all. The sign rewrite leaves the four instructions the magnitude was built out of. Same litter, same reason, same pass takes it out.
Structs§
- Simplify
- The pass. It holds nothing, because a peephole needs to know nothing beyond the pattern.