RegAllocGreedy.cpp revision d2056e51c662765f98413fa071afbff53d87b384
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" 42d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen#include "llvm/Support/CommandLine.h" 43cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "llvm/Support/Debug.h" 44cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "llvm/Support/ErrorHandling.h" 45cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "llvm/Support/raw_ostream.h" 46533f58ecdd8a4732c2f0e149387c4d8d8d4142deJakob Stoklund Olesen#include "llvm/Support/Timer.h" 47cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 4898d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen#include <queue> 4998d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen 50cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesenusing namespace llvm; 51cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 520db841f9c2b9a25fb5ecb36e350d3a802c35654cJakob Stoklund OlesenSTATISTIC(NumGlobalSplits, "Number of split global live ranges"); 530db841f9c2b9a25fb5ecb36e350d3a802c35654cJakob Stoklund OlesenSTATISTIC(NumLocalSplits, "Number of split local live ranges"); 540db841f9c2b9a25fb5ecb36e350d3a802c35654cJakob Stoklund OlesenSTATISTIC(NumEvicted, "Number of interferences evicted"); 550db841f9c2b9a25fb5ecb36e350d3a802c35654cJakob Stoklund Olesen 56d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesenstatic cl::opt<bool> 57d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund OlesenComplexEviction("complex-eviction", cl::Hidden, 58d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen cl::desc("Use complex eviction heuristics")); 59d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen 60cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesenstatic RegisterRegAlloc greedyRegAlloc("greedy", "greedy register allocator", 61cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen createGreedyRegisterAllocator); 62cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 63cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesennamespace { 6492a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesenclass RAGreedy : public MachineFunctionPass, 6592a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen public RegAllocBase, 6692a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen private LiveRangeEdit::Delegate { 6792a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen 68cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen // context 69cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen MachineFunction *MF; 70cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen BitVector ReservedRegs; 71cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 72cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen // analyses 73b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen SlotIndexes *Indexes; 74cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen LiveStacks *LS; 75f428eb6c1b09a2322b7a577b0bf2e49dd107bceaJakob Stoklund Olesen MachineDominatorTree *DomTree; 76d0bb5e2ca05d9c942223bf05e5940bb0c6cc9d3fJakob Stoklund Olesen MachineLoopInfo *Loops; 77d0bb5e2ca05d9c942223bf05e5940bb0c6cc9d3fJakob Stoklund Olesen MachineLoopRanges *LoopRanges; 78b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen EdgeBundles *Bundles; 79b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen SpillPlacement *SpillPlacer; 80f42b66169d75301346e3685fd2b3e45e47806367Jakob Stoklund Olesen LiveDebugVariables *DebugVars; 81f428eb6c1b09a2322b7a577b0bf2e49dd107bceaJakob Stoklund Olesen 82cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen // state 83cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen std::auto_ptr<Spiller> SpillerInstance; 8498d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen std::priority_queue<std::pair<unsigned, unsigned> > Queue; 8522a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen 8622a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // Live ranges pass through a number of stages as we try to allocate them. 8722a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // Some of the stages may also create new live ranges: 8822a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // 8922a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // - Region splitting. 9022a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // - Per-block splitting. 9122a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // - Local splitting. 9222a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // - Spilling. 9322a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // 9422a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // Ranges produced by one of the stages skip the previous stages when they are 9522a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // dequeued. This improves performance because we can skip interference checks 9622a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // that are unlikely to give any results. It also guarantees that the live 9722a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // range splitting algorithm terminates, something that is otherwise hard to 9822a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // ensure. 9922a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen enum LiveRangeStage { 100f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund Olesen RS_New, ///< Never seen before. 101f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund Olesen RS_First, ///< First time in the queue. 102d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen RS_Evicted, ///< Requeued after being evicted. 103d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen RS_Second, ///< Second time in the queue, ready for splitting. 104fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen RS_Global, ///< Produced by global splitting. 10522a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen RS_Local, ///< Produced by local splitting. 10622a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen RS_Spill ///< Produced by spilling. 10722a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen }; 10822a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen 109b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen static const char *const StageName[]; 110b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen 11122a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen IndexedMap<unsigned char, VirtReg2IndexFunctor> LRStage; 11222a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen 11322a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen LiveRangeStage getStage(const LiveInterval &VirtReg) const { 11422a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen return LiveRangeStage(LRStage[VirtReg.reg]); 11522a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen } 11622a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen 11722a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen template<typename Iterator> 11822a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen void setStage(Iterator Begin, Iterator End, LiveRangeStage NewStage) { 11922a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen LRStage.resize(MRI->getNumVirtRegs()); 120f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund Olesen for (;Begin != End; ++Begin) { 121f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund Olesen unsigned Reg = (*Begin)->reg; 122f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund Olesen if (LRStage[Reg] == RS_New) 123f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund Olesen LRStage[Reg] = NewStage; 124f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund Olesen } 12522a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen } 126cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 127b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen // splitting state. 12822a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen std::auto_ptr<SplitAnalysis> SA; 129bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen std::auto_ptr<SplitEditor> SE; 130b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 131eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen /// Cached per-block interference maps 132eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen InterferenceCache IntfCache; 133eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen 1347b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen /// All basic blocks where the current register has uses. 13596dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen SmallVector<SpillPlacement::BlockConstraint, 8> SplitConstraints; 136b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 13796dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen /// Global live range splitting candidate info. 13896dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen struct GlobalSplitCandidate { 13996dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen unsigned PhysReg; 14096dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen BitVector LiveBundles; 1415db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen SmallVector<unsigned, 8> ActiveBlocks; 1425db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen 1435db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen void reset(unsigned Reg) { 1445db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen PhysReg = Reg; 1455db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen LiveBundles.clear(); 1465db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen ActiveBlocks.clear(); 1475db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen } 14896dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen }; 14996dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen 15096dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen /// Candidate info for for each PhysReg in AllocationOrder. 15196dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen /// This vector never shrinks, but grows to the size of the largest register 15296dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen /// class. 15396dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen SmallVector<GlobalSplitCandidate, 32> GlobalCand; 15496dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen 155034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen /// For every instruction in SA->UseSlots, store the previous non-copy 156034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen /// instruction. 157034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen SmallVector<SlotIndex, 8> PrevSlot; 158034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 159cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesenpublic: 160cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen RAGreedy(); 161cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 162cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen /// Return the pass name. 163cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen virtual const char* getPassName() const { 164533f58ecdd8a4732c2f0e149387c4d8d8d4142deJakob Stoklund Olesen return "Greedy Register Allocator"; 165cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen } 166cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 167cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen /// RAGreedy analysis usage. 168cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen virtual void getAnalysisUsage(AnalysisUsage &AU) const; 169cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen virtual void releaseMemory(); 170cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen virtual Spiller &spiller() { return *SpillerInstance; } 17198d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen virtual void enqueue(LiveInterval *LI); 17298d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen virtual LiveInterval *dequeue(); 173ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen virtual unsigned selectOrSplit(LiveInterval&, 174ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen SmallVectorImpl<LiveInterval*>&); 175cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 176cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen /// Perform register allocation. 177cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen virtual bool runOnMachineFunction(MachineFunction &mf); 178cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 179cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen static char ID; 180b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick 181b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trickprivate: 18292a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen void LRE_WillEraseInstruction(MachineInstr*); 1837792e980c43536814ea42448db9799b4da32fef6Jakob Stoklund Olesen bool LRE_CanEraseVirtReg(unsigned); 1841d5b84508173b93faf513032b3847152e6060791Jakob Stoklund Olesen void LRE_WillShrinkVirtReg(unsigned); 185f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund Olesen void LRE_DidCloneVirtReg(unsigned, unsigned); 18692a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen 187200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen float calcSpillCost(); 188f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen bool addSplitConstraints(InterferenceCache::Cursor, float&); 189f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen void addThroughConstraints(InterferenceCache::Cursor, ArrayRef<unsigned>); 1905db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen void growRegion(GlobalSplitCandidate &Cand, InterferenceCache::Cursor); 1915db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen float calcGlobalSplitCost(GlobalSplitCandidate&, InterferenceCache::Cursor); 1925db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen void splitAroundRegion(LiveInterval&, GlobalSplitCandidate&, 193ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen SmallVectorImpl<LiveInterval*>&); 194034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen void calcGapWeights(unsigned, SmallVectorImpl<float>&); 195034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen SlotIndex getPrevMappedIndex(const MachineInstr*); 196034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen void calcPrevSlots(); 197034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen unsigned nextSplitPoint(unsigned); 198d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen bool hasDefInRange(const LiveInterval&, const LiveInterval&); 199d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen bool hasUseInRange(const LiveInterval&, const LiveInterval&); 200d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen bool canEvict(LiveInterval &A, LiveInterval &B); 201d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen bool canEvictInterference(LiveInterval&, unsigned, float&, bool); 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", 222d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen "RS_Evicted", 223b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen "RS_Second", 224b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen "RS_Global", 225b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen "RS_Local", 226b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen "RS_Spill" 227b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen}; 228b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen#endif 229b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen 230200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen// Hysteresis to use when comparing floats. 231200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen// This helps stabilize decisions based on float comparisons. 232200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesenconst float Hysteresis = 0.98f; 233200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen 234200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen 235cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund OlesenFunctionPass* llvm::createGreedyRegisterAllocator() { 236cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen return new RAGreedy(); 237cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen} 238cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 239f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund OlesenRAGreedy::RAGreedy(): MachineFunctionPass(ID), LRStage(RS_New) { 240cfafc54040cc9722995558124f253d05a038176bJakob Stoklund Olesen initializeLiveDebugVariablesPass(*PassRegistry::getPassRegistry()); 241b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen initializeSlotIndexesPass(*PassRegistry::getPassRegistry()); 242cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen initializeLiveIntervalsPass(*PassRegistry::getPassRegistry()); 243cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen initializeSlotIndexesPass(*PassRegistry::getPassRegistry()); 244cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen initializeStrongPHIEliminationPass(*PassRegistry::getPassRegistry()); 245cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen initializeRegisterCoalescerAnalysisGroup(*PassRegistry::getPassRegistry()); 246cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen initializeCalculateSpillWeightsPass(*PassRegistry::getPassRegistry()); 247cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen initializeLiveStacksPass(*PassRegistry::getPassRegistry()); 248cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry()); 249cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen initializeMachineLoopInfoPass(*PassRegistry::getPassRegistry()); 250d0bb5e2ca05d9c942223bf05e5940bb0c6cc9d3fJakob Stoklund Olesen initializeMachineLoopRangesPass(*PassRegistry::getPassRegistry()); 251cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen initializeVirtRegMapPass(*PassRegistry::getPassRegistry()); 252b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen initializeEdgeBundlesPass(*PassRegistry::getPassRegistry()); 253b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen initializeSpillPlacementPass(*PassRegistry::getPassRegistry()); 254cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen} 255cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 256cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesenvoid RAGreedy::getAnalysisUsage(AnalysisUsage &AU) const { 257cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.setPreservesCFG(); 258cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addRequired<AliasAnalysis>(); 259cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addPreserved<AliasAnalysis>(); 260cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addRequired<LiveIntervals>(); 261b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen AU.addRequired<SlotIndexes>(); 262cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addPreserved<SlotIndexes>(); 263cfafc54040cc9722995558124f253d05a038176bJakob Stoklund Olesen AU.addRequired<LiveDebugVariables>(); 264cfafc54040cc9722995558124f253d05a038176bJakob Stoklund Olesen AU.addPreserved<LiveDebugVariables>(); 265cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen if (StrongPHIElim) 266cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addRequiredID(StrongPHIEliminationID); 267cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addRequiredTransitive<RegisterCoalescer>(); 268cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addRequired<CalculateSpillWeights>(); 269cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addRequired<LiveStacks>(); 270cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addPreserved<LiveStacks>(); 271f428eb6c1b09a2322b7a577b0bf2e49dd107bceaJakob Stoklund Olesen AU.addRequired<MachineDominatorTree>(); 272f428eb6c1b09a2322b7a577b0bf2e49dd107bceaJakob Stoklund Olesen AU.addPreserved<MachineDominatorTree>(); 273cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addRequired<MachineLoopInfo>(); 274cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addPreserved<MachineLoopInfo>(); 275d0bb5e2ca05d9c942223bf05e5940bb0c6cc9d3fJakob Stoklund Olesen AU.addRequired<MachineLoopRanges>(); 276d0bb5e2ca05d9c942223bf05e5940bb0c6cc9d3fJakob Stoklund Olesen AU.addPreserved<MachineLoopRanges>(); 277cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addRequired<VirtRegMap>(); 278cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addPreserved<VirtRegMap>(); 279b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen AU.addRequired<EdgeBundles>(); 280b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen AU.addRequired<SpillPlacement>(); 281cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen MachineFunctionPass::getAnalysisUsage(AU); 282cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen} 283cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 28492a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen 28592a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 28692a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen// LiveRangeEdit delegate methods 28792a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 28892a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen 28992a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesenvoid RAGreedy::LRE_WillEraseInstruction(MachineInstr *MI) { 29092a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen // LRE itself will remove from SlotIndexes and parent basic block. 29192a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen VRM->RemoveMachineInstrFromMaps(MI); 29292a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen} 29392a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen 2947792e980c43536814ea42448db9799b4da32fef6Jakob Stoklund Olesenbool RAGreedy::LRE_CanEraseVirtReg(unsigned VirtReg) { 2957792e980c43536814ea42448db9799b4da32fef6Jakob Stoklund Olesen if (unsigned PhysReg = VRM->getPhys(VirtReg)) { 2967792e980c43536814ea42448db9799b4da32fef6Jakob Stoklund Olesen unassign(LIS->getInterval(VirtReg), PhysReg); 2977792e980c43536814ea42448db9799b4da32fef6Jakob Stoklund Olesen return true; 2987792e980c43536814ea42448db9799b4da32fef6Jakob Stoklund Olesen } 2997792e980c43536814ea42448db9799b4da32fef6Jakob Stoklund Olesen // Unassigned virtreg is probably in the priority queue. 3007792e980c43536814ea42448db9799b4da32fef6Jakob Stoklund Olesen // RegAllocBase will erase it after dequeueing. 3017792e980c43536814ea42448db9799b4da32fef6Jakob Stoklund Olesen return false; 3027792e980c43536814ea42448db9799b4da32fef6Jakob Stoklund Olesen} 30392a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen 3041d5b84508173b93faf513032b3847152e6060791Jakob Stoklund Olesenvoid RAGreedy::LRE_WillShrinkVirtReg(unsigned VirtReg) { 3051d5b84508173b93faf513032b3847152e6060791Jakob Stoklund Olesen unsigned PhysReg = VRM->getPhys(VirtReg); 3061d5b84508173b93faf513032b3847152e6060791Jakob Stoklund Olesen if (!PhysReg) 3071d5b84508173b93faf513032b3847152e6060791Jakob Stoklund Olesen return; 3081d5b84508173b93faf513032b3847152e6060791Jakob Stoklund Olesen 3091d5b84508173b93faf513032b3847152e6060791Jakob Stoklund Olesen // Register is assigned, put it back on the queue for reassignment. 3101d5b84508173b93faf513032b3847152e6060791Jakob Stoklund Olesen LiveInterval &LI = LIS->getInterval(VirtReg); 3111d5b84508173b93faf513032b3847152e6060791Jakob Stoklund Olesen unassign(LI, PhysReg); 3121d5b84508173b93faf513032b3847152e6060791Jakob Stoklund Olesen enqueue(&LI); 3131d5b84508173b93faf513032b3847152e6060791Jakob Stoklund Olesen} 3141d5b84508173b93faf513032b3847152e6060791Jakob Stoklund Olesen 315f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund Olesenvoid RAGreedy::LRE_DidCloneVirtReg(unsigned New, unsigned Old) { 316f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund Olesen // LRE may clone a virtual register because dead code elimination causes it to 317f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund Olesen // be split into connected components. Ensure that the new register gets the 318f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund Olesen // same stage as the parent. 319f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund Olesen LRStage.grow(New); 320f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund Olesen LRStage[New] = LRStage[Old]; 321f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund Olesen} 322f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund Olesen 323cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesenvoid RAGreedy::releaseMemory() { 324cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen SpillerInstance.reset(0); 32522a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen LRStage.clear(); 3265db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen GlobalCand.clear(); 327cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen RegAllocBase::releaseMemory(); 328cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen} 329cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 33098d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesenvoid RAGreedy::enqueue(LiveInterval *LI) { 33198d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen // Prioritize live ranges by size, assigning larger ranges first. 33298d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen // The queue holds (size, reg) pairs. 333107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen const unsigned Size = LI->getSize(); 334107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen const unsigned Reg = LI->reg; 33598d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen assert(TargetRegisterInfo::isVirtualRegister(Reg) && 33698d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen "Can only enqueue virtual registers"); 337107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen unsigned Prio; 33890c1d7ddfc65654f7efe72d56cad65d1af9e6b2aJakob Stoklund Olesen 33922a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen LRStage.grow(Reg); 340f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund Olesen if (LRStage[Reg] == RS_New) 341f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund Olesen LRStage[Reg] = RS_First; 342f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund Olesen 343eb29157d80847c207b77910bcd40a6a6c91ca5c5Jakob Stoklund Olesen if (LRStage[Reg] == RS_Second) 344eb29157d80847c207b77910bcd40a6a6c91ca5c5Jakob Stoklund Olesen // Unsplit ranges that couldn't be allocated immediately are deferred until 345eb29157d80847c207b77910bcd40a6a6c91ca5c5Jakob Stoklund Olesen // everything else has been allocated. Long ranges are allocated last so 346eb29157d80847c207b77910bcd40a6a6c91ca5c5Jakob Stoklund Olesen // they are split against realistic interference. 347eb29157d80847c207b77910bcd40a6a6c91ca5c5Jakob Stoklund Olesen Prio = (1u << 31) - Size; 348eb29157d80847c207b77910bcd40a6a6c91ca5c5Jakob Stoklund Olesen else { 349eb29157d80847c207b77910bcd40a6a6c91ca5c5Jakob Stoklund Olesen // Everything else is allocated in long->short order. Long ranges that don't 350eb29157d80847c207b77910bcd40a6a6c91ca5c5Jakob Stoklund Olesen // fit should be spilled ASAP so they don't create interference. 351107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen Prio = (1u << 31) + Size; 352d2a50734234a80893ad71da90d9f32032c47e000Jakob Stoklund Olesen 353eb29157d80847c207b77910bcd40a6a6c91ca5c5Jakob Stoklund Olesen // Boost ranges that have a physical register hint. 354eb29157d80847c207b77910bcd40a6a6c91ca5c5Jakob Stoklund Olesen if (TargetRegisterInfo::isPhysicalRegister(VRM->getRegAllocPref(Reg))) 355eb29157d80847c207b77910bcd40a6a6c91ca5c5Jakob Stoklund Olesen Prio |= (1u << 30); 356eb29157d80847c207b77910bcd40a6a6c91ca5c5Jakob Stoklund Olesen } 357107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen 358107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen Queue.push(std::make_pair(Prio, Reg)); 35990c1d7ddfc65654f7efe72d56cad65d1af9e6b2aJakob Stoklund Olesen} 36090c1d7ddfc65654f7efe72d56cad65d1af9e6b2aJakob Stoklund Olesen 36198d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund OlesenLiveInterval *RAGreedy::dequeue() { 36298d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen if (Queue.empty()) 36398d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen return 0; 36498d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen LiveInterval *LI = &LIS->getInterval(Queue.top().second); 36598d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen Queue.pop(); 36698d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen return LI; 36798d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen} 368770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen 3696bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen 3706bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 3716bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen// Direct Assignment 3726bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 3736bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen 3746bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen/// tryAssign - Try to assign VirtReg to an available register. 3756bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesenunsigned RAGreedy::tryAssign(LiveInterval &VirtReg, 3766bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen AllocationOrder &Order, 3776bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen SmallVectorImpl<LiveInterval*> &NewVRegs) { 3786bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen Order.rewind(); 3796bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen unsigned PhysReg; 3806bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen while ((PhysReg = Order.next())) 3816bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen if (!checkPhysRegInterference(VirtReg, PhysReg)) 3826bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen break; 3836bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen if (!PhysReg || Order.isHint(PhysReg)) 3846bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen return PhysReg; 3856bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen 3866bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen // PhysReg is available. Try to evict interference from a cheaper alternative. 3876bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen unsigned Cost = TRI->getCostPerUse(PhysReg); 3886bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen 3896bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen // Most registers have 0 additional cost. 3906bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen if (!Cost) 3916bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen return PhysReg; 3926bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen 3936bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen DEBUG(dbgs() << PrintReg(PhysReg, TRI) << " is available at cost " << Cost 3946bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen << '\n'); 3956bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen unsigned CheapReg = tryEvict(VirtReg, Order, NewVRegs, Cost); 3966bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen return CheapReg ? CheapReg : PhysReg; 3976bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen} 3986bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen 3996bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen 400770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen//===----------------------------------------------------------------------===// 40198c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen// Interference eviction 40298c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 4032710638db2eb84cd7eefb8bb9a1b7e5c49413d45Jakob Stoklund Olesen 404d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen/// hasDefInRange - Returns true when any def of A happens where B is live. 405d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen/// 406d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen/// The SSA form of live intervals guarantees: 407d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen/// 408d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen/// A.overlaps(B) == hasDefInRange(A, B) || hasDefInRange(B, A) 409d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen/// 410d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesenbool RAGreedy::hasDefInRange(const LiveInterval &A, const LiveInterval &B) { 411d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen for (LiveInterval::const_vni_iterator I = A.vni_begin(), E = A.vni_end(); 412d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen I != E; ++I) { 413d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen const VNInfo *VNI = *I; 414d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen if (VNI->isUnused()) 415d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen continue; 416d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen if (B.liveAt(VNI->def)) 417d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen return true; 418d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen } 419d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen return false; 420d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen} 421d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen 422d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen/// hasUseInRange - Returns true when any def or use of A happens where B is 423d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen/// live. The following is always true: 424d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen/// 425d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen/// A.overlaps(B) == hasUseInRange(A, B) || hasUseInRange(B, A) 426d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen/// 427d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesenbool RAGreedy::hasUseInRange(const LiveInterval &A, const LiveInterval &B) { 428d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen if (hasDefInRange(A, B)) 429d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen return true; 430d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen for (MachineRegisterInfo::use_nodbg_iterator I = MRI->use_nodbg_begin(A.reg), 431d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen E = MRI->use_nodbg_end(); I != E; ++I) { 432d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen if (I.getOperand().isUndef()) 433d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen continue; 434d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen SlotIndex Idx = Indexes->getInstructionIndex(&*I).getDefIndex(); 435d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen if (B.liveAt(Idx)) 436d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen return true; 437d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen } 438d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen return false; 439d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen} 440d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen 441b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen/// canEvict - determine if A can evict the assigned live range B. The eviction 442b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen/// policy defined by this function together with the allocation order defined 443b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen/// by enqueue() decides which registers ultimately end up being split and 444b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen/// spilled. 445b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen/// 446d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen/// Safeguards ensure that canEvict can never cause an infinite loop. 447d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen/// 448d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesenbool RAGreedy::canEvict(LiveInterval &A, LiveInterval &B) { 449d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen if (!ComplexEviction) 450d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen return A.weight > B.weight; 451d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen 452d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen // Evict B if it has no uses in A's live range. 453d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen if (!hasUseInRange(B, A)) { 454d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen DEBUG(dbgs() << "Bypass: " << B << '\n'); 455d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen return true; 456d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen } 457d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen return A.weight > B.weight; 458b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen} 459b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen 46098c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen/// canEvict - Return true if all interferences between VirtReg and PhysReg can 4613f5bedf5cbde2cc2badc86b1a0b377f6efcde71cJakob Stoklund Olesen/// be evicted. 4623f5bedf5cbde2cc2badc86b1a0b377f6efcde71cJakob Stoklund Olesen/// Return false if any interference is heavier than MaxWeight. 4633f5bedf5cbde2cc2badc86b1a0b377f6efcde71cJakob Stoklund Olesen/// On return, set MaxWeight to the maximal spill weight of an interference. 46498c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesenbool RAGreedy::canEvictInterference(LiveInterval &VirtReg, unsigned PhysReg, 465d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen float &MaxWeight, bool OnlyCheap) { 46698c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen float Weight = 0; 46798c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen for (const unsigned *AliasI = TRI->getOverlaps(PhysReg); *AliasI; ++AliasI) { 46898c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen LiveIntervalUnion::Query &Q = query(VirtReg, *AliasI); 4693f5bedf5cbde2cc2badc86b1a0b377f6efcde71cJakob Stoklund Olesen // If there is 10 or more interferences, chances are one is heavier. 4703f5bedf5cbde2cc2badc86b1a0b377f6efcde71cJakob Stoklund Olesen if (Q.collectInterferingVRegs(10, MaxWeight) >= 10) 47198c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen return false; 47298c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen 4733f5bedf5cbde2cc2badc86b1a0b377f6efcde71cJakob Stoklund Olesen // Check if any interfering live range is heavier than MaxWeight. 4743f5bedf5cbde2cc2badc86b1a0b377f6efcde71cJakob Stoklund Olesen for (unsigned i = Q.interferingVRegs().size(); i; --i) { 4753f5bedf5cbde2cc2badc86b1a0b377f6efcde71cJakob Stoklund Olesen LiveInterval *Intf = Q.interferingVRegs()[i - 1]; 47698c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen if (TargetRegisterInfo::isPhysicalRegister(Intf->reg)) 47798c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen return false; 478d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen if (getStage(*Intf) == RS_Spill) 47998c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen return false; 480d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen if (Intf->weight >= MaxWeight) 481b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen return false; 482d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen // When we are simply looking for a cheaper alternative, don't try too 483d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen // hard. The evicted range shouldn't end up getting split. 484d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen if (OnlyCheap) { 485d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen // Don't evict something that won't be able to reevict something else. 486d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen if (getStage(*Intf) != RS_First) 487d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen return false; 488d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen // Don't break a satisfied hint. 489d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen if (VRM->getRegAllocPref(Intf->reg) == *AliasI) 490b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen return false; 491b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen } 492d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen if (VirtReg.isSpillable() && !canEvict(VirtReg, *Intf)) 493d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen return false; 49498c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen Weight = std::max(Weight, Intf->weight); 4952710638db2eb84cd7eefb8bb9a1b7e5c49413d45Jakob Stoklund Olesen } 4962710638db2eb84cd7eefb8bb9a1b7e5c49413d45Jakob Stoklund Olesen } 49798c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen MaxWeight = Weight; 49898c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen return true; 49998c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen} 50098c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen 50198c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen/// tryEvict - Try to evict all interferences for a physreg. 502d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen/// @param VirtReg Currently unassigned virtual register. 503d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen/// @param Order Physregs to try. 504d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen/// @param CostPerUseLimit Only look at physregs below this cost per use. 505d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen/// @return Physreg to assign VirtReg, or 0. 50698c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesenunsigned RAGreedy::tryEvict(LiveInterval &VirtReg, 50798c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen AllocationOrder &Order, 5086bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen SmallVectorImpl<LiveInterval*> &NewVRegs, 5096bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen unsigned CostPerUseLimit) { 510d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen // Ranges that may have been evicted or requeued for splitting may never evict 511d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen // other ranges. That could cause looping. 512d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen // Spill ranges can always evict. 513d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen LiveRangeStage Stage = getStage(VirtReg); 514d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen if (Stage >= RS_Evicted && VirtReg.isSpillable()) 515d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen return 0; 51698c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen NamedRegionTimer T("Evict", TimerGroupName, TimePassesIsEnabled); 51798c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen 518d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen bool OnlyCheap = CostPerUseLimit != ~0u; 519d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen 52098c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen // Keep track of the lightest single interference seen so far. 521d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen // When scavenging for a cheap register, never consider evicting heavier 522d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen // ranges. 523d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen float BestWeight = OnlyCheap ? VirtReg.weight : HUGE_VALF; 52498c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen unsigned BestPhys = 0; 52598c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen 52698c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen Order.rewind(); 52798c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen while (unsigned PhysReg = Order.next()) { 5286bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen if (TRI->getCostPerUse(PhysReg) >= CostPerUseLimit) 5296bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen continue; 5306bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen // The first use of a register in a function has cost 1. 5316bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen if (CostPerUseLimit == 1 && !MRI->isPhysRegUsed(PhysReg)) 5326bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen continue; 5336bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen 5343f5bedf5cbde2cc2badc86b1a0b377f6efcde71cJakob Stoklund Olesen float Weight = BestWeight; 535d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen if (!canEvictInterference(VirtReg, PhysReg, Weight, OnlyCheap)) 53698c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen continue; 53798c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen 53898c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen // This is an eviction candidate. 5393f5bedf5cbde2cc2badc86b1a0b377f6efcde71cJakob Stoklund Olesen DEBUG(dbgs() << PrintReg(PhysReg, TRI) << " interference = " 54098c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen << Weight << '\n'); 54198c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen if (BestPhys && Weight >= BestWeight) 54298c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen continue; 54398c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen 54498c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen // Best so far. 54598c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen BestPhys = PhysReg; 54698c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen BestWeight = Weight; 54757f1e2cee06f9b57995727d786aeb1031c5376bdJakob Stoklund Olesen // Stop if the hint can be used. 54857f1e2cee06f9b57995727d786aeb1031c5376bdJakob Stoklund Olesen if (Order.isHint(PhysReg)) 54957f1e2cee06f9b57995727d786aeb1031c5376bdJakob Stoklund Olesen break; 5502710638db2eb84cd7eefb8bb9a1b7e5c49413d45Jakob Stoklund Olesen } 5512710638db2eb84cd7eefb8bb9a1b7e5c49413d45Jakob Stoklund Olesen 55298c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen if (!BestPhys) 55398c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen return 0; 55498c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen 55598c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen DEBUG(dbgs() << "evicting " << PrintReg(BestPhys, TRI) << " interference\n"); 55698c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen for (const unsigned *AliasI = TRI->getOverlaps(BestPhys); *AliasI; ++AliasI) { 55798c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen LiveIntervalUnion::Query &Q = query(VirtReg, *AliasI); 55898c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen assert(Q.seenAllInterferences() && "Didn't check all interfererences."); 55998c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen for (unsigned i = 0, e = Q.interferingVRegs().size(); i != e; ++i) { 56098c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen LiveInterval *Intf = Q.interferingVRegs()[i]; 56198c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen unassign(*Intf, VRM->getPhys(Intf->reg)); 56298c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen ++NumEvicted; 56398c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen NewVRegs.push_back(Intf); 564d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen // Prevent looping by marking the evicted ranges as RS_Evicted. 565d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen // When OnlyCheap is set, Intf is guaranteed to have a smaller spill 566d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen // weight which also prevents looping. 567d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen if (!OnlyCheap && getStage(*Intf) < RS_Evicted) 568d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen LRStage[Intf->reg] = RS_Evicted; 56998c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen } 57098c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen } 57198c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen return BestPhys; 572b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick} 573b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick 574770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen 575770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen//===----------------------------------------------------------------------===// 576b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen// Region Splitting 577b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen//===----------------------------------------------------------------------===// 578b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 5791b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen/// addSplitConstraints - Fill out the SplitConstraints vector based on the 5801b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen/// interference pattern in Physreg and its aliases. Add the constraints to 5811b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen/// SpillPlacement and return the static cost of this split in Cost, assuming 5821b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen/// that all preferences in SplitConstraints are met. 583f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen/// Return false if there are no bundles with positive bias. 584f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesenbool RAGreedy::addSplitConstraints(InterferenceCache::Cursor Intf, 585f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen float &Cost) { 586db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks(); 587eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen 588b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen // Reset interference dependent info. 589db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen SplitConstraints.resize(UseBlocks.size()); 59096dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen float StaticCost = 0; 591db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen for (unsigned i = 0; i != UseBlocks.size(); ++i) { 592db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen const SplitAnalysis::BlockInfo &BI = UseBlocks[i]; 59396dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen SpillPlacement::BlockConstraint &BC = SplitConstraints[i]; 59496dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen 595f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen BC.Number = BI.MBB->getNumber(); 596eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen Intf.moveToBlock(BC.Number); 597db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen BC.Entry = BI.LiveIn ? SpillPlacement::PrefReg : SpillPlacement::DontCare; 598db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen BC.Exit = BI.LiveOut ? SpillPlacement::PrefReg : SpillPlacement::DontCare; 599b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 600eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen if (!Intf.hasInterference()) 601eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen continue; 602eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen 60396dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen // Number of spill code instructions to insert. 60496dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen unsigned Ins = 0; 60596dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen 60696dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen // Interference for the live-in value. 607eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen if (BI.LiveIn) { 6086c8afd728eb02742ce320ecd39bcf3774d8423b7Jakob Stoklund Olesen if (Intf.first() <= Indexes->getMBBStartIdx(BC.Number)) 609db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen BC.Entry = SpillPlacement::MustSpill, ++Ins; 610eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen else if (Intf.first() < BI.FirstUse) 61196dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen BC.Entry = SpillPlacement::PrefSpill, ++Ins; 612a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen else if (Intf.first() < BI.LastUse) 61396dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen ++Ins; 614a50c539b7a9e74597da34bfaea5429a48481f18bJakob Stoklund Olesen } 615b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 61696dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen // Interference for the live-out value. 617eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen if (BI.LiveOut) { 618612f7807c581eafb7c8105e1a55c8d839033bfb3Jakob Stoklund Olesen if (Intf.last() >= SA->getLastSplitPoint(BC.Number)) 619db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen BC.Exit = SpillPlacement::MustSpill, ++Ins; 620eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen else if (Intf.last() > BI.LastUse) 62196dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen BC.Exit = SpillPlacement::PrefSpill, ++Ins; 622a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen else if (Intf.last() > BI.FirstUse) 62396dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen ++Ins; 624b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen } 625b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 62696dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen // Accumulate the total frequency of inserted spill code. 62796dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen if (Ins) 62896dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen StaticCost += Ins * SpillPlacer->getBlockFrequency(BC.Number); 629b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen } 630f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen Cost = StaticCost; 631db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen 6321b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen // Add constraints for use-blocks. Note that these are the only constraints 6331b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen // that may add a positive bias, it is downhill from here. 6341b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen SpillPlacer->addConstraints(SplitConstraints); 635f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen return SpillPlacer->scanActiveBundles(); 636f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen} 637db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen 638db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen 639f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen/// addThroughConstraints - Add constraints and links to SpillPlacer from the 640f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen/// live-through blocks in Blocks. 641f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesenvoid RAGreedy::addThroughConstraints(InterferenceCache::Cursor Intf, 642f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen ArrayRef<unsigned> Blocks) { 6431b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen const unsigned GroupSize = 8; 6441b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen SpillPlacement::BlockConstraint BCS[GroupSize]; 645f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen unsigned TBS[GroupSize]; 646f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen unsigned B = 0, T = 0; 647db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen 648f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen for (unsigned i = 0; i != Blocks.size(); ++i) { 649f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen unsigned Number = Blocks[i]; 6501b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen Intf.moveToBlock(Number); 6511b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen 6527b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen if (!Intf.hasInterference()) { 653f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen assert(T < GroupSize && "Array overflow"); 654f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen TBS[T] = Number; 655f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen if (++T == GroupSize) { 656f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen SpillPlacer->addLinks(ArrayRef<unsigned>(TBS, T)); 657f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen T = 0; 658f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen } 6597b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen continue; 6601b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen } 6611b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen 662f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen assert(B < GroupSize && "Array overflow"); 663f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen BCS[B].Number = Number; 664f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen 6657b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen // Interference for the live-in value. 6667b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen if (Intf.first() <= Indexes->getMBBStartIdx(Number)) 6677b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen BCS[B].Entry = SpillPlacement::MustSpill; 6687b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen else 6697b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen BCS[B].Entry = SpillPlacement::PrefSpill; 6707b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen 6717b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen // Interference for the live-out value. 6727b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen if (Intf.last() >= SA->getLastSplitPoint(Number)) 6737b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen BCS[B].Exit = SpillPlacement::MustSpill; 6747b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen else 6757b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen BCS[B].Exit = SpillPlacement::PrefSpill; 6767b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen 6771b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen if (++B == GroupSize) { 6781b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen ArrayRef<SpillPlacement::BlockConstraint> Array(BCS, B); 6791b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen SpillPlacer->addConstraints(Array); 6801b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen B = 0; 6811b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen } 682db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen } 683db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen 6841b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen ArrayRef<SpillPlacement::BlockConstraint> Array(BCS, B); 6851b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen SpillPlacer->addConstraints(Array); 686f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen SpillPlacer->addLinks(ArrayRef<unsigned>(TBS, T)); 687b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen} 688b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 6895db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesenvoid RAGreedy::growRegion(GlobalSplitCandidate &Cand, 6905db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen InterferenceCache::Cursor Intf) { 6915db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen // Keep track of through blocks that have not been added to SpillPlacer. 6925db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen BitVector Todo = SA->getThroughBlocks(); 6935db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen SmallVectorImpl<unsigned> &ActiveBlocks = Cand.ActiveBlocks; 6945db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen unsigned AddedTo = 0; 695f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen#ifndef NDEBUG 696f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen unsigned Visited = 0; 697f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen#endif 6985db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen 699f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen for (;;) { 700f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen ArrayRef<unsigned> NewBundles = SpillPlacer->getRecentPositive(); 701f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen if (NewBundles.empty()) 702f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen break; 703f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen // Find new through blocks in the periphery of PrefRegBundles. 704f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen for (int i = 0, e = NewBundles.size(); i != e; ++i) { 705f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen unsigned Bundle = NewBundles[i]; 706f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen // Look at all blocks connected to Bundle in the full graph. 707f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen ArrayRef<unsigned> Blocks = Bundles->getBlocks(Bundle); 708f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen for (ArrayRef<unsigned>::iterator I = Blocks.begin(), E = Blocks.end(); 709f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen I != E; ++I) { 710f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen unsigned Block = *I; 7115db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen if (!Todo.test(Block)) 712f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen continue; 7135db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen Todo.reset(Block); 714f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen // This is a new through block. Add it to SpillPlacer later. 7155db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen ActiveBlocks.push_back(Block); 716f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen#ifndef NDEBUG 717f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen ++Visited; 718f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen#endif 719f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen } 720f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen } 721f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen // Any new blocks to add? 7225db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen if (ActiveBlocks.size() > AddedTo) { 7235db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen ArrayRef<unsigned> Add(&ActiveBlocks[AddedTo], 7245db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen ActiveBlocks.size() - AddedTo); 7255db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen addThroughConstraints(Intf, Add); 7265db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen AddedTo = ActiveBlocks.size(); 727f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen } 728f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen // Perhaps iterating can enable more bundles? 729f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen SpillPlacer->iterate(); 730f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen } 731f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen DEBUG(dbgs() << ", v=" << Visited); 732f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen} 73396dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen 734200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen/// calcSpillCost - Compute how expensive it would be to split the live range in 735200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen/// SA around all use blocks instead of forming bundle regions. 736200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesenfloat RAGreedy::calcSpillCost() { 737200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen float Cost = 0; 738200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen const LiveInterval &LI = SA->getParent(); 739200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks(); 740200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen for (unsigned i = 0; i != UseBlocks.size(); ++i) { 741200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen const SplitAnalysis::BlockInfo &BI = UseBlocks[i]; 742200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen unsigned Number = BI.MBB->getNumber(); 743200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen // We normally only need one spill instruction - a load or a store. 744200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen Cost += SpillPlacer->getBlockFrequency(Number); 745200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen 746200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen // Unless the value is redefined in the block. 747200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen if (BI.LiveIn && BI.LiveOut) { 748200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen SlotIndex Start, Stop; 749200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen tie(Start, Stop) = Indexes->getMBBRange(Number); 750200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen LiveInterval::const_iterator I = LI.find(Start); 751200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen assert(I != LI.end() && "Expected live-in value"); 752200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen // Is there a different live-out value? If so, we need an extra spill 753200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen // instruction. 754200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen if (I->end < Stop) 755200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen Cost += SpillPlacer->getBlockFrequency(Number); 756200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen } 757200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen } 758200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen return Cost; 759200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen} 760200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen 761b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen/// calcGlobalSplitCost - Return the global split cost of following the split 762b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen/// pattern in LiveBundles. This cost should be added to the local cost of the 76396dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen/// interference pattern in SplitConstraints. 764b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen/// 7655db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesenfloat RAGreedy::calcGlobalSplitCost(GlobalSplitCandidate &Cand, 7665db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen InterferenceCache::Cursor Intf) { 767b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen float GlobalCost = 0; 7685db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen const BitVector &LiveBundles = Cand.LiveBundles; 769db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks(); 770db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen for (unsigned i = 0; i != UseBlocks.size(); ++i) { 771db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen const SplitAnalysis::BlockInfo &BI = UseBlocks[i]; 77296dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen SpillPlacement::BlockConstraint &BC = SplitConstraints[i]; 773874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen bool RegIn = LiveBundles[Bundles->getBundle(BC.Number, 0)]; 774874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen bool RegOut = LiveBundles[Bundles->getBundle(BC.Number, 1)]; 775874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen unsigned Ins = 0; 776874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen 777db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen if (BI.LiveIn) 778db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen Ins += RegIn != (BC.Entry == SpillPlacement::PrefReg); 779db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen if (BI.LiveOut) 780db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen Ins += RegOut != (BC.Exit == SpillPlacement::PrefReg); 781874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen if (Ins) 782874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen GlobalCost += Ins * SpillPlacer->getBlockFrequency(BC.Number); 783b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen } 784db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen 7855db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen for (unsigned i = 0, e = Cand.ActiveBlocks.size(); i != e; ++i) { 7865db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen unsigned Number = Cand.ActiveBlocks[i]; 787db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen bool RegIn = LiveBundles[Bundles->getBundle(Number, 0)]; 788db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen bool RegOut = LiveBundles[Bundles->getBundle(Number, 1)]; 7899a54352879e5aaac2e2c37490e5cb7844550db8bJakob Stoklund Olesen if (!RegIn && !RegOut) 7909a54352879e5aaac2e2c37490e5cb7844550db8bJakob Stoklund Olesen continue; 7919a54352879e5aaac2e2c37490e5cb7844550db8bJakob Stoklund Olesen if (RegIn && RegOut) { 7929a54352879e5aaac2e2c37490e5cb7844550db8bJakob Stoklund Olesen // We need double spill code if this block has interference. 7939a54352879e5aaac2e2c37490e5cb7844550db8bJakob Stoklund Olesen Intf.moveToBlock(Number); 7949a54352879e5aaac2e2c37490e5cb7844550db8bJakob Stoklund Olesen if (Intf.hasInterference()) 7959a54352879e5aaac2e2c37490e5cb7844550db8bJakob Stoklund Olesen GlobalCost += 2*SpillPlacer->getBlockFrequency(Number); 7969a54352879e5aaac2e2c37490e5cb7844550db8bJakob Stoklund Olesen continue; 7979a54352879e5aaac2e2c37490e5cb7844550db8bJakob Stoklund Olesen } 7989a54352879e5aaac2e2c37490e5cb7844550db8bJakob Stoklund Olesen // live-in / stack-out or stack-in live-out. 7999a54352879e5aaac2e2c37490e5cb7844550db8bJakob Stoklund Olesen GlobalCost += SpillPlacer->getBlockFrequency(Number); 800db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen } 801b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen return GlobalCost; 802b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen} 803b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 804ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen/// splitAroundRegion - Split VirtReg around the region determined by 805ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen/// LiveBundles. Make an effort to avoid interference from PhysReg. 806ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen/// 807ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen/// The 'register' interval is going to contain as many uses as possible while 808ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen/// avoiding interference. The 'stack' interval is the complement constructed by 809ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen/// SplitEditor. It will contain the rest. 810ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen/// 8115db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesenvoid RAGreedy::splitAroundRegion(LiveInterval &VirtReg, 8125db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen GlobalSplitCandidate &Cand, 813ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen SmallVectorImpl<LiveInterval*> &NewVRegs) { 8145db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen const BitVector &LiveBundles = Cand.LiveBundles; 8155db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen 816ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen DEBUG({ 8175db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen dbgs() << "Splitting around region for " << PrintReg(Cand.PhysReg, TRI) 818ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen << " with bundles"; 819ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen for (int i = LiveBundles.find_first(); i>=0; i = LiveBundles.find_next(i)) 820ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen dbgs() << " EB#" << i; 821ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen dbgs() << ".\n"; 822ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen }); 823ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 8245db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen InterferenceCache::Cursor Intf(IntfCache, Cand.PhysReg); 82592a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen LiveRangeEdit LREdit(VirtReg, NewVRegs, this); 826bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen SE->reset(LREdit); 827ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 828ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Create the main cross-block interval. 829fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen const unsigned MainIntv = SE->openIntv(); 830ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 831ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // First add all defs that are live out of a block. 832db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks(); 833db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen for (unsigned i = 0; i != UseBlocks.size(); ++i) { 834db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen const SplitAnalysis::BlockInfo &BI = UseBlocks[i]; 835ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen bool RegIn = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 0)]; 836ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen bool RegOut = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 1)]; 837ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 838fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen // Create separate intervals for isolated blocks with multiple uses. 839fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen if (!RegIn && !RegOut && BI.FirstUse != BI.LastUse) { 840fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " isolated.\n"); 841fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen SE->splitSingleBlock(BI); 842fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen SE->selectIntv(MainIntv); 843fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen continue; 844fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen } 845fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen 846ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Should the register be live out? 847ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen if (!BI.LiveOut || !RegOut) 848ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen continue; 849ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 8506c8afd728eb02742ce320ecd39bcf3774d8423b7Jakob Stoklund Olesen SlotIndex Start, Stop; 8516c8afd728eb02742ce320ecd39bcf3774d8423b7Jakob Stoklund Olesen tie(Start, Stop) = Indexes->getMBBRange(BI.MBB); 852eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen Intf.moveToBlock(BI.MBB->getNumber()); 853ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " -> EB#" 8542dfbb3e9125aa0a66feab7a7638815b57da85968Jakob Stoklund Olesen << Bundles->getBundle(BI.MBB->getNumber(), 1) 855612f7807c581eafb7c8105e1a55c8d839033bfb3Jakob Stoklund Olesen << " [" << Start << ';' 856612f7807c581eafb7c8105e1a55c8d839033bfb3Jakob Stoklund Olesen << SA->getLastSplitPoint(BI.MBB->getNumber()) << '-' << Stop 857612f7807c581eafb7c8105e1a55c8d839033bfb3Jakob Stoklund Olesen << ") intf [" << Intf.first() << ';' << Intf.last() << ')'); 8582dfbb3e9125aa0a66feab7a7638815b57da85968Jakob Stoklund Olesen 8592dfbb3e9125aa0a66feab7a7638815b57da85968Jakob Stoklund Olesen // The interference interval should either be invalid or overlap MBB. 8606c8afd728eb02742ce320ecd39bcf3774d8423b7Jakob Stoklund Olesen assert((!Intf.hasInterference() || Intf.first() < Stop) 861eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen && "Bad interference"); 8626c8afd728eb02742ce320ecd39bcf3774d8423b7Jakob Stoklund Olesen assert((!Intf.hasInterference() || Intf.last() > Start) 86336d61863bc83bd2301e0224adc560098b35ec0dcJakob Stoklund Olesen && "Bad interference"); 864ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 865ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Check interference leaving the block. 866eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen if (!Intf.hasInterference()) { 867ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Block is interference-free. 868ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen DEBUG(dbgs() << ", no interference"); 869ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen if (!BI.LiveThrough) { 870ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen DEBUG(dbgs() << ", not live-through.\n"); 871a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen SE->useIntv(SE->enterIntvBefore(BI.FirstUse), Stop); 872ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen continue; 873ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen } 874ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen if (!RegIn) { 875ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Block is live-through, but entry bundle is on the stack. 876ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Reload just before the first use. 877ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen DEBUG(dbgs() << ", not live-in, enter before first use.\n"); 8786c8afd728eb02742ce320ecd39bcf3774d8423b7Jakob Stoklund Olesen SE->useIntv(SE->enterIntvBefore(BI.FirstUse), Stop); 879ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen continue; 880ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen } 881ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen DEBUG(dbgs() << ", live-through.\n"); 882ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen continue; 883ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen } 884ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 885ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Block has interference. 886eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen DEBUG(dbgs() << ", interference to " << Intf.last()); 887fe3f99f95c7c9ceaac3ceebbea31e40cfbc157e3Jakob Stoklund Olesen 888a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen if (!BI.LiveThrough && Intf.last() <= BI.FirstUse) { 889fe3f99f95c7c9ceaac3ceebbea31e40cfbc157e3Jakob Stoklund Olesen // The interference doesn't reach the outgoing segment. 890a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen DEBUG(dbgs() << " doesn't affect def from " << BI.FirstUse << '\n'); 891a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen SE->useIntv(BI.FirstUse, Stop); 892fe3f99f95c7c9ceaac3ceebbea31e40cfbc157e3Jakob Stoklund Olesen continue; 893fe3f99f95c7c9ceaac3ceebbea31e40cfbc157e3Jakob Stoklund Olesen } 894fe3f99f95c7c9ceaac3ceebbea31e40cfbc157e3Jakob Stoklund Olesen 895612f7807c581eafb7c8105e1a55c8d839033bfb3Jakob Stoklund Olesen SlotIndex LastSplitPoint = SA->getLastSplitPoint(BI.MBB->getNumber()); 896eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen if (Intf.last().getBoundaryIndex() < BI.LastUse) { 897ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // There are interference-free uses at the end of the block. 898ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Find the first use that can get the live-out register. 899c0de99571297720a37ae405c77fb2ef4aaf00ccdJakob Stoklund Olesen SmallVectorImpl<SlotIndex>::const_iterator UI = 900fe3f99f95c7c9ceaac3ceebbea31e40cfbc157e3Jakob Stoklund Olesen std::lower_bound(SA->UseSlots.begin(), SA->UseSlots.end(), 901eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen Intf.last().getBoundaryIndex()); 902c0de99571297720a37ae405c77fb2ef4aaf00ccdJakob Stoklund Olesen assert(UI != SA->UseSlots.end() && "Couldn't find last use"); 903c0de99571297720a37ae405c77fb2ef4aaf00ccdJakob Stoklund Olesen SlotIndex Use = *UI; 904c0de99571297720a37ae405c77fb2ef4aaf00ccdJakob Stoklund Olesen assert(Use <= BI.LastUse && "Couldn't find last use"); 9058a2bbdeee24b40da6187199658646d04329c139eJakob Stoklund Olesen // Only attempt a split befroe the last split point. 906612f7807c581eafb7c8105e1a55c8d839033bfb3Jakob Stoklund Olesen if (Use.getBaseIndex() <= LastSplitPoint) { 9078a2bbdeee24b40da6187199658646d04329c139eJakob Stoklund Olesen DEBUG(dbgs() << ", free use at " << Use << ".\n"); 908bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen SlotIndex SegStart = SE->enterIntvBefore(Use); 909eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen assert(SegStart >= Intf.last() && "Couldn't avoid interference"); 910612f7807c581eafb7c8105e1a55c8d839033bfb3Jakob Stoklund Olesen assert(SegStart < LastSplitPoint && "Impossible split point"); 9116c8afd728eb02742ce320ecd39bcf3774d8423b7Jakob Stoklund Olesen SE->useIntv(SegStart, Stop); 9128a2bbdeee24b40da6187199658646d04329c139eJakob Stoklund Olesen continue; 9138a2bbdeee24b40da6187199658646d04329c139eJakob Stoklund Olesen } 914ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen } 915ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 916ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Interference is after the last use. 917ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen DEBUG(dbgs() << " after last use.\n"); 918bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen SlotIndex SegStart = SE->enterIntvAtEnd(*BI.MBB); 919eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen assert(SegStart >= Intf.last() && "Couldn't avoid interference"); 920ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen } 921ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 922ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Now all defs leading to live bundles are handled, do everything else. 923db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen for (unsigned i = 0; i != UseBlocks.size(); ++i) { 924db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen const SplitAnalysis::BlockInfo &BI = UseBlocks[i]; 925ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen bool RegIn = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 0)]; 926ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen bool RegOut = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 1)]; 927ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 928ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Is the register live-in? 929ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen if (!BI.LiveIn || !RegIn) 930ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen continue; 931ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 932ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // We have an incoming register. Check for interference. 9336c8afd728eb02742ce320ecd39bcf3774d8423b7Jakob Stoklund Olesen SlotIndex Start, Stop; 9346c8afd728eb02742ce320ecd39bcf3774d8423b7Jakob Stoklund Olesen tie(Start, Stop) = Indexes->getMBBRange(BI.MBB); 935eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen Intf.moveToBlock(BI.MBB->getNumber()); 936ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen DEBUG(dbgs() << "EB#" << Bundles->getBundle(BI.MBB->getNumber(), 0) 9376c8afd728eb02742ce320ecd39bcf3774d8423b7Jakob Stoklund Olesen << " -> BB#" << BI.MBB->getNumber() << " [" << Start << ';' 938612f7807c581eafb7c8105e1a55c8d839033bfb3Jakob Stoklund Olesen << SA->getLastSplitPoint(BI.MBB->getNumber()) << '-' << Stop 939612f7807c581eafb7c8105e1a55c8d839033bfb3Jakob Stoklund Olesen << ')'); 940ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 941ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Check interference entering the block. 942eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen if (!Intf.hasInterference()) { 943ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Block is interference-free. 944ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen DEBUG(dbgs() << ", no interference"); 945ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen if (!BI.LiveThrough) { 946ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen DEBUG(dbgs() << ", killed in block.\n"); 947a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen SE->useIntv(Start, SE->leaveIntvAfter(BI.LastUse)); 948ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen continue; 949ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen } 950ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen if (!RegOut) { 951612f7807c581eafb7c8105e1a55c8d839033bfb3Jakob Stoklund Olesen SlotIndex LastSplitPoint = SA->getLastSplitPoint(BI.MBB->getNumber()); 952ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Block is live-through, but exit bundle is on the stack. 953ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Spill immediately after the last use. 954612f7807c581eafb7c8105e1a55c8d839033bfb3Jakob Stoklund Olesen if (BI.LastUse < LastSplitPoint) { 9555c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen DEBUG(dbgs() << ", uses, stack-out.\n"); 9566c8afd728eb02742ce320ecd39bcf3774d8423b7Jakob Stoklund Olesen SE->useIntv(Start, SE->leaveIntvAfter(BI.LastUse)); 9575c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen continue; 9585c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen } 9595c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen // The last use is after the last split point, it is probably an 9605c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen // indirect jump. 9615c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen DEBUG(dbgs() << ", uses at " << BI.LastUse << " after split point " 962612f7807c581eafb7c8105e1a55c8d839033bfb3Jakob Stoklund Olesen << LastSplitPoint << ", stack-out.\n"); 963612f7807c581eafb7c8105e1a55c8d839033bfb3Jakob Stoklund Olesen SlotIndex SegEnd = SE->leaveIntvBefore(LastSplitPoint); 9646c8afd728eb02742ce320ecd39bcf3774d8423b7Jakob Stoklund Olesen SE->useIntv(Start, SegEnd); 9655c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen // Run a double interval from the split to the last use. 9665c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen // This makes it possible to spill the complement without affecting the 9675c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen // indirect branch. 968bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen SE->overlapIntv(SegEnd, BI.LastUse); 969ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen continue; 970ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen } 971ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Register is live-through. 972ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen DEBUG(dbgs() << ", uses, live-through.\n"); 9736c8afd728eb02742ce320ecd39bcf3774d8423b7Jakob Stoklund Olesen SE->useIntv(Start, Stop); 974ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen continue; 975ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen } 976ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 977ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Block has interference. 978eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen DEBUG(dbgs() << ", interference from " << Intf.first()); 979fe3f99f95c7c9ceaac3ceebbea31e40cfbc157e3Jakob Stoklund Olesen 980a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen if (!BI.LiveThrough && Intf.first() >= BI.LastUse) { 981fe3f99f95c7c9ceaac3ceebbea31e40cfbc157e3Jakob Stoklund Olesen // The interference doesn't reach the outgoing segment. 982a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen DEBUG(dbgs() << " doesn't affect kill at " << BI.LastUse << '\n'); 983a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen SE->useIntv(Start, BI.LastUse); 984fe3f99f95c7c9ceaac3ceebbea31e40cfbc157e3Jakob Stoklund Olesen continue; 985fe3f99f95c7c9ceaac3ceebbea31e40cfbc157e3Jakob Stoklund Olesen } 986fe3f99f95c7c9ceaac3ceebbea31e40cfbc157e3Jakob Stoklund Olesen 987eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen if (Intf.first().getBaseIndex() > BI.FirstUse) { 988ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // There are interference-free uses at the beginning of the block. 989ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Find the last use that can get the register. 990c0de99571297720a37ae405c77fb2ef4aaf00ccdJakob Stoklund Olesen SmallVectorImpl<SlotIndex>::const_iterator UI = 991fe3f99f95c7c9ceaac3ceebbea31e40cfbc157e3Jakob Stoklund Olesen std::lower_bound(SA->UseSlots.begin(), SA->UseSlots.end(), 992eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen Intf.first().getBaseIndex()); 993c0de99571297720a37ae405c77fb2ef4aaf00ccdJakob Stoklund Olesen assert(UI != SA->UseSlots.begin() && "Couldn't find first use"); 994c0de99571297720a37ae405c77fb2ef4aaf00ccdJakob Stoklund Olesen SlotIndex Use = (--UI)->getBoundaryIndex(); 995c0de99571297720a37ae405c77fb2ef4aaf00ccdJakob Stoklund Olesen DEBUG(dbgs() << ", free use at " << *UI << ".\n"); 996bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen SlotIndex SegEnd = SE->leaveIntvAfter(Use); 997eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen assert(SegEnd <= Intf.first() && "Couldn't avoid interference"); 9986c8afd728eb02742ce320ecd39bcf3774d8423b7Jakob Stoklund Olesen SE->useIntv(Start, SegEnd); 999ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen continue; 1000ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen } 1001ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 1002ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Interference is before the first use. 1003ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen DEBUG(dbgs() << " before first use.\n"); 1004bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen SlotIndex SegEnd = SE->leaveIntvAtTop(*BI.MBB); 1005eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen assert(SegEnd <= Intf.first() && "Couldn't avoid interference"); 1006ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen } 1007ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 1008db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen // Handle live-through blocks. 10095db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen for (unsigned i = 0, e = Cand.ActiveBlocks.size(); i != e; ++i) { 10105db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen unsigned Number = Cand.ActiveBlocks[i]; 1011db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen bool RegIn = LiveBundles[Bundles->getBundle(Number, 0)]; 1012db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen bool RegOut = LiveBundles[Bundles->getBundle(Number, 1)]; 1013db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen DEBUG(dbgs() << "Live through BB#" << Number << '\n'); 1014db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen if (RegIn && RegOut) { 1015db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen Intf.moveToBlock(Number); 1016db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen if (!Intf.hasInterference()) { 1017db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen SE->useIntv(Indexes->getMBBStartIdx(Number), 1018db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen Indexes->getMBBEndIdx(Number)); 1019db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen continue; 1020db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen } 1021db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen } 1022db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen MachineBasicBlock *MBB = MF->getBlockNumbered(Number); 1023db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen if (RegIn) 1024db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen SE->leaveIntvAtTop(*MBB); 1025db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen if (RegOut) 1026db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen SE->enterIntvAtEnd(*MBB); 1027db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen } 1028db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen 10290db841f9c2b9a25fb5ecb36e350d3a802c35654cJakob Stoklund Olesen ++NumGlobalSplits; 1030ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 10315928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen SmallVector<unsigned, 8> IntvMap; 10325928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen SE->finish(&IntvMap); 1033f42b66169d75301346e3685fd2b3e45e47806367Jakob Stoklund Olesen DebugVars->splitRegister(VirtReg.reg, LREdit.regs()); 1034f42b66169d75301346e3685fd2b3e45e47806367Jakob Stoklund Olesen 10355928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen LRStage.resize(MRI->getNumVirtRegs()); 1036b2abfa0bf30edf292a27a06e091d03983e644c9bJakob Stoklund Olesen unsigned OrigBlocks = SA->getNumLiveBlocks(); 10375928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen 10385928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen // Sort out the new intervals created by splitting. We get four kinds: 10395928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen // - Remainder intervals should not be split again. 10405928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen // - Candidate intervals can be assigned to Cand.PhysReg. 10415928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen // - Block-local splits are candidates for local splitting. 10425928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen // - DCE leftovers should go back on the queue. 10435928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen for (unsigned i = 0, e = LREdit.size(); i != e; ++i) { 10445928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen unsigned Reg = LREdit.get(i)->reg; 10455928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen 10465928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen // Ignore old intervals from DCE. 10475928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen if (LRStage[Reg] != RS_New) 10485928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen continue; 10495928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen 10505928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen // Remainder interval. Don't try splitting again, spill if it doesn't 10515928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen // allocate. 10525928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen if (IntvMap[i] == 0) { 10535928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen LRStage[Reg] = RS_Global; 10545928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen continue; 10555928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen } 10565928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen 10579f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen // Main interval. Allow repeated splitting as long as the number of live 10589f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen // blocks is strictly decreasing. 10599f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen if (IntvMap[i] == MainIntv) { 10609f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen if (SA->countLiveBlocks(LREdit.get(i)) >= OrigBlocks) { 10619f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen DEBUG(dbgs() << "Main interval covers the same " << OrigBlocks 10629f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen << " blocks as original.\n"); 10639f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen // Don't allow repeated splitting as a safe guard against looping. 10649f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen LRStage[Reg] = RS_Global; 10659f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen } 10669f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen continue; 10679f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen } 10689f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen 10699f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen // Other intervals are treated as new. This includes local intervals created 10709f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen // for blocks with multiple uses, and anything created by DCE. 10715928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen } 10725928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen 1073eb29157d80847c207b77910bcd40a6a6c91ca5c5Jakob Stoklund Olesen if (VerifyEnabled) 1074ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen MF->verify(this, "After splitting live range around region"); 1075ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen} 1076ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 1077b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesenunsigned RAGreedy::tryRegionSplit(LiveInterval &VirtReg, AllocationOrder &Order, 1078b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen SmallVectorImpl<LiveInterval*> &NewVRegs) { 1079200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen float BestCost = Hysteresis * calcSpillCost(); 1080200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen DEBUG(dbgs() << "Cost of isolating all blocks = " << BestCost << '\n'); 10815db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen const unsigned NoCand = ~0u; 10825db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen unsigned BestCand = NoCand; 108396dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen 1084b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen Order.rewind(); 108596dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen for (unsigned Cand = 0; unsigned PhysReg = Order.next(); ++Cand) { 108696dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen if (GlobalCand.size() <= Cand) 108796dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen GlobalCand.resize(Cand+1); 10885db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen GlobalCand[Cand].reset(PhysReg); 108996dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen 10905db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen SpillPlacer->prepare(GlobalCand[Cand].LiveBundles); 10911b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen float Cost; 1092f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen InterferenceCache::Cursor Intf(IntfCache, PhysReg); 1093f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen if (!addSplitConstraints(Intf, Cost)) { 1094f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen DEBUG(dbgs() << PrintReg(PhysReg, TRI) << "\tno positive bundles\n"); 10951b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen continue; 10961b400e840f58489c7950f815780cf08917cecaa8Jakob Stoklund Olesen } 1097f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen DEBUG(dbgs() << PrintReg(PhysReg, TRI) << "\tstatic = " << Cost); 1098200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen if (Cost >= BestCost) { 1099200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen DEBUG({ 1100200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen if (BestCand == NoCand) 1101200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen dbgs() << " worse than no bundles\n"; 1102200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen else 1103200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen dbgs() << " worse than " 1104200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen << PrintReg(GlobalCand[BestCand].PhysReg, TRI) << '\n'; 1105200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen }); 1106b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen continue; 1107874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen } 11085db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen growRegion(GlobalCand[Cand], Intf); 1109ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 11109efa2a263ea470caacef1c85f6ca45e32bf516d3Jakob Stoklund Olesen SpillPlacer->finish(); 11119efa2a263ea470caacef1c85f6ca45e32bf516d3Jakob Stoklund Olesen 1112ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // No live bundles, defer to splitSingleBlocks(). 11135db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen if (!GlobalCand[Cand].LiveBundles.any()) { 1114874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen DEBUG(dbgs() << " no bundles.\n"); 1115ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen continue; 1116874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen } 1117ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 11185db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen Cost += calcGlobalSplitCost(GlobalCand[Cand], Intf); 1119874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen DEBUG({ 1120874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen dbgs() << ", total = " << Cost << " with bundles"; 11215db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen for (int i = GlobalCand[Cand].LiveBundles.find_first(); i>=0; 11225db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen i = GlobalCand[Cand].LiveBundles.find_next(i)) 1123874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen dbgs() << " EB#" << i; 1124874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen dbgs() << ".\n"; 1125874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen }); 1126200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen if (Cost < BestCost) { 11275db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen BestCand = Cand; 1128200729882a47535d4c2496283d26600171531fadJakob Stoklund Olesen BestCost = Hysteresis * Cost; // Prevent rounding effects. 1129b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen } 1130b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen } 1131ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 11325db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen if (BestCand == NoCand) 1133ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen return 0; 1134ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 11355db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen splitAroundRegion(VirtReg, GlobalCand[BestCand], NewVRegs); 1136b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen return 0; 1137b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen} 1138b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 1139ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 1140ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen//===----------------------------------------------------------------------===// 1141034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen// Local Splitting 1142034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 1143034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1144034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1145034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// calcGapWeights - Compute the maximum spill weight that needs to be evicted 1146034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// in order to use PhysReg between two entries in SA->UseSlots. 1147034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// 1148034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// GapWeight[i] represents the gap between UseSlots[i] and UseSlots[i+1]. 1149034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// 1150034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesenvoid RAGreedy::calcGapWeights(unsigned PhysReg, 1151034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen SmallVectorImpl<float> &GapWeight) { 1152db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen assert(SA->getUseBlocks().size() == 1 && "Not a local interval"); 1153db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen const SplitAnalysis::BlockInfo &BI = SA->getUseBlocks().front(); 1154034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const SmallVectorImpl<SlotIndex> &Uses = SA->UseSlots; 1155034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const unsigned NumGaps = Uses.size()-1; 1156034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1157034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Start and end points for the interference check. 1158034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen SlotIndex StartIdx = BI.LiveIn ? BI.FirstUse.getBaseIndex() : BI.FirstUse; 1159034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen SlotIndex StopIdx = BI.LiveOut ? BI.LastUse.getBoundaryIndex() : BI.LastUse; 1160034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1161034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen GapWeight.assign(NumGaps, 0.0f); 1162034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1163034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Add interference from each overlapping register. 1164034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen for (const unsigned *AI = TRI->getOverlaps(PhysReg); *AI; ++AI) { 1165034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (!query(const_cast<LiveInterval&>(SA->getParent()), *AI) 1166034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen .checkInterference()) 1167034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen continue; 1168034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1169034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // We know that VirtReg is a continuous interval from FirstUse to LastUse, 1170034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // so we don't need InterferenceQuery. 1171034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // 1172034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Interference that overlaps an instruction is counted in both gaps 1173034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // surrounding the instruction. The exception is interference before 1174034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // StartIdx and after StopIdx. 1175034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // 1176034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen LiveIntervalUnion::SegmentIter IntI = PhysReg2LiveUnion[*AI].find(StartIdx); 1177034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen for (unsigned Gap = 0; IntI.valid() && IntI.start() < StopIdx; ++IntI) { 1178034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Skip the gaps before IntI. 1179034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen while (Uses[Gap+1].getBoundaryIndex() < IntI.start()) 1180034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (++Gap == NumGaps) 1181034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen break; 1182034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (Gap == NumGaps) 1183034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen break; 1184034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1185034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Update the gaps covered by IntI. 1186034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const float weight = IntI.value()->weight; 1187034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen for (; Gap != NumGaps; ++Gap) { 1188034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen GapWeight[Gap] = std::max(GapWeight[Gap], weight); 1189034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (Uses[Gap+1].getBaseIndex() >= IntI.stop()) 1190034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen break; 1191034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1192034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (Gap == NumGaps) 1193034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen break; 1194034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1195034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1196034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen} 1197034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1198034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// getPrevMappedIndex - Return the slot index of the last non-copy instruction 1199034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// before MI that has a slot index. If MI is the first mapped instruction in 1200034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// its block, return the block start index instead. 1201034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// 1202034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund OlesenSlotIndex RAGreedy::getPrevMappedIndex(const MachineInstr *MI) { 1203034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen assert(MI && "Missing MachineInstr"); 1204034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const MachineBasicBlock *MBB = MI->getParent(); 1205034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen MachineBasicBlock::const_iterator B = MBB->begin(), I = MI; 1206034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen while (I != B) 1207034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (!(--I)->isDebugValue() && !I->isCopy()) 1208034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen return Indexes->getInstructionIndex(I); 1209034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen return Indexes->getMBBStartIdx(MBB); 1210034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen} 1211034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1212034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// calcPrevSlots - Fill in the PrevSlot array with the index of the previous 1213034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// real non-copy instruction for each instruction in SA->UseSlots. 1214034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// 1215034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesenvoid RAGreedy::calcPrevSlots() { 1216034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const SmallVectorImpl<SlotIndex> &Uses = SA->UseSlots; 1217034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen PrevSlot.clear(); 1218034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen PrevSlot.reserve(Uses.size()); 1219034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen for (unsigned i = 0, e = Uses.size(); i != e; ++i) { 1220034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const MachineInstr *MI = Indexes->getInstructionFromIndex(Uses[i]); 1221034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen PrevSlot.push_back(getPrevMappedIndex(MI).getDefIndex()); 1222034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1223034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen} 1224034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1225034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// nextSplitPoint - Find the next index into SA->UseSlots > i such that it may 1226034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// be beneficial to split before UseSlots[i]. 1227034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// 1228034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// 0 is always a valid split point 1229034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesenunsigned RAGreedy::nextSplitPoint(unsigned i) { 1230034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const SmallVectorImpl<SlotIndex> &Uses = SA->UseSlots; 1231034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const unsigned Size = Uses.size(); 1232034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen assert(i != Size && "No split points after the end"); 1233034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Allow split before i when Uses[i] is not adjacent to the previous use. 1234034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen while (++i != Size && PrevSlot[i].getBaseIndex() <= Uses[i-1].getBaseIndex()) 1235034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen ; 1236034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen return i; 1237034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen} 1238034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1239034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// tryLocalSplit - Try to split VirtReg into smaller intervals inside its only 1240034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// basic block. 1241034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// 1242034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesenunsigned RAGreedy::tryLocalSplit(LiveInterval &VirtReg, AllocationOrder &Order, 1243034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen SmallVectorImpl<LiveInterval*> &NewVRegs) { 1244db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen assert(SA->getUseBlocks().size() == 1 && "Not a local interval"); 1245db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen const SplitAnalysis::BlockInfo &BI = SA->getUseBlocks().front(); 1246034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1247034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Note that it is possible to have an interval that is live-in or live-out 1248034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // while only covering a single block - A phi-def can use undef values from 1249034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // predecessors, and the block could be a single-block loop. 1250034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // We don't bother doing anything clever about such a case, we simply assume 1251034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // that the interval is continuous from FirstUse to LastUse. We should make 1252034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // sure that we don't do anything illegal to such an interval, though. 1253034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1254034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const SmallVectorImpl<SlotIndex> &Uses = SA->UseSlots; 1255034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (Uses.size() <= 2) 1256034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen return 0; 1257034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const unsigned NumGaps = Uses.size()-1; 1258034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1259034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen DEBUG({ 1260034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen dbgs() << "tryLocalSplit: "; 1261034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen for (unsigned i = 0, e = Uses.size(); i != e; ++i) 1262034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen dbgs() << ' ' << SA->UseSlots[i]; 1263034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen dbgs() << '\n'; 1264034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen }); 1265034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1266034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // For every use, find the previous mapped non-copy instruction. 1267034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // We use this to detect valid split points, and to estimate new interval 1268034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // sizes. 1269034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen calcPrevSlots(); 1270034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1271034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen unsigned BestBefore = NumGaps; 1272034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen unsigned BestAfter = 0; 1273034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen float BestDiff = 0; 1274034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 127540a42a2ccaaa19a109667ed7abf224cc8733cd9cJakob Stoklund Olesen const float blockFreq = SpillPlacer->getBlockFrequency(BI.MBB->getNumber()); 1276034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen SmallVector<float, 8> GapWeight; 1277034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1278034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen Order.rewind(); 1279034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen while (unsigned PhysReg = Order.next()) { 1280034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Keep track of the largest spill weight that would need to be evicted in 1281034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // order to make use of PhysReg between UseSlots[i] and UseSlots[i+1]. 1282034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen calcGapWeights(PhysReg, GapWeight); 1283034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1284034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Try to find the best sequence of gaps to close. 1285034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // The new spill weight must be larger than any gap interference. 1286034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1287034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // We will split before Uses[SplitBefore] and after Uses[SplitAfter]. 1288034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen unsigned SplitBefore = 0, SplitAfter = nextSplitPoint(1) - 1; 1289034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1290034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // MaxGap should always be max(GapWeight[SplitBefore..SplitAfter-1]). 1291034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // It is the spill weight that needs to be evicted. 1292034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen float MaxGap = GapWeight[0]; 1293034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen for (unsigned i = 1; i != SplitAfter; ++i) 1294034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen MaxGap = std::max(MaxGap, GapWeight[i]); 1295034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1296034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen for (;;) { 1297034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Live before/after split? 1298034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const bool LiveBefore = SplitBefore != 0 || BI.LiveIn; 1299034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const bool LiveAfter = SplitAfter != NumGaps || BI.LiveOut; 1300034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1301034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen DEBUG(dbgs() << PrintReg(PhysReg, TRI) << ' ' 1302034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen << Uses[SplitBefore] << '-' << Uses[SplitAfter] 1303034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen << " i=" << MaxGap); 1304034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1305034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Stop before the interval gets so big we wouldn't be making progress. 1306034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (!LiveBefore && !LiveAfter) { 1307034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen DEBUG(dbgs() << " all\n"); 1308034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen break; 1309034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1310034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Should the interval be extended or shrunk? 1311034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen bool Shrink = true; 1312034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (MaxGap < HUGE_VALF) { 1313034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Estimate the new spill weight. 1314034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // 1315034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Each instruction reads and writes the register, except the first 1316034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // instr doesn't read when !FirstLive, and the last instr doesn't write 1317034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // when !LastLive. 1318034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // 1319034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // We will be inserting copies before and after, so the total number of 1320034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // reads and writes is 2 * EstUses. 1321034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // 1322034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const unsigned EstUses = 2*(SplitAfter - SplitBefore) + 1323034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 2*(LiveBefore + LiveAfter); 1324034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1325034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Try to guess the size of the new interval. This should be trivial, 1326034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // but the slot index of an inserted copy can be a lot smaller than the 1327034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // instruction it is inserted before if there are many dead indexes 1328034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // between them. 1329034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // 1330034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // We measure the distance from the instruction before SplitBefore to 1331034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // get a conservative estimate. 1332034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // 1333034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // The final distance can still be different if inserting copies 1334034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // triggers a slot index renumbering. 1335034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // 1336034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const float EstWeight = normalizeSpillWeight(blockFreq * EstUses, 1337034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen PrevSlot[SplitBefore].distance(Uses[SplitAfter])); 1338034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Would this split be possible to allocate? 1339034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Never allocate all gaps, we wouldn't be making progress. 134066446c803a11a26e4bb39b74091d146ac850ae4cJakob Stoklund Olesen DEBUG(dbgs() << " w=" << EstWeight); 134166446c803a11a26e4bb39b74091d146ac850ae4cJakob Stoklund Olesen if (EstWeight * Hysteresis >= MaxGap) { 1342034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen Shrink = false; 134366446c803a11a26e4bb39b74091d146ac850ae4cJakob Stoklund Olesen float Diff = EstWeight - MaxGap; 1344034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (Diff > BestDiff) { 1345034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen DEBUG(dbgs() << " (best)"); 134666446c803a11a26e4bb39b74091d146ac850ae4cJakob Stoklund Olesen BestDiff = Hysteresis * Diff; 1347034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen BestBefore = SplitBefore; 1348034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen BestAfter = SplitAfter; 1349034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1350034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1351034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1352034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1353034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Try to shrink. 1354034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (Shrink) { 1355034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen SplitBefore = nextSplitPoint(SplitBefore); 1356034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (SplitBefore < SplitAfter) { 1357034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen DEBUG(dbgs() << " shrink\n"); 1358034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Recompute the max when necessary. 1359034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (GapWeight[SplitBefore - 1] >= MaxGap) { 1360034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen MaxGap = GapWeight[SplitBefore]; 1361034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen for (unsigned i = SplitBefore + 1; i != SplitAfter; ++i) 1362034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen MaxGap = std::max(MaxGap, GapWeight[i]); 1363034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1364034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen continue; 1365034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1366034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen MaxGap = 0; 1367034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1368034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1369034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Try to extend the interval. 1370034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (SplitAfter >= NumGaps) { 1371034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen DEBUG(dbgs() << " end\n"); 1372034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen break; 1373034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1374034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1375034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen DEBUG(dbgs() << " extend\n"); 1376034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen for (unsigned e = nextSplitPoint(SplitAfter + 1) - 1; 1377034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen SplitAfter != e; ++SplitAfter) 1378034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen MaxGap = std::max(MaxGap, GapWeight[SplitAfter]); 1379034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen continue; 1380034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1381034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1382034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1383034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Didn't find any candidates? 1384034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (BestBefore == NumGaps) 1385034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen return 0; 1386034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1387034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen DEBUG(dbgs() << "Best local split range: " << Uses[BestBefore] 1388034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen << '-' << Uses[BestAfter] << ", " << BestDiff 1389034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen << ", " << (BestAfter - BestBefore + 1) << " instrs\n"); 1390034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 139192a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen LiveRangeEdit LREdit(VirtReg, NewVRegs, this); 1392bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen SE->reset(LREdit); 1393bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen 1394bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen SE->openIntv(); 1395bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen SlotIndex SegStart = SE->enterIntvBefore(Uses[BestBefore]); 1396bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen SlotIndex SegStop = SE->leaveIntvAfter(Uses[BestAfter]); 1397bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen SE->useIntv(SegStart, SegStop); 1398bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen SE->finish(); 1399f42b66169d75301346e3685fd2b3e45e47806367Jakob Stoklund Olesen DebugVars->splitRegister(VirtReg.reg, LREdit.regs()); 140022a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen setStage(NewVRegs.begin(), NewVRegs.end(), RS_Local); 14010db841f9c2b9a25fb5ecb36e350d3a802c35654cJakob Stoklund Olesen ++NumLocalSplits; 1402034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1403034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen return 0; 1404034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen} 1405034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1406034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 1407ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen// Live Range Splitting 1408ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen//===----------------------------------------------------------------------===// 1409ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 1410ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen/// trySplit - Try to split VirtReg or one of its interferences, making it 1411ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen/// assignable. 1412ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen/// @return Physreg when VirtReg may be assigned and/or new NewVRegs. 1413ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesenunsigned RAGreedy::trySplit(LiveInterval &VirtReg, AllocationOrder &Order, 1414ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen SmallVectorImpl<LiveInterval*>&NewVRegs) { 1415034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Local intervals are handled separately. 1416a2ebf60ef2c434428af7f810b13327ab50245a67Jakob Stoklund Olesen if (LIS->intervalIsInOneMBB(VirtReg)) { 1417a2ebf60ef2c434428af7f810b13327ab50245a67Jakob Stoklund Olesen NamedRegionTimer T("Local Splitting", TimerGroupName, TimePassesIsEnabled); 141822a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen SA->analyze(&VirtReg); 1419034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen return tryLocalSplit(VirtReg, Order, NewVRegs); 1420a2ebf60ef2c434428af7f810b13327ab50245a67Jakob Stoklund Olesen } 1421a2ebf60ef2c434428af7f810b13327ab50245a67Jakob Stoklund Olesen 1422a2ebf60ef2c434428af7f810b13327ab50245a67Jakob Stoklund Olesen NamedRegionTimer T("Global Splitting", TimerGroupName, TimePassesIsEnabled); 1423ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 142422a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // Don't iterate global splitting. 142522a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // Move straight to spilling if this range was produced by a global split. 1426fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen if (getStage(VirtReg) >= RS_Global) 142722a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen return 0; 142822a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen 142922a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen SA->analyze(&VirtReg); 143022a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen 14317d6b6a05b549da70b4473f015c97954c2a422724Jakob Stoklund Olesen // FIXME: SplitAnalysis may repair broken live ranges coming from the 14327d6b6a05b549da70b4473f015c97954c2a422724Jakob Stoklund Olesen // coalescer. That may cause the range to become allocatable which means that 14337d6b6a05b549da70b4473f015c97954c2a422724Jakob Stoklund Olesen // tryRegionSplit won't be making progress. This check should be replaced with 14347d6b6a05b549da70b4473f015c97954c2a422724Jakob Stoklund Olesen // an assertion when the coalescer is fixed. 14357d6b6a05b549da70b4473f015c97954c2a422724Jakob Stoklund Olesen if (SA->didRepairRange()) { 14367d6b6a05b549da70b4473f015c97954c2a422724Jakob Stoklund Olesen // VirtReg has changed, so all cached queries are invalid. 1437bdda37d7fbafe6876f248341837423a4100f95a5Jakob Stoklund Olesen invalidateVirtRegs(); 14387d6b6a05b549da70b4473f015c97954c2a422724Jakob Stoklund Olesen if (unsigned PhysReg = tryAssign(VirtReg, Order, NewVRegs)) 14397d6b6a05b549da70b4473f015c97954c2a422724Jakob Stoklund Olesen return PhysReg; 14407d6b6a05b549da70b4473f015c97954c2a422724Jakob Stoklund Olesen } 14417d6b6a05b549da70b4473f015c97954c2a422724Jakob Stoklund Olesen 1442ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // First try to split around a region spanning multiple blocks. 1443fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen unsigned PhysReg = tryRegionSplit(VirtReg, Order, NewVRegs); 1444fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen if (PhysReg || !NewVRegs.empty()) 1445fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen return PhysReg; 1446ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 1447ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Then isolate blocks with multiple uses. 1448fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen SplitAnalysis::BlockPtrSet Blocks; 1449fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen if (SA->getMultiUseBlocks(Blocks)) { 1450fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen LiveRangeEdit LREdit(VirtReg, NewVRegs, this); 1451fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen SE->reset(LREdit); 1452fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen SE->splitSingleBlocks(Blocks); 1453fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen setStage(NewVRegs.begin(), NewVRegs.end(), RS_Global); 1454fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen if (VerifyEnabled) 1455fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen MF->verify(this, "After splitting live range around basic blocks"); 1456ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen } 1457ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 1458ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Don't assign any physregs. 1459ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen return 0; 1460ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen} 1461ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 1462ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 1463b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen//===----------------------------------------------------------------------===// 1464770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen// Main Entry Point 1465770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen//===----------------------------------------------------------------------===// 1466770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen 1467770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesenunsigned RAGreedy::selectOrSplit(LiveInterval &VirtReg, 1468ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen SmallVectorImpl<LiveInterval*> &NewVRegs) { 1469770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen // First try assigning a free register. 1470dd479e9769eceee9fcc34e2173376024f3aa3c5fJakob Stoklund Olesen AllocationOrder Order(VirtReg.reg, *VRM, ReservedRegs); 14716bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen if (unsigned PhysReg = tryAssign(VirtReg, Order, NewVRegs)) 14726bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen return PhysReg; 1473b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick 1474b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen LiveRangeStage Stage = getStage(VirtReg); 1475b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen DEBUG(dbgs() << StageName[Stage] << '\n'); 1476b8d936bc179ddf31b6350015d74900b74db6b450Jakob Stoklund Olesen 1477d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen if (unsigned PhysReg = tryEvict(VirtReg, Order, NewVRegs)) 1478d2056e51c662765f98413fa071afbff53d87b384Jakob Stoklund Olesen return PhysReg; 1479b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick 1480ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen assert(NewVRegs.empty() && "Cannot append to existing NewVRegs"); 1481ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 1482107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen // The first time we see a live range, don't try to split or spill. 1483107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen // Wait until the second time, when all smaller ranges have been allocated. 1484107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen // This gives a better picture of the interference to split around. 1485f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund Olesen if (Stage == RS_First) { 1486eb29157d80847c207b77910bcd40a6a6c91ca5c5Jakob Stoklund Olesen LRStage[VirtReg.reg] = RS_Second; 1487c1655e1a3c3a566b91b0513b56d61b58da1e36baJakob Stoklund Olesen DEBUG(dbgs() << "wait for second round\n"); 1488107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen NewVRegs.push_back(&VirtReg); 1489107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen return 0; 1490107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen } 1491107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen 1492bf4e10f2f69db24c107cb61d6fe10ed5b2047374Jakob Stoklund Olesen // If we couldn't allocate a register from spilling, there is probably some 1493bf4e10f2f69db24c107cb61d6fe10ed5b2047374Jakob Stoklund Olesen // invalid inline assembly. The base class wil report it. 1494bf4e10f2f69db24c107cb61d6fe10ed5b2047374Jakob Stoklund Olesen if (Stage >= RS_Spill) 1495bf4e10f2f69db24c107cb61d6fe10ed5b2047374Jakob Stoklund Olesen return ~0u; 149622a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen 149746c83c80c5737743c955ff007fa6409804a7abf0Jakob Stoklund Olesen // Try splitting VirtReg or interferences. 1498ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen unsigned PhysReg = trySplit(VirtReg, Order, NewVRegs); 1499ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen if (PhysReg || !NewVRegs.empty()) 1500b64d92e29f38002e52a22fe36ea2d488968e3537Jakob Stoklund Olesen return PhysReg; 1501b64d92e29f38002e52a22fe36ea2d488968e3537Jakob Stoklund Olesen 1502770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen // Finally spill VirtReg itself. 1503770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen NamedRegionTimer T("Spiller", TimerGroupName, TimePassesIsEnabled); 150447dbf6cef761c25cfeb0aa7d624a6f98288bb96aJakob Stoklund Olesen LiveRangeEdit LRE(VirtReg, NewVRegs, this); 150547dbf6cef761c25cfeb0aa7d624a6f98288bb96aJakob Stoklund Olesen spiller().spill(LRE); 15066094bd87d845afabba5b99ec4848fa6116bac682Jakob Stoklund Olesen setStage(NewVRegs.begin(), NewVRegs.end(), RS_Spill); 1507cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 1508c46570dc05851395829bef904bb6ddb1260400d1Jakob Stoklund Olesen if (VerifyEnabled) 1509c46570dc05851395829bef904bb6ddb1260400d1Jakob Stoklund Olesen MF->verify(this, "After spilling"); 1510c46570dc05851395829bef904bb6ddb1260400d1Jakob Stoklund Olesen 1511cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen // The live virtual register requesting allocation was spilled, so tell 1512cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen // the caller not to allocate anything during this round. 1513cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen return 0; 1514cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen} 1515cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 1516cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesenbool RAGreedy::runOnMachineFunction(MachineFunction &mf) { 1517cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen DEBUG(dbgs() << "********** GREEDY REGISTER ALLOCATION **********\n" 1518cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen << "********** Function: " 1519cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen << ((Value*)mf.getFunction())->getName() << '\n'); 1520cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 1521cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen MF = &mf; 1522af24964251e27c2dd863239ba66ffd967b593be5Jakob Stoklund Olesen if (VerifyEnabled) 152389cab93fe999f6d81b4b99a71ac797b7ecfec277Jakob Stoklund Olesen MF->verify(this, "Before greedy register allocator"); 1524af24964251e27c2dd863239ba66ffd967b593be5Jakob Stoklund Olesen 15254680dec5fb3a1b624f13ca9b2a555ca90a07973eJakob Stoklund Olesen RegAllocBase::init(getAnalysis<VirtRegMap>(), getAnalysis<LiveIntervals>()); 1526b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen Indexes = &getAnalysis<SlotIndexes>(); 1527f428eb6c1b09a2322b7a577b0bf2e49dd107bceaJakob Stoklund Olesen DomTree = &getAnalysis<MachineDominatorTree>(); 1528cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen ReservedRegs = TRI->getReservedRegs(*MF); 1529f6dff84d4e44d6c4a46c4f8a18e13c78f804547cJakob Stoklund Olesen SpillerInstance.reset(createInlineSpiller(*this, *MF, *VRM)); 1530d0bb5e2ca05d9c942223bf05e5940bb0c6cc9d3fJakob Stoklund Olesen Loops = &getAnalysis<MachineLoopInfo>(); 1531d0bb5e2ca05d9c942223bf05e5940bb0c6cc9d3fJakob Stoklund Olesen LoopRanges = &getAnalysis<MachineLoopRanges>(); 1532b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen Bundles = &getAnalysis<EdgeBundles>(); 1533b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen SpillPlacer = &getAnalysis<SpillPlacement>(); 1534f42b66169d75301346e3685fd2b3e45e47806367Jakob Stoklund Olesen DebugVars = &getAnalysis<LiveDebugVariables>(); 1535b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 15361b847deb26b52051de39f4cbecd224c9fbd0d1c2Jakob Stoklund Olesen SA.reset(new SplitAnalysis(*VRM, *LIS, *Loops)); 1537bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen SE.reset(new SplitEditor(*SA, *LIS, *VRM, *DomTree)); 153822a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen LRStage.clear(); 153922a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen LRStage.resize(MRI->getNumVirtRegs()); 1540eda0fe8d58b0aaff5f18e7f13edfda3022384e70Jakob Stoklund Olesen IntfCache.init(MF, &PhysReg2LiveUnion[0], Indexes, TRI); 1541d0bb5e2ca05d9c942223bf05e5940bb0c6cc9d3fJakob Stoklund Olesen 1542cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen allocatePhysRegs(); 1543cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen addMBBLiveIns(MF); 15448a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen LIS->addKillFlags(); 1545cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 1546cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen // Run rewriter 1547533f58ecdd8a4732c2f0e149387c4d8d8d4142deJakob Stoklund Olesen { 1548533f58ecdd8a4732c2f0e149387c4d8d8d4142deJakob Stoklund Olesen NamedRegionTimer T("Rewriter", TimerGroupName, TimePassesIsEnabled); 1549ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen VRM->rewrite(Indexes); 1550533f58ecdd8a4732c2f0e149387c4d8d8d4142deJakob Stoklund Olesen } 1551cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 1552cfafc54040cc9722995558124f253d05a038176bJakob Stoklund Olesen // Write out new DBG_VALUE instructions. 1553f42b66169d75301346e3685fd2b3e45e47806367Jakob Stoklund Olesen DebugVars->emitDebugValues(VRM); 1554cfafc54040cc9722995558124f253d05a038176bJakob Stoklund Olesen 1555cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen // The pass output is in VirtRegMap. Release all the transient data. 1556cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen releaseMemory(); 1557cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 1558cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen return true; 1559cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen} 1560