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