aboutsummaryrefslogtreecommitdiff
path: root/llvm/lib/Transforms/Utils/SimplifyCFG.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'llvm/lib/Transforms/Utils/SimplifyCFG.cpp')
-rw-r--r--llvm/lib/Transforms/Utils/SimplifyCFG.cpp269
1 files changed, 145 insertions, 124 deletions
diff --git a/llvm/lib/Transforms/Utils/SimplifyCFG.cpp b/llvm/lib/Transforms/Utils/SimplifyCFG.cpp
index 84a838b..02d6393 100644
--- a/llvm/lib/Transforms/Utils/SimplifyCFG.cpp
+++ b/llvm/lib/Transforms/Utils/SimplifyCFG.cpp
@@ -6441,34 +6441,39 @@ static bool trySwitchToSelect(SwitchInst *SI, IRBuilder<> &Builder,
namespace {
-/// This class represents a lookup table that can be used to replace a switch.
-class SwitchLookupTable {
+/// This class finds alternatives for switches to ultimately
+/// replace the switch.
+class SwitchReplacement {
public:
- /// 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(
+ /// Create a helper for optimizations to use as a switch replacement.
+ /// Find a better representation for the content of Values,
+ /// using DefaultValue to fill any holes in the table.
+ SwitchReplacement(
Module &M, uint64_t TableSize, ConstantInt *Offset,
const SmallVectorImpl<std::pair<ConstantInt *, Constant *>> &Values,
Constant *DefaultValue, const DataLayout &DL, const StringRef &FuncName);
- /// Build instructions with Builder to retrieve the value at
- /// the position given by Index in the lookup table.
- Value *buildLookup(Value *Index, IRBuilder<> &Builder, const DataLayout &DL);
+ /// Build instructions with Builder to retrieve values using Index
+ /// and replace the switch.
+ Value *replaceSwitch(Value *Index, IRBuilder<> &Builder, const DataLayout &DL,
+ Function *Func);
/// 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,
Type *ElementType);
+ /// Return the default value of the switch.
+ Constant *getDefaultValue();
+
private:
- // Depending on the contents of the table, it can be represented in
- // different ways.
+ // Depending on the switch, there are different alternatives.
enum {
- // For tables where each element contains the same value, we just have to
+ // For switches where each case contains the same value, we just have to
// store that single value and return it for each lookup.
SingleValueKind,
- // For tables where there is a linear relationship between table index
+ // For switches 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,
@@ -6480,9 +6485,15 @@ private:
// The table is stored as an array of values. Values are retrieved by load
// instructions from the table.
- ArrayKind
+ LookupTableKind
} Kind;
+ // The default value of the switch.
+ Constant *DefaultValue;
+
+ // The type of the output values.
+ Type *ValueType;
+
// For SingleValueKind, this is the single value.
Constant *SingleValue = nullptr;
@@ -6495,23 +6506,24 @@ private:
ConstantInt *LinearMultiplier = nullptr;
bool LinearMapValWrapped = false;
- // For ArrayKind, this is the array.
- GlobalVariable *Array = nullptr;
+ // For LookupTableKind, this is the table.
+ Constant *Initializer = nullptr;
};
} // end anonymous namespace
-SwitchLookupTable::SwitchLookupTable(
+SwitchReplacement::SwitchReplacement(
Module &M, uint64_t TableSize, ConstantInt *Offset,
const SmallVectorImpl<std::pair<ConstantInt *, Constant *>> &Values,
- Constant *DefaultValue, const DataLayout &DL, const StringRef &FuncName) {
+ Constant *DefaultValue, const DataLayout &DL, const StringRef &FuncName)
+ : DefaultValue(DefaultValue) {
assert(Values.size() && "Can't build lookup table without values!");
assert(TableSize >= Values.size() && "Can't fit values in table!");
// If all values in the table are equal, this is that value.
SingleValue = Values.begin()->second;
- Type *ValueType = Values.begin()->second->getType();
+ ValueType = Values.begin()->second->getType();
// Build up the table contents.
SmallVector<Constant *, 64> TableContents(TableSize);
@@ -6626,21 +6638,14 @@ SwitchLookupTable::SwitchLookupTable(
}
// Store the table in an array.
- ArrayType *ArrayTy = ArrayType::get(ValueType, TableSize);
- Constant *Initializer = ConstantArray::get(ArrayTy, TableContents);
-
- Array = new GlobalVariable(M, ArrayTy, /*isConstant=*/true,
- GlobalVariable::PrivateLinkage, Initializer,
- "switch.table." + FuncName);
- Array->setUnnamedAddr(GlobalValue::UnnamedAddr::Global);
- // Set the alignment to that of an array items. We will be only loading one
- // value out of it.
- Array->setAlignment(DL.getPrefTypeAlign(ValueType));
- Kind = ArrayKind;
+ auto *TableTy = ArrayType::get(ValueType, TableSize);
+ Initializer = ConstantArray::get(TableTy, TableContents);
+
+ Kind = LookupTableKind;
}
-Value *SwitchLookupTable::buildLookup(Value *Index, IRBuilder<> &Builder,
- const DataLayout &DL) {
+Value *SwitchReplacement::replaceSwitch(Value *Index, IRBuilder<> &Builder,
+ const DataLayout &DL, Function *Func) {
switch (Kind) {
case SingleValueKind:
return SingleValue;
@@ -6681,9 +6686,17 @@ Value *SwitchLookupTable::buildLookup(Value *Index, IRBuilder<> &Builder,
// Mask off.
return Builder.CreateTrunc(DownShifted, BitMapElementTy, "switch.masked");
}
- case ArrayKind: {
- Type *IndexTy = DL.getIndexType(Array->getType());
- auto *ArrayTy = cast<ArrayType>(Array->getValueType());
+ case LookupTableKind: {
+ auto *Table =
+ new GlobalVariable(*Func->getParent(), Initializer->getType(),
+ /*isConstant=*/true, GlobalVariable::PrivateLinkage,
+ Initializer, "switch.table." + Func->getName());
+ Table->setUnnamedAddr(GlobalValue::UnnamedAddr::Global);
+ // Set the alignment to that of an array items. We will be only loading one
+ // value out of it.
+ Table->setAlignment(DL.getPrefTypeAlign(ValueType));
+ Type *IndexTy = DL.getIndexType(Table->getType());
+ auto *ArrayTy = cast<ArrayType>(Table->getValueType());
if (Index->getType() != IndexTy) {
unsigned OldBitWidth = Index->getType()->getIntegerBitWidth();
@@ -6695,14 +6708,14 @@ Value *SwitchLookupTable::buildLookup(Value *Index, IRBuilder<> &Builder,
Value *GEPIndices[] = {ConstantInt::get(IndexTy, 0), Index};
Value *GEP =
- Builder.CreateInBoundsGEP(ArrayTy, Array, GEPIndices, "switch.gep");
+ Builder.CreateInBoundsGEP(ArrayTy, Table, GEPIndices, "switch.gep");
return Builder.CreateLoad(ArrayTy->getElementType(), GEP, "switch.load");
}
}
- llvm_unreachable("Unknown lookup table kind!");
+ llvm_unreachable("Unknown helper kind!");
}
-bool SwitchLookupTable::wouldFitInRegister(const DataLayout &DL,
+bool SwitchReplacement::wouldFitInRegister(const DataLayout &DL,
uint64_t TableSize,
Type *ElementType) {
auto *IT = dyn_cast<IntegerType>(ElementType);
@@ -6738,6 +6751,8 @@ static bool isTypeLegalForLookupTable(Type *Ty, const TargetTransformInfo &TTI,
DL.fitsInLegalInteger(IT->getBitWidth());
}
+Constant *SwitchReplacement::getDefaultValue() { return DefaultValue; }
+
static bool isSwitchDense(uint64_t NumCases, uint64_t CaseRange) {
// 40% is the default density for building a jump table in optsize/minsize
// mode. See also TargetLoweringBase::isSuitableForJumpTable(), which this
@@ -6764,25 +6779,23 @@ static bool isSwitchDense(ArrayRef<int64_t> Values) {
// TODO: We could support larger than legal types by limiting based on the
// number of loads required and/or table size. If the constants are small we
// could use smaller table entries and extend after the load.
-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 SmallVector<Type *> &ResultTypes) {
if (SI->getNumCases() > TableSize)
return false; // TableSize overflowed.
bool AllTablesFitInRegister = true;
bool HasIllegalType = false;
- for (const auto &I : ResultTypes) {
- Type *Ty = I.second;
-
+ for (const auto &Ty : ResultTypes) {
// Saturate this flag to true.
HasIllegalType = HasIllegalType || !isTypeLegalForLookupTable(Ty, TTI, DL);
// Saturate this flag to false.
AllTablesFitInRegister =
AllTablesFitInRegister &&
- SwitchLookupTable::wouldFitInRegister(DL, TableSize, Ty);
+ SwitchReplacement::wouldFitInRegister(DL, TableSize, Ty);
// If both flags saturate, we're done. NOTE: This *only* works with
// saturating flags, and all flags have to saturate first due to the
@@ -6804,7 +6817,7 @@ shouldBuildLookupTable(SwitchInst *SI, uint64_t TableSize,
static bool shouldUseSwitchConditionAsTableIndex(
ConstantInt &MinCaseVal, const ConstantInt &MaxCaseVal,
- bool HasDefaultResults, const SmallDenseMap<PHINode *, Type *> &ResultTypes,
+ bool HasDefaultResults, const SmallVector<Type *> &ResultTypes,
const DataLayout &DL, const TargetTransformInfo &TTI) {
if (MinCaseVal.isNullValue())
return true;
@@ -6812,10 +6825,9 @@ static bool shouldUseSwitchConditionAsTableIndex(
MaxCaseVal.getLimitedValue() == std::numeric_limits<uint64_t>::max() ||
!HasDefaultResults)
return false;
- return all_of(ResultTypes, [&](const auto &KV) {
- return SwitchLookupTable::wouldFitInRegister(
- DL, MaxCaseVal.getLimitedValue() + 1 /* TableSize */,
- KV.second /* ResultType */);
+ return all_of(ResultTypes, [&](const auto &ResultType) {
+ return SwitchReplacement::wouldFitInRegister(
+ DL, MaxCaseVal.getLimitedValue() + 1 /* TableSize */, ResultType);
});
}
@@ -6904,9 +6916,9 @@ static void reuseTableCompare(
/// 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,
- DomTreeUpdater *DTU, const DataLayout &DL,
- const TargetTransformInfo &TTI) {
+static bool simplifySwitchLookup(SwitchInst *SI, IRBuilder<> &Builder,
+ DomTreeUpdater *DTU, const DataLayout &DL,
+ const TargetTransformInfo &TTI) {
assert(SI->getNumCases() > 1 && "Degenerate switch?");
BasicBlock *BB = SI->getParent();
@@ -6942,7 +6954,7 @@ static bool switchToLookupTable(SwitchInst *SI, IRBuilder<> &Builder,
SmallDenseMap<PHINode *, ResultListTy> ResultLists;
SmallDenseMap<PHINode *, Constant *> DefaultResults;
- SmallDenseMap<PHINode *, Type *> ResultTypes;
+ SmallVector<Type *> ResultTypes;
SmallVector<PHINode *, 4> PHIs;
for (SwitchInst::CaseIt E = SI->case_end(); CI != E; ++CI) {
@@ -6959,7 +6971,8 @@ static bool switchToLookupTable(SwitchInst *SI, IRBuilder<> &Builder,
Results, DL, TTI))
return false;
- // Append the result from this case to the list for each phi.
+ // Append the result and result types from this case to the list for each
+ // phi.
for (const auto &I : Results) {
PHINode *PHI = I.first;
Constant *Value = I.second;
@@ -6967,23 +6980,16 @@ static bool switchToLookupTable(SwitchInst *SI, IRBuilder<> &Builder,
if (Inserted)
PHIs.push_back(PHI);
It->second.push_back(std::make_pair(CaseVal, Value));
+ ResultTypes.push_back(PHI->getType());
}
}
- // Keep track of the result types.
- for (PHINode *PHI : PHIs) {
- ResultTypes[PHI] = ResultLists[PHI][0].second->getType();
- }
-
- uint64_t NumResults = ResultLists[PHIs[0]].size();
-
// 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 =
getCaseResults(SI, nullptr, SI->getDefaultDest(), &CommonDest,
DefaultResultsList, DL, TTI);
-
for (const auto &I : DefaultResultsList) {
PHINode *PHI = I.first;
Constant *Result = I.second;
@@ -6993,15 +6999,21 @@ static bool switchToLookupTable(SwitchInst *SI, IRBuilder<> &Builder,
bool UseSwitchConditionAsTableIndex = shouldUseSwitchConditionAsTableIndex(
*MinCaseVal, *MaxCaseVal, HasDefaultResults, ResultTypes, DL, TTI);
uint64_t TableSize;
- if (UseSwitchConditionAsTableIndex)
+ ConstantInt *TableIndexOffset;
+ if (UseSwitchConditionAsTableIndex) {
TableSize = MaxCaseVal->getLimitedValue() + 1;
- else
+ TableIndexOffset = ConstantInt::get(MaxCaseVal->getIntegerType(), 0);
+ } else {
TableSize =
(MaxCaseVal->getValue() - MinCaseVal->getValue()).getLimitedValue() + 1;
+ TableIndexOffset = MinCaseVal;
+ }
+
// 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.
+ uint64_t NumResults = ResultLists[PHIs[0]].size();
bool DefaultIsReachable = !SI->defaultDestUnreachable();
bool TableHasHoles = (NumResults < TableSize);
@@ -7029,68 +7041,86 @@ static bool switchToLookupTable(SwitchInst *SI, IRBuilder<> &Builder,
if (!shouldBuildLookupTable(SI, TableSize, TTI, DL, ResultTypes))
return false;
- std::vector<DominatorTree::UpdateType> Updates;
-
- // Compute the maximum table size representable by the integer type we are
- // switching upon.
- unsigned CaseSize = MinCaseVal->getType()->getPrimitiveSizeInBits();
- uint64_t MaxTableSize = CaseSize > 63 ? UINT64_MAX : 1ULL << CaseSize;
- assert(MaxTableSize >= TableSize &&
- "It is impossible for a switch to have more entries than the max "
- "representable value of its input integer type's size.");
-
- // Create the BB that does the lookups.
- Module &Mod = *CommonDest->getParent()->getParent();
- BasicBlock *LookupBB = BasicBlock::Create(
- Mod.getContext(), "switch.lookup", CommonDest->getParent(), CommonDest);
-
// Compute the table index value.
- Builder.SetInsertPoint(SI);
Value *TableIndex;
- ConstantInt *TableIndexOffset;
if (UseSwitchConditionAsTableIndex) {
- TableIndexOffset = ConstantInt::get(MaxCaseVal->getIntegerType(), 0);
TableIndex = SI->getCondition();
- } else {
- TableIndexOffset = MinCaseVal;
+ if (HasDefaultResults) {
+ // Grow the table to cover all possible index values to avoid the range
+ // check. It will use the default result to fill in the table hole later,
+ // so make sure it exist.
+ ConstantRange CR =
+ computeConstantRange(TableIndex, /* ForSigned */ false);
+ // Grow the table shouldn't have any size impact by checking
+ // wouldFitInRegister.
+ // TODO: Consider growing the table also when it doesn't fit in a register
+ // if no optsize is specified.
+ const uint64_t UpperBound = CR.getUpper().getLimitedValue();
+ if (!CR.isUpperWrapped() &&
+ all_of(ResultTypes, [&](const auto &ResultType) {
+ return SwitchReplacement::wouldFitInRegister(DL, UpperBound,
+ ResultType);
+ })) {
+ // There may be some case index larger than the UpperBound (unreachable
+ // case), so make sure the table size does not get smaller.
+ TableSize = std::max(UpperBound, TableSize);
+ // The default branch is unreachable after we enlarge the lookup table.
+ // Adjust DefaultIsReachable to reuse code path.
+ DefaultIsReachable = false;
+ }
+ }
+ }
+
+ // Keep track of the switch replacement for each phi
+ SmallDenseMap<PHINode *, SwitchReplacement> PhiToReplacementMap;
+ for (PHINode *PHI : PHIs) {
+ const auto &ResultList = ResultLists[PHI];
+
+ Type *ResultType = ResultList.begin()->second->getType();
+ // Use any value to fill the lookup table holes.
+ Constant *DefaultVal =
+ AllHolesArePoison ? PoisonValue::get(ResultType) : DefaultResults[PHI];
+ StringRef FuncName = Fn->getName();
+ SwitchReplacement Replacement(*Fn->getParent(), TableSize, TableIndexOffset,
+ ResultList, DefaultVal, DL, FuncName);
+ PhiToReplacementMap.insert({PHI, Replacement});
+ }
+
+ Builder.SetInsertPoint(SI);
+ // TableIndex is the switch condition - TableIndexOffset if we don't
+ // use the condition directly
+ if (!UseSwitchConditionAsTableIndex) {
// If the default is unreachable, all case values are s>= MinCaseVal. Then
// we can try to attach nsw.
bool MayWrap = true;
if (!DefaultIsReachable) {
- APInt Res = MaxCaseVal->getValue().ssub_ov(MinCaseVal->getValue(), MayWrap);
+ APInt Res =
+ MaxCaseVal->getValue().ssub_ov(MinCaseVal->getValue(), MayWrap);
(void)Res;
}
-
TableIndex = Builder.CreateSub(SI->getCondition(), TableIndexOffset,
"switch.tableidx", /*HasNUW =*/false,
/*HasNSW =*/!MayWrap);
}
- BranchInst *RangeCheckBranch = nullptr;
+ std::vector<DominatorTree::UpdateType> Updates;
- // Grow the table to cover all possible index values to avoid the range check.
- // It will use the default result to fill in the table hole later, so make
- // sure it exist.
- if (UseSwitchConditionAsTableIndex && HasDefaultResults) {
- ConstantRange CR = computeConstantRange(TableIndex, /* ForSigned */ false);
- // Grow the table shouldn't have any size impact by checking
- // wouldFitInRegister.
- // TODO: Consider growing the table also when it doesn't fit in a register
- // if no optsize is specified.
- const uint64_t UpperBound = CR.getUpper().getLimitedValue();
- if (!CR.isUpperWrapped() && all_of(ResultTypes, [&](const auto &KV) {
- return SwitchLookupTable::wouldFitInRegister(
- DL, UpperBound, KV.second /* ResultType */);
- })) {
- // There may be some case index larger than the UpperBound (unreachable
- // case), so make sure the table size does not get smaller.
- TableSize = std::max(UpperBound, TableSize);
- // The default branch is unreachable after we enlarge the lookup table.
- // Adjust DefaultIsReachable to reuse code path.
- DefaultIsReachable = false;
- }
- }
+ // Compute the maximum table size representable by the integer type we are
+ // switching upon.
+ unsigned CaseSize = MinCaseVal->getType()->getPrimitiveSizeInBits();
+ uint64_t MaxTableSize = CaseSize > 63 ? UINT64_MAX : 1ULL << CaseSize;
+ assert(MaxTableSize >= TableSize &&
+ "It is impossible for a switch to have more entries than the max "
+ "representable value of its input integer type's size.");
+ // Create the BB that does the lookups.
+ Module &Mod = *CommonDest->getParent()->getParent();
+ BasicBlock *LookupBB = BasicBlock::Create(
+ Mod.getContext(), "switch.lookup", CommonDest->getParent(), CommonDest);
+
+ BranchInst *RangeCheckBranch = nullptr;
+
+ Builder.SetInsertPoint(SI);
const bool GeneratingCoveredLookupTable = (MaxTableSize == TableSize);
if (!DefaultIsReachable || GeneratingCoveredLookupTable) {
Builder.CreateBr(LookupBB);
@@ -7161,25 +7191,16 @@ static bool switchToLookupTable(SwitchInst *SI, IRBuilder<> &Builder,
for (PHINode *PHI : PHIs) {
const ResultListTy &ResultList = ResultLists[PHI];
-
- Type *ResultType = ResultList.begin()->second->getType();
-
- // Use any value to fill the lookup table holes.
- Constant *DV =
- AllHolesArePoison ? PoisonValue::get(ResultType) : DefaultResults[PHI];
- StringRef FuncName = Fn->getName();
- SwitchLookupTable Table(Mod, TableSize, TableIndexOffset, ResultList, DV,
- DL, FuncName);
-
- Value *Result = Table.buildLookup(TableIndex, Builder, DL);
-
+ auto Replacement = PhiToReplacementMap.at(PHI);
+ auto *Result = Replacement.replaceSwitch(TableIndex, Builder, DL, Fn);
// 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);
+ reuseTableCompare(User, PhiBlock, RangeCheckBranch,
+ Replacement.getDefaultValue(), ResultList);
}
}
@@ -7712,7 +7733,7 @@ bool SimplifyCFGOpt::simplifySwitch(SwitchInst *SI, IRBuilder<> &Builder) {
// CVP. Therefore, only apply this transformation during late stages of the
// optimisation pipeline.
if (Options.ConvertSwitchToLookupTable &&
- switchToLookupTable(SI, Builder, DTU, DL, TTI))
+ simplifySwitchLookup(SI, Builder, DTU, DL, TTI))
return requestResimplify();
if (simplifySwitchOfPowersOfTwo(SI, Builder, DL, TTI))
generated by cgit v1.1 at 2025-10-01 21:00:04 +0000