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 "VirtRegMap.h"
16 #include "VirtRegRewriter.h"
18 #include "llvm/Function.h"
19 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
20 #include "llvm/CodeGen/LiveStackAnalysis.h"
21 #include "llvm/CodeGen/MachineFunctionPass.h"
22 #include "llvm/CodeGen/MachineInstr.h"
23 #include "llvm/CodeGen/MachineLoopInfo.h"
24 #include "llvm/CodeGen/MachineRegisterInfo.h"
25 #include "llvm/CodeGen/Passes.h"
26 #include "llvm/CodeGen/RegAllocRegistry.h"
27 #include "llvm/CodeGen/RegisterCoalescer.h"
28 #include "llvm/Target/TargetRegisterInfo.h"
29 #include "llvm/Target/TargetMachine.h"
30 #include "llvm/Target/TargetOptions.h"
31 #include "llvm/Target/TargetInstrInfo.h"
32 #include "llvm/ADT/EquivalenceClasses.h"
33 #include "llvm/ADT/SmallSet.h"
34 #include "llvm/ADT/Statistic.h"
35 #include "llvm/ADT/STLExtras.h"
36 #include "llvm/Support/Debug.h"
37 #include "llvm/Support/ErrorHandling.h"
38 #include "llvm/Support/raw_ostream.h"
47 STATISTIC(NumIters
, "Number of iterations performed");
48 STATISTIC(NumBacktracks
, "Number of times we had to backtrack");
49 STATISTIC(NumCoalesce
, "Number of copies coalesced");
50 STATISTIC(NumDowngrade
, "Number of registers downgraded");
53 NewHeuristic("new-spilling-heuristic",
54 cl::desc("Use new spilling heuristic"),
55 cl::init(false), cl::Hidden
);
58 PreSplitIntervals("pre-alloc-split",
59 cl::desc("Pre-register allocation live interval splitting"),
60 cl::init(false), cl::Hidden
);
63 NewSpillFramework("new-spill-framework",
64 cl::desc("New spilling framework"),
65 cl::init(false), cl::Hidden
);
67 static RegisterRegAlloc
68 linearscanRegAlloc("linearscan", "linear scan register allocator",
69 createLinearScanRegisterAllocator
);
72 struct RALinScan
: public MachineFunctionPass
{
74 RALinScan() : MachineFunctionPass(&ID
) {}
76 typedef std::pair
<LiveInterval
*, LiveInterval::iterator
> IntervalPtr
;
77 typedef SmallVector
<IntervalPtr
, 32> IntervalPtrs
;
79 /// RelatedRegClasses - This structure is built the first time a function is
80 /// compiled, and keeps track of which register classes have registers that
81 /// belong to multiple classes or have aliases that are in other classes.
82 EquivalenceClasses
<const TargetRegisterClass
*> RelatedRegClasses
;
83 DenseMap
<unsigned, const TargetRegisterClass
*> OneClassForEachPhysReg
;
85 // NextReloadMap - For each register in the map, it maps to the another
86 // register which is defined by a reload from the same stack slot and
87 // both reloads are in the same basic block.
88 DenseMap
<unsigned, unsigned> NextReloadMap
;
90 // DowngradedRegs - A set of registers which are being "downgraded", i.e.
91 // un-favored for allocation.
92 SmallSet
<unsigned, 8> DowngradedRegs
;
94 // DowngradeMap - A map from virtual registers to physical registers being
95 // downgraded for the virtual registers.
96 DenseMap
<unsigned, unsigned> DowngradeMap
;
99 MachineRegisterInfo
* mri_
;
100 const TargetMachine
* tm_
;
101 const TargetRegisterInfo
* tri_
;
102 const TargetInstrInfo
* tii_
;
103 BitVector allocatableRegs_
;
106 const MachineLoopInfo
*loopInfo
;
108 /// handled_ - Intervals are added to the handled_ set in the order of their
109 /// start value. This is uses for backtracking.
110 std::vector
<LiveInterval
*> handled_
;
112 /// fixed_ - Intervals that correspond to machine registers.
116 /// active_ - Intervals that are currently being processed, and which have a
117 /// live range active for the current point.
118 IntervalPtrs active_
;
120 /// inactive_ - Intervals that are currently being processed, but which have
121 /// a hold at the current point.
122 IntervalPtrs inactive_
;
124 typedef std::priority_queue
<LiveInterval
*,
125 SmallVector
<LiveInterval
*, 64>,
126 greater_ptr
<LiveInterval
> > IntervalHeap
;
127 IntervalHeap unhandled_
;
129 /// regUse_ - Tracks register usage.
130 SmallVector
<unsigned, 32> regUse_
;
131 SmallVector
<unsigned, 32> regUseBackUp_
;
133 /// vrm_ - Tracks register assignments.
136 std::auto_ptr
<VirtRegRewriter
> rewriter_
;
138 std::auto_ptr
<Spiller
> spiller_
;
141 virtual const char* getPassName() const {
142 return "Linear Scan Register Allocator";
145 virtual void getAnalysisUsage(AnalysisUsage
&AU
) const {
146 AU
.setPreservesCFG();
147 AU
.addRequired
<LiveIntervals
>();
149 AU
.addRequiredID(StrongPHIEliminationID
);
150 // Make sure PassManager knows which analyses to make available
151 // to coalescing and which analyses coalescing invalidates.
152 AU
.addRequiredTransitive
<RegisterCoalescer
>();
153 if (PreSplitIntervals
)
154 AU
.addRequiredID(PreAllocSplittingID
);
155 AU
.addRequired
<LiveStacks
>();
156 AU
.addPreserved
<LiveStacks
>();
157 AU
.addRequired
<MachineLoopInfo
>();
158 AU
.addPreserved
<MachineLoopInfo
>();
159 AU
.addRequired
<VirtRegMap
>();
160 AU
.addPreserved
<VirtRegMap
>();
161 AU
.addPreservedID(MachineDominatorsID
);
162 MachineFunctionPass::getAnalysisUsage(AU
);
165 /// runOnMachineFunction - register allocate the whole function
166 bool runOnMachineFunction(MachineFunction
&);
169 /// linearScan - the linear scan algorithm
172 /// initIntervalSets - initialize the interval sets.
174 void initIntervalSets();
176 /// processActiveIntervals - expire old intervals and move non-overlapping
177 /// ones to the inactive list.
178 void processActiveIntervals(LiveIndex CurPoint
);
180 /// processInactiveIntervals - expire old intervals and move overlapping
181 /// ones to the active list.
182 void processInactiveIntervals(LiveIndex CurPoint
);
184 /// hasNextReloadInterval - Return the next liveinterval that's being
185 /// defined by a reload from the same SS as the specified one.
186 LiveInterval
*hasNextReloadInterval(LiveInterval
*cur
);
188 /// DowngradeRegister - Downgrade a register for allocation.
189 void DowngradeRegister(LiveInterval
*li
, unsigned Reg
);
191 /// UpgradeRegister - Upgrade a register for allocation.
192 void UpgradeRegister(unsigned Reg
);
194 /// assignRegOrStackSlotAtInterval - assign a register if one
195 /// is available, or spill.
196 void assignRegOrStackSlotAtInterval(LiveInterval
* cur
);
198 void updateSpillWeights(std::vector
<float> &Weights
,
199 unsigned reg
, float weight
,
200 const TargetRegisterClass
*RC
);
202 /// findIntervalsToSpill - Determine the intervals to spill for the
203 /// specified interval. It's passed the physical registers whose spill
204 /// weight is the lowest among all the registers whose live intervals
205 /// conflict with the interval.
206 void findIntervalsToSpill(LiveInterval
*cur
,
207 std::vector
<std::pair
<unsigned,float> > &Candidates
,
209 SmallVector
<LiveInterval
*, 8> &SpillIntervals
);
211 /// attemptTrivialCoalescing - If a simple interval is defined by a copy,
212 /// try allocate the definition the same register as the source register
213 /// if the register is not defined during live time of the interval. This
214 /// eliminate a copy. This is used to coalesce copies which were not
215 /// coalesced away before allocation either due to dest and src being in
216 /// different register classes or because the coalescer was overly
218 unsigned attemptTrivialCoalescing(LiveInterval
&cur
, unsigned Reg
);
221 /// Register usage / availability tracking helpers.
225 regUse_
.resize(tri_
->getNumRegs(), 0);
226 regUseBackUp_
.resize(tri_
->getNumRegs(), 0);
229 void finalizeRegUses() {
231 // Verify all the registers are "freed".
233 for (unsigned i
= 0, e
= tri_
->getNumRegs(); i
!= e
; ++i
) {
234 if (regUse_
[i
] != 0) {
235 errs() << tri_
->getName(i
) << " is still in use!\n";
243 regUseBackUp_
.clear();
246 void addRegUse(unsigned physReg
) {
247 assert(TargetRegisterInfo::isPhysicalRegister(physReg
) &&
248 "should be physical register!");
250 for (const unsigned* as
= tri_
->getAliasSet(physReg
); *as
; ++as
)
254 void delRegUse(unsigned physReg
) {
255 assert(TargetRegisterInfo::isPhysicalRegister(physReg
) &&
256 "should be physical register!");
257 assert(regUse_
[physReg
] != 0);
259 for (const unsigned* as
= tri_
->getAliasSet(physReg
); *as
; ++as
) {
260 assert(regUse_
[*as
] != 0);
265 bool isRegAvail(unsigned physReg
) const {
266 assert(TargetRegisterInfo::isPhysicalRegister(physReg
) &&
267 "should be physical register!");
268 return regUse_
[physReg
] == 0;
271 void backUpRegUses() {
272 regUseBackUp_
= regUse_
;
275 void restoreRegUses() {
276 regUse_
= regUseBackUp_
;
280 /// Register handling helpers.
283 /// getFreePhysReg - return a free physical register for this virtual
284 /// register interval if we have one, otherwise return 0.
285 unsigned getFreePhysReg(LiveInterval
* cur
);
286 unsigned getFreePhysReg(LiveInterval
* cur
,
287 const TargetRegisterClass
*RC
,
288 unsigned MaxInactiveCount
,
289 SmallVector
<unsigned, 256> &inactiveCounts
,
292 /// assignVirt2StackSlot - assigns this virtual register to a
293 /// stack slot. returns the stack slot
294 int assignVirt2StackSlot(unsigned virtReg
);
296 void ComputeRelatedRegClasses();
298 template <typename ItTy
>
299 void printIntervals(const char* const str
, ItTy i
, ItTy e
) const {
302 errs() << str
<< " intervals:\n";
304 for (; i
!= e
; ++i
) {
305 errs() << "\t" << *i
->first
<< " -> ";
307 unsigned reg
= i
->first
->reg
;
308 if (TargetRegisterInfo::isVirtualRegister(reg
))
309 reg
= vrm_
->getPhys(reg
);
311 errs() << tri_
->getName(reg
) << '\n';
316 char RALinScan::ID
= 0;
319 static RegisterPass
<RALinScan
>
320 X("linearscan-regalloc", "Linear Scan Register Allocator");
322 void RALinScan::ComputeRelatedRegClasses() {
323 // First pass, add all reg classes to the union, and determine at least one
324 // reg class that each register is in.
325 bool HasAliases
= false;
326 for (TargetRegisterInfo::regclass_iterator RCI
= tri_
->regclass_begin(),
327 E
= tri_
->regclass_end(); RCI
!= E
; ++RCI
) {
328 RelatedRegClasses
.insert(*RCI
);
329 for (TargetRegisterClass::iterator I
= (*RCI
)->begin(), E
= (*RCI
)->end();
331 HasAliases
= HasAliases
|| *tri_
->getAliasSet(*I
) != 0;
333 const TargetRegisterClass
*&PRC
= OneClassForEachPhysReg
[*I
];
335 // Already processed this register. Just make sure we know that
336 // multiple register classes share a register.
337 RelatedRegClasses
.unionSets(PRC
, *RCI
);
344 // Second pass, now that we know conservatively what register classes each reg
345 // belongs to, add info about aliases. We don't need to do this for targets
346 // without register aliases.
348 for (DenseMap
<unsigned, const TargetRegisterClass
*>::iterator
349 I
= OneClassForEachPhysReg
.begin(), E
= OneClassForEachPhysReg
.end();
351 for (const unsigned *AS
= tri_
->getAliasSet(I
->first
); *AS
; ++AS
)
352 RelatedRegClasses
.unionSets(I
->second
, OneClassForEachPhysReg
[*AS
]);
355 /// attemptTrivialCoalescing - If a simple interval is defined by a copy,
356 /// try allocate the definition the same register as the source register
357 /// if the register is not defined during live time of the interval. This
358 /// eliminate a copy. This is used to coalesce copies which were not
359 /// coalesced away before allocation either due to dest and src being in
360 /// different register classes or because the coalescer was overly
362 unsigned RALinScan::attemptTrivialCoalescing(LiveInterval
&cur
, unsigned Reg
) {
363 unsigned Preference
= vrm_
->getRegAllocPref(cur
.reg
);
364 if ((Preference
&& Preference
== Reg
) || !cur
.containsOneValue())
367 VNInfo
*vni
= cur
.begin()->valno
;
368 if ((vni
->def
== LiveIndex()) ||
369 vni
->isUnused() || !vni
->isDefAccurate())
371 MachineInstr
*CopyMI
= li_
->getInstructionFromIndex(vni
->def
);
372 unsigned SrcReg
, DstReg
, SrcSubReg
, DstSubReg
, PhysReg
;
374 !tii_
->isMoveInstr(*CopyMI
, SrcReg
, DstReg
, SrcSubReg
, DstSubReg
))
377 if (TargetRegisterInfo::isVirtualRegister(SrcReg
)) {
378 if (!vrm_
->isAssignedReg(SrcReg
))
380 PhysReg
= vrm_
->getPhys(SrcReg
);
385 const TargetRegisterClass
*RC
= mri_
->getRegClass(cur
.reg
);
386 if (!RC
->contains(PhysReg
))
390 if (!li_
->conflictsWithPhysRegDef(cur
, *vrm_
, PhysReg
)) {
391 DEBUG(errs() << "Coalescing: " << cur
<< " -> " << tri_
->getName(PhysReg
)
393 vrm_
->clearVirt(cur
.reg
);
394 vrm_
->assignVirt2Phys(cur
.reg
, PhysReg
);
396 // Remove unnecessary kills since a copy does not clobber the register.
397 if (li_
->hasInterval(SrcReg
)) {
398 LiveInterval
&SrcLI
= li_
->getInterval(SrcReg
);
399 for (MachineRegisterInfo::use_iterator I
= mri_
->use_begin(cur
.reg
),
400 E
= mri_
->use_end(); I
!= E
; ++I
) {
401 MachineOperand
&O
= I
.getOperand();
404 MachineInstr
*MI
= &*I
;
405 if (SrcLI
.liveAt(li_
->getDefIndex(li_
->getInstructionIndex(MI
))))
417 bool RALinScan::runOnMachineFunction(MachineFunction
&fn
) {
419 mri_
= &fn
.getRegInfo();
420 tm_
= &fn
.getTarget();
421 tri_
= tm_
->getRegisterInfo();
422 tii_
= tm_
->getInstrInfo();
423 allocatableRegs_
= tri_
->getAllocatableSet(fn
);
424 li_
= &getAnalysis
<LiveIntervals
>();
425 ls_
= &getAnalysis
<LiveStacks
>();
426 loopInfo
= &getAnalysis
<MachineLoopInfo
>();
428 // We don't run the coalescer here because we have no reason to
429 // interact with it. If the coalescer requires interaction, it
430 // won't do anything. If it doesn't require interaction, we assume
431 // it was run as a separate pass.
433 // If this is the first function compiled, compute the related reg classes.
434 if (RelatedRegClasses
.empty())
435 ComputeRelatedRegClasses();
437 // Also resize register usage trackers.
440 vrm_
= &getAnalysis
<VirtRegMap
>();
441 if (!rewriter_
.get()) rewriter_
.reset(createVirtRegRewriter());
443 if (NewSpillFramework
) {
444 spiller_
.reset(createSpiller(mf_
, li_
, ls_
, vrm_
));
451 // Rewrite spill code and update the PhysRegsUsed set.
452 rewriter_
->runOnMachineFunction(*mf_
, *vrm_
, li_
);
454 assert(unhandled_
.empty() && "Unhandled live intervals remain!");
462 NextReloadMap
.clear();
463 DowngradedRegs
.clear();
464 DowngradeMap
.clear();
470 /// initIntervalSets - initialize the interval sets.
472 void RALinScan::initIntervalSets()
474 assert(unhandled_
.empty() && fixed_
.empty() &&
475 active_
.empty() && inactive_
.empty() &&
476 "interval sets should be empty on initialization");
478 handled_
.reserve(li_
->getNumIntervals());
480 for (LiveIntervals::iterator i
= li_
->begin(), e
= li_
->end(); i
!= e
; ++i
) {
481 if (TargetRegisterInfo::isPhysicalRegister(i
->second
->reg
)) {
482 mri_
->setPhysRegUsed(i
->second
->reg
);
483 fixed_
.push_back(std::make_pair(i
->second
, i
->second
->begin()));
485 unhandled_
.push(i
->second
);
489 void RALinScan::linearScan() {
490 // linear scan algorithm
492 errs() << "********** LINEAR SCAN **********\n"
493 << "********** Function: "
494 << mf_
->getFunction()->getName() << '\n';
495 printIntervals("fixed", fixed_
.begin(), fixed_
.end());
498 while (!unhandled_
.empty()) {
499 // pick the interval with the earliest start point
500 LiveInterval
* cur
= unhandled_
.top();
503 DEBUG(errs() << "\n*** CURRENT ***: " << *cur
<< '\n');
506 processActiveIntervals(cur
->beginIndex());
507 processInactiveIntervals(cur
->beginIndex());
509 assert(TargetRegisterInfo::isVirtualRegister(cur
->reg
) &&
510 "Can only allocate virtual registers!");
513 // Allocating a virtual register. try to find a free
514 // physical register or spill an interval (possibly this one) in order to
516 assignRegOrStackSlotAtInterval(cur
);
519 printIntervals("active", active_
.begin(), active_
.end());
520 printIntervals("inactive", inactive_
.begin(), inactive_
.end());
524 // Expire any remaining active intervals
525 while (!active_
.empty()) {
526 IntervalPtr
&IP
= active_
.back();
527 unsigned reg
= IP
.first
->reg
;
528 DEBUG(errs() << "\tinterval " << *IP
.first
<< " expired\n");
529 assert(TargetRegisterInfo::isVirtualRegister(reg
) &&
530 "Can only allocate virtual registers!");
531 reg
= vrm_
->getPhys(reg
);
536 // Expire any remaining inactive intervals
538 for (IntervalPtrs::reverse_iterator
539 i
= inactive_
.rbegin(); i
!= inactive_
.rend(); ++i
)
540 errs() << "\tinterval " << *i
->first
<< " expired\n";
544 // Add live-ins to every BB except for entry. Also perform trivial coalescing.
545 MachineFunction::iterator EntryMBB
= mf_
->begin();
546 SmallVector
<MachineBasicBlock
*, 8> LiveInMBBs
;
547 for (LiveIntervals::iterator i
= li_
->begin(), e
= li_
->end(); i
!= e
; ++i
) {
548 LiveInterval
&cur
= *i
->second
;
550 bool isPhys
= TargetRegisterInfo::isPhysicalRegister(cur
.reg
);
553 else if (vrm_
->isAssignedReg(cur
.reg
))
554 Reg
= attemptTrivialCoalescing(cur
, vrm_
->getPhys(cur
.reg
));
557 // Ignore splited live intervals.
558 if (!isPhys
&& vrm_
->getPreSplitReg(cur
.reg
))
561 for (LiveInterval::Ranges::const_iterator I
= cur
.begin(), E
= cur
.end();
563 const LiveRange
&LR
= *I
;
564 if (li_
->findLiveInMBBs(LR
.start
, LR
.end
, LiveInMBBs
)) {
565 for (unsigned i
= 0, e
= LiveInMBBs
.size(); i
!= e
; ++i
)
566 if (LiveInMBBs
[i
] != EntryMBB
) {
567 assert(TargetRegisterInfo::isPhysicalRegister(Reg
) &&
568 "Adding a virtual register to livein set?");
569 LiveInMBBs
[i
]->addLiveIn(Reg
);
576 DEBUG(errs() << *vrm_
);
578 // Look for physical registers that end up not being allocated even though
579 // register allocator had to spill other registers in its register class.
580 if (ls_
->getNumIntervals() == 0)
582 if (!vrm_
->FindUnusedRegisters(li_
))
586 /// processActiveIntervals - expire old intervals and move non-overlapping ones
587 /// to the inactive list.
588 void RALinScan::processActiveIntervals(LiveIndex CurPoint
)
590 DEBUG(errs() << "\tprocessing active intervals:\n");
592 for (unsigned i
= 0, e
= active_
.size(); i
!= e
; ++i
) {
593 LiveInterval
*Interval
= active_
[i
].first
;
594 LiveInterval::iterator IntervalPos
= active_
[i
].second
;
595 unsigned reg
= Interval
->reg
;
597 IntervalPos
= Interval
->advanceTo(IntervalPos
, CurPoint
);
599 if (IntervalPos
== Interval
->end()) { // Remove expired intervals.
600 DEBUG(errs() << "\t\tinterval " << *Interval
<< " expired\n");
601 assert(TargetRegisterInfo::isVirtualRegister(reg
) &&
602 "Can only allocate virtual registers!");
603 reg
= vrm_
->getPhys(reg
);
606 // Pop off the end of the list.
607 active_
[i
] = active_
.back();
611 } else if (IntervalPos
->start
> CurPoint
) {
612 // Move inactive intervals to inactive list.
613 DEBUG(errs() << "\t\tinterval " << *Interval
<< " inactive\n");
614 assert(TargetRegisterInfo::isVirtualRegister(reg
) &&
615 "Can only allocate virtual registers!");
616 reg
= vrm_
->getPhys(reg
);
619 inactive_
.push_back(std::make_pair(Interval
, IntervalPos
));
621 // Pop off the end of the list.
622 active_
[i
] = active_
.back();
626 // Otherwise, just update the iterator position.
627 active_
[i
].second
= IntervalPos
;
632 /// processInactiveIntervals - expire old intervals and move overlapping
633 /// ones to the active list.
634 void RALinScan::processInactiveIntervals(LiveIndex CurPoint
)
636 DEBUG(errs() << "\tprocessing inactive intervals:\n");
638 for (unsigned i
= 0, e
= inactive_
.size(); i
!= e
; ++i
) {
639 LiveInterval
*Interval
= inactive_
[i
].first
;
640 LiveInterval::iterator IntervalPos
= inactive_
[i
].second
;
641 unsigned reg
= Interval
->reg
;
643 IntervalPos
= Interval
->advanceTo(IntervalPos
, CurPoint
);
645 if (IntervalPos
== Interval
->end()) { // remove expired intervals.
646 DEBUG(errs() << "\t\tinterval " << *Interval
<< " expired\n");
648 // Pop off the end of the list.
649 inactive_
[i
] = inactive_
.back();
650 inactive_
.pop_back();
652 } else if (IntervalPos
->start
<= CurPoint
) {
653 // move re-activated intervals in active list
654 DEBUG(errs() << "\t\tinterval " << *Interval
<< " active\n");
655 assert(TargetRegisterInfo::isVirtualRegister(reg
) &&
656 "Can only allocate virtual registers!");
657 reg
= vrm_
->getPhys(reg
);
660 active_
.push_back(std::make_pair(Interval
, IntervalPos
));
662 // Pop off the end of the list.
663 inactive_
[i
] = inactive_
.back();
664 inactive_
.pop_back();
667 // Otherwise, just update the iterator position.
668 inactive_
[i
].second
= IntervalPos
;
673 /// updateSpillWeights - updates the spill weights of the specifed physical
674 /// register and its weight.
675 void RALinScan::updateSpillWeights(std::vector
<float> &Weights
,
676 unsigned reg
, float weight
,
677 const TargetRegisterClass
*RC
) {
678 SmallSet
<unsigned, 4> Processed
;
679 SmallSet
<unsigned, 4> SuperAdded
;
680 SmallVector
<unsigned, 4> Supers
;
681 Weights
[reg
] += weight
;
682 Processed
.insert(reg
);
683 for (const unsigned* as
= tri_
->getAliasSet(reg
); *as
; ++as
) {
684 Weights
[*as
] += weight
;
685 Processed
.insert(*as
);
686 if (tri_
->isSubRegister(*as
, reg
) &&
687 SuperAdded
.insert(*as
) &&
689 Supers
.push_back(*as
);
693 // If the alias is a super-register, and the super-register is in the
694 // register class we are trying to allocate. Then add the weight to all
695 // sub-registers of the super-register even if they are not aliases.
696 // e.g. allocating for GR32, bh is not used, updating bl spill weight.
697 // bl should get the same spill weight otherwise it will be choosen
698 // as a spill candidate since spilling bh doesn't make ebx available.
699 for (unsigned i
= 0, e
= Supers
.size(); i
!= e
; ++i
) {
700 for (const unsigned *sr
= tri_
->getSubRegisters(Supers
[i
]); *sr
; ++sr
)
701 if (!Processed
.count(*sr
))
702 Weights
[*sr
] += weight
;
707 RALinScan::IntervalPtrs::iterator
708 FindIntervalInVector(RALinScan::IntervalPtrs
&IP
, LiveInterval
*LI
) {
709 for (RALinScan::IntervalPtrs::iterator I
= IP
.begin(), E
= IP
.end();
711 if (I
->first
== LI
) return I
;
715 static void RevertVectorIteratorsTo(RALinScan::IntervalPtrs
&V
, LiveIndex Point
){
716 for (unsigned i
= 0, e
= V
.size(); i
!= e
; ++i
) {
717 RALinScan::IntervalPtr
&IP
= V
[i
];
718 LiveInterval::iterator I
= std::upper_bound(IP
.first
->begin(),
720 if (I
!= IP
.first
->begin()) --I
;
725 /// addStackInterval - Create a LiveInterval for stack if the specified live
726 /// interval has been spilled.
727 static void addStackInterval(LiveInterval
*cur
, LiveStacks
*ls_
,
729 MachineRegisterInfo
* mri_
, VirtRegMap
&vrm_
) {
730 int SS
= vrm_
.getStackSlot(cur
->reg
);
731 if (SS
== VirtRegMap::NO_STACK_SLOT
)
734 const TargetRegisterClass
*RC
= mri_
->getRegClass(cur
->reg
);
735 LiveInterval
&SI
= ls_
->getOrCreateInterval(SS
, RC
);
738 if (SI
.hasAtLeastOneValue())
739 VNI
= SI
.getValNumInfo(0);
741 VNI
= SI
.getNextValue(LiveIndex(), 0, false,
742 ls_
->getVNInfoAllocator());
744 LiveInterval
&RI
= li_
->getInterval(cur
->reg
);
745 // FIXME: This may be overly conservative.
746 SI
.MergeRangesInAsValue(RI
, VNI
);
749 /// getConflictWeight - Return the number of conflicts between cur
750 /// live interval and defs and uses of Reg weighted by loop depthes.
752 float getConflictWeight(LiveInterval
*cur
, unsigned Reg
, LiveIntervals
*li_
,
753 MachineRegisterInfo
*mri_
,
754 const MachineLoopInfo
*loopInfo
) {
756 for (MachineRegisterInfo::reg_iterator I
= mri_
->reg_begin(Reg
),
757 E
= mri_
->reg_end(); I
!= E
; ++I
) {
758 MachineInstr
*MI
= &*I
;
759 if (cur
->liveAt(li_
->getInstructionIndex(MI
))) {
760 unsigned loopDepth
= loopInfo
->getLoopDepth(MI
->getParent());
761 Conflicts
+= powf(10.0f
, (float)loopDepth
);
767 /// findIntervalsToSpill - Determine the intervals to spill for the
768 /// specified interval. It's passed the physical registers whose spill
769 /// weight is the lowest among all the registers whose live intervals
770 /// conflict with the interval.
771 void RALinScan::findIntervalsToSpill(LiveInterval
*cur
,
772 std::vector
<std::pair
<unsigned,float> > &Candidates
,
774 SmallVector
<LiveInterval
*, 8> &SpillIntervals
) {
775 // We have figured out the *best* register to spill. But there are other
776 // registers that are pretty good as well (spill weight within 3%). Spill
777 // the one that has fewest defs and uses that conflict with cur.
778 float Conflicts
[3] = { 0.0f
, 0.0f
, 0.0f
};
779 SmallVector
<LiveInterval
*, 8> SLIs
[3];
782 errs() << "\tConsidering " << NumCands
<< " candidates: ";
783 for (unsigned i
= 0; i
!= NumCands
; ++i
)
784 errs() << tri_
->getName(Candidates
[i
].first
) << " ";
788 // Calculate the number of conflicts of each candidate.
789 for (IntervalPtrs::iterator i
= active_
.begin(); i
!= active_
.end(); ++i
) {
790 unsigned Reg
= i
->first
->reg
;
791 unsigned PhysReg
= vrm_
->getPhys(Reg
);
792 if (!cur
->overlapsFrom(*i
->first
, i
->second
))
794 for (unsigned j
= 0; j
< NumCands
; ++j
) {
795 unsigned Candidate
= Candidates
[j
].first
;
796 if (tri_
->regsOverlap(PhysReg
, Candidate
)) {
798 Conflicts
[j
] += getConflictWeight(cur
, Reg
, li_
, mri_
, loopInfo
);
799 SLIs
[j
].push_back(i
->first
);
804 for (IntervalPtrs::iterator i
= inactive_
.begin(); i
!= inactive_
.end(); ++i
){
805 unsigned Reg
= i
->first
->reg
;
806 unsigned PhysReg
= vrm_
->getPhys(Reg
);
807 if (!cur
->overlapsFrom(*i
->first
, i
->second
-1))
809 for (unsigned j
= 0; j
< NumCands
; ++j
) {
810 unsigned Candidate
= Candidates
[j
].first
;
811 if (tri_
->regsOverlap(PhysReg
, Candidate
)) {
813 Conflicts
[j
] += getConflictWeight(cur
, Reg
, li_
, mri_
, loopInfo
);
814 SLIs
[j
].push_back(i
->first
);
819 // Which is the best candidate?
820 unsigned BestCandidate
= 0;
821 float MinConflicts
= Conflicts
[0];
822 for (unsigned i
= 1; i
!= NumCands
; ++i
) {
823 if (Conflicts
[i
] < MinConflicts
) {
825 MinConflicts
= Conflicts
[i
];
829 std::copy(SLIs
[BestCandidate
].begin(), SLIs
[BestCandidate
].end(),
830 std::back_inserter(SpillIntervals
));
834 struct WeightCompare
{
835 typedef std::pair
<unsigned, float> RegWeightPair
;
836 bool operator()(const RegWeightPair
&LHS
, const RegWeightPair
&RHS
) const {
837 return LHS
.second
< RHS
.second
;
842 static bool weightsAreClose(float w1
, float w2
) {
846 float diff
= w1
- w2
;
847 if (diff
<= 0.02f
) // Within 0.02f
849 return (diff
/ w2
) <= 0.05f
; // Within 5%.
852 LiveInterval
*RALinScan::hasNextReloadInterval(LiveInterval
*cur
) {
853 DenseMap
<unsigned, unsigned>::iterator I
= NextReloadMap
.find(cur
->reg
);
854 if (I
== NextReloadMap
.end())
856 return &li_
->getInterval(I
->second
);
859 void RALinScan::DowngradeRegister(LiveInterval
*li
, unsigned Reg
) {
860 bool isNew
= DowngradedRegs
.insert(Reg
);
861 isNew
= isNew
; // Silence compiler warning.
862 assert(isNew
&& "Multiple reloads holding the same register?");
863 DowngradeMap
.insert(std::make_pair(li
->reg
, Reg
));
864 for (const unsigned *AS
= tri_
->getAliasSet(Reg
); *AS
; ++AS
) {
865 isNew
= DowngradedRegs
.insert(*AS
);
866 isNew
= isNew
; // Silence compiler warning.
867 assert(isNew
&& "Multiple reloads holding the same register?");
868 DowngradeMap
.insert(std::make_pair(li
->reg
, *AS
));
873 void RALinScan::UpgradeRegister(unsigned Reg
) {
875 DowngradedRegs
.erase(Reg
);
876 for (const unsigned *AS
= tri_
->getAliasSet(Reg
); *AS
; ++AS
)
877 DowngradedRegs
.erase(*AS
);
883 bool operator()(LiveInterval
* A
, LiveInterval
* B
) {
884 return A
->beginIndex() < B
->beginIndex();
889 /// assignRegOrStackSlotAtInterval - assign a register if one is available, or
891 void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval
* cur
) {
892 DEBUG(errs() << "\tallocating current interval: ");
894 // This is an implicitly defined live interval, just assign any register.
895 const TargetRegisterClass
*RC
= mri_
->getRegClass(cur
->reg
);
897 unsigned physReg
= vrm_
->getRegAllocPref(cur
->reg
);
899 physReg
= *RC
->allocation_order_begin(*mf_
);
900 DEBUG(errs() << tri_
->getName(physReg
) << '\n');
901 // Note the register is not really in use.
902 vrm_
->assignVirt2Phys(cur
->reg
, physReg
);
908 std::vector
<std::pair
<unsigned, float> > SpillWeightsToAdd
;
909 LiveIndex StartPosition
= cur
->beginIndex();
910 const TargetRegisterClass
*RCLeader
= RelatedRegClasses
.getLeaderValue(RC
);
912 // If start of this live interval is defined by a move instruction and its
913 // source is assigned a physical register that is compatible with the target
914 // register class, then we should try to assign it the same register.
915 // This can happen when the move is from a larger register class to a smaller
916 // one, e.g. X86::mov32to32_. These move instructions are not coalescable.
917 if (!vrm_
->getRegAllocPref(cur
->reg
) && cur
->hasAtLeastOneValue()) {
918 VNInfo
*vni
= cur
->begin()->valno
;
919 if ((vni
->def
!= LiveIndex()) && !vni
->isUnused() &&
920 vni
->isDefAccurate()) {
921 MachineInstr
*CopyMI
= li_
->getInstructionFromIndex(vni
->def
);
922 unsigned SrcReg
, DstReg
, SrcSubReg
, DstSubReg
;
924 tii_
->isMoveInstr(*CopyMI
, SrcReg
, DstReg
, SrcSubReg
, DstSubReg
)) {
926 if (TargetRegisterInfo::isPhysicalRegister(SrcReg
))
928 else if (vrm_
->isAssignedReg(SrcReg
))
929 Reg
= vrm_
->getPhys(SrcReg
);
932 Reg
= tri_
->getSubReg(Reg
, SrcSubReg
);
934 Reg
= tri_
->getMatchingSuperReg(Reg
, DstSubReg
, RC
);
935 if (Reg
&& allocatableRegs_
[Reg
] && RC
->contains(Reg
))
936 mri_
->setRegAllocationHint(cur
->reg
, 0, Reg
);
942 // For every interval in inactive we overlap with, mark the
943 // register as not free and update spill weights.
944 for (IntervalPtrs::const_iterator i
= inactive_
.begin(),
945 e
= inactive_
.end(); i
!= e
; ++i
) {
946 unsigned Reg
= i
->first
->reg
;
947 assert(TargetRegisterInfo::isVirtualRegister(Reg
) &&
948 "Can only allocate virtual registers!");
949 const TargetRegisterClass
*RegRC
= mri_
->getRegClass(Reg
);
950 // If this is not in a related reg class to the register we're allocating,
952 if (RelatedRegClasses
.getLeaderValue(RegRC
) == RCLeader
&&
953 cur
->overlapsFrom(*i
->first
, i
->second
-1)) {
954 Reg
= vrm_
->getPhys(Reg
);
956 SpillWeightsToAdd
.push_back(std::make_pair(Reg
, i
->first
->weight
));
960 // Speculatively check to see if we can get a register right now. If not,
961 // we know we won't be able to by adding more constraints. If so, we can
962 // check to see if it is valid. Doing an exhaustive search of the fixed_ list
963 // is very bad (it contains all callee clobbered registers for any functions
964 // with a call), so we want to avoid doing that if possible.
965 unsigned physReg
= getFreePhysReg(cur
);
966 unsigned BestPhysReg
= physReg
;
968 // We got a register. However, if it's in the fixed_ list, we might
969 // conflict with it. Check to see if we conflict with it or any of its
971 SmallSet
<unsigned, 8> RegAliases
;
972 for (const unsigned *AS
= tri_
->getAliasSet(physReg
); *AS
; ++AS
)
973 RegAliases
.insert(*AS
);
975 bool ConflictsWithFixed
= false;
976 for (unsigned i
= 0, e
= fixed_
.size(); i
!= e
; ++i
) {
977 IntervalPtr
&IP
= fixed_
[i
];
978 if (physReg
== IP
.first
->reg
|| RegAliases
.count(IP
.first
->reg
)) {
979 // Okay, this reg is on the fixed list. Check to see if we actually
981 LiveInterval
*I
= IP
.first
;
982 if (I
->endIndex() > StartPosition
) {
983 LiveInterval::iterator II
= I
->advanceTo(IP
.second
, StartPosition
);
985 if (II
!= I
->begin() && II
->start
> StartPosition
)
987 if (cur
->overlapsFrom(*I
, II
)) {
988 ConflictsWithFixed
= true;
995 // Okay, the register picked by our speculative getFreePhysReg call turned
996 // out to be in use. Actually add all of the conflicting fixed registers to
997 // regUse_ so we can do an accurate query.
998 if (ConflictsWithFixed
) {
999 // For every interval in fixed we overlap with, mark the register as not
1000 // free and update spill weights.
1001 for (unsigned i
= 0, e
= fixed_
.size(); i
!= e
; ++i
) {
1002 IntervalPtr
&IP
= fixed_
[i
];
1003 LiveInterval
*I
= IP
.first
;
1005 const TargetRegisterClass
*RegRC
= OneClassForEachPhysReg
[I
->reg
];
1006 if (RelatedRegClasses
.getLeaderValue(RegRC
) == RCLeader
&&
1007 I
->endIndex() > StartPosition
) {
1008 LiveInterval::iterator II
= I
->advanceTo(IP
.second
, StartPosition
);
1010 if (II
!= I
->begin() && II
->start
> StartPosition
)
1012 if (cur
->overlapsFrom(*I
, II
)) {
1013 unsigned reg
= I
->reg
;
1015 SpillWeightsToAdd
.push_back(std::make_pair(reg
, I
->weight
));
1020 // Using the newly updated regUse_ object, which includes conflicts in the
1021 // future, see if there are any registers available.
1022 physReg
= getFreePhysReg(cur
);
1026 // Restore the physical register tracker, removing information about the
1030 // If we find a free register, we are done: assign this virtual to
1031 // the free physical register and add this interval to the active
1034 DEBUG(errs() << tri_
->getName(physReg
) << '\n');
1035 vrm_
->assignVirt2Phys(cur
->reg
, physReg
);
1037 active_
.push_back(std::make_pair(cur
, cur
->begin()));
1038 handled_
.push_back(cur
);
1040 // "Upgrade" the physical register since it has been allocated.
1041 UpgradeRegister(physReg
);
1042 if (LiveInterval
*NextReloadLI
= hasNextReloadInterval(cur
)) {
1043 // "Downgrade" physReg to try to keep physReg from being allocated until
1044 // the next reload from the same SS is allocated.
1045 mri_
->setRegAllocationHint(NextReloadLI
->reg
, 0, physReg
);
1046 DowngradeRegister(cur
, physReg
);
1050 DEBUG(errs() << "no free registers\n");
1052 // Compile the spill weights into an array that is better for scanning.
1053 std::vector
<float> SpillWeights(tri_
->getNumRegs(), 0.0f
);
1054 for (std::vector
<std::pair
<unsigned, float> >::iterator
1055 I
= SpillWeightsToAdd
.begin(), E
= SpillWeightsToAdd
.end(); I
!= E
; ++I
)
1056 updateSpillWeights(SpillWeights
, I
->first
, I
->second
, RC
);
1058 // for each interval in active, update spill weights.
1059 for (IntervalPtrs::const_iterator i
= active_
.begin(), e
= active_
.end();
1061 unsigned reg
= i
->first
->reg
;
1062 assert(TargetRegisterInfo::isVirtualRegister(reg
) &&
1063 "Can only allocate virtual registers!");
1064 reg
= vrm_
->getPhys(reg
);
1065 updateSpillWeights(SpillWeights
, reg
, i
->first
->weight
, RC
);
1068 DEBUG(errs() << "\tassigning stack slot at interval "<< *cur
<< ":\n");
1070 // Find a register to spill.
1071 float minWeight
= HUGE_VALF
;
1072 unsigned minReg
= 0;
1075 std::vector
<std::pair
<unsigned,float> > RegsWeights
;
1076 if (!minReg
|| SpillWeights
[minReg
] == HUGE_VALF
)
1077 for (TargetRegisterClass::iterator i
= RC
->allocation_order_begin(*mf_
),
1078 e
= RC
->allocation_order_end(*mf_
); i
!= e
; ++i
) {
1080 float regWeight
= SpillWeights
[reg
];
1081 if (minWeight
> regWeight
)
1083 RegsWeights
.push_back(std::make_pair(reg
, regWeight
));
1086 // If we didn't find a register that is spillable, try aliases?
1088 for (TargetRegisterClass::iterator i
= RC
->allocation_order_begin(*mf_
),
1089 e
= RC
->allocation_order_end(*mf_
); i
!= e
; ++i
) {
1091 // No need to worry about if the alias register size < regsize of RC.
1092 // We are going to spill all registers that alias it anyway.
1093 for (const unsigned* as
= tri_
->getAliasSet(reg
); *as
; ++as
)
1094 RegsWeights
.push_back(std::make_pair(*as
, SpillWeights
[*as
]));
1098 // Sort all potential spill candidates by weight.
1099 std::sort(RegsWeights
.begin(), RegsWeights
.end(), WeightCompare());
1100 minReg
= RegsWeights
[0].first
;
1101 minWeight
= RegsWeights
[0].second
;
1102 if (minWeight
== HUGE_VALF
) {
1103 // All registers must have inf weight. Just grab one!
1104 minReg
= BestPhysReg
? BestPhysReg
: *RC
->allocation_order_begin(*mf_
);
1105 if (cur
->weight
== HUGE_VALF
||
1106 li_
->getApproximateInstructionCount(*cur
) == 0) {
1107 // Spill a physical register around defs and uses.
1108 if (li_
->spillPhysRegAroundRegDefsUses(*cur
, minReg
, *vrm_
)) {
1109 // spillPhysRegAroundRegDefsUses may have invalidated iterator stored
1110 // in fixed_. Reset them.
1111 for (unsigned i
= 0, e
= fixed_
.size(); i
!= e
; ++i
) {
1112 IntervalPtr
&IP
= fixed_
[i
];
1113 LiveInterval
*I
= IP
.first
;
1114 if (I
->reg
== minReg
|| tri_
->isSubRegister(minReg
, I
->reg
))
1115 IP
.second
= I
->advanceTo(I
->begin(), StartPosition
);
1118 DowngradedRegs
.clear();
1119 assignRegOrStackSlotAtInterval(cur
);
1121 llvm_report_error("Ran out of registers during register allocation!");
1127 // Find up to 3 registers to consider as spill candidates.
1128 unsigned LastCandidate
= RegsWeights
.size() >= 3 ? 3 : 1;
1129 while (LastCandidate
> 1) {
1130 if (weightsAreClose(RegsWeights
[LastCandidate
-1].second
, minWeight
))
1136 errs() << "\t\tregister(s) with min weight(s): ";
1138 for (unsigned i
= 0; i
!= LastCandidate
; ++i
)
1139 errs() << tri_
->getName(RegsWeights
[i
].first
)
1140 << " (" << RegsWeights
[i
].second
<< ")\n";
1143 // If the current has the minimum weight, we need to spill it and
1144 // add any added intervals back to unhandled, and restart
1146 if (cur
->weight
!= HUGE_VALF
&& cur
->weight
<= minWeight
) {
1147 DEBUG(errs() << "\t\t\tspilling(c): " << *cur
<< '\n');
1148 SmallVector
<LiveInterval
*, 8> spillIs
;
1149 std::vector
<LiveInterval
*> added
;
1151 if (!NewSpillFramework
) {
1152 added
= li_
->addIntervalsForSpills(*cur
, spillIs
, loopInfo
, *vrm_
);
1154 added
= spiller_
->spill(cur
);
1157 std::sort(added
.begin(), added
.end(), LISorter());
1158 addStackInterval(cur
, ls_
, li_
, mri_
, *vrm_
);
1160 return; // Early exit if all spills were folded.
1162 // Merge added with unhandled. Note that we have already sorted
1163 // intervals returned by addIntervalsForSpills by their starting
1165 // This also update the NextReloadMap. That is, it adds mapping from a
1166 // register defined by a reload from SS to the next reload from SS in the
1167 // same basic block.
1168 MachineBasicBlock
*LastReloadMBB
= 0;
1169 LiveInterval
*LastReload
= 0;
1170 int LastReloadSS
= VirtRegMap::NO_STACK_SLOT
;
1171 for (unsigned i
= 0, e
= added
.size(); i
!= e
; ++i
) {
1172 LiveInterval
*ReloadLi
= added
[i
];
1173 if (ReloadLi
->weight
== HUGE_VALF
&&
1174 li_
->getApproximateInstructionCount(*ReloadLi
) == 0) {
1175 LiveIndex ReloadIdx
= ReloadLi
->beginIndex();
1176 MachineBasicBlock
*ReloadMBB
= li_
->getMBBFromIndex(ReloadIdx
);
1177 int ReloadSS
= vrm_
->getStackSlot(ReloadLi
->reg
);
1178 if (LastReloadMBB
== ReloadMBB
&& LastReloadSS
== ReloadSS
) {
1179 // Last reload of same SS is in the same MBB. We want to try to
1180 // allocate both reloads the same register and make sure the reg
1181 // isn't clobbered in between if at all possible.
1182 assert(LastReload
->beginIndex() < ReloadIdx
);
1183 NextReloadMap
.insert(std::make_pair(LastReload
->reg
, ReloadLi
->reg
));
1185 LastReloadMBB
= ReloadMBB
;
1186 LastReload
= ReloadLi
;
1187 LastReloadSS
= ReloadSS
;
1189 unhandled_
.push(ReloadLi
);
1196 // Push the current interval back to unhandled since we are going
1197 // to re-run at least this iteration. Since we didn't modify it it
1198 // should go back right in the front of the list
1199 unhandled_
.push(cur
);
1201 assert(TargetRegisterInfo::isPhysicalRegister(minReg
) &&
1202 "did not choose a register to spill?");
1204 // We spill all intervals aliasing the register with
1205 // minimum weight, rollback to the interval with the earliest
1206 // start point and let the linear scan algorithm run again
1207 SmallVector
<LiveInterval
*, 8> spillIs
;
1209 // Determine which intervals have to be spilled.
1210 findIntervalsToSpill(cur
, RegsWeights
, LastCandidate
, spillIs
);
1212 // Set of spilled vregs (used later to rollback properly)
1213 SmallSet
<unsigned, 8> spilled
;
1215 // The earliest start of a Spilled interval indicates up to where
1216 // in handled we need to roll back
1218 LiveInterval
*earliestStartInterval
= cur
;
1220 // Spill live intervals of virtual regs mapped to the physical register we
1221 // want to clear (and its aliases). We only spill those that overlap with the
1222 // current interval as the rest do not affect its allocation. we also keep
1223 // track of the earliest start of all spilled live intervals since this will
1224 // mark our rollback point.
1225 std::vector
<LiveInterval
*> added
;
1226 while (!spillIs
.empty()) {
1227 LiveInterval
*sli
= spillIs
.back();
1229 DEBUG(errs() << "\t\t\tspilling(a): " << *sli
<< '\n');
1230 earliestStartInterval
=
1231 (earliestStartInterval
->beginIndex() < sli
->beginIndex()) ?
1232 earliestStartInterval
: sli
;
1234 std::vector
<LiveInterval
*> newIs
;
1235 if (!NewSpillFramework
) {
1236 newIs
= li_
->addIntervalsForSpills(*sli
, spillIs
, loopInfo
, *vrm_
);
1238 newIs
= spiller_
->spill(sli
);
1240 addStackInterval(sli
, ls_
, li_
, mri_
, *vrm_
);
1241 std::copy(newIs
.begin(), newIs
.end(), std::back_inserter(added
));
1242 spilled
.insert(sli
->reg
);
1245 LiveIndex earliestStart
= earliestStartInterval
->beginIndex();
1247 DEBUG(errs() << "\t\trolling back to: " << earliestStart
<< '\n');
1249 // Scan handled in reverse order up to the earliest start of a
1250 // spilled live interval and undo each one, restoring the state of
1252 while (!handled_
.empty()) {
1253 LiveInterval
* i
= handled_
.back();
1254 // If this interval starts before t we are done.
1255 if (i
->beginIndex() < earliestStart
)
1257 DEBUG(errs() << "\t\t\tundo changes for: " << *i
<< '\n');
1258 handled_
.pop_back();
1260 // When undoing a live interval allocation we must know if it is active or
1261 // inactive to properly update regUse_ and the VirtRegMap.
1262 IntervalPtrs::iterator it
;
1263 if ((it
= FindIntervalInVector(active_
, i
)) != active_
.end()) {
1265 assert(!TargetRegisterInfo::isPhysicalRegister(i
->reg
));
1266 if (!spilled
.count(i
->reg
))
1268 delRegUse(vrm_
->getPhys(i
->reg
));
1269 vrm_
->clearVirt(i
->reg
);
1270 } else if ((it
= FindIntervalInVector(inactive_
, i
)) != inactive_
.end()) {
1271 inactive_
.erase(it
);
1272 assert(!TargetRegisterInfo::isPhysicalRegister(i
->reg
));
1273 if (!spilled
.count(i
->reg
))
1275 vrm_
->clearVirt(i
->reg
);
1277 assert(TargetRegisterInfo::isVirtualRegister(i
->reg
) &&
1278 "Can only allocate virtual registers!");
1279 vrm_
->clearVirt(i
->reg
);
1283 DenseMap
<unsigned, unsigned>::iterator ii
= DowngradeMap
.find(i
->reg
);
1284 if (ii
== DowngradeMap
.end())
1285 // It interval has a preference, it must be defined by a copy. Clear the
1286 // preference now since the source interval allocation may have been
1288 mri_
->setRegAllocationHint(i
->reg
, 0, 0);
1290 UpgradeRegister(ii
->second
);
1294 // Rewind the iterators in the active, inactive, and fixed lists back to the
1295 // point we reverted to.
1296 RevertVectorIteratorsTo(active_
, earliestStart
);
1297 RevertVectorIteratorsTo(inactive_
, earliestStart
);
1298 RevertVectorIteratorsTo(fixed_
, earliestStart
);
1300 // Scan the rest and undo each interval that expired after t and
1301 // insert it in active (the next iteration of the algorithm will
1302 // put it in inactive if required)
1303 for (unsigned i
= 0, e
= handled_
.size(); i
!= e
; ++i
) {
1304 LiveInterval
*HI
= handled_
[i
];
1305 if (!HI
->expiredAt(earliestStart
) &&
1306 HI
->expiredAt(cur
->beginIndex())) {
1307 DEBUG(errs() << "\t\t\tundo changes for: " << *HI
<< '\n');
1308 active_
.push_back(std::make_pair(HI
, HI
->begin()));
1309 assert(!TargetRegisterInfo::isPhysicalRegister(HI
->reg
));
1310 addRegUse(vrm_
->getPhys(HI
->reg
));
1314 // Merge added with unhandled.
1315 // This also update the NextReloadMap. That is, it adds mapping from a
1316 // register defined by a reload from SS to the next reload from SS in the
1317 // same basic block.
1318 MachineBasicBlock
*LastReloadMBB
= 0;
1319 LiveInterval
*LastReload
= 0;
1320 int LastReloadSS
= VirtRegMap::NO_STACK_SLOT
;
1321 std::sort(added
.begin(), added
.end(), LISorter());
1322 for (unsigned i
= 0, e
= added
.size(); i
!= e
; ++i
) {
1323 LiveInterval
*ReloadLi
= added
[i
];
1324 if (ReloadLi
->weight
== HUGE_VALF
&&
1325 li_
->getApproximateInstructionCount(*ReloadLi
) == 0) {
1326 LiveIndex ReloadIdx
= ReloadLi
->beginIndex();
1327 MachineBasicBlock
*ReloadMBB
= li_
->getMBBFromIndex(ReloadIdx
);
1328 int ReloadSS
= vrm_
->getStackSlot(ReloadLi
->reg
);
1329 if (LastReloadMBB
== ReloadMBB
&& LastReloadSS
== ReloadSS
) {
1330 // Last reload of same SS is in the same MBB. We want to try to
1331 // allocate both reloads the same register and make sure the reg
1332 // isn't clobbered in between if at all possible.
1333 assert(LastReload
->beginIndex() < ReloadIdx
);
1334 NextReloadMap
.insert(std::make_pair(LastReload
->reg
, ReloadLi
->reg
));
1336 LastReloadMBB
= ReloadMBB
;
1337 LastReload
= ReloadLi
;
1338 LastReloadSS
= ReloadSS
;
1340 unhandled_
.push(ReloadLi
);
1344 unsigned RALinScan::getFreePhysReg(LiveInterval
* cur
,
1345 const TargetRegisterClass
*RC
,
1346 unsigned MaxInactiveCount
,
1347 SmallVector
<unsigned, 256> &inactiveCounts
,
1349 unsigned FreeReg
= 0;
1350 unsigned FreeRegInactiveCount
= 0;
1352 std::pair
<unsigned, unsigned> Hint
= mri_
->getRegAllocationHint(cur
->reg
);
1353 // Resolve second part of the hint (if possible) given the current allocation.
1354 unsigned physReg
= Hint
.second
;
1356 TargetRegisterInfo::isVirtualRegister(physReg
) && vrm_
->hasPhys(physReg
))
1357 physReg
= vrm_
->getPhys(physReg
);
1359 TargetRegisterClass::iterator I
, E
;
1360 tie(I
, E
) = tri_
->getAllocationOrder(RC
, Hint
.first
, physReg
, *mf_
);
1361 assert(I
!= E
&& "No allocatable register in this register class!");
1363 // Scan for the first available register.
1364 for (; I
!= E
; ++I
) {
1366 // Ignore "downgraded" registers.
1367 if (SkipDGRegs
&& DowngradedRegs
.count(Reg
))
1369 if (isRegAvail(Reg
)) {
1371 if (FreeReg
< inactiveCounts
.size())
1372 FreeRegInactiveCount
= inactiveCounts
[FreeReg
];
1374 FreeRegInactiveCount
= 0;
1379 // If there are no free regs, or if this reg has the max inactive count,
1380 // return this register.
1381 if (FreeReg
== 0 || FreeRegInactiveCount
== MaxInactiveCount
)
1384 // Continue scanning the registers, looking for the one with the highest
1385 // inactive count. Alkis found that this reduced register pressure very
1386 // slightly on X86 (in rev 1.94 of this file), though this should probably be
1388 for (; I
!= E
; ++I
) {
1390 // Ignore "downgraded" registers.
1391 if (SkipDGRegs
&& DowngradedRegs
.count(Reg
))
1393 if (isRegAvail(Reg
) && Reg
< inactiveCounts
.size() &&
1394 FreeRegInactiveCount
< inactiveCounts
[Reg
]) {
1396 FreeRegInactiveCount
= inactiveCounts
[Reg
];
1397 if (FreeRegInactiveCount
== MaxInactiveCount
)
1398 break; // We found the one with the max inactive count.
1405 /// getFreePhysReg - return a free physical register for this virtual register
1406 /// interval if we have one, otherwise return 0.
1407 unsigned RALinScan::getFreePhysReg(LiveInterval
*cur
) {
1408 SmallVector
<unsigned, 256> inactiveCounts
;
1409 unsigned MaxInactiveCount
= 0;
1411 const TargetRegisterClass
*RC
= mri_
->getRegClass(cur
->reg
);
1412 const TargetRegisterClass
*RCLeader
= RelatedRegClasses
.getLeaderValue(RC
);
1414 for (IntervalPtrs::iterator i
= inactive_
.begin(), e
= inactive_
.end();
1416 unsigned reg
= i
->first
->reg
;
1417 assert(TargetRegisterInfo::isVirtualRegister(reg
) &&
1418 "Can only allocate virtual registers!");
1420 // If this is not in a related reg class to the register we're allocating,
1422 const TargetRegisterClass
*RegRC
= mri_
->getRegClass(reg
);
1423 if (RelatedRegClasses
.getLeaderValue(RegRC
) == RCLeader
) {
1424 reg
= vrm_
->getPhys(reg
);
1425 if (inactiveCounts
.size() <= reg
)
1426 inactiveCounts
.resize(reg
+1);
1427 ++inactiveCounts
[reg
];
1428 MaxInactiveCount
= std::max(MaxInactiveCount
, inactiveCounts
[reg
]);
1432 // If copy coalescer has assigned a "preferred" register, check if it's
1434 unsigned Preference
= vrm_
->getRegAllocPref(cur
->reg
);
1436 DEBUG(errs() << "(preferred: " << tri_
->getName(Preference
) << ") ");
1437 if (isRegAvail(Preference
) &&
1438 RC
->contains(Preference
))
1442 if (!DowngradedRegs
.empty()) {
1443 unsigned FreeReg
= getFreePhysReg(cur
, RC
, MaxInactiveCount
, inactiveCounts
,
1448 return getFreePhysReg(cur
, RC
, MaxInactiveCount
, inactiveCounts
, false);
1451 FunctionPass
* llvm::createLinearScanRegisterAllocator() {
1452 return new RALinScan();