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 void initializeHexagonHardwareLoopsPass(PassRegistry&);
71 struct HexagonHardwareLoops : public MachineFunctionPass {
73 MachineRegisterInfo *MRI;
74 MachineDominatorTree *MDT;
75 const HexagonInstrInfo *TII;
83 HexagonHardwareLoops() : MachineFunctionPass(ID) {
84 initializeHexagonHardwareLoopsPass(*PassRegistry::getPassRegistry());
87 bool runOnMachineFunction(MachineFunction &MF) override;
89 const char *getPassName() const override { return "Hexagon Hardware Loops"; }
91 void getAnalysisUsage(AnalysisUsage &AU) const override {
92 AU.addRequired<MachineDominatorTree>();
93 AU.addRequired<MachineLoopInfo>();
94 MachineFunctionPass::getAnalysisUsage(AU);
98 typedef std::map<unsigned, MachineInstr *> LoopFeederMap;
100 /// Kinds of comparisons in the compare instructions.
118 static Kind getSwappedComparison(Kind Cmp) {
119 assert ((!((Cmp & L) && (Cmp & G))) && "Malformed comparison operator");
120 if ((Cmp & L) || (Cmp & G))
121 return (Kind)(Cmp ^ (L|G));
125 static Kind getNegatedComparison(Kind Cmp) {
126 if ((Cmp & L) || (Cmp & G))
127 return (Kind)((Cmp ^ (L | G)) ^ EQ);
128 if ((Cmp & NE) || (Cmp & EQ))
129 return (Kind)(Cmp ^ (EQ | NE));
133 static bool isSigned(Kind Cmp) {
134 return (Cmp & (L | G) && !(Cmp & U));
137 static bool isUnsigned(Kind Cmp) {
143 /// \brief Find the register that contains the loop controlling
144 /// induction variable.
145 /// If successful, it will return true and set the \p Reg, \p IVBump
146 /// and \p IVOp arguments. Otherwise it will return false.
147 /// The returned induction register is the register R that follows the
148 /// following induction pattern:
150 /// R = phi ..., [ R.next, LatchBlock ]
151 /// R.next = R + #bump
152 /// if (R.next < #N) goto loop
153 /// IVBump is the immediate value added to R, and IVOp is the instruction
154 /// "R.next = R + #bump".
155 bool findInductionRegister(MachineLoop *L, unsigned &Reg,
156 int64_t &IVBump, MachineInstr *&IVOp) const;
158 /// \brief Return the comparison kind for the specified opcode.
159 Comparison::Kind getComparisonKind(unsigned CondOpc,
160 MachineOperand *InitialValue,
161 const MachineOperand *Endvalue,
162 int64_t IVBump) const;
164 /// \brief Analyze the statements in a loop to determine if the loop
165 /// has a computable trip count and, if so, return a value that represents
166 /// the trip count expression.
167 CountValue *getLoopTripCount(MachineLoop *L,
168 SmallVectorImpl<MachineInstr *> &OldInsts);
170 /// \brief Return the expression that represents the number of times
171 /// a loop iterates. The function takes the operands that represent the
172 /// loop start value, loop end value, and induction value. Based upon
173 /// these operands, the function attempts to compute the trip count.
174 /// If the trip count is not directly available (as an immediate value,
175 /// or a register), the function will attempt to insert computation of it
176 /// to the loop's preheader.
177 CountValue *computeCount(MachineLoop *Loop, const MachineOperand *Start,
178 const MachineOperand *End, unsigned IVReg,
179 int64_t IVBump, Comparison::Kind Cmp) const;
181 /// \brief Return true if the instruction is not valid within a hardware
183 bool isInvalidLoopOperation(const MachineInstr *MI,
184 bool IsInnerHWLoop) const;
186 /// \brief Return true if the loop contains an instruction that inhibits
187 /// using the hardware loop.
188 bool containsInvalidInstruction(MachineLoop *L, bool IsInnerHWLoop) const;
190 /// \brief Given a loop, check if we can convert it to a hardware loop.
191 /// If so, then perform the conversion and return true.
192 bool convertToHardwareLoop(MachineLoop *L, bool &L0used, bool &L1used);
194 /// \brief Return true if the instruction is now dead.
195 bool isDead(const MachineInstr *MI,
196 SmallVectorImpl<MachineInstr *> &DeadPhis) const;
198 /// \brief Remove the instruction if it is now dead.
199 void removeIfDead(MachineInstr *MI);
201 /// \brief Make sure that the "bump" instruction executes before the
202 /// compare. We need that for the IV fixup, so that the compare
203 /// instruction would not use a bumped value that has not yet been
204 /// defined. If the instructions are out of order, try to reorder them.
205 bool orderBumpCompare(MachineInstr *BumpI, MachineInstr *CmpI);
207 /// \brief Return true if MO and MI pair is visited only once. If visited
208 /// more than once, this indicates there is recursion. In such a case,
210 bool isLoopFeeder(MachineLoop *L, MachineBasicBlock *A, MachineInstr *MI,
211 const MachineOperand *MO,
212 LoopFeederMap &LoopFeederPhi) const;
214 /// \brief Return true if the Phi may generate a value that may underflow,
216 bool phiMayWrapOrUnderflow(MachineInstr *Phi, const MachineOperand *EndVal,
217 MachineBasicBlock *MBB, MachineLoop *L,
218 LoopFeederMap &LoopFeederPhi) const;
220 /// \brief Return true if the induction variable may underflow an unsigned
221 /// value in the first iteration.
222 bool loopCountMayWrapOrUnderFlow(const MachineOperand *InitVal,
223 const MachineOperand *EndVal,
224 MachineBasicBlock *MBB, MachineLoop *L,
225 LoopFeederMap &LoopFeederPhi) const;
227 /// \brief Check if the given operand has a compile-time known constant
228 /// value. Return true if yes, and false otherwise. When returning true, set
229 /// Val to the corresponding constant value.
230 bool checkForImmediate(const MachineOperand &MO, int64_t &Val) const;
232 /// \brief Check if the operand has a compile-time known constant value.
233 bool isImmediate(const MachineOperand &MO) const {
235 return checkForImmediate(MO, V);
238 /// \brief Return the immediate for the specified operand.
239 int64_t getImmediate(const MachineOperand &MO) const {
241 if (!checkForImmediate(MO, V))
242 llvm_unreachable("Invalid operand");
246 /// \brief Reset the given machine operand to now refer to a new immediate
247 /// value. Assumes that the operand was already referencing an immediate
248 /// value, either directly, or via a register.
249 void setImmediate(MachineOperand &MO, int64_t Val);
251 /// \brief Fix the data flow of the induction varible.
252 /// The desired flow is: phi ---> bump -+-> comparison-in-latch.
255 /// where "bump" is the increment of the induction variable:
256 /// iv = iv + #const.
257 /// Due to some prior code transformations, the actual flow may look
259 /// phi -+-> bump ---> back to phi
261 /// +-> comparison-in-latch (against upper_bound-bump),
262 /// i.e. the comparison that controls the loop execution may be using
263 /// the value of the induction variable from before the increment.
265 /// Return true if the loop's flow is the desired one (i.e. it's
266 /// either been fixed, or no fixing was necessary).
267 /// Otherwise, return false. This can happen if the induction variable
268 /// couldn't be identified, or if the value in the latch's comparison
269 /// cannot be adjusted to reflect the post-bump value.
270 bool fixupInductionVariable(MachineLoop *L);
272 /// \brief Given a loop, if it does not have a preheader, create one.
273 /// Return the block that is the preheader.
274 MachineBasicBlock *createPreheaderForLoop(MachineLoop *L);
277 char HexagonHardwareLoops::ID = 0;
279 int HexagonHardwareLoops::Counter = 0;
282 /// \brief Abstraction for a trip count of a loop. A smaller version
283 /// of the MachineOperand class without the concerns of changing the
284 /// operand representation.
287 enum CountValueType {
302 explicit CountValue(CountValueType t, unsigned v, unsigned u = 0) {
304 if (Kind == CV_Register) {
311 bool isReg() const { return Kind == CV_Register; }
312 bool isImm() const { return Kind == CV_Immediate; }
314 unsigned getReg() const {
315 assert(isReg() && "Wrong CountValue accessor");
316 return Contents.R.Reg;
318 unsigned getSubReg() const {
319 assert(isReg() && "Wrong CountValue accessor");
320 return Contents.R.Sub;
322 unsigned getImm() const {
323 assert(isImm() && "Wrong CountValue accessor");
324 return Contents.ImmVal;
327 void print(raw_ostream &OS, const TargetRegisterInfo *TRI = nullptr) const {
328 if (isReg()) { OS << PrintReg(Contents.R.Reg, TRI, Contents.R.Sub); }
329 if (isImm()) { OS << Contents.ImmVal; }
332 } // end anonymous namespace
335 INITIALIZE_PASS_BEGIN(HexagonHardwareLoops, "hwloops",
336 "Hexagon Hardware Loops", false, false)
337 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
338 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
339 INITIALIZE_PASS_END(HexagonHardwareLoops, "hwloops",
340 "Hexagon Hardware Loops", false, false)
342 FunctionPass *llvm::createHexagonHardwareLoops() {
343 return new HexagonHardwareLoops();
346 bool HexagonHardwareLoops::runOnMachineFunction(MachineFunction &MF) {
347 DEBUG(dbgs() << "********* Hexagon Hardware Loops *********\n");
349 bool Changed = false;
351 MLI = &getAnalysis<MachineLoopInfo>();
352 MRI = &MF.getRegInfo();
353 MDT = &getAnalysis<MachineDominatorTree>();
354 TII = MF.getSubtarget<HexagonSubtarget>().getInstrInfo();
357 if (!L->getParentLoop()) {
360 Changed |= convertToHardwareLoop(L, L0Used, L1Used);
366 /// \brief Return the latch block if it's one of the exiting blocks. Otherwise,
367 /// return the exiting block. Return 'null' when multiple exiting blocks are
369 static MachineBasicBlock* getExitingBlock(MachineLoop *L) {
370 if (MachineBasicBlock *Latch = L->getLoopLatch()) {
371 if (L->isLoopExiting(Latch))
374 return L->getExitingBlock();
379 bool HexagonHardwareLoops::findInductionRegister(MachineLoop *L,
384 MachineBasicBlock *Header = L->getHeader();
385 MachineBasicBlock *Preheader = L->getLoopPreheader();
386 MachineBasicBlock *Latch = L->getLoopLatch();
387 MachineBasicBlock *ExitingBlock = getExitingBlock(L);
388 if (!Header || !Preheader || !Latch || !ExitingBlock)
391 // This pair represents an induction register together with an immediate
392 // value that will be added to it in each loop iteration.
393 typedef std::pair<unsigned,int64_t> RegisterBump;
395 // Mapping: R.next -> (R, bump), where R, R.next and bump are derived
396 // from an induction operation
398 // where bump is an immediate value.
399 typedef std::map<unsigned,RegisterBump> InductionMap;
403 typedef MachineBasicBlock::instr_iterator instr_iterator;
404 for (instr_iterator I = Header->instr_begin(), E = Header->instr_end();
405 I != E && I->isPHI(); ++I) {
406 MachineInstr *Phi = &*I;
408 // Have a PHI instruction. Get the operand that corresponds to the
409 // latch block, and see if is a result of an addition of form "reg+imm",
410 // where the "reg" is defined by the PHI node we are looking at.
411 for (unsigned i = 1, n = Phi->getNumOperands(); i < n; i += 2) {
412 if (Phi->getOperand(i+1).getMBB() != Latch)
415 unsigned PhiOpReg = Phi->getOperand(i).getReg();
416 MachineInstr *DI = MRI->getVRegDef(PhiOpReg);
417 unsigned UpdOpc = DI->getOpcode();
418 bool isAdd = (UpdOpc == Hexagon::A2_addi || UpdOpc == Hexagon::A2_addp);
421 // If the register operand to the add is the PHI we're looking at, this
422 // meets the induction pattern.
423 unsigned IndReg = DI->getOperand(1).getReg();
424 MachineOperand &Opnd2 = DI->getOperand(2);
426 if (MRI->getVRegDef(IndReg) == Phi && checkForImmediate(Opnd2, V)) {
427 unsigned UpdReg = DI->getOperand(0).getReg();
428 IndMap.insert(std::make_pair(UpdReg, std::make_pair(IndReg, V)));
434 SmallVector<MachineOperand,2> Cond;
435 MachineBasicBlock *TB = nullptr, *FB = nullptr;
436 bool NotAnalyzed = TII->AnalyzeBranch(*ExitingBlock, TB, FB, Cond, false);
440 unsigned PredR, PredPos, PredRegFlags;
441 if (!TII->getPredReg(Cond, PredR, PredPos, PredRegFlags))
444 MachineInstr *PredI = MRI->getVRegDef(PredR);
445 if (!PredI->isCompare())
448 unsigned CmpReg1 = 0, CmpReg2 = 0;
449 int CmpImm = 0, CmpMask = 0;
450 bool CmpAnalyzed = TII->analyzeCompare(PredI, CmpReg1, CmpReg2,
452 // Fail if the compare was not analyzed, or it's not comparing a register
453 // with an immediate value. Not checking the mask here, since we handle
454 // the individual compare opcodes (including A4_cmpb*) later on.
458 // Exactly one of the input registers to the comparison should be among
459 // the induction registers.
460 InductionMap::iterator IndMapEnd = IndMap.end();
461 InductionMap::iterator F = IndMapEnd;
463 InductionMap::iterator F1 = IndMap.find(CmpReg1);
468 InductionMap::iterator F2 = IndMap.find(CmpReg2);
469 if (F2 != IndMapEnd) {
478 Reg = F->second.first;
479 IVBump = F->second.second;
480 IVOp = MRI->getVRegDef(F->first);
484 // Return the comparison kind for the specified opcode.
485 HexagonHardwareLoops::Comparison::Kind
486 HexagonHardwareLoops::getComparisonKind(unsigned CondOpc,
487 MachineOperand *InitialValue,
488 const MachineOperand *EndValue,
489 int64_t IVBump) const {
490 Comparison::Kind Cmp = (Comparison::Kind)0;
492 case Hexagon::C2_cmpeqi:
493 case Hexagon::C2_cmpeq:
494 case Hexagon::C2_cmpeqp:
495 Cmp = Comparison::EQ;
497 case Hexagon::C4_cmpneq:
498 case Hexagon::C4_cmpneqi:
499 Cmp = Comparison::NE;
501 case Hexagon::C4_cmplte:
502 Cmp = Comparison::LEs;
504 case Hexagon::C4_cmplteu:
505 Cmp = Comparison::LEu;
507 case Hexagon::C2_cmpgtui:
508 case Hexagon::C2_cmpgtu:
509 case Hexagon::C2_cmpgtup:
510 Cmp = Comparison::GTu;
512 case Hexagon::C2_cmpgti:
513 case Hexagon::C2_cmpgt:
514 case Hexagon::C2_cmpgtp:
515 Cmp = Comparison::GTs;
518 return (Comparison::Kind)0;
523 /// \brief Analyze the statements in a loop to determine if the loop has
524 /// a computable trip count and, if so, return a value that represents
525 /// the trip count expression.
527 /// This function iterates over the phi nodes in the loop to check for
528 /// induction variable patterns that are used in the calculation for
529 /// the number of time the loop is executed.
530 CountValue *HexagonHardwareLoops::getLoopTripCount(MachineLoop *L,
531 SmallVectorImpl<MachineInstr *> &OldInsts) {
532 MachineBasicBlock *TopMBB = L->getTopBlock();
533 MachineBasicBlock::pred_iterator PI = TopMBB->pred_begin();
534 assert(PI != TopMBB->pred_end() &&
535 "Loop must have more than one incoming edge!");
536 MachineBasicBlock *Backedge = *PI++;
537 if (PI == TopMBB->pred_end()) // dead loop?
539 MachineBasicBlock *Incoming = *PI++;
540 if (PI != TopMBB->pred_end()) // multiple backedges?
543 // Make sure there is one incoming and one backedge and determine which
545 if (L->contains(Incoming)) {
546 if (L->contains(Backedge))
548 std::swap(Incoming, Backedge);
549 } else if (!L->contains(Backedge))
552 // Look for the cmp instruction to determine if we can get a useful trip
553 // count. The trip count can be either a register or an immediate. The
554 // location of the value depends upon the type (reg or imm).
555 MachineBasicBlock *ExitingBlock = getExitingBlock(L);
562 bool FoundIV = findInductionRegister(L, IVReg, IVBump, IVOp);
566 MachineBasicBlock *Preheader = L->getLoopPreheader();
568 MachineOperand *InitialValue = nullptr;
569 MachineInstr *IV_Phi = MRI->getVRegDef(IVReg);
570 MachineBasicBlock *Latch = L->getLoopLatch();
571 for (unsigned i = 1, n = IV_Phi->getNumOperands(); i < n; i += 2) {
572 MachineBasicBlock *MBB = IV_Phi->getOperand(i+1).getMBB();
573 if (MBB == Preheader)
574 InitialValue = &IV_Phi->getOperand(i);
575 else if (MBB == Latch)
576 IVReg = IV_Phi->getOperand(i).getReg(); // Want IV reg after bump.
581 SmallVector<MachineOperand,2> Cond;
582 MachineBasicBlock *TB = nullptr, *FB = nullptr;
583 bool NotAnalyzed = TII->AnalyzeBranch(*ExitingBlock, TB, FB, Cond, false);
587 MachineBasicBlock *Header = L->getHeader();
588 // TB must be non-null. If FB is also non-null, one of them must be
589 // the header. Otherwise, branch to TB could be exiting the loop, and
590 // the fall through can go to the header.
591 assert (TB && "Exit block without a branch?");
592 if (ExitingBlock != Latch && (TB == Latch || FB == Latch)) {
593 MachineBasicBlock *LTB = 0, *LFB = 0;
594 SmallVector<MachineOperand,2> LCond;
595 bool NotAnalyzed = TII->AnalyzeBranch(*Latch, LTB, LFB, LCond, false);
599 TB = (LTB == Header) ? LTB : LFB;
601 FB = (LTB == Header) ? LTB: LFB;
603 assert ((!FB || TB == Header || FB == Header) && "Branches not to header?");
604 if (!TB || (FB && TB != Header && FB != Header))
607 // Branches of form "if (!P) ..." cause HexagonInstrInfo::AnalyzeBranch
608 // to put imm(0), followed by P in the vector Cond.
609 // If TB is not the header, it means that the "not-taken" path must lead
611 bool Negated = TII->predOpcodeHasNot(Cond) ^ (TB != Header);
612 unsigned PredReg, PredPos, PredRegFlags;
613 if (!TII->getPredReg(Cond, PredReg, PredPos, PredRegFlags))
615 MachineInstr *CondI = MRI->getVRegDef(PredReg);
616 unsigned CondOpc = CondI->getOpcode();
618 unsigned CmpReg1 = 0, CmpReg2 = 0;
619 int Mask = 0, ImmValue = 0;
620 bool AnalyzedCmp = TII->analyzeCompare(CondI, CmpReg1, CmpReg2,
625 // The comparison operator type determines how we compute the loop
627 OldInsts.push_back(CondI);
628 OldInsts.push_back(IVOp);
630 // Sadly, the following code gets information based on the position
631 // of the operands in the compare instruction. This has to be done
632 // this way, because the comparisons check for a specific relationship
633 // between the operands (e.g. is-less-than), rather than to find out
634 // what relationship the operands are in (as on PPC).
635 Comparison::Kind Cmp;
636 bool isSwapped = false;
637 const MachineOperand &Op1 = CondI->getOperand(1);
638 const MachineOperand &Op2 = CondI->getOperand(2);
639 const MachineOperand *EndValue = nullptr;
642 if (Op2.isImm() || Op1.getReg() == IVReg)
653 Cmp = getComparisonKind(CondOpc, InitialValue, EndValue, IVBump);
657 Cmp = Comparison::getNegatedComparison(Cmp);
659 Cmp = Comparison::getSwappedComparison(Cmp);
661 if (InitialValue->isReg()) {
662 unsigned R = InitialValue->getReg();
663 MachineBasicBlock *DefBB = MRI->getVRegDef(R)->getParent();
664 if (!MDT->properlyDominates(DefBB, Header))
666 OldInsts.push_back(MRI->getVRegDef(R));
668 if (EndValue->isReg()) {
669 unsigned R = EndValue->getReg();
670 MachineBasicBlock *DefBB = MRI->getVRegDef(R)->getParent();
671 if (!MDT->properlyDominates(DefBB, Header))
673 OldInsts.push_back(MRI->getVRegDef(R));
676 return computeCount(L, InitialValue, EndValue, IVReg, IVBump, Cmp);
679 /// \brief Helper function that returns the expression that represents the
680 /// number of times a loop iterates. The function takes the operands that
681 /// represent the loop start value, loop end value, and induction value.
682 /// Based upon these operands, the function attempts to compute the trip count.
683 CountValue *HexagonHardwareLoops::computeCount(MachineLoop *Loop,
684 const MachineOperand *Start,
685 const MachineOperand *End,
688 Comparison::Kind Cmp) const {
689 // Cannot handle comparison EQ, i.e. while (A == B).
690 if (Cmp == Comparison::EQ)
693 // Check if either the start or end values are an assignment of an immediate.
694 // If so, use the immediate value rather than the register.
695 if (Start->isReg()) {
696 const MachineInstr *StartValInstr = MRI->getVRegDef(Start->getReg());
697 if (StartValInstr && (StartValInstr->getOpcode() == Hexagon::A2_tfrsi ||
698 StartValInstr->getOpcode() == Hexagon::A2_tfrpi))
699 Start = &StartValInstr->getOperand(1);
702 const MachineInstr *EndValInstr = MRI->getVRegDef(End->getReg());
703 if (EndValInstr && (EndValInstr->getOpcode() == Hexagon::A2_tfrsi ||
704 EndValInstr->getOpcode() == Hexagon::A2_tfrpi))
705 End = &EndValInstr->getOperand(1);
708 if (!Start->isReg() && !Start->isImm())
710 if (!End->isReg() && !End->isImm())
713 bool CmpLess = Cmp & Comparison::L;
714 bool CmpGreater = Cmp & Comparison::G;
715 bool CmpHasEqual = Cmp & Comparison::EQ;
717 // Avoid certain wrap-arounds. This doesn't detect all wrap-arounds.
718 if (CmpLess && IVBump < 0)
719 // Loop going while iv is "less" with the iv value going down. Must wrap.
722 if (CmpGreater && IVBump > 0)
723 // Loop going while iv is "greater" with the iv value going up. Must wrap.
726 // Phis that may feed into the loop.
727 LoopFeederMap LoopFeederPhi;
729 // Check if the inital value may be zero and can be decremented in the first
730 // iteration. If the value is zero, the endloop instruction will not decrement
731 // the loop counter, so we shoudn't generate a hardware loop in this case.
732 if (loopCountMayWrapOrUnderFlow(Start, End, Loop->getLoopPreheader(), Loop,
736 if (Start->isImm() && End->isImm()) {
737 // Both, start and end are immediates.
738 int64_t StartV = Start->getImm();
739 int64_t EndV = End->getImm();
740 int64_t Dist = EndV - StartV;
744 bool Exact = (Dist % IVBump) == 0;
746 if (Cmp == Comparison::NE) {
749 if ((Dist < 0) ^ (IVBump < 0))
753 // For comparisons that include the final value (i.e. include equality
754 // with the final value), we need to increase the distance by 1.
756 Dist = Dist > 0 ? Dist+1 : Dist-1;
758 // For the loop to iterate, CmpLess should imply Dist > 0. Similarly,
759 // CmpGreater should imply Dist < 0. These conditions could actually
760 // fail, for example, in unreachable code (which may still appear to be
761 // reachable in the CFG).
762 if ((CmpLess && Dist < 0) || (CmpGreater && Dist > 0))
765 // "Normalized" distance, i.e. with the bump set to +-1.
766 int64_t Dist1 = (IVBump > 0) ? (Dist + (IVBump - 1)) / IVBump
767 : (-Dist + (-IVBump - 1)) / (-IVBump);
768 assert (Dist1 > 0 && "Fishy thing. Both operands have the same sign.");
770 uint64_t Count = Dist1;
772 if (Count > 0xFFFFFFFFULL)
775 return new CountValue(CountValue::CV_Immediate, Count);
778 // A general case: Start and End are some values, but the actual
779 // iteration count may not be available. If it is not, insert
780 // a computation of it into the preheader.
782 // If the induction variable bump is not a power of 2, quit.
783 // Othwerise we'd need a general integer division.
784 if (!isPowerOf2_64(std::abs(IVBump)))
787 MachineBasicBlock *PH = Loop->getLoopPreheader();
788 assert (PH && "Should have a preheader by now");
789 MachineBasicBlock::iterator InsertPos = PH->getFirstTerminator();
791 if (InsertPos != PH->end())
792 DL = InsertPos->getDebugLoc();
794 // If Start is an immediate and End is a register, the trip count
795 // will be "reg - imm". Hexagon's "subtract immediate" instruction
796 // is actually "reg + -imm".
798 // If the loop IV is going downwards, i.e. if the bump is negative,
799 // then the iteration count (computed as End-Start) will need to be
800 // negated. To avoid the negation, just swap Start and End.
802 std::swap(Start, End);
805 // Cmp may now have a wrong direction, e.g. LEs may now be GEs.
806 // Signedness, and "including equality" are preserved.
808 bool RegToImm = Start->isReg() && End->isImm(); // for (reg..imm)
809 bool RegToReg = Start->isReg() && End->isReg(); // for (reg..reg)
811 int64_t StartV = 0, EndV = 0;
813 StartV = Start->getImm();
815 EndV = End->getImm();
818 // To compute the iteration count, we would need this computation:
819 // Count = (End - Start + (IVBump-1)) / IVBump
820 // or, when CmpHasEqual:
821 // Count = (End - Start + (IVBump-1)+1) / IVBump
822 // The "IVBump-1" part is the adjustment (AdjV). We can avoid
823 // generating an instruction specifically to add it if we can adjust
824 // the immediate values for Start or End.
827 // Need to add 1 to the total iteration count.
830 else if (End->isImm())
836 if (Cmp != Comparison::NE) {
838 StartV -= (IVBump-1);
839 else if (End->isImm())
845 unsigned R = 0, SR = 0;
846 if (Start->isReg()) {
848 SR = Start->getSubReg();
851 SR = End->getSubReg();
853 const TargetRegisterClass *RC = MRI->getRegClass(R);
854 // Hardware loops cannot handle 64-bit registers. If it's a double
855 // register, it has to have a subregister.
856 if (!SR && RC == &Hexagon::DoubleRegsRegClass)
858 const TargetRegisterClass *IntRC = &Hexagon::IntRegsRegClass;
860 // Compute DistR (register with the distance between Start and End).
861 unsigned DistR, DistSR;
863 // Avoid special case, where the start value is an imm(0).
864 if (Start->isImm() && StartV == 0) {
865 DistR = End->getReg();
866 DistSR = End->getSubReg();
868 const MCInstrDesc &SubD = RegToReg ? TII->get(Hexagon::A2_sub) :
869 (RegToImm ? TII->get(Hexagon::A2_subri) :
870 TII->get(Hexagon::A2_addi));
871 if (RegToReg || RegToImm) {
872 unsigned SubR = MRI->createVirtualRegister(IntRC);
873 MachineInstrBuilder SubIB =
874 BuildMI(*PH, InsertPos, DL, SubD, SubR);
877 SubIB.addReg(End->getReg(), 0, End->getSubReg())
878 .addReg(Start->getReg(), 0, Start->getSubReg());
881 .addReg(Start->getReg(), 0, Start->getSubReg());
884 // If the loop has been unrolled, we should use the original loop count
885 // instead of recalculating the value. This will avoid additional
886 // 'Add' instruction.
887 const MachineInstr *EndValInstr = MRI->getVRegDef(End->getReg());
888 if (EndValInstr->getOpcode() == Hexagon::A2_addi &&
889 EndValInstr->getOperand(2).getImm() == StartV) {
890 DistR = EndValInstr->getOperand(1).getReg();
892 unsigned SubR = MRI->createVirtualRegister(IntRC);
893 MachineInstrBuilder SubIB =
894 BuildMI(*PH, InsertPos, DL, SubD, SubR);
895 SubIB.addReg(End->getReg(), 0, End->getSubReg())
903 // From DistR, compute AdjR (register with the adjusted distance).
904 unsigned AdjR, AdjSR;
910 // Generate CountR = ADD DistR, AdjVal
911 unsigned AddR = MRI->createVirtualRegister(IntRC);
912 MCInstrDesc const &AddD = TII->get(Hexagon::A2_addi);
913 BuildMI(*PH, InsertPos, DL, AddD, AddR)
914 .addReg(DistR, 0, DistSR)
921 // From AdjR, compute CountR (register with the final count).
922 unsigned CountR, CountSR;
928 // The IV bump is a power of two. Log_2(IV bump) is the shift amount.
929 unsigned Shift = Log2_32(IVBump);
931 // Generate NormR = LSR DistR, Shift.
932 unsigned LsrR = MRI->createVirtualRegister(IntRC);
933 const MCInstrDesc &LsrD = TII->get(Hexagon::S2_lsr_i_r);
934 BuildMI(*PH, InsertPos, DL, LsrD, LsrR)
935 .addReg(AdjR, 0, AdjSR)
942 return new CountValue(CountValue::CV_Register, CountR, CountSR);
945 /// \brief Return true if the operation is invalid within hardware loop.
946 bool HexagonHardwareLoops::isInvalidLoopOperation(const MachineInstr *MI,
947 bool IsInnerHWLoop) const {
949 // Call is not allowed because the callee may use a hardware loop except for
950 // the case when the call never returns.
951 if (MI->getDesc().isCall() && MI->getOpcode() != Hexagon::CALLv3nr)
954 // Check if the instruction defines a hardware loop register.
955 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
956 const MachineOperand &MO = MI->getOperand(i);
957 if (!MO.isReg() || !MO.isDef())
959 unsigned R = MO.getReg();
960 if (IsInnerHWLoop && (R == Hexagon::LC0 || R == Hexagon::SA0 ||
961 R == Hexagon::LC1 || R == Hexagon::SA1))
963 if (!IsInnerHWLoop && (R == Hexagon::LC1 || R == Hexagon::SA1))
969 /// \brief Return true if the loop contains an instruction that inhibits
970 /// the use of the hardware loop instruction.
971 bool HexagonHardwareLoops::containsInvalidInstruction(MachineLoop *L,
972 bool IsInnerHWLoop) const {
973 const std::vector<MachineBasicBlock *> &Blocks = L->getBlocks();
974 DEBUG(dbgs() << "\nhw_loop head, BB#" << Blocks[0]->getNumber(););
975 for (unsigned i = 0, e = Blocks.size(); i != e; ++i) {
976 MachineBasicBlock *MBB = Blocks[i];
977 for (MachineBasicBlock::iterator
978 MII = MBB->begin(), E = MBB->end(); MII != E; ++MII) {
979 const MachineInstr *MI = &*MII;
980 if (isInvalidLoopOperation(MI, IsInnerHWLoop)) {
981 DEBUG(dbgs()<< "\nCannot convert to hw_loop due to:"; MI->dump(););
989 /// \brief Returns true if the instruction is dead. This was essentially
990 /// copied from DeadMachineInstructionElim::isDead, but with special cases
991 /// for inline asm, physical registers and instructions with side effects
993 bool HexagonHardwareLoops::isDead(const MachineInstr *MI,
994 SmallVectorImpl<MachineInstr *> &DeadPhis) const {
995 // Examine each operand.
996 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
997 const MachineOperand &MO = MI->getOperand(i);
998 if (!MO.isReg() || !MO.isDef())
1001 unsigned Reg = MO.getReg();
1002 if (MRI->use_nodbg_empty(Reg))
1005 typedef MachineRegisterInfo::use_nodbg_iterator use_nodbg_iterator;
1007 // This instruction has users, but if the only user is the phi node for the
1008 // parent block, and the only use of that phi node is this instruction, then
1009 // this instruction is dead: both it (and the phi node) can be removed.
1010 use_nodbg_iterator I = MRI->use_nodbg_begin(Reg);
1011 use_nodbg_iterator End = MRI->use_nodbg_end();
1012 if (std::next(I) != End || !I->getParent()->isPHI())
1015 MachineInstr *OnePhi = I->getParent();
1016 for (unsigned j = 0, f = OnePhi->getNumOperands(); j != f; ++j) {
1017 const MachineOperand &OPO = OnePhi->getOperand(j);
1018 if (!OPO.isReg() || !OPO.isDef())
1021 unsigned OPReg = OPO.getReg();
1022 use_nodbg_iterator nextJ;
1023 for (use_nodbg_iterator J = MRI->use_nodbg_begin(OPReg);
1024 J != End; J = nextJ) {
1025 nextJ = std::next(J);
1026 MachineOperand &Use = *J;
1027 MachineInstr *UseMI = Use.getParent();
1029 // If the phi node has a user that is not MI, bail.
1034 DeadPhis.push_back(OnePhi);
1037 // If there are no defs with uses, the instruction is dead.
1041 void HexagonHardwareLoops::removeIfDead(MachineInstr *MI) {
1042 // This procedure was essentially copied from DeadMachineInstructionElim.
1044 SmallVector<MachineInstr*, 1> DeadPhis;
1045 if (isDead(MI, DeadPhis)) {
1046 DEBUG(dbgs() << "HW looping will remove: " << *MI);
1048 // It is possible that some DBG_VALUE instructions refer to this
1049 // instruction. Examine each def operand for such references;
1050 // if found, mark the DBG_VALUE as undef (but don't delete it).
1051 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
1052 const MachineOperand &MO = MI->getOperand(i);
1053 if (!MO.isReg() || !MO.isDef())
1055 unsigned Reg = MO.getReg();
1056 MachineRegisterInfo::use_iterator nextI;
1057 for (MachineRegisterInfo::use_iterator I = MRI->use_begin(Reg),
1058 E = MRI->use_end(); I != E; I = nextI) {
1059 nextI = std::next(I); // I is invalidated by the setReg
1060 MachineOperand &Use = *I;
1061 MachineInstr *UseMI = I->getParent();
1065 UseMI->getOperand(0).setReg(0U);
1069 MI->eraseFromParent();
1070 for (unsigned i = 0; i < DeadPhis.size(); ++i)
1071 DeadPhis[i]->eraseFromParent();
1075 /// \brief Check if the loop is a candidate for converting to a hardware
1076 /// loop. If so, then perform the transformation.
1078 /// This function works on innermost loops first. A loop can be converted
1079 /// if it is a counting loop; either a register value or an immediate.
1081 /// The code makes several assumptions about the representation of the loop
1083 bool HexagonHardwareLoops::convertToHardwareLoop(MachineLoop *L,
1086 // This is just for sanity.
1087 assert(L->getHeader() && "Loop without a header?");
1089 bool Changed = false;
1090 bool L0Used = false;
1091 bool L1Used = false;
1093 // Process nested loops first.
1094 for (MachineLoop::iterator I = L->begin(), E = L->end(); I != E; ++I) {
1095 Changed |= convertToHardwareLoop(*I, RecL0used, RecL1used);
1096 L0Used |= RecL0used;
1097 L1Used |= RecL1used;
1100 // If a nested loop has been converted, then we can't convert this loop.
1101 if (Changed && L0Used && L1Used)
1108 // Flag used to track loopN instruction:
1109 // 1 - Hardware loop is being generated for the inner most loop.
1110 // 0 - Hardware loop is being generated for the outer loop.
1111 unsigned IsInnerHWLoop = 1;
1114 LOOP_i = Hexagon::J2_loop1i;
1115 LOOP_r = Hexagon::J2_loop1r;
1116 ENDLOOP = Hexagon::ENDLOOP1;
1119 LOOP_i = Hexagon::J2_loop0i;
1120 LOOP_r = Hexagon::J2_loop0r;
1121 ENDLOOP = Hexagon::ENDLOOP0;
1125 // Stop trying after reaching the limit (if any).
1126 int Limit = HWLoopLimit;
1128 if (Counter >= HWLoopLimit)
1134 // Does the loop contain any invalid instructions?
1135 if (containsInvalidInstruction(L, IsInnerHWLoop))
1138 MachineBasicBlock *LastMBB = getExitingBlock(L);
1139 // Don't generate hw loop if the loop has more than one exit.
1143 MachineBasicBlock::iterator LastI = LastMBB->getFirstTerminator();
1144 if (LastI == LastMBB->end())
1147 // Is the induction variable bump feeding the latch condition?
1148 if (!fixupInductionVariable(L))
1151 // Ensure the loop has a preheader: the loop instruction will be
1153 MachineBasicBlock *Preheader = L->getLoopPreheader();
1155 Preheader = createPreheaderForLoop(L);
1160 MachineBasicBlock::iterator InsertPos = Preheader->getFirstTerminator();
1162 SmallVector<MachineInstr*, 2> OldInsts;
1163 // Are we able to determine the trip count for the loop?
1164 CountValue *TripCount = getLoopTripCount(L, OldInsts);
1168 // Is the trip count available in the preheader?
1169 if (TripCount->isReg()) {
1170 // There will be a use of the register inserted into the preheader,
1171 // so make sure that the register is actually defined at that point.
1172 MachineInstr *TCDef = MRI->getVRegDef(TripCount->getReg());
1173 MachineBasicBlock *BBDef = TCDef->getParent();
1174 if (!MDT->dominates(BBDef, Preheader))
1178 // Determine the loop start.
1179 MachineBasicBlock *TopBlock = L->getTopBlock();
1180 MachineBasicBlock *ExitingBlock = getExitingBlock(L);
1181 MachineBasicBlock *LoopStart = 0;
1182 if (ExitingBlock != L->getLoopLatch()) {
1183 MachineBasicBlock *TB = 0, *FB = 0;
1184 SmallVector<MachineOperand, 2> Cond;
1186 if (TII->AnalyzeBranch(*ExitingBlock, TB, FB, Cond, false))
1189 if (L->contains(TB))
1191 else if (L->contains(FB))
1197 LoopStart = TopBlock;
1199 // Convert the loop to a hardware loop.
1200 DEBUG(dbgs() << "Change to hardware loop at "; L->dump());
1202 if (InsertPos != Preheader->end())
1203 DL = InsertPos->getDebugLoc();
1205 if (TripCount->isReg()) {
1206 // Create a copy of the loop count register.
1207 unsigned CountReg = MRI->createVirtualRegister(&Hexagon::IntRegsRegClass);
1208 BuildMI(*Preheader, InsertPos, DL, TII->get(TargetOpcode::COPY), CountReg)
1209 .addReg(TripCount->getReg(), 0, TripCount->getSubReg());
1210 // Add the Loop instruction to the beginning of the loop.
1211 BuildMI(*Preheader, InsertPos, DL, TII->get(LOOP_r)).addMBB(LoopStart)
1214 assert(TripCount->isImm() && "Expecting immediate value for trip count");
1215 // Add the Loop immediate instruction to the beginning of the loop,
1216 // if the immediate fits in the instructions. Otherwise, we need to
1217 // create a new virtual register.
1218 int64_t CountImm = TripCount->getImm();
1219 if (!TII->isValidOffset(LOOP_i, CountImm)) {
1220 unsigned CountReg = MRI->createVirtualRegister(&Hexagon::IntRegsRegClass);
1221 BuildMI(*Preheader, InsertPos, DL, TII->get(Hexagon::A2_tfrsi), CountReg)
1223 BuildMI(*Preheader, InsertPos, DL, TII->get(LOOP_r))
1224 .addMBB(LoopStart).addReg(CountReg);
1226 BuildMI(*Preheader, InsertPos, DL, TII->get(LOOP_i))
1227 .addMBB(LoopStart).addImm(CountImm);
1230 // Make sure the loop start always has a reference in the CFG. We need
1231 // to create a BlockAddress operand to get this mechanism to work both the
1232 // MachineBasicBlock and BasicBlock objects need the flag set.
1233 LoopStart->setHasAddressTaken();
1234 // This line is needed to set the hasAddressTaken flag on the BasicBlock
1236 BlockAddress::get(const_cast<BasicBlock *>(LoopStart->getBasicBlock()));
1238 // Replace the loop branch with an endloop instruction.
1239 DebugLoc LastIDL = LastI->getDebugLoc();
1240 BuildMI(*LastMBB, LastI, LastIDL, TII->get(ENDLOOP)).addMBB(LoopStart);
1242 // The loop ends with either:
1243 // - a conditional branch followed by an unconditional branch, or
1244 // - a conditional branch to the loop start.
1245 if (LastI->getOpcode() == Hexagon::J2_jumpt ||
1246 LastI->getOpcode() == Hexagon::J2_jumpf) {
1247 // Delete one and change/add an uncond. branch to out of the loop.
1248 MachineBasicBlock *BranchTarget = LastI->getOperand(1).getMBB();
1249 LastI = LastMBB->erase(LastI);
1250 if (!L->contains(BranchTarget)) {
1251 if (LastI != LastMBB->end())
1252 LastI = LastMBB->erase(LastI);
1253 SmallVector<MachineOperand, 0> Cond;
1254 TII->InsertBranch(*LastMBB, BranchTarget, nullptr, Cond, LastIDL);
1257 // Conditional branch to loop start; just delete it.
1258 LastMBB->erase(LastI);
1262 // The induction operation and the comparison may now be
1263 // unneeded. If these are unneeded, then remove them.
1264 for (unsigned i = 0; i < OldInsts.size(); ++i)
1265 removeIfDead(OldInsts[i]);
1269 // Set RecL1used and RecL0used only after hardware loop has been
1270 // successfully generated. Doing it earlier can cause wrong loop instruction
1272 if (L0Used) // Loop0 was already used. So, the correct loop must be loop1.
1280 bool HexagonHardwareLoops::orderBumpCompare(MachineInstr *BumpI,
1281 MachineInstr *CmpI) {
1282 assert (BumpI != CmpI && "Bump and compare in the same instruction?");
1284 MachineBasicBlock *BB = BumpI->getParent();
1285 if (CmpI->getParent() != BB)
1288 typedef MachineBasicBlock::instr_iterator instr_iterator;
1289 // Check if things are in order to begin with.
1290 for (instr_iterator I = BumpI, E = BB->instr_end(); I != E; ++I)
1295 unsigned PredR = CmpI->getOperand(0).getReg();
1296 bool FoundBump = false;
1297 instr_iterator CmpIt = CmpI, NextIt = std::next(CmpIt);
1298 for (instr_iterator I = NextIt, E = BB->instr_end(); I != E; ++I) {
1299 MachineInstr *In = &*I;
1300 for (unsigned i = 0, n = In->getNumOperands(); i < n; ++i) {
1301 MachineOperand &MO = In->getOperand(i);
1302 if (MO.isReg() && MO.isUse()) {
1303 if (MO.getReg() == PredR) // Found an intervening use of PredR.
1309 instr_iterator After = BumpI;
1310 instr_iterator From = CmpI;
1311 BB->splice(std::next(After), BB, From);
1316 assert (FoundBump && "Cannot determine instruction order");
1320 /// This function is required to break recursion. Visiting phis in a loop may
1321 /// result in recursion during compilation. We break the recursion by making
1322 /// sure that we visit a MachineOperand and its definition in a
1323 /// MachineInstruction only once. If we attempt to visit more than once, then
1324 /// there is recursion, and will return false.
1325 bool HexagonHardwareLoops::isLoopFeeder(MachineLoop *L, MachineBasicBlock *A,
1327 const MachineOperand *MO,
1328 LoopFeederMap &LoopFeederPhi) const {
1329 if (LoopFeederPhi.find(MO->getReg()) == LoopFeederPhi.end()) {
1330 const std::vector<MachineBasicBlock *> &Blocks = L->getBlocks();
1331 DEBUG(dbgs() << "\nhw_loop head, BB#" << Blocks[0]->getNumber(););
1332 // Ignore all BBs that form Loop.
1333 for (unsigned i = 0, e = Blocks.size(); i != e; ++i) {
1334 MachineBasicBlock *MBB = Blocks[i];
1338 MachineInstr *Def = MRI->getVRegDef(MO->getReg());
1339 LoopFeederPhi.insert(std::make_pair(MO->getReg(), Def));
1342 // Already visited node.
1346 /// Return true if a Phi may generate a value that can underflow.
1347 /// This function calls loopCountMayWrapOrUnderFlow for each Phi operand.
1348 bool HexagonHardwareLoops::phiMayWrapOrUnderflow(
1349 MachineInstr *Phi, const MachineOperand *EndVal, MachineBasicBlock *MBB,
1350 MachineLoop *L, LoopFeederMap &LoopFeederPhi) const {
1351 assert(Phi->isPHI() && "Expecting a Phi.");
1352 // Walk through each Phi, and its used operands. Make sure that
1353 // if there is recursion in Phi, we won't generate hardware loops.
1354 for (int i = 1, n = Phi->getNumOperands(); i < n; i += 2)
1355 if (isLoopFeeder(L, MBB, Phi, &(Phi->getOperand(i)), LoopFeederPhi))
1356 if (loopCountMayWrapOrUnderFlow(&(Phi->getOperand(i)), EndVal,
1357 Phi->getParent(), L, LoopFeederPhi))
1362 /// Return true if the induction variable can underflow in the first iteration.
1363 /// An example, is an initial unsigned value that is 0 and is decrement in the
1364 /// first itertion of a do-while loop. In this case, we cannot generate a
1365 /// hardware loop because the endloop instruction does not decrement the loop
1366 /// counter if it is <= 1. We only need to perform this analysis if the
1367 /// initial value is a register.
1369 /// This function assumes the initial value may underfow unless proven
1370 /// otherwise. If the type is signed, then we don't care because signed
1371 /// underflow is undefined. We attempt to prove the initial value is not
1372 /// zero by perfoming a crude analysis of the loop counter. This function
1373 /// checks if the initial value is used in any comparison prior to the loop
1374 /// and, if so, assumes the comparison is a range check. This is inexact,
1375 /// but will catch the simple cases.
1376 bool HexagonHardwareLoops::loopCountMayWrapOrUnderFlow(
1377 const MachineOperand *InitVal, const MachineOperand *EndVal,
1378 MachineBasicBlock *MBB, MachineLoop *L,
1379 LoopFeederMap &LoopFeederPhi) const {
1380 // Only check register values since they are unknown.
1381 if (!InitVal->isReg())
1384 if (!EndVal->isImm())
1387 // A register value that is assigned an immediate is a known value, and it
1388 // won't underflow in the first iteration.
1390 if (checkForImmediate(*InitVal, Imm))
1391 return (EndVal->getImm() == Imm);
1393 unsigned Reg = InitVal->getReg();
1395 // We don't know the value of a physical register.
1396 if (!TargetRegisterInfo::isVirtualRegister(Reg))
1399 MachineInstr *Def = MRI->getVRegDef(Reg);
1403 // If the initial value is a Phi or copy and the operands may not underflow,
1404 // then the definition cannot be underflow either.
1405 if (Def->isPHI() && !phiMayWrapOrUnderflow(Def, EndVal, Def->getParent(),
1408 if (Def->isCopy() && !loopCountMayWrapOrUnderFlow(&(Def->getOperand(1)),
1409 EndVal, Def->getParent(),
1413 // Iterate over the uses of the initial value. If the initial value is used
1414 // in a compare, then we assume this is a range check that ensures the loop
1415 // doesn't underflow. This is not an exact test and should be improved.
1416 for (MachineRegisterInfo::use_instr_nodbg_iterator I = MRI->use_instr_nodbg_begin(Reg),
1417 E = MRI->use_instr_nodbg_end(); I != E; ++I) {
1418 MachineInstr *MI = &*I;
1419 unsigned CmpReg1 = 0, CmpReg2 = 0;
1420 int CmpMask = 0, CmpValue = 0;
1422 if (!TII->analyzeCompare(MI, CmpReg1, CmpReg2, CmpMask, CmpValue))
1425 MachineBasicBlock *TBB = 0, *FBB = 0;
1426 SmallVector<MachineOperand, 2> Cond;
1427 if (TII->AnalyzeBranch(*MI->getParent(), TBB, FBB, Cond, false))
1430 Comparison::Kind Cmp = getComparisonKind(MI->getOpcode(), 0, 0, 0);
1433 if (TII->predOpcodeHasNot(Cond) ^ (TBB != MBB))
1434 Cmp = Comparison::getNegatedComparison(Cmp);
1435 if (CmpReg2 != 0 && CmpReg2 == Reg)
1436 Cmp = Comparison::getSwappedComparison(Cmp);
1438 // Signed underflow is undefined.
1439 if (Comparison::isSigned(Cmp))
1442 // Check if there is a comparison of the inital value. If the initial value
1443 // is greater than or not equal to another value, then assume this is a
1445 if ((Cmp & Comparison::G) || Cmp == Comparison::NE)
1449 // OK - this is a hack that needs to be improved. We really need to analyze
1450 // the instructions performed on the initial value. This works on the simplest
1452 if (!Def->isCopy() && !Def->isPHI())
1458 bool HexagonHardwareLoops::checkForImmediate(const MachineOperand &MO,
1459 int64_t &Val) const {
1467 // MO is a register. Check whether it is defined as an immediate value,
1468 // and if so, get the value of it in TV. That value will then need to be
1469 // processed to handle potential subregisters in MO.
1472 unsigned R = MO.getReg();
1473 if (!TargetRegisterInfo::isVirtualRegister(R))
1475 MachineInstr *DI = MRI->getVRegDef(R);
1476 unsigned DOpc = DI->getOpcode();
1478 case TargetOpcode::COPY:
1479 case Hexagon::A2_tfrsi:
1480 case Hexagon::A2_tfrpi:
1481 case Hexagon::CONST32_Int_Real:
1482 case Hexagon::CONST64_Int_Real: {
1483 // Call recursively to avoid an extra check whether operand(1) is
1484 // indeed an immediate (it could be a global address, for example),
1485 // plus we can handle COPY at the same time.
1486 if (!checkForImmediate(DI->getOperand(1), TV))
1490 case Hexagon::A2_combineii:
1491 case Hexagon::A4_combineir:
1492 case Hexagon::A4_combineii:
1493 case Hexagon::A4_combineri:
1494 case Hexagon::A2_combinew: {
1495 const MachineOperand &S1 = DI->getOperand(1);
1496 const MachineOperand &S2 = DI->getOperand(2);
1498 if (!checkForImmediate(S1, V1) || !checkForImmediate(S2, V2))
1500 TV = V2 | (V1 << 32);
1503 case TargetOpcode::REG_SEQUENCE: {
1504 const MachineOperand &S1 = DI->getOperand(1);
1505 const MachineOperand &S3 = DI->getOperand(3);
1507 if (!checkForImmediate(S1, V1) || !checkForImmediate(S3, V3))
1509 unsigned Sub2 = DI->getOperand(2).getImm();
1510 unsigned Sub4 = DI->getOperand(4).getImm();
1511 if (Sub2 == Hexagon::subreg_loreg && Sub4 == Hexagon::subreg_hireg)
1512 TV = V1 | (V3 << 32);
1513 else if (Sub2 == Hexagon::subreg_hireg && Sub4 == Hexagon::subreg_loreg)
1514 TV = V3 | (V1 << 32);
1516 llvm_unreachable("Unexpected form of REG_SEQUENCE");
1524 // By now, we should have successfuly obtained the immediate value defining
1525 // the register referenced in MO. Handle a potential use of a subregister.
1526 switch (MO.getSubReg()) {
1527 case Hexagon::subreg_loreg:
1528 Val = TV & 0xFFFFFFFFULL;
1530 case Hexagon::subreg_hireg:
1531 Val = (TV >> 32) & 0xFFFFFFFFULL;
1540 void HexagonHardwareLoops::setImmediate(MachineOperand &MO, int64_t Val) {
1547 unsigned R = MO.getReg();
1548 MachineInstr *DI = MRI->getVRegDef(R);
1550 const TargetRegisterClass *RC = MRI->getRegClass(R);
1551 unsigned NewR = MRI->createVirtualRegister(RC);
1552 MachineBasicBlock &B = *DI->getParent();
1553 DebugLoc DL = DI->getDebugLoc();
1554 BuildMI(B, DI, DL, TII->get(DI->getOpcode()), NewR).addImm(Val);
1558 static bool isImmValidForOpcode(unsigned CmpOpc, int64_t Imm) {
1559 // These two instructions are not extendable.
1560 if (CmpOpc == Hexagon::A4_cmpbeqi)
1561 return isUInt<8>(Imm);
1562 if (CmpOpc == Hexagon::A4_cmpbgti)
1563 return isInt<8>(Imm);
1564 // The rest of the comparison-with-immediate instructions are extendable.
1568 bool HexagonHardwareLoops::fixupInductionVariable(MachineLoop *L) {
1569 MachineBasicBlock *Header = L->getHeader();
1570 MachineBasicBlock *Latch = L->getLoopLatch();
1571 MachineBasicBlock *ExitingBlock = getExitingBlock(L);
1573 if (!(Header && Latch && ExitingBlock))
1576 // These data structures follow the same concept as the corresponding
1577 // ones in findInductionRegister (where some comments are).
1578 typedef std::pair<unsigned,int64_t> RegisterBump;
1579 typedef std::pair<unsigned,RegisterBump> RegisterInduction;
1580 typedef std::set<RegisterInduction> RegisterInductionSet;
1582 // Register candidates for induction variables, with their associated bumps.
1583 RegisterInductionSet IndRegs;
1585 // Look for induction patterns:
1586 // vreg1 = PHI ..., [ latch, vreg2 ]
1587 // vreg2 = ADD vreg1, imm
1588 typedef MachineBasicBlock::instr_iterator instr_iterator;
1589 for (instr_iterator I = Header->instr_begin(), E = Header->instr_end();
1590 I != E && I->isPHI(); ++I) {
1591 MachineInstr *Phi = &*I;
1593 // Have a PHI instruction.
1594 for (unsigned i = 1, n = Phi->getNumOperands(); i < n; i += 2) {
1595 if (Phi->getOperand(i+1).getMBB() != Latch)
1598 unsigned PhiReg = Phi->getOperand(i).getReg();
1599 MachineInstr *DI = MRI->getVRegDef(PhiReg);
1600 unsigned UpdOpc = DI->getOpcode();
1601 bool isAdd = (UpdOpc == Hexagon::A2_addi || UpdOpc == Hexagon::A2_addp);
1604 // If the register operand to the add/sub is the PHI we are looking
1605 // at, this meets the induction pattern.
1606 unsigned IndReg = DI->getOperand(1).getReg();
1607 MachineOperand &Opnd2 = DI->getOperand(2);
1609 if (MRI->getVRegDef(IndReg) == Phi && checkForImmediate(Opnd2, V)) {
1610 unsigned UpdReg = DI->getOperand(0).getReg();
1611 IndRegs.insert(std::make_pair(UpdReg, std::make_pair(IndReg, V)));
1617 if (IndRegs.empty())
1620 MachineBasicBlock *TB = nullptr, *FB = nullptr;
1621 SmallVector<MachineOperand,2> Cond;
1622 // AnalyzeBranch returns true if it fails to analyze branch.
1623 bool NotAnalyzed = TII->AnalyzeBranch(*ExitingBlock, TB, FB, Cond, false);
1624 if (NotAnalyzed || Cond.empty())
1627 if (ExitingBlock != Latch && (TB == Latch || FB == Latch)) {
1628 MachineBasicBlock *LTB = 0, *LFB = 0;
1629 SmallVector<MachineOperand,2> LCond;
1630 bool NotAnalyzed = TII->AnalyzeBranch(*Latch, LTB, LFB, LCond, false);
1634 // Since latch is not the exiting block, the latch branch should be an
1635 // unconditional branch to the loop header.
1637 TB = (LTB == Header) ? LTB : LFB;
1639 FB = (LTB == Header) ? LTB : LFB;
1643 // The latch/exit block does not go back to the header.
1646 // FB is the header (i.e., uncond. jump to branch header)
1647 // In this case, the LoopBody -> TB should not be a back edge otherwise
1648 // it could result in an infinite loop after conversion to hw_loop.
1649 // This case can happen when the Latch has two jumps like this:
1650 // Jmp_c OuterLoopHeader <-- TB
1651 // Jmp InnerLoopHeader <-- FB
1652 if (MDT->dominates(TB, FB))
1656 // Expecting a predicate register as a condition. It won't be a hardware
1657 // predicate register at this point yet, just a vreg.
1658 // HexagonInstrInfo::AnalyzeBranch for negated branches inserts imm(0)
1659 // into Cond, followed by the predicate register. For non-negated branches
1660 // it's just the register.
1661 unsigned CSz = Cond.size();
1662 if (CSz != 1 && CSz != 2)
1665 if (!Cond[CSz-1].isReg())
1668 unsigned P = Cond[CSz-1].getReg();
1669 MachineInstr *PredDef = MRI->getVRegDef(P);
1671 if (!PredDef->isCompare())
1674 SmallSet<unsigned,2> CmpRegs;
1675 MachineOperand *CmpImmOp = nullptr;
1677 // Go over all operands to the compare and look for immediate and register
1678 // operands. Assume that if the compare has a single register use and a
1679 // single immediate operand, then the register is being compared with the
1681 for (unsigned i = 0, n = PredDef->getNumOperands(); i < n; ++i) {
1682 MachineOperand &MO = PredDef->getOperand(i);
1684 // Skip all implicit references. In one case there was:
1685 // %vreg140<def> = FCMPUGT32_rr %vreg138, %vreg139, %USR<imp-use>
1686 if (MO.isImplicit())
1689 if (!isImmediate(MO)) {
1690 CmpRegs.insert(MO.getReg());
1693 // Consider the register to be the "immediate" operand.
1698 } else if (MO.isImm()) {
1699 if (CmpImmOp) // A second immediate argument? Confusing. Bail out.
1705 if (CmpRegs.empty())
1708 // Check if the compared register follows the order we want. Fix if needed.
1709 for (RegisterInductionSet::iterator I = IndRegs.begin(), E = IndRegs.end();
1711 // This is a success. If the register used in the comparison is one that
1712 // we have identified as a bumped (updated) induction register, there is
1714 if (CmpRegs.count(I->first))
1717 // Otherwise, if the register being compared comes out of a PHI node,
1718 // and has been recognized as following the induction pattern, and is
1719 // compared against an immediate, we can fix it.
1720 const RegisterBump &RB = I->second;
1721 if (CmpRegs.count(RB.first)) {
1723 // If both operands to the compare instruction are registers, see if
1724 // it can be changed to use induction register as one of the operands.
1725 MachineInstr *IndI = nullptr;
1726 MachineInstr *nonIndI = nullptr;
1727 MachineOperand *IndMO = nullptr;
1728 MachineOperand *nonIndMO = nullptr;
1730 for (unsigned i = 1, n = PredDef->getNumOperands(); i < n; ++i) {
1731 MachineOperand &MO = PredDef->getOperand(i);
1732 if (MO.isReg() && MO.getReg() == RB.first) {
1733 DEBUG(dbgs() << "\n DefMI(" << i << ") = "
1734 << *(MRI->getVRegDef(I->first)));
1738 IndI = MRI->getVRegDef(I->first);
1740 } else if (MO.isReg()) {
1741 DEBUG(dbgs() << "\n DefMI(" << i << ") = "
1742 << *(MRI->getVRegDef(MO.getReg())));
1746 nonIndI = MRI->getVRegDef(MO.getReg());
1750 if (IndI && nonIndI &&
1751 nonIndI->getOpcode() == Hexagon::A2_addi &&
1752 nonIndI->getOperand(2).isImm() &&
1753 nonIndI->getOperand(2).getImm() == - RB.second) {
1754 bool Order = orderBumpCompare(IndI, PredDef);
1756 IndMO->setReg(I->first);
1757 nonIndMO->setReg(nonIndI->getOperand(1).getReg());
1764 // It is not valid to do this transformation on an unsigned comparison
1765 // because it may underflow.
1766 Comparison::Kind Cmp = getComparisonKind(PredDef->getOpcode(), 0, 0, 0);
1767 if (!Cmp || Comparison::isUnsigned(Cmp))
1770 // If the register is being compared against an immediate, try changing
1771 // the compare instruction to use induction register and adjust the
1772 // immediate operand.
1773 int64_t CmpImm = getImmediate(*CmpImmOp);
1774 int64_t V = RB.second;
1775 // Handle Overflow (64-bit).
1776 if (((V > 0) && (CmpImm > INT64_MAX - V)) ||
1777 ((V < 0) && (CmpImm < INT64_MIN - V)))
1780 // Most comparisons of register against an immediate value allow
1781 // the immediate to be constant-extended. There are some exceptions
1782 // though. Make sure the new combination will work.
1783 if (CmpImmOp->isImm())
1784 if (!isImmValidForOpcode(PredDef->getOpcode(), CmpImm))
1787 // Make sure that the compare happens after the bump. Otherwise,
1788 // after the fixup, the compare would use a yet-undefined register.
1789 MachineInstr *BumpI = MRI->getVRegDef(I->first);
1790 bool Order = orderBumpCompare(BumpI, PredDef);
1794 // Finally, fix the compare instruction.
1795 setImmediate(*CmpImmOp, CmpImm);
1796 for (unsigned i = 0, n = PredDef->getNumOperands(); i < n; ++i) {
1797 MachineOperand &MO = PredDef->getOperand(i);
1798 if (MO.isReg() && MO.getReg() == RB.first) {
1799 MO.setReg(I->first);
1809 /// \brief Create a preheader for a given loop.
1810 MachineBasicBlock *HexagonHardwareLoops::createPreheaderForLoop(
1812 if (MachineBasicBlock *TmpPH = L->getLoopPreheader())
1815 if (!HWCreatePreheader)
1818 MachineBasicBlock *Header = L->getHeader();
1819 MachineBasicBlock *Latch = L->getLoopLatch();
1820 MachineBasicBlock *ExitingBlock = getExitingBlock(L);
1821 MachineFunction *MF = Header->getParent();
1825 if ((PHFn != "") && (PHFn != MF->getName()))
1829 if (!Latch || !ExitingBlock || Header->hasAddressTaken())
1832 typedef MachineBasicBlock::instr_iterator instr_iterator;
1834 // Verify that all existing predecessors have analyzable branches
1835 // (or no branches at all).
1836 typedef std::vector<MachineBasicBlock*> MBBVector;
1837 MBBVector Preds(Header->pred_begin(), Header->pred_end());
1838 SmallVector<MachineOperand,2> Tmp1;
1839 MachineBasicBlock *TB = nullptr, *FB = nullptr;
1841 if (TII->AnalyzeBranch(*ExitingBlock, TB, FB, Tmp1, false))
1844 for (MBBVector::iterator I = Preds.begin(), E = Preds.end(); I != E; ++I) {
1845 MachineBasicBlock *PB = *I;
1846 bool NotAnalyzed = TII->AnalyzeBranch(*PB, TB, FB, Tmp1, false);
1851 MachineBasicBlock *NewPH = MF->CreateMachineBasicBlock();
1852 MF->insert(Header, NewPH);
1854 if (Header->pred_size() > 2) {
1855 // Ensure that the header has only two predecessors: the preheader and
1856 // the loop latch. Any additional predecessors of the header should
1857 // join at the newly created preheader. Inspect all PHI nodes from the
1858 // header and create appropriate corresponding PHI nodes in the preheader.
1860 for (instr_iterator I = Header->instr_begin(), E = Header->instr_end();
1861 I != E && I->isPHI(); ++I) {
1862 MachineInstr *PN = &*I;
1864 const MCInstrDesc &PD = TII->get(TargetOpcode::PHI);
1865 MachineInstr *NewPN = MF->CreateMachineInstr(PD, DL);
1866 NewPH->insert(NewPH->end(), NewPN);
1868 unsigned PR = PN->getOperand(0).getReg();
1869 const TargetRegisterClass *RC = MRI->getRegClass(PR);
1870 unsigned NewPR = MRI->createVirtualRegister(RC);
1871 NewPN->addOperand(MachineOperand::CreateReg(NewPR, true));
1873 // Copy all non-latch operands of a header's PHI node to the newly
1874 // created PHI node in the preheader.
1875 for (unsigned i = 1, n = PN->getNumOperands(); i < n; i += 2) {
1876 unsigned PredR = PN->getOperand(i).getReg();
1877 unsigned PredRSub = PN->getOperand(i).getSubReg();
1878 MachineBasicBlock *PredB = PN->getOperand(i+1).getMBB();
1882 MachineOperand MO = MachineOperand::CreateReg(PredR, false);
1883 MO.setSubReg(PredRSub);
1884 NewPN->addOperand(MO);
1885 NewPN->addOperand(MachineOperand::CreateMBB(PredB));
1888 // Remove copied operands from the old PHI node and add the value
1889 // coming from the preheader's PHI.
1890 for (int i = PN->getNumOperands()-2; i > 0; i -= 2) {
1891 MachineBasicBlock *PredB = PN->getOperand(i+1).getMBB();
1892 if (PredB != Latch) {
1893 PN->RemoveOperand(i+1);
1894 PN->RemoveOperand(i);
1897 PN->addOperand(MachineOperand::CreateReg(NewPR, false));
1898 PN->addOperand(MachineOperand::CreateMBB(NewPH));
1902 assert(Header->pred_size() == 2);
1904 // The header has only two predecessors, but the non-latch predecessor
1905 // is not a preheader (e.g. it has other successors, etc.)
1906 // In such a case we don't need any extra PHI nodes in the new preheader,
1907 // all we need is to adjust existing PHIs in the header to now refer to
1908 // the new preheader.
1909 for (instr_iterator I = Header->instr_begin(), E = Header->instr_end();
1910 I != E && I->isPHI(); ++I) {
1911 MachineInstr *PN = &*I;
1912 for (unsigned i = 1, n = PN->getNumOperands(); i < n; i += 2) {
1913 MachineOperand &MO = PN->getOperand(i+1);
1914 if (MO.getMBB() != Latch)
1920 // "Reroute" the CFG edges to link in the new preheader.
1921 // If any of the predecessors falls through to the header, insert a branch
1922 // to the new preheader in that place.
1923 SmallVector<MachineOperand,1> Tmp2;
1924 SmallVector<MachineOperand,1> EmptyCond;
1928 for (MBBVector::iterator I = Preds.begin(), E = Preds.end(); I != E; ++I) {
1929 MachineBasicBlock *PB = *I;
1932 bool NotAnalyzed = TII->AnalyzeBranch(*PB, TB, FB, Tmp2, false);
1933 (void)NotAnalyzed; // suppress compiler warning
1934 assert (!NotAnalyzed && "Should be analyzable!");
1935 if (TB != Header && (Tmp2.empty() || FB != Header))
1936 TII->InsertBranch(*PB, NewPH, nullptr, EmptyCond, DL);
1937 PB->ReplaceUsesOfBlockWith(Header, NewPH);
1941 // It can happen that the latch block will fall through into the header.
1942 // Insert an unconditional branch to the header.
1944 bool LatchNotAnalyzed = TII->AnalyzeBranch(*Latch, TB, FB, Tmp2, false);
1945 (void)LatchNotAnalyzed; // suppress compiler warning
1946 assert (!LatchNotAnalyzed && "Should be analyzable!");
1948 TII->InsertBranch(*Latch, Header, nullptr, EmptyCond, DL);
1950 // Finally, the branch from the preheader to the header.
1951 TII->InsertBranch(*NewPH, Header, nullptr, EmptyCond, DL);
1952 NewPH->addSuccessor(Header);
1954 MachineLoop *ParentLoop = L->getParentLoop();
1956 ParentLoop->addBasicBlockToLoop(NewPH, MLI->getBase());
1958 // Update the dominator information with the new preheader.
1960 MachineDomTreeNode *HDom = MDT->getNode(Header);
1961 MDT->addNewBlock(NewPH, HDom->getIDom()->getBlock());
1962 MDT->changeImmediateDominator(Header, NewPH);