LLVM API Documentation

RegAllocPBQP.cpp

Go to the documentation of this file.
00001 //===------ RegAllocPBQP.cpp ---- PBQP Register Allocator -------*- C++ -*-===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file contains a Partitioned Boolean Quadratic Programming (PBQP) based
00011 // register allocator for LLVM. This allocator works by constructing a PBQP
00012 // problem representing the register allocation problem under consideration,
00013 // solving this using a PBQP solver, and mapping the solution back to a
00014 // register assignment. If any variables are selected for spilling then spill
00015 // code is inserted and the process repeated.
00016 //
00017 // The PBQP solver (pbqp.c) provided for this allocator uses a heuristic tuned
00018 // for register allocation. For more information on PBQP for register
00019 // allocation, see the following papers:
00020 //
00021 //   (1) Hames, L. and Scholz, B. 2006. Nearly optimal register allocation with
00022 //   PBQP. In Proceedings of the 7th Joint Modular Languages Conference
00023 //   (JMLC'06). LNCS, vol. 4228. Springer, New York, NY, USA. 346-361.
00024 //
00025 //   (2) Scholz, B., Eckstein, E. 2002. Register allocation for irregular
00026 //   architectures. In Proceedings of the Joint Conference on Languages,
00027 //   Compilers and Tools for Embedded Systems (LCTES'02), ACM Press, New York,
00028 //   NY, USA, 139-148.
00029 //
00030 //===----------------------------------------------------------------------===//
00031 
00032 #define DEBUG_TYPE "regalloc"
00033 
00034 #include "PBQP/HeuristicSolver.h"
00035 #include "PBQP/SimpleGraph.h"
00036 #include "PBQP/Heuristics/Briggs.h"
00037 #include "VirtRegMap.h"
00038 #include "VirtRegRewriter.h"
00039 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
00040 #include "llvm/CodeGen/LiveStackAnalysis.h"
00041 #include "llvm/CodeGen/MachineFunctionPass.h"
00042 #include "llvm/CodeGen/MachineLoopInfo.h"
00043 #include "llvm/CodeGen/MachineRegisterInfo.h"
00044 #include "llvm/CodeGen/RegAllocRegistry.h"
00045 #include "llvm/CodeGen/RegisterCoalescer.h"
00046 #include "llvm/Support/Debug.h"
00047 #include "llvm/Support/raw_ostream.h"
00048 #include "llvm/Target/TargetInstrInfo.h"
00049 #include "llvm/Target/TargetMachine.h"
00050 #include <limits>
00051 #include <map>
00052 #include <memory>
00053 #include <set>
00054 #include <vector>
00055 
00056 using namespace llvm;
00057 
00058 static RegisterRegAlloc
00059 registerPBQPRepAlloc("pbqp", "PBQP register allocator.",
00060                       llvm::createPBQPRegisterAllocator);
00061 
00062 static cl::opt<bool>
00063 pbqpCoalescing("pbqp-coalescing",
00064                cl::desc("Attempt coalescing during PBQP register allocation."),
00065                cl::init(false), cl::Hidden);
00066 
00067 namespace {
00068 
00069   ///
00070   /// PBQP based allocators solve the register allocation problem by mapping
00071   /// register allocation problems to Partitioned Boolean Quadratic
00072   /// Programming problems.
00073   class VISIBILITY_HIDDEN PBQPRegAlloc : public MachineFunctionPass {
00074   public:
00075 
00076     static char ID;
00077     
00078     /// Construct a PBQP register allocator.
00079     PBQPRegAlloc() : MachineFunctionPass(&ID) {}
00080 
00081     /// Return the pass name.
00082     virtual const char* getPassName() const {
00083       return "PBQP Register Allocator";
00084     }
00085 
00086     /// PBQP analysis usage.
00087     virtual void getAnalysisUsage(AnalysisUsage &au) const {
00088       au.addRequired<LiveIntervals>();
00089       //au.addRequiredID(SplitCriticalEdgesID);
00090       au.addRequired<RegisterCoalescer>();
00091       au.addRequired<LiveStacks>();
00092       au.addPreserved<LiveStacks>();
00093       au.addRequired<MachineLoopInfo>();
00094       au.addPreserved<MachineLoopInfo>();
00095       au.addRequired<VirtRegMap>();
00096       MachineFunctionPass::getAnalysisUsage(au);
00097     }
00098 
00099     /// Perform register allocation
00100     virtual bool runOnMachineFunction(MachineFunction &MF);
00101 
00102   private:
00103     typedef std::map<const LiveInterval*, unsigned> LI2NodeMap;
00104     typedef std::vector<const LiveInterval*> Node2LIMap;
00105     typedef std::vector<unsigned> AllowedSet;
00106     typedef std::vector<AllowedSet> AllowedSetMap;
00107     typedef std::set<unsigned> RegSet;
00108     typedef std::pair<unsigned, unsigned> RegPair;
00109     typedef std::map<RegPair, PBQP::PBQPNum> CoalesceMap;
00110 
00111     typedef std::set<LiveInterval*> LiveIntervalSet;
00112 
00113     MachineFunction *mf;
00114     const TargetMachine *tm;
00115     const TargetRegisterInfo *tri;
00116     const TargetInstrInfo *tii;
00117     const MachineLoopInfo *loopInfo;
00118     MachineRegisterInfo *mri;
00119 
00120     LiveIntervals *lis;
00121     LiveStacks *lss;
00122     VirtRegMap *vrm;
00123 
00124     LI2NodeMap li2Node;
00125     Node2LIMap node2LI;
00126     AllowedSetMap allowedSets;
00127     LiveIntervalSet vregIntervalsToAlloc,
00128                     emptyVRegIntervals;
00129 
00130 
00131     /// Builds a PBQP cost vector.
00132     template <typename RegContainer>
00133     PBQP::Vector buildCostVector(unsigned vReg,
00134                                  const RegContainer &allowed,
00135                                  const CoalesceMap &cealesces,
00136                                  PBQP::PBQPNum spillCost) const;
00137 
00138     /// \brief Builds a PBQP interference matrix.
00139     ///
00140     /// @return Either a pointer to a non-zero PBQP matrix representing the
00141     ///         allocation option costs, or a null pointer for a zero matrix.
00142     ///
00143     /// Expects allowed sets for two interfering LiveIntervals. These allowed
00144     /// sets should contain only allocable registers from the LiveInterval's
00145     /// register class, with any interfering pre-colored registers removed.
00146     template <typename RegContainer>
00147     PBQP::Matrix* buildInterferenceMatrix(const RegContainer &allowed1,
00148                                           const RegContainer &allowed2) const;
00149 
00150     ///
00151     /// Expects allowed sets for two potentially coalescable LiveIntervals,
00152     /// and an estimated benefit due to coalescing. The allowed sets should
00153     /// contain only allocable registers from the LiveInterval's register
00154     /// classes, with any interfering pre-colored registers removed.
00155     template <typename RegContainer>
00156     PBQP::Matrix* buildCoalescingMatrix(const RegContainer &allowed1,
00157                                         const RegContainer &allowed2,
00158                                         PBQP::PBQPNum cBenefit) const;
00159 
00160     /// \brief Finds coalescing opportunities and returns them as a map.
00161     ///
00162     /// Any entries in the map are guaranteed coalescable, even if their
00163     /// corresponding live intervals overlap.
00164     CoalesceMap findCoalesces();
00165 
00166     /// \brief Finds the initial set of vreg intervals to allocate.
00167     void findVRegIntervalsToAlloc();
00168 
00169     /// \brief Constructs a PBQP problem representation of the register
00170     /// allocation problem for this function.
00171     ///
00172     /// @return a PBQP solver object for the register allocation problem.
00173     PBQP::SimpleGraph constructPBQPProblem();
00174 
00175     /// \brief Adds a stack interval if the given live interval has been
00176     /// spilled. Used to support stack slot coloring.
00177     void addStackInterval(const LiveInterval *spilled,MachineRegisterInfo* mri);
00178 
00179     /// \brief Given a solved PBQP problem maps this solution back to a register
00180     /// assignment.
00181     bool mapPBQPToRegAlloc(const PBQP::Solution &solution);
00182 
00183     /// \brief Postprocessing before final spilling. Sets basic block "live in"
00184     /// variables.
00185     void finalizeAlloc() const;
00186 
00187   };
00188 
00189   char PBQPRegAlloc::ID = 0;
00190 }
00191 
00192 
00193 template <typename RegContainer>
00194 PBQP::Vector PBQPRegAlloc::buildCostVector(unsigned vReg,
00195                                            const RegContainer &allowed,
00196                                            const CoalesceMap &coalesces,
00197                                            PBQP::PBQPNum spillCost) const {
00198 
00199   typedef typename RegContainer::const_iterator AllowedItr;
00200 
00201   // Allocate vector. Additional element (0th) used for spill option
00202   PBQP::Vector v(allowed.size() + 1, 0);
00203 
00204   v[0] = spillCost;
00205 
00206   // Iterate over the allowed registers inserting coalesce benefits if there
00207   // are any.
00208   unsigned ai = 0;
00209   for (AllowedItr itr = allowed.begin(), end = allowed.end();
00210        itr != end; ++itr, ++ai) {
00211 
00212     unsigned pReg = *itr;
00213 
00214     CoalesceMap::const_iterator cmItr =
00215       coalesces.find(RegPair(vReg, pReg));
00216 
00217     // No coalesce - on to the next preg.
00218     if (cmItr == coalesces.end())
00219       continue;
00220 
00221     // We have a coalesce - insert the benefit.
00222     v[ai + 1] = -cmItr->second;
00223   }
00224 
00225   return v;
00226 }
00227 
00228 template <typename RegContainer>
00229 PBQP::Matrix* PBQPRegAlloc::buildInterferenceMatrix(
00230       const RegContainer &allowed1, const RegContainer &allowed2) const {
00231 
00232   typedef typename RegContainer::const_iterator RegContainerIterator;
00233 
00234   // Construct a PBQP matrix representing the cost of allocation options. The
00235   // rows and columns correspond to the allocation options for the two live
00236   // intervals.  Elements will be infinite where corresponding registers alias,
00237   // since we cannot allocate aliasing registers to interfering live intervals.
00238   // All other elements (non-aliasing combinations) will have zero cost. Note
00239   // that the spill option (element 0,0) has zero cost, since we can allocate
00240   // both intervals to memory safely (the cost for each individual allocation
00241   // to memory is accounted for by the cost vectors for each live interval).
00242   PBQP::Matrix *m =
00243     new PBQP::Matrix(allowed1.size() + 1, allowed2.size() + 1, 0);
00244 
00245   // Assume this is a zero matrix until proven otherwise.  Zero matrices occur
00246   // between interfering live ranges with non-overlapping register sets (e.g.
00247   // non-overlapping reg classes, or disjoint sets of allowed regs within the
00248   // same class). The term "overlapping" is used advisedly: sets which do not
00249   // intersect, but contain registers which alias, will have non-zero matrices.
00250   // We optimize zero matrices away to improve solver speed.
00251   bool isZeroMatrix = true;
00252 
00253 
00254   // Row index. Starts at 1, since the 0th row is for the spill option, which
00255   // is always zero.
00256   unsigned ri = 1;
00257 
00258   // Iterate over allowed sets, insert infinities where required.
00259   for (RegContainerIterator a1Itr = allowed1.begin(), a1End = allowed1.end();
00260        a1Itr != a1End; ++a1Itr) {
00261 
00262     // Column index, starts at 1 as for row index.
00263     unsigned ci = 1;
00264     unsigned reg1 = *a1Itr;
00265 
00266     for (RegContainerIterator a2Itr = allowed2.begin(), a2End = allowed2.end();
00267          a2Itr != a2End; ++a2Itr) {
00268 
00269       unsigned reg2 = *a2Itr;
00270 
00271       // If the row/column regs are identical or alias insert an infinity.
00272       if (tri->regsOverlap(reg1, reg2)) {
00273         (*m)[ri][ci] = std::numeric_limits<PBQP::PBQPNum>::infinity();
00274         isZeroMatrix = false;
00275       }
00276 
00277       ++ci;
00278     }
00279 
00280     ++ri;
00281   }
00282 
00283   // If this turns out to be a zero matrix...
00284   if (isZeroMatrix) {
00285     // free it and return null.
00286     delete m;
00287     return 0;
00288   }
00289 
00290   // ...otherwise return the cost matrix.
00291   return m;
00292 }
00293 
00294 template <typename RegContainer>
00295 PBQP::Matrix* PBQPRegAlloc::buildCoalescingMatrix(
00296       const RegContainer &allowed1, const RegContainer &allowed2,
00297       PBQP::PBQPNum cBenefit) const {
00298 
00299   typedef typename RegContainer::const_iterator RegContainerIterator;
00300 
00301   // Construct a PBQP Matrix representing the benefits of coalescing. As with
00302   // interference matrices the rows and columns represent allowed registers
00303   // for the LiveIntervals which are (potentially) to be coalesced. The amount
00304   // -cBenefit will be placed in any element representing the same register
00305   // for both intervals.
00306   PBQP::Matrix *m =
00307     new PBQP::Matrix(allowed1.size() + 1, allowed2.size() + 1, 0);
00308 
00309   // Reset costs to zero.
00310   m->reset(0);
00311 
00312   // Assume the matrix is zero till proven otherwise. Zero matrices will be
00313   // optimized away as in the interference case.
00314   bool isZeroMatrix = true;
00315 
00316   // Row index. Starts at 1, since the 0th row is for the spill option, which
00317   // is always zero.
00318   unsigned ri = 1;
00319 
00320   // Iterate over the allowed sets, insert coalescing benefits where
00321   // appropriate.
00322   for (RegContainerIterator a1Itr = allowed1.begin(), a1End = allowed1.end();
00323        a1Itr != a1End; ++a1Itr) {
00324 
00325     // Column index, starts at 1 as for row index.
00326     unsigned ci = 1;
00327     unsigned reg1 = *a1Itr;
00328 
00329     for (RegContainerIterator a2Itr = allowed2.begin(), a2End = allowed2.end();
00330          a2Itr != a2End; ++a2Itr) {
00331 
00332       // If the row and column represent the same register insert a beneficial
00333       // cost to preference this allocation - it would allow us to eliminate a
00334       // move instruction.
00335       if (reg1 == *a2Itr) {
00336         (*m)[ri][ci] = -cBenefit;
00337         isZeroMatrix = false;
00338       }
00339 
00340       ++ci;
00341     }
00342 
00343     ++ri;
00344   }
00345 
00346   // If this turns out to be a zero matrix...
00347   if (isZeroMatrix) {
00348     // ...free it and return null.
00349     delete m;
00350     return 0;
00351   }
00352 
00353   return m;
00354 }
00355 
00356 PBQPRegAlloc::CoalesceMap PBQPRegAlloc::findCoalesces() {
00357 
00358   typedef MachineFunction::const_iterator MFIterator;
00359   typedef MachineBasicBlock::const_iterator MBBIterator;
00360   typedef LiveInterval::const_vni_iterator VNIIterator;
00361 
00362   CoalesceMap coalescesFound;
00363 
00364   // To find coalesces we need to iterate over the function looking for
00365   // copy instructions.
00366   for (MFIterator bbItr = mf->begin(), bbEnd = mf->end();
00367        bbItr != bbEnd; ++bbItr) {
00368 
00369     const MachineBasicBlock *mbb = &*bbItr;
00370 
00371     for (MBBIterator iItr = mbb->begin(), iEnd = mbb->end();
00372          iItr != iEnd; ++iItr) {
00373 
00374       const MachineInstr *instr = &*iItr;
00375       unsigned srcReg, dstReg, srcSubReg, dstSubReg;
00376 
00377       // If this isn't a copy then continue to the next instruction.
00378       if (!tii->isMoveInstr(*instr, srcReg, dstReg, srcSubReg, dstSubReg))
00379         continue;
00380 
00381       // If the registers are already the same our job is nice and easy.
00382       if (dstReg == srcReg)
00383         continue;
00384 
00385       bool srcRegIsPhysical = TargetRegisterInfo::isPhysicalRegister(srcReg),
00386            dstRegIsPhysical = TargetRegisterInfo::isPhysicalRegister(dstReg);
00387 
00388       // If both registers are physical then we can't coalesce.
00389       if (srcRegIsPhysical && dstRegIsPhysical)
00390         continue;
00391 
00392       // If it's a copy that includes a virtual register but the source and
00393       // destination classes differ then we can't coalesce, so continue with
00394       // the next instruction.
00395       const TargetRegisterClass *srcRegClass = srcRegIsPhysical ?
00396           tri->getPhysicalRegisterRegClass(srcReg) : mri->getRegClass(srcReg);
00397 
00398       const TargetRegisterClass *dstRegClass = dstRegIsPhysical ?
00399           tri->getPhysicalRegisterRegClass(dstReg) : mri->getRegClass(dstReg);
00400 
00401       if (srcRegClass != dstRegClass)
00402         continue;
00403 
00404       // We also need any physical regs to be allocable, coalescing with
00405       // a non-allocable register is invalid.
00406       if (srcRegIsPhysical) {
00407         if (std::find(srcRegClass->allocation_order_begin(*mf),
00408                       srcRegClass->allocation_order_end(*mf), srcReg) ==
00409             srcRegClass->allocation_order_end(*mf))
00410           continue;
00411       }
00412 
00413       if (dstRegIsPhysical) {
00414         if (std::find(dstRegClass->allocation_order_begin(*mf),
00415                       dstRegClass->allocation_order_end(*mf), dstReg) ==
00416             dstRegClass->allocation_order_end(*mf))
00417           continue;
00418       }
00419 
00420       // If we've made it here we have a copy with compatible register classes.
00421       // We can probably coalesce, but we need to consider overlap.
00422       const LiveInterval *srcLI = &lis->getInterval(srcReg),
00423                          *dstLI = &lis->getInterval(dstReg);
00424 
00425       if (srcLI->overlaps(*dstLI)) {
00426         // Even in the case of an overlap we might still be able to coalesce,
00427         // but we need to make sure that no definition of either range occurs
00428         // while the other range is live.
00429 
00430         // Otherwise start by assuming we're ok.
00431         bool badDef = false;
00432 
00433         // Test all defs of the source range.
00434         for (VNIIterator
00435                vniItr = srcLI->vni_begin(), vniEnd = srcLI->vni_end();
00436                vniItr != vniEnd; ++vniItr) {
00437 
00438           // If we find a def that kills the coalescing opportunity then
00439           // record it and break from the loop.
00440           if (dstLI->liveAt((*vniItr)->def)) {
00441             badDef = true;
00442             break;
00443           }
00444         }
00445 
00446         // If we have a bad def give up, continue to the next instruction.
00447         if (badDef)
00448           continue;
00449 
00450         // Otherwise test definitions of the destination range.
00451         for (VNIIterator
00452                vniItr = dstLI->vni_begin(), vniEnd = dstLI->vni_end();
00453                vniItr != vniEnd; ++vniItr) {
00454 
00455           // We want to make sure we skip the copy instruction itself.
00456           if ((*vniItr)->getCopy() == instr)
00457             continue;
00458 
00459           if (srcLI->liveAt((*vniItr)->def)) {
00460             badDef = true;
00461             break;
00462           }
00463         }
00464 
00465         // As before a bad def we give up and continue to the next instr.
00466         if (badDef)
00467           continue;
00468       }
00469 
00470       // If we make it to here then either the ranges didn't overlap, or they
00471       // did, but none of their definitions would prevent us from coalescing.
00472       // We're good to go with the coalesce.
00473 
00474       float cBenefit = powf(10.0f, loopInfo->getLoopDepth(mbb)) / 5.0;
00475 
00476       coalescesFound[RegPair(srcReg, dstReg)] = cBenefit;
00477       coalescesFound[RegPair(dstReg, srcReg)] = cBenefit;
00478     }
00479 
00480   }
00481 
00482   return coalescesFound;
00483 }
00484 
00485 void PBQPRegAlloc::findVRegIntervalsToAlloc() {
00486 
00487   // Iterate over all live ranges.
00488   for (LiveIntervals::iterator itr = lis->begin(), end = lis->end();
00489        itr != end; ++itr) {
00490 
00491     // Ignore physical ones.
00492     if (TargetRegisterInfo::isPhysicalRegister(itr->first))
00493       continue;
00494 
00495     LiveInterval *li = itr->second;
00496 
00497     // If this live interval is non-empty we will use pbqp to allocate it.
00498     // Empty intervals we allocate in a simple post-processing stage in
00499     // finalizeAlloc.
00500     if (!li->empty()) {
00501       vregIntervalsToAlloc.insert(li);
00502     }
00503     else {
00504       emptyVRegIntervals.insert(li);
00505     }
00506   }
00507 }
00508 
00509 PBQP::SimpleGraph PBQPRegAlloc::constructPBQPProblem() {
00510 
00511   typedef std::vector<const LiveInterval*> LIVector;
00512   typedef std::vector<unsigned> RegVector;
00513   typedef std::vector<PBQP::SimpleGraph::NodeIterator> NodeVector;
00514 
00515   // This will store the physical intervals for easy reference.
00516   LIVector physIntervals;
00517 
00518   // Start by clearing the old node <-> live interval mappings & allowed sets
00519   li2Node.clear();
00520   node2LI.clear();
00521   allowedSets.clear();
00522 
00523   // Populate physIntervals, update preg use:
00524   for (LiveIntervals::iterator itr = lis->begin(), end = lis->end();
00525        itr != end; ++itr) {
00526 
00527     if (TargetRegisterInfo::isPhysicalRegister(itr->first)) {
00528       physIntervals.push_back(itr->second);
00529       mri->setPhysRegUsed(itr->second->reg);
00530     }
00531   }
00532 
00533   // Iterate over vreg intervals, construct live interval <-> node number
00534   //  mappings.
00535   for (LiveIntervalSet::const_iterator
00536        itr = vregIntervalsToAlloc.begin(), end = vregIntervalsToAlloc.end();
00537        itr != end; ++itr) {
00538     const LiveInterval *li = *itr;
00539 
00540     li2Node[li] = node2LI.size();
00541     node2LI.push_back(li);
00542   }
00543 
00544   // Get the set of potential coalesces.
00545   CoalesceMap coalesces;
00546 
00547   if (pbqpCoalescing) {
00548     coalesces = findCoalesces();
00549   }
00550 
00551   // Construct a PBQP solver for this problem
00552   PBQP::SimpleGraph problem;
00553   NodeVector problemNodes(vregIntervalsToAlloc.size());
00554 
00555   // Resize allowedSets container appropriately.
00556   allowedSets.resize(vregIntervalsToAlloc.size());
00557 
00558   // Iterate over virtual register intervals to compute allowed sets...
00559   for (unsigned node = 0; node < node2LI.size(); ++node) {
00560 
00561     // Grab pointers to the interval and its register class.
00562     const LiveInterval *li = node2LI[node];
00563     const TargetRegisterClass *liRC = mri->getRegClass(li->reg);
00564 
00565     // Start by assuming all allocable registers in the class are allowed...
00566     RegVector liAllowed(liRC->allocation_order_begin(*mf),
00567                         liRC->allocation_order_end(*mf));
00568 
00569     // Eliminate the physical registers which overlap with this range, along
00570     // with all their aliases.
00571     for (LIVector::iterator pItr = physIntervals.begin(),
00572        pEnd = physIntervals.end(); pItr != pEnd; ++pItr) {
00573 
00574       if (!li->overlaps(**pItr))
00575         continue;
00576 
00577       unsigned pReg = (*pItr)->reg;
00578 
00579       // If we get here then the live intervals overlap, but we're still ok
00580       // if they're coalescable.
00581       if (coalesces.find(RegPair(li->reg, pReg)) != coalesces.end())
00582         continue;
00583 
00584       // If we get here then we have a genuine exclusion.
00585 
00586       // Remove the overlapping reg...
00587       RegVector::iterator eraseItr =
00588         std::find(liAllowed.begin(), liAllowed.end(), pReg);
00589 
00590       if (eraseItr != liAllowed.end())
00591         liAllowed.erase(eraseItr);
00592 
00593       const unsigned *aliasItr = tri->getAliasSet(pReg);
00594 
00595       if (aliasItr != 0) {
00596         // ...and its aliases.
00597         for (; *aliasItr != 0; ++aliasItr) {
00598           RegVector::iterator eraseItr =
00599             std::find(liAllowed.begin(), liAllowed.end(), *aliasItr);
00600 
00601           if (eraseItr != liAllowed.end()) {
00602             liAllowed.erase(eraseItr);
00603           }
00604         }
00605       }
00606     }
00607 
00608     // Copy the allowed set into a member vector for use when constructing cost
00609     // vectors & matrices, and mapping PBQP solutions back to assignments.
00610     allowedSets[node] = AllowedSet(liAllowed.begin(), liAllowed.end());
00611 
00612     // Set the spill cost to the interval weight, or epsilon if the
00613     // interval weight is zero
00614     PBQP::PBQPNum spillCost = (li->weight != 0.0) ?
00615         li->weight : std::numeric_limits<PBQP::PBQPNum>::min();
00616 
00617     // Build a cost vector for this interval.
00618     problemNodes[node] =
00619       problem.addNode(
00620         buildCostVector(li->reg, allowedSets[node], coalesces, spillCost));
00621 
00622   }
00623 
00624 
00625   // Now add the cost matrices...
00626   for (unsigned node1 = 0; node1 < node2LI.size(); ++node1) {
00627     const LiveInterval *li = node2LI[node1];
00628 
00629     // Test for live range overlaps and insert interference matrices.
00630     for (unsigned node2 = node1 + 1; node2 < node2LI.size(); ++node2) {
00631       const LiveInterval *li2 = node2LI[node2];
00632 
00633       CoalesceMap::const_iterator cmItr =
00634         coalesces.find(RegPair(li->reg, li2->reg));
00635 
00636       PBQP::Matrix *m = 0;
00637 
00638       if (cmItr != coalesces.end()) {
00639         m = buildCoalescingMatrix(allowedSets[node1], allowedSets[node2],
00640                                   cmItr->second);
00641       }
00642       else if (li->overlaps(*li2)) {
00643         m = buildInterferenceMatrix(allowedSets[node1], allowedSets[node2]);
00644       }
00645 
00646       if (m != 0) {
00647         problem.addEdge(problemNodes[node1],
00648                         problemNodes[node2],
00649                         *m);
00650 
00651         delete m;
00652       }
00653     }
00654   }
00655 
00656   problem.assignNodeIDs();
00657 
00658   assert(problem.getNumNodes() == allowedSets.size());
00659   for (unsigned i = 0; i < allowedSets.size(); ++i) {
00660     assert(problem.getNodeItr(i) == problemNodes[i]);
00661   }
00662 /*
00663   std::cerr << "Allocating for " << problem.getNumNodes() << " nodes, "
00664             << problem.getNumEdges() << " edges.\n";
00665 
00666   problem.printDot(std::cerr);
00667 */
00668   // We're done, PBQP problem constructed - return it.
00669   return problem;
00670 }
00671 
00672 void PBQPRegAlloc::addStackInterval(const LiveInterval *spilled,
00673                                     MachineRegisterInfo* mri) {
00674   int stackSlot = vrm->getStackSlot(spilled->reg);
00675 
00676   if (stackSlot == VirtRegMap::NO_STACK_SLOT)
00677     return;
00678 
00679   const TargetRegisterClass *RC = mri->getRegClass(spilled->reg);
00680   LiveInterval &stackInterval = lss->getOrCreateInterval(stackSlot, RC);
00681 
00682   VNInfo *vni;
00683   if (stackInterval.getNumValNums() != 0)
00684     vni = stackInterval.getValNumInfo(0);
00685   else
00686     vni = stackInterval.getNextValue(0, 0, false, lss->getVNInfoAllocator());
00687 
00688   LiveInterval &rhsInterval = lis->getInterval(spilled->reg);
00689   stackInterval.MergeRangesInAsValue(rhsInterval, vni);
00690 }
00691 
00692 bool PBQPRegAlloc::mapPBQPToRegAlloc(const PBQP::Solution &solution) {
00693 
00694   static unsigned round = 0;
00695   (void) round;
00696 
00697   // Set to true if we have any spills
00698   bool anotherRoundNeeded = false;
00699 
00700   // Clear the existing allocation.
00701   vrm->clearAllVirt();
00702   
00703   // Iterate over the nodes mapping the PBQP solution to a register assignment.
00704   for (unsigned node = 0; node < node2LI.size(); ++node) {
00705     unsigned virtReg = node2LI[node]->reg,
00706              allocSelection = solution.getSelection(node);
00707 
00708 
00709     // If the PBQP solution is non-zero it's a physical register...
00710     if (allocSelection != 0) {
00711       // Get the physical reg, subtracting 1 to account for the spill option.
00712       unsigned physReg = allowedSets[node][allocSelection - 1];
00713 
00714       DEBUG(errs() << "VREG " << virtReg << " -> "
00715                    << tri->getName(physReg) << "\n");
00716 
00717       assert(physReg != 0);
00718 
00719       // Add to the virt reg map and update the used phys regs.
00720       vrm->assignVirt2Phys(virtReg, physReg);
00721     }
00722     // ...Otherwise it's a spill.
00723     else {
00724 
00725       // Make sure we ignore this virtual reg on the next round
00726       // of allocation
00727       vregIntervalsToAlloc.erase(&lis->getInterval(virtReg));
00728 
00729       // Insert spill ranges for this live range
00730       const LiveInterval *spillInterval = node2LI[node];
00731       double oldSpillWeight = spillInterval->weight;
00732       SmallVector<LiveInterval*, 8> spillIs;
00733       std::vector<LiveInterval*> newSpills =
00734         lis->addIntervalsForSpills(*spillInterval, spillIs, loopInfo, *vrm);
00735       addStackInterval(spillInterval, mri);
00736 
00737       (void) oldSpillWeight;
00738       DEBUG(errs() << "VREG " << virtReg << " -> SPILLED (Cost: "
00739                    << oldSpillWeight << ", New vregs: ");
00740 
00741       // Copy any newly inserted live intervals into the list of regs to
00742       // allocate.
00743       for (std::vector<LiveInterval*>::const_iterator
00744            itr = newSpills.begin(), end = newSpills.end();
00745            itr != end; ++itr) {
00746 
00747         assert(!(*itr)->empty() && "Empty spill range.");
00748 
00749         DEBUG(errs() << (*itr)->reg << " ");
00750 
00751         vregIntervalsToAlloc.insert(*itr);
00752       }
00753 
00754       DEBUG(errs() << ")\n");
00755 
00756       // We need another round if spill intervals were added.
00757       anotherRoundNeeded |= !newSpills.empty();
00758     }
00759   }
00760 
00761   return !anotherRoundNeeded;
00762 }
00763 
00764 void PBQPRegAlloc::finalizeAlloc() const {
00765   typedef LiveIntervals::iterator LIIterator;
00766   typedef LiveInterval::Ranges::const_iterator LRIterator;
00767 
00768   // First allocate registers for the empty intervals.
00769   for (LiveIntervalSet::const_iterator
00770    itr = emptyVRegIntervals.begin(), end = emptyVRegIntervals.end();
00771          itr != end; ++itr) {
00772     LiveInterval *li = *itr;
00773 
00774     unsigned physReg = vrm->getRegAllocPref(li->reg);
00775 
00776     if (physReg == 0) {
00777       const TargetRegisterClass *liRC = mri->getRegClass(li->reg);
00778       physReg = *liRC->allocation_order_begin(*mf);
00779     }
00780 
00781     vrm->assignVirt2Phys(li->reg, physReg);
00782   }
00783 
00784   // Finally iterate over the basic blocks to compute and set the live-in sets.
00785   SmallVector<MachineBasicBlock*, 8> liveInMBBs;
00786   MachineBasicBlock *entryMBB = &*mf->begin();
00787 
00788   for (LIIterator liItr = lis->begin(), liEnd = lis->end();
00789        liItr != liEnd; ++liItr) {
00790 
00791     const LiveInterval *li = liItr->second;
00792     unsigned reg = 0;
00793 
00794     // Get the physical register for this interval
00795     if (TargetRegisterInfo::isPhysicalRegister(li->reg)) {
00796       reg = li->reg;
00797     }
00798     else if (vrm->isAssignedReg(li->reg)) {
00799       reg = vrm->getPhys(li->reg);
00800     }
00801     else {
00802       // Ranges which are assigned a stack slot only are ignored.
00803       continue;
00804     }
00805 
00806     if (reg == 0) {
00807       // Filter out zero regs - they're for intervals that were spilled.
00808       continue;
00809     }
00810 
00811     // Iterate over the ranges of the current interval...
00812     for (LRIterator lrItr = li->begin(), lrEnd = li->end();
00813          lrItr != lrEnd; ++lrItr) {
00814 
00815       // Find the set of basic blocks which this range is live into...
00816       if (lis->findLiveInMBBs(lrItr->start, lrItr->end,  liveInMBBs)) {
00817         // And add the physreg for this interval to their live-in sets.
00818         for (unsigned i = 0; i < liveInMBBs.size(); ++i) {
00819           if (liveInMBBs[i] != entryMBB) {
00820             if (!liveInMBBs[i]->isLiveIn(reg)) {
00821               liveInMBBs[i]->addLiveIn(reg);
00822             }
00823           }
00824         }
00825         liveInMBBs.clear();
00826       }
00827     }
00828   }
00829 
00830 }
00831 
00832 bool PBQPRegAlloc::runOnMachineFunction(MachineFunction &MF) {
00833 
00834   mf = &MF;
00835   tm = &mf->getTarget();
00836   tri = tm->getRegisterInfo();
00837   tii = tm->getInstrInfo();
00838   mri = &mf->getRegInfo();
00839 
00840   lis = &getAnalysis<LiveIntervals>();
00841   lss = &getAnalysis<LiveStacks>();
00842   loopInfo = &getAnalysis<MachineLoopInfo>();
00843 
00844   vrm = &getAnalysis<VirtRegMap>();
00845 
00846   DEBUG(errs() << "PBQP2 Register Allocating for " << mf->getFunction()->getName() << "\n");
00847 
00848   // Allocator main loop:
00849   //
00850   // * Map current regalloc problem to a PBQP problem
00851   // * Solve the PBQP problem
00852   // * Map the solution back to a register allocation
00853   // * Spill if necessary
00854   //
00855   // This process is continued till no more spills are generated.
00856 
00857   // Find the vreg intervals in need of allocation.
00858   findVRegIntervalsToAlloc();
00859 
00860   // If there aren't any then we're done here.
00861   if (vregIntervalsToAlloc.empty() && emptyVRegIntervals.empty())
00862     return true;
00863 
00864   // If there are non-empty intervals allocate them using pbqp.
00865   if (!vregIntervalsToAlloc.empty()) {
00866 
00867     bool pbqpAllocComplete = false;
00868     unsigned round = 0;
00869 
00870     while (!pbqpAllocComplete) {
00871       DEBUG(errs() << "  PBQP Regalloc round " << round << ":\n");
00872 
00873       PBQP::SimpleGraph problem = constructPBQPProblem();
00874       PBQP::HeuristicSolver<PBQP::Heuristics::Briggs> solver;
00875       problem.assignNodeIDs();
00876       PBQP::Solution solution = solver.solve(problem);
00877 
00878       pbqpAllocComplete = mapPBQPToRegAlloc(solution);
00879 
00880       ++round;
00881     }
00882   }
00883 
00884   // Finalise allocation, allocate empty ranges.
00885   finalizeAlloc();
00886 
00887   vregIntervalsToAlloc.clear();
00888   emptyVRegIntervals.clear();
00889   li2Node.clear();
00890   node2LI.clear();
00891   allowedSets.clear();
00892 
00893   DEBUG(errs() << "Post alloc VirtRegMap:\n" << *vrm << "\n");
00894 
00895   // Run rewriter
00896   std::auto_ptr<VirtRegRewriter> rewriter(createVirtRegRewriter());
00897 
00898   rewriter->runOnMachineFunction(*mf, *vrm, lis);
00899 
00900   return true;
00901 }
00902 
00903 FunctionPass* llvm::createPBQPRegisterAllocator() {
00904   return new PBQPRegAlloc();
00905 }
00906 
00907 
00908 #undef DEBUG_TYPE