Index: llvm/include/llvm/Analysis/DomTreeUpdater.h =================================================================== --- llvm/include/llvm/Analysis/DomTreeUpdater.h +++ llvm/include/llvm/Analysis/DomTreeUpdater.h @@ -103,8 +103,24 @@ /// Although GenericDomTree provides several update primitives, /// it is not encouraged to use these APIs directly. - /// Submit updates to all available trees. Under Eager UpdateStrategy with - /// ForceRemoveDuplicates enabled or under Lazy UpdateStrategy, it will + /// Submit updates to all available trees. + /// The Eager Strategy flushes updates immediately while the Lazy Strategy + /// queues the updates. + /// + /// Note: The "existence" of an edge in a CFG refers to the CFG which DTU is + /// in sync with + all updates before that single update. + /// + /// CAUTION! + /// 1. It is required for the state of the LLVM IR to be updated + /// *before* submitting the updates because the internal update routine will + /// analyze the current state of the CFG to determine whether an update + /// is valid. + /// 2. It is illegal to submit any update that has already been submitted, + /// i.e., you are supposed not to insert an existent edge or delete a + /// nonexistent edge. + void applyUpdates(ArrayRef Updates); + + /// Submit updates to all available trees. It will also /// 1. discard duplicated updates, /// 2. remove invalid updates. (Invalid updates means deletion of an edge that /// still exists or insertion of an edge that does not exist.) @@ -122,8 +138,10 @@ /// 2. It is illegal to submit any update that has already been submitted, /// i.e., you are supposed not to insert an existent edge or delete a /// nonexistent edge. - void applyUpdates(ArrayRef Updates, - bool ForceRemoveDuplicates = false); + /// 3. It is only legal to submit updates to an edge in the order CFG changes + /// are made. The order you submit updates on different edges is not + /// restricted. + void applyUpdatesPermissive(ArrayRef Updates); /// Notify DTU that the entry block was replaced. /// Recalculate all available trees and flush all BasicBlocks @@ -149,7 +167,7 @@ /// submitted. } LLVM_ATTRIBUTE_DEPRECATED(void insertEdgeRelaxed(BasicBlock *From, BasicBlock *To), - "Use applyUpdates() instead."); + "Use applyUpdatesPermissive() instead."); /// \deprecated { Submit an edge deletion to all available trees. The Eager /// Strategy flushes this update immediately while the Lazy Strategy queues @@ -171,7 +189,7 @@ /// submitted. } LLVM_ATTRIBUTE_DEPRECATED(void deleteEdgeRelaxed(BasicBlock *From, BasicBlock *To), - "Use applyUpdates() instead."); + "Use applyUpdatesPermissive() instead."); /// Delete DelBB. DelBB will be removed from its Parent and /// erased from available trees if it exists and finally get deleted. @@ -260,11 +278,6 @@ /// Returns true if at least one BasicBlock is deleted. bool forceFlushDeletedBB(); - /// Deduplicate and remove unnecessary updates (no-ops) when using Lazy - /// UpdateStrategy. Returns true if the update is queued for update. - bool applyLazyUpdate(DominatorTree::UpdateKind Kind, BasicBlock *From, - BasicBlock *To); - /// Helper function to apply all pending DomTree updates. void applyDomTreeUpdates(); Index: llvm/lib/Analysis/DomTreeUpdater.cpp =================================================================== --- llvm/lib/Analysis/DomTreeUpdater.cpp +++ llvm/lib/Analysis/DomTreeUpdater.cpp @@ -12,11 +12,13 @@ //===----------------------------------------------------------------------===// #include "llvm/Analysis/DomTreeUpdater.h" +#include "llvm/ADT/SmallSet.h" #include "llvm/Analysis/PostDominators.h" #include "llvm/IR/Dominators.h" #include "llvm/Support/GenericDomTree.h" #include #include +#include namespace llvm { @@ -53,41 +55,6 @@ 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}; - // Only check duplicates in updates that are not applied by both trees. - auto I = - PendUpdates.begin() + std::max(PendDTUpdateIndex, PendPDTUpdateIndex); - const auto E = PendUpdates.end(); - - assert(I <= E && "Iterator out of range."); - - for (; I != E; ++I) { - if (Update == *I) - return false; // Discard duplicate updates. - - if (Invert == *I) { - // Update and Invert are both valid (equivalent to a no-op). Remove - // Invert from PendUpdates and discard the Update. - PendUpdates.erase(I); - return false; - } - } - - PendUpdates.push_back(Update); // Save the valid update. - return true; -} - void DomTreeUpdater::applyDomTreeUpdates() { // No pending DomTreeUpdates. if (Strategy != UpdateStrategy::Lazy || !DT) @@ -261,31 +228,15 @@ new UnreachableInst(DelBB->getContext(), DelBB); } -void DomTreeUpdater::applyUpdates(ArrayRef Updates, - bool ForceRemoveDuplicates) { +void DomTreeUpdater::applyUpdates(ArrayRef Updates) { if (!DT && !PDT) return; - if (Strategy == UpdateStrategy::Lazy || ForceRemoveDuplicates) { - SmallVector Seen; + if (Strategy == UpdateStrategy::Lazy) { 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; }) && - isUpdateValid(U) && !isSelfDominance(U)) { - Seen.push_back(U); - if (Strategy == UpdateStrategy::Lazy) - applyLazyUpdate(U.getKind(), U.getFrom(), U.getTo()); - } - if (Strategy == UpdateStrategy::Lazy) - return; + if (!isSelfDominance(U)) + PendUpdates.push_back(U); - if (DT) - DT->applyUpdates(Seen); - if (PDT) - PDT->applyUpdates(Seen); return; } @@ -295,6 +246,60 @@ PDT->applyUpdates(Updates); } +void DomTreeUpdater::applyUpdatesPermissive( + ArrayRef Updates) { + if (!DT && !PDT) + return; + + SmallSet, 8> Seen; + SmallVector DeduplicatedUpdates; + for (const auto U : Updates) { + auto Edge = std::make_pair(U.getFrom(), U.getTo()); + // Because it is illegal to submit updates that have already been applied + // and updates to an edge need to be strictly ordered, + // it is safe to infer the existence of an edge from the first update + // to this edge. + // If the first update to an edge is "Delete", it means that the edge + // existed before. If the first update to an edge is "Insert", it means + // that the edge didn't exist before. + // + // For example, if the user submits {{Delete, A, B}, {Insert, A, B}}, + // because + // 1. it is illegal to submit updates that have already been applied, + // i.e., user cannot delete an nonexistent edge, + // 2. updates to an edge need to be strictly ordered, + // So, initially edge A -> B existed. + // We can then safely ignore future updates to this edge and directly + // inspect the current CFG: + // a. If the edge still exists, because the user cannot insert an existent + // edge, so both {Delete, A, B}, {Insert, A, B} actually happened and + // resulted in a no-op. DTU won't submit any update in this case. + // b. If the edge doesn't exist, we can then infer that {Delete, A, B} + // actually happened but {Insert, A, B} was an invalid update which never + // happened. DTU will submit {Delete, A, B} in this case. + if (!isSelfDominance(U) && Seen.count(Edge) == 0) { + Seen.insert(Edge); + // If the update doesn't appear in the CFG, it means that + // either the change isn't made or relevant operations + // result in a no-op. + if (isUpdateValid(U)) { + if (isLazy()) + PendUpdates.push_back(U); + else + DeduplicatedUpdates.push_back(U); + } + } + } + + if (Strategy == UpdateStrategy::Lazy) + return; + + if (DT) + DT->applyUpdates(DeduplicatedUpdates); + if (PDT) + PDT->applyUpdates(DeduplicatedUpdates); +} + DominatorTree &DomTreeUpdater::getDomTree() { assert(DT && "Invalid acquisition of a null DomTree"); applyDomTreeUpdates(); @@ -331,7 +336,7 @@ return; } - applyLazyUpdate(DominatorTree::Insert, From, To); + PendUpdates.push_back({DominatorTree::Insert, From, To}); } void DomTreeUpdater::insertEdgeRelaxed(BasicBlock *From, BasicBlock *To) { @@ -352,7 +357,7 @@ return; } - applyLazyUpdate(DominatorTree::Insert, From, To); + PendUpdates.push_back({DominatorTree::Insert, From, To}); } void DomTreeUpdater::deleteEdge(BasicBlock *From, BasicBlock *To) { @@ -377,7 +382,7 @@ return; } - applyLazyUpdate(DominatorTree::Delete, From, To); + PendUpdates.push_back({DominatorTree::Delete, From, To}); } void DomTreeUpdater::deleteEdgeRelaxed(BasicBlock *From, BasicBlock *To) { @@ -398,7 +403,7 @@ return; } - applyLazyUpdate(DominatorTree::Delete, From, To); + PendUpdates.push_back({DominatorTree::Delete, From, To}); } void DomTreeUpdater::dropOutOfDateUpdates() { Index: llvm/lib/Transforms/Scalar/CallSiteSplitting.cpp =================================================================== --- llvm/lib/Transforms/Scalar/CallSiteSplitting.cpp +++ llvm/lib/Transforms/Scalar/CallSiteSplitting.cpp @@ -366,7 +366,7 @@ assert(Splits.size() == 2 && "Expected exactly 2 splits!"); for (unsigned i = 0; i < Splits.size(); i++) { Splits[i]->getTerminator()->eraseFromParent(); - DTU.applyUpdates({{DominatorTree::Delete, Splits[i], TailBB}}); + DTU.applyUpdatesPermissive({{DominatorTree::Delete, Splits[i], TailBB}}); } // Erase the tail block once done with musttail patching Index: llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp =================================================================== --- llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp +++ llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp @@ -373,7 +373,7 @@ ++NumDeadCases; Changed = true; if (--SuccessorsCount[Succ] == 0) - DTU.applyUpdates({{DominatorTree::Delete, BB, Succ}}); + DTU.applyUpdatesPermissive({{DominatorTree::Delete, BB, Succ}}); continue; } if (State == LazyValueInfo::True) { Index: llvm/lib/Transforms/Scalar/JumpThreading.cpp =================================================================== --- llvm/lib/Transforms/Scalar/JumpThreading.cpp +++ llvm/lib/Transforms/Scalar/JumpThreading.cpp @@ -1091,7 +1091,7 @@ << "' folding undef terminator: " << *BBTerm << '\n'); BranchInst::Create(BBTerm->getSuccessor(BestSucc), BBTerm); BBTerm->eraseFromParent(); - DTU->applyUpdates(Updates); + DTU->applyUpdatesPermissive(Updates); return true; } @@ -1159,7 +1159,8 @@ ConstantInt::getFalse(CondCmp->getType()); ReplaceFoldableUses(CondCmp, CI); } - DTU->applyUpdates({{DominatorTree::Delete, BB, ToRemoveSucc}}); + DTU->applyUpdatesPermissive( + {{DominatorTree::Delete, BB, ToRemoveSucc}}); return true; } @@ -1246,7 +1247,7 @@ RemoveSucc->removePredecessor(BB); BranchInst::Create(KeepSucc, BI); BI->eraseFromParent(); - DTU->applyUpdates({{DominatorTree::Delete, BB, RemoveSucc}}); + DTU->applyUpdatesPermissive({{DominatorTree::Delete, BB, RemoveSucc}}); return true; } CurrentBB = CurrentPred; @@ -1676,7 +1677,7 @@ Instruction *Term = BB->getTerminator(); BranchInst::Create(OnlyDest, Term); Term->eraseFromParent(); - DTU->applyUpdates(Updates); + DTU->applyUpdatesPermissive(Updates); // If the condition is now dead due to the removal of the old terminator, // erase it. @@ -2018,9 +2019,9 @@ } // Enqueue required DT updates. - DTU->applyUpdates({{DominatorTree::Insert, NewBB, SuccBB}, - {DominatorTree::Insert, PredBB, NewBB}, - {DominatorTree::Delete, PredBB, BB}}); + DTU->applyUpdatesPermissive({{DominatorTree::Insert, NewBB, SuccBB}, + {DominatorTree::Insert, PredBB, NewBB}, + {DominatorTree::Delete, PredBB, BB}}); // If there were values defined in BB that are used outside the block, then we // now have to update all uses of the value to use either the original value, @@ -2114,7 +2115,7 @@ BFI->setBlockFreq(NewBB, NewBBFreq.getFrequency()); } - DTU->applyUpdates(Updates); + DTU->applyUpdatesPermissive(Updates); return NewBBs[0]; } @@ -2387,7 +2388,7 @@ // Remove the unconditional branch at the end of the PredBB block. OldPredBranch->eraseFromParent(); - DTU->applyUpdates(Updates); + DTU->applyUpdatesPermissive(Updates); ++NumDupes; return true; @@ -2423,8 +2424,8 @@ // The select is now dead. SI->eraseFromParent(); - DTU->applyUpdates({{DominatorTree::Insert, NewBB, BB}, - {DominatorTree::Insert, Pred, NewBB}}); + DTU->applyUpdatesPermissive({{DominatorTree::Insert, NewBB, BB}, + {DominatorTree::Insert, Pred, NewBB}}); // Update any other PHI nodes in BB. for (BasicBlock::iterator BI = BB->begin(); @@ -2601,7 +2602,7 @@ Updates.push_back({DominatorTree::Delete, BB, Succ}); Updates.push_back({DominatorTree::Insert, SplitBB, Succ}); } - DTU->applyUpdates(Updates); + DTU->applyUpdatesPermissive(Updates); return true; } return false; Index: llvm/lib/Transforms/Utils/BasicBlockUtils.cpp =================================================================== --- llvm/lib/Transforms/Utils/BasicBlockUtils.cpp +++ llvm/lib/Transforms/Utils/BasicBlockUtils.cpp @@ -101,7 +101,7 @@ DetatchDeadBlocks(BBs, DTU ? &Updates : nullptr, KeepOneInputPHIs); if (DTU) - DTU->applyUpdates(Updates, /*ForceRemoveDuplicates*/ true); + DTU->applyUpdatesPermissive(Updates); for (BasicBlock *BB : BBs) if (DTU) @@ -237,7 +237,7 @@ isa(BB->getTerminator()) && "The successor list of BB isn't empty before " "applying corresponding DTU updates."); - DTU->applyUpdates(Updates, /*ForceRemoveDuplicates*/ true); + DTU->applyUpdatesPermissive(Updates); DTU->deleteBB(BB); } Index: llvm/lib/Transforms/Utils/Local.cpp =================================================================== --- llvm/lib/Transforms/Utils/Local.cpp +++ llvm/lib/Transforms/Utils/Local.cpp @@ -128,8 +128,7 @@ Builder.CreateBr(Destination); BI->eraseFromParent(); if (DTU) - DTU->applyUpdates({{DominatorTree::Delete, BB, OldDest}}, - /*ForceRemoveDuplicates*/ true); + DTU->applyUpdatesPermissive({{DominatorTree::Delete, BB, OldDest}}); return true; } @@ -205,8 +204,8 @@ i = SI->removeCase(i); e = SI->case_end(); if (DTU) - DTU->applyUpdates({{DominatorTree::Delete, ParentBB, DefaultDest}}, - /*ForceRemoveDuplicates*/ true); + DTU->applyUpdatesPermissive( + {{DominatorTree::Delete, ParentBB, DefaultDest}}); continue; } @@ -254,7 +253,7 @@ if (DeleteDeadConditions) RecursivelyDeleteTriviallyDeadInstructions(Cond, TLI); if (DTU) - DTU->applyUpdates(Updates, /*ForceRemoveDuplicates*/ true); + DTU->applyUpdatesPermissive(Updates); return true; } @@ -332,7 +331,7 @@ } if (DTU) - DTU->applyUpdates(Updates, /*ForceRemoveDuplicates*/ true); + DTU->applyUpdatesPermissive(Updates); return true; } } @@ -666,8 +665,7 @@ if (PhiIt != OldPhiIt) PhiIt = &BB->front(); } if (DTU) - DTU->applyUpdates({{DominatorTree::Delete, Pred, BB}}, - /*ForceRemoveDuplicates*/ true); + DTU->applyUpdatesPermissive({{DominatorTree::Delete, Pred, BB}}); } /// MergeBasicBlockIntoOnlyPred - DestBB is a block with one predecessor and its @@ -736,7 +734,7 @@ isa(PredBB->getTerminator()) && "The successor list of PredBB isn't empty before " "applying corresponding DTU updates."); - DTU->applyUpdates(Updates, /*ForceRemoveDuplicates*/ true); + DTU->applyUpdatesPermissive(Updates); DTU->deleteBB(PredBB); // Recalculation of DomTree is needed when updating a forward DomTree and // the Entry BB is replaced. @@ -1078,7 +1076,7 @@ "applying corresponding DTU updates."); if (DTU) { - DTU->applyUpdates(Updates, /*ForceRemoveDuplicates*/ true); + DTU->applyUpdatesPermissive(Updates); DTU->deleteBB(BB); } else { BB->eraseFromParent(); // Delete the old basic block. @@ -1942,7 +1940,7 @@ ++NumInstrsRemoved; } if (DTU) - DTU->applyUpdates(Updates, /*ForceRemoveDuplicates*/ true); + DTU->applyUpdatesPermissive(Updates); return NumInstrsRemoved; } @@ -1970,8 +1968,7 @@ UnwindDestBB->removePredecessor(BB); II->eraseFromParent(); if (DTU) - DTU->applyUpdates({{DominatorTree::Delete, BB, UnwindDestBB}}, - /*ForceRemoveDuplicates*/ true); + DTU->applyUpdatesPermissive({{DominatorTree::Delete, BB, UnwindDestBB}}); } BasicBlock *llvm::changeToInvokeAndSplitBasicBlock(CallInst *CI, @@ -2118,8 +2115,8 @@ UnwindDestBB->removePredecessor(II->getParent()); II->eraseFromParent(); if (DTU) - DTU->applyUpdates({{DominatorTree::Delete, BB, UnwindDestBB}}, - /*ForceRemoveDuplicates*/ true); + DTU->applyUpdatesPermissive( + {{DominatorTree::Delete, BB, UnwindDestBB}}); } else changeToCall(II, DTU); Changed = true; @@ -2208,8 +2205,7 @@ TI->replaceAllUsesWith(NewTI); TI->eraseFromParent(); if (DTU) - DTU->applyUpdates({{DominatorTree::Delete, BB, UnwindDest}}, - /*ForceRemoveDuplicates*/ true); + DTU->applyUpdatesPermissive({{DominatorTree::Delete, BB, UnwindDest}}); } /// removeUnreachableBlocks - Remove blocks that are not reachable, even @@ -2274,7 +2270,7 @@ } if (DTU) { - DTU->applyUpdates(Updates, /*ForceRemoveDuplicates*/ true); + DTU->applyUpdatesPermissive(Updates); bool Deleted = false; for (auto *BB : DeadBlockSet) { if (DTU->isBBPendingDeletion(BB)) Index: llvm/unittests/Analysis/DomTreeUpdaterTest.cpp =================================================================== --- llvm/unittests/Analysis/DomTreeUpdaterTest.cpp +++ llvm/unittests/Analysis/DomTreeUpdaterTest.cpp @@ -71,9 +71,9 @@ SwitchInst *SI = dyn_cast(BB0->getTerminator()); ASSERT_NE(SI, nullptr) << "Couldn't get SwitchInst."; - DTU.applyUpdates( - {{DominatorTree::Insert, BB0, BB0}, {DominatorTree::Delete, BB0, BB0}}, - /*ForceRemoveDuplicates*/ true); + DTU.applyUpdatesPermissive( + {{DominatorTree::Insert, BB0, BB0}, {DominatorTree::Delete, BB0, BB0}}); + ASSERT_FALSE(DTU.hasPendingUpdates()); // Delete edge bb0 -> bb3 and push the update twice to verify duplicate // entries are discarded. @@ -102,14 +102,13 @@ // queued for deletion. ASSERT_FALSE(isa(BB3->getTerminator())); EXPECT_FALSE(DTU.isBBPendingDeletion(BB3)); - DTU.applyUpdates(Updates, /*ForceRemoveDuplicates*/ true); + DTU.applyUpdatesPermissive(Updates); ASSERT_FALSE(DTU.hasPendingUpdates()); // Invalid Insert: no edge bb1 -> bb2 after change to bb0. // Invalid Delete: edge exists bb0 -> bb1 after change to bb0. - DTU.applyUpdates( - {{DominatorTree::Insert, BB1, BB2}, {DominatorTree::Delete, BB0, BB1}}, - /*ForceRemoveDuplicates*/ true); + DTU.applyUpdatesPermissive( + {{DominatorTree::Insert, BB1, BB2}, {DominatorTree::Delete, BB0, BB1}}); // DTU working with Eager UpdateStrategy does not need to flush. ASSERT_TRUE(DT.verify()); @@ -184,8 +183,7 @@ EXPECT_EQ(F->begin()->getName(), NewEntry->getName()); EXPECT_TRUE(&F->getEntryBlock() == NewEntry); - DTU.applyUpdates({{DominatorTree::Insert, NewEntry, BB0}}, - /*ForceRemoveDuplicates*/ true); + DTU.applyUpdates({{DominatorTree::Insert, NewEntry, BB0}}); // Changing the Entry BB requires a full recalculation of DomTree. DTU.recalculate(*F); @@ -254,7 +252,7 @@ BasicBlock *BB3 = &*FI++; // Test discards of self-domination update. - DTU.applyUpdates({{DominatorTree::Delete, BB0, BB0}}); + DTU.applyUpdatesPermissive({{DominatorTree::Insert, BB0, BB0}}); ASSERT_FALSE(DTU.hasPendingDomTreeUpdates()); // Delete edge bb0 -> bb3 and push the update twice to verify duplicate @@ -277,7 +275,7 @@ // Verify. Updates to DTU must be applied *after* all changes to the CFG // (including block deletion). - DTU.applyUpdates(Updates); + DTU.applyUpdatesPermissive(Updates); ASSERT_TRUE(DTU.getDomTree().verify()); // Deletion of a BasicBlock is an immediate event. We remove all uses to the @@ -362,9 +360,9 @@ // // While the final CFG form is functionally identical the updates to // DTU are not. In the first case we must have - // DTU.applyUpdates({{DominatorTree::Insert, Pred1, Succ}}) while in the - // latter case we must *NOT* have DTU.applyUpdates({{DominatorTree::Insert, - // Pred1, Succ}}). + // DTU.applyUpdates({{DominatorTree::Insert, Pred1, Succ}}) while in + // the latter case we must *NOT* have + // DTU.applyUpdates({{DominatorTree::Insert, Pred1, Succ}}). // CFG Change: bb0 now only has bb0 -> bb1 and bb0 -> bb3. We are preparing to // remove bb2. @@ -384,9 +382,9 @@ BasicBlocks.end()); }; ASSERT_EQ(BasicBlocks.size(), static_cast(2)); - // Remove bb2 from F. This has to happen before the call to applyUpdates() for - // DTU to detect there is no longer an edge between bb2 -> bb3. The deleteBB() - // method converts bb2's TI into "unreachable". + // Remove bb2 from F. This has to happen before the call to + // applyUpdates() for DTU to detect there is no longer an edge between + // bb2 -> bb3. The deleteBB() method converts bb2's TI into "unreachable". ASSERT_FALSE(isa(BB2->getTerminator())); EXPECT_FALSE(DTU.isBBPendingDeletion(BB2)); DTU.callbackDeleteBB(BB2, Eraser); @@ -407,9 +405,9 @@ BranchInst::Create(BB3, BB0); EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 1u); - // Remove bb1 from F. This has to happen before the call to applyUpdates() for - // DTU to detect there is no longer an edge between bb1 -> bb3. The deleteBB() - // method converts bb1's TI into "unreachable". + // Remove bb1 from F. This has to happen before the call to + // applyUpdates() for DTU to detect there is no longer an edge between + // bb1 -> bb3. The deleteBB() method converts bb1's TI into "unreachable". ASSERT_FALSE(isa(BB1->getTerminator())); EXPECT_FALSE(DTU.isBBPendingDeletion(BB1)); DTU.callbackDeleteBB(BB1, Eraser); @@ -424,7 +422,7 @@ Updates.push_back({DominatorTree::Delete, BB1, BB3}); // Verify everything. - DTU.applyUpdates(Updates); + DTU.applyUpdatesPermissive(Updates); ASSERT_EQ(BasicBlocks.size(), static_cast(2)); DTU.flush(); ASSERT_EQ(BasicBlocks.size(), static_cast(0)); @@ -509,7 +507,7 @@ // Verify. Updates to DTU must be applied *after* all changes to the CFG // (including block deletion). - DTU.applyUpdates(Updates); + DTU.applyUpdatesPermissive(Updates); ASSERT_TRUE(DTU.getDomTree().verify()); ASSERT_TRUE(DTU.hasPendingUpdates()); ASSERT_TRUE(DTU.hasPendingPostDomTreeUpdates()); @@ -648,8 +646,7 @@ SwitchInst *SI = dyn_cast(BB0->getTerminator()); ASSERT_NE(SI, nullptr) << "Couldn't get SwitchInst."; - // Delete edge bb0 -> bb3 and push the update twice to verify duplicate - // entries are discarded. + // Delete edge bb0 -> bb3. std::vector Updates; Updates.reserve(1); Updates.push_back({DominatorTree::Delete, BB0, BB3}); @@ -694,7 +691,7 @@ ++i; } - DTU.applyUpdates(Updates); + DTU.applyUpdatesPermissive(Updates); // flush PostDomTree ASSERT_TRUE(DTU.getPostDomTree().verify()); ASSERT_FALSE(DTU.hasPendingPostDomTreeUpdates()); @@ -729,3 +726,69 @@ DTU.recalculate(*F); ASSERT_FALSE(DTU.hasPendingDeletedBB()); } + +TEST(DomTreeUpdater, LazyUpdateDeduplicationTest) { + StringRef FuncName = "f"; + StringRef ModuleString = R"( + define i32 @f() { + bb0: + br label %bb1 + bb1: + ret i32 1 + bb2: + ret i32 1 + } + )"; + // Make the module. + LLVMContext Context; + std::unique_ptr M = makeLLVMModule(Context, ModuleString); + Function *F = M->getFunction(FuncName); + + // Make the DTU. + DominatorTree DT(*F); + DomTreeUpdater DTU(&DT, nullptr, DomTreeUpdater::UpdateStrategy::Lazy); + ASSERT_TRUE(DTU.getDomTree().verify()); + + Function::iterator FI = F->begin(); + BasicBlock *BB0 = &*FI++; + BasicBlock *BB1 = &*FI++; + BasicBlock *BB2 = &*FI++; + + // CFG Change: remove bb0 -> bb1 and add back bb0 -> bb1. + EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 1u); + BB0->getTerminator()->eraseFromParent(); + BranchInst::Create(BB1, BB0); + EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 1u); + + // Update the DTU and simulate duplicates. + DTU.applyUpdatesPermissive({{DominatorTree::Delete, BB0, BB1}, + {DominatorTree::Delete, BB0, BB1}, + {DominatorTree::Insert, BB0, BB1}, + {DominatorTree::Insert, BB0, BB1}, + {DominatorTree::Insert, BB0, BB1}}); + + // The above operations result in a no-op. + ASSERT_FALSE(DTU.hasPendingUpdates()); + + // Update the DTU. Simulate an invalid update. + DTU.applyUpdatesPermissive({{DominatorTree::Delete, BB0, BB1}}); + ASSERT_FALSE(DTU.hasPendingUpdates()); + + // CFG Change: remove bb0 -> bb1. + EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 1u); + BB0->getTerminator()->eraseFromParent(); + + // Update the DTU and simulate invalid updates. + DTU.applyUpdatesPermissive({{DominatorTree::Delete, BB0, BB1}, + {DominatorTree::Insert, BB0, BB1}, + {DominatorTree::Delete, BB0, BB1}, + {DominatorTree::Insert, BB0, BB1}, + {DominatorTree::Insert, BB0, BB1}}); + ASSERT_TRUE(DTU.hasPendingUpdates()); + + // CFG Change: add bb0 -> bb2. + BranchInst::Create(BB2, BB0); + EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 1u); + DTU.applyUpdates({{DominatorTree::Insert, BB0, BB2}}); + ASSERT_TRUE(DTU.getDomTree().verify()); +}