Deleted Added
sdiff udiff text old ( 223017 ) new ( 224145 )
full compact
RegAllocGreedy.cpp (223017) RegAllocGreedy.cpp (224145)
1//===-- 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//===----------------------------------------------------------------------===//

--- 8 unchanged lines hidden (view full) ---

17#include "InterferenceCache.h"
18#include "LiveDebugVariables.h"
19#include "LiveRangeEdit.h"
20#include "RegAllocBase.h"
21#include "Spiller.h"
22#include "SpillPlacement.h"
23#include "SplitKit.h"
24#include "VirtRegMap.h"
1//===-- 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//===----------------------------------------------------------------------===//

--- 8 unchanged lines hidden (view full) ---

17#include "InterferenceCache.h"
18#include "LiveDebugVariables.h"
19#include "LiveRangeEdit.h"
20#include "RegAllocBase.h"
21#include "Spiller.h"
22#include "SpillPlacement.h"
23#include "SplitKit.h"
24#include "VirtRegMap.h"
25#include "RegisterCoalescer.h"
25#include "llvm/ADT/Statistic.h"
26#include "llvm/Analysis/AliasAnalysis.h"
27#include "llvm/Function.h"
28#include "llvm/PassAnalysisSupport.h"
29#include "llvm/CodeGen/CalcSpillWeights.h"
30#include "llvm/CodeGen/EdgeBundles.h"
31#include "llvm/CodeGen/LiveIntervalAnalysis.h"
32#include "llvm/CodeGen/LiveStackAnalysis.h"
33#include "llvm/CodeGen/MachineDominators.h"
34#include "llvm/CodeGen/MachineFunctionPass.h"
35#include "llvm/CodeGen/MachineLoopInfo.h"
26#include "llvm/ADT/Statistic.h"
27#include "llvm/Analysis/AliasAnalysis.h"
28#include "llvm/Function.h"
29#include "llvm/PassAnalysisSupport.h"
30#include "llvm/CodeGen/CalcSpillWeights.h"
31#include "llvm/CodeGen/EdgeBundles.h"
32#include "llvm/CodeGen/LiveIntervalAnalysis.h"
33#include "llvm/CodeGen/LiveStackAnalysis.h"
34#include "llvm/CodeGen/MachineDominators.h"
35#include "llvm/CodeGen/MachineFunctionPass.h"
36#include "llvm/CodeGen/MachineLoopInfo.h"
36#include "llvm/CodeGen/MachineLoopRanges.h"
37#include "llvm/CodeGen/MachineRegisterInfo.h"
38#include "llvm/CodeGen/Passes.h"
39#include "llvm/CodeGen/RegAllocRegistry.h"
37#include "llvm/CodeGen/MachineRegisterInfo.h"
38#include "llvm/CodeGen/Passes.h"
39#include "llvm/CodeGen/RegAllocRegistry.h"
40#include "llvm/CodeGen/RegisterCoalescer.h"
41#include "llvm/Target/TargetOptions.h"
42#include "llvm/Support/Debug.h"
43#include "llvm/Support/ErrorHandling.h"
44#include "llvm/Support/raw_ostream.h"
45#include "llvm/Support/Timer.h"
46
47#include <queue>
48

--- 14 unchanged lines hidden (view full) ---

63 // context
64 MachineFunction *MF;
65
66 // analyses
67 SlotIndexes *Indexes;
68 LiveStacks *LS;
69 MachineDominatorTree *DomTree;
70 MachineLoopInfo *Loops;
40#include "llvm/Target/TargetOptions.h"
41#include "llvm/Support/Debug.h"
42#include "llvm/Support/ErrorHandling.h"
43#include "llvm/Support/raw_ostream.h"
44#include "llvm/Support/Timer.h"
45
46#include <queue>
47

--- 14 unchanged lines hidden (view full) ---

62 // context
63 MachineFunction *MF;
64
65 // analyses
66 SlotIndexes *Indexes;
67 LiveStacks *LS;
68 MachineDominatorTree *DomTree;
69 MachineLoopInfo *Loops;
71 MachineLoopRanges *LoopRanges;
72 EdgeBundles *Bundles;
73 SpillPlacement *SpillPlacer;
74 LiveDebugVariables *DebugVars;
75
76 // state
77 std::auto_ptr<Spiller> SpillerInstance;
78 std::priority_queue<std::pair<unsigned, unsigned> > Queue;
70 EdgeBundles *Bundles;
71 SpillPlacement *SpillPlacer;
72 LiveDebugVariables *DebugVars;
73
74 // state
75 std::auto_ptr<Spiller> SpillerInstance;
76 std::priority_queue<std::pair<unsigned, unsigned> > Queue;
77 unsigned NextCascade;
79
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.

--- 9 unchanged lines hidden (view full) ---

96 RS_Second, ///< Second time in the queue.
97 RS_Global, ///< Produced by global splitting.
98 RS_Local, ///< Produced by local splitting.
99 RS_Spill ///< Produced by spilling.
100 };
101
102 static const char *const StageName[];
103
78
79 // Live ranges pass through a number of stages as we try to allocate them.
80 // Some of the stages may also create new live ranges:
81 //
82 // - Region splitting.
83 // - Per-block splitting.
84 // - Local splitting.
85 // - Spilling.

--- 9 unchanged lines hidden (view full) ---

95 RS_Second, ///< Second time in the queue.
96 RS_Global, ///< Produced by global splitting.
97 RS_Local, ///< Produced by local splitting.
98 RS_Spill ///< Produced by spilling.
99 };
100
101 static const char *const StageName[];
102
104 IndexedMap<unsigned char, VirtReg2IndexFunctor> LRStage;
103 // RegInfo - Keep additional information about each live range.
104 struct RegInfo {
105 LiveRangeStage Stage;
105
106
107 // Cascade - Eviction loop prevention. See canEvictInterference().
108 unsigned Cascade;
109
110 RegInfo() : Stage(RS_New), Cascade(0) {}
111 };
112
113 IndexedMap<RegInfo, VirtReg2IndexFunctor> ExtraRegInfo;
114
106 LiveRangeStage getStage(const LiveInterval &VirtReg) const {
115 LiveRangeStage getStage(const LiveInterval &VirtReg) const {
107 return LiveRangeStage(LRStage[VirtReg.reg]);
116 return ExtraRegInfo[VirtReg.reg].Stage;
108 }
109
117 }
118
119 void setStage(const LiveInterval &VirtReg, LiveRangeStage Stage) {
120 ExtraRegInfo.resize(MRI->getNumVirtRegs());
121 ExtraRegInfo[VirtReg.reg].Stage = Stage;
122 }
123
110 template<typename Iterator>
111 void setStage(Iterator Begin, Iterator End, LiveRangeStage NewStage) {
124 template<typename Iterator>
125 void setStage(Iterator Begin, Iterator End, LiveRangeStage NewStage) {
112 LRStage.resize(MRI->getNumVirtRegs());
126 ExtraRegInfo.resize(MRI->getNumVirtRegs());
113 for (;Begin != End; ++Begin) {
114 unsigned Reg = (*Begin)->reg;
127 for (;Begin != End; ++Begin) {
128 unsigned Reg = (*Begin)->reg;
115 if (LRStage[Reg] == RS_New)
116 LRStage[Reg] = NewStage;
129 if (ExtraRegInfo[Reg].Stage == RS_New)
130 ExtraRegInfo[Reg].Stage = NewStage;
117 }
118 }
119
131 }
132 }
133
120 // Eviction. Sometimes an assigned live range can be evicted without
121 // conditions, but other times it must be split after being evicted to avoid
122 // infinite loops.
123 enum CanEvict {
124 CE_Never, ///< Can never evict.
125 CE_Always, ///< Can always evict.
126 CE_WithSplit ///< Can evict only if range is also split or spilled.
134 /// Cost of evicting interference.
135 struct EvictionCost {
136 unsigned BrokenHints; ///< Total number of broken hints.
137 float MaxWeight; ///< Maximum spill weight evicted.
138
139 EvictionCost(unsigned B = 0) : BrokenHints(B), MaxWeight(0) {}
140
141 bool operator<(const EvictionCost &O) const {
142 if (BrokenHints != O.BrokenHints)
143 return BrokenHints < O.BrokenHints;
144 return MaxWeight < O.MaxWeight;
145 }
127 };
128
129 // splitting state.
130 std::auto_ptr<SplitAnalysis> SA;
131 std::auto_ptr<SplitEditor> SE;
132
133 /// Cached per-block interference maps
134 InterferenceCache IntfCache;
135
136 /// All basic blocks where the current register has uses.
137 SmallVector<SpillPlacement::BlockConstraint, 8> SplitConstraints;
138
139 /// Global live range splitting candidate info.
140 struct GlobalSplitCandidate {
141 unsigned PhysReg;
146 };
147
148 // splitting state.
149 std::auto_ptr<SplitAnalysis> SA;
150 std::auto_ptr<SplitEditor> SE;
151
152 /// Cached per-block interference maps
153 InterferenceCache IntfCache;
154
155 /// All basic blocks where the current register has uses.
156 SmallVector<SpillPlacement::BlockConstraint, 8> SplitConstraints;
157
158 /// Global live range splitting candidate info.
159 struct GlobalSplitCandidate {
160 unsigned PhysReg;
161 InterferenceCache::Cursor Intf;
142 BitVector LiveBundles;
143 SmallVector<unsigned, 8> ActiveBlocks;
144
162 BitVector LiveBundles;
163 SmallVector<unsigned, 8> ActiveBlocks;
164
145 void reset(unsigned Reg) {
165 void reset(InterferenceCache &Cache, unsigned Reg) {
146 PhysReg = Reg;
166 PhysReg = Reg;
167 Intf.setPhysReg(Cache, Reg);
147 LiveBundles.clear();
148 ActiveBlocks.clear();
149 }
150 };
151
152 /// Candidate info for for each PhysReg in AllocationOrder.
153 /// This vector never shrinks, but grows to the size of the largest register
154 /// class.

--- 25 unchanged lines hidden (view full) ---

180 void LRE_WillEraseInstruction(MachineInstr*);
181 bool LRE_CanEraseVirtReg(unsigned);
182 void LRE_WillShrinkVirtReg(unsigned);
183 void LRE_DidCloneVirtReg(unsigned, unsigned);
184
185 float calcSpillCost();
186 bool addSplitConstraints(InterferenceCache::Cursor, float&);
187 void addThroughConstraints(InterferenceCache::Cursor, ArrayRef<unsigned>);
168 LiveBundles.clear();
169 ActiveBlocks.clear();
170 }
171 };
172
173 /// Candidate info for for each PhysReg in AllocationOrder.
174 /// This vector never shrinks, but grows to the size of the largest register
175 /// class.

--- 25 unchanged lines hidden (view full) ---

201 void LRE_WillEraseInstruction(MachineInstr*);
202 bool LRE_CanEraseVirtReg(unsigned);
203 void LRE_WillShrinkVirtReg(unsigned);
204 void LRE_DidCloneVirtReg(unsigned, unsigned);
205
206 float calcSpillCost();
207 bool addSplitConstraints(InterferenceCache::Cursor, float&);
208 void addThroughConstraints(InterferenceCache::Cursor, ArrayRef<unsigned>);
188 void growRegion(GlobalSplitCandidate &Cand, InterferenceCache::Cursor);
189 float calcGlobalSplitCost(GlobalSplitCandidate&, InterferenceCache::Cursor);
209 void growRegion(GlobalSplitCandidate &Cand);
210 float calcGlobalSplitCost(GlobalSplitCandidate&);
190 void splitAroundRegion(LiveInterval&, GlobalSplitCandidate&,
191 SmallVectorImpl<LiveInterval*>&);
192 void calcGapWeights(unsigned, SmallVectorImpl<float>&);
211 void splitAroundRegion(LiveInterval&, GlobalSplitCandidate&,
212 SmallVectorImpl<LiveInterval*>&);
213 void calcGapWeights(unsigned, SmallVectorImpl<float>&);
193 CanEvict canEvict(LiveInterval &A, LiveInterval &B);
194 bool canEvictInterference(LiveInterval&, unsigned, float&);
214 bool shouldEvict(LiveInterval &A, bool, LiveInterval &B, bool);
215 bool canEvictInterference(LiveInterval&, unsigned, bool, EvictionCost&);
216 void evictInterference(LiveInterval&, unsigned,
217 SmallVectorImpl<LiveInterval*>&);
195
196 unsigned tryAssign(LiveInterval&, AllocationOrder&,
197 SmallVectorImpl<LiveInterval*>&);
198 unsigned tryEvict(LiveInterval&, AllocationOrder&,
199 SmallVectorImpl<LiveInterval*>&, unsigned = ~0u);
200 unsigned tryRegionSplit(LiveInterval&, AllocationOrder&,
201 SmallVectorImpl<LiveInterval*>&);
202 unsigned tryLocalSplit(LiveInterval&, AllocationOrder&,

--- 20 unchanged lines hidden (view full) ---

223// This helps stabilize decisions based on float comparisons.
224const float Hysteresis = 0.98f;
225
226
227FunctionPass* llvm::createGreedyRegisterAllocator() {
228 return new RAGreedy();
229}
230
218
219 unsigned tryAssign(LiveInterval&, AllocationOrder&,
220 SmallVectorImpl<LiveInterval*>&);
221 unsigned tryEvict(LiveInterval&, AllocationOrder&,
222 SmallVectorImpl<LiveInterval*>&, unsigned = ~0u);
223 unsigned tryRegionSplit(LiveInterval&, AllocationOrder&,
224 SmallVectorImpl<LiveInterval*>&);
225 unsigned tryLocalSplit(LiveInterval&, AllocationOrder&,

--- 20 unchanged lines hidden (view full) ---

246// This helps stabilize decisions based on float comparisons.
247const float Hysteresis = 0.98f;
248
249
250FunctionPass* llvm::createGreedyRegisterAllocator() {
251 return new RAGreedy();
252}
253
231RAGreedy::RAGreedy(): MachineFunctionPass(ID), LRStage(RS_New) {
254RAGreedy::RAGreedy(): MachineFunctionPass(ID) {
232 initializeLiveDebugVariablesPass(*PassRegistry::getPassRegistry());
233 initializeSlotIndexesPass(*PassRegistry::getPassRegistry());
234 initializeLiveIntervalsPass(*PassRegistry::getPassRegistry());
235 initializeSlotIndexesPass(*PassRegistry::getPassRegistry());
236 initializeStrongPHIEliminationPass(*PassRegistry::getPassRegistry());
255 initializeLiveDebugVariablesPass(*PassRegistry::getPassRegistry());
256 initializeSlotIndexesPass(*PassRegistry::getPassRegistry());
257 initializeLiveIntervalsPass(*PassRegistry::getPassRegistry());
258 initializeSlotIndexesPass(*PassRegistry::getPassRegistry());
259 initializeStrongPHIEliminationPass(*PassRegistry::getPassRegistry());
237 initializeRegisterCoalescerAnalysisGroup(*PassRegistry::getPassRegistry());
260 initializeRegisterCoalescerPass(*PassRegistry::getPassRegistry());
238 initializeCalculateSpillWeightsPass(*PassRegistry::getPassRegistry());
239 initializeLiveStacksPass(*PassRegistry::getPassRegistry());
240 initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry());
241 initializeMachineLoopInfoPass(*PassRegistry::getPassRegistry());
261 initializeCalculateSpillWeightsPass(*PassRegistry::getPassRegistry());
262 initializeLiveStacksPass(*PassRegistry::getPassRegistry());
263 initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry());
264 initializeMachineLoopInfoPass(*PassRegistry::getPassRegistry());
242 initializeMachineLoopRangesPass(*PassRegistry::getPassRegistry());
243 initializeVirtRegMapPass(*PassRegistry::getPassRegistry());
244 initializeEdgeBundlesPass(*PassRegistry::getPassRegistry());
245 initializeSpillPlacementPass(*PassRegistry::getPassRegistry());
246}
247
248void RAGreedy::getAnalysisUsage(AnalysisUsage &AU) const {
249 AU.setPreservesCFG();
250 AU.addRequired<AliasAnalysis>();

--- 8 unchanged lines hidden (view full) ---

259 AU.addRequiredTransitive<RegisterCoalescer>();
260 AU.addRequired<CalculateSpillWeights>();
261 AU.addRequired<LiveStacks>();
262 AU.addPreserved<LiveStacks>();
263 AU.addRequired<MachineDominatorTree>();
264 AU.addPreserved<MachineDominatorTree>();
265 AU.addRequired<MachineLoopInfo>();
266 AU.addPreserved<MachineLoopInfo>();
265 initializeVirtRegMapPass(*PassRegistry::getPassRegistry());
266 initializeEdgeBundlesPass(*PassRegistry::getPassRegistry());
267 initializeSpillPlacementPass(*PassRegistry::getPassRegistry());
268}
269
270void RAGreedy::getAnalysisUsage(AnalysisUsage &AU) const {
271 AU.setPreservesCFG();
272 AU.addRequired<AliasAnalysis>();

--- 8 unchanged lines hidden (view full) ---

281 AU.addRequiredTransitive<RegisterCoalescer>();
282 AU.addRequired<CalculateSpillWeights>();
283 AU.addRequired<LiveStacks>();
284 AU.addPreserved<LiveStacks>();
285 AU.addRequired<MachineDominatorTree>();
286 AU.addPreserved<MachineDominatorTree>();
287 AU.addRequired<MachineLoopInfo>();
288 AU.addPreserved<MachineLoopInfo>();
267 AU.addRequired<MachineLoopRanges>();
268 AU.addPreserved<MachineLoopRanges>();
269 AU.addRequired<VirtRegMap>();
270 AU.addPreserved<VirtRegMap>();
271 AU.addRequired<EdgeBundles>();
272 AU.addRequired<SpillPlacement>();
273 MachineFunctionPass::getAnalysisUsage(AU);
274}
275
276

--- 26 unchanged lines hidden (view full) ---

303 unassign(LI, PhysReg);
304 enqueue(&LI);
305}
306
307void RAGreedy::LRE_DidCloneVirtReg(unsigned New, unsigned Old) {
308 // LRE may clone a virtual register because dead code elimination causes it to
309 // be split into connected components. Ensure that the new register gets the
310 // same stage as the parent.
289 AU.addRequired<VirtRegMap>();
290 AU.addPreserved<VirtRegMap>();
291 AU.addRequired<EdgeBundles>();
292 AU.addRequired<SpillPlacement>();
293 MachineFunctionPass::getAnalysisUsage(AU);
294}
295
296

--- 26 unchanged lines hidden (view full) ---

323 unassign(LI, PhysReg);
324 enqueue(&LI);
325}
326
327void RAGreedy::LRE_DidCloneVirtReg(unsigned New, unsigned Old) {
328 // LRE may clone a virtual register because dead code elimination causes it to
329 // be split into connected components. Ensure that the new register gets the
330 // same stage as the parent.
311 LRStage.grow(New);
312 LRStage[New] = LRStage[Old];
331 ExtraRegInfo.grow(New);
332 ExtraRegInfo[New] = ExtraRegInfo[Old];
313}
314
315void RAGreedy::releaseMemory() {
316 SpillerInstance.reset(0);
333}
334
335void RAGreedy::releaseMemory() {
336 SpillerInstance.reset(0);
317 LRStage.clear();
337 ExtraRegInfo.clear();
318 GlobalCand.clear();
319 RegAllocBase::releaseMemory();
320}
321
322void RAGreedy::enqueue(LiveInterval *LI) {
323 // Prioritize live ranges by size, assigning larger ranges first.
324 // The queue holds (size, reg) pairs.
325 const unsigned Size = LI->getSize();
326 const unsigned Reg = LI->reg;
327 assert(TargetRegisterInfo::isVirtualRegister(Reg) &&
328 "Can only enqueue virtual registers");
329 unsigned Prio;
330
338 GlobalCand.clear();
339 RegAllocBase::releaseMemory();
340}
341
342void RAGreedy::enqueue(LiveInterval *LI) {
343 // Prioritize live ranges by size, assigning larger ranges first.
344 // The queue holds (size, reg) pairs.
345 const unsigned Size = LI->getSize();
346 const unsigned Reg = LI->reg;
347 assert(TargetRegisterInfo::isVirtualRegister(Reg) &&
348 "Can only enqueue virtual registers");
349 unsigned Prio;
350
331 LRStage.grow(Reg);
332 if (LRStage[Reg] == RS_New)
333 LRStage[Reg] = RS_First;
351 ExtraRegInfo.grow(Reg);
352 if (ExtraRegInfo[Reg].Stage == RS_New)
353 ExtraRegInfo[Reg].Stage = RS_First;
334
354
335 if (LRStage[Reg] == RS_Second)
355 if (ExtraRegInfo[Reg].Stage == RS_Second)
336 // Unsplit ranges that couldn't be allocated immediately are deferred until
337 // everything else has been allocated. Long ranges are allocated last so
338 // they are split against realistic interference.
339 Prio = (1u << 31) - Size;
340 else {
341 // Everything else is allocated in long->short order. Long ranges that don't
342 // fit should be spilled ASAP so they don't create interference.
343 Prio = (1u << 31) + Size;

--- 26 unchanged lines hidden (view full) ---

370 Order.rewind();
371 unsigned PhysReg;
372 while ((PhysReg = Order.next()))
373 if (!checkPhysRegInterference(VirtReg, PhysReg))
374 break;
375 if (!PhysReg || Order.isHint(PhysReg))
376 return PhysReg;
377
356 // Unsplit ranges that couldn't be allocated immediately are deferred until
357 // everything else has been allocated. Long ranges are allocated last so
358 // they are split against realistic interference.
359 Prio = (1u << 31) - Size;
360 else {
361 // Everything else is allocated in long->short order. Long ranges that don't
362 // fit should be spilled ASAP so they don't create interference.
363 Prio = (1u << 31) + Size;

--- 26 unchanged lines hidden (view full) ---

390 Order.rewind();
391 unsigned PhysReg;
392 while ((PhysReg = Order.next()))
393 if (!checkPhysRegInterference(VirtReg, PhysReg))
394 break;
395 if (!PhysReg || Order.isHint(PhysReg))
396 return PhysReg;
397
378 // PhysReg is available. Try to evict interference from a cheaper alternative.
398 // PhysReg is available, but there may be a better choice.
399
400 // If we missed a simple hint, try to cheaply evict interference from the
401 // preferred register.
402 if (unsigned Hint = MRI->getSimpleHint(VirtReg.reg))
403 if (Order.isHint(Hint)) {
404 DEBUG(dbgs() << "missed hint " << PrintReg(Hint, TRI) << '\n');
405 EvictionCost MaxCost(1);
406 if (canEvictInterference(VirtReg, Hint, true, MaxCost)) {
407 evictInterference(VirtReg, Hint, NewVRegs);
408 return Hint;
409 }
410 }
411
412 // Try to evict interference from a cheaper alternative.
379 unsigned Cost = TRI->getCostPerUse(PhysReg);
380
381 // Most registers have 0 additional cost.
382 if (!Cost)
383 return PhysReg;
384
385 DEBUG(dbgs() << PrintReg(PhysReg, TRI) << " is available at cost " << Cost
386 << '\n');
387 unsigned CheapReg = tryEvict(VirtReg, Order, NewVRegs, Cost);
388 return CheapReg ? CheapReg : PhysReg;
389}
390
391
392//===----------------------------------------------------------------------===//
393// Interference eviction
394//===----------------------------------------------------------------------===//
395
413 unsigned Cost = TRI->getCostPerUse(PhysReg);
414
415 // Most registers have 0 additional cost.
416 if (!Cost)
417 return PhysReg;
418
419 DEBUG(dbgs() << PrintReg(PhysReg, TRI) << " is available at cost " << Cost
420 << '\n');
421 unsigned CheapReg = tryEvict(VirtReg, Order, NewVRegs, Cost);
422 return CheapReg ? CheapReg : PhysReg;
423}
424
425
426//===----------------------------------------------------------------------===//
427// Interference eviction
428//===----------------------------------------------------------------------===//
429
396/// canEvict - determine if A can evict the assigned live range B. The eviction
397/// policy defined by this function together with the allocation order defined
398/// by enqueue() decides which registers ultimately end up being split and
399/// spilled.
430/// shouldEvict - determine if A should evict the assigned live range B. The
431/// eviction policy defined by this function together with the allocation order
432/// defined by enqueue() decides which registers ultimately end up being split
433/// and spilled.
400///
434///
401/// This function must define a non-circular relation when it returns CE_Always,
402/// otherwise infinite eviction loops are possible. When evicting a <= RS_Second
403/// range, it is possible to return CE_WithSplit which forces the evicted
404/// register to be split or spilled before it can evict anything again. That
405/// guarantees progress.
406RAGreedy::CanEvict RAGreedy::canEvict(LiveInterval &A, LiveInterval &B) {
407 return A.weight > B.weight ? CE_Always : CE_Never;
435/// Cascade numbers are used to prevent infinite loops if this function is a
436/// cyclic relation.
437///
438/// @param A The live range to be assigned.
439/// @param IsHint True when A is about to be assigned to its preferred
440/// register.
441/// @param B The live range to be evicted.
442/// @param BreaksHint True when B is already assigned to its preferred register.
443bool RAGreedy::shouldEvict(LiveInterval &A, bool IsHint,
444 LiveInterval &B, bool BreaksHint) {
445 bool CanSplit = getStage(B) <= RS_Second;
446
447 // Be fairly aggressive about following hints as long as the evictee can be
448 // split.
449 if (CanSplit && IsHint && !BreaksHint)
450 return true;
451
452 return A.weight > B.weight;
408}
409
453}
454
410/// canEvict - Return true if all interferences between VirtReg and PhysReg can
411/// be evicted.
412/// Return false if any interference is heavier than MaxWeight.
413/// On return, set MaxWeight to the maximal spill weight of an interference.
455/// canEvictInterference - Return true if all interferences between VirtReg and
456/// PhysReg can be evicted. When OnlyCheap is set, don't do anything
457///
458/// @param VirtReg Live range that is about to be assigned.
459/// @param PhysReg Desired register for assignment.
460/// @prarm IsHint True when PhysReg is VirtReg's preferred register.
461/// @param MaxCost Only look for cheaper candidates and update with new cost
462/// when returning true.
463/// @returns True when interference can be evicted cheaper than MaxCost.
414bool RAGreedy::canEvictInterference(LiveInterval &VirtReg, unsigned PhysReg,
464bool RAGreedy::canEvictInterference(LiveInterval &VirtReg, unsigned PhysReg,
415 float &MaxWeight) {
416 float Weight = 0;
465 bool IsHint, EvictionCost &MaxCost) {
466 // Find VirtReg's cascade number. This will be unassigned if VirtReg was never
467 // involved in an eviction before. If a cascade number was assigned, deny
468 // evicting anything with the same or a newer cascade number. This prevents
469 // infinite eviction loops.
470 //
471 // This works out so a register without a cascade number is allowed to evict
472 // anything, and it can be evicted by anything.
473 unsigned Cascade = ExtraRegInfo[VirtReg.reg].Cascade;
474 if (!Cascade)
475 Cascade = NextCascade;
476
477 EvictionCost Cost;
417 for (const unsigned *AliasI = TRI->getOverlaps(PhysReg); *AliasI; ++AliasI) {
418 LiveIntervalUnion::Query &Q = query(VirtReg, *AliasI);
419 // If there is 10 or more interferences, chances are one is heavier.
478 for (const unsigned *AliasI = TRI->getOverlaps(PhysReg); *AliasI; ++AliasI) {
479 LiveIntervalUnion::Query &Q = query(VirtReg, *AliasI);
480 // If there is 10 or more interferences, chances are one is heavier.
420 if (Q.collectInterferingVRegs(10, MaxWeight) >= 10)
481 if (Q.collectInterferingVRegs(10) >= 10)
421 return false;
422
423 // Check if any interfering live range is heavier than MaxWeight.
424 for (unsigned i = Q.interferingVRegs().size(); i; --i) {
425 LiveInterval *Intf = Q.interferingVRegs()[i - 1];
426 if (TargetRegisterInfo::isPhysicalRegister(Intf->reg))
427 return false;
482 return false;
483
484 // Check if any interfering live range is heavier than MaxWeight.
485 for (unsigned i = Q.interferingVRegs().size(); i; --i) {
486 LiveInterval *Intf = Q.interferingVRegs()[i - 1];
487 if (TargetRegisterInfo::isPhysicalRegister(Intf->reg))
488 return false;
428 if (Intf->weight >= MaxWeight)
489 // Never evict spill products. They cannot split or spill.
490 if (getStage(*Intf) == RS_Spill)
429 return false;
491 return false;
430 switch (canEvict(VirtReg, *Intf)) {
431 case CE_Always:
432 break;
433 case CE_Never:
434 return false;
435 case CE_WithSplit:
436 if (getStage(*Intf) > RS_Second)
492 // Once a live range becomes small enough, it is urgent that we find a
493 // register for it. This is indicated by an infinite spill weight. These
494 // urgent live ranges get to evict almost anything.
495 bool Urgent = !VirtReg.isSpillable() && Intf->isSpillable();
496 // Only evict older cascades or live ranges without a cascade.
497 unsigned IntfCascade = ExtraRegInfo[Intf->reg].Cascade;
498 if (Cascade <= IntfCascade) {
499 if (!Urgent)
437 return false;
500 return false;
438 break;
501 // We permit breaking cascades for urgent evictions. It should be the
502 // last resort, though, so make it really expensive.
503 Cost.BrokenHints += 10;
439 }
504 }
440 Weight = std::max(Weight, Intf->weight);
505 // Would this break a satisfied hint?
506 bool BreaksHint = VRM->hasPreferredPhys(Intf->reg);
507 // Update eviction cost.
508 Cost.BrokenHints += BreaksHint;
509 Cost.MaxWeight = std::max(Cost.MaxWeight, Intf->weight);
510 // Abort if this would be too expensive.
511 if (!(Cost < MaxCost))
512 return false;
513 // Finally, apply the eviction policy for non-urgent evictions.
514 if (!Urgent && !shouldEvict(VirtReg, IsHint, *Intf, BreaksHint))
515 return false;
441 }
442 }
516 }
517 }
443 MaxWeight = Weight;
518 MaxCost = Cost;
444 return true;
445}
446
519 return true;
520}
521
522/// evictInterference - Evict any interferring registers that prevent VirtReg
523/// from being assigned to Physreg. This assumes that canEvictInterference
524/// returned true.
525void RAGreedy::evictInterference(LiveInterval &VirtReg, unsigned PhysReg,
526 SmallVectorImpl<LiveInterval*> &NewVRegs) {
527 // Make sure that VirtReg has a cascade number, and assign that cascade
528 // number to every evicted register. These live ranges than then only be
529 // evicted by a newer cascade, preventing infinite loops.
530 unsigned Cascade = ExtraRegInfo[VirtReg.reg].Cascade;
531 if (!Cascade)
532 Cascade = ExtraRegInfo[VirtReg.reg].Cascade = NextCascade++;
533
534 DEBUG(dbgs() << "evicting " << PrintReg(PhysReg, TRI)
535 << " interference: Cascade " << Cascade << '\n');
536 for (const unsigned *AliasI = TRI->getOverlaps(PhysReg); *AliasI; ++AliasI) {
537 LiveIntervalUnion::Query &Q = query(VirtReg, *AliasI);
538 assert(Q.seenAllInterferences() && "Didn't check all interfererences.");
539 for (unsigned i = 0, e = Q.interferingVRegs().size(); i != e; ++i) {
540 LiveInterval *Intf = Q.interferingVRegs()[i];
541 unassign(*Intf, VRM->getPhys(Intf->reg));
542 assert((ExtraRegInfo[Intf->reg].Cascade < Cascade ||
543 VirtReg.isSpillable() < Intf->isSpillable()) &&
544 "Cannot decrease cascade number, illegal eviction");
545 ExtraRegInfo[Intf->reg].Cascade = Cascade;
546 ++NumEvicted;
547 NewVRegs.push_back(Intf);
548 }
549 }
550}
551
447/// tryEvict - Try to evict all interferences for a physreg.
448/// @param VirtReg Currently unassigned virtual register.
449/// @param Order Physregs to try.
450/// @return Physreg to assign VirtReg, or 0.
451unsigned RAGreedy::tryEvict(LiveInterval &VirtReg,
452 AllocationOrder &Order,
453 SmallVectorImpl<LiveInterval*> &NewVRegs,
454 unsigned CostPerUseLimit) {
455 NamedRegionTimer T("Evict", TimerGroupName, TimePassesIsEnabled);
456
552/// tryEvict - Try to evict all interferences for a physreg.
553/// @param VirtReg Currently unassigned virtual register.
554/// @param Order Physregs to try.
555/// @return Physreg to assign VirtReg, or 0.
556unsigned RAGreedy::tryEvict(LiveInterval &VirtReg,
557 AllocationOrder &Order,
558 SmallVectorImpl<LiveInterval*> &NewVRegs,
559 unsigned CostPerUseLimit) {
560 NamedRegionTimer T("Evict", TimerGroupName, TimePassesIsEnabled);
561
457 // Keep track of the lightest single interference seen so far.
458 float BestWeight = HUGE_VALF;
562 // Keep track of the cheapest interference seen so far.
563 EvictionCost BestCost(~0u);
459 unsigned BestPhys = 0;
460
564 unsigned BestPhys = 0;
565
566 // When we are just looking for a reduced cost per use, don't break any
567 // hints, and only evict smaller spill weights.
568 if (CostPerUseLimit < ~0u) {
569 BestCost.BrokenHints = 0;
570 BestCost.MaxWeight = VirtReg.weight;
571 }
572
461 Order.rewind();
462 while (unsigned PhysReg = Order.next()) {
463 if (TRI->getCostPerUse(PhysReg) >= CostPerUseLimit)
464 continue;
573 Order.rewind();
574 while (unsigned PhysReg = Order.next()) {
575 if (TRI->getCostPerUse(PhysReg) >= CostPerUseLimit)
576 continue;
465 // The first use of a register in a function has cost 1.
466 if (CostPerUseLimit == 1 && !MRI->isPhysRegUsed(PhysReg))
467 continue;
577 // The first use of a callee-saved register in a function has cost 1.
578 // Don't start using a CSR when the CostPerUseLimit is low.
579 if (CostPerUseLimit == 1)
580 if (unsigned CSR = RegClassInfo.getLastCalleeSavedAlias(PhysReg))
581 if (!MRI->isPhysRegUsed(CSR)) {
582 DEBUG(dbgs() << PrintReg(PhysReg, TRI) << " would clobber CSR "
583 << PrintReg(CSR, TRI) << '\n');
584 continue;
585 }
468
586
469 float Weight = BestWeight;
470 if (!canEvictInterference(VirtReg, PhysReg, Weight))
587 if (!canEvictInterference(VirtReg, PhysReg, false, BestCost))
471 continue;
472
588 continue;
589
473 // This is an eviction candidate.
474 DEBUG(dbgs() << PrintReg(PhysReg, TRI) << " interference = "
475 << Weight << '\n');
476 if (BestPhys && Weight >= BestWeight)
477 continue;
478
479 // Best so far.
480 BestPhys = PhysReg;
590 // Best so far.
591 BestPhys = PhysReg;
481 BestWeight = Weight;
592
482 // Stop if the hint can be used.
483 if (Order.isHint(PhysReg))
484 break;
485 }
486
487 if (!BestPhys)
488 return 0;
489
593 // Stop if the hint can be used.
594 if (Order.isHint(PhysReg))
595 break;
596 }
597
598 if (!BestPhys)
599 return 0;
600
490 DEBUG(dbgs() << "evicting " << PrintReg(BestPhys, TRI) << " interference\n");
491 for (const unsigned *AliasI = TRI->getOverlaps(BestPhys); *AliasI; ++AliasI) {
492 LiveIntervalUnion::Query &Q = query(VirtReg, *AliasI);
493 assert(Q.seenAllInterferences() && "Didn't check all interfererences.");
494 for (unsigned i = 0, e = Q.interferingVRegs().size(); i != e; ++i) {
495 LiveInterval *Intf = Q.interferingVRegs()[i];
496 unassign(*Intf, VRM->getPhys(Intf->reg));
497 ++NumEvicted;
498 NewVRegs.push_back(Intf);
499 // Prevent looping by forcing the evicted ranges to be split before they
500 // can evict anything else.
501 if (getStage(*Intf) < RS_Second &&
502 canEvict(VirtReg, *Intf) == CE_WithSplit)
503 LRStage[Intf->reg] = RS_Second;
504 }
505 }
601 evictInterference(VirtReg, BestPhys, NewVRegs);
506 return BestPhys;
507}
508
509
510//===----------------------------------------------------------------------===//
511// Region Splitting
512//===----------------------------------------------------------------------===//
513

--- 102 unchanged lines hidden (view full) ---

616 }
617 }
618
619 ArrayRef<SpillPlacement::BlockConstraint> Array(BCS, B);
620 SpillPlacer->addConstraints(Array);
621 SpillPlacer->addLinks(ArrayRef<unsigned>(TBS, T));
622}
623
602 return BestPhys;
603}
604
605
606//===----------------------------------------------------------------------===//
607// Region Splitting
608//===----------------------------------------------------------------------===//
609

--- 102 unchanged lines hidden (view full) ---

712 }
713 }
714
715 ArrayRef<SpillPlacement::BlockConstraint> Array(BCS, B);
716 SpillPlacer->addConstraints(Array);
717 SpillPlacer->addLinks(ArrayRef<unsigned>(TBS, T));
718}
719
624void RAGreedy::growRegion(GlobalSplitCandidate &Cand,
625 InterferenceCache::Cursor Intf) {
720void RAGreedy::growRegion(GlobalSplitCandidate &Cand) {
626 // Keep track of through blocks that have not been added to SpillPlacer.
627 BitVector Todo = SA->getThroughBlocks();
628 SmallVectorImpl<unsigned> &ActiveBlocks = Cand.ActiveBlocks;
629 unsigned AddedTo = 0;
630#ifndef NDEBUG
631 unsigned Visited = 0;
632#endif
633
634 for (;;) {
635 ArrayRef<unsigned> NewBundles = SpillPlacer->getRecentPositive();
721 // Keep track of through blocks that have not been added to SpillPlacer.
722 BitVector Todo = SA->getThroughBlocks();
723 SmallVectorImpl<unsigned> &ActiveBlocks = Cand.ActiveBlocks;
724 unsigned AddedTo = 0;
725#ifndef NDEBUG
726 unsigned Visited = 0;
727#endif
728
729 for (;;) {
730 ArrayRef<unsigned> NewBundles = SpillPlacer->getRecentPositive();
636 if (NewBundles.empty())
637 break;
638 // Find new through blocks in the periphery of PrefRegBundles.
639 for (int i = 0, e = NewBundles.size(); i != e; ++i) {
640 unsigned Bundle = NewBundles[i];
641 // Look at all blocks connected to Bundle in the full graph.
642 ArrayRef<unsigned> Blocks = Bundles->getBlocks(Bundle);
643 for (ArrayRef<unsigned>::iterator I = Blocks.begin(), E = Blocks.end();
644 I != E; ++I) {
645 unsigned Block = *I;
646 if (!Todo.test(Block))
647 continue;
648 Todo.reset(Block);
649 // This is a new through block. Add it to SpillPlacer later.
650 ActiveBlocks.push_back(Block);
651#ifndef NDEBUG
652 ++Visited;
653#endif
654 }
655 }
656 // Any new blocks to add?
731 // Find new through blocks in the periphery of PrefRegBundles.
732 for (int i = 0, e = NewBundles.size(); i != e; ++i) {
733 unsigned Bundle = NewBundles[i];
734 // Look at all blocks connected to Bundle in the full graph.
735 ArrayRef<unsigned> Blocks = Bundles->getBlocks(Bundle);
736 for (ArrayRef<unsigned>::iterator I = Blocks.begin(), E = Blocks.end();
737 I != E; ++I) {
738 unsigned Block = *I;
739 if (!Todo.test(Block))
740 continue;
741 Todo.reset(Block);
742 // This is a new through block. Add it to SpillPlacer later.
743 ActiveBlocks.push_back(Block);
744#ifndef NDEBUG
745 ++Visited;
746#endif
747 }
748 }
749 // Any new blocks to add?
657 if (ActiveBlocks.size() > AddedTo) {
658 ArrayRef<unsigned> Add(&ActiveBlocks[AddedTo],
659 ActiveBlocks.size() - AddedTo);
660 addThroughConstraints(Intf, Add);
661 AddedTo = ActiveBlocks.size();
662 }
750 if (ActiveBlocks.size() == AddedTo)
751 break;
752 addThroughConstraints(Cand.Intf,
753 ArrayRef<unsigned>(ActiveBlocks).slice(AddedTo));
754 AddedTo = ActiveBlocks.size();
755
663 // Perhaps iterating can enable more bundles?
664 SpillPlacer->iterate();
665 }
666 DEBUG(dbgs() << ", v=" << Visited);
667}
668
669/// calcSpillCost - Compute how expensive it would be to split the live range in
670/// SA around all use blocks instead of forming bundle regions.

--- 21 unchanged lines hidden (view full) ---

692 }
693 return Cost;
694}
695
696/// calcGlobalSplitCost - Return the global split cost of following the split
697/// pattern in LiveBundles. This cost should be added to the local cost of the
698/// interference pattern in SplitConstraints.
699///
756 // Perhaps iterating can enable more bundles?
757 SpillPlacer->iterate();
758 }
759 DEBUG(dbgs() << ", v=" << Visited);
760}
761
762/// calcSpillCost - Compute how expensive it would be to split the live range in
763/// SA around all use blocks instead of forming bundle regions.

--- 21 unchanged lines hidden (view full) ---

785 }
786 return Cost;
787}
788
789/// calcGlobalSplitCost - Return the global split cost of following the split
790/// pattern in LiveBundles. This cost should be added to the local cost of the
791/// interference pattern in SplitConstraints.
792///
700float RAGreedy::calcGlobalSplitCost(GlobalSplitCandidate &Cand,
701 InterferenceCache::Cursor Intf) {
793float RAGreedy::calcGlobalSplitCost(GlobalSplitCandidate &Cand) {
702 float GlobalCost = 0;
703 const BitVector &LiveBundles = Cand.LiveBundles;
704 ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks();
705 for (unsigned i = 0; i != UseBlocks.size(); ++i) {
706 const SplitAnalysis::BlockInfo &BI = UseBlocks[i];
707 SpillPlacement::BlockConstraint &BC = SplitConstraints[i];
708 bool RegIn = LiveBundles[Bundles->getBundle(BC.Number, 0)];
709 bool RegOut = LiveBundles[Bundles->getBundle(BC.Number, 1)];

--- 10 unchanged lines hidden (view full) ---

720 for (unsigned i = 0, e = Cand.ActiveBlocks.size(); i != e; ++i) {
721 unsigned Number = Cand.ActiveBlocks[i];
722 bool RegIn = LiveBundles[Bundles->getBundle(Number, 0)];
723 bool RegOut = LiveBundles[Bundles->getBundle(Number, 1)];
724 if (!RegIn && !RegOut)
725 continue;
726 if (RegIn && RegOut) {
727 // We need double spill code if this block has interference.
794 float GlobalCost = 0;
795 const BitVector &LiveBundles = Cand.LiveBundles;
796 ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks();
797 for (unsigned i = 0; i != UseBlocks.size(); ++i) {
798 const SplitAnalysis::BlockInfo &BI = UseBlocks[i];
799 SpillPlacement::BlockConstraint &BC = SplitConstraints[i];
800 bool RegIn = LiveBundles[Bundles->getBundle(BC.Number, 0)];
801 bool RegOut = LiveBundles[Bundles->getBundle(BC.Number, 1)];

--- 10 unchanged lines hidden (view full) ---

812 for (unsigned i = 0, e = Cand.ActiveBlocks.size(); i != e; ++i) {
813 unsigned Number = Cand.ActiveBlocks[i];
814 bool RegIn = LiveBundles[Bundles->getBundle(Number, 0)];
815 bool RegOut = LiveBundles[Bundles->getBundle(Number, 1)];
816 if (!RegIn && !RegOut)
817 continue;
818 if (RegIn && RegOut) {
819 // We need double spill code if this block has interference.
728 Intf.moveToBlock(Number);
729 if (Intf.hasInterference())
820 Cand.Intf.moveToBlock(Number);
821 if (Cand.Intf.hasInterference())
730 GlobalCost += 2*SpillPlacer->getBlockFrequency(Number);
731 continue;
732 }
733 // live-in / stack-out or stack-in live-out.
734 GlobalCost += SpillPlacer->getBlockFrequency(Number);
735 }
736 return GlobalCost;
737}

--- 13 unchanged lines hidden (view full) ---

751 DEBUG({
752 dbgs() << "Splitting around region for " << PrintReg(Cand.PhysReg, TRI)
753 << " with bundles";
754 for (int i = LiveBundles.find_first(); i>=0; i = LiveBundles.find_next(i))
755 dbgs() << " EB#" << i;
756 dbgs() << ".\n";
757 });
758
822 GlobalCost += 2*SpillPlacer->getBlockFrequency(Number);
823 continue;
824 }
825 // live-in / stack-out or stack-in live-out.
826 GlobalCost += SpillPlacer->getBlockFrequency(Number);
827 }
828 return GlobalCost;
829}

--- 13 unchanged lines hidden (view full) ---

843 DEBUG({
844 dbgs() << "Splitting around region for " << PrintReg(Cand.PhysReg, TRI)
845 << " with bundles";
846 for (int i = LiveBundles.find_first(); i>=0; i = LiveBundles.find_next(i))
847 dbgs() << " EB#" << i;
848 dbgs() << ".\n";
849 });
850
759 InterferenceCache::Cursor Intf(IntfCache, Cand.PhysReg);
851 InterferenceCache::Cursor &Intf = Cand.Intf;
760 LiveRangeEdit LREdit(VirtReg, NewVRegs, this);
761 SE->reset(LREdit);
762
763 // Create the main cross-block interval.
764 const unsigned MainIntv = SE->openIntv();
765
852 LiveRangeEdit LREdit(VirtReg, NewVRegs, this);
853 SE->reset(LREdit);
854
855 // Create the main cross-block interval.
856 const unsigned MainIntv = SE->openIntv();
857
766 // First add all defs that are live out of a block.
858 // First handle all the blocks with uses.
767 ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks();
768 for (unsigned i = 0; i != UseBlocks.size(); ++i) {
769 const SplitAnalysis::BlockInfo &BI = UseBlocks[i];
859 ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks();
860 for (unsigned i = 0; i != UseBlocks.size(); ++i) {
861 const SplitAnalysis::BlockInfo &BI = UseBlocks[i];
770 bool RegIn = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 0)];
771 bool RegOut = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 1)];
862 bool RegIn = BI.LiveIn &&
863 LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 0)];
864 bool RegOut = BI.LiveOut &&
865 LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 1)];
772
773 // Create separate intervals for isolated blocks with multiple uses.
866
867 // Create separate intervals for isolated blocks with multiple uses.
774 if (!RegIn && !RegOut && BI.FirstUse != BI.LastUse) {
868 if (!RegIn && !RegOut) {
775 DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " isolated.\n");
869 DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " isolated.\n");
776 SE->splitSingleBlock(BI);
777 SE->selectIntv(MainIntv);
778 continue;
779 }
780
781 // Should the register be live out?
782 if (!BI.LiveOut || !RegOut)
783 continue;
784
785 SlotIndex Start, Stop;
786 tie(Start, Stop) = Indexes->getMBBRange(BI.MBB);
787 Intf.moveToBlock(BI.MBB->getNumber());
788 DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " -> EB#"
789 << Bundles->getBundle(BI.MBB->getNumber(), 1)
790 << " [" << Start << ';'
791 << SA->getLastSplitPoint(BI.MBB->getNumber()) << '-' << Stop
792 << ") intf [" << Intf.first() << ';' << Intf.last() << ')');
793
794 // The interference interval should either be invalid or overlap MBB.
795 assert((!Intf.hasInterference() || Intf.first() < Stop)
796 && "Bad interference");
797 assert((!Intf.hasInterference() || Intf.last() > Start)
798 && "Bad interference");
799
800 // Check interference leaving the block.
801 if (!Intf.hasInterference()) {
802 // Block is interference-free.
803 DEBUG(dbgs() << ", no interference");
804 if (!BI.LiveThrough) {
805 DEBUG(dbgs() << ", not live-through.\n");
806 SE->useIntv(SE->enterIntvBefore(BI.FirstUse), Stop);
807 continue;
870 if (!BI.isOneInstr()) {
871 SE->splitSingleBlock(BI);
872 SE->selectIntv(MainIntv);
808 }
873 }
809 if (!RegIn) {
810 // Block is live-through, but entry bundle is on the stack.
811 // Reload just before the first use.
812 DEBUG(dbgs() << ", not live-in, enter before first use.\n");
813 SE->useIntv(SE->enterIntvBefore(BI.FirstUse), Stop);
814 continue;
815 }
816 DEBUG(dbgs() << ", live-through.\n");
817 continue;
818 }
819
874 continue;
875 }
876
820 // Block has interference.
821 DEBUG(dbgs() << ", interference to " << Intf.last());
822
823 if (!BI.LiveThrough && Intf.last() <= BI.FirstUse) {
824 // The interference doesn't reach the outgoing segment.
825 DEBUG(dbgs() << " doesn't affect def from " << BI.FirstUse << '\n');
826 SE->useIntv(BI.FirstUse, Stop);
827 continue;
828 }
829
830 SlotIndex LastSplitPoint = SA->getLastSplitPoint(BI.MBB->getNumber());
831 if (Intf.last().getBoundaryIndex() < BI.LastUse) {
832 // There are interference-free uses at the end of the block.
833 // Find the first use that can get the live-out register.
834 SmallVectorImpl<SlotIndex>::const_iterator UI =
835 std::lower_bound(SA->UseSlots.begin(), SA->UseSlots.end(),
836 Intf.last().getBoundaryIndex());
837 assert(UI != SA->UseSlots.end() && "Couldn't find last use");
838 SlotIndex Use = *UI;
839 assert(Use <= BI.LastUse && "Couldn't find last use");
840 // Only attempt a split befroe the last split point.
841 if (Use.getBaseIndex() <= LastSplitPoint) {
842 DEBUG(dbgs() << ", free use at " << Use << ".\n");
843 SlotIndex SegStart = SE->enterIntvBefore(Use);
844 assert(SegStart >= Intf.last() && "Couldn't avoid interference");
845 assert(SegStart < LastSplitPoint && "Impossible split point");
846 SE->useIntv(SegStart, Stop);
847 continue;
848 }
849 }
850
851 // Interference is after the last use.
852 DEBUG(dbgs() << " after last use.\n");
853 SlotIndex SegStart = SE->enterIntvAtEnd(*BI.MBB);
854 assert(SegStart >= Intf.last() && "Couldn't avoid interference");
855 }
856
857 // Now all defs leading to live bundles are handled, do everything else.
858 for (unsigned i = 0; i != UseBlocks.size(); ++i) {
859 const SplitAnalysis::BlockInfo &BI = UseBlocks[i];
860 bool RegIn = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 0)];
861 bool RegOut = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 1)];
862
863 // Is the register live-in?
864 if (!BI.LiveIn || !RegIn)
865 continue;
866
867 // We have an incoming register. Check for interference.
868 SlotIndex Start, Stop;
869 tie(Start, Stop) = Indexes->getMBBRange(BI.MBB);
870 Intf.moveToBlock(BI.MBB->getNumber());
877 Intf.moveToBlock(BI.MBB->getNumber());
871 DEBUG(dbgs() << "EB#" << Bundles->getBundle(BI.MBB->getNumber(), 0)
872 << " -> BB#" << BI.MBB->getNumber() << " [" << Start << ';'
873 << SA->getLastSplitPoint(BI.MBB->getNumber()) << '-' << Stop
874 << ')');
875
878
876 // Check interference entering the block.
877 if (!Intf.hasInterference()) {
878 // Block is interference-free.
879 DEBUG(dbgs() << ", no interference");
880 if (!BI.LiveThrough) {
881 DEBUG(dbgs() << ", killed in block.\n");
882 SE->useIntv(Start, SE->leaveIntvAfter(BI.LastUse));
883 continue;
884 }
885 if (!RegOut) {
886 SlotIndex LastSplitPoint = SA->getLastSplitPoint(BI.MBB->getNumber());
887 // Block is live-through, but exit bundle is on the stack.
888 // Spill immediately after the last use.
889 if (BI.LastUse < LastSplitPoint) {
890 DEBUG(dbgs() << ", uses, stack-out.\n");
891 SE->useIntv(Start, SE->leaveIntvAfter(BI.LastUse));
892 continue;
893 }
894 // The last use is after the last split point, it is probably an
895 // indirect jump.
896 DEBUG(dbgs() << ", uses at " << BI.LastUse << " after split point "
897 << LastSplitPoint << ", stack-out.\n");
898 SlotIndex SegEnd = SE->leaveIntvBefore(LastSplitPoint);
899 SE->useIntv(Start, SegEnd);
900 // Run a double interval from the split to the last use.
901 // This makes it possible to spill the complement without affecting the
902 // indirect branch.
903 SE->overlapIntv(SegEnd, BI.LastUse);
904 continue;
905 }
906 // Register is live-through.
907 DEBUG(dbgs() << ", uses, live-through.\n");
908 SE->useIntv(Start, Stop);
909 continue;
910 }
911
912 // Block has interference.
913 DEBUG(dbgs() << ", interference from " << Intf.first());
914
915 if (!BI.LiveThrough && Intf.first() >= BI.LastUse) {
916 // The interference doesn't reach the outgoing segment.
917 DEBUG(dbgs() << " doesn't affect kill at " << BI.LastUse << '\n');
918 SE->useIntv(Start, BI.LastUse);
919 continue;
920 }
921
922 if (Intf.first().getBaseIndex() > BI.FirstUse) {
923 // There are interference-free uses at the beginning of the block.
924 // Find the last use that can get the register.
925 SmallVectorImpl<SlotIndex>::const_iterator UI =
926 std::lower_bound(SA->UseSlots.begin(), SA->UseSlots.end(),
927 Intf.first().getBaseIndex());
928 assert(UI != SA->UseSlots.begin() && "Couldn't find first use");
929 SlotIndex Use = (--UI)->getBoundaryIndex();
930 DEBUG(dbgs() << ", free use at " << *UI << ".\n");
931 SlotIndex SegEnd = SE->leaveIntvAfter(Use);
932 assert(SegEnd <= Intf.first() && "Couldn't avoid interference");
933 SE->useIntv(Start, SegEnd);
934 continue;
935 }
936
937 // Interference is before the first use.
938 DEBUG(dbgs() << " before first use.\n");
939 SlotIndex SegEnd = SE->leaveIntvAtTop(*BI.MBB);
940 assert(SegEnd <= Intf.first() && "Couldn't avoid interference");
879 if (RegIn && RegOut)
880 SE->splitLiveThroughBlock(BI.MBB->getNumber(),
881 MainIntv, Intf.first(),
882 MainIntv, Intf.last());
883 else if (RegIn)
884 SE->splitRegInBlock(BI, MainIntv, Intf.first());
885 else
886 SE->splitRegOutBlock(BI, MainIntv, Intf.last());
941 }
942
943 // Handle live-through blocks.
944 for (unsigned i = 0, e = Cand.ActiveBlocks.size(); i != e; ++i) {
945 unsigned Number = Cand.ActiveBlocks[i];
946 bool RegIn = LiveBundles[Bundles->getBundle(Number, 0)];
947 bool RegOut = LiveBundles[Bundles->getBundle(Number, 1)];
887 }
888
889 // Handle live-through blocks.
890 for (unsigned i = 0, e = Cand.ActiveBlocks.size(); i != e; ++i) {
891 unsigned Number = Cand.ActiveBlocks[i];
892 bool RegIn = LiveBundles[Bundles->getBundle(Number, 0)];
893 bool RegOut = LiveBundles[Bundles->getBundle(Number, 1)];
948 DEBUG(dbgs() << "Live through BB#" << Number << '\n');
949 if (RegIn && RegOut) {
950 Intf.moveToBlock(Number);
951 if (!Intf.hasInterference()) {
952 SE->useIntv(Indexes->getMBBStartIdx(Number),
953 Indexes->getMBBEndIdx(Number));
954 continue;
955 }
956 }
957 MachineBasicBlock *MBB = MF->getBlockNumbered(Number);
958 if (RegIn)
959 SE->leaveIntvAtTop(*MBB);
960 if (RegOut)
961 SE->enterIntvAtEnd(*MBB);
894 if (!RegIn && !RegOut)
895 continue;
896 Intf.moveToBlock(Number);
897 SE->splitLiveThroughBlock(Number, RegIn ? MainIntv : 0, Intf.first(),
898 RegOut ? MainIntv : 0, Intf.last());
962 }
963
964 ++NumGlobalSplits;
965
966 SmallVector<unsigned, 8> IntvMap;
967 SE->finish(&IntvMap);
968 DebugVars->splitRegister(VirtReg.reg, LREdit.regs());
969
899 }
900
901 ++NumGlobalSplits;
902
903 SmallVector<unsigned, 8> IntvMap;
904 SE->finish(&IntvMap);
905 DebugVars->splitRegister(VirtReg.reg, LREdit.regs());
906
970 LRStage.resize(MRI->getNumVirtRegs());
907 ExtraRegInfo.resize(MRI->getNumVirtRegs());
971 unsigned OrigBlocks = SA->getNumLiveBlocks();
972
973 // Sort out the new intervals created by splitting. We get four kinds:
974 // - Remainder intervals should not be split again.
975 // - Candidate intervals can be assigned to Cand.PhysReg.
976 // - Block-local splits are candidates for local splitting.
977 // - DCE leftovers should go back on the queue.
978 for (unsigned i = 0, e = LREdit.size(); i != e; ++i) {
908 unsigned OrigBlocks = SA->getNumLiveBlocks();
909
910 // Sort out the new intervals created by splitting. We get four kinds:
911 // - Remainder intervals should not be split again.
912 // - Candidate intervals can be assigned to Cand.PhysReg.
913 // - Block-local splits are candidates for local splitting.
914 // - DCE leftovers should go back on the queue.
915 for (unsigned i = 0, e = LREdit.size(); i != e; ++i) {
979 unsigned Reg = LREdit.get(i)->reg;
916 LiveInterval &Reg = *LREdit.get(i);
980
981 // Ignore old intervals from DCE.
917
918 // Ignore old intervals from DCE.
982 if (LRStage[Reg] != RS_New)
919 if (getStage(Reg) != RS_New)
983 continue;
984
985 // Remainder interval. Don't try splitting again, spill if it doesn't
986 // allocate.
987 if (IntvMap[i] == 0) {
920 continue;
921
922 // Remainder interval. Don't try splitting again, spill if it doesn't
923 // allocate.
924 if (IntvMap[i] == 0) {
988 LRStage[Reg] = RS_Global;
925 setStage(Reg, RS_Global);
989 continue;
990 }
991
992 // Main interval. Allow repeated splitting as long as the number of live
993 // blocks is strictly decreasing.
994 if (IntvMap[i] == MainIntv) {
926 continue;
927 }
928
929 // Main interval. Allow repeated splitting as long as the number of live
930 // blocks is strictly decreasing.
931 if (IntvMap[i] == MainIntv) {
995 if (SA->countLiveBlocks(LREdit.get(i)) >= OrigBlocks) {
932 if (SA->countLiveBlocks(&Reg) >= OrigBlocks) {
996 DEBUG(dbgs() << "Main interval covers the same " << OrigBlocks
997 << " blocks as original.\n");
998 // Don't allow repeated splitting as a safe guard against looping.
933 DEBUG(dbgs() << "Main interval covers the same " << OrigBlocks
934 << " blocks as original.\n");
935 // Don't allow repeated splitting as a safe guard against looping.
999 LRStage[Reg] = RS_Global;
936 setStage(Reg, RS_Global);
1000 }
1001 continue;
1002 }
1003
1004 // Other intervals are treated as new. This includes local intervals created
1005 // for blocks with multiple uses, and anything created by DCE.
1006 }
1007
1008 if (VerifyEnabled)
1009 MF->verify(this, "After splitting live range around region");
1010}
1011
1012unsigned RAGreedy::tryRegionSplit(LiveInterval &VirtReg, AllocationOrder &Order,
1013 SmallVectorImpl<LiveInterval*> &NewVRegs) {
1014 float BestCost = Hysteresis * calcSpillCost();
1015 DEBUG(dbgs() << "Cost of isolating all blocks = " << BestCost << '\n');
1016 const unsigned NoCand = ~0u;
1017 unsigned BestCand = NoCand;
937 }
938 continue;
939 }
940
941 // Other intervals are treated as new. This includes local intervals created
942 // for blocks with multiple uses, and anything created by DCE.
943 }
944
945 if (VerifyEnabled)
946 MF->verify(this, "After splitting live range around region");
947}
948
949unsigned RAGreedy::tryRegionSplit(LiveInterval &VirtReg, AllocationOrder &Order,
950 SmallVectorImpl<LiveInterval*> &NewVRegs) {
951 float BestCost = Hysteresis * calcSpillCost();
952 DEBUG(dbgs() << "Cost of isolating all blocks = " << BestCost << '\n');
953 const unsigned NoCand = ~0u;
954 unsigned BestCand = NoCand;
955 unsigned NumCands = 0;
1018
1019 Order.rewind();
956
957 Order.rewind();
1020 for (unsigned Cand = 0; unsigned PhysReg = Order.next(); ++Cand) {
1021 if (GlobalCand.size() <= Cand)
1022 GlobalCand.resize(Cand+1);
1023 GlobalCand[Cand].reset(PhysReg);
958 while (unsigned PhysReg = Order.next()) {
959 // Discard bad candidates before we run out of interference cache cursors.
960 // This will only affect register classes with a lot of registers (>32).
961 if (NumCands == IntfCache.getMaxCursors()) {
962 unsigned WorstCount = ~0u;
963 unsigned Worst = 0;
964 for (unsigned i = 0; i != NumCands; ++i) {
965 if (i == BestCand)
966 continue;
967 unsigned Count = GlobalCand[i].LiveBundles.count();
968 if (Count < WorstCount)
969 Worst = i, WorstCount = Count;
970 }
971 --NumCands;
972 GlobalCand[Worst] = GlobalCand[NumCands];
973 }
1024
974
1025 SpillPlacer->prepare(GlobalCand[Cand].LiveBundles);
975 if (GlobalCand.size() <= NumCands)
976 GlobalCand.resize(NumCands+1);
977 GlobalSplitCandidate &Cand = GlobalCand[NumCands];
978 Cand.reset(IntfCache, PhysReg);
979
980 SpillPlacer->prepare(Cand.LiveBundles);
1026 float Cost;
981 float Cost;
1027 InterferenceCache::Cursor Intf(IntfCache, PhysReg);
1028 if (!addSplitConstraints(Intf, Cost)) {
982 if (!addSplitConstraints(Cand.Intf, Cost)) {
1029 DEBUG(dbgs() << PrintReg(PhysReg, TRI) << "\tno positive bundles\n");
1030 continue;
1031 }
1032 DEBUG(dbgs() << PrintReg(PhysReg, TRI) << "\tstatic = " << Cost);
1033 if (Cost >= BestCost) {
1034 DEBUG({
1035 if (BestCand == NoCand)
1036 dbgs() << " worse than no bundles\n";
1037 else
1038 dbgs() << " worse than "
1039 << PrintReg(GlobalCand[BestCand].PhysReg, TRI) << '\n';
1040 });
1041 continue;
1042 }
983 DEBUG(dbgs() << PrintReg(PhysReg, TRI) << "\tno positive bundles\n");
984 continue;
985 }
986 DEBUG(dbgs() << PrintReg(PhysReg, TRI) << "\tstatic = " << Cost);
987 if (Cost >= BestCost) {
988 DEBUG({
989 if (BestCand == NoCand)
990 dbgs() << " worse than no bundles\n";
991 else
992 dbgs() << " worse than "
993 << PrintReg(GlobalCand[BestCand].PhysReg, TRI) << '\n';
994 });
995 continue;
996 }
1043 growRegion(GlobalCand[Cand], Intf);
997 growRegion(Cand);
1044
1045 SpillPlacer->finish();
1046
1047 // No live bundles, defer to splitSingleBlocks().
998
999 SpillPlacer->finish();
1000
1001 // No live bundles, defer to splitSingleBlocks().
1048 if (!GlobalCand[Cand].LiveBundles.any()) {
1002 if (!Cand.LiveBundles.any()) {
1049 DEBUG(dbgs() << " no bundles.\n");
1050 continue;
1051 }
1052
1003 DEBUG(dbgs() << " no bundles.\n");
1004 continue;
1005 }
1006
1053 Cost += calcGlobalSplitCost(GlobalCand[Cand], Intf);
1007 Cost += calcGlobalSplitCost(Cand);
1054 DEBUG({
1055 dbgs() << ", total = " << Cost << " with bundles";
1008 DEBUG({
1009 dbgs() << ", total = " << Cost << " with bundles";
1056 for (int i = GlobalCand[Cand].LiveBundles.find_first(); i>=0;
1057 i = GlobalCand[Cand].LiveBundles.find_next(i))
1010 for (int i = Cand.LiveBundles.find_first(); i>=0;
1011 i = Cand.LiveBundles.find_next(i))
1058 dbgs() << " EB#" << i;
1059 dbgs() << ".\n";
1060 });
1061 if (Cost < BestCost) {
1012 dbgs() << " EB#" << i;
1013 dbgs() << ".\n";
1014 });
1015 if (Cost < BestCost) {
1062 BestCand = Cand;
1016 BestCand = NumCands;
1063 BestCost = Hysteresis * Cost; // Prevent rounding effects.
1064 }
1017 BestCost = Hysteresis * Cost; // Prevent rounding effects.
1018 }
1019 ++NumCands;
1065 }
1066
1067 if (BestCand == NoCand)
1068 return 0;
1069
1070 splitAroundRegion(VirtReg, GlobalCand[BestCand], NewVRegs);
1071 return 0;
1072}

--- 224 unchanged lines hidden (view full) ---

1297 // RS_Local so the next split will be forced to make progress. Otherwise,
1298 // leave the new intervals as RS_New so they can compete.
1299 bool LiveBefore = BestBefore != 0 || BI.LiveIn;
1300 bool LiveAfter = BestAfter != NumGaps || BI.LiveOut;
1301 unsigned NewGaps = LiveBefore + BestAfter - BestBefore + LiveAfter;
1302 if (NewGaps >= NumGaps) {
1303 DEBUG(dbgs() << "Tagging non-progress ranges: ");
1304 assert(!ProgressRequired && "Didn't make progress when it was required.");
1020 }
1021
1022 if (BestCand == NoCand)
1023 return 0;
1024
1025 splitAroundRegion(VirtReg, GlobalCand[BestCand], NewVRegs);
1026 return 0;
1027}

--- 224 unchanged lines hidden (view full) ---

1252 // RS_Local so the next split will be forced to make progress. Otherwise,
1253 // leave the new intervals as RS_New so they can compete.
1254 bool LiveBefore = BestBefore != 0 || BI.LiveIn;
1255 bool LiveAfter = BestAfter != NumGaps || BI.LiveOut;
1256 unsigned NewGaps = LiveBefore + BestAfter - BestBefore + LiveAfter;
1257 if (NewGaps >= NumGaps) {
1258 DEBUG(dbgs() << "Tagging non-progress ranges: ");
1259 assert(!ProgressRequired && "Didn't make progress when it was required.");
1305 LRStage.resize(MRI->getNumVirtRegs());
1306 for (unsigned i = 0, e = IntvMap.size(); i != e; ++i)
1307 if (IntvMap[i] == 1) {
1260 for (unsigned i = 0, e = IntvMap.size(); i != e; ++i)
1261 if (IntvMap[i] == 1) {
1308 LRStage[LREdit.get(i)->reg] = RS_Local;
1262 setStage(*LREdit.get(i), RS_Local);
1309 DEBUG(dbgs() << PrintReg(LREdit.get(i)->reg));
1310 }
1311 DEBUG(dbgs() << '\n');
1312 }
1313 ++NumLocalSplits;
1314
1315 return 0;
1316}

--- 62 unchanged lines hidden (view full) ---

1379unsigned RAGreedy::selectOrSplit(LiveInterval &VirtReg,
1380 SmallVectorImpl<LiveInterval*> &NewVRegs) {
1381 // First try assigning a free register.
1382 AllocationOrder Order(VirtReg.reg, *VRM, RegClassInfo);
1383 if (unsigned PhysReg = tryAssign(VirtReg, Order, NewVRegs))
1384 return PhysReg;
1385
1386 LiveRangeStage Stage = getStage(VirtReg);
1263 DEBUG(dbgs() << PrintReg(LREdit.get(i)->reg));
1264 }
1265 DEBUG(dbgs() << '\n');
1266 }
1267 ++NumLocalSplits;
1268
1269 return 0;
1270}

--- 62 unchanged lines hidden (view full) ---

1333unsigned RAGreedy::selectOrSplit(LiveInterval &VirtReg,
1334 SmallVectorImpl<LiveInterval*> &NewVRegs) {
1335 // First try assigning a free register.
1336 AllocationOrder Order(VirtReg.reg, *VRM, RegClassInfo);
1337 if (unsigned PhysReg = tryAssign(VirtReg, Order, NewVRegs))
1338 return PhysReg;
1339
1340 LiveRangeStage Stage = getStage(VirtReg);
1387 DEBUG(dbgs() << StageName[Stage] << '\n');
1341 DEBUG(dbgs() << StageName[Stage]
1342 << " Cascade " << ExtraRegInfo[VirtReg.reg].Cascade << '\n');
1388
1389 // Try to evict a less worthy live range, but only for ranges from the primary
1390 // queue. The RS_Second ranges already failed to do this, and they should not
1391 // get a second chance until they have been split.
1392 if (Stage != RS_Second)
1393 if (unsigned PhysReg = tryEvict(VirtReg, Order, NewVRegs))
1394 return PhysReg;
1395
1396 assert(NewVRegs.empty() && "Cannot append to existing NewVRegs");
1397
1398 // The first time we see a live range, don't try to split or spill.
1399 // Wait until the second time, when all smaller ranges have been allocated.
1400 // This gives a better picture of the interference to split around.
1401 if (Stage == RS_First) {
1343
1344 // Try to evict a less worthy live range, but only for ranges from the primary
1345 // queue. The RS_Second ranges already failed to do this, and they should not
1346 // get a second chance until they have been split.
1347 if (Stage != RS_Second)
1348 if (unsigned PhysReg = tryEvict(VirtReg, Order, NewVRegs))
1349 return PhysReg;
1350
1351 assert(NewVRegs.empty() && "Cannot append to existing NewVRegs");
1352
1353 // The first time we see a live range, don't try to split or spill.
1354 // Wait until the second time, when all smaller ranges have been allocated.
1355 // This gives a better picture of the interference to split around.
1356 if (Stage == RS_First) {
1402 LRStage[VirtReg.reg] = RS_Second;
1357 setStage(VirtReg, RS_Second);
1403 DEBUG(dbgs() << "wait for second round\n");
1404 NewVRegs.push_back(&VirtReg);
1405 return 0;
1406 }
1407
1408 // If we couldn't allocate a register from spilling, there is probably some
1409 // invalid inline assembly. The base class wil report it.
1358 DEBUG(dbgs() << "wait for second round\n");
1359 NewVRegs.push_back(&VirtReg);
1360 return 0;
1361 }
1362
1363 // If we couldn't allocate a register from spilling, there is probably some
1364 // invalid inline assembly. The base class wil report it.
1410 if (Stage >= RS_Spill)
1365 if (Stage >= RS_Spill || !VirtReg.isSpillable())
1411 return ~0u;
1412
1413 // Try splitting VirtReg or interferences.
1414 unsigned PhysReg = trySplit(VirtReg, Order, NewVRegs);
1415 if (PhysReg || !NewVRegs.empty())
1416 return PhysReg;
1417
1418 // Finally spill VirtReg itself.

--- 19 unchanged lines hidden (view full) ---

1438 if (VerifyEnabled)
1439 MF->verify(this, "Before greedy register allocator");
1440
1441 RegAllocBase::init(getAnalysis<VirtRegMap>(), getAnalysis<LiveIntervals>());
1442 Indexes = &getAnalysis<SlotIndexes>();
1443 DomTree = &getAnalysis<MachineDominatorTree>();
1444 SpillerInstance.reset(createInlineSpiller(*this, *MF, *VRM));
1445 Loops = &getAnalysis<MachineLoopInfo>();
1366 return ~0u;
1367
1368 // Try splitting VirtReg or interferences.
1369 unsigned PhysReg = trySplit(VirtReg, Order, NewVRegs);
1370 if (PhysReg || !NewVRegs.empty())
1371 return PhysReg;
1372
1373 // Finally spill VirtReg itself.

--- 19 unchanged lines hidden (view full) ---

1393 if (VerifyEnabled)
1394 MF->verify(this, "Before greedy register allocator");
1395
1396 RegAllocBase::init(getAnalysis<VirtRegMap>(), getAnalysis<LiveIntervals>());
1397 Indexes = &getAnalysis<SlotIndexes>();
1398 DomTree = &getAnalysis<MachineDominatorTree>();
1399 SpillerInstance.reset(createInlineSpiller(*this, *MF, *VRM));
1400 Loops = &getAnalysis<MachineLoopInfo>();
1446 LoopRanges = &getAnalysis<MachineLoopRanges>();
1447 Bundles = &getAnalysis<EdgeBundles>();
1448 SpillPlacer = &getAnalysis<SpillPlacement>();
1449 DebugVars = &getAnalysis<LiveDebugVariables>();
1450
1451 SA.reset(new SplitAnalysis(*VRM, *LIS, *Loops));
1452 SE.reset(new SplitEditor(*SA, *LIS, *VRM, *DomTree));
1401 Bundles = &getAnalysis<EdgeBundles>();
1402 SpillPlacer = &getAnalysis<SpillPlacement>();
1403 DebugVars = &getAnalysis<LiveDebugVariables>();
1404
1405 SA.reset(new SplitAnalysis(*VRM, *LIS, *Loops));
1406 SE.reset(new SplitEditor(*SA, *LIS, *VRM, *DomTree));
1453 LRStage.clear();
1454 LRStage.resize(MRI->getNumVirtRegs());
1407 ExtraRegInfo.clear();
1408 ExtraRegInfo.resize(MRI->getNumVirtRegs());
1409 NextCascade = 1;
1455 IntfCache.init(MF, &PhysReg2LiveUnion[0], Indexes, TRI);
1456
1457 allocatePhysRegs();
1458 addMBBLiveIns(MF);
1459 LIS->addKillFlags();
1460
1461 // Run rewriter
1462 {

--- 12 unchanged lines hidden --- 		1410 IntfCache.init(MF, &PhysReg2LiveUnion[0], Indexes, TRI);
1411
1412 allocatePhysRegs();
1413 addMBBLiveIns(MF);
1414 LIS->addKillFlags();
1415
1416 // Run rewriter
1417 {

--- 12 unchanged lines hidden ---