xref: /freebsd/contrib/llvm-project/llvm/lib/Target/Hexagon/HexagonHardwareLoops.cpp (revision e32fecd0c2c3ee37c47ee100f169e7eb0282a873)
1 //===- HexagonHardwareLoops.cpp - Identify and generate hardware loops ----===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This pass identifies loops where we can generate the Hexagon hardware
10 // loop instruction.  The hardware loop can perform loop branches with a
11 // zero-cycle overhead.
12 //
13 // The pattern that defines the induction variable can changed depending on
14 // prior optimizations.  For example, the IndVarSimplify phase run by 'opt'
15 // normalizes induction variables, and the Loop Strength Reduction pass
16 // run by 'llc' may also make changes to the induction variable.
17 // The pattern detected by this phase is due to running Strength Reduction.
18 //
19 // Criteria for hardware loops:
20 //  - Countable loops (w/ ind. var for a trip count)
21 //  - Assumes loops are normalized by IndVarSimplify
22 //  - Try inner-most loops first
23 //  - No function calls in loops.
24 //
25 //===----------------------------------------------------------------------===//
26 
27 #include "HexagonInstrInfo.h"
28 #include "HexagonSubtarget.h"
29 #include "llvm/ADT/ArrayRef.h"
30 #include "llvm/ADT/STLExtras.h"
31 #include "llvm/ADT/SmallSet.h"
32 #include "llvm/ADT/SmallVector.h"
33 #include "llvm/ADT/Statistic.h"
34 #include "llvm/ADT/StringRef.h"
35 #include "llvm/CodeGen/MachineBasicBlock.h"
36 #include "llvm/CodeGen/MachineDominators.h"
37 #include "llvm/CodeGen/MachineFunction.h"
38 #include "llvm/CodeGen/MachineFunctionPass.h"
39 #include "llvm/CodeGen/MachineInstr.h"
40 #include "llvm/CodeGen/MachineInstrBuilder.h"
41 #include "llvm/CodeGen/MachineLoopInfo.h"
42 #include "llvm/CodeGen/MachineOperand.h"
43 #include "llvm/CodeGen/MachineRegisterInfo.h"
44 #include "llvm/CodeGen/TargetRegisterInfo.h"
45 #include "llvm/IR/Constants.h"
46 #include "llvm/IR/DebugLoc.h"
47 #include "llvm/InitializePasses.h"
48 #include "llvm/Pass.h"
49 #include "llvm/Support/CommandLine.h"
50 #include "llvm/Support/Debug.h"
51 #include "llvm/Support/ErrorHandling.h"
52 #include "llvm/Support/MathExtras.h"
53 #include "llvm/Support/raw_ostream.h"
54 #include <cassert>
55 #include <cstdint>
56 #include <cstdlib>
57 #include <iterator>
58 #include <map>
59 #include <set>
60 #include <string>
61 #include <utility>
62 #include <vector>
63 
64 using namespace llvm;
65 
66 #define DEBUG_TYPE "hwloops"
67 
68 #ifndef NDEBUG
69 static cl::opt<int> HWLoopLimit("hexagon-max-hwloop", cl::Hidden, cl::init(-1));
70 
71 // Option to create preheader only for a specific function.
72 static cl::opt<std::string> PHFn("hexagon-hwloop-phfn", cl::Hidden,
73                                  cl::init(""));
74 #endif
75 
76 // Option to create a preheader if one doesn't exist.
77 static cl::opt<bool> HWCreatePreheader("hexagon-hwloop-preheader",
78     cl::Hidden, cl::init(true),
79     cl::desc("Add a preheader to a hardware loop if one doesn't exist"));
80 
81 // Turn it off by default. If a preheader block is not created here, the
82 // software pipeliner may be unable to find a block suitable to serve as
83 // a preheader. In that case SWP will not run.
84 static cl::opt<bool> SpecPreheader("hwloop-spec-preheader", cl::Hidden,
85                                    cl::desc("Allow speculation of preheader "
86                                             "instructions"));
87 
88 STATISTIC(NumHWLoops, "Number of loops converted to hardware loops");
89 
90 namespace llvm {
91 
92   FunctionPass *createHexagonHardwareLoops();
93   void initializeHexagonHardwareLoopsPass(PassRegistry&);
94 
95 } // end namespace llvm
96 
97 namespace {
98 
99   class CountValue;
100 
101   struct HexagonHardwareLoops : public MachineFunctionPass {
102     MachineLoopInfo            *MLI;
103     MachineRegisterInfo        *MRI;
104     MachineDominatorTree       *MDT;
105     const HexagonInstrInfo     *TII;
106     const HexagonRegisterInfo  *TRI;
107 #ifndef NDEBUG
108     static int Counter;
109 #endif
110 
111   public:
112     static char ID;
113 
114     HexagonHardwareLoops() : MachineFunctionPass(ID) {}
115 
116     bool runOnMachineFunction(MachineFunction &MF) override;
117 
118     StringRef getPassName() const override { return "Hexagon Hardware Loops"; }
119 
120     void getAnalysisUsage(AnalysisUsage &AU) const override {
121       AU.addRequired<MachineDominatorTree>();
122       AU.addRequired<MachineLoopInfo>();
123       MachineFunctionPass::getAnalysisUsage(AU);
124     }
125 
126   private:
127     using LoopFeederMap = std::map<unsigned, MachineInstr *>;
128 
129     /// Kinds of comparisons in the compare instructions.
130     struct Comparison {
131       enum Kind {
132         EQ  = 0x01,
133         NE  = 0x02,
134         L   = 0x04,
135         G   = 0x08,
136         U   = 0x40,
137         LTs = L,
138         LEs = L | EQ,
139         GTs = G,
140         GEs = G | EQ,
141         LTu = L      | U,
142         LEu = L | EQ | U,
143         GTu = G      | U,
144         GEu = G | EQ | U
145       };
146 
147       static Kind getSwappedComparison(Kind Cmp) {
148         assert ((!((Cmp & L) && (Cmp & G))) && "Malformed comparison operator");
149         if ((Cmp & L) || (Cmp & G))
150           return (Kind)(Cmp ^ (L|G));
151         return Cmp;
152       }
153 
154       static Kind getNegatedComparison(Kind Cmp) {
155         if ((Cmp & L) || (Cmp & G))
156           return (Kind)((Cmp ^ (L | G)) ^ EQ);
157         if ((Cmp & NE) || (Cmp & EQ))
158           return (Kind)(Cmp ^ (EQ | NE));
159         return (Kind)0;
160       }
161 
162       static bool isSigned(Kind Cmp) {
163         return (Cmp & (L | G) && !(Cmp & U));
164       }
165 
166       static bool isUnsigned(Kind Cmp) {
167         return (Cmp & U);
168       }
169     };
170 
171     /// Find the register that contains the loop controlling
172     /// induction variable.
173     /// If successful, it will return true and set the \p Reg, \p IVBump
174     /// and \p IVOp arguments.  Otherwise it will return false.
175     /// The returned induction register is the register R that follows the
176     /// following induction pattern:
177     /// loop:
178     ///   R = phi ..., [ R.next, LatchBlock ]
179     ///   R.next = R + #bump
180     ///   if (R.next < #N) goto loop
181     /// IVBump is the immediate value added to R, and IVOp is the instruction
182     /// "R.next = R + #bump".
183     bool findInductionRegister(MachineLoop *L, unsigned &Reg,
184                                int64_t &IVBump, MachineInstr *&IVOp) const;
185 
186     /// Return the comparison kind for the specified opcode.
187     Comparison::Kind getComparisonKind(unsigned CondOpc,
188                                        MachineOperand *InitialValue,
189                                        const MachineOperand *Endvalue,
190                                        int64_t IVBump) const;
191 
192     /// Analyze the statements in a loop to determine if the loop
193     /// has a computable trip count and, if so, return a value that represents
194     /// the trip count expression.
195     CountValue *getLoopTripCount(MachineLoop *L,
196                                  SmallVectorImpl<MachineInstr *> &OldInsts);
197 
198     /// Return the expression that represents the number of times
199     /// a loop iterates.  The function takes the operands that represent the
200     /// loop start value, loop end value, and induction value.  Based upon
201     /// these operands, the function attempts to compute the trip count.
202     /// If the trip count is not directly available (as an immediate value,
203     /// or a register), the function will attempt to insert computation of it
204     /// to the loop's preheader.
205     CountValue *computeCount(MachineLoop *Loop, const MachineOperand *Start,
206                              const MachineOperand *End, unsigned IVReg,
207                              int64_t IVBump, Comparison::Kind Cmp) const;
208 
209     /// Return true if the instruction is not valid within a hardware
210     /// loop.
211     bool isInvalidLoopOperation(const MachineInstr *MI,
212                                 bool IsInnerHWLoop) const;
213 
214     /// Return true if the loop contains an instruction that inhibits
215     /// using the hardware loop.
216     bool containsInvalidInstruction(MachineLoop *L, bool IsInnerHWLoop) const;
217 
218     /// Given a loop, check if we can convert it to a hardware loop.
219     /// If so, then perform the conversion and return true.
220     bool convertToHardwareLoop(MachineLoop *L, bool &L0used, bool &L1used);
221 
222     /// Return true if the instruction is now dead.
223     bool isDead(const MachineInstr *MI,
224                 SmallVectorImpl<MachineInstr *> &DeadPhis) const;
225 
226     /// Remove the instruction if it is now dead.
227     void removeIfDead(MachineInstr *MI);
228 
229     /// Make sure that the "bump" instruction executes before the
230     /// compare.  We need that for the IV fixup, so that the compare
231     /// instruction would not use a bumped value that has not yet been
232     /// defined.  If the instructions are out of order, try to reorder them.
233     bool orderBumpCompare(MachineInstr *BumpI, MachineInstr *CmpI);
234 
235     /// Return true if MO and MI pair is visited only once. If visited
236     /// more than once, this indicates there is recursion. In such a case,
237     /// return false.
238     bool isLoopFeeder(MachineLoop *L, MachineBasicBlock *A, MachineInstr *MI,
239                       const MachineOperand *MO,
240                       LoopFeederMap &LoopFeederPhi) const;
241 
242     /// Return true if the Phi may generate a value that may underflow,
243     /// or may wrap.
244     bool phiMayWrapOrUnderflow(MachineInstr *Phi, const MachineOperand *EndVal,
245                                MachineBasicBlock *MBB, MachineLoop *L,
246                                LoopFeederMap &LoopFeederPhi) const;
247 
248     /// Return true if the induction variable may underflow an unsigned
249     /// value in the first iteration.
250     bool loopCountMayWrapOrUnderFlow(const MachineOperand *InitVal,
251                                      const MachineOperand *EndVal,
252                                      MachineBasicBlock *MBB, MachineLoop *L,
253                                      LoopFeederMap &LoopFeederPhi) const;
254 
255     /// Check if the given operand has a compile-time known constant
256     /// value. Return true if yes, and false otherwise. When returning true, set
257     /// Val to the corresponding constant value.
258     bool checkForImmediate(const MachineOperand &MO, int64_t &Val) const;
259 
260     /// Check if the operand has a compile-time known constant value.
261     bool isImmediate(const MachineOperand &MO) const {
262       int64_t V;
263       return checkForImmediate(MO, V);
264     }
265 
266     /// Return the immediate for the specified operand.
267     int64_t getImmediate(const MachineOperand &MO) const {
268       int64_t V;
269       if (!checkForImmediate(MO, V))
270         llvm_unreachable("Invalid operand");
271       return V;
272     }
273 
274     /// Reset the given machine operand to now refer to a new immediate
275     /// value.  Assumes that the operand was already referencing an immediate
276     /// value, either directly, or via a register.
277     void setImmediate(MachineOperand &MO, int64_t Val);
278 
279     /// Fix the data flow of the induction variable.
280     /// The desired flow is: phi ---> bump -+-> comparison-in-latch.
281     ///                                     |
282     ///                                     +-> back to phi
283     /// where "bump" is the increment of the induction variable:
284     ///   iv = iv + #const.
285     /// Due to some prior code transformations, the actual flow may look
286     /// like this:
287     ///   phi -+-> bump ---> back to phi
288     ///        |
289     ///        +-> comparison-in-latch (against upper_bound-bump),
290     /// i.e. the comparison that controls the loop execution may be using
291     /// the value of the induction variable from before the increment.
292     ///
293     /// Return true if the loop's flow is the desired one (i.e. it's
294     /// either been fixed, or no fixing was necessary).
295     /// Otherwise, return false.  This can happen if the induction variable
296     /// couldn't be identified, or if the value in the latch's comparison
297     /// cannot be adjusted to reflect the post-bump value.
298     bool fixupInductionVariable(MachineLoop *L);
299 
300     /// Given a loop, if it does not have a preheader, create one.
301     /// Return the block that is the preheader.
302     MachineBasicBlock *createPreheaderForLoop(MachineLoop *L);
303   };
304 
305   char HexagonHardwareLoops::ID = 0;
306 #ifndef NDEBUG
307   int HexagonHardwareLoops::Counter = 0;
308 #endif
309 
310   /// Abstraction for a trip count of a loop. A smaller version
311   /// of the MachineOperand class without the concerns of changing the
312   /// operand representation.
313   class CountValue {
314   public:
315     enum CountValueType {
316       CV_Register,
317       CV_Immediate
318     };
319 
320   private:
321     CountValueType Kind;
322     union Values {
323       struct {
324         unsigned Reg;
325         unsigned Sub;
326       } R;
327       unsigned ImmVal;
328     } Contents;
329 
330   public:
331     explicit CountValue(CountValueType t, unsigned v, unsigned u = 0) {
332       Kind = t;
333       if (Kind == CV_Register) {
334         Contents.R.Reg = v;
335         Contents.R.Sub = u;
336       } else {
337         Contents.ImmVal = v;
338       }
339     }
340 
341     bool isReg() const { return Kind == CV_Register; }
342     bool isImm() const { return Kind == CV_Immediate; }
343 
344     unsigned getReg() const {
345       assert(isReg() && "Wrong CountValue accessor");
346       return Contents.R.Reg;
347     }
348 
349     unsigned getSubReg() const {
350       assert(isReg() && "Wrong CountValue accessor");
351       return Contents.R.Sub;
352     }
353 
354     unsigned getImm() const {
355       assert(isImm() && "Wrong CountValue accessor");
356       return Contents.ImmVal;
357     }
358 
359     void print(raw_ostream &OS, const TargetRegisterInfo *TRI = nullptr) const {
360       if (isReg()) { OS << printReg(Contents.R.Reg, TRI, Contents.R.Sub); }
361       if (isImm()) { OS << Contents.ImmVal; }
362     }
363   };
364 
365 } // end anonymous namespace
366 
367 INITIALIZE_PASS_BEGIN(HexagonHardwareLoops, "hwloops",
368                       "Hexagon Hardware Loops", false, false)
369 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
370 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
371 INITIALIZE_PASS_END(HexagonHardwareLoops, "hwloops",
372                     "Hexagon Hardware Loops", false, false)
373 
374 FunctionPass *llvm::createHexagonHardwareLoops() {
375   return new HexagonHardwareLoops();
376 }
377 
378 bool HexagonHardwareLoops::runOnMachineFunction(MachineFunction &MF) {
379   LLVM_DEBUG(dbgs() << "********* Hexagon Hardware Loops *********\n");
380   if (skipFunction(MF.getFunction()))
381     return false;
382 
383   bool Changed = false;
384 
385   MLI = &getAnalysis<MachineLoopInfo>();
386   MRI = &MF.getRegInfo();
387   MDT = &getAnalysis<MachineDominatorTree>();
388   const HexagonSubtarget &HST = MF.getSubtarget<HexagonSubtarget>();
389   TII = HST.getInstrInfo();
390   TRI = HST.getRegisterInfo();
391 
392   for (auto &L : *MLI)
393     if (L->isOutermost()) {
394       bool L0Used = false;
395       bool L1Used = false;
396       Changed |= convertToHardwareLoop(L, L0Used, L1Used);
397     }
398 
399   return Changed;
400 }
401 
402 bool HexagonHardwareLoops::findInductionRegister(MachineLoop *L,
403                                                  unsigned &Reg,
404                                                  int64_t &IVBump,
405                                                  MachineInstr *&IVOp
406                                                  ) const {
407   MachineBasicBlock *Header = L->getHeader();
408   MachineBasicBlock *Preheader = MLI->findLoopPreheader(L, SpecPreheader);
409   MachineBasicBlock *Latch = L->getLoopLatch();
410   MachineBasicBlock *ExitingBlock = L->findLoopControlBlock();
411   if (!Header || !Preheader || !Latch || !ExitingBlock)
412     return false;
413 
414   // This pair represents an induction register together with an immediate
415   // value that will be added to it in each loop iteration.
416   using RegisterBump = std::pair<unsigned, int64_t>;
417 
418   // Mapping:  R.next -> (R, bump), where R, R.next and bump are derived
419   // from an induction operation
420   //   R.next = R + bump
421   // where bump is an immediate value.
422   using InductionMap = std::map<unsigned, RegisterBump>;
423 
424   InductionMap IndMap;
425 
426   using instr_iterator = MachineBasicBlock::instr_iterator;
427 
428   for (instr_iterator I = Header->instr_begin(), E = Header->instr_end();
429        I != E && I->isPHI(); ++I) {
430     MachineInstr *Phi = &*I;
431 
432     // Have a PHI instruction.  Get the operand that corresponds to the
433     // latch block, and see if is a result of an addition of form "reg+imm",
434     // where the "reg" is defined by the PHI node we are looking at.
435     for (unsigned i = 1, n = Phi->getNumOperands(); i < n; i += 2) {
436       if (Phi->getOperand(i+1).getMBB() != Latch)
437         continue;
438 
439       Register PhiOpReg = Phi->getOperand(i).getReg();
440       MachineInstr *DI = MRI->getVRegDef(PhiOpReg);
441 
442       if (DI->getDesc().isAdd()) {
443         // If the register operand to the add is the PHI we're looking at, this
444         // meets the induction pattern.
445         Register IndReg = DI->getOperand(1).getReg();
446         MachineOperand &Opnd2 = DI->getOperand(2);
447         int64_t V;
448         if (MRI->getVRegDef(IndReg) == Phi && checkForImmediate(Opnd2, V)) {
449           Register UpdReg = DI->getOperand(0).getReg();
450           IndMap.insert(std::make_pair(UpdReg, std::make_pair(IndReg, V)));
451         }
452       }
453     }  // for (i)
454   }  // for (instr)
455 
456   SmallVector<MachineOperand,2> Cond;
457   MachineBasicBlock *TB = nullptr, *FB = nullptr;
458   bool NotAnalyzed = TII->analyzeBranch(*ExitingBlock, TB, FB, Cond, false);
459   if (NotAnalyzed)
460     return false;
461 
462   unsigned PredR, PredPos, PredRegFlags;
463   if (!TII->getPredReg(Cond, PredR, PredPos, PredRegFlags))
464     return false;
465 
466   MachineInstr *PredI = MRI->getVRegDef(PredR);
467   if (!PredI->isCompare())
468     return false;
469 
470   Register CmpReg1, CmpReg2;
471   int64_t CmpImm = 0, CmpMask = 0;
472   bool CmpAnalyzed =
473       TII->analyzeCompare(*PredI, CmpReg1, CmpReg2, CmpMask, CmpImm);
474   // Fail if the compare was not analyzed, or it's not comparing a register
475   // with an immediate value.  Not checking the mask here, since we handle
476   // the individual compare opcodes (including A4_cmpb*) later on.
477   if (!CmpAnalyzed)
478     return false;
479 
480   // Exactly one of the input registers to the comparison should be among
481   // the induction registers.
482   InductionMap::iterator IndMapEnd = IndMap.end();
483   InductionMap::iterator F = IndMapEnd;
484   if (CmpReg1 != 0) {
485     InductionMap::iterator F1 = IndMap.find(CmpReg1);
486     if (F1 != IndMapEnd)
487       F = F1;
488   }
489   if (CmpReg2 != 0) {
490     InductionMap::iterator F2 = IndMap.find(CmpReg2);
491     if (F2 != IndMapEnd) {
492       if (F != IndMapEnd)
493         return false;
494       F = F2;
495     }
496   }
497   if (F == IndMapEnd)
498     return false;
499 
500   Reg = F->second.first;
501   IVBump = F->second.second;
502   IVOp = MRI->getVRegDef(F->first);
503   return true;
504 }
505 
506 // Return the comparison kind for the specified opcode.
507 HexagonHardwareLoops::Comparison::Kind
508 HexagonHardwareLoops::getComparisonKind(unsigned CondOpc,
509                                         MachineOperand *InitialValue,
510                                         const MachineOperand *EndValue,
511                                         int64_t IVBump) const {
512   Comparison::Kind Cmp = (Comparison::Kind)0;
513   switch (CondOpc) {
514   case Hexagon::C2_cmpeq:
515   case Hexagon::C2_cmpeqi:
516   case Hexagon::C2_cmpeqp:
517     Cmp = Comparison::EQ;
518     break;
519   case Hexagon::C4_cmpneq:
520   case Hexagon::C4_cmpneqi:
521     Cmp = Comparison::NE;
522     break;
523   case Hexagon::C2_cmplt:
524     Cmp = Comparison::LTs;
525     break;
526   case Hexagon::C2_cmpltu:
527     Cmp = Comparison::LTu;
528     break;
529   case Hexagon::C4_cmplte:
530   case Hexagon::C4_cmpltei:
531     Cmp = Comparison::LEs;
532     break;
533   case Hexagon::C4_cmplteu:
534   case Hexagon::C4_cmplteui:
535     Cmp = Comparison::LEu;
536     break;
537   case Hexagon::C2_cmpgt:
538   case Hexagon::C2_cmpgti:
539   case Hexagon::C2_cmpgtp:
540     Cmp = Comparison::GTs;
541     break;
542   case Hexagon::C2_cmpgtu:
543   case Hexagon::C2_cmpgtui:
544   case Hexagon::C2_cmpgtup:
545     Cmp = Comparison::GTu;
546     break;
547   case Hexagon::C2_cmpgei:
548     Cmp = Comparison::GEs;
549     break;
550   case Hexagon::C2_cmpgeui:
551     Cmp = Comparison::GEs;
552     break;
553   default:
554     return (Comparison::Kind)0;
555   }
556   return Cmp;
557 }
558 
559 /// Analyze the statements in a loop to determine if the loop has
560 /// a computable trip count and, if so, return a value that represents
561 /// the trip count expression.
562 ///
563 /// This function iterates over the phi nodes in the loop to check for
564 /// induction variable patterns that are used in the calculation for
565 /// the number of time the loop is executed.
566 CountValue *HexagonHardwareLoops::getLoopTripCount(MachineLoop *L,
567     SmallVectorImpl<MachineInstr *> &OldInsts) {
568   MachineBasicBlock *TopMBB = L->getTopBlock();
569   MachineBasicBlock::pred_iterator PI = TopMBB->pred_begin();
570   assert(PI != TopMBB->pred_end() &&
571          "Loop must have more than one incoming edge!");
572   MachineBasicBlock *Backedge = *PI++;
573   if (PI == TopMBB->pred_end())  // dead loop?
574     return nullptr;
575   MachineBasicBlock *Incoming = *PI++;
576   if (PI != TopMBB->pred_end())  // multiple backedges?
577     return nullptr;
578 
579   // Make sure there is one incoming and one backedge and determine which
580   // is which.
581   if (L->contains(Incoming)) {
582     if (L->contains(Backedge))
583       return nullptr;
584     std::swap(Incoming, Backedge);
585   } else if (!L->contains(Backedge))
586     return nullptr;
587 
588   // Look for the cmp instruction to determine if we can get a useful trip
589   // count.  The trip count can be either a register or an immediate.  The
590   // location of the value depends upon the type (reg or imm).
591   MachineBasicBlock *ExitingBlock = L->findLoopControlBlock();
592   if (!ExitingBlock)
593     return nullptr;
594 
595   unsigned IVReg = 0;
596   int64_t IVBump = 0;
597   MachineInstr *IVOp;
598   bool FoundIV = findInductionRegister(L, IVReg, IVBump, IVOp);
599   if (!FoundIV)
600     return nullptr;
601 
602   MachineBasicBlock *Preheader = MLI->findLoopPreheader(L, SpecPreheader);
603 
604   MachineOperand *InitialValue = nullptr;
605   MachineInstr *IV_Phi = MRI->getVRegDef(IVReg);
606   MachineBasicBlock *Latch = L->getLoopLatch();
607   for (unsigned i = 1, n = IV_Phi->getNumOperands(); i < n; i += 2) {
608     MachineBasicBlock *MBB = IV_Phi->getOperand(i+1).getMBB();
609     if (MBB == Preheader)
610       InitialValue = &IV_Phi->getOperand(i);
611     else if (MBB == Latch)
612       IVReg = IV_Phi->getOperand(i).getReg();  // Want IV reg after bump.
613   }
614   if (!InitialValue)
615     return nullptr;
616 
617   SmallVector<MachineOperand,2> Cond;
618   MachineBasicBlock *TB = nullptr, *FB = nullptr;
619   bool NotAnalyzed = TII->analyzeBranch(*ExitingBlock, TB, FB, Cond, false);
620   if (NotAnalyzed)
621     return nullptr;
622 
623   MachineBasicBlock *Header = L->getHeader();
624   // TB must be non-null.  If FB is also non-null, one of them must be
625   // the header.  Otherwise, branch to TB could be exiting the loop, and
626   // the fall through can go to the header.
627   assert (TB && "Exit block without a branch?");
628   if (ExitingBlock != Latch && (TB == Latch || FB == Latch)) {
629     MachineBasicBlock *LTB = nullptr, *LFB = nullptr;
630     SmallVector<MachineOperand,2> LCond;
631     bool NotAnalyzed = TII->analyzeBranch(*Latch, LTB, LFB, LCond, false);
632     if (NotAnalyzed)
633       return nullptr;
634     if (TB == Latch)
635       TB = (LTB == Header) ? LTB : LFB;
636     else
637       FB = (LTB == Header) ? LTB: LFB;
638   }
639   assert ((!FB || TB == Header || FB == Header) && "Branches not to header?");
640   if (!TB || (FB && TB != Header && FB != Header))
641     return nullptr;
642 
643   // Branches of form "if (!P) ..." cause HexagonInstrInfo::analyzeBranch
644   // to put imm(0), followed by P in the vector Cond.
645   // If TB is not the header, it means that the "not-taken" path must lead
646   // to the header.
647   bool Negated = TII->predOpcodeHasNot(Cond) ^ (TB != Header);
648   unsigned PredReg, PredPos, PredRegFlags;
649   if (!TII->getPredReg(Cond, PredReg, PredPos, PredRegFlags))
650     return nullptr;
651   MachineInstr *CondI = MRI->getVRegDef(PredReg);
652   unsigned CondOpc = CondI->getOpcode();
653 
654   Register CmpReg1, CmpReg2;
655   int64_t Mask = 0, ImmValue = 0;
656   bool AnalyzedCmp =
657       TII->analyzeCompare(*CondI, CmpReg1, CmpReg2, Mask, ImmValue);
658   if (!AnalyzedCmp)
659     return nullptr;
660 
661   // The comparison operator type determines how we compute the loop
662   // trip count.
663   OldInsts.push_back(CondI);
664   OldInsts.push_back(IVOp);
665 
666   // Sadly, the following code gets information based on the position
667   // of the operands in the compare instruction.  This has to be done
668   // this way, because the comparisons check for a specific relationship
669   // between the operands (e.g. is-less-than), rather than to find out
670   // what relationship the operands are in (as on PPC).
671   Comparison::Kind Cmp;
672   bool isSwapped = false;
673   const MachineOperand &Op1 = CondI->getOperand(1);
674   const MachineOperand &Op2 = CondI->getOperand(2);
675   const MachineOperand *EndValue = nullptr;
676 
677   if (Op1.isReg()) {
678     if (Op2.isImm() || Op1.getReg() == IVReg)
679       EndValue = &Op2;
680     else {
681       EndValue = &Op1;
682       isSwapped = true;
683     }
684   }
685 
686   if (!EndValue)
687     return nullptr;
688 
689   Cmp = getComparisonKind(CondOpc, InitialValue, EndValue, IVBump);
690   if (!Cmp)
691     return nullptr;
692   if (Negated)
693     Cmp = Comparison::getNegatedComparison(Cmp);
694   if (isSwapped)
695     Cmp = Comparison::getSwappedComparison(Cmp);
696 
697   if (InitialValue->isReg()) {
698     Register R = InitialValue->getReg();
699     MachineBasicBlock *DefBB = MRI->getVRegDef(R)->getParent();
700     if (!MDT->properlyDominates(DefBB, Header)) {
701       int64_t V;
702       if (!checkForImmediate(*InitialValue, V))
703         return nullptr;
704     }
705     OldInsts.push_back(MRI->getVRegDef(R));
706   }
707   if (EndValue->isReg()) {
708     Register R = EndValue->getReg();
709     MachineBasicBlock *DefBB = MRI->getVRegDef(R)->getParent();
710     if (!MDT->properlyDominates(DefBB, Header)) {
711       int64_t V;
712       if (!checkForImmediate(*EndValue, V))
713         return nullptr;
714     }
715     OldInsts.push_back(MRI->getVRegDef(R));
716   }
717 
718   return computeCount(L, InitialValue, EndValue, IVReg, IVBump, Cmp);
719 }
720 
721 /// Helper function that returns the expression that represents the
722 /// number of times a loop iterates.  The function takes the operands that
723 /// represent the loop start value, loop end value, and induction value.
724 /// Based upon these operands, the function attempts to compute the trip count.
725 CountValue *HexagonHardwareLoops::computeCount(MachineLoop *Loop,
726                                                const MachineOperand *Start,
727                                                const MachineOperand *End,
728                                                unsigned IVReg,
729                                                int64_t IVBump,
730                                                Comparison::Kind Cmp) const {
731   // Cannot handle comparison EQ, i.e. while (A == B).
732   if (Cmp == Comparison::EQ)
733     return nullptr;
734 
735   // Check if either the start or end values are an assignment of an immediate.
736   // If so, use the immediate value rather than the register.
737   if (Start->isReg()) {
738     const MachineInstr *StartValInstr = MRI->getVRegDef(Start->getReg());
739     if (StartValInstr && (StartValInstr->getOpcode() == Hexagon::A2_tfrsi ||
740                           StartValInstr->getOpcode() == Hexagon::A2_tfrpi))
741       Start = &StartValInstr->getOperand(1);
742   }
743   if (End->isReg()) {
744     const MachineInstr *EndValInstr = MRI->getVRegDef(End->getReg());
745     if (EndValInstr && (EndValInstr->getOpcode() == Hexagon::A2_tfrsi ||
746                         EndValInstr->getOpcode() == Hexagon::A2_tfrpi))
747       End = &EndValInstr->getOperand(1);
748   }
749 
750   if (!Start->isReg() && !Start->isImm())
751     return nullptr;
752   if (!End->isReg() && !End->isImm())
753     return nullptr;
754 
755   bool CmpLess =     Cmp & Comparison::L;
756   bool CmpGreater =  Cmp & Comparison::G;
757   bool CmpHasEqual = Cmp & Comparison::EQ;
758 
759   // Avoid certain wrap-arounds.  This doesn't detect all wrap-arounds.
760   if (CmpLess && IVBump < 0)
761     // Loop going while iv is "less" with the iv value going down.  Must wrap.
762     return nullptr;
763 
764   if (CmpGreater && IVBump > 0)
765     // Loop going while iv is "greater" with the iv value going up.  Must wrap.
766     return nullptr;
767 
768   // Phis that may feed into the loop.
769   LoopFeederMap LoopFeederPhi;
770 
771   // Check if the initial value may be zero and can be decremented in the first
772   // iteration. If the value is zero, the endloop instruction will not decrement
773   // the loop counter, so we shouldn't generate a hardware loop in this case.
774   if (loopCountMayWrapOrUnderFlow(Start, End, Loop->getLoopPreheader(), Loop,
775                                   LoopFeederPhi))
776       return nullptr;
777 
778   if (Start->isImm() && End->isImm()) {
779     // Both, start and end are immediates.
780     int64_t StartV = Start->getImm();
781     int64_t EndV = End->getImm();
782     int64_t Dist = EndV - StartV;
783     if (Dist == 0)
784       return nullptr;
785 
786     bool Exact = (Dist % IVBump) == 0;
787 
788     if (Cmp == Comparison::NE) {
789       if (!Exact)
790         return nullptr;
791       if ((Dist < 0) ^ (IVBump < 0))
792         return nullptr;
793     }
794 
795     // For comparisons that include the final value (i.e. include equality
796     // with the final value), we need to increase the distance by 1.
797     if (CmpHasEqual)
798       Dist = Dist > 0 ? Dist+1 : Dist-1;
799 
800     // For the loop to iterate, CmpLess should imply Dist > 0.  Similarly,
801     // CmpGreater should imply Dist < 0.  These conditions could actually
802     // fail, for example, in unreachable code (which may still appear to be
803     // reachable in the CFG).
804     if ((CmpLess && Dist < 0) || (CmpGreater && Dist > 0))
805       return nullptr;
806 
807     // "Normalized" distance, i.e. with the bump set to +-1.
808     int64_t Dist1 = (IVBump > 0) ? (Dist +  (IVBump - 1)) / IVBump
809                                  : (-Dist + (-IVBump - 1)) / (-IVBump);
810     assert (Dist1 > 0 && "Fishy thing.  Both operands have the same sign.");
811 
812     uint64_t Count = Dist1;
813 
814     if (Count > 0xFFFFFFFFULL)
815       return nullptr;
816 
817     return new CountValue(CountValue::CV_Immediate, Count);
818   }
819 
820   // A general case: Start and End are some values, but the actual
821   // iteration count may not be available.  If it is not, insert
822   // a computation of it into the preheader.
823 
824   // If the induction variable bump is not a power of 2, quit.
825   // Othwerise we'd need a general integer division.
826   if (!isPowerOf2_64(std::abs(IVBump)))
827     return nullptr;
828 
829   MachineBasicBlock *PH = MLI->findLoopPreheader(Loop, SpecPreheader);
830   assert (PH && "Should have a preheader by now");
831   MachineBasicBlock::iterator InsertPos = PH->getFirstTerminator();
832   DebugLoc DL;
833   if (InsertPos != PH->end())
834     DL = InsertPos->getDebugLoc();
835 
836   // If Start is an immediate and End is a register, the trip count
837   // will be "reg - imm".  Hexagon's "subtract immediate" instruction
838   // is actually "reg + -imm".
839 
840   // If the loop IV is going downwards, i.e. if the bump is negative,
841   // then the iteration count (computed as End-Start) will need to be
842   // negated.  To avoid the negation, just swap Start and End.
843   if (IVBump < 0) {
844     std::swap(Start, End);
845     IVBump = -IVBump;
846   }
847   // Cmp may now have a wrong direction, e.g.  LEs may now be GEs.
848   // Signedness, and "including equality" are preserved.
849 
850   bool RegToImm = Start->isReg() && End->isImm(); // for (reg..imm)
851   bool RegToReg = Start->isReg() && End->isReg(); // for (reg..reg)
852 
853   int64_t StartV = 0, EndV = 0;
854   if (Start->isImm())
855     StartV = Start->getImm();
856   if (End->isImm())
857     EndV = End->getImm();
858 
859   int64_t AdjV = 0;
860   // To compute the iteration count, we would need this computation:
861   //   Count = (End - Start + (IVBump-1)) / IVBump
862   // or, when CmpHasEqual:
863   //   Count = (End - Start + (IVBump-1)+1) / IVBump
864   // The "IVBump-1" part is the adjustment (AdjV).  We can avoid
865   // generating an instruction specifically to add it if we can adjust
866   // the immediate values for Start or End.
867 
868   if (CmpHasEqual) {
869     // Need to add 1 to the total iteration count.
870     if (Start->isImm())
871       StartV--;
872     else if (End->isImm())
873       EndV++;
874     else
875       AdjV += 1;
876   }
877 
878   if (Cmp != Comparison::NE) {
879     if (Start->isImm())
880       StartV -= (IVBump-1);
881     else if (End->isImm())
882       EndV += (IVBump-1);
883     else
884       AdjV += (IVBump-1);
885   }
886 
887   unsigned R = 0, SR = 0;
888   if (Start->isReg()) {
889     R = Start->getReg();
890     SR = Start->getSubReg();
891   } else {
892     R = End->getReg();
893     SR = End->getSubReg();
894   }
895   const TargetRegisterClass *RC = MRI->getRegClass(R);
896   // Hardware loops cannot handle 64-bit registers.  If it's a double
897   // register, it has to have a subregister.
898   if (!SR && RC == &Hexagon::DoubleRegsRegClass)
899     return nullptr;
900   const TargetRegisterClass *IntRC = &Hexagon::IntRegsRegClass;
901 
902   // Compute DistR (register with the distance between Start and End).
903   unsigned DistR, DistSR;
904 
905   // Avoid special case, where the start value is an imm(0).
906   if (Start->isImm() && StartV == 0) {
907     DistR = End->getReg();
908     DistSR = End->getSubReg();
909   } else {
910     const MCInstrDesc &SubD = RegToReg ? TII->get(Hexagon::A2_sub) :
911                               (RegToImm ? TII->get(Hexagon::A2_subri) :
912                                           TII->get(Hexagon::A2_addi));
913     if (RegToReg || RegToImm) {
914       Register SubR = MRI->createVirtualRegister(IntRC);
915       MachineInstrBuilder SubIB =
916         BuildMI(*PH, InsertPos, DL, SubD, SubR);
917 
918       if (RegToReg)
919         SubIB.addReg(End->getReg(), 0, End->getSubReg())
920           .addReg(Start->getReg(), 0, Start->getSubReg());
921       else
922         SubIB.addImm(EndV)
923           .addReg(Start->getReg(), 0, Start->getSubReg());
924       DistR = SubR;
925     } else {
926       // If the loop has been unrolled, we should use the original loop count
927       // instead of recalculating the value. This will avoid additional
928       // 'Add' instruction.
929       const MachineInstr *EndValInstr = MRI->getVRegDef(End->getReg());
930       if (EndValInstr->getOpcode() == Hexagon::A2_addi &&
931           EndValInstr->getOperand(1).getSubReg() == 0 &&
932           EndValInstr->getOperand(2).getImm() == StartV) {
933         DistR = EndValInstr->getOperand(1).getReg();
934       } else {
935         Register SubR = MRI->createVirtualRegister(IntRC);
936         MachineInstrBuilder SubIB =
937           BuildMI(*PH, InsertPos, DL, SubD, SubR);
938         SubIB.addReg(End->getReg(), 0, End->getSubReg())
939              .addImm(-StartV);
940         DistR = SubR;
941       }
942     }
943     DistSR = 0;
944   }
945 
946   // From DistR, compute AdjR (register with the adjusted distance).
947   unsigned AdjR, AdjSR;
948 
949   if (AdjV == 0) {
950     AdjR = DistR;
951     AdjSR = DistSR;
952   } else {
953     // Generate CountR = ADD DistR, AdjVal
954     Register AddR = MRI->createVirtualRegister(IntRC);
955     MCInstrDesc const &AddD = TII->get(Hexagon::A2_addi);
956     BuildMI(*PH, InsertPos, DL, AddD, AddR)
957       .addReg(DistR, 0, DistSR)
958       .addImm(AdjV);
959 
960     AdjR = AddR;
961     AdjSR = 0;
962   }
963 
964   // From AdjR, compute CountR (register with the final count).
965   unsigned CountR, CountSR;
966 
967   if (IVBump == 1) {
968     CountR = AdjR;
969     CountSR = AdjSR;
970   } else {
971     // The IV bump is a power of two. Log_2(IV bump) is the shift amount.
972     unsigned Shift = Log2_32(IVBump);
973 
974     // Generate NormR = LSR DistR, Shift.
975     Register LsrR = MRI->createVirtualRegister(IntRC);
976     const MCInstrDesc &LsrD = TII->get(Hexagon::S2_lsr_i_r);
977     BuildMI(*PH, InsertPos, DL, LsrD, LsrR)
978       .addReg(AdjR, 0, AdjSR)
979       .addImm(Shift);
980 
981     CountR = LsrR;
982     CountSR = 0;
983   }
984 
985   return new CountValue(CountValue::CV_Register, CountR, CountSR);
986 }
987 
988 /// Return true if the operation is invalid within hardware loop.
989 bool HexagonHardwareLoops::isInvalidLoopOperation(const MachineInstr *MI,
990                                                   bool IsInnerHWLoop) const {
991   // Call is not allowed because the callee may use a hardware loop except for
992   // the case when the call never returns.
993   if (MI->getDesc().isCall())
994     return !TII->doesNotReturn(*MI);
995 
996   // Check if the instruction defines a hardware loop register.
997   using namespace Hexagon;
998 
999   static const unsigned Regs01[] = { LC0, SA0, LC1, SA1 };
1000   static const unsigned Regs1[]  = { LC1, SA1 };
1001   auto CheckRegs = IsInnerHWLoop ? makeArrayRef(Regs01, array_lengthof(Regs01))
1002                                  : makeArrayRef(Regs1, array_lengthof(Regs1));
1003   for (unsigned R : CheckRegs)
1004     if (MI->modifiesRegister(R, TRI))
1005       return true;
1006 
1007   return false;
1008 }
1009 
1010 /// Return true if the loop contains an instruction that inhibits
1011 /// the use of the hardware loop instruction.
1012 bool HexagonHardwareLoops::containsInvalidInstruction(MachineLoop *L,
1013     bool IsInnerHWLoop) const {
1014   LLVM_DEBUG(dbgs() << "\nhw_loop head, "
1015                     << printMBBReference(**L->block_begin()));
1016   for (MachineBasicBlock *MBB : L->getBlocks()) {
1017     for (const MachineInstr &MI : *MBB) {
1018       if (isInvalidLoopOperation(&MI, IsInnerHWLoop)) {
1019         LLVM_DEBUG(dbgs() << "\nCannot convert to hw_loop due to:";
1020                    MI.dump(););
1021         return true;
1022       }
1023     }
1024   }
1025   return false;
1026 }
1027 
1028 /// Returns true if the instruction is dead.  This was essentially
1029 /// copied from DeadMachineInstructionElim::isDead, but with special cases
1030 /// for inline asm, physical registers and instructions with side effects
1031 /// removed.
1032 bool HexagonHardwareLoops::isDead(const MachineInstr *MI,
1033                               SmallVectorImpl<MachineInstr *> &DeadPhis) const {
1034   // Examine each operand.
1035   for (const MachineOperand &MO : MI->operands()) {
1036     if (!MO.isReg() || !MO.isDef())
1037       continue;
1038 
1039     Register Reg = MO.getReg();
1040     if (MRI->use_nodbg_empty(Reg))
1041       continue;
1042 
1043     using use_nodbg_iterator = MachineRegisterInfo::use_nodbg_iterator;
1044 
1045     // This instruction has users, but if the only user is the phi node for the
1046     // parent block, and the only use of that phi node is this instruction, then
1047     // this instruction is dead: both it (and the phi node) can be removed.
1048     use_nodbg_iterator I = MRI->use_nodbg_begin(Reg);
1049     use_nodbg_iterator End = MRI->use_nodbg_end();
1050     if (std::next(I) != End || !I->getParent()->isPHI())
1051       return false;
1052 
1053     MachineInstr *OnePhi = I->getParent();
1054     for (unsigned j = 0, f = OnePhi->getNumOperands(); j != f; ++j) {
1055       const MachineOperand &OPO = OnePhi->getOperand(j);
1056       if (!OPO.isReg() || !OPO.isDef())
1057         continue;
1058 
1059       Register OPReg = OPO.getReg();
1060       use_nodbg_iterator nextJ;
1061       for (use_nodbg_iterator J = MRI->use_nodbg_begin(OPReg);
1062            J != End; J = nextJ) {
1063         nextJ = std::next(J);
1064         MachineOperand &Use = *J;
1065         MachineInstr *UseMI = Use.getParent();
1066 
1067         // If the phi node has a user that is not MI, bail.
1068         if (MI != UseMI)
1069           return false;
1070       }
1071     }
1072     DeadPhis.push_back(OnePhi);
1073   }
1074 
1075   // If there are no defs with uses, the instruction is dead.
1076   return true;
1077 }
1078 
1079 void HexagonHardwareLoops::removeIfDead(MachineInstr *MI) {
1080   // This procedure was essentially copied from DeadMachineInstructionElim.
1081 
1082   SmallVector<MachineInstr*, 1> DeadPhis;
1083   if (isDead(MI, DeadPhis)) {
1084     LLVM_DEBUG(dbgs() << "HW looping will remove: " << *MI);
1085 
1086     // It is possible that some DBG_VALUE instructions refer to this
1087     // instruction.  Examine each def operand for such references;
1088     // if found, mark the DBG_VALUE as undef (but don't delete it).
1089     for (const MachineOperand &MO : MI->operands()) {
1090       if (!MO.isReg() || !MO.isDef())
1091         continue;
1092       Register Reg = MO.getReg();
1093       // We use make_early_inc_range here because setReg below invalidates the
1094       // iterator.
1095       for (MachineOperand &MO :
1096            llvm::make_early_inc_range(MRI->use_operands(Reg))) {
1097         MachineInstr *UseMI = MO.getParent();
1098         if (UseMI == MI)
1099           continue;
1100         if (MO.isDebug())
1101           MO.setReg(0U);
1102       }
1103     }
1104 
1105     MI->eraseFromParent();
1106     for (unsigned i = 0; i < DeadPhis.size(); ++i)
1107       DeadPhis[i]->eraseFromParent();
1108   }
1109 }
1110 
1111 /// Check if the loop is a candidate for converting to a hardware
1112 /// loop.  If so, then perform the transformation.
1113 ///
1114 /// This function works on innermost loops first.  A loop can be converted
1115 /// if it is a counting loop; either a register value or an immediate.
1116 ///
1117 /// The code makes several assumptions about the representation of the loop
1118 /// in llvm.
1119 bool HexagonHardwareLoops::convertToHardwareLoop(MachineLoop *L,
1120                                                  bool &RecL0used,
1121                                                  bool &RecL1used) {
1122   // This is just to confirm basic correctness.
1123   assert(L->getHeader() && "Loop without a header?");
1124 
1125   bool Changed = false;
1126   bool L0Used = false;
1127   bool L1Used = false;
1128 
1129   // Process nested loops first.
1130   for (MachineLoop *I : *L) {
1131     Changed |= convertToHardwareLoop(I, RecL0used, RecL1used);
1132     L0Used |= RecL0used;
1133     L1Used |= RecL1used;
1134   }
1135 
1136   // If a nested loop has been converted, then we can't convert this loop.
1137   if (Changed && L0Used && L1Used)
1138     return Changed;
1139 
1140   unsigned LOOP_i;
1141   unsigned LOOP_r;
1142   unsigned ENDLOOP;
1143 
1144   // Flag used to track loopN instruction:
1145   // 1 - Hardware loop is being generated for the inner most loop.
1146   // 0 - Hardware loop is being generated for the outer loop.
1147   unsigned IsInnerHWLoop = 1;
1148 
1149   if (L0Used) {
1150     LOOP_i = Hexagon::J2_loop1i;
1151     LOOP_r = Hexagon::J2_loop1r;
1152     ENDLOOP = Hexagon::ENDLOOP1;
1153     IsInnerHWLoop = 0;
1154   } else {
1155     LOOP_i = Hexagon::J2_loop0i;
1156     LOOP_r = Hexagon::J2_loop0r;
1157     ENDLOOP = Hexagon::ENDLOOP0;
1158   }
1159 
1160 #ifndef NDEBUG
1161   // Stop trying after reaching the limit (if any).
1162   int Limit = HWLoopLimit;
1163   if (Limit >= 0) {
1164     if (Counter >= HWLoopLimit)
1165       return false;
1166     Counter++;
1167   }
1168 #endif
1169 
1170   // Does the loop contain any invalid instructions?
1171   if (containsInvalidInstruction(L, IsInnerHWLoop))
1172     return false;
1173 
1174   MachineBasicBlock *LastMBB = L->findLoopControlBlock();
1175   // Don't generate hw loop if the loop has more than one exit.
1176   if (!LastMBB)
1177     return false;
1178 
1179   MachineBasicBlock::iterator LastI = LastMBB->getFirstTerminator();
1180   if (LastI == LastMBB->end())
1181     return false;
1182 
1183   // Is the induction variable bump feeding the latch condition?
1184   if (!fixupInductionVariable(L))
1185     return false;
1186 
1187   // Ensure the loop has a preheader: the loop instruction will be
1188   // placed there.
1189   MachineBasicBlock *Preheader = MLI->findLoopPreheader(L, SpecPreheader);
1190   if (!Preheader) {
1191     Preheader = createPreheaderForLoop(L);
1192     if (!Preheader)
1193       return false;
1194   }
1195 
1196   MachineBasicBlock::iterator InsertPos = Preheader->getFirstTerminator();
1197 
1198   SmallVector<MachineInstr*, 2> OldInsts;
1199   // Are we able to determine the trip count for the loop?
1200   CountValue *TripCount = getLoopTripCount(L, OldInsts);
1201   if (!TripCount)
1202     return false;
1203 
1204   // Is the trip count available in the preheader?
1205   if (TripCount->isReg()) {
1206     // There will be a use of the register inserted into the preheader,
1207     // so make sure that the register is actually defined at that point.
1208     MachineInstr *TCDef = MRI->getVRegDef(TripCount->getReg());
1209     MachineBasicBlock *BBDef = TCDef->getParent();
1210     if (!MDT->dominates(BBDef, Preheader))
1211       return false;
1212   }
1213 
1214   // Determine the loop start.
1215   MachineBasicBlock *TopBlock = L->getTopBlock();
1216   MachineBasicBlock *ExitingBlock = L->findLoopControlBlock();
1217   MachineBasicBlock *LoopStart = nullptr;
1218   if (ExitingBlock !=  L->getLoopLatch()) {
1219     MachineBasicBlock *TB = nullptr, *FB = nullptr;
1220     SmallVector<MachineOperand, 2> Cond;
1221 
1222     if (TII->analyzeBranch(*ExitingBlock, TB, FB, Cond, false))
1223       return false;
1224 
1225     if (L->contains(TB))
1226       LoopStart = TB;
1227     else if (L->contains(FB))
1228       LoopStart = FB;
1229     else
1230       return false;
1231   }
1232   else
1233     LoopStart = TopBlock;
1234 
1235   // Convert the loop to a hardware loop.
1236   LLVM_DEBUG(dbgs() << "Change to hardware loop at "; L->dump());
1237   DebugLoc DL;
1238   if (InsertPos != Preheader->end())
1239     DL = InsertPos->getDebugLoc();
1240 
1241   if (TripCount->isReg()) {
1242     // Create a copy of the loop count register.
1243     Register CountReg = MRI->createVirtualRegister(&Hexagon::IntRegsRegClass);
1244     BuildMI(*Preheader, InsertPos, DL, TII->get(TargetOpcode::COPY), CountReg)
1245       .addReg(TripCount->getReg(), 0, TripCount->getSubReg());
1246     // Add the Loop instruction to the beginning of the loop.
1247     BuildMI(*Preheader, InsertPos, DL, TII->get(LOOP_r)).addMBB(LoopStart)
1248       .addReg(CountReg);
1249   } else {
1250     assert(TripCount->isImm() && "Expecting immediate value for trip count");
1251     // Add the Loop immediate instruction to the beginning of the loop,
1252     // if the immediate fits in the instructions.  Otherwise, we need to
1253     // create a new virtual register.
1254     int64_t CountImm = TripCount->getImm();
1255     if (!TII->isValidOffset(LOOP_i, CountImm, TRI)) {
1256       Register CountReg = MRI->createVirtualRegister(&Hexagon::IntRegsRegClass);
1257       BuildMI(*Preheader, InsertPos, DL, TII->get(Hexagon::A2_tfrsi), CountReg)
1258         .addImm(CountImm);
1259       BuildMI(*Preheader, InsertPos, DL, TII->get(LOOP_r))
1260         .addMBB(LoopStart).addReg(CountReg);
1261     } else
1262       BuildMI(*Preheader, InsertPos, DL, TII->get(LOOP_i))
1263         .addMBB(LoopStart).addImm(CountImm);
1264   }
1265 
1266   // Make sure the loop start always has a reference in the CFG.  We need
1267   // to create a BlockAddress operand to get this mechanism to work both the
1268   // MachineBasicBlock and BasicBlock objects need the flag set.
1269   LoopStart->setHasAddressTaken();
1270   // This line is needed to set the hasAddressTaken flag on the BasicBlock
1271   // object.
1272   BlockAddress::get(const_cast<BasicBlock *>(LoopStart->getBasicBlock()));
1273 
1274   // Replace the loop branch with an endloop instruction.
1275   DebugLoc LastIDL = LastI->getDebugLoc();
1276   BuildMI(*LastMBB, LastI, LastIDL, TII->get(ENDLOOP)).addMBB(LoopStart);
1277 
1278   // The loop ends with either:
1279   //  - a conditional branch followed by an unconditional branch, or
1280   //  - a conditional branch to the loop start.
1281   if (LastI->getOpcode() == Hexagon::J2_jumpt ||
1282       LastI->getOpcode() == Hexagon::J2_jumpf) {
1283     // Delete one and change/add an uncond. branch to out of the loop.
1284     MachineBasicBlock *BranchTarget = LastI->getOperand(1).getMBB();
1285     LastI = LastMBB->erase(LastI);
1286     if (!L->contains(BranchTarget)) {
1287       if (LastI != LastMBB->end())
1288         LastI = LastMBB->erase(LastI);
1289       SmallVector<MachineOperand, 0> Cond;
1290       TII->insertBranch(*LastMBB, BranchTarget, nullptr, Cond, LastIDL);
1291     }
1292   } else {
1293     // Conditional branch to loop start; just delete it.
1294     LastMBB->erase(LastI);
1295   }
1296   delete TripCount;
1297 
1298   // The induction operation and the comparison may now be
1299   // unneeded. If these are unneeded, then remove them.
1300   for (unsigned i = 0; i < OldInsts.size(); ++i)
1301     removeIfDead(OldInsts[i]);
1302 
1303   ++NumHWLoops;
1304 
1305   // Set RecL1used and RecL0used only after hardware loop has been
1306   // successfully generated. Doing it earlier can cause wrong loop instruction
1307   // to be used.
1308   if (L0Used) // Loop0 was already used. So, the correct loop must be loop1.
1309     RecL1used = true;
1310   else
1311     RecL0used = true;
1312 
1313   return true;
1314 }
1315 
1316 bool HexagonHardwareLoops::orderBumpCompare(MachineInstr *BumpI,
1317                                             MachineInstr *CmpI) {
1318   assert (BumpI != CmpI && "Bump and compare in the same instruction?");
1319 
1320   MachineBasicBlock *BB = BumpI->getParent();
1321   if (CmpI->getParent() != BB)
1322     return false;
1323 
1324   using instr_iterator = MachineBasicBlock::instr_iterator;
1325 
1326   // Check if things are in order to begin with.
1327   for (instr_iterator I(BumpI), E = BB->instr_end(); I != E; ++I)
1328     if (&*I == CmpI)
1329       return true;
1330 
1331   // Out of order.
1332   Register PredR = CmpI->getOperand(0).getReg();
1333   bool FoundBump = false;
1334   instr_iterator CmpIt = CmpI->getIterator(), NextIt = std::next(CmpIt);
1335   for (instr_iterator I = NextIt, E = BB->instr_end(); I != E; ++I) {
1336     MachineInstr *In = &*I;
1337     for (unsigned i = 0, n = In->getNumOperands(); i < n; ++i) {
1338       MachineOperand &MO = In->getOperand(i);
1339       if (MO.isReg() && MO.isUse()) {
1340         if (MO.getReg() == PredR)  // Found an intervening use of PredR.
1341           return false;
1342       }
1343     }
1344 
1345     if (In == BumpI) {
1346       BB->splice(++BumpI->getIterator(), BB, CmpI->getIterator());
1347       FoundBump = true;
1348       break;
1349     }
1350   }
1351   assert (FoundBump && "Cannot determine instruction order");
1352   return FoundBump;
1353 }
1354 
1355 /// This function is required to break recursion. Visiting phis in a loop may
1356 /// result in recursion during compilation. We break the recursion by making
1357 /// sure that we visit a MachineOperand and its definition in a
1358 /// MachineInstruction only once. If we attempt to visit more than once, then
1359 /// there is recursion, and will return false.
1360 bool HexagonHardwareLoops::isLoopFeeder(MachineLoop *L, MachineBasicBlock *A,
1361                                         MachineInstr *MI,
1362                                         const MachineOperand *MO,
1363                                         LoopFeederMap &LoopFeederPhi) const {
1364   if (LoopFeederPhi.find(MO->getReg()) == LoopFeederPhi.end()) {
1365     LLVM_DEBUG(dbgs() << "\nhw_loop head, "
1366                       << printMBBReference(**L->block_begin()));
1367     // Ignore all BBs that form Loop.
1368     if (llvm::is_contained(L->getBlocks(), A))
1369       return false;
1370     MachineInstr *Def = MRI->getVRegDef(MO->getReg());
1371     LoopFeederPhi.insert(std::make_pair(MO->getReg(), Def));
1372     return true;
1373   } else
1374     // Already visited node.
1375     return false;
1376 }
1377 
1378 /// Return true if a Phi may generate a value that can underflow.
1379 /// This function calls loopCountMayWrapOrUnderFlow for each Phi operand.
1380 bool HexagonHardwareLoops::phiMayWrapOrUnderflow(
1381     MachineInstr *Phi, const MachineOperand *EndVal, MachineBasicBlock *MBB,
1382     MachineLoop *L, LoopFeederMap &LoopFeederPhi) const {
1383   assert(Phi->isPHI() && "Expecting a Phi.");
1384   // Walk through each Phi, and its used operands. Make sure that
1385   // if there is recursion in Phi, we won't generate hardware loops.
1386   for (int i = 1, n = Phi->getNumOperands(); i < n; i += 2)
1387     if (isLoopFeeder(L, MBB, Phi, &(Phi->getOperand(i)), LoopFeederPhi))
1388       if (loopCountMayWrapOrUnderFlow(&(Phi->getOperand(i)), EndVal,
1389                                       Phi->getParent(), L, LoopFeederPhi))
1390         return true;
1391   return false;
1392 }
1393 
1394 /// Return true if the induction variable can underflow in the first iteration.
1395 /// An example, is an initial unsigned value that is 0 and is decrement in the
1396 /// first itertion of a do-while loop.  In this case, we cannot generate a
1397 /// hardware loop because the endloop instruction does not decrement the loop
1398 /// counter if it is <= 1. We only need to perform this analysis if the
1399 /// initial value is a register.
1400 ///
1401 /// This function assumes the initial value may underfow unless proven
1402 /// otherwise. If the type is signed, then we don't care because signed
1403 /// underflow is undefined. We attempt to prove the initial value is not
1404 /// zero by perfoming a crude analysis of the loop counter. This function
1405 /// checks if the initial value is used in any comparison prior to the loop
1406 /// and, if so, assumes the comparison is a range check. This is inexact,
1407 /// but will catch the simple cases.
1408 bool HexagonHardwareLoops::loopCountMayWrapOrUnderFlow(
1409     const MachineOperand *InitVal, const MachineOperand *EndVal,
1410     MachineBasicBlock *MBB, MachineLoop *L,
1411     LoopFeederMap &LoopFeederPhi) const {
1412   // Only check register values since they are unknown.
1413   if (!InitVal->isReg())
1414     return false;
1415 
1416   if (!EndVal->isImm())
1417     return false;
1418 
1419   // A register value that is assigned an immediate is a known value, and it
1420   // won't underflow in the first iteration.
1421   int64_t Imm;
1422   if (checkForImmediate(*InitVal, Imm))
1423     return (EndVal->getImm() == Imm);
1424 
1425   Register Reg = InitVal->getReg();
1426 
1427   // We don't know the value of a physical register.
1428   if (!Reg.isVirtual())
1429     return true;
1430 
1431   MachineInstr *Def = MRI->getVRegDef(Reg);
1432   if (!Def)
1433     return true;
1434 
1435   // If the initial value is a Phi or copy and the operands may not underflow,
1436   // then the definition cannot be underflow either.
1437   if (Def->isPHI() && !phiMayWrapOrUnderflow(Def, EndVal, Def->getParent(),
1438                                              L, LoopFeederPhi))
1439     return false;
1440   if (Def->isCopy() && !loopCountMayWrapOrUnderFlow(&(Def->getOperand(1)),
1441                                                     EndVal, Def->getParent(),
1442                                                     L, LoopFeederPhi))
1443     return false;
1444 
1445   // Iterate over the uses of the initial value. If the initial value is used
1446   // in a compare, then we assume this is a range check that ensures the loop
1447   // doesn't underflow. This is not an exact test and should be improved.
1448   for (MachineRegisterInfo::use_instr_nodbg_iterator I = MRI->use_instr_nodbg_begin(Reg),
1449          E = MRI->use_instr_nodbg_end(); I != E; ++I) {
1450     MachineInstr *MI = &*I;
1451     Register CmpReg1, CmpReg2;
1452     int64_t CmpMask = 0, CmpValue = 0;
1453 
1454     if (!TII->analyzeCompare(*MI, CmpReg1, CmpReg2, CmpMask, CmpValue))
1455       continue;
1456 
1457     MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
1458     SmallVector<MachineOperand, 2> Cond;
1459     if (TII->analyzeBranch(*MI->getParent(), TBB, FBB, Cond, false))
1460       continue;
1461 
1462     Comparison::Kind Cmp =
1463         getComparisonKind(MI->getOpcode(), nullptr, nullptr, 0);
1464     if (Cmp == 0)
1465       continue;
1466     if (TII->predOpcodeHasNot(Cond) ^ (TBB != MBB))
1467       Cmp = Comparison::getNegatedComparison(Cmp);
1468     if (CmpReg2 != 0 && CmpReg2 == Reg)
1469       Cmp = Comparison::getSwappedComparison(Cmp);
1470 
1471     // Signed underflow is undefined.
1472     if (Comparison::isSigned(Cmp))
1473       return false;
1474 
1475     // Check if there is a comparison of the initial value. If the initial value
1476     // is greater than or not equal to another value, then assume this is a
1477     // range check.
1478     if ((Cmp & Comparison::G) || Cmp == Comparison::NE)
1479       return false;
1480   }
1481 
1482   // OK - this is a hack that needs to be improved. We really need to analyze
1483   // the instructions performed on the initial value. This works on the simplest
1484   // cases only.
1485   if (!Def->isCopy() && !Def->isPHI())
1486     return false;
1487 
1488   return true;
1489 }
1490 
1491 bool HexagonHardwareLoops::checkForImmediate(const MachineOperand &MO,
1492                                              int64_t &Val) const {
1493   if (MO.isImm()) {
1494     Val = MO.getImm();
1495     return true;
1496   }
1497   if (!MO.isReg())
1498     return false;
1499 
1500   // MO is a register. Check whether it is defined as an immediate value,
1501   // and if so, get the value of it in TV. That value will then need to be
1502   // processed to handle potential subregisters in MO.
1503   int64_t TV;
1504 
1505   Register R = MO.getReg();
1506   if (!R.isVirtual())
1507     return false;
1508   MachineInstr *DI = MRI->getVRegDef(R);
1509   unsigned DOpc = DI->getOpcode();
1510   switch (DOpc) {
1511     case TargetOpcode::COPY:
1512     case Hexagon::A2_tfrsi:
1513     case Hexagon::A2_tfrpi:
1514     case Hexagon::CONST32:
1515     case Hexagon::CONST64:
1516       // Call recursively to avoid an extra check whether operand(1) is
1517       // indeed an immediate (it could be a global address, for example),
1518       // plus we can handle COPY at the same time.
1519       if (!checkForImmediate(DI->getOperand(1), TV))
1520         return false;
1521       break;
1522     case Hexagon::A2_combineii:
1523     case Hexagon::A4_combineir:
1524     case Hexagon::A4_combineii:
1525     case Hexagon::A4_combineri:
1526     case Hexagon::A2_combinew: {
1527       const MachineOperand &S1 = DI->getOperand(1);
1528       const MachineOperand &S2 = DI->getOperand(2);
1529       int64_t V1, V2;
1530       if (!checkForImmediate(S1, V1) || !checkForImmediate(S2, V2))
1531         return false;
1532       TV = V2 | (static_cast<uint64_t>(V1) << 32);
1533       break;
1534     }
1535     case TargetOpcode::REG_SEQUENCE: {
1536       const MachineOperand &S1 = DI->getOperand(1);
1537       const MachineOperand &S3 = DI->getOperand(3);
1538       int64_t V1, V3;
1539       if (!checkForImmediate(S1, V1) || !checkForImmediate(S3, V3))
1540         return false;
1541       unsigned Sub2 = DI->getOperand(2).getImm();
1542       unsigned Sub4 = DI->getOperand(4).getImm();
1543       if (Sub2 == Hexagon::isub_lo && Sub4 == Hexagon::isub_hi)
1544         TV = V1 | (V3 << 32);
1545       else if (Sub2 == Hexagon::isub_hi && Sub4 == Hexagon::isub_lo)
1546         TV = V3 | (V1 << 32);
1547       else
1548         llvm_unreachable("Unexpected form of REG_SEQUENCE");
1549       break;
1550     }
1551 
1552     default:
1553       return false;
1554   }
1555 
1556   // By now, we should have successfully obtained the immediate value defining
1557   // the register referenced in MO. Handle a potential use of a subregister.
1558   switch (MO.getSubReg()) {
1559     case Hexagon::isub_lo:
1560       Val = TV & 0xFFFFFFFFULL;
1561       break;
1562     case Hexagon::isub_hi:
1563       Val = (TV >> 32) & 0xFFFFFFFFULL;
1564       break;
1565     default:
1566       Val = TV;
1567       break;
1568   }
1569   return true;
1570 }
1571 
1572 void HexagonHardwareLoops::setImmediate(MachineOperand &MO, int64_t Val) {
1573   if (MO.isImm()) {
1574     MO.setImm(Val);
1575     return;
1576   }
1577 
1578   assert(MO.isReg());
1579   Register R = MO.getReg();
1580   MachineInstr *DI = MRI->getVRegDef(R);
1581 
1582   const TargetRegisterClass *RC = MRI->getRegClass(R);
1583   Register NewR = MRI->createVirtualRegister(RC);
1584   MachineBasicBlock &B = *DI->getParent();
1585   DebugLoc DL = DI->getDebugLoc();
1586   BuildMI(B, DI, DL, TII->get(DI->getOpcode()), NewR).addImm(Val);
1587   MO.setReg(NewR);
1588 }
1589 
1590 bool HexagonHardwareLoops::fixupInductionVariable(MachineLoop *L) {
1591   MachineBasicBlock *Header = L->getHeader();
1592   MachineBasicBlock *Latch = L->getLoopLatch();
1593   MachineBasicBlock *ExitingBlock = L->findLoopControlBlock();
1594 
1595   if (!(Header && Latch && ExitingBlock))
1596     return false;
1597 
1598   // These data structures follow the same concept as the corresponding
1599   // ones in findInductionRegister (where some comments are).
1600   using RegisterBump = std::pair<unsigned, int64_t>;
1601   using RegisterInduction = std::pair<unsigned, RegisterBump>;
1602   using RegisterInductionSet = std::set<RegisterInduction>;
1603 
1604   // Register candidates for induction variables, with their associated bumps.
1605   RegisterInductionSet IndRegs;
1606 
1607   // Look for induction patterns:
1608   //   %1 = PHI ..., [ latch, %2 ]
1609   //   %2 = ADD %1, imm
1610   using instr_iterator = MachineBasicBlock::instr_iterator;
1611 
1612   for (instr_iterator I = Header->instr_begin(), E = Header->instr_end();
1613        I != E && I->isPHI(); ++I) {
1614     MachineInstr *Phi = &*I;
1615 
1616     // Have a PHI instruction.
1617     for (unsigned i = 1, n = Phi->getNumOperands(); i < n; i += 2) {
1618       if (Phi->getOperand(i+1).getMBB() != Latch)
1619         continue;
1620 
1621       Register PhiReg = Phi->getOperand(i).getReg();
1622       MachineInstr *DI = MRI->getVRegDef(PhiReg);
1623 
1624       if (DI->getDesc().isAdd()) {
1625         // If the register operand to the add/sub is the PHI we are looking
1626         // at, this meets the induction pattern.
1627         Register IndReg = DI->getOperand(1).getReg();
1628         MachineOperand &Opnd2 = DI->getOperand(2);
1629         int64_t V;
1630         if (MRI->getVRegDef(IndReg) == Phi && checkForImmediate(Opnd2, V)) {
1631           Register UpdReg = DI->getOperand(0).getReg();
1632           IndRegs.insert(std::make_pair(UpdReg, std::make_pair(IndReg, V)));
1633         }
1634       }
1635     }  // for (i)
1636   }  // for (instr)
1637 
1638   if (IndRegs.empty())
1639     return false;
1640 
1641   MachineBasicBlock *TB = nullptr, *FB = nullptr;
1642   SmallVector<MachineOperand,2> Cond;
1643   // analyzeBranch returns true if it fails to analyze branch.
1644   bool NotAnalyzed = TII->analyzeBranch(*ExitingBlock, TB, FB, Cond, false);
1645   if (NotAnalyzed || Cond.empty())
1646     return false;
1647 
1648   if (ExitingBlock != Latch && (TB == Latch || FB == Latch)) {
1649     MachineBasicBlock *LTB = nullptr, *LFB = nullptr;
1650     SmallVector<MachineOperand,2> LCond;
1651     bool NotAnalyzed = TII->analyzeBranch(*Latch, LTB, LFB, LCond, false);
1652     if (NotAnalyzed)
1653       return false;
1654 
1655     // Since latch is not the exiting block, the latch branch should be an
1656     // unconditional branch to the loop header.
1657     if (TB == Latch)
1658       TB = (LTB == Header) ? LTB : LFB;
1659     else
1660       FB = (LTB == Header) ? LTB : LFB;
1661   }
1662   if (TB != Header) {
1663     if (FB != Header) {
1664       // The latch/exit block does not go back to the header.
1665       return false;
1666     }
1667     // FB is the header (i.e., uncond. jump to branch header)
1668     // In this case, the LoopBody -> TB should not be a back edge otherwise
1669     // it could result in an infinite loop after conversion to hw_loop.
1670     // This case can happen when the Latch has two jumps like this:
1671     // Jmp_c OuterLoopHeader <-- TB
1672     // Jmp   InnerLoopHeader <-- FB
1673     if (MDT->dominates(TB, FB))
1674       return false;
1675   }
1676 
1677   // Expecting a predicate register as a condition.  It won't be a hardware
1678   // predicate register at this point yet, just a vreg.
1679   // HexagonInstrInfo::analyzeBranch for negated branches inserts imm(0)
1680   // into Cond, followed by the predicate register.  For non-negated branches
1681   // it's just the register.
1682   unsigned CSz = Cond.size();
1683   if (CSz != 1 && CSz != 2)
1684     return false;
1685 
1686   if (!Cond[CSz-1].isReg())
1687     return false;
1688 
1689   Register P = Cond[CSz - 1].getReg();
1690   MachineInstr *PredDef = MRI->getVRegDef(P);
1691 
1692   if (!PredDef->isCompare())
1693     return false;
1694 
1695   SmallSet<unsigned,2> CmpRegs;
1696   MachineOperand *CmpImmOp = nullptr;
1697 
1698   // Go over all operands to the compare and look for immediate and register
1699   // operands.  Assume that if the compare has a single register use and a
1700   // single immediate operand, then the register is being compared with the
1701   // immediate value.
1702   for (unsigned i = 0, n = PredDef->getNumOperands(); i < n; ++i) {
1703     MachineOperand &MO = PredDef->getOperand(i);
1704     if (MO.isReg()) {
1705       // Skip all implicit references.  In one case there was:
1706       //   %140 = FCMPUGT32_rr %138, %139, implicit %usr
1707       if (MO.isImplicit())
1708         continue;
1709       if (MO.isUse()) {
1710         if (!isImmediate(MO)) {
1711           CmpRegs.insert(MO.getReg());
1712           continue;
1713         }
1714         // Consider the register to be the "immediate" operand.
1715         if (CmpImmOp)
1716           return false;
1717         CmpImmOp = &MO;
1718       }
1719     } else if (MO.isImm()) {
1720       if (CmpImmOp)    // A second immediate argument?  Confusing.  Bail out.
1721         return false;
1722       CmpImmOp = &MO;
1723     }
1724   }
1725 
1726   if (CmpRegs.empty())
1727     return false;
1728 
1729   // Check if the compared register follows the order we want.  Fix if needed.
1730   for (RegisterInductionSet::iterator I = IndRegs.begin(), E = IndRegs.end();
1731        I != E; ++I) {
1732     // This is a success.  If the register used in the comparison is one that
1733     // we have identified as a bumped (updated) induction register, there is
1734     // nothing to do.
1735     if (CmpRegs.count(I->first))
1736       return true;
1737 
1738     // Otherwise, if the register being compared comes out of a PHI node,
1739     // and has been recognized as following the induction pattern, and is
1740     // compared against an immediate, we can fix it.
1741     const RegisterBump &RB = I->second;
1742     if (CmpRegs.count(RB.first)) {
1743       if (!CmpImmOp) {
1744         // If both operands to the compare instruction are registers, see if
1745         // it can be changed to use induction register as one of the operands.
1746         MachineInstr *IndI = nullptr;
1747         MachineInstr *nonIndI = nullptr;
1748         MachineOperand *IndMO = nullptr;
1749         MachineOperand *nonIndMO = nullptr;
1750 
1751         for (unsigned i = 1, n = PredDef->getNumOperands(); i < n; ++i) {
1752           MachineOperand &MO = PredDef->getOperand(i);
1753           if (MO.isReg() && MO.getReg() == RB.first) {
1754             LLVM_DEBUG(dbgs() << "\n DefMI(" << i
1755                               << ") = " << *(MRI->getVRegDef(I->first)));
1756             if (IndI)
1757               return false;
1758 
1759             IndI = MRI->getVRegDef(I->first);
1760             IndMO = &MO;
1761           } else if (MO.isReg()) {
1762             LLVM_DEBUG(dbgs() << "\n DefMI(" << i
1763                               << ") = " << *(MRI->getVRegDef(MO.getReg())));
1764             if (nonIndI)
1765               return false;
1766 
1767             nonIndI = MRI->getVRegDef(MO.getReg());
1768             nonIndMO = &MO;
1769           }
1770         }
1771         if (IndI && nonIndI &&
1772             nonIndI->getOpcode() == Hexagon::A2_addi &&
1773             nonIndI->getOperand(2).isImm() &&
1774             nonIndI->getOperand(2).getImm() == - RB.second) {
1775           bool Order = orderBumpCompare(IndI, PredDef);
1776           if (Order) {
1777             IndMO->setReg(I->first);
1778             nonIndMO->setReg(nonIndI->getOperand(1).getReg());
1779             return true;
1780           }
1781         }
1782         return false;
1783       }
1784 
1785       // It is not valid to do this transformation on an unsigned comparison
1786       // because it may underflow.
1787       Comparison::Kind Cmp =
1788           getComparisonKind(PredDef->getOpcode(), nullptr, nullptr, 0);
1789       if (!Cmp || Comparison::isUnsigned(Cmp))
1790         return false;
1791 
1792       // If the register is being compared against an immediate, try changing
1793       // the compare instruction to use induction register and adjust the
1794       // immediate operand.
1795       int64_t CmpImm = getImmediate(*CmpImmOp);
1796       int64_t V = RB.second;
1797       // Handle Overflow (64-bit).
1798       if (((V > 0) && (CmpImm > INT64_MAX - V)) ||
1799           ((V < 0) && (CmpImm < INT64_MIN - V)))
1800         return false;
1801       CmpImm += V;
1802       // Most comparisons of register against an immediate value allow
1803       // the immediate to be constant-extended. There are some exceptions
1804       // though. Make sure the new combination will work.
1805       if (CmpImmOp->isImm() && !TII->isExtendable(*PredDef) &&
1806           !TII->isValidOffset(PredDef->getOpcode(), CmpImm, TRI, false))
1807         return false;
1808 
1809       // Make sure that the compare happens after the bump.  Otherwise,
1810       // after the fixup, the compare would use a yet-undefined register.
1811       MachineInstr *BumpI = MRI->getVRegDef(I->first);
1812       bool Order = orderBumpCompare(BumpI, PredDef);
1813       if (!Order)
1814         return false;
1815 
1816       // Finally, fix the compare instruction.
1817       setImmediate(*CmpImmOp, CmpImm);
1818       for (unsigned i = 0, n = PredDef->getNumOperands(); i < n; ++i) {
1819         MachineOperand &MO = PredDef->getOperand(i);
1820         if (MO.isReg() && MO.getReg() == RB.first) {
1821           MO.setReg(I->first);
1822           return true;
1823         }
1824       }
1825     }
1826   }
1827 
1828   return false;
1829 }
1830 
1831 /// createPreheaderForLoop - Create a preheader for a given loop.
1832 MachineBasicBlock *HexagonHardwareLoops::createPreheaderForLoop(
1833       MachineLoop *L) {
1834   if (MachineBasicBlock *TmpPH = MLI->findLoopPreheader(L, SpecPreheader))
1835     return TmpPH;
1836   if (!HWCreatePreheader)
1837     return nullptr;
1838 
1839   MachineBasicBlock *Header = L->getHeader();
1840   MachineBasicBlock *Latch = L->getLoopLatch();
1841   MachineBasicBlock *ExitingBlock = L->findLoopControlBlock();
1842   MachineFunction *MF = Header->getParent();
1843   DebugLoc DL;
1844 
1845 #ifndef NDEBUG
1846   if ((!PHFn.empty()) && (PHFn != MF->getName()))
1847     return nullptr;
1848 #endif
1849 
1850   if (!Latch || !ExitingBlock || Header->hasAddressTaken())
1851     return nullptr;
1852 
1853   using instr_iterator = MachineBasicBlock::instr_iterator;
1854 
1855   // Verify that all existing predecessors have analyzable branches
1856   // (or no branches at all).
1857   using MBBVector = std::vector<MachineBasicBlock *>;
1858 
1859   MBBVector Preds(Header->pred_begin(), Header->pred_end());
1860   SmallVector<MachineOperand,2> Tmp1;
1861   MachineBasicBlock *TB = nullptr, *FB = nullptr;
1862 
1863   if (TII->analyzeBranch(*ExitingBlock, TB, FB, Tmp1, false))
1864     return nullptr;
1865 
1866   for (MachineBasicBlock *PB : Preds) {
1867     bool NotAnalyzed = TII->analyzeBranch(*PB, TB, FB, Tmp1, false);
1868     if (NotAnalyzed)
1869       return nullptr;
1870   }
1871 
1872   MachineBasicBlock *NewPH = MF->CreateMachineBasicBlock();
1873   MF->insert(Header->getIterator(), NewPH);
1874 
1875   if (Header->pred_size() > 2) {
1876     // Ensure that the header has only two predecessors: the preheader and
1877     // the loop latch.  Any additional predecessors of the header should
1878     // join at the newly created preheader. Inspect all PHI nodes from the
1879     // header and create appropriate corresponding PHI nodes in the preheader.
1880 
1881     for (instr_iterator I = Header->instr_begin(), E = Header->instr_end();
1882          I != E && I->isPHI(); ++I) {
1883       MachineInstr *PN = &*I;
1884 
1885       const MCInstrDesc &PD = TII->get(TargetOpcode::PHI);
1886       MachineInstr *NewPN = MF->CreateMachineInstr(PD, DL);
1887       NewPH->insert(NewPH->end(), NewPN);
1888 
1889       Register PR = PN->getOperand(0).getReg();
1890       const TargetRegisterClass *RC = MRI->getRegClass(PR);
1891       Register NewPR = MRI->createVirtualRegister(RC);
1892       NewPN->addOperand(MachineOperand::CreateReg(NewPR, true));
1893 
1894       // Copy all non-latch operands of a header's PHI node to the newly
1895       // created PHI node in the preheader.
1896       for (unsigned i = 1, n = PN->getNumOperands(); i < n; i += 2) {
1897         Register PredR = PN->getOperand(i).getReg();
1898         unsigned PredRSub = PN->getOperand(i).getSubReg();
1899         MachineBasicBlock *PredB = PN->getOperand(i+1).getMBB();
1900         if (PredB == Latch)
1901           continue;
1902 
1903         MachineOperand MO = MachineOperand::CreateReg(PredR, false);
1904         MO.setSubReg(PredRSub);
1905         NewPN->addOperand(MO);
1906         NewPN->addOperand(MachineOperand::CreateMBB(PredB));
1907       }
1908 
1909       // Remove copied operands from the old PHI node and add the value
1910       // coming from the preheader's PHI.
1911       for (int i = PN->getNumOperands()-2; i > 0; i -= 2) {
1912         MachineBasicBlock *PredB = PN->getOperand(i+1).getMBB();
1913         if (PredB != Latch) {
1914           PN->removeOperand(i+1);
1915           PN->removeOperand(i);
1916         }
1917       }
1918       PN->addOperand(MachineOperand::CreateReg(NewPR, false));
1919       PN->addOperand(MachineOperand::CreateMBB(NewPH));
1920     }
1921   } else {
1922     assert(Header->pred_size() == 2);
1923 
1924     // The header has only two predecessors, but the non-latch predecessor
1925     // is not a preheader (e.g. it has other successors, etc.)
1926     // In such a case we don't need any extra PHI nodes in the new preheader,
1927     // all we need is to adjust existing PHIs in the header to now refer to
1928     // the new preheader.
1929     for (instr_iterator I = Header->instr_begin(), E = Header->instr_end();
1930          I != E && I->isPHI(); ++I) {
1931       MachineInstr *PN = &*I;
1932       for (unsigned i = 1, n = PN->getNumOperands(); i < n; i += 2) {
1933         MachineOperand &MO = PN->getOperand(i+1);
1934         if (MO.getMBB() != Latch)
1935           MO.setMBB(NewPH);
1936       }
1937     }
1938   }
1939 
1940   // "Reroute" the CFG edges to link in the new preheader.
1941   // If any of the predecessors falls through to the header, insert a branch
1942   // to the new preheader in that place.
1943   SmallVector<MachineOperand,1> Tmp2;
1944   SmallVector<MachineOperand,1> EmptyCond;
1945 
1946   TB = FB = nullptr;
1947 
1948   for (MachineBasicBlock *PB : Preds) {
1949     if (PB != Latch) {
1950       Tmp2.clear();
1951       bool NotAnalyzed = TII->analyzeBranch(*PB, TB, FB, Tmp2, false);
1952       (void)NotAnalyzed; // suppress compiler warning
1953       assert (!NotAnalyzed && "Should be analyzable!");
1954       if (TB != Header && (Tmp2.empty() || FB != Header))
1955         TII->insertBranch(*PB, NewPH, nullptr, EmptyCond, DL);
1956       PB->ReplaceUsesOfBlockWith(Header, NewPH);
1957     }
1958   }
1959 
1960   // It can happen that the latch block will fall through into the header.
1961   // Insert an unconditional branch to the header.
1962   TB = FB = nullptr;
1963   bool LatchNotAnalyzed = TII->analyzeBranch(*Latch, TB, FB, Tmp2, false);
1964   (void)LatchNotAnalyzed; // suppress compiler warning
1965   assert (!LatchNotAnalyzed && "Should be analyzable!");
1966   if (!TB && !FB)
1967     TII->insertBranch(*Latch, Header, nullptr, EmptyCond, DL);
1968 
1969   // Finally, the branch from the preheader to the header.
1970   TII->insertBranch(*NewPH, Header, nullptr, EmptyCond, DL);
1971   NewPH->addSuccessor(Header);
1972 
1973   MachineLoop *ParentLoop = L->getParentLoop();
1974   if (ParentLoop)
1975     ParentLoop->addBasicBlockToLoop(NewPH, MLI->getBase());
1976 
1977   // Update the dominator information with the new preheader.
1978   if (MDT) {
1979     if (MachineDomTreeNode *HN = MDT->getNode(Header)) {
1980       if (MachineDomTreeNode *DHN = HN->getIDom()) {
1981         MDT->addNewBlock(NewPH, DHN->getBlock());
1982         MDT->changeImmediateDominator(Header, NewPH);
1983       }
1984     }
1985   }
1986 
1987   return NewPH;
1988 }
1989