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 limit and never more than the truth, so what this pass asks for is as much as the arithmetic carries. That used to be a trip count times a step, on the grounds that what the query walked was work the loop was about to do anyway. tamnd/rucc#861 stopped it walking and tamnd/rucc#871 took the bound off: the query probes the far end of what it was asked for and halves, so the price does not turn on the number, and a limit smaller than the object is a smaller window and so fewer iterations in the half with no checks in it.

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. 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. Not knowing 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, and the reason is money rather than soundness. The guard compares the difference against the window at run time, so p = p->next is safe to measure: a node that landed inside the first one’s object passes the comparison and one that did not takes the slow half, and either way the answer is right. It is that a list never passes. The next node of a heap allocated list is its own object, so the guard fails on the second iteration and every one after it, and the split bought a second copy of the loop with every check still in both halves. Letting lists through on SQLite splits 73 more loops, puts 220 more calls to check_bounds in the object and adds 139 kilobytes, for 5 liveness checks. 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 is buying is.

A fixed distance from a pointer the header carries is not the only address the guard can find its way to, and on real code it is not even the commonest. The one above it is that pointer plus a variable, which is an address that is still a function of what the header carries and of what the loop was handed, and both the guard and the preheader hold every one of those. So the guard writes the arithmetic out again from its own parameters, the preheader writes it out again from the values it passes, and the subtraction between the two is the same subtraction. That is rematerialization rather than measurement, writable is where it is decided and remade is where it is written, and the fixed distance case is the instance of it that costs nothing to write.

What may be written again is a list of opcodes rather than a question about effects, because two things have to hold and neither is what an effect flag answers. The copy has to compute the same number somewhere else, which is what rules out reading memory, and it has to be harmless in the preheader of a loop that turns out to run no iterations, which is what rules out a divide.

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.

check_deriv asks whether a pointer computed from another one stayed inside the capability the first one had, and that is the same containment written about a pointer rather than about the bytes under it. It is the narrower question of the two, since the window document 03 section 3.1 allows a derivation runs a stride below the object and up to its end, and the fast half is only ever claiming the address is inside. So a loop whose bounds check the window covers has a derivation check the same window covers, and on the two benchmarks where an index walks a byte at a time that check was all the fast half had left in it.

What it needs beyond a walk is that the extent was asked about the object the check names. The query goes to the first iteration’s address, so an address a little way along from the pointer the check is about is a question about whatever owns that instead, which past the end of one object is the next object rather than nothing. Two shapes give the right object and started and paired are the two. Either the walk starts on the pointer the check names, or that pointer walks the loop alongside the new one, in which case the two are a fixed distance apart on every iteration and a window that wide holds the pair: the lower end being inside the object says the capability is that object and the upper end being inside it says the derivation stayed there.

The second is the commoner by a long way, because p = p + k is what most pointer arithmetic in a loop is, and it is what bench/safety/a-string-scan does.

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

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, and not even a step: the count was spent on how far to ask the runtime to look and nothing asks for less than everything any more, and the step was spent on the same thing. 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 once refused 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 that this repairs the one loop it is splitting rather than the pipeline repairing every loop in the function. repaired is that, and with the repair reaching the joins the exits meet at as well as the exits themselves the condition now refuses none of them.

What the repair cannot help with is a name the pass is about to write and has not written yet. A guard is worked out from values the loop was handed, and where the loop before it is one this is also splitting, a value that loop defines stops being one value the moment it has two halves. Those loops are refused, and there are five of them on SQLite against the two hundred and fifty the repair finishes.

A loop with a loop inside it is not refused, and there is nothing about an inner loop that would make the copy wrong: the copier takes any set of blocks and the guard goes in front of the outer header either way. What the outer guard cannot speak for is a check inside the inner loop, since it measures where the outer walk has got to at the top of an outer iteration and the inner loop runs its whole way inside that iteration. Those checks stay in both halves and the inner loop’s own split is what takes them, so what an outer split is worth is the checks in the outer loop’s own blocks. On SQLite that is most of what is there: of the 169 nests the pass used to refuse outright, 162 have a check in the outer loop’s own blocks and 113 have more than six.

Where a nest plans twice the inner plan wins, because the two plans name blocks in common and applying either moves them. The outer one comes back on the next run of the pipeline. The size limit is the one limit, counted over the whole nest, which is what heuristics::SPLIT_MAX_INSNS already counts since a loop’s block list holds the blocks of the loops inside it. A second and smaller limit was the obvious guess and the measurement says it is not needed: the outer loop’s own blocks are over fifty instructions in 115 of those 169, so a nest that fits inside the limit is mostly the outer loop rather than mostly the inner one, and the limit is already pricing the part that pays.

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.