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 const MCInstrDesc &DistCheckD = TII->get(Opcode: Hexagon::C2_cmpgti);
1053 BuildMI(BB&: *PH, I: InsertPos, MIMD: DL, MCID: DistCheckD, DestReg: DistCheckR)
1054 .addReg(RegNo: DistR, Flags: {}, SubReg: DistSR)
1055 .addImm(Val: (CmpLess) ? 0 : -1);
1056
1057 // Generate:
1058 // MUXR = MUX DistCheck, CountR, 1 --> CmpLess
1059 // MUXR = MUX DistCheck, 1, CountR --> CmpGreater
1060 MuxR = MRI->createVirtualRegister(RegClass: IntRC);
1061 if (CmpLess) {
1062 const MCInstrDesc &MuxD = TII->get(Opcode: Hexagon::C2_muxir);
1063 BuildMI(BB&: *PH, I: InsertPos, MIMD: DL, MCID: MuxD, DestReg: MuxR)
1064 .addReg(RegNo: DistCheckR)
1065 .addReg(RegNo: CountR, Flags: {}, SubReg: CountSR)
1066 .addImm(Val: 1);
1067 } else {
1068 const MCInstrDesc &MuxD = TII->get(Opcode: Hexagon::C2_muxri);
1069 BuildMI(BB&: *PH, I: InsertPos, MIMD: DL, MCID: MuxD, DestReg: MuxR)
1070 .addReg(RegNo: DistCheckR)
1071 .addImm(Val: 1)
1072 .addReg(RegNo: CountR, Flags: {}, SubReg: CountSR);
1073 }
1074 MuxSR = 0;
1075 }
1076
1077 return new CountValue(CountValue::CV_Register, MuxR, MuxSR);
1078}
1079
1080/// Return true if the operation is invalid within hardware loop.
1081bool HexagonHardwareLoops::isInvalidLoopOperation(const MachineInstr *MI,
1082 bool IsInnerHWLoop) const {
1083 // Call is not allowed because the callee may use a hardware loop except for
1084 // the case when the call never returns.
1085 if (MI->getDesc().isCall())
1086 return !TII->doesNotReturn(CallMI: *MI);
1087
1088 // Check if the instruction defines a hardware loop register.
1089 using namespace Hexagon;
1090
1091 static const Register Regs01[] = { LC0, SA0, LC1, SA1 };
1092 static const Register Regs1[] = { LC1, SA1 };
1093 auto CheckRegs = IsInnerHWLoop ? ArrayRef(Regs01) : ArrayRef(Regs1);
1094 for (Register R : CheckRegs)
1095 if (MI->modifiesRegister(Reg: R, TRI))
1096 return true;
1097
1098 return false;
1099}
1100
1101/// Return true if the loop contains an instruction that inhibits
1102/// the use of the hardware loop instruction.
1103bool HexagonHardwareLoops::containsInvalidInstruction(MachineLoop *L,
1104 bool IsInnerHWLoop) const {
1105 LLVM_DEBUG(dbgs() << "\nhw_loop head, "
1106 << printMBBReference(**L->block_begin()));
1107 for (MachineBasicBlock *MBB : L->getBlocks()) {
1108 for (const MachineInstr &MI : *MBB) {
1109 if (isInvalidLoopOperation(MI: &MI, IsInnerHWLoop)) {
1110 LLVM_DEBUG(dbgs() << "\nCannot convert to hw_loop due to:";
1111 MI.dump(););
1112 return true;
1113 }
1114 }
1115 }
1116 return false;
1117}
1118
1119/// Returns true if the instruction is dead. This was essentially
1120/// copied from DeadMachineInstructionElim::isDead, but with special cases
1121/// for inline asm, physical registers and instructions with side effects
1122/// removed.
1123bool HexagonHardwareLoops::isDead(const MachineInstr *MI,
1124 SmallVectorImpl<MachineInstr *> &DeadPhis) const {
1125 // Examine each operand.
1126 for (const MachineOperand &MO : MI->operands()) {
1127 if (!MO.isReg() || !MO.isDef())
1128 continue;
1129
1130 Register Reg = MO.getReg();
1131 if (MRI->use_nodbg_empty(RegNo: Reg))
1132 continue;
1133
1134 using use_nodbg_iterator = MachineRegisterInfo::use_nodbg_iterator;
1135
1136 // This instruction has users, but if the only user is the phi node for the
1137 // parent block, and the only use of that phi node is this instruction, then
1138 // this instruction is dead: both it (and the phi node) can be removed.
1139 use_nodbg_iterator I = MRI->use_nodbg_begin(RegNo: Reg);
1140 use_nodbg_iterator End = MRI->use_nodbg_end();
1141 if (std::next(x: I) != End || !I->getParent()->isPHI())
1142 return false;
1143
1144 MachineInstr *OnePhi = I->getParent();
1145 for (const MachineOperand &OPO : OnePhi->operands()) {
1146 if (!OPO.isReg() || !OPO.isDef())
1147 continue;
1148
1149 Register OPReg = OPO.getReg();
1150 use_nodbg_iterator nextJ;
1151 for (use_nodbg_iterator J = MRI->use_nodbg_begin(RegNo: OPReg);
1152 J != End; J = nextJ) {
1153 nextJ = std::next(x: J);
1154 MachineOperand &Use = *J;
1155 MachineInstr *UseMI = Use.getParent();
1156
1157 // If the phi node has a user that is not MI, bail.
1158 if (MI != UseMI)
1159 return false;
1160 }
1161 }
1162 DeadPhis.push_back(Elt: OnePhi);
1163 }
1164
1165 // If there are no defs with uses, the instruction is dead.
1166 return true;
1167}
1168
1169void HexagonHardwareLoops::removeIfDead(MachineInstr *MI) {
1170 // This procedure was essentially copied from DeadMachineInstructionElim.
1171
1172 SmallVector<MachineInstr*, 1> DeadPhis;
1173 if (isDead(MI, DeadPhis)) {
1174 LLVM_DEBUG(dbgs() << "HW looping will remove: " << *MI);
1175
1176 // It is possible that some DBG_VALUE instructions refer to this
1177 // instruction. Examine each def operand for such references;
1178 // if found, mark the DBG_VALUE as undef (but don't delete it).
1179 for (const MachineOperand &MO : MI->operands()) {
1180 if (!MO.isReg() || !MO.isDef())
1181 continue;
1182 Register Reg = MO.getReg();
1183 // We use make_early_inc_range here because setReg below invalidates the
1184 // iterator.
1185 for (MachineOperand &MO :
1186 llvm::make_early_inc_range(Range: MRI->use_operands(Reg))) {
1187 MachineInstr *UseMI = MO.getParent();
1188 if (UseMI == MI)
1189 continue;
1190 if (MO.isDebug())
1191 MO.setReg(0U);
1192 }
1193 }
1194
1195 MI->eraseFromParent();
1196 for (unsigned i = 0; i < DeadPhis.size(); ++i)
1197 DeadPhis[i]->eraseFromParent();
1198 }
1199}
1200
1201/// Check if the loop is a candidate for converting to a hardware
1202/// loop. If so, then perform the transformation.
1203///
1204/// This function works on innermost loops first. A loop can be converted
1205/// if it is a counting loop; either a register value or an immediate.
1206///
1207/// The code makes several assumptions about the representation of the loop
1208/// in llvm.
1209bool HexagonHardwareLoops::convertToHardwareLoop(MachineLoop *L,
1210 bool &RecL0used,
1211 bool &RecL1used) {
1212 // This is just to confirm basic correctness.
1213 assert(L->getHeader() && "Loop without a header?");
1214
1215 bool Changed = false;
1216 bool L0Used = false;
1217 bool L1Used = false;
1218
1219 // Process nested loops first.
1220 for (MachineLoop *I : *L) {
1221 Changed |= convertToHardwareLoop(L: I, RecL0used, RecL1used);
1222 L0Used |= RecL0used;
1223 L1Used |= RecL1used;
1224 }
1225
1226 // If a nested loop has been converted, then we can't convert this loop.
1227 if (Changed && L0Used && L1Used)
1228 return Changed;
1229
1230 unsigned LOOP_i;
1231 unsigned LOOP_r;
1232 unsigned ENDLOOP;
1233
1234 // Flag used to track loopN instruction:
1235 // 1 - Hardware loop is being generated for the inner most loop.
1236 // 0 - Hardware loop is being generated for the outer loop.
1237 unsigned IsInnerHWLoop = 1;
1238
1239 if (L0Used) {
1240 LOOP_i = Hexagon::J2_loop1i;
1241 LOOP_r = Hexagon::J2_loop1r;
1242 ENDLOOP = Hexagon::ENDLOOP1;
1243 IsInnerHWLoop = 0;
1244 } else {
1245 LOOP_i = Hexagon::J2_loop0i;
1246 LOOP_r = Hexagon::J2_loop0r;
1247 ENDLOOP = Hexagon::ENDLOOP0;
1248 }
1249
1250#ifndef NDEBUG
1251 // Stop trying after reaching the limit (if any).
1252 int Limit = HWLoopLimit;
1253 if (Limit >= 0) {
1254 if (Counter >= HWLoopLimit)
1255 return false;
1256 Counter++;
1257 }
1258#endif
1259
1260 // Does the loop contain any invalid instructions?
1261 if (containsInvalidInstruction(L, IsInnerHWLoop)) {
1262 MORE->emit(RemarkBuilder: [&]() {
1263 return MachineOptimizationRemarkMissed(DEBUG_TYPE, "InvalidInstruction",
1264 L->getStartLoc(), L->getHeader())
1265 << "loop contains an instruction that prevents hardware loop "
1266 "generation (e.g. a call or hardware loop register definition)";
1267 });
1268 return false;
1269 }
1270
1271 MachineBasicBlock *LastMBB = L->findLoopControlBlock();
1272 // Don't generate hw loop if the loop has more than one exit.
1273 if (!LastMBB) {
1274 MORE->emit(RemarkBuilder: [&]() {
1275 return MachineOptimizationRemarkMissed(DEBUG_TYPE, "MultipleExits",
1276 L->getStartLoc(), L->getHeader())
1277 << "loop has multiple exits and cannot be converted to a "
1278 "hardware loop";
1279 });
1280 return false;
1281 }
1282
1283 MachineBasicBlock::iterator LastI = LastMBB->getFirstTerminator();
1284 if (LastI == LastMBB->end())
1285 return false;
1286
1287 // Is the induction variable bump feeding the latch condition?
1288 if (!fixupInductionVariable(L)) {
1289 MORE->emit(RemarkBuilder: [&]() {
1290 return MachineOptimizationRemarkMissed(DEBUG_TYPE, "InductionVariable",
1291 L->getStartLoc(), L->getHeader())
1292 << "could not identify or fix up the induction variable";
1293 });
1294 return false;
1295 }
1296
1297 // Ensure the loop has a preheader: the loop instruction will be
1298 // placed there.
1299 MachineBasicBlock *Preheader = MLI->findLoopPreheader(L, SpeculativePreheader: SpecPreheader);
1300 if (!Preheader) {
1301 Preheader = createPreheaderForLoop(L);
1302 if (!Preheader)
1303 return false;
1304 }
1305
1306 MachineBasicBlock::iterator InsertPos = Preheader->getFirstTerminator();
1307
1308 SmallVector<MachineInstr*, 2> OldInsts;
1309 // Are we able to determine the trip count for the loop?
1310 CountValue *TripCount = getLoopTripCount(L, OldInsts);
1311 if (!TripCount) {
1312 MORE->emit(RemarkBuilder: [&]() {
1313 return MachineOptimizationRemarkMissed(DEBUG_TYPE, "TripCount",
1314 L->getStartLoc(), L->getHeader())
1315 << "trip count of the loop could not be computed";
1316 });
1317 return false;
1318 }
1319
1320 // Is the trip count available in the preheader?
1321 if (TripCount->isReg()) {
1322 // There will be a use of the register inserted into the preheader,
1323 // so make sure that the register is actually defined at that point.
1324 MachineInstr *TCDef = MRI->getVRegDef(Reg: TripCount->getReg());
1325 MachineBasicBlock *BBDef = TCDef->getParent();
1326 if (!MDT->dominates(A: BBDef, B: Preheader)) {
1327 MORE->emit(RemarkBuilder: [&]() {
1328 return MachineOptimizationRemarkMissed(DEBUG_TYPE,
1329 "TripCountNotDominating",
1330 L->getStartLoc(), L->getHeader())
1331 << "trip count register is not available in the loop preheader";
1332 });
1333 return false;
1334 }
1335 }
1336
1337 // Determine the loop start.
1338 MachineBasicBlock *TopBlock = L->getTopBlock();
1339 MachineBasicBlock *ExitingBlock = L->findLoopControlBlock();
1340 MachineBasicBlock *LoopStart = nullptr;
1341 if (ExitingBlock != L->getLoopLatch()) {
1342 MachineBasicBlock *TB = nullptr, *FB = nullptr;
1343 SmallVector<MachineOperand, 2> Cond;
1344
1345 if (TII->analyzeBranch(MBB&: *ExitingBlock, TBB&: TB, FBB&: FB, Cond, AllowModify: false))
1346 return false;
1347
1348 if (L->contains(BB: TB))
1349 LoopStart = TB;
1350 else if (L->contains(BB: FB))
1351 LoopStart = FB;
1352 else
1353 return false;
1354 }
1355 else
1356 LoopStart = TopBlock;
1357
1358 // Convert the loop to a hardware loop.
1359 LLVM_DEBUG(dbgs() << "Change to hardware loop at "; L->dump());
1360 DebugLoc DL;
1361 if (InsertPos != Preheader->end())
1362 DL = InsertPos->getDebugLoc();
1363
1364 if (TripCount->isReg()) {
1365 // Create a copy of the loop count register.
1366 Register CountReg = MRI->createVirtualRegister(RegClass: &Hexagon::IntRegsRegClass);
1367 BuildMI(BB&: *Preheader, I: InsertPos, MIMD: DL, MCID: TII->get(Opcode: TargetOpcode::COPY), DestReg: CountReg)
1368 .addReg(RegNo: TripCount->getReg(), Flags: {}, SubReg: TripCount->getSubReg());
1369 // Add the Loop instruction to the beginning of the loop.
1370 BuildMI(BB&: *Preheader, I: InsertPos, MIMD: DL, MCID: TII->get(Opcode: LOOP_r)).addMBB(MBB: LoopStart)
1371 .addReg(RegNo: CountReg);
1372 } else {
1373 assert(TripCount->isImm() && "Expecting immediate value for trip count");
1374 // Add the Loop immediate instruction to the beginning of the loop,
1375 // if the immediate fits in the instructions. Otherwise, we need to
1376 // create a new virtual register.
1377 int64_t CountImm = TripCount->getImm();
1378 if (!TII->isValidOffset(Opcode: LOOP_i, Offset: CountImm)) {
1379 Register CountReg = MRI->createVirtualRegister(RegClass: &Hexagon::IntRegsRegClass);
1380 BuildMI(BB&: *Preheader, I: InsertPos, MIMD: DL, MCID: TII->get(Opcode: Hexagon::A2_tfrsi), DestReg: CountReg)
1381 .addImm(Val: CountImm);
1382 BuildMI(BB&: *Preheader, I: InsertPos, MIMD: DL, MCID: TII->get(Opcode: LOOP_r))
1383 .addMBB(MBB: LoopStart).addReg(RegNo: CountReg);
1384 } else
1385 BuildMI(BB&: *Preheader, I: InsertPos, MIMD: DL, MCID: TII->get(Opcode: LOOP_i))
1386 .addMBB(MBB: LoopStart).addImm(Val: CountImm);
1387 }
1388
1389 // Make sure the loop start always has a reference in the CFG.
1390 LoopStart->setMachineBlockAddressTaken();
1391
1392 // Replace the loop branch with an endloop instruction.
1393 DebugLoc LastIDL = LastI->getDebugLoc();
1394 BuildMI(BB&: *LastMBB, I: LastI, MIMD: LastIDL, MCID: TII->get(Opcode: ENDLOOP)).addMBB(MBB: LoopStart);
1395
1396 // The loop ends with either:
1397 // - a conditional branch followed by an unconditional branch, or
1398 // - a conditional branch to the loop start.
1399 if (LastI->getOpcode() == Hexagon::J2_jumpt ||
1400 LastI->getOpcode() == Hexagon::J2_jumpf) {
1401 // Delete one and change/add an uncond. branch to out of the loop.
1402 MachineBasicBlock *BranchTarget = LastI->getOperand(i: 1).getMBB();
1403 LastI = LastMBB->erase(I: LastI);
1404 if (!L->contains(BB: BranchTarget)) {
1405 if (LastI != LastMBB->end())
1406 LastI = LastMBB->erase(I: LastI);
1407 SmallVector<MachineOperand, 0> Cond;
1408 TII->insertBranch(MBB&: *LastMBB, TBB: BranchTarget, FBB: nullptr, Cond, DL: LastIDL);
1409 }
1410 } else {
1411 // Conditional branch to loop start; just delete it.
1412 LastMBB->erase(I: LastI);
1413 }
1414 delete TripCount;
1415
1416 // The induction operation and the comparison may now be
1417 // unneeded. If these are unneeded, then remove them.
1418 for (unsigned i = 0; i < OldInsts.size(); ++i)
1419 removeIfDead(MI: OldInsts[i]);
1420
1421 ++NumHWLoops;
1422
1423 MORE->emit(RemarkBuilder: [&]() {
1424 return MachineOptimizationRemark(DEBUG_TYPE, "HardwareLoop",
1425 L->getStartLoc(), L->getHeader())
1426 << "converted loop to hardware loop";
1427 });
1428
1429 // Set RecL1used and RecL0used only after hardware loop has been
1430 // successfully generated. Doing it earlier can cause wrong loop instruction
1431 // to be used.
1432 if (L0Used) // Loop0 was already used. So, the correct loop must be loop1.
1433 RecL1used = true;
1434 else
1435 RecL0used = true;
1436
1437 return true;
1438}
1439
1440bool HexagonHardwareLoops::orderBumpCompare(MachineInstr *BumpI,
1441 MachineInstr *CmpI) {
1442 assert (BumpI != CmpI && "Bump and compare in the same instruction?");
1443
1444 MachineBasicBlock *BB = BumpI->getParent();
1445 if (CmpI->getParent() != BB)
1446 return false;
1447
1448 using instr_iterator = MachineBasicBlock::instr_iterator;
1449
1450 // Check if things are in order to begin with.
1451 for (instr_iterator I(BumpI), E = BB->instr_end(); I != E; ++I)
1452 if (&*I == CmpI)
1453 return true;
1454
1455 // Out of order.
1456 Register PredR = CmpI->getOperand(i: 0).getReg();
1457 bool FoundBump = false;
1458 instr_iterator CmpIt = CmpI->getIterator(), NextIt = std::next(x: CmpIt);
1459 for (instr_iterator I = NextIt, E = BB->instr_end(); I != E; ++I) {
1460 MachineInstr *In = &*I;
1461 for (unsigned i = 0, n = In->getNumOperands(); i < n; ++i) {
1462 MachineOperand &MO = In->getOperand(i);
1463 if (MO.isReg() && MO.isUse()) {
1464 if (MO.getReg() == PredR) // Found an intervening use of PredR.
1465 return false;
1466 }
1467 }
1468
1469 if (In == BumpI) {
1470 BB->splice(Where: ++BumpI->getIterator(), Other: BB, From: CmpI->getIterator());
1471 FoundBump = true;
1472 break;
1473 }
1474 }
1475 assert (FoundBump && "Cannot determine instruction order");
1476 return FoundBump;
1477}
1478
1479/// This function is required to break recursion. Visiting phis in a loop may
1480/// result in recursion during compilation. We break the recursion by making
1481/// sure that we visit a MachineOperand and its definition in a
1482/// MachineInstruction only once. If we attempt to visit more than once, then
1483/// there is recursion, and will return false.
1484bool HexagonHardwareLoops::isLoopFeeder(MachineLoop *L, MachineBasicBlock *A,
1485 MachineInstr *MI,
1486 const MachineOperand *MO,
1487 LoopFeederMap &LoopFeederPhi) const {
1488 if (LoopFeederPhi.find(x: MO->getReg()) == LoopFeederPhi.end()) {
1489 LLVM_DEBUG(dbgs() << "\nhw_loop head, "
1490 << printMBBReference(**L->block_begin()));
1491 // Ignore all BBs that form Loop.
1492 if (llvm::is_contained(Range: L->getBlocks(), Element: A))
1493 return false;
1494 MachineInstr *Def = MRI->getVRegDef(Reg: MO->getReg());
1495 LoopFeederPhi.insert(x: std::make_pair(x: MO->getReg(), y&: Def));
1496 return true;
1497 } else
1498 // Already visited node.
1499 return false;
1500}
1501
1502/// Return true if a Phi may generate a value that can underflow.
1503/// This function calls loopCountMayWrapOrUnderFlow for each Phi operand.
1504bool HexagonHardwareLoops::phiMayWrapOrUnderflow(
1505 MachineInstr *Phi, const MachineOperand *EndVal, MachineBasicBlock *MBB,
1506 MachineLoop *L, LoopFeederMap &LoopFeederPhi) const {
1507 assert(Phi->isPHI() && "Expecting a Phi.");
1508 // Walk through each Phi, and its used operands. Make sure that
1509 // if there is recursion in Phi, we won't generate hardware loops.
1510 for (int i = 1, n = Phi->getNumOperands(); i < n; i += 2)
1511 if (isLoopFeeder(L, A: MBB, MI: Phi, MO: &(Phi->getOperand(i)), LoopFeederPhi))
1512 if (loopCountMayWrapOrUnderFlow(InitVal: &(Phi->getOperand(i)), EndVal,
1513 MBB: Phi->getParent(), L, LoopFeederPhi))
1514 return true;
1515 return false;
1516}
1517
1518/// Return true if the induction variable can underflow in the first iteration.
1519/// An example, is an initial unsigned value that is 0 and is decrement in the
1520/// first itertion of a do-while loop. In this case, we cannot generate a
1521/// hardware loop because the endloop instruction does not decrement the loop
1522/// counter if it is <= 1. We only need to perform this analysis if the
1523/// initial value is a register.
1524///
1525/// This function assumes the initial value may underflow unless proven
1526/// otherwise. If the type is signed, then we don't care because signed
1527/// underflow is undefined. We attempt to prove the initial value is not
1528/// zero by performing a crude analysis of the loop counter. This function
1529/// checks if the initial value is used in any comparison prior to the loop
1530/// and, if so, assumes the comparison is a range check. This is inexact,
1531/// but will catch the simple cases.
1532bool HexagonHardwareLoops::loopCountMayWrapOrUnderFlow(
1533 const MachineOperand *InitVal, const MachineOperand *EndVal,
1534 MachineBasicBlock *MBB, MachineLoop *L,
1535 LoopFeederMap &LoopFeederPhi) const {
1536 // Only check register values since they are unknown.
1537 if (!InitVal->isReg())
1538 return false;
1539
1540 if (!EndVal->isImm())
1541 return false;
1542
1543 // A register value that is assigned an immediate is a known value, and it
1544 // won't underflow in the first iteration.
1545 int64_t Imm;
1546 if (checkForImmediate(MO: *InitVal, Val&: Imm))
1547 return (EndVal->getImm() == Imm);
1548
1549 Register Reg = InitVal->getReg();
1550
1551 // We don't know the value of a physical register.
1552 if (!Reg.isVirtual())
1553 return true;
1554
1555 MachineInstr *Def = MRI->getVRegDef(Reg);
1556 if (!Def)
1557 return true;
1558
1559 // If the initial value is a Phi or copy and the operands may not underflow,
1560 // then the definition cannot be underflow either.
1561 if (Def->isPHI() && !phiMayWrapOrUnderflow(Phi: Def, EndVal, MBB: Def->getParent(),
1562 L, LoopFeederPhi))
1563 return false;
1564 if (Def->isCopy() && !loopCountMayWrapOrUnderFlow(InitVal: &(Def->getOperand(i: 1)),
1565 EndVal, MBB: Def->getParent(),
1566 L, LoopFeederPhi))
1567 return false;
1568
1569 // Iterate over the uses of the initial value. If the initial value is used
1570 // in a compare, then we assume this is a range check that ensures the loop
1571 // doesn't underflow. This is not an exact test and should be improved.
1572 for (MachineRegisterInfo::use_instr_nodbg_iterator I = MRI->use_instr_nodbg_begin(RegNo: Reg),
1573 E = MRI->use_instr_nodbg_end(); I != E; ++I) {
1574 MachineInstr *MI = &*I;
1575 Register CmpReg1, CmpReg2;
1576 int64_t CmpMask = 0, CmpValue = 0;
1577
1578 if (!TII->analyzeCompare(MI: *MI, SrcReg&: CmpReg1, SrcReg2&: CmpReg2, Mask&: CmpMask, Value&: CmpValue))
1579 continue;
1580
1581 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
1582 SmallVector<MachineOperand, 2> Cond;
1583 if (TII->analyzeBranch(MBB&: *MI->getParent(), TBB, FBB, Cond, AllowModify: false))
1584 continue;
1585
1586 Comparison::Kind Cmp =
1587 getComparisonKind(CondOpc: MI->getOpcode(), InitialValue: nullptr, EndValue: nullptr, IVBump: 0);
1588 if (Cmp == 0)
1589 continue;
1590 if (TII->predOpcodeHasNot(Cond) ^ (TBB != MBB))
1591 Cmp = Comparison::getNegatedComparison(Cmp);
1592 if (CmpReg2 != 0 && CmpReg2 == Reg)
1593 Cmp = Comparison::getSwappedComparison(Cmp);
1594
1595 // Signed underflow is undefined.
1596 if (Comparison::isSigned(Cmp))
1597 return false;
1598
1599 // Check if there is a comparison of the initial value. If the initial value
1600 // is greater than or not equal to another value, then assume this is a
1601 // range check.
1602 if ((Cmp & Comparison::G) || Cmp == Comparison::NE)
1603 return false;
1604 }
1605
1606 // OK - this is a hack that needs to be improved. We really need to analyze
1607 // the instructions performed on the initial value. This works on the simplest
1608 // cases only.
1609 if (!Def->isCopy() && !Def->isPHI())
1610 return false;
1611
1612 return true;
1613}
1614
1615bool HexagonHardwareLoops::checkForImmediate(const MachineOperand &MO,
1616 int64_t &Val) const {
1617 if (MO.isImm()) {
1618 Val = MO.getImm();
1619 return true;
1620 }
1621 if (!MO.isReg())
1622 return false;
1623
1624 // MO is a register. Check whether it is defined as an immediate value,
1625 // and if so, get the value of it in TV. That value will then need to be
1626 // processed to handle potential subregisters in MO.
1627 int64_t TV;
1628
1629 Register R = MO.getReg();
1630 if (!R.isVirtual())
1631 return false;
1632 MachineInstr *DI = MRI->getVRegDef(Reg: R);
1633 unsigned DOpc = DI->getOpcode();
1634 switch (DOpc) {
1635 case TargetOpcode::COPY:
1636 case Hexagon::A2_tfrsi:
1637 case Hexagon::A2_tfrpi:
1638 case Hexagon::CONST32:
1639 case Hexagon::CONST64:
1640 // Call recursively to avoid an extra check whether operand(1) is
1641 // indeed an immediate (it could be a global address, for example),
1642 // plus we can handle COPY at the same time.
1643 if (!checkForImmediate(MO: DI->getOperand(i: 1), Val&: TV))
1644 return false;
1645 break;
1646 case Hexagon::A2_combineii:
1647 case Hexagon::A4_combineir:
1648 case Hexagon::A4_combineii:
1649 case Hexagon::A4_combineri:
1650 case Hexagon::A2_combinew: {
1651 const MachineOperand &S1 = DI->getOperand(i: 1);
1652 const MachineOperand &S2 = DI->getOperand(i: 2);
1653 int64_t V1, V2;
1654 if (!checkForImmediate(MO: S1, Val&: V1) || !checkForImmediate(MO: S2, Val&: V2))
1655 return false;
1656 TV = V2 | (static_cast<uint64_t>(V1) << 32);
1657 break;
1658 }
1659 case TargetOpcode::REG_SEQUENCE: {
1660 const MachineOperand &S1 = DI->getOperand(i: 1);
1661 const MachineOperand &S3 = DI->getOperand(i: 3);
1662 int64_t V1, V3;
1663 if (!checkForImmediate(MO: S1, Val&: V1) || !checkForImmediate(MO: S3, Val&: V3))
1664 return false;
1665 unsigned Sub2 = DI->getOperand(i: 2).getImm();
1666 unsigned Sub4 = DI->getOperand(i: 4).getImm();
1667 if (Sub2 == Hexagon::isub_lo && Sub4 == Hexagon::isub_hi)
1668 TV = V1 | (V3 << 32);
1669 else if (Sub2 == Hexagon::isub_hi && Sub4 == Hexagon::isub_lo)
1670 TV = V3 | (V1 << 32);
1671 else
1672 llvm_unreachable("Unexpected form of REG_SEQUENCE");
1673 break;
1674 }
1675
1676 default:
1677 return false;
1678 }
1679
1680 // By now, we should have successfully obtained the immediate value defining
1681 // the register referenced in MO. Handle a potential use of a subregister.
1682 switch (MO.getSubReg()) {
1683 case Hexagon::isub_lo:
1684 Val = TV & 0xFFFFFFFFULL;
1685 break;
1686 case Hexagon::isub_hi:
1687 Val = (TV >> 32) & 0xFFFFFFFFULL;
1688 break;
1689 default:
1690 Val = TV;
1691 break;
1692 }
1693 return true;
1694}
1695
1696void HexagonHardwareLoops::setImmediate(MachineOperand &MO, int64_t Val) {
1697 if (MO.isImm()) {
1698 MO.setImm(Val);
1699 return;
1700 }
1701
1702 assert(MO.isReg());
1703 Register R = MO.getReg();
1704 MachineInstr *DI = MRI->getVRegDef(Reg: R);
1705
1706 const TargetRegisterClass *RC = MRI->getRegClass(Reg: R);
1707 Register NewR = MRI->createVirtualRegister(RegClass: RC);
1708 MachineBasicBlock &B = *DI->getParent();
1709 DebugLoc DL = DI->getDebugLoc();
1710 BuildMI(BB&: B, I: DI, MIMD: DL, MCID: TII->get(Opcode: DI->getOpcode()), DestReg: NewR).addImm(Val);
1711 MO.setReg(NewR);
1712}
1713
1714bool HexagonHardwareLoops::fixupInductionVariable(MachineLoop *L) {
1715 MachineBasicBlock *Header = L->getHeader();
1716 MachineBasicBlock *Latch = L->getLoopLatch();
1717 MachineBasicBlock *ExitingBlock = L->findLoopControlBlock();
1718
1719 if (!(Header && Latch && ExitingBlock))
1720 return false;
1721
1722 // These data structures follow the same concept as the corresponding
1723 // ones in findInductionRegister (where some comments are).
1724 using RegisterBump = std::pair<Register, int64_t>;
1725 using RegisterInduction = std::pair<Register, RegisterBump>;
1726 using RegisterInductionSet = std::set<RegisterInduction>;
1727
1728 // Register candidates for induction variables, with their associated bumps.
1729 RegisterInductionSet IndRegs;
1730
1731 // Look for induction patterns:
1732 // %1 = PHI ..., [ latch, %2 ]
1733 // %2 = ADD %1, imm
1734 using instr_iterator = MachineBasicBlock::instr_iterator;
1735
1736 for (instr_iterator I = Header->instr_begin(), E = Header->instr_end();
1737 I != E && I->isPHI(); ++I) {
1738 MachineInstr *Phi = &*I;
1739
1740 // Have a PHI instruction.
1741 for (unsigned i = 1, n = Phi->getNumOperands(); i < n; i += 2) {
1742 if (Phi->getOperand(i: i+1).getMBB() != Latch)
1743 continue;
1744
1745 Register PhiReg = Phi->getOperand(i).getReg();
1746 MachineInstr *DI = MRI->getVRegDef(Reg: PhiReg);
1747
1748 if (DI->getDesc().isAdd()) {
1749 // If the register operand to the add/sub is the PHI we are looking
1750 // at, this meets the induction pattern.
1751 Register IndReg = DI->getOperand(i: 1).getReg();
1752 MachineOperand &Opnd2 = DI->getOperand(i: 2);
1753 int64_t V;
1754 if (MRI->getVRegDef(Reg: IndReg) == Phi && checkForImmediate(MO: Opnd2, Val&: V)) {
1755 Register UpdReg = DI->getOperand(i: 0).getReg();
1756 IndRegs.insert(x: std::make_pair(x&: UpdReg, y: std::make_pair(x&: IndReg, y&: V)));
1757 }
1758 } else {
1759 Register IndReg;
1760 int64_t V;
1761 if (tryExtractPostIncInduction(DI, Phi, PhiOpReg: PhiReg, IndReg, IVBump&: V))
1762 IndRegs.insert(x: std::make_pair(x&: PhiReg, y: std::make_pair(x&: IndReg, y&: V)));
1763 }
1764 } // for (i)
1765 } // for (instr)
1766
1767 if (IndRegs.empty())
1768 return false;
1769
1770 MachineBasicBlock *TB = nullptr, *FB = nullptr;
1771 SmallVector<MachineOperand,2> Cond;
1772 // analyzeBranch returns true if it fails to analyze branch.
1773 bool NotAnalyzed = TII->analyzeBranch(MBB&: *ExitingBlock, TBB&: TB, FBB&: FB, Cond, AllowModify: false);
1774 if (NotAnalyzed || Cond.empty())
1775 return false;
1776
1777 if (ExitingBlock != Latch && (TB == Latch || FB == Latch)) {
1778 MachineBasicBlock *LTB = nullptr, *LFB = nullptr;
1779 SmallVector<MachineOperand,2> LCond;
1780 bool NotAnalyzed = TII->analyzeBranch(MBB&: *Latch, TBB&: LTB, FBB&: LFB, Cond&: LCond, AllowModify: false);
1781 if (NotAnalyzed)
1782 return false;
1783
1784 // Since latch is not the exiting block, the latch branch should be an
1785 // unconditional branch to the loop header.
1786 if (TB == Latch)
1787 TB = (LTB == Header) ? LTB : LFB;
1788 else
1789 FB = (LTB == Header) ? LTB : LFB;
1790 }
1791 if (TB != Header) {
1792 if (FB != Header) {
1793 // The latch/exit block does not go back to the header.
1794 return false;
1795 }
1796 // FB is the header (i.e., uncond. jump to branch header)
1797 // In this case, the LoopBody -> TB should not be a back edge otherwise
1798 // it could result in an infinite loop after conversion to hw_loop.
1799 // This case can happen when the Latch has two jumps like this:
1800 // Jmp_c OuterLoopHeader <-- TB
1801 // Jmp InnerLoopHeader <-- FB
1802 if (MDT->dominates(A: TB, B: FB))
1803 return false;
1804 }
1805
1806 // Expecting a predicate register as a condition. It won't be a hardware
1807 // predicate register at this point yet, just a vreg.
1808 // HexagonInstrInfo::analyzeBranch for negated branches inserts imm(0)
1809 // into Cond, followed by the predicate register. For non-negated branches
1810 // it's just the register.
1811 unsigned CSz = Cond.size();
1812 if (CSz != 1 && CSz != 2)
1813 return false;
1814
1815 if (!Cond[CSz-1].isReg())
1816 return false;
1817
1818 Register P = Cond[CSz - 1].getReg();
1819 MachineInstr *PredDef = MRI->getVRegDef(Reg: P);
1820
1821 if (!PredDef->isCompare())
1822 return false;
1823
1824 SmallSet<Register,2> CmpRegs;
1825 MachineOperand *CmpImmOp = nullptr;
1826
1827 // Go over all operands to the compare and look for immediate and register
1828 // operands. Assume that if the compare has a single register use and a
1829 // single immediate operand, then the register is being compared with the
1830 // immediate value.
1831 for (MachineOperand &MO : PredDef->operands()) {
1832 if (MO.isReg()) {
1833 // Skip all implicit references. In one case there was:
1834 // %140 = FCMPUGT32_rr %138, %139, implicit %usr
1835 if (MO.isImplicit())
1836 continue;
1837 if (MO.isUse()) {
1838 if (!isImmediate(MO)) {
1839 CmpRegs.insert(V: MO.getReg());
1840 continue;
1841 }
1842 // Consider the register to be the "immediate" operand.
1843 if (CmpImmOp)
1844 return false;
1845 CmpImmOp = &MO;
1846 }
1847 } else if (MO.isImm()) {
1848 if (CmpImmOp) // A second immediate argument? Confusing. Bail out.
1849 return false;
1850 CmpImmOp = &MO;
1851 }
1852 }
1853
1854 if (CmpRegs.empty())
1855 return false;
1856
1857 // Check if the compared register follows the order we want. Fix if needed.
1858 for (RegisterInductionSet::iterator I = IndRegs.begin(), E = IndRegs.end();
1859 I != E; ++I) {
1860 // This is a success. If the register used in the comparison is one that
1861 // we have identified as a bumped (updated) induction register, there is
1862 // nothing to do.
1863 if (CmpRegs.count(V: I->first))
1864 return true;
1865
1866 // Otherwise, if the register being compared comes out of a PHI node,
1867 // and has been recognized as following the induction pattern, and is
1868 // compared against an immediate, we can fix it.
1869 const RegisterBump &RB = I->second;
1870 if (CmpRegs.count(V: RB.first)) {
1871 if (!CmpImmOp) {
1872 // If both operands to the compare instruction are registers, see if
1873 // it can be changed to use induction register as one of the operands.
1874 MachineInstr *IndI = nullptr;
1875 MachineInstr *nonIndI = nullptr;
1876 MachineOperand *IndMO = nullptr;
1877 MachineOperand *nonIndMO = nullptr;
1878
1879 for (unsigned i = 1, n = PredDef->getNumOperands(); i < n; ++i) {
1880 MachineOperand &MO = PredDef->getOperand(i);
1881 if (MO.isReg() && MO.getReg() == RB.first) {
1882 LLVM_DEBUG(dbgs() << "\n DefMI(" << i
1883 << ") = " << *(MRI->getVRegDef(I->first)));
1884 if (IndI)
1885 return false;
1886
1887 IndI = MRI->getVRegDef(Reg: I->first);
1888 IndMO = &MO;
1889 } else if (MO.isReg()) {
1890 LLVM_DEBUG(dbgs() << "\n DefMI(" << i
1891 << ") = " << *(MRI->getVRegDef(MO.getReg())));
1892 if (nonIndI)
1893 return false;
1894
1895 nonIndI = MRI->getVRegDef(Reg: MO.getReg());
1896 nonIndMO = &MO;
1897 }
1898 }
1899 if (IndI && nonIndI &&
1900 nonIndI->getOpcode() == Hexagon::A2_addi &&
1901 nonIndI->getOperand(i: 2).isImm() &&
1902 nonIndI->getOperand(i: 2).getImm() == - RB.second) {
1903 bool Order = orderBumpCompare(BumpI: IndI, CmpI: PredDef);
1904 if (Order) {
1905 IndMO->setReg(I->first);
1906 nonIndMO->setReg(nonIndI->getOperand(i: 1).getReg());
1907 return true;
1908 }
1909 }
1910 return false;
1911 }
1912
1913 // It is not valid to do this transformation on an unsigned comparison
1914 // because it may underflow.
1915 Comparison::Kind Cmp =
1916 getComparisonKind(CondOpc: PredDef->getOpcode(), InitialValue: nullptr, EndValue: nullptr, IVBump: 0);
1917 if (!Cmp || Comparison::isUnsigned(Cmp))
1918 return false;
1919
1920 // If the register is being compared against an immediate, try changing
1921 // the compare instruction to use induction register and adjust the
1922 // immediate operand.
1923 int64_t CmpImm = getImmediate(MO: *CmpImmOp);
1924 int64_t V = RB.second;
1925 // Handle Overflow (64-bit).
1926 if (((V > 0) && (CmpImm > INT64_MAX - V)) ||
1927 ((V < 0) && (CmpImm < INT64_MIN - V)))
1928 return false;
1929 CmpImm += V;
1930 // Most comparisons of register against an immediate value allow
1931 // the immediate to be constant-extended. There are some exceptions
1932 // though. Make sure the new combination will work.
1933 if (CmpImmOp->isImm() && !TII->isExtendable(MI: *PredDef) &&
1934 !TII->isValidOffset(Opcode: PredDef->getOpcode(), Offset: CmpImm, Extend: false))
1935 return false;
1936
1937 // Make sure that the compare happens after the bump. Otherwise,
1938 // after the fixup, the compare would use a yet-undefined register.
1939 MachineInstr *BumpI = MRI->getVRegDef(Reg: I->first);
1940 bool Order = orderBumpCompare(BumpI, CmpI: PredDef);
1941 if (!Order)
1942 return false;
1943
1944 // Finally, fix the compare instruction.
1945 setImmediate(MO&: *CmpImmOp, Val: CmpImm);
1946 for (MachineOperand &MO : PredDef->operands()) {
1947 if (MO.isReg() && MO.getReg() == RB.first) {
1948 MO.setReg(I->first);
1949 return true;
1950 }
1951 }
1952 }
1953 }
1954
1955 return false;
1956}
1957
1958/// createPreheaderForLoop - Create a preheader for a given loop.
1959MachineBasicBlock *HexagonHardwareLoops::createPreheaderForLoop(
1960 MachineLoop *L) {
1961 if (MachineBasicBlock *TmpPH = MLI->findLoopPreheader(L, SpeculativePreheader: SpecPreheader))
1962 return TmpPH;
1963 if (!HWCreatePreheader)
1964 return nullptr;
1965
1966 MachineBasicBlock *Header = L->getHeader();
1967 MachineBasicBlock *Latch = L->getLoopLatch();
1968 MachineBasicBlock *ExitingBlock = L->findLoopControlBlock();
1969 MachineFunction *MF = Header->getParent();
1970 DebugLoc DL;
1971
1972#ifndef NDEBUG
1973 if ((!PHFn.empty()) && (PHFn != MF->getName()))
1974 return nullptr;
1975#endif
1976
1977 if (!Latch || !ExitingBlock || Header->hasAddressTaken())
1978 return nullptr;
1979
1980 using instr_iterator = MachineBasicBlock::instr_iterator;
1981
1982 // Verify that all existing predecessors have analyzable branches
1983 // (or no branches at all).
1984 using MBBVector = std::vector<MachineBasicBlock *>;
1985
1986 MBBVector Preds(Header->pred_begin(), Header->pred_end());
1987 SmallVector<MachineOperand,2> Tmp1;
1988 MachineBasicBlock *TB = nullptr, *FB = nullptr;
1989
1990 if (TII->analyzeBranch(MBB&: *ExitingBlock, TBB&: TB, FBB&: FB, Cond&: Tmp1, AllowModify: false))
1991 return nullptr;
1992
1993 for (MachineBasicBlock *PB : Preds) {
1994 bool NotAnalyzed = TII->analyzeBranch(MBB&: *PB, TBB&: TB, FBB&: FB, Cond&: Tmp1, AllowModify: false);
1995 if (NotAnalyzed)
1996 return nullptr;
1997 }
1998
1999 MachineBasicBlock *NewPH = MF->CreateMachineBasicBlock();
2000 MF->insert(MBBI: Header->getIterator(), MBB: NewPH);
2001
2002 if (Header->pred_size() > 2) {
2003 // Ensure that the header has only two predecessors: the preheader and
2004 // the loop latch. Any additional predecessors of the header should
2005 // join at the newly created preheader. Inspect all PHI nodes from the
2006 // header and create appropriate corresponding PHI nodes in the preheader.
2007
2008 for (instr_iterator I = Header->instr_begin(), E = Header->instr_end();
2009 I != E && I->isPHI(); ++I) {
2010 MachineInstr *PN = &*I;
2011
2012 const MCInstrDesc &PD = TII->get(Opcode: TargetOpcode::PHI);
2013 MachineInstr *NewPN = MF->CreateMachineInstr(MCID: PD, DL);
2014 NewPH->insert(I: NewPH->end(), MI: NewPN);
2015
2016 Register PR = PN->getOperand(i: 0).getReg();
2017 const TargetRegisterClass *RC = MRI->getRegClass(Reg: PR);
2018 Register NewPR = MRI->createVirtualRegister(RegClass: RC);
2019 NewPN->addOperand(Op: MachineOperand::CreateReg(Reg: NewPR, isDef: true));
2020
2021 // Copy all non-latch operands of a header's PHI node to the newly
2022 // created PHI node in the preheader.
2023 for (unsigned i = 1, n = PN->getNumOperands(); i < n; i += 2) {
2024 Register PredR = PN->getOperand(i).getReg();
2025 unsigned PredRSub = PN->getOperand(i).getSubReg();
2026 MachineBasicBlock *PredB = PN->getOperand(i: i+1).getMBB();
2027 if (PredB == Latch)
2028 continue;
2029
2030 MachineOperand MO = MachineOperand::CreateReg(Reg: PredR, isDef: false);
2031 MO.setSubReg(PredRSub);
2032 NewPN->addOperand(Op: MO);
2033 NewPN->addOperand(Op: MachineOperand::CreateMBB(MBB: PredB));
2034 }
2035
2036 // Remove copied operands from the old PHI node and add the value
2037 // coming from the preheader's PHI.
2038 for (int i = PN->getNumOperands()-2; i > 0; i -= 2) {
2039 MachineBasicBlock *PredB = PN->getOperand(i: i+1).getMBB();
2040 if (PredB != Latch) {
2041 PN->removeOperand(OpNo: i+1);
2042 PN->removeOperand(OpNo: i);
2043 }
2044 }
2045 PN->addOperand(Op: MachineOperand::CreateReg(Reg: NewPR, isDef: false));
2046 PN->addOperand(Op: MachineOperand::CreateMBB(MBB: NewPH));
2047 }
2048 } else {
2049 assert(Header->pred_size() == 2);
2050
2051 // The header has only two predecessors, but the non-latch predecessor
2052 // is not a preheader (e.g. it has other successors, etc.)
2053 // In such a case we don't need any extra PHI nodes in the new preheader,
2054 // all we need is to adjust existing PHIs in the header to now refer to
2055 // the new preheader.
2056 for (instr_iterator I = Header->instr_begin(), E = Header->instr_end();
2057 I != E && I->isPHI(); ++I) {
2058 MachineInstr *PN = &*I;
2059 for (unsigned i = 1, n = PN->getNumOperands(); i < n; i += 2) {
2060 MachineOperand &MO = PN->getOperand(i: i+1);
2061 if (MO.getMBB() != Latch)
2062 MO.setMBB(NewPH);
2063 }
2064 }
2065 }
2066
2067 // "Reroute" the CFG edges to link in the new preheader.
2068 // If any of the predecessors falls through to the header, insert a branch
2069 // to the new preheader in that place.
2070 SmallVector<MachineOperand,1> Tmp2;
2071 SmallVector<MachineOperand,1> EmptyCond;
2072
2073 TB = FB = nullptr;
2074
2075 for (MachineBasicBlock *PB : Preds) {
2076 if (PB != Latch) {
2077 Tmp2.clear();
2078 bool NotAnalyzed = TII->analyzeBranch(MBB&: *PB, TBB&: TB, FBB&: FB, Cond&: Tmp2, AllowModify: false);
2079 (void)NotAnalyzed; // suppress compiler warning
2080 assert (!NotAnalyzed && "Should be analyzable!");
2081 if (TB != Header && (Tmp2.empty() || FB != Header))
2082 TII->insertBranch(MBB&: *PB, TBB: NewPH, FBB: nullptr, Cond: EmptyCond, DL);
2083 PB->ReplaceUsesOfBlockWith(Old: Header, New: NewPH);
2084 }
2085 }
2086
2087 // It can happen that the latch block will fall through into the header.
2088 // Insert an unconditional branch to the header.
2089 TB = FB = nullptr;
2090 bool LatchNotAnalyzed = TII->analyzeBranch(MBB&: *Latch, TBB&: TB, FBB&: FB, Cond&: Tmp2, AllowModify: false);
2091 (void)LatchNotAnalyzed; // suppress compiler warning
2092 assert (!LatchNotAnalyzed && "Should be analyzable!");
2093 if (!TB && !FB)
2094 TII->insertBranch(MBB&: *Latch, TBB: Header, FBB: nullptr, Cond: EmptyCond, DL);
2095
2096 // Finally, the branch from the preheader to the header.
2097 TII->insertBranch(MBB&: *NewPH, TBB: Header, FBB: nullptr, Cond: EmptyCond, DL);
2098 NewPH->addSuccessor(Succ: Header);
2099
2100 MachineLoop *ParentLoop = L->getParentLoop();
2101 if (ParentLoop)
2102 ParentLoop->addBasicBlockToLoop(NewBB: NewPH, LI&: *MLI);
2103
2104 // Update the dominator information with the new preheader.
2105 if (MDT) {
2106 if (MachineDomTreeNode *HN = MDT->getNode(BB: Header)) {
2107 if (MachineDomTreeNode *DHN = HN->getIDom()) {
2108 MDT->addNewBlock(BB: NewPH, DomBB: DHN->getBlock());
2109 MDT->changeImmediateDominator(BB: Header, NewBB: NewPH);
2110 }
2111 }
2112 }
2113
2114 return NewPH;
2115}
2116