aboutsummaryrefslogtreecommitdiffstats
path: root/lib
diff options
context:
space:
mode:
authorChris Lattner <sabre@nondot.org>2004-10-14 05:13:36 +0000
committerChris Lattner <sabre@nondot.org>2004-10-14 05:13:36 +0000
commit9c07866ef861e072395306e9811c329c7fe5bbe8 (patch)
tree8c3d9180a3539c32211a3ca4398cd458cbca75df /lib
parent1c7efba2bddd6b17326a012d7bb77f3cf9668078 (diff)
downloadexternal_llvm-9c07866ef861e072395306e9811c329c7fe5bbe8.zip
external_llvm-9c07866ef861e072395306e9811c329c7fe5bbe8.tar.gz
external_llvm-9c07866ef861e072395306e9811c329c7fe5bbe8.tar.bz2
When converting phi nodes into select instructions, we shouldn't promote PHI
nodes unless we KNOW that we are able to promote all of them. This fixes: test/Regression/Transforms/SimplifyCFG/PhiNoEliminate.ll git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@16973 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'lib')
-rw-r--r--lib/Transforms/Utils/SimplifyCFG.cpp134
1 files changed, 93 insertions, 41 deletions
diff --git a/lib/Transforms/Utils/SimplifyCFG.cpp b/lib/Transforms/Utils/SimplifyCFG.cpp
index 77d3fe3..9a6be49 100644
--- a/lib/Transforms/Utils/SimplifyCFG.cpp
+++ b/lib/Transforms/Utils/SimplifyCFG.cpp
@@ -185,7 +185,13 @@ static Value *GetIfCondition(BasicBlock *BB,
// if the specified value dominates the block. We don't handle the true
// generality of domination here, just a special case which works well enough
// for us.
-static bool DominatesMergePoint(Value *V, BasicBlock *BB, bool AllowAggressive){
+//
+// If AggressiveInsts is non-null, and if V does not dominate BB, we check to
+// see if V (which must be an instruction) is cheap to compute and is
+// non-trapping. If both are true, the instruction is inserted into the set and
+// true is returned.
+static bool DominatesMergePoint(Value *V, BasicBlock *BB,
+ std::set<Instruction*> *AggressiveInsts) {
Instruction *I = dyn_cast<Instruction>(V);
if (!I) return true; // Non-instructions all dominate instructions.
BasicBlock *PBB = I->getParent();
@@ -199,7 +205,7 @@ static bool DominatesMergePoint(Value *V, BasicBlock *BB, bool AllowAggressive){
// statement".
if (BranchInst *BI = dyn_cast<BranchInst>(PBB->getTerminator()))
if (BI->isUnconditional() && BI->getSuccessor(0) == BB) {
- if (!AllowAggressive) return false;
+ if (!AggressiveInsts) return false;
// Okay, it looks like the instruction IS in the "condition". Check to
// see if its a cheap instruction to unconditionally compute, and if it
// only uses stuff defined outside of the condition. If so, hoist it out.
@@ -232,9 +238,10 @@ static bool DominatesMergePoint(Value *V, BasicBlock *BB, bool AllowAggressive){
// Okay, we can only really hoist these out if their operands are not
// defined in the conditional region.
for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
- if (!DominatesMergePoint(I->getOperand(i), BB, false))
+ if (!DominatesMergePoint(I->getOperand(i), BB, 0))
return false;
- // Okay, it's safe to do this!
+ // Okay, it's safe to do this! Remember this instruction.
+ AggressiveInsts->insert(I);
}
return true;
@@ -1038,54 +1045,99 @@ bool llvm::SimplifyCFG(BasicBlock *BB) {
DEBUG(std::cerr << "FOUND IF CONDITION! " << *IfCond << " T: "
<< IfTrue->getName() << " F: " << IfFalse->getName() << "\n");
- // Figure out where to insert instructions as necessary.
+ // Loop over the PHI's seeing if we can promote them all to select
+ // instructions. While we are at it, keep track of the instructions
+ // that need to be moved to the dominating block.
+ std::set<Instruction*> AggressiveInsts;
+ bool CanPromote = true;
+
BasicBlock::iterator AfterPHIIt = BB->begin();
- while (isa<PHINode>(AfterPHIIt)) ++AfterPHIIt;
+ while (isa<PHINode>(AfterPHIIt)) {
+ PHINode *PN = cast<PHINode>(AfterPHIIt++);
+ if (PN->getIncomingValue(0) == PN->getIncomingValue(1))
+ PN->replaceAllUsesWith(PN->getIncomingValue(0));
+ else if (!DominatesMergePoint(PN->getIncomingValue(0), BB,
+ &AggressiveInsts) ||
+ !DominatesMergePoint(PN->getIncomingValue(1), BB,
+ &AggressiveInsts)) {
+ CanPromote = false;
+ break;
+ }
+ }
- BasicBlock::iterator I = BB->begin();
- while (PHINode *PN = dyn_cast<PHINode>(I)) {
- ++I;
-
- // If we can eliminate this PHI by directly computing it based on the
- // condition, do so now. We can't eliminate PHI nodes where the
- // incoming values are defined in the conditional parts of the branch,
- // so check for this.
- //
- if (DominatesMergePoint(PN->getIncomingValue(0), BB, true) &&
- DominatesMergePoint(PN->getIncomingValue(1), BB, true)) {
+ // Did we eliminate all PHI's?
+ CanPromote |= AfterPHIIt == BB->begin();
+
+ // If we all PHI nodes are promotable, check to make sure that all
+ // instructions in the predecessor blocks can be promoted as well. If
+ // not, we won't be able to get rid of the control flow, so it's not
+ // worth promoting to select instructions.
+ BasicBlock *DomBlock, *IfBlock1 = 0, *IfBlock2 = 0;
+ if (CanPromote) {
+ PN = cast<PHINode>(BB->begin());
+ BasicBlock *Pred = PN->getIncomingBlock(0);
+ if (cast<BranchInst>(Pred->getTerminator())->isUnconditional()) {
+ IfBlock1 = Pred;
+ DomBlock = *pred_begin(Pred);
+ for (BasicBlock::iterator I = Pred->begin();
+ !isa<TerminatorInst>(I); ++I)
+ if (!AggressiveInsts.count(I)) {
+ // This is not an aggressive instruction that we can promote.
+ // Because of this, we won't be able to get rid of the control
+ // flow, so the xform is not worth it.
+ CanPromote = false;
+ break;
+ }
+ }
+
+ Pred = PN->getIncomingBlock(1);
+ if (CanPromote &&
+ cast<BranchInst>(Pred->getTerminator())->isUnconditional()) {
+ IfBlock2 = Pred;
+ DomBlock = *pred_begin(Pred);
+ for (BasicBlock::iterator I = Pred->begin();
+ !isa<TerminatorInst>(I); ++I)
+ if (!AggressiveInsts.count(I)) {
+ // This is not an aggressive instruction that we can promote.
+ // Because of this, we won't be able to get rid of the control
+ // flow, so the xform is not worth it.
+ CanPromote = false;
+ break;
+ }
+ }
+ }
+
+ // If we can still promote the PHI nodes after this gauntlet of tests,
+ // do all of the PHI's now.
+ if (CanPromote) {
+ // Move all 'aggressive' instructions, which are defined in the
+ // conditional parts of the if's up to the dominating block.
+ if (IfBlock1) {
+ DomBlock->getInstList().splice(DomBlock->getTerminator(),
+ IfBlock1->getInstList(),
+ IfBlock1->begin(),
+ IfBlock1->getTerminator());
+ }
+ if (IfBlock2) {
+ DomBlock->getInstList().splice(DomBlock->getTerminator(),
+ IfBlock2->getInstList(),
+ IfBlock2->begin(),
+ IfBlock2->getTerminator());
+ }
+
+ while (PHINode *PN = dyn_cast<PHINode>(BB->begin())) {
+ // Change the PHI node into a select instruction.
Value *TrueVal =
PN->getIncomingValue(PN->getIncomingBlock(0) == IfFalse);
Value *FalseVal =
PN->getIncomingValue(PN->getIncomingBlock(0) == IfTrue);
- // If one of the incoming values is defined in the conditional
- // region, move it into it's predecessor block, which we know is
- // safe.
- if (!DominatesMergePoint(TrueVal, BB, false)) {
- Instruction *TrueI = cast<Instruction>(TrueVal);
- BasicBlock *OldBB = TrueI->getParent();
- OldBB->getInstList().remove(TrueI);
- BasicBlock *NewBB = *pred_begin(OldBB);
- NewBB->getInstList().insert(NewBB->getTerminator(), TrueI);
- }
- if (!DominatesMergePoint(FalseVal, BB, false)) {
- Instruction *FalseI = cast<Instruction>(FalseVal);
- BasicBlock *OldBB = FalseI->getParent();
- OldBB->getInstList().remove(FalseI);
- BasicBlock *NewBB = *pred_begin(OldBB);
- NewBB->getInstList().insert(NewBB->getTerminator(), FalseI);
- }
-
- // Change the PHI node into a select instruction.
- BasicBlock::iterator InsertPos = PN;
- while (isa<PHINode>(InsertPos)) ++InsertPos;
-
std::string Name = PN->getName(); PN->setName("");
PN->replaceAllUsesWith(new SelectInst(IfCond, TrueVal, FalseVal,
- Name, InsertPos));
+ Name, AfterPHIIt));
BB->getInstList().erase(PN);
- Changed = true;
}
+ Changed = true;
}
}
}