1//===- HexagonHardwareLoops.cpp - Identify and generate hardware loops ----===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This pass identifies loops where we can generate the Hexagon hardware
10// loop instruction. The hardware loop can perform loop branches with a
11// zero-cycle overhead.
12//
13// The pattern that defines the induction variable can changed depending on
14// prior optimizations. For example, the IndVarSimplify phase run by 'opt'
15// normalizes induction variables, and the Loop Strength Reduction pass
16// run by 'llc' may also make changes to the induction variable.
17// The pattern detected by this phase is due to running Strength Reduction.
18//
19// Criteria for hardware loops:
20// - Countable loops (w/ ind. var for a trip count)
21// - Assumes loops are normalized by IndVarSimplify
22// - Try inner-most loops first
23// - No function calls in loops.
24//
25//===----------------------------------------------------------------------===//
26
27#include "Hexagon.h"
28#include "HexagonInstrInfo.h"
29#include "HexagonSubtarget.h"
30#include "llvm/ADT/ArrayRef.h"
31#include "llvm/ADT/STLExtras.h"
32#include "llvm/ADT/SmallSet.h"
33#include "llvm/ADT/SmallVector.h"
34#include "llvm/ADT/Statistic.h"
35#include "llvm/ADT/StringRef.h"
36#include "llvm/CodeGen/MachineBasicBlock.h"
37#include "llvm/CodeGen/MachineDominators.h"
38#include "llvm/CodeGen/MachineFunction.h"
39#include "llvm/CodeGen/MachineFunctionPass.h"
40#include "llvm/CodeGen/MachineInstr.h"
41#include "llvm/CodeGen/MachineInstrBuilder.h"
42#include "llvm/CodeGen/MachineLoopInfo.h"
43#include "llvm/CodeGen/MachineOperand.h"
44#include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"
45#include "llvm/CodeGen/MachineRegisterInfo.h"
46#include "llvm/CodeGen/TargetRegisterInfo.h"
47#include "llvm/IR/DebugLoc.h"
48#include "llvm/InitializePasses.h"
49#include "llvm/Pass.h"
50#include "llvm/Support/CommandLine.h"
51#include "llvm/Support/Debug.h"
52#include "llvm/Support/ErrorHandling.h"
53#include "llvm/Support/MathExtras.h"
54#include "llvm/Support/raw_ostream.h"
55#include <cassert>
56#include <cstdint>
57#include <cstdlib>
58#include <iterator>
59#include <map>
60#include <set>
61#include <string>
62#include <utility>
63#include <vector>
64
65using namespace llvm;
66
67#define DEBUG_TYPE "hwloops"
68
69#ifndef NDEBUG
70static cl::opt<int> HWLoopLimit("hexagon-max-hwloop", cl::Hidden, cl::init(-1));
71
72// Option to create preheader only for a specific function.
73static cl::opt<std::string> PHFn("hexagon-hwloop-phfn", cl::Hidden,
74 cl::init(""));
75#endif
76
77// Option to create a preheader if one doesn't exist.
78static cl::opt<bool> HWCreatePreheader("hexagon-hwloop-preheader",
79 cl::Hidden, cl::init(Val: true),
80 cl::desc("Add a preheader to a hardware loop if one doesn't exist"));
81
82// Turn it off by default. If a preheader block is not created here, the
83// software pipeliner may be unable to find a block suitable to serve as
84// a preheader. In that case SWP will not run.
85static cl::opt<bool> SpecPreheader("hwloop-spec-preheader", cl::Hidden,
86 cl::desc("Allow speculation of preheader "
87 "instructions"));
88
89STATISTIC(NumHWLoops, "Number of loops converted to hardware loops");
90
91namespace {
92
93 class CountValue;
94
95 struct HexagonHardwareLoops : public MachineFunctionPass {
96 MachineLoopInfo *MLI;
97 MachineRegisterInfo *MRI;
98 MachineDominatorTree *MDT;
99 const HexagonInstrInfo *TII;
100 const HexagonRegisterInfo *TRI;
101 MachineOptimizationRemarkEmitter *MORE;
102#ifndef NDEBUG
103 static int Counter;
104#endif
105
106 public:
107 static char ID;
108
109 HexagonHardwareLoops() : MachineFunctionPass(ID) {}
110
111 bool runOnMachineFunction(MachineFunction &MF) override;
112
113 StringRef getPassName() const override { return "Hexagon Hardware Loops"; }
114
115 void getAnalysisUsage(AnalysisUsage &AU) const override {
116 AU.addRequired<MachineDominatorTreeWrapperPass>();
117 AU.addRequired<MachineLoopInfoWrapperPass>();
118 AU.addRequired<MachineOptimizationRemarkEmitterPass>();
119 MachineFunctionPass::getAnalysisUsage(AU);
120 }
121
122 private:
123 using LoopFeederMap = std::map<Register, MachineInstr *>;
124
125 /// Kinds of comparisons in the compare instructions.
126 struct Comparison {
127 enum Kind {
128 EQ = 0x01,
129 NE = 0x02,
130 L = 0x04,
131 G = 0x08,
132 U = 0x40,
133 LTs = L,
134 LEs = L | EQ,
135 GTs = G,
136 GEs = G | EQ,
137 LTu = L | U,
138 LEu = L | EQ | U,
139 GTu = G | U,
140 GEu = G | EQ | U
141 };
142
143 static Kind getSwappedComparison(Kind Cmp) {
144 assert ((!((Cmp & L) && (Cmp & G))) && "Malformed comparison operator");
145 if ((Cmp & L) || (Cmp & G))
146 return (Kind)(Cmp ^ (L|G));
147 return Cmp;
148 }
149
150 static Kind getNegatedComparison(Kind Cmp) {
151 if ((Cmp & L) || (Cmp & G))
152 return (Kind)((Cmp ^ (L | G)) ^ EQ);
153 if ((Cmp & NE) || (Cmp & EQ))
154 return (Kind)(Cmp ^ (EQ | NE));
155 return (Kind)0;
156 }
157
158 static bool isSigned(Kind Cmp) {
159 return (Cmp & (L | G) && !(Cmp & U));
160 }
161
162 static bool isUnsigned(Kind Cmp) {
163 return (Cmp & U);
164 }
165 };
166
167 /// Find the register that contains the loop controlling
168 /// induction variable.
169 /// If successful, it will return true and set the \p Reg, \p IVBump
170 /// and \p IVOp arguments. Otherwise it will return false.
171 /// The returned induction register is the register R that follows the
172 /// following induction pattern:
173 /// loop:
174 /// R = phi ..., [ R.next, LatchBlock ]
175 /// R.next = R + #bump
176 /// if (R.next < #N) goto loop
177 /// IVBump is the immediate value added to R, and IVOp is the instruction
178 /// "R.next = R + #bump".
179 bool findInductionRegister(MachineLoop *L, Register &Reg,
180 int64_t &IVBump, MachineInstr *&IVOp) const;
181
182 /// Return the comparison kind for the specified opcode.
183 Comparison::Kind getComparisonKind(unsigned CondOpc,
184 MachineOperand *InitialValue,
185 const MachineOperand *Endvalue,
186 int64_t IVBump) const;
187
188 /// Analyze the statements in a loop to determine if the loop
189 /// has a computable trip count and, if so, return a value that represents
190 /// the trip count expression.
191 CountValue *getLoopTripCount(MachineLoop *L,
192 SmallVectorImpl<MachineInstr *> &OldInsts);
193
194 /// Return the expression that represents the number of times
195 /// a loop iterates. The function takes the operands that represent the
196 /// loop start value, loop end value, and induction value. Based upon
197 /// these operands, the function attempts to compute the trip count.
198 /// If the trip count is not directly available (as an immediate value,
199 /// or a register), the function will attempt to insert computation of it
200 /// to the loop's preheader.
201 CountValue *computeCount(MachineLoop *Loop, const MachineOperand *Start,
202 const MachineOperand *End, Register IVReg,
203 int64_t IVBump, Comparison::Kind Cmp) const;
204
205 /// Return true if the instruction is not valid within a hardware
206 /// loop.
207 bool isInvalidLoopOperation(const MachineInstr *MI,
208 bool IsInnerHWLoop) const;
209
210 /// Return true if the loop contains an instruction that inhibits
211 /// using the hardware loop.
212 bool containsInvalidInstruction(MachineLoop *L, bool IsInnerHWLoop) const;
213
214 /// Given a loop, check if we can convert it to a hardware loop.
215 /// If so, then perform the conversion and return true.
216 bool convertToHardwareLoop(MachineLoop *L, bool &L0used, bool &L1used);
217
218 /// Return true if the instruction is now dead.
219 bool isDead(const MachineInstr *MI,
220 SmallVectorImpl<MachineInstr *> &DeadPhis) const;
221
222 /// Remove the instruction if it is now dead.
223 void removeIfDead(MachineInstr *MI);
224
225 /// Make sure that the "bump" instruction executes before the
226 /// compare. We need that for the IV fixup, so that the compare
227 /// instruction would not use a bumped value that has not yet been
228 /// defined. If the instructions are out of order, try to reorder them.
229 bool orderBumpCompare(MachineInstr *BumpI, MachineInstr *CmpI);
230
231 /// Return true if MO and MI pair is visited only once. If visited
232 /// more than once, this indicates there is recursion. In such a case,
233 /// return false.
234 bool isLoopFeeder(MachineLoop *L, MachineBasicBlock *A, MachineInstr *MI,
235 const MachineOperand *MO,
236 LoopFeederMap &LoopFeederPhi) const;
237
238 /// Return true if the Phi may generate a value that may underflow,
239 /// or may wrap.
240 bool phiMayWrapOrUnderflow(MachineInstr *Phi, const MachineOperand *EndVal,
241 MachineBasicBlock *MBB, MachineLoop *L,
242 LoopFeederMap &LoopFeederPhi) const;
243
244 /// Return true if the induction variable may underflow an unsigned
245 /// value in the first iteration.
246 bool loopCountMayWrapOrUnderFlow(const MachineOperand *InitVal,
247 const MachineOperand *EndVal,
248 MachineBasicBlock *MBB, MachineLoop *L,
249 LoopFeederMap &LoopFeederPhi) const;
250
251 /// Check if the given operand has a compile-time known constant
252 /// value. Return true if yes, and false otherwise. When returning true, set
253 /// Val to the corresponding constant value.
254 bool checkForImmediate(const MachineOperand &MO, int64_t &Val) const;
255
256 /// Check if the operand has a compile-time known constant value.
257 bool isImmediate(const MachineOperand &MO) const {
258 int64_t V;
259 return checkForImmediate(MO, Val&: V);
260 }
261
262 /// Return the immediate for the specified operand.
263 int64_t getImmediate(const MachineOperand &MO) const {
264 int64_t V;
265 if (!checkForImmediate(MO, Val&: V))
266 llvm_unreachable("Invalid operand");
267 return V;
268 }
269
270 /// Reset the given machine operand to now refer to a new immediate
271 /// value. Assumes that the operand was already referencing an immediate
272 /// value, either directly, or via a register.
273 void setImmediate(MachineOperand &MO, int64_t Val);
274
275 /// If DI is a post-increment instruction whose base register is defined
276 /// by Phi and whose incremented address is PhiOpReg (the register feeding
277 /// Phi from the latch), extract the induction register and immediate bump
278 /// into IndReg and IVBump and return true. Returns false otherwise.
279 bool tryExtractPostIncInduction(MachineInstr *DI, MachineInstr *Phi,
280 Register PhiOpReg, Register &IndReg,
281 int64_t &IVBump) const;
282
283 /// Fix the data flow of the induction variable.
284 /// The desired flow is: phi ---> bump -+-> comparison-in-latch.
285 /// |
286 /// +-> back to phi
287 /// where "bump" is the increment of the induction variable:
288 /// iv = iv + #const.
289 /// Due to some prior code transformations, the actual flow may look
290 /// like this:
291 /// phi -+-> bump ---> back to phi
292 /// |
293 /// +-> comparison-in-latch (against upper_bound-bump),
294 /// i.e. the comparison that controls the loop execution may be using
295 /// the value of the induction variable from before the increment.
296 ///
297 /// Return true if the loop's flow is the desired one (i.e. it's
298 /// either been fixed, or no fixing was necessary).
299 /// Otherwise, return false. This can happen if the induction variable
300 /// couldn't be identified, or if the value in the latch's comparison
301 /// cannot be adjusted to reflect the post-bump value.
302 bool fixupInductionVariable(MachineLoop *L);
303
304 /// Given a loop, if it does not have a preheader, create one.
305 /// Return the block that is the preheader.
306 MachineBasicBlock *createPreheaderForLoop(MachineLoop *L);
307 };
308
309 char HexagonHardwareLoops::ID = 0;
310#ifndef NDEBUG
311 int HexagonHardwareLoops::Counter = 0;
312#endif
313
314 /// Abstraction for a trip count of a loop. A smaller version
315 /// of the MachineOperand class without the concerns of changing the
316 /// operand representation.
317 class CountValue {
318 public:
319 enum CountValueType {
320 CV_Register,
321 CV_Immediate
322 };
323
324 private:
325 CountValueType Kind;
326 union Values {
327 Values() : R{.Reg: Register(), .Sub: 0} {}
328 Values(const Values&) = default;
329 struct {
330 Register Reg;
331 unsigned Sub;
332 } R;
333 unsigned ImmVal;
334 } Contents;
335
336 public:
337 explicit CountValue(CountValueType t, Register v, unsigned u = 0) {
338 Kind = t;
339 if (Kind == CV_Register) {
340 Contents.R.Reg = v;
341 Contents.R.Sub = u;
342 } else {
343 Contents.ImmVal = v;
344 }
345 }
346
347 bool isReg() const { return Kind == CV_Register; }
348 bool isImm() const { return Kind == CV_Immediate; }
349
350 Register getReg() const {
351 assert(isReg() && "Wrong CountValue accessor");
352 return Contents.R.Reg;
353 }
354
355 unsigned getSubReg() const {
356 assert(isReg() && "Wrong CountValue accessor");
357 return Contents.R.Sub;
358 }
359
360 unsigned getImm() const {
361 assert(isImm() && "Wrong CountValue accessor");
362 return Contents.ImmVal;
363 }
364
365 void print(raw_ostream &OS, const TargetRegisterInfo *TRI = nullptr) const {
366 if (isReg()) { OS << printReg(Reg: Contents.R.Reg, TRI, SubIdx: Contents.R.Sub); }
367 if (isImm()) { OS << Contents.ImmVal; }
368 }
369 };
370
371} // end anonymous namespace
372
373INITIALIZE_PASS_BEGIN(HexagonHardwareLoops, "hwloops",
374 "Hexagon Hardware Loops", false, false)
375INITIALIZE_PASS_DEPENDENCY(MachineDominatorTreeWrapperPass)
376INITIALIZE_PASS_DEPENDENCY(MachineLoopInfoWrapperPass)
377INITIALIZE_PASS_END(HexagonHardwareLoops, "hwloops",
378 "Hexagon Hardware Loops", false, false)
379
380FunctionPass *llvm::createHexagonHardwareLoops() {
381 return new HexagonHardwareLoops();
382}
383
384bool HexagonHardwareLoops::runOnMachineFunction(MachineFunction &MF) {
385 LLVM_DEBUG(dbgs() << "********* Hexagon Hardware Loops *********\n");
386 if (skipFunction(F: MF.getFunction()))
387 return false;
388
389 bool Changed = false;
390
391 MLI = &getAnalysis<MachineLoopInfoWrapperPass>().getLI();
392 MRI = &MF.getRegInfo();
393 MDT = &getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();
394 const HexagonSubtarget &HST = MF.getSubtarget<HexagonSubtarget>();
395 TII = HST.getInstrInfo();
396 TRI = HST.getRegisterInfo();
397
398 MORE = &getAnalysis<MachineOptimizationRemarkEmitterPass>().getORE();
399
400 for (auto &L : *MLI)
401 if (L->isOutermost()) {
402 bool L0Used = false;
403 bool L1Used = false;
404 Changed |= convertToHardwareLoop(L, L0used&: L0Used, L1used&: L1Used);
405 }
406
407 return Changed;
408}
409
410bool HexagonHardwareLoops::tryExtractPostIncInduction(MachineInstr *DI,
411 MachineInstr *Phi,
412 Register PhiOpReg,
413 Register &IndReg,
414 int64_t &IVBump) const {
415 if (!TII->isPostIncWithImmOffset(MI: *DI))
416 return false;
417
418 unsigned BasePos, OffsetPos;
419 if (!TII->getBaseAndOffsetPosition(MI: *DI, BasePos, OffsetPos))
420 return false;
421
422 if (BasePos >= DI->getNumOperands() || OffsetPos >= DI->getNumOperands())
423 return false;
424
425 // A post-increment load also defines the loaded value, which is unrelated
426 // to the base. Only the incremented address, tied to the base operand, is
427 // "base + offset", so require that it is what feeds the PHI.
428 const MachineOperand &BaseOp = DI->getOperand(i: BasePos);
429 if (!BaseOp.isReg() || !BaseOp.isTied())
430 return false;
431 if (DI->getOperand(i: DI->findTiedOperandIdx(OpIdx: BasePos)).getReg() != PhiOpReg)
432 return false;
433
434 IndReg = BaseOp.getReg();
435 IVBump = DI->getOperand(i: OffsetPos).getImm();
436 return MRI->getVRegDef(Reg: IndReg) == Phi;
437}
438
439bool HexagonHardwareLoops::findInductionRegister(MachineLoop *L,
440 Register &Reg,
441 int64_t &IVBump,
442 MachineInstr *&IVOp
443 ) const {
444 MachineBasicBlock *Header = L->getHeader();
445 MachineBasicBlock *Preheader = MLI->findLoopPreheader(L, SpeculativePreheader: SpecPreheader);
446 MachineBasicBlock *Latch = L->getLoopLatch();
447 MachineBasicBlock *ExitingBlock = L->findLoopControlBlock();
448 if (!Header || !Preheader || !Latch || !ExitingBlock)
449 return false;
450
451 // This pair represents an induction register together with an immediate
452 // value that will be added to it in each loop iteration.
453 using RegisterBump = std::pair<Register, int64_t>;
454
455 // Mapping: R.next -> (R, bump), where R, R.next and bump are derived
456 // from an induction operation
457 // R.next = R + bump
458 // where bump is an immediate value.
459 using InductionMap = std::map<Register, RegisterBump>;
460
461 InductionMap IndMap;
462
463 using instr_iterator = MachineBasicBlock::instr_iterator;
464
465 for (instr_iterator I = Header->instr_begin(), E = Header->instr_end();
466 I != E && I->isPHI(); ++I) {
467 MachineInstr *Phi = &*I;
468
469 // Have a PHI instruction. Get the operand that corresponds to the
470 // latch block, and see if is a result of an addition of form "reg+imm",
471 // where the "reg" is defined by the PHI node we are looking at.
472 for (unsigned i = 1, n = Phi->getNumOperands(); i < n; i += 2) {
473 if (Phi->getOperand(i: i+1).getMBB() != Latch)
474 continue;
475
476 Register PhiOpReg = Phi->getOperand(i).getReg();
477 MachineInstr *DI = MRI->getVRegDef(Reg: PhiOpReg);
478
479 if (DI->getDesc().isAdd()) {
480 // If the register operand to the add is the PHI we're looking at, this
481 // meets the induction pattern.
482 Register IndReg = DI->getOperand(i: 1).getReg();
483 MachineOperand &Opnd2 = DI->getOperand(i: 2);
484 int64_t V;
485 if (MRI->getVRegDef(Reg: IndReg) == Phi && checkForImmediate(MO: Opnd2, Val&: V)) {
486 Register UpdReg = DI->getOperand(i: 0).getReg();
487 IndMap.insert(x: std::make_pair(x&: UpdReg, y: std::make_pair(x&: IndReg, y&: V)));
488 }
489 } else {
490 Register IndReg;
491 int64_t V;
492 if (tryExtractPostIncInduction(DI, Phi, PhiOpReg, IndReg, IVBump&: V))
493 IndMap.insert(x: std::make_pair(x&: PhiOpReg, y: std::make_pair(x&: IndReg, y&: V)));
494 }
495 } // for (i)
496 } // for (instr)
497
498 SmallVector<MachineOperand,2> Cond;
499 MachineBasicBlock *TB = nullptr, *FB = nullptr;
500 bool NotAnalyzed = TII->analyzeBranch(MBB&: *ExitingBlock, TBB&: TB, FBB&: FB, Cond, AllowModify: false);
501 if (NotAnalyzed)
502 return false;
503
504 Register PredR;
505 unsigned PredPos;
506 RegState PredRegFlags;
507 if (!TII->getPredReg(Cond, PredReg&: PredR, PredRegPos&: PredPos, PredRegFlags))
508 return false;
509
510 MachineInstr *PredI = MRI->getVRegDef(Reg: PredR);
511 if (!PredI->isCompare())
512 return false;
513
514 Register CmpReg1, CmpReg2;
515 int64_t CmpImm = 0, CmpMask = 0;
516 bool CmpAnalyzed =
517 TII->analyzeCompare(MI: *PredI, SrcReg&: CmpReg1, SrcReg2&: CmpReg2, Mask&: CmpMask, Value&: CmpImm);
518 // Fail if the compare was not analyzed, or it's not comparing a register
519 // with an immediate value. Not checking the mask here, since we handle
520 // the individual compare opcodes (including A4_cmpb*) later on.
521 if (!CmpAnalyzed)
522 return false;
523
524 // Exactly one of the input registers to the comparison should be among
525 // the induction registers.
526 InductionMap::iterator IndMapEnd = IndMap.end();
527 InductionMap::iterator F = IndMapEnd;
528 if (CmpReg1 != 0) {
529 InductionMap::iterator F1 = IndMap.find(x: CmpReg1);
530 if (F1 != IndMapEnd)
531 F = F1;
532 }
533 if (CmpReg2 != 0) {
534 InductionMap::iterator F2 = IndMap.find(x: CmpReg2);
535 if (F2 != IndMapEnd) {
536 if (F != IndMapEnd)
537 return false;
538 F = F2;
539 }
540 }
541 if (F == IndMapEnd)
542 return false;
543
544 Reg = F->second.first;
545 IVBump = F->second.second;
546 IVOp = MRI->getVRegDef(Reg: F->first);
547 return true;
548}
549
550// Return the comparison kind for the specified opcode.
551HexagonHardwareLoops::Comparison::Kind
552HexagonHardwareLoops::getComparisonKind(unsigned CondOpc,
553 MachineOperand *InitialValue,
554 const MachineOperand *EndValue,
555 int64_t IVBump) const {
556 Comparison::Kind Cmp = (Comparison::Kind)0;
557 switch (CondOpc) {
558 case Hexagon::C2_cmpeq:
559 case Hexagon::C2_cmpeqi:
560 case Hexagon::C2_cmpeqp:
561 Cmp = Comparison::EQ;
562 break;
563 case Hexagon::C4_cmpneq:
564 case Hexagon::C4_cmpneqi:
565 Cmp = Comparison::NE;
566 break;
567 case Hexagon::C2_cmplt:
568 Cmp = Comparison::LTs;
569 break;
570 case Hexagon::C2_cmpltu:
571 Cmp = Comparison::LTu;
572 break;
573 case Hexagon::C4_cmplte:
574 case Hexagon::C4_cmpltei:
575 Cmp = Comparison::LEs;
576 break;
577 case Hexagon::C4_cmplteu:
578 case Hexagon::C4_cmplteui:
579 Cmp = Comparison::LEu;
580 break;
581 case Hexagon::C2_cmpgt:
582 case Hexagon::C2_cmpgti:
583 case Hexagon::C2_cmpgtp:
584 Cmp = Comparison::GTs;
585 break;
586 case Hexagon::C2_cmpgtu:
587 case Hexagon::C2_cmpgtui:
588 case Hexagon::C2_cmpgtup:
589 Cmp = Comparison::GTu;
590 break;
591 case Hexagon::C2_cmpgei:
592 Cmp = Comparison::GEs;
593 break;
594 case Hexagon::C2_cmpgeui:
595 Cmp = Comparison::GEs;
596 break;
597 default:
598 return (Comparison::Kind)0;
599 }
600 return Cmp;
601}
602
603/// Analyze the statements in a loop to determine if the loop has
604/// a computable trip count and, if so, return a value that represents
605/// the trip count expression.
606///
607/// This function iterates over the phi nodes in the loop to check for
608/// induction variable patterns that are used in the calculation for
609/// the number of time the loop is executed.
610CountValue *HexagonHardwareLoops::getLoopTripCount(MachineLoop *L,
611 SmallVectorImpl<MachineInstr *> &OldInsts) {
612 MachineBasicBlock *TopMBB = L->getTopBlock();
613 MachineBasicBlock::pred_iterator PI = TopMBB->pred_begin();
614 assert(PI != TopMBB->pred_end() &&
615 "Loop must have more than one incoming edge!");
616 MachineBasicBlock *Backedge = *PI++;
617 if (PI == TopMBB->pred_end()) // dead loop?
618 return nullptr;
619 MachineBasicBlock *Incoming = *PI++;
620 if (PI != TopMBB->pred_end()) // multiple backedges?
621 return nullptr;
622
623 // Make sure there is one incoming and one backedge and determine which
624 // is which.
625 if (L->contains(BB: Incoming)) {
626 if (L->contains(BB: Backedge))
627 return nullptr;
628 std::swap(a&: Incoming, b&: Backedge);
629 } else if (!L->contains(BB: Backedge))
630 return nullptr;
631
632 // Look for the cmp instruction to determine if we can get a useful trip
633 // count. The trip count can be either a register or an immediate. The
634 // location of the value depends upon the type (reg or imm).
635 MachineBasicBlock *ExitingBlock = L->findLoopControlBlock();
636 if (!ExitingBlock)
637 return nullptr;
638
639 Register IVReg = 0;
640 int64_t IVBump = 0;
641 MachineInstr *IVOp;
642 bool FoundIV = findInductionRegister(L, Reg&: IVReg, IVBump, IVOp);
643 if (!FoundIV)
644 return nullptr;
645
646 MachineBasicBlock *Preheader = MLI->findLoopPreheader(L, SpeculativePreheader: SpecPreheader);
647
648 MachineOperand *InitialValue = nullptr;
649 MachineInstr *IV_Phi = MRI->getVRegDef(Reg: IVReg);
650 MachineBasicBlock *Latch = L->getLoopLatch();
651 for (unsigned i = 1, n = IV_Phi->getNumOperands(); i < n; i += 2) {
652 MachineBasicBlock *MBB = IV_Phi->getOperand(i: i+1).getMBB();
653 if (MBB == Preheader)
654 InitialValue = &IV_Phi->getOperand(i);
655 else if (MBB == Latch)
656 IVReg = IV_Phi->getOperand(i).getReg(); // Want IV reg after bump.
657 }
658 if (!InitialValue)
659 return nullptr;
660
661 SmallVector<MachineOperand,2> Cond;
662 MachineBasicBlock *TB = nullptr, *FB = nullptr;
663 bool NotAnalyzed = TII->analyzeBranch(MBB&: *ExitingBlock, TBB&: TB, FBB&: FB, Cond, AllowModify: false);
664 if (NotAnalyzed)
665 return nullptr;
666
667 MachineBasicBlock *Header = L->getHeader();
668 // TB must be non-null. If FB is also non-null, one of them must be
669 // the header. Otherwise, branch to TB could be exiting the loop, and
670 // the fall through can go to the header.
671 assert (TB && "Exit block without a branch?");
672 if (ExitingBlock != Latch && (TB == Latch || FB == Latch)) {
673 MachineBasicBlock *LTB = nullptr, *LFB = nullptr;
674 SmallVector<MachineOperand,2> LCond;
675 bool NotAnalyzed = TII->analyzeBranch(MBB&: *Latch, TBB&: LTB, FBB&: LFB, Cond&: LCond, AllowModify: false);
676 if (NotAnalyzed)
677 return nullptr;
678 if (TB == Latch)
679 TB = (LTB == Header) ? LTB : LFB;
680 else
681 FB = (LTB == Header) ? LTB: LFB;
682 }
683 assert ((!FB || TB == Header || FB == Header) && "Branches not to header?");
684 if (!TB || (FB && TB != Header && FB != Header))
685 return nullptr;
686
687 // Branches of form "if (!P) ..." cause HexagonInstrInfo::analyzeBranch
688 // to put imm(0), followed by P in the vector Cond.
689 // If TB is not the header, it means that the "not-taken" path must lead
690 // to the header.
691 bool Negated = TII->predOpcodeHasNot(Cond) ^ (TB != Header);
692 Register PredReg;
693 unsigned PredPos;
694 RegState PredRegFlags;
695 if (!TII->getPredReg(Cond, PredReg, PredRegPos&: PredPos, PredRegFlags))
696 return nullptr;
697 MachineInstr *CondI = MRI->getVRegDef(Reg: PredReg);
698 unsigned CondOpc = CondI->getOpcode();
699
700 Register CmpReg1, CmpReg2;
701 int64_t Mask = 0, ImmValue = 0;
702 bool AnalyzedCmp =
703 TII->analyzeCompare(MI: *CondI, SrcReg&: CmpReg1, SrcReg2&: CmpReg2, Mask, Value&: ImmValue);
704 if (!AnalyzedCmp)
705 return nullptr;
706
707 // The comparison operator type determines how we compute the loop
708 // trip count.
709 OldInsts.push_back(Elt: CondI);
710 OldInsts.push_back(Elt: IVOp);
711
712 // Sadly, the following code gets information based on the position
713 // of the operands in the compare instruction. This has to be done
714 // this way, because the comparisons check for a specific relationship
715 // between the operands (e.g. is-less-than), rather than to find out
716 // what relationship the operands are in (as on PPC).
717 Comparison::Kind Cmp;
718 bool isSwapped = false;
719 const MachineOperand &Op1 = CondI->getOperand(i: 1);
720 const MachineOperand &Op2 = CondI->getOperand(i: 2);
721 const MachineOperand *EndValue = nullptr;
722
723 if (Op1.isReg()) {
724 if (Op2.isImm() || Op1.getReg() == IVReg)
725 EndValue = &Op2;
726 else {
727 EndValue = &Op1;
728 isSwapped = true;
729 }
730 }
731
732 if (!EndValue)
733 return nullptr;
734
735 Cmp = getComparisonKind(CondOpc, InitialValue, EndValue, IVBump);
736 if (!Cmp)
737 return nullptr;
738 if (Negated)
739 Cmp = Comparison::getNegatedComparison(Cmp);
740 if (isSwapped)
741 Cmp = Comparison::getSwappedComparison(Cmp);
742
743 if (InitialValue->isReg()) {
744 Register R = InitialValue->getReg();
745 MachineBasicBlock *DefBB = MRI->getDefBlock(Reg: R);
746 if (!MDT->properlyDominates(A: DefBB, B: Header)) {
747 int64_t V;
748 if (!checkForImmediate(MO: *InitialValue, Val&: V))
749 return nullptr;
750 }
751 OldInsts.push_back(Elt: MRI->getVRegDef(Reg: R));
752 }
753 if (EndValue->isReg()) {
754 Register R = EndValue->getReg();
755 MachineBasicBlock *DefBB = MRI->getDefBlock(Reg: R);
756 if (!MDT->properlyDominates(A: DefBB, B: Header)) {
757 int64_t V;
758 if (!checkForImmediate(MO: *EndValue, Val&: V))
759 return nullptr;
760 }
761 OldInsts.push_back(Elt: MRI->getVRegDef(Reg: R));
762 }
763
764 return computeCount(Loop: L, Start: InitialValue, End: EndValue, IVReg, IVBump, Cmp);
765}
766
767/// Helper function that returns the expression that represents the
768/// number of times a loop iterates. The function takes the operands that
769/// represent the loop start value, loop end value, and induction value.
770/// Based upon these operands, the function attempts to compute the trip count.
771CountValue *HexagonHardwareLoops::computeCount(MachineLoop *Loop,
772 const MachineOperand *Start,
773 const MachineOperand *End,
774 Register IVReg,
775 int64_t IVBump,
776 Comparison::Kind Cmp) const {
777 LLVM_DEBUG(llvm::dbgs() << "Loop: " << *Loop << "\n");
778 LLVM_DEBUG(llvm::dbgs() << "Initial Value: " << *Start << "\n");
779 LLVM_DEBUG(llvm::dbgs() << "End Value: " << *End << "\n");
780 LLVM_DEBUG(llvm::dbgs() << "Inc/Dec Value: " << IVBump << "\n");
781 LLVM_DEBUG(llvm::dbgs() << "Comparison: " << Cmp << "\n");
782 // Cannot handle comparison EQ, i.e. while (A == B).
783 if (Cmp == Comparison::EQ)
784 return nullptr;
785
786 // Check if either the start or end values are an assignment of an immediate.
787 // If so, use the immediate value rather than the register.
788 if (Start->isReg()) {
789 const MachineInstr *StartValInstr = MRI->getVRegDef(Reg: Start->getReg());
790 if (StartValInstr && (StartValInstr->getOpcode() == Hexagon::A2_tfrsi ||
791 StartValInstr->getOpcode() == Hexagon::A2_tfrpi))
792 Start = &StartValInstr->getOperand(i: 1);
793 }
794 if (End->isReg()) {
795 const MachineInstr *EndValInstr = MRI->getVRegDef(Reg: End->getReg());
796 if (EndValInstr && (EndValInstr->getOpcode() == Hexagon::A2_tfrsi ||
797 EndValInstr->getOpcode() == Hexagon::A2_tfrpi))
798 End = &EndValInstr->getOperand(i: 1);
799 }
800
801 if (!Start->isReg() && !Start->isImm())
802 return nullptr;
803 if (!End->isReg() && !End->isImm())
804 return nullptr;
805
806 bool CmpLess = Cmp & Comparison::L;
807 bool CmpGreater = Cmp & Comparison::G;
808 bool CmpHasEqual = Cmp & Comparison::EQ;
809
810 // Avoid certain wrap-arounds. This doesn't detect all wrap-arounds.
811 if (CmpLess && IVBump < 0)
812 // Loop going while iv is "less" with the iv value going down. Must wrap.
813 return nullptr;
814
815 if (CmpGreater && IVBump > 0)
816 // Loop going while iv is "greater" with the iv value going up. Must wrap.
817 return nullptr;
818
819 // Phis that may feed into the loop.
820 LoopFeederMap LoopFeederPhi;
821
822 // Check if the initial value may be zero and can be decremented in the first
823 // iteration. If the value is zero, the endloop instruction will not decrement
824 // the loop counter, so we shouldn't generate a hardware loop in this case.
825 if (loopCountMayWrapOrUnderFlow(InitVal: Start, EndVal: End, MBB: Loop->getLoopPreheader(), L: Loop,
826 LoopFeederPhi))
827 return nullptr;
828
829 if (Start->isImm() && End->isImm()) {
830 // Both, start and end are immediates.
831 int64_t StartV = Start->getImm();
832 int64_t EndV = End->getImm();
833 int64_t Dist = EndV - StartV;
834 if (Dist == 0)
835 return nullptr;
836
837 bool Exact = (Dist % IVBump) == 0;
838
839 if (Cmp == Comparison::NE) {
840 if (!Exact)
841 return nullptr;
842 if ((Dist < 0) ^ (IVBump < 0))
843 return nullptr;
844 }
845
846 // For comparisons that include the final value (i.e. include equality
847 // with the final value), we need to increase the distance by 1.
848 if (CmpHasEqual)
849 Dist = Dist > 0 ? Dist+1 : Dist-1;
850
851 // For the loop to iterate, CmpLess should imply Dist > 0. Similarly,
852 // CmpGreater should imply Dist < 0. These conditions could actually
853 // fail, for example, in unreachable code (which may still appear to be
854 // reachable in the CFG).
855 if ((CmpLess && Dist < 0) || (CmpGreater && Dist > 0))
856 return nullptr;
857
858 // "Normalized" distance, i.e. with the bump set to +-1.
859 int64_t Dist1 = (IVBump > 0) ? (Dist + (IVBump - 1)) / IVBump
860 : (-Dist + (-IVBump - 1)) / (-IVBump);
861 assert (Dist1 > 0 && "Fishy thing. Both operands have the same sign.");
862
863 uint64_t Count = Dist1;
864
865 if (Count > 0xFFFFFFFFULL)
866 return nullptr;
867
868 return new CountValue(CountValue::CV_Immediate, Count);
869 }
870
871 // A general case: Start and End are some values, but the actual
872 // iteration count may not be available. If it is not, insert
873 // a computation of it into the preheader.
874
875 // If the induction variable bump is not a power of 2, quit.
876 // Otherwise we'd need a general integer division.
877 if (!isPowerOf2_64(Value: std::abs(i: IVBump)))
878 return nullptr;
879
880 MachineBasicBlock *PH = MLI->findLoopPreheader(L: Loop, SpeculativePreheader: SpecPreheader);
881 assert (PH && "Should have a preheader by now");
882 MachineBasicBlock::iterator InsertPos = PH->getFirstTerminator();
883 DebugLoc DL;
884 if (InsertPos != PH->end())
885 DL = InsertPos->getDebugLoc();
886
887 // If Start is an immediate and End is a register, the trip count
888 // will be "reg - imm". Hexagon's "subtract immediate" instruction
889 // is actually "reg + -imm".
890
891 // If the loop IV is going downwards, i.e. if the bump is negative,
892 // then the iteration count (computed as End-Start) will need to be
893 // negated. To avoid the negation, just swap Start and End.
894 if (IVBump < 0) {
895 std::swap(a&: Start, b&: End);
896 IVBump = -IVBump;
897 std::swap(a&: CmpLess, b&: CmpGreater);
898 }
899 // Cmp may now have a wrong direction, e.g. LEs may now be GEs.
900 // Signedness, and "including equality" are preserved.
901
902 bool RegToImm = Start->isReg() && End->isImm(); // for (reg..imm)
903 bool RegToReg = Start->isReg() && End->isReg(); // for (reg..reg)
904
905 int64_t StartV = 0, EndV = 0;
906 if (Start->isImm())
907 StartV = Start->getImm();
908 if (End->isImm())
909 EndV = End->getImm();
910
911 int64_t AdjV = 0;
912 // To compute the iteration count, we would need this computation:
913 // Count = (End - Start + (IVBump-1)) / IVBump
914 // or, when CmpHasEqual:
915 // Count = (End - Start + (IVBump-1)+1) / IVBump
916 // The "IVBump-1" part is the adjustment (AdjV). We can avoid
917 // generating an instruction specifically to add it if we can adjust
918 // the immediate values for Start or End.
919
920 if (CmpHasEqual) {
921 // Need to add 1 to the total iteration count.
922 if (Start->isImm())
923 StartV--;
924 else if (End->isImm())
925 EndV++;
926 else
927 AdjV += 1;
928 }
929
930 if (Cmp != Comparison::NE) {
931 if (Start->isImm())
932 StartV -= (IVBump-1);
933 else if (End->isImm())
934 EndV += (IVBump-1);
935 else
936 AdjV += (IVBump-1);
937 }
938
939 Register R = 0;
940 unsigned SR = 0;
941 if (Start->isReg()) {
942 R = Start->getReg();
943 SR = Start->getSubReg();
944 } else {
945 R = End->getReg();
946 SR = End->getSubReg();
947 }
948 const TargetRegisterClass *RC = MRI->getRegClass(Reg: R);
949 // Hardware loops cannot handle 64-bit registers. If it's a double
950 // register, it has to have a subregister.
951 if (!SR && RC == &Hexagon::DoubleRegsRegClass)
952 return nullptr;
953 const TargetRegisterClass *IntRC = &Hexagon::IntRegsRegClass;
954
955 // Compute DistR (register with the distance between Start and End).
956 Register DistR;
957 unsigned DistSR;
958
959 // Avoid special case, where the start value is an imm(0).
960 if (Start->isImm() && StartV == 0) {
961 DistR = End->getReg();
962 DistSR = End->getSubReg();
963 } else {
964 const MCInstrDesc &SubD = RegToReg ? TII->get(Opcode: Hexagon::A2_sub) :
965 (RegToImm ? TII->get(Opcode: Hexagon::A2_subri) :
966 TII->get(Opcode: Hexagon::A2_addi));
967 if (RegToReg || RegToImm) {
968 Register SubR = MRI->createVirtualRegister(RegClass: IntRC);
969 MachineInstrBuilder SubIB =
970 BuildMI(BB&: *PH, I: InsertPos, MIMD: DL, MCID: SubD, DestReg: SubR);
971
972 if (RegToReg)
973 SubIB.addReg(RegNo: End->getReg(), Flags: {}, SubReg: End->getSubReg())
974 .addReg(RegNo: Start->getReg(), Flags: {}, SubReg: Start->getSubReg());
975 else
976 SubIB.addImm(Val: EndV).addReg(RegNo: Start->getReg(), Flags: {}, SubReg: Start->getSubReg());
977 DistR = SubR;
978 } else {
979 // If the loop has been unrolled, we should use the original loop count
980 // instead of recalculating the value. This will avoid additional
981 // 'Add' instruction.
982 const MachineInstr *EndValInstr = MRI->getVRegDef(Reg: End->getReg());
983 if (EndValInstr->getOpcode() == Hexagon::A2_addi &&
984 EndValInstr->getOperand(i: 1).getSubReg() == 0 &&
985 EndValInstr->getOperand(i: 2).getImm() == StartV) {
986 DistR = EndValInstr->getOperand(i: 1).getReg();
987 } else {
988 Register SubR = MRI->createVirtualRegister(RegClass: IntRC);
989 MachineInstrBuilder SubIB =
990 BuildMI(BB&: *PH, I: InsertPos, MIMD: DL, MCID: SubD, DestReg: SubR);
991 SubIB.addReg(RegNo: End->getReg(), Flags: {}, SubReg: End->getSubReg()).addImm(Val: -StartV);
992 DistR = SubR;
993 }
994 }
995 DistSR = 0;
996 }
997
998 // From DistR, compute AdjR (register with the adjusted distance).
999 Register AdjR;
1000 unsigned AdjSR;
1001
1002 if (AdjV == 0) {
1003 AdjR = DistR;
1004 AdjSR = DistSR;
1005 } else {
1006 // Generate CountR = ADD DistR, AdjVal
1007 Register AddR = MRI->createVirtualRegister(RegClass: IntRC);
1008 MCInstrDesc const &AddD = TII->get(Opcode: Hexagon::A2_addi);
1009 BuildMI(BB&: *PH, I: InsertPos, MIMD: DL, MCID: AddD, DestReg: AddR)
1010 .addReg(RegNo: DistR, Flags: {}, SubReg: DistSR)
1011 .addImm(Val: AdjV);
1012
1013 AdjR = AddR;
1014 AdjSR = 0;
1015 }
1016
1017 // From AdjR, compute CountR (register with the final count).
1018 Register CountR;
1019 unsigned CountSR;
1020
1021 if (IVBump == 1) {
1022 CountR = AdjR;
1023 CountSR = AdjSR;
1024 } else {
1025 // The IV bump is a power of two. Log_2(IV bump) is the shift amount.
1026 unsigned Shift = Log2_32(Value: IVBump);
1027
1028 // Generate NormR = LSR DistR, Shift.
1029 Register LsrR = MRI->createVirtualRegister(RegClass: IntRC);
1030 const MCInstrDesc &LsrD = TII->get(Opcode: Hexagon::S2_lsr_i_r);
1031 BuildMI(BB&: *PH, I: InsertPos, MIMD: DL, MCID: LsrD, DestReg: LsrR)
1032 .addReg(RegNo: AdjR, Flags: {}, SubReg: AdjSR)
1033 .addImm(Val: Shift);
1034
1035 CountR = LsrR;
1036 CountSR = 0;
1037 }
1038
1039 const TargetRegisterClass *PredRC = &Hexagon::PredRegsRegClass;
1040 Register MuxR = CountR;
1041 unsigned MuxSR = CountSR;
1042 // For the loop count to be valid unsigned number, CmpLess should imply
1043 // Dist >= 0. Similarly, CmpGreater should imply Dist < 0. We can skip the
1044 // check if the initial distance is zero and the comparison is LTu || LTEu.
1045 if (!(Start->isImm() && StartV == 0 && Comparison::isUnsigned(Cmp) &&
1046 CmpLess) &&
1047 (CmpLess || CmpGreater)) {
1048 // Generate:
1049 // DistCheck = CMP_GT DistR, 0 --> CmpLess
1050 // DistCheck = CMP_GT DistR, -1 --> CmpGreater
1051 Register DistCheckR = MRI->createVirtualRegister(RegClass: PredRC);
1052 unsigned DistCheckOpc = (CmpLess && Comparison::isUnsigned(Cmp))
1053 ? Hexagon::C2_cmpgtui
1054 : Hexagon::C2_cmpgti;
1055 const MCInstrDesc &DistCheckD = TII->get(Opcode: DistCheckOpc);
1056 BuildMI(BB&: *PH, I: InsertPos, MIMD: DL, MCID: DistCheckD, DestReg: DistCheckR)
1057 .addReg(RegNo: DistR, Flags: {}, SubReg: DistSR)
1058 .addImm(Val: (CmpLess) ? 0 : -1);
1059
1060 // Generate:
1061 // MUXR = MUX DistCheck, CountR, 1 --> CmpLess
1062 // MUXR = MUX DistCheck, 1, CountR --> CmpGreater
1063 MuxR = MRI->createVirtualRegister(RegClass: IntRC);
1064 if (CmpLess) {
1065 const MCInstrDesc &MuxD = TII->get(Opcode: Hexagon::C2_muxir);
1066 BuildMI(BB&: *PH, I: InsertPos, MIMD: DL, MCID: MuxD, DestReg: MuxR)
1067 .addReg(RegNo: DistCheckR)
1068 .addReg(RegNo: CountR, Flags: {}, SubReg: CountSR)
1069 .addImm(Val: 1);
1070 } else {
1071 const MCInstrDesc &MuxD = TII->get(Opcode: Hexagon::C2_muxri);
1072 BuildMI(BB&: *PH, I: InsertPos, MIMD: DL, MCID: MuxD, DestReg: MuxR)
1073 .addReg(RegNo: DistCheckR)
1074 .addImm(Val: 1)
1075 .addReg(RegNo: CountR, Flags: {}, SubReg: CountSR);
1076 }
1077 MuxSR = 0;
1078 }
1079
1080 return new CountValue(CountValue::CV_Register, MuxR, MuxSR);
1081}
1082
1083/// Return true if the operation is invalid within hardware loop.
1084bool HexagonHardwareLoops::isInvalidLoopOperation(const MachineInstr *MI,
1085 bool IsInnerHWLoop) const {
1086 // Call is not allowed because the callee may use a hardware loop except for
1087 // the case when the call never returns.
1088 if (MI->getDesc().isCall())
1089 return !TII->doesNotReturn(CallMI: *MI);
1090
1091 // Check if the instruction defines a hardware loop register.
1092 using namespace Hexagon;
1093
1094 static const Register Regs01[] = { LC0, SA0, LC1, SA1 };
1095 static const Register Regs1[] = { LC1, SA1 };
1096 auto CheckRegs = IsInnerHWLoop ? ArrayRef(Regs01) : ArrayRef(Regs1);
1097 for (Register R : CheckRegs)
1098 if (MI->modifiesRegister(Reg: R, TRI))
1099 return true;
1100
1101 return false;
1102}
1103
1104/// Return true if the loop contains an instruction that inhibits
1105/// the use of the hardware loop instruction.
1106bool HexagonHardwareLoops::containsInvalidInstruction(MachineLoop *L,
1107 bool IsInnerHWLoop) const {
1108 LLVM_DEBUG(dbgs() << "\nhw_loop head, "
1109 << printMBBReference(**L->block_begin()));
1110 for (MachineBasicBlock *MBB : L->getBlocks()) {
1111 for (const MachineInstr &MI : *MBB) {
1112 if (isInvalidLoopOperation(MI: &MI, IsInnerHWLoop)) {
1113 LLVM_DEBUG(dbgs() << "\nCannot convert to hw_loop due to:";
1114 MI.dump(););
1115 return true;
1116 }
1117 }
1118 }
1119 return false;
1120}
1121
1122/// Returns true if the instruction is dead. This was essentially
1123/// copied from DeadMachineInstructionElim::isDead, but with special cases
1124/// for inline asm, physical registers and instructions with side effects
1125/// removed.
1126bool HexagonHardwareLoops::isDead(const MachineInstr *MI,
1127 SmallVectorImpl<MachineInstr *> &DeadPhis) const {
1128 // Examine each operand.
1129 for (const MachineOperand &MO : MI->operands()) {
1130 if (!MO.isReg() || !MO.isDef())
1131 continue;
1132
1133 Register Reg = MO.getReg();
1134 if (MRI->use_nodbg_empty(RegNo: Reg))
1135 continue;
1136
1137 using use_nodbg_iterator = MachineRegisterInfo::use_nodbg_iterator;
1138
1139 // This instruction has users, but if the only user is the phi node for the
1140 // parent block, and the only use of that phi node is this instruction, then
1141 // this instruction is dead: both it (and the phi node) can be removed.
1142 use_nodbg_iterator I = MRI->use_nodbg_begin(RegNo: Reg);
1143 use_nodbg_iterator End = MRI->use_nodbg_end();
1144 if (std::next(x: I) != End || !I->getParent()->isPHI())
1145 return false;
1146
1147 MachineInstr *OnePhi = I->getParent();
1148 for (const MachineOperand &OPO : OnePhi->operands()) {
1149 if (!OPO.isReg() || !OPO.isDef())
1150 continue;
1151
1152 Register OPReg = OPO.getReg();
1153 use_nodbg_iterator nextJ;
1154 for (use_nodbg_iterator J = MRI->use_nodbg_begin(RegNo: OPReg);
1155 J != End; J = nextJ) {
1156 nextJ = std::next(x: J);
1157 MachineOperand &Use = *J;
1158 MachineInstr *UseMI = Use.getParent();
1159
1160 // If the phi node has a user that is not MI, bail.
1161 if (MI != UseMI)
1162 return false;
1163 }
1164 }
1165 DeadPhis.push_back(Elt: OnePhi);
1166 }
1167
1168 // If there are no defs with uses, the instruction is dead.
1169 return true;
1170}
1171
1172void HexagonHardwareLoops::removeIfDead(MachineInstr *MI) {
1173 // This procedure was essentially copied from DeadMachineInstructionElim.
1174
1175 SmallVector<MachineInstr*, 1> DeadPhis;
1176 if (isDead(MI, DeadPhis)) {
1177 LLVM_DEBUG(dbgs() << "HW looping will remove: " << *MI);
1178
1179 // It is possible that some DBG_VALUE instructions refer to this
1180 // instruction. Examine each def operand for such references;
1181 // if found, mark the DBG_VALUE as undef (but don't delete it).
1182 for (const MachineOperand &MO : MI->operands()) {
1183 if (!MO.isReg() || !MO.isDef())
1184 continue;
1185 Register Reg = MO.getReg();
1186 // We use make_early_inc_range here because setReg below invalidates the
1187 // iterator.
1188 for (MachineOperand &MO :
1189 llvm::make_early_inc_range(Range: MRI->use_operands(Reg))) {
1190 MachineInstr *UseMI = MO.getParent();
1191 if (UseMI == MI)
1192 continue;
1193 if (MO.isDebug())
1194 MO.setReg(0U);
1195 }
1196 }
1197
1198 MI->eraseFromParent();
1199 for (unsigned i = 0; i < DeadPhis.size(); ++i)
1200 DeadPhis[i]->eraseFromParent();
1201 }
1202}
1203
1204/// Check if the loop is a candidate for converting to a hardware
1205/// loop. If so, then perform the transformation.
1206///
1207/// This function works on innermost loops first. A loop can be converted
1208/// if it is a counting loop; either a register value or an immediate.
1209///
1210/// The code makes several assumptions about the representation of the loop
1211/// in llvm.
1212bool HexagonHardwareLoops::convertToHardwareLoop(MachineLoop *L,
1213 bool &RecL0used,
1214 bool &RecL1used) {
1215 // This is just to confirm basic correctness.
1216 assert(L->getHeader() && "Loop without a header?");
1217
1218 bool Changed = false;
1219 bool L0Used = false;
1220 bool L1Used = false;
1221
1222 // Process nested loops first.
1223 for (MachineLoop *I : *L) {
1224 Changed |= convertToHardwareLoop(L: I, RecL0used, RecL1used);
1225 L0Used |= RecL0used;
1226 L1Used |= RecL1used;
1227 }
1228
1229 // If a nested loop has been converted, then we can't convert this loop.
1230 if (Changed && L0Used && L1Used)
1231 return Changed;
1232
1233 unsigned LOOP_i;
1234 unsigned LOOP_r;
1235 unsigned ENDLOOP;
1236
1237 // Flag used to track loopN instruction:
1238 // 1 - Hardware loop is being generated for the inner most loop.
1239 // 0 - Hardware loop is being generated for the outer loop.
1240 unsigned IsInnerHWLoop = 1;
1241
1242 if (L0Used) {
1243 LOOP_i = Hexagon::J2_loop1i;
1244 LOOP_r = Hexagon::J2_loop1r;
1245 ENDLOOP = Hexagon::ENDLOOP1;
1246 IsInnerHWLoop = 0;
1247 } else {
1248 LOOP_i = Hexagon::J2_loop0i;
1249 LOOP_r = Hexagon::J2_loop0r;
1250 ENDLOOP = Hexagon::ENDLOOP0;
1251 }
1252
1253#ifndef NDEBUG
1254 // Stop trying after reaching the limit (if any).
1255 int Limit = HWLoopLimit;
1256 if (Limit >= 0) {
1257 if (Counter >= HWLoopLimit)
1258 return false;
1259 Counter++;
1260 }
1261#endif
1262
1263 // Does the loop contain any invalid instructions?
1264 if (containsInvalidInstruction(L, IsInnerHWLoop)) {
1265 MORE->emit(RemarkBuilder: [&]() {
1266 return MachineOptimizationRemarkMissed(DEBUG_TYPE, "InvalidInstruction",
1267 L->getStartLoc(), L->getHeader())
1268 << "loop contains an instruction that prevents hardware loop "
1269 "generation (e.g. a call or hardware loop register definition)";
1270 });
1271 return false;
1272 }
1273
1274 MachineBasicBlock *LastMBB = L->findLoopControlBlock();
1275 // Check actual CFG successors: analyzeBranch omits implicit fallthroughs.
1276 // Only reject multi-exit loops whose selected exit reaches an unreachable
1277 // sink, preserving valid multi-exit loops.
1278 SmallVector<MachineBasicBlock *, 2> ExitingBlocks;
1279 L->getExitingBlocks(ExitingBlocks);
1280 bool HasUnreachableExit = false;
1281 if (LastMBB && ExitingBlocks.size() > 1) {
1282 for (MachineBasicBlock *Succ : LastMBB->successors()) {
1283 if (!L->contains(BB: Succ) && !Succ->empty() && Succ->succ_empty() &&
1284 !Succ->isReturnBlock()) {
1285 HasUnreachableExit = true;
1286 break;
1287 }
1288 }
1289 }
1290 if (!LastMBB || HasUnreachableExit) {
1291 MORE->emit(RemarkBuilder: [&]() {
1292 return MachineOptimizationRemarkMissed(DEBUG_TYPE, "MultipleExits",
1293 L->getStartLoc(), L->getHeader())
1294 << "loop has multiple exits and cannot be converted to a "
1295 "hardware loop";
1296 });
1297 return false;
1298 }
1299
1300 MachineBasicBlock::iterator LastI = LastMBB->getFirstTerminator();
1301 if (LastI == LastMBB->end())
1302 return false;
1303
1304 // Is the induction variable bump feeding the latch condition?
1305 if (!fixupInductionVariable(L)) {
1306 MORE->emit(RemarkBuilder: [&]() {
1307 return MachineOptimizationRemarkMissed(DEBUG_TYPE, "InductionVariable",
1308 L->getStartLoc(), L->getHeader())
1309 << "could not identify or fix up the induction variable";
1310 });
1311 return false;
1312 }
1313
1314 // Ensure the loop has a preheader: the loop instruction will be
1315 // placed there.
1316 MachineBasicBlock *Preheader = MLI->findLoopPreheader(L, SpeculativePreheader: SpecPreheader);
1317 if (!Preheader) {
1318 Preheader = createPreheaderForLoop(L);
1319 if (!Preheader)
1320 return false;
1321 }
1322
1323 MachineBasicBlock::iterator InsertPos = Preheader->getFirstTerminator();
1324
1325 SmallVector<MachineInstr*, 2> OldInsts;
1326 // Are we able to determine the trip count for the loop?
1327 CountValue *TripCount = getLoopTripCount(L, OldInsts);
1328 if (!TripCount) {
1329 MORE->emit(RemarkBuilder: [&]() {
1330 return MachineOptimizationRemarkMissed(DEBUG_TYPE, "TripCount",
1331 L->getStartLoc(), L->getHeader())
1332 << "trip count of the loop could not be computed";
1333 });
1334 return false;
1335 }
1336
1337 // Is the trip count available in the preheader?
1338 if (TripCount->isReg()) {
1339 // There will be a use of the register inserted into the preheader,
1340 // so make sure that the register is actually defined at that point.
1341 MachineInstr *TCDef = MRI->getVRegDef(Reg: TripCount->getReg());
1342 MachineBasicBlock *BBDef = TCDef->getParent();
1343 if (!MDT->dominates(A: BBDef, B: Preheader)) {
1344 MORE->emit(RemarkBuilder: [&]() {
1345 return MachineOptimizationRemarkMissed(DEBUG_TYPE,
1346 "TripCountNotDominating",
1347 L->getStartLoc(), L->getHeader())
1348 << "trip count register is not available in the loop preheader";
1349 });
1350 return false;
1351 }
1352 }
1353
1354 // Determine the loop start.
1355 MachineBasicBlock *TopBlock = L->getTopBlock();
1356 MachineBasicBlock *ExitingBlock = L->findLoopControlBlock();
1357 MachineBasicBlock *LoopStart = nullptr;
1358 if (ExitingBlock != L->getLoopLatch()) {
1359 MachineBasicBlock *TB = nullptr, *FB = nullptr;
1360 SmallVector<MachineOperand, 2> Cond;
1361
1362 if (TII->analyzeBranch(MBB&: *ExitingBlock, TBB&: TB, FBB&: FB, Cond, AllowModify: false))
1363 return false;
1364
1365 if (L->contains(BB: TB))
1366 LoopStart = TB;
1367 else if (L->contains(BB: FB))
1368 LoopStart = FB;
1369 else
1370 return false;
1371 }
1372 else
1373 LoopStart = TopBlock;
1374
1375 // Convert the loop to a hardware loop.
1376 LLVM_DEBUG(dbgs() << "Change to hardware loop at "; L->dump());
1377 DebugLoc DL;
1378 if (InsertPos != Preheader->end())
1379 DL = InsertPos->getDebugLoc();
1380
1381 if (TripCount->isReg()) {
1382 // Create a copy of the loop count register.
1383 Register CountReg = MRI->createVirtualRegister(RegClass: &Hexagon::IntRegsRegClass);
1384 BuildMI(BB&: *Preheader, I: InsertPos, MIMD: DL, MCID: TII->get(Opcode: TargetOpcode::COPY), DestReg: CountReg)
1385 .addReg(RegNo: TripCount->getReg(), Flags: {}, SubReg: TripCount->getSubReg());
1386 // Add the Loop instruction to the beginning of the loop.
1387 BuildMI(BB&: *Preheader, I: InsertPos, MIMD: DL, MCID: TII->get(Opcode: LOOP_r)).addMBB(MBB: LoopStart)
1388 .addReg(RegNo: CountReg);
1389 } else {
1390 assert(TripCount->isImm() && "Expecting immediate value for trip count");
1391 // Add the Loop immediate instruction to the beginning of the loop,
1392 // if the immediate fits in the instructions. Otherwise, we need to
1393 // create a new virtual register.
1394 int64_t CountImm = TripCount->getImm();
1395 if (!TII->isValidOffset(Opcode: LOOP_i, Offset: CountImm)) {
1396 Register CountReg = MRI->createVirtualRegister(RegClass: &Hexagon::IntRegsRegClass);
1397 BuildMI(BB&: *Preheader, I: InsertPos, MIMD: DL, MCID: TII->get(Opcode: Hexagon::A2_tfrsi), DestReg: CountReg)
1398 .addImm(Val: CountImm);
1399 BuildMI(BB&: *Preheader, I: InsertPos, MIMD: DL, MCID: TII->get(Opcode: LOOP_r))
1400 .addMBB(MBB: LoopStart).addReg(RegNo: CountReg);
1401 } else
1402 BuildMI(BB&: *Preheader, I: InsertPos, MIMD: DL, MCID: TII->get(Opcode: LOOP_i))
1403 .addMBB(MBB: LoopStart).addImm(Val: CountImm);
1404 }
1405
1406 // Make sure the loop start always has a reference in the CFG.
1407 LoopStart->setMachineBlockAddressTaken();
1408
1409 // Replace the loop branch with an endloop instruction.
1410 DebugLoc LastIDL = LastI->getDebugLoc();
1411 BuildMI(BB&: *LastMBB, I: LastI, MIMD: LastIDL, MCID: TII->get(Opcode: ENDLOOP)).addMBB(MBB: LoopStart);
1412
1413 // The loop ends with either:
1414 // - a conditional branch followed by an unconditional branch, or
1415 // - a conditional branch to the loop start.
1416 if (LastI->getOpcode() == Hexagon::J2_jumpt ||
1417 LastI->getOpcode() == Hexagon::J2_jumpf) {
1418 // Delete one and change/add an uncond. branch to out of the loop.
1419 MachineBasicBlock *BranchTarget = LastI->getOperand(i: 1).getMBB();
1420 LastI = LastMBB->erase(I: LastI);
1421 if (!L->contains(BB: BranchTarget)) {
1422 if (LastI != LastMBB->end())
1423 LastI = LastMBB->erase(I: LastI);
1424 SmallVector<MachineOperand, 0> Cond;
1425 TII->insertBranch(MBB&: *LastMBB, TBB: BranchTarget, FBB: nullptr, Cond, DL: LastIDL);
1426 }
1427 } else {
1428 // Conditional branch to loop start; just delete it.
1429 LastMBB->erase(I: LastI);
1430 }
1431 delete TripCount;
1432
1433 // The induction operation and the comparison may now be
1434 // unneeded. If these are unneeded, then remove them.
1435 for (unsigned i = 0; i < OldInsts.size(); ++i)
1436 removeIfDead(MI: OldInsts[i]);
1437
1438 ++NumHWLoops;
1439
1440 MORE->emit(RemarkBuilder: [&]() {
1441 return MachineOptimizationRemark(DEBUG_TYPE, "HardwareLoop",
1442 L->getStartLoc(), L->getHeader())
1443 << "converted loop to hardware loop";
1444 });
1445
1446 // Set RecL1used and RecL0used only after hardware loop has been
1447 // successfully generated. Doing it earlier can cause wrong loop instruction
1448 // to be used.
1449 if (L0Used) // Loop0 was already used. So, the correct loop must be loop1.
1450 RecL1used = true;
1451 else
1452 RecL0used = true;
1453
1454 return true;
1455}
1456
1457bool HexagonHardwareLoops::orderBumpCompare(MachineInstr *BumpI,
1458 MachineInstr *CmpI) {
1459 assert (BumpI != CmpI && "Bump and compare in the same instruction?");
1460
1461 MachineBasicBlock *BB = BumpI->getParent();
1462 if (CmpI->getParent() != BB)
1463 return false;
1464
1465 using instr_iterator = MachineBasicBlock::instr_iterator;
1466
1467 // Check if things are in order to begin with.
1468 for (instr_iterator I(BumpI), E = BB->instr_end(); I != E; ++I)
1469 if (&*I == CmpI)
1470 return true;
1471
1472 // Out of order.
1473 Register PredR = CmpI->getOperand(i: 0).getReg();
1474 bool FoundBump = false;
1475 instr_iterator CmpIt = CmpI->getIterator(), NextIt = std::next(x: CmpIt);
1476 for (instr_iterator I = NextIt, E = BB->instr_end(); I != E; ++I) {
1477 MachineInstr *In = &*I;
1478 for (unsigned i = 0, n = In->getNumOperands(); i < n; ++i) {
1479 MachineOperand &MO = In->getOperand(i);
1480 if (MO.isReg() && MO.isUse()) {
1481 if (MO.getReg() == PredR) // Found an intervening use of PredR.
1482 return false;
1483 }
1484 }
1485
1486 if (In == BumpI) {
1487 BB->splice(Where: ++BumpI->getIterator(), Other: BB, From: CmpI->getIterator());
1488 FoundBump = true;
1489 break;
1490 }
1491 }
1492 assert (FoundBump && "Cannot determine instruction order");
1493 return FoundBump;
1494}
1495
1496/// This function is required to break recursion. Visiting phis in a loop may
1497/// result in recursion during compilation. We break the recursion by making
1498/// sure that we visit a MachineOperand and its definition in a
1499/// MachineInstruction only once. If we attempt to visit more than once, then
1500/// there is recursion, and will return false.
1501bool HexagonHardwareLoops::isLoopFeeder(MachineLoop *L, MachineBasicBlock *A,
1502 MachineInstr *MI,
1503 const MachineOperand *MO,
1504 LoopFeederMap &LoopFeederPhi) const {
1505 if (LoopFeederPhi.find(x: MO->getReg()) == LoopFeederPhi.end()) {
1506 LLVM_DEBUG(dbgs() << "\nhw_loop head, "
1507 << printMBBReference(**L->block_begin()));
1508 // Ignore all BBs that form Loop.
1509 if (llvm::is_contained(Range: L->getBlocks(), Element: A))
1510 return false;
1511 MachineInstr *Def = MRI->getVRegDef(Reg: MO->getReg());
1512 LoopFeederPhi.insert(x: std::make_pair(x: MO->getReg(), y&: Def));
1513 return true;
1514 } else
1515 // Already visited node.
1516 return false;
1517}
1518
1519/// Return true if a Phi may generate a value that can underflow.
1520/// This function calls loopCountMayWrapOrUnderFlow for each Phi operand.
1521bool HexagonHardwareLoops::phiMayWrapOrUnderflow(
1522 MachineInstr *Phi, const MachineOperand *EndVal, MachineBasicBlock *MBB,
1523 MachineLoop *L, LoopFeederMap &LoopFeederPhi) const {
1524 assert(Phi->isPHI() && "Expecting a Phi.");
1525 // Walk through each Phi, and its used operands. Make sure that
1526 // if there is recursion in Phi, we won't generate hardware loops.
1527 for (int i = 1, n = Phi->getNumOperands(); i < n; i += 2)
1528 if (isLoopFeeder(L, A: MBB, MI: Phi, MO: &(Phi->getOperand(i)), LoopFeederPhi))
1529 if (loopCountMayWrapOrUnderFlow(InitVal: &(Phi->getOperand(i)), EndVal,
1530 MBB: Phi->getParent(), L, LoopFeederPhi))
1531 return true;
1532 return false;
1533}
1534
1535/// Return true if the induction variable can underflow in the first iteration.
1536/// An example, is an initial unsigned value that is 0 and is decrement in the
1537/// first itertion of a do-while loop. In this case, we cannot generate a
1538/// hardware loop because the endloop instruction does not decrement the loop
1539/// counter if it is <= 1. We only need to perform this analysis if the
1540/// initial value is a register.
1541///
1542/// This function assumes the initial value may underflow unless proven
1543/// otherwise. If the type is signed, then we don't care because signed
1544/// underflow is undefined. We attempt to prove the initial value is not
1545/// zero by performing a crude analysis of the loop counter. This function
1546/// checks if the initial value is used in any comparison prior to the loop
1547/// and, if so, assumes the comparison is a range check. This is inexact,
1548/// but will catch the simple cases.
1549bool HexagonHardwareLoops::loopCountMayWrapOrUnderFlow(
1550 const MachineOperand *InitVal, const MachineOperand *EndVal,
1551 MachineBasicBlock *MBB, MachineLoop *L,
1552 LoopFeederMap &LoopFeederPhi) const {
1553 // Only check register values since they are unknown.
1554 if (!InitVal->isReg())
1555 return false;
1556
1557 if (!EndVal->isImm())
1558 return false;
1559
1560 // A register value that is assigned an immediate is a known value, and it
1561 // won't underflow in the first iteration.
1562 int64_t Imm;
1563 if (checkForImmediate(MO: *InitVal, Val&: Imm))
1564 return (EndVal->getImm() == Imm);
1565
1566 Register Reg = InitVal->getReg();
1567
1568 // We don't know the value of a physical register.
1569 if (!Reg.isVirtual())
1570 return true;
1571
1572 MachineInstr *Def = MRI->getVRegDef(Reg);
1573 if (!Def)
1574 return true;
1575
1576 // If the initial value is a Phi or copy and the operands may not underflow,
1577 // then the definition cannot be underflow either.
1578 if (Def->isPHI() && !phiMayWrapOrUnderflow(Phi: Def, EndVal, MBB: Def->getParent(),
1579 L, LoopFeederPhi))
1580 return false;
1581 if (Def->isCopy() && !loopCountMayWrapOrUnderFlow(InitVal: &(Def->getOperand(i: 1)),
1582 EndVal, MBB: Def->getParent(),
1583 L, LoopFeederPhi))
1584 return false;
1585
1586 // Iterate over the uses of the initial value. If the initial value is used
1587 // in a compare, then we assume this is a range check that ensures the loop
1588 // doesn't underflow. This is not an exact test and should be improved.
1589 for (MachineRegisterInfo::use_instr_nodbg_iterator I = MRI->use_instr_nodbg_begin(RegNo: Reg),
1590 E = MRI->use_instr_nodbg_end(); I != E; ++I) {
1591 MachineInstr *MI = &*I;
1592 Register CmpReg1, CmpReg2;
1593 int64_t CmpMask = 0, CmpValue = 0;
1594
1595 if (!TII->analyzeCompare(MI: *MI, SrcReg&: CmpReg1, SrcReg2&: CmpReg2, Mask&: CmpMask, Value&: CmpValue))
1596 continue;
1597
1598 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
1599 SmallVector<MachineOperand, 2> Cond;
1600 if (TII->analyzeBranch(MBB&: *MI->getParent(), TBB, FBB, Cond, AllowModify: false))
1601 continue;
1602
1603 Comparison::Kind Cmp =
1604 getComparisonKind(CondOpc: MI->getOpcode(), InitialValue: nullptr, EndValue: nullptr, IVBump: 0);
1605 if (Cmp == 0)
1606 continue;
1607 if (TII->predOpcodeHasNot(Cond) ^ (TBB != MBB))
1608 Cmp = Comparison::getNegatedComparison(Cmp);
1609 if (CmpReg2 != 0 && CmpReg2 == Reg)
1610 Cmp = Comparison::getSwappedComparison(Cmp);
1611
1612 // Signed underflow is undefined.
1613 if (Comparison::isSigned(Cmp))
1614 return false;
1615
1616 // Check if there is a comparison of the initial value. If the initial value
1617 // is greater than or not equal to another value, then assume this is a
1618 // range check.
1619 if ((Cmp & Comparison::G) || Cmp == Comparison::NE)
1620 return false;
1621 }
1622
1623 // OK - this is a hack that needs to be improved. We really need to analyze
1624 // the instructions performed on the initial value. This works on the simplest
1625 // cases only.
1626 if (!Def->isCopy() && !Def->isPHI())
1627 return false;
1628
1629 return true;
1630}
1631
1632bool HexagonHardwareLoops::checkForImmediate(const MachineOperand &MO,
1633 int64_t &Val) const {
1634 if (MO.isImm()) {
1635 Val = MO.getImm();
1636 return true;
1637 }
1638 if (!MO.isReg())
1639 return false;
1640
1641 // MO is a register. Check whether it is defined as an immediate value,
1642 // and if so, get the value of it in TV. That value will then need to be
1643 // processed to handle potential subregisters in MO.
1644 int64_t TV;
1645
1646 Register R = MO.getReg();
1647 if (!R.isVirtual())
1648 return false;
1649 MachineInstr *DI = MRI->getVRegDef(Reg: R);
1650 unsigned DOpc = DI->getOpcode();
1651 switch (DOpc) {
1652 case TargetOpcode::COPY:
1653 case Hexagon::A2_tfrsi:
1654 case Hexagon::A2_tfrpi:
1655 case Hexagon::CONST32:
1656 case Hexagon::CONST64:
1657 // Call recursively to avoid an extra check whether operand(1) is
1658 // indeed an immediate (it could be a global address, for example),
1659 // plus we can handle COPY at the same time.
1660 if (!checkForImmediate(MO: DI->getOperand(i: 1), Val&: TV))
1661 return false;
1662 break;
1663 case Hexagon::A2_combineii:
1664 case Hexagon::A4_combineir:
1665 case Hexagon::A4_combineii:
1666 case Hexagon::A4_combineri:
1667 case Hexagon::A2_combinew: {
1668 const MachineOperand &S1 = DI->getOperand(i: 1);
1669 const MachineOperand &S2 = DI->getOperand(i: 2);
1670 int64_t V1, V2;
1671 if (!checkForImmediate(MO: S1, Val&: V1) || !checkForImmediate(MO: S2, Val&: V2))
1672 return false;
1673 TV = V2 | (static_cast<uint64_t>(V1) << 32);
1674 break;
1675 }
1676 case TargetOpcode::REG_SEQUENCE: {
1677 const MachineOperand &S1 = DI->getOperand(i: 1);
1678 const MachineOperand &S3 = DI->getOperand(i: 3);
1679 int64_t V1, V3;
1680 if (!checkForImmediate(MO: S1, Val&: V1) || !checkForImmediate(MO: S3, Val&: V3))
1681 return false;
1682 unsigned Sub2 = DI->getOperand(i: 2).getImm();
1683 unsigned Sub4 = DI->getOperand(i: 4).getImm();
1684 if (Sub2 == Hexagon::isub_lo && Sub4 == Hexagon::isub_hi)
1685 TV = V1 | (V3 << 32);
1686 else if (Sub2 == Hexagon::isub_hi && Sub4 == Hexagon::isub_lo)
1687 TV = V3 | (V1 << 32);
1688 else
1689 llvm_unreachable("Unexpected form of REG_SEQUENCE");
1690 break;
1691 }
1692
1693 default:
1694 return false;
1695 }
1696
1697 // By now, we should have successfully obtained the immediate value defining
1698 // the register referenced in MO. Handle a potential use of a subregister.
1699 switch (MO.getSubReg()) {
1700 case Hexagon::isub_lo:
1701 Val = TV & 0xFFFFFFFFULL;
1702 break;
1703 case Hexagon::isub_hi:
1704 Val = (TV >> 32) & 0xFFFFFFFFULL;
1705 break;
1706 default:
1707 Val = TV;
1708 break;
1709 }
1710 return true;
1711}
1712
1713void HexagonHardwareLoops::setImmediate(MachineOperand &MO, int64_t Val) {
1714 if (MO.isImm()) {
1715 MO.setImm(Val);
1716 return;
1717 }
1718
1719 assert(MO.isReg());
1720 Register R = MO.getReg();
1721 MachineInstr *DI = MRI->getVRegDef(Reg: R);
1722
1723 const TargetRegisterClass *RC = MRI->getRegClass(Reg: R);
1724 Register NewR = MRI->createVirtualRegister(RegClass: RC);
1725 MachineBasicBlock &B = *DI->getParent();
1726 DebugLoc DL = DI->getDebugLoc();
1727 BuildMI(BB&: B, I: DI, MIMD: DL, MCID: TII->get(Opcode: DI->getOpcode()), DestReg: NewR).addImm(Val);
1728 MO.setReg(NewR);
1729}
1730
1731bool HexagonHardwareLoops::fixupInductionVariable(MachineLoop *L) {
1732 MachineBasicBlock *Header = L->getHeader();
1733 MachineBasicBlock *Latch = L->getLoopLatch();
1734 MachineBasicBlock *ExitingBlock = L->findLoopControlBlock();
1735
1736 if (!(Header && Latch && ExitingBlock))
1737 return false;
1738
1739 // These data structures follow the same concept as the corresponding
1740 // ones in findInductionRegister (where some comments are).
1741 using RegisterBump = std::pair<Register, int64_t>;
1742 using RegisterInduction = std::pair<Register, RegisterBump>;
1743 using RegisterInductionSet = std::set<RegisterInduction>;
1744
1745 // Register candidates for induction variables, with their associated bumps.
1746 RegisterInductionSet IndRegs;
1747
1748 // Look for induction patterns:
1749 // %1 = PHI ..., [ latch, %2 ]
1750 // %2 = ADD %1, imm
1751 using instr_iterator = MachineBasicBlock::instr_iterator;
1752
1753 for (instr_iterator I = Header->instr_begin(), E = Header->instr_end();
1754 I != E && I->isPHI(); ++I) {
1755 MachineInstr *Phi = &*I;
1756
1757 // Have a PHI instruction.
1758 for (unsigned i = 1, n = Phi->getNumOperands(); i < n; i += 2) {
1759 if (Phi->getOperand(i: i+1).getMBB() != Latch)
1760 continue;
1761
1762 Register PhiReg = Phi->getOperand(i).getReg();
1763 MachineInstr *DI = MRI->getVRegDef(Reg: PhiReg);
1764
1765 if (DI->getDesc().isAdd()) {
1766 // If the register operand to the add/sub is the PHI we are looking
1767 // at, this meets the induction pattern.
1768 Register IndReg = DI->getOperand(i: 1).getReg();
1769 MachineOperand &Opnd2 = DI->getOperand(i: 2);
1770 int64_t V;
1771 if (MRI->getVRegDef(Reg: IndReg) == Phi && checkForImmediate(MO: Opnd2, Val&: V)) {
1772 Register UpdReg = DI->getOperand(i: 0).getReg();
1773 IndRegs.insert(x: std::make_pair(x&: UpdReg, y: std::make_pair(x&: IndReg, y&: V)));
1774 }
1775 } else {
1776 Register IndReg;
1777 int64_t V;
1778 if (tryExtractPostIncInduction(DI, Phi, PhiOpReg: PhiReg, IndReg, IVBump&: V))
1779 IndRegs.insert(x: std::make_pair(x&: PhiReg, y: std::make_pair(x&: IndReg, y&: V)));
1780 }
1781 } // for (i)
1782 } // for (instr)
1783
1784 if (IndRegs.empty())
1785 return false;
1786
1787 MachineBasicBlock *TB = nullptr, *FB = nullptr;
1788 SmallVector<MachineOperand,2> Cond;
1789 // analyzeBranch returns true if it fails to analyze branch.
1790 bool NotAnalyzed = TII->analyzeBranch(MBB&: *ExitingBlock, TBB&: TB, FBB&: FB, Cond, AllowModify: false);
1791 if (NotAnalyzed || Cond.empty())
1792 return false;
1793
1794 if (ExitingBlock != Latch && (TB == Latch || FB == Latch)) {
1795 MachineBasicBlock *LTB = nullptr, *LFB = nullptr;
1796 SmallVector<MachineOperand,2> LCond;
1797 bool NotAnalyzed = TII->analyzeBranch(MBB&: *Latch, TBB&: LTB, FBB&: LFB, Cond&: LCond, AllowModify: false);
1798 if (NotAnalyzed)
1799 return false;
1800
1801 // Since latch is not the exiting block, the latch branch should be an
1802 // unconditional branch to the loop header.
1803 if (TB == Latch)
1804 TB = (LTB == Header) ? LTB : LFB;
1805 else
1806 FB = (LTB == Header) ? LTB : LFB;
1807 }
1808 if (TB != Header) {
1809 if (FB != Header) {
1810 // The latch/exit block does not go back to the header.
1811 return false;
1812 }
1813 // FB is the header (i.e., uncond. jump to branch header)
1814 // In this case, the LoopBody -> TB should not be a back edge otherwise
1815 // it could result in an infinite loop after conversion to hw_loop.
1816 // This case can happen when the Latch has two jumps like this:
1817 // Jmp_c OuterLoopHeader <-- TB
1818 // Jmp InnerLoopHeader <-- FB
1819 if (MDT->dominates(A: TB, B: FB))
1820 return false;
1821 }
1822
1823 // Expecting a predicate register as a condition. It won't be a hardware
1824 // predicate register at this point yet, just a vreg.
1825 // HexagonInstrInfo::analyzeBranch for negated branches inserts imm(0)
1826 // into Cond, followed by the predicate register. For non-negated branches
1827 // it's just the register.
1828 unsigned CSz = Cond.size();
1829 if (CSz != 1 && CSz != 2)
1830 return false;
1831
1832 if (!Cond[CSz-1].isReg())
1833 return false;
1834
1835 Register P = Cond[CSz - 1].getReg();
1836 MachineInstr *PredDef = MRI->getVRegDef(Reg: P);
1837
1838 if (!PredDef->isCompare())
1839 return false;
1840
1841 SmallSet<Register,2> CmpRegs;
1842 MachineOperand *CmpImmOp = nullptr;
1843
1844 // Go over all operands to the compare and look for immediate and register
1845 // operands. Assume that if the compare has a single register use and a
1846 // single immediate operand, then the register is being compared with the
1847 // immediate value.
1848 for (MachineOperand &MO : PredDef->operands()) {
1849 if (MO.isReg()) {
1850 // Skip all implicit references. In one case there was:
1851 // %140 = FCMPUGT32_rr %138, %139, implicit %usr
1852 if (MO.isImplicit())
1853 continue;
1854 if (MO.isUse()) {
1855 if (!isImmediate(MO)) {
1856 CmpRegs.insert(V: MO.getReg());
1857 continue;
1858 }
1859 // Consider the register to be the "immediate" operand.
1860 if (CmpImmOp)
1861 return false;
1862 CmpImmOp = &MO;
1863 }
1864 } else if (MO.isImm()) {
1865 if (CmpImmOp) // A second immediate argument? Confusing. Bail out.
1866 return false;
1867 CmpImmOp = &MO;
1868 }
1869 }
1870
1871 if (CmpRegs.empty())
1872 return false;
1873
1874 // Check if the compared register follows the order we want. Fix if needed.
1875 for (RegisterInductionSet::iterator I = IndRegs.begin(), E = IndRegs.end();
1876 I != E; ++I) {
1877 // This is a success. If the register used in the comparison is one that
1878 // we have identified as a bumped (updated) induction register, there is
1879 // nothing to do.
1880 if (CmpRegs.count(V: I->first))
1881 return true;
1882
1883 // Otherwise, if the register being compared comes out of a PHI node,
1884 // and has been recognized as following the induction pattern, and is
1885 // compared against an immediate, we can fix it.
1886 const RegisterBump &RB = I->second;
1887 if (CmpRegs.count(V: RB.first)) {
1888 if (!CmpImmOp) {
1889 // If both operands to the compare instruction are registers, see if
1890 // it can be changed to use induction register as one of the operands.
1891 MachineInstr *IndI = nullptr;
1892 MachineInstr *nonIndI = nullptr;
1893 MachineOperand *IndMO = nullptr;
1894 MachineOperand *nonIndMO = nullptr;
1895
1896 for (unsigned i = 1, n = PredDef->getNumOperands(); i < n; ++i) {
1897 MachineOperand &MO = PredDef->getOperand(i);
1898 if (MO.isReg() && MO.getReg() == RB.first) {
1899 LLVM_DEBUG(dbgs() << "\n DefMI(" << i
1900 << ") = " << *(MRI->getVRegDef(I->first)));
1901 if (IndI)
1902 return false;
1903
1904 IndI = MRI->getVRegDef(Reg: I->first);
1905 IndMO = &MO;
1906 } else if (MO.isReg()) {
1907 LLVM_DEBUG(dbgs() << "\n DefMI(" << i
1908 << ") = " << *(MRI->getVRegDef(MO.getReg())));
1909 if (nonIndI)
1910 return false;
1911
1912 nonIndI = MRI->getVRegDef(Reg: MO.getReg());
1913 nonIndMO = &MO;
1914 }
1915 }
1916 if (IndI && nonIndI &&
1917 nonIndI->getOpcode() == Hexagon::A2_addi &&
1918 nonIndI->getOperand(i: 2).isImm() &&
1919 nonIndI->getOperand(i: 2).getImm() == - RB.second) {
1920 bool Order = orderBumpCompare(BumpI: IndI, CmpI: PredDef);
1921 if (Order) {
1922 IndMO->setReg(I->first);
1923 nonIndMO->setReg(nonIndI->getOperand(i: 1).getReg());
1924 return true;
1925 }
1926 }
1927 return false;
1928 }
1929
1930 // It is not valid to do this transformation on an unsigned comparison
1931 // because it may underflow.
1932 Comparison::Kind Cmp =
1933 getComparisonKind(CondOpc: PredDef->getOpcode(), InitialValue: nullptr, EndValue: nullptr, IVBump: 0);
1934 if (!Cmp || Comparison::isUnsigned(Cmp))
1935 return false;
1936
1937 // If the register is being compared against an immediate, try changing
1938 // the compare instruction to use induction register and adjust the
1939 // immediate operand.
1940 int64_t CmpImm = getImmediate(MO: *CmpImmOp);
1941 int64_t V = RB.second;
1942 // Handle Overflow (64-bit).
1943 if (((V > 0) && (CmpImm > INT64_MAX - V)) ||
1944 ((V < 0) && (CmpImm < INT64_MIN - V)))
1945 return false;
1946 CmpImm += V;
1947 // Most comparisons of register against an immediate value allow
1948 // the immediate to be constant-extended. There are some exceptions
1949 // though. Make sure the new combination will work.
1950 if (CmpImmOp->isImm() && !TII->isExtendable(MI: *PredDef) &&
1951 !TII->isValidOffset(Opcode: PredDef->getOpcode(), Offset: CmpImm, Extend: false))
1952 return false;
1953
1954 // Make sure that the compare happens after the bump. Otherwise,
1955 // after the fixup, the compare would use a yet-undefined register.
1956 MachineInstr *BumpI = MRI->getVRegDef(Reg: I->first);
1957 bool Order = orderBumpCompare(BumpI, CmpI: PredDef);
1958 if (!Order)
1959 return false;
1960
1961 // Finally, fix the compare instruction.
1962 setImmediate(MO&: *CmpImmOp, Val: CmpImm);
1963 for (MachineOperand &MO : PredDef->operands()) {
1964 if (MO.isReg() && MO.getReg() == RB.first) {
1965 MO.setReg(I->first);
1966 return true;
1967 }
1968 }
1969 }
1970 }
1971
1972 return false;
1973}
1974
1975/// createPreheaderForLoop - Create a preheader for a given loop.
1976MachineBasicBlock *HexagonHardwareLoops::createPreheaderForLoop(
1977 MachineLoop *L) {
1978 if (MachineBasicBlock *TmpPH = MLI->findLoopPreheader(L, SpeculativePreheader: SpecPreheader))
1979 return TmpPH;
1980 if (!HWCreatePreheader)
1981 return nullptr;
1982
1983 MachineBasicBlock *Header = L->getHeader();
1984 MachineBasicBlock *Latch = L->getLoopLatch();
1985 MachineBasicBlock *ExitingBlock = L->findLoopControlBlock();
1986 MachineFunction *MF = Header->getParent();
1987 DebugLoc DL;
1988
1989#ifndef NDEBUG
1990 if ((!PHFn.empty()) && (PHFn != MF->getName()))
1991 return nullptr;
1992#endif
1993
1994 if (!Latch || !ExitingBlock || Header->hasAddressTaken())
1995 return nullptr;
1996
1997 using instr_iterator = MachineBasicBlock::instr_iterator;
1998
1999 // Verify that all existing predecessors have analyzable branches
2000 // (or no branches at all).
2001 using MBBVector = std::vector<MachineBasicBlock *>;
2002
2003 MBBVector Preds(Header->pred_begin(), Header->pred_end());
2004 SmallVector<MachineOperand,2> Tmp1;
2005 MachineBasicBlock *TB = nullptr, *FB = nullptr;
2006
2007 if (TII->analyzeBranch(MBB&: *ExitingBlock, TBB&: TB, FBB&: FB, Cond&: Tmp1, AllowModify: false))
2008 return nullptr;
2009
2010 for (MachineBasicBlock *PB : Preds) {
2011 bool NotAnalyzed = TII->analyzeBranch(MBB&: *PB, TBB&: TB, FBB&: FB, Cond&: Tmp1, AllowModify: false);
2012 if (NotAnalyzed)
2013 return nullptr;
2014 }
2015
2016 MachineBasicBlock *NewPH = MF->CreateMachineBasicBlock();
2017 MF->insert(MBBI: Header->getIterator(), MBB: NewPH);
2018
2019 if (Header->pred_size() > 2) {
2020 // Ensure that the header has only two predecessors: the preheader and
2021 // the loop latch. Any additional predecessors of the header should
2022 // join at the newly created preheader. Inspect all PHI nodes from the
2023 // header and create appropriate corresponding PHI nodes in the preheader.
2024
2025 for (instr_iterator I = Header->instr_begin(), E = Header->instr_end();
2026 I != E && I->isPHI(); ++I) {
2027 MachineInstr *PN = &*I;
2028
2029 const MCInstrDesc &PD = TII->get(Opcode: TargetOpcode::PHI);
2030 MachineInstr *NewPN = MF->CreateMachineInstr(MCID: PD, DL);
2031 NewPH->insert(I: NewPH->end(), MI: NewPN);
2032
2033 Register PR = PN->getOperand(i: 0).getReg();
2034 const TargetRegisterClass *RC = MRI->getRegClass(Reg: PR);
2035 Register NewPR = MRI->createVirtualRegister(RegClass: RC);
2036 NewPN->addOperand(Op: MachineOperand::CreateReg(Reg: NewPR, isDef: true));
2037
2038 // Copy all non-latch operands of a header's PHI node to the newly
2039 // created PHI node in the preheader.
2040 for (unsigned i = 1, n = PN->getNumOperands(); i < n; i += 2) {
2041 Register PredR = PN->getOperand(i).getReg();
2042 unsigned PredRSub = PN->getOperand(i).getSubReg();
2043 MachineBasicBlock *PredB = PN->getOperand(i: i+1).getMBB();
2044 if (PredB == Latch)
2045 continue;
2046
2047 MachineOperand MO = MachineOperand::CreateReg(Reg: PredR, isDef: false);
2048 MO.setSubReg(PredRSub);
2049 NewPN->addOperand(Op: MO);
2050 NewPN->addOperand(Op: MachineOperand::CreateMBB(MBB: PredB));
2051 }
2052
2053 // Remove copied operands from the old PHI node and add the value
2054 // coming from the preheader's PHI.
2055 for (int i = PN->getNumOperands()-2; i > 0; i -= 2) {
2056 MachineBasicBlock *PredB = PN->getOperand(i: i+1).getMBB();
2057 if (PredB != Latch) {
2058 PN->removeOperand(OpNo: i+1);
2059 PN->removeOperand(OpNo: i);
2060 }
2061 }
2062 PN->addOperand(Op: MachineOperand::CreateReg(Reg: NewPR, isDef: false));
2063 PN->addOperand(Op: MachineOperand::CreateMBB(MBB: NewPH));
2064 }
2065 } else {
2066 assert(Header->pred_size() == 2);
2067
2068 // The header has only two predecessors, but the non-latch predecessor
2069 // is not a preheader (e.g. it has other successors, etc.)
2070 // In such a case we don't need any extra PHI nodes in the new preheader,
2071 // all we need is to adjust existing PHIs in the header to now refer to
2072 // the new preheader.
2073 for (instr_iterator I = Header->instr_begin(), E = Header->instr_end();
2074 I != E && I->isPHI(); ++I) {
2075 MachineInstr *PN = &*I;
2076 for (unsigned i = 1, n = PN->getNumOperands(); i < n; i += 2) {
2077 MachineOperand &MO = PN->getOperand(i: i+1);
2078 if (MO.getMBB() != Latch)
2079 MO.setMBB(NewPH);
2080 }
2081 }
2082 }
2083
2084 // "Reroute" the CFG edges to link in the new preheader.
2085 // If any of the predecessors falls through to the header, insert a branch
2086 // to the new preheader in that place.
2087 SmallVector<MachineOperand,1> Tmp2;
2088 SmallVector<MachineOperand,1> EmptyCond;
2089
2090 TB = FB = nullptr;
2091
2092 for (MachineBasicBlock *PB : Preds) {
2093 if (PB != Latch) {
2094 Tmp2.clear();
2095 bool NotAnalyzed = TII->analyzeBranch(MBB&: *PB, TBB&: TB, FBB&: FB, Cond&: Tmp2, AllowModify: false);
2096 (void)NotAnalyzed; // suppress compiler warning
2097 assert (!NotAnalyzed && "Should be analyzable!");
2098 if (TB != Header && (Tmp2.empty() || FB != Header))
2099 TII->insertBranch(MBB&: *PB, TBB: NewPH, FBB: nullptr, Cond: EmptyCond, DL);
2100 PB->ReplaceUsesOfBlockWith(Old: Header, New: NewPH);
2101 }
2102 }
2103
2104 // It can happen that the latch block will fall through into the header.
2105 // Insert an unconditional branch to the header.
2106 TB = FB = nullptr;
2107 bool LatchNotAnalyzed = TII->analyzeBranch(MBB&: *Latch, TBB&: TB, FBB&: FB, Cond&: Tmp2, AllowModify: false);
2108 (void)LatchNotAnalyzed; // suppress compiler warning
2109 assert (!LatchNotAnalyzed && "Should be analyzable!");
2110 if (!TB && !FB)
2111 TII->insertBranch(MBB&: *Latch, TBB: Header, FBB: nullptr, Cond: EmptyCond, DL);
2112
2113 // Finally, the branch from the preheader to the header.
2114 TII->insertBranch(MBB&: *NewPH, TBB: Header, FBB: nullptr, Cond: EmptyCond, DL);
2115 NewPH->addSuccessor(Succ: Header);
2116
2117 MachineLoop *ParentLoop = L->getParentLoop();
2118 if (ParentLoop)
2119 ParentLoop->addBasicBlockToLoop(NewBB: NewPH, LI&: *MLI);
2120
2121 // Update the dominator information with the new preheader.
2122 if (MDT) {
2123 if (MachineDomTreeNode *HN = MDT->getNode(BB: Header)) {
2124 if (MachineDomTreeNode *DHN = HN->getIDom()) {
2125 MDT->addNewBlock(BB: NewPH, DomBB: DHN->getBlock());
2126 MDT->changeImmediateDominator(BB: Header, NewBB: NewPH);
2127 }
2128 }
2129 }
2130
2131 return NewPH;
2132}
2133