Module thread 

Jump threading, the part of it that does not copy anything.

Design: spec/optimizer/23-jump-threading.md. If, on the path through block A into block B, the condition B tests is already decided, then A should branch straight to the arm B was going to take and skip B’s test. On real C that removes more branches than anything else in the compiler, because C is full of conditions that are redundant along some paths and not along others.

It is also the pass most likely to explode, because the general form works by copying B, and a copy grows the function, and the growth compounds because each thread makes new paths on which further threading is possible. Section 23.4 is four separate limits on that growth and section 23.6 names the subset where there is none: the case where the block being threaded past does not have to be copied at all, which is pure edge redirection. That subset is what is here.

What decides a branch here, and what does not

Arguments in this IR live on the edge rather than in the block, so a block parameter is a value that arrives differently depending on which way control came. Bind a block’s parameters to what one edge carries and its terminator may resolve on that edge while resolving on no other, which is the whole of the path sensitivity this pass has. It covers section 23.3’s example directly:

if (a) x = 1; else x = 2;
if (x == 1) ...

Nothing dominating the second test decides it, so the forward threader of section 23.2 cannot see it and neither can simplify-cfg. But x arrives at the second test as a block parameter, it is 1 along one edge and 2 along the other, and both edges resolve. Both are threaded, nothing is left reaching the block, and the second branch goes.

What is not here is section 23.3’s backward search with the path-sensitive range solver. This asks about one edge and not about a path of them, so a condition decided two blocks back and not one is a condition this does not see. The range machinery for that exists in crate::range and the search is the larger half of the document.

Why no block has to be copied

Section 23.1 quotes GCC’s six step surgery, whose first step is a copy of B. The copy exists so that B’s side effects still happen on the threaded path and so that the values B defines are available to the arm the thread lands on. Where neither is needed, neither is the copy, and this pass threads exactly the edges where neither is needed:

• Every instruction in B other than its terminator has no effects, so a path that skips them skips nothing that had to happen. That is the same predicate crate::dce deletes an instruction under, which is the point: an instruction it would delete outright is one a path can walk past.
• Nothing outside B reads a value B defines. Those are the values the copy would have existed to compute, and both the arm’s arguments and the blocks further down are asking for them.

The second condition has to be about the whole function and not just about the arm. An argument is how a value crosses into a block that B does not dominate, but a block B does dominate reads what B defined with no argument at all, because dominance is the only permission a use needs. Threading an edge past B takes that dominance away, and the read is then of a value that was never computed on the path taken. Checking only the arm’s arguments misses exactly that, which is what a_value_the_block_defines_and_something_below_it_reads_needs_the_copy is about.

B’s parameters are covered by the same rule, since a parameter is a value B defines. Along the edge being redirected they are known, so B’s own reads of them are substituted rather than refused, but a read from below is a read of a value that is about to stop existing. And a value the arm carries that is defined outside B dominates the block it is being carried out of, so it dominates the predecessor as well: it is on every path to B, the predecessor has an edge to B, so it is on every path to the predecessor. That is section 23.1’s “the values must still dominate”, and it is the same argument spec/optimizer/21-cfg-simplification.md section 21.4 needs for forwarder removal.

The loop rules, which are refusals and not scores

Section 23.5. Threading a path into a loop somewhere other than its header makes an irreducible loop, and document 06.4 established that rucc does not split nodes and gives up on irreducible regions instead. So the rule here is stronger than GCC’s, where it is one input to a cost model: a thread that would do it is refused, at every level. A predecessor that is a latch is refused too, because moving a latch’s edge is how the single latch property document 07.3 wants stops being true. And a block already in an irreducible region is left alone entirely, since the loop forest has given up on it and the two checks above would be reading an answer nobody stands behind.

Because nothing is copied, no new cycle can appear. The new edge from A goes where the edge out of B went, so a path along it is a path that was already there with B taken out of the middle. Loops can therefore only be destroyed, and the loop forest is rebuilt after each thread anyway, which is what keeps the next decision honest.

Which level this runs at

Every level that optimizes, including -Os and -Oz. Section 23.6 restricts threading at those two to the case where the block is empty, on the ground that it is the only part that is free, and this pass is that part generalized: a block whose instructions all have no effects and whose outgoing arguments do not come from it costs the same as an empty one, which is nothing.

Once, and not to a fixed point. Threading enables threading, and section 23.7 says the answer to that is a fixed number of instances rather than a loop, because threading is the pass where adversarial input is easiest to construct. Section 23.5 asks for two instances at -O2, an early one and a late one after the loop pipeline and SCCP. There is one here, in the early position. The late one wants the passes that are not written yet.

What it counts

Every refusal is recorded, and they are the measurement section 23.8 asks this document for. Three of them count edges that decide a branch this pass cannot thread without the copy, split by which part of the copy is in the way: something in the block that has to happen, a value the arm carries that the block worked out, and a value the block defines that a block below it reads. Together they are the size of the prize for building section 23.1’s surgery, and separately they say what the surgery has to do first. The fourth counts edges refused on loop structure, which is the price of document 06.4’s position on irreducible regions stated as a number rather than as an argument.

On the 1461 programs of the corpus at -O2, 623 edges decide the branch they arrive at and one of them is threadable without a copy. So the subset that is free is close to worthless on real C, and this pass earns its place by measuring that rather than by what it removes. The 623 is the number that justifies the rest of document 23.

The split says where the rest of the work is. 619 of the 623 are blocked on a value the block defines being read below it, 4 on the arm carrying one, and none at all on the block doing something that has to happen. That is one conclusion rather than three: the block being threaded past is almost never doing work that matters, it is holding a value that matters, so section 23.1’s copy is there to reconstruct values and not to repeat effects. A cheaper thing than a full block copy might do it, and that is worth knowing before the surgery is written rather than after.

Structs

Thread

The pass.