[DomTree] Cleanup Update and LegalizeUpdate API moved to Support header.

[asbirlea]

Summary

Clean-up following D50479.
Make Update and LegalizeUpdate refer to the utilities in Support/CFGUpdate.

[kuhar]

LGTM

include/llvm/IR/Dominators.h

 class Instruction;
 class Module;
 class raw_ostream;
 
 extern template class DomTreeNodeBase<BasicBlock>;
 extern template class DominatorTreeBase<BasicBlock, false>; // DomTree
 extern template class DominatorTreeBase<BasicBlock, true>; // PostDomTree
 
+extern template class cfg::Update<BasicBlock *>;
+
 namespace DomTreeBuilder {
 using BBDomTree = DomTreeBase<BasicBlock>;
 using BBPostDomTree = PostDomTreeBase<BasicBlock>;
 
-extern template struct Update<BasicBlock *>;
-
-using BBUpdates = ArrayRef<Update<BasicBlock *>>;
+using BBUpdates = ArrayRef<llvm::cfg::Update<BasicBlock *>>;
 
 extern template void Calculate<BBDomTree>(BBDomTree &DT);
 extern template void Calculate<BBPostDomTree>(BBPostDomTree &DT);
 
 extern template void InsertEdge<BBDomTree>(BBDomTree &DT, BasicBlock *From,
                                            BasicBlock *To);
 extern template void InsertEdge<BBPostDomTree>(BBPostDomTree &DT,
                                                BasicBlock *From,

include/llvm/Support/GenericDomTree.h

 ///
 /// FIXME: Maybe GenericDomTree needs a TreeTraits, instead of GraphTraits.
 ///
 //===----------------------------------------------------------------------===//
 
 #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 <algorithm>
 #include <cassert>
 #include <cstddef>
 #include <iterator>
 #include <memory>
 #include <type_traits>
 #include <utility>
 #include <vector>
-#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 {
 
 template <typename NodeT, bool IsPostDom>
 class DominatorTreeBase;
 
 namespace DomTreeBuilder {
 template <typename DomTreeT>

 template <typename DomTreeT>
 void InsertEdge(DomTreeT &DT, typename DomTreeT::NodePtr From,
                 typename DomTreeT::NodePtr To);
 
 template <typename DomTreeT>
 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 <typename NodePtr>
-struct Update {
-  using NodeKindPair = PointerIntPair<NodePtr, 1, UpdateKind>;
-
-  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 <typename DomTreeT>
 void ApplyUpdates(DomTreeT &DT,
                   ArrayRef<typename DomTreeT::UpdateType> Updates);
 
 template <typename DomTreeT>
 bool Verify(const DomTreeT &DT, typename DomTreeT::VerificationLevel VL);
 }  // namespace DomTreeBuilder
 
public:
   using NodeType = NodeT;
   using NodePtr = NodeT *;
   using ParentPtr = decltype(std::declval<NodeT *>()->getParent());
   static_assert(std::is_pointer<ParentPtr>::value,
                 "Currently NodeT's parent must be a pointer type");
   using ParentType = typename std::remove_pointer<ParentPtr>::type;
   static constexpr bool IsPostDominator = IsPostDom;
 
-  using UpdateType = DomTreeBuilder::Update<NodePtr>;
-  using UpdateKind = DomTreeBuilder::UpdateKind;
+  using UpdateType = cfg::Update<NodePtr>;
+  using UpdateKind = cfg::UpdateKind;
   static constexpr UpdateKind Insert = UpdateKind::Insert;
   static constexpr UpdateKind Delete = UpdateKind::Delete;
 
   enum class VerificationLevel { Fast, Basic, Full };
 
 protected:
   // Dominators always have a single root, postdominators can have more.
   SmallVector<NodeT *, IsPostDom ? 4 : 1> Roots;

include/llvm/Support/GenericDomTreeConstruction.h

struct SemiNCAInfo {
   };
 
   // Number to node mapping is 1-based. Initialize the mapping to start with
   // a dummy element.
   std::vector<NodePtr> NumToNode = {nullptr};
   DenseMap<NodePtr, InfoRec> NodeToInfo;
 
   using UpdateT = typename DomTreeT::UpdateType;
+  using UpdateKind = typename DomTreeT::UpdateKind;
   struct BatchUpdateInfo {
     SmallVector<UpdateT, 4> Updates;
     using NodePtrAndKind = PointerIntPair<NodePtr, 1, UpdateKind>;
 
     // In order to be able to walk a CFG that is out of sync with the CFG
     // DominatorTree last knew about, use the list of updates to reconstruct
     // previous CFG versions of the current CFG. For each node, we store a set
     // of its virtually added/deleted future successors and predecessors.
if (NumUpdates == 1) {
         DT.insertEdge(Update.getFrom(), Update.getTo());
       else
         DT.deleteEdge(Update.getFrom(), Update.getTo());
 
       return;
     }
 
     BatchUpdateInfo BUI;
-    LegalizeUpdates(Updates, BUI.Updates);
+    LLVM_DEBUG(dbgs() << "Legalizing " << BUI.Updates.size() << " updates\n");
+    cfg::LegalizeUpdates<NodePtr>(Updates, BUI.Updates, IsPostDom);
 
     const size_t NumLegalized = BUI.Updates.size();
     BUI.FutureSuccessors.reserve(NumLegalized);
     BUI.FuturePredecessors.reserve(NumLegalized);
 
     // Use the legalized future updates to initialize future successors and
     // predecessors. Note that these sets will only decrease size over time, as
     // the next CFG snapshots slowly approach the actual (current) CFG.
     for (UpdateT &U : BUI.Updates) {
       BUI.FutureSuccessors[U.getFrom()].push_back({U.getTo(), U.getKind()});
       BUI.FuturePredecessors[U.getTo()].push_back({U.getFrom(), U.getKind()});
     }
 
     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
     // updates. Full recalculations ignore batch updates and look at the actual
     // CFG.
     for (size_t i = 0; i < NumLegalized && !BUI.IsRecalculated; ++i)
       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<UpdateT> AllUpdates,
-                              SmallVectorImpl<UpdateT> &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<std::pair<NodePtr, NodePtr>, 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
     // legalized it's sufficient to pop the last item here.
     auto &FS = BUI.FutureSuccessors[CurrentUpdate.getFrom()];
     assert(FS.back().getPointer() == CurrentUpdate.getTo() &&
            FS.back().getInt() == CurrentUpdate.getKind());
     FS.pop_back();

lib/IR/Dominators.cpp

 // GenericDomTreeConstruction.h.
 //
 //===----------------------------------------------------------------------===//
 
 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 class llvm::cfg::Update<BasicBlock *>;
 
 template void llvm::DomTreeBuilder::Calculate<DomTreeBuilder::BBDomTree>(
     DomTreeBuilder::BBDomTree &DT);
 template void llvm::DomTreeBuilder::Calculate<DomTreeBuilder::BBPostDomTree>(
     DomTreeBuilder::BBPostDomTree &DT);
 
 template void llvm::DomTreeBuilder::InsertEdge<DomTreeBuilder::BBDomTree>(
     DomTreeBuilder::BBDomTree &DT, BasicBlock *From, BasicBlock *To);

unittests/IR/DominatorTreeBatchUpdatesTest.cpp

TEST(DominatorTreeBatchUpdates, LegalizeDomUpdates) {
   BasicBlock *B = Builder.getOrAddBlock("B");
   BasicBlock *C = Builder.getOrAddBlock("C");
   BasicBlock *D = Builder.getOrAddBlock("D");
 
   std::vector<DomUpdate> Updates = {
       {Insert, B, C}, {Insert, C, D}, {Delete, B, C}, {Insert, B, C},
       {Insert, B, D}, {Delete, C, D}, {Delete, A, B}};
   SmallVector<DomUpdate, 4> Legalized;
-  DomSNCA::LegalizeUpdates(Updates, Legalized);
+  cfg::LegalizeUpdates<BasicBlock *>(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());
   EXPECT_NE(llvm::find(Legalized, DomUpdate{Insert, B, D}), Legalized.end());
   EXPECT_NE(llvm::find(Legalized, DomUpdate{Delete, A, B}), Legalized.end());
 }
 
 TEST(DominatorTreeBatchUpdates, LegalizePostDomUpdates) {
   CFGHolder Holder;
   CFGBuilder Builder(Holder.F, {{"A", "B"}}, {});
 
   BasicBlock *A = Builder.getOrAddBlock("A");
   BasicBlock *B = Builder.getOrAddBlock("B");
   BasicBlock *C = Builder.getOrAddBlock("C");
   BasicBlock *D = Builder.getOrAddBlock("D");
 
   std::vector<DomUpdate> Updates = {
       {Insert, B, C}, {Insert, C, D}, {Delete, B, C}, {Insert, B, C},
       {Insert, B, D}, {Delete, C, D}, {Delete, A, B}};
   SmallVector<DomUpdate, 4> Legalized;
-  PostDomSNCA::LegalizeUpdates(Updates, Legalized);
+  cfg::LegalizeUpdates<BasicBlock *>(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());
   EXPECT_NE(llvm::find(Legalized, DomUpdate{Insert, D, B}), Legalized.end());
   EXPECT_NE(llvm::find(Legalized, DomUpdate{Delete, B, A}), Legalized.end());
 }
 
 TEST(DominatorTreeBatchUpdates, SingleInsertion) {