Expand description
Takes out a loop that comes back, working out what it left behind.
Design: spec/optimizer/17-dce.md for what makes a thing removable and section 28.9 for the
closed form, the off by one in it, and why the two questions this pass asks want different
things from the trip count. This is tamnd/rucc#1631.
crate::dce cannot do this and the reason is worth stating, because it looks at first like a
gap in that pass. An empty counted loop has a counter, an add, a compare and a branch, and
every one of them is used: the add feeds the compare, the compare feeds the branch, and the
branch feeds the block parameter the add reads. Nothing in it has a use count of zero, so a
pass driven by use counts correctly leaves all of it alone. The question that gets the loop out
is not asked of an instruction, it is asked of the loop: does anything outside read what it
computes, does it do anything to memory, and does it come back. Three yeses and the loop is a
way of spending time.
§Which loops
A preheader, one exit, and a bound rather than an estimate. The bound is what says the loop terminates, which is the third question and the one a person is most likely to forget: a loop that computes nothing and never comes back still cannot be taken out, because not coming back is what it does. Section 7.5’s distinction between a bound and an estimate is exactly this: an estimate decides whether a transformation pays and a bound decides what the program does.
The bound is read through crate::scev::Bound::comes_back rather than through the accessor
crate::unroll uses, and the difference is worth a sentence. Unrolling multiplies by the
count, so it needs the count to be the right number. Deleting only needs there to be a last
iteration, and for (i = 0; i < n; i++) has one whatever n turns out to be, so a count
worked out from a value the loop does not change is as good as a number here. It stops being
as good the moment anything reads what the loop left behind, which is why the two questions
are asked in that order and with different accessors.
Every instruction inside has to be one whose not happening nothing can tell. That is the
predicate crate::dce already has, so it is read from there rather than written again, and
it means a plain load may be inside the loop and a volatile one may not. A call is allowed
when the purity analysis says it reads memory at most and comes back, which is the same rule
that lets a call whose result nothing reads go.
§What the loop leaves behind
A loop whose total somebody reads afterwards is a loop that hands something over, and most
loops worth writing are that kind. Sometimes what it hands over can be worked out without
running it. A value that goes up by the same amount every time round is {base, +, step} in
crate::scev’s terms, the loop is left on the iteration the exit test first fails, and that
iteration’s number is the count, so what the loop leaves behind is base + step * count. The
preheader works that out in one go and hands it over instead, and then nothing outside reads
anything the loop computed and the loop goes.
Handing it over is two different edits, because a value defined in the loop reaches the code
after it by two different roads. It may be an argument on the edge out, landing in a parameter
of the block the loop leaves to, which is the shape crate::canon puts things in. Or the
block after the loop may simply name it, which is legal wherever the definition dominates the
use and is what is actually there by the time this runs, since the block loop closed form put in
the way is one crate::simplify_cfg has every reason to fold away again. So both are looked
for, and a use of the second kind is rewritten where it stands.
No overflow argument is needed for this and it is worth saying why, because the neighbouring
transformation in section 28.4 does need one. A value that steps by a fixed amount evolves in
its own type, which is to say modulo two to the width, and addition modulo two to the width is
associative, so adding step to base count times and working out base + step * count the
same way are the same number whatever either of them does to the top bit. Section 28.4’s rewrite
is a different claim, that one comparison holds exactly where another does, and that one does
turn on whether the limit overflows. So the arithmetic written here carries neither nsw nor
nuw, and the promise the loop’s own increment carried is not copied onto it, because that
promise is about the sequence and says nothing about this.
What is written down is the whole expression rather than three instructions to be folded later,
because this pass is the last one in the pipeline and there is no later. base and step are
both crate::scev::Invariant, which is value * scale + offset with the arithmetic on it
already, so base + step * count is worked out in that form first and only what is left of it
reaches the function. A loop adding one a million times leaves a constant behind and a loop
adding an invariant n a million times leaves one multiply.
A count that is an expression rather than a number is written as base + step * max(count, 0),
and the two things bolted onto it there are two assumptions paid for rather than believed. The
clamp is crate::scev::Assumption::Entered. A count that comes out negative is a loop whose
test failed the first time it ran, which is a loop that took its back edge no times and handed
over what one pass through its body left, and zero is the count that says exactly that. The
widening is the reading the exit test took, a sign extension for a signed test and a zero
extension for an unsigned one. Section 7.7 is the warning about getting that one wrong: a limit
past the middle of a thirty two bit type is a large number to an unsigned test and a negative
one to a signed test, so sign extending what an unsigned test compared would clamp to zero and
turn a loop over three billion elements into one that ran no times.
The clamp is done in sixty four bits and the arithmetic in the value’s own type, and the cut between the two is exact rather than close enough. Multiplying modulo two to the width and then cutting to a narrower width is the same number as cutting first and then multiplying, so a count worked out wide and truncated is the count. Widening it instead is a zero extension, because the clamp has already made it a number that is not negative.
It is only done when it lets the loop go, which is a cost rule rather than a correctness one.
Writing the final value down where the loop stays behind costs a multiply in the preheader and
saves nothing, because the loop still carries the value round its own back edge and nothing in
rucc yet takes out a block parameter whose only reader is the argument it passes to itself.
crate::dce’s own notes call that out as a transformation worth having and a different one
from what it does. When there is one, this gate is the thing to reconsider.
§What it does
Works out in the preheader whatever the loop was going to leave behind, puts those values where
the loop’s own were read, points the preheader at the block the loop left to with whatever the
edge out was already carrying from outside, and lets the sweep in crate::simplify_cfg take
the blocks nothing reaches. Every value named in any of it is asserted to dominate the preheader
rather than assumed to: a value defined outside the loop that reaches the exit test has to
dominate the preheader, and an assertion is cheaper than being wrong about why.
Structs§
- Loop
Delete - Section 17’s dead code elimination, asked about a loop rather than about an instruction.