Jakob Stoklund Olesen | ccc9581 | 2012-01-11 22:28:30 +0000 | [diff] [blame] | 1 | //===-- RegAllocBasic.cpp - Basic Register Allocator ----------------------===// |
Andrew Trick | 14e8d71 | 2010-10-22 23:09:15 +0000 | [diff] [blame] | 2 | // |
| 3 | // The LLVM Compiler Infrastructure |
| 4 | // |
| 5 | // This file is distributed under the University of Illinois Open Source |
| 6 | // License. See LICENSE.TXT for details. |
| 7 | // |
| 8 | //===----------------------------------------------------------------------===// |
| 9 | // |
| 10 | // This file defines the RABasic function pass, which provides a minimal |
| 11 | // implementation of the basic register allocator. |
| 12 | // |
| 13 | //===----------------------------------------------------------------------===// |
| 14 | |
| 15 | #define DEBUG_TYPE "regalloc" |
Jakob Stoklund Olesen | 5f2316a | 2011-06-03 20:34:53 +0000 | [diff] [blame] | 16 | #include "RegAllocBase.h" |
Jakob Stoklund Olesen | cfafc54 | 2011-04-05 21:40:37 +0000 | [diff] [blame] | 17 | #include "LiveDebugVariables.h" |
Jakob Stoklund Olesen | 47dbf6c | 2011-03-10 01:51:42 +0000 | [diff] [blame] | 18 | #include "LiveRangeEdit.h" |
Andrew Trick | 14e8d71 | 2010-10-22 23:09:15 +0000 | [diff] [blame] | 19 | #include "RenderMachineFunction.h" |
| 20 | #include "Spiller.h" |
Andrew Trick | e141a49 | 2010-11-08 18:02:08 +0000 | [diff] [blame] | 21 | #include "VirtRegMap.h" |
Andrew Trick | 8a83d54 | 2010-11-11 17:46:29 +0000 | [diff] [blame] | 22 | #include "llvm/Analysis/AliasAnalysis.h" |
Andrew Trick | 14e8d71 | 2010-10-22 23:09:15 +0000 | [diff] [blame] | 23 | #include "llvm/Function.h" |
| 24 | #include "llvm/PassAnalysisSupport.h" |
| 25 | #include "llvm/CodeGen/CalcSpillWeights.h" |
Andrew Trick | e141a49 | 2010-11-08 18:02:08 +0000 | [diff] [blame] | 26 | #include "llvm/CodeGen/LiveIntervalAnalysis.h" |
Andrew Trick | 14e8d71 | 2010-10-22 23:09:15 +0000 | [diff] [blame] | 27 | #include "llvm/CodeGen/LiveStackAnalysis.h" |
| 28 | #include "llvm/CodeGen/MachineFunctionPass.h" |
| 29 | #include "llvm/CodeGen/MachineInstr.h" |
| 30 | #include "llvm/CodeGen/MachineLoopInfo.h" |
| 31 | #include "llvm/CodeGen/MachineRegisterInfo.h" |
| 32 | #include "llvm/CodeGen/Passes.h" |
| 33 | #include "llvm/CodeGen/RegAllocRegistry.h" |
Andrew Trick | 14e8d71 | 2010-10-22 23:09:15 +0000 | [diff] [blame] | 34 | #include "llvm/Target/TargetMachine.h" |
| 35 | #include "llvm/Target/TargetOptions.h" |
Andrew Trick | e16eecc | 2010-10-26 18:34:01 +0000 | [diff] [blame] | 36 | #include "llvm/Target/TargetRegisterInfo.h" |
Andrew Trick | e141a49 | 2010-11-08 18:02:08 +0000 | [diff] [blame] | 37 | #include "llvm/Support/Debug.h" |
Andrew Trick | e141a49 | 2010-11-08 18:02:08 +0000 | [diff] [blame] | 38 | #include "llvm/Support/raw_ostream.h" |
Andrew Trick | e16eecc | 2010-10-26 18:34:01 +0000 | [diff] [blame] | 39 | |
Jakob Stoklund Olesen | 953af2c | 2010-12-07 23:18:47 +0000 | [diff] [blame] | 40 | #include <cstdlib> |
Jakob Stoklund Olesen | 98d9648 | 2011-02-22 23:01:52 +0000 | [diff] [blame] | 41 | #include <queue> |
Andrew Trick | e16eecc | 2010-10-26 18:34:01 +0000 | [diff] [blame] | 42 | |
Andrew Trick | 14e8d71 | 2010-10-22 23:09:15 +0000 | [diff] [blame] | 43 | using namespace llvm; |
| 44 | |
| 45 | static RegisterRegAlloc basicRegAlloc("basic", "basic register allocator", |
| 46 | createBasicRegisterAllocator); |
| 47 | |
Benjamin Kramer | c62feda | 2010-11-25 16:42:51 +0000 | [diff] [blame] | 48 | namespace { |
Jakob Stoklund Olesen | 98d9648 | 2011-02-22 23:01:52 +0000 | [diff] [blame] | 49 | struct CompSpillWeight { |
| 50 | bool operator()(LiveInterval *A, LiveInterval *B) const { |
| 51 | return A->weight < B->weight; |
| 52 | } |
| 53 | }; |
| 54 | } |
| 55 | |
| 56 | namespace { |
Andrew Trick | 14e8d71 | 2010-10-22 23:09:15 +0000 | [diff] [blame] | 57 | /// RABasic provides a minimal implementation of the basic register allocation |
| 58 | /// algorithm. It prioritizes live virtual registers by spill weight and spills |
| 59 | /// whenever a register is unavailable. This is not practical in production but |
| 60 | /// provides a useful baseline both for measuring other allocators and comparing |
| 61 | /// the speed of the basic algorithm against other styles of allocators. |
| 62 | class RABasic : public MachineFunctionPass, public RegAllocBase |
| 63 | { |
| 64 | // context |
Andrew Trick | 18c57a8 | 2010-11-30 23:18:47 +0000 | [diff] [blame] | 65 | MachineFunction *MF; |
Andrew Trick | 14e8d71 | 2010-10-22 23:09:15 +0000 | [diff] [blame] | 66 | |
| 67 | // analyses |
Andrew Trick | 18c57a8 | 2010-11-30 23:18:47 +0000 | [diff] [blame] | 68 | LiveStacks *LS; |
| 69 | RenderMachineFunction *RMF; |
Andrew Trick | 14e8d71 | 2010-10-22 23:09:15 +0000 | [diff] [blame] | 70 | |
| 71 | // state |
Andrew Trick | 18c57a8 | 2010-11-30 23:18:47 +0000 | [diff] [blame] | 72 | std::auto_ptr<Spiller> SpillerInstance; |
Jakob Stoklund Olesen | 98d9648 | 2011-02-22 23:01:52 +0000 | [diff] [blame] | 73 | std::priority_queue<LiveInterval*, std::vector<LiveInterval*>, |
| 74 | CompSpillWeight> Queue; |
Jakob Stoklund Olesen | a94e635 | 2012-02-08 18:54:35 +0000 | [diff] [blame] | 75 | |
| 76 | // Scratch space. Allocated here to avoid repeated malloc calls in |
| 77 | // selectOrSplit(). |
| 78 | BitVector UsableRegs; |
| 79 | |
Andrew Trick | 14e8d71 | 2010-10-22 23:09:15 +0000 | [diff] [blame] | 80 | public: |
| 81 | RABasic(); |
| 82 | |
| 83 | /// Return the pass name. |
| 84 | virtual const char* getPassName() const { |
| 85 | return "Basic Register Allocator"; |
| 86 | } |
| 87 | |
| 88 | /// RABasic analysis usage. |
Andrew Trick | 18c57a8 | 2010-11-30 23:18:47 +0000 | [diff] [blame] | 89 | virtual void getAnalysisUsage(AnalysisUsage &AU) const; |
Andrew Trick | 14e8d71 | 2010-10-22 23:09:15 +0000 | [diff] [blame] | 90 | |
| 91 | virtual void releaseMemory(); |
| 92 | |
Andrew Trick | 18c57a8 | 2010-11-30 23:18:47 +0000 | [diff] [blame] | 93 | virtual Spiller &spiller() { return *SpillerInstance; } |
Andrew Trick | f4baeaf | 2010-11-10 19:18:47 +0000 | [diff] [blame] | 94 | |
Jakob Stoklund Olesen | d0bec3e | 2010-12-08 22:22:41 +0000 | [diff] [blame] | 95 | virtual float getPriority(LiveInterval *LI) { return LI->weight; } |
| 96 | |
Jakob Stoklund Olesen | 98d9648 | 2011-02-22 23:01:52 +0000 | [diff] [blame] | 97 | virtual void enqueue(LiveInterval *LI) { |
| 98 | Queue.push(LI); |
| 99 | } |
| 100 | |
| 101 | virtual LiveInterval *dequeue() { |
| 102 | if (Queue.empty()) |
| 103 | return 0; |
| 104 | LiveInterval *LI = Queue.top(); |
| 105 | Queue.pop(); |
| 106 | return LI; |
| 107 | } |
| 108 | |
Andrew Trick | 18c57a8 | 2010-11-30 23:18:47 +0000 | [diff] [blame] | 109 | virtual unsigned selectOrSplit(LiveInterval &VirtReg, |
| 110 | SmallVectorImpl<LiveInterval*> &SplitVRegs); |
Andrew Trick | 14e8d71 | 2010-10-22 23:09:15 +0000 | [diff] [blame] | 111 | |
| 112 | /// Perform register allocation. |
| 113 | virtual bool runOnMachineFunction(MachineFunction &mf); |
| 114 | |
Jakob Stoklund Olesen | a8bd9a6 | 2012-01-11 22:52:14 +0000 | [diff] [blame] | 115 | // Helper for spilling all live virtual registers currently unified under preg |
| 116 | // that interfere with the most recently queried lvr. Return true if spilling |
| 117 | // was successful, and append any new spilled/split intervals to splitLVRs. |
| 118 | bool spillInterferences(LiveInterval &VirtReg, unsigned PhysReg, |
| 119 | SmallVectorImpl<LiveInterval*> &SplitVRegs); |
| 120 | |
| 121 | void spillReg(LiveInterval &VirtReg, unsigned PhysReg, |
| 122 | SmallVectorImpl<LiveInterval*> &SplitVRegs); |
| 123 | |
Andrew Trick | 14e8d71 | 2010-10-22 23:09:15 +0000 | [diff] [blame] | 124 | static char ID; |
| 125 | }; |
| 126 | |
| 127 | char RABasic::ID = 0; |
| 128 | |
| 129 | } // end anonymous namespace |
| 130 | |
Andrew Trick | 14e8d71 | 2010-10-22 23:09:15 +0000 | [diff] [blame] | 131 | RABasic::RABasic(): MachineFunctionPass(ID) { |
Jakob Stoklund Olesen | cfafc54 | 2011-04-05 21:40:37 +0000 | [diff] [blame] | 132 | initializeLiveDebugVariablesPass(*PassRegistry::getPassRegistry()); |
Andrew Trick | 14e8d71 | 2010-10-22 23:09:15 +0000 | [diff] [blame] | 133 | initializeLiveIntervalsPass(*PassRegistry::getPassRegistry()); |
| 134 | initializeSlotIndexesPass(*PassRegistry::getPassRegistry()); |
Rafael Espindola | 5b22021 | 2011-06-26 22:34:10 +0000 | [diff] [blame] | 135 | initializeRegisterCoalescerPass(*PassRegistry::getPassRegistry()); |
Andrew Trick | 42b7a71 | 2012-01-17 06:55:03 +0000 | [diff] [blame] | 136 | initializeMachineSchedulerPass(*PassRegistry::getPassRegistry()); |
Andrew Trick | 14e8d71 | 2010-10-22 23:09:15 +0000 | [diff] [blame] | 137 | initializeCalculateSpillWeightsPass(*PassRegistry::getPassRegistry()); |
| 138 | initializeLiveStacksPass(*PassRegistry::getPassRegistry()); |
Jakob Stoklund Olesen | 964bc25 | 2010-11-03 20:39:26 +0000 | [diff] [blame] | 139 | initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry()); |
Andrew Trick | 14e8d71 | 2010-10-22 23:09:15 +0000 | [diff] [blame] | 140 | initializeMachineLoopInfoPass(*PassRegistry::getPassRegistry()); |
| 141 | initializeVirtRegMapPass(*PassRegistry::getPassRegistry()); |
| 142 | initializeRenderMachineFunctionPass(*PassRegistry::getPassRegistry()); |
| 143 | } |
| 144 | |
Andrew Trick | 18c57a8 | 2010-11-30 23:18:47 +0000 | [diff] [blame] | 145 | void RABasic::getAnalysisUsage(AnalysisUsage &AU) const { |
| 146 | AU.setPreservesCFG(); |
| 147 | AU.addRequired<AliasAnalysis>(); |
| 148 | AU.addPreserved<AliasAnalysis>(); |
| 149 | AU.addRequired<LiveIntervals>(); |
| 150 | AU.addPreserved<SlotIndexes>(); |
Jakob Stoklund Olesen | cfafc54 | 2011-04-05 21:40:37 +0000 | [diff] [blame] | 151 | AU.addRequired<LiveDebugVariables>(); |
| 152 | AU.addPreserved<LiveDebugVariables>(); |
Andrew Trick | 18c57a8 | 2010-11-30 23:18:47 +0000 | [diff] [blame] | 153 | AU.addRequired<CalculateSpillWeights>(); |
| 154 | AU.addRequired<LiveStacks>(); |
| 155 | AU.addPreserved<LiveStacks>(); |
| 156 | AU.addRequiredID(MachineDominatorsID); |
| 157 | AU.addPreservedID(MachineDominatorsID); |
| 158 | AU.addRequired<MachineLoopInfo>(); |
| 159 | AU.addPreserved<MachineLoopInfo>(); |
| 160 | AU.addRequired<VirtRegMap>(); |
| 161 | AU.addPreserved<VirtRegMap>(); |
| 162 | DEBUG(AU.addRequired<RenderMachineFunction>()); |
| 163 | MachineFunctionPass::getAnalysisUsage(AU); |
Andrew Trick | 14e8d71 | 2010-10-22 23:09:15 +0000 | [diff] [blame] | 164 | } |
| 165 | |
| 166 | void RABasic::releaseMemory() { |
Andrew Trick | 18c57a8 | 2010-11-30 23:18:47 +0000 | [diff] [blame] | 167 | SpillerInstance.reset(0); |
Andrew Trick | 14e8d71 | 2010-10-22 23:09:15 +0000 | [diff] [blame] | 168 | RegAllocBase::releaseMemory(); |
| 169 | } |
| 170 | |
Jakob Stoklund Olesen | a8bd9a6 | 2012-01-11 22:52:14 +0000 | [diff] [blame] | 171 | // Helper for spillInterferences() that spills all interfering vregs currently |
| 172 | // assigned to this physical register. |
| 173 | void RABasic::spillReg(LiveInterval& VirtReg, unsigned PhysReg, |
| 174 | SmallVectorImpl<LiveInterval*> &SplitVRegs) { |
| 175 | LiveIntervalUnion::Query &Q = query(VirtReg, PhysReg); |
| 176 | assert(Q.seenAllInterferences() && "need collectInterferences()"); |
| 177 | const SmallVectorImpl<LiveInterval*> &PendingSpills = Q.interferingVRegs(); |
| 178 | |
| 179 | for (SmallVectorImpl<LiveInterval*>::const_iterator I = PendingSpills.begin(), |
| 180 | E = PendingSpills.end(); I != E; ++I) { |
| 181 | LiveInterval &SpilledVReg = **I; |
| 182 | DEBUG(dbgs() << "extracting from " << |
| 183 | TRI->getName(PhysReg) << " " << SpilledVReg << '\n'); |
| 184 | |
| 185 | // Deallocate the interfering vreg by removing it from the union. |
| 186 | // A LiveInterval instance may not be in a union during modification! |
| 187 | unassign(SpilledVReg, PhysReg); |
| 188 | |
| 189 | // Spill the extracted interval. |
| 190 | LiveRangeEdit LRE(SpilledVReg, SplitVRegs, 0, &PendingSpills); |
| 191 | spiller().spill(LRE); |
| 192 | } |
| 193 | // After extracting segments, the query's results are invalid. But keep the |
| 194 | // contents valid until we're done accessing pendingSpills. |
| 195 | Q.clear(); |
| 196 | } |
| 197 | |
| 198 | // Spill or split all live virtual registers currently unified under PhysReg |
| 199 | // that interfere with VirtReg. The newly spilled or split live intervals are |
| 200 | // returned by appending them to SplitVRegs. |
| 201 | bool RABasic::spillInterferences(LiveInterval &VirtReg, unsigned PhysReg, |
| 202 | SmallVectorImpl<LiveInterval*> &SplitVRegs) { |
| 203 | // Record each interference and determine if all are spillable before mutating |
| 204 | // either the union or live intervals. |
| 205 | unsigned NumInterferences = 0; |
| 206 | // Collect interferences assigned to any alias of the physical register. |
| 207 | for (const unsigned *asI = TRI->getOverlaps(PhysReg); *asI; ++asI) { |
| 208 | LiveIntervalUnion::Query &QAlias = query(VirtReg, *asI); |
| 209 | NumInterferences += QAlias.collectInterferingVRegs(); |
| 210 | if (QAlias.seenUnspillableVReg()) { |
| 211 | return false; |
| 212 | } |
| 213 | } |
| 214 | DEBUG(dbgs() << "spilling " << TRI->getName(PhysReg) << |
| 215 | " interferences with " << VirtReg << "\n"); |
| 216 | assert(NumInterferences > 0 && "expect interference"); |
| 217 | |
| 218 | // Spill each interfering vreg allocated to PhysReg or an alias. |
| 219 | for (const unsigned *AliasI = TRI->getOverlaps(PhysReg); *AliasI; ++AliasI) |
| 220 | spillReg(VirtReg, *AliasI, SplitVRegs); |
| 221 | return true; |
| 222 | } |
| 223 | |
Andrew Trick | 14e8d71 | 2010-10-22 23:09:15 +0000 | [diff] [blame] | 224 | // Driver for the register assignment and splitting heuristics. |
| 225 | // Manages iteration over the LiveIntervalUnions. |
Andrew Trick | 13bdbb0 | 2010-11-20 02:43:55 +0000 | [diff] [blame] | 226 | // |
Andrew Trick | 18c57a8 | 2010-11-30 23:18:47 +0000 | [diff] [blame] | 227 | // This is a minimal implementation of register assignment and splitting that |
| 228 | // spills whenever we run out of registers. |
Andrew Trick | 14e8d71 | 2010-10-22 23:09:15 +0000 | [diff] [blame] | 229 | // |
| 230 | // selectOrSplit can only be called once per live virtual register. We then do a |
| 231 | // single interference test for each register the correct class until we find an |
| 232 | // available register. So, the number of interference tests in the worst case is |
| 233 | // |vregs| * |machineregs|. And since the number of interference tests is |
Andrew Trick | 18c57a8 | 2010-11-30 23:18:47 +0000 | [diff] [blame] | 234 | // minimal, there is no value in caching them outside the scope of |
| 235 | // selectOrSplit(). |
| 236 | unsigned RABasic::selectOrSplit(LiveInterval &VirtReg, |
| 237 | SmallVectorImpl<LiveInterval*> &SplitVRegs) { |
Jakob Stoklund Olesen | a94e635 | 2012-02-08 18:54:35 +0000 | [diff] [blame] | 238 | // Check for register mask interference. When live ranges cross calls, the |
| 239 | // set of usable registers is reduced to the callee-saved ones. |
| 240 | bool CrossRegMasks = LIS->checkRegMaskInterference(VirtReg, UsableRegs); |
| 241 | |
Andrew Trick | f4baeaf | 2010-11-10 19:18:47 +0000 | [diff] [blame] | 242 | // Populate a list of physical register spill candidates. |
Andrew Trick | 18c57a8 | 2010-11-30 23:18:47 +0000 | [diff] [blame] | 243 | SmallVector<unsigned, 8> PhysRegSpillCands; |
Andrew Trick | e141a49 | 2010-11-08 18:02:08 +0000 | [diff] [blame] | 244 | |
Andrew Trick | 13bdbb0 | 2010-11-20 02:43:55 +0000 | [diff] [blame] | 245 | // Check for an available register in this class. |
Jakob Stoklund Olesen | 5f2316a | 2011-06-03 20:34:53 +0000 | [diff] [blame] | 246 | ArrayRef<unsigned> Order = |
| 247 | RegClassInfo.getOrder(MRI->getRegClass(VirtReg.reg)); |
| 248 | for (ArrayRef<unsigned>::iterator I = Order.begin(), E = Order.end(); I != E; |
| 249 | ++I) { |
Andrew Trick | 18c57a8 | 2010-11-30 23:18:47 +0000 | [diff] [blame] | 250 | unsigned PhysReg = *I; |
Andrew Trick | 18c57a8 | 2010-11-30 23:18:47 +0000 | [diff] [blame] | 251 | |
Jakob Stoklund Olesen | a94e635 | 2012-02-08 18:54:35 +0000 | [diff] [blame] | 252 | // If PhysReg is clobbered by a register mask, it isn't useful for |
| 253 | // allocation or spilling. |
| 254 | if (CrossRegMasks && !UsableRegs.test(PhysReg)) |
| 255 | continue; |
| 256 | |
Andrew Trick | 18c57a8 | 2010-11-30 23:18:47 +0000 | [diff] [blame] | 257 | // Check interference and as a side effect, intialize queries for this |
| 258 | // VirtReg and its aliases. |
| 259 | unsigned interfReg = checkPhysRegInterference(VirtReg, PhysReg); |
Andrew Trick | e141a49 | 2010-11-08 18:02:08 +0000 | [diff] [blame] | 260 | if (interfReg == 0) { |
Andrew Trick | f4baeaf | 2010-11-10 19:18:47 +0000 | [diff] [blame] | 261 | // Found an available register. |
Andrew Trick | 18c57a8 | 2010-11-30 23:18:47 +0000 | [diff] [blame] | 262 | return PhysReg; |
Andrew Trick | 14e8d71 | 2010-10-22 23:09:15 +0000 | [diff] [blame] | 263 | } |
Jakob Stoklund Olesen | 9384111 | 2012-01-11 23:19:08 +0000 | [diff] [blame] | 264 | LiveIntervalUnion::Query &IntfQ = query(VirtReg, interfReg); |
| 265 | IntfQ.collectInterferingVRegs(1); |
| 266 | LiveInterval *interferingVirtReg = IntfQ.interferingVRegs().front(); |
Andrew Trick | f4baeaf | 2010-11-10 19:18:47 +0000 | [diff] [blame] | 267 | |
Andrew Trick | b853e6c | 2010-12-09 18:15:21 +0000 | [diff] [blame] | 268 | // The current VirtReg must either be spillable, or one of its interferences |
Andrew Trick | 18c57a8 | 2010-11-30 23:18:47 +0000 | [diff] [blame] | 269 | // must have less spill weight. |
| 270 | if (interferingVirtReg->weight < VirtReg.weight ) { |
| 271 | PhysRegSpillCands.push_back(PhysReg); |
Andrew Trick | e141a49 | 2010-11-08 18:02:08 +0000 | [diff] [blame] | 272 | } |
Andrew Trick | 14e8d71 | 2010-10-22 23:09:15 +0000 | [diff] [blame] | 273 | } |
Andrew Trick | f4baeaf | 2010-11-10 19:18:47 +0000 | [diff] [blame] | 274 | // Try to spill another interfering reg with less spill weight. |
Andrew Trick | 18c57a8 | 2010-11-30 23:18:47 +0000 | [diff] [blame] | 275 | for (SmallVectorImpl<unsigned>::iterator PhysRegI = PhysRegSpillCands.begin(), |
| 276 | PhysRegE = PhysRegSpillCands.end(); PhysRegI != PhysRegE; ++PhysRegI) { |
Andrew Trick | f4baeaf | 2010-11-10 19:18:47 +0000 | [diff] [blame] | 277 | |
Andrew Trick | 18c57a8 | 2010-11-30 23:18:47 +0000 | [diff] [blame] | 278 | if (!spillInterferences(VirtReg, *PhysRegI, SplitVRegs)) continue; |
Andrew Trick | 13bdbb0 | 2010-11-20 02:43:55 +0000 | [diff] [blame] | 279 | |
Jakob Stoklund Olesen | 2b38c51 | 2010-12-07 18:51:27 +0000 | [diff] [blame] | 280 | assert(checkPhysRegInterference(VirtReg, *PhysRegI) == 0 && |
| 281 | "Interference after spill."); |
Andrew Trick | f4baeaf | 2010-11-10 19:18:47 +0000 | [diff] [blame] | 282 | // Tell the caller to allocate to this newly freed physical register. |
Andrew Trick | 18c57a8 | 2010-11-30 23:18:47 +0000 | [diff] [blame] | 283 | return *PhysRegI; |
Andrew Trick | e141a49 | 2010-11-08 18:02:08 +0000 | [diff] [blame] | 284 | } |
Jakob Stoklund Olesen | bf4e10f | 2011-05-06 21:58:30 +0000 | [diff] [blame] | 285 | |
Andrew Trick | 18c57a8 | 2010-11-30 23:18:47 +0000 | [diff] [blame] | 286 | // No other spill candidates were found, so spill the current VirtReg. |
| 287 | DEBUG(dbgs() << "spilling: " << VirtReg << '\n'); |
Jakob Stoklund Olesen | bf4e10f | 2011-05-06 21:58:30 +0000 | [diff] [blame] | 288 | if (!VirtReg.isSpillable()) |
| 289 | return ~0u; |
Jakob Stoklund Olesen | 47dbf6c | 2011-03-10 01:51:42 +0000 | [diff] [blame] | 290 | LiveRangeEdit LRE(VirtReg, SplitVRegs); |
| 291 | spiller().spill(LRE); |
Andrew Trick | 13bdbb0 | 2010-11-20 02:43:55 +0000 | [diff] [blame] | 292 | |
Andrew Trick | f4baeaf | 2010-11-10 19:18:47 +0000 | [diff] [blame] | 293 | // The live virtual register requesting allocation was spilled, so tell |
| 294 | // the caller not to allocate anything during this round. |
| 295 | return 0; |
Andrew Trick | e141a49 | 2010-11-08 18:02:08 +0000 | [diff] [blame] | 296 | } |
Andrew Trick | 14e8d71 | 2010-10-22 23:09:15 +0000 | [diff] [blame] | 297 | |
Andrew Trick | 14e8d71 | 2010-10-22 23:09:15 +0000 | [diff] [blame] | 298 | bool RABasic::runOnMachineFunction(MachineFunction &mf) { |
| 299 | DEBUG(dbgs() << "********** BASIC REGISTER ALLOCATION **********\n" |
| 300 | << "********** Function: " |
| 301 | << ((Value*)mf.getFunction())->getName() << '\n'); |
| 302 | |
Andrew Trick | 18c57a8 | 2010-11-30 23:18:47 +0000 | [diff] [blame] | 303 | MF = &mf; |
Andrew Trick | 18c57a8 | 2010-11-30 23:18:47 +0000 | [diff] [blame] | 304 | DEBUG(RMF = &getAnalysis<RenderMachineFunction>()); |
Andrew Trick | 8a83d54 | 2010-11-11 17:46:29 +0000 | [diff] [blame] | 305 | |
Jakob Stoklund Olesen | 4680dec | 2010-12-10 23:49:00 +0000 | [diff] [blame] | 306 | RegAllocBase::init(getAnalysis<VirtRegMap>(), getAnalysis<LiveIntervals>()); |
Jakob Stoklund Olesen | 8427596 | 2011-03-31 23:02:17 +0000 | [diff] [blame] | 307 | SpillerInstance.reset(createInlineSpiller(*this, *MF, *VRM)); |
Andrew Trick | 13bdbb0 | 2010-11-20 02:43:55 +0000 | [diff] [blame] | 308 | |
Andrew Trick | e16eecc | 2010-10-26 18:34:01 +0000 | [diff] [blame] | 309 | allocatePhysRegs(); |
Andrew Trick | 14e8d71 | 2010-10-22 23:09:15 +0000 | [diff] [blame] | 310 | |
Jakob Stoklund Olesen | 1b19dc1 | 2010-12-08 01:06:06 +0000 | [diff] [blame] | 311 | addMBBLiveIns(MF); |
Andrew Trick | 316df4b | 2010-11-20 02:57:05 +0000 | [diff] [blame] | 312 | |
Andrew Trick | 14e8d71 | 2010-10-22 23:09:15 +0000 | [diff] [blame] | 313 | // Diagnostic output before rewriting |
Andrew Trick | 18c57a8 | 2010-11-30 23:18:47 +0000 | [diff] [blame] | 314 | DEBUG(dbgs() << "Post alloc VirtRegMap:\n" << *VRM << "\n"); |
Andrew Trick | 14e8d71 | 2010-10-22 23:09:15 +0000 | [diff] [blame] | 315 | |
| 316 | // optional HTML output |
Andrew Trick | 18c57a8 | 2010-11-30 23:18:47 +0000 | [diff] [blame] | 317 | DEBUG(RMF->renderMachineFunction("After basic register allocation.", VRM)); |
Andrew Trick | 14e8d71 | 2010-10-22 23:09:15 +0000 | [diff] [blame] | 318 | |
Andrew Trick | 071d1c0 | 2010-11-09 21:04:34 +0000 | [diff] [blame] | 319 | // FIXME: Verification currently must run before VirtRegRewriter. We should |
| 320 | // make the rewriter a separate pass and override verifyAnalysis instead. When |
| 321 | // that happens, verification naturally falls under VerifyMachineCode. |
| 322 | #ifndef NDEBUG |
Jakob Stoklund Olesen | af24964 | 2010-12-17 23:16:35 +0000 | [diff] [blame] | 323 | if (VerifyEnabled) { |
Andrew Trick | 071d1c0 | 2010-11-09 21:04:34 +0000 | [diff] [blame] | 324 | // Verify accuracy of LiveIntervals. The standard machine code verifier |
| 325 | // ensures that each LiveIntervals covers all uses of the virtual reg. |
| 326 | |
Andrew Trick | 18c57a8 | 2010-11-30 23:18:47 +0000 | [diff] [blame] | 327 | // FIXME: MachineVerifier is badly broken when using the standard |
| 328 | // spiller. Always use -spiller=inline with -verify-regalloc. Even with the |
| 329 | // inline spiller, some tests fail to verify because the coalescer does not |
| 330 | // always generate verifiable code. |
Jakob Stoklund Olesen | 89cab93 | 2010-12-18 00:06:56 +0000 | [diff] [blame] | 331 | MF->verify(this, "In RABasic::verify"); |
Andrew Trick | 13bdbb0 | 2010-11-20 02:43:55 +0000 | [diff] [blame] | 332 | |
Andrew Trick | 071d1c0 | 2010-11-09 21:04:34 +0000 | [diff] [blame] | 333 | // Verify that LiveIntervals are partitioned into unions and disjoint within |
| 334 | // the unions. |
| 335 | verify(); |
| 336 | } |
| 337 | #endif // !NDEBUG |
Andrew Trick | 13bdbb0 | 2010-11-20 02:43:55 +0000 | [diff] [blame] | 338 | |
Andrew Trick | 14e8d71 | 2010-10-22 23:09:15 +0000 | [diff] [blame] | 339 | // Run rewriter |
Jakob Stoklund Olesen | ba05c01 | 2011-02-18 22:03:18 +0000 | [diff] [blame] | 340 | VRM->rewrite(LIS->getSlotIndexes()); |
Andrew Trick | e16eecc | 2010-10-26 18:34:01 +0000 | [diff] [blame] | 341 | |
Jakob Stoklund Olesen | cfafc54 | 2011-04-05 21:40:37 +0000 | [diff] [blame] | 342 | // Write out new DBG_VALUE instructions. |
| 343 | getAnalysis<LiveDebugVariables>().emitDebugValues(VRM); |
| 344 | |
Andrew Trick | e16eecc | 2010-10-26 18:34:01 +0000 | [diff] [blame] | 345 | // The pass output is in VirtRegMap. Release all the transient data. |
| 346 | releaseMemory(); |
Andrew Trick | 13bdbb0 | 2010-11-20 02:43:55 +0000 | [diff] [blame] | 347 | |
Andrew Trick | 14e8d71 | 2010-10-22 23:09:15 +0000 | [diff] [blame] | 348 | return true; |
| 349 | } |
| 350 | |
Andrew Trick | 13bdbb0 | 2010-11-20 02:43:55 +0000 | [diff] [blame] | 351 | FunctionPass* llvm::createBasicRegisterAllocator() |
Andrew Trick | 14e8d71 | 2010-10-22 23:09:15 +0000 | [diff] [blame] | 352 | { |
| 353 | return new RABasic(); |
| 354 | } |