lib/Target/Hexagon/HexagonHardwareLoops.cpp

   1 //===-- HexagonHardwareLoops.cpp - Identify and generate hardware loops ---===//
   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 pass identifies loops where we can generate the Hexagon hardware
  11 // loop instruction.  The hardware loop can perform loop branches with a
  12 // zero-cycle overhead.
  13 //
  14 // The pattern that defines the induction variable can changed depending on
  15 // prior optimizations.  For example, the IndVarSimplify phase run by 'opt'
  16 // normalizes induction variables, and the Loop Strength Reduction pass
  17 // run by 'llc' may also make changes to the induction variable.
  18 // The pattern detected by this phase is due to running Strength Reduction.
  19 //
  20 // Criteria for hardware loops:
  21 //  - Countable loops (w/ ind. var for a trip count)
  22 //  - Assumes loops are normalized by IndVarSimplify
  23 //  - Try inner-most loops first
  24 //  - No nested hardware loops.
  25 //  - No function calls in loops.
  26 //
  27 //===----------------------------------------------------------------------===//
  28
  29 #define DEBUG_TYPE "hwloops"
  30 #include "llvm/ADT/SmallSet.h"
  31 #include "Hexagon.h"
  32 #include "HexagonTargetMachine.h"
  33 #include "llvm/ADT/Statistic.h"
  34 #include "llvm/CodeGen/MachineDominators.h"
  35 #include "llvm/CodeGen/MachineFunction.h"
  36 #include "llvm/CodeGen/MachineFunctionPass.h"
  37 #include "llvm/CodeGen/MachineInstrBuilder.h"
  38 #include "llvm/CodeGen/MachineLoopInfo.h"
  39 #include "llvm/CodeGen/MachineRegisterInfo.h"
  40 #include "llvm/PassSupport.h"
  41 #include "llvm/Support/CommandLine.h"
  42 #include "llvm/Support/Debug.h"
  43 #include "llvm/Support/raw_ostream.h"
  44 #include "llvm/Target/TargetInstrInfo.h"
  45 #include <algorithm>
  46 #include <vector>
  47
  48 using namespace llvm;
  49
  50 #ifndef NDEBUG
  51 static cl::opt<int> HWLoopLimit("max-hwloop", cl::Hidden, cl::init(-1));
  52 #endif
  53
  54 STATISTIC(NumHWLoops, "Number of loops converted to hardware loops");
  55
  56 namespace llvm {
  57   void initializeHexagonHardwareLoopsPass(PassRegistry&);
  58 }
  59
  60 namespace {
  61   class CountValue;
  62   struct HexagonHardwareLoops : public MachineFunctionPass {
  63     MachineLoopInfo            *MLI;
  64     MachineRegisterInfo        *MRI;
  65     MachineDominatorTree       *MDT;
  66     const HexagonTargetMachine *TM;
  67     const HexagonInstrInfo     *TII;
  68     const HexagonRegisterInfo  *TRI;
  69 #ifndef NDEBUG
  70     static int Counter;
  71 #endif
  72
  73   public:
  74     static char ID;
  75
  76     HexagonHardwareLoops() : MachineFunctionPass(ID) {
  77       initializeHexagonHardwareLoopsPass(*PassRegistry::getPassRegistry());
  78     }
  79
  80     virtual bool runOnMachineFunction(MachineFunction &MF);
  81
  82     const char *getPassName() const { return "Hexagon Hardware Loops"; }
  83
  84     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  85       AU.addRequired<MachineDominatorTree>();
  86       AU.addRequired<MachineLoopInfo>();
  87       MachineFunctionPass::getAnalysisUsage(AU);
  88     }
  89
  90   private:
  91     /// Kinds of comparisons in the compare instructions.
  92     struct Comparison {
  93       enum Kind {
  94         EQ  = 0x01,
  95         NE  = 0x02,
  96         L   = 0x04, // Less-than property.
  97         G   = 0x08, // Greater-than property.
  98         U   = 0x40, // Unsigned property.
  99         LTs = L,
 100         LEs = L | EQ,
 101         GTs = G,
 102         GEs = G | EQ,
 103         LTu = L      | U,
 104         LEu = L | EQ | U,
 105         GTu = G      | U,
 106         GEu = G | EQ | U
 107       };
 108
 109       static Kind getSwappedComparison(Kind Cmp) {
 110         assert ((!((Cmp & L) && (Cmp & G))) && "Malformed comparison operator");
 111         if ((Cmp & L) || (Cmp & G))
 112           return (Kind)(Cmp ^ (L|G));
 113         return Cmp;
 114       }
 115     };
 116
 117     /// \brief Find the register that contains the loop controlling
 118     /// induction variable.
 119     /// If successful, it will return true and set the \p Reg, \p IVBump
 120     /// and \p IVOp arguments.  Otherwise it will return false.
 121     /// The returned induction register is the register R that follows the
 122     /// following induction pattern:
 123     /// loop:
 124     ///   R = phi ..., [ R.next, LatchBlock ]
 125     ///   R.next = R + #bump
 126     ///   if (R.next < #N) goto loop
 127     /// IVBump is the immediate value added to R, and IVOp is the instruction
 128     /// "R.next = R + #bump".
 129     bool findInductionRegister(MachineLoop *L, unsigned &Reg,
 130                                int64_t &IVBump, MachineInstr *&IVOp) const;
 131
 132     /// \brief Analyze the statements in a loop to determine if the loop
 133     /// has a computable trip count and, if so, return a value that represents
 134     /// the trip count expression.
 135     CountValue *getLoopTripCount(MachineLoop *L,
 136                                  SmallVectorImpl<MachineInstr *> &OldInsts);
 137
 138     /// \brief Return the expression that represents the number of times
 139     /// a loop iterates.  The function takes the operands that represent the
 140     /// loop start value, loop end value, and induction value.  Based upon
 141     /// these operands, the function attempts to compute the trip count.
 142     /// If the trip count is not directly available (as an immediate value,
 143     /// or a register), the function will attempt to insert computation of it
 144     /// to the loop's preheader.
 145     CountValue *computeCount(MachineLoop *Loop,
 146                              const MachineOperand *Start,
 147                              const MachineOperand *End,
 148                              unsigned IVReg,
 149                              int64_t IVBump,
 150                              Comparison::Kind Cmp) const;
 151
 152     /// \brief Return true if the instruction is not valid within a hardware
 153     /// loop.
 154     bool isInvalidLoopOperation(const MachineInstr *MI) const;
 155
 156     /// \brief Return true if the loop contains an instruction that inhibits
 157     /// using the hardware loop.
 158     bool containsInvalidInstruction(MachineLoop *L) const;
 159
 160     /// \brief Given a loop, check if we can convert it to a hardware loop.
 161     /// If so, then perform the conversion and return true.
 162     bool convertToHardwareLoop(MachineLoop *L);
 163
 164     /// \brief Return true if the instruction is now dead.
 165     bool isDead(const MachineInstr *MI,
 166                 SmallVectorImpl<MachineInstr *> &DeadPhis) const;
 167
 168     /// \brief Remove the instruction if it is now dead.
 169     void removeIfDead(MachineInstr *MI);
 170
 171     /// \brief Make sure that the "bump" instruction executes before the
 172     /// compare.  We need that for the IV fixup, so that the compare
 173     /// instruction would not use a bumped value that has not yet been
 174     /// defined.  If the instructions are out of order, try to reorder them.
 175     bool orderBumpCompare(MachineInstr *BumpI, MachineInstr *CmpI);
 176
 177     /// \brief Get the instruction that loads an immediate value into \p R,
 178     /// or 0 if such an instruction does not exist.
 179     MachineInstr *defWithImmediate(unsigned R);
 180
 181     /// \brief Get the immediate value referenced to by \p MO, either for
 182     /// immediate operands, or for register operands, where the register
 183     /// was defined with an immediate value.
 184     int64_t getImmediate(MachineOperand &MO);
 185
 186     /// \brief Reset the given machine operand to now refer to a new immediate
 187     /// value.  Assumes that the operand was already referencing an immediate
 188     /// value, either directly, or via a register.
 189     void setImmediate(MachineOperand &MO, int64_t Val);
 190
 191     /// \brief Fix the data flow of the induction varible.
 192     /// The desired flow is: phi ---> bump -+-> comparison-in-latch.
 193     ///                                     |
 194     ///                                     +-> back to phi
 195     /// where "bump" is the increment of the induction variable:
 196     ///   iv = iv + #const.
 197     /// Due to some prior code transformations, the actual flow may look
 198     /// like this:
 199     ///   phi -+-> bump ---> back to phi
 200     ///        |
 201     ///        +-> comparison-in-latch (against upper_bound-bump),
 202     /// i.e. the comparison that controls the loop execution may be using
 203     /// the value of the induction variable from before the increment.
 204     ///
 205     /// Return true if the loop's flow is the desired one (i.e. it's
 206     /// either been fixed, or no fixing was necessary).
 207     /// Otherwise, return false.  This can happen if the induction variable
 208     /// couldn't be identified, or if the value in the latch's comparison
 209     /// cannot be adjusted to reflect the post-bump value.
 210     bool fixupInductionVariable(MachineLoop *L);
 211
 212     /// \brief Given a loop, if it does not have a preheader, create one.
 213     /// Return the block that is the preheader.
 214     MachineBasicBlock *createPreheaderForLoop(MachineLoop *L);
 215   };
 216
 217   char HexagonHardwareLoops::ID = 0;
 218 #ifndef NDEBUG
 219   int HexagonHardwareLoops::Counter = 0;
 220 #endif
 221
 222   /// \brief Abstraction for a trip count of a loop. A smaller vesrsion
 223   /// of the MachineOperand class without the concerns of changing the
 224   /// operand representation.
 225   class CountValue {
 226   public:
 227     enum CountValueType {
 228       CV_Register,
 229       CV_Immediate
 230     };
 231   private:
 232     CountValueType Kind;
 233     union Values {
 234       struct {
 235         unsigned Reg;
 236         unsigned Sub;
 237       } R;
 238       unsigned ImmVal;
 239     } Contents;
 240
 241   public:
 242     explicit CountValue(CountValueType t, unsigned v, unsigned u = 0) {
 243       Kind = t;
 244       if (Kind == CV_Register) {
 245         Contents.R.Reg = v;
 246         Contents.R.Sub = u;
 247       } else {
 248         Contents.ImmVal = v;
 249       }
 250     }
 251     bool isReg() const { return Kind == CV_Register; }
 252     bool isImm() const { return Kind == CV_Immediate; }
 253
 254     unsigned getReg() const {
 255       assert(isReg() && "Wrong CountValue accessor");
 256       return Contents.R.Reg;
 257     }
 258     unsigned getSubReg() const {
 259       assert(isReg() && "Wrong CountValue accessor");
 260       return Contents.R.Sub;
 261     }
 262     unsigned getImm() const {
 263       assert(isImm() && "Wrong CountValue accessor");
 264       return Contents.ImmVal;
 265     }
 266
 267     void print(raw_ostream &OS, const TargetMachine *TM = 0) const {
 268       const TargetRegisterInfo *TRI = TM ? TM->getRegisterInfo() : 0;
 269       if (isReg()) { OS << PrintReg(Contents.R.Reg, TRI, Contents.R.Sub); }
 270       if (isImm()) { OS << Contents.ImmVal; }
 271     }
 272   };
 273 } // end anonymous namespace
 274
 275
 276 INITIALIZE_PASS_BEGIN(HexagonHardwareLoops, "hwloops",
 277                       "Hexagon Hardware Loops", false, false)
 278 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
 279 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
 280 INITIALIZE_PASS_END(HexagonHardwareLoops, "hwloops",
 281                     "Hexagon Hardware Loops", false, false)
 282
 283
 284 /// \brief Returns true if the instruction is a hardware loop instruction.
 285 static bool isHardwareLoop(const MachineInstr *MI) {
 286   return MI->getOpcode() == Hexagon::LOOP0_r ||
 287     MI->getOpcode() == Hexagon::LOOP0_i;
 288 }
 289
 290 FunctionPass *llvm::createHexagonHardwareLoops() {
 291   return new HexagonHardwareLoops();
 292 }
 293
 294
 295 bool HexagonHardwareLoops::runOnMachineFunction(MachineFunction &MF) {
 296   DEBUG(dbgs() << "********* Hexagon Hardware Loops *********\n");
 297
 298   bool Changed = false;
 299
 300   MLI = &getAnalysis<MachineLoopInfo>();
 301   MRI = &MF.getRegInfo();
 302   MDT = &getAnalysis<MachineDominatorTree>();
 303   TM  = static_cast<const HexagonTargetMachine*>(&MF.getTarget());
 304   TII = static_cast<const HexagonInstrInfo*>(TM->getInstrInfo());
 305   TRI = static_cast<const HexagonRegisterInfo*>(TM->getRegisterInfo());
 306
 307   for (MachineLoopInfo::iterator I = MLI->begin(), E = MLI->end();
 308        I != E; ++I) {
 309     MachineLoop *L = *I;
 310     if (!L->getParentLoop())
 311       Changed |= convertToHardwareLoop(L);
 312   }
 313
 314   return Changed;
 315 }
 316
 317
 318 bool HexagonHardwareLoops::findInductionRegister(MachineLoop *L,
 319                                                  unsigned &Reg,
 320                                                  int64_t &IVBump,
 321                                                  MachineInstr *&IVOp
 322                                                  ) const {
 323   MachineBasicBlock *Header = L->getHeader();
 324   MachineBasicBlock *Preheader = L->getLoopPreheader();
 325   MachineBasicBlock *Latch = L->getLoopLatch();
 326   if (!Header || !Preheader || !Latch)
 327     return false;
 328
 329   // This pair represents an induction register together with an immediate
 330   // value that will be added to it in each loop iteration.
 331   typedef std::pair<unsigned,int64_t> RegisterBump;
 332
 333   // Mapping:  R.next -> (R, bump), where R, R.next and bump are derived
 334   // from an induction operation
 335   //   R.next = R + bump
 336   // where bump is an immediate value.
 337   typedef std::map<unsigned,RegisterBump> InductionMap;
 338
 339   InductionMap IndMap;
 340
 341   typedef MachineBasicBlock::instr_iterator instr_iterator;
 342   for (instr_iterator I = Header->instr_begin(), E = Header->instr_end();
 343        I != E && I->isPHI(); ++I) {
 344     MachineInstr *Phi = &*I;
 345
 346     // Have a PHI instruction.  Get the operand that corresponds to the
 347     // latch block, and see if is a result of an addition of form "reg+imm",
 348     // where the "reg" is defined by the PHI node we are looking at.
 349     for (unsigned i = 1, n = Phi->getNumOperands(); i < n; i += 2) {
 350       if (Phi->getOperand(i+1).getMBB() != Latch)
 351         continue;
 352
 353       unsigned PhiOpReg = Phi->getOperand(i).getReg();
 354       MachineInstr *DI = MRI->getVRegDef(PhiOpReg);
 355       unsigned UpdOpc = DI->getOpcode();
 356       bool isAdd = (UpdOpc == Hexagon::ADD_ri);
 357
 358       if (isAdd) {
 359         // If the register operand to the add is the PHI we're
 360         // looking at, this meets the induction pattern.
 361         unsigned IndReg = DI->getOperand(1).getReg();
 362         if (MRI->getVRegDef(IndReg) == Phi) {
 363           unsigned UpdReg = DI->getOperand(0).getReg();
 364           int64_t V = DI->getOperand(2).getImm();
 365           IndMap.insert(std::make_pair(UpdReg, std::make_pair(IndReg, V)));
 366         }
 367       }
 368     }  // for (i)
 369   }  // for (instr)
 370
 371   SmallVector<MachineOperand,2> Cond;
 372   MachineBasicBlock *TB = 0, *FB = 0;
 373   bool NotAnalyzed = TII->AnalyzeBranch(*Latch, TB, FB, Cond, false);
 374   if (NotAnalyzed)
 375     return false;
 376
 377   unsigned CSz = Cond.size();
 378   assert (CSz == 1 || CSz == 2);
 379   unsigned PredR = Cond[CSz-1].getReg();
 380
 381   MachineInstr *PredI = MRI->getVRegDef(PredR);
 382   if (!PredI->isCompare())
 383     return false;
 384
 385   unsigned CmpReg1 = 0, CmpReg2 = 0;
 386   int CmpImm = 0, CmpMask = 0;
 387   bool CmpAnalyzed = TII->analyzeCompare(PredI, CmpReg1, CmpReg2,
 388                                          CmpMask, CmpImm);
 389   // Fail if the compare was not analyzed, or it's not comparing a register
 390   // with an immediate value.  Not checking the mask here, since we handle
 391   // the individual compare opcodes (including CMPb) later on.
 392   if (!CmpAnalyzed)
 393     return false;
 394
 395   // Exactly one of the input registers to the comparison should be among
 396   // the induction registers.
 397   InductionMap::iterator IndMapEnd = IndMap.end();
 398   InductionMap::iterator F = IndMapEnd;
 399   if (CmpReg1 != 0) {
 400     InductionMap::iterator F1 = IndMap.find(CmpReg1);
 401     if (F1 != IndMapEnd)
 402       F = F1;
 403   }
 404   if (CmpReg2 != 0) {
 405     InductionMap::iterator F2 = IndMap.find(CmpReg2);
 406     if (F2 != IndMapEnd) {
 407       if (F != IndMapEnd)
 408         return false;
 409       F = F2;
 410     }
 411   }
 412   if (F == IndMapEnd)
 413     return false;
 414
 415   Reg = F->second.first;
 416   IVBump = F->second.second;
 417   IVOp = MRI->getVRegDef(F->first);
 418   return true;
 419 }
 420
 421
 422 /// \brief Analyze the statements in a loop to determine if the loop has
 423 /// a computable trip count and, if so, return a value that represents
 424 /// the trip count expression.
 425 ///
 426 /// This function iterates over the phi nodes in the loop to check for
 427 /// induction variable patterns that are used in the calculation for
 428 /// the number of time the loop is executed.
 429 CountValue *HexagonHardwareLoops::getLoopTripCount(MachineLoop *L,
 430                                     SmallVectorImpl<MachineInstr *> &OldInsts) {
 431   MachineBasicBlock *TopMBB = L->getTopBlock();
 432   MachineBasicBlock::pred_iterator PI = TopMBB->pred_begin();
 433   assert(PI != TopMBB->pred_end() &&
 434          "Loop must have more than one incoming edge!");
 435   MachineBasicBlock *Backedge = *PI++;
 436   if (PI == TopMBB->pred_end())  // dead loop?
 437     return 0;
 438   MachineBasicBlock *Incoming = *PI++;
 439   if (PI != TopMBB->pred_end())  // multiple backedges?
 440     return 0;
 441
 442   // Make sure there is one incoming and one backedge and determine which
 443   // is which.
 444   if (L->contains(Incoming)) {
 445     if (L->contains(Backedge))
 446       return 0;
 447     std::swap(Incoming, Backedge);
 448   } else if (!L->contains(Backedge))
 449     return 0;
 450
 451   // Look for the cmp instruction to determine if we can get a useful trip
 452   // count.  The trip count can be either a register or an immediate.  The
 453   // location of the value depends upon the type (reg or imm).
 454   MachineBasicBlock *Latch = L->getLoopLatch();
 455   if (!Latch)
 456     return 0;
 457
 458   unsigned IVReg = 0;
 459   int64_t IVBump = 0;
 460   MachineInstr *IVOp;
 461   bool FoundIV = findInductionRegister(L, IVReg, IVBump, IVOp);
 462   if (!FoundIV)
 463     return 0;
 464
 465   MachineBasicBlock *Preheader = L->getLoopPreheader();
 466
 467   MachineOperand *InitialValue = 0;
 468   MachineInstr *IV_Phi = MRI->getVRegDef(IVReg);
 469   for (unsigned i = 1, n = IV_Phi->getNumOperands(); i < n; i += 2) {
 470     MachineBasicBlock *MBB = IV_Phi->getOperand(i+1).getMBB();
 471     if (MBB == Preheader)
 472       InitialValue = &IV_Phi->getOperand(i);
 473     else if (MBB == Latch)
 474       IVReg = IV_Phi->getOperand(i).getReg();  // Want IV reg after bump.
 475   }
 476   if (!InitialValue)
 477     return 0;
 478
 479   SmallVector<MachineOperand,2> Cond;
 480   MachineBasicBlock *TB = 0, *FB = 0;
 481   bool NotAnalyzed = TII->AnalyzeBranch(*Latch, TB, FB, Cond, false);
 482   if (NotAnalyzed)
 483     return 0;
 484
 485   MachineBasicBlock *Header = L->getHeader();
 486   // TB must be non-null.  If FB is also non-null, one of them must be
 487   // the header.  Otherwise, branch to TB could be exiting the loop, and
 488   // the fall through can go to the header.
 489   assert (TB && "Latch block without a branch?");
 490   assert ((!FB || TB == Header || FB == Header) && "Branches not to header?");
 491   if (!TB || (FB && TB != Header && FB != Header))
 492     return 0;
 493
 494   // Branches of form "if (!P) ..." cause HexagonInstrInfo::AnalyzeBranch
 495   // to put imm(0), followed by P in the vector Cond.
 496   // If TB is not the header, it means that the "not-taken" path must lead
 497   // to the header.
 498   bool Negated = (Cond.size() > 1) ^ (TB != Header);
 499   unsigned PredReg = Cond[Cond.size()-1].getReg();
 500   MachineInstr *CondI = MRI->getVRegDef(PredReg);
 501   unsigned CondOpc = CondI->getOpcode();
 502
 503   unsigned CmpReg1 = 0, CmpReg2 = 0;
 504   int Mask = 0, ImmValue = 0;
 505   bool AnalyzedCmp = TII->analyzeCompare(CondI, CmpReg1, CmpReg2,
 506                                          Mask, ImmValue);
 507   if (!AnalyzedCmp)
 508     return 0;
 509
 510   // The comparison operator type determines how we compute the loop
 511   // trip count.
 512   OldInsts.push_back(CondI);
 513   OldInsts.push_back(IVOp);
 514
 515   // Sadly, the following code gets information based on the position
 516   // of the operands in the compare instruction.  This has to be done
 517   // this way, because the comparisons check for a specific relationship
 518   // between the operands (e.g. is-less-than), rather than to find out
 519   // what relationship the operands are in (as on PPC).
 520   Comparison::Kind Cmp;
 521   bool isSwapped = false;
 522   const MachineOperand &Op1 = CondI->getOperand(1);
 523   const MachineOperand &Op2 = CondI->getOperand(2);
 524   const MachineOperand *EndValue = 0;
 525
 526   if (Op1.isReg()) {
 527     if (Op2.isImm() || Op1.getReg() == IVReg)
 528       EndValue = &Op2;
 529     else {
 530       EndValue = &Op1;
 531       isSwapped = true;
 532     }
 533   }
 534
 535   if (!EndValue)
 536     return 0;
 537
 538   switch (CondOpc) {
 539     case Hexagon::CMPEQri:
 540     case Hexagon::CMPEQrr:
 541       Cmp = !Negated ? Comparison::EQ : Comparison::NE;
 542       break;
 543     case Hexagon::CMPGTUri:
 544     case Hexagon::CMPGTUrr:
 545       Cmp = !Negated ? Comparison::GTu : Comparison::LEu;
 546       break;
 547     case Hexagon::CMPGTri:
 548     case Hexagon::CMPGTrr:
 549       Cmp = !Negated ? Comparison::GTs : Comparison::LEs;
 550       break;
 551     // Very limited support for byte/halfword compares.
 552     case Hexagon::CMPbEQri_V4:
 553     case Hexagon::CMPhEQri_V4: {
 554       if (IVBump != 1)
 555         return 0;
 556
 557       int64_t InitV, EndV;
 558       // Since the comparisons are "ri", the EndValue should be an
 559       // immediate.  Check it just in case.
 560       assert(EndValue->isImm() && "Unrecognized latch comparison");
 561       EndV = EndValue->getImm();
 562       // Allow InitialValue to be a register defined with an immediate.
 563       if (InitialValue->isReg()) {
 564         if (!defWithImmediate(InitialValue->getReg()))
 565           return 0;
 566         InitV = getImmediate(*InitialValue);
 567       } else {
 568         assert(InitialValue->isImm());
 569         InitV = InitialValue->getImm();
 570       }
 571       if (InitV >= EndV)
 572         return 0;
 573       if (CondOpc == Hexagon::CMPbEQri_V4) {
 574         if (!isInt<8>(InitV) || !isInt<8>(EndV))
 575           return 0;
 576       } else {  // Hexagon::CMPhEQri_V4
 577         if (!isInt<16>(InitV) || !isInt<16>(EndV))
 578           return 0;
 579       }
 580       Cmp = !Negated ? Comparison::EQ : Comparison::NE;
 581       break;
 582     }
 583     default:
 584       return 0;
 585   }
 586
 587   if (isSwapped)
 588    Cmp = Comparison::getSwappedComparison(Cmp);
 589
 590   if (InitialValue->isReg()) {
 591     unsigned R = InitialValue->getReg();
 592     MachineBasicBlock *DefBB = MRI->getVRegDef(R)->getParent();
 593     if (!MDT->properlyDominates(DefBB, Header))
 594       return 0;
 595     OldInsts.push_back(MRI->getVRegDef(R));
 596   }
 597   if (EndValue->isReg()) {
 598     unsigned R = EndValue->getReg();
 599     MachineBasicBlock *DefBB = MRI->getVRegDef(R)->getParent();
 600     if (!MDT->properlyDominates(DefBB, Header))
 601       return 0;
 602   }
 603
 604   return computeCount(L, InitialValue, EndValue, IVReg, IVBump, Cmp);
 605 }
 606
 607 /// \brief Helper function that returns the expression that represents the
 608 /// number of times a loop iterates.  The function takes the operands that
 609 /// represent the loop start value, loop end value, and induction value.
 610 /// Based upon these operands, the function attempts to compute the trip count.
 611 CountValue *HexagonHardwareLoops::computeCount(MachineLoop *Loop,
 612                                                const MachineOperand *Start,
 613                                                const MachineOperand *End,
 614                                                unsigned IVReg,
 615                                                int64_t IVBump,
 616                                                Comparison::Kind Cmp) const {
 617   // Cannot handle comparison EQ, i.e. while (A == B).
 618   if (Cmp == Comparison::EQ)
 619     return 0;
 620
 621   // Check if either the start or end values are an assignment of an immediate.
 622   // If so, use the immediate value rather than the register.
 623   if (Start->isReg()) {
 624     const MachineInstr *StartValInstr = MRI->getVRegDef(Start->getReg());
 625     if (StartValInstr && StartValInstr->getOpcode() == Hexagon::TFRI)
 626       Start = &StartValInstr->getOperand(1);
 627   }
 628   if (End->isReg()) {
 629     const MachineInstr *EndValInstr = MRI->getVRegDef(End->getReg());
 630     if (EndValInstr && EndValInstr->getOpcode() == Hexagon::TFRI)
 631       End = &EndValInstr->getOperand(1);
 632   }
 633
 634   assert (Start->isReg() || Start->isImm());
 635   assert (End->isReg() || End->isImm());
 636
 637   bool CmpLess =     Cmp & Comparison::L;
 638   bool CmpGreater =  Cmp & Comparison::G;
 639   bool CmpHasEqual = Cmp & Comparison::EQ;
 640
 641   // Avoid certain wrap-arounds.  This doesn't detect all wrap-arounds.
 642   // If loop executes while iv is "less" with the iv value going down, then
 643   // the iv must wrap.
 644   if (CmpLess && IVBump < 0)
 645     return 0;
 646   // If loop executes while iv is "greater" with the iv value going up, then
 647   // the iv must wrap.
 648   if (CmpGreater && IVBump > 0)
 649     return 0;
 650
 651   if (Start->isImm() && End->isImm()) {
 652     // Both, start and end are immediates.
 653     int64_t StartV = Start->getImm();
 654     int64_t EndV = End->getImm();
 655     int64_t Dist = EndV - StartV;
 656     if (Dist == 0)
 657       return 0;
 658
 659     bool Exact = (Dist % IVBump) == 0;
 660
 661     if (Cmp == Comparison::NE) {
 662       if (!Exact)
 663         return 0;
 664       if ((Dist < 0) ^ (IVBump < 0))
 665         return 0;
 666     }
 667
 668     // For comparisons that include the final value (i.e. include equality
 669     // with the final value), we need to increase the distance by 1.
 670     if (CmpHasEqual)
 671       Dist = Dist > 0 ? Dist+1 : Dist-1;
 672
 673     // assert (CmpLess => Dist > 0);
 674     assert ((!CmpLess || Dist > 0) && "Loop should never iterate!");
 675     // assert (CmpGreater => Dist < 0);
 676     assert ((!CmpGreater || Dist < 0) && "Loop should never iterate!");
 677
 678     // "Normalized" distance, i.e. with the bump set to +-1.
 679     int64_t Dist1 = (IVBump > 0) ? (Dist +  (IVBump-1)) /   IVBump
 680                                :  (-Dist + (-IVBump-1)) / (-IVBump);
 681     assert (Dist1 > 0 && "Fishy thing.  Both operands have the same sign.");
 682
 683     uint64_t Count = Dist1;
 684
 685     if (Count > 0xFFFFFFFFULL)
 686       return 0;
 687
 688     return new CountValue(CountValue::CV_Immediate, Count);
 689   }
 690
 691   // A general case: Start and End are some values, but the actual
 692   // iteration count may not be available.  If it is not, insert
 693   // a computation of it into the preheader.
 694
 695   // If the induction variable bump is not a power of 2, quit.
 696   // Othwerise we'd need a general integer division.
 697   if (!isPowerOf2_64(abs64(IVBump)))
 698     return 0;
 699
 700   MachineBasicBlock *PH = Loop->getLoopPreheader();
 701   assert (PH && "Should have a preheader by now");
 702   MachineBasicBlock::iterator InsertPos = PH->getFirstTerminator();
 703   DebugLoc DL = (InsertPos != PH->end()) ? InsertPos->getDebugLoc()
 704                                          : DebugLoc();
 705
 706   // If Start is an immediate and End is a register, the trip count
 707   // will be "reg - imm".  Hexagon's "subtract immediate" instruction
 708   // is actually "reg + -imm".
 709
 710   // If the loop IV is going downwards, i.e. if the bump is negative,
 711   // then the iteration count (computed as End-Start) will need to be
 712   // negated.  To avoid the negation, just swap Start and End.
 713   if (IVBump < 0) {
 714     std::swap(Start, End);
 715     IVBump = -IVBump;
 716   }
 717   // Cmp may now have a wrong direction, e.g.  LEs may now be GEs.
 718   // Signedness, and "including equality" are preserved.
 719
 720   bool RegToImm = Start->isReg() && End->isImm(); // for (reg..imm)
 721   bool RegToReg = Start->isReg() && End->isReg(); // for (reg..reg)
 722
 723   int64_t StartV = 0, EndV = 0;
 724   if (Start->isImm())
 725     StartV = Start->getImm();
 726   if (End->isImm())
 727     EndV = End->getImm();
 728
 729   int64_t AdjV = 0;
 730   // To compute the iteration count, we would need this computation:
 731   //   Count = (End - Start + (IVBump-1)) / IVBump
 732   // or, when CmpHasEqual:
 733   //   Count = (End - Start + (IVBump-1)+1) / IVBump
 734   // The "IVBump-1" part is the adjustment (AdjV).  We can avoid
 735   // generating an instruction specifically to add it if we can adjust
 736   // the immediate values for Start or End.
 737
 738   if (CmpHasEqual) {
 739     // Need to add 1 to the total iteration count.
 740     if (Start->isImm())
 741       StartV--;
 742     else if (End->isImm())
 743       EndV++;
 744     else
 745       AdjV += 1;
 746   }
 747
 748   if (Cmp != Comparison::NE) {
 749     if (Start->isImm())
 750       StartV -= (IVBump-1);
 751     else if (End->isImm())
 752       EndV += (IVBump-1);
 753     else
 754       AdjV += (IVBump-1);
 755   }
 756
 757   unsigned R = 0, SR = 0;
 758   if (Start->isReg()) {
 759     R = Start->getReg();
 760     SR = Start->getSubReg();
 761   } else {
 762     R = End->getReg();
 763     SR = End->getSubReg();
 764   }
 765   const TargetRegisterClass *RC = MRI->getRegClass(R);
 766   // Hardware loops cannot handle 64-bit registers.  If it's a double
 767   // register, it has to have a subregister.
 768   if (!SR && RC == &Hexagon::DoubleRegsRegClass)
 769     return 0;
 770   const TargetRegisterClass *IntRC = &Hexagon::IntRegsRegClass;
 771
 772   // Compute DistR (register with the distance between Start and End).
 773   unsigned DistR, DistSR;
 774
 775   // Avoid special case, where the start value is an imm(0).
 776   if (Start->isImm() && StartV == 0) {
 777     DistR = End->getReg();
 778     DistSR = End->getSubReg();
 779   } else {
 780     const MCInstrDesc &SubD = RegToReg ? TII->get(Hexagon::SUB_rr) :
 781                               (RegToImm ? TII->get(Hexagon::SUB_ri) :
 782                                           TII->get(Hexagon::ADD_ri));
 783     unsigned SubR = MRI->createVirtualRegister(IntRC);
 784     MachineInstrBuilder SubIB =
 785       BuildMI(*PH, InsertPos, DL, SubD, SubR);
 786
 787     if (RegToReg) {
 788       SubIB.addReg(End->getReg(), 0, End->getSubReg())
 789            .addReg(Start->getReg(), 0, Start->getSubReg());
 790     } else if (RegToImm) {
 791       SubIB.addImm(EndV)
 792            .addReg(Start->getReg(), 0, Start->getSubReg());
 793     } else { // ImmToReg
 794       SubIB.addReg(End->getReg(), 0, End->getSubReg())
 795            .addImm(-StartV);
 796     }
 797     DistR = SubR;
 798     DistSR = 0;
 799   }
 800
 801   // From DistR, compute AdjR (register with the adjusted distance).
 802   unsigned AdjR, AdjSR;
 803
 804   if (AdjV == 0) {
 805     AdjR = DistR;
 806     AdjSR = DistSR;
 807   } else {
 808     // Generate CountR = ADD DistR, AdjVal
 809     unsigned AddR = MRI->createVirtualRegister(IntRC);
 810     const MCInstrDesc &AddD = TII->get(Hexagon::ADD_ri);
 811     BuildMI(*PH, InsertPos, DL, AddD, AddR)
 812       .addReg(DistR, 0, DistSR)
 813       .addImm(AdjV);
 814
 815     AdjR = AddR;
 816     AdjSR = 0;
 817   }
 818
 819   // From AdjR, compute CountR (register with the final count).
 820   unsigned CountR, CountSR;
 821
 822   if (IVBump == 1) {
 823     CountR = AdjR;
 824     CountSR = AdjSR;
 825   } else {
 826     // The IV bump is a power of two. Log_2(IV bump) is the shift amount.
 827     unsigned Shift = Log2_32(IVBump);
 828
 829     // Generate NormR = LSR DistR, Shift.
 830     unsigned LsrR = MRI->createVirtualRegister(IntRC);
 831     const MCInstrDesc &LsrD = TII->get(Hexagon::LSR_ri);
 832     BuildMI(*PH, InsertPos, DL, LsrD, LsrR)
 833       .addReg(AdjR, 0, AdjSR)
 834       .addImm(Shift);
 835
 836     CountR = LsrR;
 837     CountSR = 0;
 838   }
 839
 840   return new CountValue(CountValue::CV_Register, CountR, CountSR);
 841 }
 842
 843
 844 /// \brief Return true if the operation is invalid within hardware loop.
 845 bool HexagonHardwareLoops::isInvalidLoopOperation(
 846       const MachineInstr *MI) const {
 847
 848   // call is not allowed because the callee may use a hardware loop
 849   if (MI->getDesc().isCall())
 850     return true;
 851
 852   // do not allow nested hardware loops
 853   if (isHardwareLoop(MI))
 854     return true;
 855
 856   // check if the instruction defines a hardware loop register
 857   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 858     const MachineOperand &MO = MI->getOperand(i);
 859     if (!MO.isReg() || !MO.isDef())
 860       continue;
 861     unsigned R = MO.getReg();
 862     if (R == Hexagon::LC0 || R == Hexagon::LC1 ||
 863         R == Hexagon::SA0 || R == Hexagon::SA1)
 864       return true;
 865   }
 866   return false;
 867 }
 868
 869
 870 /// \brief - Return true if the loop contains an instruction that inhibits
 871 /// the use of the hardware loop function.
 872 bool HexagonHardwareLoops::containsInvalidInstruction(MachineLoop *L) const {
 873   const std::vector<MachineBasicBlock *> &Blocks = L->getBlocks();
 874   for (unsigned i = 0, e = Blocks.size(); i != e; ++i) {
 875     MachineBasicBlock *MBB = Blocks[i];
 876     for (MachineBasicBlock::iterator
 877            MII = MBB->begin(), E = MBB->end(); MII != E; ++MII) {
 878       const MachineInstr *MI = &*MII;
 879       if (isInvalidLoopOperation(MI))
 880         return true;
 881     }
 882   }
 883   return false;
 884 }
 885
 886
 887 /// \brief Returns true if the instruction is dead.  This was essentially
 888 /// copied from DeadMachineInstructionElim::isDead, but with special cases
 889 /// for inline asm, physical registers and instructions with side effects
 890 /// removed.
 891 bool HexagonHardwareLoops::isDead(const MachineInstr *MI,
 892                               SmallVectorImpl<MachineInstr *> &DeadPhis) const {
 893   // Examine each operand.
 894   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 895     const MachineOperand &MO = MI->getOperand(i);
 896     if (!MO.isReg() || !MO.isDef())
 897       continue;
 898
 899     unsigned Reg = MO.getReg();
 900     if (MRI->use_nodbg_empty(Reg))
 901       continue;
 902
 903     typedef MachineRegisterInfo::use_nodbg_iterator use_nodbg_iterator;
 904
 905     // This instruction has users, but if the only user is the phi node for the
 906     // parent block, and the only use of that phi node is this instruction, then
 907     // this instruction is dead: both it (and the phi node) can be removed.
 908     use_nodbg_iterator I = MRI->use_nodbg_begin(Reg);
 909     use_nodbg_iterator End = MRI->use_nodbg_end();
 910     if (llvm::next(I) != End || !I.getOperand().getParent()->isPHI())
 911       return false;
 912
 913     MachineInstr *OnePhi = I.getOperand().getParent();
 914     for (unsigned j = 0, f = OnePhi->getNumOperands(); j != f; ++j) {
 915       const MachineOperand &OPO = OnePhi->getOperand(j);
 916       if (!OPO.isReg() || !OPO.isDef())
 917         continue;
 918
 919       unsigned OPReg = OPO.getReg();
 920       use_nodbg_iterator nextJ;
 921       for (use_nodbg_iterator J = MRI->use_nodbg_begin(OPReg);
 922            J != End; J = nextJ) {
 923         nextJ = llvm::next(J);
 924         MachineOperand &Use = J.getOperand();
 925         MachineInstr *UseMI = Use.getParent();
 926
 927         // If the phi node has a user that is not MI, bail...
 928         if (MI != UseMI)
 929           return false;
 930       }
 931     }
 932     DeadPhis.push_back(OnePhi);
 933   }
 934
 935   // If there are no defs with uses, the instruction is dead.
 936   return true;
 937 }
 938
 939 void HexagonHardwareLoops::removeIfDead(MachineInstr *MI) {
 940   // This procedure was essentially copied from DeadMachineInstructionElim.
 941
 942   SmallVector<MachineInstr*, 1> DeadPhis;
 943   if (isDead(MI, DeadPhis)) {
 944     DEBUG(dbgs() << "HW looping will remove: " << *MI);
 945
 946     // It is possible that some DBG_VALUE instructions refer to this
 947     // instruction.  Examine each def operand for such references;
 948     // if found, mark the DBG_VALUE as undef (but don't delete it).
 949     for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 950       const MachineOperand &MO = MI->getOperand(i);
 951       if (!MO.isReg() || !MO.isDef())
 952         continue;
 953       unsigned Reg = MO.getReg();
 954       MachineRegisterInfo::use_iterator nextI;
 955       for (MachineRegisterInfo::use_iterator I = MRI->use_begin(Reg),
 956            E = MRI->use_end(); I != E; I = nextI) {
 957         nextI = llvm::next(I);  // I is invalidated by the setReg
 958         MachineOperand &Use = I.getOperand();
 959         MachineInstr *UseMI = Use.getParent();
 960         if (UseMI == MI)
 961           continue;
 962         if (Use.isDebug())
 963           UseMI->getOperand(0).setReg(0U);
 964         // This may also be a "instr -> phi -> instr" case which can
 965         // be removed too.
 966       }
 967     }
 968
 969     MI->eraseFromParent();
 970     for (unsigned i = 0; i < DeadPhis.size(); ++i)
 971       DeadPhis[i]->eraseFromParent();
 972   }
 973 }
 974
 975 /// \brief Check if the loop is a candidate for converting to a hardware
 976 /// loop.  If so, then perform the transformation.
 977 ///
 978 /// This function works on innermost loops first.  A loop can be converted
 979 /// if it is a counting loop; either a register value or an immediate.
 980 ///
 981 /// The code makes several assumptions about the representation of the loop
 982 /// in llvm.
 983 bool HexagonHardwareLoops::convertToHardwareLoop(MachineLoop *L) {
 984   // This is just for sanity.
 985   assert(L->getHeader() && "Loop without a header?");
 986
 987   bool Changed = false;
 988   // Process nested loops first.
 989   for (MachineLoop::iterator I = L->begin(), E = L->end(); I != E; ++I)
 990     Changed |= convertToHardwareLoop(*I);
 991
 992   // If a nested loop has been converted, then we can't convert this loop.
 993   if (Changed)
 994     return Changed;
 995
 996 #ifndef NDEBUG
 997   // Stop trying after reaching the limit (if any).
 998   int Limit = HWLoopLimit;
 999   if (Limit >= 0) {
1000     if (Counter >= HWLoopLimit)
1001       return false;
1002     Counter++;
1003   }
1004 #endif
1005
1006   // Does the loop contain any invalid instructions?
1007   if (containsInvalidInstruction(L))
1008     return false;
1009
1010   // Is the induction variable bump feeding the latch condition?
1011   if (!fixupInductionVariable(L))
1012     return false;
1013
1014   MachineBasicBlock *LastMBB = L->getExitingBlock();
1015   // Don't generate hw loop if the loop has more than one exit.
1016   if (LastMBB == 0)
1017     return false;
1018
1019   MachineBasicBlock::iterator LastI = LastMBB->getFirstTerminator();
1020   if (LastI == LastMBB->end())
1021     return false;
1022
1023   // Ensure the loop has a preheader: the loop instruction will be
1024   // placed there.
1025   bool NewPreheader = false;
1026   MachineBasicBlock *Preheader = L->getLoopPreheader();
1027   if (!Preheader) {
1028     Preheader = createPreheaderForLoop(L);
1029     if (!Preheader)
1030       return false;
1031     NewPreheader = true;
1032   }
1033   MachineBasicBlock::iterator InsertPos = Preheader->getFirstTerminator();
1034
1035   SmallVector<MachineInstr*, 2> OldInsts;
1036   // Are we able to determine the trip count for the loop?
1037   CountValue *TripCount = getLoopTripCount(L, OldInsts);
1038   if (TripCount == 0)
1039     return false;
1040
1041   // Is the trip count available in the preheader?
1042   if (TripCount->isReg()) {
1043     // There will be a use of the register inserted into the preheader,
1044     // so make sure that the register is actually defined at that point.
1045     MachineInstr *TCDef = MRI->getVRegDef(TripCount->getReg());
1046     MachineBasicBlock *BBDef = TCDef->getParent();
1047     if (!NewPreheader) {
1048       if (!MDT->dominates(BBDef, Preheader))
1049         return false;
1050     } else {
1051       // If we have just created a preheader, the dominator tree won't be
1052       // aware of it.  Check if the definition of the register dominates
1053       // the header, but is not the header itself.
1054       if (!MDT->properlyDominates(BBDef, L->getHeader()))
1055         return false;
1056     }
1057   }
1058
1059   // Determine the loop start.
1060   MachineBasicBlock *LoopStart = L->getTopBlock();
1061   if (L->getLoopLatch() != LastMBB) {
1062     // When the exit and latch are not the same, use the latch block as the
1063     // start.
1064     // The loop start address is used only after the 1st iteration, and the
1065     // loop latch may contains instrs. that need to be executed after the
1066     // first iteration.
1067     LoopStart = L->getLoopLatch();
1068     // Make sure the latch is a successor of the exit, otherwise it won't work.
1069     if (!LastMBB->isSuccessor(LoopStart))
1070       return false;
1071   }
1072
1073   // Convert the loop to a hardware loop.
1074   DEBUG(dbgs() << "Change to hardware loop at "; L->dump());
1075   DebugLoc DL;
1076   if (InsertPos != Preheader->end())
1077     DL = InsertPos->getDebugLoc();
1078
1079   if (TripCount->isReg()) {
1080     // Create a copy of the loop count register.
1081     unsigned CountReg = MRI->createVirtualRegister(&Hexagon::IntRegsRegClass);
1082     BuildMI(*Preheader, InsertPos, DL, TII->get(TargetOpcode::COPY), CountReg)
1083       .addReg(TripCount->getReg(), 0, TripCount->getSubReg());
1084     // Add the Loop instruction to the beginning of the loop.
1085     BuildMI(*Preheader, InsertPos, DL, TII->get(Hexagon::LOOP0_r))
1086       .addMBB(LoopStart)
1087       .addReg(CountReg);
1088   } else {
1089     assert(TripCount->isImm() && "Expecting immediate value for trip count");
1090     // Add the Loop immediate instruction to the beginning of the loop,
1091     // if the immediate fits in the instructions.  Otherwise, we need to
1092     // create a new virtual register.
1093     int64_t CountImm = TripCount->getImm();
1094     if (!TII->isValidOffset(Hexagon::LOOP0_i, CountImm)) {
1095       unsigned CountReg = MRI->createVirtualRegister(&Hexagon::IntRegsRegClass);
1096       BuildMI(*Preheader, InsertPos, DL, TII->get(Hexagon::TFRI), CountReg)
1097         .addImm(CountImm);
1098       BuildMI(*Preheader, InsertPos, DL, TII->get(Hexagon::LOOP0_r))
1099         .addMBB(LoopStart).addReg(CountReg);
1100     } else
1101       BuildMI(*Preheader, InsertPos, DL, TII->get(Hexagon::LOOP0_i))
1102         .addMBB(LoopStart).addImm(CountImm);
1103   }
1104
1105   // Make sure the loop start always has a reference in the CFG.  We need
1106   // to create a BlockAddress operand to get this mechanism to work both the
1107   // MachineBasicBlock and BasicBlock objects need the flag set.
1108   LoopStart->setHasAddressTaken();
1109   // This line is needed to set the hasAddressTaken flag on the BasicBlock
1110   // object.
1111   BlockAddress::get(const_cast<BasicBlock *>(LoopStart->getBasicBlock()));
1112
1113   // Replace the loop branch with an endloop instruction.
1114   DebugLoc LastIDL = LastI->getDebugLoc();
1115   BuildMI(*LastMBB, LastI, LastIDL,
1116           TII->get(Hexagon::ENDLOOP0)).addMBB(LoopStart);
1117
1118   // The loop ends with either:
1119   //  - a conditional branch followed by an unconditional branch, or
1120   //  - a conditional branch to the loop start.
1121   if (LastI->getOpcode() == Hexagon::JMP_t ||
1122       LastI->getOpcode() == Hexagon::JMP_f) {
1123     // Delete one and change/add an uncond. branch to out of the loop.
1124     MachineBasicBlock *BranchTarget = LastI->getOperand(1).getMBB();
1125     LastI = LastMBB->erase(LastI);
1126     if (!L->contains(BranchTarget)) {
1127       if (LastI != LastMBB->end())
1128         LastI = LastMBB->erase(LastI);
1129       SmallVector<MachineOperand, 0> Cond;
1130       TII->InsertBranch(*LastMBB, BranchTarget, 0, Cond, LastIDL);
1131     }
1132   } else {
1133     // Conditional branch to loop start; just delete it.
1134     LastMBB->erase(LastI);
1135   }
1136   delete TripCount;
1137
1138   // The induction operation and the comparison may now be
1139   // unneeded. If these are unneeded, then remove them.
1140   for (unsigned i = 0; i < OldInsts.size(); ++i)
1141     removeIfDead(OldInsts[i]);
1142
1143   ++NumHWLoops;
1144   return true;
1145 }
1146
1147
1148 bool HexagonHardwareLoops::orderBumpCompare(MachineInstr *BumpI,
1149                                             MachineInstr *CmpI) {
1150   assert (BumpI != CmpI && "Bump and compare in the same instruction?");
1151
1152   MachineBasicBlock *BB = BumpI->getParent();
1153   if (CmpI->getParent() != BB)
1154     return false;
1155
1156   typedef MachineBasicBlock::instr_iterator instr_iterator;
1157   // Check if things are in order to begin with.
1158   for (instr_iterator I = BumpI, E = BB->instr_end(); I != E; ++I)
1159     if (&*I == CmpI)
1160       return true;
1161
1162   // Out of order.
1163   unsigned PredR = CmpI->getOperand(0).getReg();
1164   bool FoundBump = false;
1165   instr_iterator CmpIt = CmpI, NextIt = llvm::next(CmpIt);
1166   for (instr_iterator I = NextIt, E = BB->instr_end(); I != E; ++I) {
1167     MachineInstr *In = &*I;
1168     for (unsigned i = 0, n = In->getNumOperands(); i < n; ++i) {
1169       MachineOperand &MO = In->getOperand(i);
1170       if (MO.isReg() && MO.isUse()) {
1171         if (MO.getReg() == PredR)  // Found an intervening use of PredR.
1172           return false;
1173       }
1174     }
1175
1176     if (In == BumpI) {
1177       instr_iterator After = BumpI;
1178       instr_iterator From = CmpI;
1179       BB->splice(llvm::next(After), BB, From);
1180       FoundBump = true;
1181       break;
1182     }
1183   }
1184   assert (FoundBump && "Cannot determine instruction order");
1185   return FoundBump;
1186 }
1187
1188
1189 MachineInstr *HexagonHardwareLoops::defWithImmediate(unsigned R) {
1190   MachineInstr *DI = MRI->getVRegDef(R);
1191   unsigned DOpc = DI->getOpcode();
1192   switch (DOpc) {
1193     case Hexagon::TFRI:
1194     case Hexagon::TFRI64:
1195     case Hexagon::CONST32_Int_Real:
1196     case Hexagon::CONST64_Int_Real:
1197       return DI;
1198   }
1199   return 0;
1200 }
1201
1202
1203 int64_t HexagonHardwareLoops::getImmediate(MachineOperand &MO) {
1204   if (MO.isImm())
1205     return MO.getImm();
1206   assert(MO.isReg());
1207   unsigned R = MO.getReg();
1208   MachineInstr *DI = defWithImmediate(R);
1209   assert(DI && "Need an immediate operand");
1210   // All currently supported "define-with-immediate" instructions have the
1211   // actual immediate value in the operand(1).
1212   int64_t v = DI->getOperand(1).getImm();
1213   return v;
1214 }
1215
1216
1217 void HexagonHardwareLoops::setImmediate(MachineOperand &MO, int64_t Val) {
1218   if (MO.isImm()) {
1219     MO.setImm(Val);
1220     return;
1221   }
1222
1223   assert(MO.isReg());
1224   unsigned R = MO.getReg();
1225   MachineInstr *DI = defWithImmediate(R);
1226   if (MRI->hasOneNonDBGUse(R)) {
1227     // If R has only one use, then just change its defining instruction to
1228     // the new immediate value.
1229     DI->getOperand(1).setImm(Val);
1230     return;
1231   }
1232
1233   const TargetRegisterClass *RC = MRI->getRegClass(R);
1234   unsigned NewR = MRI->createVirtualRegister(RC);
1235   MachineBasicBlock &B = *DI->getParent();
1236   DebugLoc DL = DI->getDebugLoc();
1237   BuildMI(B, DI, DL, TII->get(DI->getOpcode()), NewR)
1238     .addImm(Val);
1239   MO.setReg(NewR);
1240 }
1241
1242
1243 bool HexagonHardwareLoops::fixupInductionVariable(MachineLoop *L) {
1244   MachineBasicBlock *Header = L->getHeader();
1245   MachineBasicBlock *Preheader = L->getLoopPreheader();
1246   MachineBasicBlock *Latch = L->getLoopLatch();
1247
1248   if (!Header || !Preheader || !Latch)
1249     return false;
1250
1251   // These data structures follow the same concept as the corresponding
1252   // ones in findInductionRegister (where some comments are).
1253   typedef std::pair<unsigned,int64_t> RegisterBump;
1254   typedef std::pair<unsigned,RegisterBump> RegisterInduction;
1255   typedef std::set<RegisterInduction> RegisterInductionSet;
1256
1257   // Register candidates for induction variables, with their associated bumps.
1258   RegisterInductionSet IndRegs;
1259
1260   // Look for induction patterns:
1261   //   vreg1 = PHI ..., [ latch, vreg2 ]
1262   //   vreg2 = ADD vreg1, imm
1263   typedef MachineBasicBlock::instr_iterator instr_iterator;
1264   for (instr_iterator I = Header->instr_begin(), E = Header->instr_end();
1265        I != E && I->isPHI(); ++I) {
1266     MachineInstr *Phi = &*I;
1267
1268     // Have a PHI instruction.
1269     for (unsigned i = 1, n = Phi->getNumOperands(); i < n; i += 2) {
1270       if (Phi->getOperand(i+1).getMBB() != Latch)
1271         continue;
1272
1273       unsigned PhiReg = Phi->getOperand(i).getReg();
1274       MachineInstr *DI = MRI->getVRegDef(PhiReg);
1275       unsigned UpdOpc = DI->getOpcode();
1276       bool isAdd = (UpdOpc == Hexagon::ADD_ri);
1277
1278       if (isAdd) {
1279         // If the register operand to the add/sub is the PHI we are looking
1280         // at, this meets the induction pattern.
1281         unsigned IndReg = DI->getOperand(1).getReg();
1282         if (MRI->getVRegDef(IndReg) == Phi) {
1283           unsigned UpdReg = DI->getOperand(0).getReg();
1284           int64_t V = DI->getOperand(2).getImm();
1285           IndRegs.insert(std::make_pair(UpdReg, std::make_pair(IndReg, V)));
1286         }
1287       }
1288     }  // for (i)
1289   }  // for (instr)
1290
1291   if (IndRegs.empty())
1292     return false;
1293
1294   MachineBasicBlock *TB = 0, *FB = 0;
1295   SmallVector<MachineOperand,2> Cond;
1296   // AnalyzeBranch returns true if it fails to analyze branch.
1297   bool NotAnalyzed = TII->AnalyzeBranch(*Latch, TB, FB, Cond, false);
1298   if (NotAnalyzed)
1299     return false;
1300
1301   // Check if the latch branch is unconditional.
1302   if (Cond.empty())
1303     return false;
1304
1305   if (TB != Header && FB != Header)
1306     // The latch does not go back to the header.  Not a latch we know and love.
1307     return false;
1308
1309   // Expecting a predicate register as a condition.  It won't be a hardware
1310   // predicate register at this point yet, just a vreg.
1311   // HexagonInstrInfo::AnalyzeBranch for negated branches inserts imm(0)
1312   // into Cond, followed by the predicate register.  For non-negated branches
1313   // it's just the register.
1314   unsigned CSz = Cond.size();
1315   if (CSz != 1 && CSz != 2)
1316     return false;
1317
1318   unsigned P = Cond[CSz-1].getReg();
1319   MachineInstr *PredDef = MRI->getVRegDef(P);
1320
1321   if (!PredDef->isCompare())
1322     return false;
1323
1324   SmallSet<unsigned,2> CmpRegs;
1325   MachineOperand *CmpImmOp = 0;
1326
1327   // Go over all operands to the compare and look for immediate and register
1328   // operands.  Assume that if the compare has a single register use and a
1329   // single immediate operand, then the register is being compared with the
1330   // immediate value.
1331   for (unsigned i = 0, n = PredDef->getNumOperands(); i < n; ++i) {
1332     MachineOperand &MO = PredDef->getOperand(i);
1333     if (MO.isReg()) {
1334       // Skip all implicit references.  In one case there was:
1335       //   %vreg140<def> = FCMPUGT32_rr %vreg138, %vreg139, %USR<imp-use>
1336       if (MO.isImplicit())
1337         continue;
1338       if (MO.isUse()) {
1339         unsigned R = MO.getReg();
1340         if (!defWithImmediate(R)) {
1341           CmpRegs.insert(MO.getReg());
1342           continue;
1343         }
1344         // Consider the register to be the "immediate" operand.
1345         if (CmpImmOp)
1346           return false;
1347         CmpImmOp = &MO;
1348       }
1349     } else if (MO.isImm()) {
1350       if (CmpImmOp)    // A second immediate argument?  Confusing.  Bail out.
1351         return false;
1352       CmpImmOp = &MO;
1353     }
1354   }
1355
1356   if (CmpRegs.empty())
1357     return false;
1358
1359   // Check if the compared register follows the order we want.  Fix if needed.
1360   for (RegisterInductionSet::iterator I = IndRegs.begin(), E = IndRegs.end();
1361        I != E; ++I) {
1362     // This is a success.  If the register used in the comparison is one that
1363     // we have identified as a bumped (updated) induction register, there is
1364     // nothing to do.
1365     if (CmpRegs.count(I->first))
1366       return true;
1367
1368     // Otherwise, if the register being compared comes out of a PHI node,
1369     // and has been recognized as following the induction pattern, and is
1370     // compared against an immediate, we can fix it.
1371     const RegisterBump &RB = I->second;
1372     if (CmpRegs.count(RB.first)) {
1373       if (!CmpImmOp)
1374         return false;
1375
1376       int64_t CmpImm = getImmediate(*CmpImmOp);
1377       int64_t V = RB.second;
1378       if (V > 0 && CmpImm+V < CmpImm)  // Overflow (64-bit).
1379         return false;
1380       if (V < 0 && CmpImm+V > CmpImm)  // Overflow (64-bit).
1381         return false;
1382       CmpImm += V;
1383       // Some forms of cmp-immediate allow u9 and s10.  Assume the worst case
1384       // scenario, i.e. an 8-bit value.
1385       if (CmpImmOp->isImm() && !isInt<8>(CmpImm))
1386         return false;
1387
1388       // Make sure that the compare happens after the bump.  Otherwise,
1389       // after the fixup, the compare would use a yet-undefined register.
1390       MachineInstr *BumpI = MRI->getVRegDef(I->first);
1391       bool Order = orderBumpCompare(BumpI, PredDef);
1392       if (!Order)
1393         return false;
1394
1395       // Finally, fix the compare instruction.
1396       setImmediate(*CmpImmOp, CmpImm);
1397       for (unsigned i = 0, n = PredDef->getNumOperands(); i < n; ++i) {
1398         MachineOperand &MO = PredDef->getOperand(i);
1399         if (MO.isReg() && MO.getReg() == RB.first) {
1400           MO.setReg(I->first);
1401           return true;
1402         }
1403       }
1404     }
1405   }
1406
1407   return false;
1408 }
1409
1410
1411 /// \brief Create a preheader for a given loop.
1412 MachineBasicBlock *HexagonHardwareLoops::createPreheaderForLoop(
1413       MachineLoop *L) {
1414   if (MachineBasicBlock *TmpPH = L->getLoopPreheader())
1415     return TmpPH;
1416
1417   MachineBasicBlock *Header = L->getHeader();
1418   MachineBasicBlock *Latch = L->getLoopLatch();
1419   MachineFunction *MF = Header->getParent();
1420   DebugLoc DL;
1421
1422   if (!Latch || Header->hasAddressTaken())
1423     return 0;
1424
1425   typedef MachineBasicBlock::instr_iterator instr_iterator;
1426
1427   // Verify that all existing predecessors have analyzable branches
1428   // (or no branches at all).
1429   typedef std::vector<MachineBasicBlock*> MBBVector;
1430   MBBVector Preds(Header->pred_begin(), Header->pred_end());
1431   SmallVector<MachineOperand,2> Tmp1;
1432   MachineBasicBlock *TB = 0, *FB = 0;
1433
1434   if (TII->AnalyzeBranch(*Latch, TB, FB, Tmp1, false))
1435     return 0;
1436
1437   for (MBBVector::iterator I = Preds.begin(), E = Preds.end(); I != E; ++I) {
1438     MachineBasicBlock *PB = *I;
1439     if (PB != Latch) {
1440       bool NotAnalyzed = TII->AnalyzeBranch(*PB, TB, FB, Tmp1, false);
1441       if (NotAnalyzed)
1442         return 0;
1443     }
1444   }
1445
1446   MachineBasicBlock *NewPH = MF->CreateMachineBasicBlock();
1447   MF->insert(Header, NewPH);
1448
1449   if (Header->pred_size() > 2) {
1450     // Ensure that the header has only two predecessors: the preheader and
1451     // the loop latch.  Any additional predecessors of the header should
1452     // join at the newly created preheader.  Inspect all PHI nodes from the
1453     // header and create appropriate corresponding PHI nodes in the preheader.
1454
1455     for (instr_iterator I = Header->instr_begin(), E = Header->instr_end();
1456          I != E && I->isPHI(); ++I) {
1457       MachineInstr *PN = &*I;
1458
1459       const MCInstrDesc &PD = TII->get(TargetOpcode::PHI);
1460       MachineInstr *NewPN = MF->CreateMachineInstr(PD, DL);
1461       NewPH->insert(NewPH->end(), NewPN);
1462
1463       unsigned PR = PN->getOperand(0).getReg();
1464       const TargetRegisterClass *RC = MRI->getRegClass(PR);
1465       unsigned NewPR = MRI->createVirtualRegister(RC);
1466       NewPN->addOperand(MachineOperand::CreateReg(NewPR, true));
1467
1468       // Copy all non-latch operands of a header's PHI node to the newly
1469       // created PHI node in the preheader.
1470       for (unsigned i = 1, n = PN->getNumOperands(); i < n; i += 2) {
1471         unsigned PredR = PN->getOperand(i).getReg();
1472         MachineBasicBlock *PredB = PN->getOperand(i+1).getMBB();
1473         if (PredB == Latch)
1474           continue;
1475
1476         NewPN->addOperand(MachineOperand::CreateReg(PredR, false));
1477         NewPN->addOperand(MachineOperand::CreateMBB(PredB));
1478       }
1479
1480       // Remove copied operands from the old PHI node and add the value
1481       // coming from the preheader's PHI.
1482       for (int i = PN->getNumOperands()-2; i > 0; i -= 2) {
1483         MachineBasicBlock *PredB = PN->getOperand(i+1).getMBB();
1484         if (PredB != Latch) {
1485           PN->RemoveOperand(i+1);
1486           PN->RemoveOperand(i);
1487         }
1488       }
1489       PN->addOperand(MachineOperand::CreateReg(NewPR, false));
1490       PN->addOperand(MachineOperand::CreateMBB(NewPH));
1491     }
1492
1493   } else {
1494     assert(Header->pred_size() == 2);
1495
1496     // The header has only two predecessors, but the non-latch predecessor
1497     // is not a preheader (e.g. it has other successors, etc.)
1498     // In such a case we don't need any extra PHI nodes in the new preheader,
1499     // all we need is to adjust existing PHIs in the header to now refer to
1500     // the new preheader.
1501     for (instr_iterator I = Header->instr_begin(), E = Header->instr_end();
1502          I != E && I->isPHI(); ++I) {
1503       MachineInstr *PN = &*I;
1504       for (unsigned i = 1, n = PN->getNumOperands(); i < n; i += 2) {
1505         MachineOperand &MO = PN->getOperand(i+1);
1506         if (MO.getMBB() != Latch)
1507           MO.setMBB(NewPH);
1508       }
1509     }
1510   }
1511
1512   // "Reroute" the CFG edges to link in the new preheader.
1513   // If any of the predecessors falls through to the header, insert a branch
1514   // to the new preheader in that place.
1515   SmallVector<MachineOperand,1> Tmp2;
1516   SmallVector<MachineOperand,1> EmptyCond;
1517
1518   TB = FB = 0;
1519
1520   for (MBBVector::iterator I = Preds.begin(), E = Preds.end(); I != E; ++I) {
1521     MachineBasicBlock *PB = *I;
1522     if (PB != Latch) {
1523       Tmp2.clear();
1524       bool NotAnalyzed = TII->AnalyzeBranch(*PB, TB, FB, Tmp2, false);
1525       (void)NotAnalyzed; // supress compiler warning
1526       assert (!NotAnalyzed && "Should be analyzable!");
1527       if (TB != Header && (Tmp2.empty() || FB != Header))
1528         TII->InsertBranch(*PB, NewPH, 0, EmptyCond, DL);
1529       PB->ReplaceUsesOfBlockWith(Header, NewPH);
1530     }
1531   }
1532
1533   // It can happen that the latch block will fall through into the header.
1534   // Insert an unconditional branch to the header.
1535   TB = FB = 0;
1536   bool LatchNotAnalyzed = TII->AnalyzeBranch(*Latch, TB, FB, Tmp2, false);
1537   (void)LatchNotAnalyzed; // supress compiler warning
1538   assert (!LatchNotAnalyzed && "Should be analyzable!");
1539   if (!TB && !FB)
1540     TII->InsertBranch(*Latch, Header, 0, EmptyCond, DL);
1541
1542   // Finally, the branch from the preheader to the header.
1543   TII->InsertBranch(*NewPH, Header, 0, EmptyCond, DL);
1544   NewPH->addSuccessor(Header);
1545
1546   return NewPH;
1547 }