Module jump_threading 

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

Condition 🔒

Represent the following statement. If we can prove that the current local is equal/not-equal to value, jump to target.

ConditionSet 🔒

JumpThreading 🔒

OpportunitySet 🔒

TOFinder 🔒

ThreadingOpportunity 🔒

Enums

Polarity 🔒

Update 🔒

Constants

MAX_BACKTRACK 🔒

MAX_COST 🔒

MAX_PLACES 🔒

Functions

predecessor_count 🔒