[NFC] SimplifyCFG: Detect switch replacement earlier in switchToLookup
#155602
Conversation
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Move the insertion into ResultTypes further up and the NumResults further down.
If we use the switch condition as table index, the default results can influence the TableSize. The TableSize is used for the decision whether we want to create a table in the first place, so it makes sense to set TableIndex and the final TableSize before the check in `shouldBuildLookupTable`. However, if we do not use the switch condition as the table index, we move the setting *after* the decision to build it. Since we need to create a sub instruction in that case, only do that once we are sure. Additionally, that case does not influence the TableSize, so there is no harm in setting it later.
The table decides what kind of lookup table is created. To become more flexible in a future change, we want to know the type before we check if we want to create it.
Previously, the global LUT was created in the constructor of SwitchLookupTable. Since we want to call the constructor way earlier to decide what kind of LUT to create (and if we want to create any), this can create the LUT unnecessarily if we later on decide not to use one. Only create it once we are certain we want to create a LUT.
|
@llvm/pr-subscribers-llvm-transforms Author: Jessica Del (OutOfCache) ChangesThis PR is the first part to solve the issue in #149937. The end goal is enabling more switch optimizations on targets that do not support lookup tables. SimplifyCFG has the ability to replace switches with either a few simple calculations, a single value, or a lookup table. To enable more targets to use these other kinds of optimization, this PR restructures the code in This PR moves the code so it first determines the replacement kind and then generates the instructions. A later PR will insert the target support check after determining the kind of replacement. If the result is not a LUT, then even targets without LUT support can replace the switch with something else. Full diff: https://github.com/llvm/llvm-project/pull/155602.diff 1 Files Affected:
diff --git a/llvm/lib/Transforms/Utils/SimplifyCFG.cpp b/llvm/lib/Transforms/Utils/SimplifyCFG.cpp
index ef110a6922f05..a8bae3f99746a 100644
--- a/llvm/lib/Transforms/Utils/SimplifyCFG.cpp
+++ b/llvm/lib/Transforms/Utils/SimplifyCFG.cpp
@@ -6437,19 +6437,22 @@ 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.
@@ -6457,14 +6460,13 @@ class SwitchLookupTable {
Type *ElementType);
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,
@@ -6476,9 +6478,12 @@ class SwitchLookupTable {
// The table is stored as an array of values. Values are retrieved by load
// instructions from the table.
- ArrayKind
+ LookupTableKind
} Kind;
+ // The type of the output values.
+ Type *ValueType;
+
// For SingleValueKind, this is the single value.
Constant *SingleValue = nullptr;
@@ -6491,13 +6496,15 @@ class SwitchLookupTable {
ConstantInt *LinearMultiplier = nullptr;
bool LinearMapValWrapped = false;
- // For ArrayKind, this is the array.
- GlobalVariable *Array = nullptr;
+ // For LookupTableKind, this is the table.
+ GlobalVariable *Table = nullptr;
+ ArrayType *TableTy = nullptr;
+ 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) {
@@ -6507,7 +6514,7 @@ SwitchLookupTable::SwitchLookupTable(
// 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);
@@ -6622,21 +6629,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;
+ 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;
@@ -6677,9 +6677,18 @@ 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: {
+ // Only build lookup table when we have a target that supports it or the
+ // attribute is notable.
+ Table = new GlobalVariable(*Func->getParent(), TableTy, /*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();
@@ -6691,14 +6700,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);
@@ -6778,7 +6787,7 @@ shouldBuildLookupTable(SwitchInst *SI, uint64_t TableSize,
// 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
@@ -6809,7 +6818,7 @@ static bool shouldUseSwitchConditionAsTableIndex(
!HasDefaultResults)
return false;
return all_of(ResultTypes, [&](const auto &KV) {
- return SwitchLookupTable::wouldFitInRegister(
+ return SwitchReplacement::wouldFitInRegister(
DL, MaxCaseVal.getLimitedValue() + 1 /* TableSize */,
KV.second /* ResultType */);
});
@@ -6900,9 +6909,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();
@@ -6955,7 +6964,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;
@@ -6963,23 +6973,16 @@ static bool switchToLookupTable(SwitchInst *SI, IRBuilder<> &Builder,
if (Inserted)
PHIs.push_back(PHI);
It->second.push_back(std::make_pair(CaseVal, Value));
+ ResultTypes[PHI] = ResultLists[PHI][0].second->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;
@@ -6989,15 +6992,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);
@@ -7022,9 +7031,76 @@ static bool switchToLookupTable(SwitchInst *SI, IRBuilder<> &Builder,
return false;
}
+ // Compute the table index value.
+ Value *TableIndex;
+ if (UseSwitchConditionAsTableIndex) {
+ TableIndex = SI->getCondition();
+ 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 &KV) {
+ return SwitchReplacement::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;
+ }
+ }
+ }
+
if (!shouldBuildLookupTable(SI, TableSize, TTI, DL, ResultTypes))
return false;
+ 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);
+ (void)Res;
+ }
+ TableIndex = Builder.CreateSub(SI->getCondition(), TableIndexOffset,
+ "switch.tableidx", /*HasNUW =*/false,
+ /*HasNSW =*/!MayWrap);
+ }
+
+ // Keep track of the tables we create for each phi node
+ struct ReplacementParams {
+ SwitchReplacement Replacer;
+ Constant *DefaultVal;
+ };
+ // Keep track of the switch replacement for each phi
+ SmallDenseMap<PHINode *, ReplacementParams> 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);
+ ReplacementParams Parameters = {Replacement, DefaultVal};
+ PhiToReplacementMap.insert({PHI, Parameters});
+ }
+
std::vector<DominatorTree::UpdateType> Updates;
// Compute the maximum table size representable by the integer type we are
@@ -7040,53 +7116,9 @@ static bool switchToLookupTable(SwitchInst *SI, IRBuilder<> &Builder,
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 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);
- (void)Res;
- }
-
- TableIndex = Builder.CreateSub(SI->getCondition(), TableIndexOffset,
- "switch.tableidx", /*HasNUW =*/false,
- /*HasNSW =*/!MayWrap);
- }
-
BranchInst *RangeCheckBranch = nullptr;
- // 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;
- }
- }
-
+ Builder.SetInsertPoint(SI);
const bool GeneratingCoveredLookupTable = (MaxTableSize == TableSize);
if (!DefaultIsReachable || GeneratingCoveredLookupTable) {
Builder.CreateBr(LookupBB);
@@ -7157,25 +7189,17 @@ 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 TableInfo = PhiToReplacementMap.at(PHI);
+ auto *Result =
+ TableInfo.Replacer.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,
+ TableInfo.DefaultVal, ResultList);
}
}
@@ -7708,7 +7732,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))
|
|
✅ With the latest revision this PR passed the C/C++ code formatter. |
SwitchLookupTable -> SwitchReplacement This class contains more than just a typical lookup table. It helps to optimize the switch away, either by lookup table, or with a linear function, a bitmap, or a single value replacement. ArrayKind -> LookupTableKind ArrayKind is the "true" LUT kind. buildLookup -> replaceSwitch
8490b44 to
a2b2cff
Compare
nikic
reviewed
Aug 28, 2025
| DefaultIsReachable = false; | ||
| } | ||
| } | ||
| } |
There was a problem hiding this comment.
Why did this code get moved above shouldBuildLookupTable? Note that TableSize is passed to that function, so I'm not sure this is really NFC.
| } | ||
| TableIndex = Builder.CreateSub(SI->getCondition(), TableIndexOffset, | ||
| "switch.tableidx", /*HasNUW =*/false, | ||
| /*HasNSW =*/!MayWrap); |
There was a problem hiding this comment.
If you want to make decisions after creating the SwitchReplacements below, wouldn't this IR change be problematic? Doesn't it need to happen afterwards?
Track the default switch value in the SwitchReplacement.
ResultTypes was a map of PHINodes to a Type, but the PHINode key was never used. Track the types in a SmallVector instead.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
This PR is the first part to solve the issue in #149937.
The end goal is enabling more switch optimizations on targets that do not support lookup tables.
SimplifyCFG has the ability to replace switches with either a few simple calculations, a single value, or a lookup table.
However, it only considers these options if the target supports lookup tables, even if the final result is not a LUT, but a few simple instructions like muls, adds and shifts.
To enable more targets to use these other kinds of optimization, this PR restructures the code in
switchToLookup.Previously, code was generated even before choosing what kind of replacement to do. However, we need to know if we actually want to create a true LUT or not before generating anything. Then we can check for target support only if any LUT would be created.
This PR moves the code so it first determines the replacement kind and then generates the instructions.
A later PR will insert the target support check after determining the kind of replacement. If the result is not a LUT, then even targets without LUT support can replace the switch with something else.