cl::desc("Hoist conditional stores if an unconditional store precedes"));
STATISTIC(NumBitMaps, "Number of switch instructions turned into bitmaps");
+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(NumSinkCommons, "Number of common instructions sunk down to the end block");
STATISTIC(NumSpeculations, "Number of speculative executed instructions");
namespace {
+ // The first field contains the value that the switch produces when a certain
+ // case group is selected, and the second field is a vector containing the cases
+ // composing the case group.
+ typedef SmallVector<std::pair<Constant *, SmallVector<ConstantInt *, 4>>, 2>
+ SwitchCaseResultVectorTy;
+ // The first field contains the phi node that generates a result of the switch
+ // and the second field contains the value generated for a certain case in the switch
+ // for that PHI.
+ typedef SmallVector<std::pair<PHINode *, Constant *>, 4> SwitchCaseResultsTy;
+
/// ValueEqualityComparisonCase - Represents a case of a switch.
struct ValueEqualityComparisonCase {
ConstantInt *Value;
return nullptr;
}
-/// GatherConstantCompares - Given a potentially 'or'd or 'and'd together
-/// collection of icmp eq/ne instructions that compare a value against a
-/// constant, return the value being compared, and stick the constant into the
-/// Values vector.
-static Value *
-GatherConstantCompares(Value *V, std::vector<ConstantInt*> &Vals, Value *&Extra,
- const DataLayout *DL, bool isEQ, unsigned &UsedICmps) {
- Instruction *I = dyn_cast<Instruction>(V);
- if (!I) return nullptr;
-
- // If this is an icmp against a constant, handle this as one of the cases.
- if (ICmpInst *ICI = dyn_cast<ICmpInst>(I)) {
- if (ConstantInt *C = GetConstantInt(I->getOperand(1), DL)) {
- Value *RHSVal;
- ConstantInt *RHSC;
-
- if (ICI->getPredicate() == (isEQ ? ICmpInst::ICMP_EQ:ICmpInst::ICMP_NE)) {
- // (x & ~2^x) == y --> x == y || x == y|2^x
- // This undoes a transformation done by instcombine to fuse 2 compares.
- if (match(ICI->getOperand(0),
- m_And(m_Value(RHSVal), m_ConstantInt(RHSC)))) {
- APInt Not = ~RHSC->getValue();
- if (Not.isPowerOf2()) {
- Vals.push_back(C);
- Vals.push_back(
- ConstantInt::get(C->getContext(), C->getValue() | Not));
- UsedICmps++;
- return RHSVal;
- }
- }
+/// 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.
+/// It will depth-first traverse the chain of comparison, seeking for patterns
+/// like %a == 12 or %a < 4 and combine them to produce a set of integer
+/// representing the different cases for the switch.
+/// Note that if the chain is composed of '||' it will build the set of elements
+/// that matches the comparisons (i.e. any of this value validate the chain)
+/// while for a chain of '&&' it will build the set elements that make the test
+/// fail.
+struct ConstantComparesGatherer {
+
+ 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);
+ }
+
+ /// Prevent copy
+ ConstantComparesGatherer(const ConstantComparesGatherer &)
+ LLVM_DELETED_FUNCTION;
+ ConstantComparesGatherer &
+ operator=(const ConstantComparesGatherer &) LLVM_DELETED_FUNCTION;
- UsedICmps++;
- Vals.push_back(C);
- return I->getOperand(0);
+private:
+
+ /// Try to set the current value used for the comparison, it succeeds only if
+ /// 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;
+ }
+
+ /// Try to match Instruction "I" as a comparison against a constant and
+ /// populates the array Vals with the set of values that match (or do not
+ /// match depending on isEQ).
+ /// Return false on failure. On success, the Value the comparison matched
+ /// 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) {
+ // If this is an icmp against a constant, handle this as one of the cases.
+ ICmpInst *ICI;
+ ConstantInt *C;
+ if (!((ICI = dyn_cast<ICmpInst>(I)) &&
+ (C = GetConstantInt(I->getOperand(1), DL)))) {
+ return false;
+ }
+
+ Value *RHSVal;
+ ConstantInt *RHSC;
+
+ // Pattern match a special case
+ // (x & ~2^x) == y --> x == y || x == y|2^x
+ // This undoes a transformation done by instcombine to fuse 2 compares.
+ if (ICI->getPredicate() == (isEQ ? ICmpInst::ICMP_EQ:ICmpInst::ICMP_NE)) {
+ if (match(ICI->getOperand(0),
+ m_And(m_Value(RHSVal), m_ConstantInt(RHSC)))) {
+ APInt Not = ~RHSC->getValue();
+ if (Not.isPowerOf2()) {
+ // If we already have a value for the switch, it has to match!
+ if(!setValueOnce(RHSVal))
+ return false;
+
+ Vals.push_back(C);
+ Vals.push_back(ConstantInt::get(C->getContext(),
+ C->getValue() | Not));
+ UsedICmps++;
+ return true;
+ }
}
- // If we have "x ult 3" comparison, for example, then we can add 0,1,2 to
- // the set.
- ConstantRange Span =
- ConstantRange::makeICmpRegion(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.
- bool hasAdd =
- match(I->getOperand(0), m_Add(m_Value(RHSVal), m_ConstantInt(RHSC)));
- if (hasAdd)
- Span = Span.subtract(RHSC->getValue());
-
- // If this is an and/!= check then we want to optimize "x ugt 2" into
- // x != 0 && x != 1.
- if (!isEQ)
- Span = Span.inverse();
-
- // If there are a ton of values, we don't want to make a ginormous switch.
- if (Span.getSetSize().ugt(8) || Span.isEmptySet())
- return nullptr;
-
- for (APInt Tmp = Span.getLower(); Tmp != Span.getUpper(); ++Tmp)
- Vals.push_back(ConstantInt::get(V->getContext(), Tmp));
+ // If we already have a value for the switch, it has to match!
+ if(!setValueOnce(ICI->getOperand(0)))
+ return false;
+
UsedICmps++;
- return hasAdd ? RHSVal : I->getOperand(0);
+ Vals.push_back(C);
+ return ICI->getOperand(0);
}
- return nullptr;
- }
- // Otherwise, we can only handle an | or &, depending on isEQ.
- if (I->getOpcode() != (isEQ ? Instruction::Or : Instruction::And))
- return nullptr;
+ // 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());
- unsigned NumValsBeforeLHS = Vals.size();
- unsigned UsedICmpsBeforeLHS = UsedICmps;
- if (Value *LHS = GatherConstantCompares(I->getOperand(0), Vals, Extra, DL,
- isEQ, UsedICmps)) {
- unsigned NumVals = Vals.size();
- unsigned UsedICmpsBeforeRHS = UsedICmps;
- if (Value *RHS = GatherConstantCompares(I->getOperand(1), Vals, Extra, DL,
- isEQ, UsedICmps)) {
- if (LHS == RHS)
- return LHS;
- Vals.resize(NumVals);
- UsedICmps = UsedICmpsBeforeRHS;
+ // Shift the range if the compare is fed by an add. This is the range
+ // compare idiom as emitted by instcombine.
+ Value *CandidateVal = I->getOperand(0);
+ if(match(I->getOperand(0), m_Add(m_Value(RHSVal), m_ConstantInt(RHSC)))) {
+ Span = Span.subtract(RHSC->getValue());
+ CandidateVal = RHSVal;
}
- // The RHS of the or/and can't be folded in and we haven't used "Extra" yet,
- // set it and return success.
- if (Extra == nullptr || Extra == I->getOperand(1)) {
- Extra = I->getOperand(1);
- return LHS;
+ // If this is an and/!= check, then we are looking to build the set of
+ // value that *don't* pass the and chain. I.e. to turn "x ugt 2" into
+ // x != 0 && x != 1.
+ if (!isEQ)
+ Span = Span.inverse();
+
+ // If there are a ton of values, we don't want to make a ginormous switch.
+ if (Span.getSetSize().ugt(8) || Span.isEmptySet()) {
+ return false;
}
- Vals.resize(NumValsBeforeLHS);
- UsedICmps = UsedICmpsBeforeLHS;
- return nullptr;
- }
+ // If we already have a value for the switch, it has to match!
+ if(!setValueOnce(CandidateVal))
+ return false;
+
+ // Add all values from the range to the set
+ for (APInt Tmp = Span.getLower(); Tmp != Span.getUpper(); ++Tmp)
+ Vals.push_back(ConstantInt::get(I->getContext(), Tmp));
+
+ UsedICmps++;
+ return true;
- // If the LHS can't be folded in, but Extra is available and RHS can, try to
- // use LHS as Extra.
- if (Extra == nullptr || Extra == I->getOperand(0)) {
- Value *OldExtra = Extra;
- Extra = I->getOperand(0);
- if (Value *RHS = GatherConstantCompares(I->getOperand(1), Vals, Extra, DL,
- isEQ, UsedICmps))
- return RHS;
- assert(Vals.size() == NumValsBeforeLHS);
- Extra = OldExtra;
}
- return nullptr;
-}
+ /// gather - Given a potentially 'or'd or 'and'd together collection of icmp
+ /// eq/ne/lt/gt instructions that compare a value against a constant, extract
+ /// 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) {
+ Instruction *I = dyn_cast<Instruction>(V);
+ bool isEQ = (I->getOpcode() == Instruction::Or);
+
+ // Keep a stack (SmallVector for efficiency) for depth-first traversal
+ SmallVector<Value *, 8> DFT;
+
+ // Initialize
+ DFT.push_back(V);
+
+ while(!DFT.empty()) {
+ V = DFT.pop_back_val();
+
+ if (Instruction *I = dyn_cast<Instruction>(V)) {
+ // If it is a || (or && depending on isEQ), process the operands.
+ if (I->getOpcode() == (isEQ ? Instruction::Or : Instruction::And)) {
+ DFT.push_back(I->getOperand(1));
+ DFT.push_back(I->getOperand(0));
+ continue;
+ }
+
+ // Try to match the current instruction
+ if (matchInstruction(I, DL, isEQ))
+ // Match succeed, continue the loop
+ continue;
+ }
+
+ // One element of the sequence of || (or &&) could not be match as a
+ // comparison against the same value as the others.
+ // We allow only one "Extra" case to be checked before the switch
+ if (!Extra) {
+ Extra = V;
+ continue;
+ }
+ // Failed to parse a proper sequence, abort now
+ CompValue = nullptr;
+ break;
+ }
+ }
+};
static void EraseTerminatorInstAndDCECond(TerminatorInst *TI) {
Instruction *Cond = nullptr;
// Collect branch weights into a vector.
SmallVector<uint32_t, 8> Weights;
- MDNode* MD = SI->getMetadata(LLVMContext::MD_prof);
+ MDNode *MD = SI->getMetadata(LLVMContext::MD_prof);
bool HasWeight = MD && (MD->getNumOperands() == 2 + SI->getNumCases());
if (HasWeight)
for (unsigned MD_i = 1, MD_e = MD->getNumOperands(); MD_i < MD_e;
}
static inline bool HasBranchWeights(const Instruction* I) {
- MDNode* ProfMD = I->getMetadata(LLVMContext::MD_prof);
+ MDNode *ProfMD = I->getMetadata(LLVMContext::MD_prof);
if (ProfMD && ProfMD->getOperand(0))
if (MDString* MDS = dyn_cast<MDString>(ProfMD->getOperand(0)))
return MDS->getString().equals("branch_weights");
/// metadata.
static void GetBranchWeights(TerminatorInst *TI,
SmallVectorImpl<uint64_t> &Weights) {
- MDNode* MD = TI->getMetadata(LLVMContext::MD_prof);
+ 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));
LLVMContext::MD_tbaa,
LLVMContext::MD_range,
LLVMContext::MD_fpmath,
- LLVMContext::MD_invariant_load
+ LLVMContext::MD_invariant_load,
+ LLVMContext::MD_nonnull
};
combineMetadata(I1, I2, KnownIDs);
I2->eraseFromParent();
if (!I2->use_empty())
I2->replaceAllUsesWith(I1);
I1->intersectOptionalDataWith(I2);
+ // TODO: Use combineMetadata here to preserve what metadata we can
+ // (analogous to the hoisting case above).
I2->eraseFromParent();
if (UpdateRE1)
Instruction *Cond = dyn_cast<Instruction>(BI->getCondition());
if (!Cond) return false;
-
// Change br (X == 0 | X == 1), T, F into a switch instruction.
// If this is a bunch of seteq's or'd together, or if it's a bunch of
// 'setne's and'ed together, collect them.
- Value *CompVal = nullptr;
- std::vector<ConstantInt*> Values;
- bool TrueWhenEqual = true;
- Value *ExtraCase = nullptr;
- unsigned UsedICmps = 0;
-
- if (Cond->getOpcode() == Instruction::Or) {
- CompVal = GatherConstantCompares(Cond, Values, ExtraCase, DL, true,
- UsedICmps);
- } else if (Cond->getOpcode() == Instruction::And) {
- CompVal = GatherConstantCompares(Cond, Values, ExtraCase, DL, false,
- UsedICmps);
- TrueWhenEqual = false;
- }
+
+ // Try to gather values from a chain of and/or to be turned into a switch
+ ConstantComparesGatherer ConstantCompare(Cond, DL);
+ // Unpack the result
+ SmallVectorImpl<ConstantInt*> &Values = ConstantCompare.Vals;
+ Value *CompVal = ConstantCompare.CompValue;
+ unsigned UsedICmps = ConstantCompare.UsedICmps;
+ Value *ExtraCase = ConstantCompare.Extra;
// If we didn't have a multiply compared value, fail.
if (!CompVal) return false;
if (UsedICmps <= 1)
return false;
+ bool TrueWhenEqual = (Cond->getOpcode() == Instruction::Or);
+
// There might be duplicate constants in the list, which the switch
// instruction can't handle, remove them now.
array_pod_sort(Values.begin(), Values.end(), ConstantIntSortPredicate);
return Res.size() > 0;
}
+// MapCaseToResult - Helper function used to
+// add CaseVal to the list of cases that generate Result.
+static void MapCaseToResult(ConstantInt *CaseVal,
+ SwitchCaseResultVectorTy &UniqueResults,
+ Constant *Result) {
+ for (auto &I : UniqueResults) {
+ if (I.first == Result) {
+ I.second.push_back(CaseVal);
+ return;
+ }
+ }
+ UniqueResults.push_back(std::make_pair(Result,
+ SmallVector<ConstantInt*, 4>(1, CaseVal)));
+}
+
+// InitializeUniqueCases - Helper function that initializes a map containing
+// 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) {
+ for (auto &I : SI->cases()) {
+ ConstantInt *CaseVal = I.getCaseValue();
+
+ // Resulting value at phi nodes for this case value.
+ SwitchCaseResultsTy Results;
+ if (!GetCaseResults(SI, CaseVal, I.getCaseSuccessor(), &CommonDest, Results,
+ DL))
+ return false;
+
+ // Only one value per case is permitted
+ if (Results.size() > 1)
+ return false;
+ MapCaseToResult(CaseVal, UniqueResults, Results.begin()->second);
+
+ // Check the PHI consistency.
+ if (!PHI)
+ PHI = Results[0].first;
+ else if (PHI != Results[0].first)
+ return false;
+ }
+ // Find the default result value.
+ SmallVector<std::pair<PHINode *, Constant *>, 1> DefaultResults;
+ BasicBlock *DefaultDest = SI->getDefaultDest();
+ GetCaseResults(SI, nullptr, SI->getDefaultDest(), &CommonDest, DefaultResults,
+ DL);
+ // If the default value is not found abort unless the default destination
+ // is unreachable.
+ DefaultResult =
+ DefaultResults.size() == 1 ? DefaultResults.begin()->second : nullptr;
+ if ((!DefaultResult &&
+ !isa<UnreachableInst>(DefaultDest->getFirstNonPHIOrDbg())))
+ return false;
+
+ return true;
+}
+
+// ConvertTwoCaseSwitch - Helper function that checks if it is possible to
+// transform a switch with only two cases (or two cases + default)
+// that produces a result into a value select.
+// Example:
+// switch (a) {
+// case 10: %0 = icmp eq i32 %a, 10
+// return 10; %1 = select i1 %0, i32 10, i32 4
+// case 20: ----> %2 = icmp eq i32 %a, 20
+// return 2; %3 = select i1 %2, i32 2, i32 %1
+// default:
+// return 4;
+// }
+static Value *
+ConvertTwoCaseSwitch(const SwitchCaseResultVectorTy &ResultVector,
+ Constant *DefaultResult, Value *Condition,
+ IRBuilder<> &Builder) {
+ assert(ResultVector.size() == 2 &&
+ "We should have exactly two unique results at this point");
+ // If we are selecting between only two cases transform into a simple
+ // select or a two-way select if default is possible.
+ if (ResultVector[0].second.size() == 1 &&
+ ResultVector[1].second.size() == 1) {
+ ConstantInt *const FirstCase = ResultVector[0].second[0];
+ ConstantInt *const SecondCase = ResultVector[1].second[0];
+
+ bool DefaultCanTrigger = DefaultResult;
+ Value *SelectValue = ResultVector[1].first;
+ if (DefaultCanTrigger) {
+ Value *const ValueCompare =
+ Builder.CreateICmpEQ(Condition, SecondCase, "switch.selectcmp");
+ SelectValue = Builder.CreateSelect(ValueCompare, ResultVector[1].first,
+ DefaultResult, "switch.select");
+ }
+ Value *const ValueCompare =
+ Builder.CreateICmpEQ(Condition, FirstCase, "switch.selectcmp");
+ return Builder.CreateSelect(ValueCompare, ResultVector[0].first, SelectValue,
+ "switch.select");
+ }
+
+ return nullptr;
+}
+
+// RemoveSwitchAfterSelectConversion - Helper function to cleanup a switch
+// instruction that has been converted into a select, fixing up PHI nodes and
+// basic blocks.
+static void RemoveSwitchAfterSelectConversion(SwitchInst *SI, PHINode *PHI,
+ Value *SelectValue,
+ IRBuilder<> &Builder) {
+ BasicBlock *SelectBB = SI->getParent();
+ while (PHI->getBasicBlockIndex(SelectBB) >= 0)
+ PHI->removeIncomingValue(SelectBB);
+ PHI->addIncoming(SelectValue, SelectBB);
+
+ Builder.CreateBr(PHI->getParent());
+
+ // Remove the switch.
+ for (unsigned i = 0, e = SI->getNumSuccessors(); i < e; ++i) {
+ BasicBlock *Succ = SI->getSuccessor(i);
+
+ if (Succ == PHI->getParent())
+ continue;
+ Succ->removePredecessor(SelectBB);
+ }
+ SI->eraseFromParent();
+}
+
+/// SwitchToSelect - If the switch is only used to initialize one or more
+/// 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) {
+ 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))
+ return false;
+ // Selects choose between maximum two values.
+ if (UniqueResults.size() != 2)
+ return false;
+ assert(PHI != nullptr && "PHI for value select not found");
+
+ Builder.SetInsertPoint(SI);
+ Value *SelectValue = ConvertTwoCaseSwitch(
+ UniqueResults,
+ DefaultResult, Cond, Builder);
+ if (SelectValue) {
+ RemoveSwitchAfterSelectConversion(SI, PHI, SelectValue, Builder);
+ return true;
+ }
+ // The switch couldn't be converted into a select.
+ return false;
+}
+
namespace {
/// SwitchLookupTable - This class represents a lookup table that can be used
/// to replace a switch.
// store that single value and return it for each lookup.
SingleValueKind,
+ // For tables where there is a linear relationship between table index
+ // and values. We calculate the result with a simple multiplication
+ // and addition instead of a table lookup.
+ LinearMapKind,
+
// For small tables with integer elements, we can pack them into a bitmap
// that fits into a target-legal register. Values are retrieved by
// shift and mask operations.
ConstantInt *BitMap;
IntegerType *BitMapElementTy;
+ // For LinearMapKind, these are the constants used to derive the value.
+ ConstantInt *LinearOffset;
+ ConstantInt *LinearMultiplier;
+
// For ArrayKind, this is the array.
GlobalVariable *Array;
};
Constant *DefaultValue,
const DataLayout *DL)
: SingleValue(nullptr), BitMap(nullptr), BitMapElementTy(nullptr),
- Array(nullptr) {
+ LinearOffset(nullptr), LinearMultiplier(nullptr), Array(nullptr) {
assert(Values.size() && "Can't build lookup table without values!");
assert(TableSize >= Values.size() && "Can't fit values in table!");
return;
}
+ // Check if we can derive the value with a linear transformation from the
+ // table index.
+ if (isa<IntegerType>(ValueType)) {
+ bool LinearMappingPossible = true;
+ APInt PrevVal;
+ APInt DistToPrev;
+ assert(TableSize >= 2 && "Should be a SingleValue table.");
+ // Check if there is the same distance between two consecutive values.
+ for (uint64_t I = 0; I < TableSize; ++I) {
+ ConstantInt *ConstVal = dyn_cast<ConstantInt>(TableContents[I]);
+ if (!ConstVal) {
+ // This is an undef. We could deal with it, but undefs in lookup tables
+ // are very seldom. It's probably not worth the additional complexity.
+ LinearMappingPossible = false;
+ break;
+ }
+ APInt Val = ConstVal->getValue();
+ if (I != 0) {
+ APInt Dist = Val - PrevVal;
+ if (I == 1) {
+ DistToPrev = Dist;
+ } else if (Dist != DistToPrev) {
+ LinearMappingPossible = false;
+ break;
+ }
+ }
+ PrevVal = Val;
+ }
+ if (LinearMappingPossible) {
+ LinearOffset = cast<ConstantInt>(TableContents[0]);
+ LinearMultiplier = ConstantInt::get(M.getContext(), DistToPrev);
+ Kind = LinearMapKind;
+ ++NumLinearMaps;
+ return;
+ }
+ }
+
// If the type is integer and the table fits in a register, build a bitmap.
if (WouldFitInRegister(DL, TableSize, ValueType)) {
IntegerType *IT = cast<IntegerType>(ValueType);
switch (Kind) {
case SingleValueKind:
return SingleValue;
+ case LinearMapKind: {
+ // Derive the result value from the input value.
+ Value *Result = Builder.CreateIntCast(Index, LinearMultiplier->getType(),
+ false, "switch.idx.cast");
+ if (!LinearMultiplier->isOne())
+ Result = Builder.CreateMul(Result, LinearMultiplier, "switch.idx.mult");
+ if (!LinearOffset->isZero())
+ Result = Builder.CreateAdd(Result, LinearOffset, "switch.offset");
+ return Result;
+ }
case BitMapKind: {
// Type of the bitmap (e.g. i59).
IntegerType *MapTy = BitMap->getType();
bool AllTablesFitInRegister = true;
bool HasIllegalType = false;
- for (SmallDenseMap<PHINode*, Type*>::const_iterator I = ResultTypes.begin(),
- E = ResultTypes.end(); I != E; ++I) {
- Type *Ty = I->second;
+ for (const auto &I : ResultTypes) {
+ Type *Ty = I.second;
// Saturate this flag to true.
HasIllegalType = HasIllegalType || !TTI.isTypeLegal(Ty);
return false;
// Append the result from this case to the list for each phi.
- for (ResultsTy::iterator I = Results.begin(), E = Results.end(); I!=E; ++I) {
- if (!ResultLists.count(I->first))
- PHIs.push_back(I->first);
- ResultLists[I->first].push_back(std::make_pair(CaseVal, I->second));
+ for (const auto &I : Results) {
+ PHINode *PHI = I.first;
+ Constant *Value = I.second;
+ if (!ResultLists.count(PHI))
+ PHIs.push_back(PHI);
+ ResultLists[PHI].push_back(std::make_pair(CaseVal, Value));
}
}
// Keep track of the result types.
- for (size_t I = 0, E = PHIs.size(); I != E; ++I) {
- PHINode *PHI = PHIs[I];
+ for (PHINode *PHI : PHIs) {
ResultTypes[PHI] = ResultLists[PHI][0].second->getType();
}
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.
return false;
}
- for (size_t I = 0, E = DefaultResultsList.size(); I != E; ++I) {
- PHINode *PHI = DefaultResultsList[I].first;
- Constant *Result = DefaultResultsList[I].second;
+ for (const auto &I : DefaultResultsList) {
+ PHINode *PHI = I.first;
+ Constant *Result = I.second;
DefaultResults[PHI] = Result;
}
CommonDest->getParent(),
CommonDest);
+ // Make the mask's bitwidth at least 8bit and a power-of-2 to avoid
+ // unnecessary illegal types.
+ uint64_t TableSizePowOf2 = NextPowerOf2(std::max(7ULL, TableSize - 1ULL));
+ APInt MaskInt(TableSizePowOf2, 0);
+ APInt One(TableSizePowOf2, 1);
// Build bitmask; fill in a 1 bit for every case.
- APInt MaskInt(TableSize, 0);
- APInt One(TableSize, 1);
const ResultListTy &ResultList = ResultLists[PHIs[0]];
for (size_t I = 0, E = ResultList.size(); I != E; ++I) {
uint64_t Idx = (ResultList[I].first->getValue() -
if (EliminateDeadSwitchCases(SI, DL, AT))
return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AT) | true;
+ if (SwitchToSelect(SI, Builder, DL, AT))
+ return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AT) | true;
+
if (ForwardSwitchConditionToPHI(SI))
return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AT) | true;
SmallPtrSet<Value *, 8> Succs;
for (unsigned i = 0, e = IBI->getNumDestinations(); i != e; ++i) {
BasicBlock *Dest = IBI->getDestination(i);
- if (!Dest->hasAddressTaken() || !Succs.insert(Dest)) {
+ if (!Dest->hasAddressTaken() || !Succs.insert(Dest).second) {
Dest->removePredecessor(BB);
IBI->removeDestination(i);
--i; --e;
projects / oota-llvm.git / blobdiff