RegAllocPBQP.cpp revision 218893
1193323Sed//===------ RegAllocPBQP.cpp ---- PBQP Register Allocator -------*- C++ -*-===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// This file contains a Partitioned Boolean Quadratic Programming (PBQP) based 11193323Sed// register allocator for LLVM. This allocator works by constructing a PBQP 12193323Sed// problem representing the register allocation problem under consideration, 13193323Sed// solving this using a PBQP solver, and mapping the solution back to a 14193323Sed// register assignment. If any variables are selected for spilling then spill 15193323Sed// code is inserted and the process repeated. 16193323Sed// 17193323Sed// The PBQP solver (pbqp.c) provided for this allocator uses a heuristic tuned 18193323Sed// for register allocation. For more information on PBQP for register 19193323Sed// allocation, see the following papers: 20193323Sed// 21193323Sed// (1) Hames, L. and Scholz, B. 2006. Nearly optimal register allocation with 22193323Sed// PBQP. In Proceedings of the 7th Joint Modular Languages Conference 23193323Sed// (JMLC'06). LNCS, vol. 4228. Springer, New York, NY, USA. 346-361. 24193323Sed// 25193323Sed// (2) Scholz, B., Eckstein, E. 2002. Register allocation for irregular 26193323Sed// architectures. In Proceedings of the Joint Conference on Languages, 27193323Sed// Compilers and Tools for Embedded Systems (LCTES'02), ACM Press, New York, 28193323Sed// NY, USA, 139-148. 29193323Sed// 30193323Sed//===----------------------------------------------------------------------===// 31193323Sed 32193323Sed#define DEBUG_TYPE "regalloc" 33193323Sed 34212904Sdim#include "RenderMachineFunction.h" 35212904Sdim#include "Splitter.h" 36193323Sed#include "VirtRegMap.h" 37193323Sed#include "VirtRegRewriter.h" 38200581Srdivacky#include "llvm/CodeGen/CalcSpillWeights.h" 39193323Sed#include "llvm/CodeGen/LiveIntervalAnalysis.h" 40193323Sed#include "llvm/CodeGen/LiveStackAnalysis.h" 41218893Sdim#include "llvm/CodeGen/RegAllocPBQP.h" 42193323Sed#include "llvm/CodeGen/MachineFunctionPass.h" 43193323Sed#include "llvm/CodeGen/MachineLoopInfo.h" 44193323Sed#include "llvm/CodeGen/MachineRegisterInfo.h" 45218893Sdim#include "llvm/CodeGen/PBQP/HeuristicSolver.h" 46218893Sdim#include "llvm/CodeGen/PBQP/Graph.h" 47218893Sdim#include "llvm/CodeGen/PBQP/Heuristics/Briggs.h" 48193323Sed#include "llvm/CodeGen/RegAllocRegistry.h" 49193323Sed#include "llvm/CodeGen/RegisterCoalescer.h" 50193323Sed#include "llvm/Support/Debug.h" 51198090Srdivacky#include "llvm/Support/raw_ostream.h" 52193323Sed#include "llvm/Target/TargetInstrInfo.h" 53193323Sed#include "llvm/Target/TargetMachine.h" 54193323Sed#include <limits> 55193323Sed#include <memory> 56193323Sed#include <set> 57193323Sed#include <vector> 58193323Sed 59193323Sedusing namespace llvm; 60193323Sed 61193323Sedstatic RegisterRegAlloc 62204642SrdivackyregisterPBQPRepAlloc("pbqp", "PBQP register allocator", 63218893Sdim createDefaultPBQPRegisterAllocator); 64193323Sed 65198090Srdivackystatic cl::opt<bool> 66198090SrdivackypbqpCoalescing("pbqp-coalescing", 67203954Srdivacky cl::desc("Attempt coalescing during PBQP register allocation."), 68203954Srdivacky cl::init(false), cl::Hidden); 69198090Srdivacky 70212904Sdimstatic cl::opt<bool> 71212904SdimpbqpPreSplitting("pbqp-pre-splitting", 72218893Sdim cl::desc("Pre-split before PBQP register allocation."), 73212904Sdim cl::init(false), cl::Hidden); 74212904Sdim 75193323Sednamespace { 76193323Sed 77218893Sdim/// 78218893Sdim/// PBQP based allocators solve the register allocation problem by mapping 79218893Sdim/// register allocation problems to Partitioned Boolean Quadratic 80218893Sdim/// Programming problems. 81218893Sdimclass RegAllocPBQP : public MachineFunctionPass { 82218893Sdimpublic: 83193323Sed 84218893Sdim static char ID; 85193323Sed 86218893Sdim /// Construct a PBQP register allocator. 87218893Sdim RegAllocPBQP(std::auto_ptr<PBQPBuilder> b) 88218893Sdim : MachineFunctionPass(ID), builder(b) { 89218893Sdim initializeSlotIndexesPass(*PassRegistry::getPassRegistry()); 90218893Sdim initializeLiveIntervalsPass(*PassRegistry::getPassRegistry()); 91218893Sdim initializeRegisterCoalescerAnalysisGroup(*PassRegistry::getPassRegistry()); 92218893Sdim initializeCalculateSpillWeightsPass(*PassRegistry::getPassRegistry()); 93218893Sdim initializeLiveStacksPass(*PassRegistry::getPassRegistry()); 94218893Sdim initializeMachineLoopInfoPass(*PassRegistry::getPassRegistry()); 95218893Sdim initializeLoopSplitterPass(*PassRegistry::getPassRegistry()); 96218893Sdim initializeVirtRegMapPass(*PassRegistry::getPassRegistry()); 97218893Sdim initializeRenderMachineFunctionPass(*PassRegistry::getPassRegistry()); 98218893Sdim } 99193323Sed 100218893Sdim /// Return the pass name. 101218893Sdim virtual const char* getPassName() const { 102218893Sdim return "PBQP Register Allocator"; 103218893Sdim } 104193323Sed 105218893Sdim /// PBQP analysis usage. 106218893Sdim virtual void getAnalysisUsage(AnalysisUsage &au) const; 107193323Sed 108218893Sdim /// Perform register allocation 109218893Sdim virtual bool runOnMachineFunction(MachineFunction &MF); 110193323Sed 111218893Sdimprivate: 112212904Sdim 113218893Sdim typedef std::map<const LiveInterval*, unsigned> LI2NodeMap; 114218893Sdim typedef std::vector<const LiveInterval*> Node2LIMap; 115218893Sdim typedef std::vector<unsigned> AllowedSet; 116218893Sdim typedef std::vector<AllowedSet> AllowedSetMap; 117218893Sdim typedef std::pair<unsigned, unsigned> RegPair; 118218893Sdim typedef std::map<RegPair, PBQP::PBQPNum> CoalesceMap; 119218893Sdim typedef std::vector<PBQP::Graph::NodeItr> NodeVector; 120218893Sdim typedef std::set<unsigned> RegSet; 121212904Sdim 122193323Sed 123218893Sdim std::auto_ptr<PBQPBuilder> builder; 124193323Sed 125218893Sdim MachineFunction *mf; 126218893Sdim const TargetMachine *tm; 127218893Sdim const TargetRegisterInfo *tri; 128218893Sdim const TargetInstrInfo *tii; 129218893Sdim const MachineLoopInfo *loopInfo; 130218893Sdim MachineRegisterInfo *mri; 131218893Sdim RenderMachineFunction *rmf; 132203954Srdivacky 133218893Sdim LiveIntervals *lis; 134218893Sdim LiveStacks *lss; 135218893Sdim VirtRegMap *vrm; 136193323Sed 137218893Sdim RegSet vregsToAlloc, emptyIntervalVRegs; 138193323Sed 139218893Sdim /// \brief Finds the initial set of vreg intervals to allocate. 140218893Sdim void findVRegIntervalsToAlloc(); 141193323Sed 142218893Sdim /// \brief Adds a stack interval if the given live interval has been 143218893Sdim /// spilled. Used to support stack slot coloring. 144218893Sdim void addStackInterval(const LiveInterval *spilled,MachineRegisterInfo* mri); 145193323Sed 146218893Sdim /// \brief Given a solved PBQP problem maps this solution back to a register 147218893Sdim /// assignment. 148218893Sdim bool mapPBQPToRegAlloc(const PBQPRAProblem &problem, 149218893Sdim const PBQP::Solution &solution); 150193323Sed 151218893Sdim /// \brief Postprocessing before final spilling. Sets basic block "live in" 152218893Sdim /// variables. 153218893Sdim void finalizeAlloc() const; 154193323Sed 155218893Sdim}; 156193323Sed 157218893Sdimchar RegAllocPBQP::ID = 0; 158193323Sed 159218893Sdim} // End anonymous namespace. 160193323Sed 161218893Sdimunsigned PBQPRAProblem::getVRegForNode(PBQP::Graph::ConstNodeItr node) const { 162218893Sdim Node2VReg::const_iterator vregItr = node2VReg.find(node); 163218893Sdim assert(vregItr != node2VReg.end() && "No vreg for node."); 164218893Sdim return vregItr->second; 165218893Sdim} 166193323Sed 167218893SdimPBQP::Graph::NodeItr PBQPRAProblem::getNodeForVReg(unsigned vreg) const { 168218893Sdim VReg2Node::const_iterator nodeItr = vreg2Node.find(vreg); 169218893Sdim assert(nodeItr != vreg2Node.end() && "No node for vreg."); 170218893Sdim return nodeItr->second; 171218893Sdim 172218893Sdim} 173193323Sed 174218893Sdimconst PBQPRAProblem::AllowedSet& 175218893Sdim PBQPRAProblem::getAllowedSet(unsigned vreg) const { 176218893Sdim AllowedSetMap::const_iterator allowedSetItr = allowedSets.find(vreg); 177218893Sdim assert(allowedSetItr != allowedSets.end() && "No pregs for vreg."); 178218893Sdim const AllowedSet &allowedSet = allowedSetItr->second; 179218893Sdim return allowedSet; 180218893Sdim} 181193323Sed 182218893Sdimunsigned PBQPRAProblem::getPRegForOption(unsigned vreg, unsigned option) const { 183218893Sdim assert(isPRegOption(vreg, option) && "Not a preg option."); 184193323Sed 185218893Sdim const AllowedSet& allowedSet = getAllowedSet(vreg); 186218893Sdim assert(option <= allowedSet.size() && "Option outside allowed set."); 187218893Sdim return allowedSet[option - 1]; 188193323Sed} 189193323Sed 190218893Sdimstd::auto_ptr<PBQPRAProblem> PBQPBuilder::build(MachineFunction *mf, 191218893Sdim const LiveIntervals *lis, 192218893Sdim const MachineLoopInfo *loopInfo, 193218893Sdim const RegSet &vregs) { 194193323Sed 195218893Sdim typedef std::vector<const LiveInterval*> LIVector; 196193323Sed 197218893Sdim MachineRegisterInfo *mri = &mf->getRegInfo(); 198218893Sdim const TargetRegisterInfo *tri = mf->getTarget().getRegisterInfo(); 199193323Sed 200218893Sdim std::auto_ptr<PBQPRAProblem> p(new PBQPRAProblem()); 201218893Sdim PBQP::Graph &g = p->getGraph(); 202218893Sdim RegSet pregs; 203193323Sed 204218893Sdim // Collect the set of preg intervals, record that they're used in the MF. 205218893Sdim for (LiveIntervals::const_iterator itr = lis->begin(), end = lis->end(); 206218893Sdim itr != end; ++itr) { 207218893Sdim if (TargetRegisterInfo::isPhysicalRegister(itr->first)) { 208218893Sdim pregs.insert(itr->first); 209218893Sdim mri->setPhysRegUsed(itr->first); 210218893Sdim } 211218893Sdim } 212193323Sed 213218893Sdim BitVector reservedRegs = tri->getReservedRegs(*mf); 214193323Sed 215218893Sdim // Iterate over vregs. 216218893Sdim for (RegSet::const_iterator vregItr = vregs.begin(), vregEnd = vregs.end(); 217218893Sdim vregItr != vregEnd; ++vregItr) { 218218893Sdim unsigned vreg = *vregItr; 219218893Sdim const TargetRegisterClass *trc = mri->getRegClass(vreg); 220218893Sdim const LiveInterval *vregLI = &lis->getInterval(vreg); 221193323Sed 222218893Sdim // Compute an initial allowed set for the current vreg. 223218893Sdim typedef std::vector<unsigned> VRAllowed; 224218893Sdim VRAllowed vrAllowed; 225218893Sdim for (TargetRegisterClass::iterator aoItr = trc->allocation_order_begin(*mf), 226218893Sdim aoEnd = trc->allocation_order_end(*mf); 227218893Sdim aoItr != aoEnd; ++aoItr) { 228218893Sdim unsigned preg = *aoItr; 229218893Sdim if (!reservedRegs.test(preg)) { 230218893Sdim vrAllowed.push_back(preg); 231218893Sdim } 232218893Sdim } 233193323Sed 234218893Sdim // Remove any physical registers which overlap. 235218893Sdim for (RegSet::const_iterator pregItr = pregs.begin(), 236218893Sdim pregEnd = pregs.end(); 237218893Sdim pregItr != pregEnd; ++pregItr) { 238218893Sdim unsigned preg = *pregItr; 239218893Sdim const LiveInterval *pregLI = &lis->getInterval(preg); 240193323Sed 241218893Sdim if (pregLI->empty()) { 242218893Sdim continue; 243218893Sdim } 244193323Sed 245218893Sdim if (!vregLI->overlaps(*pregLI)) { 246218893Sdim continue; 247218893Sdim } 248193323Sed 249218893Sdim // Remove the register from the allowed set. 250218893Sdim VRAllowed::iterator eraseItr = 251218893Sdim std::find(vrAllowed.begin(), vrAllowed.end(), preg); 252193323Sed 253218893Sdim if (eraseItr != vrAllowed.end()) { 254218893Sdim vrAllowed.erase(eraseItr); 255218893Sdim } 256193323Sed 257218893Sdim // Also remove any aliases. 258218893Sdim const unsigned *aliasItr = tri->getAliasSet(preg); 259218893Sdim if (aliasItr != 0) { 260218893Sdim for (; *aliasItr != 0; ++aliasItr) { 261218893Sdim VRAllowed::iterator eraseItr = 262218893Sdim std::find(vrAllowed.begin(), vrAllowed.end(), *aliasItr); 263193323Sed 264218893Sdim if (eraseItr != vrAllowed.end()) { 265218893Sdim vrAllowed.erase(eraseItr); 266218893Sdim } 267218893Sdim } 268218893Sdim } 269218893Sdim } 270193323Sed 271218893Sdim // Construct the node. 272218893Sdim PBQP::Graph::NodeItr node = 273218893Sdim g.addNode(PBQP::Vector(vrAllowed.size() + 1, 0)); 274193323Sed 275218893Sdim // Record the mapping and allowed set in the problem. 276218893Sdim p->recordVReg(vreg, node, vrAllowed.begin(), vrAllowed.end()); 277193323Sed 278218893Sdim PBQP::PBQPNum spillCost = (vregLI->weight != 0.0) ? 279218893Sdim vregLI->weight : std::numeric_limits<PBQP::PBQPNum>::min(); 280193323Sed 281218893Sdim addSpillCosts(g.getNodeCosts(node), spillCost); 282218893Sdim } 283193323Sed 284218893Sdim for (RegSet::const_iterator vr1Itr = vregs.begin(), vrEnd = vregs.end(); 285218893Sdim vr1Itr != vrEnd; ++vr1Itr) { 286218893Sdim unsigned vr1 = *vr1Itr; 287218893Sdim const LiveInterval &l1 = lis->getInterval(vr1); 288218893Sdim const PBQPRAProblem::AllowedSet &vr1Allowed = p->getAllowedSet(vr1); 289193323Sed 290218893Sdim for (RegSet::const_iterator vr2Itr = llvm::next(vr1Itr); 291218893Sdim vr2Itr != vrEnd; ++vr2Itr) { 292218893Sdim unsigned vr2 = *vr2Itr; 293218893Sdim const LiveInterval &l2 = lis->getInterval(vr2); 294218893Sdim const PBQPRAProblem::AllowedSet &vr2Allowed = p->getAllowedSet(vr2); 295193323Sed 296218893Sdim assert(!l2.empty() && "Empty interval in vreg set?"); 297218893Sdim if (l1.overlaps(l2)) { 298218893Sdim PBQP::Graph::EdgeItr edge = 299218893Sdim g.addEdge(p->getNodeForVReg(vr1), p->getNodeForVReg(vr2), 300218893Sdim PBQP::Matrix(vr1Allowed.size()+1, vr2Allowed.size()+1, 0)); 301218893Sdim 302218893Sdim addInterferenceCosts(g.getEdgeCosts(edge), vr1Allowed, vr2Allowed, tri); 303193323Sed } 304193323Sed } 305193323Sed } 306193323Sed 307218893Sdim return p; 308218893Sdim} 309193323Sed 310218893Sdimvoid PBQPBuilder::addSpillCosts(PBQP::Vector &costVec, 311218893Sdim PBQP::PBQPNum spillCost) { 312218893Sdim costVec[0] = spillCost; 313193323Sed} 314193323Sed 315218893Sdimvoid PBQPBuilder::addInterferenceCosts( 316218893Sdim PBQP::Matrix &costMat, 317218893Sdim const PBQPRAProblem::AllowedSet &vr1Allowed, 318218893Sdim const PBQPRAProblem::AllowedSet &vr2Allowed, 319218893Sdim const TargetRegisterInfo *tri) { 320218893Sdim assert(costMat.getRows() == vr1Allowed.size() + 1 && "Matrix height mismatch."); 321218893Sdim assert(costMat.getCols() == vr2Allowed.size() + 1 && "Matrix width mismatch."); 322193323Sed 323218893Sdim for (unsigned i = 0; i != vr1Allowed.size(); ++i) { 324218893Sdim unsigned preg1 = vr1Allowed[i]; 325193323Sed 326218893Sdim for (unsigned j = 0; j != vr2Allowed.size(); ++j) { 327218893Sdim unsigned preg2 = vr2Allowed[j]; 328193323Sed 329218893Sdim if (tri->regsOverlap(preg1, preg2)) { 330218893Sdim costMat[i + 1][j + 1] = std::numeric_limits<PBQP::PBQPNum>::infinity(); 331193323Sed } 332193323Sed } 333193323Sed } 334193323Sed} 335193323Sed 336218893Sdimstd::auto_ptr<PBQPRAProblem> PBQPBuilderWithCoalescing::build( 337218893Sdim MachineFunction *mf, 338218893Sdim const LiveIntervals *lis, 339218893Sdim const MachineLoopInfo *loopInfo, 340218893Sdim const RegSet &vregs) { 341193323Sed 342218893Sdim std::auto_ptr<PBQPRAProblem> p = PBQPBuilder::build(mf, lis, loopInfo, vregs); 343218893Sdim PBQP::Graph &g = p->getGraph(); 344193323Sed 345218893Sdim const TargetMachine &tm = mf->getTarget(); 346218893Sdim CoalescerPair cp(*tm.getInstrInfo(), *tm.getRegisterInfo()); 347193323Sed 348218893Sdim // Scan the machine function and add a coalescing cost whenever CoalescerPair 349218893Sdim // gives the Ok. 350218893Sdim for (MachineFunction::const_iterator mbbItr = mf->begin(), 351218893Sdim mbbEnd = mf->end(); 352218893Sdim mbbItr != mbbEnd; ++mbbItr) { 353218893Sdim const MachineBasicBlock *mbb = &*mbbItr; 354193323Sed 355218893Sdim for (MachineBasicBlock::const_iterator miItr = mbb->begin(), 356218893Sdim miEnd = mbb->end(); 357218893Sdim miItr != miEnd; ++miItr) { 358218893Sdim const MachineInstr *mi = &*miItr; 359193323Sed 360218893Sdim if (!cp.setRegisters(mi)) { 361218893Sdim continue; // Not coalescable. 362218893Sdim } 363193323Sed 364218893Sdim if (cp.getSrcReg() == cp.getDstReg()) { 365218893Sdim continue; // Already coalesced. 366218893Sdim } 367193323Sed 368218893Sdim unsigned dst = cp.getDstReg(), 369218893Sdim src = cp.getSrcReg(); 370193323Sed 371218893Sdim const float copyFactor = 0.5; // Cost of copy relative to load. Current 372218893Sdim // value plucked randomly out of the air. 373218893Sdim 374218893Sdim PBQP::PBQPNum cBenefit = 375218893Sdim copyFactor * LiveIntervals::getSpillWeight(false, true, 376218893Sdim loopInfo->getLoopDepth(mbb)); 377212904Sdim 378218893Sdim if (cp.isPhys()) { 379218893Sdim if (!lis->isAllocatable(dst)) { 380193323Sed continue; 381218893Sdim } 382193323Sed 383218893Sdim const PBQPRAProblem::AllowedSet &allowed = p->getAllowedSet(src); 384218893Sdim unsigned pregOpt = 0; 385218893Sdim while (pregOpt < allowed.size() && allowed[pregOpt] != dst) { 386218893Sdim ++pregOpt; 387218893Sdim } 388218893Sdim if (pregOpt < allowed.size()) { 389218893Sdim ++pregOpt; // +1 to account for spill option. 390218893Sdim PBQP::Graph::NodeItr node = p->getNodeForVReg(src); 391218893Sdim addPhysRegCoalesce(g.getNodeCosts(node), pregOpt, cBenefit); 392218893Sdim } 393218893Sdim } else { 394218893Sdim const PBQPRAProblem::AllowedSet *allowed1 = &p->getAllowedSet(dst); 395218893Sdim const PBQPRAProblem::AllowedSet *allowed2 = &p->getAllowedSet(src); 396218893Sdim PBQP::Graph::NodeItr node1 = p->getNodeForVReg(dst); 397218893Sdim PBQP::Graph::NodeItr node2 = p->getNodeForVReg(src); 398218893Sdim PBQP::Graph::EdgeItr edge = g.findEdge(node1, node2); 399218893Sdim if (edge == g.edgesEnd()) { 400218893Sdim edge = g.addEdge(node1, node2, PBQP::Matrix(allowed1->size() + 1, 401218893Sdim allowed2->size() + 1, 402218893Sdim 0)); 403218893Sdim } else { 404218893Sdim if (g.getEdgeNode1(edge) == node2) { 405218893Sdim std::swap(node1, node2); 406218893Sdim std::swap(allowed1, allowed2); 407203954Srdivacky } 408193323Sed } 409218893Sdim 410218893Sdim addVirtRegCoalesce(g.getEdgeCosts(edge), *allowed1, *allowed2, 411218893Sdim cBenefit); 412218893Sdim } 413218893Sdim } 414218893Sdim } 415193323Sed 416218893Sdim return p; 417218893Sdim} 418193323Sed 419218893Sdimvoid PBQPBuilderWithCoalescing::addPhysRegCoalesce(PBQP::Vector &costVec, 420218893Sdim unsigned pregOption, 421218893Sdim PBQP::PBQPNum benefit) { 422218893Sdim costVec[pregOption] += -benefit; 423218893Sdim} 424193323Sed 425218893Sdimvoid PBQPBuilderWithCoalescing::addVirtRegCoalesce( 426218893Sdim PBQP::Matrix &costMat, 427218893Sdim const PBQPRAProblem::AllowedSet &vr1Allowed, 428218893Sdim const PBQPRAProblem::AllowedSet &vr2Allowed, 429218893Sdim PBQP::PBQPNum benefit) { 430193323Sed 431218893Sdim assert(costMat.getRows() == vr1Allowed.size() + 1 && "Size mismatch."); 432218893Sdim assert(costMat.getCols() == vr2Allowed.size() + 1 && "Size mismatch."); 433203954Srdivacky 434218893Sdim for (unsigned i = 0; i != vr1Allowed.size(); ++i) { 435218893Sdim unsigned preg1 = vr1Allowed[i]; 436218893Sdim for (unsigned j = 0; j != vr2Allowed.size(); ++j) { 437218893Sdim unsigned preg2 = vr2Allowed[j]; 438193323Sed 439218893Sdim if (preg1 == preg2) { 440218893Sdim costMat[i + 1][j + 1] += -benefit; 441218893Sdim } 442193323Sed } 443193323Sed } 444218893Sdim} 445193323Sed 446218893Sdim 447218893Sdimvoid RegAllocPBQP::getAnalysisUsage(AnalysisUsage &au) const { 448218893Sdim au.addRequired<SlotIndexes>(); 449218893Sdim au.addPreserved<SlotIndexes>(); 450218893Sdim au.addRequired<LiveIntervals>(); 451218893Sdim //au.addRequiredID(SplitCriticalEdgesID); 452218893Sdim au.addRequired<RegisterCoalescer>(); 453218893Sdim au.addRequired<CalculateSpillWeights>(); 454218893Sdim au.addRequired<LiveStacks>(); 455218893Sdim au.addPreserved<LiveStacks>(); 456218893Sdim au.addRequired<MachineLoopInfo>(); 457218893Sdim au.addPreserved<MachineLoopInfo>(); 458218893Sdim if (pbqpPreSplitting) 459218893Sdim au.addRequired<LoopSplitter>(); 460218893Sdim au.addRequired<VirtRegMap>(); 461218893Sdim au.addRequired<RenderMachineFunction>(); 462218893Sdim MachineFunctionPass::getAnalysisUsage(au); 463193323Sed} 464193323Sed 465218893Sdimvoid RegAllocPBQP::findVRegIntervalsToAlloc() { 466193323Sed 467193323Sed // Iterate over all live ranges. 468193323Sed for (LiveIntervals::iterator itr = lis->begin(), end = lis->end(); 469193323Sed itr != end; ++itr) { 470193323Sed 471193323Sed // Ignore physical ones. 472193323Sed if (TargetRegisterInfo::isPhysicalRegister(itr->first)) 473193323Sed continue; 474193323Sed 475193323Sed LiveInterval *li = itr->second; 476193323Sed 477193323Sed // If this live interval is non-empty we will use pbqp to allocate it. 478193323Sed // Empty intervals we allocate in a simple post-processing stage in 479193323Sed // finalizeAlloc. 480193323Sed if (!li->empty()) { 481218893Sdim vregsToAlloc.insert(li->reg); 482218893Sdim } else { 483218893Sdim emptyIntervalVRegs.insert(li->reg); 484193323Sed } 485193323Sed } 486193323Sed} 487193323Sed 488218893Sdimvoid RegAllocPBQP::addStackInterval(const LiveInterval *spilled, 489193323Sed MachineRegisterInfo* mri) { 490193323Sed int stackSlot = vrm->getStackSlot(spilled->reg); 491193323Sed 492218893Sdim if (stackSlot == VirtRegMap::NO_STACK_SLOT) { 493193323Sed return; 494218893Sdim } 495193323Sed 496193323Sed const TargetRegisterClass *RC = mri->getRegClass(spilled->reg); 497193323Sed LiveInterval &stackInterval = lss->getOrCreateInterval(stackSlot, RC); 498193323Sed 499193323Sed VNInfo *vni; 500218893Sdim if (stackInterval.getNumValNums() != 0) { 501193323Sed vni = stackInterval.getValNumInfo(0); 502218893Sdim } else { 503198090Srdivacky vni = stackInterval.getNextValue( 504218893Sdim SlotIndex(), 0, lss->getVNInfoAllocator()); 505218893Sdim } 506193323Sed 507193323Sed LiveInterval &rhsInterval = lis->getInterval(spilled->reg); 508193323Sed stackInterval.MergeRangesInAsValue(rhsInterval, vni); 509193323Sed} 510193323Sed 511218893Sdimbool RegAllocPBQP::mapPBQPToRegAlloc(const PBQPRAProblem &problem, 512218893Sdim const PBQP::Solution &solution) { 513193323Sed // Set to true if we have any spills 514193323Sed bool anotherRoundNeeded = false; 515193323Sed 516193323Sed // Clear the existing allocation. 517193323Sed vrm->clearAllVirt(); 518193323Sed 519218893Sdim const PBQP::Graph &g = problem.getGraph(); 520218893Sdim // Iterate over the nodes mapping the PBQP solution to a register 521218893Sdim // assignment. 522218893Sdim for (PBQP::Graph::ConstNodeItr node = g.nodesBegin(), 523218893Sdim nodeEnd = g.nodesEnd(); 524218893Sdim node != nodeEnd; ++node) { 525218893Sdim unsigned vreg = problem.getVRegForNode(node); 526218893Sdim unsigned alloc = solution.getSelection(node); 527193323Sed 528218893Sdim if (problem.isPRegOption(vreg, alloc)) { 529218893Sdim unsigned preg = problem.getPRegForOption(vreg, alloc); 530218893Sdim DEBUG(dbgs() << "VREG " << vreg << " -> " << tri->getName(preg) << "\n"); 531218893Sdim assert(preg != 0 && "Invalid preg selected."); 532218893Sdim vrm->assignVirt2Phys(vreg, preg); 533218893Sdim } else if (problem.isSpillOption(vreg, alloc)) { 534218893Sdim vregsToAlloc.erase(vreg); 535218893Sdim const LiveInterval* spillInterval = &lis->getInterval(vreg); 536218893Sdim double oldWeight = spillInterval->weight; 537193323Sed SmallVector<LiveInterval*, 8> spillIs; 538212904Sdim rmf->rememberUseDefs(spillInterval); 539193323Sed std::vector<LiveInterval*> newSpills = 540193323Sed lis->addIntervalsForSpills(*spillInterval, spillIs, loopInfo, *vrm); 541193323Sed addStackInterval(spillInterval, mri); 542212904Sdim rmf->rememberSpills(spillInterval, newSpills); 543193323Sed 544218893Sdim (void) oldWeight; 545218893Sdim DEBUG(dbgs() << "VREG " << vreg << " -> SPILLED (Cost: " 546218893Sdim << oldWeight << ", New vregs: "); 547193323Sed 548193323Sed // Copy any newly inserted live intervals into the list of regs to 549193323Sed // allocate. 550193323Sed for (std::vector<LiveInterval*>::const_iterator 551193323Sed itr = newSpills.begin(), end = newSpills.end(); 552193323Sed itr != end; ++itr) { 553193323Sed assert(!(*itr)->empty() && "Empty spill range."); 554202375Srdivacky DEBUG(dbgs() << (*itr)->reg << " "); 555218893Sdim vregsToAlloc.insert((*itr)->reg); 556193323Sed } 557193323Sed 558202375Srdivacky DEBUG(dbgs() << ")\n"); 559193323Sed 560193323Sed // We need another round if spill intervals were added. 561193323Sed anotherRoundNeeded |= !newSpills.empty(); 562218893Sdim } else { 563218893Sdim assert(false && "Unknown allocation option."); 564193323Sed } 565193323Sed } 566193323Sed 567193323Sed return !anotherRoundNeeded; 568193323Sed} 569193323Sed 570218893Sdim 571218893Sdimvoid RegAllocPBQP::finalizeAlloc() const { 572193323Sed typedef LiveIntervals::iterator LIIterator; 573193323Sed typedef LiveInterval::Ranges::const_iterator LRIterator; 574193323Sed 575193323Sed // First allocate registers for the empty intervals. 576218893Sdim for (RegSet::const_iterator 577218893Sdim itr = emptyIntervalVRegs.begin(), end = emptyIntervalVRegs.end(); 578193323Sed itr != end; ++itr) { 579218893Sdim LiveInterval *li = &lis->getInterval(*itr); 580193323Sed 581194612Sed unsigned physReg = vrm->getRegAllocPref(li->reg); 582198090Srdivacky 583193323Sed if (physReg == 0) { 584193323Sed const TargetRegisterClass *liRC = mri->getRegClass(li->reg); 585193323Sed physReg = *liRC->allocation_order_begin(*mf); 586193323Sed } 587193323Sed 588193323Sed vrm->assignVirt2Phys(li->reg, physReg); 589193323Sed } 590193323Sed 591193323Sed // Finally iterate over the basic blocks to compute and set the live-in sets. 592193323Sed SmallVector<MachineBasicBlock*, 8> liveInMBBs; 593193323Sed MachineBasicBlock *entryMBB = &*mf->begin(); 594193323Sed 595193323Sed for (LIIterator liItr = lis->begin(), liEnd = lis->end(); 596193323Sed liItr != liEnd; ++liItr) { 597193323Sed 598193323Sed const LiveInterval *li = liItr->second; 599193323Sed unsigned reg = 0; 600193323Sed 601193323Sed // Get the physical register for this interval 602193323Sed if (TargetRegisterInfo::isPhysicalRegister(li->reg)) { 603193323Sed reg = li->reg; 604218893Sdim } else if (vrm->isAssignedReg(li->reg)) { 605193323Sed reg = vrm->getPhys(li->reg); 606218893Sdim } else { 607193323Sed // Ranges which are assigned a stack slot only are ignored. 608193323Sed continue; 609193323Sed } 610193323Sed 611193323Sed if (reg == 0) { 612198090Srdivacky // Filter out zero regs - they're for intervals that were spilled. 613193323Sed continue; 614193323Sed } 615193323Sed 616193323Sed // Iterate over the ranges of the current interval... 617193323Sed for (LRIterator lrItr = li->begin(), lrEnd = li->end(); 618193323Sed lrItr != lrEnd; ++lrItr) { 619193323Sed 620193323Sed // Find the set of basic blocks which this range is live into... 621193323Sed if (lis->findLiveInMBBs(lrItr->start, lrItr->end, liveInMBBs)) { 622193323Sed // And add the physreg for this interval to their live-in sets. 623218893Sdim for (unsigned i = 0; i != liveInMBBs.size(); ++i) { 624193323Sed if (liveInMBBs[i] != entryMBB) { 625193323Sed if (!liveInMBBs[i]->isLiveIn(reg)) { 626193323Sed liveInMBBs[i]->addLiveIn(reg); 627193323Sed } 628193323Sed } 629193323Sed } 630193323Sed liveInMBBs.clear(); 631193323Sed } 632193323Sed } 633193323Sed } 634193323Sed 635193323Sed} 636193323Sed 637218893Sdimbool RegAllocPBQP::runOnMachineFunction(MachineFunction &MF) { 638193323Sed 639193323Sed mf = &MF; 640193323Sed tm = &mf->getTarget(); 641193323Sed tri = tm->getRegisterInfo(); 642193323Sed tii = tm->getInstrInfo(); 643198892Srdivacky mri = &mf->getRegInfo(); 644193323Sed 645193323Sed lis = &getAnalysis<LiveIntervals>(); 646193323Sed lss = &getAnalysis<LiveStacks>(); 647193323Sed loopInfo = &getAnalysis<MachineLoopInfo>(); 648212904Sdim rmf = &getAnalysis<RenderMachineFunction>(); 649193323Sed 650193323Sed vrm = &getAnalysis<VirtRegMap>(); 651193323Sed 652212904Sdim 653203954Srdivacky DEBUG(dbgs() << "PBQP Register Allocating for " << mf->getFunction()->getName() << "\n"); 654193323Sed 655193323Sed // Allocator main loop: 656193323Sed // 657193323Sed // * Map current regalloc problem to a PBQP problem 658193323Sed // * Solve the PBQP problem 659193323Sed // * Map the solution back to a register allocation 660193323Sed // * Spill if necessary 661193323Sed // 662193323Sed // This process is continued till no more spills are generated. 663193323Sed 664193323Sed // Find the vreg intervals in need of allocation. 665193323Sed findVRegIntervalsToAlloc(); 666193323Sed 667193323Sed // If there are non-empty intervals allocate them using pbqp. 668218893Sdim if (!vregsToAlloc.empty()) { 669193323Sed 670193323Sed bool pbqpAllocComplete = false; 671193323Sed unsigned round = 0; 672193323Sed 673193323Sed while (!pbqpAllocComplete) { 674202375Srdivacky DEBUG(dbgs() << " PBQP Regalloc round " << round << ":\n"); 675193323Sed 676218893Sdim std::auto_ptr<PBQPRAProblem> problem = 677218893Sdim builder->build(mf, lis, loopInfo, vregsToAlloc); 678203954Srdivacky PBQP::Solution solution = 679218893Sdim PBQP::HeuristicSolver<PBQP::Heuristics::Briggs>::solve( 680218893Sdim problem->getGraph()); 681193323Sed 682218893Sdim pbqpAllocComplete = mapPBQPToRegAlloc(*problem, solution); 683193323Sed 684193323Sed ++round; 685193323Sed } 686193323Sed } 687193323Sed 688193323Sed // Finalise allocation, allocate empty ranges. 689193323Sed finalizeAlloc(); 690193323Sed 691212904Sdim rmf->renderMachineFunction("After PBQP register allocation.", vrm); 692212904Sdim 693218893Sdim vregsToAlloc.clear(); 694218893Sdim emptyIntervalVRegs.clear(); 695193323Sed 696202375Srdivacky DEBUG(dbgs() << "Post alloc VirtRegMap:\n" << *vrm << "\n"); 697193323Sed 698193323Sed // Run rewriter 699193323Sed std::auto_ptr<VirtRegRewriter> rewriter(createVirtRegRewriter()); 700193323Sed 701193323Sed rewriter->runOnMachineFunction(*mf, *vrm, lis); 702193323Sed 703193323Sed return true; 704193323Sed} 705193323Sed 706218893SdimFunctionPass* llvm::createPBQPRegisterAllocator( 707218893Sdim std::auto_ptr<PBQPBuilder> builder) { 708218893Sdim return new RegAllocPBQP(builder); 709193323Sed} 710193323Sed 711218893SdimFunctionPass* llvm::createDefaultPBQPRegisterAllocator() { 712218893Sdim if (pbqpCoalescing) { 713218893Sdim return createPBQPRegisterAllocator( 714218893Sdim std::auto_ptr<PBQPBuilder>(new PBQPBuilderWithCoalescing())); 715218893Sdim } // else 716218893Sdim return createPBQPRegisterAllocator( 717218893Sdim std::auto_ptr<PBQPBuilder>(new PBQPBuilder())); 718218893Sdim} 719193323Sed 720193323Sed#undef DEBUG_TYPE 721