RegAllocGreedy.cpp revision 0d4fea786670473b53d285be378e619399e03488
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" 19f428eb6c1b09a2322b7a577b0bf2e49dd107bceaJakob Stoklund Olesen#include "LiveRangeEdit.h" 20cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "RegAllocBase.h" 21cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "Spiller.h" 22b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen#include "SpillPlacement.h" 23d0bb5e2ca05d9c942223bf05e5940bb0c6cc9d3fJakob Stoklund Olesen#include "SplitKit.h" 24cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "VirtRegMap.h" 250db841f9c2b9a25fb5ecb36e350d3a802c35654cJakob Stoklund Olesen#include "llvm/ADT/Statistic.h" 26cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "llvm/Analysis/AliasAnalysis.h" 27cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "llvm/Function.h" 28cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "llvm/PassAnalysisSupport.h" 29cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "llvm/CodeGen/CalcSpillWeights.h" 30b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen#include "llvm/CodeGen/EdgeBundles.h" 31cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "llvm/CodeGen/LiveIntervalAnalysis.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; 76cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen LiveStacks *LS; 77f428eb6c1b09a2322b7a577b0bf2e49dd107bceaJakob Stoklund Olesen MachineDominatorTree *DomTree; 78d0bb5e2ca05d9c942223bf05e5940bb0c6cc9d3fJakob Stoklund Olesen MachineLoopInfo *Loops; 79b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen EdgeBundles *Bundles; 80b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen SpillPlacement *SpillPlacer; 81f42b66169d75301346e3685fd2b3e45e47806367Jakob Stoklund Olesen LiveDebugVariables *DebugVars; 82f428eb6c1b09a2322b7a577b0bf2e49dd107bceaJakob Stoklund Olesen 83cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen // state 84cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen std::auto_ptr<Spiller> SpillerInstance; 8598d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen std::priority_queue<std::pair<unsigned, unsigned> > Queue; 861a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen unsigned NextCascade; 8722a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen 8822a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // Live ranges pass through a number of stages as we try to allocate them. 8922a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // Some of the stages may also create new live ranges: 9022a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // 9122a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // - Region splitting. 9222a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // - Per-block splitting. 9322a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // - Local splitting. 9422a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // - Spilling. 9522a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // 9622a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // Ranges produced by one of the stages skip the previous stages when they are 9722a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // dequeued. This improves performance because we can skip interference checks 9822a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // that are unlikely to give any results. It also guarantees that the live 9922a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // range splitting algorithm terminates, something that is otherwise hard to 10022a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // ensure. 10122a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen enum LiveRangeStage { 102fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen /// Newly created live range that has never been queued. 103fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen RS_New, 104fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen 105fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen /// Only attempt assignment and eviction. Then requeue as RS_Split. 106fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen RS_Assign, 107fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen 108fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen /// Attempt live range splitting if assignment is impossible. 109fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen RS_Split, 110fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen 11149743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen /// Attempt more aggressive live range splitting that is guaranteed to make 11249743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen /// progress. This is used for split products that may not be making 11349743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen /// progress. 11449743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen RS_Split2, 11549743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen 116fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen /// Live range will be spilled. No more splitting will be attempted. 117fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen RS_Spill, 118fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen 119fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen /// There is nothing more we can do to this live range. Abort compilation 120fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen /// if it can't be assigned. 121fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen RS_Done 12222a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen }; 12322a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen 124b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen static const char *const StageName[]; 125b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen 1261a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen // RegInfo - Keep additional information about each live range. 1271a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen struct RegInfo { 1281a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen LiveRangeStage Stage; 1291a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen 1301a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen // Cascade - Eviction loop prevention. See canEvictInterference(). 1311a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen unsigned Cascade; 1321a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen 1331a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen RegInfo() : Stage(RS_New), Cascade(0) {} 1341a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen }; 1351a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen 1361a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen IndexedMap<RegInfo, VirtReg2IndexFunctor> ExtraRegInfo; 13722a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen 13822a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen LiveRangeStage getStage(const LiveInterval &VirtReg) const { 1391a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen return ExtraRegInfo[VirtReg.reg].Stage; 1401a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen } 1411a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen 1421a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen void setStage(const LiveInterval &VirtReg, LiveRangeStage Stage) { 1431a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen ExtraRegInfo.resize(MRI->getNumVirtRegs()); 1441a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen ExtraRegInfo[VirtReg.reg].Stage = Stage; 14522a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen } 14622a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen 14722a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen template<typename Iterator> 14822a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen void setStage(Iterator Begin, Iterator End, LiveRangeStage NewStage) { 1491a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen ExtraRegInfo.resize(MRI->getNumVirtRegs()); 150f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund Olesen for (;Begin != End; ++Begin) { 151f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund Olesen unsigned Reg = (*Begin)->reg; 1521a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen if (ExtraRegInfo[Reg].Stage == RS_New) 1531a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen ExtraRegInfo[Reg].Stage = NewStage; 154f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund Olesen } 15522a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen } 156cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 15751458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen /// Cost of evicting interference. 15851458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen struct EvictionCost { 15951458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen unsigned BrokenHints; ///< Total number of broken hints. 16051458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen float MaxWeight; ///< Maximum spill weight evicted. 16151458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen 16251458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen EvictionCost(unsigned B = 0) : BrokenHints(B), MaxWeight(0) {} 16351458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen 16451458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen bool operator<(const EvictionCost &O) const { 16551458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen if (BrokenHints != O.BrokenHints) 16651458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen return BrokenHints < O.BrokenHints; 16751458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen return MaxWeight < O.MaxWeight; 16851458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen } 16951458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen }; 17051458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen 171b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen // splitting state. 17222a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen std::auto_ptr<SplitAnalysis> SA; 173bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen std::auto_ptr<SplitEditor> SE; 174b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 175eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen /// Cached per-block interference maps 176eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen InterferenceCache IntfCache; 177eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen 1787b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen /// All basic blocks where the current register has uses. 17996dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen SmallVector<SpillPlacement::BlockConstraint, 8> SplitConstraints; 180b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 18196dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen /// Global live range splitting candidate info. 18296dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen struct GlobalSplitCandidate { 18300005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // Register intended for assignment, or 0. 18496dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen unsigned PhysReg; 18500005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen 18600005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // SplitKit interval index for this candidate. 18700005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen unsigned IntvIdx; 18800005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen 18900005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // Interference for PhysReg. 190c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen InterferenceCache::Cursor Intf; 19100005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen 19200005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // Bundles where this candidate should be live. 19396dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen BitVector LiveBundles; 1945db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen SmallVector<unsigned, 8> ActiveBlocks; 1955db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen 196c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen void reset(InterferenceCache &Cache, unsigned Reg) { 1975db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen PhysReg = Reg; 19800005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen IntvIdx = 0; 199c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen Intf.setPhysReg(Cache, Reg); 2005db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen LiveBundles.clear(); 2015db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen ActiveBlocks.clear(); 2025db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen } 20300005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen 20400005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // Set B[i] = C for every live bundle where B[i] was NoCand. 20500005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen unsigned getBundles(SmallVectorImpl<unsigned> &B, unsigned C) { 20600005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen unsigned Count = 0; 20700005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen for (int i = LiveBundles.find_first(); i >= 0; 20800005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen i = LiveBundles.find_next(i)) 20900005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen if (B[i] == NoCand) { 21000005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen B[i] = C; 21100005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen Count++; 21200005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen } 21300005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen return Count; 21400005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen } 21596dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen }; 21696dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen 21796dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen /// Candidate info for for each PhysReg in AllocationOrder. 21896dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen /// This vector never shrinks, but grows to the size of the largest register 21996dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen /// class. 22096dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen SmallVector<GlobalSplitCandidate, 32> GlobalCand; 22196dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen 22200005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen enum { NoCand = ~0u }; 22300005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen 22400005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen /// Candidate map. Each edge bundle is assigned to a GlobalCand entry, or to 22500005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen /// NoCand which indicates the stack interval. 22600005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen SmallVector<unsigned, 32> BundleCand; 22700005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen 228cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesenpublic: 229cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen RAGreedy(); 230cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 231cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen /// Return the pass name. 232cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen virtual const char* getPassName() const { 233533f58ecdd8a4732c2f0e149387c4d8d8d4142deJakob Stoklund Olesen return "Greedy Register Allocator"; 234cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen } 235cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 236cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen /// RAGreedy analysis usage. 237cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen virtual void getAnalysisUsage(AnalysisUsage &AU) const; 238cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen virtual void releaseMemory(); 239cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen virtual Spiller &spiller() { return *SpillerInstance; } 24098d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen virtual void enqueue(LiveInterval *LI); 24198d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen virtual LiveInterval *dequeue(); 242ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen virtual unsigned selectOrSplit(LiveInterval&, 243ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen SmallVectorImpl<LiveInterval*>&); 244cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 245cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen /// Perform register allocation. 246cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen virtual bool runOnMachineFunction(MachineFunction &mf); 247cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 248cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen static char ID; 249b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick 250b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trickprivate: 25192a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen void LRE_WillEraseInstruction(MachineInstr*); 2527792e980c43536814ea42448db9799b4da32fef6Jakob Stoklund Olesen bool LRE_CanEraseVirtReg(unsigned); 2531d5b84508173b93faf513032b3847152e6060791Jakob Stoklund Olesen void LRE_WillShrinkVirtReg(unsigned); 254f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund Olesen void LRE_DidCloneVirtReg(unsigned, unsigned); 25592a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen 256200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen float calcSpillCost(); 257f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen bool addSplitConstraints(InterferenceCache::Cursor, float&); 258f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen void addThroughConstraints(InterferenceCache::Cursor, ArrayRef<unsigned>); 259c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen void growRegion(GlobalSplitCandidate &Cand); 260c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen float calcGlobalSplitCost(GlobalSplitCandidate&); 26187972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen bool calcCompactRegion(GlobalSplitCandidate&); 26200005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen void splitAroundRegion(LiveRangeEdit&, ArrayRef<unsigned>); 263034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen void calcGapWeights(unsigned, SmallVectorImpl<float>&); 26451458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen bool shouldEvict(LiveInterval &A, bool, LiveInterval &B, bool); 26551458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen bool canEvictInterference(LiveInterval&, unsigned, bool, EvictionCost&); 26651458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen void evictInterference(LiveInterval&, unsigned, 26751458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen SmallVectorImpl<LiveInterval*>&); 268b64d92e29f38002e52a22fe36ea2d488968e3537Jakob Stoklund Olesen 2696bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen unsigned tryAssign(LiveInterval&, AllocationOrder&, 2706bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen SmallVectorImpl<LiveInterval*>&); 27198c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen unsigned tryEvict(LiveInterval&, AllocationOrder&, 2726bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen SmallVectorImpl<LiveInterval*>&, unsigned = ~0u); 273b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen unsigned tryRegionSplit(LiveInterval&, AllocationOrder&, 274b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen SmallVectorImpl<LiveInterval*>&); 275dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen unsigned tryBlockSplit(LiveInterval&, AllocationOrder&, 276dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob 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()); 311cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen initializeStrongPHIEliminationPass(*PassRegistry::getPassRegistry()); 3125b220213bfe9c37c2bb41a7ae0804e06a14f1007Rafael Espindola initializeRegisterCoalescerPass(*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()); 318b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen initializeEdgeBundlesPass(*PassRegistry::getPassRegistry()); 319b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen initializeSpillPlacementPass(*PassRegistry::getPassRegistry()); 320cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen} 321cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 322cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesenvoid RAGreedy::getAnalysisUsage(AnalysisUsage &AU) const { 323cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.setPreservesCFG(); 324cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addRequired<AliasAnalysis>(); 325cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addPreserved<AliasAnalysis>(); 326cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addRequired<LiveIntervals>(); 327b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen AU.addRequired<SlotIndexes>(); 328cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addPreserved<SlotIndexes>(); 329cfafc54040cc9722995558124f253d05a038176bJakob Stoklund Olesen AU.addRequired<LiveDebugVariables>(); 330cfafc54040cc9722995558124f253d05a038176bJakob Stoklund Olesen AU.addPreserved<LiveDebugVariables>(); 331cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen if (StrongPHIElim) 332cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addRequiredID(StrongPHIEliminationID); 33327215676c7114132a0374f7b5c9ea73d9354d329Jakob Stoklund Olesen AU.addRequiredTransitiveID(RegisterCoalescerPassID); 334cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addRequired<CalculateSpillWeights>(); 335cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addRequired<LiveStacks>(); 336cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addPreserved<LiveStacks>(); 337f428eb6c1b09a2322b7a577b0bf2e49dd107bceaJakob Stoklund Olesen AU.addRequired<MachineDominatorTree>(); 338f428eb6c1b09a2322b7a577b0bf2e49dd107bceaJakob Stoklund Olesen AU.addPreserved<MachineDominatorTree>(); 339cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addRequired<MachineLoopInfo>(); 340cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addPreserved<MachineLoopInfo>(); 341cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addRequired<VirtRegMap>(); 342cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addPreserved<VirtRegMap>(); 343b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen AU.addRequired<EdgeBundles>(); 344b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen AU.addRequired<SpillPlacement>(); 345cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen MachineFunctionPass::getAnalysisUsage(AU); 346cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen} 347cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 34892a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen 34992a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 35092a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen// LiveRangeEdit delegate methods 35192a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 35292a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen 35392a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesenvoid RAGreedy::LRE_WillEraseInstruction(MachineInstr *MI) { 35492a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen // LRE itself will remove from SlotIndexes and parent basic block. 35592a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen VRM->RemoveMachineInstrFromMaps(MI); 35692a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen} 35792a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen 3587792e980c43536814ea42448db9799b4da32fef6Jakob Stoklund Olesenbool RAGreedy::LRE_CanEraseVirtReg(unsigned VirtReg) { 3597792e980c43536814ea42448db9799b4da32fef6Jakob Stoklund Olesen if (unsigned PhysReg = VRM->getPhys(VirtReg)) { 3607792e980c43536814ea42448db9799b4da32fef6Jakob Stoklund Olesen unassign(LIS->getInterval(VirtReg), PhysReg); 3617792e980c43536814ea42448db9799b4da32fef6Jakob Stoklund Olesen return true; 3627792e980c43536814ea42448db9799b4da32fef6Jakob Stoklund Olesen } 3637792e980c43536814ea42448db9799b4da32fef6Jakob Stoklund Olesen // Unassigned virtreg is probably in the priority queue. 3647792e980c43536814ea42448db9799b4da32fef6Jakob Stoklund Olesen // RegAllocBase will erase it after dequeueing. 3657792e980c43536814ea42448db9799b4da32fef6Jakob Stoklund Olesen return false; 3667792e980c43536814ea42448db9799b4da32fef6Jakob Stoklund Olesen} 36792a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen 3681d5b84508173b93faf513032b3847152e6060791Jakob Stoklund Olesenvoid RAGreedy::LRE_WillShrinkVirtReg(unsigned VirtReg) { 3691d5b84508173b93faf513032b3847152e6060791Jakob Stoklund Olesen unsigned PhysReg = VRM->getPhys(VirtReg); 3701d5b84508173b93faf513032b3847152e6060791Jakob Stoklund Olesen if (!PhysReg) 3711d5b84508173b93faf513032b3847152e6060791Jakob Stoklund Olesen return; 3721d5b84508173b93faf513032b3847152e6060791Jakob Stoklund Olesen 3731d5b84508173b93faf513032b3847152e6060791Jakob Stoklund Olesen // Register is assigned, put it back on the queue for reassignment. 3741d5b84508173b93faf513032b3847152e6060791Jakob Stoklund Olesen LiveInterval &LI = LIS->getInterval(VirtReg); 3751d5b84508173b93faf513032b3847152e6060791Jakob Stoklund Olesen unassign(LI, PhysReg); 3761d5b84508173b93faf513032b3847152e6060791Jakob Stoklund Olesen enqueue(&LI); 3771d5b84508173b93faf513032b3847152e6060791Jakob Stoklund Olesen} 3781d5b84508173b93faf513032b3847152e6060791Jakob Stoklund Olesen 379f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund Olesenvoid RAGreedy::LRE_DidCloneVirtReg(unsigned New, unsigned Old) { 3800d4fea786670473b53d285be378e619399e03488Jakob Stoklund Olesen // Cloning a register we haven't even heard about yet? Just ignore it. 3810d4fea786670473b53d285be378e619399e03488Jakob Stoklund Olesen if (!ExtraRegInfo.inBounds(Old)) 3820d4fea786670473b53d285be378e619399e03488Jakob Stoklund Olesen return; 3830d4fea786670473b53d285be378e619399e03488Jakob Stoklund Olesen 384f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund Olesen // LRE may clone a virtual register because dead code elimination causes it to 385165e231c4295deb5cabd124d08e231b551bcc0b2Jakob Stoklund Olesen // be split into connected components. The new components are much smaller 386165e231c4295deb5cabd124d08e231b551bcc0b2Jakob Stoklund Olesen // than the original, so they should get a new chance at being assigned. 387f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund Olesen // same stage as the parent. 388165e231c4295deb5cabd124d08e231b551bcc0b2Jakob Stoklund Olesen ExtraRegInfo[Old].Stage = RS_Assign; 3891a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen ExtraRegInfo.grow(New); 3901a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen ExtraRegInfo[New] = ExtraRegInfo[Old]; 391f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund Olesen} 392f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund Olesen 393cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesenvoid RAGreedy::releaseMemory() { 394cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen SpillerInstance.reset(0); 3951a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen ExtraRegInfo.clear(); 3965db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen GlobalCand.clear(); 397cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen RegAllocBase::releaseMemory(); 398cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen} 399cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 40098d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesenvoid RAGreedy::enqueue(LiveInterval *LI) { 40198d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen // Prioritize live ranges by size, assigning larger ranges first. 40298d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen // The queue holds (size, reg) pairs. 403107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen const unsigned Size = LI->getSize(); 404107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen const unsigned Reg = LI->reg; 40598d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen assert(TargetRegisterInfo::isVirtualRegister(Reg) && 40698d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen "Can only enqueue virtual registers"); 407107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen unsigned Prio; 40890c1d7ddfc65654f7efe72d56cad65d1af9e6b2aJakob Stoklund Olesen 4091a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen ExtraRegInfo.grow(Reg); 4101a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen if (ExtraRegInfo[Reg].Stage == RS_New) 411fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen ExtraRegInfo[Reg].Stage = RS_Assign; 412f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund Olesen 413cc07e04262fe4bc35469fbadc53d2ec7bfd02fe2Jakob Stoklund Olesen if (ExtraRegInfo[Reg].Stage == RS_Split) { 414eb29157d80847c207b77910bcd40a6a6c91ca5c5Jakob Stoklund Olesen // Unsplit ranges that couldn't be allocated immediately are deferred until 415a16a25ddeaf495b78b04e2a19feeac00d9824e63Jakob Stoklund Olesen // everything else has been allocated. 416a16a25ddeaf495b78b04e2a19feeac00d9824e63Jakob Stoklund Olesen Prio = Size; 417cc07e04262fe4bc35469fbadc53d2ec7bfd02fe2Jakob Stoklund Olesen } else { 418a16a25ddeaf495b78b04e2a19feeac00d9824e63Jakob Stoklund Olesen // Everything is allocated in long->short order. Long ranges that don't fit 419a16a25ddeaf495b78b04e2a19feeac00d9824e63Jakob Stoklund Olesen // should be spilled (or split) ASAP so they don't create interference. 420107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen Prio = (1u << 31) + Size; 421d2a50734234a80893ad71da90d9f32032c47e000Jakob Stoklund Olesen 422eb29157d80847c207b77910bcd40a6a6c91ca5c5Jakob Stoklund Olesen // Boost ranges that have a physical register hint. 423eb29157d80847c207b77910bcd40a6a6c91ca5c5Jakob Stoklund Olesen if (TargetRegisterInfo::isPhysicalRegister(VRM->getRegAllocPref(Reg))) 424eb29157d80847c207b77910bcd40a6a6c91ca5c5Jakob Stoklund Olesen Prio |= (1u << 30); 425eb29157d80847c207b77910bcd40a6a6c91ca5c5Jakob Stoklund Olesen } 426107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen 427107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen Queue.push(std::make_pair(Prio, Reg)); 42890c1d7ddfc65654f7efe72d56cad65d1af9e6b2aJakob Stoklund Olesen} 42990c1d7ddfc65654f7efe72d56cad65d1af9e6b2aJakob Stoklund Olesen 43098d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund OlesenLiveInterval *RAGreedy::dequeue() { 43198d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen if (Queue.empty()) 43298d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen return 0; 43398d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen LiveInterval *LI = &LIS->getInterval(Queue.top().second); 43498d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen Queue.pop(); 43598d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen return LI; 43698d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen} 437770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen 4386bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen 4396bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 4406bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen// Direct Assignment 4416bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 4426bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen 4436bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen/// tryAssign - Try to assign VirtReg to an available register. 4446bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesenunsigned RAGreedy::tryAssign(LiveInterval &VirtReg, 4456bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen AllocationOrder &Order, 4466bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen SmallVectorImpl<LiveInterval*> &NewVRegs) { 4476bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen Order.rewind(); 4486bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen unsigned PhysReg; 4496bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen while ((PhysReg = Order.next())) 4506bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen if (!checkPhysRegInterference(VirtReg, PhysReg)) 4516bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen break; 4526bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen if (!PhysReg || Order.isHint(PhysReg)) 4536bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen return PhysReg; 4546bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen 45551458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // PhysReg is available, but there may be a better choice. 45651458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen 45751458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // If we missed a simple hint, try to cheaply evict interference from the 45851458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // preferred register. 45951458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen if (unsigned Hint = MRI->getSimpleHint(VirtReg.reg)) 46051458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen if (Order.isHint(Hint)) { 46151458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen DEBUG(dbgs() << "missed hint " << PrintReg(Hint, TRI) << '\n'); 46251458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen EvictionCost MaxCost(1); 46351458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen if (canEvictInterference(VirtReg, Hint, true, MaxCost)) { 46451458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen evictInterference(VirtReg, Hint, NewVRegs); 46551458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen return Hint; 46651458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen } 46751458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen } 46851458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen 46951458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // Try to evict interference from a cheaper alternative. 4706bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen unsigned Cost = TRI->getCostPerUse(PhysReg); 4716bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen 4726bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen // Most registers have 0 additional cost. 4736bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen if (!Cost) 4746bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen return PhysReg; 4756bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen 4766bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen DEBUG(dbgs() << PrintReg(PhysReg, TRI) << " is available at cost " << Cost 4776bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen << '\n'); 4786bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen unsigned CheapReg = tryEvict(VirtReg, Order, NewVRegs, Cost); 4796bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen return CheapReg ? CheapReg : PhysReg; 4806bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen} 4816bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen 4826bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen 483770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen//===----------------------------------------------------------------------===// 48498c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen// Interference eviction 48598c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 4862710638db2eb84cd7eefb8bb9a1b7e5c49413d45Jakob Stoklund Olesen 48751458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// shouldEvict - determine if A should evict the assigned live range B. The 48851458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// eviction policy defined by this function together with the allocation order 48951458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// defined by enqueue() decides which registers ultimately end up being split 49051458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// and spilled. 491b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen/// 4921a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen/// Cascade numbers are used to prevent infinite loops if this function is a 4931a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen/// cyclic relation. 49451458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// 49551458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// @param A The live range to be assigned. 49651458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// @param IsHint True when A is about to be assigned to its preferred 49751458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// register. 49851458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// @param B The live range to be evicted. 49951458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// @param BreaksHint True when B is already assigned to its preferred register. 50051458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesenbool RAGreedy::shouldEvict(LiveInterval &A, bool IsHint, 50151458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen LiveInterval &B, bool BreaksHint) { 50249743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen bool CanSplit = getStage(B) < RS_Spill; 50351458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen 50451458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // Be fairly aggressive about following hints as long as the evictee can be 50551458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // split. 50651458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen if (CanSplit && IsHint && !BreaksHint) 50751458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen return true; 50851458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen 5091a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen return A.weight > B.weight; 510b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen} 511b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen 51251458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// canEvictInterference - Return true if all interferences between VirtReg and 51351458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// PhysReg can be evicted. When OnlyCheap is set, don't do anything 51451458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// 51551458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// @param VirtReg Live range that is about to be assigned. 51651458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// @param PhysReg Desired register for assignment. 51751458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// @prarm IsHint True when PhysReg is VirtReg's preferred register. 51851458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// @param MaxCost Only look for cheaper candidates and update with new cost 51951458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// when returning true. 52051458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// @returns True when interference can be evicted cheaper than MaxCost. 52198c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesenbool RAGreedy::canEvictInterference(LiveInterval &VirtReg, unsigned PhysReg, 52251458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen bool IsHint, EvictionCost &MaxCost) { 5231a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen // Find VirtReg's cascade number. This will be unassigned if VirtReg was never 5241a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen // involved in an eviction before. If a cascade number was assigned, deny 5251a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen // evicting anything with the same or a newer cascade number. This prevents 5261a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen // infinite eviction loops. 5271a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen // 5281a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen // This works out so a register without a cascade number is allowed to evict 5291a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen // anything, and it can be evicted by anything. 5301a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen unsigned Cascade = ExtraRegInfo[VirtReg.reg].Cascade; 5311a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen if (!Cascade) 5321a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen Cascade = NextCascade; 5331a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen 53451458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen EvictionCost Cost; 53598c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen for (const unsigned *AliasI = TRI->getOverlaps(PhysReg); *AliasI; ++AliasI) { 53698c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen LiveIntervalUnion::Query &Q = query(VirtReg, *AliasI); 5373f5bedf5cbde2cc2badc86b1a0b377f6efcde71cJakob Stoklund Olesen // If there is 10 or more interferences, chances are one is heavier. 53851458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen if (Q.collectInterferingVRegs(10) >= 10) 53998c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen return false; 54098c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen 5413f5bedf5cbde2cc2badc86b1a0b377f6efcde71cJakob Stoklund Olesen // Check if any interfering live range is heavier than MaxWeight. 5423f5bedf5cbde2cc2badc86b1a0b377f6efcde71cJakob Stoklund Olesen for (unsigned i = Q.interferingVRegs().size(); i; --i) { 5433f5bedf5cbde2cc2badc86b1a0b377f6efcde71cJakob Stoklund Olesen LiveInterval *Intf = Q.interferingVRegs()[i - 1]; 54498c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen if (TargetRegisterInfo::isPhysicalRegister(Intf->reg)) 54598c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen return false; 54651458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // Never evict spill products. They cannot split or spill. 547fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen if (getStage(*Intf) == RS_Done) 5481a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen return false; 54951458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // Once a live range becomes small enough, it is urgent that we find a 55051458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // register for it. This is indicated by an infinite spill weight. These 55151458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // urgent live ranges get to evict almost anything. 55251458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen bool Urgent = !VirtReg.isSpillable() && Intf->isSpillable(); 55351458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // Only evict older cascades or live ranges without a cascade. 55451458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen unsigned IntfCascade = ExtraRegInfo[Intf->reg].Cascade; 55551458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen if (Cascade <= IntfCascade) { 55651458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen if (!Urgent) 55751458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen return false; 55851458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // We permit breaking cascades for urgent evictions. It should be the 55951458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // last resort, though, so make it really expensive. 56051458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen Cost.BrokenHints += 10; 56151458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen } 56251458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // Would this break a satisfied hint? 56351458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen bool BreaksHint = VRM->hasPreferredPhys(Intf->reg); 56451458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // Update eviction cost. 56551458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen Cost.BrokenHints += BreaksHint; 56651458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen Cost.MaxWeight = std::max(Cost.MaxWeight, Intf->weight); 56751458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // Abort if this would be too expensive. 56851458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen if (!(Cost < MaxCost)) 569b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen return false; 57051458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // Finally, apply the eviction policy for non-urgent evictions. 57151458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen if (!Urgent && !shouldEvict(VirtReg, IsHint, *Intf, BreaksHint)) 57276395c9a31444fa86514473e0852cdd67752d0e8Jakob Stoklund Olesen return false; 5732710638db2eb84cd7eefb8bb9a1b7e5c49413d45Jakob Stoklund Olesen } 5742710638db2eb84cd7eefb8bb9a1b7e5c49413d45Jakob Stoklund Olesen } 57551458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen MaxCost = Cost; 57698c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen return true; 57798c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen} 57898c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen 57951458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// evictInterference - Evict any interferring registers that prevent VirtReg 58051458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// from being assigned to Physreg. This assumes that canEvictInterference 58151458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen/// returned true. 58251458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesenvoid RAGreedy::evictInterference(LiveInterval &VirtReg, unsigned PhysReg, 58351458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen SmallVectorImpl<LiveInterval*> &NewVRegs) { 58451458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // Make sure that VirtReg has a cascade number, and assign that cascade 58551458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // number to every evicted register. These live ranges than then only be 58651458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // evicted by a newer cascade, preventing infinite loops. 58751458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen unsigned Cascade = ExtraRegInfo[VirtReg.reg].Cascade; 58851458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen if (!Cascade) 58951458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen Cascade = ExtraRegInfo[VirtReg.reg].Cascade = NextCascade++; 59051458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen 59151458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen DEBUG(dbgs() << "evicting " << PrintReg(PhysReg, TRI) 59251458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen << " interference: Cascade " << Cascade << '\n'); 59351458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen for (const unsigned *AliasI = TRI->getOverlaps(PhysReg); *AliasI; ++AliasI) { 59451458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen LiveIntervalUnion::Query &Q = query(VirtReg, *AliasI); 59551458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen assert(Q.seenAllInterferences() && "Didn't check all interfererences."); 59651458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen for (unsigned i = 0, e = Q.interferingVRegs().size(); i != e; ++i) { 59751458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen LiveInterval *Intf = Q.interferingVRegs()[i]; 59851458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen unassign(*Intf, VRM->getPhys(Intf->reg)); 59951458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen assert((ExtraRegInfo[Intf->reg].Cascade < Cascade || 60051458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen VirtReg.isSpillable() < Intf->isSpillable()) && 60151458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen "Cannot decrease cascade number, illegal eviction"); 60251458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen ExtraRegInfo[Intf->reg].Cascade = Cascade; 60351458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen ++NumEvicted; 60451458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen NewVRegs.push_back(Intf); 60551458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen } 60651458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen } 60751458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen} 60851458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen 60998c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen/// tryEvict - Try to evict all interferences for a physreg. 61076395c9a31444fa86514473e0852cdd67752d0e8Jakob Stoklund Olesen/// @param VirtReg Currently unassigned virtual register. 61176395c9a31444fa86514473e0852cdd67752d0e8Jakob Stoklund Olesen/// @param Order Physregs to try. 61276395c9a31444fa86514473e0852cdd67752d0e8Jakob Stoklund Olesen/// @return Physreg to assign VirtReg, or 0. 61398c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesenunsigned RAGreedy::tryEvict(LiveInterval &VirtReg, 61498c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen AllocationOrder &Order, 6156bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen SmallVectorImpl<LiveInterval*> &NewVRegs, 6166bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen unsigned CostPerUseLimit) { 61798c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen NamedRegionTimer T("Evict", TimerGroupName, TimePassesIsEnabled); 61898c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen 61951458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // Keep track of the cheapest interference seen so far. 62051458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen EvictionCost BestCost(~0u); 62198c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen unsigned BestPhys = 0; 62298c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen 62351458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // When we are just looking for a reduced cost per use, don't break any 62451458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // hints, and only evict smaller spill weights. 62551458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen if (CostPerUseLimit < ~0u) { 62651458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen BestCost.BrokenHints = 0; 62751458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen BestCost.MaxWeight = VirtReg.weight; 62851458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen } 62951458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen 63098c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen Order.rewind(); 63198c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen while (unsigned PhysReg = Order.next()) { 6326bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen if (TRI->getCostPerUse(PhysReg) >= CostPerUseLimit) 6336bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen continue; 63451458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // The first use of a callee-saved register in a function has cost 1. 63551458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen // Don't start using a CSR when the CostPerUseLimit is low. 63651458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen if (CostPerUseLimit == 1) 63751458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen if (unsigned CSR = RegClassInfo.getLastCalleeSavedAlias(PhysReg)) 63851458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen if (!MRI->isPhysRegUsed(CSR)) { 63951458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen DEBUG(dbgs() << PrintReg(PhysReg, TRI) << " would clobber CSR " 64051458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen << PrintReg(CSR, TRI) << '\n'); 64151458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen continue; 64251458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen } 64351458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen 64451458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen if (!canEvictInterference(VirtReg, PhysReg, false, BestCost)) 64598c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen continue; 64698c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen 64798c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen // Best so far. 64898c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen BestPhys = PhysReg; 64951458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen 65057f1e2cee06f9b57995727d786aeb1031c5376bdJakob Stoklund Olesen // Stop if the hint can be used. 65157f1e2cee06f9b57995727d786aeb1031c5376bdJakob Stoklund Olesen if (Order.isHint(PhysReg)) 65257f1e2cee06f9b57995727d786aeb1031c5376bdJakob Stoklund Olesen break; 6532710638db2eb84cd7eefb8bb9a1b7e5c49413d45Jakob Stoklund Olesen } 6542710638db2eb84cd7eefb8bb9a1b7e5c49413d45Jakob Stoklund Olesen 65598c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen if (!BestPhys) 65698c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen return 0; 65798c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen 65851458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen evictInterference(VirtReg, BestPhys, NewVRegs); 65998c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen return BestPhys; 660b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick} 661b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick 662770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen 663770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen//===----------------------------------------------------------------------===// 664b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen// Region Splitting 665b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen//===----------------------------------------------------------------------===// 666b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 6671b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen/// addSplitConstraints - Fill out the SplitConstraints vector based on the 6681b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen/// interference pattern in Physreg and its aliases. Add the constraints to 6691b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen/// SpillPlacement and return the static cost of this split in Cost, assuming 6701b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen/// that all preferences in SplitConstraints are met. 671f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen/// Return false if there are no bundles with positive bias. 672f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesenbool RAGreedy::addSplitConstraints(InterferenceCache::Cursor Intf, 673f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen float &Cost) { 674db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks(); 675eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen 676b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen // Reset interference dependent info. 677db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen SplitConstraints.resize(UseBlocks.size()); 67896dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen float StaticCost = 0; 679db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen for (unsigned i = 0; i != UseBlocks.size(); ++i) { 680db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen const SplitAnalysis::BlockInfo &BI = UseBlocks[i]; 68196dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen SpillPlacement::BlockConstraint &BC = SplitConstraints[i]; 68296dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen 683f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen BC.Number = BI.MBB->getNumber(); 684eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen Intf.moveToBlock(BC.Number); 685db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen BC.Entry = BI.LiveIn ? SpillPlacement::PrefReg : SpillPlacement::DontCare; 686db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen BC.Exit = BI.LiveOut ? SpillPlacement::PrefReg : SpillPlacement::DontCare; 6875ebca793db6262386d7464d03cdaefeb5b640ad3Jakob Stoklund Olesen BC.ChangesValue = BI.FirstDef; 688b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 689eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen if (!Intf.hasInterference()) 690eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen continue; 691eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen 69296dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen // Number of spill code instructions to insert. 69396dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen unsigned Ins = 0; 69496dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen 69596dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen // Interference for the live-in value. 696eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen if (BI.LiveIn) { 6976c8afd728eb02742ce320ecd39bcf3774d8423b7Jakob Stoklund Olesen if (Intf.first() <= Indexes->getMBBStartIdx(BC.Number)) 698db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen BC.Entry = SpillPlacement::MustSpill, ++Ins; 699fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen else if (Intf.first() < BI.FirstInstr) 70096dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen BC.Entry = SpillPlacement::PrefSpill, ++Ins; 701fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen else if (Intf.first() < BI.LastInstr) 70296dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen ++Ins; 703a50c539b7a9e74597da34bfaea5429a48481f18bJakob Stoklund Olesen } 704b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 70596dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen // Interference for the live-out value. 706eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen if (BI.LiveOut) { 707612f7807c581eafb7c8105e1a55c8d839033bfb3Jakob Stoklund Olesen if (Intf.last() >= SA->getLastSplitPoint(BC.Number)) 708db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen BC.Exit = SpillPlacement::MustSpill, ++Ins; 709fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen else if (Intf.last() > BI.LastInstr) 71096dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen BC.Exit = SpillPlacement::PrefSpill, ++Ins; 711fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen else if (Intf.last() > BI.FirstInstr) 71296dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen ++Ins; 713b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen } 714b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 71596dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen // Accumulate the total frequency of inserted spill code. 71696dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen if (Ins) 71796dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen StaticCost += Ins * SpillPlacer->getBlockFrequency(BC.Number); 718b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen } 719f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen Cost = StaticCost; 720db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen 7211b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen // Add constraints for use-blocks. Note that these are the only constraints 7221b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen // that may add a positive bias, it is downhill from here. 7231b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen SpillPlacer->addConstraints(SplitConstraints); 724f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen return SpillPlacer->scanActiveBundles(); 725f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen} 726db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen 727db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen 728f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen/// addThroughConstraints - Add constraints and links to SpillPlacer from the 729f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen/// live-through blocks in Blocks. 730f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesenvoid RAGreedy::addThroughConstraints(InterferenceCache::Cursor Intf, 731f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen ArrayRef<unsigned> Blocks) { 7321b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen const unsigned GroupSize = 8; 7331b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen SpillPlacement::BlockConstraint BCS[GroupSize]; 734f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen unsigned TBS[GroupSize]; 735f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen unsigned B = 0, T = 0; 736db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen 737f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen for (unsigned i = 0; i != Blocks.size(); ++i) { 738f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen unsigned Number = Blocks[i]; 7391b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen Intf.moveToBlock(Number); 7401b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen 7417b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen if (!Intf.hasInterference()) { 742f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen assert(T < GroupSize && "Array overflow"); 743f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen TBS[T] = Number; 744f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen if (++T == GroupSize) { 74539b5abf507b43da6b92f68b86406e0015ead18e9Frits van Bommel SpillPlacer->addLinks(makeArrayRef(TBS, T)); 746f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen T = 0; 747f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen } 7487b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen continue; 7491b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen } 7501b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen 751f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen assert(B < GroupSize && "Array overflow"); 752f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen BCS[B].Number = Number; 753f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen 7547b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen // Interference for the live-in value. 7557b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen if (Intf.first() <= Indexes->getMBBStartIdx(Number)) 7567b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen BCS[B].Entry = SpillPlacement::MustSpill; 7577b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen else 7587b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen BCS[B].Entry = SpillPlacement::PrefSpill; 7597b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen 7607b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen // Interference for the live-out value. 7617b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen if (Intf.last() >= SA->getLastSplitPoint(Number)) 7627b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen BCS[B].Exit = SpillPlacement::MustSpill; 7637b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen else 7647b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen BCS[B].Exit = SpillPlacement::PrefSpill; 7657b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen 7661b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen if (++B == GroupSize) { 7671b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen ArrayRef<SpillPlacement::BlockConstraint> Array(BCS, B); 7681b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen SpillPlacer->addConstraints(Array); 7691b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen B = 0; 7701b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen } 771db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen } 772db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen 7731b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen ArrayRef<SpillPlacement::BlockConstraint> Array(BCS, B); 7741b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen SpillPlacer->addConstraints(Array); 77539b5abf507b43da6b92f68b86406e0015ead18e9Frits van Bommel SpillPlacer->addLinks(makeArrayRef(TBS, T)); 776b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen} 777b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 778c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesenvoid RAGreedy::growRegion(GlobalSplitCandidate &Cand) { 7795db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen // Keep track of through blocks that have not been added to SpillPlacer. 7805db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen BitVector Todo = SA->getThroughBlocks(); 7815db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen SmallVectorImpl<unsigned> &ActiveBlocks = Cand.ActiveBlocks; 7825db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen unsigned AddedTo = 0; 783f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen#ifndef NDEBUG 784f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen unsigned Visited = 0; 785f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen#endif 7865db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen 787f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen for (;;) { 788f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen ArrayRef<unsigned> NewBundles = SpillPlacer->getRecentPositive(); 789f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen // Find new through blocks in the periphery of PrefRegBundles. 790f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen for (int i = 0, e = NewBundles.size(); i != e; ++i) { 791f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen unsigned Bundle = NewBundles[i]; 792f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen // Look at all blocks connected to Bundle in the full graph. 793f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen ArrayRef<unsigned> Blocks = Bundles->getBlocks(Bundle); 794f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen for (ArrayRef<unsigned>::iterator I = Blocks.begin(), E = Blocks.end(); 795f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen I != E; ++I) { 796f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen unsigned Block = *I; 7975db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen if (!Todo.test(Block)) 798f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen continue; 7995db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen Todo.reset(Block); 800f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen // This is a new through block. Add it to SpillPlacer later. 8015db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen ActiveBlocks.push_back(Block); 802f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen#ifndef NDEBUG 803f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen ++Visited; 804f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen#endif 805f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen } 806f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen } 807f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen // Any new blocks to add? 808549019792a8b14500cab093ac8f3c5f7331e86d7Jakob Stoklund Olesen if (ActiveBlocks.size() == AddedTo) 809549019792a8b14500cab093ac8f3c5f7331e86d7Jakob Stoklund Olesen break; 810b4666364f4db4889883d7a6c02a177ebcde7c240Jakob Stoklund Olesen 811b4666364f4db4889883d7a6c02a177ebcde7c240Jakob Stoklund Olesen // Compute through constraints from the interference, or assume that all 812b4666364f4db4889883d7a6c02a177ebcde7c240Jakob Stoklund Olesen // through blocks prefer spilling when forming compact regions. 813b4666364f4db4889883d7a6c02a177ebcde7c240Jakob Stoklund Olesen ArrayRef<unsigned> NewBlocks = makeArrayRef(ActiveBlocks).slice(AddedTo); 814b4666364f4db4889883d7a6c02a177ebcde7c240Jakob Stoklund Olesen if (Cand.PhysReg) 815b4666364f4db4889883d7a6c02a177ebcde7c240Jakob Stoklund Olesen addThroughConstraints(Cand.Intf, NewBlocks); 816b4666364f4db4889883d7a6c02a177ebcde7c240Jakob Stoklund Olesen else 817b87f91b063a0ac853735f2af3bd94fb8551a11ffJakob Stoklund Olesen // Provide a strong negative bias on through blocks to prevent unwanted 818b87f91b063a0ac853735f2af3bd94fb8551a11ffJakob Stoklund Olesen // liveness on loop backedges. 819b87f91b063a0ac853735f2af3bd94fb8551a11ffJakob Stoklund Olesen SpillPlacer->addPrefSpill(NewBlocks, /* Strong= */ true); 820549019792a8b14500cab093ac8f3c5f7331e86d7Jakob Stoklund Olesen AddedTo = ActiveBlocks.size(); 821549019792a8b14500cab093ac8f3c5f7331e86d7Jakob Stoklund Olesen 822f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen // Perhaps iterating can enable more bundles? 823f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen SpillPlacer->iterate(); 824f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen } 825f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen DEBUG(dbgs() << ", v=" << Visited); 826f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen} 82796dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen 82887972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen/// calcCompactRegion - Compute the set of edge bundles that should be live 82987972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen/// when splitting the current live range into compact regions. Compact 83087972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen/// regions can be computed without looking at interference. They are the 83187972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen/// regions formed by removing all the live-through blocks from the live range. 83287972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen/// 83387972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen/// Returns false if the current live range is already compact, or if the 83487972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen/// compact regions would form single block regions anyway. 83587972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesenbool RAGreedy::calcCompactRegion(GlobalSplitCandidate &Cand) { 83687972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen // Without any through blocks, the live range is already compact. 83787972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen if (!SA->getNumThroughBlocks()) 83887972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen return false; 83987972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen 84087972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen // Compact regions don't correspond to any physreg. 84187972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen Cand.reset(IntfCache, 0); 84287972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen 84387972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen DEBUG(dbgs() << "Compact region bundles"); 84487972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen 84587972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen // Use the spill placer to determine the live bundles. GrowRegion pretends 84687972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen // that all the through blocks have interference when PhysReg is unset. 84787972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen SpillPlacer->prepare(Cand.LiveBundles); 84887972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen 84987972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen // The static split cost will be zero since Cand.Intf reports no interference. 85087972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen float Cost; 85187972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen if (!addSplitConstraints(Cand.Intf, Cost)) { 85287972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen DEBUG(dbgs() << ", none.\n"); 85387972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen return false; 85487972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen } 85587972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen 85687972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen growRegion(Cand); 85787972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen SpillPlacer->finish(); 85887972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen 85987972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen if (!Cand.LiveBundles.any()) { 86087972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen DEBUG(dbgs() << ", none.\n"); 86187972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen return false; 86287972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen } 86387972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen 86487972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen DEBUG({ 86587972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen for (int i = Cand.LiveBundles.find_first(); i>=0; 86687972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen i = Cand.LiveBundles.find_next(i)) 86787972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen dbgs() << " EB#" << i; 86887972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen dbgs() << ".\n"; 86987972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen }); 87087972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen return true; 87187972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen} 87287972fa63f0e2631778166e0c258c456ec12db7cJakob Stoklund Olesen 873200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen/// calcSpillCost - Compute how expensive it would be to split the live range in 874200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen/// SA around all use blocks instead of forming bundle regions. 875200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesenfloat RAGreedy::calcSpillCost() { 876200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen float Cost = 0; 877200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks(); 878200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen for (unsigned i = 0; i != UseBlocks.size(); ++i) { 879200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen const SplitAnalysis::BlockInfo &BI = UseBlocks[i]; 880200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen unsigned Number = BI.MBB->getNumber(); 881200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen // We normally only need one spill instruction - a load or a store. 882200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen Cost += SpillPlacer->getBlockFrequency(Number); 883200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen 884200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen // Unless the value is redefined in the block. 8853f5beede1bb97ba4e06dc300e00b70e1013e7216Jakob Stoklund Olesen if (BI.LiveIn && BI.LiveOut && BI.FirstDef) 8863f5beede1bb97ba4e06dc300e00b70e1013e7216Jakob Stoklund Olesen Cost += SpillPlacer->getBlockFrequency(Number); 887200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen } 888200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen return Cost; 889200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen} 890200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen 891b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen/// calcGlobalSplitCost - Return the global split cost of following the split 892b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen/// pattern in LiveBundles. This cost should be added to the local cost of the 89396dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen/// interference pattern in SplitConstraints. 894b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen/// 895c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesenfloat RAGreedy::calcGlobalSplitCost(GlobalSplitCandidate &Cand) { 896b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen float GlobalCost = 0; 8975db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen const BitVector &LiveBundles = Cand.LiveBundles; 898db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks(); 899db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen for (unsigned i = 0; i != UseBlocks.size(); ++i) { 900db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen const SplitAnalysis::BlockInfo &BI = UseBlocks[i]; 90196dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen SpillPlacement::BlockConstraint &BC = SplitConstraints[i]; 902874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen bool RegIn = LiveBundles[Bundles->getBundle(BC.Number, 0)]; 903874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen bool RegOut = LiveBundles[Bundles->getBundle(BC.Number, 1)]; 904874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen unsigned Ins = 0; 905874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen 906db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen if (BI.LiveIn) 907db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen Ins += RegIn != (BC.Entry == SpillPlacement::PrefReg); 908db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen if (BI.LiveOut) 909db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen Ins += RegOut != (BC.Exit == SpillPlacement::PrefReg); 910874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen if (Ins) 911874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen GlobalCost += Ins * SpillPlacer->getBlockFrequency(BC.Number); 912b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen } 913db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen 9145db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen for (unsigned i = 0, e = Cand.ActiveBlocks.size(); i != e; ++i) { 9155db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen unsigned Number = Cand.ActiveBlocks[i]; 916db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen bool RegIn = LiveBundles[Bundles->getBundle(Number, 0)]; 917db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen bool RegOut = LiveBundles[Bundles->getBundle(Number, 1)]; 9189a54352879e5aaac2e2c37490e5cb7844550db8bJakob Stoklund Olesen if (!RegIn && !RegOut) 9199a54352879e5aaac2e2c37490e5cb7844550db8bJakob Stoklund Olesen continue; 9209a54352879e5aaac2e2c37490e5cb7844550db8bJakob Stoklund Olesen if (RegIn && RegOut) { 9219a54352879e5aaac2e2c37490e5cb7844550db8bJakob Stoklund Olesen // We need double spill code if this block has interference. 922c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen Cand.Intf.moveToBlock(Number); 923c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen if (Cand.Intf.hasInterference()) 9249a54352879e5aaac2e2c37490e5cb7844550db8bJakob Stoklund Olesen GlobalCost += 2*SpillPlacer->getBlockFrequency(Number); 9259a54352879e5aaac2e2c37490e5cb7844550db8bJakob Stoklund Olesen continue; 9269a54352879e5aaac2e2c37490e5cb7844550db8bJakob Stoklund Olesen } 9279a54352879e5aaac2e2c37490e5cb7844550db8bJakob Stoklund Olesen // live-in / stack-out or stack-in live-out. 9289a54352879e5aaac2e2c37490e5cb7844550db8bJakob Stoklund Olesen GlobalCost += SpillPlacer->getBlockFrequency(Number); 929db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen } 930b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen return GlobalCost; 931b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen} 932b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 93300005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen/// splitAroundRegion - Split the current live range around the regions 93400005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen/// determined by BundleCand and GlobalCand. 935ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen/// 93600005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen/// Before calling this function, GlobalCand and BundleCand must be initialized 93700005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen/// so each bundle is assigned to a valid candidate, or NoCand for the 93800005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen/// stack-bound bundles. The shared SA/SE SplitAnalysis and SplitEditor 93900005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen/// objects must be initialized for the current live range, and intervals 94000005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen/// created for the used candidates. 941ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen/// 94200005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen/// @param LREdit The LiveRangeEdit object handling the current split. 94300005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen/// @param UsedCands List of used GlobalCand entries. Every BundleCand value 94400005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen/// must appear in this list. 94500005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesenvoid RAGreedy::splitAroundRegion(LiveRangeEdit &LREdit, 94600005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen ArrayRef<unsigned> UsedCands) { 94700005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // These are the intervals created for new global ranges. We may create more 94800005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // intervals for local ranges. 94900005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen const unsigned NumGlobalIntvs = LREdit.size(); 95000005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen DEBUG(dbgs() << "splitAroundRegion with " << NumGlobalIntvs << " globals.\n"); 95100005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen assert(NumGlobalIntvs && "No global intervals configured"); 952ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 9532d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen // Isolate even single instructions when dealing with a proper sub-class. 95469145baf36219b07a49d8ce14b4a04870e72a123Jakob Stoklund Olesen // That guarantees register class inflation for the stack interval because it 9552d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen // is all copies. 9562d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen unsigned Reg = SA->getParent().reg; 9572d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen bool SingleInstrs = RegClassInfo.isProperSubClass(MRI->getRegClass(Reg)); 9582d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen 95987360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen // First handle all the blocks with uses. 960db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks(); 961db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen for (unsigned i = 0; i != UseBlocks.size(); ++i) { 962db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen const SplitAnalysis::BlockInfo &BI = UseBlocks[i]; 96300005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen unsigned Number = BI.MBB->getNumber(); 96400005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen unsigned IntvIn = 0, IntvOut = 0; 96500005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen SlotIndex IntfIn, IntfOut; 96600005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen if (BI.LiveIn) { 96700005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen unsigned CandIn = BundleCand[Bundles->getBundle(Number, 0)]; 96800005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen if (CandIn != NoCand) { 96900005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen GlobalSplitCandidate &Cand = GlobalCand[CandIn]; 97000005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen IntvIn = Cand.IntvIdx; 97100005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen Cand.Intf.moveToBlock(Number); 97200005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen IntfIn = Cand.Intf.first(); 97300005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen } 97400005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen } 97500005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen if (BI.LiveOut) { 97600005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen unsigned CandOut = BundleCand[Bundles->getBundle(Number, 1)]; 97700005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen if (CandOut != NoCand) { 97800005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen GlobalSplitCandidate &Cand = GlobalCand[CandOut]; 97900005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen IntvOut = Cand.IntvIdx; 98000005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen Cand.Intf.moveToBlock(Number); 98100005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen IntfOut = Cand.Intf.last(); 98200005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen } 98300005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen } 984ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 985fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen // Create separate intervals for isolated blocks with multiple uses. 98600005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen if (!IntvIn && !IntvOut) { 987fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " isolated.\n"); 9882d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen if (SA->shouldSplitSingleBlock(BI, SingleInstrs)) 98987360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen SE->splitSingleBlock(BI); 990fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen continue; 991fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen } 992fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen 99300005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen if (IntvIn && IntvOut) 99400005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen SE->splitLiveThroughBlock(Number, IntvIn, IntfIn, IntvOut, IntfOut); 99500005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen else if (IntvIn) 99600005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen SE->splitRegInBlock(BI, IntvIn, IntfIn); 997b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen else 99800005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen SE->splitRegOutBlock(BI, IntvOut, IntfOut); 999ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen } 1000ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 100100005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // Handle live-through blocks. The relevant live-through blocks are stored in 100200005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // the ActiveBlocks list with each candidate. We need to filter out 100300005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // duplicates. 100400005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen BitVector Todo = SA->getThroughBlocks(); 100500005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen for (unsigned c = 0; c != UsedCands.size(); ++c) { 100600005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen ArrayRef<unsigned> Blocks = GlobalCand[UsedCands[c]].ActiveBlocks; 100700005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen for (unsigned i = 0, e = Blocks.size(); i != e; ++i) { 100800005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen unsigned Number = Blocks[i]; 100900005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen if (!Todo.test(Number)) 101000005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen continue; 101100005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen Todo.reset(Number); 101200005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen 101300005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen unsigned IntvIn = 0, IntvOut = 0; 101400005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen SlotIndex IntfIn, IntfOut; 101500005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen 101600005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen unsigned CandIn = BundleCand[Bundles->getBundle(Number, 0)]; 101700005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen if (CandIn != NoCand) { 101800005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen GlobalSplitCandidate &Cand = GlobalCand[CandIn]; 101900005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen IntvIn = Cand.IntvIdx; 102000005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen Cand.Intf.moveToBlock(Number); 102100005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen IntfIn = Cand.Intf.first(); 102200005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen } 102300005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen 102400005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen unsigned CandOut = BundleCand[Bundles->getBundle(Number, 1)]; 102500005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen if (CandOut != NoCand) { 102600005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen GlobalSplitCandidate &Cand = GlobalCand[CandOut]; 102700005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen IntvOut = Cand.IntvIdx; 102800005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen Cand.Intf.moveToBlock(Number); 102900005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen IntfOut = Cand.Intf.last(); 103000005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen } 103100005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen if (!IntvIn && !IntvOut) 103200005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen continue; 103300005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen SE->splitLiveThroughBlock(Number, IntvIn, IntfIn, IntvOut, IntfOut); 103400005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen } 1035db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen } 1036db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen 10370db841f9c2b9a25fb5ecb36e350d3a802c35654cJakob Stoklund Olesen ++NumGlobalSplits; 1038ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 10395928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen SmallVector<unsigned, 8> IntvMap; 10405928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen SE->finish(&IntvMap); 10411f8804263ffc5e6843d81f5c7bd9c739aa90fde5Jakob Stoklund Olesen DebugVars->splitRegister(Reg, LREdit.regs()); 1042f42b66169d75301346e3685fd2b3e45e47806367Jakob Stoklund Olesen 10431a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen ExtraRegInfo.resize(MRI->getNumVirtRegs()); 1044b2abfa0bf30edf292a27a06e091d03983e644c9bJakob Stoklund Olesen unsigned OrigBlocks = SA->getNumLiveBlocks(); 10455928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen 10465928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen // Sort out the new intervals created by splitting. We get four kinds: 10475928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen // - Remainder intervals should not be split again. 10485928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen // - Candidate intervals can be assigned to Cand.PhysReg. 10495928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen // - Block-local splits are candidates for local splitting. 10505928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen // - DCE leftovers should go back on the queue. 10515928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen for (unsigned i = 0, e = LREdit.size(); i != e; ++i) { 10521a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen LiveInterval &Reg = *LREdit.get(i); 10535928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen 10545928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen // Ignore old intervals from DCE. 10551a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen if (getStage(Reg) != RS_New) 10565928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen continue; 10575928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen 10585928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen // Remainder interval. Don't try splitting again, spill if it doesn't 10595928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen // allocate. 10605928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen if (IntvMap[i] == 0) { 1061fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen setStage(Reg, RS_Spill); 10625928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen continue; 10635928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen } 10645928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen 106500005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // Global intervals. Allow repeated splitting as long as the number of live 106600005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // blocks is strictly decreasing. 106700005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen if (IntvMap[i] < NumGlobalIntvs) { 10681a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen if (SA->countLiveBlocks(&Reg) >= OrigBlocks) { 10699f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen DEBUG(dbgs() << "Main interval covers the same " << OrigBlocks 10709f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen << " blocks as original.\n"); 10719f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen // Don't allow repeated splitting as a safe guard against looping. 107249743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen setStage(Reg, RS_Split2); 10739f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen } 10749f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen continue; 10759f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen } 10769f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen 10779f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen // Other intervals are treated as new. This includes local intervals created 10789f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen // for blocks with multiple uses, and anything created by DCE. 10795928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen } 10805928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen 1081eb29157d80847c207b77910bcd40a6a6c91ca5c5Jakob Stoklund Olesen if (VerifyEnabled) 1082ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen MF->verify(this, "After splitting live range around region"); 1083ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen} 1084ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 1085b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesenunsigned RAGreedy::tryRegionSplit(LiveInterval &VirtReg, AllocationOrder &Order, 1086b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen SmallVectorImpl<LiveInterval*> &NewVRegs) { 1087c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen unsigned NumCands = 0; 108800005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen unsigned BestCand = NoCand; 108900005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen float BestCost; 109000005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen SmallVector<unsigned, 8> UsedCands; 109100005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen 109200005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // Check if we can split this live range around a compact region. 1093a16a25ddeaf495b78b04e2a19feeac00d9824e63Jakob Stoklund Olesen bool HasCompact = calcCompactRegion(GlobalCand.front()); 109400005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen if (HasCompact) { 109500005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // Yes, keep GlobalCand[0] as the compact region candidate. 109600005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen NumCands = 1; 109700005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen BestCost = HUGE_VALF; 109800005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen } else { 109900005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // No benefit from the compact region, our fallback will be per-block 110000005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // splitting. Make sure we find a solution that is cheaper than spilling. 110100005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen BestCost = Hysteresis * calcSpillCost(); 110200005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen DEBUG(dbgs() << "Cost of isolating all blocks = " << BestCost << '\n'); 110300005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen } 110496dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen 1105b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen Order.rewind(); 1106c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen while (unsigned PhysReg = Order.next()) { 1107f1c709837bd11c5383fce3b8a026a7c8eaabba86Jakob Stoklund Olesen // Discard bad candidates before we run out of interference cache cursors. 1108f1c709837bd11c5383fce3b8a026a7c8eaabba86Jakob Stoklund Olesen // This will only affect register classes with a lot of registers (>32). 1109f1c709837bd11c5383fce3b8a026a7c8eaabba86Jakob Stoklund Olesen if (NumCands == IntfCache.getMaxCursors()) { 1110f1c709837bd11c5383fce3b8a026a7c8eaabba86Jakob Stoklund Olesen unsigned WorstCount = ~0u; 1111f1c709837bd11c5383fce3b8a026a7c8eaabba86Jakob Stoklund Olesen unsigned Worst = 0; 1112f1c709837bd11c5383fce3b8a026a7c8eaabba86Jakob Stoklund Olesen for (unsigned i = 0; i != NumCands; ++i) { 111300005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen if (i == BestCand || !GlobalCand[i].PhysReg) 1114f1c709837bd11c5383fce3b8a026a7c8eaabba86Jakob Stoklund Olesen continue; 1115f1c709837bd11c5383fce3b8a026a7c8eaabba86Jakob Stoklund Olesen unsigned Count = GlobalCand[i].LiveBundles.count(); 1116f1c709837bd11c5383fce3b8a026a7c8eaabba86Jakob Stoklund Olesen if (Count < WorstCount) 1117f1c709837bd11c5383fce3b8a026a7c8eaabba86Jakob Stoklund Olesen Worst = i, WorstCount = Count; 1118f1c709837bd11c5383fce3b8a026a7c8eaabba86Jakob Stoklund Olesen } 1119f1c709837bd11c5383fce3b8a026a7c8eaabba86Jakob Stoklund Olesen --NumCands; 1120f1c709837bd11c5383fce3b8a026a7c8eaabba86Jakob Stoklund Olesen GlobalCand[Worst] = GlobalCand[NumCands]; 1121f1c709837bd11c5383fce3b8a026a7c8eaabba86Jakob Stoklund Olesen } 1122f1c709837bd11c5383fce3b8a026a7c8eaabba86Jakob Stoklund Olesen 1123c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen if (GlobalCand.size() <= NumCands) 1124c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen GlobalCand.resize(NumCands+1); 1125c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen GlobalSplitCandidate &Cand = GlobalCand[NumCands]; 1126c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen Cand.reset(IntfCache, PhysReg); 112796dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen 1128c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen SpillPlacer->prepare(Cand.LiveBundles); 11291b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen float Cost; 1130c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen if (!addSplitConstraints(Cand.Intf, Cost)) { 1131f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen DEBUG(dbgs() << PrintReg(PhysReg, TRI) << "\tno positive bundles\n"); 11321b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen continue; 11331b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen } 1134f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen DEBUG(dbgs() << PrintReg(PhysReg, TRI) << "\tstatic = " << Cost); 1135200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen if (Cost >= BestCost) { 1136200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen DEBUG({ 1137200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen if (BestCand == NoCand) 1138200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen dbgs() << " worse than no bundles\n"; 1139200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen else 1140200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen dbgs() << " worse than " 1141200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen << PrintReg(GlobalCand[BestCand].PhysReg, TRI) << '\n'; 1142200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen }); 1143b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen continue; 1144874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen } 1145c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen growRegion(Cand); 1146ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 11479efa2a263ea470caacef1c85f6ca45e32bf516d3Jakob Stoklund Olesen SpillPlacer->finish(); 11489efa2a263ea470caacef1c85f6ca45e32bf516d3Jakob Stoklund Olesen 1149ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // No live bundles, defer to splitSingleBlocks(). 1150c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen if (!Cand.LiveBundles.any()) { 1151874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen DEBUG(dbgs() << " no bundles.\n"); 1152ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen continue; 1153874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen } 1154ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 1155c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen Cost += calcGlobalSplitCost(Cand); 1156874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen DEBUG({ 1157874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen dbgs() << ", total = " << Cost << " with bundles"; 1158c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen for (int i = Cand.LiveBundles.find_first(); i>=0; 1159c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen i = Cand.LiveBundles.find_next(i)) 1160874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen dbgs() << " EB#" << i; 1161874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen dbgs() << ".\n"; 1162874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen }); 1163200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen if (Cost < BestCost) { 1164c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen BestCand = NumCands; 1165200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen BestCost = Hysteresis * Cost; // Prevent rounding effects. 1166b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen } 1167c66a37df73f70ec3dbed06277763624f33ee3512Jakob Stoklund Olesen ++NumCands; 1168b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen } 1169ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 117000005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // No solutions found, fall back to single block splitting. 117100005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen if (!HasCompact && BestCand == NoCand) 1172ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen return 0; 1173ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 117400005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // Prepare split editor. 117500005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen LiveRangeEdit LREdit(VirtReg, NewVRegs, this); 1176708d06f7fb5dfd9c8559aea07b042a88c65645f8Jakob Stoklund Olesen SE->reset(LREdit, SplitSpillMode); 117700005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen 117800005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // Assign all edge bundles to the preferred candidate, or NoCand. 117900005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen BundleCand.assign(Bundles->getNumBundles(), NoCand); 118000005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen 118100005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // Assign bundles for the best candidate region. 118200005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen if (BestCand != NoCand) { 118300005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen GlobalSplitCandidate &Cand = GlobalCand[BestCand]; 118400005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen if (unsigned B = Cand.getBundles(BundleCand, BestCand)) { 118500005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen UsedCands.push_back(BestCand); 118600005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen Cand.IntvIdx = SE->openIntv(); 118700005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen DEBUG(dbgs() << "Split for " << PrintReg(Cand.PhysReg, TRI) << " in " 118800005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen << B << " bundles, intv " << Cand.IntvIdx << ".\n"); 118932668ea7a290ee1cb6bfe8cd677cdd4e5df05b4dChandler Carruth (void)B; 119000005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen } 119100005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen } 119200005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen 119300005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen // Assign bundles for the compact region. 119400005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen if (HasCompact) { 119500005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen GlobalSplitCandidate &Cand = GlobalCand.front(); 119600005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen assert(!Cand.PhysReg && "Compact region has no physreg"); 119700005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen if (unsigned B = Cand.getBundles(BundleCand, 0)) { 119800005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen UsedCands.push_back(0); 119900005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen Cand.IntvIdx = SE->openIntv(); 120000005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen DEBUG(dbgs() << "Split for compact region in " << B << " bundles, intv " 120100005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen << Cand.IntvIdx << ".\n"); 120232668ea7a290ee1cb6bfe8cd677cdd4e5df05b4dChandler Carruth (void)B; 120300005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen } 120400005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen } 120500005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen 120600005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen splitAroundRegion(LREdit, UsedCands); 1207b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen return 0; 1208b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen} 1209b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 1210ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 1211ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen//===----------------------------------------------------------------------===// 1212dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen// Per-Block Splitting 1213dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen//===----------------------------------------------------------------------===// 1214dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen 1215dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen/// tryBlockSplit - Split a global live range around every block with uses. This 1216dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen/// creates a lot of local live ranges, that will be split by tryLocalSplit if 1217dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen/// they don't allocate. 1218dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesenunsigned RAGreedy::tryBlockSplit(LiveInterval &VirtReg, AllocationOrder &Order, 1219dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen SmallVectorImpl<LiveInterval*> &NewVRegs) { 1220dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen assert(&SA->getParent() == &VirtReg && "Live range wasn't analyzed"); 1221dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen unsigned Reg = VirtReg.reg; 1222dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen bool SingleInstrs = RegClassInfo.isProperSubClass(MRI->getRegClass(Reg)); 1223dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen LiveRangeEdit LREdit(VirtReg, NewVRegs, this); 1224708d06f7fb5dfd9c8559aea07b042a88c65645f8Jakob Stoklund Olesen SE->reset(LREdit, SplitSpillMode); 1225dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks(); 1226dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen for (unsigned i = 0; i != UseBlocks.size(); ++i) { 1227dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen const SplitAnalysis::BlockInfo &BI = UseBlocks[i]; 1228dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen if (SA->shouldSplitSingleBlock(BI, SingleInstrs)) 1229dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen SE->splitSingleBlock(BI); 1230dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen } 1231dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen // No blocks were split. 1232dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen if (LREdit.empty()) 1233dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen return 0; 1234dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen 1235dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen // We did split for some blocks. 1236a9c41d39d1adc92107e095aca6f851aed71b6a5fJakob Stoklund Olesen SmallVector<unsigned, 8> IntvMap; 1237a9c41d39d1adc92107e095aca6f851aed71b6a5fJakob Stoklund Olesen SE->finish(&IntvMap); 12381f8804263ffc5e6843d81f5c7bd9c739aa90fde5Jakob Stoklund Olesen 12391f8804263ffc5e6843d81f5c7bd9c739aa90fde5Jakob Stoklund Olesen // Tell LiveDebugVariables about the new ranges. 12401f8804263ffc5e6843d81f5c7bd9c739aa90fde5Jakob Stoklund Olesen DebugVars->splitRegister(Reg, LREdit.regs()); 12411f8804263ffc5e6843d81f5c7bd9c739aa90fde5Jakob Stoklund Olesen 1242a9c41d39d1adc92107e095aca6f851aed71b6a5fJakob Stoklund Olesen ExtraRegInfo.resize(MRI->getNumVirtRegs()); 1243a9c41d39d1adc92107e095aca6f851aed71b6a5fJakob Stoklund Olesen 1244a9c41d39d1adc92107e095aca6f851aed71b6a5fJakob Stoklund Olesen // Sort out the new intervals created by splitting. The remainder interval 1245a9c41d39d1adc92107e095aca6f851aed71b6a5fJakob Stoklund Olesen // goes straight to spilling, the new local ranges get to stay RS_New. 1246a9c41d39d1adc92107e095aca6f851aed71b6a5fJakob Stoklund Olesen for (unsigned i = 0, e = LREdit.size(); i != e; ++i) { 1247a9c41d39d1adc92107e095aca6f851aed71b6a5fJakob Stoklund Olesen LiveInterval &LI = *LREdit.get(i); 1248a9c41d39d1adc92107e095aca6f851aed71b6a5fJakob Stoklund Olesen if (getStage(LI) == RS_New && IntvMap[i] == 0) 1249a9c41d39d1adc92107e095aca6f851aed71b6a5fJakob Stoklund Olesen setStage(LI, RS_Spill); 1250a9c41d39d1adc92107e095aca6f851aed71b6a5fJakob Stoklund Olesen } 1251a9c41d39d1adc92107e095aca6f851aed71b6a5fJakob Stoklund Olesen 1252dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen if (VerifyEnabled) 1253dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen MF->verify(this, "After splitting live range around basic blocks"); 1254dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen return 0; 1255dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen} 1256dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen 1257dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen//===----------------------------------------------------------------------===// 1258034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen// Local Splitting 1259034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 1260034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1261034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1262034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// calcGapWeights - Compute the maximum spill weight that needs to be evicted 1263034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// in order to use PhysReg between two entries in SA->UseSlots. 1264034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// 1265034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// GapWeight[i] represents the gap between UseSlots[i] and UseSlots[i+1]. 1266034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// 1267034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesenvoid RAGreedy::calcGapWeights(unsigned PhysReg, 1268034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen SmallVectorImpl<float> &GapWeight) { 1269db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen assert(SA->getUseBlocks().size() == 1 && "Not a local interval"); 1270db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen const SplitAnalysis::BlockInfo &BI = SA->getUseBlocks().front(); 1271034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const SmallVectorImpl<SlotIndex> &Uses = SA->UseSlots; 1272034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const unsigned NumGaps = Uses.size()-1; 1273034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1274034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Start and end points for the interference check. 1275fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen SlotIndex StartIdx = 1276fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen BI.LiveIn ? BI.FirstInstr.getBaseIndex() : BI.FirstInstr; 1277fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen SlotIndex StopIdx = 1278fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen BI.LiveOut ? BI.LastInstr.getBoundaryIndex() : BI.LastInstr; 1279034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1280034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen GapWeight.assign(NumGaps, 0.0f); 1281034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1282034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Add interference from each overlapping register. 1283034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen for (const unsigned *AI = TRI->getOverlaps(PhysReg); *AI; ++AI) { 1284034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (!query(const_cast<LiveInterval&>(SA->getParent()), *AI) 1285034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen .checkInterference()) 1286034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen continue; 1287034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1288fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen // We know that VirtReg is a continuous interval from FirstInstr to 1289fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen // LastInstr, so we don't need InterferenceQuery. 1290034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // 1291034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Interference that overlaps an instruction is counted in both gaps 1292034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // surrounding the instruction. The exception is interference before 1293034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // StartIdx and after StopIdx. 1294034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // 1295034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen LiveIntervalUnion::SegmentIter IntI = PhysReg2LiveUnion[*AI].find(StartIdx); 1296034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen for (unsigned Gap = 0; IntI.valid() && IntI.start() < StopIdx; ++IntI) { 1297034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Skip the gaps before IntI. 1298034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen while (Uses[Gap+1].getBoundaryIndex() < IntI.start()) 1299034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (++Gap == NumGaps) 1300034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen break; 1301034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (Gap == NumGaps) 1302034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen break; 1303034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1304034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Update the gaps covered by IntI. 1305034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const float weight = IntI.value()->weight; 1306034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen for (; Gap != NumGaps; ++Gap) { 1307034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen GapWeight[Gap] = std::max(GapWeight[Gap], weight); 1308034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (Uses[Gap+1].getBaseIndex() >= IntI.stop()) 1309034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen break; 1310034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1311034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (Gap == NumGaps) 1312034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen break; 1313034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1314034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1315034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen} 1316034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1317034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// tryLocalSplit - Try to split VirtReg into smaller intervals inside its only 1318034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// basic block. 1319034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// 1320034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesenunsigned RAGreedy::tryLocalSplit(LiveInterval &VirtReg, AllocationOrder &Order, 1321034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen SmallVectorImpl<LiveInterval*> &NewVRegs) { 1322db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen assert(SA->getUseBlocks().size() == 1 && "Not a local interval"); 1323db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen const SplitAnalysis::BlockInfo &BI = SA->getUseBlocks().front(); 1324034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1325034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Note that it is possible to have an interval that is live-in or live-out 1326034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // while only covering a single block - A phi-def can use undef values from 1327034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // predecessors, and the block could be a single-block loop. 1328034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // We don't bother doing anything clever about such a case, we simply assume 1329fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen // that the interval is continuous from FirstInstr to LastInstr. We should 1330fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen // make sure that we don't do anything illegal to such an interval, though. 1331034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1332034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const SmallVectorImpl<SlotIndex> &Uses = SA->UseSlots; 1333034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (Uses.size() <= 2) 1334034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen return 0; 1335034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const unsigned NumGaps = Uses.size()-1; 1336034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1337034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen DEBUG({ 1338034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen dbgs() << "tryLocalSplit: "; 1339034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen for (unsigned i = 0, e = Uses.size(); i != e; ++i) 1340034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen dbgs() << ' ' << SA->UseSlots[i]; 1341034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen dbgs() << '\n'; 1342034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen }); 1343034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1344b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // Since we allow local split results to be split again, there is a risk of 1345b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // creating infinite loops. It is tempting to require that the new live 1346b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // ranges have less instructions than the original. That would guarantee 1347b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // convergence, but it is too strict. A live range with 3 instructions can be 1348b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // split 2+3 (including the COPY), and we want to allow that. 1349b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // 1350b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // Instead we use these rules: 1351b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // 135249743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen // 1. Allow any split for ranges with getStage() < RS_Split2. (Except for the 1353b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // noop split, of course). 135449743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen // 2. Require progress be made for ranges with getStage() == RS_Split2. All 1355b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // the new ranges must have fewer instructions than before the split. 135649743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen // 3. New ranges with the same number of instructions are marked RS_Split2, 1357b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // smaller ranges are marked RS_New. 1358b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // 1359b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // These rules allow a 3 -> 2+3 split once, which we need. They also prevent 1360b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // excessive splitting and infinite loops. 1361b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // 136249743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen bool ProgressRequired = getStage(VirtReg) >= RS_Split2; 1363034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1364b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // Best split candidate. 1365034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen unsigned BestBefore = NumGaps; 1366034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen unsigned BestAfter = 0; 1367034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen float BestDiff = 0; 1368034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 136940a42a2ccaaa19a109667ed7abf224cc8733cd9cJakob Stoklund Olesen const float blockFreq = SpillPlacer->getBlockFrequency(BI.MBB->getNumber()); 1370034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen SmallVector<float, 8> GapWeight; 1371034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1372034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen Order.rewind(); 1373034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen while (unsigned PhysReg = Order.next()) { 1374034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Keep track of the largest spill weight that would need to be evicted in 1375034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // order to make use of PhysReg between UseSlots[i] and UseSlots[i+1]. 1376034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen calcGapWeights(PhysReg, GapWeight); 1377034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1378034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Try to find the best sequence of gaps to close. 1379034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // The new spill weight must be larger than any gap interference. 1380034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1381034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // We will split before Uses[SplitBefore] and after Uses[SplitAfter]. 1382b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen unsigned SplitBefore = 0, SplitAfter = 1; 1383034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1384034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // MaxGap should always be max(GapWeight[SplitBefore..SplitAfter-1]). 1385034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // It is the spill weight that needs to be evicted. 1386034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen float MaxGap = GapWeight[0]; 1387034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1388034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen for (;;) { 1389034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Live before/after split? 1390034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const bool LiveBefore = SplitBefore != 0 || BI.LiveIn; 1391034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const bool LiveAfter = SplitAfter != NumGaps || BI.LiveOut; 1392034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1393034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen DEBUG(dbgs() << PrintReg(PhysReg, TRI) << ' ' 1394034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen << Uses[SplitBefore] << '-' << Uses[SplitAfter] 1395034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen << " i=" << MaxGap); 1396034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1397034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Stop before the interval gets so big we wouldn't be making progress. 1398034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (!LiveBefore && !LiveAfter) { 1399034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen DEBUG(dbgs() << " all\n"); 1400034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen break; 1401034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1402034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Should the interval be extended or shrunk? 1403034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen bool Shrink = true; 1404034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1405b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // How many gaps would the new range have? 1406b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen unsigned NewGaps = LiveBefore + SplitAfter - SplitBefore + LiveAfter; 1407b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen 1408b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // Legally, without causing looping? 1409b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen bool Legal = !ProgressRequired || NewGaps < NumGaps; 1410b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen 1411b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen if (Legal && MaxGap < HUGE_VALF) { 1412b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // Estimate the new spill weight. Each instruction reads or writes the 1413b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // register. Conservatively assume there are no read-modify-write 1414b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // instructions. 1415034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // 1416b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // Try to guess the size of the new interval. 1417b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen const float EstWeight = normalizeSpillWeight(blockFreq * (NewGaps + 1), 1418b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen Uses[SplitBefore].distance(Uses[SplitAfter]) + 1419b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen (LiveBefore + LiveAfter)*SlotIndex::InstrDist); 1420034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Would this split be possible to allocate? 1421034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Never allocate all gaps, we wouldn't be making progress. 142266446c803a11a26e4bb39b74091d146ac850ae4cJakob Stoklund Olesen DEBUG(dbgs() << " w=" << EstWeight); 142366446c803a11a26e4bb39b74091d146ac850ae4cJakob Stoklund Olesen if (EstWeight * Hysteresis >= MaxGap) { 1424034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen Shrink = false; 142566446c803a11a26e4bb39b74091d146ac850ae4cJakob Stoklund Olesen float Diff = EstWeight - MaxGap; 1426034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (Diff > BestDiff) { 1427034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen DEBUG(dbgs() << " (best)"); 142866446c803a11a26e4bb39b74091d146ac850ae4cJakob Stoklund Olesen BestDiff = Hysteresis * Diff; 1429034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen BestBefore = SplitBefore; 1430034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen BestAfter = SplitAfter; 1431034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1432034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1433034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1434034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1435034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Try to shrink. 1436034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (Shrink) { 1437b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen if (++SplitBefore < SplitAfter) { 1438034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen DEBUG(dbgs() << " shrink\n"); 1439034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Recompute the max when necessary. 1440034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (GapWeight[SplitBefore - 1] >= MaxGap) { 1441034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen MaxGap = GapWeight[SplitBefore]; 1442034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen for (unsigned i = SplitBefore + 1; i != SplitAfter; ++i) 1443034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen MaxGap = std::max(MaxGap, GapWeight[i]); 1444034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1445034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen continue; 1446034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1447034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen MaxGap = 0; 1448034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1449034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1450034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Try to extend the interval. 1451034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (SplitAfter >= NumGaps) { 1452034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen DEBUG(dbgs() << " end\n"); 1453034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen break; 1454034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1455034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1456034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen DEBUG(dbgs() << " extend\n"); 1457b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen MaxGap = std::max(MaxGap, GapWeight[SplitAfter++]); 1458034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1459034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1460034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1461034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Didn't find any candidates? 1462034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (BestBefore == NumGaps) 1463034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen return 0; 1464034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1465034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen DEBUG(dbgs() << "Best local split range: " << Uses[BestBefore] 1466034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen << '-' << Uses[BestAfter] << ", " << BestDiff 1467034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen << ", " << (BestAfter - BestBefore + 1) << " instrs\n"); 1468034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 146992a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen LiveRangeEdit LREdit(VirtReg, NewVRegs, this); 1470bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen SE->reset(LREdit); 1471bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen 1472bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen SE->openIntv(); 1473bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen SlotIndex SegStart = SE->enterIntvBefore(Uses[BestBefore]); 1474bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen SlotIndex SegStop = SE->leaveIntvAfter(Uses[BestAfter]); 1475bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen SE->useIntv(SegStart, SegStop); 1476b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen SmallVector<unsigned, 8> IntvMap; 1477b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen SE->finish(&IntvMap); 1478f42b66169d75301346e3685fd2b3e45e47806367Jakob Stoklund Olesen DebugVars->splitRegister(VirtReg.reg, LREdit.regs()); 1479b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen 1480b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // If the new range has the same number of instructions as before, mark it as 148149743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen // RS_Split2 so the next split will be forced to make progress. Otherwise, 1482b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen // leave the new intervals as RS_New so they can compete. 1483b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen bool LiveBefore = BestBefore != 0 || BI.LiveIn; 1484b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen bool LiveAfter = BestAfter != NumGaps || BI.LiveOut; 1485b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen unsigned NewGaps = LiveBefore + BestAfter - BestBefore + LiveAfter; 1486b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen if (NewGaps >= NumGaps) { 1487b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen DEBUG(dbgs() << "Tagging non-progress ranges: "); 1488b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen assert(!ProgressRequired && "Didn't make progress when it was required."); 1489b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen for (unsigned i = 0, e = IntvMap.size(); i != e; ++i) 1490b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen if (IntvMap[i] == 1) { 149149743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen setStage(*LREdit.get(i), RS_Split2); 1492b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen DEBUG(dbgs() << PrintReg(LREdit.get(i)->reg)); 1493b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen } 1494b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen DEBUG(dbgs() << '\n'); 1495b3e705f88987608d4eb49668dac0e235d04df884Jakob Stoklund Olesen } 14960db841f9c2b9a25fb5ecb36e350d3a802c35654cJakob Stoklund Olesen ++NumLocalSplits; 1497034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1498034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen return 0; 1499034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen} 1500034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1501034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 1502ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen// Live Range Splitting 1503ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen//===----------------------------------------------------------------------===// 1504ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 1505ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen/// trySplit - Try to split VirtReg or one of its interferences, making it 1506ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen/// assignable. 1507ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen/// @return Physreg when VirtReg may be assigned and/or new NewVRegs. 1508ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesenunsigned RAGreedy::trySplit(LiveInterval &VirtReg, AllocationOrder &Order, 1509ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen SmallVectorImpl<LiveInterval*>&NewVRegs) { 1510ccfa446450c9e3e0b3591343c4c5bea1e4cdc043Jakob Stoklund Olesen // Ranges must be Split2 or less. 1511ccfa446450c9e3e0b3591343c4c5bea1e4cdc043Jakob Stoklund Olesen if (getStage(VirtReg) >= RS_Spill) 1512ccfa446450c9e3e0b3591343c4c5bea1e4cdc043Jakob Stoklund Olesen return 0; 1513ccfa446450c9e3e0b3591343c4c5bea1e4cdc043Jakob Stoklund Olesen 1514034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Local intervals are handled separately. 1515a2ebf60ef2c434428af7f810b13327ab50245a67Jakob Stoklund Olesen if (LIS->intervalIsInOneMBB(VirtReg)) { 1516a2ebf60ef2c434428af7f810b13327ab50245a67Jakob Stoklund Olesen NamedRegionTimer T("Local Splitting", TimerGroupName, TimePassesIsEnabled); 151722a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen SA->analyze(&VirtReg); 1518034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen return tryLocalSplit(VirtReg, Order, NewVRegs); 1519a2ebf60ef2c434428af7f810b13327ab50245a67Jakob Stoklund Olesen } 1520a2ebf60ef2c434428af7f810b13327ab50245a67Jakob Stoklund Olesen 1521a2ebf60ef2c434428af7f810b13327ab50245a67Jakob Stoklund Olesen NamedRegionTimer T("Global Splitting", TimerGroupName, TimePassesIsEnabled); 1522ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 152322a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen SA->analyze(&VirtReg); 152422a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen 15257d6b6a05b549da70b4473f015c97954c2a422724Jakob Stoklund Olesen // FIXME: SplitAnalysis may repair broken live ranges coming from the 15267d6b6a05b549da70b4473f015c97954c2a422724Jakob Stoklund Olesen // coalescer. That may cause the range to become allocatable which means that 15277d6b6a05b549da70b4473f015c97954c2a422724Jakob Stoklund Olesen // tryRegionSplit won't be making progress. This check should be replaced with 15287d6b6a05b549da70b4473f015c97954c2a422724Jakob Stoklund Olesen // an assertion when the coalescer is fixed. 15297d6b6a05b549da70b4473f015c97954c2a422724Jakob Stoklund Olesen if (SA->didRepairRange()) { 15307d6b6a05b549da70b4473f015c97954c2a422724Jakob Stoklund Olesen // VirtReg has changed, so all cached queries are invalid. 1531bdda37d7fbafe6876f248341837423a4100f95a5Jakob Stoklund Olesen invalidateVirtRegs(); 15327d6b6a05b549da70b4473f015c97954c2a422724Jakob Stoklund Olesen if (unsigned PhysReg = tryAssign(VirtReg, Order, NewVRegs)) 15337d6b6a05b549da70b4473f015c97954c2a422724Jakob Stoklund Olesen return PhysReg; 15347d6b6a05b549da70b4473f015c97954c2a422724Jakob Stoklund Olesen } 15357d6b6a05b549da70b4473f015c97954c2a422724Jakob Stoklund Olesen 153649743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen // First try to split around a region spanning multiple blocks. RS_Split2 153749743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen // ranges already made dubious progress with region splitting, so they go 153849743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen // straight to single block splitting. 153949743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen if (getStage(VirtReg) < RS_Split2) { 154049743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen unsigned PhysReg = tryRegionSplit(VirtReg, Order, NewVRegs); 154149743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen if (PhysReg || !NewVRegs.empty()) 154249743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen return PhysReg; 154349743b18f50ac0f7e065f4754a26965d4db388deJakob Stoklund Olesen } 1544ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 1545dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen // Then isolate blocks. 1546dab35d33ae17353cb01aaaa42abbcb28b33eb98aJakob Stoklund Olesen return tryBlockSplit(VirtReg, Order, NewVRegs); 1547ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen} 1548ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 1549ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 1550b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen//===----------------------------------------------------------------------===// 1551770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen// Main Entry Point 1552770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen//===----------------------------------------------------------------------===// 1553770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen 1554770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesenunsigned RAGreedy::selectOrSplit(LiveInterval &VirtReg, 1555ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen SmallVectorImpl<LiveInterval*> &NewVRegs) { 1556770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen // First try assigning a free register. 15575f2316a3b55f88dab2190212210770180a32aa95Jakob Stoklund Olesen AllocationOrder Order(VirtReg.reg, *VRM, RegClassInfo); 15586bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen if (unsigned PhysReg = tryAssign(VirtReg, Order, NewVRegs)) 15596bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen return PhysReg; 1560b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick 1561b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen LiveRangeStage Stage = getStage(VirtReg); 15621a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen DEBUG(dbgs() << StageName[Stage] 15631a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen << " Cascade " << ExtraRegInfo[VirtReg.reg].Cascade << '\n'); 1564b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen 156576395c9a31444fa86514473e0852cdd67752d0e8Jakob Stoklund Olesen // Try to evict a less worthy live range, but only for ranges from the primary 1566fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen // queue. The RS_Split ranges already failed to do this, and they should not 156776395c9a31444fa86514473e0852cdd67752d0e8Jakob Stoklund Olesen // get a second chance until they have been split. 1568fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen if (Stage != RS_Split) 156976395c9a31444fa86514473e0852cdd67752d0e8Jakob Stoklund Olesen if (unsigned PhysReg = tryEvict(VirtReg, Order, NewVRegs)) 157076395c9a31444fa86514473e0852cdd67752d0e8Jakob Stoklund Olesen return PhysReg; 1571b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick 1572ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen assert(NewVRegs.empty() && "Cannot append to existing NewVRegs"); 1573ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 1574107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen // The first time we see a live range, don't try to split or spill. 1575107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen // Wait until the second time, when all smaller ranges have been allocated. 1576107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen // This gives a better picture of the interference to split around. 1577fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen if (Stage < RS_Split) { 1578fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen setStage(VirtReg, RS_Split); 1579c1655e1a3c3a566b91b0513b56d61b58da1e36baJakob Stoklund Olesen DEBUG(dbgs() << "wait for second round\n"); 1580107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen NewVRegs.push_back(&VirtReg); 1581107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen return 0; 1582107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen } 1583107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen 1584bf4e10f2f69db24c107cb61d6fe10ed5b2047374Jakob Stoklund Olesen // If we couldn't allocate a register from spilling, there is probably some 1585bf4e10f2f69db24c107cb61d6fe10ed5b2047374Jakob Stoklund Olesen // invalid inline assembly. The base class wil report it. 1586fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen if (Stage >= RS_Done || !VirtReg.isSpillable()) 1587bf4e10f2f69db24c107cb61d6fe10ed5b2047374Jakob Stoklund Olesen return ~0u; 158822a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen 158946c83c80c5737743c955ff007fa6409804a7abf0Jakob Stoklund Olesen // Try splitting VirtReg or interferences. 1590ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen unsigned PhysReg = trySplit(VirtReg, Order, NewVRegs); 1591ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen if (PhysReg || !NewVRegs.empty()) 1592b64d92e29f38002e52a22fe36ea2d488968e3537Jakob Stoklund Olesen return PhysReg; 1593b64d92e29f38002e52a22fe36ea2d488968e3537Jakob Stoklund Olesen 1594770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen // Finally spill VirtReg itself. 1595770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen NamedRegionTimer T("Spiller", TimerGroupName, TimePassesIsEnabled); 159647dbf6cef761c25cfeb0aa7d624a6f98288bb96aJakob Stoklund Olesen LiveRangeEdit LRE(VirtReg, NewVRegs, this); 159747dbf6cef761c25cfeb0aa7d624a6f98288bb96aJakob Stoklund Olesen spiller().spill(LRE); 1598fa89a0344bba7a0ae87d3de204d18bb1ecaa5955Jakob Stoklund Olesen setStage(NewVRegs.begin(), NewVRegs.end(), RS_Done); 1599cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 1600c46570dc05851395829bef904bb6ddb1260400d1Jakob Stoklund Olesen if (VerifyEnabled) 1601c46570dc05851395829bef904bb6ddb1260400d1Jakob Stoklund Olesen MF->verify(this, "After spilling"); 1602c46570dc05851395829bef904bb6ddb1260400d1Jakob Stoklund Olesen 1603cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen // The live virtual register requesting allocation was spilled, so tell 1604cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen // the caller not to allocate anything during this round. 1605cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen return 0; 1606cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen} 1607cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 1608cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesenbool RAGreedy::runOnMachineFunction(MachineFunction &mf) { 1609cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen DEBUG(dbgs() << "********** GREEDY REGISTER ALLOCATION **********\n" 1610cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen << "********** Function: " 1611cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen << ((Value*)mf.getFunction())->getName() << '\n'); 1612cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 1613cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen MF = &mf; 1614af24964251e27c2dd863239ba66ffd967b593be5Jakob Stoklund Olesen if (VerifyEnabled) 161589cab93fe999f6d81b4b99a71ac797b7ecfec277Jakob Stoklund Olesen MF->verify(this, "Before greedy register allocator"); 1616af24964251e27c2dd863239ba66ffd967b593be5Jakob Stoklund Olesen 16174680dec5fb3a1b624f13ca9b2a555ca90a07973eJakob Stoklund Olesen RegAllocBase::init(getAnalysis<VirtRegMap>(), getAnalysis<LiveIntervals>()); 1618b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen Indexes = &getAnalysis<SlotIndexes>(); 1619f428eb6c1b09a2322b7a577b0bf2e49dd107bceaJakob Stoklund Olesen DomTree = &getAnalysis<MachineDominatorTree>(); 1620f6dff84d4e44d6c4a46c4f8a18e13c78f804547cJakob Stoklund Olesen SpillerInstance.reset(createInlineSpiller(*this, *MF, *VRM)); 1621d0bb5e2ca05d9c942223bf05e5940bb0c6cc9d3fJakob Stoklund Olesen Loops = &getAnalysis<MachineLoopInfo>(); 1622b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen Bundles = &getAnalysis<EdgeBundles>(); 1623b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen SpillPlacer = &getAnalysis<SpillPlacement>(); 1624f42b66169d75301346e3685fd2b3e45e47806367Jakob Stoklund Olesen DebugVars = &getAnalysis<LiveDebugVariables>(); 1625b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 16261b847deb26b52051de39f4cbecd224c9fbd0d1c2Jakob Stoklund Olesen SA.reset(new SplitAnalysis(*VRM, *LIS, *Loops)); 1627bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen SE.reset(new SplitEditor(*SA, *LIS, *VRM, *DomTree)); 16281a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen ExtraRegInfo.clear(); 16291a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen ExtraRegInfo.resize(MRI->getNumVirtRegs()); 16301a988004dba412deb5d6b8e93b955dfc837065f0Jakob Stoklund Olesen NextCascade = 1; 1631eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen IntfCache.init(MF, &PhysReg2LiveUnion[0], Indexes, TRI); 163200005782fa860f4b48b3b5261d92541c61ee2495Jakob Stoklund Olesen GlobalCand.resize(32); // This will grow as needed. 1633d0bb5e2ca05d9c942223bf05e5940bb0c6cc9d3fJakob Stoklund Olesen 1634cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen allocatePhysRegs(); 1635cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen addMBBLiveIns(MF); 16368a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen LIS->addKillFlags(); 1637cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 1638cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen // Run rewriter 1639533f58ecdd8a4732c2f0e149387c4d8d8d4142deJakob Stoklund Olesen { 1640533f58ecdd8a4732c2f0e149387c4d8d8d4142deJakob Stoklund Olesen NamedRegionTimer T("Rewriter", TimerGroupName, TimePassesIsEnabled); 1641ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen VRM->rewrite(Indexes); 1642533f58ecdd8a4732c2f0e149387c4d8d8d4142deJakob Stoklund Olesen } 1643cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 1644cfafc54040cc9722995558124f253d05a038176bJakob Stoklund Olesen // Write out new DBG_VALUE instructions. 1645c47690264abd6ec6bdeab86ce057e99bb5d39fe4Jakob Stoklund Olesen { 1646c47690264abd6ec6bdeab86ce057e99bb5d39fe4Jakob Stoklund Olesen NamedRegionTimer T("Emit Debug Info", TimerGroupName, TimePassesIsEnabled); 1647c47690264abd6ec6bdeab86ce057e99bb5d39fe4Jakob Stoklund Olesen DebugVars->emitDebugValues(VRM); 1648c47690264abd6ec6bdeab86ce057e99bb5d39fe4Jakob Stoklund Olesen } 1649cfafc54040cc9722995558124f253d05a038176bJakob Stoklund Olesen 1650cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen // The pass output is in VirtRegMap. Release all the transient data. 1651cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen releaseMemory(); 1652cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 1653cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen return true; 1654cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen} 1655