lib/CodeGen/MachineLICM.cpp

   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 does not attempt to throttle itself to limit register pressure.
  14 // The register allocation phases are expected to perform rematerialization
  15 // to recover when register pressure is high.
  16 //
  17 // This pass is not intended to be a replacement or a complete alternative
  18 // for the LLVM-IR-level LICM pass. It is only designed to hoist simple
  19 // constructs that are not exposed before lowering and instruction selection.
  20 //
  21 //===----------------------------------------------------------------------===//
  22
  23 #include "llvm/CodeGen/Passes.h"
  24 #include "llvm/ADT/DenseMap.h"
  25 #include "llvm/ADT/SmallSet.h"
  26 #include "llvm/ADT/Statistic.h"
  27 #include "llvm/Analysis/AliasAnalysis.h"
  28 #include "llvm/CodeGen/MachineDominators.h"
  29 #include "llvm/CodeGen/MachineFrameInfo.h"
  30 #include "llvm/CodeGen/MachineLoopInfo.h"
  31 #include "llvm/CodeGen/MachineMemOperand.h"
  32 #include "llvm/CodeGen/MachineRegisterInfo.h"
  33 #include "llvm/CodeGen/PseudoSourceValue.h"
  34 #include "llvm/MC/MCInstrItineraries.h"
  35 #include "llvm/Support/CommandLine.h"
  36 #include "llvm/Support/Debug.h"
  37 #include "llvm/Support/raw_ostream.h"
  38 #include "llvm/Target/TargetInstrInfo.h"
  39 #include "llvm/Target/TargetLowering.h"
  40 #include "llvm/Target/TargetMachine.h"
  41 #include "llvm/Target/TargetRegisterInfo.h"
  42 #include "llvm/Target/TargetSubtargetInfo.h"
  43 using namespace llvm;
  44
  45 #define DEBUG_TYPE "machine-licm"
  46
  47 static cl::opt<bool>
  48 AvoidSpeculation("avoid-speculation",
  49                  cl::desc("MachineLICM should avoid speculation"),
  50                  cl::init(true), cl::Hidden);
  51
  52 STATISTIC(NumHoisted,
  53           "Number of machine instructions hoisted out of loops");
  54 STATISTIC(NumLowRP,
  55           "Number of instructions hoisted in low reg pressure situation");
  56 STATISTIC(NumHighLatency,
  57           "Number of high latency instructions hoisted");
  58 STATISTIC(NumCSEed,
  59           "Number of hoisted machine instructions CSEed");
  60 STATISTIC(NumPostRAHoisted,
  61           "Number of machine instructions hoisted out of loops post regalloc");
  62
  63 namespace {
  64   class MachineLICM : public MachineFunctionPass {
  65     const TargetMachine   *TM;
  66     const TargetInstrInfo *TII;
  67     const TargetLoweringBase *TLI;
  68     const TargetRegisterInfo *TRI;
  69     const MachineFrameInfo *MFI;
  70     MachineRegisterInfo *MRI;
  71     const InstrItineraryData *InstrItins;
  72     bool PreRegAlloc;
  73
  74     // Various analyses that we use...
  75     AliasAnalysis        *AA;      // Alias analysis info.
  76     MachineLoopInfo      *MLI;     // Current MachineLoopInfo
  77     MachineDominatorTree *DT;      // Machine dominator tree for the cur loop
  78
  79     // State that is updated as we process loops
  80     bool         Changed;          // True if a loop is changed.
  81     bool         FirstInLoop;      // True if it's the first LICM in the loop.
  82     MachineLoop *CurLoop;          // The current loop we are working on.
  83     MachineBasicBlock *CurPreheader; // The preheader for CurLoop.
  84
  85     // Exit blocks for CurLoop.
  86     SmallVector<MachineBasicBlock*, 8> ExitBlocks;
  87
  88     bool isExitBlock(const MachineBasicBlock *MBB) const {
  89       return std::find(ExitBlocks.begin(), ExitBlocks.end(), MBB) !=
  90         ExitBlocks.end();
  91     }
  92
  93     // Track 'estimated' register pressure.
  94     SmallSet<unsigned, 32> RegSeen;
  95     SmallVector<unsigned, 8> RegPressure;
  96
  97     // Register pressure "limit" per register class. If the pressure
  98     // is higher than the limit, then it's considered high.
  99     SmallVector<unsigned, 8> RegLimit;
 100
 101     // Register pressure on path leading from loop preheader to current BB.
 102     SmallVector<SmallVector<unsigned, 8>, 16> BackTrace;
 103
 104     // For each opcode, keep a list of potential CSE instructions.
 105     DenseMap<unsigned, std::vector<const MachineInstr*> > CSEMap;
 106
 107     enum {
 108       SpeculateFalse   = 0,
 109       SpeculateTrue    = 1,
 110       SpeculateUnknown = 2
 111     };
 112
 113     // If a MBB does not dominate loop exiting blocks then it may not safe
 114     // to hoist loads from this block.
 115     // Tri-state: 0 - false, 1 - true, 2 - unknown
 116     unsigned SpeculationState;
 117
 118   public:
 119     static char ID; // Pass identification, replacement for typeid
 120     MachineLICM() :
 121       MachineFunctionPass(ID), PreRegAlloc(true) {
 122         initializeMachineLICMPass(*PassRegistry::getPassRegistry());
 123       }
 124
 125     explicit MachineLICM(bool PreRA) :
 126       MachineFunctionPass(ID), PreRegAlloc(PreRA) {
 127         initializeMachineLICMPass(*PassRegistry::getPassRegistry());
 128       }
 129
 130     bool runOnMachineFunction(MachineFunction &MF) override;
 131
 132     void getAnalysisUsage(AnalysisUsage &AU) const override {
 133       AU.addRequired<MachineLoopInfo>();
 134       AU.addRequired<MachineDominatorTree>();
 135       AU.addRequired<AliasAnalysis>();
 136       AU.addPreserved<MachineLoopInfo>();
 137       AU.addPreserved<MachineDominatorTree>();
 138       MachineFunctionPass::getAnalysisUsage(AU);
 139     }
 140
 141     void releaseMemory() override {
 142       RegSeen.clear();
 143       RegPressure.clear();
 144       RegLimit.clear();
 145       BackTrace.clear();
 146       for (DenseMap<unsigned,std::vector<const MachineInstr*> >::iterator
 147              CI = CSEMap.begin(), CE = CSEMap.end(); CI != CE; ++CI)
 148         CI->second.clear();
 149       CSEMap.clear();
 150     }
 151
 152   private:
 153     /// CandidateInfo - Keep track of information about hoisting candidates.
 154     struct CandidateInfo {
 155       MachineInstr *MI;
 156       unsigned      Def;
 157       int           FI;
 158       CandidateInfo(MachineInstr *mi, unsigned def, int fi)
 159         : MI(mi), Def(def), FI(fi) {}
 160     };
 161
 162     /// HoistRegionPostRA - Walk the specified region of the CFG and hoist loop
 163     /// invariants out to the preheader.
 164     void HoistRegionPostRA();
 165
 166     /// HoistPostRA - When an instruction is found to only use loop invariant
 167     /// operands that is safe to hoist, this instruction is called to do the
 168     /// dirty work.
 169     void HoistPostRA(MachineInstr *MI, unsigned Def);
 170
 171     /// ProcessMI - Examine the instruction for potentai LICM candidate. Also
 172     /// gather register def and frame object update information.
 173     void ProcessMI(MachineInstr *MI,
 174                    BitVector &PhysRegDefs,
 175                    BitVector &PhysRegClobbers,
 176                    SmallSet<int, 32> &StoredFIs,
 177                    SmallVectorImpl<CandidateInfo> &Candidates);
 178
 179     /// AddToLiveIns - Add register 'Reg' to the livein sets of BBs in the
 180     /// current loop.
 181     void AddToLiveIns(unsigned Reg);
 182
 183     /// IsLICMCandidate - Returns true if the instruction may be a suitable
 184     /// candidate for LICM. e.g. If the instruction is a call, then it's
 185     /// obviously not safe to hoist it.
 186     bool IsLICMCandidate(MachineInstr &I);
 187
 188     /// IsLoopInvariantInst - Returns true if the instruction is loop
 189     /// invariant. I.e., all virtual register operands are defined outside of
 190     /// the loop, physical registers aren't accessed (explicitly or implicitly),
 191     /// and the instruction is hoistable.
 192     ///
 193     bool IsLoopInvariantInst(MachineInstr &I);
 194
 195     /// HasLoopPHIUse - Return true if the specified instruction is used by any
 196     /// phi node in the current loop.
 197     bool HasLoopPHIUse(const MachineInstr *MI) const;
 198
 199     /// HasHighOperandLatency - Compute operand latency between a def of 'Reg'
 200     /// and an use in the current loop, return true if the target considered
 201     /// it 'high'.
 202     bool HasHighOperandLatency(MachineInstr &MI, unsigned DefIdx,
 203                                unsigned Reg) const;
 204
 205     bool IsCheapInstruction(MachineInstr &MI) const;
 206
 207     /// CanCauseHighRegPressure - Visit BBs from header to current BB,
 208     /// check if hoisting an instruction of the given cost matrix can cause high
 209     /// register pressure.
 210     bool CanCauseHighRegPressure(DenseMap<unsigned, int> &Cost, bool Cheap);
 211
 212     /// UpdateBackTraceRegPressure - Traverse the back trace from header to
 213     /// the current block and update their register pressures to reflect the
 214     /// effect of hoisting MI from the current block to the preheader.
 215     void UpdateBackTraceRegPressure(const MachineInstr *MI);
 216
 217     /// IsProfitableToHoist - Return true if it is potentially profitable to
 218     /// hoist the given loop invariant.
 219     bool IsProfitableToHoist(MachineInstr &MI);
 220
 221     /// IsGuaranteedToExecute - Check if this mbb is guaranteed to execute.
 222     /// If not then a load from this mbb may not be safe to hoist.
 223     bool IsGuaranteedToExecute(MachineBasicBlock *BB);
 224
 225     void EnterScope(MachineBasicBlock *MBB);
 226
 227     void ExitScope(MachineBasicBlock *MBB);
 228
 229     /// ExitScopeIfDone - Destroy scope for the MBB that corresponds to given
 230     /// dominator tree node if its a leaf or all of its children are done. Walk
 231     /// up the dominator tree to destroy ancestors which are now done.
 232     void ExitScopeIfDone(MachineDomTreeNode *Node,
 233                 DenseMap<MachineDomTreeNode*, unsigned> &OpenChildren,
 234                 DenseMap<MachineDomTreeNode*, MachineDomTreeNode*> &ParentMap);
 235
 236     /// HoistOutOfLoop - Walk the specified loop in the CFG (defined by all
 237     /// blocks dominated by the specified header block, and that are in the
 238     /// current loop) in depth first order w.r.t the DominatorTree. This allows
 239     /// us to visit definitions before uses, allowing us to hoist a loop body in
 240     /// one pass without iteration.
 241     ///
 242     void HoistOutOfLoop(MachineDomTreeNode *LoopHeaderNode);
 243     void HoistRegion(MachineDomTreeNode *N, bool IsHeader);
 244
 245     /// getRegisterClassIDAndCost - For a given MI, register, and the operand
 246     /// index, return the ID and cost of its representative register class by
 247     /// reference.
 248     void getRegisterClassIDAndCost(const MachineInstr *MI,
 249                                    unsigned Reg, unsigned OpIdx,
 250                                    unsigned &RCId, unsigned &RCCost) const;
 251
 252     /// InitRegPressure - Find all virtual register references that are liveout
 253     /// of the preheader to initialize the starting "register pressure". Note
 254     /// this does not count live through (livein but not used) registers.
 255     void InitRegPressure(MachineBasicBlock *BB);
 256
 257     /// UpdateRegPressure - Update estimate of register pressure after the
 258     /// specified instruction.
 259     void UpdateRegPressure(const MachineInstr *MI);
 260
 261     /// ExtractHoistableLoad - Unfold a load from the given machineinstr if
 262     /// the load itself could be hoisted. Return the unfolded and hoistable
 263     /// load, or null if the load couldn't be unfolded or if it wouldn't
 264     /// be hoistable.
 265     MachineInstr *ExtractHoistableLoad(MachineInstr *MI);
 266
 267     /// LookForDuplicate - Find an instruction amount PrevMIs that is a
 268     /// duplicate of MI. Return this instruction if it's found.
 269     const MachineInstr *LookForDuplicate(const MachineInstr *MI,
 270                                      std::vector<const MachineInstr*> &PrevMIs);
 271
 272     /// EliminateCSE - Given a LICM'ed instruction, look for an instruction on
 273     /// the preheader that compute the same value. If it's found, do a RAU on
 274     /// with the definition of the existing instruction rather than hoisting
 275     /// the instruction to the preheader.
 276     bool EliminateCSE(MachineInstr *MI,
 277            DenseMap<unsigned, std::vector<const MachineInstr*> >::iterator &CI);
 278
 279     /// MayCSE - Return true if the given instruction will be CSE'd if it's
 280     /// hoisted out of the loop.
 281     bool MayCSE(MachineInstr *MI);
 282
 283     /// Hoist - When an instruction is found to only use loop invariant operands
 284     /// that is safe to hoist, this instruction is called to do the dirty work.
 285     /// It returns true if the instruction is hoisted.
 286     bool Hoist(MachineInstr *MI, MachineBasicBlock *Preheader);
 287
 288     /// InitCSEMap - Initialize the CSE map with instructions that are in the
 289     /// current loop preheader that may become duplicates of instructions that
 290     /// are hoisted out of the loop.
 291     void InitCSEMap(MachineBasicBlock *BB);
 292
 293     /// getCurPreheader - Get the preheader for the current loop, splitting
 294     /// a critical edge if needed.
 295     MachineBasicBlock *getCurPreheader();
 296   };
 297 } // end anonymous namespace
 298
 299 char MachineLICM::ID = 0;
 300 char &llvm::MachineLICMID = MachineLICM::ID;
 301 INITIALIZE_PASS_BEGIN(MachineLICM, "machinelicm",
 302                 "Machine Loop Invariant Code Motion", false, false)
 303 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
 304 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
 305 INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
 306 INITIALIZE_PASS_END(MachineLICM, "machinelicm",
 307                 "Machine Loop Invariant Code Motion", false, false)
 308
 309 /// LoopIsOuterMostWithPredecessor - Test if the given loop is the outer-most
 310 /// loop that has a unique predecessor.
 311 static bool LoopIsOuterMostWithPredecessor(MachineLoop *CurLoop) {
 312   // Check whether this loop even has a unique predecessor.
 313   if (!CurLoop->getLoopPredecessor())
 314     return false;
 315   // Ok, now check to see if any of its outer loops do.
 316   for (MachineLoop *L = CurLoop->getParentLoop(); L; L = L->getParentLoop())
 317     if (L->getLoopPredecessor())
 318       return false;
 319   // None of them did, so this is the outermost with a unique predecessor.
 320   return true;
 321 }
 322
 323 bool MachineLICM::runOnMachineFunction(MachineFunction &MF) {
 324   if (skipOptnoneFunction(*MF.getFunction()))
 325     return false;
 326
 327   Changed = FirstInLoop = false;
 328   TM = &MF.getTarget();
 329   TII = TM->getSubtargetImpl()->getInstrInfo();
 330   TLI = TM->getSubtargetImpl()->getTargetLowering();
 331   TRI = TM->getSubtargetImpl()->getRegisterInfo();
 332   MFI = MF.getFrameInfo();
 333   MRI = &MF.getRegInfo();
 334   InstrItins = TM->getSubtargetImpl()->getInstrItineraryData();
 335
 336   PreRegAlloc = MRI->isSSA();
 337
 338   if (PreRegAlloc)
 339     DEBUG(dbgs() << "******** Pre-regalloc Machine LICM: ");
 340   else
 341     DEBUG(dbgs() << "******** Post-regalloc Machine LICM: ");
 342   DEBUG(dbgs() << MF.getName() << " ********\n");
 343
 344   if (PreRegAlloc) {
 345     // Estimate register pressure during pre-regalloc pass.
 346     unsigned NumRC = TRI->getNumRegClasses();
 347     RegPressure.resize(NumRC);
 348     std::fill(RegPressure.begin(), RegPressure.end(), 0);
 349     RegLimit.resize(NumRC);
 350     for (TargetRegisterInfo::regclass_iterator I = TRI->regclass_begin(),
 351            E = TRI->regclass_end(); I != E; ++I)
 352       RegLimit[(*I)->getID()] = TRI->getRegPressureLimit(*I, MF);
 353   }
 354
 355   // Get our Loop information...
 356   MLI = &getAnalysis<MachineLoopInfo>();
 357   DT  = &getAnalysis<MachineDominatorTree>();
 358   AA  = &getAnalysis<AliasAnalysis>();
 359
 360   SmallVector<MachineLoop *, 8> Worklist(MLI->begin(), MLI->end());
 361   while (!Worklist.empty()) {
 362     CurLoop = Worklist.pop_back_val();
 363     CurPreheader = nullptr;
 364     ExitBlocks.clear();
 365
 366     // If this is done before regalloc, only visit outer-most preheader-sporting
 367     // loops.
 368     if (PreRegAlloc && !LoopIsOuterMostWithPredecessor(CurLoop)) {
 369       Worklist.append(CurLoop->begin(), CurLoop->end());
 370       continue;
 371     }
 372
 373     CurLoop->getExitBlocks(ExitBlocks);
 374
 375     if (!PreRegAlloc)
 376       HoistRegionPostRA();
 377     else {
 378       // CSEMap is initialized for loop header when the first instruction is
 379       // being hoisted.
 380       MachineDomTreeNode *N = DT->getNode(CurLoop->getHeader());
 381       FirstInLoop = true;
 382       HoistOutOfLoop(N);
 383       CSEMap.clear();
 384     }
 385   }
 386
 387   return Changed;
 388 }
 389
 390 /// InstructionStoresToFI - Return true if instruction stores to the
 391 /// specified frame.
 392 static bool InstructionStoresToFI(const MachineInstr *MI, int FI) {
 393   for (MachineInstr::mmo_iterator o = MI->memoperands_begin(),
 394          oe = MI->memoperands_end(); o != oe; ++o) {
 395     if (!(*o)->isStore() || !(*o)->getPseudoValue())
 396       continue;
 397     if (const FixedStackPseudoSourceValue *Value =
 398         dyn_cast<FixedStackPseudoSourceValue>((*o)->getPseudoValue())) {
 399       if (Value->getFrameIndex() == FI)
 400         return true;
 401     }
 402   }
 403   return false;
 404 }
 405
 406 /// ProcessMI - Examine the instruction for potentai LICM candidate. Also
 407 /// gather register def and frame object update information.
 408 void MachineLICM::ProcessMI(MachineInstr *MI,
 409                             BitVector &PhysRegDefs,
 410                             BitVector &PhysRegClobbers,
 411                             SmallSet<int, 32> &StoredFIs,
 412                             SmallVectorImpl<CandidateInfo> &Candidates) {
 413   bool RuledOut = false;
 414   bool HasNonInvariantUse = false;
 415   unsigned Def = 0;
 416   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 417     const MachineOperand &MO = MI->getOperand(i);
 418     if (MO.isFI()) {
 419       // Remember if the instruction stores to the frame index.
 420       int FI = MO.getIndex();
 421       if (!StoredFIs.count(FI) &&
 422           MFI->isSpillSlotObjectIndex(FI) &&
 423           InstructionStoresToFI(MI, FI))
 424         StoredFIs.insert(FI);
 425       HasNonInvariantUse = true;
 426       continue;
 427     }
 428
 429     // We can't hoist an instruction defining a physreg that is clobbered in
 430     // the loop.
 431     if (MO.isRegMask()) {
 432       PhysRegClobbers.setBitsNotInMask(MO.getRegMask());
 433       continue;
 434     }
 435
 436     if (!MO.isReg())
 437       continue;
 438     unsigned Reg = MO.getReg();
 439     if (!Reg)
 440       continue;
 441     assert(TargetRegisterInfo::isPhysicalRegister(Reg) &&
 442            "Not expecting virtual register!");
 443
 444     if (!MO.isDef()) {
 445       if (Reg && (PhysRegDefs.test(Reg) || PhysRegClobbers.test(Reg)))
 446         // If it's using a non-loop-invariant register, then it's obviously not
 447         // safe to hoist.
 448         HasNonInvariantUse = true;
 449       continue;
 450     }
 451
 452     if (MO.isImplicit()) {
 453       for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI)
 454         PhysRegClobbers.set(*AI);
 455       if (!MO.isDead())
 456         // Non-dead implicit def? This cannot be hoisted.
 457         RuledOut = true;
 458       // No need to check if a dead implicit def is also defined by
 459       // another instruction.
 460       continue;
 461     }
 462
 463     // FIXME: For now, avoid instructions with multiple defs, unless
 464     // it's a dead implicit def.
 465     if (Def)
 466       RuledOut = true;
 467     else
 468       Def = Reg;
 469
 470     // If we have already seen another instruction that defines the same
 471     // register, then this is not safe.  Two defs is indicated by setting a
 472     // PhysRegClobbers bit.
 473     for (MCRegAliasIterator AS(Reg, TRI, true); AS.isValid(); ++AS) {
 474       if (PhysRegDefs.test(*AS))
 475         PhysRegClobbers.set(*AS);
 476       PhysRegDefs.set(*AS);
 477     }
 478     if (PhysRegClobbers.test(Reg))
 479       // MI defined register is seen defined by another instruction in
 480       // the loop, it cannot be a LICM candidate.
 481       RuledOut = true;
 482   }
 483
 484   // Only consider reloads for now and remats which do not have register
 485   // operands. FIXME: Consider unfold load folding instructions.
 486   if (Def && !RuledOut) {
 487     int FI = INT_MIN;
 488     if ((!HasNonInvariantUse && IsLICMCandidate(*MI)) ||
 489         (TII->isLoadFromStackSlot(MI, FI) && MFI->isSpillSlotObjectIndex(FI)))
 490       Candidates.push_back(CandidateInfo(MI, Def, FI));
 491   }
 492 }
 493
 494 /// HoistRegionPostRA - Walk the specified region of the CFG and hoist loop
 495 /// invariants out to the preheader.
 496 void MachineLICM::HoistRegionPostRA() {
 497   MachineBasicBlock *Preheader = getCurPreheader();
 498   if (!Preheader)
 499     return;
 500
 501   unsigned NumRegs = TRI->getNumRegs();
 502   BitVector PhysRegDefs(NumRegs); // Regs defined once in the loop.
 503   BitVector PhysRegClobbers(NumRegs); // Regs defined more than once.
 504
 505   SmallVector<CandidateInfo, 32> Candidates;
 506   SmallSet<int, 32> StoredFIs;
 507
 508   // Walk the entire region, count number of defs for each register, and
 509   // collect potential LICM candidates.
 510   const std::vector<MachineBasicBlock *> &Blocks = CurLoop->getBlocks();
 511   for (unsigned i = 0, e = Blocks.size(); i != e; ++i) {
 512     MachineBasicBlock *BB = Blocks[i];
 513
 514     // If the header of the loop containing this basic block is a landing pad,
 515     // then don't try to hoist instructions out of this loop.
 516     const MachineLoop *ML = MLI->getLoopFor(BB);
 517     if (ML && ML->getHeader()->isLandingPad()) continue;
 518
 519     // Conservatively treat live-in's as an external def.
 520     // FIXME: That means a reload that're reused in successor block(s) will not
 521     // be LICM'ed.
 522     for (MachineBasicBlock::livein_iterator I = BB->livein_begin(),
 523            E = BB->livein_end(); I != E; ++I) {
 524       unsigned Reg = *I;
 525       for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI)
 526         PhysRegDefs.set(*AI);
 527     }
 528
 529     SpeculationState = SpeculateUnknown;
 530     for (MachineBasicBlock::iterator
 531            MII = BB->begin(), E = BB->end(); MII != E; ++MII) {
 532       MachineInstr *MI = &*MII;
 533       ProcessMI(MI, PhysRegDefs, PhysRegClobbers, StoredFIs, Candidates);
 534     }
 535   }
 536
 537   // Gather the registers read / clobbered by the terminator.
 538   BitVector TermRegs(NumRegs);
 539   MachineBasicBlock::iterator TI = Preheader->getFirstTerminator();
 540   if (TI != Preheader->end()) {
 541     for (unsigned i = 0, e = TI->getNumOperands(); i != e; ++i) {
 542       const MachineOperand &MO = TI->getOperand(i);
 543       if (!MO.isReg())
 544         continue;
 545       unsigned Reg = MO.getReg();
 546       if (!Reg)
 547         continue;
 548       for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI)
 549         TermRegs.set(*AI);
 550     }
 551   }
 552
 553   // Now evaluate whether the potential candidates qualify.
 554   // 1. Check if the candidate defined register is defined by another
 555   //    instruction in the loop.
 556   // 2. If the candidate is a load from stack slot (always true for now),
 557   //    check if the slot is stored anywhere in the loop.
 558   // 3. Make sure candidate def should not clobber
 559   //    registers read by the terminator. Similarly its def should not be
 560   //    clobbered by the terminator.
 561   for (unsigned i = 0, e = Candidates.size(); i != e; ++i) {
 562     if (Candidates[i].FI != INT_MIN &&
 563         StoredFIs.count(Candidates[i].FI))
 564       continue;
 565
 566     unsigned Def = Candidates[i].Def;
 567     if (!PhysRegClobbers.test(Def) && !TermRegs.test(Def)) {
 568       bool Safe = true;
 569       MachineInstr *MI = Candidates[i].MI;
 570       for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) {
 571         const MachineOperand &MO = MI->getOperand(j);
 572         if (!MO.isReg() || MO.isDef() || !MO.getReg())
 573           continue;
 574         unsigned Reg = MO.getReg();
 575         if (PhysRegDefs.test(Reg) ||
 576             PhysRegClobbers.test(Reg)) {
 577           // If it's using a non-loop-invariant register, then it's obviously
 578           // not safe to hoist.
 579           Safe = false;
 580           break;
 581         }
 582       }
 583       if (Safe)
 584         HoistPostRA(MI, Candidates[i].Def);
 585     }
 586   }
 587 }
 588
 589 /// AddToLiveIns - Add register 'Reg' to the livein sets of BBs in the current
 590 /// loop, and make sure it is not killed by any instructions in the loop.
 591 void MachineLICM::AddToLiveIns(unsigned Reg) {
 592   const std::vector<MachineBasicBlock *> &Blocks = CurLoop->getBlocks();
 593   for (unsigned i = 0, e = Blocks.size(); i != e; ++i) {
 594     MachineBasicBlock *BB = Blocks[i];
 595     if (!BB->isLiveIn(Reg))
 596       BB->addLiveIn(Reg);
 597     for (MachineBasicBlock::iterator
 598            MII = BB->begin(), E = BB->end(); MII != E; ++MII) {
 599       MachineInstr *MI = &*MII;
 600       for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 601         MachineOperand &MO = MI->getOperand(i);
 602         if (!MO.isReg() || !MO.getReg() || MO.isDef()) continue;
 603         if (MO.getReg() == Reg || TRI->isSuperRegister(Reg, MO.getReg()))
 604           MO.setIsKill(false);
 605       }
 606     }
 607   }
 608 }
 609
 610 /// HoistPostRA - When an instruction is found to only use loop invariant
 611 /// operands that is safe to hoist, this instruction is called to do the
 612 /// dirty work.
 613 void MachineLICM::HoistPostRA(MachineInstr *MI, unsigned Def) {
 614   MachineBasicBlock *Preheader = getCurPreheader();
 615
 616   // Now move the instructions to the predecessor, inserting it before any
 617   // terminator instructions.
 618   DEBUG(dbgs() << "Hoisting to BB#" << Preheader->getNumber() << " from BB#"
 619                << MI->getParent()->getNumber() << ": " << *MI);
 620
 621   // Splice the instruction to the preheader.
 622   MachineBasicBlock *MBB = MI->getParent();
 623   Preheader->splice(Preheader->getFirstTerminator(), MBB, MI);
 624
 625   // Add register to livein list to all the BBs in the current loop since a
 626   // loop invariant must be kept live throughout the whole loop. This is
 627   // important to ensure later passes do not scavenge the def register.
 628   AddToLiveIns(Def);
 629
 630   ++NumPostRAHoisted;
 631   Changed = true;
 632 }
 633
 634 // IsGuaranteedToExecute - Check if this mbb is guaranteed to execute.
 635 // If not then a load from this mbb may not be safe to hoist.
 636 bool MachineLICM::IsGuaranteedToExecute(MachineBasicBlock *BB) {
 637   if (SpeculationState != SpeculateUnknown)
 638     return SpeculationState == SpeculateFalse;
 639
 640   if (BB != CurLoop->getHeader()) {
 641     // Check loop exiting blocks.
 642     SmallVector<MachineBasicBlock*, 8> CurrentLoopExitingBlocks;
 643     CurLoop->getExitingBlocks(CurrentLoopExitingBlocks);
 644     for (unsigned i = 0, e = CurrentLoopExitingBlocks.size(); i != e; ++i)
 645       if (!DT->dominates(BB, CurrentLoopExitingBlocks[i])) {
 646         SpeculationState = SpeculateTrue;
 647         return false;
 648       }
 649   }
 650
 651   SpeculationState = SpeculateFalse;
 652   return true;
 653 }
 654
 655 void MachineLICM::EnterScope(MachineBasicBlock *MBB) {
 656   DEBUG(dbgs() << "Entering: " << MBB->getName() << '\n');
 657
 658   // Remember livein register pressure.
 659   BackTrace.push_back(RegPressure);
 660 }
 661
 662 void MachineLICM::ExitScope(MachineBasicBlock *MBB) {
 663   DEBUG(dbgs() << "Exiting: " << MBB->getName() << '\n');
 664   BackTrace.pop_back();
 665 }
 666
 667 /// ExitScopeIfDone - Destroy scope for the MBB that corresponds to the given
 668 /// dominator tree node if its a leaf or all of its children are done. Walk
 669 /// up the dominator tree to destroy ancestors which are now done.
 670 void MachineLICM::ExitScopeIfDone(MachineDomTreeNode *Node,
 671                 DenseMap<MachineDomTreeNode*, unsigned> &OpenChildren,
 672                 DenseMap<MachineDomTreeNode*, MachineDomTreeNode*> &ParentMap) {
 673   if (OpenChildren[Node])
 674     return;
 675
 676   // Pop scope.
 677   ExitScope(Node->getBlock());
 678
 679   // Now traverse upwards to pop ancestors whose offsprings are all done.
 680   while (MachineDomTreeNode *Parent = ParentMap[Node]) {
 681     unsigned Left = --OpenChildren[Parent];
 682     if (Left != 0)
 683       break;
 684     ExitScope(Parent->getBlock());
 685     Node = Parent;
 686   }
 687 }
 688
 689 /// HoistOutOfLoop - Walk the specified loop in the CFG (defined by all
 690 /// blocks dominated by the specified header block, and that are in the
 691 /// current loop) in depth first order w.r.t the DominatorTree. This allows
 692 /// us to visit definitions before uses, allowing us to hoist a loop body in
 693 /// one pass without iteration.
 694 ///
 695 void MachineLICM::HoistOutOfLoop(MachineDomTreeNode *HeaderN) {
 696   SmallVector<MachineDomTreeNode*, 32> Scopes;
 697   SmallVector<MachineDomTreeNode*, 8> WorkList;
 698   DenseMap<MachineDomTreeNode*, MachineDomTreeNode*> ParentMap;
 699   DenseMap<MachineDomTreeNode*, unsigned> OpenChildren;
 700
 701   // Perform a DFS walk to determine the order of visit.
 702   WorkList.push_back(HeaderN);
 703   do {
 704     MachineDomTreeNode *Node = WorkList.pop_back_val();
 705     assert(Node && "Null dominator tree node?");
 706     MachineBasicBlock *BB = Node->getBlock();
 707
 708     // If the header of the loop containing this basic block is a landing pad,
 709     // then don't try to hoist instructions out of this loop.
 710     const MachineLoop *ML = MLI->getLoopFor(BB);
 711     if (ML && ML->getHeader()->isLandingPad())
 712       continue;
 713
 714     // If this subregion is not in the top level loop at all, exit.
 715     if (!CurLoop->contains(BB))
 716       continue;
 717
 718     Scopes.push_back(Node);
 719     const std::vector<MachineDomTreeNode*> &Children = Node->getChildren();
 720     unsigned NumChildren = Children.size();
 721
 722     // Don't hoist things out of a large switch statement.  This often causes
 723     // code to be hoisted that wasn't going to be executed, and increases
 724     // register pressure in a situation where it's likely to matter.
 725     if (BB->succ_size() >= 25)
 726       NumChildren = 0;
 727
 728     OpenChildren[Node] = NumChildren;
 729     // Add children in reverse order as then the next popped worklist node is
 730     // the first child of this node.  This means we ultimately traverse the
 731     // DOM tree in exactly the same order as if we'd recursed.
 732     for (int i = (int)NumChildren-1; i >= 0; --i) {
 733       MachineDomTreeNode *Child = Children[i];
 734       ParentMap[Child] = Node;
 735       WorkList.push_back(Child);
 736     }
 737   } while (!WorkList.empty());
 738
 739   if (Scopes.size() != 0) {
 740     MachineBasicBlock *Preheader = getCurPreheader();
 741     if (!Preheader)
 742       return;
 743
 744     // Compute registers which are livein into the loop headers.
 745     RegSeen.clear();
 746     BackTrace.clear();
 747     InitRegPressure(Preheader);
 748   }
 749
 750   // Now perform LICM.
 751   for (unsigned i = 0, e = Scopes.size(); i != e; ++i) {
 752     MachineDomTreeNode *Node = Scopes[i];
 753     MachineBasicBlock *MBB = Node->getBlock();
 754
 755     MachineBasicBlock *Preheader = getCurPreheader();
 756     if (!Preheader)
 757       continue;
 758
 759     EnterScope(MBB);
 760
 761     // Process the block
 762     SpeculationState = SpeculateUnknown;
 763     for (MachineBasicBlock::iterator
 764          MII = MBB->begin(), E = MBB->end(); MII != E; ) {
 765       MachineBasicBlock::iterator NextMII = MII; ++NextMII;
 766       MachineInstr *MI = &*MII;
 767       if (!Hoist(MI, Preheader))
 768         UpdateRegPressure(MI);
 769       MII = NextMII;
 770     }
 771
 772     // If it's a leaf node, it's done. Traverse upwards to pop ancestors.
 773     ExitScopeIfDone(Node, OpenChildren, ParentMap);
 774   }
 775 }
 776
 777 static bool isOperandKill(const MachineOperand &MO, MachineRegisterInfo *MRI) {
 778   return MO.isKill() || MRI->hasOneNonDBGUse(MO.getReg());
 779 }
 780
 781 /// getRegisterClassIDAndCost - For a given MI, register, and the operand
 782 /// index, return the ID and cost of its representative register class.
 783 void
 784 MachineLICM::getRegisterClassIDAndCost(const MachineInstr *MI,
 785                                        unsigned Reg, unsigned OpIdx,
 786                                        unsigned &RCId, unsigned &RCCost) const {
 787   const TargetRegisterClass *RC = MRI->getRegClass(Reg);
 788   MVT VT = *RC->vt_begin();
 789   if (VT == MVT::Untyped) {
 790     RCId = RC->getID();
 791     RCCost = 1;
 792   } else {
 793     RCId = TLI->getRepRegClassFor(VT)->getID();
 794     RCCost = TLI->getRepRegClassCostFor(VT);
 795   }
 796 }
 797
 798 /// InitRegPressure - Find all virtual register references that are liveout of
 799 /// the preheader to initialize the starting "register pressure". Note this
 800 /// does not count live through (livein but not used) registers.
 801 void MachineLICM::InitRegPressure(MachineBasicBlock *BB) {
 802   std::fill(RegPressure.begin(), RegPressure.end(), 0);
 803
 804   // If the preheader has only a single predecessor and it ends with a
 805   // fallthrough or an unconditional branch, then scan its predecessor for live
 806   // defs as well. This happens whenever the preheader is created by splitting
 807   // the critical edge from the loop predecessor to the loop header.
 808   if (BB->pred_size() == 1) {
 809     MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
 810     SmallVector<MachineOperand, 4> Cond;
 811     if (!TII->AnalyzeBranch(*BB, TBB, FBB, Cond, false) && Cond.empty())
 812       InitRegPressure(*BB->pred_begin());
 813   }
 814
 815   for (MachineBasicBlock::iterator MII = BB->begin(), E = BB->end();
 816        MII != E; ++MII) {
 817     MachineInstr *MI = &*MII;
 818     for (unsigned i = 0, e = MI->getDesc().getNumOperands(); i != e; ++i) {
 819       const MachineOperand &MO = MI->getOperand(i);
 820       if (!MO.isReg() || MO.isImplicit())
 821         continue;
 822       unsigned Reg = MO.getReg();
 823       if (!TargetRegisterInfo::isVirtualRegister(Reg))
 824         continue;
 825
 826       bool isNew = RegSeen.insert(Reg);
 827       unsigned RCId, RCCost;
 828       getRegisterClassIDAndCost(MI, Reg, i, RCId, RCCost);
 829       if (MO.isDef())
 830         RegPressure[RCId] += RCCost;
 831       else {
 832         bool isKill = isOperandKill(MO, MRI);
 833         if (isNew && !isKill)
 834           // Haven't seen this, it must be a livein.
 835           RegPressure[RCId] += RCCost;
 836         else if (!isNew && isKill)
 837           RegPressure[RCId] -= RCCost;
 838       }
 839     }
 840   }
 841 }
 842
 843 /// UpdateRegPressure - Update estimate of register pressure after the
 844 /// specified instruction.
 845 void MachineLICM::UpdateRegPressure(const MachineInstr *MI) {
 846   if (MI->isImplicitDef())
 847     return;
 848
 849   SmallVector<unsigned, 4> Defs;
 850   for (unsigned i = 0, e = MI->getDesc().getNumOperands(); i != e; ++i) {
 851     const MachineOperand &MO = MI->getOperand(i);
 852     if (!MO.isReg() || MO.isImplicit())
 853       continue;
 854     unsigned Reg = MO.getReg();
 855     if (!TargetRegisterInfo::isVirtualRegister(Reg))
 856       continue;
 857
 858     bool isNew = RegSeen.insert(Reg);
 859     if (MO.isDef())
 860       Defs.push_back(Reg);
 861     else if (!isNew && isOperandKill(MO, MRI)) {
 862       unsigned RCId, RCCost;
 863       getRegisterClassIDAndCost(MI, Reg, i, RCId, RCCost);
 864       if (RCCost > RegPressure[RCId])
 865         RegPressure[RCId] = 0;
 866       else
 867         RegPressure[RCId] -= RCCost;
 868     }
 869   }
 870
 871   unsigned Idx = 0;
 872   while (!Defs.empty()) {
 873     unsigned Reg = Defs.pop_back_val();
 874     unsigned RCId, RCCost;
 875     getRegisterClassIDAndCost(MI, Reg, Idx, RCId, RCCost);
 876     RegPressure[RCId] += RCCost;
 877     ++Idx;
 878   }
 879 }
 880
 881 /// isLoadFromGOTOrConstantPool - Return true if this machine instruction
 882 /// loads from global offset table or constant pool.
 883 static bool isLoadFromGOTOrConstantPool(MachineInstr &MI) {
 884   assert (MI.mayLoad() && "Expected MI that loads!");
 885   for (MachineInstr::mmo_iterator I = MI.memoperands_begin(),
 886          E = MI.memoperands_end(); I != E; ++I) {
 887     if (const PseudoSourceValue *PSV = (*I)->getPseudoValue()) {
 888       if (PSV == PSV->getGOT() || PSV == PSV->getConstantPool())
 889         return true;
 890     }
 891   }
 892   return false;
 893 }
 894
 895 /// IsLICMCandidate - Returns true if the instruction may be a suitable
 896 /// candidate for LICM. e.g. If the instruction is a call, then it's obviously
 897 /// not safe to hoist it.
 898 bool MachineLICM::IsLICMCandidate(MachineInstr &I) {
 899   // Check if it's safe to move the instruction.
 900   bool DontMoveAcrossStore = true;
 901   if (!I.isSafeToMove(TII, AA, DontMoveAcrossStore))
 902     return false;
 903
 904   // If it is load then check if it is guaranteed to execute by making sure that
 905   // it dominates all exiting blocks. If it doesn't, then there is a path out of
 906   // the loop which does not execute this load, so we can't hoist it. Loads
 907   // from constant memory are not safe to speculate all the time, for example
 908   // indexed load from a jump table.
 909   // Stores and side effects are already checked by isSafeToMove.
 910   if (I.mayLoad() && !isLoadFromGOTOrConstantPool(I) &&
 911       !IsGuaranteedToExecute(I.getParent()))
 912     return false;
 913
 914   return true;
 915 }
 916
 917 /// IsLoopInvariantInst - Returns true if the instruction is loop
 918 /// invariant. I.e., all virtual register operands are defined outside of the
 919 /// loop, physical registers aren't accessed explicitly, and there are no side
 920 /// effects that aren't captured by the operands or other flags.
 921 ///
 922 bool MachineLICM::IsLoopInvariantInst(MachineInstr &I) {
 923   if (!IsLICMCandidate(I))
 924     return false;
 925
 926   // The instruction is loop invariant if all of its operands are.
 927   for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) {
 928     const MachineOperand &MO = I.getOperand(i);
 929
 930     if (!MO.isReg())
 931       continue;
 932
 933     unsigned Reg = MO.getReg();
 934     if (Reg == 0) continue;
 935
 936     // Don't hoist an instruction that uses or defines a physical register.
 937     if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
 938       if (MO.isUse()) {
 939         // If the physreg has no defs anywhere, it's just an ambient register
 940         // and we can freely move its uses. Alternatively, if it's allocatable,
 941         // it could get allocated to something with a def during allocation.
 942         if (!MRI->isConstantPhysReg(Reg, *I.getParent()->getParent()))
 943           return false;
 944         // Otherwise it's safe to move.
 945         continue;
 946       } else if (!MO.isDead()) {
 947         // A def that isn't dead. We can't move it.
 948         return false;
 949       } else if (CurLoop->getHeader()->isLiveIn(Reg)) {
 950         // If the reg is live into the loop, we can't hoist an instruction
 951         // which would clobber it.
 952         return false;
 953       }
 954     }
 955
 956     if (!MO.isUse())
 957       continue;
 958
 959     assert(MRI->getVRegDef(Reg) &&
 960            "Machine instr not mapped for this vreg?!");
 961
 962     // If the loop contains the definition of an operand, then the instruction
 963     // isn't loop invariant.
 964     if (CurLoop->contains(MRI->getVRegDef(Reg)))
 965       return false;
 966   }
 967
 968   // If we got this far, the instruction is loop invariant!
 969   return true;
 970 }
 971
 972
 973 /// HasLoopPHIUse - Return true if the specified instruction is used by a
 974 /// phi node and hoisting it could cause a copy to be inserted.
 975 bool MachineLICM::HasLoopPHIUse(const MachineInstr *MI) const {
 976   SmallVector<const MachineInstr*, 8> Work(1, MI);
 977   do {
 978     MI = Work.pop_back_val();
 979     for (ConstMIOperands MO(MI); MO.isValid(); ++MO) {
 980       if (!MO->isReg() || !MO->isDef())
 981         continue;
 982       unsigned Reg = MO->getReg();
 983       if (!TargetRegisterInfo::isVirtualRegister(Reg))
 984         continue;
 985       for (MachineInstr &UseMI : MRI->use_instructions(Reg)) {
 986         // A PHI may cause a copy to be inserted.
 987         if (UseMI.isPHI()) {
 988           // A PHI inside the loop causes a copy because the live range of Reg is
 989           // extended across the PHI.
 990           if (CurLoop->contains(&UseMI))
 991             return true;
 992           // A PHI in an exit block can cause a copy to be inserted if the PHI
 993           // has multiple predecessors in the loop with different values.
 994           // For now, approximate by rejecting all exit blocks.
 995           if (isExitBlock(UseMI.getParent()))
 996             return true;
 997           continue;
 998         }
 999         // Look past copies as well.
1000         if (UseMI.isCopy() && CurLoop->contains(&UseMI))
1001           Work.push_back(&UseMI);
1002       }
1003     }
1004   } while (!Work.empty());
1005   return false;
1006 }
1007
1008 /// HasHighOperandLatency - Compute operand latency between a def of 'Reg'
1009 /// and an use in the current loop, return true if the target considered
1010 /// it 'high'.
1011 bool MachineLICM::HasHighOperandLatency(MachineInstr &MI,
1012                                         unsigned DefIdx, unsigned Reg) const {
1013   if (!InstrItins || InstrItins->isEmpty() || MRI->use_nodbg_empty(Reg))
1014     return false;
1015
1016   for (MachineInstr &UseMI : MRI->use_nodbg_instructions(Reg)) {
1017     if (UseMI.isCopyLike())
1018       continue;
1019     if (!CurLoop->contains(UseMI.getParent()))
1020       continue;
1021     for (unsigned i = 0, e = UseMI.getNumOperands(); i != e; ++i) {
1022       const MachineOperand &MO = UseMI.getOperand(i);
1023       if (!MO.isReg() || !MO.isUse())
1024         continue;
1025       unsigned MOReg = MO.getReg();
1026       if (MOReg != Reg)
1027         continue;
1028
1029       if (TII->hasHighOperandLatency(InstrItins, MRI, &MI, DefIdx, &UseMI, i))
1030         return true;
1031     }
1032
1033     // Only look at the first in loop use.
1034     break;
1035   }
1036
1037   return false;
1038 }
1039
1040 /// IsCheapInstruction - Return true if the instruction is marked "cheap" or
1041 /// the operand latency between its def and a use is one or less.
1042 bool MachineLICM::IsCheapInstruction(MachineInstr &MI) const {
1043   if (TII->isAsCheapAsAMove(&MI) || MI.isCopyLike())
1044     return true;
1045   if (!InstrItins || InstrItins->isEmpty())
1046     return false;
1047
1048   bool isCheap = false;
1049   unsigned NumDefs = MI.getDesc().getNumDefs();
1050   for (unsigned i = 0, e = MI.getNumOperands(); NumDefs && i != e; ++i) {
1051     MachineOperand &DefMO = MI.getOperand(i);
1052     if (!DefMO.isReg() || !DefMO.isDef())
1053       continue;
1054     --NumDefs;
1055     unsigned Reg = DefMO.getReg();
1056     if (TargetRegisterInfo::isPhysicalRegister(Reg))
1057       continue;
1058
1059     if (!TII->hasLowDefLatency(InstrItins, &MI, i))
1060       return false;
1061     isCheap = true;
1062   }
1063
1064   return isCheap;
1065 }
1066
1067 /// CanCauseHighRegPressure - Visit BBs from header to current BB, check
1068 /// if hoisting an instruction of the given cost matrix can cause high
1069 /// register pressure.
1070 bool MachineLICM::CanCauseHighRegPressure(DenseMap<unsigned, int> &Cost,
1071                                           bool CheapInstr) {
1072   for (DenseMap<unsigned, int>::iterator CI = Cost.begin(), CE = Cost.end();
1073        CI != CE; ++CI) {
1074     if (CI->second <= 0)
1075       continue;
1076
1077     unsigned RCId = CI->first;
1078     unsigned Limit = RegLimit[RCId];
1079     int Cost = CI->second;
1080
1081     // Don't hoist cheap instructions if they would increase register pressure,
1082     // even if we're under the limit.
1083     if (CheapInstr)
1084       return true;
1085
1086     for (unsigned i = BackTrace.size(); i != 0; --i) {
1087       SmallVectorImpl<unsigned> &RP = BackTrace[i-1];
1088       if (RP[RCId] + Cost >= Limit)
1089         return true;
1090     }
1091   }
1092
1093   return false;
1094 }
1095
1096 /// UpdateBackTraceRegPressure - Traverse the back trace from header to the
1097 /// current block and update their register pressures to reflect the effect
1098 /// of hoisting MI from the current block to the preheader.
1099 void MachineLICM::UpdateBackTraceRegPressure(const MachineInstr *MI) {
1100   if (MI->isImplicitDef())
1101     return;
1102
1103   // First compute the 'cost' of the instruction, i.e. its contribution
1104   // to register pressure.
1105   DenseMap<unsigned, int> Cost;
1106   for (unsigned i = 0, e = MI->getDesc().getNumOperands(); i != e; ++i) {
1107     const MachineOperand &MO = MI->getOperand(i);
1108     if (!MO.isReg() || MO.isImplicit())
1109       continue;
1110     unsigned Reg = MO.getReg();
1111     if (!TargetRegisterInfo::isVirtualRegister(Reg))
1112       continue;
1113
1114     unsigned RCId, RCCost;
1115     getRegisterClassIDAndCost(MI, Reg, i, RCId, RCCost);
1116     if (MO.isDef()) {
1117       DenseMap<unsigned, int>::iterator CI = Cost.find(RCId);
1118       if (CI != Cost.end())
1119         CI->second += RCCost;
1120       else
1121         Cost.insert(std::make_pair(RCId, RCCost));
1122     } else if (isOperandKill(MO, MRI)) {
1123       DenseMap<unsigned, int>::iterator CI = Cost.find(RCId);
1124       if (CI != Cost.end())
1125         CI->second -= RCCost;
1126       else
1127         Cost.insert(std::make_pair(RCId, -RCCost));
1128     }
1129   }
1130
1131   // Update register pressure of blocks from loop header to current block.
1132   for (unsigned i = 0, e = BackTrace.size(); i != e; ++i) {
1133     SmallVectorImpl<unsigned> &RP = BackTrace[i];
1134     for (DenseMap<unsigned, int>::iterator CI = Cost.begin(), CE = Cost.end();
1135          CI != CE; ++CI) {
1136       unsigned RCId = CI->first;
1137       RP[RCId] += CI->second;
1138     }
1139   }
1140 }
1141
1142 /// IsProfitableToHoist - Return true if it is potentially profitable to hoist
1143 /// the given loop invariant.
1144 bool MachineLICM::IsProfitableToHoist(MachineInstr &MI) {
1145   if (MI.isImplicitDef())
1146     return true;
1147
1148   // Besides removing computation from the loop, hoisting an instruction has
1149   // these effects:
1150   //
1151   // - The value defined by the instruction becomes live across the entire
1152   //   loop. This increases register pressure in the loop.
1153   //
1154   // - If the value is used by a PHI in the loop, a copy will be required for
1155   //   lowering the PHI after extending the live range.
1156   //
1157   // - When hoisting the last use of a value in the loop, that value no longer
1158   //   needs to be live in the loop. This lowers register pressure in the loop.
1159
1160   bool CheapInstr = IsCheapInstruction(MI);
1161   bool CreatesCopy = HasLoopPHIUse(&MI);
1162
1163   // Don't hoist a cheap instruction if it would create a copy in the loop.
1164   if (CheapInstr && CreatesCopy) {
1165     DEBUG(dbgs() << "Won't hoist cheap instr with loop PHI use: " << MI);
1166     return false;
1167   }
1168
1169   // Rematerializable instructions should always be hoisted since the register
1170   // allocator can just pull them down again when needed.
1171   if (TII->isTriviallyReMaterializable(&MI, AA))
1172     return true;
1173
1174   // Estimate register pressure to determine whether to LICM the instruction.
1175   // In low register pressure situation, we can be more aggressive about
1176   // hoisting. Also, favors hoisting long latency instructions even in
1177   // moderately high pressure situation.
1178   // Cheap instructions will only be hoisted if they don't increase register
1179   // pressure at all.
1180   // FIXME: If there are long latency loop-invariant instructions inside the
1181   // loop at this point, why didn't the optimizer's LICM hoist them?
1182   DenseMap<unsigned, int> Cost;
1183   for (unsigned i = 0, e = MI.getDesc().getNumOperands(); i != e; ++i) {
1184     const MachineOperand &MO = MI.getOperand(i);
1185     if (!MO.isReg() || MO.isImplicit())
1186       continue;
1187     unsigned Reg = MO.getReg();
1188     if (!TargetRegisterInfo::isVirtualRegister(Reg))
1189       continue;
1190
1191     unsigned RCId, RCCost;
1192     getRegisterClassIDAndCost(&MI, Reg, i, RCId, RCCost);
1193     if (MO.isDef()) {
1194       if (HasHighOperandLatency(MI, i, Reg)) {
1195         DEBUG(dbgs() << "Hoist High Latency: " << MI);
1196         ++NumHighLatency;
1197         return true;
1198       }
1199       Cost[RCId] += RCCost;
1200     } else if (isOperandKill(MO, MRI)) {
1201       // Is a virtual register use is a kill, hoisting it out of the loop
1202       // may actually reduce register pressure or be register pressure
1203       // neutral.
1204       Cost[RCId] -= RCCost;
1205     }
1206   }
1207
1208   // Visit BBs from header to current BB, if hoisting this doesn't cause
1209   // high register pressure, then it's safe to proceed.
1210   if (!CanCauseHighRegPressure(Cost, CheapInstr)) {
1211     DEBUG(dbgs() << "Hoist non-reg-pressure: " << MI);
1212     ++NumLowRP;
1213     return true;
1214   }
1215
1216   // Don't risk increasing register pressure if it would create copies.
1217   if (CreatesCopy) {
1218     DEBUG(dbgs() << "Won't hoist instr with loop PHI use: " << MI);
1219     return false;
1220   }
1221
1222   // Do not "speculate" in high register pressure situation. If an
1223   // instruction is not guaranteed to be executed in the loop, it's best to be
1224   // conservative.
1225   if (AvoidSpeculation &&
1226       (!IsGuaranteedToExecute(MI.getParent()) && !MayCSE(&MI))) {
1227     DEBUG(dbgs() << "Won't speculate: " << MI);
1228     return false;
1229   }
1230
1231   // High register pressure situation, only hoist if the instruction is going
1232   // to be remat'ed.
1233   if (!TII->isTriviallyReMaterializable(&MI, AA) &&
1234       !MI.isInvariantLoad(AA)) {
1235     DEBUG(dbgs() << "Can't remat / high reg-pressure: " << MI);
1236     return false;
1237   }
1238
1239   return true;
1240 }
1241
1242 MachineInstr *MachineLICM::ExtractHoistableLoad(MachineInstr *MI) {
1243   // Don't unfold simple loads.
1244   if (MI->canFoldAsLoad())
1245     return nullptr;
1246
1247   // If not, we may be able to unfold a load and hoist that.
1248   // First test whether the instruction is loading from an amenable
1249   // memory location.
1250   if (!MI->isInvariantLoad(AA))
1251     return nullptr;
1252
1253   // Next determine the register class for a temporary register.
1254   unsigned LoadRegIndex;
1255   unsigned NewOpc =
1256     TII->getOpcodeAfterMemoryUnfold(MI->getOpcode(),
1257                                     /*UnfoldLoad=*/true,
1258                                     /*UnfoldStore=*/false,
1259                                     &LoadRegIndex);
1260   if (NewOpc == 0) return nullptr;
1261   const MCInstrDesc &MID = TII->get(NewOpc);
1262   if (MID.getNumDefs() != 1) return nullptr;
1263   MachineFunction &MF = *MI->getParent()->getParent();
1264   const TargetRegisterClass *RC = TII->getRegClass(MID, LoadRegIndex, TRI, MF);
1265   // Ok, we're unfolding. Create a temporary register and do the unfold.
1266   unsigned Reg = MRI->createVirtualRegister(RC);
1267
1268   SmallVector<MachineInstr *, 2> NewMIs;
1269   bool Success =
1270     TII->unfoldMemoryOperand(MF, MI, Reg,
1271                              /*UnfoldLoad=*/true, /*UnfoldStore=*/false,
1272                              NewMIs);
1273   (void)Success;
1274   assert(Success &&
1275          "unfoldMemoryOperand failed when getOpcodeAfterMemoryUnfold "
1276          "succeeded!");
1277   assert(NewMIs.size() == 2 &&
1278          "Unfolded a load into multiple instructions!");
1279   MachineBasicBlock *MBB = MI->getParent();
1280   MachineBasicBlock::iterator Pos = MI;
1281   MBB->insert(Pos, NewMIs[0]);
1282   MBB->insert(Pos, NewMIs[1]);
1283   // If unfolding produced a load that wasn't loop-invariant or profitable to
1284   // hoist, discard the new instructions and bail.
1285   if (!IsLoopInvariantInst(*NewMIs[0]) || !IsProfitableToHoist(*NewMIs[0])) {
1286     NewMIs[0]->eraseFromParent();
1287     NewMIs[1]->eraseFromParent();
1288     return nullptr;
1289   }
1290
1291   // Update register pressure for the unfolded instruction.
1292   UpdateRegPressure(NewMIs[1]);
1293
1294   // Otherwise we successfully unfolded a load that we can hoist.
1295   MI->eraseFromParent();
1296   return NewMIs[0];
1297 }
1298
1299 void MachineLICM::InitCSEMap(MachineBasicBlock *BB) {
1300   for (MachineBasicBlock::iterator I = BB->begin(),E = BB->end(); I != E; ++I) {
1301     const MachineInstr *MI = &*I;
1302     unsigned Opcode = MI->getOpcode();
1303     DenseMap<unsigned, std::vector<const MachineInstr*> >::iterator
1304       CI = CSEMap.find(Opcode);
1305     if (CI != CSEMap.end())
1306       CI->second.push_back(MI);
1307     else {
1308       std::vector<const MachineInstr*> CSEMIs;
1309       CSEMIs.push_back(MI);
1310       CSEMap.insert(std::make_pair(Opcode, CSEMIs));
1311     }
1312   }
1313 }
1314
1315 const MachineInstr*
1316 MachineLICM::LookForDuplicate(const MachineInstr *MI,
1317                               std::vector<const MachineInstr*> &PrevMIs) {
1318   for (unsigned i = 0, e = PrevMIs.size(); i != e; ++i) {
1319     const MachineInstr *PrevMI = PrevMIs[i];
1320     if (TII->produceSameValue(MI, PrevMI, (PreRegAlloc ? MRI : nullptr)))
1321       return PrevMI;
1322   }
1323   return nullptr;
1324 }
1325
1326 bool MachineLICM::EliminateCSE(MachineInstr *MI,
1327           DenseMap<unsigned, std::vector<const MachineInstr*> >::iterator &CI) {
1328   // Do not CSE implicit_def so ProcessImplicitDefs can properly propagate
1329   // the undef property onto uses.
1330   if (CI == CSEMap.end() || MI->isImplicitDef())
1331     return false;
1332
1333   if (const MachineInstr *Dup = LookForDuplicate(MI, CI->second)) {
1334     DEBUG(dbgs() << "CSEing " << *MI << " with " << *Dup);
1335
1336     // Replace virtual registers defined by MI by their counterparts defined
1337     // by Dup.
1338     SmallVector<unsigned, 2> Defs;
1339     for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
1340       const MachineOperand &MO = MI->getOperand(i);
1341
1342       // Physical registers may not differ here.
1343       assert((!MO.isReg() || MO.getReg() == 0 ||
1344               !TargetRegisterInfo::isPhysicalRegister(MO.getReg()) ||
1345               MO.getReg() == Dup->getOperand(i).getReg()) &&
1346              "Instructions with different phys regs are not identical!");
1347
1348       if (MO.isReg() && MO.isDef() &&
1349           !TargetRegisterInfo::isPhysicalRegister(MO.getReg()))
1350         Defs.push_back(i);
1351     }
1352
1353     SmallVector<const TargetRegisterClass*, 2> OrigRCs;
1354     for (unsigned i = 0, e = Defs.size(); i != e; ++i) {
1355       unsigned Idx = Defs[i];
1356       unsigned Reg = MI->getOperand(Idx).getReg();
1357       unsigned DupReg = Dup->getOperand(Idx).getReg();
1358       OrigRCs.push_back(MRI->getRegClass(DupReg));
1359
1360       if (!MRI->constrainRegClass(DupReg, MRI->getRegClass(Reg))) {
1361         // Restore old RCs if more than one defs.
1362         for (unsigned j = 0; j != i; ++j)
1363           MRI->setRegClass(Dup->getOperand(Defs[j]).getReg(), OrigRCs[j]);
1364         return false;
1365       }
1366     }
1367
1368     for (unsigned i = 0, e = Defs.size(); i != e; ++i) {
1369       unsigned Idx = Defs[i];
1370       unsigned Reg = MI->getOperand(Idx).getReg();
1371       unsigned DupReg = Dup->getOperand(Idx).getReg();
1372       MRI->replaceRegWith(Reg, DupReg);
1373       MRI->clearKillFlags(DupReg);
1374     }
1375
1376     MI->eraseFromParent();
1377     ++NumCSEed;
1378     return true;
1379   }
1380   return false;
1381 }
1382
1383 /// MayCSE - Return true if the given instruction will be CSE'd if it's
1384 /// hoisted out of the loop.
1385 bool MachineLICM::MayCSE(MachineInstr *MI) {
1386   unsigned Opcode = MI->getOpcode();
1387   DenseMap<unsigned, std::vector<const MachineInstr*> >::iterator
1388     CI = CSEMap.find(Opcode);
1389   // Do not CSE implicit_def so ProcessImplicitDefs can properly propagate
1390   // the undef property onto uses.
1391   if (CI == CSEMap.end() || MI->isImplicitDef())
1392     return false;
1393
1394   return LookForDuplicate(MI, CI->second) != nullptr;
1395 }
1396
1397 /// Hoist - When an instruction is found to use only loop invariant operands
1398 /// that are safe to hoist, this instruction is called to do the dirty work.
1399 ///
1400 bool MachineLICM::Hoist(MachineInstr *MI, MachineBasicBlock *Preheader) {
1401   // First check whether we should hoist this instruction.
1402   if (!IsLoopInvariantInst(*MI) || !IsProfitableToHoist(*MI)) {
1403     // If not, try unfolding a hoistable load.
1404     MI = ExtractHoistableLoad(MI);
1405     if (!MI) return false;
1406   }
1407
1408   // Now move the instructions to the predecessor, inserting it before any
1409   // terminator instructions.
1410   DEBUG({
1411       dbgs() << "Hoisting " << *MI;
1412       if (Preheader->getBasicBlock())
1413         dbgs() << " to MachineBasicBlock "
1414                << Preheader->getName();
1415       if (MI->getParent()->getBasicBlock())
1416         dbgs() << " from MachineBasicBlock "
1417                << MI->getParent()->getName();
1418       dbgs() << "\n";
1419     });
1420
1421   // If this is the first instruction being hoisted to the preheader,
1422   // initialize the CSE map with potential common expressions.
1423   if (FirstInLoop) {
1424     InitCSEMap(Preheader);
1425     FirstInLoop = false;
1426   }
1427
1428   // Look for opportunity to CSE the hoisted instruction.
1429   unsigned Opcode = MI->getOpcode();
1430   DenseMap<unsigned, std::vector<const MachineInstr*> >::iterator
1431     CI = CSEMap.find(Opcode);
1432   if (!EliminateCSE(MI, CI)) {
1433     // Otherwise, splice the instruction to the preheader.
1434     Preheader->splice(Preheader->getFirstTerminator(),MI->getParent(),MI);
1435
1436     // Update register pressure for BBs from header to this block.
1437     UpdateBackTraceRegPressure(MI);
1438
1439     // Clear the kill flags of any register this instruction defines,
1440     // since they may need to be live throughout the entire loop
1441     // rather than just live for part of it.
1442     for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
1443       MachineOperand &MO = MI->getOperand(i);
1444       if (MO.isReg() && MO.isDef() && !MO.isDead())
1445         MRI->clearKillFlags(MO.getReg());
1446     }
1447
1448     // Add to the CSE map.
1449     if (CI != CSEMap.end())
1450       CI->second.push_back(MI);
1451     else {
1452       std::vector<const MachineInstr*> CSEMIs;
1453       CSEMIs.push_back(MI);
1454       CSEMap.insert(std::make_pair(Opcode, CSEMIs));
1455     }
1456   }
1457
1458   ++NumHoisted;
1459   Changed = true;
1460
1461   return true;
1462 }
1463
1464 MachineBasicBlock *MachineLICM::getCurPreheader() {
1465   // Determine the block to which to hoist instructions. If we can't find a
1466   // suitable loop predecessor, we can't do any hoisting.
1467
1468   // If we've tried to get a preheader and failed, don't try again.
1469   if (CurPreheader == reinterpret_cast<MachineBasicBlock *>(-1))
1470     return nullptr;
1471
1472   if (!CurPreheader) {
1473     CurPreheader = CurLoop->getLoopPreheader();
1474     if (!CurPreheader) {
1475       MachineBasicBlock *Pred = CurLoop->getLoopPredecessor();
1476       if (!Pred) {
1477         CurPreheader = reinterpret_cast<MachineBasicBlock *>(-1);
1478         return nullptr;
1479       }
1480
1481       CurPreheader = Pred->SplitCriticalEdge(CurLoop->getHeader(), this);
1482       if (!CurPreheader) {
1483         CurPreheader = reinterpret_cast<MachineBasicBlock *>(-1);
1484         return nullptr;
1485       }
1486     }
1487   }
1488   return CurPreheader;
1489 }