[GraphDiff] Extend GraphDiff to track a list of updates.

[asbirlea]

Summary

This patch includes two extensions:

1. It extends the GraphDiff to also keep the original list of updates

after legalization, not just the deletes/insert vectors.
It also provides an API to pop the first update (the updates are store
in reverse, such that the first update is at the end of the list)

2. It adds a bool to mark whether the given updates should be applied as

given, or applied in reverse. This moves the task of reversing the
updates (when the caller needs this) to a functionality inside
GraphDiff, versus having the caller do this.

The two changes could be split into two patches, but they seemed
reasonably small to be reviewed together.

[asbirlea]

clang-format.

[kuhar]

LGTM

llvm/include/llvm/IR/CFGDiff.h

83

nit: to apply these updates forward/as-is/...?

94–99

I don't think it makes any difference whatsoever, but maybe set the size to 0 here? There's a SmallVector specialization for that case.

130

auto?

135

nit: getNumLegalizedUpdates

llvm/include/llvm/Support/CFGUpdate.h

106–107

nit: this if-else spans 13 lines, consider adding braces

107

nit: this looks weird; did clang-format split it like this?

[dblaikie]

llvm/include/llvm/IR/CFGDiff.h

80–91

Perhaps making a struct { Succ, Pred } & then you could even have an array of [2] of these and index into it with isInsert, so delete ones are at index zero and the succeess ones are at index 1. Could make the existing code and the new use of these maps a bit tidier (that if/else around line 156 -separates the initialization from the declarations and duplicates a fair bit of text between the two sides, making it less obvious what's different on either side)

llvm/include/llvm/Support/CFGUpdate.h

106–112

I'd /probably/ rephrase this as:

sort(Result, [&] (...) {
  const auto &OpA = Operations...;
  const auto &OpB = ...;
  return ReverseResultOrder ? OpA < OpB
       OpA > OpB;
});

Or something roughly like that - as it'd make it easier to see the difference between the two cases rather than trying to look at two blocks of very similar code and spot the </> difference in amongst all the other content.

[dblaikie]

Should this have any tests (unit or otherwise)?

[asbirlea]

Address comments.
Update condition to filter nullptr in clang.

[dblaikie]

llvm/include/llvm/IR/CFGDiff.h

139

These two variables are uninitialized & used later, guess the uses should be changed to Edges[IsInsert], etc...

(or since they're used in a few places, you could: const auto &E = Edges[IsInsert]; .... E.Pred(..), E.Succ(...))

[asbirlea]

Address comment. Thanks for noticing!

[dblaikie]

Sounds good :)

llvm/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, bool InverseGraph = false> class GraphDiff {
   using UpdateMapType = SmallDenseMap<NodePtr, SmallVector<NodePtr, 2>>;
-  UpdateMapType SuccInsert;
-  UpdateMapType SuccDelete;
-  UpdateMapType PredInsert;
-  UpdateMapType PredDelete;
+  struct EdgesInsertedDeleted {
+    UpdateMapType Succ;
+    UpdateMapType Pred;
+  };
+  // Store Deleted edges on position 0, and Inserted edges on position 1.
+  EdgesInsertedDeleted Edges[2];
+  // 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, 1> Empty;
+  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) {
         OS << "(";
         Pair.first->printAsOperand(OS, false);
         OS << ", ";
         Child->printAsOperand(OS, false);
         OS << ") ";
       }
     OS << "\n";
   }
 
 public:
-  GraphDiff() {}
-  GraphDiff(ArrayRef<cfg::Update<NodePtr>> Updates) {
-    SmallVector<cfg::Update<NodePtr>, 4> LegalizedUpdates;
-    cfg::LegalizeUpdates<NodePtr>(Updates, LegalizedUpdates, InverseGraph);
+  GraphDiff() : UpdatedAreReverseApplied(false) {}
+  GraphDiff(ArrayRef<cfg::Update<NodePtr>> Updates,
+            bool ReverseApplyUpdates = false) {
+    cfg::LegalizeUpdates<NodePtr>(Updates, LegalizedUpdates, InverseGraph,
+                                  /*ReverseResultOrder=*/true);
+    // The legalized updates are stored in reverse so we can pop_back when doing
+    // incremental updates.
     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());
-      }
-    }
+      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());
+    }
+    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()];
+    assert(SuccList.back() == U.getTo());
+    SuccList.pop_back();
+    if (SuccList.empty())
+      Edges[IsInsert].Succ.erase(U.getFrom());
+
+    auto &PredList = Edges[IsInsert].Pred[U.getTo()];
+    assert(PredList.back() == U.getFrom());
+    PredList.pop_back();
+    if (PredList.empty())
+      Edges[IsInsert].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) ? PredDelete : SuccDelete;
+        (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) ? PredInsert : SuccInsert;
+        (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());
   }
 
   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, SuccInsert);
+    printMap(OS, Edges[1].Succ);
     OS << "Children to delete:\n\t";
-    printMap(OS, SuccDelete);
+    printMap(OS, Edges[0].Succ);
     OS << "Inverse_children to insert:\n\t";
-    printMap(OS, PredInsert);
+    printMap(OS, Edges[1].Pred);
     OS << "Inverse_children to delete:\n\t";
-    printMap(OS, PredDelete);
+    printMap(OS, Edges[0].Pred);
     OS << "\n";
   }
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
   LLVM_DUMP_METHOD void dump() const { print(dbgs()); }
 #endif
 };
 
auto First = make_filter_range(makeChildRange(R, 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();

llvm/include/llvm/Support/CFGUpdate.h

 // 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.
 template <typename NodePtr>
 void LegalizeUpdates(ArrayRef<Update<NodePtr>> AllUpdates,
                      SmallVectorImpl<Update<NodePtr>> &Result,
-                     bool InverseGraph) {
+                     bool InverseGraph, bool ReverseResultOrder = false) {
   // 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());
 
void LegalizeUpdates(ArrayRef<Update<NodePtr>> AllUpdates,
   // 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 (!InverseGraph)
       Operations[{U.getFrom(), U.getTo()}] = int(i);
     else
       Operations[{U.getTo(), U.getFrom()}] = int(i);
   }
 
-  llvm::sort(Result,
-             [&Operations](const Update<NodePtr> &A, const Update<NodePtr> &B) {
-               return Operations[{A.getFrom(), A.getTo()}] >
-                      Operations[{B.getFrom(), B.getTo()}];
-             });
+  llvm::sort(Result, [&](const Update<NodePtr> &A, const Update<NodePtr> &B) {
+    const auto &OpA = Operations[{A.getFrom(), A.getTo()}];
+    const auto &OpB = Operations[{B.getFrom(), B.getTo()}];
+    return ReverseResultOrder ? OpA < OpB : OpA > OpB;
 }
 
 } // end namespace cfg
 } // end namespace llvm
 
 #endif // LLVM_SUPPORT_CFGUPDATE_H

llvm/lib/Analysis/MemorySSAUpdater.cpp

using MappedIteratorType =
                       decltype(GetPtr)>;
   auto MapBegin = MappedIteratorType(VMaps.begin(), GetPtr);
   auto MapEnd = MappedIteratorType(VMaps.end(), GetPtr);
   privateUpdateExitBlocksForClonedLoop(ExitBlocks, MapBegin, MapEnd, DT);
 }
 
 void MemorySSAUpdater::applyUpdates(ArrayRef<CFGUpdate> Updates,
                                     DominatorTree &DT) {
-  SmallVector<CFGUpdate, 4> RevDeleteUpdates;
+  SmallVector<CFGUpdate, 4> DeleteUpdates;
   SmallVector<CFGUpdate, 4> InsertUpdates;
   for (auto &Update : Updates) {
     if (Update.getKind() == DT.Insert)
       InsertUpdates.push_back({DT.Insert, Update.getFrom(), Update.getTo()});
     else
-      RevDeleteUpdates.push_back({DT.Insert, Update.getFrom(), Update.getTo()});
+      DeleteUpdates.push_back({DT.Delete, Update.getFrom(), Update.getTo()});
   }
 
-  if (!RevDeleteUpdates.empty()) {
+  if (!DeleteUpdates.empty()) {
     // Update for inserted edges: use newDT and snapshot CFG as if deletes had
     // not occurred.
     // FIXME: This creates a new DT, so it's more expensive to do mix
     // delete/inserts vs just inserts. We can do an incremental update on the DT
     // to revert deletes, than re-delete the edges. Teaching DT to do this, is
     // part of a pending cleanup.
-    DominatorTree NewDT(DT, RevDeleteUpdates);
-    GraphDiff<BasicBlock *> GD(RevDeleteUpdates);
+    DominatorTree NewDT(DT, DeleteUpdates);
+    GraphDiff<BasicBlock *> GD(DeleteUpdates, /*ReverseApplyUpdates=*/true);
     applyInsertUpdates(InsertUpdates, NewDT, &GD);
   } else {
     GraphDiff<BasicBlock *> GD;
     applyInsertUpdates(InsertUpdates, DT, &GD);
   }
 
   // Update for deleted edges
-  for (auto &Update : RevDeleteUpdates)
+  for (auto &Update : DeleteUpdates)
     removeEdge(Update.getFrom(), Update.getTo());
 }
 
 void MemorySSAUpdater::applyInsertUpdates(ArrayRef<CFGUpdate> Updates,
                                           DominatorTree &DT) {
   GraphDiff<BasicBlock *> GD;
   applyInsertUpdates(Updates, DT, &GD);
 }