Incrementally updating the Dominator
Preface
An input program function is represented using a Control Flow Graph (CFG). It’s composed of different Statements, which decompose into Expressions, but we will not concern ourselves with Expressions. The main control flow constructs are SplitStatement and MergeStatement. The SplitStatement has outgoing edges to N (N = 2 in the case of IfStatement) other Statements, and the MergeStatement has incoming edges from M other Statements.
The Dominator is a data structure that holds “domination relationship” between any two Statements in the CFG. “A dominates B” means: all paths starting from the start of the CFG to end of the CFG, that flow through A, must necessarily flow through B. It’s represented using a tree of things that progressively dominate their children. We want to incrementally update this structure.
Motivation
Any code motion transform will invalidate the Dominator at each step, and running Cooper or LengauerTarjan on each invalidation is expensive even if the algorithm is nearlinear. The number of queries is several times the number of reconstructions; we cannot trade off queryefficiency for easeofupdate.^{1}
Background
The main supporting data structure we will use for this feat is the Program Structure Tree, which is incrementally updated. The PST is a tree representation of structured control flow: all Control Flow Graph nodes belong to a Region in a nesting of singleentry singleexit Regions. Any controlflow that cannot be classified is boxed in an UnstructuredRegion, which we will not handle.
This is a Region:
This is a ChainRegion comprising of an IfRegion and a BasicBlockRegion:
This is an UnstructuredRegion, but it is very much SESE:
Updating a vanilla Dominator tree is relatively easy: simply add a child to the correct node. The problem at hand is that we have an O(1)query Dominator object that we want to keep up to date as we make edits to the IR. How is it O(1)query? Every node in the tree is assigned DFS start and end times: so if one interval nests within another, the corresponding node is dominated by the other node.
Supporting arbitarary IR edits is both very hard and not a useful goal: we can reduce all our edits to two items, namely inserting a SESE Statement, and inserting a SESE PST Region. Removing a Statment or Region is not interesting, because it just leaves gaps in the numbering, and doesn’t affect any existing Dominance relationships if we make no changes after removal. Modifying a Region can be easily expressed as the removal of the old Region/insertion of the new Region.
The PST gives us an excellent mechanism to classify the blob we’re injecting into the CFG. The interesting Regions begin with a SplitStatement, and end with a MergeStatement, or begin with a MergeStatement and end with a SpiltStatement: IfRegions, SwitchRegions, and LoopRegions. This is the key property we will use to do the inremental update.
Possible approaches
First, it must be noted that by using tight consecutive DFS start and end timers, we will have no choice but to renumber the descendant tree when something is inserted. So, we leave gaps of 64 between the numbering, to stuff our new SESE Statement or Region into. It may be argued that using fractions is profitable, but we found that space to fit intervals wasn’t the bottlneck: the hard problem is determining dominance. When attempting to stuff a new Region into an existing gap, we can imagine centering around the midpoint of the gap, and leaving space for more Regions above and below. Bisecting each gap will exhaust the gaps quickly, and we decided to optimize for insertion only from top to bottom.
One approach we could take is to assume that the Regiontobeinserted has been removed from a different part of the tree, and has some numbers already that we simply need to adjust them (those numbers will be spaced with gaps of 64, and we need to compress them). This approach wouldn’t be able to handle newly created Regions.
Our algorithm
The key insight in our algorithm is that we need to match a Split Statement with
its Merge Statement(s), and need to paritition our DFS start/end time intervals
into two categories: intervals to trust (ie. ones that exist, and should not be
modified), and intervals to assign. The DFS start time corresponds to DFS
firstvisit sequence, and end time corresponds to DFS finalvisit sequence.
interval1.start_time > interval2.start_time
and
interval1.end_time < interval2.end_time
means that interval1 is nested within
interval2, or that the node corresponding to interval2 dominates the node
corresponding to interval1.
The reason we need to match a Split to a Merge is that there are two cases:

The Merge dominates the Split, in which case, the Merge dominates everything lying on the outEdges of the Split leading to the Merge

The Split dominates the Merge, in which case, the Split dominates everything on its outEdges leading to the Merge.
The intervals of the each of the outEdges (“branches”) must stagger with each other so there’s no false dominance relationship between them. Two intervals “staggering” means one not being nested within the other. In the case of SplitdominatesMerge, they must additionally stagger with the Merge.
Our API looks like:
void assignHeads(std::vector<Statement*> branchHeads,
std::vector<Statement*> headsToStaggerWith,
Statement* nestWithin, Statement* toEnclose);
First, we assign intervals to the split and merge Statements in the Region, by looking at their predecessor and succeesor. The predecessor is something we need to nest within. Since we decided that we’ll only optimize for the case of toptobottom insertion, we can simply add one to the start time, and subtract one from the end time to get the necessary start and end times for the Region entry. For the Region exit, it’s a little more tricky: we need to leave gaps on either side, because there may be nodes along the inEdge(s) as well as nodes along the outEdge(s). For simplicity, let’s simply assign an interval halfway between the Region entry and successor intervals.
Then, we assign intervals to be branchHeads
(ie. successors of the
SplitStatement whose intervals we need to assign), by staggering with the
headsToStaggerWith
(ie. successors of the SplitStmt whose intervals we must
trust + the MergeStatement if SplitdominatesMerge). nestWithin
is the
SplitStatement, and toEnclose
is nullptr
.
Finally, we trivially assign intervals to the rest of the Stmts in the Region, following the Split, by nesting them within the branch heads.
Now, this API generalizes to SESE Statements as well. branchHeads
is the
singular SESE Statement, headsToStaggerWith
may or may not include the
containing Region’s MergeStatement. headsToStaggerWith
will contain all the
other successors of the SplitStatement
, if the SESE Statement is one of the
successors, and may contain the MergeStatement. If the successor has one
inEdge, it’s used as toEnclose
.
The actual interval calculation is quite simple. Subtract the staggerUnion
interval (union of all the stagger intervals) from the nestWithin
interval:
this produces two “gaps” which we need to “dice up” into N intervals (where N is
the number of branchHeads
). The number of intervals in the left gap versus the
right gap is dependent on the ratio of the sizes of the gaps. toEnclose
simply
tells us whether to pick the left gap or right gap in the case of a single
branchHead
. It’s also useful to check interval exhaustion cases.
There is an elegant way to catch all the cases when the interval has been
exhausted. Just throw
an exception from the intervalconstruction class.
Catch this exception and abort the incremental update: recompute the Dominator.
Closing notes
Conceptually, the algorithm is simple. The implementation, as leveraged by one transform, passes our entire testsuite (~6k tests).
Our implemenation of the Dominator incremental update relies on a correct implementation of the PST incremental update: incorrect information from one incremental update will propagate to the other incremental update and wreak havoc.
The best way to test the implementation is to have a recomputed Dominator as reference, and checking that the dominatesrelationship between every two nodes is the same in the incremental update and recompution case.