LLVM 24.0.0git
HexagonHardwareLoops.cpp
Go to the documentation of this file.
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"
34#include "llvm/ADT/Statistic.h"
35#include "llvm/ADT/StringRef.h"
47#include "llvm/IR/DebugLoc.h"
49#include "llvm/Pass.h"
51#include "llvm/Support/Debug.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(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;
99 const HexagonInstrInfo *TII;
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>();
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, 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, 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{Register(), 0} {}
328 Values(const Values&) = default;
329 struct {
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(Contents.R.Reg, TRI, 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)
377INITIALIZE_PASS_END(HexagonHardwareLoops, "hwloops",
378 "Hexagon Hardware Loops", false, false)
379
381 return new HexagonHardwareLoops();
382}
383
384bool HexagonHardwareLoops::runOnMachineFunction(MachineFunction &MF) {
385 LLVM_DEBUG(dbgs() << "********* Hexagon Hardware Loops *********\n");
386 if (skipFunction(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();
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, 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(*DI))
416 return false;
417
418 unsigned BasePos, OffsetPos;
419 if (!TII->getBaseAndOffsetPosition(*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(BasePos);
429 if (!BaseOp.isReg() || !BaseOp.isTied())
430 return false;
431 if (DI->getOperand(DI->findTiedOperandIdx(BasePos)).getReg() != PhiOpReg)
432 return false;
433
434 IndReg = BaseOp.getReg();
435 IVBump = DI->getOperand(OffsetPos).getImm();
436 return MRI->getVRegDef(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, 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+1).getMBB() != Latch)
474 continue;
475
476 Register PhiOpReg = Phi->getOperand(i).getReg();
477 MachineInstr *DI = MRI->getVRegDef(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(1).getReg();
483 MachineOperand &Opnd2 = DI->getOperand(2);
484 int64_t V;
485 if (MRI->getVRegDef(IndReg) == Phi && checkForImmediate(Opnd2, V)) {
486 Register UpdReg = DI->getOperand(0).getReg();
487 IndMap.insert(std::make_pair(UpdReg, std::make_pair(IndReg, V)));
488 }
489 } else {
490 Register IndReg;
491 int64_t V;
492 if (tryExtractPostIncInduction(DI, Phi, PhiOpReg, IndReg, V))
493 IndMap.insert(std::make_pair(PhiOpReg, std::make_pair(IndReg, V)));
494 }
495 } // for (i)
496 } // for (instr)
497
499 MachineBasicBlock *TB = nullptr, *FB = nullptr;
500 bool NotAnalyzed = TII->analyzeBranch(*ExitingBlock, TB, FB, Cond, false);
501 if (NotAnalyzed)
502 return false;
503
504 Register PredR;
505 unsigned PredPos;
506 RegState PredRegFlags;
507 if (!TII->getPredReg(Cond, PredR, PredPos, PredRegFlags))
508 return false;
509
510 MachineInstr *PredI = MRI->getVRegDef(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(*PredI, CmpReg1, CmpReg2, CmpMask, 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(CmpReg1);
530 if (F1 != IndMapEnd)
531 F = F1;
532 }
533 if (CmpReg2 != 0) {
534 InductionMap::iterator F2 = IndMap.find(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(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();
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(Incoming)) {
626 if (L->contains(Backedge))
627 return nullptr;
628 std::swap(Incoming, Backedge);
629 } else if (!L->contains(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, IVReg, IVBump, IVOp);
643 if (!FoundIV)
644 return nullptr;
645
646 MachineBasicBlock *Preheader = MLI->findLoopPreheader(L, SpecPreheader);
647
648 MachineOperand *InitialValue = nullptr;
649 MachineInstr *IV_Phi = MRI->getVRegDef(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+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
662 MachineBasicBlock *TB = nullptr, *FB = nullptr;
663 bool NotAnalyzed = TII->analyzeBranch(*ExitingBlock, TB, FB, Cond, 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;
675 bool NotAnalyzed = TII->analyzeBranch(*Latch, LTB, LFB, LCond, 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, PredPos, PredRegFlags))
696 return nullptr;
697 MachineInstr *CondI = MRI->getVRegDef(PredReg);
698 unsigned CondOpc = CondI->getOpcode();
699
700 Register CmpReg1, CmpReg2;
701 int64_t Mask = 0, ImmValue = 0;
702 bool AnalyzedCmp =
703 TII->analyzeCompare(*CondI, CmpReg1, CmpReg2, Mask, 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(CondI);
710 OldInsts.push_back(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(1);
720 const MachineOperand &Op2 = CondI->getOperand(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(R);
746 if (!MDT->properlyDominates(DefBB, Header)) {
747 int64_t V;
748 if (!checkForImmediate(*InitialValue, V))
749 return nullptr;
750 }
751 OldInsts.push_back(MRI->getVRegDef(R));
752 }
753 if (EndValue->isReg()) {
754 Register R = EndValue->getReg();
755 MachineBasicBlock *DefBB = MRI->getDefBlock(R);
756 if (!MDT->properlyDominates(DefBB, Header)) {
757 int64_t V;
758 if (!checkForImmediate(*EndValue, V))
759 return nullptr;
760 }
761 OldInsts.push_back(MRI->getVRegDef(R));
762 }
763
764 return computeCount(L, InitialValue, 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(Start->getReg());
790 if (StartValInstr && (StartValInstr->getOpcode() == Hexagon::A2_tfrsi ||
791 StartValInstr->getOpcode() == Hexagon::A2_tfrpi))
792 Start = &StartValInstr->getOperand(1);
793 }
794 if (End->isReg()) {
795 const MachineInstr *EndValInstr = MRI->getVRegDef(End->getReg());
796 if (EndValInstr && (EndValInstr->getOpcode() == Hexagon::A2_tfrsi ||
797 EndValInstr->getOpcode() == Hexagon::A2_tfrpi))
798 End = &EndValInstr->getOperand(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(Start, End, Loop->getLoopPreheader(), 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(std::abs(IVBump)))
878 return nullptr;
879
880 MachineBasicBlock *PH = MLI->findLoopPreheader(Loop, SpecPreheader);
881 assert (PH && "Should have a preheader by now");
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(Start, End);
896 IVBump = -IVBump;
897 std::swap(CmpLess, 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(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(Hexagon::A2_sub) :
965 (RegToImm ? TII->get(Hexagon::A2_subri) :
966 TII->get(Hexagon::A2_addi));
967 if (RegToReg || RegToImm) {
968 Register SubR = MRI->createVirtualRegister(IntRC);
969 MachineInstrBuilder SubIB =
970 BuildMI(*PH, InsertPos, DL, SubD, SubR);
971
972 if (RegToReg)
973 SubIB.addReg(End->getReg(), {}, End->getSubReg())
974 .addReg(Start->getReg(), {}, Start->getSubReg());
975 else
976 SubIB.addImm(EndV).addReg(Start->getReg(), {}, 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(End->getReg());
983 if (EndValInstr->getOpcode() == Hexagon::A2_addi &&
984 EndValInstr->getOperand(1).getSubReg() == 0 &&
985 EndValInstr->getOperand(2).getImm() == StartV) {
986 DistR = EndValInstr->getOperand(1).getReg();
987 } else {
988 Register SubR = MRI->createVirtualRegister(IntRC);
989 MachineInstrBuilder SubIB =
990 BuildMI(*PH, InsertPos, DL, SubD, SubR);
991 SubIB.addReg(End->getReg(), {}, End->getSubReg()).addImm(-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(IntRC);
1008 MCInstrDesc const &AddD = TII->get(Hexagon::A2_addi);
1009 BuildMI(*PH, InsertPos, DL, AddD, AddR)
1010 .addReg(DistR, {}, DistSR)
1011 .addImm(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(IVBump);
1027
1028 // Generate NormR = LSR DistR, Shift.
1029 Register LsrR = MRI->createVirtualRegister(IntRC);
1030 const MCInstrDesc &LsrD = TII->get(Hexagon::S2_lsr_i_r);
1031 BuildMI(*PH, InsertPos, DL, LsrD, LsrR)
1032 .addReg(AdjR, {}, AdjSR)
1033 .addImm(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(PredRC);
1052 unsigned DistCheckOpc = (CmpLess && Comparison::isUnsigned(Cmp))
1053 ? Hexagon::C2_cmpgtui
1054 : Hexagon::C2_cmpgti;
1055 const MCInstrDesc &DistCheckD = TII->get(DistCheckOpc);
1056 BuildMI(*PH, InsertPos, DL, DistCheckD, DistCheckR)
1057 .addReg(DistR, {}, DistSR)
1058 .addImm((CmpLess) ? 0 : -1);
1059
1060 // Generate:
1061 // MUXR = MUX DistCheck, CountR, 1 --> CmpLess
1062 // MUXR = MUX DistCheck, 1, CountR --> CmpGreater
1063 MuxR = MRI->createVirtualRegister(IntRC);
1064 if (CmpLess) {
1065 const MCInstrDesc &MuxD = TII->get(Hexagon::C2_muxir);
1066 BuildMI(*PH, InsertPos, DL, MuxD, MuxR)
1067 .addReg(DistCheckR)
1068 .addReg(CountR, {}, CountSR)
1069 .addImm(1);
1070 } else {
1071 const MCInstrDesc &MuxD = TII->get(Hexagon::C2_muxri);
1072 BuildMI(*PH, InsertPos, DL, MuxD, MuxR)
1073 .addReg(DistCheckR)
1074 .addImm(1)
1075 .addReg(CountR, {}, 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(*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(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, 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(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(Reg);
1143 use_nodbg_iterator End = MRI->use_nodbg_end();
1144 if (std::next(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(OPReg);
1155 J != End; J = nextJ) {
1156 nextJ = std::next(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(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
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 :
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(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([&]() {
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.
1279 L->getExitingBlocks(ExitingBlocks);
1280 bool HasUnreachableExit = false;
1281 if (LastMBB && ExitingBlocks.size() > 1) {
1282 for (MachineBasicBlock *Succ : LastMBB->successors()) {
1283 if (!L->contains(Succ) && !Succ->empty() && Succ->succ_empty() &&
1284 !Succ->isReturnBlock()) {
1285 HasUnreachableExit = true;
1286 break;
1287 }
1288 }
1289 }
1290 if (!LastMBB || HasUnreachableExit) {
1291 MORE->emit([&]() {
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
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([&]() {
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, 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([&]() {
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(TripCount->getReg());
1342 MachineBasicBlock *BBDef = TCDef->getParent();
1343 if (!MDT->dominates(BBDef, Preheader)) {
1344 MORE->emit([&]() {
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;
1361
1362 if (TII->analyzeBranch(*ExitingBlock, TB, FB, Cond, false))
1363 return false;
1364
1365 if (L->contains(TB))
1366 LoopStart = TB;
1367 else if (L->contains(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(&Hexagon::IntRegsRegClass);
1384 BuildMI(*Preheader, InsertPos, DL, TII->get(TargetOpcode::COPY), CountReg)
1385 .addReg(TripCount->getReg(), {}, TripCount->getSubReg());
1386 // Add the Loop instruction to the beginning of the loop.
1387 BuildMI(*Preheader, InsertPos, DL, TII->get(LOOP_r)).addMBB(LoopStart)
1388 .addReg(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(LOOP_i, CountImm)) {
1396 Register CountReg = MRI->createVirtualRegister(&Hexagon::IntRegsRegClass);
1397 BuildMI(*Preheader, InsertPos, DL, TII->get(Hexagon::A2_tfrsi), CountReg)
1398 .addImm(CountImm);
1399 BuildMI(*Preheader, InsertPos, DL, TII->get(LOOP_r))
1400 .addMBB(LoopStart).addReg(CountReg);
1401 } else
1402 BuildMI(*Preheader, InsertPos, DL, TII->get(LOOP_i))
1403 .addMBB(LoopStart).addImm(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(*LastMBB, LastI, LastIDL, TII->get(ENDLOOP)).addMBB(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(1).getMBB();
1420 LastI = LastMBB->erase(LastI);
1421 if (!L->contains(BranchTarget)) {
1422 if (LastI != LastMBB->end())
1423 LastI = LastMBB->erase(LastI);
1425 TII->insertBranch(*LastMBB, BranchTarget, nullptr, Cond, LastIDL);
1426 }
1427 } else {
1428 // Conditional branch to loop start; just delete it.
1429 LastMBB->erase(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(OldInsts[i]);
1437
1438 ++NumHWLoops;
1439
1440 MORE->emit([&]() {
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(0).getReg();
1474 bool FoundBump = false;
1475 instr_iterator CmpIt = CmpI->getIterator(), NextIt = std::next(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(++BumpI->getIterator(), BB, 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(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(L->getBlocks(), A))
1510 return false;
1511 MachineInstr *Def = MRI->getVRegDef(MO->getReg());
1512 LoopFeederPhi.insert(std::make_pair(MO->getReg(), 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, MBB, Phi, &(Phi->getOperand(i)), LoopFeederPhi))
1529 if (loopCountMayWrapOrUnderFlow(&(Phi->getOperand(i)), EndVal,
1530 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(*InitVal, 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(Def, EndVal, Def->getParent(),
1579 L, LoopFeederPhi))
1580 return false;
1581 if (Def->isCopy() && !loopCountMayWrapOrUnderFlow(&(Def->getOperand(1)),
1582 EndVal, 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.
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, CmpReg1, CmpReg2, CmpMask, CmpValue))
1596 continue;
1597
1598 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
1600 if (TII->analyzeBranch(*MI->getParent(), TBB, FBB, Cond, false))
1601 continue;
1602
1603 Comparison::Kind Cmp =
1604 getComparisonKind(MI->getOpcode(), nullptr, nullptr, 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(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(DI->getOperand(1), 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(1);
1669 const MachineOperand &S2 = DI->getOperand(2);
1670 int64_t V1, V2;
1671 if (!checkForImmediate(S1, V1) || !checkForImmediate(S2, 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(1);
1678 const MachineOperand &S3 = DI->getOperand(3);
1679 int64_t V1, V3;
1680 if (!checkForImmediate(S1, V1) || !checkForImmediate(S3, V3))
1681 return false;
1682 unsigned Sub2 = DI->getOperand(2).getImm();
1683 unsigned Sub4 = DI->getOperand(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(R);
1722
1723 const TargetRegisterClass *RC = MRI->getRegClass(R);
1725 MachineBasicBlock &B = *DI->getParent();
1726 DebugLoc DL = DI->getDebugLoc();
1727 BuildMI(B, DI, DL, TII->get(DI->getOpcode()), 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+1).getMBB() != Latch)
1760 continue;
1761
1762 Register PhiReg = Phi->getOperand(i).getReg();
1763 MachineInstr *DI = MRI->getVRegDef(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(1).getReg();
1769 MachineOperand &Opnd2 = DI->getOperand(2);
1770 int64_t V;
1771 if (MRI->getVRegDef(IndReg) == Phi && checkForImmediate(Opnd2, V)) {
1772 Register UpdReg = DI->getOperand(0).getReg();
1773 IndRegs.insert(std::make_pair(UpdReg, std::make_pair(IndReg, V)));
1774 }
1775 } else {
1776 Register IndReg;
1777 int64_t V;
1778 if (tryExtractPostIncInduction(DI, Phi, PhiReg, IndReg, V))
1779 IndRegs.insert(std::make_pair(PhiReg, std::make_pair(IndReg, V)));
1780 }
1781 } // for (i)
1782 } // for (instr)
1783
1784 if (IndRegs.empty())
1785 return false;
1786
1787 MachineBasicBlock *TB = nullptr, *FB = nullptr;
1789 // analyzeBranch returns true if it fails to analyze branch.
1790 bool NotAnalyzed = TII->analyzeBranch(*ExitingBlock, TB, FB, Cond, false);
1791 if (NotAnalyzed || Cond.empty())
1792 return false;
1793
1794 if (ExitingBlock != Latch && (TB == Latch || FB == Latch)) {
1795 MachineBasicBlock *LTB = nullptr, *LFB = nullptr;
1797 bool NotAnalyzed = TII->analyzeBranch(*Latch, LTB, LFB, LCond, 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(TB, 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(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(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(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(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(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(MO.getReg());
1913 nonIndMO = &MO;
1914 }
1915 }
1916 if (IndI && nonIndI &&
1917 nonIndI->getOpcode() == Hexagon::A2_addi &&
1918 nonIndI->getOperand(2).isImm() &&
1919 nonIndI->getOperand(2).getImm() == - RB.second) {
1920 bool Order = orderBumpCompare(IndI, PredDef);
1921 if (Order) {
1922 IndMO->setReg(I->first);
1923 nonIndMO->setReg(nonIndI->getOperand(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(PredDef->getOpcode(), nullptr, nullptr, 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(*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(*PredDef) &&
1951 !TII->isValidOffset(PredDef->getOpcode(), CmpImm, 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(I->first);
1957 bool Order = orderBumpCompare(BumpI, PredDef);
1958 if (!Order)
1959 return false;
1960
1961 // Finally, fix the compare instruction.
1962 setImmediate(*CmpImmOp, 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, 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());
2005 MachineBasicBlock *TB = nullptr, *FB = nullptr;
2006
2007 if (TII->analyzeBranch(*ExitingBlock, TB, FB, Tmp1, false))
2008 return nullptr;
2009
2010 for (MachineBasicBlock *PB : Preds) {
2011 bool NotAnalyzed = TII->analyzeBranch(*PB, TB, FB, Tmp1, false);
2012 if (NotAnalyzed)
2013 return nullptr;
2014 }
2015
2016 MachineBasicBlock *NewPH = MF->CreateMachineBasicBlock();
2017 MF->insert(Header->getIterator(), 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(TargetOpcode::PHI);
2030 MachineInstr *NewPN = MF->CreateMachineInstr(PD, DL);
2031 NewPH->insert(NewPH->end(), NewPN);
2032
2033 Register PR = PN->getOperand(0).getReg();
2034 const TargetRegisterClass *RC = MRI->getRegClass(PR);
2035 Register NewPR = MRI->createVirtualRegister(RC);
2036 NewPN->addOperand(MachineOperand::CreateReg(NewPR, 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+1).getMBB();
2044 if (PredB == Latch)
2045 continue;
2046
2047 MachineOperand MO = MachineOperand::CreateReg(PredR, false);
2048 MO.setSubReg(PredRSub);
2049 NewPN->addOperand(MO);
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+1).getMBB();
2057 if (PredB != Latch) {
2058 PN->removeOperand(i+1);
2059 PN->removeOperand(i);
2060 }
2061 }
2062 PN->addOperand(MachineOperand::CreateReg(NewPR, false));
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+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.
2089
2090 TB = FB = nullptr;
2091
2092 for (MachineBasicBlock *PB : Preds) {
2093 if (PB != Latch) {
2094 Tmp2.clear();
2095 bool NotAnalyzed = TII->analyzeBranch(*PB, TB, FB, Tmp2, false);
2096 (void)NotAnalyzed; // suppress compiler warning
2097 assert (!NotAnalyzed && "Should be analyzable!");
2098 if (TB != Header && (Tmp2.empty() || FB != Header))
2099 TII->insertBranch(*PB, NewPH, nullptr, EmptyCond, DL);
2100 PB->ReplaceUsesOfBlockWith(Header, 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(*Latch, TB, FB, Tmp2, false);
2108 (void)LatchNotAnalyzed; // suppress compiler warning
2109 assert (!LatchNotAnalyzed && "Should be analyzable!");
2110 if (!TB && !FB)
2111 TII->insertBranch(*Latch, Header, nullptr, EmptyCond, DL);
2112
2113 // Finally, the branch from the preheader to the header.
2114 TII->insertBranch(*NewPH, Header, nullptr, EmptyCond, DL);
2115 NewPH->addSuccessor(Header);
2116
2117 MachineLoop *ParentLoop = L->getParentLoop();
2118 if (ParentLoop)
2119 ParentLoop->addBasicBlockToLoop(NewPH, *MLI);
2120
2121 // Update the dominator information with the new preheader.
2122 if (MDT) {
2123 if (MachineDomTreeNode *HN = MDT->getNode(Header)) {
2124 if (MachineDomTreeNode *DHN = HN->getIDom()) {
2125 MDT->addNewBlock(NewPH, DHN->getBlock());
2126 MDT->changeImmediateDominator(Header, NewPH);
2127 }
2128 }
2129 }
2130
2131 return NewPH;
2132}
MachineInstrBuilder & UseMI
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
uint64_t uint64_t
uint64_t Imm
constexpr LLT S1
MachineBasicBlock & MBB
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static bool isSigned(unsigned Opcode)
#define DEBUG_TYPE
const HexagonInstrInfo * TII
static cl::opt< bool > HWCreatePreheader("hexagon-hwloop-preheader", cl::Hidden, cl::init(true), cl::desc("Add a preheader to a hardware loop if one doesn't exist"))
static cl::opt< bool > SpecPreheader("hwloop-spec-preheader", cl::Hidden, cl::desc("Allow speculation of preheader " "instructions"))
static cl::opt< std::string > PHFn("hexagon-hwloop-phfn", cl::Hidden, cl::init(""))
static cl::opt< int > HWLoopLimit("hexagon-max-hwloop", cl::Hidden, cl::init(-1))
IRTranslator LLVM IR MI
#define F(x, y, z)
Definition MD5.cpp:54
#define I(x, y, z)
Definition MD5.cpp:57
===- MachineOptimizationRemarkEmitter.h - Opt Diagnostics -*- C++ -*-—===//
Register Reg
Register const TargetRegisterInfo * TRI
Promote Memory to Register
Definition Mem2Reg.cpp:110
static MCRegister getReg(const MCDisassembler *D, unsigned RC, unsigned RegNo)
static bool isReg(const MCInst &MI, unsigned OpNo)
#define P(N)
PassBuilder PB(Mod->getContext(), Machine, PassOpts->PTO, std::nullopt, &PIC)
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition PassSupport.h:42
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition PassSupport.h:44
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition PassSupport.h:39
SmallVector< MachineBasicBlock *, 4 > MBBVector
SmallVector< MachineOperand, 4 > Cond
MachineRegisterInfo & MRI
const SmallVectorImpl< MachineOperand > MachineBasicBlock * TBB
bool isDead(const MachineInstr &MI, const MachineRegisterInfo &MRI)
This file contains some templates that are useful if you are working with the STL at all.
This file defines the SmallSet class.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Definition Statistic.h:171
#define LLVM_DEBUG(...)
Definition Debug.h:119
AnalysisUsage & addRequired()
DomTreeNodeBase * getIDom() const
void changeImmediateDominator(DomTreeNodeBase< NodeT > *N, DomTreeNodeBase< NodeT > *NewIDom)
changeImmediateDominator - This method is used to update the dominator tree information when a node's...
DomTreeNodeBase< NodeT > * addNewBlock(NodeT *BB, NodeT *DomBB)
Add a new node to the dominator tree information.
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
bool properlyDominates(const DomTreeNodeBase< NodeT > *A, const DomTreeNodeBase< NodeT > *B) const
properlyDominates - Returns true iff A dominates B and A != B.
FunctionPass class - This class is used to implement most global optimizations.
Definition Pass.h:312
bool doesNotReturn(const MachineInstr &CallMI) const
bool analyzeBranch(MachineBasicBlock &MBB, MachineBasicBlock *&TBB, MachineBasicBlock *&FBB, SmallVectorImpl< MachineOperand > &Cond, bool AllowModify) const override
Analyze the branching code at the end of MBB, returning true if it cannot be understood (e....
bool isPostIncWithImmOffset(const MachineInstr &MI) const
bool analyzeCompare(const MachineInstr &MI, Register &SrcReg, Register &SrcReg2, int64_t &Mask, int64_t &Value) const override
For a comparison instruction, return the source registers in SrcReg and SrcReg2 if having two registe...
unsigned insertBranch(MachineBasicBlock &MBB, MachineBasicBlock *TBB, MachineBasicBlock *FBB, ArrayRef< MachineOperand > Cond, const DebugLoc &DL, int *BytesAdded=nullptr) const override
Insert branch code into the end of the specified MachineBasicBlock.
bool predOpcodeHasNot(ArrayRef< MachineOperand > Cond) const
bool getPredReg(ArrayRef< MachineOperand > Cond, Register &PredReg, unsigned &PredRegPos, RegState &PredRegFlags) const
bool getBaseAndOffsetPosition(const MachineInstr &MI, unsigned &BasePos, unsigned &OffsetPos) const override
For instructions with a base and offset, return the position of the base register and offset operands...
bool isExtendable(const MachineInstr &MI) const
bool isValidOffset(unsigned Opcode, int Offset, bool Extend=true) const
const HexagonInstrInfo * getInstrInfo() const override
const HexagonRegisterInfo * getRegisterInfo() const override
void addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase< BlockT, LoopT > &LI)
This method is used by other analyses to update loop information.
bool isAdd() const
Return true if the instruction is an add instruction.
LLVM_ABI instr_iterator insert(instr_iterator I, MachineInstr *M)
Insert MI into the instruction list before I, possibly inside a bundle.
LLVM_ABI iterator getFirstTerminator()
Returns an iterator to the first terminator instruction of this basic block.
LLVM_ABI void addSuccessor(MachineBasicBlock *Succ, BranchProbability Prob=BranchProbability::getUnknown())
Add Succ as a successor of this MachineBasicBlock.
SmallVectorImpl< MachineBasicBlock * >::iterator pred_iterator
Instructions::iterator instr_iterator
LLVM_ABI instr_iterator erase(instr_iterator I)
Remove an instruction from the instruction list and delete it.
iterator_range< succ_iterator > successors()
void splice(iterator Where, MachineBasicBlock *Other, iterator From)
Take an instruction from MBB 'Other' at the position From, and insert it into this MBB right before '...
MachineInstrBundleIterator< MachineInstr > iterator
void setMachineBlockAddressTaken()
Set this block to indicate that its address is used as something other than the target of a terminato...
Analysis pass which computes a MachineDominatorTree.
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
bool dominates(const MachineInstr *A, const MachineInstr *B) const
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Function & getFunction()
Return the LLVM function that this machine code represents.
MachineBasicBlock * CreateMachineBasicBlock(const BasicBlock *BB=nullptr, std::optional< UniqueBBID > BBID=std::nullopt)
CreateMachineInstr - Allocate a new MachineInstr.
void insert(iterator MBBI, MachineBasicBlock *MBB)
const MachineInstrBuilder & addReg(Register RegNo, RegState Flags={}, unsigned SubReg=0) const
Add a new virtual register operand.
const MachineInstrBuilder & addImm(int64_t Val) const
Add a new immediate operand.
const MachineInstrBuilder & addMBB(MachineBasicBlock *MBB, unsigned TargetFlags=0) const
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
const MachineBasicBlock * getParent() const
unsigned getNumOperands() const
Retuns the total number of operands.
LLVM_ABI void addOperand(MachineFunction &MF, const MachineOperand &Op)
Add the specified operand to the instruction.
bool isCompare(QueryType Type=IgnoreBundle) const
Return true if this instruction is a comparison.
const MCInstrDesc & getDesc() const
Returns the target instruction descriptor of this MachineInstr.
mop_range operands()
LLVM_ABI void insert(mop_iterator InsertBefore, ArrayRef< MachineOperand > Ops)
Inserts Ops BEFORE It. Can untie/retie tied operands.
LLVM_ABI unsigned findTiedOperandIdx(unsigned OpIdx) const
Given the index of a tied register operand, find the operand it is tied to.
const DebugLoc & getDebugLoc() const
Returns the debug location id of this MachineInstr.
LLVM_ABI void removeOperand(unsigned OpNo)
Erase an operand from an instruction, leaving it with one fewer operand than it started with.
const MachineOperand & getOperand(unsigned i) const
void setSubReg(unsigned subReg)
unsigned getSubReg() const
void setImm(int64_t immVal)
int64_t getImm() const
bool isReg() const
isReg - Tests if this is a MO_Register operand.
MachineBasicBlock * getMBB() const
LLVM_ABI void setReg(Register Reg)
Change the register this operand corresponds to.
bool isImm() const
isImm - Tests if this is a MO_Immediate operand.
MachineInstr * getParent()
getParent - Return the instruction that this operand belongs to.
void setMBB(MachineBasicBlock *MBB)
Register getReg() const
getReg - Returns the register number.
static MachineOperand CreateReg(Register Reg, bool isDef, bool isImp=false, bool isKill=false, bool isDead=false, bool isUndef=false, bool isEarlyClobber=false, unsigned SubReg=0, bool isDebug=false, bool isInternalRead=false, bool isRenamable=false)
static MachineOperand CreateMBB(MachineBasicBlock *MBB, unsigned TargetFlags=0)
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
use_nodbg_iterator use_nodbg_begin(Register RegNo) const
defusechain_instr_iterator< true, false, true, true > use_instr_nodbg_iterator
use_instr_nodbg_iterator/use_instr_nodbg_begin/use_instr_nodbg_end - Walk all uses of the specified r...
const TargetRegisterClass * getRegClass(Register Reg) const
Return the register class of the specified virtual register.
static use_nodbg_iterator use_nodbg_end()
LLVM_ABI LLVM_READONLY MachineInstr * getVRegDef(Register Reg) const
getVRegDef - Return the machine instr that defines the specified virtual register or null if none is ...
bool use_nodbg_empty(Register RegNo) const
use_nodbg_empty - Return true if there are no non-Debug instructions using the specified register.
MachineBasicBlock * getDefBlock(Register Reg) const
Return the machine basic block in which the specified virtual register is defined,...
LLVM_ABI Register createVirtualRegister(const TargetRegisterClass *RegClass, StringRef Name="")
createVirtualRegister - Create and return a new virtual register in the function with the specified r...
use_instr_nodbg_iterator use_instr_nodbg_begin(Register RegNo) const
defusechain_iterator< true, false, true, true, false > use_nodbg_iterator
use_nodbg_iterator/use_nodbg_begin/use_nodbg_end - Walk all uses of the specified register,...
iterator_range< use_iterator > use_operands(Register Reg) const
static use_instr_nodbg_iterator use_instr_nodbg_end()
constexpr bool isVirtual() const
Return true if the specified register number is in the virtual register namespace.
Definition Register.h:79
size_type count(const T &V) const
count - Return 1 if the element is in the set, 0 otherwise.
Definition SmallSet.h:176
bool empty() const
Definition SmallSet.h:169
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
Definition SmallSet.h:184
void push_back(const T &Elt)
self_iterator getIterator()
Definition ilist_node.h:123
#define INT64_MIN
Definition DataTypes.h:74
#define INT64_MAX
Definition DataTypes.h:71
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
constexpr std::underlying_type_t< E > Mask()
Get a bitmask with 1s in all places up to the high-order bit of E's largest value.
@ TB
TB - TwoByte - Set if this instruction has a two byte opcode, which starts with a 0x0F byte before th...
@ PD
PD - Prefix code for packed double precision vector floating point operations performed in the SSE re...
initializer< Ty > init(const Ty &Val)
NodeAddr< DefNode * > Def
Definition RDFGraph.h:384
NodeAddr< PhiNode * > Phi
Definition RDFGraph.h:390
NodeAddr< UseNode * > Use
Definition RDFGraph.h:385
unsigned getLoopTripCount(const Loop *L, ScalarEvolution &SE, unsigned LoopAwareTripCount)
This is an optimization pass for GlobalISel generic memory operations.
Printable print(const GCNRegPressure &RP, const GCNSubtarget *ST=nullptr, unsigned DynamicVGPRBlockSize=0)
MachineInstrBuilder BuildMI(MachineFunction &MF, const MIMetadata &MIMD, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
RelativeUniformCounterPtr Values
Definition InstrProf.h:91
RegState
Flags to represent properties of register accesses.
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition STLExtras.h:649
constexpr bool isPowerOf2_64(uint64_t Value)
Return true if the argument is a power of two > 0 (64 bit edition.)
Definition MathExtras.h:285
unsigned Log2_32(uint32_t Value)
Return the floor log base 2 of the specified value, -1 if the value is zero.
Definition MathExtras.h:326
MachineInstr * getImm(const MachineOperand &MO, const MachineRegisterInfo *MRI)
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition Debug.cpp:209
FunctionPass * createHexagonHardwareLoops()
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
DomTreeNodeBase< MachineBasicBlock > MachineDomTreeNode
@ Sub
Subtraction of integers.
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Count
Definition InstrProf.h:145
ArrayRef(const T &OneElt) -> ArrayRef< T >
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
Definition STLExtras.h:1963
@ End
Run the machine verifier once, at the end of the pipeline.
Definition CodeGen.h:320
LLVM_ABI Printable printReg(Register Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)
Prints virtual and physical registers with or without a TRI instance.
LLVM_ABI Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
MCRegisterClass TargetRegisterClass
Definition FastISel.h:58
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition BitVector.h:881
#define MORE()
Definition regcomp.c:247