[DomTreeUpdater] Ignore updates when both DT and PDT are nullptrs

[NutshellySima]

Summary

Previously, when both DT and PDT are nullptrs and the UpdateStrategy is Lazy, DomTreeUpdater still pends updates inside.
After this patch, DomTreeUpdater will ignore all updates from(applyUpdates()/insertEdge*()/deleteEdge*()) in this case. (call delBB() still pends BasicBlock deletion until a flush event according to the doc).
The behavior of DomTreeUpdater previously documented won't change after the patch.

[kuhar]

Have you considered detecting that both trees are null and overriding the update strategy to Eager in that case? I think that should functionally be equivalent, although more confusing when the strategy you get can be different from what someone just set :P I'm just wondering what pros/cons there are.

lib/IR/DomTreeUpdater.cpp

343 ↗

(On Diff #154240)

Same as below.

390 ↗

(On Diff #154240)

Can you save some work by moving it at the top of the function such that it doesn't have to validate updates if both trees are null?

Or is it intentional to validate them and catch some logic errors in this case as well?

[brzycki]

(call delBB() still pends BasicBlock deletion until a flush event according to the doc).

This is an interesting idea as it gives callers a deferred deletion tool for Lazy and both trees are nullptr. It'd be worthwhile to add documentation somewhere to let others know about this. I know of at least one case when I was working on JumpThreading that the original code flushed LVI information about a block because it called an external routine that might delete the block (it was at the end of runImpl()). This feature gives others a simple way of calling potentially destructive calls, checking the return code, and cleaning up on success or failure.

[NutshellySima]

In D48974#1155938, @kuhar wrote:

Have you considered detecting that both trees are null and overriding the update strategy to Eager in that case? I think that should functionally be equivalent, although more confusing when the strategy you get can be different from what someone just set :P I'm just wondering what pros/cons there are.

1. If I override the UpdateStrategy to Eager when both DT* and PDT* are nullptrs, users may be confused if they use DTU as the following

// An imaginary pass which tries to preserve both DT and PDT. It uses DTU inside so it doesn't need to deal with both strategies.
// We get DT* and PDT* from the pass manager.
void f() {
  DomTreeUpdater DTU (DT, PDT, Lazy); // Both DT and PDT are nullptrs.
  BasicBlock* BB = ...;
  ...
  DTU.delBB(BB); // Caller doesn't expect BB be deleted here.
  ... // Still try to access BB.
}

If the pass gets DT and PDT successfully, it will work. But if it can't access both DT and PDT, it will break.
I think this behavior will make others confused.

2. So I add logic to ignore updates rather than making DTU with both DT/PDT==nullptr functionally equivalent with Eager ones.

[NutshellySima]

In D48974#1155962, @brzycki wrote:

(call delBB() still pends BasicBlock deletion until a flush event according to the doc).

This is an interesting idea as it gives callers a deferred deletion tool for Lazy and both trees are nullptr. It'd be worthwhile to add documentation somewhere to let others know about this. I know of at least one case when I was working on JumpThreading that the original code flushed LVI information about a block because it called an external routine that might delete the block (it was at the end of runImpl()). This feature gives others a simple way of calling potentially destructive calls, checking the return code, and cleaning up on success or failure.

Yes, I think we can document it.

lib/IR/DomTreeUpdater.cpp

390 ↗

(On Diff #154240)

Previously, I think because *Relaxed functions need to inspect whether the update is valid (it must be checked when DT!=null && PDT!=null), so I add a return value to indicate whether the update is valid.
Now, because there isn't any user of this return value, so I think it's better to remove the return value and move this upward.

[NutshellySima]

Address comments.
Change return type of *Relaxed into void and avoid unnecessary checks.

[kuhar]

LGTM, but please wait to see if @brzycki has some comments before submitting the patch

[brzycki]

@NutshellySima I think you said that BasicBlocks that are deleted with deleteBB() aren't removed immediately and are held until a a flush() event, correct? I don't see any comments informing the users that this is the case. I consider it to be unexpected behavior and should be noted.

Code-wise it LGTM as well.

[NutshellySima]

Add the doc on the behavior of deleteBB() when both DT and PDT are null under Lazy Strategy.

[NutshellySima]

Amend the document.

llvm/trunk/include/llvm/IR/DomTreeUpdater.h

public:
   /// Returns true if either of DT or PDT is valid and the tree has at
   /// least one update pending. If DT or PDT is nullptr it is treated
   /// as having no pending updates. This function does not check
   /// whether there is BasicBlock awaiting deletion.
   /// Returns false under Eager UpdateStrategy.
   bool hasPendingUpdates() const;
 
   /// Returns true if there are DominatorTree updates queued.
-  /// Returns false under Eager UpdateStrategy.
+  /// Returns false under Eager UpdateStrategy or DT is nullptr.
   bool hasPendingDomTreeUpdates() const;
 
   /// Returns true if there are PostDominatorTree updates queued.
-  /// Returns false under Eager UpdateStrategy.
+  /// Returns false under Eager UpdateStrategy or PDT is nullptr.
   bool hasPendingPostDomTreeUpdates() const;
 
   /// Apply updates on all available trees. Under Eager UpdateStrategy with
   /// ForceRemoveDuplicates enabled or under Lazy UpdateStrategy, it will
-  /// discard duplicated updates and self-dominance updates. The Eager
-  /// Strategy applies the updates immediately while the Lazy Strategy
-  /// queues the updates. It is required for the state of
-  /// the LLVM IR to be updated *before* applying the Updates because the
-  /// internal update routine will analyze the current state of the relationship
-  /// between a pair of (From, To) BasicBlocks to determine whether a single
-  /// update needs to be discarded.
+  /// discard duplicated updates and self-dominance updates. If both DT and PDT
+  /// are nullptrs, this function discards all updates. The Eager Strategy
+  /// applies the updates immediately while the Lazy Strategy queues the
+  /// updates. It is required for the state of the LLVM IR to be updated
+  /// *before* applying the Updates because the internal update routine will
+  /// analyze the current state of the relationship between a pair of (From, To)
+  /// BasicBlocks to determine whether a single update needs to be discarded.
   void applyUpdates(ArrayRef<DominatorTree::UpdateType> Updates,
                     bool ForceRemoveDuplicates = false);
 
-  /// Notify all available trees on an edge insertion. Under either Strategy,
+  /// Notify all available trees on an edge insertion. If both DT and PDT are
+  /// nullptrs, this function discards the update. Under either Strategy,
   /// self-dominance update will be removed. The Eager Strategy applies
   /// the update immediately while the Lazy Strategy queues the update.
   /// It is recommended to only use this method when you have exactly one
   /// insertion (and no deletions). It is recommended to use applyUpdates() in
   /// all other cases. This function has to be called *after* making the update
   /// on the actual CFG. An internal functions checks if the edge exists in the
   /// CFG in DEBUG mode.
   void insertEdge(BasicBlock *From, BasicBlock *To);
 
   /// Notify all available trees on an edge insertion.
-  /// Under either Strategy, these updates will be discard silently in the
-  /// following sequence
+  /// Under either Strategy, the following updates will be discard silently
   /// 1. Invalid - Inserting an edge that does not exist in the CFG.
   /// 2. Self-dominance update.
+  /// 3. Both DT and PDT are nullptrs.
   /// The Eager Strategy applies the update immediately while the Lazy Strategy
   /// queues the update. It is recommended to only use this method when you have
   /// exactly one insertion (and no deletions) and want to discard an invalid
-  /// update. Returns true if the update is valid.
-  bool insertEdgeRelaxed(BasicBlock *From, BasicBlock *To);
+  /// update.
+  void insertEdgeRelaxed(BasicBlock *From, BasicBlock *To);
 
-  /// Notify all available trees on an edge deletion. Under either Strategy,
+  /// Notify all available trees on an edge deletion. If both DT and PDT are
+  /// nullptrs, this function discards the update. Under either Strategy,
   /// self-dominance update will be removed. The Eager Strategy applies
   /// the update immediately while the Lazy Strategy queues the update.
   /// It is recommended to only use this method when you have exactly one
   /// deletion (and no insertions). It is recommended to use applyUpdates() in
   /// all other cases. This function has to be called *after* making the update
   /// on the actual CFG. An internal functions checks if the edge doesn't exist
   /// in the CFG in DEBUG mode.
   void deleteEdge(BasicBlock *From, BasicBlock *To);
 
   /// Notify all available trees on an edge deletion.
-  /// Under either Strategy, these updates will be discard silently in the
-  /// following sequence:
+  /// Under either Strategy, the following updates will be discard silently
   /// 1. Invalid - Deleting an edge that still exists in the CFG.
   /// 2. Self-dominance update.
+  /// 3. Both DT and PDT are nullptrs.
   /// The Eager Strategy applies the update immediately while the Lazy Strategy
   /// queues the update. It is recommended to only use this method when you have
   /// exactly one deletion (and no insertions) and want to discard an invalid
-  /// update. Returns true if the update is valid.
-  bool deleteEdgeRelaxed(BasicBlock *From, BasicBlock *To);
+  /// update.
+  void deleteEdgeRelaxed(BasicBlock *From, BasicBlock *To);
 
   /// Delete DelBB. DelBB will be removed from its Parent and
   /// erased from available trees if it exists and finally get deleted.
   /// Under Eager UpdateStrategy, DelBB will be processed immediately.
   /// Under Lazy UpdateStrategy, DelBB will be queued until a flush event and
-  /// all available trees are up-to-date.
+  /// all available trees are up-to-date. When both DT and PDT are nullptrs,
+  /// DelBB will be queued until flush() is called.
   void deleteBB(BasicBlock *DelBB);
 
   /// Delete DelBB. DelBB will be removed from its Parent and
   /// erased from available trees if it exists. Then the callback will
   /// be called. Finally, DelBB will be deleted.
   /// Under Eager UpdateStrategy, DelBB will be processed immediately.
   /// Under Lazy UpdateStrategy, DelBB will be queued until a flush event and
   /// all available trees are up-to-date.

llvm/trunk/lib/IR/DomTreeUpdater.cpp

 bool DomTreeUpdater::isSelfDominance(
     const DominatorTree::UpdateType Update) const {
   // Won't affect DomTree and PostDomTree.
   return Update.getFrom() == Update.getTo();
 }
 
 bool DomTreeUpdater::applyLazyUpdate(DominatorTree::UpdateKind Kind,
                                      BasicBlock *From, BasicBlock *To) {
+  assert(DT ||
+         PDT && "Call applyLazyUpdate() when both DT and PDT are nullptrs.");
   assert(Strategy == DomTreeUpdater::UpdateStrategy::Lazy &&
          "Call applyLazyUpdate() with Eager strategy error");
   // Analyze pending updates to determine if the update is unnecessary.
   const DominatorTree::UpdateType Update = {Kind, From, To};
   const DominatorTree::UpdateType Invert = {Kind != DominatorTree::Insert
                                                 ? DominatorTree::Insert
                                                 : DominatorTree::Delete,
                                             From, To};
void DomTreeUpdater::validateDeleteBB(BasicBlock *DelBB) {
   }
   // Make sure DelBB has a valid terminator instruction. As long as DelBB is a
   // Child of Function F it must contain valid IR.
   new UnreachableInst(DelBB->getContext(), DelBB);
 }
 
 void DomTreeUpdater::applyUpdates(ArrayRef<DominatorTree::UpdateType> Updates,
                                   bool ForceRemoveDuplicates) {
+  if (!DT && !PDT)
+    return;
+
   if (Strategy == UpdateStrategy::Lazy || ForceRemoveDuplicates) {
     SmallVector<DominatorTree::UpdateType, 8> Seen;
     for (const auto U : Updates)
       // For Lazy UpdateStrategy, avoid duplicates to applyLazyUpdate() to save
       // on analysis.
       if (llvm::none_of(
               Seen,
               [U](const DominatorTree::UpdateType S) { return S == U; }) &&

 
 void DomTreeUpdater::insertEdge(BasicBlock *From, BasicBlock *To) {
 
 #ifndef NDEBUG
   assert(isUpdateValid({DominatorTree::Insert, From, To}) &&
          "Inserted edge does not appear in the CFG");
 #endif
 
+  if (!DT && !PDT)
+    return;
+
   // Won't affect DomTree and PostDomTree; discard update.
   if (From == To)
     return;
 
   if (Strategy == UpdateStrategy::Eager) {
     if (DT)
       DT->insertEdge(From, To);
     if (PDT)
       PDT->insertEdge(From, To);
     return;
   }
 
   applyLazyUpdate(DominatorTree::Insert, From, To);
 }
 
-bool DomTreeUpdater::insertEdgeRelaxed(BasicBlock *From, BasicBlock *To) {
-  if (!isUpdateValid({DominatorTree::Insert, From, To}))
-    return false;
-
+void DomTreeUpdater::insertEdgeRelaxed(BasicBlock *From, BasicBlock *To) {
   if (From == To)
-    return true;
+    return;
+
+  if (!DT && !PDT)
+    return;
+
+  if (!isUpdateValid({DominatorTree::Insert, From, To}))
+    return;
 
   if (Strategy == UpdateStrategy::Eager) {
     if (DT)
       DT->insertEdge(From, To);
     if (PDT)
       PDT->insertEdge(From, To);
-    return true;
+    return;
   }
 
   applyLazyUpdate(DominatorTree::Insert, From, To);
-  return true;
 }
 
 void DomTreeUpdater::deleteEdge(BasicBlock *From, BasicBlock *To) {
 
 #ifndef NDEBUG
   assert(isUpdateValid({DominatorTree::Delete, From, To}) &&
          "Deleted edge still exists in the CFG!");
 #endif
 
+  if (!DT && !PDT)
+    return;
+
   // Won't affect DomTree and PostDomTree; discard update.
   if (From == To)
     return;
 
   if (Strategy == UpdateStrategy::Eager) {
     if (DT)
       DT->deleteEdge(From, To);
     if (PDT)
       PDT->deleteEdge(From, To);
     return;
   }
 
   applyLazyUpdate(DominatorTree::Delete, From, To);
 }
 
-bool DomTreeUpdater::deleteEdgeRelaxed(BasicBlock *From, BasicBlock *To) {
-  if (!isUpdateValid({DominatorTree::Delete, From, To}))
-    return false;
-
+void DomTreeUpdater::deleteEdgeRelaxed(BasicBlock *From, BasicBlock *To) {
   if (From == To)
-    return true;
+    return;
+
+  if (!DT && !PDT)
+    return;
+
+  if (!isUpdateValid({DominatorTree::Delete, From, To}))
+    return;
 
   if (Strategy == UpdateStrategy::Eager) {
     if (DT)
       DT->deleteEdge(From, To);
     if (PDT)
       PDT->deleteEdge(From, To);
-    return true;
+    return;
   }
 
   applyLazyUpdate(DominatorTree::Delete, From, To);
-  return true;
 }
 
 void DomTreeUpdater::dropOutOfDateUpdates() {
   if (Strategy == DomTreeUpdater::UpdateStrategy::Eager)
     return;
 
   tryFlushDeletedBB();
 

llvm/trunk/unittests/IR/DomTreeUpdaterTest.cpp

TEST(DomTreeUpdater, EagerUpdateBasicOperations) {
   Function::iterator FI = F->begin();
   BasicBlock *BB0 = &*FI++;
   BasicBlock *BB1 = &*FI++;
   BasicBlock *BB2 = &*FI++;
   BasicBlock *BB3 = &*FI++;
   SwitchInst *SI = dyn_cast<SwitchInst>(BB0->getTerminator());
   ASSERT_NE(SI, nullptr) << "Couldn't get SwitchInst.";
 
-  ASSERT_FALSE(DTU.insertEdgeRelaxed(BB0, BB0));
-  ASSERT_TRUE(DTU.deleteEdgeRelaxed(BB0, BB0));
+  DTU.insertEdgeRelaxed(BB0, BB0);
+  DTU.deleteEdgeRelaxed(BB0, BB0);
 
   // Delete edge bb0 -> bb3 and push the update twice to verify duplicate
   // entries are discarded.
   std::vector<DominatorTree::UpdateType> Updates;
   Updates.reserve(4);
   Updates.push_back({DominatorTree::Delete, BB0, BB3});
   Updates.push_back({DominatorTree::Delete, BB0, BB3});
 
TEST(DomTreeUpdater, EagerUpdateBasicOperations) {
   // contained Instructions and change the Terminator to "unreachable" when
   // queued for deletion.
   ASSERT_FALSE(isa<UnreachableInst>(BB3->getTerminator()));
   EXPECT_FALSE(DTU.isBBPendingDeletion(BB3));
   DTU.applyUpdates(Updates, /*ForceRemoveDuplicates*/ true);
   ASSERT_FALSE(DTU.hasPendingUpdates());
 
   // Invalid Insert: no edge bb1 -> bb2 after change to bb0.
-  ASSERT_FALSE(DTU.insertEdgeRelaxed(BB1, BB2));
+  DTU.insertEdgeRelaxed(BB1, BB2);
   // Invalid Delete: edge exists bb0 -> bb1 after change to bb0.
-  ASSERT_FALSE(DTU.deleteEdgeRelaxed(BB0, BB1));
+  DTU.deleteEdgeRelaxed(BB0, BB1);
 
   // DTU working with Eager UpdateStrategy does not need to flush.
   ASSERT_TRUE(DT.verify());
   ASSERT_TRUE(PDT.verify());
 
   // Test callback utils.
   ASSERT_EQ(BB3->getParent(), F);
   DTU.callbackDeleteBB(BB3,
TEST(DomTreeUpdater, EagerUpdateReplaceEntryBB) {
 
   // Add a block as the new function entry BB. We also link it to BB0.
   BasicBlock *NewEntry =
       BasicBlock::Create(F->getContext(), "new_entry", F, BB0);
   BranchInst::Create(BB0, NewEntry);
   EXPECT_EQ(F->begin()->getName(), NewEntry->getName());
   EXPECT_TRUE(&F->getEntryBlock() == NewEntry);
 
-  ASSERT_TRUE(DTU.insertEdgeRelaxed(NewEntry, BB0));
+  DTU.insertEdgeRelaxed(NewEntry, BB0);
 
   // Changing the Entry BB requires a full recalculation of DomTree.
   DTU.recalculate(*F);
   ASSERT_TRUE(DT.verify());
   ASSERT_TRUE(PDT.verify());
 
   // CFG Change: remove new_edge -> bb0 and redirect to new_edge -> bb1.
   EXPECT_EQ(NewEntry->getTerminator()->getNumSuccessors(), 1u);