1321369Sdim//===- RegAllocPBQP.cpp ---- PBQP Register Allocator ----------------------===// 2193323Sed// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6193323Sed// 7193323Sed//===----------------------------------------------------------------------===// 8193323Sed// 9193323Sed// This file contains a Partitioned Boolean Quadratic Programming (PBQP) based 10193323Sed// register allocator for LLVM. This allocator works by constructing a PBQP 11193323Sed// problem representing the register allocation problem under consideration, 12193323Sed// solving this using a PBQP solver, and mapping the solution back to a 13193323Sed// register assignment. If any variables are selected for spilling then spill 14193323Sed// code is inserted and the process repeated. 15193323Sed// 16193323Sed// The PBQP solver (pbqp.c) provided for this allocator uses a heuristic tuned 17193323Sed// for register allocation. For more information on PBQP for register 18193323Sed// allocation, see the following papers: 19193323Sed// 20193323Sed// (1) Hames, L. and Scholz, B. 2006. Nearly optimal register allocation with 21193323Sed// PBQP. In Proceedings of the 7th Joint Modular Languages Conference 22193323Sed// (JMLC'06). LNCS, vol. 4228. Springer, New York, NY, USA. 346-361. 23193323Sed// 24193323Sed// (2) Scholz, B., Eckstein, E. 2002. Register allocation for irregular 25193323Sed// architectures. In Proceedings of the Joint Conference on Languages, 26193323Sed// Compilers and Tools for Embedded Systems (LCTES'02), ACM Press, New York, 27193323Sed// NY, USA, 139-148. 28193323Sed// 29193323Sed//===----------------------------------------------------------------------===// 30193323Sed 31249423Sdim#include "llvm/CodeGen/RegAllocPBQP.h" 32249423Sdim#include "RegisterCoalescer.h" 33234353Sdim#include "Spiller.h" 34321369Sdim#include "llvm/ADT/ArrayRef.h" 35321369Sdim#include "llvm/ADT/BitVector.h" 36321369Sdim#include "llvm/ADT/DenseMap.h" 37321369Sdim#include "llvm/ADT/DenseSet.h" 38321369Sdim#include "llvm/ADT/STLExtras.h" 39321369Sdim#include "llvm/ADT/SmallPtrSet.h" 40321369Sdim#include "llvm/ADT/SmallVector.h" 41321369Sdim#include "llvm/ADT/StringRef.h" 42234353Sdim#include "llvm/Analysis/AliasAnalysis.h" 43200581Srdivacky#include "llvm/CodeGen/CalcSpillWeights.h" 44321369Sdim#include "llvm/CodeGen/LiveInterval.h" 45327952Sdim#include "llvm/CodeGen/LiveIntervals.h" 46234353Sdim#include "llvm/CodeGen/LiveRangeEdit.h" 47327952Sdim#include "llvm/CodeGen/LiveStacks.h" 48261991Sdim#include "llvm/CodeGen/MachineBlockFrequencyInfo.h" 49234353Sdim#include "llvm/CodeGen/MachineDominators.h" 50321369Sdim#include "llvm/CodeGen/MachineFunction.h" 51193323Sed#include "llvm/CodeGen/MachineFunctionPass.h" 52321369Sdim#include "llvm/CodeGen/MachineInstr.h" 53193323Sed#include "llvm/CodeGen/MachineLoopInfo.h" 54193323Sed#include "llvm/CodeGen/MachineRegisterInfo.h" 55321369Sdim#include "llvm/CodeGen/PBQP/Graph.h" 56321369Sdim#include "llvm/CodeGen/PBQP/Math.h" 57321369Sdim#include "llvm/CodeGen/PBQP/Solution.h" 58321369Sdim#include "llvm/CodeGen/PBQPRAConstraint.h" 59193323Sed#include "llvm/CodeGen/RegAllocRegistry.h" 60321369Sdim#include "llvm/CodeGen/SlotIndexes.h" 61327952Sdim#include "llvm/CodeGen/TargetRegisterInfo.h" 62327952Sdim#include "llvm/CodeGen/TargetSubtargetInfo.h" 63249423Sdim#include "llvm/CodeGen/VirtRegMap.h" 64341825Sdim#include "llvm/Config/llvm-config.h" 65321369Sdim#include "llvm/IR/Function.h" 66249423Sdim#include "llvm/IR/Module.h" 67321369Sdim#include "llvm/MC/MCRegisterInfo.h" 68321369Sdim#include "llvm/Pass.h" 69321369Sdim#include "llvm/Support/CommandLine.h" 70321369Sdim#include "llvm/Support/Compiler.h" 71193323Sed#include "llvm/Support/Debug.h" 72276479Sdim#include "llvm/Support/FileSystem.h" 73296417Sdim#include "llvm/Support/Printable.h" 74198090Srdivacky#include "llvm/Support/raw_ostream.h" 75321369Sdim#include <algorithm> 76321369Sdim#include <cassert> 77321369Sdim#include <cstddef> 78193323Sed#include <limits> 79321369Sdim#include <map> 80193323Sed#include <memory> 81280031Sdim#include <queue> 82193323Sed#include <set> 83234353Sdim#include <sstream> 84321369Sdim#include <string> 85321369Sdim#include <system_error> 86321369Sdim#include <tuple> 87321369Sdim#include <utility> 88193323Sed#include <vector> 89193323Sed 90193323Sedusing namespace llvm; 91193323Sed 92276479Sdim#define DEBUG_TYPE "regalloc" 93276479Sdim 94193323Sedstatic RegisterRegAlloc 95280031SdimRegisterPBQPRepAlloc("pbqp", "PBQP register allocator", 96218893Sdim createDefaultPBQPRegisterAllocator); 97193323Sed 98198090Srdivackystatic cl::opt<bool> 99280031SdimPBQPCoalescing("pbqp-coalescing", 100203954Srdivacky cl::desc("Attempt coalescing during PBQP register allocation."), 101203954Srdivacky cl::init(false), cl::Hidden); 102198090Srdivacky 103234353Sdim#ifndef NDEBUG 104212904Sdimstatic cl::opt<bool> 105280031SdimPBQPDumpGraphs("pbqp-dump-graphs", 106234353Sdim cl::desc("Dump graphs for each function/round in the compilation unit."), 107234353Sdim cl::init(false), cl::Hidden); 108234353Sdim#endif 109212904Sdim 110193323Sednamespace { 111193323Sed 112218893Sdim/// 113218893Sdim/// PBQP based allocators solve the register allocation problem by mapping 114218893Sdim/// register allocation problems to Partitioned Boolean Quadratic 115218893Sdim/// Programming problems. 116218893Sdimclass RegAllocPBQP : public MachineFunctionPass { 117218893Sdimpublic: 118218893Sdim static char ID; 119193323Sed 120218893Sdim /// Construct a PBQP register allocator. 121280031Sdim RegAllocPBQP(char *cPassID = nullptr) 122280031Sdim : MachineFunctionPass(ID), customPassID(cPassID) { 123218893Sdim initializeSlotIndexesPass(*PassRegistry::getPassRegistry()); 124218893Sdim initializeLiveIntervalsPass(*PassRegistry::getPassRegistry()); 125218893Sdim initializeLiveStacksPass(*PassRegistry::getPassRegistry()); 126218893Sdim initializeVirtRegMapPass(*PassRegistry::getPassRegistry()); 127218893Sdim } 128193323Sed 129218893Sdim /// Return the pass name. 130314564Sdim StringRef getPassName() const override { return "PBQP Register Allocator"; } 131193323Sed 132218893Sdim /// PBQP analysis usage. 133276479Sdim void getAnalysisUsage(AnalysisUsage &au) const override; 134193323Sed 135218893Sdim /// Perform register allocation 136276479Sdim bool runOnMachineFunction(MachineFunction &MF) override; 137193323Sed 138314564Sdim MachineFunctionProperties getRequiredProperties() const override { 139314564Sdim return MachineFunctionProperties().set( 140314564Sdim MachineFunctionProperties::Property::NoPHIs); 141314564Sdim } 142314564Sdim 143218893Sdimprivate: 144321369Sdim using LI2NodeMap = std::map<const LiveInterval *, unsigned>; 145321369Sdim using Node2LIMap = std::vector<const LiveInterval *>; 146321369Sdim using AllowedSet = std::vector<unsigned>; 147321369Sdim using AllowedSetMap = std::vector<AllowedSet>; 148321369Sdim using RegPair = std::pair<unsigned, unsigned>; 149321369Sdim using CoalesceMap = std::map<RegPair, PBQP::PBQPNum>; 150321369Sdim using RegSet = std::set<unsigned>; 151212904Sdim 152224145Sdim char *customPassID; 153224145Sdim 154280031Sdim RegSet VRegsToAlloc, EmptyIntervalVRegs; 155203954Srdivacky 156309124Sdim /// Inst which is a def of an original reg and whose defs are already all 157309124Sdim /// dead after remat is saved in DeadRemats. The deletion of such inst is 158309124Sdim /// postponed till all the allocations are done, so its remat expr is 159309124Sdim /// always available for the remat of all the siblings of the original reg. 160309124Sdim SmallPtrSet<MachineInstr *, 32> DeadRemats; 161309124Sdim 162341825Sdim /// Finds the initial set of vreg intervals to allocate. 163280031Sdim void findVRegIntervalsToAlloc(const MachineFunction &MF, LiveIntervals &LIS); 164193323Sed 165341825Sdim /// Constructs an initial graph. 166288943Sdim void initializeGraph(PBQPRAGraph &G, VirtRegMap &VRM, Spiller &VRegSpiller); 167193323Sed 168341825Sdim /// Spill the given VReg. 169288943Sdim void spillVReg(unsigned VReg, SmallVectorImpl<unsigned> &NewIntervals, 170288943Sdim MachineFunction &MF, LiveIntervals &LIS, VirtRegMap &VRM, 171288943Sdim Spiller &VRegSpiller); 172288943Sdim 173341825Sdim /// Given a solved PBQP problem maps this solution back to a register 174218893Sdim /// assignment. 175280031Sdim bool mapPBQPToRegAlloc(const PBQPRAGraph &G, 176280031Sdim const PBQP::Solution &Solution, 177280031Sdim VirtRegMap &VRM, 178280031Sdim Spiller &VRegSpiller); 179193323Sed 180341825Sdim /// Postprocessing before final spilling. Sets basic block "live in" 181218893Sdim /// variables. 182280031Sdim void finalizeAlloc(MachineFunction &MF, LiveIntervals &LIS, 183280031Sdim VirtRegMap &VRM) const; 184193323Sed 185309124Sdim void postOptimization(Spiller &VRegSpiller, LiveIntervals &LIS); 186218893Sdim}; 187193323Sed 188218893Sdimchar RegAllocPBQP::ID = 0; 189193323Sed 190341825Sdim/// Set spill costs for each node in the PBQP reg-alloc graph. 191280031Sdimclass SpillCosts : public PBQPRAConstraint { 192280031Sdimpublic: 193280031Sdim void apply(PBQPRAGraph &G) override { 194280031Sdim LiveIntervals &LIS = G.getMetadata().LIS; 195193323Sed 196280031Sdim // A minimum spill costs, so that register constraints can can be set 197280031Sdim // without normalization in the [0.0:MinSpillCost( interval. 198280031Sdim const PBQP::PBQPNum MinSpillCost = 10.0; 199193323Sed 200280031Sdim for (auto NId : G.nodeIds()) { 201280031Sdim PBQP::PBQPNum SpillCost = 202280031Sdim LIS.getInterval(G.getNodeMetadata(NId).getVReg()).weight; 203280031Sdim if (SpillCost == 0.0) 204280031Sdim SpillCost = std::numeric_limits<PBQP::PBQPNum>::min(); 205280031Sdim else 206280031Sdim SpillCost += MinSpillCost; 207280031Sdim PBQPRAGraph::RawVector NodeCosts(G.getNodeCosts(NId)); 208280031Sdim NodeCosts[PBQP::RegAlloc::getSpillOptionIdx()] = SpillCost; 209280031Sdim G.setNodeCosts(NId, std::move(NodeCosts)); 210280031Sdim } 211280031Sdim } 212280031Sdim}; 213234353Sdim 214341825Sdim/// Add interference edges between overlapping vregs. 215280031Sdimclass Interference : public PBQPRAConstraint { 216280031Sdimprivate: 217321369Sdim using AllowedRegVecPtr = const PBQP::RegAlloc::AllowedRegVector *; 218321369Sdim using IKey = std::pair<AllowedRegVecPtr, AllowedRegVecPtr>; 219321369Sdim using IMatrixCache = DenseMap<IKey, PBQPRAGraph::MatrixPtr>; 220321369Sdim using DisjointAllowedRegsCache = DenseSet<IKey>; 221321369Sdim using IEdgeKey = std::pair<PBQP::GraphBase::NodeId, PBQP::GraphBase::NodeId>; 222321369Sdim using IEdgeCache = DenseSet<IEdgeKey>; 223193323Sed 224288943Sdim bool haveDisjointAllowedRegs(const PBQPRAGraph &G, PBQPRAGraph::NodeId NId, 225288943Sdim PBQPRAGraph::NodeId MId, 226288943Sdim const DisjointAllowedRegsCache &D) const { 227288943Sdim const auto *NRegs = &G.getNodeMetadata(NId).getAllowedRegs(); 228288943Sdim const auto *MRegs = &G.getNodeMetadata(MId).getAllowedRegs(); 229288943Sdim 230288943Sdim if (NRegs == MRegs) 231288943Sdim return false; 232288943Sdim 233288943Sdim if (NRegs < MRegs) 234288943Sdim return D.count(IKey(NRegs, MRegs)) > 0; 235288943Sdim 236288943Sdim return D.count(IKey(MRegs, NRegs)) > 0; 237288943Sdim } 238288943Sdim 239288943Sdim void setDisjointAllowedRegs(const PBQPRAGraph &G, PBQPRAGraph::NodeId NId, 240288943Sdim PBQPRAGraph::NodeId MId, 241288943Sdim DisjointAllowedRegsCache &D) { 242288943Sdim const auto *NRegs = &G.getNodeMetadata(NId).getAllowedRegs(); 243288943Sdim const auto *MRegs = &G.getNodeMetadata(MId).getAllowedRegs(); 244288943Sdim 245288943Sdim assert(NRegs != MRegs && "AllowedRegs can not be disjoint with itself"); 246288943Sdim 247288943Sdim if (NRegs < MRegs) 248288943Sdim D.insert(IKey(NRegs, MRegs)); 249288943Sdim else 250288943Sdim D.insert(IKey(MRegs, NRegs)); 251288943Sdim } 252288943Sdim 253280031Sdim // Holds (Interval, CurrentSegmentID, and NodeId). The first two are required 254280031Sdim // for the fast interference graph construction algorithm. The last is there 255280031Sdim // to save us from looking up node ids via the VRegToNode map in the graph 256280031Sdim // metadata. 257321369Sdim using IntervalInfo = 258321369Sdim std::tuple<LiveInterval*, size_t, PBQP::GraphBase::NodeId>; 259193323Sed 260280031Sdim static SlotIndex getStartPoint(const IntervalInfo &I) { 261280031Sdim return std::get<0>(I)->segments[std::get<1>(I)].start; 262280031Sdim } 263193323Sed 264280031Sdim static SlotIndex getEndPoint(const IntervalInfo &I) { 265280031Sdim return std::get<0>(I)->segments[std::get<1>(I)].end; 266280031Sdim } 267193323Sed 268280031Sdim static PBQP::GraphBase::NodeId getNodeId(const IntervalInfo &I) { 269280031Sdim return std::get<2>(I); 270280031Sdim } 271193323Sed 272280031Sdim static bool lowestStartPoint(const IntervalInfo &I1, 273280031Sdim const IntervalInfo &I2) { 274280031Sdim // Condition reversed because priority queue has the *highest* element at 275280031Sdim // the front, rather than the lowest. 276280031Sdim return getStartPoint(I1) > getStartPoint(I2); 277218893Sdim } 278193323Sed 279280031Sdim static bool lowestEndPoint(const IntervalInfo &I1, 280280031Sdim const IntervalInfo &I2) { 281280031Sdim SlotIndex E1 = getEndPoint(I1); 282280031Sdim SlotIndex E2 = getEndPoint(I2); 283193323Sed 284280031Sdim if (E1 < E2) 285280031Sdim return true; 286239462Sdim 287280031Sdim if (E1 > E2) 288280031Sdim return false; 289193323Sed 290280031Sdim // If two intervals end at the same point, we need a way to break the tie or 291280031Sdim // the set will assume they're actually equal and refuse to insert a 292280031Sdim // "duplicate". Just compare the vregs - fast and guaranteed unique. 293280031Sdim return std::get<0>(I1)->reg < std::get<0>(I2)->reg; 294280031Sdim } 295193323Sed 296280031Sdim static bool isAtLastSegment(const IntervalInfo &I) { 297280031Sdim return std::get<1>(I) == std::get<0>(I)->size() - 1; 298280031Sdim } 299193323Sed 300280031Sdim static IntervalInfo nextSegment(const IntervalInfo &I) { 301280031Sdim return std::make_tuple(std::get<0>(I), std::get<1>(I) + 1, std::get<2>(I)); 302280031Sdim } 303234353Sdim 304280031Sdimpublic: 305280031Sdim void apply(PBQPRAGraph &G) override { 306280031Sdim // The following is loosely based on the linear scan algorithm introduced in 307280031Sdim // "Linear Scan Register Allocation" by Poletto and Sarkar. This version 308280031Sdim // isn't linear, because the size of the active set isn't bound by the 309280031Sdim // number of registers, but rather the size of the largest clique in the 310280031Sdim // graph. Still, we expect this to be better than N^2. 311280031Sdim LiveIntervals &LIS = G.getMetadata().LIS; 312276479Sdim 313280031Sdim // Interferenc matrices are incredibly regular - they're only a function of 314280031Sdim // the allowed sets, so we cache them to avoid the overhead of constructing 315280031Sdim // and uniquing them. 316280031Sdim IMatrixCache C; 317276479Sdim 318288943Sdim // Finding an edge is expensive in the worst case (O(max_clique(G))). So 319288943Sdim // cache locally edges we have already seen. 320288943Sdim IEdgeCache EC; 321288943Sdim 322288943Sdim // Cache known disjoint allowed registers pairs 323288943Sdim DisjointAllowedRegsCache D; 324288943Sdim 325321369Sdim using IntervalSet = std::set<IntervalInfo, decltype(&lowestEndPoint)>; 326321369Sdim using IntervalQueue = 327321369Sdim std::priority_queue<IntervalInfo, std::vector<IntervalInfo>, 328321369Sdim decltype(&lowestStartPoint)>; 329280031Sdim IntervalSet Active(lowestEndPoint); 330280031Sdim IntervalQueue Inactive(lowestStartPoint); 331193323Sed 332280031Sdim // Start by building the inactive set. 333280031Sdim for (auto NId : G.nodeIds()) { 334280031Sdim unsigned VReg = G.getNodeMetadata(NId).getVReg(); 335280031Sdim LiveInterval &LI = LIS.getInterval(VReg); 336280031Sdim assert(!LI.empty() && "PBQP graph contains node for empty interval"); 337280031Sdim Inactive.push(std::make_tuple(&LI, 0, NId)); 338280031Sdim } 339193323Sed 340280031Sdim while (!Inactive.empty()) { 341280031Sdim // Tentatively grab the "next" interval - this choice may be overriden 342280031Sdim // below. 343280031Sdim IntervalInfo Cur = Inactive.top(); 344193323Sed 345280031Sdim // Retire any active intervals that end before Cur starts. 346280031Sdim IntervalSet::iterator RetireItr = Active.begin(); 347280031Sdim while (RetireItr != Active.end() && 348280031Sdim (getEndPoint(*RetireItr) <= getStartPoint(Cur))) { 349280031Sdim // If this interval has subsequent segments, add the next one to the 350280031Sdim // inactive list. 351280031Sdim if (!isAtLastSegment(*RetireItr)) 352280031Sdim Inactive.push(nextSegment(*RetireItr)); 353193323Sed 354280031Sdim ++RetireItr; 355280031Sdim } 356280031Sdim Active.erase(Active.begin(), RetireItr); 357193323Sed 358280031Sdim // One of the newly retired segments may actually start before the 359280031Sdim // Cur segment, so re-grab the front of the inactive list. 360280031Sdim Cur = Inactive.top(); 361280031Sdim Inactive.pop(); 362218893Sdim 363280031Sdim // At this point we know that Cur overlaps all active intervals. Add the 364280031Sdim // interference edges. 365280031Sdim PBQP::GraphBase::NodeId NId = getNodeId(Cur); 366280031Sdim for (const auto &A : Active) { 367280031Sdim PBQP::GraphBase::NodeId MId = getNodeId(A); 368280031Sdim 369288943Sdim // Do not add an edge when the nodes' allowed registers do not 370288943Sdim // intersect: there is obviously no interference. 371288943Sdim if (haveDisjointAllowedRegs(G, NId, MId, D)) 372288943Sdim continue; 373288943Sdim 374280031Sdim // Check that we haven't already added this edge 375288943Sdim IEdgeKey EK(std::min(NId, MId), std::max(NId, MId)); 376288943Sdim if (EC.count(EK)) 377280031Sdim continue; 378280031Sdim 379280031Sdim // This is a new edge - add it to the graph. 380288943Sdim if (!createInterferenceEdge(G, NId, MId, C)) 381288943Sdim setDisjointAllowedRegs(G, NId, MId, D); 382288943Sdim else 383288943Sdim EC.insert(EK); 384193323Sed } 385280031Sdim 386280031Sdim // Finally, add Cur to the Active set. 387280031Sdim Active.insert(Cur); 388193323Sed } 389193323Sed } 390193323Sed 391280031Sdimprivate: 392288943Sdim // Create an Interference edge and add it to the graph, unless it is 393288943Sdim // a null matrix, meaning the nodes' allowed registers do not have any 394288943Sdim // interference. This case occurs frequently between integer and floating 395288943Sdim // point registers for example. 396288943Sdim // return true iff both nodes interferes. 397288943Sdim bool createInterferenceEdge(PBQPRAGraph &G, 398288943Sdim PBQPRAGraph::NodeId NId, PBQPRAGraph::NodeId MId, 399288943Sdim IMatrixCache &C) { 400280031Sdim const TargetRegisterInfo &TRI = 401288943Sdim *G.getMetadata().MF.getSubtarget().getRegisterInfo(); 402280031Sdim const auto &NRegs = G.getNodeMetadata(NId).getAllowedRegs(); 403280031Sdim const auto &MRegs = G.getNodeMetadata(MId).getAllowedRegs(); 404193323Sed 405280031Sdim // Try looking the edge costs up in the IMatrixCache first. 406288943Sdim IKey K(&NRegs, &MRegs); 407280031Sdim IMatrixCache::iterator I = C.find(K); 408280031Sdim if (I != C.end()) { 409280031Sdim G.addEdgeBypassingCostAllocator(NId, MId, I->second); 410288943Sdim return true; 411280031Sdim } 412193323Sed 413280031Sdim PBQPRAGraph::RawMatrix M(NRegs.size() + 1, MRegs.size() + 1, 0); 414288943Sdim bool NodesInterfere = false; 415280031Sdim for (unsigned I = 0; I != NRegs.size(); ++I) { 416280031Sdim unsigned PRegN = NRegs[I]; 417280031Sdim for (unsigned J = 0; J != MRegs.size(); ++J) { 418280031Sdim unsigned PRegM = MRegs[J]; 419288943Sdim if (TRI.regsOverlap(PRegN, PRegM)) { 420280031Sdim M[I + 1][J + 1] = std::numeric_limits<PBQP::PBQPNum>::infinity(); 421288943Sdim NodesInterfere = true; 422288943Sdim } 423193323Sed } 424193323Sed } 425280031Sdim 426288943Sdim if (!NodesInterfere) 427288943Sdim return false; 428288943Sdim 429280031Sdim PBQPRAGraph::EdgeId EId = G.addEdge(NId, MId, std::move(M)); 430280031Sdim C[K] = G.getEdgeCostsPtr(EId); 431288943Sdim 432288943Sdim return true; 433193323Sed } 434280031Sdim}; 435193323Sed 436280031Sdimclass Coalescing : public PBQPRAConstraint { 437280031Sdimpublic: 438280031Sdim void apply(PBQPRAGraph &G) override { 439280031Sdim MachineFunction &MF = G.getMetadata().MF; 440280031Sdim MachineBlockFrequencyInfo &MBFI = G.getMetadata().MBFI; 441288943Sdim CoalescerPair CP(*MF.getSubtarget().getRegisterInfo()); 442193323Sed 443280031Sdim // Scan the machine function and add a coalescing cost whenever CoalescerPair 444280031Sdim // gives the Ok. 445280031Sdim for (const auto &MBB : MF) { 446280031Sdim for (const auto &MI : MBB) { 447280031Sdim // Skip not-coalescable or already coalesced copies. 448280031Sdim if (!CP.setRegisters(&MI) || CP.getSrcReg() == CP.getDstReg()) 449280031Sdim continue; 450193323Sed 451280031Sdim unsigned DstReg = CP.getDstReg(); 452280031Sdim unsigned SrcReg = CP.getSrcReg(); 453193323Sed 454280031Sdim const float Scale = 1.0f / MBFI.getEntryFreq(); 455280031Sdim PBQP::PBQPNum CBenefit = MBFI.getBlockFreq(&MBB).getFrequency() * Scale; 456193323Sed 457280031Sdim if (CP.isPhys()) { 458280031Sdim if (!MF.getRegInfo().isAllocatable(DstReg)) 459280031Sdim continue; 460234353Sdim 461280031Sdim PBQPRAGraph::NodeId NId = G.getMetadata().getNodeIdForVReg(SrcReg); 462212904Sdim 463280031Sdim const PBQPRAGraph::NodeMetadata::AllowedRegVector &Allowed = 464280031Sdim G.getNodeMetadata(NId).getAllowedRegs(); 465193323Sed 466280031Sdim unsigned PRegOpt = 0; 467280031Sdim while (PRegOpt < Allowed.size() && Allowed[PRegOpt] != DstReg) 468280031Sdim ++PRegOpt; 469280031Sdim 470280031Sdim if (PRegOpt < Allowed.size()) { 471280031Sdim PBQPRAGraph::RawVector NewCosts(G.getNodeCosts(NId)); 472280031Sdim NewCosts[PRegOpt + 1] -= CBenefit; 473280031Sdim G.setNodeCosts(NId, std::move(NewCosts)); 474280031Sdim } 475218893Sdim } else { 476280031Sdim PBQPRAGraph::NodeId N1Id = G.getMetadata().getNodeIdForVReg(DstReg); 477280031Sdim PBQPRAGraph::NodeId N2Id = G.getMetadata().getNodeIdForVReg(SrcReg); 478280031Sdim const PBQPRAGraph::NodeMetadata::AllowedRegVector *Allowed1 = 479280031Sdim &G.getNodeMetadata(N1Id).getAllowedRegs(); 480280031Sdim const PBQPRAGraph::NodeMetadata::AllowedRegVector *Allowed2 = 481280031Sdim &G.getNodeMetadata(N2Id).getAllowedRegs(); 482280031Sdim 483280031Sdim PBQPRAGraph::EdgeId EId = G.findEdge(N1Id, N2Id); 484280031Sdim if (EId == G.invalidEdgeId()) { 485280031Sdim PBQPRAGraph::RawMatrix Costs(Allowed1->size() + 1, 486280031Sdim Allowed2->size() + 1, 0); 487280031Sdim addVirtRegCoalesce(Costs, *Allowed1, *Allowed2, CBenefit); 488280031Sdim G.addEdge(N1Id, N2Id, std::move(Costs)); 489280031Sdim } else { 490280031Sdim if (G.getEdgeNode1Id(EId) == N2Id) { 491280031Sdim std::swap(N1Id, N2Id); 492280031Sdim std::swap(Allowed1, Allowed2); 493280031Sdim } 494280031Sdim PBQPRAGraph::RawMatrix Costs(G.getEdgeCosts(EId)); 495280031Sdim addVirtRegCoalesce(Costs, *Allowed1, *Allowed2, CBenefit); 496288943Sdim G.updateEdgeCosts(EId, std::move(Costs)); 497203954Srdivacky } 498193323Sed } 499218893Sdim } 500218893Sdim } 501218893Sdim } 502193323Sed 503280031Sdimprivate: 504280031Sdim void addVirtRegCoalesce( 505280031Sdim PBQPRAGraph::RawMatrix &CostMat, 506280031Sdim const PBQPRAGraph::NodeMetadata::AllowedRegVector &Allowed1, 507280031Sdim const PBQPRAGraph::NodeMetadata::AllowedRegVector &Allowed2, 508280031Sdim PBQP::PBQPNum Benefit) { 509280031Sdim assert(CostMat.getRows() == Allowed1.size() + 1 && "Size mismatch."); 510280031Sdim assert(CostMat.getCols() == Allowed2.size() + 1 && "Size mismatch."); 511280031Sdim for (unsigned I = 0; I != Allowed1.size(); ++I) { 512280031Sdim unsigned PReg1 = Allowed1[I]; 513280031Sdim for (unsigned J = 0; J != Allowed2.size(); ++J) { 514280031Sdim unsigned PReg2 = Allowed2[J]; 515280031Sdim if (PReg1 == PReg2) 516280031Sdim CostMat[I + 1][J + 1] -= Benefit; 517234353Sdim } 518193323Sed } 519193323Sed } 520280031Sdim}; 521218893Sdim 522321369Sdim} // end anonymous namespace 523280031Sdim 524280031Sdim// Out-of-line destructor/anchor for PBQPRAConstraint. 525321369SdimPBQPRAConstraint::~PBQPRAConstraint() = default; 526321369Sdim 527280031Sdimvoid PBQPRAConstraint::anchor() {} 528321369Sdim 529280031Sdimvoid PBQPRAConstraintList::anchor() {} 530280031Sdim 531218893Sdimvoid RegAllocPBQP::getAnalysisUsage(AnalysisUsage &au) const { 532234353Sdim au.setPreservesCFG(); 533296417Sdim au.addRequired<AAResultsWrapperPass>(); 534296417Sdim au.addPreserved<AAResultsWrapperPass>(); 535218893Sdim au.addRequired<SlotIndexes>(); 536218893Sdim au.addPreserved<SlotIndexes>(); 537218893Sdim au.addRequired<LiveIntervals>(); 538243830Sdim au.addPreserved<LiveIntervals>(); 539218893Sdim //au.addRequiredID(SplitCriticalEdgesID); 540224145Sdim if (customPassID) 541224145Sdim au.addRequiredID(*customPassID); 542218893Sdim au.addRequired<LiveStacks>(); 543218893Sdim au.addPreserved<LiveStacks>(); 544261991Sdim au.addRequired<MachineBlockFrequencyInfo>(); 545261991Sdim au.addPreserved<MachineBlockFrequencyInfo>(); 546261991Sdim au.addRequired<MachineLoopInfo>(); 547261991Sdim au.addPreserved<MachineLoopInfo>(); 548234353Sdim au.addRequired<MachineDominatorTree>(); 549234353Sdim au.addPreserved<MachineDominatorTree>(); 550218893Sdim au.addRequired<VirtRegMap>(); 551243830Sdim au.addPreserved<VirtRegMap>(); 552218893Sdim MachineFunctionPass::getAnalysisUsage(au); 553193323Sed} 554193323Sed 555280031Sdimvoid RegAllocPBQP::findVRegIntervalsToAlloc(const MachineFunction &MF, 556280031Sdim LiveIntervals &LIS) { 557280031Sdim const MachineRegisterInfo &MRI = MF.getRegInfo(); 558193323Sed 559193323Sed // Iterate over all live ranges. 560280031Sdim for (unsigned I = 0, E = MRI.getNumVirtRegs(); I != E; ++I) { 561360784Sdim unsigned Reg = Register::index2VirtReg(I); 562280031Sdim if (MRI.reg_nodbg_empty(Reg)) 563193323Sed continue; 564341825Sdim VRegsToAlloc.insert(Reg); 565193323Sed } 566193323Sed} 567193323Sed 568280031Sdimstatic bool isACalleeSavedRegister(unsigned reg, const TargetRegisterInfo &TRI, 569280031Sdim const MachineFunction &MF) { 570321369Sdim const MCPhysReg *CSR = MF.getRegInfo().getCalleeSavedRegs(); 571280031Sdim for (unsigned i = 0; CSR[i] != 0; ++i) 572280031Sdim if (TRI.regsOverlap(reg, CSR[i])) 573280031Sdim return true; 574280031Sdim return false; 575280031Sdim} 576280031Sdim 577288943Sdimvoid RegAllocPBQP::initializeGraph(PBQPRAGraph &G, VirtRegMap &VRM, 578288943Sdim Spiller &VRegSpiller) { 579280031Sdim MachineFunction &MF = G.getMetadata().MF; 580280031Sdim 581280031Sdim LiveIntervals &LIS = G.getMetadata().LIS; 582280031Sdim const MachineRegisterInfo &MRI = G.getMetadata().MF.getRegInfo(); 583280031Sdim const TargetRegisterInfo &TRI = 584288943Sdim *G.getMetadata().MF.getSubtarget().getRegisterInfo(); 585280031Sdim 586288943Sdim std::vector<unsigned> Worklist(VRegsToAlloc.begin(), VRegsToAlloc.end()); 587288943Sdim 588341825Sdim std::map<unsigned, std::vector<unsigned>> VRegAllowedMap; 589341825Sdim 590288943Sdim while (!Worklist.empty()) { 591288943Sdim unsigned VReg = Worklist.back(); 592288943Sdim Worklist.pop_back(); 593288943Sdim 594280031Sdim LiveInterval &VRegLI = LIS.getInterval(VReg); 595280031Sdim 596341825Sdim // If this is an empty interval move it to the EmptyIntervalVRegs set then 597341825Sdim // continue. 598341825Sdim if (VRegLI.empty()) { 599341825Sdim EmptyIntervalVRegs.insert(VRegLI.reg); 600341825Sdim VRegsToAlloc.erase(VRegLI.reg); 601341825Sdim continue; 602341825Sdim } 603341825Sdim 604341825Sdim const TargetRegisterClass *TRC = MRI.getRegClass(VReg); 605341825Sdim 606280031Sdim // Record any overlaps with regmask operands. 607280031Sdim BitVector RegMaskOverlaps; 608280031Sdim LIS.checkRegMaskInterference(VRegLI, RegMaskOverlaps); 609280031Sdim 610280031Sdim // Compute an initial allowed set for the current vreg. 611280031Sdim std::vector<unsigned> VRegAllowed; 612280031Sdim ArrayRef<MCPhysReg> RawPRegOrder = TRC->getRawAllocationOrder(MF); 613280031Sdim for (unsigned I = 0; I != RawPRegOrder.size(); ++I) { 614280031Sdim unsigned PReg = RawPRegOrder[I]; 615280031Sdim if (MRI.isReserved(PReg)) 616280031Sdim continue; 617280031Sdim 618280031Sdim // vregLI crosses a regmask operand that clobbers preg. 619280031Sdim if (!RegMaskOverlaps.empty() && !RegMaskOverlaps.test(PReg)) 620280031Sdim continue; 621280031Sdim 622280031Sdim // vregLI overlaps fixed regunit interference. 623280031Sdim bool Interference = false; 624280031Sdim for (MCRegUnitIterator Units(PReg, &TRI); Units.isValid(); ++Units) { 625280031Sdim if (VRegLI.overlaps(LIS.getRegUnit(*Units))) { 626280031Sdim Interference = true; 627280031Sdim break; 628280031Sdim } 629280031Sdim } 630280031Sdim if (Interference) 631280031Sdim continue; 632280031Sdim 633280031Sdim // preg is usable for this virtual register. 634280031Sdim VRegAllowed.push_back(PReg); 635280031Sdim } 636280031Sdim 637288943Sdim // Check for vregs that have no allowed registers. These should be 638288943Sdim // pre-spilled and the new vregs added to the worklist. 639288943Sdim if (VRegAllowed.empty()) { 640288943Sdim SmallVector<unsigned, 8> NewVRegs; 641288943Sdim spillVReg(VReg, NewVRegs, MF, LIS, VRM, VRegSpiller); 642288943Sdim Worklist.insert(Worklist.end(), NewVRegs.begin(), NewVRegs.end()); 643288943Sdim continue; 644341825Sdim } else 645341825Sdim VRegAllowedMap[VReg] = std::move(VRegAllowed); 646341825Sdim } 647341825Sdim 648341825Sdim for (auto &KV : VRegAllowedMap) { 649341825Sdim auto VReg = KV.first; 650341825Sdim 651341825Sdim // Move empty intervals to the EmptyIntervalVReg set. 652341825Sdim if (LIS.getInterval(VReg).empty()) { 653341825Sdim EmptyIntervalVRegs.insert(VReg); 654341825Sdim VRegsToAlloc.erase(VReg); 655341825Sdim continue; 656288943Sdim } 657288943Sdim 658341825Sdim auto &VRegAllowed = KV.second; 659341825Sdim 660280031Sdim PBQPRAGraph::RawVector NodeCosts(VRegAllowed.size() + 1, 0); 661280031Sdim 662280031Sdim // Tweak cost of callee saved registers, as using then force spilling and 663280031Sdim // restoring them. This would only happen in the prologue / epilogue though. 664280031Sdim for (unsigned i = 0; i != VRegAllowed.size(); ++i) 665280031Sdim if (isACalleeSavedRegister(VRegAllowed[i], TRI, MF)) 666280031Sdim NodeCosts[1 + i] += 1.0; 667280031Sdim 668280031Sdim PBQPRAGraph::NodeId NId = G.addNode(std::move(NodeCosts)); 669280031Sdim G.getNodeMetadata(NId).setVReg(VReg); 670280031Sdim G.getNodeMetadata(NId).setAllowedRegs( 671280031Sdim G.getMetadata().getAllowedRegs(std::move(VRegAllowed))); 672280031Sdim G.getMetadata().setNodeIdForVReg(VReg, NId); 673280031Sdim } 674280031Sdim} 675280031Sdim 676288943Sdimvoid RegAllocPBQP::spillVReg(unsigned VReg, 677288943Sdim SmallVectorImpl<unsigned> &NewIntervals, 678288943Sdim MachineFunction &MF, LiveIntervals &LIS, 679288943Sdim VirtRegMap &VRM, Spiller &VRegSpiller) { 680288943Sdim VRegsToAlloc.erase(VReg); 681309124Sdim LiveRangeEdit LRE(&LIS.getInterval(VReg), NewIntervals, MF, LIS, &VRM, 682309124Sdim nullptr, &DeadRemats); 683288943Sdim VRegSpiller.spill(LRE); 684288943Sdim 685288943Sdim const TargetRegisterInfo &TRI = *MF.getSubtarget().getRegisterInfo(); 686288943Sdim (void)TRI; 687341825Sdim LLVM_DEBUG(dbgs() << "VREG " << printReg(VReg, &TRI) << " -> SPILLED (Cost: " 688341825Sdim << LRE.getParent().weight << ", New vregs: "); 689288943Sdim 690288943Sdim // Copy any newly inserted live intervals into the list of regs to 691288943Sdim // allocate. 692288943Sdim for (LiveRangeEdit::iterator I = LRE.begin(), E = LRE.end(); 693288943Sdim I != E; ++I) { 694288943Sdim const LiveInterval &LI = LIS.getInterval(*I); 695288943Sdim assert(!LI.empty() && "Empty spill range."); 696341825Sdim LLVM_DEBUG(dbgs() << printReg(LI.reg, &TRI) << " "); 697288943Sdim VRegsToAlloc.insert(LI.reg); 698288943Sdim } 699288943Sdim 700341825Sdim LLVM_DEBUG(dbgs() << ")\n"); 701288943Sdim} 702288943Sdim 703280031Sdimbool RegAllocPBQP::mapPBQPToRegAlloc(const PBQPRAGraph &G, 704280031Sdim const PBQP::Solution &Solution, 705280031Sdim VirtRegMap &VRM, 706280031Sdim Spiller &VRegSpiller) { 707280031Sdim MachineFunction &MF = G.getMetadata().MF; 708280031Sdim LiveIntervals &LIS = G.getMetadata().LIS; 709288943Sdim const TargetRegisterInfo &TRI = *MF.getSubtarget().getRegisterInfo(); 710280031Sdim (void)TRI; 711280031Sdim 712193323Sed // Set to true if we have any spills 713280031Sdim bool AnotherRoundNeeded = false; 714193323Sed 715193323Sed // Clear the existing allocation. 716280031Sdim VRM.clearAllVirt(); 717193323Sed 718218893Sdim // Iterate over the nodes mapping the PBQP solution to a register 719218893Sdim // assignment. 720280031Sdim for (auto NId : G.nodeIds()) { 721280031Sdim unsigned VReg = G.getNodeMetadata(NId).getVReg(); 722280031Sdim unsigned AllocOption = Solution.getSelection(NId); 723193323Sed 724280031Sdim if (AllocOption != PBQP::RegAlloc::getSpillOptionIdx()) { 725280031Sdim unsigned PReg = G.getNodeMetadata(NId).getAllowedRegs()[AllocOption - 1]; 726341825Sdim LLVM_DEBUG(dbgs() << "VREG " << printReg(VReg, &TRI) << " -> " 727341825Sdim << TRI.getName(PReg) << "\n"); 728280031Sdim assert(PReg != 0 && "Invalid preg selected."); 729280031Sdim VRM.assignVirt2Phys(VReg, PReg); 730280031Sdim } else { 731288943Sdim // Spill VReg. If this introduces new intervals we'll need another round 732288943Sdim // of allocation. 733288943Sdim SmallVector<unsigned, 8> NewVRegs; 734288943Sdim spillVReg(VReg, NewVRegs, MF, LIS, VRM, VRegSpiller); 735288943Sdim AnotherRoundNeeded |= !NewVRegs.empty(); 736193323Sed } 737193323Sed } 738193323Sed 739280031Sdim return !AnotherRoundNeeded; 740193323Sed} 741193323Sed 742280031Sdimvoid RegAllocPBQP::finalizeAlloc(MachineFunction &MF, 743280031Sdim LiveIntervals &LIS, 744280031Sdim VirtRegMap &VRM) const { 745280031Sdim MachineRegisterInfo &MRI = MF.getRegInfo(); 746218893Sdim 747193323Sed // First allocate registers for the empty intervals. 748218893Sdim for (RegSet::const_iterator 749280031Sdim I = EmptyIntervalVRegs.begin(), E = EmptyIntervalVRegs.end(); 750280031Sdim I != E; ++I) { 751280031Sdim LiveInterval &LI = LIS.getInterval(*I); 752193323Sed 753280031Sdim unsigned PReg = MRI.getSimpleHint(LI.reg); 754198090Srdivacky 755280031Sdim if (PReg == 0) { 756280031Sdim const TargetRegisterClass &RC = *MRI.getRegClass(LI.reg); 757321369Sdim const ArrayRef<MCPhysReg> RawPRegOrder = RC.getRawAllocationOrder(MF); 758321369Sdim for (unsigned CandidateReg : RawPRegOrder) { 759321369Sdim if (!VRM.getRegInfo().isReserved(CandidateReg)) { 760321369Sdim PReg = CandidateReg; 761321369Sdim break; 762321369Sdim } 763321369Sdim } 764321369Sdim assert(PReg && 765321369Sdim "No un-reserved physical registers in this register class"); 766193323Sed } 767193323Sed 768280031Sdim VRM.assignVirt2Phys(LI.reg, PReg); 769193323Sed } 770193323Sed} 771193323Sed 772309124Sdimvoid RegAllocPBQP::postOptimization(Spiller &VRegSpiller, LiveIntervals &LIS) { 773309124Sdim VRegSpiller.postOptimization(); 774309124Sdim /// Remove dead defs because of rematerialization. 775309124Sdim for (auto DeadInst : DeadRemats) { 776309124Sdim LIS.RemoveMachineInstrFromMaps(*DeadInst); 777309124Sdim DeadInst->eraseFromParent(); 778309124Sdim } 779309124Sdim DeadRemats.clear(); 780309124Sdim} 781309124Sdim 782280031Sdimstatic inline float normalizePBQPSpillWeight(float UseDefFreq, unsigned Size, 783280031Sdim unsigned NumInstr) { 784280031Sdim // All intervals have a spill weight that is mostly proportional to the number 785280031Sdim // of uses, with uses in loops having a bigger weight. 786280031Sdim return NumInstr * normalizeSpillWeight(UseDefFreq, Size, 1); 787280031Sdim} 788280031Sdim 789218893Sdimbool RegAllocPBQP::runOnMachineFunction(MachineFunction &MF) { 790280031Sdim LiveIntervals &LIS = getAnalysis<LiveIntervals>(); 791280031Sdim MachineBlockFrequencyInfo &MBFI = 792280031Sdim getAnalysis<MachineBlockFrequencyInfo>(); 793193323Sed 794280031Sdim VirtRegMap &VRM = getAnalysis<VirtRegMap>(); 795193323Sed 796296417Sdim calculateSpillWeightsAndHints(LIS, MF, &VRM, getAnalysis<MachineLoopInfo>(), 797296417Sdim MBFI, normalizePBQPSpillWeight); 798296417Sdim 799280031Sdim std::unique_ptr<Spiller> VRegSpiller(createInlineSpiller(*this, MF, VRM)); 800261991Sdim 801280031Sdim MF.getRegInfo().freezeReservedRegs(MF); 802193323Sed 803341825Sdim LLVM_DEBUG(dbgs() << "PBQP Register Allocating for " << MF.getName() << "\n"); 804212904Sdim 805193323Sed // Allocator main loop: 806193323Sed // 807193323Sed // * Map current regalloc problem to a PBQP problem 808193323Sed // * Solve the PBQP problem 809193323Sed // * Map the solution back to a register allocation 810193323Sed // * Spill if necessary 811193323Sed // 812193323Sed // This process is continued till no more spills are generated. 813193323Sed 814193323Sed // Find the vreg intervals in need of allocation. 815280031Sdim findVRegIntervalsToAlloc(MF, LIS); 816193323Sed 817243830Sdim#ifndef NDEBUG 818327952Sdim const Function &F = MF.getFunction(); 819280031Sdim std::string FullyQualifiedName = 820280031Sdim F.getParent()->getModuleIdentifier() + "." + F.getName().str(); 821243830Sdim#endif 822234353Sdim 823193323Sed // If there are non-empty intervals allocate them using pbqp. 824280031Sdim if (!VRegsToAlloc.empty()) { 825288943Sdim const TargetSubtargetInfo &Subtarget = MF.getSubtarget(); 826280031Sdim std::unique_ptr<PBQPRAConstraintList> ConstraintsRoot = 827360784Sdim std::make_unique<PBQPRAConstraintList>(); 828360784Sdim ConstraintsRoot->addConstraint(std::make_unique<SpillCosts>()); 829360784Sdim ConstraintsRoot->addConstraint(std::make_unique<Interference>()); 830280031Sdim if (PBQPCoalescing) 831360784Sdim ConstraintsRoot->addConstraint(std::make_unique<Coalescing>()); 832280031Sdim ConstraintsRoot->addConstraint(Subtarget.getCustomPBQPConstraints()); 833193323Sed 834280031Sdim bool PBQPAllocComplete = false; 835280031Sdim unsigned Round = 0; 836193323Sed 837280031Sdim while (!PBQPAllocComplete) { 838341825Sdim LLVM_DEBUG(dbgs() << " PBQP Regalloc round " << Round << ":\n"); 839234353Sdim 840280031Sdim PBQPRAGraph G(PBQPRAGraph::GraphMetadata(MF, LIS, MBFI)); 841288943Sdim initializeGraph(G, VRM, *VRegSpiller); 842280031Sdim ConstraintsRoot->apply(G); 843280031Sdim 844234353Sdim#ifndef NDEBUG 845280031Sdim if (PBQPDumpGraphs) { 846280031Sdim std::ostringstream RS; 847280031Sdim RS << Round; 848280031Sdim std::string GraphFileName = FullyQualifiedName + "." + RS.str() + 849280031Sdim ".pbqpgraph"; 850280031Sdim std::error_code EC; 851360784Sdim raw_fd_ostream OS(GraphFileName, EC, sys::fs::OF_Text); 852341825Sdim LLVM_DEBUG(dbgs() << "Dumping graph for round " << Round << " to \"" 853341825Sdim << GraphFileName << "\"\n"); 854288943Sdim G.dump(OS); 855234353Sdim } 856234353Sdim#endif 857234353Sdim 858280031Sdim PBQP::Solution Solution = PBQP::RegAlloc::solve(G); 859280031Sdim PBQPAllocComplete = mapPBQPToRegAlloc(G, Solution, VRM, *VRegSpiller); 860280031Sdim ++Round; 861193323Sed } 862193323Sed } 863193323Sed 864193323Sed // Finalise allocation, allocate empty ranges. 865280031Sdim finalizeAlloc(MF, LIS, VRM); 866309124Sdim postOptimization(*VRegSpiller, LIS); 867280031Sdim VRegsToAlloc.clear(); 868280031Sdim EmptyIntervalVRegs.clear(); 869193323Sed 870341825Sdim LLVM_DEBUG(dbgs() << "Post alloc VirtRegMap:\n" << VRM << "\n"); 871193323Sed 872193323Sed return true; 873193323Sed} 874193323Sed 875296417Sdim/// Create Printable object for node and register info. 876296417Sdimstatic Printable PrintNodeInfo(PBQP::RegAlloc::PBQPRAGraph::NodeId NId, 877296417Sdim const PBQP::RegAlloc::PBQPRAGraph &G) { 878296417Sdim return Printable([NId, &G](raw_ostream &OS) { 879288943Sdim const MachineRegisterInfo &MRI = G.getMetadata().MF.getRegInfo(); 880288943Sdim const TargetRegisterInfo *TRI = MRI.getTargetRegisterInfo(); 881288943Sdim unsigned VReg = G.getNodeMetadata(NId).getVReg(); 882288943Sdim const char *RegClassName = TRI->getRegClassName(MRI.getRegClass(VReg)); 883327952Sdim OS << NId << " (" << RegClassName << ':' << printReg(VReg, TRI) << ')'; 884296417Sdim }); 885288943Sdim} 886288943Sdim 887321369Sdim#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 888321369SdimLLVM_DUMP_METHOD void PBQP::RegAlloc::PBQPRAGraph::dump(raw_ostream &OS) const { 889288943Sdim for (auto NId : nodeIds()) { 890288943Sdim const Vector &Costs = getNodeCosts(NId); 891288943Sdim assert(Costs.getLength() != 0 && "Empty vector in graph."); 892288943Sdim OS << PrintNodeInfo(NId, *this) << ": " << Costs << '\n'; 893288943Sdim } 894288943Sdim OS << '\n'; 895288943Sdim 896288943Sdim for (auto EId : edgeIds()) { 897288943Sdim NodeId N1Id = getEdgeNode1Id(EId); 898288943Sdim NodeId N2Id = getEdgeNode2Id(EId); 899288943Sdim assert(N1Id != N2Id && "PBQP graphs should not have self-edges."); 900288943Sdim const Matrix &M = getEdgeCosts(EId); 901288943Sdim assert(M.getRows() != 0 && "No rows in matrix."); 902288943Sdim assert(M.getCols() != 0 && "No cols in matrix."); 903288943Sdim OS << PrintNodeInfo(N1Id, *this) << ' ' << M.getRows() << " rows / "; 904288943Sdim OS << PrintNodeInfo(N2Id, *this) << ' ' << M.getCols() << " cols:\n"; 905288943Sdim OS << M << '\n'; 906288943Sdim } 907288943Sdim} 908288943Sdim 909321369SdimLLVM_DUMP_METHOD void PBQP::RegAlloc::PBQPRAGraph::dump() const { 910321369Sdim dump(dbgs()); 911321369Sdim} 912321369Sdim#endif 913288943Sdim 914288943Sdimvoid PBQP::RegAlloc::PBQPRAGraph::printDot(raw_ostream &OS) const { 915288943Sdim OS << "graph {\n"; 916288943Sdim for (auto NId : nodeIds()) { 917288943Sdim OS << " node" << NId << " [ label=\"" 918288943Sdim << PrintNodeInfo(NId, *this) << "\\n" 919288943Sdim << getNodeCosts(NId) << "\" ]\n"; 920288943Sdim } 921288943Sdim 922288943Sdim OS << " edge [ len=" << nodeIds().size() << " ]\n"; 923288943Sdim for (auto EId : edgeIds()) { 924288943Sdim OS << " node" << getEdgeNode1Id(EId) 925288943Sdim << " -- node" << getEdgeNode2Id(EId) 926288943Sdim << " [ label=\""; 927288943Sdim const Matrix &EdgeCosts = getEdgeCosts(EId); 928288943Sdim for (unsigned i = 0; i < EdgeCosts.getRows(); ++i) { 929288943Sdim OS << EdgeCosts.getRowAsVector(i) << "\\n"; 930288943Sdim } 931288943Sdim OS << "\" ]\n"; 932288943Sdim } 933288943Sdim OS << "}\n"; 934288943Sdim} 935288943Sdim 936280031SdimFunctionPass *llvm::createPBQPRegisterAllocator(char *customPassID) { 937280031Sdim return new RegAllocPBQP(customPassID); 938193323Sed} 939193323Sed 940218893SdimFunctionPass* llvm::createDefaultPBQPRegisterAllocator() { 941280031Sdim return createPBQPRegisterAllocator(); 942218893Sdim} 943