[RFC][Dominators] Batch update API for dominators

Hi folks,

Earlier today I submitted for review a patch 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, 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