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 nested hardware loops.
25 // - No function calls in loops.
27 //===----------------------------------------------------------------------===//
29 #define DEBUG_TYPE "hwloops"
30 #include "llvm/ADT/SmallSet.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"
44 #include "HexagonTargetMachine.h"
52 static cl::opt<int> HWLoopLimit("max-hwloop", cl::Hidden, cl::init(-1));
55 STATISTIC(NumHWLoops, "Number of loops converted to hardware loops");
58 void initializeHexagonHardwareLoopsPass(PassRegistry&);
63 struct HexagonHardwareLoops : public MachineFunctionPass {
65 MachineRegisterInfo *MRI;
66 MachineDominatorTree *MDT;
67 const HexagonTargetMachine *TM;
68 const HexagonInstrInfo *TII;
69 const HexagonRegisterInfo *TRI;
77 HexagonHardwareLoops() : MachineFunctionPass(ID) {
78 initializeHexagonHardwareLoopsPass(*PassRegistry::getPassRegistry());
81 virtual bool runOnMachineFunction(MachineFunction &MF);
83 const char *getPassName() const { return "Hexagon Hardware Loops"; }
85 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
86 AU.addRequired<MachineDominatorTree>();
87 AU.addRequired<MachineLoopInfo>();
88 MachineFunctionPass::getAnalysisUsage(AU);
92 /// Kinds of comparisons in the compare instructions.
97 L = 0x04, // Less-than property.
98 G = 0x08, // Greater-than property.
99 U = 0x40, // Unsigned property.
110 static Kind getSwappedComparison(Kind Cmp) {
111 assert ((!((Cmp & L) && (Cmp & G))) && "Malformed comparison operator");
112 if ((Cmp & L) || (Cmp & G))
113 return (Kind)(Cmp ^ (L|G));
118 /// \brief Find the register that contains the loop controlling
119 /// induction variable.
120 /// If successful, it will return true and set the \p Reg, \p IVBump
121 /// and \p IVOp arguments. Otherwise it will return false.
122 /// The returned induction register is the register R that follows the
123 /// following induction pattern:
125 /// R = phi ..., [ R.next, LatchBlock ]
126 /// R.next = R + #bump
127 /// if (R.next < #N) goto loop
128 /// IVBump is the immediate value added to R, and IVOp is the instruction
129 /// "R.next = R + #bump".
130 bool findInductionRegister(MachineLoop *L, unsigned &Reg,
131 int64_t &IVBump, MachineInstr *&IVOp) const;
133 /// \brief Analyze the statements in a loop to determine if the loop
134 /// has a computable trip count and, if so, return a value that represents
135 /// the trip count expression.
136 CountValue *getLoopTripCount(MachineLoop *L,
137 SmallVector<MachineInstr*, 2> &OldInsts);
139 /// \brief Return the expression that represents the number of times
140 /// a loop iterates. The function takes the operands that represent the
141 /// loop start value, loop end value, and induction value. Based upon
142 /// these operands, the function attempts to compute the trip count.
143 /// If the trip count is not directly available (as an immediate value,
144 /// or a register), the function will attempt to insert computation of it
145 /// to the loop's preheader.
146 CountValue *computeCount(MachineLoop *Loop,
147 const MachineOperand *Start,
148 const MachineOperand *End,
151 Comparison::Kind Cmp) const;
153 /// \brief Return true if the instruction is not valid within a hardware
155 bool isInvalidLoopOperation(const MachineInstr *MI) const;
157 /// \brief Return true if the loop contains an instruction that inhibits
158 /// using the hardware loop.
159 bool containsInvalidInstruction(MachineLoop *L) const;
161 /// \brief Given a loop, check if we can convert it to a hardware loop.
162 /// If so, then perform the conversion and return true.
163 bool convertToHardwareLoop(MachineLoop *L);
165 /// \brief Return true if the instruction is now dead.
166 bool isDead(const MachineInstr *MI,
167 SmallVector<MachineInstr*, 1> &DeadPhis) const;
169 /// \brief Remove the instruction if it is now dead.
170 void removeIfDead(MachineInstr *MI);
172 /// \brief Make sure that the "bump" instruction executes before the
173 /// compare. We need that for the IV fixup, so that the compare
174 /// instruction would not use a bumped value that has not yet been
175 /// defined. If the instructions are out of order, try to reorder them.
176 bool orderBumpCompare(MachineInstr *BumpI, MachineInstr *CmpI);
178 /// \brief Get the instruction that loads an immediate value into \p R,
179 /// or 0 if such an instruction does not exist.
180 MachineInstr *defWithImmediate(unsigned R);
182 /// \brief Get the immediate value referenced to by \p MO, either for
183 /// immediate operands, or for register operands, where the register
184 /// was defined with an immediate value.
185 int64_t getImmediate(MachineOperand &MO);
187 /// \brief Reset the given machine operand to now refer to a new immediate
188 /// value. Assumes that the operand was already referencing an immediate
189 /// value, either directly, or via a register.
190 void setImmediate(MachineOperand &MO, int64_t Val);
192 /// \brief Fix the data flow of the induction varible.
193 /// The desired flow is: phi ---> bump -+-> comparison-in-latch.
196 /// where "bump" is the increment of the induction variable:
197 /// iv = iv + #const.
198 /// Due to some prior code transformations, the actual flow may look
200 /// phi -+-> bump ---> back to phi
202 /// +-> comparison-in-latch (against upper_bound-bump),
203 /// i.e. the comparison that controls the loop execution may be using
204 /// the value of the induction variable from before the increment.
206 /// Return true if the loop's flow is the desired one (i.e. it's
207 /// either been fixed, or no fixing was necessary).
208 /// Otherwise, return false. This can happen if the induction variable
209 /// couldn't be identified, or if the value in the latch's comparison
210 /// cannot be adjusted to reflect the post-bump value.
211 bool fixupInductionVariable(MachineLoop *L);
213 /// \brief Given a loop, if it does not have a preheader, create one.
214 /// Return the block that is the preheader.
215 MachineBasicBlock *createPreheaderForLoop(MachineLoop *L);
218 char HexagonHardwareLoops::ID = 0;
220 int HexagonHardwareLoops::Counter = 0;
223 /// \brief Abstraction for a trip count of a loop. A smaller vesrsion
224 /// of the MachineOperand class without the concerns of changing the
225 /// operand representation.
228 enum CountValueType {
243 explicit CountValue(CountValueType t, unsigned v, unsigned u = 0) {
245 if (Kind == CV_Register) {
252 bool isReg() const { return Kind == CV_Register; }
253 bool isImm() const { return Kind == CV_Immediate; }
255 unsigned getReg() const {
256 assert(isReg() && "Wrong CountValue accessor");
257 return Contents.R.Reg;
259 unsigned getSubReg() const {
260 assert(isReg() && "Wrong CountValue accessor");
261 return Contents.R.Sub;
263 unsigned getImm() const {
264 assert(isImm() && "Wrong CountValue accessor");
265 return Contents.ImmVal;
268 void print(raw_ostream &OS, const TargetMachine *TM = 0) const {
269 const TargetRegisterInfo *TRI = TM ? TM->getRegisterInfo() : 0;
270 if (isReg()) { OS << PrintReg(Contents.R.Reg, TRI, Contents.R.Sub); }
271 if (isImm()) { OS << Contents.ImmVal; }
274 } // end anonymous namespace
277 INITIALIZE_PASS_BEGIN(HexagonHardwareLoops, "hwloops",
278 "Hexagon Hardware Loops", false, false)
279 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
280 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
281 INITIALIZE_PASS_END(HexagonHardwareLoops, "hwloops",
282 "Hexagon Hardware Loops", false, false)
285 /// \brief Returns true if the instruction is a hardware loop instruction.
286 static bool isHardwareLoop(const MachineInstr *MI) {
287 return MI->getOpcode() == Hexagon::LOOP0_r ||
288 MI->getOpcode() == Hexagon::LOOP0_i;
291 FunctionPass *llvm::createHexagonHardwareLoops() {
292 return new HexagonHardwareLoops();
296 bool HexagonHardwareLoops::runOnMachineFunction(MachineFunction &MF) {
297 DEBUG(dbgs() << "********* Hexagon Hardware Loops *********\n");
299 bool Changed = false;
301 MLI = &getAnalysis<MachineLoopInfo>();
302 MRI = &MF.getRegInfo();
303 MDT = &getAnalysis<MachineDominatorTree>();
304 TM = static_cast<const HexagonTargetMachine*>(&MF.getTarget());
305 TII = static_cast<const HexagonInstrInfo*>(TM->getInstrInfo());
306 TRI = static_cast<const HexagonRegisterInfo*>(TM->getRegisterInfo());
308 for (MachineLoopInfo::iterator I = MLI->begin(), E = MLI->end();
311 if (!L->getParentLoop())
312 Changed |= convertToHardwareLoop(L);
319 bool HexagonHardwareLoops::findInductionRegister(MachineLoop *L,
324 MachineBasicBlock *Header = L->getHeader();
325 MachineBasicBlock *Preheader = L->getLoopPreheader();
326 MachineBasicBlock *Latch = L->getLoopLatch();
327 if (!Header || !Preheader || !Latch)
330 // This pair represents an induction register together with an immediate
331 // value that will be added to it in each loop iteration.
332 typedef std::pair<unsigned,int64_t> RegisterBump;
334 // Mapping: R.next -> (R, bump), where R, R.next and bump are derived
335 // from an induction operation
337 // where bump is an immediate value.
338 typedef std::map<unsigned,RegisterBump> InductionMap;
342 typedef MachineBasicBlock::instr_iterator instr_iterator;
343 for (instr_iterator I = Header->instr_begin(), E = Header->instr_end();
344 I != E && I->isPHI(); ++I) {
345 MachineInstr *Phi = &*I;
347 // Have a PHI instruction. Get the operand that corresponds to the
348 // latch block, and see if is a result of an addition of form "reg+imm",
349 // where the "reg" is defined by the PHI node we are looking at.
350 for (unsigned i = 1, n = Phi->getNumOperands(); i < n; i += 2) {
351 if (Phi->getOperand(i+1).getMBB() != Latch)
354 unsigned PhiOpReg = Phi->getOperand(i).getReg();
355 MachineInstr *DI = MRI->getVRegDef(PhiOpReg);
356 unsigned UpdOpc = DI->getOpcode();
357 bool isAdd = (UpdOpc == Hexagon::ADD_ri);
360 // If the register operand to the add is the PHI we're
361 // looking at, this meets the induction pattern.
362 unsigned IndReg = DI->getOperand(1).getReg();
363 if (MRI->getVRegDef(IndReg) == Phi) {
364 unsigned UpdReg = DI->getOperand(0).getReg();
365 int64_t V = DI->getOperand(2).getImm();
366 IndMap.insert(std::make_pair(UpdReg, std::make_pair(IndReg, V)));
372 SmallVector<MachineOperand,2> Cond;
373 MachineBasicBlock *TB = 0, *FB = 0;
374 bool NotAnalyzed = TII->AnalyzeBranch(*Latch, TB, FB, Cond, false);
378 unsigned CSz = Cond.size();
379 assert (CSz == 1 || CSz == 2);
380 unsigned PredR = Cond[CSz-1].getReg();
382 MachineInstr *PredI = MRI->getVRegDef(PredR);
383 if (!PredI->isCompare())
386 unsigned CmpReg1 = 0, CmpReg2 = 0;
387 int CmpImm = 0, CmpMask = 0;
388 bool CmpAnalyzed = TII->analyzeCompare(PredI, CmpReg1, CmpReg2,
390 // Fail if the compare was not analyzed, or it's not comparing a register
391 // with an immediate value. Not checking the mask here, since we handle
392 // the individual compare opcodes (including CMPb) later on.
396 // Exactly one of the input registers to the comparison should be among
397 // the induction registers.
398 InductionMap::iterator IndMapEnd = IndMap.end();
399 InductionMap::iterator F = IndMapEnd;
401 InductionMap::iterator F1 = IndMap.find(CmpReg1);
406 InductionMap::iterator F2 = IndMap.find(CmpReg2);
407 if (F2 != IndMapEnd) {
416 Reg = F->second.first;
417 IVBump = F->second.second;
418 IVOp = MRI->getVRegDef(F->first);
423 /// \brief Analyze the statements in a loop to determine if the loop has
424 /// a computable trip count and, if so, return a value that represents
425 /// the trip count expression.
427 /// This function iterates over the phi nodes in the loop to check for
428 /// induction variable patterns that are used in the calculation for
429 /// the number of time the loop is executed.
430 CountValue *HexagonHardwareLoops::getLoopTripCount(MachineLoop *L,
431 SmallVector<MachineInstr*, 2> &OldInsts) {
432 MachineBasicBlock *TopMBB = L->getTopBlock();
433 MachineBasicBlock::pred_iterator PI = TopMBB->pred_begin();
434 assert(PI != TopMBB->pred_end() &&
435 "Loop must have more than one incoming edge!");
436 MachineBasicBlock *Backedge = *PI++;
437 if (PI == TopMBB->pred_end()) // dead loop?
439 MachineBasicBlock *Incoming = *PI++;
440 if (PI != TopMBB->pred_end()) // multiple backedges?
443 // Make sure there is one incoming and one backedge and determine which
445 if (L->contains(Incoming)) {
446 if (L->contains(Backedge))
448 std::swap(Incoming, Backedge);
449 } else if (!L->contains(Backedge))
452 // Look for the cmp instruction to determine if we can get a useful trip
453 // count. The trip count can be either a register or an immediate. The
454 // location of the value depends upon the type (reg or imm).
455 MachineBasicBlock *Latch = L->getLoopLatch();
462 bool FoundIV = findInductionRegister(L, IVReg, IVBump, IVOp);
466 MachineBasicBlock *Preheader = L->getLoopPreheader();
468 MachineOperand *InitialValue = 0;
469 MachineInstr *IV_Phi = MRI->getVRegDef(IVReg);
470 for (unsigned i = 1, n = IV_Phi->getNumOperands(); i < n; i += 2) {
471 MachineBasicBlock *MBB = IV_Phi->getOperand(i+1).getMBB();
472 if (MBB == Preheader)
473 InitialValue = &IV_Phi->getOperand(i);
474 else if (MBB == Latch)
475 IVReg = IV_Phi->getOperand(i).getReg(); // Want IV reg after bump.
480 SmallVector<MachineOperand,2> Cond;
481 MachineBasicBlock *TB = 0, *FB = 0;
482 bool NotAnalyzed = TII->AnalyzeBranch(*Latch, TB, FB, Cond, false);
486 MachineBasicBlock *Header = L->getHeader();
487 // TB must be non-null. If FB is also non-null, one of them must be
488 // the header. Otherwise, branch to TB could be exiting the loop, and
489 // the fall through can go to the header.
490 assert (TB && "Latch block without a branch?");
491 assert ((!FB || TB == Header || FB == Header) && "Branches not to header?");
492 if (!TB || (FB && TB != Header && FB != Header))
495 // Branches of form "if (!P) ..." cause HexagonInstrInfo::AnalyzeBranch
496 // to put imm(0), followed by P in the vector Cond.
497 // If TB is not the header, it means that the "not-taken" path must lead
499 bool Negated = (Cond.size() > 1) ^ (TB != Header);
500 unsigned PredReg = Cond[Cond.size()-1].getReg();
501 MachineInstr *CondI = MRI->getVRegDef(PredReg);
502 unsigned CondOpc = CondI->getOpcode();
504 unsigned CmpReg1 = 0, CmpReg2 = 0;
505 int Mask = 0, ImmValue = 0;
506 bool AnalyzedCmp = TII->analyzeCompare(CondI, CmpReg1, CmpReg2,
511 // The comparison operator type determines how we compute the loop
513 OldInsts.push_back(CondI);
514 OldInsts.push_back(IVOp);
516 // Sadly, the following code gets information based on the position
517 // of the operands in the compare instruction. This has to be done
518 // this way, because the comparisons check for a specific relationship
519 // between the operands (e.g. is-less-than), rather than to find out
520 // what relationship the operands are in (as on PPC).
521 Comparison::Kind Cmp;
522 bool isSwapped = false;
523 const MachineOperand &Op1 = CondI->getOperand(1);
524 const MachineOperand &Op2 = CondI->getOperand(2);
525 const MachineOperand *EndValue = 0;
528 if (Op2.isImm() || Op1.getReg() == IVReg)
540 case Hexagon::CMPEQri:
541 case Hexagon::CMPEQrr:
542 Cmp = !Negated ? Comparison::EQ : Comparison::NE;
544 case Hexagon::CMPLTrr:
545 Cmp = !Negated ? Comparison::LTs : Comparison::GEs;
547 case Hexagon::CMPLTUrr:
548 Cmp = !Negated ? Comparison::LTu : Comparison::GEu;
550 case Hexagon::CMPGTUri:
551 case Hexagon::CMPGTUrr:
552 Cmp = !Negated ? Comparison::GTu : Comparison::LEu;
554 case Hexagon::CMPGTri:
555 case Hexagon::CMPGTrr:
556 Cmp = !Negated ? Comparison::GTs : Comparison::LEs;
558 // Very limited support for byte/halfword compares.
559 case Hexagon::CMPbEQri_V4:
560 case Hexagon::CMPhEQri_V4: {
565 // Since the comparisons are "ri", the EndValue should be an
566 // immediate. Check it just in case.
567 assert(EndValue->isImm() && "Unrecognized latch comparison");
568 EndV = EndValue->getImm();
569 // Allow InitialValue to be a register defined with an immediate.
570 if (InitialValue->isReg()) {
571 if (!defWithImmediate(InitialValue->getReg()))
573 InitV = getImmediate(*InitialValue);
575 assert(InitialValue->isImm());
576 InitV = InitialValue->getImm();
580 if (CondOpc == Hexagon::CMPbEQri_V4) {
581 if (!isInt<8>(InitV) || !isInt<8>(EndV))
583 } else { // Hexagon::CMPhEQri_V4
584 if (!isInt<16>(InitV) || !isInt<16>(EndV))
587 Cmp = !Negated ? Comparison::EQ : Comparison::NE;
595 Cmp = Comparison::getSwappedComparison(Cmp);
597 if (InitialValue->isReg()) {
598 unsigned R = InitialValue->getReg();
599 MachineBasicBlock *DefBB = MRI->getVRegDef(R)->getParent();
600 if (!MDT->properlyDominates(DefBB, Header))
602 OldInsts.push_back(MRI->getVRegDef(R));
604 if (EndValue->isReg()) {
605 unsigned R = EndValue->getReg();
606 MachineBasicBlock *DefBB = MRI->getVRegDef(R)->getParent();
607 if (!MDT->properlyDominates(DefBB, Header))
611 return computeCount(L, InitialValue, EndValue, IVReg, IVBump, Cmp);
614 /// \brief Helper function that returns the expression that represents the
615 /// number of times a loop iterates. The function takes the operands that
616 /// represent the loop start value, loop end value, and induction value.
617 /// Based upon these operands, the function attempts to compute the trip count.
618 CountValue *HexagonHardwareLoops::computeCount(MachineLoop *Loop,
619 const MachineOperand *Start,
620 const MachineOperand *End,
623 Comparison::Kind Cmp) const {
624 // Cannot handle comparison EQ, i.e. while (A == B).
625 if (Cmp == Comparison::EQ)
628 // Check if either the start or end values are an assignment of an immediate.
629 // If so, use the immediate value rather than the register.
630 if (Start->isReg()) {
631 const MachineInstr *StartValInstr = MRI->getVRegDef(Start->getReg());
632 if (StartValInstr && StartValInstr->getOpcode() == Hexagon::TFRI)
633 Start = &StartValInstr->getOperand(1);
636 const MachineInstr *EndValInstr = MRI->getVRegDef(End->getReg());
637 if (EndValInstr && EndValInstr->getOpcode() == Hexagon::TFRI)
638 End = &EndValInstr->getOperand(1);
641 assert (Start->isReg() || Start->isImm());
642 assert (End->isReg() || End->isImm());
644 bool CmpLess = Cmp & Comparison::L;
645 bool CmpGreater = Cmp & Comparison::G;
646 bool CmpHasEqual = Cmp & Comparison::EQ;
648 // Avoid certain wrap-arounds. This doesn't detect all wrap-arounds.
649 // If loop executes while iv is "less" with the iv value going down, then
651 if (CmpLess && IVBump < 0)
653 // If loop executes while iv is "greater" with the iv value going up, then
655 if (CmpGreater && IVBump > 0)
658 if (Start->isImm() && End->isImm()) {
659 // Both, start and end are immediates.
660 int64_t StartV = Start->getImm();
661 int64_t EndV = End->getImm();
662 int64_t Dist = EndV - StartV;
666 bool Exact = (Dist % IVBump) == 0;
668 if (Cmp == Comparison::NE) {
671 if ((Dist < 0) ^ (IVBump < 0))
675 // For comparisons that include the final value (i.e. include equality
676 // with the final value), we need to increase the distance by 1.
678 Dist = Dist > 0 ? Dist+1 : Dist-1;
680 // assert (CmpLess => Dist > 0);
681 assert ((!CmpLess || Dist > 0) && "Loop should never iterate!");
682 // assert (CmpGreater => Dist < 0);
683 assert ((!CmpGreater || Dist < 0) && "Loop should never iterate!");
685 // "Normalized" distance, i.e. with the bump set to +-1.
686 int64_t Dist1 = (IVBump > 0) ? (Dist + (IVBump-1)) / IVBump
687 : (-Dist + (-IVBump-1)) / (-IVBump);
688 assert (Dist1 > 0 && "Fishy thing. Both operands have the same sign.");
690 uint64_t Count = Dist1;
692 if (Count > 0xFFFFFFFFULL)
695 return new CountValue(CountValue::CV_Immediate, Count);
698 // A general case: Start and End are some values, but the actual
699 // iteration count may not be available. If it is not, insert
700 // a computation of it into the preheader.
702 // If the induction variable bump is not a power of 2, quit.
703 // Othwerise we'd need a general integer division.
704 if (!isPowerOf2_64(abs64(IVBump)))
707 MachineBasicBlock *PH = Loop->getLoopPreheader();
708 assert (PH && "Should have a preheader by now");
709 MachineBasicBlock::iterator InsertPos = PH->getFirstTerminator();
710 DebugLoc DL = (InsertPos != PH->end()) ? InsertPos->getDebugLoc()
713 // If Start is an immediate and End is a register, the trip count
714 // will be "reg - imm". Hexagon's "subtract immediate" instruction
715 // is actually "reg + -imm".
717 // If the loop IV is going downwards, i.e. if the bump is negative,
718 // then the iteration count (computed as End-Start) will need to be
719 // negated. To avoid the negation, just swap Start and End.
721 std::swap(Start, End);
724 // Cmp may now have a wrong direction, e.g. LEs may now be GEs.
725 // Signedness, and "including equality" are preserved.
727 bool RegToImm = Start->isReg() && End->isImm(); // for (reg..imm)
728 bool RegToReg = Start->isReg() && End->isReg(); // for (reg..reg)
730 int64_t StartV = 0, EndV = 0;
732 StartV = Start->getImm();
734 EndV = End->getImm();
737 // To compute the iteration count, we would need this computation:
738 // Count = (End - Start + (IVBump-1)) / IVBump
739 // or, when CmpHasEqual:
740 // Count = (End - Start + (IVBump-1)+1) / IVBump
741 // The "IVBump-1" part is the adjustment (AdjV). We can avoid
742 // generating an instruction specifically to add it if we can adjust
743 // the immediate values for Start or End.
746 // Need to add 1 to the total iteration count.
749 else if (End->isImm())
755 if (Cmp != Comparison::NE) {
757 StartV -= (IVBump-1);
758 else if (End->isImm())
764 unsigned R = 0, SR = 0;
765 if (Start->isReg()) {
767 SR = Start->getSubReg();
770 SR = End->getSubReg();
772 const TargetRegisterClass *RC = MRI->getRegClass(R);
773 // Hardware loops cannot handle 64-bit registers. If it's a double
774 // register, it has to have a subregister.
775 if (!SR && RC == &Hexagon::DoubleRegsRegClass)
777 const TargetRegisterClass *IntRC = &Hexagon::IntRegsRegClass;
779 // Compute DistR (register with the distance between Start and End).
780 unsigned DistR, DistSR;
782 // Avoid special case, where the start value is an imm(0).
783 if (Start->isImm() && StartV == 0) {
784 DistR = End->getReg();
785 DistSR = End->getSubReg();
787 const MCInstrDesc &SubD = RegToReg ? TII->get(Hexagon::SUB_rr) :
788 (RegToImm ? TII->get(Hexagon::SUB_ri) :
789 TII->get(Hexagon::ADD_ri));
790 unsigned SubR = MRI->createVirtualRegister(IntRC);
791 MachineInstrBuilder SubIB =
792 BuildMI(*PH, InsertPos, DL, SubD, SubR);
795 SubIB.addReg(End->getReg(), 0, End->getSubReg())
796 .addReg(Start->getReg(), 0, Start->getSubReg());
797 } else if (RegToImm) {
799 .addReg(Start->getReg(), 0, Start->getSubReg());
801 SubIB.addReg(End->getReg(), 0, End->getSubReg())
808 // From DistR, compute AdjR (register with the adjusted distance).
809 unsigned AdjR, AdjSR;
815 // Generate CountR = ADD DistR, AdjVal
816 unsigned AddR = MRI->createVirtualRegister(IntRC);
817 const MCInstrDesc &AddD = TII->get(Hexagon::ADD_ri);
818 BuildMI(*PH, InsertPos, DL, AddD, AddR)
819 .addReg(DistR, 0, DistSR)
826 // From AdjR, compute CountR (register with the final count).
827 unsigned CountR, CountSR;
833 // The IV bump is a power of two. Log_2(IV bump) is the shift amount.
834 unsigned Shift = Log2_32(IVBump);
836 // Generate NormR = LSR DistR, Shift.
837 unsigned LsrR = MRI->createVirtualRegister(IntRC);
838 const MCInstrDesc &LsrD = TII->get(Hexagon::LSR_ri);
839 BuildMI(*PH, InsertPos, DL, LsrD, LsrR)
840 .addReg(AdjR, 0, AdjSR)
847 return new CountValue(CountValue::CV_Register, CountR, CountSR);
851 /// \brief Return true if the operation is invalid within hardware loop.
852 bool HexagonHardwareLoops::isInvalidLoopOperation(
853 const MachineInstr *MI) const {
855 // call is not allowed because the callee may use a hardware loop
856 if (MI->getDesc().isCall())
859 // do not allow nested hardware loops
860 if (isHardwareLoop(MI))
863 // check if the instruction defines a hardware loop register
864 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
865 const MachineOperand &MO = MI->getOperand(i);
866 if (!MO.isReg() || !MO.isDef())
868 unsigned R = MO.getReg();
869 if (R == Hexagon::LC0 || R == Hexagon::LC1 ||
870 R == Hexagon::SA0 || R == Hexagon::SA1)
877 /// \brief - Return true if the loop contains an instruction that inhibits
878 /// the use of the hardware loop function.
879 bool HexagonHardwareLoops::containsInvalidInstruction(MachineLoop *L) const {
880 const std::vector<MachineBasicBlock*> Blocks = L->getBlocks();
881 for (unsigned i = 0, e = Blocks.size(); i != e; ++i) {
882 MachineBasicBlock *MBB = Blocks[i];
883 for (MachineBasicBlock::iterator
884 MII = MBB->begin(), E = MBB->end(); MII != E; ++MII) {
885 const MachineInstr *MI = &*MII;
886 if (isInvalidLoopOperation(MI))
894 /// \brief Returns true if the instruction is dead. This was essentially
895 /// copied from DeadMachineInstructionElim::isDead, but with special cases
896 /// for inline asm, physical registers and instructions with side effects
898 bool HexagonHardwareLoops::isDead(const MachineInstr *MI,
899 SmallVector<MachineInstr*, 1> &DeadPhis) const {
900 // Examine each operand.
901 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
902 const MachineOperand &MO = MI->getOperand(i);
903 if (!MO.isReg() || !MO.isDef())
906 unsigned Reg = MO.getReg();
907 if (MRI->use_nodbg_empty(Reg))
910 typedef MachineRegisterInfo::use_nodbg_iterator use_nodbg_iterator;
912 // This instruction has users, but if the only user is the phi node for the
913 // parent block, and the only use of that phi node is this instruction, then
914 // this instruction is dead: both it (and the phi node) can be removed.
915 use_nodbg_iterator I = MRI->use_nodbg_begin(Reg);
916 use_nodbg_iterator End = MRI->use_nodbg_end();
917 if (llvm::next(I) != End || !I.getOperand().getParent()->isPHI())
920 MachineInstr *OnePhi = I.getOperand().getParent();
921 for (unsigned j = 0, f = OnePhi->getNumOperands(); j != f; ++j) {
922 const MachineOperand &OPO = OnePhi->getOperand(j);
923 if (!OPO.isReg() || !OPO.isDef())
926 unsigned OPReg = OPO.getReg();
927 use_nodbg_iterator nextJ;
928 for (use_nodbg_iterator J = MRI->use_nodbg_begin(OPReg);
929 J != End; J = nextJ) {
930 nextJ = llvm::next(J);
931 MachineOperand &Use = J.getOperand();
932 MachineInstr *UseMI = Use.getParent();
934 // If the phi node has a user that is not MI, bail...
939 DeadPhis.push_back(OnePhi);
942 // If there are no defs with uses, the instruction is dead.
946 void HexagonHardwareLoops::removeIfDead(MachineInstr *MI) {
947 // This procedure was essentially copied from DeadMachineInstructionElim.
949 SmallVector<MachineInstr*, 1> DeadPhis;
950 if (isDead(MI, DeadPhis)) {
951 DEBUG(dbgs() << "HW looping will remove: " << *MI);
953 // It is possible that some DBG_VALUE instructions refer to this
954 // instruction. Examine each def operand for such references;
955 // if found, mark the DBG_VALUE as undef (but don't delete it).
956 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
957 const MachineOperand &MO = MI->getOperand(i);
958 if (!MO.isReg() || !MO.isDef())
960 unsigned Reg = MO.getReg();
961 MachineRegisterInfo::use_iterator nextI;
962 for (MachineRegisterInfo::use_iterator I = MRI->use_begin(Reg),
963 E = MRI->use_end(); I != E; I = nextI) {
964 nextI = llvm::next(I); // I is invalidated by the setReg
965 MachineOperand &Use = I.getOperand();
966 MachineInstr *UseMI = Use.getParent();
970 UseMI->getOperand(0).setReg(0U);
971 // This may also be a "instr -> phi -> instr" case which can
976 MI->eraseFromParent();
977 for (unsigned i = 0; i < DeadPhis.size(); ++i)
978 DeadPhis[i]->eraseFromParent();
982 /// \brief Check if the loop is a candidate for converting to a hardware
983 /// loop. If so, then perform the transformation.
985 /// This function works on innermost loops first. A loop can be converted
986 /// if it is a counting loop; either a register value or an immediate.
988 /// The code makes several assumptions about the representation of the loop
990 bool HexagonHardwareLoops::convertToHardwareLoop(MachineLoop *L) {
991 // This is just for sanity.
992 assert(L->getHeader() && "Loop without a header?");
994 bool Changed = false;
995 // Process nested loops first.
996 for (MachineLoop::iterator I = L->begin(), E = L->end(); I != E; ++I)
997 Changed |= convertToHardwareLoop(*I);
999 // If a nested loop has been converted, then we can't convert this loop.
1004 // Stop trying after reaching the limit (if any).
1005 int Limit = HWLoopLimit;
1007 if (Counter >= HWLoopLimit)
1013 // Does the loop contain any invalid instructions?
1014 if (containsInvalidInstruction(L))
1017 // Is the induction variable bump feeding the latch condition?
1018 if (!fixupInductionVariable(L))
1021 MachineBasicBlock *LastMBB = L->getExitingBlock();
1022 // Don't generate hw loop if the loop has more than one exit.
1026 MachineBasicBlock::iterator LastI = LastMBB->getFirstTerminator();
1027 if (LastI == LastMBB->end())
1030 // Ensure the loop has a preheader: the loop instruction will be
1032 bool NewPreheader = false;
1033 MachineBasicBlock *Preheader = L->getLoopPreheader();
1035 Preheader = createPreheaderForLoop(L);
1038 NewPreheader = true;
1040 MachineBasicBlock::iterator InsertPos = Preheader->getFirstTerminator();
1042 SmallVector<MachineInstr*, 2> OldInsts;
1043 // Are we able to determine the trip count for the loop?
1044 CountValue *TripCount = getLoopTripCount(L, OldInsts);
1048 // Is the trip count available in the preheader?
1049 if (TripCount->isReg()) {
1050 // There will be a use of the register inserted into the preheader,
1051 // so make sure that the register is actually defined at that point.
1052 MachineInstr *TCDef = MRI->getVRegDef(TripCount->getReg());
1053 MachineBasicBlock *BBDef = TCDef->getParent();
1054 if (!NewPreheader) {
1055 if (!MDT->dominates(BBDef, Preheader))
1058 // If we have just created a preheader, the dominator tree won't be
1059 // aware of it. Check if the definition of the register dominates
1060 // the header, but is not the header itself.
1061 if (!MDT->properlyDominates(BBDef, L->getHeader()))
1066 // Determine the loop start.
1067 MachineBasicBlock *LoopStart = L->getTopBlock();
1068 if (L->getLoopLatch() != LastMBB) {
1069 // When the exit and latch are not the same, use the latch block as the
1071 // The loop start address is used only after the 1st iteration, and the
1072 // loop latch may contains instrs. that need to be executed after the
1074 LoopStart = L->getLoopLatch();
1075 // Make sure the latch is a successor of the exit, otherwise it won't work.
1076 if (!LastMBB->isSuccessor(LoopStart))
1080 // Convert the loop to a hardware loop.
1081 DEBUG(dbgs() << "Change to hardware loop at "; L->dump());
1083 if (InsertPos != Preheader->end())
1084 DL = InsertPos->getDebugLoc();
1086 if (TripCount->isReg()) {
1087 // Create a copy of the loop count register.
1088 unsigned CountReg = MRI->createVirtualRegister(&Hexagon::IntRegsRegClass);
1089 BuildMI(*Preheader, InsertPos, DL, TII->get(TargetOpcode::COPY), CountReg)
1090 .addReg(TripCount->getReg(), 0, TripCount->getSubReg());
1091 // Add the Loop instruction to the beginning of the loop.
1092 BuildMI(*Preheader, InsertPos, DL, TII->get(Hexagon::LOOP0_r))
1096 assert(TripCount->isImm() && "Expecting immediate value for trip count");
1097 // Add the Loop immediate instruction to the beginning of the loop,
1098 // if the immediate fits in the instructions. Otherwise, we need to
1099 // create a new virtual register.
1100 int64_t CountImm = TripCount->getImm();
1101 if (!TII->isValidOffset(Hexagon::LOOP0_i, CountImm)) {
1102 unsigned CountReg = MRI->createVirtualRegister(&Hexagon::IntRegsRegClass);
1103 BuildMI(*Preheader, InsertPos, DL, TII->get(Hexagon::TFRI), CountReg)
1105 BuildMI(*Preheader, InsertPos, DL, TII->get(Hexagon::LOOP0_r))
1106 .addMBB(LoopStart).addReg(CountReg);
1108 BuildMI(*Preheader, InsertPos, DL, TII->get(Hexagon::LOOP0_i))
1109 .addMBB(LoopStart).addImm(CountImm);
1112 // Make sure the loop start always has a reference in the CFG. We need
1113 // to create a BlockAddress operand to get this mechanism to work both the
1114 // MachineBasicBlock and BasicBlock objects need the flag set.
1115 LoopStart->setHasAddressTaken();
1116 // This line is needed to set the hasAddressTaken flag on the BasicBlock
1118 BlockAddress::get(const_cast<BasicBlock *>(LoopStart->getBasicBlock()));
1120 // Replace the loop branch with an endloop instruction.
1121 DebugLoc LastIDL = LastI->getDebugLoc();
1122 BuildMI(*LastMBB, LastI, LastIDL,
1123 TII->get(Hexagon::ENDLOOP0)).addMBB(LoopStart);
1125 // The loop ends with either:
1126 // - a conditional branch followed by an unconditional branch, or
1127 // - a conditional branch to the loop start.
1128 if (LastI->getOpcode() == Hexagon::JMP_c ||
1129 LastI->getOpcode() == Hexagon::JMP_cNot) {
1130 // Delete one and change/add an uncond. branch to out of the loop.
1131 MachineBasicBlock *BranchTarget = LastI->getOperand(1).getMBB();
1132 LastI = LastMBB->erase(LastI);
1133 if (!L->contains(BranchTarget)) {
1134 if (LastI != LastMBB->end())
1135 LastI = LastMBB->erase(LastI);
1136 SmallVector<MachineOperand, 0> Cond;
1137 TII->InsertBranch(*LastMBB, BranchTarget, 0, Cond, LastIDL);
1140 // Conditional branch to loop start; just delete it.
1141 LastMBB->erase(LastI);
1145 // The induction operation and the comparison may now be
1146 // unneeded. If these are unneeded, then remove them.
1147 for (unsigned i = 0; i < OldInsts.size(); ++i)
1148 removeIfDead(OldInsts[i]);
1155 bool HexagonHardwareLoops::orderBumpCompare(MachineInstr *BumpI,
1156 MachineInstr *CmpI) {
1157 assert (BumpI != CmpI && "Bump and compare in the same instruction?");
1159 MachineBasicBlock *BB = BumpI->getParent();
1160 if (CmpI->getParent() != BB)
1163 typedef MachineBasicBlock::instr_iterator instr_iterator;
1164 // Check if things are in order to begin with.
1165 for (instr_iterator I = BumpI, E = BB->instr_end(); I != E; ++I)
1170 unsigned PredR = CmpI->getOperand(0).getReg();
1171 bool FoundBump = false;
1172 instr_iterator CmpIt = CmpI, NextIt = llvm::next(CmpIt);
1173 for (instr_iterator I = NextIt, E = BB->instr_end(); I != E; ++I) {
1174 MachineInstr *In = &*I;
1175 for (unsigned i = 0, n = In->getNumOperands(); i < n; ++i) {
1176 MachineOperand &MO = In->getOperand(i);
1177 if (MO.isReg() && MO.isUse()) {
1178 if (MO.getReg() == PredR) // Found an intervening use of PredR.
1184 instr_iterator After = BumpI;
1185 instr_iterator From = CmpI;
1186 BB->splice(llvm::next(After), BB, From);
1191 assert (FoundBump && "Cannot determine instruction order");
1196 MachineInstr *HexagonHardwareLoops::defWithImmediate(unsigned R) {
1197 MachineInstr *DI = MRI->getVRegDef(R);
1198 unsigned DOpc = DI->getOpcode();
1201 case Hexagon::TFRI64:
1202 case Hexagon::CONST32_Int_Real:
1203 case Hexagon::CONST64_Int_Real:
1210 int64_t HexagonHardwareLoops::getImmediate(MachineOperand &MO) {
1214 unsigned R = MO.getReg();
1215 MachineInstr *DI = defWithImmediate(R);
1216 assert(DI && "Need an immediate operand");
1217 // All currently supported "define-with-immediate" instructions have the
1218 // actual immediate value in the operand(1).
1219 int64_t v = DI->getOperand(1).getImm();
1224 void HexagonHardwareLoops::setImmediate(MachineOperand &MO, int64_t Val) {
1231 unsigned R = MO.getReg();
1232 MachineInstr *DI = defWithImmediate(R);
1233 if (MRI->hasOneNonDBGUse(R)) {
1234 // If R has only one use, then just change its defining instruction to
1235 // the new immediate value.
1236 DI->getOperand(1).setImm(Val);
1240 const TargetRegisterClass *RC = MRI->getRegClass(R);
1241 unsigned NewR = MRI->createVirtualRegister(RC);
1242 MachineBasicBlock &B = *DI->getParent();
1243 DebugLoc DL = DI->getDebugLoc();
1244 BuildMI(B, DI, DL, TII->get(DI->getOpcode()), NewR)
1250 bool HexagonHardwareLoops::fixupInductionVariable(MachineLoop *L) {
1251 MachineBasicBlock *Header = L->getHeader();
1252 MachineBasicBlock *Preheader = L->getLoopPreheader();
1253 MachineBasicBlock *Latch = L->getLoopLatch();
1255 if (!Header || !Preheader || !Latch)
1258 // These data structures follow the same concept as the corresponding
1259 // ones in findInductionRegister (where some comments are).
1260 typedef std::pair<unsigned,int64_t> RegisterBump;
1261 typedef std::pair<unsigned,RegisterBump> RegisterInduction;
1262 typedef std::set<RegisterInduction> RegisterInductionSet;
1264 // Register candidates for induction variables, with their associated bumps.
1265 RegisterInductionSet IndRegs;
1267 // Look for induction patterns:
1268 // vreg1 = PHI ..., [ latch, vreg2 ]
1269 // vreg2 = ADD vreg1, imm
1270 typedef MachineBasicBlock::instr_iterator instr_iterator;
1271 for (instr_iterator I = Header->instr_begin(), E = Header->instr_end();
1272 I != E && I->isPHI(); ++I) {
1273 MachineInstr *Phi = &*I;
1275 // Have a PHI instruction.
1276 for (unsigned i = 1, n = Phi->getNumOperands(); i < n; i += 2) {
1277 if (Phi->getOperand(i+1).getMBB() != Latch)
1280 unsigned PhiReg = Phi->getOperand(i).getReg();
1281 MachineInstr *DI = MRI->getVRegDef(PhiReg);
1282 unsigned UpdOpc = DI->getOpcode();
1283 bool isAdd = (UpdOpc == Hexagon::ADD_ri);
1286 // If the register operand to the add/sub is the PHI we are looking
1287 // at, this meets the induction pattern.
1288 unsigned IndReg = DI->getOperand(1).getReg();
1289 if (MRI->getVRegDef(IndReg) == Phi) {
1290 unsigned UpdReg = DI->getOperand(0).getReg();
1291 int64_t V = DI->getOperand(2).getImm();
1292 IndRegs.insert(std::make_pair(UpdReg, std::make_pair(IndReg, V)));
1298 if (IndRegs.empty())
1301 MachineBasicBlock *TB = 0, *FB = 0;
1302 SmallVector<MachineOperand,2> Cond;
1303 // AnalyzeBranch returns true if it fails to analyze branch.
1304 bool NotAnalyzed = TII->AnalyzeBranch(*Latch, TB, FB, Cond, false);
1308 // Check if the latch branch is unconditional.
1312 if (TB != Header && FB != Header)
1313 // The latch does not go back to the header. Not a latch we know and love.
1316 // Expecting a predicate register as a condition. It won't be a hardware
1317 // predicate register at this point yet, just a vreg.
1318 // HexagonInstrInfo::AnalyzeBranch for negated branches inserts imm(0)
1319 // into Cond, followed by the predicate register. For non-negated branches
1320 // it's just the register.
1321 unsigned CSz = Cond.size();
1322 if (CSz != 1 && CSz != 2)
1325 unsigned P = Cond[CSz-1].getReg();
1326 MachineInstr *PredDef = MRI->getVRegDef(P);
1328 if (!PredDef->isCompare())
1331 SmallSet<unsigned,2> CmpRegs;
1332 MachineOperand *CmpImmOp = 0;
1334 // Go over all operands to the compare and look for immediate and register
1335 // operands. Assume that if the compare has a single register use and a
1336 // single immediate operand, then the register is being compared with the
1338 for (unsigned i = 0, n = PredDef->getNumOperands(); i < n; ++i) {
1339 MachineOperand &MO = PredDef->getOperand(i);
1341 // Skip all implicit references. In one case there was:
1342 // %vreg140<def> = FCMPUGT32_rr %vreg138, %vreg139, %USR<imp-use>
1343 if (MO.isImplicit())
1346 unsigned R = MO.getReg();
1347 if (!defWithImmediate(R)) {
1348 CmpRegs.insert(MO.getReg());
1351 // Consider the register to be the "immediate" operand.
1356 } else if (MO.isImm()) {
1357 if (CmpImmOp) // A second immediate argument? Confusing. Bail out.
1363 if (CmpRegs.empty())
1366 // Check if the compared register follows the order we want. Fix if needed.
1367 for (RegisterInductionSet::iterator I = IndRegs.begin(), E = IndRegs.end();
1369 // This is a success. If the register used in the comparison is one that
1370 // we have identified as a bumped (updated) induction register, there is
1372 if (CmpRegs.count(I->first))
1375 // Otherwise, if the register being compared comes out of a PHI node,
1376 // and has been recognized as following the induction pattern, and is
1377 // compared against an immediate, we can fix it.
1378 const RegisterBump &RB = I->second;
1379 if (CmpRegs.count(RB.first)) {
1383 int64_t CmpImm = getImmediate(*CmpImmOp);
1384 int64_t V = RB.second;
1385 if (V > 0 && CmpImm+V < CmpImm) // Overflow (64-bit).
1387 if (V < 0 && CmpImm+V > CmpImm) // Overflow (64-bit).
1390 // Some forms of cmp-immediate allow u9 and s10. Assume the worst case
1391 // scenario, i.e. an 8-bit value.
1392 if (CmpImmOp->isImm() && !isInt<8>(CmpImm))
1395 // Make sure that the compare happens after the bump. Otherwise,
1396 // after the fixup, the compare would use a yet-undefined register.
1397 MachineInstr *BumpI = MRI->getVRegDef(I->first);
1398 bool Order = orderBumpCompare(BumpI, PredDef);
1402 // Finally, fix the compare instruction.
1403 setImmediate(*CmpImmOp, CmpImm);
1404 for (unsigned i = 0, n = PredDef->getNumOperands(); i < n; ++i) {
1405 MachineOperand &MO = PredDef->getOperand(i);
1406 if (MO.isReg() && MO.getReg() == RB.first) {
1407 MO.setReg(I->first);
1418 /// \brief Create a preheader for a given loop.
1419 MachineBasicBlock *HexagonHardwareLoops::createPreheaderForLoop(
1421 if (MachineBasicBlock *TmpPH = L->getLoopPreheader())
1424 MachineBasicBlock *Header = L->getHeader();
1425 MachineBasicBlock *Latch = L->getLoopLatch();
1426 MachineFunction *MF = Header->getParent();
1429 if (!Latch || Header->hasAddressTaken())
1432 typedef MachineBasicBlock::instr_iterator instr_iterator;
1434 // Verify that all existing predecessors have analyzable branches
1435 // (or no branches at all).
1436 typedef std::vector<MachineBasicBlock*> MBBVector;
1437 MBBVector Preds(Header->pred_begin(), Header->pred_end());
1438 SmallVector<MachineOperand,2> Tmp1;
1439 MachineBasicBlock *TB = 0, *FB = 0;
1441 if (TII->AnalyzeBranch(*Latch, TB, FB, Tmp1, false))
1444 for (MBBVector::iterator I = Preds.begin(), E = Preds.end(); I != E; ++I) {
1445 MachineBasicBlock *PB = *I;
1447 bool NotAnalyzed = TII->AnalyzeBranch(*PB, TB, FB, Tmp1, false);
1453 MachineBasicBlock *NewPH = MF->CreateMachineBasicBlock();
1454 MF->insert(Header, NewPH);
1456 if (Header->pred_size() > 2) {
1457 // Ensure that the header has only two predecessors: the preheader and
1458 // the loop latch. Any additional predecessors of the header should
1459 // join at the newly created preheader. Inspect all PHI nodes from the
1460 // header and create appropriate corresponding PHI nodes in the preheader.
1462 for (instr_iterator I = Header->instr_begin(), E = Header->instr_end();
1463 I != E && I->isPHI(); ++I) {
1464 MachineInstr *PN = &*I;
1466 const MCInstrDesc &PD = TII->get(TargetOpcode::PHI);
1467 MachineInstr *NewPN = MF->CreateMachineInstr(PD, DL);
1468 NewPH->insert(NewPH->end(), NewPN);
1470 unsigned PR = PN->getOperand(0).getReg();
1471 const TargetRegisterClass *RC = MRI->getRegClass(PR);
1472 unsigned NewPR = MRI->createVirtualRegister(RC);
1473 NewPN->addOperand(MachineOperand::CreateReg(NewPR, true));
1475 // Copy all non-latch operands of a header's PHI node to the newly
1476 // created PHI node in the preheader.
1477 for (unsigned i = 1, n = PN->getNumOperands(); i < n; i += 2) {
1478 unsigned PredR = PN->getOperand(i).getReg();
1479 MachineBasicBlock *PredB = PN->getOperand(i+1).getMBB();
1483 NewPN->addOperand(MachineOperand::CreateReg(PredR, false));
1484 NewPN->addOperand(MachineOperand::CreateMBB(PredB));
1487 // Remove copied operands from the old PHI node and add the value
1488 // coming from the preheader's PHI.
1489 for (int i = PN->getNumOperands()-2; i > 0; i -= 2) {
1490 MachineBasicBlock *PredB = PN->getOperand(i+1).getMBB();
1491 if (PredB != Latch) {
1492 PN->RemoveOperand(i+1);
1493 PN->RemoveOperand(i);
1496 PN->addOperand(MachineOperand::CreateReg(NewPR, false));
1497 PN->addOperand(MachineOperand::CreateMBB(NewPH));
1501 assert(Header->pred_size() == 2);
1503 // The header has only two predecessors, but the non-latch predecessor
1504 // is not a preheader (e.g. it has other successors, etc.)
1505 // In such a case we don't need any extra PHI nodes in the new preheader,
1506 // all we need is to adjust existing PHIs in the header to now refer to
1507 // the new preheader.
1508 for (instr_iterator I = Header->instr_begin(), E = Header->instr_end();
1509 I != E && I->isPHI(); ++I) {
1510 MachineInstr *PN = &*I;
1511 for (unsigned i = 1, n = PN->getNumOperands(); i < n; i += 2) {
1512 MachineOperand &MO = PN->getOperand(i+1);
1513 if (MO.getMBB() != Latch)
1519 // "Reroute" the CFG edges to link in the new preheader.
1520 // If any of the predecessors falls through to the header, insert a branch
1521 // to the new preheader in that place.
1522 SmallVector<MachineOperand,1> Tmp2;
1523 SmallVector<MachineOperand,1> EmptyCond;
1527 for (MBBVector::iterator I = Preds.begin(), E = Preds.end(); I != E; ++I) {
1528 MachineBasicBlock *PB = *I;
1531 bool NotAnalyzed = TII->AnalyzeBranch(*PB, TB, FB, Tmp2, false);
1532 (void)NotAnalyzed; // supress compiler warning
1533 assert (!NotAnalyzed && "Should be analyzable!");
1534 if (TB != Header && (Tmp2.empty() || FB != Header))
1535 TII->InsertBranch(*PB, NewPH, 0, EmptyCond, DL);
1536 PB->ReplaceUsesOfBlockWith(Header, NewPH);
1540 // It can happen that the latch block will fall through into the header.
1541 // Insert an unconditional branch to the header.
1543 bool LatchNotAnalyzed = TII->AnalyzeBranch(*Latch, TB, FB, Tmp2, false);
1544 (void)LatchNotAnalyzed; // supress compiler warning
1545 assert (!LatchNotAnalyzed && "Should be analyzable!");
1547 TII->InsertBranch(*Latch, Header, 0, EmptyCond, DL);
1549 // Finally, the branch from the preheader to the header.
1550 TII->InsertBranch(*NewPH, Header, 0, EmptyCond, DL);
1551 NewPH->addSuccessor(Header);