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

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
1 message Options
Reply | Threaded
Open this post in threaded view
|

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

Tim Northover via llvm-dev

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);

}

  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

[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




_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev