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