Revert "[SimplifyCFG] Handle tail-sinking of more than 2 incoming branches"
This reverts commit r280217. r280216 caused buildbot failures - backing out the entire chain.
llvm-svn: 280233
diff --git a/llvm/lib/Transforms/Utils/SimplifyCFG.cpp b/llvm/lib/Transforms/Utils/SimplifyCFG.cpp
index 3404a4d..213169b 100644
--- a/llvm/lib/Transforms/Utils/SimplifyCFG.cpp
+++ b/llvm/lib/Transforms/Utils/SimplifyCFG.cpp
@@ -1561,62 +1561,20 @@
assert(BI1->isUnconditional());
BasicBlock *BBEnd = BI1->getSuccessor(0);
- // We support two situations:
- // (1) all incoming arcs are unconditional
- // (2) one incoming arc is conditional
- //
- // (2) is very common in switch defaults and
- // else-if patterns;
- //
- // if (a) f(1);
- // else if (b) f(2);
- //
- // produces:
- //
- // [if]
- // / \
- // [f(1)] [if]
- // | | \
- // | | \
- // | [f(2)]|
- // \ | /
- // [ end ]
- //
- // [end] has two unconditional predecessor arcs and one conditional. The
- // conditional refers to the implicit empty 'else' arc. This conditional
- // arc can also be caused by an empty default block in a switch.
- //
- // In this case, we attempt to sink code from all *unconditional* arcs.
- // If we can sink instructions from these arcs (determined during the scan
- // phase below) we insert a common successor for all unconditional arcs and
- // connect that to [end], to enable sinking:
- //
- // [if]
- // / \
- // [x(1)] [if]
- // | | \
- // | | \
- // | [x(2)] |
- // \ / |
- // [sink.split] |
- // \ /
- // [ end ]
- //
- SmallVector<BasicBlock*,4> UnconditionalPreds;
- Instruction *Cond = nullptr;
- for (auto *B : predecessors(BBEnd)) {
- auto *T = B->getTerminator();
- if (isa<BranchInst>(T) && cast<BranchInst>(T)->isUnconditional())
- UnconditionalPreds.push_back(B);
- else if ((isa<BranchInst>(T) || isa<SwitchInst>(T)) && !Cond)
- Cond = T;
- else
- return false;
- }
- if (UnconditionalPreds.size() < 2)
+ // We currently only support branch targets with two predecessors.
+ // FIXME: this is an arbitrary restriction and should be lifted.
+ SmallVector<BasicBlock*,4> Blocks;
+ for (auto *BB : predecessors(BBEnd))
+ Blocks.push_back(BB);
+ if (Blocks.size() != 2 ||
+ !all_of(Blocks, [](const BasicBlock *BB) {
+ auto *BI = dyn_cast<BranchInst>(BB->getTerminator());
+ return BI && BI->isUnconditional();
+ }))
return false;
-
+
bool Changed = false;
+
// We take a two-step approach to tail sinking. First we scan from the end of
// each block upwards in lockstep. If the n'th instruction from the end of each
// block can be sunk, those instructions are added to ValuesToSink and we
@@ -1626,7 +1584,7 @@
unsigned ScanIdx = 0;
SmallPtrSet<Value*,4> InstructionsToSink;
DenseMap<Instruction*, SmallVector<Value*,4>> PHIOperands;
- LockstepReverseIterator LRI(UnconditionalPreds);
+ LockstepReverseIterator LRI(Blocks);
while (LRI.isValid() &&
canSinkInstructions(*LRI, PHIOperands)) {
DEBUG(dbgs() << "SINK: instruction can be sunk: " << (*LRI)[0] << "\n");
@@ -1635,35 +1593,6 @@
--LRI;
}
- auto ProfitableToSinkLastInstruction = [&]() {
- LRI.reset();
- unsigned NumPHIdValues = 0;
- for (auto *I : *LRI)
- for (auto *V : PHIOperands[I])
- if (InstructionsToSink.count(V) == 0)
- ++NumPHIdValues;
- DEBUG(dbgs() << "SINK: #phid values: " << NumPHIdValues << "\n");
- assert((NumPHIdValues % UnconditionalPreds.size() == 0) &&
- "Every operand must either be PHId or not PHId!");
-
- return NumPHIdValues / UnconditionalPreds.size() <= 1;
- };
-
- if (ScanIdx > 0 && Cond) {
- // Check if we would actually sink anything first!
- if (!ProfitableToSinkLastInstruction())
- return false;
-
- DEBUG(dbgs() << "SINK: Splitting edge\n");
- // We have a conditional edge and we're going to sink some instructions.
- // Insert a new block postdominating all blocks we're going to sink from.
- if (!SplitBlockPredecessors(BI1->getSuccessor(0), UnconditionalPreds,
- ".sink.split"))
- // Edges couldn't be split.
- return false;
- Changed = true;
- }
-
// Now that we've analyzed all potential sinking candidates, perform the
// actual sink. We iteratively sink the last non-terminator of the source
// blocks into their common successor unless doing so would require too
@@ -1678,20 +1607,29 @@
// This is unlikely in practice though.
for (unsigned SinkIdx = 0; SinkIdx != ScanIdx; ++SinkIdx) {
DEBUG(dbgs() << "SINK: Sink: "
- << *UnconditionalPreds[0]->getTerminator()->getPrevNode()
+ << *Blocks[0]->getTerminator()->getPrevNode()
<< "\n");
// Because we've sunk every instruction in turn, the current instruction to
// sink is always at index 0.
- if (!ProfitableToSinkLastInstruction()) {
- // Too many PHIs would be created.
- DEBUG(dbgs() << "SINK: stopping here, too many PHIs would be created!\n");
- break;
- }
+ LRI.reset();
+ unsigned NumPHIdValues = 0;
+ for (auto *I : *LRI)
+ for (auto *V : PHIOperands[I])
+ if (InstructionsToSink.count(V) == 0)
+ ++NumPHIdValues;
+ DEBUG(dbgs() << "SINK: #phid values: " << NumPHIdValues << "\n");
+ assert((NumPHIdValues % Blocks.size() == 0) &&
+ "Every operand must either be PHId or not PHId!");
- sinkLastInstruction(UnconditionalPreds);
+ if (NumPHIdValues / Blocks.size() > 1)
+ // Too many PHIs would be created.
+ break;
+
+ sinkLastInstruction(Blocks);
NumSinkCommons++;
Changed = true;
}
+
return Changed;
}