[CFGDiff] Refactor Succ/Pred maps.

[asbirlea]

Summary

Refactor Succ/Pred maps to have a single map lookup when constructing
children. The preivous desing made sense when used by GraphTraits.
This more closely matches the previous approach in DomTree.

[dblaikie]

llvm/include/llvm/Support/CFGDiff.h

81

Should this 0 be IsInsert?

122–131

1 - IsInsert might be more clearly written as !IsInsert or IsInsert == false? (I'd tend towards the ! notation myself, but I understand the == false notation might be a bit more legible/clear/harder-to-miss)

148–150

I think we've probably got a utility for erase+remove in STLExtras.h?

[asbirlea]

Address comments.

[dblaikie]

Looks good!

llvm/include/llvm/ADT/STLExtras.h

 ///
 /// This version works for any container with an erase method call accepting
 /// two iterators.
 template <typename Container, typename UnaryPredicate>
 void erase_if(Container &C, UnaryPredicate P) {
   C.erase(remove_if(C, P), C.end());
 }
 
+/// Wrapper function to remove a value from a container:
+///
+/// C.erase(remove(C.begin(), C.end(), V), C.end());
+template <typename Container, typename ValueType>
+void erase_value(Container &C, ValueType V) {
+  C.erase(std::remove(C.begin(), C.end(), V), C.end());
+}
+
 /// Given a sequence container Cont, replace the range [ContIt, ContEnd) with
 /// the range [ValIt, ValEnd) (which is not from the same container).
 template<typename Container, typename RandomAccessIterator>
 void replace(Container &Cont, typename Container::iterator ContIt,
              typename Container::iterator ContEnd, RandomAccessIterator ValIt,
              RandomAccessIterator ValEnd) {
   while (true) {
     if (ValIt == ValEnd) {

llvm/include/llvm/Support/CFGDiff.h

 } // namespace detail
 
 // GraphDiff defines a CFG snapshot: given a set of Update<NodePtr>, provides
 // a getChildren method to get a Node's children based on the additional updates
 // in the snapshot. The current diff treats the CFG as a graph rather than a
 // multigraph. Added edges are pruned to be unique, and deleted edges will
 // remove all existing edges between two blocks.
 template <typename NodePtr, bool InverseGraph = false> class GraphDiff {
-  using UpdateMapType = SmallDenseMap<NodePtr, SmallVector<NodePtr, 2>>;
-  struct EdgesInsertedDeleted {
-    UpdateMapType Succ;
-    UpdateMapType Pred;
-  };
-  // Store Deleted edges on position 0, and Inserted edges on position 1.
-  EdgesInsertedDeleted Edges[2];
+  struct DeletesInserts {
+    SmallVector<NodePtr, 2> DI[2];
+  };
+  using UpdateMapType = SmallDenseMap<NodePtr, DeletesInserts>;
+
   // By default, it is assumed that, given a CFG and a set of updates, we wish
   // to apply these updates as given. If UpdatedAreReverseApplied is set, the
   // updates will be applied in reverse: deleted edges are considered re-added
   // and inserted edges are considered deleted when returning children.
   bool UpdatedAreReverseApplied;
-  // Using a singleton empty vector for all node requests with no
-  // children.
-  SmallVector<NodePtr, 0> Empty;
 
   // Keep the list of legalized updates for a deterministic order of updates
   // when using a GraphDiff for incremental updates in the DominatorTree.
   // The list is kept in reverse to allow popping from end.
   SmallVector<cfg::Update<NodePtr>, 4> LegalizedUpdates;
 
   void printMap(raw_ostream &OS, const UpdateMapType &M) const {
-    for (auto Pair : M)
-      for (auto Child : Pair.second) {
+    StringRef DIText[2] = {"Delete", "Insert"};
+    for (auto Pair : M) {
+      for (unsigned IsInsert = 0; IsInsert <= 1; ++IsInsert) {
+        OS << DIText[IsInsert] << " edges: \n";
+        for (auto Child : Pair.second.DI[IsInsert]) {
           OS << "(";
           Pair.first->printAsOperand(OS, false);
           OS << ", ";
           Child->printAsOperand(OS, false);
           OS << ") ";
         }
+      }
+    }
     OS << "\n";
   }
 
 public:
   GraphDiff() : UpdatedAreReverseApplied(false) {}
   GraphDiff(ArrayRef<cfg::Update<NodePtr>> Updates,
             bool ReverseApplyUpdates = false) {
     cfg::LegalizeUpdates<NodePtr>(Updates, LegalizedUpdates, InverseGraph);
-    // The legalized updates are stored in reverse so we can pop_back when doing
-    // incremental updates.
     for (auto U : LegalizedUpdates) {
       unsigned IsInsert =
           (U.getKind() == cfg::UpdateKind::Insert) == !ReverseApplyUpdates;
-      Edges[IsInsert].Succ[U.getFrom()].push_back(U.getTo());
-      Edges[IsInsert].Pred[U.getTo()].push_back(U.getFrom());
+      Succ[U.getFrom()].DI[IsInsert].push_back(U.getTo());
+      Pred[U.getTo()].DI[IsInsert].push_back(U.getFrom());
     }
     UpdatedAreReverseApplied = ReverseApplyUpdates;
   }
 
   auto getLegalizedUpdates() const {
     return make_range(LegalizedUpdates.begin(), LegalizedUpdates.end());
   }
 
   unsigned getNumLegalizedUpdates() const { return LegalizedUpdates.size(); }
 
   cfg::Update<NodePtr> popUpdateForIncrementalUpdates() {
     assert(!LegalizedUpdates.empty() && "No updates to apply!");
     auto U = LegalizedUpdates.pop_back_val();
     unsigned IsInsert =
         (U.getKind() == cfg::UpdateKind::Insert) == !UpdatedAreReverseApplied;
-    auto &SuccList = Edges[IsInsert].Succ[U.getFrom()];
+    auto &SuccDIList = Succ[U.getFrom()];
+    auto &SuccList = SuccDIList.DI[IsInsert];
     assert(SuccList.back() == U.getTo());
     SuccList.pop_back();
-    if (SuccList.empty())
-      Edges[IsInsert].Succ.erase(U.getFrom());
+    if (SuccList.empty() && SuccDIList.DI[!IsInsert].empty())
+      Succ.erase(U.getFrom());
 
-    auto &PredList = Edges[IsInsert].Pred[U.getTo()];
+    auto &PredDIList = Pred[U.getTo()];
+    auto &PredList = PredDIList.DI[IsInsert];
     assert(PredList.back() == U.getFrom());
     PredList.pop_back();
-    if (PredList.empty())
-      Edges[IsInsert].Pred.erase(U.getTo());
+    if (PredList.empty() && PredDIList.DI[!IsInsert].empty())
+      Pred.erase(U.getTo());
     return U;
   }
 
-  bool ignoreChild(const NodePtr BB, NodePtr EdgeEnd, bool InverseEdge) const {
-    // Used to filter nullptr in clang.
-    if (EdgeEnd == nullptr)
-      return true;
-    auto &DeleteChildren =
-        (InverseEdge != InverseGraph) ? Edges[0].Pred : Edges[0].Succ;
-    auto It = DeleteChildren.find(BB);
-    if (It == DeleteChildren.end())
-      return false;
-    auto &EdgesForBB = It->second;
-    return llvm::find(EdgesForBB, EdgeEnd) != EdgesForBB.end();
-  }
-
-  iterator_range<typename SmallVectorImpl<NodePtr>::const_iterator>
-  getAddedChildren(const NodePtr BB, bool InverseEdge) const {
-    auto &InsertChildren =
-        (InverseEdge != InverseGraph) ? Edges[1].Pred : Edges[1].Succ;
-    auto It = InsertChildren.find(BB);
-    if (It == InsertChildren.end())
-      return make_range(Empty.begin(), Empty.end());
-    return make_range(It->second.begin(), It->second.end());
-  }
-
   using VectRet = SmallVector<NodePtr, 8>;
   template <bool InverseEdge> VectRet getChildren(NodePtr N) const {
     using DirectedNodeT =
         std::conditional_t<InverseEdge, Inverse<NodePtr>, NodePtr>;
     auto R = children<DirectedNodeT>(N);
-    auto CurrentCFGChildren = detail::reverse_if<!InverseEdge>(R);
+    VectRet Res = VectRet(detail::reverse_if<!InverseEdge>(R));
+
+    // Remove nullptr children for clang.
+    llvm::erase_value(Res, nullptr);
+
+    auto &Children = (InverseEdge != InverseGraph) ? Pred : Succ;
+    auto It = Children.find(N);
+    if (It == Children.end())
+      return Res;
+
+    // Remove children present in the CFG but not in the snapshot.
+    for (auto *Child : It->second.DI[0])
+      llvm::erase_value(Res, Child);
+
+    // Add children present in the snapshot for not in the real CFG.
+    auto &AddedChildren = It->second.DI[1];
+    Res.insert(Res.end(), AddedChildren.begin(), AddedChildren.end());
 
-    VectRet UpdatedCFGChildren;
-    for (auto Child : CurrentCFGChildren)
-      if (Child && !ignoreChild(N, Child, InverseEdge))
-        UpdatedCFGChildren.push_back(Child);
-
-    auto AddedCFGChildren = getAddedChildren(N, InverseEdge);
-    UpdatedCFGChildren.insert(UpdatedCFGChildren.end(),
-                              AddedCFGChildren.begin(), AddedCFGChildren.end());
-    return UpdatedCFGChildren;
+    return Res;
   }
 
   void print(raw_ostream &OS) const {
     OS << "===== GraphDiff: CFG edge changes to create a CFG snapshot. \n"
           "===== (Note: notion of children/inverse_children depends on "
           "the direction of edges and the graph.)\n";
-    OS << "Children to insert:\n\t";
-    printMap(OS, Edges[1].Succ);
-    OS << "Children to delete:\n\t";
-    printMap(OS, Edges[0].Succ);
-    OS << "Inverse_children to insert:\n\t";
-    printMap(OS, Edges[1].Pred);
-    OS << "Inverse_children to delete:\n\t";
-    printMap(OS, Edges[0].Pred);
+    OS << "Children to delete/insert:\n\t";
+    printMap(OS, Succ);
+    OS << "Inverse_children to delete/insert:\n\t";
+    printMap(OS, Pred);
     OS << "\n";
   }
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
   LLVM_DUMP_METHOD void dump() const { print(dbgs()); }
 #endif
 };
 } // end namespace llvm
 
 #endif // LLVM_SUPPORT_CFGDIFF_H