[llvm-dev] [GSoC] [RFC] A new dominator tree updater for LLVM

[Chijun Sima via llvm-dev]

Hello,

Here is the plain text version of the RFC:

TL;DR
The purpose of this RFC is to bring a new updater to unify the API
when performing updates to the dominator tree and the post dominator
tree using different update strategies. The prototype of the new
updater class APIs is available on Github for feedback. [1] The
existing interface to update the dominator tree/post dominator tree is
fragmented. (DT.applyUpdates(Updates) when performing eager updates or
construct a DeferredDominance class instance to perform deferred
updates).

The new dominator tree updater resolves these issues by providing a
cleaner API to perform updates on available dominator trees (none,
only DomTree, only PostDomTree, both) using different update
strategies (eagerly or lazily) to simplify the updating process. We
will also try to enable more optimizations when performing updates in
the future.

—Motivation—

1. The current API is quite fragmented and different functions using
these APIs need to write redundant code to manually deal with various
kinds of update strategies which makes code hard to maintain. Directly
calling update functions of DominatorTree updates the data structure
eagerly while DeferredDominance does updates lazily. Thus some
functions need to perform lazy incremental updates in the codebase
need to construct an additional lazy updater. [2] DeferredDominance
class cannot be used when a PostDominatorTree also needs to be updated
because BasicBlocks are maybe pending to be removed. And functions
receiving DominatorTrees can avoid code patterns like that in [5]
which is currently necessary.

For eager updates:
DT.applyUpdates(Updates);
For deferred updates:
DeferredDominance DDT(DT);
DDT.applyUpdates(Updates);
...
DDT.flush();
When passing into functions:
void llvm::Func(DominatorTree *DT, PostDominatorTree *PDT, LoopInfo *LI){
 // Some code from the LLVM code reviewer
 if (!DT && !PDT && !LI)
   return;
 if (DT || PDT) {
   // Construct the Updates vector.
   if (DT)
     DT->applyUpdates(Updates);
   if (PDT)
     PDT->applyUpdates(Updates);
  }
}
2. Some functions using both DomTree and PostDomTree need to call the
update function separately on both trees. [3]
For example:
DominatorTree DT;
PostDominatorTree PDT;
...
DT.applyUpdates(Updates);
PDT.applyUpdates(Updates);
3. With the current APIs, we need to manually decide whether to erase
a BasicBlock from the dominator tree when one is removed from the CFG
[4].
4. When using lazy updating methods, the BasicBlock waiting to delete
will be deleted in an unforeseeable time after being removed from the
Function so the user cannot do further actions on it.
5. When we have both trees (DomTree and PostDomTree), we can try using
the update information of one of them to prune updates of another to
accelerate the updating process.

—General Design—

1. To address the issue (1), the new updater class needs to have the
ability to perform either eager updates or lazy updates. So, all the
abilities of the DeferredDominance are subsumed by the new updater
class. And the API user can use an enum to specify which update
strategy to use.
2. To address the issue (2), the new updater class can update all the
data structures it holds when the user calls the update function.
3. To address the issue (3), the new updater class will first check
whether these BasicBlocks still act as a node in the holding trees
then call delete to prevent further manual checks.
4. To address the issue (4), the updater class adds a callbackDeleteBB
function which accepts a callable to let users do additional
operations on the BasicBlock before deletion.

—More Details—

The updater class can be constructed by specifying the related tree
and the update strategy. It is because currently, a single pass will
only use a single update strategy to update the DomTree/PostDomTree.
When using the eager update strategy, it will perform updates the same
as holding those trees. If it works in the lazy updating mode, it will
perform updates deduplicating and remove invert updates like
DeferredDominance class. Users can use hasDomTree() and
hasPostDomTree() to query which tree the updater holds to enable
further uses when passing into functions.

—Implementation plan—

1. New DomTreeUpdater class, which brings a clean API to update
DominatorTree and PostDominatorTree with either deferred/eager update
strategy.
2. Unittests for basic functions of the new class.
3. Replace existing users of DeferredDominance with the new class.
4. Remove DeferredDominance.
—Future—
Further optimizations enabled by the new design.

Thanks,
Chijun Sima

[1] https://github.com/NutshellySima/llvm/pull/1/files
[2] https://llvm.org/doxygen/classllvm_1_1DeferredDominance.html
[3] https://github.com/llvm-mirror/llvm/blob/master/unittests/IR/DominatorTreeBatchUpdatesTest.cpp#L109-L112
[4] https://github.com/llvm-mirror/llvm/blob/master/unittests/IR/DominatorTreeTest.cpp#L578-L584
[5] https://reviews.llvm.org/D42804