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