From 6d103d7746c94cc865138093c7c65138b89aa77c Mon Sep 17 00:00:00 2001 From: Alexis Engelke Date: Wed, 31 Jul 2024 19:20:49 +0200 Subject: [Support] Erase blocks after DomTree::eraseNode (#101195) Change eraseNode to require that the basic block is still contained inside the function. This is a preparation for using numbers of basic blocks inside the dominator tree, which are invalid for blocks that are not inside a function. --- llvm/include/llvm/Analysis/GenericDomTreeUpdater.h | 2 +- llvm/lib/Analysis/DomTreeUpdater.cpp | 8 ++-- llvm/lib/CodeGen/EarlyIfConversion.cpp | 46 +++++++++++++--------- .../Target/AArch64/AArch64ConditionalCompares.cpp | 3 +- llvm/unittests/IR/DominatorTreeTest.cpp | 3 +- 5 files changed, 34 insertions(+), 28 deletions(-) diff --git a/llvm/include/llvm/Analysis/GenericDomTreeUpdater.h b/llvm/include/llvm/Analysis/GenericDomTreeUpdater.h index 84ed882..ca4ce68 100644 --- a/llvm/include/llvm/Analysis/GenericDomTreeUpdater.h +++ b/llvm/include/llvm/Analysis/GenericDomTreeUpdater.h @@ -232,7 +232,7 @@ protected: /// insertEdge/deleteEdge or is unnecessary in the batch update. bool isUpdateValid(typename DomTreeT::UpdateType Update) const; - /// Erase Basic Block node that has been unlinked from Function + /// Erase Basic Block node before it is unlinked from Function /// in the DomTree and PostDomTree. void eraseDelBBNode(BasicBlockT *DelBB); diff --git a/llvm/lib/Analysis/DomTreeUpdater.cpp b/llvm/lib/Analysis/DomTreeUpdater.cpp index 6895317..351bd66 100644 --- a/llvm/lib/Analysis/DomTreeUpdater.cpp +++ b/llvm/lib/Analysis/DomTreeUpdater.cpp @@ -42,9 +42,8 @@ bool DomTreeUpdater::forceFlushDeletedBB() { // delete only has an UnreachableInst inside. assert(BB->size() == 1 && isa(BB->getTerminator()) && "DelBB has been modified while awaiting deletion."); - BB->removeFromParent(); eraseDelBBNode(BB); - delete BB; + BB->eraseFromParent(); } DeletedBBs.clear(); Callbacks.clear(); @@ -63,9 +62,8 @@ void DomTreeUpdater::deleteBB(BasicBlock *DelBB) { return; } - DelBB->removeFromParent(); eraseDelBBNode(DelBB); - delete DelBB; + DelBB->eraseFromParent(); } void DomTreeUpdater::callbackDeleteBB( @@ -77,8 +75,8 @@ void DomTreeUpdater::callbackDeleteBB( return; } - DelBB->removeFromParent(); eraseDelBBNode(DelBB); + DelBB->removeFromParent(); Callback(DelBB); delete DelBB; } diff --git a/llvm/lib/CodeGen/EarlyIfConversion.cpp b/llvm/lib/CodeGen/EarlyIfConversion.cpp index d506c62..0de8112 100644 --- a/llvm/lib/CodeGen/EarlyIfConversion.cpp +++ b/llvm/lib/CodeGen/EarlyIfConversion.cpp @@ -181,8 +181,8 @@ public: bool canConvertIf(MachineBasicBlock *MBB, bool Predicate = false); /// convertIf - If-convert the last block passed to canConvertIf(), assuming - /// it is possible. Add any erased blocks to RemovedBlocks. - void convertIf(SmallVectorImpl &RemovedBlocks, + /// it is possible. Add any blocks that are to be erased to RemoveBlocks. + void convertIf(SmallVectorImpl &RemoveBlocks, bool Predicate = false); }; } // end anonymous namespace @@ -678,9 +678,9 @@ void SSAIfConv::rewritePHIOperands() { /// convertIf - Execute the if conversion after canConvertIf has determined the /// feasibility. /// -/// Any basic blocks erased will be added to RemovedBlocks. +/// Any basic blocks that need to be erased will be added to RemoveBlocks. /// -void SSAIfConv::convertIf(SmallVectorImpl &RemovedBlocks, +void SSAIfConv::convertIf(SmallVectorImpl &RemoveBlocks, bool Predicate) { assert(Head && Tail && TBB && FBB && "Call canConvertIf first."); @@ -721,15 +721,18 @@ void SSAIfConv::convertIf(SmallVectorImpl &RemovedBlocks, DebugLoc HeadDL = Head->getFirstTerminator()->getDebugLoc(); TII->removeBranch(*Head); - // Erase the now empty conditional blocks. It is likely that Head can fall + // Mark the now empty conditional blocks for removal and move them to the end. + // It is likely that Head can fall // through to Tail, and we can join the two blocks. if (TBB != Tail) { - RemovedBlocks.push_back(TBB); - TBB->eraseFromParent(); + RemoveBlocks.push_back(TBB); + if (TBB != &TBB->getParent()->back()) + TBB->moveAfter(&TBB->getParent()->back()); } if (FBB != Tail) { - RemovedBlocks.push_back(FBB); - FBB->eraseFromParent(); + RemoveBlocks.push_back(FBB); + if (FBB != &FBB->getParent()->back()) + FBB->moveAfter(&FBB->getParent()->back()); } assert(Head->succ_empty() && "Additional head successors?"); @@ -740,8 +743,9 @@ void SSAIfConv::convertIf(SmallVectorImpl &RemovedBlocks, Head->splice(Head->end(), Tail, Tail->begin(), Tail->end()); Head->transferSuccessorsAndUpdatePHIs(Tail); - RemovedBlocks.push_back(Tail); - Tail->eraseFromParent(); + RemoveBlocks.push_back(Tail); + if (Tail != &Tail->getParent()->back()) + Tail->moveAfter(&Tail->getParent()->back()); } else { // We need a branch to Tail, let code placement work it out later. LLVM_DEBUG(dbgs() << "Converting to unconditional branch.\n"); @@ -1062,11 +1066,13 @@ bool EarlyIfConverter::tryConvertIf(MachineBasicBlock *MBB) { while (IfConv.canConvertIf(MBB) && shouldConvertIf()) { // If-convert MBB and update analyses. invalidateTraces(); - SmallVector RemovedBlocks; - IfConv.convertIf(RemovedBlocks); + SmallVector RemoveBlocks; + IfConv.convertIf(RemoveBlocks); Changed = true; - updateDomTree(DomTree, IfConv, RemovedBlocks); - updateLoops(Loops, RemovedBlocks); + updateDomTree(DomTree, IfConv, RemoveBlocks); + for (MachineBasicBlock *MBB : RemoveBlocks) + MBB->eraseFromParent(); + updateLoops(Loops, RemoveBlocks); } return Changed; } @@ -1200,11 +1206,13 @@ bool EarlyIfPredicator::tryConvertIf(MachineBasicBlock *MBB) { bool Changed = false; while (IfConv.canConvertIf(MBB, /*Predicate*/ true) && shouldConvertIf()) { // If-convert MBB and update analyses. - SmallVector RemovedBlocks; - IfConv.convertIf(RemovedBlocks, /*Predicate*/ true); + SmallVector RemoveBlocks; + IfConv.convertIf(RemoveBlocks, /*Predicate*/ true); Changed = true; - updateDomTree(DomTree, IfConv, RemovedBlocks); - updateLoops(Loops, RemovedBlocks); + updateDomTree(DomTree, IfConv, RemoveBlocks); + for (MachineBasicBlock *MBB : RemoveBlocks) + MBB->eraseFromParent(); + updateLoops(Loops, RemoveBlocks); } return Changed; } diff --git a/llvm/lib/Target/AArch64/AArch64ConditionalCompares.cpp b/llvm/lib/Target/AArch64/AArch64ConditionalCompares.cpp index 49e5211..9669a39 100644 --- a/llvm/lib/Target/AArch64/AArch64ConditionalCompares.cpp +++ b/llvm/lib/Target/AArch64/AArch64ConditionalCompares.cpp @@ -711,7 +711,6 @@ void SSACCmpConv::convert(SmallVectorImpl &RemovedBlocks) { Head->updateTerminator(CmpBB->getNextNode()); RemovedBlocks.push_back(CmpBB); - CmpBB->eraseFromParent(); LLVM_DEBUG(dbgs() << "Result:\n" << *Head); ++NumConverted; } @@ -918,6 +917,8 @@ bool AArch64ConditionalCompares::tryConvert(MachineBasicBlock *MBB) { CmpConv.convert(RemovedBlocks); Changed = true; updateDomTree(RemovedBlocks); + for (MachineBasicBlock *MBB : RemovedBlocks) + MBB->eraseFromParent(); updateLoops(RemovedBlocks); } return Changed; diff --git a/llvm/unittests/IR/DominatorTreeTest.cpp b/llvm/unittests/IR/DominatorTreeTest.cpp index 44bde74..555348c 100644 --- a/llvm/unittests/IR/DominatorTreeTest.cpp +++ b/llvm/unittests/IR/DominatorTreeTest.cpp @@ -607,11 +607,10 @@ TEST(DominatorTree, DeletingEdgesIntroducesInfiniteLoop2) { SwitchC->removeCase(SwitchC->case_begin()); DT->deleteEdge(C, C2); PDT->deleteEdge(C, C2); - C2->removeFromParent(); EXPECT_EQ(DT->getNode(C2), nullptr); PDT->eraseNode(C2); - delete C2; + C2->eraseFromParent(); EXPECT_TRUE(DT->verify()); EXPECT_TRUE(PDT->verify()); -- cgit v1.1