File: | llvm/lib/Target/Hexagon/HexagonEarlyIfConv.cpp |
Warning: | line 285, column 18 Called C++ object pointer is null |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
1 | //===- HexagonEarlyIfConv.cpp ---------------------------------------------===// | ||||||
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 | // This implements a Hexagon-specific if-conversion pass that runs on the | ||||||
10 | // SSA form. | ||||||
11 | // In SSA it is not straightforward to represent instructions that condi- | ||||||
12 | // tionally define registers, since a conditionally-defined register may | ||||||
13 | // only be used under the same condition on which the definition was based. | ||||||
14 | // To avoid complications of this nature, this patch will only generate | ||||||
15 | // predicated stores, and speculate other instructions from the "if-conver- | ||||||
16 | // ted" block. | ||||||
17 | // The code will recognize CFG patterns where a block with a conditional | ||||||
18 | // branch "splits" into a "true block" and a "false block". Either of these | ||||||
19 | // could be omitted (in case of a triangle, for example). | ||||||
20 | // If after conversion of the side block(s) the CFG allows it, the resul- | ||||||
21 | // ting blocks may be merged. If the "join" block contained PHI nodes, they | ||||||
22 | // will be replaced with MUX (or MUX-like) instructions to maintain the | ||||||
23 | // semantics of the PHI. | ||||||
24 | // | ||||||
25 | // Example: | ||||||
26 | // | ||||||
27 | // %40 = L2_loadrub_io killed %39, 1 | ||||||
28 | // %41 = S2_tstbit_i killed %40, 0 | ||||||
29 | // J2_jumpt killed %41, <%bb.5>, implicit dead %pc | ||||||
30 | // J2_jump <%bb.4>, implicit dead %pc | ||||||
31 | // Successors according to CFG: %bb.4(62) %bb.5(62) | ||||||
32 | // | ||||||
33 | // %bb.4: derived from LLVM BB %if.then | ||||||
34 | // Predecessors according to CFG: %bb.3 | ||||||
35 | // %11 = A2_addp %6, %10 | ||||||
36 | // S2_storerd_io %32, 16, %11 | ||||||
37 | // Successors according to CFG: %bb.5 | ||||||
38 | // | ||||||
39 | // %bb.5: derived from LLVM BB %if.end | ||||||
40 | // Predecessors according to CFG: %bb.3 %bb.4 | ||||||
41 | // %12 = PHI %6, <%bb.3>, %11, <%bb.4> | ||||||
42 | // %13 = A2_addp %7, %12 | ||||||
43 | // %42 = C2_cmpeqi %9, 10 | ||||||
44 | // J2_jumpf killed %42, <%bb.3>, implicit dead %pc | ||||||
45 | // J2_jump <%bb.6>, implicit dead %pc | ||||||
46 | // Successors according to CFG: %bb.6(4) %bb.3(124) | ||||||
47 | // | ||||||
48 | // would become: | ||||||
49 | // | ||||||
50 | // %40 = L2_loadrub_io killed %39, 1 | ||||||
51 | // %41 = S2_tstbit_i killed %40, 0 | ||||||
52 | // spec-> %11 = A2_addp %6, %10 | ||||||
53 | // pred-> S2_pstorerdf_io %41, %32, 16, %11 | ||||||
54 | // %46 = PS_pselect %41, %6, %11 | ||||||
55 | // %13 = A2_addp %7, %46 | ||||||
56 | // %42 = C2_cmpeqi %9, 10 | ||||||
57 | // J2_jumpf killed %42, <%bb.3>, implicit dead %pc | ||||||
58 | // J2_jump <%bb.6>, implicit dead %pc | ||||||
59 | // Successors according to CFG: %bb.6 %bb.3 | ||||||
60 | |||||||
61 | #include "Hexagon.h" | ||||||
62 | #include "HexagonInstrInfo.h" | ||||||
63 | #include "HexagonSubtarget.h" | ||||||
64 | #include "llvm/ADT/DenseSet.h" | ||||||
65 | #include "llvm/ADT/SmallVector.h" | ||||||
66 | #include "llvm/ADT/StringRef.h" | ||||||
67 | #include "llvm/ADT/iterator_range.h" | ||||||
68 | #include "llvm/CodeGen/MachineBasicBlock.h" | ||||||
69 | #include "llvm/CodeGen/MachineBranchProbabilityInfo.h" | ||||||
70 | #include "llvm/CodeGen/MachineDominators.h" | ||||||
71 | #include "llvm/CodeGen/MachineFunction.h" | ||||||
72 | #include "llvm/CodeGen/MachineFunctionPass.h" | ||||||
73 | #include "llvm/CodeGen/MachineInstr.h" | ||||||
74 | #include "llvm/CodeGen/MachineInstrBuilder.h" | ||||||
75 | #include "llvm/CodeGen/MachineLoopInfo.h" | ||||||
76 | #include "llvm/CodeGen/MachineOperand.h" | ||||||
77 | #include "llvm/CodeGen/MachineRegisterInfo.h" | ||||||
78 | #include "llvm/CodeGen/TargetRegisterInfo.h" | ||||||
79 | #include "llvm/IR/DebugLoc.h" | ||||||
80 | #include "llvm/Pass.h" | ||||||
81 | #include "llvm/Support/BranchProbability.h" | ||||||
82 | #include "llvm/Support/CommandLine.h" | ||||||
83 | #include "llvm/Support/Compiler.h" | ||||||
84 | #include "llvm/Support/Debug.h" | ||||||
85 | #include "llvm/Support/ErrorHandling.h" | ||||||
86 | #include "llvm/Support/raw_ostream.h" | ||||||
87 | #include <cassert> | ||||||
88 | #include <iterator> | ||||||
89 | |||||||
90 | #define DEBUG_TYPE"hexagon-eif" "hexagon-eif" | ||||||
91 | |||||||
92 | using namespace llvm; | ||||||
93 | |||||||
94 | namespace llvm { | ||||||
95 | |||||||
96 | FunctionPass *createHexagonEarlyIfConversion(); | ||||||
97 | void initializeHexagonEarlyIfConversionPass(PassRegistry& Registry); | ||||||
98 | |||||||
99 | } // end namespace llvm | ||||||
100 | |||||||
101 | static cl::opt<bool> EnableHexagonBP("enable-hexagon-br-prob", cl::Hidden, | ||||||
102 | cl::init(true), cl::desc("Enable branch probability info")); | ||||||
103 | static cl::opt<unsigned> SizeLimit("eif-limit", cl::init(6), cl::Hidden, | ||||||
104 | cl::desc("Size limit in Hexagon early if-conversion")); | ||||||
105 | static cl::opt<bool> SkipExitBranches("eif-no-loop-exit", cl::init(false), | ||||||
106 | cl::Hidden, cl::desc("Do not convert branches that may exit the loop")); | ||||||
107 | |||||||
108 | namespace { | ||||||
109 | |||||||
110 | struct PrintMB { | ||||||
111 | PrintMB(const MachineBasicBlock *B) : MB(B) {} | ||||||
112 | |||||||
113 | const MachineBasicBlock *MB; | ||||||
114 | }; | ||||||
115 | raw_ostream &operator<< (raw_ostream &OS, const PrintMB &P) { | ||||||
116 | if (!P.MB) | ||||||
117 | return OS << "<none>"; | ||||||
118 | return OS << '#' << P.MB->getNumber(); | ||||||
119 | } | ||||||
120 | |||||||
121 | struct FlowPattern { | ||||||
122 | FlowPattern() = default; | ||||||
123 | FlowPattern(MachineBasicBlock *B, unsigned PR, MachineBasicBlock *TB, | ||||||
124 | MachineBasicBlock *FB, MachineBasicBlock *JB) | ||||||
125 | : SplitB(B), TrueB(TB), FalseB(FB), JoinB(JB), PredR(PR) {} | ||||||
126 | |||||||
127 | MachineBasicBlock *SplitB = nullptr; | ||||||
128 | MachineBasicBlock *TrueB = nullptr; | ||||||
129 | MachineBasicBlock *FalseB = nullptr; | ||||||
130 | MachineBasicBlock *JoinB = nullptr; | ||||||
131 | unsigned PredR = 0; | ||||||
132 | }; | ||||||
133 | |||||||
134 | struct PrintFP { | ||||||
135 | PrintFP(const FlowPattern &P, const TargetRegisterInfo &T) | ||||||
136 | : FP(P), TRI(T) {} | ||||||
137 | |||||||
138 | const FlowPattern &FP; | ||||||
139 | const TargetRegisterInfo &TRI; | ||||||
140 | friend raw_ostream &operator<< (raw_ostream &OS, const PrintFP &P); | ||||||
141 | }; | ||||||
142 | raw_ostream &operator<<(raw_ostream &OS, | ||||||
143 | const PrintFP &P) LLVM_ATTRIBUTE_UNUSED__attribute__((__unused__)); | ||||||
144 | raw_ostream &operator<<(raw_ostream &OS, const PrintFP &P) { | ||||||
145 | OS << "{ SplitB:" << PrintMB(P.FP.SplitB) | ||||||
146 | << ", PredR:" << printReg(P.FP.PredR, &P.TRI) | ||||||
147 | << ", TrueB:" << PrintMB(P.FP.TrueB) | ||||||
148 | << ", FalseB:" << PrintMB(P.FP.FalseB) | ||||||
149 | << ", JoinB:" << PrintMB(P.FP.JoinB) << " }"; | ||||||
150 | return OS; | ||||||
151 | } | ||||||
152 | |||||||
153 | class HexagonEarlyIfConversion : public MachineFunctionPass { | ||||||
154 | public: | ||||||
155 | static char ID; | ||||||
156 | |||||||
157 | HexagonEarlyIfConversion() : MachineFunctionPass(ID) {} | ||||||
158 | |||||||
159 | StringRef getPassName() const override { | ||||||
160 | return "Hexagon early if conversion"; | ||||||
161 | } | ||||||
162 | |||||||
163 | void getAnalysisUsage(AnalysisUsage &AU) const override { | ||||||
164 | AU.addRequired<MachineBranchProbabilityInfo>(); | ||||||
165 | AU.addRequired<MachineDominatorTree>(); | ||||||
166 | AU.addPreserved<MachineDominatorTree>(); | ||||||
167 | AU.addRequired<MachineLoopInfo>(); | ||||||
168 | MachineFunctionPass::getAnalysisUsage(AU); | ||||||
169 | } | ||||||
170 | |||||||
171 | bool runOnMachineFunction(MachineFunction &MF) override; | ||||||
172 | |||||||
173 | private: | ||||||
174 | using BlockSetType = DenseSet<MachineBasicBlock *>; | ||||||
175 | |||||||
176 | bool isPreheader(const MachineBasicBlock *B) const; | ||||||
177 | bool matchFlowPattern(MachineBasicBlock *B, MachineLoop *L, | ||||||
178 | FlowPattern &FP); | ||||||
179 | bool visitBlock(MachineBasicBlock *B, MachineLoop *L); | ||||||
180 | bool visitLoop(MachineLoop *L); | ||||||
181 | |||||||
182 | bool hasEHLabel(const MachineBasicBlock *B) const; | ||||||
183 | bool hasUncondBranch(const MachineBasicBlock *B) const; | ||||||
184 | bool isValidCandidate(const MachineBasicBlock *B) const; | ||||||
185 | bool usesUndefVReg(const MachineInstr *MI) const; | ||||||
186 | bool isValid(const FlowPattern &FP) const; | ||||||
187 | unsigned countPredicateDefs(const MachineBasicBlock *B) const; | ||||||
188 | unsigned computePhiCost(const MachineBasicBlock *B, | ||||||
189 | const FlowPattern &FP) const; | ||||||
190 | bool isProfitable(const FlowPattern &FP) const; | ||||||
191 | bool isPredicableStore(const MachineInstr *MI) const; | ||||||
192 | bool isSafeToSpeculate(const MachineInstr *MI) const; | ||||||
193 | bool isPredicate(unsigned R) const; | ||||||
194 | |||||||
195 | unsigned getCondStoreOpcode(unsigned Opc, bool IfTrue) const; | ||||||
196 | void predicateInstr(MachineBasicBlock *ToB, MachineBasicBlock::iterator At, | ||||||
197 | MachineInstr *MI, unsigned PredR, bool IfTrue); | ||||||
198 | void predicateBlockNB(MachineBasicBlock *ToB, | ||||||
199 | MachineBasicBlock::iterator At, MachineBasicBlock *FromB, | ||||||
200 | unsigned PredR, bool IfTrue); | ||||||
201 | |||||||
202 | unsigned buildMux(MachineBasicBlock *B, MachineBasicBlock::iterator At, | ||||||
203 | const TargetRegisterClass *DRC, unsigned PredR, unsigned TR, | ||||||
204 | unsigned TSR, unsigned FR, unsigned FSR); | ||||||
205 | void updatePhiNodes(MachineBasicBlock *WhereB, const FlowPattern &FP); | ||||||
206 | void convert(const FlowPattern &FP); | ||||||
207 | |||||||
208 | void removeBlock(MachineBasicBlock *B); | ||||||
209 | void eliminatePhis(MachineBasicBlock *B); | ||||||
210 | void mergeBlocks(MachineBasicBlock *PredB, MachineBasicBlock *SuccB); | ||||||
211 | void simplifyFlowGraph(const FlowPattern &FP); | ||||||
212 | |||||||
213 | const HexagonInstrInfo *HII = nullptr; | ||||||
214 | const TargetRegisterInfo *TRI = nullptr; | ||||||
215 | MachineFunction *MFN = nullptr; | ||||||
216 | MachineRegisterInfo *MRI = nullptr; | ||||||
217 | MachineDominatorTree *MDT = nullptr; | ||||||
218 | MachineLoopInfo *MLI = nullptr; | ||||||
219 | BlockSetType Deleted; | ||||||
220 | const MachineBranchProbabilityInfo *MBPI = nullptr; | ||||||
221 | }; | ||||||
222 | |||||||
223 | } // end anonymous namespace | ||||||
224 | |||||||
225 | char HexagonEarlyIfConversion::ID = 0; | ||||||
226 | |||||||
227 | INITIALIZE_PASS(HexagonEarlyIfConversion, "hexagon-early-if",static void *initializeHexagonEarlyIfConversionPassOnce(PassRegistry &Registry) { PassInfo *PI = new PassInfo( "Hexagon early if conversion" , "hexagon-early-if", &HexagonEarlyIfConversion::ID, PassInfo ::NormalCtor_t(callDefaultCtor<HexagonEarlyIfConversion> ), false, false); Registry.registerPass(*PI, true); return PI ; } static llvm::once_flag InitializeHexagonEarlyIfConversionPassFlag ; void llvm::initializeHexagonEarlyIfConversionPass(PassRegistry &Registry) { llvm::call_once(InitializeHexagonEarlyIfConversionPassFlag , initializeHexagonEarlyIfConversionPassOnce, std::ref(Registry )); } | ||||||
228 | "Hexagon early if conversion", false, false)static void *initializeHexagonEarlyIfConversionPassOnce(PassRegistry &Registry) { PassInfo *PI = new PassInfo( "Hexagon early if conversion" , "hexagon-early-if", &HexagonEarlyIfConversion::ID, PassInfo ::NormalCtor_t(callDefaultCtor<HexagonEarlyIfConversion> ), false, false); Registry.registerPass(*PI, true); return PI ; } static llvm::once_flag InitializeHexagonEarlyIfConversionPassFlag ; void llvm::initializeHexagonEarlyIfConversionPass(PassRegistry &Registry) { llvm::call_once(InitializeHexagonEarlyIfConversionPassFlag , initializeHexagonEarlyIfConversionPassOnce, std::ref(Registry )); } | ||||||
229 | |||||||
230 | bool HexagonEarlyIfConversion::isPreheader(const MachineBasicBlock *B) const { | ||||||
231 | if (B->succ_size() != 1) | ||||||
232 | return false; | ||||||
233 | MachineBasicBlock *SB = *B->succ_begin(); | ||||||
234 | MachineLoop *L = MLI->getLoopFor(SB); | ||||||
235 | return L && SB == L->getHeader() && MDT->dominates(B, SB); | ||||||
236 | } | ||||||
237 | |||||||
238 | bool HexagonEarlyIfConversion::matchFlowPattern(MachineBasicBlock *B, | ||||||
239 | MachineLoop *L, FlowPattern &FP) { | ||||||
240 | LLVM_DEBUG(dbgs() << "Checking flow pattern at " << printMBBReference(*B)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("hexagon-eif")) { dbgs() << "Checking flow pattern at " << printMBBReference(*B) << "\n"; } } while (false ) | ||||||
241 | << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("hexagon-eif")) { dbgs() << "Checking flow pattern at " << printMBBReference(*B) << "\n"; } } while (false ); | ||||||
242 | |||||||
243 | // Interested only in conditional branches, no .new, no new-value, etc. | ||||||
244 | // Check the terminators directly, it's easier than handling all responses | ||||||
245 | // from analyzeBranch. | ||||||
246 | MachineBasicBlock *TB = nullptr, *FB = nullptr; | ||||||
247 | MachineBasicBlock::const_iterator T1I = B->getFirstTerminator(); | ||||||
248 | if (T1I == B->end()) | ||||||
249 | return false; | ||||||
250 | unsigned Opc = T1I->getOpcode(); | ||||||
251 | if (Opc != Hexagon::J2_jumpt && Opc != Hexagon::J2_jumpf) | ||||||
252 | return false; | ||||||
253 | Register PredR = T1I->getOperand(0).getReg(); | ||||||
254 | |||||||
255 | // Get the layout successor, or 0 if B does not have one. | ||||||
256 | MachineFunction::iterator NextBI = std::next(MachineFunction::iterator(B)); | ||||||
257 | MachineBasicBlock *NextB = (NextBI != MFN->end()) ? &*NextBI : nullptr; | ||||||
258 | |||||||
259 | MachineBasicBlock *T1B = T1I->getOperand(1).getMBB(); | ||||||
260 | MachineBasicBlock::const_iterator T2I = std::next(T1I); | ||||||
261 | // The second terminator should be an unconditional branch. | ||||||
262 | assert(T2I == B->end() || T2I->getOpcode() == Hexagon::J2_jump)((T2I == B->end() || T2I->getOpcode() == Hexagon::J2_jump ) ? static_cast<void> (0) : __assert_fail ("T2I == B->end() || T2I->getOpcode() == Hexagon::J2_jump" , "/build/llvm-toolchain-snapshot-10~++20200110111110+a1cc19b5814/llvm/lib/Target/Hexagon/HexagonEarlyIfConv.cpp" , 262, __PRETTY_FUNCTION__)); | ||||||
263 | MachineBasicBlock *T2B = (T2I == B->end()) ? NextB | ||||||
264 | : T2I->getOperand(0).getMBB(); | ||||||
265 | if (T1B == T2B) { | ||||||
266 | // XXX merge if T1B == NextB, or convert branch to unconditional. | ||||||
267 | // mark as diamond with both sides equal? | ||||||
268 | return false; | ||||||
269 | } | ||||||
270 | |||||||
271 | // Record the true/false blocks in such a way that "true" means "if (PredR)", | ||||||
272 | // and "false" means "if (!PredR)". | ||||||
273 | if (Opc
| ||||||
274 | TB = T1B, FB = T2B; | ||||||
275 | else | ||||||
276 | TB = T2B, FB = T1B; | ||||||
277 | |||||||
278 | if (!MDT->properlyDominates(B, TB) || !MDT->properlyDominates(B, FB)) | ||||||
279 | return false; | ||||||
280 | |||||||
281 | // Detect triangle first. In case of a triangle, one of the blocks TB/FB | ||||||
282 | // can fall through into the other, in other words, it will be executed | ||||||
283 | // in both cases. We only want to predicate the block that is executed | ||||||
284 | // conditionally. | ||||||
285 | unsigned TNP = TB->pred_size(), FNP = FB->pred_size(); | ||||||
| |||||||
286 | unsigned TNS = TB->succ_size(), FNS = FB->succ_size(); | ||||||
287 | |||||||
288 | // A block is predicable if it has one predecessor (it must be B), and | ||||||
289 | // it has a single successor. In fact, the block has to end either with | ||||||
290 | // an unconditional branch (which can be predicated), or with a fall- | ||||||
291 | // through. | ||||||
292 | // Also, skip blocks that do not belong to the same loop. | ||||||
293 | bool TOk = (TNP == 1 && TNS == 1 && MLI->getLoopFor(TB) == L); | ||||||
294 | bool FOk = (FNP == 1 && FNS == 1 && MLI->getLoopFor(FB) == L); | ||||||
295 | |||||||
296 | // If requested (via an option), do not consider branches where the | ||||||
297 | // true and false targets do not belong to the same loop. | ||||||
298 | if (SkipExitBranches && MLI->getLoopFor(TB) != MLI->getLoopFor(FB)) | ||||||
299 | return false; | ||||||
300 | |||||||
301 | // If neither is predicable, there is nothing interesting. | ||||||
302 | if (!TOk && !FOk) | ||||||
303 | return false; | ||||||
304 | |||||||
305 | MachineBasicBlock *TSB = (TNS > 0) ? *TB->succ_begin() : nullptr; | ||||||
306 | MachineBasicBlock *FSB = (FNS > 0) ? *FB->succ_begin() : nullptr; | ||||||
307 | MachineBasicBlock *JB = nullptr; | ||||||
308 | |||||||
309 | if (TOk) { | ||||||
310 | if (FOk) { | ||||||
311 | if (TSB == FSB) | ||||||
312 | JB = TSB; | ||||||
313 | // Diamond: "if (P) then TB; else FB;". | ||||||
314 | } else { | ||||||
315 | // TOk && !FOk | ||||||
316 | if (TSB == FB) | ||||||
317 | JB = FB; | ||||||
318 | FB = nullptr; | ||||||
319 | } | ||||||
320 | } else { | ||||||
321 | // !TOk && FOk (at least one must be true by now). | ||||||
322 | if (FSB == TB) | ||||||
323 | JB = TB; | ||||||
324 | TB = nullptr; | ||||||
325 | } | ||||||
326 | // Don't try to predicate loop preheaders. | ||||||
327 | if ((TB && isPreheader(TB)) || (FB && isPreheader(FB))) { | ||||||
328 | LLVM_DEBUG(dbgs() << "One of blocks " << PrintMB(TB) << ", " << PrintMB(FB)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("hexagon-eif")) { dbgs() << "One of blocks " << PrintMB (TB) << ", " << PrintMB(FB) << " is a loop preheader. Skipping.\n" ; } } while (false) | ||||||
329 | << " is a loop preheader. Skipping.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("hexagon-eif")) { dbgs() << "One of blocks " << PrintMB (TB) << ", " << PrintMB(FB) << " is a loop preheader. Skipping.\n" ; } } while (false); | ||||||
330 | return false; | ||||||
331 | } | ||||||
332 | |||||||
333 | FP = FlowPattern(B, PredR, TB, FB, JB); | ||||||
334 | LLVM_DEBUG(dbgs() << "Detected " << PrintFP(FP, *TRI) << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("hexagon-eif")) { dbgs() << "Detected " << PrintFP (FP, *TRI) << "\n"; } } while (false); | ||||||
335 | return true; | ||||||
336 | } | ||||||
337 | |||||||
338 | // KLUDGE: HexagonInstrInfo::analyzeBranch won't work on a block that | ||||||
339 | // contains EH_LABEL. | ||||||
340 | bool HexagonEarlyIfConversion::hasEHLabel(const MachineBasicBlock *B) const { | ||||||
341 | for (auto &I : *B) | ||||||
342 | if (I.isEHLabel()) | ||||||
343 | return true; | ||||||
344 | return false; | ||||||
345 | } | ||||||
346 | |||||||
347 | // KLUDGE: HexagonInstrInfo::analyzeBranch may be unable to recognize | ||||||
348 | // that a block can never fall-through. | ||||||
349 | bool HexagonEarlyIfConversion::hasUncondBranch(const MachineBasicBlock *B) | ||||||
350 | const { | ||||||
351 | MachineBasicBlock::const_iterator I = B->getFirstTerminator(), E = B->end(); | ||||||
352 | while (I != E) { | ||||||
353 | if (I->isBarrier()) | ||||||
354 | return true; | ||||||
355 | ++I; | ||||||
356 | } | ||||||
357 | return false; | ||||||
358 | } | ||||||
359 | |||||||
360 | bool HexagonEarlyIfConversion::isValidCandidate(const MachineBasicBlock *B) | ||||||
361 | const { | ||||||
362 | if (!B) | ||||||
363 | return true; | ||||||
364 | if (B->isEHPad() || B->hasAddressTaken()) | ||||||
365 | return false; | ||||||
366 | if (B->succ_size() == 0) | ||||||
367 | return false; | ||||||
368 | |||||||
369 | for (auto &MI : *B) { | ||||||
370 | if (MI.isDebugInstr()) | ||||||
371 | continue; | ||||||
372 | if (MI.isConditionalBranch()) | ||||||
373 | return false; | ||||||
374 | unsigned Opc = MI.getOpcode(); | ||||||
375 | bool IsJMP = (Opc == Hexagon::J2_jump); | ||||||
376 | if (!isPredicableStore(&MI) && !IsJMP && !isSafeToSpeculate(&MI)) | ||||||
377 | return false; | ||||||
378 | // Look for predicate registers defined by this instruction. It's ok | ||||||
379 | // to speculate such an instruction, but the predicate register cannot | ||||||
380 | // be used outside of this block (or else it won't be possible to | ||||||
381 | // update the use of it after predication). PHI uses will be updated | ||||||
382 | // to use a result of a MUX, and a MUX cannot be created for predicate | ||||||
383 | // registers. | ||||||
384 | for (const MachineOperand &MO : MI.operands()) { | ||||||
385 | if (!MO.isReg() || !MO.isDef()) | ||||||
386 | continue; | ||||||
387 | Register R = MO.getReg(); | ||||||
388 | if (!Register::isVirtualRegister(R)) | ||||||
389 | continue; | ||||||
390 | if (!isPredicate(R)) | ||||||
391 | continue; | ||||||
392 | for (auto U = MRI->use_begin(R); U != MRI->use_end(); ++U) | ||||||
393 | if (U->getParent()->isPHI()) | ||||||
394 | return false; | ||||||
395 | } | ||||||
396 | } | ||||||
397 | return true; | ||||||
398 | } | ||||||
399 | |||||||
400 | bool HexagonEarlyIfConversion::usesUndefVReg(const MachineInstr *MI) const { | ||||||
401 | for (const MachineOperand &MO : MI->operands()) { | ||||||
402 | if (!MO.isReg() || !MO.isUse()) | ||||||
403 | continue; | ||||||
404 | Register R = MO.getReg(); | ||||||
405 | if (!Register::isVirtualRegister(R)) | ||||||
406 | continue; | ||||||
407 | const MachineInstr *DefI = MRI->getVRegDef(R); | ||||||
408 | // "Undefined" virtual registers are actually defined via IMPLICIT_DEF. | ||||||
409 | assert(DefI && "Expecting a reaching def in MRI")((DefI && "Expecting a reaching def in MRI") ? static_cast <void> (0) : __assert_fail ("DefI && \"Expecting a reaching def in MRI\"" , "/build/llvm-toolchain-snapshot-10~++20200110111110+a1cc19b5814/llvm/lib/Target/Hexagon/HexagonEarlyIfConv.cpp" , 409, __PRETTY_FUNCTION__)); | ||||||
410 | if (DefI->isImplicitDef()) | ||||||
411 | return true; | ||||||
412 | } | ||||||
413 | return false; | ||||||
414 | } | ||||||
415 | |||||||
416 | bool HexagonEarlyIfConversion::isValid(const FlowPattern &FP) const { | ||||||
417 | if (hasEHLabel(FP.SplitB)) // KLUDGE: see function definition | ||||||
418 | return false; | ||||||
419 | if (FP.TrueB && !isValidCandidate(FP.TrueB)) | ||||||
420 | return false; | ||||||
421 | if (FP.FalseB && !isValidCandidate(FP.FalseB)) | ||||||
422 | return false; | ||||||
423 | // Check the PHIs in the join block. If any of them use a register | ||||||
424 | // that is defined as IMPLICIT_DEF, do not convert this. This can | ||||||
425 | // legitimately happen if one side of the split never executes, but | ||||||
426 | // the compiler is unable to prove it. That side may then seem to | ||||||
427 | // provide an "undef" value to the join block, however it will never | ||||||
428 | // execute at run-time. If we convert this case, the "undef" will | ||||||
429 | // be used in a MUX instruction, and that may seem like actually | ||||||
430 | // using an undefined value to other optimizations. This could lead | ||||||
431 | // to trouble further down the optimization stream, cause assertions | ||||||
432 | // to fail, etc. | ||||||
433 | if (FP.JoinB) { | ||||||
434 | const MachineBasicBlock &B = *FP.JoinB; | ||||||
435 | for (auto &MI : B) { | ||||||
436 | if (!MI.isPHI()) | ||||||
437 | break; | ||||||
438 | if (usesUndefVReg(&MI)) | ||||||
439 | return false; | ||||||
440 | Register DefR = MI.getOperand(0).getReg(); | ||||||
441 | if (isPredicate(DefR)) | ||||||
442 | return false; | ||||||
443 | } | ||||||
444 | } | ||||||
445 | return true; | ||||||
446 | } | ||||||
447 | |||||||
448 | unsigned HexagonEarlyIfConversion::computePhiCost(const MachineBasicBlock *B, | ||||||
449 | const FlowPattern &FP) const { | ||||||
450 | if (B->pred_size() < 2) | ||||||
451 | return 0; | ||||||
452 | |||||||
453 | unsigned Cost = 0; | ||||||
454 | for (const MachineInstr &MI : *B) { | ||||||
455 | if (!MI.isPHI()) | ||||||
456 | break; | ||||||
457 | // If both incoming blocks are one of the TrueB/FalseB/SplitB, then | ||||||
458 | // a MUX may be needed. Otherwise the PHI will need to be updated at | ||||||
459 | // no extra cost. | ||||||
460 | // Find the interesting PHI operands for further checks. | ||||||
461 | SmallVector<unsigned,2> Inc; | ||||||
462 | for (unsigned i = 1, e = MI.getNumOperands(); i != e; i += 2) { | ||||||
463 | const MachineBasicBlock *BB = MI.getOperand(i+1).getMBB(); | ||||||
464 | if (BB == FP.SplitB || BB == FP.TrueB || BB == FP.FalseB) | ||||||
465 | Inc.push_back(i); | ||||||
466 | } | ||||||
467 | assert(Inc.size() <= 2)((Inc.size() <= 2) ? static_cast<void> (0) : __assert_fail ("Inc.size() <= 2", "/build/llvm-toolchain-snapshot-10~++20200110111110+a1cc19b5814/llvm/lib/Target/Hexagon/HexagonEarlyIfConv.cpp" , 467, __PRETTY_FUNCTION__)); | ||||||
468 | if (Inc.size() < 2) | ||||||
469 | continue; | ||||||
470 | |||||||
471 | const MachineOperand &RA = MI.getOperand(1); | ||||||
472 | const MachineOperand &RB = MI.getOperand(3); | ||||||
473 | assert(RA.isReg() && RB.isReg())((RA.isReg() && RB.isReg()) ? static_cast<void> (0) : __assert_fail ("RA.isReg() && RB.isReg()", "/build/llvm-toolchain-snapshot-10~++20200110111110+a1cc19b5814/llvm/lib/Target/Hexagon/HexagonEarlyIfConv.cpp" , 473, __PRETTY_FUNCTION__)); | ||||||
474 | // Must have a MUX if the phi uses a subregister. | ||||||
475 | if (RA.getSubReg() != 0 || RB.getSubReg() != 0) { | ||||||
476 | Cost++; | ||||||
477 | continue; | ||||||
478 | } | ||||||
479 | const MachineInstr *Def1 = MRI->getVRegDef(RA.getReg()); | ||||||
480 | const MachineInstr *Def3 = MRI->getVRegDef(RB.getReg()); | ||||||
481 | if (!HII->isPredicable(*Def1) || !HII->isPredicable(*Def3)) | ||||||
482 | Cost++; | ||||||
483 | } | ||||||
484 | return Cost; | ||||||
485 | } | ||||||
486 | |||||||
487 | unsigned HexagonEarlyIfConversion::countPredicateDefs( | ||||||
488 | const MachineBasicBlock *B) const { | ||||||
489 | unsigned PredDefs = 0; | ||||||
490 | for (auto &MI : *B) { | ||||||
491 | for (const MachineOperand &MO : MI.operands()) { | ||||||
492 | if (!MO.isReg() || !MO.isDef()) | ||||||
493 | continue; | ||||||
494 | Register R = MO.getReg(); | ||||||
495 | if (!Register::isVirtualRegister(R)) | ||||||
496 | continue; | ||||||
497 | if (isPredicate(R)) | ||||||
498 | PredDefs++; | ||||||
499 | } | ||||||
500 | } | ||||||
501 | return PredDefs; | ||||||
502 | } | ||||||
503 | |||||||
504 | bool HexagonEarlyIfConversion::isProfitable(const FlowPattern &FP) const { | ||||||
505 | BranchProbability JumpProb(1, 10); | ||||||
506 | BranchProbability Prob(9, 10); | ||||||
507 | if (MBPI && FP.TrueB && !FP.FalseB && | ||||||
508 | (MBPI->getEdgeProbability(FP.SplitB, FP.TrueB) < JumpProb || | ||||||
509 | MBPI->getEdgeProbability(FP.SplitB, FP.TrueB) > Prob)) | ||||||
510 | return false; | ||||||
511 | |||||||
512 | if (MBPI && !FP.TrueB && FP.FalseB && | ||||||
513 | (MBPI->getEdgeProbability(FP.SplitB, FP.FalseB) < JumpProb || | ||||||
514 | MBPI->getEdgeProbability(FP.SplitB, FP.FalseB) > Prob)) | ||||||
515 | return false; | ||||||
516 | |||||||
517 | if (FP.TrueB && FP.FalseB) { | ||||||
518 | // Do not IfCovert if the branch is one sided. | ||||||
519 | if (MBPI) { | ||||||
520 | if (MBPI->getEdgeProbability(FP.SplitB, FP.TrueB) > Prob) | ||||||
521 | return false; | ||||||
522 | if (MBPI->getEdgeProbability(FP.SplitB, FP.FalseB) > Prob) | ||||||
523 | return false; | ||||||
524 | } | ||||||
525 | |||||||
526 | // If both sides are predicable, convert them if they join, and the | ||||||
527 | // join block has no other predecessors. | ||||||
528 | MachineBasicBlock *TSB = *FP.TrueB->succ_begin(); | ||||||
529 | MachineBasicBlock *FSB = *FP.FalseB->succ_begin(); | ||||||
530 | if (TSB != FSB) | ||||||
531 | return false; | ||||||
532 | if (TSB->pred_size() != 2) | ||||||
533 | return false; | ||||||
534 | } | ||||||
535 | |||||||
536 | // Calculate the total size of the predicated blocks. | ||||||
537 | // Assume instruction counts without branches to be the approximation of | ||||||
538 | // the code size. If the predicated blocks are smaller than a packet size, | ||||||
539 | // approximate the spare room in the packet that could be filled with the | ||||||
540 | // predicated/speculated instructions. | ||||||
541 | auto TotalCount = [] (const MachineBasicBlock *B, unsigned &Spare) { | ||||||
542 | if (!B) | ||||||
543 | return 0u; | ||||||
544 | unsigned T = std::count_if(B->begin(), B->getFirstTerminator(), | ||||||
545 | [](const MachineInstr &MI) { | ||||||
546 | return !MI.isMetaInstruction(); | ||||||
547 | }); | ||||||
548 | if (T < HEXAGON_PACKET_SIZE4) | ||||||
549 | Spare += HEXAGON_PACKET_SIZE4-T; | ||||||
550 | return T; | ||||||
551 | }; | ||||||
552 | unsigned Spare = 0; | ||||||
553 | unsigned TotalIn = TotalCount(FP.TrueB, Spare) + TotalCount(FP.FalseB, Spare); | ||||||
554 | LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("hexagon-eif")) { dbgs() << "Total number of instructions to be predicated/speculated: " << TotalIn << ", spare room: " << Spare << "\n"; } } while (false) | ||||||
555 | dbgs() << "Total number of instructions to be predicated/speculated: "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("hexagon-eif")) { dbgs() << "Total number of instructions to be predicated/speculated: " << TotalIn << ", spare room: " << Spare << "\n"; } } while (false) | ||||||
556 | << TotalIn << ", spare room: " << Spare << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("hexagon-eif")) { dbgs() << "Total number of instructions to be predicated/speculated: " << TotalIn << ", spare room: " << Spare << "\n"; } } while (false); | ||||||
557 | if (TotalIn >= SizeLimit+Spare) | ||||||
558 | return false; | ||||||
559 | |||||||
560 | // Count the number of PHI nodes that will need to be updated (converted | ||||||
561 | // to MUX). Those can be later converted to predicated instructions, so | ||||||
562 | // they aren't always adding extra cost. | ||||||
563 | // KLUDGE: Also, count the number of predicate register definitions in | ||||||
564 | // each block. The scheduler may increase the pressure of these and cause | ||||||
565 | // expensive spills (e.g. bitmnp01). | ||||||
566 | unsigned TotalPh = 0; | ||||||
567 | unsigned PredDefs = countPredicateDefs(FP.SplitB); | ||||||
568 | if (FP.JoinB) { | ||||||
569 | TotalPh = computePhiCost(FP.JoinB, FP); | ||||||
570 | PredDefs += countPredicateDefs(FP.JoinB); | ||||||
571 | } else { | ||||||
572 | if (FP.TrueB && FP.TrueB->succ_size() > 0) { | ||||||
573 | MachineBasicBlock *SB = *FP.TrueB->succ_begin(); | ||||||
574 | TotalPh += computePhiCost(SB, FP); | ||||||
575 | PredDefs += countPredicateDefs(SB); | ||||||
576 | } | ||||||
577 | if (FP.FalseB && FP.FalseB->succ_size() > 0) { | ||||||
578 | MachineBasicBlock *SB = *FP.FalseB->succ_begin(); | ||||||
579 | TotalPh += computePhiCost(SB, FP); | ||||||
580 | PredDefs += countPredicateDefs(SB); | ||||||
581 | } | ||||||
582 | } | ||||||
583 | LLVM_DEBUG(dbgs() << "Total number of extra muxes from converted phis: "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("hexagon-eif")) { dbgs() << "Total number of extra muxes from converted phis: " << TotalPh << "\n"; } } while (false) | ||||||
584 | << TotalPh << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("hexagon-eif")) { dbgs() << "Total number of extra muxes from converted phis: " << TotalPh << "\n"; } } while (false); | ||||||
585 | if (TotalIn+TotalPh >= SizeLimit+Spare) | ||||||
586 | return false; | ||||||
587 | |||||||
588 | LLVM_DEBUG(dbgs() << "Total number of predicate registers: " << PredDefsdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("hexagon-eif")) { dbgs() << "Total number of predicate registers: " << PredDefs << "\n"; } } while (false) | ||||||
589 | << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("hexagon-eif")) { dbgs() << "Total number of predicate registers: " << PredDefs << "\n"; } } while (false); | ||||||
590 | if (PredDefs > 4) | ||||||
591 | return false; | ||||||
592 | |||||||
593 | return true; | ||||||
594 | } | ||||||
595 | |||||||
596 | bool HexagonEarlyIfConversion::visitBlock(MachineBasicBlock *B, | ||||||
597 | MachineLoop *L) { | ||||||
598 | bool Changed = false; | ||||||
599 | |||||||
600 | // Visit all dominated blocks from the same loop first, then process B. | ||||||
601 | MachineDomTreeNode *N = MDT->getNode(B); | ||||||
602 | |||||||
603 | using GTN = GraphTraits<MachineDomTreeNode *>; | ||||||
604 | |||||||
605 | // We will change CFG/DT during this traversal, so take precautions to | ||||||
606 | // avoid problems related to invalidated iterators. In fact, processing | ||||||
607 | // a child C of B cannot cause another child to be removed, but it can | ||||||
608 | // cause a new child to be added (which was a child of C before C itself | ||||||
609 | // was removed. This new child C, however, would have been processed | ||||||
610 | // prior to processing B, so there is no need to process it again. | ||||||
611 | // Simply keep a list of children of B, and traverse that list. | ||||||
612 | using DTNodeVectType = SmallVector<MachineDomTreeNode *, 4>; | ||||||
613 | DTNodeVectType Cn(GTN::child_begin(N), GTN::child_end(N)); | ||||||
614 | for (DTNodeVectType::iterator I = Cn.begin(), E = Cn.end(); I != E; ++I) { | ||||||
615 | MachineBasicBlock *SB = (*I)->getBlock(); | ||||||
616 | if (!Deleted.count(SB)) | ||||||
617 | Changed |= visitBlock(SB, L); | ||||||
618 | } | ||||||
619 | // When walking down the dominator tree, we want to traverse through | ||||||
620 | // blocks from nested (other) loops, because they can dominate blocks | ||||||
621 | // that are in L. Skip the non-L blocks only after the tree traversal. | ||||||
622 | if (MLI->getLoopFor(B) != L) | ||||||
623 | return Changed; | ||||||
624 | |||||||
625 | FlowPattern FP; | ||||||
626 | if (!matchFlowPattern(B, L, FP)) | ||||||
627 | return Changed; | ||||||
628 | |||||||
629 | if (!isValid(FP)) { | ||||||
630 | LLVM_DEBUG(dbgs() << "Conversion is not valid\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("hexagon-eif")) { dbgs() << "Conversion is not valid\n" ; } } while (false); | ||||||
631 | return Changed; | ||||||
632 | } | ||||||
633 | if (!isProfitable(FP)) { | ||||||
634 | LLVM_DEBUG(dbgs() << "Conversion is not profitable\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("hexagon-eif")) { dbgs() << "Conversion is not profitable\n" ; } } while (false); | ||||||
635 | return Changed; | ||||||
636 | } | ||||||
637 | |||||||
638 | convert(FP); | ||||||
639 | simplifyFlowGraph(FP); | ||||||
640 | return true; | ||||||
641 | } | ||||||
642 | |||||||
643 | bool HexagonEarlyIfConversion::visitLoop(MachineLoop *L) { | ||||||
644 | MachineBasicBlock *HB = L
| ||||||
645 | LLVM_DEBUG((L ? dbgs() << "Visiting loop H:" << PrintMB(HB)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("hexagon-eif")) { (L ? dbgs() << "Visiting loop H:" << PrintMB(HB) : dbgs() << "Visiting function") << "\n" ; } } while (false) | ||||||
646 | : dbgs() << "Visiting function")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("hexagon-eif")) { (L ? dbgs() << "Visiting loop H:" << PrintMB(HB) : dbgs() << "Visiting function") << "\n" ; } } while (false) | ||||||
647 | << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("hexagon-eif")) { (L ? dbgs() << "Visiting loop H:" << PrintMB(HB) : dbgs() << "Visiting function") << "\n" ; } } while (false); | ||||||
648 | bool Changed = false; | ||||||
649 | if (L
| ||||||
650 | for (MachineLoop::iterator I = L->begin(), E = L->end(); I != E; ++I) | ||||||
651 | Changed |= visitLoop(*I); | ||||||
652 | } | ||||||
653 | |||||||
654 | MachineBasicBlock *EntryB = GraphTraits<MachineFunction*>::getEntryNode(MFN); | ||||||
655 | Changed |= visitBlock(L
| ||||||
656 | return Changed; | ||||||
657 | } | ||||||
658 | |||||||
659 | bool HexagonEarlyIfConversion::isPredicableStore(const MachineInstr *MI) | ||||||
660 | const { | ||||||
661 | // HexagonInstrInfo::isPredicable will consider these stores are non- | ||||||
662 | // -predicable if the offset would become constant-extended after | ||||||
663 | // predication. | ||||||
664 | unsigned Opc = MI->getOpcode(); | ||||||
665 | switch (Opc) { | ||||||
666 | case Hexagon::S2_storerb_io: | ||||||
667 | case Hexagon::S2_storerbnew_io: | ||||||
668 | case Hexagon::S2_storerh_io: | ||||||
669 | case Hexagon::S2_storerhnew_io: | ||||||
670 | case Hexagon::S2_storeri_io: | ||||||
671 | case Hexagon::S2_storerinew_io: | ||||||
672 | case Hexagon::S2_storerd_io: | ||||||
673 | case Hexagon::S4_storeirb_io: | ||||||
674 | case Hexagon::S4_storeirh_io: | ||||||
675 | case Hexagon::S4_storeiri_io: | ||||||
676 | return true; | ||||||
677 | } | ||||||
678 | |||||||
679 | // TargetInstrInfo::isPredicable takes a non-const pointer. | ||||||
680 | return MI->mayStore() && HII->isPredicable(const_cast<MachineInstr&>(*MI)); | ||||||
681 | } | ||||||
682 | |||||||
683 | bool HexagonEarlyIfConversion::isSafeToSpeculate(const MachineInstr *MI) | ||||||
684 | const { | ||||||
685 | if (MI->mayLoadOrStore()) | ||||||
686 | return false; | ||||||
687 | if (MI->isCall() || MI->isBarrier() || MI->isBranch()) | ||||||
688 | return false; | ||||||
689 | if (MI->hasUnmodeledSideEffects()) | ||||||
690 | return false; | ||||||
691 | if (MI->getOpcode() == TargetOpcode::LIFETIME_END) | ||||||
692 | return false; | ||||||
693 | |||||||
694 | return true; | ||||||
695 | } | ||||||
696 | |||||||
697 | bool HexagonEarlyIfConversion::isPredicate(unsigned R) const { | ||||||
698 | const TargetRegisterClass *RC = MRI->getRegClass(R); | ||||||
699 | return RC == &Hexagon::PredRegsRegClass || | ||||||
700 | RC == &Hexagon::HvxQRRegClass; | ||||||
701 | } | ||||||
702 | |||||||
703 | unsigned HexagonEarlyIfConversion::getCondStoreOpcode(unsigned Opc, | ||||||
704 | bool IfTrue) const { | ||||||
705 | return HII->getCondOpcode(Opc, !IfTrue); | ||||||
706 | } | ||||||
707 | |||||||
708 | void HexagonEarlyIfConversion::predicateInstr(MachineBasicBlock *ToB, | ||||||
709 | MachineBasicBlock::iterator At, MachineInstr *MI, | ||||||
710 | unsigned PredR, bool IfTrue) { | ||||||
711 | DebugLoc DL; | ||||||
712 | if (At != ToB->end()) | ||||||
713 | DL = At->getDebugLoc(); | ||||||
714 | else if (!ToB->empty()) | ||||||
715 | DL = ToB->back().getDebugLoc(); | ||||||
716 | |||||||
717 | unsigned Opc = MI->getOpcode(); | ||||||
718 | |||||||
719 | if (isPredicableStore(MI)) { | ||||||
720 | unsigned COpc = getCondStoreOpcode(Opc, IfTrue); | ||||||
721 | assert(COpc)((COpc) ? static_cast<void> (0) : __assert_fail ("COpc" , "/build/llvm-toolchain-snapshot-10~++20200110111110+a1cc19b5814/llvm/lib/Target/Hexagon/HexagonEarlyIfConv.cpp" , 721, __PRETTY_FUNCTION__)); | ||||||
722 | MachineInstrBuilder MIB = BuildMI(*ToB, At, DL, HII->get(COpc)); | ||||||
723 | MachineInstr::mop_iterator MOI = MI->operands_begin(); | ||||||
724 | if (HII->isPostIncrement(*MI)) { | ||||||
725 | MIB.add(*MOI); | ||||||
726 | ++MOI; | ||||||
727 | } | ||||||
728 | MIB.addReg(PredR); | ||||||
729 | for (const MachineOperand &MO : make_range(MOI, MI->operands_end())) | ||||||
730 | MIB.add(MO); | ||||||
731 | |||||||
732 | // Set memory references. | ||||||
733 | MIB.cloneMemRefs(*MI); | ||||||
734 | |||||||
735 | MI->eraseFromParent(); | ||||||
736 | return; | ||||||
737 | } | ||||||
738 | |||||||
739 | if (Opc == Hexagon::J2_jump) { | ||||||
740 | MachineBasicBlock *TB = MI->getOperand(0).getMBB(); | ||||||
741 | const MCInstrDesc &D = HII->get(IfTrue ? Hexagon::J2_jumpt | ||||||
742 | : Hexagon::J2_jumpf); | ||||||
743 | BuildMI(*ToB, At, DL, D) | ||||||
744 | .addReg(PredR) | ||||||
745 | .addMBB(TB); | ||||||
746 | MI->eraseFromParent(); | ||||||
747 | return; | ||||||
748 | } | ||||||
749 | |||||||
750 | // Print the offending instruction unconditionally as we are about to | ||||||
751 | // abort. | ||||||
752 | dbgs() << *MI; | ||||||
753 | llvm_unreachable("Unexpected instruction")::llvm::llvm_unreachable_internal("Unexpected instruction", "/build/llvm-toolchain-snapshot-10~++20200110111110+a1cc19b5814/llvm/lib/Target/Hexagon/HexagonEarlyIfConv.cpp" , 753); | ||||||
754 | } | ||||||
755 | |||||||
756 | // Predicate/speculate non-branch instructions from FromB into block ToB. | ||||||
757 | // Leave the branches alone, they will be handled later. Btw, at this point | ||||||
758 | // FromB should have at most one branch, and it should be unconditional. | ||||||
759 | void HexagonEarlyIfConversion::predicateBlockNB(MachineBasicBlock *ToB, | ||||||
760 | MachineBasicBlock::iterator At, MachineBasicBlock *FromB, | ||||||
761 | unsigned PredR, bool IfTrue) { | ||||||
762 | LLVM_DEBUG(dbgs() << "Predicating block " << PrintMB(FromB) << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("hexagon-eif")) { dbgs() << "Predicating block " << PrintMB(FromB) << "\n"; } } while (false); | ||||||
763 | MachineBasicBlock::iterator End = FromB->getFirstTerminator(); | ||||||
764 | MachineBasicBlock::iterator I, NextI; | ||||||
765 | |||||||
766 | for (I = FromB->begin(); I != End; I = NextI) { | ||||||
767 | assert(!I->isPHI())((!I->isPHI()) ? static_cast<void> (0) : __assert_fail ("!I->isPHI()", "/build/llvm-toolchain-snapshot-10~++20200110111110+a1cc19b5814/llvm/lib/Target/Hexagon/HexagonEarlyIfConv.cpp" , 767, __PRETTY_FUNCTION__)); | ||||||
768 | NextI = std::next(I); | ||||||
769 | if (isSafeToSpeculate(&*I)) | ||||||
770 | ToB->splice(At, FromB, I); | ||||||
771 | else | ||||||
772 | predicateInstr(ToB, At, &*I, PredR, IfTrue); | ||||||
773 | } | ||||||
774 | } | ||||||
775 | |||||||
776 | unsigned HexagonEarlyIfConversion::buildMux(MachineBasicBlock *B, | ||||||
777 | MachineBasicBlock::iterator At, const TargetRegisterClass *DRC, | ||||||
778 | unsigned PredR, unsigned TR, unsigned TSR, unsigned FR, unsigned FSR) { | ||||||
779 | unsigned Opc = 0; | ||||||
780 | switch (DRC->getID()) { | ||||||
781 | case Hexagon::IntRegsRegClassID: | ||||||
782 | case Hexagon::IntRegsLow8RegClassID: | ||||||
783 | Opc = Hexagon::C2_mux; | ||||||
784 | break; | ||||||
785 | case Hexagon::DoubleRegsRegClassID: | ||||||
786 | case Hexagon::GeneralDoubleLow8RegsRegClassID: | ||||||
787 | Opc = Hexagon::PS_pselect; | ||||||
788 | break; | ||||||
789 | case Hexagon::HvxVRRegClassID: | ||||||
790 | Opc = Hexagon::PS_vselect; | ||||||
791 | break; | ||||||
792 | case Hexagon::HvxWRRegClassID: | ||||||
793 | Opc = Hexagon::PS_wselect; | ||||||
794 | break; | ||||||
795 | default: | ||||||
796 | llvm_unreachable("unexpected register type")::llvm::llvm_unreachable_internal("unexpected register type", "/build/llvm-toolchain-snapshot-10~++20200110111110+a1cc19b5814/llvm/lib/Target/Hexagon/HexagonEarlyIfConv.cpp" , 796); | ||||||
797 | } | ||||||
798 | const MCInstrDesc &D = HII->get(Opc); | ||||||
799 | |||||||
800 | DebugLoc DL = B->findBranchDebugLoc(); | ||||||
801 | Register MuxR = MRI->createVirtualRegister(DRC); | ||||||
802 | BuildMI(*B, At, DL, D, MuxR) | ||||||
803 | .addReg(PredR) | ||||||
804 | .addReg(TR, 0, TSR) | ||||||
805 | .addReg(FR, 0, FSR); | ||||||
806 | return MuxR; | ||||||
807 | } | ||||||
808 | |||||||
809 | void HexagonEarlyIfConversion::updatePhiNodes(MachineBasicBlock *WhereB, | ||||||
810 | const FlowPattern &FP) { | ||||||
811 | // Visit all PHI nodes in the WhereB block and generate MUX instructions | ||||||
812 | // in the split block. Update the PHI nodes with the values of the MUX. | ||||||
813 | auto NonPHI = WhereB->getFirstNonPHI(); | ||||||
814 | for (auto I = WhereB->begin(); I != NonPHI; ++I) { | ||||||
815 | MachineInstr *PN = &*I; | ||||||
816 | // Registers and subregisters corresponding to TrueB, FalseB and SplitB. | ||||||
817 | unsigned TR = 0, TSR = 0, FR = 0, FSR = 0, SR = 0, SSR = 0; | ||||||
818 | for (int i = PN->getNumOperands()-2; i > 0; i -= 2) { | ||||||
819 | const MachineOperand &RO = PN->getOperand(i), &BO = PN->getOperand(i+1); | ||||||
820 | if (BO.getMBB() == FP.SplitB) | ||||||
821 | SR = RO.getReg(), SSR = RO.getSubReg(); | ||||||
822 | else if (BO.getMBB() == FP.TrueB) | ||||||
823 | TR = RO.getReg(), TSR = RO.getSubReg(); | ||||||
824 | else if (BO.getMBB() == FP.FalseB) | ||||||
825 | FR = RO.getReg(), FSR = RO.getSubReg(); | ||||||
826 | else | ||||||
827 | continue; | ||||||
828 | PN->RemoveOperand(i+1); | ||||||
829 | PN->RemoveOperand(i); | ||||||
830 | } | ||||||
831 | if (TR == 0) | ||||||
832 | TR = SR, TSR = SSR; | ||||||
833 | else if (FR == 0) | ||||||
834 | FR = SR, FSR = SSR; | ||||||
835 | |||||||
836 | assert(TR || FR)((TR || FR) ? static_cast<void> (0) : __assert_fail ("TR || FR" , "/build/llvm-toolchain-snapshot-10~++20200110111110+a1cc19b5814/llvm/lib/Target/Hexagon/HexagonEarlyIfConv.cpp" , 836, __PRETTY_FUNCTION__)); | ||||||
837 | unsigned MuxR = 0, MuxSR = 0; | ||||||
838 | |||||||
839 | if (TR && FR) { | ||||||
840 | Register DR = PN->getOperand(0).getReg(); | ||||||
841 | const TargetRegisterClass *RC = MRI->getRegClass(DR); | ||||||
842 | MuxR = buildMux(FP.SplitB, FP.SplitB->getFirstTerminator(), RC, | ||||||
843 | FP.PredR, TR, TSR, FR, FSR); | ||||||
844 | } else if (TR) { | ||||||
845 | MuxR = TR; | ||||||
846 | MuxSR = TSR; | ||||||
847 | } else { | ||||||
848 | MuxR = FR; | ||||||
849 | MuxSR = FSR; | ||||||
850 | } | ||||||
851 | |||||||
852 | PN->addOperand(MachineOperand::CreateReg(MuxR, false, false, false, false, | ||||||
853 | false, false, MuxSR)); | ||||||
854 | PN->addOperand(MachineOperand::CreateMBB(FP.SplitB)); | ||||||
855 | } | ||||||
856 | } | ||||||
857 | |||||||
858 | void HexagonEarlyIfConversion::convert(const FlowPattern &FP) { | ||||||
859 | MachineBasicBlock *TSB = nullptr, *FSB = nullptr; | ||||||
860 | MachineBasicBlock::iterator OldTI = FP.SplitB->getFirstTerminator(); | ||||||
861 | assert(OldTI != FP.SplitB->end())((OldTI != FP.SplitB->end()) ? static_cast<void> (0) : __assert_fail ("OldTI != FP.SplitB->end()", "/build/llvm-toolchain-snapshot-10~++20200110111110+a1cc19b5814/llvm/lib/Target/Hexagon/HexagonEarlyIfConv.cpp" , 861, __PRETTY_FUNCTION__)); | ||||||
862 | DebugLoc DL = OldTI->getDebugLoc(); | ||||||
863 | |||||||
864 | if (FP.TrueB) { | ||||||
865 | TSB = *FP.TrueB->succ_begin(); | ||||||
866 | predicateBlockNB(FP.SplitB, OldTI, FP.TrueB, FP.PredR, true); | ||||||
867 | } | ||||||
868 | if (FP.FalseB) { | ||||||
869 | FSB = *FP.FalseB->succ_begin(); | ||||||
870 | MachineBasicBlock::iterator At = FP.SplitB->getFirstTerminator(); | ||||||
871 | predicateBlockNB(FP.SplitB, At, FP.FalseB, FP.PredR, false); | ||||||
872 | } | ||||||
873 | |||||||
874 | // Regenerate new terminators in the split block and update the successors. | ||||||
875 | // First, remember any information that may be needed later and remove the | ||||||
876 | // existing terminators/successors from the split block. | ||||||
877 | MachineBasicBlock *SSB = nullptr; | ||||||
878 | FP.SplitB->erase(OldTI, FP.SplitB->end()); | ||||||
879 | while (FP.SplitB->succ_size() > 0) { | ||||||
880 | MachineBasicBlock *T = *FP.SplitB->succ_begin(); | ||||||
881 | // It's possible that the split block had a successor that is not a pre- | ||||||
882 | // dicated block. This could only happen if there was only one block to | ||||||
883 | // be predicated. Example: | ||||||
884 | // split_b: | ||||||
885 | // if (p) jump true_b | ||||||
886 | // jump unrelated2_b | ||||||
887 | // unrelated1_b: | ||||||
888 | // ... | ||||||
889 | // unrelated2_b: ; can have other predecessors, so it's not "false_b" | ||||||
890 | // jump other_b | ||||||
891 | // true_b: ; only reachable from split_b, can be predicated | ||||||
892 | // ... | ||||||
893 | // | ||||||
894 | // Find this successor (SSB) if it exists. | ||||||
895 | if (T != FP.TrueB && T != FP.FalseB) { | ||||||
896 | assert(!SSB)((!SSB) ? static_cast<void> (0) : __assert_fail ("!SSB" , "/build/llvm-toolchain-snapshot-10~++20200110111110+a1cc19b5814/llvm/lib/Target/Hexagon/HexagonEarlyIfConv.cpp" , 896, __PRETTY_FUNCTION__)); | ||||||
897 | SSB = T; | ||||||
898 | } | ||||||
899 | FP.SplitB->removeSuccessor(FP.SplitB->succ_begin()); | ||||||
900 | } | ||||||
901 | |||||||
902 | // Insert new branches and update the successors of the split block. This | ||||||
903 | // may create unconditional branches to the layout successor, etc., but | ||||||
904 | // that will be cleaned up later. For now, make sure that correct code is | ||||||
905 | // generated. | ||||||
906 | if (FP.JoinB) { | ||||||
907 | assert(!SSB || SSB == FP.JoinB)((!SSB || SSB == FP.JoinB) ? static_cast<void> (0) : __assert_fail ("!SSB || SSB == FP.JoinB", "/build/llvm-toolchain-snapshot-10~++20200110111110+a1cc19b5814/llvm/lib/Target/Hexagon/HexagonEarlyIfConv.cpp" , 907, __PRETTY_FUNCTION__)); | ||||||
908 | BuildMI(*FP.SplitB, FP.SplitB->end(), DL, HII->get(Hexagon::J2_jump)) | ||||||
909 | .addMBB(FP.JoinB); | ||||||
910 | FP.SplitB->addSuccessor(FP.JoinB); | ||||||
911 | } else { | ||||||
912 | bool HasBranch = false; | ||||||
913 | if (TSB) { | ||||||
914 | BuildMI(*FP.SplitB, FP.SplitB->end(), DL, HII->get(Hexagon::J2_jumpt)) | ||||||
915 | .addReg(FP.PredR) | ||||||
916 | .addMBB(TSB); | ||||||
917 | FP.SplitB->addSuccessor(TSB); | ||||||
918 | HasBranch = true; | ||||||
919 | } | ||||||
920 | if (FSB) { | ||||||
921 | const MCInstrDesc &D = HasBranch ? HII->get(Hexagon::J2_jump) | ||||||
922 | : HII->get(Hexagon::J2_jumpf); | ||||||
923 | MachineInstrBuilder MIB = BuildMI(*FP.SplitB, FP.SplitB->end(), DL, D); | ||||||
924 | if (!HasBranch) | ||||||
925 | MIB.addReg(FP.PredR); | ||||||
926 | MIB.addMBB(FSB); | ||||||
927 | FP.SplitB->addSuccessor(FSB); | ||||||
928 | } | ||||||
929 | if (SSB) { | ||||||
930 | // This cannot happen if both TSB and FSB are set. [TF]SB are the | ||||||
931 | // successor blocks of the TrueB and FalseB (or null of the TrueB | ||||||
932 | // or FalseB block is null). SSB is the potential successor block | ||||||
933 | // of the SplitB that is neither TrueB nor FalseB. | ||||||
934 | BuildMI(*FP.SplitB, FP.SplitB->end(), DL, HII->get(Hexagon::J2_jump)) | ||||||
935 | .addMBB(SSB); | ||||||
936 | FP.SplitB->addSuccessor(SSB); | ||||||
937 | } | ||||||
938 | } | ||||||
939 | |||||||
940 | // What is left to do is to update the PHI nodes that could have entries | ||||||
941 | // referring to predicated blocks. | ||||||
942 | if (FP.JoinB) { | ||||||
943 | updatePhiNodes(FP.JoinB, FP); | ||||||
944 | } else { | ||||||
945 | if (TSB) | ||||||
946 | updatePhiNodes(TSB, FP); | ||||||
947 | if (FSB) | ||||||
948 | updatePhiNodes(FSB, FP); | ||||||
949 | // Nothing to update in SSB, since SSB's predecessors haven't changed. | ||||||
950 | } | ||||||
951 | } | ||||||
952 | |||||||
953 | void HexagonEarlyIfConversion::removeBlock(MachineBasicBlock *B) { | ||||||
954 | LLVM_DEBUG(dbgs() << "Removing block " << PrintMB(B) << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("hexagon-eif")) { dbgs() << "Removing block " << PrintMB(B) << "\n"; } } while (false); | ||||||
955 | |||||||
956 | // Transfer the immediate dominator information from B to its descendants. | ||||||
957 | MachineDomTreeNode *N = MDT->getNode(B); | ||||||
958 | MachineDomTreeNode *IDN = N->getIDom(); | ||||||
959 | if (IDN) { | ||||||
960 | MachineBasicBlock *IDB = IDN->getBlock(); | ||||||
961 | |||||||
962 | using GTN = GraphTraits<MachineDomTreeNode *>; | ||||||
963 | using DTNodeVectType = SmallVector<MachineDomTreeNode *, 4>; | ||||||
964 | |||||||
965 | DTNodeVectType Cn(GTN::child_begin(N), GTN::child_end(N)); | ||||||
966 | for (DTNodeVectType::iterator I = Cn.begin(), E = Cn.end(); I != E; ++I) { | ||||||
967 | MachineBasicBlock *SB = (*I)->getBlock(); | ||||||
968 | MDT->changeImmediateDominator(SB, IDB); | ||||||
969 | } | ||||||
970 | } | ||||||
971 | |||||||
972 | while (B->succ_size() > 0) | ||||||
973 | B->removeSuccessor(B->succ_begin()); | ||||||
974 | |||||||
975 | for (auto I = B->pred_begin(), E = B->pred_end(); I != E; ++I) | ||||||
976 | (*I)->removeSuccessor(B, true); | ||||||
977 | |||||||
978 | Deleted.insert(B); | ||||||
979 | MDT->eraseNode(B); | ||||||
980 | MFN->erase(B->getIterator()); | ||||||
981 | } | ||||||
982 | |||||||
983 | void HexagonEarlyIfConversion::eliminatePhis(MachineBasicBlock *B) { | ||||||
984 | LLVM_DEBUG(dbgs() << "Removing phi nodes from block " << PrintMB(B) << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("hexagon-eif")) { dbgs() << "Removing phi nodes from block " << PrintMB(B) << "\n"; } } while (false); | ||||||
985 | MachineBasicBlock::iterator I, NextI, NonPHI = B->getFirstNonPHI(); | ||||||
986 | for (I = B->begin(); I != NonPHI; I = NextI) { | ||||||
987 | NextI = std::next(I); | ||||||
988 | MachineInstr *PN = &*I; | ||||||
989 | assert(PN->getNumOperands() == 3 && "Invalid phi node")((PN->getNumOperands() == 3 && "Invalid phi node") ? static_cast<void> (0) : __assert_fail ("PN->getNumOperands() == 3 && \"Invalid phi node\"" , "/build/llvm-toolchain-snapshot-10~++20200110111110+a1cc19b5814/llvm/lib/Target/Hexagon/HexagonEarlyIfConv.cpp" , 989, __PRETTY_FUNCTION__)); | ||||||
990 | MachineOperand &UO = PN->getOperand(1); | ||||||
991 | Register UseR = UO.getReg(), UseSR = UO.getSubReg(); | ||||||
992 | Register DefR = PN->getOperand(0).getReg(); | ||||||
993 | unsigned NewR = UseR; | ||||||
994 | if (UseSR) { | ||||||
995 | // MRI.replaceVregUsesWith does not allow to update the subregister, | ||||||
996 | // so instead of doing the use-iteration here, create a copy into a | ||||||
997 | // "non-subregistered" register. | ||||||
998 | const DebugLoc &DL = PN->getDebugLoc(); | ||||||
999 | const TargetRegisterClass *RC = MRI->getRegClass(DefR); | ||||||
1000 | NewR = MRI->createVirtualRegister(RC); | ||||||
1001 | NonPHI = BuildMI(*B, NonPHI, DL, HII->get(TargetOpcode::COPY), NewR) | ||||||
1002 | .addReg(UseR, 0, UseSR); | ||||||
1003 | } | ||||||
1004 | MRI->replaceRegWith(DefR, NewR); | ||||||
1005 | B->erase(I); | ||||||
1006 | } | ||||||
1007 | } | ||||||
1008 | |||||||
1009 | void HexagonEarlyIfConversion::mergeBlocks(MachineBasicBlock *PredB, | ||||||
1010 | MachineBasicBlock *SuccB) { | ||||||
1011 | LLVM_DEBUG(dbgs() << "Merging blocks " << PrintMB(PredB) << " and "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("hexagon-eif")) { dbgs() << "Merging blocks " << PrintMB(PredB) << " and " << PrintMB(SuccB) << "\n"; } } while (false) | ||||||
1012 | << PrintMB(SuccB) << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("hexagon-eif")) { dbgs() << "Merging blocks " << PrintMB(PredB) << " and " << PrintMB(SuccB) << "\n"; } } while (false); | ||||||
1013 | bool TermOk = hasUncondBranch(SuccB); | ||||||
1014 | eliminatePhis(SuccB); | ||||||
1015 | HII->removeBranch(*PredB); | ||||||
1016 | PredB->removeSuccessor(SuccB); | ||||||
1017 | PredB->splice(PredB->end(), SuccB, SuccB->begin(), SuccB->end()); | ||||||
1018 | PredB->transferSuccessorsAndUpdatePHIs(SuccB); | ||||||
1019 | removeBlock(SuccB); | ||||||
1020 | if (!TermOk) | ||||||
1021 | PredB->updateTerminator(); | ||||||
1022 | } | ||||||
1023 | |||||||
1024 | void HexagonEarlyIfConversion::simplifyFlowGraph(const FlowPattern &FP) { | ||||||
1025 | if (FP.TrueB) | ||||||
1026 | removeBlock(FP.TrueB); | ||||||
1027 | if (FP.FalseB) | ||||||
1028 | removeBlock(FP.FalseB); | ||||||
1029 | |||||||
1030 | FP.SplitB->updateTerminator(); | ||||||
1031 | if (FP.SplitB->succ_size() != 1) | ||||||
1032 | return; | ||||||
1033 | |||||||
1034 | MachineBasicBlock *SB = *FP.SplitB->succ_begin(); | ||||||
1035 | if (SB->pred_size() != 1) | ||||||
1036 | return; | ||||||
1037 | |||||||
1038 | // By now, the split block has only one successor (SB), and SB has only | ||||||
1039 | // one predecessor. We can try to merge them. We will need to update ter- | ||||||
1040 | // minators in FP.Split+SB, and that requires working analyzeBranch, which | ||||||
1041 | // fails on Hexagon for blocks that have EH_LABELs. However, if SB ends | ||||||
1042 | // with an unconditional branch, we won't need to touch the terminators. | ||||||
1043 | if (!hasEHLabel(SB) || hasUncondBranch(SB)) | ||||||
1044 | mergeBlocks(FP.SplitB, SB); | ||||||
1045 | } | ||||||
1046 | |||||||
1047 | bool HexagonEarlyIfConversion::runOnMachineFunction(MachineFunction &MF) { | ||||||
1048 | if (skipFunction(MF.getFunction())) | ||||||
| |||||||
1049 | return false; | ||||||
1050 | |||||||
1051 | auto &ST = MF.getSubtarget<HexagonSubtarget>(); | ||||||
1052 | HII = ST.getInstrInfo(); | ||||||
1053 | TRI = ST.getRegisterInfo(); | ||||||
1054 | MFN = &MF; | ||||||
1055 | MRI = &MF.getRegInfo(); | ||||||
1056 | MDT = &getAnalysis<MachineDominatorTree>(); | ||||||
1057 | MLI = &getAnalysis<MachineLoopInfo>(); | ||||||
1058 | MBPI = EnableHexagonBP ? &getAnalysis<MachineBranchProbabilityInfo>() : | ||||||
1059 | nullptr; | ||||||
1060 | |||||||
1061 | Deleted.clear(); | ||||||
1062 | bool Changed = false; | ||||||
1063 | |||||||
1064 | for (MachineLoopInfo::iterator I = MLI->begin(), E = MLI->end(); I != E; ++I) | ||||||
1065 | Changed |= visitLoop(*I); | ||||||
1066 | Changed |= visitLoop(nullptr); | ||||||
1067 | |||||||
1068 | return Changed; | ||||||
1069 | } | ||||||
1070 | |||||||
1071 | //===----------------------------------------------------------------------===// | ||||||
1072 | // Public Constructor Functions | ||||||
1073 | //===----------------------------------------------------------------------===// | ||||||
1074 | FunctionPass *llvm::createHexagonEarlyIfConversion() { | ||||||
1075 | return new HexagonEarlyIfConversion(); | ||||||
1076 | } |
1 | //===- llvm/CodeGen/MachineInstrBundleIterator.h ----------------*- 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 | // Defines an iterator class that bundles MachineInstr. |
10 | // |
11 | //===----------------------------------------------------------------------===// |
12 | |
13 | #ifndef LLVM_CODEGEN_MACHINEINSTRBUNDLEITERATOR_H |
14 | #define LLVM_CODEGEN_MACHINEINSTRBUNDLEITERATOR_H |
15 | |
16 | #include "llvm/ADT/ilist.h" |
17 | #include "llvm/ADT/simple_ilist.h" |
18 | #include <cassert> |
19 | #include <iterator> |
20 | #include <type_traits> |
21 | |
22 | namespace llvm { |
23 | |
24 | template <class T, bool IsReverse> struct MachineInstrBundleIteratorTraits; |
25 | template <class T> struct MachineInstrBundleIteratorTraits<T, false> { |
26 | using list_type = simple_ilist<T, ilist_sentinel_tracking<true>>; |
27 | using instr_iterator = typename list_type::iterator; |
28 | using nonconst_instr_iterator = typename list_type::iterator; |
29 | using const_instr_iterator = typename list_type::const_iterator; |
30 | }; |
31 | template <class T> struct MachineInstrBundleIteratorTraits<T, true> { |
32 | using list_type = simple_ilist<T, ilist_sentinel_tracking<true>>; |
33 | using instr_iterator = typename list_type::reverse_iterator; |
34 | using nonconst_instr_iterator = typename list_type::reverse_iterator; |
35 | using const_instr_iterator = typename list_type::const_reverse_iterator; |
36 | }; |
37 | template <class T> struct MachineInstrBundleIteratorTraits<const T, false> { |
38 | using list_type = simple_ilist<T, ilist_sentinel_tracking<true>>; |
39 | using instr_iterator = typename list_type::const_iterator; |
40 | using nonconst_instr_iterator = typename list_type::iterator; |
41 | using const_instr_iterator = typename list_type::const_iterator; |
42 | }; |
43 | template <class T> struct MachineInstrBundleIteratorTraits<const T, true> { |
44 | using list_type = simple_ilist<T, ilist_sentinel_tracking<true>>; |
45 | using instr_iterator = typename list_type::const_reverse_iterator; |
46 | using nonconst_instr_iterator = typename list_type::reverse_iterator; |
47 | using const_instr_iterator = typename list_type::const_reverse_iterator; |
48 | }; |
49 | |
50 | template <bool IsReverse> struct MachineInstrBundleIteratorHelper; |
51 | template <> struct MachineInstrBundleIteratorHelper<false> { |
52 | /// Get the beginning of the current bundle. |
53 | template <class Iterator> static Iterator getBundleBegin(Iterator I) { |
54 | if (!I.isEnd()) |
55 | while (I->isBundledWithPred()) |
56 | --I; |
57 | return I; |
58 | } |
59 | |
60 | /// Get the final node of the current bundle. |
61 | template <class Iterator> static Iterator getBundleFinal(Iterator I) { |
62 | if (!I.isEnd()) |
63 | while (I->isBundledWithSucc()) |
64 | ++I; |
65 | return I; |
66 | } |
67 | |
68 | /// Increment forward ilist iterator. |
69 | template <class Iterator> static void increment(Iterator &I) { |
70 | I = std::next(getBundleFinal(I)); |
71 | } |
72 | |
73 | /// Decrement forward ilist iterator. |
74 | template <class Iterator> static void decrement(Iterator &I) { |
75 | I = getBundleBegin(std::prev(I)); |
76 | } |
77 | }; |
78 | |
79 | template <> struct MachineInstrBundleIteratorHelper<true> { |
80 | /// Get the beginning of the current bundle. |
81 | template <class Iterator> static Iterator getBundleBegin(Iterator I) { |
82 | return MachineInstrBundleIteratorHelper<false>::getBundleBegin( |
83 | I.getReverse()) |
84 | .getReverse(); |
85 | } |
86 | |
87 | /// Get the final node of the current bundle. |
88 | template <class Iterator> static Iterator getBundleFinal(Iterator I) { |
89 | return MachineInstrBundleIteratorHelper<false>::getBundleFinal( |
90 | I.getReverse()) |
91 | .getReverse(); |
92 | } |
93 | |
94 | /// Increment reverse ilist iterator. |
95 | template <class Iterator> static void increment(Iterator &I) { |
96 | I = getBundleBegin(std::next(I)); |
97 | } |
98 | |
99 | /// Decrement reverse ilist iterator. |
100 | template <class Iterator> static void decrement(Iterator &I) { |
101 | I = std::prev(getBundleFinal(I)); |
102 | } |
103 | }; |
104 | |
105 | /// MachineBasicBlock iterator that automatically skips over MIs that are |
106 | /// inside bundles (i.e. walk top level MIs only). |
107 | template <typename Ty, bool IsReverse = false> |
108 | class MachineInstrBundleIterator : MachineInstrBundleIteratorHelper<IsReverse> { |
109 | using Traits = MachineInstrBundleIteratorTraits<Ty, IsReverse>; |
110 | using instr_iterator = typename Traits::instr_iterator; |
111 | |
112 | instr_iterator MII; |
113 | |
114 | public: |
115 | using value_type = typename instr_iterator::value_type; |
116 | using difference_type = typename instr_iterator::difference_type; |
117 | using pointer = typename instr_iterator::pointer; |
118 | using reference = typename instr_iterator::reference; |
119 | using const_pointer = typename instr_iterator::const_pointer; |
120 | using const_reference = typename instr_iterator::const_reference; |
121 | using iterator_category = std::bidirectional_iterator_tag; |
122 | |
123 | private: |
124 | using nonconst_instr_iterator = typename Traits::nonconst_instr_iterator; |
125 | using const_instr_iterator = typename Traits::const_instr_iterator; |
126 | using nonconst_iterator = |
127 | MachineInstrBundleIterator<typename nonconst_instr_iterator::value_type, |
128 | IsReverse>; |
129 | using reverse_iterator = MachineInstrBundleIterator<Ty, !IsReverse>; |
130 | |
131 | public: |
132 | MachineInstrBundleIterator(instr_iterator MI) : MII(MI) { |
133 | assert((!MI.getNodePtr() || MI.isEnd() || !MI->isBundledWithPred()) &&(((!MI.getNodePtr() || MI.isEnd() || !MI->isBundledWithPred ()) && "It's not legal to initialize MachineInstrBundleIterator with a " "bundled MI") ? static_cast<void> (0) : __assert_fail ( "(!MI.getNodePtr() || MI.isEnd() || !MI->isBundledWithPred()) && \"It's not legal to initialize MachineInstrBundleIterator with a \" \"bundled MI\"" , "/build/llvm-toolchain-snapshot-10~++20200110111110+a1cc19b5814/llvm/include/llvm/CodeGen/MachineInstrBundleIterator.h" , 135, __PRETTY_FUNCTION__)) |
134 | "It's not legal to initialize MachineInstrBundleIterator with a "(((!MI.getNodePtr() || MI.isEnd() || !MI->isBundledWithPred ()) && "It's not legal to initialize MachineInstrBundleIterator with a " "bundled MI") ? static_cast<void> (0) : __assert_fail ( "(!MI.getNodePtr() || MI.isEnd() || !MI->isBundledWithPred()) && \"It's not legal to initialize MachineInstrBundleIterator with a \" \"bundled MI\"" , "/build/llvm-toolchain-snapshot-10~++20200110111110+a1cc19b5814/llvm/include/llvm/CodeGen/MachineInstrBundleIterator.h" , 135, __PRETTY_FUNCTION__)) |
135 | "bundled MI")(((!MI.getNodePtr() || MI.isEnd() || !MI->isBundledWithPred ()) && "It's not legal to initialize MachineInstrBundleIterator with a " "bundled MI") ? static_cast<void> (0) : __assert_fail ( "(!MI.getNodePtr() || MI.isEnd() || !MI->isBundledWithPred()) && \"It's not legal to initialize MachineInstrBundleIterator with a \" \"bundled MI\"" , "/build/llvm-toolchain-snapshot-10~++20200110111110+a1cc19b5814/llvm/include/llvm/CodeGen/MachineInstrBundleIterator.h" , 135, __PRETTY_FUNCTION__)); |
136 | } |
137 | |
138 | MachineInstrBundleIterator(reference MI) : MII(MI) { |
139 | assert(!MI.isBundledWithPred() && "It's not legal to initialize "((!MI.isBundledWithPred() && "It's not legal to initialize " "MachineInstrBundleIterator with a " "bundled MI") ? static_cast <void> (0) : __assert_fail ("!MI.isBundledWithPred() && \"It's not legal to initialize \" \"MachineInstrBundleIterator with a \" \"bundled MI\"" , "/build/llvm-toolchain-snapshot-10~++20200110111110+a1cc19b5814/llvm/include/llvm/CodeGen/MachineInstrBundleIterator.h" , 141, __PRETTY_FUNCTION__)) |
140 | "MachineInstrBundleIterator with a "((!MI.isBundledWithPred() && "It's not legal to initialize " "MachineInstrBundleIterator with a " "bundled MI") ? static_cast <void> (0) : __assert_fail ("!MI.isBundledWithPred() && \"It's not legal to initialize \" \"MachineInstrBundleIterator with a \" \"bundled MI\"" , "/build/llvm-toolchain-snapshot-10~++20200110111110+a1cc19b5814/llvm/include/llvm/CodeGen/MachineInstrBundleIterator.h" , 141, __PRETTY_FUNCTION__)) |
141 | "bundled MI")((!MI.isBundledWithPred() && "It's not legal to initialize " "MachineInstrBundleIterator with a " "bundled MI") ? static_cast <void> (0) : __assert_fail ("!MI.isBundledWithPred() && \"It's not legal to initialize \" \"MachineInstrBundleIterator with a \" \"bundled MI\"" , "/build/llvm-toolchain-snapshot-10~++20200110111110+a1cc19b5814/llvm/include/llvm/CodeGen/MachineInstrBundleIterator.h" , 141, __PRETTY_FUNCTION__)); |
142 | } |
143 | |
144 | MachineInstrBundleIterator(pointer MI) : MII(MI) { |
145 | // FIXME: This conversion should be explicit. |
146 | assert((!MI || !MI->isBundledWithPred()) && "It's not legal to initialize "(((!MI || !MI->isBundledWithPred()) && "It's not legal to initialize " "MachineInstrBundleIterator " "with a bundled MI") ? static_cast <void> (0) : __assert_fail ("(!MI || !MI->isBundledWithPred()) && \"It's not legal to initialize \" \"MachineInstrBundleIterator \" \"with a bundled MI\"" , "/build/llvm-toolchain-snapshot-10~++20200110111110+a1cc19b5814/llvm/include/llvm/CodeGen/MachineInstrBundleIterator.h" , 148, __PRETTY_FUNCTION__)) |
147 | "MachineInstrBundleIterator "(((!MI || !MI->isBundledWithPred()) && "It's not legal to initialize " "MachineInstrBundleIterator " "with a bundled MI") ? static_cast <void> (0) : __assert_fail ("(!MI || !MI->isBundledWithPred()) && \"It's not legal to initialize \" \"MachineInstrBundleIterator \" \"with a bundled MI\"" , "/build/llvm-toolchain-snapshot-10~++20200110111110+a1cc19b5814/llvm/include/llvm/CodeGen/MachineInstrBundleIterator.h" , 148, __PRETTY_FUNCTION__)) |
148 | "with a bundled MI")(((!MI || !MI->isBundledWithPred()) && "It's not legal to initialize " "MachineInstrBundleIterator " "with a bundled MI") ? static_cast <void> (0) : __assert_fail ("(!MI || !MI->isBundledWithPred()) && \"It's not legal to initialize \" \"MachineInstrBundleIterator \" \"with a bundled MI\"" , "/build/llvm-toolchain-snapshot-10~++20200110111110+a1cc19b5814/llvm/include/llvm/CodeGen/MachineInstrBundleIterator.h" , 148, __PRETTY_FUNCTION__)); |
149 | } |
150 | |
151 | // Template allows conversion from const to nonconst. |
152 | template <class OtherTy> |
153 | MachineInstrBundleIterator( |
154 | const MachineInstrBundleIterator<OtherTy, IsReverse> &I, |
155 | typename std::enable_if<std::is_convertible<OtherTy *, Ty *>::value, |
156 | void *>::type = nullptr) |
157 | : MII(I.getInstrIterator()) {} |
158 | |
159 | MachineInstrBundleIterator() : MII(nullptr) {} |
160 | |
161 | /// Explicit conversion between forward/reverse iterators. |
162 | /// |
163 | /// Translate between forward and reverse iterators without changing range |
164 | /// boundaries. The resulting iterator will dereference (and have a handle) |
165 | /// to the previous node, which is somewhat unexpected; but converting the |
166 | /// two endpoints in a range will give the same range in reverse. |
167 | /// |
168 | /// This matches std::reverse_iterator conversions. |
169 | explicit MachineInstrBundleIterator( |
170 | const MachineInstrBundleIterator<Ty, !IsReverse> &I) |
171 | : MachineInstrBundleIterator(++I.getReverse()) {} |
172 | |
173 | /// Get the bundle iterator for the given instruction's bundle. |
174 | static MachineInstrBundleIterator getAtBundleBegin(instr_iterator MI) { |
175 | return MachineInstrBundleIteratorHelper<IsReverse>::getBundleBegin(MI); |
176 | } |
177 | |
178 | reference operator*() const { return *MII; } |
179 | pointer operator->() const { return &operator*(); } |
180 | |
181 | /// Check for null. |
182 | bool isValid() const { return MII.getNodePtr(); } |
183 | |
184 | friend bool operator==(const MachineInstrBundleIterator &L, |
185 | const MachineInstrBundleIterator &R) { |
186 | return L.MII == R.MII; |
187 | } |
188 | friend bool operator==(const MachineInstrBundleIterator &L, |
189 | const const_instr_iterator &R) { |
190 | return L.MII == R; // Avoid assertion about validity of R. |
191 | } |
192 | friend bool operator==(const const_instr_iterator &L, |
193 | const MachineInstrBundleIterator &R) { |
194 | return L == R.MII; // Avoid assertion about validity of L. |
195 | } |
196 | friend bool operator==(const MachineInstrBundleIterator &L, |
197 | const nonconst_instr_iterator &R) { |
198 | return L.MII == R; // Avoid assertion about validity of R. |
199 | } |
200 | friend bool operator==(const nonconst_instr_iterator &L, |
201 | const MachineInstrBundleIterator &R) { |
202 | return L == R.MII; // Avoid assertion about validity of L. |
203 | } |
204 | friend bool operator==(const MachineInstrBundleIterator &L, const_pointer R) { |
205 | return L == const_instr_iterator(R); // Avoid assertion about validity of R. |
206 | } |
207 | friend bool operator==(const_pointer L, const MachineInstrBundleIterator &R) { |
208 | return const_instr_iterator(L) == R; // Avoid assertion about validity of L. |
209 | } |
210 | friend bool operator==(const MachineInstrBundleIterator &L, |
211 | const_reference R) { |
212 | return L == &R; // Avoid assertion about validity of R. |
213 | } |
214 | friend bool operator==(const_reference L, |
215 | const MachineInstrBundleIterator &R) { |
216 | return &L == R; // Avoid assertion about validity of L. |
217 | } |
218 | |
219 | friend bool operator!=(const MachineInstrBundleIterator &L, |
220 | const MachineInstrBundleIterator &R) { |
221 | return !(L == R); |
222 | } |
223 | friend bool operator!=(const MachineInstrBundleIterator &L, |
224 | const const_instr_iterator &R) { |
225 | return !(L == R); |
226 | } |
227 | friend bool operator!=(const const_instr_iterator &L, |
228 | const MachineInstrBundleIterator &R) { |
229 | return !(L == R); |
230 | } |
231 | friend bool operator!=(const MachineInstrBundleIterator &L, |
232 | const nonconst_instr_iterator &R) { |
233 | return !(L == R); |
234 | } |
235 | friend bool operator!=(const nonconst_instr_iterator &L, |
236 | const MachineInstrBundleIterator &R) { |
237 | return !(L == R); |
238 | } |
239 | friend bool operator!=(const MachineInstrBundleIterator &L, const_pointer R) { |
240 | return !(L == R); |
241 | } |
242 | friend bool operator!=(const_pointer L, const MachineInstrBundleIterator &R) { |
243 | return !(L == R); |
244 | } |
245 | friend bool operator!=(const MachineInstrBundleIterator &L, |
246 | const_reference R) { |
247 | return !(L == R); |
248 | } |
249 | friend bool operator!=(const_reference L, |
250 | const MachineInstrBundleIterator &R) { |
251 | return !(L == R); |
252 | } |
253 | |
254 | // Increment and decrement operators... |
255 | MachineInstrBundleIterator &operator--() { |
256 | this->decrement(MII); |
257 | return *this; |
258 | } |
259 | MachineInstrBundleIterator &operator++() { |
260 | this->increment(MII); |
261 | return *this; |
262 | } |
263 | MachineInstrBundleIterator operator--(int) { |
264 | MachineInstrBundleIterator Temp = *this; |
265 | --*this; |
266 | return Temp; |
267 | } |
268 | MachineInstrBundleIterator operator++(int) { |
269 | MachineInstrBundleIterator Temp = *this; |
270 | ++*this; |
271 | return Temp; |
272 | } |
273 | |
274 | instr_iterator getInstrIterator() const { return MII; } |
275 | |
276 | nonconst_iterator getNonConstIterator() const { return MII.getNonConst(); } |
277 | |
278 | /// Get a reverse iterator to the same node. |
279 | /// |
280 | /// Gives a reverse iterator that will dereference (and have a handle) to the |
281 | /// same node. Converting the endpoint iterators in a range will give a |
282 | /// different range; for range operations, use the explicit conversions. |
283 | reverse_iterator getReverse() const { return MII.getReverse(); } |
284 | }; |
285 | |
286 | } // end namespace llvm |
287 | |
288 | #endif // LLVM_CODEGEN_MACHINEINSTRBUNDLEITERATOR_H |
1 | //===- llvm/ADT/ilist_iterator.h - Intrusive List Iterator ------*- 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_ADT_ILIST_ITERATOR_H |
10 | #define LLVM_ADT_ILIST_ITERATOR_H |
11 | |
12 | #include "llvm/ADT/ilist_node.h" |
13 | #include <cassert> |
14 | #include <cstddef> |
15 | #include <iterator> |
16 | #include <type_traits> |
17 | |
18 | namespace llvm { |
19 | |
20 | namespace ilist_detail { |
21 | |
22 | /// Find const-correct node types. |
23 | template <class OptionsT, bool IsConst> struct IteratorTraits; |
24 | template <class OptionsT> struct IteratorTraits<OptionsT, false> { |
25 | using value_type = typename OptionsT::value_type; |
26 | using pointer = typename OptionsT::pointer; |
27 | using reference = typename OptionsT::reference; |
28 | using node_pointer = ilist_node_impl<OptionsT> *; |
29 | using node_reference = ilist_node_impl<OptionsT> &; |
30 | }; |
31 | template <class OptionsT> struct IteratorTraits<OptionsT, true> { |
32 | using value_type = const typename OptionsT::value_type; |
33 | using pointer = typename OptionsT::const_pointer; |
34 | using reference = typename OptionsT::const_reference; |
35 | using node_pointer = const ilist_node_impl<OptionsT> *; |
36 | using node_reference = const ilist_node_impl<OptionsT> &; |
37 | }; |
38 | |
39 | template <bool IsReverse> struct IteratorHelper; |
40 | template <> struct IteratorHelper<false> : ilist_detail::NodeAccess { |
41 | using Access = ilist_detail::NodeAccess; |
42 | |
43 | template <class T> static void increment(T *&I) { I = Access::getNext(*I); } |
44 | template <class T> static void decrement(T *&I) { I = Access::getPrev(*I); } |
45 | }; |
46 | template <> struct IteratorHelper<true> : ilist_detail::NodeAccess { |
47 | using Access = ilist_detail::NodeAccess; |
48 | |
49 | template <class T> static void increment(T *&I) { I = Access::getPrev(*I); } |
50 | template <class T> static void decrement(T *&I) { I = Access::getNext(*I); } |
51 | }; |
52 | |
53 | } // end namespace ilist_detail |
54 | |
55 | /// Iterator for intrusive lists based on ilist_node. |
56 | template <class OptionsT, bool IsReverse, bool IsConst> |
57 | class ilist_iterator : ilist_detail::SpecificNodeAccess<OptionsT> { |
58 | friend ilist_iterator<OptionsT, IsReverse, !IsConst>; |
59 | friend ilist_iterator<OptionsT, !IsReverse, IsConst>; |
60 | friend ilist_iterator<OptionsT, !IsReverse, !IsConst>; |
61 | |
62 | using Traits = ilist_detail::IteratorTraits<OptionsT, IsConst>; |
63 | using Access = ilist_detail::SpecificNodeAccess<OptionsT>; |
64 | |
65 | public: |
66 | using value_type = typename Traits::value_type; |
67 | using pointer = typename Traits::pointer; |
68 | using reference = typename Traits::reference; |
69 | using difference_type = ptrdiff_t; |
70 | using iterator_category = std::bidirectional_iterator_tag; |
71 | using const_pointer = typename OptionsT::const_pointer; |
72 | using const_reference = typename OptionsT::const_reference; |
73 | |
74 | private: |
75 | using node_pointer = typename Traits::node_pointer; |
76 | using node_reference = typename Traits::node_reference; |
77 | |
78 | node_pointer NodePtr = nullptr; |
79 | |
80 | public: |
81 | /// Create from an ilist_node. |
82 | explicit ilist_iterator(node_reference N) : NodePtr(&N) {} |
83 | |
84 | explicit ilist_iterator(pointer NP) : NodePtr(Access::getNodePtr(NP)) {} |
85 | explicit ilist_iterator(reference NR) : NodePtr(Access::getNodePtr(&NR)) {} |
86 | ilist_iterator() = default; |
87 | |
88 | // This is templated so that we can allow constructing a const iterator from |
89 | // a nonconst iterator... |
90 | template <bool RHSIsConst> |
91 | ilist_iterator( |
92 | const ilist_iterator<OptionsT, IsReverse, RHSIsConst> &RHS, |
93 | typename std::enable_if<IsConst || !RHSIsConst, void *>::type = nullptr) |
94 | : NodePtr(RHS.NodePtr) {} |
95 | |
96 | // This is templated so that we can allow assigning to a const iterator from |
97 | // a nonconst iterator... |
98 | template <bool RHSIsConst> |
99 | typename std::enable_if<IsConst || !RHSIsConst, ilist_iterator &>::type |
100 | operator=(const ilist_iterator<OptionsT, IsReverse, RHSIsConst> &RHS) { |
101 | NodePtr = RHS.NodePtr; |
102 | return *this; |
103 | } |
104 | |
105 | /// Explicit conversion between forward/reverse iterators. |
106 | /// |
107 | /// Translate between forward and reverse iterators without changing range |
108 | /// boundaries. The resulting iterator will dereference (and have a handle) |
109 | /// to the previous node, which is somewhat unexpected; but converting the |
110 | /// two endpoints in a range will give the same range in reverse. |
111 | /// |
112 | /// This matches std::reverse_iterator conversions. |
113 | explicit ilist_iterator( |
114 | const ilist_iterator<OptionsT, !IsReverse, IsConst> &RHS) |
115 | : ilist_iterator(++RHS.getReverse()) {} |
116 | |
117 | /// Get a reverse iterator to the same node. |
118 | /// |
119 | /// Gives a reverse iterator that will dereference (and have a handle) to the |
120 | /// same node. Converting the endpoint iterators in a range will give a |
121 | /// different range; for range operations, use the explicit conversions. |
122 | ilist_iterator<OptionsT, !IsReverse, IsConst> getReverse() const { |
123 | if (NodePtr) |
124 | return ilist_iterator<OptionsT, !IsReverse, IsConst>(*NodePtr); |
125 | return ilist_iterator<OptionsT, !IsReverse, IsConst>(); |
126 | } |
127 | |
128 | /// Const-cast. |
129 | ilist_iterator<OptionsT, IsReverse, false> getNonConst() const { |
130 | if (NodePtr) |
131 | return ilist_iterator<OptionsT, IsReverse, false>( |
132 | const_cast<typename ilist_iterator<OptionsT, IsReverse, |
133 | false>::node_reference>(*NodePtr)); |
134 | return ilist_iterator<OptionsT, IsReverse, false>(); |
135 | } |
136 | |
137 | // Accessors... |
138 | reference operator*() const { |
139 | assert(!NodePtr->isKnownSentinel())((!NodePtr->isKnownSentinel()) ? static_cast<void> ( 0) : __assert_fail ("!NodePtr->isKnownSentinel()", "/build/llvm-toolchain-snapshot-10~++20200110111110+a1cc19b5814/llvm/include/llvm/ADT/ilist_iterator.h" , 139, __PRETTY_FUNCTION__)); |
140 | return *Access::getValuePtr(NodePtr); |
141 | } |
142 | pointer operator->() const { return &operator*(); } |
143 | |
144 | // Comparison operators |
145 | friend bool operator==(const ilist_iterator &LHS, const ilist_iterator &RHS) { |
146 | return LHS.NodePtr == RHS.NodePtr; |
147 | } |
148 | friend bool operator!=(const ilist_iterator &LHS, const ilist_iterator &RHS) { |
149 | return LHS.NodePtr != RHS.NodePtr; |
150 | } |
151 | |
152 | // Increment and decrement operators... |
153 | ilist_iterator &operator--() { |
154 | NodePtr = IsReverse ? NodePtr->getNext() : NodePtr->getPrev(); |
155 | return *this; |
156 | } |
157 | ilist_iterator &operator++() { |
158 | NodePtr = IsReverse ? NodePtr->getPrev() : NodePtr->getNext(); |
159 | return *this; |
160 | } |
161 | ilist_iterator operator--(int) { |
162 | ilist_iterator tmp = *this; |
163 | --*this; |
164 | return tmp; |
165 | } |
166 | ilist_iterator operator++(int) { |
167 | ilist_iterator tmp = *this; |
168 | ++*this; |
169 | return tmp; |
170 | } |
171 | |
172 | /// Get the underlying ilist_node. |
173 | node_pointer getNodePtr() const { return static_cast<node_pointer>(NodePtr); } |
174 | |
175 | /// Check for end. Only valid if ilist_sentinel_tracking<true>. |
176 | bool isEnd() const { return NodePtr ? NodePtr->isSentinel() : false; } |
177 | }; |
178 | |
179 | template <typename From> struct simplify_type; |
180 | |
181 | /// Allow ilist_iterators to convert into pointers to a node automatically when |
182 | /// used by the dyn_cast, cast, isa mechanisms... |
183 | /// |
184 | /// FIXME: remove this, since there is no implicit conversion to NodeTy. |
185 | template <class OptionsT, bool IsConst> |
186 | struct simplify_type<ilist_iterator<OptionsT, false, IsConst>> { |
187 | using iterator = ilist_iterator<OptionsT, false, IsConst>; |
188 | using SimpleType = typename iterator::pointer; |
189 | |
190 | static SimpleType getSimplifiedValue(const iterator &Node) { return &*Node; } |
191 | }; |
192 | template <class OptionsT, bool IsConst> |
193 | struct simplify_type<const ilist_iterator<OptionsT, false, IsConst>> |
194 | : simplify_type<ilist_iterator<OptionsT, false, IsConst>> {}; |
195 | |
196 | } // end namespace llvm |
197 | |
198 | #endif // LLVM_ADT_ILIST_ITERATOR_H |