[GraphDiff] Use class method getChildren instead of GraphTraits.

[asbirlea]

Summary

Use getChildren() method in GraphDiff instead of GraphTraits.

This simplifies the code and allows for refactorigns inside GraphDiff.
All usecase need not have a light-weight/copyable range.
Clean GraphTraits implementation.

[dblaikie]

Looks good

llvm/lib/Analysis/MemorySSAUpdater.cpp

835–836

If the inverse edge part is going to be part of the "public" API, might be worth defining an enum for it, so you don't have to add a comment to every parameter like this. Fine to do that in a separate/follow-up commit.

llvm/include/llvm/Analysis/IteratedDominanceFrontier.h

ChildrenGetterTy<BasicBlock, IsPostDom>::get(const NodeRef &N) {
   using OrderedNodeTy =
       typename IDFCalculatorBase<BasicBlock, IsPostDom>::OrderedNodeTy;
 
   if (!GD) {
     auto Children = children<OrderedNodeTy>(N);
     return {Children.begin(), Children.end()};
   }
 
-  using SnapShotBBPairTy =
-      std::pair<const GraphDiff<BasicBlock *, IsPostDom> *, OrderedNodeTy>;
-
-  ChildrenTy Ret;
-  for (const auto &SnapShotBBPair : children<SnapShotBBPairTy>({GD, N}))
-    Ret.emplace_back(SnapShotBBPair.second);
-  return Ret;
+  return GD->template getChildren<IsPostDom>(N);
 }
 
 } // end of namespace IDFCalculatorDetail
 
 } // end of namespace llvm
 
 #endif

llvm/include/llvm/Analysis/MemorySSAUpdater.h

 class BranchInst;
 class DominatorTree;
 class Instruction;
 class LoopBlocksRPO;
 
 using ValueToValueMapTy = ValueMap<const Value *, WeakTrackingVH>;
 using PhiToDefMap = SmallDenseMap<MemoryPhi *, MemoryAccess *>;
 using CFGUpdate = cfg::Update<BasicBlock *>;
-using GraphDiffInvBBPair =
-    std::pair<const GraphDiff<BasicBlock *> *, Inverse<BasicBlock *>>;
 
 class MemorySSAUpdater {
 private:
   MemorySSA *MSSA;
 
   /// We use WeakVH rather than a costly deletion to deal with dangling pointers.
   /// MemoryPhis are created eagerly and sometimes get zapped shortly afterwards.
   SmallVector<WeakVH, 16> InsertedPHIs;

llvm/include/llvm/Support/CFGDiff.h

 
 // Two booleans are used to define orders in graphs:
 // InverseGraph defines when we need to reverse the whole graph and is as such
 // also equivalent to applying updates in reverse.
 // InverseEdge defines whether we want to change the edges direction. E.g., for
 // a non-inversed graph, the children are naturally the successors when
 // InverseEdge is false and the predecessors when InverseEdge is true.
 
-// We define two base clases that call into GraphDiff, one for successors
-// (CFGSuccessors), where InverseEdge is false, and one for predecessors
-// (CFGPredecessors), where InverseEdge is true.
-// FIXME: Further refactoring may merge the two base classes into a single one
-// templated / parametrized on using succ_iterator/pred_iterator and false/true
-// for the InverseEdge.
-
-// CFGViewChildren and CFGViewPredecessors, both can be parametrized to
-// consider the graph inverted or not (i.e. InverseGraph). Successors
-// implicitly has InverseEdge = false and Predecessors implicitly has
-// InverseEdge = true (see calls to GraphDiff methods in there). The GraphTraits
-// instantiations that follow define the value of InverseGraph.
-
-// GraphTraits instantiations:
-// - GraphDiff<BasicBlock *> is equivalent to InverseGraph = false
-// - GraphDiff<Inverse<BasicBlock *>> is equivalent to InverseGraph = true
-// - second pair item is BasicBlock *, then InverseEdge = false (so it inherits
-// from CFGViewChildren).
-// - second pair item is Inverse<BasicBlock *>, then InverseEdge = true (so it
-// inherits from CFGViewPredecessors).
-
-// The 4 GraphTraits are as follows:
-// 1. std::pair<const GraphDiff<BasicBlock *> *, BasicBlock *>> :
-//        CFGViewChildren<false>
-// Regular CFG, children means successors, InverseGraph = false,
-// InverseEdge = false.
-// 2. std::pair<const GraphDiff<Inverse<BasicBlock *>> *, BasicBlock *>> :
-//        CFGViewChildren<true>
-// Reverse the graph, get successors but reverse-apply updates,
-// InverseGraph = true, InverseEdge = false.
-// 3. std::pair<const GraphDiff<BasicBlock *> *, Inverse<BasicBlock *>>> :
-//        CFGViewPredecessors<false>
-// Regular CFG, reverse edges, so children mean predecessors,
-// InverseGraph = false, InverseEdge = true.
-// 4. std::pair<const GraphDiff<Inverse<BasicBlock *>> *, Inverse<BasicBlock *>>
-//        : CFGViewPredecessors<true>
-// Reverse the graph and the edges, InverseGraph = true, InverseEdge = true.
-
 namespace llvm {
 
 namespace detail {
 template <typename Range>
 auto reverse_if_helper(Range &&R, std::integral_constant<bool, false>) {
   return std::forward<Range>(R);
 }
 
 template <typename Range>
 auto reverse_if_helper(Range &&R, std::integral_constant<bool, true>) {
   return llvm::reverse(std::forward<Range>(R));
 }
 
 template <bool B, typename Range> auto reverse_if(Range &&R) {
   return reverse_if_helper(std::forward<Range>(R),
                            std::integral_constant<bool, B>{});
 }
 } // namespace detail
 
-// GraphDiff defines a CFG snapshot: given a set of Update<NodePtr>, provide
-// utilities to skip edges marked as deleted and return a set of edges marked as
-// newly inserted. The current diff treats the CFG as a graph rather than a
+// 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;
   };
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 UpdatedCFGChildren;
     for (auto Child : CurrentCFGChildren)
void print(raw_ostream &OS) const {
     printMap(OS, Edges[0].Pred);
     OS << "\n";
   }
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
   LLVM_DUMP_METHOD void dump() const { print(dbgs()); }
 #endif
 };
-
-template <typename GraphT, bool InverseGraph = false, bool InverseEdge = false,
-          typename GT = GraphTraits<GraphT>>
-struct CFGViewChildren {
-  using DataRef = const GraphDiff<typename GT::NodeRef, InverseGraph> *;
-  using NodeRef = std::pair<DataRef, typename GT::NodeRef>;
-
-  template<typename Range>
-  static auto makeChildRange(Range &&R, DataRef DR) {
-    using Iter = WrappedPairNodeDataIterator<decltype(std::forward<Range>(R).begin()), NodeRef, DataRef>;
-    return make_range(Iter(R.begin(), DR), Iter(R.end(), DR));
-  }
-
-  static auto children(NodeRef N) {
-
-    // filter iterator init:
-    auto R = make_range(GT::child_begin(N.second), GT::child_end(N.second));
-    auto RR = detail::reverse_if<!InverseEdge>(R);
-    // This lambda is copied into the iterators and persists to callers, ensure
-    // captures are by value or otherwise have sufficient lifetime.
-    auto First = make_filter_range(makeChildRange(RR, N.first), [N](NodeRef C) {
-      return !C.first->ignoreChild(N.second, C.second, InverseEdge);
-    });
-
-    // new inserts iterator init:
-    auto InsertVec = N.first->getAddedChildren(N.second, InverseEdge);
-    auto Second = makeChildRange(InsertVec, N.first);
-
-    auto CR = concat<NodeRef>(First, Second);
-
-    // concat_range contains references to other ranges, returning it would
-    // leave those references dangling - the iterators contain
-    // other iterators by value so they're safe to return.
-    return make_range(CR.begin(), CR.end());
-  }
-
-  static auto child_begin(NodeRef N) {
-    return children(N).begin();
-  }
-
-  static auto child_end(NodeRef N) {
-    return children(N).end();
-  }
-
-  using ChildIteratorType = decltype(child_end(std::declval<NodeRef>()));
-};
-
-template <typename T, bool B>
-struct GraphTraits<std::pair<const GraphDiff<T, B> *, T>>
-    : CFGViewChildren<T, B> {};
-template <typename T, bool B>
-struct GraphTraits<std::pair<const GraphDiff<T, B> *, Inverse<T>>>
-    : CFGViewChildren<Inverse<T>, B, true> {};
 } // end namespace llvm
 
 #endif // LLVM_SUPPORT_CFGDIFF_H

llvm/lib/Analysis/MemorySSAUpdater.cpp

while (true) {
       MemorySSA::DefsList *Defs = MSSA->getWritableBlockDefs(BB);
       // Return last Def or Phi in BB, if it exists.
       if (Defs)
         return &*(--Defs->end());
 
       // Check number of predecessors, we only care if there's more than one.
       unsigned Count = 0;
       BasicBlock *Pred = nullptr;
-      for (auto &Pair : children<GraphDiffInvBBPair>({GD, BB})) {
-        Pred = Pair.second;
+      for (auto *Pi : GD->template getChildren</*InverseEdge=*/true>(BB)) {
+        Pred = Pi;
         Count++;
         if (Count == 2)
           break;
       }
 
       // If BB has multiple predecessors, get last definition from IDom.
       if (Count != 1) {
         // [SimpleLoopUnswitch] If BB is a dead block, about to be deleted, its
void MemorySSAUpdater::applyInsertUpdates(ArrayRef<CFGUpdate> Updates,
 
   // Store all existing predecessor for each BB, at least one must exist.
   SmallDenseMap<std::pair<BasicBlock *, BasicBlock *>, int> EdgeCountMap;
   SmallPtrSet<BasicBlock *, 2> NewBlocks;
   for (auto &BBPredPair : PredMap) {
     auto *BB = BBPredPair.first;
     const auto &AddedBlockSet = BBPredPair.second.Added;
     auto &PrevBlockSet = BBPredPair.second.Prev;
-    for (auto &Pair : children<GraphDiffInvBBPair>({GD, BB})) {
-      BasicBlock *Pi = Pair.second;
+    for (auto *Pi : GD->template getChildren</*InverseEdge=*/true>(BB)) {
       if (!AddedBlockSet.count(Pi))
         PrevBlockSet.insert(Pi);
       EdgeCountMap[{Pi, BB}]++;
     }
 
     if (PrevBlockSet.empty()) {
       assert(pred_size(BB) == AddedBlockSet.size() && "Duplicate edges added.");
       LLVM_DEBUG(
for (auto *BBIDF : IDFBlocks) {
       auto *IDFPhi = MSSA->getMemoryAccess(BBIDF);
       assert(IDFPhi && "Phi must exist");
       if (!PhisToFill.count(IDFPhi)) {
         // Update existing Phi.
         // FIXME: some updates may be redundant, try to optimize and skip some.
         for (unsigned I = 0, E = IDFPhi->getNumIncomingValues(); I < E; ++I)
           IDFPhi->setIncomingValue(I, GetLastDef(IDFPhi->getIncomingBlock(I)));
       } else {
-        for (auto &Pair : children<GraphDiffInvBBPair>({GD, BBIDF})) {
-          BasicBlock *Pi = Pair.second;
+        for (auto *Pi : GD->template getChildren</*InverseEdge=*/true>(BBIDF))
           IDFPhi->addIncoming(GetLastDef(Pi), Pi);
-        }
-      }
-    }
-  }
 
   // Now for all defs in BlocksWithDefsToReplace, if there are uses they no
   // longer dominate, replace those with the closest dominating def.
   // This will also update optimized accesses, as they're also uses.
   for (auto *BlockWithDefsToReplace : BlocksWithDefsToReplace) {
     if (auto DefsList = MSSA->getWritableBlockDefs(BlockWithDefsToReplace)) {
       for (auto &DefToReplaceUses : *DefsList) {
         BasicBlock *DominatingBlock = DefToReplaceUses.getBlock();