if (PBB->getFirstNonPHIOrDbg() != I)
return false;
break;
+ case Instruction::GetElementPtr:
+ // GEPs are cheap if all indices are constant.
+ if (!cast<GetElementPtrInst>(I)->hasAllConstantIndices())
+ return false;
+ break;
case Instruction::Add:
case Instruction::Sub:
case Instruction::And:
/// Values vector.
static Value *
GatherConstantCompares(Value *V, std::vector<ConstantInt*> &Vals, Value *&Extra,
- const TargetData *TD, bool isEQ) {
+ const TargetData *TD, bool isEQ, unsigned &UsedICmps) {
Instruction *I = dyn_cast<Instruction>(V);
if (I == 0) return 0;
if (ICmpInst *ICI = dyn_cast<ICmpInst>(I)) {
if (ConstantInt *C = GetConstantInt(I->getOperand(1), TD)) {
if (ICI->getPredicate() == (isEQ ? ICmpInst::ICMP_EQ:ICmpInst::ICMP_NE)) {
+ UsedICmps++;
Vals.push_back(C);
return I->getOperand(0);
}
for (APInt Tmp = Span.getLower(); Tmp != Span.getUpper(); ++Tmp)
Vals.push_back(ConstantInt::get(V->getContext(), Tmp));
+ UsedICmps++;
return I->getOperand(0);
}
return 0;
return 0;
unsigned NumValsBeforeLHS = Vals.size();
+ unsigned UsedICmpsBeforeLHS = UsedICmps;
if (Value *LHS = GatherConstantCompares(I->getOperand(0), Vals, Extra, TD,
- isEQ)) {
+ isEQ, UsedICmps)) {
unsigned NumVals = Vals.size();
+ unsigned UsedICmpsBeforeRHS = UsedICmps;
if (Value *RHS = GatherConstantCompares(I->getOperand(1), Vals, Extra, TD,
- isEQ)) {
+ isEQ, UsedICmps)) {
if (LHS == RHS)
return LHS;
Vals.resize(NumVals);
+ UsedICmps = UsedICmpsBeforeRHS;
}
// The RHS of the or/and can't be folded in and we haven't used "Extra" yet,
}
Vals.resize(NumValsBeforeLHS);
+ UsedICmps = UsedICmpsBeforeLHS;
return 0;
}
Value *OldExtra = Extra;
Extra = I->getOperand(0);
if (Value *RHS = GatherConstantCompares(I->getOperand(1), Vals, Extra, TD,
- isEQ))
+ isEQ, UsedICmps))
return RHS;
assert(Vals.size() == NumValsBeforeLHS);
Extra = OldExtra;
BasicBlock::iterator BB2_Itr = BB2->begin();
Instruction *I1 = BB1_Itr++, *I2 = BB2_Itr++;
- while (isa<DbgInfoIntrinsic>(I1))
- I1 = BB1_Itr++;
- while (isa<DbgInfoIntrinsic>(I2))
- I2 = BB2_Itr++;
- if (I1->getOpcode() != I2->getOpcode() || isa<PHINode>(I1) ||
- !I1->isIdenticalToWhenDefined(I2) ||
+ // Skip debug info if it is not identical.
+ DbgInfoIntrinsic *DBI1 = dyn_cast<DbgInfoIntrinsic>(I1);
+ DbgInfoIntrinsic *DBI2 = dyn_cast<DbgInfoIntrinsic>(I2);
+ if (!DBI1 || !DBI2 || !DBI1->isIdenticalToWhenDefined(DBI2)) {
+ while (isa<DbgInfoIntrinsic>(I1))
+ I1 = BB1_Itr++;
+ while (isa<DbgInfoIntrinsic>(I2))
+ I2 = BB2_Itr++;
+ }
+ if (isa<PHINode>(I1) || !I1->isIdenticalToWhenDefined(I2) ||
(isa<InvokeInst>(I1) && !isSafeToHoistInvoke(BB1, BB2, I1, I2)))
return false;
I2->eraseFromParent();
I1 = BB1_Itr++;
- while (isa<DbgInfoIntrinsic>(I1))
- I1 = BB1_Itr++;
I2 = BB2_Itr++;
- while (isa<DbgInfoIntrinsic>(I2))
- I2 = BB2_Itr++;
- } while (I1->getOpcode() == I2->getOpcode() &&
- I1->isIdenticalToWhenDefined(I2));
+ // Skip debug info if it is not identical.
+ DbgInfoIntrinsic *DBI1 = dyn_cast<DbgInfoIntrinsic>(I1);
+ DbgInfoIntrinsic *DBI2 = dyn_cast<DbgInfoIntrinsic>(I2);
+ if (!DBI1 || !DBI2 || !DBI1->isIdenticalToWhenDefined(DBI2)) {
+ while (isa<DbgInfoIntrinsic>(I1))
+ I1 = BB1_Itr++;
+ while (isa<DbgInfoIntrinsic>(I2))
+ I2 = BB2_Itr++;
+ }
+ } while (I1->isIdenticalToWhenDefined(I2));
return true;
return true;
}
-/// FoldBranchToCommonDest - If this basic block is ONLY a setcc and a branch,
-/// and if a predecessor branches to us and one of our successors, fold the
-/// setcc into the predecessor and use logical operations to pick the right
-/// destination.
+/// FoldBranchToCommonDest - If this basic block is simple enough, and if a
+/// predecessor branches to us and one of our successors, fold the block into
+/// the predecessor and use logical operations to pick the right destination.
bool llvm::FoldBranchToCommonDest(BranchInst *BI) {
BasicBlock *BB = BI->getParent();
Instruction *Cond = dyn_cast<Instruction>(BI->getCondition());
if (Cond == 0 || (!isa<CmpInst>(Cond) && !isa<BinaryOperator>(Cond)) ||
Cond->getParent() != BB || !Cond->hasOneUse())
return false;
-
+
+ SmallVector<DbgInfoIntrinsic *, 8> DbgValues;
// Only allow this if the condition is a simple instruction that can be
// executed unconditionally. It must be in the same block as the branch, and
// must be at the front of the block.
BasicBlock::iterator FrontIt = BB->front();
// Ignore dbg intrinsics.
- while (isa<DbgInfoIntrinsic>(FrontIt))
+ while (DbgInfoIntrinsic *DBI = dyn_cast<DbgInfoIntrinsic>(FrontIt)) {
+ DbgValues.push_back(DBI);
++FrontIt;
+ }
// Allow a single instruction to be hoisted in addition to the compare
// that feeds the branch. We later ensure that any values that _it_ uses
++FrontIt;
}
+ // Ignore dbg intrinsics.
+ while (DbgInfoIntrinsic *DBI = dyn_cast<DbgInfoIntrinsic>(FrontIt)) {
+ DbgValues.push_back(DBI);
+ ++FrontIt;
+ }
+
// Only a single bonus inst is allowed.
if (&*FrontIt != Cond)
return false;
// Make sure the instruction after the condition is the cond branch.
BasicBlock::iterator CondIt = Cond; ++CondIt;
// Ingore dbg intrinsics.
- while(isa<DbgInfoIntrinsic>(CondIt))
+ while(DbgInfoIntrinsic *DBI = dyn_cast<DbgInfoIntrinsic>(CondIt)) {
+ DbgValues.push_back(DBI);
++CondIt;
+ }
if (&*CondIt != BI) {
assert (!isa<DbgInfoIntrinsic>(CondIt) && "Hey do not forget debug info!");
return false;
BasicBlock *FalseDest = BI->getSuccessor(1);
if (TrueDest == BB || FalseDest == BB)
return false;
-
+
for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
BasicBlock *PredBlock = *PI;
BranchInst *PBI = dyn_cast<BranchInst>(PredBlock->getTerminator());
AddPredecessorToBlock(FalseDest, PredBlock, BB);
PBI->setSuccessor(1, FalseDest);
}
+
+ // Move dbg value intrinsics in PredBlock.
+ for (SmallVector<DbgInfoIntrinsic *, 8>::iterator DBI = DbgValues.begin(),
+ DBE = DbgValues.end(); DBI != DBE; ++DBI)
+ (*DBI)->moveBefore(PBI);
return true;
}
return false;
// in the constant and simplify the block result. Subsequent passes of
// simplifycfg will thread the block.
if (BlockIsSimpleEnoughToThreadThrough(BB)) {
+ pred_iterator PB = pred_begin(BB), PE = pred_end(BB);
PHINode *NewPN = PHINode::Create(Type::getInt1Ty(BB->getContext()),
+ std::distance(PB, PE),
BI->getCondition()->getName() + ".pr",
BB->begin());
// Okay, we're going to insert the PHI node. Since PBI is not the only
// predecessor, compute the PHI'd conditional value for all of the preds.
// Any predecessor where the condition is not computable we keep symbolic.
- for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
+ for (pred_iterator PI = PB; PI != PE; ++PI) {
BasicBlock *P = *PI;
if ((PBI = dyn_cast<BranchInst>(P->getTerminator())) &&
PBI != BI && PBI->isConditional() &&
return true;
}
+// SimplifySwitchOnSelect - Replaces
+// (switch (select cond, X, Y)) on constant X, Y
+// with a branch - conditional if X and Y lead to distinct BBs,
+// unconditional otherwise.
+static bool SimplifySwitchOnSelect(SwitchInst *SI, SelectInst *Select) {
+ // Check for constant integer values in the select.
+ ConstantInt *TrueVal = dyn_cast<ConstantInt>(Select->getTrueValue());
+ ConstantInt *FalseVal = dyn_cast<ConstantInt>(Select->getFalseValue());
+ if (!TrueVal || !FalseVal)
+ return false;
+
+ // Find the relevant condition and destinations.
+ Value *Condition = Select->getCondition();
+ BasicBlock *TrueBB = SI->getSuccessor(SI->findCaseValue(TrueVal));
+ BasicBlock *FalseBB = SI->getSuccessor(SI->findCaseValue(FalseVal));
+
+ // Perform the actual simplification.
+ return SimplifyTerminatorOnSelect(SI, Condition, TrueBB, FalseBB);
+}
+
// SimplifyIndirectBrOnSelect - Replaces
// (indirectbr (select cond, blockaddress(@fn, BlockA),
// blockaddress(@fn, BlockB)))
std::vector<ConstantInt*> Values;
bool TrueWhenEqual = true;
Value *ExtraCase = 0;
+ unsigned UsedICmps = 0;
if (Cond->getOpcode() == Instruction::Or) {
- CompVal = GatherConstantCompares(Cond, Values, ExtraCase, TD, true);
+ CompVal = GatherConstantCompares(Cond, Values, ExtraCase, TD, true,
+ UsedICmps);
} else if (Cond->getOpcode() == Instruction::And) {
- CompVal = GatherConstantCompares(Cond, Values, ExtraCase, TD, false);
+ CompVal = GatherConstantCompares(Cond, Values, ExtraCase, TD, false,
+ UsedICmps);
TrueWhenEqual = false;
}
// If we didn't have a multiply compared value, fail.
if (CompVal == 0) return false;
+ // Avoid turning single icmps into a switch.
+ if (UsedICmps <= 1)
+ return false;
+
// There might be duplicate constants in the list, which the switch
// instruction can't handle, remove them now.
array_pod_sort(Values.begin(), Values.end(), ConstantIntSortPredicate);
if (LI->isVolatile())
break;
- // Delete this instruction
+ // Delete this instruction (any uses are guaranteed to be dead)
+ if (!BBI->use_empty())
+ BBI->replaceAllUsesWith(UndefValue::get(BBI->getType()));
BBI->eraseFromParent();
Changed = true;
}
// If the default value is unreachable, figure out the most popular
// destination and make it the default.
if (SI->getSuccessor(0) == BB) {
- std::map<BasicBlock*, unsigned> Popularity;
- for (unsigned i = 1, e = SI->getNumCases(); i != e; ++i)
- Popularity[SI->getSuccessor(i)]++;
-
+ std::map<BasicBlock*, std::pair<unsigned, unsigned> > Popularity;
+ for (unsigned i = 1, e = SI->getNumCases(); i != e; ++i) {
+ std::pair<unsigned, unsigned>& entry =
+ Popularity[SI->getSuccessor(i)];
+ if (entry.first == 0) {
+ entry.first = 1;
+ entry.second = i;
+ } else {
+ entry.first++;
+ }
+ }
+
// Find the most popular block.
unsigned MaxPop = 0;
+ unsigned MaxIndex = 0;
BasicBlock *MaxBlock = 0;
- for (std::map<BasicBlock*, unsigned>::iterator
+ for (std::map<BasicBlock*, std::pair<unsigned, unsigned> >::iterator
I = Popularity.begin(), E = Popularity.end(); I != E; ++I) {
- if (I->second > MaxPop) {
- MaxPop = I->second;
+ if (I->second.first > MaxPop ||
+ (I->second.first == MaxPop && MaxIndex > I->second.second)) {
+ MaxPop = I->second.first;
+ MaxIndex = I->second.second;
MaxBlock = I->first;
}
}
return Changed;
}
+/// TurnSwitchRangeIntoICmp - Turns a switch with that contains only a
+/// integer range comparison into a sub, an icmp and a branch.
+static bool TurnSwitchRangeIntoICmp(SwitchInst *SI) {
+ assert(SI->getNumCases() > 2 && "Degenerate switch?");
+
+ // Make sure all cases point to the same destination and gather the values.
+ SmallVector<ConstantInt *, 16> Cases;
+ Cases.push_back(SI->getCaseValue(1));
+ for (unsigned I = 2, E = SI->getNumCases(); I != E; ++I) {
+ if (SI->getSuccessor(I-1) != SI->getSuccessor(I))
+ return false;
+ Cases.push_back(SI->getCaseValue(I));
+ }
+ assert(Cases.size() == SI->getNumCases()-1 && "Not all cases gathered");
+
+ // Sort the case values, then check if they form a range we can transform.
+ array_pod_sort(Cases.begin(), Cases.end(), ConstantIntSortPredicate);
+ for (unsigned I = 1, E = Cases.size(); I != E; ++I) {
+ if (Cases[I-1]->getValue() != Cases[I]->getValue()+1)
+ return false;
+ }
+
+ Constant *Offset = ConstantExpr::getNeg(Cases.back());
+ Constant *NumCases = ConstantInt::get(Offset->getType(), SI->getNumCases()-1);
+
+ Value *Sub = SI->getCondition();
+ if (!Offset->isNullValue())
+ Sub = BinaryOperator::CreateAdd(Sub, Offset, Sub->getName()+".off", SI);
+ Value *Cmp = new ICmpInst(SI, ICmpInst::ICMP_ULT, Sub, NumCases, "switch");
+ BranchInst::Create(SI->getSuccessor(1), SI->getDefaultDest(), Cmp, SI);
+
+ // Prune obsolete incoming values off the successor's PHI nodes.
+ for (BasicBlock::iterator BBI = SI->getSuccessor(1)->begin();
+ isa<PHINode>(BBI); ++BBI) {
+ for (unsigned I = 0, E = SI->getNumCases()-2; I != E; ++I)
+ cast<PHINode>(BBI)->removeIncomingValue(SI->getParent());
+ }
+ SI->eraseFromParent();
+
+ return true;
+}
bool SimplifyCFGOpt::SimplifySwitch(SwitchInst *SI) {
// If this switch is too complex to want to look at, ignore it.
if (BasicBlock *OnlyPred = BB->getSinglePredecessor())
if (SimplifyEqualityComparisonWithOnlyPredecessor(SI, OnlyPred))
return SimplifyCFG(BB) | true;
-
+
+ Value *Cond = SI->getCondition();
+ if (SelectInst *Select = dyn_cast<SelectInst>(Cond))
+ if (SimplifySwitchOnSelect(SI, Select))
+ return SimplifyCFG(BB) | true;
+
// If the block only contains the switch, see if we can fold the block
// away into any preds.
BasicBlock::iterator BBI = BB->begin();
if (SI == &*BBI)
if (FoldValueComparisonIntoPredecessors(SI))
return SimplifyCFG(BB) | true;
+
+ // Try to transform the switch into an icmp and a branch.
+ if (TurnSwitchRangeIntoICmp(SI))
+ return SimplifyCFG(BB) | true;
return false;
}
projects / oota-llvm.git / blobdiff