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