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