contrib/llvm/lib/CodeGen/RegAllocPBQP.cpp

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