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