50 #define DEBUG_TYPE "spill-code-placement" 57 "Spill Code Placement Analysis",
true,
true)
63 void SpillPlacement::getAnalysisUsage(
AnalysisUsage &AU)
const {
117 BiasN = BiasP = Value = 0;
118 SumLinkWeights = Threshold;
129 if (
I->second == b) {
161 if (nodes[
I->second].
Value == -1)
163 else if (nodes[
I->second].
Value == 1)
176 if (SumN >= SumP + Threshold)
178 else if (SumP >= SumN + Threshold)
186 const Node nodes[])
const {
187 for (
const auto &Elt : Links) {
188 unsigned n = Elt.second;
191 if (Value != nodes[n].Value)
199 bundles = &getAnalysis<EdgeBundles>();
200 loops = &getAnalysis<MachineLoopInfo>();
203 nodes =
new Node[bundles->getNumBundles()];
205 TodoList.setUniverse(bundles->getNumBundles());
209 MBFI = &getAnalysis<MachineBlockFrequencyInfo>();
210 setThreshold(MBFI->getEntryFreq());
212 unsigned Num =
I.getNumber();
213 BlockFrequencies[Num] = MBFI->getBlockFreq(&
I);
220 void SpillPlacement::releaseMemory() {
227 void SpillPlacement::activate(
unsigned n) {
229 if (ActiveNodes->test(n))
232 nodes[n].clear(Threshold);
243 if (bundles->getBlocks(n).size() > 100) {
245 nodes[n].BiasN = (MBFI->getEntryFreq() / 16);
258 uint64_t Scaled = (Freq >> 13) +
bool(Freq & (1 << 12));
259 Threshold =
std::max(UINT64_C(1), Scaled);
266 E = LiveBlocks.
end();
I !=
E; ++
I) {
271 unsigned ib = bundles->getBundle(
I->Number,
false);
278 unsigned ob = bundles->getBundle(
I->Number,
true);
280 nodes[ob].addBias(Freq,
I->Exit);
292 unsigned ib = bundles->getBundle(*
I,
false);
293 unsigned ob = bundles->getBundle(*
I,
true);
305 unsigned ib = bundles->getBundle(Number,
false);
306 unsigned ob = bundles->getBundle(Number,
true);
315 nodes[ob].addLink(ib, Freq);
320 RecentPositive.clear();
321 for (
unsigned n : ActiveNodes->set_bits()) {
328 RecentPositive.push_back(n);
330 return !RecentPositive.empty();
333 bool SpillPlacement::update(
unsigned n) {
336 nodes[n].getDissentingNeighbors(TodoList,
nodes);
345 RecentPositive.clear();
351 unsigned Limit = bundles->getNumBundles() * 10;
352 while(Limit-- > 0 && !TodoList.empty()) {
353 unsigned n = TodoList.pop_back_val();
357 RecentPositive.push_back(n);
362 RecentPositive.clear();
365 ActiveNodes = &RegBundles;
366 ActiveNodes->
clear();
367 ActiveNodes->resize(bundles->getNumBundles());
372 assert(ActiveNodes &&
"Call prepare() first");
376 for (
unsigned n : ActiveNodes->set_bits())
378 ActiveNodes->reset(n);
381 ActiveNodes =
nullptr;
int Value
Value - Output value of this node computed from the Bias and links.
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
This class represents lattice values for constants.
std::pair< iterator, bool > insert(const ValueT &Val)
insert - Attempts to insert a new element.
A register is impossible, variable must be spilled.
unsigned getNumBlockIDs() const
getNumBlockIDs - Return the number of MBB ID's allocated.
void push_back(const T &Elt)
Spill Code Placement true
uint64_t getFrequency() const
Returns the frequency as a fixpoint number scaled by the entry frequency.
MachineBlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate machine basic b...
BlockFrequency BiasP
BiasP - Sum of blocks that prefer a register.
bool preferReg() const
preferReg - Return true when this node prefers to be in a register.
#define INITIALIZE_PASS_DEPENDENCY(depName)
void clear()
clear - Removes all bits from the bitvector. Does not change capacity.
void addPrefSpill(ArrayRef< unsigned > Blocks, bool Strong)
addPrefSpill - Add PrefSpill constraints to all blocks listed.
bool scanActiveBundles()
scanActiveBundles - Perform an initial scan of all bundles activated by addConstraints and addLinks...
LinkVector Links
Links - (Weight, BundleNo) for all transparent blocks connecting to other bundles.
void iterate()
iterate - Update the network iteratively until convergence, or new bundles are found.
void getDissentingNeighbors(SparseSet< unsigned > &List, const Node nodes[]) const
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
BlockFrequency SumLinkWeights
SumLinkWeights - Cached sum of the weights of all links + ThresHold.
void addBias(BlockFrequency freq, BorderConstraint direction)
addBias - Bias this node.
char & SpillPlacementID
SpillPlacement analysis.
void addLinks(ArrayRef< unsigned > Links)
addLinks - Add transparent blocks with the given numbers.
Unify divergent function exit nodes
Block doesn't care / variable not live.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator begin()
void clear(const BlockFrequency &Threshold)
clear - Reset per-query data, but preserve frequencies that only depend on the CFG.
Represent the analysis usage information of a pass.
bool update(const Node nodes[], const BlockFrequency &Threshold)
update - Recompute Value from Bias and Links.
bool finish()
finish - Compute the optimal spill code placement given the constraints.
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
Block entry/exit prefers a register.
Branch Probability Basic Block Placement
void addConstraints(ArrayRef< BlockConstraint > LiveBlocks)
addConstraints - Add constraints and biases.
Block entry/exit prefers a stack slot.
bool mustSpill() const
mustSpill - Return True if this node is so biased that it must spill.
INITIALIZE_PASS_BEGIN(SpillPlacement, DEBUG_TYPE, "Spill Code Placement Analysis", true, true) INITIALIZE_PASS_END(SpillPlacement
void prepare(BitVector &RegBundles)
prepare - Reset state and prepare for a new spill placement computation.
void addLink(unsigned b, BlockFrequency w)
addLink - Add a link to bundle b with weight w.
typename SuperClass::iterator iterator
Node - Each edge bundle corresponds to a Hopfield node.
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator end()
static uint64_t getMaxFrequency()
Returns the maximum possible frequency, the saturation value.
BorderConstraint
BorderConstraint - A basic block has separate constraints for entry and exit.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Spill Code Placement Analysis
BlockFrequency BiasN
BiasN - Sum of blocks that prefer a spill.