#define DEBUG_TYPE "simplifycfg"
+// Chosen as 2 so as to be cheap, but still to have enough power to fold
+// a select, so the "clamp" idiom (of a min followed by a max) will be caught.
+// To catch this, we need to fold a compare and a select, hence '2' being the
+// minimum reasonable default.
static cl::opt<unsigned>
-PHINodeFoldingThreshold("phi-node-folding-threshold", cl::Hidden, cl::init(1),
- cl::desc("Control the amount of phi node folding to perform (default = 1)"));
+PHINodeFoldingThreshold("phi-node-folding-threshold", cl::Hidden, cl::init(2),
+ cl::desc("Control the amount of phi node folding to perform (default = 2)"));
static cl::opt<bool>
DupRet("simplifycfg-dup-ret", cl::Hidden, cl::init(false),
STATISTIC(NumLinearMaps, "Number of switch instructions turned into linear mapping");
STATISTIC(NumLookupTables, "Number of switch instructions turned into lookup tables");
STATISTIC(NumLookupTablesHoles, "Number of switch instructions turned into lookup tables (holes checked)");
+STATISTIC(NumTableCmpReuses, "Number of reused switch table lookup compares");
STATISTIC(NumSinkCommons, "Number of common instructions sunk down to the end block");
STATISTIC(NumSpeculations, "Number of speculative executed instructions");
class SimplifyCFGOpt {
const TargetTransformInfo &TTI;
+ const DataLayout &DL;
unsigned BonusInstThreshold;
- const DataLayout *const DL;
- AssumptionTracker *AT;
+ AssumptionCache *AC;
Value *isValueEqualityComparison(TerminatorInst *TI);
BasicBlock *GetValueEqualityComparisonCases(TerminatorInst *TI,
std::vector<ValueEqualityComparisonCase> &Cases);
bool SimplifyCondBranch(BranchInst *BI, IRBuilder <>&Builder);
public:
- SimplifyCFGOpt(const TargetTransformInfo &TTI, unsigned BonusInstThreshold,
- const DataLayout *DL, AssumptionTracker *AT)
- : TTI(TTI), BonusInstThreshold(BonusInstThreshold), DL(DL), AT(AT) {}
+ SimplifyCFGOpt(const TargetTransformInfo &TTI, const DataLayout &DL,
+ unsigned BonusInstThreshold, AssumptionCache *AC)
+ : TTI(TTI), DL(DL), BonusInstThreshold(BonusInstThreshold), AC(AC) {}
bool run(BasicBlock *BB);
};
}
}
/// ComputeSpeculationCost - Compute an abstract "cost" of speculating the
-/// given instruction, which is assumed to be safe to speculate. 1 means
-/// cheap, 2 means less cheap, and UINT_MAX means prohibitively expensive.
-static unsigned ComputeSpeculationCost(const User *I, const DataLayout *DL) {
- assert(isSafeToSpeculativelyExecute(I, DL) &&
+/// given instruction, which is assumed to be safe to speculate. TCC_Free means
+/// cheap, TCC_Basic means less cheap, and TCC_Expensive means prohibitively
+/// expensive.
+static unsigned ComputeSpeculationCost(const User *I,
+ const TargetTransformInfo &TTI) {
+ assert(isSafeToSpeculativelyExecute(I) &&
"Instruction is not safe to speculatively execute!");
- switch (Operator::getOpcode(I)) {
- default:
- // In doubt, be conservative.
- return UINT_MAX;
- case Instruction::GetElementPtr:
- // GEPs are cheap if all indices are constant.
- if (!cast<GEPOperator>(I)->hasAllConstantIndices())
- return UINT_MAX;
- return 1;
- case Instruction::ExtractValue:
- case Instruction::Load:
- case Instruction::Add:
- case Instruction::Sub:
- case Instruction::And:
- case Instruction::Or:
- case Instruction::Xor:
- case Instruction::Shl:
- case Instruction::LShr:
- case Instruction::AShr:
- case Instruction::ICmp:
- case Instruction::Trunc:
- case Instruction::ZExt:
- case Instruction::SExt:
- case Instruction::BitCast:
- case Instruction::ExtractElement:
- case Instruction::InsertElement:
- return 1; // These are all cheap.
-
- case Instruction::Call:
- case Instruction::Select:
- return 2;
- }
+ return TTI.getUserCost(I);
}
-
/// DominatesMergePoint - If we have a merge point of an "if condition" as
/// accepted above, return true if the specified value dominates the block. We
/// don't handle the true generality of domination here, just a special case
static bool DominatesMergePoint(Value *V, BasicBlock *BB,
SmallPtrSetImpl<Instruction*> *AggressiveInsts,
unsigned &CostRemaining,
- const DataLayout *DL) {
+ const TargetTransformInfo &TTI) {
Instruction *I = dyn_cast<Instruction>(V);
if (!I) {
// Non-instructions all dominate instructions, but not all constantexprs
// Okay, it looks like the instruction IS in the "condition". Check to
// see if it's a cheap instruction to unconditionally compute, and if it
// only uses stuff defined outside of the condition. If so, hoist it out.
- if (!isSafeToSpeculativelyExecute(I, DL))
+ if (!isSafeToSpeculativelyExecute(I))
return false;
- unsigned Cost = ComputeSpeculationCost(I, DL);
+ unsigned Cost = ComputeSpeculationCost(I, TTI);
if (Cost > CostRemaining)
return false;
// Okay, we can only really hoist these out if their operands do
// not take us over the cost threshold.
for (User::op_iterator i = I->op_begin(), e = I->op_end(); i != e; ++i)
- if (!DominatesMergePoint(*i, BB, AggressiveInsts, CostRemaining, DL))
+ if (!DominatesMergePoint(*i, BB, AggressiveInsts, CostRemaining, TTI))
return false;
// Okay, it's safe to do this! Remember this instruction.
AggressiveInsts->insert(I);
/// GetConstantInt - Extract ConstantInt from value, looking through IntToPtr
/// and PointerNullValue. Return NULL if value is not a constant int.
-static ConstantInt *GetConstantInt(Value *V, const DataLayout *DL) {
+static ConstantInt *GetConstantInt(Value *V, const DataLayout &DL) {
// Normal constant int.
ConstantInt *CI = dyn_cast<ConstantInt>(V);
- if (CI || !DL || !isa<Constant>(V) || !V->getType()->isPointerTy())
+ if (CI || !isa<Constant>(V) || !V->getType()->isPointerTy())
return CI;
// This is some kind of pointer constant. Turn it into a pointer-sized
// ConstantInt if possible.
- IntegerType *PtrTy = cast<IntegerType>(DL->getIntPtrType(V->getType()));
+ IntegerType *PtrTy = cast<IntegerType>(DL.getIntPtrType(V->getType()));
// Null pointer means 0, see SelectionDAGBuilder::getValue(const Value*).
if (isa<ConstantPointerNull>(V))
return nullptr;
}
+namespace {
+
/// Given a chain of or (||) or and (&&) comparison of a value against a
/// constant, this will try to recover the information required for a switch
/// structure.
/// while for a chain of '&&' it will build the set elements that make the test
/// fail.
struct ConstantComparesGatherer {
-
+ const DataLayout &DL;
Value *CompValue; /// Value found for the switch comparison
Value *Extra; /// Extra clause to be checked before the switch
SmallVector<ConstantInt *, 8> Vals; /// Set of integers to match in switch
unsigned UsedICmps; /// Number of comparisons matched in the and/or chain
/// Construct and compute the result for the comparison instruction Cond
- ConstantComparesGatherer(Instruction *Cond, const DataLayout *DL)
- : CompValue(nullptr), Extra(nullptr), UsedICmps(0) {
- gather(Cond, DL);
+ ConstantComparesGatherer(Instruction *Cond, const DataLayout &DL)
+ : DL(DL), CompValue(nullptr), Extra(nullptr), UsedICmps(0) {
+ gather(Cond);
}
/// Prevent copy
- ConstantComparesGatherer(const ConstantComparesGatherer &)
- LLVM_DELETED_FUNCTION;
+ ConstantComparesGatherer(const ConstantComparesGatherer &) = delete;
ConstantComparesGatherer &
- operator=(const ConstantComparesGatherer &) LLVM_DELETED_FUNCTION;
+ operator=(const ConstantComparesGatherer &) = delete;
private:
/// it wasn't set before or if the new value is the same as the old one
bool setValueOnce(Value *NewVal) {
if(CompValue && CompValue != NewVal) return false;
- return CompValue = NewVal;
+ CompValue = NewVal;
+ return (CompValue != nullptr);
}
/// Try to match Instruction "I" as a comparison against a constant and
/// against is placed in CompValue.
/// If CompValue is already set, the function is expected to fail if a match
/// is found but the value compared to is different.
- bool matchInstruction(Instruction *I, const DataLayout *DL, bool isEQ) {
+ bool matchInstruction(Instruction *I, bool isEQ) {
// If this is an icmp against a constant, handle this as one of the cases.
ICmpInst *ICI;
ConstantInt *C;
}
// If we have "x ult 3", for example, then we can add 0,1,2 to the set.
- ConstantRange Span = ConstantRange::makeICmpRegion(ICI->getPredicate(),
- C->getValue());
+ ConstantRange Span = ConstantRange::makeAllowedICmpRegion(
+ ICI->getPredicate(), C->getValue());
// Shift the range if the compare is fed by an add. This is the range
// compare idiom as emitted by instcombine.
/// the value being compared, and stick the list constants into the Vals
/// vector.
/// One "Extra" case is allowed to differ from the other.
- void gather(Value *V, const DataLayout *DL) {
+ void gather(Value *V) {
Instruction *I = dyn_cast<Instruction>(V);
bool isEQ = (I->getOpcode() == Instruction::Or);
}
// Try to match the current instruction
- if (matchInstruction(I, DL, isEQ))
+ if (matchInstruction(I, isEQ))
// Match succeed, continue the loop
continue;
}
}
};
+}
+
static void EraseTerminatorInstAndDCECond(TerminatorInst *TI) {
Instruction *Cond = nullptr;
if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
CV = SI->getCondition();
} else if (BranchInst *BI = dyn_cast<BranchInst>(TI))
if (BI->isConditional() && BI->getCondition()->hasOneUse())
- if (ICmpInst *ICI = dyn_cast<ICmpInst>(BI->getCondition()))
+ if (ICmpInst *ICI = dyn_cast<ICmpInst>(BI->getCondition())) {
if (ICI->isEquality() && GetConstantInt(ICI->getOperand(1), DL))
CV = ICI->getOperand(0);
+ }
// Unwrap any lossless ptrtoint cast.
- if (DL && CV) {
+ if (CV) {
if (PtrToIntInst *PTII = dyn_cast<PtrToIntInst>(CV)) {
Value *Ptr = PTII->getPointerOperand();
- if (PTII->getType() == DL->getIntPtrType(Ptr->getType()))
+ if (PTII->getType() == DL.getIntPtrType(Ptr->getType()))
CV = Ptr;
}
}
if (HasWeight)
for (unsigned MD_i = 1, MD_e = MD->getNumOperands(); MD_i < MD_e;
++MD_i) {
- ConstantInt* CI = dyn_cast<ConstantInt>(MD->getOperand(MD_i));
- assert(CI);
+ ConstantInt *CI = mdconst::extract<ConstantInt>(MD->getOperand(MD_i));
Weights.push_back(CI->getValue().getZExtValue());
}
for (SwitchInst::CaseIt i = SI->case_end(), e = SI->case_begin(); i != e;) {
MDNode *MD = TI->getMetadata(LLVMContext::MD_prof);
assert(MD);
for (unsigned i = 1, e = MD->getNumOperands(); i < e; ++i) {
- ConstantInt *CI = cast<ConstantInt>(MD->getOperand(i));
+ ConstantInt *CI = mdconst::extract<ConstantInt>(MD->getOperand(i));
Weights.push_back(CI->getValue().getZExtValue());
}
Builder.SetInsertPoint(PTI);
// Convert pointer to int before we switch.
if (CV->getType()->isPointerTy()) {
- assert(DL && "Cannot switch on pointer without DataLayout");
- CV = Builder.CreatePtrToInt(CV, DL->getIntPtrType(CV->getType()),
+ CV = Builder.CreatePtrToInt(CV, DL.getIntPtrType(CV->getType()),
"magicptr");
}
/// HoistThenElseCodeToIf - Given a conditional branch that goes to BB1 and
/// BB2, hoist any common code in the two blocks up into the branch block. The
/// caller of this function guarantees that BI's block dominates BB1 and BB2.
-static bool HoistThenElseCodeToIf(BranchInst *BI, const DataLayout *DL) {
+static bool HoistThenElseCodeToIf(BranchInst *BI,
+ const TargetTransformInfo &TTI) {
// This does very trivial matching, with limited scanning, to find identical
// instructions in the two blocks. In particular, we don't want to get into
// O(M*N) situations here where M and N are the sizes of BB1 and BB2. As
if (isa<TerminatorInst>(I1))
goto HoistTerminator;
+ if (!TTI.isProfitableToHoist(I1) || !TTI.isProfitableToHoist(I2))
+ return Changed;
+
// 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.
passingValueIsAlwaysUndefined(BB2V, PN))
return Changed;
- if (isa<ConstantExpr>(BB1V) && !isSafeToSpeculativelyExecute(BB1V, DL))
+ if (isa<ConstantExpr>(BB1V) && !isSafeToSpeculativelyExecute(BB1V))
return Changed;
- if (isa<ConstantExpr>(BB2V) && !isSafeToSpeculativelyExecute(BB2V, DL))
+ if (isa<ConstantExpr>(BB2V) && !isSafeToSpeculativelyExecute(BB2V))
return Changed;
}
}
return false;
// Gather the PHI nodes in BBEnd.
- std::map<Value*, std::pair<Value*, PHINode*> > MapValueFromBB1ToBB2;
+ SmallDenseMap<std::pair<Value *, Value *>, PHINode *> JointValueMap;
Instruction *FirstNonPhiInBBEnd = nullptr;
- for (BasicBlock::iterator I = BBEnd->begin(), E = BBEnd->end();
- I != E; ++I) {
+ for (BasicBlock::iterator I = BBEnd->begin(), E = BBEnd->end(); I != E; ++I) {
if (PHINode *PN = dyn_cast<PHINode>(I)) {
Value *BB1V = PN->getIncomingValueForBlock(BB1);
Value *BB2V = PN->getIncomingValueForBlock(BB2);
- MapValueFromBB1ToBB2[BB1V] = std::make_pair(BB2V, PN);
+ JointValueMap[std::make_pair(BB1V, BB2V)] = PN;
} else {
FirstNonPhiInBBEnd = &*I;
break;
if (!FirstNonPhiInBBEnd)
return false;
-
// This does very trivial matching, with limited scanning, to find identical
// instructions in the two blocks. We scan backward for obviously identical
// instructions in an identical order.
BasicBlock::InstListType::reverse_iterator RI1 = BB1->getInstList().rbegin(),
- RE1 = BB1->getInstList().rend(), RI2 = BB2->getInstList().rbegin(),
- RE2 = BB2->getInstList().rend();
+ RE1 = BB1->getInstList().rend(),
+ RI2 = BB2->getInstList().rbegin(),
+ RE2 = BB2->getInstList().rend();
// Skip debug info.
while (RI1 != RE1 && isa<DbgInfoIntrinsic>(&*RI1)) ++RI1;
if (RI1 == RE1)
return Changed;
Instruction *I1 = &*RI1, *I2 = &*RI2;
+ auto InstPair = std::make_pair(I1, I2);
// I1 and I2 should have a single use in the same PHI node, and they
// perform the same operation.
// Cannot move control-flow-involving, volatile loads, vaarg, etc.
I1->mayHaveSideEffects() || I2->mayHaveSideEffects() ||
I1->mayReadOrWriteMemory() || I2->mayReadOrWriteMemory() ||
!I1->hasOneUse() || !I2->hasOneUse() ||
- MapValueFromBB1ToBB2.find(I1) == MapValueFromBB1ToBB2.end() ||
- MapValueFromBB1ToBB2[I1].first != I2)
+ !JointValueMap.count(InstPair))
return Changed;
// Check whether we should swap the operands of ICmpInst.
+ // TODO: Add support of communativity.
ICmpInst *ICmp1 = dyn_cast<ICmpInst>(I1), *ICmp2 = dyn_cast<ICmpInst>(I2);
bool SwapOpnds = false;
if (ICmp1 && ICmp2 &&
// with a PHI node after sinking. We only handle the case where there is
// a single pair of different operands.
Value *DifferentOp1 = nullptr, *DifferentOp2 = nullptr;
- unsigned Op1Idx = 0;
+ unsigned Op1Idx = ~0U;
for (unsigned I = 0, E = I1->getNumOperands(); I != E; ++I) {
if (I1->getOperand(I) == I2->getOperand(I))
continue;
- // Early exit if we have more-than one pair of different operands or
- // the different operand is already in MapValueFromBB1ToBB2.
- // Early exit if we need a PHI node to replace a constant.
- if (DifferentOp1 ||
- MapValueFromBB1ToBB2.find(I1->getOperand(I)) !=
- MapValueFromBB1ToBB2.end() ||
+ // Early exit if we have more-than one pair of different operands or if
+ // we need a PHI node to replace a constant.
+ if (Op1Idx != ~0U ||
isa<Constant>(I1->getOperand(I)) ||
isa<Constant>(I2->getOperand(I))) {
// If we can't sink the instructions, undo the swapping.
DifferentOp2 = I2->getOperand(I);
}
- // We insert the pair of different operands to MapValueFromBB1ToBB2 and
- // remove (I1, I2) from MapValueFromBB1ToBB2.
- if (DifferentOp1) {
- PHINode *NewPN = PHINode::Create(DifferentOp1->getType(), 2,
- DifferentOp1->getName() + ".sink",
- BBEnd->begin());
- MapValueFromBB1ToBB2[DifferentOp1] = std::make_pair(DifferentOp2, NewPN);
+ DEBUG(dbgs() << "SINK common instructions " << *I1 << "\n");
+ DEBUG(dbgs() << " " << *I2 << "\n");
+
+ // We insert the pair of different operands to JointValueMap and
+ // remove (I1, I2) from JointValueMap.
+ if (Op1Idx != ~0U) {
+ auto &NewPN = JointValueMap[std::make_pair(DifferentOp1, DifferentOp2)];
+ if (!NewPN) {
+ NewPN =
+ PHINode::Create(DifferentOp1->getType(), 2,
+ DifferentOp1->getName() + ".sink", BBEnd->begin());
+ NewPN->addIncoming(DifferentOp1, BB1);
+ NewPN->addIncoming(DifferentOp2, BB2);
+ DEBUG(dbgs() << "Create PHI node " << *NewPN << "\n";);
+ }
// I1 should use NewPN instead of DifferentOp1.
I1->setOperand(Op1Idx, NewPN);
- NewPN->addIncoming(DifferentOp1, BB1);
- NewPN->addIncoming(DifferentOp2, BB2);
- DEBUG(dbgs() << "Create PHI node " << *NewPN << "\n";);
}
- PHINode *OldPN = MapValueFromBB1ToBB2[I1].second;
- MapValueFromBB1ToBB2.erase(I1);
+ PHINode *OldPN = JointValueMap[InstPair];
+ JointValueMap.erase(InstPair);
- DEBUG(dbgs() << "SINK common instructions " << *I1 << "\n";);
- DEBUG(dbgs() << " " << *I2 << "\n";);
// We need to update RE1 and RE2 if we are going to sink the first
// instruction in the basic block down.
bool UpdateRE1 = (I1 == BB1->begin()), UpdateRE2 = (I2 == BB2->begin());
///
/// \returns true if the conditional block is removed.
static bool SpeculativelyExecuteBB(BranchInst *BI, BasicBlock *ThenBB,
- const DataLayout *DL) {
+ const TargetTransformInfo &TTI) {
// Be conservative for now. FP select instruction can often be expensive.
Value *BrCond = BI->getCondition();
if (isa<FCmpInst>(BrCond))
if (isa<DbgInfoIntrinsic>(I))
continue;
- // Only speculatively execution a single instruction (not counting the
+ // Only speculatively execute a single instruction (not counting the
// terminator) for now.
++SpeculationCost;
if (SpeculationCost > 1)
return false;
// Don't hoist the instruction if it's unsafe or expensive.
- if (!isSafeToSpeculativelyExecute(I, DL) &&
- !(HoistCondStores &&
- (SpeculatedStoreValue = isSafeToSpeculateStore(I, BB, ThenBB,
- EndBB))))
+ if (!isSafeToSpeculativelyExecute(I) &&
+ !(HoistCondStores && (SpeculatedStoreValue = isSafeToSpeculateStore(
+ I, BB, ThenBB, EndBB))))
return false;
if (!SpeculatedStoreValue &&
- ComputeSpeculationCost(I, DL) > PHINodeFoldingThreshold)
+ ComputeSpeculationCost(I, TTI) >
+ PHINodeFoldingThreshold * TargetTransformInfo::TCC_Basic)
return false;
// Store the store speculation candidate.
if (!OrigCE && !ThenCE)
continue; // Known safe and cheap.
- if ((ThenCE && !isSafeToSpeculativelyExecute(ThenCE, DL)) ||
- (OrigCE && !isSafeToSpeculativelyExecute(OrigCE, DL)))
+ if ((ThenCE && !isSafeToSpeculativelyExecute(ThenCE)) ||
+ (OrigCE && !isSafeToSpeculativelyExecute(OrigCE)))
return false;
- unsigned OrigCost = OrigCE ? ComputeSpeculationCost(OrigCE, DL) : 0;
- unsigned ThenCost = ThenCE ? ComputeSpeculationCost(ThenCE, DL) : 0;
- if (OrigCost + ThenCost > 2 * PHINodeFoldingThreshold)
+ unsigned OrigCost = OrigCE ? ComputeSpeculationCost(OrigCE, TTI) : 0;
+ unsigned ThenCost = ThenCE ? ComputeSpeculationCost(ThenCE, TTI) : 0;
+ unsigned MaxCost = 2 * PHINodeFoldingThreshold *
+ TargetTransformInfo::TCC_Basic;
+ if (OrigCost + ThenCost > MaxCost)
return false;
// Account for the cost of an unfolded ConstantExpr which could end up
/// that is defined in the same block as the branch and if any PHI entries are
/// constants, thread edges corresponding to that entry to be branches to their
/// ultimate destination.
-static bool FoldCondBranchOnPHI(BranchInst *BI, const DataLayout *DL) {
+static bool FoldCondBranchOnPHI(BranchInst *BI, const DataLayout &DL) {
BasicBlock *BB = BI->getParent();
PHINode *PN = dyn_cast<PHINode>(BI->getCondition());
// NOTE: we currently cannot transform this case if the PHI node is used
/// FoldTwoEntryPHINode - Given a BB that starts with the specified two-entry
/// PHI node, see if we can eliminate it.
-static bool FoldTwoEntryPHINode(PHINode *PN, const DataLayout *DL) {
+static bool FoldTwoEntryPHINode(PHINode *PN, const TargetTransformInfo &TTI,
+ const DataLayout &DL) {
// Ok, this is a two entry PHI node. Check to see if this is a simple "if
// statement", which has a very simple dominance structure. Basically, we
// are trying to find the condition that is being branched on, which
SmallPtrSet<Instruction*, 4> AggressiveInsts;
unsigned MaxCostVal0 = PHINodeFoldingThreshold,
MaxCostVal1 = PHINodeFoldingThreshold;
+ MaxCostVal0 *= TargetTransformInfo::TCC_Basic;
+ MaxCostVal1 *= TargetTransformInfo::TCC_Basic;
for (BasicBlock::iterator II = BB->begin(); isa<PHINode>(II);) {
PHINode *PN = cast<PHINode>(II++);
}
if (!DominatesMergePoint(PN->getIncomingValue(0), BB, &AggressiveInsts,
- MaxCostVal0, DL) ||
+ MaxCostVal0, TTI) ||
!DominatesMergePoint(PN->getIncomingValue(1), BB, &AggressiveInsts,
- MaxCostVal1, DL))
+ MaxCostVal1, TTI))
return false;
}
"Looking for probabilities on unconditional branch?");
MDNode *ProfileData = BI->getMetadata(LLVMContext::MD_prof);
if (!ProfileData || ProfileData->getNumOperands() != 3) return false;
- ConstantInt *CITrue = dyn_cast<ConstantInt>(ProfileData->getOperand(1));
- ConstantInt *CIFalse = dyn_cast<ConstantInt>(ProfileData->getOperand(2));
+ ConstantInt *CITrue =
+ mdconst::dyn_extract<ConstantInt>(ProfileData->getOperand(1));
+ ConstantInt *CIFalse =
+ mdconst::dyn_extract<ConstantInt>(ProfileData->getOperand(2));
if (!CITrue || !CIFalse) return false;
ProbTrue = CITrue->getValue().getZExtValue();
ProbFalse = CIFalse->getValue().getZExtValue();
/// 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, const DataLayout *DL,
- unsigned BonusInstThreshold) {
+bool llvm::FoldBranchToCommonDest(BranchInst *BI, unsigned BonusInstThreshold) {
BasicBlock *BB = BI->getParent();
Instruction *Cond = nullptr;
// Ignore dbg intrinsics.
if (isa<DbgInfoIntrinsic>(I))
continue;
- if (!I->hasOneUse() || !isSafeToSpeculativelyExecute(I, DL))
+ if (!I->hasOneUse() || !isSafeToSpeculativelyExecute(I))
return false;
// I has only one use and can be executed unconditionally.
Instruction *User = dyn_cast<Instruction>(I->user_back());
// The weight to CommonDest should be PredCommon * SuccTotal +
// PredOther * SuccCommon.
// The weight to OtherDest should be PredOther * SuccOther.
- SmallVector<uint64_t, 2> NewWeights;
- NewWeights.push_back(PredCommon * (SuccCommon + SuccOther) +
- PredOther * SuccCommon);
- NewWeights.push_back(PredOther * SuccOther);
+ uint64_t NewWeights[2] = {PredCommon * (SuccCommon + SuccOther) +
+ PredOther * SuccCommon,
+ PredOther * SuccOther};
// Halve the weights if any of them cannot fit in an uint32_t
FitWeights(NewWeights);
- SmallVector<uint32_t, 2> MDWeights(NewWeights.begin(),NewWeights.end());
PBI->setMetadata(LLVMContext::MD_prof,
- MDBuilder(BI->getContext()).
- createBranchWeights(MDWeights));
+ MDBuilder(BI->getContext())
+ .createBranchWeights(NewWeights[0], NewWeights[1]));
}
// OtherDest may have phi nodes. If so, add an entry from PBI's
/// We prefer to split the edge to 'end' so that there is a true/false entry to
/// the PHI, merging the third icmp into the switch.
static bool TryToSimplifyUncondBranchWithICmpInIt(
- ICmpInst *ICI, IRBuilder<> &Builder, const TargetTransformInfo &TTI,
- unsigned BonusInstThreshold, const DataLayout *DL, AssumptionTracker *AT) {
+ ICmpInst *ICI, IRBuilder<> &Builder, const DataLayout &DL,
+ const TargetTransformInfo &TTI, unsigned BonusInstThreshold,
+ AssumptionCache *AC) {
BasicBlock *BB = ICI->getParent();
// If the block has any PHIs in it or the icmp has multiple uses, it is too
ICI->eraseFromParent();
}
// BB is now empty, so it is likely to simplify away.
- return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AT) | true;
+ return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
}
// Ok, the block is reachable from the default dest. If the constant we're
ICI->replaceAllUsesWith(V);
ICI->eraseFromParent();
// BB is now empty, so it is likely to simplify away.
- return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AT) | true;
+ return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
}
// The use of the icmp has to be in the 'end' block, by the only PHI node in
/// SimplifyBranchOnICmpChain - The specified branch is a conditional branch.
/// Check to see if it is branching on an or/and chain of icmp instructions, and
/// fold it into a switch instruction if so.
-static bool SimplifyBranchOnICmpChain(BranchInst *BI, const DataLayout *DL,
- IRBuilder<> &Builder) {
+static bool SimplifyBranchOnICmpChain(BranchInst *BI, IRBuilder<> &Builder,
+ const DataLayout &DL) {
Instruction *Cond = dyn_cast<Instruction>(BI->getCondition());
if (!Cond) return false;
Builder.SetInsertPoint(BI);
// Convert pointer to int before we switch.
if (CompVal->getType()->isPointerTy()) {
- assert(DL && "Cannot switch on pointer without DataLayout");
- CompVal = Builder.CreatePtrToInt(CompVal,
- DL->getIntPtrType(CompVal->getType()),
- "magicptr");
+ CompVal = Builder.CreatePtrToInt(
+ CompVal, DL.getIntPtrType(CompVal->getType()), "magicptr");
}
// Create the new switch instruction now.
return false;
// Turn all invokes that unwind here into calls and delete the basic block.
- bool InvokeRequiresTableEntry = false;
- bool Changed = false;
for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE;) {
InvokeInst *II = cast<InvokeInst>((*PI++)->getTerminator());
-
- if (II->hasFnAttr(Attribute::UWTable)) {
- // Don't remove an `invoke' instruction if the ABI requires an entry into
- // the table.
- InvokeRequiresTableEntry = true;
- continue;
- }
-
SmallVector<Value*, 8> Args(II->op_begin(), II->op_end() - 3);
-
// Insert a call instruction before the invoke.
CallInst *Call = CallInst::Create(II->getCalledValue(), Args, "", II);
Call->takeName(II);
// Finally, delete the invoke instruction!
II->eraseFromParent();
- Changed = true;
}
- if (!InvokeRequiresTableEntry)
- // The landingpad is now unreachable. Zap it.
- BB->eraseFromParent();
-
- return Changed;
+ // The landingpad is now unreachable. Zap it.
+ BB->eraseFromParent();
+ return true;
}
bool SimplifyCFGOpt::SimplifyReturn(ReturnInst *RI, IRBuilder<> &Builder) {
}
// If we eliminated all predecessors of the block, delete the block now.
- if (pred_begin(BB) == pred_end(BB))
+ if (pred_empty(BB))
// We know there are no successors, so just nuke the block.
BB->eraseFromParent();
--i; --e;
Changed = true;
}
- // If the default value is unreachable, figure out the most popular
- // destination and make it the default.
- if (SI->getDefaultDest() == BB) {
- std::map<BasicBlock*, std::pair<unsigned, unsigned> > Popularity;
- for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end();
- i != e; ++i) {
- std::pair<unsigned, unsigned> &entry =
- Popularity[i.getCaseSuccessor()];
- if (entry.first == 0) {
- entry.first = 1;
- entry.second = i.getCaseIndex();
- } else {
- entry.first++;
- }
- }
-
- // Find the most popular block.
- unsigned MaxPop = 0;
- unsigned MaxIndex = 0;
- BasicBlock *MaxBlock = nullptr;
- for (std::map<BasicBlock*, std::pair<unsigned, unsigned> >::iterator
- I = Popularity.begin(), E = Popularity.end(); I != E; ++I) {
- if (I->second.first > MaxPop ||
- (I->second.first == MaxPop && MaxIndex > I->second.second)) {
- MaxPop = I->second.first;
- MaxIndex = I->second.second;
- MaxBlock = I->first;
- }
- }
- if (MaxBlock) {
- // Make this the new default, allowing us to delete any explicit
- // edges to it.
- SI->setDefaultDest(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 (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end();
- i != e; ++i)
- if (i.getCaseSuccessor() == MaxBlock) {
- SI->removeCase(i);
- --i; --e;
- }
- }
- }
} else if (InvokeInst *II = dyn_cast<InvokeInst>(TI)) {
if (II->getUnwindDest() == BB) {
// Convert the invoke to a call instruction. This would be a good
}
// If this block is now dead, remove it.
- if (pred_begin(BB) == pred_end(BB) &&
+ if (pred_empty(BB) &&
BB != &BB->getParent()->getEntryBlock()) {
// We know there are no successors, so just nuke the block.
BB->eraseFromParent();
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, IRBuilder<> &Builder) {
- assert(SI->getNumCases() > 1 && "Degenerate switch?");
+static bool CasesAreContiguous(SmallVectorImpl<ConstantInt *> &Cases) {
+ assert(Cases.size() >= 1);
- // Make sure all cases point to the same destination and gather the values.
- SmallVector<ConstantInt *, 16> Cases;
- SwitchInst::CaseIt I = SI->case_begin();
- Cases.push_back(I.getCaseValue());
- SwitchInst::CaseIt PrevI = I++;
- for (SwitchInst::CaseIt E = SI->case_end(); I != E; PrevI = I++) {
- if (PrevI.getCaseSuccessor() != I.getCaseSuccessor())
+ array_pod_sort(Cases.begin(), Cases.end(), ConstantIntSortPredicate);
+ for (size_t I = 1, E = Cases.size(); I != E; ++I) {
+ if (Cases[I - 1]->getValue() != Cases[I]->getValue() + 1)
return false;
- Cases.push_back(I.getCaseValue());
}
- assert(Cases.size() == SI->getNumCases() && "Not all cases gathered");
+ return true;
+}
- // 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;
+/// Turn a switch with two reachable destinations into an integer range
+/// comparison and branch.
+static bool TurnSwitchRangeIntoICmp(SwitchInst *SI, IRBuilder<> &Builder) {
+ assert(SI->getNumCases() > 1 && "Degenerate switch?");
+
+ bool HasDefault =
+ !isa<UnreachableInst>(SI->getDefaultDest()->getFirstNonPHIOrDbg());
+
+ // Partition the cases into two sets with different destinations.
+ BasicBlock *DestA = HasDefault ? SI->getDefaultDest() : nullptr;
+ BasicBlock *DestB = nullptr;
+ SmallVector <ConstantInt *, 16> CasesA;
+ SmallVector <ConstantInt *, 16> CasesB;
+
+ for (SwitchInst::CaseIt I : SI->cases()) {
+ BasicBlock *Dest = I.getCaseSuccessor();
+ if (!DestA) DestA = Dest;
+ if (Dest == DestA) {
+ CasesA.push_back(I.getCaseValue());
+ continue;
+ }
+ if (!DestB) DestB = Dest;
+ if (Dest == DestB) {
+ CasesB.push_back(I.getCaseValue());
+ continue;
+ }
+ return false; // More than two destinations.
}
- Constant *Offset = ConstantExpr::getNeg(Cases.back());
- Constant *NumCases = ConstantInt::get(Offset->getType(), SI->getNumCases());
+ assert(DestA && DestB && "Single-destination switch should have been folded.");
+ assert(DestA != DestB);
+ assert(DestB != SI->getDefaultDest());
+ assert(!CasesB.empty() && "There must be non-default cases.");
+ assert(!CasesA.empty() || HasDefault);
+
+ // Figure out if one of the sets of cases form a contiguous range.
+ SmallVectorImpl<ConstantInt *> *ContiguousCases = nullptr;
+ BasicBlock *ContiguousDest = nullptr;
+ BasicBlock *OtherDest = nullptr;
+ if (!CasesA.empty() && CasesAreContiguous(CasesA)) {
+ ContiguousCases = &CasesA;
+ ContiguousDest = DestA;
+ OtherDest = DestB;
+ } else if (CasesAreContiguous(CasesB)) {
+ ContiguousCases = &CasesB;
+ ContiguousDest = DestB;
+ OtherDest = DestA;
+ } else
+ return false;
+
+ // Start building the compare and branch.
+
+ Constant *Offset = ConstantExpr::getNeg(ContiguousCases->back());
+ Constant *NumCases = ConstantInt::get(Offset->getType(), ContiguousCases->size());
Value *Sub = SI->getCondition();
if (!Offset->isNullValue())
- Sub = Builder.CreateAdd(Sub, Offset, Sub->getName()+".off");
+ Sub = Builder.CreateAdd(Sub, Offset, Sub->getName() + ".off");
+
Value *Cmp;
// If NumCases overflowed, then all possible values jump to the successor.
- if (NumCases->isNullValue() && SI->getNumCases() != 0)
+ if (NumCases->isNullValue() && !ContiguousCases->empty())
Cmp = ConstantInt::getTrue(SI->getContext());
else
Cmp = Builder.CreateICmpULT(Sub, NumCases, "switch");
- BranchInst *NewBI = Builder.CreateCondBr(
- Cmp, SI->case_begin().getCaseSuccessor(), SI->getDefaultDest());
+ BranchInst *NewBI = Builder.CreateCondBr(Cmp, ContiguousDest, OtherDest);
// Update weight for the newly-created conditional branch.
- SmallVector<uint64_t, 8> Weights;
- bool HasWeights = HasBranchWeights(SI);
- if (HasWeights) {
+ if (HasBranchWeights(SI)) {
+ SmallVector<uint64_t, 8> Weights;
GetBranchWeights(SI, Weights);
if (Weights.size() == 1 + SI->getNumCases()) {
- // Combine all weights for the cases to be the true weight of NewBI.
- // We assume that the sum of all weights for a Terminator can fit into 32
- // bits.
- uint32_t NewTrueWeight = 0;
- for (unsigned I = 1, E = Weights.size(); I != E; ++I)
- NewTrueWeight += (uint32_t)Weights[I];
+ uint64_t TrueWeight = 0;
+ uint64_t FalseWeight = 0;
+ for (size_t I = 0, E = Weights.size(); I != E; ++I) {
+ if (SI->getSuccessor(I) == ContiguousDest)
+ TrueWeight += Weights[I];
+ else
+ FalseWeight += Weights[I];
+ }
+ while (TrueWeight > UINT32_MAX || FalseWeight > UINT32_MAX) {
+ TrueWeight /= 2;
+ FalseWeight /= 2;
+ }
NewBI->setMetadata(LLVMContext::MD_prof,
- MDBuilder(SI->getContext()).
- createBranchWeights(NewTrueWeight,
- (uint32_t)Weights[0]));
+ MDBuilder(SI->getContext()).createBranchWeights(
+ (uint32_t)TrueWeight, (uint32_t)FalseWeight));
}
}
- // Prune obsolete incoming values off the successor's PHI nodes.
- for (BasicBlock::iterator BBI = SI->case_begin().getCaseSuccessor()->begin();
- isa<PHINode>(BBI); ++BBI) {
- for (unsigned I = 0, E = SI->getNumCases()-1; I != E; ++I)
+ // Prune obsolete incoming values off the successors' PHI nodes.
+ for (auto BBI = ContiguousDest->begin(); isa<PHINode>(BBI); ++BBI) {
+ unsigned PreviousEdges = ContiguousCases->size();
+ if (ContiguousDest == SI->getDefaultDest()) ++PreviousEdges;
+ for (unsigned I = 0, E = PreviousEdges - 1; I != E; ++I)
cast<PHINode>(BBI)->removeIncomingValue(SI->getParent());
}
+ for (auto BBI = OtherDest->begin(); isa<PHINode>(BBI); ++BBI) {
+ unsigned PreviousEdges = SI->getNumCases() - ContiguousCases->size();
+ if (OtherDest == SI->getDefaultDest()) ++PreviousEdges;
+ for (unsigned I = 0, E = PreviousEdges - 1; I != E; ++I)
+ cast<PHINode>(BBI)->removeIncomingValue(SI->getParent());
+ }
+
+ // Drop the switch.
SI->eraseFromParent();
return true;
/// EliminateDeadSwitchCases - Compute masked bits for the condition of a switch
/// and use it to remove dead cases.
-static bool EliminateDeadSwitchCases(SwitchInst *SI, const DataLayout *DL,
- AssumptionTracker *AT) {
+static bool EliminateDeadSwitchCases(SwitchInst *SI, AssumptionCache *AC,
+ const DataLayout &DL) {
Value *Cond = SI->getCondition();
unsigned Bits = Cond->getType()->getIntegerBitWidth();
APInt KnownZero(Bits, 0), KnownOne(Bits, 0);
- computeKnownBits(Cond, KnownZero, KnownOne, DL, 0, AT, SI);
+ computeKnownBits(Cond, KnownZero, KnownOne, DL, 0, AC, SI);
// Gather dead cases.
SmallVector<ConstantInt*, 8> DeadCases;
/// constant or can be replaced by constants from the ConstantPool. Returns the
/// resulting constant on success, 0 otherwise.
static Constant *
-ConstantFold(Instruction *I,
- const SmallDenseMap<Value *, Constant *> &ConstantPool,
- const DataLayout *DL) {
+ConstantFold(Instruction *I, const DataLayout &DL,
+ const SmallDenseMap<Value *, Constant *> &ConstantPool) {
if (SelectInst *Select = dyn_cast<SelectInst>(I)) {
Constant *A = LookupConstant(Select->getCondition(), ConstantPool);
if (!A)
return nullptr;
}
- if (CmpInst *Cmp = dyn_cast<CmpInst>(I))
+ if (CmpInst *Cmp = dyn_cast<CmpInst>(I)) {
return ConstantFoldCompareInstOperands(Cmp->getPredicate(), COps[0],
COps[1], DL);
+ }
return ConstantFoldInstOperands(I->getOpcode(), I->getType(), COps, DL);
}
/// destionations CaseDest corresponding to value CaseVal (0 for the default
/// case), of a switch instruction SI.
static bool
-GetCaseResults(SwitchInst *SI,
- ConstantInt *CaseVal,
- BasicBlock *CaseDest,
+GetCaseResults(SwitchInst *SI, ConstantInt *CaseVal, BasicBlock *CaseDest,
BasicBlock **CommonDest,
- SmallVectorImpl<std::pair<PHINode *, Constant *> > &Res,
- const DataLayout *DL) {
+ SmallVectorImpl<std::pair<PHINode *, Constant *>> &Res,
+ const DataLayout &DL) {
// The block from which we enter the common destination.
BasicBlock *Pred = SI->getParent();
} else if (isa<DbgInfoIntrinsic>(I)) {
// Skip debug intrinsic.
continue;
- } else if (Constant *C = ConstantFold(I, ConstantPool, DL)) {
+ } else if (Constant *C = ConstantFold(I, DL, ConstantPool)) {
// Instruction is side-effect free and constant.
+
+ // If the instruction has uses outside this block or a phi node slot for
+ // the block, it is not safe to bypass the instruction since it would then
+ // no longer dominate all its uses.
+ for (auto &Use : I->uses()) {
+ User *User = Use.getUser();
+ if (Instruction *I = dyn_cast<Instruction>(User))
+ if (I->getParent() == CaseDest)
+ continue;
+ if (PHINode *Phi = dyn_cast<PHINode>(User))
+ if (Phi->getIncomingBlock(Use) == CaseDest)
+ continue;
+ return false;
+ }
+
ConstantPool.insert(std::make_pair(I, C));
} else {
break;
if (!ConstVal)
return false;
- // Note: If the constant comes from constant-propagating the case value
- // through the CaseDest basic block, it will be safe to remove the
- // instructions in that block. They cannot be used (except in the phi nodes
- // we visit) outside CaseDest, because that block does not dominate its
- // successor. If it did, we would not be in this phi node.
-
// Be conservative about which kinds of constants we support.
if (!ValidLookupTableConstant(ConstVal))
return false;
// results for the PHI node of the common destination block for a switch
// instruction. Returns false if multiple PHI nodes have been found or if
// there is not a common destination block for the switch.
-static bool InitializeUniqueCases(
- SwitchInst *SI, const DataLayout *DL, PHINode *&PHI,
- BasicBlock *&CommonDest,
- SwitchCaseResultVectorTy &UniqueResults,
- Constant *&DefaultResult) {
+static bool InitializeUniqueCases(SwitchInst *SI, PHINode *&PHI,
+ BasicBlock *&CommonDest,
+ SwitchCaseResultVectorTy &UniqueResults,
+ Constant *&DefaultResult,
+ const DataLayout &DL) {
for (auto &I : SI->cases()) {
ConstantInt *CaseVal = I.getCaseValue();
/// phi nodes in a common successor block with only two different
/// constant values, replace the switch with select.
static bool SwitchToSelect(SwitchInst *SI, IRBuilder<> &Builder,
- const DataLayout *DL, AssumptionTracker *AT) {
+ AssumptionCache *AC, const DataLayout &DL) {
Value *const Cond = SI->getCondition();
PHINode *PHI = nullptr;
BasicBlock *CommonDest = nullptr;
Constant *DefaultResult;
SwitchCaseResultVectorTy UniqueResults;
// Collect all the cases that will deliver the same value from the switch.
- if (!InitializeUniqueCases(SI, DL, PHI, CommonDest, UniqueResults,
- DefaultResult))
+ if (!InitializeUniqueCases(SI, PHI, CommonDest, UniqueResults, DefaultResult,
+ DL))
return false;
// Selects choose between maximum two values.
if (UniqueResults.size() != 2)
/// SwitchLookupTable - Create a lookup table to use as a switch replacement
/// with the contents of Values, using DefaultValue to fill any holes in the
/// table.
- SwitchLookupTable(Module &M,
- uint64_t TableSize,
- ConstantInt *Offset,
- const SmallVectorImpl<std::pair<ConstantInt*, Constant*> >& Values,
- Constant *DefaultValue,
- const DataLayout *DL);
+ SwitchLookupTable(
+ Module &M, uint64_t TableSize, ConstantInt *Offset,
+ const SmallVectorImpl<std::pair<ConstantInt *, Constant *>> &Values,
+ Constant *DefaultValue, const DataLayout &DL);
/// BuildLookup - Build instructions with Builder to retrieve the value at
/// the position given by Index in the lookup table.
/// WouldFitInRegister - Return true if a table with TableSize elements of
/// type ElementType would fit in a target-legal register.
- static bool WouldFitInRegister(const DataLayout *DL,
- uint64_t TableSize,
+ static bool WouldFitInRegister(const DataLayout &DL, uint64_t TableSize,
const Type *ElementType);
private:
};
}
-SwitchLookupTable::SwitchLookupTable(Module &M,
- uint64_t TableSize,
- ConstantInt *Offset,
- const SmallVectorImpl<std::pair<ConstantInt*, Constant*> >& Values,
- Constant *DefaultValue,
- const DataLayout *DL)
+SwitchLookupTable::SwitchLookupTable(
+ Module &M, uint64_t TableSize, ConstantInt *Offset,
+ const SmallVectorImpl<std::pair<ConstantInt *, Constant *>> &Values,
+ Constant *DefaultValue, const DataLayout &DL)
: SingleValue(nullptr), BitMap(nullptr), BitMapElementTy(nullptr),
LinearOffset(nullptr), LinearMultiplier(nullptr), Array(nullptr) {
assert(Values.size() && "Can't build lookup table without values!");
"switch.tableidx.zext");
Value *GEPIndices[] = { Builder.getInt32(0), Index };
- Value *GEP = Builder.CreateInBoundsGEP(Array, GEPIndices,
- "switch.gep");
+ Value *GEP = Builder.CreateInBoundsGEP(Array->getValueType(), Array,
+ GEPIndices, "switch.gep");
return Builder.CreateLoad(GEP, "switch.load");
}
}
llvm_unreachable("Unknown lookup table kind!");
}
-bool SwitchLookupTable::WouldFitInRegister(const DataLayout *DL,
+bool SwitchLookupTable::WouldFitInRegister(const DataLayout &DL,
uint64_t TableSize,
const Type *ElementType) {
- if (!DL)
- return false;
const IntegerType *IT = dyn_cast<IntegerType>(ElementType);
if (!IT)
return false;
// Avoid overflow, fitsInLegalInteger uses unsigned int for the width.
if (TableSize >= UINT_MAX/IT->getBitWidth())
return false;
- return DL->fitsInLegalInteger(TableSize * IT->getBitWidth());
+ return DL.fitsInLegalInteger(TableSize * IT->getBitWidth());
}
/// ShouldBuildLookupTable - Determine whether a lookup table should be built
/// for this switch, based on the number of cases, size of the table and the
/// types of the results.
-static bool ShouldBuildLookupTable(SwitchInst *SI,
- uint64_t TableSize,
- const TargetTransformInfo &TTI,
- const DataLayout *DL,
- const SmallDenseMap<PHINode*, Type*>& ResultTypes) {
+static bool
+ShouldBuildLookupTable(SwitchInst *SI, uint64_t TableSize,
+ const TargetTransformInfo &TTI, const DataLayout &DL,
+ const SmallDenseMap<PHINode *, Type *> &ResultTypes) {
if (SI->getNumCases() > TableSize || TableSize >= UINT64_MAX / 10)
return false; // TableSize overflowed, or mul below might overflow.
return SI->getNumCases() * 10 >= TableSize * 4;
}
+/// Try to reuse the switch table index compare. Following pattern:
+/// \code
+/// if (idx < tablesize)
+/// r = table[idx]; // table does not contain default_value
+/// else
+/// r = default_value;
+/// if (r != default_value)
+/// ...
+/// \endcode
+/// Is optimized to:
+/// \code
+/// cond = idx < tablesize;
+/// if (cond)
+/// r = table[idx];
+/// else
+/// r = default_value;
+/// if (cond)
+/// ...
+/// \endcode
+/// Jump threading will then eliminate the second if(cond).
+static void reuseTableCompare(User *PhiUser, BasicBlock *PhiBlock,
+ BranchInst *RangeCheckBranch, Constant *DefaultValue,
+ const SmallVectorImpl<std::pair<ConstantInt*, Constant*> >& Values) {
+
+ ICmpInst *CmpInst = dyn_cast<ICmpInst>(PhiUser);
+ if (!CmpInst)
+ return;
+
+ // We require that the compare is in the same block as the phi so that jump
+ // threading can do its work afterwards.
+ if (CmpInst->getParent() != PhiBlock)
+ return;
+
+ Constant *CmpOp1 = dyn_cast<Constant>(CmpInst->getOperand(1));
+ if (!CmpOp1)
+ return;
+
+ Value *RangeCmp = RangeCheckBranch->getCondition();
+ Constant *TrueConst = ConstantInt::getTrue(RangeCmp->getType());
+ Constant *FalseConst = ConstantInt::getFalse(RangeCmp->getType());
+
+ // Check if the compare with the default value is constant true or false.
+ Constant *DefaultConst = ConstantExpr::getICmp(CmpInst->getPredicate(),
+ DefaultValue, CmpOp1, true);
+ if (DefaultConst != TrueConst && DefaultConst != FalseConst)
+ return;
+
+ // Check if the compare with the case values is distinct from the default
+ // compare result.
+ for (auto ValuePair : Values) {
+ Constant *CaseConst = ConstantExpr::getICmp(CmpInst->getPredicate(),
+ ValuePair.second, CmpOp1, true);
+ if (!CaseConst || CaseConst == DefaultConst)
+ return;
+ assert((CaseConst == TrueConst || CaseConst == FalseConst) &&
+ "Expect true or false as compare result.");
+ }
+
+ // Check if the branch instruction dominates the phi node. It's a simple
+ // dominance check, but sufficient for our needs.
+ // Although this check is invariant in the calling loops, it's better to do it
+ // at this late stage. Practically we do it at most once for a switch.
+ BasicBlock *BranchBlock = RangeCheckBranch->getParent();
+ for (auto PI = pred_begin(PhiBlock), E = pred_end(PhiBlock); PI != E; ++PI) {
+ BasicBlock *Pred = *PI;
+ if (Pred != BranchBlock && Pred->getUniquePredecessor() != BranchBlock)
+ return;
+ }
+
+ if (DefaultConst == FalseConst) {
+ // The compare yields the same result. We can replace it.
+ CmpInst->replaceAllUsesWith(RangeCmp);
+ ++NumTableCmpReuses;
+ } else {
+ // The compare yields the same result, just inverted. We can replace it.
+ Value *InvertedTableCmp = BinaryOperator::CreateXor(RangeCmp,
+ ConstantInt::get(RangeCmp->getType(), 1), "inverted.cmp",
+ RangeCheckBranch);
+ CmpInst->replaceAllUsesWith(InvertedTableCmp);
+ ++NumTableCmpReuses;
+ }
+}
+
/// SwitchToLookupTable - If the switch is only used to initialize one or more
/// phi nodes in a common successor block with different constant values,
/// replace the switch with lookup tables.
-static bool SwitchToLookupTable(SwitchInst *SI,
- IRBuilder<> &Builder,
- const TargetTransformInfo &TTI,
- const DataLayout* DL) {
+static bool SwitchToLookupTable(SwitchInst *SI, IRBuilder<> &Builder,
+ const DataLayout &DL,
+ const TargetTransformInfo &TTI) {
assert(SI->getNumCases() > 1 && "Degenerate switch?");
// Only build lookup table when we have a target that supports it.
// If the table has holes, we need a constant result for the default case
// or a bitmask that fits in a register.
SmallVector<std::pair<PHINode*, Constant*>, 4> DefaultResultsList;
- bool HasDefaultResults = false;
- if (TableHasHoles) {
- HasDefaultResults = GetCaseResults(SI, nullptr, SI->getDefaultDest(),
- &CommonDest, DefaultResultsList, DL);
- }
+ bool HasDefaultResults = GetCaseResults(SI, nullptr, SI->getDefaultDest(),
+ &CommonDest, DefaultResultsList, DL);
bool NeedMask = (TableHasHoles && !HasDefaultResults);
if (NeedMask) {
// As an extra penalty for the validity test we require more cases.
if (SI->getNumCases() < 4) // FIXME: Find best threshold value (benchmark).
return false;
- if (!(DL && DL->fitsInLegalInteger(TableSize)))
+ if (!DL.fitsInLegalInteger(TableSize))
return false;
}
"It is impossible for a switch to have more entries than the max "
"representable value of its input integer type's size.");
- // If we have a fully covered lookup table, unconditionally branch to the
- // lookup table BB. Otherwise, check if the condition value is within the case
- // range. If it is so, branch to the new BB. Otherwise branch to SI's default
- // destination.
- const bool GeneratingCoveredLookupTable = MaxTableSize == TableSize;
- if (GeneratingCoveredLookupTable) {
+ // If the default destination is unreachable, or if the lookup table covers
+ // all values of the conditional variable, branch directly to the lookup table
+ // BB. Otherwise, check that the condition is within the case range.
+ const bool DefaultIsReachable =
+ !isa<UnreachableInst>(SI->getDefaultDest()->getFirstNonPHIOrDbg());
+ const bool GeneratingCoveredLookupTable = (MaxTableSize == TableSize);
+ BranchInst *RangeCheckBranch = nullptr;
+
+ if (!DefaultIsReachable || GeneratingCoveredLookupTable) {
Builder.CreateBr(LookupBB);
// We cached PHINodes in PHIs, to avoid accessing deleted PHINodes later,
// do not delete PHINodes here.
SI->getDefaultDest()->removePredecessor(SI->getParent(),
- true/*DontDeleteUselessPHIs*/);
+ /*DontDeleteUselessPHIs=*/true);
} else {
Value *Cmp = Builder.CreateICmpULT(TableIndex, ConstantInt::get(
MinCaseVal->getType(), TableSize));
- Builder.CreateCondBr(Cmp, LookupBB, SI->getDefaultDest());
+ RangeCheckBranch = Builder.CreateCondBr(Cmp, LookupBB, SI->getDefaultDest());
}
// Populate the BB that does the lookups.
bool ReturnedEarly = false;
for (size_t I = 0, E = PHIs.size(); I != E; ++I) {
PHINode *PHI = PHIs[I];
+ const ResultListTy &ResultList = ResultLists[PHI];
// If using a bitmask, use any value to fill the lookup table holes.
Constant *DV = NeedMask ? ResultLists[PHI][0].second : DefaultResults[PHI];
- SwitchLookupTable Table(Mod, TableSize, MinCaseVal, ResultLists[PHI],
- DV, DL);
+ SwitchLookupTable Table(Mod, TableSize, MinCaseVal, ResultList, DV, DL);
Value *Result = Table.BuildLookup(TableIndex, Builder);
break;
}
+ // Do a small peephole optimization: re-use the switch table compare if
+ // possible.
+ if (!TableHasHoles && HasDefaultResults && RangeCheckBranch) {
+ BasicBlock *PhiBlock = PHI->getParent();
+ // Search for compare instructions which use the phi.
+ for (auto *User : PHI->users()) {
+ reuseTableCompare(User, PhiBlock, RangeCheckBranch, DV, ResultList);
+ }
+ }
+
PHI->addIncoming(Result, LookupBB);
}
// see if that predecessor totally determines the outcome of this switch.
if (BasicBlock *OnlyPred = BB->getSinglePredecessor())
if (SimplifyEqualityComparisonWithOnlyPredecessor(SI, OnlyPred, Builder))
- return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AT) | true;
+ return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
Value *Cond = SI->getCondition();
if (SelectInst *Select = dyn_cast<SelectInst>(Cond))
if (SimplifySwitchOnSelect(SI, Select))
- return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AT) | true;
+ return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
// If the block only contains the switch, see if we can fold the block
// away into any preds.
++BBI;
if (SI == &*BBI)
if (FoldValueComparisonIntoPredecessors(SI, Builder))
- return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AT) | true;
+ return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
}
// Try to transform the switch into an icmp and a branch.
if (TurnSwitchRangeIntoICmp(SI, Builder))
- return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AT) | true;
+ return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
// Remove unreachable cases.
- if (EliminateDeadSwitchCases(SI, DL, AT))
- return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AT) | true;
+ if (EliminateDeadSwitchCases(SI, AC, DL))
+ return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
- if (SwitchToSelect(SI, Builder, DL, AT))
- return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AT) | true;
+ if (SwitchToSelect(SI, Builder, AC, DL))
+ return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
if (ForwardSwitchConditionToPHI(SI))
- return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AT) | true;
+ return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
- if (SwitchToLookupTable(SI, Builder, TTI, DL))
- return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AT) | true;
+ if (SwitchToLookupTable(SI, Builder, DL, TTI))
+ return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
return false;
}
if (SelectInst *SI = dyn_cast<SelectInst>(IBI->getAddress())) {
if (SimplifyIndirectBrOnSelect(IBI, SI))
- return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AT) | true;
+ return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
}
return Changed;
}
+/// Given an block with only a single landing pad and a unconditional branch
+/// try to find another basic block which this one can be merged with. This
+/// handles cases where we have multiple invokes with unique landing pads, but
+/// a shared handler.
+///
+/// We specifically choose to not worry about merging non-empty blocks
+/// here. That is a PRE/scheduling problem and is best solved elsewhere. In
+/// practice, the optimizer produces empty landing pad blocks quite frequently
+/// when dealing with exception dense code. (see: instcombine, gvn, if-else
+/// sinking in this file)
+///
+/// This is primarily a code size optimization. We need to avoid performing
+/// any transform which might inhibit optimization (such as our ability to
+/// specialize a particular handler via tail commoning). We do this by not
+/// merging any blocks which require us to introduce a phi. Since the same
+/// values are flowing through both blocks, we don't loose any ability to
+/// specialize. If anything, we make such specialization more likely.
+///
+/// TODO - This transformation could remove entries from a phi in the target
+/// block when the inputs in the phi are the same for the two blocks being
+/// merged. In some cases, this could result in removal of the PHI entirely.
+static bool TryToMergeLandingPad(LandingPadInst *LPad, BranchInst *BI,
+ BasicBlock *BB) {
+ auto Succ = BB->getUniqueSuccessor();
+ assert(Succ);
+ // If there's a phi in the successor block, we'd likely have to introduce
+ // a phi into the merged landing pad block.
+ if (isa<PHINode>(*Succ->begin()))
+ return false;
+
+ for (BasicBlock *OtherPred : predecessors(Succ)) {
+ if (BB == OtherPred)
+ continue;
+ BasicBlock::iterator I = OtherPred->begin();
+ LandingPadInst *LPad2 = dyn_cast<LandingPadInst>(I);
+ if (!LPad2 || !LPad2->isIdenticalTo(LPad))
+ continue;
+ for (++I; isa<DbgInfoIntrinsic>(I); ++I) {}
+ BranchInst *BI2 = dyn_cast<BranchInst>(I);
+ if (!BI2 || !BI2->isIdenticalTo(BI))
+ continue;
+
+ // We've found an identical block. Update our predeccessors to take that
+ // path instead and make ourselves dead.
+ SmallSet<BasicBlock *, 16> Preds;
+ Preds.insert(pred_begin(BB), pred_end(BB));
+ for (BasicBlock *Pred : Preds) {
+ InvokeInst *II = cast<InvokeInst>(Pred->getTerminator());
+ assert(II->getNormalDest() != BB &&
+ II->getUnwindDest() == BB && "unexpected successor");
+ II->setUnwindDest(OtherPred);
+ }
+
+ // The debug info in OtherPred doesn't cover the merged control flow that
+ // used to go through BB. We need to delete it or update it.
+ for (auto I = OtherPred->begin(), E = OtherPred->end();
+ I != E;) {
+ Instruction &Inst = *I; I++;
+ if (isa<DbgInfoIntrinsic>(Inst))
+ Inst.eraseFromParent();
+ }
+
+ SmallSet<BasicBlock *, 16> Succs;
+ Succs.insert(succ_begin(BB), succ_end(BB));
+ for (BasicBlock *Succ : Succs) {
+ Succ->removePredecessor(BB);
+ }
+
+ IRBuilder<> Builder(BI);
+ Builder.CreateUnreachable();
+ BI->eraseFromParent();
+ return true;
+ }
+ return false;
+}
+
bool SimplifyCFGOpt::SimplifyUncondBranch(BranchInst *BI, IRBuilder<> &Builder){
BasicBlock *BB = BI->getParent();
for (++I; isa<DbgInfoIntrinsic>(I); ++I)
;
if (I->isTerminator() &&
- TryToSimplifyUncondBranchWithICmpInIt(ICI, Builder, TTI,
- BonusInstThreshold, DL, AT))
+ TryToSimplifyUncondBranchWithICmpInIt(ICI, Builder, DL, TTI,
+ BonusInstThreshold, AC))
return true;
}
+ // See if we can merge an empty landing pad block with another which is
+ // equivalent.
+ if (LandingPadInst *LPad = dyn_cast<LandingPadInst>(I)) {
+ for (++I; isa<DbgInfoIntrinsic>(I); ++I) {}
+ if (I->isTerminator() &&
+ TryToMergeLandingPad(LPad, BI, BB))
+ return true;
+ }
+
// If this basic block is ONLY a compare and a branch, and if a predecessor
// branches to us and our successor, fold the comparison into the
// predecessor and use logical operations to update the incoming value
// for PHI nodes in common successor.
- if (FoldBranchToCommonDest(BI, DL, BonusInstThreshold))
- return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AT) | true;
+ if (FoldBranchToCommonDest(BI, BonusInstThreshold))
+ return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
return false;
}
// switch.
if (BasicBlock *OnlyPred = BB->getSinglePredecessor())
if (SimplifyEqualityComparisonWithOnlyPredecessor(BI, OnlyPred, Builder))
- return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AT) | true;
+ return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
// This block must be empty, except for the setcond inst, if it exists.
// Ignore dbg intrinsics.
++I;
if (&*I == BI) {
if (FoldValueComparisonIntoPredecessors(BI, Builder))
- return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AT) | true;
+ return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
} else if (&*I == cast<Instruction>(BI->getCondition())){
++I;
// Ignore dbg intrinsics.
while (isa<DbgInfoIntrinsic>(I))
++I;
if (&*I == BI && FoldValueComparisonIntoPredecessors(BI, Builder))
- return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AT) | true;
+ return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
}
}
// Try to turn "br (X == 0 | X == 1), T, F" into a switch instruction.
- if (SimplifyBranchOnICmpChain(BI, DL, Builder))
+ if (SimplifyBranchOnICmpChain(BI, Builder, DL))
return true;
// If this basic block is ONLY a compare and a branch, and if a predecessor
// branches to us and one of our successors, fold the comparison into the
// predecessor and use logical operations to pick the right destination.
- if (FoldBranchToCommonDest(BI, DL, BonusInstThreshold))
- return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AT) | true;
+ if (FoldBranchToCommonDest(BI, BonusInstThreshold))
+ return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
// We have a conditional branch to two blocks that are only reachable
// from BI. We know that the condbr dominates the two blocks, so see if
// can hoist it up to the branching block.
if (BI->getSuccessor(0)->getSinglePredecessor()) {
if (BI->getSuccessor(1)->getSinglePredecessor()) {
- if (HoistThenElseCodeToIf(BI, DL))
- return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AT) | true;
+ if (HoistThenElseCodeToIf(BI, TTI))
+ return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
} else {
// If Successor #1 has multiple preds, we may be able to conditionally
// execute Successor #0 if it branches to Successor #1.
TerminatorInst *Succ0TI = BI->getSuccessor(0)->getTerminator();
if (Succ0TI->getNumSuccessors() == 1 &&
Succ0TI->getSuccessor(0) == BI->getSuccessor(1))
- if (SpeculativelyExecuteBB(BI, BI->getSuccessor(0), DL))
- return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AT) | true;
+ if (SpeculativelyExecuteBB(BI, BI->getSuccessor(0), TTI))
+ return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
}
} else if (BI->getSuccessor(1)->getSinglePredecessor()) {
// If Successor #0 has multiple preds, we may be able to conditionally
TerminatorInst *Succ1TI = BI->getSuccessor(1)->getTerminator();
if (Succ1TI->getNumSuccessors() == 1 &&
Succ1TI->getSuccessor(0) == BI->getSuccessor(0))
- if (SpeculativelyExecuteBB(BI, BI->getSuccessor(1), DL))
- return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AT) | true;
+ if (SpeculativelyExecuteBB(BI, BI->getSuccessor(1), TTI))
+ return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
}
// If this is a branch on a phi node in the current block, thread control
if (PHINode *PN = dyn_cast<PHINode>(BI->getCondition()))
if (PN->getParent() == BI->getParent())
if (FoldCondBranchOnPHI(BI, DL))
- return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AT) | true;
+ return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
// Scan predecessor blocks for conditional branches.
for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI)
if (BranchInst *PBI = dyn_cast<BranchInst>((*PI)->getTerminator()))
if (PBI != BI && PBI->isConditional())
if (SimplifyCondBranchToCondBranch(PBI, BI))
- return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AT) | true;
+ return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
return false;
}
// Remove basic blocks that have no predecessors (except the entry block)...
// or that just have themself as a predecessor. These are unreachable.
- if ((pred_begin(BB) == pred_end(BB) &&
+ if ((pred_empty(BB) &&
BB != &BB->getParent()->getEntryBlock()) ||
BB->getSinglePredecessor() == BB) {
DEBUG(dbgs() << "Removing BB: \n" << *BB);
// eliminate it, do so now.
if (PHINode *PN = dyn_cast<PHINode>(BB->begin()))
if (PN->getNumIncomingValues() == 2)
- Changed |= FoldTwoEntryPHINode(PN, DL);
+ Changed |= FoldTwoEntryPHINode(PN, TTI, DL);
Builder.SetInsertPoint(BB->getTerminator());
if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator())) {
/// of the CFG. It returns true if a modification was made.
///
bool llvm::SimplifyCFG(BasicBlock *BB, const TargetTransformInfo &TTI,
- unsigned BonusInstThreshold,
- const DataLayout *DL, AssumptionTracker *AT) {
- return SimplifyCFGOpt(TTI, BonusInstThreshold, DL, AT).run(BB);
+ unsigned BonusInstThreshold, AssumptionCache *AC) {
+ return SimplifyCFGOpt(TTI, BB->getModule()->getDataLayout(),
+ BonusInstThreshold, AC).run(BB);
}
projects / oota-llvm.git / blobdiff