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