LLVM  10.0.0svn
MachineLICM.cpp
Go to the documentation of this file.
1 //===- MachineLICM.cpp - Machine Loop Invariant Code Motion Pass ----------===//
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 performs loop invariant code motion on machine instructions. We
10 // attempt to remove as much code from the body of a loop as possible.
11 //
12 // This pass is not intended to be a replacement or a complete alternative
13 // for the LLVM-IR-level LICM pass. It is only designed to hoist simple
14 // constructs that are not exposed before lowering and instruction selection.
15 //
16 //===----------------------------------------------------------------------===//
17 
18 #include "llvm/ADT/BitVector.h"
19 #include "llvm/ADT/DenseMap.h"
20 #include "llvm/ADT/STLExtras.h"
21 #include "llvm/ADT/SmallSet.h"
22 #include "llvm/ADT/SmallVector.h"
23 #include "llvm/ADT/Statistic.h"
41 #include "llvm/IR/DebugLoc.h"
42 #include "llvm/MC/MCInstrDesc.h"
43 #include "llvm/MC/MCRegisterInfo.h"
44 #include "llvm/Pass.h"
45 #include "llvm/Support/Casting.h"
47 #include "llvm/Support/Debug.h"
49 #include <algorithm>
50 #include <cassert>
51 #include <limits>
52 #include <vector>
53 
54 using namespace llvm;
55 
56 #define DEBUG_TYPE "machinelicm"
57 
58 static cl::opt<bool>
59 AvoidSpeculation("avoid-speculation",
60  cl::desc("MachineLICM should avoid speculation"),
61  cl::init(true), cl::Hidden);
62 
63 static cl::opt<bool>
64 HoistCheapInsts("hoist-cheap-insts",
65  cl::desc("MachineLICM should hoist even cheap instructions"),
66  cl::init(false), cl::Hidden);
67 
68 static cl::opt<bool>
69 SinkInstsToAvoidSpills("sink-insts-to-avoid-spills",
70  cl::desc("MachineLICM should sink instructions into "
71  "loops to avoid register spills"),
72  cl::init(false), cl::Hidden);
73 static cl::opt<bool>
74 HoistConstStores("hoist-const-stores",
75  cl::desc("Hoist invariant stores"),
76  cl::init(true), cl::Hidden);
77 
78 STATISTIC(NumHoisted,
79  "Number of machine instructions hoisted out of loops");
80 STATISTIC(NumLowRP,
81  "Number of instructions hoisted in low reg pressure situation");
82 STATISTIC(NumHighLatency,
83  "Number of high latency instructions hoisted");
84 STATISTIC(NumCSEed,
85  "Number of hoisted machine instructions CSEed");
86 STATISTIC(NumPostRAHoisted,
87  "Number of machine instructions hoisted out of loops post regalloc");
88 STATISTIC(NumStoreConst,
89  "Number of stores of const phys reg hoisted out of loops");
90 
91 namespace {
92 
93  class MachineLICMBase : public MachineFunctionPass {
94  const TargetInstrInfo *TII;
95  const TargetLoweringBase *TLI;
96  const TargetRegisterInfo *TRI;
97  const MachineFrameInfo *MFI;
99  TargetSchedModel SchedModel;
100  bool PreRegAlloc;
101 
102  // Various analyses that we use...
103  AliasAnalysis *AA; // Alias analysis info.
104  MachineLoopInfo *MLI; // Current MachineLoopInfo
105  MachineDominatorTree *DT; // Machine dominator tree for the cur loop
106 
107  // State that is updated as we process loops
108  bool Changed; // True if a loop is changed.
109  bool FirstInLoop; // True if it's the first LICM in the loop.
110  MachineLoop *CurLoop; // The current loop we are working on.
111  MachineBasicBlock *CurPreheader; // The preheader for CurLoop.
112 
113  // Exit blocks for CurLoop.
115 
116  bool isExitBlock(const MachineBasicBlock *MBB) const {
117  return is_contained(ExitBlocks, MBB);
118  }
119 
120  // Track 'estimated' register pressure.
121  SmallSet<unsigned, 32> RegSeen;
123 
124  // Register pressure "limit" per register pressure set. If the pressure
125  // is higher than the limit, then it's considered high.
126  SmallVector<unsigned, 8> RegLimit;
127 
128  // Register pressure on path leading from loop preheader to current BB.
130 
131  // For each opcode, keep a list of potential CSE instructions.
133 
134  enum {
135  SpeculateFalse = 0,
136  SpeculateTrue = 1,
137  SpeculateUnknown = 2
138  };
139 
140  // If a MBB does not dominate loop exiting blocks then it may not safe
141  // to hoist loads from this block.
142  // Tri-state: 0 - false, 1 - true, 2 - unknown
143  unsigned SpeculationState;
144 
145  public:
146  MachineLICMBase(char &PassID, bool PreRegAlloc)
147  : MachineFunctionPass(PassID), PreRegAlloc(PreRegAlloc) {}
148 
149  bool runOnMachineFunction(MachineFunction &MF) override;
150 
151  void getAnalysisUsage(AnalysisUsage &AU) const override {
157  }
158 
159  void releaseMemory() override {
160  RegSeen.clear();
161  RegPressure.clear();
162  RegLimit.clear();
163  BackTrace.clear();
164  CSEMap.clear();
165  }
166 
167  private:
168  /// Keep track of information about hoisting candidates.
169  struct CandidateInfo {
170  MachineInstr *MI;
171  unsigned Def;
172  int FI;
173 
174  CandidateInfo(MachineInstr *mi, unsigned def, int fi)
175  : MI(mi), Def(def), FI(fi) {}
176  };
177 
178  void HoistRegionPostRA();
179 
180  void HoistPostRA(MachineInstr *MI, unsigned Def);
181 
182  void ProcessMI(MachineInstr *MI, BitVector &PhysRegDefs,
183  BitVector &PhysRegClobbers, SmallSet<int, 32> &StoredFIs,
184  SmallVectorImpl<CandidateInfo> &Candidates);
185 
186  void AddToLiveIns(unsigned Reg);
187 
188  bool IsLICMCandidate(MachineInstr &I);
189 
190  bool IsLoopInvariantInst(MachineInstr &I);
191 
192  bool HasLoopPHIUse(const MachineInstr *MI) const;
193 
194  bool HasHighOperandLatency(MachineInstr &MI, unsigned DefIdx,
195  unsigned Reg) const;
196 
197  bool IsCheapInstruction(MachineInstr &MI) const;
198 
199  bool CanCauseHighRegPressure(const DenseMap<unsigned, int> &Cost,
200  bool Cheap);
201 
202  void UpdateBackTraceRegPressure(const MachineInstr *MI);
203 
204  bool IsProfitableToHoist(MachineInstr &MI);
205 
206  bool IsGuaranteedToExecute(MachineBasicBlock *BB);
207 
208  void EnterScope(MachineBasicBlock *MBB);
209 
210  void ExitScope(MachineBasicBlock *MBB);
211 
212  void ExitScopeIfDone(
213  MachineDomTreeNode *Node,
216 
217  void HoistOutOfLoop(MachineDomTreeNode *HeaderN);
218 
219  void HoistRegion(MachineDomTreeNode *N, bool IsHeader);
220 
221  void SinkIntoLoop();
222 
223  void InitRegPressure(MachineBasicBlock *BB);
224 
225  DenseMap<unsigned, int> calcRegisterCost(const MachineInstr *MI,
226  bool ConsiderSeen,
227  bool ConsiderUnseenAsDef);
228 
229  void UpdateRegPressure(const MachineInstr *MI,
230  bool ConsiderUnseenAsDef = false);
231 
232  MachineInstr *ExtractHoistableLoad(MachineInstr *MI);
233 
234  const MachineInstr *
235  LookForDuplicate(const MachineInstr *MI,
236  std::vector<const MachineInstr *> &PrevMIs);
237 
238  bool EliminateCSE(
239  MachineInstr *MI,
240  DenseMap<unsigned, std::vector<const MachineInstr *>>::iterator &CI);
241 
242  bool MayCSE(MachineInstr *MI);
243 
244  bool Hoist(MachineInstr *MI, MachineBasicBlock *Preheader);
245 
246  void InitCSEMap(MachineBasicBlock *BB);
247 
248  MachineBasicBlock *getCurPreheader();
249  };
250 
251  class MachineLICM : public MachineLICMBase {
252  public:
253  static char ID;
254  MachineLICM() : MachineLICMBase(ID, false) {
256  }
257  };
258 
259  class EarlyMachineLICM : public MachineLICMBase {
260  public:
261  static char ID;
262  EarlyMachineLICM() : MachineLICMBase(ID, true) {
264  }
265  };
266 
267 } // end anonymous namespace
268 
269 char MachineLICM::ID;
271 
274 
275 INITIALIZE_PASS_BEGIN(MachineLICM, DEBUG_TYPE,
276  "Machine Loop Invariant Code Motion", false, false)
281  "Machine Loop Invariant Code Motion", false, false)
282 
283 INITIALIZE_PASS_BEGIN(EarlyMachineLICM, "early-machinelicm",
284  "Early Machine Loop Invariant Code Motion", false, false)
288 INITIALIZE_PASS_END(EarlyMachineLICM, "early-machinelicm",
289  "Early Machine Loop Invariant Code Motion", false, false)
290 
291 /// Test if the given loop is the outer-most loop that has a unique predecessor.
293  // Check whether this loop even has a unique predecessor.
294  if (!CurLoop->getLoopPredecessor())
295  return false;
296  // Ok, now check to see if any of its outer loops do.
297  for (MachineLoop *L = CurLoop->getParentLoop(); L; L = L->getParentLoop())
298  if (L->getLoopPredecessor())
299  return false;
300  // None of them did, so this is the outermost with a unique predecessor.
301  return true;
302 }
303 
304 bool MachineLICMBase::runOnMachineFunction(MachineFunction &MF) {
305  if (skipFunction(MF.getFunction()))
306  return false;
307 
308  Changed = FirstInLoop = false;
309  const TargetSubtargetInfo &ST = MF.getSubtarget();
310  TII = ST.getInstrInfo();
311  TLI = ST.getTargetLowering();
312  TRI = ST.getRegisterInfo();
313  MFI = &MF.getFrameInfo();
314  MRI = &MF.getRegInfo();
315  SchedModel.init(&ST);
316 
317  PreRegAlloc = MRI->isSSA();
318 
319  if (PreRegAlloc)
320  LLVM_DEBUG(dbgs() << "******** Pre-regalloc Machine LICM: ");
321  else
322  LLVM_DEBUG(dbgs() << "******** Post-regalloc Machine LICM: ");
323  LLVM_DEBUG(dbgs() << MF.getName() << " ********\n");
324 
325  if (PreRegAlloc) {
326  // Estimate register pressure during pre-regalloc pass.
327  unsigned NumRPS = TRI->getNumRegPressureSets();
328  RegPressure.resize(NumRPS);
329  std::fill(RegPressure.begin(), RegPressure.end(), 0);
330  RegLimit.resize(NumRPS);
331  for (unsigned i = 0, e = NumRPS; i != e; ++i)
332  RegLimit[i] = TRI->getRegPressureSetLimit(MF, i);
333  }
334 
335  // Get our Loop information...
336  MLI = &getAnalysis<MachineLoopInfo>();
337  DT = &getAnalysis<MachineDominatorTree>();
338  AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
339 
340  SmallVector<MachineLoop *, 8> Worklist(MLI->begin(), MLI->end());
341  while (!Worklist.empty()) {
342  CurLoop = Worklist.pop_back_val();
343  CurPreheader = nullptr;
344  ExitBlocks.clear();
345 
346  // If this is done before regalloc, only visit outer-most preheader-sporting
347  // loops.
348  if (PreRegAlloc && !LoopIsOuterMostWithPredecessor(CurLoop)) {
349  Worklist.append(CurLoop->begin(), CurLoop->end());
350  continue;
351  }
352 
353  CurLoop->getExitBlocks(ExitBlocks);
354 
355  if (!PreRegAlloc)
356  HoistRegionPostRA();
357  else {
358  // CSEMap is initialized for loop header when the first instruction is
359  // being hoisted.
360  MachineDomTreeNode *N = DT->getNode(CurLoop->getHeader());
361  FirstInLoop = true;
362  HoistOutOfLoop(N);
363  CSEMap.clear();
364 
366  SinkIntoLoop();
367  }
368  }
369 
370  return Changed;
371 }
372 
373 /// Return true if instruction stores to the specified frame.
374 static bool InstructionStoresToFI(const MachineInstr *MI, int FI) {
375  // Check mayStore before memory operands so that e.g. DBG_VALUEs will return
376  // true since they have no memory operands.
377  if (!MI->mayStore())
378  return false;
379  // If we lost memory operands, conservatively assume that the instruction
380  // writes to all slots.
381  if (MI->memoperands_empty())
382  return true;
383  for (const MachineMemOperand *MemOp : MI->memoperands()) {
384  if (!MemOp->isStore() || !MemOp->getPseudoValue())
385  continue;
387  dyn_cast<FixedStackPseudoSourceValue>(MemOp->getPseudoValue())) {
388  if (Value->getFrameIndex() == FI)
389  return true;
390  }
391  }
392  return false;
393 }
394 
395 /// Examine the instruction for potentai LICM candidate. Also
396 /// gather register def and frame object update information.
397 void MachineLICMBase::ProcessMI(MachineInstr *MI,
398  BitVector &PhysRegDefs,
399  BitVector &PhysRegClobbers,
400  SmallSet<int, 32> &StoredFIs,
401  SmallVectorImpl<CandidateInfo> &Candidates) {
402  bool RuledOut = false;
403  bool HasNonInvariantUse = false;
404  unsigned Def = 0;
405  for (const MachineOperand &MO : MI->operands()) {
406  if (MO.isFI()) {
407  // Remember if the instruction stores to the frame index.
408  int FI = MO.getIndex();
409  if (!StoredFIs.count(FI) &&
410  MFI->isSpillSlotObjectIndex(FI) &&
411  InstructionStoresToFI(MI, FI))
412  StoredFIs.insert(FI);
413  HasNonInvariantUse = true;
414  continue;
415  }
416 
417  // We can't hoist an instruction defining a physreg that is clobbered in
418  // the loop.
419  if (MO.isRegMask()) {
420  PhysRegClobbers.setBitsNotInMask(MO.getRegMask());
421  continue;
422  }
423 
424  if (!MO.isReg())
425  continue;
426  Register Reg = MO.getReg();
427  if (!Reg)
428  continue;
430  "Not expecting virtual register!");
431 
432  if (!MO.isDef()) {
433  if (Reg && (PhysRegDefs.test(Reg) || PhysRegClobbers.test(Reg)))
434  // If it's using a non-loop-invariant register, then it's obviously not
435  // safe to hoist.
436  HasNonInvariantUse = true;
437  continue;
438  }
439 
440  if (MO.isImplicit()) {
441  for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI)
442  PhysRegClobbers.set(*AI);
443  if (!MO.isDead())
444  // Non-dead implicit def? This cannot be hoisted.
445  RuledOut = true;
446  // No need to check if a dead implicit def is also defined by
447  // another instruction.
448  continue;
449  }
450 
451  // FIXME: For now, avoid instructions with multiple defs, unless
452  // it's a dead implicit def.
453  if (Def)
454  RuledOut = true;
455  else
456  Def = Reg;
457 
458  // If we have already seen another instruction that defines the same
459  // register, then this is not safe. Two defs is indicated by setting a
460  // PhysRegClobbers bit.
461  for (MCRegAliasIterator AS(Reg, TRI, true); AS.isValid(); ++AS) {
462  if (PhysRegDefs.test(*AS))
463  PhysRegClobbers.set(*AS);
464  }
465  // Need a second loop because MCRegAliasIterator can visit the same
466  // register twice.
467  for (MCRegAliasIterator AS(Reg, TRI, true); AS.isValid(); ++AS)
468  PhysRegDefs.set(*AS);
469 
470  if (PhysRegClobbers.test(Reg))
471  // MI defined register is seen defined by another instruction in
472  // the loop, it cannot be a LICM candidate.
473  RuledOut = true;
474  }
475 
476  // Only consider reloads for now and remats which do not have register
477  // operands. FIXME: Consider unfold load folding instructions.
478  if (Def && !RuledOut) {
479  int FI = std::numeric_limits<int>::min();
480  if ((!HasNonInvariantUse && IsLICMCandidate(*MI)) ||
481  (TII->isLoadFromStackSlot(*MI, FI) && MFI->isSpillSlotObjectIndex(FI)))
482  Candidates.push_back(CandidateInfo(MI, Def, FI));
483  }
484 }
485 
486 /// Walk the specified region of the CFG and hoist loop invariants out to the
487 /// preheader.
488 void MachineLICMBase::HoistRegionPostRA() {
489  MachineBasicBlock *Preheader = getCurPreheader();
490  if (!Preheader)
491  return;
492 
493  unsigned NumRegs = TRI->getNumRegs();
494  BitVector PhysRegDefs(NumRegs); // Regs defined once in the loop.
495  BitVector PhysRegClobbers(NumRegs); // Regs defined more than once.
496 
498  SmallSet<int, 32> StoredFIs;
499 
500  // Walk the entire region, count number of defs for each register, and
501  // collect potential LICM candidates.
502  for (MachineBasicBlock *BB : CurLoop->getBlocks()) {
503  // If the header of the loop containing this basic block is a landing pad,
504  // then don't try to hoist instructions out of this loop.
505  const MachineLoop *ML = MLI->getLoopFor(BB);
506  if (ML && ML->getHeader()->isEHPad()) continue;
507 
508  // Conservatively treat live-in's as an external def.
509  // FIXME: That means a reload that're reused in successor block(s) will not
510  // be LICM'ed.
511  for (const auto &LI : BB->liveins()) {
512  for (MCRegAliasIterator AI(LI.PhysReg, TRI, true); AI.isValid(); ++AI)
513  PhysRegDefs.set(*AI);
514  }
515 
516  SpeculationState = SpeculateUnknown;
517  for (MachineInstr &MI : *BB)
518  ProcessMI(&MI, PhysRegDefs, PhysRegClobbers, StoredFIs, Candidates);
519  }
520 
521  // Gather the registers read / clobbered by the terminator.
522  BitVector TermRegs(NumRegs);
524  if (TI != Preheader->end()) {
525  for (const MachineOperand &MO : TI->operands()) {
526  if (!MO.isReg())
527  continue;
528  Register Reg = MO.getReg();
529  if (!Reg)
530  continue;
531  for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI)
532  TermRegs.set(*AI);
533  }
534  }
535 
536  // Now evaluate whether the potential candidates qualify.
537  // 1. Check if the candidate defined register is defined by another
538  // instruction in the loop.
539  // 2. If the candidate is a load from stack slot (always true for now),
540  // check if the slot is stored anywhere in the loop.
541  // 3. Make sure candidate def should not clobber
542  // registers read by the terminator. Similarly its def should not be
543  // clobbered by the terminator.
544  for (CandidateInfo &Candidate : Candidates) {
545  if (Candidate.FI != std::numeric_limits<int>::min() &&
546  StoredFIs.count(Candidate.FI))
547  continue;
548 
549  unsigned Def = Candidate.Def;
550  if (!PhysRegClobbers.test(Def) && !TermRegs.test(Def)) {
551  bool Safe = true;
552  MachineInstr *MI = Candidate.MI;
553  for (const MachineOperand &MO : MI->operands()) {
554  if (!MO.isReg() || MO.isDef() || !MO.getReg())
555  continue;
556  Register Reg = MO.getReg();
557  if (PhysRegDefs.test(Reg) ||
558  PhysRegClobbers.test(Reg)) {
559  // If it's using a non-loop-invariant register, then it's obviously
560  // not safe to hoist.
561  Safe = false;
562  break;
563  }
564  }
565  if (Safe)
566  HoistPostRA(MI, Candidate.Def);
567  }
568  }
569 }
570 
571 /// Add register 'Reg' to the livein sets of BBs in the current loop, and make
572 /// sure it is not killed by any instructions in the loop.
573 void MachineLICMBase::AddToLiveIns(unsigned Reg) {
574  for (MachineBasicBlock *BB : CurLoop->getBlocks()) {
575  if (!BB->isLiveIn(Reg))
576  BB->addLiveIn(Reg);
577  for (MachineInstr &MI : *BB) {
578  for (MachineOperand &MO : MI.operands()) {
579  if (!MO.isReg() || !MO.getReg() || MO.isDef()) continue;
580  if (MO.getReg() == Reg || TRI->isSuperRegister(Reg, MO.getReg()))
581  MO.setIsKill(false);
582  }
583  }
584  }
585 }
586 
587 /// When an instruction is found to only use loop invariant operands that is
588 /// safe to hoist, this instruction is called to do the dirty work.
589 void MachineLICMBase::HoistPostRA(MachineInstr *MI, unsigned Def) {
590  MachineBasicBlock *Preheader = getCurPreheader();
591 
592  // Now move the instructions to the predecessor, inserting it before any
593  // terminator instructions.
594  LLVM_DEBUG(dbgs() << "Hoisting to " << printMBBReference(*Preheader)
595  << " from " << printMBBReference(*MI->getParent()) << ": "
596  << *MI);
597 
598  // Splice the instruction to the preheader.
599  MachineBasicBlock *MBB = MI->getParent();
600  Preheader->splice(Preheader->getFirstTerminator(), MBB, MI);
601 
602  // Add register to livein list to all the BBs in the current loop since a
603  // loop invariant must be kept live throughout the whole loop. This is
604  // important to ensure later passes do not scavenge the def register.
605  AddToLiveIns(Def);
606 
607  ++NumPostRAHoisted;
608  Changed = true;
609 }
610 
611 /// Check if this mbb is guaranteed to execute. If not then a load from this mbb
612 /// may not be safe to hoist.
613 bool MachineLICMBase::IsGuaranteedToExecute(MachineBasicBlock *BB) {
614  if (SpeculationState != SpeculateUnknown)
615  return SpeculationState == SpeculateFalse;
616 
617  if (BB != CurLoop->getHeader()) {
618  // Check loop exiting blocks.
619  SmallVector<MachineBasicBlock*, 8> CurrentLoopExitingBlocks;
620  CurLoop->getExitingBlocks(CurrentLoopExitingBlocks);
621  for (MachineBasicBlock *CurrentLoopExitingBlock : CurrentLoopExitingBlocks)
622  if (!DT->dominates(BB, CurrentLoopExitingBlock)) {
623  SpeculationState = SpeculateTrue;
624  return false;
625  }
626  }
627 
628  SpeculationState = SpeculateFalse;
629  return true;
630 }
631 
632 void MachineLICMBase::EnterScope(MachineBasicBlock *MBB) {
633  LLVM_DEBUG(dbgs() << "Entering " << printMBBReference(*MBB) << '\n');
634 
635  // Remember livein register pressure.
636  BackTrace.push_back(RegPressure);
637 }
638 
639 void MachineLICMBase::ExitScope(MachineBasicBlock *MBB) {
640  LLVM_DEBUG(dbgs() << "Exiting " << printMBBReference(*MBB) << '\n');
641  BackTrace.pop_back();
642 }
643 
644 /// Destroy scope for the MBB that corresponds to the given dominator tree node
645 /// if its a leaf or all of its children are done. Walk up the dominator tree to
646 /// destroy ancestors which are now done.
647 void MachineLICMBase::ExitScopeIfDone(MachineDomTreeNode *Node,
650  if (OpenChildren[Node])
651  return;
652 
653  // Pop scope.
654  ExitScope(Node->getBlock());
655 
656  // Now traverse upwards to pop ancestors whose offsprings are all done.
657  while (MachineDomTreeNode *Parent = ParentMap[Node]) {
658  unsigned Left = --OpenChildren[Parent];
659  if (Left != 0)
660  break;
661  ExitScope(Parent->getBlock());
662  Node = Parent;
663  }
664 }
665 
666 /// Walk the specified loop in the CFG (defined by all blocks dominated by the
667 /// specified header block, and that are in the current loop) in depth first
668 /// order w.r.t the DominatorTree. This allows us to visit definitions before
669 /// uses, allowing us to hoist a loop body in one pass without iteration.
670 void MachineLICMBase::HoistOutOfLoop(MachineDomTreeNode *HeaderN) {
671  MachineBasicBlock *Preheader = getCurPreheader();
672  if (!Preheader)
673  return;
674 
679 
680  // Perform a DFS walk to determine the order of visit.
681  WorkList.push_back(HeaderN);
682  while (!WorkList.empty()) {
683  MachineDomTreeNode *Node = WorkList.pop_back_val();
684  assert(Node && "Null dominator tree node?");
685  MachineBasicBlock *BB = Node->getBlock();
686 
687  // If the header of the loop containing this basic block is a landing pad,
688  // then don't try to hoist instructions out of this loop.
689  const MachineLoop *ML = MLI->getLoopFor(BB);
690  if (ML && ML->getHeader()->isEHPad())
691  continue;
692 
693  // If this subregion is not in the top level loop at all, exit.
694  if (!CurLoop->contains(BB))
695  continue;
696 
697  Scopes.push_back(Node);
698  const std::vector<MachineDomTreeNode*> &Children = Node->getChildren();
699  unsigned NumChildren = Children.size();
700 
701  // Don't hoist things out of a large switch statement. This often causes
702  // code to be hoisted that wasn't going to be executed, and increases
703  // register pressure in a situation where it's likely to matter.
704  if (BB->succ_size() >= 25)
705  NumChildren = 0;
706 
707  OpenChildren[Node] = NumChildren;
708  // Add children in reverse order as then the next popped worklist node is
709  // the first child of this node. This means we ultimately traverse the
710  // DOM tree in exactly the same order as if we'd recursed.
711  for (int i = (int)NumChildren-1; i >= 0; --i) {
712  MachineDomTreeNode *Child = Children[i];
713  ParentMap[Child] = Node;
714  WorkList.push_back(Child);
715  }
716  }
717 
718  if (Scopes.size() == 0)
719  return;
720 
721  // Compute registers which are livein into the loop headers.
722  RegSeen.clear();
723  BackTrace.clear();
724  InitRegPressure(Preheader);
725 
726  // Now perform LICM.
727  for (MachineDomTreeNode *Node : Scopes) {
728  MachineBasicBlock *MBB = Node->getBlock();
729 
730  EnterScope(MBB);
731 
732  // Process the block
733  SpeculationState = SpeculateUnknown;
735  MII = MBB->begin(), E = MBB->end(); MII != E; ) {
736  MachineBasicBlock::iterator NextMII = MII; ++NextMII;
737  MachineInstr *MI = &*MII;
738  if (!Hoist(MI, Preheader))
739  UpdateRegPressure(MI);
740  // If we have hoisted an instruction that may store, it can only be a
741  // constant store.
742  MII = NextMII;
743  }
744 
745  // If it's a leaf node, it's done. Traverse upwards to pop ancestors.
746  ExitScopeIfDone(Node, OpenChildren, ParentMap);
747  }
748 }
749 
750 /// Sink instructions into loops if profitable. This especially tries to prevent
751 /// register spills caused by register pressure if there is little to no
752 /// overhead moving instructions into loops.
753 void MachineLICMBase::SinkIntoLoop() {
754  MachineBasicBlock *Preheader = getCurPreheader();
755  if (!Preheader)
756  return;
757 
759  for (MachineBasicBlock::instr_iterator I = Preheader->instr_begin();
760  I != Preheader->instr_end(); ++I) {
761  // We need to ensure that we can safely move this instruction into the loop.
762  // As such, it must not have side-effects, e.g. such as a call has.
763  if (IsLoopInvariantInst(*I) && !HasLoopPHIUse(&*I))
764  Candidates.push_back(&*I);
765  }
766 
767  for (MachineInstr *I : Candidates) {
768  const MachineOperand &MO = I->getOperand(0);
769  if (!MO.isDef() || !MO.isReg() || !MO.getReg())
770  continue;
771  if (!MRI->hasOneDef(MO.getReg()))
772  continue;
773  bool CanSink = true;
774  MachineBasicBlock *B = nullptr;
775  for (MachineInstr &MI : MRI->use_instructions(MO.getReg())) {
776  // FIXME: Come up with a proper cost model that estimates whether sinking
777  // the instruction (and thus possibly executing it on every loop
778  // iteration) is more expensive than a register.
779  // For now assumes that copies are cheap and thus almost always worth it.
780  if (!MI.isCopy()) {
781  CanSink = false;
782  break;
783  }
784  if (!B) {
785  B = MI.getParent();
786  continue;
787  }
788  B = DT->findNearestCommonDominator(B, MI.getParent());
789  if (!B) {
790  CanSink = false;
791  break;
792  }
793  }
794  if (!CanSink || !B || B == Preheader)
795  continue;
796  B->splice(B->getFirstNonPHI(), Preheader, I);
797  }
798 }
799 
800 static bool isOperandKill(const MachineOperand &MO, MachineRegisterInfo *MRI) {
801  return MO.isKill() || MRI->hasOneNonDBGUse(MO.getReg());
802 }
803 
804 /// Find all virtual register references that are liveout of the preheader to
805 /// initialize the starting "register pressure". Note this does not count live
806 /// through (livein but not used) registers.
807 void MachineLICMBase::InitRegPressure(MachineBasicBlock *BB) {
808  std::fill(RegPressure.begin(), RegPressure.end(), 0);
809 
810  // If the preheader has only a single predecessor and it ends with a
811  // fallthrough or an unconditional branch, then scan its predecessor for live
812  // defs as well. This happens whenever the preheader is created by splitting
813  // the critical edge from the loop predecessor to the loop header.
814  if (BB->pred_size() == 1) {
815  MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
817  if (!TII->analyzeBranch(*BB, TBB, FBB, Cond, false) && Cond.empty())
818  InitRegPressure(*BB->pred_begin());
819  }
820 
821  for (const MachineInstr &MI : *BB)
822  UpdateRegPressure(&MI, /*ConsiderUnseenAsDef=*/true);
823 }
824 
825 /// Update estimate of register pressure after the specified instruction.
826 void MachineLICMBase::UpdateRegPressure(const MachineInstr *MI,
827  bool ConsiderUnseenAsDef) {
828  auto Cost = calcRegisterCost(MI, /*ConsiderSeen=*/true, ConsiderUnseenAsDef);
829  for (const auto &RPIdAndCost : Cost) {
830  unsigned Class = RPIdAndCost.first;
831  if (static_cast<int>(RegPressure[Class]) < -RPIdAndCost.second)
832  RegPressure[Class] = 0;
833  else
834  RegPressure[Class] += RPIdAndCost.second;
835  }
836 }
837 
838 /// Calculate the additional register pressure that the registers used in MI
839 /// cause.
840 ///
841 /// If 'ConsiderSeen' is true, updates 'RegSeen' and uses the information to
842 /// figure out which usages are live-ins.
843 /// FIXME: Figure out a way to consider 'RegSeen' from all code paths.
845 MachineLICMBase::calcRegisterCost(const MachineInstr *MI, bool ConsiderSeen,
846  bool ConsiderUnseenAsDef) {
848  if (MI->isImplicitDef())
849  return Cost;
850  for (unsigned i = 0, e = MI->getDesc().getNumOperands(); i != e; ++i) {
851  const MachineOperand &MO = MI->getOperand(i);
852  if (!MO.isReg() || MO.isImplicit())
853  continue;
854  Register Reg = MO.getReg();
855  if (!Register::isVirtualRegister(Reg))
856  continue;
857 
858  // FIXME: It seems bad to use RegSeen only for some of these calculations.
859  bool isNew = ConsiderSeen ? RegSeen.insert(Reg).second : false;
860  const TargetRegisterClass *RC = MRI->getRegClass(Reg);
861 
863  int RCCost = 0;
864  if (MO.isDef())
865  RCCost = W.RegWeight;
866  else {
867  bool isKill = isOperandKill(MO, MRI);
868  if (isNew && !isKill && ConsiderUnseenAsDef)
869  // Haven't seen this, it must be a livein.
870  RCCost = W.RegWeight;
871  else if (!isNew && isKill)
872  RCCost = -W.RegWeight;
873  }
874  if (RCCost == 0)
875  continue;
876  const int *PS = TRI->getRegClassPressureSets(RC);
877  for (; *PS != -1; ++PS) {
878  if (Cost.find(*PS) == Cost.end())
879  Cost[*PS] = RCCost;
880  else
881  Cost[*PS] += RCCost;
882  }
883  }
884  return Cost;
885 }
886 
887 /// Return true if this machine instruction loads from global offset table or
888 /// constant pool.
890  assert(MI.mayLoad() && "Expected MI that loads!");
891 
892  // If we lost memory operands, conservatively assume that the instruction
893  // reads from everything..
894  if (MI.memoperands_empty())
895  return true;
896 
897  for (MachineMemOperand *MemOp : MI.memoperands())
898  if (const PseudoSourceValue *PSV = MemOp->getPseudoValue())
899  if (PSV->isGOT() || PSV->isConstantPool())
900  return true;
901 
902  return false;
903 }
904 
905 // This function iterates through all the operands of the input store MI and
906 // checks that each register operand statisfies isCallerPreservedPhysReg.
907 // This means, the value being stored and the address where it is being stored
908 // is constant throughout the body of the function (not including prologue and
909 // epilogue). When called with an MI that isn't a store, it returns false.
910 // A future improvement can be to check if the store registers are constant
911 // throughout the loop rather than throughout the funtion.
912 static bool isInvariantStore(const MachineInstr &MI,
913  const TargetRegisterInfo *TRI,
914  const MachineRegisterInfo *MRI) {
915 
916  bool FoundCallerPresReg = false;
917  if (!MI.mayStore() || MI.hasUnmodeledSideEffects() ||
918  (MI.getNumOperands() == 0))
919  return false;
920 
921  // Check that all register operands are caller-preserved physical registers.
922  for (const MachineOperand &MO : MI.operands()) {
923  if (MO.isReg()) {
924  Register Reg = MO.getReg();
925  // If operand is a virtual register, check if it comes from a copy of a
926  // physical register.
928  Reg = TRI->lookThruCopyLike(MO.getReg(), MRI);
930  return false;
931  if (!TRI->isCallerPreservedPhysReg(Reg, *MI.getMF()))
932  return false;
933  else
934  FoundCallerPresReg = true;
935  } else if (!MO.isImm()) {
936  return false;
937  }
938  }
939  return FoundCallerPresReg;
940 }
941 
942 // Return true if the input MI is a copy instruction that feeds an invariant
943 // store instruction. This means that the src of the copy has to satisfy
944 // isCallerPreservedPhysReg and atleast one of it's users should satisfy
945 // isInvariantStore.
947  const MachineRegisterInfo *MRI,
948  const TargetRegisterInfo *TRI) {
949 
950  // FIXME: If targets would like to look through instructions that aren't
951  // pure copies, this can be updated to a query.
952  if (!MI.isCopy())
953  return false;
954 
955  const MachineFunction *MF = MI.getMF();
956  // Check that we are copying a constant physical register.
957  Register CopySrcReg = MI.getOperand(1).getReg();
958  if (Register::isVirtualRegister(CopySrcReg))
959  return false;
960 
961  if (!TRI->isCallerPreservedPhysReg(CopySrcReg, *MF))
962  return false;
963 
964  Register CopyDstReg = MI.getOperand(0).getReg();
965  // Check if any of the uses of the copy are invariant stores.
966  assert(Register::isVirtualRegister(CopyDstReg) &&
967  "copy dst is not a virtual reg");
968 
969  for (MachineInstr &UseMI : MRI->use_instructions(CopyDstReg)) {
970  if (UseMI.mayStore() && isInvariantStore(UseMI, TRI, MRI))
971  return true;
972  }
973  return false;
974 }
975 
976 /// Returns true if the instruction may be a suitable candidate for LICM.
977 /// e.g. If the instruction is a call, then it's obviously not safe to hoist it.
978 bool MachineLICMBase::IsLICMCandidate(MachineInstr &I) {
979  // Check if it's safe to move the instruction.
980  bool DontMoveAcrossStore = true;
981  if ((!I.isSafeToMove(AA, DontMoveAcrossStore)) &&
982  !(HoistConstStores && isInvariantStore(I, TRI, MRI))) {
983  return false;
984  }
985 
986  // If it is load then check if it is guaranteed to execute by making sure that
987  // it dominates all exiting blocks. If it doesn't, then there is a path out of
988  // the loop which does not execute this load, so we can't hoist it. Loads
989  // from constant memory are not safe to speculate all the time, for example
990  // indexed load from a jump table.
991  // Stores and side effects are already checked by isSafeToMove.
992  if (I.mayLoad() && !mayLoadFromGOTOrConstantPool(I) &&
993  !IsGuaranteedToExecute(I.getParent()))
994  return false;
995 
996  return true;
997 }
998 
999 /// Returns true if the instruction is loop invariant.
1000 /// I.e., all virtual register operands are defined outside of the loop,
1001 /// physical registers aren't accessed explicitly, and there are no side
1002 /// effects that aren't captured by the operands or other flags.
1003 bool MachineLICMBase::IsLoopInvariantInst(MachineInstr &I) {
1004  if (!IsLICMCandidate(I))
1005  return false;
1006 
1007  // The instruction is loop invariant if all of its operands are.
1008  for (const MachineOperand &MO : I.operands()) {
1009  if (!MO.isReg())
1010  continue;
1011 
1012  Register Reg = MO.getReg();
1013  if (Reg == 0) continue;
1014 
1015  // Don't hoist an instruction that uses or defines a physical register.
1016  if (Register::isPhysicalRegister(Reg)) {
1017  if (MO.isUse()) {
1018  // If the physreg has no defs anywhere, it's just an ambient register
1019  // and we can freely move its uses. Alternatively, if it's allocatable,
1020  // it could get allocated to something with a def during allocation.
1021  // However, if the physreg is known to always be caller saved/restored
1022  // then this use is safe to hoist.
1023  if (!MRI->isConstantPhysReg(Reg) &&
1024  !(TRI->isCallerPreservedPhysReg(Reg, *I.getMF())))
1025  return false;
1026  // Otherwise it's safe to move.
1027  continue;
1028  } else if (!MO.isDead()) {
1029  // A def that isn't dead. We can't move it.
1030  return false;
1031  } else if (CurLoop->getHeader()->isLiveIn(Reg)) {
1032  // If the reg is live into the loop, we can't hoist an instruction
1033  // which would clobber it.
1034  return false;
1035  }
1036  }
1037 
1038  if (!MO.isUse())
1039  continue;
1040 
1041  assert(MRI->getVRegDef(Reg) &&
1042  "Machine instr not mapped for this vreg?!");
1043 
1044  // If the loop contains the definition of an operand, then the instruction
1045  // isn't loop invariant.
1046  if (CurLoop->contains(MRI->getVRegDef(Reg)))
1047  return false;
1048  }
1049 
1050  // If we got this far, the instruction is loop invariant!
1051  return true;
1052 }
1053 
1054 /// Return true if the specified instruction is used by a phi node and hoisting
1055 /// it could cause a copy to be inserted.
1056 bool MachineLICMBase::HasLoopPHIUse(const MachineInstr *MI) const {
1058  do {
1059  MI = Work.pop_back_val();
1060  for (const MachineOperand &MO : MI->operands()) {
1061  if (!MO.isReg() || !MO.isDef())
1062  continue;
1063  Register Reg = MO.getReg();
1064  if (!Register::isVirtualRegister(Reg))
1065  continue;
1066  for (MachineInstr &UseMI : MRI->use_instructions(Reg)) {
1067  // A PHI may cause a copy to be inserted.
1068  if (UseMI.isPHI()) {
1069  // A PHI inside the loop causes a copy because the live range of Reg is
1070  // extended across the PHI.
1071  if (CurLoop->contains(&UseMI))
1072  return true;
1073  // A PHI in an exit block can cause a copy to be inserted if the PHI
1074  // has multiple predecessors in the loop with different values.
1075  // For now, approximate by rejecting all exit blocks.
1076  if (isExitBlock(UseMI.getParent()))
1077  return true;
1078  continue;
1079  }
1080  // Look past copies as well.
1081  if (UseMI.isCopy() && CurLoop->contains(&UseMI))
1082  Work.push_back(&UseMI);
1083  }
1084  }
1085  } while (!Work.empty());
1086  return false;
1087 }
1088 
1089 /// Compute operand latency between a def of 'Reg' and an use in the current
1090 /// loop, return true if the target considered it high.
1091 bool MachineLICMBase::HasHighOperandLatency(MachineInstr &MI,
1092  unsigned DefIdx,
1093  unsigned Reg) const {
1094  if (MRI->use_nodbg_empty(Reg))
1095  return false;
1096 
1097  for (MachineInstr &UseMI : MRI->use_nodbg_instructions(Reg)) {
1098  if (UseMI.isCopyLike())
1099  continue;
1100  if (!CurLoop->contains(UseMI.getParent()))
1101  continue;
1102  for (unsigned i = 0, e = UseMI.getNumOperands(); i != e; ++i) {
1103  const MachineOperand &MO = UseMI.getOperand(i);
1104  if (!MO.isReg() || !MO.isUse())
1105  continue;
1106  Register MOReg = MO.getReg();
1107  if (MOReg != Reg)
1108  continue;
1109 
1110  if (TII->hasHighOperandLatency(SchedModel, MRI, MI, DefIdx, UseMI, i))
1111  return true;
1112  }
1113 
1114  // Only look at the first in loop use.
1115  break;
1116  }
1117 
1118  return false;
1119 }
1120 
1121 /// Return true if the instruction is marked "cheap" or the operand latency
1122 /// between its def and a use is one or less.
1123 bool MachineLICMBase::IsCheapInstruction(MachineInstr &MI) const {
1124  if (TII->isAsCheapAsAMove(MI) || MI.isCopyLike())
1125  return true;
1126 
1127  bool isCheap = false;
1128  unsigned NumDefs = MI.getDesc().getNumDefs();
1129  for (unsigned i = 0, e = MI.getNumOperands(); NumDefs && i != e; ++i) {
1130  MachineOperand &DefMO = MI.getOperand(i);
1131  if (!DefMO.isReg() || !DefMO.isDef())
1132  continue;
1133  --NumDefs;
1134  Register Reg = DefMO.getReg();
1136  continue;
1137 
1138  if (!TII->hasLowDefLatency(SchedModel, MI, i))
1139  return false;
1140  isCheap = true;
1141  }
1142 
1143  return isCheap;
1144 }
1145 
1146 /// Visit BBs from header to current BB, check if hoisting an instruction of the
1147 /// given cost matrix can cause high register pressure.
1148 bool
1149 MachineLICMBase::CanCauseHighRegPressure(const DenseMap<unsigned, int>& Cost,
1150  bool CheapInstr) {
1151  for (const auto &RPIdAndCost : Cost) {
1152  if (RPIdAndCost.second <= 0)
1153  continue;
1154 
1155  unsigned Class = RPIdAndCost.first;
1156  int Limit = RegLimit[Class];
1157 
1158  // Don't hoist cheap instructions if they would increase register pressure,
1159  // even if we're under the limit.
1160  if (CheapInstr && !HoistCheapInsts)
1161  return true;
1162 
1163  for (const auto &RP : BackTrace)
1164  if (static_cast<int>(RP[Class]) + RPIdAndCost.second >= Limit)
1165  return true;
1166  }
1167 
1168  return false;
1169 }
1170 
1171 /// Traverse the back trace from header to the current block and update their
1172 /// register pressures to reflect the effect of hoisting MI from the current
1173 /// block to the preheader.
1174 void MachineLICMBase::UpdateBackTraceRegPressure(const MachineInstr *MI) {
1175  // First compute the 'cost' of the instruction, i.e. its contribution
1176  // to register pressure.
1177  auto Cost = calcRegisterCost(MI, /*ConsiderSeen=*/false,
1178  /*ConsiderUnseenAsDef=*/false);
1179 
1180  // Update register pressure of blocks from loop header to current block.
1181  for (auto &RP : BackTrace)
1182  for (const auto &RPIdAndCost : Cost)
1183  RP[RPIdAndCost.first] += RPIdAndCost.second;
1184 }
1185 
1186 /// Return true if it is potentially profitable to hoist the given loop
1187 /// invariant.
1188 bool MachineLICMBase::IsProfitableToHoist(MachineInstr &MI) {
1189  if (MI.isImplicitDef())
1190  return true;
1191 
1192  // Besides removing computation from the loop, hoisting an instruction has
1193  // these effects:
1194  //
1195  // - The value defined by the instruction becomes live across the entire
1196  // loop. This increases register pressure in the loop.
1197  //
1198  // - If the value is used by a PHI in the loop, a copy will be required for
1199  // lowering the PHI after extending the live range.
1200  //
1201  // - When hoisting the last use of a value in the loop, that value no longer
1202  // needs to be live in the loop. This lowers register pressure in the loop.
1203 
1204  if (HoistConstStores && isCopyFeedingInvariantStore(MI, MRI, TRI))
1205  return true;
1206 
1207  bool CheapInstr = IsCheapInstruction(MI);
1208  bool CreatesCopy = HasLoopPHIUse(&MI);
1209 
1210  // Don't hoist a cheap instruction if it would create a copy in the loop.
1211  if (CheapInstr && CreatesCopy) {
1212  LLVM_DEBUG(dbgs() << "Won't hoist cheap instr with loop PHI use: " << MI);
1213  return false;
1214  }
1215 
1216  // Rematerializable instructions should always be hoisted since the register
1217  // allocator can just pull them down again when needed.
1218  if (TII->isTriviallyReMaterializable(MI, AA))
1219  return true;
1220 
1221  // FIXME: If there are long latency loop-invariant instructions inside the
1222  // loop at this point, why didn't the optimizer's LICM hoist them?
1223  for (unsigned i = 0, e = MI.getDesc().getNumOperands(); i != e; ++i) {
1224  const MachineOperand &MO = MI.getOperand(i);
1225  if (!MO.isReg() || MO.isImplicit())
1226  continue;
1227  Register Reg = MO.getReg();
1228  if (!Register::isVirtualRegister(Reg))
1229  continue;
1230  if (MO.isDef() && HasHighOperandLatency(MI, i, Reg)) {
1231  LLVM_DEBUG(dbgs() << "Hoist High Latency: " << MI);
1232  ++NumHighLatency;
1233  return true;
1234  }
1235  }
1236 
1237  // Estimate register pressure to determine whether to LICM the instruction.
1238  // In low register pressure situation, we can be more aggressive about
1239  // hoisting. Also, favors hoisting long latency instructions even in
1240  // moderately high pressure situation.
1241  // Cheap instructions will only be hoisted if they don't increase register
1242  // pressure at all.
1243  auto Cost = calcRegisterCost(&MI, /*ConsiderSeen=*/false,
1244  /*ConsiderUnseenAsDef=*/false);
1245 
1246  // Visit BBs from header to current BB, if hoisting this doesn't cause
1247  // high register pressure, then it's safe to proceed.
1248  if (!CanCauseHighRegPressure(Cost, CheapInstr)) {
1249  LLVM_DEBUG(dbgs() << "Hoist non-reg-pressure: " << MI);
1250  ++NumLowRP;
1251  return true;
1252  }
1253 
1254  // Don't risk increasing register pressure if it would create copies.
1255  if (CreatesCopy) {
1256  LLVM_DEBUG(dbgs() << "Won't hoist instr with loop PHI use: " << MI);
1257  return false;
1258  }
1259 
1260  // Do not "speculate" in high register pressure situation. If an
1261  // instruction is not guaranteed to be executed in the loop, it's best to be
1262  // conservative.
1263  if (AvoidSpeculation &&
1264  (!IsGuaranteedToExecute(MI.getParent()) && !MayCSE(&MI))) {
1265  LLVM_DEBUG(dbgs() << "Won't speculate: " << MI);
1266  return false;
1267  }
1268 
1269  // High register pressure situation, only hoist if the instruction is going
1270  // to be remat'ed.
1271  if (!TII->isTriviallyReMaterializable(MI, AA) &&
1273  LLVM_DEBUG(dbgs() << "Can't remat / high reg-pressure: " << MI);
1274  return false;
1275  }
1276 
1277  return true;
1278 }
1279 
1280 /// Unfold a load from the given machineinstr if the load itself could be
1281 /// hoisted. Return the unfolded and hoistable load, or null if the load
1282 /// couldn't be unfolded or if it wouldn't be hoistable.
1283 MachineInstr *MachineLICMBase::ExtractHoistableLoad(MachineInstr *MI) {
1284  // Don't unfold simple loads.
1285  if (MI->canFoldAsLoad())
1286  return nullptr;
1287 
1288  // If not, we may be able to unfold a load and hoist that.
1289  // First test whether the instruction is loading from an amenable
1290  // memory location.
1291  if (!MI->isDereferenceableInvariantLoad(AA))
1292  return nullptr;
1293 
1294  // Next determine the register class for a temporary register.
1295  unsigned LoadRegIndex;
1296  unsigned NewOpc =
1298  /*UnfoldLoad=*/true,
1299  /*UnfoldStore=*/false,
1300  &LoadRegIndex);
1301  if (NewOpc == 0) return nullptr;
1302  const MCInstrDesc &MID = TII->get(NewOpc);
1303  MachineFunction &MF = *MI->getMF();
1304  const TargetRegisterClass *RC = TII->getRegClass(MID, LoadRegIndex, TRI, MF);
1305  // Ok, we're unfolding. Create a temporary register and do the unfold.
1306  Register Reg = MRI->createVirtualRegister(RC);
1307 
1309  bool Success = TII->unfoldMemoryOperand(MF, *MI, Reg,
1310  /*UnfoldLoad=*/true,
1311  /*UnfoldStore=*/false, NewMIs);
1312  (void)Success;
1313  assert(Success &&
1314  "unfoldMemoryOperand failed when getOpcodeAfterMemoryUnfold "
1315  "succeeded!");
1316  assert(NewMIs.size() == 2 &&
1317  "Unfolded a load into multiple instructions!");
1318  MachineBasicBlock *MBB = MI->getParent();
1320  MBB->insert(Pos, NewMIs[0]);
1321  MBB->insert(Pos, NewMIs[1]);
1322  // If unfolding produced a load that wasn't loop-invariant or profitable to
1323  // hoist, discard the new instructions and bail.
1324  if (!IsLoopInvariantInst(*NewMIs[0]) || !IsProfitableToHoist(*NewMIs[0])) {
1325  NewMIs[0]->eraseFromParent();
1326  NewMIs[1]->eraseFromParent();
1327  return nullptr;
1328  }
1329 
1330  // Update register pressure for the unfolded instruction.
1331  UpdateRegPressure(NewMIs[1]);
1332 
1333  // Otherwise we successfully unfolded a load that we can hoist.
1334  MI->eraseFromParent();
1335  return NewMIs[0];
1336 }
1337 
1338 /// Initialize the CSE map with instructions that are in the current loop
1339 /// preheader that may become duplicates of instructions that are hoisted
1340 /// out of the loop.
1341 void MachineLICMBase::InitCSEMap(MachineBasicBlock *BB) {
1342  for (MachineInstr &MI : *BB)
1343  CSEMap[MI.getOpcode()].push_back(&MI);
1344 }
1345 
1346 /// Find an instruction amount PrevMIs that is a duplicate of MI.
1347 /// Return this instruction if it's found.
1348 const MachineInstr*
1349 MachineLICMBase::LookForDuplicate(const MachineInstr *MI,
1350  std::vector<const MachineInstr*> &PrevMIs) {
1351  for (const MachineInstr *PrevMI : PrevMIs)
1352  if (TII->produceSameValue(*MI, *PrevMI, (PreRegAlloc ? MRI : nullptr)))
1353  return PrevMI;
1354 
1355  return nullptr;
1356 }
1357 
1358 /// Given a LICM'ed instruction, look for an instruction on the preheader that
1359 /// computes the same value. If it's found, do a RAU on with the definition of
1360 /// the existing instruction rather than hoisting the instruction to the
1361 /// preheader.
1362 bool MachineLICMBase::EliminateCSE(MachineInstr *MI,
1363  DenseMap<unsigned, std::vector<const MachineInstr *>>::iterator &CI) {
1364  // Do not CSE implicit_def so ProcessImplicitDefs can properly propagate
1365  // the undef property onto uses.
1366  if (CI == CSEMap.end() || MI->isImplicitDef())
1367  return false;
1368 
1369  if (const MachineInstr *Dup = LookForDuplicate(MI, CI->second)) {
1370  LLVM_DEBUG(dbgs() << "CSEing " << *MI << " with " << *Dup);
1371 
1372  // Replace virtual registers defined by MI by their counterparts defined
1373  // by Dup.
1375  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
1376  const MachineOperand &MO = MI->getOperand(i);
1377 
1378  // Physical registers may not differ here.
1379  assert((!MO.isReg() || MO.getReg() == 0 ||
1381  MO.getReg() == Dup->getOperand(i).getReg()) &&
1382  "Instructions with different phys regs are not identical!");
1383 
1384  if (MO.isReg() && MO.isDef() &&
1386  Defs.push_back(i);
1387  }
1388 
1390  for (unsigned i = 0, e = Defs.size(); i != e; ++i) {
1391  unsigned Idx = Defs[i];
1392  Register Reg = MI->getOperand(Idx).getReg();
1393  Register DupReg = Dup->getOperand(Idx).getReg();
1394  OrigRCs.push_back(MRI->getRegClass(DupReg));
1395 
1396  if (!MRI->constrainRegClass(DupReg, MRI->getRegClass(Reg))) {
1397  // Restore old RCs if more than one defs.
1398  for (unsigned j = 0; j != i; ++j)
1399  MRI->setRegClass(Dup->getOperand(Defs[j]).getReg(), OrigRCs[j]);
1400  return false;
1401  }
1402  }
1403 
1404  for (unsigned Idx : Defs) {
1405  Register Reg = MI->getOperand(Idx).getReg();
1406  Register DupReg = Dup->getOperand(Idx).getReg();
1407  MRI->replaceRegWith(Reg, DupReg);
1408  MRI->clearKillFlags(DupReg);
1409  }
1410 
1411  MI->eraseFromParent();
1412  ++NumCSEed;
1413  return true;
1414  }
1415  return false;
1416 }
1417 
1418 /// Return true if the given instruction will be CSE'd if it's hoisted out of
1419 /// the loop.
1420 bool MachineLICMBase::MayCSE(MachineInstr *MI) {
1421  unsigned Opcode = MI->getOpcode();
1423  CI = CSEMap.find(Opcode);
1424  // Do not CSE implicit_def so ProcessImplicitDefs can properly propagate
1425  // the undef property onto uses.
1426  if (CI == CSEMap.end() || MI->isImplicitDef())
1427  return false;
1428 
1429  return LookForDuplicate(MI, CI->second) != nullptr;
1430 }
1431 
1432 /// When an instruction is found to use only loop invariant operands
1433 /// that are safe to hoist, this instruction is called to do the dirty work.
1434 /// It returns true if the instruction is hoisted.
1435 bool MachineLICMBase::Hoist(MachineInstr *MI, MachineBasicBlock *Preheader) {
1436  // First check whether we should hoist this instruction.
1437  if (!IsLoopInvariantInst(*MI) || !IsProfitableToHoist(*MI)) {
1438  // If not, try unfolding a hoistable load.
1439  MI = ExtractHoistableLoad(MI);
1440  if (!MI) return false;
1441  }
1442 
1443  // If we have hoisted an instruction that may store, it can only be a constant
1444  // store.
1445  if (MI->mayStore())
1446  NumStoreConst++;
1447 
1448  // Now move the instructions to the predecessor, inserting it before any
1449  // terminator instructions.
1450  LLVM_DEBUG({
1451  dbgs() << "Hoisting " << *MI;
1452  if (MI->getParent()->getBasicBlock())
1453  dbgs() << " from " << printMBBReference(*MI->getParent());
1454  if (Preheader->getBasicBlock())
1455  dbgs() << " to " << printMBBReference(*Preheader);
1456  dbgs() << "\n";
1457  });
1458 
1459  // If this is the first instruction being hoisted to the preheader,
1460  // initialize the CSE map with potential common expressions.
1461  if (FirstInLoop) {
1462  InitCSEMap(Preheader);
1463  FirstInLoop = false;
1464  }
1465 
1466  // Look for opportunity to CSE the hoisted instruction.
1467  unsigned Opcode = MI->getOpcode();
1469  CI = CSEMap.find(Opcode);
1470  if (!EliminateCSE(MI, CI)) {
1471  // Otherwise, splice the instruction to the preheader.
1472  Preheader->splice(Preheader->getFirstTerminator(),MI->getParent(),MI);
1473 
1474  // Since we are moving the instruction out of its basic block, we do not
1475  // retain its debug location. Doing so would degrade the debugging
1476  // experience and adversely affect the accuracy of profiling information.
1477  MI->setDebugLoc(DebugLoc());
1478 
1479  // Update register pressure for BBs from header to this block.
1480  UpdateBackTraceRegPressure(MI);
1481 
1482  // Clear the kill flags of any register this instruction defines,
1483  // since they may need to be live throughout the entire loop
1484  // rather than just live for part of it.
1485  for (MachineOperand &MO : MI->operands())
1486  if (MO.isReg() && MO.isDef() && !MO.isDead())
1487  MRI->clearKillFlags(MO.getReg());
1488 
1489  // Add to the CSE map.
1490  if (CI != CSEMap.end())
1491  CI->second.push_back(MI);
1492  else
1493  CSEMap[Opcode].push_back(MI);
1494  }
1495 
1496  ++NumHoisted;
1497  Changed = true;
1498 
1499  return true;
1500 }
1501 
1502 /// Get the preheader for the current loop, splitting a critical edge if needed.
1503 MachineBasicBlock *MachineLICMBase::getCurPreheader() {
1504  // Determine the block to which to hoist instructions. If we can't find a
1505  // suitable loop predecessor, we can't do any hoisting.
1506 
1507  // If we've tried to get a preheader and failed, don't try again.
1508  if (CurPreheader == reinterpret_cast<MachineBasicBlock *>(-1))
1509  return nullptr;
1510 
1511  if (!CurPreheader) {
1512  CurPreheader = CurLoop->getLoopPreheader();
1513  if (!CurPreheader) {
1514  MachineBasicBlock *Pred = CurLoop->getLoopPredecessor();
1515  if (!Pred) {
1516  CurPreheader = reinterpret_cast<MachineBasicBlock *>(-1);
1517  return nullptr;
1518  }
1519 
1520  CurPreheader = Pred->SplitCriticalEdge(CurLoop->getHeader(), *this);
1521  if (!CurPreheader) {
1522  CurPreheader = reinterpret_cast<MachineBasicBlock *>(-1);
1523  return nullptr;
1524  }
1525  }
1526  }
1527  return CurPreheader;
1528 }
BitVector & set()
Definition: BitVector.h:397
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
instr_iterator instr_begin()
bool use_nodbg_empty(unsigned RegNo) const
use_nodbg_empty - Return true if there are no non-Debug instructions using the specified register...
virtual unsigned getNumRegPressureSets() const =0
Get the number of dimensions of register pressure.
instr_iterator instr_end()
const MachineFunction * getMF() const
Return the function that contains the basic block that this instruction belongs to.
This class represents lattice values for constants.
Definition: AllocatorList.h:23
Register createVirtualRegister(const TargetRegisterClass *RegClass, StringRef Name="")
createVirtualRegister - Create and return a new virtual register in the function with the specified r...
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
char & MachineLICMID
This pass performs loop invariant code motion on machine instructions.
static bool isPhysicalRegister(unsigned Reg)
Return true if the specified register number is in the physical register namespace.
Definition: Register.h:63
iterator getFirstTerminator()
Returns an iterator to the first terminator instruction of this basic block.
Describe properties that are true of each instruction in the target description file.
Definition: MCInstrDesc.h:179
unsigned Reg
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:160
virtual const TargetLowering * getTargetLowering() const
bool test(unsigned Idx) const
Definition: BitVector.h:501
void setBitsNotInMask(const uint32_t *Mask, unsigned MaskWords=~0u)
setBitsNotInMask - Add a bit to this vector for every &#39;0&#39; bit in Mask.
Definition: BitVector.h:787
virtual const int * getRegClassPressureSets(const TargetRegisterClass *RC) const =0
Get the dimensions of register pressure impacted by this register class.
STATISTIC(NumFunctions, "Total number of functions")
unsigned const TargetRegisterInfo * TRI
A debug info location.
Definition: DebugLoc.h:33
bool hasOneDef(unsigned RegNo) const
Return true if there is exactly one operand defining the specified register.
block Block Frequency true
static bool isExitBlock(BasicBlock *BB, const SmallVectorImpl< BasicBlock *> &ExitBlocks)
Return true if the specified block is in the list.
Definition: LCSSA.cpp:68
iterator_range< mop_iterator > operands()
Definition: MachineInstr.h:476
bool isCopyLike() const
Return true if the instruction behaves like a copy.
static bool mayLoadFromGOTOrConstantPool(MachineInstr &MI)
Return true if this machine instruction loads from global offset table or constant pool...
const TargetRegisterClass * getRegClass(Register Reg) const
Return the register class of the specified virtual register.
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:50
A description of a memory reference used in the backend.
Each TargetRegisterClass has a per register weight, and weight limit which must be less than the limi...
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
unsigned getNumOperands() const
Return the number of declared MachineOperands for this MachineInstruction.
Definition: MCInstrDesc.h:226
Provide an instruction scheduling machine model to CodeGen passes.
const HexagonInstrInfo * TII
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
unsigned getNumOperands() const
Retuns the total number of operands.
Definition: MachineInstr.h:413
virtual const TargetRegisterClass * getRegClass(const MCInstrDesc &MCID, unsigned OpNum, const TargetRegisterInfo *TRI, const MachineFunction &MF) const
Given a machine instruction descriptor, returns the register class constraint for OpNum...
static bool isOperandKill(const MachineOperand &MO, MachineRegisterInfo *MRI)
virtual bool unfoldMemoryOperand(MachineFunction &MF, MachineInstr &MI, unsigned Reg, bool UnfoldLoad, bool UnfoldStore, SmallVectorImpl< MachineInstr *> &NewMIs) const
unfoldMemoryOperand - Separate a single instruction which folded a load or a store or a load and a st...
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:41
void eraseFromParent()
Unlink &#39;this&#39; from the containing basic block and delete it.
The MachineFrameInfo class represents an abstract stack frame until prolog/epilog code is inserted...
virtual bool hasLowDefLatency(const TargetSchedModel &SchedModel, const MachineInstr &DefMI, unsigned DefIdx) const
Compute operand latency of a def of &#39;Reg&#39;.
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
Definition: MachineInstr.h:410
static cl::opt< bool > AvoidSpeculation("avoid-speculation", cl::desc("MachineLICM should avoid speculation"), cl::init(true), cl::Hidden)
BlockT * getHeader() const
Definition: LoopInfo.h:105
MachineInstr * getVRegDef(unsigned Reg) const
getVRegDef - Return the machine instr that defines the specified virtual register or null if none is ...
void getExitBlocks(SmallVectorImpl< BlockT *> &ExitBlocks) const
Return all of the successor blocks of this loop.
Definition: LoopInfoImpl.h:62
Machine Loop Invariant Code Motion
const MCInstrDesc & getDesc() const
Returns the target instruction descriptor of this MachineInstr.
Definition: MachineInstr.h:407
void clear()
Definition: SmallSet.h:218
void clearKillFlags(unsigned Reg) const
clearKillFlags - Iterate over all the uses of the given register and clear the kill flag from the Mac...
#define DEBUG_TYPE
Definition: MachineLICM.cpp:56
Base class for the actual dominator tree node.
Definition: LiveRangeCalc.h:37
const std::vector< DomTreeNodeBase * > & getChildren() const
COFF::MachineTypes Machine
Definition: COFFYAML.cpp:365
virtual const TargetInstrInfo * getInstrInfo() const
MachineBasicBlock * findNearestCommonDominator(MachineBasicBlock *A, MachineBasicBlock *B)
findNearestCommonDominator - Find nearest common dominator basic block for basic block A and B...
const TargetRegisterClass * constrainRegClass(unsigned Reg, const TargetRegisterClass *RC, unsigned MinNumRegs=0)
constrainRegClass - Constrain the register class of the specified virtual register to be a common sub...
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
TargetInstrInfo - Interface to description of machine instruction set.
iterator begin() const
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:150
NodeT * getBlock() const
bool mayStore(QueryType Type=AnyInBundle) const
Return true if this instruction could possibly modify memory.
Definition: MachineInstr.h:843
unsigned getNumRegs() const
Return the number of registers this target has (useful for sizing arrays holding per register informa...
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
unsigned const MachineRegisterInfo * MRI
ArrayRef< MachineMemOperand * > memoperands() const
Access to memory operands of the instruction.
Definition: MachineInstr.h:533
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
MachineFrameInfo & getFrameInfo()
getFrameInfo - Return the frame info object for the current function.
MachineInstrBuilder & UseMI
Machine Loop Invariant Code false early Early Machine Loop Invariant Code static false bool LoopIsOuterMostWithPredecessor(MachineLoop *CurLoop)
Test if the given loop is the outer-most loop that has a unique predecessor.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:134
static cl::opt< bool > HoistCheapInsts("hoist-cheap-insts", cl::desc("MachineLICM should hoist even cheap instructions"), cl::init(false), cl::Hidden)
MCRegAliasIterator enumerates all registers aliasing Reg.
Represent the analysis usage information of a pass.
constexpr double e
Definition: MathExtras.h:57
bool isSuperRegister(MCRegister RegA, MCRegister RegB) const
Returns true if RegB is a super-register of RegA.
static bool InstructionStoresToFI(const MachineInstr *MI, int FI)
Return true if instruction stores to the specified frame.
std::pair< NoneType, bool > insert(const T &V)
insert - Insert an element into the set if it isn&#39;t already there.
Definition: SmallSet.h:180
void init(const TargetSubtargetInfo *TSInfo)
Initialize the machine model for instruction scheduling.
void getExitingBlocks(SmallVectorImpl< BlockT *> &ExitingBlocks) const
Return all blocks inside the loop that have successors outside of the loop.
Definition: LoopInfoImpl.h:34
bool isCopy() const
bool isImplicitDef() const
virtual bool analyzeBranch(MachineBasicBlock &MBB, MachineBasicBlock *&TBB, MachineBasicBlock *&FBB, SmallVectorImpl< MachineOperand > &Cond, bool AllowModify=false) const
Analyze the branching code at the end of MBB, returning true if it cannot be understood (e...
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
size_t size() const
Definition: SmallVector.h:52
static bool isInvariantStore(const MachineInstr &MI, const TargetRegisterInfo *TRI, const MachineRegisterInfo *MRI)
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
bool isConstantPhysReg(unsigned PhysReg) const
Returns true if PhysReg is unallocatable and constant throughout the function.
void initializeMachineLICMPass(PassRegistry &)
This base class for TargetLowering contains the SelectionDAG-independent parts that can be used from ...
virtual bool isAsCheapAsAMove(const MachineInstr &MI) const
Return true if the instruction is as cheap as a move instruction.
BlockT * getLoopPredecessor() const
If the given loop&#39;s header has exactly one unique predecessor outside the loop, return it...
Definition: LoopInfoImpl.h:188
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:115
Iterator for intrusive lists based on ilist_node.
bool isDereferenceableInvariantLoad(AAResults *AA) const
Return true if this load instruction never traps and points to a memory location whose value doesn&#39;t ...
MachineOperand class - Representation of each machine instruction operand.
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
virtual const RegClassWeight & getRegClassWeight(const TargetRegisterClass *RC) const =0
Get the weight in units of pressure for this register class.
bool dominates(const MachineDomTreeNode *A, const MachineDomTreeNode *B) const
virtual bool hasHighOperandLatency(const TargetSchedModel &SchedModel, const MachineRegisterInfo *MRI, const MachineInstr &DefMI, unsigned DefIdx, const MachineInstr &UseMI, unsigned UseIdx) const
Compute operand latency between a def of &#39;Reg&#39; and a use in the current loop.
iterator begin() const
Definition: LoopInfo.h:147
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:374
char & EarlyMachineLICMID
This pass performs loop invariant code motion on machine instructions.
Machine Loop Invariant Code false early machinelicm
unsigned getNumDefs() const
Return the number of MachineOperands that are register definitions.
Definition: MCInstrDesc.h:241
unsigned pred_size() const
const Function & getFunction() const
Return the LLVM function that this machine code represents.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
bool isLiveIn(MCPhysReg Reg, LaneBitmask LaneMask=LaneBitmask::getAll()) const
Return true if the specified register is in the live in set.
void setDebugLoc(DebugLoc dl)
Replace current source information with new such.
Special value supplied for machine level alias analysis.
iterator end() const
void replaceRegWith(unsigned FromReg, unsigned ToReg)
replaceRegWith - Replace all instances of FromReg with ToReg in the machine function.
unsigned succ_size() const
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:255
MachineRegisterInfo - Keep track of information for virtual and physical registers, including vreg register classes, use/def chains for registers, etc.
TargetSubtargetInfo - Generic base class for all target subtargets.
#define Success
LoopT * getParentLoop() const
Definition: LoopInfo.h:106
Representation of each machine instruction.
Definition: MachineInstr.h:63
void splice(iterator Where, MachineBasicBlock *Other, iterator From)
Take an instruction from MBB &#39;Other&#39; at the position From, and insert it into this MBB right before &#39;...
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
bool isEHPad() const
Returns true if the block is a landing pad.
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:55
virtual unsigned isLoadFromStackSlot(const MachineInstr &MI, int &FrameIndex) const
If the specified machine instruction is a direct load from a stack slot, return the virtual or physic...
virtual unsigned getRegPressureSetLimit(const MachineFunction &MF, unsigned Idx) const =0
Get the register unit pressure limit for this dimension.
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:509
ArrayRef< BlockT * > getBlocks() const
Get a list of the basic blocks which make up this loop.
Definition: LoopInfo.h:154
bool canFoldAsLoad(QueryType Type=IgnoreBundle) const
Return true for instructions that can be folded as memory operands in other instructions.
Definition: MachineInstr.h:776
const MCInstrDesc & get(unsigned Opcode) const
Return the machine instruction descriptor that corresponds to the specified instruction opcode...
Definition: MCInstrInfo.h:44
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
virtual bool produceSameValue(const MachineInstr &MI0, const MachineInstr &MI1, const MachineRegisterInfo *MRI=nullptr) const
Return true if two machine instructions would produce identical values.
iterator end()
Definition: DenseMap.h:82
INITIALIZE_PASS_BEGIN(MachineLICM, DEBUG_TYPE, "Machine Loop Invariant Code Motion", false, false) INITIALIZE_PASS_END(MachineLICM
const BasicBlock * getBasicBlock() const
Return the LLVM basic block that this instance corresponded to originally.
iterator end() const
Definition: LoopInfo.h:148
virtual bool isCallerPreservedPhysReg(unsigned PhysReg, const MachineFunction &MF) const
Physical registers that may be modified within a function but are guaranteed to be restored before an...
iterator getFirstNonPHI()
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
bool hasOneNonDBGUse(unsigned RegNo) const
hasOneNonDBGUse - Return true if there is exactly one non-Debug use of the specified register...
bool isReg() const
isReg - Tests if this is a MO_Register operand.
static bool isCopyFeedingInvariantStore(const MachineInstr &MI, const MachineRegisterInfo *MRI, const TargetRegisterInfo *TRI)
iterator_range< use_instr_iterator > use_instructions(unsigned Reg) const
void initializeEarlyMachineLICMPass(PassRegistry &)
bool mayLoad(QueryType Type=AnyInBundle) const
Return true if this instruction could possibly read memory.
Definition: MachineInstr.h:830
bool memoperands_empty() const
Return true if we don&#39;t have any memory operands which described the memory access done by this instr...
Definition: MachineInstr.h:563
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
MachineBasicBlock * SplitCriticalEdge(MachineBasicBlock *Succ, Pass &P)
Split the critical edge from this block to the given successor block, and return the newly created bl...
static cl::opt< bool > HoistConstStores("hoist-const-stores", cl::desc("Hoist invariant stores"), cl::init(true), cl::Hidden)
bool isSafeToMove(AAResults *AA, bool &SawStore) const
Return true if it is safe to move this instruction.
LLVM Value Representation.
Definition: Value.h:74
static cl::opt< bool > SinkInstsToAvoidSpills("sink-insts-to-avoid-spills", cl::desc("MachineLICM should sink instructions into " "loops to avoid register spills"), cl::init(false), cl::Hidden)
MachineLoop * getLoopFor(const MachineBasicBlock *BB) const
Return the innermost loop that BB lives in.
static bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
Definition: Register.h:69
bool isTriviallyReMaterializable(const MachineInstr &MI, AAResults *AA=nullptr) const
Return true if the instruction is trivially rematerializable, meaning it has no side effects and requ...
bool hasUnmodeledSideEffects() const
Return true if this instruction has side effects that are not modeled by mayLoad / mayStore...
IRTranslator LLVM IR MI
void setRegClass(unsigned Reg, const TargetRegisterClass *RC)
setRegClass - Set the register class of the specified virtual register.
A specialized PseudoSourceValue for holding FixedStack values, which must include a frame index...
Register getReg() const
getReg - Returns the register number.
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object...
#define LLVM_DEBUG(X)
Definition: Debug.h:122
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:415
iterator_range< use_instr_nodbg_iterator > use_nodbg_instructions(unsigned Reg) const
virtual unsigned lookThruCopyLike(unsigned SrcReg, const MachineRegisterInfo *MRI) const
Returns the original SrcReg unless it is the target of a copy-like operation, in which case we chain ...
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
virtual unsigned getOpcodeAfterMemoryUnfold(unsigned Opc, bool UnfoldLoad, bool UnfoldStore, unsigned *LoadRegIndex=nullptr) const
Returns the opcode of the would be new instruction after load / store are unfolded from an instructio...
bool isSpillSlotObjectIndex(int ObjectIdx) const
Returns true if the specified index corresponds to a spill slot.
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
This file describes how to lower LLVM code to machine code.
bool isImplicit() const
size_type count(const T &V) const
count - Return 1 if the element is in the set, 0 otherwise.
Definition: SmallSet.h:164
void resize(size_type N)
Definition: SmallVector.h:344
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:1224