1 //===-- RegAllocGreedy.cpp - greedy register allocator --------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defines the RAGreedy function pass for register allocation in
13 //===----------------------------------------------------------------------===//
15 #define DEBUG_TYPE "regalloc"
16 #include "AllocationOrder.h"
17 #include "LiveIntervalUnion.h"
18 #include "LiveRangeEdit.h"
19 #include "RegAllocBase.h"
21 #include "SpillPlacement.h"
23 #include "VirtRegMap.h"
24 #include "VirtRegRewriter.h"
25 #include "llvm/Analysis/AliasAnalysis.h"
26 #include "llvm/Function.h"
27 #include "llvm/PassAnalysisSupport.h"
28 #include "llvm/CodeGen/CalcSpillWeights.h"
29 #include "llvm/CodeGen/EdgeBundles.h"
30 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
31 #include "llvm/CodeGen/LiveStackAnalysis.h"
32 #include "llvm/CodeGen/MachineDominators.h"
33 #include "llvm/CodeGen/MachineFunctionPass.h"
34 #include "llvm/CodeGen/MachineLoopInfo.h"
35 #include "llvm/CodeGen/MachineLoopRanges.h"
36 #include "llvm/CodeGen/MachineRegisterInfo.h"
37 #include "llvm/CodeGen/Passes.h"
38 #include "llvm/CodeGen/RegAllocRegistry.h"
39 #include "llvm/CodeGen/RegisterCoalescer.h"
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"
48 static RegisterRegAlloc
greedyRegAlloc("greedy", "greedy register allocator",
49 createGreedyRegisterAllocator
);
52 class RAGreedy
: public MachineFunctionPass
, public RegAllocBase
{
55 BitVector ReservedRegs
;
60 MachineDominatorTree
*DomTree
;
61 MachineLoopInfo
*Loops
;
62 MachineLoopRanges
*LoopRanges
;
64 SpillPlacement
*SpillPlacer
;
67 std::auto_ptr
<Spiller
> SpillerInstance
;
68 std::auto_ptr
<SplitAnalysis
> SA
;
72 /// All basic blocks where the current register is live.
73 SmallVector
<SpillPlacement::BlockConstraint
, 8> SpillConstraints
;
75 /// Additional information about basic blocks where the current variable is
76 /// live. Such a block will look like one of these templates:
78 /// 1. | o---x | Internal to block. Variable is only live in this block.
79 /// 2. |---x | Live-in, kill.
80 /// 3. | o---| Def, live-out.
81 /// 4. |---x o---| Live-in, kill, def, live-out.
82 /// 5. |---o---o---| Live-through with uses or defs.
83 /// 6. |-----------| Live-through without uses. Transparent.
86 MachineBasicBlock
*MBB
;
87 SlotIndex FirstUse
; ///< First instr using current reg.
88 SlotIndex LastUse
; ///< Last instr using current reg.
89 SlotIndex Kill
; ///< Interval end point inside block.
90 SlotIndex Def
; ///< Interval start point inside block.
91 /// Last possible point for splitting live ranges.
92 SlotIndex LastSplitPoint
;
93 bool Uses
; ///< Current reg has uses or defs in block.
94 bool LiveThrough
; ///< Live in whole block (Templ 5. or 6. above).
95 bool LiveIn
; ///< Current reg is live in.
96 bool LiveOut
; ///< Current reg is live out.
98 // Per-interference pattern scratch data.
99 bool OverlapEntry
; ///< Interference overlaps entering interval.
100 bool OverlapExit
; ///< Interference overlaps exiting interval.
103 /// Basic blocks where var is live. This array is parallel to
104 /// SpillConstraints.
105 SmallVector
<BlockInfo
, 8> LiveBlocks
;
110 /// Return the pass name.
111 virtual const char* getPassName() const {
112 return "Greedy Register Allocator";
115 /// RAGreedy analysis usage.
116 virtual void getAnalysisUsage(AnalysisUsage
&AU
) const;
118 virtual void releaseMemory();
120 virtual Spiller
&spiller() { return *SpillerInstance
; }
122 virtual float getPriority(LiveInterval
*LI
);
124 virtual unsigned selectOrSplit(LiveInterval
&,
125 SmallVectorImpl
<LiveInterval
*>&);
127 /// Perform register allocation.
128 virtual bool runOnMachineFunction(MachineFunction
&mf
);
133 bool checkUncachedInterference(LiveInterval
&, unsigned);
134 LiveInterval
*getSingleInterference(LiveInterval
&, unsigned);
135 bool reassignVReg(LiveInterval
&InterferingVReg
, unsigned OldPhysReg
);
136 float calcInterferenceWeight(LiveInterval
&, unsigned);
137 void calcLiveBlockInfo(LiveInterval
&);
138 float calcInterferenceInfo(LiveInterval
&, unsigned);
139 float calcGlobalSplitCost(const BitVector
&);
140 void splitAroundRegion(LiveInterval
&, unsigned, const BitVector
&,
141 SmallVectorImpl
<LiveInterval
*>&);
143 unsigned tryReassignOrEvict(LiveInterval
&, AllocationOrder
&,
144 SmallVectorImpl
<LiveInterval
*>&);
145 unsigned tryRegionSplit(LiveInterval
&, AllocationOrder
&,
146 SmallVectorImpl
<LiveInterval
*>&);
147 unsigned trySplit(LiveInterval
&, AllocationOrder
&,
148 SmallVectorImpl
<LiveInterval
*>&);
149 unsigned trySpillInterferences(LiveInterval
&, AllocationOrder
&,
150 SmallVectorImpl
<LiveInterval
*>&);
152 } // end anonymous namespace
154 char RAGreedy::ID
= 0;
156 FunctionPass
* llvm::createGreedyRegisterAllocator() {
157 return new RAGreedy();
160 RAGreedy::RAGreedy(): MachineFunctionPass(ID
) {
161 initializeSlotIndexesPass(*PassRegistry::getPassRegistry());
162 initializeLiveIntervalsPass(*PassRegistry::getPassRegistry());
163 initializeSlotIndexesPass(*PassRegistry::getPassRegistry());
164 initializeStrongPHIEliminationPass(*PassRegistry::getPassRegistry());
165 initializeRegisterCoalescerAnalysisGroup(*PassRegistry::getPassRegistry());
166 initializeCalculateSpillWeightsPass(*PassRegistry::getPassRegistry());
167 initializeLiveStacksPass(*PassRegistry::getPassRegistry());
168 initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry());
169 initializeMachineLoopInfoPass(*PassRegistry::getPassRegistry());
170 initializeMachineLoopRangesPass(*PassRegistry::getPassRegistry());
171 initializeVirtRegMapPass(*PassRegistry::getPassRegistry());
172 initializeEdgeBundlesPass(*PassRegistry::getPassRegistry());
173 initializeSpillPlacementPass(*PassRegistry::getPassRegistry());
176 void RAGreedy::getAnalysisUsage(AnalysisUsage
&AU
) const {
177 AU
.setPreservesCFG();
178 AU
.addRequired
<AliasAnalysis
>();
179 AU
.addPreserved
<AliasAnalysis
>();
180 AU
.addRequired
<LiveIntervals
>();
181 AU
.addRequired
<SlotIndexes
>();
182 AU
.addPreserved
<SlotIndexes
>();
184 AU
.addRequiredID(StrongPHIEliminationID
);
185 AU
.addRequiredTransitive
<RegisterCoalescer
>();
186 AU
.addRequired
<CalculateSpillWeights
>();
187 AU
.addRequired
<LiveStacks
>();
188 AU
.addPreserved
<LiveStacks
>();
189 AU
.addRequired
<MachineDominatorTree
>();
190 AU
.addPreserved
<MachineDominatorTree
>();
191 AU
.addRequired
<MachineLoopInfo
>();
192 AU
.addPreserved
<MachineLoopInfo
>();
193 AU
.addRequired
<MachineLoopRanges
>();
194 AU
.addPreserved
<MachineLoopRanges
>();
195 AU
.addRequired
<VirtRegMap
>();
196 AU
.addPreserved
<VirtRegMap
>();
197 AU
.addRequired
<EdgeBundles
>();
198 AU
.addRequired
<SpillPlacement
>();
199 MachineFunctionPass::getAnalysisUsage(AU
);
202 void RAGreedy::releaseMemory() {
203 SpillerInstance
.reset(0);
204 RegAllocBase::releaseMemory();
207 float RAGreedy::getPriority(LiveInterval
*LI
) {
208 float Priority
= LI
->weight
;
210 // Prioritize hinted registers so they are allocated first.
211 std::pair
<unsigned, unsigned> Hint
;
212 if (Hint
.first
|| Hint
.second
) {
213 // The hint can be target specific, a virtual register, or a physreg.
216 // Prefer physreg hints above anything else.
217 if (Hint
.first
== 0 && TargetRegisterInfo::isPhysicalRegister(Hint
.second
))
224 //===----------------------------------------------------------------------===//
225 // Register Reassignment
226 //===----------------------------------------------------------------------===//
228 // Check interference without using the cache.
229 bool RAGreedy::checkUncachedInterference(LiveInterval
&VirtReg
,
231 for (const unsigned *AliasI
= TRI
->getOverlaps(PhysReg
); *AliasI
; ++AliasI
) {
232 LiveIntervalUnion::Query
subQ(&VirtReg
, &PhysReg2LiveUnion
[*AliasI
]);
233 if (subQ
.checkInterference())
239 /// getSingleInterference - Return the single interfering virtual register
240 /// assigned to PhysReg. Return 0 if more than one virtual register is
242 LiveInterval
*RAGreedy::getSingleInterference(LiveInterval
&VirtReg
,
244 // Check physreg and aliases.
245 LiveInterval
*Interference
= 0;
246 for (const unsigned *AliasI
= TRI
->getOverlaps(PhysReg
); *AliasI
; ++AliasI
) {
247 LiveIntervalUnion::Query
&Q
= query(VirtReg
, *AliasI
);
248 if (Q
.checkInterference()) {
251 Q
.collectInterferingVRegs(1);
252 if (!Q
.seenAllInterferences())
254 Interference
= Q
.interferingVRegs().front();
260 // Attempt to reassign this virtual register to a different physical register.
262 // FIXME: we are not yet caching these "second-level" interferences discovered
263 // in the sub-queries. These interferences can change with each call to
264 // selectOrSplit. However, we could implement a "may-interfere" cache that
265 // could be conservatively dirtied when we reassign or split.
267 // FIXME: This may result in a lot of alias queries. We could summarize alias
268 // live intervals in their parent register's live union, but it's messy.
269 bool RAGreedy::reassignVReg(LiveInterval
&InterferingVReg
,
270 unsigned WantedPhysReg
) {
271 assert(TargetRegisterInfo::isVirtualRegister(InterferingVReg
.reg
) &&
272 "Can only reassign virtual registers");
273 assert(TRI
->regsOverlap(WantedPhysReg
, VRM
->getPhys(InterferingVReg
.reg
)) &&
274 "inconsistent phys reg assigment");
276 AllocationOrder
Order(InterferingVReg
.reg
, *VRM
, ReservedRegs
);
277 while (unsigned PhysReg
= Order
.next()) {
278 // Don't reassign to a WantedPhysReg alias.
279 if (TRI
->regsOverlap(PhysReg
, WantedPhysReg
))
282 if (checkUncachedInterference(InterferingVReg
, PhysReg
))
285 // Reassign the interfering virtual reg to this physical reg.
286 unsigned OldAssign
= VRM
->getPhys(InterferingVReg
.reg
);
287 DEBUG(dbgs() << "reassigning: " << InterferingVReg
<< " from " <<
288 TRI
->getName(OldAssign
) << " to " << TRI
->getName(PhysReg
) << '\n');
289 unassign(InterferingVReg
, OldAssign
);
290 assign(InterferingVReg
, PhysReg
);
296 /// tryReassignOrEvict - Try to reassign a single interferences to a different
297 /// physreg, or evict a single interference with a lower spill weight.
298 /// @param VirtReg Currently unassigned virtual register.
299 /// @param Order Physregs to try.
300 /// @return Physreg to assign VirtReg, or 0.
301 unsigned RAGreedy::tryReassignOrEvict(LiveInterval
&VirtReg
,
302 AllocationOrder
&Order
,
303 SmallVectorImpl
<LiveInterval
*> &NewVRegs
){
304 NamedRegionTimer
T("Reassign", TimerGroupName
, TimePassesIsEnabled
);
306 // Keep track of the lightest single interference seen so far.
307 float BestWeight
= VirtReg
.weight
;
308 LiveInterval
*BestVirt
= 0;
309 unsigned BestPhys
= 0;
312 while (unsigned PhysReg
= Order
.next()) {
313 LiveInterval
*InterferingVReg
= getSingleInterference(VirtReg
, PhysReg
);
314 if (!InterferingVReg
)
316 if (TargetRegisterInfo::isPhysicalRegister(InterferingVReg
->reg
))
318 if (reassignVReg(*InterferingVReg
, PhysReg
))
321 // Cannot reassign, is this an eviction candidate?
322 if (InterferingVReg
->weight
< BestWeight
) {
323 BestVirt
= InterferingVReg
;
325 BestWeight
= InterferingVReg
->weight
;
329 // Nothing reassigned, can we evict a lighter single interference?
331 DEBUG(dbgs() << "evicting lighter " << *BestVirt
<< '\n');
332 unassign(*BestVirt
, VRM
->getPhys(BestVirt
->reg
));
333 NewVRegs
.push_back(BestVirt
);
341 //===----------------------------------------------------------------------===//
343 //===----------------------------------------------------------------------===//
345 /// calcLiveBlockInfo - Fill the LiveBlocks array with information about blocks
346 /// where VirtReg is live.
347 /// The SpillConstraints array is minimally initialized with MBB->getNumber().
348 void RAGreedy::calcLiveBlockInfo(LiveInterval
&VirtReg
) {
350 SpillConstraints
.clear();
352 assert(!VirtReg
.empty() && "Cannot allocate an empty interval");
353 LiveInterval::const_iterator LVI
= VirtReg
.begin();
354 LiveInterval::const_iterator LVE
= VirtReg
.end();
356 SmallVectorImpl
<SlotIndex
>::const_iterator UseI
, UseE
;
357 UseI
= SA
->UseSlots
.begin();
358 UseE
= SA
->UseSlots
.end();
360 // Loop over basic blocks where VirtReg is live.
361 MachineFunction::iterator MFI
= Indexes
->getMBBFromIndex(LVI
->start
);
363 // Block constraints depend on the interference pattern.
364 // Just allocate them here, don't compute anything.
365 SpillPlacement::BlockConstraint BC
;
366 BC
.Number
= MFI
->getNumber();
367 SpillConstraints
.push_back(BC
);
371 SlotIndex Start
, Stop
;
372 tie(Start
, Stop
) = Indexes
->getMBBRange(BI
.MBB
);
374 // The last split point is the latest possible insertion point that dominates
375 // all successor blocks. If interference reaches LastSplitPoint, it is not
376 // possible to insert a split or reload that makes VirtReg live in the
378 MachineBasicBlock::iterator LSP
= LIS
->getLastSplitPoint(VirtReg
, BI
.MBB
);
379 if (LSP
== BI
.MBB
->end())
380 BI
.LastSplitPoint
= Stop
;
382 BI
.LastSplitPoint
= Indexes
->getInstructionIndex(LSP
);
384 // LVI is the first live segment overlapping MBB.
385 BI
.LiveIn
= LVI
->start
<= Start
;
389 // Find the first and last uses in the block.
390 BI
.Uses
= SA
->hasUses(MFI
);
391 if (BI
.Uses
&& UseI
!= UseE
) {
393 assert(BI
.FirstUse
>= Start
);
395 while (UseI
!= UseE
&& *UseI
< Stop
);
396 BI
.LastUse
= UseI
[-1];
397 assert(BI
.LastUse
< Stop
);
400 // Look for gaps in the live range.
403 while (LVI
->end
< Stop
) {
404 SlotIndex LastStop
= LVI
->end
;
405 if (++LVI
== LVE
|| LVI
->start
>= Stop
) {
410 if (LastStop
< LVI
->start
) {
417 // Don't set LiveThrough when the block has a gap.
418 BI
.LiveThrough
= !hasGap
&& BI
.LiveIn
&& BI
.LiveOut
;
419 LiveBlocks
.push_back(BI
);
421 // LVI is now at LVE or LVI->end >= Stop.
425 // Live segment ends exactly at Stop. Move to the next segment.
426 if (LVI
->end
== Stop
&& ++LVI
== LVE
)
429 // Pick the next basic block.
430 if (LVI
->start
< Stop
)
433 MFI
= Indexes
->getMBBFromIndex(LVI
->start
);
437 /// calcInterferenceInfo - Compute per-block outgoing and ingoing constraints
438 /// when considering interference from PhysReg. Also compute an optimistic local
439 /// cost of this interference pattern.
441 /// The final cost of a split is the local cost + global cost of preferences
442 /// broken by SpillPlacement.
444 float RAGreedy::calcInterferenceInfo(LiveInterval
&VirtReg
, unsigned PhysReg
) {
445 // Reset interference dependent info.
446 for (unsigned i
= 0, e
= LiveBlocks
.size(); i
!= e
; ++i
) {
447 BlockInfo
&BI
= LiveBlocks
[i
];
448 SpillPlacement::BlockConstraint
&BC
= SpillConstraints
[i
];
449 BC
.Entry
= (BI
.Uses
&& BI
.LiveIn
) ?
450 SpillPlacement::PrefReg
: SpillPlacement::DontCare
;
451 BC
.Exit
= (BI
.Uses
&& BI
.LiveOut
) ?
452 SpillPlacement::PrefReg
: SpillPlacement::DontCare
;
453 BI
.OverlapEntry
= BI
.OverlapExit
= false;
456 // Add interference info from each PhysReg alias.
457 for (const unsigned *AI
= TRI
->getOverlaps(PhysReg
); *AI
; ++AI
) {
458 if (!query(VirtReg
, *AI
).checkInterference())
460 LiveIntervalUnion::SegmentIter IntI
=
461 PhysReg2LiveUnion
[*AI
].find(VirtReg
.beginIndex());
465 // Determine which blocks have interference live in or after the last split
467 for (unsigned i
= 0, e
= LiveBlocks
.size(); i
!= e
; ++i
) {
468 BlockInfo
&BI
= LiveBlocks
[i
];
469 SpillPlacement::BlockConstraint
&BC
= SpillConstraints
[i
];
470 SlotIndex Start
, Stop
;
471 tie(Start
, Stop
) = Indexes
->getMBBRange(BI
.MBB
);
473 // Skip interference-free blocks.
474 if (IntI
.start() >= Stop
)
477 // Is the interference live-in?
479 IntI
.advanceTo(Start
);
482 if (IntI
.start() <= Start
)
483 BC
.Entry
= SpillPlacement::MustSpill
;
486 // Is the interference overlapping the last split point?
488 if (IntI
.stop() < BI
.LastSplitPoint
)
489 IntI
.advanceTo(BI
.LastSplitPoint
.getPrevSlot());
492 if (IntI
.start() < Stop
)
493 BC
.Exit
= SpillPlacement::MustSpill
;
497 // Rewind iterator and check other interferences.
498 IntI
.find(VirtReg
.beginIndex());
499 for (unsigned i
= 0, e
= LiveBlocks
.size(); i
!= e
; ++i
) {
500 BlockInfo
&BI
= LiveBlocks
[i
];
501 SpillPlacement::BlockConstraint
&BC
= SpillConstraints
[i
];
502 SlotIndex Start
, Stop
;
503 tie(Start
, Stop
) = Indexes
->getMBBRange(BI
.MBB
);
505 // Skip interference-free blocks.
506 if (IntI
.start() >= Stop
)
509 // Handle transparent blocks with interference separately.
510 // Transparent blocks never incur any fixed cost.
511 if (BI
.LiveThrough
&& !BI
.Uses
) {
512 IntI
.advanceTo(Start
);
515 if (IntI
.start() >= Stop
)
518 if (BC
.Entry
!= SpillPlacement::MustSpill
)
519 BC
.Entry
= SpillPlacement::PrefSpill
;
520 if (BC
.Exit
!= SpillPlacement::MustSpill
)
521 BC
.Exit
= SpillPlacement::PrefSpill
;
525 // Now we only have blocks with uses left.
526 // Check if the interference overlaps the uses.
527 assert(BI
.Uses
&& "Non-transparent block without any uses");
529 // Check interference on entry.
530 if (BI
.LiveIn
&& BC
.Entry
!= SpillPlacement::MustSpill
) {
531 IntI
.advanceTo(Start
);
534 // Not live in, but before the first use.
535 if (IntI
.start() < BI
.FirstUse
)
536 BC
.Entry
= SpillPlacement::PrefSpill
;
539 // Does interference overlap the uses in the entry segment
541 if (BI
.LiveIn
&& !BI
.OverlapEntry
) {
542 IntI
.advanceTo(BI
.FirstUse
);
545 // A live-through interval has no kill.
546 // Check [FirstUse;LastUse) instead.
547 if (IntI
.start() < (BI
.LiveThrough
? BI
.LastUse
: BI
.Kill
))
548 BI
.OverlapEntry
= true;
551 // Does interference overlap the uses in the exit segment [Def;LastUse)?
552 if (BI
.LiveOut
&& !BI
.LiveThrough
&& !BI
.OverlapExit
) {
553 IntI
.advanceTo(BI
.Def
);
556 if (IntI
.start() < BI
.LastUse
)
557 BI
.OverlapExit
= true;
560 // Check interference on exit.
561 if (BI
.LiveOut
&& BC
.Exit
!= SpillPlacement::MustSpill
) {
562 // Check interference between LastUse and Stop.
563 if (BC
.Exit
!= SpillPlacement::PrefSpill
) {
564 IntI
.advanceTo(BI
.LastUse
);
567 if (IntI
.start() < Stop
)
568 BC
.Exit
= SpillPlacement::PrefSpill
;
574 // Accumulate a local cost of this interference pattern.
576 for (unsigned i
= 0, e
= LiveBlocks
.size(); i
!= e
; ++i
) {
577 BlockInfo
&BI
= LiveBlocks
[i
];
580 SpillPlacement::BlockConstraint
&BC
= SpillConstraints
[i
];
581 unsigned Inserts
= 0;
583 // Do we need spill code for the entry segment?
585 Inserts
+= BI
.OverlapEntry
|| BC
.Entry
!= SpillPlacement::PrefReg
;
587 // For the exit segment?
589 Inserts
+= BI
.OverlapExit
|| BC
.Exit
!= SpillPlacement::PrefReg
;
591 // The local cost of spill code in this block is the block frequency times
592 // the number of spill instructions inserted.
594 LocalCost
+= Inserts
* SpillPlacer
->getBlockFrequency(BI
.MBB
);
596 DEBUG(dbgs() << "Local cost of " << PrintReg(PhysReg
, TRI
) << " = "
597 << LocalCost
<< '\n');
601 /// calcGlobalSplitCost - Return the global split cost of following the split
602 /// pattern in LiveBundles. This cost should be added to the local cost of the
603 /// interference pattern in SpillConstraints.
605 float RAGreedy::calcGlobalSplitCost(const BitVector
&LiveBundles
) {
606 float GlobalCost
= 0;
607 for (unsigned i
= 0, e
= LiveBlocks
.size(); i
!= e
; ++i
) {
608 SpillPlacement::BlockConstraint
&BC
= SpillConstraints
[i
];
609 unsigned Inserts
= 0;
610 // Broken entry preference?
611 Inserts
+= LiveBundles
[Bundles
->getBundle(BC
.Number
, 0)] !=
612 (BC
.Entry
== SpillPlacement::PrefReg
);
613 // Broken exit preference?
614 Inserts
+= LiveBundles
[Bundles
->getBundle(BC
.Number
, 1)] !=
615 (BC
.Exit
== SpillPlacement::PrefReg
);
617 GlobalCost
+= Inserts
* SpillPlacer
->getBlockFrequency(LiveBlocks
[i
].MBB
);
619 DEBUG(dbgs() << "Global cost = " << GlobalCost
<< '\n');
623 /// splitAroundRegion - Split VirtReg around the region determined by
624 /// LiveBundles. Make an effort to avoid interference from PhysReg.
626 /// The 'register' interval is going to contain as many uses as possible while
627 /// avoiding interference. The 'stack' interval is the complement constructed by
628 /// SplitEditor. It will contain the rest.
630 void RAGreedy::splitAroundRegion(LiveInterval
&VirtReg
, unsigned PhysReg
,
631 const BitVector
&LiveBundles
,
632 SmallVectorImpl
<LiveInterval
*> &NewVRegs
) {
634 dbgs() << "Splitting around region for " << PrintReg(PhysReg
, TRI
)
636 for (int i
= LiveBundles
.find_first(); i
>=0; i
= LiveBundles
.find_next(i
))
637 dbgs() << " EB#" << i
;
641 // First compute interference ranges in the live blocks.
642 typedef std::pair
<SlotIndex
, SlotIndex
> IndexPair
;
643 SmallVector
<IndexPair
, 8> InterferenceRanges
;
644 InterferenceRanges
.resize(LiveBlocks
.size());
645 for (const unsigned *AI
= TRI
->getOverlaps(PhysReg
); *AI
; ++AI
) {
646 if (!query(VirtReg
, *AI
).checkInterference())
648 LiveIntervalUnion::SegmentIter IntI
=
649 PhysReg2LiveUnion
[*AI
].find(VirtReg
.beginIndex());
652 for (unsigned i
= 0, e
= LiveBlocks
.size(); i
!= e
; ++i
) {
653 const BlockInfo
&BI
= LiveBlocks
[i
];
654 IndexPair
&IP
= InterferenceRanges
[i
];
655 SlotIndex Start
, Stop
;
656 tie(Start
, Stop
) = Indexes
->getMBBRange(BI
.MBB
);
657 // Skip interference-free blocks.
658 if (IntI
.start() >= Stop
)
661 // First interference in block.
663 IntI
.advanceTo(Start
);
666 if (IntI
.start() >= Stop
)
668 if (!IP
.first
.isValid() || IntI
.start() < IP
.first
)
669 IP
.first
= IntI
.start();
672 // Last interference in block.
674 IntI
.advanceTo(Stop
);
675 if (!IntI
.valid() || IntI
.start() >= Stop
)
677 if (IntI
.stop() <= Start
)
679 if (!IP
.second
.isValid() || IntI
.stop() > IP
.second
)
680 IP
.second
= IntI
.stop();
685 SmallVector
<LiveInterval
*, 4> SpillRegs
;
686 LiveRangeEdit
LREdit(VirtReg
, NewVRegs
, SpillRegs
);
687 SplitEditor
SE(*SA
, *LIS
, *VRM
, *DomTree
, LREdit
);
689 // Create the main cross-block interval.
692 // First add all defs that are live out of a block.
693 for (unsigned i
= 0, e
= LiveBlocks
.size(); i
!= e
; ++i
) {
694 BlockInfo
&BI
= LiveBlocks
[i
];
695 bool RegIn
= LiveBundles
[Bundles
->getBundle(BI
.MBB
->getNumber(), 0)];
696 bool RegOut
= LiveBundles
[Bundles
->getBundle(BI
.MBB
->getNumber(), 1)];
698 // Should the register be live out?
699 if (!BI
.LiveOut
|| !RegOut
)
702 IndexPair
&IP
= InterferenceRanges
[i
];
703 SlotIndex Start
, Stop
;
704 tie(Start
, Stop
) = Indexes
->getMBBRange(BI
.MBB
);
706 DEBUG(dbgs() << "BB#" << BI
.MBB
->getNumber() << " -> EB#"
707 << Bundles
->getBundle(BI
.MBB
->getNumber(), 1)
708 << " intf [" << IP
.first
<< ';' << IP
.second
<< ')');
710 // The interference interval should either be invalid or overlap MBB.
711 assert((!IP
.first
.isValid() || IP
.first
< Stop
) && "Bad interference");
712 assert((!IP
.second
.isValid() || IP
.second
> Start
) && "Bad interference");
714 // Check interference leaving the block.
715 if (!IP
.second
.isValid()) {
716 // Block is interference-free.
717 DEBUG(dbgs() << ", no interference");
719 assert(BI
.LiveThrough
&& "No uses, but not live through block?");
720 // Block is live-through without interference.
721 DEBUG(dbgs() << ", no uses"
722 << (RegIn
? ", live-through.\n" : ", stack in.\n"));
724 SE
.enterIntvAtEnd(*BI
.MBB
);
727 if (!BI
.LiveThrough
) {
728 DEBUG(dbgs() << ", not live-through.\n");
729 SE
.useIntv(SE
.enterIntvBefore(BI
.Def
), Stop
);
733 // Block is live-through, but entry bundle is on the stack.
734 // Reload just before the first use.
735 DEBUG(dbgs() << ", not live-in, enter before first use.\n");
736 SE
.useIntv(SE
.enterIntvBefore(BI
.FirstUse
), Stop
);
739 DEBUG(dbgs() << ", live-through.\n");
743 // Block has interference.
744 DEBUG(dbgs() << ", interference to " << IP
.second
);
746 if (!BI
.LiveThrough
&& IP
.second
<= BI
.Def
) {
747 // The interference doesn't reach the outgoing segment.
748 DEBUG(dbgs() << " doesn't affect def from " << BI
.Def
<< '\n');
749 SE
.useIntv(BI
.Def
, Stop
);
755 // No uses in block, avoid interference by reloading as late as possible.
756 DEBUG(dbgs() << ", no uses.\n");
757 SlotIndex SegStart
= SE
.enterIntvAtEnd(*BI
.MBB
);
758 assert(SegStart
>= IP
.second
&& "Couldn't avoid interference");
762 if (IP
.second
.getBoundaryIndex() < BI
.LastUse
) {
763 // There are interference-free uses at the end of the block.
764 // Find the first use that can get the live-out register.
765 SmallVectorImpl
<SlotIndex
>::const_iterator UI
=
766 std::lower_bound(SA
->UseSlots
.begin(), SA
->UseSlots
.end(),
767 IP
.second
.getBoundaryIndex());
768 assert(UI
!= SA
->UseSlots
.end() && "Couldn't find last use");
770 assert(Use
<= BI
.LastUse
&& "Couldn't find last use");
771 // Only attempt a split befroe the last split point.
772 if (Use
.getBaseIndex() <= BI
.LastSplitPoint
) {
773 DEBUG(dbgs() << ", free use at " << Use
<< ".\n");
774 SlotIndex SegStart
= SE
.enterIntvBefore(Use
);
775 assert(SegStart
>= IP
.second
&& "Couldn't avoid interference");
776 assert(SegStart
< BI
.LastSplitPoint
&& "Impossible split point");
777 SE
.useIntv(SegStart
, Stop
);
782 // Interference is after the last use.
783 DEBUG(dbgs() << " after last use.\n");
784 SlotIndex SegStart
= SE
.enterIntvAtEnd(*BI
.MBB
);
785 assert(SegStart
>= IP
.second
&& "Couldn't avoid interference");
788 // Now all defs leading to live bundles are handled, do everything else.
789 for (unsigned i
= 0, e
= LiveBlocks
.size(); i
!= e
; ++i
) {
790 BlockInfo
&BI
= LiveBlocks
[i
];
791 bool RegIn
= LiveBundles
[Bundles
->getBundle(BI
.MBB
->getNumber(), 0)];
792 bool RegOut
= LiveBundles
[Bundles
->getBundle(BI
.MBB
->getNumber(), 1)];
794 // Is the register live-in?
795 if (!BI
.LiveIn
|| !RegIn
)
798 // We have an incoming register. Check for interference.
799 IndexPair
&IP
= InterferenceRanges
[i
];
800 SlotIndex Start
, Stop
;
801 tie(Start
, Stop
) = Indexes
->getMBBRange(BI
.MBB
);
803 DEBUG(dbgs() << "EB#" << Bundles
->getBundle(BI
.MBB
->getNumber(), 0)
804 << " -> BB#" << BI
.MBB
->getNumber());
806 // Check interference entering the block.
807 if (!IP
.first
.isValid()) {
808 // Block is interference-free.
809 DEBUG(dbgs() << ", no interference");
811 assert(BI
.LiveThrough
&& "No uses, but not live through block?");
812 // Block is live-through without interference.
814 DEBUG(dbgs() << ", no uses, live-through.\n");
815 SE
.useIntv(Start
, Stop
);
817 DEBUG(dbgs() << ", no uses, stack-out.\n");
818 SE
.leaveIntvAtTop(*BI
.MBB
);
822 if (!BI
.LiveThrough
) {
823 DEBUG(dbgs() << ", killed in block.\n");
824 SE
.useIntv(Start
, SE
.leaveIntvAfter(BI
.Kill
));
828 // Block is live-through, but exit bundle is on the stack.
829 // Spill immediately after the last use.
830 if (BI
.LastUse
< BI
.LastSplitPoint
) {
831 DEBUG(dbgs() << ", uses, stack-out.\n");
832 SE
.useIntv(Start
, SE
.leaveIntvAfter(BI
.LastUse
));
835 // The last use is after the last split point, it is probably an
837 DEBUG(dbgs() << ", uses at " << BI
.LastUse
<< " after split point "
838 << BI
.LastSplitPoint
<< ", stack-out.\n");
840 // Find the last real instruction before the split point.
841 MachineBasicBlock::iterator SplitI
=
842 LIS
->getInstructionFromIndex(BI
.LastSplitPoint
);
843 MachineBasicBlock::iterator I
= SplitI
, B
= BI
.MBB
->begin();
844 while (I
!= B
&& (--I
)->isDebugValue())
847 SegEnd
= SE
.leaveIntvAtTop(*BI
.MBB
);
849 SegEnd
= SE
.leaveIntvAfter(LIS
->getInstructionIndex(I
));
850 SE
.useIntv(Start
, SegEnd
);
852 // Run a double interval from the split to the last use.
853 // This makes it possible to spill the complement without affecting the
855 SE
.overlapIntv(SegEnd
, BI
.LastUse
);
858 // Register is live-through.
859 DEBUG(dbgs() << ", uses, live-through.\n");
860 SE
.useIntv(Start
, Stop
);
864 // Block has interference.
865 DEBUG(dbgs() << ", interference from " << IP
.first
);
867 if (!BI
.LiveThrough
&& IP
.first
>= BI
.Kill
) {
868 // The interference doesn't reach the outgoing segment.
869 DEBUG(dbgs() << " doesn't affect kill at " << BI
.Kill
<< '\n');
870 SE
.useIntv(Start
, BI
.Kill
);
875 // No uses in block, avoid interference by spilling as soon as possible.
876 DEBUG(dbgs() << ", no uses.\n");
877 SlotIndex SegEnd
= SE
.leaveIntvAtTop(*BI
.MBB
);
878 assert(SegEnd
<= IP
.first
&& "Couldn't avoid interference");
881 if (IP
.first
.getBaseIndex() > BI
.FirstUse
) {
882 // There are interference-free uses at the beginning of the block.
883 // Find the last use that can get the register.
884 SmallVectorImpl
<SlotIndex
>::const_iterator UI
=
885 std::lower_bound(SA
->UseSlots
.begin(), SA
->UseSlots
.end(),
886 IP
.first
.getBaseIndex());
887 assert(UI
!= SA
->UseSlots
.begin() && "Couldn't find first use");
888 SlotIndex Use
= (--UI
)->getBoundaryIndex();
889 DEBUG(dbgs() << ", free use at " << *UI
<< ".\n");
890 SlotIndex SegEnd
= SE
.leaveIntvAfter(Use
);
891 assert(SegEnd
<= IP
.first
&& "Couldn't avoid interference");
892 SE
.useIntv(Start
, SegEnd
);
896 // Interference is before the first use.
897 DEBUG(dbgs() << " before first use.\n");
898 SlotIndex SegEnd
= SE
.leaveIntvAtTop(*BI
.MBB
);
899 assert(SegEnd
<= IP
.first
&& "Couldn't avoid interference");
904 // FIXME: Should we be more aggressive about splitting the stack region into
905 // per-block segments? The current approach allows the stack region to
906 // separate into connected components. Some components may be allocatable.
910 MF
->verify(this, "After splitting live range around region");
913 // Make sure that at least one of the new intervals can allocate to PhysReg.
914 // That was the whole point of splitting the live range.
916 for (LiveRangeEdit::iterator I
= LREdit
.begin(), E
= LREdit
.end(); I
!= E
;
918 if (!checkUncachedInterference(**I
, PhysReg
)) {
922 assert(found
&& "No allocatable intervals after pointless splitting");
927 unsigned RAGreedy::tryRegionSplit(LiveInterval
&VirtReg
, AllocationOrder
&Order
,
928 SmallVectorImpl
<LiveInterval
*> &NewVRegs
) {
929 calcLiveBlockInfo(VirtReg
);
930 BitVector LiveBundles
, BestBundles
;
932 unsigned BestReg
= 0;
934 while (unsigned PhysReg
= Order
.next()) {
935 float Cost
= calcInterferenceInfo(VirtReg
, PhysReg
);
936 if (BestReg
&& Cost
>= BestCost
)
939 SpillPlacer
->placeSpills(SpillConstraints
, LiveBundles
);
940 // No live bundles, defer to splitSingleBlocks().
941 if (!LiveBundles
.any())
944 Cost
+= calcGlobalSplitCost(LiveBundles
);
945 if (!BestReg
|| Cost
< BestCost
) {
948 BestBundles
.swap(LiveBundles
);
955 splitAroundRegion(VirtReg
, BestReg
, BestBundles
, NewVRegs
);
960 //===----------------------------------------------------------------------===//
961 // Live Range Splitting
962 //===----------------------------------------------------------------------===//
964 /// trySplit - Try to split VirtReg or one of its interferences, making it
966 /// @return Physreg when VirtReg may be assigned and/or new NewVRegs.
967 unsigned RAGreedy::trySplit(LiveInterval
&VirtReg
, AllocationOrder
&Order
,
968 SmallVectorImpl
<LiveInterval
*>&NewVRegs
) {
969 NamedRegionTimer
T("Splitter", TimerGroupName
, TimePassesIsEnabled
);
970 SA
->analyze(&VirtReg
);
972 // Don't attempt splitting on local intervals for now. TBD.
973 if (LIS
->intervalIsInOneMBB(VirtReg
))
976 // First try to split around a region spanning multiple blocks.
977 unsigned PhysReg
= tryRegionSplit(VirtReg
, Order
, NewVRegs
);
978 if (PhysReg
|| !NewVRegs
.empty())
981 // Then isolate blocks with multiple uses.
982 SplitAnalysis::BlockPtrSet Blocks
;
983 if (SA
->getMultiUseBlocks(Blocks
)) {
984 SmallVector
<LiveInterval
*, 4> SpillRegs
;
985 LiveRangeEdit
LREdit(VirtReg
, NewVRegs
, SpillRegs
);
986 SplitEditor(*SA
, *LIS
, *VRM
, *DomTree
, LREdit
).splitSingleBlocks(Blocks
);
988 MF
->verify(this, "After splitting live range around basic blocks");
991 // Don't assign any physregs.
996 //===----------------------------------------------------------------------===//
998 //===----------------------------------------------------------------------===//
1000 /// calcInterferenceWeight - Calculate the combined spill weight of
1001 /// interferences when assigning VirtReg to PhysReg.
1002 float RAGreedy::calcInterferenceWeight(LiveInterval
&VirtReg
, unsigned PhysReg
){
1004 for (const unsigned *AI
= TRI
->getOverlaps(PhysReg
); *AI
; ++AI
) {
1005 LiveIntervalUnion::Query
&Q
= query(VirtReg
, *AI
);
1006 Q
.collectInterferingVRegs();
1007 if (Q
.seenUnspillableVReg())
1009 for (unsigned i
= 0, e
= Q
.interferingVRegs().size(); i
!= e
; ++i
)
1010 Sum
+= Q
.interferingVRegs()[i
]->weight
;
1015 /// trySpillInterferences - Try to spill interfering registers instead of the
1016 /// current one. Only do it if the accumulated spill weight is smaller than the
1017 /// current spill weight.
1018 unsigned RAGreedy::trySpillInterferences(LiveInterval
&VirtReg
,
1019 AllocationOrder
&Order
,
1020 SmallVectorImpl
<LiveInterval
*> &NewVRegs
) {
1021 NamedRegionTimer
T("Spill Interference", TimerGroupName
, TimePassesIsEnabled
);
1022 unsigned BestPhys
= 0;
1023 float BestWeight
= 0;
1026 while (unsigned PhysReg
= Order
.next()) {
1027 float Weight
= calcInterferenceWeight(VirtReg
, PhysReg
);
1028 if (Weight
== HUGE_VALF
|| Weight
>= VirtReg
.weight
)
1030 if (!BestPhys
|| Weight
< BestWeight
)
1031 BestPhys
= PhysReg
, BestWeight
= Weight
;
1034 // No candidates found.
1038 // Collect all interfering registers.
1039 SmallVector
<LiveInterval
*, 8> Spills
;
1040 for (const unsigned *AI
= TRI
->getOverlaps(BestPhys
); *AI
; ++AI
) {
1041 LiveIntervalUnion::Query
&Q
= query(VirtReg
, *AI
);
1042 Spills
.append(Q
.interferingVRegs().begin(), Q
.interferingVRegs().end());
1043 for (unsigned i
= 0, e
= Q
.interferingVRegs().size(); i
!= e
; ++i
) {
1044 LiveInterval
*VReg
= Q
.interferingVRegs()[i
];
1045 unassign(*VReg
, *AI
);
1050 DEBUG(dbgs() << "spilling " << Spills
.size() << " interferences with weight "
1051 << BestWeight
<< '\n');
1052 for (unsigned i
= 0, e
= Spills
.size(); i
!= e
; ++i
)
1053 spiller().spill(Spills
[i
], NewVRegs
, Spills
);
1058 //===----------------------------------------------------------------------===//
1060 //===----------------------------------------------------------------------===//
1062 unsigned RAGreedy::selectOrSplit(LiveInterval
&VirtReg
,
1063 SmallVectorImpl
<LiveInterval
*> &NewVRegs
) {
1064 // First try assigning a free register.
1065 AllocationOrder
Order(VirtReg
.reg
, *VRM
, ReservedRegs
);
1066 while (unsigned PhysReg
= Order
.next()) {
1067 if (!checkPhysRegInterference(VirtReg
, PhysReg
))
1071 // Try to reassign interferences.
1072 if (unsigned PhysReg
= tryReassignOrEvict(VirtReg
, Order
, NewVRegs
))
1075 assert(NewVRegs
.empty() && "Cannot append to existing NewVRegs");
1077 // Try splitting VirtReg or interferences.
1078 unsigned PhysReg
= trySplit(VirtReg
, Order
, NewVRegs
);
1079 if (PhysReg
|| !NewVRegs
.empty())
1082 // Try to spill another interfering reg with less spill weight.
1083 PhysReg
= trySpillInterferences(VirtReg
, Order
, NewVRegs
);
1087 // Finally spill VirtReg itself.
1088 NamedRegionTimer
T("Spiller", TimerGroupName
, TimePassesIsEnabled
);
1089 SmallVector
<LiveInterval
*, 1> pendingSpills
;
1090 spiller().spill(&VirtReg
, NewVRegs
, pendingSpills
);
1092 // The live virtual register requesting allocation was spilled, so tell
1093 // the caller not to allocate anything during this round.
1097 bool RAGreedy::runOnMachineFunction(MachineFunction
&mf
) {
1098 DEBUG(dbgs() << "********** GREEDY REGISTER ALLOCATION **********\n"
1099 << "********** Function: "
1100 << ((Value
*)mf
.getFunction())->getName() << '\n');
1104 MF
->verify(this, "Before greedy register allocator");
1106 RegAllocBase::init(getAnalysis
<VirtRegMap
>(), getAnalysis
<LiveIntervals
>());
1107 Indexes
= &getAnalysis
<SlotIndexes
>();
1108 DomTree
= &getAnalysis
<MachineDominatorTree
>();
1109 ReservedRegs
= TRI
->getReservedRegs(*MF
);
1110 SpillerInstance
.reset(createInlineSpiller(*this, *MF
, *VRM
));
1111 Loops
= &getAnalysis
<MachineLoopInfo
>();
1112 LoopRanges
= &getAnalysis
<MachineLoopRanges
>();
1113 Bundles
= &getAnalysis
<EdgeBundles
>();
1114 SpillPlacer
= &getAnalysis
<SpillPlacement
>();
1116 SA
.reset(new SplitAnalysis(*MF
, *LIS
, *Loops
));
1120 LIS
->addKillFlags();
1124 NamedRegionTimer
T("Rewriter", TimerGroupName
, TimePassesIsEnabled
);
1125 std::auto_ptr
<VirtRegRewriter
> rewriter(createVirtRegRewriter());
1126 rewriter
->runOnMachineFunction(*MF
, *VRM
, LIS
);
1129 // The pass output is in VirtRegMap. Release all the transient data.