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/ADT/DenseMap.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/CodeGen/Passes.h"
  41 #include "llvm/CodeGen/RegisterScavenging.h"
  42 #include "llvm/Constants.h"
  43 #include "llvm/PassSupport.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   for (MachineRegisterInfo::reg_iterator
 332        RI = MRI->reg_begin(IV_Opnd->getReg()), RE = MRI->reg_end();
 333        RI != RE; ++RI) {
 334     IV_Opnd = &RI.getOperand();
 335     const MachineInstr *MI = IV_Opnd->getParent();
 336     if (L->contains(MI) && isCompareEqualsImm(MI)) {
 337       const MachineOperand &MO = MI->getOperand(2);
 338       assert(MO.isImm() && "IV Cmp Operand should be 0");
 339       int64_t ImmVal = MO.getImm();
 340
 341       const MachineInstr *IV_DefInstr = MRI->getVRegDef(IV_Opnd->getReg());
 342       assert(L->contains(IV_DefInstr->getParent()) &&
 343              "IV definition should occurs in loop");
 344       int64_t iv_value = IV_DefInstr->getOperand(2).getImm();
 345
 346       if (ImmVal == 0) {
 347         // Make sure the induction variable changes by one on each iteration.
 348         if (iv_value != 1 && iv_value != -1) {
 349           return 0;
 350         }
 351         return new CountValue(InitialValue->getReg(), iv_value > 0);
 352       } else {
 353         assert(InitialValue->isReg() && "Expecting register for init value");
 354         const MachineInstr *DefInstr = MRI->getVRegDef(InitialValue->getReg());
 355         if (DefInstr && DefInstr->getOpcode() == Hexagon::TFRI) {
 356           int64_t count = ImmVal - DefInstr->getOperand(1).getImm();
 357           if ((count % iv_value) != 0) {
 358             return 0;
 359           }
 360           return new CountValue(count/iv_value);
 361         }
 362       }
 363     }
 364   }
 365   return 0;
 366 }
 367
 368 /// isInductionOperation - return true if the operation is matches the
 369 /// pattern that defines an induction variable:
 370 ///    add iv, c
 371 ///
 372 bool
 373 HexagonHardwareLoops::isInductionOperation(const MachineInstr *MI,
 374                                            unsigned IVReg) const {
 375   return (MI->getOpcode() ==
 376           Hexagon::ADD_ri && MI->getOperand(1).getReg() == IVReg);
 377 }
 378
 379 /// isInvalidOperation - Return true if the operation is invalid within
 380 /// hardware loop.
 381 bool
 382 HexagonHardwareLoops::isInvalidLoopOperation(const MachineInstr *MI) const {
 383
 384   // call is not allowed because the callee may use a hardware loop
 385   if (MI->getDesc().isCall()) {
 386     return true;
 387   }
 388   // do not allow nested hardware loops
 389   if (isHardwareLoop(MI)) {
 390     return true;
 391   }
 392   // check if the instruction defines a hardware loop register
 393   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 394     const MachineOperand &MO = MI->getOperand(i);
 395     if (MO.isReg() && MO.isDef() &&
 396         (MO.getReg() == Hexagon::LC0 || MO.getReg() == Hexagon::LC1 ||
 397          MO.getReg() == Hexagon::SA0 || MO.getReg() == Hexagon::SA0)) {
 398       return true;
 399     }
 400   }
 401   return false;
 402 }
 403
 404 /// containsInvalidInstruction - Return true if the loop contains
 405 /// an instruction that inhibits the use of the hardware loop function.
 406 ///
 407 bool HexagonHardwareLoops::containsInvalidInstruction(MachineLoop *L) const {
 408   const std::vector<MachineBasicBlock*> Blocks = L->getBlocks();
 409   for (unsigned i = 0, e = Blocks.size(); i != e; ++i) {
 410     MachineBasicBlock *MBB = Blocks[i];
 411     for (MachineBasicBlock::iterator
 412            MII = MBB->begin(), E = MBB->end(); MII != E; ++MII) {
 413       const MachineInstr *MI = &*MII;
 414       if (isInvalidLoopOperation(MI)) {
 415         return true;
 416       }
 417     }
 418   }
 419   return false;
 420 }
 421
 422 /// converToHardwareLoop - check if the loop is a candidate for
 423 /// converting to a hardware loop.  If so, then perform the
 424 /// transformation.
 425 ///
 426 /// This function works on innermost loops first.  A loop can
 427 /// be converted if it is a counting loop; either a register
 428 /// value or an immediate.
 429 ///
 430 /// The code makes several assumptions about the representation
 431 /// of the loop in llvm.
 432 bool HexagonHardwareLoops::convertToHardwareLoop(MachineLoop *L) {
 433   bool Changed = false;
 434   // Process nested loops first.
 435   for (MachineLoop::iterator I = L->begin(), E = L->end(); I != E; ++I) {
 436     Changed |= convertToHardwareLoop(*I);
 437   }
 438   // If a nested loop has been converted, then we can't convert this loop.
 439   if (Changed) {
 440     return Changed;
 441   }
 442   // Are we able to determine the trip count for the loop?
 443   CountValue *TripCount = getTripCount(L);
 444   if (TripCount == 0) {
 445     return false;
 446   }
 447   // Does the loop contain any invalid instructions?
 448   if (containsInvalidInstruction(L)) {
 449     return false;
 450   }
 451   MachineBasicBlock *Preheader = L->getLoopPreheader();
 452   // No preheader means there's not place for the loop instr.
 453   if (Preheader == 0) {
 454     return false;
 455   }
 456   MachineBasicBlock::iterator InsertPos = Preheader->getFirstTerminator();
 457
 458   MachineBasicBlock *LastMBB = L->getExitingBlock();
 459   // Don't generate hw loop if the loop has more than one exit.
 460   if (LastMBB == 0) {
 461     return false;
 462   }
 463   MachineBasicBlock::iterator LastI = LastMBB->getFirstTerminator();
 464
 465   // Determine the loop start.
 466   MachineBasicBlock *LoopStart = L->getTopBlock();
 467   if (L->getLoopLatch() != LastMBB) {
 468     // When the exit and latch are not the same, use the latch block as the
 469     // start.
 470     // The loop start address is used only after the 1st iteration, and the loop
 471     // latch may contains instrs. that need to be executed after the 1st iter.
 472     LoopStart = L->getLoopLatch();
 473     // Make sure the latch is a successor of the exit, otherwise it won't work.
 474     if (!LastMBB->isSuccessor(LoopStart)) {
 475       return false;
 476     }
 477   }
 478
 479   // Convert the loop to a hardware loop
 480   DEBUG(dbgs() << "Change to hardware loop at "; L->dump());
 481
 482   if (TripCount->isReg()) {
 483     // Create a copy of the loop count register.
 484     MachineFunction *MF = LastMBB->getParent();
 485     const TargetRegisterClass *RC =
 486       MF->getRegInfo().getRegClass(TripCount->getReg());
 487     unsigned CountReg = MF->getRegInfo().createVirtualRegister(RC);
 488     BuildMI(*Preheader, InsertPos, InsertPos->getDebugLoc(),
 489             TII->get(TargetOpcode::COPY), CountReg).addReg(TripCount->getReg());
 490     if (TripCount->isNeg()) {
 491       unsigned CountReg1 = CountReg;
 492       CountReg = MF->getRegInfo().createVirtualRegister(RC);
 493       BuildMI(*Preheader, InsertPos, InsertPos->getDebugLoc(),
 494               TII->get(Hexagon::NEG), CountReg).addReg(CountReg1);
 495     }
 496
 497     // Add the Loop instruction to the beginning of the loop.
 498     BuildMI(*Preheader, InsertPos, InsertPos->getDebugLoc(),
 499             TII->get(Hexagon::LOOP0_r)).addMBB(LoopStart).addReg(CountReg);
 500   } else {
 501     assert(TripCount->isImm() && "Expecting immedate vaule for trip count");
 502     // Add the Loop immediate instruction to the beginning of the loop.
 503     int64_t CountImm = TripCount->getImm();
 504     BuildMI(*Preheader, InsertPos, InsertPos->getDebugLoc(),
 505             TII->get(Hexagon::LOOP0_i)).addMBB(LoopStart).addImm(CountImm);
 506   }
 507
 508   // Make sure the loop start always has a reference in the CFG.  We need to
 509   // create a BlockAddress operand to get this mechanism to work both the
 510   // MachineBasicBlock and BasicBlock objects need the flag set.
 511   LoopStart->setHasAddressTaken();
 512   // This line is needed to set the hasAddressTaken flag on the BasicBlock
 513   // object
 514   BlockAddress::get(const_cast<BasicBlock *>(LoopStart->getBasicBlock()));
 515
 516   // Replace the loop branch with an endloop instruction.
 517   DebugLoc dl = LastI->getDebugLoc();
 518   BuildMI(*LastMBB, LastI, dl, TII->get(Hexagon::ENDLOOP0)).addMBB(LoopStart);
 519
 520   // The loop ends with either:
 521   //  - a conditional branch followed by an unconditional branch, or
 522   //  - a conditional branch to the loop start.
 523   if (LastI->getOpcode() == Hexagon::JMP_c ||
 524       LastI->getOpcode() == Hexagon::JMP_cNot) {
 525     // delete one and change/add an uncond. branch to out of the loop
 526     MachineBasicBlock *BranchTarget = LastI->getOperand(1).getMBB();
 527     LastI = LastMBB->erase(LastI);
 528     if (!L->contains(BranchTarget)) {
 529       if (LastI != LastMBB->end()) {
 530         TII->RemoveBranch(*LastMBB);
 531       }
 532       SmallVector<MachineOperand, 0> Cond;
 533       TII->InsertBranch(*LastMBB, BranchTarget, 0, Cond, dl);
 534     }
 535   } else {
 536     // Conditional branch to loop start; just delete it.
 537     LastMBB->erase(LastI);
 538   }
 539   delete TripCount;
 540
 541   ++NumHWLoops;
 542   return true;
 543 }
 544
 545 /// createHexagonFixupHwLoops - Factory for creating the hardware loop
 546 /// phase.
 547 FunctionPass *llvm::createHexagonFixupHwLoops() {
 548   return new HexagonFixupHwLoops();
 549 }
 550
 551 bool HexagonFixupHwLoops::runOnMachineFunction(MachineFunction &MF) {
 552   DEBUG(dbgs() << "****** Hexagon Hardware Loop Fixup ******\n");
 553
 554   bool Changed = fixupLoopInstrs(MF);
 555   return Changed;
 556 }
 557
 558 /// fixupLoopInsts - For Hexagon, if the loop label is to far from the
 559 /// loop instruction then we need to set the LC0 and SA0 registers
 560 /// explicitly instead of using LOOP(start,count).  This function
 561 /// checks the distance, and generates register assignments if needed.
 562 ///
 563 /// This function makes two passes over the basic blocks.  The first
 564 /// pass computes the offset of the basic block from the start.
 565 /// The second pass checks all the loop instructions.
 566 bool HexagonFixupHwLoops::fixupLoopInstrs(MachineFunction &MF) {
 567
 568   // Offset of the current instruction from the start.
 569   unsigned InstOffset = 0;
 570   // Map for each basic block to it's first instruction.
 571   DenseMap<MachineBasicBlock*, unsigned> BlockToInstOffset;
 572
 573   // First pass - compute the offset of each basic block.
 574   for (MachineFunction::iterator MBB = MF.begin(), MBBe = MF.end();
 575        MBB != MBBe; ++MBB) {
 576     BlockToInstOffset[MBB] = InstOffset;
 577     InstOffset += (MBB->size() * 4);
 578   }
 579
 580   // Second pass - check each loop instruction to see if it needs to
 581   // be converted.
 582   InstOffset = 0;
 583   bool Changed = false;
 584   RegScavenger RS;
 585
 586   // Loop over all the basic blocks.
 587   for (MachineFunction::iterator MBB = MF.begin(), MBBe = MF.end();
 588        MBB != MBBe; ++MBB) {
 589     InstOffset = BlockToInstOffset[MBB];
 590     RS.enterBasicBlock(MBB);
 591
 592     // Loop over all the instructions.
 593     MachineBasicBlock::iterator MIE = MBB->end();
 594     MachineBasicBlock::iterator MII = MBB->begin();
 595     while (MII != MIE) {
 596       if (isHardwareLoop(MII)) {
 597         RS.forward(MII);
 598         assert(MII->getOperand(0).isMBB() &&
 599                "Expect a basic block as loop operand");
 600         int diff = InstOffset - BlockToInstOffset[MII->getOperand(0).getMBB()];
 601         diff = (diff > 0 ? diff : -diff);
 602         if ((unsigned)diff > MAX_LOOP_DISTANCE) {
 603           // Convert to explicity setting LC0 and SA0.
 604           convertLoopInstr(MF, MII, RS);
 605           MII = MBB->erase(MII);
 606           Changed = true;
 607         } else {
 608           ++MII;
 609         }
 610       } else {
 611         ++MII;
 612       }
 613       InstOffset += 4;
 614     }
 615   }
 616
 617   return Changed;
 618
 619 }
 620
 621 /// convertLoopInstr - convert a loop instruction to a sequence of instructions
 622 /// that set the lc and sa register explicitly.
 623 void HexagonFixupHwLoops::convertLoopInstr(MachineFunction &MF,
 624                                            MachineBasicBlock::iterator &MII,
 625                                            RegScavenger &RS) {
 626   const TargetInstrInfo *TII = MF.getTarget().getInstrInfo();
 627   MachineBasicBlock *MBB = MII->getParent();
 628   DebugLoc DL = MII->getDebugLoc();
 629   unsigned Scratch = RS.scavengeRegister(&Hexagon::IntRegsRegClass, MII, 0);
 630
 631   // First, set the LC0 with the trip count.
 632   if (MII->getOperand(1).isReg()) {
 633     // Trip count is a register
 634     BuildMI(*MBB, MII, DL, TII->get(Hexagon::TFCR), Hexagon::LC0)
 635       .addReg(MII->getOperand(1).getReg());
 636   } else {
 637     // Trip count is an immediate.
 638     BuildMI(*MBB, MII, DL, TII->get(Hexagon::TFRI), Scratch)
 639       .addImm(MII->getOperand(1).getImm());
 640     BuildMI(*MBB, MII, DL, TII->get(Hexagon::TFCR), Hexagon::LC0)
 641       .addReg(Scratch);
 642   }
 643   // Then, set the SA0 with the loop start address.
 644   BuildMI(*MBB, MII, DL, TII->get(Hexagon::CONST32_Label), Scratch)
 645     .addMBB(MII->getOperand(0).getMBB());
 646   BuildMI(*MBB, MII, DL, TII->get(Hexagon::TFCR), Hexagon::SA0).addReg(Scratch);
 647 }