LLVM API Documentation

RegAllocGreedy.cpp
Go to the documentation of this file.
00001 //===-- RegAllocGreedy.cpp - greedy register allocator --------------------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file defines the RAGreedy function pass for register allocation in
00011 // optimized builds.
00012 //
00013 //===----------------------------------------------------------------------===//
00014 
00015 #include "llvm/CodeGen/Passes.h"
00016 #include "AllocationOrder.h"
00017 #include "InterferenceCache.h"
00018 #include "LiveDebugVariables.h"
00019 #include "RegAllocBase.h"
00020 #include "SpillPlacement.h"
00021 #include "Spiller.h"
00022 #include "SplitKit.h"
00023 #include "llvm/ADT/Statistic.h"
00024 #include "llvm/Analysis/AliasAnalysis.h"
00025 #include "llvm/CodeGen/CalcSpillWeights.h"
00026 #include "llvm/CodeGen/EdgeBundles.h"
00027 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
00028 #include "llvm/CodeGen/LiveRangeEdit.h"
00029 #include "llvm/CodeGen/LiveRegMatrix.h"
00030 #include "llvm/CodeGen/LiveStackAnalysis.h"
00031 #include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
00032 #include "llvm/CodeGen/MachineDominators.h"
00033 #include "llvm/CodeGen/MachineFunctionPass.h"
00034 #include "llvm/CodeGen/MachineLoopInfo.h"
00035 #include "llvm/CodeGen/MachineRegisterInfo.h"
00036 #include "llvm/CodeGen/RegAllocRegistry.h"
00037 #include "llvm/CodeGen/RegisterClassInfo.h"
00038 #include "llvm/CodeGen/VirtRegMap.h"
00039 #include "llvm/IR/LLVMContext.h"
00040 #include "llvm/PassAnalysisSupport.h"
00041 #include "llvm/Support/BranchProbability.h"
00042 #include "llvm/Support/CommandLine.h"
00043 #include "llvm/Support/Debug.h"
00044 #include "llvm/Support/ErrorHandling.h"
00045 #include "llvm/Support/Timer.h"
00046 #include "llvm/Support/raw_ostream.h"
00047 #include "llvm/Target/TargetSubtargetInfo.h"
00048 #include <queue>
00049 
00050 using namespace llvm;
00051 
00052 #define DEBUG_TYPE "regalloc"
00053 
00054 STATISTIC(NumGlobalSplits, "Number of split global live ranges");
00055 STATISTIC(NumLocalSplits,  "Number of split local live ranges");
00056 STATISTIC(NumEvicted,      "Number of interferences evicted");
00057 
00058 static cl::opt<SplitEditor::ComplementSpillMode>
00059 SplitSpillMode("split-spill-mode", cl::Hidden,
00060   cl::desc("Spill mode for splitting live ranges"),
00061   cl::values(clEnumValN(SplitEditor::SM_Partition, "default", "Default"),
00062              clEnumValN(SplitEditor::SM_Size,  "size",  "Optimize for size"),
00063              clEnumValN(SplitEditor::SM_Speed, "speed", "Optimize for speed"),
00064              clEnumValEnd),
00065   cl::init(SplitEditor::SM_Partition));
00066 
00067 static cl::opt<unsigned>
00068 LastChanceRecoloringMaxDepth("lcr-max-depth", cl::Hidden,
00069                              cl::desc("Last chance recoloring max depth"),
00070                              cl::init(5));
00071 
00072 static cl::opt<unsigned> LastChanceRecoloringMaxInterference(
00073     "lcr-max-interf", cl::Hidden,
00074     cl::desc("Last chance recoloring maximum number of considered"
00075              " interference at a time"),
00076     cl::init(8));
00077 
00078 static cl::opt<bool>
00079 ExhaustiveSearch("exhaustive-register-search", cl::NotHidden,
00080                  cl::desc("Exhaustive Search for registers bypassing the depth "
00081                           "and interference cutoffs of last chance recoloring"));
00082 
00083 static cl::opt<bool> EnableLocalReassignment(
00084     "enable-local-reassign", cl::Hidden,
00085     cl::desc("Local reassignment can yield better allocation decisions, but "
00086              "may be compile time intensive"),
00087     cl::init(false));
00088 
00089 // FIXME: Find a good default for this flag and remove the flag.
00090 static cl::opt<unsigned>
00091 CSRFirstTimeCost("regalloc-csr-first-time-cost",
00092               cl::desc("Cost for first time use of callee-saved register."),
00093               cl::init(0), cl::Hidden);
00094 
00095 static RegisterRegAlloc greedyRegAlloc("greedy", "greedy register allocator",
00096                                        createGreedyRegisterAllocator);
00097 
00098 namespace {
00099 class RAGreedy : public MachineFunctionPass,
00100                  public RegAllocBase,
00101                  private LiveRangeEdit::Delegate {
00102   // Convenient shortcuts.
00103   typedef std::priority_queue<std::pair<unsigned, unsigned> > PQueue;
00104   typedef SmallPtrSet<LiveInterval *, 4> SmallLISet;
00105   typedef SmallSet<unsigned, 16> SmallVirtRegSet;
00106 
00107   // context
00108   MachineFunction *MF;
00109 
00110   // Shortcuts to some useful interface.
00111   const TargetInstrInfo *TII;
00112   const TargetRegisterInfo *TRI;
00113   RegisterClassInfo RCI;
00114 
00115   // analyses
00116   SlotIndexes *Indexes;
00117   MachineBlockFrequencyInfo *MBFI;
00118   MachineDominatorTree *DomTree;
00119   MachineLoopInfo *Loops;
00120   EdgeBundles *Bundles;
00121   SpillPlacement *SpillPlacer;
00122   LiveDebugVariables *DebugVars;
00123 
00124   // state
00125   std::unique_ptr<Spiller> SpillerInstance;
00126   PQueue Queue;
00127   unsigned NextCascade;
00128 
00129   // Live ranges pass through a number of stages as we try to allocate them.
00130   // Some of the stages may also create new live ranges:
00131   //
00132   // - Region splitting.
00133   // - Per-block splitting.
00134   // - Local splitting.
00135   // - Spilling.
00136   //
00137   // Ranges produced by one of the stages skip the previous stages when they are
00138   // dequeued. This improves performance because we can skip interference checks
00139   // that are unlikely to give any results. It also guarantees that the live
00140   // range splitting algorithm terminates, something that is otherwise hard to
00141   // ensure.
00142   enum LiveRangeStage {
00143     /// Newly created live range that has never been queued.
00144     RS_New,
00145 
00146     /// Only attempt assignment and eviction. Then requeue as RS_Split.
00147     RS_Assign,
00148 
00149     /// Attempt live range splitting if assignment is impossible.
00150     RS_Split,
00151 
00152     /// Attempt more aggressive live range splitting that is guaranteed to make
00153     /// progress.  This is used for split products that may not be making
00154     /// progress.
00155     RS_Split2,
00156 
00157     /// Live range will be spilled.  No more splitting will be attempted.
00158     RS_Spill,
00159 
00160     /// There is nothing more we can do to this live range.  Abort compilation
00161     /// if it can't be assigned.
00162     RS_Done
00163   };
00164 
00165   // Enum CutOffStage to keep a track whether the register allocation failed
00166   // because of the cutoffs encountered in last chance recoloring.
00167   // Note: This is used as bitmask. New value should be next power of 2.
00168   enum CutOffStage {
00169     // No cutoffs encountered
00170     CO_None = 0,
00171 
00172     // lcr-max-depth cutoff encountered
00173     CO_Depth = 1,
00174 
00175     // lcr-max-interf cutoff encountered
00176     CO_Interf = 2
00177   };
00178 
00179   uint8_t CutOffInfo;
00180 
00181 #ifndef NDEBUG
00182   static const char *const StageName[];
00183 #endif
00184 
00185   // RegInfo - Keep additional information about each live range.
00186   struct RegInfo {
00187     LiveRangeStage Stage;
00188 
00189     // Cascade - Eviction loop prevention. See canEvictInterference().
00190     unsigned Cascade;
00191 
00192     RegInfo() : Stage(RS_New), Cascade(0) {}
00193   };
00194 
00195   IndexedMap<RegInfo, VirtReg2IndexFunctor> ExtraRegInfo;
00196 
00197   LiveRangeStage getStage(const LiveInterval &VirtReg) const {
00198     return ExtraRegInfo[VirtReg.reg].Stage;
00199   }
00200 
00201   void setStage(const LiveInterval &VirtReg, LiveRangeStage Stage) {
00202     ExtraRegInfo.resize(MRI->getNumVirtRegs());
00203     ExtraRegInfo[VirtReg.reg].Stage = Stage;
00204   }
00205 
00206   template<typename Iterator>
00207   void setStage(Iterator Begin, Iterator End, LiveRangeStage NewStage) {
00208     ExtraRegInfo.resize(MRI->getNumVirtRegs());
00209     for (;Begin != End; ++Begin) {
00210       unsigned Reg = *Begin;
00211       if (ExtraRegInfo[Reg].Stage == RS_New)
00212         ExtraRegInfo[Reg].Stage = NewStage;
00213     }
00214   }
00215 
00216   /// Cost of evicting interference.
00217   struct EvictionCost {
00218     unsigned BrokenHints; ///< Total number of broken hints.
00219     float MaxWeight;      ///< Maximum spill weight evicted.
00220 
00221     EvictionCost(): BrokenHints(0), MaxWeight(0) {}
00222 
00223     bool isMax() const { return BrokenHints == ~0u; }
00224 
00225     void setMax() { BrokenHints = ~0u; }
00226 
00227     void setBrokenHints(unsigned NHints) { BrokenHints = NHints; }
00228 
00229     bool operator<(const EvictionCost &O) const {
00230       return std::tie(BrokenHints, MaxWeight) <
00231              std::tie(O.BrokenHints, O.MaxWeight);
00232     }
00233   };
00234 
00235   // splitting state.
00236   std::unique_ptr<SplitAnalysis> SA;
00237   std::unique_ptr<SplitEditor> SE;
00238 
00239   /// Cached per-block interference maps
00240   InterferenceCache IntfCache;
00241 
00242   /// All basic blocks where the current register has uses.
00243   SmallVector<SpillPlacement::BlockConstraint, 8> SplitConstraints;
00244 
00245   /// Global live range splitting candidate info.
00246   struct GlobalSplitCandidate {
00247     // Register intended for assignment, or 0.
00248     unsigned PhysReg;
00249 
00250     // SplitKit interval index for this candidate.
00251     unsigned IntvIdx;
00252 
00253     // Interference for PhysReg.
00254     InterferenceCache::Cursor Intf;
00255 
00256     // Bundles where this candidate should be live.
00257     BitVector LiveBundles;
00258     SmallVector<unsigned, 8> ActiveBlocks;
00259 
00260     void reset(InterferenceCache &Cache, unsigned Reg) {
00261       PhysReg = Reg;
00262       IntvIdx = 0;
00263       Intf.setPhysReg(Cache, Reg);
00264       LiveBundles.clear();
00265       ActiveBlocks.clear();
00266     }
00267 
00268     // Set B[i] = C for every live bundle where B[i] was NoCand.
00269     unsigned getBundles(SmallVectorImpl<unsigned> &B, unsigned C) {
00270       unsigned Count = 0;
00271       for (int i = LiveBundles.find_first(); i >= 0;
00272            i = LiveBundles.find_next(i))
00273         if (B[i] == NoCand) {
00274           B[i] = C;
00275           Count++;
00276         }
00277       return Count;
00278     }
00279   };
00280 
00281   /// Candidate info for each PhysReg in AllocationOrder.
00282   /// This vector never shrinks, but grows to the size of the largest register
00283   /// class.
00284   SmallVector<GlobalSplitCandidate, 32> GlobalCand;
00285 
00286   enum : unsigned { NoCand = ~0u };
00287 
00288   /// Candidate map. Each edge bundle is assigned to a GlobalCand entry, or to
00289   /// NoCand which indicates the stack interval.
00290   SmallVector<unsigned, 32> BundleCand;
00291 
00292   /// Callee-save register cost, calculated once per machine function.
00293   BlockFrequency CSRCost;
00294 
00295   /// Run or not the local reassignment heuristic. This information is
00296   /// obtained from the TargetSubtargetInfo.
00297   bool EnableLocalReassign;
00298 
00299 public:
00300   RAGreedy();
00301 
00302   /// Return the pass name.
00303   const char* getPassName() const override {
00304     return "Greedy Register Allocator";
00305   }
00306 
00307   /// RAGreedy analysis usage.
00308   void getAnalysisUsage(AnalysisUsage &AU) const override;
00309   void releaseMemory() override;
00310   Spiller &spiller() override { return *SpillerInstance; }
00311   void enqueue(LiveInterval *LI) override;
00312   LiveInterval *dequeue() override;
00313   unsigned selectOrSplit(LiveInterval&, SmallVectorImpl<unsigned>&) override;
00314 
00315   /// Perform register allocation.
00316   bool runOnMachineFunction(MachineFunction &mf) override;
00317 
00318   static char ID;
00319 
00320 private:
00321   unsigned selectOrSplitImpl(LiveInterval &, SmallVectorImpl<unsigned> &,
00322                              SmallVirtRegSet &, unsigned = 0);
00323 
00324   bool LRE_CanEraseVirtReg(unsigned) override;
00325   void LRE_WillShrinkVirtReg(unsigned) override;
00326   void LRE_DidCloneVirtReg(unsigned, unsigned) override;
00327   void enqueue(PQueue &CurQueue, LiveInterval *LI);
00328   LiveInterval *dequeue(PQueue &CurQueue);
00329 
00330   BlockFrequency calcSpillCost();
00331   bool addSplitConstraints(InterferenceCache::Cursor, BlockFrequency&);
00332   void addThroughConstraints(InterferenceCache::Cursor, ArrayRef<unsigned>);
00333   void growRegion(GlobalSplitCandidate &Cand);
00334   BlockFrequency calcGlobalSplitCost(GlobalSplitCandidate&);
00335   bool calcCompactRegion(GlobalSplitCandidate&);
00336   void splitAroundRegion(LiveRangeEdit&, ArrayRef<unsigned>);
00337   void calcGapWeights(unsigned, SmallVectorImpl<float>&);
00338   unsigned canReassign(LiveInterval &VirtReg, unsigned PhysReg);
00339   bool shouldEvict(LiveInterval &A, bool, LiveInterval &B, bool);
00340   bool canEvictInterference(LiveInterval&, unsigned, bool, EvictionCost&);
00341   void evictInterference(LiveInterval&, unsigned,
00342                          SmallVectorImpl<unsigned>&);
00343   bool mayRecolorAllInterferences(unsigned PhysReg, LiveInterval &VirtReg,
00344                                   SmallLISet &RecoloringCandidates,
00345                                   const SmallVirtRegSet &FixedRegisters);
00346 
00347   unsigned tryAssign(LiveInterval&, AllocationOrder&,
00348                      SmallVectorImpl<unsigned>&);
00349   unsigned tryEvict(LiveInterval&, AllocationOrder&,
00350                     SmallVectorImpl<unsigned>&, unsigned = ~0u);
00351   unsigned tryRegionSplit(LiveInterval&, AllocationOrder&,
00352                           SmallVectorImpl<unsigned>&);
00353   /// Calculate cost of region splitting.
00354   unsigned calculateRegionSplitCost(LiveInterval &VirtReg,
00355                                     AllocationOrder &Order,
00356                                     BlockFrequency &BestCost,
00357                                     unsigned &NumCands, bool IgnoreCSR);
00358   /// Perform region splitting.
00359   unsigned doRegionSplit(LiveInterval &VirtReg, unsigned BestCand,
00360                          bool HasCompact,
00361                          SmallVectorImpl<unsigned> &NewVRegs);
00362   /// Check other options before using a callee-saved register for the first
00363   /// time.
00364   unsigned tryAssignCSRFirstTime(LiveInterval &VirtReg, AllocationOrder &Order,
00365                                  unsigned PhysReg, unsigned &CostPerUseLimit,
00366                                  SmallVectorImpl<unsigned> &NewVRegs);
00367   void initializeCSRCost();
00368   unsigned tryBlockSplit(LiveInterval&, AllocationOrder&,
00369                          SmallVectorImpl<unsigned>&);
00370   unsigned tryInstructionSplit(LiveInterval&, AllocationOrder&,
00371                                SmallVectorImpl<unsigned>&);
00372   unsigned tryLocalSplit(LiveInterval&, AllocationOrder&,
00373     SmallVectorImpl<unsigned>&);
00374   unsigned trySplit(LiveInterval&, AllocationOrder&,
00375                     SmallVectorImpl<unsigned>&);
00376   unsigned tryLastChanceRecoloring(LiveInterval &, AllocationOrder &,
00377                                    SmallVectorImpl<unsigned> &,
00378                                    SmallVirtRegSet &, unsigned);
00379   bool tryRecoloringCandidates(PQueue &, SmallVectorImpl<unsigned> &,
00380                                SmallVirtRegSet &, unsigned);
00381 };
00382 } // end anonymous namespace
00383 
00384 char RAGreedy::ID = 0;
00385 
00386 #ifndef NDEBUG
00387 const char *const RAGreedy::StageName[] = {
00388     "RS_New",
00389     "RS_Assign",
00390     "RS_Split",
00391     "RS_Split2",
00392     "RS_Spill",
00393     "RS_Done"
00394 };
00395 #endif
00396 
00397 // Hysteresis to use when comparing floats.
00398 // This helps stabilize decisions based on float comparisons.
00399 const float Hysteresis = (2007 / 2048.0f); // 0.97998046875
00400 
00401 
00402 FunctionPass* llvm::createGreedyRegisterAllocator() {
00403   return new RAGreedy();
00404 }
00405 
00406 RAGreedy::RAGreedy(): MachineFunctionPass(ID) {
00407   initializeLiveDebugVariablesPass(*PassRegistry::getPassRegistry());
00408   initializeSlotIndexesPass(*PassRegistry::getPassRegistry());
00409   initializeLiveIntervalsPass(*PassRegistry::getPassRegistry());
00410   initializeSlotIndexesPass(*PassRegistry::getPassRegistry());
00411   initializeRegisterCoalescerPass(*PassRegistry::getPassRegistry());
00412   initializeMachineSchedulerPass(*PassRegistry::getPassRegistry());
00413   initializeLiveStacksPass(*PassRegistry::getPassRegistry());
00414   initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry());
00415   initializeMachineLoopInfoPass(*PassRegistry::getPassRegistry());
00416   initializeVirtRegMapPass(*PassRegistry::getPassRegistry());
00417   initializeLiveRegMatrixPass(*PassRegistry::getPassRegistry());
00418   initializeEdgeBundlesPass(*PassRegistry::getPassRegistry());
00419   initializeSpillPlacementPass(*PassRegistry::getPassRegistry());
00420 }
00421 
00422 void RAGreedy::getAnalysisUsage(AnalysisUsage &AU) const {
00423   AU.setPreservesCFG();
00424   AU.addRequired<MachineBlockFrequencyInfo>();
00425   AU.addPreserved<MachineBlockFrequencyInfo>();
00426   AU.addRequired<AliasAnalysis>();
00427   AU.addPreserved<AliasAnalysis>();
00428   AU.addRequired<LiveIntervals>();
00429   AU.addPreserved<LiveIntervals>();
00430   AU.addRequired<SlotIndexes>();
00431   AU.addPreserved<SlotIndexes>();
00432   AU.addRequired<LiveDebugVariables>();
00433   AU.addPreserved<LiveDebugVariables>();
00434   AU.addRequired<LiveStacks>();
00435   AU.addPreserved<LiveStacks>();
00436   AU.addRequired<MachineDominatorTree>();
00437   AU.addPreserved<MachineDominatorTree>();
00438   AU.addRequired<MachineLoopInfo>();
00439   AU.addPreserved<MachineLoopInfo>();
00440   AU.addRequired<VirtRegMap>();
00441   AU.addPreserved<VirtRegMap>();
00442   AU.addRequired<LiveRegMatrix>();
00443   AU.addPreserved<LiveRegMatrix>();
00444   AU.addRequired<EdgeBundles>();
00445   AU.addRequired<SpillPlacement>();
00446   MachineFunctionPass::getAnalysisUsage(AU);
00447 }
00448 
00449 
00450 //===----------------------------------------------------------------------===//
00451 //                     LiveRangeEdit delegate methods
00452 //===----------------------------------------------------------------------===//
00453 
00454 bool RAGreedy::LRE_CanEraseVirtReg(unsigned VirtReg) {
00455   if (VRM->hasPhys(VirtReg)) {
00456     Matrix->unassign(LIS->getInterval(VirtReg));
00457     return true;
00458   }
00459   // Unassigned virtreg is probably in the priority queue.
00460   // RegAllocBase will erase it after dequeueing.
00461   return false;
00462 }
00463 
00464 void RAGreedy::LRE_WillShrinkVirtReg(unsigned VirtReg) {
00465   if (!VRM->hasPhys(VirtReg))
00466     return;
00467 
00468   // Register is assigned, put it back on the queue for reassignment.
00469   LiveInterval &LI = LIS->getInterval(VirtReg);
00470   Matrix->unassign(LI);
00471   enqueue(&LI);
00472 }
00473 
00474 void RAGreedy::LRE_DidCloneVirtReg(unsigned New, unsigned Old) {
00475   // Cloning a register we haven't even heard about yet?  Just ignore it.
00476   if (!ExtraRegInfo.inBounds(Old))
00477     return;
00478 
00479   // LRE may clone a virtual register because dead code elimination causes it to
00480   // be split into connected components. The new components are much smaller
00481   // than the original, so they should get a new chance at being assigned.
00482   // same stage as the parent.
00483   ExtraRegInfo[Old].Stage = RS_Assign;
00484   ExtraRegInfo.grow(New);
00485   ExtraRegInfo[New] = ExtraRegInfo[Old];
00486 }
00487 
00488 void RAGreedy::releaseMemory() {
00489   SpillerInstance.reset();
00490   ExtraRegInfo.clear();
00491   GlobalCand.clear();
00492 }
00493 
00494 void RAGreedy::enqueue(LiveInterval *LI) { enqueue(Queue, LI); }
00495 
00496 void RAGreedy::enqueue(PQueue &CurQueue, LiveInterval *LI) {
00497   // Prioritize live ranges by size, assigning larger ranges first.
00498   // The queue holds (size, reg) pairs.
00499   const unsigned Size = LI->getSize();
00500   const unsigned Reg = LI->reg;
00501   assert(TargetRegisterInfo::isVirtualRegister(Reg) &&
00502          "Can only enqueue virtual registers");
00503   unsigned Prio;
00504 
00505   ExtraRegInfo.grow(Reg);
00506   if (ExtraRegInfo[Reg].Stage == RS_New)
00507     ExtraRegInfo[Reg].Stage = RS_Assign;
00508 
00509   if (ExtraRegInfo[Reg].Stage == RS_Split) {
00510     // Unsplit ranges that couldn't be allocated immediately are deferred until
00511     // everything else has been allocated.
00512     Prio = Size;
00513   } else {
00514     // Giant live ranges fall back to the global assignment heuristic, which
00515     // prevents excessive spilling in pathological cases.
00516     bool ReverseLocal = TRI->reverseLocalAssignment();
00517     bool ForceGlobal = !ReverseLocal && TRI->mayOverrideLocalAssignment() &&
00518       (Size / SlotIndex::InstrDist) > (2 * MRI->getRegClass(Reg)->getNumRegs());
00519 
00520     if (ExtraRegInfo[Reg].Stage == RS_Assign && !ForceGlobal && !LI->empty() &&
00521         LIS->intervalIsInOneMBB(*LI)) {
00522       // Allocate original local ranges in linear instruction order. Since they
00523       // are singly defined, this produces optimal coloring in the absence of
00524       // global interference and other constraints.
00525       if (!ReverseLocal)
00526         Prio = LI->beginIndex().getInstrDistance(Indexes->getLastIndex());
00527       else {
00528         // Allocating bottom up may allow many short LRGs to be assigned first
00529         // to one of the cheap registers. This could be much faster for very
00530         // large blocks on targets with many physical registers.
00531         Prio = Indexes->getZeroIndex().getInstrDistance(LI->beginIndex());
00532       }
00533     }
00534     else {
00535       // Allocate global and split ranges in long->short order. Long ranges that
00536       // don't fit should be spilled (or split) ASAP so they don't create
00537       // interference.  Mark a bit to prioritize global above local ranges.
00538       Prio = (1u << 29) + Size;
00539     }
00540     // Mark a higher bit to prioritize global and local above RS_Split.
00541     Prio |= (1u << 31);
00542 
00543     // Boost ranges that have a physical register hint.
00544     if (VRM->hasKnownPreference(Reg))
00545       Prio |= (1u << 30);
00546   }
00547   // The virtual register number is a tie breaker for same-sized ranges.
00548   // Give lower vreg numbers higher priority to assign them first.
00549   CurQueue.push(std::make_pair(Prio, ~Reg));
00550 }
00551 
00552 LiveInterval *RAGreedy::dequeue() { return dequeue(Queue); }
00553 
00554 LiveInterval *RAGreedy::dequeue(PQueue &CurQueue) {
00555   if (CurQueue.empty())
00556     return nullptr;
00557   LiveInterval *LI = &LIS->getInterval(~CurQueue.top().second);
00558   CurQueue.pop();
00559   return LI;
00560 }
00561 
00562 
00563 //===----------------------------------------------------------------------===//
00564 //                            Direct Assignment
00565 //===----------------------------------------------------------------------===//
00566 
00567 /// tryAssign - Try to assign VirtReg to an available register.
00568 unsigned RAGreedy::tryAssign(LiveInterval &VirtReg,
00569                              AllocationOrder &Order,
00570                              SmallVectorImpl<unsigned> &NewVRegs) {
00571   Order.rewind();
00572   unsigned PhysReg;
00573   while ((PhysReg = Order.next()))
00574     if (!Matrix->checkInterference(VirtReg, PhysReg))
00575       break;
00576   if (!PhysReg || Order.isHint())
00577     return PhysReg;
00578 
00579   // PhysReg is available, but there may be a better choice.
00580 
00581   // If we missed a simple hint, try to cheaply evict interference from the
00582   // preferred register.
00583   if (unsigned Hint = MRI->getSimpleHint(VirtReg.reg))
00584     if (Order.isHint(Hint)) {
00585       DEBUG(dbgs() << "missed hint " << PrintReg(Hint, TRI) << '\n');
00586       EvictionCost MaxCost;
00587       MaxCost.setBrokenHints(1);
00588       if (canEvictInterference(VirtReg, Hint, true, MaxCost)) {
00589         evictInterference(VirtReg, Hint, NewVRegs);
00590         return Hint;
00591       }
00592     }
00593 
00594   // Try to evict interference from a cheaper alternative.
00595   unsigned Cost = TRI->getCostPerUse(PhysReg);
00596 
00597   // Most registers have 0 additional cost.
00598   if (!Cost)
00599     return PhysReg;
00600 
00601   DEBUG(dbgs() << PrintReg(PhysReg, TRI) << " is available at cost " << Cost
00602                << '\n');
00603   unsigned CheapReg = tryEvict(VirtReg, Order, NewVRegs, Cost);
00604   return CheapReg ? CheapReg : PhysReg;
00605 }
00606 
00607 
00608 //===----------------------------------------------------------------------===//
00609 //                         Interference eviction
00610 //===----------------------------------------------------------------------===//
00611 
00612 unsigned RAGreedy::canReassign(LiveInterval &VirtReg, unsigned PrevReg) {
00613   AllocationOrder Order(VirtReg.reg, *VRM, RegClassInfo);
00614   unsigned PhysReg;
00615   while ((PhysReg = Order.next())) {
00616     if (PhysReg == PrevReg)
00617       continue;
00618 
00619     MCRegUnitIterator Units(PhysReg, TRI);
00620     for (; Units.isValid(); ++Units) {
00621       // Instantiate a "subquery", not to be confused with the Queries array.
00622       LiveIntervalUnion::Query subQ(&VirtReg, &Matrix->getLiveUnions()[*Units]);
00623       if (subQ.checkInterference())
00624         break;
00625     }
00626     // If no units have interference, break out with the current PhysReg.
00627     if (!Units.isValid())
00628       break;
00629   }
00630   if (PhysReg)
00631     DEBUG(dbgs() << "can reassign: " << VirtReg << " from "
00632           << PrintReg(PrevReg, TRI) << " to " << PrintReg(PhysReg, TRI)
00633           << '\n');
00634   return PhysReg;
00635 }
00636 
00637 /// shouldEvict - determine if A should evict the assigned live range B. The
00638 /// eviction policy defined by this function together with the allocation order
00639 /// defined by enqueue() decides which registers ultimately end up being split
00640 /// and spilled.
00641 ///
00642 /// Cascade numbers are used to prevent infinite loops if this function is a
00643 /// cyclic relation.
00644 ///
00645 /// @param A          The live range to be assigned.
00646 /// @param IsHint     True when A is about to be assigned to its preferred
00647 ///                   register.
00648 /// @param B          The live range to be evicted.
00649 /// @param BreaksHint True when B is already assigned to its preferred register.
00650 bool RAGreedy::shouldEvict(LiveInterval &A, bool IsHint,
00651                            LiveInterval &B, bool BreaksHint) {
00652   bool CanSplit = getStage(B) < RS_Spill;
00653 
00654   // Be fairly aggressive about following hints as long as the evictee can be
00655   // split.
00656   if (CanSplit && IsHint && !BreaksHint)
00657     return true;
00658 
00659   if (A.weight > B.weight) {
00660     DEBUG(dbgs() << "should evict: " << B << " w= " << B.weight << '\n');
00661     return true;
00662   }
00663   return false;
00664 }
00665 
00666 /// canEvictInterference - Return true if all interferences between VirtReg and
00667 /// PhysReg can be evicted.
00668 ///
00669 /// @param VirtReg Live range that is about to be assigned.
00670 /// @param PhysReg Desired register for assignment.
00671 /// @param IsHint  True when PhysReg is VirtReg's preferred register.
00672 /// @param MaxCost Only look for cheaper candidates and update with new cost
00673 ///                when returning true.
00674 /// @returns True when interference can be evicted cheaper than MaxCost.
00675 bool RAGreedy::canEvictInterference(LiveInterval &VirtReg, unsigned PhysReg,
00676                                     bool IsHint, EvictionCost &MaxCost) {
00677   // It is only possible to evict virtual register interference.
00678   if (Matrix->checkInterference(VirtReg, PhysReg) > LiveRegMatrix::IK_VirtReg)
00679     return false;
00680 
00681   bool IsLocal = LIS->intervalIsInOneMBB(VirtReg);
00682 
00683   // Find VirtReg's cascade number. This will be unassigned if VirtReg was never
00684   // involved in an eviction before. If a cascade number was assigned, deny
00685   // evicting anything with the same or a newer cascade number. This prevents
00686   // infinite eviction loops.
00687   //
00688   // This works out so a register without a cascade number is allowed to evict
00689   // anything, and it can be evicted by anything.
00690   unsigned Cascade = ExtraRegInfo[VirtReg.reg].Cascade;
00691   if (!Cascade)
00692     Cascade = NextCascade;
00693 
00694   EvictionCost Cost;
00695   for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
00696     LiveIntervalUnion::Query &Q = Matrix->query(VirtReg, *Units);
00697     // If there is 10 or more interferences, chances are one is heavier.
00698     if (Q.collectInterferingVRegs(10) >= 10)
00699       return false;
00700 
00701     // Check if any interfering live range is heavier than MaxWeight.
00702     for (unsigned i = Q.interferingVRegs().size(); i; --i) {
00703       LiveInterval *Intf = Q.interferingVRegs()[i - 1];
00704       assert(TargetRegisterInfo::isVirtualRegister(Intf->reg) &&
00705              "Only expecting virtual register interference from query");
00706       // Never evict spill products. They cannot split or spill.
00707       if (getStage(*Intf) == RS_Done)
00708         return false;
00709       // Once a live range becomes small enough, it is urgent that we find a
00710       // register for it. This is indicated by an infinite spill weight. These
00711       // urgent live ranges get to evict almost anything.
00712       //
00713       // Also allow urgent evictions of unspillable ranges from a strictly
00714       // larger allocation order.
00715       bool Urgent = !VirtReg.isSpillable() &&
00716         (Intf->isSpillable() ||
00717          RegClassInfo.getNumAllocatableRegs(MRI->getRegClass(VirtReg.reg)) <
00718          RegClassInfo.getNumAllocatableRegs(MRI->getRegClass(Intf->reg)));
00719       // Only evict older cascades or live ranges without a cascade.
00720       unsigned IntfCascade = ExtraRegInfo[Intf->reg].Cascade;
00721       if (Cascade <= IntfCascade) {
00722         if (!Urgent)
00723           return false;
00724         // We permit breaking cascades for urgent evictions. It should be the
00725         // last resort, though, so make it really expensive.
00726         Cost.BrokenHints += 10;
00727       }
00728       // Would this break a satisfied hint?
00729       bool BreaksHint = VRM->hasPreferredPhys(Intf->reg);
00730       // Update eviction cost.
00731       Cost.BrokenHints += BreaksHint;
00732       Cost.MaxWeight = std::max(Cost.MaxWeight, Intf->weight);
00733       // Abort if this would be too expensive.
00734       if (!(Cost < MaxCost))
00735         return false;
00736       if (Urgent)
00737         continue;
00738       // Apply the eviction policy for non-urgent evictions.
00739       if (!shouldEvict(VirtReg, IsHint, *Intf, BreaksHint))
00740         return false;
00741       // If !MaxCost.isMax(), then we're just looking for a cheap register.
00742       // Evicting another local live range in this case could lead to suboptimal
00743       // coloring.
00744       if (!MaxCost.isMax() && IsLocal && LIS->intervalIsInOneMBB(*Intf) &&
00745           (!EnableLocalReassign || !canReassign(*Intf, PhysReg))) {
00746         return false;
00747       }
00748     }
00749   }
00750   MaxCost = Cost;
00751   return true;
00752 }
00753 
00754 /// evictInterference - Evict any interferring registers that prevent VirtReg
00755 /// from being assigned to Physreg. This assumes that canEvictInterference
00756 /// returned true.
00757 void RAGreedy::evictInterference(LiveInterval &VirtReg, unsigned PhysReg,
00758                                  SmallVectorImpl<unsigned> &NewVRegs) {
00759   // Make sure that VirtReg has a cascade number, and assign that cascade
00760   // number to every evicted register. These live ranges than then only be
00761   // evicted by a newer cascade, preventing infinite loops.
00762   unsigned Cascade = ExtraRegInfo[VirtReg.reg].Cascade;
00763   if (!Cascade)
00764     Cascade = ExtraRegInfo[VirtReg.reg].Cascade = NextCascade++;
00765 
00766   DEBUG(dbgs() << "evicting " << PrintReg(PhysReg, TRI)
00767                << " interference: Cascade " << Cascade << '\n');
00768 
00769   // Collect all interfering virtregs first.
00770   SmallVector<LiveInterval*, 8> Intfs;
00771   for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
00772     LiveIntervalUnion::Query &Q = Matrix->query(VirtReg, *Units);
00773     assert(Q.seenAllInterferences() && "Didn't check all interfererences.");
00774     ArrayRef<LiveInterval*> IVR = Q.interferingVRegs();
00775     Intfs.append(IVR.begin(), IVR.end());
00776   }
00777 
00778   // Evict them second. This will invalidate the queries.
00779   for (unsigned i = 0, e = Intfs.size(); i != e; ++i) {
00780     LiveInterval *Intf = Intfs[i];
00781     // The same VirtReg may be present in multiple RegUnits. Skip duplicates.
00782     if (!VRM->hasPhys(Intf->reg))
00783       continue;
00784     Matrix->unassign(*Intf);
00785     assert((ExtraRegInfo[Intf->reg].Cascade < Cascade ||
00786             VirtReg.isSpillable() < Intf->isSpillable()) &&
00787            "Cannot decrease cascade number, illegal eviction");
00788     ExtraRegInfo[Intf->reg].Cascade = Cascade;
00789     ++NumEvicted;
00790     NewVRegs.push_back(Intf->reg);
00791   }
00792 }
00793 
00794 /// tryEvict - Try to evict all interferences for a physreg.
00795 /// @param  VirtReg Currently unassigned virtual register.
00796 /// @param  Order   Physregs to try.
00797 /// @return         Physreg to assign VirtReg, or 0.
00798 unsigned RAGreedy::tryEvict(LiveInterval &VirtReg,
00799                             AllocationOrder &Order,
00800                             SmallVectorImpl<unsigned> &NewVRegs,
00801                             unsigned CostPerUseLimit) {
00802   NamedRegionTimer T("Evict", TimerGroupName, TimePassesIsEnabled);
00803 
00804   // Keep track of the cheapest interference seen so far.
00805   EvictionCost BestCost;
00806   BestCost.setMax();
00807   unsigned BestPhys = 0;
00808   unsigned OrderLimit = Order.getOrder().size();
00809 
00810   // When we are just looking for a reduced cost per use, don't break any
00811   // hints, and only evict smaller spill weights.
00812   if (CostPerUseLimit < ~0u) {
00813     BestCost.BrokenHints = 0;
00814     BestCost.MaxWeight = VirtReg.weight;
00815 
00816     // Check of any registers in RC are below CostPerUseLimit.
00817     const TargetRegisterClass *RC = MRI->getRegClass(VirtReg.reg);
00818     unsigned MinCost = RegClassInfo.getMinCost(RC);
00819     if (MinCost >= CostPerUseLimit) {
00820       DEBUG(dbgs() << RC->getName() << " minimum cost = " << MinCost
00821                    << ", no cheaper registers to be found.\n");
00822       return 0;
00823     }
00824 
00825     // It is normal for register classes to have a long tail of registers with
00826     // the same cost. We don't need to look at them if they're too expensive.
00827     if (TRI->getCostPerUse(Order.getOrder().back()) >= CostPerUseLimit) {
00828       OrderLimit = RegClassInfo.getLastCostChange(RC);
00829       DEBUG(dbgs() << "Only trying the first " << OrderLimit << " regs.\n");
00830     }
00831   }
00832 
00833   Order.rewind();
00834   while (unsigned PhysReg = Order.next(OrderLimit)) {
00835     if (TRI->getCostPerUse(PhysReg) >= CostPerUseLimit)
00836       continue;
00837     // The first use of a callee-saved register in a function has cost 1.
00838     // Don't start using a CSR when the CostPerUseLimit is low.
00839     if (CostPerUseLimit == 1)
00840      if (unsigned CSR = RegClassInfo.getLastCalleeSavedAlias(PhysReg))
00841        if (!MRI->isPhysRegUsed(CSR)) {
00842          DEBUG(dbgs() << PrintReg(PhysReg, TRI) << " would clobber CSR "
00843                       << PrintReg(CSR, TRI) << '\n');
00844          continue;
00845        }
00846 
00847     if (!canEvictInterference(VirtReg, PhysReg, false, BestCost))
00848       continue;
00849 
00850     // Best so far.
00851     BestPhys = PhysReg;
00852 
00853     // Stop if the hint can be used.
00854     if (Order.isHint())
00855       break;
00856   }
00857 
00858   if (!BestPhys)
00859     return 0;
00860 
00861   evictInterference(VirtReg, BestPhys, NewVRegs);
00862   return BestPhys;
00863 }
00864 
00865 
00866 //===----------------------------------------------------------------------===//
00867 //                              Region Splitting
00868 //===----------------------------------------------------------------------===//
00869 
00870 /// addSplitConstraints - Fill out the SplitConstraints vector based on the
00871 /// interference pattern in Physreg and its aliases. Add the constraints to
00872 /// SpillPlacement and return the static cost of this split in Cost, assuming
00873 /// that all preferences in SplitConstraints are met.
00874 /// Return false if there are no bundles with positive bias.
00875 bool RAGreedy::addSplitConstraints(InterferenceCache::Cursor Intf,
00876                                    BlockFrequency &Cost) {
00877   ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks();
00878 
00879   // Reset interference dependent info.
00880   SplitConstraints.resize(UseBlocks.size());
00881   BlockFrequency StaticCost = 0;
00882   for (unsigned i = 0; i != UseBlocks.size(); ++i) {
00883     const SplitAnalysis::BlockInfo &BI = UseBlocks[i];
00884     SpillPlacement::BlockConstraint &BC = SplitConstraints[i];
00885 
00886     BC.Number = BI.MBB->getNumber();
00887     Intf.moveToBlock(BC.Number);
00888     BC.Entry = BI.LiveIn ? SpillPlacement::PrefReg : SpillPlacement::DontCare;
00889     BC.Exit = BI.LiveOut ? SpillPlacement::PrefReg : SpillPlacement::DontCare;
00890     BC.ChangesValue = BI.FirstDef.isValid();
00891 
00892     if (!Intf.hasInterference())
00893       continue;
00894 
00895     // Number of spill code instructions to insert.
00896     unsigned Ins = 0;
00897 
00898     // Interference for the live-in value.
00899     if (BI.LiveIn) {
00900       if (Intf.first() <= Indexes->getMBBStartIdx(BC.Number))
00901         BC.Entry = SpillPlacement::MustSpill, ++Ins;
00902       else if (Intf.first() < BI.FirstInstr)
00903         BC.Entry = SpillPlacement::PrefSpill, ++Ins;
00904       else if (Intf.first() < BI.LastInstr)
00905         ++Ins;
00906     }
00907 
00908     // Interference for the live-out value.
00909     if (BI.LiveOut) {
00910       if (Intf.last() >= SA->getLastSplitPoint(BC.Number))
00911         BC.Exit = SpillPlacement::MustSpill, ++Ins;
00912       else if (Intf.last() > BI.LastInstr)
00913         BC.Exit = SpillPlacement::PrefSpill, ++Ins;
00914       else if (Intf.last() > BI.FirstInstr)
00915         ++Ins;
00916     }
00917 
00918     // Accumulate the total frequency of inserted spill code.
00919     while (Ins--)
00920       StaticCost += SpillPlacer->getBlockFrequency(BC.Number);
00921   }
00922   Cost = StaticCost;
00923 
00924   // Add constraints for use-blocks. Note that these are the only constraints
00925   // that may add a positive bias, it is downhill from here.
00926   SpillPlacer->addConstraints(SplitConstraints);
00927   return SpillPlacer->scanActiveBundles();
00928 }
00929 
00930 
00931 /// addThroughConstraints - Add constraints and links to SpillPlacer from the
00932 /// live-through blocks in Blocks.
00933 void RAGreedy::addThroughConstraints(InterferenceCache::Cursor Intf,
00934                                      ArrayRef<unsigned> Blocks) {
00935   const unsigned GroupSize = 8;
00936   SpillPlacement::BlockConstraint BCS[GroupSize];
00937   unsigned TBS[GroupSize];
00938   unsigned B = 0, T = 0;
00939 
00940   for (unsigned i = 0; i != Blocks.size(); ++i) {
00941     unsigned Number = Blocks[i];
00942     Intf.moveToBlock(Number);
00943 
00944     if (!Intf.hasInterference()) {
00945       assert(T < GroupSize && "Array overflow");
00946       TBS[T] = Number;
00947       if (++T == GroupSize) {
00948         SpillPlacer->addLinks(makeArrayRef(TBS, T));
00949         T = 0;
00950       }
00951       continue;
00952     }
00953 
00954     assert(B < GroupSize && "Array overflow");
00955     BCS[B].Number = Number;
00956 
00957     // Interference for the live-in value.
00958     if (Intf.first() <= Indexes->getMBBStartIdx(Number))
00959       BCS[B].Entry = SpillPlacement::MustSpill;
00960     else
00961       BCS[B].Entry = SpillPlacement::PrefSpill;
00962 
00963     // Interference for the live-out value.
00964     if (Intf.last() >= SA->getLastSplitPoint(Number))
00965       BCS[B].Exit = SpillPlacement::MustSpill;
00966     else
00967       BCS[B].Exit = SpillPlacement::PrefSpill;
00968 
00969     if (++B == GroupSize) {
00970       ArrayRef<SpillPlacement::BlockConstraint> Array(BCS, B);
00971       SpillPlacer->addConstraints(Array);
00972       B = 0;
00973     }
00974   }
00975 
00976   ArrayRef<SpillPlacement::BlockConstraint> Array(BCS, B);
00977   SpillPlacer->addConstraints(Array);
00978   SpillPlacer->addLinks(makeArrayRef(TBS, T));
00979 }
00980 
00981 void RAGreedy::growRegion(GlobalSplitCandidate &Cand) {
00982   // Keep track of through blocks that have not been added to SpillPlacer.
00983   BitVector Todo = SA->getThroughBlocks();
00984   SmallVectorImpl<unsigned> &ActiveBlocks = Cand.ActiveBlocks;
00985   unsigned AddedTo = 0;
00986 #ifndef NDEBUG
00987   unsigned Visited = 0;
00988 #endif
00989 
00990   for (;;) {
00991     ArrayRef<unsigned> NewBundles = SpillPlacer->getRecentPositive();
00992     // Find new through blocks in the periphery of PrefRegBundles.
00993     for (int i = 0, e = NewBundles.size(); i != e; ++i) {
00994       unsigned Bundle = NewBundles[i];
00995       // Look at all blocks connected to Bundle in the full graph.
00996       ArrayRef<unsigned> Blocks = Bundles->getBlocks(Bundle);
00997       for (ArrayRef<unsigned>::iterator I = Blocks.begin(), E = Blocks.end();
00998            I != E; ++I) {
00999         unsigned Block = *I;
01000         if (!Todo.test(Block))
01001           continue;
01002         Todo.reset(Block);
01003         // This is a new through block. Add it to SpillPlacer later.
01004         ActiveBlocks.push_back(Block);
01005 #ifndef NDEBUG
01006         ++Visited;
01007 #endif
01008       }
01009     }
01010     // Any new blocks to add?
01011     if (ActiveBlocks.size() == AddedTo)
01012       break;
01013 
01014     // Compute through constraints from the interference, or assume that all
01015     // through blocks prefer spilling when forming compact regions.
01016     ArrayRef<unsigned> NewBlocks = makeArrayRef(ActiveBlocks).slice(AddedTo);
01017     if (Cand.PhysReg)
01018       addThroughConstraints(Cand.Intf, NewBlocks);
01019     else
01020       // Provide a strong negative bias on through blocks to prevent unwanted
01021       // liveness on loop backedges.
01022       SpillPlacer->addPrefSpill(NewBlocks, /* Strong= */ true);
01023     AddedTo = ActiveBlocks.size();
01024 
01025     // Perhaps iterating can enable more bundles?
01026     SpillPlacer->iterate();
01027   }
01028   DEBUG(dbgs() << ", v=" << Visited);
01029 }
01030 
01031 /// calcCompactRegion - Compute the set of edge bundles that should be live
01032 /// when splitting the current live range into compact regions.  Compact
01033 /// regions can be computed without looking at interference.  They are the
01034 /// regions formed by removing all the live-through blocks from the live range.
01035 ///
01036 /// Returns false if the current live range is already compact, or if the
01037 /// compact regions would form single block regions anyway.
01038 bool RAGreedy::calcCompactRegion(GlobalSplitCandidate &Cand) {
01039   // Without any through blocks, the live range is already compact.
01040   if (!SA->getNumThroughBlocks())
01041     return false;
01042 
01043   // Compact regions don't correspond to any physreg.
01044   Cand.reset(IntfCache, 0);
01045 
01046   DEBUG(dbgs() << "Compact region bundles");
01047 
01048   // Use the spill placer to determine the live bundles. GrowRegion pretends
01049   // that all the through blocks have interference when PhysReg is unset.
01050   SpillPlacer->prepare(Cand.LiveBundles);
01051 
01052   // The static split cost will be zero since Cand.Intf reports no interference.
01053   BlockFrequency Cost;
01054   if (!addSplitConstraints(Cand.Intf, Cost)) {
01055     DEBUG(dbgs() << ", none.\n");
01056     return false;
01057   }
01058 
01059   growRegion(Cand);
01060   SpillPlacer->finish();
01061 
01062   if (!Cand.LiveBundles.any()) {
01063     DEBUG(dbgs() << ", none.\n");
01064     return false;
01065   }
01066 
01067   DEBUG({
01068     for (int i = Cand.LiveBundles.find_first(); i>=0;
01069          i = Cand.LiveBundles.find_next(i))
01070     dbgs() << " EB#" << i;
01071     dbgs() << ".\n";
01072   });
01073   return true;
01074 }
01075 
01076 /// calcSpillCost - Compute how expensive it would be to split the live range in
01077 /// SA around all use blocks instead of forming bundle regions.
01078 BlockFrequency RAGreedy::calcSpillCost() {
01079   BlockFrequency Cost = 0;
01080   ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks();
01081   for (unsigned i = 0; i != UseBlocks.size(); ++i) {
01082     const SplitAnalysis::BlockInfo &BI = UseBlocks[i];
01083     unsigned Number = BI.MBB->getNumber();
01084     // We normally only need one spill instruction - a load or a store.
01085     Cost += SpillPlacer->getBlockFrequency(Number);
01086 
01087     // Unless the value is redefined in the block.
01088     if (BI.LiveIn && BI.LiveOut && BI.FirstDef)
01089       Cost += SpillPlacer->getBlockFrequency(Number);
01090   }
01091   return Cost;
01092 }
01093 
01094 /// calcGlobalSplitCost - Return the global split cost of following the split
01095 /// pattern in LiveBundles. This cost should be added to the local cost of the
01096 /// interference pattern in SplitConstraints.
01097 ///
01098 BlockFrequency RAGreedy::calcGlobalSplitCost(GlobalSplitCandidate &Cand) {
01099   BlockFrequency GlobalCost = 0;
01100   const BitVector &LiveBundles = Cand.LiveBundles;
01101   ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks();
01102   for (unsigned i = 0; i != UseBlocks.size(); ++i) {
01103     const SplitAnalysis::BlockInfo &BI = UseBlocks[i];
01104     SpillPlacement::BlockConstraint &BC = SplitConstraints[i];
01105     bool RegIn  = LiveBundles[Bundles->getBundle(BC.Number, 0)];
01106     bool RegOut = LiveBundles[Bundles->getBundle(BC.Number, 1)];
01107     unsigned Ins = 0;
01108 
01109     if (BI.LiveIn)
01110       Ins += RegIn != (BC.Entry == SpillPlacement::PrefReg);
01111     if (BI.LiveOut)
01112       Ins += RegOut != (BC.Exit == SpillPlacement::PrefReg);
01113     while (Ins--)
01114       GlobalCost += SpillPlacer->getBlockFrequency(BC.Number);
01115   }
01116 
01117   for (unsigned i = 0, e = Cand.ActiveBlocks.size(); i != e; ++i) {
01118     unsigned Number = Cand.ActiveBlocks[i];
01119     bool RegIn  = LiveBundles[Bundles->getBundle(Number, 0)];
01120     bool RegOut = LiveBundles[Bundles->getBundle(Number, 1)];
01121     if (!RegIn && !RegOut)
01122       continue;
01123     if (RegIn && RegOut) {
01124       // We need double spill code if this block has interference.
01125       Cand.Intf.moveToBlock(Number);
01126       if (Cand.Intf.hasInterference()) {
01127         GlobalCost += SpillPlacer->getBlockFrequency(Number);
01128         GlobalCost += SpillPlacer->getBlockFrequency(Number);
01129       }
01130       continue;
01131     }
01132     // live-in / stack-out or stack-in live-out.
01133     GlobalCost += SpillPlacer->getBlockFrequency(Number);
01134   }
01135   return GlobalCost;
01136 }
01137 
01138 /// splitAroundRegion - Split the current live range around the regions
01139 /// determined by BundleCand and GlobalCand.
01140 ///
01141 /// Before calling this function, GlobalCand and BundleCand must be initialized
01142 /// so each bundle is assigned to a valid candidate, or NoCand for the
01143 /// stack-bound bundles.  The shared SA/SE SplitAnalysis and SplitEditor
01144 /// objects must be initialized for the current live range, and intervals
01145 /// created for the used candidates.
01146 ///
01147 /// @param LREdit    The LiveRangeEdit object handling the current split.
01148 /// @param UsedCands List of used GlobalCand entries. Every BundleCand value
01149 ///                  must appear in this list.
01150 void RAGreedy::splitAroundRegion(LiveRangeEdit &LREdit,
01151                                  ArrayRef<unsigned> UsedCands) {
01152   // These are the intervals created for new global ranges. We may create more
01153   // intervals for local ranges.
01154   const unsigned NumGlobalIntvs = LREdit.size();
01155   DEBUG(dbgs() << "splitAroundRegion with " << NumGlobalIntvs << " globals.\n");
01156   assert(NumGlobalIntvs && "No global intervals configured");
01157 
01158   // Isolate even single instructions when dealing with a proper sub-class.
01159   // That guarantees register class inflation for the stack interval because it
01160   // is all copies.
01161   unsigned Reg = SA->getParent().reg;
01162   bool SingleInstrs = RegClassInfo.isProperSubClass(MRI->getRegClass(Reg));
01163 
01164   // First handle all the blocks with uses.
01165   ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks();
01166   for (unsigned i = 0; i != UseBlocks.size(); ++i) {
01167     const SplitAnalysis::BlockInfo &BI = UseBlocks[i];
01168     unsigned Number = BI.MBB->getNumber();
01169     unsigned IntvIn = 0, IntvOut = 0;
01170     SlotIndex IntfIn, IntfOut;
01171     if (BI.LiveIn) {
01172       unsigned CandIn = BundleCand[Bundles->getBundle(Number, 0)];
01173       if (CandIn != NoCand) {
01174         GlobalSplitCandidate &Cand = GlobalCand[CandIn];
01175         IntvIn = Cand.IntvIdx;
01176         Cand.Intf.moveToBlock(Number);
01177         IntfIn = Cand.Intf.first();
01178       }
01179     }
01180     if (BI.LiveOut) {
01181       unsigned CandOut = BundleCand[Bundles->getBundle(Number, 1)];
01182       if (CandOut != NoCand) {
01183         GlobalSplitCandidate &Cand = GlobalCand[CandOut];
01184         IntvOut = Cand.IntvIdx;
01185         Cand.Intf.moveToBlock(Number);
01186         IntfOut = Cand.Intf.last();
01187       }
01188     }
01189 
01190     // Create separate intervals for isolated blocks with multiple uses.
01191     if (!IntvIn && !IntvOut) {
01192       DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " isolated.\n");
01193       if (SA->shouldSplitSingleBlock(BI, SingleInstrs))
01194         SE->splitSingleBlock(BI);
01195       continue;
01196     }
01197 
01198     if (IntvIn && IntvOut)
01199       SE->splitLiveThroughBlock(Number, IntvIn, IntfIn, IntvOut, IntfOut);
01200     else if (IntvIn)
01201       SE->splitRegInBlock(BI, IntvIn, IntfIn);
01202     else
01203       SE->splitRegOutBlock(BI, IntvOut, IntfOut);
01204   }
01205 
01206   // Handle live-through blocks. The relevant live-through blocks are stored in
01207   // the ActiveBlocks list with each candidate. We need to filter out
01208   // duplicates.
01209   BitVector Todo = SA->getThroughBlocks();
01210   for (unsigned c = 0; c != UsedCands.size(); ++c) {
01211     ArrayRef<unsigned> Blocks = GlobalCand[UsedCands[c]].ActiveBlocks;
01212     for (unsigned i = 0, e = Blocks.size(); i != e; ++i) {
01213       unsigned Number = Blocks[i];
01214       if (!Todo.test(Number))
01215         continue;
01216       Todo.reset(Number);
01217 
01218       unsigned IntvIn = 0, IntvOut = 0;
01219       SlotIndex IntfIn, IntfOut;
01220 
01221       unsigned CandIn = BundleCand[Bundles->getBundle(Number, 0)];
01222       if (CandIn != NoCand) {
01223         GlobalSplitCandidate &Cand = GlobalCand[CandIn];
01224         IntvIn = Cand.IntvIdx;
01225         Cand.Intf.moveToBlock(Number);
01226         IntfIn = Cand.Intf.first();
01227       }
01228 
01229       unsigned CandOut = BundleCand[Bundles->getBundle(Number, 1)];
01230       if (CandOut != NoCand) {
01231         GlobalSplitCandidate &Cand = GlobalCand[CandOut];
01232         IntvOut = Cand.IntvIdx;
01233         Cand.Intf.moveToBlock(Number);
01234         IntfOut = Cand.Intf.last();
01235       }
01236       if (!IntvIn && !IntvOut)
01237         continue;
01238       SE->splitLiveThroughBlock(Number, IntvIn, IntfIn, IntvOut, IntfOut);
01239     }
01240   }
01241 
01242   ++NumGlobalSplits;
01243 
01244   SmallVector<unsigned, 8> IntvMap;
01245   SE->finish(&IntvMap);
01246   DebugVars->splitRegister(Reg, LREdit.regs(), *LIS);
01247 
01248   ExtraRegInfo.resize(MRI->getNumVirtRegs());
01249   unsigned OrigBlocks = SA->getNumLiveBlocks();
01250 
01251   // Sort out the new intervals created by splitting. We get four kinds:
01252   // - Remainder intervals should not be split again.
01253   // - Candidate intervals can be assigned to Cand.PhysReg.
01254   // - Block-local splits are candidates for local splitting.
01255   // - DCE leftovers should go back on the queue.
01256   for (unsigned i = 0, e = LREdit.size(); i != e; ++i) {
01257     LiveInterval &Reg = LIS->getInterval(LREdit.get(i));
01258 
01259     // Ignore old intervals from DCE.
01260     if (getStage(Reg) != RS_New)
01261       continue;
01262 
01263     // Remainder interval. Don't try splitting again, spill if it doesn't
01264     // allocate.
01265     if (IntvMap[i] == 0) {
01266       setStage(Reg, RS_Spill);
01267       continue;
01268     }
01269 
01270     // Global intervals. Allow repeated splitting as long as the number of live
01271     // blocks is strictly decreasing.
01272     if (IntvMap[i] < NumGlobalIntvs) {
01273       if (SA->countLiveBlocks(&Reg) >= OrigBlocks) {
01274         DEBUG(dbgs() << "Main interval covers the same " << OrigBlocks
01275                      << " blocks as original.\n");
01276         // Don't allow repeated splitting as a safe guard against looping.
01277         setStage(Reg, RS_Split2);
01278       }
01279       continue;
01280     }
01281 
01282     // Other intervals are treated as new. This includes local intervals created
01283     // for blocks with multiple uses, and anything created by DCE.
01284   }
01285 
01286   if (VerifyEnabled)
01287     MF->verify(this, "After splitting live range around region");
01288 }
01289 
01290 unsigned RAGreedy::tryRegionSplit(LiveInterval &VirtReg, AllocationOrder &Order,
01291                                   SmallVectorImpl<unsigned> &NewVRegs) {
01292   unsigned NumCands = 0;
01293   BlockFrequency BestCost;
01294 
01295   // Check if we can split this live range around a compact region.
01296   bool HasCompact = calcCompactRegion(GlobalCand.front());
01297   if (HasCompact) {
01298     // Yes, keep GlobalCand[0] as the compact region candidate.
01299     NumCands = 1;
01300     BestCost = BlockFrequency::getMaxFrequency();
01301   } else {
01302     // No benefit from the compact region, our fallback will be per-block
01303     // splitting. Make sure we find a solution that is cheaper than spilling.
01304     BestCost = calcSpillCost();
01305     DEBUG(dbgs() << "Cost of isolating all blocks = ";
01306                  MBFI->printBlockFreq(dbgs(), BestCost) << '\n');
01307   }
01308 
01309   unsigned BestCand =
01310       calculateRegionSplitCost(VirtReg, Order, BestCost, NumCands,
01311                                false/*IgnoreCSR*/);
01312 
01313   // No solutions found, fall back to single block splitting.
01314   if (!HasCompact && BestCand == NoCand)
01315     return 0;
01316 
01317   return doRegionSplit(VirtReg, BestCand, HasCompact, NewVRegs);
01318 }
01319 
01320 unsigned RAGreedy::calculateRegionSplitCost(LiveInterval &VirtReg,
01321                                             AllocationOrder &Order,
01322                                             BlockFrequency &BestCost,
01323                                             unsigned &NumCands,
01324                                             bool IgnoreCSR) {
01325   unsigned BestCand = NoCand;
01326   Order.rewind();
01327   while (unsigned PhysReg = Order.next()) {
01328    if (unsigned CSR = RegClassInfo.getLastCalleeSavedAlias(PhysReg))
01329      if (IgnoreCSR && !MRI->isPhysRegUsed(CSR))
01330        continue;
01331 
01332     // Discard bad candidates before we run out of interference cache cursors.
01333     // This will only affect register classes with a lot of registers (>32).
01334     if (NumCands == IntfCache.getMaxCursors()) {
01335       unsigned WorstCount = ~0u;
01336       unsigned Worst = 0;
01337       for (unsigned i = 0; i != NumCands; ++i) {
01338         if (i == BestCand || !GlobalCand[i].PhysReg)
01339           continue;
01340         unsigned Count = GlobalCand[i].LiveBundles.count();
01341         if (Count < WorstCount)
01342           Worst = i, WorstCount = Count;
01343       }
01344       --NumCands;
01345       GlobalCand[Worst] = GlobalCand[NumCands];
01346       if (BestCand == NumCands)
01347         BestCand = Worst;
01348     }
01349 
01350     if (GlobalCand.size() <= NumCands)
01351       GlobalCand.resize(NumCands+1);
01352     GlobalSplitCandidate &Cand = GlobalCand[NumCands];
01353     Cand.reset(IntfCache, PhysReg);
01354 
01355     SpillPlacer->prepare(Cand.LiveBundles);
01356     BlockFrequency Cost;
01357     if (!addSplitConstraints(Cand.Intf, Cost)) {
01358       DEBUG(dbgs() << PrintReg(PhysReg, TRI) << "\tno positive bundles\n");
01359       continue;
01360     }
01361     DEBUG(dbgs() << PrintReg(PhysReg, TRI) << "\tstatic = ";
01362                  MBFI->printBlockFreq(dbgs(), Cost));
01363     if (Cost >= BestCost) {
01364       DEBUG({
01365         if (BestCand == NoCand)
01366           dbgs() << " worse than no bundles\n";
01367         else
01368           dbgs() << " worse than "
01369                  << PrintReg(GlobalCand[BestCand].PhysReg, TRI) << '\n';
01370       });
01371       continue;
01372     }
01373     growRegion(Cand);
01374 
01375     SpillPlacer->finish();
01376 
01377     // No live bundles, defer to splitSingleBlocks().
01378     if (!Cand.LiveBundles.any()) {
01379       DEBUG(dbgs() << " no bundles.\n");
01380       continue;
01381     }
01382 
01383     Cost += calcGlobalSplitCost(Cand);
01384     DEBUG({
01385       dbgs() << ", total = "; MBFI->printBlockFreq(dbgs(), Cost)
01386                                 << " with bundles";
01387       for (int i = Cand.LiveBundles.find_first(); i>=0;
01388            i = Cand.LiveBundles.find_next(i))
01389         dbgs() << " EB#" << i;
01390       dbgs() << ".\n";
01391     });
01392     if (Cost < BestCost) {
01393       BestCand = NumCands;
01394       BestCost = Cost;
01395     }
01396     ++NumCands;
01397   }
01398   return BestCand;
01399 }
01400 
01401 unsigned RAGreedy::doRegionSplit(LiveInterval &VirtReg, unsigned BestCand,
01402                                  bool HasCompact,
01403                                  SmallVectorImpl<unsigned> &NewVRegs) {
01404   SmallVector<unsigned, 8> UsedCands;
01405   // Prepare split editor.
01406   LiveRangeEdit LREdit(&VirtReg, NewVRegs, *MF, *LIS, VRM, this);
01407   SE->reset(LREdit, SplitSpillMode);
01408 
01409   // Assign all edge bundles to the preferred candidate, or NoCand.
01410   BundleCand.assign(Bundles->getNumBundles(), NoCand);
01411 
01412   // Assign bundles for the best candidate region.
01413   if (BestCand != NoCand) {
01414     GlobalSplitCandidate &Cand = GlobalCand[BestCand];
01415     if (unsigned B = Cand.getBundles(BundleCand, BestCand)) {
01416       UsedCands.push_back(BestCand);
01417       Cand.IntvIdx = SE->openIntv();
01418       DEBUG(dbgs() << "Split for " << PrintReg(Cand.PhysReg, TRI) << " in "
01419                    << B << " bundles, intv " << Cand.IntvIdx << ".\n");
01420       (void)B;
01421     }
01422   }
01423 
01424   // Assign bundles for the compact region.
01425   if (HasCompact) {
01426     GlobalSplitCandidate &Cand = GlobalCand.front();
01427     assert(!Cand.PhysReg && "Compact region has no physreg");
01428     if (unsigned B = Cand.getBundles(BundleCand, 0)) {
01429       UsedCands.push_back(0);
01430       Cand.IntvIdx = SE->openIntv();
01431       DEBUG(dbgs() << "Split for compact region in " << B << " bundles, intv "
01432                    << Cand.IntvIdx << ".\n");
01433       (void)B;
01434     }
01435   }
01436 
01437   splitAroundRegion(LREdit, UsedCands);
01438   return 0;
01439 }
01440 
01441 
01442 //===----------------------------------------------------------------------===//
01443 //                            Per-Block Splitting
01444 //===----------------------------------------------------------------------===//
01445 
01446 /// tryBlockSplit - Split a global live range around every block with uses. This
01447 /// creates a lot of local live ranges, that will be split by tryLocalSplit if
01448 /// they don't allocate.
01449 unsigned RAGreedy::tryBlockSplit(LiveInterval &VirtReg, AllocationOrder &Order,
01450                                  SmallVectorImpl<unsigned> &NewVRegs) {
01451   assert(&SA->getParent() == &VirtReg && "Live range wasn't analyzed");
01452   unsigned Reg = VirtReg.reg;
01453   bool SingleInstrs = RegClassInfo.isProperSubClass(MRI->getRegClass(Reg));
01454   LiveRangeEdit LREdit(&VirtReg, NewVRegs, *MF, *LIS, VRM, this);
01455   SE->reset(LREdit, SplitSpillMode);
01456   ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks();
01457   for (unsigned i = 0; i != UseBlocks.size(); ++i) {
01458     const SplitAnalysis::BlockInfo &BI = UseBlocks[i];
01459     if (SA->shouldSplitSingleBlock(BI, SingleInstrs))
01460       SE->splitSingleBlock(BI);
01461   }
01462   // No blocks were split.
01463   if (LREdit.empty())
01464     return 0;
01465 
01466   // We did split for some blocks.
01467   SmallVector<unsigned, 8> IntvMap;
01468   SE->finish(&IntvMap);
01469 
01470   // Tell LiveDebugVariables about the new ranges.
01471   DebugVars->splitRegister(Reg, LREdit.regs(), *LIS);
01472 
01473   ExtraRegInfo.resize(MRI->getNumVirtRegs());
01474 
01475   // Sort out the new intervals created by splitting. The remainder interval
01476   // goes straight to spilling, the new local ranges get to stay RS_New.
01477   for (unsigned i = 0, e = LREdit.size(); i != e; ++i) {
01478     LiveInterval &LI = LIS->getInterval(LREdit.get(i));
01479     if (getStage(LI) == RS_New && IntvMap[i] == 0)
01480       setStage(LI, RS_Spill);
01481   }
01482 
01483   if (VerifyEnabled)
01484     MF->verify(this, "After splitting live range around basic blocks");
01485   return 0;
01486 }
01487 
01488 
01489 //===----------------------------------------------------------------------===//
01490 //                         Per-Instruction Splitting
01491 //===----------------------------------------------------------------------===//
01492 
01493 /// Get the number of allocatable registers that match the constraints of \p Reg
01494 /// on \p MI and that are also in \p SuperRC.
01495 static unsigned getNumAllocatableRegsForConstraints(
01496     const MachineInstr *MI, unsigned Reg, const TargetRegisterClass *SuperRC,
01497     const TargetInstrInfo *TII, const TargetRegisterInfo *TRI,
01498     const RegisterClassInfo &RCI) {
01499   assert(SuperRC && "Invalid register class");
01500 
01501   const TargetRegisterClass *ConstrainedRC =
01502       MI->getRegClassConstraintEffectForVReg(Reg, SuperRC, TII, TRI,
01503                                              /* ExploreBundle */ true);
01504   if (!ConstrainedRC)
01505     return 0;
01506   return RCI.getNumAllocatableRegs(ConstrainedRC);
01507 }
01508 
01509 /// tryInstructionSplit - Split a live range around individual instructions.
01510 /// This is normally not worthwhile since the spiller is doing essentially the
01511 /// same thing. However, when the live range is in a constrained register
01512 /// class, it may help to insert copies such that parts of the live range can
01513 /// be moved to a larger register class.
01514 ///
01515 /// This is similar to spilling to a larger register class.
01516 unsigned
01517 RAGreedy::tryInstructionSplit(LiveInterval &VirtReg, AllocationOrder &Order,
01518                               SmallVectorImpl<unsigned> &NewVRegs) {
01519   const TargetRegisterClass *CurRC = MRI->getRegClass(VirtReg.reg);
01520   // There is no point to this if there are no larger sub-classes.
01521   if (!RegClassInfo.isProperSubClass(CurRC))
01522     return 0;
01523 
01524   // Always enable split spill mode, since we're effectively spilling to a
01525   // register.
01526   LiveRangeEdit LREdit(&VirtReg, NewVRegs, *MF, *LIS, VRM, this);
01527   SE->reset(LREdit, SplitEditor::SM_Size);
01528 
01529   ArrayRef<SlotIndex> Uses = SA->getUseSlots();
01530   if (Uses.size() <= 1)
01531     return 0;
01532 
01533   DEBUG(dbgs() << "Split around " << Uses.size() << " individual instrs.\n");
01534 
01535   const TargetRegisterClass *SuperRC = TRI->getLargestLegalSuperClass(CurRC);
01536   unsigned SuperRCNumAllocatableRegs = RCI.getNumAllocatableRegs(SuperRC);
01537   // Split around every non-copy instruction if this split will relax
01538   // the constraints on the virtual register.
01539   // Otherwise, splitting just inserts uncoalescable copies that do not help
01540   // the allocation.
01541   for (unsigned i = 0; i != Uses.size(); ++i) {
01542     if (const MachineInstr *MI = Indexes->getInstructionFromIndex(Uses[i]))
01543       if (MI->isFullCopy() ||
01544           SuperRCNumAllocatableRegs ==
01545               getNumAllocatableRegsForConstraints(MI, VirtReg.reg, SuperRC, TII,
01546                                                   TRI, RCI)) {
01547         DEBUG(dbgs() << "    skip:\t" << Uses[i] << '\t' << *MI);
01548         continue;
01549       }
01550     SE->openIntv();
01551     SlotIndex SegStart = SE->enterIntvBefore(Uses[i]);
01552     SlotIndex SegStop  = SE->leaveIntvAfter(Uses[i]);
01553     SE->useIntv(SegStart, SegStop);
01554   }
01555 
01556   if (LREdit.empty()) {
01557     DEBUG(dbgs() << "All uses were copies.\n");
01558     return 0;
01559   }
01560 
01561   SmallVector<unsigned, 8> IntvMap;
01562   SE->finish(&IntvMap);
01563   DebugVars->splitRegister(VirtReg.reg, LREdit.regs(), *LIS);
01564   ExtraRegInfo.resize(MRI->getNumVirtRegs());
01565 
01566   // Assign all new registers to RS_Spill. This was the last chance.
01567   setStage(LREdit.begin(), LREdit.end(), RS_Spill);
01568   return 0;
01569 }
01570 
01571 
01572 //===----------------------------------------------------------------------===//
01573 //                             Local Splitting
01574 //===----------------------------------------------------------------------===//
01575 
01576 
01577 /// calcGapWeights - Compute the maximum spill weight that needs to be evicted
01578 /// in order to use PhysReg between two entries in SA->UseSlots.
01579 ///
01580 /// GapWeight[i] represents the gap between UseSlots[i] and UseSlots[i+1].
01581 ///
01582 void RAGreedy::calcGapWeights(unsigned PhysReg,
01583                               SmallVectorImpl<float> &GapWeight) {
01584   assert(SA->getUseBlocks().size() == 1 && "Not a local interval");
01585   const SplitAnalysis::BlockInfo &BI = SA->getUseBlocks().front();
01586   ArrayRef<SlotIndex> Uses = SA->getUseSlots();
01587   const unsigned NumGaps = Uses.size()-1;
01588 
01589   // Start and end points for the interference check.
01590   SlotIndex StartIdx =
01591     BI.LiveIn ? BI.FirstInstr.getBaseIndex() : BI.FirstInstr;
01592   SlotIndex StopIdx =
01593     BI.LiveOut ? BI.LastInstr.getBoundaryIndex() : BI.LastInstr;
01594 
01595   GapWeight.assign(NumGaps, 0.0f);
01596 
01597   // Add interference from each overlapping register.
01598   for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
01599     if (!Matrix->query(const_cast<LiveInterval&>(SA->getParent()), *Units)
01600           .checkInterference())
01601       continue;
01602 
01603     // We know that VirtReg is a continuous interval from FirstInstr to
01604     // LastInstr, so we don't need InterferenceQuery.
01605     //
01606     // Interference that overlaps an instruction is counted in both gaps
01607     // surrounding the instruction. The exception is interference before
01608     // StartIdx and after StopIdx.
01609     //
01610     LiveIntervalUnion::SegmentIter IntI =
01611       Matrix->getLiveUnions()[*Units] .find(StartIdx);
01612     for (unsigned Gap = 0; IntI.valid() && IntI.start() < StopIdx; ++IntI) {
01613       // Skip the gaps before IntI.
01614       while (Uses[Gap+1].getBoundaryIndex() < IntI.start())
01615         if (++Gap == NumGaps)
01616           break;
01617       if (Gap == NumGaps)
01618         break;
01619 
01620       // Update the gaps covered by IntI.
01621       const float weight = IntI.value()->weight;
01622       for (; Gap != NumGaps; ++Gap) {
01623         GapWeight[Gap] = std::max(GapWeight[Gap], weight);
01624         if (Uses[Gap+1].getBaseIndex() >= IntI.stop())
01625           break;
01626       }
01627       if (Gap == NumGaps)
01628         break;
01629     }
01630   }
01631 
01632   // Add fixed interference.
01633   for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
01634     const LiveRange &LR = LIS->getRegUnit(*Units);
01635     LiveRange::const_iterator I = LR.find(StartIdx);
01636     LiveRange::const_iterator E = LR.end();
01637 
01638     // Same loop as above. Mark any overlapped gaps as HUGE_VALF.
01639     for (unsigned Gap = 0; I != E && I->start < StopIdx; ++I) {
01640       while (Uses[Gap+1].getBoundaryIndex() < I->start)
01641         if (++Gap == NumGaps)
01642           break;
01643       if (Gap == NumGaps)
01644         break;
01645 
01646       for (; Gap != NumGaps; ++Gap) {
01647         GapWeight[Gap] = llvm::huge_valf;
01648         if (Uses[Gap+1].getBaseIndex() >= I->end)
01649           break;
01650       }
01651       if (Gap == NumGaps)
01652         break;
01653     }
01654   }
01655 }
01656 
01657 /// tryLocalSplit - Try to split VirtReg into smaller intervals inside its only
01658 /// basic block.
01659 ///
01660 unsigned RAGreedy::tryLocalSplit(LiveInterval &VirtReg, AllocationOrder &Order,
01661                                  SmallVectorImpl<unsigned> &NewVRegs) {
01662   assert(SA->getUseBlocks().size() == 1 && "Not a local interval");
01663   const SplitAnalysis::BlockInfo &BI = SA->getUseBlocks().front();
01664 
01665   // Note that it is possible to have an interval that is live-in or live-out
01666   // while only covering a single block - A phi-def can use undef values from
01667   // predecessors, and the block could be a single-block loop.
01668   // We don't bother doing anything clever about such a case, we simply assume
01669   // that the interval is continuous from FirstInstr to LastInstr. We should
01670   // make sure that we don't do anything illegal to such an interval, though.
01671 
01672   ArrayRef<SlotIndex> Uses = SA->getUseSlots();
01673   if (Uses.size() <= 2)
01674     return 0;
01675   const unsigned NumGaps = Uses.size()-1;
01676 
01677   DEBUG({
01678     dbgs() << "tryLocalSplit: ";
01679     for (unsigned i = 0, e = Uses.size(); i != e; ++i)
01680       dbgs() << ' ' << Uses[i];
01681     dbgs() << '\n';
01682   });
01683 
01684   // If VirtReg is live across any register mask operands, compute a list of
01685   // gaps with register masks.
01686   SmallVector<unsigned, 8> RegMaskGaps;
01687   if (Matrix->checkRegMaskInterference(VirtReg)) {
01688     // Get regmask slots for the whole block.
01689     ArrayRef<SlotIndex> RMS = LIS->getRegMaskSlotsInBlock(BI.MBB->getNumber());
01690     DEBUG(dbgs() << RMS.size() << " regmasks in block:");
01691     // Constrain to VirtReg's live range.
01692     unsigned ri = std::lower_bound(RMS.begin(), RMS.end(),
01693                                    Uses.front().getRegSlot()) - RMS.begin();
01694     unsigned re = RMS.size();
01695     for (unsigned i = 0; i != NumGaps && ri != re; ++i) {
01696       // Look for Uses[i] <= RMS <= Uses[i+1].
01697       assert(!SlotIndex::isEarlierInstr(RMS[ri], Uses[i]));
01698       if (SlotIndex::isEarlierInstr(Uses[i+1], RMS[ri]))
01699         continue;
01700       // Skip a regmask on the same instruction as the last use. It doesn't
01701       // overlap the live range.
01702       if (SlotIndex::isSameInstr(Uses[i+1], RMS[ri]) && i+1 == NumGaps)
01703         break;
01704       DEBUG(dbgs() << ' ' << RMS[ri] << ':' << Uses[i] << '-' << Uses[i+1]);
01705       RegMaskGaps.push_back(i);
01706       // Advance ri to the next gap. A regmask on one of the uses counts in
01707       // both gaps.
01708       while (ri != re && SlotIndex::isEarlierInstr(RMS[ri], Uses[i+1]))
01709         ++ri;
01710     }
01711     DEBUG(dbgs() << '\n');
01712   }
01713 
01714   // Since we allow local split results to be split again, there is a risk of
01715   // creating infinite loops. It is tempting to require that the new live
01716   // ranges have less instructions than the original. That would guarantee
01717   // convergence, but it is too strict. A live range with 3 instructions can be
01718   // split 2+3 (including the COPY), and we want to allow that.
01719   //
01720   // Instead we use these rules:
01721   //
01722   // 1. Allow any split for ranges with getStage() < RS_Split2. (Except for the
01723   //    noop split, of course).
01724   // 2. Require progress be made for ranges with getStage() == RS_Split2. All
01725   //    the new ranges must have fewer instructions than before the split.
01726   // 3. New ranges with the same number of instructions are marked RS_Split2,
01727   //    smaller ranges are marked RS_New.
01728   //
01729   // These rules allow a 3 -> 2+3 split once, which we need. They also prevent
01730   // excessive splitting and infinite loops.
01731   //
01732   bool ProgressRequired = getStage(VirtReg) >= RS_Split2;
01733 
01734   // Best split candidate.
01735   unsigned BestBefore = NumGaps;
01736   unsigned BestAfter = 0;
01737   float BestDiff = 0;
01738 
01739   const float blockFreq =
01740     SpillPlacer->getBlockFrequency(BI.MBB->getNumber()).getFrequency() *
01741     (1.0f / MBFI->getEntryFreq());
01742   SmallVector<float, 8> GapWeight;
01743 
01744   Order.rewind();
01745   while (unsigned PhysReg = Order.next()) {
01746     // Keep track of the largest spill weight that would need to be evicted in
01747     // order to make use of PhysReg between UseSlots[i] and UseSlots[i+1].
01748     calcGapWeights(PhysReg, GapWeight);
01749 
01750     // Remove any gaps with regmask clobbers.
01751     if (Matrix->checkRegMaskInterference(VirtReg, PhysReg))
01752       for (unsigned i = 0, e = RegMaskGaps.size(); i != e; ++i)
01753         GapWeight[RegMaskGaps[i]] = llvm::huge_valf;
01754 
01755     // Try to find the best sequence of gaps to close.
01756     // The new spill weight must be larger than any gap interference.
01757 
01758     // We will split before Uses[SplitBefore] and after Uses[SplitAfter].
01759     unsigned SplitBefore = 0, SplitAfter = 1;
01760 
01761     // MaxGap should always be max(GapWeight[SplitBefore..SplitAfter-1]).
01762     // It is the spill weight that needs to be evicted.
01763     float MaxGap = GapWeight[0];
01764 
01765     for (;;) {
01766       // Live before/after split?
01767       const bool LiveBefore = SplitBefore != 0 || BI.LiveIn;
01768       const bool LiveAfter = SplitAfter != NumGaps || BI.LiveOut;
01769 
01770       DEBUG(dbgs() << PrintReg(PhysReg, TRI) << ' '
01771                    << Uses[SplitBefore] << '-' << Uses[SplitAfter]
01772                    << " i=" << MaxGap);
01773 
01774       // Stop before the interval gets so big we wouldn't be making progress.
01775       if (!LiveBefore && !LiveAfter) {
01776         DEBUG(dbgs() << " all\n");
01777         break;
01778       }
01779       // Should the interval be extended or shrunk?
01780       bool Shrink = true;
01781 
01782       // How many gaps would the new range have?
01783       unsigned NewGaps = LiveBefore + SplitAfter - SplitBefore + LiveAfter;
01784 
01785       // Legally, without causing looping?
01786       bool Legal = !ProgressRequired || NewGaps < NumGaps;
01787 
01788       if (Legal && MaxGap < llvm::huge_valf) {
01789         // Estimate the new spill weight. Each instruction reads or writes the
01790         // register. Conservatively assume there are no read-modify-write
01791         // instructions.
01792         //
01793         // Try to guess the size of the new interval.
01794         const float EstWeight = normalizeSpillWeight(blockFreq * (NewGaps + 1),
01795                                  Uses[SplitBefore].distance(Uses[SplitAfter]) +
01796                                  (LiveBefore + LiveAfter)*SlotIndex::InstrDist);
01797         // Would this split be possible to allocate?
01798         // Never allocate all gaps, we wouldn't be making progress.
01799         DEBUG(dbgs() << " w=" << EstWeight);
01800         if (EstWeight * Hysteresis >= MaxGap) {
01801           Shrink = false;
01802           float Diff = EstWeight - MaxGap;
01803           if (Diff > BestDiff) {
01804             DEBUG(dbgs() << " (best)");
01805             BestDiff = Hysteresis * Diff;
01806             BestBefore = SplitBefore;
01807             BestAfter = SplitAfter;
01808           }
01809         }
01810       }
01811 
01812       // Try to shrink.
01813       if (Shrink) {
01814         if (++SplitBefore < SplitAfter) {
01815           DEBUG(dbgs() << " shrink\n");
01816           // Recompute the max when necessary.
01817           if (GapWeight[SplitBefore - 1] >= MaxGap) {
01818             MaxGap = GapWeight[SplitBefore];
01819             for (unsigned i = SplitBefore + 1; i != SplitAfter; ++i)
01820               MaxGap = std::max(MaxGap, GapWeight[i]);
01821           }
01822           continue;
01823         }
01824         MaxGap = 0;
01825       }
01826 
01827       // Try to extend the interval.
01828       if (SplitAfter >= NumGaps) {
01829         DEBUG(dbgs() << " end\n");
01830         break;
01831       }
01832 
01833       DEBUG(dbgs() << " extend\n");
01834       MaxGap = std::max(MaxGap, GapWeight[SplitAfter++]);
01835     }
01836   }
01837 
01838   // Didn't find any candidates?
01839   if (BestBefore == NumGaps)
01840     return 0;
01841 
01842   DEBUG(dbgs() << "Best local split range: " << Uses[BestBefore]
01843                << '-' << Uses[BestAfter] << ", " << BestDiff
01844                << ", " << (BestAfter - BestBefore + 1) << " instrs\n");
01845 
01846   LiveRangeEdit LREdit(&VirtReg, NewVRegs, *MF, *LIS, VRM, this);
01847   SE->reset(LREdit);
01848 
01849   SE->openIntv();
01850   SlotIndex SegStart = SE->enterIntvBefore(Uses[BestBefore]);
01851   SlotIndex SegStop  = SE->leaveIntvAfter(Uses[BestAfter]);
01852   SE->useIntv(SegStart, SegStop);
01853   SmallVector<unsigned, 8> IntvMap;
01854   SE->finish(&IntvMap);
01855   DebugVars->splitRegister(VirtReg.reg, LREdit.regs(), *LIS);
01856 
01857   // If the new range has the same number of instructions as before, mark it as
01858   // RS_Split2 so the next split will be forced to make progress. Otherwise,
01859   // leave the new intervals as RS_New so they can compete.
01860   bool LiveBefore = BestBefore != 0 || BI.LiveIn;
01861   bool LiveAfter = BestAfter != NumGaps || BI.LiveOut;
01862   unsigned NewGaps = LiveBefore + BestAfter - BestBefore + LiveAfter;
01863   if (NewGaps >= NumGaps) {
01864     DEBUG(dbgs() << "Tagging non-progress ranges: ");
01865     assert(!ProgressRequired && "Didn't make progress when it was required.");
01866     for (unsigned i = 0, e = IntvMap.size(); i != e; ++i)
01867       if (IntvMap[i] == 1) {
01868         setStage(LIS->getInterval(LREdit.get(i)), RS_Split2);
01869         DEBUG(dbgs() << PrintReg(LREdit.get(i)));
01870       }
01871     DEBUG(dbgs() << '\n');
01872   }
01873   ++NumLocalSplits;
01874 
01875   return 0;
01876 }
01877 
01878 //===----------------------------------------------------------------------===//
01879 //                          Live Range Splitting
01880 //===----------------------------------------------------------------------===//
01881 
01882 /// trySplit - Try to split VirtReg or one of its interferences, making it
01883 /// assignable.
01884 /// @return Physreg when VirtReg may be assigned and/or new NewVRegs.
01885 unsigned RAGreedy::trySplit(LiveInterval &VirtReg, AllocationOrder &Order,
01886                             SmallVectorImpl<unsigned>&NewVRegs) {
01887   // Ranges must be Split2 or less.
01888   if (getStage(VirtReg) >= RS_Spill)
01889     return 0;
01890 
01891   // Local intervals are handled separately.
01892   if (LIS->intervalIsInOneMBB(VirtReg)) {
01893     NamedRegionTimer T("Local Splitting", TimerGroupName, TimePassesIsEnabled);
01894     SA->analyze(&VirtReg);
01895     unsigned PhysReg = tryLocalSplit(VirtReg, Order, NewVRegs);
01896     if (PhysReg || !NewVRegs.empty())
01897       return PhysReg;
01898     return tryInstructionSplit(VirtReg, Order, NewVRegs);
01899   }
01900 
01901   NamedRegionTimer T("Global Splitting", TimerGroupName, TimePassesIsEnabled);
01902 
01903   SA->analyze(&VirtReg);
01904 
01905   // FIXME: SplitAnalysis may repair broken live ranges coming from the
01906   // coalescer. That may cause the range to become allocatable which means that
01907   // tryRegionSplit won't be making progress. This check should be replaced with
01908   // an assertion when the coalescer is fixed.
01909   if (SA->didRepairRange()) {
01910     // VirtReg has changed, so all cached queries are invalid.
01911     Matrix->invalidateVirtRegs();
01912     if (unsigned PhysReg = tryAssign(VirtReg, Order, NewVRegs))
01913       return PhysReg;
01914   }
01915 
01916   // First try to split around a region spanning multiple blocks. RS_Split2
01917   // ranges already made dubious progress with region splitting, so they go
01918   // straight to single block splitting.
01919   if (getStage(VirtReg) < RS_Split2) {
01920     unsigned PhysReg = tryRegionSplit(VirtReg, Order, NewVRegs);
01921     if (PhysReg || !NewVRegs.empty())
01922       return PhysReg;
01923   }
01924 
01925   // Then isolate blocks.
01926   return tryBlockSplit(VirtReg, Order, NewVRegs);
01927 }
01928 
01929 //===----------------------------------------------------------------------===//
01930 //                          Last Chance Recoloring
01931 //===----------------------------------------------------------------------===//
01932 
01933 /// mayRecolorAllInterferences - Check if the virtual registers that
01934 /// interfere with \p VirtReg on \p PhysReg (or one of its aliases) may be
01935 /// recolored to free \p PhysReg.
01936 /// When true is returned, \p RecoloringCandidates has been augmented with all
01937 /// the live intervals that need to be recolored in order to free \p PhysReg
01938 /// for \p VirtReg.
01939 /// \p FixedRegisters contains all the virtual registers that cannot be
01940 /// recolored.
01941 bool
01942 RAGreedy::mayRecolorAllInterferences(unsigned PhysReg, LiveInterval &VirtReg,
01943                                      SmallLISet &RecoloringCandidates,
01944                                      const SmallVirtRegSet &FixedRegisters) {
01945   const TargetRegisterClass *CurRC = MRI->getRegClass(VirtReg.reg);
01946 
01947   for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
01948     LiveIntervalUnion::Query &Q = Matrix->query(VirtReg, *Units);
01949     // If there is LastChanceRecoloringMaxInterference or more interferences,
01950     // chances are one would not be recolorable.
01951     if (Q.collectInterferingVRegs(LastChanceRecoloringMaxInterference) >=
01952         LastChanceRecoloringMaxInterference && !ExhaustiveSearch) {
01953       DEBUG(dbgs() << "Early abort: too many interferences.\n");
01954       CutOffInfo |= CO_Interf;
01955       return false;
01956     }
01957     for (unsigned i = Q.interferingVRegs().size(); i; --i) {
01958       LiveInterval *Intf = Q.interferingVRegs()[i - 1];
01959       // If Intf is done and sit on the same register class as VirtReg,
01960       // it would not be recolorable as it is in the same state as VirtReg.
01961       if ((getStage(*Intf) == RS_Done &&
01962            MRI->getRegClass(Intf->reg) == CurRC) ||
01963           FixedRegisters.count(Intf->reg)) {
01964         DEBUG(dbgs() << "Early abort: the inteference is not recolorable.\n");
01965         return false;
01966       }
01967       RecoloringCandidates.insert(Intf);
01968     }
01969   }
01970   return true;
01971 }
01972 
01973 /// tryLastChanceRecoloring - Try to assign a color to \p VirtReg by recoloring
01974 /// its interferences.
01975 /// Last chance recoloring chooses a color for \p VirtReg and recolors every
01976 /// virtual register that was using it. The recoloring process may recursively
01977 /// use the last chance recoloring. Therefore, when a virtual register has been
01978 /// assigned a color by this mechanism, it is marked as Fixed, i.e., it cannot
01979 /// be last-chance-recolored again during this recoloring "session".
01980 /// E.g.,
01981 /// Let
01982 /// vA can use {R1, R2    }
01983 /// vB can use {    R2, R3}
01984 /// vC can use {R1        }
01985 /// Where vA, vB, and vC cannot be split anymore (they are reloads for
01986 /// instance) and they all interfere.
01987 ///
01988 /// vA is assigned R1
01989 /// vB is assigned R2
01990 /// vC tries to evict vA but vA is already done.
01991 /// Regular register allocation fails.
01992 ///
01993 /// Last chance recoloring kicks in:
01994 /// vC does as if vA was evicted => vC uses R1.
01995 /// vC is marked as fixed.
01996 /// vA needs to find a color.
01997 /// None are available.
01998 /// vA cannot evict vC: vC is a fixed virtual register now.
01999 /// vA does as if vB was evicted => vA uses R2.
02000 /// vB needs to find a color.
02001 /// R3 is available.
02002 /// Recoloring => vC = R1, vA = R2, vB = R3
02003 ///
02004 /// \p Order defines the preferred allocation order for \p VirtReg.
02005 /// \p NewRegs will contain any new virtual register that have been created
02006 /// (split, spill) during the process and that must be assigned.
02007 /// \p FixedRegisters contains all the virtual registers that cannot be
02008 /// recolored.
02009 /// \p Depth gives the current depth of the last chance recoloring.
02010 /// \return a physical register that can be used for VirtReg or ~0u if none
02011 /// exists.
02012 unsigned RAGreedy::tryLastChanceRecoloring(LiveInterval &VirtReg,
02013                                            AllocationOrder &Order,
02014                                            SmallVectorImpl<unsigned> &NewVRegs,
02015                                            SmallVirtRegSet &FixedRegisters,
02016                                            unsigned Depth) {
02017   DEBUG(dbgs() << "Try last chance recoloring for " << VirtReg << '\n');
02018   // Ranges must be Done.
02019   assert((getStage(VirtReg) >= RS_Done || !VirtReg.isSpillable()) &&
02020          "Last chance recoloring should really be last chance");
02021   // Set the max depth to LastChanceRecoloringMaxDepth.
02022   // We may want to reconsider that if we end up with a too large search space
02023   // for target with hundreds of registers.
02024   // Indeed, in that case we may want to cut the search space earlier.
02025   if (Depth >= LastChanceRecoloringMaxDepth && !ExhaustiveSearch) {
02026     DEBUG(dbgs() << "Abort because max depth has been reached.\n");
02027     CutOffInfo |= CO_Depth;
02028     return ~0u;
02029   }
02030 
02031   // Set of Live intervals that will need to be recolored.
02032   SmallLISet RecoloringCandidates;
02033   // Record the original mapping virtual register to physical register in case
02034   // the recoloring fails.
02035   DenseMap<unsigned, unsigned> VirtRegToPhysReg;
02036   // Mark VirtReg as fixed, i.e., it will not be recolored pass this point in
02037   // this recoloring "session".
02038   FixedRegisters.insert(VirtReg.reg);
02039 
02040   Order.rewind();
02041   while (unsigned PhysReg = Order.next()) {
02042     DEBUG(dbgs() << "Try to assign: " << VirtReg << " to "
02043                  << PrintReg(PhysReg, TRI) << '\n');
02044     RecoloringCandidates.clear();
02045     VirtRegToPhysReg.clear();
02046 
02047     // It is only possible to recolor virtual register interference.
02048     if (Matrix->checkInterference(VirtReg, PhysReg) >
02049         LiveRegMatrix::IK_VirtReg) {
02050       DEBUG(dbgs() << "Some inteferences are not with virtual registers.\n");
02051 
02052       continue;
02053     }
02054 
02055     // Early give up on this PhysReg if it is obvious we cannot recolor all
02056     // the interferences.
02057     if (!mayRecolorAllInterferences(PhysReg, VirtReg, RecoloringCandidates,
02058                                     FixedRegisters)) {
02059       DEBUG(dbgs() << "Some inteferences cannot be recolored.\n");
02060       continue;
02061     }
02062 
02063     // RecoloringCandidates contains all the virtual registers that interfer
02064     // with VirtReg on PhysReg (or one of its aliases).
02065     // Enqueue them for recoloring and perform the actual recoloring.
02066     PQueue RecoloringQueue;
02067     for (SmallLISet::iterator It = RecoloringCandidates.begin(),
02068                               EndIt = RecoloringCandidates.end();
02069          It != EndIt; ++It) {
02070       unsigned ItVirtReg = (*It)->reg;
02071       enqueue(RecoloringQueue, *It);
02072       assert(VRM->hasPhys(ItVirtReg) &&
02073              "Interferences are supposed to be with allocated vairables");
02074 
02075       // Record the current allocation.
02076       VirtRegToPhysReg[ItVirtReg] = VRM->getPhys(ItVirtReg);
02077       // unset the related struct.
02078       Matrix->unassign(**It);
02079     }
02080 
02081     // Do as if VirtReg was assigned to PhysReg so that the underlying
02082     // recoloring has the right information about the interferes and
02083     // available colors.
02084     Matrix->assign(VirtReg, PhysReg);
02085 
02086     // Save the current recoloring state.
02087     // If we cannot recolor all the interferences, we will have to start again
02088     // at this point for the next physical register.
02089     SmallVirtRegSet SaveFixedRegisters(FixedRegisters);
02090     if (tryRecoloringCandidates(RecoloringQueue, NewVRegs, FixedRegisters,
02091                                 Depth)) {
02092       // Do not mess up with the global assignment process.
02093       // I.e., VirtReg must be unassigned.
02094       Matrix->unassign(VirtReg);
02095       return PhysReg;
02096     }
02097 
02098     DEBUG(dbgs() << "Fail to assign: " << VirtReg << " to "
02099                  << PrintReg(PhysReg, TRI) << '\n');
02100 
02101     // The recoloring attempt failed, undo the changes.
02102     FixedRegisters = SaveFixedRegisters;
02103     Matrix->unassign(VirtReg);
02104 
02105     for (SmallLISet::iterator It = RecoloringCandidates.begin(),
02106                               EndIt = RecoloringCandidates.end();
02107          It != EndIt; ++It) {
02108       unsigned ItVirtReg = (*It)->reg;
02109       if (VRM->hasPhys(ItVirtReg))
02110         Matrix->unassign(**It);
02111       Matrix->assign(**It, VirtRegToPhysReg[ItVirtReg]);
02112     }
02113   }
02114 
02115   // Last chance recoloring did not worked either, give up.
02116   return ~0u;
02117 }
02118 
02119 /// tryRecoloringCandidates - Try to assign a new color to every register
02120 /// in \RecoloringQueue.
02121 /// \p NewRegs will contain any new virtual register created during the
02122 /// recoloring process.
02123 /// \p FixedRegisters[in/out] contains all the registers that have been
02124 /// recolored.
02125 /// \return true if all virtual registers in RecoloringQueue were successfully
02126 /// recolored, false otherwise.
02127 bool RAGreedy::tryRecoloringCandidates(PQueue &RecoloringQueue,
02128                                        SmallVectorImpl<unsigned> &NewVRegs,
02129                                        SmallVirtRegSet &FixedRegisters,
02130                                        unsigned Depth) {
02131   while (!RecoloringQueue.empty()) {
02132     LiveInterval *LI = dequeue(RecoloringQueue);
02133     DEBUG(dbgs() << "Try to recolor: " << *LI << '\n');
02134     unsigned PhysReg;
02135     PhysReg = selectOrSplitImpl(*LI, NewVRegs, FixedRegisters, Depth + 1);
02136     if (PhysReg == ~0u || !PhysReg)
02137       return false;
02138     DEBUG(dbgs() << "Recoloring of " << *LI
02139                  << " succeeded with: " << PrintReg(PhysReg, TRI) << '\n');
02140     Matrix->assign(*LI, PhysReg);
02141     FixedRegisters.insert(LI->reg);
02142   }
02143   return true;
02144 }
02145 
02146 //===----------------------------------------------------------------------===//
02147 //                            Main Entry Point
02148 //===----------------------------------------------------------------------===//
02149 
02150 unsigned RAGreedy::selectOrSplit(LiveInterval &VirtReg,
02151                                  SmallVectorImpl<unsigned> &NewVRegs) {
02152   CutOffInfo = CO_None;
02153   LLVMContext &Ctx = MF->getFunction()->getContext();
02154   SmallVirtRegSet FixedRegisters;
02155   unsigned Reg = selectOrSplitImpl(VirtReg, NewVRegs, FixedRegisters);
02156   if (Reg == ~0U && (CutOffInfo != CO_None)) {
02157     uint8_t CutOffEncountered = CutOffInfo & (CO_Depth | CO_Interf);
02158     if (CutOffEncountered == CO_Depth)
02159       Ctx.emitError("register allocation failed: maximum depth for recoloring "
02160                     "reached. Use -fexhaustive-register-search to skip "
02161                     "cutoffs");
02162     else if (CutOffEncountered == CO_Interf)
02163       Ctx.emitError("register allocation failed: maximum interference for "
02164                     "recoloring reached. Use -fexhaustive-register-search "
02165                     "to skip cutoffs");
02166     else if (CutOffEncountered == (CO_Depth | CO_Interf))
02167       Ctx.emitError("register allocation failed: maximum interference and "
02168                     "depth for recoloring reached. Use "
02169                     "-fexhaustive-register-search to skip cutoffs");
02170   }
02171   return Reg;
02172 }
02173 
02174 /// Using a CSR for the first time has a cost because it causes push|pop
02175 /// to be added to prologue|epilogue. Splitting a cold section of the live
02176 /// range can have lower cost than using the CSR for the first time;
02177 /// Spilling a live range in the cold path can have lower cost than using
02178 /// the CSR for the first time. Returns the physical register if we decide
02179 /// to use the CSR; otherwise return 0.
02180 unsigned RAGreedy::tryAssignCSRFirstTime(LiveInterval &VirtReg,
02181                                          AllocationOrder &Order,
02182                                          unsigned PhysReg,
02183                                          unsigned &CostPerUseLimit,
02184                                          SmallVectorImpl<unsigned> &NewVRegs) {
02185   if (getStage(VirtReg) == RS_Spill && VirtReg.isSpillable()) {
02186     // We choose spill over using the CSR for the first time if the spill cost
02187     // is lower than CSRCost.
02188     SA->analyze(&VirtReg);
02189     if (calcSpillCost() >= CSRCost)
02190       return PhysReg;
02191 
02192     // We are going to spill, set CostPerUseLimit to 1 to make sure that
02193     // we will not use a callee-saved register in tryEvict.
02194     CostPerUseLimit = 1;
02195     return 0;
02196   }
02197   if (getStage(VirtReg) < RS_Split) {
02198     // We choose pre-splitting over using the CSR for the first time if
02199     // the cost of splitting is lower than CSRCost.
02200     SA->analyze(&VirtReg);
02201     unsigned NumCands = 0;
02202     BlockFrequency BestCost = CSRCost; // Don't modify CSRCost.
02203     unsigned BestCand = calculateRegionSplitCost(VirtReg, Order, BestCost,
02204                                                  NumCands, true /*IgnoreCSR*/);
02205     if (BestCand == NoCand)
02206       // Use the CSR if we can't find a region split below CSRCost.
02207       return PhysReg;
02208 
02209     // Perform the actual pre-splitting.
02210     doRegionSplit(VirtReg, BestCand, false/*HasCompact*/, NewVRegs);
02211     return 0;
02212   }
02213   return PhysReg;
02214 }
02215 
02216 void RAGreedy::initializeCSRCost() {
02217   // We use the larger one out of the command-line option and the value report
02218   // by TRI.
02219   CSRCost = BlockFrequency(
02220       std::max((unsigned)CSRFirstTimeCost, TRI->getCSRFirstUseCost()));
02221   if (!CSRCost.getFrequency())
02222     return;
02223 
02224   // Raw cost is relative to Entry == 2^14; scale it appropriately.
02225   uint64_t ActualEntry = MBFI->getEntryFreq();
02226   if (!ActualEntry) {
02227     CSRCost = 0;
02228     return;
02229   }
02230   uint64_t FixedEntry = 1 << 14;
02231   if (ActualEntry < FixedEntry)
02232     CSRCost *= BranchProbability(ActualEntry, FixedEntry);
02233   else if (ActualEntry <= UINT32_MAX)
02234     // Invert the fraction and divide.
02235     CSRCost /= BranchProbability(FixedEntry, ActualEntry);
02236   else
02237     // Can't use BranchProbability in general, since it takes 32-bit numbers.
02238     CSRCost = CSRCost.getFrequency() * (ActualEntry / FixedEntry);
02239 }
02240 
02241 unsigned RAGreedy::selectOrSplitImpl(LiveInterval &VirtReg,
02242                                      SmallVectorImpl<unsigned> &NewVRegs,
02243                                      SmallVirtRegSet &FixedRegisters,
02244                                      unsigned Depth) {
02245   unsigned CostPerUseLimit = ~0u;
02246   // First try assigning a free register.
02247   AllocationOrder Order(VirtReg.reg, *VRM, RegClassInfo);
02248   if (unsigned PhysReg = tryAssign(VirtReg, Order, NewVRegs)) {
02249     // We check other options if we are using a CSR for the first time.
02250     bool CSRFirstUse = false;
02251     if (unsigned CSR = RegClassInfo.getLastCalleeSavedAlias(PhysReg))
02252       if (!MRI->isPhysRegUsed(CSR))
02253         CSRFirstUse = true;
02254 
02255     // When NewVRegs is not empty, we may have made decisions such as evicting
02256     // a virtual register, go with the earlier decisions and use the physical
02257     // register.
02258     if (CSRCost.getFrequency() && CSRFirstUse && NewVRegs.empty()) {
02259       unsigned CSRReg = tryAssignCSRFirstTime(VirtReg, Order, PhysReg,
02260                                               CostPerUseLimit, NewVRegs);
02261       if (CSRReg || !NewVRegs.empty())
02262         // Return now if we decide to use a CSR or create new vregs due to
02263         // pre-splitting.
02264         return CSRReg;
02265     } else
02266       return PhysReg;
02267   }
02268 
02269   LiveRangeStage Stage = getStage(VirtReg);
02270   DEBUG(dbgs() << StageName[Stage]
02271                << " Cascade " << ExtraRegInfo[VirtReg.reg].Cascade << '\n');
02272 
02273   // Try to evict a less worthy live range, but only for ranges from the primary
02274   // queue. The RS_Split ranges already failed to do this, and they should not
02275   // get a second chance until they have been split.
02276   if (Stage != RS_Split)
02277     if (unsigned PhysReg = tryEvict(VirtReg, Order, NewVRegs, CostPerUseLimit))
02278       return PhysReg;
02279 
02280   assert(NewVRegs.empty() && "Cannot append to existing NewVRegs");
02281 
02282   // The first time we see a live range, don't try to split or spill.
02283   // Wait until the second time, when all smaller ranges have been allocated.
02284   // This gives a better picture of the interference to split around.
02285   if (Stage < RS_Split) {
02286     setStage(VirtReg, RS_Split);
02287     DEBUG(dbgs() << "wait for second round\n");
02288     NewVRegs.push_back(VirtReg.reg);
02289     return 0;
02290   }
02291 
02292   // If we couldn't allocate a register from spilling, there is probably some
02293   // invalid inline assembly. The base class wil report it.
02294   if (Stage >= RS_Done || !VirtReg.isSpillable())
02295     return tryLastChanceRecoloring(VirtReg, Order, NewVRegs, FixedRegisters,
02296                                    Depth);
02297 
02298   // Try splitting VirtReg or interferences.
02299   unsigned PhysReg = trySplit(VirtReg, Order, NewVRegs);
02300   if (PhysReg || !NewVRegs.empty())
02301     return PhysReg;
02302 
02303   // Finally spill VirtReg itself.
02304   NamedRegionTimer T("Spiller", TimerGroupName, TimePassesIsEnabled);
02305   LiveRangeEdit LRE(&VirtReg, NewVRegs, *MF, *LIS, VRM, this);
02306   spiller().spill(LRE);
02307   setStage(NewVRegs.begin(), NewVRegs.end(), RS_Done);
02308 
02309   if (VerifyEnabled)
02310     MF->verify(this, "After spilling");
02311 
02312   // The live virtual register requesting allocation was spilled, so tell
02313   // the caller not to allocate anything during this round.
02314   return 0;
02315 }
02316 
02317 bool RAGreedy::runOnMachineFunction(MachineFunction &mf) {
02318   DEBUG(dbgs() << "********** GREEDY REGISTER ALLOCATION **********\n"
02319                << "********** Function: " << mf.getName() << '\n');
02320 
02321   MF = &mf;
02322   const TargetMachine &TM = MF->getTarget();
02323   TRI = TM.getRegisterInfo();
02324   TII = TM.getInstrInfo();
02325   RCI.runOnMachineFunction(mf);
02326 
02327   EnableLocalReassign = EnableLocalReassignment ||
02328     TM.getSubtargetImpl()->enableRALocalReassignment(TM.getOptLevel());
02329 
02330   if (VerifyEnabled)
02331     MF->verify(this, "Before greedy register allocator");
02332 
02333   RegAllocBase::init(getAnalysis<VirtRegMap>(),
02334                      getAnalysis<LiveIntervals>(),
02335                      getAnalysis<LiveRegMatrix>());
02336   Indexes = &getAnalysis<SlotIndexes>();
02337   MBFI = &getAnalysis<MachineBlockFrequencyInfo>();
02338   DomTree = &getAnalysis<MachineDominatorTree>();
02339   SpillerInstance.reset(createInlineSpiller(*this, *MF, *VRM));
02340   Loops = &getAnalysis<MachineLoopInfo>();
02341   Bundles = &getAnalysis<EdgeBundles>();
02342   SpillPlacer = &getAnalysis<SpillPlacement>();
02343   DebugVars = &getAnalysis<LiveDebugVariables>();
02344 
02345   initializeCSRCost();
02346 
02347   calculateSpillWeightsAndHints(*LIS, mf, *Loops, *MBFI);
02348 
02349   DEBUG(LIS->dump());
02350 
02351   SA.reset(new SplitAnalysis(*VRM, *LIS, *Loops));
02352   SE.reset(new SplitEditor(*SA, *LIS, *VRM, *DomTree, *MBFI));
02353   ExtraRegInfo.clear();
02354   ExtraRegInfo.resize(MRI->getNumVirtRegs());
02355   NextCascade = 1;
02356   IntfCache.init(MF, Matrix->getLiveUnions(), Indexes, LIS, TRI);
02357   GlobalCand.resize(32);  // This will grow as needed.
02358 
02359   allocatePhysRegs();
02360   releaseMemory();
02361   return true;
02362 }