10b57cec5SDimitry Andric //===- SpillPlacement.cpp - Optimal Spill Code Placement ------------------===// 20b57cec5SDimitry Andric // 30b57cec5SDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 40b57cec5SDimitry Andric // See https://llvm.org/LICENSE.txt for license information. 50b57cec5SDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 60b57cec5SDimitry Andric // 70b57cec5SDimitry Andric //===----------------------------------------------------------------------===// 80b57cec5SDimitry Andric // 90b57cec5SDimitry Andric // This file implements the spill code placement analysis. 100b57cec5SDimitry Andric // 110b57cec5SDimitry Andric // Each edge bundle corresponds to a node in a Hopfield network. Constraints on 120b57cec5SDimitry Andric // basic blocks are weighted by the block frequency and added to become the node 130b57cec5SDimitry Andric // bias. 140b57cec5SDimitry Andric // 150b57cec5SDimitry Andric // Transparent basic blocks have the variable live through, but don't care if it 160b57cec5SDimitry Andric // is spilled or in a register. These blocks become connections in the Hopfield 170b57cec5SDimitry Andric // network, again weighted by block frequency. 180b57cec5SDimitry Andric // 190b57cec5SDimitry Andric // The Hopfield network minimizes (possibly locally) its energy function: 200b57cec5SDimitry Andric // 210b57cec5SDimitry Andric // E = -sum_n V_n * ( B_n + sum_{n, m linked by b} V_m * F_b ) 220b57cec5SDimitry Andric // 230b57cec5SDimitry Andric // The energy function represents the expected spill code execution frequency, 240b57cec5SDimitry Andric // or the cost of spilling. This is a Lyapunov function which never increases 250b57cec5SDimitry Andric // when a node is updated. It is guaranteed to converge to a local minimum. 260b57cec5SDimitry Andric // 270b57cec5SDimitry Andric //===----------------------------------------------------------------------===// 280b57cec5SDimitry Andric 290b57cec5SDimitry Andric #include "SpillPlacement.h" 300b57cec5SDimitry Andric #include "llvm/ADT/BitVector.h" 310b57cec5SDimitry Andric #include "llvm/CodeGen/EdgeBundles.h" 320b57cec5SDimitry Andric #include "llvm/CodeGen/MachineBasicBlock.h" 330b57cec5SDimitry Andric #include "llvm/CodeGen/MachineBlockFrequencyInfo.h" 340b57cec5SDimitry Andric #include "llvm/CodeGen/MachineFunction.h" 350b57cec5SDimitry Andric #include "llvm/CodeGen/Passes.h" 36480093f4SDimitry Andric #include "llvm/InitializePasses.h" 370b57cec5SDimitry Andric #include "llvm/Pass.h" 380b57cec5SDimitry Andric #include <algorithm> 390b57cec5SDimitry Andric #include <cassert> 400b57cec5SDimitry Andric #include <cstdint> 410b57cec5SDimitry Andric #include <utility> 420b57cec5SDimitry Andric 430b57cec5SDimitry Andric using namespace llvm; 440b57cec5SDimitry Andric 450b57cec5SDimitry Andric #define DEBUG_TYPE "spill-code-placement" 460b57cec5SDimitry Andric 470b57cec5SDimitry Andric char SpillPlacement::ID = 0; 480b57cec5SDimitry Andric 490b57cec5SDimitry Andric char &llvm::SpillPlacementID = SpillPlacement::ID; 500b57cec5SDimitry Andric 510b57cec5SDimitry Andric INITIALIZE_PASS_BEGIN(SpillPlacement, DEBUG_TYPE, 520b57cec5SDimitry Andric "Spill Code Placement Analysis", true, true) 530b57cec5SDimitry Andric INITIALIZE_PASS_DEPENDENCY(EdgeBundles) 540b57cec5SDimitry Andric INITIALIZE_PASS_END(SpillPlacement, DEBUG_TYPE, 550b57cec5SDimitry Andric "Spill Code Placement Analysis", true, true) 560b57cec5SDimitry Andric 570b57cec5SDimitry Andric void SpillPlacement::getAnalysisUsage(AnalysisUsage &AU) const { 580b57cec5SDimitry Andric AU.setPreservesAll(); 59*0fca6ea1SDimitry Andric AU.addRequired<MachineBlockFrequencyInfoWrapperPass>(); 600b57cec5SDimitry Andric AU.addRequiredTransitive<EdgeBundles>(); 610b57cec5SDimitry Andric MachineFunctionPass::getAnalysisUsage(AU); 620b57cec5SDimitry Andric } 630b57cec5SDimitry Andric 640b57cec5SDimitry Andric /// Node - Each edge bundle corresponds to a Hopfield node. 650b57cec5SDimitry Andric /// 660b57cec5SDimitry Andric /// The node contains precomputed frequency data that only depends on the CFG, 670b57cec5SDimitry Andric /// but Bias and Links are computed each time placeSpills is called. 680b57cec5SDimitry Andric /// 690b57cec5SDimitry Andric /// The node Value is positive when the variable should be in a register. The 700b57cec5SDimitry Andric /// value can change when linked nodes change, but convergence is very fast 710b57cec5SDimitry Andric /// because all weights are positive. 720b57cec5SDimitry Andric struct SpillPlacement::Node { 730b57cec5SDimitry Andric /// BiasN - Sum of blocks that prefer a spill. 740b57cec5SDimitry Andric BlockFrequency BiasN; 750b57cec5SDimitry Andric 760b57cec5SDimitry Andric /// BiasP - Sum of blocks that prefer a register. 770b57cec5SDimitry Andric BlockFrequency BiasP; 780b57cec5SDimitry Andric 790b57cec5SDimitry Andric /// Value - Output value of this node computed from the Bias and links. 800b57cec5SDimitry Andric /// This is always on of the values {-1, 0, 1}. A positive number means the 810b57cec5SDimitry Andric /// variable should go in a register through this bundle. 820b57cec5SDimitry Andric int Value; 830b57cec5SDimitry Andric 840b57cec5SDimitry Andric using LinkVector = SmallVector<std::pair<BlockFrequency, unsigned>, 4>; 850b57cec5SDimitry Andric 860b57cec5SDimitry Andric /// Links - (Weight, BundleNo) for all transparent blocks connecting to other 870b57cec5SDimitry Andric /// bundles. The weights are all positive block frequencies. 880b57cec5SDimitry Andric LinkVector Links; 890b57cec5SDimitry Andric 900b57cec5SDimitry Andric /// SumLinkWeights - Cached sum of the weights of all links + ThresHold. 910b57cec5SDimitry Andric BlockFrequency SumLinkWeights; 920b57cec5SDimitry Andric 930b57cec5SDimitry Andric /// preferReg - Return true when this node prefers to be in a register. 940b57cec5SDimitry Andric bool preferReg() const { 950b57cec5SDimitry Andric // Undecided nodes (Value==0) go on the stack. 960b57cec5SDimitry Andric return Value > 0; 970b57cec5SDimitry Andric } 980b57cec5SDimitry Andric 990b57cec5SDimitry Andric /// mustSpill - Return True if this node is so biased that it must spill. 1000b57cec5SDimitry Andric bool mustSpill() const { 1010b57cec5SDimitry Andric // We must spill if Bias < -sum(weights) or the MustSpill flag was set. 1020b57cec5SDimitry Andric // BiasN is saturated when MustSpill is set, make sure this still returns 1030b57cec5SDimitry Andric // true when the RHS saturates. Note that SumLinkWeights includes Threshold. 1040b57cec5SDimitry Andric return BiasN >= BiasP + SumLinkWeights; 1050b57cec5SDimitry Andric } 1060b57cec5SDimitry Andric 1070b57cec5SDimitry Andric /// clear - Reset per-query data, but preserve frequencies that only depend on 1080b57cec5SDimitry Andric /// the CFG. 1095f757f3fSDimitry Andric void clear(BlockFrequency Threshold) { 1105f757f3fSDimitry Andric BiasN = BlockFrequency(0); 1115f757f3fSDimitry Andric BiasP = BlockFrequency(0); 1125f757f3fSDimitry Andric Value = 0; 1130b57cec5SDimitry Andric SumLinkWeights = Threshold; 1140b57cec5SDimitry Andric Links.clear(); 1150b57cec5SDimitry Andric } 1160b57cec5SDimitry Andric 1170b57cec5SDimitry Andric /// addLink - Add a link to bundle b with weight w. 1180b57cec5SDimitry Andric void addLink(unsigned b, BlockFrequency w) { 1190b57cec5SDimitry Andric // Update cached sum. 1200b57cec5SDimitry Andric SumLinkWeights += w; 1210b57cec5SDimitry Andric 1220b57cec5SDimitry Andric // There can be multiple links to the same bundle, add them up. 123fe6060f1SDimitry Andric for (std::pair<BlockFrequency, unsigned> &L : Links) 124fe6060f1SDimitry Andric if (L.second == b) { 125fe6060f1SDimitry Andric L.first += w; 1260b57cec5SDimitry Andric return; 1270b57cec5SDimitry Andric } 1280b57cec5SDimitry Andric // This must be the first link to b. 1290b57cec5SDimitry Andric Links.push_back(std::make_pair(w, b)); 1300b57cec5SDimitry Andric } 1310b57cec5SDimitry Andric 1320b57cec5SDimitry Andric /// addBias - Bias this node. 1330b57cec5SDimitry Andric void addBias(BlockFrequency freq, BorderConstraint direction) { 1340b57cec5SDimitry Andric switch (direction) { 1350b57cec5SDimitry Andric default: 1360b57cec5SDimitry Andric break; 1370b57cec5SDimitry Andric case PrefReg: 1380b57cec5SDimitry Andric BiasP += freq; 1390b57cec5SDimitry Andric break; 1400b57cec5SDimitry Andric case PrefSpill: 1410b57cec5SDimitry Andric BiasN += freq; 1420b57cec5SDimitry Andric break; 1430b57cec5SDimitry Andric case MustSpill: 1445f757f3fSDimitry Andric BiasN = BlockFrequency::max(); 1450b57cec5SDimitry Andric break; 1460b57cec5SDimitry Andric } 1470b57cec5SDimitry Andric } 1480b57cec5SDimitry Andric 1490b57cec5SDimitry Andric /// update - Recompute Value from Bias and Links. Return true when node 1500b57cec5SDimitry Andric /// preference changes. 1515f757f3fSDimitry Andric bool update(const Node nodes[], BlockFrequency Threshold) { 1520b57cec5SDimitry Andric // Compute the weighted sum of inputs. 1530b57cec5SDimitry Andric BlockFrequency SumN = BiasN; 1540b57cec5SDimitry Andric BlockFrequency SumP = BiasP; 155fe6060f1SDimitry Andric for (std::pair<BlockFrequency, unsigned> &L : Links) { 156fe6060f1SDimitry Andric if (nodes[L.second].Value == -1) 157fe6060f1SDimitry Andric SumN += L.first; 158fe6060f1SDimitry Andric else if (nodes[L.second].Value == 1) 159fe6060f1SDimitry Andric SumP += L.first; 1600b57cec5SDimitry Andric } 1610b57cec5SDimitry Andric 1620b57cec5SDimitry Andric // Each weighted sum is going to be less than the total frequency of the 1630b57cec5SDimitry Andric // bundle. Ideally, we should simply set Value = sign(SumP - SumN), but we 1640b57cec5SDimitry Andric // will add a dead zone around 0 for two reasons: 1650b57cec5SDimitry Andric // 1660b57cec5SDimitry Andric // 1. It avoids arbitrary bias when all links are 0 as is possible during 1670b57cec5SDimitry Andric // initial iterations. 1680b57cec5SDimitry Andric // 2. It helps tame rounding errors when the links nominally sum to 0. 1690b57cec5SDimitry Andric // 1700b57cec5SDimitry Andric bool Before = preferReg(); 1710b57cec5SDimitry Andric if (SumN >= SumP + Threshold) 1720b57cec5SDimitry Andric Value = -1; 1730b57cec5SDimitry Andric else if (SumP >= SumN + Threshold) 1740b57cec5SDimitry Andric Value = 1; 1750b57cec5SDimitry Andric else 1760b57cec5SDimitry Andric Value = 0; 1770b57cec5SDimitry Andric return Before != preferReg(); 1780b57cec5SDimitry Andric } 1790b57cec5SDimitry Andric 1800b57cec5SDimitry Andric void getDissentingNeighbors(SparseSet<unsigned> &List, 1810b57cec5SDimitry Andric const Node nodes[]) const { 1820b57cec5SDimitry Andric for (const auto &Elt : Links) { 1830b57cec5SDimitry Andric unsigned n = Elt.second; 1840b57cec5SDimitry Andric // Neighbors that already have the same value are not going to 1850b57cec5SDimitry Andric // change because of this node changing. 1860b57cec5SDimitry Andric if (Value != nodes[n].Value) 1870b57cec5SDimitry Andric List.insert(n); 1880b57cec5SDimitry Andric } 1890b57cec5SDimitry Andric } 1900b57cec5SDimitry Andric }; 1910b57cec5SDimitry Andric 1920b57cec5SDimitry Andric bool SpillPlacement::runOnMachineFunction(MachineFunction &mf) { 1930b57cec5SDimitry Andric MF = &mf; 1940b57cec5SDimitry Andric bundles = &getAnalysis<EdgeBundles>(); 1950b57cec5SDimitry Andric 1960b57cec5SDimitry Andric assert(!nodes && "Leaking node array"); 1970b57cec5SDimitry Andric nodes = new Node[bundles->getNumBundles()]; 1980b57cec5SDimitry Andric TodoList.clear(); 1990b57cec5SDimitry Andric TodoList.setUniverse(bundles->getNumBundles()); 2000b57cec5SDimitry Andric 2010b57cec5SDimitry Andric // Compute total ingoing and outgoing block frequencies for all bundles. 2020b57cec5SDimitry Andric BlockFrequencies.resize(mf.getNumBlockIDs()); 203*0fca6ea1SDimitry Andric MBFI = &getAnalysis<MachineBlockFrequencyInfoWrapperPass>().getMBFI(); 2040b57cec5SDimitry Andric setThreshold(MBFI->getEntryFreq()); 2050b57cec5SDimitry Andric for (auto &I : mf) { 2060b57cec5SDimitry Andric unsigned Num = I.getNumber(); 2070b57cec5SDimitry Andric BlockFrequencies[Num] = MBFI->getBlockFreq(&I); 2080b57cec5SDimitry Andric } 2090b57cec5SDimitry Andric 2100b57cec5SDimitry Andric // We never change the function. 2110b57cec5SDimitry Andric return false; 2120b57cec5SDimitry Andric } 2130b57cec5SDimitry Andric 2140b57cec5SDimitry Andric void SpillPlacement::releaseMemory() { 2150b57cec5SDimitry Andric delete[] nodes; 2160b57cec5SDimitry Andric nodes = nullptr; 2170b57cec5SDimitry Andric TodoList.clear(); 2180b57cec5SDimitry Andric } 2190b57cec5SDimitry Andric 2200b57cec5SDimitry Andric /// activate - mark node n as active if it wasn't already. 2210b57cec5SDimitry Andric void SpillPlacement::activate(unsigned n) { 2220b57cec5SDimitry Andric TodoList.insert(n); 2230b57cec5SDimitry Andric if (ActiveNodes->test(n)) 2240b57cec5SDimitry Andric return; 2250b57cec5SDimitry Andric ActiveNodes->set(n); 2260b57cec5SDimitry Andric nodes[n].clear(Threshold); 2270b57cec5SDimitry Andric 2280b57cec5SDimitry Andric // Very large bundles usually come from big switches, indirect branches, 2290b57cec5SDimitry Andric // landing pads, or loops with many 'continue' statements. It is difficult to 2300b57cec5SDimitry Andric // allocate registers when so many different blocks are involved. 2310b57cec5SDimitry Andric // 2320b57cec5SDimitry Andric // Give a small negative bias to large bundles such that a substantial 2330b57cec5SDimitry Andric // fraction of the connected blocks need to be interested before we consider 2340b57cec5SDimitry Andric // expanding the region through the bundle. This helps compile time by 2350b57cec5SDimitry Andric // limiting the number of blocks visited and the number of links in the 2360b57cec5SDimitry Andric // Hopfield network. 2370b57cec5SDimitry Andric if (bundles->getBlocks(n).size() > 100) { 2385f757f3fSDimitry Andric nodes[n].BiasP = BlockFrequency(0); 2395f757f3fSDimitry Andric BlockFrequency BiasN = MBFI->getEntryFreq(); 2405f757f3fSDimitry Andric BiasN >>= 4; 2415f757f3fSDimitry Andric nodes[n].BiasN = BiasN; 2420b57cec5SDimitry Andric } 2430b57cec5SDimitry Andric } 2440b57cec5SDimitry Andric 2450b57cec5SDimitry Andric /// Set the threshold for a given entry frequency. 2460b57cec5SDimitry Andric /// 2470b57cec5SDimitry Andric /// Set the threshold relative to \c Entry. Since the threshold is used as a 2480b57cec5SDimitry Andric /// bound on the open interval (-Threshold;Threshold), 1 is the minimum 2490b57cec5SDimitry Andric /// threshold. 2505f757f3fSDimitry Andric void SpillPlacement::setThreshold(BlockFrequency Entry) { 2510b57cec5SDimitry Andric // Apparently 2 is a good threshold when Entry==2^14, but we need to scale 2520b57cec5SDimitry Andric // it. Divide by 2^13, rounding as appropriate. 2530b57cec5SDimitry Andric uint64_t Freq = Entry.getFrequency(); 2540b57cec5SDimitry Andric uint64_t Scaled = (Freq >> 13) + bool(Freq & (1 << 12)); 2555f757f3fSDimitry Andric Threshold = BlockFrequency(std::max(UINT64_C(1), Scaled)); 2560b57cec5SDimitry Andric } 2570b57cec5SDimitry Andric 2580b57cec5SDimitry Andric /// addConstraints - Compute node biases and weights from a set of constraints. 2590b57cec5SDimitry Andric /// Set a bit in NodeMask for each active node. 2600b57cec5SDimitry Andric void SpillPlacement::addConstraints(ArrayRef<BlockConstraint> LiveBlocks) { 261fe6060f1SDimitry Andric for (const BlockConstraint &LB : LiveBlocks) { 262fe6060f1SDimitry Andric BlockFrequency Freq = BlockFrequencies[LB.Number]; 2630b57cec5SDimitry Andric 2640b57cec5SDimitry Andric // Live-in to block? 265fe6060f1SDimitry Andric if (LB.Entry != DontCare) { 266fe6060f1SDimitry Andric unsigned ib = bundles->getBundle(LB.Number, false); 2670b57cec5SDimitry Andric activate(ib); 268fe6060f1SDimitry Andric nodes[ib].addBias(Freq, LB.Entry); 2690b57cec5SDimitry Andric } 2700b57cec5SDimitry Andric 2710b57cec5SDimitry Andric // Live-out from block? 272fe6060f1SDimitry Andric if (LB.Exit != DontCare) { 273fe6060f1SDimitry Andric unsigned ob = bundles->getBundle(LB.Number, true); 2740b57cec5SDimitry Andric activate(ob); 275fe6060f1SDimitry Andric nodes[ob].addBias(Freq, LB.Exit); 2760b57cec5SDimitry Andric } 2770b57cec5SDimitry Andric } 2780b57cec5SDimitry Andric } 2790b57cec5SDimitry Andric 2800b57cec5SDimitry Andric /// addPrefSpill - Same as addConstraints(PrefSpill) 2810b57cec5SDimitry Andric void SpillPlacement::addPrefSpill(ArrayRef<unsigned> Blocks, bool Strong) { 282fe6060f1SDimitry Andric for (unsigned B : Blocks) { 283fe6060f1SDimitry Andric BlockFrequency Freq = BlockFrequencies[B]; 2840b57cec5SDimitry Andric if (Strong) 2850b57cec5SDimitry Andric Freq += Freq; 286fe6060f1SDimitry Andric unsigned ib = bundles->getBundle(B, false); 287fe6060f1SDimitry Andric unsigned ob = bundles->getBundle(B, true); 2880b57cec5SDimitry Andric activate(ib); 2890b57cec5SDimitry Andric activate(ob); 2900b57cec5SDimitry Andric nodes[ib].addBias(Freq, PrefSpill); 2910b57cec5SDimitry Andric nodes[ob].addBias(Freq, PrefSpill); 2920b57cec5SDimitry Andric } 2930b57cec5SDimitry Andric } 2940b57cec5SDimitry Andric 2950b57cec5SDimitry Andric void SpillPlacement::addLinks(ArrayRef<unsigned> Links) { 296fe6060f1SDimitry Andric for (unsigned Number : Links) { 2970b57cec5SDimitry Andric unsigned ib = bundles->getBundle(Number, false); 2980b57cec5SDimitry Andric unsigned ob = bundles->getBundle(Number, true); 2990b57cec5SDimitry Andric 3000b57cec5SDimitry Andric // Ignore self-loops. 3010b57cec5SDimitry Andric if (ib == ob) 3020b57cec5SDimitry Andric continue; 3030b57cec5SDimitry Andric activate(ib); 3040b57cec5SDimitry Andric activate(ob); 3050b57cec5SDimitry Andric BlockFrequency Freq = BlockFrequencies[Number]; 3060b57cec5SDimitry Andric nodes[ib].addLink(ob, Freq); 3070b57cec5SDimitry Andric nodes[ob].addLink(ib, Freq); 3080b57cec5SDimitry Andric } 3090b57cec5SDimitry Andric } 3100b57cec5SDimitry Andric 3110b57cec5SDimitry Andric bool SpillPlacement::scanActiveBundles() { 3120b57cec5SDimitry Andric RecentPositive.clear(); 3130b57cec5SDimitry Andric for (unsigned n : ActiveNodes->set_bits()) { 3140b57cec5SDimitry Andric update(n); 3150b57cec5SDimitry Andric // A node that must spill, or a node without any links is not going to 3160b57cec5SDimitry Andric // change its value ever again, so exclude it from iterations. 3170b57cec5SDimitry Andric if (nodes[n].mustSpill()) 3180b57cec5SDimitry Andric continue; 3190b57cec5SDimitry Andric if (nodes[n].preferReg()) 3200b57cec5SDimitry Andric RecentPositive.push_back(n); 3210b57cec5SDimitry Andric } 3220b57cec5SDimitry Andric return !RecentPositive.empty(); 3230b57cec5SDimitry Andric } 3240b57cec5SDimitry Andric 3250b57cec5SDimitry Andric bool SpillPlacement::update(unsigned n) { 3260b57cec5SDimitry Andric if (!nodes[n].update(nodes, Threshold)) 3270b57cec5SDimitry Andric return false; 3280b57cec5SDimitry Andric nodes[n].getDissentingNeighbors(TodoList, nodes); 3290b57cec5SDimitry Andric return true; 3300b57cec5SDimitry Andric } 3310b57cec5SDimitry Andric 3320b57cec5SDimitry Andric /// iterate - Repeatedly update the Hopfield nodes until stability or the 3330b57cec5SDimitry Andric /// maximum number of iterations is reached. 3340b57cec5SDimitry Andric void SpillPlacement::iterate() { 3350b57cec5SDimitry Andric // We do not need to push those node in the todolist. 3360b57cec5SDimitry Andric // They are already been proceeded as part of the previous iteration. 3370b57cec5SDimitry Andric RecentPositive.clear(); 3380b57cec5SDimitry Andric 3390b57cec5SDimitry Andric // Since the last iteration, the todolist have been augmented by calls 3400b57cec5SDimitry Andric // to addConstraints, addLinks, and co. 3410b57cec5SDimitry Andric // Update the network energy starting at this new frontier. 3420b57cec5SDimitry Andric // The call to ::update will add the nodes that changed into the todolist. 3430b57cec5SDimitry Andric unsigned Limit = bundles->getNumBundles() * 10; 3440b57cec5SDimitry Andric while(Limit-- > 0 && !TodoList.empty()) { 3450b57cec5SDimitry Andric unsigned n = TodoList.pop_back_val(); 3460b57cec5SDimitry Andric if (!update(n)) 3470b57cec5SDimitry Andric continue; 3480b57cec5SDimitry Andric if (nodes[n].preferReg()) 3490b57cec5SDimitry Andric RecentPositive.push_back(n); 3500b57cec5SDimitry Andric } 3510b57cec5SDimitry Andric } 3520b57cec5SDimitry Andric 3530b57cec5SDimitry Andric void SpillPlacement::prepare(BitVector &RegBundles) { 3540b57cec5SDimitry Andric RecentPositive.clear(); 3550b57cec5SDimitry Andric TodoList.clear(); 3560b57cec5SDimitry Andric // Reuse RegBundles as our ActiveNodes vector. 3570b57cec5SDimitry Andric ActiveNodes = &RegBundles; 3580b57cec5SDimitry Andric ActiveNodes->clear(); 3590b57cec5SDimitry Andric ActiveNodes->resize(bundles->getNumBundles()); 3600b57cec5SDimitry Andric } 3610b57cec5SDimitry Andric 3620b57cec5SDimitry Andric bool 3630b57cec5SDimitry Andric SpillPlacement::finish() { 3640b57cec5SDimitry Andric assert(ActiveNodes && "Call prepare() first"); 3650b57cec5SDimitry Andric 3660b57cec5SDimitry Andric // Write preferences back to ActiveNodes. 3670b57cec5SDimitry Andric bool Perfect = true; 3680b57cec5SDimitry Andric for (unsigned n : ActiveNodes->set_bits()) 3690b57cec5SDimitry Andric if (!nodes[n].preferReg()) { 3700b57cec5SDimitry Andric ActiveNodes->reset(n); 3710b57cec5SDimitry Andric Perfect = false; 3720b57cec5SDimitry Andric } 3730b57cec5SDimitry Andric ActiveNodes = nullptr; 3740b57cec5SDimitry Andric return Perfect; 3750b57cec5SDimitry Andric } 376fe6060f1SDimitry Andric 377fe6060f1SDimitry Andric void SpillPlacement::BlockConstraint::print(raw_ostream &OS) const { 378fe6060f1SDimitry Andric auto toString = [](BorderConstraint C) -> StringRef { 379fe6060f1SDimitry Andric switch(C) { 380fe6060f1SDimitry Andric case DontCare: return "DontCare"; 381fe6060f1SDimitry Andric case PrefReg: return "PrefReg"; 382fe6060f1SDimitry Andric case PrefSpill: return "PrefSpill"; 383fe6060f1SDimitry Andric case PrefBoth: return "PrefBoth"; 384fe6060f1SDimitry Andric case MustSpill: return "MustSpill"; 385fe6060f1SDimitry Andric }; 386fe6060f1SDimitry Andric llvm_unreachable("uncovered switch"); 387fe6060f1SDimitry Andric }; 388fe6060f1SDimitry Andric 389fe6060f1SDimitry Andric dbgs() << "{" << Number << ", " 390fe6060f1SDimitry Andric << toString(Entry) << ", " 391fe6060f1SDimitry Andric << toString(Exit) << ", " 392fe6060f1SDimitry Andric << (ChangesValue ? "changes" : "no change") << "}"; 393fe6060f1SDimitry Andric } 394fe6060f1SDimitry Andric 395fe6060f1SDimitry Andric void SpillPlacement::BlockConstraint::dump() const { 396fe6060f1SDimitry Andric print(dbgs()); 397fe6060f1SDimitry Andric dbgs() << "\n"; 398fe6060f1SDimitry Andric } 399