LLVM  14.0.0git
SpillPlacement.cpp
Go to the documentation of this file.
1 //===- SpillPlacement.cpp - Optimal Spill Code Placement ------------------===//
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 implements the spill code placement analysis.
10 //
11 // Each edge bundle corresponds to a node in a Hopfield network. Constraints on
12 // basic blocks are weighted by the block frequency and added to become the node
13 // bias.
14 //
15 // Transparent basic blocks have the variable live through, but don't care if it
16 // is spilled or in a register. These blocks become connections in the Hopfield
17 // network, again weighted by block frequency.
18 //
19 // The Hopfield network minimizes (possibly locally) its energy function:
20 //
21 // E = -sum_n V_n * ( B_n + sum_{n, m linked by b} V_m * F_b )
22 //
23 // The energy function represents the expected spill code execution frequency,
24 // or the cost of spilling. This is a Lyapunov function which never increases
25 // when a node is updated. It is guaranteed to converge to a local minimum.
26 //
27 //===----------------------------------------------------------------------===//
28 
29 #include "SpillPlacement.h"
30 #include "llvm/ADT/BitVector.h"
36 #include "llvm/CodeGen/Passes.h"
37 #include "llvm/InitializePasses.h"
38 #include "llvm/Pass.h"
39 #include <algorithm>
40 #include <cassert>
41 #include <cstdint>
42 #include <utility>
43 
44 using namespace llvm;
45 
46 #define DEBUG_TYPE "spill-code-placement"
47 
48 char SpillPlacement::ID = 0;
49 
51 
53  "Spill Code Placement Analysis", true, true)
57  "Spill Code Placement Analysis", true, true)
58 
59 void SpillPlacement::getAnalysisUsage(AnalysisUsage &AU) const {
60  AU.setPreservesAll();
61  AU.addRequired<MachineBlockFrequencyInfo>();
62  AU.addRequiredTransitive<EdgeBundles>();
63  AU.addRequiredTransitive<MachineLoopInfo>();
65 }
66 
67 /// Node - Each edge bundle corresponds to a Hopfield node.
68 ///
69 /// The node contains precomputed frequency data that only depends on the CFG,
70 /// but Bias and Links are computed each time placeSpills is called.
71 ///
72 /// The node Value is positive when the variable should be in a register. The
73 /// value can change when linked nodes change, but convergence is very fast
74 /// because all weights are positive.
76  /// BiasN - Sum of blocks that prefer a spill.
78 
79  /// BiasP - Sum of blocks that prefer a register.
81 
82  /// Value - Output value of this node computed from the Bias and links.
83  /// This is always on of the values {-1, 0, 1}. A positive number means the
84  /// variable should go in a register through this bundle.
85  int Value;
86 
88 
89  /// Links - (Weight, BundleNo) for all transparent blocks connecting to other
90  /// bundles. The weights are all positive block frequencies.
92 
93  /// SumLinkWeights - Cached sum of the weights of all links + ThresHold.
95 
96  /// preferReg - Return true when this node prefers to be in a register.
97  bool preferReg() const {
98  // Undecided nodes (Value==0) go on the stack.
99  return Value > 0;
100  }
101 
102  /// mustSpill - Return True if this node is so biased that it must spill.
103  bool mustSpill() const {
104  // We must spill if Bias < -sum(weights) or the MustSpill flag was set.
105  // BiasN is saturated when MustSpill is set, make sure this still returns
106  // true when the RHS saturates. Note that SumLinkWeights includes Threshold.
107  return BiasN >= BiasP + SumLinkWeights;
108  }
109 
110  /// clear - Reset per-query data, but preserve frequencies that only depend on
111  /// the CFG.
112  void clear(const BlockFrequency &Threshold) {
113  BiasN = BiasP = Value = 0;
114  SumLinkWeights = Threshold;
115  Links.clear();
116  }
117 
118  /// addLink - Add a link to bundle b with weight w.
119  void addLink(unsigned b, BlockFrequency w) {
120  // Update cached sum.
121  SumLinkWeights += w;
122 
123  // There can be multiple links to the same bundle, add them up.
124  for (std::pair<BlockFrequency, unsigned> &L : Links)
125  if (L.second == b) {
126  L.first += w;
127  return;
128  }
129  // This must be the first link to b.
130  Links.push_back(std::make_pair(w, b));
131  }
132 
133  /// addBias - Bias this node.
135  switch (direction) {
136  default:
137  break;
138  case PrefReg:
139  BiasP += freq;
140  break;
141  case PrefSpill:
142  BiasN += freq;
143  break;
144  case MustSpill:
146  break;
147  }
148  }
149 
150  /// update - Recompute Value from Bias and Links. Return true when node
151  /// preference changes.
152  bool update(const Node nodes[], const BlockFrequency &Threshold) {
153  // Compute the weighted sum of inputs.
154  BlockFrequency SumN = BiasN;
155  BlockFrequency SumP = BiasP;
156  for (std::pair<BlockFrequency, unsigned> &L : Links) {
157  if (nodes[L.second].Value == -1)
158  SumN += L.first;
159  else if (nodes[L.second].Value == 1)
160  SumP += L.first;
161  }
162 
163  // Each weighted sum is going to be less than the total frequency of the
164  // bundle. Ideally, we should simply set Value = sign(SumP - SumN), but we
165  // will add a dead zone around 0 for two reasons:
166  //
167  // 1. It avoids arbitrary bias when all links are 0 as is possible during
168  // initial iterations.
169  // 2. It helps tame rounding errors when the links nominally sum to 0.
170  //
171  bool Before = preferReg();
172  if (SumN >= SumP + Threshold)
173  Value = -1;
174  else if (SumP >= SumN + Threshold)
175  Value = 1;
176  else
177  Value = 0;
178  return Before != preferReg();
179  }
180 
182  const Node nodes[]) const {
183  for (const auto &Elt : Links) {
184  unsigned n = Elt.second;
185  // Neighbors that already have the same value are not going to
186  // change because of this node changing.
187  if (Value != nodes[n].Value)
188  List.insert(n);
189  }
190  }
191 };
192 
193 bool SpillPlacement::runOnMachineFunction(MachineFunction &mf) {
194  MF = &mf;
195  bundles = &getAnalysis<EdgeBundles>();
196  loops = &getAnalysis<MachineLoopInfo>();
197 
198  assert(!nodes && "Leaking node array");
199  nodes = new Node[bundles->getNumBundles()];
200  TodoList.clear();
201  TodoList.setUniverse(bundles->getNumBundles());
202 
203  // Compute total ingoing and outgoing block frequencies for all bundles.
204  BlockFrequencies.resize(mf.getNumBlockIDs());
205  MBFI = &getAnalysis<MachineBlockFrequencyInfo>();
206  setThreshold(MBFI->getEntryFreq());
207  for (auto &I : mf) {
208  unsigned Num = I.getNumber();
209  BlockFrequencies[Num] = MBFI->getBlockFreq(&I);
210  }
211 
212  // We never change the function.
213  return false;
214 }
215 
216 void SpillPlacement::releaseMemory() {
217  delete[] nodes;
218  nodes = nullptr;
219  TodoList.clear();
220 }
221 
222 /// activate - mark node n as active if it wasn't already.
223 void SpillPlacement::activate(unsigned n) {
224  TodoList.insert(n);
225  if (ActiveNodes->test(n))
226  return;
227  ActiveNodes->set(n);
228  nodes[n].clear(Threshold);
229 
230  // Very large bundles usually come from big switches, indirect branches,
231  // landing pads, or loops with many 'continue' statements. It is difficult to
232  // allocate registers when so many different blocks are involved.
233  //
234  // Give a small negative bias to large bundles such that a substantial
235  // fraction of the connected blocks need to be interested before we consider
236  // expanding the region through the bundle. This helps compile time by
237  // limiting the number of blocks visited and the number of links in the
238  // Hopfield network.
239  if (bundles->getBlocks(n).size() > 100) {
240  nodes[n].BiasP = 0;
241  nodes[n].BiasN = (MBFI->getEntryFreq() / 16);
242  }
243 }
244 
245 /// Set the threshold for a given entry frequency.
246 ///
247 /// Set the threshold relative to \c Entry. Since the threshold is used as a
248 /// bound on the open interval (-Threshold;Threshold), 1 is the minimum
249 /// threshold.
250 void SpillPlacement::setThreshold(const BlockFrequency &Entry) {
251  // Apparently 2 is a good threshold when Entry==2^14, but we need to scale
252  // it. Divide by 2^13, rounding as appropriate.
253  uint64_t Freq = Entry.getFrequency();
254  uint64_t Scaled = (Freq >> 13) + bool(Freq & (1 << 12));
255  Threshold = std::max(UINT64_C(1), Scaled);
256 }
257 
258 /// addConstraints - Compute node biases and weights from a set of constraints.
259 /// Set a bit in NodeMask for each active node.
261  for (const BlockConstraint &LB : LiveBlocks) {
262  BlockFrequency Freq = BlockFrequencies[LB.Number];
263 
264  // Live-in to block?
265  if (LB.Entry != DontCare) {
266  unsigned ib = bundles->getBundle(LB.Number, false);
267  activate(ib);
268  nodes[ib].addBias(Freq, LB.Entry);
269  }
270 
271  // Live-out from block?
272  if (LB.Exit != DontCare) {
273  unsigned ob = bundles->getBundle(LB.Number, true);
274  activate(ob);
275  nodes[ob].addBias(Freq, LB.Exit);
276  }
277  }
278 }
279 
280 /// addPrefSpill - Same as addConstraints(PrefSpill)
282  for (unsigned B : Blocks) {
283  BlockFrequency Freq = BlockFrequencies[B];
284  if (Strong)
285  Freq += Freq;
286  unsigned ib = bundles->getBundle(B, false);
287  unsigned ob = bundles->getBundle(B, true);
288  activate(ib);
289  activate(ob);
290  nodes[ib].addBias(Freq, PrefSpill);
291  nodes[ob].addBias(Freq, PrefSpill);
292  }
293 }
294 
296  for (unsigned Number : Links) {
297  unsigned ib = bundles->getBundle(Number, false);
298  unsigned ob = bundles->getBundle(Number, true);
299 
300  // Ignore self-loops.
301  if (ib == ob)
302  continue;
303  activate(ib);
304  activate(ob);
305  BlockFrequency Freq = BlockFrequencies[Number];
306  nodes[ib].addLink(ob, Freq);
307  nodes[ob].addLink(ib, Freq);
308  }
309 }
310 
312  RecentPositive.clear();
313  for (unsigned n : ActiveNodes->set_bits()) {
314  update(n);
315  // A node that must spill, or a node without any links is not going to
316  // change its value ever again, so exclude it from iterations.
317  if (nodes[n].mustSpill())
318  continue;
319  if (nodes[n].preferReg())
320  RecentPositive.push_back(n);
321  }
322  return !RecentPositive.empty();
323 }
324 
325 bool SpillPlacement::update(unsigned n) {
326  if (!nodes[n].update(nodes, Threshold))
327  return false;
328  nodes[n].getDissentingNeighbors(TodoList, nodes);
329  return true;
330 }
331 
332 /// iterate - Repeatedly update the Hopfield nodes until stability or the
333 /// maximum number of iterations is reached.
335  // We do not need to push those node in the todolist.
336  // They are already been proceeded as part of the previous iteration.
337  RecentPositive.clear();
338 
339  // Since the last iteration, the todolist have been augmented by calls
340  // to addConstraints, addLinks, and co.
341  // Update the network energy starting at this new frontier.
342  // The call to ::update will add the nodes that changed into the todolist.
343  unsigned Limit = bundles->getNumBundles() * 10;
344  while(Limit-- > 0 && !TodoList.empty()) {
345  unsigned n = TodoList.pop_back_val();
346  if (!update(n))
347  continue;
348  if (nodes[n].preferReg())
349  RecentPositive.push_back(n);
350  }
351 }
352 
354  RecentPositive.clear();
355  TodoList.clear();
356  // Reuse RegBundles as our ActiveNodes vector.
357  ActiveNodes = &RegBundles;
358  ActiveNodes->clear();
359  ActiveNodes->resize(bundles->getNumBundles());
360 }
361 
362 bool
364  assert(ActiveNodes && "Call prepare() first");
365 
366  // Write preferences back to ActiveNodes.
367  bool Perfect = true;
368  for (unsigned n : ActiveNodes->set_bits())
369  if (!nodes[n].preferReg()) {
370  ActiveNodes->reset(n);
371  Perfect = false;
372  }
373  ActiveNodes = nullptr;
374  return Perfect;
375 }
376 
378  auto toString = [](BorderConstraint C) -> StringRef {
379  switch(C) {
380  case DontCare: return "DontCare";
381  case PrefReg: return "PrefReg";
382  case PrefSpill: return "PrefSpill";
383  case PrefBoth: return "PrefBoth";
384  case MustSpill: return "MustSpill";
385  };
386  llvm_unreachable("uncovered switch");
387  };
388 
389  dbgs() << "{" << Number << ", "
390  << toString(Entry) << ", "
391  << toString(Exit) << ", "
392  << (ChangesValue ? "changes" : "no change") << "}";
393 }
394 
396  print(dbgs());
397  dbgs() << "\n";
398 }
true
Spill Code Placement true
Definition: SpillPlacement.cpp:57
llvm::SpillPlacement
Definition: SpillPlacement.h:43
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::SpillPlacement::Node::BiasN
BlockFrequency BiasN
BiasN - Sum of blocks that prefer a spill.
Definition: SpillPlacement.cpp:77
Pass.h
llvm::BitVector::set
BitVector & set()
Definition: BitVector.h:343
llvm::BitVector::clear
void clear()
clear - Removes all bits from the bitvector.
Definition: BitVector.h:327
llvm::toString
std::string toString(Error E)
Write all error messages (if any) in E to a string.
Definition: Error.h:1020
llvm::SmallVector< std::pair< BlockFrequency, unsigned >, 4 >
llvm::BitVector::set_bits
iterator_range< const_set_bits_iterator > set_bits() const
Definition: BitVector.h:132
MachineBasicBlock.h
llvm::MachineFunction::getNumBlockIDs
unsigned getNumBlockIDs() const
getNumBlockIDs - Return the number of MBB ID's allocated.
Definition: MachineFunction.h:753
llvm::SpillPlacement::iterate
void iterate()
iterate - Update the network iteratively until convergence, or new bundles are found.
Definition: SpillPlacement.cpp:334
llvm::SpillPlacement::Node::Value
int Value
Value - Output value of this node computed from the Bias and links.
Definition: SpillPlacement.cpp:85
llvm::BlockFrequency::getMaxFrequency
static uint64_t getMaxFrequency()
Returns the maximum possible frequency, the saturation value.
Definition: BlockFrequency.h:31
llvm::BitVector::resize
void resize(unsigned N, bool t=false)
resize - Grow or shrink the bitvector.
Definition: BitVector.h:333
llvm::SpillPlacementID
char & SpillPlacementID
SpillPlacement analysis.
Definition: SpillPlacement.cpp:50
llvm::SpillPlacement::Node::preferReg
bool preferReg() const
preferReg - Return true when this node prefers to be in a register.
Definition: SpillPlacement.cpp:97
llvm::SpillPlacement::addConstraints
void addConstraints(ArrayRef< BlockConstraint > LiveBlocks)
addConstraints - Add constraints and biases.
Definition: SpillPlacement.cpp:260
SpillPlacement.h
freq
block freq
Definition: BlockFrequencyInfo.cpp:301
llvm::MachineBlockFrequencyInfo::getBlockFreq
BlockFrequency getBlockFreq(const MachineBasicBlock *MBB) const
getblockFreq - Return block frequency.
Definition: MachineBlockFrequencyInfo.cpp:230
llvm::MachineFunctionPass::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
Definition: MachineFunctionPass.cpp:102
llvm::MachineLoopInfo
Definition: MachineLoopInfo.h:90
llvm::EdgeBundles
Definition: EdgeBundles.h:24
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::SpillPlacement::Node::addBias
void addBias(BlockFrequency freq, BorderConstraint direction)
addBias - Bias this node.
Definition: SpillPlacement.cpp:134
llvm::SpillPlacement::Node::BiasP
BlockFrequency BiasP
BiasP - Sum of blocks that prefer a register.
Definition: SpillPlacement.cpp:80
MachineLoopInfo.h
llvm::SpillPlacement::BlockConstraint::ChangesValue
bool ChangesValue
True when this block changes the value of the live range.
Definition: SpillPlacement.h:97
llvm::MachineBlockFrequencyInfo
MachineBlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate machine basic b...
Definition: MachineBlockFrequencyInfo.h:33
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::SpillPlacement::Node::SumLinkWeights
BlockFrequency SumLinkWeights
SumLinkWeights - Cached sum of the weights of all links + ThresHold.
Definition: SpillPlacement.cpp:94
llvm::SpillPlacement::Node::getDissentingNeighbors
void getDissentingNeighbors(SparseSet< unsigned > &List, const Node nodes[]) const
Definition: SpillPlacement.cpp:181
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
b
the resulting code requires compare and branches when and if the revised code is with conditional branches instead of More there is a byte word extend before each where there should be only and the condition codes are not remembered when the same two values are compared twice More LSR enhancements i8 and i32 load store addressing modes are identical int b
Definition: README.txt:418
llvm::SpillPlacement::Node::clear
void clear(const BlockFrequency &Threshold)
clear - Reset per-query data, but preserve frequencies that only depend on the CFG.
Definition: SpillPlacement.cpp:112
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::SpillPlacement::finish
bool finish()
finish - Compute the optimal spill code placement given the constraints.
Definition: SpillPlacement.cpp:363
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:53
BitVector.h
llvm::BitVector
Definition: BitVector.h:74
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(SpillPlacement, DEBUG_TYPE, "Spill Code Placement Analysis", true, true) INITIALIZE_PASS_END(SpillPlacement
llvm::EdgeBundles::getNumBundles
unsigned getNumBundles() const
getNumBundles - Return the total number of bundles in the CFG.
Definition: EdgeBundles.h:44
EdgeBundles.h
llvm::SpillPlacement::Node::update
bool update(const Node nodes[], const BlockFrequency &Threshold)
update - Recompute Value from Bias and Links.
Definition: SpillPlacement.cpp:152
llvm::SpillPlacement::Node::Links
LinkVector Links
Links - (Weight, BundleNo) for all transparent blocks connecting to other bundles.
Definition: SpillPlacement.cpp:91
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
llvm::Pass::print
virtual void print(raw_ostream &OS, const Module *M) const
print - Print out the internal state of the pass.
Definition: Pass.cpp:125
llvm::SpillPlacement::BlockConstraint::Number
unsigned Number
Basic block number (from MBB::getNumber()).
Definition: SpillPlacement.h:90
Passes.h
llvm::SpillPlacement::BlockConstraint::Entry
BorderConstraint Entry
Constraint on block entry.
Definition: SpillPlacement.h:91
llvm::SpillPlacement::Node
Node - Each edge bundle corresponds to a Hopfield node.
Definition: SpillPlacement.cpp:75
llvm::BlockFrequency
Definition: BlockFrequency.h:24
llvm::SpillPlacement::PrefReg
@ PrefReg
Block entry/exit prefers a register.
Definition: SpillPlacement.h:82
nodes
Unify divergent function exit nodes
Definition: AMDGPUUnifyDivergentExitNodes.cpp:87
uint64_t
llvm::SparseSet::clear
void clear()
clear - Clears the set.
Definition: SparseSet.h:194
Scaled
@ Scaled
Definition: ARCInstrInfo.cpp:35
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::SpillPlacement::addPrefSpill
void addPrefSpill(ArrayRef< unsigned > Blocks, bool Strong)
addPrefSpill - Add PrefSpill constraints to all blocks listed.
Definition: SpillPlacement.cpp:281
llvm::SparseSet::setUniverse
void setUniverse(unsigned U)
setUniverse - Set the universe size which determines the largest key the set can hold.
Definition: SparseSet.h:155
llvm::SparseSet::pop_back_val
ValueT pop_back_val()
Definition: SparseSet.h:269
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::SpillPlacement::Node::mustSpill
bool mustSpill() const
mustSpill - Return True if this node is so biased that it must spill.
Definition: SpillPlacement.cpp:103
llvm::SpillPlacement::BlockConstraint::dump
void dump() const
Definition: SpillPlacement.cpp:395
llvm::SpillPlacement::PrefSpill
@ PrefSpill
Block entry/exit prefers a stack slot.
Definition: SpillPlacement.h:83
llvm::SpillPlacement::addLinks
void addLinks(ArrayRef< unsigned > Links)
addLinks - Add transparent blocks with the given numbers.
Definition: SpillPlacement.cpp:295
llvm::SpillPlacement::DontCare
@ DontCare
Block doesn't care / variable not live.
Definition: SpillPlacement.h:81
llvm::MachineFunction
Definition: MachineFunction.h:230
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:58
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:136
Number
uint32_t Number
Definition: Profile.cpp:47
llvm::SparseSet::empty
bool empty() const
empty - Returns true if the set is empty.
Definition: SparseSet.h:183
DEBUG_TYPE
#define DEBUG_TYPE
Definition: SpillPlacement.cpp:46
llvm::SpillPlacement::prepare
void prepare(BitVector &RegBundles)
prepare - Reset state and prepare for a new spill placement computation.
Definition: SpillPlacement.cpp:353
llvm::SpillPlacement::MustSpill
@ MustSpill
A register is impossible, variable must be spilled.
Definition: SpillPlacement.h:85
llvm::SpillPlacement::scanActiveBundles
bool scanActiveBundles()
scanActiveBundles - Perform an initial scan of all bundles activated by addConstraints and addLinks,...
Definition: SpillPlacement.cpp:311
llvm::BitVector::test
bool test(unsigned Idx) const
Definition: BitVector.h:447
llvm::SparseSet::insert
std::pair< iterator, bool > insert(const ValueT &Val)
insert - Attempts to insert a new element.
Definition: SparseSet.h:252
llvm::SpillPlacement::PrefBoth
@ PrefBoth
Block entry prefers both register and stack.
Definition: SpillPlacement.h:84
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:585
llvm::BitVector::reset
BitVector & reset()
Definition: BitVector.h:384
llvm::SpillPlacement::Node::addLink
void addLink(unsigned b, BlockFrequency w)
addLink - Add a link to bundle b with weight w.
Definition: SpillPlacement.cpp:119
Placement
Branch Probability Basic Block Placement
Definition: MachineBlockPlacement.cpp:600
llvm::SpillPlacement::BlockConstraint::print
void print(raw_ostream &OS) const
Definition: SpillPlacement.cpp:377
List
const NodeList & List
Definition: RDFGraph.cpp:201
llvm::SpillPlacement::BlockConstraint::Exit
BorderConstraint Exit
Constraint on block exit.
Definition: SpillPlacement.h:92
llvm::ARM_AM::ib
@ ib
Definition: ARMAddressingModes.h:69
llvm::ArrayRef::size
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:165
llvm::max
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:340
llvm::EdgeBundles::getBlocks
ArrayRef< unsigned > getBlocks(unsigned Bundle) const
getBlocks - Return an array of blocks that are connected to Bundle.
Definition: EdgeBundles.h:47
llvm::SparseSet< unsigned >
n
The same transformation can work with an even modulo with the addition of a and shrink the compare RHS by the same amount Unless the target supports that transformation probably isn t worthwhile The transformation can also easily be made to work with non zero equality for n
Definition: README.txt:685
MachineFunction.h
llvm::MachineBlockFrequencyInfo::getEntryFreq
uint64_t getEntryFreq() const
Divide a block's BlockFrequency::getFrequency() value by this value to obtain the entry block - relat...
Definition: MachineBlockFrequencyInfo.cpp:289
InitializePasses.h
MachineBlockFrequencyInfo.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
llvm::SpillPlacement::BlockConstraint
BlockConstraint - Entry and exit constraints for a basic block.
Definition: SpillPlacement.h:89
llvm::EdgeBundles::getBundle
unsigned getBundle(unsigned N, bool Out) const
getBundle - Return the ingoing (Out = false) or outgoing (Out = true) bundle number for basic block N
Definition: EdgeBundles.h:41
llvm::SpillPlacement::ID
static char ID
Definition: SpillPlacement.h:73
llvm::SpillPlacement::BorderConstraint
BorderConstraint
BorderConstraint - A basic block has separate constraints for entry and exit.
Definition: SpillPlacement.h:80