From 92879a8cb1490c90bf952a17a110dc45063832b0 Mon Sep 17 00:00:00 2001 From: Jakob Stoklund Olesen Date: Tue, 2 Jul 2013 17:31:58 +0000 Subject: [PATCH] Revert (most of) r185393 and r185395. "Remove floating point computations form SpillPlacement.cpp." These commits caused test failures in lencod on clang-native-arm-lnt. I suspect these changes are only exposing an existing issue, but reverting anyway to keep the bots passing while we investigate. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@185447 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/SpillPlacement.cpp | 155 +++++++++++++++++---------------- lib/CodeGen/SpillPlacement.h | 7 +- 2 files changed, 82 insertions(+), 80 deletions(-) diff --git a/lib/CodeGen/SpillPlacement.cpp b/lib/CodeGen/SpillPlacement.cpp index 10a93b7fa4d..840f05b9ff4 100644 --- a/lib/CodeGen/SpillPlacement.cpp +++ b/lib/CodeGen/SpillPlacement.cpp @@ -59,10 +59,6 @@ void SpillPlacement::getAnalysisUsage(AnalysisUsage &AU) const { 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, @@ -73,25 +69,31 @@ static const BlockFrequency Threshold = 2; /// because all weights are positive. /// struct SpillPlacement::Node { - /// BiasN - Sum of blocks that prefer a spill. - BlockFrequency BiasN; - /// BiasP - Sum of blocks that prefer a register. - BlockFrequency BiasP; + /// 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 Scale[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; /// Value - Output value of this node computed from the Bias and links. - /// 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; + /// This is always in the range [-1;1]. A positive number means the variable + /// should go in a register through this bundle. + float 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 block frequencies. + /// 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. 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,24 +102,28 @@ struct SpillPlacement::Node { /// mustSpill - Return True if this node is so biased that it must spill. bool mustSpill() const { - // 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; + // 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() { + Scale[0] = Scale[1] = 0; } /// clear - Reset per-query data, but preserve frequencies that only depend on // the CFG. void clear() { - BiasN = BiasP = Value = 0; - SumLinkWeights = Threshold; + Bias = Value = 0; Links.clear(); } /// addLink - Add a link to bundle b with weight w. - void addLink(unsigned b, BlockFrequency w) { - // Update cached sum. - SumLinkWeights += 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 *= 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) @@ -129,48 +135,33 @@ struct SpillPlacement::Node { Links.push_back(std::make_pair(w, b)); } - /// 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; - } + /// addBias - Bias this node from an ingoing[0] or outgoing[1] link. + /// Return the change to the total number of positive biases. + void addBias(float w, bool out) { + // Normalize w relative to all connected blocks from that direction. + w *= Scale[out]; + Bias += w; } /// update - Recompute Value from Bias and Links. Return true when node /// preference changes. bool update(const Node nodes[]) { // Compute the weighted sum of inputs. - 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; - } + float Sum = Bias; + for (LinkVector::iterator I = Links.begin(), E = Links.end(); I != E; ++I) + Sum += I->first * nodes[I->second].Value; - // 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: - // + // 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: // 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 (SumN >= SumP + Threshold) + if (Sum < -Thres) Value = -1; - else if (SumP >= SumN + Threshold) + else if (Sum > Thres) Value = 1; else Value = 0; @@ -187,13 +178,23 @@ bool SpillPlacement::runOnMachineFunction(MachineFunction &mf) { nodes = new Node[bundles->getNumBundles()]; // Compute total ingoing and outgoing block frequencies for all bundles. - BlockFrequencies.resize(mf.getNumBlockIDs()); + BlockFrequency.resize(mf.getNumBlockIDs()); MachineBlockFrequencyInfo &MBFI = getAnalysis(); + float EntryFreq = BlockFrequency::getEntryFrequency(); for (MachineFunction::iterator I = mf.begin(), E = mf.end(); I != E; ++I) { + float Freq = MBFI.getBlockFreq(I).getFrequency() / EntryFreq; unsigned Num = I->getNumber(); - BlockFrequencies[Num] = MBFI.getBlockFreq(I); + BlockFrequency[Num] = 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; } @@ -214,15 +215,12 @@ void SpillPlacement::activate(unsigned n) { // 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 = (BlockFrequency::getEntryFrequency() / 16); - } + // 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. + if (bundles->getBlocks(n).size() > 100) + nodes[n].Bias = -0.0625f; } @@ -231,20 +229,27 @@ void SpillPlacement::activate(unsigned n) { void SpillPlacement::addConstraints(ArrayRef LiveBlocks) { for (ArrayRef::iterator I = LiveBlocks.begin(), E = LiveBlocks.end(); I != E; ++I) { - BlockFrequency Freq = BlockFrequencies[I->Number]; + float Freq = getBlockFrequency(I->Number); + const float Bias[] = { + 0, // DontCare, + 1, // PrefReg, + -1, // PrefSpill + 0, // PrefBoth + -HUGE_VALF // MustSpill + }; // Live-in to block? if (I->Entry != DontCare) { unsigned ib = bundles->getBundle(I->Number, 0); activate(ib); - nodes[ib].addBias(Freq, I->Entry); + 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); - nodes[ob].addBias(Freq, I->Exit); + nodes[ob].addBias(Freq * Bias[I->Exit], 0); } } } @@ -253,15 +258,15 @@ void SpillPlacement::addConstraints(ArrayRef LiveBlocks) { void SpillPlacement::addPrefSpill(ArrayRef Blocks, bool Strong) { for (ArrayRef::iterator I = Blocks.begin(), E = Blocks.end(); I != E; ++I) { - BlockFrequency Freq = BlockFrequencies[*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, PrefSpill); - nodes[ob].addBias(Freq, PrefSpill); + nodes[ib].addBias(-Freq, 1); + nodes[ob].addBias(-Freq, 0); } } @@ -281,9 +286,9 @@ void SpillPlacement::addLinks(ArrayRef Links) { 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); + float Freq = getBlockFrequency(Number); + nodes[ib].addLink(ob, Freq, 1); + nodes[ob].addLink(ib, Freq, 0); } } diff --git a/lib/CodeGen/SpillPlacement.h b/lib/CodeGen/SpillPlacement.h index a0480d587d6..fc412f817cd 100644 --- a/lib/CodeGen/SpillPlacement.h +++ b/lib/CodeGen/SpillPlacement.h @@ -30,7 +30,6 @@ #include "llvm/ADT/ArrayRef.h" #include "llvm/ADT/SmallVector.h" #include "llvm/CodeGen/MachineFunctionPass.h" -#include "llvm/Support/BlockFrequency.h" namespace llvm { @@ -58,7 +57,7 @@ class SpillPlacement : public MachineFunctionPass { SmallVector RecentPositive; // Block frequencies are computed once. Indexed by block number. - SmallVector BlockFrequencies; + SmallVector BlockFrequency; public: static char ID; // Pass identification, replacement for typeid. @@ -141,9 +140,7 @@ public: /// getBlockFrequency - Return the estimated block execution frequency per /// function invocation. float getBlockFrequency(unsigned Number) const { - // FIXME: Return the BlockFrequency directly. - const float Scale = 1.0f / BlockFrequency::getEntryFrequency(); - return BlockFrequencies[Number].getFrequency() * Scale; + return BlockFrequency[Number]; } private: -- 2.34.1