LLVM  14.0.0git
RegAllocPBQP.h
Go to the documentation of this file.
1 //===- RegAllocPBQP.h -------------------------------------------*- C++ -*-===//
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 defines the PBQPBuilder interface, for classes which build PBQP
10 // instances to represent register allocation problems, and the RegAllocPBQP
11 // interface.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #ifndef LLVM_CODEGEN_REGALLOCPBQP_H
16 #define LLVM_CODEGEN_REGALLOCPBQP_H
17 
18 #include "llvm/ADT/DenseMap.h"
19 #include "llvm/ADT/Hashing.h"
22 #include "llvm/CodeGen/PBQP/Math.h"
25 #include "llvm/CodeGen/Register.h"
26 #include "llvm/MC/MCRegister.h"
28 #include <algorithm>
29 #include <cassert>
30 #include <cstddef>
31 #include <limits>
32 #include <memory>
33 #include <set>
34 #include <vector>
35 
36 namespace llvm {
37 
38 class FunctionPass;
39 class LiveIntervals;
40 class MachineBlockFrequencyInfo;
41 class MachineFunction;
42 class raw_ostream;
43 
44 namespace PBQP {
45 namespace RegAlloc {
46 
47 /// Spill option index.
48 inline unsigned getSpillOptionIdx() { return 0; }
49 
50 /// Metadata to speed allocatability test.
51 ///
52 /// Keeps track of the number of infinities in each row and column.
54 public:
56  : UnsafeRows(new bool[M.getRows() - 1]()),
57  UnsafeCols(new bool[M.getCols() - 1]()) {
58  unsigned* ColCounts = new unsigned[M.getCols() - 1]();
59 
60  for (unsigned i = 1; i < M.getRows(); ++i) {
61  unsigned RowCount = 0;
62  for (unsigned j = 1; j < M.getCols(); ++j) {
63  if (M[i][j] == std::numeric_limits<PBQPNum>::infinity()) {
64  ++RowCount;
65  ++ColCounts[j - 1];
66  UnsafeRows[i - 1] = true;
67  UnsafeCols[j - 1] = true;
68  }
69  }
70  WorstRow = std::max(WorstRow, RowCount);
71  }
72  unsigned WorstColCountForCurRow =
73  *std::max_element(ColCounts, ColCounts + M.getCols() - 1);
74  WorstCol = std::max(WorstCol, WorstColCountForCurRow);
75  delete[] ColCounts;
76  }
77 
78  MatrixMetadata(const MatrixMetadata &) = delete;
79  MatrixMetadata &operator=(const MatrixMetadata &) = delete;
80 
81  unsigned getWorstRow() const { return WorstRow; }
82  unsigned getWorstCol() const { return WorstCol; }
83  const bool* getUnsafeRows() const { return UnsafeRows.get(); }
84  const bool* getUnsafeCols() const { return UnsafeCols.get(); }
85 
86 private:
87  unsigned WorstRow = 0;
88  unsigned WorstCol = 0;
89  std::unique_ptr<bool[]> UnsafeRows;
90  std::unique_ptr<bool[]> UnsafeCols;
91 };
92 
93 /// Holds a vector of the allowed physical regs for a vreg.
95  friend hash_code hash_value(const AllowedRegVector &);
96 
97 public:
98  AllowedRegVector() = default;
99  AllowedRegVector(AllowedRegVector &&) = default;
100 
101  AllowedRegVector(const std::vector<MCRegister> &OptVec)
102  : NumOpts(OptVec.size()), Opts(new MCRegister[NumOpts]) {
103  std::copy(OptVec.begin(), OptVec.end(), Opts.get());
104  }
105 
106  unsigned size() const { return NumOpts; }
107  MCRegister operator[](size_t I) const { return Opts[I]; }
108 
109  bool operator==(const AllowedRegVector &Other) const {
110  if (NumOpts != Other.NumOpts)
111  return false;
112  return std::equal(Opts.get(), Opts.get() + NumOpts, Other.Opts.get());
113  }
114 
115  bool operator!=(const AllowedRegVector &Other) const {
116  return !(*this == Other);
117  }
118 
119 private:
120  unsigned NumOpts = 0;
121  std::unique_ptr<MCRegister[]> Opts;
122 };
123 
124 inline hash_code hash_value(const AllowedRegVector &OptRegs) {
125  MCRegister *OStart = OptRegs.Opts.get();
126  MCRegister *OEnd = OptRegs.Opts.get() + OptRegs.NumOpts;
127  return hash_combine(OptRegs.NumOpts,
128  hash_combine_range(OStart, OEnd));
129 }
130 
131 /// Holds graph-level metadata relevant to PBQP RA problems.
133 private:
135 
136 public:
138 
142  : MF(MF), LIS(LIS), MBFI(MBFI) {}
143 
147 
149  VRegToNodeId[VReg.id()] = NId;
150  }
151 
153  auto VRegItr = VRegToNodeId.find(VReg);
154  if (VRegItr == VRegToNodeId.end())
155  return GraphBase::invalidNodeId();
156  return VRegItr->second;
157  }
158 
160  return AllowedRegVecs.getValue(std::move(Allowed));
161  }
162 
163 private:
165  AllowedRegVecPool AllowedRegVecs;
166 };
167 
168 /// Holds solver state and other metadata relevant to each PBQP RA node.
170 public:
172 
173  // The node's reduction state. The order in this enum is important,
174  // as it is assumed nodes can only progress up (i.e. towards being
175  // optimally reducible) when reducing the graph.
176  using ReductionState = enum {
177  Unprocessed,
178  NotProvablyAllocatable,
179  ConservativelyAllocatable,
180  OptimallyReducible
181  };
182 
183  NodeMetadata() = default;
184 
186  : RS(Other.RS), NumOpts(Other.NumOpts), DeniedOpts(Other.DeniedOpts),
187  OptUnsafeEdges(new unsigned[NumOpts]), VReg(Other.VReg),
188  AllowedRegs(Other.AllowedRegs)
189 #ifndef NDEBUG
190  , everConservativelyAllocatable(Other.everConservativelyAllocatable)
191 #endif
192  {
193  if (NumOpts > 0) {
194  std::copy(&Other.OptUnsafeEdges[0], &Other.OptUnsafeEdges[NumOpts],
195  &OptUnsafeEdges[0]);
196  }
197  }
198 
199  NodeMetadata(NodeMetadata &&) = default;
200  NodeMetadata& operator=(NodeMetadata &&) = default;
201 
202  void setVReg(Register VReg) { this->VReg = VReg; }
203  Register getVReg() const { return VReg; }
204 
206  this->AllowedRegs = std::move(AllowedRegs);
207  }
208  const AllowedRegVector& getAllowedRegs() const { return *AllowedRegs; }
209 
210  void setup(const Vector& Costs) {
211  NumOpts = Costs.getLength() - 1;
212  OptUnsafeEdges = std::unique_ptr<unsigned[]>(new unsigned[NumOpts]());
213  }
214 
215  ReductionState getReductionState() const { return RS; }
217  assert(RS >= this->RS && "A node's reduction state can not be downgraded");
218  this->RS = RS;
219 
220 #ifndef NDEBUG
221  // Remember this state to assert later that a non-infinite register
222  // option was available.
223  if (RS == ConservativelyAllocatable)
224  everConservativelyAllocatable = true;
225 #endif
226  }
227 
228  void handleAddEdge(const MatrixMetadata& MD, bool Transpose) {
229  DeniedOpts += Transpose ? MD.getWorstRow() : MD.getWorstCol();
230  const bool* UnsafeOpts =
231  Transpose ? MD.getUnsafeCols() : MD.getUnsafeRows();
232  for (unsigned i = 0; i < NumOpts; ++i)
233  OptUnsafeEdges[i] += UnsafeOpts[i];
234  }
235 
236  void handleRemoveEdge(const MatrixMetadata& MD, bool Transpose) {
237  DeniedOpts -= Transpose ? MD.getWorstRow() : MD.getWorstCol();
238  const bool* UnsafeOpts =
239  Transpose ? MD.getUnsafeCols() : MD.getUnsafeRows();
240  for (unsigned i = 0; i < NumOpts; ++i)
241  OptUnsafeEdges[i] -= UnsafeOpts[i];
242  }
243 
245  return (DeniedOpts < NumOpts) ||
246  (std::find(&OptUnsafeEdges[0], &OptUnsafeEdges[NumOpts], 0) !=
247  &OptUnsafeEdges[NumOpts]);
248  }
249 
250 #ifndef NDEBUG
252  return everConservativelyAllocatable;
253  }
254 #endif
255 
256 private:
257  ReductionState RS = Unprocessed;
258  unsigned NumOpts = 0;
259  unsigned DeniedOpts = 0;
260  std::unique_ptr<unsigned[]> OptUnsafeEdges;
261  Register VReg;
263 
264 #ifndef NDEBUG
265  bool everConservativelyAllocatable = false;
266 #endif
267 };
268 
270 private:
272 
273 public:
277  using Matrix = RAMatrix;
279 
282 
284  struct EdgeMetadata {};
286 
288 
290 
292  G.setSolver(*this);
293  Solution S;
294  setup();
295  S = backpropagate(G, reduce());
296  G.unsetSolver();
297  return S;
298  }
299 
300  void handleAddNode(NodeId NId) {
301  assert(G.getNodeCosts(NId).getLength() > 1 &&
302  "PBQP Graph should not contain single or zero-option nodes");
303  G.getNodeMetadata(NId).setup(G.getNodeCosts(NId));
304  }
305 
307  void handleSetNodeCosts(NodeId NId, const Vector& newCosts) {}
308 
309  void handleAddEdge(EdgeId EId) {
310  handleReconnectEdge(EId, G.getEdgeNode1Id(EId));
311  handleReconnectEdge(EId, G.getEdgeNode2Id(EId));
312  }
313 
315  NodeMetadata& NMd = G.getNodeMetadata(NId);
316  const MatrixMetadata& MMd = G.getEdgeCosts(EId).getMetadata();
317  NMd.handleRemoveEdge(MMd, NId == G.getEdgeNode2Id(EId));
318  promote(NId, NMd);
319  }
320 
322  NodeMetadata& NMd = G.getNodeMetadata(NId);
323  const MatrixMetadata& MMd = G.getEdgeCosts(EId).getMetadata();
324  NMd.handleAddEdge(MMd, NId == G.getEdgeNode2Id(EId));
325  }
326 
327  void handleUpdateCosts(EdgeId EId, const Matrix& NewCosts) {
328  NodeId N1Id = G.getEdgeNode1Id(EId);
329  NodeId N2Id = G.getEdgeNode2Id(EId);
330  NodeMetadata& N1Md = G.getNodeMetadata(N1Id);
331  NodeMetadata& N2Md = G.getNodeMetadata(N2Id);
332  bool Transpose = N1Id != G.getEdgeNode1Id(EId);
333 
334  // Metadata are computed incrementally. First, update them
335  // by removing the old cost.
336  const MatrixMetadata& OldMMd = G.getEdgeCosts(EId).getMetadata();
337  N1Md.handleRemoveEdge(OldMMd, Transpose);
338  N2Md.handleRemoveEdge(OldMMd, !Transpose);
339 
340  // And update now the metadata with the new cost.
341  const MatrixMetadata& MMd = NewCosts.getMetadata();
342  N1Md.handleAddEdge(MMd, Transpose);
343  N2Md.handleAddEdge(MMd, !Transpose);
344 
345  // As the metadata may have changed with the update, the nodes may have
346  // become ConservativelyAllocatable or OptimallyReducible.
347  promote(N1Id, N1Md);
348  promote(N2Id, N2Md);
349  }
350 
351 private:
352  void promote(NodeId NId, NodeMetadata& NMd) {
353  if (G.getNodeDegree(NId) == 3) {
354  // This node is becoming optimally reducible.
355  moveToOptimallyReducibleNodes(NId);
356  } else if (NMd.getReductionState() ==
357  NodeMetadata::NotProvablyAllocatable &&
359  // This node just became conservatively allocatable.
360  moveToConservativelyAllocatableNodes(NId);
361  }
362  }
363 
364  void removeFromCurrentSet(NodeId NId) {
365  switch (G.getNodeMetadata(NId).getReductionState()) {
366  case NodeMetadata::Unprocessed: break;
367  case NodeMetadata::OptimallyReducible:
368  assert(OptimallyReducibleNodes.find(NId) !=
369  OptimallyReducibleNodes.end() &&
370  "Node not in optimally reducible set.");
371  OptimallyReducibleNodes.erase(NId);
372  break;
373  case NodeMetadata::ConservativelyAllocatable:
374  assert(ConservativelyAllocatableNodes.find(NId) !=
375  ConservativelyAllocatableNodes.end() &&
376  "Node not in conservatively allocatable set.");
377  ConservativelyAllocatableNodes.erase(NId);
378  break;
379  case NodeMetadata::NotProvablyAllocatable:
380  assert(NotProvablyAllocatableNodes.find(NId) !=
381  NotProvablyAllocatableNodes.end() &&
382  "Node not in not-provably-allocatable set.");
383  NotProvablyAllocatableNodes.erase(NId);
384  break;
385  }
386  }
387 
388  void moveToOptimallyReducibleNodes(NodeId NId) {
389  removeFromCurrentSet(NId);
390  OptimallyReducibleNodes.insert(NId);
392  NodeMetadata::OptimallyReducible);
393  }
394 
395  void moveToConservativelyAllocatableNodes(NodeId NId) {
396  removeFromCurrentSet(NId);
397  ConservativelyAllocatableNodes.insert(NId);
399  NodeMetadata::ConservativelyAllocatable);
400  }
401 
402  void moveToNotProvablyAllocatableNodes(NodeId NId) {
403  removeFromCurrentSet(NId);
404  NotProvablyAllocatableNodes.insert(NId);
406  NodeMetadata::NotProvablyAllocatable);
407  }
408 
409  void setup() {
410  // Set up worklists.
411  for (auto NId : G.nodeIds()) {
412  if (G.getNodeDegree(NId) < 3)
413  moveToOptimallyReducibleNodes(NId);
415  moveToConservativelyAllocatableNodes(NId);
416  else
417  moveToNotProvablyAllocatableNodes(NId);
418  }
419  }
420 
421  // Compute a reduction order for the graph by iteratively applying PBQP
422  // reduction rules. Locally optimal rules are applied whenever possible (R0,
423  // R1, R2). If no locally-optimal rules apply then any conservatively
424  // allocatable node is reduced. Finally, if no conservatively allocatable
425  // node exists then the node with the lowest spill-cost:degree ratio is
426  // selected.
427  std::vector<GraphBase::NodeId> reduce() {
428  assert(!G.empty() && "Cannot reduce empty graph.");
429 
430  using NodeId = GraphBase::NodeId;
431  std::vector<NodeId> NodeStack;
432 
433  // Consume worklists.
434  while (true) {
435  if (!OptimallyReducibleNodes.empty()) {
436  NodeSet::iterator NItr = OptimallyReducibleNodes.begin();
437  NodeId NId = *NItr;
438  OptimallyReducibleNodes.erase(NItr);
439  NodeStack.push_back(NId);
440  switch (G.getNodeDegree(NId)) {
441  case 0:
442  break;
443  case 1:
444  applyR1(G, NId);
445  break;
446  case 2:
447  applyR2(G, NId);
448  break;
449  default: llvm_unreachable("Not an optimally reducible node.");
450  }
451  } else if (!ConservativelyAllocatableNodes.empty()) {
452  // Conservatively allocatable nodes will never spill. For now just
453  // take the first node in the set and push it on the stack. When we
454  // start optimizing more heavily for register preferencing, it may
455  // would be better to push nodes with lower 'expected' or worst-case
456  // register costs first (since early nodes are the most
457  // constrained).
458  NodeSet::iterator NItr = ConservativelyAllocatableNodes.begin();
459  NodeId NId = *NItr;
460  ConservativelyAllocatableNodes.erase(NItr);
461  NodeStack.push_back(NId);
463  } else if (!NotProvablyAllocatableNodes.empty()) {
464  NodeSet::iterator NItr =
465  std::min_element(NotProvablyAllocatableNodes.begin(),
466  NotProvablyAllocatableNodes.end(),
467  SpillCostComparator(G));
468  NodeId NId = *NItr;
469  NotProvablyAllocatableNodes.erase(NItr);
470  NodeStack.push_back(NId);
472  } else
473  break;
474  }
475 
476  return NodeStack;
477  }
478 
479  class SpillCostComparator {
480  public:
481  SpillCostComparator(const Graph& G) : G(G) {}
482 
483  bool operator()(NodeId N1Id, NodeId N2Id) {
484  PBQPNum N1SC = G.getNodeCosts(N1Id)[0];
485  PBQPNum N2SC = G.getNodeCosts(N2Id)[0];
486  if (N1SC == N2SC)
487  return G.getNodeDegree(N1Id) < G.getNodeDegree(N2Id);
488  return N1SC < N2SC;
489  }
490 
491  private:
492  const Graph& G;
493  };
494 
495  Graph& G;
496  using NodeSet = std::set<NodeId>;
497  NodeSet OptimallyReducibleNodes;
498  NodeSet ConservativelyAllocatableNodes;
499  NodeSet NotProvablyAllocatableNodes;
500 };
501 
502 class PBQPRAGraph : public PBQP::Graph<RegAllocSolverImpl> {
503 private:
505 
506 public:
508 
509  /// Dump this graph to dbgs().
510  void dump() const;
511 
512  /// Dump this graph to an output stream.
513  /// @param OS Output stream to print on.
514  void dump(raw_ostream &OS) const;
515 
516  /// Print a representation of this graph in DOT format.
517  /// @param OS Output stream to print on.
518  void printDot(raw_ostream &OS) const;
519 };
520 
522  if (G.empty())
523  return Solution();
524  RegAllocSolverImpl RegAllocSolver(G);
525  return RegAllocSolver.solve();
526 }
527 
528 } // end namespace RegAlloc
529 } // end namespace PBQP
530 
531 /// Create a PBQP register allocator instance.
532 FunctionPass *
533 createPBQPRegisterAllocator(char *customPassID = nullptr);
534 
535 } // end namespace llvm
536 
537 #endif // LLVM_CODEGEN_REGALLOCPBQP_H
i
i
Definition: README.txt:29
llvm::PBQP::RegAlloc::NodeMetadata::getAllowedRegs
const AllowedRegVector & getAllowedRegs() const
Definition: RegAllocPBQP.h:208
llvm::PBQP::RegAlloc::PBQPRAGraph::dump
void dump() const
Dump this graph to dbgs().
Definition: RegAllocPBQP.cpp:920
llvm::PBQP::RegAlloc::MatrixMetadata::MatrixMetadata
MatrixMetadata(const Matrix &M)
Definition: RegAllocPBQP.h:55
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::RegAllocType::PBQP
@ PBQP
llvm::PBQP::RegAlloc::NodeMetadata::setReductionState
void setReductionState(ReductionState RS)
Definition: RegAllocPBQP.h:216
llvm::PBQP::RegAlloc::AllowedRegVector::operator==
bool operator==(const AllowedRegVector &Other) const
Definition: RegAllocPBQP.h:109
M
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
Definition: README.txt:252
llvm::PBQP::RegAlloc::MatrixMetadata
Metadata to speed allocatability test.
Definition: RegAllocPBQP.h:53
llvm::PBQP::RegAlloc::MatrixMetadata::getUnsafeCols
const bool * getUnsafeCols() const
Definition: RegAllocPBQP.h:84
llvm::PBQP::Graph::getEdgeNode1Id
NodeId getEdgeNode1Id(EdgeId EId) const
Get the first node connected to this edge.
Definition: Graph.h:545
llvm::PBQP::RegAlloc::NodeMetadata::operator=
NodeMetadata & operator=(NodeMetadata &&)=default
llvm::PBQP::RegAlloc::GraphMetadata
Holds graph-level metadata relevant to PBQP RA problems.
Definition: RegAllocPBQP.h:132
llvm::createPBQPRegisterAllocator
FunctionPass * createPBQPRegisterAllocator(char *customPassID=nullptr)
Create a PBQP register allocator instance.
Definition: RegAllocPBQP.cpp:947
llvm::PBQP::RegAlloc::RegAllocSolverImpl::handleAddEdge
void handleAddEdge(EdgeId EId)
Definition: RegAllocPBQP.h:309
llvm::Register::id
unsigned id() const
Definition: Register.h:111
llvm::PBQP::RegAlloc::NodeMetadata::setup
void setup(const Vector &Costs)
Definition: RegAllocPBQP.h:210
llvm::PBQP::GraphBase::invalidNodeId
static NodeId invalidNodeId()
Returns a value representing an invalid (non-existent) node.
Definition: Graph.h:32
llvm::PBQP::RegAlloc::RegAllocSolverImpl
Definition: RegAllocPBQP.h:269
llvm::NodeSet::iterator
SetVector< SUnit * >::const_iterator iterator
Definition: MachinePipeliner.h:322
ErrorHandling.h
llvm::PBQP::RegAlloc::NodeMetadata::handleAddEdge
void handleAddEdge(const MatrixMetadata &MD, bool Transpose)
Definition: RegAllocPBQP.h:228
llvm::PBQP::GraphBase::EdgeId
unsigned EdgeId
Definition: Graph.h:29
llvm::PBQP::Graph::getEdgeNode2Id
NodeId getEdgeNode2Id(EdgeId EId) const
Get the second node connected to this edge.
Definition: Graph.h:552
DenseMap.h
llvm::PBQP::RegAlloc::GraphMetadata::MF
MachineFunction & MF
Definition: RegAllocPBQP.h:144
llvm::PBQP::RegAlloc::PBQPRAGraph::PBQPRAGraph
PBQPRAGraph(GraphMetadata Metadata)
Definition: RegAllocPBQP.h:507
llvm::PBQP::Graph< RegAllocSolverImpl >::GraphMetadata
typename RegAllocSolverImpl ::GraphMetadata GraphMetadata
Definition: Graph.h:59
Hashing.h
llvm::PBQP::PBQPNum
float PBQPNum
Definition: Math.h:22
endif
__FakeVCSRevision h endif() endif() set(generated_files "$
Definition: CMakeLists.txt:16
llvm::PBQP::RegAlloc::RegAllocSolverImpl::handleRemoveNode
void handleRemoveNode(NodeId NId)
Definition: RegAllocPBQP.h:306
new
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM ID Predecessors according to mbb< bb27, 0x8b0a7c0 > Note ADDri is not a two address instruction its result reg1037 is an operand of the PHI node in bb76 and its operand reg1039 is the result of the PHI node We should treat it as a two address code and make sure the ADDri is scheduled after any node that reads reg1039 Use info(i.e. register scavenger) to assign it a free register to allow reuse the collector could move the objects and invalidate the derived pointer This is bad enough in the first but safe points can crop up unpredictably **array_addr i32 n y store obj * new
Definition: README.txt:125
CostAllocator.h
llvm::lltok::equal
@ equal
Definition: LLToken.h:25
llvm::PBQP::RegAlloc::RegAllocSolverImpl::EdgeId
GraphBase::EdgeId EdgeId
Definition: RegAllocPBQP.h:281
llvm::PBQP::RegAlloc::AllowedRegVector::size
unsigned size() const
Definition: RegAllocPBQP.h:106
llvm::PBQP::RegAlloc::NodeMetadata::NodeMetadata
NodeMetadata()=default
llvm::MachineBlockFrequencyInfo
MachineBlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate machine basic b...
Definition: MachineBlockFrequencyInfo.h:33
llvm::PBQP::RegAlloc::RegAllocSolverImpl::handleAddNode
void handleAddNode(NodeId NId)
Definition: RegAllocPBQP.h:300
llvm::PBQP::Graph::getNodeCosts
const Vector & getNodeCosts(NodeId NId) const
Get a node's cost vector.
Definition: Graph.h:488
llvm::PBQP::RegAlloc::GraphMetadata::GraphMetadata
GraphMetadata(MachineFunction &MF, LiveIntervals &LIS, MachineBlockFrequencyInfo &MBFI)
Definition: RegAllocPBQP.h:139
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:53
llvm::PBQP::RegAlloc::PBQPRAGraph::printDot
void printDot(raw_ostream &OS) const
Print a representation of this graph in DOT format.
Definition: RegAllocPBQP.cpp:925
llvm::PBQP::RegAlloc::PBQPRAGraph
Definition: RegAllocPBQP.h:502
llvm::PBQP::RegAlloc::RegAllocSolverImpl::NodeId
GraphBase::NodeId NodeId
Definition: RegAllocPBQP.h:280
llvm::Metadata
Root of the metadata hierarchy.
Definition: Metadata.h:62
llvm::PBQP::RegAlloc::RegAllocSolverImpl::Graph
PBQP::Graph< RegAllocSolverImpl > Graph
Definition: RegAllocPBQP.h:287
MCRegister.h
llvm::PBQP::RegAlloc::MatrixMetadata::getWorstCol
unsigned getWorstCol() const
Definition: RegAllocPBQP.h:82
llvm::ARMBuildAttrs::Allowed
@ Allowed
Definition: ARMBuildAttributes.h:121
Math.h
llvm::PBQP::RegAlloc::NodeMetadata::setVReg
void setVReg(Register VReg)
Definition: RegAllocPBQP.h:202
G
const DataFlowGraph & G
Definition: RDFGraph.cpp:202
llvm::PBQP::RegAlloc::NodeMetadata::NodeMetadata
NodeMetadata(const NodeMetadata &Other)
Definition: RegAllocPBQP.h:185
llvm::PBQP::RegAlloc::NodeMetadata::isConservativelyAllocatable
bool isConservativelyAllocatable() const
Definition: RegAllocPBQP.h:244
llvm::PBQP::Graph::getEdgeCosts
const Matrix & getEdgeCosts(EdgeId EId) const
Get an edge's cost matrix.
Definition: Graph.h:530
llvm::PBQP::RegAlloc::NodeMetadata::handleRemoveEdge
void handleRemoveEdge(const MatrixMetadata &MD, bool Transpose)
Definition: RegAllocPBQP.h:236
llvm::PBQP::Graph::disconnectAllNeighborsFromNode
void disconnectAllNeighborsFromNode(NodeId NId)
Convenience method to disconnect all neighbours from the given node.
Definition: Graph.h:635
llvm::PBQP::RegAlloc::RegAllocSolverImpl::handleReconnectEdge
void handleReconnectEdge(EdgeId EId, NodeId NId)
Definition: RegAllocPBQP.h:321
llvm::PBQP::RegAlloc::AllowedRegVector::hash_value
friend hash_code hash_value(const AllowedRegVector &)
Definition: RegAllocPBQP.h:124
llvm::PBQP::Solution
Represents a solution to a PBQP problem.
Definition: Solution.h:26
llvm::find
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1571
move
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
Definition: README.txt:546
llvm::PBQP::RegAlloc::RegAllocSolverImpl::solve
Solution solve()
Definition: RegAllocPBQP.h:291
llvm::PBQP::Vector
PBQP Vector class.
Definition: Math.h:25
llvm::DenseMap
Definition: DenseMap.h:714
llvm::PBQP::Vector::getLength
unsigned getLength() const
Return the length of the vector.
Definition: Math.h:60
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::PBQP::RegAlloc::MatrixMetadata::getUnsafeRows
const bool * getUnsafeRows() const
Definition: RegAllocPBQP.h:83
G
#define G(x, y, z)
Definition: MD5.cpp:57
llvm::PBQP::GraphBase::NodeId
unsigned NodeId
Definition: Graph.h:28
llvm::PBQP::Graph::getNodeDegree
NodeEntry::AdjEdgeList::size_type getNodeDegree(NodeId NId) const
Definition: Graph.h:500
llvm::PBQP::RegAlloc::NodeMetadata
Holds solver state and other metadata relevant to each PBQP RA node.
Definition: RegAllocPBQP.h:169
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::PBQP::applyR1
void applyR1(GraphT &G, typename GraphT::NodeId NId)
Reduce a node of degree one.
Definition: ReductionRules.h:30
llvm::move
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1609
llvm::PBQP::RegAlloc::RegAllocSolverImpl::EdgeMetadata
Definition: RegAllocPBQP.h:284
llvm::PBQP::Graph::empty
bool empty() const
Returns true if the graph is empty.
Definition: Graph.h:447
llvm::PBQP::Graph::nodeIds
NodeIdSet nodeIds() const
Definition: Graph.h:449
llvm::PBQP::RegAlloc::getSpillOptionIdx
unsigned getSpillOptionIdx()
Spill option index.
Definition: RegAllocPBQP.h:48
llvm::PBQP::RegAlloc::GraphMetadata::AllowedRegVecRef
AllowedRegVecPool::PoolRef AllowedRegVecRef
Definition: RegAllocPBQP.h:137
llvm::PBQP::RegAlloc::hash_value
hash_code hash_value(const AllowedRegVector &OptRegs)
Definition: RegAllocPBQP.h:124
llvm::PBQP::backpropagate
Solution backpropagate(GraphT &G, StackT stack)
Definition: ReductionRules.h:180
llvm::PBQP::RegAlloc::NodeMetadata::ReductionState
enum { Unprocessed, NotProvablyAllocatable, ConservativelyAllocatable, OptimallyReducible } ReductionState
Definition: RegAllocPBQP.h:181
llvm::PBQP::RegAlloc::GraphMetadata::getAllowedRegs
AllowedRegVecRef getAllowedRegs(AllowedRegVector Allowed)
Definition: RegAllocPBQP.h:159
Graph.h
NDEBUG
#define NDEBUG
Definition: regutils.h:48
llvm::PBQP::RegAlloc::RegAllocSolverImpl::handleDisconnectEdge
void handleDisconnectEdge(EdgeId EId, NodeId NId)
Definition: RegAllocPBQP.h:314
llvm::MachineFunction
Definition: MachineFunction.h:230
llvm::PBQP::RegAlloc::AllowedRegVector::operator[]
MCRegister operator[](size_t I) const
Definition: RegAllocPBQP.h:107
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:136
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
llvm::PBQP::RegAlloc::AllowedRegVector
Holds a vector of the allowed physical regs for a vreg.
Definition: RegAllocPBQP.h:94
llvm::PBQP::RegAlloc::AllowedRegVector::AllowedRegVector
AllowedRegVector()=default
llvm::PBQP::RegAlloc::NodeMetadata::getReductionState
ReductionState getReductionState() const
Definition: RegAllocPBQP.h:215
llvm::Register
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
llvm::PBQP::RegAlloc::RegAllocSolverImpl::handleSetNodeCosts
void handleSetNodeCosts(NodeId NId, const Vector &newCosts)
Definition: RegAllocPBQP.h:307
llvm::PBQP::RegAlloc::solve
Solution solve(PBQPRAGraph &G)
Definition: RegAllocPBQP.h:521
j
return j(j<< 16)
llvm::PBQP::RegAlloc::MatrixMetadata::getWorstRow
unsigned getWorstRow() const
Definition: RegAllocPBQP.h:81
llvm::PBQP::Graph::getNodeMetadata
NodeMetadata & getNodeMetadata(NodeId NId)
Definition: Graph.h:492
std
Definition: BitVector.h:838
llvm::PBQP::ValuePool< AllowedRegVector >::PoolRef
std::shared_ptr< const AllowedRegVector > PoolRef
Definition: CostAllocator.h:30
llvm::PBQP::RegAlloc::GraphMetadata::LIS
LiveIntervals & LIS
Definition: RegAllocPBQP.h:145
llvm::PBQP::RegAlloc::GraphMetadata::setNodeIdForVReg
void setNodeIdForVReg(Register VReg, GraphBase::NodeId NId)
Definition: RegAllocPBQP.h:148
llvm::PBQP::PoolCostAllocator
Definition: CostAllocator.h:107
llvm::PBQP::ValuePool< AllowedRegVector >
llvm::PBQP::MDMatrix
Definition: Math.h:272
llvm::PBQP::applyR2
void applyR2(GraphT &G, typename GraphT::NodeId NId)
Definition: ReductionRules.h:74
llvm::PBQP::RegAlloc::MatrixMetadata::operator=
MatrixMetadata & operator=(const MatrixMetadata &)=delete
llvm::PBQP::ValuePool::getValue
PoolRef getValue(ValueKeyT ValueKey)
Definition: CostAllocator.h:95
llvm::LiveIntervals
Definition: LiveIntervals.h:54
llvm::PBQP::RegAlloc::NodeMetadata::wasConservativelyAllocatable
bool wasConservativelyAllocatable() const
Definition: RegAllocPBQP.h:251
Solution.h
llvm::PBQP::Graph::setSolver
void setSolver(SolverT &S)
Lock this graph to the given solver instance in preparation for running the solver.
Definition: Graph.h:356
llvm::hash_combine
hash_code hash_combine(const Ts &...args)
Combine values into a single hash_code.
Definition: Hashing.h:604
llvm::hash_combine_range
hash_code hash_combine_range(InputIteratorT first, InputIteratorT last)
Compute a hash_code for a sequence of values.
Definition: Hashing.h:482
llvm::max
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:340
RegAlloc
static cl::opt< RegisterRegAlloc::FunctionPassCtor, false, RegisterPassParser< RegisterRegAlloc > > RegAlloc("regalloc", cl::Hidden, cl::init(&useDefaultRegisterAllocator), cl::desc("Register allocator to use"))
llvm::PBQP::Graph< RegAllocSolverImpl >
llvm::PBQP::RegAlloc::GraphMetadata::getNodeIdForVReg
GraphBase::NodeId getNodeIdForVReg(Register VReg) const
Definition: RegAllocPBQP.h:152
llvm::PBQP::RegAlloc::NodeMetadata::setAllowedRegs
void setAllowedRegs(GraphMetadata::AllowedRegVecRef AllowedRegs)
Definition: RegAllocPBQP.h:205
llvm::PBQP::RegAlloc::AllowedRegVector::operator!=
bool operator!=(const AllowedRegVector &Other) const
Definition: RegAllocPBQP.h:115
Register.h
ReductionRules.h
llvm::PBQP::RegAlloc::NodeMetadata::getVReg
Register getVReg() const
Definition: RegAllocPBQP.h:203
llvm::PBQP::RegAlloc::RegAllocSolverImpl::RegAllocSolverImpl
RegAllocSolverImpl(Graph &G)
Definition: RegAllocPBQP.h:289
llvm::PBQP::Graph::unsetSolver
void unsetSolver()
Release from solver instance.
Definition: Graph.h:366
llvm::PBQP::RegAlloc::AllowedRegVector::AllowedRegVector
AllowedRegVector(const std::vector< MCRegister > &OptVec)
Definition: RegAllocPBQP.h:101
llvm::PBQP::MDMatrix::getMetadata
const Metadata & getMetadata() const
Definition: Math.h:277
copy
we should consider alternate ways to model stack dependencies Lots of things could be done in WebAssemblyTargetTransformInfo cpp there are numerous optimization related hooks that can be overridden in WebAssemblyTargetLowering Instead of the OptimizeReturned which should consider preserving the returned attribute through to MachineInstrs and extending the MemIntrinsicResults pass to do this optimization on calls too That would also let the WebAssemblyPeephole pass clean up dead defs for such as it does for stores Consider implementing and or getMachineCombinerPatterns Find a clean way to fix the problem which leads to the Shrink Wrapping pass being run after the WebAssembly PEI pass When setting multiple variables to the same we currently get code like const It could be done with a smaller encoding like local tee $pop5 local copy
Definition: README.txt:101
llvm::PBQP::RegAlloc::GraphMetadata::MBFI
MachineBlockFrequencyInfo & MBFI
Definition: RegAllocPBQP.h:146
Other
Optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:1172
llvm::PBQP::RegAlloc::RegAllocSolverImpl::handleUpdateCosts
void handleUpdateCosts(EdgeId EId, const Matrix &NewCosts)
Definition: RegAllocPBQP.h:327
llvm::MCRegister
Wrapper class representing physical registers. Should be passed by value.
Definition: MCRegister.h:23
llvm::PBQP::Matrix
PBQP Matrix class.
Definition: Math.h:121
llvm::hash_code
An opaque object representing a hash code.
Definition: Hashing.h:72