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 34249423Sdim#include "llvm/CodeGen/RegAllocPBQP.h" 35249423Sdim#include "RegisterCoalescer.h" 36234353Sdim#include "Spiller.h" 37251662Sdim#include "llvm/ADT/OwningPtr.h" 38234353Sdim#include "llvm/Analysis/AliasAnalysis.h" 39200581Srdivacky#include "llvm/CodeGen/CalcSpillWeights.h" 40193323Sed#include "llvm/CodeGen/LiveIntervalAnalysis.h" 41234353Sdim#include "llvm/CodeGen/LiveRangeEdit.h" 42193323Sed#include "llvm/CodeGen/LiveStackAnalysis.h" 43263508Sdim#include "llvm/CodeGen/MachineBlockFrequencyInfo.h" 44234353Sdim#include "llvm/CodeGen/MachineDominators.h" 45193323Sed#include "llvm/CodeGen/MachineFunctionPass.h" 46193323Sed#include "llvm/CodeGen/MachineLoopInfo.h" 47193323Sed#include "llvm/CodeGen/MachineRegisterInfo.h" 48249423Sdim#include "llvm/CodeGen/PBQP/Graph.h" 49218893Sdim#include "llvm/CodeGen/PBQP/HeuristicSolver.h" 50218893Sdim#include "llvm/CodeGen/PBQP/Heuristics/Briggs.h" 51193323Sed#include "llvm/CodeGen/RegAllocRegistry.h" 52249423Sdim#include "llvm/CodeGen/VirtRegMap.h" 53249423Sdim#include "llvm/IR/Module.h" 54193323Sed#include "llvm/Support/Debug.h" 55198090Srdivacky#include "llvm/Support/raw_ostream.h" 56193323Sed#include "llvm/Target/TargetInstrInfo.h" 57193323Sed#include "llvm/Target/TargetMachine.h" 58193323Sed#include <limits> 59193323Sed#include <memory> 60193323Sed#include <set> 61234353Sdim#include <sstream> 62193323Sed#include <vector> 63193323Sed 64193323Sedusing namespace llvm; 65193323Sed 66193323Sedstatic RegisterRegAlloc 67204642SrdivackyregisterPBQPRepAlloc("pbqp", "PBQP register allocator", 68218893Sdim createDefaultPBQPRegisterAllocator); 69193323Sed 70198090Srdivackystatic cl::opt<bool> 71198090SrdivackypbqpCoalescing("pbqp-coalescing", 72203954Srdivacky cl::desc("Attempt coalescing during PBQP register allocation."), 73203954Srdivacky cl::init(false), cl::Hidden); 74198090Srdivacky 75234353Sdim#ifndef NDEBUG 76212904Sdimstatic cl::opt<bool> 77234353SdimpbqpDumpGraphs("pbqp-dump-graphs", 78234353Sdim cl::desc("Dump graphs for each function/round in the compilation unit."), 79234353Sdim cl::init(false), cl::Hidden); 80234353Sdim#endif 81212904Sdim 82193323Sednamespace { 83193323Sed 84218893Sdim/// 85218893Sdim/// PBQP based allocators solve the register allocation problem by mapping 86218893Sdim/// register allocation problems to Partitioned Boolean Quadratic 87218893Sdim/// Programming problems. 88218893Sdimclass RegAllocPBQP : public MachineFunctionPass { 89218893Sdimpublic: 90193323Sed 91218893Sdim static char ID; 92193323Sed 93218893Sdim /// Construct a PBQP register allocator. 94251662Sdim RegAllocPBQP(OwningPtr<PBQPBuilder> &b, char *cPassID=0) 95251662Sdim : MachineFunctionPass(ID), builder(b.take()), customPassID(cPassID) { 96218893Sdim initializeSlotIndexesPass(*PassRegistry::getPassRegistry()); 97218893Sdim initializeLiveIntervalsPass(*PassRegistry::getPassRegistry()); 98218893Sdim initializeLiveStacksPass(*PassRegistry::getPassRegistry()); 99218893Sdim initializeVirtRegMapPass(*PassRegistry::getPassRegistry()); 100218893Sdim } 101193323Sed 102218893Sdim /// Return the pass name. 103218893Sdim virtual const char* getPassName() const { 104218893Sdim return "PBQP Register Allocator"; 105218893Sdim } 106193323Sed 107218893Sdim /// PBQP analysis usage. 108218893Sdim virtual void getAnalysisUsage(AnalysisUsage &au) const; 109193323Sed 110218893Sdim /// Perform register allocation 111218893Sdim virtual bool runOnMachineFunction(MachineFunction &MF); 112193323Sed 113218893Sdimprivate: 114212904Sdim 115218893Sdim typedef std::map<const LiveInterval*, unsigned> LI2NodeMap; 116218893Sdim typedef std::vector<const LiveInterval*> Node2LIMap; 117218893Sdim typedef std::vector<unsigned> AllowedSet; 118218893Sdim typedef std::vector<AllowedSet> AllowedSetMap; 119218893Sdim typedef std::pair<unsigned, unsigned> RegPair; 120218893Sdim typedef std::map<RegPair, PBQP::PBQPNum> CoalesceMap; 121218893Sdim typedef std::set<unsigned> RegSet; 122212904Sdim 123193323Sed 124251662Sdim OwningPtr<PBQPBuilder> builder; 125193323Sed 126224145Sdim char *customPassID; 127224145Sdim 128218893Sdim MachineFunction *mf; 129218893Sdim const TargetMachine *tm; 130218893Sdim const TargetRegisterInfo *tri; 131218893Sdim const TargetInstrInfo *tii; 132218893Sdim MachineRegisterInfo *mri; 133263508Sdim const MachineBlockFrequencyInfo *mbfi; 134203954Srdivacky 135251662Sdim OwningPtr<Spiller> spiller; 136218893Sdim LiveIntervals *lis; 137218893Sdim LiveStacks *lss; 138218893Sdim VirtRegMap *vrm; 139193323Sed 140218893Sdim RegSet vregsToAlloc, emptyIntervalVRegs; 141193323Sed 142218893Sdim /// \brief Finds the initial set of vreg intervals to allocate. 143218893Sdim void findVRegIntervalsToAlloc(); 144193323Sed 145218893Sdim /// \brief Given a solved PBQP problem maps this solution back to a register 146218893Sdim /// assignment. 147218893Sdim bool mapPBQPToRegAlloc(const PBQPRAProblem &problem, 148218893Sdim const PBQP::Solution &solution); 149193323Sed 150218893Sdim /// \brief Postprocessing before final spilling. Sets basic block "live in" 151218893Sdim /// variables. 152218893Sdim void finalizeAlloc() const; 153193323Sed 154218893Sdim}; 155193323Sed 156218893Sdimchar RegAllocPBQP::ID = 0; 157193323Sed 158218893Sdim} // End anonymous namespace. 159193323Sed 160263508Sdimunsigned PBQPRAProblem::getVRegForNode(PBQP::Graph::NodeId node) const { 161218893Sdim Node2VReg::const_iterator vregItr = node2VReg.find(node); 162218893Sdim assert(vregItr != node2VReg.end() && "No vreg for node."); 163218893Sdim return vregItr->second; 164218893Sdim} 165193323Sed 166263508SdimPBQP::Graph::NodeId PBQPRAProblem::getNodeForVReg(unsigned vreg) const { 167218893Sdim VReg2Node::const_iterator nodeItr = vreg2Node.find(vreg); 168218893Sdim assert(nodeItr != vreg2Node.end() && "No node for vreg."); 169218893Sdim return nodeItr->second; 170234353Sdim 171218893Sdim} 172193323Sed 173218893Sdimconst PBQPRAProblem::AllowedSet& 174218893Sdim PBQPRAProblem::getAllowedSet(unsigned vreg) const { 175218893Sdim AllowedSetMap::const_iterator allowedSetItr = allowedSets.find(vreg); 176218893Sdim assert(allowedSetItr != allowedSets.end() && "No pregs for vreg."); 177218893Sdim const AllowedSet &allowedSet = allowedSetItr->second; 178218893Sdim return allowedSet; 179218893Sdim} 180193323Sed 181218893Sdimunsigned PBQPRAProblem::getPRegForOption(unsigned vreg, unsigned option) const { 182218893Sdim assert(isPRegOption(vreg, option) && "Not a preg option."); 183193323Sed 184218893Sdim const AllowedSet& allowedSet = getAllowedSet(vreg); 185218893Sdim assert(option <= allowedSet.size() && "Option outside allowed set."); 186218893Sdim return allowedSet[option - 1]; 187193323Sed} 188193323Sed 189251662SdimPBQPRAProblem *PBQPBuilder::build(MachineFunction *mf, const LiveIntervals *lis, 190263508Sdim const MachineBlockFrequencyInfo *mbfi, 191251662Sdim const RegSet &vregs) { 192193323Sed 193239462Sdim LiveIntervals *LIS = const_cast<LiveIntervals*>(lis); 194218893Sdim MachineRegisterInfo *mri = &mf->getRegInfo(); 195234353Sdim const TargetRegisterInfo *tri = mf->getTarget().getRegisterInfo(); 196193323Sed 197251662Sdim OwningPtr<PBQPRAProblem> p(new PBQPRAProblem()); 198218893Sdim PBQP::Graph &g = p->getGraph(); 199218893Sdim RegSet pregs; 200193323Sed 201218893Sdim // Collect the set of preg intervals, record that they're used in the MF. 202239462Sdim for (unsigned Reg = 1, e = tri->getNumRegs(); Reg != e; ++Reg) { 203239462Sdim if (mri->def_empty(Reg)) 204239462Sdim continue; 205239462Sdim pregs.insert(Reg); 206239462Sdim mri->setPhysRegUsed(Reg); 207218893Sdim } 208193323Sed 209234353Sdim // Iterate over vregs. 210218893Sdim for (RegSet::const_iterator vregItr = vregs.begin(), vregEnd = vregs.end(); 211218893Sdim vregItr != vregEnd; ++vregItr) { 212218893Sdim unsigned vreg = *vregItr; 213218893Sdim const TargetRegisterClass *trc = mri->getRegClass(vreg); 214239462Sdim LiveInterval *vregLI = &LIS->getInterval(vreg); 215193323Sed 216239462Sdim // Record any overlaps with regmask operands. 217243830Sdim BitVector regMaskOverlaps; 218239462Sdim LIS->checkRegMaskInterference(*vregLI, regMaskOverlaps); 219239462Sdim 220218893Sdim // Compute an initial allowed set for the current vreg. 221218893Sdim typedef std::vector<unsigned> VRAllowed; 222218893Sdim VRAllowed vrAllowed; 223234353Sdim ArrayRef<uint16_t> rawOrder = trc->getRawAllocationOrder(*mf); 224224145Sdim for (unsigned i = 0; i != rawOrder.size(); ++i) { 225224145Sdim unsigned preg = rawOrder[i]; 226243830Sdim if (mri->isReserved(preg)) 227239462Sdim continue; 228193323Sed 229239462Sdim // vregLI crosses a regmask operand that clobbers preg. 230239462Sdim if (!regMaskOverlaps.empty() && !regMaskOverlaps.test(preg)) 231218893Sdim continue; 232193323Sed 233239462Sdim // vregLI overlaps fixed regunit interference. 234239462Sdim bool Interference = false; 235239462Sdim for (MCRegUnitIterator Units(preg, tri); Units.isValid(); ++Units) { 236239462Sdim if (vregLI->overlaps(LIS->getRegUnit(*Units))) { 237239462Sdim Interference = true; 238239462Sdim break; 239234353Sdim } 240218893Sdim } 241239462Sdim if (Interference) 242239462Sdim continue; 243193323Sed 244239462Sdim // preg is usable for this virtual register. 245239462Sdim vrAllowed.push_back(preg); 246234353Sdim } 247234353Sdim 248218893Sdim // Construct the node. 249263508Sdim PBQP::Graph::NodeId node = 250218893Sdim g.addNode(PBQP::Vector(vrAllowed.size() + 1, 0)); 251193323Sed 252218893Sdim // Record the mapping and allowed set in the problem. 253218893Sdim p->recordVReg(vreg, node, vrAllowed.begin(), vrAllowed.end()); 254193323Sed 255218893Sdim PBQP::PBQPNum spillCost = (vregLI->weight != 0.0) ? 256218893Sdim vregLI->weight : std::numeric_limits<PBQP::PBQPNum>::min(); 257193323Sed 258218893Sdim addSpillCosts(g.getNodeCosts(node), spillCost); 259218893Sdim } 260193323Sed 261218893Sdim for (RegSet::const_iterator vr1Itr = vregs.begin(), vrEnd = vregs.end(); 262218893Sdim vr1Itr != vrEnd; ++vr1Itr) { 263218893Sdim unsigned vr1 = *vr1Itr; 264218893Sdim const LiveInterval &l1 = lis->getInterval(vr1); 265218893Sdim const PBQPRAProblem::AllowedSet &vr1Allowed = p->getAllowedSet(vr1); 266193323Sed 267218893Sdim for (RegSet::const_iterator vr2Itr = llvm::next(vr1Itr); 268218893Sdim vr2Itr != vrEnd; ++vr2Itr) { 269218893Sdim unsigned vr2 = *vr2Itr; 270218893Sdim const LiveInterval &l2 = lis->getInterval(vr2); 271218893Sdim const PBQPRAProblem::AllowedSet &vr2Allowed = p->getAllowedSet(vr2); 272193323Sed 273218893Sdim assert(!l2.empty() && "Empty interval in vreg set?"); 274218893Sdim if (l1.overlaps(l2)) { 275263508Sdim PBQP::Graph::EdgeId edge = 276218893Sdim g.addEdge(p->getNodeForVReg(vr1), p->getNodeForVReg(vr2), 277218893Sdim PBQP::Matrix(vr1Allowed.size()+1, vr2Allowed.size()+1, 0)); 278218893Sdim 279218893Sdim addInterferenceCosts(g.getEdgeCosts(edge), vr1Allowed, vr2Allowed, tri); 280193323Sed } 281193323Sed } 282193323Sed } 283193323Sed 284251662Sdim return p.take(); 285218893Sdim} 286193323Sed 287218893Sdimvoid PBQPBuilder::addSpillCosts(PBQP::Vector &costVec, 288218893Sdim PBQP::PBQPNum spillCost) { 289218893Sdim costVec[0] = spillCost; 290193323Sed} 291193323Sed 292218893Sdimvoid PBQPBuilder::addInterferenceCosts( 293218893Sdim PBQP::Matrix &costMat, 294218893Sdim const PBQPRAProblem::AllowedSet &vr1Allowed, 295218893Sdim const PBQPRAProblem::AllowedSet &vr2Allowed, 296218893Sdim const TargetRegisterInfo *tri) { 297218893Sdim assert(costMat.getRows() == vr1Allowed.size() + 1 && "Matrix height mismatch."); 298218893Sdim assert(costMat.getCols() == vr2Allowed.size() + 1 && "Matrix width mismatch."); 299193323Sed 300218893Sdim for (unsigned i = 0; i != vr1Allowed.size(); ++i) { 301218893Sdim unsigned preg1 = vr1Allowed[i]; 302193323Sed 303218893Sdim for (unsigned j = 0; j != vr2Allowed.size(); ++j) { 304218893Sdim unsigned preg2 = vr2Allowed[j]; 305193323Sed 306218893Sdim if (tri->regsOverlap(preg1, preg2)) { 307218893Sdim costMat[i + 1][j + 1] = std::numeric_limits<PBQP::PBQPNum>::infinity(); 308193323Sed } 309193323Sed } 310193323Sed } 311193323Sed} 312193323Sed 313251662SdimPBQPRAProblem *PBQPBuilderWithCoalescing::build(MachineFunction *mf, 314218893Sdim const LiveIntervals *lis, 315263508Sdim const MachineBlockFrequencyInfo *mbfi, 316218893Sdim const RegSet &vregs) { 317193323Sed 318263508Sdim OwningPtr<PBQPRAProblem> p(PBQPBuilder::build(mf, lis, mbfi, vregs)); 319218893Sdim PBQP::Graph &g = p->getGraph(); 320193323Sed 321218893Sdim const TargetMachine &tm = mf->getTarget(); 322239462Sdim CoalescerPair cp(*tm.getRegisterInfo()); 323193323Sed 324218893Sdim // Scan the machine function and add a coalescing cost whenever CoalescerPair 325218893Sdim // gives the Ok. 326218893Sdim for (MachineFunction::const_iterator mbbItr = mf->begin(), 327218893Sdim mbbEnd = mf->end(); 328218893Sdim mbbItr != mbbEnd; ++mbbItr) { 329218893Sdim const MachineBasicBlock *mbb = &*mbbItr; 330193323Sed 331218893Sdim for (MachineBasicBlock::const_iterator miItr = mbb->begin(), 332218893Sdim miEnd = mbb->end(); 333218893Sdim miItr != miEnd; ++miItr) { 334218893Sdim const MachineInstr *mi = &*miItr; 335193323Sed 336218893Sdim if (!cp.setRegisters(mi)) { 337218893Sdim continue; // Not coalescable. 338218893Sdim } 339193323Sed 340218893Sdim if (cp.getSrcReg() == cp.getDstReg()) { 341218893Sdim continue; // Already coalesced. 342218893Sdim } 343193323Sed 344218893Sdim unsigned dst = cp.getDstReg(), 345218893Sdim src = cp.getSrcReg(); 346193323Sed 347218893Sdim const float copyFactor = 0.5; // Cost of copy relative to load. Current 348218893Sdim // value plucked randomly out of the air. 349234353Sdim 350218893Sdim PBQP::PBQPNum cBenefit = 351218893Sdim copyFactor * LiveIntervals::getSpillWeight(false, true, 352263508Sdim mbfi->getBlockFreq(mbb)); 353212904Sdim 354218893Sdim if (cp.isPhys()) { 355243830Sdim if (!mf->getRegInfo().isAllocatable(dst)) { 356193323Sed continue; 357218893Sdim } 358193323Sed 359218893Sdim const PBQPRAProblem::AllowedSet &allowed = p->getAllowedSet(src); 360234353Sdim unsigned pregOpt = 0; 361218893Sdim while (pregOpt < allowed.size() && allowed[pregOpt] != dst) { 362218893Sdim ++pregOpt; 363218893Sdim } 364218893Sdim if (pregOpt < allowed.size()) { 365218893Sdim ++pregOpt; // +1 to account for spill option. 366263508Sdim PBQP::Graph::NodeId node = p->getNodeForVReg(src); 367218893Sdim addPhysRegCoalesce(g.getNodeCosts(node), pregOpt, cBenefit); 368218893Sdim } 369218893Sdim } else { 370218893Sdim const PBQPRAProblem::AllowedSet *allowed1 = &p->getAllowedSet(dst); 371218893Sdim const PBQPRAProblem::AllowedSet *allowed2 = &p->getAllowedSet(src); 372263508Sdim PBQP::Graph::NodeId node1 = p->getNodeForVReg(dst); 373263508Sdim PBQP::Graph::NodeId node2 = p->getNodeForVReg(src); 374263508Sdim PBQP::Graph::EdgeId edge = g.findEdge(node1, node2); 375263508Sdim if (edge == g.invalidEdgeId()) { 376218893Sdim edge = g.addEdge(node1, node2, PBQP::Matrix(allowed1->size() + 1, 377218893Sdim allowed2->size() + 1, 378218893Sdim 0)); 379218893Sdim } else { 380218893Sdim if (g.getEdgeNode1(edge) == node2) { 381218893Sdim std::swap(node1, node2); 382218893Sdim std::swap(allowed1, allowed2); 383203954Srdivacky } 384193323Sed } 385234353Sdim 386218893Sdim addVirtRegCoalesce(g.getEdgeCosts(edge), *allowed1, *allowed2, 387218893Sdim cBenefit); 388218893Sdim } 389218893Sdim } 390218893Sdim } 391193323Sed 392251662Sdim return p.take(); 393218893Sdim} 394193323Sed 395218893Sdimvoid PBQPBuilderWithCoalescing::addPhysRegCoalesce(PBQP::Vector &costVec, 396218893Sdim unsigned pregOption, 397218893Sdim PBQP::PBQPNum benefit) { 398218893Sdim costVec[pregOption] += -benefit; 399218893Sdim} 400193323Sed 401218893Sdimvoid PBQPBuilderWithCoalescing::addVirtRegCoalesce( 402218893Sdim PBQP::Matrix &costMat, 403218893Sdim const PBQPRAProblem::AllowedSet &vr1Allowed, 404218893Sdim const PBQPRAProblem::AllowedSet &vr2Allowed, 405218893Sdim PBQP::PBQPNum benefit) { 406193323Sed 407218893Sdim assert(costMat.getRows() == vr1Allowed.size() + 1 && "Size mismatch."); 408218893Sdim assert(costMat.getCols() == vr2Allowed.size() + 1 && "Size mismatch."); 409203954Srdivacky 410218893Sdim for (unsigned i = 0; i != vr1Allowed.size(); ++i) { 411218893Sdim unsigned preg1 = vr1Allowed[i]; 412218893Sdim for (unsigned j = 0; j != vr2Allowed.size(); ++j) { 413218893Sdim unsigned preg2 = vr2Allowed[j]; 414193323Sed 415218893Sdim if (preg1 == preg2) { 416218893Sdim costMat[i + 1][j + 1] += -benefit; 417234353Sdim } 418193323Sed } 419193323Sed } 420218893Sdim} 421193323Sed 422218893Sdim 423218893Sdimvoid RegAllocPBQP::getAnalysisUsage(AnalysisUsage &au) const { 424234353Sdim au.setPreservesCFG(); 425234353Sdim au.addRequired<AliasAnalysis>(); 426234353Sdim au.addPreserved<AliasAnalysis>(); 427218893Sdim au.addRequired<SlotIndexes>(); 428218893Sdim au.addPreserved<SlotIndexes>(); 429218893Sdim au.addRequired<LiveIntervals>(); 430243830Sdim au.addPreserved<LiveIntervals>(); 431218893Sdim //au.addRequiredID(SplitCriticalEdgesID); 432224145Sdim if (customPassID) 433224145Sdim au.addRequiredID(*customPassID); 434218893Sdim au.addRequired<LiveStacks>(); 435218893Sdim au.addPreserved<LiveStacks>(); 436263508Sdim au.addRequired<MachineBlockFrequencyInfo>(); 437263508Sdim au.addPreserved<MachineBlockFrequencyInfo>(); 438263508Sdim au.addRequired<MachineLoopInfo>(); 439263508Sdim au.addPreserved<MachineLoopInfo>(); 440234353Sdim au.addRequired<MachineDominatorTree>(); 441234353Sdim au.addPreserved<MachineDominatorTree>(); 442218893Sdim au.addRequired<VirtRegMap>(); 443243830Sdim au.addPreserved<VirtRegMap>(); 444218893Sdim MachineFunctionPass::getAnalysisUsage(au); 445193323Sed} 446193323Sed 447218893Sdimvoid RegAllocPBQP::findVRegIntervalsToAlloc() { 448193323Sed 449193323Sed // Iterate over all live ranges. 450239462Sdim for (unsigned i = 0, e = mri->getNumVirtRegs(); i != e; ++i) { 451239462Sdim unsigned Reg = TargetRegisterInfo::index2VirtReg(i); 452239462Sdim if (mri->reg_nodbg_empty(Reg)) 453193323Sed continue; 454239462Sdim LiveInterval *li = &lis->getInterval(Reg); 455193323Sed 456193323Sed // If this live interval is non-empty we will use pbqp to allocate it. 457193323Sed // Empty intervals we allocate in a simple post-processing stage in 458193323Sed // finalizeAlloc. 459193323Sed if (!li->empty()) { 460218893Sdim vregsToAlloc.insert(li->reg); 461218893Sdim } else { 462218893Sdim emptyIntervalVRegs.insert(li->reg); 463193323Sed } 464193323Sed } 465193323Sed} 466193323Sed 467218893Sdimbool RegAllocPBQP::mapPBQPToRegAlloc(const PBQPRAProblem &problem, 468218893Sdim const PBQP::Solution &solution) { 469193323Sed // Set to true if we have any spills 470193323Sed bool anotherRoundNeeded = false; 471193323Sed 472193323Sed // Clear the existing allocation. 473193323Sed vrm->clearAllVirt(); 474193323Sed 475218893Sdim const PBQP::Graph &g = problem.getGraph(); 476218893Sdim // Iterate over the nodes mapping the PBQP solution to a register 477218893Sdim // assignment. 478263508Sdim for (PBQP::Graph::NodeItr nodeItr = g.nodesBegin(), 479263508Sdim nodeEnd = g.nodesEnd(); 480263508Sdim nodeItr != nodeEnd; ++nodeItr) { 481263508Sdim unsigned vreg = problem.getVRegForNode(*nodeItr); 482263508Sdim unsigned alloc = solution.getSelection(*nodeItr); 483193323Sed 484218893Sdim if (problem.isPRegOption(vreg, alloc)) { 485234353Sdim unsigned preg = problem.getPRegForOption(vreg, alloc); 486239462Sdim DEBUG(dbgs() << "VREG " << PrintReg(vreg, tri) << " -> " 487239462Sdim << tri->getName(preg) << "\n"); 488218893Sdim assert(preg != 0 && "Invalid preg selected."); 489234353Sdim vrm->assignVirt2Phys(vreg, preg); 490218893Sdim } else if (problem.isSpillOption(vreg, alloc)) { 491218893Sdim vregsToAlloc.erase(vreg); 492263508Sdim SmallVector<unsigned, 8> newSpills; 493239462Sdim LiveRangeEdit LRE(&lis->getInterval(vreg), newSpills, *mf, *lis, vrm); 494234353Sdim spiller->spill(LRE); 495193323Sed 496239462Sdim DEBUG(dbgs() << "VREG " << PrintReg(vreg, tri) << " -> SPILLED (Cost: " 497234353Sdim << LRE.getParent().weight << ", New vregs: "); 498193323Sed 499193323Sed // Copy any newly inserted live intervals into the list of regs to 500193323Sed // allocate. 501234353Sdim for (LiveRangeEdit::iterator itr = LRE.begin(), end = LRE.end(); 502193323Sed itr != end; ++itr) { 503263508Sdim LiveInterval &li = lis->getInterval(*itr); 504263508Sdim assert(!li.empty() && "Empty spill range."); 505263508Sdim DEBUG(dbgs() << PrintReg(li.reg, tri) << " "); 506263508Sdim vregsToAlloc.insert(li.reg); 507193323Sed } 508193323Sed 509202375Srdivacky DEBUG(dbgs() << ")\n"); 510193323Sed 511193323Sed // We need another round if spill intervals were added. 512234353Sdim anotherRoundNeeded |= !LRE.empty(); 513218893Sdim } else { 514234353Sdim llvm_unreachable("Unknown allocation option."); 515193323Sed } 516193323Sed } 517193323Sed 518193323Sed return !anotherRoundNeeded; 519193323Sed} 520193323Sed 521218893Sdim 522218893Sdimvoid RegAllocPBQP::finalizeAlloc() const { 523193323Sed // First allocate registers for the empty intervals. 524218893Sdim for (RegSet::const_iterator 525218893Sdim itr = emptyIntervalVRegs.begin(), end = emptyIntervalVRegs.end(); 526193323Sed itr != end; ++itr) { 527218893Sdim LiveInterval *li = &lis->getInterval(*itr); 528193323Sed 529249423Sdim unsigned physReg = mri->getSimpleHint(li->reg); 530198090Srdivacky 531193323Sed if (physReg == 0) { 532193323Sed const TargetRegisterClass *liRC = mri->getRegClass(li->reg); 533224145Sdim physReg = liRC->getRawAllocationOrder(*mf).front(); 534193323Sed } 535193323Sed 536193323Sed vrm->assignVirt2Phys(li->reg, physReg); 537193323Sed } 538193323Sed} 539193323Sed 540218893Sdimbool RegAllocPBQP::runOnMachineFunction(MachineFunction &MF) { 541193323Sed 542193323Sed mf = &MF; 543193323Sed tm = &mf->getTarget(); 544193323Sed tri = tm->getRegisterInfo(); 545193323Sed tii = tm->getInstrInfo(); 546234353Sdim mri = &mf->getRegInfo(); 547193323Sed 548193323Sed lis = &getAnalysis<LiveIntervals>(); 549193323Sed lss = &getAnalysis<LiveStacks>(); 550263508Sdim mbfi = &getAnalysis<MachineBlockFrequencyInfo>(); 551193323Sed 552263508Sdim calculateSpillWeightsAndHints(*lis, MF, getAnalysis<MachineLoopInfo>(), 553263508Sdim *mbfi); 554263508Sdim 555193323Sed vrm = &getAnalysis<VirtRegMap>(); 556234353Sdim spiller.reset(createInlineSpiller(*this, MF, *vrm)); 557193323Sed 558234353Sdim mri->freezeReservedRegs(MF); 559212904Sdim 560243830Sdim DEBUG(dbgs() << "PBQP Register Allocating for " << mf->getName() << "\n"); 561193323Sed 562193323Sed // Allocator main loop: 563193323Sed // 564193323Sed // * Map current regalloc problem to a PBQP problem 565193323Sed // * Solve the PBQP problem 566193323Sed // * Map the solution back to a register allocation 567193323Sed // * Spill if necessary 568193323Sed // 569193323Sed // This process is continued till no more spills are generated. 570193323Sed 571193323Sed // Find the vreg intervals in need of allocation. 572193323Sed findVRegIntervalsToAlloc(); 573193323Sed 574243830Sdim#ifndef NDEBUG 575234353Sdim const Function* func = mf->getFunction(); 576234353Sdim std::string fqn = 577234353Sdim func->getParent()->getModuleIdentifier() + "." + 578234353Sdim func->getName().str(); 579243830Sdim#endif 580234353Sdim 581193323Sed // If there are non-empty intervals allocate them using pbqp. 582218893Sdim if (!vregsToAlloc.empty()) { 583193323Sed 584193323Sed bool pbqpAllocComplete = false; 585193323Sed unsigned round = 0; 586193323Sed 587193323Sed while (!pbqpAllocComplete) { 588202375Srdivacky DEBUG(dbgs() << " PBQP Regalloc round " << round << ":\n"); 589193323Sed 590251662Sdim OwningPtr<PBQPRAProblem> problem( 591263508Sdim builder->build(mf, lis, mbfi, vregsToAlloc)); 592234353Sdim 593234353Sdim#ifndef NDEBUG 594234353Sdim if (pbqpDumpGraphs) { 595234353Sdim std::ostringstream rs; 596234353Sdim rs << round; 597234353Sdim std::string graphFileName(fqn + "." + rs.str() + ".pbqpgraph"); 598234353Sdim std::string tmp; 599234353Sdim raw_fd_ostream os(graphFileName.c_str(), tmp); 600234353Sdim DEBUG(dbgs() << "Dumping graph for round " << round << " to \"" 601234353Sdim << graphFileName << "\"\n"); 602234353Sdim problem->getGraph().dump(os); 603234353Sdim } 604234353Sdim#endif 605234353Sdim 606203954Srdivacky PBQP::Solution solution = 607218893Sdim PBQP::HeuristicSolver<PBQP::Heuristics::Briggs>::solve( 608218893Sdim problem->getGraph()); 609193323Sed 610218893Sdim pbqpAllocComplete = mapPBQPToRegAlloc(*problem, solution); 611193323Sed 612193323Sed ++round; 613193323Sed } 614193323Sed } 615193323Sed 616193323Sed // Finalise allocation, allocate empty ranges. 617193323Sed finalizeAlloc(); 618218893Sdim vregsToAlloc.clear(); 619218893Sdim emptyIntervalVRegs.clear(); 620193323Sed 621202375Srdivacky DEBUG(dbgs() << "Post alloc VirtRegMap:\n" << *vrm << "\n"); 622193323Sed 623193323Sed return true; 624193323Sed} 625193323Sed 626218893SdimFunctionPass* llvm::createPBQPRegisterAllocator( 627251662Sdim OwningPtr<PBQPBuilder> &builder, 628224145Sdim char *customPassID) { 629224145Sdim return new RegAllocPBQP(builder, customPassID); 630193323Sed} 631193323Sed 632218893SdimFunctionPass* llvm::createDefaultPBQPRegisterAllocator() { 633251662Sdim OwningPtr<PBQPBuilder> Builder; 634251662Sdim if (pbqpCoalescing) 635251662Sdim Builder.reset(new PBQPBuilderWithCoalescing()); 636251662Sdim else 637251662Sdim Builder.reset(new PBQPBuilder()); 638251662Sdim return createPBQPRegisterAllocator(Builder); 639218893Sdim} 640193323Sed 641193323Sed#undef DEBUG_TYPE 642