1 //===- SwitchLoweringUtils.h - Switch Lowering ------------------*- C++ -*-===//
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
7 //===----------------------------------------------------------------------===//
9 #ifndef LLVM_CODEGEN_SWITCHLOWERINGUTILS_H
10 #define LLVM_CODEGEN_SWITCHLOWERINGUTILS_H
12 #include "llvm/ADT/SmallVector.h"
13 #include "llvm/CodeGen/SelectionDAGNodes.h"
14 #include "llvm/CodeGen/TargetLowering.h"
15 #include "llvm/IR/Constants.h"
16 #include "llvm/Support/BranchProbability.h"
20 class FunctionLoweringInfo;
21 class MachineBasicBlock;
22 class BlockFrequencyInfo;
26 enum CaseClusterKind {
27 /// A cluster of adjacent case labels with the same destination, or just one
30 /// A cluster of cases suitable for jump table lowering.
32 /// A cluster of cases suitable for bit test lowering.
36 /// A cluster of case labels.
39 const ConstantInt *Low, *High;
41 MachineBasicBlock *MBB;
42 unsigned JTCasesIndex;
43 unsigned BTCasesIndex;
45 BranchProbability Prob;
47 static CaseCluster range(const ConstantInt *Low, const ConstantInt *High,
48 MachineBasicBlock *MBB, BranchProbability Prob) {
58 static CaseCluster jumpTable(const ConstantInt *Low, const ConstantInt *High,
59 unsigned JTCasesIndex, BranchProbability Prob) {
61 C.Kind = CC_JumpTable;
64 C.JTCasesIndex = JTCasesIndex;
69 static CaseCluster bitTests(const ConstantInt *Low, const ConstantInt *High,
70 unsigned BTCasesIndex, BranchProbability Prob) {
75 C.BTCasesIndex = BTCasesIndex;
81 using CaseClusterVector = std::vector<CaseCluster>;
82 using CaseClusterIt = CaseClusterVector::iterator;
84 /// Sort Clusters and merge adjacent cases.
85 void sortAndRangeify(CaseClusterVector &Clusters);
89 MachineBasicBlock *BB = nullptr;
91 BranchProbability ExtraProb;
94 CaseBits(uint64_t mask, MachineBasicBlock *bb, unsigned bits,
95 BranchProbability Prob)
96 : Mask(mask), BB(bb), Bits(bits), ExtraProb(Prob) {}
99 using CaseBitsVector = std::vector<CaseBits>;
101 /// This structure is used to communicate between SelectionDAGBuilder and
102 /// SDISel for the code generation of additional basic blocks needed by
103 /// multi-case switch statements.
105 // For the GISel interface.
106 struct PredInfoPair {
107 CmpInst::Predicate Pred;
108 // Set when no comparison should be emitted.
112 // The condition code to use for the case block's setcc node.
113 // Besides the integer condition codes, this can also be SETTRUE, in which
114 // case no comparison gets emitted.
116 struct PredInfoPair PredInfo;
119 // The LHS/MHS/RHS of the comparison to emit.
120 // Emit by default LHS op RHS. MHS is used for range comparisons:
121 // If MHS is not null: (LHS <= MHS) and (MHS <= RHS).
122 const Value *CmpLHS, *CmpMHS, *CmpRHS;
124 // The block to branch to if the setcc is true/false.
125 MachineBasicBlock *TrueBB, *FalseBB;
127 // The block into which to emit the code for the setcc and branches.
128 MachineBasicBlock *ThisBB;
130 /// The debug location of the instruction this CaseBlock was
136 BranchProbability TrueProb, FalseProb;
138 // Constructor for SelectionDAG.
139 CaseBlock(ISD::CondCode cc, const Value *cmplhs, const Value *cmprhs,
140 const Value *cmpmiddle, MachineBasicBlock *truebb,
141 MachineBasicBlock *falsebb, MachineBasicBlock *me, SDLoc dl,
142 BranchProbability trueprob = BranchProbability::getUnknown(),
143 BranchProbability falseprob = BranchProbability::getUnknown())
144 : CC(cc), CmpLHS(cmplhs), CmpMHS(cmpmiddle), CmpRHS(cmprhs),
145 TrueBB(truebb), FalseBB(falsebb), ThisBB(me), DL(dl),
146 TrueProb(trueprob), FalseProb(falseprob) {}
148 // Constructor for GISel.
149 CaseBlock(CmpInst::Predicate pred, bool nocmp, const Value *cmplhs,
150 const Value *cmprhs, const Value *cmpmiddle,
151 MachineBasicBlock *truebb, MachineBasicBlock *falsebb,
152 MachineBasicBlock *me, DebugLoc dl,
153 BranchProbability trueprob = BranchProbability::getUnknown(),
154 BranchProbability falseprob = BranchProbability::getUnknown())
155 : PredInfo({pred, nocmp}), CmpLHS(cmplhs), CmpMHS(cmpmiddle),
156 CmpRHS(cmprhs), TrueBB(truebb), FalseBB(falsebb), ThisBB(me),
157 DbgLoc(dl), TrueProb(trueprob), FalseProb(falseprob) {}
161 /// The virtual register containing the index of the jump table entry
164 /// The JumpTableIndex for this jump table in the function.
166 /// The MBB into which to emit the code for the indirect jump.
167 MachineBasicBlock *MBB;
168 /// The MBB of the default bb, which is a successor of the range
169 /// check MBB. This is when updating PHI nodes in successors.
170 MachineBasicBlock *Default;
172 JumpTable(unsigned R, unsigned J, MachineBasicBlock *M, MachineBasicBlock *D)
173 : Reg(R), JTI(J), MBB(M), Default(D) {}
175 struct JumpTableHeader {
179 MachineBasicBlock *HeaderBB;
183 JumpTableHeader(APInt F, APInt L, const Value *SV, MachineBasicBlock *H,
185 : First(std::move(F)), Last(std::move(L)), SValue(SV), HeaderBB(H),
186 Emitted(E), OmitRangeCheck(false) {}
188 using JumpTableBlock = std::pair<JumpTableHeader, JumpTable>;
192 MachineBasicBlock *ThisBB;
193 MachineBasicBlock *TargetBB;
194 BranchProbability ExtraProb;
196 BitTestCase(uint64_t M, MachineBasicBlock *T, MachineBasicBlock *Tr,
197 BranchProbability Prob)
198 : Mask(M), ThisBB(T), TargetBB(Tr), ExtraProb(Prob) {}
201 using BitTestInfo = SmallVector<BitTestCase, 3>;
203 struct BitTestBlock {
210 bool ContiguousRange;
211 MachineBasicBlock *Parent;
212 MachineBasicBlock *Default;
214 BranchProbability Prob;
215 BranchProbability DefaultProb;
218 BitTestBlock(APInt F, APInt R, const Value *SV, unsigned Rg, MVT RgVT, bool E,
219 bool CR, MachineBasicBlock *P, MachineBasicBlock *D,
220 BitTestInfo C, BranchProbability Pr)
221 : First(std::move(F)), Range(std::move(R)), SValue(SV), Reg(Rg),
222 RegVT(RgVT), Emitted(E), ContiguousRange(CR), Parent(P), Default(D),
223 Cases(std::move(C)), Prob(Pr), OmitRangeCheck(false) {}
226 /// Return the range of values within a range.
227 uint64_t getJumpTableRange(const CaseClusterVector &Clusters, unsigned First,
230 /// Return the number of cases within a range.
231 uint64_t getJumpTableNumCases(const SmallVectorImpl<unsigned> &TotalCases,
232 unsigned First, unsigned Last);
234 struct SwitchWorkListItem {
235 MachineBasicBlock *MBB;
236 CaseClusterIt FirstCluster;
237 CaseClusterIt LastCluster;
238 const ConstantInt *GE;
239 const ConstantInt *LT;
240 BranchProbability DefaultProb;
242 using SwitchWorkList = SmallVector<SwitchWorkListItem, 4>;
244 class SwitchLowering {
246 SwitchLowering(FunctionLoweringInfo &funcinfo) : FuncInfo(funcinfo) {}
248 void init(const TargetLowering &tli, const TargetMachine &tm,
249 const DataLayout &dl) {
255 /// Vector of CaseBlock structures used to communicate SwitchInst code
256 /// generation information.
257 std::vector<CaseBlock> SwitchCases;
259 /// Vector of JumpTable structures used to communicate SwitchInst code
260 /// generation information.
261 std::vector<JumpTableBlock> JTCases;
263 /// Vector of BitTestBlock structures used to communicate SwitchInst code
264 /// generation information.
265 std::vector<BitTestBlock> BitTestCases;
267 void findJumpTables(CaseClusterVector &Clusters, const SwitchInst *SI,
268 MachineBasicBlock *DefaultMBB,
269 ProfileSummaryInfo *PSI, BlockFrequencyInfo *BFI);
271 bool buildJumpTable(const CaseClusterVector &Clusters, unsigned First,
272 unsigned Last, const SwitchInst *SI,
273 MachineBasicBlock *DefaultMBB, CaseCluster &JTCluster);
276 void findBitTestClusters(CaseClusterVector &Clusters, const SwitchInst *SI);
278 /// Build a bit test cluster from Clusters[First..Last]. Returns false if it
279 /// decides it's not a good idea.
280 bool buildBitTests(CaseClusterVector &Clusters, unsigned First, unsigned Last,
281 const SwitchInst *SI, CaseCluster &BTCluster);
283 virtual void addSuccessorWithProb(
284 MachineBasicBlock *Src, MachineBasicBlock *Dst,
285 BranchProbability Prob = BranchProbability::getUnknown()) = 0;
287 virtual ~SwitchLowering() = default;
290 const TargetLowering *TLI;
291 const TargetMachine *TM;
292 const DataLayout *DL;
293 FunctionLoweringInfo &FuncInfo;
296 } // namespace SwitchCG
299 #endif // LLVM_CODEGEN_SWITCHLOWERINGUTILS_H