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