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.

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.

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 the same restriction hoisting has, for a weaker reason, and lifting it is a matter of asking crate::nofree about the callee rather than refusing every call.

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, a count, nothing in it that could free, and no value defined inside it that anything outside reads. 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.