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");
const TargetTransformInfo &TTI;
unsigned BonusInstThreshold;
const DataLayout *const DL;
- AssumptionTracker *AT;
+ AssumptionCache *AC;
Value *isValueEqualityComparison(TerminatorInst *TI);
BasicBlock *GetValueEqualityComparisonCases(TerminatorInst *TI,
std::vector<ValueEqualityComparisonCase> &Cases);
public:
SimplifyCFGOpt(const TargetTransformInfo &TTI, unsigned BonusInstThreshold,
- const DataLayout *DL, AssumptionTracker *AT)
- : TTI(TTI), BonusInstThreshold(BonusInstThreshold), DL(DL), AT(AT) {}
+ const DataLayout *DL, AssumptionCache *AC)
+ : TTI(TTI), BonusInstThreshold(BonusInstThreshold), DL(DL), AC(AC) {}
bool run(BasicBlock *BB);
};
}
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.
/// fail.
struct ConstantComparesGatherer {
- Value *CompValue = nullptr; /// Value found for the switch comparison
- Value *Extra = nullptr; /// Extra clause to be checked before the switch
- SmallVector<ConstantInt*, 8> Vals; /// Set of integers to match in switch
- unsigned UsedICmps = 0; /// Number of comparisons matched in the and/or chain
+ 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) {
+ ConstantComparesGatherer(Instruction *Cond, const DataLayout *DL)
+ : CompValue(nullptr), Extra(nullptr), UsedICmps(0) {
gather(Cond, DL);
}
/// Prevent copy
- ConstantComparesGatherer(const ConstantComparesGatherer&) = delete;
- ConstantComparesGatherer &operator=(const ConstantComparesGatherer&) = delete;
+ ConstantComparesGatherer(const ConstantComparesGatherer &)
+ LLVM_DELETED_FUNCTION;
+ ConstantComparesGatherer &
+ operator=(const ConstantComparesGatherer &) LLVM_DELETED_FUNCTION;
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
}
};
+}
+
static void EraseTerminatorInstAndDCECond(TerminatorInst *TI) {
Instruction *Cond = nullptr;
if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
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());
}
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());
"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();
/// 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) {
+ unsigned BonusInstThreshold, const DataLayout *DL, 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, DL, 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, DL, AC) | true;
}
// The use of the icmp has to be in the 'end' block, by the only PHI node in
// 'setne's and'ed together, collect them.
// Try to gather values from a chain of and/or to be turned into a switch
- ConstantComparesGatherer ConstantCompare{Cond, DL};
+ ConstantComparesGatherer ConstantCompare(Cond, DL);
// Unpack the result
SmallVectorImpl<ConstantInt*> &Values = ConstantCompare.Vals;
Value *CompVal = ConstantCompare.CompValue;
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) {
+ AssumptionCache *AC) {
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;
continue;
} else if (Constant *C = ConstantFold(I, ConstantPool, DL)) {
// 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;
/// 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) {
+ const DataLayout *DL, AssumptionCache *AC) {
Value *const Cond = SI->getCondition();
PHINode *PHI = nullptr;
BasicBlock *CommonDest = nullptr;
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.
// 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(),
+ bool HasDefaultResults = GetCaseResults(SI, nullptr, SI->getDefaultDest(),
&CommonDest, DefaultResultsList, DL);
- }
bool NeedMask = (TableHasHoles && !HasDefaultResults);
if (NeedMask) {
// 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.
+ BranchInst *RangeCheckBranch = nullptr;
+
const bool GeneratingCoveredLookupTable = MaxTableSize == TableSize;
if (GeneratingCoveredLookupTable) {
Builder.CreateBr(LookupBB);
} 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, DL, 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, DL, 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, DL, 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, DL, AC) | true;
// Remove unreachable cases.
- if (EliminateDeadSwitchCases(SI, DL, AT))
- return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AT) | true;
+ if (EliminateDeadSwitchCases(SI, DL, AC))
+ return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AC) | true;
- if (SwitchToSelect(SI, Builder, DL, AT))
- return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AT) | true;
+ if (SwitchToSelect(SI, Builder, DL, AC))
+ return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AC) | true;
if (ForwardSwitchConditionToPHI(SI))
- return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AT) | true;
+ return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AC) | true;
if (SwitchToLookupTable(SI, Builder, TTI, DL))
- return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AT) | true;
+ return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, 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, DL, AC) | true;
}
return Changed;
}
;
if (I->isTerminator() &&
TryToSimplifyUncondBranchWithICmpInIt(ICI, Builder, TTI,
- BonusInstThreshold, DL, AT))
+ BonusInstThreshold, DL, AC))
return true;
}
// 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;
+ return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, 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, DL, 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, DL, 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, DL, AC) | true;
}
}
// 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;
+ return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, 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
if (BI->getSuccessor(0)->getSinglePredecessor()) {
if (BI->getSuccessor(1)->getSinglePredecessor()) {
if (HoistThenElseCodeToIf(BI, DL))
- return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AT) | true;
+ return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AC) | true;
} else {
// If Successor #1 has multiple preds, we may be able to conditionally
// execute Successor #0 if it branches to Successor #1.
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;
+ return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AC) | true;
}
} else if (BI->getSuccessor(1)->getSinglePredecessor()) {
// If Successor #0 has multiple preds, we may be able to conditionally
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;
+ return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, 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, DL, 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, DL, 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);
/// 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, const DataLayout *DL,
+ AssumptionCache *AC) {
+ return SimplifyCFGOpt(TTI, BonusInstThreshold, DL, AC).run(BB);
}
projects / oota-llvm.git / blobdiff