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