LCOV - code coverage report
Current view: top level - lib/CodeGen - MachineLICM.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 516 528 97.7 %
Date: 2018-07-13 00:08:38 Functions: 47 50 94.0 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.13