1218885Sdim//===-- SpillPlacement.cpp - Optimal Spill Code Placement -----------------===// 2218885Sdim// 3218885Sdim// The LLVM Compiler Infrastructure 4218885Sdim// 5218885Sdim// This file is distributed under the University of Illinois Open Source 6218885Sdim// License. See LICENSE.TXT for details. 7218885Sdim// 8218885Sdim//===----------------------------------------------------------------------===// 9218885Sdim// 10218885Sdim// This file implements the spill code placement analysis. 11218885Sdim// 12218885Sdim// Each edge bundle corresponds to a node in a Hopfield network. Constraints on 13218885Sdim// basic blocks are weighted by the block frequency and added to become the node 14218885Sdim// bias. 15218885Sdim// 16218885Sdim// Transparent basic blocks have the variable live through, but don't care if it 17218885Sdim// is spilled or in a register. These blocks become connections in the Hopfield 18218885Sdim// network, again weighted by block frequency. 19218885Sdim// 20218885Sdim// The Hopfield network minimizes (possibly locally) its energy function: 21218885Sdim// 22218885Sdim// E = -sum_n V_n * ( B_n + sum_{n, m linked by b} V_m * F_b ) 23218885Sdim// 24218885Sdim// The energy function represents the expected spill code execution frequency, 25218885Sdim// or the cost of spilling. This is a Lyapunov function which never increases 26218885Sdim// when a node is updated. It is guaranteed to converge to a local minimum. 27218885Sdim// 28218885Sdim//===----------------------------------------------------------------------===// 29218885Sdim 30218885Sdim#define DEBUG_TYPE "spillplacement" 31218885Sdim#include "SpillPlacement.h" 32252723Sdim#include "llvm/ADT/BitVector.h" 33218885Sdim#include "llvm/CodeGen/EdgeBundles.h" 34218885Sdim#include "llvm/CodeGen/MachineBasicBlock.h" 35263509Sdim#include "llvm/CodeGen/MachineBlockFrequencyInfo.h" 36218885Sdim#include "llvm/CodeGen/MachineFunction.h" 37218885Sdim#include "llvm/CodeGen/MachineLoopInfo.h" 38218885Sdim#include "llvm/CodeGen/Passes.h" 39218885Sdim#include "llvm/Support/Debug.h" 40218885Sdim#include "llvm/Support/Format.h" 41218885Sdim 42218885Sdimusing namespace llvm; 43218885Sdim 44218885Sdimchar SpillPlacement::ID = 0; 45218885SdimINITIALIZE_PASS_BEGIN(SpillPlacement, "spill-code-placement", 46218885Sdim "Spill Code Placement Analysis", true, true) 47218885SdimINITIALIZE_PASS_DEPENDENCY(EdgeBundles) 48218885SdimINITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) 49218885SdimINITIALIZE_PASS_END(SpillPlacement, "spill-code-placement", 50218885Sdim "Spill Code Placement Analysis", true, true) 51218885Sdim 52218885Sdimchar &llvm::SpillPlacementID = SpillPlacement::ID; 53218885Sdim 54218885Sdimvoid SpillPlacement::getAnalysisUsage(AnalysisUsage &AU) const { 55218885Sdim AU.setPreservesAll(); 56263509Sdim AU.addRequired<MachineBlockFrequencyInfo>(); 57218885Sdim AU.addRequiredTransitive<EdgeBundles>(); 58218885Sdim AU.addRequiredTransitive<MachineLoopInfo>(); 59218885Sdim MachineFunctionPass::getAnalysisUsage(AU); 60218885Sdim} 61218885Sdim 62263509Sdim/// Decision threshold. A node gets the output value 0 if the weighted sum of 63263509Sdim/// its inputs falls in the open interval (-Threshold;Threshold). 64263509Sdimstatic const BlockFrequency Threshold = 2; 65263509Sdim 66218885Sdim/// Node - Each edge bundle corresponds to a Hopfield node. 67218885Sdim/// 68218885Sdim/// The node contains precomputed frequency data that only depends on the CFG, 69218885Sdim/// but Bias and Links are computed each time placeSpills is called. 70218885Sdim/// 71218885Sdim/// The node Value is positive when the variable should be in a register. The 72218885Sdim/// value can change when linked nodes change, but convergence is very fast 73218885Sdim/// because all weights are positive. 74218885Sdim/// 75218885Sdimstruct SpillPlacement::Node { 76263509Sdim /// BiasN - Sum of blocks that prefer a spill. 77263509Sdim BlockFrequency BiasN; 78263509Sdim /// BiasP - Sum of blocks that prefer a register. 79263509Sdim BlockFrequency BiasP; 80218885Sdim 81218885Sdim /// Value - Output value of this node computed from the Bias and links. 82263509Sdim /// This is always on of the values {-1, 0, 1}. A positive number means the 83263509Sdim /// variable should go in a register through this bundle. 84263509Sdim int Value; 85218885Sdim 86263509Sdim typedef SmallVector<std::pair<BlockFrequency, unsigned>, 4> LinkVector; 87218885Sdim 88218885Sdim /// Links - (Weight, BundleNo) for all transparent blocks connecting to other 89263509Sdim /// bundles. The weights are all positive block frequencies. 90218885Sdim LinkVector Links; 91218885Sdim 92263509Sdim /// SumLinkWeights - Cached sum of the weights of all links + ThresHold. 93263509Sdim BlockFrequency SumLinkWeights; 94263509Sdim 95218885Sdim /// preferReg - Return true when this node prefers to be in a register. 96218885Sdim bool preferReg() const { 97218885Sdim // Undecided nodes (Value==0) go on the stack. 98218885Sdim return Value > 0; 99218885Sdim } 100218885Sdim 101218885Sdim /// mustSpill - Return True if this node is so biased that it must spill. 102218885Sdim bool mustSpill() const { 103263509Sdim // We must spill if Bias < -sum(weights) or the MustSpill flag was set. 104263509Sdim // BiasN is saturated when MustSpill is set, make sure this still returns 105263509Sdim // true when the RHS saturates. Note that SumLinkWeights includes Threshold. 106263509Sdim return BiasN >= BiasP + SumLinkWeights; 107218885Sdim } 108218885Sdim 109218885Sdim /// clear - Reset per-query data, but preserve frequencies that only depend on 110218885Sdim // the CFG. 111218885Sdim void clear() { 112263509Sdim BiasN = BiasP = Value = 0; 113263509Sdim SumLinkWeights = Threshold; 114218885Sdim Links.clear(); 115218885Sdim } 116218885Sdim 117218885Sdim /// addLink - Add a link to bundle b with weight w. 118263509Sdim void addLink(unsigned b, BlockFrequency w) { 119263509Sdim // Update cached sum. 120263509Sdim SumLinkWeights += w; 121218885Sdim 122218885Sdim // There can be multiple links to the same bundle, add them up. 123218885Sdim for (LinkVector::iterator I = Links.begin(), E = Links.end(); I != E; ++I) 124218885Sdim if (I->second == b) { 125218885Sdim I->first += w; 126218885Sdim return; 127218885Sdim } 128218885Sdim // This must be the first link to b. 129218885Sdim Links.push_back(std::make_pair(w, b)); 130218885Sdim } 131218885Sdim 132263509Sdim /// addBias - Bias this node. 133263509Sdim void addBias(BlockFrequency freq, BorderConstraint direction) { 134263509Sdim switch (direction) { 135263509Sdim default: 136263509Sdim break; 137263509Sdim case PrefReg: 138263509Sdim BiasP += freq; 139263509Sdim break; 140263509Sdim case PrefSpill: 141263509Sdim BiasN += freq; 142263509Sdim break; 143263509Sdim case MustSpill: 144263509Sdim BiasN = BlockFrequency::getMaxFrequency(); 145263509Sdim break; 146263509Sdim } 147218885Sdim } 148218885Sdim 149218885Sdim /// update - Recompute Value from Bias and Links. Return true when node 150218885Sdim /// preference changes. 151218885Sdim bool update(const Node nodes[]) { 152218885Sdim // Compute the weighted sum of inputs. 153263509Sdim BlockFrequency SumN = BiasN; 154263509Sdim BlockFrequency SumP = BiasP; 155263509Sdim for (LinkVector::iterator I = Links.begin(), E = Links.end(); I != E; ++I) { 156263509Sdim if (nodes[I->second].Value == -1) 157263509Sdim SumN += I->first; 158263509Sdim else if (nodes[I->second].Value == 1) 159263509Sdim SumP += I->first; 160263509Sdim } 161218885Sdim 162263509Sdim // Each weighted sum is going to be less than the total frequency of the 163263509Sdim // bundle. Ideally, we should simply set Value = sign(SumP - SumN), but we 164263509Sdim // will add a dead zone around 0 for two reasons: 165263509Sdim // 166218885Sdim // 1. It avoids arbitrary bias when all links are 0 as is possible during 167218885Sdim // initial iterations. 168218885Sdim // 2. It helps tame rounding errors when the links nominally sum to 0. 169263509Sdim // 170218885Sdim bool Before = preferReg(); 171263509Sdim if (SumN >= SumP + Threshold) 172218885Sdim Value = -1; 173263509Sdim else if (SumP >= SumN + Threshold) 174218885Sdim Value = 1; 175218885Sdim else 176218885Sdim Value = 0; 177218885Sdim return Before != preferReg(); 178218885Sdim } 179218885Sdim}; 180218885Sdim 181218885Sdimbool SpillPlacement::runOnMachineFunction(MachineFunction &mf) { 182218885Sdim MF = &mf; 183218885Sdim bundles = &getAnalysis<EdgeBundles>(); 184218885Sdim loops = &getAnalysis<MachineLoopInfo>(); 185218885Sdim 186218885Sdim assert(!nodes && "Leaking node array"); 187218885Sdim nodes = new Node[bundles->getNumBundles()]; 188218885Sdim 189218885Sdim // Compute total ingoing and outgoing block frequencies for all bundles. 190263509Sdim BlockFrequencies.resize(mf.getNumBlockIDs()); 191263509Sdim MachineBlockFrequencyInfo &MBFI = getAnalysis<MachineBlockFrequencyInfo>(); 192218885Sdim for (MachineFunction::iterator I = mf.begin(), E = mf.end(); I != E; ++I) { 193218885Sdim unsigned Num = I->getNumber(); 194263509Sdim BlockFrequencies[Num] = MBFI.getBlockFreq(I); 195218885Sdim } 196218885Sdim 197218885Sdim // We never change the function. 198218885Sdim return false; 199218885Sdim} 200218885Sdim 201218885Sdimvoid SpillPlacement::releaseMemory() { 202218885Sdim delete[] nodes; 203218885Sdim nodes = 0; 204218885Sdim} 205218885Sdim 206218885Sdim/// activate - mark node n as active if it wasn't already. 207218885Sdimvoid SpillPlacement::activate(unsigned n) { 208218885Sdim if (ActiveNodes->test(n)) 209218885Sdim return; 210218885Sdim ActiveNodes->set(n); 211218885Sdim nodes[n].clear(); 212245431Sdim 213245431Sdim // Very large bundles usually come from big switches, indirect branches, 214245431Sdim // landing pads, or loops with many 'continue' statements. It is difficult to 215245431Sdim // allocate registers when so many different blocks are involved. 216245431Sdim // 217263509Sdim // Give a small negative bias to large bundles such that a substantial 218263509Sdim // fraction of the connected blocks need to be interested before we consider 219263509Sdim // expanding the region through the bundle. This helps compile time by 220263509Sdim // limiting the number of blocks visited and the number of links in the 221263509Sdim // Hopfield network. 222263509Sdim if (bundles->getBlocks(n).size() > 100) { 223263509Sdim nodes[n].BiasP = 0; 224263509Sdim nodes[n].BiasN = (BlockFrequency::getEntryFrequency() / 16); 225263509Sdim } 226218885Sdim} 227218885Sdim 228218885Sdim 229221345Sdim/// addConstraints - Compute node biases and weights from a set of constraints. 230218885Sdim/// Set a bit in NodeMask for each active node. 231221345Sdimvoid SpillPlacement::addConstraints(ArrayRef<BlockConstraint> LiveBlocks) { 232221345Sdim for (ArrayRef<BlockConstraint>::iterator I = LiveBlocks.begin(), 233218885Sdim E = LiveBlocks.end(); I != E; ++I) { 234263509Sdim BlockFrequency Freq = BlockFrequencies[I->Number]; 235218885Sdim 236218885Sdim // Live-in to block? 237218885Sdim if (I->Entry != DontCare) { 238218885Sdim unsigned ib = bundles->getBundle(I->Number, 0); 239218885Sdim activate(ib); 240263509Sdim nodes[ib].addBias(Freq, I->Entry); 241218885Sdim } 242218885Sdim 243218885Sdim // Live-out from block? 244218885Sdim if (I->Exit != DontCare) { 245218885Sdim unsigned ob = bundles->getBundle(I->Number, 1); 246218885Sdim activate(ob); 247263509Sdim nodes[ob].addBias(Freq, I->Exit); 248218885Sdim } 249218885Sdim } 250218885Sdim} 251218885Sdim 252226890Sdim/// addPrefSpill - Same as addConstraints(PrefSpill) 253226890Sdimvoid SpillPlacement::addPrefSpill(ArrayRef<unsigned> Blocks, bool Strong) { 254226890Sdim for (ArrayRef<unsigned>::iterator I = Blocks.begin(), E = Blocks.end(); 255226890Sdim I != E; ++I) { 256263509Sdim BlockFrequency Freq = BlockFrequencies[*I]; 257226890Sdim if (Strong) 258226890Sdim Freq += Freq; 259226890Sdim unsigned ib = bundles->getBundle(*I, 0); 260226890Sdim unsigned ob = bundles->getBundle(*I, 1); 261226890Sdim activate(ib); 262226890Sdim activate(ob); 263263509Sdim nodes[ib].addBias(Freq, PrefSpill); 264263509Sdim nodes[ob].addBias(Freq, PrefSpill); 265226890Sdim } 266226890Sdim} 267226890Sdim 268221345Sdimvoid SpillPlacement::addLinks(ArrayRef<unsigned> Links) { 269221345Sdim for (ArrayRef<unsigned>::iterator I = Links.begin(), E = Links.end(); I != E; 270221345Sdim ++I) { 271221345Sdim unsigned Number = *I; 272221345Sdim unsigned ib = bundles->getBundle(Number, 0); 273221345Sdim unsigned ob = bundles->getBundle(Number, 1); 274221345Sdim 275221345Sdim // Ignore self-loops. 276221345Sdim if (ib == ob) 277221345Sdim continue; 278221345Sdim activate(ib); 279221345Sdim activate(ob); 280221345Sdim if (nodes[ib].Links.empty() && !nodes[ib].mustSpill()) 281221345Sdim Linked.push_back(ib); 282221345Sdim if (nodes[ob].Links.empty() && !nodes[ob].mustSpill()) 283221345Sdim Linked.push_back(ob); 284263509Sdim BlockFrequency Freq = BlockFrequencies[Number]; 285263509Sdim nodes[ib].addLink(ob, Freq); 286263509Sdim nodes[ob].addLink(ib, Freq); 287221345Sdim } 288221345Sdim} 289221345Sdim 290221345Sdimbool SpillPlacement::scanActiveBundles() { 291221345Sdim Linked.clear(); 292221345Sdim RecentPositive.clear(); 293221345Sdim for (int n = ActiveNodes->find_first(); n>=0; n = ActiveNodes->find_next(n)) { 294221345Sdim nodes[n].update(nodes); 295221345Sdim // A node that must spill, or a node without any links is not going to 296221345Sdim // change its value ever again, so exclude it from iterations. 297221345Sdim if (nodes[n].mustSpill()) 298221345Sdim continue; 299221345Sdim if (!nodes[n].Links.empty()) 300221345Sdim Linked.push_back(n); 301221345Sdim if (nodes[n].preferReg()) 302221345Sdim RecentPositive.push_back(n); 303221345Sdim } 304221345Sdim return !RecentPositive.empty(); 305221345Sdim} 306221345Sdim 307218885Sdim/// iterate - Repeatedly update the Hopfield nodes until stability or the 308218885Sdim/// maximum number of iterations is reached. 309218885Sdim/// @param Linked - Numbers of linked nodes that need updating. 310221345Sdimvoid SpillPlacement::iterate() { 311221345Sdim // First update the recently positive nodes. They have likely received new 312221345Sdim // negative bias that will turn them off. 313221345Sdim while (!RecentPositive.empty()) 314221345Sdim nodes[RecentPositive.pop_back_val()].update(nodes); 315221345Sdim 316218885Sdim if (Linked.empty()) 317218885Sdim return; 318218885Sdim 319218885Sdim // Run up to 10 iterations. The edge bundle numbering is closely related to 320218885Sdim // basic block numbering, so there is a strong tendency towards chains of 321218885Sdim // linked nodes with sequential numbers. By scanning the linked nodes 322218885Sdim // backwards and forwards, we make it very likely that a single node can 323218885Sdim // affect the entire network in a single iteration. That means very fast 324218885Sdim // convergence, usually in a single iteration. 325218885Sdim for (unsigned iteration = 0; iteration != 10; ++iteration) { 326218885Sdim // Scan backwards, skipping the last node which was just updated. 327218885Sdim bool Changed = false; 328218885Sdim for (SmallVectorImpl<unsigned>::const_reverse_iterator I = 329218885Sdim llvm::next(Linked.rbegin()), E = Linked.rend(); I != E; ++I) { 330218885Sdim unsigned n = *I; 331221345Sdim if (nodes[n].update(nodes)) { 332221345Sdim Changed = true; 333221345Sdim if (nodes[n].preferReg()) 334221345Sdim RecentPositive.push_back(n); 335221345Sdim } 336218885Sdim } 337221345Sdim if (!Changed || !RecentPositive.empty()) 338218885Sdim return; 339218885Sdim 340218885Sdim // Scan forwards, skipping the first node which was just updated. 341218885Sdim Changed = false; 342218885Sdim for (SmallVectorImpl<unsigned>::const_iterator I = 343218885Sdim llvm::next(Linked.begin()), E = Linked.end(); I != E; ++I) { 344218885Sdim unsigned n = *I; 345221345Sdim if (nodes[n].update(nodes)) { 346221345Sdim Changed = true; 347221345Sdim if (nodes[n].preferReg()) 348221345Sdim RecentPositive.push_back(n); 349221345Sdim } 350218885Sdim } 351221345Sdim if (!Changed || !RecentPositive.empty()) 352218885Sdim return; 353218885Sdim } 354218885Sdim} 355218885Sdim 356221345Sdimvoid SpillPlacement::prepare(BitVector &RegBundles) { 357221345Sdim Linked.clear(); 358221345Sdim RecentPositive.clear(); 359218885Sdim // Reuse RegBundles as our ActiveNodes vector. 360218885Sdim ActiveNodes = &RegBundles; 361218885Sdim ActiveNodes->clear(); 362218885Sdim ActiveNodes->resize(bundles->getNumBundles()); 363221345Sdim} 364218885Sdim 365221345Sdimbool 366221345SdimSpillPlacement::finish() { 367221345Sdim assert(ActiveNodes && "Call prepare() first"); 368218885Sdim 369221345Sdim // Write preferences back to ActiveNodes. 370218885Sdim bool Perfect = true; 371221345Sdim for (int n = ActiveNodes->find_first(); n>=0; n = ActiveNodes->find_next(n)) 372218885Sdim if (!nodes[n].preferReg()) { 373221345Sdim ActiveNodes->reset(n); 374218885Sdim Perfect = false; 375218885Sdim } 376221345Sdim ActiveNodes = 0; 377218885Sdim return Perfect; 378218885Sdim} 379