//
//===----------------------------------------------------------------------===//
-#define DEBUG_TYPE "spillplacement"
#include "SpillPlacement.h"
#include "llvm/ADT/BitVector.h"
#include "llvm/CodeGen/EdgeBundles.h"
#include "llvm/CodeGen/MachineLoopInfo.h"
#include "llvm/CodeGen/Passes.h"
#include "llvm/Support/Debug.h"
-#include "llvm/Support/Format.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)
MachineFunctionPass::getAnalysisUsage(AU);
}
-/// Decision threshold. A node gets the output value 0 if the weighted sum of
-/// its inputs falls in the open interval (-Threshold;Threshold).
-static const BlockFrequency Threshold = 2;
-
/// Node - Each edge bundle corresponds to a Hopfield node.
///
/// The node contains precomputed frequency data that only depends on the CFG,
BlockFrequency BiasP;
/// Value - Output value of this node computed from the Bias and links.
- /// This is always in the range [-1;1]. A positive number means the variable
- /// should go in a register through this bundle.
+ /// This is always on of the values {-1, 0, 1}. A positive number means the
+ /// variable should go in a register through this bundle.
int Value;
typedef SmallVector<std::pair<BlockFrequency, unsigned>, 4> LinkVector;
/// Links - (Weight, BundleNo) for all transparent blocks connecting to other
- /// bundles. The weights are all positive and add up to at most 2, weights
- /// from ingoing and outgoing nodes separately add up to a most 1. The weight
- /// sum can be less than 2 when the variable is not live into / out of some
- /// connected basic blocks.
+ /// bundles. The weights are all positive block frequencies.
LinkVector Links;
/// SumLinkWeights - Cached sum of the weights of all links + ThresHold.
/// clear - Reset per-query data, but preserve frequencies that only depend on
// the CFG.
- void clear() {
+ void clear(const BlockFrequency &Threshold) {
BiasN = BiasP = Value = 0;
SumLinkWeights = Threshold;
Links.clear();
/// update - Recompute Value from Bias and Links. Return true when node
/// preference changes.
- bool update(const Node nodes[]) {
+ bool update(const Node nodes[], const BlockFrequency &Threshold) {
// Compute the weighted sum of inputs.
BlockFrequency SumN = BiasN;
BlockFrequency SumP = BiasP;
SumP += I->first;
}
- // The weighted sum is going to be in the range [-2;2]. Ideally, we should
- // simply set Value = sign(Sum), but we will add a dead zone around 0 for
- // two reasons:
+ // Each weighted sum is going to be less than the total frequency of the
+ // bundle. Ideally, we should simply set Value = sign(SumP - SumN), but we
+ // will add a dead zone around 0 for two reasons:
+ //
// 1. It avoids arbitrary bias when all links are 0 as is possible during
// initial iterations.
// 2. It helps tame rounding errors when the links nominally sum to 0.
+ //
bool Before = preferReg();
if (SumN >= SumP + Threshold)
Value = -1;
// Compute total ingoing and outgoing block frequencies for all bundles.
BlockFrequencies.resize(mf.getNumBlockIDs());
- MachineBlockFrequencyInfo &MBFI = getAnalysis<MachineBlockFrequencyInfo>();
- for (MachineFunction::iterator I = mf.begin(), E = mf.end(); I != E; ++I) {
- unsigned Num = I->getNumber();
- BlockFrequencies[Num] = MBFI.getBlockFreq(I);
+ MBFI = &getAnalysis<MachineBlockFrequencyInfo>();
+ setThreshold(MBFI->getEntryFreq());
+ for (auto &I : mf) {
+ unsigned Num = I.getNumber();
+ BlockFrequencies[Num] = MBFI->getBlockFreq(&I);
}
// We never change the function.
void SpillPlacement::releaseMemory() {
delete[] nodes;
- nodes = 0;
+ nodes = nullptr;
}
/// activate - mark node n as active if it wasn't already.
if (ActiveNodes->test(n))
return;
ActiveNodes->set(n);
- nodes[n].clear();
+ nodes[n].clear(Threshold);
// Very large bundles usually come from big switches, indirect branches,
// landing pads, or loops with many 'continue' statements. It is difficult to
// allocate registers when so many different blocks are involved.
//
- // Give a small negative bias to large bundles such that 1/32 of the
- // connected blocks need to be interested before we consider expanding the
- // region through the bundle. This helps compile time by limiting the number
- // of blocks visited and the number of links in the Hopfield network.
+ // Give a small negative bias to large bundles such that a substantial
+ // fraction of the connected blocks need to be interested before we consider
+ // expanding the region through the bundle. This helps compile time by
+ // limiting the number of blocks visited and the number of links in the
+ // Hopfield network.
if (bundles->getBlocks(n).size() > 100) {
nodes[n].BiasP = 0;
- nodes[n].BiasN = (BlockFrequency::getEntryFrequency() / 16);
+ nodes[n].BiasN = (MBFI->getEntryFreq() / 16);
}
}
+/// \brief Set the threshold for a given entry frequency.
+///
+/// Set the threshold relative to \c Entry. Since the threshold is used as a
+/// bound on the open interval (-Threshold;Threshold), 1 is the minimum
+/// threshold.
+void SpillPlacement::setThreshold(const BlockFrequency &Entry) {
+ // Apparently 2 is a good threshold when Entry==2^14, but we need to scale
+ // it. Divide by 2^13, rounding as appropriate.
+ uint64_t Freq = Entry.getFrequency();
+ uint64_t Scaled = (Freq >> 13) + bool(Freq & (1 << 12));
+ Threshold = std::max(UINT64_C(1), Scaled);
+}
/// addConstraints - Compute node biases and weights from a set of constraints.
/// Set a bit in NodeMask for each active node.
Linked.clear();
RecentPositive.clear();
for (int n = ActiveNodes->find_first(); n>=0; n = ActiveNodes->find_next(n)) {
- nodes[n].update(nodes);
+ nodes[n].update(nodes, Threshold);
// 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())
// 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);
+ nodes[RecentPositive.pop_back_val()].update(nodes, Threshold);
if (Linked.empty())
return;
// affect the entire network in a single iteration. That means very fast
// convergence, usually in a single iteration.
for (unsigned iteration = 0; iteration != 10; ++iteration) {
- // Scan backwards, skipping the last node which was just updated.
+ // Scan backwards, skipping the last node when iteration is not zero. When
+ // iteration is not zero, the last node was just updated.
bool Changed = false;
for (SmallVectorImpl<unsigned>::const_reverse_iterator I =
- llvm::next(Linked.rbegin()), E = Linked.rend(); I != E; ++I) {
+ iteration == 0 ? Linked.rbegin() : std::next(Linked.rbegin()),
+ E = Linked.rend(); I != E; ++I) {
unsigned n = *I;
- if (nodes[n].update(nodes)) {
+ if (nodes[n].update(nodes, Threshold)) {
Changed = true;
if (nodes[n].preferReg())
RecentPositive.push_back(n);
// Scan forwards, skipping the first node which was just updated.
Changed = false;
for (SmallVectorImpl<unsigned>::const_iterator I =
- llvm::next(Linked.begin()), E = Linked.end(); I != E; ++I) {
+ std::next(Linked.begin()), E = Linked.end(); I != E; ++I) {
unsigned n = *I;
- if (nodes[n].update(nodes)) {
+ if (nodes[n].update(nodes, Threshold)) {
Changed = true;
if (nodes[n].preferReg())
RecentPositive.push_back(n);
ActiveNodes->reset(n);
Perfect = false;
}
- ActiveNodes = 0;
+ ActiveNodes = nullptr;
return Perfect;
}