1 //===- HexagonHardwareLoops.cpp - Identify and generate hardware loops ----===//
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
9 // This pass identifies loops where we can generate the Hexagon hardware
10 // loop instruction. The hardware loop can perform loop branches with a
11 // zero-cycle overhead.
13 // The pattern that defines the induction variable can changed depending on
14 // prior optimizations. For example, the IndVarSimplify phase run by 'opt'
15 // normalizes induction variables, and the Loop Strength Reduction pass
16 // run by 'llc' may also make changes to the induction variable.
17 // The pattern detected by this phase is due to running Strength Reduction.
19 // Criteria for hardware loops:
20 // - Countable loops (w/ ind. var for a trip count)
21 // - Assumes loops are normalized by IndVarSimplify
22 // - Try inner-most loops first
23 // - No function calls in loops.
25 //===----------------------------------------------------------------------===//
27 #include "HexagonInstrInfo.h"
28 #include "HexagonSubtarget.h"
29 #include "llvm/ADT/ArrayRef.h"
30 #include "llvm/ADT/STLExtras.h"
31 #include "llvm/ADT/SmallSet.h"
32 #include "llvm/ADT/SmallVector.h"
33 #include "llvm/ADT/Statistic.h"
34 #include "llvm/ADT/StringRef.h"
35 #include "llvm/CodeGen/MachineBasicBlock.h"
36 #include "llvm/CodeGen/MachineDominators.h"
37 #include "llvm/CodeGen/MachineFunction.h"
38 #include "llvm/CodeGen/MachineFunctionPass.h"
39 #include "llvm/CodeGen/MachineInstr.h"
40 #include "llvm/CodeGen/MachineInstrBuilder.h"
41 #include "llvm/CodeGen/MachineLoopInfo.h"
42 #include "llvm/CodeGen/MachineOperand.h"
43 #include "llvm/CodeGen/MachineRegisterInfo.h"
44 #include "llvm/CodeGen/TargetRegisterInfo.h"
45 #include "llvm/IR/Constants.h"
46 #include "llvm/IR/DebugLoc.h"
47 #include "llvm/InitializePasses.h"
48 #include "llvm/Pass.h"
49 #include "llvm/Support/CommandLine.h"
50 #include "llvm/Support/Debug.h"
51 #include "llvm/Support/ErrorHandling.h"
52 #include "llvm/Support/MathExtras.h"
53 #include "llvm/Support/raw_ostream.h"
66 #define DEBUG_TYPE "hwloops"
69 static cl::opt<int> HWLoopLimit("hexagon-max-hwloop", cl::Hidden, cl::init(-1));
71 // Option to create preheader only for a specific function.
72 static cl::opt<std::string> PHFn("hexagon-hwloop-phfn", cl::Hidden,
76 // Option to create a preheader if one doesn't exist.
77 static cl::opt<bool> HWCreatePreheader("hexagon-hwloop-preheader",
78 cl::Hidden, cl::init(true),
79 cl::desc("Add a preheader to a hardware loop if one doesn't exist"));
81 // Turn it off by default. If a preheader block is not created here, the
82 // software pipeliner may be unable to find a block suitable to serve as
83 // a preheader. In that case SWP will not run.
84 static cl::opt<bool> SpecPreheader("hwloop-spec-preheader", cl::init(false),
85 cl::Hidden, cl::ZeroOrMore, cl::desc("Allow speculation of preheader "
88 STATISTIC(NumHWLoops, "Number of loops converted to hardware loops");
92 FunctionPass *createHexagonHardwareLoops();
93 void initializeHexagonHardwareLoopsPass(PassRegistry&);
95 } // end namespace llvm
101 struct HexagonHardwareLoops : public MachineFunctionPass {
102 MachineLoopInfo *MLI;
103 MachineRegisterInfo *MRI;
104 MachineDominatorTree *MDT;
105 const HexagonInstrInfo *TII;
106 const HexagonRegisterInfo *TRI;
114 HexagonHardwareLoops() : MachineFunctionPass(ID) {}
116 bool runOnMachineFunction(MachineFunction &MF) override;
118 StringRef getPassName() const override { return "Hexagon Hardware Loops"; }
120 void getAnalysisUsage(AnalysisUsage &AU) const override {
121 AU.addRequired<MachineDominatorTree>();
122 AU.addRequired<MachineLoopInfo>();
123 MachineFunctionPass::getAnalysisUsage(AU);
127 using LoopFeederMap = std::map<unsigned, MachineInstr *>;
129 /// Kinds of comparisons in the compare instructions.
147 static Kind getSwappedComparison(Kind Cmp) {
148 assert ((!((Cmp & L) && (Cmp & G))) && "Malformed comparison operator");
149 if ((Cmp & L) || (Cmp & G))
150 return (Kind)(Cmp ^ (L|G));
154 static Kind getNegatedComparison(Kind Cmp) {
155 if ((Cmp & L) || (Cmp & G))
156 return (Kind)((Cmp ^ (L | G)) ^ EQ);
157 if ((Cmp & NE) || (Cmp & EQ))
158 return (Kind)(Cmp ^ (EQ | NE));
162 static bool isSigned(Kind Cmp) {
163 return (Cmp & (L | G) && !(Cmp & U));
166 static bool isUnsigned(Kind Cmp) {
171 /// Find the register that contains the loop controlling
172 /// induction variable.
173 /// If successful, it will return true and set the \p Reg, \p IVBump
174 /// and \p IVOp arguments. Otherwise it will return false.
175 /// The returned induction register is the register R that follows the
176 /// following induction pattern:
178 /// R = phi ..., [ R.next, LatchBlock ]
179 /// R.next = R + #bump
180 /// if (R.next < #N) goto loop
181 /// IVBump is the immediate value added to R, and IVOp is the instruction
182 /// "R.next = R + #bump".
183 bool findInductionRegister(MachineLoop *L, unsigned &Reg,
184 int64_t &IVBump, MachineInstr *&IVOp) const;
186 /// Return the comparison kind for the specified opcode.
187 Comparison::Kind getComparisonKind(unsigned CondOpc,
188 MachineOperand *InitialValue,
189 const MachineOperand *Endvalue,
190 int64_t IVBump) const;
192 /// Analyze the statements in a loop to determine if the loop
193 /// has a computable trip count and, if so, return a value that represents
194 /// the trip count expression.
195 CountValue *getLoopTripCount(MachineLoop *L,
196 SmallVectorImpl<MachineInstr *> &OldInsts);
198 /// Return the expression that represents the number of times
199 /// a loop iterates. The function takes the operands that represent the
200 /// loop start value, loop end value, and induction value. Based upon
201 /// these operands, the function attempts to compute the trip count.
202 /// If the trip count is not directly available (as an immediate value,
203 /// or a register), the function will attempt to insert computation of it
204 /// to the loop's preheader.
205 CountValue *computeCount(MachineLoop *Loop, const MachineOperand *Start,
206 const MachineOperand *End, unsigned IVReg,
207 int64_t IVBump, Comparison::Kind Cmp) const;
209 /// Return true if the instruction is not valid within a hardware
211 bool isInvalidLoopOperation(const MachineInstr *MI,
212 bool IsInnerHWLoop) const;
214 /// Return true if the loop contains an instruction that inhibits
215 /// using the hardware loop.
216 bool containsInvalidInstruction(MachineLoop *L, bool IsInnerHWLoop) const;
218 /// Given a loop, check if we can convert it to a hardware loop.
219 /// If so, then perform the conversion and return true.
220 bool convertToHardwareLoop(MachineLoop *L, bool &L0used, bool &L1used);
222 /// Return true if the instruction is now dead.
223 bool isDead(const MachineInstr *MI,
224 SmallVectorImpl<MachineInstr *> &DeadPhis) const;
226 /// Remove the instruction if it is now dead.
227 void removeIfDead(MachineInstr *MI);
229 /// Make sure that the "bump" instruction executes before the
230 /// compare. We need that for the IV fixup, so that the compare
231 /// instruction would not use a bumped value that has not yet been
232 /// defined. If the instructions are out of order, try to reorder them.
233 bool orderBumpCompare(MachineInstr *BumpI, MachineInstr *CmpI);
235 /// Return true if MO and MI pair is visited only once. If visited
236 /// more than once, this indicates there is recursion. In such a case,
238 bool isLoopFeeder(MachineLoop *L, MachineBasicBlock *A, MachineInstr *MI,
239 const MachineOperand *MO,
240 LoopFeederMap &LoopFeederPhi) const;
242 /// Return true if the Phi may generate a value that may underflow,
244 bool phiMayWrapOrUnderflow(MachineInstr *Phi, const MachineOperand *EndVal,
245 MachineBasicBlock *MBB, MachineLoop *L,
246 LoopFeederMap &LoopFeederPhi) const;
248 /// Return true if the induction variable may underflow an unsigned
249 /// value in the first iteration.
250 bool loopCountMayWrapOrUnderFlow(const MachineOperand *InitVal,
251 const MachineOperand *EndVal,
252 MachineBasicBlock *MBB, MachineLoop *L,
253 LoopFeederMap &LoopFeederPhi) const;
255 /// Check if the given operand has a compile-time known constant
256 /// value. Return true if yes, and false otherwise. When returning true, set
257 /// Val to the corresponding constant value.
258 bool checkForImmediate(const MachineOperand &MO, int64_t &Val) const;
260 /// Check if the operand has a compile-time known constant value.
261 bool isImmediate(const MachineOperand &MO) const {
263 return checkForImmediate(MO, V);
266 /// Return the immediate for the specified operand.
267 int64_t getImmediate(const MachineOperand &MO) const {
269 if (!checkForImmediate(MO, V))
270 llvm_unreachable("Invalid operand");
274 /// Reset the given machine operand to now refer to a new immediate
275 /// value. Assumes that the operand was already referencing an immediate
276 /// value, either directly, or via a register.
277 void setImmediate(MachineOperand &MO, int64_t Val);
279 /// Fix the data flow of the induction variable.
280 /// The desired flow is: phi ---> bump -+-> comparison-in-latch.
283 /// where "bump" is the increment of the induction variable:
284 /// iv = iv + #const.
285 /// Due to some prior code transformations, the actual flow may look
287 /// phi -+-> bump ---> back to phi
289 /// +-> comparison-in-latch (against upper_bound-bump),
290 /// i.e. the comparison that controls the loop execution may be using
291 /// the value of the induction variable from before the increment.
293 /// Return true if the loop's flow is the desired one (i.e. it's
294 /// either been fixed, or no fixing was necessary).
295 /// Otherwise, return false. This can happen if the induction variable
296 /// couldn't be identified, or if the value in the latch's comparison
297 /// cannot be adjusted to reflect the post-bump value.
298 bool fixupInductionVariable(MachineLoop *L);
300 /// Given a loop, if it does not have a preheader, create one.
301 /// Return the block that is the preheader.
302 MachineBasicBlock *createPreheaderForLoop(MachineLoop *L);
305 char HexagonHardwareLoops::ID = 0;
307 int HexagonHardwareLoops::Counter = 0;
310 /// Abstraction for a trip count of a loop. A smaller version
311 /// of the MachineOperand class without the concerns of changing the
312 /// operand representation.
315 enum CountValueType {
331 explicit CountValue(CountValueType t, unsigned v, unsigned u = 0) {
333 if (Kind == CV_Register) {
341 bool isReg() const { return Kind == CV_Register; }
342 bool isImm() const { return Kind == CV_Immediate; }
344 unsigned getReg() const {
345 assert(isReg() && "Wrong CountValue accessor");
346 return Contents.R.Reg;
349 unsigned getSubReg() const {
350 assert(isReg() && "Wrong CountValue accessor");
351 return Contents.R.Sub;
354 unsigned getImm() const {
355 assert(isImm() && "Wrong CountValue accessor");
356 return Contents.ImmVal;
359 void print(raw_ostream &OS, const TargetRegisterInfo *TRI = nullptr) const {
360 if (isReg()) { OS << printReg(Contents.R.Reg, TRI, Contents.R.Sub); }
361 if (isImm()) { OS << Contents.ImmVal; }
365 } // end anonymous namespace
367 INITIALIZE_PASS_BEGIN(HexagonHardwareLoops, "hwloops",
368 "Hexagon Hardware Loops", false, false)
369 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
370 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
371 INITIALIZE_PASS_END(HexagonHardwareLoops, "hwloops",
372 "Hexagon Hardware Loops", false, false)
374 FunctionPass *llvm::createHexagonHardwareLoops() {
375 return new HexagonHardwareLoops();
378 bool HexagonHardwareLoops::runOnMachineFunction(MachineFunction &MF) {
379 LLVM_DEBUG(dbgs() << "********* Hexagon Hardware Loops *********\n");
380 if (skipFunction(MF.getFunction()))
383 bool Changed = false;
385 MLI = &getAnalysis<MachineLoopInfo>();
386 MRI = &MF.getRegInfo();
387 MDT = &getAnalysis<MachineDominatorTree>();
388 const HexagonSubtarget &HST = MF.getSubtarget<HexagonSubtarget>();
389 TII = HST.getInstrInfo();
390 TRI = HST.getRegisterInfo();
393 if (!L->getParentLoop()) {
396 Changed |= convertToHardwareLoop(L, L0Used, L1Used);
402 bool HexagonHardwareLoops::findInductionRegister(MachineLoop *L,
407 MachineBasicBlock *Header = L->getHeader();
408 MachineBasicBlock *Preheader = MLI->findLoopPreheader(L, SpecPreheader);
409 MachineBasicBlock *Latch = L->getLoopLatch();
410 MachineBasicBlock *ExitingBlock = L->findLoopControlBlock();
411 if (!Header || !Preheader || !Latch || !ExitingBlock)
414 // This pair represents an induction register together with an immediate
415 // value that will be added to it in each loop iteration.
416 using RegisterBump = std::pair<unsigned, int64_t>;
418 // Mapping: R.next -> (R, bump), where R, R.next and bump are derived
419 // from an induction operation
421 // where bump is an immediate value.
422 using InductionMap = std::map<unsigned, RegisterBump>;
426 using instr_iterator = MachineBasicBlock::instr_iterator;
428 for (instr_iterator I = Header->instr_begin(), E = Header->instr_end();
429 I != E && I->isPHI(); ++I) {
430 MachineInstr *Phi = &*I;
432 // Have a PHI instruction. Get the operand that corresponds to the
433 // latch block, and see if is a result of an addition of form "reg+imm",
434 // where the "reg" is defined by the PHI node we are looking at.
435 for (unsigned i = 1, n = Phi->getNumOperands(); i < n; i += 2) {
436 if (Phi->getOperand(i+1).getMBB() != Latch)
439 Register PhiOpReg = Phi->getOperand(i).getReg();
440 MachineInstr *DI = MRI->getVRegDef(PhiOpReg);
442 if (DI->getDesc().isAdd()) {
443 // If the register operand to the add is the PHI we're looking at, this
444 // meets the induction pattern.
445 Register IndReg = DI->getOperand(1).getReg();
446 MachineOperand &Opnd2 = DI->getOperand(2);
448 if (MRI->getVRegDef(IndReg) == Phi && checkForImmediate(Opnd2, V)) {
449 Register UpdReg = DI->getOperand(0).getReg();
450 IndMap.insert(std::make_pair(UpdReg, std::make_pair(IndReg, V)));
456 SmallVector<MachineOperand,2> Cond;
457 MachineBasicBlock *TB = nullptr, *FB = nullptr;
458 bool NotAnalyzed = TII->analyzeBranch(*ExitingBlock, TB, FB, Cond, false);
462 unsigned PredR, PredPos, PredRegFlags;
463 if (!TII->getPredReg(Cond, PredR, PredPos, PredRegFlags))
466 MachineInstr *PredI = MRI->getVRegDef(PredR);
467 if (!PredI->isCompare())
470 unsigned CmpReg1 = 0, CmpReg2 = 0;
471 int CmpImm = 0, CmpMask = 0;
473 TII->analyzeCompare(*PredI, CmpReg1, CmpReg2, CmpMask, CmpImm);
474 // Fail if the compare was not analyzed, or it's not comparing a register
475 // with an immediate value. Not checking the mask here, since we handle
476 // the individual compare opcodes (including A4_cmpb*) later on.
480 // Exactly one of the input registers to the comparison should be among
481 // the induction registers.
482 InductionMap::iterator IndMapEnd = IndMap.end();
483 InductionMap::iterator F = IndMapEnd;
485 InductionMap::iterator F1 = IndMap.find(CmpReg1);
490 InductionMap::iterator F2 = IndMap.find(CmpReg2);
491 if (F2 != IndMapEnd) {
500 Reg = F->second.first;
501 IVBump = F->second.second;
502 IVOp = MRI->getVRegDef(F->first);
506 // Return the comparison kind for the specified opcode.
507 HexagonHardwareLoops::Comparison::Kind
508 HexagonHardwareLoops::getComparisonKind(unsigned CondOpc,
509 MachineOperand *InitialValue,
510 const MachineOperand *EndValue,
511 int64_t IVBump) const {
512 Comparison::Kind Cmp = (Comparison::Kind)0;
514 case Hexagon::C2_cmpeq:
515 case Hexagon::C2_cmpeqi:
516 case Hexagon::C2_cmpeqp:
517 Cmp = Comparison::EQ;
519 case Hexagon::C4_cmpneq:
520 case Hexagon::C4_cmpneqi:
521 Cmp = Comparison::NE;
523 case Hexagon::C2_cmplt:
524 Cmp = Comparison::LTs;
526 case Hexagon::C2_cmpltu:
527 Cmp = Comparison::LTu;
529 case Hexagon::C4_cmplte:
530 case Hexagon::C4_cmpltei:
531 Cmp = Comparison::LEs;
533 case Hexagon::C4_cmplteu:
534 case Hexagon::C4_cmplteui:
535 Cmp = Comparison::LEu;
537 case Hexagon::C2_cmpgt:
538 case Hexagon::C2_cmpgti:
539 case Hexagon::C2_cmpgtp:
540 Cmp = Comparison::GTs;
542 case Hexagon::C2_cmpgtu:
543 case Hexagon::C2_cmpgtui:
544 case Hexagon::C2_cmpgtup:
545 Cmp = Comparison::GTu;
547 case Hexagon::C2_cmpgei:
548 Cmp = Comparison::GEs;
550 case Hexagon::C2_cmpgeui:
551 Cmp = Comparison::GEs;
554 return (Comparison::Kind)0;
559 /// Analyze the statements in a loop to determine if the loop has
560 /// a computable trip count and, if so, return a value that represents
561 /// the trip count expression.
563 /// This function iterates over the phi nodes in the loop to check for
564 /// induction variable patterns that are used in the calculation for
565 /// the number of time the loop is executed.
566 CountValue *HexagonHardwareLoops::getLoopTripCount(MachineLoop *L,
567 SmallVectorImpl<MachineInstr *> &OldInsts) {
568 MachineBasicBlock *TopMBB = L->getTopBlock();
569 MachineBasicBlock::pred_iterator PI = TopMBB->pred_begin();
570 assert(PI != TopMBB->pred_end() &&
571 "Loop must have more than one incoming edge!");
572 MachineBasicBlock *Backedge = *PI++;
573 if (PI == TopMBB->pred_end()) // dead loop?
575 MachineBasicBlock *Incoming = *PI++;
576 if (PI != TopMBB->pred_end()) // multiple backedges?
579 // Make sure there is one incoming and one backedge and determine which
581 if (L->contains(Incoming)) {
582 if (L->contains(Backedge))
584 std::swap(Incoming, Backedge);
585 } else if (!L->contains(Backedge))
588 // Look for the cmp instruction to determine if we can get a useful trip
589 // count. The trip count can be either a register or an immediate. The
590 // location of the value depends upon the type (reg or imm).
591 MachineBasicBlock *ExitingBlock = L->findLoopControlBlock();
598 bool FoundIV = findInductionRegister(L, IVReg, IVBump, IVOp);
602 MachineBasicBlock *Preheader = MLI->findLoopPreheader(L, SpecPreheader);
604 MachineOperand *InitialValue = nullptr;
605 MachineInstr *IV_Phi = MRI->getVRegDef(IVReg);
606 MachineBasicBlock *Latch = L->getLoopLatch();
607 for (unsigned i = 1, n = IV_Phi->getNumOperands(); i < n; i += 2) {
608 MachineBasicBlock *MBB = IV_Phi->getOperand(i+1).getMBB();
609 if (MBB == Preheader)
610 InitialValue = &IV_Phi->getOperand(i);
611 else if (MBB == Latch)
612 IVReg = IV_Phi->getOperand(i).getReg(); // Want IV reg after bump.
617 SmallVector<MachineOperand,2> Cond;
618 MachineBasicBlock *TB = nullptr, *FB = nullptr;
619 bool NotAnalyzed = TII->analyzeBranch(*ExitingBlock, TB, FB, Cond, false);
623 MachineBasicBlock *Header = L->getHeader();
624 // TB must be non-null. If FB is also non-null, one of them must be
625 // the header. Otherwise, branch to TB could be exiting the loop, and
626 // the fall through can go to the header.
627 assert (TB && "Exit block without a branch?");
628 if (ExitingBlock != Latch && (TB == Latch || FB == Latch)) {
629 MachineBasicBlock *LTB = nullptr, *LFB = nullptr;
630 SmallVector<MachineOperand,2> LCond;
631 bool NotAnalyzed = TII->analyzeBranch(*Latch, LTB, LFB, LCond, false);
635 TB = (LTB == Header) ? LTB : LFB;
637 FB = (LTB == Header) ? LTB: LFB;
639 assert ((!FB || TB == Header || FB == Header) && "Branches not to header?");
640 if (!TB || (FB && TB != Header && FB != Header))
643 // Branches of form "if (!P) ..." cause HexagonInstrInfo::AnalyzeBranch
644 // to put imm(0), followed by P in the vector Cond.
645 // If TB is not the header, it means that the "not-taken" path must lead
647 bool Negated = TII->predOpcodeHasNot(Cond) ^ (TB != Header);
648 unsigned PredReg, PredPos, PredRegFlags;
649 if (!TII->getPredReg(Cond, PredReg, PredPos, PredRegFlags))
651 MachineInstr *CondI = MRI->getVRegDef(PredReg);
652 unsigned CondOpc = CondI->getOpcode();
654 unsigned CmpReg1 = 0, CmpReg2 = 0;
655 int Mask = 0, ImmValue = 0;
657 TII->analyzeCompare(*CondI, CmpReg1, CmpReg2, Mask, ImmValue);
661 // The comparison operator type determines how we compute the loop
663 OldInsts.push_back(CondI);
664 OldInsts.push_back(IVOp);
666 // Sadly, the following code gets information based on the position
667 // of the operands in the compare instruction. This has to be done
668 // this way, because the comparisons check for a specific relationship
669 // between the operands (e.g. is-less-than), rather than to find out
670 // what relationship the operands are in (as on PPC).
671 Comparison::Kind Cmp;
672 bool isSwapped = false;
673 const MachineOperand &Op1 = CondI->getOperand(1);
674 const MachineOperand &Op2 = CondI->getOperand(2);
675 const MachineOperand *EndValue = nullptr;
678 if (Op2.isImm() || Op1.getReg() == IVReg)
689 Cmp = getComparisonKind(CondOpc, InitialValue, EndValue, IVBump);
693 Cmp = Comparison::getNegatedComparison(Cmp);
695 Cmp = Comparison::getSwappedComparison(Cmp);
697 if (InitialValue->isReg()) {
698 Register R = InitialValue->getReg();
699 MachineBasicBlock *DefBB = MRI->getVRegDef(R)->getParent();
700 if (!MDT->properlyDominates(DefBB, Header)) {
702 if (!checkForImmediate(*InitialValue, V))
705 OldInsts.push_back(MRI->getVRegDef(R));
707 if (EndValue->isReg()) {
708 Register R = EndValue->getReg();
709 MachineBasicBlock *DefBB = MRI->getVRegDef(R)->getParent();
710 if (!MDT->properlyDominates(DefBB, Header)) {
712 if (!checkForImmediate(*EndValue, V))
715 OldInsts.push_back(MRI->getVRegDef(R));
718 return computeCount(L, InitialValue, EndValue, IVReg, IVBump, Cmp);
721 /// Helper function that returns the expression that represents the
722 /// number of times a loop iterates. The function takes the operands that
723 /// represent the loop start value, loop end value, and induction value.
724 /// Based upon these operands, the function attempts to compute the trip count.
725 CountValue *HexagonHardwareLoops::computeCount(MachineLoop *Loop,
726 const MachineOperand *Start,
727 const MachineOperand *End,
730 Comparison::Kind Cmp) const {
731 // Cannot handle comparison EQ, i.e. while (A == B).
732 if (Cmp == Comparison::EQ)
735 // Check if either the start or end values are an assignment of an immediate.
736 // If so, use the immediate value rather than the register.
737 if (Start->isReg()) {
738 const MachineInstr *StartValInstr = MRI->getVRegDef(Start->getReg());
739 if (StartValInstr && (StartValInstr->getOpcode() == Hexagon::A2_tfrsi ||
740 StartValInstr->getOpcode() == Hexagon::A2_tfrpi))
741 Start = &StartValInstr->getOperand(1);
744 const MachineInstr *EndValInstr = MRI->getVRegDef(End->getReg());
745 if (EndValInstr && (EndValInstr->getOpcode() == Hexagon::A2_tfrsi ||
746 EndValInstr->getOpcode() == Hexagon::A2_tfrpi))
747 End = &EndValInstr->getOperand(1);
750 if (!Start->isReg() && !Start->isImm())
752 if (!End->isReg() && !End->isImm())
755 bool CmpLess = Cmp & Comparison::L;
756 bool CmpGreater = Cmp & Comparison::G;
757 bool CmpHasEqual = Cmp & Comparison::EQ;
759 // Avoid certain wrap-arounds. This doesn't detect all wrap-arounds.
760 if (CmpLess && IVBump < 0)
761 // Loop going while iv is "less" with the iv value going down. Must wrap.
764 if (CmpGreater && IVBump > 0)
765 // Loop going while iv is "greater" with the iv value going up. Must wrap.
768 // Phis that may feed into the loop.
769 LoopFeederMap LoopFeederPhi;
771 // Check if the initial value may be zero and can be decremented in the first
772 // iteration. If the value is zero, the endloop instruction will not decrement
773 // the loop counter, so we shouldn't generate a hardware loop in this case.
774 if (loopCountMayWrapOrUnderFlow(Start, End, Loop->getLoopPreheader(), Loop,
778 if (Start->isImm() && End->isImm()) {
779 // Both, start and end are immediates.
780 int64_t StartV = Start->getImm();
781 int64_t EndV = End->getImm();
782 int64_t Dist = EndV - StartV;
786 bool Exact = (Dist % IVBump) == 0;
788 if (Cmp == Comparison::NE) {
791 if ((Dist < 0) ^ (IVBump < 0))
795 // For comparisons that include the final value (i.e. include equality
796 // with the final value), we need to increase the distance by 1.
798 Dist = Dist > 0 ? Dist+1 : Dist-1;
800 // For the loop to iterate, CmpLess should imply Dist > 0. Similarly,
801 // CmpGreater should imply Dist < 0. These conditions could actually
802 // fail, for example, in unreachable code (which may still appear to be
803 // reachable in the CFG).
804 if ((CmpLess && Dist < 0) || (CmpGreater && Dist > 0))
807 // "Normalized" distance, i.e. with the bump set to +-1.
808 int64_t Dist1 = (IVBump > 0) ? (Dist + (IVBump - 1)) / IVBump
809 : (-Dist + (-IVBump - 1)) / (-IVBump);
810 assert (Dist1 > 0 && "Fishy thing. Both operands have the same sign.");
812 uint64_t Count = Dist1;
814 if (Count > 0xFFFFFFFFULL)
817 return new CountValue(CountValue::CV_Immediate, Count);
820 // A general case: Start and End are some values, but the actual
821 // iteration count may not be available. If it is not, insert
822 // a computation of it into the preheader.
824 // If the induction variable bump is not a power of 2, quit.
825 // Othwerise we'd need a general integer division.
826 if (!isPowerOf2_64(std::abs(IVBump)))
829 MachineBasicBlock *PH = MLI->findLoopPreheader(Loop, SpecPreheader);
830 assert (PH && "Should have a preheader by now");
831 MachineBasicBlock::iterator InsertPos = PH->getFirstTerminator();
833 if (InsertPos != PH->end())
834 DL = InsertPos->getDebugLoc();
836 // If Start is an immediate and End is a register, the trip count
837 // will be "reg - imm". Hexagon's "subtract immediate" instruction
838 // is actually "reg + -imm".
840 // If the loop IV is going downwards, i.e. if the bump is negative,
841 // then the iteration count (computed as End-Start) will need to be
842 // negated. To avoid the negation, just swap Start and End.
844 std::swap(Start, End);
847 // Cmp may now have a wrong direction, e.g. LEs may now be GEs.
848 // Signedness, and "including equality" are preserved.
850 bool RegToImm = Start->isReg() && End->isImm(); // for (reg..imm)
851 bool RegToReg = Start->isReg() && End->isReg(); // for (reg..reg)
853 int64_t StartV = 0, EndV = 0;
855 StartV = Start->getImm();
857 EndV = End->getImm();
860 // To compute the iteration count, we would need this computation:
861 // Count = (End - Start + (IVBump-1)) / IVBump
862 // or, when CmpHasEqual:
863 // Count = (End - Start + (IVBump-1)+1) / IVBump
864 // The "IVBump-1" part is the adjustment (AdjV). We can avoid
865 // generating an instruction specifically to add it if we can adjust
866 // the immediate values for Start or End.
869 // Need to add 1 to the total iteration count.
872 else if (End->isImm())
878 if (Cmp != Comparison::NE) {
880 StartV -= (IVBump-1);
881 else if (End->isImm())
887 unsigned R = 0, SR = 0;
888 if (Start->isReg()) {
890 SR = Start->getSubReg();
893 SR = End->getSubReg();
895 const TargetRegisterClass *RC = MRI->getRegClass(R);
896 // Hardware loops cannot handle 64-bit registers. If it's a double
897 // register, it has to have a subregister.
898 if (!SR && RC == &Hexagon::DoubleRegsRegClass)
900 const TargetRegisterClass *IntRC = &Hexagon::IntRegsRegClass;
902 // Compute DistR (register with the distance between Start and End).
903 unsigned DistR, DistSR;
905 // Avoid special case, where the start value is an imm(0).
906 if (Start->isImm() && StartV == 0) {
907 DistR = End->getReg();
908 DistSR = End->getSubReg();
910 const MCInstrDesc &SubD = RegToReg ? TII->get(Hexagon::A2_sub) :
911 (RegToImm ? TII->get(Hexagon::A2_subri) :
912 TII->get(Hexagon::A2_addi));
913 if (RegToReg || RegToImm) {
914 Register SubR = MRI->createVirtualRegister(IntRC);
915 MachineInstrBuilder SubIB =
916 BuildMI(*PH, InsertPos, DL, SubD, SubR);
919 SubIB.addReg(End->getReg(), 0, End->getSubReg())
920 .addReg(Start->getReg(), 0, Start->getSubReg());
923 .addReg(Start->getReg(), 0, Start->getSubReg());
926 // If the loop has been unrolled, we should use the original loop count
927 // instead of recalculating the value. This will avoid additional
928 // 'Add' instruction.
929 const MachineInstr *EndValInstr = MRI->getVRegDef(End->getReg());
930 if (EndValInstr->getOpcode() == Hexagon::A2_addi &&
931 EndValInstr->getOperand(1).getSubReg() == 0 &&
932 EndValInstr->getOperand(2).getImm() == StartV) {
933 DistR = EndValInstr->getOperand(1).getReg();
935 Register SubR = MRI->createVirtualRegister(IntRC);
936 MachineInstrBuilder SubIB =
937 BuildMI(*PH, InsertPos, DL, SubD, SubR);
938 SubIB.addReg(End->getReg(), 0, End->getSubReg())
946 // From DistR, compute AdjR (register with the adjusted distance).
947 unsigned AdjR, AdjSR;
953 // Generate CountR = ADD DistR, AdjVal
954 Register AddR = MRI->createVirtualRegister(IntRC);
955 MCInstrDesc const &AddD = TII->get(Hexagon::A2_addi);
956 BuildMI(*PH, InsertPos, DL, AddD, AddR)
957 .addReg(DistR, 0, DistSR)
964 // From AdjR, compute CountR (register with the final count).
965 unsigned CountR, CountSR;
971 // The IV bump is a power of two. Log_2(IV bump) is the shift amount.
972 unsigned Shift = Log2_32(IVBump);
974 // Generate NormR = LSR DistR, Shift.
975 Register LsrR = MRI->createVirtualRegister(IntRC);
976 const MCInstrDesc &LsrD = TII->get(Hexagon::S2_lsr_i_r);
977 BuildMI(*PH, InsertPos, DL, LsrD, LsrR)
978 .addReg(AdjR, 0, AdjSR)
985 return new CountValue(CountValue::CV_Register, CountR, CountSR);
988 /// Return true if the operation is invalid within hardware loop.
989 bool HexagonHardwareLoops::isInvalidLoopOperation(const MachineInstr *MI,
990 bool IsInnerHWLoop) const {
991 // Call is not allowed because the callee may use a hardware loop except for
992 // the case when the call never returns.
993 if (MI->getDesc().isCall())
994 return !TII->doesNotReturn(*MI);
996 // Check if the instruction defines a hardware loop register.
997 using namespace Hexagon;
999 static const unsigned Regs01[] = { LC0, SA0, LC1, SA1 };
1000 static const unsigned Regs1[] = { LC1, SA1 };
1001 auto CheckRegs = IsInnerHWLoop ? makeArrayRef(Regs01, array_lengthof(Regs01))
1002 : makeArrayRef(Regs1, array_lengthof(Regs1));
1003 for (unsigned R : CheckRegs)
1004 if (MI->modifiesRegister(R, TRI))
1010 /// Return true if the loop contains an instruction that inhibits
1011 /// the use of the hardware loop instruction.
1012 bool HexagonHardwareLoops::containsInvalidInstruction(MachineLoop *L,
1013 bool IsInnerHWLoop) const {
1014 LLVM_DEBUG(dbgs() << "\nhw_loop head, "
1015 << printMBBReference(**L->block_begin()));
1016 for (MachineBasicBlock *MBB : L->getBlocks()) {
1017 for (MachineBasicBlock::iterator
1018 MII = MBB->begin(), E = MBB->end(); MII != E; ++MII) {
1019 const MachineInstr *MI = &*MII;
1020 if (isInvalidLoopOperation(MI, IsInnerHWLoop)) {
1021 LLVM_DEBUG(dbgs() << "\nCannot convert to hw_loop due to:";
1030 /// Returns true if the instruction is dead. This was essentially
1031 /// copied from DeadMachineInstructionElim::isDead, but with special cases
1032 /// for inline asm, physical registers and instructions with side effects
1034 bool HexagonHardwareLoops::isDead(const MachineInstr *MI,
1035 SmallVectorImpl<MachineInstr *> &DeadPhis) const {
1036 // Examine each operand.
1037 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
1038 const MachineOperand &MO = MI->getOperand(i);
1039 if (!MO.isReg() || !MO.isDef())
1042 Register Reg = MO.getReg();
1043 if (MRI->use_nodbg_empty(Reg))
1046 using use_nodbg_iterator = MachineRegisterInfo::use_nodbg_iterator;
1048 // This instruction has users, but if the only user is the phi node for the
1049 // parent block, and the only use of that phi node is this instruction, then
1050 // this instruction is dead: both it (and the phi node) can be removed.
1051 use_nodbg_iterator I = MRI->use_nodbg_begin(Reg);
1052 use_nodbg_iterator End = MRI->use_nodbg_end();
1053 if (std::next(I) != End || !I->getParent()->isPHI())
1056 MachineInstr *OnePhi = I->getParent();
1057 for (unsigned j = 0, f = OnePhi->getNumOperands(); j != f; ++j) {
1058 const MachineOperand &OPO = OnePhi->getOperand(j);
1059 if (!OPO.isReg() || !OPO.isDef())
1062 Register OPReg = OPO.getReg();
1063 use_nodbg_iterator nextJ;
1064 for (use_nodbg_iterator J = MRI->use_nodbg_begin(OPReg);
1065 J != End; J = nextJ) {
1066 nextJ = std::next(J);
1067 MachineOperand &Use = *J;
1068 MachineInstr *UseMI = Use.getParent();
1070 // If the phi node has a user that is not MI, bail.
1075 DeadPhis.push_back(OnePhi);
1078 // If there are no defs with uses, the instruction is dead.
1082 void HexagonHardwareLoops::removeIfDead(MachineInstr *MI) {
1083 // This procedure was essentially copied from DeadMachineInstructionElim.
1085 SmallVector<MachineInstr*, 1> DeadPhis;
1086 if (isDead(MI, DeadPhis)) {
1087 LLVM_DEBUG(dbgs() << "HW looping will remove: " << *MI);
1089 // It is possible that some DBG_VALUE instructions refer to this
1090 // instruction. Examine each def operand for such references;
1091 // if found, mark the DBG_VALUE as undef (but don't delete it).
1092 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
1093 const MachineOperand &MO = MI->getOperand(i);
1094 if (!MO.isReg() || !MO.isDef())
1096 Register Reg = MO.getReg();
1097 MachineRegisterInfo::use_iterator nextI;
1098 for (MachineRegisterInfo::use_iterator I = MRI->use_begin(Reg),
1099 E = MRI->use_end(); I != E; I = nextI) {
1100 nextI = std::next(I); // I is invalidated by the setReg
1101 MachineOperand &Use = *I;
1102 MachineInstr *UseMI = I->getParent();
1106 UseMI->getOperand(0).setReg(0U);
1110 MI->eraseFromParent();
1111 for (unsigned i = 0; i < DeadPhis.size(); ++i)
1112 DeadPhis[i]->eraseFromParent();
1116 /// Check if the loop is a candidate for converting to a hardware
1117 /// loop. If so, then perform the transformation.
1119 /// This function works on innermost loops first. A loop can be converted
1120 /// if it is a counting loop; either a register value or an immediate.
1122 /// The code makes several assumptions about the representation of the loop
1124 bool HexagonHardwareLoops::convertToHardwareLoop(MachineLoop *L,
1127 // This is just for sanity.
1128 assert(L->getHeader() && "Loop without a header?");
1130 bool Changed = false;
1131 bool L0Used = false;
1132 bool L1Used = false;
1134 // Process nested loops first.
1135 for (MachineLoop::iterator I = L->begin(), E = L->end(); I != E; ++I) {
1136 Changed |= convertToHardwareLoop(*I, RecL0used, RecL1used);
1137 L0Used |= RecL0used;
1138 L1Used |= RecL1used;
1141 // If a nested loop has been converted, then we can't convert this loop.
1142 if (Changed && L0Used && L1Used)
1149 // Flag used to track loopN instruction:
1150 // 1 - Hardware loop is being generated for the inner most loop.
1151 // 0 - Hardware loop is being generated for the outer loop.
1152 unsigned IsInnerHWLoop = 1;
1155 LOOP_i = Hexagon::J2_loop1i;
1156 LOOP_r = Hexagon::J2_loop1r;
1157 ENDLOOP = Hexagon::ENDLOOP1;
1160 LOOP_i = Hexagon::J2_loop0i;
1161 LOOP_r = Hexagon::J2_loop0r;
1162 ENDLOOP = Hexagon::ENDLOOP0;
1166 // Stop trying after reaching the limit (if any).
1167 int Limit = HWLoopLimit;
1169 if (Counter >= HWLoopLimit)
1175 // Does the loop contain any invalid instructions?
1176 if (containsInvalidInstruction(L, IsInnerHWLoop))
1179 MachineBasicBlock *LastMBB = L->findLoopControlBlock();
1180 // Don't generate hw loop if the loop has more than one exit.
1184 MachineBasicBlock::iterator LastI = LastMBB->getFirstTerminator();
1185 if (LastI == LastMBB->end())
1188 // Is the induction variable bump feeding the latch condition?
1189 if (!fixupInductionVariable(L))
1192 // Ensure the loop has a preheader: the loop instruction will be
1194 MachineBasicBlock *Preheader = MLI->findLoopPreheader(L, SpecPreheader);
1196 Preheader = createPreheaderForLoop(L);
1201 MachineBasicBlock::iterator InsertPos = Preheader->getFirstTerminator();
1203 SmallVector<MachineInstr*, 2> OldInsts;
1204 // Are we able to determine the trip count for the loop?
1205 CountValue *TripCount = getLoopTripCount(L, OldInsts);
1209 // Is the trip count available in the preheader?
1210 if (TripCount->isReg()) {
1211 // There will be a use of the register inserted into the preheader,
1212 // so make sure that the register is actually defined at that point.
1213 MachineInstr *TCDef = MRI->getVRegDef(TripCount->getReg());
1214 MachineBasicBlock *BBDef = TCDef->getParent();
1215 if (!MDT->dominates(BBDef, Preheader))
1219 // Determine the loop start.
1220 MachineBasicBlock *TopBlock = L->getTopBlock();
1221 MachineBasicBlock *ExitingBlock = L->findLoopControlBlock();
1222 MachineBasicBlock *LoopStart = nullptr;
1223 if (ExitingBlock != L->getLoopLatch()) {
1224 MachineBasicBlock *TB = nullptr, *FB = nullptr;
1225 SmallVector<MachineOperand, 2> Cond;
1227 if (TII->analyzeBranch(*ExitingBlock, TB, FB, Cond, false))
1230 if (L->contains(TB))
1232 else if (L->contains(FB))
1238 LoopStart = TopBlock;
1240 // Convert the loop to a hardware loop.
1241 LLVM_DEBUG(dbgs() << "Change to hardware loop at "; L->dump());
1243 if (InsertPos != Preheader->end())
1244 DL = InsertPos->getDebugLoc();
1246 if (TripCount->isReg()) {
1247 // Create a copy of the loop count register.
1248 Register CountReg = MRI->createVirtualRegister(&Hexagon::IntRegsRegClass);
1249 BuildMI(*Preheader, InsertPos, DL, TII->get(TargetOpcode::COPY), CountReg)
1250 .addReg(TripCount->getReg(), 0, TripCount->getSubReg());
1251 // Add the Loop instruction to the beginning of the loop.
1252 BuildMI(*Preheader, InsertPos, DL, TII->get(LOOP_r)).addMBB(LoopStart)
1255 assert(TripCount->isImm() && "Expecting immediate value for trip count");
1256 // Add the Loop immediate instruction to the beginning of the loop,
1257 // if the immediate fits in the instructions. Otherwise, we need to
1258 // create a new virtual register.
1259 int64_t CountImm = TripCount->getImm();
1260 if (!TII->isValidOffset(LOOP_i, CountImm, TRI)) {
1261 Register CountReg = MRI->createVirtualRegister(&Hexagon::IntRegsRegClass);
1262 BuildMI(*Preheader, InsertPos, DL, TII->get(Hexagon::A2_tfrsi), CountReg)
1264 BuildMI(*Preheader, InsertPos, DL, TII->get(LOOP_r))
1265 .addMBB(LoopStart).addReg(CountReg);
1267 BuildMI(*Preheader, InsertPos, DL, TII->get(LOOP_i))
1268 .addMBB(LoopStart).addImm(CountImm);
1271 // Make sure the loop start always has a reference in the CFG. We need
1272 // to create a BlockAddress operand to get this mechanism to work both the
1273 // MachineBasicBlock and BasicBlock objects need the flag set.
1274 LoopStart->setHasAddressTaken();
1275 // This line is needed to set the hasAddressTaken flag on the BasicBlock
1277 BlockAddress::get(const_cast<BasicBlock *>(LoopStart->getBasicBlock()));
1279 // Replace the loop branch with an endloop instruction.
1280 DebugLoc LastIDL = LastI->getDebugLoc();
1281 BuildMI(*LastMBB, LastI, LastIDL, TII->get(ENDLOOP)).addMBB(LoopStart);
1283 // The loop ends with either:
1284 // - a conditional branch followed by an unconditional branch, or
1285 // - a conditional branch to the loop start.
1286 if (LastI->getOpcode() == Hexagon::J2_jumpt ||
1287 LastI->getOpcode() == Hexagon::J2_jumpf) {
1288 // Delete one and change/add an uncond. branch to out of the loop.
1289 MachineBasicBlock *BranchTarget = LastI->getOperand(1).getMBB();
1290 LastI = LastMBB->erase(LastI);
1291 if (!L->contains(BranchTarget)) {
1292 if (LastI != LastMBB->end())
1293 LastI = LastMBB->erase(LastI);
1294 SmallVector<MachineOperand, 0> Cond;
1295 TII->insertBranch(*LastMBB, BranchTarget, nullptr, Cond, LastIDL);
1298 // Conditional branch to loop start; just delete it.
1299 LastMBB->erase(LastI);
1303 // The induction operation and the comparison may now be
1304 // unneeded. If these are unneeded, then remove them.
1305 for (unsigned i = 0; i < OldInsts.size(); ++i)
1306 removeIfDead(OldInsts[i]);
1310 // Set RecL1used and RecL0used only after hardware loop has been
1311 // successfully generated. Doing it earlier can cause wrong loop instruction
1313 if (L0Used) // Loop0 was already used. So, the correct loop must be loop1.
1321 bool HexagonHardwareLoops::orderBumpCompare(MachineInstr *BumpI,
1322 MachineInstr *CmpI) {
1323 assert (BumpI != CmpI && "Bump and compare in the same instruction?");
1325 MachineBasicBlock *BB = BumpI->getParent();
1326 if (CmpI->getParent() != BB)
1329 using instr_iterator = MachineBasicBlock::instr_iterator;
1331 // Check if things are in order to begin with.
1332 for (instr_iterator I(BumpI), E = BB->instr_end(); I != E; ++I)
1337 Register PredR = CmpI->getOperand(0).getReg();
1338 bool FoundBump = false;
1339 instr_iterator CmpIt = CmpI->getIterator(), NextIt = std::next(CmpIt);
1340 for (instr_iterator I = NextIt, E = BB->instr_end(); I != E; ++I) {
1341 MachineInstr *In = &*I;
1342 for (unsigned i = 0, n = In->getNumOperands(); i < n; ++i) {
1343 MachineOperand &MO = In->getOperand(i);
1344 if (MO.isReg() && MO.isUse()) {
1345 if (MO.getReg() == PredR) // Found an intervening use of PredR.
1351 BB->splice(++BumpI->getIterator(), BB, CmpI->getIterator());
1356 assert (FoundBump && "Cannot determine instruction order");
1360 /// This function is required to break recursion. Visiting phis in a loop may
1361 /// result in recursion during compilation. We break the recursion by making
1362 /// sure that we visit a MachineOperand and its definition in a
1363 /// MachineInstruction only once. If we attempt to visit more than once, then
1364 /// there is recursion, and will return false.
1365 bool HexagonHardwareLoops::isLoopFeeder(MachineLoop *L, MachineBasicBlock *A,
1367 const MachineOperand *MO,
1368 LoopFeederMap &LoopFeederPhi) const {
1369 if (LoopFeederPhi.find(MO->getReg()) == LoopFeederPhi.end()) {
1370 LLVM_DEBUG(dbgs() << "\nhw_loop head, "
1371 << printMBBReference(**L->block_begin()));
1372 // Ignore all BBs that form Loop.
1373 for (MachineBasicBlock *MBB : L->getBlocks()) {
1377 MachineInstr *Def = MRI->getVRegDef(MO->getReg());
1378 LoopFeederPhi.insert(std::make_pair(MO->getReg(), Def));
1381 // Already visited node.
1385 /// Return true if a Phi may generate a value that can underflow.
1386 /// This function calls loopCountMayWrapOrUnderFlow for each Phi operand.
1387 bool HexagonHardwareLoops::phiMayWrapOrUnderflow(
1388 MachineInstr *Phi, const MachineOperand *EndVal, MachineBasicBlock *MBB,
1389 MachineLoop *L, LoopFeederMap &LoopFeederPhi) const {
1390 assert(Phi->isPHI() && "Expecting a Phi.");
1391 // Walk through each Phi, and its used operands. Make sure that
1392 // if there is recursion in Phi, we won't generate hardware loops.
1393 for (int i = 1, n = Phi->getNumOperands(); i < n; i += 2)
1394 if (isLoopFeeder(L, MBB, Phi, &(Phi->getOperand(i)), LoopFeederPhi))
1395 if (loopCountMayWrapOrUnderFlow(&(Phi->getOperand(i)), EndVal,
1396 Phi->getParent(), L, LoopFeederPhi))
1401 /// Return true if the induction variable can underflow in the first iteration.
1402 /// An example, is an initial unsigned value that is 0 and is decrement in the
1403 /// first itertion of a do-while loop. In this case, we cannot generate a
1404 /// hardware loop because the endloop instruction does not decrement the loop
1405 /// counter if it is <= 1. We only need to perform this analysis if the
1406 /// initial value is a register.
1408 /// This function assumes the initial value may underfow unless proven
1409 /// otherwise. If the type is signed, then we don't care because signed
1410 /// underflow is undefined. We attempt to prove the initial value is not
1411 /// zero by perfoming a crude analysis of the loop counter. This function
1412 /// checks if the initial value is used in any comparison prior to the loop
1413 /// and, if so, assumes the comparison is a range check. This is inexact,
1414 /// but will catch the simple cases.
1415 bool HexagonHardwareLoops::loopCountMayWrapOrUnderFlow(
1416 const MachineOperand *InitVal, const MachineOperand *EndVal,
1417 MachineBasicBlock *MBB, MachineLoop *L,
1418 LoopFeederMap &LoopFeederPhi) const {
1419 // Only check register values since they are unknown.
1420 if (!InitVal->isReg())
1423 if (!EndVal->isImm())
1426 // A register value that is assigned an immediate is a known value, and it
1427 // won't underflow in the first iteration.
1429 if (checkForImmediate(*InitVal, Imm))
1430 return (EndVal->getImm() == Imm);
1432 Register Reg = InitVal->getReg();
1434 // We don't know the value of a physical register.
1435 if (!Register::isVirtualRegister(Reg))
1438 MachineInstr *Def = MRI->getVRegDef(Reg);
1442 // If the initial value is a Phi or copy and the operands may not underflow,
1443 // then the definition cannot be underflow either.
1444 if (Def->isPHI() && !phiMayWrapOrUnderflow(Def, EndVal, Def->getParent(),
1447 if (Def->isCopy() && !loopCountMayWrapOrUnderFlow(&(Def->getOperand(1)),
1448 EndVal, Def->getParent(),
1452 // Iterate over the uses of the initial value. If the initial value is used
1453 // in a compare, then we assume this is a range check that ensures the loop
1454 // doesn't underflow. This is not an exact test and should be improved.
1455 for (MachineRegisterInfo::use_instr_nodbg_iterator I = MRI->use_instr_nodbg_begin(Reg),
1456 E = MRI->use_instr_nodbg_end(); I != E; ++I) {
1457 MachineInstr *MI = &*I;
1458 unsigned CmpReg1 = 0, CmpReg2 = 0;
1459 int CmpMask = 0, CmpValue = 0;
1461 if (!TII->analyzeCompare(*MI, CmpReg1, CmpReg2, CmpMask, CmpValue))
1464 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
1465 SmallVector<MachineOperand, 2> Cond;
1466 if (TII->analyzeBranch(*MI->getParent(), TBB, FBB, Cond, false))
1469 Comparison::Kind Cmp =
1470 getComparisonKind(MI->getOpcode(), nullptr, nullptr, 0);
1473 if (TII->predOpcodeHasNot(Cond) ^ (TBB != MBB))
1474 Cmp = Comparison::getNegatedComparison(Cmp);
1475 if (CmpReg2 != 0 && CmpReg2 == Reg)
1476 Cmp = Comparison::getSwappedComparison(Cmp);
1478 // Signed underflow is undefined.
1479 if (Comparison::isSigned(Cmp))
1482 // Check if there is a comparison of the initial value. If the initial value
1483 // is greater than or not equal to another value, then assume this is a
1485 if ((Cmp & Comparison::G) || Cmp == Comparison::NE)
1489 // OK - this is a hack that needs to be improved. We really need to analyze
1490 // the instructions performed on the initial value. This works on the simplest
1492 if (!Def->isCopy() && !Def->isPHI())
1498 bool HexagonHardwareLoops::checkForImmediate(const MachineOperand &MO,
1499 int64_t &Val) const {
1507 // MO is a register. Check whether it is defined as an immediate value,
1508 // and if so, get the value of it in TV. That value will then need to be
1509 // processed to handle potential subregisters in MO.
1512 Register R = MO.getReg();
1513 if (!Register::isVirtualRegister(R))
1515 MachineInstr *DI = MRI->getVRegDef(R);
1516 unsigned DOpc = DI->getOpcode();
1518 case TargetOpcode::COPY:
1519 case Hexagon::A2_tfrsi:
1520 case Hexagon::A2_tfrpi:
1521 case Hexagon::CONST32:
1522 case Hexagon::CONST64:
1523 // Call recursively to avoid an extra check whether operand(1) is
1524 // indeed an immediate (it could be a global address, for example),
1525 // plus we can handle COPY at the same time.
1526 if (!checkForImmediate(DI->getOperand(1), TV))
1529 case Hexagon::A2_combineii:
1530 case Hexagon::A4_combineir:
1531 case Hexagon::A4_combineii:
1532 case Hexagon::A4_combineri:
1533 case Hexagon::A2_combinew: {
1534 const MachineOperand &S1 = DI->getOperand(1);
1535 const MachineOperand &S2 = DI->getOperand(2);
1537 if (!checkForImmediate(S1, V1) || !checkForImmediate(S2, V2))
1539 TV = V2 | (static_cast<uint64_t>(V1) << 32);
1542 case TargetOpcode::REG_SEQUENCE: {
1543 const MachineOperand &S1 = DI->getOperand(1);
1544 const MachineOperand &S3 = DI->getOperand(3);
1546 if (!checkForImmediate(S1, V1) || !checkForImmediate(S3, V3))
1548 unsigned Sub2 = DI->getOperand(2).getImm();
1549 unsigned Sub4 = DI->getOperand(4).getImm();
1550 if (Sub2 == Hexagon::isub_lo && Sub4 == Hexagon::isub_hi)
1551 TV = V1 | (V3 << 32);
1552 else if (Sub2 == Hexagon::isub_hi && Sub4 == Hexagon::isub_lo)
1553 TV = V3 | (V1 << 32);
1555 llvm_unreachable("Unexpected form of REG_SEQUENCE");
1563 // By now, we should have successfully obtained the immediate value defining
1564 // the register referenced in MO. Handle a potential use of a subregister.
1565 switch (MO.getSubReg()) {
1566 case Hexagon::isub_lo:
1567 Val = TV & 0xFFFFFFFFULL;
1569 case Hexagon::isub_hi:
1570 Val = (TV >> 32) & 0xFFFFFFFFULL;
1579 void HexagonHardwareLoops::setImmediate(MachineOperand &MO, int64_t Val) {
1586 Register R = MO.getReg();
1587 MachineInstr *DI = MRI->getVRegDef(R);
1589 const TargetRegisterClass *RC = MRI->getRegClass(R);
1590 Register NewR = MRI->createVirtualRegister(RC);
1591 MachineBasicBlock &B = *DI->getParent();
1592 DebugLoc DL = DI->getDebugLoc();
1593 BuildMI(B, DI, DL, TII->get(DI->getOpcode()), NewR).addImm(Val);
1597 static bool isImmValidForOpcode(unsigned CmpOpc, int64_t Imm) {
1598 // These two instructions are not extendable.
1599 if (CmpOpc == Hexagon::A4_cmpbeqi)
1600 return isUInt<8>(Imm);
1601 if (CmpOpc == Hexagon::A4_cmpbgti)
1602 return isInt<8>(Imm);
1603 // The rest of the comparison-with-immediate instructions are extendable.
1607 bool HexagonHardwareLoops::fixupInductionVariable(MachineLoop *L) {
1608 MachineBasicBlock *Header = L->getHeader();
1609 MachineBasicBlock *Latch = L->getLoopLatch();
1610 MachineBasicBlock *ExitingBlock = L->findLoopControlBlock();
1612 if (!(Header && Latch && ExitingBlock))
1615 // These data structures follow the same concept as the corresponding
1616 // ones in findInductionRegister (where some comments are).
1617 using RegisterBump = std::pair<unsigned, int64_t>;
1618 using RegisterInduction = std::pair<unsigned, RegisterBump>;
1619 using RegisterInductionSet = std::set<RegisterInduction>;
1621 // Register candidates for induction variables, with their associated bumps.
1622 RegisterInductionSet IndRegs;
1624 // Look for induction patterns:
1625 // %1 = PHI ..., [ latch, %2 ]
1627 using instr_iterator = MachineBasicBlock::instr_iterator;
1629 for (instr_iterator I = Header->instr_begin(), E = Header->instr_end();
1630 I != E && I->isPHI(); ++I) {
1631 MachineInstr *Phi = &*I;
1633 // Have a PHI instruction.
1634 for (unsigned i = 1, n = Phi->getNumOperands(); i < n; i += 2) {
1635 if (Phi->getOperand(i+1).getMBB() != Latch)
1638 Register PhiReg = Phi->getOperand(i).getReg();
1639 MachineInstr *DI = MRI->getVRegDef(PhiReg);
1641 if (DI->getDesc().isAdd()) {
1642 // If the register operand to the add/sub is the PHI we are looking
1643 // at, this meets the induction pattern.
1644 Register IndReg = DI->getOperand(1).getReg();
1645 MachineOperand &Opnd2 = DI->getOperand(2);
1647 if (MRI->getVRegDef(IndReg) == Phi && checkForImmediate(Opnd2, V)) {
1648 Register UpdReg = DI->getOperand(0).getReg();
1649 IndRegs.insert(std::make_pair(UpdReg, std::make_pair(IndReg, V)));
1655 if (IndRegs.empty())
1658 MachineBasicBlock *TB = nullptr, *FB = nullptr;
1659 SmallVector<MachineOperand,2> Cond;
1660 // AnalyzeBranch returns true if it fails to analyze branch.
1661 bool NotAnalyzed = TII->analyzeBranch(*ExitingBlock, TB, FB, Cond, false);
1662 if (NotAnalyzed || Cond.empty())
1665 if (ExitingBlock != Latch && (TB == Latch || FB == Latch)) {
1666 MachineBasicBlock *LTB = nullptr, *LFB = nullptr;
1667 SmallVector<MachineOperand,2> LCond;
1668 bool NotAnalyzed = TII->analyzeBranch(*Latch, LTB, LFB, LCond, false);
1672 // Since latch is not the exiting block, the latch branch should be an
1673 // unconditional branch to the loop header.
1675 TB = (LTB == Header) ? LTB : LFB;
1677 FB = (LTB == Header) ? LTB : LFB;
1681 // The latch/exit block does not go back to the header.
1684 // FB is the header (i.e., uncond. jump to branch header)
1685 // In this case, the LoopBody -> TB should not be a back edge otherwise
1686 // it could result in an infinite loop after conversion to hw_loop.
1687 // This case can happen when the Latch has two jumps like this:
1688 // Jmp_c OuterLoopHeader <-- TB
1689 // Jmp InnerLoopHeader <-- FB
1690 if (MDT->dominates(TB, FB))
1694 // Expecting a predicate register as a condition. It won't be a hardware
1695 // predicate register at this point yet, just a vreg.
1696 // HexagonInstrInfo::AnalyzeBranch for negated branches inserts imm(0)
1697 // into Cond, followed by the predicate register. For non-negated branches
1698 // it's just the register.
1699 unsigned CSz = Cond.size();
1700 if (CSz != 1 && CSz != 2)
1703 if (!Cond[CSz-1].isReg())
1706 Register P = Cond[CSz - 1].getReg();
1707 MachineInstr *PredDef = MRI->getVRegDef(P);
1709 if (!PredDef->isCompare())
1712 SmallSet<unsigned,2> CmpRegs;
1713 MachineOperand *CmpImmOp = nullptr;
1715 // Go over all operands to the compare and look for immediate and register
1716 // operands. Assume that if the compare has a single register use and a
1717 // single immediate operand, then the register is being compared with the
1719 for (unsigned i = 0, n = PredDef->getNumOperands(); i < n; ++i) {
1720 MachineOperand &MO = PredDef->getOperand(i);
1722 // Skip all implicit references. In one case there was:
1723 // %140 = FCMPUGT32_rr %138, %139, implicit %usr
1724 if (MO.isImplicit())
1727 if (!isImmediate(MO)) {
1728 CmpRegs.insert(MO.getReg());
1731 // Consider the register to be the "immediate" operand.
1736 } else if (MO.isImm()) {
1737 if (CmpImmOp) // A second immediate argument? Confusing. Bail out.
1743 if (CmpRegs.empty())
1746 // Check if the compared register follows the order we want. Fix if needed.
1747 for (RegisterInductionSet::iterator I = IndRegs.begin(), E = IndRegs.end();
1749 // This is a success. If the register used in the comparison is one that
1750 // we have identified as a bumped (updated) induction register, there is
1752 if (CmpRegs.count(I->first))
1755 // Otherwise, if the register being compared comes out of a PHI node,
1756 // and has been recognized as following the induction pattern, and is
1757 // compared against an immediate, we can fix it.
1758 const RegisterBump &RB = I->second;
1759 if (CmpRegs.count(RB.first)) {
1761 // If both operands to the compare instruction are registers, see if
1762 // it can be changed to use induction register as one of the operands.
1763 MachineInstr *IndI = nullptr;
1764 MachineInstr *nonIndI = nullptr;
1765 MachineOperand *IndMO = nullptr;
1766 MachineOperand *nonIndMO = nullptr;
1768 for (unsigned i = 1, n = PredDef->getNumOperands(); i < n; ++i) {
1769 MachineOperand &MO = PredDef->getOperand(i);
1770 if (MO.isReg() && MO.getReg() == RB.first) {
1771 LLVM_DEBUG(dbgs() << "\n DefMI(" << i
1772 << ") = " << *(MRI->getVRegDef(I->first)));
1776 IndI = MRI->getVRegDef(I->first);
1778 } else if (MO.isReg()) {
1779 LLVM_DEBUG(dbgs() << "\n DefMI(" << i
1780 << ") = " << *(MRI->getVRegDef(MO.getReg())));
1784 nonIndI = MRI->getVRegDef(MO.getReg());
1788 if (IndI && nonIndI &&
1789 nonIndI->getOpcode() == Hexagon::A2_addi &&
1790 nonIndI->getOperand(2).isImm() &&
1791 nonIndI->getOperand(2).getImm() == - RB.second) {
1792 bool Order = orderBumpCompare(IndI, PredDef);
1794 IndMO->setReg(I->first);
1795 nonIndMO->setReg(nonIndI->getOperand(1).getReg());
1802 // It is not valid to do this transformation on an unsigned comparison
1803 // because it may underflow.
1804 Comparison::Kind Cmp =
1805 getComparisonKind(PredDef->getOpcode(), nullptr, nullptr, 0);
1806 if (!Cmp || Comparison::isUnsigned(Cmp))
1809 // If the register is being compared against an immediate, try changing
1810 // the compare instruction to use induction register and adjust the
1811 // immediate operand.
1812 int64_t CmpImm = getImmediate(*CmpImmOp);
1813 int64_t V = RB.second;
1814 // Handle Overflow (64-bit).
1815 if (((V > 0) && (CmpImm > INT64_MAX - V)) ||
1816 ((V < 0) && (CmpImm < INT64_MIN - V)))
1819 // Most comparisons of register against an immediate value allow
1820 // the immediate to be constant-extended. There are some exceptions
1821 // though. Make sure the new combination will work.
1822 if (CmpImmOp->isImm())
1823 if (!isImmValidForOpcode(PredDef->getOpcode(), CmpImm))
1826 // Make sure that the compare happens after the bump. Otherwise,
1827 // after the fixup, the compare would use a yet-undefined register.
1828 MachineInstr *BumpI = MRI->getVRegDef(I->first);
1829 bool Order = orderBumpCompare(BumpI, PredDef);
1833 // Finally, fix the compare instruction.
1834 setImmediate(*CmpImmOp, CmpImm);
1835 for (unsigned i = 0, n = PredDef->getNumOperands(); i < n; ++i) {
1836 MachineOperand &MO = PredDef->getOperand(i);
1837 if (MO.isReg() && MO.getReg() == RB.first) {
1838 MO.setReg(I->first);
1848 /// createPreheaderForLoop - Create a preheader for a given loop.
1849 MachineBasicBlock *HexagonHardwareLoops::createPreheaderForLoop(
1851 if (MachineBasicBlock *TmpPH = MLI->findLoopPreheader(L, SpecPreheader))
1853 if (!HWCreatePreheader)
1856 MachineBasicBlock *Header = L->getHeader();
1857 MachineBasicBlock *Latch = L->getLoopLatch();
1858 MachineBasicBlock *ExitingBlock = L->findLoopControlBlock();
1859 MachineFunction *MF = Header->getParent();
1863 if ((!PHFn.empty()) && (PHFn != MF->getName()))
1867 if (!Latch || !ExitingBlock || Header->hasAddressTaken())
1870 using instr_iterator = MachineBasicBlock::instr_iterator;
1872 // Verify that all existing predecessors have analyzable branches
1873 // (or no branches at all).
1874 using MBBVector = std::vector<MachineBasicBlock *>;
1876 MBBVector Preds(Header->pred_begin(), Header->pred_end());
1877 SmallVector<MachineOperand,2> Tmp1;
1878 MachineBasicBlock *TB = nullptr, *FB = nullptr;
1880 if (TII->analyzeBranch(*ExitingBlock, TB, FB, Tmp1, false))
1883 for (MBBVector::iterator I = Preds.begin(), E = Preds.end(); I != E; ++I) {
1884 MachineBasicBlock *PB = *I;
1885 bool NotAnalyzed = TII->analyzeBranch(*PB, TB, FB, Tmp1, false);
1890 MachineBasicBlock *NewPH = MF->CreateMachineBasicBlock();
1891 MF->insert(Header->getIterator(), NewPH);
1893 if (Header->pred_size() > 2) {
1894 // Ensure that the header has only two predecessors: the preheader and
1895 // the loop latch. Any additional predecessors of the header should
1896 // join at the newly created preheader. Inspect all PHI nodes from the
1897 // header and create appropriate corresponding PHI nodes in the preheader.
1899 for (instr_iterator I = Header->instr_begin(), E = Header->instr_end();
1900 I != E && I->isPHI(); ++I) {
1901 MachineInstr *PN = &*I;
1903 const MCInstrDesc &PD = TII->get(TargetOpcode::PHI);
1904 MachineInstr *NewPN = MF->CreateMachineInstr(PD, DL);
1905 NewPH->insert(NewPH->end(), NewPN);
1907 Register PR = PN->getOperand(0).getReg();
1908 const TargetRegisterClass *RC = MRI->getRegClass(PR);
1909 Register NewPR = MRI->createVirtualRegister(RC);
1910 NewPN->addOperand(MachineOperand::CreateReg(NewPR, true));
1912 // Copy all non-latch operands of a header's PHI node to the newly
1913 // created PHI node in the preheader.
1914 for (unsigned i = 1, n = PN->getNumOperands(); i < n; i += 2) {
1915 Register PredR = PN->getOperand(i).getReg();
1916 unsigned PredRSub = PN->getOperand(i).getSubReg();
1917 MachineBasicBlock *PredB = PN->getOperand(i+1).getMBB();
1921 MachineOperand MO = MachineOperand::CreateReg(PredR, false);
1922 MO.setSubReg(PredRSub);
1923 NewPN->addOperand(MO);
1924 NewPN->addOperand(MachineOperand::CreateMBB(PredB));
1927 // Remove copied operands from the old PHI node and add the value
1928 // coming from the preheader's PHI.
1929 for (int i = PN->getNumOperands()-2; i > 0; i -= 2) {
1930 MachineBasicBlock *PredB = PN->getOperand(i+1).getMBB();
1931 if (PredB != Latch) {
1932 PN->RemoveOperand(i+1);
1933 PN->RemoveOperand(i);
1936 PN->addOperand(MachineOperand::CreateReg(NewPR, false));
1937 PN->addOperand(MachineOperand::CreateMBB(NewPH));
1940 assert(Header->pred_size() == 2);
1942 // The header has only two predecessors, but the non-latch predecessor
1943 // is not a preheader (e.g. it has other successors, etc.)
1944 // In such a case we don't need any extra PHI nodes in the new preheader,
1945 // all we need is to adjust existing PHIs in the header to now refer to
1946 // the new preheader.
1947 for (instr_iterator I = Header->instr_begin(), E = Header->instr_end();
1948 I != E && I->isPHI(); ++I) {
1949 MachineInstr *PN = &*I;
1950 for (unsigned i = 1, n = PN->getNumOperands(); i < n; i += 2) {
1951 MachineOperand &MO = PN->getOperand(i+1);
1952 if (MO.getMBB() != Latch)
1958 // "Reroute" the CFG edges to link in the new preheader.
1959 // If any of the predecessors falls through to the header, insert a branch
1960 // to the new preheader in that place.
1961 SmallVector<MachineOperand,1> Tmp2;
1962 SmallVector<MachineOperand,1> EmptyCond;
1966 for (MBBVector::iterator I = Preds.begin(), E = Preds.end(); I != E; ++I) {
1967 MachineBasicBlock *PB = *I;
1970 bool NotAnalyzed = TII->analyzeBranch(*PB, TB, FB, Tmp2, false);
1971 (void)NotAnalyzed; // suppress compiler warning
1972 assert (!NotAnalyzed && "Should be analyzable!");
1973 if (TB != Header && (Tmp2.empty() || FB != Header))
1974 TII->insertBranch(*PB, NewPH, nullptr, EmptyCond, DL);
1975 PB->ReplaceUsesOfBlockWith(Header, NewPH);
1979 // It can happen that the latch block will fall through into the header.
1980 // Insert an unconditional branch to the header.
1982 bool LatchNotAnalyzed = TII->analyzeBranch(*Latch, TB, FB, Tmp2, false);
1983 (void)LatchNotAnalyzed; // suppress compiler warning
1984 assert (!LatchNotAnalyzed && "Should be analyzable!");
1986 TII->insertBranch(*Latch, Header, nullptr, EmptyCond, DL);
1988 // Finally, the branch from the preheader to the header.
1989 TII->insertBranch(*NewPH, Header, nullptr, EmptyCond, DL);
1990 NewPH->addSuccessor(Header);
1992 MachineLoop *ParentLoop = L->getParentLoop();
1994 ParentLoop->addBasicBlockToLoop(NewPH, MLI->getBase());
1996 // Update the dominator information with the new preheader.
1998 if (MachineDomTreeNode *HN = MDT->getNode(Header)) {
1999 if (MachineDomTreeNode *DHN = HN->getIDom()) {
2000 MDT->addNewBlock(NewPH, DHN->getBlock());
2001 MDT->changeImmediateDominator(Header, NewPH);