LLVM  14.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  // Pop scope.
704  ExitScope(Node->getBlock());
705 
706  // Now traverse upwards to pop ancestors whose offsprings are all done.
707  while (MachineDomTreeNode *Parent = ParentMap[Node]) {
708  unsigned Left = --OpenChildren[Parent];
709  if (Left != 0)
710  break;
711  ExitScope(Parent->getBlock());
712  Node = Parent;
713  }
714 }
715 
716 /// Walk the specified loop in the CFG (defined by all blocks dominated by the
717 /// specified header block, and that are in the current loop) in depth first
718 /// order w.r.t the DominatorTree. This allows us to visit definitions before
719 /// uses, allowing us to hoist a loop body in one pass without iteration.
720 void MachineLICMBase::HoistOutOfLoop(MachineDomTreeNode *HeaderN) {
721  MachineBasicBlock *Preheader = getCurPreheader();
722  if (!Preheader)
723  return;
724 
729 
730  // Perform a DFS walk to determine the order of visit.
731  WorkList.push_back(HeaderN);
732  while (!WorkList.empty()) {
733  MachineDomTreeNode *Node = WorkList.pop_back_val();
734  assert(Node && "Null dominator tree node?");
735  MachineBasicBlock *BB = Node->getBlock();
736 
737  // If the header of the loop containing this basic block is a landing pad,
738  // then don't try to hoist instructions out of this loop.
739  const MachineLoop *ML = MLI->getLoopFor(BB);
740  if (ML && ML->getHeader()->isEHPad())
741  continue;
742 
743  // If this subregion is not in the top level loop at all, exit.
744  if (!CurLoop->contains(BB))
745  continue;
746 
747  Scopes.push_back(Node);
748  unsigned NumChildren = Node->getNumChildren();
749 
750  // Don't hoist things out of a large switch statement. This often causes
751  // code to be hoisted that wasn't going to be executed, and increases
752  // register pressure in a situation where it's likely to matter.
753  if (BB->succ_size() >= 25)
754  NumChildren = 0;
755 
756  OpenChildren[Node] = NumChildren;
757  if (NumChildren) {
758  // Add children in reverse order as then the next popped worklist node is
759  // the first child of this node. This means we ultimately traverse the
760  // DOM tree in exactly the same order as if we'd recursed.
761  for (MachineDomTreeNode *Child : reverse(Node->children())) {
762  ParentMap[Child] = Node;
763  WorkList.push_back(Child);
764  }
765  }
766  }
767 
768  if (Scopes.size() == 0)
769  return;
770 
771  // Compute registers which are livein into the loop headers.
772  RegSeen.clear();
773  BackTrace.clear();
774  InitRegPressure(Preheader);
775 
776  // Now perform LICM.
777  for (MachineDomTreeNode *Node : Scopes) {
778  MachineBasicBlock *MBB = Node->getBlock();
779 
780  EnterScope(MBB);
781 
782  // Process the block
783  SpeculationState = SpeculateUnknown;
785  MII = MBB->begin(), E = MBB->end(); MII != E; ) {
786  MachineBasicBlock::iterator NextMII = MII; ++NextMII;
787  MachineInstr *MI = &*MII;
788  if (!Hoist(MI, Preheader))
789  UpdateRegPressure(MI);
790  // If we have hoisted an instruction that may store, it can only be a
791  // constant store.
792  MII = NextMII;
793  }
794 
795  // If it's a leaf node, it's done. Traverse upwards to pop ancestors.
796  ExitScopeIfDone(Node, OpenChildren, ParentMap);
797  }
798 }
799 
801  return MO.isKill() || MRI->hasOneNonDBGUse(MO.getReg());
802 }
803 
804 /// Find all virtual register references that are liveout of the preheader to
805 /// initialize the starting "register pressure". Note this does not count live
806 /// through (livein but not used) registers.
807 void MachineLICMBase::InitRegPressure(MachineBasicBlock *BB) {
808  std::fill(RegPressure.begin(), RegPressure.end(), 0);
809 
810  // If the preheader has only a single predecessor and it ends with a
811  // fallthrough or an unconditional branch, then scan its predecessor for live
812  // defs as well. This happens whenever the preheader is created by splitting
813  // the critical edge from the loop predecessor to the loop header.
814  if (BB->pred_size() == 1) {
815  MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
817  if (!TII->analyzeBranch(*BB, TBB, FBB, Cond, false) && Cond.empty())
818  InitRegPressure(*BB->pred_begin());
819  }
820 
821  for (const MachineInstr &MI : *BB)
822  UpdateRegPressure(&MI, /*ConsiderUnseenAsDef=*/true);
823 }
824 
825 /// Update estimate of register pressure after the specified instruction.
826 void MachineLICMBase::UpdateRegPressure(const MachineInstr *MI,
827  bool ConsiderUnseenAsDef) {
828  auto Cost = calcRegisterCost(MI, /*ConsiderSeen=*/true, ConsiderUnseenAsDef);
829  for (const auto &RPIdAndCost : Cost) {
830  unsigned Class = RPIdAndCost.first;
831  if (static_cast<int>(RegPressure[Class]) < -RPIdAndCost.second)
832  RegPressure[Class] = 0;
833  else
834  RegPressure[Class] += RPIdAndCost.second;
835  }
836 }
837 
838 /// Calculate the additional register pressure that the registers used in MI
839 /// cause.
840 ///
841 /// If 'ConsiderSeen' is true, updates 'RegSeen' and uses the information to
842 /// figure out which usages are live-ins.
843 /// FIXME: Figure out a way to consider 'RegSeen' from all code paths.
845 MachineLICMBase::calcRegisterCost(const MachineInstr *MI, bool ConsiderSeen,
846  bool ConsiderUnseenAsDef) {
848  if (MI->isImplicitDef())
849  return Cost;
850  for (unsigned i = 0, e = MI->getDesc().getNumOperands(); i != e; ++i) {
851  const MachineOperand &MO = MI->getOperand(i);
852  if (!MO.isReg() || MO.isImplicit())
853  continue;
854  Register Reg = MO.getReg();
856  continue;
857 
858  // FIXME: It seems bad to use RegSeen only for some of these calculations.
859  bool isNew = ConsiderSeen ? RegSeen.insert(Reg).second : false;
860  const TargetRegisterClass *RC = MRI->getRegClass(Reg);
861 
863  int RCCost = 0;
864  if (MO.isDef())
865  RCCost = W.RegWeight;
866  else {
867  bool isKill = isOperandKill(MO, MRI);
868  if (isNew && !isKill && ConsiderUnseenAsDef)
869  // Haven't seen this, it must be a livein.
870  RCCost = W.RegWeight;
871  else if (!isNew && isKill)
872  RCCost = -W.RegWeight;
873  }
874  if (RCCost == 0)
875  continue;
876  const int *PS = TRI->getRegClassPressureSets(RC);
877  for (; *PS != -1; ++PS) {
878  if (Cost.find(*PS) == Cost.end())
879  Cost[*PS] = RCCost;
880  else
881  Cost[*PS] += RCCost;
882  }
883  }
884  return Cost;
885 }
886 
887 /// Return true if this machine instruction loads from global offset table or
888 /// constant pool.
890  assert(MI.mayLoad() && "Expected MI that loads!");
891 
892  // If we lost memory operands, conservatively assume that the instruction
893  // reads from everything..
894  if (MI.memoperands_empty())
895  return true;
896 
897  for (MachineMemOperand *MemOp : MI.memoperands())
898  if (const PseudoSourceValue *PSV = MemOp->getPseudoValue())
899  if (PSV->isGOT() || PSV->isConstantPool())
900  return true;
901 
902  return false;
903 }
904 
905 // This function iterates through all the operands of the input store MI and
906 // checks that each register operand statisfies isCallerPreservedPhysReg.
907 // This means, the value being stored and the address where it is being stored
908 // is constant throughout the body of the function (not including prologue and
909 // epilogue). When called with an MI that isn't a store, it returns false.
910 // A future improvement can be to check if the store registers are constant
911 // throughout the loop rather than throughout the funtion.
912 static bool isInvariantStore(const MachineInstr &MI,
913  const TargetRegisterInfo *TRI,
914  const MachineRegisterInfo *MRI) {
915 
916  bool FoundCallerPresReg = false;
917  if (!MI.mayStore() || MI.hasUnmodeledSideEffects() ||
918  (MI.getNumOperands() == 0))
919  return false;
920 
921  // Check that all register operands are caller-preserved physical registers.
922  for (const MachineOperand &MO : MI.operands()) {
923  if (MO.isReg()) {
924  Register Reg = MO.getReg();
925  // If operand is a virtual register, check if it comes from a copy of a
926  // physical register.
928  Reg = TRI->lookThruCopyLike(MO.getReg(), MRI);
930  return false;
931  if (!TRI->isCallerPreservedPhysReg(Reg.asMCReg(), *MI.getMF()))
932  return false;
933  else
934  FoundCallerPresReg = true;
935  } else if (!MO.isImm()) {
936  return false;
937  }
938  }
939  return FoundCallerPresReg;
940 }
941 
942 // Return true if the input MI is a copy instruction that feeds an invariant
943 // store instruction. This means that the src of the copy has to satisfy
944 // isCallerPreservedPhysReg and atleast one of it's users should satisfy
945 // isInvariantStore.
947  const MachineRegisterInfo *MRI,
948  const TargetRegisterInfo *TRI) {
949 
950  // FIXME: If targets would like to look through instructions that aren't
951  // pure copies, this can be updated to a query.
952  if (!MI.isCopy())
953  return false;
954 
955  const MachineFunction *MF = MI.getMF();
956  // Check that we are copying a constant physical register.
957  Register CopySrcReg = MI.getOperand(1).getReg();
958  if (Register::isVirtualRegister(CopySrcReg))
959  return false;
960 
961  if (!TRI->isCallerPreservedPhysReg(CopySrcReg.asMCReg(), *MF))
962  return false;
963 
964  Register CopyDstReg = MI.getOperand(0).getReg();
965  // Check if any of the uses of the copy are invariant stores.
966  assert(Register::isVirtualRegister(CopyDstReg) &&
967  "copy dst is not a virtual reg");
968 
969  for (MachineInstr &UseMI : MRI->use_instructions(CopyDstReg)) {
970  if (UseMI.mayStore() && isInvariantStore(UseMI, TRI, MRI))
971  return true;
972  }
973  return false;
974 }
975 
976 /// Returns true if the instruction may be a suitable candidate for LICM.
977 /// e.g. If the instruction is a call, then it's obviously not safe to hoist it.
978 bool MachineLICMBase::IsLICMCandidate(MachineInstr &I) {
979  // Check if it's safe to move the instruction.
980  bool DontMoveAcrossStore = true;
981  if ((!I.isSafeToMove(AA, DontMoveAcrossStore)) &&
983  LLVM_DEBUG(dbgs() << "LICM: Instruction not safe to move.\n");
984  return false;
985  }
986 
987  // If it is a load then check if it is guaranteed to execute by making sure
988  // that it dominates all exiting blocks. If it doesn't, then there is a path
989  // out of the loop which does not execute this load, so we can't hoist it.
990  // Loads from constant memory are safe to speculate, for example indexed load
991  // from a jump table.
992  // Stores and side effects are already checked by isSafeToMove.
993  if (I.mayLoad() && !mayLoadFromGOTOrConstantPool(I) &&
994  !IsGuaranteedToExecute(I.getParent())) {
995  LLVM_DEBUG(dbgs() << "LICM: Load not guaranteed to execute.\n");
996  return false;
997  }
998 
999  // Convergent attribute has been used on operations that involve inter-thread
1000  // communication which results are implicitly affected by the enclosing
1001  // control flows. It is not safe to hoist or sink such operations across
1002  // control flow.
1003  if (I.isConvergent())
1004  return false;
1005 
1006  return true;
1007 }
1008 
1009 /// Returns true if the instruction is loop invariant.
1010 bool MachineLICMBase::IsLoopInvariantInst(MachineInstr &I) {
1011  if (!IsLICMCandidate(I)) {
1012  LLVM_DEBUG(dbgs() << "LICM: Instruction not a LICM candidate\n");
1013  return false;
1014  }
1015  return CurLoop->isLoopInvariant(I);
1016 }
1017 
1018 /// Return true if the specified instruction is used by a phi node and hoisting
1019 /// it could cause a copy to be inserted.
1020 bool MachineLICMBase::HasLoopPHIUse(const MachineInstr *MI) const {
1022  do {
1023  MI = Work.pop_back_val();
1024  for (const MachineOperand &MO : MI->operands()) {
1025  if (!MO.isReg() || !MO.isDef())
1026  continue;
1027  Register Reg = MO.getReg();
1029  continue;
1031  // A PHI may cause a copy to be inserted.
1032  if (UseMI.isPHI()) {
1033  // A PHI inside the loop causes a copy because the live range of Reg is
1034  // extended across the PHI.
1035  if (CurLoop->contains(&UseMI))
1036  return true;
1037  // A PHI in an exit block can cause a copy to be inserted if the PHI
1038  // has multiple predecessors in the loop with different values.
1039  // For now, approximate by rejecting all exit blocks.
1040  if (isExitBlock(UseMI.getParent()))
1041  return true;
1042  continue;
1043  }
1044  // Look past copies as well.
1045  if (UseMI.isCopy() && CurLoop->contains(&UseMI))
1046  Work.push_back(&UseMI);
1047  }
1048  }
1049  } while (!Work.empty());
1050  return false;
1051 }
1052 
1053 /// Compute operand latency between a def of 'Reg' and an use in the current
1054 /// loop, return true if the target considered it high.
1055 bool MachineLICMBase::HasHighOperandLatency(MachineInstr &MI, unsigned DefIdx,
1056  Register Reg) const {
1057  if (MRI->use_nodbg_empty(Reg))
1058  return false;
1059 
1061  if (UseMI.isCopyLike())
1062  continue;
1063  if (!CurLoop->contains(UseMI.getParent()))
1064  continue;
1065  for (unsigned i = 0, e = UseMI.getNumOperands(); i != e; ++i) {
1066  const MachineOperand &MO = UseMI.getOperand(i);
1067  if (!MO.isReg() || !MO.isUse())
1068  continue;
1069  Register MOReg = MO.getReg();
1070  if (MOReg != Reg)
1071  continue;
1072 
1073  if (TII->hasHighOperandLatency(SchedModel, MRI, MI, DefIdx, UseMI, i))
1074  return true;
1075  }
1076 
1077  // Only look at the first in loop use.
1078  break;
1079  }
1080 
1081  return false;
1082 }
1083 
1084 /// Return true if the instruction is marked "cheap" or the operand latency
1085 /// between its def and a use is one or less.
1086 bool MachineLICMBase::IsCheapInstruction(MachineInstr &MI) const {
1087  if (TII->isAsCheapAsAMove(MI) || MI.isCopyLike())
1088  return true;
1089 
1090  bool isCheap = false;
1091  unsigned NumDefs = MI.getDesc().getNumDefs();
1092  for (unsigned i = 0, e = MI.getNumOperands(); NumDefs && i != e; ++i) {
1093  MachineOperand &DefMO = MI.getOperand(i);
1094  if (!DefMO.isReg() || !DefMO.isDef())
1095  continue;
1096  --NumDefs;
1097  Register Reg = DefMO.getReg();
1099  continue;
1100 
1101  if (!TII->hasLowDefLatency(SchedModel, MI, i))
1102  return false;
1103  isCheap = true;
1104  }
1105 
1106  return isCheap;
1107 }
1108 
1109 /// Visit BBs from header to current BB, check if hoisting an instruction of the
1110 /// given cost matrix can cause high register pressure.
1111 bool
1112 MachineLICMBase::CanCauseHighRegPressure(const DenseMap<unsigned, int>& Cost,
1113  bool CheapInstr) {
1114  for (const auto &RPIdAndCost : Cost) {
1115  if (RPIdAndCost.second <= 0)
1116  continue;
1117 
1118  unsigned Class = RPIdAndCost.first;
1119  int Limit = RegLimit[Class];
1120 
1121  // Don't hoist cheap instructions if they would increase register pressure,
1122  // even if we're under the limit.
1123  if (CheapInstr && !HoistCheapInsts)
1124  return true;
1125 
1126  for (const auto &RP : BackTrace)
1127  if (static_cast<int>(RP[Class]) + RPIdAndCost.second >= Limit)
1128  return true;
1129  }
1130 
1131  return false;
1132 }
1133 
1134 /// Traverse the back trace from header to the current block and update their
1135 /// register pressures to reflect the effect of hoisting MI from the current
1136 /// block to the preheader.
1137 void MachineLICMBase::UpdateBackTraceRegPressure(const MachineInstr *MI) {
1138  // First compute the 'cost' of the instruction, i.e. its contribution
1139  // to register pressure.
1140  auto Cost = calcRegisterCost(MI, /*ConsiderSeen=*/false,
1141  /*ConsiderUnseenAsDef=*/false);
1142 
1143  // Update register pressure of blocks from loop header to current block.
1144  for (auto &RP : BackTrace)
1145  for (const auto &RPIdAndCost : Cost)
1146  RP[RPIdAndCost.first] += RPIdAndCost.second;
1147 }
1148 
1149 /// Return true if it is potentially profitable to hoist the given loop
1150 /// invariant.
1151 bool MachineLICMBase::IsProfitableToHoist(MachineInstr &MI) {
1152  if (MI.isImplicitDef())
1153  return true;
1154 
1155  // Besides removing computation from the loop, hoisting an instruction has
1156  // these effects:
1157  //
1158  // - The value defined by the instruction becomes live across the entire
1159  // loop. This increases register pressure in the loop.
1160  //
1161  // - If the value is used by a PHI in the loop, a copy will be required for
1162  // lowering the PHI after extending the live range.
1163  //
1164  // - When hoisting the last use of a value in the loop, that value no longer
1165  // needs to be live in the loop. This lowers register pressure in the loop.
1166 
1168  return true;
1169 
1170  bool CheapInstr = IsCheapInstruction(MI);
1171  bool CreatesCopy = HasLoopPHIUse(&MI);
1172 
1173  // Don't hoist a cheap instruction if it would create a copy in the loop.
1174  if (CheapInstr && CreatesCopy) {
1175  LLVM_DEBUG(dbgs() << "Won't hoist cheap instr with loop PHI use: " << MI);
1176  return false;
1177  }
1178 
1179  // Rematerializable instructions should always be hoisted providing the
1180  // register allocator can just pull them down again when needed.
1181  if (isTriviallyReMaterializable(MI, AA))
1182  return true;
1183 
1184  // FIXME: If there are long latency loop-invariant instructions inside the
1185  // loop at this point, why didn't the optimizer's LICM hoist them?
1186  for (unsigned i = 0, e = MI.getDesc().getNumOperands(); i != e; ++i) {
1187  const MachineOperand &MO = MI.getOperand(i);
1188  if (!MO.isReg() || MO.isImplicit())
1189  continue;
1190  Register Reg = MO.getReg();
1192  continue;
1193  if (MO.isDef() && HasHighOperandLatency(MI, i, Reg)) {
1194  LLVM_DEBUG(dbgs() << "Hoist High Latency: " << MI);
1195  ++NumHighLatency;
1196  return true;
1197  }
1198  }
1199 
1200  // Estimate register pressure to determine whether to LICM the instruction.
1201  // In low register pressure situation, we can be more aggressive about
1202  // hoisting. Also, favors hoisting long latency instructions even in
1203  // moderately high pressure situation.
1204  // Cheap instructions will only be hoisted if they don't increase register
1205  // pressure at all.
1206  auto Cost = calcRegisterCost(&MI, /*ConsiderSeen=*/false,
1207  /*ConsiderUnseenAsDef=*/false);
1208 
1209  // Visit BBs from header to current BB, if hoisting this doesn't cause
1210  // high register pressure, then it's safe to proceed.
1211  if (!CanCauseHighRegPressure(Cost, CheapInstr)) {
1212  LLVM_DEBUG(dbgs() << "Hoist non-reg-pressure: " << MI);
1213  ++NumLowRP;
1214  return true;
1215  }
1216 
1217  // Don't risk increasing register pressure if it would create copies.
1218  if (CreatesCopy) {
1219  LLVM_DEBUG(dbgs() << "Won't hoist instr with loop PHI use: " << MI);
1220  return false;
1221  }
1222 
1223  // Do not "speculate" in high register pressure situation. If an
1224  // instruction is not guaranteed to be executed in the loop, it's best to be
1225  // conservative.
1226  if (AvoidSpeculation &&
1227  (!IsGuaranteedToExecute(MI.getParent()) && !MayCSE(&MI))) {
1228  LLVM_DEBUG(dbgs() << "Won't speculate: " << MI);
1229  return false;
1230  }
1231 
1232  // High register pressure situation, only hoist if the instruction is going
1233  // to be remat'ed.
1234  if (!isTriviallyReMaterializable(MI, AA) &&
1235  !MI.isDereferenceableInvariantLoad(AA)) {
1236  LLVM_DEBUG(dbgs() << "Can't remat / high reg-pressure: " << MI);
1237  return false;
1238  }
1239 
1240  return true;
1241 }
1242 
1243 /// Unfold a load from the given machineinstr if the load itself could be
1244 /// hoisted. Return the unfolded and hoistable load, or null if the load
1245 /// couldn't be unfolded or if it wouldn't be hoistable.
1246 MachineInstr *MachineLICMBase::ExtractHoistableLoad(MachineInstr *MI) {
1247  // Don't unfold simple loads.
1248  if (MI->canFoldAsLoad())
1249  return nullptr;
1250 
1251  // If not, we may be able to unfold a load and hoist that.
1252  // First test whether the instruction is loading from an amenable
1253  // memory location.
1254  if (!MI->isDereferenceableInvariantLoad(AA))
1255  return nullptr;
1256 
1257  // Next determine the register class for a temporary register.
1258  unsigned LoadRegIndex;
1259  unsigned NewOpc =
1260  TII->getOpcodeAfterMemoryUnfold(MI->getOpcode(),
1261  /*UnfoldLoad=*/true,
1262  /*UnfoldStore=*/false,
1263  &LoadRegIndex);
1264  if (NewOpc == 0) return nullptr;
1265  const MCInstrDesc &MID = TII->get(NewOpc);
1266  MachineFunction &MF = *MI->getMF();
1267  const TargetRegisterClass *RC = TII->getRegClass(MID, LoadRegIndex, TRI, MF);
1268  // Ok, we're unfolding. Create a temporary register and do the unfold.
1270 
1272  bool Success = TII->unfoldMemoryOperand(MF, *MI, Reg,
1273  /*UnfoldLoad=*/true,
1274  /*UnfoldStore=*/false, NewMIs);
1275  (void)Success;
1276  assert(Success &&
1277  "unfoldMemoryOperand failed when getOpcodeAfterMemoryUnfold "
1278  "succeeded!");
1279  assert(NewMIs.size() == 2 &&
1280  "Unfolded a load into multiple instructions!");
1281  MachineBasicBlock *MBB = MI->getParent();
1283  MBB->insert(Pos, NewMIs[0]);
1284  MBB->insert(Pos, NewMIs[1]);
1285  // If unfolding produced a load that wasn't loop-invariant or profitable to
1286  // hoist, discard the new instructions and bail.
1287  if (!IsLoopInvariantInst(*NewMIs[0]) || !IsProfitableToHoist(*NewMIs[0])) {
1288  NewMIs[0]->eraseFromParent();
1289  NewMIs[1]->eraseFromParent();
1290  return nullptr;
1291  }
1292 
1293  // Update register pressure for the unfolded instruction.
1294  UpdateRegPressure(NewMIs[1]);
1295 
1296  // Otherwise we successfully unfolded a load that we can hoist.
1297 
1298  // Update the call site info.
1299  if (MI->shouldUpdateCallSiteInfo())
1300  MF.eraseCallSiteInfo(MI);
1301 
1302  MI->eraseFromParent();
1303  return NewMIs[0];
1304 }
1305 
1306 /// Initialize the CSE map with instructions that are in the current loop
1307 /// preheader that may become duplicates of instructions that are hoisted
1308 /// out of the loop.
1309 void MachineLICMBase::InitCSEMap(MachineBasicBlock *BB) {
1310  for (MachineInstr &MI : *BB)
1311  CSEMap[MI.getOpcode()].push_back(&MI);
1312 }
1313 
1314 /// Find an instruction amount PrevMIs that is a duplicate of MI.
1315 /// Return this instruction if it's found.
1316 MachineInstr *
1317 MachineLICMBase::LookForDuplicate(const MachineInstr *MI,
1318  std::vector<MachineInstr *> &PrevMIs) {
1319  for (MachineInstr *PrevMI : PrevMIs)
1320  if (TII->produceSameValue(*MI, *PrevMI, (PreRegAlloc ? MRI : nullptr)))
1321  return PrevMI;
1322 
1323  return nullptr;
1324 }
1325 
1326 /// Given a LICM'ed instruction, look for an instruction on the preheader that
1327 /// computes the same value. If it's found, do a RAU on with the definition of
1328 /// the existing instruction rather than hoisting the instruction to the
1329 /// preheader.
1330 bool MachineLICMBase::EliminateCSE(
1331  MachineInstr *MI,
1332  DenseMap<unsigned, std::vector<MachineInstr *>>::iterator &CI) {
1333  // Do not CSE implicit_def so ProcessImplicitDefs can properly propagate
1334  // the undef property onto uses.
1335  if (CI == CSEMap.end() || MI->isImplicitDef())
1336  return false;
1337 
1338  if (MachineInstr *Dup = LookForDuplicate(MI, CI->second)) {
1339  LLVM_DEBUG(dbgs() << "CSEing " << *MI << " with " << *Dup);
1340 
1341  // Replace virtual registers defined by MI by their counterparts defined
1342  // by Dup.
1344  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
1345  const MachineOperand &MO = MI->getOperand(i);
1346 
1347  // Physical registers may not differ here.
1348  assert((!MO.isReg() || MO.getReg() == 0 ||
1350  MO.getReg() == Dup->getOperand(i).getReg()) &&
1351  "Instructions with different phys regs are not identical!");
1352 
1353  if (MO.isReg() && MO.isDef() &&
1355  Defs.push_back(i);
1356  }
1357 
1359  for (unsigned i = 0, e = Defs.size(); i != e; ++i) {
1360  unsigned Idx = Defs[i];
1361  Register Reg = MI->getOperand(Idx).getReg();
1362  Register DupReg = Dup->getOperand(Idx).getReg();
1363  OrigRCs.push_back(MRI->getRegClass(DupReg));
1364 
1365  if (!MRI->constrainRegClass(DupReg, MRI->getRegClass(Reg))) {
1366  // Restore old RCs if more than one defs.
1367  for (unsigned j = 0; j != i; ++j)
1368  MRI->setRegClass(Dup->getOperand(Defs[j]).getReg(), OrigRCs[j]);
1369  return false;
1370  }
1371  }
1372 
1373  for (unsigned Idx : Defs) {
1374  Register Reg = MI->getOperand(Idx).getReg();
1375  Register DupReg = Dup->getOperand(Idx).getReg();
1376  MRI->replaceRegWith(Reg, DupReg);
1377  MRI->clearKillFlags(DupReg);
1378  // Clear Dup dead flag if any, we reuse it for Reg.
1379  if (!MRI->use_nodbg_empty(DupReg))
1380  Dup->getOperand(Idx).setIsDead(false);
1381  }
1382 
1383  MI->eraseFromParent();
1384  ++NumCSEed;
1385  return true;
1386  }
1387  return false;
1388 }
1389 
1390 /// Return true if the given instruction will be CSE'd if it's hoisted out of
1391 /// the loop.
1392 bool MachineLICMBase::MayCSE(MachineInstr *MI) {
1393  unsigned Opcode = MI->getOpcode();
1395  CSEMap.find(Opcode);
1396  // Do not CSE implicit_def so ProcessImplicitDefs can properly propagate
1397  // the undef property onto uses.
1398  if (CI == CSEMap.end() || MI->isImplicitDef())
1399  return false;
1400 
1401  return LookForDuplicate(MI, CI->second) != nullptr;
1402 }
1403 
1404 /// When an instruction is found to use only loop invariant operands
1405 /// that are safe to hoist, this instruction is called to do the dirty work.
1406 /// It returns true if the instruction is hoisted.
1407 bool MachineLICMBase::Hoist(MachineInstr *MI, MachineBasicBlock *Preheader) {
1408  MachineBasicBlock *SrcBlock = MI->getParent();
1409 
1410  // Disable the instruction hoisting due to block hotness
1412  (DisableHoistingToHotterBlocks == UseBFI::PGO && HasProfileData)) &&
1413  isTgtHotterThanSrc(SrcBlock, Preheader)) {
1414  ++NumNotHoistedDueToHotness;
1415  return false;
1416  }
1417  // First check whether we should hoist this instruction.
1418  if (!IsLoopInvariantInst(*MI) || !IsProfitableToHoist(*MI)) {
1419  // If not, try unfolding a hoistable load.
1420  MI = ExtractHoistableLoad(MI);
1421  if (!MI) return false;
1422  }
1423 
1424  // If we have hoisted an instruction that may store, it can only be a constant
1425  // store.
1426  if (MI->mayStore())
1427  NumStoreConst++;
1428 
1429  // Now move the instructions to the predecessor, inserting it before any
1430  // terminator instructions.
1431  LLVM_DEBUG({
1432  dbgs() << "Hoisting " << *MI;
1433  if (MI->getParent()->getBasicBlock())
1434  dbgs() << " from " << printMBBReference(*MI->getParent());
1435  if (Preheader->getBasicBlock())
1436  dbgs() << " to " << printMBBReference(*Preheader);
1437  dbgs() << "\n";
1438  });
1439 
1440  // If this is the first instruction being hoisted to the preheader,
1441  // initialize the CSE map with potential common expressions.
1442  if (FirstInLoop) {
1443  InitCSEMap(Preheader);
1444  FirstInLoop = false;
1445  }
1446 
1447  // Look for opportunity to CSE the hoisted instruction.
1448  unsigned Opcode = MI->getOpcode();
1450  CSEMap.find(Opcode);
1451  if (!EliminateCSE(MI, CI)) {
1452  // Otherwise, splice the instruction to the preheader.
1453  Preheader->splice(Preheader->getFirstTerminator(),MI->getParent(),MI);
1454 
1455  // Since we are moving the instruction out of its basic block, we do not
1456  // retain its debug location. Doing so would degrade the debugging
1457  // experience and adversely affect the accuracy of profiling information.
1458  assert(!MI->isDebugInstr() && "Should not hoist debug inst");
1459  MI->setDebugLoc(DebugLoc());
1460 
1461  // Update register pressure for BBs from header to this block.
1462  UpdateBackTraceRegPressure(MI);
1463 
1464  // Clear the kill flags of any register this instruction defines,
1465  // since they may need to be live throughout the entire loop
1466  // rather than just live for part of it.
1467  for (MachineOperand &MO : MI->operands())
1468  if (MO.isReg() && MO.isDef() && !MO.isDead())
1469  MRI->clearKillFlags(MO.getReg());
1470 
1471  // Add to the CSE map.
1472  if (CI != CSEMap.end())
1473  CI->second.push_back(MI);
1474  else
1475  CSEMap[Opcode].push_back(MI);
1476  }
1477 
1478  ++NumHoisted;
1479  Changed = true;
1480 
1481  return true;
1482 }
1483 
1484 /// Get the preheader for the current loop, splitting a critical edge if needed.
1485 MachineBasicBlock *MachineLICMBase::getCurPreheader() {
1486  // Determine the block to which to hoist instructions. If we can't find a
1487  // suitable loop predecessor, we can't do any hoisting.
1488 
1489  // If we've tried to get a preheader and failed, don't try again.
1490  if (CurPreheader == reinterpret_cast<MachineBasicBlock *>(-1))
1491  return nullptr;
1492 
1493  if (!CurPreheader) {
1494  CurPreheader = CurLoop->getLoopPreheader();
1495  if (!CurPreheader) {
1496  MachineBasicBlock *Pred = CurLoop->getLoopPredecessor();
1497  if (!Pred) {
1498  CurPreheader = reinterpret_cast<MachineBasicBlock *>(-1);
1499  return nullptr;
1500  }
1501 
1502  CurPreheader = Pred->SplitCriticalEdge(CurLoop->getHeader(), *this);
1503  if (!CurPreheader) {
1504  CurPreheader = reinterpret_cast<MachineBasicBlock *>(-1);
1505  return nullptr;
1506  }
1507  }
1508  }
1509  return CurPreheader;
1510 }
1511 
1512 /// Is the target basic block at least "BlockFrequencyRatioThreshold"
1513 /// times hotter than the source basic block.
1514 bool MachineLICMBase::isTgtHotterThanSrc(MachineBasicBlock *SrcBlock,
1515  MachineBasicBlock *TgtBlock) {
1516  // Parse source and target basic block frequency from MBFI
1517  uint64_t SrcBF = MBFI->getBlockFreq(SrcBlock).getFrequency();
1518  uint64_t DstBF = MBFI->getBlockFreq(TgtBlock).getFrequency();
1519 
1520  // Disable the hoisting if source block frequency is zero
1521  if (!SrcBF)
1522  return true;
1523 
1524  double Ratio = (double)DstBF / SrcBF;
1525 
1526  // Compare the block frequency ratio with the threshold
1527  return Ratio > BlockFrequencyRatioThreshold;
1528 }
i
i
Definition: README.txt:29
UseBFI::All
@ All
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:105
MachineInstr.h
llvm
This file implements support for optimizing divisions by a constant.
Definition: AllocatorList.h:23
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:192
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:699
Reg
unsigned Reg
Definition: MachineSink.cpp:1566
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:102
llvm::LoopBase::getExitBlocks
void getExitBlocks(SmallVectorImpl< BlockT * > &ExitBlocks) const
Return all of the successor blocks of this loop.
Definition: LoopInfoImpl.h:62
llvm::MachineLoopInfo::getLoopFor
MachineLoop * getLoopFor(const MachineBasicBlock *BB) const
Return the innermost loop that BB lives in.
Definition: MachineLoopInfo.h:127
llvm::MachineBasicBlock::getBasicBlock
const BasicBlock * getBasicBlock() const
Return the LLVM basic block that this instance corresponded to originally.
Definition: MachineBasicBlock.h:202
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:158
MCInstrDesc.h
llvm::MachineRegisterInfo
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
Definition: MachineRegisterInfo.h:52
UseBFI::None
@ None
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:530
Pass.h
llvm::BitVector::set
BitVector & set()
Definition: BitVector.h:343
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:391
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:1168
Statistic.h
llvm::RISCVFenceField::W
@ W
Definition: RISCVBaseInfo.h:199
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:195
llvm::printMBBReference
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
Definition: MachineBasicBlock.cpp:119
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::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:143
llvm::MemOp
Definition: TargetLowering.h:112
llvm::MachineRegisterInfo::use_nodbg_instructions
iterator_range< use_instr_nodbg_iterator > use_nodbg_instructions(Register Reg) const
Definition: MachineRegisterInfo.h:543
llvm::TargetRegisterInfo
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
Definition: TargetRegisterInfo.h:233
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")))
DenseMap.h
llvm::MachineRegisterInfo::use_instructions
iterator_range< use_instr_iterator > use_instructions(Register Reg) const
Definition: MachineRegisterInfo.h:485
llvm::reverse
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
Definition: STLExtras.h:333
TargetInstrInfo.h
llvm::MachineMemOperand
A description of a memory reference used in the backend.
Definition: MachineMemOperand.h:128
llvm::SmallSet
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:134
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:109
STLExtras.h
llvm::SmallVectorImpl::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:635
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:1567
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:102
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:90
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:889
AliasAnalysis.h
llvm::TargetSchedModel::init
void init(const TargetSubtargetInfo *TSInfo)
Initialize the machine model for instruction scheduling.
Definition: TargetSchedule.cpp:63
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::AlignStyle::Left
@ Left
llvm::MachineOperand::isKill
bool isKill() const
Definition: MachineOperand.h:390
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:644
llvm::MachineOperand::isImplicit
bool isImplicit() const
Definition: MachineOperand.h:380
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:122
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:508
llvm::AArch64::RP
@ RP
Definition: AArch64ISelLowering.h:475
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::MachineOperand::isUse
bool isUse() const
Definition: MachineOperand.h:370
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.
llvm::LoopBase::end
iterator end() const
Definition: LoopInfo.h:155
false
Definition: StackSlotColoring.cpp:142
PseudoSourceValue.h
TII
const HexagonInstrInfo * TII
Definition: HexagonCopyToCombine.cpp:129
llvm::MCInstrDesc
Describe properties that are true of each instruction in the target description file.
Definition: MCInstrDesc.h:195
llvm::MachineOperand
MachineOperand class - Representation of each machine instruction operand.
Definition: MachineOperand.h:49
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:606
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:34
BitVector.h
DebugLoc.h
llvm::BitVector
Definition: BitVector.h:74
llvm::PseudoSourceValue
Special value supplied for machine level alias analysis.
Definition: PseudoSourceValue.h:35
llvm::None
const NoneType None
Definition: None.h:23
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:560
MCRegister.h
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:95
UseBFI::PGO
@ PGO
llvm::Sched::RegPressure
@ RegPressure
Definition: TargetLowering.h:101
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:634
llvm::MachineRegisterInfo::isSSA
bool isSSA() const
Definition: MachineRegisterInfo.h:185
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:431
llvm::MachineFunction::getSubtarget
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
Definition: MachineFunction.h:634
llvm::RegClassWeight
Each TargetRegisterClass has a per register weight, and weight limit which must be less than the limi...
Definition: TargetRegisterInfo.h:222
llvm::cl::opt< bool >
llvm::MachineLoop
Definition: MachineLoopInfo.h:45
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:164
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:697
isOperandKill
static bool isOperandKill(const MachineOperand &MO, MachineRegisterInfo *MRI)
Definition: MachineLICM.cpp:800
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:111
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:321
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:64
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:169
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
llvm::DenseMap
Definition: DenseMap.h:714
llvm::MachineOperand::isDead
bool isDead() const
Definition: MachineOperand.h:385
I
#define I(x, y, z)
Definition: MD5.cpp:59
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:35
UseBFI
UseBFI
Definition: MachineLICM.cpp:83
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:441
MCRegisterInfo.h
llvm::LoopBase::getLoopPreheader
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:167
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:1616
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:150
llvm::MachineFunction::getName
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
Definition: MachineFunction.cpp:542
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:650
DEBUG_TYPE
#define DEBUG_TYPE
Definition: MachineLICM.cpp:59
llvm::MachineOperand::getReg
Register getReg() const
getReg - Returns the register number.
Definition: MachineOperand.h:360
llvm::Register::asMCReg
MCRegister asMCReg() const
Utility to check-convert this value to a MCRegister.
Definition: Register.h:120
llvm::MachineFunction
Definition: MachineFunction.h:234
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:566
llvm::MachineBasicBlock::getFirstTerminator
iterator getFirstTerminator()
Returns an iterator to the first terminator instruction of this basic block.
Definition: MachineBasicBlock.cpp:242
llvm::min
Expected< ExpressionValue > min(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:357
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:179
llvm::MachineBasicBlock::isEHPad
bool isEHPad() const
Returns true if the block is a landing pad.
Definition: MachineBasicBlock.h:526
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:950
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:419
isInvariantStore
static bool isInvariantStore(const MachineInstr &MI, const TargetRegisterInfo *TRI, const MachineRegisterInfo *MRI)
Definition: MachineLICM.cpp:912
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:672
llvm::MachineOperand::isDef
bool isDef() const
Definition: MachineOperand.h:375
llvm::HexagonInstrInfo::isLoadFromStackSlot
unsigned isLoadFromStackSlot(const MachineInstr &MI, int &FrameIndex) const override
TargetInstrInfo overrides.
Definition: HexagonInstrInfo.cpp:245
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:180
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:59
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:380
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:447
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:595
llvm::MachineFunction::getFunction
Function & getFunction()
Return the LLVM function that this machine code represents.
Definition: MachineFunction.h:600
isCopyFeedingInvariantStore
static bool isCopyFeedingInvariantStore(const MachineInstr &MI, const MachineRegisterInfo *MRI, const TargetRegisterInfo *TRI)
Definition: MachineLICM.cpp:946
llvm::DenseMapBase::end
iterator end()
Definition: DenseMap.h:83
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:1317
MachineFrameInfo.h
Success
#define Success
Definition: AArch64Disassembler.cpp:260
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:303
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:585
llvm::MachineFrameInfo::isSpillSlotObjectIndex
bool isSpillSlotObjectIndex(int ObjectIdx) const
Returns true if the specified index corresponds to a spill slot.
Definition: MachineFrameInfo.h:686
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:323
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:656
llvm::MCRegAliasIterator::isValid
bool isValid() const
Definition: MCRegisterInfo.h:805
llvm::MachineFrameInfo
The MachineFrameInfo class represents an abstract stack frame until prolog/epilog code is inserted.
Definition: MachineFrameInfo.h:107
Machine
COFF::MachineTypes Machine
Definition: COFFYAML.cpp:366
llvm::MachineLoopInfo::begin
iterator begin() const
Definition: MachineLoopInfo.h:121
SmallVector.h
llvm::MachineBasicBlock::begin
iterator begin()
Definition: MachineBasicBlock.h:268
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:71
llvm::AAResultsWrapperPass
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
Definition: AliasAnalysis.h:1336
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:218
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:85
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:43
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:412
raw_ostream.h
llvm::MachineDominatorTree
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
Definition: MachineDominators.h:45
MachineFunction.h
llvm::MachineFunction::eraseCallSiteInfo
void eraseCallSiteInfo(const MachineInstr *MI)
Following functions update call site info.
Definition: MachineFunction.cpp:919
llvm::MachineLoop::isLoopInvariant
bool isLoopInvariant(MachineInstr &I) const
Returns true if the instruction is loop invariant.
Definition: MachineLoopInfo.cpp:155
llvm::MachineInstrBundleIterator< MachineInstr >
true
basic Basic Alias true
Definition: BasicAliasAnalysis.cpp:1894
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:1011
MachineBlockFrequencyInfo.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
TargetRegisterInfo.h
Debug.h
llvm::MachineBasicBlock::end
iterator end()
Definition: MachineBasicBlock.h:270
llvm::MachineRegisterInfo::setRegClass
void setRegClass(Register Reg, const TargetRegisterClass *RC)
setRegClass - Set the register class of the specified virtual register.
Definition: MachineRegisterInfo.cpp:58
llvm::MCRegAliasIterator
MCRegAliasIterator enumerates all registers aliasing Reg.
Definition: MCRegisterInfo.h:780
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