LLVM 18.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 JumpTable(unsigned R, unsigned J, MachineBasicBlock *M, MachineBasicBlock *D)
178 : Reg(R), JTI(J), MBB(M), Default(D) {}
179};
183 const Value *SValue;
187
189 bool E = false)
190 : First(std::move(F)), Last(std::move(L)), SValue(SV), HeaderBB(H),
191 Emitted(E) {}
192};
193using JumpTableBlock = std::pair<JumpTableHeader, JumpTable>;
194
200
203 : Mask(M), ThisBB(T), TargetBB(Tr), ExtraProb(Prob) {}
204};
205
207
211 const Value *SValue;
212 unsigned Reg;
222
223 BitTestBlock(APInt F, APInt R, const Value *SV, unsigned Rg, MVT RgVT, bool E,
226 : First(std::move(F)), Range(std::move(R)), SValue(SV), Reg(Rg),
227 RegVT(RgVT), Emitted(E), ContiguousRange(CR), Parent(P), Default(D),
228 Cases(std::move(C)), Prob(Pr) {}
229};
230
231/// Return the range of values within a range.
232uint64_t getJumpTableRange(const CaseClusterVector &Clusters, unsigned First,
233 unsigned Last);
234
235/// Return the number of cases within a range.
237 unsigned First, unsigned Last);
238
243 const ConstantInt *GE = nullptr;
244 const ConstantInt *LT = nullptr;
246};
248
250public:
251 SwitchLowering(FunctionLoweringInfo &funcinfo) : FuncInfo(funcinfo) {}
252
253 void init(const TargetLowering &tli, const TargetMachine &tm,
254 const DataLayout &dl) {
255 TLI = &tli;
256 TM = &tm;
257 DL = &dl;
258 }
259
260 /// Vector of CaseBlock structures used to communicate SwitchInst code
261 /// generation information.
262 std::vector<CaseBlock> SwitchCases;
263
264 /// Vector of JumpTable structures used to communicate SwitchInst code
265 /// generation information.
266 std::vector<JumpTableBlock> JTCases;
267
268 /// Vector of BitTestBlock structures used to communicate SwitchInst code
269 /// generation information.
270 std::vector<BitTestBlock> BitTestCases;
271
272 void findJumpTables(CaseClusterVector &Clusters, const SwitchInst *SI,
273 MachineBasicBlock *DefaultMBB,
275
276 bool buildJumpTable(const CaseClusterVector &Clusters, unsigned First,
277 unsigned Last, const SwitchInst *SI,
278 MachineBasicBlock *DefaultMBB, CaseCluster &JTCluster);
279
280
281 void findBitTestClusters(CaseClusterVector &Clusters, const SwitchInst *SI);
282
283 /// Build a bit test cluster from Clusters[First..Last]. Returns false if it
284 /// decides it's not a good idea.
285 bool buildBitTests(CaseClusterVector &Clusters, unsigned First, unsigned Last,
286 const SwitchInst *SI, CaseCluster &BTCluster);
287
291
292 virtual ~SwitchLowering() = default;
293
294private:
295 const TargetLowering *TLI = nullptr;
296 const TargetMachine *TM = nullptr;
297 const DataLayout *DL = nullptr;
298 FunctionLoweringInfo &FuncInfo;
299};
300
301} // namespace SwitchCG
302} // namespace llvm
303
304#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:711
This is the shared class of boolean and integer constants.
Definition: Constants.h:78
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:577
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.
bool buildJumpTable(const CaseClusterVector &Clusters, unsigned First, unsigned Last, const SwitchInst *SI, MachineBasicBlock *DefaultMBB, CaseCluster &JTCluster)
void findJumpTables(CaseClusterVector &Clusters, const SwitchInst *SI, 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)
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:78
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:1503
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:1854
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)