RegAllocGreedy.cpp revision 1ead68d769f27f6d68d4aaeffe4199fa2cacbc95
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" 16dd479e9769eceee9fcc34e2173376024f3aa3c5fJakob Stoklund Olesen#include "AllocationOrder.h" 175907d863659eb972ebb2afe07bc863a4c616f0efJakob Stoklund Olesen#include "InterferenceCache.h" 18cfafc54040cc9722995558124f253d05a038176bJakob Stoklund Olesen#include "LiveDebugVariables.h" 19cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "RegAllocBase.h" 20cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "Spiller.h" 21b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen#include "SpillPlacement.h" 22d0bb5e2ca05d9c942223bf05e5940bb0c6cc9d3fJakob Stoklund Olesen#include "SplitKit.h" 231ead68d769f27f6d68d4aaeffe4199fa2cacbc95Jakob Stoklund Olesen#include "llvm/CodeGen/VirtRegMap.h" 240db841f9c2b9a25fb5ecb36e350d3a802c35654cJakob Stoklund Olesen#include "llvm/ADT/Statistic.h" 25cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "llvm/Analysis/AliasAnalysis.h" 26cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "llvm/PassAnalysisSupport.h" 27cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "llvm/CodeGen/CalcSpillWeights.h" 28b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen#include "llvm/CodeGen/EdgeBundles.h" 29cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "llvm/CodeGen/LiveIntervalAnalysis.h" 30789d5d85ba6e9259a8e0f0bcfbd06a59ad164512Pete Cooper#include "llvm/CodeGen/LiveRangeEdit.h" 311ead68d769f27f6d68d4aaeffe4199fa2cacbc95Jakob Stoklund Olesen#include "llvm/CodeGen/LiveRegMatrix.h" 32cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "llvm/CodeGen/LiveStackAnalysis.h" 33f428eb6c1b09a2322b7a577b0bf2e49dd107bceaJakob Stoklund Olesen#include "llvm/CodeGen/MachineDominators.h" 34cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "llvm/CodeGen/MachineFunctionPass.h" 35cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "llvm/CodeGen/MachineLoopInfo.h" 36cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "llvm/CodeGen/MachineRegisterInfo.h" 37cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "llvm/CodeGen/Passes.h" 38cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "llvm/CodeGen/RegAllocRegistry.h" 39cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "llvm/Target/TargetOptions.h" 4000005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen#include "llvm/Support/CommandLine.h" 41cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "llvm/Support/Debug.h" 42cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "llvm/Support/ErrorHandling.h" 43cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "llvm/Support/raw_ostream.h" 44533f58ecdd8a4732c2f0e149387c4d8d8d4142deJakob Stoklund Olesen#include "llvm/Support/Timer.h" 45cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 4698d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen#include <queue> 4798d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen 48cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesenusing namespace llvm; 49cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 500db841f9c2b9a25fb5ecb36e350d3a802c35654cJakob Stoklund OlesenSTATISTIC(NumGlobalSplits, "Number of split global live ranges"); 510db841f9c2b9a25fb5ecb36e350d3a802c35654cJakob Stoklund OlesenSTATISTIC(NumLocalSplits, "Number of split local live ranges"); 520db841f9c2b9a25fb5ecb36e350d3a802c35654cJakob Stoklund OlesenSTATISTIC(NumEvicted, "Number of interferences evicted"); 530db841f9c2b9a25fb5ecb36e350d3a802c35654cJakob Stoklund Olesen 54708d06f7fb5dfd9c8559aea07b042a88c65645f8Jakob Stoklund Olesenstatic cl::opt<SplitEditor::ComplementSpillMode> 55708d06f7fb5dfd9c8559aea07b042a88c65645f8Jakob Stoklund OlesenSplitSpillMode("split-spill-mode", cl::Hidden, 56708d06f7fb5dfd9c8559aea07b042a88c65645f8Jakob Stoklund Olesen cl::desc("Spill mode for splitting live ranges"), 57708d06f7fb5dfd9c8559aea07b042a88c65645f8Jakob Stoklund Olesen cl::values(clEnumValN(SplitEditor::SM_Partition, "default", "Default"), 58708d06f7fb5dfd9c8559aea07b042a88c65645f8Jakob Stoklund Olesen clEnumValN(SplitEditor::SM_Size, "size", "Optimize for size"), 59708d06f7fb5dfd9c8559aea07b042a88c65645f8Jakob Stoklund Olesen clEnumValN(SplitEditor::SM_Speed, "speed", "Optimize for speed"), 60708d06f7fb5dfd9c8559aea07b042a88c65645f8Jakob Stoklund Olesen clEnumValEnd), 61708d06f7fb5dfd9c8559aea07b042a88c65645f8Jakob Stoklund Olesen cl::init(SplitEditor::SM_Partition)); 62708d06f7fb5dfd9c8559aea07b042a88c65645f8Jakob Stoklund Olesen 63cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesenstatic RegisterRegAlloc greedyRegAlloc("greedy", "greedy register allocator", 64cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen createGreedyRegisterAllocator); 65cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 66cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesennamespace { 6792a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesenclass RAGreedy : public MachineFunctionPass, 6892a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen public RegAllocBase, 6992a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen private LiveRangeEdit::Delegate { 7092a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen 71cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen // context 72cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen MachineFunction *MF; 73cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 74cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen // analyses 75b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen SlotIndexes *Indexes; 76f428eb6c1b09a2322b7a577b0bf2e49dd107bceaJakob Stoklund Olesen MachineDominatorTree *DomTree; 77d0bb5e2ca05d9c942223bf05e5940bb0c6cc9d3fJakob Stoklund Olesen MachineLoopInfo *Loops; 78b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen EdgeBundles *Bundles; 79b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen SpillPlacement *SpillPlacer; 80f42b66169d75301346e3685fd2b3e45e47806367Jakob Stoklund Olesen LiveDebugVariables *DebugVars; 81f428eb6c1b09a2322b7a577b0bf2e49dd107bceaJakob Stoklund Olesen 82cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen // state 83cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen std::auto_ptr<Spiller> SpillerInstance; 8498d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen std::priority_queue<std::pair<unsigned, unsigned> > Queue; 851a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen unsigned NextCascade; 8622a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen 8722a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // Live ranges pass through a number of stages as we try to allocate them. 8822a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // Some of the stages may also create new live ranges: 8922a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // 9022a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // - Region splitting. 9122a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // - Per-block splitting. 9222a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // - Local splitting. 9322a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // - Spilling. 9422a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // 9522a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // Ranges produced by one of the stages skip the previous stages when they are 9622a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // dequeued. This improves performance because we can skip interference checks 9722a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // that are unlikely to give any results. It also guarantees that the live 9822a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // range splitting algorithm terminates, something that is otherwise hard to 9922a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // ensure. 10022a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen enum LiveRangeStage { 101fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen /// Newly created live range that has never been queued. 102fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen RS_New, 103fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen 104fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen /// Only attempt assignment and eviction. Then requeue as RS_Split. 105fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen RS_Assign, 106fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen 107fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen /// Attempt live range splitting if assignment is impossible. 108fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen RS_Split, 109fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen 11049743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen /// Attempt more aggressive live range splitting that is guaranteed to make 11149743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen /// progress. This is used for split products that may not be making 11249743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen /// progress. 11349743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen RS_Split2, 11449743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen 115fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen /// Live range will be spilled. No more splitting will be attempted. 116fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen RS_Spill, 117fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen 118fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen /// There is nothing more we can do to this live range. Abort compilation 119fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen /// if it can't be assigned. 120fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen RS_Done 12122a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen }; 12222a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen 123b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen static const char *const StageName[]; 124b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen 1251a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen // RegInfo - Keep additional information about each live range. 1261a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen struct RegInfo { 1271a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen LiveRangeStage Stage; 1281a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen 1291a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen // Cascade - Eviction loop prevention. See canEvictInterference(). 1301a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen unsigned Cascade; 1311a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen 1321a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen RegInfo() : Stage(RS_New), Cascade(0) {} 1331a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen }; 1341a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen 1351a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen IndexedMap<RegInfo, VirtReg2IndexFunctor> ExtraRegInfo; 13622a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen 13722a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen LiveRangeStage getStage(const LiveInterval &VirtReg) const { 1381a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen return ExtraRegInfo[VirtReg.reg].Stage; 1391a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen } 1401a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen 1411a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen void setStage(const LiveInterval &VirtReg, LiveRangeStage Stage) { 1421a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen ExtraRegInfo.resize(MRI->getNumVirtRegs()); 1431a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen ExtraRegInfo[VirtReg.reg].Stage = Stage; 14422a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen } 14522a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen 14622a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen template<typename Iterator> 14722a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen void setStage(Iterator Begin, Iterator End, LiveRangeStage NewStage) { 1481a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen ExtraRegInfo.resize(MRI->getNumVirtRegs()); 149f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund Olesen for (;Begin != End; ++Begin) { 150f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund Olesen unsigned Reg = (*Begin)->reg; 1511a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen if (ExtraRegInfo[Reg].Stage == RS_New) 1521a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen ExtraRegInfo[Reg].Stage = NewStage; 153f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund Olesen } 15422a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen } 155cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 15651458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen /// Cost of evicting interference. 15751458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen struct EvictionCost { 15851458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen unsigned BrokenHints; ///< Total number of broken hints. 15951458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen float MaxWeight; ///< Maximum spill weight evicted. 16051458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen 16151458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen EvictionCost(unsigned B = 0) : BrokenHints(B), MaxWeight(0) {} 16251458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen 16351458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen bool operator<(const EvictionCost &O) const { 16451458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen if (BrokenHints != O.BrokenHints) 16551458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen return BrokenHints < O.BrokenHints; 16651458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen return MaxWeight < O.MaxWeight; 16751458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen } 16851458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen }; 16951458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen 170b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen // splitting state. 17122a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen std::auto_ptr<SplitAnalysis> SA; 172bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen std::auto_ptr<SplitEditor> SE; 173b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 174eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen /// Cached per-block interference maps 175eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen InterferenceCache IntfCache; 176eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen 1777b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen /// All basic blocks where the current register has uses. 17896dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen SmallVector<SpillPlacement::BlockConstraint, 8> SplitConstraints; 179b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 18096dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen /// Global live range splitting candidate info. 18196dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen struct GlobalSplitCandidate { 18200005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // Register intended for assignment, or 0. 18396dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen unsigned PhysReg; 18400005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen 18500005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // SplitKit interval index for this candidate. 18600005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen unsigned IntvIdx; 18700005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen 18800005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // Interference for PhysReg. 189c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen InterferenceCache::Cursor Intf; 19000005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen 19100005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // Bundles where this candidate should be live. 19296dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen BitVector LiveBundles; 1935db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen SmallVector<unsigned, 8> ActiveBlocks; 1945db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen 195c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen void reset(InterferenceCache &Cache, unsigned Reg) { 1965db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen PhysReg = Reg; 19700005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen IntvIdx = 0; 198c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen Intf.setPhysReg(Cache, Reg); 1995db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen LiveBundles.clear(); 2005db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen ActiveBlocks.clear(); 2015db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen } 20200005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen 20300005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // Set B[i] = C for every live bundle where B[i] was NoCand. 20400005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen unsigned getBundles(SmallVectorImpl<unsigned> &B, unsigned C) { 20500005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen unsigned Count = 0; 20600005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen for (int i = LiveBundles.find_first(); i >= 0; 20700005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen i = LiveBundles.find_next(i)) 20800005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen if (B[i] == NoCand) { 20900005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen B[i] = C; 21000005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen Count++; 21100005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen } 21200005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen return Count; 21300005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen } 21496dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen }; 21596dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen 21696dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen /// Candidate info for for each PhysReg in AllocationOrder. 21796dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen /// This vector never shrinks, but grows to the size of the largest register 21896dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen /// class. 21996dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen SmallVector<GlobalSplitCandidate, 32> GlobalCand; 22096dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen 22100005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen enum { NoCand = ~0u }; 22200005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen 22300005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen /// Candidate map. Each edge bundle is assigned to a GlobalCand entry, or to 22400005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen /// NoCand which indicates the stack interval. 22500005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen SmallVector<unsigned, 32> BundleCand; 22600005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen 227cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesenpublic: 228cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen RAGreedy(); 229cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 230cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen /// Return the pass name. 231cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen virtual const char* getPassName() const { 232533f58ecdd8a4732c2f0e149387c4d8d8d4142deJakob Stoklund Olesen return "Greedy Register Allocator"; 233cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen } 234cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 235cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen /// RAGreedy analysis usage. 236cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen virtual void getAnalysisUsage(AnalysisUsage &AU) const; 237cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen virtual void releaseMemory(); 238cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen virtual Spiller &spiller() { return *SpillerInstance; } 23998d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen virtual void enqueue(LiveInterval *LI); 24098d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen virtual LiveInterval *dequeue(); 241ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen virtual unsigned selectOrSplit(LiveInterval&, 242ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen SmallVectorImpl<LiveInterval*>&); 243cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 244cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen /// Perform register allocation. 245cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen virtual bool runOnMachineFunction(MachineFunction &mf); 246cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 247cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen static char ID; 248b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick 249b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trickprivate: 2507792e980c43536814ea42448db9799b4da32fef6Jakob Stoklund Olesen bool LRE_CanEraseVirtReg(unsigned); 2511d5b84508173b93faf513032b3847152e6060791Jakob Stoklund Olesen void LRE_WillShrinkVirtReg(unsigned); 252f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund Olesen void LRE_DidCloneVirtReg(unsigned, unsigned); 25392a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen 254200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen float calcSpillCost(); 255f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen bool addSplitConstraints(InterferenceCache::Cursor, float&); 256f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen void addThroughConstraints(InterferenceCache::Cursor, ArrayRef<unsigned>); 257c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen void growRegion(GlobalSplitCandidate &Cand); 258c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen float calcGlobalSplitCost(GlobalSplitCandidate&); 25987972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen bool calcCompactRegion(GlobalSplitCandidate&); 26000005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen void splitAroundRegion(LiveRangeEdit&, ArrayRef<unsigned>); 261034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen void calcGapWeights(unsigned, SmallVectorImpl<float>&); 26251458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen bool shouldEvict(LiveInterval &A, bool, LiveInterval &B, bool); 26351458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen bool canEvictInterference(LiveInterval&, unsigned, bool, EvictionCost&); 26451458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen void evictInterference(LiveInterval&, unsigned, 26551458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen SmallVectorImpl<LiveInterval*>&); 266b64d92e29f38002e52a22fe36ea2d488968e3537Jakob Stoklund Olesen 2676bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen unsigned tryAssign(LiveInterval&, AllocationOrder&, 2686bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen SmallVectorImpl<LiveInterval*>&); 26998c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen unsigned tryEvict(LiveInterval&, AllocationOrder&, 2706bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen SmallVectorImpl<LiveInterval*>&, unsigned = ~0u); 271b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen unsigned tryRegionSplit(LiveInterval&, AllocationOrder&, 272b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen SmallVectorImpl<LiveInterval*>&); 273dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen unsigned tryBlockSplit(LiveInterval&, AllocationOrder&, 274dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen SmallVectorImpl<LiveInterval*>&); 275d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen unsigned tryInstructionSplit(LiveInterval&, AllocationOrder&, 276d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen SmallVectorImpl<LiveInterval*>&); 277034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen unsigned tryLocalSplit(LiveInterval&, AllocationOrder&, 278034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen SmallVectorImpl<LiveInterval*>&); 279b64d92e29f38002e52a22fe36ea2d488968e3537Jakob Stoklund Olesen unsigned trySplit(LiveInterval&, AllocationOrder&, 280b64d92e29f38002e52a22fe36ea2d488968e3537Jakob Stoklund Olesen SmallVectorImpl<LiveInterval*>&); 281cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen}; 282cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen} // end anonymous namespace 283cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 284cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesenchar RAGreedy::ID = 0; 285cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 286b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen#ifndef NDEBUG 287b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesenconst char *const RAGreedy::StageName[] = { 288fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen "RS_New", 289fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen "RS_Assign", 290fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen "RS_Split", 29149743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen "RS_Split2", 292fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen "RS_Spill", 293fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen "RS_Done" 294b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen}; 295b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen#endif 296b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen 297200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen// Hysteresis to use when comparing floats. 298200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen// This helps stabilize decisions based on float comparisons. 299200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesenconst float Hysteresis = 0.98f; 300200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen 301200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen 302cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund OlesenFunctionPass* llvm::createGreedyRegisterAllocator() { 303cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen return new RAGreedy(); 304cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen} 305cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 3061a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund OlesenRAGreedy::RAGreedy(): MachineFunctionPass(ID) { 307cfafc54040cc9722995558124f253d05a038176bJakob Stoklund Olesen initializeLiveDebugVariablesPass(*PassRegistry::getPassRegistry()); 308b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen initializeSlotIndexesPass(*PassRegistry::getPassRegistry()); 309cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen initializeLiveIntervalsPass(*PassRegistry::getPassRegistry()); 310cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen initializeSlotIndexesPass(*PassRegistry::getPassRegistry()); 3115b220213bfe9c37c2bb41a7ae0804e06a14f1007Rafael Espindola initializeRegisterCoalescerPass(*PassRegistry::getPassRegistry()); 31242b7a71dc7381d1f38bf7b7201fc26dd80453364Andrew Trick initializeMachineSchedulerPass(*PassRegistry::getPassRegistry()); 313cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen initializeCalculateSpillWeightsPass(*PassRegistry::getPassRegistry()); 314cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen initializeLiveStacksPass(*PassRegistry::getPassRegistry()); 315cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry()); 316cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen initializeMachineLoopInfoPass(*PassRegistry::getPassRegistry()); 317cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen initializeVirtRegMapPass(*PassRegistry::getPassRegistry()); 318042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen initializeLiveRegMatrixPass(*PassRegistry::getPassRegistry()); 319b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen initializeEdgeBundlesPass(*PassRegistry::getPassRegistry()); 320b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen initializeSpillPlacementPass(*PassRegistry::getPassRegistry()); 321cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen} 322cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 323cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesenvoid RAGreedy::getAnalysisUsage(AnalysisUsage &AU) const { 324cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.setPreservesCFG(); 325cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addRequired<AliasAnalysis>(); 326cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addPreserved<AliasAnalysis>(); 327cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addRequired<LiveIntervals>(); 32805ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen AU.addPreserved<LiveIntervals>(); 329b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen AU.addRequired<SlotIndexes>(); 330cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addPreserved<SlotIndexes>(); 331cfafc54040cc9722995558124f253d05a038176bJakob Stoklund Olesen AU.addRequired<LiveDebugVariables>(); 332cfafc54040cc9722995558124f253d05a038176bJakob Stoklund Olesen AU.addPreserved<LiveDebugVariables>(); 333cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addRequired<LiveStacks>(); 334cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addPreserved<LiveStacks>(); 335bb36a438722d4d56febc07c6472c8446bb6faafeEvan Cheng AU.addRequired<CalculateSpillWeights>(); 336f428eb6c1b09a2322b7a577b0bf2e49dd107bceaJakob Stoklund Olesen AU.addRequired<MachineDominatorTree>(); 337f428eb6c1b09a2322b7a577b0bf2e49dd107bceaJakob Stoklund Olesen AU.addPreserved<MachineDominatorTree>(); 338cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addRequired<MachineLoopInfo>(); 339cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addPreserved<MachineLoopInfo>(); 340cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addRequired<VirtRegMap>(); 341cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addPreserved<VirtRegMap>(); 342042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen AU.addRequired<LiveRegMatrix>(); 343042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen AU.addPreserved<LiveRegMatrix>(); 344b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen AU.addRequired<EdgeBundles>(); 345b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen AU.addRequired<SpillPlacement>(); 346cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen MachineFunctionPass::getAnalysisUsage(AU); 347cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen} 348cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 34992a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen 35092a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 35192a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen// LiveRangeEdit delegate methods 35292a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 35392a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen 3547792e980c43536814ea42448db9799b4da32fef6Jakob Stoklund Olesenbool RAGreedy::LRE_CanEraseVirtReg(unsigned VirtReg) { 355042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen if (VRM->hasPhys(VirtReg)) { 356042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen Matrix->unassign(LIS->getInterval(VirtReg)); 3577792e980c43536814ea42448db9799b4da32fef6Jakob Stoklund Olesen return true; 3587792e980c43536814ea42448db9799b4da32fef6Jakob Stoklund Olesen } 3597792e980c43536814ea42448db9799b4da32fef6Jakob Stoklund Olesen // Unassigned virtreg is probably in the priority queue. 3607792e980c43536814ea42448db9799b4da32fef6Jakob Stoklund Olesen // RegAllocBase will erase it after dequeueing. 3617792e980c43536814ea42448db9799b4da32fef6Jakob Stoklund Olesen return false; 3627792e980c43536814ea42448db9799b4da32fef6Jakob Stoklund Olesen} 36392a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen 3641d5b84508173b93faf513032b3847152e6060791Jakob Stoklund Olesenvoid RAGreedy::LRE_WillShrinkVirtReg(unsigned VirtReg) { 365042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen if (!VRM->hasPhys(VirtReg)) 3661d5b84508173b93faf513032b3847152e6060791Jakob Stoklund Olesen return; 3671d5b84508173b93faf513032b3847152e6060791Jakob Stoklund Olesen 3681d5b84508173b93faf513032b3847152e6060791Jakob Stoklund Olesen // Register is assigned, put it back on the queue for reassignment. 3691d5b84508173b93faf513032b3847152e6060791Jakob Stoklund Olesen LiveInterval &LI = LIS->getInterval(VirtReg); 370042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen Matrix->unassign(LI); 3711d5b84508173b93faf513032b3847152e6060791Jakob Stoklund Olesen enqueue(&LI); 3721d5b84508173b93faf513032b3847152e6060791Jakob Stoklund Olesen} 3731d5b84508173b93faf513032b3847152e6060791Jakob Stoklund Olesen 374f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund Olesenvoid RAGreedy::LRE_DidCloneVirtReg(unsigned New, unsigned Old) { 3750d4fea786670473b53d285be378e619399e03488Jakob Stoklund Olesen // Cloning a register we haven't even heard about yet? Just ignore it. 3760d4fea786670473b53d285be378e619399e03488Jakob Stoklund Olesen if (!ExtraRegInfo.inBounds(Old)) 3770d4fea786670473b53d285be378e619399e03488Jakob Stoklund Olesen return; 3780d4fea786670473b53d285be378e619399e03488Jakob Stoklund Olesen 379f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund Olesen // LRE may clone a virtual register because dead code elimination causes it to 380165e231c4295deb5cabd124d08e231b551bcc0b2Jakob Stoklund Olesen // be split into connected components. The new components are much smaller 381165e231c4295deb5cabd124d08e231b551bcc0b2Jakob Stoklund Olesen // than the original, so they should get a new chance at being assigned. 382f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund Olesen // same stage as the parent. 383165e231c4295deb5cabd124d08e231b551bcc0b2Jakob Stoklund Olesen ExtraRegInfo[Old].Stage = RS_Assign; 3841a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen ExtraRegInfo.grow(New); 3851a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen ExtraRegInfo[New] = ExtraRegInfo[Old]; 386f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund Olesen} 387f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund Olesen 388cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesenvoid RAGreedy::releaseMemory() { 389cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen SpillerInstance.reset(0); 3901a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen ExtraRegInfo.clear(); 3915db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen GlobalCand.clear(); 392cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen} 393cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 39498d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesenvoid RAGreedy::enqueue(LiveInterval *LI) { 39598d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen // Prioritize live ranges by size, assigning larger ranges first. 39698d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen // The queue holds (size, reg) pairs. 397107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen const unsigned Size = LI->getSize(); 398107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen const unsigned Reg = LI->reg; 39998d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen assert(TargetRegisterInfo::isVirtualRegister(Reg) && 40098d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen "Can only enqueue virtual registers"); 401107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen unsigned Prio; 40290c1d7ddfc65654f7efe72d56cad65d1af9e6b2aJakob Stoklund Olesen 4031a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen ExtraRegInfo.grow(Reg); 4041a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen if (ExtraRegInfo[Reg].Stage == RS_New) 405fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen ExtraRegInfo[Reg].Stage = RS_Assign; 406f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund Olesen 407cc07e04262fe4bc35469fbadc53d2ec7bfd02fe2Jakob Stoklund Olesen if (ExtraRegInfo[Reg].Stage == RS_Split) { 408eb29157d80847c207b77910bcd40a6a6c91ca5c5Jakob Stoklund Olesen // Unsplit ranges that couldn't be allocated immediately are deferred until 409a16a25ddeaf495b78b04e2a19feeac00d9824e63Jakob Stoklund Olesen // everything else has been allocated. 410a16a25ddeaf495b78b04e2a19feeac00d9824e63Jakob Stoklund Olesen Prio = Size; 411cc07e04262fe4bc35469fbadc53d2ec7bfd02fe2Jakob Stoklund Olesen } else { 412a16a25ddeaf495b78b04e2a19feeac00d9824e63Jakob Stoklund Olesen // Everything is allocated in long->short order. Long ranges that don't fit 413a16a25ddeaf495b78b04e2a19feeac00d9824e63Jakob Stoklund Olesen // should be spilled (or split) ASAP so they don't create interference. 414107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen Prio = (1u << 31) + Size; 415d2a50734234a80893ad71da90d9f32032c47e000Jakob Stoklund Olesen 416eb29157d80847c207b77910bcd40a6a6c91ca5c5Jakob Stoklund Olesen // Boost ranges that have a physical register hint. 417eb29157d80847c207b77910bcd40a6a6c91ca5c5Jakob Stoklund Olesen if (TargetRegisterInfo::isPhysicalRegister(VRM->getRegAllocPref(Reg))) 418eb29157d80847c207b77910bcd40a6a6c91ca5c5Jakob Stoklund Olesen Prio |= (1u << 30); 419eb29157d80847c207b77910bcd40a6a6c91ca5c5Jakob Stoklund Olesen } 420107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen 421e3b23cde80b19507f1d8b641a541e91ace0864dcJakob Stoklund Olesen Queue.push(std::make_pair(Prio, ~Reg)); 42290c1d7ddfc65654f7efe72d56cad65d1af9e6b2aJakob Stoklund Olesen} 42390c1d7ddfc65654f7efe72d56cad65d1af9e6b2aJakob Stoklund Olesen 42498d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund OlesenLiveInterval *RAGreedy::dequeue() { 42598d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen if (Queue.empty()) 42698d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen return 0; 427e3b23cde80b19507f1d8b641a541e91ace0864dcJakob Stoklund Olesen LiveInterval *LI = &LIS->getInterval(~Queue.top().second); 42898d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen Queue.pop(); 42998d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen return LI; 43098d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen} 431770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen 4326bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen 4336bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 4346bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen// Direct Assignment 4356bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 4366bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen 4376bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen/// tryAssign - Try to assign VirtReg to an available register. 4386bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesenunsigned RAGreedy::tryAssign(LiveInterval &VirtReg, 4396bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen AllocationOrder &Order, 4406bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen SmallVectorImpl<LiveInterval*> &NewVRegs) { 4416bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen Order.rewind(); 4426bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen unsigned PhysReg; 443042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen while ((PhysReg = Order.next())) 444042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen if (!Matrix->checkInterference(VirtReg, PhysReg)) 4456bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen break; 4466bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen if (!PhysReg || Order.isHint(PhysReg)) 4476bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen return PhysReg; 4486bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen 44951458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // PhysReg is available, but there may be a better choice. 45051458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen 45151458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // If we missed a simple hint, try to cheaply evict interference from the 45251458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // preferred register. 45351458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen if (unsigned Hint = MRI->getSimpleHint(VirtReg.reg)) 454042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen if (Order.isHint(Hint)) { 45551458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen DEBUG(dbgs() << "missed hint " << PrintReg(Hint, TRI) << '\n'); 45651458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen EvictionCost MaxCost(1); 45751458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen if (canEvictInterference(VirtReg, Hint, true, MaxCost)) { 45851458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen evictInterference(VirtReg, Hint, NewVRegs); 45951458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen return Hint; 46051458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen } 46151458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen } 46251458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen 46351458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // Try to evict interference from a cheaper alternative. 4646bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen unsigned Cost = TRI->getCostPerUse(PhysReg); 4656bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen 4666bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen // Most registers have 0 additional cost. 4676bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen if (!Cost) 4686bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen return PhysReg; 4696bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen 4706bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen DEBUG(dbgs() << PrintReg(PhysReg, TRI) << " is available at cost " << Cost 4716bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen << '\n'); 4726bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen unsigned CheapReg = tryEvict(VirtReg, Order, NewVRegs, Cost); 4736bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen return CheapReg ? CheapReg : PhysReg; 4746bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen} 4756bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen 4766bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen 477770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen//===----------------------------------------------------------------------===// 47898c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen// Interference eviction 47998c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 4802710638db2eb84cd7eefb8bb9a1b7e5c49413d45Jakob Stoklund Olesen 48151458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// shouldEvict - determine if A should evict the assigned live range B. The 48251458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// eviction policy defined by this function together with the allocation order 48351458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// defined by enqueue() decides which registers ultimately end up being split 48451458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// and spilled. 485b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen/// 4861a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen/// Cascade numbers are used to prevent infinite loops if this function is a 4871a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen/// cyclic relation. 48851458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// 48951458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// @param A The live range to be assigned. 49051458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// @param IsHint True when A is about to be assigned to its preferred 49151458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// register. 49251458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// @param B The live range to be evicted. 49351458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// @param BreaksHint True when B is already assigned to its preferred register. 49451458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesenbool RAGreedy::shouldEvict(LiveInterval &A, bool IsHint, 49551458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen LiveInterval &B, bool BreaksHint) { 49649743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen bool CanSplit = getStage(B) < RS_Spill; 49751458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen 49851458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // Be fairly aggressive about following hints as long as the evictee can be 49951458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // split. 50051458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen if (CanSplit && IsHint && !BreaksHint) 50151458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen return true; 50251458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen 5031a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen return A.weight > B.weight; 504b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen} 505b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen 50651458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// canEvictInterference - Return true if all interferences between VirtReg and 50751458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// PhysReg can be evicted. When OnlyCheap is set, don't do anything 50851458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// 50951458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// @param VirtReg Live range that is about to be assigned. 51051458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// @param PhysReg Desired register for assignment. 51167c8978617c3bce9d07210f93f6c64c715f77695Dmitri Gribenko/// @param IsHint True when PhysReg is VirtReg's preferred register. 51251458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// @param MaxCost Only look for cheaper candidates and update with new cost 51351458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// when returning true. 51451458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// @returns True when interference can be evicted cheaper than MaxCost. 51598c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesenbool RAGreedy::canEvictInterference(LiveInterval &VirtReg, unsigned PhysReg, 51651458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen bool IsHint, EvictionCost &MaxCost) { 517042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen // It is only possible to evict virtual register interference. 518042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen if (Matrix->checkInterference(VirtReg, PhysReg) > LiveRegMatrix::IK_VirtReg) 519042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen return false; 520042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen 5211a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen // Find VirtReg's cascade number. This will be unassigned if VirtReg was never 5221a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen // involved in an eviction before. If a cascade number was assigned, deny 5231a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen // evicting anything with the same or a newer cascade number. This prevents 5241a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen // infinite eviction loops. 5251a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen // 5261a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen // This works out so a register without a cascade number is allowed to evict 5271a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen // anything, and it can be evicted by anything. 5281a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen unsigned Cascade = ExtraRegInfo[VirtReg.reg].Cascade; 5291a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen if (!Cascade) 5301a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen Cascade = NextCascade; 5311a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen 53251458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen EvictionCost Cost; 533042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) { 534042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen LiveIntervalUnion::Query &Q = Matrix->query(VirtReg, *Units); 5353f5bedf5cbde2cc2badc86b1a0b377f6efcde71cJakob Stoklund Olesen // If there is 10 or more interferences, chances are one is heavier. 53651458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen if (Q.collectInterferingVRegs(10) >= 10) 53798c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen return false; 53898c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen 5393f5bedf5cbde2cc2badc86b1a0b377f6efcde71cJakob Stoklund Olesen // Check if any interfering live range is heavier than MaxWeight. 5403f5bedf5cbde2cc2badc86b1a0b377f6efcde71cJakob Stoklund Olesen for (unsigned i = Q.interferingVRegs().size(); i; --i) { 5413f5bedf5cbde2cc2badc86b1a0b377f6efcde71cJakob Stoklund Olesen LiveInterval *Intf = Q.interferingVRegs()[i - 1]; 542042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen assert(TargetRegisterInfo::isVirtualRegister(Intf->reg) && 543042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen "Only expecting virtual register interference from query"); 54451458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // Never evict spill products. They cannot split or spill. 545fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen if (getStage(*Intf) == RS_Done) 5461a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen return false; 54751458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // Once a live range becomes small enough, it is urgent that we find a 54851458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // register for it. This is indicated by an infinite spill weight. These 54951458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // urgent live ranges get to evict almost anything. 5509cda1be0aa5e9e70ae493ef6944a8c202c1c70e6Jakob Stoklund Olesen // 5519cda1be0aa5e9e70ae493ef6944a8c202c1c70e6Jakob Stoklund Olesen // Also allow urgent evictions of unspillable ranges from a strictly 5529cda1be0aa5e9e70ae493ef6944a8c202c1c70e6Jakob Stoklund Olesen // larger allocation order. 5539cda1be0aa5e9e70ae493ef6944a8c202c1c70e6Jakob Stoklund Olesen bool Urgent = !VirtReg.isSpillable() && 5549cda1be0aa5e9e70ae493ef6944a8c202c1c70e6Jakob Stoklund Olesen (Intf->isSpillable() || 5559cda1be0aa5e9e70ae493ef6944a8c202c1c70e6Jakob Stoklund Olesen RegClassInfo.getNumAllocatableRegs(MRI->getRegClass(VirtReg.reg)) < 5569cda1be0aa5e9e70ae493ef6944a8c202c1c70e6Jakob Stoklund Olesen RegClassInfo.getNumAllocatableRegs(MRI->getRegClass(Intf->reg))); 55751458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // Only evict older cascades or live ranges without a cascade. 55851458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen unsigned IntfCascade = ExtraRegInfo[Intf->reg].Cascade; 55951458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen if (Cascade <= IntfCascade) { 56051458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen if (!Urgent) 56151458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen return false; 56251458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // We permit breaking cascades for urgent evictions. It should be the 56351458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // last resort, though, so make it really expensive. 56451458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen Cost.BrokenHints += 10; 56551458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen } 56651458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // Would this break a satisfied hint? 56751458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen bool BreaksHint = VRM->hasPreferredPhys(Intf->reg); 56851458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // Update eviction cost. 56951458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen Cost.BrokenHints += BreaksHint; 57051458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen Cost.MaxWeight = std::max(Cost.MaxWeight, Intf->weight); 57151458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // Abort if this would be too expensive. 57251458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen if (!(Cost < MaxCost)) 573b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen return false; 57451458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // Finally, apply the eviction policy for non-urgent evictions. 57551458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen if (!Urgent && !shouldEvict(VirtReg, IsHint, *Intf, BreaksHint)) 57676395c9a31444fa86514473e0852cdd67752d0e8Jakob Stoklund Olesen return false; 5772710638db2eb84cd7eefb8bb9a1b7e5c49413d45Jakob Stoklund Olesen } 5782710638db2eb84cd7eefb8bb9a1b7e5c49413d45Jakob Stoklund Olesen } 57951458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen MaxCost = Cost; 58098c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen return true; 58198c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen} 58298c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen 58351458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// evictInterference - Evict any interferring registers that prevent VirtReg 58451458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// from being assigned to Physreg. This assumes that canEvictInterference 58551458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// returned true. 58651458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesenvoid RAGreedy::evictInterference(LiveInterval &VirtReg, unsigned PhysReg, 58751458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen SmallVectorImpl<LiveInterval*> &NewVRegs) { 58851458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // Make sure that VirtReg has a cascade number, and assign that cascade 58951458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // number to every evicted register. These live ranges than then only be 59051458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // evicted by a newer cascade, preventing infinite loops. 59151458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen unsigned Cascade = ExtraRegInfo[VirtReg.reg].Cascade; 59251458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen if (!Cascade) 59351458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen Cascade = ExtraRegInfo[VirtReg.reg].Cascade = NextCascade++; 59451458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen 59551458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen DEBUG(dbgs() << "evicting " << PrintReg(PhysReg, TRI) 59651458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen << " interference: Cascade " << Cascade << '\n'); 597042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen 598042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen // Collect all interfering virtregs first. 599042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen SmallVector<LiveInterval*, 8> Intfs; 600042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) { 601042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen LiveIntervalUnion::Query &Q = Matrix->query(VirtReg, *Units); 60251458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen assert(Q.seenAllInterferences() && "Didn't check all interfererences."); 603042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen ArrayRef<LiveInterval*> IVR = Q.interferingVRegs(); 604042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen Intfs.append(IVR.begin(), IVR.end()); 605042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen } 606042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen 607042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen // Evict them second. This will invalidate the queries. 608042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen for (unsigned i = 0, e = Intfs.size(); i != e; ++i) { 609042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen LiveInterval *Intf = Intfs[i]; 610042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen // The same VirtReg may be present in multiple RegUnits. Skip duplicates. 611042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen if (!VRM->hasPhys(Intf->reg)) 612042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen continue; 613042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen Matrix->unassign(*Intf); 614042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen assert((ExtraRegInfo[Intf->reg].Cascade < Cascade || 615042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen VirtReg.isSpillable() < Intf->isSpillable()) && 616042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen "Cannot decrease cascade number, illegal eviction"); 617042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen ExtraRegInfo[Intf->reg].Cascade = Cascade; 618042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen ++NumEvicted; 619042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen NewVRegs.push_back(Intf); 62051458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen } 62151458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen} 62251458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen 62398c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen/// tryEvict - Try to evict all interferences for a physreg. 62476395c9a31444fa86514473e0852cdd67752d0e8Jakob Stoklund Olesen/// @param VirtReg Currently unassigned virtual register. 62576395c9a31444fa86514473e0852cdd67752d0e8Jakob Stoklund Olesen/// @param Order Physregs to try. 62676395c9a31444fa86514473e0852cdd67752d0e8Jakob Stoklund Olesen/// @return Physreg to assign VirtReg, or 0. 62798c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesenunsigned RAGreedy::tryEvict(LiveInterval &VirtReg, 62898c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen AllocationOrder &Order, 6296bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen SmallVectorImpl<LiveInterval*> &NewVRegs, 6306bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen unsigned CostPerUseLimit) { 63198c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen NamedRegionTimer T("Evict", TimerGroupName, TimePassesIsEnabled); 63298c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen 63351458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // Keep track of the cheapest interference seen so far. 63451458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen EvictionCost BestCost(~0u); 63598c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen unsigned BestPhys = 0; 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; 64251458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen } 64351458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen 64498c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen Order.rewind(); 64598c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen while (unsigned PhysReg = Order.next()) { 6466bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen if (TRI->getCostPerUse(PhysReg) >= CostPerUseLimit) 6476bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen continue; 64851458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // The first use of a callee-saved register in a function has cost 1. 64951458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // Don't start using a CSR when the CostPerUseLimit is low. 65051458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen if (CostPerUseLimit == 1) 65151458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen if (unsigned CSR = RegClassInfo.getLastCalleeSavedAlias(PhysReg)) 65251458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen if (!MRI->isPhysRegUsed(CSR)) { 65351458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen DEBUG(dbgs() << PrintReg(PhysReg, TRI) << " would clobber CSR " 65451458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen << PrintReg(CSR, TRI) << '\n'); 65551458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen continue; 65651458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen } 65751458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen 65851458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen if (!canEvictInterference(VirtReg, PhysReg, false, BestCost)) 65998c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen continue; 66098c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen 66198c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen // Best so far. 66298c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen BestPhys = PhysReg; 66351458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen 66457f1e2cee06f9b57995727d786aeb1031c5376bdJakob Stoklund Olesen // Stop if the hint can be used. 66557f1e2cee06f9b57995727d786aeb1031c5376bdJakob Stoklund Olesen if (Order.isHint(PhysReg)) 66657f1e2cee06f9b57995727d786aeb1031c5376bdJakob Stoklund Olesen break; 6672710638db2eb84cd7eefb8bb9a1b7e5c49413d45Jakob Stoklund Olesen } 6682710638db2eb84cd7eefb8bb9a1b7e5c49413d45Jakob Stoklund Olesen 66998c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen if (!BestPhys) 67098c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen return 0; 67198c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen 67251458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen evictInterference(VirtReg, BestPhys, NewVRegs); 67398c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen return BestPhys; 674b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick} 675b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick 676770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen 677770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen//===----------------------------------------------------------------------===// 678b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen// Region Splitting 679b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen//===----------------------------------------------------------------------===// 680b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 6811b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen/// addSplitConstraints - Fill out the SplitConstraints vector based on the 6821b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen/// interference pattern in Physreg and its aliases. Add the constraints to 6831b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen/// SpillPlacement and return the static cost of this split in Cost, assuming 6841b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen/// that all preferences in SplitConstraints are met. 685f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen/// Return false if there are no bundles with positive bias. 686f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesenbool RAGreedy::addSplitConstraints(InterferenceCache::Cursor Intf, 687f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen float &Cost) { 688db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks(); 689eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen 690b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen // Reset interference dependent info. 691db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen SplitConstraints.resize(UseBlocks.size()); 69296dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen float StaticCost = 0; 693db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen for (unsigned i = 0; i != UseBlocks.size(); ++i) { 694db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen const SplitAnalysis::BlockInfo &BI = UseBlocks[i]; 69596dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen SpillPlacement::BlockConstraint &BC = SplitConstraints[i]; 69696dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen 697f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen BC.Number = BI.MBB->getNumber(); 698eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen Intf.moveToBlock(BC.Number); 699db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen BC.Entry = BI.LiveIn ? SpillPlacement::PrefReg : SpillPlacement::DontCare; 700db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen BC.Exit = BI.LiveOut ? SpillPlacement::PrefReg : SpillPlacement::DontCare; 7015ebca793db6262386d7464d03cdaefeb5b640ad3Jakob Stoklund Olesen BC.ChangesValue = BI.FirstDef; 702b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 703eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen if (!Intf.hasInterference()) 704eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen continue; 705eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen 70696dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen // Number of spill code instructions to insert. 70796dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen unsigned Ins = 0; 70896dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen 70996dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen // Interference for the live-in value. 710eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen if (BI.LiveIn) { 7116c8afd728eb02742ce320ecd39bcf3774d8423b7Jakob Stoklund Olesen if (Intf.first() <= Indexes->getMBBStartIdx(BC.Number)) 712db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen BC.Entry = SpillPlacement::MustSpill, ++Ins; 713fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen else if (Intf.first() < BI.FirstInstr) 71496dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen BC.Entry = SpillPlacement::PrefSpill, ++Ins; 715fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen else if (Intf.first() < BI.LastInstr) 71696dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen ++Ins; 717a50c539b7a9e74597da34bfaea5429a48481f18bJakob Stoklund Olesen } 718b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 71996dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen // Interference for the live-out value. 720eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen if (BI.LiveOut) { 721612f7807c581eafb7c8105e1a55c8d839033bfb3Jakob Stoklund Olesen if (Intf.last() >= SA->getLastSplitPoint(BC.Number)) 722db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen BC.Exit = SpillPlacement::MustSpill, ++Ins; 723fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen else if (Intf.last() > BI.LastInstr) 72496dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen BC.Exit = SpillPlacement::PrefSpill, ++Ins; 725fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen else if (Intf.last() > BI.FirstInstr) 72696dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen ++Ins; 727b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen } 728b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 72996dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen // Accumulate the total frequency of inserted spill code. 73096dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen if (Ins) 73196dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen StaticCost += Ins * SpillPlacer->getBlockFrequency(BC.Number); 732b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen } 733f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen Cost = StaticCost; 734db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen 7351b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen // Add constraints for use-blocks. Note that these are the only constraints 7361b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen // that may add a positive bias, it is downhill from here. 7371b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen SpillPlacer->addConstraints(SplitConstraints); 738f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen return SpillPlacer->scanActiveBundles(); 739f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen} 740db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen 741db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen 742f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen/// addThroughConstraints - Add constraints and links to SpillPlacer from the 743f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen/// live-through blocks in Blocks. 744f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesenvoid RAGreedy::addThroughConstraints(InterferenceCache::Cursor Intf, 745f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen ArrayRef<unsigned> Blocks) { 7461b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen const unsigned GroupSize = 8; 7471b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen SpillPlacement::BlockConstraint BCS[GroupSize]; 748f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen unsigned TBS[GroupSize]; 749f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen unsigned B = 0, T = 0; 750db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen 751f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen for (unsigned i = 0; i != Blocks.size(); ++i) { 752f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen unsigned Number = Blocks[i]; 7531b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen Intf.moveToBlock(Number); 7541b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen 7557b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen if (!Intf.hasInterference()) { 756f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen assert(T < GroupSize && "Array overflow"); 757f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen TBS[T] = Number; 758f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen if (++T == GroupSize) { 75939b5abf507b43da6b92f68b86406e0015ead18e9Frits van Bommel SpillPlacer->addLinks(makeArrayRef(TBS, T)); 760f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen T = 0; 761f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen } 7627b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen continue; 7631b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen } 7641b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen 765f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen assert(B < GroupSize && "Array overflow"); 766f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen BCS[B].Number = Number; 767f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen 7687b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen // Interference for the live-in value. 7697b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen if (Intf.first() <= Indexes->getMBBStartIdx(Number)) 7707b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen BCS[B].Entry = SpillPlacement::MustSpill; 7717b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen else 7727b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen BCS[B].Entry = SpillPlacement::PrefSpill; 7737b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen 7747b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen // Interference for the live-out value. 7757b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen if (Intf.last() >= SA->getLastSplitPoint(Number)) 7767b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen BCS[B].Exit = SpillPlacement::MustSpill; 7777b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen else 7787b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen BCS[B].Exit = SpillPlacement::PrefSpill; 7797b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen 7801b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen if (++B == GroupSize) { 7811b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen ArrayRef<SpillPlacement::BlockConstraint> Array(BCS, B); 7821b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen SpillPlacer->addConstraints(Array); 7831b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen B = 0; 7841b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen } 785db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen } 786db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen 7871b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen ArrayRef<SpillPlacement::BlockConstraint> Array(BCS, B); 7881b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen SpillPlacer->addConstraints(Array); 78939b5abf507b43da6b92f68b86406e0015ead18e9Frits van Bommel SpillPlacer->addLinks(makeArrayRef(TBS, T)); 790b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen} 791b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 792c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesenvoid RAGreedy::growRegion(GlobalSplitCandidate &Cand) { 7935db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen // Keep track of through blocks that have not been added to SpillPlacer. 7945db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen BitVector Todo = SA->getThroughBlocks(); 7955db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen SmallVectorImpl<unsigned> &ActiveBlocks = Cand.ActiveBlocks; 7965db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen unsigned AddedTo = 0; 797f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen#ifndef NDEBUG 798f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen unsigned Visited = 0; 799f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen#endif 8005db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen 801f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen for (;;) { 802f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen ArrayRef<unsigned> NewBundles = SpillPlacer->getRecentPositive(); 803f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen // Find new through blocks in the periphery of PrefRegBundles. 804f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen for (int i = 0, e = NewBundles.size(); i != e; ++i) { 805f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen unsigned Bundle = NewBundles[i]; 806f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen // Look at all blocks connected to Bundle in the full graph. 807f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen ArrayRef<unsigned> Blocks = Bundles->getBlocks(Bundle); 808f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen for (ArrayRef<unsigned>::iterator I = Blocks.begin(), E = Blocks.end(); 809f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen I != E; ++I) { 810f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen unsigned Block = *I; 8115db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen if (!Todo.test(Block)) 812f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen continue; 8135db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen Todo.reset(Block); 814f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen // This is a new through block. Add it to SpillPlacer later. 8155db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen ActiveBlocks.push_back(Block); 816f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen#ifndef NDEBUG 817f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen ++Visited; 818f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen#endif 819f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen } 820f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen } 821f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen // Any new blocks to add? 822549019792a8b14500cab093ac8f3c5f7331e86d7Jakob Stoklund Olesen if (ActiveBlocks.size() == AddedTo) 823549019792a8b14500cab093ac8f3c5f7331e86d7Jakob Stoklund Olesen break; 824b4666364f4db4889883d7a6c02a177ebcde7c240Jakob Stoklund Olesen 825b4666364f4db4889883d7a6c02a177ebcde7c240Jakob Stoklund Olesen // Compute through constraints from the interference, or assume that all 826b4666364f4db4889883d7a6c02a177ebcde7c240Jakob Stoklund Olesen // through blocks prefer spilling when forming compact regions. 827b4666364f4db4889883d7a6c02a177ebcde7c240Jakob Stoklund Olesen ArrayRef<unsigned> NewBlocks = makeArrayRef(ActiveBlocks).slice(AddedTo); 828b4666364f4db4889883d7a6c02a177ebcde7c240Jakob Stoklund Olesen if (Cand.PhysReg) 829b4666364f4db4889883d7a6c02a177ebcde7c240Jakob Stoklund Olesen addThroughConstraints(Cand.Intf, NewBlocks); 830b4666364f4db4889883d7a6c02a177ebcde7c240Jakob Stoklund Olesen else 831b87f91b063a0ac853735f2af3bd94fb8551a11ffJakob Stoklund Olesen // Provide a strong negative bias on through blocks to prevent unwanted 832b87f91b063a0ac853735f2af3bd94fb8551a11ffJakob Stoklund Olesen // liveness on loop backedges. 833b87f91b063a0ac853735f2af3bd94fb8551a11ffJakob Stoklund Olesen SpillPlacer->addPrefSpill(NewBlocks, /* Strong= */ true); 834549019792a8b14500cab093ac8f3c5f7331e86d7Jakob Stoklund Olesen AddedTo = ActiveBlocks.size(); 835549019792a8b14500cab093ac8f3c5f7331e86d7Jakob Stoklund Olesen 836f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen // Perhaps iterating can enable more bundles? 837f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen SpillPlacer->iterate(); 838f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen } 839f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen DEBUG(dbgs() << ", v=" << Visited); 840f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen} 84196dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen 84287972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen/// calcCompactRegion - Compute the set of edge bundles that should be live 84387972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen/// when splitting the current live range into compact regions. Compact 84487972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen/// regions can be computed without looking at interference. They are the 84587972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen/// regions formed by removing all the live-through blocks from the live range. 84687972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen/// 84787972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen/// Returns false if the current live range is already compact, or if the 84887972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen/// compact regions would form single block regions anyway. 84987972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesenbool RAGreedy::calcCompactRegion(GlobalSplitCandidate &Cand) { 85087972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen // Without any through blocks, the live range is already compact. 85187972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen if (!SA->getNumThroughBlocks()) 85287972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen return false; 85387972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen 85487972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen // Compact regions don't correspond to any physreg. 85587972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen Cand.reset(IntfCache, 0); 85687972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen 85787972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen DEBUG(dbgs() << "Compact region bundles"); 85887972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen 85987972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen // Use the spill placer to determine the live bundles. GrowRegion pretends 86087972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen // that all the through blocks have interference when PhysReg is unset. 86187972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen SpillPlacer->prepare(Cand.LiveBundles); 86287972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen 86387972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen // The static split cost will be zero since Cand.Intf reports no interference. 86487972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen float Cost; 86587972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen if (!addSplitConstraints(Cand.Intf, Cost)) { 86687972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen DEBUG(dbgs() << ", none.\n"); 86787972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen return false; 86887972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen } 86987972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen 87087972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen growRegion(Cand); 87187972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen SpillPlacer->finish(); 87287972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen 87387972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen if (!Cand.LiveBundles.any()) { 87487972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen DEBUG(dbgs() << ", none.\n"); 87587972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen return false; 87687972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen } 87787972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen 87887972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen DEBUG({ 87987972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen for (int i = Cand.LiveBundles.find_first(); i>=0; 88087972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen i = Cand.LiveBundles.find_next(i)) 88187972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen dbgs() << " EB#" << i; 88287972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen dbgs() << ".\n"; 88387972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen }); 88487972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen return true; 88587972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen} 88687972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen 887200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen/// calcSpillCost - Compute how expensive it would be to split the live range in 888200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen/// SA around all use blocks instead of forming bundle regions. 889200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesenfloat RAGreedy::calcSpillCost() { 890200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen float Cost = 0; 891200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks(); 892200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen for (unsigned i = 0; i != UseBlocks.size(); ++i) { 893200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen const SplitAnalysis::BlockInfo &BI = UseBlocks[i]; 894200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen unsigned Number = BI.MBB->getNumber(); 895200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen // We normally only need one spill instruction - a load or a store. 896200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen Cost += SpillPlacer->getBlockFrequency(Number); 897200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen 898200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen // Unless the value is redefined in the block. 8993f5beede1bb97ba4e06dc300e00b70e1013e7216Jakob Stoklund Olesen if (BI.LiveIn && BI.LiveOut && BI.FirstDef) 9003f5beede1bb97ba4e06dc300e00b70e1013e7216Jakob Stoklund Olesen Cost += SpillPlacer->getBlockFrequency(Number); 901200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen } 902200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen return Cost; 903200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen} 904200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen 905b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen/// calcGlobalSplitCost - Return the global split cost of following the split 906b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen/// pattern in LiveBundles. This cost should be added to the local cost of the 90796dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen/// interference pattern in SplitConstraints. 908b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen/// 909c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesenfloat RAGreedy::calcGlobalSplitCost(GlobalSplitCandidate &Cand) { 910b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen float GlobalCost = 0; 9115db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen const BitVector &LiveBundles = Cand.LiveBundles; 912db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks(); 913db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen for (unsigned i = 0; i != UseBlocks.size(); ++i) { 914db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen const SplitAnalysis::BlockInfo &BI = UseBlocks[i]; 91596dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen SpillPlacement::BlockConstraint &BC = SplitConstraints[i]; 916874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen bool RegIn = LiveBundles[Bundles->getBundle(BC.Number, 0)]; 917874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen bool RegOut = LiveBundles[Bundles->getBundle(BC.Number, 1)]; 918874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen unsigned Ins = 0; 919874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen 920db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen if (BI.LiveIn) 921db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen Ins += RegIn != (BC.Entry == SpillPlacement::PrefReg); 922db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen if (BI.LiveOut) 923db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen Ins += RegOut != (BC.Exit == SpillPlacement::PrefReg); 924874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen if (Ins) 925874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen GlobalCost += Ins * SpillPlacer->getBlockFrequency(BC.Number); 926b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen } 927db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen 9285db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen for (unsigned i = 0, e = Cand.ActiveBlocks.size(); i != e; ++i) { 9295db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen unsigned Number = Cand.ActiveBlocks[i]; 930db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen bool RegIn = LiveBundles[Bundles->getBundle(Number, 0)]; 931db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen bool RegOut = LiveBundles[Bundles->getBundle(Number, 1)]; 9329a54352879e5aaac2e2c37490e5cb7844550db8bJakob Stoklund Olesen if (!RegIn && !RegOut) 9339a54352879e5aaac2e2c37490e5cb7844550db8bJakob Stoklund Olesen continue; 9349a54352879e5aaac2e2c37490e5cb7844550db8bJakob Stoklund Olesen if (RegIn && RegOut) { 9359a54352879e5aaac2e2c37490e5cb7844550db8bJakob Stoklund Olesen // We need double spill code if this block has interference. 936c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen Cand.Intf.moveToBlock(Number); 937c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen if (Cand.Intf.hasInterference()) 9389a54352879e5aaac2e2c37490e5cb7844550db8bJakob Stoklund Olesen GlobalCost += 2*SpillPlacer->getBlockFrequency(Number); 9399a54352879e5aaac2e2c37490e5cb7844550db8bJakob Stoklund Olesen continue; 9409a54352879e5aaac2e2c37490e5cb7844550db8bJakob Stoklund Olesen } 9419a54352879e5aaac2e2c37490e5cb7844550db8bJakob Stoklund Olesen // live-in / stack-out or stack-in live-out. 9429a54352879e5aaac2e2c37490e5cb7844550db8bJakob Stoklund Olesen GlobalCost += SpillPlacer->getBlockFrequency(Number); 943db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen } 944b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen return GlobalCost; 945b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen} 946b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 94700005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen/// splitAroundRegion - Split the current live range around the regions 94800005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen/// determined by BundleCand and GlobalCand. 949ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen/// 95000005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen/// Before calling this function, GlobalCand and BundleCand must be initialized 95100005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen/// so each bundle is assigned to a valid candidate, or NoCand for the 95200005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen/// stack-bound bundles. The shared SA/SE SplitAnalysis and SplitEditor 95300005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen/// objects must be initialized for the current live range, and intervals 95400005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen/// created for the used candidates. 955ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen/// 95600005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen/// @param LREdit The LiveRangeEdit object handling the current split. 95700005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen/// @param UsedCands List of used GlobalCand entries. Every BundleCand value 95800005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen/// must appear in this list. 95900005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesenvoid RAGreedy::splitAroundRegion(LiveRangeEdit &LREdit, 96000005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen ArrayRef<unsigned> UsedCands) { 96100005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // These are the intervals created for new global ranges. We may create more 96200005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // intervals for local ranges. 96300005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen const unsigned NumGlobalIntvs = LREdit.size(); 96400005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen DEBUG(dbgs() << "splitAroundRegion with " << NumGlobalIntvs << " globals.\n"); 96500005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen assert(NumGlobalIntvs && "No global intervals configured"); 966ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 9672d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen // Isolate even single instructions when dealing with a proper sub-class. 96869145baf36219b07a49d8ce14b4a04870e72a123Jakob Stoklund Olesen // That guarantees register class inflation for the stack interval because it 9692d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen // is all copies. 9702d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen unsigned Reg = SA->getParent().reg; 9712d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen bool SingleInstrs = RegClassInfo.isProperSubClass(MRI->getRegClass(Reg)); 9722d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen 97387360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen // First handle all the blocks with uses. 974db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks(); 975db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen for (unsigned i = 0; i != UseBlocks.size(); ++i) { 976db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen const SplitAnalysis::BlockInfo &BI = UseBlocks[i]; 97700005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen unsigned Number = BI.MBB->getNumber(); 97800005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen unsigned IntvIn = 0, IntvOut = 0; 97900005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen SlotIndex IntfIn, IntfOut; 98000005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen if (BI.LiveIn) { 98100005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen unsigned CandIn = BundleCand[Bundles->getBundle(Number, 0)]; 98200005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen if (CandIn != NoCand) { 98300005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen GlobalSplitCandidate &Cand = GlobalCand[CandIn]; 98400005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen IntvIn = Cand.IntvIdx; 98500005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen Cand.Intf.moveToBlock(Number); 98600005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen IntfIn = Cand.Intf.first(); 98700005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen } 98800005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen } 98900005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen if (BI.LiveOut) { 99000005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen unsigned CandOut = BundleCand[Bundles->getBundle(Number, 1)]; 99100005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen if (CandOut != NoCand) { 99200005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen GlobalSplitCandidate &Cand = GlobalCand[CandOut]; 99300005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen IntvOut = Cand.IntvIdx; 99400005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen Cand.Intf.moveToBlock(Number); 99500005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen IntfOut = Cand.Intf.last(); 99600005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen } 99700005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen } 998ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 999fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen // Create separate intervals for isolated blocks with multiple uses. 100000005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen if (!IntvIn && !IntvOut) { 1001fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " isolated.\n"); 10022d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen if (SA->shouldSplitSingleBlock(BI, SingleInstrs)) 100387360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen SE->splitSingleBlock(BI); 1004fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen continue; 1005fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen } 1006fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen 100700005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen if (IntvIn && IntvOut) 100800005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen SE->splitLiveThroughBlock(Number, IntvIn, IntfIn, IntvOut, IntfOut); 100900005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen else if (IntvIn) 101000005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen SE->splitRegInBlock(BI, IntvIn, IntfIn); 1011b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen else 101200005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen SE->splitRegOutBlock(BI, IntvOut, IntfOut); 1013ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen } 1014ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 101500005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // Handle live-through blocks. The relevant live-through blocks are stored in 101600005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // the ActiveBlocks list with each candidate. We need to filter out 101700005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // duplicates. 101800005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen BitVector Todo = SA->getThroughBlocks(); 101900005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen for (unsigned c = 0; c != UsedCands.size(); ++c) { 102000005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen ArrayRef<unsigned> Blocks = GlobalCand[UsedCands[c]].ActiveBlocks; 102100005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen for (unsigned i = 0, e = Blocks.size(); i != e; ++i) { 102200005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen unsigned Number = Blocks[i]; 102300005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen if (!Todo.test(Number)) 102400005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen continue; 102500005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen Todo.reset(Number); 102600005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen 102700005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen unsigned IntvIn = 0, IntvOut = 0; 102800005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen SlotIndex IntfIn, IntfOut; 102900005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen 103000005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen unsigned CandIn = BundleCand[Bundles->getBundle(Number, 0)]; 103100005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen if (CandIn != NoCand) { 103200005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen GlobalSplitCandidate &Cand = GlobalCand[CandIn]; 103300005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen IntvIn = Cand.IntvIdx; 103400005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen Cand.Intf.moveToBlock(Number); 103500005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen IntfIn = Cand.Intf.first(); 103600005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen } 103700005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen 103800005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen unsigned CandOut = BundleCand[Bundles->getBundle(Number, 1)]; 103900005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen if (CandOut != NoCand) { 104000005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen GlobalSplitCandidate &Cand = GlobalCand[CandOut]; 104100005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen IntvOut = Cand.IntvIdx; 104200005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen Cand.Intf.moveToBlock(Number); 104300005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen IntfOut = Cand.Intf.last(); 104400005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen } 104500005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen if (!IntvIn && !IntvOut) 104600005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen continue; 104700005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen SE->splitLiveThroughBlock(Number, IntvIn, IntfIn, IntvOut, IntfOut); 104800005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen } 1049db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen } 1050db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen 10510db841f9c2b9a25fb5ecb36e350d3a802c35654cJakob Stoklund Olesen ++NumGlobalSplits; 1052ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 10535928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen SmallVector<unsigned, 8> IntvMap; 10545928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen SE->finish(&IntvMap); 10551f8804263ffc5e6843d81f5c7bd9c739aa90fde5Jakob Stoklund Olesen DebugVars->splitRegister(Reg, LREdit.regs()); 1056f42b66169d75301346e3685fd2b3e45e47806367Jakob Stoklund Olesen 10571a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen ExtraRegInfo.resize(MRI->getNumVirtRegs()); 1058b2abfa0bf30edf292a27a06e091d03983e644c9bJakob Stoklund Olesen unsigned OrigBlocks = SA->getNumLiveBlocks(); 10595928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen 10605928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen // Sort out the new intervals created by splitting. We get four kinds: 10615928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen // - Remainder intervals should not be split again. 10625928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen // - Candidate intervals can be assigned to Cand.PhysReg. 10635928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen // - Block-local splits are candidates for local splitting. 10645928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen // - DCE leftovers should go back on the queue. 10655928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen for (unsigned i = 0, e = LREdit.size(); i != e; ++i) { 10661a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen LiveInterval &Reg = *LREdit.get(i); 10675928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen 10685928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen // Ignore old intervals from DCE. 10691a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen if (getStage(Reg) != RS_New) 10705928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen continue; 10715928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen 10725928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen // Remainder interval. Don't try splitting again, spill if it doesn't 10735928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen // allocate. 10745928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen if (IntvMap[i] == 0) { 1075fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen setStage(Reg, RS_Spill); 10765928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen continue; 10775928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen } 10785928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen 107900005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // Global intervals. Allow repeated splitting as long as the number of live 108000005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // blocks is strictly decreasing. 108100005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen if (IntvMap[i] < NumGlobalIntvs) { 10821a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen if (SA->countLiveBlocks(&Reg) >= OrigBlocks) { 10839f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen DEBUG(dbgs() << "Main interval covers the same " << OrigBlocks 10849f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen << " blocks as original.\n"); 10859f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen // Don't allow repeated splitting as a safe guard against looping. 108649743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen setStage(Reg, RS_Split2); 10879f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen } 10889f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen continue; 10899f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen } 10909f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen 10919f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen // Other intervals are treated as new. This includes local intervals created 10929f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen // for blocks with multiple uses, and anything created by DCE. 10935928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen } 10945928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen 1095eb29157d80847c207b77910bcd40a6a6c91ca5c5Jakob Stoklund Olesen if (VerifyEnabled) 1096ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen MF->verify(this, "After splitting live range around region"); 1097ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen} 1098ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 1099b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesenunsigned RAGreedy::tryRegionSplit(LiveInterval &VirtReg, AllocationOrder &Order, 1100b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen SmallVectorImpl<LiveInterval*> &NewVRegs) { 1101c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen unsigned NumCands = 0; 110200005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen unsigned BestCand = NoCand; 110300005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen float BestCost; 110400005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen SmallVector<unsigned, 8> UsedCands; 110500005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen 110600005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // Check if we can split this live range around a compact region. 1107a16a25ddeaf495b78b04e2a19feeac00d9824e63Jakob Stoklund Olesen bool HasCompact = calcCompactRegion(GlobalCand.front()); 110800005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen if (HasCompact) { 110900005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // Yes, keep GlobalCand[0] as the compact region candidate. 111000005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen NumCands = 1; 111100005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen BestCost = HUGE_VALF; 111200005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen } else { 111300005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // No benefit from the compact region, our fallback will be per-block 111400005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // splitting. Make sure we find a solution that is cheaper than spilling. 111500005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen BestCost = Hysteresis * calcSpillCost(); 111600005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen DEBUG(dbgs() << "Cost of isolating all blocks = " << BestCost << '\n'); 111700005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen } 111896dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen 1119b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen Order.rewind(); 1120c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen while (unsigned PhysReg = Order.next()) { 1121f1c709837bd11c5383fce3b8a026a7c8eaabba86Jakob Stoklund Olesen // Discard bad candidates before we run out of interference cache cursors. 1122f1c709837bd11c5383fce3b8a026a7c8eaabba86Jakob Stoklund Olesen // This will only affect register classes with a lot of registers (>32). 1123f1c709837bd11c5383fce3b8a026a7c8eaabba86Jakob Stoklund Olesen if (NumCands == IntfCache.getMaxCursors()) { 1124f1c709837bd11c5383fce3b8a026a7c8eaabba86Jakob Stoklund Olesen unsigned WorstCount = ~0u; 1125f1c709837bd11c5383fce3b8a026a7c8eaabba86Jakob Stoklund Olesen unsigned Worst = 0; 1126f1c709837bd11c5383fce3b8a026a7c8eaabba86Jakob Stoklund Olesen for (unsigned i = 0; i != NumCands; ++i) { 112700005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen if (i == BestCand || !GlobalCand[i].PhysReg) 1128f1c709837bd11c5383fce3b8a026a7c8eaabba86Jakob Stoklund Olesen continue; 1129f1c709837bd11c5383fce3b8a026a7c8eaabba86Jakob Stoklund Olesen unsigned Count = GlobalCand[i].LiveBundles.count(); 1130f1c709837bd11c5383fce3b8a026a7c8eaabba86Jakob Stoklund Olesen if (Count < WorstCount) 1131f1c709837bd11c5383fce3b8a026a7c8eaabba86Jakob Stoklund Olesen Worst = i, WorstCount = Count; 1132f1c709837bd11c5383fce3b8a026a7c8eaabba86Jakob Stoklund Olesen } 1133f1c709837bd11c5383fce3b8a026a7c8eaabba86Jakob Stoklund Olesen --NumCands; 1134f1c709837bd11c5383fce3b8a026a7c8eaabba86Jakob Stoklund Olesen GlobalCand[Worst] = GlobalCand[NumCands]; 11357bdf0060a00f04ad03d3c6f294d8db6f4951dbc2Jakob Stoklund Olesen if (BestCand == NumCands) 11367bdf0060a00f04ad03d3c6f294d8db6f4951dbc2Jakob Stoklund Olesen BestCand = Worst; 1137f1c709837bd11c5383fce3b8a026a7c8eaabba86Jakob Stoklund Olesen } 1138f1c709837bd11c5383fce3b8a026a7c8eaabba86Jakob Stoklund Olesen 1139c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen if (GlobalCand.size() <= NumCands) 1140c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen GlobalCand.resize(NumCands+1); 1141c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen GlobalSplitCandidate &Cand = GlobalCand[NumCands]; 1142c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen Cand.reset(IntfCache, PhysReg); 114396dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen 1144c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen SpillPlacer->prepare(Cand.LiveBundles); 11451b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen float Cost; 1146c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen if (!addSplitConstraints(Cand.Intf, Cost)) { 1147f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen DEBUG(dbgs() << PrintReg(PhysReg, TRI) << "\tno positive bundles\n"); 11481b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen continue; 11491b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen } 1150f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen DEBUG(dbgs() << PrintReg(PhysReg, TRI) << "\tstatic = " << Cost); 1151200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen if (Cost >= BestCost) { 1152200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen DEBUG({ 1153200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen if (BestCand == NoCand) 1154200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen dbgs() << " worse than no bundles\n"; 1155200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen else 1156200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen dbgs() << " worse than " 1157200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen << PrintReg(GlobalCand[BestCand].PhysReg, TRI) << '\n'; 1158200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen }); 1159b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen continue; 1160874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen } 1161c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen growRegion(Cand); 1162ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 11639efa2a263ea470caacef1c85f6ca45e32bf516d3Jakob Stoklund Olesen SpillPlacer->finish(); 11649efa2a263ea470caacef1c85f6ca45e32bf516d3Jakob Stoklund Olesen 1165ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // No live bundles, defer to splitSingleBlocks(). 1166c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen if (!Cand.LiveBundles.any()) { 1167874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen DEBUG(dbgs() << " no bundles.\n"); 1168ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen continue; 1169874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen } 1170ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 1171c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen Cost += calcGlobalSplitCost(Cand); 1172874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen DEBUG({ 1173874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen dbgs() << ", total = " << Cost << " with bundles"; 1174c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen for (int i = Cand.LiveBundles.find_first(); i>=0; 1175c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen i = Cand.LiveBundles.find_next(i)) 1176874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen dbgs() << " EB#" << i; 1177874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen dbgs() << ".\n"; 1178874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen }); 1179200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen if (Cost < BestCost) { 1180c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen BestCand = NumCands; 1181200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen BestCost = Hysteresis * Cost; // Prevent rounding effects. 1182b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen } 1183c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen ++NumCands; 1184b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen } 1185ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 118600005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // No solutions found, fall back to single block splitting. 118700005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen if (!HasCompact && BestCand == NoCand) 1188ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen return 0; 1189ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 119000005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // Prepare split editor. 119120942dcd8634ad75091fe89669868cfebf74e869Jakob Stoklund Olesen LiveRangeEdit LREdit(&VirtReg, NewVRegs, *MF, *LIS, VRM, this); 1192708d06f7fb5dfd9c8559aea07b042a88c65645f8Jakob Stoklund Olesen SE->reset(LREdit, SplitSpillMode); 119300005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen 119400005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // Assign all edge bundles to the preferred candidate, or NoCand. 119500005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen BundleCand.assign(Bundles->getNumBundles(), NoCand); 119600005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen 119700005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // Assign bundles for the best candidate region. 119800005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen if (BestCand != NoCand) { 119900005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen GlobalSplitCandidate &Cand = GlobalCand[BestCand]; 120000005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen if (unsigned B = Cand.getBundles(BundleCand, BestCand)) { 120100005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen UsedCands.push_back(BestCand); 120200005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen Cand.IntvIdx = SE->openIntv(); 120300005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen DEBUG(dbgs() << "Split for " << PrintReg(Cand.PhysReg, TRI) << " in " 120400005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen << B << " bundles, intv " << Cand.IntvIdx << ".\n"); 120532668ea7a290ee1cb6bfe8cd677cdd4e5df05b4dChandler Carruth (void)B; 120600005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen } 120700005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen } 120800005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen 120900005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // Assign bundles for the compact region. 121000005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen if (HasCompact) { 121100005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen GlobalSplitCandidate &Cand = GlobalCand.front(); 121200005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen assert(!Cand.PhysReg && "Compact region has no physreg"); 121300005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen if (unsigned B = Cand.getBundles(BundleCand, 0)) { 121400005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen UsedCands.push_back(0); 121500005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen Cand.IntvIdx = SE->openIntv(); 121600005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen DEBUG(dbgs() << "Split for compact region in " << B << " bundles, intv " 121700005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen << Cand.IntvIdx << ".\n"); 121832668ea7a290ee1cb6bfe8cd677cdd4e5df05b4dChandler Carruth (void)B; 121900005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen } 122000005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen } 122100005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen 122200005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen splitAroundRegion(LREdit, UsedCands); 1223b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen return 0; 1224b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen} 1225b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 1226ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 1227ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen//===----------------------------------------------------------------------===// 1228dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen// Per-Block Splitting 1229dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen//===----------------------------------------------------------------------===// 1230dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen 1231dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen/// tryBlockSplit - Split a global live range around every block with uses. This 1232dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen/// creates a lot of local live ranges, that will be split by tryLocalSplit if 1233dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen/// they don't allocate. 1234dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesenunsigned RAGreedy::tryBlockSplit(LiveInterval &VirtReg, AllocationOrder &Order, 1235dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen SmallVectorImpl<LiveInterval*> &NewVRegs) { 1236dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen assert(&SA->getParent() == &VirtReg && "Live range wasn't analyzed"); 1237dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen unsigned Reg = VirtReg.reg; 1238dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen bool SingleInstrs = RegClassInfo.isProperSubClass(MRI->getRegClass(Reg)); 123920942dcd8634ad75091fe89669868cfebf74e869Jakob Stoklund Olesen LiveRangeEdit LREdit(&VirtReg, NewVRegs, *MF, *LIS, VRM, this); 1240708d06f7fb5dfd9c8559aea07b042a88c65645f8Jakob Stoklund Olesen SE->reset(LREdit, SplitSpillMode); 1241dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks(); 1242dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen for (unsigned i = 0; i != UseBlocks.size(); ++i) { 1243dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen const SplitAnalysis::BlockInfo &BI = UseBlocks[i]; 1244dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen if (SA->shouldSplitSingleBlock(BI, SingleInstrs)) 1245dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen SE->splitSingleBlock(BI); 1246dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen } 1247dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen // No blocks were split. 1248dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen if (LREdit.empty()) 1249dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen return 0; 1250dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen 1251dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen // We did split for some blocks. 1252a9c41d39d1adc92107e095aca6f851aed71b6a5fJakob Stoklund Olesen SmallVector<unsigned, 8> IntvMap; 1253a9c41d39d1adc92107e095aca6f851aed71b6a5fJakob Stoklund Olesen SE->finish(&IntvMap); 12541f8804263ffc5e6843d81f5c7bd9c739aa90fde5Jakob Stoklund Olesen 12551f8804263ffc5e6843d81f5c7bd9c739aa90fde5Jakob Stoklund Olesen // Tell LiveDebugVariables about the new ranges. 12561f8804263ffc5e6843d81f5c7bd9c739aa90fde5Jakob Stoklund Olesen DebugVars->splitRegister(Reg, LREdit.regs()); 12571f8804263ffc5e6843d81f5c7bd9c739aa90fde5Jakob Stoklund Olesen 1258a9c41d39d1adc92107e095aca6f851aed71b6a5fJakob Stoklund Olesen ExtraRegInfo.resize(MRI->getNumVirtRegs()); 1259a9c41d39d1adc92107e095aca6f851aed71b6a5fJakob Stoklund Olesen 1260a9c41d39d1adc92107e095aca6f851aed71b6a5fJakob Stoklund Olesen // Sort out the new intervals created by splitting. The remainder interval 1261a9c41d39d1adc92107e095aca6f851aed71b6a5fJakob Stoklund Olesen // goes straight to spilling, the new local ranges get to stay RS_New. 1262a9c41d39d1adc92107e095aca6f851aed71b6a5fJakob Stoklund Olesen for (unsigned i = 0, e = LREdit.size(); i != e; ++i) { 1263a9c41d39d1adc92107e095aca6f851aed71b6a5fJakob Stoklund Olesen LiveInterval &LI = *LREdit.get(i); 1264a9c41d39d1adc92107e095aca6f851aed71b6a5fJakob Stoklund Olesen if (getStage(LI) == RS_New && IntvMap[i] == 0) 1265a9c41d39d1adc92107e095aca6f851aed71b6a5fJakob Stoklund Olesen setStage(LI, RS_Spill); 1266a9c41d39d1adc92107e095aca6f851aed71b6a5fJakob Stoklund Olesen } 1267a9c41d39d1adc92107e095aca6f851aed71b6a5fJakob Stoklund Olesen 1268dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen if (VerifyEnabled) 1269dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen MF->verify(this, "After splitting live range around basic blocks"); 1270dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen return 0; 1271dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen} 1272dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen 1273d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen 1274d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 1275d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen// Per-Instruction Splitting 1276d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 1277d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen 1278d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen/// tryInstructionSplit - Split a live range around individual instructions. 1279d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen/// This is normally not worthwhile since the spiller is doing essentially the 1280d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen/// same thing. However, when the live range is in a constrained register 1281d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen/// class, it may help to insert copies such that parts of the live range can 1282d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen/// be moved to a larger register class. 1283d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen/// 1284d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen/// This is similar to spilling to a larger register class. 1285d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesenunsigned 1286d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund OlesenRAGreedy::tryInstructionSplit(LiveInterval &VirtReg, AllocationOrder &Order, 1287d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen SmallVectorImpl<LiveInterval*> &NewVRegs) { 1288d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen // There is no point to this if there are no larger sub-classes. 1289d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen if (!RegClassInfo.isProperSubClass(MRI->getRegClass(VirtReg.reg))) 1290d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen return 0; 1291d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen 1292d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen // Always enable split spill mode, since we're effectively spilling to a 1293d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen // register. 1294d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen LiveRangeEdit LREdit(&VirtReg, NewVRegs, *MF, *LIS, VRM, this); 1295d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen SE->reset(LREdit, SplitEditor::SM_Size); 1296d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen 1297d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen ArrayRef<SlotIndex> Uses = SA->getUseSlots(); 1298d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen if (Uses.size() <= 1) 1299d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen return 0; 1300d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen 1301d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen DEBUG(dbgs() << "Split around " << Uses.size() << " individual instrs.\n"); 1302d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen 1303d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen // Split around every non-copy instruction. 1304d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen for (unsigned i = 0; i != Uses.size(); ++i) { 1305d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen if (const MachineInstr *MI = Indexes->getInstructionFromIndex(Uses[i])) 1306d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen if (MI->isFullCopy()) { 1307d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen DEBUG(dbgs() << " skip:\t" << Uses[i] << '\t' << *MI); 1308d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen continue; 1309d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen } 1310d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen SE->openIntv(); 1311d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen SlotIndex SegStart = SE->enterIntvBefore(Uses[i]); 1312d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen SlotIndex SegStop = SE->leaveIntvAfter(Uses[i]); 1313d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen SE->useIntv(SegStart, SegStop); 1314d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen } 1315d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen 1316d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen if (LREdit.empty()) { 1317d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen DEBUG(dbgs() << "All uses were copies.\n"); 1318d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen return 0; 1319d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen } 1320d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen 1321d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen SmallVector<unsigned, 8> IntvMap; 1322d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen SE->finish(&IntvMap); 1323d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen DebugVars->splitRegister(VirtReg.reg, LREdit.regs()); 1324d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen ExtraRegInfo.resize(MRI->getNumVirtRegs()); 1325d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen 1326d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen // Assign all new registers to RS_Spill. This was the last chance. 1327d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen setStage(LREdit.begin(), LREdit.end(), RS_Spill); 1328d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen return 0; 1329d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen} 1330d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen 1331d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen 1332dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen//===----------------------------------------------------------------------===// 1333034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen// Local Splitting 1334034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 1335034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1336034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1337034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// calcGapWeights - Compute the maximum spill weight that needs to be evicted 1338034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// in order to use PhysReg between two entries in SA->UseSlots. 1339034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// 1340034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// GapWeight[i] represents the gap between UseSlots[i] and UseSlots[i+1]. 1341034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// 1342034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesenvoid RAGreedy::calcGapWeights(unsigned PhysReg, 1343034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen SmallVectorImpl<float> &GapWeight) { 1344db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen assert(SA->getUseBlocks().size() == 1 && "Not a local interval"); 1345db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen const SplitAnalysis::BlockInfo &BI = SA->getUseBlocks().front(); 1346b20b518f800293ea6b2bed04134c71293ac52403Jakob Stoklund Olesen ArrayRef<SlotIndex> Uses = SA->getUseSlots(); 1347034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const unsigned NumGaps = Uses.size()-1; 1348034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1349034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Start and end points for the interference check. 1350fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen SlotIndex StartIdx = 1351fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen BI.LiveIn ? BI.FirstInstr.getBaseIndex() : BI.FirstInstr; 1352fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen SlotIndex StopIdx = 1353fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen BI.LiveOut ? BI.LastInstr.getBoundaryIndex() : BI.LastInstr; 1354034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1355034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen GapWeight.assign(NumGaps, 0.0f); 1356034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1357034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Add interference from each overlapping register. 1358042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) { 1359042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen if (!Matrix->query(const_cast<LiveInterval&>(SA->getParent()), *Units) 1360042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen .checkInterference()) 1361034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen continue; 1362034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1363fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen // We know that VirtReg is a continuous interval from FirstInstr to 1364fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen // LastInstr, so we don't need InterferenceQuery. 1365034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // 1366034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Interference that overlaps an instruction is counted in both gaps 1367034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // surrounding the instruction. The exception is interference before 1368034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // StartIdx and after StopIdx. 1369034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // 1370042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen LiveIntervalUnion::SegmentIter IntI = 1371042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen Matrix->getLiveUnions()[*Units] .find(StartIdx); 1372034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen for (unsigned Gap = 0; IntI.valid() && IntI.start() < StopIdx; ++IntI) { 1373034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Skip the gaps before IntI. 1374034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen while (Uses[Gap+1].getBoundaryIndex() < IntI.start()) 1375034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (++Gap == NumGaps) 1376034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen break; 1377034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (Gap == NumGaps) 1378034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen break; 1379034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1380034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Update the gaps covered by IntI. 1381034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const float weight = IntI.value()->weight; 1382034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen for (; Gap != NumGaps; ++Gap) { 1383034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen GapWeight[Gap] = std::max(GapWeight[Gap], weight); 1384034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (Uses[Gap+1].getBaseIndex() >= IntI.stop()) 1385034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen break; 1386034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1387034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (Gap == NumGaps) 1388034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen break; 1389034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1390034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1391042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen 1392042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen // Add fixed interference. 1393042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) { 1394042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen const LiveInterval &LI = LIS->getRegUnit(*Units); 1395042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen LiveInterval::const_iterator I = LI.find(StartIdx); 1396042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen LiveInterval::const_iterator E = LI.end(); 1397042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen 1398042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen // Same loop as above. Mark any overlapped gaps as HUGE_VALF. 1399042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen for (unsigned Gap = 0; I != E && I->start < StopIdx; ++I) { 1400042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen while (Uses[Gap+1].getBoundaryIndex() < I->start) 1401042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen if (++Gap == NumGaps) 1402042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen break; 1403042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen if (Gap == NumGaps) 1404042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen break; 1405042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen 1406042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen for (; Gap != NumGaps; ++Gap) { 1407042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen GapWeight[Gap] = HUGE_VALF; 1408042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen if (Uses[Gap+1].getBaseIndex() >= I->end) 1409042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen break; 1410042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen } 1411042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen if (Gap == NumGaps) 1412042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen break; 1413042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen } 1414042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen } 1415034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen} 1416034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1417034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// tryLocalSplit - Try to split VirtReg into smaller intervals inside its only 1418034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// basic block. 1419034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// 1420034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesenunsigned RAGreedy::tryLocalSplit(LiveInterval &VirtReg, AllocationOrder &Order, 1421034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen SmallVectorImpl<LiveInterval*> &NewVRegs) { 1422db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen assert(SA->getUseBlocks().size() == 1 && "Not a local interval"); 1423db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen const SplitAnalysis::BlockInfo &BI = SA->getUseBlocks().front(); 1424034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1425034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Note that it is possible to have an interval that is live-in or live-out 1426034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // while only covering a single block - A phi-def can use undef values from 1427034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // predecessors, and the block could be a single-block loop. 1428034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // We don't bother doing anything clever about such a case, we simply assume 1429fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen // that the interval is continuous from FirstInstr to LastInstr. We should 1430fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen // make sure that we don't do anything illegal to such an interval, though. 1431034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1432b20b518f800293ea6b2bed04134c71293ac52403Jakob Stoklund Olesen ArrayRef<SlotIndex> Uses = SA->getUseSlots(); 1433034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (Uses.size() <= 2) 1434034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen return 0; 1435034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const unsigned NumGaps = Uses.size()-1; 1436034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1437034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen DEBUG({ 1438034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen dbgs() << "tryLocalSplit: "; 1439034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen for (unsigned i = 0, e = Uses.size(); i != e; ++i) 1440b20b518f800293ea6b2bed04134c71293ac52403Jakob Stoklund Olesen dbgs() << ' ' << Uses[i]; 1441034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen dbgs() << '\n'; 1442034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen }); 1443034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1444a6d513f47467b90344a74624d4fb77673942e3ceJakob Stoklund Olesen // If VirtReg is live across any register mask operands, compute a list of 1445a6d513f47467b90344a74624d4fb77673942e3ceJakob Stoklund Olesen // gaps with register masks. 1446a6d513f47467b90344a74624d4fb77673942e3ceJakob Stoklund Olesen SmallVector<unsigned, 8> RegMaskGaps; 1447042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen if (Matrix->checkRegMaskInterference(VirtReg)) { 1448a6d513f47467b90344a74624d4fb77673942e3ceJakob Stoklund Olesen // Get regmask slots for the whole block. 1449a6d513f47467b90344a74624d4fb77673942e3ceJakob Stoklund Olesen ArrayRef<SlotIndex> RMS = LIS->getRegMaskSlotsInBlock(BI.MBB->getNumber()); 1450cac5fa39bd861861018bb2c3f0b36cc71c2caa38Jakob Stoklund Olesen DEBUG(dbgs() << RMS.size() << " regmasks in block:"); 1451a6d513f47467b90344a74624d4fb77673942e3ceJakob Stoklund Olesen // Constrain to VirtReg's live range. 1452cac5fa39bd861861018bb2c3f0b36cc71c2caa38Jakob Stoklund Olesen unsigned ri = std::lower_bound(RMS.begin(), RMS.end(), 1453cac5fa39bd861861018bb2c3f0b36cc71c2caa38Jakob Stoklund Olesen Uses.front().getRegSlot()) - RMS.begin(); 1454a6d513f47467b90344a74624d4fb77673942e3ceJakob Stoklund Olesen unsigned re = RMS.size(); 1455a6d513f47467b90344a74624d4fb77673942e3ceJakob Stoklund Olesen for (unsigned i = 0; i != NumGaps && ri != re; ++i) { 1456cac5fa39bd861861018bb2c3f0b36cc71c2caa38Jakob Stoklund Olesen // Look for Uses[i] <= RMS <= Uses[i+1]. 1457cac5fa39bd861861018bb2c3f0b36cc71c2caa38Jakob Stoklund Olesen assert(!SlotIndex::isEarlierInstr(RMS[ri], Uses[i])); 1458cac5fa39bd861861018bb2c3f0b36cc71c2caa38Jakob Stoklund Olesen if (SlotIndex::isEarlierInstr(Uses[i+1], RMS[ri])) 1459a6d513f47467b90344a74624d4fb77673942e3ceJakob Stoklund Olesen continue; 1460cac5fa39bd861861018bb2c3f0b36cc71c2caa38Jakob Stoklund Olesen // Skip a regmask on the same instruction as the last use. It doesn't 1461cac5fa39bd861861018bb2c3f0b36cc71c2caa38Jakob Stoklund Olesen // overlap the live range. 1462cac5fa39bd861861018bb2c3f0b36cc71c2caa38Jakob Stoklund Olesen if (SlotIndex::isSameInstr(Uses[i+1], RMS[ri]) && i+1 == NumGaps) 1463cac5fa39bd861861018bb2c3f0b36cc71c2caa38Jakob Stoklund Olesen break; 1464cac5fa39bd861861018bb2c3f0b36cc71c2caa38Jakob Stoklund Olesen DEBUG(dbgs() << ' ' << RMS[ri] << ':' << Uses[i] << '-' << Uses[i+1]); 1465a6d513f47467b90344a74624d4fb77673942e3ceJakob Stoklund Olesen RegMaskGaps.push_back(i); 1466cac5fa39bd861861018bb2c3f0b36cc71c2caa38Jakob Stoklund Olesen // Advance ri to the next gap. A regmask on one of the uses counts in 1467cac5fa39bd861861018bb2c3f0b36cc71c2caa38Jakob Stoklund Olesen // both gaps. 1468cac5fa39bd861861018bb2c3f0b36cc71c2caa38Jakob Stoklund Olesen while (ri != re && SlotIndex::isEarlierInstr(RMS[ri], Uses[i+1])) 1469cac5fa39bd861861018bb2c3f0b36cc71c2caa38Jakob Stoklund Olesen ++ri; 1470a6d513f47467b90344a74624d4fb77673942e3ceJakob Stoklund Olesen } 1471cac5fa39bd861861018bb2c3f0b36cc71c2caa38Jakob Stoklund Olesen DEBUG(dbgs() << '\n'); 1472a6d513f47467b90344a74624d4fb77673942e3ceJakob Stoklund Olesen } 1473a6d513f47467b90344a74624d4fb77673942e3ceJakob Stoklund Olesen 1474b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // Since we allow local split results to be split again, there is a risk of 1475b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // creating infinite loops. It is tempting to require that the new live 1476b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // ranges have less instructions than the original. That would guarantee 1477b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // convergence, but it is too strict. A live range with 3 instructions can be 1478b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // split 2+3 (including the COPY), and we want to allow that. 1479b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // 1480b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // Instead we use these rules: 1481b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // 148249743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen // 1. Allow any split for ranges with getStage() < RS_Split2. (Except for the 1483b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // noop split, of course). 148449743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen // 2. Require progress be made for ranges with getStage() == RS_Split2. All 1485b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // the new ranges must have fewer instructions than before the split. 148649743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen // 3. New ranges with the same number of instructions are marked RS_Split2, 1487b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // smaller ranges are marked RS_New. 1488b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // 1489b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // These rules allow a 3 -> 2+3 split once, which we need. They also prevent 1490b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // excessive splitting and infinite loops. 1491b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // 149249743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen bool ProgressRequired = getStage(VirtReg) >= RS_Split2; 1493034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1494b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // Best split candidate. 1495034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen unsigned BestBefore = NumGaps; 1496034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen unsigned BestAfter = 0; 1497034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen float BestDiff = 0; 1498034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 149940a42a2ccaaa19a109667ed7abf224cc8733cd9cJakob Stoklund Olesen const float blockFreq = SpillPlacer->getBlockFrequency(BI.MBB->getNumber()); 1500034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen SmallVector<float, 8> GapWeight; 1501034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1502034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen Order.rewind(); 1503034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen while (unsigned PhysReg = Order.next()) { 1504034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Keep track of the largest spill weight that would need to be evicted in 1505034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // order to make use of PhysReg between UseSlots[i] and UseSlots[i+1]. 1506034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen calcGapWeights(PhysReg, GapWeight); 1507034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1508a6d513f47467b90344a74624d4fb77673942e3ceJakob Stoklund Olesen // Remove any gaps with regmask clobbers. 1509042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen if (Matrix->checkRegMaskInterference(VirtReg, PhysReg)) 1510a6d513f47467b90344a74624d4fb77673942e3ceJakob Stoklund Olesen for (unsigned i = 0, e = RegMaskGaps.size(); i != e; ++i) 1511a6d513f47467b90344a74624d4fb77673942e3ceJakob Stoklund Olesen GapWeight[RegMaskGaps[i]] = HUGE_VALF; 1512a6d513f47467b90344a74624d4fb77673942e3ceJakob Stoklund Olesen 1513034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Try to find the best sequence of gaps to close. 1514034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // The new spill weight must be larger than any gap interference. 1515034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1516034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // We will split before Uses[SplitBefore] and after Uses[SplitAfter]. 1517b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen unsigned SplitBefore = 0, SplitAfter = 1; 1518034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1519034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // MaxGap should always be max(GapWeight[SplitBefore..SplitAfter-1]). 1520034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // It is the spill weight that needs to be evicted. 1521034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen float MaxGap = GapWeight[0]; 1522034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1523034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen for (;;) { 1524034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Live before/after split? 1525034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const bool LiveBefore = SplitBefore != 0 || BI.LiveIn; 1526034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const bool LiveAfter = SplitAfter != NumGaps || BI.LiveOut; 1527034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1528034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen DEBUG(dbgs() << PrintReg(PhysReg, TRI) << ' ' 1529034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen << Uses[SplitBefore] << '-' << Uses[SplitAfter] 1530034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen << " i=" << MaxGap); 1531034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1532034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Stop before the interval gets so big we wouldn't be making progress. 1533034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (!LiveBefore && !LiveAfter) { 1534034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen DEBUG(dbgs() << " all\n"); 1535034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen break; 1536034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1537034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Should the interval be extended or shrunk? 1538034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen bool Shrink = true; 1539034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1540b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // How many gaps would the new range have? 1541b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen unsigned NewGaps = LiveBefore + SplitAfter - SplitBefore + LiveAfter; 1542b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen 1543b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // Legally, without causing looping? 1544b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen bool Legal = !ProgressRequired || NewGaps < NumGaps; 1545b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen 1546b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen if (Legal && MaxGap < HUGE_VALF) { 1547b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // Estimate the new spill weight. Each instruction reads or writes the 1548b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // register. Conservatively assume there are no read-modify-write 1549b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // instructions. 1550034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // 1551b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // Try to guess the size of the new interval. 1552b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen const float EstWeight = normalizeSpillWeight(blockFreq * (NewGaps + 1), 1553b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen Uses[SplitBefore].distance(Uses[SplitAfter]) + 1554b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen (LiveBefore + LiveAfter)*SlotIndex::InstrDist); 1555034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Would this split be possible to allocate? 1556034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Never allocate all gaps, we wouldn't be making progress. 155766446c803a11a26e4bb39b74091d146ac850ae4cJakob Stoklund Olesen DEBUG(dbgs() << " w=" << EstWeight); 155866446c803a11a26e4bb39b74091d146ac850ae4cJakob Stoklund Olesen if (EstWeight * Hysteresis >= MaxGap) { 1559034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen Shrink = false; 156066446c803a11a26e4bb39b74091d146ac850ae4cJakob Stoklund Olesen float Diff = EstWeight - MaxGap; 1561034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (Diff > BestDiff) { 1562034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen DEBUG(dbgs() << " (best)"); 156366446c803a11a26e4bb39b74091d146ac850ae4cJakob Stoklund Olesen BestDiff = Hysteresis * Diff; 1564034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen BestBefore = SplitBefore; 1565034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen BestAfter = SplitAfter; 1566034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1567034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1568034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1569034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1570034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Try to shrink. 1571034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (Shrink) { 1572b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen if (++SplitBefore < SplitAfter) { 1573034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen DEBUG(dbgs() << " shrink\n"); 1574034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Recompute the max when necessary. 1575034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (GapWeight[SplitBefore - 1] >= MaxGap) { 1576034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen MaxGap = GapWeight[SplitBefore]; 1577034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen for (unsigned i = SplitBefore + 1; i != SplitAfter; ++i) 1578034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen MaxGap = std::max(MaxGap, GapWeight[i]); 1579034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1580034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen continue; 1581034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1582034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen MaxGap = 0; 1583034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1584034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1585034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Try to extend the interval. 1586034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (SplitAfter >= NumGaps) { 1587034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen DEBUG(dbgs() << " end\n"); 1588034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen break; 1589034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1590034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1591034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen DEBUG(dbgs() << " extend\n"); 1592b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen MaxGap = std::max(MaxGap, GapWeight[SplitAfter++]); 1593034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1594034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1595034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1596034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Didn't find any candidates? 1597034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (BestBefore == NumGaps) 1598034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen return 0; 1599034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1600034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen DEBUG(dbgs() << "Best local split range: " << Uses[BestBefore] 1601034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen << '-' << Uses[BestAfter] << ", " << BestDiff 1602034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen << ", " << (BestAfter - BestBefore + 1) << " instrs\n"); 1603034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 160420942dcd8634ad75091fe89669868cfebf74e869Jakob Stoklund Olesen LiveRangeEdit LREdit(&VirtReg, NewVRegs, *MF, *LIS, VRM, this); 1605bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen SE->reset(LREdit); 1606bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen 1607bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen SE->openIntv(); 1608bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen SlotIndex SegStart = SE->enterIntvBefore(Uses[BestBefore]); 1609bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen SlotIndex SegStop = SE->leaveIntvAfter(Uses[BestAfter]); 1610bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen SE->useIntv(SegStart, SegStop); 1611b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen SmallVector<unsigned, 8> IntvMap; 1612b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen SE->finish(&IntvMap); 1613f42b66169d75301346e3685fd2b3e45e47806367Jakob Stoklund Olesen DebugVars->splitRegister(VirtReg.reg, LREdit.regs()); 1614b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen 1615b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // If the new range has the same number of instructions as before, mark it as 161649743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen // RS_Split2 so the next split will be forced to make progress. Otherwise, 1617b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // leave the new intervals as RS_New so they can compete. 1618b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen bool LiveBefore = BestBefore != 0 || BI.LiveIn; 1619b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen bool LiveAfter = BestAfter != NumGaps || BI.LiveOut; 1620b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen unsigned NewGaps = LiveBefore + BestAfter - BestBefore + LiveAfter; 1621b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen if (NewGaps >= NumGaps) { 1622b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen DEBUG(dbgs() << "Tagging non-progress ranges: "); 1623b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen assert(!ProgressRequired && "Didn't make progress when it was required."); 1624b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen for (unsigned i = 0, e = IntvMap.size(); i != e; ++i) 1625b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen if (IntvMap[i] == 1) { 162649743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen setStage(*LREdit.get(i), RS_Split2); 1627b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen DEBUG(dbgs() << PrintReg(LREdit.get(i)->reg)); 1628b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen } 1629b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen DEBUG(dbgs() << '\n'); 1630b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen } 16310db841f9c2b9a25fb5ecb36e350d3a802c35654cJakob Stoklund Olesen ++NumLocalSplits; 1632034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1633034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen return 0; 1634034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen} 1635034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1636034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 1637ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen// Live Range Splitting 1638ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen//===----------------------------------------------------------------------===// 1639ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 1640ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen/// trySplit - Try to split VirtReg or one of its interferences, making it 1641ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen/// assignable. 1642ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen/// @return Physreg when VirtReg may be assigned and/or new NewVRegs. 1643ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesenunsigned RAGreedy::trySplit(LiveInterval &VirtReg, AllocationOrder &Order, 1644ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen SmallVectorImpl<LiveInterval*>&NewVRegs) { 1645ccfa446450c9e3e0b3591343c4c5bea1e4cdc043Jakob Stoklund Olesen // Ranges must be Split2 or less. 1646ccfa446450c9e3e0b3591343c4c5bea1e4cdc043Jakob Stoklund Olesen if (getStage(VirtReg) >= RS_Spill) 1647ccfa446450c9e3e0b3591343c4c5bea1e4cdc043Jakob Stoklund Olesen return 0; 1648ccfa446450c9e3e0b3591343c4c5bea1e4cdc043Jakob Stoklund Olesen 1649034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Local intervals are handled separately. 1650a2ebf60ef2c434428af7f810b13327ab50245a67Jakob Stoklund Olesen if (LIS->intervalIsInOneMBB(VirtReg)) { 1651a2ebf60ef2c434428af7f810b13327ab50245a67Jakob Stoklund Olesen NamedRegionTimer T("Local Splitting", TimerGroupName, TimePassesIsEnabled); 165222a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen SA->analyze(&VirtReg); 1653d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen unsigned PhysReg = tryLocalSplit(VirtReg, Order, NewVRegs); 1654d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen if (PhysReg || !NewVRegs.empty()) 1655d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen return PhysReg; 1656d74d2847573df690b6a91254688ef3fd974f83f7Jakob Stoklund Olesen return tryInstructionSplit(VirtReg, Order, NewVRegs); 1657a2ebf60ef2c434428af7f810b13327ab50245a67Jakob Stoklund Olesen } 1658a2ebf60ef2c434428af7f810b13327ab50245a67Jakob Stoklund Olesen 1659a2ebf60ef2c434428af7f810b13327ab50245a67Jakob Stoklund Olesen NamedRegionTimer T("Global Splitting", TimerGroupName, TimePassesIsEnabled); 1660ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 166122a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen SA->analyze(&VirtReg); 166222a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen 16637d6b6a05b549da70b4473f015c97954c2a422724Jakob Stoklund Olesen // FIXME: SplitAnalysis may repair broken live ranges coming from the 16647d6b6a05b549da70b4473f015c97954c2a422724Jakob Stoklund Olesen // coalescer. That may cause the range to become allocatable which means that 16657d6b6a05b549da70b4473f015c97954c2a422724Jakob Stoklund Olesen // tryRegionSplit won't be making progress. This check should be replaced with 16667d6b6a05b549da70b4473f015c97954c2a422724Jakob Stoklund Olesen // an assertion when the coalescer is fixed. 16677d6b6a05b549da70b4473f015c97954c2a422724Jakob Stoklund Olesen if (SA->didRepairRange()) { 16687d6b6a05b549da70b4473f015c97954c2a422724Jakob Stoklund Olesen // VirtReg has changed, so all cached queries are invalid. 1669042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen Matrix->invalidateVirtRegs(); 16707d6b6a05b549da70b4473f015c97954c2a422724Jakob Stoklund Olesen if (unsigned PhysReg = tryAssign(VirtReg, Order, NewVRegs)) 16717d6b6a05b549da70b4473f015c97954c2a422724Jakob Stoklund Olesen return PhysReg; 16727d6b6a05b549da70b4473f015c97954c2a422724Jakob Stoklund Olesen } 16737d6b6a05b549da70b4473f015c97954c2a422724Jakob Stoklund Olesen 167449743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen // First try to split around a region spanning multiple blocks. RS_Split2 167549743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen // ranges already made dubious progress with region splitting, so they go 167649743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen // straight to single block splitting. 167749743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen if (getStage(VirtReg) < RS_Split2) { 167849743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen unsigned PhysReg = tryRegionSplit(VirtReg, Order, NewVRegs); 167949743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen if (PhysReg || !NewVRegs.empty()) 168049743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen return PhysReg; 168149743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen } 1682ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 1683dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen // Then isolate blocks. 1684dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen return tryBlockSplit(VirtReg, Order, NewVRegs); 1685ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen} 1686ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 1687ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 1688b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen//===----------------------------------------------------------------------===// 1689770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen// Main Entry Point 1690770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen//===----------------------------------------------------------------------===// 1691770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen 1692770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesenunsigned RAGreedy::selectOrSplit(LiveInterval &VirtReg, 1693ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen SmallVectorImpl<LiveInterval*> &NewVRegs) { 1694770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen // First try assigning a free register. 16955f2316a3b55f88dab2190212210770180a32aa95Jakob Stoklund Olesen AllocationOrder Order(VirtReg.reg, *VRM, RegClassInfo); 16966bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen if (unsigned PhysReg = tryAssign(VirtReg, Order, NewVRegs)) 16976bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen return PhysReg; 1698b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick 1699b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen LiveRangeStage Stage = getStage(VirtReg); 17001a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen DEBUG(dbgs() << StageName[Stage] 17011a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen << " Cascade " << ExtraRegInfo[VirtReg.reg].Cascade << '\n'); 1702b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen 170376395c9a31444fa86514473e0852cdd67752d0e8Jakob Stoklund Olesen // Try to evict a less worthy live range, but only for ranges from the primary 1704fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen // queue. The RS_Split ranges already failed to do this, and they should not 170576395c9a31444fa86514473e0852cdd67752d0e8Jakob Stoklund Olesen // get a second chance until they have been split. 1706fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen if (Stage != RS_Split) 170776395c9a31444fa86514473e0852cdd67752d0e8Jakob Stoklund Olesen if (unsigned PhysReg = tryEvict(VirtReg, Order, NewVRegs)) 170876395c9a31444fa86514473e0852cdd67752d0e8Jakob Stoklund Olesen return PhysReg; 1709b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick 1710ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen assert(NewVRegs.empty() && "Cannot append to existing NewVRegs"); 1711ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 1712107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen // The first time we see a live range, don't try to split or spill. 1713107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen // Wait until the second time, when all smaller ranges have been allocated. 1714107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen // This gives a better picture of the interference to split around. 1715fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen if (Stage < RS_Split) { 1716fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen setStage(VirtReg, RS_Split); 1717c1655e1a3c3a566b91b0513b56d61b58da1e36baJakob Stoklund Olesen DEBUG(dbgs() << "wait for second round\n"); 1718107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen NewVRegs.push_back(&VirtReg); 1719107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen return 0; 1720107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen } 1721107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen 1722bf4e10f2f69db24c107cb61d6fe10ed5b2047374Jakob Stoklund Olesen // If we couldn't allocate a register from spilling, there is probably some 1723bf4e10f2f69db24c107cb61d6fe10ed5b2047374Jakob Stoklund Olesen // invalid inline assembly. The base class wil report it. 1724fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen if (Stage >= RS_Done || !VirtReg.isSpillable()) 1725bf4e10f2f69db24c107cb61d6fe10ed5b2047374Jakob Stoklund Olesen return ~0u; 172622a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen 172746c83c80c5737743c955ff007fa6409804a7abf0Jakob Stoklund Olesen // Try splitting VirtReg or interferences. 1728ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen unsigned PhysReg = trySplit(VirtReg, Order, NewVRegs); 1729ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen if (PhysReg || !NewVRegs.empty()) 1730b64d92e29f38002e52a22fe36ea2d488968e3537Jakob Stoklund Olesen return PhysReg; 1731b64d92e29f38002e52a22fe36ea2d488968e3537Jakob Stoklund Olesen 1732770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen // Finally spill VirtReg itself. 1733770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen NamedRegionTimer T("Spiller", TimerGroupName, TimePassesIsEnabled); 173420942dcd8634ad75091fe89669868cfebf74e869Jakob Stoklund Olesen LiveRangeEdit LRE(&VirtReg, NewVRegs, *MF, *LIS, VRM, this); 173547dbf6cef761c25cfeb0aa7d624a6f98288bb96aJakob Stoklund Olesen spiller().spill(LRE); 1736fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen setStage(NewVRegs.begin(), NewVRegs.end(), RS_Done); 1737cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 1738c46570dc05851395829bef904bb6ddb1260400d1Jakob Stoklund Olesen if (VerifyEnabled) 1739c46570dc05851395829bef904bb6ddb1260400d1Jakob Stoklund Olesen MF->verify(this, "After spilling"); 1740c46570dc05851395829bef904bb6ddb1260400d1Jakob Stoklund Olesen 1741cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen // The live virtual register requesting allocation was spilled, so tell 1742cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen // the caller not to allocate anything during this round. 1743cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen return 0; 1744cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen} 1745cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 1746cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesenbool RAGreedy::runOnMachineFunction(MachineFunction &mf) { 1747cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen DEBUG(dbgs() << "********** GREEDY REGISTER ALLOCATION **********\n" 1748986d76d7b3844b9a2f3d01a48975952749267a93David Blaikie << "********** Function: " << mf.getName() << '\n'); 1749cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 1750cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen MF = &mf; 1751af24964251e27c2dd863239ba66ffd967b593be5Jakob Stoklund Olesen if (VerifyEnabled) 175289cab93fe999f6d81b4b99a71ac797b7ecfec277Jakob Stoklund Olesen MF->verify(this, "Before greedy register allocator"); 1753af24964251e27c2dd863239ba66ffd967b593be5Jakob Stoklund Olesen 1754d4348a2dc24c4fb012c1b9b20e71908f52049283Jakob Stoklund Olesen RegAllocBase::init(getAnalysis<VirtRegMap>(), 1755d4348a2dc24c4fb012c1b9b20e71908f52049283Jakob Stoklund Olesen getAnalysis<LiveIntervals>(), 1756d4348a2dc24c4fb012c1b9b20e71908f52049283Jakob Stoklund Olesen getAnalysis<LiveRegMatrix>()); 1757b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen Indexes = &getAnalysis<SlotIndexes>(); 1758f428eb6c1b09a2322b7a577b0bf2e49dd107bceaJakob Stoklund Olesen DomTree = &getAnalysis<MachineDominatorTree>(); 1759f6dff84d4e44d6c4a46c4f8a18e13c78f804547cJakob Stoklund Olesen SpillerInstance.reset(createInlineSpiller(*this, *MF, *VRM)); 1760d0bb5e2ca05d9c942223bf05e5940bb0c6cc9d3fJakob Stoklund Olesen Loops = &getAnalysis<MachineLoopInfo>(); 1761b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen Bundles = &getAnalysis<EdgeBundles>(); 1762b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen SpillPlacer = &getAnalysis<SpillPlacement>(); 1763f42b66169d75301346e3685fd2b3e45e47806367Jakob Stoklund Olesen DebugVars = &getAnalysis<LiveDebugVariables>(); 1764b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 17651b847deb26b52051de39f4cbecd224c9fbd0d1c2Jakob Stoklund Olesen SA.reset(new SplitAnalysis(*VRM, *LIS, *Loops)); 1766bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen SE.reset(new SplitEditor(*SA, *LIS, *VRM, *DomTree)); 17671a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen ExtraRegInfo.clear(); 17681a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen ExtraRegInfo.resize(MRI->getNumVirtRegs()); 17691a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen NextCascade = 1; 1770042888db2bb195c86bf34afbb6907d70855d2830Jakob Stoklund Olesen IntfCache.init(MF, Matrix->getLiveUnions(), Indexes, LIS, TRI); 177100005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen GlobalCand.resize(32); // This will grow as needed. 1772d0bb5e2ca05d9c942223bf05e5940bb0c6cc9d3fJakob Stoklund Olesen 1773cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen allocatePhysRegs(); 1774cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen releaseMemory(); 1775cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen return true; 1776cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen} 1777