1 //===-- HexagonHardwareLoops.cpp - Identify and generate hardware loops ---===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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.
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.
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 function calls in loops.
26 //===----------------------------------------------------------------------===//
28 #include "llvm/ADT/SmallSet.h"
30 #include "HexagonSubtarget.h"
31 #include "llvm/ADT/Statistic.h"
32 #include "llvm/CodeGen/MachineDominators.h"
33 #include "llvm/CodeGen/MachineFunction.h"
34 #include "llvm/CodeGen/MachineFunctionPass.h"
35 #include "llvm/CodeGen/MachineInstrBuilder.h"
36 #include "llvm/CodeGen/MachineLoopInfo.h"
37 #include "llvm/CodeGen/MachineRegisterInfo.h"
38 #include "llvm/PassSupport.h"
39 #include "llvm/Support/CommandLine.h"
40 #include "llvm/Support/Debug.h"
41 #include "llvm/Support/raw_ostream.h"
42 #include "llvm/Target/TargetInstrInfo.h"
48 #define DEBUG_TYPE "hwloops"
51 static cl::opt<int> HWLoopLimit("hexagon-max-hwloop", cl::Hidden, cl::init(-1));
53 // Option to create preheader only for a specific function.
54 static cl::opt<std::string> PHFn("hexagon-hwloop-phfn", cl::Hidden,
58 // Option to create a preheader if one doesn't exist.
59 static cl::opt<bool> HWCreatePreheader("hexagon-hwloop-preheader",
60 cl::Hidden, cl::init(true),
61 cl::desc("Add a preheader to a hardware loop if one doesn't exist"));
63 STATISTIC(NumHWLoops, "Number of loops converted to hardware loops");
66 FunctionPass *createHexagonHardwareLoops();
67 void initializeHexagonHardwareLoopsPass(PassRegistry&);
72 struct HexagonHardwareLoops : public MachineFunctionPass {
74 MachineRegisterInfo *MRI;
75 MachineDominatorTree *MDT;
76 const HexagonInstrInfo *TII;
84 HexagonHardwareLoops() : MachineFunctionPass(ID) {
85 initializeHexagonHardwareLoopsPass(*PassRegistry::getPassRegistry());
88 bool runOnMachineFunction(MachineFunction &MF) override;
90 const char *getPassName() const override { return "Hexagon Hardware Loops"; }
92 void getAnalysisUsage(AnalysisUsage &AU) const override {
93 AU.addRequired<MachineDominatorTree>();
94 AU.addRequired<MachineLoopInfo>();
95 MachineFunctionPass::getAnalysisUsage(AU);
99 typedef std::map<unsigned, MachineInstr *> LoopFeederMap;
101 /// Kinds of comparisons in the compare instructions.
119 static Kind getSwappedComparison(Kind Cmp) {
120 assert ((!((Cmp & L) && (Cmp & G))) && "Malformed comparison operator");
121 if ((Cmp & L) || (Cmp & G))
122 return (Kind)(Cmp ^ (L|G));
126 static Kind getNegatedComparison(Kind Cmp) {
127 if ((Cmp & L) || (Cmp & G))
128 return (Kind)((Cmp ^ (L | G)) ^ EQ);
129 if ((Cmp & NE) || (Cmp & EQ))
130 return (Kind)(Cmp ^ (EQ | NE));
134 static bool isSigned(Kind Cmp) {
135 return (Cmp & (L | G) && !(Cmp & U));
138 static bool isUnsigned(Kind Cmp) {
144 /// \brief Find the register that contains the loop controlling
145 /// induction variable.
146 /// If successful, it will return true and set the \p Reg, \p IVBump
147 /// and \p IVOp arguments. Otherwise it will return false.
148 /// The returned induction register is the register R that follows the
149 /// following induction pattern:
151 /// R = phi ..., [ R.next, LatchBlock ]
152 /// R.next = R + #bump
153 /// if (R.next < #N) goto loop
154 /// IVBump is the immediate value added to R, and IVOp is the instruction
155 /// "R.next = R + #bump".
156 bool findInductionRegister(MachineLoop *L, unsigned &Reg,
157 int64_t &IVBump, MachineInstr *&IVOp) const;
159 /// \brief Return the comparison kind for the specified opcode.
160 Comparison::Kind getComparisonKind(unsigned CondOpc,
161 MachineOperand *InitialValue,
162 const MachineOperand *Endvalue,
163 int64_t IVBump) const;
165 /// \brief Analyze the statements in a loop to determine if the loop
166 /// has a computable trip count and, if so, return a value that represents
167 /// the trip count expression.
168 CountValue *getLoopTripCount(MachineLoop *L,
169 SmallVectorImpl<MachineInstr *> &OldInsts);
171 /// \brief Return the expression that represents the number of times
172 /// a loop iterates. The function takes the operands that represent the
173 /// loop start value, loop end value, and induction value. Based upon
174 /// these operands, the function attempts to compute the trip count.
175 /// If the trip count is not directly available (as an immediate value,
176 /// or a register), the function will attempt to insert computation of it
177 /// to the loop's preheader.
178 CountValue *computeCount(MachineLoop *Loop, const MachineOperand *Start,
179 const MachineOperand *End, unsigned IVReg,
180 int64_t IVBump, Comparison::Kind Cmp) const;
182 /// \brief Return true if the instruction is not valid within a hardware
184 bool isInvalidLoopOperation(const MachineInstr *MI,
185 bool IsInnerHWLoop) const;
187 /// \brief Return true if the loop contains an instruction that inhibits
188 /// using the hardware loop.
189 bool containsInvalidInstruction(MachineLoop *L, bool IsInnerHWLoop) const;
191 /// \brief Given a loop, check if we can convert it to a hardware loop.
192 /// If so, then perform the conversion and return true.
193 bool convertToHardwareLoop(MachineLoop *L, bool &L0used, bool &L1used);
195 /// \brief Return true if the instruction is now dead.
196 bool isDead(const MachineInstr *MI,
197 SmallVectorImpl<MachineInstr *> &DeadPhis) const;
199 /// \brief Remove the instruction if it is now dead.
200 void removeIfDead(MachineInstr *MI);
202 /// \brief Make sure that the "bump" instruction executes before the
203 /// compare. We need that for the IV fixup, so that the compare
204 /// instruction would not use a bumped value that has not yet been
205 /// defined. If the instructions are out of order, try to reorder them.
206 bool orderBumpCompare(MachineInstr *BumpI, MachineInstr *CmpI);
208 /// \brief Return true if MO and MI pair is visited only once. If visited
209 /// more than once, this indicates there is recursion. In such a case,
211 bool isLoopFeeder(MachineLoop *L, MachineBasicBlock *A, MachineInstr *MI,
212 const MachineOperand *MO,
213 LoopFeederMap &LoopFeederPhi) const;
215 /// \brief Return true if the Phi may generate a value that may underflow,
217 bool phiMayWrapOrUnderflow(MachineInstr *Phi, const MachineOperand *EndVal,
218 MachineBasicBlock *MBB, MachineLoop *L,
219 LoopFeederMap &LoopFeederPhi) const;
221 /// \brief Return true if the induction variable may underflow an unsigned
222 /// value in the first iteration.
223 bool loopCountMayWrapOrUnderFlow(const MachineOperand *InitVal,
224 const MachineOperand *EndVal,
225 MachineBasicBlock *MBB, MachineLoop *L,
226 LoopFeederMap &LoopFeederPhi) const;
228 /// \brief Check if the given operand has a compile-time known constant
229 /// value. Return true if yes, and false otherwise. When returning true, set
230 /// Val to the corresponding constant value.
231 bool checkForImmediate(const MachineOperand &MO, int64_t &Val) const;
233 /// \brief Check if the operand has a compile-time known constant value.
234 bool isImmediate(const MachineOperand &MO) const {
236 return checkForImmediate(MO, V);
239 /// \brief Return the immediate for the specified operand.
240 int64_t getImmediate(const MachineOperand &MO) const {
242 if (!checkForImmediate(MO, V))
243 llvm_unreachable("Invalid operand");
247 /// \brief Reset the given machine operand to now refer to a new immediate
248 /// value. Assumes that the operand was already referencing an immediate
249 /// value, either directly, or via a register.
250 void setImmediate(MachineOperand &MO, int64_t Val);
252 /// \brief Fix the data flow of the induction varible.
253 /// The desired flow is: phi ---> bump -+-> comparison-in-latch.
256 /// where "bump" is the increment of the induction variable:
257 /// iv = iv + #const.
258 /// Due to some prior code transformations, the actual flow may look
260 /// phi -+-> bump ---> back to phi
262 /// +-> comparison-in-latch (against upper_bound-bump),
263 /// i.e. the comparison that controls the loop execution may be using
264 /// the value of the induction variable from before the increment.
266 /// Return true if the loop's flow is the desired one (i.e. it's
267 /// either been fixed, or no fixing was necessary).
268 /// Otherwise, return false. This can happen if the induction variable
269 /// couldn't be identified, or if the value in the latch's comparison
270 /// cannot be adjusted to reflect the post-bump value.
271 bool fixupInductionVariable(MachineLoop *L);
273 /// \brief Given a loop, if it does not have a preheader, create one.
274 /// Return the block that is the preheader.
275 MachineBasicBlock *createPreheaderForLoop(MachineLoop *L);
278 char HexagonHardwareLoops::ID = 0;
280 int HexagonHardwareLoops::Counter = 0;
283 /// \brief Abstraction for a trip count of a loop. A smaller version
284 /// of the MachineOperand class without the concerns of changing the
285 /// operand representation.
288 enum CountValueType {
303 explicit CountValue(CountValueType t, unsigned v, unsigned u = 0) {
305 if (Kind == CV_Register) {
312 bool isReg() const { return Kind == CV_Register; }
313 bool isImm() const { return Kind == CV_Immediate; }
315 unsigned getReg() const {
316 assert(isReg() && "Wrong CountValue accessor");
317 return Contents.R.Reg;
319 unsigned getSubReg() const {
320 assert(isReg() && "Wrong CountValue accessor");
321 return Contents.R.Sub;
323 unsigned getImm() const {
324 assert(isImm() && "Wrong CountValue accessor");
325 return Contents.ImmVal;
328 void print(raw_ostream &OS, const TargetRegisterInfo *TRI = nullptr) const {
329 if (isReg()) { OS << PrintReg(Contents.R.Reg, TRI, Contents.R.Sub); }
330 if (isImm()) { OS << Contents.ImmVal; }
333 } // end anonymous namespace
336 INITIALIZE_PASS_BEGIN(HexagonHardwareLoops, "hwloops",
337 "Hexagon Hardware Loops", false, false)
338 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
339 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
340 INITIALIZE_PASS_END(HexagonHardwareLoops, "hwloops",
341 "Hexagon Hardware Loops", false, false)
343 FunctionPass *llvm::createHexagonHardwareLoops() {
344 return new HexagonHardwareLoops();
347 bool HexagonHardwareLoops::runOnMachineFunction(MachineFunction &MF) {
348 DEBUG(dbgs() << "********* Hexagon Hardware Loops *********\n");
350 bool Changed = false;
352 MLI = &getAnalysis<MachineLoopInfo>();
353 MRI = &MF.getRegInfo();
354 MDT = &getAnalysis<MachineDominatorTree>();
355 TII = MF.getSubtarget<HexagonSubtarget>().getInstrInfo();
358 if (!L->getParentLoop()) {
361 Changed |= convertToHardwareLoop(L, L0Used, L1Used);
367 /// \brief Return the latch block if it's one of the exiting blocks. Otherwise,
368 /// return the exiting block. Return 'null' when multiple exiting blocks are
370 static MachineBasicBlock* getExitingBlock(MachineLoop *L) {
371 if (MachineBasicBlock *Latch = L->getLoopLatch()) {
372 if (L->isLoopExiting(Latch))
375 return L->getExitingBlock();
380 bool HexagonHardwareLoops::findInductionRegister(MachineLoop *L,
385 MachineBasicBlock *Header = L->getHeader();
386 MachineBasicBlock *Preheader = L->getLoopPreheader();
387 MachineBasicBlock *Latch = L->getLoopLatch();
388 MachineBasicBlock *ExitingBlock = getExitingBlock(L);
389 if (!Header || !Preheader || !Latch || !ExitingBlock)
392 // This pair represents an induction register together with an immediate
393 // value that will be added to it in each loop iteration.
394 typedef std::pair<unsigned,int64_t> RegisterBump;
396 // Mapping: R.next -> (R, bump), where R, R.next and bump are derived
397 // from an induction operation
399 // where bump is an immediate value.
400 typedef std::map<unsigned,RegisterBump> InductionMap;
404 typedef MachineBasicBlock::instr_iterator instr_iterator;
405 for (instr_iterator I = Header->instr_begin(), E = Header->instr_end();
406 I != E && I->isPHI(); ++I) {
407 MachineInstr *Phi = &*I;
409 // Have a PHI instruction. Get the operand that corresponds to the
410 // latch block, and see if is a result of an addition of form "reg+imm",
411 // where the "reg" is defined by the PHI node we are looking at.
412 for (unsigned i = 1, n = Phi->getNumOperands(); i < n; i += 2) {
413 if (Phi->getOperand(i+1).getMBB() != Latch)
416 unsigned PhiOpReg = Phi->getOperand(i).getReg();
417 MachineInstr *DI = MRI->getVRegDef(PhiOpReg);
418 unsigned UpdOpc = DI->getOpcode();
419 bool isAdd = (UpdOpc == Hexagon::A2_addi || UpdOpc == Hexagon::A2_addp);
422 // If the register operand to the add is the PHI we're looking at, this
423 // meets the induction pattern.
424 unsigned IndReg = DI->getOperand(1).getReg();
425 MachineOperand &Opnd2 = DI->getOperand(2);
427 if (MRI->getVRegDef(IndReg) == Phi && checkForImmediate(Opnd2, V)) {
428 unsigned UpdReg = DI->getOperand(0).getReg();
429 IndMap.insert(std::make_pair(UpdReg, std::make_pair(IndReg, V)));
435 SmallVector<MachineOperand,2> Cond;
436 MachineBasicBlock *TB = nullptr, *FB = nullptr;
437 bool NotAnalyzed = TII->AnalyzeBranch(*ExitingBlock, TB, FB, Cond, false);
441 unsigned PredR, PredPos, PredRegFlags;
442 if (!TII->getPredReg(Cond, PredR, PredPos, PredRegFlags))
445 MachineInstr *PredI = MRI->getVRegDef(PredR);
446 if (!PredI->isCompare())
449 unsigned CmpReg1 = 0, CmpReg2 = 0;
450 int CmpImm = 0, CmpMask = 0;
451 bool CmpAnalyzed = TII->analyzeCompare(PredI, CmpReg1, CmpReg2,
453 // Fail if the compare was not analyzed, or it's not comparing a register
454 // with an immediate value. Not checking the mask here, since we handle
455 // the individual compare opcodes (including A4_cmpb*) later on.
459 // Exactly one of the input registers to the comparison should be among
460 // the induction registers.
461 InductionMap::iterator IndMapEnd = IndMap.end();
462 InductionMap::iterator F = IndMapEnd;
464 InductionMap::iterator F1 = IndMap.find(CmpReg1);
469 InductionMap::iterator F2 = IndMap.find(CmpReg2);
470 if (F2 != IndMapEnd) {
479 Reg = F->second.first;
480 IVBump = F->second.second;
481 IVOp = MRI->getVRegDef(F->first);
485 // Return the comparison kind for the specified opcode.
486 HexagonHardwareLoops::Comparison::Kind
487 HexagonHardwareLoops::getComparisonKind(unsigned CondOpc,
488 MachineOperand *InitialValue,
489 const MachineOperand *EndValue,
490 int64_t IVBump) const {
491 Comparison::Kind Cmp = (Comparison::Kind)0;
493 case Hexagon::C2_cmpeqi:
494 case Hexagon::C2_cmpeq:
495 case Hexagon::C2_cmpeqp:
496 Cmp = Comparison::EQ;
498 case Hexagon::C4_cmpneq:
499 case Hexagon::C4_cmpneqi:
500 Cmp = Comparison::NE;
502 case Hexagon::C4_cmplte:
503 Cmp = Comparison::LEs;
505 case Hexagon::C4_cmplteu:
506 Cmp = Comparison::LEu;
508 case Hexagon::C2_cmpgtui:
509 case Hexagon::C2_cmpgtu:
510 case Hexagon::C2_cmpgtup:
511 Cmp = Comparison::GTu;
513 case Hexagon::C2_cmpgti:
514 case Hexagon::C2_cmpgt:
515 case Hexagon::C2_cmpgtp:
516 Cmp = Comparison::GTs;
519 return (Comparison::Kind)0;
524 /// \brief Analyze the statements in a loop to determine if the loop has
525 /// a computable trip count and, if so, return a value that represents
526 /// the trip count expression.
528 /// This function iterates over the phi nodes in the loop to check for
529 /// induction variable patterns that are used in the calculation for
530 /// the number of time the loop is executed.
531 CountValue *HexagonHardwareLoops::getLoopTripCount(MachineLoop *L,
532 SmallVectorImpl<MachineInstr *> &OldInsts) {
533 MachineBasicBlock *TopMBB = L->getTopBlock();
534 MachineBasicBlock::pred_iterator PI = TopMBB->pred_begin();
535 assert(PI != TopMBB->pred_end() &&
536 "Loop must have more than one incoming edge!");
537 MachineBasicBlock *Backedge = *PI++;
538 if (PI == TopMBB->pred_end()) // dead loop?
540 MachineBasicBlock *Incoming = *PI++;
541 if (PI != TopMBB->pred_end()) // multiple backedges?
544 // Make sure there is one incoming and one backedge and determine which
546 if (L->contains(Incoming)) {
547 if (L->contains(Backedge))
549 std::swap(Incoming, Backedge);
550 } else if (!L->contains(Backedge))
553 // Look for the cmp instruction to determine if we can get a useful trip
554 // count. The trip count can be either a register or an immediate. The
555 // location of the value depends upon the type (reg or imm).
556 MachineBasicBlock *ExitingBlock = getExitingBlock(L);
563 bool FoundIV = findInductionRegister(L, IVReg, IVBump, IVOp);
567 MachineBasicBlock *Preheader = L->getLoopPreheader();
569 MachineOperand *InitialValue = nullptr;
570 MachineInstr *IV_Phi = MRI->getVRegDef(IVReg);
571 MachineBasicBlock *Latch = L->getLoopLatch();
572 for (unsigned i = 1, n = IV_Phi->getNumOperands(); i < n; i += 2) {
573 MachineBasicBlock *MBB = IV_Phi->getOperand(i+1).getMBB();
574 if (MBB == Preheader)
575 InitialValue = &IV_Phi->getOperand(i);
576 else if (MBB == Latch)
577 IVReg = IV_Phi->getOperand(i).getReg(); // Want IV reg after bump.
582 SmallVector<MachineOperand,2> Cond;
583 MachineBasicBlock *TB = nullptr, *FB = nullptr;
584 bool NotAnalyzed = TII->AnalyzeBranch(*ExitingBlock, TB, FB, Cond, false);
588 MachineBasicBlock *Header = L->getHeader();
589 // TB must be non-null. If FB is also non-null, one of them must be
590 // the header. Otherwise, branch to TB could be exiting the loop, and
591 // the fall through can go to the header.
592 assert (TB && "Exit block without a branch?");
593 if (ExitingBlock != Latch && (TB == Latch || FB == Latch)) {
594 MachineBasicBlock *LTB = 0, *LFB = 0;
595 SmallVector<MachineOperand,2> LCond;
596 bool NotAnalyzed = TII->AnalyzeBranch(*Latch, LTB, LFB, LCond, false);
600 TB = (LTB == Header) ? LTB : LFB;
602 FB = (LTB == Header) ? LTB: LFB;
604 assert ((!FB || TB == Header || FB == Header) && "Branches not to header?");
605 if (!TB || (FB && TB != Header && FB != Header))
608 // Branches of form "if (!P) ..." cause HexagonInstrInfo::AnalyzeBranch
609 // to put imm(0), followed by P in the vector Cond.
610 // If TB is not the header, it means that the "not-taken" path must lead
612 bool Negated = TII->predOpcodeHasNot(Cond) ^ (TB != Header);
613 unsigned PredReg, PredPos, PredRegFlags;
614 if (!TII->getPredReg(Cond, PredReg, PredPos, PredRegFlags))
616 MachineInstr *CondI = MRI->getVRegDef(PredReg);
617 unsigned CondOpc = CondI->getOpcode();
619 unsigned CmpReg1 = 0, CmpReg2 = 0;
620 int Mask = 0, ImmValue = 0;
621 bool AnalyzedCmp = TII->analyzeCompare(CondI, CmpReg1, CmpReg2,
626 // The comparison operator type determines how we compute the loop
628 OldInsts.push_back(CondI);
629 OldInsts.push_back(IVOp);
631 // Sadly, the following code gets information based on the position
632 // of the operands in the compare instruction. This has to be done
633 // this way, because the comparisons check for a specific relationship
634 // between the operands (e.g. is-less-than), rather than to find out
635 // what relationship the operands are in (as on PPC).
636 Comparison::Kind Cmp;
637 bool isSwapped = false;
638 const MachineOperand &Op1 = CondI->getOperand(1);
639 const MachineOperand &Op2 = CondI->getOperand(2);
640 const MachineOperand *EndValue = nullptr;
643 if (Op2.isImm() || Op1.getReg() == IVReg)
654 Cmp = getComparisonKind(CondOpc, InitialValue, EndValue, IVBump);
658 Cmp = Comparison::getNegatedComparison(Cmp);
660 Cmp = Comparison::getSwappedComparison(Cmp);
662 if (InitialValue->isReg()) {
663 unsigned R = InitialValue->getReg();
664 MachineBasicBlock *DefBB = MRI->getVRegDef(R)->getParent();
665 if (!MDT->properlyDominates(DefBB, Header))
667 OldInsts.push_back(MRI->getVRegDef(R));
669 if (EndValue->isReg()) {
670 unsigned R = EndValue->getReg();
671 MachineBasicBlock *DefBB = MRI->getVRegDef(R)->getParent();
672 if (!MDT->properlyDominates(DefBB, Header))
674 OldInsts.push_back(MRI->getVRegDef(R));
677 return computeCount(L, InitialValue, EndValue, IVReg, IVBump, Cmp);
680 /// \brief Helper function that returns the expression that represents the
681 /// number of times a loop iterates. The function takes the operands that
682 /// represent the loop start value, loop end value, and induction value.
683 /// Based upon these operands, the function attempts to compute the trip count.
684 CountValue *HexagonHardwareLoops::computeCount(MachineLoop *Loop,
685 const MachineOperand *Start,
686 const MachineOperand *End,
689 Comparison::Kind Cmp) const {
690 // Cannot handle comparison EQ, i.e. while (A == B).
691 if (Cmp == Comparison::EQ)
694 // Check if either the start or end values are an assignment of an immediate.
695 // If so, use the immediate value rather than the register.
696 if (Start->isReg()) {
697 const MachineInstr *StartValInstr = MRI->getVRegDef(Start->getReg());
698 if (StartValInstr && (StartValInstr->getOpcode() == Hexagon::A2_tfrsi ||
699 StartValInstr->getOpcode() == Hexagon::A2_tfrpi))
700 Start = &StartValInstr->getOperand(1);
703 const MachineInstr *EndValInstr = MRI->getVRegDef(End->getReg());
704 if (EndValInstr && (EndValInstr->getOpcode() == Hexagon::A2_tfrsi ||
705 EndValInstr->getOpcode() == Hexagon::A2_tfrpi))
706 End = &EndValInstr->getOperand(1);
709 if (!Start->isReg() && !Start->isImm())
711 if (!End->isReg() && !End->isImm())
714 bool CmpLess = Cmp & Comparison::L;
715 bool CmpGreater = Cmp & Comparison::G;
716 bool CmpHasEqual = Cmp & Comparison::EQ;
718 // Avoid certain wrap-arounds. This doesn't detect all wrap-arounds.
719 if (CmpLess && IVBump < 0)
720 // Loop going while iv is "less" with the iv value going down. Must wrap.
723 if (CmpGreater && IVBump > 0)
724 // Loop going while iv is "greater" with the iv value going up. Must wrap.
727 // Phis that may feed into the loop.
728 LoopFeederMap LoopFeederPhi;
730 // Check if the inital value may be zero and can be decremented in the first
731 // iteration. If the value is zero, the endloop instruction will not decrement
732 // the loop counter, so we shoudn't generate a hardware loop in this case.
733 if (loopCountMayWrapOrUnderFlow(Start, End, Loop->getLoopPreheader(), Loop,
737 if (Start->isImm() && End->isImm()) {
738 // Both, start and end are immediates.
739 int64_t StartV = Start->getImm();
740 int64_t EndV = End->getImm();
741 int64_t Dist = EndV - StartV;
745 bool Exact = (Dist % IVBump) == 0;
747 if (Cmp == Comparison::NE) {
750 if ((Dist < 0) ^ (IVBump < 0))
754 // For comparisons that include the final value (i.e. include equality
755 // with the final value), we need to increase the distance by 1.
757 Dist = Dist > 0 ? Dist+1 : Dist-1;
759 // For the loop to iterate, CmpLess should imply Dist > 0. Similarly,
760 // CmpGreater should imply Dist < 0. These conditions could actually
761 // fail, for example, in unreachable code (which may still appear to be
762 // reachable in the CFG).
763 if ((CmpLess && Dist < 0) || (CmpGreater && Dist > 0))
766 // "Normalized" distance, i.e. with the bump set to +-1.
767 int64_t Dist1 = (IVBump > 0) ? (Dist + (IVBump - 1)) / IVBump
768 : (-Dist + (-IVBump - 1)) / (-IVBump);
769 assert (Dist1 > 0 && "Fishy thing. Both operands have the same sign.");
771 uint64_t Count = Dist1;
773 if (Count > 0xFFFFFFFFULL)
776 return new CountValue(CountValue::CV_Immediate, Count);
779 // A general case: Start and End are some values, but the actual
780 // iteration count may not be available. If it is not, insert
781 // a computation of it into the preheader.
783 // If the induction variable bump is not a power of 2, quit.
784 // Othwerise we'd need a general integer division.
785 if (!isPowerOf2_64(std::abs(IVBump)))
788 MachineBasicBlock *PH = Loop->getLoopPreheader();
789 assert (PH && "Should have a preheader by now");
790 MachineBasicBlock::iterator InsertPos = PH->getFirstTerminator();
792 if (InsertPos != PH->end())
793 DL = InsertPos->getDebugLoc();
795 // If Start is an immediate and End is a register, the trip count
796 // will be "reg - imm". Hexagon's "subtract immediate" instruction
797 // is actually "reg + -imm".
799 // If the loop IV is going downwards, i.e. if the bump is negative,
800 // then the iteration count (computed as End-Start) will need to be
801 // negated. To avoid the negation, just swap Start and End.
803 std::swap(Start, End);
806 // Cmp may now have a wrong direction, e.g. LEs may now be GEs.
807 // Signedness, and "including equality" are preserved.
809 bool RegToImm = Start->isReg() && End->isImm(); // for (reg..imm)
810 bool RegToReg = Start->isReg() && End->isReg(); // for (reg..reg)
812 int64_t StartV = 0, EndV = 0;
814 StartV = Start->getImm();
816 EndV = End->getImm();
819 // To compute the iteration count, we would need this computation:
820 // Count = (End - Start + (IVBump-1)) / IVBump
821 // or, when CmpHasEqual:
822 // Count = (End - Start + (IVBump-1)+1) / IVBump
823 // The "IVBump-1" part is the adjustment (AdjV). We can avoid
824 // generating an instruction specifically to add it if we can adjust
825 // the immediate values for Start or End.
828 // Need to add 1 to the total iteration count.
831 else if (End->isImm())
837 if (Cmp != Comparison::NE) {
839 StartV -= (IVBump-1);
840 else if (End->isImm())
846 unsigned R = 0, SR = 0;
847 if (Start->isReg()) {
849 SR = Start->getSubReg();
852 SR = End->getSubReg();
854 const TargetRegisterClass *RC = MRI->getRegClass(R);
855 // Hardware loops cannot handle 64-bit registers. If it's a double
856 // register, it has to have a subregister.
857 if (!SR && RC == &Hexagon::DoubleRegsRegClass)
859 const TargetRegisterClass *IntRC = &Hexagon::IntRegsRegClass;
861 // Compute DistR (register with the distance between Start and End).
862 unsigned DistR, DistSR;
864 // Avoid special case, where the start value is an imm(0).
865 if (Start->isImm() && StartV == 0) {
866 DistR = End->getReg();
867 DistSR = End->getSubReg();
869 const MCInstrDesc &SubD = RegToReg ? TII->get(Hexagon::A2_sub) :
870 (RegToImm ? TII->get(Hexagon::A2_subri) :
871 TII->get(Hexagon::A2_addi));
872 if (RegToReg || RegToImm) {
873 unsigned SubR = MRI->createVirtualRegister(IntRC);
874 MachineInstrBuilder SubIB =
875 BuildMI(*PH, InsertPos, DL, SubD, SubR);
878 SubIB.addReg(End->getReg(), 0, End->getSubReg())
879 .addReg(Start->getReg(), 0, Start->getSubReg());
882 .addReg(Start->getReg(), 0, Start->getSubReg());
885 // If the loop has been unrolled, we should use the original loop count
886 // instead of recalculating the value. This will avoid additional
887 // 'Add' instruction.
888 const MachineInstr *EndValInstr = MRI->getVRegDef(End->getReg());
889 if (EndValInstr->getOpcode() == Hexagon::A2_addi &&
890 EndValInstr->getOperand(2).getImm() == StartV) {
891 DistR = EndValInstr->getOperand(1).getReg();
893 unsigned SubR = MRI->createVirtualRegister(IntRC);
894 MachineInstrBuilder SubIB =
895 BuildMI(*PH, InsertPos, DL, SubD, SubR);
896 SubIB.addReg(End->getReg(), 0, End->getSubReg())
904 // From DistR, compute AdjR (register with the adjusted distance).
905 unsigned AdjR, AdjSR;
911 // Generate CountR = ADD DistR, AdjVal
912 unsigned AddR = MRI->createVirtualRegister(IntRC);
913 MCInstrDesc const &AddD = TII->get(Hexagon::A2_addi);
914 BuildMI(*PH, InsertPos, DL, AddD, AddR)
915 .addReg(DistR, 0, DistSR)
922 // From AdjR, compute CountR (register with the final count).
923 unsigned CountR, CountSR;
929 // The IV bump is a power of two. Log_2(IV bump) is the shift amount.
930 unsigned Shift = Log2_32(IVBump);
932 // Generate NormR = LSR DistR, Shift.
933 unsigned LsrR = MRI->createVirtualRegister(IntRC);
934 const MCInstrDesc &LsrD = TII->get(Hexagon::S2_lsr_i_r);
935 BuildMI(*PH, InsertPos, DL, LsrD, LsrR)
936 .addReg(AdjR, 0, AdjSR)
943 return new CountValue(CountValue::CV_Register, CountR, CountSR);
946 /// \brief Return true if the operation is invalid within hardware loop.
947 bool HexagonHardwareLoops::isInvalidLoopOperation(const MachineInstr *MI,
948 bool IsInnerHWLoop) const {
950 // Call is not allowed because the callee may use a hardware loop except for
951 // the case when the call never returns.
952 if (MI->getDesc().isCall() && MI->getOpcode() != Hexagon::CALLv3nr)
955 // Check if the instruction defines a hardware loop register.
956 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
957 const MachineOperand &MO = MI->getOperand(i);
958 if (!MO.isReg() || !MO.isDef())
960 unsigned R = MO.getReg();
961 if (IsInnerHWLoop && (R == Hexagon::LC0 || R == Hexagon::SA0 ||
962 R == Hexagon::LC1 || R == Hexagon::SA1))
964 if (!IsInnerHWLoop && (R == Hexagon::LC1 || R == Hexagon::SA1))
970 /// \brief Return true if the loop contains an instruction that inhibits
971 /// the use of the hardware loop instruction.
972 bool HexagonHardwareLoops::containsInvalidInstruction(MachineLoop *L,
973 bool IsInnerHWLoop) const {
974 const std::vector<MachineBasicBlock *> &Blocks = L->getBlocks();
975 DEBUG(dbgs() << "\nhw_loop head, BB#" << Blocks[0]->getNumber(););
976 for (unsigned i = 0, e = Blocks.size(); i != e; ++i) {
977 MachineBasicBlock *MBB = Blocks[i];
978 for (MachineBasicBlock::iterator
979 MII = MBB->begin(), E = MBB->end(); MII != E; ++MII) {
980 const MachineInstr *MI = &*MII;
981 if (isInvalidLoopOperation(MI, IsInnerHWLoop)) {
982 DEBUG(dbgs()<< "\nCannot convert to hw_loop due to:"; MI->dump(););
990 /// \brief Returns true if the instruction is dead. This was essentially
991 /// copied from DeadMachineInstructionElim::isDead, but with special cases
992 /// for inline asm, physical registers and instructions with side effects
994 bool HexagonHardwareLoops::isDead(const MachineInstr *MI,
995 SmallVectorImpl<MachineInstr *> &DeadPhis) const {
996 // Examine each operand.
997 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
998 const MachineOperand &MO = MI->getOperand(i);
999 if (!MO.isReg() || !MO.isDef())
1002 unsigned Reg = MO.getReg();
1003 if (MRI->use_nodbg_empty(Reg))
1006 typedef MachineRegisterInfo::use_nodbg_iterator use_nodbg_iterator;
1008 // This instruction has users, but if the only user is the phi node for the
1009 // parent block, and the only use of that phi node is this instruction, then
1010 // this instruction is dead: both it (and the phi node) can be removed.
1011 use_nodbg_iterator I = MRI->use_nodbg_begin(Reg);
1012 use_nodbg_iterator End = MRI->use_nodbg_end();
1013 if (std::next(I) != End || !I->getParent()->isPHI())
1016 MachineInstr *OnePhi = I->getParent();
1017 for (unsigned j = 0, f = OnePhi->getNumOperands(); j != f; ++j) {
1018 const MachineOperand &OPO = OnePhi->getOperand(j);
1019 if (!OPO.isReg() || !OPO.isDef())
1022 unsigned OPReg = OPO.getReg();
1023 use_nodbg_iterator nextJ;
1024 for (use_nodbg_iterator J = MRI->use_nodbg_begin(OPReg);
1025 J != End; J = nextJ) {
1026 nextJ = std::next(J);
1027 MachineOperand &Use = *J;
1028 MachineInstr *UseMI = Use.getParent();
1030 // If the phi node has a user that is not MI, bail.
1035 DeadPhis.push_back(OnePhi);
1038 // If there are no defs with uses, the instruction is dead.
1042 void HexagonHardwareLoops::removeIfDead(MachineInstr *MI) {
1043 // This procedure was essentially copied from DeadMachineInstructionElim.
1045 SmallVector<MachineInstr*, 1> DeadPhis;
1046 if (isDead(MI, DeadPhis)) {
1047 DEBUG(dbgs() << "HW looping will remove: " << *MI);
1049 // It is possible that some DBG_VALUE instructions refer to this
1050 // instruction. Examine each def operand for such references;
1051 // if found, mark the DBG_VALUE as undef (but don't delete it).
1052 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
1053 const MachineOperand &MO = MI->getOperand(i);
1054 if (!MO.isReg() || !MO.isDef())
1056 unsigned Reg = MO.getReg();
1057 MachineRegisterInfo::use_iterator nextI;
1058 for (MachineRegisterInfo::use_iterator I = MRI->use_begin(Reg),
1059 E = MRI->use_end(); I != E; I = nextI) {
1060 nextI = std::next(I); // I is invalidated by the setReg
1061 MachineOperand &Use = *I;
1062 MachineInstr *UseMI = I->getParent();
1066 UseMI->getOperand(0).setReg(0U);
1070 MI->eraseFromParent();
1071 for (unsigned i = 0; i < DeadPhis.size(); ++i)
1072 DeadPhis[i]->eraseFromParent();
1076 /// \brief Check if the loop is a candidate for converting to a hardware
1077 /// loop. If so, then perform the transformation.
1079 /// This function works on innermost loops first. A loop can be converted
1080 /// if it is a counting loop; either a register value or an immediate.
1082 /// The code makes several assumptions about the representation of the loop
1084 bool HexagonHardwareLoops::convertToHardwareLoop(MachineLoop *L,
1087 // This is just for sanity.
1088 assert(L->getHeader() && "Loop without a header?");
1090 bool Changed = false;
1091 bool L0Used = false;
1092 bool L1Used = false;
1094 // Process nested loops first.
1095 for (MachineLoop::iterator I = L->begin(), E = L->end(); I != E; ++I) {
1096 Changed |= convertToHardwareLoop(*I, RecL0used, RecL1used);
1097 L0Used |= RecL0used;
1098 L1Used |= RecL1used;
1101 // If a nested loop has been converted, then we can't convert this loop.
1102 if (Changed && L0Used && L1Used)
1109 // Flag used to track loopN instruction:
1110 // 1 - Hardware loop is being generated for the inner most loop.
1111 // 0 - Hardware loop is being generated for the outer loop.
1112 unsigned IsInnerHWLoop = 1;
1115 LOOP_i = Hexagon::J2_loop1i;
1116 LOOP_r = Hexagon::J2_loop1r;
1117 ENDLOOP = Hexagon::ENDLOOP1;
1120 LOOP_i = Hexagon::J2_loop0i;
1121 LOOP_r = Hexagon::J2_loop0r;
1122 ENDLOOP = Hexagon::ENDLOOP0;
1126 // Stop trying after reaching the limit (if any).
1127 int Limit = HWLoopLimit;
1129 if (Counter >= HWLoopLimit)
1135 // Does the loop contain any invalid instructions?
1136 if (containsInvalidInstruction(L, IsInnerHWLoop))
1139 MachineBasicBlock *LastMBB = getExitingBlock(L);
1140 // Don't generate hw loop if the loop has more than one exit.
1144 MachineBasicBlock::iterator LastI = LastMBB->getFirstTerminator();
1145 if (LastI == LastMBB->end())
1148 // Is the induction variable bump feeding the latch condition?
1149 if (!fixupInductionVariable(L))
1152 // Ensure the loop has a preheader: the loop instruction will be
1154 MachineBasicBlock *Preheader = L->getLoopPreheader();
1156 Preheader = createPreheaderForLoop(L);
1161 MachineBasicBlock::iterator InsertPos = Preheader->getFirstTerminator();
1163 SmallVector<MachineInstr*, 2> OldInsts;
1164 // Are we able to determine the trip count for the loop?
1165 CountValue *TripCount = getLoopTripCount(L, OldInsts);
1169 // Is the trip count available in the preheader?
1170 if (TripCount->isReg()) {
1171 // There will be a use of the register inserted into the preheader,
1172 // so make sure that the register is actually defined at that point.
1173 MachineInstr *TCDef = MRI->getVRegDef(TripCount->getReg());
1174 MachineBasicBlock *BBDef = TCDef->getParent();
1175 if (!MDT->dominates(BBDef, Preheader))
1179 // Determine the loop start.
1180 MachineBasicBlock *TopBlock = L->getTopBlock();
1181 MachineBasicBlock *ExitingBlock = getExitingBlock(L);
1182 MachineBasicBlock *LoopStart = 0;
1183 if (ExitingBlock != L->getLoopLatch()) {
1184 MachineBasicBlock *TB = 0, *FB = 0;
1185 SmallVector<MachineOperand, 2> Cond;
1187 if (TII->AnalyzeBranch(*ExitingBlock, TB, FB, Cond, false))
1190 if (L->contains(TB))
1192 else if (L->contains(FB))
1198 LoopStart = TopBlock;
1200 // Convert the loop to a hardware loop.
1201 DEBUG(dbgs() << "Change to hardware loop at "; L->dump());
1203 if (InsertPos != Preheader->end())
1204 DL = InsertPos->getDebugLoc();
1206 if (TripCount->isReg()) {
1207 // Create a copy of the loop count register.
1208 unsigned CountReg = MRI->createVirtualRegister(&Hexagon::IntRegsRegClass);
1209 BuildMI(*Preheader, InsertPos, DL, TII->get(TargetOpcode::COPY), CountReg)
1210 .addReg(TripCount->getReg(), 0, TripCount->getSubReg());
1211 // Add the Loop instruction to the beginning of the loop.
1212 BuildMI(*Preheader, InsertPos, DL, TII->get(LOOP_r)).addMBB(LoopStart)
1215 assert(TripCount->isImm() && "Expecting immediate value for trip count");
1216 // Add the Loop immediate instruction to the beginning of the loop,
1217 // if the immediate fits in the instructions. Otherwise, we need to
1218 // create a new virtual register.
1219 int64_t CountImm = TripCount->getImm();
1220 if (!TII->isValidOffset(LOOP_i, CountImm)) {
1221 unsigned CountReg = MRI->createVirtualRegister(&Hexagon::IntRegsRegClass);
1222 BuildMI(*Preheader, InsertPos, DL, TII->get(Hexagon::A2_tfrsi), CountReg)
1224 BuildMI(*Preheader, InsertPos, DL, TII->get(LOOP_r))
1225 .addMBB(LoopStart).addReg(CountReg);
1227 BuildMI(*Preheader, InsertPos, DL, TII->get(LOOP_i))
1228 .addMBB(LoopStart).addImm(CountImm);
1231 // Make sure the loop start always has a reference in the CFG. We need
1232 // to create a BlockAddress operand to get this mechanism to work both the
1233 // MachineBasicBlock and BasicBlock objects need the flag set.
1234 LoopStart->setHasAddressTaken();
1235 // This line is needed to set the hasAddressTaken flag on the BasicBlock
1237 BlockAddress::get(const_cast<BasicBlock *>(LoopStart->getBasicBlock()));
1239 // Replace the loop branch with an endloop instruction.
1240 DebugLoc LastIDL = LastI->getDebugLoc();
1241 BuildMI(*LastMBB, LastI, LastIDL, TII->get(ENDLOOP)).addMBB(LoopStart);
1243 // The loop ends with either:
1244 // - a conditional branch followed by an unconditional branch, or
1245 // - a conditional branch to the loop start.
1246 if (LastI->getOpcode() == Hexagon::J2_jumpt ||
1247 LastI->getOpcode() == Hexagon::J2_jumpf) {
1248 // Delete one and change/add an uncond. branch to out of the loop.
1249 MachineBasicBlock *BranchTarget = LastI->getOperand(1).getMBB();
1250 LastI = LastMBB->erase(LastI);
1251 if (!L->contains(BranchTarget)) {
1252 if (LastI != LastMBB->end())
1253 LastI = LastMBB->erase(LastI);
1254 SmallVector<MachineOperand, 0> Cond;
1255 TII->InsertBranch(*LastMBB, BranchTarget, nullptr, Cond, LastIDL);
1258 // Conditional branch to loop start; just delete it.
1259 LastMBB->erase(LastI);
1263 // The induction operation and the comparison may now be
1264 // unneeded. If these are unneeded, then remove them.
1265 for (unsigned i = 0; i < OldInsts.size(); ++i)
1266 removeIfDead(OldInsts[i]);
1270 // Set RecL1used and RecL0used only after hardware loop has been
1271 // successfully generated. Doing it earlier can cause wrong loop instruction
1273 if (L0Used) // Loop0 was already used. So, the correct loop must be loop1.
1281 bool HexagonHardwareLoops::orderBumpCompare(MachineInstr *BumpI,
1282 MachineInstr *CmpI) {
1283 assert (BumpI != CmpI && "Bump and compare in the same instruction?");
1285 MachineBasicBlock *BB = BumpI->getParent();
1286 if (CmpI->getParent() != BB)
1289 typedef MachineBasicBlock::instr_iterator instr_iterator;
1290 // Check if things are in order to begin with.
1291 for (instr_iterator I = BumpI, E = BB->instr_end(); I != E; ++I)
1296 unsigned PredR = CmpI->getOperand(0).getReg();
1297 bool FoundBump = false;
1298 instr_iterator CmpIt = CmpI, NextIt = std::next(CmpIt);
1299 for (instr_iterator I = NextIt, E = BB->instr_end(); I != E; ++I) {
1300 MachineInstr *In = &*I;
1301 for (unsigned i = 0, n = In->getNumOperands(); i < n; ++i) {
1302 MachineOperand &MO = In->getOperand(i);
1303 if (MO.isReg() && MO.isUse()) {
1304 if (MO.getReg() == PredR) // Found an intervening use of PredR.
1310 instr_iterator After = BumpI;
1311 instr_iterator From = CmpI;
1312 BB->splice(std::next(After), BB, From);
1317 assert (FoundBump && "Cannot determine instruction order");
1321 /// This function is required to break recursion. Visiting phis in a loop may
1322 /// result in recursion during compilation. We break the recursion by making
1323 /// sure that we visit a MachineOperand and its definition in a
1324 /// MachineInstruction only once. If we attempt to visit more than once, then
1325 /// there is recursion, and will return false.
1326 bool HexagonHardwareLoops::isLoopFeeder(MachineLoop *L, MachineBasicBlock *A,
1328 const MachineOperand *MO,
1329 LoopFeederMap &LoopFeederPhi) const {
1330 if (LoopFeederPhi.find(MO->getReg()) == LoopFeederPhi.end()) {
1331 const std::vector<MachineBasicBlock *> &Blocks = L->getBlocks();
1332 DEBUG(dbgs() << "\nhw_loop head, BB#" << Blocks[0]->getNumber(););
1333 // Ignore all BBs that form Loop.
1334 for (unsigned i = 0, e = Blocks.size(); i != e; ++i) {
1335 MachineBasicBlock *MBB = Blocks[i];
1339 MachineInstr *Def = MRI->getVRegDef(MO->getReg());
1340 LoopFeederPhi.insert(std::make_pair(MO->getReg(), Def));
1343 // Already visited node.
1347 /// Return true if a Phi may generate a value that can underflow.
1348 /// This function calls loopCountMayWrapOrUnderFlow for each Phi operand.
1349 bool HexagonHardwareLoops::phiMayWrapOrUnderflow(
1350 MachineInstr *Phi, const MachineOperand *EndVal, MachineBasicBlock *MBB,
1351 MachineLoop *L, LoopFeederMap &LoopFeederPhi) const {
1352 assert(Phi->isPHI() && "Expecting a Phi.");
1353 // Walk through each Phi, and its used operands. Make sure that
1354 // if there is recursion in Phi, we won't generate hardware loops.
1355 for (int i = 1, n = Phi->getNumOperands(); i < n; i += 2)
1356 if (isLoopFeeder(L, MBB, Phi, &(Phi->getOperand(i)), LoopFeederPhi))
1357 if (loopCountMayWrapOrUnderFlow(&(Phi->getOperand(i)), EndVal,
1358 Phi->getParent(), L, LoopFeederPhi))
1363 /// Return true if the induction variable can underflow in the first iteration.
1364 /// An example, is an initial unsigned value that is 0 and is decrement in the
1365 /// first itertion of a do-while loop. In this case, we cannot generate a
1366 /// hardware loop because the endloop instruction does not decrement the loop
1367 /// counter if it is <= 1. We only need to perform this analysis if the
1368 /// initial value is a register.
1370 /// This function assumes the initial value may underfow unless proven
1371 /// otherwise. If the type is signed, then we don't care because signed
1372 /// underflow is undefined. We attempt to prove the initial value is not
1373 /// zero by perfoming a crude analysis of the loop counter. This function
1374 /// checks if the initial value is used in any comparison prior to the loop
1375 /// and, if so, assumes the comparison is a range check. This is inexact,
1376 /// but will catch the simple cases.
1377 bool HexagonHardwareLoops::loopCountMayWrapOrUnderFlow(
1378 const MachineOperand *InitVal, const MachineOperand *EndVal,
1379 MachineBasicBlock *MBB, MachineLoop *L,
1380 LoopFeederMap &LoopFeederPhi) const {
1381 // Only check register values since they are unknown.
1382 if (!InitVal->isReg())
1385 if (!EndVal->isImm())
1388 // A register value that is assigned an immediate is a known value, and it
1389 // won't underflow in the first iteration.
1391 if (checkForImmediate(*InitVal, Imm))
1392 return (EndVal->getImm() == Imm);
1394 unsigned Reg = InitVal->getReg();
1396 // We don't know the value of a physical register.
1397 if (!TargetRegisterInfo::isVirtualRegister(Reg))
1400 MachineInstr *Def = MRI->getVRegDef(Reg);
1404 // If the initial value is a Phi or copy and the operands may not underflow,
1405 // then the definition cannot be underflow either.
1406 if (Def->isPHI() && !phiMayWrapOrUnderflow(Def, EndVal, Def->getParent(),
1409 if (Def->isCopy() && !loopCountMayWrapOrUnderFlow(&(Def->getOperand(1)),
1410 EndVal, Def->getParent(),
1414 // Iterate over the uses of the initial value. If the initial value is used
1415 // in a compare, then we assume this is a range check that ensures the loop
1416 // doesn't underflow. This is not an exact test and should be improved.
1417 for (MachineRegisterInfo::use_instr_nodbg_iterator I = MRI->use_instr_nodbg_begin(Reg),
1418 E = MRI->use_instr_nodbg_end(); I != E; ++I) {
1419 MachineInstr *MI = &*I;
1420 unsigned CmpReg1 = 0, CmpReg2 = 0;
1421 int CmpMask = 0, CmpValue = 0;
1423 if (!TII->analyzeCompare(MI, CmpReg1, CmpReg2, CmpMask, CmpValue))
1426 MachineBasicBlock *TBB = 0, *FBB = 0;
1427 SmallVector<MachineOperand, 2> Cond;
1428 if (TII->AnalyzeBranch(*MI->getParent(), TBB, FBB, Cond, false))
1431 Comparison::Kind Cmp = getComparisonKind(MI->getOpcode(), 0, 0, 0);
1434 if (TII->predOpcodeHasNot(Cond) ^ (TBB != MBB))
1435 Cmp = Comparison::getNegatedComparison(Cmp);
1436 if (CmpReg2 != 0 && CmpReg2 == Reg)
1437 Cmp = Comparison::getSwappedComparison(Cmp);
1439 // Signed underflow is undefined.
1440 if (Comparison::isSigned(Cmp))
1443 // Check if there is a comparison of the inital value. If the initial value
1444 // is greater than or not equal to another value, then assume this is a
1446 if ((Cmp & Comparison::G) || Cmp == Comparison::NE)
1450 // OK - this is a hack that needs to be improved. We really need to analyze
1451 // the instructions performed on the initial value. This works on the simplest
1453 if (!Def->isCopy() && !Def->isPHI())
1459 bool HexagonHardwareLoops::checkForImmediate(const MachineOperand &MO,
1460 int64_t &Val) const {
1468 // MO is a register. Check whether it is defined as an immediate value,
1469 // and if so, get the value of it in TV. That value will then need to be
1470 // processed to handle potential subregisters in MO.
1473 unsigned R = MO.getReg();
1474 if (!TargetRegisterInfo::isVirtualRegister(R))
1476 MachineInstr *DI = MRI->getVRegDef(R);
1477 unsigned DOpc = DI->getOpcode();
1479 case TargetOpcode::COPY:
1480 case Hexagon::A2_tfrsi:
1481 case Hexagon::A2_tfrpi:
1482 case Hexagon::CONST32_Int_Real:
1483 case Hexagon::CONST64_Int_Real: {
1484 // Call recursively to avoid an extra check whether operand(1) is
1485 // indeed an immediate (it could be a global address, for example),
1486 // plus we can handle COPY at the same time.
1487 if (!checkForImmediate(DI->getOperand(1), TV))
1491 case Hexagon::A2_combineii:
1492 case Hexagon::A4_combineir:
1493 case Hexagon::A4_combineii:
1494 case Hexagon::A4_combineri:
1495 case Hexagon::A2_combinew: {
1496 const MachineOperand &S1 = DI->getOperand(1);
1497 const MachineOperand &S2 = DI->getOperand(2);
1499 if (!checkForImmediate(S1, V1) || !checkForImmediate(S2, V2))
1501 TV = V2 | (V1 << 32);
1504 case TargetOpcode::REG_SEQUENCE: {
1505 const MachineOperand &S1 = DI->getOperand(1);
1506 const MachineOperand &S3 = DI->getOperand(3);
1508 if (!checkForImmediate(S1, V1) || !checkForImmediate(S3, V3))
1510 unsigned Sub2 = DI->getOperand(2).getImm();
1511 unsigned Sub4 = DI->getOperand(4).getImm();
1512 if (Sub2 == Hexagon::subreg_loreg && Sub4 == Hexagon::subreg_hireg)
1513 TV = V1 | (V3 << 32);
1514 else if (Sub2 == Hexagon::subreg_hireg && Sub4 == Hexagon::subreg_loreg)
1515 TV = V3 | (V1 << 32);
1517 llvm_unreachable("Unexpected form of REG_SEQUENCE");
1525 // By now, we should have successfuly obtained the immediate value defining
1526 // the register referenced in MO. Handle a potential use of a subregister.
1527 switch (MO.getSubReg()) {
1528 case Hexagon::subreg_loreg:
1529 Val = TV & 0xFFFFFFFFULL;
1531 case Hexagon::subreg_hireg:
1532 Val = (TV >> 32) & 0xFFFFFFFFULL;
1541 void HexagonHardwareLoops::setImmediate(MachineOperand &MO, int64_t Val) {
1548 unsigned R = MO.getReg();
1549 MachineInstr *DI = MRI->getVRegDef(R);
1551 const TargetRegisterClass *RC = MRI->getRegClass(R);
1552 unsigned NewR = MRI->createVirtualRegister(RC);
1553 MachineBasicBlock &B = *DI->getParent();
1554 DebugLoc DL = DI->getDebugLoc();
1555 BuildMI(B, DI, DL, TII->get(DI->getOpcode()), NewR).addImm(Val);
1559 static bool isImmValidForOpcode(unsigned CmpOpc, int64_t Imm) {
1560 // These two instructions are not extendable.
1561 if (CmpOpc == Hexagon::A4_cmpbeqi)
1562 return isUInt<8>(Imm);
1563 if (CmpOpc == Hexagon::A4_cmpbgti)
1564 return isInt<8>(Imm);
1565 // The rest of the comparison-with-immediate instructions are extendable.
1569 bool HexagonHardwareLoops::fixupInductionVariable(MachineLoop *L) {
1570 MachineBasicBlock *Header = L->getHeader();
1571 MachineBasicBlock *Latch = L->getLoopLatch();
1572 MachineBasicBlock *ExitingBlock = getExitingBlock(L);
1574 if (!(Header && Latch && ExitingBlock))
1577 // These data structures follow the same concept as the corresponding
1578 // ones in findInductionRegister (where some comments are).
1579 typedef std::pair<unsigned,int64_t> RegisterBump;
1580 typedef std::pair<unsigned,RegisterBump> RegisterInduction;
1581 typedef std::set<RegisterInduction> RegisterInductionSet;
1583 // Register candidates for induction variables, with their associated bumps.
1584 RegisterInductionSet IndRegs;
1586 // Look for induction patterns:
1587 // vreg1 = PHI ..., [ latch, vreg2 ]
1588 // vreg2 = ADD vreg1, imm
1589 typedef MachineBasicBlock::instr_iterator instr_iterator;
1590 for (instr_iterator I = Header->instr_begin(), E = Header->instr_end();
1591 I != E && I->isPHI(); ++I) {
1592 MachineInstr *Phi = &*I;
1594 // Have a PHI instruction.
1595 for (unsigned i = 1, n = Phi->getNumOperands(); i < n; i += 2) {
1596 if (Phi->getOperand(i+1).getMBB() != Latch)
1599 unsigned PhiReg = Phi->getOperand(i).getReg();
1600 MachineInstr *DI = MRI->getVRegDef(PhiReg);
1601 unsigned UpdOpc = DI->getOpcode();
1602 bool isAdd = (UpdOpc == Hexagon::A2_addi || UpdOpc == Hexagon::A2_addp);
1605 // If the register operand to the add/sub is the PHI we are looking
1606 // at, this meets the induction pattern.
1607 unsigned IndReg = DI->getOperand(1).getReg();
1608 MachineOperand &Opnd2 = DI->getOperand(2);
1610 if (MRI->getVRegDef(IndReg) == Phi && checkForImmediate(Opnd2, V)) {
1611 unsigned UpdReg = DI->getOperand(0).getReg();
1612 IndRegs.insert(std::make_pair(UpdReg, std::make_pair(IndReg, V)));
1618 if (IndRegs.empty())
1621 MachineBasicBlock *TB = nullptr, *FB = nullptr;
1622 SmallVector<MachineOperand,2> Cond;
1623 // AnalyzeBranch returns true if it fails to analyze branch.
1624 bool NotAnalyzed = TII->AnalyzeBranch(*ExitingBlock, TB, FB, Cond, false);
1625 if (NotAnalyzed || Cond.empty())
1628 if (ExitingBlock != Latch && (TB == Latch || FB == Latch)) {
1629 MachineBasicBlock *LTB = 0, *LFB = 0;
1630 SmallVector<MachineOperand,2> LCond;
1631 bool NotAnalyzed = TII->AnalyzeBranch(*Latch, LTB, LFB, LCond, false);
1635 // Since latch is not the exiting block, the latch branch should be an
1636 // unconditional branch to the loop header.
1638 TB = (LTB == Header) ? LTB : LFB;
1640 FB = (LTB == Header) ? LTB : LFB;
1644 // The latch/exit block does not go back to the header.
1647 // FB is the header (i.e., uncond. jump to branch header)
1648 // In this case, the LoopBody -> TB should not be a back edge otherwise
1649 // it could result in an infinite loop after conversion to hw_loop.
1650 // This case can happen when the Latch has two jumps like this:
1651 // Jmp_c OuterLoopHeader <-- TB
1652 // Jmp InnerLoopHeader <-- FB
1653 if (MDT->dominates(TB, FB))
1657 // Expecting a predicate register as a condition. It won't be a hardware
1658 // predicate register at this point yet, just a vreg.
1659 // HexagonInstrInfo::AnalyzeBranch for negated branches inserts imm(0)
1660 // into Cond, followed by the predicate register. For non-negated branches
1661 // it's just the register.
1662 unsigned CSz = Cond.size();
1663 if (CSz != 1 && CSz != 2)
1666 if (!Cond[CSz-1].isReg())
1669 unsigned P = Cond[CSz-1].getReg();
1670 MachineInstr *PredDef = MRI->getVRegDef(P);
1672 if (!PredDef->isCompare())
1675 SmallSet<unsigned,2> CmpRegs;
1676 MachineOperand *CmpImmOp = nullptr;
1678 // Go over all operands to the compare and look for immediate and register
1679 // operands. Assume that if the compare has a single register use and a
1680 // single immediate operand, then the register is being compared with the
1682 for (unsigned i = 0, n = PredDef->getNumOperands(); i < n; ++i) {
1683 MachineOperand &MO = PredDef->getOperand(i);
1685 // Skip all implicit references. In one case there was:
1686 // %vreg140<def> = FCMPUGT32_rr %vreg138, %vreg139, %USR<imp-use>
1687 if (MO.isImplicit())
1690 if (!isImmediate(MO)) {
1691 CmpRegs.insert(MO.getReg());
1694 // Consider the register to be the "immediate" operand.
1699 } else if (MO.isImm()) {
1700 if (CmpImmOp) // A second immediate argument? Confusing. Bail out.
1706 if (CmpRegs.empty())
1709 // Check if the compared register follows the order we want. Fix if needed.
1710 for (RegisterInductionSet::iterator I = IndRegs.begin(), E = IndRegs.end();
1712 // This is a success. If the register used in the comparison is one that
1713 // we have identified as a bumped (updated) induction register, there is
1715 if (CmpRegs.count(I->first))
1718 // Otherwise, if the register being compared comes out of a PHI node,
1719 // and has been recognized as following the induction pattern, and is
1720 // compared against an immediate, we can fix it.
1721 const RegisterBump &RB = I->second;
1722 if (CmpRegs.count(RB.first)) {
1724 // If both operands to the compare instruction are registers, see if
1725 // it can be changed to use induction register as one of the operands.
1726 MachineInstr *IndI = nullptr;
1727 MachineInstr *nonIndI = nullptr;
1728 MachineOperand *IndMO = nullptr;
1729 MachineOperand *nonIndMO = nullptr;
1731 for (unsigned i = 1, n = PredDef->getNumOperands(); i < n; ++i) {
1732 MachineOperand &MO = PredDef->getOperand(i);
1733 if (MO.isReg() && MO.getReg() == RB.first) {
1734 DEBUG(dbgs() << "\n DefMI(" << i << ") = "
1735 << *(MRI->getVRegDef(I->first)));
1739 IndI = MRI->getVRegDef(I->first);
1741 } else if (MO.isReg()) {
1742 DEBUG(dbgs() << "\n DefMI(" << i << ") = "
1743 << *(MRI->getVRegDef(MO.getReg())));
1747 nonIndI = MRI->getVRegDef(MO.getReg());
1751 if (IndI && nonIndI &&
1752 nonIndI->getOpcode() == Hexagon::A2_addi &&
1753 nonIndI->getOperand(2).isImm() &&
1754 nonIndI->getOperand(2).getImm() == - RB.second) {
1755 bool Order = orderBumpCompare(IndI, PredDef);
1757 IndMO->setReg(I->first);
1758 nonIndMO->setReg(nonIndI->getOperand(1).getReg());
1765 // It is not valid to do this transformation on an unsigned comparison
1766 // because it may underflow.
1767 Comparison::Kind Cmp = getComparisonKind(PredDef->getOpcode(), 0, 0, 0);
1768 if (!Cmp || Comparison::isUnsigned(Cmp))
1771 // If the register is being compared against an immediate, try changing
1772 // the compare instruction to use induction register and adjust the
1773 // immediate operand.
1774 int64_t CmpImm = getImmediate(*CmpImmOp);
1775 int64_t V = RB.second;
1776 // Handle Overflow (64-bit).
1777 if (((V > 0) && (CmpImm > INT64_MAX - V)) ||
1778 ((V < 0) && (CmpImm < INT64_MIN - V)))
1781 // Most comparisons of register against an immediate value allow
1782 // the immediate to be constant-extended. There are some exceptions
1783 // though. Make sure the new combination will work.
1784 if (CmpImmOp->isImm())
1785 if (!isImmValidForOpcode(PredDef->getOpcode(), CmpImm))
1788 // Make sure that the compare happens after the bump. Otherwise,
1789 // after the fixup, the compare would use a yet-undefined register.
1790 MachineInstr *BumpI = MRI->getVRegDef(I->first);
1791 bool Order = orderBumpCompare(BumpI, PredDef);
1795 // Finally, fix the compare instruction.
1796 setImmediate(*CmpImmOp, CmpImm);
1797 for (unsigned i = 0, n = PredDef->getNumOperands(); i < n; ++i) {
1798 MachineOperand &MO = PredDef->getOperand(i);
1799 if (MO.isReg() && MO.getReg() == RB.first) {
1800 MO.setReg(I->first);
1810 /// \brief Create a preheader for a given loop.
1811 MachineBasicBlock *HexagonHardwareLoops::createPreheaderForLoop(
1813 if (MachineBasicBlock *TmpPH = L->getLoopPreheader())
1816 if (!HWCreatePreheader)
1819 MachineBasicBlock *Header = L->getHeader();
1820 MachineBasicBlock *Latch = L->getLoopLatch();
1821 MachineBasicBlock *ExitingBlock = getExitingBlock(L);
1822 MachineFunction *MF = Header->getParent();
1826 if ((PHFn != "") && (PHFn != MF->getName()))
1830 if (!Latch || !ExitingBlock || Header->hasAddressTaken())
1833 typedef MachineBasicBlock::instr_iterator instr_iterator;
1835 // Verify that all existing predecessors have analyzable branches
1836 // (or no branches at all).
1837 typedef std::vector<MachineBasicBlock*> MBBVector;
1838 MBBVector Preds(Header->pred_begin(), Header->pred_end());
1839 SmallVector<MachineOperand,2> Tmp1;
1840 MachineBasicBlock *TB = nullptr, *FB = nullptr;
1842 if (TII->AnalyzeBranch(*ExitingBlock, TB, FB, Tmp1, false))
1845 for (MBBVector::iterator I = Preds.begin(), E = Preds.end(); I != E; ++I) {
1846 MachineBasicBlock *PB = *I;
1847 bool NotAnalyzed = TII->AnalyzeBranch(*PB, TB, FB, Tmp1, false);
1852 MachineBasicBlock *NewPH = MF->CreateMachineBasicBlock();
1853 MF->insert(Header, NewPH);
1855 if (Header->pred_size() > 2) {
1856 // Ensure that the header has only two predecessors: the preheader and
1857 // the loop latch. Any additional predecessors of the header should
1858 // join at the newly created preheader. Inspect all PHI nodes from the
1859 // header and create appropriate corresponding PHI nodes in the preheader.
1861 for (instr_iterator I = Header->instr_begin(), E = Header->instr_end();
1862 I != E && I->isPHI(); ++I) {
1863 MachineInstr *PN = &*I;
1865 const MCInstrDesc &PD = TII->get(TargetOpcode::PHI);
1866 MachineInstr *NewPN = MF->CreateMachineInstr(PD, DL);
1867 NewPH->insert(NewPH->end(), NewPN);
1869 unsigned PR = PN->getOperand(0).getReg();
1870 const TargetRegisterClass *RC = MRI->getRegClass(PR);
1871 unsigned NewPR = MRI->createVirtualRegister(RC);
1872 NewPN->addOperand(MachineOperand::CreateReg(NewPR, true));
1874 // Copy all non-latch operands of a header's PHI node to the newly
1875 // created PHI node in the preheader.
1876 for (unsigned i = 1, n = PN->getNumOperands(); i < n; i += 2) {
1877 unsigned PredR = PN->getOperand(i).getReg();
1878 unsigned PredRSub = PN->getOperand(i).getSubReg();
1879 MachineBasicBlock *PredB = PN->getOperand(i+1).getMBB();
1883 MachineOperand MO = MachineOperand::CreateReg(PredR, false);
1884 MO.setSubReg(PredRSub);
1885 NewPN->addOperand(MO);
1886 NewPN->addOperand(MachineOperand::CreateMBB(PredB));
1889 // Remove copied operands from the old PHI node and add the value
1890 // coming from the preheader's PHI.
1891 for (int i = PN->getNumOperands()-2; i > 0; i -= 2) {
1892 MachineBasicBlock *PredB = PN->getOperand(i+1).getMBB();
1893 if (PredB != Latch) {
1894 PN->RemoveOperand(i+1);
1895 PN->RemoveOperand(i);
1898 PN->addOperand(MachineOperand::CreateReg(NewPR, false));
1899 PN->addOperand(MachineOperand::CreateMBB(NewPH));
1903 assert(Header->pred_size() == 2);
1905 // The header has only two predecessors, but the non-latch predecessor
1906 // is not a preheader (e.g. it has other successors, etc.)
1907 // In such a case we don't need any extra PHI nodes in the new preheader,
1908 // all we need is to adjust existing PHIs in the header to now refer to
1909 // the new preheader.
1910 for (instr_iterator I = Header->instr_begin(), E = Header->instr_end();
1911 I != E && I->isPHI(); ++I) {
1912 MachineInstr *PN = &*I;
1913 for (unsigned i = 1, n = PN->getNumOperands(); i < n; i += 2) {
1914 MachineOperand &MO = PN->getOperand(i+1);
1915 if (MO.getMBB() != Latch)
1921 // "Reroute" the CFG edges to link in the new preheader.
1922 // If any of the predecessors falls through to the header, insert a branch
1923 // to the new preheader in that place.
1924 SmallVector<MachineOperand,1> Tmp2;
1925 SmallVector<MachineOperand,1> EmptyCond;
1929 for (MBBVector::iterator I = Preds.begin(), E = Preds.end(); I != E; ++I) {
1930 MachineBasicBlock *PB = *I;
1933 bool NotAnalyzed = TII->AnalyzeBranch(*PB, TB, FB, Tmp2, false);
1934 (void)NotAnalyzed; // suppress compiler warning
1935 assert (!NotAnalyzed && "Should be analyzable!");
1936 if (TB != Header && (Tmp2.empty() || FB != Header))
1937 TII->InsertBranch(*PB, NewPH, nullptr, EmptyCond, DL);
1938 PB->ReplaceUsesOfBlockWith(Header, NewPH);
1942 // It can happen that the latch block will fall through into the header.
1943 // Insert an unconditional branch to the header.
1945 bool LatchNotAnalyzed = TII->AnalyzeBranch(*Latch, TB, FB, Tmp2, false);
1946 (void)LatchNotAnalyzed; // suppress compiler warning
1947 assert (!LatchNotAnalyzed && "Should be analyzable!");
1949 TII->InsertBranch(*Latch, Header, nullptr, EmptyCond, DL);
1951 // Finally, the branch from the preheader to the header.
1952 TII->InsertBranch(*NewPH, Header, nullptr, EmptyCond, DL);
1953 NewPH->addSuccessor(Header);
1955 MachineLoop *ParentLoop = L->getParentLoop();
1957 ParentLoop->addBasicBlockToLoop(NewPH, MLI->getBase());
1959 // Update the dominator information with the new preheader.
1961 MachineDomTreeNode *HDom = MDT->getNode(Header);
1962 MDT->addNewBlock(NewPH, HDom->getIDom()->getBlock());
1963 MDT->changeImmediateDominator(Header, NewPH);