SpillPlacement.cpp [plain text]
#define DEBUG_TYPE "spillplacement"
#include "SpillPlacement.h"
#include "llvm/CodeGen/EdgeBundles.h"
#include "llvm/CodeGen/LiveIntervalAnalysis.h"
#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineLoopInfo.h"
#include "llvm/CodeGen/Passes.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/Format.h"
using namespace llvm;
char SpillPlacement::ID = 0;
INITIALIZE_PASS_BEGIN(SpillPlacement, "spill-code-placement",
"Spill Code Placement Analysis", true, true)
INITIALIZE_PASS_DEPENDENCY(EdgeBundles)
INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
INITIALIZE_PASS_END(SpillPlacement, "spill-code-placement",
"Spill Code Placement Analysis", true, true)
char &llvm::SpillPlacementID = SpillPlacement::ID;
void SpillPlacement::getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesAll();
AU.addRequiredTransitive<EdgeBundles>();
AU.addRequiredTransitive<MachineLoopInfo>();
MachineFunctionPass::getAnalysisUsage(AU);
}
struct SpillPlacement::Node {
float Scale[2];
float Bias;
float Value;
typedef SmallVector<std::pair<float, unsigned>, 4> LinkVector;
LinkVector Links;
bool preferReg() const {
return Value > 0;
}
bool mustSpill() const {
return Bias < -2.0f;
}
Node() {
Scale[0] = Scale[1] = 0;
}
void clear() {
Bias = Value = 0;
Links.clear();
}
void addLink(unsigned b, float w, bool out) {
w *= Scale[out];
for (LinkVector::iterator I = Links.begin(), E = Links.end(); I != E; ++I)
if (I->second == b) {
I->first += w;
return;
}
Links.push_back(std::make_pair(w, b));
}
void addBias(float w, bool out) {
w *= Scale[out];
Bias += w;
}
bool update(const Node nodes[]) {
float Sum = Bias;
for (LinkVector::iterator I = Links.begin(), E = Links.end(); I != E; ++I)
Sum += I->first * nodes[I->second].Value;
const float Thres = 1e-4f;
bool Before = preferReg();
if (Sum < -Thres)
Value = -1;
else if (Sum > Thres)
Value = 1;
else
Value = 0;
return Before != preferReg();
}
};
bool SpillPlacement::runOnMachineFunction(MachineFunction &mf) {
MF = &mf;
bundles = &getAnalysis<EdgeBundles>();
loops = &getAnalysis<MachineLoopInfo>();
assert(!nodes && "Leaking node array");
nodes = new Node[bundles->getNumBundles()];
BlockFrequency.resize(mf.getNumBlockIDs());
for (MachineFunction::iterator I = mf.begin(), E = mf.end(); I != E; ++I) {
float Freq = LiveIntervals::getSpillWeight(true, false,
loops->getLoopDepth(I));
unsigned Num = I->getNumber();
BlockFrequency[Num] = Freq;
nodes[bundles->getBundle(Num, 1)].Scale[0] += Freq;
nodes[bundles->getBundle(Num, 0)].Scale[1] += Freq;
}
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];
return false;
}
void SpillPlacement::releaseMemory() {
delete[] nodes;
nodes = 0;
}
void SpillPlacement::activate(unsigned n) {
if (ActiveNodes->test(n))
return;
ActiveNodes->set(n);
nodes[n].clear();
if (bundles->getBlocks(n).size() > 100)
nodes[n].Bias = -0.0625f;
}
void SpillPlacement::addConstraints(ArrayRef<BlockConstraint> LiveBlocks) {
for (ArrayRef<BlockConstraint>::iterator I = LiveBlocks.begin(),
E = LiveBlocks.end(); I != E; ++I) {
float Freq = getBlockFrequency(I->Number);
const float Bias[] = {
0, 1, -1, 0, -HUGE_VALF };
if (I->Entry != DontCare) {
unsigned ib = bundles->getBundle(I->Number, 0);
activate(ib);
nodes[ib].addBias(Freq * Bias[I->Entry], 1);
}
if (I->Exit != DontCare) {
unsigned ob = bundles->getBundle(I->Number, 1);
activate(ob);
nodes[ob].addBias(Freq * Bias[I->Exit], 0);
}
}
}
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) {
unsigned Number = *I;
unsigned ib = bundles->getBundle(Number, 0);
unsigned ob = bundles->getBundle(Number, 1);
if (ib == ob)
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);
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();
}
void SpillPlacement::iterate() {
while (!RecentPositive.empty())
nodes[RecentPositive.pop_back_val()].update(nodes);
if (Linked.empty())
return;
for (unsigned iteration = 0; iteration != 10; ++iteration) {
bool Changed = false;
for (SmallVectorImpl<unsigned>::const_reverse_iterator I =
llvm::next(Linked.rbegin()), E = Linked.rend(); I != E; ++I) {
unsigned n = *I;
if (nodes[n].update(nodes)) {
Changed = true;
if (nodes[n].preferReg())
RecentPositive.push_back(n);
}
}
if (!Changed || !RecentPositive.empty())
return;
Changed = false;
for (SmallVectorImpl<unsigned>::const_iterator I =
llvm::next(Linked.begin()), E = Linked.end(); I != E; ++I) {
unsigned n = *I;
if (nodes[n].update(nodes)) {
Changed = true;
if (nodes[n].preferReg())
RecentPositive.push_back(n);
}
}
if (!Changed || !RecentPositive.empty())
return;
}
}
void SpillPlacement::prepare(BitVector &RegBundles) {
Linked.clear();
RecentPositive.clear();
ActiveNodes = &RegBundles;
ActiveNodes->clear();
ActiveNodes->resize(bundles->getNumBundles());
}
bool
SpillPlacement::finish() {
assert(ActiveNodes && "Call prepare() first");
bool Perfect = true;
for (int n = ActiveNodes->find_first(); n>=0; n = ActiveNodes->find_next(n))
if (!nodes[n].preferReg()) {
ActiveNodes->reset(n);
Perfect = false;
}
ActiveNodes = 0;
return Perfect;
}