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] contains Condition { value, polarity: Eq, target } if assigning value to place turns the SwitchInt into Goto { target }.
  • conditions[place] contains Condition { value, polarity: Ne, target } if assigning anything different from value to place turns the SwitchInt into Goto { 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 ThreadingOpportunitys 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§

Enums§

Constants§

Functions§

  • loop_headers 🔒
    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.
  • predecessor_count 🔒