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