Index: include/llvm/IR/Dominators.h =================================================================== --- include/llvm/IR/Dominators.h +++ include/llvm/IR/Dominators.h @@ -37,13 +37,13 @@ extern template class DominatorTreeBase; // DomTree extern template class DominatorTreeBase; // PostDomTree +extern template class cfg::Update; + namespace DomTreeBuilder { using BBDomTree = DomTreeBase; using BBPostDomTree = PostDomTreeBase; -extern template struct Update; - -using BBUpdates = ArrayRef>; +using BBUpdates = ArrayRef>; extern template void Calculate(BBDomTree &DT); extern template void Calculate(BBPostDomTree &DT); Index: include/llvm/Support/GenericDomTree.h =================================================================== --- include/llvm/Support/GenericDomTree.h +++ include/llvm/Support/GenericDomTree.h @@ -24,6 +24,14 @@ #ifndef LLVM_SUPPORT_GENERICDOMTREE_H #define LLVM_SUPPORT_GENERICDOMTREE_H +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/GraphTraits.h" +#include "llvm/ADT/PointerIntPair.h" +#include "llvm/ADT/STLExtras.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/Support/CFGUpdate.h" +#include "llvm/Support/raw_ostream.h" #include #include #include @@ -32,13 +40,6 @@ #include #include #include -#include "llvm/ADT/DenseMap.h" -#include "llvm/ADT/GraphTraits.h" -#include "llvm/ADT/PointerIntPair.h" -#include "llvm/ADT/STLExtras.h" -#include "llvm/ADT/SmallPtrSet.h" -#include "llvm/ADT/SmallVector.h" -#include "llvm/Support/raw_ostream.h" namespace llvm { @@ -199,36 +200,6 @@ void DeleteEdge(DomTreeT &DT, typename DomTreeT::NodePtr From, typename DomTreeT::NodePtr To); -// UpdateKind and Update are used by the batch update API and it's easiest to -// define them here. -enum class UpdateKind : unsigned char { Insert, Delete }; - -template -struct Update { - using NodeKindPair = PointerIntPair; - - NodePtr From; - NodeKindPair ToAndKind; - - Update(UpdateKind Kind, NodePtr From, NodePtr To) - : From(From), ToAndKind(To, Kind) {} - - UpdateKind getKind() const { return ToAndKind.getInt(); } - NodePtr getFrom() const { return From; } - NodePtr getTo() const { return ToAndKind.getPointer(); } - bool operator==(const Update &RHS) const { - return From == RHS.From && ToAndKind == RHS.ToAndKind; - } - - friend raw_ostream &operator<<(raw_ostream &OS, const Update &U) { - OS << (U.getKind() == UpdateKind::Insert ? "Insert " : "Delete "); - U.getFrom()->printAsOperand(OS, false); - OS << " -> "; - U.getTo()->printAsOperand(OS, false); - return OS; - } -}; - template void ApplyUpdates(DomTreeT &DT, ArrayRef Updates); @@ -254,8 +225,8 @@ using ParentType = typename std::remove_pointer::type; static constexpr bool IsPostDominator = IsPostDom; - using UpdateType = DomTreeBuilder::Update; - using UpdateKind = DomTreeBuilder::UpdateKind; + using UpdateType = cfg::Update; + using UpdateKind = cfg::UpdateKind; static constexpr UpdateKind Insert = UpdateKind::Insert; static constexpr UpdateKind Delete = UpdateKind::Delete; Index: include/llvm/Support/GenericDomTreeConstruction.h =================================================================== --- include/llvm/Support/GenericDomTreeConstruction.h +++ include/llvm/Support/GenericDomTreeConstruction.h @@ -71,6 +71,7 @@ DenseMap NodeToInfo; using UpdateT = typename DomTreeT::UpdateType; + using UpdateKind = typename DomTreeT::UpdateKind; struct BatchUpdateInfo { SmallVector Updates; using NodePtrAndKind = PointerIntPair; @@ -1166,7 +1167,8 @@ } BatchUpdateInfo BUI; - LegalizeUpdates(Updates, BUI.Updates); + LLVM_DEBUG(dbgs() << "Legalizing " << BUI.Updates.size() << " updates\n"); + cfg::LegalizeUpdates(Updates, BUI.Updates, IsPostDom); const size_t NumLegalized = BUI.Updates.size(); BUI.FutureSuccessors.reserve(NumLegalized); @@ -1182,8 +1184,11 @@ LLVM_DEBUG(dbgs() << "About to apply " << NumLegalized << " updates\n"); LLVM_DEBUG(if (NumLegalized < 32) for (const auto &U - : reverse(BUI.Updates)) dbgs() - << '\t' << U << "\n"); + : reverse(BUI.Updates)) { + dbgs() << "\t"; + U.dump(); + dbgs() << "\n"; + }); LLVM_DEBUG(dbgs() << "\n"); // If the DominatorTree was recalculated at some point, stop the batch @@ -1193,76 +1198,11 @@ ApplyNextUpdate(DT, BUI); } - // This function serves double purpose: - // a) It removes redundant updates, which makes it easier to reverse-apply - // them when traversing CFG. - // b) It optimizes away updates that cancel each other out, as the end result - // is the same. - // - // It relies on the property of the incremental updates that says that the - // order of updates doesn't matter. This allows us to reorder them and end up - // with the exact same DomTree every time. - // - // Following the same logic, the function doesn't care about the order of - // input updates, so it's OK to pass it an unordered sequence of updates, that - // doesn't make sense when applied sequentially, eg. performing double - // insertions or deletions and then doing an opposite update. - // - // In the future, it should be possible to schedule updates in way that - // minimizes the amount of work needed done during incremental updates. - static void LegalizeUpdates(ArrayRef AllUpdates, - SmallVectorImpl &Result) { - LLVM_DEBUG(dbgs() << "Legalizing " << AllUpdates.size() << " updates\n"); - // Count the total number of inserions of each edge. - // Each insertion adds 1 and deletion subtracts 1. The end number should be - // one of {-1 (deletion), 0 (NOP), +1 (insertion)}. Otherwise, the sequence - // of updates contains multiple updates of the same kind and we assert for - // that case. - SmallDenseMap, int, 4> Operations; - Operations.reserve(AllUpdates.size()); - - for (const auto &U : AllUpdates) { - NodePtr From = U.getFrom(); - NodePtr To = U.getTo(); - if (IsPostDom) std::swap(From, To); // Reverse edge for postdominators. - - Operations[{From, To}] += (U.getKind() == UpdateKind::Insert ? 1 : -1); - } - - Result.clear(); - Result.reserve(Operations.size()); - for (auto &Op : Operations) { - const int NumInsertions = Op.second; - assert(std::abs(NumInsertions) <= 1 && "Unbalanced operations!"); - if (NumInsertions == 0) continue; - const UpdateKind UK = - NumInsertions > 0 ? UpdateKind::Insert : UpdateKind::Delete; - Result.push_back({UK, Op.first.first, Op.first.second}); - } - - // Make the order consistent by not relying on pointer values within the - // set. Reuse the old Operations map. - // In the future, we should sort by something else to minimize the amount - // of work needed to perform the series of updates. - for (size_t i = 0, e = AllUpdates.size(); i != e; ++i) { - const auto &U = AllUpdates[i]; - if (!IsPostDom) - Operations[{U.getFrom(), U.getTo()}] = int(i); - else - Operations[{U.getTo(), U.getFrom()}] = int(i); - } - - llvm::sort(Result.begin(), Result.end(), - [&Operations](const UpdateT &A, const UpdateT &B) { - return Operations[{A.getFrom(), A.getTo()}] > - Operations[{B.getFrom(), B.getTo()}]; - }); - } - static void ApplyNextUpdate(DomTreeT &DT, BatchUpdateInfo &BUI) { assert(!BUI.Updates.empty() && "No updates to apply!"); UpdateT CurrentUpdate = BUI.Updates.pop_back_val(); - LLVM_DEBUG(dbgs() << "Applying update: " << CurrentUpdate << "\n"); + LLVM_DEBUG(dbgs() << "Applying update: "); + LLVM_DEBUG(CurrentUpdate.dump(); dbgs() << "\n"); // Move to the next snapshot of the CFG by removing the reverse-applied // current update. Since updates are performed in the same order they are Index: lib/IR/Dominators.cpp =================================================================== --- lib/IR/Dominators.cpp +++ lib/IR/Dominators.cpp @@ -67,7 +67,7 @@ template class llvm::DominatorTreeBase; // DomTreeBase template class llvm::DominatorTreeBase; // PostDomTreeBase -template struct llvm::DomTreeBuilder::Update; +template class llvm::cfg::Update; template void llvm::DomTreeBuilder::Calculate( DomTreeBuilder::BBDomTree &DT); Index: unittests/IR/DominatorTreeBatchUpdatesTest.cpp =================================================================== --- unittests/IR/DominatorTreeBatchUpdatesTest.cpp +++ unittests/IR/DominatorTreeBatchUpdatesTest.cpp @@ -58,9 +58,9 @@ {Insert, B, C}, {Insert, C, D}, {Delete, B, C}, {Insert, B, C}, {Insert, B, D}, {Delete, C, D}, {Delete, A, B}}; SmallVector Legalized; - DomSNCA::LegalizeUpdates(Updates, Legalized); + cfg::LegalizeUpdates(Updates, Legalized, false); LLVM_DEBUG(dbgs() << "Legalized updates:\t"); - LLVM_DEBUG(for (auto &U : Legalized) dbgs() << U << ", "); + LLVM_DEBUG(for (auto &U : Legalized) { U.dump(); dbgs() << ", "; }); LLVM_DEBUG(dbgs() << "\n"); EXPECT_EQ(Legalized.size(), 3UL); EXPECT_NE(llvm::find(Legalized, DomUpdate{Insert, B, C}), Legalized.end()); @@ -81,9 +81,9 @@ {Insert, B, C}, {Insert, C, D}, {Delete, B, C}, {Insert, B, C}, {Insert, B, D}, {Delete, C, D}, {Delete, A, B}}; SmallVector Legalized; - PostDomSNCA::LegalizeUpdates(Updates, Legalized); + cfg::LegalizeUpdates(Updates, Legalized, true); LLVM_DEBUG(dbgs() << "Legalized postdom updates:\t"); - LLVM_DEBUG(for (auto &U : Legalized) dbgs() << U << ", "); + LLVM_DEBUG(for (auto &U : Legalized) { U.dump(); dbgs() << ", "; }); LLVM_DEBUG(dbgs() << "\n"); EXPECT_EQ(Legalized.size(), 3UL); EXPECT_NE(llvm::find(Legalized, DomUpdate{Insert, C, B}), Legalized.end());