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