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 #include "llvm/ADT/SmallSet.h"
31 #include "HexagonTargetMachine.h"
32 #include "llvm/ADT/Statistic.h"
33 #include "llvm/CodeGen/MachineDominators.h"
34 #include "llvm/CodeGen/MachineFunction.h"
35 #include "llvm/CodeGen/MachineFunctionPass.h"
36 #include "llvm/CodeGen/MachineInstrBuilder.h"
37 #include "llvm/CodeGen/MachineLoopInfo.h"
38 #include "llvm/CodeGen/MachineRegisterInfo.h"
39 #include "llvm/PassSupport.h"
40 #include "llvm/Support/CommandLine.h"
41 #include "llvm/Support/Debug.h"
42 #include "llvm/Support/raw_ostream.h"
43 #include "llvm/Target/TargetInstrInfo.h"
49 #define DEBUG_TYPE "hwloops"
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 bool runOnMachineFunction(MachineFunction
&MF
) override
;
83 const char *getPassName() const override
{ return "Hexagon Hardware Loops"; }
85 void getAnalysisUsage(AnalysisUsage
&AU
) const override
{
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 SmallVectorImpl
<MachineInstr
*> &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 SmallVectorImpl
<MachineInstr
*> &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 version
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
= nullptr) const {
269 const TargetRegisterInfo
*TRI
=
270 TM
? TM
->getSubtargetImpl()->getRegisterInfo() : nullptr;
271 if (isReg()) { OS
<< PrintReg(Contents
.R
.Reg
, TRI
, Contents
.R
.Sub
); }
272 if (isImm()) { OS
<< Contents
.ImmVal
; }
275 } // end anonymous namespace
278 INITIALIZE_PASS_BEGIN(HexagonHardwareLoops
, "hwloops",
279 "Hexagon Hardware Loops", false, false)
280 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree
)
281 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo
)
282 INITIALIZE_PASS_END(HexagonHardwareLoops
, "hwloops",
283 "Hexagon Hardware Loops", false, false)
286 /// \brief Returns true if the instruction is a hardware loop instruction.
287 static bool isHardwareLoop(const MachineInstr
*MI
) {
288 return MI
->getOpcode() == Hexagon::J2_loop0r
||
289 MI
->getOpcode() == Hexagon::J2_loop0i
;
292 FunctionPass
*llvm::createHexagonHardwareLoops() {
293 return new HexagonHardwareLoops();
297 bool HexagonHardwareLoops::runOnMachineFunction(MachineFunction
&MF
) {
298 DEBUG(dbgs() << "********* Hexagon Hardware Loops *********\n");
300 bool Changed
= false;
302 MLI
= &getAnalysis
<MachineLoopInfo
>();
303 MRI
= &MF
.getRegInfo();
304 MDT
= &getAnalysis
<MachineDominatorTree
>();
305 TM
= static_cast<const HexagonTargetMachine
*>(&MF
.getTarget());
306 TII
= static_cast<const HexagonInstrInfo
*>(
307 TM
->getSubtargetImpl()->getInstrInfo());
308 TRI
= static_cast<const HexagonRegisterInfo
*>(
309 TM
->getSubtargetImpl()->getRegisterInfo());
311 for (MachineLoopInfo::iterator I
= MLI
->begin(), E
= MLI
->end();
314 if (!L
->getParentLoop())
315 Changed
|= convertToHardwareLoop(L
);
322 bool HexagonHardwareLoops::findInductionRegister(MachineLoop
*L
,
327 MachineBasicBlock
*Header
= L
->getHeader();
328 MachineBasicBlock
*Preheader
= L
->getLoopPreheader();
329 MachineBasicBlock
*Latch
= L
->getLoopLatch();
330 if (!Header
|| !Preheader
|| !Latch
)
333 // This pair represents an induction register together with an immediate
334 // value that will be added to it in each loop iteration.
335 typedef std::pair
<unsigned,int64_t> RegisterBump
;
337 // Mapping: R.next -> (R, bump), where R, R.next and bump are derived
338 // from an induction operation
340 // where bump is an immediate value.
341 typedef std::map
<unsigned,RegisterBump
> InductionMap
;
345 typedef MachineBasicBlock::instr_iterator instr_iterator
;
346 for (instr_iterator I
= Header
->instr_begin(), E
= Header
->instr_end();
347 I
!= E
&& I
->isPHI(); ++I
) {
348 MachineInstr
*Phi
= &*I
;
350 // Have a PHI instruction. Get the operand that corresponds to the
351 // latch block, and see if is a result of an addition of form "reg+imm",
352 // where the "reg" is defined by the PHI node we are looking at.
353 for (unsigned i
= 1, n
= Phi
->getNumOperands(); i
< n
; i
+= 2) {
354 if (Phi
->getOperand(i
+1).getMBB() != Latch
)
357 unsigned PhiOpReg
= Phi
->getOperand(i
).getReg();
358 MachineInstr
*DI
= MRI
->getVRegDef(PhiOpReg
);
359 unsigned UpdOpc
= DI
->getOpcode();
360 bool isAdd
= (UpdOpc
== Hexagon::ADD_ri
);
363 // If the register operand to the add is the PHI we're
364 // looking at, this meets the induction pattern.
365 unsigned IndReg
= DI
->getOperand(1).getReg();
366 if (MRI
->getVRegDef(IndReg
) == Phi
) {
367 unsigned UpdReg
= DI
->getOperand(0).getReg();
368 int64_t V
= DI
->getOperand(2).getImm();
369 IndMap
.insert(std::make_pair(UpdReg
, std::make_pair(IndReg
, V
)));
375 SmallVector
<MachineOperand
,2> Cond
;
376 MachineBasicBlock
*TB
= nullptr, *FB
= nullptr;
377 bool NotAnalyzed
= TII
->AnalyzeBranch(*Latch
, TB
, FB
, Cond
, false);
381 unsigned CSz
= Cond
.size();
382 assert (CSz
== 1 || CSz
== 2);
383 unsigned PredR
= Cond
[CSz
-1].getReg();
385 MachineInstr
*PredI
= MRI
->getVRegDef(PredR
);
386 if (!PredI
->isCompare())
389 unsigned CmpReg1
= 0, CmpReg2
= 0;
390 int CmpImm
= 0, CmpMask
= 0;
391 bool CmpAnalyzed
= TII
->analyzeCompare(PredI
, CmpReg1
, CmpReg2
,
393 // Fail if the compare was not analyzed, or it's not comparing a register
394 // with an immediate value. Not checking the mask here, since we handle
395 // the individual compare opcodes (including CMPb) later on.
399 // Exactly one of the input registers to the comparison should be among
400 // the induction registers.
401 InductionMap::iterator IndMapEnd
= IndMap
.end();
402 InductionMap::iterator F
= IndMapEnd
;
404 InductionMap::iterator F1
= IndMap
.find(CmpReg1
);
409 InductionMap::iterator F2
= IndMap
.find(CmpReg2
);
410 if (F2
!= IndMapEnd
) {
419 Reg
= F
->second
.first
;
420 IVBump
= F
->second
.second
;
421 IVOp
= MRI
->getVRegDef(F
->first
);
426 /// \brief Analyze the statements in a loop to determine if the loop has
427 /// a computable trip count and, if so, return a value that represents
428 /// the trip count expression.
430 /// This function iterates over the phi nodes in the loop to check for
431 /// induction variable patterns that are used in the calculation for
432 /// the number of time the loop is executed.
433 CountValue
*HexagonHardwareLoops::getLoopTripCount(MachineLoop
*L
,
434 SmallVectorImpl
<MachineInstr
*> &OldInsts
) {
435 MachineBasicBlock
*TopMBB
= L
->getTopBlock();
436 MachineBasicBlock::pred_iterator PI
= TopMBB
->pred_begin();
437 assert(PI
!= TopMBB
->pred_end() &&
438 "Loop must have more than one incoming edge!");
439 MachineBasicBlock
*Backedge
= *PI
++;
440 if (PI
== TopMBB
->pred_end()) // dead loop?
442 MachineBasicBlock
*Incoming
= *PI
++;
443 if (PI
!= TopMBB
->pred_end()) // multiple backedges?
446 // Make sure there is one incoming and one backedge and determine which
448 if (L
->contains(Incoming
)) {
449 if (L
->contains(Backedge
))
451 std::swap(Incoming
, Backedge
);
452 } else if (!L
->contains(Backedge
))
455 // Look for the cmp instruction to determine if we can get a useful trip
456 // count. The trip count can be either a register or an immediate. The
457 // location of the value depends upon the type (reg or imm).
458 MachineBasicBlock
*Latch
= L
->getLoopLatch();
465 bool FoundIV
= findInductionRegister(L
, IVReg
, IVBump
, IVOp
);
469 MachineBasicBlock
*Preheader
= L
->getLoopPreheader();
471 MachineOperand
*InitialValue
= nullptr;
472 MachineInstr
*IV_Phi
= MRI
->getVRegDef(IVReg
);
473 for (unsigned i
= 1, n
= IV_Phi
->getNumOperands(); i
< n
; i
+= 2) {
474 MachineBasicBlock
*MBB
= IV_Phi
->getOperand(i
+1).getMBB();
475 if (MBB
== Preheader
)
476 InitialValue
= &IV_Phi
->getOperand(i
);
477 else if (MBB
== Latch
)
478 IVReg
= IV_Phi
->getOperand(i
).getReg(); // Want IV reg after bump.
483 SmallVector
<MachineOperand
,2> Cond
;
484 MachineBasicBlock
*TB
= nullptr, *FB
= nullptr;
485 bool NotAnalyzed
= TII
->AnalyzeBranch(*Latch
, TB
, FB
, Cond
, false);
489 MachineBasicBlock
*Header
= L
->getHeader();
490 // TB must be non-null. If FB is also non-null, one of them must be
491 // the header. Otherwise, branch to TB could be exiting the loop, and
492 // the fall through can go to the header.
493 assert (TB
&& "Latch block without a branch?");
494 assert ((!FB
|| TB
== Header
|| FB
== Header
) && "Branches not to header?");
495 if (!TB
|| (FB
&& TB
!= Header
&& FB
!= Header
))
498 // Branches of form "if (!P) ..." cause HexagonInstrInfo::AnalyzeBranch
499 // to put imm(0), followed by P in the vector Cond.
500 // If TB is not the header, it means that the "not-taken" path must lead
502 bool Negated
= (Cond
.size() > 1) ^ (TB
!= Header
);
503 unsigned PredReg
= Cond
[Cond
.size()-1].getReg();
504 MachineInstr
*CondI
= MRI
->getVRegDef(PredReg
);
505 unsigned CondOpc
= CondI
->getOpcode();
507 unsigned CmpReg1
= 0, CmpReg2
= 0;
508 int Mask
= 0, ImmValue
= 0;
509 bool AnalyzedCmp
= TII
->analyzeCompare(CondI
, CmpReg1
, CmpReg2
,
514 // The comparison operator type determines how we compute the loop
516 OldInsts
.push_back(CondI
);
517 OldInsts
.push_back(IVOp
);
519 // Sadly, the following code gets information based on the position
520 // of the operands in the compare instruction. This has to be done
521 // this way, because the comparisons check for a specific relationship
522 // between the operands (e.g. is-less-than), rather than to find out
523 // what relationship the operands are in (as on PPC).
524 Comparison::Kind Cmp
;
525 bool isSwapped
= false;
526 const MachineOperand
&Op1
= CondI
->getOperand(1);
527 const MachineOperand
&Op2
= CondI
->getOperand(2);
528 const MachineOperand
*EndValue
= nullptr;
531 if (Op2
.isImm() || Op1
.getReg() == IVReg
)
543 case Hexagon::C2_cmpeqi
:
544 case Hexagon::C2_cmpeq
:
545 Cmp
= !Negated
? Comparison::EQ
: Comparison::NE
;
547 case Hexagon::C2_cmpgtui
:
548 case Hexagon::C2_cmpgtu
:
549 Cmp
= !Negated
? Comparison::GTu
: Comparison::LEu
;
551 case Hexagon::C2_cmpgti
:
552 case Hexagon::C2_cmpgt
:
553 Cmp
= !Negated
? Comparison::GTs
: Comparison::LEs
;
555 // Very limited support for byte/halfword compares.
556 case Hexagon::CMPbEQri_V4
:
557 case Hexagon::CMPhEQri_V4
: {
562 // Since the comparisons are "ri", the EndValue should be an
563 // immediate. Check it just in case.
564 assert(EndValue
->isImm() && "Unrecognized latch comparison");
565 EndV
= EndValue
->getImm();
566 // Allow InitialValue to be a register defined with an immediate.
567 if (InitialValue
->isReg()) {
568 if (!defWithImmediate(InitialValue
->getReg()))
570 InitV
= getImmediate(*InitialValue
);
572 assert(InitialValue
->isImm());
573 InitV
= InitialValue
->getImm();
577 if (CondOpc
== Hexagon::CMPbEQri_V4
) {
578 if (!isInt
<8>(InitV
) || !isInt
<8>(EndV
))
580 } else { // Hexagon::CMPhEQri_V4
581 if (!isInt
<16>(InitV
) || !isInt
<16>(EndV
))
584 Cmp
= !Negated
? Comparison::EQ
: Comparison::NE
;
592 Cmp
= Comparison::getSwappedComparison(Cmp
);
594 if (InitialValue
->isReg()) {
595 unsigned R
= InitialValue
->getReg();
596 MachineBasicBlock
*DefBB
= MRI
->getVRegDef(R
)->getParent();
597 if (!MDT
->properlyDominates(DefBB
, Header
))
599 OldInsts
.push_back(MRI
->getVRegDef(R
));
601 if (EndValue
->isReg()) {
602 unsigned R
= EndValue
->getReg();
603 MachineBasicBlock
*DefBB
= MRI
->getVRegDef(R
)->getParent();
604 if (!MDT
->properlyDominates(DefBB
, Header
))
608 return computeCount(L
, InitialValue
, EndValue
, IVReg
, IVBump
, Cmp
);
611 /// \brief Helper function that returns the expression that represents the
612 /// number of times a loop iterates. The function takes the operands that
613 /// represent the loop start value, loop end value, and induction value.
614 /// Based upon these operands, the function attempts to compute the trip count.
615 CountValue
*HexagonHardwareLoops::computeCount(MachineLoop
*Loop
,
616 const MachineOperand
*Start
,
617 const MachineOperand
*End
,
620 Comparison::Kind Cmp
) const {
621 // Cannot handle comparison EQ, i.e. while (A == B).
622 if (Cmp
== Comparison::EQ
)
625 // Check if either the start or end values are an assignment of an immediate.
626 // If so, use the immediate value rather than the register.
627 if (Start
->isReg()) {
628 const MachineInstr
*StartValInstr
= MRI
->getVRegDef(Start
->getReg());
629 if (StartValInstr
&& StartValInstr
->getOpcode() == Hexagon::A2_tfrsi
)
630 Start
= &StartValInstr
->getOperand(1);
633 const MachineInstr
*EndValInstr
= MRI
->getVRegDef(End
->getReg());
634 if (EndValInstr
&& EndValInstr
->getOpcode() == Hexagon::A2_tfrsi
)
635 End
= &EndValInstr
->getOperand(1);
638 assert (Start
->isReg() || Start
->isImm());
639 assert (End
->isReg() || End
->isImm());
641 bool CmpLess
= Cmp
& Comparison::L
;
642 bool CmpGreater
= Cmp
& Comparison::G
;
643 bool CmpHasEqual
= Cmp
& Comparison::EQ
;
645 // Avoid certain wrap-arounds. This doesn't detect all wrap-arounds.
646 // If loop executes while iv is "less" with the iv value going down, then
648 if (CmpLess
&& IVBump
< 0)
650 // If loop executes while iv is "greater" with the iv value going up, then
652 if (CmpGreater
&& IVBump
> 0)
655 if (Start
->isImm() && End
->isImm()) {
656 // Both, start and end are immediates.
657 int64_t StartV
= Start
->getImm();
658 int64_t EndV
= End
->getImm();
659 int64_t Dist
= EndV
- StartV
;
663 bool Exact
= (Dist
% IVBump
) == 0;
665 if (Cmp
== Comparison::NE
) {
668 if ((Dist
< 0) ^ (IVBump
< 0))
672 // For comparisons that include the final value (i.e. include equality
673 // with the final value), we need to increase the distance by 1.
675 Dist
= Dist
> 0 ? Dist
+1 : Dist
-1;
677 // assert (CmpLess => Dist > 0);
678 assert ((!CmpLess
|| Dist
> 0) && "Loop should never iterate!");
679 // assert (CmpGreater => Dist < 0);
680 assert ((!CmpGreater
|| Dist
< 0) && "Loop should never iterate!");
682 // "Normalized" distance, i.e. with the bump set to +-1.
683 int64_t Dist1
= (IVBump
> 0) ? (Dist
+ (IVBump
-1)) / IVBump
684 : (-Dist
+ (-IVBump
-1)) / (-IVBump
);
685 assert (Dist1
> 0 && "Fishy thing. Both operands have the same sign.");
687 uint64_t Count
= Dist1
;
689 if (Count
> 0xFFFFFFFFULL
)
692 return new CountValue(CountValue::CV_Immediate
, Count
);
695 // A general case: Start and End are some values, but the actual
696 // iteration count may not be available. If it is not, insert
697 // a computation of it into the preheader.
699 // If the induction variable bump is not a power of 2, quit.
700 // Othwerise we'd need a general integer division.
701 if (!isPowerOf2_64(abs64(IVBump
)))
704 MachineBasicBlock
*PH
= Loop
->getLoopPreheader();
705 assert (PH
&& "Should have a preheader by now");
706 MachineBasicBlock::iterator InsertPos
= PH
->getFirstTerminator();
707 DebugLoc DL
= (InsertPos
!= PH
->end()) ? InsertPos
->getDebugLoc()
710 // If Start is an immediate and End is a register, the trip count
711 // will be "reg - imm". Hexagon's "subtract immediate" instruction
712 // is actually "reg + -imm".
714 // If the loop IV is going downwards, i.e. if the bump is negative,
715 // then the iteration count (computed as End-Start) will need to be
716 // negated. To avoid the negation, just swap Start and End.
718 std::swap(Start
, End
);
721 // Cmp may now have a wrong direction, e.g. LEs may now be GEs.
722 // Signedness, and "including equality" are preserved.
724 bool RegToImm
= Start
->isReg() && End
->isImm(); // for (reg..imm)
725 bool RegToReg
= Start
->isReg() && End
->isReg(); // for (reg..reg)
727 int64_t StartV
= 0, EndV
= 0;
729 StartV
= Start
->getImm();
731 EndV
= End
->getImm();
734 // To compute the iteration count, we would need this computation:
735 // Count = (End - Start + (IVBump-1)) / IVBump
736 // or, when CmpHasEqual:
737 // Count = (End - Start + (IVBump-1)+1) / IVBump
738 // The "IVBump-1" part is the adjustment (AdjV). We can avoid
739 // generating an instruction specifically to add it if we can adjust
740 // the immediate values for Start or End.
743 // Need to add 1 to the total iteration count.
746 else if (End
->isImm())
752 if (Cmp
!= Comparison::NE
) {
754 StartV
-= (IVBump
-1);
755 else if (End
->isImm())
761 unsigned R
= 0, SR
= 0;
762 if (Start
->isReg()) {
764 SR
= Start
->getSubReg();
767 SR
= End
->getSubReg();
769 const TargetRegisterClass
*RC
= MRI
->getRegClass(R
);
770 // Hardware loops cannot handle 64-bit registers. If it's a double
771 // register, it has to have a subregister.
772 if (!SR
&& RC
== &Hexagon::DoubleRegsRegClass
)
774 const TargetRegisterClass
*IntRC
= &Hexagon::IntRegsRegClass
;
776 // Compute DistR (register with the distance between Start and End).
777 unsigned DistR
, DistSR
;
779 // Avoid special case, where the start value is an imm(0).
780 if (Start
->isImm() && StartV
== 0) {
781 DistR
= End
->getReg();
782 DistSR
= End
->getSubReg();
784 const MCInstrDesc
&SubD
= RegToReg
? TII
->get(Hexagon::A2_sub
) :
785 (RegToImm
? TII
->get(Hexagon::SUB_ri
) :
786 TII
->get(Hexagon::ADD_ri
));
787 unsigned SubR
= MRI
->createVirtualRegister(IntRC
);
788 MachineInstrBuilder SubIB
=
789 BuildMI(*PH
, InsertPos
, DL
, SubD
, SubR
);
792 SubIB
.addReg(End
->getReg(), 0, End
->getSubReg())
793 .addReg(Start
->getReg(), 0, Start
->getSubReg());
794 } else if (RegToImm
) {
796 .addReg(Start
->getReg(), 0, Start
->getSubReg());
798 SubIB
.addReg(End
->getReg(), 0, End
->getSubReg())
805 // From DistR, compute AdjR (register with the adjusted distance).
806 unsigned AdjR
, AdjSR
;
812 // Generate CountR = ADD DistR, AdjVal
813 unsigned AddR
= MRI
->createVirtualRegister(IntRC
);
814 const MCInstrDesc
&AddD
= TII
->get(Hexagon::ADD_ri
);
815 BuildMI(*PH
, InsertPos
, DL
, AddD
, AddR
)
816 .addReg(DistR
, 0, DistSR
)
823 // From AdjR, compute CountR (register with the final count).
824 unsigned CountR
, CountSR
;
830 // The IV bump is a power of two. Log_2(IV bump) is the shift amount.
831 unsigned Shift
= Log2_32(IVBump
);
833 // Generate NormR = LSR DistR, Shift.
834 unsigned LsrR
= MRI
->createVirtualRegister(IntRC
);
835 const MCInstrDesc
&LsrD
= TII
->get(Hexagon::S2_lsr_i_r
);
836 BuildMI(*PH
, InsertPos
, DL
, LsrD
, LsrR
)
837 .addReg(AdjR
, 0, AdjSR
)
844 return new CountValue(CountValue::CV_Register
, CountR
, CountSR
);
848 /// \brief Return true if the operation is invalid within hardware loop.
849 bool HexagonHardwareLoops::isInvalidLoopOperation(
850 const MachineInstr
*MI
) const {
852 // call is not allowed because the callee may use a hardware loop
853 if (MI
->getDesc().isCall())
856 // do not allow nested hardware loops
857 if (isHardwareLoop(MI
))
860 // check if the instruction defines a hardware loop register
861 for (unsigned i
= 0, e
= MI
->getNumOperands(); i
!= e
; ++i
) {
862 const MachineOperand
&MO
= MI
->getOperand(i
);
863 if (!MO
.isReg() || !MO
.isDef())
865 unsigned R
= MO
.getReg();
866 if (R
== Hexagon::LC0
|| R
== Hexagon::LC1
||
867 R
== Hexagon::SA0
|| R
== Hexagon::SA1
)
874 /// \brief - Return true if the loop contains an instruction that inhibits
875 /// the use of the hardware loop function.
876 bool HexagonHardwareLoops::containsInvalidInstruction(MachineLoop
*L
) const {
877 const std::vector
<MachineBasicBlock
*> &Blocks
= L
->getBlocks();
878 for (unsigned i
= 0, e
= Blocks
.size(); i
!= e
; ++i
) {
879 MachineBasicBlock
*MBB
= Blocks
[i
];
880 for (MachineBasicBlock::iterator
881 MII
= MBB
->begin(), E
= MBB
->end(); MII
!= E
; ++MII
) {
882 const MachineInstr
*MI
= &*MII
;
883 if (isInvalidLoopOperation(MI
))
891 /// \brief Returns true if the instruction is dead. This was essentially
892 /// copied from DeadMachineInstructionElim::isDead, but with special cases
893 /// for inline asm, physical registers and instructions with side effects
895 bool HexagonHardwareLoops::isDead(const MachineInstr
*MI
,
896 SmallVectorImpl
<MachineInstr
*> &DeadPhis
) const {
897 // Examine each operand.
898 for (unsigned i
= 0, e
= MI
->getNumOperands(); i
!= e
; ++i
) {
899 const MachineOperand
&MO
= MI
->getOperand(i
);
900 if (!MO
.isReg() || !MO
.isDef())
903 unsigned Reg
= MO
.getReg();
904 if (MRI
->use_nodbg_empty(Reg
))
907 typedef MachineRegisterInfo::use_nodbg_iterator use_nodbg_iterator
;
909 // This instruction has users, but if the only user is the phi node for the
910 // parent block, and the only use of that phi node is this instruction, then
911 // this instruction is dead: both it (and the phi node) can be removed.
912 use_nodbg_iterator I
= MRI
->use_nodbg_begin(Reg
);
913 use_nodbg_iterator End
= MRI
->use_nodbg_end();
914 if (std::next(I
) != End
|| !I
->getParent()->isPHI())
917 MachineInstr
*OnePhi
= I
->getParent();
918 for (unsigned j
= 0, f
= OnePhi
->getNumOperands(); j
!= f
; ++j
) {
919 const MachineOperand
&OPO
= OnePhi
->getOperand(j
);
920 if (!OPO
.isReg() || !OPO
.isDef())
923 unsigned OPReg
= OPO
.getReg();
924 use_nodbg_iterator nextJ
;
925 for (use_nodbg_iterator J
= MRI
->use_nodbg_begin(OPReg
);
926 J
!= End
; J
= nextJ
) {
927 nextJ
= std::next(J
);
928 MachineOperand
&Use
= *J
;
929 MachineInstr
*UseMI
= Use
.getParent();
931 // If the phi node has a user that is not MI, bail...
936 DeadPhis
.push_back(OnePhi
);
939 // If there are no defs with uses, the instruction is dead.
943 void HexagonHardwareLoops::removeIfDead(MachineInstr
*MI
) {
944 // This procedure was essentially copied from DeadMachineInstructionElim.
946 SmallVector
<MachineInstr
*, 1> DeadPhis
;
947 if (isDead(MI
, DeadPhis
)) {
948 DEBUG(dbgs() << "HW looping will remove: " << *MI
);
950 // It is possible that some DBG_VALUE instructions refer to this
951 // instruction. Examine each def operand for such references;
952 // if found, mark the DBG_VALUE as undef (but don't delete it).
953 for (unsigned i
= 0, e
= MI
->getNumOperands(); i
!= e
; ++i
) {
954 const MachineOperand
&MO
= MI
->getOperand(i
);
955 if (!MO
.isReg() || !MO
.isDef())
957 unsigned Reg
= MO
.getReg();
958 MachineRegisterInfo::use_iterator nextI
;
959 for (MachineRegisterInfo::use_iterator I
= MRI
->use_begin(Reg
),
960 E
= MRI
->use_end(); I
!= E
; I
= nextI
) {
961 nextI
= std::next(I
); // I is invalidated by the setReg
962 MachineOperand
&Use
= *I
;
963 MachineInstr
*UseMI
= I
->getParent();
967 UseMI
->getOperand(0).setReg(0U);
968 // This may also be a "instr -> phi -> instr" case which can
973 MI
->eraseFromParent();
974 for (unsigned i
= 0; i
< DeadPhis
.size(); ++i
)
975 DeadPhis
[i
]->eraseFromParent();
979 /// \brief Check if the loop is a candidate for converting to a hardware
980 /// loop. If so, then perform the transformation.
982 /// This function works on innermost loops first. A loop can be converted
983 /// if it is a counting loop; either a register value or an immediate.
985 /// The code makes several assumptions about the representation of the loop
987 bool HexagonHardwareLoops::convertToHardwareLoop(MachineLoop
*L
) {
988 // This is just for sanity.
989 assert(L
->getHeader() && "Loop without a header?");
991 bool Changed
= false;
992 // Process nested loops first.
993 for (MachineLoop::iterator I
= L
->begin(), E
= L
->end(); I
!= E
; ++I
)
994 Changed
|= convertToHardwareLoop(*I
);
996 // If a nested loop has been converted, then we can't convert this loop.
1001 // Stop trying after reaching the limit (if any).
1002 int Limit
= HWLoopLimit
;
1004 if (Counter
>= HWLoopLimit
)
1010 // Does the loop contain any invalid instructions?
1011 if (containsInvalidInstruction(L
))
1014 // Is the induction variable bump feeding the latch condition?
1015 if (!fixupInductionVariable(L
))
1018 MachineBasicBlock
*LastMBB
= L
->getExitingBlock();
1019 // Don't generate hw loop if the loop has more than one exit.
1023 MachineBasicBlock::iterator LastI
= LastMBB
->getFirstTerminator();
1024 if (LastI
== LastMBB
->end())
1027 // Ensure the loop has a preheader: the loop instruction will be
1029 bool NewPreheader
= false;
1030 MachineBasicBlock
*Preheader
= L
->getLoopPreheader();
1032 Preheader
= createPreheaderForLoop(L
);
1035 NewPreheader
= true;
1037 MachineBasicBlock::iterator InsertPos
= Preheader
->getFirstTerminator();
1039 SmallVector
<MachineInstr
*, 2> OldInsts
;
1040 // Are we able to determine the trip count for the loop?
1041 CountValue
*TripCount
= getLoopTripCount(L
, OldInsts
);
1045 // Is the trip count available in the preheader?
1046 if (TripCount
->isReg()) {
1047 // There will be a use of the register inserted into the preheader,
1048 // so make sure that the register is actually defined at that point.
1049 MachineInstr
*TCDef
= MRI
->getVRegDef(TripCount
->getReg());
1050 MachineBasicBlock
*BBDef
= TCDef
->getParent();
1051 if (!NewPreheader
) {
1052 if (!MDT
->dominates(BBDef
, Preheader
))
1055 // If we have just created a preheader, the dominator tree won't be
1056 // aware of it. Check if the definition of the register dominates
1057 // the header, but is not the header itself.
1058 if (!MDT
->properlyDominates(BBDef
, L
->getHeader()))
1063 // Determine the loop start.
1064 MachineBasicBlock
*LoopStart
= L
->getTopBlock();
1065 if (L
->getLoopLatch() != LastMBB
) {
1066 // When the exit and latch are not the same, use the latch block as the
1068 // The loop start address is used only after the 1st iteration, and the
1069 // loop latch may contains instrs. that need to be executed after the
1071 LoopStart
= L
->getLoopLatch();
1072 // Make sure the latch is a successor of the exit, otherwise it won't work.
1073 if (!LastMBB
->isSuccessor(LoopStart
))
1077 // Convert the loop to a hardware loop.
1078 DEBUG(dbgs() << "Change to hardware loop at "; L
->dump());
1080 if (InsertPos
!= Preheader
->end())
1081 DL
= InsertPos
->getDebugLoc();
1083 if (TripCount
->isReg()) {
1084 // Create a copy of the loop count register.
1085 unsigned CountReg
= MRI
->createVirtualRegister(&Hexagon::IntRegsRegClass
);
1086 BuildMI(*Preheader
, InsertPos
, DL
, TII
->get(TargetOpcode::COPY
), CountReg
)
1087 .addReg(TripCount
->getReg(), 0, TripCount
->getSubReg());
1088 // Add the Loop instruction to the beginning of the loop.
1089 BuildMI(*Preheader
, InsertPos
, DL
, TII
->get(Hexagon::J2_loop0r
))
1093 assert(TripCount
->isImm() && "Expecting immediate value for trip count");
1094 // Add the Loop immediate instruction to the beginning of the loop,
1095 // if the immediate fits in the instructions. Otherwise, we need to
1096 // create a new virtual register.
1097 int64_t CountImm
= TripCount
->getImm();
1098 if (!TII
->isValidOffset(Hexagon::J2_loop0i
, CountImm
)) {
1099 unsigned CountReg
= MRI
->createVirtualRegister(&Hexagon::IntRegsRegClass
);
1100 BuildMI(*Preheader
, InsertPos
, DL
, TII
->get(Hexagon::A2_tfrsi
), CountReg
)
1102 BuildMI(*Preheader
, InsertPos
, DL
, TII
->get(Hexagon::J2_loop0r
))
1103 .addMBB(LoopStart
).addReg(CountReg
);
1105 BuildMI(*Preheader
, InsertPos
, DL
, TII
->get(Hexagon::J2_loop0i
))
1106 .addMBB(LoopStart
).addImm(CountImm
);
1109 // Make sure the loop start always has a reference in the CFG. We need
1110 // to create a BlockAddress operand to get this mechanism to work both the
1111 // MachineBasicBlock and BasicBlock objects need the flag set.
1112 LoopStart
->setHasAddressTaken();
1113 // This line is needed to set the hasAddressTaken flag on the BasicBlock
1115 BlockAddress::get(const_cast<BasicBlock
*>(LoopStart
->getBasicBlock()));
1117 // Replace the loop branch with an endloop instruction.
1118 DebugLoc LastIDL
= LastI
->getDebugLoc();
1119 BuildMI(*LastMBB
, LastI
, LastIDL
,
1120 TII
->get(Hexagon::ENDLOOP0
)).addMBB(LoopStart
);
1122 // The loop ends with either:
1123 // - a conditional branch followed by an unconditional branch, or
1124 // - a conditional branch to the loop start.
1125 if (LastI
->getOpcode() == Hexagon::J2_jumpt
||
1126 LastI
->getOpcode() == Hexagon::J2_jumpf
) {
1127 // Delete one and change/add an uncond. branch to out of the loop.
1128 MachineBasicBlock
*BranchTarget
= LastI
->getOperand(1).getMBB();
1129 LastI
= LastMBB
->erase(LastI
);
1130 if (!L
->contains(BranchTarget
)) {
1131 if (LastI
!= LastMBB
->end())
1132 LastI
= LastMBB
->erase(LastI
);
1133 SmallVector
<MachineOperand
, 0> Cond
;
1134 TII
->InsertBranch(*LastMBB
, BranchTarget
, nullptr, Cond
, LastIDL
);
1137 // Conditional branch to loop start; just delete it.
1138 LastMBB
->erase(LastI
);
1142 // The induction operation and the comparison may now be
1143 // unneeded. If these are unneeded, then remove them.
1144 for (unsigned i
= 0; i
< OldInsts
.size(); ++i
)
1145 removeIfDead(OldInsts
[i
]);
1152 bool HexagonHardwareLoops::orderBumpCompare(MachineInstr
*BumpI
,
1153 MachineInstr
*CmpI
) {
1154 assert (BumpI
!= CmpI
&& "Bump and compare in the same instruction?");
1156 MachineBasicBlock
*BB
= BumpI
->getParent();
1157 if (CmpI
->getParent() != BB
)
1160 typedef MachineBasicBlock::instr_iterator instr_iterator
;
1161 // Check if things are in order to begin with.
1162 for (instr_iterator I
= BumpI
, E
= BB
->instr_end(); I
!= E
; ++I
)
1167 unsigned PredR
= CmpI
->getOperand(0).getReg();
1168 bool FoundBump
= false;
1169 instr_iterator CmpIt
= CmpI
, NextIt
= std::next(CmpIt
);
1170 for (instr_iterator I
= NextIt
, E
= BB
->instr_end(); I
!= E
; ++I
) {
1171 MachineInstr
*In
= &*I
;
1172 for (unsigned i
= 0, n
= In
->getNumOperands(); i
< n
; ++i
) {
1173 MachineOperand
&MO
= In
->getOperand(i
);
1174 if (MO
.isReg() && MO
.isUse()) {
1175 if (MO
.getReg() == PredR
) // Found an intervening use of PredR.
1181 instr_iterator After
= BumpI
;
1182 instr_iterator From
= CmpI
;
1183 BB
->splice(std::next(After
), BB
, From
);
1188 assert (FoundBump
&& "Cannot determine instruction order");
1193 MachineInstr
*HexagonHardwareLoops::defWithImmediate(unsigned R
) {
1194 MachineInstr
*DI
= MRI
->getVRegDef(R
);
1195 unsigned DOpc
= DI
->getOpcode();
1197 case Hexagon::A2_tfrsi
:
1198 case Hexagon::A2_tfrpi
:
1199 case Hexagon::CONST32_Int_Real
:
1200 case Hexagon::CONST64_Int_Real
:
1207 int64_t HexagonHardwareLoops::getImmediate(MachineOperand
&MO
) {
1211 unsigned R
= MO
.getReg();
1212 MachineInstr
*DI
= defWithImmediate(R
);
1213 assert(DI
&& "Need an immediate operand");
1214 // All currently supported "define-with-immediate" instructions have the
1215 // actual immediate value in the operand(1).
1216 int64_t v
= DI
->getOperand(1).getImm();
1221 void HexagonHardwareLoops::setImmediate(MachineOperand
&MO
, int64_t Val
) {
1228 unsigned R
= MO
.getReg();
1229 MachineInstr
*DI
= defWithImmediate(R
);
1230 if (MRI
->hasOneNonDBGUse(R
)) {
1231 // If R has only one use, then just change its defining instruction to
1232 // the new immediate value.
1233 DI
->getOperand(1).setImm(Val
);
1237 const TargetRegisterClass
*RC
= MRI
->getRegClass(R
);
1238 unsigned NewR
= MRI
->createVirtualRegister(RC
);
1239 MachineBasicBlock
&B
= *DI
->getParent();
1240 DebugLoc DL
= DI
->getDebugLoc();
1241 BuildMI(B
, DI
, DL
, TII
->get(DI
->getOpcode()), NewR
)
1247 bool HexagonHardwareLoops::fixupInductionVariable(MachineLoop
*L
) {
1248 MachineBasicBlock
*Header
= L
->getHeader();
1249 MachineBasicBlock
*Preheader
= L
->getLoopPreheader();
1250 MachineBasicBlock
*Latch
= L
->getLoopLatch();
1252 if (!Header
|| !Preheader
|| !Latch
)
1255 // These data structures follow the same concept as the corresponding
1256 // ones in findInductionRegister (where some comments are).
1257 typedef std::pair
<unsigned,int64_t> RegisterBump
;
1258 typedef std::pair
<unsigned,RegisterBump
> RegisterInduction
;
1259 typedef std::set
<RegisterInduction
> RegisterInductionSet
;
1261 // Register candidates for induction variables, with their associated bumps.
1262 RegisterInductionSet IndRegs
;
1264 // Look for induction patterns:
1265 // vreg1 = PHI ..., [ latch, vreg2 ]
1266 // vreg2 = ADD vreg1, imm
1267 typedef MachineBasicBlock::instr_iterator instr_iterator
;
1268 for (instr_iterator I
= Header
->instr_begin(), E
= Header
->instr_end();
1269 I
!= E
&& I
->isPHI(); ++I
) {
1270 MachineInstr
*Phi
= &*I
;
1272 // Have a PHI instruction.
1273 for (unsigned i
= 1, n
= Phi
->getNumOperands(); i
< n
; i
+= 2) {
1274 if (Phi
->getOperand(i
+1).getMBB() != Latch
)
1277 unsigned PhiReg
= Phi
->getOperand(i
).getReg();
1278 MachineInstr
*DI
= MRI
->getVRegDef(PhiReg
);
1279 unsigned UpdOpc
= DI
->getOpcode();
1280 bool isAdd
= (UpdOpc
== Hexagon::ADD_ri
);
1283 // If the register operand to the add/sub is the PHI we are looking
1284 // at, this meets the induction pattern.
1285 unsigned IndReg
= DI
->getOperand(1).getReg();
1286 if (MRI
->getVRegDef(IndReg
) == Phi
) {
1287 unsigned UpdReg
= DI
->getOperand(0).getReg();
1288 int64_t V
= DI
->getOperand(2).getImm();
1289 IndRegs
.insert(std::make_pair(UpdReg
, std::make_pair(IndReg
, V
)));
1295 if (IndRegs
.empty())
1298 MachineBasicBlock
*TB
= nullptr, *FB
= nullptr;
1299 SmallVector
<MachineOperand
,2> Cond
;
1300 // AnalyzeBranch returns true if it fails to analyze branch.
1301 bool NotAnalyzed
= TII
->AnalyzeBranch(*Latch
, TB
, FB
, Cond
, false);
1305 // Check if the latch branch is unconditional.
1309 if (TB
!= Header
&& FB
!= Header
)
1310 // The latch does not go back to the header. Not a latch we know and love.
1313 // Expecting a predicate register as a condition. It won't be a hardware
1314 // predicate register at this point yet, just a vreg.
1315 // HexagonInstrInfo::AnalyzeBranch for negated branches inserts imm(0)
1316 // into Cond, followed by the predicate register. For non-negated branches
1317 // it's just the register.
1318 unsigned CSz
= Cond
.size();
1319 if (CSz
!= 1 && CSz
!= 2)
1322 unsigned P
= Cond
[CSz
-1].getReg();
1323 MachineInstr
*PredDef
= MRI
->getVRegDef(P
);
1325 if (!PredDef
->isCompare())
1328 SmallSet
<unsigned,2> CmpRegs
;
1329 MachineOperand
*CmpImmOp
= nullptr;
1331 // Go over all operands to the compare and look for immediate and register
1332 // operands. Assume that if the compare has a single register use and a
1333 // single immediate operand, then the register is being compared with the
1335 for (unsigned i
= 0, n
= PredDef
->getNumOperands(); i
< n
; ++i
) {
1336 MachineOperand
&MO
= PredDef
->getOperand(i
);
1338 // Skip all implicit references. In one case there was:
1339 // %vreg140<def> = FCMPUGT32_rr %vreg138, %vreg139, %USR<imp-use>
1340 if (MO
.isImplicit())
1343 unsigned R
= MO
.getReg();
1344 if (!defWithImmediate(R
)) {
1345 CmpRegs
.insert(MO
.getReg());
1348 // Consider the register to be the "immediate" operand.
1353 } else if (MO
.isImm()) {
1354 if (CmpImmOp
) // A second immediate argument? Confusing. Bail out.
1360 if (CmpRegs
.empty())
1363 // Check if the compared register follows the order we want. Fix if needed.
1364 for (RegisterInductionSet::iterator I
= IndRegs
.begin(), E
= IndRegs
.end();
1366 // This is a success. If the register used in the comparison is one that
1367 // we have identified as a bumped (updated) induction register, there is
1369 if (CmpRegs
.count(I
->first
))
1372 // Otherwise, if the register being compared comes out of a PHI node,
1373 // and has been recognized as following the induction pattern, and is
1374 // compared against an immediate, we can fix it.
1375 const RegisterBump
&RB
= I
->second
;
1376 if (CmpRegs
.count(RB
.first
)) {
1380 int64_t CmpImm
= getImmediate(*CmpImmOp
);
1381 int64_t V
= RB
.second
;
1382 if (V
> 0 && CmpImm
+V
< CmpImm
) // Overflow (64-bit).
1384 if (V
< 0 && CmpImm
+V
> CmpImm
) // Overflow (64-bit).
1387 // Some forms of cmp-immediate allow u9 and s10. Assume the worst case
1388 // scenario, i.e. an 8-bit value.
1389 if (CmpImmOp
->isImm() && !isInt
<8>(CmpImm
))
1392 // Make sure that the compare happens after the bump. Otherwise,
1393 // after the fixup, the compare would use a yet-undefined register.
1394 MachineInstr
*BumpI
= MRI
->getVRegDef(I
->first
);
1395 bool Order
= orderBumpCompare(BumpI
, PredDef
);
1399 // Finally, fix the compare instruction.
1400 setImmediate(*CmpImmOp
, CmpImm
);
1401 for (unsigned i
= 0, n
= PredDef
->getNumOperands(); i
< n
; ++i
) {
1402 MachineOperand
&MO
= PredDef
->getOperand(i
);
1403 if (MO
.isReg() && MO
.getReg() == RB
.first
) {
1404 MO
.setReg(I
->first
);
1415 /// \brief Create a preheader for a given loop.
1416 MachineBasicBlock
*HexagonHardwareLoops::createPreheaderForLoop(
1418 if (MachineBasicBlock
*TmpPH
= L
->getLoopPreheader())
1421 MachineBasicBlock
*Header
= L
->getHeader();
1422 MachineBasicBlock
*Latch
= L
->getLoopLatch();
1423 MachineFunction
*MF
= Header
->getParent();
1426 if (!Latch
|| Header
->hasAddressTaken())
1429 typedef MachineBasicBlock::instr_iterator instr_iterator
;
1431 // Verify that all existing predecessors have analyzable branches
1432 // (or no branches at all).
1433 typedef std::vector
<MachineBasicBlock
*> MBBVector
;
1434 MBBVector
Preds(Header
->pred_begin(), Header
->pred_end());
1435 SmallVector
<MachineOperand
,2> Tmp1
;
1436 MachineBasicBlock
*TB
= nullptr, *FB
= nullptr;
1438 if (TII
->AnalyzeBranch(*Latch
, TB
, FB
, Tmp1
, false))
1441 for (MBBVector::iterator I
= Preds
.begin(), E
= Preds
.end(); I
!= E
; ++I
) {
1442 MachineBasicBlock
*PB
= *I
;
1444 bool NotAnalyzed
= TII
->AnalyzeBranch(*PB
, TB
, FB
, Tmp1
, false);
1450 MachineBasicBlock
*NewPH
= MF
->CreateMachineBasicBlock();
1451 MF
->insert(Header
, NewPH
);
1453 if (Header
->pred_size() > 2) {
1454 // Ensure that the header has only two predecessors: the preheader and
1455 // the loop latch. Any additional predecessors of the header should
1456 // join at the newly created preheader. Inspect all PHI nodes from the
1457 // header and create appropriate corresponding PHI nodes in the preheader.
1459 for (instr_iterator I
= Header
->instr_begin(), E
= Header
->instr_end();
1460 I
!= E
&& I
->isPHI(); ++I
) {
1461 MachineInstr
*PN
= &*I
;
1463 const MCInstrDesc
&PD
= TII
->get(TargetOpcode::PHI
);
1464 MachineInstr
*NewPN
= MF
->CreateMachineInstr(PD
, DL
);
1465 NewPH
->insert(NewPH
->end(), NewPN
);
1467 unsigned PR
= PN
->getOperand(0).getReg();
1468 const TargetRegisterClass
*RC
= MRI
->getRegClass(PR
);
1469 unsigned NewPR
= MRI
->createVirtualRegister(RC
);
1470 NewPN
->addOperand(MachineOperand::CreateReg(NewPR
, true));
1472 // Copy all non-latch operands of a header's PHI node to the newly
1473 // created PHI node in the preheader.
1474 for (unsigned i
= 1, n
= PN
->getNumOperands(); i
< n
; i
+= 2) {
1475 unsigned PredR
= PN
->getOperand(i
).getReg();
1476 MachineBasicBlock
*PredB
= PN
->getOperand(i
+1).getMBB();
1480 NewPN
->addOperand(MachineOperand::CreateReg(PredR
, false));
1481 NewPN
->addOperand(MachineOperand::CreateMBB(PredB
));
1484 // Remove copied operands from the old PHI node and add the value
1485 // coming from the preheader's PHI.
1486 for (int i
= PN
->getNumOperands()-2; i
> 0; i
-= 2) {
1487 MachineBasicBlock
*PredB
= PN
->getOperand(i
+1).getMBB();
1488 if (PredB
!= Latch
) {
1489 PN
->RemoveOperand(i
+1);
1490 PN
->RemoveOperand(i
);
1493 PN
->addOperand(MachineOperand::CreateReg(NewPR
, false));
1494 PN
->addOperand(MachineOperand::CreateMBB(NewPH
));
1498 assert(Header
->pred_size() == 2);
1500 // The header has only two predecessors, but the non-latch predecessor
1501 // is not a preheader (e.g. it has other successors, etc.)
1502 // In such a case we don't need any extra PHI nodes in the new preheader,
1503 // all we need is to adjust existing PHIs in the header to now refer to
1504 // the new preheader.
1505 for (instr_iterator I
= Header
->instr_begin(), E
= Header
->instr_end();
1506 I
!= E
&& I
->isPHI(); ++I
) {
1507 MachineInstr
*PN
= &*I
;
1508 for (unsigned i
= 1, n
= PN
->getNumOperands(); i
< n
; i
+= 2) {
1509 MachineOperand
&MO
= PN
->getOperand(i
+1);
1510 if (MO
.getMBB() != Latch
)
1516 // "Reroute" the CFG edges to link in the new preheader.
1517 // If any of the predecessors falls through to the header, insert a branch
1518 // to the new preheader in that place.
1519 SmallVector
<MachineOperand
,1> Tmp2
;
1520 SmallVector
<MachineOperand
,1> EmptyCond
;
1524 for (MBBVector::iterator I
= Preds
.begin(), E
= Preds
.end(); I
!= E
; ++I
) {
1525 MachineBasicBlock
*PB
= *I
;
1528 bool NotAnalyzed
= TII
->AnalyzeBranch(*PB
, TB
, FB
, Tmp2
, false);
1529 (void)NotAnalyzed
; // suppress compiler warning
1530 assert (!NotAnalyzed
&& "Should be analyzable!");
1531 if (TB
!= Header
&& (Tmp2
.empty() || FB
!= Header
))
1532 TII
->InsertBranch(*PB
, NewPH
, nullptr, EmptyCond
, DL
);
1533 PB
->ReplaceUsesOfBlockWith(Header
, NewPH
);
1537 // It can happen that the latch block will fall through into the header.
1538 // Insert an unconditional branch to the header.
1540 bool LatchNotAnalyzed
= TII
->AnalyzeBranch(*Latch
, TB
, FB
, Tmp2
, false);
1541 (void)LatchNotAnalyzed
; // suppress compiler warning
1542 assert (!LatchNotAnalyzed
&& "Should be analyzable!");
1544 TII
->InsertBranch(*Latch
, Header
, nullptr, EmptyCond
, DL
);
1546 // Finally, the branch from the preheader to the header.
1547 TII
->InsertBranch(*NewPH
, Header
, nullptr, EmptyCond
, DL
);
1548 NewPH
->addSuccessor(Header
);