RegAllocBasic.cpp revision e16eecc323879744dcff4f359ba9ccdb25bd6909
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 "LiveIntervalUnion.h" 17#include "RegAllocBase.h" 18#include "RenderMachineFunction.h" 19#include "Spiller.h" 20#include "VirtRegRewriter.h" 21#include "llvm/Function.h" 22#include "llvm/PassAnalysisSupport.h" 23#include "llvm/CodeGen/CalcSpillWeights.h" 24#include "llvm/CodeGen/LiveStackAnalysis.h" 25#include "llvm/CodeGen/MachineFunctionPass.h" 26#include "llvm/CodeGen/MachineInstr.h" 27#include "llvm/CodeGen/MachineLoopInfo.h" 28#include "llvm/CodeGen/MachineRegisterInfo.h" 29#include "llvm/CodeGen/Passes.h" 30#include "llvm/CodeGen/RegAllocRegistry.h" 31#include "llvm/CodeGen/RegisterCoalescer.h" 32#include "llvm/Target/TargetMachine.h" 33#include "llvm/Target/TargetOptions.h" 34#include "llvm/Support/Debug.h" 35#include "llvm/Support/raw_ostream.h" 36 37#include "VirtRegMap.h" 38#include "llvm/CodeGen/LiveIntervalAnalysis.h" 39#include "llvm/Target/TargetRegisterInfo.h" 40 41 42#include <vector> 43#include <queue> 44 45using namespace llvm; 46 47static RegisterRegAlloc basicRegAlloc("basic", "basic register allocator", 48 createBasicRegisterAllocator); 49 50namespace { 51 52/// RABasic provides a minimal implementation of the basic register allocation 53/// algorithm. It prioritizes live virtual registers by spill weight and spills 54/// whenever a register is unavailable. This is not practical in production but 55/// provides a useful baseline both for measuring other allocators and comparing 56/// the speed of the basic algorithm against other styles of allocators. 57class RABasic : public MachineFunctionPass, public RegAllocBase 58{ 59 // context 60 MachineFunction *mf_; 61 const TargetMachine *tm_; 62 MachineRegisterInfo *mri_; 63 64 // analyses 65 LiveStacks *ls_; 66 RenderMachineFunction *rmf_; 67 68 // state 69 std::auto_ptr<Spiller> spiller_; 70 71public: 72 RABasic(); 73 74 /// Return the pass name. 75 virtual const char* getPassName() const { 76 return "Basic Register Allocator"; 77 } 78 79 /// RABasic analysis usage. 80 virtual void getAnalysisUsage(AnalysisUsage &au) const; 81 82 virtual void releaseMemory(); 83 84 virtual unsigned selectOrSplit(LiveInterval &lvr, 85 SmallVectorImpl<LiveInterval*> &splitLVRs); 86 87 /// Perform register allocation. 88 virtual bool runOnMachineFunction(MachineFunction &mf); 89 90 static char ID; 91}; 92 93char RABasic::ID = 0; 94 95} // end anonymous namespace 96 97// We should not need to publish the initializer as long as no other passes 98// require RABasic. 99#if 0 // disable INITIALIZE_PASS 100INITIALIZE_PASS_BEGIN(RABasic, "basic-regalloc", 101 "Basic Register Allocator", false, false) 102INITIALIZE_PASS_DEPENDENCY(LiveIntervals) 103INITIALIZE_PASS_DEPENDENCY(StrongPHIElimination) 104INITIALIZE_AG_DEPENDENCY(RegisterCoalescer) 105INITIALIZE_PASS_DEPENDENCY(CalculateSpillWeights) 106INITIALIZE_PASS_DEPENDENCY(LiveStacks) 107INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) 108INITIALIZE_PASS_DEPENDENCY(VirtRegMap) 109#ifndef NDEBUG 110INITIALIZE_PASS_DEPENDENCY(RenderMachineFunction) 111#endif 112INITIALIZE_PASS_END(RABasic, "basic-regalloc", 113 "Basic Register Allocator", false, false) 114#endif // disable INITIALIZE_PASS 115 116RABasic::RABasic(): MachineFunctionPass(ID) { 117 initializeLiveIntervalsPass(*PassRegistry::getPassRegistry()); 118 initializeSlotIndexesPass(*PassRegistry::getPassRegistry()); 119 initializeStrongPHIEliminationPass(*PassRegistry::getPassRegistry()); 120 initializeRegisterCoalescerAnalysisGroup(*PassRegistry::getPassRegistry()); 121 initializeCalculateSpillWeightsPass(*PassRegistry::getPassRegistry()); 122 initializeLiveStacksPass(*PassRegistry::getPassRegistry()); 123 initializeMachineLoopInfoPass(*PassRegistry::getPassRegistry()); 124 initializeVirtRegMapPass(*PassRegistry::getPassRegistry()); 125 initializeRenderMachineFunctionPass(*PassRegistry::getPassRegistry()); 126} 127 128void RABasic::getAnalysisUsage(AnalysisUsage &au) const { 129 au.setPreservesCFG(); 130 au.addRequired<LiveIntervals>(); 131 au.addPreserved<SlotIndexes>(); 132 if (StrongPHIElim) 133 au.addRequiredID(StrongPHIEliminationID); 134 au.addRequiredTransitive<RegisterCoalescer>(); 135 au.addRequired<CalculateSpillWeights>(); 136 au.addRequired<LiveStacks>(); 137 au.addPreserved<LiveStacks>(); 138 au.addRequired<MachineLoopInfo>(); 139 au.addPreserved<MachineLoopInfo>(); 140 au.addRequired<VirtRegMap>(); 141 au.addPreserved<VirtRegMap>(); 142 DEBUG(au.addRequired<RenderMachineFunction>()); 143 MachineFunctionPass::getAnalysisUsage(au); 144} 145 146void RABasic::releaseMemory() { 147 spiller_.reset(0); 148 RegAllocBase::releaseMemory(); 149} 150 151//===----------------------------------------------------------------------===// 152// RegAllocBase Implementation 153//===----------------------------------------------------------------------===// 154 155// Instantiate a LiveIntervalUnion for each physical register. 156void RegAllocBase::LIUArray::init(unsigned nRegs) { 157 array_.reset(new LiveIntervalUnion[nRegs]); 158 nRegs_ = nRegs; 159 for (unsigned pr = 0; pr < nRegs; ++pr) { 160 array_[pr].init(pr); 161 } 162} 163 164void RegAllocBase::init(const TargetRegisterInfo &tri, VirtRegMap &vrm, 165 LiveIntervals &lis) { 166 tri_ = &tri; 167 vrm_ = &vrm; 168 lis_ = &lis; 169 physReg2liu_.init(tri_->getNumRegs()); 170} 171 172void RegAllocBase::LIUArray::clear() { 173 nRegs_ = 0; 174 array_.reset(0); 175} 176 177void RegAllocBase::releaseMemory() { 178 physReg2liu_.clear(); 179} 180 181namespace llvm { 182/// This class defines a queue of live virtual registers prioritized by spill 183/// weight. The heaviest vreg is popped first. 184/// 185/// Currently, this is trivial wrapper that gives us an opaque type in the 186/// header, but we may later give it a virtual interface for register allocators 187/// to override the priority queue comparator. 188class LiveVirtRegQueue { 189 typedef std::priority_queue 190 <LiveInterval*, std::vector<LiveInterval*>, LessSpillWeightPriority> PQ; 191 PQ pq_; 192 193public: 194 // Is the queue empty? 195 bool empty() { return pq_.empty(); } 196 197 // Get the highest priority lvr (top + pop) 198 LiveInterval *get() { 199 LiveInterval *lvr = pq_.top(); 200 pq_.pop(); 201 return lvr; 202 } 203 // Add this lvr to the queue 204 void push(LiveInterval *lvr) { 205 pq_.push(lvr); 206 } 207}; 208} // end namespace llvm 209 210// Visit all the live virtual registers. If they are already assigned to a 211// physical register, unify them with the corresponding LiveIntervalUnion, 212// otherwise push them on the priority queue for later assignment. 213void RegAllocBase::seedLiveVirtRegs(LiveVirtRegQueue &lvrQ) { 214 for (LiveIntervals::iterator liItr = lis_->begin(), liEnd = lis_->end(); 215 liItr != liEnd; ++liItr) { 216 unsigned reg = liItr->first; 217 LiveInterval &li = *liItr->second; 218 if (TargetRegisterInfo::isPhysicalRegister(reg)) { 219 physReg2liu_[reg].unify(li); 220 } 221 else { 222 lvrQ.push(&li); 223 } 224 } 225} 226 227// Top-level driver to manage the queue of unassigned LiveVirtRegs and call the 228// selectOrSplit implementation. 229void RegAllocBase::allocatePhysRegs() { 230 LiveVirtRegQueue lvrQ; 231 seedLiveVirtRegs(lvrQ); 232 while (!lvrQ.empty()) { 233 LiveInterval *lvr = lvrQ.get(); 234 typedef SmallVector<LiveInterval*, 4> LVRVec; 235 LVRVec splitLVRs; 236 unsigned availablePhysReg = selectOrSplit(*lvr, splitLVRs); 237 if (availablePhysReg) { 238 assert(splitLVRs.empty() && "inconsistent splitting"); 239 assert(!vrm_->hasPhys(lvr->reg) && "duplicate vreg in interval unions"); 240 vrm_->assignVirt2Phys(lvr->reg, availablePhysReg); 241 physReg2liu_[availablePhysReg].unify(*lvr); 242 } 243 else { 244 for (LVRVec::iterator lvrI = splitLVRs.begin(), lvrEnd = splitLVRs.end(); 245 lvrI != lvrEnd; ++lvrI) { 246 assert(TargetRegisterInfo::isVirtualRegister((*lvrI)->reg) && 247 "expect split value in virtual register"); 248 lvrQ.push(*lvrI); 249 } 250 } 251 } 252} 253 254// Check if this live virtual reg interferes with a physical register. If not, 255// then check for interference on each register that aliases with the physical 256// register. 257bool RegAllocBase::checkPhysRegInterference(LiveIntervalUnion::Query &query, 258 unsigned preg) { 259 if (query.checkInterference()) 260 return true; 261 for (const unsigned *asI = tri_->getAliasSet(preg); *asI; ++asI) { 262 // We assume it's very unlikely for a register in the alias set to also be 263 // in the original register class. So we don't bother caching the 264 // interference. 265 LiveIntervalUnion::Query subQuery(query.lvr(), physReg2liu_[*asI] ); 266 if (subQuery.checkInterference()) 267 return true; 268 } 269 return false; 270} 271 272//===----------------------------------------------------------------------===// 273// RABasic Implementation 274//===----------------------------------------------------------------------===// 275 276// Driver for the register assignment and splitting heuristics. 277// Manages iteration over the LiveIntervalUnions. 278// 279// Minimal implementation of register assignment and splitting--spills whenever 280// we run out of registers. 281// 282// selectOrSplit can only be called once per live virtual register. We then do a 283// single interference test for each register the correct class until we find an 284// available register. So, the number of interference tests in the worst case is 285// |vregs| * |machineregs|. And since the number of interference tests is 286// minimal, there is no value in caching them. 287unsigned RABasic::selectOrSplit(LiveInterval &lvr, 288 SmallVectorImpl<LiveInterval*> &splitLVRs) { 289 // Check for an available reg in this class. 290 const TargetRegisterClass *trc = mri_->getRegClass(lvr.reg); 291 for (TargetRegisterClass::iterator trcI = trc->allocation_order_begin(*mf_), 292 trcEnd = trc->allocation_order_end(*mf_); 293 trcI != trcEnd; ++trcI) { 294 unsigned preg = *trcI; 295 LiveIntervalUnion::Query query(lvr, physReg2liu_[preg]); 296 if (!checkPhysRegInterference(query, preg)) { 297 DEBUG(dbgs() << "\tallocating: " << tri_->getName(preg) << lvr << '\n'); 298 return preg; 299 } 300 } 301 DEBUG(dbgs() << "\tspilling: " << lvr << '\n'); 302 SmallVector<LiveInterval*, 1> spillIs; // ignored 303 spiller_->spill(&lvr, splitLVRs, spillIs); 304 305 // FIXME: update LiveStacks 306 return 0; 307} 308 309bool RABasic::runOnMachineFunction(MachineFunction &mf) { 310 DEBUG(dbgs() << "********** BASIC REGISTER ALLOCATION **********\n" 311 << "********** Function: " 312 << ((Value*)mf.getFunction())->getName() << '\n'); 313 314 mf_ = &mf; 315 tm_ = &mf.getTarget(); 316 mri_ = &mf.getRegInfo(); 317 318 DEBUG(rmf_ = &getAnalysis<RenderMachineFunction>()); 319 320 RegAllocBase::init(*tm_->getRegisterInfo(), getAnalysis<VirtRegMap>(), 321 getAnalysis<LiveIntervals>()); 322 323 spiller_.reset(createSpiller(*this, *mf_, *vrm_)); 324 325 allocatePhysRegs(); 326 327 // Diagnostic output before rewriting 328 DEBUG(dbgs() << "Post alloc VirtRegMap:\n" << *vrm_ << "\n"); 329 330 // optional HTML output 331 DEBUG(rmf_->renderMachineFunction("After basic register allocation.", vrm_)); 332 333 // Run rewriter 334 std::auto_ptr<VirtRegRewriter> rewriter(createVirtRegRewriter()); 335 rewriter->runOnMachineFunction(*mf_, *vrm_, lis_); 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