From 624463a0031ead3f9b7f35109f130eec9900fc5c Mon Sep 17 00:00:00 2001
From: Jakub Kuderski <kubakuderski@gmail.com>
Date: Wed, 16 Aug 2017 16:12:52 +0000
Subject: [Dominators] Introduce batch updates

Summary:
This patch introduces a way of informing the (Post)DominatorTree about multiple CFG updates that happened since the last tree update. This makes performing tree updates much easier, as it internally takes care of applying the updates in lockstep with the (virtual) updates to the CFG, which is done by reverse-applying future CFG updates.

The batch updater is able to remove redundant updates that cancel each other out. In the future, it should be also possible to reorder updates to reduce the amount of work needed to perform the updates.

Reviewers: dberlin, sanjoy, grosser, davide, brzycki

Reviewed By: brzycki

Subscribers: mgorny, llvm-commits

Differential Revision: https://reviews.llvm.org/D36167

llvm-svn: 311015
---
 llvm/lib/IR/Dominators.cpp | 10 ++++++++++
 1 file changed, 10 insertions(+)

(limited to 'llvm/lib/IR/Dominators.cpp')

diff --git a/llvm/lib/IR/Dominators.cpp b/llvm/lib/IR/Dominators.cpp
index 993ef1d7c22..a5900e49ad0 100644
--- a/llvm/lib/IR/Dominators.cpp
+++ b/llvm/lib/IR/Dominators.cpp
@@ -64,6 +64,8 @@ template class llvm::DomTreeNodeBase<BasicBlock>;
 template class llvm::DominatorTreeBase<BasicBlock, false>; // DomTreeBase
 template class llvm::DominatorTreeBase<BasicBlock, true>; // PostDomTreeBase
 
+template struct llvm::DomTreeBuilder::Update<BasicBlock *>;
+
 template void llvm::DomTreeBuilder::Calculate<DomTreeBuilder::BBDomTree>(
     DomTreeBuilder::BBDomTree &DT);
 template void llvm::DomTreeBuilder::Calculate<DomTreeBuilder::BBPostDomTree>(
@@ -79,6 +81,11 @@ template void llvm::DomTreeBuilder::DeleteEdge<DomTreeBuilder::BBDomTree>(
 template void llvm::DomTreeBuilder::DeleteEdge<DomTreeBuilder::BBPostDomTree>(
     DomTreeBuilder::BBPostDomTree &DT, BasicBlock *From, BasicBlock *To);
 
+template void llvm::DomTreeBuilder::ApplyUpdates<DomTreeBuilder::BBDomTree>(
+    DomTreeBuilder::BBDomTree &DT, DomTreeBuilder::BBUpdates);
+template void llvm::DomTreeBuilder::ApplyUpdates<DomTreeBuilder::BBPostDomTree>(
+    DomTreeBuilder::BBPostDomTree &DT, DomTreeBuilder::BBUpdates);
+
 template bool llvm::DomTreeBuilder::Verify<DomTreeBuilder::BBDomTree>(
     const DomTreeBuilder::BBDomTree &DT);
 template bool llvm::DomTreeBuilder::Verify<DomTreeBuilder::BBPostDomTree>(
@@ -312,6 +319,9 @@ void DominatorTree::verifyDomTree() const {
     print(errs());
     errs() << "\nActual:\n";
     OtherDT.print(errs());
+    errs() << "\nCFG:\n";
+    F.print(errs());
+    errs().flush();
     abort();
   }
 }
-- 
cgit v1.2.3