RegAllocGreedy.cpp revision 5f2316a3b55f88dab2190212210770180a32aa95
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" 36d0bb5e2ca05d9c942223bf05e5940bb0c6cc9d3fJakob Stoklund Olesen#include "llvm/CodeGen/MachineLoopRanges.h" 37cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "llvm/CodeGen/MachineRegisterInfo.h" 38cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "llvm/CodeGen/Passes.h" 39cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "llvm/CodeGen/RegAllocRegistry.h" 40cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "llvm/CodeGen/RegisterCoalescer.h" 41cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "llvm/Target/TargetOptions.h" 42cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "llvm/Support/Debug.h" 43cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "llvm/Support/ErrorHandling.h" 44cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "llvm/Support/raw_ostream.h" 45533f58ecdd8a4732c2f0e149387c4d8d8d4142deJakob Stoklund Olesen#include "llvm/Support/Timer.h" 46cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 4798d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen#include <queue> 4898d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen 49cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesenusing namespace llvm; 50cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 510db841f9c2b9a25fb5ecb36e350d3a802c35654cJakob Stoklund OlesenSTATISTIC(NumGlobalSplits, "Number of split global live ranges"); 520db841f9c2b9a25fb5ecb36e350d3a802c35654cJakob Stoklund OlesenSTATISTIC(NumLocalSplits, "Number of split local live ranges"); 530db841f9c2b9a25fb5ecb36e350d3a802c35654cJakob Stoklund OlesenSTATISTIC(NumEvicted, "Number of interferences evicted"); 540db841f9c2b9a25fb5ecb36e350d3a802c35654cJakob Stoklund Olesen 55cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesenstatic RegisterRegAlloc greedyRegAlloc("greedy", "greedy register allocator", 56cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen createGreedyRegisterAllocator); 57cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 58cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesennamespace { 5992a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesenclass RAGreedy : public MachineFunctionPass, 6092a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen public RegAllocBase, 6192a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen private LiveRangeEdit::Delegate { 6292a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen 63cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen // context 64cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen MachineFunction *MF; 65cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 66cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen // analyses 67b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen SlotIndexes *Indexes; 68cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen LiveStacks *LS; 69f428eb6c1b09a2322b7a577b0bf2e49dd107bceaJakob Stoklund Olesen MachineDominatorTree *DomTree; 70d0bb5e2ca05d9c942223bf05e5940bb0c6cc9d3fJakob Stoklund Olesen MachineLoopInfo *Loops; 71d0bb5e2ca05d9c942223bf05e5940bb0c6cc9d3fJakob Stoklund Olesen MachineLoopRanges *LoopRanges; 72b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen EdgeBundles *Bundles; 73b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen SpillPlacement *SpillPlacer; 74f42b66169d75301346e3685fd2b3e45e47806367Jakob Stoklund Olesen LiveDebugVariables *DebugVars; 75f428eb6c1b09a2322b7a577b0bf2e49dd107bceaJakob Stoklund Olesen 76cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen // state 77cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen std::auto_ptr<Spiller> SpillerInstance; 7898d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen std::priority_queue<std::pair<unsigned, unsigned> > Queue; 7922a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen 8022a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // Live ranges pass through a number of stages as we try to allocate them. 8122a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // Some of the stages may also create new live ranges: 8222a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // 8322a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // - Region splitting. 8422a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // - Per-block splitting. 8522a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // - Local splitting. 8622a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // - Spilling. 8722a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // 8822a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // Ranges produced by one of the stages skip the previous stages when they are 8922a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // dequeued. This improves performance because we can skip interference checks 9022a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // that are unlikely to give any results. It also guarantees that the live 9122a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // range splitting algorithm terminates, something that is otherwise hard to 9222a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // ensure. 9322a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen enum LiveRangeStage { 94f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund Olesen RS_New, ///< Never seen before. 95f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund Olesen RS_First, ///< First time in the queue. 9676395c9a31444fa86514473e0852cdd67752d0e8Jakob Stoklund Olesen RS_Second, ///< Second time in the queue. 97fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen RS_Global, ///< Produced by global splitting. 9822a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen RS_Local, ///< Produced by local splitting. 9922a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen RS_Spill ///< Produced by spilling. 10022a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen }; 10122a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen 102b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen static const char *const StageName[]; 103b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen 10422a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen IndexedMap<unsigned char, VirtReg2IndexFunctor> LRStage; 10522a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen 10622a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen LiveRangeStage getStage(const LiveInterval &VirtReg) const { 10722a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen return LiveRangeStage(LRStage[VirtReg.reg]); 10822a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen } 10922a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen 11022a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen template<typename Iterator> 11122a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen void setStage(Iterator Begin, Iterator End, LiveRangeStage NewStage) { 11222a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen LRStage.resize(MRI->getNumVirtRegs()); 113f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund Olesen for (;Begin != End; ++Begin) { 114f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund Olesen unsigned Reg = (*Begin)->reg; 115f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund Olesen if (LRStage[Reg] == RS_New) 116f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund Olesen LRStage[Reg] = NewStage; 117f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund Olesen } 11822a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen } 119cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 12076395c9a31444fa86514473e0852cdd67752d0e8Jakob Stoklund Olesen // Eviction. Sometimes an assigned live range can be evicted without 12176395c9a31444fa86514473e0852cdd67752d0e8Jakob Stoklund Olesen // conditions, but other times it must be split after being evicted to avoid 12276395c9a31444fa86514473e0852cdd67752d0e8Jakob Stoklund Olesen // infinite loops. 12376395c9a31444fa86514473e0852cdd67752d0e8Jakob Stoklund Olesen enum CanEvict { 12476395c9a31444fa86514473e0852cdd67752d0e8Jakob Stoklund Olesen CE_Never, ///< Can never evict. 12576395c9a31444fa86514473e0852cdd67752d0e8Jakob Stoklund Olesen CE_Always, ///< Can always evict. 12676395c9a31444fa86514473e0852cdd67752d0e8Jakob Stoklund Olesen CE_WithSplit ///< Can evict only if range is also split or spilled. 12776395c9a31444fa86514473e0852cdd67752d0e8Jakob Stoklund Olesen }; 12876395c9a31444fa86514473e0852cdd67752d0e8Jakob Stoklund Olesen 129b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen // splitting state. 13022a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen std::auto_ptr<SplitAnalysis> SA; 131bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen std::auto_ptr<SplitEditor> SE; 132b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 133eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen /// Cached per-block interference maps 134eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen InterferenceCache IntfCache; 135eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen 1367b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen /// All basic blocks where the current register has uses. 13796dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen SmallVector<SpillPlacement::BlockConstraint, 8> SplitConstraints; 138b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 13996dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen /// Global live range splitting candidate info. 14096dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen struct GlobalSplitCandidate { 14196dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen unsigned PhysReg; 14296dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen BitVector LiveBundles; 1435db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen SmallVector<unsigned, 8> ActiveBlocks; 1445db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen 1455db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen void reset(unsigned Reg) { 1465db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen PhysReg = Reg; 1475db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen LiveBundles.clear(); 1485db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen ActiveBlocks.clear(); 1495db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen } 15096dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen }; 15196dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen 15296dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen /// Candidate info for for each PhysReg in AllocationOrder. 15396dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen /// This vector never shrinks, but grows to the size of the largest register 15496dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen /// class. 15596dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen SmallVector<GlobalSplitCandidate, 32> GlobalCand; 15696dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen 157034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen /// For every instruction in SA->UseSlots, store the previous non-copy 158034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen /// instruction. 159034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen SmallVector<SlotIndex, 8> PrevSlot; 160034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 161cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesenpublic: 162cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen RAGreedy(); 163cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 164cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen /// Return the pass name. 165cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen virtual const char* getPassName() const { 166533f58ecdd8a4732c2f0e149387c4d8d8d4142deJakob Stoklund Olesen return "Greedy Register Allocator"; 167cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen } 168cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 169cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen /// RAGreedy analysis usage. 170cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen virtual void getAnalysisUsage(AnalysisUsage &AU) const; 171cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen virtual void releaseMemory(); 172cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen virtual Spiller &spiller() { return *SpillerInstance; } 17398d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen virtual void enqueue(LiveInterval *LI); 17498d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen virtual LiveInterval *dequeue(); 175ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen virtual unsigned selectOrSplit(LiveInterval&, 176ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen SmallVectorImpl<LiveInterval*>&); 177cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 178cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen /// Perform register allocation. 179cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen virtual bool runOnMachineFunction(MachineFunction &mf); 180cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 181cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen static char ID; 182b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick 183b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trickprivate: 18492a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen void LRE_WillEraseInstruction(MachineInstr*); 1857792e980c43536814ea42448db9799b4da32fef6Jakob Stoklund Olesen bool LRE_CanEraseVirtReg(unsigned); 1861d5b84508173b93faf513032b3847152e6060791Jakob Stoklund Olesen void LRE_WillShrinkVirtReg(unsigned); 187f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund Olesen void LRE_DidCloneVirtReg(unsigned, unsigned); 18892a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen 189200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen float calcSpillCost(); 190f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen bool addSplitConstraints(InterferenceCache::Cursor, float&); 191f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen void addThroughConstraints(InterferenceCache::Cursor, ArrayRef<unsigned>); 1925db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen void growRegion(GlobalSplitCandidate &Cand, InterferenceCache::Cursor); 1935db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen float calcGlobalSplitCost(GlobalSplitCandidate&, InterferenceCache::Cursor); 1945db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen void splitAroundRegion(LiveInterval&, GlobalSplitCandidate&, 195ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen SmallVectorImpl<LiveInterval*>&); 196034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen void calcGapWeights(unsigned, SmallVectorImpl<float>&); 197034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen SlotIndex getPrevMappedIndex(const MachineInstr*); 198034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen void calcPrevSlots(); 199034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen unsigned nextSplitPoint(unsigned); 20076395c9a31444fa86514473e0852cdd67752d0e8Jakob Stoklund Olesen CanEvict canEvict(LiveInterval &A, LiveInterval &B); 20176395c9a31444fa86514473e0852cdd67752d0e8Jakob Stoklund Olesen bool canEvictInterference(LiveInterval&, unsigned, float&); 202b64d92e29f38002e52a22fe36ea2d488968e3537Jakob Stoklund Olesen 2036bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen unsigned tryAssign(LiveInterval&, AllocationOrder&, 2046bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen SmallVectorImpl<LiveInterval*>&); 20598c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen unsigned tryEvict(LiveInterval&, AllocationOrder&, 2066bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen SmallVectorImpl<LiveInterval*>&, unsigned = ~0u); 207b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen unsigned tryRegionSplit(LiveInterval&, AllocationOrder&, 208b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen SmallVectorImpl<LiveInterval*>&); 209034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen unsigned tryLocalSplit(LiveInterval&, AllocationOrder&, 210034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen SmallVectorImpl<LiveInterval*>&); 211b64d92e29f38002e52a22fe36ea2d488968e3537Jakob Stoklund Olesen unsigned trySplit(LiveInterval&, AllocationOrder&, 212b64d92e29f38002e52a22fe36ea2d488968e3537Jakob Stoklund Olesen SmallVectorImpl<LiveInterval*>&); 213cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen}; 214cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen} // end anonymous namespace 215cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 216cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesenchar RAGreedy::ID = 0; 217cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 218b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen#ifndef NDEBUG 219b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesenconst char *const RAGreedy::StageName[] = { 220b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen "RS_New", 221b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen "RS_First", 222b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen "RS_Second", 223b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen "RS_Global", 224b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen "RS_Local", 225b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen "RS_Spill" 226b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen}; 227b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen#endif 228b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen 229200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen// Hysteresis to use when comparing floats. 230200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen// This helps stabilize decisions based on float comparisons. 231200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesenconst float Hysteresis = 0.98f; 232200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen 233200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen 234cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund OlesenFunctionPass* llvm::createGreedyRegisterAllocator() { 235cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen return new RAGreedy(); 236cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen} 237cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 238f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund OlesenRAGreedy::RAGreedy(): MachineFunctionPass(ID), LRStage(RS_New) { 239cfafc54040cc9722995558124f253d05a038176bJakob Stoklund Olesen initializeLiveDebugVariablesPass(*PassRegistry::getPassRegistry()); 240b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen initializeSlotIndexesPass(*PassRegistry::getPassRegistry()); 241cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen initializeLiveIntervalsPass(*PassRegistry::getPassRegistry()); 242cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen initializeSlotIndexesPass(*PassRegistry::getPassRegistry()); 243cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen initializeStrongPHIEliminationPass(*PassRegistry::getPassRegistry()); 244cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen initializeRegisterCoalescerAnalysisGroup(*PassRegistry::getPassRegistry()); 245cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen initializeCalculateSpillWeightsPass(*PassRegistry::getPassRegistry()); 246cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen initializeLiveStacksPass(*PassRegistry::getPassRegistry()); 247cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry()); 248cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen initializeMachineLoopInfoPass(*PassRegistry::getPassRegistry()); 249d0bb5e2ca05d9c942223bf05e5940bb0c6cc9d3fJakob Stoklund Olesen initializeMachineLoopRangesPass(*PassRegistry::getPassRegistry()); 250cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen initializeVirtRegMapPass(*PassRegistry::getPassRegistry()); 251b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen initializeEdgeBundlesPass(*PassRegistry::getPassRegistry()); 252b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen initializeSpillPlacementPass(*PassRegistry::getPassRegistry()); 253cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen} 254cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 255cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesenvoid RAGreedy::getAnalysisUsage(AnalysisUsage &AU) const { 256cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.setPreservesCFG(); 257cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addRequired<AliasAnalysis>(); 258cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addPreserved<AliasAnalysis>(); 259cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addRequired<LiveIntervals>(); 260b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen AU.addRequired<SlotIndexes>(); 261cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addPreserved<SlotIndexes>(); 262cfafc54040cc9722995558124f253d05a038176bJakob Stoklund Olesen AU.addRequired<LiveDebugVariables>(); 263cfafc54040cc9722995558124f253d05a038176bJakob Stoklund Olesen AU.addPreserved<LiveDebugVariables>(); 264cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen if (StrongPHIElim) 265cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addRequiredID(StrongPHIEliminationID); 266cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addRequiredTransitive<RegisterCoalescer>(); 267cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addRequired<CalculateSpillWeights>(); 268cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addRequired<LiveStacks>(); 269cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addPreserved<LiveStacks>(); 270f428eb6c1b09a2322b7a577b0bf2e49dd107bceaJakob Stoklund Olesen AU.addRequired<MachineDominatorTree>(); 271f428eb6c1b09a2322b7a577b0bf2e49dd107bceaJakob Stoklund Olesen AU.addPreserved<MachineDominatorTree>(); 272cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addRequired<MachineLoopInfo>(); 273cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addPreserved<MachineLoopInfo>(); 274d0bb5e2ca05d9c942223bf05e5940bb0c6cc9d3fJakob Stoklund Olesen AU.addRequired<MachineLoopRanges>(); 275d0bb5e2ca05d9c942223bf05e5940bb0c6cc9d3fJakob Stoklund Olesen AU.addPreserved<MachineLoopRanges>(); 276cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addRequired<VirtRegMap>(); 277cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addPreserved<VirtRegMap>(); 278b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen AU.addRequired<EdgeBundles>(); 279b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen AU.addRequired<SpillPlacement>(); 280cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen MachineFunctionPass::getAnalysisUsage(AU); 281cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen} 282cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 28392a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen 28492a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 28592a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen// LiveRangeEdit delegate methods 28692a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 28792a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen 28892a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesenvoid RAGreedy::LRE_WillEraseInstruction(MachineInstr *MI) { 28992a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen // LRE itself will remove from SlotIndexes and parent basic block. 29092a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen VRM->RemoveMachineInstrFromMaps(MI); 29192a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen} 29292a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen 2937792e980c43536814ea42448db9799b4da32fef6Jakob Stoklund Olesenbool RAGreedy::LRE_CanEraseVirtReg(unsigned VirtReg) { 2947792e980c43536814ea42448db9799b4da32fef6Jakob Stoklund Olesen if (unsigned PhysReg = VRM->getPhys(VirtReg)) { 2957792e980c43536814ea42448db9799b4da32fef6Jakob Stoklund Olesen unassign(LIS->getInterval(VirtReg), PhysReg); 2967792e980c43536814ea42448db9799b4da32fef6Jakob Stoklund Olesen return true; 2977792e980c43536814ea42448db9799b4da32fef6Jakob Stoklund Olesen } 2987792e980c43536814ea42448db9799b4da32fef6Jakob Stoklund Olesen // Unassigned virtreg is probably in the priority queue. 2997792e980c43536814ea42448db9799b4da32fef6Jakob Stoklund Olesen // RegAllocBase will erase it after dequeueing. 3007792e980c43536814ea42448db9799b4da32fef6Jakob Stoklund Olesen return false; 3017792e980c43536814ea42448db9799b4da32fef6Jakob Stoklund Olesen} 30292a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen 3031d5b84508173b93faf513032b3847152e6060791Jakob Stoklund Olesenvoid RAGreedy::LRE_WillShrinkVirtReg(unsigned VirtReg) { 3041d5b84508173b93faf513032b3847152e6060791Jakob Stoklund Olesen unsigned PhysReg = VRM->getPhys(VirtReg); 3051d5b84508173b93faf513032b3847152e6060791Jakob Stoklund Olesen if (!PhysReg) 3061d5b84508173b93faf513032b3847152e6060791Jakob Stoklund Olesen return; 3071d5b84508173b93faf513032b3847152e6060791Jakob Stoklund Olesen 3081d5b84508173b93faf513032b3847152e6060791Jakob Stoklund Olesen // Register is assigned, put it back on the queue for reassignment. 3091d5b84508173b93faf513032b3847152e6060791Jakob Stoklund Olesen LiveInterval &LI = LIS->getInterval(VirtReg); 3101d5b84508173b93faf513032b3847152e6060791Jakob Stoklund Olesen unassign(LI, PhysReg); 3111d5b84508173b93faf513032b3847152e6060791Jakob Stoklund Olesen enqueue(&LI); 3121d5b84508173b93faf513032b3847152e6060791Jakob Stoklund Olesen} 3131d5b84508173b93faf513032b3847152e6060791Jakob Stoklund Olesen 314f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund Olesenvoid RAGreedy::LRE_DidCloneVirtReg(unsigned New, unsigned Old) { 315f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund Olesen // LRE may clone a virtual register because dead code elimination causes it to 316f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund Olesen // be split into connected components. Ensure that the new register gets the 317f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund Olesen // same stage as the parent. 318f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund Olesen LRStage.grow(New); 319f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund Olesen LRStage[New] = LRStage[Old]; 320f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund Olesen} 321f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund Olesen 322cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesenvoid RAGreedy::releaseMemory() { 323cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen SpillerInstance.reset(0); 32422a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen LRStage.clear(); 3255db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen GlobalCand.clear(); 326cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen RegAllocBase::releaseMemory(); 327cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen} 328cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 32998d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesenvoid RAGreedy::enqueue(LiveInterval *LI) { 33098d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen // Prioritize live ranges by size, assigning larger ranges first. 33198d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen // The queue holds (size, reg) pairs. 332107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen const unsigned Size = LI->getSize(); 333107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen const unsigned Reg = LI->reg; 33498d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen assert(TargetRegisterInfo::isVirtualRegister(Reg) && 33598d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen "Can only enqueue virtual registers"); 336107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen unsigned Prio; 33790c1d7ddfc65654f7efe72d56cad65d1af9e6b2aJakob Stoklund Olesen 33822a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen LRStage.grow(Reg); 339f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund Olesen if (LRStage[Reg] == RS_New) 340f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund Olesen LRStage[Reg] = RS_First; 341f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund Olesen 342eb29157d80847c207b77910bcd40a6a6c91ca5c5Jakob Stoklund Olesen if (LRStage[Reg] == RS_Second) 343eb29157d80847c207b77910bcd40a6a6c91ca5c5Jakob Stoklund Olesen // Unsplit ranges that couldn't be allocated immediately are deferred until 344eb29157d80847c207b77910bcd40a6a6c91ca5c5Jakob Stoklund Olesen // everything else has been allocated. Long ranges are allocated last so 345eb29157d80847c207b77910bcd40a6a6c91ca5c5Jakob Stoklund Olesen // they are split against realistic interference. 346eb29157d80847c207b77910bcd40a6a6c91ca5c5Jakob Stoklund Olesen Prio = (1u << 31) - Size; 347eb29157d80847c207b77910bcd40a6a6c91ca5c5Jakob Stoklund Olesen else { 348eb29157d80847c207b77910bcd40a6a6c91ca5c5Jakob Stoklund Olesen // Everything else is allocated in long->short order. Long ranges that don't 349eb29157d80847c207b77910bcd40a6a6c91ca5c5Jakob Stoklund Olesen // fit should be spilled ASAP so they don't create interference. 350107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen Prio = (1u << 31) + Size; 351d2a50734234a80893ad71da90d9f32032c47e000Jakob Stoklund Olesen 352eb29157d80847c207b77910bcd40a6a6c91ca5c5Jakob Stoklund Olesen // Boost ranges that have a physical register hint. 353eb29157d80847c207b77910bcd40a6a6c91ca5c5Jakob Stoklund Olesen if (TargetRegisterInfo::isPhysicalRegister(VRM->getRegAllocPref(Reg))) 354eb29157d80847c207b77910bcd40a6a6c91ca5c5Jakob Stoklund Olesen Prio |= (1u << 30); 355eb29157d80847c207b77910bcd40a6a6c91ca5c5Jakob Stoklund Olesen } 356107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen 357107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen Queue.push(std::make_pair(Prio, Reg)); 35890c1d7ddfc65654f7efe72d56cad65d1af9e6b2aJakob Stoklund Olesen} 35990c1d7ddfc65654f7efe72d56cad65d1af9e6b2aJakob Stoklund Olesen 36098d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund OlesenLiveInterval *RAGreedy::dequeue() { 36198d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen if (Queue.empty()) 36298d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen return 0; 36398d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen LiveInterval *LI = &LIS->getInterval(Queue.top().second); 36498d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen Queue.pop(); 36598d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen return LI; 36698d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen} 367770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen 3686bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen 3696bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 3706bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen// Direct Assignment 3716bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 3726bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen 3736bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen/// tryAssign - Try to assign VirtReg to an available register. 3746bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesenunsigned RAGreedy::tryAssign(LiveInterval &VirtReg, 3756bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen AllocationOrder &Order, 3766bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen SmallVectorImpl<LiveInterval*> &NewVRegs) { 3776bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen Order.rewind(); 3786bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen unsigned PhysReg; 3796bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen while ((PhysReg = Order.next())) 3806bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen if (!checkPhysRegInterference(VirtReg, PhysReg)) 3816bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen break; 3826bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen if (!PhysReg || Order.isHint(PhysReg)) 3836bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen return PhysReg; 3846bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen 3856bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen // PhysReg is available. Try to evict interference from a cheaper alternative. 3866bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen unsigned Cost = TRI->getCostPerUse(PhysReg); 3876bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen 3886bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen // Most registers have 0 additional cost. 3896bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen if (!Cost) 3906bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen return PhysReg; 3916bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen 3926bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen DEBUG(dbgs() << PrintReg(PhysReg, TRI) << " is available at cost " << Cost 3936bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen << '\n'); 3946bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen unsigned CheapReg = tryEvict(VirtReg, Order, NewVRegs, Cost); 3956bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen return CheapReg ? CheapReg : PhysReg; 3966bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen} 3976bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen 3986bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen 399770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen//===----------------------------------------------------------------------===// 40098c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen// Interference eviction 40198c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 4022710638db2eb84cd7eefb8bb9a1b7e5c49413d45Jakob Stoklund Olesen 403b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen/// canEvict - determine if A can evict the assigned live range B. The eviction 404b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen/// policy defined by this function together with the allocation order defined 405b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen/// by enqueue() decides which registers ultimately end up being split and 406b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen/// spilled. 407b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen/// 40876395c9a31444fa86514473e0852cdd67752d0e8Jakob Stoklund Olesen/// This function must define a non-circular relation when it returns CE_Always, 40976395c9a31444fa86514473e0852cdd67752d0e8Jakob Stoklund Olesen/// otherwise infinite eviction loops are possible. When evicting a <= RS_Second 41076395c9a31444fa86514473e0852cdd67752d0e8Jakob Stoklund Olesen/// range, it is possible to return CE_WithSplit which forces the evicted 41176395c9a31444fa86514473e0852cdd67752d0e8Jakob Stoklund Olesen/// register to be split or spilled before it can evict anything again. That 41276395c9a31444fa86514473e0852cdd67752d0e8Jakob Stoklund Olesen/// guarantees progress. 41376395c9a31444fa86514473e0852cdd67752d0e8Jakob Stoklund OlesenRAGreedy::CanEvict RAGreedy::canEvict(LiveInterval &A, LiveInterval &B) { 41476395c9a31444fa86514473e0852cdd67752d0e8Jakob Stoklund Olesen return A.weight > B.weight ? CE_Always : CE_Never; 415b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen} 416b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen 41798c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen/// canEvict - Return true if all interferences between VirtReg and PhysReg can 4183f5bedf5cbde2cc2badc86b1a0b377f6efcde71cJakob Stoklund Olesen/// be evicted. 4193f5bedf5cbde2cc2badc86b1a0b377f6efcde71cJakob Stoklund Olesen/// Return false if any interference is heavier than MaxWeight. 4203f5bedf5cbde2cc2badc86b1a0b377f6efcde71cJakob Stoklund Olesen/// On return, set MaxWeight to the maximal spill weight of an interference. 42198c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesenbool RAGreedy::canEvictInterference(LiveInterval &VirtReg, unsigned PhysReg, 42276395c9a31444fa86514473e0852cdd67752d0e8Jakob Stoklund Olesen float &MaxWeight) { 42398c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen float Weight = 0; 42498c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen for (const unsigned *AliasI = TRI->getOverlaps(PhysReg); *AliasI; ++AliasI) { 42598c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen LiveIntervalUnion::Query &Q = query(VirtReg, *AliasI); 4263f5bedf5cbde2cc2badc86b1a0b377f6efcde71cJakob Stoklund Olesen // If there is 10 or more interferences, chances are one is heavier. 4273f5bedf5cbde2cc2badc86b1a0b377f6efcde71cJakob Stoklund Olesen if (Q.collectInterferingVRegs(10, MaxWeight) >= 10) 42898c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen return false; 42998c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen 4303f5bedf5cbde2cc2badc86b1a0b377f6efcde71cJakob Stoklund Olesen // Check if any interfering live range is heavier than MaxWeight. 4313f5bedf5cbde2cc2badc86b1a0b377f6efcde71cJakob Stoklund Olesen for (unsigned i = Q.interferingVRegs().size(); i; --i) { 4323f5bedf5cbde2cc2badc86b1a0b377f6efcde71cJakob Stoklund Olesen LiveInterval *Intf = Q.interferingVRegs()[i - 1]; 43398c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen if (TargetRegisterInfo::isPhysicalRegister(Intf->reg)) 43498c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen return false; 435d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen if (Intf->weight >= MaxWeight) 436b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen return false; 43776395c9a31444fa86514473e0852cdd67752d0e8Jakob Stoklund Olesen switch (canEvict(VirtReg, *Intf)) { 43876395c9a31444fa86514473e0852cdd67752d0e8Jakob Stoklund Olesen case CE_Always: 43976395c9a31444fa86514473e0852cdd67752d0e8Jakob Stoklund Olesen break; 44076395c9a31444fa86514473e0852cdd67752d0e8Jakob Stoklund Olesen case CE_Never: 44176395c9a31444fa86514473e0852cdd67752d0e8Jakob Stoklund Olesen return false; 44276395c9a31444fa86514473e0852cdd67752d0e8Jakob Stoklund Olesen case CE_WithSplit: 44376395c9a31444fa86514473e0852cdd67752d0e8Jakob Stoklund Olesen if (getStage(*Intf) > RS_Second) 444b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen return false; 44576395c9a31444fa86514473e0852cdd67752d0e8Jakob Stoklund Olesen break; 446b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen } 44798c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen Weight = std::max(Weight, Intf->weight); 4482710638db2eb84cd7eefb8bb9a1b7e5c49413d45Jakob Stoklund Olesen } 4492710638db2eb84cd7eefb8bb9a1b7e5c49413d45Jakob Stoklund Olesen } 45098c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen MaxWeight = Weight; 45198c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen return true; 45298c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen} 45398c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen 45498c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen/// tryEvict - Try to evict all interferences for a physreg. 45576395c9a31444fa86514473e0852cdd67752d0e8Jakob Stoklund Olesen/// @param VirtReg Currently unassigned virtual register. 45676395c9a31444fa86514473e0852cdd67752d0e8Jakob Stoklund Olesen/// @param Order Physregs to try. 45776395c9a31444fa86514473e0852cdd67752d0e8Jakob Stoklund Olesen/// @return Physreg to assign VirtReg, or 0. 45898c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesenunsigned RAGreedy::tryEvict(LiveInterval &VirtReg, 45998c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen AllocationOrder &Order, 4606bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen SmallVectorImpl<LiveInterval*> &NewVRegs, 4616bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen unsigned CostPerUseLimit) { 46298c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen NamedRegionTimer T("Evict", TimerGroupName, TimePassesIsEnabled); 46398c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen 46498c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen // Keep track of the lightest single interference seen so far. 46576395c9a31444fa86514473e0852cdd67752d0e8Jakob Stoklund Olesen float BestWeight = HUGE_VALF; 46698c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen unsigned BestPhys = 0; 46798c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen 46898c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen Order.rewind(); 46998c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen while (unsigned PhysReg = Order.next()) { 4706bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen if (TRI->getCostPerUse(PhysReg) >= CostPerUseLimit) 4716bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen continue; 4726bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen // The first use of a register in a function has cost 1. 4736bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen if (CostPerUseLimit == 1 && !MRI->isPhysRegUsed(PhysReg)) 4746bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen continue; 4756bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen 4763f5bedf5cbde2cc2badc86b1a0b377f6efcde71cJakob Stoklund Olesen float Weight = BestWeight; 47776395c9a31444fa86514473e0852cdd67752d0e8Jakob Stoklund Olesen if (!canEvictInterference(VirtReg, PhysReg, Weight)) 47898c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen continue; 47998c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen 48098c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen // This is an eviction candidate. 4813f5bedf5cbde2cc2badc86b1a0b377f6efcde71cJakob Stoklund Olesen DEBUG(dbgs() << PrintReg(PhysReg, TRI) << " interference = " 48298c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen << Weight << '\n'); 48398c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen if (BestPhys && Weight >= BestWeight) 48498c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen continue; 48598c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen 48698c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen // Best so far. 48798c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen BestPhys = PhysReg; 48898c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen BestWeight = Weight; 48957f1e2cee06f9b57995727d786aeb1031c5376bdJakob Stoklund Olesen // Stop if the hint can be used. 49057f1e2cee06f9b57995727d786aeb1031c5376bdJakob Stoklund Olesen if (Order.isHint(PhysReg)) 49157f1e2cee06f9b57995727d786aeb1031c5376bdJakob Stoklund Olesen break; 4922710638db2eb84cd7eefb8bb9a1b7e5c49413d45Jakob Stoklund Olesen } 4932710638db2eb84cd7eefb8bb9a1b7e5c49413d45Jakob Stoklund Olesen 49498c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen if (!BestPhys) 49598c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen return 0; 49698c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen 49798c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen DEBUG(dbgs() << "evicting " << PrintReg(BestPhys, TRI) << " interference\n"); 49898c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen for (const unsigned *AliasI = TRI->getOverlaps(BestPhys); *AliasI; ++AliasI) { 49998c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen LiveIntervalUnion::Query &Q = query(VirtReg, *AliasI); 50098c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen assert(Q.seenAllInterferences() && "Didn't check all interfererences."); 50198c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen for (unsigned i = 0, e = Q.interferingVRegs().size(); i != e; ++i) { 50298c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen LiveInterval *Intf = Q.interferingVRegs()[i]; 50398c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen unassign(*Intf, VRM->getPhys(Intf->reg)); 50498c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen ++NumEvicted; 50598c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen NewVRegs.push_back(Intf); 50676395c9a31444fa86514473e0852cdd67752d0e8Jakob Stoklund Olesen // Prevent looping by forcing the evicted ranges to be split before they 50776395c9a31444fa86514473e0852cdd67752d0e8Jakob Stoklund Olesen // can evict anything else. 50876395c9a31444fa86514473e0852cdd67752d0e8Jakob Stoklund Olesen if (getStage(*Intf) < RS_Second && 50976395c9a31444fa86514473e0852cdd67752d0e8Jakob Stoklund Olesen canEvict(VirtReg, *Intf) == CE_WithSplit) 51076395c9a31444fa86514473e0852cdd67752d0e8Jakob Stoklund Olesen LRStage[Intf->reg] = RS_Second; 51198c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen } 51298c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen } 51398c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen return BestPhys; 514b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick} 515b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick 516770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen 517770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen//===----------------------------------------------------------------------===// 518b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen// Region Splitting 519b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen//===----------------------------------------------------------------------===// 520b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 5211b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen/// addSplitConstraints - Fill out the SplitConstraints vector based on the 5221b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen/// interference pattern in Physreg and its aliases. Add the constraints to 5231b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen/// SpillPlacement and return the static cost of this split in Cost, assuming 5241b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen/// that all preferences in SplitConstraints are met. 525f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen/// Return false if there are no bundles with positive bias. 526f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesenbool RAGreedy::addSplitConstraints(InterferenceCache::Cursor Intf, 527f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen float &Cost) { 528db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks(); 529eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen 530b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen // Reset interference dependent info. 531db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen SplitConstraints.resize(UseBlocks.size()); 53296dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen float StaticCost = 0; 533db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen for (unsigned i = 0; i != UseBlocks.size(); ++i) { 534db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen const SplitAnalysis::BlockInfo &BI = UseBlocks[i]; 53596dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen SpillPlacement::BlockConstraint &BC = SplitConstraints[i]; 53696dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen 537f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen BC.Number = BI.MBB->getNumber(); 538eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen Intf.moveToBlock(BC.Number); 539db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen BC.Entry = BI.LiveIn ? SpillPlacement::PrefReg : SpillPlacement::DontCare; 540db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen BC.Exit = BI.LiveOut ? SpillPlacement::PrefReg : SpillPlacement::DontCare; 541b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 542eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen if (!Intf.hasInterference()) 543eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen continue; 544eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen 54596dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen // Number of spill code instructions to insert. 54696dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen unsigned Ins = 0; 54796dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen 54896dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen // Interference for the live-in value. 549eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen if (BI.LiveIn) { 5506c8afd728eb02742ce320ecd39bcf3774d8423b7Jakob Stoklund Olesen if (Intf.first() <= Indexes->getMBBStartIdx(BC.Number)) 551db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen BC.Entry = SpillPlacement::MustSpill, ++Ins; 552eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen else if (Intf.first() < BI.FirstUse) 55396dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen BC.Entry = SpillPlacement::PrefSpill, ++Ins; 554a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen else if (Intf.first() < BI.LastUse) 55596dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen ++Ins; 556a50c539b7a9e74597da34bfaea5429a48481f18bJakob Stoklund Olesen } 557b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 55896dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen // Interference for the live-out value. 559eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen if (BI.LiveOut) { 560612f7807c581eafb7c8105e1a55c8d839033bfb3Jakob Stoklund Olesen if (Intf.last() >= SA->getLastSplitPoint(BC.Number)) 561db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen BC.Exit = SpillPlacement::MustSpill, ++Ins; 562eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen else if (Intf.last() > BI.LastUse) 56396dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen BC.Exit = SpillPlacement::PrefSpill, ++Ins; 564a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen else if (Intf.last() > BI.FirstUse) 56596dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen ++Ins; 566b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen } 567b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 56896dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen // Accumulate the total frequency of inserted spill code. 56996dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen if (Ins) 57096dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen StaticCost += Ins * SpillPlacer->getBlockFrequency(BC.Number); 571b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen } 572f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen Cost = StaticCost; 573db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen 5741b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen // Add constraints for use-blocks. Note that these are the only constraints 5751b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen // that may add a positive bias, it is downhill from here. 5761b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen SpillPlacer->addConstraints(SplitConstraints); 577f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen return SpillPlacer->scanActiveBundles(); 578f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen} 579db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen 580db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen 581f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen/// addThroughConstraints - Add constraints and links to SpillPlacer from the 582f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen/// live-through blocks in Blocks. 583f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesenvoid RAGreedy::addThroughConstraints(InterferenceCache::Cursor Intf, 584f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen ArrayRef<unsigned> Blocks) { 5851b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen const unsigned GroupSize = 8; 5861b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen SpillPlacement::BlockConstraint BCS[GroupSize]; 587f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen unsigned TBS[GroupSize]; 588f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen unsigned B = 0, T = 0; 589db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen 590f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen for (unsigned i = 0; i != Blocks.size(); ++i) { 591f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen unsigned Number = Blocks[i]; 5921b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen Intf.moveToBlock(Number); 5931b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen 5947b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen if (!Intf.hasInterference()) { 595f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen assert(T < GroupSize && "Array overflow"); 596f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen TBS[T] = Number; 597f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen if (++T == GroupSize) { 598f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen SpillPlacer->addLinks(ArrayRef<unsigned>(TBS, T)); 599f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen T = 0; 600f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen } 6017b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen continue; 6021b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen } 6031b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen 604f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen assert(B < GroupSize && "Array overflow"); 605f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen BCS[B].Number = Number; 606f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen 6077b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen // Interference for the live-in value. 6087b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen if (Intf.first() <= Indexes->getMBBStartIdx(Number)) 6097b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen BCS[B].Entry = SpillPlacement::MustSpill; 6107b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen else 6117b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen BCS[B].Entry = SpillPlacement::PrefSpill; 6127b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen 6137b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen // Interference for the live-out value. 6147b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen if (Intf.last() >= SA->getLastSplitPoint(Number)) 6157b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen BCS[B].Exit = SpillPlacement::MustSpill; 6167b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen else 6177b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen BCS[B].Exit = SpillPlacement::PrefSpill; 6187b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen 6191b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen if (++B == GroupSize) { 6201b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen ArrayRef<SpillPlacement::BlockConstraint> Array(BCS, B); 6211b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen SpillPlacer->addConstraints(Array); 6221b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen B = 0; 6231b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen } 624db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen } 625db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen 6261b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen ArrayRef<SpillPlacement::BlockConstraint> Array(BCS, B); 6271b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen SpillPlacer->addConstraints(Array); 628f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen SpillPlacer->addLinks(ArrayRef<unsigned>(TBS, T)); 629b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen} 630b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 6315db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesenvoid RAGreedy::growRegion(GlobalSplitCandidate &Cand, 6325db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen InterferenceCache::Cursor Intf) { 6335db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen // Keep track of through blocks that have not been added to SpillPlacer. 6345db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen BitVector Todo = SA->getThroughBlocks(); 6355db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen SmallVectorImpl<unsigned> &ActiveBlocks = Cand.ActiveBlocks; 6365db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen unsigned AddedTo = 0; 637f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen#ifndef NDEBUG 638f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen unsigned Visited = 0; 639f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen#endif 6405db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen 641f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen for (;;) { 642f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen ArrayRef<unsigned> NewBundles = SpillPlacer->getRecentPositive(); 643f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen if (NewBundles.empty()) 644f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen break; 645f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen // Find new through blocks in the periphery of PrefRegBundles. 646f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen for (int i = 0, e = NewBundles.size(); i != e; ++i) { 647f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen unsigned Bundle = NewBundles[i]; 648f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen // Look at all blocks connected to Bundle in the full graph. 649f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen ArrayRef<unsigned> Blocks = Bundles->getBlocks(Bundle); 650f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen for (ArrayRef<unsigned>::iterator I = Blocks.begin(), E = Blocks.end(); 651f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen I != E; ++I) { 652f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen unsigned Block = *I; 6535db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen if (!Todo.test(Block)) 654f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen continue; 6555db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen Todo.reset(Block); 656f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen // This is a new through block. Add it to SpillPlacer later. 6575db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen ActiveBlocks.push_back(Block); 658f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen#ifndef NDEBUG 659f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen ++Visited; 660f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen#endif 661f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen } 662f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen } 663f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen // Any new blocks to add? 6645db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen if (ActiveBlocks.size() > AddedTo) { 6655db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen ArrayRef<unsigned> Add(&ActiveBlocks[AddedTo], 6665db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen ActiveBlocks.size() - AddedTo); 6675db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen addThroughConstraints(Intf, Add); 6685db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen AddedTo = ActiveBlocks.size(); 669f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen } 670f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen // Perhaps iterating can enable more bundles? 671f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen SpillPlacer->iterate(); 672f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen } 673f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen DEBUG(dbgs() << ", v=" << Visited); 674f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen} 67596dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen 676200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen/// calcSpillCost - Compute how expensive it would be to split the live range in 677200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen/// SA around all use blocks instead of forming bundle regions. 678200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesenfloat RAGreedy::calcSpillCost() { 679200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen float Cost = 0; 680200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen const LiveInterval &LI = SA->getParent(); 681200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks(); 682200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen for (unsigned i = 0; i != UseBlocks.size(); ++i) { 683200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen const SplitAnalysis::BlockInfo &BI = UseBlocks[i]; 684200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen unsigned Number = BI.MBB->getNumber(); 685200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen // We normally only need one spill instruction - a load or a store. 686200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen Cost += SpillPlacer->getBlockFrequency(Number); 687200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen 688200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen // Unless the value is redefined in the block. 689200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen if (BI.LiveIn && BI.LiveOut) { 690200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen SlotIndex Start, Stop; 691200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen tie(Start, Stop) = Indexes->getMBBRange(Number); 692200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen LiveInterval::const_iterator I = LI.find(Start); 693200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen assert(I != LI.end() && "Expected live-in value"); 694200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen // Is there a different live-out value? If so, we need an extra spill 695200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen // instruction. 696200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen if (I->end < Stop) 697200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen Cost += SpillPlacer->getBlockFrequency(Number); 698200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen } 699200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen } 700200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen return Cost; 701200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen} 702200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen 703b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen/// calcGlobalSplitCost - Return the global split cost of following the split 704b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen/// pattern in LiveBundles. This cost should be added to the local cost of the 70596dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen/// interference pattern in SplitConstraints. 706b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen/// 7075db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesenfloat RAGreedy::calcGlobalSplitCost(GlobalSplitCandidate &Cand, 7085db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen InterferenceCache::Cursor Intf) { 709b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen float GlobalCost = 0; 7105db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen const BitVector &LiveBundles = Cand.LiveBundles; 711db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks(); 712db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen for (unsigned i = 0; i != UseBlocks.size(); ++i) { 713db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen const SplitAnalysis::BlockInfo &BI = UseBlocks[i]; 71496dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen SpillPlacement::BlockConstraint &BC = SplitConstraints[i]; 715874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen bool RegIn = LiveBundles[Bundles->getBundle(BC.Number, 0)]; 716874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen bool RegOut = LiveBundles[Bundles->getBundle(BC.Number, 1)]; 717874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen unsigned Ins = 0; 718874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen 719db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen if (BI.LiveIn) 720db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen Ins += RegIn != (BC.Entry == SpillPlacement::PrefReg); 721db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen if (BI.LiveOut) 722db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen Ins += RegOut != (BC.Exit == SpillPlacement::PrefReg); 723874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen if (Ins) 724874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen GlobalCost += Ins * SpillPlacer->getBlockFrequency(BC.Number); 725b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen } 726db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen 7275db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen for (unsigned i = 0, e = Cand.ActiveBlocks.size(); i != e; ++i) { 7285db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen unsigned Number = Cand.ActiveBlocks[i]; 729db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen bool RegIn = LiveBundles[Bundles->getBundle(Number, 0)]; 730db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen bool RegOut = LiveBundles[Bundles->getBundle(Number, 1)]; 7319a54352879e5aaac2e2c37490e5cb7844550db8bJakob Stoklund Olesen if (!RegIn && !RegOut) 7329a54352879e5aaac2e2c37490e5cb7844550db8bJakob Stoklund Olesen continue; 7339a54352879e5aaac2e2c37490e5cb7844550db8bJakob Stoklund Olesen if (RegIn && RegOut) { 7349a54352879e5aaac2e2c37490e5cb7844550db8bJakob Stoklund Olesen // We need double spill code if this block has interference. 7359a54352879e5aaac2e2c37490e5cb7844550db8bJakob Stoklund Olesen Intf.moveToBlock(Number); 7369a54352879e5aaac2e2c37490e5cb7844550db8bJakob Stoklund Olesen if (Intf.hasInterference()) 7379a54352879e5aaac2e2c37490e5cb7844550db8bJakob Stoklund Olesen GlobalCost += 2*SpillPlacer->getBlockFrequency(Number); 7389a54352879e5aaac2e2c37490e5cb7844550db8bJakob Stoklund Olesen continue; 7399a54352879e5aaac2e2c37490e5cb7844550db8bJakob Stoklund Olesen } 7409a54352879e5aaac2e2c37490e5cb7844550db8bJakob Stoklund Olesen // live-in / stack-out or stack-in live-out. 7419a54352879e5aaac2e2c37490e5cb7844550db8bJakob Stoklund Olesen GlobalCost += SpillPlacer->getBlockFrequency(Number); 742db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen } 743b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen return GlobalCost; 744b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen} 745b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 746ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen/// splitAroundRegion - Split VirtReg around the region determined by 747ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen/// LiveBundles. Make an effort to avoid interference from PhysReg. 748ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen/// 749ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen/// The 'register' interval is going to contain as many uses as possible while 750ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen/// avoiding interference. The 'stack' interval is the complement constructed by 751ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen/// SplitEditor. It will contain the rest. 752ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen/// 7535db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesenvoid RAGreedy::splitAroundRegion(LiveInterval &VirtReg, 7545db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen GlobalSplitCandidate &Cand, 755ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen SmallVectorImpl<LiveInterval*> &NewVRegs) { 7565db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen const BitVector &LiveBundles = Cand.LiveBundles; 7575db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen 758ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen DEBUG({ 7595db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen dbgs() << "Splitting around region for " << PrintReg(Cand.PhysReg, TRI) 760ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen << " with bundles"; 761ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen for (int i = LiveBundles.find_first(); i>=0; i = LiveBundles.find_next(i)) 762ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen dbgs() << " EB#" << i; 763ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen dbgs() << ".\n"; 764ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen }); 765ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 7665db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen InterferenceCache::Cursor Intf(IntfCache, Cand.PhysReg); 76792a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen LiveRangeEdit LREdit(VirtReg, NewVRegs, this); 768bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen SE->reset(LREdit); 769ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 770ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Create the main cross-block interval. 771fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen const unsigned MainIntv = SE->openIntv(); 772ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 773ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // First add all defs that are live out of a block. 774db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks(); 775db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen for (unsigned i = 0; i != UseBlocks.size(); ++i) { 776db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen const SplitAnalysis::BlockInfo &BI = UseBlocks[i]; 777ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen bool RegIn = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 0)]; 778ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen bool RegOut = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 1)]; 779ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 780fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen // Create separate intervals for isolated blocks with multiple uses. 781fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen if (!RegIn && !RegOut && BI.FirstUse != BI.LastUse) { 782fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " isolated.\n"); 783fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen SE->splitSingleBlock(BI); 784fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen SE->selectIntv(MainIntv); 785fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen continue; 786fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen } 787fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen 788ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Should the register be live out? 789ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen if (!BI.LiveOut || !RegOut) 790ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen continue; 791ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 7926c8afd728eb02742ce320ecd39bcf3774d8423b7Jakob Stoklund Olesen SlotIndex Start, Stop; 7936c8afd728eb02742ce320ecd39bcf3774d8423b7Jakob Stoklund Olesen tie(Start, Stop) = Indexes->getMBBRange(BI.MBB); 794eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen Intf.moveToBlock(BI.MBB->getNumber()); 795ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " -> EB#" 7962dfbb3e9125aa0a66feab7a7638815b57da85968Jakob Stoklund Olesen << Bundles->getBundle(BI.MBB->getNumber(), 1) 797612f7807c581eafb7c8105e1a55c8d839033bfb3Jakob Stoklund Olesen << " [" << Start << ';' 798612f7807c581eafb7c8105e1a55c8d839033bfb3Jakob Stoklund Olesen << SA->getLastSplitPoint(BI.MBB->getNumber()) << '-' << Stop 799612f7807c581eafb7c8105e1a55c8d839033bfb3Jakob Stoklund Olesen << ") intf [" << Intf.first() << ';' << Intf.last() << ')'); 8002dfbb3e9125aa0a66feab7a7638815b57da85968Jakob Stoklund Olesen 8012dfbb3e9125aa0a66feab7a7638815b57da85968Jakob Stoklund Olesen // The interference interval should either be invalid or overlap MBB. 8026c8afd728eb02742ce320ecd39bcf3774d8423b7Jakob Stoklund Olesen assert((!Intf.hasInterference() || Intf.first() < Stop) 803eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen && "Bad interference"); 8046c8afd728eb02742ce320ecd39bcf3774d8423b7Jakob Stoklund Olesen assert((!Intf.hasInterference() || Intf.last() > Start) 80536d61863bc83bd2301e0224adc560098b35ec0dcJakob Stoklund Olesen && "Bad interference"); 806ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 807ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Check interference leaving the block. 808eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen if (!Intf.hasInterference()) { 809ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Block is interference-free. 810ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen DEBUG(dbgs() << ", no interference"); 811ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen if (!BI.LiveThrough) { 812ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen DEBUG(dbgs() << ", not live-through.\n"); 813a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen SE->useIntv(SE->enterIntvBefore(BI.FirstUse), Stop); 814ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen continue; 815ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen } 816ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen if (!RegIn) { 817ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Block is live-through, but entry bundle is on the stack. 818ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Reload just before the first use. 819ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen DEBUG(dbgs() << ", not live-in, enter before first use.\n"); 8206c8afd728eb02742ce320ecd39bcf3774d8423b7Jakob Stoklund Olesen SE->useIntv(SE->enterIntvBefore(BI.FirstUse), Stop); 821ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen continue; 822ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen } 823ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen DEBUG(dbgs() << ", live-through.\n"); 824ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen continue; 825ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen } 826ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 827ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Block has interference. 828eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen DEBUG(dbgs() << ", interference to " << Intf.last()); 829fe3f99f95c7c9ceaac3ceebbea31e40cfbc157e3Jakob Stoklund Olesen 830a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen if (!BI.LiveThrough && Intf.last() <= BI.FirstUse) { 831fe3f99f95c7c9ceaac3ceebbea31e40cfbc157e3Jakob Stoklund Olesen // The interference doesn't reach the outgoing segment. 832a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen DEBUG(dbgs() << " doesn't affect def from " << BI.FirstUse << '\n'); 833a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen SE->useIntv(BI.FirstUse, Stop); 834fe3f99f95c7c9ceaac3ceebbea31e40cfbc157e3Jakob Stoklund Olesen continue; 835fe3f99f95c7c9ceaac3ceebbea31e40cfbc157e3Jakob Stoklund Olesen } 836fe3f99f95c7c9ceaac3ceebbea31e40cfbc157e3Jakob Stoklund Olesen 837612f7807c581eafb7c8105e1a55c8d839033bfb3Jakob Stoklund Olesen SlotIndex LastSplitPoint = SA->getLastSplitPoint(BI.MBB->getNumber()); 838eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen if (Intf.last().getBoundaryIndex() < BI.LastUse) { 839ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // There are interference-free uses at the end of the block. 840ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Find the first use that can get the live-out register. 841c0de99571297720a37ae405c77fb2ef4aaf00ccdJakob Stoklund Olesen SmallVectorImpl<SlotIndex>::const_iterator UI = 842fe3f99f95c7c9ceaac3ceebbea31e40cfbc157e3Jakob Stoklund Olesen std::lower_bound(SA->UseSlots.begin(), SA->UseSlots.end(), 843eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen Intf.last().getBoundaryIndex()); 844c0de99571297720a37ae405c77fb2ef4aaf00ccdJakob Stoklund Olesen assert(UI != SA->UseSlots.end() && "Couldn't find last use"); 845c0de99571297720a37ae405c77fb2ef4aaf00ccdJakob Stoklund Olesen SlotIndex Use = *UI; 846c0de99571297720a37ae405c77fb2ef4aaf00ccdJakob Stoklund Olesen assert(Use <= BI.LastUse && "Couldn't find last use"); 8478a2bbdeee24b40da6187199658646d04329c139eJakob Stoklund Olesen // Only attempt a split befroe the last split point. 848612f7807c581eafb7c8105e1a55c8d839033bfb3Jakob Stoklund Olesen if (Use.getBaseIndex() <= LastSplitPoint) { 8498a2bbdeee24b40da6187199658646d04329c139eJakob Stoklund Olesen DEBUG(dbgs() << ", free use at " << Use << ".\n"); 850bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen SlotIndex SegStart = SE->enterIntvBefore(Use); 851eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen assert(SegStart >= Intf.last() && "Couldn't avoid interference"); 852612f7807c581eafb7c8105e1a55c8d839033bfb3Jakob Stoklund Olesen assert(SegStart < LastSplitPoint && "Impossible split point"); 8536c8afd728eb02742ce320ecd39bcf3774d8423b7Jakob Stoklund Olesen SE->useIntv(SegStart, Stop); 8548a2bbdeee24b40da6187199658646d04329c139eJakob Stoklund Olesen continue; 8558a2bbdeee24b40da6187199658646d04329c139eJakob Stoklund Olesen } 856ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen } 857ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 858ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Interference is after the last use. 859ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen DEBUG(dbgs() << " after last use.\n"); 860bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen SlotIndex SegStart = SE->enterIntvAtEnd(*BI.MBB); 861eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen assert(SegStart >= Intf.last() && "Couldn't avoid interference"); 862ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen } 863ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 864ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Now all defs leading to live bundles are handled, do everything else. 865db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen for (unsigned i = 0; i != UseBlocks.size(); ++i) { 866db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen const SplitAnalysis::BlockInfo &BI = UseBlocks[i]; 867ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen bool RegIn = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 0)]; 868ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen bool RegOut = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 1)]; 869ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 870ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Is the register live-in? 871ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen if (!BI.LiveIn || !RegIn) 872ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen continue; 873ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 874ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // We have an incoming register. Check for interference. 8756c8afd728eb02742ce320ecd39bcf3774d8423b7Jakob Stoklund Olesen SlotIndex Start, Stop; 8766c8afd728eb02742ce320ecd39bcf3774d8423b7Jakob Stoklund Olesen tie(Start, Stop) = Indexes->getMBBRange(BI.MBB); 877eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen Intf.moveToBlock(BI.MBB->getNumber()); 878ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen DEBUG(dbgs() << "EB#" << Bundles->getBundle(BI.MBB->getNumber(), 0) 8796c8afd728eb02742ce320ecd39bcf3774d8423b7Jakob Stoklund Olesen << " -> BB#" << BI.MBB->getNumber() << " [" << Start << ';' 880612f7807c581eafb7c8105e1a55c8d839033bfb3Jakob Stoklund Olesen << SA->getLastSplitPoint(BI.MBB->getNumber()) << '-' << Stop 881612f7807c581eafb7c8105e1a55c8d839033bfb3Jakob Stoklund Olesen << ')'); 882ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 883ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Check interference entering the block. 884eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen if (!Intf.hasInterference()) { 885ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Block is interference-free. 886ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen DEBUG(dbgs() << ", no interference"); 887ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen if (!BI.LiveThrough) { 888ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen DEBUG(dbgs() << ", killed in block.\n"); 889a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen SE->useIntv(Start, SE->leaveIntvAfter(BI.LastUse)); 890ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen continue; 891ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen } 892ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen if (!RegOut) { 893612f7807c581eafb7c8105e1a55c8d839033bfb3Jakob Stoklund Olesen SlotIndex LastSplitPoint = SA->getLastSplitPoint(BI.MBB->getNumber()); 894ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Block is live-through, but exit bundle is on the stack. 895ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Spill immediately after the last use. 896612f7807c581eafb7c8105e1a55c8d839033bfb3Jakob Stoklund Olesen if (BI.LastUse < LastSplitPoint) { 8975c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen DEBUG(dbgs() << ", uses, stack-out.\n"); 8986c8afd728eb02742ce320ecd39bcf3774d8423b7Jakob Stoklund Olesen SE->useIntv(Start, SE->leaveIntvAfter(BI.LastUse)); 8995c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen continue; 9005c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen } 9015c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen // The last use is after the last split point, it is probably an 9025c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen // indirect jump. 9035c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen DEBUG(dbgs() << ", uses at " << BI.LastUse << " after split point " 904612f7807c581eafb7c8105e1a55c8d839033bfb3Jakob Stoklund Olesen << LastSplitPoint << ", stack-out.\n"); 905612f7807c581eafb7c8105e1a55c8d839033bfb3Jakob Stoklund Olesen SlotIndex SegEnd = SE->leaveIntvBefore(LastSplitPoint); 9066c8afd728eb02742ce320ecd39bcf3774d8423b7Jakob Stoklund Olesen SE->useIntv(Start, SegEnd); 9075c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen // Run a double interval from the split to the last use. 9085c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen // This makes it possible to spill the complement without affecting the 9095c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen // indirect branch. 910bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen SE->overlapIntv(SegEnd, BI.LastUse); 911ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen continue; 912ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen } 913ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Register is live-through. 914ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen DEBUG(dbgs() << ", uses, live-through.\n"); 9156c8afd728eb02742ce320ecd39bcf3774d8423b7Jakob Stoklund Olesen SE->useIntv(Start, Stop); 916ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen continue; 917ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen } 918ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 919ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Block has interference. 920eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen DEBUG(dbgs() << ", interference from " << Intf.first()); 921fe3f99f95c7c9ceaac3ceebbea31e40cfbc157e3Jakob Stoklund Olesen 922a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen if (!BI.LiveThrough && Intf.first() >= BI.LastUse) { 923fe3f99f95c7c9ceaac3ceebbea31e40cfbc157e3Jakob Stoklund Olesen // The interference doesn't reach the outgoing segment. 924a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen DEBUG(dbgs() << " doesn't affect kill at " << BI.LastUse << '\n'); 925a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen SE->useIntv(Start, BI.LastUse); 926fe3f99f95c7c9ceaac3ceebbea31e40cfbc157e3Jakob Stoklund Olesen continue; 927fe3f99f95c7c9ceaac3ceebbea31e40cfbc157e3Jakob Stoklund Olesen } 928fe3f99f95c7c9ceaac3ceebbea31e40cfbc157e3Jakob Stoklund Olesen 929eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen if (Intf.first().getBaseIndex() > BI.FirstUse) { 930ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // There are interference-free uses at the beginning of the block. 931ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Find the last use that can get the register. 932c0de99571297720a37ae405c77fb2ef4aaf00ccdJakob Stoklund Olesen SmallVectorImpl<SlotIndex>::const_iterator UI = 933fe3f99f95c7c9ceaac3ceebbea31e40cfbc157e3Jakob Stoklund Olesen std::lower_bound(SA->UseSlots.begin(), SA->UseSlots.end(), 934eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen Intf.first().getBaseIndex()); 935c0de99571297720a37ae405c77fb2ef4aaf00ccdJakob Stoklund Olesen assert(UI != SA->UseSlots.begin() && "Couldn't find first use"); 936c0de99571297720a37ae405c77fb2ef4aaf00ccdJakob Stoklund Olesen SlotIndex Use = (--UI)->getBoundaryIndex(); 937c0de99571297720a37ae405c77fb2ef4aaf00ccdJakob Stoklund Olesen DEBUG(dbgs() << ", free use at " << *UI << ".\n"); 938bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen SlotIndex SegEnd = SE->leaveIntvAfter(Use); 939eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen assert(SegEnd <= Intf.first() && "Couldn't avoid interference"); 9406c8afd728eb02742ce320ecd39bcf3774d8423b7Jakob Stoklund Olesen SE->useIntv(Start, SegEnd); 941ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen continue; 942ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen } 943ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 944ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Interference is before the first use. 945ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen DEBUG(dbgs() << " before first use.\n"); 946bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen SlotIndex SegEnd = SE->leaveIntvAtTop(*BI.MBB); 947eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen assert(SegEnd <= Intf.first() && "Couldn't avoid interference"); 948ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen } 949ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 950db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen // Handle live-through blocks. 9515db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen for (unsigned i = 0, e = Cand.ActiveBlocks.size(); i != e; ++i) { 9525db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen unsigned Number = Cand.ActiveBlocks[i]; 953db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen bool RegIn = LiveBundles[Bundles->getBundle(Number, 0)]; 954db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen bool RegOut = LiveBundles[Bundles->getBundle(Number, 1)]; 955db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen DEBUG(dbgs() << "Live through BB#" << Number << '\n'); 956db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen if (RegIn && RegOut) { 957db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen Intf.moveToBlock(Number); 958db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen if (!Intf.hasInterference()) { 959db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen SE->useIntv(Indexes->getMBBStartIdx(Number), 960db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen Indexes->getMBBEndIdx(Number)); 961db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen continue; 962db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen } 963db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen } 964db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen MachineBasicBlock *MBB = MF->getBlockNumbered(Number); 965db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen if (RegIn) 966db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen SE->leaveIntvAtTop(*MBB); 967db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen if (RegOut) 968db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen SE->enterIntvAtEnd(*MBB); 969db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen } 970db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen 9710db841f9c2b9a25fb5ecb36e350d3a802c35654cJakob Stoklund Olesen ++NumGlobalSplits; 972ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 9735928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen SmallVector<unsigned, 8> IntvMap; 9745928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen SE->finish(&IntvMap); 975f42b66169d75301346e3685fd2b3e45e47806367Jakob Stoklund Olesen DebugVars->splitRegister(VirtReg.reg, LREdit.regs()); 976f42b66169d75301346e3685fd2b3e45e47806367Jakob Stoklund Olesen 9775928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen LRStage.resize(MRI->getNumVirtRegs()); 978b2abfa0bf30edf292a27a06e091d03983e644c9bJakob Stoklund Olesen unsigned OrigBlocks = SA->getNumLiveBlocks(); 9795928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen 9805928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen // Sort out the new intervals created by splitting. We get four kinds: 9815928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen // - Remainder intervals should not be split again. 9825928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen // - Candidate intervals can be assigned to Cand.PhysReg. 9835928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen // - Block-local splits are candidates for local splitting. 9845928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen // - DCE leftovers should go back on the queue. 9855928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen for (unsigned i = 0, e = LREdit.size(); i != e; ++i) { 9865928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen unsigned Reg = LREdit.get(i)->reg; 9875928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen 9885928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen // Ignore old intervals from DCE. 9895928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen if (LRStage[Reg] != RS_New) 9905928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen continue; 9915928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen 9925928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen // Remainder interval. Don't try splitting again, spill if it doesn't 9935928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen // allocate. 9945928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen if (IntvMap[i] == 0) { 9955928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen LRStage[Reg] = RS_Global; 9965928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen continue; 9975928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen } 9985928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen 9999f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen // Main interval. Allow repeated splitting as long as the number of live 10009f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen // blocks is strictly decreasing. 10019f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen if (IntvMap[i] == MainIntv) { 10029f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen if (SA->countLiveBlocks(LREdit.get(i)) >= OrigBlocks) { 10039f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen DEBUG(dbgs() << "Main interval covers the same " << OrigBlocks 10049f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen << " blocks as original.\n"); 10059f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen // Don't allow repeated splitting as a safe guard against looping. 10069f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen LRStage[Reg] = RS_Global; 10079f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen } 10089f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen continue; 10099f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen } 10109f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen 10119f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen // Other intervals are treated as new. This includes local intervals created 10129f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen // for blocks with multiple uses, and anything created by DCE. 10135928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen } 10145928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen 1015eb29157d80847c207b77910bcd40a6a6c91ca5c5Jakob Stoklund Olesen if (VerifyEnabled) 1016ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen MF->verify(this, "After splitting live range around region"); 1017ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen} 1018ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 1019b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesenunsigned RAGreedy::tryRegionSplit(LiveInterval &VirtReg, AllocationOrder &Order, 1020b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen SmallVectorImpl<LiveInterval*> &NewVRegs) { 1021200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen float BestCost = Hysteresis * calcSpillCost(); 1022200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen DEBUG(dbgs() << "Cost of isolating all blocks = " << BestCost << '\n'); 10235db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen const unsigned NoCand = ~0u; 10245db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen unsigned BestCand = NoCand; 102596dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen 1026b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen Order.rewind(); 102796dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen for (unsigned Cand = 0; unsigned PhysReg = Order.next(); ++Cand) { 102896dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen if (GlobalCand.size() <= Cand) 102996dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen GlobalCand.resize(Cand+1); 10305db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen GlobalCand[Cand].reset(PhysReg); 103196dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen 10325db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen SpillPlacer->prepare(GlobalCand[Cand].LiveBundles); 10331b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen float Cost; 1034f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen InterferenceCache::Cursor Intf(IntfCache, PhysReg); 1035f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen if (!addSplitConstraints(Intf, Cost)) { 1036f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen DEBUG(dbgs() << PrintReg(PhysReg, TRI) << "\tno positive bundles\n"); 10371b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen continue; 10381b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen } 1039f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen DEBUG(dbgs() << PrintReg(PhysReg, TRI) << "\tstatic = " << Cost); 1040200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen if (Cost >= BestCost) { 1041200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen DEBUG({ 1042200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen if (BestCand == NoCand) 1043200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen dbgs() << " worse than no bundles\n"; 1044200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen else 1045200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen dbgs() << " worse than " 1046200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen << PrintReg(GlobalCand[BestCand].PhysReg, TRI) << '\n'; 1047200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen }); 1048b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen continue; 1049874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen } 10505db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen growRegion(GlobalCand[Cand], Intf); 1051ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 10529efa2a263ea470caacef1c85f6ca45e32bf516d3Jakob Stoklund Olesen SpillPlacer->finish(); 10539efa2a263ea470caacef1c85f6ca45e32bf516d3Jakob Stoklund Olesen 1054ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // No live bundles, defer to splitSingleBlocks(). 10555db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen if (!GlobalCand[Cand].LiveBundles.any()) { 1056874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen DEBUG(dbgs() << " no bundles.\n"); 1057ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen continue; 1058874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen } 1059ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 10605db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen Cost += calcGlobalSplitCost(GlobalCand[Cand], Intf); 1061874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen DEBUG({ 1062874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen dbgs() << ", total = " << Cost << " with bundles"; 10635db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen for (int i = GlobalCand[Cand].LiveBundles.find_first(); i>=0; 10645db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen i = GlobalCand[Cand].LiveBundles.find_next(i)) 1065874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen dbgs() << " EB#" << i; 1066874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen dbgs() << ".\n"; 1067874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen }); 1068200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen if (Cost < BestCost) { 10695db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen BestCand = Cand; 1070200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen BestCost = Hysteresis * Cost; // Prevent rounding effects. 1071b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen } 1072b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen } 1073ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 10745db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen if (BestCand == NoCand) 1075ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen return 0; 1076ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 10775db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen splitAroundRegion(VirtReg, GlobalCand[BestCand], NewVRegs); 1078b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen return 0; 1079b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen} 1080b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 1081ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 1082ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen//===----------------------------------------------------------------------===// 1083034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen// Local Splitting 1084034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 1085034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1086034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1087034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// calcGapWeights - Compute the maximum spill weight that needs to be evicted 1088034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// in order to use PhysReg between two entries in SA->UseSlots. 1089034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// 1090034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// GapWeight[i] represents the gap between UseSlots[i] and UseSlots[i+1]. 1091034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// 1092034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesenvoid RAGreedy::calcGapWeights(unsigned PhysReg, 1093034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen SmallVectorImpl<float> &GapWeight) { 1094db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen assert(SA->getUseBlocks().size() == 1 && "Not a local interval"); 1095db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen const SplitAnalysis::BlockInfo &BI = SA->getUseBlocks().front(); 1096034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const SmallVectorImpl<SlotIndex> &Uses = SA->UseSlots; 1097034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const unsigned NumGaps = Uses.size()-1; 1098034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1099034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Start and end points for the interference check. 1100034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen SlotIndex StartIdx = BI.LiveIn ? BI.FirstUse.getBaseIndex() : BI.FirstUse; 1101034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen SlotIndex StopIdx = BI.LiveOut ? BI.LastUse.getBoundaryIndex() : BI.LastUse; 1102034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1103034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen GapWeight.assign(NumGaps, 0.0f); 1104034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1105034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Add interference from each overlapping register. 1106034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen for (const unsigned *AI = TRI->getOverlaps(PhysReg); *AI; ++AI) { 1107034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (!query(const_cast<LiveInterval&>(SA->getParent()), *AI) 1108034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen .checkInterference()) 1109034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen continue; 1110034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1111034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // We know that VirtReg is a continuous interval from FirstUse to LastUse, 1112034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // so we don't need InterferenceQuery. 1113034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // 1114034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Interference that overlaps an instruction is counted in both gaps 1115034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // surrounding the instruction. The exception is interference before 1116034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // StartIdx and after StopIdx. 1117034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // 1118034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen LiveIntervalUnion::SegmentIter IntI = PhysReg2LiveUnion[*AI].find(StartIdx); 1119034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen for (unsigned Gap = 0; IntI.valid() && IntI.start() < StopIdx; ++IntI) { 1120034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Skip the gaps before IntI. 1121034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen while (Uses[Gap+1].getBoundaryIndex() < IntI.start()) 1122034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (++Gap == NumGaps) 1123034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen break; 1124034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (Gap == NumGaps) 1125034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen break; 1126034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1127034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Update the gaps covered by IntI. 1128034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const float weight = IntI.value()->weight; 1129034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen for (; Gap != NumGaps; ++Gap) { 1130034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen GapWeight[Gap] = std::max(GapWeight[Gap], weight); 1131034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (Uses[Gap+1].getBaseIndex() >= IntI.stop()) 1132034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen break; 1133034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1134034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (Gap == NumGaps) 1135034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen break; 1136034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1137034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1138034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen} 1139034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1140034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// getPrevMappedIndex - Return the slot index of the last non-copy instruction 1141034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// before MI that has a slot index. If MI is the first mapped instruction in 1142034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// its block, return the block start index instead. 1143034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// 1144034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund OlesenSlotIndex RAGreedy::getPrevMappedIndex(const MachineInstr *MI) { 1145034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen assert(MI && "Missing MachineInstr"); 1146034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const MachineBasicBlock *MBB = MI->getParent(); 1147034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen MachineBasicBlock::const_iterator B = MBB->begin(), I = MI; 1148034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen while (I != B) 1149034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (!(--I)->isDebugValue() && !I->isCopy()) 1150034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen return Indexes->getInstructionIndex(I); 1151034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen return Indexes->getMBBStartIdx(MBB); 1152034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen} 1153034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1154034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// calcPrevSlots - Fill in the PrevSlot array with the index of the previous 1155034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// real non-copy instruction for each instruction in SA->UseSlots. 1156034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// 1157034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesenvoid RAGreedy::calcPrevSlots() { 1158034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const SmallVectorImpl<SlotIndex> &Uses = SA->UseSlots; 1159034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen PrevSlot.clear(); 1160034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen PrevSlot.reserve(Uses.size()); 1161034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen for (unsigned i = 0, e = Uses.size(); i != e; ++i) { 1162034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const MachineInstr *MI = Indexes->getInstructionFromIndex(Uses[i]); 1163034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen PrevSlot.push_back(getPrevMappedIndex(MI).getDefIndex()); 1164034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1165034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen} 1166034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1167034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// nextSplitPoint - Find the next index into SA->UseSlots > i such that it may 1168034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// be beneficial to split before UseSlots[i]. 1169034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// 1170034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// 0 is always a valid split point 1171034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesenunsigned RAGreedy::nextSplitPoint(unsigned i) { 1172034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const SmallVectorImpl<SlotIndex> &Uses = SA->UseSlots; 1173034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const unsigned Size = Uses.size(); 1174034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen assert(i != Size && "No split points after the end"); 1175034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Allow split before i when Uses[i] is not adjacent to the previous use. 1176034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen while (++i != Size && PrevSlot[i].getBaseIndex() <= Uses[i-1].getBaseIndex()) 1177034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen ; 1178034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen return i; 1179034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen} 1180034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1181034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// tryLocalSplit - Try to split VirtReg into smaller intervals inside its only 1182034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// basic block. 1183034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// 1184034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesenunsigned RAGreedy::tryLocalSplit(LiveInterval &VirtReg, AllocationOrder &Order, 1185034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen SmallVectorImpl<LiveInterval*> &NewVRegs) { 1186db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen assert(SA->getUseBlocks().size() == 1 && "Not a local interval"); 1187db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen const SplitAnalysis::BlockInfo &BI = SA->getUseBlocks().front(); 1188034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1189034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Note that it is possible to have an interval that is live-in or live-out 1190034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // while only covering a single block - A phi-def can use undef values from 1191034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // predecessors, and the block could be a single-block loop. 1192034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // We don't bother doing anything clever about such a case, we simply assume 1193034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // that the interval is continuous from FirstUse to LastUse. We should make 1194034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // sure that we don't do anything illegal to such an interval, though. 1195034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1196034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const SmallVectorImpl<SlotIndex> &Uses = SA->UseSlots; 1197034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (Uses.size() <= 2) 1198034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen return 0; 1199034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const unsigned NumGaps = Uses.size()-1; 1200034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1201034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen DEBUG({ 1202034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen dbgs() << "tryLocalSplit: "; 1203034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen for (unsigned i = 0, e = Uses.size(); i != e; ++i) 1204034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen dbgs() << ' ' << SA->UseSlots[i]; 1205034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen dbgs() << '\n'; 1206034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen }); 1207034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1208034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // For every use, find the previous mapped non-copy instruction. 1209034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // We use this to detect valid split points, and to estimate new interval 1210034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // sizes. 1211034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen calcPrevSlots(); 1212034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1213034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen unsigned BestBefore = NumGaps; 1214034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen unsigned BestAfter = 0; 1215034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen float BestDiff = 0; 1216034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 121740a42a2ccaaa19a109667ed7abf224cc8733cd9cJakob Stoklund Olesen const float blockFreq = SpillPlacer->getBlockFrequency(BI.MBB->getNumber()); 1218034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen SmallVector<float, 8> GapWeight; 1219034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1220034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen Order.rewind(); 1221034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen while (unsigned PhysReg = Order.next()) { 1222034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Keep track of the largest spill weight that would need to be evicted in 1223034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // order to make use of PhysReg between UseSlots[i] and UseSlots[i+1]. 1224034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen calcGapWeights(PhysReg, GapWeight); 1225034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1226034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Try to find the best sequence of gaps to close. 1227034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // The new spill weight must be larger than any gap interference. 1228034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1229034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // We will split before Uses[SplitBefore] and after Uses[SplitAfter]. 1230034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen unsigned SplitBefore = 0, SplitAfter = nextSplitPoint(1) - 1; 1231034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1232034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // MaxGap should always be max(GapWeight[SplitBefore..SplitAfter-1]). 1233034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // It is the spill weight that needs to be evicted. 1234034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen float MaxGap = GapWeight[0]; 1235034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen for (unsigned i = 1; i != SplitAfter; ++i) 1236034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen MaxGap = std::max(MaxGap, GapWeight[i]); 1237034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1238034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen for (;;) { 1239034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Live before/after split? 1240034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const bool LiveBefore = SplitBefore != 0 || BI.LiveIn; 1241034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const bool LiveAfter = SplitAfter != NumGaps || BI.LiveOut; 1242034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1243034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen DEBUG(dbgs() << PrintReg(PhysReg, TRI) << ' ' 1244034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen << Uses[SplitBefore] << '-' << Uses[SplitAfter] 1245034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen << " i=" << MaxGap); 1246034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1247034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Stop before the interval gets so big we wouldn't be making progress. 1248034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (!LiveBefore && !LiveAfter) { 1249034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen DEBUG(dbgs() << " all\n"); 1250034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen break; 1251034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1252034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Should the interval be extended or shrunk? 1253034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen bool Shrink = true; 1254034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (MaxGap < HUGE_VALF) { 1255034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Estimate the new spill weight. 1256034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // 1257034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Each instruction reads and writes the register, except the first 1258034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // instr doesn't read when !FirstLive, and the last instr doesn't write 1259034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // when !LastLive. 1260034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // 1261034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // We will be inserting copies before and after, so the total number of 1262034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // reads and writes is 2 * EstUses. 1263034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // 1264034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const unsigned EstUses = 2*(SplitAfter - SplitBefore) + 1265034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 2*(LiveBefore + LiveAfter); 1266034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1267034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Try to guess the size of the new interval. This should be trivial, 1268034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // but the slot index of an inserted copy can be a lot smaller than the 1269034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // instruction it is inserted before if there are many dead indexes 1270034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // between them. 1271034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // 1272034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // We measure the distance from the instruction before SplitBefore to 1273034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // get a conservative estimate. 1274034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // 1275034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // The final distance can still be different if inserting copies 1276034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // triggers a slot index renumbering. 1277034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // 1278034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const float EstWeight = normalizeSpillWeight(blockFreq * EstUses, 1279034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen PrevSlot[SplitBefore].distance(Uses[SplitAfter])); 1280034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Would this split be possible to allocate? 1281034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Never allocate all gaps, we wouldn't be making progress. 128266446c803a11a26e4bb39b74091d146ac850ae4cJakob Stoklund Olesen DEBUG(dbgs() << " w=" << EstWeight); 128366446c803a11a26e4bb39b74091d146ac850ae4cJakob Stoklund Olesen if (EstWeight * Hysteresis >= MaxGap) { 1284034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen Shrink = false; 128566446c803a11a26e4bb39b74091d146ac850ae4cJakob Stoklund Olesen float Diff = EstWeight - MaxGap; 1286034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (Diff > BestDiff) { 1287034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen DEBUG(dbgs() << " (best)"); 128866446c803a11a26e4bb39b74091d146ac850ae4cJakob Stoklund Olesen BestDiff = Hysteresis * Diff; 1289034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen BestBefore = SplitBefore; 1290034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen BestAfter = SplitAfter; 1291034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1292034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1293034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1294034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1295034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Try to shrink. 1296034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (Shrink) { 1297034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen SplitBefore = nextSplitPoint(SplitBefore); 1298034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (SplitBefore < SplitAfter) { 1299034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen DEBUG(dbgs() << " shrink\n"); 1300034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Recompute the max when necessary. 1301034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (GapWeight[SplitBefore - 1] >= MaxGap) { 1302034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen MaxGap = GapWeight[SplitBefore]; 1303034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen for (unsigned i = SplitBefore + 1; i != SplitAfter; ++i) 1304034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen MaxGap = std::max(MaxGap, GapWeight[i]); 1305034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1306034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen continue; 1307034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1308034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen MaxGap = 0; 1309034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1310034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1311034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Try to extend the interval. 1312034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (SplitAfter >= NumGaps) { 1313034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen DEBUG(dbgs() << " end\n"); 1314034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen break; 1315034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1316034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1317034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen DEBUG(dbgs() << " extend\n"); 1318034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen for (unsigned e = nextSplitPoint(SplitAfter + 1) - 1; 1319034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen SplitAfter != e; ++SplitAfter) 1320034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen MaxGap = std::max(MaxGap, GapWeight[SplitAfter]); 1321034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen continue; 1322034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1323034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1324034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1325034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Didn't find any candidates? 1326034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (BestBefore == NumGaps) 1327034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen return 0; 1328034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1329034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen DEBUG(dbgs() << "Best local split range: " << Uses[BestBefore] 1330034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen << '-' << Uses[BestAfter] << ", " << BestDiff 1331034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen << ", " << (BestAfter - BestBefore + 1) << " instrs\n"); 1332034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 133392a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen LiveRangeEdit LREdit(VirtReg, NewVRegs, this); 1334bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen SE->reset(LREdit); 1335bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen 1336bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen SE->openIntv(); 1337bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen SlotIndex SegStart = SE->enterIntvBefore(Uses[BestBefore]); 1338bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen SlotIndex SegStop = SE->leaveIntvAfter(Uses[BestAfter]); 1339bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen SE->useIntv(SegStart, SegStop); 1340bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen SE->finish(); 1341f42b66169d75301346e3685fd2b3e45e47806367Jakob Stoklund Olesen DebugVars->splitRegister(VirtReg.reg, LREdit.regs()); 134222a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen setStage(NewVRegs.begin(), NewVRegs.end(), RS_Local); 13430db841f9c2b9a25fb5ecb36e350d3a802c35654cJakob Stoklund Olesen ++NumLocalSplits; 1344034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1345034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen return 0; 1346034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen} 1347034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1348034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 1349ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen// Live Range Splitting 1350ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen//===----------------------------------------------------------------------===// 1351ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 1352ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen/// trySplit - Try to split VirtReg or one of its interferences, making it 1353ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen/// assignable. 1354ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen/// @return Physreg when VirtReg may be assigned and/or new NewVRegs. 1355ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesenunsigned RAGreedy::trySplit(LiveInterval &VirtReg, AllocationOrder &Order, 1356ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen SmallVectorImpl<LiveInterval*>&NewVRegs) { 1357034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Local intervals are handled separately. 1358a2ebf60ef2c434428af7f810b13327ab50245a67Jakob Stoklund Olesen if (LIS->intervalIsInOneMBB(VirtReg)) { 1359a2ebf60ef2c434428af7f810b13327ab50245a67Jakob Stoklund Olesen NamedRegionTimer T("Local Splitting", TimerGroupName, TimePassesIsEnabled); 136022a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen SA->analyze(&VirtReg); 1361034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen return tryLocalSplit(VirtReg, Order, NewVRegs); 1362a2ebf60ef2c434428af7f810b13327ab50245a67Jakob Stoklund Olesen } 1363a2ebf60ef2c434428af7f810b13327ab50245a67Jakob Stoklund Olesen 1364a2ebf60ef2c434428af7f810b13327ab50245a67Jakob Stoklund Olesen NamedRegionTimer T("Global Splitting", TimerGroupName, TimePassesIsEnabled); 1365ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 136622a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // Don't iterate global splitting. 136722a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // Move straight to spilling if this range was produced by a global split. 1368fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen if (getStage(VirtReg) >= RS_Global) 136922a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen return 0; 137022a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen 137122a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen SA->analyze(&VirtReg); 137222a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen 13737d6b6a05b549da70b4473f015c97954c2a422724Jakob Stoklund Olesen // FIXME: SplitAnalysis may repair broken live ranges coming from the 13747d6b6a05b549da70b4473f015c97954c2a422724Jakob Stoklund Olesen // coalescer. That may cause the range to become allocatable which means that 13757d6b6a05b549da70b4473f015c97954c2a422724Jakob Stoklund Olesen // tryRegionSplit won't be making progress. This check should be replaced with 13767d6b6a05b549da70b4473f015c97954c2a422724Jakob Stoklund Olesen // an assertion when the coalescer is fixed. 13777d6b6a05b549da70b4473f015c97954c2a422724Jakob Stoklund Olesen if (SA->didRepairRange()) { 13787d6b6a05b549da70b4473f015c97954c2a422724Jakob Stoklund Olesen // VirtReg has changed, so all cached queries are invalid. 1379bdda37d7fbafe6876f248341837423a4100f95a5Jakob Stoklund Olesen invalidateVirtRegs(); 13807d6b6a05b549da70b4473f015c97954c2a422724Jakob Stoklund Olesen if (unsigned PhysReg = tryAssign(VirtReg, Order, NewVRegs)) 13817d6b6a05b549da70b4473f015c97954c2a422724Jakob Stoklund Olesen return PhysReg; 13827d6b6a05b549da70b4473f015c97954c2a422724Jakob Stoklund Olesen } 13837d6b6a05b549da70b4473f015c97954c2a422724Jakob Stoklund Olesen 1384ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // First try to split around a region spanning multiple blocks. 1385fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen unsigned PhysReg = tryRegionSplit(VirtReg, Order, NewVRegs); 1386fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen if (PhysReg || !NewVRegs.empty()) 1387fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen return PhysReg; 1388ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 1389ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Then isolate blocks with multiple uses. 1390fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen SplitAnalysis::BlockPtrSet Blocks; 1391fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen if (SA->getMultiUseBlocks(Blocks)) { 1392fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen LiveRangeEdit LREdit(VirtReg, NewVRegs, this); 1393fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen SE->reset(LREdit); 1394fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen SE->splitSingleBlocks(Blocks); 1395fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen setStage(NewVRegs.begin(), NewVRegs.end(), RS_Global); 1396fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen if (VerifyEnabled) 1397fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen MF->verify(this, "After splitting live range around basic blocks"); 1398ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen } 1399ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 1400ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Don't assign any physregs. 1401ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen return 0; 1402ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen} 1403ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 1404ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 1405b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen//===----------------------------------------------------------------------===// 1406770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen// Main Entry Point 1407770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen//===----------------------------------------------------------------------===// 1408770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen 1409770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesenunsigned RAGreedy::selectOrSplit(LiveInterval &VirtReg, 1410ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen SmallVectorImpl<LiveInterval*> &NewVRegs) { 1411770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen // First try assigning a free register. 14125f2316a3b55f88dab2190212210770180a32aa95Jakob Stoklund Olesen AllocationOrder Order(VirtReg.reg, *VRM, RegClassInfo); 14136bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen if (unsigned PhysReg = tryAssign(VirtReg, Order, NewVRegs)) 14146bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen return PhysReg; 1415b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick 1416b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen LiveRangeStage Stage = getStage(VirtReg); 1417b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen DEBUG(dbgs() << StageName[Stage] << '\n'); 1418b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen 141976395c9a31444fa86514473e0852cdd67752d0e8Jakob Stoklund Olesen // Try to evict a less worthy live range, but only for ranges from the primary 142076395c9a31444fa86514473e0852cdd67752d0e8Jakob Stoklund Olesen // queue. The RS_Second ranges already failed to do this, and they should not 142176395c9a31444fa86514473e0852cdd67752d0e8Jakob Stoklund Olesen // get a second chance until they have been split. 142276395c9a31444fa86514473e0852cdd67752d0e8Jakob Stoklund Olesen if (Stage != RS_Second) 142376395c9a31444fa86514473e0852cdd67752d0e8Jakob Stoklund Olesen if (unsigned PhysReg = tryEvict(VirtReg, Order, NewVRegs)) 142476395c9a31444fa86514473e0852cdd67752d0e8Jakob Stoklund Olesen return PhysReg; 1425b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick 1426ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen assert(NewVRegs.empty() && "Cannot append to existing NewVRegs"); 1427ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 1428107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen // The first time we see a live range, don't try to split or spill. 1429107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen // Wait until the second time, when all smaller ranges have been allocated. 1430107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen // This gives a better picture of the interference to split around. 1431f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund Olesen if (Stage == RS_First) { 1432eb29157d80847c207b77910bcd40a6a6c91ca5c5Jakob Stoklund Olesen LRStage[VirtReg.reg] = RS_Second; 1433c1655e1a3c3a566b91b0513b56d61b58da1e36baJakob Stoklund Olesen DEBUG(dbgs() << "wait for second round\n"); 1434107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen NewVRegs.push_back(&VirtReg); 1435107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen return 0; 1436107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen } 1437107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen 1438bf4e10f2f69db24c107cb61d6fe10ed5b2047374Jakob Stoklund Olesen // If we couldn't allocate a register from spilling, there is probably some 1439bf4e10f2f69db24c107cb61d6fe10ed5b2047374Jakob Stoklund Olesen // invalid inline assembly. The base class wil report it. 1440bf4e10f2f69db24c107cb61d6fe10ed5b2047374Jakob Stoklund Olesen if (Stage >= RS_Spill) 1441bf4e10f2f69db24c107cb61d6fe10ed5b2047374Jakob Stoklund Olesen return ~0u; 144222a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen 144346c83c80c5737743c955ff007fa6409804a7abf0Jakob Stoklund Olesen // Try splitting VirtReg or interferences. 1444ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen unsigned PhysReg = trySplit(VirtReg, Order, NewVRegs); 1445ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen if (PhysReg || !NewVRegs.empty()) 1446b64d92e29f38002e52a22fe36ea2d488968e3537Jakob Stoklund Olesen return PhysReg; 1447b64d92e29f38002e52a22fe36ea2d488968e3537Jakob Stoklund Olesen 1448770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen // Finally spill VirtReg itself. 1449770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen NamedRegionTimer T("Spiller", TimerGroupName, TimePassesIsEnabled); 145047dbf6cef761c25cfeb0aa7d624a6f98288bb96aJakob Stoklund Olesen LiveRangeEdit LRE(VirtReg, NewVRegs, this); 145147dbf6cef761c25cfeb0aa7d624a6f98288bb96aJakob Stoklund Olesen spiller().spill(LRE); 14526094bd87d845afabba5b99ec4848fa6116bac682Jakob Stoklund Olesen setStage(NewVRegs.begin(), NewVRegs.end(), RS_Spill); 1453cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 1454c46570dc05851395829bef904bb6ddb1260400d1Jakob Stoklund Olesen if (VerifyEnabled) 1455c46570dc05851395829bef904bb6ddb1260400d1Jakob Stoklund Olesen MF->verify(this, "After spilling"); 1456c46570dc05851395829bef904bb6ddb1260400d1Jakob Stoklund Olesen 1457cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen // The live virtual register requesting allocation was spilled, so tell 1458cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen // the caller not to allocate anything during this round. 1459cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen return 0; 1460cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen} 1461cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 1462cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesenbool RAGreedy::runOnMachineFunction(MachineFunction &mf) { 1463cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen DEBUG(dbgs() << "********** GREEDY REGISTER ALLOCATION **********\n" 1464cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen << "********** Function: " 1465cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen << ((Value*)mf.getFunction())->getName() << '\n'); 1466cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 1467cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen MF = &mf; 1468af24964251e27c2dd863239ba66ffd967b593be5Jakob Stoklund Olesen if (VerifyEnabled) 146989cab93fe999f6d81b4b99a71ac797b7ecfec277Jakob Stoklund Olesen MF->verify(this, "Before greedy register allocator"); 1470af24964251e27c2dd863239ba66ffd967b593be5Jakob Stoklund Olesen 14714680dec5fb3a1b624f13ca9b2a555ca90a07973eJakob Stoklund Olesen RegAllocBase::init(getAnalysis<VirtRegMap>(), getAnalysis<LiveIntervals>()); 1472b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen Indexes = &getAnalysis<SlotIndexes>(); 1473f428eb6c1b09a2322b7a577b0bf2e49dd107bceaJakob Stoklund Olesen DomTree = &getAnalysis<MachineDominatorTree>(); 1474f6dff84d4e44d6c4a46c4f8a18e13c78f804547cJakob Stoklund Olesen SpillerInstance.reset(createInlineSpiller(*this, *MF, *VRM)); 1475d0bb5e2ca05d9c942223bf05e5940bb0c6cc9d3fJakob Stoklund Olesen Loops = &getAnalysis<MachineLoopInfo>(); 1476d0bb5e2ca05d9c942223bf05e5940bb0c6cc9d3fJakob Stoklund Olesen LoopRanges = &getAnalysis<MachineLoopRanges>(); 1477b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen Bundles = &getAnalysis<EdgeBundles>(); 1478b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen SpillPlacer = &getAnalysis<SpillPlacement>(); 1479f42b66169d75301346e3685fd2b3e45e47806367Jakob Stoklund Olesen DebugVars = &getAnalysis<LiveDebugVariables>(); 1480b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 14811b847deb26b52051de39f4cbecd224c9fbd0d1c2Jakob Stoklund Olesen SA.reset(new SplitAnalysis(*VRM, *LIS, *Loops)); 1482bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen SE.reset(new SplitEditor(*SA, *LIS, *VRM, *DomTree)); 148322a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen LRStage.clear(); 148422a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen LRStage.resize(MRI->getNumVirtRegs()); 1485eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen IntfCache.init(MF, &PhysReg2LiveUnion[0], Indexes, TRI); 1486d0bb5e2ca05d9c942223bf05e5940bb0c6cc9d3fJakob Stoklund Olesen 1487cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen allocatePhysRegs(); 1488cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen addMBBLiveIns(MF); 14898a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen LIS->addKillFlags(); 1490cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 1491cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen // Run rewriter 1492533f58ecdd8a4732c2f0e149387c4d8d8d4142deJakob Stoklund Olesen { 1493533f58ecdd8a4732c2f0e149387c4d8d8d4142deJakob Stoklund Olesen NamedRegionTimer T("Rewriter", TimerGroupName, TimePassesIsEnabled); 1494ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen VRM->rewrite(Indexes); 1495533f58ecdd8a4732c2f0e149387c4d8d8d4142deJakob Stoklund Olesen } 1496cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 1497cfafc54040cc9722995558124f253d05a038176bJakob Stoklund Olesen // Write out new DBG_VALUE instructions. 1498f42b66169d75301346e3685fd2b3e45e47806367Jakob Stoklund Olesen DebugVars->emitDebugValues(VRM); 1499cfafc54040cc9722995558124f253d05a038176bJakob Stoklund Olesen 1500cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen // The pass output is in VirtRegMap. Release all the transient data. 1501cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen releaseMemory(); 1502cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 1503cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen return true; 1504cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen} 1505