contrib/llvm/lib/Target/Hexagon/HexagonEarlyIfConv.cpp

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