[DomTree] Extend update API to allow a post CFG view.

[asbirlea]

Summary

Extend the applyUpdates in DominatorTree to allow a post CFG view,
different from the current CFG.
This patch implements the functionality of updating an already up to
date DT, to the desired PostCFGView.
Combining a set of updates towards an up to date DT and a PostCFGView is
not yet supported.

[asbirlea]

I'm inclined to change the API to pass a second vector of updates instead of the GraphDiff directly (for the PostView), since during updates the GD gets modified and it makes sense to keep it as an internal component. Thoughts?

[kuhar]

This makes sense to me. I think the only missing piece is some documentation which also explains how to interpret when PostView is missing (PostView == nullptr ===> Current CFG is the implicit PostView?)

llvm/include/llvm/Support/GenericDomTree.h

542–547

Can you update the comment?

553

nit: early return and not else?

[asbirlea]

I made the update to keep the creation of the GD object internal to the DT. Since the GD is modified during updates, this makes the most sense to me.
I split the API to take only Updates or Updates+PostViewUpdates.

[kuhar]

llvm/include/llvm/Support/GenericDomTreeConstruction.h

567

nit: would it be possible to give it a more descriptive name? I have no idea what L stands for

[asbirlea]

llvm/include/llvm/Support/GenericDomTreeConstruction.h

567

Good point, it was meant to be L for Local :-)

[asbirlea]

Rename variable.

llvm/include/llvm/IR/Dominators.h

 
 extern template void DeleteEdge<BBDomTree>(BBDomTree &DT, BasicBlock *From,
                                            BasicBlock *To);
 extern template void DeleteEdge<BBPostDomTree>(BBPostDomTree &DT,
                                                BasicBlock *From,
                                                BasicBlock *To);
 
 extern template void ApplyUpdates<BBDomTree>(BBDomTree &DT,
-                                             BBDomTreeGraphDiff &);
+                                             BBDomTreeGraphDiff &,
+                                             BBDomTreeGraphDiff *);
 extern template void ApplyUpdates<BBPostDomTree>(BBPostDomTree &DT,
-                                                 BBPostDomTreeGraphDiff &);
+                                                 BBPostDomTreeGraphDiff &,
+                                                 BBPostDomTreeGraphDiff *);
 
 extern template bool Verify<BBDomTree>(const BBDomTree &DT,
                                        BBDomTree::VerificationLevel VL);
 extern template bool Verify<BBPostDomTree>(const BBPostDomTree &DT,
                                            BBPostDomTree::VerificationLevel VL);
 }  // namespace DomTreeBuilder
 
 using DomTreeNode = DomTreeNodeBase<BasicBlock>;

llvm/include/llvm/Support/GenericDomTree.h

 
 template <typename DomTreeT>
 void DeleteEdge(DomTreeT &DT, typename DomTreeT::NodePtr From,
                 typename DomTreeT::NodePtr To);
 
 template <typename DomTreeT>
 void ApplyUpdates(DomTreeT &DT,
                   GraphDiff<typename DomTreeT::NodePtr,
-                            DomTreeT::IsPostDominator> &PreViewCFG);
+                            DomTreeT::IsPostDominator> &PreViewCFG,
+                  GraphDiff<typename DomTreeT::NodePtr,
+                            DomTreeT::IsPostDominator> *PostViewCFG);
 
 template <typename DomTreeT>
 bool Verify(const DomTreeT &DT, typename DomTreeT::VerificationLevel VL);
 }  // namespace DomTreeBuilder
 
 /// Core dominator tree base class.
 ///
 /// This class is a generic template over graph nodes. It is instantiated for
#endif
   /// cases.
   ///
   /// Note that for postdominators it automatically takes care of applying
   /// updates on reverse edges internally (so there's no need to swap the
   /// From and To pointers when constructing DominatorTree::UpdateType).
   /// The type of updates is the same for DomTreeBase<T> and PostDomTreeBase<T>
   /// with the same template parameter T.
   ///
   /// \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<UpdateType> Updates) {
     GraphDiff<NodePtr, IsPostDominator> 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<UpdateType> Updates,
+                    ArrayRef<UpdateType> PostViewUpdates) {
+    // GraphDiff<NodePtr, IsPostDom> *PostViewCFG = nullptr) {
+    if (Updates.empty()) {
+      GraphDiff<NodePtr, IsPostDom> 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.
   ///
   /// This function has to be called just before or just after making the update
   /// on the actual CFG. There cannot be any other updates that the dominator
   /// tree doesn't know about.
   ///

llvm/include/llvm/Support/GenericDomTreeConstruction.h

struct SemiNCAInfo {
   // a dummy element.
   std::vector<NodePtr> NumToNode = {nullptr};
   DenseMap<NodePtr, InfoRec> NodeToInfo;
 
   using UpdateT = typename DomTreeT::UpdateType;
   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;
   };
 
   BatchUpdateInfo *BatchUpdates;
   using BatchUpdatePtr = BatchUpdateInfo *;
 
   // If BUI is a nullptr, then there's no batch update in progress.
   SemiNCAInfo(BatchUpdatePtr BUI) : BatchUpdates(BUI) {}
void doFullDFSWalk(const DomTreeT &DT, DescendCondition DC) {
     unsigned Num = 1;
     for (const NodePtr Root : DT.Roots) Num = runDFS(Root, Num, DC, 0);
   }
 
   static void CalculateFromScratch(DomTreeT &DT, BatchUpdatePtr BUI) {
     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);
     if (BUI) {
       BUI->IsRecalculated = true;
       LLVM_DEBUG(
           dbgs() << "DomTree recalculated, skipping future batch updates\n");
     }
static void EraseNode(DomTreeT &DT, const TreeNodePtr TN) {
 
     DT.DomTreeNodes.erase(TN->getBlock());
   }
 
   //~~
   //===--------------------- 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;
 
     // Take the fast path for a single update and avoid running the batch update
     // machinery.
     if (NumUpdates == 1) {
       UpdateT Update = PreViewCFG.popUpdateForIncrementalUpdates();
+      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
     // size of the DominatorTree. The constant is selected
     // by choosing the one with an acceptable performance on some real-world
     // inputs.
 
     // Make unittests of the incremental algorithm work
void DeleteEdge(DomTreeT &DT, typename DomTreeT::NodePtr From,
                 typename DomTreeT::NodePtr To) {
   if (DT.isPostDominator()) std::swap(From, To);
   SemiNCAInfo<DomTreeT>::DeleteEdge(DT, nullptr, From, To);
 }
 
 template <class DomTreeT>
 void ApplyUpdates(DomTreeT &DT,
                   GraphDiff<typename DomTreeT::NodePtr,
-                            DomTreeT::IsPostDominator> &PreViewCFG) {
-  SemiNCAInfo<DomTreeT>::ApplyUpdates(DT, PreViewCFG);
+                            DomTreeT::IsPostDominator> &PreViewCFG,
+                  GraphDiff<typename DomTreeT::NodePtr,
+                            DomTreeT::IsPostDominator> *PostViewCFG) {
+  SemiNCAInfo<DomTreeT>::ApplyUpdates(DT, PreViewCFG, PostViewCFG);
 }
 
 template <class DomTreeT>
 bool Verify(const DomTreeT &DT, typename DomTreeT::VerificationLevel VL) {
   SemiNCAInfo<DomTreeT> SNCA(nullptr);
 
   // Simplist check is to compare against a new tree. This will also
   // usefully print the old and new trees, if they are different.

llvm/lib/Analysis/MemorySSAUpdater.cpp

void MemorySSAUpdater::updateExitBlocksForClonedLoop(
   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> DeleteUpdates;
+  SmallVector<CFGUpdate, 4> RevDeleteUpdates;
   SmallVector<CFGUpdate, 4> 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<BasicBlock *> GD(DeleteUpdates, /*ReverseApplyUpdates=*/true);
-    applyInsertUpdates(InsertUpdates, NewDT, &GD);
+    SmallVector<CFGUpdate, 0> 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<BasicBlock *> 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<BasicBlock *> GD;
     applyInsertUpdates(InsertUpdates, DT, &GD);
   }
 
   // Update for deleted edges
   for (auto &Update : DeleteUpdates)
     removeEdge(Update.getFrom(), Update.getTo());

llvm/lib/IR/Dominators.cpp

template void llvm::DomTreeBuilder::InsertEdge<DomTreeBuilder::BBPostDomTree>(
     DomTreeBuilder::BBPostDomTree &DT, BasicBlock *From, BasicBlock *To);
 
 template void llvm::DomTreeBuilder::DeleteEdge<DomTreeBuilder::BBDomTree>(
     DomTreeBuilder::BBDomTree &DT, BasicBlock *From, BasicBlock *To);
 template void llvm::DomTreeBuilder::DeleteEdge<DomTreeBuilder::BBPostDomTree>(
     DomTreeBuilder::BBPostDomTree &DT, BasicBlock *From, BasicBlock *To);
 
 template void llvm::DomTreeBuilder::ApplyUpdates<DomTreeBuilder::BBDomTree>(
-    DomTreeBuilder::BBDomTree &DT, DomTreeBuilder::BBDomTreeGraphDiff &);
+    DomTreeBuilder::BBDomTree &DT, DomTreeBuilder::BBDomTreeGraphDiff &,
+    DomTreeBuilder::BBDomTreeGraphDiff *);
 template void llvm::DomTreeBuilder::ApplyUpdates<DomTreeBuilder::BBPostDomTree>(
-    DomTreeBuilder::BBPostDomTree &DT,
-    DomTreeBuilder::BBPostDomTreeGraphDiff &);
+    DomTreeBuilder::BBPostDomTree &DT, DomTreeBuilder::BBPostDomTreeGraphDiff &,
+    DomTreeBuilder::BBPostDomTreeGraphDiff *);
 
 template bool llvm::DomTreeBuilder::Verify<DomTreeBuilder::BBDomTree>(
     const DomTreeBuilder::BBDomTree &DT,
     DomTreeBuilder::BBDomTree::VerificationLevel VL);
 template bool llvm::DomTreeBuilder::Verify<DomTreeBuilder::BBPostDomTree>(
     const DomTreeBuilder::BBPostDomTree &DT,
     DomTreeBuilder::BBPostDomTree::VerificationLevel VL);