Module rustc_mir_transform::jump_threading
source · Expand description
A jump threading optimization.
This optimization seeks to replace join-then-switch control flow patterns by straight jumps X = 0 X = 0 ————\ /–––– ———— X = 1 X––X SwitchInt(X) => X = 1 ————/ -—–– ————
We proceed by walking the cfg backwards starting from each SwitchInt
terminator,
looking for assignments that will turn the SwitchInt
into a simple Goto
.
The algorithm maintains a set of replacement conditions:
conditions[place]
containsCondition { value, polarity: Eq, target }
if assigningvalue
toplace
turns theSwitchInt
intoGoto { target }
.conditions[place]
containsCondition { value, polarity: Ne, target }
if assigning anything different fromvalue
toplace
turns theSwitchInt
intoGoto { target }
.
In this file, we denote as place ?= value
the existence of a replacement condition
on place
with given value
, irrespective of the polarity and target of that
replacement condition.
We then walk the CFG backwards transforming the set of conditions.
When we find a fulfilling assignment, we record a ThreadingOpportunity
.
All ThreadingOpportunity
s are applied to the body, by duplicating blocks if required.
The optimization search can be very heavy, as it performs a DFS on MIR starting from
each SwitchInt
terminator. To manage the complexity, we:
- bound the maximum depth by a constant
MAX_BACKTRACK
; - we only traverse
Goto
terminators.
We try to avoid creating irreducible control-flow by not threading through a loop header.
Likewise, applying the optimisation can create a lot of new MIR, so we bound the instruction
cost by MAX_COST
.
Structs§
- Represent the following statement. If we can prove that the current local is equal/not-equal to
value
, jump totarget
. - TOFinder 🔒
Enums§
Constants§
- MAX_
COST 🔒
Functions§
- Compute the set of loop headers in the given body. We define a loop header as a block which has at least a predecessor which it dominates. This definition is only correct for reducible CFGs. But if the CFG is already irreducible, there is no point in trying much harder. is already irreducible.