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 //         %40 = L2_loadrub_io killed %39, 1
  29 //         %41 = S2_tstbit_i killed %40, 0
  30 //         J2_jumpt killed %41, <%bb.5>, implicit dead %pc
  31 //         J2_jump <%bb.4>, implicit dead %pc
  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 //         %11 = A2_addp %6, %10
  37 //         S2_storerd_io %32, 16, %11
  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 //         %12 = PHI %6, <%bb.3>, %11, <%bb.4>
  43 //         %13 = A2_addp %7, %12
  44 //         %42 = C2_cmpeqi %9, 10
  45 //         J2_jumpf killed %42, <%bb.3>, implicit dead %pc
  46 //         J2_jump <%bb.6>, implicit dead %pc
  47 //     Successors according to CFG: %bb.6(4) %bb.3(124)
  48 //
  49 // would become:
  50 //
  51 //         %40 = L2_loadrub_io killed %39, 1
  52 //         %41 = S2_tstbit_i killed %40, 0
  53 // spec->  %11 = A2_addp %6, %10
  54 // pred->  S2_pstorerdf_io %41, %32, 16, %11
  55 //         %46 = PS_pselect %41, %6, %11
  56 //         %13 = A2_addp %7, %46
  57 //         %42 = C2_cmpeqi %9, 10
  58 //         J2_jumpf killed %42, <%bb.3>, implicit dead %pc
  59 //         J2_jump <%bb.6>, implicit dead %pc
  60 //     Successors according to CFG: %bb.6 %bb.3
  61
  62 #include "Hexagon.h"
  63 #include "HexagonInstrInfo.h"
  64 #include "HexagonSubtarget.h"
  65 #include "llvm/ADT/DenseSet.h"
  66 #include "llvm/ADT/SmallVector.h"
  67 #include "llvm/ADT/StringRef.h"
  68 #include "llvm/ADT/iterator_range.h"
  69 #include "llvm/CodeGen/MachineBasicBlock.h"
  70 #include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
  71 #include "llvm/CodeGen/MachineDominators.h"
  72 #include "llvm/CodeGen/MachineFunction.h"
  73 #include "llvm/CodeGen/MachineFunctionPass.h"
  74 #include "llvm/CodeGen/MachineInstr.h"
  75 #include "llvm/CodeGen/MachineInstrBuilder.h"
  76 #include "llvm/CodeGen/MachineLoopInfo.h"
  77 #include "llvm/CodeGen/MachineOperand.h"
  78 #include "llvm/CodeGen/MachineRegisterInfo.h"
  79 #include "llvm/CodeGen/TargetRegisterInfo.h"
  80 #include "llvm/IR/DebugLoc.h"
  81 #include "llvm/Pass.h"
  82 #include "llvm/Support/BranchProbability.h"
  83 #include "llvm/Support/CommandLine.h"
  84 #include "llvm/Support/Compiler.h"
  85 #include "llvm/Support/Debug.h"
  86 #include "llvm/Support/ErrorHandling.h"
  87 #include "llvm/Support/raw_ostream.h"
  88 #include <cassert>
  89 #include <iterator>
  90
  91 #define DEBUG_TYPE "hexagon-eif"
  92
  93 using namespace llvm;
  94
  95 namespace llvm {
  96
  97   FunctionPass *createHexagonEarlyIfConversion();
  98   void initializeHexagonEarlyIfConversionPass(PassRegistry& Registry);
  99
 100 } // end namespace llvm
 101
 102 static cl::opt<bool> EnableHexagonBP("enable-hexagon-br-prob", cl::Hidden,
 103   cl::init(true), cl::desc("Enable branch probability info"));
 104 static cl::opt<unsigned> SizeLimit("eif-limit", cl::init(6), cl::Hidden,
 105   cl::desc("Size limit in Hexagon early if-conversion"));
 106 static cl::opt<bool> SkipExitBranches("eif-no-loop-exit", cl::init(false),
 107   cl::Hidden, cl::desc("Do not convert branches that may exit the loop"));
 108
 109 namespace {
 110
 111   struct PrintMB {
 112     PrintMB(const MachineBasicBlock *B) : MB(B) {}
 113
 114     const MachineBasicBlock *MB;
 115   };
 116   raw_ostream &operator<< (raw_ostream &OS, const PrintMB &P) {
 117     if (!P.MB)
 118       return OS << "<none>";
 119     return OS << '#' << P.MB->getNumber();
 120   }
 121
 122   struct FlowPattern {
 123     FlowPattern() = default;
 124     FlowPattern(MachineBasicBlock *B, unsigned PR, MachineBasicBlock *TB,
 125           MachineBasicBlock *FB, MachineBasicBlock *JB)
 126       : SplitB(B), TrueB(TB), FalseB(FB), JoinB(JB), PredR(PR) {}
 127
 128     MachineBasicBlock *SplitB = nullptr;
 129     MachineBasicBlock *TrueB = nullptr;
 130     MachineBasicBlock *FalseB = nullptr;
 131     MachineBasicBlock *JoinB = nullptr;
 132     unsigned PredR = 0;
 133   };
 134
 135   struct PrintFP {
 136     PrintFP(const FlowPattern &P, const TargetRegisterInfo &T)
 137       : FP(P), TRI(T) {}
 138
 139     const FlowPattern &FP;
 140     const TargetRegisterInfo &TRI;
 141     friend raw_ostream &operator<< (raw_ostream &OS, const PrintFP &P);
 142   };
 143   raw_ostream &operator<<(raw_ostream &OS,
 144                           const PrintFP &P) LLVM_ATTRIBUTE_UNUSED;
 145   raw_ostream &operator<<(raw_ostream &OS, const PrintFP &P) {
 146     OS << "{ SplitB:" << PrintMB(P.FP.SplitB)
 147        << ", PredR:" << printReg(P.FP.PredR, &P.TRI)
 148        << ", TrueB:" << PrintMB(P.FP.TrueB)
 149        << ", FalseB:" << PrintMB(P.FP.FalseB)
 150        << ", JoinB:" << PrintMB(P.FP.JoinB) << " }";
 151     return OS;
 152   }
 153
 154   class HexagonEarlyIfConversion : public MachineFunctionPass {
 155   public:
 156     static char ID;
 157
 158     HexagonEarlyIfConversion() : MachineFunctionPass(ID) {}
 159
 160     StringRef getPassName() const override {
 161       return "Hexagon early if conversion";
 162     }
 163
 164     void getAnalysisUsage(AnalysisUsage &AU) const override {
 165       AU.addRequired<MachineBranchProbabilityInfo>();
 166       AU.addRequired<MachineDominatorTree>();
 167       AU.addPreserved<MachineDominatorTree>();
 168       AU.addRequired<MachineLoopInfo>();
 169       MachineFunctionPass::getAnalysisUsage(AU);
 170     }
 171
 172     bool runOnMachineFunction(MachineFunction &MF) override;
 173
 174   private:
 175     using BlockSetType = DenseSet<MachineBasicBlock *>;
 176
 177     bool isPreheader(const MachineBasicBlock *B) const;
 178     bool matchFlowPattern(MachineBasicBlock *B, MachineLoop *L,
 179           FlowPattern &FP);
 180     bool visitBlock(MachineBasicBlock *B, MachineLoop *L);
 181     bool visitLoop(MachineLoop *L);
 182
 183     bool hasEHLabel(const MachineBasicBlock *B) const;
 184     bool hasUncondBranch(const MachineBasicBlock *B) const;
 185     bool isValidCandidate(const MachineBasicBlock *B) const;
 186     bool usesUndefVReg(const MachineInstr *MI) const;
 187     bool isValid(const FlowPattern &FP) const;
 188     unsigned countPredicateDefs(const MachineBasicBlock *B) const;
 189     unsigned computePhiCost(const MachineBasicBlock *B,
 190           const FlowPattern &FP) const;
 191     bool isProfitable(const FlowPattern &FP) const;
 192     bool isPredicableStore(const MachineInstr *MI) const;
 193     bool isSafeToSpeculate(const MachineInstr *MI) const;
 194     bool isPredicate(unsigned R) const;
 195
 196     unsigned getCondStoreOpcode(unsigned Opc, bool IfTrue) const;
 197     void predicateInstr(MachineBasicBlock *ToB, MachineBasicBlock::iterator At,
 198           MachineInstr *MI, unsigned PredR, bool IfTrue);
 199     void predicateBlockNB(MachineBasicBlock *ToB,
 200           MachineBasicBlock::iterator At, MachineBasicBlock *FromB,
 201           unsigned PredR, bool IfTrue);
 202
 203     unsigned buildMux(MachineBasicBlock *B, MachineBasicBlock::iterator At,
 204           const TargetRegisterClass *DRC, unsigned PredR, unsigned TR,
 205           unsigned TSR, unsigned FR, unsigned FSR);
 206     void updatePhiNodes(MachineBasicBlock *WhereB, const FlowPattern &FP);
 207     void convert(const FlowPattern &FP);
 208
 209     void removeBlock(MachineBasicBlock *B);
 210     void eliminatePhis(MachineBasicBlock *B);
 211     void mergeBlocks(MachineBasicBlock *PredB, MachineBasicBlock *SuccB);
 212     void simplifyFlowGraph(const FlowPattern &FP);
 213
 214     const HexagonInstrInfo *HII = nullptr;
 215     const TargetRegisterInfo *TRI = nullptr;
 216     MachineFunction *MFN = nullptr;
 217     MachineRegisterInfo *MRI = nullptr;
 218     MachineDominatorTree *MDT = nullptr;
 219     MachineLoopInfo *MLI = nullptr;
 220     BlockSetType Deleted;
 221     const MachineBranchProbabilityInfo *MBPI;
 222   };
 223
 224 } // end anonymous namespace
 225
 226 char HexagonEarlyIfConversion::ID = 0;
 227
 228 INITIALIZE_PASS(HexagonEarlyIfConversion, "hexagon-early-if",
 229   "Hexagon early if conversion", false, false)
 230
 231 bool HexagonEarlyIfConversion::isPreheader(const MachineBasicBlock *B) const {
 232   if (B->succ_size() != 1)
 233     return false;
 234   MachineBasicBlock *SB = *B->succ_begin();
 235   MachineLoop *L = MLI->getLoopFor(SB);
 236   return L && SB == L->getHeader() && MDT->dominates(B, SB);
 237 }
 238
 239 bool HexagonEarlyIfConversion::matchFlowPattern(MachineBasicBlock *B,
 240     MachineLoop *L, FlowPattern &FP) {
 241   LLVM_DEBUG(dbgs() << "Checking flow pattern at " << printMBBReference(*B)
 242                     << "\n");
 243
 244   // Interested only in conditional branches, no .new, no new-value, etc.
 245   // Check the terminators directly, it's easier than handling all responses
 246   // from analyzeBranch.
 247   MachineBasicBlock *TB = nullptr, *FB = nullptr;
 248   MachineBasicBlock::const_iterator T1I = B->getFirstTerminator();
 249   if (T1I == B->end())
 250     return false;
 251   unsigned Opc = T1I->getOpcode();
 252   if (Opc != Hexagon::J2_jumpt && Opc != Hexagon::J2_jumpf)
 253     return false;
 254   unsigned PredR = T1I->getOperand(0).getReg();
 255
 256   // Get the layout successor, or 0 if B does not have one.
 257   MachineFunction::iterator NextBI = std::next(MachineFunction::iterator(B));
 258   MachineBasicBlock *NextB = (NextBI != MFN->end()) ? &*NextBI : nullptr;
 259
 260   MachineBasicBlock *T1B = T1I->getOperand(1).getMBB();
 261   MachineBasicBlock::const_iterator T2I = std::next(T1I);
 262   // The second terminator should be an unconditional branch.
 263   assert(T2I == B->end() || T2I->getOpcode() == Hexagon::J2_jump);
 264   MachineBasicBlock *T2B = (T2I == B->end()) ? NextB
 265                                              : T2I->getOperand(0).getMBB();
 266   if (T1B == T2B) {
 267     // XXX merge if T1B == NextB, or convert branch to unconditional.
 268     // mark as diamond with both sides equal?
 269     return false;
 270   }
 271
 272   // Record the true/false blocks in such a way that "true" means "if (PredR)",
 273   // and "false" means "if (!PredR)".
 274   if (Opc == Hexagon::J2_jumpt)
 275     TB = T1B, FB = T2B;
 276   else
 277     TB = T2B, FB = T1B;
 278
 279   if (!MDT->properlyDominates(B, TB) || !MDT->properlyDominates(B, FB))
 280     return false;
 281
 282   // Detect triangle first. In case of a triangle, one of the blocks TB/FB
 283   // can fall through into the other, in other words, it will be executed
 284   // in both cases. We only want to predicate the block that is executed
 285   // conditionally.
 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(TB) == L);
 295   bool FOk = (FNP == 1 && FNS == 1 && MLI->getLoopFor(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(TB) != MLI->getLoopFor(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(TB)) || (FB && isPreheader(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.
 341 bool 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.
 350 bool 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
 361 bool 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_size() == 0)
 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) && !IsJMP && !isSafeToSpeculate(&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       unsigned R = MO.getReg();
 389       if (!TargetRegisterInfo::isVirtualRegister(R))
 390         continue;
 391       if (!isPredicate(R))
 392         continue;
 393       for (auto U = MRI->use_begin(R); U != MRI->use_end(); ++U)
 394         if (U->getParent()->isPHI())
 395           return false;
 396     }
 397   }
 398   return true;
 399 }
 400
 401 bool HexagonEarlyIfConversion::usesUndefVReg(const MachineInstr *MI) const {
 402   for (const MachineOperand &MO : MI->operands()) {
 403     if (!MO.isReg() || !MO.isUse())
 404       continue;
 405     unsigned R = MO.getReg();
 406     if (!TargetRegisterInfo::isVirtualRegister(R))
 407       continue;
 408     const MachineInstr *DefI = MRI->getVRegDef(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
 417 bool HexagonEarlyIfConversion::isValid(const FlowPattern &FP) const {
 418   if (hasEHLabel(FP.SplitB))  // KLUDGE: see function definition
 419     return false;
 420   if (FP.TrueB && !isValidCandidate(FP.TrueB))
 421     return false;
 422   if (FP.FalseB && !isValidCandidate(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))
 440         return false;
 441       unsigned DefR = MI.getOperand(0).getReg();
 442       if (isPredicate(DefR))
 443         return false;
 444     }
 445   }
 446   return true;
 447 }
 448
 449 unsigned 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+1).getMBB();
 465       if (BB == FP.SplitB || BB == FP.TrueB || BB == FP.FalseB)
 466         Inc.push_back(i);
 467     }
 468     assert(Inc.size() <= 2);
 469     if (Inc.size() < 2)
 470       continue;
 471
 472     const MachineOperand &RA = MI.getOperand(1);
 473     const MachineOperand &RB = MI.getOperand(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(RA.getReg());
 481     const MachineInstr *Def3 = MRI->getVRegDef(RB.getReg());
 482     if (!HII->isPredicable(*Def1) || !HII->isPredicable(*Def3))
 483       Cost++;
 484   }
 485   return Cost;
 486 }
 487
 488 unsigned 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       unsigned R = MO.getReg();
 496       if (!TargetRegisterInfo::isVirtualRegister(R))
 497         continue;
 498       if (isPredicate(R))
 499         PredDefs++;
 500     }
 501   }
 502   return PredDefs;
 503 }
 504
 505 bool 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(FP.SplitB, FP.TrueB) < JumpProb ||
 510        MBPI->getEdgeProbability(FP.SplitB, FP.TrueB) > Prob))
 511     return false;
 512
 513   if (MBPI && !FP.TrueB && FP.FalseB &&
 514       (MBPI->getEdgeProbability(FP.SplitB, FP.FalseB) < JumpProb ||
 515        MBPI->getEdgeProbability(FP.SplitB, 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(FP.SplitB, FP.TrueB) > Prob)
 522         return false;
 523       if (MBPI->getEdgeProbability(FP.SplitB, 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(B->begin(), B->getFirstTerminator(),
 546                                [](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(FP.SplitB);
 569   if (FP.JoinB) {
 570     TotalPh = computePhiCost(FP.JoinB, FP);
 571     PredDefs += countPredicateDefs(FP.JoinB);
 572   } else {
 573     if (FP.TrueB && FP.TrueB->succ_size() > 0) {
 574       MachineBasicBlock *SB = *FP.TrueB->succ_begin();
 575       TotalPh += computePhiCost(SB, FP);
 576       PredDefs += countPredicateDefs(SB);
 577     }
 578     if (FP.FalseB && FP.FalseB->succ_size() > 0) {
 579       MachineBasicBlock *SB = *FP.FalseB->succ_begin();
 580       TotalPh += computePhiCost(SB, FP);
 581       PredDefs += countPredicateDefs(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
 597 bool 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(B);
 603
 604   using GTN = GraphTraits<MachineDomTreeNode *>;
 605
 606   // We will change CFG/DT during this traversal, so take precautions to
 607   // avoid problems related to invalidated iterators. In fact, processing
 608   // a child C of B cannot cause another child to be removed, but it can
 609   // cause a new child to be added (which was a child of C before C itself
 610   // was removed. This new child C, however, would have been processed
 611   // prior to processing B, so there is no need to process it again.
 612   // Simply keep a list of children of B, and traverse that list.
 613   using DTNodeVectType = SmallVector<MachineDomTreeNode *, 4>;
 614   DTNodeVectType Cn(GTN::child_begin(N), GTN::child_end(N));
 615   for (DTNodeVectType::iterator I = Cn.begin(), E = Cn.end(); I != E; ++I) {
 616     MachineBasicBlock *SB = (*I)->getBlock();
 617     if (!Deleted.count(SB))
 618       Changed |= visitBlock(SB, L);
 619   }
 620   // When walking down the dominator tree, we want to traverse through
 621   // blocks from nested (other) loops, because they can dominate blocks
 622   // that are in L. Skip the non-L blocks only after the tree traversal.
 623   if (MLI->getLoopFor(B) != L)
 624     return Changed;
 625
 626   FlowPattern FP;
 627   if (!matchFlowPattern(B, L, FP))
 628     return Changed;
 629
 630   if (!isValid(FP)) {
 631     LLVM_DEBUG(dbgs() << "Conversion is not valid\n");
 632     return Changed;
 633   }
 634   if (!isProfitable(FP)) {
 635     LLVM_DEBUG(dbgs() << "Conversion is not profitable\n");
 636     return Changed;
 637   }
 638
 639   convert(FP);
 640   simplifyFlowGraph(FP);
 641   return true;
 642 }
 643
 644 bool HexagonEarlyIfConversion::visitLoop(MachineLoop *L) {
 645   MachineBasicBlock *HB = L ? L->getHeader() : nullptr;
 646   LLVM_DEBUG((L ? dbgs() << "Visiting loop H:" << PrintMB(HB)
 647                 : dbgs() << "Visiting function")
 648              << "\n");
 649   bool Changed = false;
 650   if (L) {
 651     for (MachineLoop::iterator I = L->begin(), E = L->end(); I != E; ++I)
 652       Changed |= visitLoop(*I);
 653   }
 654
 655   MachineBasicBlock *EntryB = GraphTraits<MachineFunction*>::getEntryNode(MFN);
 656   Changed |= visitBlock(L ? HB : EntryB, L);
 657   return Changed;
 658 }
 659
 660 bool HexagonEarlyIfConversion::isPredicableStore(const MachineInstr *MI)
 661       const {
 662   // HexagonInstrInfo::isPredicable will consider these stores are non-
 663   // -predicable if the offset would become constant-extended after
 664   // predication.
 665   unsigned Opc = MI->getOpcode();
 666   switch (Opc) {
 667     case Hexagon::S2_storerb_io:
 668     case Hexagon::S2_storerbnew_io:
 669     case Hexagon::S2_storerh_io:
 670     case Hexagon::S2_storerhnew_io:
 671     case Hexagon::S2_storeri_io:
 672     case Hexagon::S2_storerinew_io:
 673     case Hexagon::S2_storerd_io:
 674     case Hexagon::S4_storeirb_io:
 675     case Hexagon::S4_storeirh_io:
 676     case Hexagon::S4_storeiri_io:
 677       return true;
 678   }
 679
 680   // TargetInstrInfo::isPredicable takes a non-const pointer.
 681   return MI->mayStore() && HII->isPredicable(const_cast<MachineInstr&>(*MI));
 682 }
 683
 684 bool HexagonEarlyIfConversion::isSafeToSpeculate(const MachineInstr *MI)
 685       const {
 686   if (MI->mayLoad() || MI->mayStore())
 687     return false;
 688   if (MI->isCall() || MI->isBarrier() || MI->isBranch())
 689     return false;
 690   if (MI->hasUnmodeledSideEffects())
 691     return false;
 692   if (MI->getOpcode() == TargetOpcode::LIFETIME_END)
 693     return false;
 694
 695   return true;
 696 }
 697
 698 bool HexagonEarlyIfConversion::isPredicate(unsigned R) const {
 699   const TargetRegisterClass *RC = MRI->getRegClass(R);
 700   return RC == &Hexagon::PredRegsRegClass ||
 701          RC == &Hexagon::HvxQRRegClass;
 702 }
 703
 704 unsigned HexagonEarlyIfConversion::getCondStoreOpcode(unsigned Opc,
 705       bool IfTrue) const {
 706   return HII->getCondOpcode(Opc, !IfTrue);
 707 }
 708
 709 void HexagonEarlyIfConversion::predicateInstr(MachineBasicBlock *ToB,
 710       MachineBasicBlock::iterator At, MachineInstr *MI,
 711       unsigned PredR, bool IfTrue) {
 712   DebugLoc DL;
 713   if (At != ToB->end())
 714     DL = At->getDebugLoc();
 715   else if (!ToB->empty())
 716     DL = ToB->back().getDebugLoc();
 717
 718   unsigned Opc = MI->getOpcode();
 719
 720   if (isPredicableStore(MI)) {
 721     unsigned COpc = getCondStoreOpcode(Opc, IfTrue);
 722     assert(COpc);
 723     MachineInstrBuilder MIB = BuildMI(*ToB, At, DL, HII->get(COpc));
 724     MachineInstr::mop_iterator MOI = MI->operands_begin();
 725     if (HII->isPostIncrement(*MI)) {
 726       MIB.add(*MOI);
 727       ++MOI;
 728     }
 729     MIB.addReg(PredR);
 730     for (const MachineOperand &MO : make_range(MOI, MI->operands_end()))
 731       MIB.add(MO);
 732
 733     // Set memory references.
 734     MachineInstr::mmo_iterator MMOBegin = MI->memoperands_begin();
 735     MachineInstr::mmo_iterator MMOEnd = MI->memoperands_end();
 736     MIB.setMemRefs(MMOBegin, MMOEnd);
 737
 738     MI->eraseFromParent();
 739     return;
 740   }
 741
 742   if (Opc == Hexagon::J2_jump) {
 743     MachineBasicBlock *TB = MI->getOperand(0).getMBB();
 744     const MCInstrDesc &D = HII->get(IfTrue ? Hexagon::J2_jumpt
 745                                            : Hexagon::J2_jumpf);
 746     BuildMI(*ToB, At, DL, D)
 747       .addReg(PredR)
 748       .addMBB(TB);
 749     MI->eraseFromParent();
 750     return;
 751   }
 752
 753   // Print the offending instruction unconditionally as we are about to
 754   // abort.
 755   dbgs() << *MI;
 756   llvm_unreachable("Unexpected instruction");
 757 }
 758
 759 // Predicate/speculate non-branch instructions from FromB into block ToB.
 760 // Leave the branches alone, they will be handled later. Btw, at this point
 761 // FromB should have at most one branch, and it should be unconditional.
 762 void HexagonEarlyIfConversion::predicateBlockNB(MachineBasicBlock *ToB,
 763       MachineBasicBlock::iterator At, MachineBasicBlock *FromB,
 764       unsigned PredR, bool IfTrue) {
 765   LLVM_DEBUG(dbgs() << "Predicating block " << PrintMB(FromB) << "\n");
 766   MachineBasicBlock::iterator End = FromB->getFirstTerminator();
 767   MachineBasicBlock::iterator I, NextI;
 768
 769   for (I = FromB->begin(); I != End; I = NextI) {
 770     assert(!I->isPHI());
 771     NextI = std::next(I);
 772     if (isSafeToSpeculate(&*I))
 773       ToB->splice(At, FromB, I);
 774     else
 775       predicateInstr(ToB, At, &*I, PredR, IfTrue);
 776   }
 777 }
 778
 779 unsigned HexagonEarlyIfConversion::buildMux(MachineBasicBlock *B,
 780       MachineBasicBlock::iterator At, const TargetRegisterClass *DRC,
 781       unsigned PredR, unsigned TR, unsigned TSR, unsigned FR, unsigned FSR) {
 782   unsigned Opc = 0;
 783   switch (DRC->getID()) {
 784     case Hexagon::IntRegsRegClassID:
 785     case Hexagon::IntRegsLow8RegClassID:
 786       Opc = Hexagon::C2_mux;
 787       break;
 788     case Hexagon::DoubleRegsRegClassID:
 789     case Hexagon::GeneralDoubleLow8RegsRegClassID:
 790       Opc = Hexagon::PS_pselect;
 791       break;
 792     case Hexagon::HvxVRRegClassID:
 793       Opc = Hexagon::PS_vselect;
 794       break;
 795     case Hexagon::HvxWRRegClassID:
 796       Opc = Hexagon::PS_wselect;
 797       break;
 798     default:
 799       llvm_unreachable("unexpected register type");
 800   }
 801   const MCInstrDesc &D = HII->get(Opc);
 802
 803   DebugLoc DL = B->findBranchDebugLoc();
 804   unsigned MuxR = MRI->createVirtualRegister(DRC);
 805   BuildMI(*B, At, DL, D, MuxR)
 806     .addReg(PredR)
 807     .addReg(TR, 0, TSR)
 808     .addReg(FR, 0, FSR);
 809   return MuxR;
 810 }
 811
 812 void HexagonEarlyIfConversion::updatePhiNodes(MachineBasicBlock *WhereB,
 813       const FlowPattern &FP) {
 814   // Visit all PHI nodes in the WhereB block and generate MUX instructions
 815   // in the split block. Update the PHI nodes with the values of the MUX.
 816   auto NonPHI = WhereB->getFirstNonPHI();
 817   for (auto I = WhereB->begin(); I != NonPHI; ++I) {
 818     MachineInstr *PN = &*I;
 819     // Registers and subregisters corresponding to TrueB, FalseB and SplitB.
 820     unsigned TR = 0, TSR = 0, FR = 0, FSR = 0, SR = 0, SSR = 0;
 821     for (int i = PN->getNumOperands()-2; i > 0; i -= 2) {
 822       const MachineOperand &RO = PN->getOperand(i), &BO = PN->getOperand(i+1);
 823       if (BO.getMBB() == FP.SplitB)
 824         SR = RO.getReg(), SSR = RO.getSubReg();
 825       else if (BO.getMBB() == FP.TrueB)
 826         TR = RO.getReg(), TSR = RO.getSubReg();
 827       else if (BO.getMBB() == FP.FalseB)
 828         FR = RO.getReg(), FSR = RO.getSubReg();
 829       else
 830         continue;
 831       PN->RemoveOperand(i+1);
 832       PN->RemoveOperand(i);
 833     }
 834     if (TR == 0)
 835       TR = SR, TSR = SSR;
 836     else if (FR == 0)
 837       FR = SR, FSR = SSR;
 838
 839     assert(TR || FR);
 840     unsigned MuxR = 0, MuxSR = 0;
 841
 842     if (TR && FR) {
 843       unsigned DR = PN->getOperand(0).getReg();
 844       const TargetRegisterClass *RC = MRI->getRegClass(DR);
 845       MuxR = buildMux(FP.SplitB, FP.SplitB->getFirstTerminator(), RC,
 846                       FP.PredR, TR, TSR, FR, FSR);
 847     } else if (TR) {
 848       MuxR = TR;
 849       MuxSR = TSR;
 850     } else {
 851       MuxR = FR;
 852       MuxSR = FSR;
 853     }
 854
 855     PN->addOperand(MachineOperand::CreateReg(MuxR, false, false, false, false,
 856                                              false, false, MuxSR));
 857     PN->addOperand(MachineOperand::CreateMBB(FP.SplitB));
 858   }
 859 }
 860
 861 void HexagonEarlyIfConversion::convert(const FlowPattern &FP) {
 862   MachineBasicBlock *TSB = nullptr, *FSB = nullptr;
 863   MachineBasicBlock::iterator OldTI = FP.SplitB->getFirstTerminator();
 864   assert(OldTI != FP.SplitB->end());
 865   DebugLoc DL = OldTI->getDebugLoc();
 866
 867   if (FP.TrueB) {
 868     TSB = *FP.TrueB->succ_begin();
 869     predicateBlockNB(FP.SplitB, OldTI, FP.TrueB, FP.PredR, true);
 870   }
 871   if (FP.FalseB) {
 872     FSB = *FP.FalseB->succ_begin();
 873     MachineBasicBlock::iterator At = FP.SplitB->getFirstTerminator();
 874     predicateBlockNB(FP.SplitB, At, FP.FalseB, FP.PredR, false);
 875   }
 876
 877   // Regenerate new terminators in the split block and update the successors.
 878   // First, remember any information that may be needed later and remove the
 879   // existing terminators/successors from the split block.
 880   MachineBasicBlock *SSB = nullptr;
 881   FP.SplitB->erase(OldTI, FP.SplitB->end());
 882   while (FP.SplitB->succ_size() > 0) {
 883     MachineBasicBlock *T = *FP.SplitB->succ_begin();
 884     // It's possible that the split block had a successor that is not a pre-
 885     // dicated block. This could only happen if there was only one block to
 886     // be predicated. Example:
 887     //   split_b:
 888     //     if (p) jump true_b
 889     //     jump unrelated2_b
 890     //   unrelated1_b:
 891     //     ...
 892     //   unrelated2_b:  ; can have other predecessors, so it's not "false_b"
 893     //     jump other_b
 894     //   true_b:        ; only reachable from split_b, can be predicated
 895     //     ...
 896     //
 897     // Find this successor (SSB) if it exists.
 898     if (T != FP.TrueB && T != FP.FalseB) {
 899       assert(!SSB);
 900       SSB = T;
 901     }
 902     FP.SplitB->removeSuccessor(FP.SplitB->succ_begin());
 903   }
 904
 905   // Insert new branches and update the successors of the split block. This
 906   // may create unconditional branches to the layout successor, etc., but
 907   // that will be cleaned up later. For now, make sure that correct code is
 908   // generated.
 909   if (FP.JoinB) {
 910     assert(!SSB || SSB == FP.JoinB);
 911     BuildMI(*FP.SplitB, FP.SplitB->end(), DL, HII->get(Hexagon::J2_jump))
 912       .addMBB(FP.JoinB);
 913     FP.SplitB->addSuccessor(FP.JoinB);
 914   } else {
 915     bool HasBranch = false;
 916     if (TSB) {
 917       BuildMI(*FP.SplitB, FP.SplitB->end(), DL, HII->get(Hexagon::J2_jumpt))
 918         .addReg(FP.PredR)
 919         .addMBB(TSB);
 920       FP.SplitB->addSuccessor(TSB);
 921       HasBranch = true;
 922     }
 923     if (FSB) {
 924       const MCInstrDesc &D = HasBranch ? HII->get(Hexagon::J2_jump)
 925                                        : HII->get(Hexagon::J2_jumpf);
 926       MachineInstrBuilder MIB = BuildMI(*FP.SplitB, FP.SplitB->end(), DL, D);
 927       if (!HasBranch)
 928         MIB.addReg(FP.PredR);
 929       MIB.addMBB(FSB);
 930       FP.SplitB->addSuccessor(FSB);
 931     }
 932     if (SSB) {
 933       // This cannot happen if both TSB and FSB are set. [TF]SB are the
 934       // successor blocks of the TrueB and FalseB (or null of the TrueB
 935       // or FalseB block is null). SSB is the potential successor block
 936       // of the SplitB that is neither TrueB nor FalseB.
 937       BuildMI(*FP.SplitB, FP.SplitB->end(), DL, HII->get(Hexagon::J2_jump))
 938         .addMBB(SSB);
 939       FP.SplitB->addSuccessor(SSB);
 940     }
 941   }
 942
 943   // What is left to do is to update the PHI nodes that could have entries
 944   // referring to predicated blocks.
 945   if (FP.JoinB) {
 946     updatePhiNodes(FP.JoinB, FP);
 947   } else {
 948     if (TSB)
 949       updatePhiNodes(TSB, FP);
 950     if (FSB)
 951       updatePhiNodes(FSB, FP);
 952     // Nothing to update in SSB, since SSB's predecessors haven't changed.
 953   }
 954 }
 955
 956 void HexagonEarlyIfConversion::removeBlock(MachineBasicBlock *B) {
 957   LLVM_DEBUG(dbgs() << "Removing block " << PrintMB(B) << "\n");
 958
 959   // Transfer the immediate dominator information from B to its descendants.
 960   MachineDomTreeNode *N = MDT->getNode(B);
 961   MachineDomTreeNode *IDN = N->getIDom();
 962   if (IDN) {
 963     MachineBasicBlock *IDB = IDN->getBlock();
 964
 965     using GTN = GraphTraits<MachineDomTreeNode *>;
 966     using DTNodeVectType = SmallVector<MachineDomTreeNode *, 4>;
 967
 968     DTNodeVectType Cn(GTN::child_begin(N), GTN::child_end(N));
 969     for (DTNodeVectType::iterator I = Cn.begin(), E = Cn.end(); I != E; ++I) {
 970       MachineBasicBlock *SB = (*I)->getBlock();
 971       MDT->changeImmediateDominator(SB, IDB);
 972     }
 973   }
 974
 975   while (B->succ_size() > 0)
 976     B->removeSuccessor(B->succ_begin());
 977
 978   for (auto I = B->pred_begin(), E = B->pred_end(); I != E; ++I)
 979     (*I)->removeSuccessor(B, true);
 980
 981   Deleted.insert(B);
 982   MDT->eraseNode(B);
 983   MFN->erase(B->getIterator());
 984 }
 985
 986 void HexagonEarlyIfConversion::eliminatePhis(MachineBasicBlock *B) {
 987   LLVM_DEBUG(dbgs() << "Removing phi nodes from block " << PrintMB(B) << "\n");
 988   MachineBasicBlock::iterator I, NextI, NonPHI = B->getFirstNonPHI();
 989   for (I = B->begin(); I != NonPHI; I = NextI) {
 990     NextI = std::next(I);
 991     MachineInstr *PN = &*I;
 992     assert(PN->getNumOperands() == 3 && "Invalid phi node");
 993     MachineOperand &UO = PN->getOperand(1);
 994     unsigned UseR = UO.getReg(), UseSR = UO.getSubReg();
 995     unsigned DefR = PN->getOperand(0).getReg();
 996     unsigned NewR = UseR;
 997     if (UseSR) {
 998       // MRI.replaceVregUsesWith does not allow to update the subregister,
 999       // so instead of doing the use-iteration here, create a copy into a
1000       // "non-subregistered" register.
1001       const DebugLoc &DL = PN->getDebugLoc();
1002       const TargetRegisterClass *RC = MRI->getRegClass(DefR);
1003       NewR = MRI->createVirtualRegister(RC);
1004       NonPHI = BuildMI(*B, NonPHI, DL, HII->get(TargetOpcode::COPY), NewR)
1005         .addReg(UseR, 0, UseSR);
1006     }
1007     MRI->replaceRegWith(DefR, NewR);
1008     B->erase(I);
1009   }
1010 }
1011
1012 void HexagonEarlyIfConversion::mergeBlocks(MachineBasicBlock *PredB,
1013       MachineBasicBlock *SuccB) {
1014   LLVM_DEBUG(dbgs() << "Merging blocks " << PrintMB(PredB) << " and "
1015                     << PrintMB(SuccB) << "\n");
1016   bool TermOk = hasUncondBranch(SuccB);
1017   eliminatePhis(SuccB);
1018   HII->removeBranch(*PredB);
1019   PredB->removeSuccessor(SuccB);
1020   PredB->splice(PredB->end(), SuccB, SuccB->begin(), SuccB->end());
1021   PredB->transferSuccessorsAndUpdatePHIs(SuccB);
1022   removeBlock(SuccB);
1023   if (!TermOk)
1024     PredB->updateTerminator();
1025 }
1026
1027 void HexagonEarlyIfConversion::simplifyFlowGraph(const FlowPattern &FP) {
1028   if (FP.TrueB)
1029     removeBlock(FP.TrueB);
1030   if (FP.FalseB)
1031     removeBlock(FP.FalseB);
1032
1033   FP.SplitB->updateTerminator();
1034   if (FP.SplitB->succ_size() != 1)
1035     return;
1036
1037   MachineBasicBlock *SB = *FP.SplitB->succ_begin();
1038   if (SB->pred_size() != 1)
1039     return;
1040
1041   // By now, the split block has only one successor (SB), and SB has only
1042   // one predecessor. We can try to merge them. We will need to update ter-
1043   // minators in FP.Split+SB, and that requires working analyzeBranch, which
1044   // fails on Hexagon for blocks that have EH_LABELs. However, if SB ends
1045   // with an unconditional branch, we won't need to touch the terminators.
1046   if (!hasEHLabel(SB) || hasUncondBranch(SB))
1047     mergeBlocks(FP.SplitB, SB);
1048 }
1049
1050 bool HexagonEarlyIfConversion::runOnMachineFunction(MachineFunction &MF) {
1051   if (skipFunction(MF.getFunction()))
1052     return false;
1053
1054   auto &ST = MF.getSubtarget<HexagonSubtarget>();
1055   HII = ST.getInstrInfo();
1056   TRI = ST.getRegisterInfo();
1057   MFN = &MF;
1058   MRI = &MF.getRegInfo();
1059   MDT = &getAnalysis<MachineDominatorTree>();
1060   MLI = &getAnalysis<MachineLoopInfo>();
1061   MBPI = EnableHexagonBP ? &getAnalysis<MachineBranchProbabilityInfo>() :
1062     nullptr;
1063
1064   Deleted.clear();
1065   bool Changed = false;
1066
1067   for (MachineLoopInfo::iterator I = MLI->begin(), E = MLI->end(); I != E; ++I)
1068     Changed |= visitLoop(*I);
1069   Changed |= visitLoop(nullptr);
1070
1071   return Changed;
1072 }
1073
1074 //===----------------------------------------------------------------------===//
1075 //                         Public Constructor Functions
1076 //===----------------------------------------------------------------------===//
1077 FunctionPass *llvm::createHexagonEarlyIfConversion() {
1078   return new HexagonEarlyIfConversion();
1079 }