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 #define DEBUG_TYPE "regalloc"
  33
  34 #include "PBQP/HeuristicSolver.h"
  35 #include "PBQP/Graph.h"
  36 #include "PBQP/Heuristics/Briggs.h"
  37 #include "RenderMachineFunction.h"
  38 #include "Splitter.h"
  39 #include "VirtRegMap.h"
  40 #include "VirtRegRewriter.h"
  41 #include "llvm/CodeGen/CalcSpillWeights.h"
  42 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
  43 #include "llvm/CodeGen/LiveStackAnalysis.h"
  44 #include "llvm/CodeGen/MachineFunctionPass.h"
  45 #include "llvm/CodeGen/MachineLoopInfo.h"
  46 #include "llvm/CodeGen/MachineRegisterInfo.h"
  47 #include "llvm/CodeGen/RegAllocRegistry.h"
  48 #include "llvm/CodeGen/RegisterCoalescer.h"
  49 #include "llvm/Support/Debug.h"
  50 #include "llvm/Support/raw_ostream.h"
  51 #include "llvm/Target/TargetInstrInfo.h"
  52 #include "llvm/Target/TargetMachine.h"
  53 #include <limits>
  54 #include <map>
  55 #include <memory>
  56 #include <set>
  57 #include <vector>
  58
  59 using namespace llvm;
  60
  61 static RegisterRegAlloc
  62 registerPBQPRepAlloc("pbqp", "PBQP register allocator",
  63                        llvm::createPBQPRegisterAllocator);
  64
  65 static cl::opt<bool>
  66 pbqpCoalescing("pbqp-coalescing",
  67                 cl::desc("Attempt coalescing during PBQP register allocation."),
  68                 cl::init(false), cl::Hidden);
  69
  70 static cl::opt<bool>
  71 pbqpPreSplitting("pbqp-pre-splitting",
  72                  cl::desc("Pre-splite before PBQP register allocation."),
  73                  cl::init(false), cl::Hidden);
  74
  75 namespace {
  76
  77   ///
  78   /// PBQP based allocators solve the register allocation problem by mapping
  79   /// register allocation problems to Partitioned Boolean Quadratic
  80   /// Programming problems.
  81   class PBQPRegAlloc : public MachineFunctionPass {
  82   public:
  83
  84     static char ID;
  85
  86     /// Construct a PBQP register allocator.
  87     PBQPRegAlloc() : MachineFunctionPass(ID) {}
  88
  89     /// Return the pass name.
  90     virtual const char* getPassName() const {
  91       return "PBQP Register Allocator";
  92     }
  93
  94     /// PBQP analysis usage.
  95     virtual void getAnalysisUsage(AnalysisUsage &au) const {
  96       au.addRequired<SlotIndexes>();
  97       au.addPreserved<SlotIndexes>();
  98       au.addRequired<LiveIntervals>();
  99       //au.addRequiredID(SplitCriticalEdgesID);
 100       au.addRequired<RegisterCoalescer>();
 101       au.addRequired<CalculateSpillWeights>();
 102       au.addRequired<LiveStacks>();
 103       au.addPreserved<LiveStacks>();
 104       au.addRequired<MachineLoopInfo>();
 105       au.addPreserved<MachineLoopInfo>();
 106       if (pbqpPreSplitting)
 107         au.addRequired<LoopSplitter>();
 108       au.addRequired<VirtRegMap>();
 109       au.addRequired<RenderMachineFunction>();
 110       MachineFunctionPass::getAnalysisUsage(au);
 111     }
 112
 113     /// Perform register allocation
 114     virtual bool runOnMachineFunction(MachineFunction &MF);
 115
 116   private:
 117
 118     class LIOrdering {
 119     public:
 120       bool operator()(const LiveInterval *li1, const LiveInterval *li2) const {
 121         return li1->reg < li2->reg;
 122       }
 123     };
 124
 125     typedef std::map<const LiveInterval*, unsigned, LIOrdering> LI2NodeMap;
 126     typedef std::vector<const LiveInterval*> Node2LIMap;
 127     typedef std::vector<unsigned> AllowedSet;
 128     typedef std::vector<AllowedSet> AllowedSetMap;
 129     typedef std::set<unsigned> RegSet;
 130     typedef std::pair<unsigned, unsigned> RegPair;
 131     typedef std::map<RegPair, PBQP::PBQPNum> CoalesceMap;
 132
 133     typedef std::set<LiveInterval*, LIOrdering> LiveIntervalSet;
 134
 135     typedef std::vector<PBQP::Graph::NodeItr> NodeVector;
 136
 137     MachineFunction *mf;
 138     const TargetMachine *tm;
 139     const TargetRegisterInfo *tri;
 140     const TargetInstrInfo *tii;
 141     const MachineLoopInfo *loopInfo;
 142     MachineRegisterInfo *mri;
 143     RenderMachineFunction *rmf;
 144
 145     LiveIntervals *lis;
 146     LiveStacks *lss;
 147     VirtRegMap *vrm;
 148
 149     LI2NodeMap li2Node;
 150     Node2LIMap node2LI;
 151     AllowedSetMap allowedSets;
 152     LiveIntervalSet vregIntervalsToAlloc,
 153                     emptyVRegIntervals;
 154     NodeVector problemNodes;
 155
 156
 157     /// Builds a PBQP cost vector.
 158     template <typename RegContainer>
 159     PBQP::Vector buildCostVector(unsigned vReg,
 160                                  const RegContainer &allowed,
 161                                  const CoalesceMap &cealesces,
 162                                  PBQP::PBQPNum spillCost) const;
 163
 164     /// \brief Builds a PBQP interference matrix.
 165     ///
 166     /// @return Either a pointer to a non-zero PBQP matrix representing the
 167     ///         allocation option costs, or a null pointer for a zero matrix.
 168     ///
 169     /// Expects allowed sets for two interfering LiveIntervals. These allowed
 170     /// sets should contain only allocable registers from the LiveInterval's
 171     /// register class, with any interfering pre-colored registers removed.
 172     template <typename RegContainer>
 173     PBQP::Matrix* buildInterferenceMatrix(const RegContainer &allowed1,
 174                                           const RegContainer &allowed2) const;
 175
 176     ///
 177     /// Expects allowed sets for two potentially coalescable LiveIntervals,
 178     /// and an estimated benefit due to coalescing. The allowed sets should
 179     /// contain only allocable registers from the LiveInterval's register
 180     /// classes, with any interfering pre-colored registers removed.
 181     template <typename RegContainer>
 182     PBQP::Matrix* buildCoalescingMatrix(const RegContainer &allowed1,
 183                                         const RegContainer &allowed2,
 184                                         PBQP::PBQPNum cBenefit) const;
 185
 186     /// \brief Finds coalescing opportunities and returns them as a map.
 187     ///
 188     /// Any entries in the map are guaranteed coalescable, even if their
 189     /// corresponding live intervals overlap.
 190     CoalesceMap findCoalesces();
 191
 192     /// \brief Finds the initial set of vreg intervals to allocate.
 193     void findVRegIntervalsToAlloc();
 194
 195     /// \brief Constructs a PBQP problem representation of the register
 196     /// allocation problem for this function.
 197     ///
 198     /// @return a PBQP solver object for the register allocation problem.
 199     PBQP::Graph constructPBQPProblem();
 200
 201     /// \brief Adds a stack interval if the given live interval has been
 202     /// spilled. Used to support stack slot coloring.
 203     void addStackInterval(const LiveInterval *spilled,MachineRegisterInfo* mri);
 204
 205     /// \brief Given a solved PBQP problem maps this solution back to a register
 206     /// assignment.
 207     bool mapPBQPToRegAlloc(const PBQP::Solution &solution);
 208
 209     /// \brief Postprocessing before final spilling. Sets basic block "live in"
 210     /// variables.
 211     void finalizeAlloc() const;
 212
 213   };
 214
 215   char PBQPRegAlloc::ID = 0;
 216 }
 217
 218
 219 template <typename RegContainer>
 220 PBQP::Vector PBQPRegAlloc::buildCostVector(unsigned vReg,
 221                                            const RegContainer &allowed,
 222                                            const CoalesceMap &coalesces,
 223                                            PBQP::PBQPNum spillCost) const {
 224
 225   typedef typename RegContainer::const_iterator AllowedItr;
 226
 227   // Allocate vector. Additional element (0th) used for spill option
 228   PBQP::Vector v(allowed.size() + 1, 0);
 229
 230   v[0] = spillCost;
 231
 232   // Iterate over the allowed registers inserting coalesce benefits if there
 233   // are any.
 234   unsigned ai = 0;
 235   for (AllowedItr itr = allowed.begin(), end = allowed.end();
 236        itr != end; ++itr, ++ai) {
 237
 238     unsigned pReg = *itr;
 239
 240     CoalesceMap::const_iterator cmItr =
 241       coalesces.find(RegPair(vReg, pReg));
 242
 243     // No coalesce - on to the next preg.
 244     if (cmItr == coalesces.end())
 245       continue;
 246
 247     // We have a coalesce - insert the benefit.
 248     v[ai + 1] = -cmItr->second;
 249   }
 250
 251   return v;
 252 }
 253
 254 template <typename RegContainer>
 255 PBQP::Matrix* PBQPRegAlloc::buildInterferenceMatrix(
 256       const RegContainer &allowed1, const RegContainer &allowed2) const {
 257
 258   typedef typename RegContainer::const_iterator RegContainerIterator;
 259
 260   // Construct a PBQP matrix representing the cost of allocation options. The
 261   // rows and columns correspond to the allocation options for the two live
 262   // intervals.  Elements will be infinite where corresponding registers alias,
 263   // since we cannot allocate aliasing registers to interfering live intervals.
 264   // All other elements (non-aliasing combinations) will have zero cost. Note
 265   // that the spill option (element 0,0) has zero cost, since we can allocate
 266   // both intervals to memory safely (the cost for each individual allocation
 267   // to memory is accounted for by the cost vectors for each live interval).
 268   PBQP::Matrix *m =
 269     new PBQP::Matrix(allowed1.size() + 1, allowed2.size() + 1, 0);
 270
 271   // Assume this is a zero matrix until proven otherwise.  Zero matrices occur
 272   // between interfering live ranges with non-overlapping register sets (e.g.
 273   // non-overlapping reg classes, or disjoint sets of allowed regs within the
 274   // same class). The term "overlapping" is used advisedly: sets which do not
 275   // intersect, but contain registers which alias, will have non-zero matrices.
 276   // We optimize zero matrices away to improve solver speed.
 277   bool isZeroMatrix = true;
 278
 279
 280   // Row index. Starts at 1, since the 0th row is for the spill option, which
 281   // is always zero.
 282   unsigned ri = 1;
 283
 284   // Iterate over allowed sets, insert infinities where required.
 285   for (RegContainerIterator a1Itr = allowed1.begin(), a1End = allowed1.end();
 286        a1Itr != a1End; ++a1Itr) {
 287
 288     // Column index, starts at 1 as for row index.
 289     unsigned ci = 1;
 290     unsigned reg1 = *a1Itr;
 291
 292     for (RegContainerIterator a2Itr = allowed2.begin(), a2End = allowed2.end();
 293          a2Itr != a2End; ++a2Itr) {
 294
 295       unsigned reg2 = *a2Itr;
 296
 297       // If the row/column regs are identical or alias insert an infinity.
 298       if (tri->regsOverlap(reg1, reg2)) {
 299         (*m)[ri][ci] = std::numeric_limits<PBQP::PBQPNum>::infinity();
 300         isZeroMatrix = false;
 301       }
 302
 303       ++ci;
 304     }
 305
 306     ++ri;
 307   }
 308
 309   // If this turns out to be a zero matrix...
 310   if (isZeroMatrix) {
 311     // free it and return null.
 312     delete m;
 313     return 0;
 314   }
 315
 316   // ...otherwise return the cost matrix.
 317   return m;
 318 }
 319
 320 template <typename RegContainer>
 321 PBQP::Matrix* PBQPRegAlloc::buildCoalescingMatrix(
 322       const RegContainer &allowed1, const RegContainer &allowed2,
 323       PBQP::PBQPNum cBenefit) const {
 324
 325   typedef typename RegContainer::const_iterator RegContainerIterator;
 326
 327   // Construct a PBQP Matrix representing the benefits of coalescing. As with
 328   // interference matrices the rows and columns represent allowed registers
 329   // for the LiveIntervals which are (potentially) to be coalesced. The amount
 330   // -cBenefit will be placed in any element representing the same register
 331   // for both intervals.
 332   PBQP::Matrix *m =
 333     new PBQP::Matrix(allowed1.size() + 1, allowed2.size() + 1, 0);
 334
 335   // Reset costs to zero.
 336   m->reset(0);
 337
 338   // Assume the matrix is zero till proven otherwise. Zero matrices will be
 339   // optimized away as in the interference case.
 340   bool isZeroMatrix = true;
 341
 342   // Row index. Starts at 1, since the 0th row is for the spill option, which
 343   // is always zero.
 344   unsigned ri = 1;
 345
 346   // Iterate over the allowed sets, insert coalescing benefits where
 347   // appropriate.
 348   for (RegContainerIterator a1Itr = allowed1.begin(), a1End = allowed1.end();
 349        a1Itr != a1End; ++a1Itr) {
 350
 351     // Column index, starts at 1 as for row index.
 352     unsigned ci = 1;
 353     unsigned reg1 = *a1Itr;
 354
 355     for (RegContainerIterator a2Itr = allowed2.begin(), a2End = allowed2.end();
 356          a2Itr != a2End; ++a2Itr) {
 357
 358       // If the row and column represent the same register insert a beneficial
 359       // cost to preference this allocation - it would allow us to eliminate a
 360       // move instruction.
 361       if (reg1 == *a2Itr) {
 362         (*m)[ri][ci] = -cBenefit;
 363         isZeroMatrix = false;
 364       }
 365
 366       ++ci;
 367     }
 368
 369     ++ri;
 370   }
 371
 372   // If this turns out to be a zero matrix...
 373   if (isZeroMatrix) {
 374     // ...free it and return null.
 375     delete m;
 376     return 0;
 377   }
 378
 379   return m;
 380 }
 381
 382 PBQPRegAlloc::CoalesceMap PBQPRegAlloc::findCoalesces() {
 383
 384   typedef MachineFunction::const_iterator MFIterator;
 385   typedef MachineBasicBlock::const_iterator MBBIterator;
 386   typedef LiveInterval::const_vni_iterator VNIIterator;
 387
 388   CoalesceMap coalescesFound;
 389
 390   // To find coalesces we need to iterate over the function looking for
 391   // copy instructions.
 392   for (MFIterator bbItr = mf->begin(), bbEnd = mf->end();
 393        bbItr != bbEnd; ++bbItr) {
 394
 395     const MachineBasicBlock *mbb = &*bbItr;
 396
 397     for (MBBIterator iItr = mbb->begin(), iEnd = mbb->end();
 398          iItr != iEnd; ++iItr) {
 399
 400       const MachineInstr *instr = &*iItr;
 401
 402       // If this isn't a copy then continue to the next instruction.
 403       if (!instr->isCopy())
 404         continue;
 405
 406       unsigned srcReg = instr->getOperand(1).getReg();
 407       unsigned dstReg = instr->getOperand(0).getReg();
 408
 409       // If the registers are already the same our job is nice and easy.
 410       if (dstReg == srcReg)
 411         continue;
 412
 413       bool srcRegIsPhysical = TargetRegisterInfo::isPhysicalRegister(srcReg),
 414            dstRegIsPhysical = TargetRegisterInfo::isPhysicalRegister(dstReg);
 415
 416       // If both registers are physical then we can't coalesce.
 417       if (srcRegIsPhysical && dstRegIsPhysical)
 418         continue;
 419
 420       // If it's a copy that includes two virtual register but the source and
 421       // destination classes differ then we can't coalesce.
 422       if (!srcRegIsPhysical && !dstRegIsPhysical &&
 423           mri->getRegClass(srcReg) != mri->getRegClass(dstReg))
 424         continue;
 425
 426       // If one is physical and one is virtual, check that the physical is
 427       // allocatable in the class of the virtual.
 428       if (srcRegIsPhysical && !dstRegIsPhysical) {
 429         const TargetRegisterClass *dstRegClass = mri->getRegClass(dstReg);
 430         if (std::find(dstRegClass->allocation_order_begin(*mf),
 431                       dstRegClass->allocation_order_end(*mf), srcReg) ==
 432             dstRegClass->allocation_order_end(*mf))
 433           continue;
 434       }
 435       if (!srcRegIsPhysical && dstRegIsPhysical) {
 436         const TargetRegisterClass *srcRegClass = mri->getRegClass(srcReg);
 437         if (std::find(srcRegClass->allocation_order_begin(*mf),
 438                       srcRegClass->allocation_order_end(*mf), dstReg) ==
 439             srcRegClass->allocation_order_end(*mf))
 440           continue;
 441       }
 442
 443       // If we've made it here we have a copy with compatible register classes.
 444       // We can probably coalesce, but we need to consider overlap.
 445       const LiveInterval *srcLI = &lis->getInterval(srcReg),
 446                          *dstLI = &lis->getInterval(dstReg);
 447
 448       if (srcLI->overlaps(*dstLI)) {
 449         // Even in the case of an overlap we might still be able to coalesce,
 450         // but we need to make sure that no definition of either range occurs
 451         // while the other range is live.
 452
 453         // Otherwise start by assuming we're ok.
 454         bool badDef = false;
 455
 456         // Test all defs of the source range.
 457         for (VNIIterator
 458                vniItr = srcLI->vni_begin(), vniEnd = srcLI->vni_end();
 459                vniItr != vniEnd; ++vniItr) {
 460
 461           // If we find a poorly defined def we err on the side of caution.
 462           if (!(*vniItr)->def.isValid()) {
 463             badDef = true;
 464             break;
 465           }
 466
 467           // If we find a def that kills the coalescing opportunity then
 468           // record it and break from the loop.
 469           if (dstLI->liveAt((*vniItr)->def)) {
 470             badDef = true;
 471             break;
 472           }
 473         }
 474
 475         // If we have a bad def give up, continue to the next instruction.
 476         if (badDef)
 477           continue;
 478
 479         // Otherwise test definitions of the destination range.
 480         for (VNIIterator
 481                vniItr = dstLI->vni_begin(), vniEnd = dstLI->vni_end();
 482                vniItr != vniEnd; ++vniItr) {
 483
 484           // We want to make sure we skip the copy instruction itself.
 485           if ((*vniItr)->getCopy() == instr)
 486             continue;
 487
 488           if (!(*vniItr)->def.isValid()) {
 489             badDef = true;
 490             break;
 491           }
 492
 493           if (srcLI->liveAt((*vniItr)->def)) {
 494             badDef = true;
 495             break;
 496           }
 497         }
 498
 499         // As before a bad def we give up and continue to the next instr.
 500         if (badDef)
 501           continue;
 502       }
 503
 504       // If we make it to here then either the ranges didn't overlap, or they
 505       // did, but none of their definitions would prevent us from coalescing.
 506       // We're good to go with the coalesce.
 507
 508       float cBenefit = std::pow(10.0f, (float)loopInfo->getLoopDepth(mbb)) / 5.0;
 509
 510       coalescesFound[RegPair(srcReg, dstReg)] = cBenefit;
 511       coalescesFound[RegPair(dstReg, srcReg)] = cBenefit;
 512     }
 513
 514   }
 515
 516   return coalescesFound;
 517 }
 518
 519 void PBQPRegAlloc::findVRegIntervalsToAlloc() {
 520
 521   // Iterate over all live ranges.
 522   for (LiveIntervals::iterator itr = lis->begin(), end = lis->end();
 523        itr != end; ++itr) {
 524
 525     // Ignore physical ones.
 526     if (TargetRegisterInfo::isPhysicalRegister(itr->first))
 527       continue;
 528
 529     LiveInterval *li = itr->second;
 530
 531     // If this live interval is non-empty we will use pbqp to allocate it.
 532     // Empty intervals we allocate in a simple post-processing stage in
 533     // finalizeAlloc.
 534     if (!li->empty()) {
 535       vregIntervalsToAlloc.insert(li);
 536     }
 537     else {
 538       emptyVRegIntervals.insert(li);
 539     }
 540   }
 541 }
 542
 543 PBQP::Graph PBQPRegAlloc::constructPBQPProblem() {
 544
 545   typedef std::vector<const LiveInterval*> LIVector;
 546   typedef std::vector<unsigned> RegVector;
 547
 548   // This will store the physical intervals for easy reference.
 549   LIVector physIntervals;
 550
 551   // Start by clearing the old node <-> live interval mappings & allowed sets
 552   li2Node.clear();
 553   node2LI.clear();
 554   allowedSets.clear();
 555
 556   // Populate physIntervals, update preg use:
 557   for (LiveIntervals::iterator itr = lis->begin(), end = lis->end();
 558        itr != end; ++itr) {
 559
 560     if (TargetRegisterInfo::isPhysicalRegister(itr->first)) {
 561       physIntervals.push_back(itr->second);
 562       mri->setPhysRegUsed(itr->second->reg);
 563     }
 564   }
 565
 566   // Iterate over vreg intervals, construct live interval <-> node number
 567   //  mappings.
 568   for (LiveIntervalSet::const_iterator
 569        itr = vregIntervalsToAlloc.begin(), end = vregIntervalsToAlloc.end();
 570        itr != end; ++itr) {
 571     const LiveInterval *li = *itr;
 572
 573     li2Node[li] = node2LI.size();
 574     node2LI.push_back(li);
 575   }
 576
 577   // Get the set of potential coalesces.
 578   CoalesceMap coalesces;
 579
 580   if (pbqpCoalescing) {
 581     coalesces = findCoalesces();
 582   }
 583
 584   // Construct a PBQP solver for this problem
 585   PBQP::Graph problem;
 586   problemNodes.resize(vregIntervalsToAlloc.size());
 587
 588   // Resize allowedSets container appropriately.
 589   allowedSets.resize(vregIntervalsToAlloc.size());
 590
 591   BitVector ReservedRegs = tri->getReservedRegs(*mf);
 592
 593   // Iterate over virtual register intervals to compute allowed sets...
 594   for (unsigned node = 0; node < node2LI.size(); ++node) {
 595
 596     // Grab pointers to the interval and its register class.
 597     const LiveInterval *li = node2LI[node];
 598     const TargetRegisterClass *liRC = mri->getRegClass(li->reg);
 599
 600     // Start by assuming all allocable registers in the class are allowed...
 601     RegVector liAllowed;
 602     TargetRegisterClass::iterator aob = liRC->allocation_order_begin(*mf);
 603     TargetRegisterClass::iterator aoe = liRC->allocation_order_end(*mf);
 604     for (TargetRegisterClass::iterator it = aob; it != aoe; ++it)
 605       if (!ReservedRegs.test(*it))
 606         liAllowed.push_back(*it);
 607
 608     // Eliminate the physical registers which overlap with this range, along
 609     // with all their aliases.
 610     for (LIVector::iterator pItr = physIntervals.begin(),
 611        pEnd = physIntervals.end(); pItr != pEnd; ++pItr) {
 612
 613       if (!li->overlaps(**pItr))
 614         continue;
 615
 616       unsigned pReg = (*pItr)->reg;
 617
 618       // If we get here then the live intervals overlap, but we're still ok
 619       // if they're coalescable.
 620       if (coalesces.find(RegPair(li->reg, pReg)) != coalesces.end())
 621         continue;
 622
 623       // If we get here then we have a genuine exclusion.
 624
 625       // Remove the overlapping reg...
 626       RegVector::iterator eraseItr =
 627         std::find(liAllowed.begin(), liAllowed.end(), pReg);
 628
 629       if (eraseItr != liAllowed.end())
 630         liAllowed.erase(eraseItr);
 631
 632       const unsigned *aliasItr = tri->getAliasSet(pReg);
 633
 634       if (aliasItr != 0) {
 635         // ...and its aliases.
 636         for (; *aliasItr != 0; ++aliasItr) {
 637           RegVector::iterator eraseItr =
 638             std::find(liAllowed.begin(), liAllowed.end(), *aliasItr);
 639
 640           if (eraseItr != liAllowed.end()) {
 641             liAllowed.erase(eraseItr);
 642           }
 643         }
 644       }
 645     }
 646
 647     // Copy the allowed set into a member vector for use when constructing cost
 648     // vectors & matrices, and mapping PBQP solutions back to assignments.
 649     allowedSets[node] = AllowedSet(liAllowed.begin(), liAllowed.end());
 650
 651     // Set the spill cost to the interval weight, or epsilon if the
 652     // interval weight is zero
 653     PBQP::PBQPNum spillCost = (li->weight != 0.0) ?
 654         li->weight : std::numeric_limits<PBQP::PBQPNum>::min();
 655
 656     // Build a cost vector for this interval.
 657     problemNodes[node] =
 658       problem.addNode(
 659         buildCostVector(li->reg, allowedSets[node], coalesces, spillCost));
 660
 661   }
 662
 663
 664   // Now add the cost matrices...
 665   for (unsigned node1 = 0; node1 < node2LI.size(); ++node1) {
 666     const LiveInterval *li = node2LI[node1];
 667
 668     // Test for live range overlaps and insert interference matrices.
 669     for (unsigned node2 = node1 + 1; node2 < node2LI.size(); ++node2) {
 670       const LiveInterval *li2 = node2LI[node2];
 671
 672       CoalesceMap::const_iterator cmItr =
 673         coalesces.find(RegPair(li->reg, li2->reg));
 674
 675       PBQP::Matrix *m = 0;
 676
 677       if (cmItr != coalesces.end()) {
 678         m = buildCoalescingMatrix(allowedSets[node1], allowedSets[node2],
 679                                   cmItr->second);
 680       }
 681       else if (li->overlaps(*li2)) {
 682         m = buildInterferenceMatrix(allowedSets[node1], allowedSets[node2]);
 683       }
 684
 685       if (m != 0) {
 686         problem.addEdge(problemNodes[node1],
 687                         problemNodes[node2],
 688                         *m);
 689
 690         delete m;
 691       }
 692     }
 693   }
 694
 695   assert(problem.getNumNodes() == allowedSets.size());
 696 /*
 697   std::cerr << "Allocating for " << problem.getNumNodes() << " nodes, "
 698             << problem.getNumEdges() << " edges.\n";
 699
 700   problem.printDot(std::cerr);
 701 */
 702   // We're done, PBQP problem constructed - return it.
 703   return problem;
 704 }
 705
 706 void PBQPRegAlloc::addStackInterval(const LiveInterval *spilled,
 707                                     MachineRegisterInfo* mri) {
 708   int stackSlot = vrm->getStackSlot(spilled->reg);
 709
 710   if (stackSlot == VirtRegMap::NO_STACK_SLOT)
 711     return;
 712
 713   const TargetRegisterClass *RC = mri->getRegClass(spilled->reg);
 714   LiveInterval &stackInterval = lss->getOrCreateInterval(stackSlot, RC);
 715
 716   VNInfo *vni;
 717   if (stackInterval.getNumValNums() != 0)
 718     vni = stackInterval.getValNumInfo(0);
 719   else
 720     vni = stackInterval.getNextValue(
 721       SlotIndex(), 0, false, lss->getVNInfoAllocator());
 722
 723   LiveInterval &rhsInterval = lis->getInterval(spilled->reg);
 724   stackInterval.MergeRangesInAsValue(rhsInterval, vni);
 725 }
 726
 727 bool PBQPRegAlloc::mapPBQPToRegAlloc(const PBQP::Solution &solution) {
 728
 729   // Set to true if we have any spills
 730   bool anotherRoundNeeded = false;
 731
 732   // Clear the existing allocation.
 733   vrm->clearAllVirt();
 734
 735   // Iterate over the nodes mapping the PBQP solution to a register assignment.
 736   for (unsigned node = 0; node < node2LI.size(); ++node) {
 737     unsigned virtReg = node2LI[node]->reg,
 738              allocSelection = solution.getSelection(problemNodes[node]);
 739
 740
 741     // If the PBQP solution is non-zero it's a physical register...
 742     if (allocSelection != 0) {
 743       // Get the physical reg, subtracting 1 to account for the spill option.
 744       unsigned physReg = allowedSets[node][allocSelection - 1];
 745
 746       DEBUG(dbgs() << "VREG " << virtReg << " -> "
 747                    << tri->getName(physReg) << "\n");
 748
 749       assert(physReg != 0);
 750
 751       // Add to the virt reg map and update the used phys regs.
 752       vrm->assignVirt2Phys(virtReg, physReg);
 753     }
 754     // ...Otherwise it's a spill.
 755     else {
 756
 757       // Make sure we ignore this virtual reg on the next round
 758       // of allocation
 759       vregIntervalsToAlloc.erase(&lis->getInterval(virtReg));
 760
 761       // Insert spill ranges for this live range
 762       const LiveInterval *spillInterval = node2LI[node];
 763       double oldSpillWeight = spillInterval->weight;
 764       SmallVector<LiveInterval*, 8> spillIs;
 765       rmf->rememberUseDefs(spillInterval);
 766       std::vector<LiveInterval*> newSpills =
 767         lis->addIntervalsForSpills(*spillInterval, spillIs, loopInfo, *vrm);
 768       addStackInterval(spillInterval, mri);
 769       rmf->rememberSpills(spillInterval, newSpills);
 770
 771       (void) oldSpillWeight;
 772       DEBUG(dbgs() << "VREG " << virtReg << " -> SPILLED (Cost: "
 773                    << oldSpillWeight << ", New vregs: ");
 774
 775       // Copy any newly inserted live intervals into the list of regs to
 776       // allocate.
 777       for (std::vector<LiveInterval*>::const_iterator
 778            itr = newSpills.begin(), end = newSpills.end();
 779            itr != end; ++itr) {
 780
 781         assert(!(*itr)->empty() && "Empty spill range.");
 782
 783         DEBUG(dbgs() << (*itr)->reg << " ");
 784
 785         vregIntervalsToAlloc.insert(*itr);
 786       }
 787
 788       DEBUG(dbgs() << ")\n");
 789
 790       // We need another round if spill intervals were added.
 791       anotherRoundNeeded |= !newSpills.empty();
 792     }
 793   }
 794
 795   return !anotherRoundNeeded;
 796 }
 797
 798 void PBQPRegAlloc::finalizeAlloc() const {
 799   typedef LiveIntervals::iterator LIIterator;
 800   typedef LiveInterval::Ranges::const_iterator LRIterator;
 801
 802   // First allocate registers for the empty intervals.
 803   for (LiveIntervalSet::const_iterator
 804          itr = emptyVRegIntervals.begin(), end = emptyVRegIntervals.end();
 805          itr != end; ++itr) {
 806     LiveInterval *li = *itr;
 807
 808     unsigned physReg = vrm->getRegAllocPref(li->reg);
 809
 810     if (physReg == 0) {
 811       const TargetRegisterClass *liRC = mri->getRegClass(li->reg);
 812       physReg = *liRC->allocation_order_begin(*mf);
 813     }
 814
 815     vrm->assignVirt2Phys(li->reg, physReg);
 816   }
 817
 818   // Finally iterate over the basic blocks to compute and set the live-in sets.
 819   SmallVector<MachineBasicBlock*, 8> liveInMBBs;
 820   MachineBasicBlock *entryMBB = &*mf->begin();
 821
 822   for (LIIterator liItr = lis->begin(), liEnd = lis->end();
 823        liItr != liEnd; ++liItr) {
 824
 825     const LiveInterval *li = liItr->second;
 826     unsigned reg = 0;
 827
 828     // Get the physical register for this interval
 829     if (TargetRegisterInfo::isPhysicalRegister(li->reg)) {
 830       reg = li->reg;
 831     }
 832     else if (vrm->isAssignedReg(li->reg)) {
 833       reg = vrm->getPhys(li->reg);
 834     }
 835     else {
 836       // Ranges which are assigned a stack slot only are ignored.
 837       continue;
 838     }
 839
 840     if (reg == 0) {
 841       // Filter out zero regs - they're for intervals that were spilled.
 842       continue;
 843     }
 844
 845     // Iterate over the ranges of the current interval...
 846     for (LRIterator lrItr = li->begin(), lrEnd = li->end();
 847          lrItr != lrEnd; ++lrItr) {
 848
 849       // Find the set of basic blocks which this range is live into...
 850       if (lis->findLiveInMBBs(lrItr->start, lrItr->end,  liveInMBBs)) {
 851         // And add the physreg for this interval to their live-in sets.
 852         for (unsigned i = 0; i < liveInMBBs.size(); ++i) {
 853           if (liveInMBBs[i] != entryMBB) {
 854             if (!liveInMBBs[i]->isLiveIn(reg)) {
 855               liveInMBBs[i]->addLiveIn(reg);
 856             }
 857           }
 858         }
 859         liveInMBBs.clear();
 860       }
 861     }
 862   }
 863
 864 }
 865
 866 bool PBQPRegAlloc::runOnMachineFunction(MachineFunction &MF) {
 867
 868   mf = &MF;
 869   tm = &mf->getTarget();
 870   tri = tm->getRegisterInfo();
 871   tii = tm->getInstrInfo();
 872   mri = &mf->getRegInfo();
 873
 874   lis = &getAnalysis<LiveIntervals>();
 875   lss = &getAnalysis<LiveStacks>();
 876   loopInfo = &getAnalysis<MachineLoopInfo>();
 877   rmf = &getAnalysis<RenderMachineFunction>();
 878
 879   vrm = &getAnalysis<VirtRegMap>();
 880
 881
 882   DEBUG(dbgs() << "PBQP Register Allocating for " << mf->getFunction()->getName() << "\n");
 883
 884   // Allocator main loop:
 885   //
 886   // * Map current regalloc problem to a PBQP problem
 887   // * Solve the PBQP problem
 888   // * Map the solution back to a register allocation
 889   // * Spill if necessary
 890   //
 891   // This process is continued till no more spills are generated.
 892
 893   // Find the vreg intervals in need of allocation.
 894   findVRegIntervalsToAlloc();
 895
 896   // If there are non-empty intervals allocate them using pbqp.
 897   if (!vregIntervalsToAlloc.empty()) {
 898
 899     bool pbqpAllocComplete = false;
 900     unsigned round = 0;
 901
 902     while (!pbqpAllocComplete) {
 903       DEBUG(dbgs() << "  PBQP Regalloc round " << round << ":\n");
 904
 905       PBQP::Graph problem = constructPBQPProblem();
 906       PBQP::Solution solution =
 907         PBQP::HeuristicSolver<PBQP::Heuristics::Briggs>::solve(problem);
 908
 909       pbqpAllocComplete = mapPBQPToRegAlloc(solution);
 910
 911       ++round;
 912     }
 913   }
 914
 915   // Finalise allocation, allocate empty ranges.
 916   finalizeAlloc();
 917
 918   rmf->renderMachineFunction("After PBQP register allocation.", vrm);
 919
 920   vregIntervalsToAlloc.clear();
 921   emptyVRegIntervals.clear();
 922   li2Node.clear();
 923   node2LI.clear();
 924   allowedSets.clear();
 925   problemNodes.clear();
 926
 927   DEBUG(dbgs() << "Post alloc VirtRegMap:\n" << *vrm << "\n");
 928
 929   // Run rewriter
 930   std::auto_ptr<VirtRegRewriter> rewriter(createVirtRegRewriter());
 931
 932   rewriter->runOnMachineFunction(*mf, *vrm, lis);
 933
 934   return true;
 935 }
 936
 937 FunctionPass* llvm::createPBQPRegisterAllocator() {
 938   return new PBQPRegAlloc();
 939 }
 940
 941
 942 #undef DEBUG_TYPE