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