RegAllocGreedy.cpp revision a77da0579bc141eba62760e21a216e5d3eafd792
1cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen//===-- RegAllocGreedy.cpp - greedy register allocator --------------------===// 2cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen// 3cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen// The LLVM Compiler Infrastructure 4cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen// 5cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen// This file is distributed under the University of Illinois Open Source 6cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen// License. See LICENSE.TXT for details. 7cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen// 8cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen//===----------------------------------------------------------------------===// 9cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen// 10cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen// This file defines the RAGreedy function pass for register allocation in 11cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen// optimized builds. 12cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen// 13cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen//===----------------------------------------------------------------------===// 14cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 15cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#define DEBUG_TYPE "regalloc" 16d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/CodeGen/Passes.h" 17dd479e9769eceee9fcc34e2173376024f3aa3c5fJakob Stoklund Olesen#include "AllocationOrder.h" 185907d863659eb972ebb2afe07bc863a4c616f0efJakob Stoklund Olesen#include "InterferenceCache.h" 19cfafc54040cc9722995558124f253d05a038176bJakob Stoklund Olesen#include "LiveDebugVariables.h" 20cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "RegAllocBase.h" 21b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen#include "SpillPlacement.h" 22d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "Spiller.h" 23d0bb5e2ca05d9c942223bf05e5940bb0c6cc9d3fJakob Stoklund Olesen#include "SplitKit.h" 240db841f9c2b9a25fb5ecb36e350d3a802c35654cJakob Stoklund Olesen#include "llvm/ADT/Statistic.h" 25cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "llvm/Analysis/AliasAnalysis.h" 26cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "llvm/CodeGen/CalcSpillWeights.h" 27b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen#include "llvm/CodeGen/EdgeBundles.h" 28cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "llvm/CodeGen/LiveIntervalAnalysis.h" 29789d5d85ba6e9259a8e0f0bcfbd06a59ad164512Pete Cooper#include "llvm/CodeGen/LiveRangeEdit.h" 301ead68d769f27f6d68d4aaeffe4199fa2cacbc95Jakob Stoklund Olesen#include "llvm/CodeGen/LiveRegMatrix.h" 31cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "llvm/CodeGen/LiveStackAnalysis.h" 324eed756153b84c211114a3e9186bf0cb55d4b394Benjamin Kramer#include "llvm/CodeGen/MachineBlockFrequencyInfo.h" 33f428eb6c1b09a2322b7a577b0bf2e49dd107bceaJakob Stoklund Olesen#include "llvm/CodeGen/MachineDominators.h" 34cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "llvm/CodeGen/MachineFunctionPass.h" 35cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "llvm/CodeGen/MachineLoopInfo.h" 36cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "llvm/CodeGen/MachineRegisterInfo.h" 37cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "llvm/CodeGen/RegAllocRegistry.h" 38d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/CodeGen/VirtRegMap.h" 39d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/PassAnalysisSupport.h" 4000005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen#include "llvm/Support/CommandLine.h" 41cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "llvm/Support/Debug.h" 42cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "llvm/Support/ErrorHandling.h" 43533f58ecdd8a4732c2f0e149387c4d8d8d4142deJakob Stoklund Olesen#include "llvm/Support/Timer.h" 44d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Support/raw_ostream.h" 4598d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen#include <queue> 4698d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen 47cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesenusing namespace llvm; 48cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 490db841f9c2b9a25fb5ecb36e350d3a802c35654cJakob Stoklund OlesenSTATISTIC(NumGlobalSplits, "Number of split global live ranges"); 500db841f9c2b9a25fb5ecb36e350d3a802c35654cJakob Stoklund OlesenSTATISTIC(NumLocalSplits, "Number of split local live ranges"); 510db841f9c2b9a25fb5ecb36e350d3a802c35654cJakob Stoklund OlesenSTATISTIC(NumEvicted, "Number of interferences evicted"); 520db841f9c2b9a25fb5ecb36e350d3a802c35654cJakob Stoklund Olesen 53708d06f7fb5dfd9c8559aea07b042a88c65645f8Jakob Stoklund Olesenstatic cl::opt<SplitEditor::ComplementSpillMode> 54708d06f7fb5dfd9c8559aea07b042a88c65645f8Jakob Stoklund OlesenSplitSpillMode("split-spill-mode", cl::Hidden, 55708d06f7fb5dfd9c8559aea07b042a88c65645f8Jakob Stoklund Olesen cl::desc("Spill mode for splitting live ranges"), 56708d06f7fb5dfd9c8559aea07b042a88c65645f8Jakob Stoklund Olesen cl::values(clEnumValN(SplitEditor::SM_Partition, "default", "Default"), 57708d06f7fb5dfd9c8559aea07b042a88c65645f8Jakob Stoklund Olesen clEnumValN(SplitEditor::SM_Size, "size", "Optimize for size"), 58708d06f7fb5dfd9c8559aea07b042a88c65645f8Jakob Stoklund Olesen clEnumValN(SplitEditor::SM_Speed, "speed", "Optimize for speed"), 59708d06f7fb5dfd9c8559aea07b042a88c65645f8Jakob Stoklund Olesen clEnumValEnd), 60708d06f7fb5dfd9c8559aea07b042a88c65645f8Jakob Stoklund Olesen cl::init(SplitEditor::SM_Partition)); 61708d06f7fb5dfd9c8559aea07b042a88c65645f8Jakob Stoklund Olesen 62cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesenstatic RegisterRegAlloc greedyRegAlloc("greedy", "greedy register allocator", 63cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen createGreedyRegisterAllocator); 64cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 65cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesennamespace { 6692a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesenclass RAGreedy : public MachineFunctionPass, 6792a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen public RegAllocBase, 6892a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen private LiveRangeEdit::Delegate { 6992a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen 70cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen // context 71cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen MachineFunction *MF; 72cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 73cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen // analyses 74b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen SlotIndexes *Indexes; 754eed756153b84c211114a3e9186bf0cb55d4b394Benjamin Kramer MachineBlockFrequencyInfo *MBFI; 76f428eb6c1b09a2322b7a577b0bf2e49dd107bceaJakob Stoklund Olesen MachineDominatorTree *DomTree; 77d0bb5e2ca05d9c942223bf05e5940bb0c6cc9d3fJakob Stoklund Olesen MachineLoopInfo *Loops; 78b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen EdgeBundles *Bundles; 79b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen SpillPlacement *SpillPlacer; 80f42b66169d75301346e3685fd2b3e45e47806367Jakob Stoklund Olesen LiveDebugVariables *DebugVars; 81f428eb6c1b09a2322b7a577b0bf2e49dd107bceaJakob Stoklund Olesen 82cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen // state 83200241e4de11981523b3d14f3acab6129efed701Andy Gibbs OwningPtr<Spiller> SpillerInstance; 8498d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen std::priority_queue<std::pair<unsigned, unsigned> > Queue; 851a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen unsigned NextCascade; 8622a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen 8722a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // Live ranges pass through a number of stages as we try to allocate them. 8822a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // Some of the stages may also create new live ranges: 8922a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // 9022a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // - Region splitting. 9122a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // - Per-block splitting. 9222a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // - Local splitting. 9322a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // - Spilling. 9422a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // 9522a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // Ranges produced by one of the stages skip the previous stages when they are 9622a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // dequeued. This improves performance because we can skip interference checks 9722a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // that are unlikely to give any results. It also guarantees that the live 9822a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // range splitting algorithm terminates, something that is otherwise hard to 9922a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // ensure. 10022a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen enum LiveRangeStage { 101fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen /// Newly created live range that has never been queued. 102fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen RS_New, 103fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen 104fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen /// Only attempt assignment and eviction. Then requeue as RS_Split. 105fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen RS_Assign, 106fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen 107fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen /// Attempt live range splitting if assignment is impossible. 108fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen RS_Split, 109fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen 11049743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen /// Attempt more aggressive live range splitting that is guaranteed to make 11149743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen /// progress. This is used for split products that may not be making 11249743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen /// progress. 11349743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen RS_Split2, 11449743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen 115fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen /// Live range will be spilled. No more splitting will be attempted. 116fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen RS_Spill, 117fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen 118fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen /// There is nothing more we can do to this live range. Abort compilation 119fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen /// if it can't be assigned. 120fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen RS_Done 12122a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen }; 12222a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen 123ae43dac30037395cce2b54af0a02500985813183Eli Friedman#ifndef NDEBUG 124b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen static const char *const StageName[]; 125ae43dac30037395cce2b54af0a02500985813183Eli Friedman#endif 126b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen 1271a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen // RegInfo - Keep additional information about each live range. 1281a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen struct RegInfo { 1291a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen LiveRangeStage Stage; 1301a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen 1311a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen // Cascade - Eviction loop prevention. See canEvictInterference(). 1321a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen unsigned Cascade; 1331a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen 1341a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen RegInfo() : Stage(RS_New), Cascade(0) {} 1351a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen }; 1361a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen 1371a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen IndexedMap<RegInfo, VirtReg2IndexFunctor> ExtraRegInfo; 13822a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen 13922a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen LiveRangeStage getStage(const LiveInterval &VirtReg) const { 1401a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen return ExtraRegInfo[VirtReg.reg].Stage; 1411a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen } 1421a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen 1431a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen void setStage(const LiveInterval &VirtReg, LiveRangeStage Stage) { 1441a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen ExtraRegInfo.resize(MRI->getNumVirtRegs()); 1451a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen ExtraRegInfo[VirtReg.reg].Stage = Stage; 14622a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen } 14722a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen 14822a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen template<typename Iterator> 14922a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen void setStage(Iterator Begin, Iterator End, LiveRangeStage NewStage) { 1501a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen ExtraRegInfo.resize(MRI->getNumVirtRegs()); 151f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund Olesen for (;Begin != End; ++Begin) { 1521feb5854aeeda897e9318c8193d187673c8576b8Mark Lacey unsigned Reg = *Begin; 1531a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen if (ExtraRegInfo[Reg].Stage == RS_New) 1541a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen ExtraRegInfo[Reg].Stage = NewStage; 155f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund Olesen } 15622a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen } 157cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 15851458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen /// Cost of evicting interference. 15951458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen struct EvictionCost { 16051458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen unsigned BrokenHints; ///< Total number of broken hints. 16151458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen float MaxWeight; ///< Maximum spill weight evicted. 16251458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen 16351458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen EvictionCost(unsigned B = 0) : BrokenHints(B), MaxWeight(0) {} 16451458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen 1656ea2b9608a38e9b53d208ff85051e8e3ed53192cAndrew Trick bool isMax() const { return BrokenHints == ~0u; } 1666ea2b9608a38e9b53d208ff85051e8e3ed53192cAndrew Trick 16751458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen bool operator<(const EvictionCost &O) const { 16851458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen if (BrokenHints != O.BrokenHints) 16951458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen return BrokenHints < O.BrokenHints; 17051458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen return MaxWeight < O.MaxWeight; 17151458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen } 17251458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen }; 17351458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen 174b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen // splitting state. 175200241e4de11981523b3d14f3acab6129efed701Andy Gibbs OwningPtr<SplitAnalysis> SA; 176200241e4de11981523b3d14f3acab6129efed701Andy Gibbs OwningPtr<SplitEditor> SE; 177b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 178eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen /// Cached per-block interference maps 179eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen InterferenceCache IntfCache; 180eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen 1817b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen /// All basic blocks where the current register has uses. 18296dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen SmallVector<SpillPlacement::BlockConstraint, 8> SplitConstraints; 183b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 18496dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen /// Global live range splitting candidate info. 18596dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen struct GlobalSplitCandidate { 18600005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // Register intended for assignment, or 0. 18796dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen unsigned PhysReg; 18800005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen 18900005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // SplitKit interval index for this candidate. 19000005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen unsigned IntvIdx; 19100005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen 19200005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // Interference for PhysReg. 193c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen InterferenceCache::Cursor Intf; 19400005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen 19500005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // Bundles where this candidate should be live. 19696dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen BitVector LiveBundles; 1975db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen SmallVector<unsigned, 8> ActiveBlocks; 1985db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen 199c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen void reset(InterferenceCache &Cache, unsigned Reg) { 2005db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen PhysReg = Reg; 20100005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen IntvIdx = 0; 202c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen Intf.setPhysReg(Cache, Reg); 2035db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen LiveBundles.clear(); 2045db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen ActiveBlocks.clear(); 2055db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen } 20600005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen 20700005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // Set B[i] = C for every live bundle where B[i] was NoCand. 20800005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen unsigned getBundles(SmallVectorImpl<unsigned> &B, unsigned C) { 20900005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen unsigned Count = 0; 21000005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen for (int i = LiveBundles.find_first(); i >= 0; 21100005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen i = LiveBundles.find_next(i)) 21200005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen if (B[i] == NoCand) { 21300005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen B[i] = C; 21400005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen Count++; 21500005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen } 21600005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen return Count; 21700005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen } 21896dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen }; 21996dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen 22096dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen /// Candidate info for for each PhysReg in AllocationOrder. 22196dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen /// This vector never shrinks, but grows to the size of the largest register 22296dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen /// class. 22396dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen SmallVector<GlobalSplitCandidate, 32> GlobalCand; 22496dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen 22573f615b0bd822db3a2a8aab2fd4ed58f093c9769Reid Kleckner enum LLVM_ENUM_INT_TYPE(unsigned) { NoCand = ~0u }; 22600005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen 22700005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen /// Candidate map. Each edge bundle is assigned to a GlobalCand entry, or to 22800005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen /// NoCand which indicates the stack interval. 22900005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen SmallVector<unsigned, 32> BundleCand; 23000005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen 231cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesenpublic: 232cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen RAGreedy(); 233cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 234cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen /// Return the pass name. 235cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen virtual const char* getPassName() const { 236533f58ecdd8a4732c2f0e149387c4d8d8d4142deJakob Stoklund Olesen return "Greedy Register Allocator"; 237cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen } 238cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 239cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen /// RAGreedy analysis usage. 240cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen virtual void getAnalysisUsage(AnalysisUsage &AU) const; 241cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen virtual void releaseMemory(); 242cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen virtual Spiller &spiller() { return *SpillerInstance; } 24398d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen virtual void enqueue(LiveInterval *LI); 24498d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen virtual LiveInterval *dequeue(); 245ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen virtual unsigned selectOrSplit(LiveInterval&, 2461feb5854aeeda897e9318c8193d187673c8576b8Mark Lacey SmallVectorImpl<unsigned>&); 247cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 248cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen /// Perform register allocation. 249cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen virtual bool runOnMachineFunction(MachineFunction &mf); 250cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 251cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen static char ID; 252b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick 253b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trickprivate: 2547792e980c43536814ea42448db9799b4da32fef6Jakob Stoklund Olesen bool LRE_CanEraseVirtReg(unsigned); 2551d5b84508173b93faf513032b3847152e6060791Jakob Stoklund Olesen void LRE_WillShrinkVirtReg(unsigned); 256f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund Olesen void LRE_DidCloneVirtReg(unsigned, unsigned); 25792a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen 25803ef600623704e6dbf6ef0322062395e7b70bcd2Jakob Stoklund Olesen BlockFrequency calcSpillCost(); 25903ef600623704e6dbf6ef0322062395e7b70bcd2Jakob Stoklund Olesen bool addSplitConstraints(InterferenceCache::Cursor, BlockFrequency&); 260f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen void addThroughConstraints(InterferenceCache::Cursor, ArrayRef<unsigned>); 261c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen void growRegion(GlobalSplitCandidate &Cand); 26203ef600623704e6dbf6ef0322062395e7b70bcd2Jakob Stoklund Olesen BlockFrequency calcGlobalSplitCost(GlobalSplitCandidate&); 26387972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen bool calcCompactRegion(GlobalSplitCandidate&); 26400005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen void splitAroundRegion(LiveRangeEdit&, ArrayRef<unsigned>); 265034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen void calcGapWeights(unsigned, SmallVectorImpl<float>&); 2668adae96fd905daa8835b6fde5e74e25d818c7471Andrew Trick unsigned canReassign(LiveInterval &VirtReg, unsigned PhysReg); 26751458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen bool shouldEvict(LiveInterval &A, bool, LiveInterval &B, bool); 26851458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen bool canEvictInterference(LiveInterval&, unsigned, bool, EvictionCost&); 26951458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen void evictInterference(LiveInterval&, unsigned, 2701feb5854aeeda897e9318c8193d187673c8576b8Mark Lacey SmallVectorImpl<unsigned>&); 271b64d92e29f38002e52a22fe36ea2d488968e3537Jakob Stoklund Olesen 2726bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen unsigned tryAssign(LiveInterval&, AllocationOrder&, 2731feb5854aeeda897e9318c8193d187673c8576b8Mark Lacey SmallVectorImpl<unsigned>&); 27498c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen unsigned tryEvict(LiveInterval&, AllocationOrder&, 2751feb5854aeeda897e9318c8193d187673c8576b8Mark Lacey SmallVectorImpl<unsigned>&, unsigned = ~0u); 276b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen unsigned tryRegionSplit(LiveInterval&, AllocationOrder&, 2771feb5854aeeda897e9318c8193d187673c8576b8Mark Lacey SmallVectorImpl<unsigned>&); 278dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen unsigned tryBlockSplit(LiveInterval&, AllocationOrder&, 2791feb5854aeeda897e9318c8193d187673c8576b8Mark Lacey SmallVectorImpl<unsigned>&); 280d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen unsigned tryInstructionSplit(LiveInterval&, AllocationOrder&, 2811feb5854aeeda897e9318c8193d187673c8576b8Mark Lacey SmallVectorImpl<unsigned>&); 282034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen unsigned tryLocalSplit(LiveInterval&, AllocationOrder&, 2831feb5854aeeda897e9318c8193d187673c8576b8Mark Lacey SmallVectorImpl<unsigned>&); 284b64d92e29f38002e52a22fe36ea2d488968e3537Jakob Stoklund Olesen unsigned trySplit(LiveInterval&, AllocationOrder&, 2851feb5854aeeda897e9318c8193d187673c8576b8Mark Lacey SmallVectorImpl<unsigned>&); 286cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen}; 287cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen} // end anonymous namespace 288cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 289cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesenchar RAGreedy::ID = 0; 290cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 291b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen#ifndef NDEBUG 292b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesenconst char *const RAGreedy::StageName[] = { 293fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen "RS_New", 294fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen "RS_Assign", 295fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen "RS_Split", 29649743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen "RS_Split2", 297fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen "RS_Spill", 298fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen "RS_Done" 299b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen}; 300b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen#endif 301b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen 302200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen// Hysteresis to use when comparing floats. 303200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen// This helps stabilize decisions based on float comparisons. 304200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesenconst float Hysteresis = 0.98f; 305200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen 306200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen 307cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund OlesenFunctionPass* llvm::createGreedyRegisterAllocator() { 308cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen return new RAGreedy(); 309cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen} 310cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 3111a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund OlesenRAGreedy::RAGreedy(): MachineFunctionPass(ID) { 312cfafc54040cc9722995558124f253d05a038176bJakob Stoklund Olesen initializeLiveDebugVariablesPass(*PassRegistry::getPassRegistry()); 313b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen initializeSlotIndexesPass(*PassRegistry::getPassRegistry()); 314cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen initializeLiveIntervalsPass(*PassRegistry::getPassRegistry()); 315cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen initializeSlotIndexesPass(*PassRegistry::getPassRegistry()); 3165b220213bfe9c37c2bb41a7ae0804e06a14f1007Rafael Espindola initializeRegisterCoalescerPass(*PassRegistry::getPassRegistry()); 31742b7a71dc7381d1f38bf7b7201fc26dd80453364Andrew Trick initializeMachineSchedulerPass(*PassRegistry::getPassRegistry()); 318cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen initializeLiveStacksPass(*PassRegistry::getPassRegistry()); 319cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry()); 320cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen initializeMachineLoopInfoPass(*PassRegistry::getPassRegistry()); 321cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen initializeVirtRegMapPass(*PassRegistry::getPassRegistry()); 322042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen initializeLiveRegMatrixPass(*PassRegistry::getPassRegistry()); 323b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen initializeEdgeBundlesPass(*PassRegistry::getPassRegistry()); 324b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen initializeSpillPlacementPass(*PassRegistry::getPassRegistry()); 325cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen} 326cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 327cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesenvoid RAGreedy::getAnalysisUsage(AnalysisUsage &AU) const { 328cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.setPreservesCFG(); 3294eed756153b84c211114a3e9186bf0cb55d4b394Benjamin Kramer AU.addRequired<MachineBlockFrequencyInfo>(); 3304eed756153b84c211114a3e9186bf0cb55d4b394Benjamin Kramer AU.addPreserved<MachineBlockFrequencyInfo>(); 331cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addRequired<AliasAnalysis>(); 332cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addPreserved<AliasAnalysis>(); 333cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addRequired<LiveIntervals>(); 33405ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen AU.addPreserved<LiveIntervals>(); 335b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen AU.addRequired<SlotIndexes>(); 336cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addPreserved<SlotIndexes>(); 337cfafc54040cc9722995558124f253d05a038176bJakob Stoklund Olesen AU.addRequired<LiveDebugVariables>(); 338cfafc54040cc9722995558124f253d05a038176bJakob Stoklund Olesen AU.addPreserved<LiveDebugVariables>(); 339cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addRequired<LiveStacks>(); 340cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addPreserved<LiveStacks>(); 341f428eb6c1b09a2322b7a577b0bf2e49dd107bceaJakob Stoklund Olesen AU.addRequired<MachineDominatorTree>(); 342f428eb6c1b09a2322b7a577b0bf2e49dd107bceaJakob Stoklund Olesen AU.addPreserved<MachineDominatorTree>(); 343cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addRequired<MachineLoopInfo>(); 344cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addPreserved<MachineLoopInfo>(); 345cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addRequired<VirtRegMap>(); 346cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addPreserved<VirtRegMap>(); 347042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen AU.addRequired<LiveRegMatrix>(); 348042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen AU.addPreserved<LiveRegMatrix>(); 349b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen AU.addRequired<EdgeBundles>(); 350b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen AU.addRequired<SpillPlacement>(); 351cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen MachineFunctionPass::getAnalysisUsage(AU); 352cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen} 353cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 35492a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen 35592a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 35692a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen// LiveRangeEdit delegate methods 35792a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 35892a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen 3597792e980c43536814ea42448db9799b4da32fef6Jakob Stoklund Olesenbool RAGreedy::LRE_CanEraseVirtReg(unsigned VirtReg) { 360042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen if (VRM->hasPhys(VirtReg)) { 361042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen Matrix->unassign(LIS->getInterval(VirtReg)); 3627792e980c43536814ea42448db9799b4da32fef6Jakob Stoklund Olesen return true; 3637792e980c43536814ea42448db9799b4da32fef6Jakob Stoklund Olesen } 3647792e980c43536814ea42448db9799b4da32fef6Jakob Stoklund Olesen // Unassigned virtreg is probably in the priority queue. 3657792e980c43536814ea42448db9799b4da32fef6Jakob Stoklund Olesen // RegAllocBase will erase it after dequeueing. 3667792e980c43536814ea42448db9799b4da32fef6Jakob Stoklund Olesen return false; 3677792e980c43536814ea42448db9799b4da32fef6Jakob Stoklund Olesen} 36892a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen 3691d5b84508173b93faf513032b3847152e6060791Jakob Stoklund Olesenvoid RAGreedy::LRE_WillShrinkVirtReg(unsigned VirtReg) { 370042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen if (!VRM->hasPhys(VirtReg)) 3711d5b84508173b93faf513032b3847152e6060791Jakob Stoklund Olesen return; 3721d5b84508173b93faf513032b3847152e6060791Jakob Stoklund Olesen 3731d5b84508173b93faf513032b3847152e6060791Jakob Stoklund Olesen // Register is assigned, put it back on the queue for reassignment. 3741d5b84508173b93faf513032b3847152e6060791Jakob Stoklund Olesen LiveInterval &LI = LIS->getInterval(VirtReg); 375042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen Matrix->unassign(LI); 3761d5b84508173b93faf513032b3847152e6060791Jakob Stoklund Olesen enqueue(&LI); 3771d5b84508173b93faf513032b3847152e6060791Jakob Stoklund Olesen} 3781d5b84508173b93faf513032b3847152e6060791Jakob Stoklund Olesen 379f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund Olesenvoid RAGreedy::LRE_DidCloneVirtReg(unsigned New, unsigned Old) { 3800d4fea786670473b53d285be378e619399e03488Jakob Stoklund Olesen // Cloning a register we haven't even heard about yet? Just ignore it. 3810d4fea786670473b53d285be378e619399e03488Jakob Stoklund Olesen if (!ExtraRegInfo.inBounds(Old)) 3820d4fea786670473b53d285be378e619399e03488Jakob Stoklund Olesen return; 3830d4fea786670473b53d285be378e619399e03488Jakob Stoklund Olesen 384f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund Olesen // LRE may clone a virtual register because dead code elimination causes it to 385165e231c4295deb5cabd124d08e231b551bcc0b2Jakob Stoklund Olesen // be split into connected components. The new components are much smaller 386165e231c4295deb5cabd124d08e231b551bcc0b2Jakob Stoklund Olesen // than the original, so they should get a new chance at being assigned. 387f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund Olesen // same stage as the parent. 388165e231c4295deb5cabd124d08e231b551bcc0b2Jakob Stoklund Olesen ExtraRegInfo[Old].Stage = RS_Assign; 3891a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen ExtraRegInfo.grow(New); 3901a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen ExtraRegInfo[New] = ExtraRegInfo[Old]; 391f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund Olesen} 392f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund Olesen 393cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesenvoid RAGreedy::releaseMemory() { 394cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen SpillerInstance.reset(0); 3951a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen ExtraRegInfo.clear(); 3965db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen GlobalCand.clear(); 397cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen} 398cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 39998d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesenvoid RAGreedy::enqueue(LiveInterval *LI) { 40098d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen // Prioritize live ranges by size, assigning larger ranges first. 40198d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen // The queue holds (size, reg) pairs. 402107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen const unsigned Size = LI->getSize(); 403107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen const unsigned Reg = LI->reg; 40498d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen assert(TargetRegisterInfo::isVirtualRegister(Reg) && 40598d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen "Can only enqueue virtual registers"); 406107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen unsigned Prio; 40790c1d7ddfc65654f7efe72d56cad65d1af9e6b2aJakob Stoklund Olesen 4081a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen ExtraRegInfo.grow(Reg); 4091a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen if (ExtraRegInfo[Reg].Stage == RS_New) 410fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen ExtraRegInfo[Reg].Stage = RS_Assign; 411f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund Olesen 412cc07e04262fe4bc35469fbadc53d2ec7bfd02fe2Jakob Stoklund Olesen if (ExtraRegInfo[Reg].Stage == RS_Split) { 413eb29157d80847c207b77910bcd40a6a6c91ca5c5Jakob Stoklund Olesen // Unsplit ranges that couldn't be allocated immediately are deferred until 414a16a25ddeaf495b78b04e2a19feeac00d9824e63Jakob Stoklund Olesen // everything else has been allocated. 415a16a25ddeaf495b78b04e2a19feeac00d9824e63Jakob Stoklund Olesen Prio = Size; 416cc07e04262fe4bc35469fbadc53d2ec7bfd02fe2Jakob Stoklund Olesen } else { 4176ea2b9608a38e9b53d208ff85051e8e3ed53192cAndrew Trick if (ExtraRegInfo[Reg].Stage == RS_Assign && !LI->empty() && 4186ea2b9608a38e9b53d208ff85051e8e3ed53192cAndrew Trick LIS->intervalIsInOneMBB(*LI)) { 4196ea2b9608a38e9b53d208ff85051e8e3ed53192cAndrew Trick // Allocate original local ranges in linear instruction order. Since they 4206ea2b9608a38e9b53d208ff85051e8e3ed53192cAndrew Trick // are singly defined, this produces optimal coloring in the absence of 4216ea2b9608a38e9b53d208ff85051e8e3ed53192cAndrew Trick // global interference and other constraints. 422c0173e6f9f0de4497cd9b52b4f2269a57846f2acAndrew Trick Prio = LI->beginIndex().getInstrDistance(Indexes->getLastIndex()); 4236ea2b9608a38e9b53d208ff85051e8e3ed53192cAndrew Trick } 4246ea2b9608a38e9b53d208ff85051e8e3ed53192cAndrew Trick else { 4256ea2b9608a38e9b53d208ff85051e8e3ed53192cAndrew Trick // Allocate global and split ranges in long->short order. Long ranges that 4266ea2b9608a38e9b53d208ff85051e8e3ed53192cAndrew Trick // don't fit should be spilled (or split) ASAP so they don't create 4276ea2b9608a38e9b53d208ff85051e8e3ed53192cAndrew Trick // interference. Mark a bit to prioritize global above local ranges. 4286ea2b9608a38e9b53d208ff85051e8e3ed53192cAndrew Trick Prio = (1u << 29) + Size; 4296ea2b9608a38e9b53d208ff85051e8e3ed53192cAndrew Trick } 4306ea2b9608a38e9b53d208ff85051e8e3ed53192cAndrew Trick // Mark a higher bit to prioritize global and local above RS_Split. 4316ea2b9608a38e9b53d208ff85051e8e3ed53192cAndrew Trick Prio |= (1u << 31); 432d2a50734234a80893ad71da90d9f32032c47e000Jakob Stoklund Olesen 433eb29157d80847c207b77910bcd40a6a6c91ca5c5Jakob Stoklund Olesen // Boost ranges that have a physical register hint. 434fc6374439edf2f74da4026f4cea8e341d092be5cJakob Stoklund Olesen if (VRM->hasKnownPreference(Reg)) 435eb29157d80847c207b77910bcd40a6a6c91ca5c5Jakob Stoklund Olesen Prio |= (1u << 30); 436eb29157d80847c207b77910bcd40a6a6c91ca5c5Jakob Stoklund Olesen } 437bef4c3e069a66c8b2d5871468cb57978f44ddc54Andrew Trick // The virtual register number is a tie breaker for same-sized ranges. 438bef4c3e069a66c8b2d5871468cb57978f44ddc54Andrew Trick // Give lower vreg numbers higher priority to assign them first. 439e3b23cde80b19507f1d8b641a541e91ace0864dcJakob Stoklund Olesen Queue.push(std::make_pair(Prio, ~Reg)); 44090c1d7ddfc65654f7efe72d56cad65d1af9e6b2aJakob Stoklund Olesen} 44190c1d7ddfc65654f7efe72d56cad65d1af9e6b2aJakob Stoklund Olesen 44298d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund OlesenLiveInterval *RAGreedy::dequeue() { 44398d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen if (Queue.empty()) 44498d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen return 0; 445e3b23cde80b19507f1d8b641a541e91ace0864dcJakob Stoklund Olesen LiveInterval *LI = &LIS->getInterval(~Queue.top().second); 44698d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen Queue.pop(); 44798d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen return LI; 44898d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen} 449770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen 4506bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen 4516bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 4526bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen// Direct Assignment 4536bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 4546bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen 4556bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen/// tryAssign - Try to assign VirtReg to an available register. 4566bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesenunsigned RAGreedy::tryAssign(LiveInterval &VirtReg, 4576bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen AllocationOrder &Order, 4581feb5854aeeda897e9318c8193d187673c8576b8Mark Lacey SmallVectorImpl<unsigned> &NewVRegs) { 4596bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen Order.rewind(); 4606bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen unsigned PhysReg; 461042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen while ((PhysReg = Order.next())) 462042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen if (!Matrix->checkInterference(VirtReg, PhysReg)) 4636bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen break; 464f7999fe1cb2c2bdb0a4080efabb4743719ce45caJakob Stoklund Olesen if (!PhysReg || Order.isHint()) 4656bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen return PhysReg; 4666bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen 46751458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // PhysReg is available, but there may be a better choice. 46851458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen 46951458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // If we missed a simple hint, try to cheaply evict interference from the 47051458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // preferred register. 47151458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen if (unsigned Hint = MRI->getSimpleHint(VirtReg.reg)) 472042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen if (Order.isHint(Hint)) { 47351458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen DEBUG(dbgs() << "missed hint " << PrintReg(Hint, TRI) << '\n'); 47451458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen EvictionCost MaxCost(1); 47551458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen if (canEvictInterference(VirtReg, Hint, true, MaxCost)) { 47651458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen evictInterference(VirtReg, Hint, NewVRegs); 47751458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen return Hint; 47851458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen } 47951458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen } 48051458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen 48151458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // Try to evict interference from a cheaper alternative. 4826bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen unsigned Cost = TRI->getCostPerUse(PhysReg); 4836bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen 4846bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen // Most registers have 0 additional cost. 4856bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen if (!Cost) 4866bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen return PhysReg; 4876bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen 4886bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen DEBUG(dbgs() << PrintReg(PhysReg, TRI) << " is available at cost " << Cost 4896bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen << '\n'); 4906bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen unsigned CheapReg = tryEvict(VirtReg, Order, NewVRegs, Cost); 4916bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen return CheapReg ? CheapReg : PhysReg; 4926bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen} 4936bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen 4946bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen 495770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen//===----------------------------------------------------------------------===// 49698c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen// Interference eviction 49798c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 4982710638db2eb84cd7eefb8bb9a1b7e5c49413d45Jakob Stoklund Olesen 4998adae96fd905daa8835b6fde5e74e25d818c7471Andrew Trickunsigned RAGreedy::canReassign(LiveInterval &VirtReg, unsigned PrevReg) { 5008adae96fd905daa8835b6fde5e74e25d818c7471Andrew Trick AllocationOrder Order(VirtReg.reg, *VRM, RegClassInfo); 5018adae96fd905daa8835b6fde5e74e25d818c7471Andrew Trick unsigned PhysReg; 5028adae96fd905daa8835b6fde5e74e25d818c7471Andrew Trick while ((PhysReg = Order.next())) { 5038adae96fd905daa8835b6fde5e74e25d818c7471Andrew Trick if (PhysReg == PrevReg) 5048adae96fd905daa8835b6fde5e74e25d818c7471Andrew Trick continue; 5058adae96fd905daa8835b6fde5e74e25d818c7471Andrew Trick 5068adae96fd905daa8835b6fde5e74e25d818c7471Andrew Trick MCRegUnitIterator Units(PhysReg, TRI); 5078adae96fd905daa8835b6fde5e74e25d818c7471Andrew Trick for (; Units.isValid(); ++Units) { 5088adae96fd905daa8835b6fde5e74e25d818c7471Andrew Trick // Instantiate a "subquery", not to be confused with the Queries array. 5098adae96fd905daa8835b6fde5e74e25d818c7471Andrew Trick LiveIntervalUnion::Query subQ(&VirtReg, &Matrix->getLiveUnions()[*Units]); 5108adae96fd905daa8835b6fde5e74e25d818c7471Andrew Trick if (subQ.checkInterference()) 5118adae96fd905daa8835b6fde5e74e25d818c7471Andrew Trick break; 5128adae96fd905daa8835b6fde5e74e25d818c7471Andrew Trick } 5138adae96fd905daa8835b6fde5e74e25d818c7471Andrew Trick // If no units have interference, break out with the current PhysReg. 5148adae96fd905daa8835b6fde5e74e25d818c7471Andrew Trick if (!Units.isValid()) 5158adae96fd905daa8835b6fde5e74e25d818c7471Andrew Trick break; 5168adae96fd905daa8835b6fde5e74e25d818c7471Andrew Trick } 5178adae96fd905daa8835b6fde5e74e25d818c7471Andrew Trick if (PhysReg) 5188adae96fd905daa8835b6fde5e74e25d818c7471Andrew Trick DEBUG(dbgs() << "can reassign: " << VirtReg << " from " 5198adae96fd905daa8835b6fde5e74e25d818c7471Andrew Trick << PrintReg(PrevReg, TRI) << " to " << PrintReg(PhysReg, TRI) 5208adae96fd905daa8835b6fde5e74e25d818c7471Andrew Trick << '\n'); 5218adae96fd905daa8835b6fde5e74e25d818c7471Andrew Trick return PhysReg; 5228adae96fd905daa8835b6fde5e74e25d818c7471Andrew Trick} 5238adae96fd905daa8835b6fde5e74e25d818c7471Andrew Trick 52451458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// shouldEvict - determine if A should evict the assigned live range B. The 52551458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// eviction policy defined by this function together with the allocation order 52651458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// defined by enqueue() decides which registers ultimately end up being split 52751458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// and spilled. 528b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen/// 5291a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen/// Cascade numbers are used to prevent infinite loops if this function is a 5301a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen/// cyclic relation. 53151458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// 53251458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// @param A The live range to be assigned. 53351458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// @param IsHint True when A is about to be assigned to its preferred 53451458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// register. 53551458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// @param B The live range to be evicted. 53651458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// @param BreaksHint True when B is already assigned to its preferred register. 53751458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesenbool RAGreedy::shouldEvict(LiveInterval &A, bool IsHint, 53851458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen LiveInterval &B, bool BreaksHint) { 53949743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen bool CanSplit = getStage(B) < RS_Spill; 54051458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen 54151458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // Be fairly aggressive about following hints as long as the evictee can be 54251458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // split. 54351458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen if (CanSplit && IsHint && !BreaksHint) 54451458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen return true; 54551458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen 5461a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen return A.weight > B.weight; 547b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen} 548b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen 54951458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// canEvictInterference - Return true if all interferences between VirtReg and 55051458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// PhysReg can be evicted. When OnlyCheap is set, don't do anything 55151458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// 55251458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// @param VirtReg Live range that is about to be assigned. 55351458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// @param PhysReg Desired register for assignment. 55467c8978617c3bce9d07210f93f6c64c715f77695Dmitri Gribenko/// @param IsHint True when PhysReg is VirtReg's preferred register. 55551458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// @param MaxCost Only look for cheaper candidates and update with new cost 55651458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// when returning true. 55751458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// @returns True when interference can be evicted cheaper than MaxCost. 55898c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesenbool RAGreedy::canEvictInterference(LiveInterval &VirtReg, unsigned PhysReg, 55951458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen bool IsHint, EvictionCost &MaxCost) { 560042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen // It is only possible to evict virtual register interference. 561042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen if (Matrix->checkInterference(VirtReg, PhysReg) > LiveRegMatrix::IK_VirtReg) 562042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen return false; 563042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen 5646ea2b9608a38e9b53d208ff85051e8e3ed53192cAndrew Trick bool IsLocal = LIS->intervalIsInOneMBB(VirtReg); 5656ea2b9608a38e9b53d208ff85051e8e3ed53192cAndrew Trick 5661a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen // Find VirtReg's cascade number. This will be unassigned if VirtReg was never 5671a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen // involved in an eviction before. If a cascade number was assigned, deny 5681a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen // evicting anything with the same or a newer cascade number. This prevents 5691a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen // infinite eviction loops. 5701a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen // 5711a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen // This works out so a register without a cascade number is allowed to evict 5721a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen // anything, and it can be evicted by anything. 5731a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen unsigned Cascade = ExtraRegInfo[VirtReg.reg].Cascade; 5741a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen if (!Cascade) 5751a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen Cascade = NextCascade; 5761a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen 57751458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen EvictionCost Cost; 578042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) { 579042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen LiveIntervalUnion::Query &Q = Matrix->query(VirtReg, *Units); 5803f5bedf5cbde2cc2badc86b1a0b377f6efcde71cJakob Stoklund Olesen // If there is 10 or more interferences, chances are one is heavier. 58151458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen if (Q.collectInterferingVRegs(10) >= 10) 58298c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen return false; 58398c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen 5843f5bedf5cbde2cc2badc86b1a0b377f6efcde71cJakob Stoklund Olesen // Check if any interfering live range is heavier than MaxWeight. 5853f5bedf5cbde2cc2badc86b1a0b377f6efcde71cJakob Stoklund Olesen for (unsigned i = Q.interferingVRegs().size(); i; --i) { 5863f5bedf5cbde2cc2badc86b1a0b377f6efcde71cJakob Stoklund Olesen LiveInterval *Intf = Q.interferingVRegs()[i - 1]; 587042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen assert(TargetRegisterInfo::isVirtualRegister(Intf->reg) && 588042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen "Only expecting virtual register interference from query"); 58951458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // Never evict spill products. They cannot split or spill. 590fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen if (getStage(*Intf) == RS_Done) 5911a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen return false; 59251458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // Once a live range becomes small enough, it is urgent that we find a 59351458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // register for it. This is indicated by an infinite spill weight. These 59451458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // urgent live ranges get to evict almost anything. 5959cda1be0aa5e9e70ae493ef6944a8c202c1c70e6Jakob Stoklund Olesen // 5969cda1be0aa5e9e70ae493ef6944a8c202c1c70e6Jakob Stoklund Olesen // Also allow urgent evictions of unspillable ranges from a strictly 5979cda1be0aa5e9e70ae493ef6944a8c202c1c70e6Jakob Stoklund Olesen // larger allocation order. 5989cda1be0aa5e9e70ae493ef6944a8c202c1c70e6Jakob Stoklund Olesen bool Urgent = !VirtReg.isSpillable() && 5999cda1be0aa5e9e70ae493ef6944a8c202c1c70e6Jakob Stoklund Olesen (Intf->isSpillable() || 6009cda1be0aa5e9e70ae493ef6944a8c202c1c70e6Jakob Stoklund Olesen RegClassInfo.getNumAllocatableRegs(MRI->getRegClass(VirtReg.reg)) < 6019cda1be0aa5e9e70ae493ef6944a8c202c1c70e6Jakob Stoklund Olesen RegClassInfo.getNumAllocatableRegs(MRI->getRegClass(Intf->reg))); 60251458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // Only evict older cascades or live ranges without a cascade. 60351458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen unsigned IntfCascade = ExtraRegInfo[Intf->reg].Cascade; 60451458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen if (Cascade <= IntfCascade) { 60551458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen if (!Urgent) 60651458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen return false; 60751458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // We permit breaking cascades for urgent evictions. It should be the 60851458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // last resort, though, so make it really expensive. 60951458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen Cost.BrokenHints += 10; 61051458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen } 61151458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // Would this break a satisfied hint? 61251458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen bool BreaksHint = VRM->hasPreferredPhys(Intf->reg); 61351458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // Update eviction cost. 61451458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen Cost.BrokenHints += BreaksHint; 61551458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen Cost.MaxWeight = std::max(Cost.MaxWeight, Intf->weight); 61651458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // Abort if this would be too expensive. 61751458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen if (!(Cost < MaxCost)) 618b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen return false; 6196ea2b9608a38e9b53d208ff85051e8e3ed53192cAndrew Trick if (Urgent) 6206ea2b9608a38e9b53d208ff85051e8e3ed53192cAndrew Trick continue; 6216ea2b9608a38e9b53d208ff85051e8e3ed53192cAndrew Trick // If !MaxCost.isMax(), then we're just looking for a cheap register. 6226ea2b9608a38e9b53d208ff85051e8e3ed53192cAndrew Trick // Evicting another local live range in this case could lead to suboptimal 6236ea2b9608a38e9b53d208ff85051e8e3ed53192cAndrew Trick // coloring. 6248adae96fd905daa8835b6fde5e74e25d818c7471Andrew Trick if (!MaxCost.isMax() && IsLocal && LIS->intervalIsInOneMBB(*Intf) && 6258adae96fd905daa8835b6fde5e74e25d818c7471Andrew Trick !canReassign(*Intf, PhysReg)) { 6266ea2b9608a38e9b53d208ff85051e8e3ed53192cAndrew Trick return false; 6278adae96fd905daa8835b6fde5e74e25d818c7471Andrew Trick } 62851458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // Finally, apply the eviction policy for non-urgent evictions. 6296ea2b9608a38e9b53d208ff85051e8e3ed53192cAndrew Trick if (!shouldEvict(VirtReg, IsHint, *Intf, BreaksHint)) 63076395c9a31444fa86514473e0852cdd67752d0e8Jakob Stoklund Olesen return false; 6312710638db2eb84cd7eefb8bb9a1b7e5c49413d45Jakob Stoklund Olesen } 6322710638db2eb84cd7eefb8bb9a1b7e5c49413d45Jakob Stoklund Olesen } 63351458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen MaxCost = Cost; 63498c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen return true; 63598c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen} 63698c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen 63751458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// evictInterference - Evict any interferring registers that prevent VirtReg 63851458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// from being assigned to Physreg. This assumes that canEvictInterference 63951458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// returned true. 64051458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesenvoid RAGreedy::evictInterference(LiveInterval &VirtReg, unsigned PhysReg, 6411feb5854aeeda897e9318c8193d187673c8576b8Mark Lacey SmallVectorImpl<unsigned> &NewVRegs) { 64251458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // Make sure that VirtReg has a cascade number, and assign that cascade 64351458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // number to every evicted register. These live ranges than then only be 64451458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // evicted by a newer cascade, preventing infinite loops. 64551458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen unsigned Cascade = ExtraRegInfo[VirtReg.reg].Cascade; 64651458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen if (!Cascade) 64751458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen Cascade = ExtraRegInfo[VirtReg.reg].Cascade = NextCascade++; 64851458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen 64951458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen DEBUG(dbgs() << "evicting " << PrintReg(PhysReg, TRI) 65051458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen << " interference: Cascade " << Cascade << '\n'); 651042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen 652042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen // Collect all interfering virtregs first. 653042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen SmallVector<LiveInterval*, 8> Intfs; 654042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) { 655042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen LiveIntervalUnion::Query &Q = Matrix->query(VirtReg, *Units); 65651458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen assert(Q.seenAllInterferences() && "Didn't check all interfererences."); 657042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen ArrayRef<LiveInterval*> IVR = Q.interferingVRegs(); 658042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen Intfs.append(IVR.begin(), IVR.end()); 659042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen } 660042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen 661042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen // Evict them second. This will invalidate the queries. 662042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen for (unsigned i = 0, e = Intfs.size(); i != e; ++i) { 663042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen LiveInterval *Intf = Intfs[i]; 664042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen // The same VirtReg may be present in multiple RegUnits. Skip duplicates. 665042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen if (!VRM->hasPhys(Intf->reg)) 666042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen continue; 667042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen Matrix->unassign(*Intf); 668042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen assert((ExtraRegInfo[Intf->reg].Cascade < Cascade || 669042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen VirtReg.isSpillable() < Intf->isSpillable()) && 670042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen "Cannot decrease cascade number, illegal eviction"); 671042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen ExtraRegInfo[Intf->reg].Cascade = Cascade; 672042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen ++NumEvicted; 6731feb5854aeeda897e9318c8193d187673c8576b8Mark Lacey NewVRegs.push_back(Intf->reg); 67451458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen } 67551458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen} 67651458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen 67798c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen/// tryEvict - Try to evict all interferences for a physreg. 67876395c9a31444fa86514473e0852cdd67752d0e8Jakob Stoklund Olesen/// @param VirtReg Currently unassigned virtual register. 67976395c9a31444fa86514473e0852cdd67752d0e8Jakob Stoklund Olesen/// @param Order Physregs to try. 68076395c9a31444fa86514473e0852cdd67752d0e8Jakob Stoklund Olesen/// @return Physreg to assign VirtReg, or 0. 68198c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesenunsigned RAGreedy::tryEvict(LiveInterval &VirtReg, 68298c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen AllocationOrder &Order, 6831feb5854aeeda897e9318c8193d187673c8576b8Mark Lacey SmallVectorImpl<unsigned> &NewVRegs, 6846bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen unsigned CostPerUseLimit) { 68598c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen NamedRegionTimer T("Evict", TimerGroupName, TimePassesIsEnabled); 68698c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen 68751458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // Keep track of the cheapest interference seen so far. 68851458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen EvictionCost BestCost(~0u); 68998c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen unsigned BestPhys = 0; 6906d6132986d2ef14bbf9d76f5acbf2a0bace32d69Jakob Stoklund Olesen unsigned OrderLimit = Order.getOrder().size(); 69198c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen 69251458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // When we are just looking for a reduced cost per use, don't break any 69351458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // hints, and only evict smaller spill weights. 69451458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen if (CostPerUseLimit < ~0u) { 69551458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen BestCost.BrokenHints = 0; 69651458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen BestCost.MaxWeight = VirtReg.weight; 6976d6132986d2ef14bbf9d76f5acbf2a0bace32d69Jakob Stoklund Olesen 6986d6132986d2ef14bbf9d76f5acbf2a0bace32d69Jakob Stoklund Olesen // Check of any registers in RC are below CostPerUseLimit. 6996d6132986d2ef14bbf9d76f5acbf2a0bace32d69Jakob Stoklund Olesen const TargetRegisterClass *RC = MRI->getRegClass(VirtReg.reg); 7006d6132986d2ef14bbf9d76f5acbf2a0bace32d69Jakob Stoklund Olesen unsigned MinCost = RegClassInfo.getMinCost(RC); 7016d6132986d2ef14bbf9d76f5acbf2a0bace32d69Jakob Stoklund Olesen if (MinCost >= CostPerUseLimit) { 7026d6132986d2ef14bbf9d76f5acbf2a0bace32d69Jakob Stoklund Olesen DEBUG(dbgs() << RC->getName() << " minimum cost = " << MinCost 7036d6132986d2ef14bbf9d76f5acbf2a0bace32d69Jakob Stoklund Olesen << ", no cheaper registers to be found.\n"); 7046d6132986d2ef14bbf9d76f5acbf2a0bace32d69Jakob Stoklund Olesen return 0; 7056d6132986d2ef14bbf9d76f5acbf2a0bace32d69Jakob Stoklund Olesen } 7066d6132986d2ef14bbf9d76f5acbf2a0bace32d69Jakob Stoklund Olesen 7076d6132986d2ef14bbf9d76f5acbf2a0bace32d69Jakob Stoklund Olesen // It is normal for register classes to have a long tail of registers with 7086d6132986d2ef14bbf9d76f5acbf2a0bace32d69Jakob Stoklund Olesen // the same cost. We don't need to look at them if they're too expensive. 7096d6132986d2ef14bbf9d76f5acbf2a0bace32d69Jakob Stoklund Olesen if (TRI->getCostPerUse(Order.getOrder().back()) >= CostPerUseLimit) { 7106d6132986d2ef14bbf9d76f5acbf2a0bace32d69Jakob Stoklund Olesen OrderLimit = RegClassInfo.getLastCostChange(RC); 7116d6132986d2ef14bbf9d76f5acbf2a0bace32d69Jakob Stoklund Olesen DEBUG(dbgs() << "Only trying the first " << OrderLimit << " regs.\n"); 7126d6132986d2ef14bbf9d76f5acbf2a0bace32d69Jakob Stoklund Olesen } 71351458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen } 71451458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen 71598c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen Order.rewind(); 7166d6132986d2ef14bbf9d76f5acbf2a0bace32d69Jakob Stoklund Olesen while (unsigned PhysReg = Order.nextWithDups(OrderLimit)) { 7176bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen if (TRI->getCostPerUse(PhysReg) >= CostPerUseLimit) 7186bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen continue; 71951458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // The first use of a callee-saved register in a function has cost 1. 72051458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // Don't start using a CSR when the CostPerUseLimit is low. 72151458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen if (CostPerUseLimit == 1) 72251458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen if (unsigned CSR = RegClassInfo.getLastCalleeSavedAlias(PhysReg)) 72351458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen if (!MRI->isPhysRegUsed(CSR)) { 72451458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen DEBUG(dbgs() << PrintReg(PhysReg, TRI) << " would clobber CSR " 72551458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen << PrintReg(CSR, TRI) << '\n'); 72651458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen continue; 72751458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen } 72851458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen 72951458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen if (!canEvictInterference(VirtReg, PhysReg, false, BestCost)) 73098c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen continue; 73198c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen 73298c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen // Best so far. 73398c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen BestPhys = PhysReg; 73451458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen 73557f1e2cee06f9b57995727d786aeb1031c5376bdJakob Stoklund Olesen // Stop if the hint can be used. 736f7999fe1cb2c2bdb0a4080efabb4743719ce45caJakob Stoklund Olesen if (Order.isHint()) 73757f1e2cee06f9b57995727d786aeb1031c5376bdJakob Stoklund Olesen break; 7382710638db2eb84cd7eefb8bb9a1b7e5c49413d45Jakob Stoklund Olesen } 7392710638db2eb84cd7eefb8bb9a1b7e5c49413d45Jakob Stoklund Olesen 74098c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen if (!BestPhys) 74198c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen return 0; 74298c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen 74351458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen evictInterference(VirtReg, BestPhys, NewVRegs); 74498c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen return BestPhys; 745b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick} 746b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick 747770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen 748770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen//===----------------------------------------------------------------------===// 749b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen// Region Splitting 750b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen//===----------------------------------------------------------------------===// 751b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 7521b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen/// addSplitConstraints - Fill out the SplitConstraints vector based on the 7531b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen/// interference pattern in Physreg and its aliases. Add the constraints to 7541b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen/// SpillPlacement and return the static cost of this split in Cost, assuming 7551b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen/// that all preferences in SplitConstraints are met. 756f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen/// Return false if there are no bundles with positive bias. 757f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesenbool RAGreedy::addSplitConstraints(InterferenceCache::Cursor Intf, 75803ef600623704e6dbf6ef0322062395e7b70bcd2Jakob Stoklund Olesen BlockFrequency &Cost) { 759db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks(); 760eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen 761b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen // Reset interference dependent info. 762db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen SplitConstraints.resize(UseBlocks.size()); 76303ef600623704e6dbf6ef0322062395e7b70bcd2Jakob Stoklund Olesen BlockFrequency StaticCost = 0; 764db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen for (unsigned i = 0; i != UseBlocks.size(); ++i) { 765db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen const SplitAnalysis::BlockInfo &BI = UseBlocks[i]; 76696dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen SpillPlacement::BlockConstraint &BC = SplitConstraints[i]; 76796dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen 768f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen BC.Number = BI.MBB->getNumber(); 769eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen Intf.moveToBlock(BC.Number); 770db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen BC.Entry = BI.LiveIn ? SpillPlacement::PrefReg : SpillPlacement::DontCare; 771db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen BC.Exit = BI.LiveOut ? SpillPlacement::PrefReg : SpillPlacement::DontCare; 772453f4f01302f00651aae2fc7658f6e23a2beadb0David Blaikie BC.ChangesValue = BI.FirstDef.isValid(); 773b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 774eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen if (!Intf.hasInterference()) 775eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen continue; 776eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen 77796dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen // Number of spill code instructions to insert. 77896dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen unsigned Ins = 0; 77996dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen 78096dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen // Interference for the live-in value. 781eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen if (BI.LiveIn) { 7826c8afd728eb02742ce320ecd39bcf3774d8423b7Jakob Stoklund Olesen if (Intf.first() <= Indexes->getMBBStartIdx(BC.Number)) 783db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen BC.Entry = SpillPlacement::MustSpill, ++Ins; 784fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen else if (Intf.first() < BI.FirstInstr) 78596dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen BC.Entry = SpillPlacement::PrefSpill, ++Ins; 786fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen else if (Intf.first() < BI.LastInstr) 78796dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen ++Ins; 788a50c539b7a9e74597da34bfaea5429a48481f18bJakob Stoklund Olesen } 789b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 79096dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen // Interference for the live-out value. 791eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen if (BI.LiveOut) { 792612f7807c581eafb7c8105e1a55c8d839033bfb3Jakob Stoklund Olesen if (Intf.last() >= SA->getLastSplitPoint(BC.Number)) 793db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen BC.Exit = SpillPlacement::MustSpill, ++Ins; 794fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen else if (Intf.last() > BI.LastInstr) 79596dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen BC.Exit = SpillPlacement::PrefSpill, ++Ins; 796fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen else if (Intf.last() > BI.FirstInstr) 79796dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen ++Ins; 798b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen } 799b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 80096dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen // Accumulate the total frequency of inserted spill code. 80103ef600623704e6dbf6ef0322062395e7b70bcd2Jakob Stoklund Olesen while (Ins--) 80203ef600623704e6dbf6ef0322062395e7b70bcd2Jakob Stoklund Olesen StaticCost += SpillPlacer->getBlockFrequency(BC.Number); 803b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen } 804f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen Cost = StaticCost; 805db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen 8061b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen // Add constraints for use-blocks. Note that these are the only constraints 8071b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen // that may add a positive bias, it is downhill from here. 8081b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen SpillPlacer->addConstraints(SplitConstraints); 809f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen return SpillPlacer->scanActiveBundles(); 810f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen} 811db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen 812db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen 813f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen/// addThroughConstraints - Add constraints and links to SpillPlacer from the 814f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen/// live-through blocks in Blocks. 815f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesenvoid RAGreedy::addThroughConstraints(InterferenceCache::Cursor Intf, 816f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen ArrayRef<unsigned> Blocks) { 8171b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen const unsigned GroupSize = 8; 8181b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen SpillPlacement::BlockConstraint BCS[GroupSize]; 819f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen unsigned TBS[GroupSize]; 820f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen unsigned B = 0, T = 0; 821db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen 822f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen for (unsigned i = 0; i != Blocks.size(); ++i) { 823f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen unsigned Number = Blocks[i]; 8241b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen Intf.moveToBlock(Number); 8251b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen 8267b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen if (!Intf.hasInterference()) { 827f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen assert(T < GroupSize && "Array overflow"); 828f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen TBS[T] = Number; 829f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen if (++T == GroupSize) { 83039b5abf507b43da6b92f68b86406e0015ead18e9Frits van Bommel SpillPlacer->addLinks(makeArrayRef(TBS, T)); 831f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen T = 0; 832f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen } 8337b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen continue; 8341b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen } 8351b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen 836f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen assert(B < GroupSize && "Array overflow"); 837f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen BCS[B].Number = Number; 838f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen 8397b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen // Interference for the live-in value. 8407b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen if (Intf.first() <= Indexes->getMBBStartIdx(Number)) 8417b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen BCS[B].Entry = SpillPlacement::MustSpill; 8427b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen else 8437b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen BCS[B].Entry = SpillPlacement::PrefSpill; 8447b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen 8457b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen // Interference for the live-out value. 8467b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen if (Intf.last() >= SA->getLastSplitPoint(Number)) 8477b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen BCS[B].Exit = SpillPlacement::MustSpill; 8487b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen else 8497b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen BCS[B].Exit = SpillPlacement::PrefSpill; 8507b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen 8511b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen if (++B == GroupSize) { 8521b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen ArrayRef<SpillPlacement::BlockConstraint> Array(BCS, B); 8531b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen SpillPlacer->addConstraints(Array); 8541b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen B = 0; 8551b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen } 856db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen } 857db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen 8581b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen ArrayRef<SpillPlacement::BlockConstraint> Array(BCS, B); 8591b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen SpillPlacer->addConstraints(Array); 86039b5abf507b43da6b92f68b86406e0015ead18e9Frits van Bommel SpillPlacer->addLinks(makeArrayRef(TBS, T)); 861b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen} 862b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 863c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesenvoid RAGreedy::growRegion(GlobalSplitCandidate &Cand) { 8645db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen // Keep track of through blocks that have not been added to SpillPlacer. 8655db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen BitVector Todo = SA->getThroughBlocks(); 8665db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen SmallVectorImpl<unsigned> &ActiveBlocks = Cand.ActiveBlocks; 8675db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen unsigned AddedTo = 0; 868f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen#ifndef NDEBUG 869f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen unsigned Visited = 0; 870f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen#endif 8715db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen 872f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen for (;;) { 873f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen ArrayRef<unsigned> NewBundles = SpillPlacer->getRecentPositive(); 874f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen // Find new through blocks in the periphery of PrefRegBundles. 875f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen for (int i = 0, e = NewBundles.size(); i != e; ++i) { 876f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen unsigned Bundle = NewBundles[i]; 877f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen // Look at all blocks connected to Bundle in the full graph. 878f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen ArrayRef<unsigned> Blocks = Bundles->getBlocks(Bundle); 879f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen for (ArrayRef<unsigned>::iterator I = Blocks.begin(), E = Blocks.end(); 880f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen I != E; ++I) { 881f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen unsigned Block = *I; 8825db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen if (!Todo.test(Block)) 883f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen continue; 8845db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen Todo.reset(Block); 885f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen // This is a new through block. Add it to SpillPlacer later. 8865db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen ActiveBlocks.push_back(Block); 887f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen#ifndef NDEBUG 888f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen ++Visited; 889f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen#endif 890f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen } 891f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen } 892f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen // Any new blocks to add? 893549019792a8b14500cab093ac8f3c5f7331e86d7Jakob Stoklund Olesen if (ActiveBlocks.size() == AddedTo) 894549019792a8b14500cab093ac8f3c5f7331e86d7Jakob Stoklund Olesen break; 895b4666364f4db4889883d7a6c02a177ebcde7c240Jakob Stoklund Olesen 896b4666364f4db4889883d7a6c02a177ebcde7c240Jakob Stoklund Olesen // Compute through constraints from the interference, or assume that all 897b4666364f4db4889883d7a6c02a177ebcde7c240Jakob Stoklund Olesen // through blocks prefer spilling when forming compact regions. 898b4666364f4db4889883d7a6c02a177ebcde7c240Jakob Stoklund Olesen ArrayRef<unsigned> NewBlocks = makeArrayRef(ActiveBlocks).slice(AddedTo); 899b4666364f4db4889883d7a6c02a177ebcde7c240Jakob Stoklund Olesen if (Cand.PhysReg) 900b4666364f4db4889883d7a6c02a177ebcde7c240Jakob Stoklund Olesen addThroughConstraints(Cand.Intf, NewBlocks); 901b4666364f4db4889883d7a6c02a177ebcde7c240Jakob Stoklund Olesen else 902b87f91b063a0ac853735f2af3bd94fb8551a11ffJakob Stoklund Olesen // Provide a strong negative bias on through blocks to prevent unwanted 903b87f91b063a0ac853735f2af3bd94fb8551a11ffJakob Stoklund Olesen // liveness on loop backedges. 904b87f91b063a0ac853735f2af3bd94fb8551a11ffJakob Stoklund Olesen SpillPlacer->addPrefSpill(NewBlocks, /* Strong= */ true); 905549019792a8b14500cab093ac8f3c5f7331e86d7Jakob Stoklund Olesen AddedTo = ActiveBlocks.size(); 906549019792a8b14500cab093ac8f3c5f7331e86d7Jakob Stoklund Olesen 907f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen // Perhaps iterating can enable more bundles? 908f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen SpillPlacer->iterate(); 909f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen } 910f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen DEBUG(dbgs() << ", v=" << Visited); 911f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen} 91296dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen 91387972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen/// calcCompactRegion - Compute the set of edge bundles that should be live 91487972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen/// when splitting the current live range into compact regions. Compact 91587972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen/// regions can be computed without looking at interference. They are the 91687972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen/// regions formed by removing all the live-through blocks from the live range. 91787972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen/// 91887972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen/// Returns false if the current live range is already compact, or if the 91987972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen/// compact regions would form single block regions anyway. 92087972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesenbool RAGreedy::calcCompactRegion(GlobalSplitCandidate &Cand) { 92187972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen // Without any through blocks, the live range is already compact. 92287972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen if (!SA->getNumThroughBlocks()) 92387972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen return false; 92487972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen 92587972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen // Compact regions don't correspond to any physreg. 92687972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen Cand.reset(IntfCache, 0); 92787972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen 92887972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen DEBUG(dbgs() << "Compact region bundles"); 92987972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen 93087972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen // Use the spill placer to determine the live bundles. GrowRegion pretends 93187972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen // that all the through blocks have interference when PhysReg is unset. 93287972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen SpillPlacer->prepare(Cand.LiveBundles); 93387972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen 93487972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen // The static split cost will be zero since Cand.Intf reports no interference. 93503ef600623704e6dbf6ef0322062395e7b70bcd2Jakob Stoklund Olesen BlockFrequency Cost; 93687972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen if (!addSplitConstraints(Cand.Intf, Cost)) { 93787972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen DEBUG(dbgs() << ", none.\n"); 93887972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen return false; 93987972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen } 94087972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen 94187972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen growRegion(Cand); 94287972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen SpillPlacer->finish(); 94387972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen 94487972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen if (!Cand.LiveBundles.any()) { 94587972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen DEBUG(dbgs() << ", none.\n"); 94687972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen return false; 94787972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen } 94887972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen 94987972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen DEBUG({ 95087972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen for (int i = Cand.LiveBundles.find_first(); i>=0; 95187972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen i = Cand.LiveBundles.find_next(i)) 95287972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen dbgs() << " EB#" << i; 95387972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen dbgs() << ".\n"; 95487972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen }); 95587972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen return true; 95687972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen} 95787972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen 958200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen/// calcSpillCost - Compute how expensive it would be to split the live range in 959200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen/// SA around all use blocks instead of forming bundle regions. 96003ef600623704e6dbf6ef0322062395e7b70bcd2Jakob Stoklund OlesenBlockFrequency RAGreedy::calcSpillCost() { 96103ef600623704e6dbf6ef0322062395e7b70bcd2Jakob Stoklund Olesen BlockFrequency Cost = 0; 962200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks(); 963200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen for (unsigned i = 0; i != UseBlocks.size(); ++i) { 964200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen const SplitAnalysis::BlockInfo &BI = UseBlocks[i]; 965200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen unsigned Number = BI.MBB->getNumber(); 966200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen // We normally only need one spill instruction - a load or a store. 967200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen Cost += SpillPlacer->getBlockFrequency(Number); 968200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen 969200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen // Unless the value is redefined in the block. 9703f5beede1bb97ba4e06dc300e00b70e1013e7216Jakob Stoklund Olesen if (BI.LiveIn && BI.LiveOut && BI.FirstDef) 9713f5beede1bb97ba4e06dc300e00b70e1013e7216Jakob Stoklund Olesen Cost += SpillPlacer->getBlockFrequency(Number); 972200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen } 973200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen return Cost; 974200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen} 975200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen 976b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen/// calcGlobalSplitCost - Return the global split cost of following the split 977b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen/// pattern in LiveBundles. This cost should be added to the local cost of the 97896dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen/// interference pattern in SplitConstraints. 979b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen/// 98003ef600623704e6dbf6ef0322062395e7b70bcd2Jakob Stoklund OlesenBlockFrequency RAGreedy::calcGlobalSplitCost(GlobalSplitCandidate &Cand) { 98103ef600623704e6dbf6ef0322062395e7b70bcd2Jakob Stoklund Olesen BlockFrequency GlobalCost = 0; 9825db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen const BitVector &LiveBundles = Cand.LiveBundles; 983db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks(); 984db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen for (unsigned i = 0; i != UseBlocks.size(); ++i) { 985db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen const SplitAnalysis::BlockInfo &BI = UseBlocks[i]; 98696dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen SpillPlacement::BlockConstraint &BC = SplitConstraints[i]; 987874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen bool RegIn = LiveBundles[Bundles->getBundle(BC.Number, 0)]; 988874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen bool RegOut = LiveBundles[Bundles->getBundle(BC.Number, 1)]; 989874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen unsigned Ins = 0; 990874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen 991db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen if (BI.LiveIn) 992db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen Ins += RegIn != (BC.Entry == SpillPlacement::PrefReg); 993db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen if (BI.LiveOut) 994db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen Ins += RegOut != (BC.Exit == SpillPlacement::PrefReg); 99503ef600623704e6dbf6ef0322062395e7b70bcd2Jakob Stoklund Olesen while (Ins--) 99603ef600623704e6dbf6ef0322062395e7b70bcd2Jakob Stoklund Olesen GlobalCost += SpillPlacer->getBlockFrequency(BC.Number); 997b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen } 998db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen 9995db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen for (unsigned i = 0, e = Cand.ActiveBlocks.size(); i != e; ++i) { 10005db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen unsigned Number = Cand.ActiveBlocks[i]; 1001db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen bool RegIn = LiveBundles[Bundles->getBundle(Number, 0)]; 1002db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen bool RegOut = LiveBundles[Bundles->getBundle(Number, 1)]; 10039a54352879e5aaac2e2c37490e5cb7844550db8bJakob Stoklund Olesen if (!RegIn && !RegOut) 10049a54352879e5aaac2e2c37490e5cb7844550db8bJakob Stoklund Olesen continue; 10059a54352879e5aaac2e2c37490e5cb7844550db8bJakob Stoklund Olesen if (RegIn && RegOut) { 10069a54352879e5aaac2e2c37490e5cb7844550db8bJakob Stoklund Olesen // We need double spill code if this block has interference. 1007c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen Cand.Intf.moveToBlock(Number); 100803ef600623704e6dbf6ef0322062395e7b70bcd2Jakob Stoklund Olesen if (Cand.Intf.hasInterference()) { 100903ef600623704e6dbf6ef0322062395e7b70bcd2Jakob Stoklund Olesen GlobalCost += SpillPlacer->getBlockFrequency(Number); 101003ef600623704e6dbf6ef0322062395e7b70bcd2Jakob Stoklund Olesen GlobalCost += SpillPlacer->getBlockFrequency(Number); 101103ef600623704e6dbf6ef0322062395e7b70bcd2Jakob Stoklund Olesen } 10129a54352879e5aaac2e2c37490e5cb7844550db8bJakob Stoklund Olesen continue; 10139a54352879e5aaac2e2c37490e5cb7844550db8bJakob Stoklund Olesen } 10149a54352879e5aaac2e2c37490e5cb7844550db8bJakob Stoklund Olesen // live-in / stack-out or stack-in live-out. 10159a54352879e5aaac2e2c37490e5cb7844550db8bJakob Stoklund Olesen GlobalCost += SpillPlacer->getBlockFrequency(Number); 1016db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen } 1017b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen return GlobalCost; 1018b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen} 1019b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 102000005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen/// splitAroundRegion - Split the current live range around the regions 102100005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen/// determined by BundleCand and GlobalCand. 1022ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen/// 102300005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen/// Before calling this function, GlobalCand and BundleCand must be initialized 102400005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen/// so each bundle is assigned to a valid candidate, or NoCand for the 102500005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen/// stack-bound bundles. The shared SA/SE SplitAnalysis and SplitEditor 102600005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen/// objects must be initialized for the current live range, and intervals 102700005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen/// created for the used candidates. 1028ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen/// 102900005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen/// @param LREdit The LiveRangeEdit object handling the current split. 103000005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen/// @param UsedCands List of used GlobalCand entries. Every BundleCand value 103100005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen/// must appear in this list. 103200005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesenvoid RAGreedy::splitAroundRegion(LiveRangeEdit &LREdit, 103300005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen ArrayRef<unsigned> UsedCands) { 103400005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // These are the intervals created for new global ranges. We may create more 103500005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // intervals for local ranges. 103600005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen const unsigned NumGlobalIntvs = LREdit.size(); 103700005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen DEBUG(dbgs() << "splitAroundRegion with " << NumGlobalIntvs << " globals.\n"); 103800005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen assert(NumGlobalIntvs && "No global intervals configured"); 1039ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 10402d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen // Isolate even single instructions when dealing with a proper sub-class. 104169145baf36219b07a49d8ce14b4a04870e72a123Jakob Stoklund Olesen // That guarantees register class inflation for the stack interval because it 10422d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen // is all copies. 10432d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen unsigned Reg = SA->getParent().reg; 10442d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen bool SingleInstrs = RegClassInfo.isProperSubClass(MRI->getRegClass(Reg)); 10452d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen 104687360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen // First handle all the blocks with uses. 1047db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks(); 1048db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen for (unsigned i = 0; i != UseBlocks.size(); ++i) { 1049db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen const SplitAnalysis::BlockInfo &BI = UseBlocks[i]; 105000005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen unsigned Number = BI.MBB->getNumber(); 105100005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen unsigned IntvIn = 0, IntvOut = 0; 105200005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen SlotIndex IntfIn, IntfOut; 105300005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen if (BI.LiveIn) { 105400005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen unsigned CandIn = BundleCand[Bundles->getBundle(Number, 0)]; 105500005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen if (CandIn != NoCand) { 105600005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen GlobalSplitCandidate &Cand = GlobalCand[CandIn]; 105700005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen IntvIn = Cand.IntvIdx; 105800005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen Cand.Intf.moveToBlock(Number); 105900005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen IntfIn = Cand.Intf.first(); 106000005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen } 106100005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen } 106200005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen if (BI.LiveOut) { 106300005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen unsigned CandOut = BundleCand[Bundles->getBundle(Number, 1)]; 106400005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen if (CandOut != NoCand) { 106500005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen GlobalSplitCandidate &Cand = GlobalCand[CandOut]; 106600005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen IntvOut = Cand.IntvIdx; 106700005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen Cand.Intf.moveToBlock(Number); 106800005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen IntfOut = Cand.Intf.last(); 106900005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen } 107000005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen } 1071ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 1072fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen // Create separate intervals for isolated blocks with multiple uses. 107300005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen if (!IntvIn && !IntvOut) { 1074fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " isolated.\n"); 10752d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen if (SA->shouldSplitSingleBlock(BI, SingleInstrs)) 107687360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen SE->splitSingleBlock(BI); 1077fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen continue; 1078fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen } 1079fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen 108000005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen if (IntvIn && IntvOut) 108100005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen SE->splitLiveThroughBlock(Number, IntvIn, IntfIn, IntvOut, IntfOut); 108200005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen else if (IntvIn) 108300005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen SE->splitRegInBlock(BI, IntvIn, IntfIn); 1084b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen else 108500005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen SE->splitRegOutBlock(BI, IntvOut, IntfOut); 1086ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen } 1087ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 108800005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // Handle live-through blocks. The relevant live-through blocks are stored in 108900005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // the ActiveBlocks list with each candidate. We need to filter out 109000005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // duplicates. 109100005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen BitVector Todo = SA->getThroughBlocks(); 109200005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen for (unsigned c = 0; c != UsedCands.size(); ++c) { 109300005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen ArrayRef<unsigned> Blocks = GlobalCand[UsedCands[c]].ActiveBlocks; 109400005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen for (unsigned i = 0, e = Blocks.size(); i != e; ++i) { 109500005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen unsigned Number = Blocks[i]; 109600005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen if (!Todo.test(Number)) 109700005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen continue; 109800005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen Todo.reset(Number); 109900005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen 110000005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen unsigned IntvIn = 0, IntvOut = 0; 110100005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen SlotIndex IntfIn, IntfOut; 110200005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen 110300005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen unsigned CandIn = BundleCand[Bundles->getBundle(Number, 0)]; 110400005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen if (CandIn != NoCand) { 110500005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen GlobalSplitCandidate &Cand = GlobalCand[CandIn]; 110600005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen IntvIn = Cand.IntvIdx; 110700005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen Cand.Intf.moveToBlock(Number); 110800005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen IntfIn = Cand.Intf.first(); 110900005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen } 111000005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen 111100005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen unsigned CandOut = BundleCand[Bundles->getBundle(Number, 1)]; 111200005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen if (CandOut != NoCand) { 111300005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen GlobalSplitCandidate &Cand = GlobalCand[CandOut]; 111400005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen IntvOut = Cand.IntvIdx; 111500005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen Cand.Intf.moveToBlock(Number); 111600005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen IntfOut = Cand.Intf.last(); 111700005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen } 111800005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen if (!IntvIn && !IntvOut) 111900005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen continue; 112000005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen SE->splitLiveThroughBlock(Number, IntvIn, IntfIn, IntvOut, IntfOut); 112100005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen } 1122db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen } 1123db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen 11240db841f9c2b9a25fb5ecb36e350d3a802c35654cJakob Stoklund Olesen ++NumGlobalSplits; 1125ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 11265928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen SmallVector<unsigned, 8> IntvMap; 11275928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen SE->finish(&IntvMap); 11281feb5854aeeda897e9318c8193d187673c8576b8Mark Lacey DebugVars->splitRegister(Reg, LREdit.regs(), *LIS); 1129f42b66169d75301346e3685fd2b3e45e47806367Jakob Stoklund Olesen 11301a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen ExtraRegInfo.resize(MRI->getNumVirtRegs()); 1131b2abfa0bf30edf292a27a06e091d03983e644c9bJakob Stoklund Olesen unsigned OrigBlocks = SA->getNumLiveBlocks(); 11325928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen 11335928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen // Sort out the new intervals created by splitting. We get four kinds: 11345928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen // - Remainder intervals should not be split again. 11355928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen // - Candidate intervals can be assigned to Cand.PhysReg. 11365928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen // - Block-local splits are candidates for local splitting. 11375928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen // - DCE leftovers should go back on the queue. 11385928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen for (unsigned i = 0, e = LREdit.size(); i != e; ++i) { 11391feb5854aeeda897e9318c8193d187673c8576b8Mark Lacey LiveInterval &Reg = LIS->getInterval(LREdit.get(i)); 11405928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen 11415928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen // Ignore old intervals from DCE. 11421a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen if (getStage(Reg) != RS_New) 11435928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen continue; 11445928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen 11455928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen // Remainder interval. Don't try splitting again, spill if it doesn't 11465928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen // allocate. 11475928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen if (IntvMap[i] == 0) { 1148fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen setStage(Reg, RS_Spill); 11495928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen continue; 11505928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen } 11515928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen 115200005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // Global intervals. Allow repeated splitting as long as the number of live 115300005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // blocks is strictly decreasing. 115400005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen if (IntvMap[i] < NumGlobalIntvs) { 11551a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen if (SA->countLiveBlocks(&Reg) >= OrigBlocks) { 11569f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen DEBUG(dbgs() << "Main interval covers the same " << OrigBlocks 11579f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen << " blocks as original.\n"); 11589f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen // Don't allow repeated splitting as a safe guard against looping. 115949743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen setStage(Reg, RS_Split2); 11609f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen } 11619f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen continue; 11629f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen } 11639f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen 11649f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen // Other intervals are treated as new. This includes local intervals created 11659f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen // for blocks with multiple uses, and anything created by DCE. 11665928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen } 11675928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen 1168eb29157d80847c207b77910bcd40a6a6c91ca5c5Jakob Stoklund Olesen if (VerifyEnabled) 1169ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen MF->verify(this, "After splitting live range around region"); 1170ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen} 1171ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 1172b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesenunsigned RAGreedy::tryRegionSplit(LiveInterval &VirtReg, AllocationOrder &Order, 11731feb5854aeeda897e9318c8193d187673c8576b8Mark Lacey SmallVectorImpl<unsigned> &NewVRegs) { 1174c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen unsigned NumCands = 0; 117500005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen unsigned BestCand = NoCand; 117603ef600623704e6dbf6ef0322062395e7b70bcd2Jakob Stoklund Olesen BlockFrequency BestCost; 117700005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen SmallVector<unsigned, 8> UsedCands; 117800005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen 117900005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // Check if we can split this live range around a compact region. 1180a16a25ddeaf495b78b04e2a19feeac00d9824e63Jakob Stoklund Olesen bool HasCompact = calcCompactRegion(GlobalCand.front()); 118100005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen if (HasCompact) { 118200005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // Yes, keep GlobalCand[0] as the compact region candidate. 118300005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen NumCands = 1; 118403ef600623704e6dbf6ef0322062395e7b70bcd2Jakob Stoklund Olesen BestCost = BlockFrequency::getMaxFrequency(); 118500005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen } else { 118600005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // No benefit from the compact region, our fallback will be per-block 118700005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // splitting. Make sure we find a solution that is cheaper than spilling. 118803ef600623704e6dbf6ef0322062395e7b70bcd2Jakob Stoklund Olesen BestCost = calcSpillCost(); 118900005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen DEBUG(dbgs() << "Cost of isolating all blocks = " << BestCost << '\n'); 119000005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen } 119196dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen 1192b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen Order.rewind(); 1193c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen while (unsigned PhysReg = Order.next()) { 1194f1c709837bd11c5383fce3b8a026a7c8eaabba86Jakob Stoklund Olesen // Discard bad candidates before we run out of interference cache cursors. 1195f1c709837bd11c5383fce3b8a026a7c8eaabba86Jakob Stoklund Olesen // This will only affect register classes with a lot of registers (>32). 1196f1c709837bd11c5383fce3b8a026a7c8eaabba86Jakob Stoklund Olesen if (NumCands == IntfCache.getMaxCursors()) { 1197f1c709837bd11c5383fce3b8a026a7c8eaabba86Jakob Stoklund Olesen unsigned WorstCount = ~0u; 1198f1c709837bd11c5383fce3b8a026a7c8eaabba86Jakob Stoklund Olesen unsigned Worst = 0; 1199f1c709837bd11c5383fce3b8a026a7c8eaabba86Jakob Stoklund Olesen for (unsigned i = 0; i != NumCands; ++i) { 120000005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen if (i == BestCand || !GlobalCand[i].PhysReg) 1201f1c709837bd11c5383fce3b8a026a7c8eaabba86Jakob Stoklund Olesen continue; 1202f1c709837bd11c5383fce3b8a026a7c8eaabba86Jakob Stoklund Olesen unsigned Count = GlobalCand[i].LiveBundles.count(); 1203f1c709837bd11c5383fce3b8a026a7c8eaabba86Jakob Stoklund Olesen if (Count < WorstCount) 1204f1c709837bd11c5383fce3b8a026a7c8eaabba86Jakob Stoklund Olesen Worst = i, WorstCount = Count; 1205f1c709837bd11c5383fce3b8a026a7c8eaabba86Jakob Stoklund Olesen } 1206f1c709837bd11c5383fce3b8a026a7c8eaabba86Jakob Stoklund Olesen --NumCands; 1207f1c709837bd11c5383fce3b8a026a7c8eaabba86Jakob Stoklund Olesen GlobalCand[Worst] = GlobalCand[NumCands]; 12087bdf0060a00f04ad03d3c6f294d8db6f4951dbc2Jakob Stoklund Olesen if (BestCand == NumCands) 12097bdf0060a00f04ad03d3c6f294d8db6f4951dbc2Jakob Stoklund Olesen BestCand = Worst; 1210f1c709837bd11c5383fce3b8a026a7c8eaabba86Jakob Stoklund Olesen } 1211f1c709837bd11c5383fce3b8a026a7c8eaabba86Jakob Stoklund Olesen 1212c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen if (GlobalCand.size() <= NumCands) 1213c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen GlobalCand.resize(NumCands+1); 1214c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen GlobalSplitCandidate &Cand = GlobalCand[NumCands]; 1215c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen Cand.reset(IntfCache, PhysReg); 121696dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen 1217c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen SpillPlacer->prepare(Cand.LiveBundles); 121803ef600623704e6dbf6ef0322062395e7b70bcd2Jakob Stoklund Olesen BlockFrequency Cost; 1219c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen if (!addSplitConstraints(Cand.Intf, Cost)) { 1220f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen DEBUG(dbgs() << PrintReg(PhysReg, TRI) << "\tno positive bundles\n"); 12211b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen continue; 12221b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen } 1223f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen DEBUG(dbgs() << PrintReg(PhysReg, TRI) << "\tstatic = " << Cost); 1224200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen if (Cost >= BestCost) { 1225200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen DEBUG({ 1226200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen if (BestCand == NoCand) 1227200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen dbgs() << " worse than no bundles\n"; 1228200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen else 1229200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen dbgs() << " worse than " 1230200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen << PrintReg(GlobalCand[BestCand].PhysReg, TRI) << '\n'; 1231200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen }); 1232b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen continue; 1233874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen } 1234c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen growRegion(Cand); 1235ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 12369efa2a263ea470caacef1c85f6ca45e32bf516d3Jakob Stoklund Olesen SpillPlacer->finish(); 12379efa2a263ea470caacef1c85f6ca45e32bf516d3Jakob Stoklund Olesen 1238ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // No live bundles, defer to splitSingleBlocks(). 1239c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen if (!Cand.LiveBundles.any()) { 1240874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen DEBUG(dbgs() << " no bundles.\n"); 1241ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen continue; 1242874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen } 1243ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 1244c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen Cost += calcGlobalSplitCost(Cand); 1245874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen DEBUG({ 1246874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen dbgs() << ", total = " << Cost << " with bundles"; 1247c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen for (int i = Cand.LiveBundles.find_first(); i>=0; 1248c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen i = Cand.LiveBundles.find_next(i)) 1249874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen dbgs() << " EB#" << i; 1250874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen dbgs() << ".\n"; 1251874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen }); 1252200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen if (Cost < BestCost) { 1253c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen BestCand = NumCands; 125403ef600623704e6dbf6ef0322062395e7b70bcd2Jakob Stoklund Olesen BestCost = Cost; 1255b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen } 1256c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen ++NumCands; 1257b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen } 1258ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 125900005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // No solutions found, fall back to single block splitting. 126000005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen if (!HasCompact && BestCand == NoCand) 1261ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen return 0; 1262ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 126300005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // Prepare split editor. 126420942dcd8634ad75091fe89669868cfebf74e869Jakob Stoklund Olesen LiveRangeEdit LREdit(&VirtReg, NewVRegs, *MF, *LIS, VRM, this); 1265708d06f7fb5dfd9c8559aea07b042a88c65645f8Jakob Stoklund Olesen SE->reset(LREdit, SplitSpillMode); 126600005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen 126700005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // Assign all edge bundles to the preferred candidate, or NoCand. 126800005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen BundleCand.assign(Bundles->getNumBundles(), NoCand); 126900005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen 127000005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // Assign bundles for the best candidate region. 127100005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen if (BestCand != NoCand) { 127200005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen GlobalSplitCandidate &Cand = GlobalCand[BestCand]; 127300005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen if (unsigned B = Cand.getBundles(BundleCand, BestCand)) { 127400005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen UsedCands.push_back(BestCand); 127500005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen Cand.IntvIdx = SE->openIntv(); 127600005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen DEBUG(dbgs() << "Split for " << PrintReg(Cand.PhysReg, TRI) << " in " 127700005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen << B << " bundles, intv " << Cand.IntvIdx << ".\n"); 127832668ea7a290ee1cb6bfe8cd677cdd4e5df05b4dChandler Carruth (void)B; 127900005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen } 128000005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen } 128100005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen 128200005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // Assign bundles for the compact region. 128300005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen if (HasCompact) { 128400005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen GlobalSplitCandidate &Cand = GlobalCand.front(); 128500005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen assert(!Cand.PhysReg && "Compact region has no physreg"); 128600005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen if (unsigned B = Cand.getBundles(BundleCand, 0)) { 128700005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen UsedCands.push_back(0); 128800005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen Cand.IntvIdx = SE->openIntv(); 128900005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen DEBUG(dbgs() << "Split for compact region in " << B << " bundles, intv " 129000005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen << Cand.IntvIdx << ".\n"); 129132668ea7a290ee1cb6bfe8cd677cdd4e5df05b4dChandler Carruth (void)B; 129200005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen } 129300005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen } 129400005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen 129500005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen splitAroundRegion(LREdit, UsedCands); 1296b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen return 0; 1297b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen} 1298b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 1299ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 1300ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen//===----------------------------------------------------------------------===// 1301dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen// Per-Block Splitting 1302dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen//===----------------------------------------------------------------------===// 1303dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen 1304dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen/// tryBlockSplit - Split a global live range around every block with uses. This 1305dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen/// creates a lot of local live ranges, that will be split by tryLocalSplit if 1306dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen/// they don't allocate. 1307dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesenunsigned RAGreedy::tryBlockSplit(LiveInterval &VirtReg, AllocationOrder &Order, 13081feb5854aeeda897e9318c8193d187673c8576b8Mark Lacey SmallVectorImpl<unsigned> &NewVRegs) { 1309dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen assert(&SA->getParent() == &VirtReg && "Live range wasn't analyzed"); 1310dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen unsigned Reg = VirtReg.reg; 1311dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen bool SingleInstrs = RegClassInfo.isProperSubClass(MRI->getRegClass(Reg)); 131220942dcd8634ad75091fe89669868cfebf74e869Jakob Stoklund Olesen LiveRangeEdit LREdit(&VirtReg, NewVRegs, *MF, *LIS, VRM, this); 1313708d06f7fb5dfd9c8559aea07b042a88c65645f8Jakob Stoklund Olesen SE->reset(LREdit, SplitSpillMode); 1314dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks(); 1315dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen for (unsigned i = 0; i != UseBlocks.size(); ++i) { 1316dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen const SplitAnalysis::BlockInfo &BI = UseBlocks[i]; 1317dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen if (SA->shouldSplitSingleBlock(BI, SingleInstrs)) 1318dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen SE->splitSingleBlock(BI); 1319dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen } 1320dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen // No blocks were split. 1321dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen if (LREdit.empty()) 1322dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen return 0; 1323dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen 1324dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen // We did split for some blocks. 1325a9c41d39d1adc92107e095aca6f851aed71b6a5fJakob Stoklund Olesen SmallVector<unsigned, 8> IntvMap; 1326a9c41d39d1adc92107e095aca6f851aed71b6a5fJakob Stoklund Olesen SE->finish(&IntvMap); 13271f8804263ffc5e6843d81f5c7bd9c739aa90fde5Jakob Stoklund Olesen 13281f8804263ffc5e6843d81f5c7bd9c739aa90fde5Jakob Stoklund Olesen // Tell LiveDebugVariables about the new ranges. 13291feb5854aeeda897e9318c8193d187673c8576b8Mark Lacey DebugVars->splitRegister(Reg, LREdit.regs(), *LIS); 13301f8804263ffc5e6843d81f5c7bd9c739aa90fde5Jakob Stoklund Olesen 1331a9c41d39d1adc92107e095aca6f851aed71b6a5fJakob Stoklund Olesen ExtraRegInfo.resize(MRI->getNumVirtRegs()); 1332a9c41d39d1adc92107e095aca6f851aed71b6a5fJakob Stoklund Olesen 1333a9c41d39d1adc92107e095aca6f851aed71b6a5fJakob Stoklund Olesen // Sort out the new intervals created by splitting. The remainder interval 1334a9c41d39d1adc92107e095aca6f851aed71b6a5fJakob Stoklund Olesen // goes straight to spilling, the new local ranges get to stay RS_New. 1335a9c41d39d1adc92107e095aca6f851aed71b6a5fJakob Stoklund Olesen for (unsigned i = 0, e = LREdit.size(); i != e; ++i) { 13361feb5854aeeda897e9318c8193d187673c8576b8Mark Lacey LiveInterval &LI = LIS->getInterval(LREdit.get(i)); 1337a9c41d39d1adc92107e095aca6f851aed71b6a5fJakob Stoklund Olesen if (getStage(LI) == RS_New && IntvMap[i] == 0) 1338a9c41d39d1adc92107e095aca6f851aed71b6a5fJakob Stoklund Olesen setStage(LI, RS_Spill); 1339a9c41d39d1adc92107e095aca6f851aed71b6a5fJakob Stoklund Olesen } 1340a9c41d39d1adc92107e095aca6f851aed71b6a5fJakob Stoklund Olesen 1341dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen if (VerifyEnabled) 1342dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen MF->verify(this, "After splitting live range around basic blocks"); 1343dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen return 0; 1344dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen} 1345dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen 1346d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen 1347d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 1348d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen// Per-Instruction Splitting 1349d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 1350d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen 1351d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen/// tryInstructionSplit - Split a live range around individual instructions. 1352d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen/// This is normally not worthwhile since the spiller is doing essentially the 1353d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen/// same thing. However, when the live range is in a constrained register 1354d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen/// class, it may help to insert copies such that parts of the live range can 1355d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen/// be moved to a larger register class. 1356d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen/// 1357d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen/// This is similar to spilling to a larger register class. 1358d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesenunsigned 1359d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund OlesenRAGreedy::tryInstructionSplit(LiveInterval &VirtReg, AllocationOrder &Order, 13601feb5854aeeda897e9318c8193d187673c8576b8Mark Lacey SmallVectorImpl<unsigned> &NewVRegs) { 1361d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen // There is no point to this if there are no larger sub-classes. 1362d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen if (!RegClassInfo.isProperSubClass(MRI->getRegClass(VirtReg.reg))) 1363d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen return 0; 1364d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen 1365d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen // Always enable split spill mode, since we're effectively spilling to a 1366d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen // register. 1367d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen LiveRangeEdit LREdit(&VirtReg, NewVRegs, *MF, *LIS, VRM, this); 1368d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen SE->reset(LREdit, SplitEditor::SM_Size); 1369d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen 1370d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen ArrayRef<SlotIndex> Uses = SA->getUseSlots(); 1371d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen if (Uses.size() <= 1) 1372d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen return 0; 1373d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen 1374d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen DEBUG(dbgs() << "Split around " << Uses.size() << " individual instrs.\n"); 1375d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen 1376d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen // Split around every non-copy instruction. 1377d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen for (unsigned i = 0; i != Uses.size(); ++i) { 1378d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen if (const MachineInstr *MI = Indexes->getInstructionFromIndex(Uses[i])) 1379d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen if (MI->isFullCopy()) { 1380d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen DEBUG(dbgs() << " skip:\t" << Uses[i] << '\t' << *MI); 1381d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen continue; 1382d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen } 1383d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen SE->openIntv(); 1384d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen SlotIndex SegStart = SE->enterIntvBefore(Uses[i]); 1385d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen SlotIndex SegStop = SE->leaveIntvAfter(Uses[i]); 1386d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen SE->useIntv(SegStart, SegStop); 1387d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen } 1388d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen 1389d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen if (LREdit.empty()) { 1390d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen DEBUG(dbgs() << "All uses were copies.\n"); 1391d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen return 0; 1392d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen } 1393d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen 1394d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen SmallVector<unsigned, 8> IntvMap; 1395d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen SE->finish(&IntvMap); 13961feb5854aeeda897e9318c8193d187673c8576b8Mark Lacey DebugVars->splitRegister(VirtReg.reg, LREdit.regs(), *LIS); 1397d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen ExtraRegInfo.resize(MRI->getNumVirtRegs()); 1398d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen 1399d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen // Assign all new registers to RS_Spill. This was the last chance. 1400d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen setStage(LREdit.begin(), LREdit.end(), RS_Spill); 1401d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen return 0; 1402d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen} 1403d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen 1404d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen 1405dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen//===----------------------------------------------------------------------===// 1406034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen// Local Splitting 1407034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 1408034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1409034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1410034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// calcGapWeights - Compute the maximum spill weight that needs to be evicted 1411034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// in order to use PhysReg between two entries in SA->UseSlots. 1412034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// 1413034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// GapWeight[i] represents the gap between UseSlots[i] and UseSlots[i+1]. 1414034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// 1415034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesenvoid RAGreedy::calcGapWeights(unsigned PhysReg, 1416034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen SmallVectorImpl<float> &GapWeight) { 1417db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen assert(SA->getUseBlocks().size() == 1 && "Not a local interval"); 1418db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen const SplitAnalysis::BlockInfo &BI = SA->getUseBlocks().front(); 1419b20b518f800293ea6b2bed04134c71293ac52403Jakob Stoklund Olesen ArrayRef<SlotIndex> Uses = SA->getUseSlots(); 1420034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const unsigned NumGaps = Uses.size()-1; 1421034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1422034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Start and end points for the interference check. 1423fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen SlotIndex StartIdx = 1424fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen BI.LiveIn ? BI.FirstInstr.getBaseIndex() : BI.FirstInstr; 1425fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen SlotIndex StopIdx = 1426fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen BI.LiveOut ? BI.LastInstr.getBoundaryIndex() : BI.LastInstr; 1427034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1428034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen GapWeight.assign(NumGaps, 0.0f); 1429034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1430034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Add interference from each overlapping register. 1431042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) { 1432042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen if (!Matrix->query(const_cast<LiveInterval&>(SA->getParent()), *Units) 1433042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen .checkInterference()) 1434034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen continue; 1435034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1436fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen // We know that VirtReg is a continuous interval from FirstInstr to 1437fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen // LastInstr, so we don't need InterferenceQuery. 1438034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // 1439034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Interference that overlaps an instruction is counted in both gaps 1440034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // surrounding the instruction. The exception is interference before 1441034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // StartIdx and after StopIdx. 1442034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // 1443042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen LiveIntervalUnion::SegmentIter IntI = 1444042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen Matrix->getLiveUnions()[*Units] .find(StartIdx); 1445034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen for (unsigned Gap = 0; IntI.valid() && IntI.start() < StopIdx; ++IntI) { 1446034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Skip the gaps before IntI. 1447034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen while (Uses[Gap+1].getBoundaryIndex() < IntI.start()) 1448034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (++Gap == NumGaps) 1449034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen break; 1450034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (Gap == NumGaps) 1451034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen break; 1452034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1453034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Update the gaps covered by IntI. 1454034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const float weight = IntI.value()->weight; 1455034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen for (; Gap != NumGaps; ++Gap) { 1456034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen GapWeight[Gap] = std::max(GapWeight[Gap], weight); 1457034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (Uses[Gap+1].getBaseIndex() >= IntI.stop()) 1458034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen break; 1459034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1460034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (Gap == NumGaps) 1461034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen break; 1462034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1463034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1464042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen 1465042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen // Add fixed interference. 1466042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) { 14674f3b5e8c9232e43d1291aab8db5f5698d7ee0ea4Matthias Braun const LiveRange &LR = LIS->getRegUnit(*Units); 14684f3b5e8c9232e43d1291aab8db5f5698d7ee0ea4Matthias Braun LiveRange::const_iterator I = LR.find(StartIdx); 14694f3b5e8c9232e43d1291aab8db5f5698d7ee0ea4Matthias Braun LiveRange::const_iterator E = LR.end(); 1470042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen 1471042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen // Same loop as above. Mark any overlapped gaps as HUGE_VALF. 1472042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen for (unsigned Gap = 0; I != E && I->start < StopIdx; ++I) { 1473042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen while (Uses[Gap+1].getBoundaryIndex() < I->start) 1474042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen if (++Gap == NumGaps) 1475042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen break; 1476042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen if (Gap == NumGaps) 1477042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen break; 1478042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen 1479042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen for (; Gap != NumGaps; ++Gap) { 1480042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen GapWeight[Gap] = HUGE_VALF; 1481042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen if (Uses[Gap+1].getBaseIndex() >= I->end) 1482042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen break; 1483042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen } 1484042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen if (Gap == NumGaps) 1485042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen break; 1486042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen } 1487042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen } 1488034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen} 1489034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1490034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// tryLocalSplit - Try to split VirtReg into smaller intervals inside its only 1491034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// basic block. 1492034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// 1493034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesenunsigned RAGreedy::tryLocalSplit(LiveInterval &VirtReg, AllocationOrder &Order, 14941feb5854aeeda897e9318c8193d187673c8576b8Mark Lacey SmallVectorImpl<unsigned> &NewVRegs) { 1495db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen assert(SA->getUseBlocks().size() == 1 && "Not a local interval"); 1496db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen const SplitAnalysis::BlockInfo &BI = SA->getUseBlocks().front(); 1497034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1498034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Note that it is possible to have an interval that is live-in or live-out 1499034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // while only covering a single block - A phi-def can use undef values from 1500034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // predecessors, and the block could be a single-block loop. 1501034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // We don't bother doing anything clever about such a case, we simply assume 1502fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen // that the interval is continuous from FirstInstr to LastInstr. We should 1503fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen // make sure that we don't do anything illegal to such an interval, though. 1504034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1505b20b518f800293ea6b2bed04134c71293ac52403Jakob Stoklund Olesen ArrayRef<SlotIndex> Uses = SA->getUseSlots(); 1506034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (Uses.size() <= 2) 1507034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen return 0; 1508034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const unsigned NumGaps = Uses.size()-1; 1509034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1510034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen DEBUG({ 1511034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen dbgs() << "tryLocalSplit: "; 1512034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen for (unsigned i = 0, e = Uses.size(); i != e; ++i) 1513b20b518f800293ea6b2bed04134c71293ac52403Jakob Stoklund Olesen dbgs() << ' ' << Uses[i]; 1514034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen dbgs() << '\n'; 1515034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen }); 1516034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1517a6d513f47467b90344a74624d4fb77673942e3ceJakob Stoklund Olesen // If VirtReg is live across any register mask operands, compute a list of 1518a6d513f47467b90344a74624d4fb77673942e3ceJakob Stoklund Olesen // gaps with register masks. 1519a6d513f47467b90344a74624d4fb77673942e3ceJakob Stoklund Olesen SmallVector<unsigned, 8> RegMaskGaps; 1520042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen if (Matrix->checkRegMaskInterference(VirtReg)) { 1521a6d513f47467b90344a74624d4fb77673942e3ceJakob Stoklund Olesen // Get regmask slots for the whole block. 1522a6d513f47467b90344a74624d4fb77673942e3ceJakob Stoklund Olesen ArrayRef<SlotIndex> RMS = LIS->getRegMaskSlotsInBlock(BI.MBB->getNumber()); 1523cac5fa39bd861861018bb2c3f0b36cc71c2caa38Jakob Stoklund Olesen DEBUG(dbgs() << RMS.size() << " regmasks in block:"); 1524a6d513f47467b90344a74624d4fb77673942e3ceJakob Stoklund Olesen // Constrain to VirtReg's live range. 1525cac5fa39bd861861018bb2c3f0b36cc71c2caa38Jakob Stoklund Olesen unsigned ri = std::lower_bound(RMS.begin(), RMS.end(), 1526cac5fa39bd861861018bb2c3f0b36cc71c2caa38Jakob Stoklund Olesen Uses.front().getRegSlot()) - RMS.begin(); 1527a6d513f47467b90344a74624d4fb77673942e3ceJakob Stoklund Olesen unsigned re = RMS.size(); 1528a6d513f47467b90344a74624d4fb77673942e3ceJakob Stoklund Olesen for (unsigned i = 0; i != NumGaps && ri != re; ++i) { 1529cac5fa39bd861861018bb2c3f0b36cc71c2caa38Jakob Stoklund Olesen // Look for Uses[i] <= RMS <= Uses[i+1]. 1530cac5fa39bd861861018bb2c3f0b36cc71c2caa38Jakob Stoklund Olesen assert(!SlotIndex::isEarlierInstr(RMS[ri], Uses[i])); 1531cac5fa39bd861861018bb2c3f0b36cc71c2caa38Jakob Stoklund Olesen if (SlotIndex::isEarlierInstr(Uses[i+1], RMS[ri])) 1532a6d513f47467b90344a74624d4fb77673942e3ceJakob Stoklund Olesen continue; 1533cac5fa39bd861861018bb2c3f0b36cc71c2caa38Jakob Stoklund Olesen // Skip a regmask on the same instruction as the last use. It doesn't 1534cac5fa39bd861861018bb2c3f0b36cc71c2caa38Jakob Stoklund Olesen // overlap the live range. 1535cac5fa39bd861861018bb2c3f0b36cc71c2caa38Jakob Stoklund Olesen if (SlotIndex::isSameInstr(Uses[i+1], RMS[ri]) && i+1 == NumGaps) 1536cac5fa39bd861861018bb2c3f0b36cc71c2caa38Jakob Stoklund Olesen break; 1537cac5fa39bd861861018bb2c3f0b36cc71c2caa38Jakob Stoklund Olesen DEBUG(dbgs() << ' ' << RMS[ri] << ':' << Uses[i] << '-' << Uses[i+1]); 1538a6d513f47467b90344a74624d4fb77673942e3ceJakob Stoklund Olesen RegMaskGaps.push_back(i); 1539cac5fa39bd861861018bb2c3f0b36cc71c2caa38Jakob Stoklund Olesen // Advance ri to the next gap. A regmask on one of the uses counts in 1540cac5fa39bd861861018bb2c3f0b36cc71c2caa38Jakob Stoklund Olesen // both gaps. 1541cac5fa39bd861861018bb2c3f0b36cc71c2caa38Jakob Stoklund Olesen while (ri != re && SlotIndex::isEarlierInstr(RMS[ri], Uses[i+1])) 1542cac5fa39bd861861018bb2c3f0b36cc71c2caa38Jakob Stoklund Olesen ++ri; 1543a6d513f47467b90344a74624d4fb77673942e3ceJakob Stoklund Olesen } 1544cac5fa39bd861861018bb2c3f0b36cc71c2caa38Jakob Stoklund Olesen DEBUG(dbgs() << '\n'); 1545a6d513f47467b90344a74624d4fb77673942e3ceJakob Stoklund Olesen } 1546a6d513f47467b90344a74624d4fb77673942e3ceJakob Stoklund Olesen 1547b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // Since we allow local split results to be split again, there is a risk of 1548b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // creating infinite loops. It is tempting to require that the new live 1549b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // ranges have less instructions than the original. That would guarantee 1550b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // convergence, but it is too strict. A live range with 3 instructions can be 1551b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // split 2+3 (including the COPY), and we want to allow that. 1552b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // 1553b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // Instead we use these rules: 1554b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // 155549743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen // 1. Allow any split for ranges with getStage() < RS_Split2. (Except for the 1556b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // noop split, of course). 155749743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen // 2. Require progress be made for ranges with getStage() == RS_Split2. All 1558b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // the new ranges must have fewer instructions than before the split. 155949743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen // 3. New ranges with the same number of instructions are marked RS_Split2, 1560b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // smaller ranges are marked RS_New. 1561b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // 1562b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // These rules allow a 3 -> 2+3 split once, which we need. They also prevent 1563b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // excessive splitting and infinite loops. 1564b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // 156549743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen bool ProgressRequired = getStage(VirtReg) >= RS_Split2; 1566034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1567b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // Best split candidate. 1568034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen unsigned BestBefore = NumGaps; 1569034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen unsigned BestAfter = 0; 1570034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen float BestDiff = 0; 1571034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 157203ef600623704e6dbf6ef0322062395e7b70bcd2Jakob Stoklund Olesen const float blockFreq = 157303ef600623704e6dbf6ef0322062395e7b70bcd2Jakob Stoklund Olesen SpillPlacer->getBlockFrequency(BI.MBB->getNumber()).getFrequency() * 157403ef600623704e6dbf6ef0322062395e7b70bcd2Jakob Stoklund Olesen (1.0f / BlockFrequency::getEntryFrequency()); 1575034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen SmallVector<float, 8> GapWeight; 1576034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1577034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen Order.rewind(); 1578034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen while (unsigned PhysReg = Order.next()) { 1579034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Keep track of the largest spill weight that would need to be evicted in 1580034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // order to make use of PhysReg between UseSlots[i] and UseSlots[i+1]. 1581034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen calcGapWeights(PhysReg, GapWeight); 1582034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1583a6d513f47467b90344a74624d4fb77673942e3ceJakob Stoklund Olesen // Remove any gaps with regmask clobbers. 1584042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen if (Matrix->checkRegMaskInterference(VirtReg, PhysReg)) 1585a6d513f47467b90344a74624d4fb77673942e3ceJakob Stoklund Olesen for (unsigned i = 0, e = RegMaskGaps.size(); i != e; ++i) 1586a6d513f47467b90344a74624d4fb77673942e3ceJakob Stoklund Olesen GapWeight[RegMaskGaps[i]] = HUGE_VALF; 1587a6d513f47467b90344a74624d4fb77673942e3ceJakob Stoklund Olesen 1588034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Try to find the best sequence of gaps to close. 1589034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // The new spill weight must be larger than any gap interference. 1590034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1591034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // We will split before Uses[SplitBefore] and after Uses[SplitAfter]. 1592b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen unsigned SplitBefore = 0, SplitAfter = 1; 1593034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1594034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // MaxGap should always be max(GapWeight[SplitBefore..SplitAfter-1]). 1595034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // It is the spill weight that needs to be evicted. 1596034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen float MaxGap = GapWeight[0]; 1597034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1598034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen for (;;) { 1599034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Live before/after split? 1600034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const bool LiveBefore = SplitBefore != 0 || BI.LiveIn; 1601034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const bool LiveAfter = SplitAfter != NumGaps || BI.LiveOut; 1602034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1603034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen DEBUG(dbgs() << PrintReg(PhysReg, TRI) << ' ' 1604034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen << Uses[SplitBefore] << '-' << Uses[SplitAfter] 1605034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen << " i=" << MaxGap); 1606034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1607034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Stop before the interval gets so big we wouldn't be making progress. 1608034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (!LiveBefore && !LiveAfter) { 1609034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen DEBUG(dbgs() << " all\n"); 1610034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen break; 1611034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1612034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Should the interval be extended or shrunk? 1613034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen bool Shrink = true; 1614034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1615b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // How many gaps would the new range have? 1616b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen unsigned NewGaps = LiveBefore + SplitAfter - SplitBefore + LiveAfter; 1617b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen 1618b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // Legally, without causing looping? 1619b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen bool Legal = !ProgressRequired || NewGaps < NumGaps; 1620b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen 1621b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen if (Legal && MaxGap < HUGE_VALF) { 1622b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // Estimate the new spill weight. Each instruction reads or writes the 1623b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // register. Conservatively assume there are no read-modify-write 1624b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // instructions. 1625034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // 1626b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // Try to guess the size of the new interval. 1627b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen const float EstWeight = normalizeSpillWeight(blockFreq * (NewGaps + 1), 1628b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen Uses[SplitBefore].distance(Uses[SplitAfter]) + 1629b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen (LiveBefore + LiveAfter)*SlotIndex::InstrDist); 1630034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Would this split be possible to allocate? 1631034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Never allocate all gaps, we wouldn't be making progress. 163266446c803a11a26e4bb39b74091d146ac850ae4cJakob Stoklund Olesen DEBUG(dbgs() << " w=" << EstWeight); 163366446c803a11a26e4bb39b74091d146ac850ae4cJakob Stoklund Olesen if (EstWeight * Hysteresis >= MaxGap) { 1634034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen Shrink = false; 163566446c803a11a26e4bb39b74091d146ac850ae4cJakob Stoklund Olesen float Diff = EstWeight - MaxGap; 1636034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (Diff > BestDiff) { 1637034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen DEBUG(dbgs() << " (best)"); 163866446c803a11a26e4bb39b74091d146ac850ae4cJakob Stoklund Olesen BestDiff = Hysteresis * Diff; 1639034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen BestBefore = SplitBefore; 1640034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen BestAfter = SplitAfter; 1641034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1642034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1643034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1644034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1645034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Try to shrink. 1646034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (Shrink) { 1647b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen if (++SplitBefore < SplitAfter) { 1648034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen DEBUG(dbgs() << " shrink\n"); 1649034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Recompute the max when necessary. 1650034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (GapWeight[SplitBefore - 1] >= MaxGap) { 1651034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen MaxGap = GapWeight[SplitBefore]; 1652034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen for (unsigned i = SplitBefore + 1; i != SplitAfter; ++i) 1653034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen MaxGap = std::max(MaxGap, GapWeight[i]); 1654034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1655034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen continue; 1656034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1657034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen MaxGap = 0; 1658034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1659034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1660034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Try to extend the interval. 1661034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (SplitAfter >= NumGaps) { 1662034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen DEBUG(dbgs() << " end\n"); 1663034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen break; 1664034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1665034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1666034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen DEBUG(dbgs() << " extend\n"); 1667b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen MaxGap = std::max(MaxGap, GapWeight[SplitAfter++]); 1668034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1669034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1670034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1671034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Didn't find any candidates? 1672034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (BestBefore == NumGaps) 1673034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen return 0; 1674034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1675034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen DEBUG(dbgs() << "Best local split range: " << Uses[BestBefore] 1676034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen << '-' << Uses[BestAfter] << ", " << BestDiff 1677034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen << ", " << (BestAfter - BestBefore + 1) << " instrs\n"); 1678034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 167920942dcd8634ad75091fe89669868cfebf74e869Jakob Stoklund Olesen LiveRangeEdit LREdit(&VirtReg, NewVRegs, *MF, *LIS, VRM, this); 1680bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen SE->reset(LREdit); 1681bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen 1682bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen SE->openIntv(); 1683bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen SlotIndex SegStart = SE->enterIntvBefore(Uses[BestBefore]); 1684bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen SlotIndex SegStop = SE->leaveIntvAfter(Uses[BestAfter]); 1685bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen SE->useIntv(SegStart, SegStop); 1686b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen SmallVector<unsigned, 8> IntvMap; 1687b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen SE->finish(&IntvMap); 16881feb5854aeeda897e9318c8193d187673c8576b8Mark Lacey DebugVars->splitRegister(VirtReg.reg, LREdit.regs(), *LIS); 1689b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen 1690b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // If the new range has the same number of instructions as before, mark it as 169149743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen // RS_Split2 so the next split will be forced to make progress. Otherwise, 1692b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // leave the new intervals as RS_New so they can compete. 1693b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen bool LiveBefore = BestBefore != 0 || BI.LiveIn; 1694b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen bool LiveAfter = BestAfter != NumGaps || BI.LiveOut; 1695b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen unsigned NewGaps = LiveBefore + BestAfter - BestBefore + LiveAfter; 1696b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen if (NewGaps >= NumGaps) { 1697b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen DEBUG(dbgs() << "Tagging non-progress ranges: "); 1698b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen assert(!ProgressRequired && "Didn't make progress when it was required."); 1699b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen for (unsigned i = 0, e = IntvMap.size(); i != e; ++i) 1700b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen if (IntvMap[i] == 1) { 17011feb5854aeeda897e9318c8193d187673c8576b8Mark Lacey setStage(LIS->getInterval(LREdit.get(i)), RS_Split2); 17021feb5854aeeda897e9318c8193d187673c8576b8Mark Lacey DEBUG(dbgs() << PrintReg(LREdit.get(i))); 1703b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen } 1704b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen DEBUG(dbgs() << '\n'); 1705b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen } 17060db841f9c2b9a25fb5ecb36e350d3a802c35654cJakob Stoklund Olesen ++NumLocalSplits; 1707034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1708034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen return 0; 1709034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen} 1710034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1711034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 1712ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen// Live Range Splitting 1713ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen//===----------------------------------------------------------------------===// 1714ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 1715ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen/// trySplit - Try to split VirtReg or one of its interferences, making it 1716ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen/// assignable. 1717ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen/// @return Physreg when VirtReg may be assigned and/or new NewVRegs. 1718ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesenunsigned RAGreedy::trySplit(LiveInterval &VirtReg, AllocationOrder &Order, 17191feb5854aeeda897e9318c8193d187673c8576b8Mark Lacey SmallVectorImpl<unsigned>&NewVRegs) { 1720ccfa446450c9e3e0b3591343c4c5bea1e4cdc043Jakob Stoklund Olesen // Ranges must be Split2 or less. 1721ccfa446450c9e3e0b3591343c4c5bea1e4cdc043Jakob Stoklund Olesen if (getStage(VirtReg) >= RS_Spill) 1722ccfa446450c9e3e0b3591343c4c5bea1e4cdc043Jakob Stoklund Olesen return 0; 1723ccfa446450c9e3e0b3591343c4c5bea1e4cdc043Jakob Stoklund Olesen 1724034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Local intervals are handled separately. 1725a2ebf60ef2c434428af7f810b13327ab50245a67Jakob Stoklund Olesen if (LIS->intervalIsInOneMBB(VirtReg)) { 1726a2ebf60ef2c434428af7f810b13327ab50245a67Jakob Stoklund Olesen NamedRegionTimer T("Local Splitting", TimerGroupName, TimePassesIsEnabled); 172722a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen SA->analyze(&VirtReg); 1728d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen unsigned PhysReg = tryLocalSplit(VirtReg, Order, NewVRegs); 1729d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen if (PhysReg || !NewVRegs.empty()) 1730d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen return PhysReg; 1731d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen return tryInstructionSplit(VirtReg, Order, NewVRegs); 1732a2ebf60ef2c434428af7f810b13327ab50245a67Jakob Stoklund Olesen } 1733a2ebf60ef2c434428af7f810b13327ab50245a67Jakob Stoklund Olesen 1734a2ebf60ef2c434428af7f810b13327ab50245a67Jakob Stoklund Olesen NamedRegionTimer T("Global Splitting", TimerGroupName, TimePassesIsEnabled); 1735ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 173622a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen SA->analyze(&VirtReg); 173722a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen 17387d6b6a05b549da70b4473f015c97954c2a422724Jakob Stoklund Olesen // FIXME: SplitAnalysis may repair broken live ranges coming from the 17397d6b6a05b549da70b4473f015c97954c2a422724Jakob Stoklund Olesen // coalescer. That may cause the range to become allocatable which means that 17407d6b6a05b549da70b4473f015c97954c2a422724Jakob Stoklund Olesen // tryRegionSplit won't be making progress. This check should be replaced with 17417d6b6a05b549da70b4473f015c97954c2a422724Jakob Stoklund Olesen // an assertion when the coalescer is fixed. 17427d6b6a05b549da70b4473f015c97954c2a422724Jakob Stoklund Olesen if (SA->didRepairRange()) { 17437d6b6a05b549da70b4473f015c97954c2a422724Jakob Stoklund Olesen // VirtReg has changed, so all cached queries are invalid. 1744042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen Matrix->invalidateVirtRegs(); 17457d6b6a05b549da70b4473f015c97954c2a422724Jakob Stoklund Olesen if (unsigned PhysReg = tryAssign(VirtReg, Order, NewVRegs)) 17467d6b6a05b549da70b4473f015c97954c2a422724Jakob Stoklund Olesen return PhysReg; 17477d6b6a05b549da70b4473f015c97954c2a422724Jakob Stoklund Olesen } 17487d6b6a05b549da70b4473f015c97954c2a422724Jakob Stoklund Olesen 174949743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen // First try to split around a region spanning multiple blocks. RS_Split2 175049743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen // ranges already made dubious progress with region splitting, so they go 175149743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen // straight to single block splitting. 175249743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen if (getStage(VirtReg) < RS_Split2) { 175349743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen unsigned PhysReg = tryRegionSplit(VirtReg, Order, NewVRegs); 175449743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen if (PhysReg || !NewVRegs.empty()) 175549743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen return PhysReg; 175649743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen } 1757ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 1758dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen // Then isolate blocks. 1759dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen return tryBlockSplit(VirtReg, Order, NewVRegs); 1760ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen} 1761ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 1762ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 1763b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen//===----------------------------------------------------------------------===// 1764770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen// Main Entry Point 1765770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen//===----------------------------------------------------------------------===// 1766770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen 1767770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesenunsigned RAGreedy::selectOrSplit(LiveInterval &VirtReg, 17681feb5854aeeda897e9318c8193d187673c8576b8Mark Lacey SmallVectorImpl<unsigned> &NewVRegs) { 1769770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen // First try assigning a free register. 17705f2316a3b55f88dab2190212210770180a32aa95Jakob Stoklund Olesen AllocationOrder Order(VirtReg.reg, *VRM, RegClassInfo); 17716bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen if (unsigned PhysReg = tryAssign(VirtReg, Order, NewVRegs)) 17726bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen return PhysReg; 1773b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick 1774b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen LiveRangeStage Stage = getStage(VirtReg); 17751a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen DEBUG(dbgs() << StageName[Stage] 17761a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen << " Cascade " << ExtraRegInfo[VirtReg.reg].Cascade << '\n'); 1777b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen 177876395c9a31444fa86514473e0852cdd67752d0e8Jakob Stoklund Olesen // Try to evict a less worthy live range, but only for ranges from the primary 1779fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen // queue. The RS_Split ranges already failed to do this, and they should not 178076395c9a31444fa86514473e0852cdd67752d0e8Jakob Stoklund Olesen // get a second chance until they have been split. 1781fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen if (Stage != RS_Split) 178276395c9a31444fa86514473e0852cdd67752d0e8Jakob Stoklund Olesen if (unsigned PhysReg = tryEvict(VirtReg, Order, NewVRegs)) 178376395c9a31444fa86514473e0852cdd67752d0e8Jakob Stoklund Olesen return PhysReg; 1784b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick 1785ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen assert(NewVRegs.empty() && "Cannot append to existing NewVRegs"); 1786ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 1787107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen // The first time we see a live range, don't try to split or spill. 1788107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen // Wait until the second time, when all smaller ranges have been allocated. 1789107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen // This gives a better picture of the interference to split around. 1790fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen if (Stage < RS_Split) { 1791fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen setStage(VirtReg, RS_Split); 1792c1655e1a3c3a566b91b0513b56d61b58da1e36baJakob Stoklund Olesen DEBUG(dbgs() << "wait for second round\n"); 17931feb5854aeeda897e9318c8193d187673c8576b8Mark Lacey NewVRegs.push_back(VirtReg.reg); 1794107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen return 0; 1795107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen } 1796107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen 1797bf4e10f2f69db24c107cb61d6fe10ed5b2047374Jakob Stoklund Olesen // If we couldn't allocate a register from spilling, there is probably some 1798bf4e10f2f69db24c107cb61d6fe10ed5b2047374Jakob Stoklund Olesen // invalid inline assembly. The base class wil report it. 1799fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen if (Stage >= RS_Done || !VirtReg.isSpillable()) 1800bf4e10f2f69db24c107cb61d6fe10ed5b2047374Jakob Stoklund Olesen return ~0u; 180122a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen 180246c83c80c5737743c955ff007fa6409804a7abf0Jakob Stoklund Olesen // Try splitting VirtReg or interferences. 1803ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen unsigned PhysReg = trySplit(VirtReg, Order, NewVRegs); 1804ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen if (PhysReg || !NewVRegs.empty()) 1805b64d92e29f38002e52a22fe36ea2d488968e3537Jakob Stoklund Olesen return PhysReg; 1806b64d92e29f38002e52a22fe36ea2d488968e3537Jakob Stoklund Olesen 1807770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen // Finally spill VirtReg itself. 1808770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen NamedRegionTimer T("Spiller", TimerGroupName, TimePassesIsEnabled); 180920942dcd8634ad75091fe89669868cfebf74e869Jakob Stoklund Olesen LiveRangeEdit LRE(&VirtReg, NewVRegs, *MF, *LIS, VRM, this); 181047dbf6cef761c25cfeb0aa7d624a6f98288bb96aJakob Stoklund Olesen spiller().spill(LRE); 1811fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen setStage(NewVRegs.begin(), NewVRegs.end(), RS_Done); 1812cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 1813c46570dc05851395829bef904bb6ddb1260400d1Jakob Stoklund Olesen if (VerifyEnabled) 1814c46570dc05851395829bef904bb6ddb1260400d1Jakob Stoklund Olesen MF->verify(this, "After spilling"); 1815c46570dc05851395829bef904bb6ddb1260400d1Jakob Stoklund Olesen 1816cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen // The live virtual register requesting allocation was spilled, so tell 1817cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen // the caller not to allocate anything during this round. 1818cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen return 0; 1819cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen} 1820cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 1821cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesenbool RAGreedy::runOnMachineFunction(MachineFunction &mf) { 1822cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen DEBUG(dbgs() << "********** GREEDY REGISTER ALLOCATION **********\n" 1823986d76d7b3844b9a2f3d01a48975952749267a93David Blaikie << "********** Function: " << mf.getName() << '\n'); 1824cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 1825cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen MF = &mf; 1826af24964251e27c2dd863239ba66ffd967b593be5Jakob Stoklund Olesen if (VerifyEnabled) 182789cab93fe999f6d81b4b99a71ac797b7ecfec277Jakob Stoklund Olesen MF->verify(this, "Before greedy register allocator"); 1828af24964251e27c2dd863239ba66ffd967b593be5Jakob Stoklund Olesen 1829d4348a2dc24c4fb012c1b9b20e71908f52049283Jakob Stoklund Olesen RegAllocBase::init(getAnalysis<VirtRegMap>(), 1830d4348a2dc24c4fb012c1b9b20e71908f52049283Jakob Stoklund Olesen getAnalysis<LiveIntervals>(), 1831d4348a2dc24c4fb012c1b9b20e71908f52049283Jakob Stoklund Olesen getAnalysis<LiveRegMatrix>()); 1832b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen Indexes = &getAnalysis<SlotIndexes>(); 18334eed756153b84c211114a3e9186bf0cb55d4b394Benjamin Kramer MBFI = &getAnalysis<MachineBlockFrequencyInfo>(); 1834f428eb6c1b09a2322b7a577b0bf2e49dd107bceaJakob Stoklund Olesen DomTree = &getAnalysis<MachineDominatorTree>(); 1835f6dff84d4e44d6c4a46c4f8a18e13c78f804547cJakob Stoklund Olesen SpillerInstance.reset(createInlineSpiller(*this, *MF, *VRM)); 1836d0bb5e2ca05d9c942223bf05e5940bb0c6cc9d3fJakob Stoklund Olesen Loops = &getAnalysis<MachineLoopInfo>(); 1837b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen Bundles = &getAnalysis<EdgeBundles>(); 1838b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen SpillPlacer = &getAnalysis<SpillPlacement>(); 1839f42b66169d75301346e3685fd2b3e45e47806367Jakob Stoklund Olesen DebugVars = &getAnalysis<LiveDebugVariables>(); 1840b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 1841a77da0579bc141eba62760e21a216e5d3eafd792Arnaud A. de Grandmaison calculateSpillWeights(*LIS, mf, *Loops, *MBFI); 1842a77da0579bc141eba62760e21a216e5d3eafd792Arnaud A. de Grandmaison 18435dca61397878a7207986455b42fa2117fbf78000Andrew Trick DEBUG(LIS->dump()); 18445dca61397878a7207986455b42fa2117fbf78000Andrew Trick 18451b847deb26b52051de39f4cbecd224c9fbd0d1c2Jakob Stoklund Olesen SA.reset(new SplitAnalysis(*VRM, *LIS, *Loops)); 18464eed756153b84c211114a3e9186bf0cb55d4b394Benjamin Kramer SE.reset(new SplitEditor(*SA, *LIS, *VRM, *DomTree, *MBFI)); 18471a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen ExtraRegInfo.clear(); 18481a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen ExtraRegInfo.resize(MRI->getNumVirtRegs()); 18491a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen NextCascade = 1; 1850042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen IntfCache.init(MF, Matrix->getLiveUnions(), Indexes, LIS, TRI); 185100005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen GlobalCand.resize(32); // This will grow as needed. 1852d0bb5e2ca05d9c942223bf05e5940bb0c6cc9d3fJakob Stoklund Olesen 1853cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen allocatePhysRegs(); 1854cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen releaseMemory(); 1855cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen return true; 1856cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen} 1857