Module split 

Splits a loop into a run of iterations that needs no checks and the rest of it, which keeps them.

Design: spec/safe-memory/07-check-elimination.md section 7.4, which names this and says what it is for: “Loop splitting is the general form. The checked part and the unchecked part are divided at min(n, extent / sizeof(T)).”

crate::hoist is the pass next door and it answers a different question. It puts one check in front of a loop that covers every access the loop makes, which needs the loop to make every one of them: an exact count, one way out, and a check every iteration reaches. Most loops in real code are not like that. The census on tamnd/rucc#782 says that of the roughly fifteen hundred checks SQLite still carries at -O2, six hundred and ninety two are in loops with a second way out and sixty four are checks an iteration can finish without reaching. Neither is a loop hoisting can say anything about, and both are loops this one can, because it never has to claim the loop reaches the end of what it might read. It only has to know a prefix that is safe.

What the two halves are

The loop is copied. The original becomes the fast half and loses its checks, the copy becomes the slow half and keeps them, and a new block in front of the original decides which one runs. That block carries an offset in bytes from the first access, walks it on by the step every time round, and hands over to the slow half once the offset passes a window worked out in the preheader.

The offset is a new value rather than one of the loop’s own pointers, and the test is against the window rather than against anything the loop compares. That is what makes this work on a loop with several ways out: the fast half keeps every exit the loop had, so leaving early still leaves early, and the extra test is only ever the reason the fast half stops early and never the reason it runs longer.

A loop where no address moves gets neither the block nor the offset. Which half runs is settled by an answer that does not change while the loop runs, so the way into the loop is where the two halves are chosen between and there is nothing to carry. Half the loops this takes on SQLite are that shape.

Where the window comes from

For a check whose address is first + delta reading reach bytes each time, every offset with delta + reach <= extent is one the check cannot fail on, where extent is how many bytes from first on belong to whatever owns first. So the window is extent - reach, and where a loop has several checks that walk by the same amount the window is the smallest of theirs.

Bytes rather than iterations, and that is the whole of the arithmetic. An earlier version of this counted iterations against (extent - reach) / step + 1, which is the same transformation and a much harder claim: it has a symbolic multiply and a symbolic divide in it at sixty four bits, and z3 does not finish on it in two and a half minutes in any of three formulations, so the pass sat outside the rule table that spec/safe-memory/07-check-elimination.md section 7.7 asks every elimination to be inside. In bytes it is swept.sym.i64, which is already in that table and already proved, and the pass asks it rather than deciding. limited below is where that happens.

The extent is the half of that a compiler cannot work out, so it is asked at run time, through the cap_extent query that tamnd/rucc#792 added. The query takes a limit on how far to look and the answer is never more than that, which is why this pass still wants a trip count: what it asks for is how many bytes the loop was going to read anyway, so the walk in the runtime is bounded by work the loop is already doing. A count that is too small costs iterations in the slow half and a count that is too large costs a slightly longer walk, and neither is a wrong answer, which is why the count is read from any exit that offers one rather than from an exit that runs every time.

An address that does not move is the same expression with a step of zero, and its offset is zero on every iteration, so there is nothing to carry and the window question collapses into whether the one access fits. How far the runtime is asked to look is then just the bytes the access reads. Hoisting would rather have these, and it takes the ones in loops it is willing to touch. What is left over is the ones in loops it refused for one of its own reasons, a second way out or a call inside, and those come back here.

A walk that goes the other way

A loop whose address goes down each time round is the same transformation looked at from the other end, and it is written here so that it is the same code. The offset the guard carries counts bytes moved from the first access rather than bytes added to it, so it still goes up by the step every time round and everything built on it is untouched: the guard block, the block parameter, the clamp and the test are the ones above, word for word.

What changes is which end of the object the runtime is asked about. The window has to be room below the first access rather than above it, so the query is cap_extent_back and it is asked at first + reach, the end of the first access rather than its start. The answer is how many bytes ending there belong to whatever owns them, the window is that less the reach as before, and the access on iteration delta is the reach bytes ending at first + reach - delta. That is what swept.down.sym.i64 in the rule table is written about, and it is asked instead of the ascending rule rather than derived from it.

Anchoring at the end is what buys all of that. Anchoring at the lowest address the loop reaches would need a real trip count, since where the verified range starts would then depend on how far the loop goes, and this pass takes loops nobody counted and gives them a guess of ten. A guess is free for an ascending walk, where asking for too little only costs iterations in the slow half. It is unsound for a descending one, so the query goes the other way instead of the anchor.

A walk nobody could follow

Everything above assumes the pass knows how far the address moves each time round. Most of what is left on real code is loops where it does not, and they are not exotic: a scanner that steps by one or by two depending on what it just read, a pointer that comes back round through a join because the body has a branch in it, a walk whose step is a width the caller passed in. None of those is an induction variable and scalar evolution has nothing to say about any of them, so they arrive here as an address that does something unknown.

The way through is to stop asking how far the address moves and ask instead where it is. If the check’s address is a fixed distance from a pointer the loop’s header carries, then the guard can take where that pointer was on the way in from where it is now, and the difference is the displacement itself. It is exact rather than an upper bound on it, so the same window and the same rule apply word for word, and the guard tests it with the same unsigned comparison. It costs a subtract in the guard and saves the block parameter and the add at the latch, so it is not more code than counting.

What has to be established is that the pointer is its own former self plus bytes. p = p->next is the case this is not allowed to take: the difference between two nodes of a list is a number, but it is not a displacement inside one object and the extent the preheader asked about says nothing about it. So the value the latch hands back has to reach the parameter through ptr_adds, block parameters inside the loop and select, and a load anywhere on the way is a refusal. measured is where that walk is, and it is syntactic because what it has to establish is.

The trip count is the one thing a measured walk is worse at. How far the runtime is asked to look is a count times a step and there is no step, so the largest constant step seen on the way round stands in for it, and a walk with no constant step anywhere falls back on the bytes one access reads. Asking for too little costs iterations in the slow half and never an answer, which is the same trade the trip count guess is already making.

Why the fast half may drop a check

check_bounds asks whether the bytes an access names lie inside one object. Every address in [first, first + extent) is inside the object that owns first, by what the query answers, and the window is exactly the offsets whose access stays inside that. So no check in the fast half could have failed.

check_live asks whether anything owns the address right now, and the query answered that too, since a byte belonging to the owner of first is a byte with an owner. Right now is the catch, and it is why nothing that could free may be in the loop. A call in the body could free the object between the question and the iteration that reads it, and then the fast half would read freed storage with nothing to say so.

That is a question about the callee rather than about calling, and crate::nofree answers it before the pipeline starts, so a call carrying rucc_ir::Flags::NOFREE is one the loop may keep. Hoisting refuses every call whatever it does, and the reason is not this one: it needs the loop to reach the end of what its count says, and a call that does not come back leaves it short. Splitting never claims the loop reaches the end, so a call that might not come back costs it nothing.

Two answers of the query carry the weight and both are argued where the query is implemented. An address no watched region covers gets the whole limit back, so a loop over a local or a global splits into a fast half that runs the whole way, which is right because no check on such an address ever fires under this milestone. An address whose granule nobody owns gets zero, so the limit is zero, the fast half runs no iterations, and the check inside the slow half is what reports the dangling pointer, at the access rather than at the loop.

Which loops

Innermost, one latch, a preheader, nothing in it that could free, and no value defined inside it that anything outside reads. Not a count, unlike hoisting, because the count is not something this rests on: it is spent on how far to ask the runtime to look, and the runtime answers with a true count of the bytes that belong to the object whatever it was asked for. A loop nobody counted gets the same guess everything else that has to guess about a loop gets, ten, which is GCC’s avg-loop-niter and the number crate::scev::Estimate already hands out. The last is loop closed form, which crate::canon establishes, and it is checked rather than assumed because the copy would otherwise leave a reader outside the loop seeing whichever half happened to define the value.

Canonicalization runs a long way in front of this, and simplify-cfg between the two undoes some of what it did, so on SQLite the closed form condition is what refuses 351 of the checks this would otherwise have taken out. Running canonicalization again in front of this gets 156 of them back and costs 17672 bytes of .text, which is a bad trade for eleven more checks, so the answer is for this to repair the exits of the one loop it is splitting rather than for the pipeline to repair every loop in the function. That is its own piece of work.

Not every check in the loop has to be one this can size. A check whose address the analysis cannot follow simply stays in both halves, and the fast half is then a loop with fewer checks in it rather than none. That is worth having on its own and it is worth having because it is what a real loop looks like: one sweep the analysis reads and one index that came out of a table.

Which level

-O2 and -O3, alongside crate::unroll and for the same reason. The loop body is copied, so the function grows by about the size of the loop, and buying speed with code is what those levels are for and what -Os and -Oz are for declining.

Structs

Split

The pass.