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