LLVM  8.0.0svn
RegAllocPBQP.cpp
Go to the documentation of this file.
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 
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"
57 #include "llvm/CodeGen/PBQP/Math.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"
71 #include "llvm/Support/Compiler.h"
72 #include "llvm/Support/Debug.h"
74 #include "llvm/Support/Printable.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 RegisterPBQPRepAlloc("pbqp", "PBQP register allocator",
98 
99 static cl::opt<bool>
100 PBQPCoalescing("pbqp-coalescing",
101  cl::desc("Attempt coalescing during PBQP register allocation."),
102  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 class RegAllocPBQP : public MachineFunctionPass {
118 public:
119  static char ID;
120 
121  /// Construct a PBQP register allocator.
122  RegAllocPBQP(char *cPassID = nullptr)
123  : MachineFunctionPass(ID), customPassID(cPassID) {
128  }
129 
130  /// Return the pass name.
131  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  MachineFunctionProperties getRequiredProperties() const override {
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.
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 class SpillCosts : public PBQPRAConstraint {
193 public:
194  void apply(PBQPRAGraph &G) override {
195  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  for (auto NId : G.nodeIds()) {
202  PBQP::PBQPNum SpillCost =
203  LIS.getInterval(G.getNodeMetadata(NId).getVReg()).weight;
204  if (SpillCost == 0.0)
205  SpillCost = std::numeric_limits<PBQP::PBQPNum>::min();
206  else
207  SpillCost += MinSpillCost;
208  PBQPRAGraph::RawVector NodeCosts(G.getNodeCosts(NId));
209  NodeCosts[PBQP::RegAlloc::getSpillOptionIdx()] = SpillCost;
210  G.setNodeCosts(NId, std::move(NodeCosts));
211  }
212  }
213 };
214 
215 /// Add interference edges between overlapping vregs.
216 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  bool haveDisjointAllowedRegs(const PBQPRAGraph &G, PBQPRAGraph::NodeId NId,
227  const DisjointAllowedRegsCache &D) const {
228  const auto *NRegs = &G.getNodeMetadata(NId).getAllowedRegs();
229  const auto *MRegs = &G.getNodeMetadata(MId).getAllowedRegs();
230 
231  if (NRegs == MRegs)
232  return false;
233 
234  if (NRegs < MRegs)
235  return D.count(IKey(NRegs, MRegs)) > 0;
236 
237  return D.count(IKey(MRegs, NRegs)) > 0;
238  }
239 
240  void setDisjointAllowedRegs(const PBQPRAGraph &G, PBQPRAGraph::NodeId NId,
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  if (NRegs < MRegs)
249  D.insert(IKey(NRegs, MRegs));
250  else
251  D.insert(IKey(MRegs, NRegs));
252  }
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  return std::get<0>(I)->segments[std::get<1>(I)].start;
263  }
264 
265  static SlotIndex getEndPoint(const IntervalInfo &I) {
266  return std::get<0>(I)->segments[std::get<1>(I)].end;
267  }
268 
269  static PBQP::GraphBase::NodeId getNodeId(const IntervalInfo &I) {
270  return std::get<2>(I);
271  }
272 
273  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  return getStartPoint(I1) > getStartPoint(I2);
278  }
279 
280  static bool lowestEndPoint(const IntervalInfo &I1,
281  const IntervalInfo &I2) {
282  SlotIndex E1 = getEndPoint(I1);
283  SlotIndex E2 = getEndPoint(I2);
284 
285  if (E1 < E2)
286  return true;
287 
288  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  return std::get<0>(I1)->reg < std::get<0>(I2)->reg;
295  }
296 
297  static bool isAtLastSegment(const IntervalInfo &I) {
298  return std::get<1>(I) == std::get<0>(I)->size() - 1;
299  }
300 
301  static IntervalInfo nextSegment(const IntervalInfo &I) {
302  return std::make_tuple(std::get<0>(I), std::get<1>(I) + 1, std::get<2>(I));
303  }
304 
305 public:
306  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  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  IntervalQueue Inactive(lowestStartPoint);
332 
333  // Start by building the inactive set.
334  for (auto NId : G.nodeIds()) {
335  unsigned VReg = G.getNodeMetadata(NId).getVReg();
336  LiveInterval &LI = LIS.getInterval(VReg);
337  assert(!LI.empty() && "PBQP graph contains node for empty interval");
338  Inactive.push(std::make_tuple(&LI, 0, NId));
339  }
340 
341  while (!Inactive.empty()) {
342  // Tentatively grab the "next" interval - this choice may be overriden
343  // below.
344  IntervalInfo Cur = Inactive.top();
345 
346  // Retire any active intervals that end before Cur starts.
347  IntervalSet::iterator RetireItr = Active.begin();
348  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  if (!isAtLastSegment(*RetireItr))
353  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  Inactive.pop();
363 
364  // At this point we know that Cur overlaps all active intervals. Add the
365  // interference edges.
366  PBQP::GraphBase::NodeId NId = getNodeId(Cur);
367  for (const auto &A : Active) {
368  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  if (haveDisjointAllowedRegs(G, NId, MId, D))
373  continue;
374 
375  // Check that we haven't already added this edge
376  IEdgeKey EK(std::min(NId, MId), std::max(NId, MId));
377  if (EC.count(EK))
378  continue;
379 
380  // This is a new edge - add it to the graph.
381  if (!createInterferenceEdge(G, NId, MId, C))
382  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  }
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  bool createInterferenceEdge(PBQPRAGraph &G,
400  IMatrixCache &C) {
401  const TargetRegisterInfo &TRI =
402  *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  IMatrixCache::iterator I = C.find(K);
409  if (I != C.end()) {
410  G.addEdgeBypassingCostAllocator(NId, MId, I->second);
411  return true;
412  }
413 
414  PBQPRAGraph::RawMatrix M(NRegs.size() + 1, MRegs.size() + 1, 0);
415  bool NodesInterfere = false;
416  for (unsigned I = 0; I != NRegs.size(); ++I) {
417  unsigned PRegN = NRegs[I];
418  for (unsigned J = 0; J != MRegs.size(); ++J) {
419  unsigned PRegM = MRegs[J];
420  if (TRI.regsOverlap(PRegN, PRegM)) {
421  M[I + 1][J + 1] = std::numeric_limits<PBQP::PBQPNum>::infinity();
422  NodesInterfere = true;
423  }
424  }
425  }
426 
427  if (!NodesInterfere)
428  return false;
429 
430  PBQPRAGraph::EdgeId EId = G.addEdge(NId, MId, std::move(M));
431  C[K] = G.getEdgeCostsPtr(EId);
432 
433  return true;
434  }
435 };
436 
437 class Coalescing : public PBQPRAConstraint {
438 public:
439  void apply(PBQPRAGraph &G) override {
440  MachineFunction &MF = G.getMetadata().MF;
441  MachineBlockFrequencyInfo &MBFI = G.getMetadata().MBFI;
443 
444  // Scan the machine function and add a coalescing cost whenever CoalescerPair
445  // gives the Ok.
446  for (const auto &MBB : MF) {
447  for (const auto &MI : MBB) {
448  // Skip not-coalescable or already coalesced copies.
449  if (!CP.setRegisters(&MI) || CP.getSrcReg() == CP.getDstReg())
450  continue;
451 
452  unsigned DstReg = CP.getDstReg();
453  unsigned SrcReg = CP.getSrcReg();
454 
455  const float Scale = 1.0f / MBFI.getEntryFreq();
456  PBQP::PBQPNum CBenefit = MBFI.getBlockFreq(&MBB).getFrequency() * Scale;
457 
458  if (CP.isPhys()) {
459  if (!MF.getRegInfo().isAllocatable(DstReg))
460  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  while (PRegOpt < Allowed.size() && Allowed[PRegOpt] != DstReg)
469  ++PRegOpt;
470 
471  if (PRegOpt < Allowed.size()) {
472  PBQPRAGraph::RawVector NewCosts(G.getNodeCosts(NId));
473  NewCosts[PRegOpt + 1] -= CBenefit;
474  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  if (EId == G.invalidEdgeId()) {
486  PBQPRAGraph::RawMatrix Costs(Allowed1->size() + 1,
487  Allowed2->size() + 1, 0);
488  addVirtRegCoalesce(Costs, *Allowed1, *Allowed2, CBenefit);
489  G.addEdge(N1Id, N2Id, std::move(Costs));
490  } else {
491  if (G.getEdgeNode1Id(EId) == N2Id) {
492  std::swap(N1Id, N2Id);
493  std::swap(Allowed1, Allowed2);
494  }
495  PBQPRAGraph::RawMatrix Costs(G.getEdgeCosts(EId));
496  addVirtRegCoalesce(Costs, *Allowed1, *Allowed2, CBenefit);
497  G.updateEdgeCosts(EId, std::move(Costs));
498  }
499  }
500  }
501  }
502  }
503 
504 private:
505  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  for (unsigned I = 0; I != Allowed1.size(); ++I) {
513  unsigned PReg1 = Allowed1[I];
514  for (unsigned J = 0; J != Allowed2.size(); ++J) {
515  unsigned PReg2 = Allowed2[J];
516  if (PReg1 == PReg2)
517  CostMat[I + 1][J + 1] -= Benefit;
518  }
519  }
520  }
521 };
522 
523 } // end anonymous namespace
524 
525 // Out-of-line destructor/anchor for PBQPRAConstraint.
527 
528 void PBQPRAConstraint::anchor() {}
529 
530 void PBQPRAConstraintList::anchor() {}
531 
532 void RegAllocPBQP::getAnalysisUsage(AnalysisUsage &au) const {
533  au.setPreservesCFG();
536  au.addRequired<SlotIndexes>();
540  //au.addRequiredID(SplitCriticalEdgesID);
541  if (customPassID)
542  au.addRequiredID(*customPassID);
543  au.addRequired<LiveStacks>();
544  au.addPreserved<LiveStacks>();
551  au.addRequired<VirtRegMap>();
552  au.addPreserved<VirtRegMap>();
554 }
555 
556 void RegAllocPBQP::findVRegIntervalsToAlloc(const MachineFunction &MF,
557  LiveIntervals &LIS) {
558  const MachineRegisterInfo &MRI = MF.getRegInfo();
559 
560  // Iterate over all live ranges.
561  for (unsigned I = 0, E = MRI.getNumVirtRegs(); I != E; ++I) {
563  if (MRI.reg_nodbg_empty(Reg))
564  continue;
565  VRegsToAlloc.insert(Reg);
566  }
567 }
568 
569 static bool isACalleeSavedRegister(unsigned reg, const TargetRegisterInfo &TRI,
570  const MachineFunction &MF) {
571  const MCPhysReg *CSR = MF.getRegInfo().getCalleeSavedRegs();
572  for (unsigned i = 0; CSR[i] != 0; ++i)
573  if (TRI.regsOverlap(reg, CSR[i]))
574  return true;
575  return false;
576 }
577 
578 void RegAllocPBQP::initializeGraph(PBQPRAGraph &G, VirtRegMap &VRM,
579  Spiller &VRegSpiller) {
580  MachineFunction &MF = G.getMetadata().MF;
581 
582  LiveIntervals &LIS = G.getMetadata().LIS;
583  const MachineRegisterInfo &MRI = G.getMetadata().MF.getRegInfo();
584  const TargetRegisterInfo &TRI =
585  *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  while (!Worklist.empty()) {
592  unsigned VReg = Worklist.back();
593  Worklist.pop_back();
594 
595  LiveInterval &VRegLI = LIS.getInterval(VReg);
596 
597  // If this is an empty interval move it to the EmptyIntervalVRegs set then
598  // continue.
599  if (VRegLI.empty()) {
600  EmptyIntervalVRegs.insert(VRegLI.reg);
601  VRegsToAlloc.erase(VRegLI.reg);
602  continue;
603  }
604 
605  const TargetRegisterClass *TRC = MRI.getRegClass(VReg);
606 
607  // Record any overlaps with regmask operands.
608  BitVector RegMaskOverlaps;
609  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  for (unsigned I = 0; I != RawPRegOrder.size(); ++I) {
615  unsigned PReg = RawPRegOrder[I];
616  if (MRI.isReserved(PReg))
617  continue;
618 
619  // vregLI crosses a regmask operand that clobbers preg.
620  if (!RegMaskOverlaps.empty() && !RegMaskOverlaps.test(PReg))
621  continue;
622 
623  // vregLI overlaps fixed regunit interference.
624  bool Interference = false;
625  for (MCRegUnitIterator Units(PReg, &TRI); Units.isValid(); ++Units) {
626  if (VRegLI.overlaps(LIS.getRegUnit(*Units))) {
627  Interference = true;
628  break;
629  }
630  }
631  if (Interference)
632  continue;
633 
634  // preg is usable for this virtual register.
635  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  if (VRegAllowed.empty()) {
641  SmallVector<unsigned, 8> NewVRegs;
642  spillVReg(VReg, NewVRegs, MF, LIS, VRM, VRegSpiller);
643  Worklist.insert(Worklist.end(), NewVRegs.begin(), NewVRegs.end());
644  continue;
645  } else
646  VRegAllowedMap[VReg] = std::move(VRegAllowed);
647  }
648 
649  for (auto &KV : VRegAllowedMap) {
650  auto VReg = KV.first;
651 
652  // Move empty intervals to the EmptyIntervalVReg set.
653  if (LIS.getInterval(VReg).empty()) {
654  EmptyIntervalVRegs.insert(VReg);
655  VRegsToAlloc.erase(VReg);
656  continue;
657  }
658 
659  auto &VRegAllowed = KV.second;
660 
661  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  for (unsigned i = 0; i != VRegAllowed.size(); ++i)
666  if (isACalleeSavedRegister(VRegAllowed[i], TRI, MF))
667  NodeCosts[1 + i] += 1.0;
668 
669  PBQPRAGraph::NodeId NId = G.addNode(std::move(NodeCosts));
670  G.getNodeMetadata(NId).setVReg(VReg);
671  G.getNodeMetadata(NId).setAllowedRegs(
672  G.getMetadata().getAllowedRegs(std::move(VRegAllowed)));
673  G.getMetadata().setNodeIdForVReg(VReg, NId);
674  }
675 }
676 
677 void RegAllocPBQP::spillVReg(unsigned VReg,
678  SmallVectorImpl<unsigned> &NewIntervals,
679  MachineFunction &MF, LiveIntervals &LIS,
680  VirtRegMap &VRM, Spiller &VRegSpiller) {
681  VRegsToAlloc.erase(VReg);
682  LiveRangeEdit LRE(&LIS.getInterval(VReg), NewIntervals, MF, LIS, &VRM,
683  nullptr, &DeadRemats);
684  VRegSpiller.spill(LRE);
685 
686  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  for (LiveRangeEdit::iterator I = LRE.begin(), E = LRE.end();
694  I != E; ++I) {
695  const LiveInterval &LI = LIS.getInterval(*I);
696  assert(!LI.empty() && "Empty spill range.");
697  LLVM_DEBUG(dbgs() << printReg(LI.reg, &TRI) << " ");
698  VRegsToAlloc.insert(LI.reg);
699  }
700 
701  LLVM_DEBUG(dbgs() << ")\n");
702 }
703 
704 bool RegAllocPBQP::mapPBQPToRegAlloc(const PBQPRAGraph &G,
705  const PBQP::Solution &Solution,
706  VirtRegMap &VRM,
707  Spiller &VRegSpiller) {
708  MachineFunction &MF = G.getMetadata().MF;
709  LiveIntervals &LIS = G.getMetadata().LIS;
710  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  for (auto NId : G.nodeIds()) {
722  unsigned VReg = G.getNodeMetadata(NId).getVReg();
723  unsigned AllocOption = Solution.getSelection(NId);
724 
725  if (AllocOption != PBQP::RegAlloc::getSpillOptionIdx()) {
726  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  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  spillVReg(VReg, NewVRegs, MF, LIS, VRM, VRegSpiller);
736  AnotherRoundNeeded |= !NewVRegs.empty();
737  }
738  }
739 
740  return !AnotherRoundNeeded;
741 }
742 
743 void RegAllocPBQP::finalizeAlloc(MachineFunction &MF,
744  LiveIntervals &LIS,
745  VirtRegMap &VRM) const {
746  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  I != E; ++I) {
752  LiveInterval &LI = LIS.getInterval(*I);
753 
754  unsigned PReg = MRI.getSimpleHint(LI.reg);
755 
756  if (PReg == 0) {
757  const TargetRegisterClass &RC = *MRI.getRegClass(LI.reg);
758  const ArrayRef<MCPhysReg> RawPRegOrder = RC.getRawAllocationOrder(MF);
759  for (unsigned CandidateReg : RawPRegOrder) {
760  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  VRM.assignVirt2Phys(LI.reg, PReg);
770  }
771 }
772 
773 void RegAllocPBQP::postOptimization(Spiller &VRegSpiller, LiveIntervals &LIS) {
774  VRegSpiller.postOptimization();
775  /// Remove dead defs because of rematerialization.
776  for (auto DeadInst : DeadRemats) {
777  LIS.RemoveMachineInstrFromMaps(*DeadInst);
778  DeadInst->eraseFromParent();
779  }
780  DeadRemats.clear();
781 }
782 
783 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  return NumInstr * normalizeSpillWeight(UseDefFreq, Size, 1);
788 }
789 
790 bool RegAllocPBQP::runOnMachineFunction(MachineFunction &MF) {
791  LiveIntervals &LIS = getAnalysis<LiveIntervals>();
793  getAnalysis<MachineBlockFrequencyInfo>();
794 
795  VirtRegMap &VRM = getAnalysis<VirtRegMap>();
796 
797  calculateSpillWeightsAndHints(LIS, MF, &VRM, getAnalysis<MachineLoopInfo>(),
799 
800  std::unique_ptr<Spiller> VRegSpiller(createInlineSpiller(*this, MF, VRM));
801 
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  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  if (!VRegsToAlloc.empty()) {
826  const TargetSubtargetInfo &Subtarget = MF.getSubtarget();
827  std::unique_ptr<PBQPRAConstraintList> ConstraintsRoot =
828  llvm::make_unique<PBQPRAConstraintList>();
829  ConstraintsRoot->addConstraint(llvm::make_unique<SpillCosts>());
830  ConstraintsRoot->addConstraint(llvm::make_unique<Interference>());
831  if (PBQPCoalescing)
832  ConstraintsRoot->addConstraint(llvm::make_unique<Coalescing>());
833  ConstraintsRoot->addConstraint(Subtarget.getCustomPBQPConstraints());
834 
835  bool PBQPAllocComplete = false;
836  unsigned Round = 0;
837 
838  while (!PBQPAllocComplete) {
839  LLVM_DEBUG(dbgs() << " PBQP Regalloc round " << Round << ":\n");
840 
841  PBQPRAGraph G(PBQPRAGraph::GraphMetadata(MF, LIS, MBFI));
842  initializeGraph(G, VRM, *VRegSpiller);
843  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 
860  PBQPAllocComplete = mapPBQPToRegAlloc(G, Solution, VRM, *VRegSpiller);
861  ++Round;
862  }
863  }
864 
865  // Finalise allocation, allocate empty ranges.
866  finalizeAlloc(MF, LIS, VRM);
867  postOptimization(*VRegSpiller, LIS);
868  VRegsToAlloc.clear();
869  EmptyIntervalVRegs.clear();
870 
871  LLVM_DEBUG(dbgs() << "Post alloc VirtRegMap:\n" << VRM << "\n");
872 
873  return true;
874 }
875 
876 /// Create Printable object for node and register info.
878  const PBQP::RegAlloc::PBQPRAGraph &G) {
879  return Printable([NId, &G](raw_ostream &OS) {
880  const MachineRegisterInfo &MRI = G.getMetadata().MF.getRegInfo();
881  const TargetRegisterInfo *TRI = MRI.getTargetRegisterInfo();
882  unsigned VReg = G.getNodeMetadata(NId).getVReg();
883  const char *RegClassName = TRI->getRegClassName(MRI.getRegClass(VReg));
884  OS << NId << " (" << RegClassName << ':' << printReg(VReg, TRI) << ')';
885  });
886 }
887 
888 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
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 
911  dump(dbgs());
912 }
913 #endif
914 
916  OS << "graph {\n";
917  for (auto NId : nodeIds()) {
918  OS << " node" << NId << " [ label=\""
919  << PrintNodeInfo(NId, *this) << "\\n"
920  << getNodeCosts(NId) << "\" ]\n";
921  }
922 
923  OS << " edge [ len=" << nodeIds().size() << " ]\n";
924  for (auto EId : edgeIds()) {
925  OS << " node" << getEdgeNode1Id(EId)
926  << " -- node" << getEdgeNode2Id(EId)
927  << " [ label=\"";
928  const Matrix &EdgeCosts = getEdgeCosts(EId);
929  for (unsigned i = 0; i < EdgeCosts.getRows(); ++i) {
930  OS << EdgeCosts.getRowAsVector(i) << "\\n";
931  }
932  OS << "\" ]\n";
933  }
934  OS << "}\n";
935 }
936 
938  return new RegAllocPBQP(customPassID);
939 }
940 
943 }
bool reg_nodbg_empty(unsigned RegNo) const
reg_nodbg_empty - Return true if the only instructions using or defining Reg are Debug instructions...
uint64_t CallInst * C
bool empty() const
Definition: LiveInterval.h:370
Represents a solution to a PBQP problem.
Definition: Solution.h:27
static Printable PrintNodeInfo(PBQP::RegAlloc::PBQPRAGraph::NodeId NId, const PBQP::RegAlloc::PBQPRAGraph &G)
Create Printable object for node and register info.
Abstract base for classes implementing PBQP register allocation constraints (e.g. ...
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
const unsigned reg
Definition: LiveInterval.h:667
LLVM_NODISCARD std::string str() const
str - Get the contents as an std::string.
Definition: StringRef.h:228
const TargetRegisterClass * getRegClass(unsigned Reg) const
Return the register class of the specified virtual register.
void RemoveMachineInstrFromMaps(MachineInstr &MI)
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
bool empty() const
empty - Tests whether there are no bits in this bitvector.
Definition: BitVector.h:167
static unsigned index2VirtReg(unsigned Index)
Convert a 0-based index to a virtual register number.
EdgeId addEdge(NodeId N1Id, NodeId N2Id, OtherVectorT Costs)
Add an edge between the given nodes with the given costs.
Definition: Graph.h:410
Holds a vector of the allowed physical regs for a vreg.
Definition: RegAllocPBQP.h:93
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
ArrayRef< MCPhysReg > getRawAllocationOrder(const MachineFunction &MF) const
Returns the preferred order for allocating registers from this register class in MF.
Implements a dense probed hash-table based set.
Definition: DenseSet.h:250
EdgeId findEdge(NodeId N1Id, NodeId N2Id)
Get the edge connecting two nodes.
Definition: Graph.h:574
LiveInterval - This class represents the liveness of a register, or stack slot.
Definition: LiveInterval.h:638
virtual ~PBQPRAConstraint()=0
unsigned Reg
bool test(unsigned Idx) const
Definition: BitVector.h:502
Spiller interface.
Definition: Spiller.h:24
uint64_t getFrequency() const
Returns the frequency as a fixpoint number scaled by the entry frequency.
MachineBlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate machine basic b...
void updateEdgeCosts(EdgeId EId, OtherMatrixT Costs)
Update an edge&#39;s cost matrix.
Definition: Graph.h:509
unsigned const TargetRegisterInfo * TRI
F(f)
NodeId addEdgeBypassingCostAllocator(NodeId N1Id, NodeId N2Id, OtherMatrixPtrT Costs)
Add an edge bypassing the cost allocator.
Definition: Graph.h:435
NodeId getEdgeNode1Id(EdgeId EId) const
Get the first node connected to this edge.
Definition: Graph.h:546
bool checkRegMaskInterference(LiveInterval &LI, BitVector &UsableRegs)
Test if LI is live across any register mask instructions, and compute a bit mask of physical register...
virtual void spill(LiveRangeEdit &LRE)=0
spill - Spill the LRE.getParent() live interval.
FunctionPass * createPBQPRegisterAllocator(char *customPassID=nullptr)
Create a PBQP register allocator instance.
virtual std::unique_ptr< PBQPRAConstraint > getCustomPBQPConstraints() const
Return PBQPConstraint(s) for the target.
const char * getRegClassName(const TargetRegisterClass *Class) const
Returns the name of the register class.
NodeMetadata & getNodeMetadata(NodeId NId)
Definition: Graph.h:493
AnalysisUsage & addRequired()
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
Printable printReg(unsigned Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)
Prints virtual and physical registers with or without a TRI instance.
typename RegAllocSolverImpl ::GraphMetadata GraphMetadata
Definition: Graph.h:60
A helper class for register coalescers.
void apply(Opt *O, const Mod &M, const Mods &... Ms)
Definition: CommandLine.h:1173
void freezeReservedRegs(const MachineFunction &)
freezeReservedRegs - Called by the register allocator to freeze the set of reserved registers before ...
float PBQPNum
Definition: Math.h:23
#define LLVM_DUMP_METHOD
Definition: Compiler.h:74
static cl::opt< bool > PBQPCoalescing("pbqp-coalescing", cl::desc("Attempt coalescing during PBQP register allocation."), cl::init(false), cl::Hidden)
NodeIdSet nodeIds() const
Definition: Graph.h:450
SlotIndexes pass.
Definition: SlotIndexes.h:331
RegisterRegAlloc class - Track the registration of register allocators.
typename RegAllocSolverImpl ::Matrix Matrix
Definition: Graph.h:55
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
const Matrix & getEdgeCosts(EdgeId EId) const
Get an edge&#39;s cost matrix.
Definition: Graph.h:531
uint16_t MCPhysReg
An unsigned integer type large enough to represent all physical registers, but not necessarily virtua...
const char * getName(unsigned RegNo) const
Return the human-readable symbolic target-specific name for the specified physical register...
unsigned NodeId
Definition: Graph.h:29
const MatrixPtr & getEdgeCostsPtr(EdgeId EId) const
Get a MatrixPtr to a node&#39;s cost matrix.
Definition: Graph.h:524
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:410
void initializeSlotIndexesPass(PassRegistry &)
const TargetRegisterInfo * getTargetRegisterInfo() const
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
unsigned const MachineRegisterInfo * MRI
const Vector & getNodeCosts(NodeId NId) const
Get a node&#39;s cost vector.
Definition: Graph.h:489
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
void initializeLiveStacksPass(PassRegistry &)
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:149
MachineRegisterInfo & getRegInfo() const
Definition: VirtRegMap.h:88
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator begin()
Definition: SmallVector.h:129
BlockFrequency getBlockFreq(const MachineBasicBlock *MBB) const
getblockFreq - Return block frequency.
Represent the analysis usage information of a pass.
void initializeLiveIntervalsPass(PassRegistry &)
FunctionPass * createDefaultPBQPRegisterAllocator()
PBQPRegisterAllocation Pass - This pass implements the Partitioned Boolean Quadratic Prograaming (PBQ...
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:285
static bool isACalleeSavedRegister(unsigned reg, const TargetRegisterInfo &TRI, const MachineFunction &MF)
static RegisterRegAlloc RegisterPBQPRepAlloc("pbqp", "PBQP register allocator", createDefaultPBQPRegisterAllocator)
unsigned getNumVirtRegs() const
getNumVirtRegs - Return the number of virtual registers created.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
const std::string & getModuleIdentifier() const
Get the module identifier which is, essentially, the name of the module.
Definition: Module.h:209
GraphMetadata & getMetadata()
Get a reference to the graph metadata.
Definition: Graph.h:348
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:418
void assignVirt2Phys(unsigned virtReg, MCPhysReg physReg)
creates a mapping for the specified virtual register to the specified physical register ...
Definition: VirtRegMap.cpp:84
void calculateSpillWeightsAndHints(LiveIntervals &LIS, MachineFunction &MF, VirtRegMap *VRM, const MachineLoopInfo &MLI, const MachineBlockFrequencyInfo &MBFI, VirtRegAuxInfo::NormalizingFn norm=normalizeSpillWeight)
Compute spill weights and allocation hints for all virtual register live intervals.
bool regsOverlap(unsigned regA, unsigned regB) const
Returns true if the two registers are equal or alias each other.
AnalysisUsage & addRequiredID(const void *ID)
Definition: Pass.cpp:299
Module.h This file contains the declarations for the Module class.
void printDot(raw_ostream &OS) const
Print a representation of this graph in DOT format.
const DataFlowGraph & G
Definition: RDFGraph.cpp:211
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:286
LiveInterval & getInterval(unsigned Reg)
const Function & getFunction() const
Return the LLVM function that this machine code represents.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:133
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:941
void dump() const
Dump this graph to dbgs().
bool isValid() const
isValid - returns true if this iterator is not yet at the end.
MachineRegisterInfo - Keep track of information for virtual and physical registers, including vreg register classes, use/def chains for registers, etc.
MachineFunctionProperties & set(Property P)
typename RegAllocSolverImpl ::RawVector RawVector
Definition: Graph.h:52
TargetSubtargetInfo - Generic base class for all target subtargets.
void initializeVirtRegMapPass(PassRegistry &)
Spiller * createInlineSpiller(MachineFunctionPass &pass, MachineFunction &mf, VirtRegMap &vrm)
Create and return a spiller that will insert spill code directly instead of deferring though VirtRegM...
static EdgeId invalidEdgeId()
Returns a value representing an invalid (non-existent) edge.
Definition: Graph.h:38
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator end()
Definition: SmallVector.h:133
A raw_ostream that writes to a file descriptor.
Definition: raw_ostream.h:366
bool overlaps(const LiveRange &other) const
overlaps - Return true if the intersection of the two live ranges is not empty.
Definition: LiveInterval.h:436
SmallVectorImpl< unsigned >::const_iterator iterator
Iterator for accessing the new registers added by this edit.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:56
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:224
#define I(x, y, z)
Definition: MD5.cpp:58
unsigned getSelection(GraphBase::NodeId nodeId) const
Get a node&#39;s selection.
Definition: Solution.h:46
Solution solve(PBQPRAGraph &G)
Definition: RegAllocPBQP.h:520
uint32_t Size
Definition: Profile.cpp:47
virtual void postOptimization()
Definition: Spiller.h:33
unsigned getSpillOptionIdx()
Spill option index.
Definition: RegAllocPBQP.h:47
typename RegAllocSolverImpl ::Vector Vector
Definition: Graph.h:54
static cl::opt< bool > PBQPDumpGraphs("pbqp-dump-graphs", cl::desc("Dump graphs for each function/round in the compilation unit."), cl::init(false), cl::Hidden)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static float normalizeSpillWeight(float UseDefFreq, unsigned Size, unsigned NumInstr)
Normalize the spill weight of a live interval.
void clearAllVirt()
clears all virtual to physical register mappings
Definition: VirtRegMap.h:120
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:566
typename RegAllocSolverImpl ::RawMatrix RawMatrix
Definition: Graph.h:53
simple register Simple Register Coalescing
const MCPhysReg * getCalleeSavedRegs() const
Returns list of callee saved registers.
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:46
IRTranslator LLVM IR MI
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:49
NodeId addNode(OtherVectorT Costs)
Add a node with the given costs.
Definition: Graph.h:376
Simple wrapper around std::function<void(raw_ostream&)>.
Definition: Printable.h:38
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object...
unsigned getSimpleHint(unsigned VReg) const
getSimpleHint - same as getRegAllocationHint except it will only return a target independent hint...
#define LLVM_DEBUG(X)
Definition: Debug.h:123
SlotIndex - An opaque wrapper around machine indexes.
Definition: SlotIndexes.h:84
void setNodeCosts(NodeId NId, OtherVectorT Costs)
Set a node&#39;s cost vector.
Definition: Graph.h:467
static float normalizePBQPSpillWeight(float UseDefFreq, unsigned Size, unsigned NumInstr)
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
LiveRange & getRegUnit(unsigned Unit)
Return the live range for register unit Unit.
Properties which a MachineFunction may have at a given point in time.
bool isReserved(unsigned PhysReg) const
isReserved - Returns true when PhysReg is a reserved register.