LLVM 19.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.
142
143 // Constructor for SelectionDAG.
144 CaseBlock(ISD::CondCode cc, const Value *cmplhs, const Value *cmprhs,
145 const Value *cmpmiddle, MachineBasicBlock *truebb,
146 MachineBasicBlock *falsebb, MachineBasicBlock *me, SDLoc dl,
149 : CC(cc), CmpLHS(cmplhs), CmpMHS(cmpmiddle), CmpRHS(cmprhs),
150 TrueBB(truebb), FalseBB(falsebb), ThisBB(me), DL(dl),
151 TrueProb(trueprob), FalseProb(falseprob) {}
152
153 // Constructor for GISel.
154 CaseBlock(CmpInst::Predicate pred, bool nocmp, const Value *cmplhs,
155 const Value *cmprhs, const Value *cmpmiddle,
156 MachineBasicBlock *truebb, MachineBasicBlock *falsebb,
160 : PredInfo({pred, nocmp}), CmpLHS(cmplhs), CmpMHS(cmpmiddle),
161 CmpRHS(cmprhs), TrueBB(truebb), FalseBB(falsebb), ThisBB(me),
162 DbgLoc(dl), TrueProb(trueprob), FalseProb(falseprob) {}
163};
164
165struct JumpTable {
166 /// The virtual register containing the index of the jump table entry
167 /// to jump to.
168 unsigned Reg;
169 /// The JumpTableIndex for this jump table in the function.
170 unsigned JTI;
171 /// The MBB into which to emit the code for the indirect jump.
173 /// The MBB of the default bb, which is a successor of the range
174 /// check MBB. This is when updating PHI nodes in successors.
176
177 /// The debug location of the instruction this JumpTable was produced from.
178 std::optional<SDLoc> SL; // For SelectionDAG
179
180 JumpTable(unsigned R, unsigned J, MachineBasicBlock *M, MachineBasicBlock *D,
181 std::optional<SDLoc> SL)
182 : Reg(R), JTI(J), MBB(M), Default(D), SL(SL) {}
183};
187 const Value *SValue;
191
193 bool E = false)
194 : First(std::move(F)), Last(std::move(L)), SValue(SV), HeaderBB(H),
195 Emitted(E) {}
196};
197using JumpTableBlock = std::pair<JumpTableHeader, JumpTable>;
198
204
207 : Mask(M), ThisBB(T), TargetBB(Tr), ExtraProb(Prob) {}
208};
209
211
215 const Value *SValue;
216 unsigned Reg;
226
227 BitTestBlock(APInt F, APInt R, const Value *SV, unsigned Rg, MVT RgVT, bool E,
230 : First(std::move(F)), Range(std::move(R)), SValue(SV), Reg(Rg),
231 RegVT(RgVT), Emitted(E), ContiguousRange(CR), Parent(P), Default(D),
232 Cases(std::move(C)), Prob(Pr) {}
233};
234
235/// Return the range of values within a range.
236uint64_t getJumpTableRange(const CaseClusterVector &Clusters, unsigned First,
237 unsigned Last);
238
239/// Return the number of cases within a range.
241 unsigned First, unsigned Last);
242
247 const ConstantInt *GE = nullptr;
248 const ConstantInt *LT = nullptr;
250};
252
254public:
255 SwitchLowering(FunctionLoweringInfo &funcinfo) : FuncInfo(funcinfo) {}
256
257 void init(const TargetLowering &tli, const TargetMachine &tm,
258 const DataLayout &dl) {
259 TLI = &tli;
260 TM = &tm;
261 DL = &dl;
262 }
263
264 /// Vector of CaseBlock structures used to communicate SwitchInst code
265 /// generation information.
266 std::vector<CaseBlock> SwitchCases;
267
268 /// Vector of JumpTable structures used to communicate SwitchInst code
269 /// generation information.
270 std::vector<JumpTableBlock> JTCases;
271
272 /// Vector of BitTestBlock structures used to communicate SwitchInst code
273 /// generation information.
274 std::vector<BitTestBlock> BitTestCases;
275
276 void findJumpTables(CaseClusterVector &Clusters, const SwitchInst *SI,
277 std::optional<SDLoc> SL, MachineBasicBlock *DefaultMBB,
279
280 bool buildJumpTable(const CaseClusterVector &Clusters, unsigned First,
281 unsigned Last, const SwitchInst *SI,
282 const std::optional<SDLoc> &SL,
283 MachineBasicBlock *DefaultMBB, CaseCluster &JTCluster);
284
285 void findBitTestClusters(CaseClusterVector &Clusters, const SwitchInst *SI);
286
287 /// Build a bit test cluster from Clusters[First..Last]. Returns false if it
288 /// decides it's not a good idea.
289 bool buildBitTests(CaseClusterVector &Clusters, unsigned First, unsigned Last,
290 const SwitchInst *SI, CaseCluster &BTCluster);
291
295
296 /// Determine the rank by weight of CC in [First,Last]. If CC has more weight
297 /// than each cluster in the range, its rank is 0.
300
306 };
307 /// Compute information to balance the tree based on branch probabilities to
308 /// create a near-optimal (in terms of search time given key frequency) binary
309 /// search tree. See e.g. Kurt Mehlhorn "Nearly Optimal Binary Search Trees"
310 /// (1975).
312 virtual ~SwitchLowering() = default;
313
314private:
315 const TargetLowering *TLI = nullptr;
316 const TargetMachine *TM = nullptr;
317 const DataLayout *DL = nullptr;
318 FunctionLoweringInfo &FuncInfo;
319};
320
321} // namespace SwitchCG
322} // namespace llvm
323
324#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:76
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:960
This is the shared class of boolean and integer constants.
Definition: Constants.h:80
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:110
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:76
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:1523
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:1858
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 ...
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())
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())
SDLoc DL
The debug location of the instruction this CaseBlock was produced from.
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.