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 @@ -66,9 +66,11 @@ BasicBlock *To); extern template void ApplyUpdates(BBDomTree &DT, - BBDomTreeGraphDiff &); + BBDomTreeGraphDiff &, + BBDomTreeGraphDiff *); extern template void ApplyUpdates(BBPostDomTree &DT, - BBPostDomTreeGraphDiff &); + BBPostDomTreeGraphDiff &, + BBPostDomTreeGraphDiff *); extern template bool Verify(const BBDomTree &DT, BBDomTree::VerificationLevel VL); 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 @@ -213,7 +213,9 @@ template void ApplyUpdates(DomTreeT &DT, GraphDiff &PreViewCFG); + DomTreeT::IsPostDominator> &PreViewCFG, + GraphDiff *PostViewCFG); template bool Verify(const DomTreeT &DT, typename DomTreeT::VerificationLevel VL); @@ -543,7 +545,30 @@ void applyUpdates(ArrayRef Updates) { GraphDiff PreViewCFG( Updates, /*ReverseApplyUpdates=*/true); - DomTreeBuilder::ApplyUpdates(*this, PreViewCFG); + DomTreeBuilder::ApplyUpdates(*this, PreViewCFG, nullptr); + } + + /// \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. + /// \param PostViewUpdates An unordered sequence of update to perform in order + /// to obtain a post-view of the CFG. The DT will be updates assuming the + /// obtained PostViewCFG is the desired end state. + void applyUpdates(ArrayRef Updates, + ArrayRef PostViewUpdates) { + // GraphDiff *PostViewCFG = nullptr) { + if (Updates.empty()) { + GraphDiff PostViewCFG(PostViewUpdates); + DomTreeBuilder::ApplyUpdates(*this, PostViewCFG, &PostViewCFG); + } else { + // TODO: + // PreViewCFG needs to merge Updates and PostViewCFG. The updates in + // Updates need to be reversed, and match the direction in PostViewCFG. + // Normally, a PostViewCFG is created without reversing updates, so one + // of the internal vectors needs reversing in order to do the + // legalization of the merged vector of updates. + llvm_unreachable("Currently unsupported to update given a set of " + "updates towards a PostView"); + } } /// 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 @@ -79,14 +79,15 @@ using UpdateKind = typename DomTreeT::UpdateKind; struct BatchUpdateInfo { // Note: Updates inside PreViewCFG are aleady legalized. - BatchUpdateInfo(GraphDiffT &PreViewCFG) - : PreViewCFG(PreViewCFG), + BatchUpdateInfo(GraphDiffT &PreViewCFG, GraphDiffT *PostViewCFG = nullptr) + : PreViewCFG(PreViewCFG), PostViewCFG(PostViewCFG), NumLegalized(PreViewCFG.getNumLegalizedUpdates()) {} // Remembers if the whole tree was recalculated at some point during the // current batch update. bool IsRecalculated = false; GraphDiffT &PreViewCFG; + GraphDiffT *PostViewCFG; const size_t NumLegalized; }; @@ -560,12 +561,21 @@ auto *Parent = DT.Parent; DT.reset(); DT.Parent = Parent; - SemiNCAInfo SNCA(nullptr); // Since we are rebuilding the whole tree, - // there's no point doing it incrementally. + // If the update is using the actual CFG, BUI is null. If it's using a view, + // BUI is non-null and the PreCFGView is used. When calculating from + // scratch, make the PreViewCFG equal to the PostCFGView, so Post is used. + BatchUpdatePtr PostViewBUI = nullptr; + if (BUI && BUI->PostViewCFG) { + BUI->PreViewCFG = *BUI->PostViewCFG; + PostViewBUI = BUI; + } + // This is rebuilding the whole tree, not incrementally, but PostViewBUI is + // used in case the caller needs a DT update with a CFGView. + SemiNCAInfo SNCA(PostViewBUI); // Step #0: Number blocks in depth-first order and initialize variables used // in later stages of the algorithm. - DT.Roots = FindRoots(DT, nullptr); + DT.Roots = FindRoots(DT, PostViewBUI); SNCA.doFullDFSWalk(DT, AlwaysDescend); SNCA.runSemiNCA(DT); @@ -1139,7 +1149,10 @@ //===--------------------- DomTree Batch Updater --------------------------=== //~~ - static void ApplyUpdates(DomTreeT &DT, GraphDiffT &PreViewCFG) { + static void ApplyUpdates(DomTreeT &DT, GraphDiffT &PreViewCFG, + GraphDiffT *PostViewCFG) { + // Note: the PostViewCFG is only used when computing from scratch. It's data + // should already included in the PreViewCFG for incremental updates. const size_t NumUpdates = PreViewCFG.getNumLegalizedUpdates(); if (NumUpdates == 0) return; @@ -1148,14 +1161,22 @@ // machinery. if (NumUpdates == 1) { UpdateT Update = PreViewCFG.popUpdateForIncrementalUpdates(); - if (Update.getKind() == UpdateKind::Insert) - InsertEdge(DT, /*BUI=*/nullptr, Update.getFrom(), Update.getTo()); - else - DeleteEdge(DT, /*BUI=*/nullptr, Update.getFrom(), Update.getTo()); + if (!PostViewCFG) { + if (Update.getKind() == UpdateKind::Insert) + InsertEdge(DT, /*BUI=*/nullptr, Update.getFrom(), Update.getTo()); + else + DeleteEdge(DT, /*BUI=*/nullptr, Update.getFrom(), Update.getTo()); + } else { + BatchUpdateInfo BUI(*PostViewCFG, PostViewCFG); + if (Update.getKind() == UpdateKind::Insert) + InsertEdge(DT, &BUI, Update.getFrom(), Update.getTo()); + else + DeleteEdge(DT, &BUI, Update.getFrom(), Update.getTo()); + } return; } - BatchUpdateInfo BUI(PreViewCFG); + BatchUpdateInfo BUI(PreViewCFG, PostViewCFG); // 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 @@ -1571,8 +1592,10 @@ template void ApplyUpdates(DomTreeT &DT, GraphDiff &PreViewCFG) { - SemiNCAInfo::ApplyUpdates(DT, PreViewCFG); + DomTreeT::IsPostDominator> &PreViewCFG, + GraphDiff *PostViewCFG) { + SemiNCAInfo::ApplyUpdates(DT, PreViewCFG, PostViewCFG); } template 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 @@ -783,24 +783,32 @@ void MemorySSAUpdater::applyUpdates(ArrayRef Updates, DominatorTree &DT) { SmallVector DeleteUpdates; + SmallVector RevDeleteUpdates; SmallVector InsertUpdates; for (auto &Update : Updates) { if (Update.getKind() == DT.Insert) InsertUpdates.push_back({DT.Insert, Update.getFrom(), Update.getTo()}); - else + else { DeleteUpdates.push_back({DT.Delete, Update.getFrom(), Update.getTo()}); + RevDeleteUpdates.push_back({DT.Insert, Update.getFrom(), Update.getTo()}); + } } 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, DeleteUpdates); - GraphDiff GD(DeleteUpdates, /*ReverseApplyUpdates=*/true); - applyInsertUpdates(InsertUpdates, NewDT, &GD); + SmallVector Empty; + // Deletes are reversed applied, because this CFGView is pretending the + // deletes did not happen yet, hence the edges still exist. + DT.applyUpdates(Empty, RevDeleteUpdates); + + // Note: the MSSA update below doesn't distinguish between a GD with + // (RevDelete,false) and (Delete, true), but this matters for the DT + // updates above; for "children" purposes they are equivalent; but the + // updates themselves convey the desired update, used inside DT only. + GraphDiff GD(RevDeleteUpdates); + applyInsertUpdates(InsertUpdates, DT, &GD); + // Update DT to redelete edges; this matches the real CFG so we can perform + // the standard update without a postview of the CFG. + DT.applyUpdates(DeleteUpdates); } else { GraphDiff GD; applyInsertUpdates(InsertUpdates, DT, &GD); 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,10 +90,11 @@ DomTreeBuilder::BBPostDomTree &DT, BasicBlock *From, BasicBlock *To); template void llvm::DomTreeBuilder::ApplyUpdates( - DomTreeBuilder::BBDomTree &DT, DomTreeBuilder::BBDomTreeGraphDiff &); + DomTreeBuilder::BBDomTree &DT, DomTreeBuilder::BBDomTreeGraphDiff &, + DomTreeBuilder::BBDomTreeGraphDiff *); template void llvm::DomTreeBuilder::ApplyUpdates( - DomTreeBuilder::BBPostDomTree &DT, - DomTreeBuilder::BBPostDomTreeGraphDiff &); + DomTreeBuilder::BBPostDomTree &DT, DomTreeBuilder::BBPostDomTreeGraphDiff &, + DomTreeBuilder::BBPostDomTreeGraphDiff *); template bool llvm::DomTreeBuilder::Verify( const DomTreeBuilder::BBDomTree &DT,