RegAllocGreedy.cpp revision 6d6132986d2ef14bbf9d76f5acbf2a0bace32d69
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" 32f428eb6c1b09a2322b7a577b0bf2e49dd107bceaJakob Stoklund Olesen#include "llvm/CodeGen/MachineDominators.h" 33cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "llvm/CodeGen/MachineFunctionPass.h" 34cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "llvm/CodeGen/MachineLoopInfo.h" 35cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "llvm/CodeGen/MachineRegisterInfo.h" 36cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "llvm/CodeGen/RegAllocRegistry.h" 37d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/CodeGen/VirtRegMap.h" 38d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/PassAnalysisSupport.h" 3900005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen#include "llvm/Support/CommandLine.h" 40cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "llvm/Support/Debug.h" 41cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "llvm/Support/ErrorHandling.h" 42533f58ecdd8a4732c2f0e149387c4d8d8d4142deJakob Stoklund Olesen#include "llvm/Support/Timer.h" 43d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Support/raw_ostream.h" 44d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Target/TargetOptions.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; 75f428eb6c1b09a2322b7a577b0bf2e49dd107bceaJakob Stoklund Olesen MachineDominatorTree *DomTree; 76d0bb5e2ca05d9c942223bf05e5940bb0c6cc9d3fJakob Stoklund Olesen MachineLoopInfo *Loops; 77b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen EdgeBundles *Bundles; 78b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen SpillPlacement *SpillPlacer; 79f42b66169d75301346e3685fd2b3e45e47806367Jakob Stoklund Olesen LiveDebugVariables *DebugVars; 80f428eb6c1b09a2322b7a577b0bf2e49dd107bceaJakob Stoklund Olesen 81cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen // state 82cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen std::auto_ptr<Spiller> SpillerInstance; 8398d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen std::priority_queue<std::pair<unsigned, unsigned> > Queue; 841a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen unsigned NextCascade; 8522a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen 8622a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // Live ranges pass through a number of stages as we try to allocate them. 8722a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // Some of the stages may also create new live ranges: 8822a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // 8922a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // - Region splitting. 9022a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // - Per-block splitting. 9122a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // - Local splitting. 9222a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // - Spilling. 9322a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // 9422a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // Ranges produced by one of the stages skip the previous stages when they are 9522a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // dequeued. This improves performance because we can skip interference checks 9622a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // that are unlikely to give any results. It also guarantees that the live 9722a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // range splitting algorithm terminates, something that is otherwise hard to 9822a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // ensure. 9922a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen enum LiveRangeStage { 100fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen /// Newly created live range that has never been queued. 101fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen RS_New, 102fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen 103fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen /// Only attempt assignment and eviction. Then requeue as RS_Split. 104fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen RS_Assign, 105fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen 106fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen /// Attempt live range splitting if assignment is impossible. 107fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen RS_Split, 108fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen 10949743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen /// Attempt more aggressive live range splitting that is guaranteed to make 11049743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen /// progress. This is used for split products that may not be making 11149743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen /// progress. 11249743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen RS_Split2, 11349743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen 114fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen /// Live range will be spilled. No more splitting will be attempted. 115fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen RS_Spill, 116fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen 117fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen /// There is nothing more we can do to this live range. Abort compilation 118fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen /// if it can't be assigned. 119fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen RS_Done 12022a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen }; 12122a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen 122b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen static const char *const StageName[]; 123b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen 1241a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen // RegInfo - Keep additional information about each live range. 1251a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen struct RegInfo { 1261a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen LiveRangeStage Stage; 1271a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen 1281a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen // Cascade - Eviction loop prevention. See canEvictInterference(). 1291a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen unsigned Cascade; 1301a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen 1311a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen RegInfo() : Stage(RS_New), Cascade(0) {} 1321a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen }; 1331a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen 1341a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen IndexedMap<RegInfo, VirtReg2IndexFunctor> ExtraRegInfo; 13522a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen 13622a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen LiveRangeStage getStage(const LiveInterval &VirtReg) const { 1371a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen return ExtraRegInfo[VirtReg.reg].Stage; 1381a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen } 1391a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen 1401a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen void setStage(const LiveInterval &VirtReg, LiveRangeStage Stage) { 1411a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen ExtraRegInfo.resize(MRI->getNumVirtRegs()); 1421a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen ExtraRegInfo[VirtReg.reg].Stage = Stage; 14322a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen } 14422a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen 14522a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen template<typename Iterator> 14622a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen void setStage(Iterator Begin, Iterator End, LiveRangeStage NewStage) { 1471a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen ExtraRegInfo.resize(MRI->getNumVirtRegs()); 148f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund Olesen for (;Begin != End; ++Begin) { 149f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund Olesen unsigned Reg = (*Begin)->reg; 1501a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen if (ExtraRegInfo[Reg].Stage == RS_New) 1511a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen ExtraRegInfo[Reg].Stage = NewStage; 152f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund Olesen } 15322a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen } 154cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 15551458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen /// Cost of evicting interference. 15651458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen struct EvictionCost { 15751458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen unsigned BrokenHints; ///< Total number of broken hints. 15851458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen float MaxWeight; ///< Maximum spill weight evicted. 15951458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen 16051458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen EvictionCost(unsigned B = 0) : BrokenHints(B), MaxWeight(0) {} 16151458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen 16251458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen bool operator<(const EvictionCost &O) const { 16351458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen if (BrokenHints != O.BrokenHints) 16451458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen return BrokenHints < O.BrokenHints; 16551458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen return MaxWeight < O.MaxWeight; 16651458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen } 16751458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen }; 16851458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen 169b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen // splitting state. 17022a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen std::auto_ptr<SplitAnalysis> SA; 171bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen std::auto_ptr<SplitEditor> SE; 172b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 173eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen /// Cached per-block interference maps 174eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen InterferenceCache IntfCache; 175eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen 1767b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen /// All basic blocks where the current register has uses. 17796dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen SmallVector<SpillPlacement::BlockConstraint, 8> SplitConstraints; 178b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 17996dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen /// Global live range splitting candidate info. 18096dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen struct GlobalSplitCandidate { 18100005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // Register intended for assignment, or 0. 18296dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen unsigned PhysReg; 18300005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen 18400005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // SplitKit interval index for this candidate. 18500005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen unsigned IntvIdx; 18600005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen 18700005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // Interference for PhysReg. 188c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen InterferenceCache::Cursor Intf; 18900005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen 19000005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // Bundles where this candidate should be live. 19196dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen BitVector LiveBundles; 1925db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen SmallVector<unsigned, 8> ActiveBlocks; 1935db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen 194c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen void reset(InterferenceCache &Cache, unsigned Reg) { 1955db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen PhysReg = Reg; 19600005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen IntvIdx = 0; 197c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen Intf.setPhysReg(Cache, Reg); 1985db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen LiveBundles.clear(); 1995db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen ActiveBlocks.clear(); 2005db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen } 20100005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen 20200005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // Set B[i] = C for every live bundle where B[i] was NoCand. 20300005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen unsigned getBundles(SmallVectorImpl<unsigned> &B, unsigned C) { 20400005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen unsigned Count = 0; 20500005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen for (int i = LiveBundles.find_first(); i >= 0; 20600005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen i = LiveBundles.find_next(i)) 20700005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen if (B[i] == NoCand) { 20800005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen B[i] = C; 20900005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen Count++; 21000005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen } 21100005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen return Count; 21200005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen } 21396dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen }; 21496dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen 21596dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen /// Candidate info for for each PhysReg in AllocationOrder. 21696dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen /// This vector never shrinks, but grows to the size of the largest register 21796dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen /// class. 21896dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen SmallVector<GlobalSplitCandidate, 32> GlobalCand; 21996dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen 22000005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen enum { NoCand = ~0u }; 22100005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen 22200005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen /// Candidate map. Each edge bundle is assigned to a GlobalCand entry, or to 22300005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen /// NoCand which indicates the stack interval. 22400005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen SmallVector<unsigned, 32> BundleCand; 22500005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen 226cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesenpublic: 227cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen RAGreedy(); 228cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 229cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen /// Return the pass name. 230cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen virtual const char* getPassName() const { 231533f58ecdd8a4732c2f0e149387c4d8d8d4142deJakob Stoklund Olesen return "Greedy Register Allocator"; 232cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen } 233cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 234cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen /// RAGreedy analysis usage. 235cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen virtual void getAnalysisUsage(AnalysisUsage &AU) const; 236cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen virtual void releaseMemory(); 237cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen virtual Spiller &spiller() { return *SpillerInstance; } 23898d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen virtual void enqueue(LiveInterval *LI); 23998d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen virtual LiveInterval *dequeue(); 240ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen virtual unsigned selectOrSplit(LiveInterval&, 241ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen SmallVectorImpl<LiveInterval*>&); 242cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 243cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen /// Perform register allocation. 244cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen virtual bool runOnMachineFunction(MachineFunction &mf); 245cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 246cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen static char ID; 247b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick 248b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trickprivate: 2497792e980c43536814ea42448db9799b4da32fef6Jakob Stoklund Olesen bool LRE_CanEraseVirtReg(unsigned); 2501d5b84508173b93faf513032b3847152e6060791Jakob Stoklund Olesen void LRE_WillShrinkVirtReg(unsigned); 251f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund Olesen void LRE_DidCloneVirtReg(unsigned, unsigned); 25292a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen 253200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen float calcSpillCost(); 254f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen bool addSplitConstraints(InterferenceCache::Cursor, float&); 255f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen void addThroughConstraints(InterferenceCache::Cursor, ArrayRef<unsigned>); 256c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen void growRegion(GlobalSplitCandidate &Cand); 257c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen float calcGlobalSplitCost(GlobalSplitCandidate&); 25887972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen bool calcCompactRegion(GlobalSplitCandidate&); 25900005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen void splitAroundRegion(LiveRangeEdit&, ArrayRef<unsigned>); 260034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen void calcGapWeights(unsigned, SmallVectorImpl<float>&); 26151458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen bool shouldEvict(LiveInterval &A, bool, LiveInterval &B, bool); 26251458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen bool canEvictInterference(LiveInterval&, unsigned, bool, EvictionCost&); 26351458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen void evictInterference(LiveInterval&, unsigned, 26451458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen SmallVectorImpl<LiveInterval*>&); 265b64d92e29f38002e52a22fe36ea2d488968e3537Jakob Stoklund Olesen 2666bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen unsigned tryAssign(LiveInterval&, AllocationOrder&, 2676bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen SmallVectorImpl<LiveInterval*>&); 26898c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen unsigned tryEvict(LiveInterval&, AllocationOrder&, 2696bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen SmallVectorImpl<LiveInterval*>&, unsigned = ~0u); 270b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen unsigned tryRegionSplit(LiveInterval&, AllocationOrder&, 271b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen SmallVectorImpl<LiveInterval*>&); 272dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen unsigned tryBlockSplit(LiveInterval&, AllocationOrder&, 273dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen SmallVectorImpl<LiveInterval*>&); 274d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen unsigned tryInstructionSplit(LiveInterval&, AllocationOrder&, 275d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen SmallVectorImpl<LiveInterval*>&); 276034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen unsigned tryLocalSplit(LiveInterval&, AllocationOrder&, 277034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen SmallVectorImpl<LiveInterval*>&); 278b64d92e29f38002e52a22fe36ea2d488968e3537Jakob Stoklund Olesen unsigned trySplit(LiveInterval&, AllocationOrder&, 279b64d92e29f38002e52a22fe36ea2d488968e3537Jakob Stoklund Olesen SmallVectorImpl<LiveInterval*>&); 280cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen}; 281cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen} // end anonymous namespace 282cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 283cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesenchar RAGreedy::ID = 0; 284cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 285b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen#ifndef NDEBUG 286b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesenconst char *const RAGreedy::StageName[] = { 287fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen "RS_New", 288fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen "RS_Assign", 289fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen "RS_Split", 29049743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen "RS_Split2", 291fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen "RS_Spill", 292fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen "RS_Done" 293b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen}; 294b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen#endif 295b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen 296200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen// Hysteresis to use when comparing floats. 297200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen// This helps stabilize decisions based on float comparisons. 298200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesenconst float Hysteresis = 0.98f; 299200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen 300200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen 301cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund OlesenFunctionPass* llvm::createGreedyRegisterAllocator() { 302cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen return new RAGreedy(); 303cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen} 304cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 3051a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund OlesenRAGreedy::RAGreedy(): MachineFunctionPass(ID) { 306cfafc54040cc9722995558124f253d05a038176bJakob Stoklund Olesen initializeLiveDebugVariablesPass(*PassRegistry::getPassRegistry()); 307b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen initializeSlotIndexesPass(*PassRegistry::getPassRegistry()); 308cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen initializeLiveIntervalsPass(*PassRegistry::getPassRegistry()); 309cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen initializeSlotIndexesPass(*PassRegistry::getPassRegistry()); 3105b220213bfe9c37c2bb41a7ae0804e06a14f1007Rafael Espindola initializeRegisterCoalescerPass(*PassRegistry::getPassRegistry()); 31142b7a71dc7381d1f38bf7b7201fc26dd80453364Andrew Trick initializeMachineSchedulerPass(*PassRegistry::getPassRegistry()); 312cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen initializeCalculateSpillWeightsPass(*PassRegistry::getPassRegistry()); 313cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen initializeLiveStacksPass(*PassRegistry::getPassRegistry()); 314cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry()); 315cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen initializeMachineLoopInfoPass(*PassRegistry::getPassRegistry()); 316cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen initializeVirtRegMapPass(*PassRegistry::getPassRegistry()); 317042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen initializeLiveRegMatrixPass(*PassRegistry::getPassRegistry()); 318b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen initializeEdgeBundlesPass(*PassRegistry::getPassRegistry()); 319b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen initializeSpillPlacementPass(*PassRegistry::getPassRegistry()); 320cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen} 321cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 322cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesenvoid RAGreedy::getAnalysisUsage(AnalysisUsage &AU) const { 323cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.setPreservesCFG(); 324cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addRequired<AliasAnalysis>(); 325cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addPreserved<AliasAnalysis>(); 326cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addRequired<LiveIntervals>(); 32705ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen AU.addPreserved<LiveIntervals>(); 328b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen AU.addRequired<SlotIndexes>(); 329cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addPreserved<SlotIndexes>(); 330cfafc54040cc9722995558124f253d05a038176bJakob Stoklund Olesen AU.addRequired<LiveDebugVariables>(); 331cfafc54040cc9722995558124f253d05a038176bJakob Stoklund Olesen AU.addPreserved<LiveDebugVariables>(); 332cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addRequired<LiveStacks>(); 333cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addPreserved<LiveStacks>(); 334bb36a438722d4d56febc07c6472c8446bb6faafeEvan Cheng AU.addRequired<CalculateSpillWeights>(); 335f428eb6c1b09a2322b7a577b0bf2e49dd107bceaJakob Stoklund Olesen AU.addRequired<MachineDominatorTree>(); 336f428eb6c1b09a2322b7a577b0bf2e49dd107bceaJakob Stoklund Olesen AU.addPreserved<MachineDominatorTree>(); 337cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addRequired<MachineLoopInfo>(); 338cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addPreserved<MachineLoopInfo>(); 339cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addRequired<VirtRegMap>(); 340cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addPreserved<VirtRegMap>(); 341042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen AU.addRequired<LiveRegMatrix>(); 342042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen AU.addPreserved<LiveRegMatrix>(); 343b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen AU.addRequired<EdgeBundles>(); 344b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen AU.addRequired<SpillPlacement>(); 345cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen MachineFunctionPass::getAnalysisUsage(AU); 346cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen} 347cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 34892a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen 34992a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 35092a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen// LiveRangeEdit delegate methods 35192a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 35292a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen 3537792e980c43536814ea42448db9799b4da32fef6Jakob Stoklund Olesenbool RAGreedy::LRE_CanEraseVirtReg(unsigned VirtReg) { 354042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen if (VRM->hasPhys(VirtReg)) { 355042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen Matrix->unassign(LIS->getInterval(VirtReg)); 3567792e980c43536814ea42448db9799b4da32fef6Jakob Stoklund Olesen return true; 3577792e980c43536814ea42448db9799b4da32fef6Jakob Stoklund Olesen } 3587792e980c43536814ea42448db9799b4da32fef6Jakob Stoklund Olesen // Unassigned virtreg is probably in the priority queue. 3597792e980c43536814ea42448db9799b4da32fef6Jakob Stoklund Olesen // RegAllocBase will erase it after dequeueing. 3607792e980c43536814ea42448db9799b4da32fef6Jakob Stoklund Olesen return false; 3617792e980c43536814ea42448db9799b4da32fef6Jakob Stoklund Olesen} 36292a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen 3631d5b84508173b93faf513032b3847152e6060791Jakob Stoklund Olesenvoid RAGreedy::LRE_WillShrinkVirtReg(unsigned VirtReg) { 364042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen if (!VRM->hasPhys(VirtReg)) 3651d5b84508173b93faf513032b3847152e6060791Jakob Stoklund Olesen return; 3661d5b84508173b93faf513032b3847152e6060791Jakob Stoklund Olesen 3671d5b84508173b93faf513032b3847152e6060791Jakob Stoklund Olesen // Register is assigned, put it back on the queue for reassignment. 3681d5b84508173b93faf513032b3847152e6060791Jakob Stoklund Olesen LiveInterval &LI = LIS->getInterval(VirtReg); 369042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen Matrix->unassign(LI); 3701d5b84508173b93faf513032b3847152e6060791Jakob Stoklund Olesen enqueue(&LI); 3711d5b84508173b93faf513032b3847152e6060791Jakob Stoklund Olesen} 3721d5b84508173b93faf513032b3847152e6060791Jakob Stoklund Olesen 373f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund Olesenvoid RAGreedy::LRE_DidCloneVirtReg(unsigned New, unsigned Old) { 3740d4fea786670473b53d285be378e619399e03488Jakob Stoklund Olesen // Cloning a register we haven't even heard about yet? Just ignore it. 3750d4fea786670473b53d285be378e619399e03488Jakob Stoklund Olesen if (!ExtraRegInfo.inBounds(Old)) 3760d4fea786670473b53d285be378e619399e03488Jakob Stoklund Olesen return; 3770d4fea786670473b53d285be378e619399e03488Jakob Stoklund Olesen 378f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund Olesen // LRE may clone a virtual register because dead code elimination causes it to 379165e231c4295deb5cabd124d08e231b551bcc0b2Jakob Stoklund Olesen // be split into connected components. The new components are much smaller 380165e231c4295deb5cabd124d08e231b551bcc0b2Jakob Stoklund Olesen // than the original, so they should get a new chance at being assigned. 381f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund Olesen // same stage as the parent. 382165e231c4295deb5cabd124d08e231b551bcc0b2Jakob Stoklund Olesen ExtraRegInfo[Old].Stage = RS_Assign; 3831a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen ExtraRegInfo.grow(New); 3841a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen ExtraRegInfo[New] = ExtraRegInfo[Old]; 385f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund Olesen} 386f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund Olesen 387cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesenvoid RAGreedy::releaseMemory() { 388cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen SpillerInstance.reset(0); 3891a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen ExtraRegInfo.clear(); 3905db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen GlobalCand.clear(); 391cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen} 392cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 39398d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesenvoid RAGreedy::enqueue(LiveInterval *LI) { 39498d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen // Prioritize live ranges by size, assigning larger ranges first. 39598d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen // The queue holds (size, reg) pairs. 396107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen const unsigned Size = LI->getSize(); 397107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen const unsigned Reg = LI->reg; 39898d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen assert(TargetRegisterInfo::isVirtualRegister(Reg) && 39998d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen "Can only enqueue virtual registers"); 400107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen unsigned Prio; 40190c1d7ddfc65654f7efe72d56cad65d1af9e6b2aJakob Stoklund Olesen 4021a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen ExtraRegInfo.grow(Reg); 4031a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen if (ExtraRegInfo[Reg].Stage == RS_New) 404fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen ExtraRegInfo[Reg].Stage = RS_Assign; 405f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund Olesen 406cc07e04262fe4bc35469fbadc53d2ec7bfd02fe2Jakob Stoklund Olesen if (ExtraRegInfo[Reg].Stage == RS_Split) { 407eb29157d80847c207b77910bcd40a6a6c91ca5c5Jakob Stoklund Olesen // Unsplit ranges that couldn't be allocated immediately are deferred until 408a16a25ddeaf495b78b04e2a19feeac00d9824e63Jakob Stoklund Olesen // everything else has been allocated. 409a16a25ddeaf495b78b04e2a19feeac00d9824e63Jakob Stoklund Olesen Prio = Size; 410cc07e04262fe4bc35469fbadc53d2ec7bfd02fe2Jakob Stoklund Olesen } else { 411a16a25ddeaf495b78b04e2a19feeac00d9824e63Jakob Stoklund Olesen // Everything is allocated in long->short order. Long ranges that don't fit 412a16a25ddeaf495b78b04e2a19feeac00d9824e63Jakob Stoklund Olesen // should be spilled (or split) ASAP so they don't create interference. 413107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen Prio = (1u << 31) + Size; 414d2a50734234a80893ad71da90d9f32032c47e000Jakob Stoklund Olesen 415eb29157d80847c207b77910bcd40a6a6c91ca5c5Jakob Stoklund Olesen // Boost ranges that have a physical register hint. 416fc6374439edf2f74da4026f4cea8e341d092be5cJakob Stoklund Olesen if (VRM->hasKnownPreference(Reg)) 417eb29157d80847c207b77910bcd40a6a6c91ca5c5Jakob Stoklund Olesen Prio |= (1u << 30); 418eb29157d80847c207b77910bcd40a6a6c91ca5c5Jakob Stoklund Olesen } 419107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen 420e3b23cde80b19507f1d8b641a541e91ace0864dcJakob Stoklund Olesen Queue.push(std::make_pair(Prio, ~Reg)); 42190c1d7ddfc65654f7efe72d56cad65d1af9e6b2aJakob Stoklund Olesen} 42290c1d7ddfc65654f7efe72d56cad65d1af9e6b2aJakob Stoklund Olesen 42398d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund OlesenLiveInterval *RAGreedy::dequeue() { 42498d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen if (Queue.empty()) 42598d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen return 0; 426e3b23cde80b19507f1d8b641a541e91ace0864dcJakob Stoklund Olesen LiveInterval *LI = &LIS->getInterval(~Queue.top().second); 42798d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen Queue.pop(); 42898d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen return LI; 42998d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen} 430770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen 4316bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen 4326bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 4336bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen// Direct Assignment 4346bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 4356bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen 4366bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen/// tryAssign - Try to assign VirtReg to an available register. 4376bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesenunsigned RAGreedy::tryAssign(LiveInterval &VirtReg, 4386bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen AllocationOrder &Order, 4396bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen SmallVectorImpl<LiveInterval*> &NewVRegs) { 4406bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen Order.rewind(); 4416bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen unsigned PhysReg; 442042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen while ((PhysReg = Order.next())) 443042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen if (!Matrix->checkInterference(VirtReg, PhysReg)) 4446bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen break; 445f7999fe1cb2c2bdb0a4080efabb4743719ce45caJakob Stoklund Olesen if (!PhysReg || Order.isHint()) 4466bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen return PhysReg; 4476bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen 44851458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // PhysReg is available, but there may be a better choice. 44951458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen 45051458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // If we missed a simple hint, try to cheaply evict interference from the 45151458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // preferred register. 45251458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen if (unsigned Hint = MRI->getSimpleHint(VirtReg.reg)) 453042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen if (Order.isHint(Hint)) { 45451458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen DEBUG(dbgs() << "missed hint " << PrintReg(Hint, TRI) << '\n'); 45551458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen EvictionCost MaxCost(1); 45651458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen if (canEvictInterference(VirtReg, Hint, true, MaxCost)) { 45751458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen evictInterference(VirtReg, Hint, NewVRegs); 45851458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen return Hint; 45951458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen } 46051458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen } 46151458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen 46251458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // Try to evict interference from a cheaper alternative. 4636bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen unsigned Cost = TRI->getCostPerUse(PhysReg); 4646bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen 4656bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen // Most registers have 0 additional cost. 4666bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen if (!Cost) 4676bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen return PhysReg; 4686bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen 4696bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen DEBUG(dbgs() << PrintReg(PhysReg, TRI) << " is available at cost " << Cost 4706bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen << '\n'); 4716bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen unsigned CheapReg = tryEvict(VirtReg, Order, NewVRegs, Cost); 4726bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen return CheapReg ? CheapReg : PhysReg; 4736bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen} 4746bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen 4756bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen 476770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen//===----------------------------------------------------------------------===// 47798c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen// Interference eviction 47898c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 4792710638db2eb84cd7eefb8bb9a1b7e5c49413d45Jakob Stoklund Olesen 48051458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// shouldEvict - determine if A should evict the assigned live range B. The 48151458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// eviction policy defined by this function together with the allocation order 48251458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// defined by enqueue() decides which registers ultimately end up being split 48351458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// and spilled. 484b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen/// 4851a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen/// Cascade numbers are used to prevent infinite loops if this function is a 4861a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen/// cyclic relation. 48751458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// 48851458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// @param A The live range to be assigned. 48951458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// @param IsHint True when A is about to be assigned to its preferred 49051458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// register. 49151458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// @param B The live range to be evicted. 49251458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// @param BreaksHint True when B is already assigned to its preferred register. 49351458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesenbool RAGreedy::shouldEvict(LiveInterval &A, bool IsHint, 49451458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen LiveInterval &B, bool BreaksHint) { 49549743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen bool CanSplit = getStage(B) < RS_Spill; 49651458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen 49751458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // Be fairly aggressive about following hints as long as the evictee can be 49851458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // split. 49951458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen if (CanSplit && IsHint && !BreaksHint) 50051458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen return true; 50151458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen 5021a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen return A.weight > B.weight; 503b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen} 504b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen 50551458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// canEvictInterference - Return true if all interferences between VirtReg and 50651458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// PhysReg can be evicted. When OnlyCheap is set, don't do anything 50751458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// 50851458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// @param VirtReg Live range that is about to be assigned. 50951458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// @param PhysReg Desired register for assignment. 51067c8978617c3bce9d07210f93f6c64c715f77695Dmitri Gribenko/// @param IsHint True when PhysReg is VirtReg's preferred register. 51151458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// @param MaxCost Only look for cheaper candidates and update with new cost 51251458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// when returning true. 51351458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// @returns True when interference can be evicted cheaper than MaxCost. 51498c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesenbool RAGreedy::canEvictInterference(LiveInterval &VirtReg, unsigned PhysReg, 51551458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen bool IsHint, EvictionCost &MaxCost) { 516042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen // It is only possible to evict virtual register interference. 517042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen if (Matrix->checkInterference(VirtReg, PhysReg) > LiveRegMatrix::IK_VirtReg) 518042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen return false; 519042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen 5201a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen // Find VirtReg's cascade number. This will be unassigned if VirtReg was never 5211a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen // involved in an eviction before. If a cascade number was assigned, deny 5221a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen // evicting anything with the same or a newer cascade number. This prevents 5231a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen // infinite eviction loops. 5241a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen // 5251a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen // This works out so a register without a cascade number is allowed to evict 5261a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen // anything, and it can be evicted by anything. 5271a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen unsigned Cascade = ExtraRegInfo[VirtReg.reg].Cascade; 5281a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen if (!Cascade) 5291a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen Cascade = NextCascade; 5301a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen 53151458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen EvictionCost Cost; 532042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) { 533042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen LiveIntervalUnion::Query &Q = Matrix->query(VirtReg, *Units); 5343f5bedf5cbde2cc2badc86b1a0b377f6efcde71cJakob Stoklund Olesen // If there is 10 or more interferences, chances are one is heavier. 53551458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen if (Q.collectInterferingVRegs(10) >= 10) 53698c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen return false; 53798c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen 5383f5bedf5cbde2cc2badc86b1a0b377f6efcde71cJakob Stoklund Olesen // Check if any interfering live range is heavier than MaxWeight. 5393f5bedf5cbde2cc2badc86b1a0b377f6efcde71cJakob Stoklund Olesen for (unsigned i = Q.interferingVRegs().size(); i; --i) { 5403f5bedf5cbde2cc2badc86b1a0b377f6efcde71cJakob Stoklund Olesen LiveInterval *Intf = Q.interferingVRegs()[i - 1]; 541042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen assert(TargetRegisterInfo::isVirtualRegister(Intf->reg) && 542042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen "Only expecting virtual register interference from query"); 54351458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // Never evict spill products. They cannot split or spill. 544fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen if (getStage(*Intf) == RS_Done) 5451a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen return false; 54651458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // Once a live range becomes small enough, it is urgent that we find a 54751458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // register for it. This is indicated by an infinite spill weight. These 54851458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // urgent live ranges get to evict almost anything. 5499cda1be0aa5e9e70ae493ef6944a8c202c1c70e6Jakob Stoklund Olesen // 5509cda1be0aa5e9e70ae493ef6944a8c202c1c70e6Jakob Stoklund Olesen // Also allow urgent evictions of unspillable ranges from a strictly 5519cda1be0aa5e9e70ae493ef6944a8c202c1c70e6Jakob Stoklund Olesen // larger allocation order. 5529cda1be0aa5e9e70ae493ef6944a8c202c1c70e6Jakob Stoklund Olesen bool Urgent = !VirtReg.isSpillable() && 5539cda1be0aa5e9e70ae493ef6944a8c202c1c70e6Jakob Stoklund Olesen (Intf->isSpillable() || 5549cda1be0aa5e9e70ae493ef6944a8c202c1c70e6Jakob Stoklund Olesen RegClassInfo.getNumAllocatableRegs(MRI->getRegClass(VirtReg.reg)) < 5559cda1be0aa5e9e70ae493ef6944a8c202c1c70e6Jakob Stoklund Olesen RegClassInfo.getNumAllocatableRegs(MRI->getRegClass(Intf->reg))); 55651458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // Only evict older cascades or live ranges without a cascade. 55751458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen unsigned IntfCascade = ExtraRegInfo[Intf->reg].Cascade; 55851458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen if (Cascade <= IntfCascade) { 55951458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen if (!Urgent) 56051458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen return false; 56151458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // We permit breaking cascades for urgent evictions. It should be the 56251458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // last resort, though, so make it really expensive. 56351458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen Cost.BrokenHints += 10; 56451458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen } 56551458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // Would this break a satisfied hint? 56651458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen bool BreaksHint = VRM->hasPreferredPhys(Intf->reg); 56751458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // Update eviction cost. 56851458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen Cost.BrokenHints += BreaksHint; 56951458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen Cost.MaxWeight = std::max(Cost.MaxWeight, Intf->weight); 57051458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // Abort if this would be too expensive. 57151458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen if (!(Cost < MaxCost)) 572b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen return false; 57351458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // Finally, apply the eviction policy for non-urgent evictions. 57451458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen if (!Urgent && !shouldEvict(VirtReg, IsHint, *Intf, BreaksHint)) 57576395c9a31444fa86514473e0852cdd67752d0e8Jakob Stoklund Olesen return false; 5762710638db2eb84cd7eefb8bb9a1b7e5c49413d45Jakob Stoklund Olesen } 5772710638db2eb84cd7eefb8bb9a1b7e5c49413d45Jakob Stoklund Olesen } 57851458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen MaxCost = Cost; 57998c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen return true; 58098c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen} 58198c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen 58251458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// evictInterference - Evict any interferring registers that prevent VirtReg 58351458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// from being assigned to Physreg. This assumes that canEvictInterference 58451458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// returned true. 58551458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesenvoid RAGreedy::evictInterference(LiveInterval &VirtReg, unsigned PhysReg, 58651458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen SmallVectorImpl<LiveInterval*> &NewVRegs) { 58751458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // Make sure that VirtReg has a cascade number, and assign that cascade 58851458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // number to every evicted register. These live ranges than then only be 58951458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // evicted by a newer cascade, preventing infinite loops. 59051458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen unsigned Cascade = ExtraRegInfo[VirtReg.reg].Cascade; 59151458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen if (!Cascade) 59251458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen Cascade = ExtraRegInfo[VirtReg.reg].Cascade = NextCascade++; 59351458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen 59451458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen DEBUG(dbgs() << "evicting " << PrintReg(PhysReg, TRI) 59551458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen << " interference: Cascade " << Cascade << '\n'); 596042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen 597042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen // Collect all interfering virtregs first. 598042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen SmallVector<LiveInterval*, 8> Intfs; 599042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) { 600042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen LiveIntervalUnion::Query &Q = Matrix->query(VirtReg, *Units); 60151458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen assert(Q.seenAllInterferences() && "Didn't check all interfererences."); 602042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen ArrayRef<LiveInterval*> IVR = Q.interferingVRegs(); 603042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen Intfs.append(IVR.begin(), IVR.end()); 604042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen } 605042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen 606042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen // Evict them second. This will invalidate the queries. 607042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen for (unsigned i = 0, e = Intfs.size(); i != e; ++i) { 608042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen LiveInterval *Intf = Intfs[i]; 609042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen // The same VirtReg may be present in multiple RegUnits. Skip duplicates. 610042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen if (!VRM->hasPhys(Intf->reg)) 611042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen continue; 612042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen Matrix->unassign(*Intf); 613042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen assert((ExtraRegInfo[Intf->reg].Cascade < Cascade || 614042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen VirtReg.isSpillable() < Intf->isSpillable()) && 615042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen "Cannot decrease cascade number, illegal eviction"); 616042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen ExtraRegInfo[Intf->reg].Cascade = Cascade; 617042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen ++NumEvicted; 618042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen NewVRegs.push_back(Intf); 61951458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen } 62051458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen} 62151458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen 62298c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen/// tryEvict - Try to evict all interferences for a physreg. 62376395c9a31444fa86514473e0852cdd67752d0e8Jakob Stoklund Olesen/// @param VirtReg Currently unassigned virtual register. 62476395c9a31444fa86514473e0852cdd67752d0e8Jakob Stoklund Olesen/// @param Order Physregs to try. 62576395c9a31444fa86514473e0852cdd67752d0e8Jakob Stoklund Olesen/// @return Physreg to assign VirtReg, or 0. 62698c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesenunsigned RAGreedy::tryEvict(LiveInterval &VirtReg, 62798c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen AllocationOrder &Order, 6286bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen SmallVectorImpl<LiveInterval*> &NewVRegs, 6296bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen unsigned CostPerUseLimit) { 63098c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen NamedRegionTimer T("Evict", TimerGroupName, TimePassesIsEnabled); 63198c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen 63251458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // Keep track of the cheapest interference seen so far. 63351458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen EvictionCost BestCost(~0u); 63498c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen unsigned BestPhys = 0; 6356d6132986d2ef14bbf9d76f5acbf2a0bace32d69Jakob Stoklund Olesen unsigned OrderLimit = Order.getOrder().size(); 63698c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen 63751458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // When we are just looking for a reduced cost per use, don't break any 63851458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // hints, and only evict smaller spill weights. 63951458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen if (CostPerUseLimit < ~0u) { 64051458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen BestCost.BrokenHints = 0; 64151458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen BestCost.MaxWeight = VirtReg.weight; 6426d6132986d2ef14bbf9d76f5acbf2a0bace32d69Jakob Stoklund Olesen 6436d6132986d2ef14bbf9d76f5acbf2a0bace32d69Jakob Stoklund Olesen // Check of any registers in RC are below CostPerUseLimit. 6446d6132986d2ef14bbf9d76f5acbf2a0bace32d69Jakob Stoklund Olesen const TargetRegisterClass *RC = MRI->getRegClass(VirtReg.reg); 6456d6132986d2ef14bbf9d76f5acbf2a0bace32d69Jakob Stoklund Olesen unsigned MinCost = RegClassInfo.getMinCost(RC); 6466d6132986d2ef14bbf9d76f5acbf2a0bace32d69Jakob Stoklund Olesen if (MinCost >= CostPerUseLimit) { 6476d6132986d2ef14bbf9d76f5acbf2a0bace32d69Jakob Stoklund Olesen DEBUG(dbgs() << RC->getName() << " minimum cost = " << MinCost 6486d6132986d2ef14bbf9d76f5acbf2a0bace32d69Jakob Stoklund Olesen << ", no cheaper registers to be found.\n"); 6496d6132986d2ef14bbf9d76f5acbf2a0bace32d69Jakob Stoklund Olesen return 0; 6506d6132986d2ef14bbf9d76f5acbf2a0bace32d69Jakob Stoklund Olesen } 6516d6132986d2ef14bbf9d76f5acbf2a0bace32d69Jakob Stoklund Olesen 6526d6132986d2ef14bbf9d76f5acbf2a0bace32d69Jakob Stoklund Olesen // It is normal for register classes to have a long tail of registers with 6536d6132986d2ef14bbf9d76f5acbf2a0bace32d69Jakob Stoklund Olesen // the same cost. We don't need to look at them if they're too expensive. 6546d6132986d2ef14bbf9d76f5acbf2a0bace32d69Jakob Stoklund Olesen if (TRI->getCostPerUse(Order.getOrder().back()) >= CostPerUseLimit) { 6556d6132986d2ef14bbf9d76f5acbf2a0bace32d69Jakob Stoklund Olesen OrderLimit = RegClassInfo.getLastCostChange(RC); 6566d6132986d2ef14bbf9d76f5acbf2a0bace32d69Jakob Stoklund Olesen DEBUG(dbgs() << "Only trying the first " << OrderLimit << " regs.\n"); 6576d6132986d2ef14bbf9d76f5acbf2a0bace32d69Jakob Stoklund Olesen } 65851458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen } 65951458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen 66098c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen Order.rewind(); 6616d6132986d2ef14bbf9d76f5acbf2a0bace32d69Jakob Stoklund Olesen while (unsigned PhysReg = Order.nextWithDups(OrderLimit)) { 6626bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen if (TRI->getCostPerUse(PhysReg) >= CostPerUseLimit) 6636bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen continue; 66451458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // The first use of a callee-saved register in a function has cost 1. 66551458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // Don't start using a CSR when the CostPerUseLimit is low. 66651458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen if (CostPerUseLimit == 1) 66751458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen if (unsigned CSR = RegClassInfo.getLastCalleeSavedAlias(PhysReg)) 66851458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen if (!MRI->isPhysRegUsed(CSR)) { 66951458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen DEBUG(dbgs() << PrintReg(PhysReg, TRI) << " would clobber CSR " 67051458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen << PrintReg(CSR, TRI) << '\n'); 67151458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen continue; 67251458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen } 67351458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen 67451458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen if (!canEvictInterference(VirtReg, PhysReg, false, BestCost)) 67598c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen continue; 67698c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen 67798c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen // Best so far. 67898c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen BestPhys = PhysReg; 67951458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen 68057f1e2cee06f9b57995727d786aeb1031c5376bdJakob Stoklund Olesen // Stop if the hint can be used. 681f7999fe1cb2c2bdb0a4080efabb4743719ce45caJakob Stoklund Olesen if (Order.isHint()) 68257f1e2cee06f9b57995727d786aeb1031c5376bdJakob Stoklund Olesen break; 6832710638db2eb84cd7eefb8bb9a1b7e5c49413d45Jakob Stoklund Olesen } 6842710638db2eb84cd7eefb8bb9a1b7e5c49413d45Jakob Stoklund Olesen 68598c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen if (!BestPhys) 68698c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen return 0; 68798c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen 68851458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen evictInterference(VirtReg, BestPhys, NewVRegs); 68998c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen return BestPhys; 690b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick} 691b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick 692770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen 693770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen//===----------------------------------------------------------------------===// 694b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen// Region Splitting 695b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen//===----------------------------------------------------------------------===// 696b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 6971b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen/// addSplitConstraints - Fill out the SplitConstraints vector based on the 6981b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen/// interference pattern in Physreg and its aliases. Add the constraints to 6991b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen/// SpillPlacement and return the static cost of this split in Cost, assuming 7001b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen/// that all preferences in SplitConstraints are met. 701f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen/// Return false if there are no bundles with positive bias. 702f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesenbool RAGreedy::addSplitConstraints(InterferenceCache::Cursor Intf, 703f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen float &Cost) { 704db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks(); 705eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen 706b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen // Reset interference dependent info. 707db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen SplitConstraints.resize(UseBlocks.size()); 70896dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen float StaticCost = 0; 709db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen for (unsigned i = 0; i != UseBlocks.size(); ++i) { 710db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen const SplitAnalysis::BlockInfo &BI = UseBlocks[i]; 71196dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen SpillPlacement::BlockConstraint &BC = SplitConstraints[i]; 71296dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen 713f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen BC.Number = BI.MBB->getNumber(); 714eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen Intf.moveToBlock(BC.Number); 715db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen BC.Entry = BI.LiveIn ? SpillPlacement::PrefReg : SpillPlacement::DontCare; 716db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen BC.Exit = BI.LiveOut ? SpillPlacement::PrefReg : SpillPlacement::DontCare; 7175ebca793db6262386d7464d03cdaefeb5b640ad3Jakob Stoklund Olesen BC.ChangesValue = BI.FirstDef; 718b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 719eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen if (!Intf.hasInterference()) 720eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen continue; 721eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen 72296dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen // Number of spill code instructions to insert. 72396dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen unsigned Ins = 0; 72496dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen 72596dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen // Interference for the live-in value. 726eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen if (BI.LiveIn) { 7276c8afd728eb02742ce320ecd39bcf3774d8423b7Jakob Stoklund Olesen if (Intf.first() <= Indexes->getMBBStartIdx(BC.Number)) 728db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen BC.Entry = SpillPlacement::MustSpill, ++Ins; 729fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen else if (Intf.first() < BI.FirstInstr) 73096dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen BC.Entry = SpillPlacement::PrefSpill, ++Ins; 731fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen else if (Intf.first() < BI.LastInstr) 73296dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen ++Ins; 733a50c539b7a9e74597da34bfaea5429a48481f18bJakob Stoklund Olesen } 734b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 73596dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen // Interference for the live-out value. 736eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen if (BI.LiveOut) { 737612f7807c581eafb7c8105e1a55c8d839033bfb3Jakob Stoklund Olesen if (Intf.last() >= SA->getLastSplitPoint(BC.Number)) 738db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen BC.Exit = SpillPlacement::MustSpill, ++Ins; 739fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen else if (Intf.last() > BI.LastInstr) 74096dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen BC.Exit = SpillPlacement::PrefSpill, ++Ins; 741fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen else if (Intf.last() > BI.FirstInstr) 74296dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen ++Ins; 743b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen } 744b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 74596dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen // Accumulate the total frequency of inserted spill code. 74696dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen if (Ins) 74796dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen StaticCost += Ins * SpillPlacer->getBlockFrequency(BC.Number); 748b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen } 749f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen Cost = StaticCost; 750db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen 7511b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen // Add constraints for use-blocks. Note that these are the only constraints 7521b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen // that may add a positive bias, it is downhill from here. 7531b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen SpillPlacer->addConstraints(SplitConstraints); 754f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen return SpillPlacer->scanActiveBundles(); 755f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen} 756db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen 757db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen 758f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen/// addThroughConstraints - Add constraints and links to SpillPlacer from the 759f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen/// live-through blocks in Blocks. 760f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesenvoid RAGreedy::addThroughConstraints(InterferenceCache::Cursor Intf, 761f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen ArrayRef<unsigned> Blocks) { 7621b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen const unsigned GroupSize = 8; 7631b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen SpillPlacement::BlockConstraint BCS[GroupSize]; 764f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen unsigned TBS[GroupSize]; 765f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen unsigned B = 0, T = 0; 766db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen 767f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen for (unsigned i = 0; i != Blocks.size(); ++i) { 768f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen unsigned Number = Blocks[i]; 7691b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen Intf.moveToBlock(Number); 7701b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen 7717b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen if (!Intf.hasInterference()) { 772f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen assert(T < GroupSize && "Array overflow"); 773f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen TBS[T] = Number; 774f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen if (++T == GroupSize) { 77539b5abf507b43da6b92f68b86406e0015ead18e9Frits van Bommel SpillPlacer->addLinks(makeArrayRef(TBS, T)); 776f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen T = 0; 777f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen } 7787b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen continue; 7791b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen } 7801b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen 781f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen assert(B < GroupSize && "Array overflow"); 782f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen BCS[B].Number = Number; 783f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen 7847b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen // Interference for the live-in value. 7857b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen if (Intf.first() <= Indexes->getMBBStartIdx(Number)) 7867b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen BCS[B].Entry = SpillPlacement::MustSpill; 7877b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen else 7887b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen BCS[B].Entry = SpillPlacement::PrefSpill; 7897b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen 7907b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen // Interference for the live-out value. 7917b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen if (Intf.last() >= SA->getLastSplitPoint(Number)) 7927b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen BCS[B].Exit = SpillPlacement::MustSpill; 7937b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen else 7947b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen BCS[B].Exit = SpillPlacement::PrefSpill; 7957b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen 7961b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen if (++B == GroupSize) { 7971b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen ArrayRef<SpillPlacement::BlockConstraint> Array(BCS, B); 7981b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen SpillPlacer->addConstraints(Array); 7991b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen B = 0; 8001b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen } 801db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen } 802db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen 8031b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen ArrayRef<SpillPlacement::BlockConstraint> Array(BCS, B); 8041b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen SpillPlacer->addConstraints(Array); 80539b5abf507b43da6b92f68b86406e0015ead18e9Frits van Bommel SpillPlacer->addLinks(makeArrayRef(TBS, T)); 806b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen} 807b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 808c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesenvoid RAGreedy::growRegion(GlobalSplitCandidate &Cand) { 8095db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen // Keep track of through blocks that have not been added to SpillPlacer. 8105db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen BitVector Todo = SA->getThroughBlocks(); 8115db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen SmallVectorImpl<unsigned> &ActiveBlocks = Cand.ActiveBlocks; 8125db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen unsigned AddedTo = 0; 813f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen#ifndef NDEBUG 814f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen unsigned Visited = 0; 815f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen#endif 8165db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen 817f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen for (;;) { 818f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen ArrayRef<unsigned> NewBundles = SpillPlacer->getRecentPositive(); 819f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen // Find new through blocks in the periphery of PrefRegBundles. 820f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen for (int i = 0, e = NewBundles.size(); i != e; ++i) { 821f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen unsigned Bundle = NewBundles[i]; 822f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen // Look at all blocks connected to Bundle in the full graph. 823f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen ArrayRef<unsigned> Blocks = Bundles->getBlocks(Bundle); 824f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen for (ArrayRef<unsigned>::iterator I = Blocks.begin(), E = Blocks.end(); 825f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen I != E; ++I) { 826f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen unsigned Block = *I; 8275db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen if (!Todo.test(Block)) 828f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen continue; 8295db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen Todo.reset(Block); 830f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen // This is a new through block. Add it to SpillPlacer later. 8315db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen ActiveBlocks.push_back(Block); 832f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen#ifndef NDEBUG 833f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen ++Visited; 834f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen#endif 835f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen } 836f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen } 837f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen // Any new blocks to add? 838549019792a8b14500cab093ac8f3c5f7331e86d7Jakob Stoklund Olesen if (ActiveBlocks.size() == AddedTo) 839549019792a8b14500cab093ac8f3c5f7331e86d7Jakob Stoklund Olesen break; 840b4666364f4db4889883d7a6c02a177ebcde7c240Jakob Stoklund Olesen 841b4666364f4db4889883d7a6c02a177ebcde7c240Jakob Stoklund Olesen // Compute through constraints from the interference, or assume that all 842b4666364f4db4889883d7a6c02a177ebcde7c240Jakob Stoklund Olesen // through blocks prefer spilling when forming compact regions. 843b4666364f4db4889883d7a6c02a177ebcde7c240Jakob Stoklund Olesen ArrayRef<unsigned> NewBlocks = makeArrayRef(ActiveBlocks).slice(AddedTo); 844b4666364f4db4889883d7a6c02a177ebcde7c240Jakob Stoklund Olesen if (Cand.PhysReg) 845b4666364f4db4889883d7a6c02a177ebcde7c240Jakob Stoklund Olesen addThroughConstraints(Cand.Intf, NewBlocks); 846b4666364f4db4889883d7a6c02a177ebcde7c240Jakob Stoklund Olesen else 847b87f91b063a0ac853735f2af3bd94fb8551a11ffJakob Stoklund Olesen // Provide a strong negative bias on through blocks to prevent unwanted 848b87f91b063a0ac853735f2af3bd94fb8551a11ffJakob Stoklund Olesen // liveness on loop backedges. 849b87f91b063a0ac853735f2af3bd94fb8551a11ffJakob Stoklund Olesen SpillPlacer->addPrefSpill(NewBlocks, /* Strong= */ true); 850549019792a8b14500cab093ac8f3c5f7331e86d7Jakob Stoklund Olesen AddedTo = ActiveBlocks.size(); 851549019792a8b14500cab093ac8f3c5f7331e86d7Jakob Stoklund Olesen 852f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen // Perhaps iterating can enable more bundles? 853f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen SpillPlacer->iterate(); 854f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen } 855f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen DEBUG(dbgs() << ", v=" << Visited); 856f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen} 85796dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen 85887972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen/// calcCompactRegion - Compute the set of edge bundles that should be live 85987972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen/// when splitting the current live range into compact regions. Compact 86087972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen/// regions can be computed without looking at interference. They are the 86187972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen/// regions formed by removing all the live-through blocks from the live range. 86287972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen/// 86387972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen/// Returns false if the current live range is already compact, or if the 86487972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen/// compact regions would form single block regions anyway. 86587972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesenbool RAGreedy::calcCompactRegion(GlobalSplitCandidate &Cand) { 86687972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen // Without any through blocks, the live range is already compact. 86787972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen if (!SA->getNumThroughBlocks()) 86887972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen return false; 86987972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen 87087972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen // Compact regions don't correspond to any physreg. 87187972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen Cand.reset(IntfCache, 0); 87287972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen 87387972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen DEBUG(dbgs() << "Compact region bundles"); 87487972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen 87587972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen // Use the spill placer to determine the live bundles. GrowRegion pretends 87687972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen // that all the through blocks have interference when PhysReg is unset. 87787972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen SpillPlacer->prepare(Cand.LiveBundles); 87887972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen 87987972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen // The static split cost will be zero since Cand.Intf reports no interference. 88087972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen float Cost; 88187972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen if (!addSplitConstraints(Cand.Intf, Cost)) { 88287972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen DEBUG(dbgs() << ", none.\n"); 88387972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen return false; 88487972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen } 88587972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen 88687972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen growRegion(Cand); 88787972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen SpillPlacer->finish(); 88887972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen 88987972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen if (!Cand.LiveBundles.any()) { 89087972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen DEBUG(dbgs() << ", none.\n"); 89187972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen return false; 89287972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen } 89387972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen 89487972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen DEBUG({ 89587972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen for (int i = Cand.LiveBundles.find_first(); i>=0; 89687972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen i = Cand.LiveBundles.find_next(i)) 89787972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen dbgs() << " EB#" << i; 89887972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen dbgs() << ".\n"; 89987972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen }); 90087972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen return true; 90187972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen} 90287972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen 903200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen/// calcSpillCost - Compute how expensive it would be to split the live range in 904200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen/// SA around all use blocks instead of forming bundle regions. 905200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesenfloat RAGreedy::calcSpillCost() { 906200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen float Cost = 0; 907200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks(); 908200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen for (unsigned i = 0; i != UseBlocks.size(); ++i) { 909200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen const SplitAnalysis::BlockInfo &BI = UseBlocks[i]; 910200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen unsigned Number = BI.MBB->getNumber(); 911200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen // We normally only need one spill instruction - a load or a store. 912200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen Cost += SpillPlacer->getBlockFrequency(Number); 913200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen 914200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen // Unless the value is redefined in the block. 9153f5beede1bb97ba4e06dc300e00b70e1013e7216Jakob Stoklund Olesen if (BI.LiveIn && BI.LiveOut && BI.FirstDef) 9163f5beede1bb97ba4e06dc300e00b70e1013e7216Jakob Stoklund Olesen Cost += SpillPlacer->getBlockFrequency(Number); 917200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen } 918200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen return Cost; 919200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen} 920200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen 921b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen/// calcGlobalSplitCost - Return the global split cost of following the split 922b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen/// pattern in LiveBundles. This cost should be added to the local cost of the 92396dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen/// interference pattern in SplitConstraints. 924b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen/// 925c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesenfloat RAGreedy::calcGlobalSplitCost(GlobalSplitCandidate &Cand) { 926b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen float GlobalCost = 0; 9275db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen const BitVector &LiveBundles = Cand.LiveBundles; 928db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks(); 929db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen for (unsigned i = 0; i != UseBlocks.size(); ++i) { 930db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen const SplitAnalysis::BlockInfo &BI = UseBlocks[i]; 93196dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen SpillPlacement::BlockConstraint &BC = SplitConstraints[i]; 932874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen bool RegIn = LiveBundles[Bundles->getBundle(BC.Number, 0)]; 933874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen bool RegOut = LiveBundles[Bundles->getBundle(BC.Number, 1)]; 934874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen unsigned Ins = 0; 935874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen 936db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen if (BI.LiveIn) 937db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen Ins += RegIn != (BC.Entry == SpillPlacement::PrefReg); 938db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen if (BI.LiveOut) 939db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen Ins += RegOut != (BC.Exit == SpillPlacement::PrefReg); 940874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen if (Ins) 941874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen GlobalCost += Ins * SpillPlacer->getBlockFrequency(BC.Number); 942b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen } 943db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen 9445db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen for (unsigned i = 0, e = Cand.ActiveBlocks.size(); i != e; ++i) { 9455db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen unsigned Number = Cand.ActiveBlocks[i]; 946db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen bool RegIn = LiveBundles[Bundles->getBundle(Number, 0)]; 947db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen bool RegOut = LiveBundles[Bundles->getBundle(Number, 1)]; 9489a54352879e5aaac2e2c37490e5cb7844550db8bJakob Stoklund Olesen if (!RegIn && !RegOut) 9499a54352879e5aaac2e2c37490e5cb7844550db8bJakob Stoklund Olesen continue; 9509a54352879e5aaac2e2c37490e5cb7844550db8bJakob Stoklund Olesen if (RegIn && RegOut) { 9519a54352879e5aaac2e2c37490e5cb7844550db8bJakob Stoklund Olesen // We need double spill code if this block has interference. 952c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen Cand.Intf.moveToBlock(Number); 953c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen if (Cand.Intf.hasInterference()) 9549a54352879e5aaac2e2c37490e5cb7844550db8bJakob Stoklund Olesen GlobalCost += 2*SpillPlacer->getBlockFrequency(Number); 9559a54352879e5aaac2e2c37490e5cb7844550db8bJakob Stoklund Olesen continue; 9569a54352879e5aaac2e2c37490e5cb7844550db8bJakob Stoklund Olesen } 9579a54352879e5aaac2e2c37490e5cb7844550db8bJakob Stoklund Olesen // live-in / stack-out or stack-in live-out. 9589a54352879e5aaac2e2c37490e5cb7844550db8bJakob Stoklund Olesen GlobalCost += SpillPlacer->getBlockFrequency(Number); 959db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen } 960b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen return GlobalCost; 961b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen} 962b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 96300005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen/// splitAroundRegion - Split the current live range around the regions 96400005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen/// determined by BundleCand and GlobalCand. 965ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen/// 96600005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen/// Before calling this function, GlobalCand and BundleCand must be initialized 96700005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen/// so each bundle is assigned to a valid candidate, or NoCand for the 96800005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen/// stack-bound bundles. The shared SA/SE SplitAnalysis and SplitEditor 96900005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen/// objects must be initialized for the current live range, and intervals 97000005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen/// created for the used candidates. 971ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen/// 97200005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen/// @param LREdit The LiveRangeEdit object handling the current split. 97300005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen/// @param UsedCands List of used GlobalCand entries. Every BundleCand value 97400005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen/// must appear in this list. 97500005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesenvoid RAGreedy::splitAroundRegion(LiveRangeEdit &LREdit, 97600005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen ArrayRef<unsigned> UsedCands) { 97700005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // These are the intervals created for new global ranges. We may create more 97800005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // intervals for local ranges. 97900005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen const unsigned NumGlobalIntvs = LREdit.size(); 98000005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen DEBUG(dbgs() << "splitAroundRegion with " << NumGlobalIntvs << " globals.\n"); 98100005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen assert(NumGlobalIntvs && "No global intervals configured"); 982ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 9832d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen // Isolate even single instructions when dealing with a proper sub-class. 98469145baf36219b07a49d8ce14b4a04870e72a123Jakob Stoklund Olesen // That guarantees register class inflation for the stack interval because it 9852d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen // is all copies. 9862d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen unsigned Reg = SA->getParent().reg; 9872d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen bool SingleInstrs = RegClassInfo.isProperSubClass(MRI->getRegClass(Reg)); 9882d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen 98987360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen // First handle all the blocks with uses. 990db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks(); 991db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen for (unsigned i = 0; i != UseBlocks.size(); ++i) { 992db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen const SplitAnalysis::BlockInfo &BI = UseBlocks[i]; 99300005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen unsigned Number = BI.MBB->getNumber(); 99400005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen unsigned IntvIn = 0, IntvOut = 0; 99500005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen SlotIndex IntfIn, IntfOut; 99600005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen if (BI.LiveIn) { 99700005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen unsigned CandIn = BundleCand[Bundles->getBundle(Number, 0)]; 99800005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen if (CandIn != NoCand) { 99900005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen GlobalSplitCandidate &Cand = GlobalCand[CandIn]; 100000005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen IntvIn = Cand.IntvIdx; 100100005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen Cand.Intf.moveToBlock(Number); 100200005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen IntfIn = Cand.Intf.first(); 100300005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen } 100400005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen } 100500005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen if (BI.LiveOut) { 100600005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen unsigned CandOut = BundleCand[Bundles->getBundle(Number, 1)]; 100700005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen if (CandOut != NoCand) { 100800005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen GlobalSplitCandidate &Cand = GlobalCand[CandOut]; 100900005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen IntvOut = Cand.IntvIdx; 101000005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen Cand.Intf.moveToBlock(Number); 101100005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen IntfOut = Cand.Intf.last(); 101200005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen } 101300005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen } 1014ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 1015fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen // Create separate intervals for isolated blocks with multiple uses. 101600005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen if (!IntvIn && !IntvOut) { 1017fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " isolated.\n"); 10182d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen if (SA->shouldSplitSingleBlock(BI, SingleInstrs)) 101987360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen SE->splitSingleBlock(BI); 1020fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen continue; 1021fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen } 1022fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen 102300005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen if (IntvIn && IntvOut) 102400005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen SE->splitLiveThroughBlock(Number, IntvIn, IntfIn, IntvOut, IntfOut); 102500005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen else if (IntvIn) 102600005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen SE->splitRegInBlock(BI, IntvIn, IntfIn); 1027b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen else 102800005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen SE->splitRegOutBlock(BI, IntvOut, IntfOut); 1029ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen } 1030ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 103100005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // Handle live-through blocks. The relevant live-through blocks are stored in 103200005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // the ActiveBlocks list with each candidate. We need to filter out 103300005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // duplicates. 103400005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen BitVector Todo = SA->getThroughBlocks(); 103500005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen for (unsigned c = 0; c != UsedCands.size(); ++c) { 103600005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen ArrayRef<unsigned> Blocks = GlobalCand[UsedCands[c]].ActiveBlocks; 103700005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen for (unsigned i = 0, e = Blocks.size(); i != e; ++i) { 103800005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen unsigned Number = Blocks[i]; 103900005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen if (!Todo.test(Number)) 104000005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen continue; 104100005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen Todo.reset(Number); 104200005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen 104300005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen unsigned IntvIn = 0, IntvOut = 0; 104400005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen SlotIndex IntfIn, IntfOut; 104500005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen 104600005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen unsigned CandIn = BundleCand[Bundles->getBundle(Number, 0)]; 104700005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen if (CandIn != NoCand) { 104800005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen GlobalSplitCandidate &Cand = GlobalCand[CandIn]; 104900005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen IntvIn = Cand.IntvIdx; 105000005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen Cand.Intf.moveToBlock(Number); 105100005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen IntfIn = Cand.Intf.first(); 105200005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen } 105300005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen 105400005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen unsigned CandOut = BundleCand[Bundles->getBundle(Number, 1)]; 105500005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen if (CandOut != NoCand) { 105600005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen GlobalSplitCandidate &Cand = GlobalCand[CandOut]; 105700005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen IntvOut = Cand.IntvIdx; 105800005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen Cand.Intf.moveToBlock(Number); 105900005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen IntfOut = Cand.Intf.last(); 106000005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen } 106100005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen if (!IntvIn && !IntvOut) 106200005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen continue; 106300005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen SE->splitLiveThroughBlock(Number, IntvIn, IntfIn, IntvOut, IntfOut); 106400005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen } 1065db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen } 1066db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen 10670db841f9c2b9a25fb5ecb36e350d3a802c35654cJakob Stoklund Olesen ++NumGlobalSplits; 1068ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 10695928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen SmallVector<unsigned, 8> IntvMap; 10705928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen SE->finish(&IntvMap); 10711f8804263ffc5e6843d81f5c7bd9c739aa90fde5Jakob Stoklund Olesen DebugVars->splitRegister(Reg, LREdit.regs()); 1072f42b66169d75301346e3685fd2b3e45e47806367Jakob Stoklund Olesen 10731a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen ExtraRegInfo.resize(MRI->getNumVirtRegs()); 1074b2abfa0bf30edf292a27a06e091d03983e644c9bJakob Stoklund Olesen unsigned OrigBlocks = SA->getNumLiveBlocks(); 10755928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen 10765928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen // Sort out the new intervals created by splitting. We get four kinds: 10775928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen // - Remainder intervals should not be split again. 10785928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen // - Candidate intervals can be assigned to Cand.PhysReg. 10795928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen // - Block-local splits are candidates for local splitting. 10805928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen // - DCE leftovers should go back on the queue. 10815928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen for (unsigned i = 0, e = LREdit.size(); i != e; ++i) { 10821a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen LiveInterval &Reg = *LREdit.get(i); 10835928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen 10845928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen // Ignore old intervals from DCE. 10851a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen if (getStage(Reg) != RS_New) 10865928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen continue; 10875928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen 10885928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen // Remainder interval. Don't try splitting again, spill if it doesn't 10895928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen // allocate. 10905928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen if (IntvMap[i] == 0) { 1091fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen setStage(Reg, RS_Spill); 10925928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen continue; 10935928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen } 10945928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen 109500005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // Global intervals. Allow repeated splitting as long as the number of live 109600005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // blocks is strictly decreasing. 109700005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen if (IntvMap[i] < NumGlobalIntvs) { 10981a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen if (SA->countLiveBlocks(&Reg) >= OrigBlocks) { 10999f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen DEBUG(dbgs() << "Main interval covers the same " << OrigBlocks 11009f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen << " blocks as original.\n"); 11019f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen // Don't allow repeated splitting as a safe guard against looping. 110249743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen setStage(Reg, RS_Split2); 11039f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen } 11049f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen continue; 11059f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen } 11069f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen 11079f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen // Other intervals are treated as new. This includes local intervals created 11089f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen // for blocks with multiple uses, and anything created by DCE. 11095928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen } 11105928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen 1111eb29157d80847c207b77910bcd40a6a6c91ca5c5Jakob Stoklund Olesen if (VerifyEnabled) 1112ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen MF->verify(this, "After splitting live range around region"); 1113ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen} 1114ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 1115b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesenunsigned RAGreedy::tryRegionSplit(LiveInterval &VirtReg, AllocationOrder &Order, 1116b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen SmallVectorImpl<LiveInterval*> &NewVRegs) { 1117c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen unsigned NumCands = 0; 111800005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen unsigned BestCand = NoCand; 111900005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen float BestCost; 112000005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen SmallVector<unsigned, 8> UsedCands; 112100005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen 112200005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // Check if we can split this live range around a compact region. 1123a16a25ddeaf495b78b04e2a19feeac00d9824e63Jakob Stoklund Olesen bool HasCompact = calcCompactRegion(GlobalCand.front()); 112400005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen if (HasCompact) { 112500005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // Yes, keep GlobalCand[0] as the compact region candidate. 112600005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen NumCands = 1; 112700005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen BestCost = HUGE_VALF; 112800005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen } else { 112900005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // No benefit from the compact region, our fallback will be per-block 113000005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // splitting. Make sure we find a solution that is cheaper than spilling. 113100005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen BestCost = Hysteresis * calcSpillCost(); 113200005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen DEBUG(dbgs() << "Cost of isolating all blocks = " << BestCost << '\n'); 113300005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen } 113496dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen 1135b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen Order.rewind(); 1136c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen while (unsigned PhysReg = Order.next()) { 1137f1c709837bd11c5383fce3b8a026a7c8eaabba86Jakob Stoklund Olesen // Discard bad candidates before we run out of interference cache cursors. 1138f1c709837bd11c5383fce3b8a026a7c8eaabba86Jakob Stoklund Olesen // This will only affect register classes with a lot of registers (>32). 1139f1c709837bd11c5383fce3b8a026a7c8eaabba86Jakob Stoklund Olesen if (NumCands == IntfCache.getMaxCursors()) { 1140f1c709837bd11c5383fce3b8a026a7c8eaabba86Jakob Stoklund Olesen unsigned WorstCount = ~0u; 1141f1c709837bd11c5383fce3b8a026a7c8eaabba86Jakob Stoklund Olesen unsigned Worst = 0; 1142f1c709837bd11c5383fce3b8a026a7c8eaabba86Jakob Stoklund Olesen for (unsigned i = 0; i != NumCands; ++i) { 114300005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen if (i == BestCand || !GlobalCand[i].PhysReg) 1144f1c709837bd11c5383fce3b8a026a7c8eaabba86Jakob Stoklund Olesen continue; 1145f1c709837bd11c5383fce3b8a026a7c8eaabba86Jakob Stoklund Olesen unsigned Count = GlobalCand[i].LiveBundles.count(); 1146f1c709837bd11c5383fce3b8a026a7c8eaabba86Jakob Stoklund Olesen if (Count < WorstCount) 1147f1c709837bd11c5383fce3b8a026a7c8eaabba86Jakob Stoklund Olesen Worst = i, WorstCount = Count; 1148f1c709837bd11c5383fce3b8a026a7c8eaabba86Jakob Stoklund Olesen } 1149f1c709837bd11c5383fce3b8a026a7c8eaabba86Jakob Stoklund Olesen --NumCands; 1150f1c709837bd11c5383fce3b8a026a7c8eaabba86Jakob Stoklund Olesen GlobalCand[Worst] = GlobalCand[NumCands]; 11517bdf0060a00f04ad03d3c6f294d8db6f4951dbc2Jakob Stoklund Olesen if (BestCand == NumCands) 11527bdf0060a00f04ad03d3c6f294d8db6f4951dbc2Jakob Stoklund Olesen BestCand = Worst; 1153f1c709837bd11c5383fce3b8a026a7c8eaabba86Jakob Stoklund Olesen } 1154f1c709837bd11c5383fce3b8a026a7c8eaabba86Jakob Stoklund Olesen 1155c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen if (GlobalCand.size() <= NumCands) 1156c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen GlobalCand.resize(NumCands+1); 1157c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen GlobalSplitCandidate &Cand = GlobalCand[NumCands]; 1158c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen Cand.reset(IntfCache, PhysReg); 115996dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen 1160c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen SpillPlacer->prepare(Cand.LiveBundles); 11611b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen float Cost; 1162c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen if (!addSplitConstraints(Cand.Intf, Cost)) { 1163f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen DEBUG(dbgs() << PrintReg(PhysReg, TRI) << "\tno positive bundles\n"); 11641b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen continue; 11651b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen } 1166f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen DEBUG(dbgs() << PrintReg(PhysReg, TRI) << "\tstatic = " << Cost); 1167200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen if (Cost >= BestCost) { 1168200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen DEBUG({ 1169200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen if (BestCand == NoCand) 1170200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen dbgs() << " worse than no bundles\n"; 1171200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen else 1172200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen dbgs() << " worse than " 1173200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen << PrintReg(GlobalCand[BestCand].PhysReg, TRI) << '\n'; 1174200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen }); 1175b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen continue; 1176874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen } 1177c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen growRegion(Cand); 1178ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 11799efa2a263ea470caacef1c85f6ca45e32bf516d3Jakob Stoklund Olesen SpillPlacer->finish(); 11809efa2a263ea470caacef1c85f6ca45e32bf516d3Jakob Stoklund Olesen 1181ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // No live bundles, defer to splitSingleBlocks(). 1182c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen if (!Cand.LiveBundles.any()) { 1183874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen DEBUG(dbgs() << " no bundles.\n"); 1184ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen continue; 1185874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen } 1186ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 1187c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen Cost += calcGlobalSplitCost(Cand); 1188874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen DEBUG({ 1189874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen dbgs() << ", total = " << Cost << " with bundles"; 1190c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen for (int i = Cand.LiveBundles.find_first(); i>=0; 1191c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen i = Cand.LiveBundles.find_next(i)) 1192874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen dbgs() << " EB#" << i; 1193874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen dbgs() << ".\n"; 1194874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen }); 1195200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen if (Cost < BestCost) { 1196c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen BestCand = NumCands; 1197200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen BestCost = Hysteresis * Cost; // Prevent rounding effects. 1198b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen } 1199c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen ++NumCands; 1200b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen } 1201ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 120200005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // No solutions found, fall back to single block splitting. 120300005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen if (!HasCompact && BestCand == NoCand) 1204ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen return 0; 1205ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 120600005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // Prepare split editor. 120720942dcd8634ad75091fe89669868cfebf74e869Jakob Stoklund Olesen LiveRangeEdit LREdit(&VirtReg, NewVRegs, *MF, *LIS, VRM, this); 1208708d06f7fb5dfd9c8559aea07b042a88c65645f8Jakob Stoklund Olesen SE->reset(LREdit, SplitSpillMode); 120900005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen 121000005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // Assign all edge bundles to the preferred candidate, or NoCand. 121100005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen BundleCand.assign(Bundles->getNumBundles(), NoCand); 121200005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen 121300005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // Assign bundles for the best candidate region. 121400005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen if (BestCand != NoCand) { 121500005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen GlobalSplitCandidate &Cand = GlobalCand[BestCand]; 121600005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen if (unsigned B = Cand.getBundles(BundleCand, BestCand)) { 121700005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen UsedCands.push_back(BestCand); 121800005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen Cand.IntvIdx = SE->openIntv(); 121900005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen DEBUG(dbgs() << "Split for " << PrintReg(Cand.PhysReg, TRI) << " in " 122000005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen << B << " bundles, intv " << Cand.IntvIdx << ".\n"); 122132668ea7a290ee1cb6bfe8cd677cdd4e5df05b4dChandler Carruth (void)B; 122200005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen } 122300005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen } 122400005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen 122500005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // Assign bundles for the compact region. 122600005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen if (HasCompact) { 122700005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen GlobalSplitCandidate &Cand = GlobalCand.front(); 122800005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen assert(!Cand.PhysReg && "Compact region has no physreg"); 122900005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen if (unsigned B = Cand.getBundles(BundleCand, 0)) { 123000005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen UsedCands.push_back(0); 123100005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen Cand.IntvIdx = SE->openIntv(); 123200005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen DEBUG(dbgs() << "Split for compact region in " << B << " bundles, intv " 123300005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen << Cand.IntvIdx << ".\n"); 123432668ea7a290ee1cb6bfe8cd677cdd4e5df05b4dChandler Carruth (void)B; 123500005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen } 123600005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen } 123700005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen 123800005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen splitAroundRegion(LREdit, UsedCands); 1239b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen return 0; 1240b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen} 1241b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 1242ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 1243ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen//===----------------------------------------------------------------------===// 1244dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen// Per-Block Splitting 1245dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen//===----------------------------------------------------------------------===// 1246dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen 1247dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen/// tryBlockSplit - Split a global live range around every block with uses. This 1248dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen/// creates a lot of local live ranges, that will be split by tryLocalSplit if 1249dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen/// they don't allocate. 1250dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesenunsigned RAGreedy::tryBlockSplit(LiveInterval &VirtReg, AllocationOrder &Order, 1251dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen SmallVectorImpl<LiveInterval*> &NewVRegs) { 1252dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen assert(&SA->getParent() == &VirtReg && "Live range wasn't analyzed"); 1253dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen unsigned Reg = VirtReg.reg; 1254dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen bool SingleInstrs = RegClassInfo.isProperSubClass(MRI->getRegClass(Reg)); 125520942dcd8634ad75091fe89669868cfebf74e869Jakob Stoklund Olesen LiveRangeEdit LREdit(&VirtReg, NewVRegs, *MF, *LIS, VRM, this); 1256708d06f7fb5dfd9c8559aea07b042a88c65645f8Jakob Stoklund Olesen SE->reset(LREdit, SplitSpillMode); 1257dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks(); 1258dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen for (unsigned i = 0; i != UseBlocks.size(); ++i) { 1259dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen const SplitAnalysis::BlockInfo &BI = UseBlocks[i]; 1260dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen if (SA->shouldSplitSingleBlock(BI, SingleInstrs)) 1261dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen SE->splitSingleBlock(BI); 1262dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen } 1263dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen // No blocks were split. 1264dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen if (LREdit.empty()) 1265dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen return 0; 1266dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen 1267dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen // We did split for some blocks. 1268a9c41d39d1adc92107e095aca6f851aed71b6a5fJakob Stoklund Olesen SmallVector<unsigned, 8> IntvMap; 1269a9c41d39d1adc92107e095aca6f851aed71b6a5fJakob Stoklund Olesen SE->finish(&IntvMap); 12701f8804263ffc5e6843d81f5c7bd9c739aa90fde5Jakob Stoklund Olesen 12711f8804263ffc5e6843d81f5c7bd9c739aa90fde5Jakob Stoklund Olesen // Tell LiveDebugVariables about the new ranges. 12721f8804263ffc5e6843d81f5c7bd9c739aa90fde5Jakob Stoklund Olesen DebugVars->splitRegister(Reg, LREdit.regs()); 12731f8804263ffc5e6843d81f5c7bd9c739aa90fde5Jakob Stoklund Olesen 1274a9c41d39d1adc92107e095aca6f851aed71b6a5fJakob Stoklund Olesen ExtraRegInfo.resize(MRI->getNumVirtRegs()); 1275a9c41d39d1adc92107e095aca6f851aed71b6a5fJakob Stoklund Olesen 1276a9c41d39d1adc92107e095aca6f851aed71b6a5fJakob Stoklund Olesen // Sort out the new intervals created by splitting. The remainder interval 1277a9c41d39d1adc92107e095aca6f851aed71b6a5fJakob Stoklund Olesen // goes straight to spilling, the new local ranges get to stay RS_New. 1278a9c41d39d1adc92107e095aca6f851aed71b6a5fJakob Stoklund Olesen for (unsigned i = 0, e = LREdit.size(); i != e; ++i) { 1279a9c41d39d1adc92107e095aca6f851aed71b6a5fJakob Stoklund Olesen LiveInterval &LI = *LREdit.get(i); 1280a9c41d39d1adc92107e095aca6f851aed71b6a5fJakob Stoklund Olesen if (getStage(LI) == RS_New && IntvMap[i] == 0) 1281a9c41d39d1adc92107e095aca6f851aed71b6a5fJakob Stoklund Olesen setStage(LI, RS_Spill); 1282a9c41d39d1adc92107e095aca6f851aed71b6a5fJakob Stoklund Olesen } 1283a9c41d39d1adc92107e095aca6f851aed71b6a5fJakob Stoklund Olesen 1284dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen if (VerifyEnabled) 1285dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen MF->verify(this, "After splitting live range around basic blocks"); 1286dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen return 0; 1287dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen} 1288dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen 1289d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen 1290d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 1291d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen// Per-Instruction Splitting 1292d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 1293d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen 1294d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen/// tryInstructionSplit - Split a live range around individual instructions. 1295d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen/// This is normally not worthwhile since the spiller is doing essentially the 1296d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen/// same thing. However, when the live range is in a constrained register 1297d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen/// class, it may help to insert copies such that parts of the live range can 1298d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen/// be moved to a larger register class. 1299d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen/// 1300d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen/// This is similar to spilling to a larger register class. 1301d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesenunsigned 1302d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund OlesenRAGreedy::tryInstructionSplit(LiveInterval &VirtReg, AllocationOrder &Order, 1303d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen SmallVectorImpl<LiveInterval*> &NewVRegs) { 1304d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen // There is no point to this if there are no larger sub-classes. 1305d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen if (!RegClassInfo.isProperSubClass(MRI->getRegClass(VirtReg.reg))) 1306d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen return 0; 1307d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen 1308d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen // Always enable split spill mode, since we're effectively spilling to a 1309d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen // register. 1310d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen LiveRangeEdit LREdit(&VirtReg, NewVRegs, *MF, *LIS, VRM, this); 1311d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen SE->reset(LREdit, SplitEditor::SM_Size); 1312d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen 1313d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen ArrayRef<SlotIndex> Uses = SA->getUseSlots(); 1314d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen if (Uses.size() <= 1) 1315d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen return 0; 1316d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen 1317d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen DEBUG(dbgs() << "Split around " << Uses.size() << " individual instrs.\n"); 1318d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen 1319d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen // Split around every non-copy instruction. 1320d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen for (unsigned i = 0; i != Uses.size(); ++i) { 1321d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen if (const MachineInstr *MI = Indexes->getInstructionFromIndex(Uses[i])) 1322d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen if (MI->isFullCopy()) { 1323d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen DEBUG(dbgs() << " skip:\t" << Uses[i] << '\t' << *MI); 1324d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen continue; 1325d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen } 1326d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen SE->openIntv(); 1327d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen SlotIndex SegStart = SE->enterIntvBefore(Uses[i]); 1328d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen SlotIndex SegStop = SE->leaveIntvAfter(Uses[i]); 1329d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen SE->useIntv(SegStart, SegStop); 1330d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen } 1331d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen 1332d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen if (LREdit.empty()) { 1333d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen DEBUG(dbgs() << "All uses were copies.\n"); 1334d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen return 0; 1335d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen } 1336d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen 1337d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen SmallVector<unsigned, 8> IntvMap; 1338d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen SE->finish(&IntvMap); 1339d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen DebugVars->splitRegister(VirtReg.reg, LREdit.regs()); 1340d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen ExtraRegInfo.resize(MRI->getNumVirtRegs()); 1341d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen 1342d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen // Assign all new registers to RS_Spill. This was the last chance. 1343d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen setStage(LREdit.begin(), LREdit.end(), RS_Spill); 1344d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen return 0; 1345d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen} 1346d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen 1347d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen 1348dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen//===----------------------------------------------------------------------===// 1349034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen// Local Splitting 1350034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 1351034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1352034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1353034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// calcGapWeights - Compute the maximum spill weight that needs to be evicted 1354034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// in order to use PhysReg between two entries in SA->UseSlots. 1355034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// 1356034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// GapWeight[i] represents the gap between UseSlots[i] and UseSlots[i+1]. 1357034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// 1358034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesenvoid RAGreedy::calcGapWeights(unsigned PhysReg, 1359034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen SmallVectorImpl<float> &GapWeight) { 1360db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen assert(SA->getUseBlocks().size() == 1 && "Not a local interval"); 1361db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen const SplitAnalysis::BlockInfo &BI = SA->getUseBlocks().front(); 1362b20b518f800293ea6b2bed04134c71293ac52403Jakob Stoklund Olesen ArrayRef<SlotIndex> Uses = SA->getUseSlots(); 1363034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const unsigned NumGaps = Uses.size()-1; 1364034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1365034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Start and end points for the interference check. 1366fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen SlotIndex StartIdx = 1367fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen BI.LiveIn ? BI.FirstInstr.getBaseIndex() : BI.FirstInstr; 1368fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen SlotIndex StopIdx = 1369fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen BI.LiveOut ? BI.LastInstr.getBoundaryIndex() : BI.LastInstr; 1370034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1371034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen GapWeight.assign(NumGaps, 0.0f); 1372034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1373034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Add interference from each overlapping register. 1374042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) { 1375042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen if (!Matrix->query(const_cast<LiveInterval&>(SA->getParent()), *Units) 1376042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen .checkInterference()) 1377034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen continue; 1378034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1379fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen // We know that VirtReg is a continuous interval from FirstInstr to 1380fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen // LastInstr, so we don't need InterferenceQuery. 1381034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // 1382034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Interference that overlaps an instruction is counted in both gaps 1383034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // surrounding the instruction. The exception is interference before 1384034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // StartIdx and after StopIdx. 1385034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // 1386042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen LiveIntervalUnion::SegmentIter IntI = 1387042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen Matrix->getLiveUnions()[*Units] .find(StartIdx); 1388034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen for (unsigned Gap = 0; IntI.valid() && IntI.start() < StopIdx; ++IntI) { 1389034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Skip the gaps before IntI. 1390034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen while (Uses[Gap+1].getBoundaryIndex() < IntI.start()) 1391034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (++Gap == NumGaps) 1392034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen break; 1393034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (Gap == NumGaps) 1394034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen break; 1395034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1396034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Update the gaps covered by IntI. 1397034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const float weight = IntI.value()->weight; 1398034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen for (; Gap != NumGaps; ++Gap) { 1399034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen GapWeight[Gap] = std::max(GapWeight[Gap], weight); 1400034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (Uses[Gap+1].getBaseIndex() >= IntI.stop()) 1401034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen break; 1402034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1403034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (Gap == NumGaps) 1404034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen break; 1405034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1406034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1407042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen 1408042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen // Add fixed interference. 1409042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) { 1410042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen const LiveInterval &LI = LIS->getRegUnit(*Units); 1411042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen LiveInterval::const_iterator I = LI.find(StartIdx); 1412042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen LiveInterval::const_iterator E = LI.end(); 1413042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen 1414042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen // Same loop as above. Mark any overlapped gaps as HUGE_VALF. 1415042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen for (unsigned Gap = 0; I != E && I->start < StopIdx; ++I) { 1416042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen while (Uses[Gap+1].getBoundaryIndex() < I->start) 1417042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen if (++Gap == NumGaps) 1418042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen break; 1419042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen if (Gap == NumGaps) 1420042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen break; 1421042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen 1422042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen for (; Gap != NumGaps; ++Gap) { 1423042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen GapWeight[Gap] = HUGE_VALF; 1424042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen if (Uses[Gap+1].getBaseIndex() >= I->end) 1425042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen break; 1426042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen } 1427042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen if (Gap == NumGaps) 1428042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen break; 1429042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen } 1430042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen } 1431034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen} 1432034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1433034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// tryLocalSplit - Try to split VirtReg into smaller intervals inside its only 1434034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// basic block. 1435034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// 1436034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesenunsigned RAGreedy::tryLocalSplit(LiveInterval &VirtReg, AllocationOrder &Order, 1437034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen SmallVectorImpl<LiveInterval*> &NewVRegs) { 1438db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen assert(SA->getUseBlocks().size() == 1 && "Not a local interval"); 1439db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen const SplitAnalysis::BlockInfo &BI = SA->getUseBlocks().front(); 1440034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1441034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Note that it is possible to have an interval that is live-in or live-out 1442034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // while only covering a single block - A phi-def can use undef values from 1443034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // predecessors, and the block could be a single-block loop. 1444034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // We don't bother doing anything clever about such a case, we simply assume 1445fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen // that the interval is continuous from FirstInstr to LastInstr. We should 1446fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen // make sure that we don't do anything illegal to such an interval, though. 1447034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1448b20b518f800293ea6b2bed04134c71293ac52403Jakob Stoklund Olesen ArrayRef<SlotIndex> Uses = SA->getUseSlots(); 1449034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (Uses.size() <= 2) 1450034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen return 0; 1451034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const unsigned NumGaps = Uses.size()-1; 1452034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1453034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen DEBUG({ 1454034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen dbgs() << "tryLocalSplit: "; 1455034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen for (unsigned i = 0, e = Uses.size(); i != e; ++i) 1456b20b518f800293ea6b2bed04134c71293ac52403Jakob Stoklund Olesen dbgs() << ' ' << Uses[i]; 1457034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen dbgs() << '\n'; 1458034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen }); 1459034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1460a6d513f47467b90344a74624d4fb77673942e3ceJakob Stoklund Olesen // If VirtReg is live across any register mask operands, compute a list of 1461a6d513f47467b90344a74624d4fb77673942e3ceJakob Stoklund Olesen // gaps with register masks. 1462a6d513f47467b90344a74624d4fb77673942e3ceJakob Stoklund Olesen SmallVector<unsigned, 8> RegMaskGaps; 1463042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen if (Matrix->checkRegMaskInterference(VirtReg)) { 1464a6d513f47467b90344a74624d4fb77673942e3ceJakob Stoklund Olesen // Get regmask slots for the whole block. 1465a6d513f47467b90344a74624d4fb77673942e3ceJakob Stoklund Olesen ArrayRef<SlotIndex> RMS = LIS->getRegMaskSlotsInBlock(BI.MBB->getNumber()); 1466cac5fa39bd861861018bb2c3f0b36cc71c2caa38Jakob Stoklund Olesen DEBUG(dbgs() << RMS.size() << " regmasks in block:"); 1467a6d513f47467b90344a74624d4fb77673942e3ceJakob Stoklund Olesen // Constrain to VirtReg's live range. 1468cac5fa39bd861861018bb2c3f0b36cc71c2caa38Jakob Stoklund Olesen unsigned ri = std::lower_bound(RMS.begin(), RMS.end(), 1469cac5fa39bd861861018bb2c3f0b36cc71c2caa38Jakob Stoklund Olesen Uses.front().getRegSlot()) - RMS.begin(); 1470a6d513f47467b90344a74624d4fb77673942e3ceJakob Stoklund Olesen unsigned re = RMS.size(); 1471a6d513f47467b90344a74624d4fb77673942e3ceJakob Stoklund Olesen for (unsigned i = 0; i != NumGaps && ri != re; ++i) { 1472cac5fa39bd861861018bb2c3f0b36cc71c2caa38Jakob Stoklund Olesen // Look for Uses[i] <= RMS <= Uses[i+1]. 1473cac5fa39bd861861018bb2c3f0b36cc71c2caa38Jakob Stoklund Olesen assert(!SlotIndex::isEarlierInstr(RMS[ri], Uses[i])); 1474cac5fa39bd861861018bb2c3f0b36cc71c2caa38Jakob Stoklund Olesen if (SlotIndex::isEarlierInstr(Uses[i+1], RMS[ri])) 1475a6d513f47467b90344a74624d4fb77673942e3ceJakob Stoklund Olesen continue; 1476cac5fa39bd861861018bb2c3f0b36cc71c2caa38Jakob Stoklund Olesen // Skip a regmask on the same instruction as the last use. It doesn't 1477cac5fa39bd861861018bb2c3f0b36cc71c2caa38Jakob Stoklund Olesen // overlap the live range. 1478cac5fa39bd861861018bb2c3f0b36cc71c2caa38Jakob Stoklund Olesen if (SlotIndex::isSameInstr(Uses[i+1], RMS[ri]) && i+1 == NumGaps) 1479cac5fa39bd861861018bb2c3f0b36cc71c2caa38Jakob Stoklund Olesen break; 1480cac5fa39bd861861018bb2c3f0b36cc71c2caa38Jakob Stoklund Olesen DEBUG(dbgs() << ' ' << RMS[ri] << ':' << Uses[i] << '-' << Uses[i+1]); 1481a6d513f47467b90344a74624d4fb77673942e3ceJakob Stoklund Olesen RegMaskGaps.push_back(i); 1482cac5fa39bd861861018bb2c3f0b36cc71c2caa38Jakob Stoklund Olesen // Advance ri to the next gap. A regmask on one of the uses counts in 1483cac5fa39bd861861018bb2c3f0b36cc71c2caa38Jakob Stoklund Olesen // both gaps. 1484cac5fa39bd861861018bb2c3f0b36cc71c2caa38Jakob Stoklund Olesen while (ri != re && SlotIndex::isEarlierInstr(RMS[ri], Uses[i+1])) 1485cac5fa39bd861861018bb2c3f0b36cc71c2caa38Jakob Stoklund Olesen ++ri; 1486a6d513f47467b90344a74624d4fb77673942e3ceJakob Stoklund Olesen } 1487cac5fa39bd861861018bb2c3f0b36cc71c2caa38Jakob Stoklund Olesen DEBUG(dbgs() << '\n'); 1488a6d513f47467b90344a74624d4fb77673942e3ceJakob Stoklund Olesen } 1489a6d513f47467b90344a74624d4fb77673942e3ceJakob Stoklund Olesen 1490b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // Since we allow local split results to be split again, there is a risk of 1491b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // creating infinite loops. It is tempting to require that the new live 1492b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // ranges have less instructions than the original. That would guarantee 1493b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // convergence, but it is too strict. A live range with 3 instructions can be 1494b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // split 2+3 (including the COPY), and we want to allow that. 1495b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // 1496b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // Instead we use these rules: 1497b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // 149849743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen // 1. Allow any split for ranges with getStage() < RS_Split2. (Except for the 1499b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // noop split, of course). 150049743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen // 2. Require progress be made for ranges with getStage() == RS_Split2. All 1501b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // the new ranges must have fewer instructions than before the split. 150249743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen // 3. New ranges with the same number of instructions are marked RS_Split2, 1503b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // smaller ranges are marked RS_New. 1504b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // 1505b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // These rules allow a 3 -> 2+3 split once, which we need. They also prevent 1506b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // excessive splitting and infinite loops. 1507b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // 150849743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen bool ProgressRequired = getStage(VirtReg) >= RS_Split2; 1509034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1510b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // Best split candidate. 1511034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen unsigned BestBefore = NumGaps; 1512034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen unsigned BestAfter = 0; 1513034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen float BestDiff = 0; 1514034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 151540a42a2ccaaa19a109667ed7abf224cc8733cd9cJakob Stoklund Olesen const float blockFreq = SpillPlacer->getBlockFrequency(BI.MBB->getNumber()); 1516034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen SmallVector<float, 8> GapWeight; 1517034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1518034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen Order.rewind(); 1519034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen while (unsigned PhysReg = Order.next()) { 1520034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Keep track of the largest spill weight that would need to be evicted in 1521034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // order to make use of PhysReg between UseSlots[i] and UseSlots[i+1]. 1522034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen calcGapWeights(PhysReg, GapWeight); 1523034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1524a6d513f47467b90344a74624d4fb77673942e3ceJakob Stoklund Olesen // Remove any gaps with regmask clobbers. 1525042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen if (Matrix->checkRegMaskInterference(VirtReg, PhysReg)) 1526a6d513f47467b90344a74624d4fb77673942e3ceJakob Stoklund Olesen for (unsigned i = 0, e = RegMaskGaps.size(); i != e; ++i) 1527a6d513f47467b90344a74624d4fb77673942e3ceJakob Stoklund Olesen GapWeight[RegMaskGaps[i]] = HUGE_VALF; 1528a6d513f47467b90344a74624d4fb77673942e3ceJakob Stoklund Olesen 1529034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Try to find the best sequence of gaps to close. 1530034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // The new spill weight must be larger than any gap interference. 1531034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1532034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // We will split before Uses[SplitBefore] and after Uses[SplitAfter]. 1533b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen unsigned SplitBefore = 0, SplitAfter = 1; 1534034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1535034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // MaxGap should always be max(GapWeight[SplitBefore..SplitAfter-1]). 1536034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // It is the spill weight that needs to be evicted. 1537034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen float MaxGap = GapWeight[0]; 1538034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1539034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen for (;;) { 1540034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Live before/after split? 1541034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const bool LiveBefore = SplitBefore != 0 || BI.LiveIn; 1542034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const bool LiveAfter = SplitAfter != NumGaps || BI.LiveOut; 1543034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1544034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen DEBUG(dbgs() << PrintReg(PhysReg, TRI) << ' ' 1545034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen << Uses[SplitBefore] << '-' << Uses[SplitAfter] 1546034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen << " i=" << MaxGap); 1547034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1548034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Stop before the interval gets so big we wouldn't be making progress. 1549034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (!LiveBefore && !LiveAfter) { 1550034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen DEBUG(dbgs() << " all\n"); 1551034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen break; 1552034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1553034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Should the interval be extended or shrunk? 1554034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen bool Shrink = true; 1555034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1556b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // How many gaps would the new range have? 1557b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen unsigned NewGaps = LiveBefore + SplitAfter - SplitBefore + LiveAfter; 1558b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen 1559b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // Legally, without causing looping? 1560b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen bool Legal = !ProgressRequired || NewGaps < NumGaps; 1561b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen 1562b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen if (Legal && MaxGap < HUGE_VALF) { 1563b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // Estimate the new spill weight. Each instruction reads or writes the 1564b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // register. Conservatively assume there are no read-modify-write 1565b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // instructions. 1566034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // 1567b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // Try to guess the size of the new interval. 1568b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen const float EstWeight = normalizeSpillWeight(blockFreq * (NewGaps + 1), 1569b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen Uses[SplitBefore].distance(Uses[SplitAfter]) + 1570b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen (LiveBefore + LiveAfter)*SlotIndex::InstrDist); 1571034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Would this split be possible to allocate? 1572034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Never allocate all gaps, we wouldn't be making progress. 157366446c803a11a26e4bb39b74091d146ac850ae4cJakob Stoklund Olesen DEBUG(dbgs() << " w=" << EstWeight); 157466446c803a11a26e4bb39b74091d146ac850ae4cJakob Stoklund Olesen if (EstWeight * Hysteresis >= MaxGap) { 1575034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen Shrink = false; 157666446c803a11a26e4bb39b74091d146ac850ae4cJakob Stoklund Olesen float Diff = EstWeight - MaxGap; 1577034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (Diff > BestDiff) { 1578034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen DEBUG(dbgs() << " (best)"); 157966446c803a11a26e4bb39b74091d146ac850ae4cJakob Stoklund Olesen BestDiff = Hysteresis * Diff; 1580034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen BestBefore = SplitBefore; 1581034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen BestAfter = SplitAfter; 1582034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1583034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1584034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1585034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1586034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Try to shrink. 1587034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (Shrink) { 1588b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen if (++SplitBefore < SplitAfter) { 1589034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen DEBUG(dbgs() << " shrink\n"); 1590034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Recompute the max when necessary. 1591034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (GapWeight[SplitBefore - 1] >= MaxGap) { 1592034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen MaxGap = GapWeight[SplitBefore]; 1593034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen for (unsigned i = SplitBefore + 1; i != SplitAfter; ++i) 1594034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen MaxGap = std::max(MaxGap, GapWeight[i]); 1595034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1596034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen continue; 1597034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1598034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen MaxGap = 0; 1599034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1600034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1601034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Try to extend the interval. 1602034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (SplitAfter >= NumGaps) { 1603034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen DEBUG(dbgs() << " end\n"); 1604034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen break; 1605034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1606034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1607034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen DEBUG(dbgs() << " extend\n"); 1608b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen MaxGap = std::max(MaxGap, GapWeight[SplitAfter++]); 1609034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1610034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1611034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1612034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Didn't find any candidates? 1613034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (BestBefore == NumGaps) 1614034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen return 0; 1615034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1616034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen DEBUG(dbgs() << "Best local split range: " << Uses[BestBefore] 1617034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen << '-' << Uses[BestAfter] << ", " << BestDiff 1618034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen << ", " << (BestAfter - BestBefore + 1) << " instrs\n"); 1619034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 162020942dcd8634ad75091fe89669868cfebf74e869Jakob Stoklund Olesen LiveRangeEdit LREdit(&VirtReg, NewVRegs, *MF, *LIS, VRM, this); 1621bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen SE->reset(LREdit); 1622bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen 1623bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen SE->openIntv(); 1624bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen SlotIndex SegStart = SE->enterIntvBefore(Uses[BestBefore]); 1625bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen SlotIndex SegStop = SE->leaveIntvAfter(Uses[BestAfter]); 1626bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen SE->useIntv(SegStart, SegStop); 1627b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen SmallVector<unsigned, 8> IntvMap; 1628b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen SE->finish(&IntvMap); 1629f42b66169d75301346e3685fd2b3e45e47806367Jakob Stoklund Olesen DebugVars->splitRegister(VirtReg.reg, LREdit.regs()); 1630b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen 1631b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // If the new range has the same number of instructions as before, mark it as 163249743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen // RS_Split2 so the next split will be forced to make progress. Otherwise, 1633b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // leave the new intervals as RS_New so they can compete. 1634b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen bool LiveBefore = BestBefore != 0 || BI.LiveIn; 1635b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen bool LiveAfter = BestAfter != NumGaps || BI.LiveOut; 1636b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen unsigned NewGaps = LiveBefore + BestAfter - BestBefore + LiveAfter; 1637b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen if (NewGaps >= NumGaps) { 1638b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen DEBUG(dbgs() << "Tagging non-progress ranges: "); 1639b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen assert(!ProgressRequired && "Didn't make progress when it was required."); 1640b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen for (unsigned i = 0, e = IntvMap.size(); i != e; ++i) 1641b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen if (IntvMap[i] == 1) { 164249743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen setStage(*LREdit.get(i), RS_Split2); 1643b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen DEBUG(dbgs() << PrintReg(LREdit.get(i)->reg)); 1644b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen } 1645b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen DEBUG(dbgs() << '\n'); 1646b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen } 16470db841f9c2b9a25fb5ecb36e350d3a802c35654cJakob Stoklund Olesen ++NumLocalSplits; 1648034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1649034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen return 0; 1650034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen} 1651034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1652034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 1653ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen// Live Range Splitting 1654ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen//===----------------------------------------------------------------------===// 1655ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 1656ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen/// trySplit - Try to split VirtReg or one of its interferences, making it 1657ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen/// assignable. 1658ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen/// @return Physreg when VirtReg may be assigned and/or new NewVRegs. 1659ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesenunsigned RAGreedy::trySplit(LiveInterval &VirtReg, AllocationOrder &Order, 1660ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen SmallVectorImpl<LiveInterval*>&NewVRegs) { 1661ccfa446450c9e3e0b3591343c4c5bea1e4cdc043Jakob Stoklund Olesen // Ranges must be Split2 or less. 1662ccfa446450c9e3e0b3591343c4c5bea1e4cdc043Jakob Stoklund Olesen if (getStage(VirtReg) >= RS_Spill) 1663ccfa446450c9e3e0b3591343c4c5bea1e4cdc043Jakob Stoklund Olesen return 0; 1664ccfa446450c9e3e0b3591343c4c5bea1e4cdc043Jakob Stoklund Olesen 1665034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Local intervals are handled separately. 1666a2ebf60ef2c434428af7f810b13327ab50245a67Jakob Stoklund Olesen if (LIS->intervalIsInOneMBB(VirtReg)) { 1667a2ebf60ef2c434428af7f810b13327ab50245a67Jakob Stoklund Olesen NamedRegionTimer T("Local Splitting", TimerGroupName, TimePassesIsEnabled); 166822a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen SA->analyze(&VirtReg); 1669d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen unsigned PhysReg = tryLocalSplit(VirtReg, Order, NewVRegs); 1670d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen if (PhysReg || !NewVRegs.empty()) 1671d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen return PhysReg; 1672d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen return tryInstructionSplit(VirtReg, Order, NewVRegs); 1673a2ebf60ef2c434428af7f810b13327ab50245a67Jakob Stoklund Olesen } 1674a2ebf60ef2c434428af7f810b13327ab50245a67Jakob Stoklund Olesen 1675a2ebf60ef2c434428af7f810b13327ab50245a67Jakob Stoklund Olesen NamedRegionTimer T("Global Splitting", TimerGroupName, TimePassesIsEnabled); 1676ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 167722a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen SA->analyze(&VirtReg); 167822a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen 16797d6b6a05b549da70b4473f015c97954c2a422724Jakob Stoklund Olesen // FIXME: SplitAnalysis may repair broken live ranges coming from the 16807d6b6a05b549da70b4473f015c97954c2a422724Jakob Stoklund Olesen // coalescer. That may cause the range to become allocatable which means that 16817d6b6a05b549da70b4473f015c97954c2a422724Jakob Stoklund Olesen // tryRegionSplit won't be making progress. This check should be replaced with 16827d6b6a05b549da70b4473f015c97954c2a422724Jakob Stoklund Olesen // an assertion when the coalescer is fixed. 16837d6b6a05b549da70b4473f015c97954c2a422724Jakob Stoklund Olesen if (SA->didRepairRange()) { 16847d6b6a05b549da70b4473f015c97954c2a422724Jakob Stoklund Olesen // VirtReg has changed, so all cached queries are invalid. 1685042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen Matrix->invalidateVirtRegs(); 16867d6b6a05b549da70b4473f015c97954c2a422724Jakob Stoklund Olesen if (unsigned PhysReg = tryAssign(VirtReg, Order, NewVRegs)) 16877d6b6a05b549da70b4473f015c97954c2a422724Jakob Stoklund Olesen return PhysReg; 16887d6b6a05b549da70b4473f015c97954c2a422724Jakob Stoklund Olesen } 16897d6b6a05b549da70b4473f015c97954c2a422724Jakob Stoklund Olesen 169049743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen // First try to split around a region spanning multiple blocks. RS_Split2 169149743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen // ranges already made dubious progress with region splitting, so they go 169249743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen // straight to single block splitting. 169349743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen if (getStage(VirtReg) < RS_Split2) { 169449743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen unsigned PhysReg = tryRegionSplit(VirtReg, Order, NewVRegs); 169549743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen if (PhysReg || !NewVRegs.empty()) 169649743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen return PhysReg; 169749743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen } 1698ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 1699dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen // Then isolate blocks. 1700dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen return tryBlockSplit(VirtReg, Order, NewVRegs); 1701ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen} 1702ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 1703ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 1704b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen//===----------------------------------------------------------------------===// 1705770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen// Main Entry Point 1706770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen//===----------------------------------------------------------------------===// 1707770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen 1708770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesenunsigned RAGreedy::selectOrSplit(LiveInterval &VirtReg, 1709ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen SmallVectorImpl<LiveInterval*> &NewVRegs) { 1710770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen // First try assigning a free register. 17115f2316a3b55f88dab2190212210770180a32aa95Jakob Stoklund Olesen AllocationOrder Order(VirtReg.reg, *VRM, RegClassInfo); 17126bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen if (unsigned PhysReg = tryAssign(VirtReg, Order, NewVRegs)) 17136bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen return PhysReg; 1714b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick 1715b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen LiveRangeStage Stage = getStage(VirtReg); 17161a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen DEBUG(dbgs() << StageName[Stage] 17171a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen << " Cascade " << ExtraRegInfo[VirtReg.reg].Cascade << '\n'); 1718b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen 171976395c9a31444fa86514473e0852cdd67752d0e8Jakob Stoklund Olesen // Try to evict a less worthy live range, but only for ranges from the primary 1720fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen // queue. The RS_Split ranges already failed to do this, and they should not 172176395c9a31444fa86514473e0852cdd67752d0e8Jakob Stoklund Olesen // get a second chance until they have been split. 1722fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen if (Stage != RS_Split) 172376395c9a31444fa86514473e0852cdd67752d0e8Jakob Stoklund Olesen if (unsigned PhysReg = tryEvict(VirtReg, Order, NewVRegs)) 172476395c9a31444fa86514473e0852cdd67752d0e8Jakob Stoklund Olesen return PhysReg; 1725b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick 1726ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen assert(NewVRegs.empty() && "Cannot append to existing NewVRegs"); 1727ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 1728107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen // The first time we see a live range, don't try to split or spill. 1729107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen // Wait until the second time, when all smaller ranges have been allocated. 1730107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen // This gives a better picture of the interference to split around. 1731fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen if (Stage < RS_Split) { 1732fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen setStage(VirtReg, RS_Split); 1733c1655e1a3c3a566b91b0513b56d61b58da1e36baJakob Stoklund Olesen DEBUG(dbgs() << "wait for second round\n"); 1734107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen NewVRegs.push_back(&VirtReg); 1735107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen return 0; 1736107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen } 1737107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen 1738bf4e10f2f69db24c107cb61d6fe10ed5b2047374Jakob Stoklund Olesen // If we couldn't allocate a register from spilling, there is probably some 1739bf4e10f2f69db24c107cb61d6fe10ed5b2047374Jakob Stoklund Olesen // invalid inline assembly. The base class wil report it. 1740fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen if (Stage >= RS_Done || !VirtReg.isSpillable()) 1741bf4e10f2f69db24c107cb61d6fe10ed5b2047374Jakob Stoklund Olesen return ~0u; 174222a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen 174346c83c80c5737743c955ff007fa6409804a7abf0Jakob Stoklund Olesen // Try splitting VirtReg or interferences. 1744ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen unsigned PhysReg = trySplit(VirtReg, Order, NewVRegs); 1745ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen if (PhysReg || !NewVRegs.empty()) 1746b64d92e29f38002e52a22fe36ea2d488968e3537Jakob Stoklund Olesen return PhysReg; 1747b64d92e29f38002e52a22fe36ea2d488968e3537Jakob Stoklund Olesen 1748770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen // Finally spill VirtReg itself. 1749770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen NamedRegionTimer T("Spiller", TimerGroupName, TimePassesIsEnabled); 175020942dcd8634ad75091fe89669868cfebf74e869Jakob Stoklund Olesen LiveRangeEdit LRE(&VirtReg, NewVRegs, *MF, *LIS, VRM, this); 175147dbf6cef761c25cfeb0aa7d624a6f98288bb96aJakob Stoklund Olesen spiller().spill(LRE); 1752fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen setStage(NewVRegs.begin(), NewVRegs.end(), RS_Done); 1753cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 1754c46570dc05851395829bef904bb6ddb1260400d1Jakob Stoklund Olesen if (VerifyEnabled) 1755c46570dc05851395829bef904bb6ddb1260400d1Jakob Stoklund Olesen MF->verify(this, "After spilling"); 1756c46570dc05851395829bef904bb6ddb1260400d1Jakob Stoklund Olesen 1757cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen // The live virtual register requesting allocation was spilled, so tell 1758cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen // the caller not to allocate anything during this round. 1759cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen return 0; 1760cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen} 1761cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 1762cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesenbool RAGreedy::runOnMachineFunction(MachineFunction &mf) { 1763cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen DEBUG(dbgs() << "********** GREEDY REGISTER ALLOCATION **********\n" 1764986d76d7b3844b9a2f3d01a48975952749267a93David Blaikie << "********** Function: " << mf.getName() << '\n'); 1765cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 1766cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen MF = &mf; 1767af24964251e27c2dd863239ba66ffd967b593be5Jakob Stoklund Olesen if (VerifyEnabled) 176889cab93fe999f6d81b4b99a71ac797b7ecfec277Jakob Stoklund Olesen MF->verify(this, "Before greedy register allocator"); 1769af24964251e27c2dd863239ba66ffd967b593be5Jakob Stoklund Olesen 1770d4348a2dc24c4fb012c1b9b20e71908f52049283Jakob Stoklund Olesen RegAllocBase::init(getAnalysis<VirtRegMap>(), 1771d4348a2dc24c4fb012c1b9b20e71908f52049283Jakob Stoklund Olesen getAnalysis<LiveIntervals>(), 1772d4348a2dc24c4fb012c1b9b20e71908f52049283Jakob Stoklund Olesen getAnalysis<LiveRegMatrix>()); 1773b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen Indexes = &getAnalysis<SlotIndexes>(); 1774f428eb6c1b09a2322b7a577b0bf2e49dd107bceaJakob Stoklund Olesen DomTree = &getAnalysis<MachineDominatorTree>(); 1775f6dff84d4e44d6c4a46c4f8a18e13c78f804547cJakob Stoklund Olesen SpillerInstance.reset(createInlineSpiller(*this, *MF, *VRM)); 1776d0bb5e2ca05d9c942223bf05e5940bb0c6cc9d3fJakob Stoklund Olesen Loops = &getAnalysis<MachineLoopInfo>(); 1777b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen Bundles = &getAnalysis<EdgeBundles>(); 1778b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen SpillPlacer = &getAnalysis<SpillPlacement>(); 1779f42b66169d75301346e3685fd2b3e45e47806367Jakob Stoklund Olesen DebugVars = &getAnalysis<LiveDebugVariables>(); 1780b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 17811b847deb26b52051de39f4cbecd224c9fbd0d1c2Jakob Stoklund Olesen SA.reset(new SplitAnalysis(*VRM, *LIS, *Loops)); 1782bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen SE.reset(new SplitEditor(*SA, *LIS, *VRM, *DomTree)); 17831a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen ExtraRegInfo.clear(); 17841a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen ExtraRegInfo.resize(MRI->getNumVirtRegs()); 17851a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen NextCascade = 1; 1786042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen IntfCache.init(MF, Matrix->getLiveUnions(), Indexes, LIS, TRI); 178700005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen GlobalCand.resize(32); // This will grow as needed. 1788d0bb5e2ca05d9c942223bf05e5940bb0c6cc9d3fJakob Stoklund Olesen 1789cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen allocatePhysRegs(); 1790cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen releaseMemory(); 1791cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen return true; 1792cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen} 1793