Go to the documentation of this file.
46 #define DEBUG_TYPE "spill-code-placement"
53 "Spill Code Placement Analysis",
true,
true)
124 for (std::pair<BlockFrequency, unsigned> &L :
Links)
130 Links.push_back(std::make_pair(w,
b));
156 for (std::pair<BlockFrequency, unsigned> &L :
Links) {
157 if (
nodes[L.second].Value == -1)
159 else if (
nodes[L.second].Value == 1)
172 if (SumN >= SumP + Threshold)
174 else if (SumP >= SumN + Threshold)
182 const Node nodes[])
const {
183 for (
const auto &Elt :
Links) {
184 unsigned n = Elt.second;
195 bundles = &getAnalysis<EdgeBundles>();
196 loops = &getAnalysis<MachineLoopInfo>();
198 assert(!nodes &&
"Leaking node array");
205 MBFI = &getAnalysis<MachineBlockFrequencyInfo>();
208 unsigned Num =
I.getNumber();
216 void SpillPlacement::releaseMemory() {
223 void SpillPlacement::activate(
unsigned n) {
225 if (ActiveNodes->
test(
n))
228 nodes[
n].
clear(Threshold);
253 uint64_t Freq = Entry.getFrequency();
266 unsigned ib = bundles->
getBundle(LB.Number,
false);
273 unsigned ob = bundles->
getBundle(LB.Number,
true);
275 nodes[ob].
addBias(Freq, LB.Exit);
282 for (
unsigned B : Blocks) {
296 for (
unsigned Number : Links) {
312 RecentPositive.
clear();
313 for (
unsigned n : ActiveNodes->
set_bits()) {
317 if (nodes[
n].mustSpill())
319 if (nodes[
n].preferReg())
320 RecentPositive.push_back(
n);
322 return !RecentPositive.empty();
325 bool SpillPlacement::update(
unsigned n) {
326 if (!nodes[
n].update(nodes, Threshold))
337 RecentPositive.
clear();
344 while(Limit-- > 0 && !TodoList.
empty()) {
348 if (nodes[
n].preferReg())
349 RecentPositive.push_back(
n);
354 RecentPositive.
clear();
357 ActiveNodes = &RegBundles;
358 ActiveNodes->
clear();
364 assert(ActiveNodes &&
"Call prepare() first");
368 for (
unsigned n : ActiveNodes->
set_bits())
369 if (!nodes[
n].preferReg()) {
373 ActiveNodes =
nullptr;
381 case PrefReg:
return "PrefReg";
Spill Code Placement true
This is an optimization pass for GlobalISel generic memory operations.
BlockFrequency BiasN
BiasN - Sum of blocks that prefer a spill.
void clear()
clear - Removes all bits from the bitvector.
iterator_range< const_set_bits_iterator > set_bits() const
unsigned getNumBlockIDs() const
getNumBlockIDs - Return the number of MBB ID's allocated.
void iterate()
iterate - Update the network iteratively until convergence, or new bundles are found.
int Value
Value - Output value of this node computed from the Bias and links.
static uint64_t getMaxFrequency()
Returns the maximum possible frequency, the saturation value.
void resize(unsigned N, bool t=false)
resize - Grow or shrink the bitvector.
char & SpillPlacementID
SpillPlacement analysis.
bool preferReg() const
preferReg - Return true when this node prefers to be in a register.
Expected< ExpressionValue > max(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
void addConstraints(ArrayRef< BlockConstraint > LiveBlocks)
addConstraints - Add constraints and biases.
BlockFrequency getBlockFreq(const MachineBasicBlock *MBB) const
getblockFreq - Return block frequency.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
void addBias(BlockFrequency freq, BorderConstraint direction)
addBias - Bias this node.
BlockFrequency BiasP
BiasP - Sum of blocks that prefer a register.
bool ChangesValue
True when this block changes the value of the live range.
MachineBlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate machine basic b...
(vector float) vec_cmpeq(*A, *B) C
BlockFrequency SumLinkWeights
SumLinkWeights - Cached sum of the weights of all links + ThresHold.
void getDissentingNeighbors(SparseSet< unsigned > &List, const Node nodes[]) const
Represent the analysis usage information of a pass.
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
void clear(const BlockFrequency &Threshold)
clear - Reset per-query data, but preserve frequencies that only depend on the CFG.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
bool finish()
finish - Compute the optimal spill code placement given the constraints.
This class implements an extremely fast bulk output stream that can only output to a stream.
INITIALIZE_PASS_BEGIN(SpillPlacement, DEBUG_TYPE, "Spill Code Placement Analysis", true, true) INITIALIZE_PASS_END(SpillPlacement
unsigned getNumBundles() const
getNumBundles - Return the total number of bundles in the CFG.
bool update(const Node nodes[], const BlockFrequency &Threshold)
update - Recompute Value from Bias and Links.
LinkVector Links
Links - (Weight, BundleNo) for all transparent blocks connecting to other bundles.
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
virtual void print(raw_ostream &OS, const Module *M) const
print - Print out the internal state of the pass.
unsigned Number
Basic block number (from MBB::getNumber()).
BorderConstraint Entry
Constraint on block entry.
Node - Each edge bundle corresponds to a Hopfield node.
@ PrefReg
Block entry/exit prefers a register.
Unify divergent function exit nodes
void clear()
clear - Clears the set.
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
void addPrefSpill(ArrayRef< unsigned > Blocks, bool Strong)
addPrefSpill - Add PrefSpill constraints to all blocks listed.
void setUniverse(unsigned U)
setUniverse - Set the universe size which determines the largest key the set can hold.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
bool mustSpill() const
mustSpill - Return True if this node is so biased that it must spill.
@ PrefSpill
Block entry/exit prefers a stack slot.
void addLinks(ArrayRef< unsigned > Links)
addLinks - Add transparent blocks with the given numbers.
@ DontCare
Block doesn't care / variable not live.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
StringRef - Represent a constant reference to a string, i.e.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
bool empty() const
empty - Returns true if the set is empty.
void prepare(BitVector &RegBundles)
prepare - Reset state and prepare for a new spill placement computation.
@ MustSpill
A register is impossible, variable must be spilled.
bool scanActiveBundles()
scanActiveBundles - Perform an initial scan of all bundles activated by addConstraints and addLinks,...
bool test(unsigned Idx) const
std::pair< iterator, bool > insert(const ValueT &Val)
insert - Attempts to insert a new element.
const char * toString(DWARFSectionKind Kind)
@ PrefBoth
Block entry prefers both register and stack.
void addLink(unsigned b, BlockFrequency w)
addLink - Add a link to bundle b with weight w.
Branch Probability Basic Block Placement
void print(raw_ostream &OS) const
BorderConstraint Exit
Constraint on block exit.
size_t size() const
size - Get the array size.
ArrayRef< unsigned > getBlocks(unsigned Bundle) const
getBlocks - Return an array of blocks that are connected to Bundle.
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
uint64_t getEntryFreq() const
Divide a block's BlockFrequency::getFrequency() value by this value to obtain the entry block - relat...
LLVM Value Representation.
BlockConstraint - Entry and exit constraints for a basic block.
unsigned getBundle(unsigned N, bool Out) const
getBundle - Return the ingoing (Out = false) or outgoing (Out = true) bundle number for basic block N
BorderConstraint
BorderConstraint - A basic block has separate constraints for entry and exit.