diff --git a/llvm/include/llvm/IR/CFGDiff.h b/llvm/include/llvm/IR/CFGDiff.h --- a/llvm/include/llvm/IR/CFGDiff.h +++ b/llvm/include/llvm/IR/CFGDiff.h @@ -78,13 +78,25 @@ // remove all existing edges between two blocks. template class GraphDiff { using UpdateMapType = SmallDenseMap>; - 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 Empty; + SmallVector 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, 4> LegalizedUpdates; void printMap(raw_ostream &OS, const UpdateMapType &M) const { for (auto Pair : M) @@ -99,24 +111,53 @@ } public: - GraphDiff() {} - GraphDiff(ArrayRef> Updates) { - SmallVector, 4> LegalizedUpdates; - cfg::LegalizeUpdates(Updates, LegalizedUpdates, InverseGraph); + GraphDiff() : UpdatedAreReverseApplied(false) {} + GraphDiff(ArrayRef> Updates, + bool ReverseApplyUpdates = false) { + cfg::LegalizeUpdates(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 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; @@ -127,7 +168,7 @@ iterator_range::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()); @@ -139,13 +180,13 @@ "===== (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"; } @@ -181,6 +222,7 @@ auto Second = makeChildRange(InsertVec, N.first); auto CR = concat(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. diff --git a/llvm/include/llvm/Support/CFGUpdate.h b/llvm/include/llvm/Support/CFGUpdate.h --- a/llvm/include/llvm/Support/CFGUpdate.h +++ b/llvm/include/llvm/Support/CFGUpdate.h @@ -62,7 +62,7 @@ template void LegalizeUpdates(ArrayRef> AllUpdates, SmallVectorImpl> &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 @@ -104,11 +104,11 @@ Operations[{U.getTo(), U.getFrom()}] = int(i); } - llvm::sort(Result, - [&Operations](const Update &A, const Update &B) { - return Operations[{A.getFrom(), A.getTo()}] > - Operations[{B.getFrom(), B.getTo()}]; - }); + llvm::sort(Result, [&](const Update &A, const Update &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 diff --git a/llvm/lib/Analysis/MemorySSAUpdater.cpp b/llvm/lib/Analysis/MemorySSAUpdater.cpp --- a/llvm/lib/Analysis/MemorySSAUpdater.cpp +++ b/llvm/lib/Analysis/MemorySSAUpdater.cpp @@ -781,24 +781,24 @@ void MemorySSAUpdater::applyUpdates(ArrayRef Updates, DominatorTree &DT) { - SmallVector RevDeleteUpdates; + SmallVector DeleteUpdates; SmallVector 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 GD(RevDeleteUpdates); + DominatorTree NewDT(DT, DeleteUpdates); + GraphDiff GD(DeleteUpdates, /*ReverseApplyUpdates=*/true); applyInsertUpdates(InsertUpdates, NewDT, &GD); } else { GraphDiff GD; @@ -806,7 +806,7 @@ } // Update for deleted edges - for (auto &Update : RevDeleteUpdates) + for (auto &Update : DeleteUpdates) removeEdge(Update.getFrom(), Update.getTo()); }