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 "Hexagon.h"
  31 #include "HexagonTargetMachine.h"
  32 #include "llvm/Constants.h"
  33 #include "llvm/PassSupport.h"
  34 #include "llvm/ADT/DenseMap.h"
  35 #include "llvm/ADT/Statistic.h"
  36 #include "llvm/CodeGen/Passes.h"
  37 #include "llvm/CodeGen/MachineDominators.h"
  38 #include "llvm/CodeGen/MachineFunction.h"
  39 #include "llvm/CodeGen/MachineFunctionPass.h"
  40 #include "llvm/CodeGen/MachineInstrBuilder.h"
  41 #include "llvm/CodeGen/MachineLoopInfo.h"
  42 #include "llvm/CodeGen/MachineRegisterInfo.h"
  43 #include "llvm/CodeGen/RegisterScavenging.h"
  44 #include "llvm/Support/Debug.h"
  45 #include "llvm/Support/raw_ostream.h"
  46 #include "llvm/Target/TargetInstrInfo.h"
  47 #include <algorithm>
  48
  49 using namespace llvm;
  50
  51 STATISTIC(NumHWLoops, "Number of loops converted to hardware loops");
  52
  53 namespace {
  54   class CountValue;
  55   struct HexagonHardwareLoops : public MachineFunctionPass {
  56     MachineLoopInfo       *MLI;
  57     MachineRegisterInfo   *MRI;
  58     const TargetInstrInfo *TII;
  59
  60   public:
  61     static char ID;   // Pass identification, replacement for typeid
  62
  63     HexagonHardwareLoops() : MachineFunctionPass(ID) {}
  64
  65     virtual bool runOnMachineFunction(MachineFunction &MF);
  66
  67     const char *getPassName() const { return "Hexagon Hardware Loops"; }
  68
  69     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  70       AU.setPreservesCFG();
  71       AU.addRequired<MachineDominatorTree>();
  72       AU.addPreserved<MachineDominatorTree>();
  73       AU.addRequired<MachineLoopInfo>();
  74       AU.addPreserved<MachineLoopInfo>();
  75       MachineFunctionPass::getAnalysisUsage(AU);
  76     }
  77
  78   private:
  79     /// getCanonicalInductionVariable - Check to see if the loop has a canonical
  80     /// induction variable.
  81     /// Should be defined in MachineLoop. Based upon version in class Loop.
  82     const MachineInstr *getCanonicalInductionVariable(MachineLoop *L) const;
  83
  84     /// getTripCount - Return a loop-invariant LLVM register indicating the
  85     /// number of times the loop will be executed.  If the trip-count cannot
  86     /// be determined, this return null.
  87     CountValue *getTripCount(MachineLoop *L) const;
  88
  89     /// isInductionOperation - Return true if the instruction matches the
  90     /// pattern for an opertion that defines an induction variable.
  91     bool isInductionOperation(const MachineInstr *MI, unsigned IVReg) const;
  92
  93     /// isInvalidOperation - Return true if the instruction is not valid within
  94     /// a hardware loop.
  95     bool isInvalidLoopOperation(const MachineInstr *MI) const;
  96
  97     /// containsInavlidInstruction - Return true if the loop contains an
  98     /// instruction that inhibits using the hardware loop.
  99     bool containsInvalidInstruction(MachineLoop *L) const;
 100
 101     /// converToHardwareLoop - Given a loop, check if we can convert it to a
 102     /// hardware loop.  If so, then perform the conversion and return true.
 103     bool convertToHardwareLoop(MachineLoop *L);
 104
 105   };
 106
 107   char HexagonHardwareLoops::ID = 0;
 108
 109
 110   // CountValue class - Abstraction for a trip count of a loop. A
 111   // smaller vesrsion of the MachineOperand class without the concerns
 112   // of changing the operand representation.
 113   class CountValue {
 114   public:
 115     enum CountValueType {
 116       CV_Register,
 117       CV_Immediate
 118     };
 119   private:
 120     CountValueType Kind;
 121     union Values {
 122       unsigned RegNum;
 123       int64_t ImmVal;
 124       Values(unsigned r) : RegNum(r) {}
 125       Values(int64_t i) : ImmVal(i) {}
 126     } Contents;
 127     bool isNegative;
 128
 129   public:
 130     CountValue(unsigned r, bool neg) : Kind(CV_Register), Contents(r),
 131                                        isNegative(neg) {}
 132     explicit CountValue(int64_t i) : Kind(CV_Immediate), Contents(i),
 133                                      isNegative(i < 0) {}
 134     CountValueType getType() const { return Kind; }
 135     bool isReg() const { return Kind == CV_Register; }
 136     bool isImm() const { return Kind == CV_Immediate; }
 137     bool isNeg() const { return isNegative; }
 138
 139     unsigned getReg() const {
 140       assert(isReg() && "Wrong CountValue accessor");
 141       return Contents.RegNum;
 142     }
 143     void setReg(unsigned Val) {
 144       Contents.RegNum = Val;
 145     }
 146     int64_t getImm() const {
 147       assert(isImm() && "Wrong CountValue accessor");
 148       if (isNegative) {
 149         return -Contents.ImmVal;
 150       }
 151       return Contents.ImmVal;
 152     }
 153     void setImm(int64_t Val) {
 154       Contents.ImmVal = Val;
 155     }
 156
 157     void print(raw_ostream &OS, const TargetMachine *TM = 0) const {
 158       if (isReg()) { OS << PrintReg(getReg()); }
 159       if (isImm()) { OS << getImm(); }
 160     }
 161   };
 162
 163   struct HexagonFixupHwLoops : public MachineFunctionPass {
 164   public:
 165     static char ID;     // Pass identification, replacement for typeid.
 166
 167     HexagonFixupHwLoops() : MachineFunctionPass(ID) {}
 168
 169     virtual bool runOnMachineFunction(MachineFunction &MF);
 170
 171     const char *getPassName() const { return "Hexagon Hardware Loop Fixup"; }
 172
 173     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 174       AU.setPreservesCFG();
 175       MachineFunctionPass::getAnalysisUsage(AU);
 176     }
 177
 178   private:
 179     /// Maximum distance between the loop instr and the basic block.
 180     /// Just an estimate.
 181     static const unsigned MAX_LOOP_DISTANCE = 200;
 182
 183     /// fixupLoopInstrs - Check the offset between each loop instruction and
 184     /// the loop basic block to determine if we can use the LOOP instruction
 185     /// or if we need to set the LC/SA registers explicitly.
 186     bool fixupLoopInstrs(MachineFunction &MF);
 187
 188     /// convertLoopInstr - Add the instruction to set the LC and SA registers
 189     /// explicitly.
 190     void convertLoopInstr(MachineFunction &MF,
 191                           MachineBasicBlock::iterator &MII,
 192                           RegScavenger &RS);
 193
 194   };
 195
 196   char HexagonFixupHwLoops::ID = 0;
 197
 198 } // end anonymous namespace
 199
 200
 201 /// isHardwareLoop - Returns true if the instruction is a hardware loop
 202 /// instruction.
 203 static bool isHardwareLoop(const MachineInstr *MI) {
 204   return MI->getOpcode() == Hexagon::LOOP0_r ||
 205     MI->getOpcode() == Hexagon::LOOP0_i;
 206 }
 207
 208 /// isCompareEquals - Returns true if the instruction is a compare equals
 209 /// instruction with an immediate operand.
 210 static bool isCompareEqualsImm(const MachineInstr *MI) {
 211   return MI->getOpcode() == Hexagon::CMPEQri;
 212 }
 213
 214
 215 /// createHexagonHardwareLoops - Factory for creating
 216 /// the hardware loop phase.
 217 FunctionPass *llvm::createHexagonHardwareLoops() {
 218   return new HexagonHardwareLoops();
 219 }
 220
 221
 222 bool HexagonHardwareLoops::runOnMachineFunction(MachineFunction &MF) {
 223   DEBUG(dbgs() << "********* Hexagon Hardware Loops *********\n");
 224
 225   bool Changed = false;
 226
 227   // get the loop information
 228   MLI = &getAnalysis<MachineLoopInfo>();
 229   // get the register information
 230   MRI = &MF.getRegInfo();
 231   // the target specific instructio info.
 232   TII = MF.getTarget().getInstrInfo();
 233
 234   for (MachineLoopInfo::iterator I = MLI->begin(), E = MLI->end();
 235        I != E; ++I) {
 236     MachineLoop *L = *I;
 237     if (!L->getParentLoop()) {
 238       Changed |= convertToHardwareLoop(L);
 239     }
 240   }
 241
 242   return Changed;
 243 }
 244
 245 /// getCanonicalInductionVariable - Check to see if the loop has a canonical
 246 /// induction variable. We check for a simple recurrence pattern - an
 247 /// integer recurrence that decrements by one each time through the loop and
 248 /// ends at zero.  If so, return the phi node that corresponds to it.
 249 ///
 250 /// Based upon the similar code in LoopInfo except this code is specific to
 251 /// the machine.
 252 /// This method assumes that the IndVarSimplify pass has been run by 'opt'.
 253 ///
 254 const MachineInstr
 255 *HexagonHardwareLoops::getCanonicalInductionVariable(MachineLoop *L) const {
 256   MachineBasicBlock *TopMBB = L->getTopBlock();
 257   MachineBasicBlock::pred_iterator PI = TopMBB->pred_begin();
 258   assert(PI != TopMBB->pred_end() &&
 259          "Loop must have more than one incoming edge!");
 260   MachineBasicBlock *Backedge = *PI++;
 261   if (PI == TopMBB->pred_end()) return 0;  // dead loop
 262   MachineBasicBlock *Incoming = *PI++;
 263   if (PI != TopMBB->pred_end()) return 0;  // multiple backedges?
 264
 265   // make sure there is one incoming and one backedge and determine which
 266   // is which.
 267   if (L->contains(Incoming)) {
 268     if (L->contains(Backedge))
 269       return 0;
 270     std::swap(Incoming, Backedge);
 271   } else if (!L->contains(Backedge))
 272     return 0;
 273
 274   // Loop over all of the PHI nodes, looking for a canonical induction variable:
 275   //   - The PHI node is "reg1 = PHI reg2, BB1, reg3, BB2".
 276   //   - The recurrence comes from the backedge.
 277   //   - the definition is an induction operatio.n
 278   for (MachineBasicBlock::iterator I = TopMBB->begin(), E = TopMBB->end();
 279        I != E && I->isPHI(); ++I) {
 280     const MachineInstr *MPhi = &*I;
 281     unsigned DefReg = MPhi->getOperand(0).getReg();
 282     for (unsigned i = 1; i != MPhi->getNumOperands(); i += 2) {
 283       // Check each operand for the value from the backedge.
 284       MachineBasicBlock *MBB = MPhi->getOperand(i+1).getMBB();
 285       if (L->contains(MBB)) { // operands comes from the backedge
 286         // Check if the definition is an induction operation.
 287         const MachineInstr *DI = MRI->getVRegDef(MPhi->getOperand(i).getReg());
 288         if (isInductionOperation(DI, DefReg)) {
 289           return MPhi;
 290         }
 291       }
 292     }
 293   }
 294   return 0;
 295 }
 296
 297 /// getTripCount - Return a loop-invariant LLVM value indicating the
 298 /// number of times the loop will be executed.  The trip count can
 299 /// be either a register or a constant value.  If the trip-count
 300 /// cannot be determined, this returns null.
 301 ///
 302 /// We find the trip count from the phi instruction that defines the
 303 /// induction variable.  We follow the links to the CMP instruction
 304 /// to get the trip count.
 305 ///
 306 /// Based upon getTripCount in LoopInfo.
 307 ///
 308 CountValue *HexagonHardwareLoops::getTripCount(MachineLoop *L) const {
 309   // Check that the loop has a induction variable.
 310   const MachineInstr *IV_Inst = getCanonicalInductionVariable(L);
 311   if (IV_Inst == 0) return 0;
 312
 313   // Canonical loops will end with a 'cmpeq_ri IV, Imm',
 314   //  if Imm is 0, get the count from the PHI opnd
 315   //  if Imm is -M, than M is the count
 316   //  Otherwise, Imm is the count
 317   const MachineOperand *IV_Opnd;
 318   const MachineOperand *InitialValue;
 319   if (!L->contains(IV_Inst->getOperand(2).getMBB())) {
 320     InitialValue = &IV_Inst->getOperand(1);
 321     IV_Opnd = &IV_Inst->getOperand(3);
 322   } else {
 323     InitialValue = &IV_Inst->getOperand(3);
 324     IV_Opnd = &IV_Inst->getOperand(1);
 325   }
 326
 327   // Look for the cmp instruction to determine if we
 328   // can get a useful trip count.  The trip count can
 329   // be either a register or an immediate.  The location
 330   // of the value depends upon the type (reg or imm).
 331   while ((IV_Opnd = IV_Opnd->getNextOperandForReg())) {
 332     const MachineInstr *MI = IV_Opnd->getParent();
 333     if (L->contains(MI) && isCompareEqualsImm(MI)) {
 334       const MachineOperand &MO = MI->getOperand(2);
 335       assert(MO.isImm() && "IV Cmp Operand should be 0");
 336       int64_t ImmVal = MO.getImm();
 337
 338       const MachineInstr *IV_DefInstr = MRI->getVRegDef(IV_Opnd->getReg());
 339       assert(L->contains(IV_DefInstr->getParent()) &&
 340              "IV definition should occurs in loop");
 341       int64_t iv_value = IV_DefInstr->getOperand(2).getImm();
 342
 343       if (ImmVal == 0) {
 344         // Make sure the induction variable changes by one on each iteration.
 345         if (iv_value != 1 && iv_value != -1) {
 346           return 0;
 347         }
 348         return new CountValue(InitialValue->getReg(), iv_value > 0);
 349       } else {
 350         assert(InitialValue->isReg() && "Expecting register for init value");
 351         const MachineInstr *DefInstr = MRI->getVRegDef(InitialValue->getReg());
 352         if (DefInstr && DefInstr->getOpcode() == Hexagon::TFRI) {
 353           int64_t count = ImmVal - DefInstr->getOperand(1).getImm();
 354           if ((count % iv_value) != 0) {
 355             return 0;
 356           }
 357           return new CountValue(count/iv_value);
 358         }
 359       }
 360     }
 361   }
 362   return 0;
 363 }
 364
 365 /// isInductionOperation - return true if the operation is matches the
 366 /// pattern that defines an induction variable:
 367 ///    add iv, c
 368 ///
 369 bool
 370 HexagonHardwareLoops::isInductionOperation(const MachineInstr *MI,
 371                                            unsigned IVReg) const {
 372   return (MI->getOpcode() ==
 373           Hexagon::ADD_ri && MI->getOperand(1).getReg() == IVReg);
 374 }
 375
 376 /// isInvalidOperation - Return true if the operation is invalid within
 377 /// hardware loop.
 378 bool
 379 HexagonHardwareLoops::isInvalidLoopOperation(const MachineInstr *MI) const {
 380
 381   // call is not allowed because the callee may use a hardware loop
 382   if (MI->getDesc().isCall()) {
 383     return true;
 384   }
 385   // do not allow nested hardware loops
 386   if (isHardwareLoop(MI)) {
 387     return true;
 388   }
 389   // check if the instruction defines a hardware loop register
 390   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 391     const MachineOperand &MO = MI->getOperand(i);
 392     if (MO.isReg() && MO.isDef() &&
 393         (MO.getReg() == Hexagon::LC0 || MO.getReg() == Hexagon::LC1 ||
 394          MO.getReg() == Hexagon::SA0 || MO.getReg() == Hexagon::SA0)) {
 395       return true;
 396     }
 397   }
 398   return false;
 399 }
 400
 401 /// containsInvalidInstruction - Return true if the loop contains
 402 /// an instruction that inhibits the use of the hardware loop function.
 403 ///
 404 bool HexagonHardwareLoops::containsInvalidInstruction(MachineLoop *L) const {
 405   const std::vector<MachineBasicBlock*> Blocks = L->getBlocks();
 406   for (unsigned i = 0, e = Blocks.size(); i != e; ++i) {
 407     MachineBasicBlock *MBB = Blocks[i];
 408     for (MachineBasicBlock::iterator
 409            MII = MBB->begin(), E = MBB->end(); MII != E; ++MII) {
 410       const MachineInstr *MI = &*MII;
 411       if (isInvalidLoopOperation(MI)) {
 412         return true;
 413       }
 414     }
 415   }
 416   return false;
 417 }
 418
 419 /// converToHardwareLoop - check if the loop is a candidate for
 420 /// converting to a hardware loop.  If so, then perform the
 421 /// transformation.
 422 ///
 423 /// This function works on innermost loops first.  A loop can
 424 /// be converted if it is a counting loop; either a register
 425 /// value or an immediate.
 426 ///
 427 /// The code makes several assumptions about the representation
 428 /// of the loop in llvm.
 429 bool HexagonHardwareLoops::convertToHardwareLoop(MachineLoop *L) {
 430   bool Changed = false;
 431   // Process nested loops first.
 432   for (MachineLoop::iterator I = L->begin(), E = L->end(); I != E; ++I) {
 433     Changed |= convertToHardwareLoop(*I);
 434   }
 435   // If a nested loop has been converted, then we can't convert this loop.
 436   if (Changed) {
 437     return Changed;
 438   }
 439   // Are we able to determine the trip count for the loop?
 440   CountValue *TripCount = getTripCount(L);
 441   if (TripCount == 0) {
 442     return false;
 443   }
 444   // Does the loop contain any invalid instructions?
 445   if (containsInvalidInstruction(L)) {
 446     return false;
 447   }
 448   MachineBasicBlock *Preheader = L->getLoopPreheader();
 449   // No preheader means there's not place for the loop instr.
 450   if (Preheader == 0) {
 451     return false;
 452   }
 453   MachineBasicBlock::iterator InsertPos = Preheader->getFirstTerminator();
 454
 455   MachineBasicBlock *LastMBB = L->getExitingBlock();
 456   // Don't generate hw loop if the loop has more than one exit.
 457   if (LastMBB == 0) {
 458     return false;
 459   }
 460   MachineBasicBlock::iterator LastI = LastMBB->getFirstTerminator();
 461
 462   // Determine the loop start.
 463   MachineBasicBlock *LoopStart = L->getTopBlock();
 464   if (L->getLoopLatch() != LastMBB) {
 465     // When the exit and latch are not the same, use the latch block as the
 466     // start.
 467     // The loop start address is used only after the 1st iteration, and the loop
 468     // latch may contains instrs. that need to be executed after the 1st iter.
 469     LoopStart = L->getLoopLatch();
 470     // Make sure the latch is a successor of the exit, otherwise it won't work.
 471     if (!LastMBB->isSuccessor(LoopStart)) {
 472       return false;
 473     }
 474   }
 475
 476   // Convert the loop to a hardware loop
 477   DEBUG(dbgs() << "Change to hardware loop at "; L->dump());
 478
 479   if (TripCount->isReg()) {
 480     // Create a copy of the loop count register.
 481     MachineFunction *MF = LastMBB->getParent();
 482     const TargetRegisterClass *RC =
 483       MF->getRegInfo().getRegClass(TripCount->getReg());
 484     unsigned CountReg = MF->getRegInfo().createVirtualRegister(RC);
 485     BuildMI(*Preheader, InsertPos, InsertPos->getDebugLoc(),
 486             TII->get(TargetOpcode::COPY), CountReg).addReg(TripCount->getReg());
 487     if (TripCount->isNeg()) {
 488       unsigned CountReg1 = CountReg;
 489       CountReg = MF->getRegInfo().createVirtualRegister(RC);
 490       BuildMI(*Preheader, InsertPos, InsertPos->getDebugLoc(),
 491               TII->get(Hexagon::NEG), CountReg).addReg(CountReg1);
 492     }
 493
 494     // Add the Loop instruction to the begining of the loop.
 495     BuildMI(*Preheader, InsertPos, InsertPos->getDebugLoc(),
 496             TII->get(Hexagon::LOOP0_r)).addMBB(LoopStart).addReg(CountReg);
 497   } else {
 498     assert(TripCount->isImm() && "Expecting immedate vaule for trip count");
 499     // Add the Loop immediate instruction to the beginning of the loop.
 500     int64_t CountImm = TripCount->getImm();
 501     BuildMI(*Preheader, InsertPos, InsertPos->getDebugLoc(),
 502             TII->get(Hexagon::LOOP0_i)).addMBB(LoopStart).addImm(CountImm);
 503   }
 504
 505   // Make sure the loop start always has a reference in the CFG.  We need to
 506   // create a BlockAddress operand to get this mechanism to work both the
 507   // MachineBasicBlock and BasicBlock objects need the flag set.
 508   LoopStart->setHasAddressTaken();
 509   // This line is needed to set the hasAddressTaken flag on the BasicBlock
 510   // object
 511   BlockAddress::get(const_cast<BasicBlock *>(LoopStart->getBasicBlock()));
 512
 513   // Replace the loop branch with an endloop instruction.
 514   DebugLoc dl = LastI->getDebugLoc();
 515   BuildMI(*LastMBB, LastI, dl, TII->get(Hexagon::ENDLOOP0)).addMBB(LoopStart);
 516
 517   // The loop ends with either:
 518   //  - a conditional branch followed by an unconditional branch, or
 519   //  - a conditional branch to the loop start.
 520   if (LastI->getOpcode() == Hexagon::JMP_c ||
 521       LastI->getOpcode() == Hexagon::JMP_cNot) {
 522     // delete one and change/add an uncond. branch to out of the loop
 523     MachineBasicBlock *BranchTarget = LastI->getOperand(1).getMBB();
 524     LastI = LastMBB->erase(LastI);
 525     if (!L->contains(BranchTarget)) {
 526       if (LastI != LastMBB->end()) {
 527         TII->RemoveBranch(*LastMBB);
 528       }
 529       SmallVector<MachineOperand, 0> Cond;
 530       TII->InsertBranch(*LastMBB, BranchTarget, 0, Cond, dl);
 531     }
 532   } else {
 533     // Conditional branch to loop start; just delete it.
 534     LastMBB->erase(LastI);
 535   }
 536   delete TripCount;
 537
 538   ++NumHWLoops;
 539   return true;
 540 }
 541
 542 /// createHexagonFixupHwLoops - Factory for creating the hardware loop
 543 /// phase.
 544 FunctionPass *llvm::createHexagonFixupHwLoops() {
 545   return new HexagonFixupHwLoops();
 546 }
 547
 548 bool HexagonFixupHwLoops::runOnMachineFunction(MachineFunction &MF) {
 549   DEBUG(dbgs() << "****** Hexagon Hardware Loop Fixup ******\n");
 550
 551   bool Changed = fixupLoopInstrs(MF);
 552   return Changed;
 553 }
 554
 555 /// fixupLoopInsts - For Hexagon, if the loop label is to far from the
 556 /// loop instruction then we need to set the LC0 and SA0 registers
 557 /// explicitly instead of using LOOP(start,count).  This function
 558 /// checks the distance, and generates register assignments if needed.
 559 ///
 560 /// This function makes two passes over the basic blocks.  The first
 561 /// pass computes the offset of the basic block from the start.
 562 /// The second pass checks all the loop instructions.
 563 bool HexagonFixupHwLoops::fixupLoopInstrs(MachineFunction &MF) {
 564
 565   // Offset of the current instruction from the start.
 566   unsigned InstOffset = 0;
 567   // Map for each basic block to it's first instruction.
 568   DenseMap<MachineBasicBlock*, unsigned> BlockToInstOffset;
 569
 570   // First pass - compute the offset of each basic block.
 571   for (MachineFunction::iterator MBB = MF.begin(), MBBe = MF.end();
 572        MBB != MBBe; ++MBB) {
 573     BlockToInstOffset[MBB] = InstOffset;
 574     InstOffset += (MBB->size() * 4);
 575   }
 576
 577   // Second pass - check each loop instruction to see if it needs to
 578   // be converted.
 579   InstOffset = 0;
 580   bool Changed = false;
 581   RegScavenger RS;
 582
 583   // Loop over all the basic blocks.
 584   for (MachineFunction::iterator MBB = MF.begin(), MBBe = MF.end();
 585        MBB != MBBe; ++MBB) {
 586     InstOffset = BlockToInstOffset[MBB];
 587     RS.enterBasicBlock(MBB);
 588
 589     // Loop over all the instructions.
 590     MachineBasicBlock::iterator MIE = MBB->end();
 591     MachineBasicBlock::iterator MII = MBB->begin();
 592     while (MII != MIE) {
 593       if (isHardwareLoop(MII)) {
 594         RS.forward(MII);
 595         assert(MII->getOperand(0).isMBB() &&
 596                "Expect a basic block as loop operand");
 597         int diff = InstOffset - BlockToInstOffset[MII->getOperand(0).getMBB()];
 598         diff = (diff > 0 ? diff : -diff);
 599         if ((unsigned)diff > MAX_LOOP_DISTANCE) {
 600           // Convert to explicity setting LC0 and SA0.
 601           convertLoopInstr(MF, MII, RS);
 602           MII = MBB->erase(MII);
 603           Changed = true;
 604         } else {
 605           ++MII;
 606         }
 607       } else {
 608         ++MII;
 609       }
 610       InstOffset += 4;
 611     }
 612   }
 613
 614   return Changed;
 615
 616 }
 617
 618 /// convertLoopInstr - convert a loop instruction to a sequence of instructions
 619 /// that set the lc and sa register explicitly.
 620 void HexagonFixupHwLoops::convertLoopInstr(MachineFunction &MF,
 621                                            MachineBasicBlock::iterator &MII,
 622                                            RegScavenger &RS) {
 623   const TargetInstrInfo *TII = MF.getTarget().getInstrInfo();
 624   MachineBasicBlock *MBB = MII->getParent();
 625   DebugLoc DL = MII->getDebugLoc();
 626   unsigned Scratch = RS.scavengeRegister(Hexagon::IntRegsRegisterClass, MII, 0);
 627
 628   // First, set the LC0 with the trip count.
 629   if (MII->getOperand(1).isReg()) {
 630     // Trip count is a register
 631     BuildMI(*MBB, MII, DL, TII->get(Hexagon::TFCR), Hexagon::LC0)
 632       .addReg(MII->getOperand(1).getReg());
 633   } else {
 634     // Trip count is an immediate.
 635     BuildMI(*MBB, MII, DL, TII->get(Hexagon::TFRI), Scratch)
 636       .addImm(MII->getOperand(1).getImm());
 637     BuildMI(*MBB, MII, DL, TII->get(Hexagon::TFCR), Hexagon::LC0)
 638       .addReg(Scratch);
 639   }
 640   // Then, set the SA0 with the loop start address.
 641   BuildMI(*MBB, MII, DL, TII->get(Hexagon::CONST32_Label), Scratch)
 642     .addMBB(MII->getOperand(0).getMBB());
 643   BuildMI(*MBB, MII, DL, TII->get(Hexagon::TFCR), Hexagon::SA0).addReg(Scratch);
 644 }