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

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

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