LCOV - code coverage report
Current view: top level - lib/CodeGen - RegAllocPBQP.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 241 277 87.0 %
Date: 2018-06-17 00:07:59 Functions: 31 38 81.6 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===- RegAllocPBQP.cpp ---- PBQP Register Allocator ----------------------===//
       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/ADT/ArrayRef.h"
      36             : #include "llvm/ADT/BitVector.h"
      37             : #include "llvm/ADT/DenseMap.h"
      38             : #include "llvm/ADT/DenseSet.h"
      39             : #include "llvm/ADT/STLExtras.h"
      40             : #include "llvm/ADT/SmallPtrSet.h"
      41             : #include "llvm/ADT/SmallVector.h"
      42             : #include "llvm/ADT/StringRef.h"
      43             : #include "llvm/Analysis/AliasAnalysis.h"
      44             : #include "llvm/CodeGen/CalcSpillWeights.h"
      45             : #include "llvm/CodeGen/LiveInterval.h"
      46             : #include "llvm/CodeGen/LiveIntervals.h"
      47             : #include "llvm/CodeGen/LiveRangeEdit.h"
      48             : #include "llvm/CodeGen/LiveStacks.h"
      49             : #include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
      50             : #include "llvm/CodeGen/MachineDominators.h"
      51             : #include "llvm/CodeGen/MachineFunction.h"
      52             : #include "llvm/CodeGen/MachineFunctionPass.h"
      53             : #include "llvm/CodeGen/MachineInstr.h"
      54             : #include "llvm/CodeGen/MachineLoopInfo.h"
      55             : #include "llvm/CodeGen/MachineRegisterInfo.h"
      56             : #include "llvm/CodeGen/PBQP/Graph.h"
      57             : #include "llvm/CodeGen/PBQP/Math.h"
      58             : #include "llvm/CodeGen/PBQP/Solution.h"
      59             : #include "llvm/CodeGen/PBQPRAConstraint.h"
      60             : #include "llvm/CodeGen/RegAllocRegistry.h"
      61             : #include "llvm/CodeGen/SlotIndexes.h"
      62             : #include "llvm/CodeGen/TargetRegisterInfo.h"
      63             : #include "llvm/CodeGen/TargetSubtargetInfo.h"
      64             : #include "llvm/CodeGen/VirtRegMap.h"
      65             : #include "llvm/Config/llvm-config.h"
      66             : #include "llvm/IR/Function.h"
      67             : #include "llvm/IR/Module.h"
      68             : #include "llvm/MC/MCRegisterInfo.h"
      69             : #include "llvm/Pass.h"
      70             : #include "llvm/Support/CommandLine.h"
      71             : #include "llvm/Support/Compiler.h"
      72             : #include "llvm/Support/Debug.h"
      73             : #include "llvm/Support/FileSystem.h"
      74             : #include "llvm/Support/Printable.h"
      75             : #include "llvm/Support/raw_ostream.h"
      76             : #include <algorithm>
      77             : #include <cassert>
      78             : #include <cstddef>
      79             : #include <limits>
      80             : #include <map>
      81             : #include <memory>
      82             : #include <queue>
      83             : #include <set>
      84             : #include <sstream>
      85             : #include <string>
      86             : #include <system_error>
      87             : #include <tuple>
      88             : #include <utility>
      89             : #include <vector>
      90             : 
      91             : using namespace llvm;
      92             : 
      93             : #define DEBUG_TYPE "regalloc"
      94             : 
      95             : static RegisterRegAlloc
      96      101169 : RegisterPBQPRepAlloc("pbqp", "PBQP register allocator",
      97             :                        createDefaultPBQPRegisterAllocator);
      98             : 
      99             : static cl::opt<bool>
     100      101169 : PBQPCoalescing("pbqp-coalescing",
     101      101169 :                 cl::desc("Attempt coalescing during PBQP register allocation."),
     102      303507 :                 cl::init(false), cl::Hidden);
     103             : 
     104             : #ifndef NDEBUG
     105             : static cl::opt<bool>
     106             : PBQPDumpGraphs("pbqp-dump-graphs",
     107             :                cl::desc("Dump graphs for each function/round in the compilation unit."),
     108             :                cl::init(false), cl::Hidden);
     109             : #endif
     110             : 
     111             : namespace {
     112             : 
     113             : ///
     114             : /// PBQP based allocators solve the register allocation problem by mapping
     115             : /// register allocation problems to Partitioned Boolean Quadratic
     116             : /// Programming problems.
     117          21 : class RegAllocPBQP : public MachineFunctionPass {
     118             : public:
     119             :   static char ID;
     120             : 
     121             :   /// Construct a PBQP register allocator.
     122           7 :   RegAllocPBQP(char *cPassID = nullptr)
     123           7 :       : MachineFunctionPass(ID), customPassID(cPassID) {
     124           7 :     initializeSlotIndexesPass(*PassRegistry::getPassRegistry());
     125           7 :     initializeLiveIntervalsPass(*PassRegistry::getPassRegistry());
     126           7 :     initializeLiveStacksPass(*PassRegistry::getPassRegistry());
     127           7 :     initializeVirtRegMapPass(*PassRegistry::getPassRegistry());
     128           7 :   }
     129             : 
     130             :   /// Return the pass name.
     131           7 :   StringRef getPassName() const override { return "PBQP Register Allocator"; }
     132             : 
     133             :   /// PBQP analysis usage.
     134             :   void getAnalysisUsage(AnalysisUsage &au) const override;
     135             : 
     136             :   /// Perform register allocation
     137             :   bool runOnMachineFunction(MachineFunction &MF) override;
     138             : 
     139           7 :   MachineFunctionProperties getRequiredProperties() const override {
     140          14 :     return MachineFunctionProperties().set(
     141           7 :         MachineFunctionProperties::Property::NoPHIs);
     142             :   }
     143             : 
     144             : private:
     145             :   using LI2NodeMap = std::map<const LiveInterval *, unsigned>;
     146             :   using Node2LIMap = std::vector<const LiveInterval *>;
     147             :   using AllowedSet = std::vector<unsigned>;
     148             :   using AllowedSetMap = std::vector<AllowedSet>;
     149             :   using RegPair = std::pair<unsigned, unsigned>;
     150             :   using CoalesceMap = std::map<RegPair, PBQP::PBQPNum>;
     151             :   using RegSet = std::set<unsigned>;
     152             : 
     153             :   char *customPassID;
     154             : 
     155             :   RegSet VRegsToAlloc, EmptyIntervalVRegs;
     156             : 
     157             :   /// Inst which is a def of an original reg and whose defs are already all
     158             :   /// dead after remat is saved in DeadRemats. The deletion of such inst is
     159             :   /// postponed till all the allocations are done, so its remat expr is
     160             :   /// always available for the remat of all the siblings of the original reg.
     161             :   SmallPtrSet<MachineInstr *, 32> DeadRemats;
     162             : 
     163             :   /// Finds the initial set of vreg intervals to allocate.
     164             :   void findVRegIntervalsToAlloc(const MachineFunction &MF, LiveIntervals &LIS);
     165             : 
     166             :   /// Constructs an initial graph.
     167             :   void initializeGraph(PBQPRAGraph &G, VirtRegMap &VRM, Spiller &VRegSpiller);
     168             : 
     169             :   /// Spill the given VReg.
     170             :   void spillVReg(unsigned VReg, SmallVectorImpl<unsigned> &NewIntervals,
     171             :                  MachineFunction &MF, LiveIntervals &LIS, VirtRegMap &VRM,
     172             :                  Spiller &VRegSpiller);
     173             : 
     174             :   /// Given a solved PBQP problem maps this solution back to a register
     175             :   /// assignment.
     176             :   bool mapPBQPToRegAlloc(const PBQPRAGraph &G,
     177             :                          const PBQP::Solution &Solution,
     178             :                          VirtRegMap &VRM,
     179             :                          Spiller &VRegSpiller);
     180             : 
     181             :   /// Postprocessing before final spilling. Sets basic block "live in"
     182             :   /// variables.
     183             :   void finalizeAlloc(MachineFunction &MF, LiveIntervals &LIS,
     184             :                      VirtRegMap &VRM) const;
     185             : 
     186             :   void postOptimization(Spiller &VRegSpiller, LiveIntervals &LIS);
     187             : };
     188             : 
     189             : char RegAllocPBQP::ID = 0;
     190             : 
     191             : /// Set spill costs for each node in the PBQP reg-alloc graph.
     192          14 : class SpillCosts : public PBQPRAConstraint {
     193             : public:
     194           8 :   void apply(PBQPRAGraph &G) override {
     195           8 :     LiveIntervals &LIS = G.getMetadata().LIS;
     196             : 
     197             :     // A minimum spill costs, so that register constraints can can be set
     198             :     // without normalization in the [0.0:MinSpillCost( interval.
     199             :     const PBQP::PBQPNum MinSpillCost = 10.0;
     200             : 
     201         169 :     for (auto NId : G.nodeIds()) {
     202             :       PBQP::PBQPNum SpillCost =
     203         153 :         LIS.getInterval(G.getNodeMetadata(NId).getVReg()).weight;
     204         153 :       if (SpillCost == 0.0)
     205             :         SpillCost = std::numeric_limits<PBQP::PBQPNum>::min();
     206             :       else
     207         153 :         SpillCost += MinSpillCost;
     208         153 :       PBQPRAGraph::RawVector NodeCosts(G.getNodeCosts(NId));
     209         153 :       NodeCosts[PBQP::RegAlloc::getSpillOptionIdx()] = SpillCost;
     210         306 :       G.setNodeCosts(NId, std::move(NodeCosts));
     211             :     }
     212           8 :   }
     213             : };
     214             : 
     215             : /// Add interference edges between overlapping vregs.
     216          14 : class Interference : public PBQPRAConstraint {
     217             : private:
     218             :   using AllowedRegVecPtr = const PBQP::RegAlloc::AllowedRegVector *;
     219             :   using IKey = std::pair<AllowedRegVecPtr, AllowedRegVecPtr>;
     220             :   using IMatrixCache = DenseMap<IKey, PBQPRAGraph::MatrixPtr>;
     221             :   using DisjointAllowedRegsCache = DenseSet<IKey>;
     222             :   using IEdgeKey = std::pair<PBQP::GraphBase::NodeId, PBQP::GraphBase::NodeId>;
     223             :   using IEdgeCache = DenseSet<IEdgeKey>;
     224             : 
     225        1071 :   bool haveDisjointAllowedRegs(const PBQPRAGraph &G, PBQPRAGraph::NodeId NId,
     226             :                                PBQPRAGraph::NodeId MId,
     227             :                                const DisjointAllowedRegsCache &D) const {
     228             :     const auto *NRegs = &G.getNodeMetadata(NId).getAllowedRegs();
     229             :     const auto *MRegs = &G.getNodeMetadata(MId).getAllowedRegs();
     230             : 
     231        1071 :     if (NRegs == MRegs)
     232             :       return false;
     233             : 
     234         630 :     if (NRegs < MRegs)
     235          82 :       return D.count(IKey(NRegs, MRegs)) > 0;
     236             : 
     237         548 :     return D.count(IKey(MRegs, NRegs)) > 0;
     238             :   }
     239             : 
     240          12 :   void setDisjointAllowedRegs(const PBQPRAGraph &G, PBQPRAGraph::NodeId NId,
     241             :                               PBQPRAGraph::NodeId MId,
     242             :                               DisjointAllowedRegsCache &D) {
     243             :     const auto *NRegs = &G.getNodeMetadata(NId).getAllowedRegs();
     244             :     const auto *MRegs = &G.getNodeMetadata(MId).getAllowedRegs();
     245             : 
     246             :     assert(NRegs != MRegs && "AllowedRegs can not be disjoint with itself");
     247             : 
     248          12 :     if (NRegs < MRegs)
     249           0 :       D.insert(IKey(NRegs, MRegs));
     250             :     else
     251          12 :       D.insert(IKey(MRegs, NRegs));
     252          12 :   }
     253             : 
     254             :   // Holds (Interval, CurrentSegmentID, and NodeId). The first two are required
     255             :   // for the fast interference graph construction algorithm. The last is there
     256             :   // to save us from looking up node ids via the VRegToNode map in the graph
     257             :   // metadata.
     258             :   using IntervalInfo =
     259             :       std::tuple<LiveInterval*, size_t, PBQP::GraphBase::NodeId>;
     260             : 
     261             :   static SlotIndex getStartPoint(const IntervalInfo &I) {
     262        2921 :     return std::get<0>(I)->segments[std::get<1>(I)].start;
     263             :   }
     264             : 
     265             :   static SlotIndex getEndPoint(const IntervalInfo &I) {
     266        2807 :     return std::get<0>(I)->segments[std::get<1>(I)].end;
     267             :   }
     268             : 
     269             :   static PBQP::GraphBase::NodeId getNodeId(const IntervalInfo &I) {
     270        1238 :     return std::get<2>(I);
     271             :   }
     272             : 
     273         781 :   static bool lowestStartPoint(const IntervalInfo &I1,
     274             :                                const IntervalInfo &I2) {
     275             :     // Condition reversed because priority queue has the *highest* element at
     276             :     // the front, rather than the lowest.
     277         781 :     return getStartPoint(I1) > getStartPoint(I2);
     278             :   }
     279             : 
     280         743 :   static bool lowestEndPoint(const IntervalInfo &I1,
     281             :                              const IntervalInfo &I2) {
     282             :     SlotIndex E1 = getEndPoint(I1);
     283             :     SlotIndex E2 = getEndPoint(I2);
     284             : 
     285         743 :     if (E1 < E2)
     286             :       return true;
     287             : 
     288         361 :     if (E1 > E2)
     289             :       return false;
     290             : 
     291             :     // If two intervals end at the same point, we need a way to break the tie or
     292             :     // the set will assume they're actually equal and refuse to insert a
     293             :     // "duplicate". Just compare the vregs - fast and guaranteed unique.
     294         167 :     return std::get<0>(I1)->reg < std::get<0>(I2)->reg;
     295             :   }
     296             : 
     297             :   static bool isAtLastSegment(const IntervalInfo &I) {
     298         142 :     return std::get<1>(I) == std::get<0>(I)->size() - 1;
     299             :   }
     300             : 
     301             :   static IntervalInfo nextSegment(const IntervalInfo &I) {
     302          14 :     return std::make_tuple(std::get<0>(I), std::get<1>(I) + 1, std::get<2>(I));
     303             :   }
     304             : 
     305             : public:
     306           8 :   void apply(PBQPRAGraph &G) override {
     307             :     // The following is loosely based on the linear scan algorithm introduced in
     308             :     // "Linear Scan Register Allocation" by Poletto and Sarkar. This version
     309             :     // isn't linear, because the size of the active set isn't bound by the
     310             :     // number of registers, but rather the size of the largest clique in the
     311             :     // graph. Still, we expect this to be better than N^2.
     312           8 :     LiveIntervals &LIS = G.getMetadata().LIS;
     313             : 
     314             :     // Interferenc matrices are incredibly regular - they're only a function of
     315             :     // the allowed sets, so we cache them to avoid the overhead of constructing
     316             :     // and uniquing them.
     317             :     IMatrixCache C;
     318             : 
     319             :     // Finding an edge is expensive in the worst case (O(max_clique(G))). So
     320             :     // cache locally edges we have already seen.
     321             :     IEdgeCache EC;
     322             : 
     323             :     // Cache known disjoint allowed registers pairs
     324             :     DisjointAllowedRegsCache D;
     325             : 
     326             :     using IntervalSet = std::set<IntervalInfo, decltype(&lowestEndPoint)>;
     327             :     using IntervalQueue =
     328             :         std::priority_queue<IntervalInfo, std::vector<IntervalInfo>,
     329             :                             decltype(&lowestStartPoint)>;
     330             :     IntervalSet Active(lowestEndPoint);
     331          16 :     IntervalQueue Inactive(lowestStartPoint);
     332             : 
     333             :     // Start by building the inactive set.
     334         169 :     for (auto NId : G.nodeIds()) {
     335         153 :       unsigned VReg = G.getNodeMetadata(NId).getVReg();
     336         153 :       LiveInterval &LI = LIS.getInterval(VReg);
     337             :       assert(!LI.empty() && "PBQP graph contains node for empty interval");
     338         153 :       Inactive.push(std::make_tuple(&LI, 0, NId));
     339             :     }
     340             : 
     341         342 :     while (!Inactive.empty()) {
     342             :       // Tentatively grab the "next" interval - this choice may be overriden
     343             :       // below.
     344         167 :       IntervalInfo Cur = Inactive.top();
     345             : 
     346             :       // Retire any active intervals that end before Cur starts.
     347             :       IntervalSet::iterator RetireItr = Active.begin();
     348         598 :       while (RetireItr != Active.end() &&
     349             :              (getEndPoint(*RetireItr) <= getStartPoint(Cur))) {
     350             :         // If this interval has subsequent segments, add the next one to the
     351             :         // inactive list.
     352         142 :         if (!isAtLastSegment(*RetireItr))
     353          14 :           Inactive.push(nextSegment(*RetireItr));
     354             : 
     355             :         ++RetireItr;
     356             :       }
     357             :       Active.erase(Active.begin(), RetireItr);
     358             : 
     359             :       // One of the newly retired segments may actually start before the
     360             :       // Cur segment, so re-grab the front of the inactive list.
     361             :       Cur = Inactive.top();
     362         167 :       Inactive.pop();
     363             : 
     364             :       // At this point we know that Cur overlaps all active intervals. Add the
     365             :       // interference edges.
     366         167 :       PBQP::GraphBase::NodeId NId = getNodeId(Cur);
     367        1238 :       for (const auto &A : Active) {
     368        1071 :         PBQP::GraphBase::NodeId MId = getNodeId(A);
     369             : 
     370             :         // Do not add an edge when the nodes' allowed registers do not
     371             :         // intersect: there is obviously no interference.
     372        1071 :         if (haveDisjointAllowedRegs(G, NId, MId, D))
     373        1004 :           continue;
     374             : 
     375             :         // Check that we haven't already added this edge
     376             :         IEdgeKey EK(std::min(NId, MId), std::max(NId, MId));
     377          48 :         if (EC.count(EK))
     378          48 :           continue;
     379             : 
     380             :         // This is a new edge - add it to the graph.
     381         545 :         if (!createInterferenceEdge(G, NId, MId, C))
     382          12 :           setDisjointAllowedRegs(G, NId, MId, D);
     383             :         else
     384             :           EC.insert(EK);
     385             :       }
     386             : 
     387             :       // Finally, add Cur to the Active set.
     388             :       Active.insert(Cur);
     389             :     }
     390           8 :   }
     391             : 
     392             : private:
     393             :   // Create an Interference edge and add it to the graph, unless it is
     394             :   // a null matrix, meaning the nodes' allowed registers do not have any
     395             :   // interference. This case occurs frequently between integer and floating
     396             :   // point registers for example.
     397             :   // return true iff both nodes interferes.
     398         545 :   bool createInterferenceEdge(PBQPRAGraph &G,
     399             :                               PBQPRAGraph::NodeId NId, PBQPRAGraph::NodeId MId,
     400             :                               IMatrixCache &C) {
     401             :     const TargetRegisterInfo &TRI =
     402         545 :         *G.getMetadata().MF.getSubtarget().getRegisterInfo();
     403             :     const auto &NRegs = G.getNodeMetadata(NId).getAllowedRegs();
     404             :     const auto &MRegs = G.getNodeMetadata(MId).getAllowedRegs();
     405             : 
     406             :     // Try looking the edge costs up in the IMatrixCache first.
     407             :     IKey K(&NRegs, &MRegs);
     408         545 :     IMatrixCache::iterator I = C.find(K);
     409         545 :     if (I != C.end()) {
     410        1488 :       G.addEdgeBypassingCostAllocator(NId, MId, I->second);
     411             :       return true;
     412             :     }
     413             : 
     414          49 :     PBQPRAGraph::RawMatrix M(NRegs.size() + 1, MRegs.size() + 1, 0);
     415             :     bool NodesInterfere = false;
     416        2743 :     for (unsigned I = 0; I != NRegs.size(); ++I) {
     417        1347 :       unsigned PRegN = NRegs[I];
     418       77557 :       for (unsigned J = 0; J != MRegs.size(); ++J) {
     419       38105 :         unsigned PRegM = MRegs[J];
     420       38105 :         if (TRI.regsOverlap(PRegN, PRegM)) {
     421        1826 :           M[I + 1][J + 1] = std::numeric_limits<PBQP::PBQPNum>::infinity();
     422             :           NodesInterfere = true;
     423             :         }
     424             :       }
     425             :     }
     426             : 
     427          49 :     if (!NodesInterfere)
     428             :       return false;
     429             : 
     430         111 :     PBQPRAGraph::EdgeId EId = G.addEdge(NId, MId, std::move(M));
     431             :     C[K] = G.getEdgeCostsPtr(EId);
     432             : 
     433             :     return true;
     434             :   }
     435             : };
     436             : 
     437          10 : class Coalescing : public PBQPRAConstraint {
     438             : public:
     439           5 :   void apply(PBQPRAGraph &G) override {
     440           5 :     MachineFunction &MF = G.getMetadata().MF;
     441           5 :     MachineBlockFrequencyInfo &MBFI = G.getMetadata().MBFI;
     442           5 :     CoalescerPair CP(*MF.getSubtarget().getRegisterInfo());
     443             : 
     444             :     // Scan the machine function and add a coalescing cost whenever CoalescerPair
     445             :     // gives the Ok.
     446          13 :     for (const auto &MBB : MF) {
     447         178 :       for (const auto &MI : MBB) {
     448             :         // Skip not-coalescable or already coalesced copies.
     449         162 :         if (!CP.setRegisters(&MI) || CP.getSrcReg() == CP.getDstReg())
     450         138 :           continue;
     451             : 
     452             :         unsigned DstReg = CP.getDstReg();
     453             :         unsigned SrcReg = CP.getSrcReg();
     454             : 
     455          24 :         const float Scale = 1.0f / MBFI.getEntryFreq();
     456          48 :         PBQP::PBQPNum CBenefit = MBFI.getBlockFreq(&MBB).getFrequency() * Scale;
     457             : 
     458          24 :         if (CP.isPhys()) {
     459          20 :           if (!MF.getRegInfo().isAllocatable(DstReg))
     460           0 :             continue;
     461             : 
     462             :           PBQPRAGraph::NodeId NId = G.getMetadata().getNodeIdForVReg(SrcReg);
     463             : 
     464             :           const PBQPRAGraph::NodeMetadata::AllowedRegVector &Allowed =
     465             :             G.getNodeMetadata(NId).getAllowedRegs();
     466             : 
     467             :           unsigned PRegOpt = 0;
     468        1147 :           while (PRegOpt < Allowed.size() && Allowed[PRegOpt] != DstReg)
     469         369 :             ++PRegOpt;
     470             : 
     471          20 :           if (PRegOpt < Allowed.size()) {
     472          20 :             PBQPRAGraph::RawVector NewCosts(G.getNodeCosts(NId));
     473          40 :             NewCosts[PRegOpt + 1] -= CBenefit;
     474          60 :             G.setNodeCosts(NId, std::move(NewCosts));
     475             :           }
     476             :         } else {
     477             :           PBQPRAGraph::NodeId N1Id = G.getMetadata().getNodeIdForVReg(DstReg);
     478             :           PBQPRAGraph::NodeId N2Id = G.getMetadata().getNodeIdForVReg(SrcReg);
     479             :           const PBQPRAGraph::NodeMetadata::AllowedRegVector *Allowed1 =
     480             :             &G.getNodeMetadata(N1Id).getAllowedRegs();
     481             :           const PBQPRAGraph::NodeMetadata::AllowedRegVector *Allowed2 =
     482             :             &G.getNodeMetadata(N2Id).getAllowedRegs();
     483             : 
     484             :           PBQPRAGraph::EdgeId EId = G.findEdge(N1Id, N2Id);
     485           4 :           if (EId == G.invalidEdgeId()) {
     486           0 :             PBQPRAGraph::RawMatrix Costs(Allowed1->size() + 1,
     487           0 :                                          Allowed2->size() + 1, 0);
     488           0 :             addVirtRegCoalesce(Costs, *Allowed1, *Allowed2, CBenefit);
     489           0 :             G.addEdge(N1Id, N2Id, std::move(Costs));
     490             :           } else {
     491           4 :             if (G.getEdgeNode1Id(EId) == N2Id) {
     492             :               std::swap(N1Id, N2Id);
     493             :               std::swap(Allowed1, Allowed2);
     494             :             }
     495           4 :             PBQPRAGraph::RawMatrix Costs(G.getEdgeCosts(EId));
     496           4 :             addVirtRegCoalesce(Costs, *Allowed1, *Allowed2, CBenefit);
     497          12 :             G.updateEdgeCosts(EId, std::move(Costs));
     498             :           }
     499             :         }
     500             :       }
     501             :     }
     502           5 :   }
     503             : 
     504             : private:
     505           4 :   void addVirtRegCoalesce(
     506             :                     PBQPRAGraph::RawMatrix &CostMat,
     507             :                     const PBQPRAGraph::NodeMetadata::AllowedRegVector &Allowed1,
     508             :                     const PBQPRAGraph::NodeMetadata::AllowedRegVector &Allowed2,
     509             :                     PBQP::PBQPNum Benefit) {
     510             :     assert(CostMat.getRows() == Allowed1.size() + 1 && "Size mismatch.");
     511             :     assert(CostMat.getCols() == Allowed2.size() + 1 && "Size mismatch.");
     512         258 :     for (unsigned I = 0; I != Allowed1.size(); ++I) {
     513         127 :       unsigned PReg1 = Allowed1[I];
     514        8193 :       for (unsigned J = 0; J != Allowed2.size(); ++J) {
     515        4033 :         unsigned PReg2 = Allowed2[J];
     516        4033 :         if (PReg1 == PReg2)
     517         254 :           CostMat[I + 1][J + 1] -= Benefit;
     518             :       }
     519             :     }
     520           4 :   }
     521             : };
     522             : 
     523             : } // end anonymous namespace
     524             : 
     525             : // Out-of-line destructor/anchor for PBQPRAConstraint.
     526             : PBQPRAConstraint::~PBQPRAConstraint() = default;
     527             : 
     528           0 : void PBQPRAConstraint::anchor() {}
     529             : 
     530           0 : void PBQPRAConstraintList::anchor() {}
     531             : 
     532           7 : void RegAllocPBQP::getAnalysisUsage(AnalysisUsage &au) const {
     533           7 :   au.setPreservesCFG();
     534             :   au.addRequired<AAResultsWrapperPass>();
     535             :   au.addPreserved<AAResultsWrapperPass>();
     536             :   au.addRequired<SlotIndexes>();
     537             :   au.addPreserved<SlotIndexes>();
     538             :   au.addRequired<LiveIntervals>();
     539             :   au.addPreserved<LiveIntervals>();
     540             :   //au.addRequiredID(SplitCriticalEdgesID);
     541           7 :   if (customPassID)
     542           0 :     au.addRequiredID(*customPassID);
     543             :   au.addRequired<LiveStacks>();
     544             :   au.addPreserved<LiveStacks>();
     545             :   au.addRequired<MachineBlockFrequencyInfo>();
     546             :   au.addPreserved<MachineBlockFrequencyInfo>();
     547             :   au.addRequired<MachineLoopInfo>();
     548             :   au.addPreserved<MachineLoopInfo>();
     549             :   au.addRequired<MachineDominatorTree>();
     550             :   au.addPreserved<MachineDominatorTree>();
     551             :   au.addRequired<VirtRegMap>();
     552             :   au.addPreserved<VirtRegMap>();
     553           7 :   MachineFunctionPass::getAnalysisUsage(au);
     554           7 : }
     555             : 
     556           7 : void RegAllocPBQP::findVRegIntervalsToAlloc(const MachineFunction &MF,
     557             :                                             LiveIntervals &LIS) {
     558           7 :   const MachineRegisterInfo &MRI = MF.getRegInfo();
     559             : 
     560             :   // Iterate over all live ranges.
     561         419 :   for (unsigned I = 0, E = MRI.getNumVirtRegs(); I != E; ++I) {
     562         206 :     unsigned Reg = TargetRegisterInfo::index2VirtReg(I);
     563         206 :     if (MRI.reg_nodbg_empty(Reg))
     564          63 :       continue;
     565             :     VRegsToAlloc.insert(Reg);
     566             :   }
     567           7 : }
     568             : 
     569        4104 : static bool isACalleeSavedRegister(unsigned reg, const TargetRegisterInfo &TRI,
     570             :                                    const MachineFunction &MF) {
     571        4104 :   const MCPhysReg *CSR = MF.getRegInfo().getCalleeSavedRegs();
     572      143072 :   for (unsigned i = 0; CSR[i] != 0; ++i)
     573       70757 :     if (TRI.regsOverlap(reg, CSR[i]))
     574             :       return true;
     575             :   return false;
     576             : }
     577             : 
     578           8 : void RegAllocPBQP::initializeGraph(PBQPRAGraph &G, VirtRegMap &VRM,
     579             :                                    Spiller &VRegSpiller) {
     580           8 :   MachineFunction &MF = G.getMetadata().MF;
     581             : 
     582           8 :   LiveIntervals &LIS = G.getMetadata().LIS;
     583           8 :   const MachineRegisterInfo &MRI = G.getMetadata().MF.getRegInfo();
     584             :   const TargetRegisterInfo &TRI =
     585           8 :       *G.getMetadata().MF.getSubtarget().getRegisterInfo();
     586             : 
     587             :   std::vector<unsigned> Worklist(VRegsToAlloc.begin(), VRegsToAlloc.end());
     588             : 
     589             :   std::map<unsigned, std::vector<unsigned>> VRegAllowedMap;
     590             : 
     591         163 :   while (!Worklist.empty()) {
     592         155 :     unsigned VReg = Worklist.back();
     593             :     Worklist.pop_back();
     594             : 
     595         155 :     LiveInterval &VRegLI = LIS.getInterval(VReg);
     596             : 
     597             :     // If this is an empty interval move it to the EmptyIntervalVRegs set then
     598             :     // continue.
     599         157 :     if (VRegLI.empty()) {
     600           2 :       EmptyIntervalVRegs.insert(VRegLI.reg);
     601             :       VRegsToAlloc.erase(VRegLI.reg);
     602           4 :       continue;
     603             :     }
     604             : 
     605         153 :     const TargetRegisterClass *TRC = MRI.getRegClass(VReg);
     606             : 
     607             :     // Record any overlaps with regmask operands.
     608             :     BitVector RegMaskOverlaps;
     609         153 :     LIS.checkRegMaskInterference(VRegLI, RegMaskOverlaps);
     610             : 
     611             :     // Compute an initial allowed set for the current vreg.
     612             :     std::vector<unsigned> VRegAllowed;
     613             :     ArrayRef<MCPhysReg> RawPRegOrder = TRC->getRawAllocationOrder(MF);
     614        8965 :     for (unsigned I = 0; I != RawPRegOrder.size(); ++I) {
     615        4406 :       unsigned PReg = RawPRegOrder[I];
     616        4406 :       if (MRI.isReserved(PReg))
     617         373 :         continue;
     618             : 
     619             :       // vregLI crosses a regmask operand that clobbers preg.
     620        4665 :       if (!RegMaskOverlaps.empty() && !RegMaskOverlaps.test(PReg))
     621         198 :         continue;
     622             : 
     623             :       // vregLI overlaps fixed regunit interference.
     624             :       bool Interference = false;
     625        8383 :       for (MCRegUnitIterator Units(PReg, &TRI); Units.isValid(); ++Units) {
     626        8746 :         if (VRegLI.overlaps(LIS.getRegUnit(*Units))) {
     627             :           Interference = true;
     628             :           break;
     629             :         }
     630             :       }
     631        4137 :       if (Interference)
     632          33 :         continue;
     633             : 
     634             :       // preg is usable for this virtual register.
     635        4104 :       VRegAllowed.push_back(PReg);
     636             :     }
     637             : 
     638             :     // Check for vregs that have no allowed registers. These should be
     639             :     // pre-spilled and the new vregs added to the worklist.
     640         153 :     if (VRegAllowed.empty()) {
     641             :       SmallVector<unsigned, 8> NewVRegs;
     642           0 :       spillVReg(VReg, NewVRegs, MF, LIS, VRM, VRegSpiller);
     643             :       Worklist.insert(Worklist.end(), NewVRegs.begin(), NewVRegs.end());
     644             :       continue;
     645             :     } else
     646         153 :       VRegAllowedMap[VReg] = std::move(VRegAllowed);
     647             :   }
     648             : 
     649         161 :   for (auto &KV : VRegAllowedMap) {
     650         153 :     auto VReg = KV.first;
     651             : 
     652             :     // Move empty intervals to the EmptyIntervalVReg set.
     653         306 :     if (LIS.getInterval(VReg).empty()) {
     654             :       EmptyIntervalVRegs.insert(VReg);
     655             :       VRegsToAlloc.erase(VReg);
     656           0 :       continue;
     657             :     }
     658             : 
     659         153 :     auto &VRegAllowed = KV.second;
     660             : 
     661         306 :     PBQPRAGraph::RawVector NodeCosts(VRegAllowed.size() + 1, 0);
     662             : 
     663             :     // Tweak cost of callee saved registers, as using then force spilling and
     664             :     // restoring them. This would only happen in the prologue / epilogue though.
     665       12618 :     for (unsigned i = 0; i != VRegAllowed.size(); ++i)
     666        4104 :       if (isACalleeSavedRegister(VRegAllowed[i], TRI, MF))
     667        2546 :         NodeCosts[1 + i] += 1.0;
     668             : 
     669         459 :     PBQPRAGraph::NodeId NId = G.addNode(std::move(NodeCosts));
     670         153 :     G.getNodeMetadata(NId).setVReg(VReg);
     671             :     G.getNodeMetadata(NId).setAllowedRegs(
     672         459 :       G.getMetadata().getAllowedRegs(std::move(VRegAllowed)));
     673         153 :     G.getMetadata().setNodeIdForVReg(VReg, NId);
     674             :   }
     675           8 : }
     676             : 
     677          10 : void RegAllocPBQP::spillVReg(unsigned VReg,
     678             :                              SmallVectorImpl<unsigned> &NewIntervals,
     679             :                              MachineFunction &MF, LiveIntervals &LIS,
     680             :                              VirtRegMap &VRM, Spiller &VRegSpiller) {
     681             :   VRegsToAlloc.erase(VReg);
     682          10 :   LiveRangeEdit LRE(&LIS.getInterval(VReg), NewIntervals, MF, LIS, &VRM,
     683          20 :                     nullptr, &DeadRemats);
     684          10 :   VRegSpiller.spill(LRE);
     685             : 
     686          10 :   const TargetRegisterInfo &TRI = *MF.getSubtarget().getRegisterInfo();
     687             :   (void)TRI;
     688             :   LLVM_DEBUG(dbgs() << "VREG " << printReg(VReg, &TRI) << " -> SPILLED (Cost: "
     689             :                     << LRE.getParent().weight << ", New vregs: ");
     690             : 
     691             :   // Copy any newly inserted live intervals into the list of regs to
     692             :   // allocate.
     693          14 :   for (LiveRangeEdit::iterator I = LRE.begin(), E = LRE.end();
     694          14 :        I != E; ++I) {
     695           4 :     const LiveInterval &LI = LIS.getInterval(*I);
     696             :     assert(!LI.empty() && "Empty spill range.");
     697             :     LLVM_DEBUG(dbgs() << printReg(LI.reg, &TRI) << " ");
     698           4 :     VRegsToAlloc.insert(LI.reg);
     699             :   }
     700             : 
     701             :   LLVM_DEBUG(dbgs() << ")\n");
     702          10 : }
     703             : 
     704           8 : bool RegAllocPBQP::mapPBQPToRegAlloc(const PBQPRAGraph &G,
     705             :                                      const PBQP::Solution &Solution,
     706             :                                      VirtRegMap &VRM,
     707             :                                      Spiller &VRegSpiller) {
     708           8 :   MachineFunction &MF = G.getMetadata().MF;
     709           8 :   LiveIntervals &LIS = G.getMetadata().LIS;
     710           8 :   const TargetRegisterInfo &TRI = *MF.getSubtarget().getRegisterInfo();
     711             :   (void)TRI;
     712             : 
     713             :   // Set to true if we have any spills
     714             :   bool AnotherRoundNeeded = false;
     715             : 
     716             :   // Clear the existing allocation.
     717             :   VRM.clearAllVirt();
     718             : 
     719             :   // Iterate over the nodes mapping the PBQP solution to a register
     720             :   // assignment.
     721         169 :   for (auto NId : G.nodeIds()) {
     722         153 :     unsigned VReg = G.getNodeMetadata(NId).getVReg();
     723             :     unsigned AllocOption = Solution.getSelection(NId);
     724             : 
     725         153 :     if (AllocOption != PBQP::RegAlloc::getSpillOptionIdx()) {
     726         143 :       unsigned PReg = G.getNodeMetadata(NId).getAllowedRegs()[AllocOption - 1];
     727             :       LLVM_DEBUG(dbgs() << "VREG " << printReg(VReg, &TRI) << " -> "
     728             :                         << TRI.getName(PReg) << "\n");
     729             :       assert(PReg != 0 && "Invalid preg selected.");
     730         143 :       VRM.assignVirt2Phys(VReg, PReg);
     731             :     } else {
     732             :       // Spill VReg. If this introduces new intervals we'll need another round
     733             :       // of allocation.
     734             :       SmallVector<unsigned, 8> NewVRegs;
     735          10 :       spillVReg(VReg, NewVRegs, MF, LIS, VRM, VRegSpiller);
     736          10 :       AnotherRoundNeeded |= !NewVRegs.empty();
     737             :     }
     738             :   }
     739             : 
     740           8 :   return !AnotherRoundNeeded;
     741             : }
     742             : 
     743           7 : void RegAllocPBQP::finalizeAlloc(MachineFunction &MF,
     744             :                                  LiveIntervals &LIS,
     745             :                                  VirtRegMap &VRM) const {
     746           7 :   MachineRegisterInfo &MRI = MF.getRegInfo();
     747             : 
     748             :   // First allocate registers for the empty intervals.
     749             :   for (RegSet::const_iterator
     750             :          I = EmptyIntervalVRegs.begin(), E = EmptyIntervalVRegs.end();
     751           9 :          I != E; ++I) {
     752           2 :     LiveInterval &LI = LIS.getInterval(*I);
     753             : 
     754           2 :     unsigned PReg = MRI.getSimpleHint(LI.reg);
     755             : 
     756           2 :     if (PReg == 0) {
     757             :       const TargetRegisterClass &RC = *MRI.getRegClass(LI.reg);
     758             :       const ArrayRef<MCPhysReg> RawPRegOrder = RC.getRawAllocationOrder(MF);
     759           6 :       for (unsigned CandidateReg : RawPRegOrder) {
     760           8 :         if (!VRM.getRegInfo().isReserved(CandidateReg)) {
     761             :           PReg = CandidateReg;
     762             :           break;
     763             :         }
     764             :       }
     765             :       assert(PReg &&
     766             :              "No un-reserved physical registers in this register class");
     767             :     }
     768             : 
     769           2 :     VRM.assignVirt2Phys(LI.reg, PReg);
     770             :   }
     771           7 : }
     772             : 
     773           7 : void RegAllocPBQP::postOptimization(Spiller &VRegSpiller, LiveIntervals &LIS) {
     774           7 :   VRegSpiller.postOptimization();
     775             :   /// Remove dead defs because of rematerialization.
     776           7 :   for (auto DeadInst : DeadRemats) {
     777           0 :     LIS.RemoveMachineInstrFromMaps(*DeadInst);
     778           0 :     DeadInst->eraseFromParent();
     779             :   }
     780           7 :   DeadRemats.clear();
     781           7 : }
     782             : 
     783         132 : static inline float normalizePBQPSpillWeight(float UseDefFreq, unsigned Size,
     784             :                                          unsigned NumInstr) {
     785             :   // All intervals have a spill weight that is mostly proportional to the number
     786             :   // of uses, with uses in loops having a bigger weight.
     787         264 :   return NumInstr * normalizeSpillWeight(UseDefFreq, Size, 1);
     788             : }
     789             : 
     790           7 : bool RegAllocPBQP::runOnMachineFunction(MachineFunction &MF) {
     791           7 :   LiveIntervals &LIS = getAnalysis<LiveIntervals>();
     792             :   MachineBlockFrequencyInfo &MBFI =
     793           7 :     getAnalysis<MachineBlockFrequencyInfo>();
     794             : 
     795           7 :   VirtRegMap &VRM = getAnalysis<VirtRegMap>();
     796             : 
     797           7 :   calculateSpillWeightsAndHints(LIS, MF, &VRM, getAnalysis<MachineLoopInfo>(),
     798             :                                 MBFI, normalizePBQPSpillWeight);
     799             : 
     800           7 :   std::unique_ptr<Spiller> VRegSpiller(createInlineSpiller(*this, MF, VRM));
     801             : 
     802           7 :   MF.getRegInfo().freezeReservedRegs(MF);
     803             : 
     804             :   LLVM_DEBUG(dbgs() << "PBQP Register Allocating for " << MF.getName() << "\n");
     805             : 
     806             :   // Allocator main loop:
     807             :   //
     808             :   // * Map current regalloc problem to a PBQP problem
     809             :   // * Solve the PBQP problem
     810             :   // * Map the solution back to a register allocation
     811             :   // * Spill if necessary
     812             :   //
     813             :   // This process is continued till no more spills are generated.
     814             : 
     815             :   // Find the vreg intervals in need of allocation.
     816           7 :   findVRegIntervalsToAlloc(MF, LIS);
     817             : 
     818             : #ifndef NDEBUG
     819             :   const Function &F = MF.getFunction();
     820             :   std::string FullyQualifiedName =
     821             :     F.getParent()->getModuleIdentifier() + "." + F.getName().str();
     822             : #endif
     823             : 
     824             :   // If there are non-empty intervals allocate them using pbqp.
     825           7 :   if (!VRegsToAlloc.empty()) {
     826           7 :     const TargetSubtargetInfo &Subtarget = MF.getSubtarget();
     827             :     std::unique_ptr<PBQPRAConstraintList> ConstraintsRoot =
     828             :       llvm::make_unique<PBQPRAConstraintList>();
     829           7 :     ConstraintsRoot->addConstraint(llvm::make_unique<SpillCosts>());
     830           7 :     ConstraintsRoot->addConstraint(llvm::make_unique<Interference>());
     831           7 :     if (PBQPCoalescing)
     832           5 :       ConstraintsRoot->addConstraint(llvm::make_unique<Coalescing>());
     833          14 :     ConstraintsRoot->addConstraint(Subtarget.getCustomPBQPConstraints());
     834             : 
     835             :     bool PBQPAllocComplete = false;
     836             :     unsigned Round = 0;
     837             : 
     838          23 :     while (!PBQPAllocComplete) {
     839             :       LLVM_DEBUG(dbgs() << "  PBQP Regalloc round " << Round << ":\n");
     840             : 
     841          16 :       PBQPRAGraph G(PBQPRAGraph::GraphMetadata(MF, LIS, MBFI));
     842           8 :       initializeGraph(G, VRM, *VRegSpiller);
     843           8 :       ConstraintsRoot->apply(G);
     844             : 
     845             : #ifndef NDEBUG
     846             :       if (PBQPDumpGraphs) {
     847             :         std::ostringstream RS;
     848             :         RS << Round;
     849             :         std::string GraphFileName = FullyQualifiedName + "." + RS.str() +
     850             :                                     ".pbqpgraph";
     851             :         std::error_code EC;
     852             :         raw_fd_ostream OS(GraphFileName, EC, sys::fs::F_Text);
     853             :         LLVM_DEBUG(dbgs() << "Dumping graph for round " << Round << " to \""
     854             :                           << GraphFileName << "\"\n");
     855             :         G.dump(OS);
     856             :       }
     857             : #endif
     858             : 
     859           8 :       PBQP::Solution Solution = PBQP::RegAlloc::solve(G);
     860           8 :       PBQPAllocComplete = mapPBQPToRegAlloc(G, Solution, VRM, *VRegSpiller);
     861             :       ++Round;
     862             :     }
     863             :   }
     864             : 
     865             :   // Finalise allocation, allocate empty ranges.
     866           7 :   finalizeAlloc(MF, LIS, VRM);
     867           7 :   postOptimization(*VRegSpiller, LIS);
     868             :   VRegsToAlloc.clear();
     869             :   EmptyIntervalVRegs.clear();
     870             : 
     871             :   LLVM_DEBUG(dbgs() << "Post alloc VirtRegMap:\n" << VRM << "\n");
     872             : 
     873           7 :   return true;
     874             : }
     875             : 
     876             : /// Create Printable object for node and register info.
     877             : static Printable PrintNodeInfo(PBQP::RegAlloc::PBQPRAGraph::NodeId NId,
     878             :                                const PBQP::RegAlloc::PBQPRAGraph &G) {
     879           0 :   return Printable([NId, &G](raw_ostream &OS) {
     880           0 :     const MachineRegisterInfo &MRI = G.getMetadata().MF.getRegInfo();
     881           0 :     const TargetRegisterInfo *TRI = MRI.getTargetRegisterInfo();
     882           0 :     unsigned VReg = G.getNodeMetadata(NId).getVReg();
     883           0 :     const char *RegClassName = TRI->getRegClassName(MRI.getRegClass(VReg));
     884           0 :     OS << NId << " (" << RegClassName << ':' << printReg(VReg, TRI) << ')';
     885           0 :   });
     886             : }
     887             : 
     888             : #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
     889             : LLVM_DUMP_METHOD void PBQP::RegAlloc::PBQPRAGraph::dump(raw_ostream &OS) const {
     890             :   for (auto NId : nodeIds()) {
     891             :     const Vector &Costs = getNodeCosts(NId);
     892             :     assert(Costs.getLength() != 0 && "Empty vector in graph.");
     893             :     OS << PrintNodeInfo(NId, *this) << ": " << Costs << '\n';
     894             :   }
     895             :   OS << '\n';
     896             : 
     897             :   for (auto EId : edgeIds()) {
     898             :     NodeId N1Id = getEdgeNode1Id(EId);
     899             :     NodeId N2Id = getEdgeNode2Id(EId);
     900             :     assert(N1Id != N2Id && "PBQP graphs should not have self-edges.");
     901             :     const Matrix &M = getEdgeCosts(EId);
     902             :     assert(M.getRows() != 0 && "No rows in matrix.");
     903             :     assert(M.getCols() != 0 && "No cols in matrix.");
     904             :     OS << PrintNodeInfo(N1Id, *this) << ' ' << M.getRows() << " rows / ";
     905             :     OS << PrintNodeInfo(N2Id, *this) << ' ' << M.getCols() << " cols:\n";
     906             :     OS << M << '\n';
     907             :   }
     908             : }
     909             : 
     910             : LLVM_DUMP_METHOD void PBQP::RegAlloc::PBQPRAGraph::dump() const {
     911             :   dump(dbgs());
     912             : }
     913             : #endif
     914             : 
     915           0 : void PBQP::RegAlloc::PBQPRAGraph::printDot(raw_ostream &OS) const {
     916           0 :   OS << "graph {\n";
     917           0 :   for (auto NId : nodeIds()) {
     918           0 :     OS << "  node" << NId << " [ label=\""
     919           0 :        << PrintNodeInfo(NId, *this) << "\\n"
     920           0 :        << getNodeCosts(NId) << "\" ]\n";
     921             :   }
     922             : 
     923           0 :   OS << "  edge [ len=" << nodeIds().size() << " ]\n";
     924           0 :   for (auto EId : edgeIds()) {
     925           0 :     OS << "  node" << getEdgeNode1Id(EId)
     926           0 :        << " -- node" << getEdgeNode2Id(EId)
     927           0 :        << " [ label=\"";
     928             :     const Matrix &EdgeCosts = getEdgeCosts(EId);
     929           0 :     for (unsigned i = 0; i < EdgeCosts.getRows(); ++i) {
     930           0 :       OS << EdgeCosts.getRowAsVector(i) << "\\n";
     931             :     }
     932           0 :     OS << "\" ]\n";
     933             :   }
     934           0 :   OS << "}\n";
     935           0 : }
     936             : 
     937           7 : FunctionPass *llvm::createPBQPRegisterAllocator(char *customPassID) {
     938           7 :   return new RegAllocPBQP(customPassID);
     939             : }
     940             : 
     941           7 : FunctionPass* llvm::createDefaultPBQPRegisterAllocator() {
     942           7 :   return createPBQPRegisterAllocator();
     943      303507 : }

Generated by: LCOV version 1.13