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 counts iterations of the fast half and hands over to the slow half once the count reaches a limit worked out in the preheader.

The counter is a new one rather than the loop’s own, and the test is against a limit 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 counter. 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 count. Half the loops this takes on SQLite are that shape.

Where the limit comes from

For a check whose address is first + i * step reading reach bytes each time, every iteration with i * step + 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 limit is (extent - reach) / step + 1, or zero when extent is smaller than reach, and where a loop has several such checks in it the limit is the smallest of theirs.

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, which is a division that does not have to happen and a question with a shorter answer. Such a check fits on the first iteration or on none of them, so what there is to work out is which of the two, and how far the runtime is asked to look is 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.

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 limit is exactly the iterations whose access stays in that window. 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.