SpillPlacement.cpp revision dce4a407a24b04eebc6a376f8e62b41aaa7b071f
16e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)//===-- SpillPlacement.cpp - Optimal Spill Code Placement -----------------===// 26e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)// 36e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)// The LLVM Compiler Infrastructure 46e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)// 56e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)// This file is distributed under the University of Illinois Open Source 66e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)// License. See LICENSE.TXT for details. 76e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)// 81320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci//===----------------------------------------------------------------------===// 96e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)// 106e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)// This file implements the spill code placement analysis. 116e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)// 126e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)// Each edge bundle corresponds to a node in a Hopfield network. Constraints on 136e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)// basic blocks are weighted by the block frequency and added to become the node 146e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)// bias. 156e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)// 166e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)// Transparent basic blocks have the variable live through, but don't care if it 176e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)// is spilled or in a register. These blocks become connections in the Hopfield 186e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)// network, again weighted by block frequency. 196e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)// 206e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)// The Hopfield network minimizes (possibly locally) its energy function: 216e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)// 226e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)// E = -sum_n V_n * ( B_n + sum_{n, m linked by b} V_m * F_b ) 236e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)// 246e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)// The energy function represents the expected spill code execution frequency, 256e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)// or the cost of spilling. This is a Lyapunov function which never increases 266e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)// when a node is updated. It is guaranteed to converge to a local minimum. 271320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci// 286e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)//===----------------------------------------------------------------------===// 291320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 306e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)#include "SpillPlacement.h" 311320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci#include "llvm/ADT/BitVector.h" 326e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)#include "llvm/CodeGen/EdgeBundles.h" 331320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci#include "llvm/CodeGen/MachineBasicBlock.h" 346e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)#include "llvm/CodeGen/MachineBlockFrequencyInfo.h" 356e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)#include "llvm/CodeGen/MachineFunction.h" 366e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)#include "llvm/CodeGen/MachineLoopInfo.h" 371320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci#include "llvm/CodeGen/Passes.h" 381320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci#include "llvm/Support/Debug.h" 391320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci#include "llvm/Support/Format.h" 406e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) 411320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucciusing namespace llvm; 426e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) 436e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)#define DEBUG_TYPE "spillplacement" 441320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 456e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)char SpillPlacement::ID = 0; 466e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)INITIALIZE_PASS_BEGIN(SpillPlacement, "spill-code-placement", 476e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) "Spill Code Placement Analysis", true, true) 486e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)INITIALIZE_PASS_DEPENDENCY(EdgeBundles) 496e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) 506e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)INITIALIZE_PASS_END(SpillPlacement, "spill-code-placement", 516e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) "Spill Code Placement Analysis", true, true) 521320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 531320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tuccichar &llvm::SpillPlacementID = SpillPlacement::ID; 541320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 551320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tuccivoid SpillPlacement::getAnalysisUsage(AnalysisUsage &AU) const { 566e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) AU.setPreservesAll(); 576e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) AU.addRequired<MachineBlockFrequencyInfo>(); 586e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) AU.addRequiredTransitive<EdgeBundles>(); 596e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) AU.addRequiredTransitive<MachineLoopInfo>(); 606e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) MachineFunctionPass::getAnalysisUsage(AU); 616e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)} 626e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) 636e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)namespace { 646e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)static BlockFrequency Threshold; 656e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)} 666e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) 676e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)/// Decision threshold. A node gets the output value 0 if the weighted sum of 6803b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles)/// its inputs falls in the open interval (-Threshold;Threshold). 696e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)static BlockFrequency getThreshold() { return Threshold; } 706e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) 716e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)/// \brief Set the threshold for a given entry frequency. 726e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)/// 736e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)/// Set the threshold relative to \c Entry. Since the threshold is used as a 746e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)/// bound on the open interval (-Threshold;Threshold), 1 is the minimum 751320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci/// threshold. 761320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tuccistatic void setThreshold(const BlockFrequency &Entry) { 771320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci // Apparently 2 is a good threshold when Entry==2^14, but we need to scale 781320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci // it. Divide by 2^13, rounding as appropriate. 791320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci uint64_t Freq = Entry.getFrequency(); 801320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci uint64_t Scaled = (Freq >> 13) + bool(Freq & (1 << 12)); 811320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci Threshold = std::max(UINT64_C(1), Scaled); 821320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci} 831320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 841320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci/// Node - Each edge bundle corresponds to a Hopfield node. 856e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)/// 866e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)/// The node contains precomputed frequency data that only depends on the CFG, 876e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)/// but Bias and Links are computed each time placeSpills is called. 886e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)/// 896e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)/// The node Value is positive when the variable should be in a register. The 906e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)/// value can change when linked nodes change, but convergence is very fast 916e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)/// because all weights are positive. 926e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)/// 936e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)struct SpillPlacement::Node { 941320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci /// BiasN - Sum of blocks that prefer a spill. 951320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci BlockFrequency BiasN; 966e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) /// BiasP - Sum of blocks that prefer a register. 976e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) BlockFrequency BiasP; 986e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) 996e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) /// Value - Output value of this node computed from the Bias and links. 1006e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) /// This is always on of the values {-1, 0, 1}. A positive number means the 1016e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) /// variable should go in a register through this bundle. 1026e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) int Value; 1036e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) 1046e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) typedef SmallVector<std::pair<BlockFrequency, unsigned>, 4> LinkVector; 1056e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) 1066e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) /// Links - (Weight, BundleNo) for all transparent blocks connecting to other 1071320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci /// bundles. The weights are all positive block frequencies. 1081320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci LinkVector Links; 1096e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) 1106e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) /// SumLinkWeights - Cached sum of the weights of all links + ThresHold. 1116e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) BlockFrequency SumLinkWeights; 1126e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) 1136e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) /// preferReg - Return true when this node prefers to be in a register. 1146e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) bool preferReg() const { 1156e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) // Undecided nodes (Value==0) go on the stack. 1166e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) return Value > 0; 1176e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) } 1186e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) 1196e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) /// mustSpill - Return True if this node is so biased that it must spill. 1201320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci bool mustSpill() const { 1211320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci // We must spill if Bias < -sum(weights) or the MustSpill flag was set. 1226e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) // BiasN is saturated when MustSpill is set, make sure this still returns 1236e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) // true when the RHS saturates. Note that SumLinkWeights includes Threshold. 1246e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) return BiasN >= BiasP + SumLinkWeights; 1256e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) } 1266e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) 1276e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) /// clear - Reset per-query data, but preserve frequencies that only depend on 1286e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) // the CFG. 1296e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) void clear() { 1306e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) BiasN = BiasP = Value = 0; 1316e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) SumLinkWeights = getThreshold(); 1326e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) Links.clear(); 1331320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci } 1341320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 1356e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) /// addLink - Add a link to bundle b with weight w. 1366e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) void addLink(unsigned b, BlockFrequency w) { 1376e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) // Update cached sum. 1386e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) SumLinkWeights += w; 1396e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) 1406e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) // There can be multiple links to the same bundle, add them up. 1416e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) for (LinkVector::iterator I = Links.begin(), E = Links.end(); I != E; ++I) 1426e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) if (I->second == b) { 1436e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) I->first += w; 1441320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci return; 1451320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci } 1466e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) // This must be the first link to b. 1476e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) Links.push_back(std::make_pair(w, b)); 1486e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) } 1496e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) 1506e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) /// addBias - Bias this node. 1516e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) void addBias(BlockFrequency freq, BorderConstraint direction) { 1526e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) switch (direction) { 1531320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci default: 1541320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci break; 1551320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci case PrefReg: 1561320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci BiasP += freq; 1571320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci break; 1581320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci case PrefSpill: 1591320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci BiasN += freq; 1601320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci break; 1611320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci case MustSpill: 1621320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci BiasN = BlockFrequency::getMaxFrequency(); 1631320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci break; 1641320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci } 1651320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci } 1661320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 1671320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci /// update - Recompute Value from Bias and Links. Return true when node 1681320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci /// preference changes. 1691320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci bool update(const Node nodes[]) { 1701320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci // Compute the weighted sum of inputs. 1711320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci BlockFrequency SumN = BiasN; 1721320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci BlockFrequency SumP = BiasP; 1731320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci for (LinkVector::iterator I = Links.begin(), E = Links.end(); I != E; ++I) { 1741320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci if (nodes[I->second].Value == -1) 1751320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci SumN += I->first; 1761320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci else if (nodes[I->second].Value == 1) 1771320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci SumP += I->first; 1781320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci } 1791320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 1801320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci // Each weighted sum is going to be less than the total frequency of the 1811320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci // bundle. Ideally, we should simply set Value = sign(SumP - SumN), but we 1821320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci // will add a dead zone around 0 for two reasons: 1831320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci // 1841320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci // 1. It avoids arbitrary bias when all links are 0 as is possible during 1851320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci // initial iterations. 1861320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci // 2. It helps tame rounding errors when the links nominally sum to 0. 1871320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci // 1881320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci bool Before = preferReg(); 1891320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci if (SumN >= SumP + getThreshold()) 1901320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci Value = -1; 1911320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci else if (SumP >= SumN + getThreshold()) 1921320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci Value = 1; 1931320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci else 1941320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci Value = 0; 1951320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci return Before != preferReg(); 1966e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) } 1976e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)}; 1986e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) 1996e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)bool SpillPlacement::runOnMachineFunction(MachineFunction &mf) { 2006e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) MF = &mf; 2016e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) bundles = &getAnalysis<EdgeBundles>(); 2021320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci loops = &getAnalysis<MachineLoopInfo>(); 2036e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) 2046e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) assert(!nodes && "Leaking node array"); 2056e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) nodes = new Node[bundles->getNumBundles()]; 2066e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) 2076e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) // Compute total ingoing and outgoing block frequencies for all bundles. 2086e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) BlockFrequencies.resize(mf.getNumBlockIDs()); 2091320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci MBFI = &getAnalysis<MachineBlockFrequencyInfo>(); 2101320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci setThreshold(MBFI->getEntryFreq()); 2116e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) for (MachineFunction::iterator I = mf.begin(), E = mf.end(); I != E; ++I) { 2126e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) unsigned Num = I->getNumber(); 2136e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) BlockFrequencies[Num] = MBFI->getBlockFreq(I); 2146e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) } 2156e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) 2166e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) // We never change the function. 2176e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) return false; 2186e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)} 2196e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) 2206e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)void SpillPlacement::releaseMemory() { 2216e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) delete[] nodes; 2226e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) nodes = nullptr; 2236e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)} 2246e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) 2256e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)/// activate - mark node n as active if it wasn't already. 2261320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tuccivoid SpillPlacement::activate(unsigned n) { 2276e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) if (ActiveNodes->test(n)) 2286e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) return; 2296e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) ActiveNodes->set(n); 2306e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) nodes[n].clear(); 2316e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) 2326e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) // Very large bundles usually come from big switches, indirect branches, 2336e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) // landing pads, or loops with many 'continue' statements. It is difficult to 2341320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci // allocate registers when so many different blocks are involved. 2356e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) // 2366e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) // Give a small negative bias to large bundles such that a substantial 2376e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) // fraction of the connected blocks need to be interested before we consider 2386e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) // expanding the region through the bundle. This helps compile time by 2396e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) // limiting the number of blocks visited and the number of links in the 2406e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) // Hopfield network. 2411320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci if (bundles->getBlocks(n).size() > 100) { 2426e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) nodes[n].BiasP = 0; 2436e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) nodes[n].BiasN = (MBFI->getEntryFreq() / 16); 2446e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) } 2456e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)} 2466e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) 2476e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) 2486e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)/// addConstraints - Compute node biases and weights from a set of constraints. 2496e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)/// Set a bit in NodeMask for each active node. 2506e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)void SpillPlacement::addConstraints(ArrayRef<BlockConstraint> LiveBlocks) { 2516e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) for (ArrayRef<BlockConstraint>::iterator I = LiveBlocks.begin(), 2526e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) E = LiveBlocks.end(); I != E; ++I) { 2536e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) BlockFrequency Freq = BlockFrequencies[I->Number]; 2546e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) 2556e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) // Live-in to block? 2566e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) if (I->Entry != DontCare) { 2576e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) unsigned ib = bundles->getBundle(I->Number, 0); 2586e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) activate(ib); 2596e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) nodes[ib].addBias(Freq, I->Entry); 2606e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) } 2616e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) 2626e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) // Live-out from block? 2636e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) if (I->Exit != DontCare) { 2646e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) unsigned ob = bundles->getBundle(I->Number, 1); 2656e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) activate(ob); 2666e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) nodes[ob].addBias(Freq, I->Exit); 2676e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) } 2686e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) } 2696e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)} 2706e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) 2716e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)/// addPrefSpill - Same as addConstraints(PrefSpill) 2726e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)void SpillPlacement::addPrefSpill(ArrayRef<unsigned> Blocks, bool Strong) { 2736e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) for (ArrayRef<unsigned>::iterator I = Blocks.begin(), E = Blocks.end(); 2746e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) I != E; ++I) { 2751320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci BlockFrequency Freq = BlockFrequencies[*I]; 2761320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci if (Strong) 2771320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci Freq += Freq; 2781320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci unsigned ib = bundles->getBundle(*I, 0); 2791320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci unsigned ob = bundles->getBundle(*I, 1); 2801320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci activate(ib); 2811320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci activate(ob); 2821320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci nodes[ib].addBias(Freq, PrefSpill); 2831320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci nodes[ob].addBias(Freq, PrefSpill); 2841320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci } 2851320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci} 2861320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 2876e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)void SpillPlacement::addLinks(ArrayRef<unsigned> Links) { 288 for (ArrayRef<unsigned>::iterator I = Links.begin(), E = Links.end(); I != E; 289 ++I) { 290 unsigned Number = *I; 291 unsigned ib = bundles->getBundle(Number, 0); 292 unsigned ob = bundles->getBundle(Number, 1); 293 294 // Ignore self-loops. 295 if (ib == ob) 296 continue; 297 activate(ib); 298 activate(ob); 299 if (nodes[ib].Links.empty() && !nodes[ib].mustSpill()) 300 Linked.push_back(ib); 301 if (nodes[ob].Links.empty() && !nodes[ob].mustSpill()) 302 Linked.push_back(ob); 303 BlockFrequency Freq = BlockFrequencies[Number]; 304 nodes[ib].addLink(ob, Freq); 305 nodes[ob].addLink(ib, Freq); 306 } 307} 308 309bool SpillPlacement::scanActiveBundles() { 310 Linked.clear(); 311 RecentPositive.clear(); 312 for (int n = ActiveNodes->find_first(); n>=0; n = ActiveNodes->find_next(n)) { 313 nodes[n].update(nodes); 314 // A node that must spill, or a node without any links is not going to 315 // change its value ever again, so exclude it from iterations. 316 if (nodes[n].mustSpill()) 317 continue; 318 if (!nodes[n].Links.empty()) 319 Linked.push_back(n); 320 if (nodes[n].preferReg()) 321 RecentPositive.push_back(n); 322 } 323 return !RecentPositive.empty(); 324} 325 326/// iterate - Repeatedly update the Hopfield nodes until stability or the 327/// maximum number of iterations is reached. 328/// @param Linked - Numbers of linked nodes that need updating. 329void SpillPlacement::iterate() { 330 // First update the recently positive nodes. They have likely received new 331 // negative bias that will turn them off. 332 while (!RecentPositive.empty()) 333 nodes[RecentPositive.pop_back_val()].update(nodes); 334 335 if (Linked.empty()) 336 return; 337 338 // Run up to 10 iterations. The edge bundle numbering is closely related to 339 // basic block numbering, so there is a strong tendency towards chains of 340 // linked nodes with sequential numbers. By scanning the linked nodes 341 // backwards and forwards, we make it very likely that a single node can 342 // affect the entire network in a single iteration. That means very fast 343 // convergence, usually in a single iteration. 344 for (unsigned iteration = 0; iteration != 10; ++iteration) { 345 // Scan backwards, skipping the last node when iteration is not zero. When 346 // iteration is not zero, the last node was just updated. 347 bool Changed = false; 348 for (SmallVectorImpl<unsigned>::const_reverse_iterator I = 349 iteration == 0 ? Linked.rbegin() : std::next(Linked.rbegin()), 350 E = Linked.rend(); I != E; ++I) { 351 unsigned n = *I; 352 if (nodes[n].update(nodes)) { 353 Changed = true; 354 if (nodes[n].preferReg()) 355 RecentPositive.push_back(n); 356 } 357 } 358 if (!Changed || !RecentPositive.empty()) 359 return; 360 361 // Scan forwards, skipping the first node which was just updated. 362 Changed = false; 363 for (SmallVectorImpl<unsigned>::const_iterator I = 364 std::next(Linked.begin()), E = Linked.end(); I != E; ++I) { 365 unsigned n = *I; 366 if (nodes[n].update(nodes)) { 367 Changed = true; 368 if (nodes[n].preferReg()) 369 RecentPositive.push_back(n); 370 } 371 } 372 if (!Changed || !RecentPositive.empty()) 373 return; 374 } 375} 376 377void SpillPlacement::prepare(BitVector &RegBundles) { 378 Linked.clear(); 379 RecentPositive.clear(); 380 // Reuse RegBundles as our ActiveNodes vector. 381 ActiveNodes = &RegBundles; 382 ActiveNodes->clear(); 383 ActiveNodes->resize(bundles->getNumBundles()); 384} 385 386bool 387SpillPlacement::finish() { 388 assert(ActiveNodes && "Call prepare() first"); 389 390 // Write preferences back to ActiveNodes. 391 bool Perfect = true; 392 for (int n = ActiveNodes->find_first(); n>=0; n = ActiveNodes->find_next(n)) 393 if (!nodes[n].preferReg()) { 394 ActiveNodes->reset(n); 395 Perfect = false; 396 } 397 ActiveNodes = nullptr; 398 return Perfect; 399} 400