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

[Chijun Sima via llvm-dev]

Hello,

Here is the first patch sent out:
https://reviews.llvm.org/D48383

Thanks,
Chijun Sima

Chijun Sima <simachijun at gmail.com> 于2018年6月8日周五 下午9:12写道：
>
> 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