/// because all weights are positive.
///
struct SpillPlacement::Node {
- /// Frequency - Total block frequency feeding into[0] or out of[1] the bundle.
+ /// Scale - Inverse block frequency feeding into[0] or out of[1] the bundle.
/// Ideally, these two numbers should be identical, but inaccuracies in the
/// block frequency estimates means that we need to normalize ingoing and
/// outgoing frequencies separately so they are commensurate.
- float Frequency[2];
+ float Scale[2];
/// Bias - Normalized contributions from non-transparent blocks.
/// A bundle connected to a MustSpill block has a huge negative bias,
/// Node - Create a blank Node.
Node() {
- Frequency[0] = Frequency[1] = 0;
+ Scale[0] = Scale[1] = 0;
}
/// clear - Reset per-query data, but preserve frequencies that only depend on
/// out=0 for an ingoing link, and 1 for an outgoing link.
void addLink(unsigned b, float w, bool out) {
// Normalize w relative to all connected blocks from that direction.
- w /= Frequency[out];
+ w *= Scale[out];
// There can be multiple links to the same bundle, add them up.
for (LinkVector::iterator I = Links.begin(), E = Links.end(); I != E; ++I)
/// addBias - Bias this node from an ingoing[0] or outgoing[1] link.
/// Return the change to the total number of positive biases.
- int addBias(float w, bool out) {
+ void addBias(float w, bool out) {
// Normalize w relative to all connected blocks from that direction.
- w /= Frequency[out];
- int Before = Bias > 0;
+ w *= Scale[out];
Bias += w;
- int After = Bias > 0;
- return After - Before;
}
/// update - Recompute Value from Bias and Links. Return true when node
loops->getLoopDepth(I));
unsigned Num = I->getNumber();
BlockFrequency[Num] = Freq;
- nodes[bundles->getBundle(Num, 1)].Frequency[0] += Freq;
- nodes[bundles->getBundle(Num, 0)].Frequency[1] += Freq;
+ nodes[bundles->getBundle(Num, 1)].Scale[0] += Freq;
+ nodes[bundles->getBundle(Num, 0)].Scale[1] += Freq;
}
+ // Scales are reciprocal frequencies.
+ for (unsigned i = 0, e = bundles->getNumBundles(); i != e; ++i)
+ for (unsigned d = 0; d != 2; ++d)
+ if (nodes[i].Scale[d] > 0)
+ nodes[i].Scale[d] = 1 / nodes[i].Scale[d];
+
// We never change the function.
return false;
}
0, // DontCare,
1, // PrefReg,
-1, // PrefSpill
+ 0, // PrefBoth
-HUGE_VALF // MustSpill
};
if (I->Entry != DontCare) {
unsigned ib = bundles->getBundle(I->Number, 0);
activate(ib);
- PositiveNodes += nodes[ib].addBias(Freq * Bias[I->Entry], 1);
+ nodes[ib].addBias(Freq * Bias[I->Entry], 1);
}
// Live-out from block?
if (I->Exit != DontCare) {
unsigned ob = bundles->getBundle(I->Number, 1);
activate(ob);
- PositiveNodes += nodes[ob].addBias(Freq * Bias[I->Exit], 0);
+ nodes[ob].addBias(Freq * Bias[I->Exit], 0);
}
}
}
+/// addPrefSpill - Same as addConstraints(PrefSpill)
+void SpillPlacement::addPrefSpill(ArrayRef<unsigned> Blocks, bool Strong) {
+ for (ArrayRef<unsigned>::iterator I = Blocks.begin(), E = Blocks.end();
+ I != E; ++I) {
+ float Freq = getBlockFrequency(*I);
+ if (Strong)
+ Freq += Freq;
+ unsigned ib = bundles->getBundle(*I, 0);
+ unsigned ob = bundles->getBundle(*I, 1);
+ activate(ib);
+ activate(ob);
+ nodes[ib].addBias(-Freq, 1);
+ nodes[ob].addBias(-Freq, 0);
+ }
+}
+
void SpillPlacement::addLinks(ArrayRef<unsigned> Links) {
for (ArrayRef<unsigned>::iterator I = Links.begin(), E = Links.end(); I != E;
++I) {
continue;
activate(ib);
activate(ob);
+ if (nodes[ib].Links.empty() && !nodes[ib].mustSpill())
+ Linked.push_back(ib);
+ if (nodes[ob].Links.empty() && !nodes[ob].mustSpill())
+ Linked.push_back(ob);
float Freq = getBlockFrequency(Number);
nodes[ib].addLink(ob, Freq, 1);
nodes[ob].addLink(ib, Freq, 0);
}
}
+bool SpillPlacement::scanActiveBundles() {
+ Linked.clear();
+ RecentPositive.clear();
+ for (int n = ActiveNodes->find_first(); n>=0; n = ActiveNodes->find_next(n)) {
+ nodes[n].update(nodes);
+ // A node that must spill, or a node without any links is not going to
+ // change its value ever again, so exclude it from iterations.
+ if (nodes[n].mustSpill())
+ continue;
+ if (!nodes[n].Links.empty())
+ Linked.push_back(n);
+ if (nodes[n].preferReg())
+ RecentPositive.push_back(n);
+ }
+ return !RecentPositive.empty();
+}
+
/// iterate - Repeatedly update the Hopfield nodes until stability or the
/// maximum number of iterations is reached.
/// @param Linked - Numbers of linked nodes that need updating.
-void SpillPlacement::iterate(const SmallVectorImpl<unsigned> &Linked) {
+void SpillPlacement::iterate() {
+ // First update the recently positive nodes. They have likely received new
+ // negative bias that will turn them off.
+ while (!RecentPositive.empty())
+ nodes[RecentPositive.pop_back_val()].update(nodes);
+
if (Linked.empty())
return;
for (SmallVectorImpl<unsigned>::const_reverse_iterator I =
llvm::next(Linked.rbegin()), E = Linked.rend(); I != E; ++I) {
unsigned n = *I;
- bool C = nodes[n].update(nodes);
- Changed |= C;
+ if (nodes[n].update(nodes)) {
+ Changed = true;
+ if (nodes[n].preferReg())
+ RecentPositive.push_back(n);
+ }
}
- if (!Changed)
+ if (!Changed || !RecentPositive.empty())
return;
// Scan forwards, skipping the first node which was just updated.
for (SmallVectorImpl<unsigned>::const_iterator I =
llvm::next(Linked.begin()), E = Linked.end(); I != E; ++I) {
unsigned n = *I;
- bool C = nodes[n].update(nodes);
- Changed |= C;
+ if (nodes[n].update(nodes)) {
+ Changed = true;
+ if (nodes[n].preferReg())
+ RecentPositive.push_back(n);
+ }
}
- if (!Changed)
+ if (!Changed || !RecentPositive.empty())
return;
}
}
void SpillPlacement::prepare(BitVector &RegBundles) {
+ Linked.clear();
+ RecentPositive.clear();
// Reuse RegBundles as our ActiveNodes vector.
ActiveNodes = &RegBundles;
ActiveNodes->clear();
ActiveNodes->resize(bundles->getNumBundles());
- PositiveNodes = 0;
}
bool
SpillPlacement::finish() {
assert(ActiveNodes && "Call prepare() first");
- // Update all active nodes, and find the ones that are actually linked to
- // something so their value may change when iterating.
- SmallVector<unsigned, 8> Linked;
- for (int n = ActiveNodes->find_first(); n>=0; n = ActiveNodes->find_next(n)) {
- nodes[n].update(nodes);
- // A node that must spill, or a node without any links is not going to
- // change its value ever again, so exclude it from iterations.
- if (!nodes[n].Links.empty() && !nodes[n].mustSpill())
- Linked.push_back(n);
- }
-
- // Iterate the network to convergence.
- iterate(Linked);
// Write preferences back to ActiveNodes.
bool Perfect = true;
projects / oota-llvm.git / blobdiff