[DominatorTree] Add support for mixed pre/post CFG views.

[asbirlea]

Summary

Add support for mixed pre/post CFG views.

Update usages of the MemorySSAUpdater to use the new DT API by
requesting the DT updates to be done by the MSSAUpdater.

[kuhar]

llvm/include/llvm/Analysis/MemorySSAUpdater.h

122–126

What happens when it's false? My immediate thought would be: will the DT remain unmodified and assumed up to date?

llvm/include/llvm/Support/GenericDomTree.h

566

nit: drop the size parameter and let SmallVector pick it for you?
https://llvm.org/docs/ProgrammersManual.html#llvm-adt-smallvector-h

llvm/lib/Analysis/MemorySSAUpdater.cpp

831

Does this do anything if the update vector is Empty?

llvm/lib/Transforms/Utils/LoopRotationUtils.cpp

509

nit: add braces around the else body

[asbirlea]

Address comments.

[kuhar]

LGTM

llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp

862

nit: also add braces here

llvm/include/llvm/Analysis/MemorySSAUpdater.h

public:
   /// that were not cloned don't have additional predecessors added.
   void updateExitBlocksForClonedLoop(ArrayRef<BasicBlock *> ExitBlocks,
                                      const ValueToValueMapTy &VMap,
                                      DominatorTree &DT);
   void updateExitBlocksForClonedLoop(
       ArrayRef<BasicBlock *> ExitBlocks,
       ArrayRef<std::unique_ptr<ValueToValueMapTy>> VMaps, DominatorTree &DT);
 
-  /// Apply CFG updates, analogous with the DT edge updates.
-  void applyUpdates(ArrayRef<CFGUpdate> Updates, DominatorTree &DT);
+  /// Apply CFG updates, analogous with the DT edge updates. By default, the
+  /// DT is assumed to be already up to date. If UpdateDTFirst is true, first
+  /// update the DT with the same updates.
+  void applyUpdates(ArrayRef<CFGUpdate> Updates, DominatorTree &DT,
+                    bool UpdateDTFirst = false);
   /// Apply CFG insert updates, analogous with the DT edge updates.
   void applyInsertUpdates(ArrayRef<CFGUpdate> Updates, DominatorTree &DT);
 
   void moveBefore(MemoryUseOrDef *What, MemoryUseOrDef *Where);
   void moveAfter(MemoryUseOrDef *What, MemoryUseOrDef *Where);
   void moveToPlace(MemoryUseOrDef *What, BasicBlock *BB,
                    MemorySSA::InsertionPlace Where);
   /// `From` block was spliced into `From` and `To`. There is a CFG edge from

llvm/include/llvm/Support/GenericDomTree.h

void applyUpdates(ArrayRef<UpdateType> Updates) {
     GraphDiff<NodePtr, IsPostDominator> PreViewCFG(
         Updates, /*ReverseApplyUpdates=*/true);
     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
+  /// to obtain a post-view of the CFG. The DT will be updated assuming the
   /// obtained PostViewCFG is the desired end state.
   void applyUpdates(ArrayRef<UpdateType> Updates,
                     ArrayRef<UpdateType> PostViewUpdates) {
     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");
+      // The PostViewCFG is created with updates reversed (equivalent to changes
+      // made to the CFG), so the PreViewCFG needs all the updates reverse
+      // applied.
+      SmallVector<UpdateType> AllUpdates(Updates.begin(), Updates.end());
+      for (auto &Update : PostViewUpdates)
+        AllUpdates.push_back(Update);
+      GraphDiff<NodePtr, IsPostDom> PreViewCFG(AllUpdates,
+                                               /*ReverseApplyUpdates=*/true);
+      GraphDiff<NodePtr, IsPostDom> PostViewCFG(PostViewUpdates);
+      DomTreeBuilder::ApplyUpdates(*this, PreViewCFG, &PostViewCFG);
     }
   }
 
   /// 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/lib/Analysis/MemorySSAUpdater.cpp

using MappedIteratorType =
       mapped_iterator<const std::unique_ptr<ValueToValueMapTy> *,
                       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) {
+                                    DominatorTree &DT, bool UpdateDT) {
   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 {
       DeleteUpdates.push_back({DT.Delete, Update.getFrom(), Update.getTo()});
       RevDeleteUpdates.push_back({DT.Insert, Update.getFrom(), Update.getTo()});
     }
   }
 
   if (!DeleteUpdates.empty()) {
+    if (!UpdateDT) {
       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);
+    } else {
+      // Apply all updates, with the RevDeleteUpdates as PostCFGView.
+      DT.applyUpdates(Updates, 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 {
+    if (UpdateDT)
+      DT.applyUpdates(Updates);
     GraphDiff<BasicBlock *> GD;
     applyInsertUpdates(InsertUpdates, DT, &GD);
   }
 
   // Update for deleted edges
   for (auto &Update : DeleteUpdates)
     removeEdge(Update.getFrom(), Update.getTo());
 }

llvm/lib/Transforms/Scalar/LoopSimplifyCFG.cpp

if (Loop *OuterLoop = LI.getLoopFor(Preheader)) {
         // Some values from loops in [OuterLoop, StillReachable) could be used
         // in the current loop. Now it is not their child anymore, so such uses
         // require LCSSA Phis.
         Loop *FixLCSSALoop = OuterLoop;
         while (FixLCSSALoop->getParentLoop() != StillReachable)
           FixLCSSALoop = FixLCSSALoop->getParentLoop();
         assert(FixLCSSALoop && "Should be a loop!");
         // We need all DT updates to be done before forming LCSSA.
-        DTU.applyUpdates(DTUpdates);
         if (MSSAU)
-          MSSAU->applyUpdates(DTUpdates, DT);
+          MSSAU->applyUpdates(DTUpdates, DT, /*UpdateDT=*/true);
+        else
+          DTU.applyUpdates(DTUpdates);
         DTUpdates.clear();
         formLCSSARecursively(*FixLCSSALoop, DT, &LI, &SE);
       }
     }
 
     if (MSSAU) {
       // Clear all updates now. Facilitates deletes that follow.
-      DTU.applyUpdates(DTUpdates);
-      MSSAU->applyUpdates(DTUpdates, DT);
+      MSSAU->applyUpdates(DTUpdates, DT, /*UpdateDT=*/true);
       DTUpdates.clear();
       if (VerifyMemorySSA)
         MSSAU->getMemorySSA()->verifyMemorySSA();
     }
   }
 
   /// Delete loop blocks that have become unreachable after folding. Make all
   /// relevant updates to DT and LI.

llvm/lib/Transforms/Scalar/LoopUnswitch.cpp

if (TrueDest != OldBranchSucc)
       Updates.push_back({DominatorTree::Insert, OldBranchParent, TrueDest});
     if (FalseDest != OldBranchSucc)
       Updates.push_back({DominatorTree::Insert, OldBranchParent, FalseDest});
     // If both of the new successors are different from the old one, inform the
     // DT that the edge was deleted.
     if (OldBranchSucc != TrueDest && OldBranchSucc != FalseDest) {
       Updates.push_back({DominatorTree::Delete, OldBranchParent, OldBranchSucc});
     }
-    DT->applyUpdates(Updates);
 
     if (MSSAU)
-      MSSAU->applyUpdates(Updates, *DT);
+      MSSAU->applyUpdates(Updates, *DT, /*UpdateDT=*/true);
+    else
+      DT->applyUpdates(Updates);
   }
 
   // If either edge is critical, split it. This helps preserve LoopSimplify
   // form for enclosing loops.
   auto Options =
       CriticalEdgeSplittingOptions(DT, LI, MSSAU.get()).setPreserveLCSSA();
   SplitCriticalEdge(BI, 0, Options);
   SplitCriticalEdge(BI, 1, Options);

llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp

static bool unswitchTrivialSwitch(Loop &L, SwitchInst &SI, DominatorTree &DT,
   for (auto *UnswitchedExitBB : UnswitchedExitBBs) {
     DTUpdates.push_back({DT.Delete, ParentBB, UnswitchedExitBB});
     DTUpdates.push_back({DT.Insert, OldPH, UnswitchedExitBB});
   }
   for (auto SplitUnswitchedPair : SplitExitBBMap) {
     DTUpdates.push_back({DT.Delete, ParentBB, SplitUnswitchedPair.first});
     DTUpdates.push_back({DT.Insert, OldPH, SplitUnswitchedPair.second});
   }
-  DT.applyUpdates(DTUpdates);
 
   if (MSSAU) {
-    MSSAU->applyUpdates(DTUpdates, DT);
+    MSSAU->applyUpdates(DTUpdates, DT, /*UpdateDT=*/true);
     if (VerifyMemorySSA)
       MSSAU->getMemorySSA()->verifyMemorySSA();
-  }
+  } else
+    DT.applyUpdates(DTUpdates);
 
   assert(DT.verify(DominatorTree::VerificationLevel::Fast));
 
   // We may have changed the nesting relationship for this loop so hoist it to
   // its correct parent if needed.
   hoistLoopToNewParent(L, *NewPH, DT, LI, MSSAU, SE);
 
   if (MSSAU && VerifyMemorySSA)

llvm/lib/Transforms/Utils/LoopRotationUtils.cpp

do {
     // Inform DT about changes to the CFG.
     if (DT) {
       // The OrigPreheader branches to the NewHeader and Exit now. Then, inform
       // the DT about the removed edge to the OrigHeader (that got removed).
       SmallVector<DominatorTree::UpdateType, 3> Updates;
       Updates.push_back({DominatorTree::Insert, OrigPreheader, Exit});
       Updates.push_back({DominatorTree::Insert, OrigPreheader, NewHeader});
       Updates.push_back({DominatorTree::Delete, OrigPreheader, OrigHeader});
-      DT->applyUpdates(Updates);
 
       if (MSSAU) {
-        MSSAU->applyUpdates(Updates, *DT);
+        MSSAU->applyUpdates(Updates, *DT, /*UpdateDT=*/true);
         if (VerifyMemorySSA)
           MSSAU->getMemorySSA()->verifyMemorySSA();
+      } else {
+        DT->applyUpdates(Updates);
       }
     }
 
     // At this point, we've finished our major CFG changes.  As part of cloning
     // the loop into the preheader we've simplified instructions and the
     // duplicated conditional branch may now be branching on a constant.  If it is
     // branching on a constant and if that constant means that we enter the loop,
     // then we fold away the cond branch to an uncond branch.  This simplifies the
     // loop in cases important for nested loops, and it also means we don't have