Expand description
Jump threading, with and without a copy of the block threaded past.
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 FREE, and COPY
is that plus section 23.1’s copy, under the limits of section 23.4.
§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::dcedeletes 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 copy, and what it owes the values
On the corpus the free subset threads one edge out of the 623 that decide the branch they arrive
at, and 619 of the rest are refused because a block below reads a value the block defines. So
the copy is there to make values, not to repeat effects, and COPY only copies a block the
free subset would already walk past: nothing in it has an effect, and nothing in it carries a
side table entry crate::header_copy has not been checked against. What changes is that its
values may be read below and carried on the arm.
The copy is made on the one edge being threaded. It has no parameters, since along that edge they are the arguments the edge carries, it holds the block’s instructions with those arguments put in, and it ends in a jump to the arm the edge decides. The edge is pointed at it. The arm’s arguments come from the copy, so a value the block worked out is the copy’s version of it.
What that leaves is every read of the block’s values from somewhere else. The block no longer dominates them, since the copy reaches some of them as well, so each value now has two definitions and a read below needs whichever one reached it. That is SSA construction for one variable with two definitions, and it is done the classical way: a block parameter goes on each block in the iterated dominance frontier of the block and its copy where the value is still wanted, the edges into it carry what reached the end of the block they leave, and every read is of what reached the start of the block it is in. What reached a block is the nearest of the block, the copy and the new parameters up the dominator tree, which is why the parameters go where the frontier says: those are exactly the places where the nearest one up the tree is not the only one that can arrive. Liveness is what keeps the parameters to the ones something reads, and is also what makes it safe to skip the parameters of every other block in the frontier.
§The limits
Section 23.4 adopts GCC’s four and they are all here, in rucc_cost::heuristics. A block of
more than fifteen instructions is not copied. A thread whose arm goes back to the header of a
loop the block is in counts each instruction twice. A copy whose edge came out of an earlier
copy is the next block of one path, and a path may not copy more than a hundred instructions in
all. And one run makes at most sixty four copies in one function, which is GCC’s bound on paths
turned from the paths a backward search looks at into the paths that are actually copied, since
there is no backward search here. The last two are what stop threading from feeding on itself,
since every copy is a new edge into the arm and the arm may be the next block this walk threads
past.
§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.
Without a copy 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. With one the same is true of the path through the copy, which is B’s path with B’s test taken out, so loops can still only be destroyed. The loop forest is rebuilt after each thread anyway, which is what keeps the next decision honest.
§Which level this runs at
FREE runs at -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 FREE 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. COPY runs at -O1 and
above, as GCC’s -fthread-jumps does.
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 FREE 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.
COPY threads the last two and records a limit instead where one stops it. One more 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. 619 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 split is why the copy here is the copy of a block with no effects in it.
Structs§
- Thread
- The pass, with how many instructions it may copy a block of.