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