LLVM  10.0.0svn
RegAllocPBQP.cpp
Go to the documentation of this file.
1 //===- RegAllocPBQP.cpp ---- PBQP Register Allocator ----------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file contains a Partitioned Boolean Quadratic Programming (PBQP) based
10 // register allocator for LLVM. This allocator works by constructing a PBQP
11 // problem representing the register allocation problem under consideration,
12 // solving this using a PBQP solver, and mapping the solution back to a
13 // register assignment. If any variables are selected for spilling then spill
14 // code is inserted and the process repeated.
15 //
16 // The PBQP solver (pbqp.c) provided for this allocator uses a heuristic tuned
17 // for register allocation. For more information on PBQP for register
18 // allocation, see the following papers:
19 //
20 // (1) Hames, L. and Scholz, B. 2006. Nearly optimal register allocation with
21 // PBQP. In Proceedings of the 7th Joint Modular Languages Conference
22 // (JMLC'06). LNCS, vol. 4228. Springer, New York, NY, USA. 346-361.
23 //
24 // (2) Scholz, B., Eckstein, E. 2002. Register allocation for irregular
25 // architectures. In Proceedings of the Joint Conference on Languages,
26 // Compilers and Tools for Embedded Systems (LCTES'02), ACM Press, New York,
27 // NY, USA, 139-148.
28 //
29 //===----------------------------------------------------------------------===//
30 
32 #include "RegisterCoalescer.h"
33 #include "Spiller.h"
34 #include "llvm/ADT/ArrayRef.h"
35 #include "llvm/ADT/BitVector.h"
36 #include "llvm/ADT/DenseMap.h"
37 #include "llvm/ADT/DenseSet.h"
38 #include "llvm/ADT/STLExtras.h"
39 #include "llvm/ADT/SmallPtrSet.h"
40 #include "llvm/ADT/SmallVector.h"
41 #include "llvm/ADT/StringRef.h"
56 #include "llvm/CodeGen/PBQP/Math.h"
64 #include "llvm/Config/llvm-config.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  /// Finds the initial set of vreg intervals to allocate.
163  void findVRegIntervalsToAlloc(const MachineFunction &MF, LiveIntervals &LIS);
164 
165  /// Constructs an initial graph.
166  void initializeGraph(PBQPRAGraph &G, VirtRegMap &VRM, Spiller &VRegSpiller);
167 
168  /// Spill the given VReg.
169  void spillVReg(unsigned VReg, SmallVectorImpl<unsigned> &NewIntervals,
170  MachineFunction &MF, LiveIntervals &LIS, VirtRegMap &VRM,
171  Spiller &VRegSpiller);
172 
173  /// 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  /// 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 /// 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 /// 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) {
561  unsigned Reg = Register::index2VirtReg(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  LLVM_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  LLVM_DEBUG(dbgs() << printReg(LI.reg, &TRI) << " ");
697  VRegsToAlloc.insert(LI.reg);
698  }
699 
700  LLVM_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  LLVM_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  LLVM_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  std::make_unique<PBQPRAConstraintList>();
828  ConstraintsRoot->addConstraint(std::make_unique<SpillCosts>());
829  ConstraintsRoot->addConstraint(std::make_unique<Interference>());
830  if (PBQPCoalescing)
831  ConstraintsRoot->addConstraint(std::make_unique<Coalescing>());
832  ConstraintsRoot->addConstraint(Subtarget.getCustomPBQPConstraints());
833 
834  bool PBQPAllocComplete = false;
835  unsigned Round = 0;
836 
837  while (!PBQPAllocComplete) {
838  LLVM_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::OF_Text);
852  LLVM_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  LLVM_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 }
uint64_t CallInst * C
bool empty() const
Definition: LiveInterval.h:373
Represents a solution to a PBQP problem.
Definition: Solution.h:26
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:708
LLVM_NODISCARD std::string str() const
str - Get the contents as an std::string.
Definition: StringRef.h:232
bool isReserved(Register PhysReg) const
isReserved - Returns true when PhysReg is a reserved register.
void RemoveMachineInstrFromMaps(MachineInstr &MI)
This class represents lattice values for constants.
Definition: AllocatorList.h:23
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds...
Definition: Compiler.h:476
bool empty() const
empty - Tests whether there are no bits in this bitvector.
Definition: BitVector.h:166
EdgeId addEdge(NodeId N1Id, NodeId N2Id, OtherVectorT Costs)
Add an edge between the given nodes with the given costs.
Definition: Graph.h:409
Holds a vector of the allowed physical regs for a vreg.
Definition: RegAllocPBQP.h:92
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:249
EdgeId findEdge(NodeId N1Id, NodeId N2Id)
Get the edge connecting two nodes.
Definition: Graph.h:573
LiveInterval - This class represents the liveness of a register, or stack slot.
Definition: LiveInterval.h:679
virtual ~PBQPRAConstraint()=0
unsigned Reg
bool test(unsigned Idx) const
Definition: BitVector.h:501
Spiller interface.
Definition: Spiller.h:23
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:508
unsigned const TargetRegisterInfo * TRI
F(f)
NodeId addEdgeBypassingCostAllocator(NodeId N1Id, NodeId N2Id, OtherMatrixPtrT Costs)
Add an edge bypassing the cost allocator.
Definition: Graph.h:434
Printable printReg(Register Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)
Prints virtual and physical registers with or without a TRI instance.
static unsigned index2VirtReg(unsigned Index)
Convert a 0-based index to a virtual register number.
Definition: Register.h:83
NodeId getEdgeNode1Id(EdgeId EId) const
Get the first node connected to this edge.
Definition: Graph.h:545
bool checkRegMaskInterference(LiveInterval &LI, BitVector &UsableRegs)
Test if LI is live across any register mask instructions, and compute a bit mask of physical register...
const TargetRegisterClass * getRegClass(Register Reg) const
Return the register class of the specified virtual 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:492
AnalysisUsage & addRequired()
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
typename RegAllocSolverImpl ::GraphMetadata GraphMetadata
Definition: Graph.h:59
A helper class for register coalescers.
void apply(Opt *O, const Mod &M, const Mods &... Ms)
Definition: CommandLine.h:1217
void freezeReservedRegs(const MachineFunction &)
freezeReservedRegs - Called by the register allocator to freeze the set of reserved registers before ...
float PBQPNum
Definition: Math.h:22
static cl::opt< bool > PBQPCoalescing("pbqp-coalescing", cl::desc("Attempt coalescing during PBQP register allocation."), cl::init(false), cl::Hidden)
bool regsOverlap(Register regA, Register regB) const
Returns true if the two registers are equal or alias each other.
NodeIdSet nodeIds() const
Definition: Graph.h:449
SlotIndexes pass.
Definition: SlotIndexes.h:314
typename RegAllocSolverImpl ::Matrix Matrix
Definition: Graph.h:54
The file should be opened in text mode on platforms that make this distinction.
Definition: FileSystem.h:767
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:530
uint16_t MCPhysReg
An unsigned integer type large enough to represent all physical registers, but not necessarily virtua...
Definition: MCRegister.h:19
unsigned NodeId
Definition: Graph.h:28
const MatrixPtr & getEdgeCostsPtr(EdgeId EId) const
Get a MatrixPtr to a node&#39;s cost matrix.
Definition: Graph.h:523
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
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:488
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:148
MachineRegisterInfo & getRegInfo() const
Definition: VirtRegMap.h:89
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
BlockFrequency getBlockFreq(const MachineBasicBlock *MBB) const
getblockFreq - Return block frequency.
Represent the analysis usage information of a pass.
void initializeLiveIntervalsPass(PassRegistry &)
void assignVirt2Phys(Register virtReg, MCPhysReg physReg)
creates a mapping for the specified virtual register to the specified physical register ...
Definition: VirtRegMap.cpp:83
FunctionPass * createDefaultPBQPRegisterAllocator()
PBQPRegisterAllocation Pass - This pass implements the Partitioned Boolean Quadratic Prograaming (PBQ...
bool reg_nodbg_empty(Register RegNo) const
reg_nodbg_empty - Return true if the only instructions using or defining Reg are Debug instructions...
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:284
static bool isACalleeSavedRegister(unsigned reg, const TargetRegisterInfo &TRI, const MachineFunction &MF)
LiveInterval & getInterval(Register Reg)
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:210
GraphMetadata & getMetadata()
Get a reference to the graph metadata.
Definition: Graph.h:347
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:417
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.
AnalysisUsage & addRequiredID(const void *ID)
Definition: Pass.cpp:314
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:202
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:301
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:940
void dump() const
Dump this graph to dbgs().
bool isValid() const
isValid - returns true if this iterator is not yet at the end.
const char * getName(MCRegister RegNo) const
Return the human-readable symbolic target-specific name for the specified physical register...
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:51
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:37
A raw_ostream that writes to a file descriptor.
Definition: raw_ostream.h:384
bool overlaps(const LiveRange &other) const
overlaps - Return true if the intersection of the two live ranges is not empty.
Definition: LiveInterval.h:439
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:55
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:214
#define I(x, y, z)
Definition: MD5.cpp:58
unsigned getSelection(GraphBase::NodeId nodeId) const
Get a node&#39;s selection.
Definition: Solution.h:45
Solution solve(PBQPRAGraph &G)
Definition: RegAllocPBQP.h:519
uint32_t Size
Definition: Profile.cpp:46
virtual void postOptimization()
Definition: Spiller.h:32
unsigned getSpillOptionIdx()
Spill option index.
Definition: RegAllocPBQP.h:46
typename RegAllocSolverImpl ::Vector Vector
Definition: Graph.h:53
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:121
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:575
typename RegAllocSolverImpl ::RawMatrix RawMatrix
Definition: Graph.h:52
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:45
IRTranslator LLVM IR MI
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:48
NodeId addNode(OtherVectorT Costs)
Add a node with the given costs.
Definition: Graph.h:375
Simple wrapper around std::function<void(raw_ostream&)>.
Definition: Printable.h:37
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object...
#define LLVM_DEBUG(X)
Definition: Debug.h:122
Register getSimpleHint(Register 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:83
void setNodeCosts(NodeId NId, OtherVectorT Costs)
Set a node&#39;s cost vector.
Definition: Graph.h:466
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.