[GraphDiff] Make InverseGraph a property of a GraphDiff.

[asbirlea]

Summary

Treating a graph in reverse is a property of the GraphDiff and should instead be a template argument, just like IsPostDom is one for DomTrees.
If it's just an argument to all methods, we could have mismatches between the constructor of the GraphDiff which may reverse the updates when filtering them, and the calls retrieving the filtered delete/insert updates.
Also, since this will be used in IDF, where we're using a DomTree, this creates a cleaner interface for the GraphTraits to use the existing template argument of DomTreeBase.

Separate patch from the one adding GraphDiff, so get a clear diff of what changed.

llvm/trunk/include/llvm/IR/CFGDiff.h

 
 namespace llvm {
 
 // 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
 // multigraph. Added edges are pruned to be unique, and deleted edges will
 // remove all existing edges between two blocks.
-template <typename NodePtr> class GraphDiff {
+template <typename NodePtr, bool InverseGraph = false> class GraphDiff {
   using UpdateMapType = SmallDenseMap<NodePtr, SmallVector<NodePtr, 2>>;
   UpdateMapType SuccInsert;
   UpdateMapType SuccDelete;
   UpdateMapType PredInsert;
   UpdateMapType PredDelete;
   // Using a singleton empty vector for all BasicBlock requests with no
   // children.
   SmallVector<NodePtr, 1> Empty;
 
   void printMap(raw_ostream &OS, const UpdateMapType &M) const {
     for (auto Pair : M)
       for (auto Child : Pair.second) {
         OS << "(";
         Pair.first->printAsOperand(OS, false);
         OS << ", ";
         Child->printAsOperand(OS, false);
         OS << ") ";
       }
     OS << "\n";
   }
 
 public:
   GraphDiff() {}
-  GraphDiff(ArrayRef<cfg::Update<NodePtr>> Updates, bool InverseGraph = false) {
+  GraphDiff(ArrayRef<cfg::Update<NodePtr>> Updates) {
     SmallVector<cfg::Update<NodePtr>, 4> LegalizedUpdates;
     cfg::LegalizeUpdates<NodePtr>(Updates, LegalizedUpdates, InverseGraph);
     for (auto U : LegalizedUpdates) {
       if (U.getKind() == cfg::UpdateKind::Insert) {
         SuccInsert[U.getFrom()].push_back(U.getTo());
         PredInsert[U.getTo()].push_back(U.getFrom());
       } else {
         SuccDelete[U.getFrom()].push_back(U.getTo());
         PredDelete[U.getTo()].push_back(U.getFrom());
       }
     }
   }
 
-  bool ignoreChild(const NodePtr BB, NodePtr EdgeEnd, bool InverseEdge,
-                   bool InverseGraph) const {
+  bool ignoreChild(const NodePtr BB, NodePtr EdgeEnd, bool InverseEdge) const {
     auto &DeleteChildren =
         (InverseEdge != InverseGraph) ? PredDelete : SuccDelete;
     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,
-                   bool InverseGraph) const {
+  getAddedChildren(const NodePtr BB, bool InverseEdge) const {
     auto &InsertChildren =
         (InverseEdge != InverseGraph) ? PredInsert : SuccInsert;
     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());
   }
 
public:
   }
 
 #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 *> *;
+  using DataRef = const GraphDiff<BasicBlock *, InverseGraph> *;
   using NodeRef = std::pair<DataRef, BasicBlock *>;
 
   using ExistingChildIterator =
       WrappedPairNodeDataIterator<succ_iterator, NodeRef, DataRef>;
   struct DeletedEdgesFilter {
     BasicBlock *BB;
     DeletedEdgesFilter(BasicBlock *BB) : BB(BB){};
     bool operator()(NodeRef N) const {
-      return !N.first->ignoreChild(BB, N.second, false, InverseGraph);
+      return !N.first->ignoreChild(BB, N.second, false);
     }
   };
   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, false, InverseGraph);
+    auto InsertVec = N.first->getAddedChildren(N.second, false);
     // filter iterator init:
     auto firstit = make_filter_range(
         make_range<ExistingChildIterator>({succ_begin(N.second), N.first},
                                           {succ_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, InverseGraph);
+    auto InsertVec = N.first->getAddedChildren(N.second, false);
     // filter iterator init:
     auto firstit = make_filter_range(
         make_range<ExistingChildIterator>({succ_end(N.second), N.first},
                                           {succ_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 *> *;
+  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, InverseGraph);
+      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, InverseGraph);
+    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, InverseGraph);
+    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 *> *, BasicBlock *>>
+struct GraphTraits<
+    std::pair<const GraphDiff<BasicBlock *, false> *, BasicBlock *>>
     : CFGViewSuccessors<false> {};
 template <>
 struct GraphTraits<
-    std::pair<const GraphDiff<Inverse<BasicBlock *>> *, BasicBlock *>>
+    std::pair<const GraphDiff<BasicBlock *, true> *, BasicBlock *>>
     : CFGViewSuccessors<true> {};
 template <>
 struct GraphTraits<
-    std::pair<const GraphDiff<BasicBlock *> *, Inverse<BasicBlock *>>>
+    std::pair<const GraphDiff<BasicBlock *, false> *, Inverse<BasicBlock *>>>
     : CFGViewPredecessors<false> {};
 template <>
 struct GraphTraits<
-    std::pair<const GraphDiff<Inverse<BasicBlock *>> *, Inverse<BasicBlock *>>>
+    std::pair<const GraphDiff<BasicBlock *, true> *, Inverse<BasicBlock *>>>
     : CFGViewPredecessors<true> {};
 } // end namespace llvm
 
 #endif // LLVM_IR_CFGDIFF_H