LLVM 20.0.0git
SwitchLoweringUtils.h
Go to the documentation of this file.
1//===- SwitchLoweringUtils.h - Switch Lowering ------------------*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9#ifndef LLVM_CODEGEN_SWITCHLOWERINGUTILS_H
10#define LLVM_CODEGEN_SWITCHLOWERINGUTILS_H
11
15#include "llvm/IR/InstrTypes.h"
17#include <vector>
18
19namespace llvm {
20
21class BlockFrequencyInfo;
22class ConstantInt;
23class FunctionLoweringInfo;
24class MachineBasicBlock;
25class ProfileSummaryInfo;
26class TargetLowering;
27class TargetMachine;
28
29namespace SwitchCG {
30
32 /// A cluster of adjacent case labels with the same destination, or just one
33 /// case.
35 /// A cluster of cases suitable for jump table lowering.
37 /// A cluster of cases suitable for bit test lowering.
39};
40
41/// A cluster of case labels.
45 union {
47 unsigned JTCasesIndex;
48 unsigned BTCasesIndex;
49 };
51
55 C.Kind = CC_Range;
56 C.Low = Low;
57 C.High = High;
58 C.MBB = MBB;
59 C.Prob = Prob;
60 return C;
61 }
62
66 C.Kind = CC_JumpTable;
67 C.Low = Low;
68 C.High = High;
69 C.JTCasesIndex = JTCasesIndex;
70 C.Prob = Prob;
71 return C;
72 }
73
77 C.Kind = CC_BitTests;
78 C.Low = Low;
79 C.High = High;
80 C.BTCasesIndex = BTCasesIndex;
81 C.Prob = Prob;
82 return C;
83 }
84};
85
86using CaseClusterVector = std::vector<CaseCluster>;
87using CaseClusterIt = CaseClusterVector::iterator;
88
89/// Sort Clusters and merge adjacent cases.
91
92struct CaseBits {
95 unsigned Bits = 0;
97
98 CaseBits() = default;
99 CaseBits(uint64_t mask, MachineBasicBlock *bb, unsigned bits,
101 : Mask(mask), BB(bb), Bits(bits), ExtraProb(Prob) {}
102};
103
104using CaseBitsVector = std::vector<CaseBits>;
105
106/// This structure is used to communicate between SelectionDAGBuilder and
107/// SDISel for the code generation of additional basic blocks needed by
108/// multi-case switch statements.
109struct CaseBlock {
110 // For the GISel interface.
113 // Set when no comparison should be emitted.
114 bool NoCmp;
115 };
116 union {
117 // The condition code to use for the case block's setcc node.
118 // Besides the integer condition codes, this can also be SETTRUE, in which
119 // case no comparison gets emitted.
122 };
123
124 // The LHS/MHS/RHS of the comparison to emit.
125 // Emit by default LHS op RHS. MHS is used for range comparisons:
126 // If MHS is not null: (LHS <= MHS) and (MHS <= RHS).
128
129 // The block to branch to if the setcc is true/false.
131
132 // The block into which to emit the code for the setcc and branches.
134
135 /// The debug location of the instruction this CaseBlock was
136 /// produced from.
139
140 // Branch weights and predictability.
143
144 // Constructor for SelectionDAG.
145 CaseBlock(ISD::CondCode cc, const Value *cmplhs, const Value *cmprhs,
146 const Value *cmpmiddle, MachineBasicBlock *truebb,
147 MachineBasicBlock *falsebb, MachineBasicBlock *me, SDLoc dl,
150 bool isunpredictable = false)
151 : CC(cc), CmpLHS(cmplhs), CmpMHS(cmpmiddle), CmpRHS(cmprhs),
152 TrueBB(truebb), FalseBB(falsebb), ThisBB(me), DL(dl),
153 TrueProb(trueprob), FalseProb(falseprob),
154 IsUnpredictable(isunpredictable) {}
155
156 // Constructor for GISel.
157 CaseBlock(CmpInst::Predicate pred, bool nocmp, const Value *cmplhs,
158 const Value *cmprhs, const Value *cmpmiddle,
159 MachineBasicBlock *truebb, MachineBasicBlock *falsebb,
163 bool isunpredictable = false)
164 : PredInfo({pred, nocmp}), CmpLHS(cmplhs), CmpMHS(cmpmiddle),
165 CmpRHS(cmprhs), TrueBB(truebb), FalseBB(falsebb), ThisBB(me),
166 DbgLoc(dl), TrueProb(trueprob), FalseProb(falseprob),
167 IsUnpredictable(isunpredictable) {}
168};
169
170struct JumpTable {
171 /// The virtual register containing the index of the jump table entry
172 /// to jump to.
173 unsigned Reg;
174 /// The JumpTableIndex for this jump table in the function.
175 unsigned JTI;
176 /// The MBB into which to emit the code for the indirect jump.
178 /// The MBB of the default bb, which is a successor of the range
179 /// check MBB. This is when updating PHI nodes in successors.
181
182 /// The debug location of the instruction this JumpTable was produced from.
183 std::optional<SDLoc> SL; // For SelectionDAG
184
185 JumpTable(unsigned R, unsigned J, MachineBasicBlock *M, MachineBasicBlock *D,
186 std::optional<SDLoc> SL)
187 : Reg(R), JTI(J), MBB(M), Default(D), SL(SL) {}
188};
192 const Value *SValue;
196
198 bool E = false)
199 : First(std::move(F)), Last(std::move(L)), SValue(SV), HeaderBB(H),
200 Emitted(E) {}
201};
202using JumpTableBlock = std::pair<JumpTableHeader, JumpTable>;
203
209
212 : Mask(M), ThisBB(T), TargetBB(Tr), ExtraProb(Prob) {}
213};
214
216
220 const Value *SValue;
221 unsigned Reg;
231
232 BitTestBlock(APInt F, APInt R, const Value *SV, unsigned Rg, MVT RgVT, bool E,
235 : First(std::move(F)), Range(std::move(R)), SValue(SV), Reg(Rg),
236 RegVT(RgVT), Emitted(E), ContiguousRange(CR), Parent(P), Default(D),
237 Cases(std::move(C)), Prob(Pr) {}
238};
239
240/// Return the range of values within a range.
241uint64_t getJumpTableRange(const CaseClusterVector &Clusters, unsigned First,
242 unsigned Last);
243
244/// Return the number of cases within a range.
246 unsigned First, unsigned Last);
247
252 const ConstantInt *GE = nullptr;
253 const ConstantInt *LT = nullptr;
255};
257
259public:
260 SwitchLowering(FunctionLoweringInfo &funcinfo) : FuncInfo(funcinfo) {}
261
262 void init(const TargetLowering &tli, const TargetMachine &tm,
263 const DataLayout &dl) {
264 TLI = &tli;
265 TM = &tm;
266 DL = &dl;
267 }
268
269 /// Vector of CaseBlock structures used to communicate SwitchInst code
270 /// generation information.
271 std::vector<CaseBlock> SwitchCases;
272
273 /// Vector of JumpTable structures used to communicate SwitchInst code
274 /// generation information.
275 std::vector<JumpTableBlock> JTCases;
276
277 /// Vector of BitTestBlock structures used to communicate SwitchInst code
278 /// generation information.
279 std::vector<BitTestBlock> BitTestCases;
280
281 void findJumpTables(CaseClusterVector &Clusters, const SwitchInst *SI,
282 std::optional<SDLoc> SL, MachineBasicBlock *DefaultMBB,
284
285 bool buildJumpTable(const CaseClusterVector &Clusters, unsigned First,
286 unsigned Last, const SwitchInst *SI,
287 const std::optional<SDLoc> &SL,
288 MachineBasicBlock *DefaultMBB, CaseCluster &JTCluster);
289
290 void findBitTestClusters(CaseClusterVector &Clusters, const SwitchInst *SI);
291
292 /// Build a bit test cluster from Clusters[First..Last]. Returns false if it
293 /// decides it's not a good idea.
294 bool buildBitTests(CaseClusterVector &Clusters, unsigned First, unsigned Last,
295 const SwitchInst *SI, CaseCluster &BTCluster);
296
300
301 /// Determine the rank by weight of CC in [First,Last]. If CC has more weight
302 /// than each cluster in the range, its rank is 0.
305
311 };
312 /// Compute information to balance the tree based on branch probabilities to
313 /// create a near-optimal (in terms of search time given key frequency) binary
314 /// search tree. See e.g. Kurt Mehlhorn "Nearly Optimal Binary Search Trees"
315 /// (1975).
317 virtual ~SwitchLowering() = default;
318
319private:
320 const TargetLowering *TLI = nullptr;
321 const TargetMachine *TM = nullptr;
322 const DataLayout *DL = nullptr;
323 FunctionLoweringInfo &FuncInfo;
324};
325
326} // namespace SwitchCG
327} // namespace llvm
328
329#endif // LLVM_CODEGEN_SWITCHLOWERINGUTILS_H
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
hexagon gen pred
#define F(x, y, z)
Definition: MD5.cpp:55
#define H(x, y, z)
Definition: MD5.cpp:57
#define P(N)
This file defines the SmallVector class.
Class for arbitrary precision integers.
Definition: APInt.h:78
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
static BranchProbability getUnknown()
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:757
This is the shared class of boolean and integer constants.
Definition: Constants.h:81
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:63
A debug info location.
Definition: DebugLoc.h:33
FunctionLoweringInfo - This contains information that is global to a function that is used when lower...
Machine Value Type.
Analysis providing profile information.
Wrapper class for IR location info (IR ordering and DebugLoc) to be passed into SDNode creation funct...
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:586
virtual ~SwitchLowering()=default
bool buildBitTests(CaseClusterVector &Clusters, unsigned First, unsigned Last, const SwitchInst *SI, CaseCluster &BTCluster)
Build a bit test cluster from Clusters[First..Last].
std::vector< CaseBlock > SwitchCases
Vector of CaseBlock structures used to communicate SwitchInst code generation information.
unsigned caseClusterRank(const CaseCluster &CC, CaseClusterIt First, CaseClusterIt Last)
Determine the rank by weight of CC in [First,Last].
void findJumpTables(CaseClusterVector &Clusters, const SwitchInst *SI, std::optional< SDLoc > SL, MachineBasicBlock *DefaultMBB, ProfileSummaryInfo *PSI, BlockFrequencyInfo *BFI)
virtual void addSuccessorWithProb(MachineBasicBlock *Src, MachineBasicBlock *Dst, BranchProbability Prob=BranchProbability::getUnknown())=0
void findBitTestClusters(CaseClusterVector &Clusters, const SwitchInst *SI)
std::vector< BitTestBlock > BitTestCases
Vector of BitTestBlock structures used to communicate SwitchInst code generation information.
void init(const TargetLowering &tli, const TargetMachine &tm, const DataLayout &dl)
SplitWorkItemInfo computeSplitWorkItemInfo(const SwitchWorkListItem &W)
Compute information to balance the tree based on branch probabilities to create a near-optimal (in te...
bool buildJumpTable(const CaseClusterVector &Clusters, unsigned First, unsigned Last, const SwitchInst *SI, const std::optional< SDLoc > &SL, MachineBasicBlock *DefaultMBB, CaseCluster &JTCluster)
SwitchLowering(FunctionLoweringInfo &funcinfo)
std::vector< JumpTableBlock > JTCases
Vector of JumpTable structures used to communicate SwitchInst code generation information.
Multiway switch.
This class defines information used to lower LLVM code to legal SelectionDAG operators that the targe...
Primary interface to the complete machine description for the target machine.
Definition: TargetMachine.h:77
LLVM Value Representation.
Definition: Value.h:74
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
CondCode
ISD::CondCode enum - These are ordered carefully to make the bitfields below work out,...
Definition: ISDOpcodes.h:1603
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.
CaseClusterVector::iterator CaseClusterIt
uint64_t getJumpTableRange(const CaseClusterVector &Clusters, unsigned First, unsigned Last)
Return the range of values within a range.
std::pair< JumpTableHeader, JumpTable > JumpTableBlock
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.
@ CC_BitTests
A cluster of cases suitable for bit test lowering.
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
@ First
Helpers to iterate all locations in the MemoryEffectsBase class.
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1856
Implement std::hash so that hash_code can be used in STL containers.
Definition: BitVector.h:858
BitTestBlock(APInt F, APInt R, const Value *SV, unsigned Rg, MVT RgVT, bool E, bool CR, MachineBasicBlock *P, MachineBasicBlock *D, BitTestInfo C, BranchProbability Pr)
BitTestCase(uint64_t M, MachineBasicBlock *T, MachineBasicBlock *Tr, BranchProbability Prob)
CaseBits(uint64_t mask, MachineBasicBlock *bb, unsigned bits, BranchProbability Prob)
This structure is used to communicate between SelectionDAGBuilder and SDISel for the code generation ...
struct PredInfoPair PredInfo
CaseBlock(ISD::CondCode cc, const Value *cmplhs, const Value *cmprhs, const Value *cmpmiddle, MachineBasicBlock *truebb, MachineBasicBlock *falsebb, MachineBasicBlock *me, SDLoc dl, BranchProbability trueprob=BranchProbability::getUnknown(), BranchProbability falseprob=BranchProbability::getUnknown(), bool isunpredictable=false)
SDLoc DL
The debug location of the instruction this CaseBlock was produced from.
CaseBlock(CmpInst::Predicate pred, bool nocmp, const Value *cmplhs, const Value *cmprhs, const Value *cmpmiddle, MachineBasicBlock *truebb, MachineBasicBlock *falsebb, MachineBasicBlock *me, DebugLoc dl, BranchProbability trueprob=BranchProbability::getUnknown(), BranchProbability falseprob=BranchProbability::getUnknown(), bool isunpredictable=false)
A cluster of case labels.
static CaseCluster range(const ConstantInt *Low, const ConstantInt *High, MachineBasicBlock *MBB, BranchProbability Prob)
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)
JumpTableHeader(APInt F, APInt L, const Value *SV, MachineBasicBlock *H, bool E=false)
MachineBasicBlock * Default
The MBB of the default bb, which is a successor of the range check MBB.
unsigned Reg
The virtual register containing the index of the jump table entry to jump to.
unsigned JTI
The JumpTableIndex for this jump table in the function.
MachineBasicBlock * MBB
The MBB into which to emit the code for the indirect jump.
JumpTable(unsigned R, unsigned J, MachineBasicBlock *M, MachineBasicBlock *D, std::optional< SDLoc > SL)
std::optional< SDLoc > SL
The debug location of the instruction this JumpTable was produced from.