/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/CodeGen/SwitchLoweringUtils.h
Line | Count | Source |
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 | | |
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" |
17 | | |
18 | | namespace llvm { |
19 | | |
20 | | class FunctionLoweringInfo; |
21 | | class MachineBasicBlock; |
22 | | |
23 | | namespace SwitchCG { |
24 | | |
25 | | enum CaseClusterKind { |
26 | | /// A cluster of adjacent case labels with the same destination, or just one |
27 | | /// case. |
28 | | CC_Range, |
29 | | /// A cluster of cases suitable for jump table lowering. |
30 | | CC_JumpTable, |
31 | | /// A cluster of cases suitable for bit test lowering. |
32 | | CC_BitTests |
33 | | }; |
34 | | |
35 | | /// A cluster of case labels. |
36 | | struct CaseCluster { |
37 | | CaseClusterKind Kind; |
38 | | const ConstantInt *Low, *High; |
39 | | union { |
40 | | MachineBasicBlock *MBB; |
41 | | unsigned JTCasesIndex; |
42 | | unsigned BTCasesIndex; |
43 | | }; |
44 | | BranchProbability Prob; |
45 | | |
46 | | static CaseCluster range(const ConstantInt *Low, const ConstantInt *High, |
47 | 74.8k | MachineBasicBlock *MBB, BranchProbability Prob) { |
48 | 74.8k | CaseCluster C; |
49 | 74.8k | C.Kind = CC_Range; |
50 | 74.8k | C.Low = Low; |
51 | 74.8k | C.High = High; |
52 | 74.8k | C.MBB = MBB; |
53 | 74.8k | C.Prob = Prob; |
54 | 74.8k | return C; |
55 | 74.8k | } |
56 | | |
57 | | static CaseCluster jumpTable(const ConstantInt *Low, const ConstantInt *High, |
58 | 4.53k | unsigned JTCasesIndex, BranchProbability Prob) { |
59 | 4.53k | CaseCluster C; |
60 | 4.53k | C.Kind = CC_JumpTable; |
61 | 4.53k | C.Low = Low; |
62 | 4.53k | C.High = High; |
63 | 4.53k | C.JTCasesIndex = JTCasesIndex; |
64 | 4.53k | C.Prob = Prob; |
65 | 4.53k | return C; |
66 | 4.53k | } |
67 | | |
68 | | static CaseCluster bitTests(const ConstantInt *Low, const ConstantInt *High, |
69 | 286 | unsigned BTCasesIndex, BranchProbability Prob) { |
70 | 286 | CaseCluster C; |
71 | 286 | C.Kind = CC_BitTests; |
72 | 286 | C.Low = Low; |
73 | 286 | C.High = High; |
74 | 286 | C.BTCasesIndex = BTCasesIndex; |
75 | 286 | C.Prob = Prob; |
76 | 286 | return C; |
77 | 286 | } |
78 | | }; |
79 | | |
80 | | using CaseClusterVector = std::vector<CaseCluster>; |
81 | | using CaseClusterIt = CaseClusterVector::iterator; |
82 | | |
83 | | /// Sort Clusters and merge adjacent cases. |
84 | | void sortAndRangeify(CaseClusterVector &Clusters); |
85 | | |
86 | | struct CaseBits { |
87 | | uint64_t Mask = 0; |
88 | | MachineBasicBlock *BB = nullptr; |
89 | | unsigned Bits = 0; |
90 | | BranchProbability ExtraProb; |
91 | | |
92 | | CaseBits() = default; |
93 | | CaseBits(uint64_t mask, MachineBasicBlock *bb, unsigned bits, |
94 | | BranchProbability Prob) |
95 | 447 | : Mask(mask), BB(bb), Bits(bits), ExtraProb(Prob) {} |
96 | | }; |
97 | | |
98 | | using CaseBitsVector = std::vector<CaseBits>; |
99 | | |
100 | | /// This structure is used to communicate between SelectionDAGBuilder and |
101 | | /// SDISel for the code generation of additional basic blocks needed by |
102 | | /// multi-case switch statements. |
103 | | struct CaseBlock { |
104 | | // For the GISel interface. |
105 | | struct PredInfoPair { |
106 | | CmpInst::Predicate Pred; |
107 | | // Set when no comparison should be emitted. |
108 | | bool NoCmp; |
109 | | }; |
110 | | union { |
111 | | // The condition code to use for the case block's setcc node. |
112 | | // Besides the integer condition codes, this can also be SETTRUE, in which |
113 | | // case no comparison gets emitted. |
114 | | ISD::CondCode CC; |
115 | | struct PredInfoPair PredInfo; |
116 | | }; |
117 | | |
118 | | // The LHS/MHS/RHS of the comparison to emit. |
119 | | // Emit by default LHS op RHS. MHS is used for range comparisons: |
120 | | // If MHS is not null: (LHS <= MHS) and (MHS <= RHS). |
121 | | const Value *CmpLHS, *CmpMHS, *CmpRHS; |
122 | | |
123 | | // The block to branch to if the setcc is true/false. |
124 | | MachineBasicBlock *TrueBB, *FalseBB; |
125 | | |
126 | | // The block into which to emit the code for the setcc and branches. |
127 | | MachineBasicBlock *ThisBB; |
128 | | |
129 | | /// The debug location of the instruction this CaseBlock was |
130 | | /// produced from. |
131 | | SDLoc DL; |
132 | | DebugLoc DbgLoc; |
133 | | |
134 | | // Branch weights. |
135 | | BranchProbability TrueProb, FalseProb; |
136 | | |
137 | | // Constructor for SelectionDAG. |
138 | | CaseBlock(ISD::CondCode cc, const Value *cmplhs, const Value *cmprhs, |
139 | | const Value *cmpmiddle, MachineBasicBlock *truebb, |
140 | | MachineBasicBlock *falsebb, MachineBasicBlock *me, SDLoc dl, |
141 | | BranchProbability trueprob = BranchProbability::getUnknown(), |
142 | | BranchProbability falseprob = BranchProbability::getUnknown()) |
143 | | : CC(cc), CmpLHS(cmplhs), CmpMHS(cmpmiddle), CmpRHS(cmprhs), |
144 | | TrueBB(truebb), FalseBB(falsebb), ThisBB(me), DL(dl), |
145 | 575k | TrueProb(trueprob), FalseProb(falseprob) {} |
146 | | |
147 | | // Constructor for GISel. |
148 | | CaseBlock(CmpInst::Predicate pred, bool nocmp, const Value *cmplhs, |
149 | | const Value *cmprhs, const Value *cmpmiddle, |
150 | | MachineBasicBlock *truebb, MachineBasicBlock *falsebb, |
151 | | MachineBasicBlock *me, DebugLoc dl, |
152 | | BranchProbability trueprob = BranchProbability::getUnknown(), |
153 | | BranchProbability falseprob = BranchProbability::getUnknown()) |
154 | | : PredInfo({pred, nocmp}), CmpLHS(cmplhs), CmpMHS(cmpmiddle), |
155 | | CmpRHS(cmprhs), TrueBB(truebb), FalseBB(falsebb), ThisBB(me), |
156 | 28.7k | DbgLoc(dl), TrueProb(trueprob), FalseProb(falseprob) {} |
157 | | }; |
158 | | |
159 | | struct JumpTable { |
160 | | /// The virtual register containing the index of the jump table entry |
161 | | /// to jump to. |
162 | | unsigned Reg; |
163 | | /// The JumpTableIndex for this jump table in the function. |
164 | | unsigned JTI; |
165 | | /// The MBB into which to emit the code for the indirect jump. |
166 | | MachineBasicBlock *MBB; |
167 | | /// The MBB of the default bb, which is a successor of the range |
168 | | /// check MBB. This is when updating PHI nodes in successors. |
169 | | MachineBasicBlock *Default; |
170 | | |
171 | | JumpTable(unsigned R, unsigned J, MachineBasicBlock *M, MachineBasicBlock *D) |
172 | 4.53k | : Reg(R), JTI(J), MBB(M), Default(D) {} |
173 | | }; |
174 | | struct JumpTableHeader { |
175 | | APInt First; |
176 | | APInt Last; |
177 | | const Value *SValue; |
178 | | MachineBasicBlock *HeaderBB; |
179 | | bool Emitted; |
180 | | bool OmitRangeCheck; |
181 | | |
182 | | JumpTableHeader(APInt F, APInt L, const Value *SV, MachineBasicBlock *H, |
183 | | bool E = false) |
184 | | : First(std::move(F)), Last(std::move(L)), SValue(SV), HeaderBB(H), |
185 | 4.53k | Emitted(E), OmitRangeCheck(false) {} |
186 | | }; |
187 | | using JumpTableBlock = std::pair<JumpTableHeader, JumpTable>; |
188 | | |
189 | | struct BitTestCase { |
190 | | uint64_t Mask; |
191 | | MachineBasicBlock *ThisBB; |
192 | | MachineBasicBlock *TargetBB; |
193 | | BranchProbability ExtraProb; |
194 | | |
195 | | BitTestCase(uint64_t M, MachineBasicBlock *T, MachineBasicBlock *Tr, |
196 | | BranchProbability Prob) |
197 | 447 | : Mask(M), ThisBB(T), TargetBB(Tr), ExtraProb(Prob) {} |
198 | | }; |
199 | | |
200 | | using BitTestInfo = SmallVector<BitTestCase, 3>; |
201 | | |
202 | | struct BitTestBlock { |
203 | | APInt First; |
204 | | APInt Range; |
205 | | const Value *SValue; |
206 | | unsigned Reg; |
207 | | MVT RegVT; |
208 | | bool Emitted; |
209 | | bool ContiguousRange; |
210 | | MachineBasicBlock *Parent; |
211 | | MachineBasicBlock *Default; |
212 | | BitTestInfo Cases; |
213 | | BranchProbability Prob; |
214 | | BranchProbability DefaultProb; |
215 | | |
216 | | BitTestBlock(APInt F, APInt R, const Value *SV, unsigned Rg, MVT RgVT, bool E, |
217 | | bool CR, MachineBasicBlock *P, MachineBasicBlock *D, |
218 | | BitTestInfo C, BranchProbability Pr) |
219 | | : First(std::move(F)), Range(std::move(R)), SValue(SV), Reg(Rg), |
220 | | RegVT(RgVT), Emitted(E), ContiguousRange(CR), Parent(P), Default(D), |
221 | 286 | Cases(std::move(C)), Prob(Pr) {} |
222 | | }; |
223 | | |
224 | | /// Return the range of value within a range. |
225 | | uint64_t getJumpTableRange(const CaseClusterVector &Clusters, unsigned First, |
226 | | unsigned Last); |
227 | | |
228 | | /// Return the number of cases within a range. |
229 | | uint64_t getJumpTableNumCases(const SmallVectorImpl<unsigned> &TotalCases, |
230 | | unsigned First, unsigned Last); |
231 | | |
232 | | struct SwitchWorkListItem { |
233 | | MachineBasicBlock *MBB; |
234 | | CaseClusterIt FirstCluster; |
235 | | CaseClusterIt LastCluster; |
236 | | const ConstantInt *GE; |
237 | | const ConstantInt *LT; |
238 | | BranchProbability DefaultProb; |
239 | | }; |
240 | | using SwitchWorkList = SmallVector<SwitchWorkListItem, 4>; |
241 | | |
242 | | class SwitchLowering { |
243 | | public: |
244 | 275k | SwitchLowering(FunctionLoweringInfo &funcinfo) : FuncInfo(funcinfo) {} |
245 | | |
246 | | void init(const TargetLowering &tli, const TargetMachine &tm, |
247 | 515k | const DataLayout &dl) { |
248 | 515k | TLI = &tli; |
249 | 515k | TM = &tm; |
250 | 515k | DL = &dl; |
251 | 515k | } |
252 | | |
253 | | /// Vector of CaseBlock structures used to communicate SwitchInst code |
254 | | /// generation information. |
255 | | std::vector<CaseBlock> SwitchCases; |
256 | | |
257 | | /// Vector of JumpTable structures used to communicate SwitchInst code |
258 | | /// generation information. |
259 | | std::vector<JumpTableBlock> JTCases; |
260 | | |
261 | | /// Vector of BitTestBlock structures used to communicate SwitchInst code |
262 | | /// generation information. |
263 | | std::vector<BitTestBlock> BitTestCases; |
264 | | |
265 | | void findJumpTables(CaseClusterVector &Clusters, const SwitchInst *SI, |
266 | | MachineBasicBlock *DefaultMBB); |
267 | | |
268 | | bool buildJumpTable(const CaseClusterVector &Clusters, unsigned First, |
269 | | unsigned Last, const SwitchInst *SI, |
270 | | MachineBasicBlock *DefaultMBB, CaseCluster &JTCluster); |
271 | | |
272 | | |
273 | | void findBitTestClusters(CaseClusterVector &Clusters, const SwitchInst *SI); |
274 | | |
275 | | /// Build a bit test cluster from Clusters[First..Last]. Returns false if it |
276 | | /// decides it's not a good idea. |
277 | | bool buildBitTests(CaseClusterVector &Clusters, unsigned First, unsigned Last, |
278 | | const SwitchInst *SI, CaseCluster &BTCluster); |
279 | | |
280 | | virtual void addSuccessorWithProb( |
281 | | MachineBasicBlock *Src, MachineBasicBlock *Dst, |
282 | | BranchProbability Prob = BranchProbability::getUnknown()) = 0; |
283 | | |
284 | 275k | virtual ~SwitchLowering() = default; |
285 | | |
286 | | private: |
287 | | const TargetLowering *TLI; |
288 | | const TargetMachine *TM; |
289 | | const DataLayout *DL; |
290 | | FunctionLoweringInfo &FuncInfo; |
291 | | }; |
292 | | |
293 | | } // namespace SwitchCG |
294 | | } // namespace llvm |
295 | | |
296 | | #endif // LLVM_CODEGEN_SWITCHLOWERINGUTILS_H |
297 | | |