//===- SimplifyCFG.cpp - Code to perform CFG simplification ---------------===//
-//
+//
// The LLVM Compiler Infrastructure
//
// This file was developed by the LLVM research group and is distributed under
// the University of Illinois Open Source License. See LICENSE.TXT for details.
-//
+//
//===----------------------------------------------------------------------===//
//
// Peephole optimize the CFG.
#include <map>
using namespace llvm;
-// PropagatePredecessorsForPHIs - This gets "Succ" ready to have the
-// predecessors from "BB". This is a little tricky because "Succ" has PHI
-// nodes, which need to have extra slots added to them to hold the merge edges
-// from BB's predecessors, and BB itself might have had PHI nodes in it. This
-// function returns true (failure) if the Succ BB already has a predecessor that
-// is a predecessor of BB and incoming PHI arguments would not be discernible.
+/// SafeToMergeTerminators - Return true if it is safe to merge these two
+/// terminator instructions together.
+///
+static bool SafeToMergeTerminators(TerminatorInst *SI1, TerminatorInst *SI2) {
+ if (SI1 == SI2) return false; // Can't merge with self!
+
+ // It is not safe to merge these two switch instructions if they have a common
+ // successor, and if that successor has a PHI node, and if *that* PHI node has
+ // conflicting incoming values from the two switch blocks.
+ BasicBlock *SI1BB = SI1->getParent();
+ BasicBlock *SI2BB = SI2->getParent();
+ std::set<BasicBlock*> SI1Succs(succ_begin(SI1BB), succ_end(SI1BB));
+
+ for (succ_iterator I = succ_begin(SI2BB), E = succ_end(SI2BB); I != E; ++I)
+ if (SI1Succs.count(*I))
+ for (BasicBlock::iterator BBI = (*I)->begin();
+ isa<PHINode>(BBI); ++BBI) {
+ PHINode *PN = cast<PHINode>(BBI);
+ if (PN->getIncomingValueForBlock(SI1BB) !=
+ PN->getIncomingValueForBlock(SI2BB))
+ return false;
+ }
+
+ return true;
+}
+
+/// AddPredecessorToBlock - Update PHI nodes in Succ to indicate that there will
+/// now be entries in it from the 'NewPred' block. The values that will be
+/// flowing into the PHI nodes will be the same as those coming in from
+/// ExistPred, an existing predecessor of Succ.
+static void AddPredecessorToBlock(BasicBlock *Succ, BasicBlock *NewPred,
+ BasicBlock *ExistPred) {
+ assert(std::find(succ_begin(ExistPred), succ_end(ExistPred), Succ) !=
+ succ_end(ExistPred) && "ExistPred is not a predecessor of Succ!");
+ if (!isa<PHINode>(Succ->begin())) return; // Quick exit if nothing to do
+
+ for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) {
+ PHINode *PN = cast<PHINode>(I);
+ Value *V = PN->getIncomingValueForBlock(ExistPred);
+ PN->addIncoming(V, NewPred);
+ }
+}
+
+// CanPropagatePredecessorsForPHIs - Return true if we can fold BB, an
+// almost-empty BB ending in an unconditional branch to Succ, into succ.
//
// Assumption: Succ is the single successor for BB.
//
-static bool PropagatePredecessorsForPHIs(BasicBlock *BB, BasicBlock *Succ) {
+static bool CanPropagatePredecessorsForPHIs(BasicBlock *BB, BasicBlock *Succ) {
assert(*succ_begin(BB) == Succ && "Succ is not successor of BB!");
- if (!isa<PHINode>(Succ->front()))
- return false; // We can make the transformation, no problem.
-
- // If there is more than one predecessor, and there are PHI nodes in
- // the successor, then we need to add incoming edges for the PHI nodes
- //
- const std::vector<BasicBlock*> BBPreds(pred_begin(BB), pred_end(BB));
-
// Check to see if one of the predecessors of BB is already a predecessor of
// Succ. If so, we cannot do the transformation if there are any PHI nodes
// with incompatible values coming in from the two edges!
//
- for (pred_iterator PI = pred_begin(Succ), PE = pred_end(Succ); PI != PE; ++PI)
- if (std::find(BBPreds.begin(), BBPreds.end(), *PI) != BBPreds.end()) {
- // Loop over all of the PHI nodes checking to see if there are
- // incompatible values coming in.
- for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) {
- PHINode *PN = cast<PHINode>(I);
- // Loop up the entries in the PHI node for BB and for *PI if the values
- // coming in are non-equal, we cannot merge these two blocks (instead we
- // should insert a conditional move or something, then merge the
- // blocks).
- int Idx1 = PN->getBasicBlockIndex(BB);
- int Idx2 = PN->getBasicBlockIndex(*PI);
- assert(Idx1 != -1 && Idx2 != -1 &&
- "Didn't have entries for my predecessors??");
- if (PN->getIncomingValue(Idx1) != PN->getIncomingValue(Idx2))
- return true; // Values are not equal...
+ if (isa<PHINode>(Succ->front())) {
+ std::set<BasicBlock*> BBPreds(pred_begin(BB), pred_end(BB));
+ for (pred_iterator PI = pred_begin(Succ), PE = pred_end(Succ);\
+ PI != PE; ++PI)
+ if (std::find(BBPreds.begin(), BBPreds.end(), *PI) != BBPreds.end()) {
+ // Loop over all of the PHI nodes checking to see if there are
+ // incompatible values coming in.
+ for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) {
+ PHINode *PN = cast<PHINode>(I);
+ // Loop up the entries in the PHI node for BB and for *PI if the
+ // values coming in are non-equal, we cannot merge these two blocks
+ // (instead we should insert a conditional move or something, then
+ // merge the blocks).
+ if (PN->getIncomingValueForBlock(BB) !=
+ PN->getIncomingValueForBlock(*PI))
+ return false; // Values are not equal...
+ }
}
+ }
+
+ // Finally, if BB has PHI nodes that are used by things other than the PHIs in
+ // Succ and Succ has predecessors that are not Succ and not Pred, we cannot
+ // fold these blocks, as we don't know whether BB dominates Succ or not to
+ // update the PHI nodes correctly.
+ if (!isa<PHINode>(BB->begin()) || Succ->getSinglePredecessor()) return true;
+
+ // If the predecessors of Succ are only BB and Succ itself, we can handle this.
+ bool IsSafe = true;
+ for (pred_iterator PI = pred_begin(Succ), E = pred_end(Succ); PI != E; ++PI)
+ if (*PI != Succ && *PI != BB) {
+ IsSafe = false;
+ break;
}
-
- // Loop over all of the PHI nodes in the successor BB.
- for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) {
+ if (IsSafe) return true;
+
+ // If the PHI nodes in BB are only used by instructions in Succ, we are ok.
+ IsSafe = true;
+ for (BasicBlock::iterator I = BB->begin(); isa<PHINode>(I) && IsSafe; ++I) {
PHINode *PN = cast<PHINode>(I);
- Value *OldVal = PN->removeIncomingValue(BB, false);
- assert(OldVal && "No entry in PHI for Pred BB!");
-
- // If this incoming value is one of the PHI nodes in BB, the new entries in
- // the PHI node are the entries from the old PHI.
- if (isa<PHINode>(OldVal) && cast<PHINode>(OldVal)->getParent() == BB) {
- PHINode *OldValPN = cast<PHINode>(OldVal);
- for (unsigned i = 0, e = OldValPN->getNumIncomingValues(); i != e; ++i)
- PN->addIncoming(OldValPN->getIncomingValue(i),
- OldValPN->getIncomingBlock(i));
- } else {
- for (std::vector<BasicBlock*>::const_iterator PredI = BBPreds.begin(),
+ for (Value::use_iterator UI = PN->use_begin(), E = PN->use_end(); UI != E;
+ ++UI)
+ if (cast<Instruction>(*UI)->getParent() != Succ) {
+ IsSafe = false;
+ break;
+ }
+ }
+
+ return IsSafe;
+}
+
+/// TryToSimplifyUncondBranchFromEmptyBlock - BB contains an unconditional
+/// branch to Succ, and contains no instructions other than PHI nodes and the
+/// branch. If possible, eliminate BB.
+static bool TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB,
+ BasicBlock *Succ) {
+ // If our successor has PHI nodes, then we need to update them to include
+ // entries for BB's predecessors, not for BB itself. Be careful though,
+ // if this transformation fails (returns true) then we cannot do this
+ // transformation!
+ //
+ if (!CanPropagatePredecessorsForPHIs(BB, Succ)) return false;
+
+ DEBUG(std::cerr << "Killing Trivial BB: \n" << *BB);
+
+ if (isa<PHINode>(Succ->begin())) {
+ // If there is more than one pred of succ, and there are PHI nodes in
+ // the successor, then we need to add incoming edges for the PHI nodes
+ //
+ const std::vector<BasicBlock*> BBPreds(pred_begin(BB), pred_end(BB));
+
+ // Loop over all of the PHI nodes in the successor of BB.
+ for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) {
+ PHINode *PN = cast<PHINode>(I);
+ Value *OldVal = PN->removeIncomingValue(BB, false);
+ assert(OldVal && "No entry in PHI for Pred BB!");
+
+ // If this incoming value is one of the PHI nodes in BB, the new entries
+ // in the PHI node are the entries from the old PHI.
+ if (isa<PHINode>(OldVal) && cast<PHINode>(OldVal)->getParent() == BB) {
+ PHINode *OldValPN = cast<PHINode>(OldVal);
+ for (unsigned i = 0, e = OldValPN->getNumIncomingValues(); i != e; ++i)
+ PN->addIncoming(OldValPN->getIncomingValue(i),
+ OldValPN->getIncomingBlock(i));
+ } else {
+ for (std::vector<BasicBlock*>::const_iterator PredI = BBPreds.begin(),
End = BBPreds.end(); PredI != End; ++PredI) {
- // Add an incoming value for each of the new incoming values...
- PN->addIncoming(OldVal, *PredI);
+ // Add an incoming value for each of the new incoming values...
+ PN->addIncoming(OldVal, *PredI);
+ }
}
}
}
- return false;
+
+ if (isa<PHINode>(&BB->front())) {
+ std::vector<BasicBlock*>
+ OldSuccPreds(pred_begin(Succ), pred_end(Succ));
+
+ // Move all PHI nodes in BB to Succ if they are alive, otherwise
+ // delete them.
+ while (PHINode *PN = dyn_cast<PHINode>(&BB->front()))
+ if (PN->use_empty()) {
+ // Just remove the dead phi. This happens if Succ's PHIs were the only
+ // users of the PHI nodes.
+ PN->eraseFromParent();
+ } else {
+ // The instruction is alive, so this means that Succ must have
+ // *ONLY* had BB as a predecessor, and the PHI node is still valid
+ // now. Simply move it into Succ, because we know that BB
+ // strictly dominated Succ.
+ Succ->getInstList().splice(Succ->begin(),
+ BB->getInstList(), BB->begin());
+
+ // We need to add new entries for the PHI node to account for
+ // predecessors of Succ that the PHI node does not take into
+ // account. At this point, since we know that BB dominated succ,
+ // this means that we should any newly added incoming edges should
+ // use the PHI node as the value for these edges, because they are
+ // loop back edges.
+ for (unsigned i = 0, e = OldSuccPreds.size(); i != e; ++i)
+ if (OldSuccPreds[i] != BB)
+ PN->addIncoming(PN, OldSuccPreds[i]);
+ }
+ }
+
+ // Everything that jumped to BB now goes to Succ.
+ std::string OldName = BB->getName();
+ BB->replaceAllUsesWith(Succ);
+ BB->eraseFromParent(); // Delete the old basic block.
+
+ if (!OldName.empty() && !Succ->hasName()) // Transfer name if we can
+ Succ->setName(OldName);
+ return true;
}
/// GetIfCondition - Given a basic block (BB) with two predecessors (and
/// which entry into BB will be taken. Also, return by references the block
/// that will be entered from if the condition is true, and the block that will
/// be entered if the condition is false.
-///
+///
///
static Value *GetIfCondition(BasicBlock *BB,
BasicBlock *&IfTrue, BasicBlock *&IfFalse) {
case Instruction::Xor:
case Instruction::Shl:
case Instruction::Shr:
+ case Instruction::SetEQ:
+ case Instruction::SetNE:
+ case Instruction::SetLT:
+ case Instruction::SetGT:
+ case Instruction::SetLE:
+ case Instruction::SetGE:
break; // These are all cheap and non-trapping instructions.
}
-
+
// 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)
return true;
} else if (Cond->getOpcode() == Instruction::And) {
CompVal = GatherConstantSetNEs(Cond, Values);
-
+
// Return false to indicate that the condition is false if the CompVal is
// equal to one of the constants.
return false;
}
}
-/// SafeToMergeTerminators - Return true if it is safe to merge these two
-/// terminator instructions together.
-///
-static bool SafeToMergeTerminators(TerminatorInst *SI1, TerminatorInst *SI2) {
- if (SI1 == SI2) return false; // Can't merge with self!
-
- // It is not safe to merge these two switch instructions if they have a common
- // successor, and if that successor has a PHI node, and if *that* PHI node has
- // conflicting incoming values from the two switch blocks.
- BasicBlock *SI1BB = SI1->getParent();
- BasicBlock *SI2BB = SI2->getParent();
- std::set<BasicBlock*> SI1Succs(succ_begin(SI1BB), succ_end(SI1BB));
-
- for (succ_iterator I = succ_begin(SI2BB), E = succ_end(SI2BB); I != E; ++I)
- if (SI1Succs.count(*I))
- for (BasicBlock::iterator BBI = (*I)->begin();
- isa<PHINode>(BBI); ++BBI) {
- PHINode *PN = cast<PHINode>(BBI);
- if (PN->getIncomingValueForBlock(SI1BB) !=
- PN->getIncomingValueForBlock(SI2BB))
- return false;
- }
-
- return true;
-}
-
-/// AddPredecessorToBlock - Update PHI nodes in Succ to indicate that there will
-/// now be entries in it from the 'NewPred' block. The values that will be
-/// flowing into the PHI nodes will be the same as those coming in from
-/// ExistPred, an existing predecessor of Succ.
-static void AddPredecessorToBlock(BasicBlock *Succ, BasicBlock *NewPred,
- BasicBlock *ExistPred) {
- assert(std::find(succ_begin(ExistPred), succ_end(ExistPred), Succ) !=
- succ_end(ExistPred) && "ExistPred is not a predecessor of Succ!");
- if (!isa<PHINode>(Succ->begin())) return; // Quick exit if nothing to do
-
- for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) {
- PHINode *PN = cast<PHINode>(I);
- Value *V = PN->getIncomingValueForBlock(ExistPred);
- PN->addIncoming(V, NewPred);
- }
-}
-
// isValueEqualityComparison - Return true if the specified terminator checks to
// see if a value is equal to constant integer value.
static Value *isValueEqualityComparison(TerminatorInst *TI) {
if (BI->isConditional() && BI->getCondition()->hasOneUse())
if (SetCondInst *SCI = dyn_cast<SetCondInst>(BI->getCondition()))
if ((SCI->getOpcode() == Instruction::SetEQ ||
- SCI->getOpcode() == Instruction::SetNE) &&
+ SCI->getOpcode() == Instruction::SetNE) &&
isa<ConstantInt>(SCI->getOperand(1)))
return SCI->getOperand(0);
return 0;
// Given a value comparison instruction, decode all of the 'cases' that it
// represents and return the 'default' block.
static BasicBlock *
-GetValueEqualityComparisonCases(TerminatorInst *TI,
+GetValueEqualityComparisonCases(TerminatorInst *TI,
std::vector<std::pair<ConstantInt*,
BasicBlock*> > &Cases) {
if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
// EliminateBlockCases - Given an vector of bb/value pairs, remove any entries
// in the list that match the specified block.
-static void EliminateBlockCases(BasicBlock *BB,
+static void EliminateBlockCases(BasicBlock *BB,
std::vector<std::pair<ConstantInt*, BasicBlock*> > &Cases) {
for (unsigned i = 0, e = Cases.size(); i != e; ++i)
if (Cases[i].second == BB) {
BasicBlock *PredDef = GetValueEqualityComparisonCases(Pred->getTerminator(),
PredCases);
EliminateBlockCases(PredDef, PredCases); // Remove default from cases.
-
+
// Find information about how control leaves this block.
std::vector<std::pair<ConstantInt*, BasicBlock*> > ThisCases;
BasicBlock *ThisDef = GetValueEqualityComparisonCases(TI, ThisCases);
while (!Preds.empty()) {
BasicBlock *Pred = Preds.back();
Preds.pop_back();
-
+
// See if the predecessor is a comparison with the same value.
TerminatorInst *PTI = Pred->getTerminator();
Value *PCV = isValueEqualityComparison(PTI); // PredCondVal
}
NewSI->setSuccessor(i, InfLoopBlock);
}
-
+
Changed = true;
}
}
// broken BB), instead clone it, and remove BI.
if (isa<TerminatorInst>(I1))
goto HoistTerminator;
-
+
// For a normal instruction, we just move one to right before the branch,
// then replace all uses of the other with the first. Finally, we remove
// the now redundant second instruction.
if (!I2->use_empty())
I2->replaceAllUsesWith(I1);
BB2->getInstList().erase(I2);
-
+
I1 = BB1->begin();
I2 = BB2->begin();
} while (I1->getOpcode() == I2->getOpcode() && I1->isIdenticalTo(I2));
// Update any PHI nodes in our new successors.
for (succ_iterator SI = succ_begin(BB1), E = succ_end(BB1); SI != E; ++SI)
AddPredecessorToBlock(*SI, BIParent, BB1);
-
+
BI->eraseFromParent();
return true;
}
};
}
-
// SimplifyCFG - This function is used to do simplification of a CFG. For
// example, it adjusts branches to branches to eliminate the extra hop, it
// eliminates unreachable basic blocks, and does other "peephole" optimization
// Loop through all of our successors and make sure they know that one
// of their predecessors is going away.
- for_each(succ_begin(BB), succ_end(BB),
- std::bind2nd(std::mem_fun(&BasicBlock::removePredecessor), BB));
+ for (succ_iterator SI = succ_begin(BB), E = succ_end(BB); SI != E; ++SI)
+ SI->removePredecessor(BB);
while (!BB->empty()) {
Instruction &I = BB->back();
// If this instruction is used, replace uses with an arbitrary
- // constant value. Because control flow can't get here, we don't care
- // what we replace the value with. Note that since this block is
+ // value. Because control flow can't get here, we don't care
+ // what we replace the value with. Note that since this block is
// unreachable, and all values contained within it must dominate their
// uses, that all uses will eventually be removed.
- if (!I.use_empty())
- // Make all users of this instruction reference the constant instead
- I.replaceAllUsesWith(Constant::getNullValue(I.getType()));
-
+ if (!I.use_empty())
+ // Make all users of this instruction use undef instead
+ I.replaceAllUsesWith(UndefValue::get(I.getType()));
+
// Remove the instruction from the basic block
BB->getInstList().pop_back();
}
// away...
Changed |= ConstantFoldTerminator(BB);
- // Check to see if this block has no non-phi instructions and only a single
- // successor. If so, replace references to this basic block with references
- // to the successor.
- succ_iterator SI(succ_begin(BB));
- if (SI != succ_end(BB) && ++SI == succ_end(BB)) { // One succ?
- BasicBlock::iterator BBI = BB->begin(); // Skip over phi nodes...
- while (isa<PHINode>(*BBI)) ++BBI;
-
- BasicBlock *Succ = *succ_begin(BB); // There is exactly one successor.
- if (BBI->isTerminator() && // Terminator is the only non-phi instruction!
- Succ != BB) { // Don't hurt infinite loops!
- // If our successor has PHI nodes, then we need to update them to include
- // entries for BB's predecessors, not for BB itself. Be careful though,
- // if this transformation fails (returns true) then we cannot do this
- // transformation!
- //
- if (!PropagatePredecessorsForPHIs(BB, Succ)) {
- DEBUG(std::cerr << "Killing Trivial BB: \n" << *BB);
-
- if (isa<PHINode>(&BB->front())) {
- std::vector<BasicBlock*>
- OldSuccPreds(pred_begin(Succ), pred_end(Succ));
-
- // Move all PHI nodes in BB to Succ if they are alive, otherwise
- // delete them.
- while (PHINode *PN = dyn_cast<PHINode>(&BB->front()))
- if (PN->use_empty())
- BB->getInstList().erase(BB->begin()); // Nuke instruction.
- else {
- // The instruction is alive, so this means that Succ must have
- // *ONLY* had BB as a predecessor, and the PHI node is still valid
- // now. Simply move it into Succ, because we know that BB
- // strictly dominated Succ.
- BB->getInstList().remove(BB->begin());
- Succ->getInstList().push_front(PN);
-
- // We need to add new entries for the PHI node to account for
- // predecessors of Succ that the PHI node does not take into
- // account. At this point, since we know that BB dominated succ,
- // this means that we should any newly added incoming edges should
- // use the PHI node as the value for these edges, because they are
- // loop back edges.
- for (unsigned i = 0, e = OldSuccPreds.size(); i != e; ++i)
- if (OldSuccPreds[i] != BB)
- PN->addIncoming(PN, OldSuccPreds[i]);
- }
- }
-
- // Everything that jumped to BB now goes to Succ.
- std::string OldName = BB->getName();
- BB->replaceAllUsesWith(Succ);
- BB->eraseFromParent(); // Delete the old basic block.
-
- if (!OldName.empty() && !Succ->hasName()) // Transfer name if we can
- Succ->setName(OldName);
- return true;
- }
- }
- }
-
// If this is a returning block with only PHI nodes in it, fold the return
// instruction into any unconditional branch predecessors.
//
else
CondBranchPreds.push_back(BI);
}
-
+
// If we found some, do the transformation!
if (!UncondBranchPreds.empty()) {
while (!UncondBranchPreds.empty()) {
// is now a fall through...
BranchInst *BI = new BranchInst(II->getNormalDest(), II);
Pred->getInstList().remove(II); // Take out of symbol table
-
+
// Insert the call now...
std::vector<Value*> Args(II->op_begin()+3, II->op_end());
CallInst *CI = new CallInst(II->getCalledValue(), Args,
II->getName(), BI);
+ CI->setCallingConv(II->getCallingConv());
// If the invoke produced a value, the Call now does instead
II->replaceAllUsesWith(CI);
delete II;
Changed = true;
}
-
+
Preds.pop_back();
}
return SimplifyCFG(BB) || 1;
}
} else if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator())) {
- if (BI->isConditional()) {
+ if (BI->isUnconditional()) {
+ BasicBlock::iterator BBI = BB->begin(); // Skip over phi nodes...
+ while (isa<PHINode>(*BBI)) ++BBI;
+
+ BasicBlock *Succ = BI->getSuccessor(0);
+ if (BBI->isTerminator() && // Terminator is the only non-phi instruction!
+ Succ != BB) // Don't hurt infinite loops!
+ if (TryToSimplifyUncondBranchFromEmptyBlock(BB, Succ))
+ return 1;
+
+ } else { // Conditional branch
if (Value *CompVal = isValueEqualityComparison(BI)) {
// If we only have one predecessor, and if it is a branch on this value,
// see if that predecessor totally determines the outcome of this
Instruction::BinaryOps Opcode =
PBI->getSuccessor(0) == TrueDest ?
Instruction::Or : Instruction::And;
- Value *NewCond =
+ Value *NewCond =
BinaryOperator::create(Opcode, PBI->getCondition(),
New, "bothcond", PBI);
PBI->setCondition(NewCond);
// If this block ends with a branch instruction, and if there is one
// predecessor, see if the previous block ended with a branch on the same
// condition, which makes this conditional branch redundant.
- pred_iterator PI(pred_begin(BB)), PE(pred_end(BB));
- BasicBlock *OnlyPred = *PI++;
- for (; PI != PE; ++PI)// Search all predecessors, see if they are all same
- if (*PI != OnlyPred) {
- OnlyPred = 0; // There are multiple different predecessors...
- break;
- }
-
- if (OnlyPred)
+ if (BasicBlock *OnlyPred = BB->getSinglePredecessor())
if (BranchInst *PBI = dyn_cast<BranchInst>(OnlyPred->getTerminator()))
if (PBI->isConditional() &&
PBI->getCondition() == BI->getCondition() &&
} else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
for (unsigned i = 1, e = SI->getNumCases(); i != e; ++i)
if (SI->getSuccessor(i) == BB) {
+ BB->removePredecessor(SI->getParent());
SI->removeCase(i);
--i; --e;
Changed = true;
SI->setSuccessor(0, MaxBlock);
Changed = true;
+ // If MaxBlock has phinodes in it, remove MaxPop-1 entries from
+ // it.
+ if (isa<PHINode>(MaxBlock->begin()))
+ for (unsigned i = 0; i != MaxPop-1; ++i)
+ MaxBlock->removePredecessor(SI->getParent());
+
for (unsigned i = 1, e = SI->getNumCases(); i != e; ++i)
if (SI->getSuccessor(i) == MaxBlock) {
SI->removeCase(i);
// place to note that the call does not throw though.
BranchInst *BI = new BranchInst(II->getNormalDest(), II);
II->removeFromParent(); // Take out of symbol table
-
+
// Insert the call now...
std::vector<Value*> Args(II->op_begin()+3, II->op_end());
CallInst *CI = new CallInst(II->getCalledValue(), Args,
II->getName(), BI);
+ CI->setCallingConv(II->getCallingConv());
// If the invoke produced a value, the Call does now instead.
II->replaceAllUsesWith(CI);
delete II;
// Delete the unconditional branch from the predecessor...
OnlyPred->getInstList().pop_back();
-
+
// Move all definitions in the successor to the predecessor...
OnlyPred->getInstList().splice(OnlyPred->end(), BB->getInstList());
-
+
// Make all PHI nodes that referred to BB now refer to Pred as their
// source...
BB->replaceAllUsesWith(OnlyPred);
std::string OldName = BB->getName();
- // Erase basic block from the function...
+ // Erase basic block from the function...
M->getBasicBlockList().erase(BB);
// Inherit predecessors name if it exists...
if (!OldName.empty() && !OnlyPred->hasName())
OnlyPred->setName(OldName);
-
+
return true;
}
// instruction can't handle, remove them now.
std::sort(Values.begin(), Values.end(), ConstantIntOrdering());
Values.erase(std::unique(Values.begin(), Values.end()), Values.end());
-
+
// Figure out which block is which destination.
BasicBlock *DefaultBB = BI->getSuccessor(1);
BasicBlock *EdgeBB = BI->getSuccessor(0);
if (!TrueWhenEqual) std::swap(DefaultBB, EdgeBB);
-
+
// Create the new switch instruction now.
SwitchInst *New = new SwitchInst(CompVal, DefaultBB,Values.size(),BI);
-
+
// Add all of the 'cases' to the switch instruction.
for (unsigned i = 0, e = Values.size(); i != e; ++i)
New->addCase(Values[i], EdgeBB);
-
+
// We added edges from PI to the EdgeBB. As such, if there were any
// PHI nodes in EdgeBB, they need entries to be added corresponding to
// the number of edges added.
BasicBlock::iterator AfterPHIIt = BB->begin();
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)) {
+ if (PN->getIncomingValue(0) == PN->getIncomingValue(1)) {
+ if (PN->getIncomingValue(0) != PN)
+ PN->replaceAllUsesWith(PN->getIncomingValue(0));
+ else
+ PN->replaceAllUsesWith(UndefValue::get(PN->getType()));
+ } else if (!DominatesMergePoint(PN->getIncomingValue(0), BB,
+ &AggressiveInsts) ||
+ !DominatesMergePoint(PN->getIncomingValue(1), BB,
+ &AggressiveInsts)) {
CanPromote = false;
break;
}
}
Pred = PN->getIncomingBlock(1);
- if (CanPromote &&
+ if (CanPromote &&
cast<BranchInst>(Pred->getTerminator())->isUnconditional()) {
IfBlock2 = Pred;
DomBlock = *pred_begin(Pred);
}
}
}
-
+
return Changed;
}
projects / oota-llvm.git / blobdiff