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