LLVM  16.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 #if LLVM_ENABLE_ABI_BREAKING_CHECKS
190  ,
191  everConservativelyAllocatable(Other.everConservativelyAllocatable)
192 #endif
193  {
194  if (NumOpts > 0) {
195  std::copy(&Other.OptUnsafeEdges[0], &Other.OptUnsafeEdges[NumOpts],
196  &OptUnsafeEdges[0]);
197  }
198  }
199 
200  NodeMetadata(NodeMetadata &&) = default;
201  NodeMetadata& operator=(NodeMetadata &&) = default;
202 
203  void setVReg(Register VReg) { this->VReg = VReg; }
204  Register getVReg() const { return VReg; }
205 
207  this->AllowedRegs = std::move(AllowedRegs);
208  }
209  const AllowedRegVector& getAllowedRegs() const { return *AllowedRegs; }
210 
211  void setup(const Vector& Costs) {
212  NumOpts = Costs.getLength() - 1;
213  OptUnsafeEdges = std::unique_ptr<unsigned[]>(new unsigned[NumOpts]());
214  }
215 
216  ReductionState getReductionState() const { return RS; }
218  assert(RS >= this->RS && "A node's reduction state can not be downgraded");
219  this->RS = RS;
220 
221 #if LLVM_ENABLE_ABI_BREAKING_CHECKS
222  // Remember this state to assert later that a non-infinite register
223  // option was available.
224  if (RS == ConservativelyAllocatable)
225  everConservativelyAllocatable = true;
226 #endif
227  }
228 
229  void handleAddEdge(const MatrixMetadata& MD, bool Transpose) {
230  DeniedOpts += Transpose ? MD.getWorstRow() : MD.getWorstCol();
231  const bool* UnsafeOpts =
232  Transpose ? MD.getUnsafeCols() : MD.getUnsafeRows();
233  for (unsigned i = 0; i < NumOpts; ++i)
234  OptUnsafeEdges[i] += UnsafeOpts[i];
235  }
236 
237  void handleRemoveEdge(const MatrixMetadata& MD, bool Transpose) {
238  DeniedOpts -= Transpose ? MD.getWorstRow() : MD.getWorstCol();
239  const bool* UnsafeOpts =
240  Transpose ? MD.getUnsafeCols() : MD.getUnsafeRows();
241  for (unsigned i = 0; i < NumOpts; ++i)
242  OptUnsafeEdges[i] -= UnsafeOpts[i];
243  }
244 
246  return (DeniedOpts < NumOpts) ||
247  (std::find(&OptUnsafeEdges[0], &OptUnsafeEdges[NumOpts], 0) !=
248  &OptUnsafeEdges[NumOpts]);
249  }
250 
251 #if LLVM_ENABLE_ABI_BREAKING_CHECKS
252  bool wasConservativelyAllocatable() const {
253  return everConservativelyAllocatable;
254  }
255 #endif
256 
257 private:
258  ReductionState RS = Unprocessed;
259  unsigned NumOpts = 0;
260  unsigned DeniedOpts = 0;
261  std::unique_ptr<unsigned[]> OptUnsafeEdges;
262  Register VReg;
264 
265 #if LLVM_ENABLE_ABI_BREAKING_CHECKS
266  bool everConservativelyAllocatable = false;
267 #endif
268 };
269 
271 private:
273 
274 public:
278  using Matrix = RAMatrix;
280 
283 
285  struct EdgeMetadata {};
287 
289 
291 
293  G.setSolver(*this);
294  Solution S;
295  setup();
296  S = backpropagate(G, reduce());
297  G.unsetSolver();
298  return S;
299  }
300 
301  void handleAddNode(NodeId NId) {
302  assert(G.getNodeCosts(NId).getLength() > 1 &&
303  "PBQP Graph should not contain single or zero-option nodes");
304  G.getNodeMetadata(NId).setup(G.getNodeCosts(NId));
305  }
306 
308  void handleSetNodeCosts(NodeId NId, const Vector& newCosts) {}
309 
310  void handleAddEdge(EdgeId EId) {
311  handleReconnectEdge(EId, G.getEdgeNode1Id(EId));
312  handleReconnectEdge(EId, G.getEdgeNode2Id(EId));
313  }
314 
316  NodeMetadata& NMd = G.getNodeMetadata(NId);
317  const MatrixMetadata& MMd = G.getEdgeCosts(EId).getMetadata();
318  NMd.handleRemoveEdge(MMd, NId == G.getEdgeNode2Id(EId));
319  promote(NId, NMd);
320  }
321 
323  NodeMetadata& NMd = G.getNodeMetadata(NId);
324  const MatrixMetadata& MMd = G.getEdgeCosts(EId).getMetadata();
325  NMd.handleAddEdge(MMd, NId == G.getEdgeNode2Id(EId));
326  }
327 
328  void handleUpdateCosts(EdgeId EId, const Matrix& NewCosts) {
329  NodeId N1Id = G.getEdgeNode1Id(EId);
330  NodeId N2Id = G.getEdgeNode2Id(EId);
331  NodeMetadata& N1Md = G.getNodeMetadata(N1Id);
332  NodeMetadata& N2Md = G.getNodeMetadata(N2Id);
333  bool Transpose = N1Id != G.getEdgeNode1Id(EId);
334 
335  // Metadata are computed incrementally. First, update them
336  // by removing the old cost.
337  const MatrixMetadata& OldMMd = G.getEdgeCosts(EId).getMetadata();
338  N1Md.handleRemoveEdge(OldMMd, Transpose);
339  N2Md.handleRemoveEdge(OldMMd, !Transpose);
340 
341  // And update now the metadata with the new cost.
342  const MatrixMetadata& MMd = NewCosts.getMetadata();
343  N1Md.handleAddEdge(MMd, Transpose);
344  N2Md.handleAddEdge(MMd, !Transpose);
345 
346  // As the metadata may have changed with the update, the nodes may have
347  // become ConservativelyAllocatable or OptimallyReducible.
348  promote(N1Id, N1Md);
349  promote(N2Id, N2Md);
350  }
351 
352 private:
353  void promote(NodeId NId, NodeMetadata& NMd) {
354  if (G.getNodeDegree(NId) == 3) {
355  // This node is becoming optimally reducible.
356  moveToOptimallyReducibleNodes(NId);
357  } else if (NMd.getReductionState() ==
358  NodeMetadata::NotProvablyAllocatable &&
360  // This node just became conservatively allocatable.
361  moveToConservativelyAllocatableNodes(NId);
362  }
363  }
364 
365  void removeFromCurrentSet(NodeId NId) {
366  switch (G.getNodeMetadata(NId).getReductionState()) {
367  case NodeMetadata::Unprocessed: break;
368  case NodeMetadata::OptimallyReducible:
369  assert(OptimallyReducibleNodes.find(NId) !=
370  OptimallyReducibleNodes.end() &&
371  "Node not in optimally reducible set.");
372  OptimallyReducibleNodes.erase(NId);
373  break;
374  case NodeMetadata::ConservativelyAllocatable:
375  assert(ConservativelyAllocatableNodes.find(NId) !=
376  ConservativelyAllocatableNodes.end() &&
377  "Node not in conservatively allocatable set.");
378  ConservativelyAllocatableNodes.erase(NId);
379  break;
380  case NodeMetadata::NotProvablyAllocatable:
381  assert(NotProvablyAllocatableNodes.find(NId) !=
382  NotProvablyAllocatableNodes.end() &&
383  "Node not in not-provably-allocatable set.");
384  NotProvablyAllocatableNodes.erase(NId);
385  break;
386  }
387  }
388 
389  void moveToOptimallyReducibleNodes(NodeId NId) {
390  removeFromCurrentSet(NId);
391  OptimallyReducibleNodes.insert(NId);
393  NodeMetadata::OptimallyReducible);
394  }
395 
396  void moveToConservativelyAllocatableNodes(NodeId NId) {
397  removeFromCurrentSet(NId);
398  ConservativelyAllocatableNodes.insert(NId);
400  NodeMetadata::ConservativelyAllocatable);
401  }
402 
403  void moveToNotProvablyAllocatableNodes(NodeId NId) {
404  removeFromCurrentSet(NId);
405  NotProvablyAllocatableNodes.insert(NId);
407  NodeMetadata::NotProvablyAllocatable);
408  }
409 
410  void setup() {
411  // Set up worklists.
412  for (auto NId : G.nodeIds()) {
413  if (G.getNodeDegree(NId) < 3)
414  moveToOptimallyReducibleNodes(NId);
416  moveToConservativelyAllocatableNodes(NId);
417  else
418  moveToNotProvablyAllocatableNodes(NId);
419  }
420  }
421 
422  // Compute a reduction order for the graph by iteratively applying PBQP
423  // reduction rules. Locally optimal rules are applied whenever possible (R0,
424  // R1, R2). If no locally-optimal rules apply then any conservatively
425  // allocatable node is reduced. Finally, if no conservatively allocatable
426  // node exists then the node with the lowest spill-cost:degree ratio is
427  // selected.
428  std::vector<GraphBase::NodeId> reduce() {
429  assert(!G.empty() && "Cannot reduce empty graph.");
430 
431  using NodeId = GraphBase::NodeId;
432  std::vector<NodeId> NodeStack;
433 
434  // Consume worklists.
435  while (true) {
436  if (!OptimallyReducibleNodes.empty()) {
437  NodeSet::iterator NItr = OptimallyReducibleNodes.begin();
438  NodeId NId = *NItr;
439  OptimallyReducibleNodes.erase(NItr);
440  NodeStack.push_back(NId);
441  switch (G.getNodeDegree(NId)) {
442  case 0:
443  break;
444  case 1:
445  applyR1(G, NId);
446  break;
447  case 2:
448  applyR2(G, NId);
449  break;
450  default: llvm_unreachable("Not an optimally reducible node.");
451  }
452  } else if (!ConservativelyAllocatableNodes.empty()) {
453  // Conservatively allocatable nodes will never spill. For now just
454  // take the first node in the set and push it on the stack. When we
455  // start optimizing more heavily for register preferencing, it may
456  // would be better to push nodes with lower 'expected' or worst-case
457  // register costs first (since early nodes are the most
458  // constrained).
459  NodeSet::iterator NItr = ConservativelyAllocatableNodes.begin();
460  NodeId NId = *NItr;
461  ConservativelyAllocatableNodes.erase(NItr);
462  NodeStack.push_back(NId);
464  } else if (!NotProvablyAllocatableNodes.empty()) {
465  NodeSet::iterator NItr =
466  std::min_element(NotProvablyAllocatableNodes.begin(),
467  NotProvablyAllocatableNodes.end(),
468  SpillCostComparator(G));
469  NodeId NId = *NItr;
470  NotProvablyAllocatableNodes.erase(NItr);
471  NodeStack.push_back(NId);
473  } else
474  break;
475  }
476 
477  return NodeStack;
478  }
479 
480  class SpillCostComparator {
481  public:
482  SpillCostComparator(const Graph& G) : G(G) {}
483 
484  bool operator()(NodeId N1Id, NodeId N2Id) {
485  PBQPNum N1SC = G.getNodeCosts(N1Id)[0];
486  PBQPNum N2SC = G.getNodeCosts(N2Id)[0];
487  if (N1SC == N2SC)
488  return G.getNodeDegree(N1Id) < G.getNodeDegree(N2Id);
489  return N1SC < N2SC;
490  }
491 
492  private:
493  const Graph& G;
494  };
495 
496  Graph& G;
497  using NodeSet = std::set<NodeId>;
498  NodeSet OptimallyReducibleNodes;
499  NodeSet ConservativelyAllocatableNodes;
500  NodeSet NotProvablyAllocatableNodes;
501 };
502 
503 class PBQPRAGraph : public PBQP::Graph<RegAllocSolverImpl> {
504 private:
506 
507 public:
509 
510  /// Dump this graph to dbgs().
511  void dump() const;
512 
513  /// Dump this graph to an output stream.
514  /// @param OS Output stream to print on.
515  void dump(raw_ostream &OS) const;
516 
517  /// Print a representation of this graph in DOT format.
518  /// @param OS Output stream to print on.
519  void printDot(raw_ostream &OS) const;
520 };
521 
523  if (G.empty())
524  return Solution();
525  RegAllocSolverImpl RegAllocSolver(G);
526  return RegAllocSolver.solve();
527 }
528 
529 } // end namespace RegAlloc
530 } // end namespace PBQP
531 
532 /// Create a PBQP register allocator instance.
533 FunctionPass *
534 createPBQPRegisterAllocator(char *customPassID = nullptr);
535 
536 } // end namespace llvm
537 
538 #endif // LLVM_CODEGEN_REGALLOCPBQP_H
i
i
Definition: README.txt:29
llvm::PBQP::RegAlloc::NodeMetadata::getAllowedRegs
const AllowedRegVector & getAllowedRegs() const
Definition: RegAllocPBQP.h:209
llvm::PBQP::RegAlloc::PBQPRAGraph::dump
void dump() const
Dump this graph to dbgs().
Definition: RegAllocPBQP.cpp:921
llvm::PBQP::RegAlloc::MatrixMetadata::MatrixMetadata
MatrixMetadata(const Matrix &M)
Definition: RegAllocPBQP.h:55
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::RegAllocType::PBQP
@ PBQP
llvm::PBQP::RegAlloc::NodeMetadata::setReductionState
void setReductionState(ReductionState RS)
Definition: RegAllocPBQP.h:217
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:948
llvm::PBQP::RegAlloc::RegAllocSolverImpl::handleAddEdge
void handleAddEdge(EdgeId EId)
Definition: RegAllocPBQP.h:310
llvm::Register::id
unsigned id() const
Definition: Register.h:111
llvm::PBQP::RegAlloc::NodeMetadata::setup
void setup(const Vector &Costs)
Definition: RegAllocPBQP.h:211
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:270
llvm::NodeSet::iterator
SetVector< SUnit * >::const_iterator iterator
Definition: MachinePipeliner.h:332
ErrorHandling.h
llvm::PBQP::RegAlloc::NodeMetadata::handleAddEdge
void handleAddEdge(const MatrixMetadata &MD, bool Transpose)
Definition: RegAllocPBQP.h:229
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:508
llvm::PBQP::Graph< RegAllocSolverImpl >::GraphMetadata
typename RegAllocSolverImpl ::GraphMetadata GraphMetadata
Definition: Graph.h:59
Hashing.h
llvm::max
Expected< ExpressionValue > max(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:337
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:307
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:282
llvm::PBQP::RegAlloc::AllowedRegVector::size
unsigned size() const
Definition: RegAllocPBQP.h:106
llvm::ARMBuildAttrs::Allowed
@ Allowed
Definition: ARMBuildAttributes.h:126
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:301
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:926
llvm::PBQP::RegAlloc::PBQPRAGraph
Definition: RegAllocPBQP.h:503
llvm::PBQP::RegAlloc::RegAllocSolverImpl::NodeId
GraphBase::NodeId NodeId
Definition: RegAllocPBQP.h:281
llvm::Metadata
Root of the metadata hierarchy.
Definition: Metadata.h:62
llvm::PBQP::RegAlloc::RegAllocSolverImpl::Graph
PBQP::Graph< RegAllocSolverImpl > Graph
Definition: RegAllocPBQP.h:288
MCRegister.h
llvm::PBQP::RegAlloc::MatrixMetadata::getWorstCol
unsigned getWorstCol() const
Definition: RegAllocPBQP.h:82
Math.h
llvm::PBQP::RegAlloc::NodeMetadata::setVReg
void setVReg(Register VReg)
Definition: RegAllocPBQP.h:203
G
const DataFlowGraph & G
Definition: RDFGraph.cpp:200
llvm::PBQP::RegAlloc::NodeMetadata::NodeMetadata
NodeMetadata(const NodeMetadata &Other)
Definition: RegAllocPBQP.h:185
llvm::PBQP::RegAlloc::NodeMetadata::isConservativelyAllocatable
bool isConservativelyAllocatable() const
Definition: RegAllocPBQP.h:245
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:237
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:322
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:1754
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:292
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:58
llvm::PBQP::RegAlloc::MatrixMetadata::getUnsafeRows
const bool * getUnsafeRows() const
Definition: RegAllocPBQP.h:83
G
#define G(x, y, z)
Definition: MD5.cpp:56
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:1861
llvm::PBQP::RegAlloc::RegAllocSolverImpl::EdgeMetadata
Definition: RegAllocPBQP.h:285
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
llvm::PBQP::RegAlloc::RegAllocSolverImpl::handleDisconnectEdge
void handleDisconnectEdge(EdgeId EId, NodeId NId)
Definition: RegAllocPBQP.h:315
llvm::MachineFunction
Definition: MachineFunction.h:257
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:143
if
if(llvm_vc STREQUAL "") set(fake_version_inc "$
Definition: CMakeLists.txt:14
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:216
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:308
llvm::PBQP::RegAlloc::solve
Solution solve(PBQPRAGraph &G)
Definition: RegAllocPBQP.h:522
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:851
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:53
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:605
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:483
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:206
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:204
llvm::PBQP::RegAlloc::RegAllocSolverImpl::RegAllocSolverImpl
RegAllocSolverImpl(Graph &G)
Definition: RegAllocPBQP.h:290
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:1251
llvm::PBQP::RegAlloc::RegAllocSolverImpl::handleUpdateCosts
void handleUpdateCosts(EdgeId EId, const Matrix &NewCosts)
Definition: RegAllocPBQP.h:328
llvm::MCRegister
Wrapper class representing physical registers. Should be passed by value.
Definition: MCRegister.h:24
llvm::PBQP::Matrix
PBQP Matrix class.
Definition: Math.h:121
llvm::hash_code
An opaque object representing a hash code.
Definition: Hashing.h:73