21using namespace SwitchCG;
26 const APInt &LowCase = Clusters[
First].Low->getValue();
27 const APInt &HighCase = Clusters[
Last].High->getValue();
33 return (HighCase - LowCase).getLimitedValue((
UINT64_MAX - 1) / 100) + 1;
48 std::optional<SDLoc> SL,
57 for (
unsigned i = 1, e = Clusters.size(); i < e; ++i)
58 assert(Clusters[i - 1].
High->getValue().slt(Clusters[i].Low->getValue()));
61 assert(TLI &&
"TLI not set!");
66 const unsigned SmallNumberOfEntries = MinJumpTableEntries / 2;
69 const int64_t
N = Clusters.size();
70 if (
N < 2 ||
N < MinJumpTableEntries)
75 for (
unsigned i = 0; i <
N; ++i) {
76 const APInt &
Hi = Clusters[i].High->getValue();
77 const APInt &
Lo = Clusters[i].Low->getValue();
78 TotalCases[i] = (
Hi -
Lo).getLimitedValue() + 1;
80 TotalCases[i] += TotalCases[i - 1];
91 if (
buildJumpTable(Clusters, 0,
N - 1, SI, SL, DefaultMBB, JTCluster)) {
92 Clusters[0] = JTCluster;
119 enum PartitionScores :
unsigned {
127 MinPartitions[
N - 1] = 1;
128 LastElement[
N - 1] =
N - 1;
129 PartitionsScore[
N - 1] = PartitionScores::SingleCase;
132 for (int64_t i =
N - 2; i >= 0; i--) {
135 MinPartitions[i] = MinPartitions[i + 1] + 1;
137 PartitionsScore[i] = PartitionsScore[i + 1] + PartitionScores::SingleCase;
140 for (int64_t j =
N - 1; j > i; j--) {
145 assert(Range >= NumCases);
148 unsigned NumPartitions = 1 + (j ==
N - 1 ? 0 : MinPartitions[j + 1]);
149 unsigned Score = j ==
N - 1 ? 0 : PartitionsScore[j + 1];
150 int64_t NumEntries = j - i + 1;
153 Score += PartitionScores::SingleCase;
154 else if (NumEntries <= SmallNumberOfEntries)
155 Score += PartitionScores::FewCases;
156 else if (NumEntries >= MinJumpTableEntries)
157 Score += PartitionScores::Table;
161 if (NumPartitions < MinPartitions[i] ||
162 (NumPartitions == MinPartitions[i] && Score > PartitionsScore[i])) {
163 MinPartitions[i] = NumPartitions;
165 PartitionsScore[i] = Score;
172 unsigned DstIndex = 0;
180 if (NumClusters >= MinJumpTableEntries &&
182 Clusters[DstIndex++] = JTCluster;
185 std::memmove(&Clusters[DstIndex++], &Clusters[
I],
sizeof(Clusters[
I]));
188 Clusters.resize(DstIndex);
194 const std::optional<SDLoc> &SL,
200 unsigned NumCmps = 0;
201 std::vector<MachineBasicBlock*> Table;
210 Prob += Clusters[
I].Prob;
211 const APInt &
Low = Clusters[
I].Low->getValue();
212 const APInt &
High = Clusters[
I].High->getValue();
213 NumCmps += (
Low ==
High) ? 1 : 2;
216 const APInt &PreviousHigh = Clusters[
I - 1].High->getValue();
218 uint64_t Gap = (
Low - PreviousHigh).getLimitedValue() - 1;
220 Table.push_back(DefaultMBB);
223 for (
uint64_t J = 0; J < ClusterSize; ++J)
224 Table.push_back(Clusters[
I].MBB);
225 JTProbs[Clusters[
I].MBB] += Clusters[
I].Prob;
228 unsigned NumDests = JTProbs.
size();
229 if (TLI->isSuitableForBitTests(NumDests, NumCmps,
230 Clusters[
First].Low->getValue(),
231 Clusters[
Last].High->getValue(), *
DL)) {
245 if (
Done.count(Succ))
247 addSuccessorWithProb(JumpTableMBB, Succ, JTProbs[Succ]);
256 JumpTable JT(-1U, JTI, JumpTableMBB,
nullptr, SL);
258 Clusters[
Last].High->getValue(), SI->getCondition(),
260 JTCases.emplace_back(std::move(JTH), std::move(JT));
263 JTCases.size() - 1, Prob);
274 assert(!Clusters.empty());
278 for (
unsigned i = 1; i < Clusters.size(); ++i)
279 assert(Clusters[i-1].
High->getValue().slt(Clusters[i].Low->getValue()));
287 EVT PTy = TLI->getPointerTy(*
DL);
288 if (!TLI->isOperationLegal(
ISD::SHL, PTy))
292 const int64_t
N = Clusters.size();
302 MinPartitions[
N - 1] = 1;
303 LastElement[
N - 1] =
N - 1;
306 for (int64_t i =
N - 2; i >= 0; --i) {
309 MinPartitions[i] = MinPartitions[i + 1] + 1;
314 for (int64_t j = std::min(
N - 1, i +
BitWidth - 1); j > i; --j) {
318 if (!TLI->rangeFitsInWord(Clusters[i].Low->getValue(),
319 Clusters[j].High->getValue(), *
DL))
324 bool RangesOnly =
true;
325 BitVector Dests(FuncInfo.MF->getNumBlockIDs());
326 for (int64_t k = i; k <= j; k++) {
333 if (!RangesOnly || Dests.
count() > 3)
337 unsigned NumPartitions = 1 + (j ==
N - 1 ? 0 : MinPartitions[j + 1]);
338 if (NumPartitions < MinPartitions[i]) {
340 MinPartitions[i] = NumPartitions;
347 unsigned DstIndex = 0;
354 if (buildBitTests(Clusters,
First,
Last, SI, BitTestCluster)) {
355 Clusters[DstIndex++] = BitTestCluster;
358 std::memmove(&Clusters[DstIndex], &Clusters[
First],
359 sizeof(Clusters[0]) * NumClusters);
360 DstIndex += NumClusters;
363 Clusters.resize(DstIndex);
374 BitVector Dests(FuncInfo.MF->getNumBlockIDs());
375 unsigned NumCmps = 0;
379 NumCmps += (Clusters[
I].Low == Clusters[
I].High) ? 1 : 2;
381 unsigned NumDests = Dests.
count();
387 if (!TLI->isSuitableForBitTests(NumDests, NumCmps,
Low,
High, *
DL))
393 const int BitWidth = TLI->getPointerTy(*DL).getSizeInBits();
395 "Case range must fit in bit mask!");
399 bool ContiguousRange =
true;
401 if (Clusters[
I].
Low->getValue() != Clusters[
I - 1].High->getValue() + 1) {
402 ContiguousRange =
false;
412 ContiguousRange =
false;
420 for (
unsigned i =
First; i <=
Last; ++i) {
423 for (j = 0; j < CBV.size(); ++j)
424 if (CBV[j].BB == Clusters[i].
MBB)
432 uint64_t Lo = (Clusters[i].Low->getValue() - LowBound).getZExtValue();
433 uint64_t Hi = (Clusters[i].High->getValue() - LowBound).getZExtValue();
435 CB->
Mask |= (-1ULL >> (63 - (
Hi -
Lo))) <<
Lo;
438 TotalProb += Clusters[i].Prob;
447 return a.
Bits > b.Bits;
448 return a.
Mask < b.Mask;
451 for (
auto &CB : CBV) {
453 FuncInfo.MF->CreateMachineBasicBlock(SI->getParent());
456 BitTestCases.emplace_back(std::move(LowBound), std::move(CmpRange),
457 SI->getCondition(), -1U, MVT::Other,
false,
458 ContiguousRange,
nullptr,
nullptr, std::move(BTI),
462 BitTestCases.size() - 1, TotalProb);
469 assert(
CC.Low ==
CC.High &&
"Input clusters must be single-case");
477 const unsigned N = Clusters.size();
478 unsigned DstIndex = 0;
479 for (
unsigned SrcIndex = 0; SrcIndex <
N; ++SrcIndex) {
484 if (DstIndex != 0 && Clusters[DstIndex - 1].
MBB == Succ &&
485 (CaseVal->
getValue() - Clusters[DstIndex - 1].High->getValue()) == 1) {
488 Clusters[DstIndex - 1].High = CaseVal;
489 Clusters[DstIndex - 1].Prob +=
CC.Prob;
491 std::memmove(&Clusters[DstIndex++], &Clusters[SrcIndex],
492 sizeof(Clusters[SrcIndex]));
495 Clusters.resize(DstIndex);
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
const char LLVMTargetMachineRef TM
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file describes how to lower LLVM code to machine code.
Class for arbitrary precision integers.
unsigned getBitWidth() const
Return the number of bits in the APInt.
bool slt(const APInt &RHS) const
Signed less than comparison.
static APInt getZero(unsigned numBits)
Get the '0' value for the specified bit-width.
size_type count() const
count - Returns the number of bits which are set.
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
static BranchProbability getZero()
This is the shared class of boolean and integer constants.
const APInt & getValue() const
Return the constant as an APInt value reference.
void normalizeSuccProbs()
Normalize probabilities of all successors so that the sum of them becomes one.
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
MachineJumpTableInfo * getOrCreateJumpTableInfo(unsigned JTEntryKind)
getOrCreateJumpTableInfo - Get the JumpTableInfo for this function, if it does already exist,...
MachineBasicBlock * CreateMachineBasicBlock(const BasicBlock *BB=nullptr, std::optional< UniqueBBID > BBID=std::nullopt)
CreateMachineBasicBlock - Allocate a new MachineBasicBlock.
unsigned createJumpTableIndex(const std::vector< MachineBasicBlock * > &DestBBs)
createJumpTableIndex - Create a new jump table.
Analysis providing profile information.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
bool buildBitTests(CaseClusterVector &Clusters, unsigned First, unsigned Last, const SwitchInst *SI, CaseCluster &BTCluster)
Build a bit test cluster from Clusters[First..Last].
void findJumpTables(CaseClusterVector &Clusters, const SwitchInst *SI, std::optional< SDLoc > SL, MachineBasicBlock *DefaultMBB, ProfileSummaryInfo *PSI, BlockFrequencyInfo *BFI)
void findBitTestClusters(CaseClusterVector &Clusters, const SwitchInst *SI)
bool buildJumpTable(const CaseClusterVector &Clusters, unsigned First, unsigned Last, const SwitchInst *SI, const std::optional< SDLoc > &SL, MachineBasicBlock *DefaultMBB, CaseCluster &JTCluster)
virtual unsigned getMinimumJumpTableEntries() const
Return lower limit for number of blocks in a jump table.
virtual bool isSuitableForJumpTable(const SwitchInst *SI, uint64_t NumCases, uint64_t Range, ProfileSummaryInfo *PSI, BlockFrequencyInfo *BFI) const
Return true if lowering to a jump table is suitable for a set of case clusters which may contain NumC...
virtual bool areJTsAllowed(const Function *Fn) const
Return true if lowering to a jump table is allowed.
CodeGenOptLevel getOptLevel() const
Returns the optimization level: None, Less, Default, or Aggressive.
@ C
The default llvm calling convention, compatible with C.
@ SHL
Shift and rotation operations.
uint64_t getJumpTableNumCases(const SmallVectorImpl< unsigned > &TotalCases, unsigned First, unsigned Last)
Return the number of cases within a range.
std::vector< CaseCluster > CaseClusterVector
void sortAndRangeify(CaseClusterVector &Clusters)
Sort Clusters and merge adjacent cases.
uint64_t getJumpTableRange(const CaseClusterVector &Clusters, unsigned First, unsigned Last)
Return the range of values within a range.
std::vector< CaseBits > CaseBitsVector
@ CC_Range
A cluster of adjacent case labels with the same destination, or just one case.
@ CC_JumpTable
A cluster of cases suitable for jump table lowering.
This is an optimization pass for GlobalISel generic memory operations.
@ Low
Lower the current thread's priority such that it does not affect foreground tasks significantly.
void sort(IteratorTy Start, IteratorTy End)
@ First
Helpers to iterate all locations in the MemoryEffectsBase class.
constexpr unsigned BitWidth
TypeSize getSizeInBits() const
Return the size of the specified value type in bits.
BranchProbability ExtraProb
A cluster of case labels.
static CaseCluster jumpTable(const ConstantInt *Low, const ConstantInt *High, unsigned JTCasesIndex, BranchProbability Prob)
static CaseCluster bitTests(const ConstantInt *Low, const ConstantInt *High, unsigned BTCasesIndex, BranchProbability Prob)