blob: d1961197119ba62139c319c9fe25f0646a8c1ba0 [file] [log] [blame]
Jakob Stoklund Olesencba2e062010-12-08 03:26:16 +00001//===-- RegAllocGreedy.cpp - greedy register allocator --------------------===//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file defines the RAGreedy function pass for register allocation in
11// optimized builds.
12//
13//===----------------------------------------------------------------------===//
14
15#define DEBUG_TYPE "regalloc"
Jakob Stoklund Olesendd479e92010-12-10 22:21:05 +000016#include "AllocationOrder.h"
Jakob Stoklund Olesen5907d862011-04-02 06:03:35 +000017#include "InterferenceCache.h"
Jakob Stoklund Olesencfafc542011-04-05 21:40:37 +000018#include "LiveDebugVariables.h"
Jakob Stoklund Olesenf428eb62010-12-17 23:16:32 +000019#include "LiveRangeEdit.h"
Jakob Stoklund Olesencba2e062010-12-08 03:26:16 +000020#include "RegAllocBase.h"
21#include "Spiller.h"
Jakob Stoklund Olesenb5fa9332011-01-18 21:13:27 +000022#include "SpillPlacement.h"
Jakob Stoklund Olesend0bb5e22010-12-15 23:46:13 +000023#include "SplitKit.h"
Jakob Stoklund Olesencba2e062010-12-08 03:26:16 +000024#include "VirtRegMap.h"
Jakob Stoklund Olesen0db841f2011-02-17 22:53:48 +000025#include "llvm/ADT/Statistic.h"
Jakob Stoklund Olesencba2e062010-12-08 03:26:16 +000026#include "llvm/Analysis/AliasAnalysis.h"
27#include "llvm/Function.h"
28#include "llvm/PassAnalysisSupport.h"
29#include "llvm/CodeGen/CalcSpillWeights.h"
Jakob Stoklund Olesenb5fa9332011-01-18 21:13:27 +000030#include "llvm/CodeGen/EdgeBundles.h"
Jakob Stoklund Olesencba2e062010-12-08 03:26:16 +000031#include "llvm/CodeGen/LiveIntervalAnalysis.h"
32#include "llvm/CodeGen/LiveStackAnalysis.h"
Jakob Stoklund Olesenf428eb62010-12-17 23:16:32 +000033#include "llvm/CodeGen/MachineDominators.h"
Jakob Stoklund Olesencba2e062010-12-08 03:26:16 +000034#include "llvm/CodeGen/MachineFunctionPass.h"
Jakob Stoklund Olesencba2e062010-12-08 03:26:16 +000035#include "llvm/CodeGen/MachineLoopInfo.h"
Jakob Stoklund Olesend0bb5e22010-12-15 23:46:13 +000036#include "llvm/CodeGen/MachineLoopRanges.h"
Jakob Stoklund Olesencba2e062010-12-08 03:26:16 +000037#include "llvm/CodeGen/MachineRegisterInfo.h"
38#include "llvm/CodeGen/Passes.h"
39#include "llvm/CodeGen/RegAllocRegistry.h"
40#include "llvm/CodeGen/RegisterCoalescer.h"
Jakob Stoklund Olesencba2e062010-12-08 03:26:16 +000041#include "llvm/Target/TargetOptions.h"
Jakob Stoklund Olesencba2e062010-12-08 03:26:16 +000042#include "llvm/Support/Debug.h"
43#include "llvm/Support/ErrorHandling.h"
44#include "llvm/Support/raw_ostream.h"
Jakob Stoklund Olesen533f58e2010-12-11 00:19:56 +000045#include "llvm/Support/Timer.h"
Jakob Stoklund Olesencba2e062010-12-08 03:26:16 +000046
Jakob Stoklund Olesen98d96482011-02-22 23:01:52 +000047#include <queue>
48
Jakob Stoklund Olesencba2e062010-12-08 03:26:16 +000049using namespace llvm;
50
Jakob Stoklund Olesen0db841f2011-02-17 22:53:48 +000051STATISTIC(NumGlobalSplits, "Number of split global live ranges");
52STATISTIC(NumLocalSplits, "Number of split local live ranges");
Jakob Stoklund Olesen0db841f2011-02-17 22:53:48 +000053STATISTIC(NumEvicted, "Number of interferences evicted");
54
Jakob Stoklund Olesencba2e062010-12-08 03:26:16 +000055static RegisterRegAlloc greedyRegAlloc("greedy", "greedy register allocator",
56 createGreedyRegisterAllocator);
57
58namespace {
Jakob Stoklund Olesen92a55f42011-03-09 00:57:29 +000059class RAGreedy : public MachineFunctionPass,
60 public RegAllocBase,
61 private LiveRangeEdit::Delegate {
62
Jakob Stoklund Olesencba2e062010-12-08 03:26:16 +000063 // context
64 MachineFunction *MF;
Jakob Stoklund Olesencba2e062010-12-08 03:26:16 +000065 BitVector ReservedRegs;
66
67 // analyses
Jakob Stoklund Olesenb5fa9332011-01-18 21:13:27 +000068 SlotIndexes *Indexes;
Jakob Stoklund Olesencba2e062010-12-08 03:26:16 +000069 LiveStacks *LS;
Jakob Stoklund Olesenf428eb62010-12-17 23:16:32 +000070 MachineDominatorTree *DomTree;
Jakob Stoklund Olesend0bb5e22010-12-15 23:46:13 +000071 MachineLoopInfo *Loops;
72 MachineLoopRanges *LoopRanges;
Jakob Stoklund Olesenb5fa9332011-01-18 21:13:27 +000073 EdgeBundles *Bundles;
74 SpillPlacement *SpillPlacer;
Jakob Stoklund Olesenf428eb62010-12-17 23:16:32 +000075
Jakob Stoklund Olesencba2e062010-12-08 03:26:16 +000076 // state
77 std::auto_ptr<Spiller> SpillerInstance;
Jakob Stoklund Olesen98d96482011-02-22 23:01:52 +000078 std::priority_queue<std::pair<unsigned, unsigned> > Queue;
Jakob Stoklund Olesen22a1df62011-03-01 21:10:07 +000079
80 // Live ranges pass through a number of stages as we try to allocate them.
81 // Some of the stages may also create new live ranges:
82 //
83 // - Region splitting.
84 // - Per-block splitting.
85 // - Local splitting.
86 // - Spilling.
87 //
88 // Ranges produced by one of the stages skip the previous stages when they are
89 // dequeued. This improves performance because we can skip interference checks
90 // that are unlikely to give any results. It also guarantees that the live
91 // range splitting algorithm terminates, something that is otherwise hard to
92 // ensure.
93 enum LiveRangeStage {
Jakob Stoklund Olesenf22ca3f2011-03-30 02:52:39 +000094 RS_New, ///< Never seen before.
95 RS_First, ///< First time in the queue.
Jakob Stoklund Olesen22a1df62011-03-01 21:10:07 +000096 RS_Second, ///< Second time in the queue.
Jakob Stoklund Olesenfd5c5132011-04-12 19:32:53 +000097 RS_Global, ///< Produced by global splitting.
Jakob Stoklund Olesen22a1df62011-03-01 21:10:07 +000098 RS_Local, ///< Produced by local splitting.
99 RS_Spill ///< Produced by spilling.
100 };
101
102 IndexedMap<unsigned char, VirtReg2IndexFunctor> LRStage;
103
104 LiveRangeStage getStage(const LiveInterval &VirtReg) const {
105 return LiveRangeStage(LRStage[VirtReg.reg]);
106 }
107
108 template<typename Iterator>
109 void setStage(Iterator Begin, Iterator End, LiveRangeStage NewStage) {
110 LRStage.resize(MRI->getNumVirtRegs());
Jakob Stoklund Olesenf22ca3f2011-03-30 02:52:39 +0000111 for (;Begin != End; ++Begin) {
112 unsigned Reg = (*Begin)->reg;
113 if (LRStage[Reg] == RS_New)
114 LRStage[Reg] = NewStage;
115 }
Jakob Stoklund Olesen22a1df62011-03-01 21:10:07 +0000116 }
Jakob Stoklund Olesencba2e062010-12-08 03:26:16 +0000117
Jakob Stoklund Olesenb5fa9332011-01-18 21:13:27 +0000118 // splitting state.
Jakob Stoklund Olesen22a1df62011-03-01 21:10:07 +0000119 std::auto_ptr<SplitAnalysis> SA;
Jakob Stoklund Olesenbece06f2011-03-03 01:29:13 +0000120 std::auto_ptr<SplitEditor> SE;
Jakob Stoklund Olesenb5fa9332011-01-18 21:13:27 +0000121
Jakob Stoklund Oleseneda0fe82011-04-02 06:03:38 +0000122 /// Cached per-block interference maps
123 InterferenceCache IntfCache;
124
Jakob Stoklund Olesen7b41fbe2011-04-07 17:27:46 +0000125 /// All basic blocks where the current register has uses.
Jakob Stoklund Olesen96dcd952011-03-05 01:10:31 +0000126 SmallVector<SpillPlacement::BlockConstraint, 8> SplitConstraints;
Jakob Stoklund Olesenb5fa9332011-01-18 21:13:27 +0000127
Jakob Stoklund Olesen96dcd952011-03-05 01:10:31 +0000128 /// Global live range splitting candidate info.
129 struct GlobalSplitCandidate {
130 unsigned PhysReg;
Jakob Stoklund Olesen96dcd952011-03-05 01:10:31 +0000131 BitVector LiveBundles;
Jakob Stoklund Olesen5db42892011-04-12 21:30:53 +0000132 SmallVector<unsigned, 8> ActiveBlocks;
133
134 void reset(unsigned Reg) {
135 PhysReg = Reg;
136 LiveBundles.clear();
137 ActiveBlocks.clear();
138 }
Jakob Stoklund Olesen96dcd952011-03-05 01:10:31 +0000139 };
140
141 /// Candidate info for for each PhysReg in AllocationOrder.
142 /// This vector never shrinks, but grows to the size of the largest register
143 /// class.
144 SmallVector<GlobalSplitCandidate, 32> GlobalCand;
145
Jakob Stoklund Olesen034a80d2011-02-17 19:13:53 +0000146 /// For every instruction in SA->UseSlots, store the previous non-copy
147 /// instruction.
148 SmallVector<SlotIndex, 8> PrevSlot;
149
Jakob Stoklund Olesencba2e062010-12-08 03:26:16 +0000150public:
151 RAGreedy();
152
153 /// Return the pass name.
154 virtual const char* getPassName() const {
Jakob Stoklund Olesen533f58e2010-12-11 00:19:56 +0000155 return "Greedy Register Allocator";
Jakob Stoklund Olesencba2e062010-12-08 03:26:16 +0000156 }
157
158 /// RAGreedy analysis usage.
159 virtual void getAnalysisUsage(AnalysisUsage &AU) const;
Jakob Stoklund Olesencba2e062010-12-08 03:26:16 +0000160 virtual void releaseMemory();
Jakob Stoklund Olesencba2e062010-12-08 03:26:16 +0000161 virtual Spiller &spiller() { return *SpillerInstance; }
Jakob Stoklund Olesen98d96482011-02-22 23:01:52 +0000162 virtual void enqueue(LiveInterval *LI);
163 virtual LiveInterval *dequeue();
Jakob Stoklund Olesenccdb3fc2011-01-19 22:11:48 +0000164 virtual unsigned selectOrSplit(LiveInterval&,
165 SmallVectorImpl<LiveInterval*>&);
Jakob Stoklund Olesencba2e062010-12-08 03:26:16 +0000166
167 /// Perform register allocation.
168 virtual bool runOnMachineFunction(MachineFunction &mf);
169
170 static char ID;
Andrew Trickb853e6c2010-12-09 18:15:21 +0000171
172private:
Jakob Stoklund Olesen92a55f42011-03-09 00:57:29 +0000173 void LRE_WillEraseInstruction(MachineInstr*);
Jakob Stoklund Olesen7792e982011-03-13 01:23:11 +0000174 bool LRE_CanEraseVirtReg(unsigned);
Jakob Stoklund Olesen1d5b8452011-03-16 22:56:16 +0000175 void LRE_WillShrinkVirtReg(unsigned);
Jakob Stoklund Olesenf22ca3f2011-03-30 02:52:39 +0000176 void LRE_DidCloneVirtReg(unsigned, unsigned);
Jakob Stoklund Olesen92a55f42011-03-09 00:57:29 +0000177
Jakob Stoklund Olesenf4afdfc2011-04-09 02:59:09 +0000178 bool addSplitConstraints(InterferenceCache::Cursor, float&);
179 void addThroughConstraints(InterferenceCache::Cursor, ArrayRef<unsigned>);
Jakob Stoklund Olesen5db42892011-04-12 21:30:53 +0000180 void growRegion(GlobalSplitCandidate &Cand, InterferenceCache::Cursor);
181 float calcGlobalSplitCost(GlobalSplitCandidate&, InterferenceCache::Cursor);
182 void splitAroundRegion(LiveInterval&, GlobalSplitCandidate&,
Jakob Stoklund Olesenccdb3fc2011-01-19 22:11:48 +0000183 SmallVectorImpl<LiveInterval*>&);
Jakob Stoklund Olesen034a80d2011-02-17 19:13:53 +0000184 void calcGapWeights(unsigned, SmallVectorImpl<float>&);
185 SlotIndex getPrevMappedIndex(const MachineInstr*);
186 void calcPrevSlots();
187 unsigned nextSplitPoint(unsigned);
Jakob Stoklund Olesend17924b2011-03-04 21:32:50 +0000188 bool canEvictInterference(LiveInterval&, unsigned, float&);
Jakob Stoklund Olesenb64d92e2010-12-14 00:37:44 +0000189
Jakob Stoklund Olesen98c81412011-02-23 00:29:52 +0000190 unsigned tryEvict(LiveInterval&, AllocationOrder&,
191 SmallVectorImpl<LiveInterval*>&);
Jakob Stoklund Olesenb5fa9332011-01-18 21:13:27 +0000192 unsigned tryRegionSplit(LiveInterval&, AllocationOrder&,
193 SmallVectorImpl<LiveInterval*>&);
Jakob Stoklund Olesen034a80d2011-02-17 19:13:53 +0000194 unsigned tryLocalSplit(LiveInterval&, AllocationOrder&,
195 SmallVectorImpl<LiveInterval*>&);
Jakob Stoklund Olesenb64d92e2010-12-14 00:37:44 +0000196 unsigned trySplit(LiveInterval&, AllocationOrder&,
197 SmallVectorImpl<LiveInterval*>&);
Jakob Stoklund Olesencba2e062010-12-08 03:26:16 +0000198};
199} // end anonymous namespace
200
201char RAGreedy::ID = 0;
202
203FunctionPass* llvm::createGreedyRegisterAllocator() {
204 return new RAGreedy();
205}
206
Jakob Stoklund Olesenf22ca3f2011-03-30 02:52:39 +0000207RAGreedy::RAGreedy(): MachineFunctionPass(ID), LRStage(RS_New) {
Jakob Stoklund Olesencfafc542011-04-05 21:40:37 +0000208 initializeLiveDebugVariablesPass(*PassRegistry::getPassRegistry());
Jakob Stoklund Olesenb5fa9332011-01-18 21:13:27 +0000209 initializeSlotIndexesPass(*PassRegistry::getPassRegistry());
Jakob Stoklund Olesencba2e062010-12-08 03:26:16 +0000210 initializeLiveIntervalsPass(*PassRegistry::getPassRegistry());
211 initializeSlotIndexesPass(*PassRegistry::getPassRegistry());
212 initializeStrongPHIEliminationPass(*PassRegistry::getPassRegistry());
213 initializeRegisterCoalescerAnalysisGroup(*PassRegistry::getPassRegistry());
214 initializeCalculateSpillWeightsPass(*PassRegistry::getPassRegistry());
215 initializeLiveStacksPass(*PassRegistry::getPassRegistry());
216 initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry());
217 initializeMachineLoopInfoPass(*PassRegistry::getPassRegistry());
Jakob Stoklund Olesend0bb5e22010-12-15 23:46:13 +0000218 initializeMachineLoopRangesPass(*PassRegistry::getPassRegistry());
Jakob Stoklund Olesencba2e062010-12-08 03:26:16 +0000219 initializeVirtRegMapPass(*PassRegistry::getPassRegistry());
Jakob Stoklund Olesenb5fa9332011-01-18 21:13:27 +0000220 initializeEdgeBundlesPass(*PassRegistry::getPassRegistry());
221 initializeSpillPlacementPass(*PassRegistry::getPassRegistry());
Jakob Stoklund Olesencba2e062010-12-08 03:26:16 +0000222}
223
224void RAGreedy::getAnalysisUsage(AnalysisUsage &AU) const {
225 AU.setPreservesCFG();
226 AU.addRequired<AliasAnalysis>();
227 AU.addPreserved<AliasAnalysis>();
228 AU.addRequired<LiveIntervals>();
Jakob Stoklund Olesenb5fa9332011-01-18 21:13:27 +0000229 AU.addRequired<SlotIndexes>();
Jakob Stoklund Olesencba2e062010-12-08 03:26:16 +0000230 AU.addPreserved<SlotIndexes>();
Jakob Stoklund Olesencfafc542011-04-05 21:40:37 +0000231 AU.addRequired<LiveDebugVariables>();
232 AU.addPreserved<LiveDebugVariables>();
Jakob Stoklund Olesencba2e062010-12-08 03:26:16 +0000233 if (StrongPHIElim)
234 AU.addRequiredID(StrongPHIEliminationID);
235 AU.addRequiredTransitive<RegisterCoalescer>();
236 AU.addRequired<CalculateSpillWeights>();
237 AU.addRequired<LiveStacks>();
238 AU.addPreserved<LiveStacks>();
Jakob Stoklund Olesenf428eb62010-12-17 23:16:32 +0000239 AU.addRequired<MachineDominatorTree>();
240 AU.addPreserved<MachineDominatorTree>();
Jakob Stoklund Olesencba2e062010-12-08 03:26:16 +0000241 AU.addRequired<MachineLoopInfo>();
242 AU.addPreserved<MachineLoopInfo>();
Jakob Stoklund Olesend0bb5e22010-12-15 23:46:13 +0000243 AU.addRequired<MachineLoopRanges>();
244 AU.addPreserved<MachineLoopRanges>();
Jakob Stoklund Olesencba2e062010-12-08 03:26:16 +0000245 AU.addRequired<VirtRegMap>();
246 AU.addPreserved<VirtRegMap>();
Jakob Stoklund Olesenb5fa9332011-01-18 21:13:27 +0000247 AU.addRequired<EdgeBundles>();
248 AU.addRequired<SpillPlacement>();
Jakob Stoklund Olesencba2e062010-12-08 03:26:16 +0000249 MachineFunctionPass::getAnalysisUsage(AU);
250}
251
Jakob Stoklund Olesen92a55f42011-03-09 00:57:29 +0000252
253//===----------------------------------------------------------------------===//
254// LiveRangeEdit delegate methods
255//===----------------------------------------------------------------------===//
256
257void RAGreedy::LRE_WillEraseInstruction(MachineInstr *MI) {
258 // LRE itself will remove from SlotIndexes and parent basic block.
259 VRM->RemoveMachineInstrFromMaps(MI);
260}
261
Jakob Stoklund Olesen7792e982011-03-13 01:23:11 +0000262bool RAGreedy::LRE_CanEraseVirtReg(unsigned VirtReg) {
263 if (unsigned PhysReg = VRM->getPhys(VirtReg)) {
264 unassign(LIS->getInterval(VirtReg), PhysReg);
265 return true;
266 }
267 // Unassigned virtreg is probably in the priority queue.
268 // RegAllocBase will erase it after dequeueing.
269 return false;
270}
Jakob Stoklund Olesen92a55f42011-03-09 00:57:29 +0000271
Jakob Stoklund Olesen1d5b8452011-03-16 22:56:16 +0000272void RAGreedy::LRE_WillShrinkVirtReg(unsigned VirtReg) {
273 unsigned PhysReg = VRM->getPhys(VirtReg);
274 if (!PhysReg)
275 return;
276
277 // Register is assigned, put it back on the queue for reassignment.
278 LiveInterval &LI = LIS->getInterval(VirtReg);
279 unassign(LI, PhysReg);
280 enqueue(&LI);
281}
282
Jakob Stoklund Olesenf22ca3f2011-03-30 02:52:39 +0000283void RAGreedy::LRE_DidCloneVirtReg(unsigned New, unsigned Old) {
284 // LRE may clone a virtual register because dead code elimination causes it to
285 // be split into connected components. Ensure that the new register gets the
286 // same stage as the parent.
287 LRStage.grow(New);
288 LRStage[New] = LRStage[Old];
289}
290
Jakob Stoklund Olesencba2e062010-12-08 03:26:16 +0000291void RAGreedy::releaseMemory() {
292 SpillerInstance.reset(0);
Jakob Stoklund Olesen22a1df62011-03-01 21:10:07 +0000293 LRStage.clear();
Jakob Stoklund Olesen5db42892011-04-12 21:30:53 +0000294 GlobalCand.clear();
Jakob Stoklund Olesencba2e062010-12-08 03:26:16 +0000295 RegAllocBase::releaseMemory();
296}
297
Jakob Stoklund Olesen98d96482011-02-22 23:01:52 +0000298void RAGreedy::enqueue(LiveInterval *LI) {
299 // Prioritize live ranges by size, assigning larger ranges first.
300 // The queue holds (size, reg) pairs.
Jakob Stoklund Olesen107d3662011-02-24 23:21:36 +0000301 const unsigned Size = LI->getSize();
302 const unsigned Reg = LI->reg;
Jakob Stoklund Olesen98d96482011-02-22 23:01:52 +0000303 assert(TargetRegisterInfo::isVirtualRegister(Reg) &&
304 "Can only enqueue virtual registers");
Jakob Stoklund Olesen107d3662011-02-24 23:21:36 +0000305 unsigned Prio;
Jakob Stoklund Olesen90c1d7d2010-12-08 22:57:16 +0000306
Jakob Stoklund Olesen22a1df62011-03-01 21:10:07 +0000307 LRStage.grow(Reg);
Jakob Stoklund Olesenf22ca3f2011-03-30 02:52:39 +0000308 if (LRStage[Reg] == RS_New)
309 LRStage[Reg] = RS_First;
310
Jakob Stoklund Oleseneb291572011-03-27 22:49:21 +0000311 if (LRStage[Reg] == RS_Second)
312 // Unsplit ranges that couldn't be allocated immediately are deferred until
313 // everything else has been allocated. Long ranges are allocated last so
314 // they are split against realistic interference.
315 Prio = (1u << 31) - Size;
316 else {
317 // Everything else is allocated in long->short order. Long ranges that don't
318 // fit should be spilled ASAP so they don't create interference.
Jakob Stoklund Olesen107d3662011-02-24 23:21:36 +0000319 Prio = (1u << 31) + Size;
Jakob Stoklund Olesend2a50732011-02-23 00:56:56 +0000320
Jakob Stoklund Oleseneb291572011-03-27 22:49:21 +0000321 // Boost ranges that have a physical register hint.
322 if (TargetRegisterInfo::isPhysicalRegister(VRM->getRegAllocPref(Reg)))
323 Prio |= (1u << 30);
324 }
Jakob Stoklund Olesen107d3662011-02-24 23:21:36 +0000325
326 Queue.push(std::make_pair(Prio, Reg));
Jakob Stoklund Olesen90c1d7d2010-12-08 22:57:16 +0000327}
328
Jakob Stoklund Olesen98d96482011-02-22 23:01:52 +0000329LiveInterval *RAGreedy::dequeue() {
330 if (Queue.empty())
331 return 0;
332 LiveInterval *LI = &LIS->getInterval(Queue.top().second);
333 Queue.pop();
334 return LI;
335}
Jakob Stoklund Olesen770d42d2010-12-22 22:01:30 +0000336
337//===----------------------------------------------------------------------===//
Jakob Stoklund Olesen98c81412011-02-23 00:29:52 +0000338// Interference eviction
339//===----------------------------------------------------------------------===//
340
341/// canEvict - Return true if all interferences between VirtReg and PhysReg can
Jakob Stoklund Olesen3f5bedf2011-04-11 21:47:01 +0000342/// be evicted.
343/// Return false if any interference is heavier than MaxWeight.
344/// On return, set MaxWeight to the maximal spill weight of an interference.
Jakob Stoklund Olesen98c81412011-02-23 00:29:52 +0000345bool RAGreedy::canEvictInterference(LiveInterval &VirtReg, unsigned PhysReg,
Jakob Stoklund Olesend17924b2011-03-04 21:32:50 +0000346 float &MaxWeight) {
Jakob Stoklund Olesen98c81412011-02-23 00:29:52 +0000347 float Weight = 0;
348 for (const unsigned *AliasI = TRI->getOverlaps(PhysReg); *AliasI; ++AliasI) {
349 LiveIntervalUnion::Query &Q = query(VirtReg, *AliasI);
Jakob Stoklund Olesen3f5bedf2011-04-11 21:47:01 +0000350 // If there is 10 or more interferences, chances are one is heavier.
351 if (Q.collectInterferingVRegs(10, MaxWeight) >= 10)
Jakob Stoklund Olesen98c81412011-02-23 00:29:52 +0000352 return false;
353
Jakob Stoklund Olesen3f5bedf2011-04-11 21:47:01 +0000354 // Check if any interfering live range is heavier than MaxWeight.
355 for (unsigned i = Q.interferingVRegs().size(); i; --i) {
356 LiveInterval *Intf = Q.interferingVRegs()[i - 1];
Jakob Stoklund Olesen98c81412011-02-23 00:29:52 +0000357 if (TargetRegisterInfo::isPhysicalRegister(Intf->reg))
358 return false;
Jakob Stoklund Olesen3f5bedf2011-04-11 21:47:01 +0000359 if (Intf->weight >= MaxWeight)
Jakob Stoklund Olesen98c81412011-02-23 00:29:52 +0000360 return false;
361 Weight = std::max(Weight, Intf->weight);
Jakob Stoklund Olesen27106382011-02-09 01:14:03 +0000362 }
363 }
Jakob Stoklund Olesen98c81412011-02-23 00:29:52 +0000364 MaxWeight = Weight;
365 return true;
366}
Jakob Stoklund Olesen27106382011-02-09 01:14:03 +0000367
Jakob Stoklund Olesen98c81412011-02-23 00:29:52 +0000368/// tryEvict - Try to evict all interferences for a physreg.
369/// @param VirtReg Currently unassigned virtual register.
370/// @param Order Physregs to try.
371/// @return Physreg to assign VirtReg, or 0.
372unsigned RAGreedy::tryEvict(LiveInterval &VirtReg,
373 AllocationOrder &Order,
374 SmallVectorImpl<LiveInterval*> &NewVRegs){
375 NamedRegionTimer T("Evict", TimerGroupName, TimePassesIsEnabled);
376
Jakob Stoklund Olesen98c81412011-02-23 00:29:52 +0000377 // Keep track of the lightest single interference seen so far.
Jakob Stoklund Olesen3f5bedf2011-04-11 21:47:01 +0000378 float BestWeight = VirtReg.weight;
Jakob Stoklund Olesen98c81412011-02-23 00:29:52 +0000379 unsigned BestPhys = 0;
380
381 Order.rewind();
382 while (unsigned PhysReg = Order.next()) {
Jakob Stoklund Olesen3f5bedf2011-04-11 21:47:01 +0000383 float Weight = BestWeight;
Jakob Stoklund Olesend17924b2011-03-04 21:32:50 +0000384 if (!canEvictInterference(VirtReg, PhysReg, Weight))
Jakob Stoklund Olesen98c81412011-02-23 00:29:52 +0000385 continue;
386
387 // This is an eviction candidate.
Jakob Stoklund Olesen3f5bedf2011-04-11 21:47:01 +0000388 DEBUG(dbgs() << PrintReg(PhysReg, TRI) << " interference = "
Jakob Stoklund Olesen98c81412011-02-23 00:29:52 +0000389 << Weight << '\n');
390 if (BestPhys && Weight >= BestWeight)
391 continue;
392
393 // Best so far.
394 BestPhys = PhysReg;
395 BestWeight = Weight;
Jakob Stoklund Olesen57f1e2c2011-02-25 01:04:22 +0000396 // Stop if the hint can be used.
397 if (Order.isHint(PhysReg))
398 break;
Jakob Stoklund Olesen27106382011-02-09 01:14:03 +0000399 }
400
Jakob Stoklund Olesen98c81412011-02-23 00:29:52 +0000401 if (!BestPhys)
402 return 0;
403
404 DEBUG(dbgs() << "evicting " << PrintReg(BestPhys, TRI) << " interference\n");
405 for (const unsigned *AliasI = TRI->getOverlaps(BestPhys); *AliasI; ++AliasI) {
406 LiveIntervalUnion::Query &Q = query(VirtReg, *AliasI);
407 assert(Q.seenAllInterferences() && "Didn't check all interfererences.");
408 for (unsigned i = 0, e = Q.interferingVRegs().size(); i != e; ++i) {
409 LiveInterval *Intf = Q.interferingVRegs()[i];
410 unassign(*Intf, VRM->getPhys(Intf->reg));
411 ++NumEvicted;
412 NewVRegs.push_back(Intf);
413 }
414 }
415 return BestPhys;
Andrew Trickb853e6c2010-12-09 18:15:21 +0000416}
417
Jakob Stoklund Olesen770d42d2010-12-22 22:01:30 +0000418
419//===----------------------------------------------------------------------===//
Jakob Stoklund Olesenb5fa9332011-01-18 21:13:27 +0000420// Region Splitting
421//===----------------------------------------------------------------------===//
422
Jakob Stoklund Olesen1b400e82011-04-06 21:32:38 +0000423/// addSplitConstraints - Fill out the SplitConstraints vector based on the
424/// interference pattern in Physreg and its aliases. Add the constraints to
425/// SpillPlacement and return the static cost of this split in Cost, assuming
426/// that all preferences in SplitConstraints are met.
Jakob Stoklund Olesenf4afdfc2011-04-09 02:59:09 +0000427/// Return false if there are no bundles with positive bias.
428bool RAGreedy::addSplitConstraints(InterferenceCache::Cursor Intf,
429 float &Cost) {
Jakob Stoklund Olesendb529a82011-04-06 03:57:00 +0000430 ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks();
Jakob Stoklund Oleseneda0fe82011-04-02 06:03:38 +0000431
Jakob Stoklund Olesenb5fa9332011-01-18 21:13:27 +0000432 // Reset interference dependent info.
Jakob Stoklund Olesendb529a82011-04-06 03:57:00 +0000433 SplitConstraints.resize(UseBlocks.size());
Jakob Stoklund Olesen96dcd952011-03-05 01:10:31 +0000434 float StaticCost = 0;
Jakob Stoklund Olesendb529a82011-04-06 03:57:00 +0000435 for (unsigned i = 0; i != UseBlocks.size(); ++i) {
436 const SplitAnalysis::BlockInfo &BI = UseBlocks[i];
Jakob Stoklund Olesen96dcd952011-03-05 01:10:31 +0000437 SpillPlacement::BlockConstraint &BC = SplitConstraints[i];
Jakob Stoklund Olesen96dcd952011-03-05 01:10:31 +0000438
Jakob Stoklund Olesenf0ac26c2011-02-09 22:50:26 +0000439 BC.Number = BI.MBB->getNumber();
Jakob Stoklund Oleseneda0fe82011-04-02 06:03:38 +0000440 Intf.moveToBlock(BC.Number);
Jakob Stoklund Olesendb529a82011-04-06 03:57:00 +0000441 BC.Entry = BI.LiveIn ? SpillPlacement::PrefReg : SpillPlacement::DontCare;
442 BC.Exit = BI.LiveOut ? SpillPlacement::PrefReg : SpillPlacement::DontCare;
Jakob Stoklund Olesenb5fa9332011-01-18 21:13:27 +0000443
Jakob Stoklund Oleseneda0fe82011-04-02 06:03:38 +0000444 if (!Intf.hasInterference())
445 continue;
446
Jakob Stoklund Olesen96dcd952011-03-05 01:10:31 +0000447 // Number of spill code instructions to insert.
448 unsigned Ins = 0;
Jakob Stoklund Olesenb5fa9332011-01-18 21:13:27 +0000449
Jakob Stoklund Olesen96dcd952011-03-05 01:10:31 +0000450 // Interference for the live-in value.
Jakob Stoklund Oleseneda0fe82011-04-02 06:03:38 +0000451 if (BI.LiveIn) {
Jakob Stoklund Olesen6c8afd72011-04-04 15:32:15 +0000452 if (Intf.first() <= Indexes->getMBBStartIdx(BC.Number))
Jakob Stoklund Olesendb529a82011-04-06 03:57:00 +0000453 BC.Entry = SpillPlacement::MustSpill, ++Ins;
Jakob Stoklund Oleseneda0fe82011-04-02 06:03:38 +0000454 else if (Intf.first() < BI.FirstUse)
Jakob Stoklund Olesen96dcd952011-03-05 01:10:31 +0000455 BC.Entry = SpillPlacement::PrefSpill, ++Ins;
Jakob Stoklund Oleseneda0fe82011-04-02 06:03:38 +0000456 else if (Intf.first() < (BI.LiveThrough ? BI.LastUse : BI.Kill))
Jakob Stoklund Olesen96dcd952011-03-05 01:10:31 +0000457 ++Ins;
Jakob Stoklund Olesena50c5392011-02-08 23:02:58 +0000458 }
459
Jakob Stoklund Olesen96dcd952011-03-05 01:10:31 +0000460 // Interference for the live-out value.
Jakob Stoklund Oleseneda0fe82011-04-02 06:03:38 +0000461 if (BI.LiveOut) {
Jakob Stoklund Olesen612f7802011-04-05 04:20:29 +0000462 if (Intf.last() >= SA->getLastSplitPoint(BC.Number))
Jakob Stoklund Olesendb529a82011-04-06 03:57:00 +0000463 BC.Exit = SpillPlacement::MustSpill, ++Ins;
Jakob Stoklund Oleseneda0fe82011-04-02 06:03:38 +0000464 else if (Intf.last() > BI.LastUse)
Jakob Stoklund Olesen96dcd952011-03-05 01:10:31 +0000465 BC.Exit = SpillPlacement::PrefSpill, ++Ins;
Jakob Stoklund Oleseneda0fe82011-04-02 06:03:38 +0000466 else if (Intf.last() > (BI.LiveThrough ? BI.FirstUse : BI.Def))
Jakob Stoklund Olesen96dcd952011-03-05 01:10:31 +0000467 ++Ins;
Jakob Stoklund Olesenb5fa9332011-01-18 21:13:27 +0000468 }
Jakob Stoklund Olesen96dcd952011-03-05 01:10:31 +0000469
470 // Accumulate the total frequency of inserted spill code.
471 if (Ins)
472 StaticCost += Ins * SpillPlacer->getBlockFrequency(BC.Number);
Jakob Stoklund Olesenb5fa9332011-01-18 21:13:27 +0000473 }
Jakob Stoklund Olesenf4afdfc2011-04-09 02:59:09 +0000474 Cost = StaticCost;
Jakob Stoklund Olesendb529a82011-04-06 03:57:00 +0000475
Jakob Stoklund Olesen1b400e82011-04-06 21:32:38 +0000476 // Add constraints for use-blocks. Note that these are the only constraints
477 // that may add a positive bias, it is downhill from here.
478 SpillPlacer->addConstraints(SplitConstraints);
Jakob Stoklund Olesenf4afdfc2011-04-09 02:59:09 +0000479 return SpillPlacer->scanActiveBundles();
480}
Jakob Stoklund Olesen1b400e82011-04-06 21:32:38 +0000481
Jakob Stoklund Olesen1b400e82011-04-06 21:32:38 +0000482
Jakob Stoklund Olesenf4afdfc2011-04-09 02:59:09 +0000483/// addThroughConstraints - Add constraints and links to SpillPlacer from the
484/// live-through blocks in Blocks.
485void RAGreedy::addThroughConstraints(InterferenceCache::Cursor Intf,
486 ArrayRef<unsigned> Blocks) {
Jakob Stoklund Olesen1b400e82011-04-06 21:32:38 +0000487 const unsigned GroupSize = 8;
488 SpillPlacement::BlockConstraint BCS[GroupSize];
Jakob Stoklund Olesenf4afdfc2011-04-09 02:59:09 +0000489 unsigned TBS[GroupSize];
490 unsigned B = 0, T = 0;
Jakob Stoklund Olesen1b400e82011-04-06 21:32:38 +0000491
Jakob Stoklund Olesenf4afdfc2011-04-09 02:59:09 +0000492 for (unsigned i = 0; i != Blocks.size(); ++i) {
493 unsigned Number = Blocks[i];
Jakob Stoklund Olesen1b400e82011-04-06 21:32:38 +0000494 Intf.moveToBlock(Number);
Jakob Stoklund Olesendb529a82011-04-06 03:57:00 +0000495
Jakob Stoklund Olesen7b41fbe2011-04-07 17:27:46 +0000496 if (!Intf.hasInterference()) {
Jakob Stoklund Olesenf4afdfc2011-04-09 02:59:09 +0000497 assert(T < GroupSize && "Array overflow");
498 TBS[T] = Number;
499 if (++T == GroupSize) {
500 SpillPlacer->addLinks(ArrayRef<unsigned>(TBS, T));
501 T = 0;
502 }
Jakob Stoklund Olesen7b41fbe2011-04-07 17:27:46 +0000503 continue;
Jakob Stoklund Olesen1b400e82011-04-06 21:32:38 +0000504 }
Jakob Stoklund Olesendb529a82011-04-06 03:57:00 +0000505
Jakob Stoklund Olesenf4afdfc2011-04-09 02:59:09 +0000506 assert(B < GroupSize && "Array overflow");
507 BCS[B].Number = Number;
508
Jakob Stoklund Olesen7b41fbe2011-04-07 17:27:46 +0000509 // Interference for the live-in value.
510 if (Intf.first() <= Indexes->getMBBStartIdx(Number))
511 BCS[B].Entry = SpillPlacement::MustSpill;
512 else
513 BCS[B].Entry = SpillPlacement::PrefSpill;
514
515 // Interference for the live-out value.
516 if (Intf.last() >= SA->getLastSplitPoint(Number))
517 BCS[B].Exit = SpillPlacement::MustSpill;
518 else
519 BCS[B].Exit = SpillPlacement::PrefSpill;
520
Jakob Stoklund Olesen1b400e82011-04-06 21:32:38 +0000521 if (++B == GroupSize) {
522 ArrayRef<SpillPlacement::BlockConstraint> Array(BCS, B);
523 SpillPlacer->addConstraints(Array);
524 B = 0;
Jakob Stoklund Olesen1b400e82011-04-06 21:32:38 +0000525 }
Jakob Stoklund Olesendb529a82011-04-06 03:57:00 +0000526 }
527
Jakob Stoklund Olesen1b400e82011-04-06 21:32:38 +0000528 ArrayRef<SpillPlacement::BlockConstraint> Array(BCS, B);
529 SpillPlacer->addConstraints(Array);
Jakob Stoklund Olesenf4afdfc2011-04-09 02:59:09 +0000530 SpillPlacer->addLinks(ArrayRef<unsigned>(TBS, T));
Jakob Stoklund Olesenb5fa9332011-01-18 21:13:27 +0000531}
532
Jakob Stoklund Olesen5db42892011-04-12 21:30:53 +0000533void RAGreedy::growRegion(GlobalSplitCandidate &Cand,
534 InterferenceCache::Cursor Intf) {
535 // Keep track of through blocks that have not been added to SpillPlacer.
536 BitVector Todo = SA->getThroughBlocks();
537 SmallVectorImpl<unsigned> &ActiveBlocks = Cand.ActiveBlocks;
538 unsigned AddedTo = 0;
Jakob Stoklund Olesenf4afdfc2011-04-09 02:59:09 +0000539#ifndef NDEBUG
540 unsigned Visited = 0;
541#endif
Jakob Stoklund Olesen5db42892011-04-12 21:30:53 +0000542
Jakob Stoklund Olesenf4afdfc2011-04-09 02:59:09 +0000543 for (;;) {
544 ArrayRef<unsigned> NewBundles = SpillPlacer->getRecentPositive();
545 if (NewBundles.empty())
546 break;
547 // Find new through blocks in the periphery of PrefRegBundles.
548 for (int i = 0, e = NewBundles.size(); i != e; ++i) {
549 unsigned Bundle = NewBundles[i];
550 // Look at all blocks connected to Bundle in the full graph.
551 ArrayRef<unsigned> Blocks = Bundles->getBlocks(Bundle);
552 for (ArrayRef<unsigned>::iterator I = Blocks.begin(), E = Blocks.end();
553 I != E; ++I) {
554 unsigned Block = *I;
Jakob Stoklund Olesen5db42892011-04-12 21:30:53 +0000555 if (!Todo.test(Block))
Jakob Stoklund Olesenf4afdfc2011-04-09 02:59:09 +0000556 continue;
Jakob Stoklund Olesen5db42892011-04-12 21:30:53 +0000557 Todo.reset(Block);
Jakob Stoklund Olesenf4afdfc2011-04-09 02:59:09 +0000558 // This is a new through block. Add it to SpillPlacer later.
Jakob Stoklund Olesen5db42892011-04-12 21:30:53 +0000559 ActiveBlocks.push_back(Block);
Jakob Stoklund Olesenf4afdfc2011-04-09 02:59:09 +0000560#ifndef NDEBUG
561 ++Visited;
562#endif
563 }
564 }
565 // Any new blocks to add?
Jakob Stoklund Olesen5db42892011-04-12 21:30:53 +0000566 if (ActiveBlocks.size() > AddedTo) {
567 ArrayRef<unsigned> Add(&ActiveBlocks[AddedTo],
568 ActiveBlocks.size() - AddedTo);
569 addThroughConstraints(Intf, Add);
570 AddedTo = ActiveBlocks.size();
Jakob Stoklund Olesenf4afdfc2011-04-09 02:59:09 +0000571 }
572 // Perhaps iterating can enable more bundles?
573 SpillPlacer->iterate();
574 }
Jakob Stoklund Olesenf4afdfc2011-04-09 02:59:09 +0000575 DEBUG(dbgs() << ", v=" << Visited);
576}
Jakob Stoklund Olesen96dcd952011-03-05 01:10:31 +0000577
Jakob Stoklund Olesenb5fa9332011-01-18 21:13:27 +0000578/// calcGlobalSplitCost - Return the global split cost of following the split
579/// pattern in LiveBundles. This cost should be added to the local cost of the
Jakob Stoklund Olesen96dcd952011-03-05 01:10:31 +0000580/// interference pattern in SplitConstraints.
Jakob Stoklund Olesenb5fa9332011-01-18 21:13:27 +0000581///
Jakob Stoklund Olesen5db42892011-04-12 21:30:53 +0000582float RAGreedy::calcGlobalSplitCost(GlobalSplitCandidate &Cand,
583 InterferenceCache::Cursor Intf) {
Jakob Stoklund Olesenb5fa9332011-01-18 21:13:27 +0000584 float GlobalCost = 0;
Jakob Stoklund Olesen5db42892011-04-12 21:30:53 +0000585 const BitVector &LiveBundles = Cand.LiveBundles;
Jakob Stoklund Olesendb529a82011-04-06 03:57:00 +0000586 ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks();
587 for (unsigned i = 0; i != UseBlocks.size(); ++i) {
588 const SplitAnalysis::BlockInfo &BI = UseBlocks[i];
Jakob Stoklund Olesen96dcd952011-03-05 01:10:31 +0000589 SpillPlacement::BlockConstraint &BC = SplitConstraints[i];
Jakob Stoklund Olesen874be742011-03-05 03:28:51 +0000590 bool RegIn = LiveBundles[Bundles->getBundle(BC.Number, 0)];
591 bool RegOut = LiveBundles[Bundles->getBundle(BC.Number, 1)];
592 unsigned Ins = 0;
593
Jakob Stoklund Olesendb529a82011-04-06 03:57:00 +0000594 if (BI.LiveIn)
595 Ins += RegIn != (BC.Entry == SpillPlacement::PrefReg);
596 if (BI.LiveOut)
597 Ins += RegOut != (BC.Exit == SpillPlacement::PrefReg);
Jakob Stoklund Olesen874be742011-03-05 03:28:51 +0000598 if (Ins)
599 GlobalCost += Ins * SpillPlacer->getBlockFrequency(BC.Number);
Jakob Stoklund Olesenb5fa9332011-01-18 21:13:27 +0000600 }
Jakob Stoklund Olesendb529a82011-04-06 03:57:00 +0000601
Jakob Stoklund Olesen5db42892011-04-12 21:30:53 +0000602 for (unsigned i = 0, e = Cand.ActiveBlocks.size(); i != e; ++i) {
603 unsigned Number = Cand.ActiveBlocks[i];
Jakob Stoklund Olesendb529a82011-04-06 03:57:00 +0000604 bool RegIn = LiveBundles[Bundles->getBundle(Number, 0)];
605 bool RegOut = LiveBundles[Bundles->getBundle(Number, 1)];
Jakob Stoklund Olesen9a543522011-04-06 21:32:41 +0000606 if (!RegIn && !RegOut)
607 continue;
608 if (RegIn && RegOut) {
609 // We need double spill code if this block has interference.
610 Intf.moveToBlock(Number);
611 if (Intf.hasInterference())
612 GlobalCost += 2*SpillPlacer->getBlockFrequency(Number);
613 continue;
614 }
615 // live-in / stack-out or stack-in live-out.
616 GlobalCost += SpillPlacer->getBlockFrequency(Number);
Jakob Stoklund Olesendb529a82011-04-06 03:57:00 +0000617 }
Jakob Stoklund Olesenb5fa9332011-01-18 21:13:27 +0000618 return GlobalCost;
619}
620
Jakob Stoklund Olesenccdb3fc2011-01-19 22:11:48 +0000621/// splitAroundRegion - Split VirtReg around the region determined by
622/// LiveBundles. Make an effort to avoid interference from PhysReg.
623///
624/// The 'register' interval is going to contain as many uses as possible while
625/// avoiding interference. The 'stack' interval is the complement constructed by
626/// SplitEditor. It will contain the rest.
627///
Jakob Stoklund Olesen5db42892011-04-12 21:30:53 +0000628void RAGreedy::splitAroundRegion(LiveInterval &VirtReg,
629 GlobalSplitCandidate &Cand,
Jakob Stoklund Olesenccdb3fc2011-01-19 22:11:48 +0000630 SmallVectorImpl<LiveInterval*> &NewVRegs) {
Jakob Stoklund Olesen5db42892011-04-12 21:30:53 +0000631 const BitVector &LiveBundles = Cand.LiveBundles;
632
Jakob Stoklund Olesenccdb3fc2011-01-19 22:11:48 +0000633 DEBUG({
Jakob Stoklund Olesen5db42892011-04-12 21:30:53 +0000634 dbgs() << "Splitting around region for " << PrintReg(Cand.PhysReg, TRI)
Jakob Stoklund Olesenccdb3fc2011-01-19 22:11:48 +0000635 << " with bundles";
636 for (int i = LiveBundles.find_first(); i>=0; i = LiveBundles.find_next(i))
637 dbgs() << " EB#" << i;
638 dbgs() << ".\n";
639 });
640
Jakob Stoklund Olesen5db42892011-04-12 21:30:53 +0000641 InterferenceCache::Cursor Intf(IntfCache, Cand.PhysReg);
Jakob Stoklund Olesen92a55f42011-03-09 00:57:29 +0000642 LiveRangeEdit LREdit(VirtReg, NewVRegs, this);
Jakob Stoklund Olesenbece06f2011-03-03 01:29:13 +0000643 SE->reset(LREdit);
Jakob Stoklund Olesenccdb3fc2011-01-19 22:11:48 +0000644
645 // Create the main cross-block interval.
Jakob Stoklund Olesenfd5c5132011-04-12 19:32:53 +0000646 const unsigned MainIntv = SE->openIntv();
Jakob Stoklund Olesenccdb3fc2011-01-19 22:11:48 +0000647
648 // First add all defs that are live out of a block.
Jakob Stoklund Olesendb529a82011-04-06 03:57:00 +0000649 ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks();
650 for (unsigned i = 0; i != UseBlocks.size(); ++i) {
651 const SplitAnalysis::BlockInfo &BI = UseBlocks[i];
Jakob Stoklund Olesenccdb3fc2011-01-19 22:11:48 +0000652 bool RegIn = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 0)];
653 bool RegOut = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 1)];
654
Jakob Stoklund Olesenfd5c5132011-04-12 19:32:53 +0000655 // Create separate intervals for isolated blocks with multiple uses.
656 if (!RegIn && !RegOut && BI.FirstUse != BI.LastUse) {
657 DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " isolated.\n");
658 SE->splitSingleBlock(BI);
659 SE->selectIntv(MainIntv);
660 continue;
661 }
662
Jakob Stoklund Olesenccdb3fc2011-01-19 22:11:48 +0000663 // Should the register be live out?
664 if (!BI.LiveOut || !RegOut)
665 continue;
666
Jakob Stoklund Olesen6c8afd72011-04-04 15:32:15 +0000667 SlotIndex Start, Stop;
668 tie(Start, Stop) = Indexes->getMBBRange(BI.MBB);
Jakob Stoklund Oleseneda0fe82011-04-02 06:03:38 +0000669 Intf.moveToBlock(BI.MBB->getNumber());
Jakob Stoklund Olesenccdb3fc2011-01-19 22:11:48 +0000670 DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " -> EB#"
Jakob Stoklund Olesen2dfbb3e2011-02-03 20:29:43 +0000671 << Bundles->getBundle(BI.MBB->getNumber(), 1)
Jakob Stoklund Olesen612f7802011-04-05 04:20:29 +0000672 << " [" << Start << ';'
673 << SA->getLastSplitPoint(BI.MBB->getNumber()) << '-' << Stop
674 << ") intf [" << Intf.first() << ';' << Intf.last() << ')');
Jakob Stoklund Olesen2dfbb3e2011-02-03 20:29:43 +0000675
676 // The interference interval should either be invalid or overlap MBB.
Jakob Stoklund Olesen6c8afd72011-04-04 15:32:15 +0000677 assert((!Intf.hasInterference() || Intf.first() < Stop)
Jakob Stoklund Oleseneda0fe82011-04-02 06:03:38 +0000678 && "Bad interference");
Jakob Stoklund Olesen6c8afd72011-04-04 15:32:15 +0000679 assert((!Intf.hasInterference() || Intf.last() > Start)
Jakob Stoklund Olesen36d61862011-03-03 03:41:29 +0000680 && "Bad interference");
Jakob Stoklund Olesenccdb3fc2011-01-19 22:11:48 +0000681
682 // Check interference leaving the block.
Jakob Stoklund Oleseneda0fe82011-04-02 06:03:38 +0000683 if (!Intf.hasInterference()) {
Jakob Stoklund Olesenccdb3fc2011-01-19 22:11:48 +0000684 // Block is interference-free.
685 DEBUG(dbgs() << ", no interference");
Jakob Stoklund Olesenccdb3fc2011-01-19 22:11:48 +0000686 if (!BI.LiveThrough) {
687 DEBUG(dbgs() << ", not live-through.\n");
Jakob Stoklund Olesen6c8afd72011-04-04 15:32:15 +0000688 SE->useIntv(SE->enterIntvBefore(BI.Def), Stop);
Jakob Stoklund Olesenccdb3fc2011-01-19 22:11:48 +0000689 continue;
690 }
691 if (!RegIn) {
692 // Block is live-through, but entry bundle is on the stack.
693 // Reload just before the first use.
694 DEBUG(dbgs() << ", not live-in, enter before first use.\n");
Jakob Stoklund Olesen6c8afd72011-04-04 15:32:15 +0000695 SE->useIntv(SE->enterIntvBefore(BI.FirstUse), Stop);
Jakob Stoklund Olesenccdb3fc2011-01-19 22:11:48 +0000696 continue;
697 }
698 DEBUG(dbgs() << ", live-through.\n");
699 continue;
700 }
701
702 // Block has interference.
Jakob Stoklund Oleseneda0fe82011-04-02 06:03:38 +0000703 DEBUG(dbgs() << ", interference to " << Intf.last());
Jakob Stoklund Olesenfe3f99f2011-02-05 01:06:39 +0000704
Jakob Stoklund Oleseneda0fe82011-04-02 06:03:38 +0000705 if (!BI.LiveThrough && Intf.last() <= BI.Def) {
Jakob Stoklund Olesenfe3f99f2011-02-05 01:06:39 +0000706 // The interference doesn't reach the outgoing segment.
707 DEBUG(dbgs() << " doesn't affect def from " << BI.Def << '\n');
Jakob Stoklund Olesen6c8afd72011-04-04 15:32:15 +0000708 SE->useIntv(BI.Def, Stop);
Jakob Stoklund Olesenfe3f99f2011-02-05 01:06:39 +0000709 continue;
710 }
711
Jakob Stoklund Olesen612f7802011-04-05 04:20:29 +0000712 SlotIndex LastSplitPoint = SA->getLastSplitPoint(BI.MBB->getNumber());
Jakob Stoklund Oleseneda0fe82011-04-02 06:03:38 +0000713 if (Intf.last().getBoundaryIndex() < BI.LastUse) {
Jakob Stoklund Olesenccdb3fc2011-01-19 22:11:48 +0000714 // There are interference-free uses at the end of the block.
715 // Find the first use that can get the live-out register.
Jakob Stoklund Olesenc0de9952011-01-20 17:45:23 +0000716 SmallVectorImpl<SlotIndex>::const_iterator UI =
Jakob Stoklund Olesenfe3f99f2011-02-05 01:06:39 +0000717 std::lower_bound(SA->UseSlots.begin(), SA->UseSlots.end(),
Jakob Stoklund Oleseneda0fe82011-04-02 06:03:38 +0000718 Intf.last().getBoundaryIndex());
Jakob Stoklund Olesenc0de9952011-01-20 17:45:23 +0000719 assert(UI != SA->UseSlots.end() && "Couldn't find last use");
720 SlotIndex Use = *UI;
Jakob Stoklund Olesenc0de9952011-01-20 17:45:23 +0000721 assert(Use <= BI.LastUse && "Couldn't find last use");
Jakob Stoklund Olesen8a2bbde2011-02-08 23:26:48 +0000722 // Only attempt a split befroe the last split point.
Jakob Stoklund Olesen612f7802011-04-05 04:20:29 +0000723 if (Use.getBaseIndex() <= LastSplitPoint) {
Jakob Stoklund Olesen8a2bbde2011-02-08 23:26:48 +0000724 DEBUG(dbgs() << ", free use at " << Use << ".\n");
Jakob Stoklund Olesenbece06f2011-03-03 01:29:13 +0000725 SlotIndex SegStart = SE->enterIntvBefore(Use);
Jakob Stoklund Oleseneda0fe82011-04-02 06:03:38 +0000726 assert(SegStart >= Intf.last() && "Couldn't avoid interference");
Jakob Stoklund Olesen612f7802011-04-05 04:20:29 +0000727 assert(SegStart < LastSplitPoint && "Impossible split point");
Jakob Stoklund Olesen6c8afd72011-04-04 15:32:15 +0000728 SE->useIntv(SegStart, Stop);
Jakob Stoklund Olesen8a2bbde2011-02-08 23:26:48 +0000729 continue;
730 }
Jakob Stoklund Olesenccdb3fc2011-01-19 22:11:48 +0000731 }
732
733 // Interference is after the last use.
734 DEBUG(dbgs() << " after last use.\n");
Jakob Stoklund Olesenbece06f2011-03-03 01:29:13 +0000735 SlotIndex SegStart = SE->enterIntvAtEnd(*BI.MBB);
Jakob Stoklund Oleseneda0fe82011-04-02 06:03:38 +0000736 assert(SegStart >= Intf.last() && "Couldn't avoid interference");
Jakob Stoklund Olesenccdb3fc2011-01-19 22:11:48 +0000737 }
738
739 // Now all defs leading to live bundles are handled, do everything else.
Jakob Stoklund Olesendb529a82011-04-06 03:57:00 +0000740 for (unsigned i = 0; i != UseBlocks.size(); ++i) {
741 const SplitAnalysis::BlockInfo &BI = UseBlocks[i];
Jakob Stoklund Olesenccdb3fc2011-01-19 22:11:48 +0000742 bool RegIn = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 0)];
743 bool RegOut = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 1)];
744
745 // Is the register live-in?
746 if (!BI.LiveIn || !RegIn)
747 continue;
748
749 // We have an incoming register. Check for interference.
Jakob Stoklund Olesen6c8afd72011-04-04 15:32:15 +0000750 SlotIndex Start, Stop;
751 tie(Start, Stop) = Indexes->getMBBRange(BI.MBB);
Jakob Stoklund Oleseneda0fe82011-04-02 06:03:38 +0000752 Intf.moveToBlock(BI.MBB->getNumber());
Jakob Stoklund Olesenccdb3fc2011-01-19 22:11:48 +0000753 DEBUG(dbgs() << "EB#" << Bundles->getBundle(BI.MBB->getNumber(), 0)
Jakob Stoklund Olesen6c8afd72011-04-04 15:32:15 +0000754 << " -> BB#" << BI.MBB->getNumber() << " [" << Start << ';'
Jakob Stoklund Olesen612f7802011-04-05 04:20:29 +0000755 << SA->getLastSplitPoint(BI.MBB->getNumber()) << '-' << Stop
756 << ')');
Jakob Stoklund Olesenccdb3fc2011-01-19 22:11:48 +0000757
758 // Check interference entering the block.
Jakob Stoklund Oleseneda0fe82011-04-02 06:03:38 +0000759 if (!Intf.hasInterference()) {
Jakob Stoklund Olesenccdb3fc2011-01-19 22:11:48 +0000760 // Block is interference-free.
761 DEBUG(dbgs() << ", no interference");
Jakob Stoklund Olesenccdb3fc2011-01-19 22:11:48 +0000762 if (!BI.LiveThrough) {
763 DEBUG(dbgs() << ", killed in block.\n");
Jakob Stoklund Olesen6c8afd72011-04-04 15:32:15 +0000764 SE->useIntv(Start, SE->leaveIntvAfter(BI.Kill));
Jakob Stoklund Olesenccdb3fc2011-01-19 22:11:48 +0000765 continue;
766 }
767 if (!RegOut) {
Jakob Stoklund Olesen612f7802011-04-05 04:20:29 +0000768 SlotIndex LastSplitPoint = SA->getLastSplitPoint(BI.MBB->getNumber());
Jakob Stoklund Olesenccdb3fc2011-01-19 22:11:48 +0000769 // Block is live-through, but exit bundle is on the stack.
770 // Spill immediately after the last use.
Jakob Stoklund Olesen612f7802011-04-05 04:20:29 +0000771 if (BI.LastUse < LastSplitPoint) {
Jakob Stoklund Olesen5c716bd2011-02-08 18:50:21 +0000772 DEBUG(dbgs() << ", uses, stack-out.\n");
Jakob Stoklund Olesen6c8afd72011-04-04 15:32:15 +0000773 SE->useIntv(Start, SE->leaveIntvAfter(BI.LastUse));
Jakob Stoklund Olesen5c716bd2011-02-08 18:50:21 +0000774 continue;
775 }
776 // The last use is after the last split point, it is probably an
777 // indirect jump.
778 DEBUG(dbgs() << ", uses at " << BI.LastUse << " after split point "
Jakob Stoklund Olesen612f7802011-04-05 04:20:29 +0000779 << LastSplitPoint << ", stack-out.\n");
780 SlotIndex SegEnd = SE->leaveIntvBefore(LastSplitPoint);
Jakob Stoklund Olesen6c8afd72011-04-04 15:32:15 +0000781 SE->useIntv(Start, SegEnd);
Jakob Stoklund Olesen5c716bd2011-02-08 18:50:21 +0000782 // Run a double interval from the split to the last use.
783 // This makes it possible to spill the complement without affecting the
784 // indirect branch.
Jakob Stoklund Olesenbece06f2011-03-03 01:29:13 +0000785 SE->overlapIntv(SegEnd, BI.LastUse);
Jakob Stoklund Olesenccdb3fc2011-01-19 22:11:48 +0000786 continue;
787 }
788 // Register is live-through.
789 DEBUG(dbgs() << ", uses, live-through.\n");
Jakob Stoklund Olesen6c8afd72011-04-04 15:32:15 +0000790 SE->useIntv(Start, Stop);
Jakob Stoklund Olesenccdb3fc2011-01-19 22:11:48 +0000791 continue;
792 }
793
794 // Block has interference.
Jakob Stoklund Oleseneda0fe82011-04-02 06:03:38 +0000795 DEBUG(dbgs() << ", interference from " << Intf.first());
Jakob Stoklund Olesenfe3f99f2011-02-05 01:06:39 +0000796
Jakob Stoklund Oleseneda0fe82011-04-02 06:03:38 +0000797 if (!BI.LiveThrough && Intf.first() >= BI.Kill) {
Jakob Stoklund Olesenfe3f99f2011-02-05 01:06:39 +0000798 // The interference doesn't reach the outgoing segment.
799 DEBUG(dbgs() << " doesn't affect kill at " << BI.Kill << '\n');
Jakob Stoklund Olesen6c8afd72011-04-04 15:32:15 +0000800 SE->useIntv(Start, BI.Kill);
Jakob Stoklund Olesenfe3f99f2011-02-05 01:06:39 +0000801 continue;
802 }
803
Jakob Stoklund Oleseneda0fe82011-04-02 06:03:38 +0000804 if (Intf.first().getBaseIndex() > BI.FirstUse) {
Jakob Stoklund Olesenccdb3fc2011-01-19 22:11:48 +0000805 // There are interference-free uses at the beginning of the block.
806 // Find the last use that can get the register.
Jakob Stoklund Olesenc0de9952011-01-20 17:45:23 +0000807 SmallVectorImpl<SlotIndex>::const_iterator UI =
Jakob Stoklund Olesenfe3f99f2011-02-05 01:06:39 +0000808 std::lower_bound(SA->UseSlots.begin(), SA->UseSlots.end(),
Jakob Stoklund Oleseneda0fe82011-04-02 06:03:38 +0000809 Intf.first().getBaseIndex());
Jakob Stoklund Olesenc0de9952011-01-20 17:45:23 +0000810 assert(UI != SA->UseSlots.begin() && "Couldn't find first use");
811 SlotIndex Use = (--UI)->getBoundaryIndex();
812 DEBUG(dbgs() << ", free use at " << *UI << ".\n");
Jakob Stoklund Olesenbece06f2011-03-03 01:29:13 +0000813 SlotIndex SegEnd = SE->leaveIntvAfter(Use);
Jakob Stoklund Oleseneda0fe82011-04-02 06:03:38 +0000814 assert(SegEnd <= Intf.first() && "Couldn't avoid interference");
Jakob Stoklund Olesen6c8afd72011-04-04 15:32:15 +0000815 SE->useIntv(Start, SegEnd);
Jakob Stoklund Olesenccdb3fc2011-01-19 22:11:48 +0000816 continue;
817 }
818
819 // Interference is before the first use.
820 DEBUG(dbgs() << " before first use.\n");
Jakob Stoklund Olesenbece06f2011-03-03 01:29:13 +0000821 SlotIndex SegEnd = SE->leaveIntvAtTop(*BI.MBB);
Jakob Stoklund Oleseneda0fe82011-04-02 06:03:38 +0000822 assert(SegEnd <= Intf.first() && "Couldn't avoid interference");
Jakob Stoklund Olesenccdb3fc2011-01-19 22:11:48 +0000823 }
824
Jakob Stoklund Olesendb529a82011-04-06 03:57:00 +0000825 // Handle live-through blocks.
Jakob Stoklund Olesen5db42892011-04-12 21:30:53 +0000826 for (unsigned i = 0, e = Cand.ActiveBlocks.size(); i != e; ++i) {
827 unsigned Number = Cand.ActiveBlocks[i];
Jakob Stoklund Olesendb529a82011-04-06 03:57:00 +0000828 bool RegIn = LiveBundles[Bundles->getBundle(Number, 0)];
829 bool RegOut = LiveBundles[Bundles->getBundle(Number, 1)];
830 DEBUG(dbgs() << "Live through BB#" << Number << '\n');
831 if (RegIn && RegOut) {
832 Intf.moveToBlock(Number);
833 if (!Intf.hasInterference()) {
834 SE->useIntv(Indexes->getMBBStartIdx(Number),
835 Indexes->getMBBEndIdx(Number));
836 continue;
837 }
838 }
839 MachineBasicBlock *MBB = MF->getBlockNumbered(Number);
840 if (RegIn)
841 SE->leaveIntvAtTop(*MBB);
842 if (RegOut)
843 SE->enterIntvAtEnd(*MBB);
844 }
845
Jakob Stoklund Olesenccdb3fc2011-01-19 22:11:48 +0000846 // FIXME: Should we be more aggressive about splitting the stack region into
847 // per-block segments? The current approach allows the stack region to
848 // separate into connected components. Some components may be allocatable.
Jakob Stoklund Olesenbece06f2011-03-03 01:29:13 +0000849 SE->finish();
Jakob Stoklund Olesen0db841f2011-02-17 22:53:48 +0000850 ++NumGlobalSplits;
Jakob Stoklund Olesenccdb3fc2011-01-19 22:11:48 +0000851
Jakob Stoklund Oleseneb291572011-03-27 22:49:21 +0000852 if (VerifyEnabled)
Jakob Stoklund Olesenccdb3fc2011-01-19 22:11:48 +0000853 MF->verify(this, "After splitting live range around region");
854}
855
Jakob Stoklund Olesenb5fa9332011-01-18 21:13:27 +0000856unsigned RAGreedy::tryRegionSplit(LiveInterval &VirtReg, AllocationOrder &Order,
857 SmallVectorImpl<LiveInterval*> &NewVRegs) {
Jakob Stoklund Olesenb5fa9332011-01-18 21:13:27 +0000858 float BestCost = 0;
Jakob Stoklund Olesen5db42892011-04-12 21:30:53 +0000859 const unsigned NoCand = ~0u;
860 unsigned BestCand = NoCand;
Jakob Stoklund Olesen96dcd952011-03-05 01:10:31 +0000861
Jakob Stoklund Olesenb5fa9332011-01-18 21:13:27 +0000862 Order.rewind();
Jakob Stoklund Olesen96dcd952011-03-05 01:10:31 +0000863 for (unsigned Cand = 0; unsigned PhysReg = Order.next(); ++Cand) {
864 if (GlobalCand.size() <= Cand)
865 GlobalCand.resize(Cand+1);
Jakob Stoklund Olesen5db42892011-04-12 21:30:53 +0000866 GlobalCand[Cand].reset(PhysReg);
Jakob Stoklund Olesen96dcd952011-03-05 01:10:31 +0000867
Jakob Stoklund Olesen5db42892011-04-12 21:30:53 +0000868 SpillPlacer->prepare(GlobalCand[Cand].LiveBundles);
Jakob Stoklund Olesen1b400e82011-04-06 21:32:38 +0000869 float Cost;
Jakob Stoklund Olesenf4afdfc2011-04-09 02:59:09 +0000870 InterferenceCache::Cursor Intf(IntfCache, PhysReg);
871 if (!addSplitConstraints(Intf, Cost)) {
872 DEBUG(dbgs() << PrintReg(PhysReg, TRI) << "\tno positive bundles\n");
Jakob Stoklund Olesen1b400e82011-04-06 21:32:38 +0000873 continue;
874 }
Jakob Stoklund Olesenf4afdfc2011-04-09 02:59:09 +0000875 DEBUG(dbgs() << PrintReg(PhysReg, TRI) << "\tstatic = " << Cost);
Jakob Stoklund Olesen5db42892011-04-12 21:30:53 +0000876 if (BestCand != NoCand && Cost >= BestCost) {
877 DEBUG(dbgs() << " worse than "
878 << PrintReg(GlobalCand[BestCand].PhysReg, TRI) << '\n');
Jakob Stoklund Olesenb5fa9332011-01-18 21:13:27 +0000879 continue;
Jakob Stoklund Olesen874be742011-03-05 03:28:51 +0000880 }
Jakob Stoklund Olesen5db42892011-04-12 21:30:53 +0000881 growRegion(GlobalCand[Cand], Intf);
Jakob Stoklund Olesenccdb3fc2011-01-19 22:11:48 +0000882
Jakob Stoklund Olesen9efa2a22011-04-06 19:13:57 +0000883 SpillPlacer->finish();
884
Jakob Stoklund Olesenccdb3fc2011-01-19 22:11:48 +0000885 // No live bundles, defer to splitSingleBlocks().
Jakob Stoklund Olesen5db42892011-04-12 21:30:53 +0000886 if (!GlobalCand[Cand].LiveBundles.any()) {
Jakob Stoklund Olesen874be742011-03-05 03:28:51 +0000887 DEBUG(dbgs() << " no bundles.\n");
Jakob Stoklund Olesenccdb3fc2011-01-19 22:11:48 +0000888 continue;
Jakob Stoklund Olesen874be742011-03-05 03:28:51 +0000889 }
Jakob Stoklund Olesenccdb3fc2011-01-19 22:11:48 +0000890
Jakob Stoklund Olesen5db42892011-04-12 21:30:53 +0000891 Cost += calcGlobalSplitCost(GlobalCand[Cand], Intf);
Jakob Stoklund Olesen874be742011-03-05 03:28:51 +0000892 DEBUG({
893 dbgs() << ", total = " << Cost << " with bundles";
Jakob Stoklund Olesen5db42892011-04-12 21:30:53 +0000894 for (int i = GlobalCand[Cand].LiveBundles.find_first(); i>=0;
895 i = GlobalCand[Cand].LiveBundles.find_next(i))
Jakob Stoklund Olesen874be742011-03-05 03:28:51 +0000896 dbgs() << " EB#" << i;
897 dbgs() << ".\n";
898 });
Jakob Stoklund Olesen5db42892011-04-12 21:30:53 +0000899 if (BestCand == NoCand || Cost < BestCost) {
900 BestCand = Cand;
Jakob Stoklund Olesen874be742011-03-05 03:28:51 +0000901 BestCost = 0.98f * Cost; // Prevent rounding effects.
Jakob Stoklund Olesenb5fa9332011-01-18 21:13:27 +0000902 }
903 }
Jakob Stoklund Olesenccdb3fc2011-01-19 22:11:48 +0000904
Jakob Stoklund Olesen5db42892011-04-12 21:30:53 +0000905 if (BestCand == NoCand)
Jakob Stoklund Olesenccdb3fc2011-01-19 22:11:48 +0000906 return 0;
907
Jakob Stoklund Olesen5db42892011-04-12 21:30:53 +0000908 splitAroundRegion(VirtReg, GlobalCand[BestCand], NewVRegs);
Jakob Stoklund Olesenfd5c5132011-04-12 19:32:53 +0000909 setStage(NewVRegs.begin(), NewVRegs.end(), RS_Global);
Jakob Stoklund Olesenb5fa9332011-01-18 21:13:27 +0000910 return 0;
911}
912
Jakob Stoklund Olesenccdb3fc2011-01-19 22:11:48 +0000913
914//===----------------------------------------------------------------------===//
Jakob Stoklund Olesen034a80d2011-02-17 19:13:53 +0000915// Local Splitting
916//===----------------------------------------------------------------------===//
917
918
919/// calcGapWeights - Compute the maximum spill weight that needs to be evicted
920/// in order to use PhysReg between two entries in SA->UseSlots.
921///
922/// GapWeight[i] represents the gap between UseSlots[i] and UseSlots[i+1].
923///
924void RAGreedy::calcGapWeights(unsigned PhysReg,
925 SmallVectorImpl<float> &GapWeight) {
Jakob Stoklund Olesendb529a82011-04-06 03:57:00 +0000926 assert(SA->getUseBlocks().size() == 1 && "Not a local interval");
927 const SplitAnalysis::BlockInfo &BI = SA->getUseBlocks().front();
Jakob Stoklund Olesen034a80d2011-02-17 19:13:53 +0000928 const SmallVectorImpl<SlotIndex> &Uses = SA->UseSlots;
929 const unsigned NumGaps = Uses.size()-1;
930
931 // Start and end points for the interference check.
932 SlotIndex StartIdx = BI.LiveIn ? BI.FirstUse.getBaseIndex() : BI.FirstUse;
933 SlotIndex StopIdx = BI.LiveOut ? BI.LastUse.getBoundaryIndex() : BI.LastUse;
934
935 GapWeight.assign(NumGaps, 0.0f);
936
937 // Add interference from each overlapping register.
938 for (const unsigned *AI = TRI->getOverlaps(PhysReg); *AI; ++AI) {
939 if (!query(const_cast<LiveInterval&>(SA->getParent()), *AI)
940 .checkInterference())
941 continue;
942
943 // We know that VirtReg is a continuous interval from FirstUse to LastUse,
944 // so we don't need InterferenceQuery.
945 //
946 // Interference that overlaps an instruction is counted in both gaps
947 // surrounding the instruction. The exception is interference before
948 // StartIdx and after StopIdx.
949 //
950 LiveIntervalUnion::SegmentIter IntI = PhysReg2LiveUnion[*AI].find(StartIdx);
951 for (unsigned Gap = 0; IntI.valid() && IntI.start() < StopIdx; ++IntI) {
952 // Skip the gaps before IntI.
953 while (Uses[Gap+1].getBoundaryIndex() < IntI.start())
954 if (++Gap == NumGaps)
955 break;
956 if (Gap == NumGaps)
957 break;
958
959 // Update the gaps covered by IntI.
960 const float weight = IntI.value()->weight;
961 for (; Gap != NumGaps; ++Gap) {
962 GapWeight[Gap] = std::max(GapWeight[Gap], weight);
963 if (Uses[Gap+1].getBaseIndex() >= IntI.stop())
964 break;
965 }
966 if (Gap == NumGaps)
967 break;
968 }
969 }
970}
971
972/// getPrevMappedIndex - Return the slot index of the last non-copy instruction
973/// before MI that has a slot index. If MI is the first mapped instruction in
974/// its block, return the block start index instead.
975///
976SlotIndex RAGreedy::getPrevMappedIndex(const MachineInstr *MI) {
977 assert(MI && "Missing MachineInstr");
978 const MachineBasicBlock *MBB = MI->getParent();
979 MachineBasicBlock::const_iterator B = MBB->begin(), I = MI;
980 while (I != B)
981 if (!(--I)->isDebugValue() && !I->isCopy())
982 return Indexes->getInstructionIndex(I);
983 return Indexes->getMBBStartIdx(MBB);
984}
985
986/// calcPrevSlots - Fill in the PrevSlot array with the index of the previous
987/// real non-copy instruction for each instruction in SA->UseSlots.
988///
989void RAGreedy::calcPrevSlots() {
990 const SmallVectorImpl<SlotIndex> &Uses = SA->UseSlots;
991 PrevSlot.clear();
992 PrevSlot.reserve(Uses.size());
993 for (unsigned i = 0, e = Uses.size(); i != e; ++i) {
994 const MachineInstr *MI = Indexes->getInstructionFromIndex(Uses[i]);
995 PrevSlot.push_back(getPrevMappedIndex(MI).getDefIndex());
996 }
997}
998
999/// nextSplitPoint - Find the next index into SA->UseSlots > i such that it may
1000/// be beneficial to split before UseSlots[i].
1001///
1002/// 0 is always a valid split point
1003unsigned RAGreedy::nextSplitPoint(unsigned i) {
1004 const SmallVectorImpl<SlotIndex> &Uses = SA->UseSlots;
1005 const unsigned Size = Uses.size();
1006 assert(i != Size && "No split points after the end");
1007 // Allow split before i when Uses[i] is not adjacent to the previous use.
1008 while (++i != Size && PrevSlot[i].getBaseIndex() <= Uses[i-1].getBaseIndex())
1009 ;
1010 return i;
1011}
1012
1013/// tryLocalSplit - Try to split VirtReg into smaller intervals inside its only
1014/// basic block.
1015///
1016unsigned RAGreedy::tryLocalSplit(LiveInterval &VirtReg, AllocationOrder &Order,
1017 SmallVectorImpl<LiveInterval*> &NewVRegs) {
Jakob Stoklund Olesendb529a82011-04-06 03:57:00 +00001018 assert(SA->getUseBlocks().size() == 1 && "Not a local interval");
1019 const SplitAnalysis::BlockInfo &BI = SA->getUseBlocks().front();
Jakob Stoklund Olesen034a80d2011-02-17 19:13:53 +00001020
1021 // Note that it is possible to have an interval that is live-in or live-out
1022 // while only covering a single block - A phi-def can use undef values from
1023 // predecessors, and the block could be a single-block loop.
1024 // We don't bother doing anything clever about such a case, we simply assume
1025 // that the interval is continuous from FirstUse to LastUse. We should make
1026 // sure that we don't do anything illegal to such an interval, though.
1027
1028 const SmallVectorImpl<SlotIndex> &Uses = SA->UseSlots;
1029 if (Uses.size() <= 2)
1030 return 0;
1031 const unsigned NumGaps = Uses.size()-1;
1032
1033 DEBUG({
1034 dbgs() << "tryLocalSplit: ";
1035 for (unsigned i = 0, e = Uses.size(); i != e; ++i)
1036 dbgs() << ' ' << SA->UseSlots[i];
1037 dbgs() << '\n';
1038 });
1039
1040 // For every use, find the previous mapped non-copy instruction.
1041 // We use this to detect valid split points, and to estimate new interval
1042 // sizes.
1043 calcPrevSlots();
1044
1045 unsigned BestBefore = NumGaps;
1046 unsigned BestAfter = 0;
1047 float BestDiff = 0;
1048
Jakob Stoklund Olesen40a42a22011-03-04 00:58:40 +00001049 const float blockFreq = SpillPlacer->getBlockFrequency(BI.MBB->getNumber());
Jakob Stoklund Olesen034a80d2011-02-17 19:13:53 +00001050 SmallVector<float, 8> GapWeight;
1051
1052 Order.rewind();
1053 while (unsigned PhysReg = Order.next()) {
1054 // Keep track of the largest spill weight that would need to be evicted in
1055 // order to make use of PhysReg between UseSlots[i] and UseSlots[i+1].
1056 calcGapWeights(PhysReg, GapWeight);
1057
1058 // Try to find the best sequence of gaps to close.
1059 // The new spill weight must be larger than any gap interference.
1060
1061 // We will split before Uses[SplitBefore] and after Uses[SplitAfter].
1062 unsigned SplitBefore = 0, SplitAfter = nextSplitPoint(1) - 1;
1063
1064 // MaxGap should always be max(GapWeight[SplitBefore..SplitAfter-1]).
1065 // It is the spill weight that needs to be evicted.
1066 float MaxGap = GapWeight[0];
1067 for (unsigned i = 1; i != SplitAfter; ++i)
1068 MaxGap = std::max(MaxGap, GapWeight[i]);
1069
1070 for (;;) {
1071 // Live before/after split?
1072 const bool LiveBefore = SplitBefore != 0 || BI.LiveIn;
1073 const bool LiveAfter = SplitAfter != NumGaps || BI.LiveOut;
1074
1075 DEBUG(dbgs() << PrintReg(PhysReg, TRI) << ' '
1076 << Uses[SplitBefore] << '-' << Uses[SplitAfter]
1077 << " i=" << MaxGap);
1078
1079 // Stop before the interval gets so big we wouldn't be making progress.
1080 if (!LiveBefore && !LiveAfter) {
1081 DEBUG(dbgs() << " all\n");
1082 break;
1083 }
1084 // Should the interval be extended or shrunk?
1085 bool Shrink = true;
1086 if (MaxGap < HUGE_VALF) {
1087 // Estimate the new spill weight.
1088 //
1089 // Each instruction reads and writes the register, except the first
1090 // instr doesn't read when !FirstLive, and the last instr doesn't write
1091 // when !LastLive.
1092 //
1093 // We will be inserting copies before and after, so the total number of
1094 // reads and writes is 2 * EstUses.
1095 //
1096 const unsigned EstUses = 2*(SplitAfter - SplitBefore) +
1097 2*(LiveBefore + LiveAfter);
1098
1099 // Try to guess the size of the new interval. This should be trivial,
1100 // but the slot index of an inserted copy can be a lot smaller than the
1101 // instruction it is inserted before if there are many dead indexes
1102 // between them.
1103 //
1104 // We measure the distance from the instruction before SplitBefore to
1105 // get a conservative estimate.
1106 //
1107 // The final distance can still be different if inserting copies
1108 // triggers a slot index renumbering.
1109 //
1110 const float EstWeight = normalizeSpillWeight(blockFreq * EstUses,
1111 PrevSlot[SplitBefore].distance(Uses[SplitAfter]));
1112 // Would this split be possible to allocate?
1113 // Never allocate all gaps, we wouldn't be making progress.
1114 float Diff = EstWeight - MaxGap;
1115 DEBUG(dbgs() << " w=" << EstWeight << " d=" << Diff);
1116 if (Diff > 0) {
1117 Shrink = false;
1118 if (Diff > BestDiff) {
1119 DEBUG(dbgs() << " (best)");
1120 BestDiff = Diff;
1121 BestBefore = SplitBefore;
1122 BestAfter = SplitAfter;
1123 }
1124 }
1125 }
1126
1127 // Try to shrink.
1128 if (Shrink) {
1129 SplitBefore = nextSplitPoint(SplitBefore);
1130 if (SplitBefore < SplitAfter) {
1131 DEBUG(dbgs() << " shrink\n");
1132 // Recompute the max when necessary.
1133 if (GapWeight[SplitBefore - 1] >= MaxGap) {
1134 MaxGap = GapWeight[SplitBefore];
1135 for (unsigned i = SplitBefore + 1; i != SplitAfter; ++i)
1136 MaxGap = std::max(MaxGap, GapWeight[i]);
1137 }
1138 continue;
1139 }
1140 MaxGap = 0;
1141 }
1142
1143 // Try to extend the interval.
1144 if (SplitAfter >= NumGaps) {
1145 DEBUG(dbgs() << " end\n");
1146 break;
1147 }
1148
1149 DEBUG(dbgs() << " extend\n");
1150 for (unsigned e = nextSplitPoint(SplitAfter + 1) - 1;
1151 SplitAfter != e; ++SplitAfter)
1152 MaxGap = std::max(MaxGap, GapWeight[SplitAfter]);
1153 continue;
1154 }
1155 }
1156
1157 // Didn't find any candidates?
1158 if (BestBefore == NumGaps)
1159 return 0;
1160
1161 DEBUG(dbgs() << "Best local split range: " << Uses[BestBefore]
1162 << '-' << Uses[BestAfter] << ", " << BestDiff
1163 << ", " << (BestAfter - BestBefore + 1) << " instrs\n");
1164
Jakob Stoklund Olesen92a55f42011-03-09 00:57:29 +00001165 LiveRangeEdit LREdit(VirtReg, NewVRegs, this);
Jakob Stoklund Olesenbece06f2011-03-03 01:29:13 +00001166 SE->reset(LREdit);
Jakob Stoklund Olesen034a80d2011-02-17 19:13:53 +00001167
Jakob Stoklund Olesenbece06f2011-03-03 01:29:13 +00001168 SE->openIntv();
1169 SlotIndex SegStart = SE->enterIntvBefore(Uses[BestBefore]);
1170 SlotIndex SegStop = SE->leaveIntvAfter(Uses[BestAfter]);
1171 SE->useIntv(SegStart, SegStop);
Jakob Stoklund Olesenbece06f2011-03-03 01:29:13 +00001172 SE->finish();
Jakob Stoklund Olesen22a1df62011-03-01 21:10:07 +00001173 setStage(NewVRegs.begin(), NewVRegs.end(), RS_Local);
Jakob Stoklund Olesen0db841f2011-02-17 22:53:48 +00001174 ++NumLocalSplits;
Jakob Stoklund Olesen034a80d2011-02-17 19:13:53 +00001175
1176 return 0;
1177}
1178
1179//===----------------------------------------------------------------------===//
Jakob Stoklund Olesenccdb3fc2011-01-19 22:11:48 +00001180// Live Range Splitting
1181//===----------------------------------------------------------------------===//
1182
1183/// trySplit - Try to split VirtReg or one of its interferences, making it
1184/// assignable.
1185/// @return Physreg when VirtReg may be assigned and/or new NewVRegs.
1186unsigned RAGreedy::trySplit(LiveInterval &VirtReg, AllocationOrder &Order,
1187 SmallVectorImpl<LiveInterval*>&NewVRegs) {
Jakob Stoklund Olesen034a80d2011-02-17 19:13:53 +00001188 // Local intervals are handled separately.
Jakob Stoklund Olesena2ebf602011-02-19 00:38:40 +00001189 if (LIS->intervalIsInOneMBB(VirtReg)) {
1190 NamedRegionTimer T("Local Splitting", TimerGroupName, TimePassesIsEnabled);
Jakob Stoklund Olesen22a1df62011-03-01 21:10:07 +00001191 SA->analyze(&VirtReg);
Jakob Stoklund Olesen034a80d2011-02-17 19:13:53 +00001192 return tryLocalSplit(VirtReg, Order, NewVRegs);
Jakob Stoklund Olesena2ebf602011-02-19 00:38:40 +00001193 }
1194
1195 NamedRegionTimer T("Global Splitting", TimerGroupName, TimePassesIsEnabled);
Jakob Stoklund Olesenccdb3fc2011-01-19 22:11:48 +00001196
Jakob Stoklund Olesen22a1df62011-03-01 21:10:07 +00001197 // Don't iterate global splitting.
1198 // Move straight to spilling if this range was produced by a global split.
Jakob Stoklund Olesenfd5c5132011-04-12 19:32:53 +00001199 if (getStage(VirtReg) >= RS_Global)
Jakob Stoklund Olesen22a1df62011-03-01 21:10:07 +00001200 return 0;
1201
1202 SA->analyze(&VirtReg);
1203
Jakob Stoklund Olesenccdb3fc2011-01-19 22:11:48 +00001204 // First try to split around a region spanning multiple blocks.
Jakob Stoklund Olesenfd5c5132011-04-12 19:32:53 +00001205 unsigned PhysReg = tryRegionSplit(VirtReg, Order, NewVRegs);
1206 if (PhysReg || !NewVRegs.empty())
1207 return PhysReg;
Jakob Stoklund Olesenccdb3fc2011-01-19 22:11:48 +00001208
1209 // Then isolate blocks with multiple uses.
Jakob Stoklund Olesenfd5c5132011-04-12 19:32:53 +00001210 SplitAnalysis::BlockPtrSet Blocks;
1211 if (SA->getMultiUseBlocks(Blocks)) {
1212 LiveRangeEdit LREdit(VirtReg, NewVRegs, this);
1213 SE->reset(LREdit);
1214 SE->splitSingleBlocks(Blocks);
1215 setStage(NewVRegs.begin(), NewVRegs.end(), RS_Global);
1216 if (VerifyEnabled)
1217 MF->verify(this, "After splitting live range around basic blocks");
Jakob Stoklund Olesenccdb3fc2011-01-19 22:11:48 +00001218 }
1219
1220 // Don't assign any physregs.
1221 return 0;
1222}
1223
1224
Jakob Stoklund Olesenb5fa9332011-01-18 21:13:27 +00001225//===----------------------------------------------------------------------===//
Jakob Stoklund Olesen770d42d2010-12-22 22:01:30 +00001226// Main Entry Point
1227//===----------------------------------------------------------------------===//
1228
1229unsigned RAGreedy::selectOrSplit(LiveInterval &VirtReg,
Jakob Stoklund Olesenccdb3fc2011-01-19 22:11:48 +00001230 SmallVectorImpl<LiveInterval*> &NewVRegs) {
Jakob Stoklund Olesen770d42d2010-12-22 22:01:30 +00001231 // First try assigning a free register.
Jakob Stoklund Olesendd479e92010-12-10 22:21:05 +00001232 AllocationOrder Order(VirtReg.reg, *VRM, ReservedRegs);
1233 while (unsigned PhysReg = Order.next()) {
Jakob Stoklund Olesen770d42d2010-12-22 22:01:30 +00001234 if (!checkPhysRegInterference(VirtReg, PhysReg))
Jakob Stoklund Olesencba2e062010-12-08 03:26:16 +00001235 return PhysReg;
Jakob Stoklund Olesencba2e062010-12-08 03:26:16 +00001236 }
Andrew Trickb853e6c2010-12-09 18:15:21 +00001237
Jakob Stoklund Olesen98c81412011-02-23 00:29:52 +00001238 if (unsigned PhysReg = tryEvict(VirtReg, Order, NewVRegs))
Jakob Stoklund Olesen46c83c82010-12-14 00:37:49 +00001239 return PhysReg;
Andrew Trickb853e6c2010-12-09 18:15:21 +00001240
Jakob Stoklund Olesenccdb3fc2011-01-19 22:11:48 +00001241 assert(NewVRegs.empty() && "Cannot append to existing NewVRegs");
1242
Jakob Stoklund Olesen107d3662011-02-24 23:21:36 +00001243 // The first time we see a live range, don't try to split or spill.
1244 // Wait until the second time, when all smaller ranges have been allocated.
1245 // This gives a better picture of the interference to split around.
Jakob Stoklund Oleseneb291572011-03-27 22:49:21 +00001246 LiveRangeStage Stage = getStage(VirtReg);
Jakob Stoklund Olesenf22ca3f2011-03-30 02:52:39 +00001247 if (Stage == RS_First) {
Jakob Stoklund Oleseneb291572011-03-27 22:49:21 +00001248 LRStage[VirtReg.reg] = RS_Second;
Jakob Stoklund Olesenc1655e12011-03-19 23:02:47 +00001249 DEBUG(dbgs() << "wait for second round\n");
Jakob Stoklund Olesen107d3662011-02-24 23:21:36 +00001250 NewVRegs.push_back(&VirtReg);
1251 return 0;
1252 }
1253
Jakob Stoklund Olesen22a1df62011-03-01 21:10:07 +00001254 assert(Stage < RS_Spill && "Cannot allocate after spilling");
1255
Jakob Stoklund Olesen46c83c82010-12-14 00:37:49 +00001256 // Try splitting VirtReg or interferences.
Jakob Stoklund Olesenccdb3fc2011-01-19 22:11:48 +00001257 unsigned PhysReg = trySplit(VirtReg, Order, NewVRegs);
1258 if (PhysReg || !NewVRegs.empty())
Jakob Stoklund Olesenb64d92e2010-12-14 00:37:44 +00001259 return PhysReg;
1260
Jakob Stoklund Olesen770d42d2010-12-22 22:01:30 +00001261 // Finally spill VirtReg itself.
Jakob Stoklund Olesen533f58e2010-12-11 00:19:56 +00001262 NamedRegionTimer T("Spiller", TimerGroupName, TimePassesIsEnabled);
Jakob Stoklund Olesen47dbf6c2011-03-10 01:51:42 +00001263 LiveRangeEdit LRE(VirtReg, NewVRegs, this);
1264 spiller().spill(LRE);
Jakob Stoklund Olesen6094bd82011-03-29 21:20:19 +00001265 setStage(NewVRegs.begin(), NewVRegs.end(), RS_Spill);
Jakob Stoklund Olesencba2e062010-12-08 03:26:16 +00001266
Jakob Stoklund Olesenc46570d2011-03-16 22:56:08 +00001267 if (VerifyEnabled)
1268 MF->verify(this, "After spilling");
1269
Jakob Stoklund Olesencba2e062010-12-08 03:26:16 +00001270 // The live virtual register requesting allocation was spilled, so tell
1271 // the caller not to allocate anything during this round.
1272 return 0;
1273}
1274
1275bool RAGreedy::runOnMachineFunction(MachineFunction &mf) {
1276 DEBUG(dbgs() << "********** GREEDY REGISTER ALLOCATION **********\n"
1277 << "********** Function: "
1278 << ((Value*)mf.getFunction())->getName() << '\n');
1279
1280 MF = &mf;
Jakob Stoklund Olesenaf249642010-12-17 23:16:35 +00001281 if (VerifyEnabled)
Jakob Stoklund Olesen89cab932010-12-18 00:06:56 +00001282 MF->verify(this, "Before greedy register allocator");
Jakob Stoklund Olesenaf249642010-12-17 23:16:35 +00001283
Jakob Stoklund Olesen4680dec2010-12-10 23:49:00 +00001284 RegAllocBase::init(getAnalysis<VirtRegMap>(), getAnalysis<LiveIntervals>());
Jakob Stoklund Olesenb5fa9332011-01-18 21:13:27 +00001285 Indexes = &getAnalysis<SlotIndexes>();
Jakob Stoklund Olesenf428eb62010-12-17 23:16:32 +00001286 DomTree = &getAnalysis<MachineDominatorTree>();
Jakob Stoklund Olesencba2e062010-12-08 03:26:16 +00001287 ReservedRegs = TRI->getReservedRegs(*MF);
Jakob Stoklund Olesenf6dff842010-12-10 22:54:44 +00001288 SpillerInstance.reset(createInlineSpiller(*this, *MF, *VRM));
Jakob Stoklund Olesend0bb5e22010-12-15 23:46:13 +00001289 Loops = &getAnalysis<MachineLoopInfo>();
1290 LoopRanges = &getAnalysis<MachineLoopRanges>();
Jakob Stoklund Olesenb5fa9332011-01-18 21:13:27 +00001291 Bundles = &getAnalysis<EdgeBundles>();
1292 SpillPlacer = &getAnalysis<SpillPlacement>();
1293
Jakob Stoklund Olesen1b847de2011-02-19 00:53:42 +00001294 SA.reset(new SplitAnalysis(*VRM, *LIS, *Loops));
Jakob Stoklund Olesenbece06f2011-03-03 01:29:13 +00001295 SE.reset(new SplitEditor(*SA, *LIS, *VRM, *DomTree));
Jakob Stoklund Olesen22a1df62011-03-01 21:10:07 +00001296 LRStage.clear();
1297 LRStage.resize(MRI->getNumVirtRegs());
Jakob Stoklund Oleseneda0fe82011-04-02 06:03:38 +00001298 IntfCache.init(MF, &PhysReg2LiveUnion[0], Indexes, TRI);
Jakob Stoklund Olesend0bb5e22010-12-15 23:46:13 +00001299
Jakob Stoklund Olesencba2e062010-12-08 03:26:16 +00001300 allocatePhysRegs();
1301 addMBBLiveIns(MF);
Jakob Stoklund Olesen8a61da82011-02-08 21:13:03 +00001302 LIS->addKillFlags();
Jakob Stoklund Olesencba2e062010-12-08 03:26:16 +00001303
1304 // Run rewriter
Jakob Stoklund Olesen533f58e2010-12-11 00:19:56 +00001305 {
1306 NamedRegionTimer T("Rewriter", TimerGroupName, TimePassesIsEnabled);
Jakob Stoklund Olesenba05c012011-02-18 22:03:18 +00001307 VRM->rewrite(Indexes);
Jakob Stoklund Olesen533f58e2010-12-11 00:19:56 +00001308 }
Jakob Stoklund Olesencba2e062010-12-08 03:26:16 +00001309
Jakob Stoklund Olesencfafc542011-04-05 21:40:37 +00001310 // Write out new DBG_VALUE instructions.
1311 getAnalysis<LiveDebugVariables>().emitDebugValues(VRM);
1312
Jakob Stoklund Olesencba2e062010-12-08 03:26:16 +00001313 // The pass output is in VirtRegMap. Release all the transient data.
1314 releaseMemory();
1315
1316 return true;
1317}