LLVM  6.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  LiveInterval &LI = LIS.getInterval(Reg);
565 
566  // If this live interval is non-empty we will use pbqp to allocate it.
567  // Empty intervals we allocate in a simple post-processing stage in
568  // finalizeAlloc.
569  if (!LI.empty()) {
570  VRegsToAlloc.insert(LI.reg);
571  } else {
572  EmptyIntervalVRegs.insert(LI.reg);
573  }
574  }
575 }
576 
577 static bool isACalleeSavedRegister(unsigned reg, const TargetRegisterInfo &TRI,
578  const MachineFunction &MF) {
579  const MCPhysReg *CSR = MF.getRegInfo().getCalleeSavedRegs();
580  for (unsigned i = 0; CSR[i] != 0; ++i)
581  if (TRI.regsOverlap(reg, CSR[i]))
582  return true;
583  return false;
584 }
585 
586 void RegAllocPBQP::initializeGraph(PBQPRAGraph &G, VirtRegMap &VRM,
587  Spiller &VRegSpiller) {
588  MachineFunction &MF = G.getMetadata().MF;
589 
590  LiveIntervals &LIS = G.getMetadata().LIS;
591  const MachineRegisterInfo &MRI = G.getMetadata().MF.getRegInfo();
592  const TargetRegisterInfo &TRI =
593  *G.getMetadata().MF.getSubtarget().getRegisterInfo();
594 
595  std::vector<unsigned> Worklist(VRegsToAlloc.begin(), VRegsToAlloc.end());
596 
597  while (!Worklist.empty()) {
598  unsigned VReg = Worklist.back();
599  Worklist.pop_back();
600 
601  const TargetRegisterClass *TRC = MRI.getRegClass(VReg);
602  LiveInterval &VRegLI = LIS.getInterval(VReg);
603 
604  // Record any overlaps with regmask operands.
605  BitVector RegMaskOverlaps;
606  LIS.checkRegMaskInterference(VRegLI, RegMaskOverlaps);
607 
608  // Compute an initial allowed set for the current vreg.
609  std::vector<unsigned> VRegAllowed;
610  ArrayRef<MCPhysReg> RawPRegOrder = TRC->getRawAllocationOrder(MF);
611  for (unsigned I = 0; I != RawPRegOrder.size(); ++I) {
612  unsigned PReg = RawPRegOrder[I];
613  if (MRI.isReserved(PReg))
614  continue;
615 
616  // vregLI crosses a regmask operand that clobbers preg.
617  if (!RegMaskOverlaps.empty() && !RegMaskOverlaps.test(PReg))
618  continue;
619 
620  // vregLI overlaps fixed regunit interference.
621  bool Interference = false;
622  for (MCRegUnitIterator Units(PReg, &TRI); Units.isValid(); ++Units) {
623  if (VRegLI.overlaps(LIS.getRegUnit(*Units))) {
624  Interference = true;
625  break;
626  }
627  }
628  if (Interference)
629  continue;
630 
631  // preg is usable for this virtual register.
632  VRegAllowed.push_back(PReg);
633  }
634 
635  // Check for vregs that have no allowed registers. These should be
636  // pre-spilled and the new vregs added to the worklist.
637  if (VRegAllowed.empty()) {
638  SmallVector<unsigned, 8> NewVRegs;
639  spillVReg(VReg, NewVRegs, MF, LIS, VRM, VRegSpiller);
640  Worklist.insert(Worklist.end(), NewVRegs.begin(), NewVRegs.end());
641  continue;
642  }
643 
644  PBQPRAGraph::RawVector NodeCosts(VRegAllowed.size() + 1, 0);
645 
646  // Tweak cost of callee saved registers, as using then force spilling and
647  // restoring them. This would only happen in the prologue / epilogue though.
648  for (unsigned i = 0; i != VRegAllowed.size(); ++i)
649  if (isACalleeSavedRegister(VRegAllowed[i], TRI, MF))
650  NodeCosts[1 + i] += 1.0;
651 
652  PBQPRAGraph::NodeId NId = G.addNode(std::move(NodeCosts));
653  G.getNodeMetadata(NId).setVReg(VReg);
654  G.getNodeMetadata(NId).setAllowedRegs(
655  G.getMetadata().getAllowedRegs(std::move(VRegAllowed)));
656  G.getMetadata().setNodeIdForVReg(VReg, NId);
657  }
658 }
659 
660 void RegAllocPBQP::spillVReg(unsigned VReg,
661  SmallVectorImpl<unsigned> &NewIntervals,
662  MachineFunction &MF, LiveIntervals &LIS,
663  VirtRegMap &VRM, Spiller &VRegSpiller) {
664  VRegsToAlloc.erase(VReg);
665  LiveRangeEdit LRE(&LIS.getInterval(VReg), NewIntervals, MF, LIS, &VRM,
666  nullptr, &DeadRemats);
667  VRegSpiller.spill(LRE);
668 
669  const TargetRegisterInfo &TRI = *MF.getSubtarget().getRegisterInfo();
670  (void)TRI;
671  DEBUG(dbgs() << "VREG " << PrintReg(VReg, &TRI) << " -> SPILLED (Cost: "
672  << LRE.getParent().weight << ", New vregs: ");
673 
674  // Copy any newly inserted live intervals into the list of regs to
675  // allocate.
676  for (LiveRangeEdit::iterator I = LRE.begin(), E = LRE.end();
677  I != E; ++I) {
678  const LiveInterval &LI = LIS.getInterval(*I);
679  assert(!LI.empty() && "Empty spill range.");
680  DEBUG(dbgs() << PrintReg(LI.reg, &TRI) << " ");
681  VRegsToAlloc.insert(LI.reg);
682  }
683 
684  DEBUG(dbgs() << ")\n");
685 }
686 
687 bool RegAllocPBQP::mapPBQPToRegAlloc(const PBQPRAGraph &G,
688  const PBQP::Solution &Solution,
689  VirtRegMap &VRM,
690  Spiller &VRegSpiller) {
691  MachineFunction &MF = G.getMetadata().MF;
692  LiveIntervals &LIS = G.getMetadata().LIS;
693  const TargetRegisterInfo &TRI = *MF.getSubtarget().getRegisterInfo();
694  (void)TRI;
695 
696  // Set to true if we have any spills
697  bool AnotherRoundNeeded = false;
698 
699  // Clear the existing allocation.
700  VRM.clearAllVirt();
701 
702  // Iterate over the nodes mapping the PBQP solution to a register
703  // assignment.
704  for (auto NId : G.nodeIds()) {
705  unsigned VReg = G.getNodeMetadata(NId).getVReg();
706  unsigned AllocOption = Solution.getSelection(NId);
707 
708  if (AllocOption != PBQP::RegAlloc::getSpillOptionIdx()) {
709  unsigned PReg = G.getNodeMetadata(NId).getAllowedRegs()[AllocOption - 1];
710  DEBUG(dbgs() << "VREG " << PrintReg(VReg, &TRI) << " -> "
711  << TRI.getName(PReg) << "\n");
712  assert(PReg != 0 && "Invalid preg selected.");
713  VRM.assignVirt2Phys(VReg, PReg);
714  } else {
715  // Spill VReg. If this introduces new intervals we'll need another round
716  // of allocation.
717  SmallVector<unsigned, 8> NewVRegs;
718  spillVReg(VReg, NewVRegs, MF, LIS, VRM, VRegSpiller);
719  AnotherRoundNeeded |= !NewVRegs.empty();
720  }
721  }
722 
723  return !AnotherRoundNeeded;
724 }
725 
726 void RegAllocPBQP::finalizeAlloc(MachineFunction &MF,
727  LiveIntervals &LIS,
728  VirtRegMap &VRM) const {
729  MachineRegisterInfo &MRI = MF.getRegInfo();
730 
731  // First allocate registers for the empty intervals.
732  for (RegSet::const_iterator
733  I = EmptyIntervalVRegs.begin(), E = EmptyIntervalVRegs.end();
734  I != E; ++I) {
735  LiveInterval &LI = LIS.getInterval(*I);
736 
737  unsigned PReg = MRI.getSimpleHint(LI.reg);
738 
739  if (PReg == 0) {
740  const TargetRegisterClass &RC = *MRI.getRegClass(LI.reg);
741  const ArrayRef<MCPhysReg> RawPRegOrder = RC.getRawAllocationOrder(MF);
742  for (unsigned CandidateReg : RawPRegOrder) {
743  if (!VRM.getRegInfo().isReserved(CandidateReg)) {
744  PReg = CandidateReg;
745  break;
746  }
747  }
748  assert(PReg &&
749  "No un-reserved physical registers in this register class");
750  }
751 
752  VRM.assignVirt2Phys(LI.reg, PReg);
753  }
754 }
755 
756 void RegAllocPBQP::postOptimization(Spiller &VRegSpiller, LiveIntervals &LIS) {
757  VRegSpiller.postOptimization();
758  /// Remove dead defs because of rematerialization.
759  for (auto DeadInst : DeadRemats) {
760  LIS.RemoveMachineInstrFromMaps(*DeadInst);
761  DeadInst->eraseFromParent();
762  }
763  DeadRemats.clear();
764 }
765 
766 static inline float normalizePBQPSpillWeight(float UseDefFreq, unsigned Size,
767  unsigned NumInstr) {
768  // All intervals have a spill weight that is mostly proportional to the number
769  // of uses, with uses in loops having a bigger weight.
770  return NumInstr * normalizeSpillWeight(UseDefFreq, Size, 1);
771 }
772 
773 bool RegAllocPBQP::runOnMachineFunction(MachineFunction &MF) {
774  LiveIntervals &LIS = getAnalysis<LiveIntervals>();
776  getAnalysis<MachineBlockFrequencyInfo>();
777 
778  VirtRegMap &VRM = getAnalysis<VirtRegMap>();
779 
780  calculateSpillWeightsAndHints(LIS, MF, &VRM, getAnalysis<MachineLoopInfo>(),
782 
783  std::unique_ptr<Spiller> VRegSpiller(createInlineSpiller(*this, MF, VRM));
784 
786 
787  DEBUG(dbgs() << "PBQP Register Allocating for " << MF.getName() << "\n");
788 
789  // Allocator main loop:
790  //
791  // * Map current regalloc problem to a PBQP problem
792  // * Solve the PBQP problem
793  // * Map the solution back to a register allocation
794  // * Spill if necessary
795  //
796  // This process is continued till no more spills are generated.
797 
798  // Find the vreg intervals in need of allocation.
799  findVRegIntervalsToAlloc(MF, LIS);
800 
801 #ifndef NDEBUG
802  const Function &F = *MF.getFunction();
803  std::string FullyQualifiedName =
804  F.getParent()->getModuleIdentifier() + "." + F.getName().str();
805 #endif
806 
807  // If there are non-empty intervals allocate them using pbqp.
808  if (!VRegsToAlloc.empty()) {
809  const TargetSubtargetInfo &Subtarget = MF.getSubtarget();
810  std::unique_ptr<PBQPRAConstraintList> ConstraintsRoot =
811  llvm::make_unique<PBQPRAConstraintList>();
812  ConstraintsRoot->addConstraint(llvm::make_unique<SpillCosts>());
813  ConstraintsRoot->addConstraint(llvm::make_unique<Interference>());
814  if (PBQPCoalescing)
815  ConstraintsRoot->addConstraint(llvm::make_unique<Coalescing>());
816  ConstraintsRoot->addConstraint(Subtarget.getCustomPBQPConstraints());
817 
818  bool PBQPAllocComplete = false;
819  unsigned Round = 0;
820 
821  while (!PBQPAllocComplete) {
822  DEBUG(dbgs() << " PBQP Regalloc round " << Round << ":\n");
823 
824  PBQPRAGraph G(PBQPRAGraph::GraphMetadata(MF, LIS, MBFI));
825  initializeGraph(G, VRM, *VRegSpiller);
826  ConstraintsRoot->apply(G);
827 
828 #ifndef NDEBUG
829  if (PBQPDumpGraphs) {
830  std::ostringstream RS;
831  RS << Round;
832  std::string GraphFileName = FullyQualifiedName + "." + RS.str() +
833  ".pbqpgraph";
834  std::error_code EC;
835  raw_fd_ostream OS(GraphFileName, EC, sys::fs::F_Text);
836  DEBUG(dbgs() << "Dumping graph for round " << Round << " to \""
837  << GraphFileName << "\"\n");
838  G.dump(OS);
839  }
840 #endif
841 
843  PBQPAllocComplete = mapPBQPToRegAlloc(G, Solution, VRM, *VRegSpiller);
844  ++Round;
845  }
846  }
847 
848  // Finalise allocation, allocate empty ranges.
849  finalizeAlloc(MF, LIS, VRM);
850  postOptimization(*VRegSpiller, LIS);
851  VRegsToAlloc.clear();
852  EmptyIntervalVRegs.clear();
853 
854  DEBUG(dbgs() << "Post alloc VirtRegMap:\n" << VRM << "\n");
855 
856  return true;
857 }
858 
859 /// Create Printable object for node and register info.
861  const PBQP::RegAlloc::PBQPRAGraph &G) {
862  return Printable([NId, &G](raw_ostream &OS) {
863  const MachineRegisterInfo &MRI = G.getMetadata().MF.getRegInfo();
864  const TargetRegisterInfo *TRI = MRI.getTargetRegisterInfo();
865  unsigned VReg = G.getNodeMetadata(NId).getVReg();
866  const char *RegClassName = TRI->getRegClassName(MRI.getRegClass(VReg));
867  OS << NId << " (" << RegClassName << ':' << PrintReg(VReg, TRI) << ')';
868  });
869 }
870 
871 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
873  for (auto NId : nodeIds()) {
874  const Vector &Costs = getNodeCosts(NId);
875  assert(Costs.getLength() != 0 && "Empty vector in graph.");
876  OS << PrintNodeInfo(NId, *this) << ": " << Costs << '\n';
877  }
878  OS << '\n';
879 
880  for (auto EId : edgeIds()) {
881  NodeId N1Id = getEdgeNode1Id(EId);
882  NodeId N2Id = getEdgeNode2Id(EId);
883  assert(N1Id != N2Id && "PBQP graphs should not have self-edges.");
884  const Matrix &M = getEdgeCosts(EId);
885  assert(M.getRows() != 0 && "No rows in matrix.");
886  assert(M.getCols() != 0 && "No cols in matrix.");
887  OS << PrintNodeInfo(N1Id, *this) << ' ' << M.getRows() << " rows / ";
888  OS << PrintNodeInfo(N2Id, *this) << ' ' << M.getCols() << " cols:\n";
889  OS << M << '\n';
890  }
891 }
892 
894  dump(dbgs());
895 }
896 #endif
897 
899  OS << "graph {\n";
900  for (auto NId : nodeIds()) {
901  OS << " node" << NId << " [ label=\""
902  << PrintNodeInfo(NId, *this) << "\\n"
903  << getNodeCosts(NId) << "\" ]\n";
904  }
905 
906  OS << " edge [ len=" << nodeIds().size() << " ]\n";
907  for (auto EId : edgeIds()) {
908  OS << " node" << getEdgeNode1Id(EId)
909  << " -- node" << getEdgeNode2Id(EId)
910  << " [ label=\"";
911  const Matrix &EdgeCosts = getEdgeCosts(EId);
912  for (unsigned i = 0; i < EdgeCosts.getRows(); ++i) {
913  OS << EdgeCosts.getRowAsVector(i) << "\\n";
914  }
915  OS << "\" ]\n";
916  }
917  OS << "}\n";
918 }
919 
921  return new RegAllocPBQP(customPassID);
922 }
923 
926 }
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)
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
Printable PrintReg(unsigned Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubRegIdx=0)
Prints virtual and physical registers with or without a TRI instance.
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)
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:923
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:769
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:220
#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
const Function * getFunction() const
getFunction - Return the LLVM function that this machine code represents
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:556
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 - Return the preferred register allocation hint, or 0 if a standard simple hint (Type =...
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.