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 ————/ -—–– ————

This implementation is heavily inspired by the work outlined in libfirm.

The general algorithm proceeds in two phases: (1) walk the CFG backwards to construct a graph of threading conditions, and (2) propagate fulfilled conditions forward by duplicating blocks.

1. Condition graph construction

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.

Inside a block, we associate with each condition c a set of targets:

• Goto(target) if fulfilling c changes the terminator into a Goto { target };
• Chain(target, c2) if fulfilling c means that c2 is fulfilled inside target.

Before walking a block bb, we construct the exit set of condition from its successors. For each condition c in a successor s, we record that fulfilling c in bb will fulfill c in s, as a Chain(s, c) condition.

When encountering a switchInt(place) -> [value: bb...] terminator, we also record a place == value condition for each value, and associate a Goto(target) condition.

Then, we walk the statements backwards, transforming the set of conditions along the way, resulting in a set of conditions at the block entry.

We try to avoid creating irreducible control-flow by not threading through a loop header.

Applying the optimisation can create a lot of new MIR, so we bound the instruction cost by MAX_COST.

2. Block duplication

We now have the set of fulfilled conditions inside each block and their targets.

For each block bb in reverse postorder, we apply in turn the target associated with each fulfilled condition:

• for Goto(target), change the terminator of bb into a Goto { target };
• for Chain(target, cond), duplicate target into a new block which fulfills the same conditions and also fulfills cond. This is made efficient by maintaining a map of duplicates, duplicate[(target, cond)] to avoid cloning blocks multiple times.

Structs

Condition 🔒

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

ConditionIndex 🔒

ConditionSet 🔒

JumpThreading 🔒

OpportunitySet 🔒

TOFinder 🔒

Enums

EdgeEffect 🔒

Represent the effect of fulfilling a condition.

Polarity 🔒

Constants

MAX_COST 🔒

MAX_PLACES 🔒

Functions

remove_costly_conditions 🔒

simplify_conditions 🔒

Propagate fulfilled conditions forward in the CFG to reduce the amount of duplication.