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

[Chijun Sima via llvm-dev]

*TL;DRThe 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);} 1. 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); 1. 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]. 2. 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.3. 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
<https://github.com/NutshellySima/llvm/pull/1/files>[2]
https://llvm.org/doxygen/classllvm_1_1DeferredDominance.html
<https://llvm.org/doxygen/classllvm_1_1DeferredDominance.html>[3]
https://github.com/llvm-mirror/llvm/blob/master/unittests/IR/DominatorTreeBatchUpdatesTest.cpp#L109-L112
<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
<https://github.com/llvm-mirror/llvm/blob/master/unittests/IR/DominatorTreeTest.cpp#L578-L584>[5]
https://reviews.llvm.org/D42804 <https://reviews.llvm.org/D42804>*
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20180608/409fe40b/attachment.html>