diff --git a/llvm/include/llvm/IR/Dominators.h b/llvm/include/llvm/IR/Dominators.h --- a/llvm/include/llvm/IR/Dominators.h +++ b/llvm/include/llvm/IR/Dominators.h @@ -44,6 +44,9 @@ using BBUpdates = ArrayRef>; +using BBDomTreeGraphDiff = GraphDiff; +using BBPostDomTreeGraphDiff = GraphDiff; + extern template void Calculate(BBDomTree &DT); extern template void CalculateWithUpdates(BBDomTree &DT, BBUpdates U); @@ -62,8 +65,10 @@ BasicBlock *From, BasicBlock *To); -extern template void ApplyUpdates(BBDomTree &DT, BBUpdates); -extern template void ApplyUpdates(BBPostDomTree &DT, BBUpdates); +extern template void ApplyUpdates(BBDomTree &DT, + BBDomTreeGraphDiff &); +extern template void ApplyUpdates(BBPostDomTree &DT, + BBPostDomTreeGraphDiff &); extern template bool Verify(const BBDomTree &DT, BBDomTree::VerificationLevel VL); diff --git a/llvm/include/llvm/Support/CFGDiff.h b/llvm/include/llvm/Support/CFGDiff.h --- a/llvm/include/llvm/Support/CFGDiff.h +++ b/llvm/include/llvm/Support/CFGDiff.h @@ -194,6 +194,23 @@ #endif }; +namespace detail { +template +auto reverse_if_helper(Range &&R, std::integral_constant) { + return std::forward(R); +} + +template +auto reverse_if_helper(Range &&R, std::integral_constant) { + return llvm::reverse(std::forward(R)); +} + +template auto reverse_if(Range &&R) { + return reverse_if_helper(std::forward(R), + std::integral_constant{}); +} +} // namespace detail + template > struct CFGViewChildren { @@ -210,9 +227,10 @@ // filter iterator init: auto R = make_range(GT::child_begin(N.second), GT::child_end(N.second)); + auto RR = detail::reverse_if(R); // This lambda is copied into the iterators and persists to callers, ensure // captures are by value or otherwise have sufficient lifetime. - auto First = make_filter_range(makeChildRange(R, N.first), [N](NodeRef C) { + auto First = make_filter_range(makeChildRange(RR, N.first), [N](NodeRef C) { return !C.first->ignoreChild(N.second, C.second, InverseEdge); }); diff --git a/llvm/include/llvm/Support/GenericDomTree.h b/llvm/include/llvm/Support/GenericDomTree.h --- a/llvm/include/llvm/Support/GenericDomTree.h +++ b/llvm/include/llvm/Support/GenericDomTree.h @@ -28,6 +28,7 @@ #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallVector.h" +#include "llvm/Support/CFGDiff.h" #include "llvm/Support/CFGUpdate.h" #include "llvm/Support/raw_ostream.h" #include @@ -211,7 +212,8 @@ template void ApplyUpdates(DomTreeT &DT, - ArrayRef Updates); + GraphDiff &PreViewCFG); template bool Verify(const DomTreeT &DT, typename DomTreeT::VerificationLevel VL); @@ -535,10 +537,13 @@ /// The type of updates is the same for DomTreeBase and PostDomTreeBase /// with the same template parameter T. /// - /// \param Updates An unordered sequence of updates to perform. + /// \param Updates An unordered sequence of updates to perform. The current + /// CFG and the reverse of these updates provides the pre-view of the CFG. /// void applyUpdates(ArrayRef Updates) { - DomTreeBuilder::ApplyUpdates(*this, Updates); + GraphDiff PreViewCFG( + Updates, /*ReverseApplyUpdates=*/true); + DomTreeBuilder::ApplyUpdates(*this, PreViewCFG); } /// Inform the dominator tree about a CFG edge insertion and update the tree. diff --git a/llvm/include/llvm/Support/GenericDomTreeConstruction.h b/llvm/include/llvm/Support/GenericDomTreeConstruction.h --- a/llvm/include/llvm/Support/GenericDomTreeConstruction.h +++ b/llvm/include/llvm/Support/GenericDomTreeConstruction.h @@ -58,6 +58,7 @@ using TreeNodePtr = DomTreeNodeBase *; using RootsT = decltype(DomTreeT::Roots); static constexpr bool IsPostDom = DomTreeT::IsPostDominator; + using GraphDiffT = GraphDiff; // Information record used by Semi-NCA during tree construction. struct InfoRec { @@ -77,28 +78,27 @@ using UpdateT = typename DomTreeT::UpdateType; using UpdateKind = typename DomTreeT::UpdateKind; struct BatchUpdateInfo { - SmallVector Updates; - using NodePtrAndKind = PointerIntPair; - - // In order to be able to walk a CFG that is out of sync with the CFG - // DominatorTree last knew about, use the list of updates to reconstruct - // previous CFG versions of the current CFG. For each node, we store a set - // of its virtually added/deleted future successors and predecessors. - // Note that these children are from the future relative to what the - // DominatorTree knows about -- using them to gets us some snapshot of the - // CFG from the past (relative to the state of the CFG). - DenseMap> FutureSuccessors; - DenseMap> FuturePredecessors; + // Note: Updates inside PreViewCFG are aleady legalized. + BatchUpdateInfo(GraphDiffT &PreViewCFG) + : PreViewCFG(PreViewCFG), + NumLegalized(PreViewCFG.getNumLegalizedUpdates()) {} + // Remembers if the whole tree was recalculated at some point during the // current batch update. bool IsRecalculated = false; + GraphDiffT &PreViewCFG; + const size_t NumLegalized; }; BatchUpdateInfo *BatchUpdates; using BatchUpdatePtr = BatchUpdateInfo *; + std::unique_ptr EmptyGD; // If BUI is a nullptr, then there's no batch update in progress. - SemiNCAInfo(BatchUpdatePtr BUI) : BatchUpdates(BUI) {} + SemiNCAInfo(BatchUpdatePtr BUI) : BatchUpdates(BUI) { + if (!BatchUpdates) + EmptyGD = std::make_unique(); + } void clear() { NumToNode = {nullptr}; // Restore to initial state with a dummy start node. @@ -107,8 +107,7 @@ // in progress, we need this information to continue it. } - template - struct ChildrenGetter { + template struct ChildrenGetter { using ResultTy = SmallVector; static ResultTy Get(NodePtr N, std::integral_constant) { @@ -121,49 +120,23 @@ return ResultTy(IChildren.begin(), IChildren.end()); } - using Tag = std::integral_constant; + using Tag = std::integral_constant; // The function below is the core part of the batch updater. It allows the // Depth Based Search algorithm to perform incremental updates in lockstep // with updates to the CFG. We emulated lockstep CFG updates by getting its // next snapshots by reverse-applying future updates. static ResultTy Get(NodePtr N, BatchUpdatePtr BUI) { - ResultTy Res = Get(N, Tag()); - // If there's no batch update in progress, simply return node's children. - if (!BUI) return Res; - - // CFG children are actually its *most current* children, and we have to - // reverse-apply the future updates to get the node's children at the - // point in time the update was performed. - auto &FutureChildren = (Inverse != IsPostDom) ? BUI->FuturePredecessors - : BUI->FutureSuccessors; - auto FCIt = FutureChildren.find(N); - if (FCIt == FutureChildren.end()) return Res; - - for (auto ChildAndKind : FCIt->second) { - const NodePtr Child = ChildAndKind.getPointer(); - const UpdateKind UK = ChildAndKind.getInt(); - - // Reverse-apply the future update. - if (UK == UpdateKind::Insert) { - // If there's an insertion in the future, it means that the edge must - // exist in the current CFG, but was not present in it before. - assert(llvm::find(Res, Child) != Res.end() - && "Expected child not found in the CFG"); - Res.erase(std::remove(Res.begin(), Res.end(), Child), Res.end()); - LLVM_DEBUG(dbgs() << "\tHiding edge " << BlockNamePrinter(N) << " -> " - << BlockNamePrinter(Child) << "\n"); - } else { - // If there's an deletion in the future, it means that the edge cannot - // exist in the current CFG, but existed in it before. - assert(llvm::find(Res, Child) == Res.end() && - "Unexpected child found in the CFG"); - LLVM_DEBUG(dbgs() << "\tShowing virtual edge " << BlockNamePrinter(N) - << " -> " << BlockNamePrinter(Child) << "\n"); - Res.push_back(Child); - } - } - + if (!BUI) + return Get(N, Tag()); + + ResultTy Res; + using DirectedNodeT = + std::conditional_t, NodePtr>; + using GraphDiffBBPair = std::pair; + const auto *GD = &BUI->PreViewCFG; + for (auto &Pair : children({GD, N})) + Res.push_back(Pair.second); return Res; } }; @@ -233,8 +206,7 @@ NumToNode.push_back(BB); constexpr bool Direction = IsReverse != IsPostDom; // XOR. - for (const NodePtr Succ : - ChildrenGetter::Get(BB, BatchUpdates)) { + for (const NodePtr Succ : ChildrenGetter::Get(BB, BatchUpdates)) { const auto SIT = NodeToInfo.find(Succ); // Don't visit nodes more than once but remember to collect // ReverseChildren. @@ -1005,15 +977,14 @@ const TreeNodePtr TN) { LLVM_DEBUG(dbgs() << "IsReachableFromIDom " << BlockNamePrinter(TN) << "\n"); - for (const NodePtr Pred : - ChildrenGetter::Get(TN->getBlock(), BUI)) { + auto TNB = TN->getBlock(); + for (const NodePtr Pred : ChildrenGetter::Get(TNB, BUI)) { LLVM_DEBUG(dbgs() << "\tPred " << BlockNamePrinter(Pred) << "\n"); if (!DT.getNode(Pred)) continue; - const NodePtr Support = - DT.findNearestCommonDominator(TN->getBlock(), Pred); + const NodePtr Support = DT.findNearestCommonDominator(TNB, Pred); LLVM_DEBUG(dbgs() << "\tSupport " << BlockNamePrinter(Support) << "\n"); - if (Support != TN->getBlock()) { + if (Support != TNB) { LLVM_DEBUG(dbgs() << "\t" << BlockNamePrinter(TN) << " is reachable from support " << BlockNamePrinter(Support) << "\n"); @@ -1144,53 +1115,23 @@ //===--------------------- DomTree Batch Updater --------------------------=== //~~ - static void ApplyUpdates(DomTreeT &DT, ArrayRef Updates) { - const size_t NumUpdates = Updates.size(); + static void ApplyUpdates(DomTreeT &DT, GraphDiffT &PreViewCFG) { + const size_t NumUpdates = PreViewCFG.getNumLegalizedUpdates(); if (NumUpdates == 0) return; // Take the fast path for a single update and avoid running the batch update // machinery. if (NumUpdates == 1) { - const auto &Update = Updates.front(); + UpdateT Update = PreViewCFG.popUpdateForIncrementalUpdates(); if (Update.getKind() == UpdateKind::Insert) - DT.insertEdge(Update.getFrom(), Update.getTo()); + InsertEdge(DT, /*BUI=*/nullptr, Update.getFrom(), Update.getTo()); else - DT.deleteEdge(Update.getFrom(), Update.getTo()); - + DeleteEdge(DT, /*BUI=*/nullptr, Update.getFrom(), Update.getTo()); return; } - BatchUpdateInfo BUI; - LLVM_DEBUG(dbgs() << "Legalizing " << BUI.Updates.size() << " updates\n"); - cfg::LegalizeUpdates(Updates, BUI.Updates, IsPostDom); - - const size_t NumLegalized = BUI.Updates.size(); - BUI.FutureSuccessors.reserve(NumLegalized); - BUI.FuturePredecessors.reserve(NumLegalized); - - // Use the legalized future updates to initialize future successors and - // predecessors. Note that these sets will only decrease size over time, as - // the next CFG snapshots slowly approach the actual (current) CFG. - for (UpdateT &U : BUI.Updates) { - BUI.FutureSuccessors[U.getFrom()].push_back({U.getTo(), U.getKind()}); - BUI.FuturePredecessors[U.getTo()].push_back({U.getFrom(), U.getKind()}); - } - -#if 0 - // FIXME: The LLVM_DEBUG macro only plays well with a modular - // build of LLVM when the header is marked as textual, but doing - // so causes redefinition errors. - LLVM_DEBUG(dbgs() << "About to apply " << NumLegalized << " updates\n"); - LLVM_DEBUG(if (NumLegalized < 32) for (const auto &U - : reverse(BUI.Updates)) { - dbgs() << "\t"; - U.dump(); - dbgs() << "\n"; - }); - LLVM_DEBUG(dbgs() << "\n"); -#endif - + BatchUpdateInfo BUI(PreViewCFG); // Recalculate the DominatorTree when the number of updates // exceeds a threshold, which usually makes direct updating slower than // recalculation. We select this threshold proportional to the @@ -1200,21 +1141,21 @@ // Make unittests of the incremental algorithm work if (DT.DomTreeNodes.size() <= 100) { - if (NumLegalized > DT.DomTreeNodes.size()) + if (BUI.NumLegalized > DT.DomTreeNodes.size()) CalculateFromScratch(DT, &BUI); - } else if (NumLegalized > DT.DomTreeNodes.size() / 40) + } else if (BUI.NumLegalized > DT.DomTreeNodes.size() / 40) CalculateFromScratch(DT, &BUI); // If the DominatorTree was recalculated at some point, stop the batch // updates. Full recalculations ignore batch updates and look at the actual // CFG. - for (size_t i = 0; i < NumLegalized && !BUI.IsRecalculated; ++i) + for (size_t i = 0; i < BUI.NumLegalized && !BUI.IsRecalculated; ++i) ApplyNextUpdate(DT, BUI); } static void ApplyNextUpdate(DomTreeT &DT, BatchUpdateInfo &BUI) { - assert(!BUI.Updates.empty() && "No updates to apply!"); - UpdateT CurrentUpdate = BUI.Updates.pop_back_val(); + // Popping the next update, will move the PreViewCFG to the next snapshot. + UpdateT CurrentUpdate = BUI.PreViewCFG.popUpdateForIncrementalUpdates(); #if 0 // FIXME: The LLVM_DEBUG macro only plays well with a modular // build of LLVM when the header is marked as textual, but doing @@ -1223,21 +1164,6 @@ LLVM_DEBUG(CurrentUpdate.dump(); dbgs() << "\n"); #endif - // Move to the next snapshot of the CFG by removing the reverse-applied - // current update. Since updates are performed in the same order they are - // legalized it's sufficient to pop the last item here. - auto &FS = BUI.FutureSuccessors[CurrentUpdate.getFrom()]; - assert(FS.back().getPointer() == CurrentUpdate.getTo() && - FS.back().getInt() == CurrentUpdate.getKind()); - FS.pop_back(); - if (FS.empty()) BUI.FutureSuccessors.erase(CurrentUpdate.getFrom()); - - auto &FP = BUI.FuturePredecessors[CurrentUpdate.getTo()]; - assert(FP.back().getPointer() == CurrentUpdate.getFrom() && - FP.back().getInt() == CurrentUpdate.getKind()); - FP.pop_back(); - if (FP.empty()) BUI.FuturePredecessors.erase(CurrentUpdate.getTo()); - if (CurrentUpdate.getKind() == UpdateKind::Insert) InsertEdge(DT, &BUI, CurrentUpdate.getFrom(), CurrentUpdate.getTo()); else @@ -1596,19 +1522,11 @@ template void CalculateWithUpdates(DomTreeT &DT, ArrayRef Updates) { - // TODO: Move BUI creation in common method, reuse in ApplyUpdates. - typename SemiNCAInfo::BatchUpdateInfo BUI; - LLVM_DEBUG(dbgs() << "Legalizing " << BUI.Updates.size() << " updates\n"); - cfg::LegalizeUpdates(Updates, BUI.Updates, - DomTreeT::IsPostDominator); - const size_t NumLegalized = BUI.Updates.size(); - BUI.FutureSuccessors.reserve(NumLegalized); - BUI.FuturePredecessors.reserve(NumLegalized); - for (auto &U : BUI.Updates) { - BUI.FutureSuccessors[U.getFrom()].push_back({U.getTo(), U.getKind()}); - BUI.FuturePredecessors[U.getTo()].push_back({U.getFrom(), U.getKind()}); - } - + // FIXME: Updated to use the PreViewCFG and behave the same as until now. + // This behavior is however incorrect; this actually needs the PostViewCFG. + GraphDiff PreViewCFG( + Updates, /*ReverseApplyUpdates=*/true); + typename SemiNCAInfo::BatchUpdateInfo BUI(PreViewCFG); SemiNCAInfo::CalculateFromScratch(DT, &BUI); } @@ -1628,8 +1546,9 @@ template void ApplyUpdates(DomTreeT &DT, - ArrayRef Updates) { - SemiNCAInfo::ApplyUpdates(DT, Updates); + GraphDiff &PreViewCFG) { + SemiNCAInfo::ApplyUpdates(DT, PreViewCFG); } template diff --git a/llvm/lib/IR/Dominators.cpp b/llvm/lib/IR/Dominators.cpp --- a/llvm/lib/IR/Dominators.cpp +++ b/llvm/lib/IR/Dominators.cpp @@ -90,9 +90,10 @@ DomTreeBuilder::BBPostDomTree &DT, BasicBlock *From, BasicBlock *To); template void llvm::DomTreeBuilder::ApplyUpdates( - DomTreeBuilder::BBDomTree &DT, DomTreeBuilder::BBUpdates); + DomTreeBuilder::BBDomTree &DT, DomTreeBuilder::BBDomTreeGraphDiff &); template void llvm::DomTreeBuilder::ApplyUpdates( - DomTreeBuilder::BBPostDomTree &DT, DomTreeBuilder::BBUpdates); + DomTreeBuilder::BBPostDomTree &DT, + DomTreeBuilder::BBPostDomTreeGraphDiff &); template bool llvm::DomTreeBuilder::Verify( const DomTreeBuilder::BBDomTree &DT,