X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FSpillPlacement.cpp;h=97a5424aa560c51eef3bef9b9aa710a4a7b4922b;hb=8a5eafb58d99f6aaf4e0fb4cf86c296f8ca7441e;hp=cf24a22d16e147c1cf2df572b56433ddd17c18f4;hpb=9590c7fbca2a3c18d0000676b2a6336f6458ed42;p=oota-llvm.git diff --git a/lib/CodeGen/SpillPlacement.cpp b/lib/CodeGen/SpillPlacement.cpp index cf24a22d16e..97a5424aa56 100644 --- a/lib/CodeGen/SpillPlacement.cpp +++ b/lib/CodeGen/SpillPlacement.cpp @@ -27,19 +27,22 @@ // //===----------------------------------------------------------------------===// -#define DEBUG_TYPE "spillplacement" #include "SpillPlacement.h" +#include "llvm/ADT/BitVector.h" #include "llvm/CodeGen/EdgeBundles.h" -#include "llvm/CodeGen/LiveIntervalAnalysis.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/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) @@ -52,6 +55,7 @@ char &llvm::SpillPlacementID = SpillPlacement::ID; void SpillPlacement::getAnalysisUsage(AnalysisUsage &AU) const { AU.setPreservesAll(); + AU.addRequired(); AU.addRequiredTransitive(); AU.addRequiredTransitive(); MachineFunctionPass::getAnalysisUsage(AU); @@ -67,31 +71,25 @@ void SpillPlacement::getAnalysisUsage(AnalysisUsage &AU) const { /// because all weights are positive. /// struct SpillPlacement::Node { - /// Frequency - Total 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]; - - /// Bias - Normalized contributions from non-transparent blocks. - /// A bundle connected to a MustSpill block has a huge negative bias, - /// otherwise it is a number in the range [-2;2]. - float Bias; + /// BiasN - Sum of blocks that prefer a spill. + BlockFrequency BiasN; + /// BiasP - Sum of blocks that prefer a register. + 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. - float Value; + /// 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, 4> LinkVector; + typedef SmallVector, 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. + BlockFrequency SumLinkWeights; + /// preferReg - Return true when this node prefers to be in a register. bool preferReg() const { // Undecided nodes (Value==0) go on the stack. @@ -100,28 +98,24 @@ struct SpillPlacement::Node { /// mustSpill - Return True if this node is so biased that it must spill. bool mustSpill() const { - // Actually, we must spill if Bias < sum(weights). - // It may be worth it to compute the weight sum here? - return Bias < -2.0f; - } - - /// Node - Create a blank Node. - Node() { - Frequency[0] = Frequency[1] = 0; + // We must spill if Bias < -sum(weights) or the MustSpill flag was set. + // BiasN is saturated when MustSpill is set, make sure this still returns + // true when the RHS saturates. Note that SumLinkWeights includes Threshold. + return BiasN >= BiasP + SumLinkWeights; } /// clear - Reset per-query data, but preserve frequencies that only depend on // the CFG. - void clear() { - Bias = Value = 0; + void clear(const BlockFrequency &Threshold) { + BiasN = BiasP = Value = 0; + SumLinkWeights = Threshold; Links.clear(); } /// addLink - Add a link to bundle b with weight w. - /// 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]; + void addLink(unsigned b, BlockFrequency w) { + // Update cached sum. + SumLinkWeights += w; // There can be multiple links to the same bundle, add them up. for (LinkVector::iterator I = Links.begin(), E = Links.end(); I != E; ++I) @@ -133,32 +127,48 @@ struct SpillPlacement::Node { Links.push_back(std::make_pair(w, b)); } - /// addBias - Bias this node from an ingoing[0] or outgoing[1] link. - void addBias(float w, bool out) { - // Normalize w relative to all connected blocks from that direction. - w /= Frequency[out]; - Bias += w; + /// addBias - Bias this node. + 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; + } } /// 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. - float Sum = Bias; - for (LinkVector::iterator I = Links.begin(), E = Links.end(); I != E; ++I) - Sum += I->first * nodes[I->second].Value; + 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; + } - // 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. - const float Thres = 1e-4f; + // bool Before = preferReg(); - if (Sum < -Thres) + if (SumN >= SumP + Threshold) Value = -1; - else if (Sum > Thres) + else if (SumP >= SumN + Threshold) Value = 1; else Value = 0; @@ -175,11 +185,12 @@ bool SpillPlacement::runOnMachineFunction(MachineFunction &mf) { nodes = new Node[bundles->getNumBundles()]; // Compute total ingoing and outgoing block frequencies for all bundles. + BlockFrequencies.resize(mf.getNumBlockIDs()); + MBFI = &getAnalysis(); + setThreshold(MBFI->getEntryFreq()); for (MachineFunction::iterator I = mf.begin(), E = mf.end(); I != E; ++I) { - float Freq = getBlockFrequency(I); unsigned Num = I->getNumber(); - nodes[bundles->getBundle(Num, 1)].Frequency[0] += Freq; - nodes[bundles->getBundle(Num, 0)].Frequency[1] += Freq; + BlockFrequencies[Num] = MBFI->getBlockFreq(I); } // We never change the function. @@ -188,7 +199,7 @@ bool SpillPlacement::runOnMachineFunction(MachineFunction &mf) { void SpillPlacement::releaseMemory() { delete[] nodes; - nodes = 0; + nodes = nullptr; } /// activate - mark node n as active if it wasn't already. @@ -196,71 +207,123 @@ void SpillPlacement::activate(unsigned n) { 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 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 = (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); +} -/// prepareNodes - Compute node biases and weights from a set of constraints. +/// addConstraints - Compute node biases and weights from a set of constraints. /// Set a bit in NodeMask for each active node. -void SpillPlacement:: -prepareNodes(const SmallVectorImpl &LiveBlocks) { - DEBUG(dbgs() << "Building Hopfield network from " << LiveBlocks.size() - << " constraint blocks:\n"); - for (SmallVectorImpl::const_iterator I = LiveBlocks.begin(), +void SpillPlacement::addConstraints(ArrayRef LiveBlocks) { + for (ArrayRef::iterator I = LiveBlocks.begin(), E = LiveBlocks.end(); I != E; ++I) { - MachineBasicBlock *MBB = MF->getBlockNumbered(I->Number); - float Freq = getBlockFrequency(MBB); - DEBUG(dbgs() << " BB#" << I->Number << format(", Freq = %.1f", Freq)); - - // Is this a transparent block? Link ingoing and outgoing bundles. - if (I->Entry == DontCare && I->Exit == DontCare) { - unsigned ib = bundles->getBundle(I->Number, 0); - unsigned ob = bundles->getBundle(I->Number, 1); - DEBUG(dbgs() << ", transparent EB#" << ib << " -> EB#" << ob << '\n'); - - // Ignore self-loops. - if (ib == ob) - continue; - activate(ib); - activate(ob); - nodes[ib].addLink(ob, Freq, 1); - nodes[ob].addLink(ib, Freq, 0); - continue; - } - - // This block is not transparent, but it can still add bias. - const float Bias[] = { - 0, // DontCare, - 1, // PrefReg, - -1, // PrefSpill - -HUGE_VALF // MustSpill - }; + BlockFrequency Freq = BlockFrequencies[I->Number]; // Live-in to block? if (I->Entry != DontCare) { unsigned ib = bundles->getBundle(I->Number, 0); activate(ib); - nodes[ib].addBias(Freq * Bias[I->Entry], 1); - DEBUG(dbgs() << format(", entry EB#%u %+.1f", ib, Freq * Bias[I->Entry])); + nodes[ib].addBias(Freq, I->Entry); } // Live-out from block? if (I->Exit != DontCare) { unsigned ob = bundles->getBundle(I->Number, 1); activate(ob); - nodes[ob].addBias(Freq * Bias[I->Exit], 0); - DEBUG(dbgs() << format(", exit EB#%u %+.1f", ob, Freq * Bias[I->Exit])); + nodes[ob].addBias(Freq, I->Exit); } + } +} + +/// addPrefSpill - Same as addConstraints(PrefSpill) +void SpillPlacement::addPrefSpill(ArrayRef Blocks, bool Strong) { + for (ArrayRef::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 Links) { + for (ArrayRef::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); - DEBUG(dbgs() << '\n'); + // Ignore self-loops. + 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); + // 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 &Linked) { - DEBUG(dbgs() << "Iterating over " << Linked.size() << " linked nodes:\n"); +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, Threshold); + if (Linked.empty()) return; @@ -271,85 +334,58 @@ void SpillPlacement::iterate(const SmallVectorImpl &Linked) { // 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::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; - bool C = nodes[n].update(nodes); - Changed |= C; - DEBUG(dbgs() << " \\EB#" << n << format(" = %+2.0f", nodes[n].Value) - << (C ? " *\n" : "\n")); + if (nodes[n].update(nodes, Threshold)) { + 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. Changed = false; for (SmallVectorImpl::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; - bool C = nodes[n].update(nodes); - Changed |= C; - DEBUG(dbgs() << " /EB#" << n << format(" = %+2.0f", nodes[n].Value) - << (C ? " *\n" : "\n")); + if (nodes[n].update(nodes, Threshold)) { + Changed = true; + if (nodes[n].preferReg()) + RecentPositive.push_back(n); + } } - if (!Changed) + if (!Changed || !RecentPositive.empty()) return; } } -bool -SpillPlacement::placeSpills(const SmallVectorImpl &LiveBlocks, - BitVector &RegBundles) { +void SpillPlacement::prepare(BitVector &RegBundles) { + Linked.clear(); + RecentPositive.clear(); // Reuse RegBundles as our ActiveNodes vector. ActiveNodes = &RegBundles; ActiveNodes->clear(); ActiveNodes->resize(bundles->getNumBundles()); +} - // Compute active nodes, links and biases. - prepareNodes(LiveBlocks); - - // Update all active nodes, and find the ones that are actually linked to - // something so their value may change when iterating. - DEBUG(dbgs() << "Network has " << RegBundles.count() << " active nodes:\n"); - SmallVector Linked; - for (int n = RegBundles.find_first(); n>=0; n = RegBundles.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); - - DEBUG({ - dbgs() << " EB#" << n << format(" = %+2.0f", nodes[n].Value) - << format(", Bias %+.2f", nodes[n].Bias) - << format(", Freq %.1f/%.1f", nodes[n].Frequency[0], - nodes[n].Frequency[1]); - for (unsigned i = 0, e = nodes[n].Links.size(); i != e; ++i) - dbgs() << format(", %.2f -> EB#%u", nodes[n].Links[i].first, - nodes[n].Links[i].second); - dbgs() << '\n'; - }); - } - - // Iterate the network to convergence. - iterate(Linked); +bool +SpillPlacement::finish() { + assert(ActiveNodes && "Call prepare() first"); - // Write preferences back to RegBundles. + // Write preferences back to ActiveNodes. bool Perfect = true; - for (int n = RegBundles.find_first(); n>=0; n = RegBundles.find_next(n)) + for (int n = ActiveNodes->find_first(); n>=0; n = ActiveNodes->find_next(n)) if (!nodes[n].preferReg()) { - RegBundles.reset(n); + ActiveNodes->reset(n); Perfect = false; } + ActiveNodes = nullptr; return Perfect; } - -/// getBlockFrequency - Return our best estimate of the block frequency which is -/// the expected number of block executions per function invocation. -float SpillPlacement::getBlockFrequency(const MachineBasicBlock *MBB) { - // Use the unnormalized spill weight for real block frequencies. - return LiveIntervals::getSpillWeight(true, false, loops->getLoopDepth(MBB)); -} -