RegAllocBasic.cpp revision 235633
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 "RenderMachineFunction.h" 19#include "Spiller.h" 20#include "VirtRegMap.h" 21#include "llvm/Analysis/AliasAnalysis.h" 22#include "llvm/Function.h" 23#include "llvm/PassAnalysisSupport.h" 24#include "llvm/CodeGen/CalcSpillWeights.h" 25#include "llvm/CodeGen/LiveIntervalAnalysis.h" 26#include "llvm/CodeGen/LiveRangeEdit.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; 75 76 // Scratch space. Allocated here to avoid repeated malloc calls in 77 // selectOrSplit(). 78 BitVector UsableRegs; 79 80public: 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. 89 virtual void getAnalysisUsage(AnalysisUsage &AU) const; 90 91 virtual void releaseMemory(); 92 93 virtual Spiller &spiller() { return *SpillerInstance; } 94 95 virtual float getPriority(LiveInterval *LI) { return LI->weight; } 96 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 109 virtual unsigned selectOrSplit(LiveInterval &VirtReg, 110 SmallVectorImpl<LiveInterval*> &SplitVRegs); 111 112 /// Perform register allocation. 113 virtual bool runOnMachineFunction(MachineFunction &mf); 114 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 124 static char ID; 125}; 126 127char RABasic::ID = 0; 128 129} // end anonymous namespace 130 131RABasic::RABasic(): MachineFunctionPass(ID) { 132 initializeLiveDebugVariablesPass(*PassRegistry::getPassRegistry()); 133 initializeLiveIntervalsPass(*PassRegistry::getPassRegistry()); 134 initializeSlotIndexesPass(*PassRegistry::getPassRegistry()); 135 initializeRegisterCoalescerPass(*PassRegistry::getPassRegistry()); 136 initializeMachineSchedulerPass(*PassRegistry::getPassRegistry()); 137 initializeCalculateSpillWeightsPass(*PassRegistry::getPassRegistry()); 138 initializeLiveStacksPass(*PassRegistry::getPassRegistry()); 139 initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry()); 140 initializeMachineLoopInfoPass(*PassRegistry::getPassRegistry()); 141 initializeVirtRegMapPass(*PassRegistry::getPassRegistry()); 142 initializeRenderMachineFunctionPass(*PassRegistry::getPassRegistry()); 143} 144 145void RABasic::getAnalysisUsage(AnalysisUsage &AU) const { 146 AU.setPreservesCFG(); 147 AU.addRequired<AliasAnalysis>(); 148 AU.addPreserved<AliasAnalysis>(); 149 AU.addRequired<LiveIntervals>(); 150 AU.addPreserved<SlotIndexes>(); 151 AU.addRequired<LiveDebugVariables>(); 152 AU.addPreserved<LiveDebugVariables>(); 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); 164} 165 166void RABasic::releaseMemory() { 167 SpillerInstance.reset(0); 168 RegAllocBase::releaseMemory(); 169} 170 171// Helper for spillInterferences() that spills all interfering vregs currently 172// assigned to this physical register. 173void 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, *MF, *LIS, VRM); 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. 201bool 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 uint16_t *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 uint16_t *AliasI = TRI->getOverlaps(PhysReg); *AliasI; ++AliasI) 220 spillReg(VirtReg, *AliasI, SplitVRegs); 221 return true; 222} 223 224// Driver for the register assignment and splitting heuristics. 225// Manages iteration over the LiveIntervalUnions. 226// 227// This is a minimal implementation of register assignment and splitting that 228// spills whenever we run out of registers. 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 234// minimal, there is no value in caching them outside the scope of 235// selectOrSplit(). 236unsigned RABasic::selectOrSplit(LiveInterval &VirtReg, 237 SmallVectorImpl<LiveInterval*> &SplitVRegs) { 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 242 // Populate a list of physical register spill candidates. 243 SmallVector<unsigned, 8> PhysRegSpillCands; 244 245 // Check for an available register in this class. 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) { 250 unsigned PhysReg = *I; 251 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 257 // Check interference and as a side effect, intialize queries for this 258 // VirtReg and its aliases. 259 unsigned interfReg = checkPhysRegInterference(VirtReg, PhysReg); 260 if (interfReg == 0) { 261 // Found an available register. 262 return PhysReg; 263 } 264 LiveIntervalUnion::Query &IntfQ = query(VirtReg, interfReg); 265 IntfQ.collectInterferingVRegs(1); 266 LiveInterval *interferingVirtReg = IntfQ.interferingVRegs().front(); 267 268 // The current VirtReg must either be spillable, or one of its interferences 269 // must have less spill weight. 270 if (interferingVirtReg->weight < VirtReg.weight ) { 271 PhysRegSpillCands.push_back(PhysReg); 272 } 273 } 274 // Try to spill another interfering reg with less spill weight. 275 for (SmallVectorImpl<unsigned>::iterator PhysRegI = PhysRegSpillCands.begin(), 276 PhysRegE = PhysRegSpillCands.end(); PhysRegI != PhysRegE; ++PhysRegI) { 277 278 if (!spillInterferences(VirtReg, *PhysRegI, SplitVRegs)) continue; 279 280 assert(checkPhysRegInterference(VirtReg, *PhysRegI) == 0 && 281 "Interference after spill."); 282 // Tell the caller to allocate to this newly freed physical register. 283 return *PhysRegI; 284 } 285 286 // No other spill candidates were found, so spill the current VirtReg. 287 DEBUG(dbgs() << "spilling: " << VirtReg << '\n'); 288 if (!VirtReg.isSpillable()) 289 return ~0u; 290 LiveRangeEdit LRE(VirtReg, SplitVRegs, *MF, *LIS, VRM); 291 spiller().spill(LRE); 292 293 // The live virtual register requesting allocation was spilled, so tell 294 // the caller not to allocate anything during this round. 295 return 0; 296} 297 298bool RABasic::runOnMachineFunction(MachineFunction &mf) { 299 DEBUG(dbgs() << "********** BASIC REGISTER ALLOCATION **********\n" 300 << "********** Function: " 301 << ((Value*)mf.getFunction())->getName() << '\n'); 302 303 MF = &mf; 304 DEBUG(RMF = &getAnalysis<RenderMachineFunction>()); 305 306 RegAllocBase::init(getAnalysis<VirtRegMap>(), getAnalysis<LiveIntervals>()); 307 SpillerInstance.reset(createInlineSpiller(*this, *MF, *VRM)); 308 309 allocatePhysRegs(); 310 311 addMBBLiveIns(MF); 312 313 // Diagnostic output before rewriting 314 DEBUG(dbgs() << "Post alloc VirtRegMap:\n" << *VRM << "\n"); 315 316 // optional HTML output 317 DEBUG(RMF->renderMachineFunction("After basic register allocation.", VRM)); 318 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 323 if (VerifyEnabled) { 324 // Verify accuracy of LiveIntervals. The standard machine code verifier 325 // ensures that each LiveIntervals covers all uses of the virtual reg. 326 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. 331 MF->verify(this, "In RABasic::verify"); 332 333 // Verify that LiveIntervals are partitioned into unions and disjoint within 334 // the unions. 335 verify(); 336 } 337#endif // !NDEBUG 338 339 // Run rewriter 340 VRM->rewrite(LIS->getSlotIndexes()); 341 342 // Write out new DBG_VALUE instructions. 343 getAnalysis<LiveDebugVariables>().emitDebugValues(VRM); 344 345 // All machine operands and other references to virtual registers have been 346 // replaced. Remove the virtual registers and release all the transient data. 347 VRM->clearAllVirt(); 348 MRI->clearVirtRegs(); 349 releaseMemory(); 350 351 return true; 352} 353 354FunctionPass* llvm::createBasicRegisterAllocator() 355{ 356 return new RABasic(); 357} 358