1 //===-- RegAllocLinearScan.cpp - Linear Scan 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 implements a linear scan register allocator.
12 //===----------------------------------------------------------------------===//
14 #define DEBUG_TYPE "regalloc"
15 #include "PhysRegTracker.h"
16 #include "VirtRegMap.h"
17 #include "llvm/Function.h"
18 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
19 #include "llvm/CodeGen/LiveStackAnalysis.h"
20 #include "llvm/CodeGen/MachineFunctionPass.h"
21 #include "llvm/CodeGen/MachineInstr.h"
22 #include "llvm/CodeGen/MachineLoopInfo.h"
23 #include "llvm/CodeGen/MachineRegisterInfo.h"
24 #include "llvm/CodeGen/Passes.h"
25 #include "llvm/CodeGen/RegAllocRegistry.h"
26 #include "llvm/CodeGen/RegisterCoalescer.h"
27 #include "llvm/Target/TargetRegisterInfo.h"
28 #include "llvm/Target/TargetMachine.h"
29 #include "llvm/Target/TargetInstrInfo.h"
30 #include "llvm/ADT/EquivalenceClasses.h"
31 #include "llvm/ADT/Statistic.h"
32 #include "llvm/ADT/STLExtras.h"
33 #include "llvm/Support/Debug.h"
34 #include "llvm/Support/Compiler.h"
42 STATISTIC(NumIters
, "Number of iterations performed");
43 STATISTIC(NumBacktracks
, "Number of times we had to backtrack");
44 STATISTIC(NumCoalesce
, "Number of copies coalesced");
47 NewHeuristic("new-spilling-heuristic",
48 cl::desc("Use new spilling heuristic"),
49 cl::init(false), cl::Hidden
);
51 static RegisterRegAlloc
52 linearscanRegAlloc("linearscan", " linear scan register allocator",
53 createLinearScanRegisterAllocator
);
56 struct VISIBILITY_HIDDEN RALinScan
: public MachineFunctionPass
{
58 RALinScan() : MachineFunctionPass((intptr_t)&ID
) {}
60 typedef std::pair
<LiveInterval
*, LiveInterval::iterator
> IntervalPtr
;
61 typedef SmallVector
<IntervalPtr
, 32> IntervalPtrs
;
63 /// RelatedRegClasses - This structure is built the first time a function is
64 /// compiled, and keeps track of which register classes have registers that
65 /// belong to multiple classes or have aliases that are in other classes.
66 EquivalenceClasses
<const TargetRegisterClass
*> RelatedRegClasses
;
67 DenseMap
<unsigned, const TargetRegisterClass
*> OneClassForEachPhysReg
;
70 MachineRegisterInfo
* mri_
;
71 const TargetMachine
* tm_
;
72 const TargetRegisterInfo
* tri_
;
73 const TargetInstrInfo
* tii_
;
74 MachineRegisterInfo
*reginfo_
;
75 BitVector allocatableRegs_
;
78 const MachineLoopInfo
*loopInfo
;
80 /// handled_ - Intervals are added to the handled_ set in the order of their
81 /// start value. This is uses for backtracking.
82 std::vector
<LiveInterval
*> handled_
;
84 /// fixed_ - Intervals that correspond to machine registers.
88 /// active_ - Intervals that are currently being processed, and which have a
89 /// live range active for the current point.
92 /// inactive_ - Intervals that are currently being processed, but which have
93 /// a hold at the current point.
94 IntervalPtrs inactive_
;
96 typedef std::priority_queue
<LiveInterval
*,
97 SmallVector
<LiveInterval
*, 64>,
98 greater_ptr
<LiveInterval
> > IntervalHeap
;
99 IntervalHeap unhandled_
;
100 std::auto_ptr
<PhysRegTracker
> prt_
;
101 std::auto_ptr
<VirtRegMap
> vrm_
;
102 std::auto_ptr
<Spiller
> spiller_
;
105 virtual const char* getPassName() const {
106 return "Linear Scan Register Allocator";
109 virtual void getAnalysisUsage(AnalysisUsage
&AU
) const {
110 AU
.addRequired
<LiveIntervals
>();
111 // Make sure PassManager knows which analyses to make available
112 // to coalescing and which analyses coalescing invalidates.
113 AU
.addRequiredTransitive
<RegisterCoalescer
>();
114 AU
.addRequired
<LiveStacks
>();
115 AU
.addPreserved
<LiveStacks
>();
116 AU
.addRequired
<MachineLoopInfo
>();
117 AU
.addPreserved
<MachineLoopInfo
>();
118 AU
.addPreservedID(MachineDominatorsID
);
119 MachineFunctionPass::getAnalysisUsage(AU
);
122 /// runOnMachineFunction - register allocate the whole function
123 bool runOnMachineFunction(MachineFunction
&);
126 /// linearScan - the linear scan algorithm
129 /// initIntervalSets - initialize the interval sets.
131 void initIntervalSets();
133 /// processActiveIntervals - expire old intervals and move non-overlapping
134 /// ones to the inactive list.
135 void processActiveIntervals(unsigned CurPoint
);
137 /// processInactiveIntervals - expire old intervals and move overlapping
138 /// ones to the active list.
139 void processInactiveIntervals(unsigned CurPoint
);
141 /// assignRegOrStackSlotAtInterval - assign a register if one
142 /// is available, or spill.
143 void assignRegOrStackSlotAtInterval(LiveInterval
* cur
);
145 /// findIntervalsToSpill - Determine the intervals to spill for the
146 /// specified interval. It's passed the physical registers whose spill
147 /// weight is the lowest among all the registers whose live intervals
148 /// conflict with the interval.
149 void findIntervalsToSpill(LiveInterval
*cur
,
150 std::vector
<std::pair
<unsigned,float> > &Candidates
,
152 SmallVector
<LiveInterval
*, 8> &SpillIntervals
);
154 /// attemptTrivialCoalescing - If a simple interval is defined by a copy,
155 /// try allocate the definition the same register as the source register
156 /// if the register is not defined during live time of the interval. This
157 /// eliminate a copy. This is used to coalesce copies which were not
158 /// coalesced away before allocation either due to dest and src being in
159 /// different register classes or because the coalescer was overly
161 unsigned attemptTrivialCoalescing(LiveInterval
&cur
, unsigned Reg
);
164 /// register handling helpers
167 /// getFreePhysReg - return a free physical register for this virtual
168 /// register interval if we have one, otherwise return 0.
169 unsigned getFreePhysReg(LiveInterval
* cur
);
171 /// assignVirt2StackSlot - assigns this virtual register to a
172 /// stack slot. returns the stack slot
173 int assignVirt2StackSlot(unsigned virtReg
);
175 void ComputeRelatedRegClasses();
177 template <typename ItTy
>
178 void printIntervals(const char* const str
, ItTy i
, ItTy e
) const {
179 if (str
) DOUT
<< str
<< " intervals:\n";
180 for (; i
!= e
; ++i
) {
181 DOUT
<< "\t" << *i
->first
<< " -> ";
182 unsigned reg
= i
->first
->reg
;
183 if (TargetRegisterInfo::isVirtualRegister(reg
)) {
184 reg
= vrm_
->getPhys(reg
);
186 DOUT
<< tri_
->getName(reg
) << '\n';
190 char RALinScan::ID
= 0;
193 static RegisterPass
<RALinScan
>
194 X("linearscan-regalloc", "Linear Scan Register Allocator");
196 void RALinScan::ComputeRelatedRegClasses() {
197 const TargetRegisterInfo
&TRI
= *tri_
;
199 // First pass, add all reg classes to the union, and determine at least one
200 // reg class that each register is in.
201 bool HasAliases
= false;
202 for (TargetRegisterInfo::regclass_iterator RCI
= TRI
.regclass_begin(),
203 E
= TRI
.regclass_end(); RCI
!= E
; ++RCI
) {
204 RelatedRegClasses
.insert(*RCI
);
205 for (TargetRegisterClass::iterator I
= (*RCI
)->begin(), E
= (*RCI
)->end();
207 HasAliases
= HasAliases
|| *TRI
.getAliasSet(*I
) != 0;
209 const TargetRegisterClass
*&PRC
= OneClassForEachPhysReg
[*I
];
211 // Already processed this register. Just make sure we know that
212 // multiple register classes share a register.
213 RelatedRegClasses
.unionSets(PRC
, *RCI
);
220 // Second pass, now that we know conservatively what register classes each reg
221 // belongs to, add info about aliases. We don't need to do this for targets
222 // without register aliases.
224 for (DenseMap
<unsigned, const TargetRegisterClass
*>::iterator
225 I
= OneClassForEachPhysReg
.begin(), E
= OneClassForEachPhysReg
.end();
227 for (const unsigned *AS
= TRI
.getAliasSet(I
->first
); *AS
; ++AS
)
228 RelatedRegClasses
.unionSets(I
->second
, OneClassForEachPhysReg
[*AS
]);
231 /// attemptTrivialCoalescing - If a simple interval is defined by a copy,
232 /// try allocate the definition the same register as the source register
233 /// if the register is not defined during live time of the interval. This
234 /// eliminate a copy. This is used to coalesce copies which were not
235 /// coalesced away before allocation either due to dest and src being in
236 /// different register classes or because the coalescer was overly
238 unsigned RALinScan::attemptTrivialCoalescing(LiveInterval
&cur
, unsigned Reg
) {
239 if ((cur
.preference
&& cur
.preference
== Reg
) || !cur
.containsOneValue())
242 VNInfo
*vni
= cur
.getValNumInfo(0);
243 if (!vni
->def
|| vni
->def
== ~1U || vni
->def
== ~0U)
245 MachineInstr
*CopyMI
= li_
->getInstructionFromIndex(vni
->def
);
246 unsigned SrcReg
, DstReg
;
247 if (!CopyMI
|| !tii_
->isMoveInstr(*CopyMI
, SrcReg
, DstReg
))
249 if (TargetRegisterInfo::isVirtualRegister(SrcReg
)) {
250 if (!vrm_
->isAssignedReg(SrcReg
))
253 SrcReg
= vrm_
->getPhys(SrcReg
);
258 const TargetRegisterClass
*RC
= reginfo_
->getRegClass(cur
.reg
);
259 if (!RC
->contains(SrcReg
))
263 if (!li_
->conflictsWithPhysRegDef(cur
, *vrm_
, SrcReg
)) {
264 DOUT
<< "Coalescing: " << cur
<< " -> " << tri_
->getName(SrcReg
)
266 vrm_
->clearVirt(cur
.reg
);
267 vrm_
->assignVirt2Phys(cur
.reg
, SrcReg
);
275 bool RALinScan::runOnMachineFunction(MachineFunction
&fn
) {
277 mri_
= &fn
.getRegInfo();
278 tm_
= &fn
.getTarget();
279 tri_
= tm_
->getRegisterInfo();
280 tii_
= tm_
->getInstrInfo();
281 reginfo_
= &mf_
->getRegInfo();
282 allocatableRegs_
= tri_
->getAllocatableSet(fn
);
283 li_
= &getAnalysis
<LiveIntervals
>();
284 ls_
= &getAnalysis
<LiveStacks
>();
285 loopInfo
= &getAnalysis
<MachineLoopInfo
>();
287 // We don't run the coalescer here because we have no reason to
288 // interact with it. If the coalescer requires interaction, it
289 // won't do anything. If it doesn't require interaction, we assume
290 // it was run as a separate pass.
292 // If this is the first function compiled, compute the related reg classes.
293 if (RelatedRegClasses
.empty())
294 ComputeRelatedRegClasses();
296 if (!prt_
.get()) prt_
.reset(new PhysRegTracker(*tri_
));
297 vrm_
.reset(new VirtRegMap(*mf_
));
298 if (!spiller_
.get()) spiller_
.reset(createSpiller());
304 // Rewrite spill code and update the PhysRegsUsed set.
305 spiller_
->runOnMachineFunction(*mf_
, *vrm_
);
306 vrm_
.reset(); // Free the VirtRegMap
308 assert(unhandled_
.empty() && "Unhandled live intervals remain!");
317 /// initIntervalSets - initialize the interval sets.
319 void RALinScan::initIntervalSets()
321 assert(unhandled_
.empty() && fixed_
.empty() &&
322 active_
.empty() && inactive_
.empty() &&
323 "interval sets should be empty on initialization");
325 handled_
.reserve(li_
->getNumIntervals());
327 for (LiveIntervals::iterator i
= li_
->begin(), e
= li_
->end(); i
!= e
; ++i
) {
328 if (TargetRegisterInfo::isPhysicalRegister(i
->second
->reg
)) {
329 reginfo_
->setPhysRegUsed(i
->second
->reg
);
330 fixed_
.push_back(std::make_pair(i
->second
, i
->second
->begin()));
332 unhandled_
.push(i
->second
);
336 void RALinScan::linearScan()
338 // linear scan algorithm
339 DOUT
<< "********** LINEAR SCAN **********\n";
340 DOUT
<< "********** Function: " << mf_
->getFunction()->getName() << '\n';
342 DEBUG(printIntervals("fixed", fixed_
.begin(), fixed_
.end()));
344 while (!unhandled_
.empty()) {
345 // pick the interval with the earliest start point
346 LiveInterval
* cur
= unhandled_
.top();
349 DOUT
<< "\n*** CURRENT ***: " << *cur
<< '\n';
352 processActiveIntervals(cur
->beginNumber());
353 processInactiveIntervals(cur
->beginNumber());
355 assert(TargetRegisterInfo::isVirtualRegister(cur
->reg
) &&
356 "Can only allocate virtual registers!");
359 // Allocating a virtual register. try to find a free
360 // physical register or spill an interval (possibly this one) in order to
362 assignRegOrStackSlotAtInterval(cur
);
364 DEBUG(printIntervals("active", active_
.begin(), active_
.end()));
365 DEBUG(printIntervals("inactive", inactive_
.begin(), inactive_
.end()));
368 // expire any remaining active intervals
369 while (!active_
.empty()) {
370 IntervalPtr
&IP
= active_
.back();
371 unsigned reg
= IP
.first
->reg
;
372 DOUT
<< "\tinterval " << *IP
.first
<< " expired\n";
373 assert(TargetRegisterInfo::isVirtualRegister(reg
) &&
374 "Can only allocate virtual registers!");
375 reg
= vrm_
->getPhys(reg
);
376 prt_
->delRegUse(reg
);
380 // expire any remaining inactive intervals
381 DEBUG(for (IntervalPtrs::reverse_iterator
382 i
= inactive_
.rbegin(); i
!= inactive_
.rend(); ++i
)
383 DOUT
<< "\tinterval " << *i
->first
<< " expired\n");
386 // Add live-ins to every BB except for entry. Also perform trivial coalescing.
387 MachineFunction::iterator EntryMBB
= mf_
->begin();
388 SmallVector
<MachineBasicBlock
*, 8> LiveInMBBs
;
389 for (LiveIntervals::iterator i
= li_
->begin(), e
= li_
->end(); i
!= e
; ++i
) {
390 LiveInterval
&cur
= *i
->second
;
392 bool isPhys
= TargetRegisterInfo::isPhysicalRegister(cur
.reg
);
395 else if (vrm_
->isAssignedReg(cur
.reg
))
396 Reg
= attemptTrivialCoalescing(cur
, vrm_
->getPhys(cur
.reg
));
399 // Ignore splited live intervals.
400 if (!isPhys
&& vrm_
->getPreSplitReg(cur
.reg
))
402 for (LiveInterval::Ranges::const_iterator I
= cur
.begin(), E
= cur
.end();
404 const LiveRange
&LR
= *I
;
405 if (li_
->findLiveInMBBs(LR
, LiveInMBBs
)) {
406 for (unsigned i
= 0, e
= LiveInMBBs
.size(); i
!= e
; ++i
)
407 if (LiveInMBBs
[i
] != EntryMBB
)
408 LiveInMBBs
[i
]->addLiveIn(Reg
);
417 /// processActiveIntervals - expire old intervals and move non-overlapping ones
418 /// to the inactive list.
419 void RALinScan::processActiveIntervals(unsigned CurPoint
)
421 DOUT
<< "\tprocessing active intervals:\n";
423 for (unsigned i
= 0, e
= active_
.size(); i
!= e
; ++i
) {
424 LiveInterval
*Interval
= active_
[i
].first
;
425 LiveInterval::iterator IntervalPos
= active_
[i
].second
;
426 unsigned reg
= Interval
->reg
;
428 IntervalPos
= Interval
->advanceTo(IntervalPos
, CurPoint
);
430 if (IntervalPos
== Interval
->end()) { // Remove expired intervals.
431 DOUT
<< "\t\tinterval " << *Interval
<< " expired\n";
432 assert(TargetRegisterInfo::isVirtualRegister(reg
) &&
433 "Can only allocate virtual registers!");
434 reg
= vrm_
->getPhys(reg
);
435 prt_
->delRegUse(reg
);
437 // Pop off the end of the list.
438 active_
[i
] = active_
.back();
442 } else if (IntervalPos
->start
> CurPoint
) {
443 // Move inactive intervals to inactive list.
444 DOUT
<< "\t\tinterval " << *Interval
<< " inactive\n";
445 assert(TargetRegisterInfo::isVirtualRegister(reg
) &&
446 "Can only allocate virtual registers!");
447 reg
= vrm_
->getPhys(reg
);
448 prt_
->delRegUse(reg
);
450 inactive_
.push_back(std::make_pair(Interval
, IntervalPos
));
452 // Pop off the end of the list.
453 active_
[i
] = active_
.back();
457 // Otherwise, just update the iterator position.
458 active_
[i
].second
= IntervalPos
;
463 /// processInactiveIntervals - expire old intervals and move overlapping
464 /// ones to the active list.
465 void RALinScan::processInactiveIntervals(unsigned CurPoint
)
467 DOUT
<< "\tprocessing inactive intervals:\n";
469 for (unsigned i
= 0, e
= inactive_
.size(); i
!= e
; ++i
) {
470 LiveInterval
*Interval
= inactive_
[i
].first
;
471 LiveInterval::iterator IntervalPos
= inactive_
[i
].second
;
472 unsigned reg
= Interval
->reg
;
474 IntervalPos
= Interval
->advanceTo(IntervalPos
, CurPoint
);
476 if (IntervalPos
== Interval
->end()) { // remove expired intervals.
477 DOUT
<< "\t\tinterval " << *Interval
<< " expired\n";
479 // Pop off the end of the list.
480 inactive_
[i
] = inactive_
.back();
481 inactive_
.pop_back();
483 } else if (IntervalPos
->start
<= CurPoint
) {
484 // move re-activated intervals in active list
485 DOUT
<< "\t\tinterval " << *Interval
<< " active\n";
486 assert(TargetRegisterInfo::isVirtualRegister(reg
) &&
487 "Can only allocate virtual registers!");
488 reg
= vrm_
->getPhys(reg
);
489 prt_
->addRegUse(reg
);
491 active_
.push_back(std::make_pair(Interval
, IntervalPos
));
493 // Pop off the end of the list.
494 inactive_
[i
] = inactive_
.back();
495 inactive_
.pop_back();
498 // Otherwise, just update the iterator position.
499 inactive_
[i
].second
= IntervalPos
;
504 /// updateSpillWeights - updates the spill weights of the specifed physical
505 /// register and its weight.
506 static void updateSpillWeights(std::vector
<float> &Weights
,
507 unsigned reg
, float weight
,
508 const TargetRegisterInfo
*TRI
) {
509 Weights
[reg
] += weight
;
510 for (const unsigned* as
= TRI
->getAliasSet(reg
); *as
; ++as
)
511 Weights
[*as
] += weight
;
515 RALinScan::IntervalPtrs::iterator
516 FindIntervalInVector(RALinScan::IntervalPtrs
&IP
, LiveInterval
*LI
) {
517 for (RALinScan::IntervalPtrs::iterator I
= IP
.begin(), E
= IP
.end();
519 if (I
->first
== LI
) return I
;
523 static void RevertVectorIteratorsTo(RALinScan::IntervalPtrs
&V
, unsigned Point
){
524 for (unsigned i
= 0, e
= V
.size(); i
!= e
; ++i
) {
525 RALinScan::IntervalPtr
&IP
= V
[i
];
526 LiveInterval::iterator I
= std::upper_bound(IP
.first
->begin(),
528 if (I
!= IP
.first
->begin()) --I
;
533 /// addStackInterval - Create a LiveInterval for stack if the specified live
534 /// interval has been spilled.
535 static void addStackInterval(LiveInterval
*cur
, LiveStacks
*ls_
,
536 LiveIntervals
*li_
, float &Weight
,
538 int SS
= vrm_
.getStackSlot(cur
->reg
);
539 if (SS
== VirtRegMap::NO_STACK_SLOT
)
541 LiveInterval
&SI
= ls_
->getOrCreateInterval(SS
);
545 if (SI
.getNumValNums())
546 VNI
= SI
.getValNumInfo(0);
548 VNI
= SI
.getNextValue(~0U, 0, ls_
->getVNInfoAllocator());
550 LiveInterval
&RI
= li_
->getInterval(cur
->reg
);
551 // FIXME: This may be overly conservative.
552 SI
.MergeRangesInAsValue(RI
, VNI
);
555 /// getConflictWeight - Return the number of conflicts between cur
556 /// live interval and defs and uses of Reg weighted by loop depthes.
557 static float getConflictWeight(LiveInterval
*cur
, unsigned Reg
,
559 MachineRegisterInfo
*mri_
,
560 const MachineLoopInfo
*loopInfo
) {
562 for (MachineRegisterInfo::reg_iterator I
= mri_
->reg_begin(Reg
),
563 E
= mri_
->reg_end(); I
!= E
; ++I
) {
564 MachineInstr
*MI
= &*I
;
565 if (cur
->liveAt(li_
->getInstructionIndex(MI
))) {
566 unsigned loopDepth
= loopInfo
->getLoopDepth(MI
->getParent());
567 Conflicts
+= powf(10.0f
, (float)loopDepth
);
573 /// findIntervalsToSpill - Determine the intervals to spill for the
574 /// specified interval. It's passed the physical registers whose spill
575 /// weight is the lowest among all the registers whose live intervals
576 /// conflict with the interval.
577 void RALinScan::findIntervalsToSpill(LiveInterval
*cur
,
578 std::vector
<std::pair
<unsigned,float> > &Candidates
,
580 SmallVector
<LiveInterval
*, 8> &SpillIntervals
) {
581 // We have figured out the *best* register to spill. But there are other
582 // registers that are pretty good as well (spill weight within 3%). Spill
583 // the one that has fewest defs and uses that conflict with cur.
584 float Conflicts
[3] = { 0.0f
, 0.0f
, 0.0f
};
585 SmallVector
<LiveInterval
*, 8> SLIs
[3];
587 DOUT
<< "\tConsidering " << NumCands
<< " candidates: ";
588 DEBUG(for (unsigned i
= 0; i
!= NumCands
; ++i
)
589 DOUT
<< tri_
->getName(Candidates
[i
].first
) << " ";
592 // Calculate the number of conflicts of each candidate.
593 for (IntervalPtrs::iterator i
= active_
.begin(); i
!= active_
.end(); ++i
) {
594 unsigned Reg
= i
->first
->reg
;
595 unsigned PhysReg
= vrm_
->getPhys(Reg
);
596 if (!cur
->overlapsFrom(*i
->first
, i
->second
))
598 for (unsigned j
= 0; j
< NumCands
; ++j
) {
599 unsigned Candidate
= Candidates
[j
].first
;
600 if (tri_
->regsOverlap(PhysReg
, Candidate
)) {
602 Conflicts
[j
] += getConflictWeight(cur
, Reg
, li_
, mri_
, loopInfo
);
603 SLIs
[j
].push_back(i
->first
);
608 for (IntervalPtrs::iterator i
= inactive_
.begin(); i
!= inactive_
.end(); ++i
){
609 unsigned Reg
= i
->first
->reg
;
610 unsigned PhysReg
= vrm_
->getPhys(Reg
);
611 if (!cur
->overlapsFrom(*i
->first
, i
->second
-1))
613 for (unsigned j
= 0; j
< NumCands
; ++j
) {
614 unsigned Candidate
= Candidates
[j
].first
;
615 if (tri_
->regsOverlap(PhysReg
, Candidate
)) {
617 Conflicts
[j
] += getConflictWeight(cur
, Reg
, li_
, mri_
, loopInfo
);
618 SLIs
[j
].push_back(i
->first
);
623 // Which is the best candidate?
624 unsigned BestCandidate
= 0;
625 float MinConflicts
= Conflicts
[0];
626 for (unsigned i
= 1; i
!= NumCands
; ++i
) {
627 if (Conflicts
[i
] < MinConflicts
) {
629 MinConflicts
= Conflicts
[i
];
633 std::copy(SLIs
[BestCandidate
].begin(), SLIs
[BestCandidate
].end(),
634 std::back_inserter(SpillIntervals
));
638 struct WeightCompare
{
639 typedef std::pair
<unsigned, float> RegWeightPair
;
640 bool operator()(const RegWeightPair
&LHS
, const RegWeightPair
&RHS
) const {
641 return LHS
.second
< RHS
.second
;
646 static bool weightsAreClose(float w1
, float w2
) {
650 float diff
= w1
- w2
;
651 if (diff
<= 0.02f
) // Within 0.02f
653 return (diff
/ w2
) <= 0.05f
; // Within 5%.
656 /// assignRegOrStackSlotAtInterval - assign a register if one is available, or
658 void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval
* cur
)
660 DOUT
<< "\tallocating current interval: ";
662 // This is an implicitly defined live interval, just assign any register.
663 const TargetRegisterClass
*RC
= reginfo_
->getRegClass(cur
->reg
);
665 unsigned physReg
= cur
->preference
;
667 physReg
= *RC
->allocation_order_begin(*mf_
);
668 DOUT
<< tri_
->getName(physReg
) << '\n';
669 // Note the register is not really in use.
670 vrm_
->assignVirt2Phys(cur
->reg
, physReg
);
674 PhysRegTracker backupPrt
= *prt_
;
676 std::vector
<std::pair
<unsigned, float> > SpillWeightsToAdd
;
677 unsigned StartPosition
= cur
->beginNumber();
678 const TargetRegisterClass
*RCLeader
= RelatedRegClasses
.getLeaderValue(RC
);
680 // If this live interval is defined by a move instruction and its source is
681 // assigned a physical register that is compatible with the target register
682 // class, then we should try to assign it the same register.
683 // This can happen when the move is from a larger register class to a smaller
684 // one, e.g. X86::mov32to32_. These move instructions are not coalescable.
685 if (!cur
->preference
&& cur
->containsOneValue()) {
686 VNInfo
*vni
= cur
->getValNumInfo(0);
687 if (vni
->def
&& vni
->def
!= ~1U && vni
->def
!= ~0U) {
688 MachineInstr
*CopyMI
= li_
->getInstructionFromIndex(vni
->def
);
689 unsigned SrcReg
, DstReg
;
690 if (CopyMI
&& tii_
->isMoveInstr(*CopyMI
, SrcReg
, DstReg
)) {
692 if (TargetRegisterInfo::isPhysicalRegister(SrcReg
))
694 else if (vrm_
->isAssignedReg(SrcReg
))
695 Reg
= vrm_
->getPhys(SrcReg
);
696 if (Reg
&& allocatableRegs_
[Reg
] && RC
->contains(Reg
))
697 cur
->preference
= Reg
;
702 // for every interval in inactive we overlap with, mark the
703 // register as not free and update spill weights.
704 for (IntervalPtrs::const_iterator i
= inactive_
.begin(),
705 e
= inactive_
.end(); i
!= e
; ++i
) {
706 unsigned Reg
= i
->first
->reg
;
707 assert(TargetRegisterInfo::isVirtualRegister(Reg
) &&
708 "Can only allocate virtual registers!");
709 const TargetRegisterClass
*RegRC
= reginfo_
->getRegClass(Reg
);
710 // If this is not in a related reg class to the register we're allocating,
712 if (RelatedRegClasses
.getLeaderValue(RegRC
) == RCLeader
&&
713 cur
->overlapsFrom(*i
->first
, i
->second
-1)) {
714 Reg
= vrm_
->getPhys(Reg
);
715 prt_
->addRegUse(Reg
);
716 SpillWeightsToAdd
.push_back(std::make_pair(Reg
, i
->first
->weight
));
720 // Speculatively check to see if we can get a register right now. If not,
721 // we know we won't be able to by adding more constraints. If so, we can
722 // check to see if it is valid. Doing an exhaustive search of the fixed_ list
723 // is very bad (it contains all callee clobbered registers for any functions
724 // with a call), so we want to avoid doing that if possible.
725 unsigned physReg
= getFreePhysReg(cur
);
726 unsigned BestPhysReg
= physReg
;
728 // We got a register. However, if it's in the fixed_ list, we might
729 // conflict with it. Check to see if we conflict with it or any of its
731 SmallSet
<unsigned, 8> RegAliases
;
732 for (const unsigned *AS
= tri_
->getAliasSet(physReg
); *AS
; ++AS
)
733 RegAliases
.insert(*AS
);
735 bool ConflictsWithFixed
= false;
736 for (unsigned i
= 0, e
= fixed_
.size(); i
!= e
; ++i
) {
737 IntervalPtr
&IP
= fixed_
[i
];
738 if (physReg
== IP
.first
->reg
|| RegAliases
.count(IP
.first
->reg
)) {
739 // Okay, this reg is on the fixed list. Check to see if we actually
741 LiveInterval
*I
= IP
.first
;
742 if (I
->endNumber() > StartPosition
) {
743 LiveInterval::iterator II
= I
->advanceTo(IP
.second
, StartPosition
);
745 if (II
!= I
->begin() && II
->start
> StartPosition
)
747 if (cur
->overlapsFrom(*I
, II
)) {
748 ConflictsWithFixed
= true;
755 // Okay, the register picked by our speculative getFreePhysReg call turned
756 // out to be in use. Actually add all of the conflicting fixed registers to
757 // prt so we can do an accurate query.
758 if (ConflictsWithFixed
) {
759 // For every interval in fixed we overlap with, mark the register as not
760 // free and update spill weights.
761 for (unsigned i
= 0, e
= fixed_
.size(); i
!= e
; ++i
) {
762 IntervalPtr
&IP
= fixed_
[i
];
763 LiveInterval
*I
= IP
.first
;
765 const TargetRegisterClass
*RegRC
= OneClassForEachPhysReg
[I
->reg
];
766 if (RelatedRegClasses
.getLeaderValue(RegRC
) == RCLeader
&&
767 I
->endNumber() > StartPosition
) {
768 LiveInterval::iterator II
= I
->advanceTo(IP
.second
, StartPosition
);
770 if (II
!= I
->begin() && II
->start
> StartPosition
)
772 if (cur
->overlapsFrom(*I
, II
)) {
773 unsigned reg
= I
->reg
;
774 prt_
->addRegUse(reg
);
775 SpillWeightsToAdd
.push_back(std::make_pair(reg
, I
->weight
));
780 // Using the newly updated prt_ object, which includes conflicts in the
781 // future, see if there are any registers available.
782 physReg
= getFreePhysReg(cur
);
786 // Restore the physical register tracker, removing information about the
790 // if we find a free register, we are done: assign this virtual to
791 // the free physical register and add this interval to the active
794 DOUT
<< tri_
->getName(physReg
) << '\n';
795 vrm_
->assignVirt2Phys(cur
->reg
, physReg
);
796 prt_
->addRegUse(physReg
);
797 active_
.push_back(std::make_pair(cur
, cur
->begin()));
798 handled_
.push_back(cur
);
801 DOUT
<< "no free registers\n";
803 // Compile the spill weights into an array that is better for scanning.
804 std::vector
<float> SpillWeights(tri_
->getNumRegs(), 0.0f
);
805 for (std::vector
<std::pair
<unsigned, float> >::iterator
806 I
= SpillWeightsToAdd
.begin(), E
= SpillWeightsToAdd
.end(); I
!= E
; ++I
)
807 updateSpillWeights(SpillWeights
, I
->first
, I
->second
, tri_
);
809 // for each interval in active, update spill weights.
810 for (IntervalPtrs::const_iterator i
= active_
.begin(), e
= active_
.end();
812 unsigned reg
= i
->first
->reg
;
813 assert(TargetRegisterInfo::isVirtualRegister(reg
) &&
814 "Can only allocate virtual registers!");
815 reg
= vrm_
->getPhys(reg
);
816 updateSpillWeights(SpillWeights
, reg
, i
->first
->weight
, tri_
);
819 DOUT
<< "\tassigning stack slot at interval "<< *cur
<< ":\n";
821 // Find a register to spill.
822 float minWeight
= HUGE_VALF
;
823 unsigned minReg
= 0; /*cur->preference*/; // Try the preferred register first.
826 std::vector
<std::pair
<unsigned,float> > RegsWeights
;
827 if (!minReg
|| SpillWeights
[minReg
] == HUGE_VALF
)
828 for (TargetRegisterClass::iterator i
= RC
->allocation_order_begin(*mf_
),
829 e
= RC
->allocation_order_end(*mf_
); i
!= e
; ++i
) {
831 float regWeight
= SpillWeights
[reg
];
832 if (minWeight
> regWeight
)
834 RegsWeights
.push_back(std::make_pair(reg
, regWeight
));
837 // If we didn't find a register that is spillable, try aliases?
839 for (TargetRegisterClass::iterator i
= RC
->allocation_order_begin(*mf_
),
840 e
= RC
->allocation_order_end(*mf_
); i
!= e
; ++i
) {
842 // No need to worry about if the alias register size < regsize of RC.
843 // We are going to spill all registers that alias it anyway.
844 for (const unsigned* as
= tri_
->getAliasSet(reg
); *as
; ++as
)
845 RegsWeights
.push_back(std::make_pair(*as
, SpillWeights
[*as
]));
849 // Sort all potential spill candidates by weight.
850 std::sort(RegsWeights
.begin(), RegsWeights
.end(), WeightCompare());
851 minReg
= RegsWeights
[0].first
;
852 minWeight
= RegsWeights
[0].second
;
853 if (minWeight
== HUGE_VALF
) {
854 // All registers must have inf weight. Just grab one!
855 minReg
= BestPhysReg
? BestPhysReg
: *RC
->allocation_order_begin(*mf_
);
856 if (cur
->weight
== HUGE_VALF
||
857 li_
->getApproximateInstructionCount(*cur
) == 0)
858 // Spill a physical register around defs and uses.
859 li_
->spillPhysRegAroundRegDefsUses(*cur
, minReg
, *vrm_
);
862 // Find up to 3 registers to consider as spill candidates.
863 unsigned LastCandidate
= RegsWeights
.size() >= 3 ? 3 : 1;
864 while (LastCandidate
> 1) {
865 if (weightsAreClose(RegsWeights
[LastCandidate
-1].second
, minWeight
))
870 DOUT
<< "\t\tregister(s) with min weight(s): ";
871 DEBUG(for (unsigned i
= 0; i
!= LastCandidate
; ++i
)
872 DOUT
<< tri_
->getName(RegsWeights
[i
].first
)
873 << " (" << RegsWeights
[i
].second
<< ")\n");
875 // if the current has the minimum weight, we need to spill it and
876 // add any added intervals back to unhandled, and restart
878 if (cur
->weight
!= HUGE_VALF
&& cur
->weight
<= minWeight
) {
879 DOUT
<< "\t\t\tspilling(c): " << *cur
<< '\n';
881 std::vector
<LiveInterval
*> added
=
882 li_
->addIntervalsForSpills(*cur
, loopInfo
, *vrm_
, SSWeight
);
883 addStackInterval(cur
, ls_
, li_
, SSWeight
, *vrm_
);
885 return; // Early exit if all spills were folded.
887 // Merge added with unhandled. Note that we know that
888 // addIntervalsForSpills returns intervals sorted by their starting
890 for (unsigned i
= 0, e
= added
.size(); i
!= e
; ++i
)
891 unhandled_
.push(added
[i
]);
897 // push the current interval back to unhandled since we are going
898 // to re-run at least this iteration. Since we didn't modify it it
899 // should go back right in the front of the list
900 unhandled_
.push(cur
);
902 assert(TargetRegisterInfo::isPhysicalRegister(minReg
) &&
903 "did not choose a register to spill?");
905 // We spill all intervals aliasing the register with
906 // minimum weight, rollback to the interval with the earliest
907 // start point and let the linear scan algorithm run again
908 SmallVector
<LiveInterval
*, 8> spillIs
;
910 // Determine which intervals have to be spilled.
911 findIntervalsToSpill(cur
, RegsWeights
, LastCandidate
, spillIs
);
913 // Set of spilled vregs (used later to rollback properly)
914 SmallSet
<unsigned, 8> spilled
;
916 // The earliest start of a Spilled interval indicates up to where
917 // in handled we need to roll back
918 unsigned earliestStart
= cur
->beginNumber();
920 // Spill live intervals of virtual regs mapped to the physical register we
921 // want to clear (and its aliases). We only spill those that overlap with the
922 // current interval as the rest do not affect its allocation. we also keep
923 // track of the earliest start of all spilled live intervals since this will
924 // mark our rollback point.
925 std::vector
<LiveInterval
*> added
;
926 while (!spillIs
.empty()) {
927 LiveInterval
*sli
= spillIs
.back();
929 DOUT
<< "\t\t\tspilling(a): " << *sli
<< '\n';
930 earliestStart
= std::min(earliestStart
, sli
->beginNumber());
932 std::vector
<LiveInterval
*> newIs
=
933 li_
->addIntervalsForSpills(*sli
, loopInfo
, *vrm_
, SSWeight
);
934 addStackInterval(sli
, ls_
, li_
, SSWeight
, *vrm_
);
935 std::copy(newIs
.begin(), newIs
.end(), std::back_inserter(added
));
936 spilled
.insert(sli
->reg
);
939 DOUT
<< "\t\trolling back to: " << earliestStart
<< '\n';
941 // Scan handled in reverse order up to the earliest start of a
942 // spilled live interval and undo each one, restoring the state of
944 while (!handled_
.empty()) {
945 LiveInterval
* i
= handled_
.back();
946 // If this interval starts before t we are done.
947 if (i
->beginNumber() < earliestStart
)
949 DOUT
<< "\t\t\tundo changes for: " << *i
<< '\n';
952 // When undoing a live interval allocation we must know if it is active or
953 // inactive to properly update the PhysRegTracker and the VirtRegMap.
954 IntervalPtrs::iterator it
;
955 if ((it
= FindIntervalInVector(active_
, i
)) != active_
.end()) {
957 assert(!TargetRegisterInfo::isPhysicalRegister(i
->reg
));
958 if (!spilled
.count(i
->reg
))
960 prt_
->delRegUse(vrm_
->getPhys(i
->reg
));
961 vrm_
->clearVirt(i
->reg
);
962 } else if ((it
= FindIntervalInVector(inactive_
, i
)) != inactive_
.end()) {
964 assert(!TargetRegisterInfo::isPhysicalRegister(i
->reg
));
965 if (!spilled
.count(i
->reg
))
967 vrm_
->clearVirt(i
->reg
);
969 assert(TargetRegisterInfo::isVirtualRegister(i
->reg
) &&
970 "Can only allocate virtual registers!");
971 vrm_
->clearVirt(i
->reg
);
975 // It interval has a preference, it must be defined by a copy. Clear the
976 // preference now since the source interval allocation may have been undone
981 // Rewind the iterators in the active, inactive, and fixed lists back to the
982 // point we reverted to.
983 RevertVectorIteratorsTo(active_
, earliestStart
);
984 RevertVectorIteratorsTo(inactive_
, earliestStart
);
985 RevertVectorIteratorsTo(fixed_
, earliestStart
);
987 // scan the rest and undo each interval that expired after t and
988 // insert it in active (the next iteration of the algorithm will
989 // put it in inactive if required)
990 for (unsigned i
= 0, e
= handled_
.size(); i
!= e
; ++i
) {
991 LiveInterval
*HI
= handled_
[i
];
992 if (!HI
->expiredAt(earliestStart
) &&
993 HI
->expiredAt(cur
->beginNumber())) {
994 DOUT
<< "\t\t\tundo changes for: " << *HI
<< '\n';
995 active_
.push_back(std::make_pair(HI
, HI
->begin()));
996 assert(!TargetRegisterInfo::isPhysicalRegister(HI
->reg
));
997 prt_
->addRegUse(vrm_
->getPhys(HI
->reg
));
1001 // merge added with unhandled
1002 for (unsigned i
= 0, e
= added
.size(); i
!= e
; ++i
)
1003 unhandled_
.push(added
[i
]);
1006 /// getFreePhysReg - return a free physical register for this virtual register
1007 /// interval if we have one, otherwise return 0.
1008 unsigned RALinScan::getFreePhysReg(LiveInterval
*cur
) {
1009 SmallVector
<unsigned, 256> inactiveCounts
;
1010 unsigned MaxInactiveCount
= 0;
1012 const TargetRegisterClass
*RC
= reginfo_
->getRegClass(cur
->reg
);
1013 const TargetRegisterClass
*RCLeader
= RelatedRegClasses
.getLeaderValue(RC
);
1015 for (IntervalPtrs::iterator i
= inactive_
.begin(), e
= inactive_
.end();
1017 unsigned reg
= i
->first
->reg
;
1018 assert(TargetRegisterInfo::isVirtualRegister(reg
) &&
1019 "Can only allocate virtual registers!");
1021 // If this is not in a related reg class to the register we're allocating,
1023 const TargetRegisterClass
*RegRC
= reginfo_
->getRegClass(reg
);
1024 if (RelatedRegClasses
.getLeaderValue(RegRC
) == RCLeader
) {
1025 reg
= vrm_
->getPhys(reg
);
1026 if (inactiveCounts
.size() <= reg
)
1027 inactiveCounts
.resize(reg
+1);
1028 ++inactiveCounts
[reg
];
1029 MaxInactiveCount
= std::max(MaxInactiveCount
, inactiveCounts
[reg
]);
1033 unsigned FreeReg
= 0;
1034 unsigned FreeRegInactiveCount
= 0;
1036 // If copy coalescer has assigned a "preferred" register, check if it's
1038 if (cur
->preference
) {
1039 if (prt_
->isRegAvail(cur
->preference
)) {
1040 DOUT
<< "\t\tassigned the preferred register: "
1041 << tri_
->getName(cur
->preference
) << "\n";
1042 return cur
->preference
;
1044 DOUT
<< "\t\tunable to assign the preferred register: "
1045 << tri_
->getName(cur
->preference
) << "\n";
1048 // Scan for the first available register.
1049 TargetRegisterClass::iterator I
= RC
->allocation_order_begin(*mf_
);
1050 TargetRegisterClass::iterator E
= RC
->allocation_order_end(*mf_
);
1051 assert(I
!= E
&& "No allocatable register in this register class!");
1053 if (prt_
->isRegAvail(*I
)) {
1055 if (FreeReg
< inactiveCounts
.size())
1056 FreeRegInactiveCount
= inactiveCounts
[FreeReg
];
1058 FreeRegInactiveCount
= 0;
1062 // If there are no free regs, or if this reg has the max inactive count,
1063 // return this register.
1064 if (FreeReg
== 0 || FreeRegInactiveCount
== MaxInactiveCount
) return FreeReg
;
1066 // Continue scanning the registers, looking for the one with the highest
1067 // inactive count. Alkis found that this reduced register pressure very
1068 // slightly on X86 (in rev 1.94 of this file), though this should probably be
1070 for (; I
!= E
; ++I
) {
1072 if (prt_
->isRegAvail(Reg
) && Reg
< inactiveCounts
.size() &&
1073 FreeRegInactiveCount
< inactiveCounts
[Reg
]) {
1075 FreeRegInactiveCount
= inactiveCounts
[Reg
];
1076 if (FreeRegInactiveCount
== MaxInactiveCount
)
1077 break; // We found the one with the max inactive count.
1084 FunctionPass
* llvm::createLinearScanRegisterAllocator() {
1085 return new RALinScan();