LCOV - code coverage report
Current view: top level - lib/CodeGen - MachineLICM.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 469 489 95.9 %
Date: 2018-10-20 13:21:21 Functions: 41 44 93.2 %
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             : AvoidSpeculation("avoid-speculation",
      61             :                  cl::desc("MachineLICM should avoid speculation"),
      62             :                  cl::init(true), cl::Hidden);
      63             : 
      64             : static cl::opt<bool>
      65             : HoistCheapInsts("hoist-cheap-insts",
      66             :                 cl::desc("MachineLICM should hoist even cheap instructions"),
      67             :                 cl::init(false), cl::Hidden);
      68             : 
      69             : static cl::opt<bool>
      70             : SinkInstsToAvoidSpills("sink-insts-to-avoid-spills",
      71             :                        cl::desc("MachineLICM should sink instructions into "
      72             :                                 "loops to avoid register spills"),
      73             :                        cl::init(false), cl::Hidden);
      74             : static cl::opt<bool>
      75             : HoistConstStores("hoist-const-stores",
      76             :                  cl::desc("Hoist invariant stores"),
      77             :                  cl::init(true), cl::Hidden);
      78             : 
      79             : STATISTIC(NumHoisted,
      80             :           "Number of machine instructions hoisted out of loops");
      81             : STATISTIC(NumLowRP,
      82             :           "Number of instructions hoisted in low reg pressure situation");
      83             : STATISTIC(NumHighLatency,
      84             :           "Number of high latency instructions hoisted");
      85             : STATISTIC(NumCSEed,
      86             :           "Number of hoisted machine instructions CSEed");
      87             : STATISTIC(NumPostRAHoisted,
      88             :           "Number of machine instructions hoisted out of loops post regalloc");
      89             : STATISTIC(NumStoreConst,
      90             :           "Number of stores of const phys reg hoisted out of loops");
      91             : 
      92             : namespace {
      93             : 
      94             :   class MachineLICMBase : public MachineFunctionPass {
      95             :     const TargetInstrInfo *TII;
      96             :     const TargetLoweringBase *TLI;
      97             :     const TargetRegisterInfo *TRI;
      98             :     const MachineFrameInfo *MFI;
      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       41777 :     MachineLICMBase(char &PassID, bool PreRegAlloc)
     148       41777 :         : MachineFunctionPass(PassID), PreRegAlloc(PreRegAlloc) {}
     149             : 
     150             :     bool runOnMachineFunction(MachineFunction &MF) override;
     151             : 
     152       41441 :     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       41441 :       MachineFunctionPass::getAnalysisUsage(AU);
     159       41441 :     }
     160             : 
     161      410889 :     void releaseMemory() override {
     162             :       RegSeen.clear();
     163             :       RegPressure.clear();
     164             :       RegLimit.clear();
     165      410889 :       BackTrace.clear();
     166      410889 :       CSEMap.clear();
     167      410889 :     }
     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         381 :         : 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 *HeaderN);
     220             : 
     221             :     void HoistRegion(MachineDomTreeNode *N, bool IsHeader);
     222             : 
     223             :     void SinkIntoLoop();
     224             : 
     225             :     void InitRegPressure(MachineBasicBlock *BB);
     226             : 
     227             :     DenseMap<unsigned, int> calcRegisterCost(const MachineInstr *MI,
     228             :                                              bool ConsiderSeen,
     229             :                                              bool ConsiderUnseenAsDef);
     230             : 
     231             :     void UpdateRegPressure(const MachineInstr *MI,
     232             :                            bool ConsiderUnseenAsDef = false);
     233             : 
     234             :     MachineInstr *ExtractHoistableLoad(MachineInstr *MI);
     235             : 
     236             :     const MachineInstr *
     237             :     LookForDuplicate(const MachineInstr *MI,
     238             :                      std::vector<const MachineInstr *> &PrevMIs);
     239             : 
     240             :     bool EliminateCSE(
     241             :         MachineInstr *MI,
     242             :         DenseMap<unsigned, std::vector<const MachineInstr *>>::iterator &CI);
     243             : 
     244             :     bool MayCSE(MachineInstr *MI);
     245             : 
     246             :     bool Hoist(MachineInstr *MI, MachineBasicBlock *Preheader);
     247             : 
     248             :     void InitCSEMap(MachineBasicBlock *BB);
     249             : 
     250             :     MachineBasicBlock *getCurPreheader();
     251             :   };
     252             : 
     253             :   class MachineLICM : public MachineLICMBase {
     254             :   public:
     255             :     static char ID;
     256       19679 :     MachineLICM() : MachineLICMBase(ID, false) {
     257       19679 :       initializeMachineLICMPass(*PassRegistry::getPassRegistry());
     258       19679 :     }
     259             :   };
     260             : 
     261             :   class EarlyMachineLICM : public MachineLICMBase {
     262             :   public:
     263             :     static char ID;
     264       22098 :     EarlyMachineLICM() : MachineLICMBase(ID, true) {
     265       22098 :       initializeEarlyMachineLICMPass(*PassRegistry::getPassRegistry());
     266       22098 :     }
     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       31780 : INITIALIZE_PASS_BEGIN(MachineLICM, DEBUG_TYPE,
     278             :                       "Machine Loop Invariant Code Motion", false, false)
     279       31780 : INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
     280       31780 : INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
     281       31780 : INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
     282      104826 : INITIALIZE_PASS_END(MachineLICM, DEBUG_TYPE,
     283             :                     "Machine Loop Invariant Code Motion", false, false)
     284             : 
     285       31780 : INITIALIZE_PASS_BEGIN(EarlyMachineLICM, "early-machinelicm",
     286             :                       "Early Machine Loop Invariant Code Motion", false, false)
     287       31780 : INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
     288       31780 : INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
     289       31780 : INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
     290      107245 : 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        7813 : static bool LoopIsOuterMostWithPredecessor(MachineLoop *CurLoop) {
     295             :   // Check whether this loop even has a unique predecessor.
     296        7813 :   if (!CurLoop->getLoopPredecessor())
     297             :     return false;
     298             :   // Ok, now check to see if any of its outer loops do.
     299        7748 :   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      410855 : bool MachineLICMBase::runOnMachineFunction(MachineFunction &MF) {
     307      410855 :   if (skipFunction(MF.getFunction()))
     308             :     return false;
     309             : 
     310      410501 :   Changed = FirstInLoop = false;
     311      410501 :   const TargetSubtargetInfo &ST = MF.getSubtarget();
     312      410501 :   TII = ST.getInstrInfo();
     313      410501 :   TLI = ST.getTargetLowering();
     314      410501 :   TRI = ST.getRegisterInfo();
     315      410501 :   MFI = &MF.getFrameInfo();
     316      410501 :   MRI = &MF.getRegInfo();
     317      410501 :   SchedModel.init(&ST);
     318             : 
     319      410501 :   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      410501 :   if (PreRegAlloc) {
     328             :     // Estimate register pressure during pre-regalloc pass.
     329      216717 :     unsigned NumRPS = TRI->getNumRegPressureSets();
     330      216717 :     RegPressure.resize(NumRPS);
     331             :     std::fill(RegPressure.begin(), RegPressure.end(), 0);
     332      216717 :     RegLimit.resize(NumRPS);
     333     5995613 :     for (unsigned i = 0, e = NumRPS; i != e; ++i)
     334    11557792 :       RegLimit[i] = TRI->getRegPressureSetLimit(MF, i);
     335             :   }
     336             : 
     337             :   // Get our Loop information...
     338      410501 :   MLI = &getAnalysis<MachineLoopInfo>();
     339      410501 :   DT  = &getAnalysis<MachineDominatorTree>();
     340      410501 :   AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
     341             : 
     342      410501 :   SmallVector<MachineLoop *, 8> Worklist(MLI->begin(), MLI->end());
     343      425843 :   while (!Worklist.empty()) {
     344       15342 :     CurLoop = Worklist.pop_back_val();
     345       15342 :     CurPreheader = nullptr;
     346             :     ExitBlocks.clear();
     347             : 
     348             :     // If this is done before regalloc, only visit outer-most preheader-sporting
     349             :     // loops.
     350       15342 :     if (PreRegAlloc && !LoopIsOuterMostWithPredecessor(CurLoop)) {
     351         134 :       Worklist.append(CurLoop->begin(), CurLoop->end());
     352          67 :       continue;
     353             :     }
     354             : 
     355       15275 :     CurLoop->getExitBlocks(ExitBlocks);
     356             : 
     357       15275 :     if (!PreRegAlloc)
     358        7529 :       HoistRegionPostRA();
     359             :     else {
     360             :       // CSEMap is initialized for loop header when the first instruction is
     361             :       // being hoisted.
     362       15492 :       MachineDomTreeNode *N = DT->getNode(CurLoop->getHeader());
     363        7746 :       FirstInLoop = true;
     364        7746 :       HoistOutOfLoop(N);
     365        7746 :       CSEMap.clear();
     366             : 
     367        7746 :       if (SinkInstsToAvoidSpills)
     368           1 :         SinkIntoLoop();
     369             :     }
     370             :   }
     371             : 
     372      410501 :   return Changed;
     373             : }
     374             : 
     375             : /// Return true if instruction stores to the specified frame.
     376        3718 : 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        3718 :   if (!MI->mayStore())
     380             :      return false;
     381             :   // If we lost memory operands, conservatively assume that the instruction
     382             :   // writes to all slots.
     383        1074 :   if (MI->memoperands_empty())
     384             :     return true;
     385        1118 :   for (const MachineMemOperand *MemOp : MI->memoperands()) {
     386        3166 :     if (!MemOp->isStore() || !MemOp->getPseudoValue())
     387             :       continue;
     388             :     if (const FixedStackPseudoSourceValue *Value =
     389             :         dyn_cast<FixedStackPseudoSourceValue>(MemOp->getPseudoValue())) {
     390        1024 :       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      355069 : 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     2012202 :   for (const MachineOperand &MO : MI->operands()) {
     408     1657133 :     if (MO.isFI()) {
     409             :       // Remember if the instruction stores to the frame index.
     410       24564 :       int FI = MO.getIndex();
     411       47413 :       if (!StoredFIs.count(FI) &&
     412       28282 :           MFI->isSpillSlotObjectIndex(FI) &&
     413        3718 :           InstructionStoresToFI(MI, FI))
     414        1027 :         StoredFIs.insert(FI);
     415             :       HasNonInvariantUse = true;
     416             :       continue;
     417             :     }
     418             : 
     419             :     // We can't hoist an instruction defining a physreg that is clobbered in
     420             :     // the loop.
     421     1632569 :     if (MO.isRegMask()) {
     422       11896 :       PhysRegClobbers.setBitsNotInMask(MO.getRegMask());
     423       11896 :       continue;
     424             :     }
     425             : 
     426     1620673 :     if (!MO.isReg())
     427             :       continue;
     428     1059646 :     unsigned Reg = MO.getReg();
     429     1059646 :     if (!Reg)
     430             :       continue;
     431             :     assert(TargetRegisterInfo::isPhysicalRegister(Reg) &&
     432             :            "Not expecting virtual register!");
     433             : 
     434      752962 :     if (!MO.isDef()) {
     435      432592 :       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      432592 :       continue;
     440             :     }
     441             : 
     442      320370 :     if (MO.isImplicit()) {
     443      854980 :       for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI)
     444             :         PhysRegClobbers.set(*AI);
     445      187070 :       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      187070 :       continue;
     451             :     }
     452             : 
     453             :     // FIXME: For now, avoid instructions with multiple defs, unless
     454             :     // it's a dead implicit def.
     455      133300 :     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     1194658 :     for (MCRegAliasIterator AS(Reg, TRI, true); AS.isValid(); ++AS) {
     464     1061358 :       if (PhysRegDefs.test(*AS))
     465             :         PhysRegClobbers.set(*AS);
     466             :       PhysRegDefs.set(*AS);
     467             :     }
     468      133300 :     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      355069 :   if (Def && !RuledOut) {
     477        7880 :     int FI = std::numeric_limits<int>::min();
     478       15422 :     if ((!HasNonInvariantUse && IsLICMCandidate(*MI)) ||
     479        7684 :         (TII->isLoadFromStackSlot(*MI, FI) && MFI->isSpillSlotObjectIndex(FI)))
     480         381 :       Candidates.push_back(CandidateInfo(MI, Def, FI));
     481             :   }
     482      355069 : }
     483             : 
     484             : /// Walk the specified region of the CFG and hoist loop invariants out to the
     485             : /// preheader.
     486        7529 : void MachineLICMBase::HoistRegionPostRA() {
     487        7529 :   MachineBasicBlock *Preheader = getCurPreheader();
     488        7529 :   if (!Preheader)
     489          82 :     return;
     490             : 
     491        7447 :   unsigned NumRegs = TRI->getNumRegs();
     492        7447 :   BitVector PhysRegDefs(NumRegs); // Regs defined once in the loop.
     493        7447 :   BitVector PhysRegClobbers(NumRegs); // Regs defined more than once.
     494             : 
     495        7447 :   SmallVector<CandidateInfo, 32> Candidates;
     496        7447 :   SmallSet<int, 32> StoredFIs;
     497             : 
     498             :   // Walk the entire region, count number of defs for each register, and
     499             :   // collect potential LICM candidates.
     500       47075 :   for (MachineBasicBlock *BB : CurLoop->getBlocks()) {
     501             :     // If the header of the loop containing this basic block is a landing pad,
     502             :     // then don't try to hoist instructions out of this loop.
     503       39628 :     const MachineLoop *ML = MLI->getLoopFor(BB);
     504       39628 :     if (ML && ML->getHeader()->isEHPad()) continue;
     505             : 
     506             :     // Conservatively treat live-in's as an external def.
     507             :     // FIXME: That means a reload that're reused in successor block(s) will not
     508             :     // be LICM'ed.
     509      255168 :     for (const auto &LI : BB->liveins()) {
     510     2394977 :       for (MCRegAliasIterator AI(LI.PhysReg, TRI, true); AI.isValid(); ++AI)
     511             :         PhysRegDefs.set(*AI);
     512             :     }
     513             : 
     514       39628 :     SpeculationState = SpeculateUnknown;
     515      394697 :     for (MachineInstr &MI : *BB)
     516      355069 :       ProcessMI(&MI, PhysRegDefs, PhysRegClobbers, StoredFIs, Candidates);
     517             :   }
     518             : 
     519             :   // Gather the registers read / clobbered by the terminator.
     520        7447 :   BitVector TermRegs(NumRegs);
     521        7447 :   MachineBasicBlock::iterator TI = Preheader->getFirstTerminator();
     522        7447 :   if (TI != Preheader->end()) {
     523        2478 :     for (const MachineOperand &MO : TI->operands()) {
     524        1291 :       if (!MO.isReg())
     525             :         continue;
     526          82 :       unsigned Reg = MO.getReg();
     527          82 :       if (!Reg)
     528             :         continue;
     529         180 :       for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI)
     530             :         TermRegs.set(*AI);
     531             :     }
     532             :   }
     533             : 
     534             :   // Now evaluate whether the potential candidates qualify.
     535             :   // 1. Check if the candidate defined register is defined by another
     536             :   //    instruction in the loop.
     537             :   // 2. If the candidate is a load from stack slot (always true for now),
     538             :   //    check if the slot is stored anywhere in the loop.
     539             :   // 3. Make sure candidate def should not clobber
     540             :   //    registers read by the terminator. Similarly its def should not be
     541             :   //    clobbered by the terminator.
     542        7828 :   for (CandidateInfo &Candidate : Candidates) {
     543         424 :     if (Candidate.FI != std::numeric_limits<int>::min() &&
     544          43 :         StoredFIs.count(Candidate.FI))
     545             :       continue;
     546             : 
     547         366 :     unsigned Def = Candidate.Def;
     548         366 :     if (!PhysRegClobbers.test(Def) && !TermRegs.test(Def)) {
     549             :       bool Safe = true;
     550          43 :       MachineInstr *MI = Candidate.MI;
     551         166 :       for (const MachineOperand &MO : MI->operands()) {
     552         124 :         if (!MO.isReg() || MO.isDef() || !MO.getReg())
     553             :           continue;
     554             :         unsigned Reg = MO.getReg();
     555           3 :         if (PhysRegDefs.test(Reg) ||
     556             :             PhysRegClobbers.test(Reg)) {
     557             :           // If it's using a non-loop-invariant register, then it's obviously
     558             :           // not safe to hoist.
     559             :           Safe = false;
     560             :           break;
     561             :         }
     562             :       }
     563          43 :       if (Safe)
     564          42 :         HoistPostRA(MI, Candidate.Def);
     565             :     }
     566             :   }
     567             : }
     568             : 
     569             : /// Add register 'Reg' to the livein sets of BBs in the current loop, and make
     570             : /// sure it is not killed by any instructions in the loop.
     571           0 : void MachineLICMBase::AddToLiveIns(unsigned Reg) {
     572           0 :   for (MachineBasicBlock *BB : CurLoop->getBlocks()) {
     573           0 :     if (!BB->isLiveIn(Reg))
     574             :       BB->addLiveIn(Reg);
     575           0 :     for (MachineInstr &MI : *BB) {
     576           0 :       for (MachineOperand &MO : MI.operands()) {
     577           0 :         if (!MO.isReg() || !MO.getReg() || MO.isDef()) continue;
     578           0 :         if (MO.getReg() == Reg || TRI->isSuperRegister(Reg, MO.getReg()))
     579             :           MO.setIsKill(false);
     580             :       }
     581             :     }
     582             :   }
     583           0 : }
     584             : 
     585             : /// When an instruction is found to only use loop invariant operands that is
     586             : /// safe to hoist, this instruction is called to do the dirty work.
     587          42 : void MachineLICMBase::HoistPostRA(MachineInstr *MI, unsigned Def) {
     588          42 :   MachineBasicBlock *Preheader = getCurPreheader();
     589             : 
     590             :   // Now move the instructions to the predecessor, inserting it before any
     591             :   // terminator instructions.
     592             :   LLVM_DEBUG(dbgs() << "Hoisting to " << printMBBReference(*Preheader)
     593             :                     << " from " << printMBBReference(*MI->getParent()) << ": "
     594             :                     << *MI);
     595             : 
     596             :   // Splice the instruction to the preheader.
     597          42 :   MachineBasicBlock *MBB = MI->getParent();
     598          42 :   Preheader->splice(Preheader->getFirstTerminator(), MBB, MI);
     599             : 
     600             :   // Add register to livein list to all the BBs in the current loop since a
     601             :   // loop invariant must be kept live throughout the whole loop. This is
     602             :   // important to ensure later passes do not scavenge the def register.
     603          42 :   AddToLiveIns(Def);
     604             : 
     605             :   ++NumPostRAHoisted;
     606          42 :   Changed = true;
     607          42 : }
     608             : 
     609             : /// Check if this mbb is guaranteed to execute. If not then a load from this mbb
     610             : /// may not be safe to hoist.
     611        2992 : bool MachineLICMBase::IsGuaranteedToExecute(MachineBasicBlock *BB) {
     612        2992 :   if (SpeculationState != SpeculateUnknown)
     613        1016 :     return SpeculationState == SpeculateFalse;
     614             : 
     615        3952 :   if (BB != CurLoop->getHeader()) {
     616             :     // Check loop exiting blocks.
     617             :     SmallVector<MachineBasicBlock*, 8> CurrentLoopExitingBlocks;
     618        1635 :     CurLoop->getExitingBlocks(CurrentLoopExitingBlocks);
     619        2115 :     for (MachineBasicBlock *CurrentLoopExitingBlock : CurrentLoopExitingBlocks)
     620        3942 :       if (!DT->dominates(BB, CurrentLoopExitingBlock)) {
     621        1491 :         SpeculationState = SpeculateTrue;
     622             :         return false;
     623             :       }
     624             :   }
     625             : 
     626         485 :   SpeculationState = SpeculateFalse;
     627         485 :   return true;
     628             : }
     629             : 
     630           0 : void MachineLICMBase::EnterScope(MachineBasicBlock *MBB) {
     631             :   LLVM_DEBUG(dbgs() << "Entering " << printMBBReference(*MBB) << '\n');
     632             : 
     633             :   // Remember livein register pressure.
     634           0 :   BackTrace.push_back(RegPressure);
     635           0 : }
     636             : 
     637           0 : void MachineLICMBase::ExitScope(MachineBasicBlock *MBB) {
     638             :   LLVM_DEBUG(dbgs() << "Exiting " << printMBBReference(*MBB) << '\n');
     639       18743 :   BackTrace.pop_back();
     640           0 : }
     641             : 
     642             : /// Destroy scope for the MBB that corresponds to the given dominator tree node
     643             : /// if its a leaf or all of its children are done. Walk up the dominator tree to
     644             : /// destroy ancestors which are now done.
     645       36854 : void MachineLICMBase::ExitScopeIfDone(MachineDomTreeNode *Node,
     646             :     DenseMap<MachineDomTreeNode*, unsigned> &OpenChildren,
     647             :     DenseMap<MachineDomTreeNode*, MachineDomTreeNode*> &ParentMap) {
     648       36854 :   if (OpenChildren[Node])
     649             :     return;
     650             : 
     651             :   // Pop scope.
     652             :   ExitScope(Node->getBlock());
     653             : 
     654             :   // Now traverse upwards to pop ancestors whose offsprings are all done.
     655       18743 :   while (MachineDomTreeNode *Parent = ParentMap[Node]) {
     656       16911 :     unsigned Left = --OpenChildren[Parent];
     657       16911 :     if (Left != 0)
     658             :       break;
     659             :     ExitScope(Parent->getBlock());
     660        6299 :     Node = Parent;
     661        6299 :   }
     662             : }
     663             : 
     664             : /// Walk the specified loop in the CFG (defined by all blocks dominated by the
     665             : /// specified header block, and that are in the current loop) in depth first
     666             : /// order w.r.t the DominatorTree. This allows us to visit definitions before
     667             : /// uses, allowing us to hoist a loop body in one pass without iteration.
     668        7746 : void MachineLICMBase::HoistOutOfLoop(MachineDomTreeNode *HeaderN) {
     669        7746 :   MachineBasicBlock *Preheader = getCurPreheader();
     670        7746 :   if (!Preheader)
     671          18 :     return;
     672             : 
     673             :   SmallVector<MachineDomTreeNode*, 32> Scopes;
     674             :   SmallVector<MachineDomTreeNode*, 8> WorkList;
     675             :   DenseMap<MachineDomTreeNode*, MachineDomTreeNode*> ParentMap;
     676             :   DenseMap<MachineDomTreeNode*, unsigned> OpenChildren;
     677             : 
     678             :   // Perform a DFS walk to determine the order of visit.
     679        7728 :   WorkList.push_back(HeaderN);
     680       60045 :   while (!WorkList.empty()) {
     681       52317 :     MachineDomTreeNode *Node = WorkList.pop_back_val();
     682             :     assert(Node && "Null dominator tree node?");
     683       52317 :     MachineBasicBlock *BB = Node->getBlock();
     684             : 
     685             :     // If the header of the loop containing this basic block is a landing pad,
     686             :     // then don't try to hoist instructions out of this loop.
     687       52317 :     const MachineLoop *ML = MLI->getLoopFor(BB);
     688       36881 :     if (ML && ML->getHeader()->isEHPad())
     689       15463 :       continue;
     690             : 
     691             :     // If this subregion is not in the top level loop at all, exit.
     692       52316 :     if (!CurLoop->contains(BB))
     693             :       continue;
     694             : 
     695       36854 :     Scopes.push_back(Node);
     696       36854 :     const std::vector<MachineDomTreeNode*> &Children = Node->getChildren();
     697       73708 :     unsigned NumChildren = Children.size();
     698             : 
     699             :     // Don't hoist things out of a large switch statement.  This often causes
     700             :     // code to be hoisted that wasn't going to be executed, and increases
     701             :     // register pressure in a situation where it's likely to matter.
     702       36854 :     if (BB->succ_size() >= 25)
     703             :       NumChildren = 0;
     704             : 
     705       36854 :     OpenChildren[Node] = NumChildren;
     706             :     // Add children in reverse order as then the next popped worklist node is
     707             :     // the first child of this node.  This means we ultimately traverse the
     708             :     // DOM tree in exactly the same order as if we'd recursed.
     709       81443 :     for (int i = (int)NumChildren-1; i >= 0; --i) {
     710       89178 :       MachineDomTreeNode *Child = Children[i];
     711       44589 :       ParentMap[Child] = Node;
     712       44589 :       WorkList.push_back(Child);
     713             :     }
     714             :   }
     715             : 
     716        7728 :   if (Scopes.size() == 0)
     717             :     return;
     718             : 
     719             :   // Compute registers which are livein into the loop headers.
     720             :   RegSeen.clear();
     721        7728 :   BackTrace.clear();
     722        7728 :   InitRegPressure(Preheader);
     723             : 
     724             :   // Now perform LICM.
     725       44582 :   for (MachineDomTreeNode *Node : Scopes) {
     726       36854 :     MachineBasicBlock *MBB = Node->getBlock();
     727             : 
     728             :     EnterScope(MBB);
     729             : 
     730             :     // Process the block
     731       36854 :     SpeculationState = SpeculateUnknown;
     732             :     for (MachineBasicBlock::iterator
     733      458355 :          MII = MBB->begin(), E = MBB->end(); MII != E; ) {
     734             :       MachineBasicBlock::iterator NextMII = MII; ++NextMII;
     735             :       MachineInstr *MI = &*MII;
     736      421501 :       if (!Hoist(MI, Preheader))
     737      386417 :         UpdateRegPressure(MI);
     738             :       // If we have hoisted an instruction that may store, it can only be a
     739             :       // constant store.
     740             :       MII = NextMII;
     741             :     }
     742             : 
     743             :     // If it's a leaf node, it's done. Traverse upwards to pop ancestors.
     744       36854 :     ExitScopeIfDone(Node, OpenChildren, ParentMap);
     745             :   }
     746             : }
     747             : 
     748             : /// Sink instructions into loops if profitable. This especially tries to prevent
     749             : /// register spills caused by register pressure if there is little to no
     750             : /// overhead moving instructions into loops.
     751           1 : void MachineLICMBase::SinkIntoLoop() {
     752           1 :   MachineBasicBlock *Preheader = getCurPreheader();
     753           1 :   if (!Preheader)
     754           0 :     return;
     755             : 
     756             :   SmallVector<MachineInstr *, 8> Candidates;
     757             :   for (MachineBasicBlock::instr_iterator I = Preheader->instr_begin();
     758           9 :        I != Preheader->instr_end(); ++I) {
     759             :     // We need to ensure that we can safely move this instruction into the loop.
     760             :     // As such, it must not have side-effects, e.g. such as a call has.
     761           8 :     if (IsLoopInvariantInst(*I) && !HasLoopPHIUse(&*I))
     762           5 :       Candidates.push_back(&*I);
     763             :   }
     764             : 
     765           6 :   for (MachineInstr *I : Candidates) {
     766           5 :     const MachineOperand &MO = I->getOperand(0);
     767           5 :     if (!MO.isDef() || !MO.isReg() || !MO.getReg())
     768             :       continue;
     769           5 :     if (!MRI->hasOneDef(MO.getReg()))
     770             :       continue;
     771             :     bool CanSink = true;
     772             :     MachineBasicBlock *B = nullptr;
     773          10 :     for (MachineInstr &MI : MRI->use_instructions(MO.getReg())) {
     774             :       // FIXME: Come up with a proper cost model that estimates whether sinking
     775             :       // the instruction (and thus possibly executing it on every loop
     776             :       // iteration) is more expensive than a register.
     777             :       // For now assumes that copies are cheap and thus almost always worth it.
     778           5 :       if (!MI.isCopy()) {
     779             :         CanSink = false;
     780             :         break;
     781             :       }
     782           5 :       if (!B) {
     783           5 :         B = MI.getParent();
     784           5 :         continue;
     785             :       }
     786           0 :       B = DT->findNearestCommonDominator(B, MI.getParent());
     787           0 :       if (!B) {
     788             :         CanSink = false;
     789             :         break;
     790             :       }
     791             :     }
     792           5 :     if (!CanSink || !B || B == Preheader)
     793             :       continue;
     794           5 :     B->splice(B->getFirstNonPHI(), Preheader, I);
     795             :   }
     796             : }
     797             : 
     798      342538 : static bool isOperandKill(const MachineOperand &MO, MachineRegisterInfo *MRI) {
     799      342538 :   return MO.isKill() || MRI->hasOneNonDBGUse(MO.getReg());
     800             : }
     801             : 
     802             : /// Find all virtual register references that are liveout of the preheader to
     803             : /// initialize the starting "register pressure". Note this does not count live
     804             : /// through (livein but not used) registers.
     805       11720 : void MachineLICMBase::InitRegPressure(MachineBasicBlock *BB) {
     806             :   std::fill(RegPressure.begin(), RegPressure.end(), 0);
     807             : 
     808             :   // If the preheader has only a single predecessor and it ends with a
     809             :   // fallthrough or an unconditional branch, then scan its predecessor for live
     810             :   // defs as well. This happens whenever the preheader is created by splitting
     811             :   // the critical edge from the loop predecessor to the loop header.
     812       11720 :   if (BB->pred_size() == 1) {
     813        4937 :     MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
     814             :     SmallVector<MachineOperand, 4> Cond;
     815        4937 :     if (!TII->analyzeBranch(*BB, TBB, FBB, Cond, false) && Cond.empty())
     816        3992 :       InitRegPressure(*BB->pred_begin());
     817             :   }
     818             : 
     819      114747 :   for (const MachineInstr &MI : *BB)
     820      103027 :     UpdateRegPressure(&MI, /*ConsiderUnseenAsDef=*/true);
     821       11720 : }
     822             : 
     823             : /// Update estimate of register pressure after the specified instruction.
     824      490160 : void MachineLICMBase::UpdateRegPressure(const MachineInstr *MI,
     825             :                                         bool ConsiderUnseenAsDef) {
     826      490160 :   auto Cost = calcRegisterCost(MI, /*ConsiderSeen=*/true, ConsiderUnseenAsDef);
     827      934510 :   for (const auto &RPIdAndCost : Cost) {
     828      444350 :     unsigned Class = RPIdAndCost.first;
     829      888700 :     if (static_cast<int>(RegPressure[Class]) < -RPIdAndCost.second)
     830           0 :       RegPressure[Class] = 0;
     831             :     else
     832      444350 :       RegPressure[Class] += RPIdAndCost.second;
     833             :   }
     834      490160 : }
     835             : 
     836             : /// Calculate the additional register pressure that the registers used in MI
     837             : /// cause.
     838             : ///
     839             : /// If 'ConsiderSeen' is true, updates 'RegSeen' and uses the information to
     840             : /// figure out which usages are live-ins.
     841             : /// FIXME: Figure out a way to consider 'RegSeen' from all code paths.
     842             : DenseMap<unsigned, int>
     843      517030 : MachineLICMBase::calcRegisterCost(const MachineInstr *MI, bool ConsiderSeen,
     844             :                                   bool ConsiderUnseenAsDef) {
     845             :   DenseMap<unsigned, int> Cost;
     846      517030 :   if (MI->isImplicitDef())
     847             :     return Cost;
     848     2181951 :   for (unsigned i = 0, e = MI->getDesc().getNumOperands(); i != e; ++i) {
     849     1666894 :     const MachineOperand &MO = MI->getOperand(i);
     850     1666894 :     if (!MO.isReg() || MO.isImplicit())
     851     1322335 :       continue;
     852     1007904 :     unsigned Reg = MO.getReg();
     853     1007904 :     if (!TargetRegisterInfo::isVirtualRegister(Reg))
     854             :       continue;
     855             : 
     856             :     // FIXME: It seems bad to use RegSeen only for some of these calculations.
     857      572504 :     bool isNew = ConsiderSeen ? RegSeen.insert(Reg).second : false;
     858      572504 :     const TargetRegisterClass *RC = MRI->getRegClass(Reg);
     859             : 
     860      572504 :     RegClassWeight W = TRI->getRegClassWeight(RC);
     861             :     int RCCost = 0;
     862      572504 :     if (MO.isDef())
     863      229966 :       RCCost = W.RegWeight;
     864             :     else {
     865      342538 :       bool isKill = isOperandKill(MO, MRI);
     866      342538 :       if (isNew && !isKill && ConsiderUnseenAsDef)
     867             :         // Haven't seen this, it must be a livein.
     868        3774 :         RCCost = W.RegWeight;
     869      338764 :       else if (!isNew && isKill)
     870      111478 :         RCCost = -W.RegWeight;
     871             :     }
     872      345218 :     if (RCCost == 0)
     873      227945 :       continue;
     874      344559 :     const int *PS = TRI->getRegClassPressureSets(RC);
     875      947311 :     for (; *PS != -1; ++PS) {
     876      602752 :       if (Cost.find(*PS) == Cost.end())
     877      479914 :         Cost[*PS] = RCCost;
     878             :       else
     879      122838 :         Cost[*PS] += RCCost;
     880             :     }
     881             :   }
     882             :   return Cost;
     883             : }
     884             : 
     885             : /// Return true if this machine instruction loads from global offset table or
     886             : /// constant pool.
     887        2884 : static bool mayLoadFromGOTOrConstantPool(MachineInstr &MI) {
     888             :   assert(MI.mayLoad() && "Expected MI that loads!");
     889             : 
     890             :   // If we lost memory operands, conservatively assume that the instruction
     891             :   // reads from everything..
     892        2884 :   if (MI.memoperands_empty())
     893             :     return true;
     894             : 
     895        3320 :   for (MachineMemOperand *MemOp : MI.memoperands())
     896        2498 :     if (const PseudoSourceValue *PSV = MemOp->getPseudoValue())
     897        2498 :       if (PSV->isGOT() || PSV->isConstantPool())
     898             :         return true;
     899             : 
     900             :   return false;
     901             : }
     902             : 
     903             : // This function iterates through all the operands of the input store MI and
     904             : // checks that each register operand statisfies isCallerPreservedPhysReg.
     905             : // This means, the value being stored and the address where it is being stored
     906             : // is constant throughout the body of the function (not including prologue and
     907             : // epilogue). When called with an MI that isn't a store, it returns false.
     908             : // A future improvement can be to check if the store registers are constant
     909             : // throughout the loop rather than throughout the funtion.
     910      254422 : static bool isInvariantStore(const MachineInstr &MI,
     911             :                              const TargetRegisterInfo *TRI,
     912             :                              const MachineRegisterInfo *MRI) {
     913             : 
     914             :   bool FoundCallerPresReg = false;
     915      254422 :   if (!MI.mayStore() || MI.hasUnmodeledSideEffects() ||
     916       84483 :       (MI.getNumOperands() == 0))
     917      169939 :     return false;
     918             : 
     919             :   // Check that all register operands are caller-preserved physical registers.
     920       84669 :   for (const MachineOperand &MO : MI.operands()) {
     921       84653 :     if (MO.isReg()) {
     922       80526 :       unsigned Reg = MO.getReg();
     923             :       // If operand is a virtual register, check if it comes from a copy of a
     924             :       // physical register.
     925       80526 :       if (TargetRegisterInfo::isVirtualRegister(Reg))
     926       57335 :         Reg = TRI->lookThruCopyLike(MO.getReg(), MRI);
     927       80526 :       if (TargetRegisterInfo::isVirtualRegister(Reg))
     928             :         return false;
     929       34581 :       if (!TRI->isCallerPreservedPhysReg(Reg, *MI.getMF()))
     930             :         return false;
     931             :       else
     932             :         FoundCallerPresReg = true;
     933        4127 :     } else if (!MO.isImm()) {
     934             :         return false;
     935             :     }
     936             :   }
     937             :   return FoundCallerPresReg;
     938             : }
     939             : 
     940             : // Return true if the input MI is a copy instruction that feeds an invariant
     941             : // store instruction. This means that the src of the copy has to satisfy
     942             : // isCallerPreservedPhysReg and atleast one of it's users should satisfy
     943             : // isInvariantStore.
     944       42884 : static bool isCopyFeedingInvariantStore(const MachineInstr &MI,
     945             :                                         const MachineRegisterInfo *MRI,
     946             :                                         const TargetRegisterInfo *TRI) {
     947             : 
     948             :   // FIXME: If targets would like to look through instructions that aren't
     949             :   // pure copies, this can be updated to a query.
     950       42884 :   if (!MI.isCopy())
     951             :     return false;
     952             : 
     953        1146 :   const MachineFunction *MF = MI.getMF();
     954             :   // Check that we are copying a constant physical register.
     955        1146 :   unsigned CopySrcReg = MI.getOperand(1).getReg();
     956        1146 :   if (TargetRegisterInfo::isVirtualRegister(CopySrcReg))
     957             :     return false;
     958             : 
     959          45 :   if (!TRI->isCallerPreservedPhysReg(CopySrcReg, *MF))
     960             :     return false;
     961             : 
     962           8 :   unsigned CopyDstReg = MI.getOperand(0).getReg();
     963             :   // Check if any of the uses of the copy are invariant stores.
     964             :   assert (TargetRegisterInfo::isVirtualRegister(CopyDstReg) &&
     965             :           "copy dst is not a virtual reg");
     966             : 
     967           8 :   for (MachineInstr &UseMI : MRI->use_instructions(CopyDstReg)) {
     968           8 :     if (UseMI.mayStore() && isInvariantStore(UseMI, TRI, MRI))
     969           8 :       return true;
     970             :   }
     971           0 :   return false;
     972             : }
     973             : 
     974             : /// Returns true if the instruction may be a suitable candidate for LICM.
     975             : /// e.g. If the instruction is a call, then it's obviously not safe to hoist it.
     976      423239 : bool MachineLICMBase::IsLICMCandidate(MachineInstr &I) {
     977             :   // Check if it's safe to move the instruction.
     978      423239 :   bool DontMoveAcrossStore = true;
     979      423239 :   if ((!I.isSafeToMove(AA, DontMoveAcrossStore)) &&
     980      254414 :       !(HoistConstStores && isInvariantStore(I, TRI, MRI))) {
     981      254406 :     return false;
     982             :   }
     983             : 
     984             :   // If it is load then check if it is guaranteed to execute by making sure that
     985             :   // it dominates all exiting blocks. If it doesn't, then there is a path out of
     986             :   // the loop which does not execute this load, so we can't hoist it. Loads
     987             :   // from constant memory are not safe to speculate all the time, for example
     988             :   // indexed load from a jump table.
     989             :   // Stores and side effects are already checked by isSafeToMove.
     990      169265 :   if (I.mayLoad() && !mayLoadFromGOTOrConstantPool(I) &&
     991         432 :       !IsGuaranteedToExecute(I.getParent()))
     992         108 :     return false;
     993             : 
     994             :   return true;
     995             : }
     996             : 
     997             : /// Returns true if the instruction is loop invariant.
     998             : /// I.e., all virtual register operands are defined outside of the loop,
     999             : /// physical registers aren't accessed explicitly, and there are no side
    1000             : /// effects that aren't captured by the operands or other flags.
    1001      422258 : bool MachineLICMBase::IsLoopInvariantInst(MachineInstr &I) {
    1002      422258 :   if (!IsLICMCandidate(I))
    1003             :     return false;
    1004             : 
    1005             :   // The instruction is loop invariant if all of its operands are.
    1006      556515 :   for (const MachineOperand &MO : I.operands()) {
    1007      512366 :     if (!MO.isReg())
    1008             :       continue;
    1009             : 
    1010      384235 :     unsigned Reg = MO.getReg();
    1011      384235 :     if (Reg == 0) continue;
    1012             : 
    1013             :     // Don't hoist an instruction that uses or defines a physical register.
    1014      336063 :     if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
    1015      136995 :       if (MO.isUse()) {
    1016             :         // If the physreg has no defs anywhere, it's just an ambient register
    1017             :         // and we can freely move its uses. Alternatively, if it's allocatable,
    1018             :         // it could get allocated to something with a def during allocation.
    1019             :         // However, if the physreg is known to always be caller saved/restored
    1020             :         // then this use is safe to hoist.
    1021       74007 :         if (!MRI->isConstantPhysReg(Reg) &&
    1022       32586 :             !(TRI->isCallerPreservedPhysReg(Reg, *I.getMF())))
    1023             :           return false;
    1024             :         // Otherwise it's safe to move.
    1025        8856 :         continue;
    1026       95574 :       } else if (!MO.isDead()) {
    1027             :         // A def that isn't dead. We can't move it.
    1028             :         return false;
    1029      143520 :       } else if (CurLoop->getHeader()->isLiveIn(Reg)) {
    1030             :         // If the reg is live into the loop, we can't hoist an instruction
    1031             :         // which would clobber it.
    1032             :         return false;
    1033             :       }
    1034             :     }
    1035             : 
    1036      270828 :     if (!MO.isUse())
    1037             :       continue;
    1038             : 
    1039             :     assert(MRI->getVRegDef(Reg) &&
    1040             :            "Machine instr not mapped for this vreg?!");
    1041             : 
    1042             :     // If the loop contains the definition of an operand, then the instruction
    1043             :     // isn't loop invariant.
    1044      166932 :     if (CurLoop->contains(MRI->getVRegDef(Reg)))
    1045             :       return false;
    1046             :   }
    1047             : 
    1048             :   // If we got this far, the instruction is loop invariant!
    1049             :   return true;
    1050             : }
    1051             : 
    1052             : /// Return true if the specified instruction is used by a phi node and hoisting
    1053             : /// it could cause a copy to be inserted.
    1054       42882 : bool MachineLICMBase::HasLoopPHIUse(const MachineInstr *MI) const {
    1055             :   SmallVector<const MachineInstr*, 8> Work(1, MI);
    1056             :   do {
    1057       53147 :     MI = Work.pop_back_val();
    1058      181011 :     for (const MachineOperand &MO : MI->operands()) {
    1059      141311 :       if (!MO.isReg() || !MO.isDef())
    1060             :         continue;
    1061       55287 :       unsigned Reg = MO.getReg();
    1062       55287 :       if (!TargetRegisterInfo::isVirtualRegister(Reg))
    1063             :         continue;
    1064       84383 :       for (MachineInstr &UseMI : MRI->use_instructions(Reg)) {
    1065             :         // A PHI may cause a copy to be inserted.
    1066             :         if (UseMI.isPHI()) {
    1067             :           // A PHI inside the loop causes a copy because the live range of Reg is
    1068             :           // extended across the PHI.
    1069       13452 :           if (CurLoop->contains(&UseMI))
    1070       13447 :             return true;
    1071             :           // A PHI in an exit block can cause a copy to be inserted if the PHI
    1072             :           // has multiple predecessors in the loop with different values.
    1073             :           // For now, approximate by rejecting all exit blocks.
    1074        3232 :           if (isExitBlock(UseMI.getParent()))
    1075             :             return true;
    1076             :           continue;
    1077             :         }
    1078             :         // Look past copies as well.
    1079       40713 :         if (UseMI.isCopy() && CurLoop->contains(&UseMI))
    1080       10322 :           Work.push_back(&UseMI);
    1081             :       }
    1082             :     }
    1083       39700 :   } while (!Work.empty());
    1084             :   return false;
    1085             : }
    1086             : 
    1087             : /// Compute operand latency between a def of 'Reg' and an use in the current
    1088             : /// loop, return true if the target considered it high.
    1089        9712 : bool MachineLICMBase::HasHighOperandLatency(MachineInstr &MI,
    1090             :                                             unsigned DefIdx,
    1091             :                                             unsigned Reg) const {
    1092        9712 :   if (MRI->use_nodbg_empty(Reg))
    1093             :     return false;
    1094             : 
    1095       11680 :   for (MachineInstr &UseMI : MRI->use_nodbg_instructions(Reg)) {
    1096             :     if (UseMI.isCopyLike())
    1097             :       continue;
    1098        8621 :     if (!CurLoop->contains(UseMI.getParent()))
    1099             :       continue;
    1100       50810 :     for (unsigned i = 0, e = UseMI.getNumOperands(); i != e; ++i) {
    1101       42824 :       const MachineOperand &MO = UseMI.getOperand(i);
    1102       42824 :       if (!MO.isReg() || !MO.isUse())
    1103             :         continue;
    1104       20754 :       unsigned MOReg = MO.getReg();
    1105       20754 :       if (MOReg != Reg)
    1106             :         continue;
    1107             : 
    1108        8130 :       if (TII->hasHighOperandLatency(SchedModel, MRI, MI, DefIdx, UseMI, i))
    1109          10 :         return true;
    1110             :     }
    1111             : 
    1112             :     // Only look at the first in loop use.
    1113             :     break;
    1114             :   }
    1115             : 
    1116        9702 :   return false;
    1117             : }
    1118             : 
    1119             : /// Return true if the instruction is marked "cheap" or the operand latency
    1120             : /// between its def and a use is one or less.
    1121       42876 : bool MachineLICMBase::IsCheapInstruction(MachineInstr &MI) const {
    1122       42876 :   if (TII->isAsCheapAsAMove(MI) || MI.isCopyLike())
    1123             :     return true;
    1124             : 
    1125             :   bool isCheap = false;
    1126       25930 :   unsigned NumDefs = MI.getDesc().getNumDefs();
    1127       26233 :   for (unsigned i = 0, e = MI.getNumOperands(); NumDefs && i != e; ++i) {
    1128       25919 :     MachineOperand &DefMO = MI.getOperand(i);
    1129       25919 :     if (!DefMO.isReg() || !DefMO.isDef())
    1130             :       continue;
    1131       25919 :     --NumDefs;
    1132       25919 :     unsigned Reg = DefMO.getReg();
    1133       25919 :     if (TargetRegisterInfo::isPhysicalRegister(Reg))
    1134             :       continue;
    1135             : 
    1136       25919 :     if (!TII->hasLowDefLatency(SchedModel, MI, i))
    1137             :       return false;
    1138             :     isCheap = true;
    1139             :   }
    1140             : 
    1141             :   return isCheap;
    1142             : }
    1143             : 
    1144             : /// Visit BBs from header to current BB, check if hoisting an instruction of the
    1145             : /// given cost matrix can cause high register pressure.
    1146             : bool
    1147        9710 : MachineLICMBase::CanCauseHighRegPressure(const DenseMap<unsigned, int>& Cost,
    1148             :                                          bool CheapInstr) {
    1149       15402 :   for (const auto &RPIdAndCost : Cost) {
    1150       12369 :     if (RPIdAndCost.second <= 0)
    1151             :       continue;
    1152             : 
    1153       10116 :     unsigned Class = RPIdAndCost.first;
    1154       10116 :     int Limit = RegLimit[Class];
    1155             : 
    1156             :     // Don't hoist cheap instructions if they would increase register pressure,
    1157             :     // even if we're under the limit.
    1158       10116 :     if (CheapInstr && !HoistCheapInsts)
    1159        6677 :       return true;
    1160             : 
    1161       32065 :     for (const auto &RP : BackTrace)
    1162       28626 :       if (static_cast<int>(RP[Class]) + RPIdAndCost.second >= Limit)
    1163             :         return true;
    1164             :   }
    1165             : 
    1166        3033 :   return false;
    1167             : }
    1168             : 
    1169             : /// Traverse the back trace from header to the current block and update their
    1170             : /// register pressures to reflect the effect of hoisting MI from the current
    1171             : /// block to the preheader.
    1172       17160 : void MachineLICMBase::UpdateBackTraceRegPressure(const MachineInstr *MI) {
    1173             :   // First compute the 'cost' of the instruction, i.e. its contribution
    1174             :   // to register pressure.
    1175             :   auto Cost = calcRegisterCost(MI, /*ConsiderSeen=*/false,
    1176       17160 :                                /*ConsiderUnseenAsDef=*/false);
    1177             : 
    1178             :   // Update register pressure of blocks from loop header to current block.
    1179      141831 :   for (auto &RP : BackTrace)
    1180      257074 :     for (const auto &RPIdAndCost : Cost)
    1181      264806 :       RP[RPIdAndCost.first] += RPIdAndCost.second;
    1182       17160 : }
    1183             : 
    1184             : /// Return true if it is potentially profitable to hoist the given loop
    1185             : /// invariant.
    1186       44143 : bool MachineLICMBase::IsProfitableToHoist(MachineInstr &MI) {
    1187       44143 :   if (MI.isImplicitDef())
    1188             :     return true;
    1189             : 
    1190             :   // Besides removing computation from the loop, hoisting an instruction has
    1191             :   // these effects:
    1192             :   //
    1193             :   // - The value defined by the instruction becomes live across the entire
    1194             :   //   loop. This increases register pressure in the loop.
    1195             :   //
    1196             :   // - If the value is used by a PHI in the loop, a copy will be required for
    1197             :   //   lowering the PHI after extending the live range.
    1198             :   //
    1199             :   // - When hoisting the last use of a value in the loop, that value no longer
    1200             :   //   needs to be live in the loop. This lowers register pressure in the loop.
    1201             : 
    1202       42884 :   if (HoistConstStores &&  isCopyFeedingInvariantStore(MI, MRI, TRI))
    1203             :     return true;
    1204             : 
    1205       42876 :   bool CheapInstr = IsCheapInstruction(MI);
    1206       42876 :   bool CreatesCopy = HasLoopPHIUse(&MI);
    1207             : 
    1208             :   // Don't hoist a cheap instruction if it would create a copy in the loop.
    1209       42876 :   if (CheapInstr && CreatesCopy) {
    1210             :     LLVM_DEBUG(dbgs() << "Won't hoist cheap instr with loop PHI use: " << MI);
    1211             :     return false;
    1212             :   }
    1213             : 
    1214             :   // Rematerializable instructions should always be hoisted since the register
    1215             :   // allocator can just pull them down again when needed.
    1216       40456 :   if (TII->isTriviallyReMaterializable(MI, AA))
    1217             :     return true;
    1218             : 
    1219             :   // FIXME: If there are long latency loop-invariant instructions inside the
    1220             :   // loop at this point, why didn't the optimizer's LICM hoist them?
    1221       58556 :   for (unsigned i = 0, e = MI.getDesc().getNumOperands(); i != e; ++i) {
    1222       48846 :     const MachineOperand &MO = MI.getOperand(i);
    1223       48846 :     if (!MO.isReg() || MO.isImplicit())
    1224             :       continue;
    1225       33086 :     unsigned Reg = MO.getReg();
    1226       33086 :     if (!TargetRegisterInfo::isVirtualRegister(Reg))
    1227             :       continue;
    1228       19614 :     if (MO.isDef() && HasHighOperandLatency(MI, i, Reg)) {
    1229             :       LLVM_DEBUG(dbgs() << "Hoist High Latency: " << MI);
    1230             :       ++NumHighLatency;
    1231             :       return true;
    1232             :     }
    1233             :   }
    1234             : 
    1235             :   // Estimate register pressure to determine whether to LICM the instruction.
    1236             :   // In low register pressure situation, we can be more aggressive about
    1237             :   // hoisting. Also, favors hoisting long latency instructions even in
    1238             :   // moderately high pressure situation.
    1239             :   // Cheap instructions will only be hoisted if they don't increase register
    1240             :   // pressure at all.
    1241             :   auto Cost = calcRegisterCost(&MI, /*ConsiderSeen=*/false,
    1242        9710 :                                /*ConsiderUnseenAsDef=*/false);
    1243             : 
    1244             :   // Visit BBs from header to current BB, if hoisting this doesn't cause
    1245             :   // high register pressure, then it's safe to proceed.
    1246        9710 :   if (!CanCauseHighRegPressure(Cost, CheapInstr)) {
    1247             :     LLVM_DEBUG(dbgs() << "Hoist non-reg-pressure: " << MI);
    1248             :     ++NumLowRP;
    1249             :     return true;
    1250             :   }
    1251             : 
    1252             :   // Don't risk increasing register pressure if it would create copies.
    1253        6677 :   if (CreatesCopy) {
    1254             :     LLVM_DEBUG(dbgs() << "Won't hoist instr with loop PHI use: " << MI);
    1255             :     return false;
    1256             :   }
    1257             : 
    1258             :   // Do not "speculate" in high register pressure situation. If an
    1259             :   // instruction is not guaranteed to be executed in the loop, it's best to be
    1260             :   // conservative.
    1261        5120 :   if (AvoidSpeculation &&
    1262        4516 :       (!IsGuaranteedToExecute(MI.getParent()) && !MayCSE(&MI))) {
    1263             :     LLVM_DEBUG(dbgs() << "Won't speculate: " << MI);
    1264             :     return false;
    1265             :   }
    1266             : 
    1267             :   // High register pressure situation, only hoist if the instruction is going
    1268             :   // to be remat'ed.
    1269        2110 :   if (!TII->isTriviallyReMaterializable(MI, AA) &&
    1270        1055 :       !MI.isDereferenceableInvariantLoad(AA)) {
    1271             :     LLVM_DEBUG(dbgs() << "Can't remat / high reg-pressure: " << MI);
    1272        1017 :     return false;
    1273             :   }
    1274             : 
    1275             :   return true;
    1276             : }
    1277             : 
    1278             : /// Unfold a load from the given machineinstr if the load itself could be
    1279             : /// hoisted. Return the unfolded and hoistable load, or null if the load
    1280             : /// couldn't be unfolded or if it wouldn't be hoistable.
    1281      387133 : MachineInstr *MachineLICMBase::ExtractHoistableLoad(MachineInstr *MI) {
    1282             :   // Don't unfold simple loads.
    1283      387133 :   if (MI->canFoldAsLoad())
    1284             :     return nullptr;
    1285             : 
    1286             :   // If not, we may be able to unfold a load and hoist that.
    1287             :   // First test whether the instruction is loading from an amenable
    1288             :   // memory location.
    1289      357551 :   if (!MI->isDereferenceableInvariantLoad(AA))
    1290             :     return nullptr;
    1291             : 
    1292             :   // Next determine the register class for a temporary register.
    1293             :   unsigned LoadRegIndex;
    1294             :   unsigned NewOpc =
    1295         865 :     TII->getOpcodeAfterMemoryUnfold(MI->getOpcode(),
    1296             :                                     /*UnfoldLoad=*/true,
    1297             :                                     /*UnfoldStore=*/false,
    1298         865 :                                     &LoadRegIndex);
    1299         865 :   if (NewOpc == 0) return nullptr;
    1300         749 :   const MCInstrDesc &MID = TII->get(NewOpc);
    1301             :   MachineFunction &MF = *MI->getMF();
    1302         749 :   const TargetRegisterClass *RC = TII->getRegClass(MID, LoadRegIndex, TRI, MF);
    1303             :   // Ok, we're unfolding. Create a temporary register and do the unfold.
    1304        1498 :   unsigned Reg = MRI->createVirtualRegister(RC);
    1305             : 
    1306             :   SmallVector<MachineInstr *, 2> NewMIs;
    1307        1498 :   bool Success = TII->unfoldMemoryOperand(MF, *MI, Reg,
    1308             :                                           /*UnfoldLoad=*/true,
    1309         749 :                                           /*UnfoldStore=*/false, NewMIs);
    1310             :   (void)Success;
    1311             :   assert(Success &&
    1312             :          "unfoldMemoryOperand failed when getOpcodeAfterMemoryUnfold "
    1313             :          "succeeded!");
    1314             :   assert(NewMIs.size() == 2 &&
    1315             :          "Unfolded a load into multiple instructions!");
    1316         749 :   MachineBasicBlock *MBB = MI->getParent();
    1317             :   MachineBasicBlock::iterator Pos = MI;
    1318         749 :   MBB->insert(Pos, NewMIs[0]);
    1319         749 :   MBB->insert(Pos, NewMIs[1]);
    1320             :   // If unfolding produced a load that wasn't loop-invariant or profitable to
    1321             :   // hoist, discard the new instructions and bail.
    1322         749 :   if (!IsLoopInvariantInst(*NewMIs[0]) || !IsProfitableToHoist(*NewMIs[0])) {
    1323          33 :     NewMIs[0]->eraseFromParent();
    1324          33 :     NewMIs[1]->eraseFromParent();
    1325          33 :     return nullptr;
    1326             :   }
    1327             : 
    1328             :   // Update register pressure for the unfolded instruction.
    1329         716 :   UpdateRegPressure(NewMIs[1]);
    1330             : 
    1331             :   // Otherwise we successfully unfolded a load that we can hoist.
    1332         716 :   MI->eraseFromParent();
    1333         716 :   return NewMIs[0];
    1334             : }
    1335             : 
    1336             : /// Initialize the CSE map with instructions that are in the current loop
    1337             : /// preheader that may become duplicates of instructions that are hoisted
    1338             : /// out of the loop.
    1339        3696 : void MachineLICMBase::InitCSEMap(MachineBasicBlock *BB) {
    1340       35272 :   for (MachineInstr &MI : *BB)
    1341       63152 :     CSEMap[MI.getOpcode()].push_back(&MI);
    1342        3696 : }
    1343             : 
    1344             : /// Find an instruction amount PrevMIs that is a duplicate of MI.
    1345             : /// Return this instruction if it's found.
    1346             : const MachineInstr*
    1347       30859 : MachineLICMBase::LookForDuplicate(const MachineInstr *MI,
    1348             :                                   std::vector<const MachineInstr*> &PrevMIs) {
    1349      282094 :   for (const MachineInstr *PrevMI : PrevMIs)
    1350      269610 :     if (TII->produceSameValue(*MI, *PrevMI, (PreRegAlloc ? MRI : nullptr)))
    1351             :       return PrevMI;
    1352             : 
    1353             :   return nullptr;
    1354             : }
    1355             : 
    1356             : /// Given a LICM'ed instruction, look for an instruction on the preheader that
    1357             : /// computes the same value. If it's found, do a RAU on with the definition of
    1358             : /// the existing instruction rather than hoisting the instruction to the
    1359             : /// preheader.
    1360       35084 : bool MachineLICMBase::EliminateCSE(MachineInstr *MI,
    1361             :     DenseMap<unsigned, std::vector<const MachineInstr *>>::iterator &CI) {
    1362             :   // Do not CSE implicit_def so ProcessImplicitDefs can properly propagate
    1363             :   // the undef property onto uses.
    1364       35084 :   if (CI == CSEMap.end() || MI->isImplicitDef())
    1365        5885 :     return false;
    1366             : 
    1367       29199 :   if (const MachineInstr *Dup = LookForDuplicate(MI, CI->second)) {
    1368             :     LLVM_DEBUG(dbgs() << "CSEing " << *MI << " with " << *Dup);
    1369             : 
    1370             :     // Replace virtual registers defined by MI by their counterparts defined
    1371             :     // by Dup.
    1372             :     SmallVector<unsigned, 2> Defs;
    1373       82484 :     for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
    1374       64560 :       const MachineOperand &MO = MI->getOperand(i);
    1375             : 
    1376             :       // Physical registers may not differ here.
    1377             :       assert((!MO.isReg() || MO.getReg() == 0 ||
    1378             :               !TargetRegisterInfo::isPhysicalRegister(MO.getReg()) ||
    1379             :               MO.getReg() == Dup->getOperand(i).getReg()) &&
    1380             :              "Instructions with different phys regs are not identical!");
    1381             : 
    1382       64560 :       if (MO.isReg() && MO.isDef() &&
    1383       19275 :           !TargetRegisterInfo::isPhysicalRegister(MO.getReg()))
    1384       17924 :         Defs.push_back(i);
    1385             :     }
    1386             : 
    1387             :     SmallVector<const TargetRegisterClass*, 2> OrigRCs;
    1388       35848 :     for (unsigned i = 0, e = Defs.size(); i != e; ++i) {
    1389       17924 :       unsigned Idx = Defs[i];
    1390       17924 :       unsigned Reg = MI->getOperand(Idx).getReg();
    1391       17924 :       unsigned DupReg = Dup->getOperand(Idx).getReg();
    1392       35848 :       OrigRCs.push_back(MRI->getRegClass(DupReg));
    1393             : 
    1394       35848 :       if (!MRI->constrainRegClass(DupReg, MRI->getRegClass(Reg))) {
    1395             :         // Restore old RCs if more than one defs.
    1396           0 :         for (unsigned j = 0; j != i; ++j)
    1397           0 :           MRI->setRegClass(Dup->getOperand(Defs[j]).getReg(), OrigRCs[j]);
    1398             :         return false;
    1399             :       }
    1400             :     }
    1401             : 
    1402       35848 :     for (unsigned Idx : Defs) {
    1403       17924 :       unsigned Reg = MI->getOperand(Idx).getReg();
    1404       17924 :       unsigned DupReg = Dup->getOperand(Idx).getReg();
    1405       17924 :       MRI->replaceRegWith(Reg, DupReg);
    1406       17924 :       MRI->clearKillFlags(DupReg);
    1407             :     }
    1408             : 
    1409       17924 :     MI->eraseFromParent();
    1410             :     ++NumCSEed;
    1411       17924 :     return true;
    1412             :   }
    1413             :   return false;
    1414             : }
    1415             : 
    1416             : /// Return true if the given instruction will be CSE'd if it's hoisted out of
    1417             : /// the loop.
    1418        1956 : bool MachineLICMBase::MayCSE(MachineInstr *MI) {
    1419        1956 :   unsigned Opcode = MI->getOpcode();
    1420             :   DenseMap<unsigned, std::vector<const MachineInstr *>>::iterator
    1421        1956 :     CI = CSEMap.find(Opcode);
    1422             :   // Do not CSE implicit_def so ProcessImplicitDefs can properly propagate
    1423             :   // the undef property onto uses.
    1424        1956 :   if (CI == CSEMap.end() || MI->isImplicitDef())
    1425         296 :     return false;
    1426             : 
    1427        1660 :   return LookForDuplicate(MI, CI->second) != nullptr;
    1428             : }
    1429             : 
    1430             : /// When an instruction is found to use only loop invariant operands
    1431             : /// that are safe to hoist, this instruction is called to do the dirty work.
    1432             : /// It returns true if the instruction is hoisted.
    1433      421501 : bool MachineLICMBase::Hoist(MachineInstr *MI, MachineBasicBlock *Preheader) {
    1434             :   // First check whether we should hoist this instruction.
    1435      421501 :   if (!IsLoopInvariantInst(*MI) || !IsProfitableToHoist(*MI)) {
    1436             :     // If not, try unfolding a hoistable load.
    1437      387133 :     MI = ExtractHoistableLoad(MI);
    1438      387133 :     if (!MI) return false;
    1439             :   }
    1440             : 
    1441             :   // If we have hoisted an instruction that may store, it can only be a constant
    1442             :   // store.
    1443       35084 :   if (MI->mayStore())
    1444             :     NumStoreConst++;
    1445             : 
    1446             :   // Now move the instructions to the predecessor, inserting it before any
    1447             :   // terminator instructions.
    1448             :   LLVM_DEBUG({
    1449             :     dbgs() << "Hoisting " << *MI;
    1450             :     if (MI->getParent()->getBasicBlock())
    1451             :       dbgs() << " from " << printMBBReference(*MI->getParent());
    1452             :     if (Preheader->getBasicBlock())
    1453             :       dbgs() << " to " << printMBBReference(*Preheader);
    1454             :     dbgs() << "\n";
    1455             :   });
    1456             : 
    1457             :   // If this is the first instruction being hoisted to the preheader,
    1458             :   // initialize the CSE map with potential common expressions.
    1459       35084 :   if (FirstInLoop) {
    1460        3696 :     InitCSEMap(Preheader);
    1461        3696 :     FirstInLoop = false;
    1462             :   }
    1463             : 
    1464             :   // Look for opportunity to CSE the hoisted instruction.
    1465       35084 :   unsigned Opcode = MI->getOpcode();
    1466             :   DenseMap<unsigned, std::vector<const MachineInstr *>>::iterator
    1467       35084 :     CI = CSEMap.find(Opcode);
    1468       35084 :   if (!EliminateCSE(MI, CI)) {
    1469             :     // Otherwise, splice the instruction to the preheader.
    1470       17160 :     Preheader->splice(Preheader->getFirstTerminator(),MI->getParent(),MI);
    1471             : 
    1472             :     // Since we are moving the instruction out of its basic block, we do not
    1473             :     // retain its debug location. Doing so would degrade the debugging
    1474             :     // experience and adversely affect the accuracy of profiling information.
    1475       17160 :     MI->setDebugLoc(DebugLoc());
    1476             : 
    1477             :     // Update register pressure for BBs from header to this block.
    1478       17160 :     UpdateBackTraceRegPressure(MI);
    1479             : 
    1480             :     // Clear the kill flags of any register this instruction defines,
    1481             :     // since they may need to be live throughout the entire loop
    1482             :     // rather than just live for part of it.
    1483       91384 :     for (MachineOperand &MO : MI->operands())
    1484       74224 :       if (MO.isReg() && MO.isDef() && !MO.isDead())
    1485       17155 :         MRI->clearKillFlags(MO.getReg());
    1486             : 
    1487             :     // Add to the CSE map.
    1488       17160 :     if (CI != CSEMap.end())
    1489       12008 :       CI->second.push_back(MI);
    1490             :     else
    1491        5152 :       CSEMap[Opcode].push_back(MI);
    1492             :   }
    1493             : 
    1494             :   ++NumHoisted;
    1495       35084 :   Changed = true;
    1496             : 
    1497       35084 :   return true;
    1498             : }
    1499             : 
    1500             : /// Get the preheader for the current loop, splitting a critical edge if needed.
    1501       15318 : MachineBasicBlock *MachineLICMBase::getCurPreheader() {
    1502             :   // Determine the block to which to hoist instructions. If we can't find a
    1503             :   // suitable loop predecessor, we can't do any hoisting.
    1504             : 
    1505             :   // If we've tried to get a preheader and failed, don't try again.
    1506       15318 :   if (CurPreheader == reinterpret_cast<MachineBasicBlock *>(-1))
    1507             :     return nullptr;
    1508             : 
    1509       15318 :   if (!CurPreheader) {
    1510       15275 :     CurPreheader = CurLoop->getLoopPreheader();
    1511       15275 :     if (!CurPreheader) {
    1512         426 :       MachineBasicBlock *Pred = CurLoop->getLoopPredecessor();
    1513         426 :       if (!Pred) {
    1514          64 :         CurPreheader = reinterpret_cast<MachineBasicBlock *>(-1);
    1515          64 :         return nullptr;
    1516             :       }
    1517             : 
    1518         724 :       CurPreheader = Pred->SplitCriticalEdge(CurLoop->getHeader(), *this);
    1519         362 :       if (!CurPreheader) {
    1520          36 :         CurPreheader = reinterpret_cast<MachineBasicBlock *>(-1);
    1521          36 :         return nullptr;
    1522             :       }
    1523             :     }
    1524             :   }
    1525       15218 :   return CurPreheader;
    1526             : }

Generated by: LCOV version 1.13