Expand description
Takes out a loop that runs a known number of times, working out what it left behind.
Design: spec/optimizer/17-dce.md for what makes a thing removable and
spec/optimizer/28-induction-variables.md for where the trip count comes from. 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 trip count that is a number rather than an estimate. The count 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. crate::scev::Bound::under_undefined_overflow is the same
accessor crate::unroll reads for the same reason, and 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.
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.
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.