Generalize MergeBlockIntoPredecessor. Replace uses of MergeBasicBlockIntoOnlyPred.
Summary:
Two utils methods have essentially the same functionality. This is an attempt to merge them into one.
1. lib/Transforms/Utils/Local.cpp : MergeBasicBlockIntoOnlyPred
2. lib/Transforms/Utils/BasicBlockUtils.cpp : MergeBlockIntoPredecessor
Prior to the patch:
1. MergeBasicBlockIntoOnlyPred
Updates either DomTree or DeferredDominance
Moves all instructions from Pred to BB, deletes Pred
Asserts BB has single predecessor
If address was taken, replace the block address with constant 1 (?)
2. MergeBlockIntoPredecessor
Updates DomTree, LoopInfo and MemoryDependenceResults
Moves all instruction from BB to Pred, deletes BB
Returns if doesn't have a single predecessor
Returns if BB's address was taken
After the patch:
Method 2. MergeBlockIntoPredecessor is attempting to become the new default:
Updates DomTree or DeferredDominance, and LoopInfo and MemoryDependenceResults
Moves all instruction from BB to Pred, deletes BB
Returns if doesn't have a single predecessor
Returns if BB's address was taken
Uses of MergeBasicBlockIntoOnlyPred that need to be replaced:
1. lib/Transforms/Scalar/LoopSimplifyCFG.cpp
Updated in this patch. No challenges.
2. lib/CodeGen/CodeGenPrepare.cpp
Updated in this patch.
i. eliminateFallThrough is straightforward, but I added using a temporary array to avoid the iterator invalidation.
ii. eliminateMostlyEmptyBlock(s) methods also now use a temporary array for blocks
Some interesting aspects:
- Since Pred is not deleted (BB is), the entry block does not need updating.
- The entry block was being updated with the deleted block in eliminateMostlyEmptyBlock. Added assert to make obvious that BB=SinglePred.
- isMergingEmptyBlockProfitable assumes BB is the one to be deleted.
- eliminateMostlyEmptyBlock(BB) does not delete BB on one path, it deletes its unique predecessor instead.
- adding some test owner as subscribers for the interesting tests modified:
test/CodeGen/X86/avx-cmp.ll
test/CodeGen/AMDGPU/nested-loop-conditions.ll
test/CodeGen/AMDGPU/si-annotate-cf.ll
test/CodeGen/X86/hoist-spill.ll
test/CodeGen/X86/2006-11-17-IllegalMove.ll
3. lib/Transforms/Scalar/JumpThreading.cpp
Not covered in this patch. It is the only use case using the DeferredDominance.
I would defer to Brian Rzycki to make this replacement.
Reviewers: chandlerc, spatel, davide, brzycki, bkramer, javed.absar
Subscribers: qcolombet, sanjoy, nemanjai, nhaehnle, jlebar, tpr, kbarton, RKSimon, wmi, arsenm, llvm-commits
Differential Revision: https://reviews.llvm.org/D48202
llvm-svn: 335183
diff --git a/llvm/lib/Transforms/Utils/BasicBlockUtils.cpp b/llvm/lib/Transforms/Utils/BasicBlockUtils.cpp
index 5983704..516a785 100644
--- a/llvm/lib/Transforms/Utils/BasicBlockUtils.cpp
+++ b/llvm/lib/Transforms/Utils/BasicBlockUtils.cpp
@@ -117,9 +117,12 @@
bool llvm::MergeBlockIntoPredecessor(BasicBlock *BB, DominatorTree *DT,
LoopInfo *LI,
- MemoryDependenceResults *MemDep) {
- // Don't merge away blocks who have their address taken.
- if (BB->hasAddressTaken()) return false;
+ MemoryDependenceResults *MemDep,
+ DeferredDominance *DDT) {
+ assert(!(DT && DDT) && "Cannot call with both DT and DDT.");
+
+ if (BB->hasAddressTaken())
+ return false;
// Can't merge if there are multiple predecessors, or no predecessors.
BasicBlock *PredBB = BB->getUniquePredecessor();
@@ -131,16 +134,9 @@
if (PredBB->getTerminator()->isExceptional())
return false;
- succ_iterator SI(succ_begin(PredBB)), SE(succ_end(PredBB));
- BasicBlock *OnlySucc = BB;
- for (; SI != SE; ++SI)
- if (*SI != OnlySucc) {
- OnlySucc = nullptr; // There are multiple distinct successors!
- break;
- }
-
- // Can't merge if there are multiple successors.
- if (!OnlySucc) return false;
+ // Can't merge if there are multiple distinct successors.
+ if (PredBB->getUniqueSuccessor() != BB)
+ return false;
// Can't merge if there is PHI loop.
for (PHINode &PN : BB->phis())
@@ -158,6 +154,18 @@
FoldSingleEntryPHINodes(BB, MemDep);
}
+ // Deferred DT update: Collect all the edges that exit BB. These
+ // dominator edges will be redirected from Pred.
+ std::vector<DominatorTree::UpdateType> Updates;
+ if (DDT) {
+ Updates.reserve(1 + (2 * succ_size(BB)));
+ Updates.push_back({DominatorTree::Delete, PredBB, BB});
+ for (auto I = succ_begin(BB), E = succ_end(BB); I != E; ++I) {
+ Updates.push_back({DominatorTree::Delete, BB, *I});
+ Updates.push_back({DominatorTree::Insert, PredBB, *I});
+ }
+ }
+
// Delete the unconditional branch from the predecessor...
PredBB->getInstList().pop_back();
@@ -204,7 +212,12 @@
if (MemDep)
MemDep->invalidateCachedPredecessors();
- BB->eraseFromParent();
+ if (DDT) {
+ DDT->deleteBB(BB); // Deferred deletion of BB.
+ DDT->applyUpdates(Updates);
+ } else {
+ BB->eraseFromParent(); // Nuke BB.
+ }
return true;
}