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);
99 /// Kinds of comparisons in the compare instructions.
117 static Kind getSwappedComparison(Kind Cmp) {
118 assert ((!((Cmp & L) && (Cmp & G))) && "Malformed comparison operator");
119 if ((Cmp & L) || (Cmp & G))
120 return (Kind)(Cmp ^ (L|G));
124 static Kind getNegatedComparison(Kind Cmp) {
125 if ((Cmp & L) || (Cmp & G))
126 return (Kind)((Cmp ^ (L | G)) ^ EQ);
127 if ((Cmp & NE) || (Cmp & EQ))
128 return (Kind)(Cmp ^ (EQ | NE));
132 static bool isSigned(Kind Cmp) {
133 return (Cmp & (L | G) && !(Cmp & U));
136 static bool isUnsigned(Kind Cmp) {
142 /// \brief Find the register that contains the loop controlling
143 /// induction variable.
144 /// If successful, it will return true and set the \p Reg, \p IVBump
145 /// and \p IVOp arguments. Otherwise it will return false.
146 /// The returned induction register is the register R that follows the
147 /// following induction pattern:
149 /// R = phi ..., [ R.next, LatchBlock ]
150 /// R.next = R + #bump
151 /// if (R.next < #N) goto loop
152 /// IVBump is the immediate value added to R, and IVOp is the instruction
153 /// "R.next = R + #bump".
154 bool findInductionRegister(MachineLoop *L, unsigned &Reg,
155 int64_t &IVBump, MachineInstr *&IVOp) const;
157 /// \brief Return the comparison kind for the specified opcode.
158 Comparison::Kind getComparisonKind(unsigned CondOpc,
159 MachineOperand *InitialValue,
160 const MachineOperand *Endvalue,
161 int64_t IVBump) const;
163 /// \brief Analyze the statements in a loop to determine if the loop
164 /// has a computable trip count and, if so, return a value that represents
165 /// the trip count expression.
166 CountValue *getLoopTripCount(MachineLoop *L,
167 SmallVectorImpl<MachineInstr *> &OldInsts);
169 /// \brief Return the expression that represents the number of times
170 /// a loop iterates. The function takes the operands that represent the
171 /// loop start value, loop end value, and induction value. Based upon
172 /// these operands, the function attempts to compute the trip count.
173 /// If the trip count is not directly available (as an immediate value,
174 /// or a register), the function will attempt to insert computation of it
175 /// to the loop's preheader.
176 CountValue *computeCount(MachineLoop *Loop, const MachineOperand *Start,
177 const MachineOperand *End, unsigned IVReg,
178 int64_t IVBump, Comparison::Kind Cmp) const;
180 /// \brief Return true if the instruction is not valid within a hardware
182 bool isInvalidLoopOperation(const MachineInstr *MI) const;
184 /// \brief Return true if the loop contains an instruction that inhibits
185 /// using the hardware loop.
186 bool containsInvalidInstruction(MachineLoop *L) const;
188 /// \brief Given a loop, check if we can convert it to a hardware loop.
189 /// If so, then perform the conversion and return true.
190 bool convertToHardwareLoop(MachineLoop *L);
192 /// \brief Return true if the instruction is now dead.
193 bool isDead(const MachineInstr *MI,
194 SmallVectorImpl<MachineInstr *> &DeadPhis) const;
196 /// \brief Remove the instruction if it is now dead.
197 void removeIfDead(MachineInstr *MI);
199 /// \brief Make sure that the "bump" instruction executes before the
200 /// compare. We need that for the IV fixup, so that the compare
201 /// instruction would not use a bumped value that has not yet been
202 /// defined. If the instructions are out of order, try to reorder them.
203 bool orderBumpCompare(MachineInstr *BumpI, MachineInstr *CmpI);
205 /// \brief Get the instruction that loads an immediate value into \p R,
206 /// or 0 if such an instruction does not exist.
207 MachineInstr *defWithImmediate(unsigned R);
209 /// \brief Get the immediate value referenced to by \p MO, either for
210 /// immediate operands, or for register operands, where the register
211 /// was defined with an immediate value.
212 int64_t getImmediate(MachineOperand &MO);
214 /// \brief Reset the given machine operand to now refer to a new immediate
215 /// value. Assumes that the operand was already referencing an immediate
216 /// value, either directly, or via a register.
217 void setImmediate(MachineOperand &MO, int64_t Val);
219 /// \brief Fix the data flow of the induction varible.
220 /// The desired flow is: phi ---> bump -+-> comparison-in-latch.
223 /// where "bump" is the increment of the induction variable:
224 /// iv = iv + #const.
225 /// Due to some prior code transformations, the actual flow may look
227 /// phi -+-> bump ---> back to phi
229 /// +-> comparison-in-latch (against upper_bound-bump),
230 /// i.e. the comparison that controls the loop execution may be using
231 /// the value of the induction variable from before the increment.
233 /// Return true if the loop's flow is the desired one (i.e. it's
234 /// either been fixed, or no fixing was necessary).
235 /// Otherwise, return false. This can happen if the induction variable
236 /// couldn't be identified, or if the value in the latch's comparison
237 /// cannot be adjusted to reflect the post-bump value.
238 bool fixupInductionVariable(MachineLoop *L);
240 /// \brief Given a loop, if it does not have a preheader, create one.
241 /// Return the block that is the preheader.
242 MachineBasicBlock *createPreheaderForLoop(MachineLoop *L);
245 char HexagonHardwareLoops::ID = 0;
247 int HexagonHardwareLoops::Counter = 0;
250 /// \brief Abstraction for a trip count of a loop. A smaller version
251 /// of the MachineOperand class without the concerns of changing the
252 /// operand representation.
255 enum CountValueType {
270 explicit CountValue(CountValueType t, unsigned v, unsigned u = 0) {
272 if (Kind == CV_Register) {
279 bool isReg() const { return Kind == CV_Register; }
280 bool isImm() const { return Kind == CV_Immediate; }
282 unsigned getReg() const {
283 assert(isReg() && "Wrong CountValue accessor");
284 return Contents.R.Reg;
286 unsigned getSubReg() const {
287 assert(isReg() && "Wrong CountValue accessor");
288 return Contents.R.Sub;
290 unsigned getImm() const {
291 assert(isImm() && "Wrong CountValue accessor");
292 return Contents.ImmVal;
295 void print(raw_ostream &OS, const TargetRegisterInfo *TRI = nullptr) const {
296 if (isReg()) { OS << PrintReg(Contents.R.Reg, TRI, Contents.R.Sub); }
297 if (isImm()) { OS << Contents.ImmVal; }
300 } // end anonymous namespace
303 INITIALIZE_PASS_BEGIN(HexagonHardwareLoops, "hwloops",
304 "Hexagon Hardware Loops", false, false)
305 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
306 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
307 INITIALIZE_PASS_END(HexagonHardwareLoops, "hwloops",
308 "Hexagon Hardware Loops", false, false)
311 /// \brief Returns true if the instruction is a hardware loop instruction.
312 static bool isHardwareLoop(const MachineInstr *MI) {
313 return MI->getOpcode() == Hexagon::J2_loop0r ||
314 MI->getOpcode() == Hexagon::J2_loop0i;
317 FunctionPass *llvm::createHexagonHardwareLoops() {
318 return new HexagonHardwareLoops();
322 bool HexagonHardwareLoops::runOnMachineFunction(MachineFunction &MF) {
323 DEBUG(dbgs() << "********* Hexagon Hardware Loops *********\n");
325 bool Changed = false;
327 MLI = &getAnalysis<MachineLoopInfo>();
328 MRI = &MF.getRegInfo();
329 MDT = &getAnalysis<MachineDominatorTree>();
330 TII = MF.getSubtarget<HexagonSubtarget>().getInstrInfo();
332 for (MachineLoopInfo::iterator I = MLI->begin(), E = MLI->end();
335 if (!L->getParentLoop())
336 Changed |= convertToHardwareLoop(L);
342 /// \brief Return the latch block if it's one of the exiting blocks. Otherwise,
343 /// return the exiting block. Return 'null' when multiple exiting blocks are
345 static MachineBasicBlock* getExitingBlock(MachineLoop *L) {
346 if (MachineBasicBlock *Latch = L->getLoopLatch()) {
347 if (L->isLoopExiting(Latch))
350 return L->getExitingBlock();
355 bool HexagonHardwareLoops::findInductionRegister(MachineLoop *L,
360 MachineBasicBlock *Header = L->getHeader();
361 MachineBasicBlock *Preheader = L->getLoopPreheader();
362 MachineBasicBlock *Latch = L->getLoopLatch();
363 MachineBasicBlock *ExitingBlock = getExitingBlock(L);
364 if (!Header || !Preheader || !Latch || !ExitingBlock)
367 // This pair represents an induction register together with an immediate
368 // value that will be added to it in each loop iteration.
369 typedef std::pair<unsigned,int64_t> RegisterBump;
371 // Mapping: R.next -> (R, bump), where R, R.next and bump are derived
372 // from an induction operation
374 // where bump is an immediate value.
375 typedef std::map<unsigned,RegisterBump> InductionMap;
379 typedef MachineBasicBlock::instr_iterator instr_iterator;
380 for (instr_iterator I = Header->instr_begin(), E = Header->instr_end();
381 I != E && I->isPHI(); ++I) {
382 MachineInstr *Phi = &*I;
384 // Have a PHI instruction. Get the operand that corresponds to the
385 // latch block, and see if is a result of an addition of form "reg+imm",
386 // where the "reg" is defined by the PHI node we are looking at.
387 for (unsigned i = 1, n = Phi->getNumOperands(); i < n; i += 2) {
388 if (Phi->getOperand(i+1).getMBB() != Latch)
391 unsigned PhiOpReg = Phi->getOperand(i).getReg();
392 MachineInstr *DI = MRI->getVRegDef(PhiOpReg);
393 unsigned UpdOpc = DI->getOpcode();
394 bool isAdd = (UpdOpc == Hexagon::A2_addi);
397 // If the register operand to the add is the PHI we're
398 // looking at, this meets the induction pattern.
399 unsigned IndReg = DI->getOperand(1).getReg();
400 if (MRI->getVRegDef(IndReg) == Phi) {
401 unsigned UpdReg = DI->getOperand(0).getReg();
402 int64_t V = DI->getOperand(2).getImm();
403 IndMap.insert(std::make_pair(UpdReg, std::make_pair(IndReg, V)));
409 SmallVector<MachineOperand,2> Cond;
410 MachineBasicBlock *TB = nullptr, *FB = nullptr;
411 bool NotAnalyzed = TII->AnalyzeBranch(*ExitingBlock, TB, FB, Cond, false);
415 unsigned PredR, PredPos, PredRegFlags;
416 if (!TII->getPredReg(Cond, PredR, PredPos, PredRegFlags))
419 MachineInstr *PredI = MRI->getVRegDef(PredR);
420 if (!PredI->isCompare())
423 unsigned CmpReg1 = 0, CmpReg2 = 0;
424 int CmpImm = 0, CmpMask = 0;
425 bool CmpAnalyzed = TII->analyzeCompare(PredI, CmpReg1, CmpReg2,
427 // Fail if the compare was not analyzed, or it's not comparing a register
428 // with an immediate value. Not checking the mask here, since we handle
429 // the individual compare opcodes (including A4_cmpb*) later on.
433 // Exactly one of the input registers to the comparison should be among
434 // the induction registers.
435 InductionMap::iterator IndMapEnd = IndMap.end();
436 InductionMap::iterator F = IndMapEnd;
438 InductionMap::iterator F1 = IndMap.find(CmpReg1);
443 InductionMap::iterator F2 = IndMap.find(CmpReg2);
444 if (F2 != IndMapEnd) {
453 Reg = F->second.first;
454 IVBump = F->second.second;
455 IVOp = MRI->getVRegDef(F->first);
459 // Return the comparison kind for the specified opcode.
460 HexagonHardwareLoops::Comparison::Kind
461 HexagonHardwareLoops::getComparisonKind(unsigned CondOpc,
462 MachineOperand *InitialValue,
463 const MachineOperand *EndValue,
464 int64_t IVBump) const {
465 Comparison::Kind Cmp = (Comparison::Kind)0;
467 case Hexagon::C2_cmpeqi:
468 case Hexagon::C2_cmpeq:
469 case Hexagon::C2_cmpeqp:
470 Cmp = Comparison::Kind::EQ;
472 case Hexagon::C4_cmpneq:
473 case Hexagon::C4_cmpneqi:
474 Cmp = Comparison::Kind::NE;
476 case Hexagon::C4_cmplte:
477 Cmp = Comparison::Kind::LEs;
479 case Hexagon::C4_cmplteu:
480 Cmp = Comparison::Kind::LEu;
482 case Hexagon::C2_cmpgtui:
483 case Hexagon::C2_cmpgtu:
484 case Hexagon::C2_cmpgtup:
485 Cmp = Comparison::Kind::GTu;
487 case Hexagon::C2_cmpgti:
488 case Hexagon::C2_cmpgt:
489 case Hexagon::C2_cmpgtp:
490 Cmp = Comparison::Kind::GTs;
493 return (Comparison::Kind)0;
498 /// \brief Analyze the statements in a loop to determine if the loop has
499 /// a computable trip count and, if so, return a value that represents
500 /// the trip count expression.
502 /// This function iterates over the phi nodes in the loop to check for
503 /// induction variable patterns that are used in the calculation for
504 /// the number of time the loop is executed.
505 CountValue *HexagonHardwareLoops::getLoopTripCount(MachineLoop *L,
506 SmallVectorImpl<MachineInstr *> &OldInsts) {
507 MachineBasicBlock *TopMBB = L->getTopBlock();
508 MachineBasicBlock::pred_iterator PI = TopMBB->pred_begin();
509 assert(PI != TopMBB->pred_end() &&
510 "Loop must have more than one incoming edge!");
511 MachineBasicBlock *Backedge = *PI++;
512 if (PI == TopMBB->pred_end()) // dead loop?
514 MachineBasicBlock *Incoming = *PI++;
515 if (PI != TopMBB->pred_end()) // multiple backedges?
518 // Make sure there is one incoming and one backedge and determine which
520 if (L->contains(Incoming)) {
521 if (L->contains(Backedge))
523 std::swap(Incoming, Backedge);
524 } else if (!L->contains(Backedge))
527 // Look for the cmp instruction to determine if we can get a useful trip
528 // count. The trip count can be either a register or an immediate. The
529 // location of the value depends upon the type (reg or imm).
530 MachineBasicBlock *ExitingBlock = getExitingBlock(L);
537 bool FoundIV = findInductionRegister(L, IVReg, IVBump, IVOp);
541 MachineBasicBlock *Preheader = L->getLoopPreheader();
543 MachineOperand *InitialValue = nullptr;
544 MachineInstr *IV_Phi = MRI->getVRegDef(IVReg);
545 MachineBasicBlock *Latch = L->getLoopLatch();
546 for (unsigned i = 1, n = IV_Phi->getNumOperands(); i < n; i += 2) {
547 MachineBasicBlock *MBB = IV_Phi->getOperand(i+1).getMBB();
548 if (MBB == Preheader)
549 InitialValue = &IV_Phi->getOperand(i);
550 else if (MBB == Latch)
551 IVReg = IV_Phi->getOperand(i).getReg(); // Want IV reg after bump.
556 SmallVector<MachineOperand,2> Cond;
557 MachineBasicBlock *TB = nullptr, *FB = nullptr;
558 bool NotAnalyzed = TII->AnalyzeBranch(*ExitingBlock, TB, FB, Cond, false);
562 MachineBasicBlock *Header = L->getHeader();
563 // TB must be non-null. If FB is also non-null, one of them must be
564 // the header. Otherwise, branch to TB could be exiting the loop, and
565 // the fall through can go to the header.
566 assert (TB && "Exit block without a branch?");
567 if (ExitingBlock != Latch && (TB == Latch || FB == Latch)) {
568 MachineBasicBlock *LTB = 0, *LFB = 0;
569 SmallVector<MachineOperand,2> LCond;
570 bool NotAnalyzed = TII->AnalyzeBranch(*Latch, LTB, LFB, LCond, false);
574 TB = (LTB == Header) ? LTB : LFB;
576 FB = (LTB == Header) ? LTB: LFB;
578 assert ((!FB || TB == Header || FB == Header) && "Branches not to header?");
579 if (!TB || (FB && TB != Header && FB != Header))
582 // Branches of form "if (!P) ..." cause HexagonInstrInfo::AnalyzeBranch
583 // to put imm(0), followed by P in the vector Cond.
584 // If TB is not the header, it means that the "not-taken" path must lead
586 bool Negated = TII->predOpcodeHasNot(Cond) ^ (TB != Header);
587 unsigned PredReg, PredPos, PredRegFlags;
588 if (!TII->getPredReg(Cond, PredReg, PredPos, PredRegFlags))
590 MachineInstr *CondI = MRI->getVRegDef(PredReg);
591 unsigned CondOpc = CondI->getOpcode();
593 unsigned CmpReg1 = 0, CmpReg2 = 0;
594 int Mask = 0, ImmValue = 0;
595 bool AnalyzedCmp = TII->analyzeCompare(CondI, CmpReg1, CmpReg2,
600 // The comparison operator type determines how we compute the loop
602 OldInsts.push_back(CondI);
603 OldInsts.push_back(IVOp);
605 // Sadly, the following code gets information based on the position
606 // of the operands in the compare instruction. This has to be done
607 // this way, because the comparisons check for a specific relationship
608 // between the operands (e.g. is-less-than), rather than to find out
609 // what relationship the operands are in (as on PPC).
610 Comparison::Kind Cmp;
611 bool isSwapped = false;
612 const MachineOperand &Op1 = CondI->getOperand(1);
613 const MachineOperand &Op2 = CondI->getOperand(2);
614 const MachineOperand *EndValue = nullptr;
617 if (Op2.isImm() || Op1.getReg() == IVReg)
628 Cmp = getComparisonKind(CondOpc, InitialValue, EndValue, IVBump);
632 Cmp = Comparison::getNegatedComparison(Cmp);
634 Cmp = Comparison::getSwappedComparison(Cmp);
636 if (InitialValue->isReg()) {
637 unsigned R = InitialValue->getReg();
638 MachineBasicBlock *DefBB = MRI->getVRegDef(R)->getParent();
639 if (!MDT->properlyDominates(DefBB, Header))
641 OldInsts.push_back(MRI->getVRegDef(R));
643 if (EndValue->isReg()) {
644 unsigned R = EndValue->getReg();
645 MachineBasicBlock *DefBB = MRI->getVRegDef(R)->getParent();
646 if (!MDT->properlyDominates(DefBB, Header))
650 return computeCount(L, InitialValue, EndValue, IVReg, IVBump, Cmp);
653 /// \brief Helper function that returns the expression that represents the
654 /// number of times a loop iterates. The function takes the operands that
655 /// represent the loop start value, loop end value, and induction value.
656 /// Based upon these operands, the function attempts to compute the trip count.
657 CountValue *HexagonHardwareLoops::computeCount(MachineLoop *Loop,
658 const MachineOperand *Start,
659 const MachineOperand *End,
662 Comparison::Kind Cmp) const {
663 // Cannot handle comparison EQ, i.e. while (A == B).
664 if (Cmp == Comparison::EQ)
667 // Check if either the start or end values are an assignment of an immediate.
668 // If so, use the immediate value rather than the register.
669 if (Start->isReg()) {
670 const MachineInstr *StartValInstr = MRI->getVRegDef(Start->getReg());
671 if (StartValInstr && StartValInstr->getOpcode() == Hexagon::A2_tfrsi)
672 Start = &StartValInstr->getOperand(1);
675 const MachineInstr *EndValInstr = MRI->getVRegDef(End->getReg());
676 if (EndValInstr && EndValInstr->getOpcode() == Hexagon::A2_tfrsi)
677 End = &EndValInstr->getOperand(1);
680 assert (Start->isReg() || Start->isImm());
681 assert (End->isReg() || End->isImm());
683 bool CmpLess = Cmp & Comparison::L;
684 bool CmpGreater = Cmp & Comparison::G;
685 bool CmpHasEqual = Cmp & Comparison::EQ;
687 // Avoid certain wrap-arounds. This doesn't detect all wrap-arounds.
688 if (CmpLess && IVBump < 0)
689 // Loop going while iv is "less" with the iv value going down. Must wrap.
692 // If loop executes while iv is "greater" with the iv value going up, then
694 if (CmpGreater && IVBump > 0)
695 // Loop going while iv is "greater" with the iv value going up. Must wrap.
698 if (Start->isImm() && End->isImm()) {
699 // Both, start and end are immediates.
700 int64_t StartV = Start->getImm();
701 int64_t EndV = End->getImm();
702 int64_t Dist = EndV - StartV;
706 bool Exact = (Dist % IVBump) == 0;
708 if (Cmp == Comparison::NE) {
711 if ((Dist < 0) ^ (IVBump < 0))
715 // For comparisons that include the final value (i.e. include equality
716 // with the final value), we need to increase the distance by 1.
718 Dist = Dist > 0 ? Dist+1 : Dist-1;
720 // assert (CmpLess => Dist > 0);
721 assert ((!CmpLess || Dist > 0) && "Loop should never iterate!");
722 // assert (CmpGreater => Dist < 0);
723 assert ((!CmpGreater || Dist < 0) && "Loop should never iterate!");
725 // "Normalized" distance, i.e. with the bump set to +-1.
726 int64_t Dist1 = (IVBump > 0) ? (Dist + (IVBump-1)) / IVBump
727 : (-Dist + (-IVBump-1)) / (-IVBump);
728 assert (Dist1 > 0 && "Fishy thing. Both operands have the same sign.");
730 uint64_t Count = Dist1;
732 if (Count > 0xFFFFFFFFULL)
735 return new CountValue(CountValue::CV_Immediate, Count);
738 // A general case: Start and End are some values, but the actual
739 // iteration count may not be available. If it is not, insert
740 // a computation of it into the preheader.
742 // If the induction variable bump is not a power of 2, quit.
743 // Othwerise we'd need a general integer division.
744 if (!isPowerOf2_64(std::abs(IVBump)))
747 MachineBasicBlock *PH = Loop->getLoopPreheader();
748 assert (PH && "Should have a preheader by now");
749 MachineBasicBlock::iterator InsertPos = PH->getFirstTerminator();
751 if (InsertPos != PH->end())
752 InsertPos->getDebugLoc();
754 // If Start is an immediate and End is a register, the trip count
755 // will be "reg - imm". Hexagon's "subtract immediate" instruction
756 // is actually "reg + -imm".
758 // If the loop IV is going downwards, i.e. if the bump is negative,
759 // then the iteration count (computed as End-Start) will need to be
760 // negated. To avoid the negation, just swap Start and End.
762 std::swap(Start, End);
765 // Cmp may now have a wrong direction, e.g. LEs may now be GEs.
766 // Signedness, and "including equality" are preserved.
768 bool RegToImm = Start->isReg() && End->isImm(); // for (reg..imm)
769 bool RegToReg = Start->isReg() && End->isReg(); // for (reg..reg)
771 int64_t StartV = 0, EndV = 0;
773 StartV = Start->getImm();
775 EndV = End->getImm();
778 // To compute the iteration count, we would need this computation:
779 // Count = (End - Start + (IVBump-1)) / IVBump
780 // or, when CmpHasEqual:
781 // Count = (End - Start + (IVBump-1)+1) / IVBump
782 // The "IVBump-1" part is the adjustment (AdjV). We can avoid
783 // generating an instruction specifically to add it if we can adjust
784 // the immediate values for Start or End.
787 // Need to add 1 to the total iteration count.
790 else if (End->isImm())
796 if (Cmp != Comparison::NE) {
798 StartV -= (IVBump-1);
799 else if (End->isImm())
805 unsigned R = 0, SR = 0;
806 if (Start->isReg()) {
808 SR = Start->getSubReg();
811 SR = End->getSubReg();
813 const TargetRegisterClass *RC = MRI->getRegClass(R);
814 // Hardware loops cannot handle 64-bit registers. If it's a double
815 // register, it has to have a subregister.
816 if (!SR && RC == &Hexagon::DoubleRegsRegClass)
818 const TargetRegisterClass *IntRC = &Hexagon::IntRegsRegClass;
820 // Compute DistR (register with the distance between Start and End).
821 unsigned DistR, DistSR;
823 // Avoid special case, where the start value is an imm(0).
824 if (Start->isImm() && StartV == 0) {
825 DistR = End->getReg();
826 DistSR = End->getSubReg();
828 const MCInstrDesc &SubD = RegToReg ? TII->get(Hexagon::A2_sub) :
829 (RegToImm ? TII->get(Hexagon::A2_subri) :
830 TII->get(Hexagon::A2_addi));
831 if (RegToReg || RegToImm) {
832 unsigned SubR = MRI->createVirtualRegister(IntRC);
833 MachineInstrBuilder SubIB =
834 BuildMI(*PH, InsertPos, DL, SubD, SubR);
837 SubIB.addReg(End->getReg(), 0, End->getSubReg())
838 .addReg(Start->getReg(), 0, Start->getSubReg());
841 .addReg(Start->getReg(), 0, Start->getSubReg());
844 // If the loop has been unrolled, we should use the original loop count
845 // instead of recalculating the value. This will avoid additional
846 // 'Add' instruction.
847 const MachineInstr *EndValInstr = MRI->getVRegDef(End->getReg());
848 if (EndValInstr->getOpcode() == Hexagon::A2_addi &&
849 EndValInstr->getOperand(2).getImm() == StartV) {
850 DistR = EndValInstr->getOperand(1).getReg();
852 unsigned SubR = MRI->createVirtualRegister(IntRC);
853 MachineInstrBuilder SubIB =
854 BuildMI(*PH, InsertPos, DL, SubD, SubR);
855 SubIB.addReg(End->getReg(), 0, End->getSubReg())
863 // From DistR, compute AdjR (register with the adjusted distance).
864 unsigned AdjR, AdjSR;
870 // Generate CountR = ADD DistR, AdjVal
871 unsigned AddR = MRI->createVirtualRegister(IntRC);
872 MCInstrDesc const &AddD = TII->get(Hexagon::A2_addi);
873 BuildMI(*PH, InsertPos, DL, AddD, AddR)
874 .addReg(DistR, 0, DistSR)
881 // From AdjR, compute CountR (register with the final count).
882 unsigned CountR, CountSR;
888 // The IV bump is a power of two. Log_2(IV bump) is the shift amount.
889 unsigned Shift = Log2_32(IVBump);
891 // Generate NormR = LSR DistR, Shift.
892 unsigned LsrR = MRI->createVirtualRegister(IntRC);
893 const MCInstrDesc &LsrD = TII->get(Hexagon::S2_lsr_i_r);
894 BuildMI(*PH, InsertPos, DL, LsrD, LsrR)
895 .addReg(AdjR, 0, AdjSR)
902 return new CountValue(CountValue::CV_Register, CountR, CountSR);
906 /// \brief Return true if the operation is invalid within hardware loop.
907 bool HexagonHardwareLoops::isInvalidLoopOperation(
908 const MachineInstr *MI) const {
910 // Call is not allowed because the callee may use a hardware loop except for
911 // the case when the call never returns.
912 if (MI->getDesc().isCall() && MI->getOpcode() != Hexagon::CALLv3nr)
915 // do not allow nested hardware loops
916 if (isHardwareLoop(MI))
919 // check if the instruction defines a hardware loop register
920 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
921 const MachineOperand &MO = MI->getOperand(i);
922 if (!MO.isReg() || !MO.isDef())
924 unsigned R = MO.getReg();
925 if (R == Hexagon::LC0 || R == Hexagon::LC1 ||
926 R == Hexagon::SA0 || R == Hexagon::SA1)
933 /// \brief - Return true if the loop contains an instruction that inhibits
934 /// the use of the hardware loop function.
935 bool HexagonHardwareLoops::containsInvalidInstruction(MachineLoop *L) const {
936 const std::vector<MachineBasicBlock *> &Blocks = L->getBlocks();
937 for (unsigned i = 0, e = Blocks.size(); i != e; ++i) {
938 MachineBasicBlock *MBB = Blocks[i];
939 for (MachineBasicBlock::iterator
940 MII = MBB->begin(), E = MBB->end(); MII != E; ++MII) {
941 const MachineInstr *MI = &*MII;
942 if (isInvalidLoopOperation(MI))
950 /// \brief Returns true if the instruction is dead. This was essentially
951 /// copied from DeadMachineInstructionElim::isDead, but with special cases
952 /// for inline asm, physical registers and instructions with side effects
954 bool HexagonHardwareLoops::isDead(const MachineInstr *MI,
955 SmallVectorImpl<MachineInstr *> &DeadPhis) const {
956 // Examine each operand.
957 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
958 const MachineOperand &MO = MI->getOperand(i);
959 if (!MO.isReg() || !MO.isDef())
962 unsigned Reg = MO.getReg();
963 if (MRI->use_nodbg_empty(Reg))
966 typedef MachineRegisterInfo::use_nodbg_iterator use_nodbg_iterator;
968 // This instruction has users, but if the only user is the phi node for the
969 // parent block, and the only use of that phi node is this instruction, then
970 // this instruction is dead: both it (and the phi node) can be removed.
971 use_nodbg_iterator I = MRI->use_nodbg_begin(Reg);
972 use_nodbg_iterator End = MRI->use_nodbg_end();
973 if (std::next(I) != End || !I->getParent()->isPHI())
976 MachineInstr *OnePhi = I->getParent();
977 for (unsigned j = 0, f = OnePhi->getNumOperands(); j != f; ++j) {
978 const MachineOperand &OPO = OnePhi->getOperand(j);
979 if (!OPO.isReg() || !OPO.isDef())
982 unsigned OPReg = OPO.getReg();
983 use_nodbg_iterator nextJ;
984 for (use_nodbg_iterator J = MRI->use_nodbg_begin(OPReg);
985 J != End; J = nextJ) {
986 nextJ = std::next(J);
987 MachineOperand &Use = *J;
988 MachineInstr *UseMI = Use.getParent();
990 // If the phi node has a user that is not MI, bail...
995 DeadPhis.push_back(OnePhi);
998 // If there are no defs with uses, the instruction is dead.
1002 void HexagonHardwareLoops::removeIfDead(MachineInstr *MI) {
1003 // This procedure was essentially copied from DeadMachineInstructionElim.
1005 SmallVector<MachineInstr*, 1> DeadPhis;
1006 if (isDead(MI, DeadPhis)) {
1007 DEBUG(dbgs() << "HW looping will remove: " << *MI);
1009 // It is possible that some DBG_VALUE instructions refer to this
1010 // instruction. Examine each def operand for such references;
1011 // if found, mark the DBG_VALUE as undef (but don't delete it).
1012 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
1013 const MachineOperand &MO = MI->getOperand(i);
1014 if (!MO.isReg() || !MO.isDef())
1016 unsigned Reg = MO.getReg();
1017 MachineRegisterInfo::use_iterator nextI;
1018 for (MachineRegisterInfo::use_iterator I = MRI->use_begin(Reg),
1019 E = MRI->use_end(); I != E; I = nextI) {
1020 nextI = std::next(I); // I is invalidated by the setReg
1021 MachineOperand &Use = *I;
1022 MachineInstr *UseMI = I->getParent();
1026 UseMI->getOperand(0).setReg(0U);
1030 MI->eraseFromParent();
1031 for (unsigned i = 0; i < DeadPhis.size(); ++i)
1032 DeadPhis[i]->eraseFromParent();
1036 /// \brief Check if the loop is a candidate for converting to a hardware
1037 /// loop. If so, then perform the transformation.
1039 /// This function works on innermost loops first. A loop can be converted
1040 /// if it is a counting loop; either a register value or an immediate.
1042 /// The code makes several assumptions about the representation of the loop
1044 bool HexagonHardwareLoops::convertToHardwareLoop(MachineLoop *L) {
1045 // This is just for sanity.
1046 assert(L->getHeader() && "Loop without a header?");
1048 bool Changed = false;
1049 // Process nested loops first.
1050 for (MachineLoop::iterator I = L->begin(), E = L->end(); I != E; ++I)
1051 Changed |= convertToHardwareLoop(*I);
1053 // If a nested loop has been converted, then we can't convert this loop.
1058 // Stop trying after reaching the limit (if any).
1059 int Limit = HWLoopLimit;
1061 if (Counter >= HWLoopLimit)
1067 // Does the loop contain any invalid instructions?
1068 if (containsInvalidInstruction(L))
1071 MachineBasicBlock *LastMBB = L->getExitingBlock();
1072 // Don't generate hw loop if the loop has more than one exit.
1076 MachineBasicBlock::iterator LastI = LastMBB->getFirstTerminator();
1077 if (LastI == LastMBB->end())
1080 // Is the induction variable bump feeding the latch condition?
1081 if (!fixupInductionVariable(L))
1084 // Ensure the loop has a preheader: the loop instruction will be
1086 MachineBasicBlock *Preheader = L->getLoopPreheader();
1088 Preheader = createPreheaderForLoop(L);
1093 MachineBasicBlock::iterator InsertPos = Preheader->getFirstTerminator();
1095 SmallVector<MachineInstr*, 2> OldInsts;
1096 // Are we able to determine the trip count for the loop?
1097 CountValue *TripCount = getLoopTripCount(L, OldInsts);
1101 // Is the trip count available in the preheader?
1102 if (TripCount->isReg()) {
1103 // There will be a use of the register inserted into the preheader,
1104 // so make sure that the register is actually defined at that point.
1105 MachineInstr *TCDef = MRI->getVRegDef(TripCount->getReg());
1106 MachineBasicBlock *BBDef = TCDef->getParent();
1107 if (!MDT->dominates(BBDef, Preheader))
1111 // Determine the loop start.
1112 MachineBasicBlock *TopBlock = L->getTopBlock();
1113 MachineBasicBlock *ExitingBlock = getExitingBlock(L);
1114 MachineBasicBlock *LoopStart = 0;
1115 if (ExitingBlock != L->getLoopLatch()) {
1116 MachineBasicBlock *TB = 0, *FB = 0;
1117 SmallVector<MachineOperand, 2> Cond;
1119 if (TII->AnalyzeBranch(*ExitingBlock, TB, FB, Cond, false))
1122 if (L->contains(TB))
1124 else if (L->contains(FB))
1130 LoopStart = TopBlock;
1132 // Convert the loop to a hardware loop.
1133 DEBUG(dbgs() << "Change to hardware loop at "; L->dump());
1135 if (InsertPos != Preheader->end())
1136 DL = InsertPos->getDebugLoc();
1138 if (TripCount->isReg()) {
1139 // Create a copy of the loop count register.
1140 unsigned CountReg = MRI->createVirtualRegister(&Hexagon::IntRegsRegClass);
1141 BuildMI(*Preheader, InsertPos, DL, TII->get(TargetOpcode::COPY), CountReg)
1142 .addReg(TripCount->getReg(), 0, TripCount->getSubReg());
1143 // Add the Loop instruction to the beginning of the loop.
1144 BuildMI(*Preheader, InsertPos, DL, TII->get(Hexagon::J2_loop0r))
1148 assert(TripCount->isImm() && "Expecting immediate value for trip count");
1149 // Add the Loop immediate instruction to the beginning of the loop,
1150 // if the immediate fits in the instructions. Otherwise, we need to
1151 // create a new virtual register.
1152 int64_t CountImm = TripCount->getImm();
1153 if (!TII->isValidOffset(Hexagon::J2_loop0i, CountImm)) {
1154 unsigned CountReg = MRI->createVirtualRegister(&Hexagon::IntRegsRegClass);
1155 BuildMI(*Preheader, InsertPos, DL, TII->get(Hexagon::A2_tfrsi), CountReg)
1157 BuildMI(*Preheader, InsertPos, DL, TII->get(Hexagon::J2_loop0r))
1158 .addMBB(LoopStart).addReg(CountReg);
1160 BuildMI(*Preheader, InsertPos, DL, TII->get(Hexagon::J2_loop0i))
1161 .addMBB(LoopStart).addImm(CountImm);
1164 // Make sure the loop start always has a reference in the CFG. We need
1165 // to create a BlockAddress operand to get this mechanism to work both the
1166 // MachineBasicBlock and BasicBlock objects need the flag set.
1167 LoopStart->setHasAddressTaken();
1168 // This line is needed to set the hasAddressTaken flag on the BasicBlock
1170 BlockAddress::get(const_cast<BasicBlock *>(LoopStart->getBasicBlock()));
1172 // Replace the loop branch with an endloop instruction.
1173 DebugLoc LastIDL = LastI->getDebugLoc();
1174 BuildMI(*LastMBB, LastI, LastIDL,
1175 TII->get(Hexagon::ENDLOOP0)).addMBB(LoopStart);
1177 // The loop ends with either:
1178 // - a conditional branch followed by an unconditional branch, or
1179 // - a conditional branch to the loop start.
1180 if (LastI->getOpcode() == Hexagon::J2_jumpt ||
1181 LastI->getOpcode() == Hexagon::J2_jumpf) {
1182 // Delete one and change/add an uncond. branch to out of the loop.
1183 MachineBasicBlock *BranchTarget = LastI->getOperand(1).getMBB();
1184 LastI = LastMBB->erase(LastI);
1185 if (!L->contains(BranchTarget)) {
1186 if (LastI != LastMBB->end())
1187 LastI = LastMBB->erase(LastI);
1188 SmallVector<MachineOperand, 0> Cond;
1189 TII->InsertBranch(*LastMBB, BranchTarget, nullptr, Cond, LastIDL);
1192 // Conditional branch to loop start; just delete it.
1193 LastMBB->erase(LastI);
1197 // The induction operation and the comparison may now be
1198 // unneeded. If these are unneeded, then remove them.
1199 for (unsigned i = 0; i < OldInsts.size(); ++i)
1200 removeIfDead(OldInsts[i]);
1207 bool HexagonHardwareLoops::orderBumpCompare(MachineInstr *BumpI,
1208 MachineInstr *CmpI) {
1209 assert (BumpI != CmpI && "Bump and compare in the same instruction?");
1211 MachineBasicBlock *BB = BumpI->getParent();
1212 if (CmpI->getParent() != BB)
1215 typedef MachineBasicBlock::instr_iterator instr_iterator;
1216 // Check if things are in order to begin with.
1217 for (instr_iterator I = BumpI, E = BB->instr_end(); I != E; ++I)
1222 unsigned PredR = CmpI->getOperand(0).getReg();
1223 bool FoundBump = false;
1224 instr_iterator CmpIt = CmpI, NextIt = std::next(CmpIt);
1225 for (instr_iterator I = NextIt, E = BB->instr_end(); I != E; ++I) {
1226 MachineInstr *In = &*I;
1227 for (unsigned i = 0, n = In->getNumOperands(); i < n; ++i) {
1228 MachineOperand &MO = In->getOperand(i);
1229 if (MO.isReg() && MO.isUse()) {
1230 if (MO.getReg() == PredR) // Found an intervening use of PredR.
1236 instr_iterator After = BumpI;
1237 instr_iterator From = CmpI;
1238 BB->splice(std::next(After), BB, From);
1243 assert (FoundBump && "Cannot determine instruction order");
1248 MachineInstr *HexagonHardwareLoops::defWithImmediate(unsigned R) {
1249 MachineInstr *DI = MRI->getVRegDef(R);
1250 unsigned DOpc = DI->getOpcode();
1252 case Hexagon::A2_tfrsi:
1253 case Hexagon::A2_tfrpi:
1254 case Hexagon::CONST32_Int_Real:
1255 case Hexagon::CONST64_Int_Real:
1262 int64_t HexagonHardwareLoops::getImmediate(MachineOperand &MO) {
1266 unsigned R = MO.getReg();
1267 MachineInstr *DI = defWithImmediate(R);
1268 assert(DI && "Need an immediate operand");
1269 // All currently supported "define-with-immediate" instructions have the
1270 // actual immediate value in the operand(1).
1271 int64_t v = DI->getOperand(1).getImm();
1276 void HexagonHardwareLoops::setImmediate(MachineOperand &MO, int64_t Val) {
1283 unsigned R = MO.getReg();
1284 MachineInstr *DI = MRI->getVRegDef(R);
1286 const TargetRegisterClass *RC = MRI->getRegClass(R);
1287 unsigned NewR = MRI->createVirtualRegister(RC);
1288 MachineBasicBlock &B = *DI->getParent();
1289 DebugLoc DL = DI->getDebugLoc();
1290 BuildMI(B, DI, DL, TII->get(DI->getOpcode()), NewR)
1296 bool HexagonHardwareLoops::fixupInductionVariable(MachineLoop *L) {
1297 MachineBasicBlock *Header = L->getHeader();
1298 MachineBasicBlock *Latch = L->getLoopLatch();
1299 MachineBasicBlock *ExitingBlock = getExitingBlock(L);
1301 if (!(Header && Latch && ExitingBlock))
1304 // These data structures follow the same concept as the corresponding
1305 // ones in findInductionRegister (where some comments are).
1306 typedef std::pair<unsigned,int64_t> RegisterBump;
1307 typedef std::pair<unsigned,RegisterBump> RegisterInduction;
1308 typedef std::set<RegisterInduction> RegisterInductionSet;
1310 // Register candidates for induction variables, with their associated bumps.
1311 RegisterInductionSet IndRegs;
1313 // Look for induction patterns:
1314 // vreg1 = PHI ..., [ latch, vreg2 ]
1315 // vreg2 = ADD vreg1, imm
1316 typedef MachineBasicBlock::instr_iterator instr_iterator;
1317 for (instr_iterator I = Header->instr_begin(), E = Header->instr_end();
1318 I != E && I->isPHI(); ++I) {
1319 MachineInstr *Phi = &*I;
1321 // Have a PHI instruction.
1322 for (unsigned i = 1, n = Phi->getNumOperands(); i < n; i += 2) {
1323 if (Phi->getOperand(i+1).getMBB() != Latch)
1326 unsigned PhiReg = Phi->getOperand(i).getReg();
1327 MachineInstr *DI = MRI->getVRegDef(PhiReg);
1328 unsigned UpdOpc = DI->getOpcode();
1329 bool isAdd = (UpdOpc == Hexagon::A2_addi || UpdOpc == Hexagon::A2_addp);
1332 // If the register operand to the add/sub is the PHI we are looking
1333 // at, this meets the induction pattern.
1334 unsigned IndReg = DI->getOperand(1).getReg();
1335 if (MRI->getVRegDef(IndReg) == Phi) {
1336 unsigned UpdReg = DI->getOperand(0).getReg();
1337 int64_t V = DI->getOperand(2).getImm();
1338 IndRegs.insert(std::make_pair(UpdReg, std::make_pair(IndReg, V)));
1344 if (IndRegs.empty())
1347 MachineBasicBlock *TB = nullptr, *FB = nullptr;
1348 SmallVector<MachineOperand,2> Cond;
1349 // AnalyzeBranch returns true if it fails to analyze branch.
1350 bool NotAnalyzed = TII->AnalyzeBranch(*ExitingBlock, TB, FB, Cond, false);
1351 if (NotAnalyzed || Cond.empty())
1354 if (ExitingBlock != Latch && (TB == Latch || FB == Latch)) {
1355 MachineBasicBlock *LTB = 0, *LFB = 0;
1356 SmallVector<MachineOperand,2> LCond;
1357 bool NotAnalyzed = TII->AnalyzeBranch(*Latch, LTB, LFB, LCond, false);
1361 // Since latch is not the exiting block, the latch branch should be an
1362 // unconditional branch to the loop header.
1364 TB = (LTB == Header) ? LTB : LFB;
1366 FB = (LTB == Header) ? LTB : LFB;
1370 // The latch/exit block does not go back to the header.
1373 // FB is the header (i.e., uncond. jump to branch header)
1374 // In this case, the LoopBody -> TB should not be a back edge otherwise
1375 // it could result in an infinite loop after conversion to hw_loop.
1376 // This case can happen when the Latch has two jumps like this:
1377 // Jmp_c OuterLoopHeader <-- TB
1378 // Jmp InnerLoopHeader <-- FB
1379 if (MDT->dominates(TB, FB))
1383 // Expecting a predicate register as a condition. It won't be a hardware
1384 // predicate register at this point yet, just a vreg.
1385 // HexagonInstrInfo::AnalyzeBranch for negated branches inserts imm(0)
1386 // into Cond, followed by the predicate register. For non-negated branches
1387 // it's just the register.
1388 unsigned CSz = Cond.size();
1389 if (CSz != 1 && CSz != 2)
1392 if (!Cond[CSz-1].isReg())
1395 unsigned P = Cond[CSz-1].getReg();
1396 MachineInstr *PredDef = MRI->getVRegDef(P);
1398 if (!PredDef->isCompare())
1401 SmallSet<unsigned,2> CmpRegs;
1402 MachineOperand *CmpImmOp = nullptr;
1404 // Go over all operands to the compare and look for immediate and register
1405 // operands. Assume that if the compare has a single register use and a
1406 // single immediate operand, then the register is being compared with the
1408 for (unsigned i = 0, n = PredDef->getNumOperands(); i < n; ++i) {
1409 MachineOperand &MO = PredDef->getOperand(i);
1411 // Skip all implicit references. In one case there was:
1412 // %vreg140<def> = FCMPUGT32_rr %vreg138, %vreg139, %USR<imp-use>
1413 if (MO.isImplicit())
1416 unsigned R = MO.getReg();
1417 if (!defWithImmediate(R)) {
1418 CmpRegs.insert(MO.getReg());
1421 // Consider the register to be the "immediate" operand.
1426 } else if (MO.isImm()) {
1427 if (CmpImmOp) // A second immediate argument? Confusing. Bail out.
1433 if (CmpRegs.empty())
1436 // Check if the compared register follows the order we want. Fix if needed.
1437 for (RegisterInductionSet::iterator I = IndRegs.begin(), E = IndRegs.end();
1439 // This is a success. If the register used in the comparison is one that
1440 // we have identified as a bumped (updated) induction register, there is
1442 if (CmpRegs.count(I->first))
1445 // Otherwise, if the register being compared comes out of a PHI node,
1446 // and has been recognized as following the induction pattern, and is
1447 // compared against an immediate, we can fix it.
1448 const RegisterBump &RB = I->second;
1449 if (CmpRegs.count(RB.first)) {
1453 int64_t CmpImm = getImmediate(*CmpImmOp);
1454 int64_t V = RB.second;
1455 if (V > 0 && CmpImm+V < CmpImm) // Overflow (64-bit).
1457 if (V < 0 && CmpImm+V > CmpImm) // Overflow (64-bit).
1460 // Some forms of cmp-immediate allow u9 and s10. Assume the worst case
1461 // scenario, i.e. an 8-bit value.
1462 if (CmpImmOp->isImm() && !isInt<8>(CmpImm))
1465 // Make sure that the compare happens after the bump. Otherwise,
1466 // after the fixup, the compare would use a yet-undefined register.
1467 MachineInstr *BumpI = MRI->getVRegDef(I->first);
1468 bool Order = orderBumpCompare(BumpI, PredDef);
1472 // Finally, fix the compare instruction.
1473 setImmediate(*CmpImmOp, CmpImm);
1474 for (unsigned i = 0, n = PredDef->getNumOperands(); i < n; ++i) {
1475 MachineOperand &MO = PredDef->getOperand(i);
1476 if (MO.isReg() && MO.getReg() == RB.first) {
1477 MO.setReg(I->first);
1488 /// \brief Create a preheader for a given loop.
1489 MachineBasicBlock *HexagonHardwareLoops::createPreheaderForLoop(
1491 if (MachineBasicBlock *TmpPH = L->getLoopPreheader())
1494 if (!HWCreatePreheader)
1497 MachineBasicBlock *Header = L->getHeader();
1498 MachineBasicBlock *Latch = L->getLoopLatch();
1499 MachineBasicBlock *ExitingBlock = getExitingBlock(L);
1500 MachineFunction *MF = Header->getParent();
1504 if ((PHFn != "") && (PHFn != MF->getName()))
1508 if (!Latch || !ExitingBlock || Header->hasAddressTaken())
1511 typedef MachineBasicBlock::instr_iterator instr_iterator;
1513 // Verify that all existing predecessors have analyzable branches
1514 // (or no branches at all).
1515 typedef std::vector<MachineBasicBlock*> MBBVector;
1516 MBBVector Preds(Header->pred_begin(), Header->pred_end());
1517 SmallVector<MachineOperand,2> Tmp1;
1518 MachineBasicBlock *TB = nullptr, *FB = nullptr;
1520 if (TII->AnalyzeBranch(*ExitingBlock, TB, FB, Tmp1, false))
1523 for (MBBVector::iterator I = Preds.begin(), E = Preds.end(); I != E; ++I) {
1524 MachineBasicBlock *PB = *I;
1525 bool NotAnalyzed = TII->AnalyzeBranch(*PB, TB, FB, Tmp1, false);
1530 MachineBasicBlock *NewPH = MF->CreateMachineBasicBlock();
1531 MF->insert(Header, NewPH);
1533 if (Header->pred_size() > 2) {
1534 // Ensure that the header has only two predecessors: the preheader and
1535 // the loop latch. Any additional predecessors of the header should
1536 // join at the newly created preheader. Inspect all PHI nodes from the
1537 // header and create appropriate corresponding PHI nodes in the preheader.
1539 for (instr_iterator I = Header->instr_begin(), E = Header->instr_end();
1540 I != E && I->isPHI(); ++I) {
1541 MachineInstr *PN = &*I;
1543 const MCInstrDesc &PD = TII->get(TargetOpcode::PHI);
1544 MachineInstr *NewPN = MF->CreateMachineInstr(PD, DL);
1545 NewPH->insert(NewPH->end(), NewPN);
1547 unsigned PR = PN->getOperand(0).getReg();
1548 const TargetRegisterClass *RC = MRI->getRegClass(PR);
1549 unsigned NewPR = MRI->createVirtualRegister(RC);
1550 NewPN->addOperand(MachineOperand::CreateReg(NewPR, true));
1552 // Copy all non-latch operands of a header's PHI node to the newly
1553 // created PHI node in the preheader.
1554 for (unsigned i = 1, n = PN->getNumOperands(); i < n; i += 2) {
1555 unsigned PredR = PN->getOperand(i).getReg();
1556 MachineBasicBlock *PredB = PN->getOperand(i+1).getMBB();
1560 NewPN->addOperand(MachineOperand::CreateReg(PredR, false));
1561 NewPN->addOperand(MachineOperand::CreateMBB(PredB));
1564 // Remove copied operands from the old PHI node and add the value
1565 // coming from the preheader's PHI.
1566 for (int i = PN->getNumOperands()-2; i > 0; i -= 2) {
1567 MachineBasicBlock *PredB = PN->getOperand(i+1).getMBB();
1568 if (PredB != Latch) {
1569 PN->RemoveOperand(i+1);
1570 PN->RemoveOperand(i);
1573 PN->addOperand(MachineOperand::CreateReg(NewPR, false));
1574 PN->addOperand(MachineOperand::CreateMBB(NewPH));
1578 assert(Header->pred_size() == 2);
1580 // The header has only two predecessors, but the non-latch predecessor
1581 // is not a preheader (e.g. it has other successors, etc.)
1582 // In such a case we don't need any extra PHI nodes in the new preheader,
1583 // all we need is to adjust existing PHIs in the header to now refer to
1584 // the new preheader.
1585 for (instr_iterator I = Header->instr_begin(), E = Header->instr_end();
1586 I != E && I->isPHI(); ++I) {
1587 MachineInstr *PN = &*I;
1588 for (unsigned i = 1, n = PN->getNumOperands(); i < n; i += 2) {
1589 MachineOperand &MO = PN->getOperand(i+1);
1590 if (MO.getMBB() != Latch)
1596 // "Reroute" the CFG edges to link in the new preheader.
1597 // If any of the predecessors falls through to the header, insert a branch
1598 // to the new preheader in that place.
1599 SmallVector<MachineOperand,1> Tmp2;
1600 SmallVector<MachineOperand,1> EmptyCond;
1604 for (MBBVector::iterator I = Preds.begin(), E = Preds.end(); I != E; ++I) {
1605 MachineBasicBlock *PB = *I;
1608 bool NotAnalyzed = TII->AnalyzeBranch(*PB, TB, FB, Tmp2, false);
1609 (void)NotAnalyzed; // suppress compiler warning
1610 assert (!NotAnalyzed && "Should be analyzable!");
1611 if (TB != Header && (Tmp2.empty() || FB != Header))
1612 TII->InsertBranch(*PB, NewPH, nullptr, EmptyCond, DL);
1613 PB->ReplaceUsesOfBlockWith(Header, NewPH);
1617 // It can happen that the latch block will fall through into the header.
1618 // Insert an unconditional branch to the header.
1620 bool LatchNotAnalyzed = TII->AnalyzeBranch(*Latch, TB, FB, Tmp2, false);
1621 (void)LatchNotAnalyzed; // suppress compiler warning
1622 assert (!LatchNotAnalyzed && "Should be analyzable!");
1624 TII->InsertBranch(*Latch, Header, nullptr, EmptyCond, DL);
1626 // Finally, the branch from the preheader to the header.
1627 TII->InsertBranch(*NewPH, Header, nullptr, EmptyCond, DL);
1628 NewPH->addSuccessor(Header);
1630 MachineLoop *ParentLoop = L->getParentLoop();
1632 ParentLoop->addBasicBlockToLoop(NewPH, MLI->getBase());
1634 // Update the dominator information with the new preheader.
1636 MachineDomTreeNode *HDom = MDT->getNode(Header);
1637 MDT->addNewBlock(NewPH, HDom->getIDom()->getBlock());
1638 MDT->changeImmediateDominator(Header, NewPH);