[llvm-dev] [RFC][Dominators] Batch update API for dominators

[Jakub (Kuba) Kuderski via llvm-dev]

Hi folks,

Earlier today I submitted for review a patch D36167
<https://reviews.llvm.org/D36167> that introduces API for performing batch
updates on the (Post)DominatorTree. Before that, the DomTree exposed only
very low-level functions for performing incremental updates:
insertEdge(From, To) and deleteEdge(From, To). The main problem with it is
that the API needed to know about every inserted and deleted CFG edge as
the update happened -- it wasn’t possible to perform some transformation
and then do all of the DomTree updates.

The batch updates enable us to do a transformation and defer informing the
tree about it until we are done with changing the CFG. The list of updates
to perform doesn’t even have to be provided in the same order in which they
really happened. Moreover, the batch updater is able to optimize away
redundant updates and in the future it will be also able to reorder updates
to reduce the amount of work needed to apply them.

I updated two of my patches (in review) to use the new batch update API,
you can find them here: D35581 <https://reviews.llvm.org/D35581>, D35528
<https://reviews.llvm.org/D35528>. Here’s a snippet taken from the
LoopRotate patch that uses the batch update API:

> SmallVector<DominatorTree::UpdateType, 3> Updates;
> Updates.push_back({DominatorTree::Insert, OrigPreheader, Exit});
> Updates.push_back({DominatorTree::Insert, OrigPreheader, NewHeader});
> Updates.push_back({DominatorTree::Delete, OrigPreheader, OrigHeader});
> DT->applyUpdates(Updates);


If you are interested in discussing the design or the implementation,
please leave a comment here or on phabricator.

Thanks,
Kuba

-- 
Jakub Kuderski
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170801/a1cea5c4/attachment.html>