blob: a4fdcfaa3be62cce6ee1a06961cbfb6dfee1f350 [file] [log] [blame]
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +00001//===-- RegAllocLinearScan.cpp - Linear Scan register allocator -----------===//
2//
3// The LLVM Compiler Infrastructure
4//
Chris Lattner4ee451d2007-12-29 20:36:04 +00005// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +00007//
8//===----------------------------------------------------------------------===//
9//
10// This file implements a linear scan register allocator.
11//
12//===----------------------------------------------------------------------===//
Alkis Evlogimenos0d6c5b62004-02-24 08:58:30 +000013
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +000014#define DEBUG_TYPE "regalloc"
Chris Lattnerb9805782005-08-23 22:27:31 +000015#include "VirtRegMap.h"
Lang Hames87e3bca2009-05-06 02:36:21 +000016#include "VirtRegRewriter.h"
Lang Hamese2b201b2009-05-18 19:03:16 +000017#include "Spiller.h"
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +000018#include "llvm/Function.h"
Lang Hamesa937f222009-12-14 06:49:42 +000019#include "llvm/CodeGen/CalcSpillWeights.h"
Evan Cheng3f32d652008-06-04 09:18:41 +000020#include "llvm/CodeGen/LiveIntervalAnalysis.h"
21#include "llvm/CodeGen/LiveStackAnalysis.h"
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +000022#include "llvm/CodeGen/MachineFunctionPass.h"
23#include "llvm/CodeGen/MachineInstr.h"
Evan Cheng22f07ff2007-12-11 02:09:15 +000024#include "llvm/CodeGen/MachineLoopInfo.h"
Chris Lattner84bc5422007-12-31 04:13:23 +000025#include "llvm/CodeGen/MachineRegisterInfo.h"
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +000026#include "llvm/CodeGen/Passes.h"
Jim Laskeyeb577ba2006-08-02 12:30:23 +000027#include "llvm/CodeGen/RegAllocRegistry.h"
David Greene2c17c4d2007-09-06 16:18:45 +000028#include "llvm/CodeGen/RegisterCoalescer.h"
Dan Gohman6f0d0242008-02-10 18:45:23 +000029#include "llvm/Target/TargetRegisterInfo.h"
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +000030#include "llvm/Target/TargetMachine.h"
Owen Anderson95dad832008-10-07 20:22:28 +000031#include "llvm/Target/TargetOptions.h"
Evan Chengc92da382007-11-03 07:20:12 +000032#include "llvm/Target/TargetInstrInfo.h"
Chris Lattnerb9805782005-08-23 22:27:31 +000033#include "llvm/ADT/EquivalenceClasses.h"
Dan Gohmand68a0762009-01-05 17:59:02 +000034#include "llvm/ADT/SmallSet.h"
Reid Spencer551ccae2004-09-01 22:55:40 +000035#include "llvm/ADT/Statistic.h"
36#include "llvm/ADT/STLExtras.h"
Bill Wendlingc3115a02009-08-22 20:30:53 +000037#include "llvm/Support/Debug.h"
Torok Edwin7d696d82009-07-11 13:10:19 +000038#include "llvm/Support/ErrorHandling.h"
Daniel Dunbarce63ffb2009-07-25 00:23:56 +000039#include "llvm/Support/raw_ostream.h"
Alkis Evlogimenos843b1602004-02-15 10:24:21 +000040#include <algorithm>
Alkis Evlogimenos26f5a692004-05-30 07:24:39 +000041#include <set>
Alkis Evlogimenos53eb3732004-07-22 08:14:44 +000042#include <queue>
Duraid Madina30059612005-12-28 04:55:42 +000043#include <memory>
Jeff Cohen97af7512006-12-02 02:22:01 +000044#include <cmath>
Lang Hamesf41538d2009-06-02 16:53:25 +000045
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +000046using namespace llvm;
47
Chris Lattnercd3245a2006-12-19 22:41:21 +000048STATISTIC(NumIters , "Number of iterations performed");
49STATISTIC(NumBacktracks, "Number of times we had to backtrack");
Evan Chengc92da382007-11-03 07:20:12 +000050STATISTIC(NumCoalesce, "Number of copies coalesced");
Evan Cheng206d1852009-04-20 08:01:12 +000051STATISTIC(NumDowngrade, "Number of registers downgraded");
Chris Lattnercd3245a2006-12-19 22:41:21 +000052
Evan Cheng3e172252008-06-20 21:45:16 +000053static cl::opt<bool>
54NewHeuristic("new-spilling-heuristic",
55 cl::desc("Use new spilling heuristic"),
56 cl::init(false), cl::Hidden);
57
Evan Chengf5cd4f02008-10-23 20:43:13 +000058static cl::opt<bool>
59PreSplitIntervals("pre-alloc-split",
60 cl::desc("Pre-register allocation live interval splitting"),
61 cl::init(false), cl::Hidden);
62
Jakob Stoklund Olesencf970362009-12-10 17:48:32 +000063static cl::opt<bool>
64TrivCoalesceEnds("trivial-coalesce-ends",
65 cl::desc("Attempt trivial coalescing of interval ends"),
66 cl::init(false), cl::Hidden);
67
Chris Lattnercd3245a2006-12-19 22:41:21 +000068static RegisterRegAlloc
Dan Gohmanb8cab922008-10-14 20:25:08 +000069linearscanRegAlloc("linearscan", "linear scan register allocator",
Chris Lattnercd3245a2006-12-19 22:41:21 +000070 createLinearScanRegisterAllocator);
71
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +000072namespace {
David Greene7cfd3362009-11-19 15:55:49 +000073 // When we allocate a register, add it to a fixed-size queue of
74 // registers to skip in subsequent allocations. This trades a small
75 // amount of register pressure and increased spills for flexibility in
76 // the post-pass scheduler.
77 //
78 // Note that in a the number of registers used for reloading spills
79 // will be one greater than the value of this option.
80 //
81 // One big limitation of this is that it doesn't differentiate between
82 // different register classes. So on x86-64, if there is xmm register
83 // pressure, it can caused fewer GPRs to be held in the queue.
84 static cl::opt<unsigned>
85 NumRecentlyUsedRegs("linearscan-skip-count",
Eric Christophercd075a42010-07-02 23:17:38 +000086 cl::desc("Number of registers for linearscan to remember"
87 "to skip."),
David Greene7cfd3362009-11-19 15:55:49 +000088 cl::init(0),
89 cl::Hidden);
Jim Grosbach662fb772010-09-01 21:48:06 +000090
Nick Lewycky6726b6d2009-10-25 06:33:48 +000091 struct RALinScan : public MachineFunctionPass {
Devang Patel19974732007-05-03 01:11:54 +000092 static char ID;
Owen Anderson90c579d2010-08-06 18:33:48 +000093 RALinScan() : MachineFunctionPass(ID) {
David Greene7cfd3362009-11-19 15:55:49 +000094 // Initialize the queue to record recently-used registers.
95 if (NumRecentlyUsedRegs > 0)
96 RecentRegs.resize(NumRecentlyUsedRegs, 0);
David Greenea96fc2f2009-11-20 21:13:27 +000097 RecentNext = RecentRegs.begin();
David Greene7cfd3362009-11-19 15:55:49 +000098 }
Devang Patel794fd752007-05-01 21:15:47 +000099
Chris Lattnercbb56252004-11-18 02:42:27 +0000100 typedef std::pair<LiveInterval*, LiveInterval::iterator> IntervalPtr;
Owen Andersoncd1dcbd2008-08-15 18:49:41 +0000101 typedef SmallVector<IntervalPtr, 32> IntervalPtrs;
Chris Lattnercbb56252004-11-18 02:42:27 +0000102 private:
Chris Lattnerb9805782005-08-23 22:27:31 +0000103 /// RelatedRegClasses - This structure is built the first time a function is
104 /// compiled, and keeps track of which register classes have registers that
105 /// belong to multiple classes or have aliases that are in other classes.
106 EquivalenceClasses<const TargetRegisterClass*> RelatedRegClasses;
Owen Anderson97382162008-08-13 23:36:23 +0000107 DenseMap<unsigned, const TargetRegisterClass*> OneClassForEachPhysReg;
Chris Lattnerb9805782005-08-23 22:27:31 +0000108
Evan Cheng206d1852009-04-20 08:01:12 +0000109 // NextReloadMap - For each register in the map, it maps to the another
110 // register which is defined by a reload from the same stack slot and
111 // both reloads are in the same basic block.
112 DenseMap<unsigned, unsigned> NextReloadMap;
113
114 // DowngradedRegs - A set of registers which are being "downgraded", i.e.
115 // un-favored for allocation.
116 SmallSet<unsigned, 8> DowngradedRegs;
117
118 // DowngradeMap - A map from virtual registers to physical registers being
119 // downgraded for the virtual registers.
120 DenseMap<unsigned, unsigned> DowngradeMap;
121
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000122 MachineFunction* mf_;
Evan Cheng3e172252008-06-20 21:45:16 +0000123 MachineRegisterInfo* mri_;
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000124 const TargetMachine* tm_;
Dan Gohman6f0d0242008-02-10 18:45:23 +0000125 const TargetRegisterInfo* tri_;
Evan Chengc92da382007-11-03 07:20:12 +0000126 const TargetInstrInfo* tii_;
Evan Chengc92da382007-11-03 07:20:12 +0000127 BitVector allocatableRegs_;
Jim Grosbach067a6482010-09-01 21:04:27 +0000128 BitVector reservedRegs_;
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000129 LiveIntervals* li_;
Evan Cheng3f32d652008-06-04 09:18:41 +0000130 LiveStacks* ls_;
Jakob Stoklund Olesen9529a1c2010-07-19 18:41:20 +0000131 MachineLoopInfo *loopInfo;
Chris Lattnercbb56252004-11-18 02:42:27 +0000132
133 /// handled_ - Intervals are added to the handled_ set in the order of their
134 /// start value. This is uses for backtracking.
135 std::vector<LiveInterval*> handled_;
136
137 /// fixed_ - Intervals that correspond to machine registers.
138 ///
139 IntervalPtrs fixed_;
140
141 /// active_ - Intervals that are currently being processed, and which have a
142 /// live range active for the current point.
143 IntervalPtrs active_;
144
145 /// inactive_ - Intervals that are currently being processed, but which have
146 /// a hold at the current point.
147 IntervalPtrs inactive_;
148
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000149 typedef std::priority_queue<LiveInterval*,
Owen Andersoncd1dcbd2008-08-15 18:49:41 +0000150 SmallVector<LiveInterval*, 64>,
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000151 greater_ptr<LiveInterval> > IntervalHeap;
152 IntervalHeap unhandled_;
Evan Cheng5b16cd22009-05-01 01:03:49 +0000153
154 /// regUse_ - Tracks register usage.
155 SmallVector<unsigned, 32> regUse_;
156 SmallVector<unsigned, 32> regUseBackUp_;
157
158 /// vrm_ - Tracks register assignments.
Owen Anderson49c8aa02009-03-13 05:55:11 +0000159 VirtRegMap* vrm_;
Evan Cheng5b16cd22009-05-01 01:03:49 +0000160
Lang Hames87e3bca2009-05-06 02:36:21 +0000161 std::auto_ptr<VirtRegRewriter> rewriter_;
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +0000162
Lang Hamese2b201b2009-05-18 19:03:16 +0000163 std::auto_ptr<Spiller> spiller_;
164
David Greene7cfd3362009-11-19 15:55:49 +0000165 // The queue of recently-used registers.
David Greenea96fc2f2009-11-20 21:13:27 +0000166 SmallVector<unsigned, 4> RecentRegs;
167 SmallVector<unsigned, 4>::iterator RecentNext;
David Greene7cfd3362009-11-19 15:55:49 +0000168
169 // Record that we just picked this register.
170 void recordRecentlyUsed(unsigned reg) {
171 assert(reg != 0 && "Recently used register is NOREG!");
172 if (!RecentRegs.empty()) {
David Greenea96fc2f2009-11-20 21:13:27 +0000173 *RecentNext++ = reg;
174 if (RecentNext == RecentRegs.end())
175 RecentNext = RecentRegs.begin();
David Greene7cfd3362009-11-19 15:55:49 +0000176 }
177 }
178
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000179 public:
180 virtual const char* getPassName() const {
181 return "Linear Scan Register Allocator";
182 }
183
184 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
Dan Gohman845012e2009-07-31 23:37:33 +0000185 AU.setPreservesCFG();
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000186 AU.addRequired<LiveIntervals>();
Lang Hames233a60e2009-11-03 23:52:08 +0000187 AU.addPreserved<SlotIndexes>();
Owen Anderson95dad832008-10-07 20:22:28 +0000188 if (StrongPHIElim)
189 AU.addRequiredID(StrongPHIEliminationID);
David Greene2c17c4d2007-09-06 16:18:45 +0000190 // Make sure PassManager knows which analyses to make available
191 // to coalescing and which analyses coalescing invalidates.
192 AU.addRequiredTransitive<RegisterCoalescer>();
Lang Hamesa937f222009-12-14 06:49:42 +0000193 AU.addRequired<CalculateSpillWeights>();
Evan Chengf5cd4f02008-10-23 20:43:13 +0000194 if (PreSplitIntervals)
195 AU.addRequiredID(PreAllocSplittingID);
Evan Cheng3f32d652008-06-04 09:18:41 +0000196 AU.addRequired<LiveStacks>();
197 AU.addPreserved<LiveStacks>();
Evan Cheng22f07ff2007-12-11 02:09:15 +0000198 AU.addRequired<MachineLoopInfo>();
Bill Wendling67d65bb2008-01-04 20:54:55 +0000199 AU.addPreserved<MachineLoopInfo>();
Owen Anderson49c8aa02009-03-13 05:55:11 +0000200 AU.addRequired<VirtRegMap>();
201 AU.addPreserved<VirtRegMap>();
Bill Wendling67d65bb2008-01-04 20:54:55 +0000202 AU.addPreservedID(MachineDominatorsID);
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000203 MachineFunctionPass::getAnalysisUsage(AU);
204 }
205
206 /// runOnMachineFunction - register allocate the whole function
207 bool runOnMachineFunction(MachineFunction&);
208
David Greene7cfd3362009-11-19 15:55:49 +0000209 // Determine if we skip this register due to its being recently used.
210 bool isRecentlyUsed(unsigned reg) const {
211 return std::find(RecentRegs.begin(), RecentRegs.end(), reg) !=
212 RecentRegs.end();
213 }
214
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000215 private:
216 /// linearScan - the linear scan algorithm
217 void linearScan();
218
Chris Lattnercbb56252004-11-18 02:42:27 +0000219 /// initIntervalSets - initialize the interval sets.
220 ///
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000221 void initIntervalSets();
222
Chris Lattnercbb56252004-11-18 02:42:27 +0000223 /// processActiveIntervals - expire old intervals and move non-overlapping
224 /// ones to the inactive list.
Lang Hames233a60e2009-11-03 23:52:08 +0000225 void processActiveIntervals(SlotIndex CurPoint);
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000226
Chris Lattnercbb56252004-11-18 02:42:27 +0000227 /// processInactiveIntervals - expire old intervals and move overlapping
228 /// ones to the active list.
Lang Hames233a60e2009-11-03 23:52:08 +0000229 void processInactiveIntervals(SlotIndex CurPoint);
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000230
Evan Cheng206d1852009-04-20 08:01:12 +0000231 /// hasNextReloadInterval - Return the next liveinterval that's being
232 /// defined by a reload from the same SS as the specified one.
233 LiveInterval *hasNextReloadInterval(LiveInterval *cur);
234
235 /// DowngradeRegister - Downgrade a register for allocation.
236 void DowngradeRegister(LiveInterval *li, unsigned Reg);
237
238 /// UpgradeRegister - Upgrade a register for allocation.
239 void UpgradeRegister(unsigned Reg);
240
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000241 /// assignRegOrStackSlotAtInterval - assign a register if one
242 /// is available, or spill.
243 void assignRegOrStackSlotAtInterval(LiveInterval* cur);
244
Evan Cheng5d088fe2009-03-23 22:57:19 +0000245 void updateSpillWeights(std::vector<float> &Weights,
246 unsigned reg, float weight,
247 const TargetRegisterClass *RC);
248
Evan Cheng3e172252008-06-20 21:45:16 +0000249 /// findIntervalsToSpill - Determine the intervals to spill for the
250 /// specified interval. It's passed the physical registers whose spill
251 /// weight is the lowest among all the registers whose live intervals
252 /// conflict with the interval.
253 void findIntervalsToSpill(LiveInterval *cur,
254 std::vector<std::pair<unsigned,float> > &Candidates,
255 unsigned NumCands,
256 SmallVector<LiveInterval*, 8> &SpillIntervals);
257
Evan Chengc92da382007-11-03 07:20:12 +0000258 /// attemptTrivialCoalescing - If a simple interval is defined by a copy,
Jim Grosbach977fa342010-07-27 18:36:27 +0000259 /// try to allocate the definition to the same register as the source,
260 /// if the register is not defined during the life time of the interval.
261 /// This eliminates a copy, and is used to coalesce copies which were not
Evan Chengc92da382007-11-03 07:20:12 +0000262 /// coalesced away before allocation either due to dest and src being in
263 /// different register classes or because the coalescer was overly
264 /// conservative.
265 unsigned attemptTrivialCoalescing(LiveInterval &cur, unsigned Reg);
266
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000267 ///
Evan Cheng5b16cd22009-05-01 01:03:49 +0000268 /// Register usage / availability tracking helpers.
269 ///
270
271 void initRegUses() {
272 regUse_.resize(tri_->getNumRegs(), 0);
273 regUseBackUp_.resize(tri_->getNumRegs(), 0);
274 }
275
276 void finalizeRegUses() {
Evan Chengc781a242009-05-03 18:32:42 +0000277#ifndef NDEBUG
278 // Verify all the registers are "freed".
279 bool Error = false;
280 for (unsigned i = 0, e = tri_->getNumRegs(); i != e; ++i) {
281 if (regUse_[i] != 0) {
David Greene37277762010-01-05 01:25:20 +0000282 dbgs() << tri_->getName(i) << " is still in use!\n";
Evan Chengc781a242009-05-03 18:32:42 +0000283 Error = true;
284 }
285 }
286 if (Error)
Torok Edwinc23197a2009-07-14 16:55:14 +0000287 llvm_unreachable(0);
Evan Chengc781a242009-05-03 18:32:42 +0000288#endif
Evan Cheng5b16cd22009-05-01 01:03:49 +0000289 regUse_.clear();
290 regUseBackUp_.clear();
291 }
292
293 void addRegUse(unsigned physReg) {
294 assert(TargetRegisterInfo::isPhysicalRegister(physReg) &&
295 "should be physical register!");
296 ++regUse_[physReg];
297 for (const unsigned* as = tri_->getAliasSet(physReg); *as; ++as)
298 ++regUse_[*as];
299 }
300
301 void delRegUse(unsigned physReg) {
302 assert(TargetRegisterInfo::isPhysicalRegister(physReg) &&
303 "should be physical register!");
304 assert(regUse_[physReg] != 0);
305 --regUse_[physReg];
306 for (const unsigned* as = tri_->getAliasSet(physReg); *as; ++as) {
307 assert(regUse_[*as] != 0);
308 --regUse_[*as];
309 }
310 }
311
312 bool isRegAvail(unsigned physReg) const {
313 assert(TargetRegisterInfo::isPhysicalRegister(physReg) &&
314 "should be physical register!");
315 return regUse_[physReg] == 0;
316 }
317
318 void backUpRegUses() {
319 regUseBackUp_ = regUse_;
320 }
321
322 void restoreRegUses() {
323 regUse_ = regUseBackUp_;
324 }
325
326 ///
327 /// Register handling helpers.
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000328 ///
329
Chris Lattnercbb56252004-11-18 02:42:27 +0000330 /// getFreePhysReg - return a free physical register for this virtual
331 /// register interval if we have one, otherwise return 0.
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000332 unsigned getFreePhysReg(LiveInterval* cur);
Evan Cheng358dec52009-06-15 08:28:29 +0000333 unsigned getFreePhysReg(LiveInterval* cur,
334 const TargetRegisterClass *RC,
Evan Cheng206d1852009-04-20 08:01:12 +0000335 unsigned MaxInactiveCount,
336 SmallVector<unsigned, 256> &inactiveCounts,
337 bool SkipDGRegs);
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000338
Jim Grosbach5a4cbea2010-09-01 21:34:41 +0000339 /// getFirstNonReservedPhysReg - return the first non-reserved physical
340 /// register in the register class.
341 unsigned getFirstNonReservedPhysReg(const TargetRegisterClass *RC) {
342 TargetRegisterClass::iterator aoe = RC->allocation_order_end(*mf_);
343 TargetRegisterClass::iterator i = RC->allocation_order_begin(*mf_);
344 while (i != aoe && reservedRegs_.test(*i))
345 ++i;
346 assert(i != aoe && "All registers reserved?!");
347 return *i;
348 }
349
Chris Lattnerb9805782005-08-23 22:27:31 +0000350 void ComputeRelatedRegClasses();
351
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000352 template <typename ItTy>
353 void printIntervals(const char* const str, ItTy i, ItTy e) const {
Bill Wendlingc3115a02009-08-22 20:30:53 +0000354 DEBUG({
355 if (str)
David Greene37277762010-01-05 01:25:20 +0000356 dbgs() << str << " intervals:\n";
Bill Wendlingc3115a02009-08-22 20:30:53 +0000357
358 for (; i != e; ++i) {
David Greene37277762010-01-05 01:25:20 +0000359 dbgs() << "\t" << *i->first << " -> ";
Bill Wendlingc3115a02009-08-22 20:30:53 +0000360
361 unsigned reg = i->first->reg;
362 if (TargetRegisterInfo::isVirtualRegister(reg))
363 reg = vrm_->getPhys(reg);
364
David Greene37277762010-01-05 01:25:20 +0000365 dbgs() << tri_->getName(reg) << '\n';
Bill Wendlingc3115a02009-08-22 20:30:53 +0000366 }
367 });
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000368 }
369 };
Bill Wendlinge23e00d2007-05-08 19:02:46 +0000370 char RALinScan::ID = 0;
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +0000371}
372
Owen Andersond13db2c2010-07-21 22:09:45 +0000373INITIALIZE_PASS(RALinScan, "linearscan-regalloc",
374 "Linear Scan Register Allocator", false, false);
Evan Cheng3f32d652008-06-04 09:18:41 +0000375
Bill Wendlinge23e00d2007-05-08 19:02:46 +0000376void RALinScan::ComputeRelatedRegClasses() {
Chris Lattnerb9805782005-08-23 22:27:31 +0000377 // First pass, add all reg classes to the union, and determine at least one
378 // reg class that each register is in.
379 bool HasAliases = false;
Evan Cheng206d1852009-04-20 08:01:12 +0000380 for (TargetRegisterInfo::regclass_iterator RCI = tri_->regclass_begin(),
381 E = tri_->regclass_end(); RCI != E; ++RCI) {
Chris Lattnerb9805782005-08-23 22:27:31 +0000382 RelatedRegClasses.insert(*RCI);
383 for (TargetRegisterClass::iterator I = (*RCI)->begin(), E = (*RCI)->end();
384 I != E; ++I) {
Evan Cheng206d1852009-04-20 08:01:12 +0000385 HasAliases = HasAliases || *tri_->getAliasSet(*I) != 0;
Jim Grosbach662fb772010-09-01 21:48:06 +0000386
Chris Lattnerb9805782005-08-23 22:27:31 +0000387 const TargetRegisterClass *&PRC = OneClassForEachPhysReg[*I];
388 if (PRC) {
389 // Already processed this register. Just make sure we know that
390 // multiple register classes share a register.
391 RelatedRegClasses.unionSets(PRC, *RCI);
392 } else {
393 PRC = *RCI;
394 }
395 }
396 }
Jim Grosbach662fb772010-09-01 21:48:06 +0000397
Chris Lattnerb9805782005-08-23 22:27:31 +0000398 // Second pass, now that we know conservatively what register classes each reg
399 // belongs to, add info about aliases. We don't need to do this for targets
400 // without register aliases.
401 if (HasAliases)
Owen Anderson97382162008-08-13 23:36:23 +0000402 for (DenseMap<unsigned, const TargetRegisterClass*>::iterator
Chris Lattnerb9805782005-08-23 22:27:31 +0000403 I = OneClassForEachPhysReg.begin(), E = OneClassForEachPhysReg.end();
404 I != E; ++I)
Evan Cheng206d1852009-04-20 08:01:12 +0000405 for (const unsigned *AS = tri_->getAliasSet(I->first); *AS; ++AS)
Chris Lattnerb9805782005-08-23 22:27:31 +0000406 RelatedRegClasses.unionSets(I->second, OneClassForEachPhysReg[*AS]);
407}
408
Jakob Stoklund Olesencf970362009-12-10 17:48:32 +0000409/// attemptTrivialCoalescing - If a simple interval is defined by a copy, try
410/// allocate the definition the same register as the source register if the
411/// register is not defined during live time of the interval. If the interval is
412/// killed by a copy, try to use the destination register. This eliminates a
413/// copy. This is used to coalesce copies which were not coalesced away before
414/// allocation either due to dest and src being in different register classes or
415/// because the coalescer was overly conservative.
Evan Chengc92da382007-11-03 07:20:12 +0000416unsigned RALinScan::attemptTrivialCoalescing(LiveInterval &cur, unsigned Reg) {
Evan Cheng90f95f82009-06-14 20:22:55 +0000417 unsigned Preference = vrm_->getRegAllocPref(cur.reg);
418 if ((Preference && Preference == Reg) || !cur.containsOneValue())
Evan Chengc92da382007-11-03 07:20:12 +0000419 return Reg;
420
Jakob Stoklund Olesencf970362009-12-10 17:48:32 +0000421 // We cannot handle complicated live ranges. Simple linear stuff only.
422 if (cur.ranges.size() != 1)
Evan Chengc92da382007-11-03 07:20:12 +0000423 return Reg;
Jakob Stoklund Olesencf970362009-12-10 17:48:32 +0000424
425 const LiveRange &range = cur.ranges.front();
426
427 VNInfo *vni = range.valno;
428 if (vni->isUnused())
Bill Wendlingdc492e02009-12-05 07:30:23 +0000429 return Reg;
Jakob Stoklund Olesencf970362009-12-10 17:48:32 +0000430
431 unsigned CandReg;
432 {
433 MachineInstr *CopyMI;
Lang Hames6e2968c2010-09-25 12:04:16 +0000434 if ((CopyMI = li_->getInstructionFromIndex(vni->def)) && CopyMI->isCopy())
Jakob Stoklund Olesencf970362009-12-10 17:48:32 +0000435 // Defined by a copy, try to extend SrcReg forward
Jakob Stoklund Olesen04c528a2010-07-16 04:45:42 +0000436 CandReg = CopyMI->getOperand(1).getReg();
Jakob Stoklund Olesencf970362009-12-10 17:48:32 +0000437 else if (TrivCoalesceEnds &&
Jakob Stoklund Olesen04c528a2010-07-16 04:45:42 +0000438 (CopyMI = li_->getInstructionFromIndex(range.end.getBaseIndex())) &&
439 CopyMI->isCopy() && cur.reg == CopyMI->getOperand(1).getReg())
Jakob Stoklund Olesencf970362009-12-10 17:48:32 +0000440 // Only used by a copy, try to extend DstReg backwards
Jakob Stoklund Olesen04c528a2010-07-16 04:45:42 +0000441 CandReg = CopyMI->getOperand(0).getReg();
Jakob Stoklund Olesencf970362009-12-10 17:48:32 +0000442 else
Evan Chengc92da382007-11-03 07:20:12 +0000443 return Reg;
Anton Korobeynikov4aefd6b2008-02-20 12:07:57 +0000444 }
Jakob Stoklund Olesencf970362009-12-10 17:48:32 +0000445
446 if (TargetRegisterInfo::isVirtualRegister(CandReg)) {
447 if (!vrm_->isAssignedReg(CandReg))
448 return Reg;
449 CandReg = vrm_->getPhys(CandReg);
450 }
451 if (Reg == CandReg)
Evan Chengc92da382007-11-03 07:20:12 +0000452 return Reg;
453
Evan Cheng841ee1a2008-09-18 22:38:47 +0000454 const TargetRegisterClass *RC = mri_->getRegClass(cur.reg);
Jakob Stoklund Olesencf970362009-12-10 17:48:32 +0000455 if (!RC->contains(CandReg))
456 return Reg;
457
458 if (li_->conflictsWithPhysReg(cur, *vrm_, CandReg))
Evan Chengc92da382007-11-03 07:20:12 +0000459 return Reg;
460
Bill Wendlingdc492e02009-12-05 07:30:23 +0000461 // Try to coalesce.
David Greene37277762010-01-05 01:25:20 +0000462 DEBUG(dbgs() << "Coalescing: " << cur << " -> " << tri_->getName(CandReg)
Jakob Stoklund Olesencf970362009-12-10 17:48:32 +0000463 << '\n');
464 vrm_->clearVirt(cur.reg);
465 vrm_->assignVirt2Phys(cur.reg, CandReg);
Bill Wendlingdc492e02009-12-05 07:30:23 +0000466
Jakob Stoklund Olesencf970362009-12-10 17:48:32 +0000467 ++NumCoalesce;
468 return CandReg;
Evan Chengc92da382007-11-03 07:20:12 +0000469}
470
Bill Wendlinge23e00d2007-05-08 19:02:46 +0000471bool RALinScan::runOnMachineFunction(MachineFunction &fn) {
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000472 mf_ = &fn;
Evan Cheng3e172252008-06-20 21:45:16 +0000473 mri_ = &fn.getRegInfo();
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000474 tm_ = &fn.getTarget();
Dan Gohman6f0d0242008-02-10 18:45:23 +0000475 tri_ = tm_->getRegisterInfo();
Evan Chengc92da382007-11-03 07:20:12 +0000476 tii_ = tm_->getInstrInfo();
Dan Gohman6f0d0242008-02-10 18:45:23 +0000477 allocatableRegs_ = tri_->getAllocatableSet(fn);
Jim Grosbach067a6482010-09-01 21:04:27 +0000478 reservedRegs_ = tri_->getReservedRegs(fn);
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000479 li_ = &getAnalysis<LiveIntervals>();
Evan Cheng3f32d652008-06-04 09:18:41 +0000480 ls_ = &getAnalysis<LiveStacks>();
Evan Cheng22f07ff2007-12-11 02:09:15 +0000481 loopInfo = &getAnalysis<MachineLoopInfo>();
Chris Lattnerf348e3a2004-11-18 04:33:31 +0000482
David Greene2c17c4d2007-09-06 16:18:45 +0000483 // We don't run the coalescer here because we have no reason to
484 // interact with it. If the coalescer requires interaction, it
485 // won't do anything. If it doesn't require interaction, we assume
486 // it was run as a separate pass.
487
Chris Lattnerb9805782005-08-23 22:27:31 +0000488 // If this is the first function compiled, compute the related reg classes.
489 if (RelatedRegClasses.empty())
490 ComputeRelatedRegClasses();
Evan Cheng5b16cd22009-05-01 01:03:49 +0000491
492 // Also resize register usage trackers.
493 initRegUses();
494
Owen Anderson49c8aa02009-03-13 05:55:11 +0000495 vrm_ = &getAnalysis<VirtRegMap>();
Lang Hames87e3bca2009-05-06 02:36:21 +0000496 if (!rewriter_.get()) rewriter_.reset(createVirtRegRewriter());
Jim Grosbach662fb772010-09-01 21:48:06 +0000497
Jakob Stoklund Olesenf2c6e362010-07-20 23:50:15 +0000498 spiller_.reset(createSpiller(*this, *mf_, *vrm_));
Jim Grosbach662fb772010-09-01 21:48:06 +0000499
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000500 initIntervalSets();
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +0000501
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000502 linearScan();
Alkis Evlogimenos0d6c5b62004-02-24 08:58:30 +0000503
Chris Lattnerb0f31bf2005-01-23 22:45:13 +0000504 // Rewrite spill code and update the PhysRegsUsed set.
Lang Hames87e3bca2009-05-06 02:36:21 +0000505 rewriter_->runOnMachineFunction(*mf_, *vrm_, li_);
Chris Lattnercbb56252004-11-18 02:42:27 +0000506
Dan Gohman51cd9d62008-06-23 23:51:16 +0000507 assert(unhandled_.empty() && "Unhandled live intervals remain!");
Evan Cheng5b16cd22009-05-01 01:03:49 +0000508
509 finalizeRegUses();
510
Chris Lattnercbb56252004-11-18 02:42:27 +0000511 fixed_.clear();
512 active_.clear();
513 inactive_.clear();
514 handled_.clear();
Evan Cheng206d1852009-04-20 08:01:12 +0000515 NextReloadMap.clear();
516 DowngradedRegs.clear();
517 DowngradeMap.clear();
Lang Hamesf41538d2009-06-02 16:53:25 +0000518 spiller_.reset(0);
Chris Lattnercbb56252004-11-18 02:42:27 +0000519
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000520 return true;
Alkis Evlogimenos0d6c5b62004-02-24 08:58:30 +0000521}
522
Chris Lattnerc8b9f332004-11-18 06:01:45 +0000523/// initIntervalSets - initialize the interval sets.
524///
Bill Wendlinge23e00d2007-05-08 19:02:46 +0000525void RALinScan::initIntervalSets()
Chris Lattnerc8b9f332004-11-18 06:01:45 +0000526{
527 assert(unhandled_.empty() && fixed_.empty() &&
528 active_.empty() && inactive_.empty() &&
529 "interval sets should be empty on initialization");
530
Owen Andersoncd1dcbd2008-08-15 18:49:41 +0000531 handled_.reserve(li_->getNumIntervals());
532
Chris Lattnerc8b9f332004-11-18 06:01:45 +0000533 for (LiveIntervals::iterator i = li_->begin(), e = li_->end(); i != e; ++i) {
Owen Anderson03857b22008-08-13 21:49:13 +0000534 if (TargetRegisterInfo::isPhysicalRegister(i->second->reg)) {
Lang Hames233a60e2009-11-03 23:52:08 +0000535 if (!i->second->empty()) {
536 mri_->setPhysRegUsed(i->second->reg);
537 fixed_.push_back(std::make_pair(i->second, i->second->begin()));
538 }
539 } else {
540 if (i->second->empty()) {
541 assignRegOrStackSlotAtInterval(i->second);
542 }
543 else
544 unhandled_.push(i->second);
545 }
Chris Lattnerc8b9f332004-11-18 06:01:45 +0000546 }
547}
548
Bill Wendlingc3115a02009-08-22 20:30:53 +0000549void RALinScan::linearScan() {
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000550 // linear scan algorithm
Bill Wendlingc3115a02009-08-22 20:30:53 +0000551 DEBUG({
David Greene37277762010-01-05 01:25:20 +0000552 dbgs() << "********** LINEAR SCAN **********\n"
Jim Grosbach662fb772010-09-01 21:48:06 +0000553 << "********** Function: "
Bill Wendlingc3115a02009-08-22 20:30:53 +0000554 << mf_->getFunction()->getName() << '\n';
555 printIntervals("fixed", fixed_.begin(), fixed_.end());
556 });
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000557
558 while (!unhandled_.empty()) {
559 // pick the interval with the earliest start point
560 LiveInterval* cur = unhandled_.top();
561 unhandled_.pop();
Evan Cheng11923cc2007-10-16 21:09:14 +0000562 ++NumIters;
David Greene37277762010-01-05 01:25:20 +0000563 DEBUG(dbgs() << "\n*** CURRENT ***: " << *cur << '\n');
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000564
Lang Hames233a60e2009-11-03 23:52:08 +0000565 assert(!cur->empty() && "Empty interval in unhandled set.");
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000566
Lang Hames233a60e2009-11-03 23:52:08 +0000567 processActiveIntervals(cur->beginIndex());
568 processInactiveIntervals(cur->beginIndex());
569
570 assert(TargetRegisterInfo::isVirtualRegister(cur->reg) &&
571 "Can only allocate virtual registers!");
Misha Brukmanedf128a2005-04-21 22:36:52 +0000572
Chris Lattnerc8b9f332004-11-18 06:01:45 +0000573 // Allocating a virtual register. try to find a free
574 // physical register or spill an interval (possibly this one) in order to
575 // assign it one.
576 assignRegOrStackSlotAtInterval(cur);
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000577
Bill Wendlingc3115a02009-08-22 20:30:53 +0000578 DEBUG({
579 printIntervals("active", active_.begin(), active_.end());
580 printIntervals("inactive", inactive_.begin(), inactive_.end());
581 });
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000582 }
Alkis Evlogimenos7d629b52004-01-07 09:20:58 +0000583
Evan Cheng5b16cd22009-05-01 01:03:49 +0000584 // Expire any remaining active intervals
Evan Cheng11923cc2007-10-16 21:09:14 +0000585 while (!active_.empty()) {
586 IntervalPtr &IP = active_.back();
587 unsigned reg = IP.first->reg;
David Greene37277762010-01-05 01:25:20 +0000588 DEBUG(dbgs() << "\tinterval " << *IP.first << " expired\n");
Dan Gohman6f0d0242008-02-10 18:45:23 +0000589 assert(TargetRegisterInfo::isVirtualRegister(reg) &&
Chris Lattnerc8b9f332004-11-18 06:01:45 +0000590 "Can only allocate virtual registers!");
591 reg = vrm_->getPhys(reg);
Evan Cheng5b16cd22009-05-01 01:03:49 +0000592 delRegUse(reg);
Evan Cheng11923cc2007-10-16 21:09:14 +0000593 active_.pop_back();
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000594 }
Alkis Evlogimenos7d629b52004-01-07 09:20:58 +0000595
Evan Cheng5b16cd22009-05-01 01:03:49 +0000596 // Expire any remaining inactive intervals
Bill Wendlingc3115a02009-08-22 20:30:53 +0000597 DEBUG({
598 for (IntervalPtrs::reverse_iterator
599 i = inactive_.rbegin(); i != inactive_.rend(); ++i)
David Greene37277762010-01-05 01:25:20 +0000600 dbgs() << "\tinterval " << *i->first << " expired\n";
Bill Wendlingc3115a02009-08-22 20:30:53 +0000601 });
Evan Cheng11923cc2007-10-16 21:09:14 +0000602 inactive_.clear();
Alkis Evlogimenosb7be1152004-01-13 20:42:08 +0000603
Evan Cheng81a03822007-11-17 00:40:40 +0000604 // Add live-ins to every BB except for entry. Also perform trivial coalescing.
Evan Cheng3f4b80e2007-10-17 02:12:22 +0000605 MachineFunction::iterator EntryMBB = mf_->begin();
Evan Chenga5bfc972007-10-17 06:53:44 +0000606 SmallVector<MachineBasicBlock*, 8> LiveInMBBs;
Evan Cheng3f4b80e2007-10-17 02:12:22 +0000607 for (LiveIntervals::iterator i = li_->begin(), e = li_->end(); i != e; ++i) {
Owen Anderson03857b22008-08-13 21:49:13 +0000608 LiveInterval &cur = *i->second;
Evan Cheng3f4b80e2007-10-17 02:12:22 +0000609 unsigned Reg = 0;
Dan Gohman6f0d0242008-02-10 18:45:23 +0000610 bool isPhys = TargetRegisterInfo::isPhysicalRegister(cur.reg);
Evan Cheng81a03822007-11-17 00:40:40 +0000611 if (isPhys)
Owen Anderson03857b22008-08-13 21:49:13 +0000612 Reg = cur.reg;
Evan Cheng3f4b80e2007-10-17 02:12:22 +0000613 else if (vrm_->isAssignedReg(cur.reg))
Evan Chengc92da382007-11-03 07:20:12 +0000614 Reg = attemptTrivialCoalescing(cur, vrm_->getPhys(cur.reg));
Evan Cheng3f4b80e2007-10-17 02:12:22 +0000615 if (!Reg)
616 continue;
Evan Cheng81a03822007-11-17 00:40:40 +0000617 // Ignore splited live intervals.
618 if (!isPhys && vrm_->getPreSplitReg(cur.reg))
619 continue;
Evan Cheng550aacb2009-06-04 20:28:22 +0000620
Evan Cheng3f4b80e2007-10-17 02:12:22 +0000621 for (LiveInterval::Ranges::const_iterator I = cur.begin(), E = cur.end();
622 I != E; ++I) {
623 const LiveRange &LR = *I;
Evan Chengd0e32c52008-10-29 05:06:14 +0000624 if (li_->findLiveInMBBs(LR.start, LR.end, LiveInMBBs)) {
Evan Cheng3f4b80e2007-10-17 02:12:22 +0000625 for (unsigned i = 0, e = LiveInMBBs.size(); i != e; ++i)
Evan Cheng073e7e52009-06-04 20:53:36 +0000626 if (LiveInMBBs[i] != EntryMBB) {
627 assert(TargetRegisterInfo::isPhysicalRegister(Reg) &&
628 "Adding a virtual register to livein set?");
Evan Cheng3f4b80e2007-10-17 02:12:22 +0000629 LiveInMBBs[i]->addLiveIn(Reg);
Evan Cheng073e7e52009-06-04 20:53:36 +0000630 }
Evan Chenga5bfc972007-10-17 06:53:44 +0000631 LiveInMBBs.clear();
Evan Cheng9fc508f2007-02-16 09:05:02 +0000632 }
633 }
634 }
635
David Greene37277762010-01-05 01:25:20 +0000636 DEBUG(dbgs() << *vrm_);
Evan Chengc781a242009-05-03 18:32:42 +0000637
638 // Look for physical registers that end up not being allocated even though
639 // register allocator had to spill other registers in its register class.
640 if (ls_->getNumIntervals() == 0)
641 return;
Evan Cheng90f95f82009-06-14 20:22:55 +0000642 if (!vrm_->FindUnusedRegisters(li_))
Evan Chengc781a242009-05-03 18:32:42 +0000643 return;
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +0000644}
645
Chris Lattnercbb56252004-11-18 02:42:27 +0000646/// processActiveIntervals - expire old intervals and move non-overlapping ones
647/// to the inactive list.
Lang Hames233a60e2009-11-03 23:52:08 +0000648void RALinScan::processActiveIntervals(SlotIndex CurPoint)
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +0000649{
David Greene37277762010-01-05 01:25:20 +0000650 DEBUG(dbgs() << "\tprocessing active intervals:\n");
Chris Lattner23b71c12004-11-18 01:29:39 +0000651
Chris Lattnercbb56252004-11-18 02:42:27 +0000652 for (unsigned i = 0, e = active_.size(); i != e; ++i) {
653 LiveInterval *Interval = active_[i].first;
654 LiveInterval::iterator IntervalPos = active_[i].second;
655 unsigned reg = Interval->reg;
Alkis Evlogimenosed543732004-09-01 22:52:29 +0000656
Chris Lattnercbb56252004-11-18 02:42:27 +0000657 IntervalPos = Interval->advanceTo(IntervalPos, CurPoint);
658
659 if (IntervalPos == Interval->end()) { // Remove expired intervals.
David Greene37277762010-01-05 01:25:20 +0000660 DEBUG(dbgs() << "\t\tinterval " << *Interval << " expired\n");
Dan Gohman6f0d0242008-02-10 18:45:23 +0000661 assert(TargetRegisterInfo::isVirtualRegister(reg) &&
Chris Lattnerc8b9f332004-11-18 06:01:45 +0000662 "Can only allocate virtual registers!");
663 reg = vrm_->getPhys(reg);
Evan Cheng5b16cd22009-05-01 01:03:49 +0000664 delRegUse(reg);
Chris Lattnercbb56252004-11-18 02:42:27 +0000665
666 // Pop off the end of the list.
667 active_[i] = active_.back();
668 active_.pop_back();
669 --i; --e;
Misha Brukmanedf128a2005-04-21 22:36:52 +0000670
Chris Lattnercbb56252004-11-18 02:42:27 +0000671 } else if (IntervalPos->start > CurPoint) {
672 // Move inactive intervals to inactive list.
David Greene37277762010-01-05 01:25:20 +0000673 DEBUG(dbgs() << "\t\tinterval " << *Interval << " inactive\n");
Dan Gohman6f0d0242008-02-10 18:45:23 +0000674 assert(TargetRegisterInfo::isVirtualRegister(reg) &&
Chris Lattnerc8b9f332004-11-18 06:01:45 +0000675 "Can only allocate virtual registers!");
676 reg = vrm_->getPhys(reg);
Evan Cheng5b16cd22009-05-01 01:03:49 +0000677 delRegUse(reg);
Chris Lattnercbb56252004-11-18 02:42:27 +0000678 // add to inactive.
679 inactive_.push_back(std::make_pair(Interval, IntervalPos));
680
681 // Pop off the end of the list.
682 active_[i] = active_.back();
683 active_.pop_back();
684 --i; --e;
685 } else {
686 // Otherwise, just update the iterator position.
687 active_[i].second = IntervalPos;
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000688 }
689 }
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +0000690}
691
Chris Lattnercbb56252004-11-18 02:42:27 +0000692/// processInactiveIntervals - expire old intervals and move overlapping
693/// ones to the active list.
Lang Hames233a60e2009-11-03 23:52:08 +0000694void RALinScan::processInactiveIntervals(SlotIndex CurPoint)
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +0000695{
David Greene37277762010-01-05 01:25:20 +0000696 DEBUG(dbgs() << "\tprocessing inactive intervals:\n");
Chris Lattner365b95f2004-11-18 04:13:02 +0000697
Chris Lattnercbb56252004-11-18 02:42:27 +0000698 for (unsigned i = 0, e = inactive_.size(); i != e; ++i) {
699 LiveInterval *Interval = inactive_[i].first;
700 LiveInterval::iterator IntervalPos = inactive_[i].second;
701 unsigned reg = Interval->reg;
Chris Lattner23b71c12004-11-18 01:29:39 +0000702
Chris Lattnercbb56252004-11-18 02:42:27 +0000703 IntervalPos = Interval->advanceTo(IntervalPos, CurPoint);
Misha Brukmanedf128a2005-04-21 22:36:52 +0000704
Chris Lattnercbb56252004-11-18 02:42:27 +0000705 if (IntervalPos == Interval->end()) { // remove expired intervals.
David Greene37277762010-01-05 01:25:20 +0000706 DEBUG(dbgs() << "\t\tinterval " << *Interval << " expired\n");
Alkis Evlogimenos169cfd02003-12-21 05:43:40 +0000707
Chris Lattnercbb56252004-11-18 02:42:27 +0000708 // Pop off the end of the list.
709 inactive_[i] = inactive_.back();
710 inactive_.pop_back();
711 --i; --e;
712 } else if (IntervalPos->start <= CurPoint) {
713 // move re-activated intervals in active list
David Greene37277762010-01-05 01:25:20 +0000714 DEBUG(dbgs() << "\t\tinterval " << *Interval << " active\n");
Dan Gohman6f0d0242008-02-10 18:45:23 +0000715 assert(TargetRegisterInfo::isVirtualRegister(reg) &&
Chris Lattnerc8b9f332004-11-18 06:01:45 +0000716 "Can only allocate virtual registers!");
717 reg = vrm_->getPhys(reg);
Evan Cheng5b16cd22009-05-01 01:03:49 +0000718 addRegUse(reg);
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000719 // add to active
Chris Lattnercbb56252004-11-18 02:42:27 +0000720 active_.push_back(std::make_pair(Interval, IntervalPos));
721
722 // Pop off the end of the list.
723 inactive_[i] = inactive_.back();
724 inactive_.pop_back();
725 --i; --e;
726 } else {
727 // Otherwise, just update the iterator position.
728 inactive_[i].second = IntervalPos;
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000729 }
730 }
Alkis Evlogimenos169cfd02003-12-21 05:43:40 +0000731}
732
Chris Lattnercbb56252004-11-18 02:42:27 +0000733/// updateSpillWeights - updates the spill weights of the specifed physical
734/// register and its weight.
Evan Cheng5d088fe2009-03-23 22:57:19 +0000735void RALinScan::updateSpillWeights(std::vector<float> &Weights,
736 unsigned reg, float weight,
737 const TargetRegisterClass *RC) {
738 SmallSet<unsigned, 4> Processed;
739 SmallSet<unsigned, 4> SuperAdded;
740 SmallVector<unsigned, 4> Supers;
Chris Lattnerc8b9f332004-11-18 06:01:45 +0000741 Weights[reg] += weight;
Evan Cheng5d088fe2009-03-23 22:57:19 +0000742 Processed.insert(reg);
743 for (const unsigned* as = tri_->getAliasSet(reg); *as; ++as) {
Chris Lattnerc8b9f332004-11-18 06:01:45 +0000744 Weights[*as] += weight;
Evan Cheng5d088fe2009-03-23 22:57:19 +0000745 Processed.insert(*as);
746 if (tri_->isSubRegister(*as, reg) &&
747 SuperAdded.insert(*as) &&
748 RC->contains(*as)) {
749 Supers.push_back(*as);
750 }
751 }
752
753 // If the alias is a super-register, and the super-register is in the
754 // register class we are trying to allocate. Then add the weight to all
755 // sub-registers of the super-register even if they are not aliases.
756 // e.g. allocating for GR32, bh is not used, updating bl spill weight.
757 // bl should get the same spill weight otherwise it will be choosen
758 // as a spill candidate since spilling bh doesn't make ebx available.
759 for (unsigned i = 0, e = Supers.size(); i != e; ++i) {
Evan Chengc781a242009-05-03 18:32:42 +0000760 for (const unsigned *sr = tri_->getSubRegisters(Supers[i]); *sr; ++sr)
761 if (!Processed.count(*sr))
762 Weights[*sr] += weight;
Evan Cheng5d088fe2009-03-23 22:57:19 +0000763 }
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +0000764}
765
Bill Wendlinge23e00d2007-05-08 19:02:46 +0000766static
767RALinScan::IntervalPtrs::iterator
768FindIntervalInVector(RALinScan::IntervalPtrs &IP, LiveInterval *LI) {
769 for (RALinScan::IntervalPtrs::iterator I = IP.begin(), E = IP.end();
770 I != E; ++I)
Chris Lattnercbb56252004-11-18 02:42:27 +0000771 if (I->first == LI) return I;
772 return IP.end();
773}
774
Jim Grosbach662fb772010-09-01 21:48:06 +0000775static void RevertVectorIteratorsTo(RALinScan::IntervalPtrs &V,
776 SlotIndex Point){
Chris Lattner19828d42004-11-18 03:49:30 +0000777 for (unsigned i = 0, e = V.size(); i != e; ++i) {
Bill Wendlinge23e00d2007-05-08 19:02:46 +0000778 RALinScan::IntervalPtr &IP = V[i];
Chris Lattner19828d42004-11-18 03:49:30 +0000779 LiveInterval::iterator I = std::upper_bound(IP.first->begin(),
780 IP.second, Point);
781 if (I != IP.first->begin()) --I;
782 IP.second = I;
783 }
784}
Chris Lattnercbb56252004-11-18 02:42:27 +0000785
Evan Cheng3f32d652008-06-04 09:18:41 +0000786/// addStackInterval - Create a LiveInterval for stack if the specified live
787/// interval has been spilled.
788static void addStackInterval(LiveInterval *cur, LiveStacks *ls_,
Evan Chengc781a242009-05-03 18:32:42 +0000789 LiveIntervals *li_,
790 MachineRegisterInfo* mri_, VirtRegMap &vrm_) {
Evan Cheng3f32d652008-06-04 09:18:41 +0000791 int SS = vrm_.getStackSlot(cur->reg);
792 if (SS == VirtRegMap::NO_STACK_SLOT)
793 return;
Evan Chengc781a242009-05-03 18:32:42 +0000794
795 const TargetRegisterClass *RC = mri_->getRegClass(cur->reg);
796 LiveInterval &SI = ls_->getOrCreateInterval(SS, RC);
Evan Cheng9c3c2212008-06-06 07:54:39 +0000797
Evan Cheng3f32d652008-06-04 09:18:41 +0000798 VNInfo *VNI;
Evan Cheng54898932008-10-29 08:39:34 +0000799 if (SI.hasAtLeastOneValue())
Evan Cheng3f32d652008-06-04 09:18:41 +0000800 VNI = SI.getValNumInfo(0);
801 else
Lang Hames6e2968c2010-09-25 12:04:16 +0000802 VNI = SI.getNextValue(SlotIndex(), 0,
Lang Hames86511252009-09-04 20:41:11 +0000803 ls_->getVNInfoAllocator());
Evan Cheng3f32d652008-06-04 09:18:41 +0000804
805 LiveInterval &RI = li_->getInterval(cur->reg);
806 // FIXME: This may be overly conservative.
807 SI.MergeRangesInAsValue(RI, VNI);
Evan Cheng3f32d652008-06-04 09:18:41 +0000808}
809
Evan Cheng3e172252008-06-20 21:45:16 +0000810/// getConflictWeight - Return the number of conflicts between cur
811/// live interval and defs and uses of Reg weighted by loop depthes.
Evan Chengc781a242009-05-03 18:32:42 +0000812static
813float getConflictWeight(LiveInterval *cur, unsigned Reg, LiveIntervals *li_,
814 MachineRegisterInfo *mri_,
Jakob Stoklund Olesen9529a1c2010-07-19 18:41:20 +0000815 MachineLoopInfo *loopInfo) {
Evan Cheng3e172252008-06-20 21:45:16 +0000816 float Conflicts = 0;
817 for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(Reg),
818 E = mri_->reg_end(); I != E; ++I) {
819 MachineInstr *MI = &*I;
820 if (cur->liveAt(li_->getInstructionIndex(MI))) {
821 unsigned loopDepth = loopInfo->getLoopDepth(MI->getParent());
Chris Lattner87565c12010-05-15 17:10:24 +0000822 Conflicts += std::pow(10.0f, (float)loopDepth);
Evan Cheng3e172252008-06-20 21:45:16 +0000823 }
824 }
825 return Conflicts;
826}
827
828/// findIntervalsToSpill - Determine the intervals to spill for the
829/// specified interval. It's passed the physical registers whose spill
830/// weight is the lowest among all the registers whose live intervals
831/// conflict with the interval.
832void RALinScan::findIntervalsToSpill(LiveInterval *cur,
833 std::vector<std::pair<unsigned,float> > &Candidates,
834 unsigned NumCands,
835 SmallVector<LiveInterval*, 8> &SpillIntervals) {
836 // We have figured out the *best* register to spill. But there are other
837 // registers that are pretty good as well (spill weight within 3%). Spill
838 // the one that has fewest defs and uses that conflict with cur.
839 float Conflicts[3] = { 0.0f, 0.0f, 0.0f };
840 SmallVector<LiveInterval*, 8> SLIs[3];
841
Bill Wendlingc3115a02009-08-22 20:30:53 +0000842 DEBUG({
David Greene37277762010-01-05 01:25:20 +0000843 dbgs() << "\tConsidering " << NumCands << " candidates: ";
Bill Wendlingc3115a02009-08-22 20:30:53 +0000844 for (unsigned i = 0; i != NumCands; ++i)
David Greene37277762010-01-05 01:25:20 +0000845 dbgs() << tri_->getName(Candidates[i].first) << " ";
846 dbgs() << "\n";
Bill Wendlingc3115a02009-08-22 20:30:53 +0000847 });
Jim Grosbach662fb772010-09-01 21:48:06 +0000848
Evan Cheng3e172252008-06-20 21:45:16 +0000849 // Calculate the number of conflicts of each candidate.
850 for (IntervalPtrs::iterator i = active_.begin(); i != active_.end(); ++i) {
851 unsigned Reg = i->first->reg;
852 unsigned PhysReg = vrm_->getPhys(Reg);
853 if (!cur->overlapsFrom(*i->first, i->second))
854 continue;
855 for (unsigned j = 0; j < NumCands; ++j) {
856 unsigned Candidate = Candidates[j].first;
857 if (tri_->regsOverlap(PhysReg, Candidate)) {
858 if (NumCands > 1)
859 Conflicts[j] += getConflictWeight(cur, Reg, li_, mri_, loopInfo);
860 SLIs[j].push_back(i->first);
861 }
862 }
863 }
864
865 for (IntervalPtrs::iterator i = inactive_.begin(); i != inactive_.end(); ++i){
866 unsigned Reg = i->first->reg;
867 unsigned PhysReg = vrm_->getPhys(Reg);
868 if (!cur->overlapsFrom(*i->first, i->second-1))
869 continue;
870 for (unsigned j = 0; j < NumCands; ++j) {
871 unsigned Candidate = Candidates[j].first;
872 if (tri_->regsOverlap(PhysReg, Candidate)) {
873 if (NumCands > 1)
874 Conflicts[j] += getConflictWeight(cur, Reg, li_, mri_, loopInfo);
875 SLIs[j].push_back(i->first);
876 }
877 }
878 }
879
880 // Which is the best candidate?
881 unsigned BestCandidate = 0;
882 float MinConflicts = Conflicts[0];
883 for (unsigned i = 1; i != NumCands; ++i) {
884 if (Conflicts[i] < MinConflicts) {
885 BestCandidate = i;
886 MinConflicts = Conflicts[i];
887 }
888 }
889
890 std::copy(SLIs[BestCandidate].begin(), SLIs[BestCandidate].end(),
891 std::back_inserter(SpillIntervals));
892}
893
894namespace {
895 struct WeightCompare {
David Greene7cfd3362009-11-19 15:55:49 +0000896 private:
897 const RALinScan &Allocator;
898
899 public:
Douglas Gregorcabdd742009-12-19 07:05:23 +0000900 WeightCompare(const RALinScan &Alloc) : Allocator(Alloc) {}
David Greene7cfd3362009-11-19 15:55:49 +0000901
Evan Cheng3e172252008-06-20 21:45:16 +0000902 typedef std::pair<unsigned, float> RegWeightPair;
903 bool operator()(const RegWeightPair &LHS, const RegWeightPair &RHS) const {
David Greene7cfd3362009-11-19 15:55:49 +0000904 return LHS.second < RHS.second && !Allocator.isRecentlyUsed(LHS.first);
Evan Cheng3e172252008-06-20 21:45:16 +0000905 }
906 };
907}
908
909static bool weightsAreClose(float w1, float w2) {
910 if (!NewHeuristic)
911 return false;
912
913 float diff = w1 - w2;
914 if (diff <= 0.02f) // Within 0.02f
915 return true;
916 return (diff / w2) <= 0.05f; // Within 5%.
917}
918
Evan Cheng206d1852009-04-20 08:01:12 +0000919LiveInterval *RALinScan::hasNextReloadInterval(LiveInterval *cur) {
920 DenseMap<unsigned, unsigned>::iterator I = NextReloadMap.find(cur->reg);
921 if (I == NextReloadMap.end())
922 return 0;
923 return &li_->getInterval(I->second);
924}
925
926void RALinScan::DowngradeRegister(LiveInterval *li, unsigned Reg) {
927 bool isNew = DowngradedRegs.insert(Reg);
928 isNew = isNew; // Silence compiler warning.
929 assert(isNew && "Multiple reloads holding the same register?");
930 DowngradeMap.insert(std::make_pair(li->reg, Reg));
931 for (const unsigned *AS = tri_->getAliasSet(Reg); *AS; ++AS) {
932 isNew = DowngradedRegs.insert(*AS);
933 isNew = isNew; // Silence compiler warning.
934 assert(isNew && "Multiple reloads holding the same register?");
935 DowngradeMap.insert(std::make_pair(li->reg, *AS));
936 }
937 ++NumDowngrade;
938}
939
940void RALinScan::UpgradeRegister(unsigned Reg) {
941 if (Reg) {
942 DowngradedRegs.erase(Reg);
943 for (const unsigned *AS = tri_->getAliasSet(Reg); *AS; ++AS)
944 DowngradedRegs.erase(*AS);
945 }
946}
947
948namespace {
949 struct LISorter {
950 bool operator()(LiveInterval* A, LiveInterval* B) {
Lang Hames86511252009-09-04 20:41:11 +0000951 return A->beginIndex() < B->beginIndex();
Evan Cheng206d1852009-04-20 08:01:12 +0000952 }
953 };
954}
955
Chris Lattnercbb56252004-11-18 02:42:27 +0000956/// assignRegOrStackSlotAtInterval - assign a register if one is available, or
957/// spill.
Bill Wendlingc3115a02009-08-22 20:30:53 +0000958void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) {
David Greene37277762010-01-05 01:25:20 +0000959 DEBUG(dbgs() << "\tallocating current interval: ");
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +0000960
Evan Chengf30a49d2008-04-03 16:40:27 +0000961 // This is an implicitly defined live interval, just assign any register.
Evan Cheng841ee1a2008-09-18 22:38:47 +0000962 const TargetRegisterClass *RC = mri_->getRegClass(cur->reg);
Evan Chengf30a49d2008-04-03 16:40:27 +0000963 if (cur->empty()) {
Evan Cheng90f95f82009-06-14 20:22:55 +0000964 unsigned physReg = vrm_->getRegAllocPref(cur->reg);
Jim Grosbach5a4cbea2010-09-01 21:34:41 +0000965 if (!physReg)
966 physReg = getFirstNonReservedPhysReg(RC);
David Greene37277762010-01-05 01:25:20 +0000967 DEBUG(dbgs() << tri_->getName(physReg) << '\n');
Evan Chengf30a49d2008-04-03 16:40:27 +0000968 // Note the register is not really in use.
969 vrm_->assignVirt2Phys(cur->reg, physReg);
Evan Chengf30a49d2008-04-03 16:40:27 +0000970 return;
971 }
972
Evan Cheng5b16cd22009-05-01 01:03:49 +0000973 backUpRegUses();
Alkis Evlogimenos169cfd02003-12-21 05:43:40 +0000974
Chris Lattnera6c17502005-08-22 20:20:42 +0000975 std::vector<std::pair<unsigned, float> > SpillWeightsToAdd;
Lang Hames233a60e2009-11-03 23:52:08 +0000976 SlotIndex StartPosition = cur->beginIndex();
Chris Lattnerb9805782005-08-23 22:27:31 +0000977 const TargetRegisterClass *RCLeader = RelatedRegClasses.getLeaderValue(RC);
Evan Chengc92da382007-11-03 07:20:12 +0000978
Evan Chengd0deec22009-01-20 00:16:18 +0000979 // If start of this live interval is defined by a move instruction and its
980 // source is assigned a physical register that is compatible with the target
981 // register class, then we should try to assign it the same register.
Evan Chengc92da382007-11-03 07:20:12 +0000982 // This can happen when the move is from a larger register class to a smaller
983 // one, e.g. X86::mov32to32_. These move instructions are not coalescable.
Evan Cheng90f95f82009-06-14 20:22:55 +0000984 if (!vrm_->getRegAllocPref(cur->reg) && cur->hasAtLeastOneValue()) {
Evan Chengd0deec22009-01-20 00:16:18 +0000985 VNInfo *vni = cur->begin()->valno;
Lang Hames6e2968c2010-09-25 12:04:16 +0000986 if (!vni->isUnused()) {
Evan Chengc92da382007-11-03 07:20:12 +0000987 MachineInstr *CopyMI = li_->getInstructionFromIndex(vni->def);
Jakob Stoklund Olesen04c528a2010-07-16 04:45:42 +0000988 if (CopyMI && CopyMI->isCopy()) {
989 unsigned DstSubReg = CopyMI->getOperand(0).getSubReg();
990 unsigned SrcReg = CopyMI->getOperand(1).getReg();
991 unsigned SrcSubReg = CopyMI->getOperand(1).getSubReg();
Jakob Stoklund Olesen0bc25f42010-07-08 16:40:22 +0000992 unsigned Reg = 0;
993 if (TargetRegisterInfo::isPhysicalRegister(SrcReg))
994 Reg = SrcReg;
995 else if (vrm_->isAssignedReg(SrcReg))
996 Reg = vrm_->getPhys(SrcReg);
997 if (Reg) {
998 if (SrcSubReg)
999 Reg = tri_->getSubReg(Reg, SrcSubReg);
1000 if (DstSubReg)
1001 Reg = tri_->getMatchingSuperReg(Reg, DstSubReg, RC);
1002 if (Reg && allocatableRegs_[Reg] && RC->contains(Reg))
1003 mri_->setRegAllocationHint(cur->reg, 0, Reg);
1004 }
Evan Chengc92da382007-11-03 07:20:12 +00001005 }
1006 }
1007 }
1008
Evan Cheng5b16cd22009-05-01 01:03:49 +00001009 // For every interval in inactive we overlap with, mark the
Chris Lattnera6c17502005-08-22 20:20:42 +00001010 // register as not free and update spill weights.
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +00001011 for (IntervalPtrs::const_iterator i = inactive_.begin(),
1012 e = inactive_.end(); i != e; ++i) {
Chris Lattnerb9805782005-08-23 22:27:31 +00001013 unsigned Reg = i->first->reg;
Dan Gohman6f0d0242008-02-10 18:45:23 +00001014 assert(TargetRegisterInfo::isVirtualRegister(Reg) &&
Chris Lattnerb9805782005-08-23 22:27:31 +00001015 "Can only allocate virtual registers!");
Evan Cheng841ee1a2008-09-18 22:38:47 +00001016 const TargetRegisterClass *RegRC = mri_->getRegClass(Reg);
Jim Grosbach662fb772010-09-01 21:48:06 +00001017 // If this is not in a related reg class to the register we're allocating,
Chris Lattnerb9805782005-08-23 22:27:31 +00001018 // don't check it.
1019 if (RelatedRegClasses.getLeaderValue(RegRC) == RCLeader &&
1020 cur->overlapsFrom(*i->first, i->second-1)) {
1021 Reg = vrm_->getPhys(Reg);
Evan Cheng5b16cd22009-05-01 01:03:49 +00001022 addRegUse(Reg);
Chris Lattnerb9805782005-08-23 22:27:31 +00001023 SpillWeightsToAdd.push_back(std::make_pair(Reg, i->first->weight));
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +00001024 }
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +00001025 }
Jim Grosbach662fb772010-09-01 21:48:06 +00001026
Chris Lattnera411cbc2005-08-22 20:59:30 +00001027 // Speculatively check to see if we can get a register right now. If not,
1028 // we know we won't be able to by adding more constraints. If so, we can
1029 // check to see if it is valid. Doing an exhaustive search of the fixed_ list
1030 // is very bad (it contains all callee clobbered registers for any functions
1031 // with a call), so we want to avoid doing that if possible.
1032 unsigned physReg = getFreePhysReg(cur);
Evan Cheng676dd7c2008-03-11 07:19:34 +00001033 unsigned BestPhysReg = physReg;
Chris Lattnera411cbc2005-08-22 20:59:30 +00001034 if (physReg) {
1035 // We got a register. However, if it's in the fixed_ list, we might
Chris Lattnere836ad62005-08-30 21:03:36 +00001036 // conflict with it. Check to see if we conflict with it or any of its
1037 // aliases.
Evan Chengc92da382007-11-03 07:20:12 +00001038 SmallSet<unsigned, 8> RegAliases;
Dan Gohman6f0d0242008-02-10 18:45:23 +00001039 for (const unsigned *AS = tri_->getAliasSet(physReg); *AS; ++AS)
Chris Lattnere836ad62005-08-30 21:03:36 +00001040 RegAliases.insert(*AS);
Jim Grosbach662fb772010-09-01 21:48:06 +00001041
Chris Lattnera411cbc2005-08-22 20:59:30 +00001042 bool ConflictsWithFixed = false;
1043 for (unsigned i = 0, e = fixed_.size(); i != e; ++i) {
Jim Laskeye719d9f2006-10-24 14:35:25 +00001044 IntervalPtr &IP = fixed_[i];
1045 if (physReg == IP.first->reg || RegAliases.count(IP.first->reg)) {
Chris Lattnera411cbc2005-08-22 20:59:30 +00001046 // Okay, this reg is on the fixed list. Check to see if we actually
1047 // conflict.
Chris Lattnera411cbc2005-08-22 20:59:30 +00001048 LiveInterval *I = IP.first;
Lang Hames86511252009-09-04 20:41:11 +00001049 if (I->endIndex() > StartPosition) {
Chris Lattnera411cbc2005-08-22 20:59:30 +00001050 LiveInterval::iterator II = I->advanceTo(IP.second, StartPosition);
1051 IP.second = II;
1052 if (II != I->begin() && II->start > StartPosition)
1053 --II;
Chris Lattnere836ad62005-08-30 21:03:36 +00001054 if (cur->overlapsFrom(*I, II)) {
Chris Lattnera411cbc2005-08-22 20:59:30 +00001055 ConflictsWithFixed = true;
Chris Lattnere836ad62005-08-30 21:03:36 +00001056 break;
1057 }
Chris Lattnera411cbc2005-08-22 20:59:30 +00001058 }
Chris Lattnerf348e3a2004-11-18 04:33:31 +00001059 }
Alkis Evlogimenos169cfd02003-12-21 05:43:40 +00001060 }
Jim Grosbach662fb772010-09-01 21:48:06 +00001061
Chris Lattnera411cbc2005-08-22 20:59:30 +00001062 // Okay, the register picked by our speculative getFreePhysReg call turned
1063 // out to be in use. Actually add all of the conflicting fixed registers to
Evan Cheng5b16cd22009-05-01 01:03:49 +00001064 // regUse_ so we can do an accurate query.
Chris Lattnera411cbc2005-08-22 20:59:30 +00001065 if (ConflictsWithFixed) {
Chris Lattnerb9805782005-08-23 22:27:31 +00001066 // For every interval in fixed we overlap with, mark the register as not
1067 // free and update spill weights.
Chris Lattnera411cbc2005-08-22 20:59:30 +00001068 for (unsigned i = 0, e = fixed_.size(); i != e; ++i) {
1069 IntervalPtr &IP = fixed_[i];
1070 LiveInterval *I = IP.first;
Chris Lattnerb9805782005-08-23 22:27:31 +00001071
1072 const TargetRegisterClass *RegRC = OneClassForEachPhysReg[I->reg];
Jim Grosbach662fb772010-09-01 21:48:06 +00001073 if (RelatedRegClasses.getLeaderValue(RegRC) == RCLeader &&
Lang Hames86511252009-09-04 20:41:11 +00001074 I->endIndex() > StartPosition) {
Chris Lattnera411cbc2005-08-22 20:59:30 +00001075 LiveInterval::iterator II = I->advanceTo(IP.second, StartPosition);
1076 IP.second = II;
1077 if (II != I->begin() && II->start > StartPosition)
1078 --II;
1079 if (cur->overlapsFrom(*I, II)) {
1080 unsigned reg = I->reg;
Evan Cheng5b16cd22009-05-01 01:03:49 +00001081 addRegUse(reg);
Chris Lattnera411cbc2005-08-22 20:59:30 +00001082 SpillWeightsToAdd.push_back(std::make_pair(reg, I->weight));
1083 }
1084 }
1085 }
Alkis Evlogimenos169cfd02003-12-21 05:43:40 +00001086
Evan Cheng5b16cd22009-05-01 01:03:49 +00001087 // Using the newly updated regUse_ object, which includes conflicts in the
Chris Lattnera411cbc2005-08-22 20:59:30 +00001088 // future, see if there are any registers available.
1089 physReg = getFreePhysReg(cur);
1090 }
1091 }
Jim Grosbach662fb772010-09-01 21:48:06 +00001092
Chris Lattnera6c17502005-08-22 20:20:42 +00001093 // Restore the physical register tracker, removing information about the
1094 // future.
Evan Cheng5b16cd22009-05-01 01:03:49 +00001095 restoreRegUses();
Jim Grosbach662fb772010-09-01 21:48:06 +00001096
Evan Cheng5b16cd22009-05-01 01:03:49 +00001097 // If we find a free register, we are done: assign this virtual to
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +00001098 // the free physical register and add this interval to the active
1099 // list.
1100 if (physReg) {
David Greene37277762010-01-05 01:25:20 +00001101 DEBUG(dbgs() << tri_->getName(physReg) << '\n');
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +00001102 vrm_->assignVirt2Phys(cur->reg, physReg);
Evan Cheng5b16cd22009-05-01 01:03:49 +00001103 addRegUse(physReg);
Chris Lattnercbb56252004-11-18 02:42:27 +00001104 active_.push_back(std::make_pair(cur, cur->begin()));
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +00001105 handled_.push_back(cur);
Evan Cheng206d1852009-04-20 08:01:12 +00001106
1107 // "Upgrade" the physical register since it has been allocated.
1108 UpgradeRegister(physReg);
1109 if (LiveInterval *NextReloadLI = hasNextReloadInterval(cur)) {
1110 // "Downgrade" physReg to try to keep physReg from being allocated until
Jim Grosbach662fb772010-09-01 21:48:06 +00001111 // the next reload from the same SS is allocated.
Evan Cheng358dec52009-06-15 08:28:29 +00001112 mri_->setRegAllocationHint(NextReloadLI->reg, 0, physReg);
Evan Cheng206d1852009-04-20 08:01:12 +00001113 DowngradeRegister(cur, physReg);
1114 }
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +00001115 return;
1116 }
David Greene37277762010-01-05 01:25:20 +00001117 DEBUG(dbgs() << "no free registers\n");
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +00001118
Chris Lattnera6c17502005-08-22 20:20:42 +00001119 // Compile the spill weights into an array that is better for scanning.
Evan Cheng3e172252008-06-20 21:45:16 +00001120 std::vector<float> SpillWeights(tri_->getNumRegs(), 0.0f);
Chris Lattnera6c17502005-08-22 20:20:42 +00001121 for (std::vector<std::pair<unsigned, float> >::iterator
1122 I = SpillWeightsToAdd.begin(), E = SpillWeightsToAdd.end(); I != E; ++I)
Evan Cheng5d088fe2009-03-23 22:57:19 +00001123 updateSpillWeights(SpillWeights, I->first, I->second, RC);
Jim Grosbach662fb772010-09-01 21:48:06 +00001124
Chris Lattnera6c17502005-08-22 20:20:42 +00001125 // for each interval in active, update spill weights.
1126 for (IntervalPtrs::const_iterator i = active_.begin(), e = active_.end();
1127 i != e; ++i) {
1128 unsigned reg = i->first->reg;
Dan Gohman6f0d0242008-02-10 18:45:23 +00001129 assert(TargetRegisterInfo::isVirtualRegister(reg) &&
Chris Lattnera6c17502005-08-22 20:20:42 +00001130 "Can only allocate virtual registers!");
1131 reg = vrm_->getPhys(reg);
Evan Cheng5d088fe2009-03-23 22:57:19 +00001132 updateSpillWeights(SpillWeights, reg, i->first->weight, RC);
Chris Lattnera6c17502005-08-22 20:20:42 +00001133 }
Jim Grosbach662fb772010-09-01 21:48:06 +00001134
David Greene37277762010-01-05 01:25:20 +00001135 DEBUG(dbgs() << "\tassigning stack slot at interval "<< *cur << ":\n");
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +00001136
Chris Lattnerc8e2c552006-03-25 23:00:56 +00001137 // Find a register to spill.
Jim Laskey7902c752006-11-07 12:25:45 +00001138 float minWeight = HUGE_VALF;
Evan Cheng90f95f82009-06-14 20:22:55 +00001139 unsigned minReg = 0;
Evan Cheng3e172252008-06-20 21:45:16 +00001140
1141 bool Found = false;
1142 std::vector<std::pair<unsigned,float> > RegsWeights;
Evan Cheng20b0abc2007-04-17 20:32:26 +00001143 if (!minReg || SpillWeights[minReg] == HUGE_VALF)
1144 for (TargetRegisterClass::iterator i = RC->allocation_order_begin(*mf_),
1145 e = RC->allocation_order_end(*mf_); i != e; ++i) {
1146 unsigned reg = *i;
Evan Cheng3e172252008-06-20 21:45:16 +00001147 float regWeight = SpillWeights[reg];
Jim Grosbach188da252010-09-01 22:48:34 +00001148 // Don't even consider reserved regs.
1149 if (reservedRegs_.test(reg))
1150 continue;
Jim Grosbach067a6482010-09-01 21:04:27 +00001151 // Skip recently allocated registers and reserved registers.
Jim Grosbach188da252010-09-01 22:48:34 +00001152 if (minWeight > regWeight && !isRecentlyUsed(reg))
Evan Cheng3e172252008-06-20 21:45:16 +00001153 Found = true;
1154 RegsWeights.push_back(std::make_pair(reg, regWeight));
Alkis Evlogimenos3bf564a2003-12-23 18:00:33 +00001155 }
Jim Grosbach662fb772010-09-01 21:48:06 +00001156
Chris Lattnerc8e2c552006-03-25 23:00:56 +00001157 // If we didn't find a register that is spillable, try aliases?
Evan Cheng3e172252008-06-20 21:45:16 +00001158 if (!Found) {
Evan Cheng3b6d56c2006-05-12 19:07:46 +00001159 for (TargetRegisterClass::iterator i = RC->allocation_order_begin(*mf_),
1160 e = RC->allocation_order_end(*mf_); i != e; ++i) {
1161 unsigned reg = *i;
Jim Grosbach067a6482010-09-01 21:04:27 +00001162 if (reservedRegs_.test(reg))
1163 continue;
Evan Cheng3b6d56c2006-05-12 19:07:46 +00001164 // No need to worry about if the alias register size < regsize of RC.
1165 // We are going to spill all registers that alias it anyway.
Evan Cheng3e172252008-06-20 21:45:16 +00001166 for (const unsigned* as = tri_->getAliasSet(reg); *as; ++as)
1167 RegsWeights.push_back(std::make_pair(*as, SpillWeights[*as]));
Evan Cheng676dd7c2008-03-11 07:19:34 +00001168 }
Evan Cheng3b6d56c2006-05-12 19:07:46 +00001169 }
Evan Cheng3e172252008-06-20 21:45:16 +00001170
1171 // Sort all potential spill candidates by weight.
David Greene7cfd3362009-11-19 15:55:49 +00001172 std::sort(RegsWeights.begin(), RegsWeights.end(), WeightCompare(*this));
Evan Cheng3e172252008-06-20 21:45:16 +00001173 minReg = RegsWeights[0].first;
1174 minWeight = RegsWeights[0].second;
1175 if (minWeight == HUGE_VALF) {
1176 // All registers must have inf weight. Just grab one!
Jim Grosbach5a4cbea2010-09-01 21:34:41 +00001177 minReg = BestPhysReg ? BestPhysReg : getFirstNonReservedPhysReg(RC);
Owen Andersona1566f22008-07-22 22:46:49 +00001178 if (cur->weight == HUGE_VALF ||
Evan Cheng5e8d9de2008-09-20 01:28:05 +00001179 li_->getApproximateInstructionCount(*cur) == 0) {
Evan Cheng3e172252008-06-20 21:45:16 +00001180 // Spill a physical register around defs and uses.
Evan Cheng206d1852009-04-20 08:01:12 +00001181 if (li_->spillPhysRegAroundRegDefsUses(*cur, minReg, *vrm_)) {
Evan Cheng96f3fd92009-04-29 07:16:34 +00001182 // spillPhysRegAroundRegDefsUses may have invalidated iterator stored
1183 // in fixed_. Reset them.
1184 for (unsigned i = 0, e = fixed_.size(); i != e; ++i) {
1185 IntervalPtr &IP = fixed_[i];
1186 LiveInterval *I = IP.first;
1187 if (I->reg == minReg || tri_->isSubRegister(minReg, I->reg))
1188 IP.second = I->advanceTo(I->begin(), StartPosition);
1189 }
1190
Evan Cheng206d1852009-04-20 08:01:12 +00001191 DowngradedRegs.clear();
Evan Cheng2824a652009-03-23 18:24:37 +00001192 assignRegOrStackSlotAtInterval(cur);
Evan Cheng206d1852009-04-20 08:01:12 +00001193 } else {
Lang Hames233a60e2009-11-03 23:52:08 +00001194 assert(false && "Ran out of registers during register allocation!");
Chris Lattner75361b62010-04-07 22:58:41 +00001195 report_fatal_error("Ran out of registers during register allocation!");
Evan Cheng2824a652009-03-23 18:24:37 +00001196 }
Evan Cheng5e8d9de2008-09-20 01:28:05 +00001197 return;
1198 }
Evan Cheng3e172252008-06-20 21:45:16 +00001199 }
1200
1201 // Find up to 3 registers to consider as spill candidates.
1202 unsigned LastCandidate = RegsWeights.size() >= 3 ? 3 : 1;
1203 while (LastCandidate > 1) {
1204 if (weightsAreClose(RegsWeights[LastCandidate-1].second, minWeight))
1205 break;
1206 --LastCandidate;
1207 }
1208
Bill Wendlingc3115a02009-08-22 20:30:53 +00001209 DEBUG({
David Greene37277762010-01-05 01:25:20 +00001210 dbgs() << "\t\tregister(s) with min weight(s): ";
Bill Wendlingc3115a02009-08-22 20:30:53 +00001211
1212 for (unsigned i = 0; i != LastCandidate; ++i)
David Greene37277762010-01-05 01:25:20 +00001213 dbgs() << tri_->getName(RegsWeights[i].first)
Bill Wendlingc3115a02009-08-22 20:30:53 +00001214 << " (" << RegsWeights[i].second << ")\n";
1215 });
Alkis Evlogimenos3bf564a2003-12-23 18:00:33 +00001216
Evan Cheng206d1852009-04-20 08:01:12 +00001217 // If the current has the minimum weight, we need to spill it and
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +00001218 // add any added intervals back to unhandled, and restart
1219 // linearscan.
Jim Laskey7902c752006-11-07 12:25:45 +00001220 if (cur->weight != HUGE_VALF && cur->weight <= minWeight) {
David Greene37277762010-01-05 01:25:20 +00001221 DEBUG(dbgs() << "\t\t\tspilling(c): " << *cur << '\n');
Jakob Stoklund Olesen0a2b2a12010-08-13 22:56:53 +00001222 SmallVector<LiveInterval*, 8> spillIs, added;
Jakob Stoklund Olesen67674e22010-06-24 20:54:29 +00001223 spiller_->spill(cur, added, spillIs);
Lang Hamese2b201b2009-05-18 19:03:16 +00001224
Evan Cheng206d1852009-04-20 08:01:12 +00001225 std::sort(added.begin(), added.end(), LISorter());
Evan Chengc781a242009-05-03 18:32:42 +00001226 addStackInterval(cur, ls_, li_, mri_, *vrm_);
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +00001227 if (added.empty())
1228 return; // Early exit if all spills were folded.
Alkis Evlogimenosf5eaf162004-02-06 18:08:18 +00001229
Evan Cheng206d1852009-04-20 08:01:12 +00001230 // Merge added with unhandled. Note that we have already sorted
1231 // intervals returned by addIntervalsForSpills by their starting
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +00001232 // point.
Evan Chengc4f718a2009-04-20 17:23:48 +00001233 // This also update the NextReloadMap. That is, it adds mapping from a
1234 // register defined by a reload from SS to the next reload from SS in the
1235 // same basic block.
1236 MachineBasicBlock *LastReloadMBB = 0;
1237 LiveInterval *LastReload = 0;
1238 int LastReloadSS = VirtRegMap::NO_STACK_SLOT;
1239 for (unsigned i = 0, e = added.size(); i != e; ++i) {
1240 LiveInterval *ReloadLi = added[i];
1241 if (ReloadLi->weight == HUGE_VALF &&
1242 li_->getApproximateInstructionCount(*ReloadLi) == 0) {
Lang Hames233a60e2009-11-03 23:52:08 +00001243 SlotIndex ReloadIdx = ReloadLi->beginIndex();
Evan Chengc4f718a2009-04-20 17:23:48 +00001244 MachineBasicBlock *ReloadMBB = li_->getMBBFromIndex(ReloadIdx);
1245 int ReloadSS = vrm_->getStackSlot(ReloadLi->reg);
1246 if (LastReloadMBB == ReloadMBB && LastReloadSS == ReloadSS) {
1247 // Last reload of same SS is in the same MBB. We want to try to
1248 // allocate both reloads the same register and make sure the reg
1249 // isn't clobbered in between if at all possible.
Lang Hames86511252009-09-04 20:41:11 +00001250 assert(LastReload->beginIndex() < ReloadIdx);
Evan Chengc4f718a2009-04-20 17:23:48 +00001251 NextReloadMap.insert(std::make_pair(LastReload->reg, ReloadLi->reg));
1252 }
1253 LastReloadMBB = ReloadMBB;
1254 LastReload = ReloadLi;
1255 LastReloadSS = ReloadSS;
1256 }
1257 unhandled_.push(ReloadLi);
1258 }
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +00001259 return;
1260 }
1261
Chris Lattner19828d42004-11-18 03:49:30 +00001262 ++NumBacktracks;
1263
Evan Cheng206d1852009-04-20 08:01:12 +00001264 // Push the current interval back to unhandled since we are going
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +00001265 // to re-run at least this iteration. Since we didn't modify it it
1266 // should go back right in the front of the list
1267 unhandled_.push(cur);
1268
Dan Gohman6f0d0242008-02-10 18:45:23 +00001269 assert(TargetRegisterInfo::isPhysicalRegister(minReg) &&
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +00001270 "did not choose a register to spill?");
Chris Lattner19828d42004-11-18 03:49:30 +00001271
Evan Cheng3e172252008-06-20 21:45:16 +00001272 // We spill all intervals aliasing the register with
1273 // minimum weight, rollback to the interval with the earliest
1274 // start point and let the linear scan algorithm run again
1275 SmallVector<LiveInterval*, 8> spillIs;
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +00001276
Evan Cheng3e172252008-06-20 21:45:16 +00001277 // Determine which intervals have to be spilled.
1278 findIntervalsToSpill(cur, RegsWeights, LastCandidate, spillIs);
1279
1280 // Set of spilled vregs (used later to rollback properly)
1281 SmallSet<unsigned, 8> spilled;
1282
1283 // The earliest start of a Spilled interval indicates up to where
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +00001284 // in handled we need to roll back
Jim Grosbach662fb772010-09-01 21:48:06 +00001285 assert(!spillIs.empty() && "No spill intervals?");
Lang Hames61945692009-12-09 05:39:12 +00001286 SlotIndex earliestStart = spillIs[0]->beginIndex();
Jakob Stoklund Olesen0a2b2a12010-08-13 22:56:53 +00001287
Evan Cheng3e172252008-06-20 21:45:16 +00001288 // Spill live intervals of virtual regs mapped to the physical register we
Chris Lattner19828d42004-11-18 03:49:30 +00001289 // want to clear (and its aliases). We only spill those that overlap with the
1290 // current interval as the rest do not affect its allocation. we also keep
1291 // track of the earliest start of all spilled live intervals since this will
1292 // mark our rollback point.
Jakob Stoklund Olesen0a2b2a12010-08-13 22:56:53 +00001293 SmallVector<LiveInterval*, 8> added;
Evan Cheng3e172252008-06-20 21:45:16 +00001294 while (!spillIs.empty()) {
1295 LiveInterval *sli = spillIs.back();
1296 spillIs.pop_back();
David Greene37277762010-01-05 01:25:20 +00001297 DEBUG(dbgs() << "\t\t\tspilling(a): " << *sli << '\n');
Lang Hames61945692009-12-09 05:39:12 +00001298 if (sli->beginIndex() < earliestStart)
1299 earliestStart = sli->beginIndex();
Jakob Stoklund Olesen0a2b2a12010-08-13 22:56:53 +00001300 spiller_->spill(sli, added, spillIs);
Evan Chengc781a242009-05-03 18:32:42 +00001301 addStackInterval(sli, ls_, li_, mri_, *vrm_);
Evan Cheng3e172252008-06-20 21:45:16 +00001302 spilled.insert(sli->reg);
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +00001303 }
1304
Jakob Stoklund Olesen0a2b2a12010-08-13 22:56:53 +00001305 // Include any added intervals in earliestStart.
1306 for (unsigned i = 0, e = added.size(); i != e; ++i) {
1307 SlotIndex SI = added[i]->beginIndex();
1308 if (SI < earliestStart)
1309 earliestStart = SI;
1310 }
1311
David Greene37277762010-01-05 01:25:20 +00001312 DEBUG(dbgs() << "\t\trolling back to: " << earliestStart << '\n');
Chris Lattnercbb56252004-11-18 02:42:27 +00001313
1314 // Scan handled in reverse order up to the earliest start of a
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +00001315 // spilled live interval and undo each one, restoring the state of
Chris Lattnercbb56252004-11-18 02:42:27 +00001316 // unhandled.
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +00001317 while (!handled_.empty()) {
1318 LiveInterval* i = handled_.back();
Chris Lattnercbb56252004-11-18 02:42:27 +00001319 // If this interval starts before t we are done.
Lang Hames61945692009-12-09 05:39:12 +00001320 if (!i->empty() && i->beginIndex() < earliestStart)
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +00001321 break;
David Greene37277762010-01-05 01:25:20 +00001322 DEBUG(dbgs() << "\t\t\tundo changes for: " << *i << '\n');
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +00001323 handled_.pop_back();
Chris Lattnercbb56252004-11-18 02:42:27 +00001324
1325 // When undoing a live interval allocation we must know if it is active or
Evan Cheng5b16cd22009-05-01 01:03:49 +00001326 // inactive to properly update regUse_ and the VirtRegMap.
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +00001327 IntervalPtrs::iterator it;
Chris Lattnercbb56252004-11-18 02:42:27 +00001328 if ((it = FindIntervalInVector(active_, i)) != active_.end()) {
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +00001329 active_.erase(it);
Dan Gohman6f0d0242008-02-10 18:45:23 +00001330 assert(!TargetRegisterInfo::isPhysicalRegister(i->reg));
Chris Lattnerffab4222006-02-23 06:44:17 +00001331 if (!spilled.count(i->reg))
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +00001332 unhandled_.push(i);
Evan Cheng5b16cd22009-05-01 01:03:49 +00001333 delRegUse(vrm_->getPhys(i->reg));
Chris Lattnerffab4222006-02-23 06:44:17 +00001334 vrm_->clearVirt(i->reg);
Chris Lattnercbb56252004-11-18 02:42:27 +00001335 } else if ((it = FindIntervalInVector(inactive_, i)) != inactive_.end()) {
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +00001336 inactive_.erase(it);
Dan Gohman6f0d0242008-02-10 18:45:23 +00001337 assert(!TargetRegisterInfo::isPhysicalRegister(i->reg));
Chris Lattnerffab4222006-02-23 06:44:17 +00001338 if (!spilled.count(i->reg))
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +00001339 unhandled_.push(i);
Chris Lattnerffab4222006-02-23 06:44:17 +00001340 vrm_->clearVirt(i->reg);
Chris Lattnerc8b9f332004-11-18 06:01:45 +00001341 } else {
Dan Gohman6f0d0242008-02-10 18:45:23 +00001342 assert(TargetRegisterInfo::isVirtualRegister(i->reg) &&
Chris Lattnerc8b9f332004-11-18 06:01:45 +00001343 "Can only allocate virtual registers!");
1344 vrm_->clearVirt(i->reg);
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +00001345 unhandled_.push(i);
1346 }
Evan Cheng9aeaf752007-11-04 08:32:21 +00001347
Evan Cheng206d1852009-04-20 08:01:12 +00001348 DenseMap<unsigned, unsigned>::iterator ii = DowngradeMap.find(i->reg);
1349 if (ii == DowngradeMap.end())
1350 // It interval has a preference, it must be defined by a copy. Clear the
1351 // preference now since the source interval allocation may have been
1352 // undone as well.
Evan Cheng358dec52009-06-15 08:28:29 +00001353 mri_->setRegAllocationHint(i->reg, 0, 0);
Evan Cheng206d1852009-04-20 08:01:12 +00001354 else {
1355 UpgradeRegister(ii->second);
1356 }
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +00001357 }
1358
Chris Lattner19828d42004-11-18 03:49:30 +00001359 // Rewind the iterators in the active, inactive, and fixed lists back to the
1360 // point we reverted to.
1361 RevertVectorIteratorsTo(active_, earliestStart);
1362 RevertVectorIteratorsTo(inactive_, earliestStart);
1363 RevertVectorIteratorsTo(fixed_, earliestStart);
1364
Evan Cheng206d1852009-04-20 08:01:12 +00001365 // Scan the rest and undo each interval that expired after t and
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +00001366 // insert it in active (the next iteration of the algorithm will
1367 // put it in inactive if required)
Chris Lattnercbb56252004-11-18 02:42:27 +00001368 for (unsigned i = 0, e = handled_.size(); i != e; ++i) {
1369 LiveInterval *HI = handled_[i];
1370 if (!HI->expiredAt(earliestStart) &&
Lang Hames86511252009-09-04 20:41:11 +00001371 HI->expiredAt(cur->beginIndex())) {
David Greene37277762010-01-05 01:25:20 +00001372 DEBUG(dbgs() << "\t\t\tundo changes for: " << *HI << '\n');
Chris Lattnercbb56252004-11-18 02:42:27 +00001373 active_.push_back(std::make_pair(HI, HI->begin()));
Dan Gohman6f0d0242008-02-10 18:45:23 +00001374 assert(!TargetRegisterInfo::isPhysicalRegister(HI->reg));
Evan Cheng5b16cd22009-05-01 01:03:49 +00001375 addRegUse(vrm_->getPhys(HI->reg));
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +00001376 }
1377 }
1378
Evan Cheng206d1852009-04-20 08:01:12 +00001379 // Merge added with unhandled.
1380 // This also update the NextReloadMap. That is, it adds mapping from a
1381 // register defined by a reload from SS to the next reload from SS in the
1382 // same basic block.
1383 MachineBasicBlock *LastReloadMBB = 0;
1384 LiveInterval *LastReload = 0;
1385 int LastReloadSS = VirtRegMap::NO_STACK_SLOT;
1386 std::sort(added.begin(), added.end(), LISorter());
1387 for (unsigned i = 0, e = added.size(); i != e; ++i) {
1388 LiveInterval *ReloadLi = added[i];
1389 if (ReloadLi->weight == HUGE_VALF &&
1390 li_->getApproximateInstructionCount(*ReloadLi) == 0) {
Lang Hames233a60e2009-11-03 23:52:08 +00001391 SlotIndex ReloadIdx = ReloadLi->beginIndex();
Evan Cheng206d1852009-04-20 08:01:12 +00001392 MachineBasicBlock *ReloadMBB = li_->getMBBFromIndex(ReloadIdx);
1393 int ReloadSS = vrm_->getStackSlot(ReloadLi->reg);
1394 if (LastReloadMBB == ReloadMBB && LastReloadSS == ReloadSS) {
1395 // Last reload of same SS is in the same MBB. We want to try to
1396 // allocate both reloads the same register and make sure the reg
1397 // isn't clobbered in between if at all possible.
Lang Hames86511252009-09-04 20:41:11 +00001398 assert(LastReload->beginIndex() < ReloadIdx);
Evan Cheng206d1852009-04-20 08:01:12 +00001399 NextReloadMap.insert(std::make_pair(LastReload->reg, ReloadLi->reg));
1400 }
1401 LastReloadMBB = ReloadMBB;
1402 LastReload = ReloadLi;
1403 LastReloadSS = ReloadSS;
1404 }
1405 unhandled_.push(ReloadLi);
1406 }
1407}
1408
Evan Cheng358dec52009-06-15 08:28:29 +00001409unsigned RALinScan::getFreePhysReg(LiveInterval* cur,
1410 const TargetRegisterClass *RC,
Evan Cheng206d1852009-04-20 08:01:12 +00001411 unsigned MaxInactiveCount,
1412 SmallVector<unsigned, 256> &inactiveCounts,
1413 bool SkipDGRegs) {
1414 unsigned FreeReg = 0;
1415 unsigned FreeRegInactiveCount = 0;
1416
Evan Chengf9f1da12009-06-18 02:04:01 +00001417 std::pair<unsigned, unsigned> Hint = mri_->getRegAllocationHint(cur->reg);
1418 // Resolve second part of the hint (if possible) given the current allocation.
1419 unsigned physReg = Hint.second;
1420 if (physReg &&
1421 TargetRegisterInfo::isVirtualRegister(physReg) && vrm_->hasPhys(physReg))
1422 physReg = vrm_->getPhys(physReg);
1423
Evan Cheng358dec52009-06-15 08:28:29 +00001424 TargetRegisterClass::iterator I, E;
Evan Chengf9f1da12009-06-18 02:04:01 +00001425 tie(I, E) = tri_->getAllocationOrder(RC, Hint.first, physReg, *mf_);
Evan Cheng206d1852009-04-20 08:01:12 +00001426 assert(I != E && "No allocatable register in this register class!");
1427
1428 // Scan for the first available register.
1429 for (; I != E; ++I) {
1430 unsigned Reg = *I;
1431 // Ignore "downgraded" registers.
1432 if (SkipDGRegs && DowngradedRegs.count(Reg))
1433 continue;
Jim Grosbach067a6482010-09-01 21:04:27 +00001434 // Skip reserved registers.
1435 if (reservedRegs_.test(Reg))
1436 continue;
David Greene7cfd3362009-11-19 15:55:49 +00001437 // Skip recently allocated registers.
1438 if (isRegAvail(Reg) && !isRecentlyUsed(Reg)) {
Evan Cheng206d1852009-04-20 08:01:12 +00001439 FreeReg = Reg;
1440 if (FreeReg < inactiveCounts.size())
1441 FreeRegInactiveCount = inactiveCounts[FreeReg];
1442 else
1443 FreeRegInactiveCount = 0;
1444 break;
1445 }
1446 }
1447
1448 // If there are no free regs, or if this reg has the max inactive count,
1449 // return this register.
David Greene7cfd3362009-11-19 15:55:49 +00001450 if (FreeReg == 0 || FreeRegInactiveCount == MaxInactiveCount) {
1451 // Remember what register we picked so we can skip it next time.
1452 if (FreeReg != 0) recordRecentlyUsed(FreeReg);
Evan Cheng206d1852009-04-20 08:01:12 +00001453 return FreeReg;
David Greene7cfd3362009-11-19 15:55:49 +00001454 }
1455
Evan Cheng206d1852009-04-20 08:01:12 +00001456 // Continue scanning the registers, looking for the one with the highest
1457 // inactive count. Alkis found that this reduced register pressure very
1458 // slightly on X86 (in rev 1.94 of this file), though this should probably be
1459 // reevaluated now.
1460 for (; I != E; ++I) {
1461 unsigned Reg = *I;
1462 // Ignore "downgraded" registers.
1463 if (SkipDGRegs && DowngradedRegs.count(Reg))
1464 continue;
Jim Grosbach067a6482010-09-01 21:04:27 +00001465 // Skip reserved registers.
1466 if (reservedRegs_.test(Reg))
1467 continue;
Evan Cheng5b16cd22009-05-01 01:03:49 +00001468 if (isRegAvail(Reg) && Reg < inactiveCounts.size() &&
David Greenefeb5bfb2009-11-19 19:09:39 +00001469 FreeRegInactiveCount < inactiveCounts[Reg] && !isRecentlyUsed(Reg)) {
Evan Cheng206d1852009-04-20 08:01:12 +00001470 FreeReg = Reg;
1471 FreeRegInactiveCount = inactiveCounts[Reg];
1472 if (FreeRegInactiveCount == MaxInactiveCount)
1473 break; // We found the one with the max inactive count.
1474 }
1475 }
1476
David Greene7cfd3362009-11-19 15:55:49 +00001477 // Remember what register we picked so we can skip it next time.
1478 recordRecentlyUsed(FreeReg);
1479
Evan Cheng206d1852009-04-20 08:01:12 +00001480 return FreeReg;
Alkis Evlogimenos843b1602004-02-15 10:24:21 +00001481}
Alkis Evlogimenosf5eaf162004-02-06 18:08:18 +00001482
Chris Lattnercbb56252004-11-18 02:42:27 +00001483/// getFreePhysReg - return a free physical register for this virtual register
1484/// interval if we have one, otherwise return 0.
Bill Wendlinge23e00d2007-05-08 19:02:46 +00001485unsigned RALinScan::getFreePhysReg(LiveInterval *cur) {
Chris Lattnerfe424622008-02-26 22:08:41 +00001486 SmallVector<unsigned, 256> inactiveCounts;
Chris Lattnerf8355d92005-08-22 16:55:22 +00001487 unsigned MaxInactiveCount = 0;
Jim Grosbach662fb772010-09-01 21:48:06 +00001488
Evan Cheng841ee1a2008-09-18 22:38:47 +00001489 const TargetRegisterClass *RC = mri_->getRegClass(cur->reg);
Chris Lattnerb9805782005-08-23 22:27:31 +00001490 const TargetRegisterClass *RCLeader = RelatedRegClasses.getLeaderValue(RC);
Jim Grosbach662fb772010-09-01 21:48:06 +00001491
Alkis Evlogimenos84f5bcb2004-09-02 21:23:32 +00001492 for (IntervalPtrs::iterator i = inactive_.begin(), e = inactive_.end();
1493 i != e; ++i) {
Chris Lattnercbb56252004-11-18 02:42:27 +00001494 unsigned reg = i->first->reg;
Dan Gohman6f0d0242008-02-10 18:45:23 +00001495 assert(TargetRegisterInfo::isVirtualRegister(reg) &&
Chris Lattnerc8b9f332004-11-18 06:01:45 +00001496 "Can only allocate virtual registers!");
Chris Lattnerb9805782005-08-23 22:27:31 +00001497
Jim Grosbach662fb772010-09-01 21:48:06 +00001498 // If this is not in a related reg class to the register we're allocating,
Chris Lattnerb9805782005-08-23 22:27:31 +00001499 // don't check it.
Evan Cheng841ee1a2008-09-18 22:38:47 +00001500 const TargetRegisterClass *RegRC = mri_->getRegClass(reg);
Chris Lattnerb9805782005-08-23 22:27:31 +00001501 if (RelatedRegClasses.getLeaderValue(RegRC) == RCLeader) {
1502 reg = vrm_->getPhys(reg);
Chris Lattnerfe424622008-02-26 22:08:41 +00001503 if (inactiveCounts.size() <= reg)
1504 inactiveCounts.resize(reg+1);
Chris Lattnerb9805782005-08-23 22:27:31 +00001505 ++inactiveCounts[reg];
1506 MaxInactiveCount = std::max(MaxInactiveCount, inactiveCounts[reg]);
1507 }
Alkis Evlogimenos84f5bcb2004-09-02 21:23:32 +00001508 }
1509
Evan Cheng20b0abc2007-04-17 20:32:26 +00001510 // If copy coalescer has assigned a "preferred" register, check if it's
Dale Johannesen86b49f82008-09-24 01:07:17 +00001511 // available first.
Evan Cheng90f95f82009-06-14 20:22:55 +00001512 unsigned Preference = vrm_->getRegAllocPref(cur->reg);
1513 if (Preference) {
David Greene37277762010-01-05 01:25:20 +00001514 DEBUG(dbgs() << "(preferred: " << tri_->getName(Preference) << ") ");
Jim Grosbach662fb772010-09-01 21:48:06 +00001515 if (isRegAvail(Preference) &&
Evan Cheng90f95f82009-06-14 20:22:55 +00001516 RC->contains(Preference))
1517 return Preference;
Anton Korobeynikov4aefd6b2008-02-20 12:07:57 +00001518 }
Evan Cheng20b0abc2007-04-17 20:32:26 +00001519
Evan Cheng206d1852009-04-20 08:01:12 +00001520 if (!DowngradedRegs.empty()) {
Evan Cheng358dec52009-06-15 08:28:29 +00001521 unsigned FreeReg = getFreePhysReg(cur, RC, MaxInactiveCount, inactiveCounts,
Evan Cheng206d1852009-04-20 08:01:12 +00001522 true);
1523 if (FreeReg)
1524 return FreeReg;
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +00001525 }
Evan Cheng358dec52009-06-15 08:28:29 +00001526 return getFreePhysReg(cur, RC, MaxInactiveCount, inactiveCounts, false);
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +00001527}
1528
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +00001529FunctionPass* llvm::createLinearScanRegisterAllocator() {
Bill Wendlinge23e00d2007-05-08 19:02:46 +00001530 return new RALinScan();
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +00001531}