lib/CodeGen/RegAllocPBQP.cpp

   1 //===------ RegAllocPBQP.cpp ---- PBQP Register Allocator -------*- C++ -*-===//
   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 contains a Partitioned Boolean Quadratic Programming (PBQP) based
  11 // register allocator for LLVM. This allocator works by constructing a PBQP
  12 // problem representing the register allocation problem under consideration,
  13 // solving this using a PBQP solver, and mapping the solution back to a
  14 // register assignment. If any variables are selected for spilling then spill
  15 // code is inserted and the process repeated.
  16 //
  17 // The PBQP solver (pbqp.c) provided for this allocator uses a heuristic tuned
  18 // for register allocation. For more information on PBQP for register
  19 // allocation, see the following papers:
  20 //
  21 //   (1) Hames, L. and Scholz, B. 2006. Nearly optimal register allocation with
  22 //   PBQP. In Proceedings of the 7th Joint Modular Languages Conference
  23 //   (JMLC'06). LNCS, vol. 4228. Springer, New York, NY, USA. 346-361.
  24 //
  25 //   (2) Scholz, B., Eckstein, E. 2002. Register allocation for irregular
  26 //   architectures. In Proceedings of the Joint Conference on Languages,
  27 //   Compilers and Tools for Embedded Systems (LCTES'02), ACM Press, New York,
  28 //   NY, USA, 139-148.
  29 //
  30 //===----------------------------------------------------------------------===//
  31
  32 #include "llvm/CodeGen/RegAllocPBQP.h"
  33 #include "RegisterCoalescer.h"
  34 #include "Spiller.h"
  35 #include "llvm/Analysis/AliasAnalysis.h"
  36 #include "llvm/CodeGen/CalcSpillWeights.h"
  37 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
  38 #include "llvm/CodeGen/LiveRangeEdit.h"
  39 #include "llvm/CodeGen/LiveStackAnalysis.h"
  40 #include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
  41 #include "llvm/CodeGen/MachineDominators.h"
  42 #include "llvm/CodeGen/MachineFunctionPass.h"
  43 #include "llvm/CodeGen/MachineLoopInfo.h"
  44 #include "llvm/CodeGen/MachineRegisterInfo.h"
  45 #include "llvm/CodeGen/RegAllocRegistry.h"
  46 #include "llvm/CodeGen/VirtRegMap.h"
  47 #include "llvm/IR/Module.h"
  48 #include "llvm/Support/Debug.h"
  49 #include "llvm/Support/FileSystem.h"
  50 #include "llvm/Support/raw_ostream.h"
  51 #include "llvm/Target/TargetInstrInfo.h"
  52 #include "llvm/Target/TargetMachine.h"
  53 #include "llvm/Target/TargetSubtargetInfo.h"
  54 #include <limits>
  55 #include <memory>
  56 #include <set>
  57 #include <sstream>
  58 #include <vector>
  59
  60 using namespace llvm;
  61
  62 #define DEBUG_TYPE "regalloc"
  63
  64 static RegisterRegAlloc
  65 RegisterPBQPRepAlloc("pbqp", "PBQP register allocator",
  66                        createDefaultPBQPRegisterAllocator);
  67
  68 static cl::opt<bool>
  69 PBQPCoalescing("pbqp-coalescing",
  70                 cl::desc("Attempt coalescing during PBQP register allocation."),
  71                 cl::init(false), cl::Hidden);
  72
  73 #ifndef NDEBUG
  74 static cl::opt<bool>
  75 PBQPDumpGraphs("pbqp-dump-graphs",
  76                cl::desc("Dump graphs for each function/round in the compilation unit."),
  77                cl::init(false), cl::Hidden);
  78 #endif
  79
  80 namespace {
  81
  82 ///
  83 /// PBQP based allocators solve the register allocation problem by mapping
  84 /// register allocation problems to Partitioned Boolean Quadratic
  85 /// Programming problems.
  86 class RegAllocPBQP : public MachineFunctionPass {
  87 public:
  88
  89   static char ID;
  90
  91   /// Construct a PBQP register allocator.
  92   RegAllocPBQP(char *cPassID = nullptr)
  93       : MachineFunctionPass(ID), customPassID(cPassID) {
  94     initializeSlotIndexesPass(*PassRegistry::getPassRegistry());
  95     initializeLiveIntervalsPass(*PassRegistry::getPassRegistry());
  96     initializeLiveStacksPass(*PassRegistry::getPassRegistry());
  97     initializeVirtRegMapPass(*PassRegistry::getPassRegistry());
  98   }
  99
 100   /// Return the pass name.
 101   const char* getPassName() const override {
 102     return "PBQP Register Allocator";
 103   }
 104
 105   /// PBQP analysis usage.
 106   void getAnalysisUsage(AnalysisUsage &au) const override;
 107
 108   /// Perform register allocation
 109   bool runOnMachineFunction(MachineFunction &MF) override;
 110
 111 private:
 112
 113   typedef std::map<const LiveInterval*, unsigned> LI2NodeMap;
 114   typedef std::vector<const LiveInterval*> Node2LIMap;
 115   typedef std::vector<unsigned> AllowedSet;
 116   typedef std::vector<AllowedSet> AllowedSetMap;
 117   typedef std::pair<unsigned, unsigned> RegPair;
 118   typedef std::map<RegPair, PBQP::PBQPNum> CoalesceMap;
 119   typedef std::set<unsigned> RegSet;
 120
 121   char *customPassID;
 122
 123   RegSet VRegsToAlloc, EmptyIntervalVRegs;
 124
 125   /// \brief Finds the initial set of vreg intervals to allocate.
 126   void findVRegIntervalsToAlloc(const MachineFunction &MF, LiveIntervals &LIS);
 127
 128   /// \brief Constructs an initial graph.
 129   void initializeGraph(PBQPRAGraph &G);
 130
 131   /// \brief Given a solved PBQP problem maps this solution back to a register
 132   /// assignment.
 133   bool mapPBQPToRegAlloc(const PBQPRAGraph &G,
 134                          const PBQP::Solution &Solution,
 135                          VirtRegMap &VRM,
 136                          Spiller &VRegSpiller);
 137
 138   /// \brief Postprocessing before final spilling. Sets basic block "live in"
 139   /// variables.
 140   void finalizeAlloc(MachineFunction &MF, LiveIntervals &LIS,
 141                      VirtRegMap &VRM) const;
 142
 143 };
 144
 145 char RegAllocPBQP::ID = 0;
 146
 147 /// @brief Set spill costs for each node in the PBQP reg-alloc graph.
 148 class SpillCosts : public PBQPRAConstraint {
 149 public:
 150   void apply(PBQPRAGraph &G) override {
 151     LiveIntervals &LIS = G.getMetadata().LIS;
 152
 153     for (auto NId : G.nodeIds()) {
 154       PBQP::PBQPNum SpillCost =
 155         LIS.getInterval(G.getNodeMetadata(NId).getVReg()).weight;
 156       if (SpillCost == 0.0)
 157         SpillCost = std::numeric_limits<PBQP::PBQPNum>::min();
 158       PBQPRAGraph::RawVector NodeCosts(G.getNodeCosts(NId));
 159       NodeCosts[PBQP::RegAlloc::getSpillOptionIdx()] = SpillCost;
 160       G.setNodeCosts(NId, std::move(NodeCosts));
 161     }
 162   }
 163 };
 164
 165 /// @brief Add interference edges between overlapping vregs.
 166 class Interference : public PBQPRAConstraint {
 167 public:
 168
 169   void apply(PBQPRAGraph &G) override {
 170     LiveIntervals &LIS = G.getMetadata().LIS;
 171     const TargetRegisterInfo &TRI =
 172       *G.getMetadata().MF.getTarget().getSubtargetImpl()->getRegisterInfo();
 173
 174     for (auto NItr = G.nodeIds().begin(), NEnd = G.nodeIds().end();
 175          NItr != NEnd; ++NItr) {
 176       auto NId = *NItr;
 177       unsigned NVReg = G.getNodeMetadata(NId).getVReg();
 178       LiveInterval &NLI = LIS.getInterval(NVReg);
 179
 180       for (auto MItr = std::next(NItr); MItr != NEnd; ++MItr) {
 181         auto MId = *MItr;
 182         unsigned MVReg = G.getNodeMetadata(MId).getVReg();
 183         LiveInterval &MLI = LIS.getInterval(MVReg);
 184
 185         if (NLI.overlaps(MLI)) {
 186           const auto &NOpts = G.getNodeMetadata(NId).getOptionRegs();
 187           const auto &MOpts = G.getNodeMetadata(MId).getOptionRegs();
 188           G.addEdge(NId, MId, createInterferenceMatrix(TRI, NOpts, MOpts));
 189         }
 190       }
 191     }
 192   }
 193
 194 private:
 195
 196   PBQPRAGraph::RawMatrix createInterferenceMatrix(
 197                        const TargetRegisterInfo &TRI,
 198                        const PBQPRAGraph::NodeMetadata::OptionToRegMap &NOpts,
 199                        const PBQPRAGraph::NodeMetadata::OptionToRegMap &MOpts) {
 200     PBQPRAGraph::RawMatrix M(NOpts.size() + 1, MOpts.size() + 1, 0);
 201     for (unsigned I = 0; I != NOpts.size(); ++I) {
 202       unsigned PRegN = NOpts[I];
 203       for (unsigned J = 0; J != MOpts.size(); ++J) {
 204         unsigned PRegM = MOpts[J];
 205         if (TRI.regsOverlap(PRegN, PRegM))
 206           M[I + 1][J + 1] = std::numeric_limits<PBQP::PBQPNum>::infinity();
 207       }
 208     }
 209
 210     return M;
 211   }
 212 };
 213
 214
 215 class Coalescing : public PBQPRAConstraint {
 216 public:
 217   void apply(PBQPRAGraph &G) override {
 218     MachineFunction &MF = G.getMetadata().MF;
 219     MachineBlockFrequencyInfo &MBFI = G.getMetadata().MBFI;
 220     CoalescerPair CP(*MF.getTarget().getSubtargetImpl()->getRegisterInfo());
 221
 222     // Scan the machine function and add a coalescing cost whenever CoalescerPair
 223     // gives the Ok.
 224     for (const auto &MBB : MF) {
 225       for (const auto &MI : MBB) {
 226
 227         // Skip not-coalescable or already coalesced copies.
 228         if (!CP.setRegisters(&MI) || CP.getSrcReg() == CP.getDstReg())
 229           continue;
 230
 231         unsigned DstReg = CP.getDstReg();
 232         unsigned SrcReg = CP.getSrcReg();
 233
 234         const float CopyFactor = 0.5; // Cost of copy relative to load. Current
 235                                       // value plucked randomly out of the air.
 236
 237         PBQP::PBQPNum CBenefit =
 238           CopyFactor * LiveIntervals::getSpillWeight(false, true, &MBFI, &MI);
 239
 240         if (CP.isPhys()) {
 241           if (!MF.getRegInfo().isAllocatable(DstReg))
 242             continue;
 243
 244           PBQPRAGraph::NodeId NId = G.getMetadata().getNodeIdForVReg(SrcReg);
 245
 246           const PBQPRAGraph::NodeMetadata::OptionToRegMap &Allowed =
 247             G.getNodeMetadata(NId).getOptionRegs();
 248
 249           unsigned PRegOpt = 0;
 250           while (PRegOpt < Allowed.size() && Allowed[PRegOpt] != DstReg)
 251             ++PRegOpt;
 252
 253           if (PRegOpt < Allowed.size()) {
 254             PBQPRAGraph::RawVector NewCosts(G.getNodeCosts(NId));
 255             NewCosts[PRegOpt + 1] += CBenefit;
 256             G.setNodeCosts(NId, std::move(NewCosts));
 257           }
 258         } else {
 259           PBQPRAGraph::NodeId N1Id = G.getMetadata().getNodeIdForVReg(DstReg);
 260           PBQPRAGraph::NodeId N2Id = G.getMetadata().getNodeIdForVReg(SrcReg);
 261           const PBQPRAGraph::NodeMetadata::OptionToRegMap *Allowed1 =
 262             &G.getNodeMetadata(N1Id).getOptionRegs();
 263           const PBQPRAGraph::NodeMetadata::OptionToRegMap *Allowed2 =
 264             &G.getNodeMetadata(N2Id).getOptionRegs();
 265
 266           PBQPRAGraph::EdgeId EId = G.findEdge(N1Id, N2Id);
 267           if (EId == G.invalidEdgeId()) {
 268             PBQPRAGraph::RawMatrix Costs(Allowed1->size() + 1,
 269                                          Allowed2->size() + 1, 0);
 270             addVirtRegCoalesce(Costs, *Allowed1, *Allowed2, CBenefit);
 271             G.addEdge(N1Id, N2Id, std::move(Costs));
 272           } else {
 273             if (G.getEdgeNode1Id(EId) == N2Id) {
 274               std::swap(N1Id, N2Id);
 275               std::swap(Allowed1, Allowed2);
 276             }
 277             PBQPRAGraph::RawMatrix Costs(G.getEdgeCosts(EId));
 278             addVirtRegCoalesce(Costs, *Allowed1, *Allowed2, CBenefit);
 279             G.setEdgeCosts(EId, std::move(Costs));
 280           }
 281         }
 282       }
 283     }
 284   }
 285
 286 private:
 287
 288   void addVirtRegCoalesce(
 289                       PBQPRAGraph::RawMatrix &CostMat,
 290                       const PBQPRAGraph::NodeMetadata::OptionToRegMap &Allowed1,
 291                       const PBQPRAGraph::NodeMetadata::OptionToRegMap &Allowed2,
 292                       PBQP::PBQPNum Benefit) {
 293     assert(CostMat.getRows() == Allowed1.size() + 1 && "Size mismatch.");
 294     assert(CostMat.getCols() == Allowed2.size() + 1 && "Size mismatch.");
 295     for (unsigned I = 0; I != Allowed1.size(); ++I) {
 296       unsigned PReg1 = Allowed1[I];
 297       for (unsigned J = 0; J != Allowed2.size(); ++J) {
 298         unsigned PReg2 = Allowed2[J];
 299         if (PReg1 == PReg2)
 300           CostMat[I + 1][J + 1] += -Benefit;
 301       }
 302     }
 303   }
 304
 305 };
 306
 307 } // End anonymous namespace.
 308
 309 // Out-of-line destructor/anchor for PBQPRAConstraint.
 310 PBQPRAConstraint::~PBQPRAConstraint() {}
 311 void PBQPRAConstraint::anchor() {}
 312 void PBQPRAConstraintList::anchor() {}
 313
 314 void RegAllocPBQP::getAnalysisUsage(AnalysisUsage &au) const {
 315   au.setPreservesCFG();
 316   au.addRequired<AliasAnalysis>();
 317   au.addPreserved<AliasAnalysis>();
 318   au.addRequired<SlotIndexes>();
 319   au.addPreserved<SlotIndexes>();
 320   au.addRequired<LiveIntervals>();
 321   au.addPreserved<LiveIntervals>();
 322   //au.addRequiredID(SplitCriticalEdgesID);
 323   if (customPassID)
 324     au.addRequiredID(*customPassID);
 325   au.addRequired<LiveStacks>();
 326   au.addPreserved<LiveStacks>();
 327   au.addRequired<MachineBlockFrequencyInfo>();
 328   au.addPreserved<MachineBlockFrequencyInfo>();
 329   au.addRequired<MachineLoopInfo>();
 330   au.addPreserved<MachineLoopInfo>();
 331   au.addRequired<MachineDominatorTree>();
 332   au.addPreserved<MachineDominatorTree>();
 333   au.addRequired<VirtRegMap>();
 334   au.addPreserved<VirtRegMap>();
 335   MachineFunctionPass::getAnalysisUsage(au);
 336 }
 337
 338 void RegAllocPBQP::findVRegIntervalsToAlloc(const MachineFunction &MF,
 339                                             LiveIntervals &LIS) {
 340   const MachineRegisterInfo &MRI = MF.getRegInfo();
 341
 342   // Iterate over all live ranges.
 343   for (unsigned I = 0, E = MRI.getNumVirtRegs(); I != E; ++I) {
 344     unsigned Reg = TargetRegisterInfo::index2VirtReg(I);
 345     if (MRI.reg_nodbg_empty(Reg))
 346       continue;
 347     LiveInterval &LI = LIS.getInterval(Reg);
 348
 349     // If this live interval is non-empty we will use pbqp to allocate it.
 350     // Empty intervals we allocate in a simple post-processing stage in
 351     // finalizeAlloc.
 352     if (!LI.empty()) {
 353       VRegsToAlloc.insert(LI.reg);
 354     } else {
 355       EmptyIntervalVRegs.insert(LI.reg);
 356     }
 357   }
 358 }
 359
 360 void RegAllocPBQP::initializeGraph(PBQPRAGraph &G) {
 361   MachineFunction &MF = G.getMetadata().MF;
 362
 363   LiveIntervals &LIS = G.getMetadata().LIS;
 364   const MachineRegisterInfo &MRI = G.getMetadata().MF.getRegInfo();
 365   const TargetRegisterInfo &TRI =
 366     *G.getMetadata().MF.getTarget().getSubtargetImpl()->getRegisterInfo();
 367
 368   for (auto VReg : VRegsToAlloc) {
 369     const TargetRegisterClass *TRC = MRI.getRegClass(VReg);
 370     LiveInterval &VRegLI = LIS.getInterval(VReg);
 371
 372     // Record any overlaps with regmask operands.
 373     BitVector RegMaskOverlaps;
 374     LIS.checkRegMaskInterference(VRegLI, RegMaskOverlaps);
 375
 376     // Compute an initial allowed set for the current vreg.
 377     std::vector<unsigned> VRegAllowed;
 378     ArrayRef<MCPhysReg> RawPRegOrder = TRC->getRawAllocationOrder(MF);
 379     for (unsigned I = 0; I != RawPRegOrder.size(); ++I) {
 380       unsigned PReg = RawPRegOrder[I];
 381       if (MRI.isReserved(PReg))
 382         continue;
 383
 384       // vregLI crosses a regmask operand that clobbers preg.
 385       if (!RegMaskOverlaps.empty() && !RegMaskOverlaps.test(PReg))
 386         continue;
 387
 388       // vregLI overlaps fixed regunit interference.
 389       bool Interference = false;
 390       for (MCRegUnitIterator Units(PReg, &TRI); Units.isValid(); ++Units) {
 391         if (VRegLI.overlaps(LIS.getRegUnit(*Units))) {
 392           Interference = true;
 393           break;
 394         }
 395       }
 396       if (Interference)
 397         continue;
 398
 399       // preg is usable for this virtual register.
 400       VRegAllowed.push_back(PReg);
 401     }
 402
 403     PBQPRAGraph::RawVector NodeCosts(VRegAllowed.size() + 1, 0);
 404     PBQPRAGraph::NodeId NId = G.addNode(std::move(NodeCosts));
 405     G.getNodeMetadata(NId).setVReg(VReg);
 406     G.getNodeMetadata(NId).setOptionRegs(std::move(VRegAllowed));
 407     G.getMetadata().setNodeIdForVReg(VReg, NId);
 408   }
 409 }
 410
 411 bool RegAllocPBQP::mapPBQPToRegAlloc(const PBQPRAGraph &G,
 412                                      const PBQP::Solution &Solution,
 413                                      VirtRegMap &VRM,
 414                                      Spiller &VRegSpiller) {
 415   MachineFunction &MF = G.getMetadata().MF;
 416   LiveIntervals &LIS = G.getMetadata().LIS;
 417   const TargetRegisterInfo &TRI =
 418     *MF.getTarget().getSubtargetImpl()->getRegisterInfo();
 419   (void)TRI;
 420
 421   // Set to true if we have any spills
 422   bool AnotherRoundNeeded = false;
 423
 424   // Clear the existing allocation.
 425   VRM.clearAllVirt();
 426
 427   // Iterate over the nodes mapping the PBQP solution to a register
 428   // assignment.
 429   for (auto NId : G.nodeIds()) {
 430     unsigned VReg = G.getNodeMetadata(NId).getVReg();
 431     unsigned AllocOption = Solution.getSelection(NId);
 432
 433     if (AllocOption != PBQP::RegAlloc::getSpillOptionIdx()) {
 434       unsigned PReg = G.getNodeMetadata(NId).getOptionRegs()[AllocOption - 1];
 435       DEBUG(dbgs() << "VREG " << PrintReg(VReg, &TRI) << " -> "
 436             << TRI.getName(PReg) << "\n");
 437       assert(PReg != 0 && "Invalid preg selected.");
 438       VRM.assignVirt2Phys(VReg, PReg);
 439     } else {
 440       VRegsToAlloc.erase(VReg);
 441       SmallVector<unsigned, 8> NewSpills;
 442       LiveRangeEdit LRE(&LIS.getInterval(VReg), NewSpills, MF, LIS, &VRM);
 443       VRegSpiller.spill(LRE);
 444
 445       DEBUG(dbgs() << "VREG " << PrintReg(VReg, &TRI) << " -> SPILLED (Cost: "
 446                    << LRE.getParent().weight << ", New vregs: ");
 447
 448       // Copy any newly inserted live intervals into the list of regs to
 449       // allocate.
 450       for (LiveRangeEdit::iterator I = LRE.begin(), E = LRE.end();
 451            I != E; ++I) {
 452         LiveInterval &LI = LIS.getInterval(*I);
 453         assert(!LI.empty() && "Empty spill range.");
 454         DEBUG(dbgs() << PrintReg(LI.reg, &TRI) << " ");
 455         VRegsToAlloc.insert(LI.reg);
 456       }
 457
 458       DEBUG(dbgs() << ")\n");
 459
 460       // We need another round if spill intervals were added.
 461       AnotherRoundNeeded |= !LRE.empty();
 462     }
 463   }
 464
 465   return !AnotherRoundNeeded;
 466 }
 467
 468
 469 void RegAllocPBQP::finalizeAlloc(MachineFunction &MF,
 470                                  LiveIntervals &LIS,
 471                                  VirtRegMap &VRM) const {
 472   MachineRegisterInfo &MRI = MF.getRegInfo();
 473
 474   // First allocate registers for the empty intervals.
 475   for (RegSet::const_iterator
 476          I = EmptyIntervalVRegs.begin(), E = EmptyIntervalVRegs.end();
 477          I != E; ++I) {
 478     LiveInterval &LI = LIS.getInterval(*I);
 479
 480     unsigned PReg = MRI.getSimpleHint(LI.reg);
 481
 482     if (PReg == 0) {
 483       const TargetRegisterClass &RC = *MRI.getRegClass(LI.reg);
 484       PReg = RC.getRawAllocationOrder(MF).front();
 485     }
 486
 487     VRM.assignVirt2Phys(LI.reg, PReg);
 488   }
 489 }
 490
 491 bool RegAllocPBQP::runOnMachineFunction(MachineFunction &MF) {
 492   LiveIntervals &LIS = getAnalysis<LiveIntervals>();
 493   MachineBlockFrequencyInfo &MBFI =
 494     getAnalysis<MachineBlockFrequencyInfo>();
 495
 496   calculateSpillWeightsAndHints(LIS, MF, getAnalysis<MachineLoopInfo>(), MBFI);
 497
 498   VirtRegMap &VRM = getAnalysis<VirtRegMap>();
 499
 500   std::unique_ptr<Spiller> VRegSpiller(createInlineSpiller(*this, MF, VRM));
 501
 502   MF.getRegInfo().freezeReservedRegs(MF);
 503
 504   DEBUG(dbgs() << "PBQP Register Allocating for " << MF.getName() << "\n");
 505
 506   // Allocator main loop:
 507   //
 508   // * Map current regalloc problem to a PBQP problem
 509   // * Solve the PBQP problem
 510   // * Map the solution back to a register allocation
 511   // * Spill if necessary
 512   //
 513   // This process is continued till no more spills are generated.
 514
 515   // Find the vreg intervals in need of allocation.
 516   findVRegIntervalsToAlloc(MF, LIS);
 517
 518 #ifndef NDEBUG
 519   const Function &F = *MF.getFunction();
 520   std::string FullyQualifiedName =
 521     F.getParent()->getModuleIdentifier() + "." + F.getName().str();
 522 #endif
 523
 524   // If there are non-empty intervals allocate them using pbqp.
 525   if (!VRegsToAlloc.empty()) {
 526
 527     const TargetSubtargetInfo &Subtarget = *MF.getTarget().getSubtargetImpl();
 528     std::unique_ptr<PBQPRAConstraintList> ConstraintsRoot =
 529       llvm::make_unique<PBQPRAConstraintList>();
 530     ConstraintsRoot->addConstraint(llvm::make_unique<SpillCosts>());
 531     ConstraintsRoot->addConstraint(llvm::make_unique<Interference>());
 532     if (PBQPCoalescing)
 533       ConstraintsRoot->addConstraint(llvm::make_unique<Coalescing>());
 534     ConstraintsRoot->addConstraint(Subtarget.getCustomPBQPConstraints());
 535
 536     bool PBQPAllocComplete = false;
 537     unsigned Round = 0;
 538
 539     while (!PBQPAllocComplete) {
 540       DEBUG(dbgs() << "  PBQP Regalloc round " << Round << ":\n");
 541
 542       PBQPRAGraph G(PBQPRAGraph::GraphMetadata(MF, LIS, MBFI));
 543       initializeGraph(G);
 544       ConstraintsRoot->apply(G);
 545
 546 #ifndef NDEBUG
 547       if (PBQPDumpGraphs) {
 548         std::ostringstream RS;
 549         RS << Round;
 550         std::string GraphFileName = FullyQualifiedName + "." + RS.str() +
 551                                     ".pbqpgraph";
 552         std::error_code EC;
 553         raw_fd_ostream OS(GraphFileName, EC, sys::fs::F_Text);
 554         DEBUG(dbgs() << "Dumping graph for round " << Round << " to \""
 555               << GraphFileName << "\"\n");
 556         G.dumpToStream(OS);
 557       }
 558 #endif
 559
 560       PBQP::Solution Solution = PBQP::RegAlloc::solve(G);
 561       PBQPAllocComplete = mapPBQPToRegAlloc(G, Solution, VRM, *VRegSpiller);
 562       ++Round;
 563     }
 564   }
 565
 566   // Finalise allocation, allocate empty ranges.
 567   finalizeAlloc(MF, LIS, VRM);
 568   VRegsToAlloc.clear();
 569   EmptyIntervalVRegs.clear();
 570
 571   DEBUG(dbgs() << "Post alloc VirtRegMap:\n" << VRM << "\n");
 572
 573   return true;
 574 }
 575
 576 FunctionPass *llvm::createPBQPRegisterAllocator(char *customPassID) {
 577   return new RegAllocPBQP(customPassID);
 578 }
 579
 580 FunctionPass* llvm::createDefaultPBQPRegisterAllocator() {
 581   return createPBQPRegisterAllocator();
 582 }
 583
 584 #undef DEBUG_TYPE