CFGDiff: Simplify and generalize over all graph types

[dblaikie]

Summary

Use GraphTraits in the implementation of the GraphDiff's own GraphTraits
so GraphDiff can be used across all graph types that provide
GraphTraits.

Also use partial template specializations to make the traits a bit more
compact.

(I wonder if the special handling of inverted graphs can be avoided - it
adds more variations to this code than might be ideal - what's to stop
GraphDiff from not knowing anything about inversion and only using the
Inverse<T> traits to create inverses instead?)

[asbirlea]

Thanks a lot for this clean-up! I wanted to merge these since I defined them, but couldn't figure out how to do it; this is excellent! :-).

llvm/include/llvm/IR/CFGDiff.h

160

Now that the two classes are merged, could this be called CFGViewChildren?

[dblaikie]

Rename CFGViewSuccessors to CFGViewChildren

[dblaikie]

(also fixed the formatting issues the linter picked up)

llvm/include/llvm/IR/CFGDiff.h

160

Yeah, for sure! - updated to include that rename.

[asbirlea]

Thank you, again!

llvm/include/llvm/IR/CFGDiff.h

 
 // 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.
 
-// CFGViewSuccessors and CFGViewPredecessors, both can be parametrized to
+// 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 CFGViewSuccessors).
+// 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 *>> :
-//        CFGViewSuccessors<false>
+//        CFGViewChildren<false>
 // Regular CFG, children means successors, InverseGraph = false,
 // InverseEdge = false.
 // 2. std::pair<const GraphDiff<Inverse<BasicBlock *>> *, BasicBlock *>> :
-//        CFGViewSuccessors<true>
+//        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>
void print(raw_ostream &OS) const {
     OS << "\n";
   }
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
   LLVM_DUMP_METHOD void dump() const { print(dbgs()); }
 #endif
 };
 
-template <bool InverseGraph = false> struct CFGViewSuccessors {
-  using DataRef = const GraphDiff<BasicBlock *, InverseGraph> *;
+template <typename GraphT, bool InverseGraph = false, bool InverseEdge = false,
+          typename GT = GraphTraits<GraphT>>
+struct CFGViewChildren {
+  using DataRef = const GraphDiff<typename GT::NodeRef, InverseGraph> *;
+  using RawNodeRef = typename GT::NodeRef;
   using NodeRef = std::pair<DataRef, BasicBlock *>;
 
   using ExistingChildIterator =
-      WrappedPairNodeDataIterator<succ_iterator, NodeRef, DataRef>;
+      WrappedPairNodeDataIterator<typename GT::ChildIteratorType, NodeRef,
+                                  DataRef>;
   struct DeletedEdgesFilter {
-    BasicBlock *BB;
-    DeletedEdgesFilter(BasicBlock *BB) : BB(BB){};
+    RawNodeRef BB;
+    DeletedEdgesFilter(RawNodeRef BB) : BB(BB){};
     bool operator()(NodeRef N) const {
-      return !N.first->ignoreChild(BB, N.second, false);
+      return !N.first->ignoreChild(BB, N.second, InverseEdge);
     }
   };
   using FilterExistingChildrenIterator =
       filter_iterator<ExistingChildIterator, DeletedEdgesFilter>;
 
-  using vec_iterator = SmallVectorImpl<BasicBlock *>::const_iterator;
+  using vec_iterator = typename SmallVectorImpl<RawNodeRef>::const_iterator;
   using AddNewChildrenIterator =
       WrappedPairNodeDataIterator<vec_iterator, NodeRef, DataRef>;
   using ChildIteratorType =
       concat_iterator<NodeRef, FilterExistingChildrenIterator,
                       AddNewChildrenIterator>;
 
   static ChildIteratorType child_begin(NodeRef N) {
-    auto InsertVec = N.first->getAddedChildren(N.second, false);
+    auto InsertVec = N.first->getAddedChildren(N.second, InverseEdge);
     // filter iterator init:
     auto firstit = make_filter_range(
-        make_range<ExistingChildIterator>({succ_begin(N.second), N.first},
-                                          {succ_end(N.second), N.first}),
+        make_range<ExistingChildIterator>({GT::child_begin(N.second), N.first},
+                                          {GT::child_end(N.second), N.first}),
         DeletedEdgesFilter(N.second));
     // new inserts iterator init:
     auto secondit = make_range<AddNewChildrenIterator>(
         {InsertVec.begin(), N.first}, {InsertVec.end(), N.first});
 
     return concat_iterator<NodeRef, FilterExistingChildrenIterator,
                            AddNewChildrenIterator>(firstit, secondit);
   }
 
   static ChildIteratorType child_end(NodeRef N) {
-    auto InsertVec = N.first->getAddedChildren(N.second, false);
+    auto InsertVec = N.first->getAddedChildren(N.second, InverseEdge);
     // filter iterator init:
     auto firstit = make_filter_range(
-        make_range<ExistingChildIterator>({succ_end(N.second), N.first},
-                                          {succ_end(N.second), N.first}),
+        make_range<ExistingChildIterator>({GT::child_end(N.second), N.first},
+                                          {GT::child_end(N.second), N.first}),
         DeletedEdgesFilter(N.second));
     // new inserts iterator init:
     auto secondit = make_range<AddNewChildrenIterator>(
         {InsertVec.end(), N.first}, {InsertVec.end(), N.first});
 
     return concat_iterator<NodeRef, FilterExistingChildrenIterator,
                            AddNewChildrenIterator>(firstit, secondit);
   }
 };
 
-template <bool InverseGraph = false> struct CFGViewPredecessors {
-  using DataRef = const GraphDiff<BasicBlock *, InverseGraph> *;
-  using NodeRef = std::pair<DataRef, BasicBlock *>;
-
-  using ExistingChildIterator =
-      WrappedPairNodeDataIterator<pred_iterator, NodeRef, DataRef>;
-  struct DeletedEdgesFilter {
-    BasicBlock *BB;
-    DeletedEdgesFilter(BasicBlock *BB) : BB(BB){};
-    bool operator()(NodeRef N) const {
-      return !N.first->ignoreChild(BB, N.second, true);
-    }
-  };
-  using FilterExistingChildrenIterator =
-      filter_iterator<ExistingChildIterator, DeletedEdgesFilter>;
-
-  using vec_iterator = SmallVectorImpl<BasicBlock *>::const_iterator;
-  using AddNewChildrenIterator =
-      WrappedPairNodeDataIterator<vec_iterator, NodeRef, DataRef>;
-  using ChildIteratorType =
-      concat_iterator<NodeRef, FilterExistingChildrenIterator,
-                      AddNewChildrenIterator>;
-
-  static ChildIteratorType child_begin(NodeRef N) {
-    auto InsertVec = N.first->getAddedChildren(N.second, true);
-    // filter iterator init:
-    auto firstit = make_filter_range(
-        make_range<ExistingChildIterator>({pred_begin(N.second), N.first},
-                                          {pred_end(N.second), N.first}),
-        DeletedEdgesFilter(N.second));
-    // new inserts iterator init:
-    auto secondit = make_range<AddNewChildrenIterator>(
-        {InsertVec.begin(), N.first}, {InsertVec.end(), N.first});
-
-    return concat_iterator<NodeRef, FilterExistingChildrenIterator,
-                           AddNewChildrenIterator>(firstit, secondit);
-  }
-
-  static ChildIteratorType child_end(NodeRef N) {
-    auto InsertVec = N.first->getAddedChildren(N.second, true);
-    // filter iterator init:
-    auto firstit = make_filter_range(
-        make_range<ExistingChildIterator>({pred_end(N.second), N.first},
-                                          {pred_end(N.second), N.first}),
-        DeletedEdgesFilter(N.second));
-    // new inserts iterator init:
-    auto secondit = make_range<AddNewChildrenIterator>(
-        {InsertVec.end(), N.first}, {InsertVec.end(), N.first});
-
-    return concat_iterator<NodeRef, FilterExistingChildrenIterator,
-                           AddNewChildrenIterator>(firstit, secondit);
-  }
-};
-
-template <>
-struct GraphTraits<
-    std::pair<const GraphDiff<BasicBlock *, false> *, BasicBlock *>>
-    : CFGViewSuccessors<false> {};
-template <>
-struct GraphTraits<
-    std::pair<const GraphDiff<BasicBlock *, true> *, BasicBlock *>>
-    : CFGViewSuccessors<true> {};
-template <>
-struct GraphTraits<
-    std::pair<const GraphDiff<BasicBlock *, false> *, Inverse<BasicBlock *>>>
-    : CFGViewPredecessors<false> {};
-template <>
-struct GraphTraits<
-    std::pair<const GraphDiff<BasicBlock *, true> *, Inverse<BasicBlock *>>>
-    : CFGViewPredecessors<true> {};
+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_IR_CFGDIFF_H