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