Alkis Evlogimenos | ff0cbe1 | 2003-11-20 03:32:25 +0000 | [diff] [blame] | 1 | //===-- RegAllocLinearScan.cpp - Linear Scan register allocator -----------===// |
| 2 | // |
| 3 | // The LLVM Compiler Infrastructure |
| 4 | // |
Chris Lattner | 4ee451d | 2007-12-29 20:36:04 +0000 | [diff] [blame^] | 5 | // This file is distributed under the University of Illinois Open Source |
| 6 | // License. See LICENSE.TXT for details. |
Alkis Evlogimenos | ff0cbe1 | 2003-11-20 03:32:25 +0000 | [diff] [blame] | 7 | // |
| 8 | //===----------------------------------------------------------------------===// |
| 9 | // |
| 10 | // This file implements a linear scan register allocator. |
| 11 | // |
| 12 | //===----------------------------------------------------------------------===// |
Alkis Evlogimenos | 0d6c5b6 | 2004-02-24 08:58:30 +0000 | [diff] [blame] | 13 | |
Alkis Evlogimenos | ff0cbe1 | 2003-11-20 03:32:25 +0000 | [diff] [blame] | 14 | #define DEBUG_TYPE "regalloc" |
Chris Lattner | 3c3fe46 | 2005-09-21 04:19:09 +0000 | [diff] [blame] | 15 | #include "llvm/CodeGen/LiveIntervalAnalysis.h" |
Chris Lattner | b980578 | 2005-08-23 22:27:31 +0000 | [diff] [blame] | 16 | #include "PhysRegTracker.h" |
| 17 | #include "VirtRegMap.h" |
Alkis Evlogimenos | ff0cbe1 | 2003-11-20 03:32:25 +0000 | [diff] [blame] | 18 | #include "llvm/Function.h" |
Alkis Evlogimenos | ff0cbe1 | 2003-11-20 03:32:25 +0000 | [diff] [blame] | 19 | #include "llvm/CodeGen/MachineFunctionPass.h" |
| 20 | #include "llvm/CodeGen/MachineInstr.h" |
Evan Cheng | 22f07ff | 2007-12-11 02:09:15 +0000 | [diff] [blame] | 21 | #include "llvm/CodeGen/MachineLoopInfo.h" |
Alkis Evlogimenos | ff0cbe1 | 2003-11-20 03:32:25 +0000 | [diff] [blame] | 22 | #include "llvm/CodeGen/Passes.h" |
Jim Laskey | eb577ba | 2006-08-02 12:30:23 +0000 | [diff] [blame] | 23 | #include "llvm/CodeGen/RegAllocRegistry.h" |
David Greene | 2c17c4d | 2007-09-06 16:18:45 +0000 | [diff] [blame] | 24 | #include "llvm/CodeGen/RegisterCoalescer.h" |
Alkis Evlogimenos | ff0cbe1 | 2003-11-20 03:32:25 +0000 | [diff] [blame] | 25 | #include "llvm/CodeGen/SSARegMap.h" |
| 26 | #include "llvm/Target/MRegisterInfo.h" |
Alkis Evlogimenos | ff0cbe1 | 2003-11-20 03:32:25 +0000 | [diff] [blame] | 27 | #include "llvm/Target/TargetMachine.h" |
Evan Cheng | c92da38 | 2007-11-03 07:20:12 +0000 | [diff] [blame] | 28 | #include "llvm/Target/TargetInstrInfo.h" |
Chris Lattner | b980578 | 2005-08-23 22:27:31 +0000 | [diff] [blame] | 29 | #include "llvm/ADT/EquivalenceClasses.h" |
Reid Spencer | 551ccae | 2004-09-01 22:55:40 +0000 | [diff] [blame] | 30 | #include "llvm/ADT/Statistic.h" |
| 31 | #include "llvm/ADT/STLExtras.h" |
Chris Lattner | b980578 | 2005-08-23 22:27:31 +0000 | [diff] [blame] | 32 | #include "llvm/Support/Debug.h" |
Chris Lattner | a4f0b3a | 2006-08-27 12:54:02 +0000 | [diff] [blame] | 33 | #include "llvm/Support/Compiler.h" |
Alkis Evlogimenos | 843b160 | 2004-02-15 10:24:21 +0000 | [diff] [blame] | 34 | #include <algorithm> |
Alkis Evlogimenos | 26f5a69 | 2004-05-30 07:24:39 +0000 | [diff] [blame] | 35 | #include <set> |
Alkis Evlogimenos | 53eb373 | 2004-07-22 08:14:44 +0000 | [diff] [blame] | 36 | #include <queue> |
Duraid Madina | 3005961 | 2005-12-28 04:55:42 +0000 | [diff] [blame] | 37 | #include <memory> |
Jeff Cohen | 97af751 | 2006-12-02 02:22:01 +0000 | [diff] [blame] | 38 | #include <cmath> |
Alkis Evlogimenos | ff0cbe1 | 2003-11-20 03:32:25 +0000 | [diff] [blame] | 39 | using namespace llvm; |
| 40 | |
Chris Lattner | cd3245a | 2006-12-19 22:41:21 +0000 | [diff] [blame] | 41 | STATISTIC(NumIters , "Number of iterations performed"); |
| 42 | STATISTIC(NumBacktracks, "Number of times we had to backtrack"); |
Evan Cheng | c92da38 | 2007-11-03 07:20:12 +0000 | [diff] [blame] | 43 | STATISTIC(NumCoalesce, "Number of copies coalesced"); |
Chris Lattner | cd3245a | 2006-12-19 22:41:21 +0000 | [diff] [blame] | 44 | |
| 45 | static RegisterRegAlloc |
| 46 | linearscanRegAlloc("linearscan", " linear scan register allocator", |
| 47 | createLinearScanRegisterAllocator); |
| 48 | |
Alkis Evlogimenos | ff0cbe1 | 2003-11-20 03:32:25 +0000 | [diff] [blame] | 49 | namespace { |
Bill Wendling | e23e00d | 2007-05-08 19:02:46 +0000 | [diff] [blame] | 50 | struct VISIBILITY_HIDDEN RALinScan : public MachineFunctionPass { |
Devang Patel | 1997473 | 2007-05-03 01:11:54 +0000 | [diff] [blame] | 51 | static char ID; |
Bill Wendling | e23e00d | 2007-05-08 19:02:46 +0000 | [diff] [blame] | 52 | RALinScan() : MachineFunctionPass((intptr_t)&ID) {} |
Devang Patel | 794fd75 | 2007-05-01 21:15:47 +0000 | [diff] [blame] | 53 | |
Chris Lattner | cbb5625 | 2004-11-18 02:42:27 +0000 | [diff] [blame] | 54 | typedef std::pair<LiveInterval*, LiveInterval::iterator> IntervalPtr; |
| 55 | typedef std::vector<IntervalPtr> IntervalPtrs; |
| 56 | private: |
Chris Lattner | b980578 | 2005-08-23 22:27:31 +0000 | [diff] [blame] | 57 | /// RelatedRegClasses - This structure is built the first time a function is |
| 58 | /// compiled, and keeps track of which register classes have registers that |
| 59 | /// belong to multiple classes or have aliases that are in other classes. |
| 60 | EquivalenceClasses<const TargetRegisterClass*> RelatedRegClasses; |
| 61 | std::map<unsigned, const TargetRegisterClass*> OneClassForEachPhysReg; |
| 62 | |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 63 | MachineFunction* mf_; |
| 64 | const TargetMachine* tm_; |
| 65 | const MRegisterInfo* mri_; |
Evan Cheng | c92da38 | 2007-11-03 07:20:12 +0000 | [diff] [blame] | 66 | const TargetInstrInfo* tii_; |
| 67 | SSARegMap *regmap_; |
| 68 | BitVector allocatableRegs_; |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 69 | LiveIntervals* li_; |
Evan Cheng | 22f07ff | 2007-12-11 02:09:15 +0000 | [diff] [blame] | 70 | const MachineLoopInfo *loopInfo; |
Chris Lattner | cbb5625 | 2004-11-18 02:42:27 +0000 | [diff] [blame] | 71 | |
| 72 | /// handled_ - Intervals are added to the handled_ set in the order of their |
| 73 | /// start value. This is uses for backtracking. |
| 74 | std::vector<LiveInterval*> handled_; |
| 75 | |
| 76 | /// fixed_ - Intervals that correspond to machine registers. |
| 77 | /// |
| 78 | IntervalPtrs fixed_; |
| 79 | |
| 80 | /// active_ - Intervals that are currently being processed, and which have a |
| 81 | /// live range active for the current point. |
| 82 | IntervalPtrs active_; |
| 83 | |
| 84 | /// inactive_ - Intervals that are currently being processed, but which have |
| 85 | /// a hold at the current point. |
| 86 | IntervalPtrs inactive_; |
| 87 | |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 88 | typedef std::priority_queue<LiveInterval*, |
Chris Lattner | cbb5625 | 2004-11-18 02:42:27 +0000 | [diff] [blame] | 89 | std::vector<LiveInterval*>, |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 90 | greater_ptr<LiveInterval> > IntervalHeap; |
| 91 | IntervalHeap unhandled_; |
| 92 | std::auto_ptr<PhysRegTracker> prt_; |
| 93 | std::auto_ptr<VirtRegMap> vrm_; |
| 94 | std::auto_ptr<Spiller> spiller_; |
Alkis Evlogimenos | ff0cbe1 | 2003-11-20 03:32:25 +0000 | [diff] [blame] | 95 | |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 96 | public: |
| 97 | virtual const char* getPassName() const { |
| 98 | return "Linear Scan Register Allocator"; |
| 99 | } |
| 100 | |
| 101 | virtual void getAnalysisUsage(AnalysisUsage &AU) const { |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 102 | AU.addRequired<LiveIntervals>(); |
David Greene | 2c17c4d | 2007-09-06 16:18:45 +0000 | [diff] [blame] | 103 | // Make sure PassManager knows which analyses to make available |
| 104 | // to coalescing and which analyses coalescing invalidates. |
| 105 | AU.addRequiredTransitive<RegisterCoalescer>(); |
Evan Cheng | 22f07ff | 2007-12-11 02:09:15 +0000 | [diff] [blame] | 106 | AU.addRequired<MachineLoopInfo>(); |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 107 | MachineFunctionPass::getAnalysisUsage(AU); |
| 108 | } |
| 109 | |
| 110 | /// runOnMachineFunction - register allocate the whole function |
| 111 | bool runOnMachineFunction(MachineFunction&); |
| 112 | |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 113 | private: |
| 114 | /// linearScan - the linear scan algorithm |
| 115 | void linearScan(); |
| 116 | |
Chris Lattner | cbb5625 | 2004-11-18 02:42:27 +0000 | [diff] [blame] | 117 | /// initIntervalSets - initialize the interval sets. |
| 118 | /// |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 119 | void initIntervalSets(); |
| 120 | |
Chris Lattner | cbb5625 | 2004-11-18 02:42:27 +0000 | [diff] [blame] | 121 | /// processActiveIntervals - expire old intervals and move non-overlapping |
| 122 | /// ones to the inactive list. |
| 123 | void processActiveIntervals(unsigned CurPoint); |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 124 | |
Chris Lattner | cbb5625 | 2004-11-18 02:42:27 +0000 | [diff] [blame] | 125 | /// processInactiveIntervals - expire old intervals and move overlapping |
| 126 | /// ones to the active list. |
| 127 | void processInactiveIntervals(unsigned CurPoint); |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 128 | |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 129 | /// assignRegOrStackSlotAtInterval - assign a register if one |
| 130 | /// is available, or spill. |
| 131 | void assignRegOrStackSlotAtInterval(LiveInterval* cur); |
| 132 | |
Evan Cheng | c92da38 | 2007-11-03 07:20:12 +0000 | [diff] [blame] | 133 | /// attemptTrivialCoalescing - If a simple interval is defined by a copy, |
| 134 | /// try allocate the definition the same register as the source register |
| 135 | /// if the register is not defined during live time of the interval. This |
| 136 | /// eliminate a copy. This is used to coalesce copies which were not |
| 137 | /// coalesced away before allocation either due to dest and src being in |
| 138 | /// different register classes or because the coalescer was overly |
| 139 | /// conservative. |
| 140 | unsigned attemptTrivialCoalescing(LiveInterval &cur, unsigned Reg); |
| 141 | |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 142 | /// |
| 143 | /// register handling helpers |
| 144 | /// |
| 145 | |
Chris Lattner | cbb5625 | 2004-11-18 02:42:27 +0000 | [diff] [blame] | 146 | /// getFreePhysReg - return a free physical register for this virtual |
| 147 | /// register interval if we have one, otherwise return 0. |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 148 | unsigned getFreePhysReg(LiveInterval* cur); |
| 149 | |
| 150 | /// assignVirt2StackSlot - assigns this virtual register to a |
| 151 | /// stack slot. returns the stack slot |
| 152 | int assignVirt2StackSlot(unsigned virtReg); |
| 153 | |
Chris Lattner | b980578 | 2005-08-23 22:27:31 +0000 | [diff] [blame] | 154 | void ComputeRelatedRegClasses(); |
| 155 | |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 156 | template <typename ItTy> |
| 157 | void printIntervals(const char* const str, ItTy i, ItTy e) const { |
Bill Wendling | 54fcc7f | 2006-11-17 00:50:36 +0000 | [diff] [blame] | 158 | if (str) DOUT << str << " intervals:\n"; |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 159 | for (; i != e; ++i) { |
Bill Wendling | 54fcc7f | 2006-11-17 00:50:36 +0000 | [diff] [blame] | 160 | DOUT << "\t" << *i->first << " -> "; |
Chris Lattner | cbb5625 | 2004-11-18 02:42:27 +0000 | [diff] [blame] | 161 | unsigned reg = i->first->reg; |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 162 | if (MRegisterInfo::isVirtualRegister(reg)) { |
| 163 | reg = vrm_->getPhys(reg); |
Alkis Evlogimenos | ff0cbe1 | 2003-11-20 03:32:25 +0000 | [diff] [blame] | 164 | } |
Bill Wendling | 54fcc7f | 2006-11-17 00:50:36 +0000 | [diff] [blame] | 165 | DOUT << mri_->getName(reg) << '\n'; |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 166 | } |
| 167 | } |
| 168 | }; |
Bill Wendling | e23e00d | 2007-05-08 19:02:46 +0000 | [diff] [blame] | 169 | char RALinScan::ID = 0; |
Alkis Evlogimenos | ff0cbe1 | 2003-11-20 03:32:25 +0000 | [diff] [blame] | 170 | } |
| 171 | |
Bill Wendling | e23e00d | 2007-05-08 19:02:46 +0000 | [diff] [blame] | 172 | void RALinScan::ComputeRelatedRegClasses() { |
Chris Lattner | b980578 | 2005-08-23 22:27:31 +0000 | [diff] [blame] | 173 | const MRegisterInfo &MRI = *mri_; |
| 174 | |
| 175 | // First pass, add all reg classes to the union, and determine at least one |
| 176 | // reg class that each register is in. |
| 177 | bool HasAliases = false; |
| 178 | for (MRegisterInfo::regclass_iterator RCI = MRI.regclass_begin(), |
| 179 | E = MRI.regclass_end(); RCI != E; ++RCI) { |
| 180 | RelatedRegClasses.insert(*RCI); |
| 181 | for (TargetRegisterClass::iterator I = (*RCI)->begin(), E = (*RCI)->end(); |
| 182 | I != E; ++I) { |
| 183 | HasAliases = HasAliases || *MRI.getAliasSet(*I) != 0; |
| 184 | |
| 185 | const TargetRegisterClass *&PRC = OneClassForEachPhysReg[*I]; |
| 186 | if (PRC) { |
| 187 | // Already processed this register. Just make sure we know that |
| 188 | // multiple register classes share a register. |
| 189 | RelatedRegClasses.unionSets(PRC, *RCI); |
| 190 | } else { |
| 191 | PRC = *RCI; |
| 192 | } |
| 193 | } |
| 194 | } |
| 195 | |
| 196 | // Second pass, now that we know conservatively what register classes each reg |
| 197 | // belongs to, add info about aliases. We don't need to do this for targets |
| 198 | // without register aliases. |
| 199 | if (HasAliases) |
| 200 | for (std::map<unsigned, const TargetRegisterClass*>::iterator |
| 201 | I = OneClassForEachPhysReg.begin(), E = OneClassForEachPhysReg.end(); |
| 202 | I != E; ++I) |
| 203 | for (const unsigned *AS = MRI.getAliasSet(I->first); *AS; ++AS) |
| 204 | RelatedRegClasses.unionSets(I->second, OneClassForEachPhysReg[*AS]); |
| 205 | } |
| 206 | |
Evan Cheng | c92da38 | 2007-11-03 07:20:12 +0000 | [diff] [blame] | 207 | /// attemptTrivialCoalescing - If a simple interval is defined by a copy, |
| 208 | /// try allocate the definition the same register as the source register |
| 209 | /// if the register is not defined during live time of the interval. This |
| 210 | /// eliminate a copy. This is used to coalesce copies which were not |
| 211 | /// coalesced away before allocation either due to dest and src being in |
| 212 | /// different register classes or because the coalescer was overly |
| 213 | /// conservative. |
| 214 | unsigned RALinScan::attemptTrivialCoalescing(LiveInterval &cur, unsigned Reg) { |
Evan Cheng | 9aeaf75 | 2007-11-04 08:32:21 +0000 | [diff] [blame] | 215 | if ((cur.preference && cur.preference == Reg) || !cur.containsOneValue()) |
Evan Cheng | c92da38 | 2007-11-03 07:20:12 +0000 | [diff] [blame] | 216 | return Reg; |
| 217 | |
| 218 | VNInfo *vni = cur.getValNumInfo(0); |
| 219 | if (!vni->def || vni->def == ~1U || vni->def == ~0U) |
| 220 | return Reg; |
| 221 | MachineInstr *CopyMI = li_->getInstructionFromIndex(vni->def); |
| 222 | unsigned SrcReg, DstReg; |
| 223 | if (!CopyMI || !tii_->isMoveInstr(*CopyMI, SrcReg, DstReg)) |
| 224 | return Reg; |
| 225 | if (MRegisterInfo::isVirtualRegister(SrcReg)) |
| 226 | if (!vrm_->isAssignedReg(SrcReg)) |
| 227 | return Reg; |
| 228 | else |
| 229 | SrcReg = vrm_->getPhys(SrcReg); |
| 230 | if (Reg == SrcReg) |
| 231 | return Reg; |
| 232 | |
| 233 | const TargetRegisterClass *RC = regmap_->getRegClass(cur.reg); |
| 234 | if (!RC->contains(SrcReg)) |
| 235 | return Reg; |
| 236 | |
| 237 | // Try to coalesce. |
| 238 | if (!li_->conflictsWithPhysRegDef(cur, *vrm_, SrcReg)) { |
Bill Wendling | 5b8318a | 2007-11-15 02:06:30 +0000 | [diff] [blame] | 239 | DOUT << "Coalescing: " << cur << " -> " << mri_->getName(SrcReg) << '\n'; |
Evan Cheng | c92da38 | 2007-11-03 07:20:12 +0000 | [diff] [blame] | 240 | vrm_->clearVirt(cur.reg); |
| 241 | vrm_->assignVirt2Phys(cur.reg, SrcReg); |
| 242 | ++NumCoalesce; |
| 243 | return SrcReg; |
| 244 | } |
| 245 | |
| 246 | return Reg; |
| 247 | } |
| 248 | |
Bill Wendling | e23e00d | 2007-05-08 19:02:46 +0000 | [diff] [blame] | 249 | bool RALinScan::runOnMachineFunction(MachineFunction &fn) { |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 250 | mf_ = &fn; |
| 251 | tm_ = &fn.getTarget(); |
| 252 | mri_ = tm_->getRegisterInfo(); |
Evan Cheng | c92da38 | 2007-11-03 07:20:12 +0000 | [diff] [blame] | 253 | tii_ = tm_->getInstrInfo(); |
| 254 | regmap_ = mf_->getSSARegMap(); |
| 255 | allocatableRegs_ = mri_->getAllocatableSet(fn); |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 256 | li_ = &getAnalysis<LiveIntervals>(); |
Evan Cheng | 22f07ff | 2007-12-11 02:09:15 +0000 | [diff] [blame] | 257 | loopInfo = &getAnalysis<MachineLoopInfo>(); |
Chris Lattner | f348e3a | 2004-11-18 04:33:31 +0000 | [diff] [blame] | 258 | |
David Greene | 2c17c4d | 2007-09-06 16:18:45 +0000 | [diff] [blame] | 259 | // We don't run the coalescer here because we have no reason to |
| 260 | // interact with it. If the coalescer requires interaction, it |
| 261 | // won't do anything. If it doesn't require interaction, we assume |
| 262 | // it was run as a separate pass. |
| 263 | |
Chris Lattner | b980578 | 2005-08-23 22:27:31 +0000 | [diff] [blame] | 264 | // If this is the first function compiled, compute the related reg classes. |
| 265 | if (RelatedRegClasses.empty()) |
| 266 | ComputeRelatedRegClasses(); |
| 267 | |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 268 | if (!prt_.get()) prt_.reset(new PhysRegTracker(*mri_)); |
| 269 | vrm_.reset(new VirtRegMap(*mf_)); |
| 270 | if (!spiller_.get()) spiller_.reset(createSpiller()); |
Alkis Evlogimenos | 169cfd0 | 2003-12-21 05:43:40 +0000 | [diff] [blame] | 271 | |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 272 | initIntervalSets(); |
Alkis Evlogimenos | ff0cbe1 | 2003-11-20 03:32:25 +0000 | [diff] [blame] | 273 | |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 274 | linearScan(); |
Alkis Evlogimenos | 0d6c5b6 | 2004-02-24 08:58:30 +0000 | [diff] [blame] | 275 | |
Chris Lattner | b0f31bf | 2005-01-23 22:45:13 +0000 | [diff] [blame] | 276 | // Rewrite spill code and update the PhysRegsUsed set. |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 277 | spiller_->runOnMachineFunction(*mf_, *vrm_); |
Chris Lattner | 510a3ea | 2004-09-30 02:02:33 +0000 | [diff] [blame] | 278 | vrm_.reset(); // Free the VirtRegMap |
Chris Lattner | cbb5625 | 2004-11-18 02:42:27 +0000 | [diff] [blame] | 279 | |
Chris Lattner | cbb5625 | 2004-11-18 02:42:27 +0000 | [diff] [blame] | 280 | while (!unhandled_.empty()) unhandled_.pop(); |
| 281 | fixed_.clear(); |
| 282 | active_.clear(); |
| 283 | inactive_.clear(); |
| 284 | handled_.clear(); |
| 285 | |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 286 | return true; |
Alkis Evlogimenos | 0d6c5b6 | 2004-02-24 08:58:30 +0000 | [diff] [blame] | 287 | } |
| 288 | |
Chris Lattner | c8b9f33 | 2004-11-18 06:01:45 +0000 | [diff] [blame] | 289 | /// initIntervalSets - initialize the interval sets. |
| 290 | /// |
Bill Wendling | e23e00d | 2007-05-08 19:02:46 +0000 | [diff] [blame] | 291 | void RALinScan::initIntervalSets() |
Chris Lattner | c8b9f33 | 2004-11-18 06:01:45 +0000 | [diff] [blame] | 292 | { |
| 293 | assert(unhandled_.empty() && fixed_.empty() && |
| 294 | active_.empty() && inactive_.empty() && |
| 295 | "interval sets should be empty on initialization"); |
| 296 | |
| 297 | for (LiveIntervals::iterator i = li_->begin(), e = li_->end(); i != e; ++i) { |
Chris Lattner | b0f31bf | 2005-01-23 22:45:13 +0000 | [diff] [blame] | 298 | if (MRegisterInfo::isPhysicalRegister(i->second.reg)) { |
Evan Cheng | 6c087e5 | 2007-04-25 22:13:27 +0000 | [diff] [blame] | 299 | mf_->setPhysRegUsed(i->second.reg); |
Chris Lattner | c8b9f33 | 2004-11-18 06:01:45 +0000 | [diff] [blame] | 300 | fixed_.push_back(std::make_pair(&i->second, i->second.begin())); |
Chris Lattner | b0f31bf | 2005-01-23 22:45:13 +0000 | [diff] [blame] | 301 | } else |
Chris Lattner | c8b9f33 | 2004-11-18 06:01:45 +0000 | [diff] [blame] | 302 | unhandled_.push(&i->second); |
| 303 | } |
| 304 | } |
| 305 | |
Bill Wendling | e23e00d | 2007-05-08 19:02:46 +0000 | [diff] [blame] | 306 | void RALinScan::linearScan() |
Alkis Evlogimenos | 0d6c5b6 | 2004-02-24 08:58:30 +0000 | [diff] [blame] | 307 | { |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 308 | // linear scan algorithm |
Bill Wendling | 54fcc7f | 2006-11-17 00:50:36 +0000 | [diff] [blame] | 309 | DOUT << "********** LINEAR SCAN **********\n"; |
| 310 | DOUT << "********** Function: " << mf_->getFunction()->getName() << '\n'; |
Alkis Evlogimenos | ff0cbe1 | 2003-11-20 03:32:25 +0000 | [diff] [blame] | 311 | |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 312 | DEBUG(printIntervals("fixed", fixed_.begin(), fixed_.end())); |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 313 | |
| 314 | while (!unhandled_.empty()) { |
| 315 | // pick the interval with the earliest start point |
| 316 | LiveInterval* cur = unhandled_.top(); |
| 317 | unhandled_.pop(); |
Evan Cheng | 11923cc | 2007-10-16 21:09:14 +0000 | [diff] [blame] | 318 | ++NumIters; |
Bill Wendling | 54fcc7f | 2006-11-17 00:50:36 +0000 | [diff] [blame] | 319 | DOUT << "\n*** CURRENT ***: " << *cur << '\n'; |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 320 | |
Chris Lattner | cbb5625 | 2004-11-18 02:42:27 +0000 | [diff] [blame] | 321 | processActiveIntervals(cur->beginNumber()); |
| 322 | processInactiveIntervals(cur->beginNumber()); |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 323 | |
Chris Lattner | c8b9f33 | 2004-11-18 06:01:45 +0000 | [diff] [blame] | 324 | assert(MRegisterInfo::isVirtualRegister(cur->reg) && |
| 325 | "Can only allocate virtual registers!"); |
Misha Brukman | edf128a | 2005-04-21 22:36:52 +0000 | [diff] [blame] | 326 | |
Chris Lattner | c8b9f33 | 2004-11-18 06:01:45 +0000 | [diff] [blame] | 327 | // Allocating a virtual register. try to find a free |
| 328 | // physical register or spill an interval (possibly this one) in order to |
| 329 | // assign it one. |
| 330 | assignRegOrStackSlotAtInterval(cur); |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 331 | |
Alkis Evlogimenos | 39a0d5c | 2004-02-20 06:15:40 +0000 | [diff] [blame] | 332 | DEBUG(printIntervals("active", active_.begin(), active_.end())); |
| 333 | DEBUG(printIntervals("inactive", inactive_.begin(), inactive_.end())); |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 334 | } |
Alkis Evlogimenos | 7d629b5 | 2004-01-07 09:20:58 +0000 | [diff] [blame] | 335 | |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 336 | // expire any remaining active intervals |
Evan Cheng | 11923cc | 2007-10-16 21:09:14 +0000 | [diff] [blame] | 337 | while (!active_.empty()) { |
| 338 | IntervalPtr &IP = active_.back(); |
| 339 | unsigned reg = IP.first->reg; |
| 340 | DOUT << "\tinterval " << *IP.first << " expired\n"; |
Chris Lattner | c8b9f33 | 2004-11-18 06:01:45 +0000 | [diff] [blame] | 341 | assert(MRegisterInfo::isVirtualRegister(reg) && |
| 342 | "Can only allocate virtual registers!"); |
| 343 | reg = vrm_->getPhys(reg); |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 344 | prt_->delRegUse(reg); |
Evan Cheng | 11923cc | 2007-10-16 21:09:14 +0000 | [diff] [blame] | 345 | active_.pop_back(); |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 346 | } |
Alkis Evlogimenos | 7d629b5 | 2004-01-07 09:20:58 +0000 | [diff] [blame] | 347 | |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 348 | // expire any remaining inactive intervals |
Evan Cheng | 11923cc | 2007-10-16 21:09:14 +0000 | [diff] [blame] | 349 | DEBUG(for (IntervalPtrs::reverse_iterator |
Bill Wendling | 87075ca | 2007-11-15 00:40:48 +0000 | [diff] [blame] | 350 | i = inactive_.rbegin(); i != inactive_.rend(); ++i) |
Evan Cheng | 11923cc | 2007-10-16 21:09:14 +0000 | [diff] [blame] | 351 | DOUT << "\tinterval " << *i->first << " expired\n"); |
| 352 | inactive_.clear(); |
Alkis Evlogimenos | b7be115 | 2004-01-13 20:42:08 +0000 | [diff] [blame] | 353 | |
Evan Cheng | 81a0382 | 2007-11-17 00:40:40 +0000 | [diff] [blame] | 354 | // Add live-ins to every BB except for entry. Also perform trivial coalescing. |
Evan Cheng | 3f4b80e | 2007-10-17 02:12:22 +0000 | [diff] [blame] | 355 | MachineFunction::iterator EntryMBB = mf_->begin(); |
Evan Cheng | a5bfc97 | 2007-10-17 06:53:44 +0000 | [diff] [blame] | 356 | SmallVector<MachineBasicBlock*, 8> LiveInMBBs; |
Evan Cheng | 3f4b80e | 2007-10-17 02:12:22 +0000 | [diff] [blame] | 357 | for (LiveIntervals::iterator i = li_->begin(), e = li_->end(); i != e; ++i) { |
Evan Cheng | c92da38 | 2007-11-03 07:20:12 +0000 | [diff] [blame] | 358 | LiveInterval &cur = i->second; |
Evan Cheng | 3f4b80e | 2007-10-17 02:12:22 +0000 | [diff] [blame] | 359 | unsigned Reg = 0; |
Evan Cheng | 81a0382 | 2007-11-17 00:40:40 +0000 | [diff] [blame] | 360 | bool isPhys = MRegisterInfo::isPhysicalRegister(cur.reg); |
| 361 | if (isPhys) |
Evan Cheng | 3f4b80e | 2007-10-17 02:12:22 +0000 | [diff] [blame] | 362 | Reg = i->second.reg; |
| 363 | else if (vrm_->isAssignedReg(cur.reg)) |
Evan Cheng | c92da38 | 2007-11-03 07:20:12 +0000 | [diff] [blame] | 364 | Reg = attemptTrivialCoalescing(cur, vrm_->getPhys(cur.reg)); |
Evan Cheng | 3f4b80e | 2007-10-17 02:12:22 +0000 | [diff] [blame] | 365 | if (!Reg) |
| 366 | continue; |
Evan Cheng | 81a0382 | 2007-11-17 00:40:40 +0000 | [diff] [blame] | 367 | // Ignore splited live intervals. |
| 368 | if (!isPhys && vrm_->getPreSplitReg(cur.reg)) |
| 369 | continue; |
Evan Cheng | 3f4b80e | 2007-10-17 02:12:22 +0000 | [diff] [blame] | 370 | for (LiveInterval::Ranges::const_iterator I = cur.begin(), E = cur.end(); |
| 371 | I != E; ++I) { |
| 372 | const LiveRange &LR = *I; |
Evan Cheng | 3f4b80e | 2007-10-17 02:12:22 +0000 | [diff] [blame] | 373 | if (li_->findLiveInMBBs(LR, LiveInMBBs)) { |
| 374 | for (unsigned i = 0, e = LiveInMBBs.size(); i != e; ++i) |
| 375 | if (LiveInMBBs[i] != EntryMBB) |
| 376 | LiveInMBBs[i]->addLiveIn(Reg); |
Evan Cheng | a5bfc97 | 2007-10-17 06:53:44 +0000 | [diff] [blame] | 377 | LiveInMBBs.clear(); |
Evan Cheng | 9fc508f | 2007-02-16 09:05:02 +0000 | [diff] [blame] | 378 | } |
| 379 | } |
| 380 | } |
| 381 | |
Bill Wendling | 54fcc7f | 2006-11-17 00:50:36 +0000 | [diff] [blame] | 382 | DOUT << *vrm_; |
Alkis Evlogimenos | ff0cbe1 | 2003-11-20 03:32:25 +0000 | [diff] [blame] | 383 | } |
| 384 | |
Chris Lattner | cbb5625 | 2004-11-18 02:42:27 +0000 | [diff] [blame] | 385 | /// processActiveIntervals - expire old intervals and move non-overlapping ones |
| 386 | /// to the inactive list. |
Bill Wendling | e23e00d | 2007-05-08 19:02:46 +0000 | [diff] [blame] | 387 | void RALinScan::processActiveIntervals(unsigned CurPoint) |
Alkis Evlogimenos | ff0cbe1 | 2003-11-20 03:32:25 +0000 | [diff] [blame] | 388 | { |
Bill Wendling | 54fcc7f | 2006-11-17 00:50:36 +0000 | [diff] [blame] | 389 | DOUT << "\tprocessing active intervals:\n"; |
Chris Lattner | 23b71c1 | 2004-11-18 01:29:39 +0000 | [diff] [blame] | 390 | |
Chris Lattner | cbb5625 | 2004-11-18 02:42:27 +0000 | [diff] [blame] | 391 | for (unsigned i = 0, e = active_.size(); i != e; ++i) { |
| 392 | LiveInterval *Interval = active_[i].first; |
| 393 | LiveInterval::iterator IntervalPos = active_[i].second; |
| 394 | unsigned reg = Interval->reg; |
Alkis Evlogimenos | ed54373 | 2004-09-01 22:52:29 +0000 | [diff] [blame] | 395 | |
Chris Lattner | cbb5625 | 2004-11-18 02:42:27 +0000 | [diff] [blame] | 396 | IntervalPos = Interval->advanceTo(IntervalPos, CurPoint); |
| 397 | |
| 398 | if (IntervalPos == Interval->end()) { // Remove expired intervals. |
Bill Wendling | 54fcc7f | 2006-11-17 00:50:36 +0000 | [diff] [blame] | 399 | DOUT << "\t\tinterval " << *Interval << " expired\n"; |
Chris Lattner | c8b9f33 | 2004-11-18 06:01:45 +0000 | [diff] [blame] | 400 | assert(MRegisterInfo::isVirtualRegister(reg) && |
| 401 | "Can only allocate virtual registers!"); |
| 402 | reg = vrm_->getPhys(reg); |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 403 | prt_->delRegUse(reg); |
Chris Lattner | cbb5625 | 2004-11-18 02:42:27 +0000 | [diff] [blame] | 404 | |
| 405 | // Pop off the end of the list. |
| 406 | active_[i] = active_.back(); |
| 407 | active_.pop_back(); |
| 408 | --i; --e; |
Misha Brukman | edf128a | 2005-04-21 22:36:52 +0000 | [diff] [blame] | 409 | |
Chris Lattner | cbb5625 | 2004-11-18 02:42:27 +0000 | [diff] [blame] | 410 | } else if (IntervalPos->start > CurPoint) { |
| 411 | // Move inactive intervals to inactive list. |
Bill Wendling | 54fcc7f | 2006-11-17 00:50:36 +0000 | [diff] [blame] | 412 | DOUT << "\t\tinterval " << *Interval << " inactive\n"; |
Chris Lattner | c8b9f33 | 2004-11-18 06:01:45 +0000 | [diff] [blame] | 413 | assert(MRegisterInfo::isVirtualRegister(reg) && |
| 414 | "Can only allocate virtual registers!"); |
| 415 | reg = vrm_->getPhys(reg); |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 416 | prt_->delRegUse(reg); |
Chris Lattner | cbb5625 | 2004-11-18 02:42:27 +0000 | [diff] [blame] | 417 | // add to inactive. |
| 418 | inactive_.push_back(std::make_pair(Interval, IntervalPos)); |
| 419 | |
| 420 | // Pop off the end of the list. |
| 421 | active_[i] = active_.back(); |
| 422 | active_.pop_back(); |
| 423 | --i; --e; |
| 424 | } else { |
| 425 | // Otherwise, just update the iterator position. |
| 426 | active_[i].second = IntervalPos; |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 427 | } |
| 428 | } |
Alkis Evlogimenos | ff0cbe1 | 2003-11-20 03:32:25 +0000 | [diff] [blame] | 429 | } |
| 430 | |
Chris Lattner | cbb5625 | 2004-11-18 02:42:27 +0000 | [diff] [blame] | 431 | /// processInactiveIntervals - expire old intervals and move overlapping |
| 432 | /// ones to the active list. |
Bill Wendling | e23e00d | 2007-05-08 19:02:46 +0000 | [diff] [blame] | 433 | void RALinScan::processInactiveIntervals(unsigned CurPoint) |
Alkis Evlogimenos | ff0cbe1 | 2003-11-20 03:32:25 +0000 | [diff] [blame] | 434 | { |
Bill Wendling | 54fcc7f | 2006-11-17 00:50:36 +0000 | [diff] [blame] | 435 | DOUT << "\tprocessing inactive intervals:\n"; |
Chris Lattner | 365b95f | 2004-11-18 04:13:02 +0000 | [diff] [blame] | 436 | |
Chris Lattner | cbb5625 | 2004-11-18 02:42:27 +0000 | [diff] [blame] | 437 | for (unsigned i = 0, e = inactive_.size(); i != e; ++i) { |
| 438 | LiveInterval *Interval = inactive_[i].first; |
| 439 | LiveInterval::iterator IntervalPos = inactive_[i].second; |
| 440 | unsigned reg = Interval->reg; |
Chris Lattner | 23b71c1 | 2004-11-18 01:29:39 +0000 | [diff] [blame] | 441 | |
Chris Lattner | cbb5625 | 2004-11-18 02:42:27 +0000 | [diff] [blame] | 442 | IntervalPos = Interval->advanceTo(IntervalPos, CurPoint); |
Misha Brukman | edf128a | 2005-04-21 22:36:52 +0000 | [diff] [blame] | 443 | |
Chris Lattner | cbb5625 | 2004-11-18 02:42:27 +0000 | [diff] [blame] | 444 | if (IntervalPos == Interval->end()) { // remove expired intervals. |
Bill Wendling | 54fcc7f | 2006-11-17 00:50:36 +0000 | [diff] [blame] | 445 | DOUT << "\t\tinterval " << *Interval << " expired\n"; |
Alkis Evlogimenos | 169cfd0 | 2003-12-21 05:43:40 +0000 | [diff] [blame] | 446 | |
Chris Lattner | cbb5625 | 2004-11-18 02:42:27 +0000 | [diff] [blame] | 447 | // Pop off the end of the list. |
| 448 | inactive_[i] = inactive_.back(); |
| 449 | inactive_.pop_back(); |
| 450 | --i; --e; |
| 451 | } else if (IntervalPos->start <= CurPoint) { |
| 452 | // move re-activated intervals in active list |
Bill Wendling | 54fcc7f | 2006-11-17 00:50:36 +0000 | [diff] [blame] | 453 | DOUT << "\t\tinterval " << *Interval << " active\n"; |
Chris Lattner | c8b9f33 | 2004-11-18 06:01:45 +0000 | [diff] [blame] | 454 | assert(MRegisterInfo::isVirtualRegister(reg) && |
| 455 | "Can only allocate virtual registers!"); |
| 456 | reg = vrm_->getPhys(reg); |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 457 | prt_->addRegUse(reg); |
| 458 | // add to active |
Chris Lattner | cbb5625 | 2004-11-18 02:42:27 +0000 | [diff] [blame] | 459 | active_.push_back(std::make_pair(Interval, IntervalPos)); |
| 460 | |
| 461 | // Pop off the end of the list. |
| 462 | inactive_[i] = inactive_.back(); |
| 463 | inactive_.pop_back(); |
| 464 | --i; --e; |
| 465 | } else { |
| 466 | // Otherwise, just update the iterator position. |
| 467 | inactive_[i].second = IntervalPos; |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 468 | } |
| 469 | } |
Alkis Evlogimenos | 169cfd0 | 2003-12-21 05:43:40 +0000 | [diff] [blame] | 470 | } |
| 471 | |
Chris Lattner | cbb5625 | 2004-11-18 02:42:27 +0000 | [diff] [blame] | 472 | /// updateSpillWeights - updates the spill weights of the specifed physical |
| 473 | /// register and its weight. |
Misha Brukman | edf128a | 2005-04-21 22:36:52 +0000 | [diff] [blame] | 474 | static void updateSpillWeights(std::vector<float> &Weights, |
Chris Lattner | c8b9f33 | 2004-11-18 06:01:45 +0000 | [diff] [blame] | 475 | unsigned reg, float weight, |
| 476 | const MRegisterInfo *MRI) { |
| 477 | Weights[reg] += weight; |
| 478 | for (const unsigned* as = MRI->getAliasSet(reg); *as; ++as) |
| 479 | Weights[*as] += weight; |
Alkis Evlogimenos | ff0cbe1 | 2003-11-20 03:32:25 +0000 | [diff] [blame] | 480 | } |
| 481 | |
Bill Wendling | e23e00d | 2007-05-08 19:02:46 +0000 | [diff] [blame] | 482 | static |
| 483 | RALinScan::IntervalPtrs::iterator |
| 484 | FindIntervalInVector(RALinScan::IntervalPtrs &IP, LiveInterval *LI) { |
| 485 | for (RALinScan::IntervalPtrs::iterator I = IP.begin(), E = IP.end(); |
| 486 | I != E; ++I) |
Chris Lattner | cbb5625 | 2004-11-18 02:42:27 +0000 | [diff] [blame] | 487 | if (I->first == LI) return I; |
| 488 | return IP.end(); |
| 489 | } |
| 490 | |
Bill Wendling | e23e00d | 2007-05-08 19:02:46 +0000 | [diff] [blame] | 491 | static void RevertVectorIteratorsTo(RALinScan::IntervalPtrs &V, unsigned Point){ |
Chris Lattner | 19828d4 | 2004-11-18 03:49:30 +0000 | [diff] [blame] | 492 | for (unsigned i = 0, e = V.size(); i != e; ++i) { |
Bill Wendling | e23e00d | 2007-05-08 19:02:46 +0000 | [diff] [blame] | 493 | RALinScan::IntervalPtr &IP = V[i]; |
Chris Lattner | 19828d4 | 2004-11-18 03:49:30 +0000 | [diff] [blame] | 494 | LiveInterval::iterator I = std::upper_bound(IP.first->begin(), |
| 495 | IP.second, Point); |
| 496 | if (I != IP.first->begin()) --I; |
| 497 | IP.second = I; |
| 498 | } |
| 499 | } |
Chris Lattner | cbb5625 | 2004-11-18 02:42:27 +0000 | [diff] [blame] | 500 | |
Chris Lattner | cbb5625 | 2004-11-18 02:42:27 +0000 | [diff] [blame] | 501 | /// assignRegOrStackSlotAtInterval - assign a register if one is available, or |
| 502 | /// spill. |
Bill Wendling | e23e00d | 2007-05-08 19:02:46 +0000 | [diff] [blame] | 503 | void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) |
Alkis Evlogimenos | ff0cbe1 | 2003-11-20 03:32:25 +0000 | [diff] [blame] | 504 | { |
Bill Wendling | 54fcc7f | 2006-11-17 00:50:36 +0000 | [diff] [blame] | 505 | DOUT << "\tallocating current interval: "; |
Alkis Evlogimenos | ff0cbe1 | 2003-11-20 03:32:25 +0000 | [diff] [blame] | 506 | |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 507 | PhysRegTracker backupPrt = *prt_; |
Alkis Evlogimenos | 169cfd0 | 2003-12-21 05:43:40 +0000 | [diff] [blame] | 508 | |
Chris Lattner | a6c1750 | 2005-08-22 20:20:42 +0000 | [diff] [blame] | 509 | std::vector<std::pair<unsigned, float> > SpillWeightsToAdd; |
Chris Lattner | 365b95f | 2004-11-18 04:13:02 +0000 | [diff] [blame] | 510 | unsigned StartPosition = cur->beginNumber(); |
Evan Cheng | c92da38 | 2007-11-03 07:20:12 +0000 | [diff] [blame] | 511 | const TargetRegisterClass *RC = regmap_->getRegClass(cur->reg); |
Chris Lattner | b980578 | 2005-08-23 22:27:31 +0000 | [diff] [blame] | 512 | const TargetRegisterClass *RCLeader = RelatedRegClasses.getLeaderValue(RC); |
Evan Cheng | c92da38 | 2007-11-03 07:20:12 +0000 | [diff] [blame] | 513 | |
| 514 | // If this live interval is defined by a move instruction and its source is |
| 515 | // assigned a physical register that is compatible with the target register |
| 516 | // class, then we should try to assign it the same register. |
| 517 | // This can happen when the move is from a larger register class to a smaller |
| 518 | // one, e.g. X86::mov32to32_. These move instructions are not coalescable. |
| 519 | if (!cur->preference && cur->containsOneValue()) { |
| 520 | VNInfo *vni = cur->getValNumInfo(0); |
| 521 | if (vni->def && vni->def != ~1U && vni->def != ~0U) { |
| 522 | MachineInstr *CopyMI = li_->getInstructionFromIndex(vni->def); |
| 523 | unsigned SrcReg, DstReg; |
| 524 | if (tii_->isMoveInstr(*CopyMI, SrcReg, DstReg)) { |
| 525 | unsigned Reg = 0; |
| 526 | if (MRegisterInfo::isPhysicalRegister(SrcReg)) |
| 527 | Reg = SrcReg; |
| 528 | else if (vrm_->isAssignedReg(SrcReg)) |
| 529 | Reg = vrm_->getPhys(SrcReg); |
| 530 | if (Reg && allocatableRegs_[Reg] && RC->contains(Reg)) |
| 531 | cur->preference = Reg; |
| 532 | } |
| 533 | } |
| 534 | } |
| 535 | |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 536 | // for every interval in inactive we overlap with, mark the |
Chris Lattner | a6c1750 | 2005-08-22 20:20:42 +0000 | [diff] [blame] | 537 | // register as not free and update spill weights. |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 538 | for (IntervalPtrs::const_iterator i = inactive_.begin(), |
| 539 | e = inactive_.end(); i != e; ++i) { |
Chris Lattner | b980578 | 2005-08-23 22:27:31 +0000 | [diff] [blame] | 540 | unsigned Reg = i->first->reg; |
| 541 | assert(MRegisterInfo::isVirtualRegister(Reg) && |
| 542 | "Can only allocate virtual registers!"); |
Evan Cheng | c92da38 | 2007-11-03 07:20:12 +0000 | [diff] [blame] | 543 | const TargetRegisterClass *RegRC = regmap_->getRegClass(Reg); |
Chris Lattner | b980578 | 2005-08-23 22:27:31 +0000 | [diff] [blame] | 544 | // If this is not in a related reg class to the register we're allocating, |
| 545 | // don't check it. |
| 546 | if (RelatedRegClasses.getLeaderValue(RegRC) == RCLeader && |
| 547 | cur->overlapsFrom(*i->first, i->second-1)) { |
| 548 | Reg = vrm_->getPhys(Reg); |
| 549 | prt_->addRegUse(Reg); |
| 550 | SpillWeightsToAdd.push_back(std::make_pair(Reg, i->first->weight)); |
Alkis Evlogimenos | ff0cbe1 | 2003-11-20 03:32:25 +0000 | [diff] [blame] | 551 | } |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 552 | } |
Chris Lattner | a411cbc | 2005-08-22 20:59:30 +0000 | [diff] [blame] | 553 | |
| 554 | // Speculatively check to see if we can get a register right now. If not, |
| 555 | // we know we won't be able to by adding more constraints. If so, we can |
| 556 | // check to see if it is valid. Doing an exhaustive search of the fixed_ list |
| 557 | // is very bad (it contains all callee clobbered registers for any functions |
| 558 | // with a call), so we want to avoid doing that if possible. |
| 559 | unsigned physReg = getFreePhysReg(cur); |
| 560 | if (physReg) { |
| 561 | // We got a register. However, if it's in the fixed_ list, we might |
Chris Lattner | e836ad6 | 2005-08-30 21:03:36 +0000 | [diff] [blame] | 562 | // conflict with it. Check to see if we conflict with it or any of its |
| 563 | // aliases. |
Evan Cheng | c92da38 | 2007-11-03 07:20:12 +0000 | [diff] [blame] | 564 | SmallSet<unsigned, 8> RegAliases; |
Chris Lattner | e836ad6 | 2005-08-30 21:03:36 +0000 | [diff] [blame] | 565 | for (const unsigned *AS = mri_->getAliasSet(physReg); *AS; ++AS) |
| 566 | RegAliases.insert(*AS); |
| 567 | |
Chris Lattner | a411cbc | 2005-08-22 20:59:30 +0000 | [diff] [blame] | 568 | bool ConflictsWithFixed = false; |
| 569 | for (unsigned i = 0, e = fixed_.size(); i != e; ++i) { |
Jim Laskey | e719d9f | 2006-10-24 14:35:25 +0000 | [diff] [blame] | 570 | IntervalPtr &IP = fixed_[i]; |
| 571 | if (physReg == IP.first->reg || RegAliases.count(IP.first->reg)) { |
Chris Lattner | a411cbc | 2005-08-22 20:59:30 +0000 | [diff] [blame] | 572 | // Okay, this reg is on the fixed list. Check to see if we actually |
| 573 | // conflict. |
Chris Lattner | a411cbc | 2005-08-22 20:59:30 +0000 | [diff] [blame] | 574 | LiveInterval *I = IP.first; |
| 575 | if (I->endNumber() > StartPosition) { |
| 576 | LiveInterval::iterator II = I->advanceTo(IP.second, StartPosition); |
| 577 | IP.second = II; |
| 578 | if (II != I->begin() && II->start > StartPosition) |
| 579 | --II; |
Chris Lattner | e836ad6 | 2005-08-30 21:03:36 +0000 | [diff] [blame] | 580 | if (cur->overlapsFrom(*I, II)) { |
Chris Lattner | a411cbc | 2005-08-22 20:59:30 +0000 | [diff] [blame] | 581 | ConflictsWithFixed = true; |
Chris Lattner | e836ad6 | 2005-08-30 21:03:36 +0000 | [diff] [blame] | 582 | break; |
| 583 | } |
Chris Lattner | a411cbc | 2005-08-22 20:59:30 +0000 | [diff] [blame] | 584 | } |
Chris Lattner | f348e3a | 2004-11-18 04:33:31 +0000 | [diff] [blame] | 585 | } |
Alkis Evlogimenos | 169cfd0 | 2003-12-21 05:43:40 +0000 | [diff] [blame] | 586 | } |
Chris Lattner | a411cbc | 2005-08-22 20:59:30 +0000 | [diff] [blame] | 587 | |
| 588 | // Okay, the register picked by our speculative getFreePhysReg call turned |
| 589 | // out to be in use. Actually add all of the conflicting fixed registers to |
| 590 | // prt so we can do an accurate query. |
| 591 | if (ConflictsWithFixed) { |
Chris Lattner | b980578 | 2005-08-23 22:27:31 +0000 | [diff] [blame] | 592 | // For every interval in fixed we overlap with, mark the register as not |
| 593 | // free and update spill weights. |
Chris Lattner | a411cbc | 2005-08-22 20:59:30 +0000 | [diff] [blame] | 594 | for (unsigned i = 0, e = fixed_.size(); i != e; ++i) { |
| 595 | IntervalPtr &IP = fixed_[i]; |
| 596 | LiveInterval *I = IP.first; |
Chris Lattner | b980578 | 2005-08-23 22:27:31 +0000 | [diff] [blame] | 597 | |
| 598 | const TargetRegisterClass *RegRC = OneClassForEachPhysReg[I->reg]; |
| 599 | if (RelatedRegClasses.getLeaderValue(RegRC) == RCLeader && |
| 600 | I->endNumber() > StartPosition) { |
Chris Lattner | a411cbc | 2005-08-22 20:59:30 +0000 | [diff] [blame] | 601 | LiveInterval::iterator II = I->advanceTo(IP.second, StartPosition); |
| 602 | IP.second = II; |
| 603 | if (II != I->begin() && II->start > StartPosition) |
| 604 | --II; |
| 605 | if (cur->overlapsFrom(*I, II)) { |
| 606 | unsigned reg = I->reg; |
| 607 | prt_->addRegUse(reg); |
| 608 | SpillWeightsToAdd.push_back(std::make_pair(reg, I->weight)); |
| 609 | } |
| 610 | } |
| 611 | } |
Alkis Evlogimenos | 169cfd0 | 2003-12-21 05:43:40 +0000 | [diff] [blame] | 612 | |
Chris Lattner | a411cbc | 2005-08-22 20:59:30 +0000 | [diff] [blame] | 613 | // Using the newly updated prt_ object, which includes conflicts in the |
| 614 | // future, see if there are any registers available. |
| 615 | physReg = getFreePhysReg(cur); |
| 616 | } |
| 617 | } |
| 618 | |
Chris Lattner | a6c1750 | 2005-08-22 20:20:42 +0000 | [diff] [blame] | 619 | // Restore the physical register tracker, removing information about the |
| 620 | // future. |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 621 | *prt_ = backupPrt; |
Chris Lattner | a6c1750 | 2005-08-22 20:20:42 +0000 | [diff] [blame] | 622 | |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 623 | // if we find a free register, we are done: assign this virtual to |
| 624 | // the free physical register and add this interval to the active |
| 625 | // list. |
| 626 | if (physReg) { |
Bill Wendling | 54fcc7f | 2006-11-17 00:50:36 +0000 | [diff] [blame] | 627 | DOUT << mri_->getName(physReg) << '\n'; |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 628 | vrm_->assignVirt2Phys(cur->reg, physReg); |
| 629 | prt_->addRegUse(physReg); |
Chris Lattner | cbb5625 | 2004-11-18 02:42:27 +0000 | [diff] [blame] | 630 | active_.push_back(std::make_pair(cur, cur->begin())); |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 631 | handled_.push_back(cur); |
| 632 | return; |
| 633 | } |
Bill Wendling | 54fcc7f | 2006-11-17 00:50:36 +0000 | [diff] [blame] | 634 | DOUT << "no free registers\n"; |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 635 | |
Chris Lattner | a6c1750 | 2005-08-22 20:20:42 +0000 | [diff] [blame] | 636 | // Compile the spill weights into an array that is better for scanning. |
| 637 | std::vector<float> SpillWeights(mri_->getNumRegs(), 0.0); |
| 638 | for (std::vector<std::pair<unsigned, float> >::iterator |
| 639 | I = SpillWeightsToAdd.begin(), E = SpillWeightsToAdd.end(); I != E; ++I) |
| 640 | updateSpillWeights(SpillWeights, I->first, I->second, mri_); |
| 641 | |
| 642 | // for each interval in active, update spill weights. |
| 643 | for (IntervalPtrs::const_iterator i = active_.begin(), e = active_.end(); |
| 644 | i != e; ++i) { |
| 645 | unsigned reg = i->first->reg; |
| 646 | assert(MRegisterInfo::isVirtualRegister(reg) && |
| 647 | "Can only allocate virtual registers!"); |
| 648 | reg = vrm_->getPhys(reg); |
| 649 | updateSpillWeights(SpillWeights, reg, i->first->weight, mri_); |
| 650 | } |
| 651 | |
Bill Wendling | 54fcc7f | 2006-11-17 00:50:36 +0000 | [diff] [blame] | 652 | DOUT << "\tassigning stack slot at interval "<< *cur << ":\n"; |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 653 | |
Chris Lattner | c8e2c55 | 2006-03-25 23:00:56 +0000 | [diff] [blame] | 654 | // Find a register to spill. |
Jim Laskey | 7902c75 | 2006-11-07 12:25:45 +0000 | [diff] [blame] | 655 | float minWeight = HUGE_VALF; |
Evan Cheng | 20b0abc | 2007-04-17 20:32:26 +0000 | [diff] [blame] | 656 | unsigned minReg = cur->preference; // Try the preferred register first. |
| 657 | |
| 658 | if (!minReg || SpillWeights[minReg] == HUGE_VALF) |
| 659 | for (TargetRegisterClass::iterator i = RC->allocation_order_begin(*mf_), |
| 660 | e = RC->allocation_order_end(*mf_); i != e; ++i) { |
| 661 | unsigned reg = *i; |
| 662 | if (minWeight > SpillWeights[reg]) { |
| 663 | minWeight = SpillWeights[reg]; |
| 664 | minReg = reg; |
| 665 | } |
Alkis Evlogimenos | 3bf564a | 2003-12-23 18:00:33 +0000 | [diff] [blame] | 666 | } |
Chris Lattner | c8e2c55 | 2006-03-25 23:00:56 +0000 | [diff] [blame] | 667 | |
| 668 | // If we didn't find a register that is spillable, try aliases? |
Evan Cheng | 3b6d56c | 2006-05-12 19:07:46 +0000 | [diff] [blame] | 669 | if (!minReg) { |
| 670 | for (TargetRegisterClass::iterator i = RC->allocation_order_begin(*mf_), |
| 671 | e = RC->allocation_order_end(*mf_); i != e; ++i) { |
| 672 | unsigned reg = *i; |
| 673 | // No need to worry about if the alias register size < regsize of RC. |
| 674 | // We are going to spill all registers that alias it anyway. |
| 675 | for (const unsigned* as = mri_->getAliasSet(reg); *as; ++as) { |
| 676 | if (minWeight > SpillWeights[*as]) { |
| 677 | minWeight = SpillWeights[*as]; |
| 678 | minReg = *as; |
| 679 | } |
| 680 | } |
| 681 | } |
| 682 | |
| 683 | // All registers must have inf weight. Just grab one! |
| 684 | if (!minReg) |
| 685 | minReg = *RC->allocation_order_begin(*mf_); |
| 686 | } |
Chris Lattner | c8e2c55 | 2006-03-25 23:00:56 +0000 | [diff] [blame] | 687 | |
Bill Wendling | 54fcc7f | 2006-11-17 00:50:36 +0000 | [diff] [blame] | 688 | DOUT << "\t\tregister with min weight: " |
| 689 | << mri_->getName(minReg) << " (" << minWeight << ")\n"; |
Alkis Evlogimenos | 3bf564a | 2003-12-23 18:00:33 +0000 | [diff] [blame] | 690 | |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 691 | // if the current has the minimum weight, we need to spill it and |
| 692 | // add any added intervals back to unhandled, and restart |
| 693 | // linearscan. |
Jim Laskey | 7902c75 | 2006-11-07 12:25:45 +0000 | [diff] [blame] | 694 | if (cur->weight != HUGE_VALF && cur->weight <= minWeight) { |
Bill Wendling | 54fcc7f | 2006-11-17 00:50:36 +0000 | [diff] [blame] | 695 | DOUT << "\t\t\tspilling(c): " << *cur << '\n'; |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 696 | std::vector<LiveInterval*> added = |
Evan Cheng | 81a0382 | 2007-11-17 00:40:40 +0000 | [diff] [blame] | 697 | li_->addIntervalsForSpills(*cur, loopInfo, *vrm_); |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 698 | if (added.empty()) |
| 699 | return; // Early exit if all spills were folded. |
Alkis Evlogimenos | f5eaf16 | 2004-02-06 18:08:18 +0000 | [diff] [blame] | 700 | |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 701 | // Merge added with unhandled. Note that we know that |
| 702 | // addIntervalsForSpills returns intervals sorted by their starting |
| 703 | // point. |
Alkis Evlogimenos | 53eb373 | 2004-07-22 08:14:44 +0000 | [diff] [blame] | 704 | for (unsigned i = 0, e = added.size(); i != e; ++i) |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 705 | unhandled_.push(added[i]); |
| 706 | return; |
| 707 | } |
| 708 | |
Chris Lattner | 19828d4 | 2004-11-18 03:49:30 +0000 | [diff] [blame] | 709 | ++NumBacktracks; |
| 710 | |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 711 | // push the current interval back to unhandled since we are going |
| 712 | // to re-run at least this iteration. Since we didn't modify it it |
| 713 | // should go back right in the front of the list |
| 714 | unhandled_.push(cur); |
| 715 | |
| 716 | // otherwise we spill all intervals aliasing the register with |
| 717 | // minimum weight, rollback to the interval with the earliest |
| 718 | // start point and let the linear scan algorithm run again |
| 719 | std::vector<LiveInterval*> added; |
| 720 | assert(MRegisterInfo::isPhysicalRegister(minReg) && |
| 721 | "did not choose a register to spill?"); |
Evan Cheng | 2638e1a | 2007-03-20 08:13:50 +0000 | [diff] [blame] | 722 | BitVector toSpill(mri_->getNumRegs()); |
Chris Lattner | 19828d4 | 2004-11-18 03:49:30 +0000 | [diff] [blame] | 723 | |
| 724 | // We are going to spill minReg and all its aliases. |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 725 | toSpill[minReg] = true; |
| 726 | for (const unsigned* as = mri_->getAliasSet(minReg); *as; ++as) |
| 727 | toSpill[*as] = true; |
| 728 | |
| 729 | // the earliest start of a spilled interval indicates up to where |
| 730 | // in handled we need to roll back |
Chris Lattner | 23b71c1 | 2004-11-18 01:29:39 +0000 | [diff] [blame] | 731 | unsigned earliestStart = cur->beginNumber(); |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 732 | |
| 733 | // set of spilled vregs (used later to rollback properly) |
Evan Cheng | c92da38 | 2007-11-03 07:20:12 +0000 | [diff] [blame] | 734 | SmallSet<unsigned, 32> spilled; |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 735 | |
Chris Lattner | 19828d4 | 2004-11-18 03:49:30 +0000 | [diff] [blame] | 736 | // spill live intervals of virtual regs mapped to the physical register we |
| 737 | // want to clear (and its aliases). We only spill those that overlap with the |
| 738 | // current interval as the rest do not affect its allocation. we also keep |
| 739 | // track of the earliest start of all spilled live intervals since this will |
| 740 | // mark our rollback point. |
| 741 | for (IntervalPtrs::iterator i = active_.begin(); i != active_.end(); ++i) { |
Chris Lattner | cbb5625 | 2004-11-18 02:42:27 +0000 | [diff] [blame] | 742 | unsigned reg = i->first->reg; |
Chris Lattner | c8b9f33 | 2004-11-18 06:01:45 +0000 | [diff] [blame] | 743 | if (//MRegisterInfo::isVirtualRegister(reg) && |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 744 | toSpill[vrm_->getPhys(reg)] && |
Chris Lattner | 19828d4 | 2004-11-18 03:49:30 +0000 | [diff] [blame] | 745 | cur->overlapsFrom(*i->first, i->second)) { |
Bill Wendling | 54fcc7f | 2006-11-17 00:50:36 +0000 | [diff] [blame] | 746 | DOUT << "\t\t\tspilling(a): " << *i->first << '\n'; |
Chris Lattner | cbb5625 | 2004-11-18 02:42:27 +0000 | [diff] [blame] | 747 | earliestStart = std::min(earliestStart, i->first->beginNumber()); |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 748 | std::vector<LiveInterval*> newIs = |
Evan Cheng | 81a0382 | 2007-11-17 00:40:40 +0000 | [diff] [blame] | 749 | li_->addIntervalsForSpills(*i->first, loopInfo, *vrm_); |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 750 | std::copy(newIs.begin(), newIs.end(), std::back_inserter(added)); |
| 751 | spilled.insert(reg); |
| 752 | } |
| 753 | } |
Chris Lattner | 19828d4 | 2004-11-18 03:49:30 +0000 | [diff] [blame] | 754 | for (IntervalPtrs::iterator i = inactive_.begin(); i != inactive_.end(); ++i){ |
Chris Lattner | cbb5625 | 2004-11-18 02:42:27 +0000 | [diff] [blame] | 755 | unsigned reg = i->first->reg; |
Chris Lattner | c8b9f33 | 2004-11-18 06:01:45 +0000 | [diff] [blame] | 756 | if (//MRegisterInfo::isVirtualRegister(reg) && |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 757 | toSpill[vrm_->getPhys(reg)] && |
Chris Lattner | 19828d4 | 2004-11-18 03:49:30 +0000 | [diff] [blame] | 758 | cur->overlapsFrom(*i->first, i->second-1)) { |
Bill Wendling | 54fcc7f | 2006-11-17 00:50:36 +0000 | [diff] [blame] | 759 | DOUT << "\t\t\tspilling(i): " << *i->first << '\n'; |
Chris Lattner | cbb5625 | 2004-11-18 02:42:27 +0000 | [diff] [blame] | 760 | earliestStart = std::min(earliestStart, i->first->beginNumber()); |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 761 | std::vector<LiveInterval*> newIs = |
Evan Cheng | 81a0382 | 2007-11-17 00:40:40 +0000 | [diff] [blame] | 762 | li_->addIntervalsForSpills(*i->first, loopInfo, *vrm_); |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 763 | std::copy(newIs.begin(), newIs.end(), std::back_inserter(added)); |
| 764 | spilled.insert(reg); |
| 765 | } |
| 766 | } |
| 767 | |
Bill Wendling | 54fcc7f | 2006-11-17 00:50:36 +0000 | [diff] [blame] | 768 | DOUT << "\t\trolling back to: " << earliestStart << '\n'; |
Chris Lattner | cbb5625 | 2004-11-18 02:42:27 +0000 | [diff] [blame] | 769 | |
| 770 | // Scan handled in reverse order up to the earliest start of a |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 771 | // spilled live interval and undo each one, restoring the state of |
Chris Lattner | cbb5625 | 2004-11-18 02:42:27 +0000 | [diff] [blame] | 772 | // unhandled. |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 773 | while (!handled_.empty()) { |
| 774 | LiveInterval* i = handled_.back(); |
Chris Lattner | cbb5625 | 2004-11-18 02:42:27 +0000 | [diff] [blame] | 775 | // If this interval starts before t we are done. |
Chris Lattner | 23b71c1 | 2004-11-18 01:29:39 +0000 | [diff] [blame] | 776 | if (i->beginNumber() < earliestStart) |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 777 | break; |
Bill Wendling | 54fcc7f | 2006-11-17 00:50:36 +0000 | [diff] [blame] | 778 | DOUT << "\t\t\tundo changes for: " << *i << '\n'; |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 779 | handled_.pop_back(); |
Chris Lattner | cbb5625 | 2004-11-18 02:42:27 +0000 | [diff] [blame] | 780 | |
| 781 | // When undoing a live interval allocation we must know if it is active or |
| 782 | // inactive to properly update the PhysRegTracker and the VirtRegMap. |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 783 | IntervalPtrs::iterator it; |
Chris Lattner | cbb5625 | 2004-11-18 02:42:27 +0000 | [diff] [blame] | 784 | if ((it = FindIntervalInVector(active_, i)) != active_.end()) { |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 785 | active_.erase(it); |
Chris Lattner | ffab422 | 2006-02-23 06:44:17 +0000 | [diff] [blame] | 786 | assert(!MRegisterInfo::isPhysicalRegister(i->reg)); |
| 787 | if (!spilled.count(i->reg)) |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 788 | unhandled_.push(i); |
Chris Lattner | ffab422 | 2006-02-23 06:44:17 +0000 | [diff] [blame] | 789 | prt_->delRegUse(vrm_->getPhys(i->reg)); |
| 790 | vrm_->clearVirt(i->reg); |
Chris Lattner | cbb5625 | 2004-11-18 02:42:27 +0000 | [diff] [blame] | 791 | } else if ((it = FindIntervalInVector(inactive_, i)) != inactive_.end()) { |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 792 | inactive_.erase(it); |
Chris Lattner | ffab422 | 2006-02-23 06:44:17 +0000 | [diff] [blame] | 793 | assert(!MRegisterInfo::isPhysicalRegister(i->reg)); |
| 794 | if (!spilled.count(i->reg)) |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 795 | unhandled_.push(i); |
Chris Lattner | ffab422 | 2006-02-23 06:44:17 +0000 | [diff] [blame] | 796 | vrm_->clearVirt(i->reg); |
Chris Lattner | c8b9f33 | 2004-11-18 06:01:45 +0000 | [diff] [blame] | 797 | } else { |
| 798 | assert(MRegisterInfo::isVirtualRegister(i->reg) && |
| 799 | "Can only allocate virtual registers!"); |
| 800 | vrm_->clearVirt(i->reg); |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 801 | unhandled_.push(i); |
| 802 | } |
Evan Cheng | 9aeaf75 | 2007-11-04 08:32:21 +0000 | [diff] [blame] | 803 | |
| 804 | // It interval has a preference, it must be defined by a copy. Clear the |
| 805 | // preference now since the source interval allocation may have been undone |
| 806 | // as well. |
| 807 | i->preference = 0; |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 808 | } |
| 809 | |
Chris Lattner | 19828d4 | 2004-11-18 03:49:30 +0000 | [diff] [blame] | 810 | // Rewind the iterators in the active, inactive, and fixed lists back to the |
| 811 | // point we reverted to. |
| 812 | RevertVectorIteratorsTo(active_, earliestStart); |
| 813 | RevertVectorIteratorsTo(inactive_, earliestStart); |
| 814 | RevertVectorIteratorsTo(fixed_, earliestStart); |
| 815 | |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 816 | // scan the rest and undo each interval that expired after t and |
| 817 | // insert it in active (the next iteration of the algorithm will |
| 818 | // put it in inactive if required) |
Chris Lattner | cbb5625 | 2004-11-18 02:42:27 +0000 | [diff] [blame] | 819 | for (unsigned i = 0, e = handled_.size(); i != e; ++i) { |
| 820 | LiveInterval *HI = handled_[i]; |
| 821 | if (!HI->expiredAt(earliestStart) && |
| 822 | HI->expiredAt(cur->beginNumber())) { |
Bill Wendling | 54fcc7f | 2006-11-17 00:50:36 +0000 | [diff] [blame] | 823 | DOUT << "\t\t\tundo changes for: " << *HI << '\n'; |
Chris Lattner | cbb5625 | 2004-11-18 02:42:27 +0000 | [diff] [blame] | 824 | active_.push_back(std::make_pair(HI, HI->begin())); |
Chris Lattner | ffab422 | 2006-02-23 06:44:17 +0000 | [diff] [blame] | 825 | assert(!MRegisterInfo::isPhysicalRegister(HI->reg)); |
| 826 | prt_->addRegUse(vrm_->getPhys(HI->reg)); |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 827 | } |
| 828 | } |
| 829 | |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 830 | // merge added with unhandled |
| 831 | for (unsigned i = 0, e = added.size(); i != e; ++i) |
| 832 | unhandled_.push(added[i]); |
Alkis Evlogimenos | 843b160 | 2004-02-15 10:24:21 +0000 | [diff] [blame] | 833 | } |
Alkis Evlogimenos | f5eaf16 | 2004-02-06 18:08:18 +0000 | [diff] [blame] | 834 | |
Chris Lattner | cbb5625 | 2004-11-18 02:42:27 +0000 | [diff] [blame] | 835 | /// getFreePhysReg - return a free physical register for this virtual register |
| 836 | /// interval if we have one, otherwise return 0. |
Bill Wendling | e23e00d | 2007-05-08 19:02:46 +0000 | [diff] [blame] | 837 | unsigned RALinScan::getFreePhysReg(LiveInterval *cur) { |
Alkis Evlogimenos | 84f5bcb | 2004-09-02 21:23:32 +0000 | [diff] [blame] | 838 | std::vector<unsigned> inactiveCounts(mri_->getNumRegs(), 0); |
Chris Lattner | f8355d9 | 2005-08-22 16:55:22 +0000 | [diff] [blame] | 839 | unsigned MaxInactiveCount = 0; |
| 840 | |
Evan Cheng | c92da38 | 2007-11-03 07:20:12 +0000 | [diff] [blame] | 841 | const TargetRegisterClass *RC = regmap_->getRegClass(cur->reg); |
Chris Lattner | b980578 | 2005-08-23 22:27:31 +0000 | [diff] [blame] | 842 | const TargetRegisterClass *RCLeader = RelatedRegClasses.getLeaderValue(RC); |
| 843 | |
Alkis Evlogimenos | 84f5bcb | 2004-09-02 21:23:32 +0000 | [diff] [blame] | 844 | for (IntervalPtrs::iterator i = inactive_.begin(), e = inactive_.end(); |
| 845 | i != e; ++i) { |
Chris Lattner | cbb5625 | 2004-11-18 02:42:27 +0000 | [diff] [blame] | 846 | unsigned reg = i->first->reg; |
Chris Lattner | c8b9f33 | 2004-11-18 06:01:45 +0000 | [diff] [blame] | 847 | assert(MRegisterInfo::isVirtualRegister(reg) && |
| 848 | "Can only allocate virtual registers!"); |
Chris Lattner | b980578 | 2005-08-23 22:27:31 +0000 | [diff] [blame] | 849 | |
| 850 | // If this is not in a related reg class to the register we're allocating, |
| 851 | // don't check it. |
Evan Cheng | c92da38 | 2007-11-03 07:20:12 +0000 | [diff] [blame] | 852 | const TargetRegisterClass *RegRC = regmap_->getRegClass(reg); |
Chris Lattner | b980578 | 2005-08-23 22:27:31 +0000 | [diff] [blame] | 853 | if (RelatedRegClasses.getLeaderValue(RegRC) == RCLeader) { |
| 854 | reg = vrm_->getPhys(reg); |
| 855 | ++inactiveCounts[reg]; |
| 856 | MaxInactiveCount = std::max(MaxInactiveCount, inactiveCounts[reg]); |
| 857 | } |
Alkis Evlogimenos | 84f5bcb | 2004-09-02 21:23:32 +0000 | [diff] [blame] | 858 | } |
| 859 | |
Chris Lattner | f8355d9 | 2005-08-22 16:55:22 +0000 | [diff] [blame] | 860 | unsigned FreeReg = 0; |
| 861 | unsigned FreeRegInactiveCount = 0; |
Evan Cheng | 20b0abc | 2007-04-17 20:32:26 +0000 | [diff] [blame] | 862 | |
| 863 | // If copy coalescer has assigned a "preferred" register, check if it's |
| 864 | // available first. |
| 865 | if (cur->preference) |
| 866 | if (prt_->isRegAvail(cur->preference)) { |
| 867 | DOUT << "\t\tassigned the preferred register: " |
| 868 | << mri_->getName(cur->preference) << "\n"; |
| 869 | return cur->preference; |
| 870 | } else |
| 871 | DOUT << "\t\tunable to assign the preferred register: " |
| 872 | << mri_->getName(cur->preference) << "\n"; |
| 873 | |
Chris Lattner | f8355d9 | 2005-08-22 16:55:22 +0000 | [diff] [blame] | 874 | // Scan for the first available register. |
Evan Cheng | 92efbfc | 2007-04-25 07:18:20 +0000 | [diff] [blame] | 875 | TargetRegisterClass::iterator I = RC->allocation_order_begin(*mf_); |
| 876 | TargetRegisterClass::iterator E = RC->allocation_order_end(*mf_); |
Chris Lattner | f8355d9 | 2005-08-22 16:55:22 +0000 | [diff] [blame] | 877 | for (; I != E; ++I) |
| 878 | if (prt_->isRegAvail(*I)) { |
| 879 | FreeReg = *I; |
| 880 | FreeRegInactiveCount = inactiveCounts[FreeReg]; |
| 881 | break; |
| 882 | } |
| 883 | |
| 884 | // If there are no free regs, or if this reg has the max inactive count, |
| 885 | // return this register. |
| 886 | if (FreeReg == 0 || FreeRegInactiveCount == MaxInactiveCount) return FreeReg; |
| 887 | |
| 888 | // Continue scanning the registers, looking for the one with the highest |
| 889 | // inactive count. Alkis found that this reduced register pressure very |
| 890 | // slightly on X86 (in rev 1.94 of this file), though this should probably be |
| 891 | // reevaluated now. |
| 892 | for (; I != E; ++I) { |
| 893 | unsigned Reg = *I; |
| 894 | if (prt_->isRegAvail(Reg) && FreeRegInactiveCount < inactiveCounts[Reg]) { |
| 895 | FreeReg = Reg; |
| 896 | FreeRegInactiveCount = inactiveCounts[Reg]; |
| 897 | if (FreeRegInactiveCount == MaxInactiveCount) |
| 898 | break; // We found the one with the max inactive count. |
| 899 | } |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 900 | } |
Chris Lattner | f8355d9 | 2005-08-22 16:55:22 +0000 | [diff] [blame] | 901 | |
| 902 | return FreeReg; |
Alkis Evlogimenos | ff0cbe1 | 2003-11-20 03:32:25 +0000 | [diff] [blame] | 903 | } |
| 904 | |
Alkis Evlogimenos | ff0cbe1 | 2003-11-20 03:32:25 +0000 | [diff] [blame] | 905 | FunctionPass* llvm::createLinearScanRegisterAllocator() { |
Bill Wendling | e23e00d | 2007-05-08 19:02:46 +0000 | [diff] [blame] | 906 | return new RALinScan(); |
Alkis Evlogimenos | ff0cbe1 | 2003-11-20 03:32:25 +0000 | [diff] [blame] | 907 | } |