[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

86

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

92

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.

131

auto?

136

nit: getNumLegalizedUpdates

llvm/include/llvm/Support/CFGUpdate.h

107–109

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

108

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

[dblaikie]

llvm/include/llvm/IR/CFGDiff.h

81–89

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

107–120

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

140

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

 //===- CFGDiff.h - Define a CFG snapshot. -----------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //

 
 // 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;
+  // By default, it is assumed that, given a CFG and a set of updates, we wish
+  // to apply these updates. 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;
 
+  // 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) {
+      bool isInsert = (U.getKind() == cfg::UpdateKind::Insert) == !ReverseApplyUpdates;
+      if (isInsert) {
         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());
       }
     }
+    UpdatedAreReverseApplied = ReverseApplyUpdates;
+  }
+
+  iterator_range<typename SmallVectorImpl<cfg::Update<NodePtr>>::const_iterator>
+  getLegalizedUpdates() const {
+    return make_range(LegalizedUpdates.begin(), LegalizedUpdates.end());
+  }
+
+  unsigned getNoLegalizedUpdates() const { return LegalizedUpdates.size(); }
+
+  cfg::Update<NodePtr> popUpdateForIncrementalUpdates() {
+    assert(!LegalizedUpdates.empty() && "No updates to apply!");
+    auto U = LegalizedUpdates.pop_back_val();
+    UpdateMapType *SuccMap, *PredMap;
+    bool isInsert =
+        (U.getKind() == cfg::UpdateKind::Insert) == !UpdatedAreReverseApplied;
+    if (isInsert) {
+      SuccMap = &SuccInsert;
+      PredMap = &PredInsert;
+    } else {
+      SuccMap = &SuccDelete;
+      PredMap = &PredDelete;
+    }
+    auto &SuccList = (*SuccMap)[U.getFrom()];
+    assert(SuccList.back() == U.getTo());
+    SuccList.pop_back();
+    if (SuccList.empty())
+      SuccMap->erase(U.getFrom());
+
+    auto &PredList = (*PredMap)[U.getTo()];
+    assert(PredList.back() == U.getFrom());
+    PredList.pop_back();
+    if (PredList.empty())
+      PredMap->erase(U.getTo());
+    return U;
   }
 
   bool ignoreChild(const NodePtr BB, NodePtr EdgeEnd, bool InverseEdge) const {
+    // Used to filter nullptr in clang.
+    if (BB == nullptr)
+      return true;
     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();
   }

llvm/include/llvm/Support/CFGUpdate.h

 //===- CFGUpdate.h - Encode a CFG Edge Update. ------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //

 // 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,
   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,
+  if (!ReverseResultOrder)
+    llvm::
+        sort(Result,
              [&Operations](const Update<NodePtr> &A, const Update<NodePtr> &B) {
                return Operations[{A.getFrom(), A.getTo()}] >
                       Operations[{B.getFrom(), B.getTo()}];
              });
+  else
+    llvm::sort(Result, [&Operations](const Update<NodePtr> &A,
+                                     const Update<NodePtr> &B) {
+      return Operations[{A.getFrom(), A.getTo()}] <
+             Operations[{B.getFrom(), B.getTo()}];
+    });
 }
 
 } // end namespace cfg
 } // end namespace llvm
 
 #endif // LLVM_SUPPORT_CFGUPDATE_H

llvm/lib/Analysis/MemorySSAUpdater.cpp

 //===-- MemorySSAUpdater.cpp - Memory SSA Updater--------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------===//
 //
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);
 }