SpillPlacement.cpp [plain text]
#include "SpillPlacement.h"
#include "llvm/ADT/BitVector.h"
#include "llvm/CodeGen/EdgeBundles.h"
#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineLoopInfo.h"
#include "llvm/CodeGen/Passes.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ManagedStatic.h"
using namespace llvm;
#define DEBUG_TYPE "spillplacement"
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.addRequired<MachineBlockFrequencyInfo>();
AU.addRequiredTransitive<EdgeBundles>();
AU.addRequiredTransitive<MachineLoopInfo>();
MachineFunctionPass::getAnalysisUsage(AU);
}
struct SpillPlacement::Node {
BlockFrequency BiasN;
BlockFrequency BiasP;
int Value;
typedef SmallVector<std::pair<BlockFrequency, unsigned>, 4> LinkVector;
LinkVector Links;
BlockFrequency SumLinkWeights;
bool preferReg() const {
return Value > 0;
}
bool mustSpill() const {
return BiasN >= BiasP + SumLinkWeights;
}
void clear(const BlockFrequency &Threshold) {
BiasN = BiasP = Value = 0;
SumLinkWeights = Threshold;
Links.clear();
}
void addLink(unsigned b, BlockFrequency w) {
SumLinkWeights += w;
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(BlockFrequency freq, BorderConstraint direction) {
switch (direction) {
default:
break;
case PrefReg:
BiasP += freq;
break;
case PrefSpill:
BiasN += freq;
break;
case MustSpill:
BiasN = BlockFrequency::getMaxFrequency();
break;
}
}
bool update(const Node nodes[], const BlockFrequency &Threshold) {
BlockFrequency SumN = BiasN;
BlockFrequency SumP = BiasP;
for (LinkVector::iterator I = Links.begin(), E = Links.end(); I != E; ++I) {
if (nodes[I->second].Value == -1)
SumN += I->first;
else if (nodes[I->second].Value == 1)
SumP += I->first;
}
bool Before = preferReg();
if (SumN >= SumP + Threshold)
Value = -1;
else if (SumP >= SumN + Threshold)
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()];
BlockFrequencies.resize(mf.getNumBlockIDs());
MBFI = &getAnalysis<MachineBlockFrequencyInfo>();
setThreshold(MBFI->getEntryFreq());
for (auto &I : mf) {
unsigned Num = I.getNumber();
BlockFrequencies[Num] = MBFI->getBlockFreq(&I);
}
return false;
}
void SpillPlacement::releaseMemory() {
delete[] nodes;
nodes = nullptr;
}
void SpillPlacement::activate(unsigned n) {
if (ActiveNodes->test(n))
return;
ActiveNodes->set(n);
nodes[n].clear(Threshold);
if (bundles->getBlocks(n).size() > 100) {
nodes[n].BiasP = 0;
nodes[n].BiasN = (MBFI->getEntryFreq() / 16);
}
}
void SpillPlacement::setThreshold(const BlockFrequency &Entry) {
uint64_t Freq = Entry.getFrequency();
uint64_t Scaled = (Freq >> 13) + bool(Freq & (1 << 12));
Threshold = std::max(UINT64_C(1), Scaled);
}
void SpillPlacement::addConstraints(ArrayRef<BlockConstraint> LiveBlocks) {
for (ArrayRef<BlockConstraint>::iterator I = LiveBlocks.begin(),
E = LiveBlocks.end(); I != E; ++I) {
BlockFrequency Freq = BlockFrequencies[I->Number];
if (I->Entry != DontCare) {
unsigned ib = bundles->getBundle(I->Number, 0);
activate(ib);
nodes[ib].addBias(Freq, I->Entry);
}
if (I->Exit != DontCare) {
unsigned ob = bundles->getBundle(I->Number, 1);
activate(ob);
nodes[ob].addBias(Freq, I->Exit);
}
}
}
void SpillPlacement::addPrefSpill(ArrayRef<unsigned> Blocks, bool Strong) {
for (ArrayRef<unsigned>::iterator I = Blocks.begin(), E = Blocks.end();
I != E; ++I) {
BlockFrequency Freq = BlockFrequencies[*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, PrefSpill);
nodes[ob].addBias(Freq, PrefSpill);
}
}
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);
BlockFrequency Freq = BlockFrequencies[Number];
nodes[ib].addLink(ob, Freq);
nodes[ob].addLink(ib, Freq);
}
}
bool SpillPlacement::scanActiveBundles() {
Linked.clear();
RecentPositive.clear();
for (int n = ActiveNodes->find_first(); n>=0; n = ActiveNodes->find_next(n)) {
nodes[n].update(nodes, Threshold);
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, Threshold);
if (Linked.empty())
return;
for (unsigned iteration = 0; iteration != 10; ++iteration) {
bool Changed = false;
for (SmallVectorImpl<unsigned>::const_reverse_iterator I =
iteration == 0 ? Linked.rbegin() : std::next(Linked.rbegin()),
E = Linked.rend(); I != E; ++I) {
unsigned n = *I;
if (nodes[n].update(nodes, Threshold)) {
Changed = true;
if (nodes[n].preferReg())
RecentPositive.push_back(n);
}
}
if (!Changed || !RecentPositive.empty())
return;
Changed = false;
for (SmallVectorImpl<unsigned>::const_iterator I =
std::next(Linked.begin()), E = Linked.end(); I != E; ++I) {
unsigned n = *I;
if (nodes[n].update(nodes, Threshold)) {
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 = nullptr;
return Perfect;
}