RegAllocGreedy.cpp revision eb29157d80847c207b77910bcd40a6a6c91ca5c5
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" 17cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "LiveIntervalUnion.h" 18f428eb6c1b09a2322b7a577b0bf2e49dd107bceaJakob Stoklund Olesen#include "LiveRangeEdit.h" 19cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "RegAllocBase.h" 20cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "Spiller.h" 21b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen#include "SpillPlacement.h" 22d0bb5e2ca05d9c942223bf05e5940bb0c6cc9d3fJakob Stoklund Olesen#include "SplitKit.h" 23cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "VirtRegMap.h" 240db841f9c2b9a25fb5ecb36e350d3a802c35654cJakob Stoklund Olesen#include "llvm/ADT/Statistic.h" 25cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "llvm/Analysis/AliasAnalysis.h" 26cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "llvm/Function.h" 27cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "llvm/PassAnalysisSupport.h" 28cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "llvm/CodeGen/CalcSpillWeights.h" 29b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen#include "llvm/CodeGen/EdgeBundles.h" 30cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "llvm/CodeGen/LiveIntervalAnalysis.h" 31cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "llvm/CodeGen/LiveStackAnalysis.h" 32f428eb6c1b09a2322b7a577b0bf2e49dd107bceaJakob Stoklund Olesen#include "llvm/CodeGen/MachineDominators.h" 33cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "llvm/CodeGen/MachineFunctionPass.h" 34cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "llvm/CodeGen/MachineLoopInfo.h" 35d0bb5e2ca05d9c942223bf05e5940bb0c6cc9d3fJakob Stoklund Olesen#include "llvm/CodeGen/MachineLoopRanges.h" 36cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "llvm/CodeGen/MachineRegisterInfo.h" 37cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "llvm/CodeGen/Passes.h" 38cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "llvm/CodeGen/RegAllocRegistry.h" 39cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "llvm/CodeGen/RegisterCoalescer.h" 40cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "llvm/Target/TargetOptions.h" 41cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "llvm/Support/Debug.h" 42cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "llvm/Support/ErrorHandling.h" 43cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "llvm/Support/raw_ostream.h" 44533f58ecdd8a4732c2f0e149387c4d8d8d4142deJakob Stoklund Olesen#include "llvm/Support/Timer.h" 45cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 4698d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen#include <queue> 4798d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen 48cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesenusing namespace llvm; 49cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 500db841f9c2b9a25fb5ecb36e350d3a802c35654cJakob Stoklund OlesenSTATISTIC(NumGlobalSplits, "Number of split global live ranges"); 510db841f9c2b9a25fb5ecb36e350d3a802c35654cJakob Stoklund OlesenSTATISTIC(NumLocalSplits, "Number of split local live ranges"); 520db841f9c2b9a25fb5ecb36e350d3a802c35654cJakob Stoklund OlesenSTATISTIC(NumEvicted, "Number of interferences evicted"); 530db841f9c2b9a25fb5ecb36e350d3a802c35654cJakob Stoklund Olesen 54cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesenstatic RegisterRegAlloc greedyRegAlloc("greedy", "greedy register allocator", 55cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen createGreedyRegisterAllocator); 56cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 57cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesennamespace { 5892a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesenclass RAGreedy : public MachineFunctionPass, 5992a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen public RegAllocBase, 6092a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen private LiveRangeEdit::Delegate { 6192a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen 62cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen // context 63cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen MachineFunction *MF; 64cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen BitVector ReservedRegs; 65cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 66cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen // analyses 67b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen SlotIndexes *Indexes; 68cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen LiveStacks *LS; 69f428eb6c1b09a2322b7a577b0bf2e49dd107bceaJakob Stoklund Olesen MachineDominatorTree *DomTree; 70d0bb5e2ca05d9c942223bf05e5940bb0c6cc9d3fJakob Stoklund Olesen MachineLoopInfo *Loops; 71d0bb5e2ca05d9c942223bf05e5940bb0c6cc9d3fJakob Stoklund Olesen MachineLoopRanges *LoopRanges; 72b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen EdgeBundles *Bundles; 73b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen SpillPlacement *SpillPlacer; 74f428eb6c1b09a2322b7a577b0bf2e49dd107bceaJakob Stoklund Olesen 75cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen // state 76cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen std::auto_ptr<Spiller> SpillerInstance; 7798d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen std::priority_queue<std::pair<unsigned, unsigned> > Queue; 7822a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen 7922a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // Live ranges pass through a number of stages as we try to allocate them. 8022a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // Some of the stages may also create new live ranges: 8122a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // 8222a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // - Region splitting. 8322a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // - Per-block splitting. 8422a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // - Local splitting. 8522a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // - Spilling. 8622a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // 8722a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // Ranges produced by one of the stages skip the previous stages when they are 8822a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // dequeued. This improves performance because we can skip interference checks 8922a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // that are unlikely to give any results. It also guarantees that the live 9022a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // range splitting algorithm terminates, something that is otherwise hard to 9122a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // ensure. 9222a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen enum LiveRangeStage { 9322a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen RS_Original, ///< Never seen before, never split. 9422a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen RS_Second, ///< Second time in the queue. 9522a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen RS_Region, ///< Produced by region splitting. 9622a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen RS_Block, ///< Produced by per-block splitting. 9722a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen RS_Local, ///< Produced by local splitting. 9822a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen RS_Spill ///< Produced by spilling. 9922a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen }; 10022a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen 10122a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen IndexedMap<unsigned char, VirtReg2IndexFunctor> LRStage; 10222a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen 10322a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen LiveRangeStage getStage(const LiveInterval &VirtReg) const { 10422a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen return LiveRangeStage(LRStage[VirtReg.reg]); 10522a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen } 10622a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen 10722a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen template<typename Iterator> 10822a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen void setStage(Iterator Begin, Iterator End, LiveRangeStage NewStage) { 10922a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen LRStage.resize(MRI->getNumVirtRegs()); 11022a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen for (;Begin != End; ++Begin) 11122a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen LRStage[(*Begin)->reg] = NewStage; 11222a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen } 113cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 114b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen // splitting state. 11522a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen std::auto_ptr<SplitAnalysis> SA; 116bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen std::auto_ptr<SplitEditor> SE; 117b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 118b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen /// All basic blocks where the current register is live. 11996dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen SmallVector<SpillPlacement::BlockConstraint, 8> SplitConstraints; 120b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 1218b6a933498299773243a6b4e05513d6dc11e4d32Jakob Stoklund Olesen typedef std::pair<SlotIndex, SlotIndex> IndexPair; 1228b6a933498299773243a6b4e05513d6dc11e4d32Jakob Stoklund Olesen 12396dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen /// Global live range splitting candidate info. 12496dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen struct GlobalSplitCandidate { 12596dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen unsigned PhysReg; 12696dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen SmallVector<IndexPair, 8> Interference; 12796dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen BitVector LiveBundles; 12896dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen }; 12996dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen 13096dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen /// Candidate info for for each PhysReg in AllocationOrder. 13196dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen /// This vector never shrinks, but grows to the size of the largest register 13296dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen /// class. 13396dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen SmallVector<GlobalSplitCandidate, 32> GlobalCand; 13496dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen 135034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen /// For every instruction in SA->UseSlots, store the previous non-copy 136034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen /// instruction. 137034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen SmallVector<SlotIndex, 8> PrevSlot; 138034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 139cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesenpublic: 140cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen RAGreedy(); 141cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 142cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen /// Return the pass name. 143cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen virtual const char* getPassName() const { 144533f58ecdd8a4732c2f0e149387c4d8d8d4142deJakob Stoklund Olesen return "Greedy Register Allocator"; 145cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen } 146cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 147cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen /// RAGreedy analysis usage. 148cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen virtual void getAnalysisUsage(AnalysisUsage &AU) const; 149cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen virtual void releaseMemory(); 150cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen virtual Spiller &spiller() { return *SpillerInstance; } 15198d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen virtual void enqueue(LiveInterval *LI); 15298d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen virtual LiveInterval *dequeue(); 153ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen virtual unsigned selectOrSplit(LiveInterval&, 154ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen SmallVectorImpl<LiveInterval*>&); 155cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 156cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen /// Perform register allocation. 157cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen virtual bool runOnMachineFunction(MachineFunction &mf); 158cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 159cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen static char ID; 160b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick 161b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trickprivate: 16292a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen void LRE_WillEraseInstruction(MachineInstr*); 1637792e980c43536814ea42448db9799b4da32fef6Jakob Stoklund Olesen bool LRE_CanEraseVirtReg(unsigned); 1641d5b84508173b93faf513032b3847152e6060791Jakob Stoklund Olesen void LRE_WillShrinkVirtReg(unsigned); 16592a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen 1668b6a933498299773243a6b4e05513d6dc11e4d32Jakob Stoklund Olesen void mapGlobalInterference(unsigned, SmallVectorImpl<IndexPair>&); 16796dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen float calcSplitConstraints(const SmallVectorImpl<IndexPair>&); 16896dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen 169b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen float calcGlobalSplitCost(const BitVector&); 170ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen void splitAroundRegion(LiveInterval&, unsigned, const BitVector&, 171ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen SmallVectorImpl<LiveInterval*>&); 172034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen void calcGapWeights(unsigned, SmallVectorImpl<float>&); 173034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen SlotIndex getPrevMappedIndex(const MachineInstr*); 174034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen void calcPrevSlots(); 175034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen unsigned nextSplitPoint(unsigned); 176d17924b1bd0329acb8be2d7dfc5fc4434c24b832Jakob Stoklund Olesen bool canEvictInterference(LiveInterval&, unsigned, float&); 177b64d92e29f38002e52a22fe36ea2d488968e3537Jakob Stoklund Olesen 17898c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen unsigned tryEvict(LiveInterval&, AllocationOrder&, 17998c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen SmallVectorImpl<LiveInterval*>&); 180b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen unsigned tryRegionSplit(LiveInterval&, AllocationOrder&, 181b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen SmallVectorImpl<LiveInterval*>&); 182034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen unsigned tryLocalSplit(LiveInterval&, AllocationOrder&, 183034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen SmallVectorImpl<LiveInterval*>&); 184b64d92e29f38002e52a22fe36ea2d488968e3537Jakob Stoklund Olesen unsigned trySplit(LiveInterval&, AllocationOrder&, 185b64d92e29f38002e52a22fe36ea2d488968e3537Jakob Stoklund Olesen SmallVectorImpl<LiveInterval*>&); 186cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen}; 187cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen} // end anonymous namespace 188cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 189cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesenchar RAGreedy::ID = 0; 190cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 191cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund OlesenFunctionPass* llvm::createGreedyRegisterAllocator() { 192cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen return new RAGreedy(); 193cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen} 194cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 19522a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund OlesenRAGreedy::RAGreedy(): MachineFunctionPass(ID), LRStage(RS_Original) { 196b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen initializeSlotIndexesPass(*PassRegistry::getPassRegistry()); 197cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen initializeLiveIntervalsPass(*PassRegistry::getPassRegistry()); 198cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen initializeSlotIndexesPass(*PassRegistry::getPassRegistry()); 199cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen initializeStrongPHIEliminationPass(*PassRegistry::getPassRegistry()); 200cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen initializeRegisterCoalescerAnalysisGroup(*PassRegistry::getPassRegistry()); 201cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen initializeCalculateSpillWeightsPass(*PassRegistry::getPassRegistry()); 202cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen initializeLiveStacksPass(*PassRegistry::getPassRegistry()); 203cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry()); 204cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen initializeMachineLoopInfoPass(*PassRegistry::getPassRegistry()); 205d0bb5e2ca05d9c942223bf05e5940bb0c6cc9d3fJakob Stoklund Olesen initializeMachineLoopRangesPass(*PassRegistry::getPassRegistry()); 206cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen initializeVirtRegMapPass(*PassRegistry::getPassRegistry()); 207b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen initializeEdgeBundlesPass(*PassRegistry::getPassRegistry()); 208b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen initializeSpillPlacementPass(*PassRegistry::getPassRegistry()); 209cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen} 210cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 211cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesenvoid RAGreedy::getAnalysisUsage(AnalysisUsage &AU) const { 212cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.setPreservesCFG(); 213cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addRequired<AliasAnalysis>(); 214cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addPreserved<AliasAnalysis>(); 215cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addRequired<LiveIntervals>(); 216b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen AU.addRequired<SlotIndexes>(); 217cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addPreserved<SlotIndexes>(); 218cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen if (StrongPHIElim) 219cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addRequiredID(StrongPHIEliminationID); 220cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addRequiredTransitive<RegisterCoalescer>(); 221cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addRequired<CalculateSpillWeights>(); 222cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addRequired<LiveStacks>(); 223cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addPreserved<LiveStacks>(); 224f428eb6c1b09a2322b7a577b0bf2e49dd107bceaJakob Stoklund Olesen AU.addRequired<MachineDominatorTree>(); 225f428eb6c1b09a2322b7a577b0bf2e49dd107bceaJakob Stoklund Olesen AU.addPreserved<MachineDominatorTree>(); 226cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addRequired<MachineLoopInfo>(); 227cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addPreserved<MachineLoopInfo>(); 228d0bb5e2ca05d9c942223bf05e5940bb0c6cc9d3fJakob Stoklund Olesen AU.addRequired<MachineLoopRanges>(); 229d0bb5e2ca05d9c942223bf05e5940bb0c6cc9d3fJakob Stoklund Olesen AU.addPreserved<MachineLoopRanges>(); 230cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addRequired<VirtRegMap>(); 231cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addPreserved<VirtRegMap>(); 232b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen AU.addRequired<EdgeBundles>(); 233b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen AU.addRequired<SpillPlacement>(); 234cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen MachineFunctionPass::getAnalysisUsage(AU); 235cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen} 236cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 23792a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen 23892a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 23992a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen// LiveRangeEdit delegate methods 24092a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 24192a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen 24292a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesenvoid RAGreedy::LRE_WillEraseInstruction(MachineInstr *MI) { 24392a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen // LRE itself will remove from SlotIndexes and parent basic block. 24492a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen VRM->RemoveMachineInstrFromMaps(MI); 24592a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen} 24692a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen 2477792e980c43536814ea42448db9799b4da32fef6Jakob Stoklund Olesenbool RAGreedy::LRE_CanEraseVirtReg(unsigned VirtReg) { 2487792e980c43536814ea42448db9799b4da32fef6Jakob Stoklund Olesen if (unsigned PhysReg = VRM->getPhys(VirtReg)) { 2497792e980c43536814ea42448db9799b4da32fef6Jakob Stoklund Olesen unassign(LIS->getInterval(VirtReg), PhysReg); 2507792e980c43536814ea42448db9799b4da32fef6Jakob Stoklund Olesen return true; 2517792e980c43536814ea42448db9799b4da32fef6Jakob Stoklund Olesen } 2527792e980c43536814ea42448db9799b4da32fef6Jakob Stoklund Olesen // Unassigned virtreg is probably in the priority queue. 2537792e980c43536814ea42448db9799b4da32fef6Jakob Stoklund Olesen // RegAllocBase will erase it after dequeueing. 2547792e980c43536814ea42448db9799b4da32fef6Jakob Stoklund Olesen return false; 2557792e980c43536814ea42448db9799b4da32fef6Jakob Stoklund Olesen} 25692a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen 2571d5b84508173b93faf513032b3847152e6060791Jakob Stoklund Olesenvoid RAGreedy::LRE_WillShrinkVirtReg(unsigned VirtReg) { 2581d5b84508173b93faf513032b3847152e6060791Jakob Stoklund Olesen unsigned PhysReg = VRM->getPhys(VirtReg); 2591d5b84508173b93faf513032b3847152e6060791Jakob Stoklund Olesen if (!PhysReg) 2601d5b84508173b93faf513032b3847152e6060791Jakob Stoklund Olesen return; 2611d5b84508173b93faf513032b3847152e6060791Jakob Stoklund Olesen 2621d5b84508173b93faf513032b3847152e6060791Jakob Stoklund Olesen // Register is assigned, put it back on the queue for reassignment. 2631d5b84508173b93faf513032b3847152e6060791Jakob Stoklund Olesen LiveInterval &LI = LIS->getInterval(VirtReg); 2641d5b84508173b93faf513032b3847152e6060791Jakob Stoklund Olesen unassign(LI, PhysReg); 2651d5b84508173b93faf513032b3847152e6060791Jakob Stoklund Olesen enqueue(&LI); 2661d5b84508173b93faf513032b3847152e6060791Jakob Stoklund Olesen} 2671d5b84508173b93faf513032b3847152e6060791Jakob Stoklund Olesen 268cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesenvoid RAGreedy::releaseMemory() { 269cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen SpillerInstance.reset(0); 27022a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen LRStage.clear(); 271cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen RegAllocBase::releaseMemory(); 272cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen} 273cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 27498d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesenvoid RAGreedy::enqueue(LiveInterval *LI) { 27598d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen // Prioritize live ranges by size, assigning larger ranges first. 27698d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen // The queue holds (size, reg) pairs. 277107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen const unsigned Size = LI->getSize(); 278107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen const unsigned Reg = LI->reg; 27998d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen assert(TargetRegisterInfo::isVirtualRegister(Reg) && 28098d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen "Can only enqueue virtual registers"); 281107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen unsigned Prio; 28290c1d7ddfc65654f7efe72d56cad65d1af9e6b2aJakob Stoklund Olesen 28322a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen LRStage.grow(Reg); 284eb29157d80847c207b77910bcd40a6a6c91ca5c5Jakob Stoklund Olesen if (LRStage[Reg] == RS_Second) 285eb29157d80847c207b77910bcd40a6a6c91ca5c5Jakob Stoklund Olesen // Unsplit ranges that couldn't be allocated immediately are deferred until 286eb29157d80847c207b77910bcd40a6a6c91ca5c5Jakob Stoklund Olesen // everything else has been allocated. Long ranges are allocated last so 287eb29157d80847c207b77910bcd40a6a6c91ca5c5Jakob Stoklund Olesen // they are split against realistic interference. 288eb29157d80847c207b77910bcd40a6a6c91ca5c5Jakob Stoklund Olesen Prio = (1u << 31) - Size; 289eb29157d80847c207b77910bcd40a6a6c91ca5c5Jakob Stoklund Olesen else { 290eb29157d80847c207b77910bcd40a6a6c91ca5c5Jakob Stoklund Olesen // Everything else is allocated in long->short order. Long ranges that don't 291eb29157d80847c207b77910bcd40a6a6c91ca5c5Jakob Stoklund Olesen // fit should be spilled ASAP so they don't create interference. 292107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen Prio = (1u << 31) + Size; 293d2a50734234a80893ad71da90d9f32032c47e000Jakob Stoklund Olesen 294eb29157d80847c207b77910bcd40a6a6c91ca5c5Jakob Stoklund Olesen // Boost ranges that have a physical register hint. 295eb29157d80847c207b77910bcd40a6a6c91ca5c5Jakob Stoklund Olesen if (TargetRegisterInfo::isPhysicalRegister(VRM->getRegAllocPref(Reg))) 296eb29157d80847c207b77910bcd40a6a6c91ca5c5Jakob Stoklund Olesen Prio |= (1u << 30); 297eb29157d80847c207b77910bcd40a6a6c91ca5c5Jakob Stoklund Olesen } 298107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen 299107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen Queue.push(std::make_pair(Prio, Reg)); 30090c1d7ddfc65654f7efe72d56cad65d1af9e6b2aJakob Stoklund Olesen} 30190c1d7ddfc65654f7efe72d56cad65d1af9e6b2aJakob Stoklund Olesen 30298d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund OlesenLiveInterval *RAGreedy::dequeue() { 30398d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen if (Queue.empty()) 30498d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen return 0; 30598d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen LiveInterval *LI = &LIS->getInterval(Queue.top().second); 30698d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen Queue.pop(); 30798d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen return LI; 30898d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen} 309770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen 310770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen//===----------------------------------------------------------------------===// 31198c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen// Interference eviction 31298c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 3132710638db2eb84cd7eefb8bb9a1b7e5c49413d45Jakob Stoklund Olesen 31498c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen/// canEvict - Return true if all interferences between VirtReg and PhysReg can 31598c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen/// be evicted. Set maxWeight to the maximal spill weight of an interference. 31698c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesenbool RAGreedy::canEvictInterference(LiveInterval &VirtReg, unsigned PhysReg, 317d17924b1bd0329acb8be2d7dfc5fc4434c24b832Jakob Stoklund Olesen float &MaxWeight) { 31898c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen float Weight = 0; 31998c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen for (const unsigned *AliasI = TRI->getOverlaps(PhysReg); *AliasI; ++AliasI) { 32098c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen LiveIntervalUnion::Query &Q = query(VirtReg, *AliasI); 32198c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen // If there is 10 or more interferences, chances are one is smaller. 32298c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen if (Q.collectInterferingVRegs(10) >= 10) 32398c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen return false; 32498c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen 325d17924b1bd0329acb8be2d7dfc5fc4434c24b832Jakob Stoklund Olesen // Check if any interfering live range is heavier than VirtReg. 32698c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen for (unsigned i = 0, e = Q.interferingVRegs().size(); i != e; ++i) { 32798c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen LiveInterval *Intf = Q.interferingVRegs()[i]; 32898c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen if (TargetRegisterInfo::isPhysicalRegister(Intf->reg)) 32998c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen return false; 330d17924b1bd0329acb8be2d7dfc5fc4434c24b832Jakob Stoklund Olesen if (Intf->weight >= VirtReg.weight) 33198c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen return false; 33298c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen Weight = std::max(Weight, Intf->weight); 3332710638db2eb84cd7eefb8bb9a1b7e5c49413d45Jakob Stoklund Olesen } 3342710638db2eb84cd7eefb8bb9a1b7e5c49413d45Jakob Stoklund Olesen } 33598c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen MaxWeight = Weight; 33698c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen return true; 33798c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen} 33898c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen 33998c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen/// tryEvict - Try to evict all interferences for a physreg. 34098c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen/// @param VirtReg Currently unassigned virtual register. 34198c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen/// @param Order Physregs to try. 34298c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen/// @return Physreg to assign VirtReg, or 0. 34398c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesenunsigned RAGreedy::tryEvict(LiveInterval &VirtReg, 34498c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen AllocationOrder &Order, 34598c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen SmallVectorImpl<LiveInterval*> &NewVRegs){ 34698c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen NamedRegionTimer T("Evict", TimerGroupName, TimePassesIsEnabled); 34798c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen 34898c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen // Keep track of the lightest single interference seen so far. 34998c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen float BestWeight = 0; 35098c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen unsigned BestPhys = 0; 35198c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen 35298c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen Order.rewind(); 35398c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen while (unsigned PhysReg = Order.next()) { 35498c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen float Weight = 0; 355d17924b1bd0329acb8be2d7dfc5fc4434c24b832Jakob Stoklund Olesen if (!canEvictInterference(VirtReg, PhysReg, Weight)) 35698c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen continue; 35798c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen 35898c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen // This is an eviction candidate. 35998c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen DEBUG(dbgs() << "max " << PrintReg(PhysReg, TRI) << " interference = " 36098c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen << Weight << '\n'); 36198c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen if (BestPhys && Weight >= BestWeight) 36298c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen continue; 36398c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen 36498c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen // Best so far. 36598c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen BestPhys = PhysReg; 36698c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen BestWeight = Weight; 36757f1e2cee06f9b57995727d786aeb1031c5376bdJakob Stoklund Olesen // Stop if the hint can be used. 36857f1e2cee06f9b57995727d786aeb1031c5376bdJakob Stoklund Olesen if (Order.isHint(PhysReg)) 36957f1e2cee06f9b57995727d786aeb1031c5376bdJakob Stoklund Olesen break; 3702710638db2eb84cd7eefb8bb9a1b7e5c49413d45Jakob Stoklund Olesen } 3712710638db2eb84cd7eefb8bb9a1b7e5c49413d45Jakob Stoklund Olesen 37298c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen if (!BestPhys) 37398c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen return 0; 37498c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen 37598c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen DEBUG(dbgs() << "evicting " << PrintReg(BestPhys, TRI) << " interference\n"); 37698c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen for (const unsigned *AliasI = TRI->getOverlaps(BestPhys); *AliasI; ++AliasI) { 37798c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen LiveIntervalUnion::Query &Q = query(VirtReg, *AliasI); 37898c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen assert(Q.seenAllInterferences() && "Didn't check all interfererences."); 37998c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen for (unsigned i = 0, e = Q.interferingVRegs().size(); i != e; ++i) { 38098c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen LiveInterval *Intf = Q.interferingVRegs()[i]; 38198c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen unassign(*Intf, VRM->getPhys(Intf->reg)); 38298c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen ++NumEvicted; 38398c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen NewVRegs.push_back(Intf); 38498c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen } 38598c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen } 38698c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen return BestPhys; 387b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick} 388b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick 389770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen 390770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen//===----------------------------------------------------------------------===// 391b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen// Region Splitting 392b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen//===----------------------------------------------------------------------===// 393b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 3948b6a933498299773243a6b4e05513d6dc11e4d32Jakob Stoklund Olesen/// mapGlobalInterference - Compute a map of the interference from PhysReg and 3958b6a933498299773243a6b4e05513d6dc11e4d32Jakob Stoklund Olesen/// its aliases in each block in SA->LiveBlocks. 3968b6a933498299773243a6b4e05513d6dc11e4d32Jakob Stoklund Olesen/// If LiveBlocks[i] is live-in, Ranges[i].first is the first interference. 3978b6a933498299773243a6b4e05513d6dc11e4d32Jakob Stoklund Olesen/// If LiveBlocks[i] is live-out, Ranges[i].second is the last interference. 3988b6a933498299773243a6b4e05513d6dc11e4d32Jakob Stoklund Olesenvoid RAGreedy::mapGlobalInterference(unsigned PhysReg, 3998b6a933498299773243a6b4e05513d6dc11e4d32Jakob Stoklund Olesen SmallVectorImpl<IndexPair> &Ranges) { 4008b6a933498299773243a6b4e05513d6dc11e4d32Jakob Stoklund Olesen Ranges.assign(SA->LiveBlocks.size(), IndexPair()); 4018b6a933498299773243a6b4e05513d6dc11e4d32Jakob Stoklund Olesen LiveInterval &VirtReg = const_cast<LiveInterval&>(SA->getParent()); 4028b6a933498299773243a6b4e05513d6dc11e4d32Jakob Stoklund Olesen for (const unsigned *AI = TRI->getOverlaps(PhysReg); *AI; ++AI) { 4038b6a933498299773243a6b4e05513d6dc11e4d32Jakob Stoklund Olesen if (!query(VirtReg, *AI).checkInterference()) 4048b6a933498299773243a6b4e05513d6dc11e4d32Jakob Stoklund Olesen continue; 4058b6a933498299773243a6b4e05513d6dc11e4d32Jakob Stoklund Olesen LiveIntervalUnion::SegmentIter IntI = 4068b6a933498299773243a6b4e05513d6dc11e4d32Jakob Stoklund Olesen PhysReg2LiveUnion[*AI].find(VirtReg.beginIndex()); 4078b6a933498299773243a6b4e05513d6dc11e4d32Jakob Stoklund Olesen if (!IntI.valid()) 4088b6a933498299773243a6b4e05513d6dc11e4d32Jakob Stoklund Olesen continue; 4098b6a933498299773243a6b4e05513d6dc11e4d32Jakob Stoklund Olesen for (unsigned i = 0, e = SA->LiveBlocks.size(); i != e; ++i) { 4108b6a933498299773243a6b4e05513d6dc11e4d32Jakob Stoklund Olesen const SplitAnalysis::BlockInfo &BI = SA->LiveBlocks[i]; 4118b6a933498299773243a6b4e05513d6dc11e4d32Jakob Stoklund Olesen IndexPair &IP = Ranges[i]; 4128b6a933498299773243a6b4e05513d6dc11e4d32Jakob Stoklund Olesen 4138b6a933498299773243a6b4e05513d6dc11e4d32Jakob Stoklund Olesen // Skip interference-free blocks. 4148b6a933498299773243a6b4e05513d6dc11e4d32Jakob Stoklund Olesen if (IntI.start() >= BI.Stop) 4158b6a933498299773243a6b4e05513d6dc11e4d32Jakob Stoklund Olesen continue; 4168b6a933498299773243a6b4e05513d6dc11e4d32Jakob Stoklund Olesen 4178b6a933498299773243a6b4e05513d6dc11e4d32Jakob Stoklund Olesen // First interference in block. 4188b6a933498299773243a6b4e05513d6dc11e4d32Jakob Stoklund Olesen if (BI.LiveIn) { 4198b6a933498299773243a6b4e05513d6dc11e4d32Jakob Stoklund Olesen IntI.advanceTo(BI.Start); 4208b6a933498299773243a6b4e05513d6dc11e4d32Jakob Stoklund Olesen if (!IntI.valid()) 4218b6a933498299773243a6b4e05513d6dc11e4d32Jakob Stoklund Olesen break; 4228b6a933498299773243a6b4e05513d6dc11e4d32Jakob Stoklund Olesen if (IntI.start() >= BI.Stop) 4238b6a933498299773243a6b4e05513d6dc11e4d32Jakob Stoklund Olesen continue; 4248b6a933498299773243a6b4e05513d6dc11e4d32Jakob Stoklund Olesen if (!IP.first.isValid() || IntI.start() < IP.first) 4258b6a933498299773243a6b4e05513d6dc11e4d32Jakob Stoklund Olesen IP.first = IntI.start(); 4268b6a933498299773243a6b4e05513d6dc11e4d32Jakob Stoklund Olesen } 4278b6a933498299773243a6b4e05513d6dc11e4d32Jakob Stoklund Olesen 4288b6a933498299773243a6b4e05513d6dc11e4d32Jakob Stoklund Olesen // Last interference in block. 4298b6a933498299773243a6b4e05513d6dc11e4d32Jakob Stoklund Olesen if (BI.LiveOut) { 4308b6a933498299773243a6b4e05513d6dc11e4d32Jakob Stoklund Olesen IntI.advanceTo(BI.Stop); 4318b6a933498299773243a6b4e05513d6dc11e4d32Jakob Stoklund Olesen if (!IntI.valid() || IntI.start() >= BI.Stop) 4328b6a933498299773243a6b4e05513d6dc11e4d32Jakob Stoklund Olesen --IntI; 4338b6a933498299773243a6b4e05513d6dc11e4d32Jakob Stoklund Olesen if (IntI.stop() <= BI.Start) 4348b6a933498299773243a6b4e05513d6dc11e4d32Jakob Stoklund Olesen continue; 4358b6a933498299773243a6b4e05513d6dc11e4d32Jakob Stoklund Olesen if (!IP.second.isValid() || IntI.stop() > IP.second) 4368b6a933498299773243a6b4e05513d6dc11e4d32Jakob Stoklund Olesen IP.second = IntI.stop(); 4378b6a933498299773243a6b4e05513d6dc11e4d32Jakob Stoklund Olesen } 4388b6a933498299773243a6b4e05513d6dc11e4d32Jakob Stoklund Olesen } 4398b6a933498299773243a6b4e05513d6dc11e4d32Jakob Stoklund Olesen } 4408b6a933498299773243a6b4e05513d6dc11e4d32Jakob Stoklund Olesen} 4418b6a933498299773243a6b4e05513d6dc11e4d32Jakob Stoklund Olesen 44296dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen/// calcSplitConstraints - Fill out the SplitConstraints vector based on the 44396dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen/// interference pattern in Intf. Return the static cost of this split, 44496dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen/// assuming that all preferences in SplitConstraints are met. 44596dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesenfloat RAGreedy::calcSplitConstraints(const SmallVectorImpl<IndexPair> &Intf) { 446b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen // Reset interference dependent info. 44796dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen SplitConstraints.resize(SA->LiveBlocks.size()); 44896dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen float StaticCost = 0; 449f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen for (unsigned i = 0, e = SA->LiveBlocks.size(); i != e; ++i) { 450f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen SplitAnalysis::BlockInfo &BI = SA->LiveBlocks[i]; 45196dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen SpillPlacement::BlockConstraint &BC = SplitConstraints[i]; 45296dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen IndexPair IP = Intf[i]; 45396dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen 454f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen BC.Number = BI.MBB->getNumber(); 455b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen BC.Entry = (BI.Uses && BI.LiveIn) ? 456b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen SpillPlacement::PrefReg : SpillPlacement::DontCare; 457b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen BC.Exit = (BI.Uses && BI.LiveOut) ? 458b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen SpillPlacement::PrefReg : SpillPlacement::DontCare; 459b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 46096dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen // Number of spill code instructions to insert. 46196dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen unsigned Ins = 0; 46296dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen 46396dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen // Interference for the live-in value. 46496dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen if (IP.first.isValid()) { 46596dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen if (IP.first <= BI.Start) 46696dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen BC.Entry = SpillPlacement::MustSpill, Ins += BI.Uses; 46796dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen else if (!BI.Uses) 46896dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen BC.Entry = SpillPlacement::PrefSpill; 46996dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen else if (IP.first < BI.FirstUse) 47096dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen BC.Entry = SpillPlacement::PrefSpill, ++Ins; 47196dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen else if (IP.first < (BI.LiveThrough ? BI.LastUse : BI.Kill)) 47296dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen ++Ins; 473a50c539b7a9e74597da34bfaea5429a48481f18bJakob Stoklund Olesen } 474b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 47596dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen // Interference for the live-out value. 47696dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen if (IP.second.isValid()) { 47796dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen if (IP.second >= BI.LastSplitPoint) 47896dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen BC.Exit = SpillPlacement::MustSpill, Ins += BI.Uses; 47996dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen else if (!BI.Uses) 48096dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen BC.Exit = SpillPlacement::PrefSpill; 48196dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen else if (IP.second > BI.LastUse) 48296dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen BC.Exit = SpillPlacement::PrefSpill, ++Ins; 48396dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen else if (IP.second > (BI.LiveThrough ? BI.FirstUse : BI.Def)) 48496dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen ++Ins; 485b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen } 486b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 48796dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen // Accumulate the total frequency of inserted spill code. 48896dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen if (Ins) 48996dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen StaticCost += Ins * SpillPlacer->getBlockFrequency(BC.Number); 490b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen } 49196dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen return StaticCost; 492b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen} 493b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 49496dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen 495b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen/// calcGlobalSplitCost - Return the global split cost of following the split 496b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen/// pattern in LiveBundles. This cost should be added to the local cost of the 49796dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen/// interference pattern in SplitConstraints. 498b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen/// 499b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesenfloat RAGreedy::calcGlobalSplitCost(const BitVector &LiveBundles) { 500b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen float GlobalCost = 0; 501874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen for (unsigned i = 0, e = SA->LiveBlocks.size(); i != e; ++i) { 502874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen SplitAnalysis::BlockInfo &BI = SA->LiveBlocks[i]; 50396dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen SpillPlacement::BlockConstraint &BC = SplitConstraints[i]; 504874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen bool RegIn = LiveBundles[Bundles->getBundle(BC.Number, 0)]; 505874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen bool RegOut = LiveBundles[Bundles->getBundle(BC.Number, 1)]; 506874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen unsigned Ins = 0; 507874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen 508874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen if (!BI.Uses) 509874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen Ins += RegIn != RegOut; 510874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen else { 511874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen if (BI.LiveIn) 512874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen Ins += RegIn != (BC.Entry == SpillPlacement::PrefReg); 513874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen if (BI.LiveOut) 514874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen Ins += RegOut != (BC.Exit == SpillPlacement::PrefReg); 515874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen } 516874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen if (Ins) 517874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen GlobalCost += Ins * SpillPlacer->getBlockFrequency(BC.Number); 518b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen } 519b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen return GlobalCost; 520b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen} 521b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 522ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen/// splitAroundRegion - Split VirtReg around the region determined by 523ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen/// LiveBundles. Make an effort to avoid interference from PhysReg. 524ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen/// 525ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen/// The 'register' interval is going to contain as many uses as possible while 526ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen/// avoiding interference. The 'stack' interval is the complement constructed by 527ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen/// SplitEditor. It will contain the rest. 528ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen/// 529ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesenvoid RAGreedy::splitAroundRegion(LiveInterval &VirtReg, unsigned PhysReg, 530ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen const BitVector &LiveBundles, 531ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen SmallVectorImpl<LiveInterval*> &NewVRegs) { 532ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen DEBUG({ 533ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen dbgs() << "Splitting around region for " << PrintReg(PhysReg, TRI) 534ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen << " with bundles"; 535ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen for (int i = LiveBundles.find_first(); i>=0; i = LiveBundles.find_next(i)) 536ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen dbgs() << " EB#" << i; 537ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen dbgs() << ".\n"; 538ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen }); 539ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 540ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // First compute interference ranges in the live blocks. 541ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen SmallVector<IndexPair, 8> InterferenceRanges; 5428b6a933498299773243a6b4e05513d6dc11e4d32Jakob Stoklund Olesen mapGlobalInterference(PhysReg, InterferenceRanges); 543ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 54492a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen LiveRangeEdit LREdit(VirtReg, NewVRegs, this); 545bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen SE->reset(LREdit); 546ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 547ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Create the main cross-block interval. 548bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen SE->openIntv(); 549ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 550ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // First add all defs that are live out of a block. 551f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen for (unsigned i = 0, e = SA->LiveBlocks.size(); i != e; ++i) { 552f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen SplitAnalysis::BlockInfo &BI = SA->LiveBlocks[i]; 553ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen bool RegIn = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 0)]; 554ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen bool RegOut = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 1)]; 555ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 556ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Should the register be live out? 557ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen if (!BI.LiveOut || !RegOut) 558ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen continue; 559ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 560ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen IndexPair &IP = InterferenceRanges[i]; 561ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " -> EB#" 5622dfbb3e9125aa0a66feab7a7638815b57da85968Jakob Stoklund Olesen << Bundles->getBundle(BI.MBB->getNumber(), 1) 563c46570dc05851395829bef904bb6ddb1260400d1Jakob Stoklund Olesen << " [" << BI.Start << ';' << BI.LastSplitPoint << '-' 564c46570dc05851395829bef904bb6ddb1260400d1Jakob Stoklund Olesen << BI.Stop << ") intf [" << IP.first << ';' << IP.second 565c46570dc05851395829bef904bb6ddb1260400d1Jakob Stoklund Olesen << ')'); 5662dfbb3e9125aa0a66feab7a7638815b57da85968Jakob Stoklund Olesen 5672dfbb3e9125aa0a66feab7a7638815b57da85968Jakob Stoklund Olesen // The interference interval should either be invalid or overlap MBB. 56836d61863bc83bd2301e0224adc560098b35ec0dcJakob Stoklund Olesen assert((!IP.first.isValid() || IP.first < BI.Stop) && "Bad interference"); 56936d61863bc83bd2301e0224adc560098b35ec0dcJakob Stoklund Olesen assert((!IP.second.isValid() || IP.second > BI.Start) 57036d61863bc83bd2301e0224adc560098b35ec0dcJakob Stoklund Olesen && "Bad interference"); 571ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 572ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Check interference leaving the block. 5732dfbb3e9125aa0a66feab7a7638815b57da85968Jakob Stoklund Olesen if (!IP.second.isValid()) { 574ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Block is interference-free. 575ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen DEBUG(dbgs() << ", no interference"); 576ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen if (!BI.Uses) { 577ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen assert(BI.LiveThrough && "No uses, but not live through block?"); 578ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Block is live-through without interference. 579ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen DEBUG(dbgs() << ", no uses" 580ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen << (RegIn ? ", live-through.\n" : ", stack in.\n")); 581ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen if (!RegIn) 582bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen SE->enterIntvAtEnd(*BI.MBB); 583ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen continue; 584ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen } 585ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen if (!BI.LiveThrough) { 586ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen DEBUG(dbgs() << ", not live-through.\n"); 58736d61863bc83bd2301e0224adc560098b35ec0dcJakob Stoklund Olesen SE->useIntv(SE->enterIntvBefore(BI.Def), BI.Stop); 588ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen continue; 589ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen } 590ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen if (!RegIn) { 591ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Block is live-through, but entry bundle is on the stack. 592ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Reload just before the first use. 593ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen DEBUG(dbgs() << ", not live-in, enter before first use.\n"); 59436d61863bc83bd2301e0224adc560098b35ec0dcJakob Stoklund Olesen SE->useIntv(SE->enterIntvBefore(BI.FirstUse), BI.Stop); 595ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen continue; 596ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen } 597ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen DEBUG(dbgs() << ", live-through.\n"); 598ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen continue; 599ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen } 600ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 601ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Block has interference. 602ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen DEBUG(dbgs() << ", interference to " << IP.second); 603fe3f99f95c7c9ceaac3ceebbea31e40cfbc157e3Jakob Stoklund Olesen 604fe3f99f95c7c9ceaac3ceebbea31e40cfbc157e3Jakob Stoklund Olesen if (!BI.LiveThrough && IP.second <= BI.Def) { 605fe3f99f95c7c9ceaac3ceebbea31e40cfbc157e3Jakob Stoklund Olesen // The interference doesn't reach the outgoing segment. 606fe3f99f95c7c9ceaac3ceebbea31e40cfbc157e3Jakob Stoklund Olesen DEBUG(dbgs() << " doesn't affect def from " << BI.Def << '\n'); 60736d61863bc83bd2301e0224adc560098b35ec0dcJakob Stoklund Olesen SE->useIntv(BI.Def, BI.Stop); 608fe3f99f95c7c9ceaac3ceebbea31e40cfbc157e3Jakob Stoklund Olesen continue; 609fe3f99f95c7c9ceaac3ceebbea31e40cfbc157e3Jakob Stoklund Olesen } 610fe3f99f95c7c9ceaac3ceebbea31e40cfbc157e3Jakob Stoklund Olesen 611fe3f99f95c7c9ceaac3ceebbea31e40cfbc157e3Jakob Stoklund Olesen 612ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen if (!BI.Uses) { 613ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // No uses in block, avoid interference by reloading as late as possible. 614ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen DEBUG(dbgs() << ", no uses.\n"); 615bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen SlotIndex SegStart = SE->enterIntvAtEnd(*BI.MBB); 616de71095a1a930eee81696d5770cdce46d3e19a61Jakob Stoklund Olesen assert(SegStart >= IP.second && "Couldn't avoid interference"); 617ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen continue; 618ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen } 619fe3f99f95c7c9ceaac3ceebbea31e40cfbc157e3Jakob Stoklund Olesen 6208a2bbdeee24b40da6187199658646d04329c139eJakob Stoklund Olesen if (IP.second.getBoundaryIndex() < BI.LastUse) { 621ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // There are interference-free uses at the end of the block. 622ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Find the first use that can get the live-out register. 623c0de99571297720a37ae405c77fb2ef4aaf00ccdJakob Stoklund Olesen SmallVectorImpl<SlotIndex>::const_iterator UI = 624fe3f99f95c7c9ceaac3ceebbea31e40cfbc157e3Jakob Stoklund Olesen std::lower_bound(SA->UseSlots.begin(), SA->UseSlots.end(), 625fe3f99f95c7c9ceaac3ceebbea31e40cfbc157e3Jakob Stoklund Olesen IP.second.getBoundaryIndex()); 626c0de99571297720a37ae405c77fb2ef4aaf00ccdJakob Stoklund Olesen assert(UI != SA->UseSlots.end() && "Couldn't find last use"); 627c0de99571297720a37ae405c77fb2ef4aaf00ccdJakob Stoklund Olesen SlotIndex Use = *UI; 628c0de99571297720a37ae405c77fb2ef4aaf00ccdJakob Stoklund Olesen assert(Use <= BI.LastUse && "Couldn't find last use"); 6298a2bbdeee24b40da6187199658646d04329c139eJakob Stoklund Olesen // Only attempt a split befroe the last split point. 6308a2bbdeee24b40da6187199658646d04329c139eJakob Stoklund Olesen if (Use.getBaseIndex() <= BI.LastSplitPoint) { 6318a2bbdeee24b40da6187199658646d04329c139eJakob Stoklund Olesen DEBUG(dbgs() << ", free use at " << Use << ".\n"); 632bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen SlotIndex SegStart = SE->enterIntvBefore(Use); 6338a2bbdeee24b40da6187199658646d04329c139eJakob Stoklund Olesen assert(SegStart >= IP.second && "Couldn't avoid interference"); 6348a2bbdeee24b40da6187199658646d04329c139eJakob Stoklund Olesen assert(SegStart < BI.LastSplitPoint && "Impossible split point"); 63536d61863bc83bd2301e0224adc560098b35ec0dcJakob Stoklund Olesen SE->useIntv(SegStart, BI.Stop); 6368a2bbdeee24b40da6187199658646d04329c139eJakob Stoklund Olesen continue; 6378a2bbdeee24b40da6187199658646d04329c139eJakob Stoklund Olesen } 638ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen } 639ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 640ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Interference is after the last use. 641ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen DEBUG(dbgs() << " after last use.\n"); 642bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen SlotIndex SegStart = SE->enterIntvAtEnd(*BI.MBB); 643de71095a1a930eee81696d5770cdce46d3e19a61Jakob Stoklund Olesen assert(SegStart >= IP.second && "Couldn't avoid interference"); 644ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen } 645ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 646ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Now all defs leading to live bundles are handled, do everything else. 647f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen for (unsigned i = 0, e = SA->LiveBlocks.size(); i != e; ++i) { 648f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen SplitAnalysis::BlockInfo &BI = SA->LiveBlocks[i]; 649ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen bool RegIn = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 0)]; 650ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen bool RegOut = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 1)]; 651ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 652ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Is the register live-in? 653ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen if (!BI.LiveIn || !RegIn) 654ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen continue; 655ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 656ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // We have an incoming register. Check for interference. 657ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen IndexPair &IP = InterferenceRanges[i]; 658ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 659ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen DEBUG(dbgs() << "EB#" << Bundles->getBundle(BI.MBB->getNumber(), 0) 660c46570dc05851395829bef904bb6ddb1260400d1Jakob Stoklund Olesen << " -> BB#" << BI.MBB->getNumber() << " [" << BI.Start << ';' 661c46570dc05851395829bef904bb6ddb1260400d1Jakob Stoklund Olesen << BI.LastSplitPoint << '-' << BI.Stop << ')'); 662ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 663ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Check interference entering the block. 6642dfbb3e9125aa0a66feab7a7638815b57da85968Jakob Stoklund Olesen if (!IP.first.isValid()) { 665ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Block is interference-free. 666ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen DEBUG(dbgs() << ", no interference"); 667ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen if (!BI.Uses) { 668ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen assert(BI.LiveThrough && "No uses, but not live through block?"); 669ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Block is live-through without interference. 670ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen if (RegOut) { 671ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen DEBUG(dbgs() << ", no uses, live-through.\n"); 67236d61863bc83bd2301e0224adc560098b35ec0dcJakob Stoklund Olesen SE->useIntv(BI.Start, BI.Stop); 673ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen } else { 674ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen DEBUG(dbgs() << ", no uses, stack-out.\n"); 675bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen SE->leaveIntvAtTop(*BI.MBB); 676ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen } 677ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen continue; 678ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen } 679ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen if (!BI.LiveThrough) { 680ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen DEBUG(dbgs() << ", killed in block.\n"); 68136d61863bc83bd2301e0224adc560098b35ec0dcJakob Stoklund Olesen SE->useIntv(BI.Start, SE->leaveIntvAfter(BI.Kill)); 682ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen continue; 683ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen } 684ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen if (!RegOut) { 685ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Block is live-through, but exit bundle is on the stack. 686ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Spill immediately after the last use. 6875c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen if (BI.LastUse < BI.LastSplitPoint) { 6885c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen DEBUG(dbgs() << ", uses, stack-out.\n"); 68936d61863bc83bd2301e0224adc560098b35ec0dcJakob Stoklund Olesen SE->useIntv(BI.Start, SE->leaveIntvAfter(BI.LastUse)); 6905c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen continue; 6915c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen } 6925c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen // The last use is after the last split point, it is probably an 6935c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen // indirect jump. 6945c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen DEBUG(dbgs() << ", uses at " << BI.LastUse << " after split point " 6955c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen << BI.LastSplitPoint << ", stack-out.\n"); 696bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen SlotIndex SegEnd = SE->leaveIntvBefore(BI.LastSplitPoint); 69736d61863bc83bd2301e0224adc560098b35ec0dcJakob Stoklund Olesen SE->useIntv(BI.Start, SegEnd); 6985c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen // Run a double interval from the split to the last use. 6995c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen // This makes it possible to spill the complement without affecting the 7005c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen // indirect branch. 701bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen SE->overlapIntv(SegEnd, BI.LastUse); 702ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen continue; 703ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen } 704ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Register is live-through. 705ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen DEBUG(dbgs() << ", uses, live-through.\n"); 70636d61863bc83bd2301e0224adc560098b35ec0dcJakob Stoklund Olesen SE->useIntv(BI.Start, BI.Stop); 707ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen continue; 708ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen } 709ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 710ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Block has interference. 711ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen DEBUG(dbgs() << ", interference from " << IP.first); 712fe3f99f95c7c9ceaac3ceebbea31e40cfbc157e3Jakob Stoklund Olesen 713fe3f99f95c7c9ceaac3ceebbea31e40cfbc157e3Jakob Stoklund Olesen if (!BI.LiveThrough && IP.first >= BI.Kill) { 714fe3f99f95c7c9ceaac3ceebbea31e40cfbc157e3Jakob Stoklund Olesen // The interference doesn't reach the outgoing segment. 715fe3f99f95c7c9ceaac3ceebbea31e40cfbc157e3Jakob Stoklund Olesen DEBUG(dbgs() << " doesn't affect kill at " << BI.Kill << '\n'); 71636d61863bc83bd2301e0224adc560098b35ec0dcJakob Stoklund Olesen SE->useIntv(BI.Start, BI.Kill); 717fe3f99f95c7c9ceaac3ceebbea31e40cfbc157e3Jakob Stoklund Olesen continue; 718fe3f99f95c7c9ceaac3ceebbea31e40cfbc157e3Jakob Stoklund Olesen } 719fe3f99f95c7c9ceaac3ceebbea31e40cfbc157e3Jakob Stoklund Olesen 720ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen if (!BI.Uses) { 721ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // No uses in block, avoid interference by spilling as soon as possible. 722ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen DEBUG(dbgs() << ", no uses.\n"); 723bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen SlotIndex SegEnd = SE->leaveIntvAtTop(*BI.MBB); 724de71095a1a930eee81696d5770cdce46d3e19a61Jakob Stoklund Olesen assert(SegEnd <= IP.first && "Couldn't avoid interference"); 725ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen continue; 726ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen } 727fe3f99f95c7c9ceaac3ceebbea31e40cfbc157e3Jakob Stoklund Olesen if (IP.first.getBaseIndex() > BI.FirstUse) { 728ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // There are interference-free uses at the beginning of the block. 729ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Find the last use that can get the register. 730c0de99571297720a37ae405c77fb2ef4aaf00ccdJakob Stoklund Olesen SmallVectorImpl<SlotIndex>::const_iterator UI = 731fe3f99f95c7c9ceaac3ceebbea31e40cfbc157e3Jakob Stoklund Olesen std::lower_bound(SA->UseSlots.begin(), SA->UseSlots.end(), 732fe3f99f95c7c9ceaac3ceebbea31e40cfbc157e3Jakob Stoklund Olesen IP.first.getBaseIndex()); 733c0de99571297720a37ae405c77fb2ef4aaf00ccdJakob Stoklund Olesen assert(UI != SA->UseSlots.begin() && "Couldn't find first use"); 734c0de99571297720a37ae405c77fb2ef4aaf00ccdJakob Stoklund Olesen SlotIndex Use = (--UI)->getBoundaryIndex(); 735c0de99571297720a37ae405c77fb2ef4aaf00ccdJakob Stoklund Olesen DEBUG(dbgs() << ", free use at " << *UI << ".\n"); 736bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen SlotIndex SegEnd = SE->leaveIntvAfter(Use); 737de71095a1a930eee81696d5770cdce46d3e19a61Jakob Stoklund Olesen assert(SegEnd <= IP.first && "Couldn't avoid interference"); 73836d61863bc83bd2301e0224adc560098b35ec0dcJakob Stoklund Olesen SE->useIntv(BI.Start, SegEnd); 739ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen continue; 740ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen } 741ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 742ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Interference is before the first use. 743ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen DEBUG(dbgs() << " before first use.\n"); 744bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen SlotIndex SegEnd = SE->leaveIntvAtTop(*BI.MBB); 745de71095a1a930eee81696d5770cdce46d3e19a61Jakob Stoklund Olesen assert(SegEnd <= IP.first && "Couldn't avoid interference"); 746ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen } 747ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 748bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen SE->closeIntv(); 749ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 750ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // FIXME: Should we be more aggressive about splitting the stack region into 751ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // per-block segments? The current approach allows the stack region to 752ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // separate into connected components. Some components may be allocatable. 753bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen SE->finish(); 7540db841f9c2b9a25fb5ecb36e350d3a802c35654cJakob Stoklund Olesen ++NumGlobalSplits; 755ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 756eb29157d80847c207b77910bcd40a6a6c91ca5c5Jakob Stoklund Olesen if (VerifyEnabled) 757ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen MF->verify(this, "After splitting live range around region"); 758ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen} 759ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 760b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesenunsigned RAGreedy::tryRegionSplit(LiveInterval &VirtReg, AllocationOrder &Order, 761b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen SmallVectorImpl<LiveInterval*> &NewVRegs) { 762b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen BitVector LiveBundles, BestBundles; 763b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen float BestCost = 0; 764b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen unsigned BestReg = 0; 76596dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen 766b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen Order.rewind(); 76796dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen for (unsigned Cand = 0; unsigned PhysReg = Order.next(); ++Cand) { 76896dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen if (GlobalCand.size() <= Cand) 76996dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen GlobalCand.resize(Cand+1); 77096dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen GlobalCand[Cand].PhysReg = PhysReg; 77196dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen 77296dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen mapGlobalInterference(PhysReg, GlobalCand[Cand].Interference); 77396dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen float Cost = calcSplitConstraints(GlobalCand[Cand].Interference); 774874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen DEBUG(dbgs() << PrintReg(PhysReg, TRI) << "\tstatic = " << Cost); 775874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen if (BestReg && Cost >= BestCost) { 776874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen DEBUG(dbgs() << " higher.\n"); 777b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen continue; 778874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen } 779ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 78096dcd95a45968de6cb05864cf91aae33169cf179Jakob Stoklund Olesen SpillPlacer->placeSpills(SplitConstraints, LiveBundles); 781ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // No live bundles, defer to splitSingleBlocks(). 782874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen if (!LiveBundles.any()) { 783874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen DEBUG(dbgs() << " no bundles.\n"); 784ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen continue; 785874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen } 786ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 787ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen Cost += calcGlobalSplitCost(LiveBundles); 788874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen DEBUG({ 789874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen dbgs() << ", total = " << Cost << " with bundles"; 790874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen for (int i = LiveBundles.find_first(); i>=0; i = LiveBundles.find_next(i)) 791874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen dbgs() << " EB#" << i; 792874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen dbgs() << ".\n"; 793874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen }); 794b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen if (!BestReg || Cost < BestCost) { 795b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen BestReg = PhysReg; 796874be74179b087be36a6e7869f3aa8b70732aca1Jakob Stoklund Olesen BestCost = 0.98f * Cost; // Prevent rounding effects. 797b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen BestBundles.swap(LiveBundles); 798b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen } 799b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen } 800ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 801ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen if (!BestReg) 802ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen return 0; 803ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 804ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen splitAroundRegion(VirtReg, BestReg, BestBundles, NewVRegs); 80522a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen setStage(NewVRegs.begin(), NewVRegs.end(), RS_Region); 806b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen return 0; 807b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen} 808b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 809ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 810ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen//===----------------------------------------------------------------------===// 811034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen// Local Splitting 812034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 813034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 814034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 815034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// calcGapWeights - Compute the maximum spill weight that needs to be evicted 816034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// in order to use PhysReg between two entries in SA->UseSlots. 817034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// 818034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// GapWeight[i] represents the gap between UseSlots[i] and UseSlots[i+1]. 819034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// 820034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesenvoid RAGreedy::calcGapWeights(unsigned PhysReg, 821034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen SmallVectorImpl<float> &GapWeight) { 822034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen assert(SA->LiveBlocks.size() == 1 && "Not a local interval"); 823034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const SplitAnalysis::BlockInfo &BI = SA->LiveBlocks.front(); 824034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const SmallVectorImpl<SlotIndex> &Uses = SA->UseSlots; 825034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const unsigned NumGaps = Uses.size()-1; 826034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 827034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Start and end points for the interference check. 828034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen SlotIndex StartIdx = BI.LiveIn ? BI.FirstUse.getBaseIndex() : BI.FirstUse; 829034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen SlotIndex StopIdx = BI.LiveOut ? BI.LastUse.getBoundaryIndex() : BI.LastUse; 830034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 831034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen GapWeight.assign(NumGaps, 0.0f); 832034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 833034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Add interference from each overlapping register. 834034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen for (const unsigned *AI = TRI->getOverlaps(PhysReg); *AI; ++AI) { 835034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (!query(const_cast<LiveInterval&>(SA->getParent()), *AI) 836034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen .checkInterference()) 837034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen continue; 838034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 839034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // We know that VirtReg is a continuous interval from FirstUse to LastUse, 840034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // so we don't need InterferenceQuery. 841034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // 842034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Interference that overlaps an instruction is counted in both gaps 843034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // surrounding the instruction. The exception is interference before 844034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // StartIdx and after StopIdx. 845034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // 846034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen LiveIntervalUnion::SegmentIter IntI = PhysReg2LiveUnion[*AI].find(StartIdx); 847034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen for (unsigned Gap = 0; IntI.valid() && IntI.start() < StopIdx; ++IntI) { 848034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Skip the gaps before IntI. 849034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen while (Uses[Gap+1].getBoundaryIndex() < IntI.start()) 850034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (++Gap == NumGaps) 851034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen break; 852034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (Gap == NumGaps) 853034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen break; 854034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 855034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Update the gaps covered by IntI. 856034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const float weight = IntI.value()->weight; 857034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen for (; Gap != NumGaps; ++Gap) { 858034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen GapWeight[Gap] = std::max(GapWeight[Gap], weight); 859034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (Uses[Gap+1].getBaseIndex() >= IntI.stop()) 860034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen break; 861034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 862034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (Gap == NumGaps) 863034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen break; 864034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 865034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 866034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen} 867034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 868034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// getPrevMappedIndex - Return the slot index of the last non-copy instruction 869034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// before MI that has a slot index. If MI is the first mapped instruction in 870034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// its block, return the block start index instead. 871034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// 872034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund OlesenSlotIndex RAGreedy::getPrevMappedIndex(const MachineInstr *MI) { 873034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen assert(MI && "Missing MachineInstr"); 874034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const MachineBasicBlock *MBB = MI->getParent(); 875034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen MachineBasicBlock::const_iterator B = MBB->begin(), I = MI; 876034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen while (I != B) 877034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (!(--I)->isDebugValue() && !I->isCopy()) 878034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen return Indexes->getInstructionIndex(I); 879034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen return Indexes->getMBBStartIdx(MBB); 880034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen} 881034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 882034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// calcPrevSlots - Fill in the PrevSlot array with the index of the previous 883034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// real non-copy instruction for each instruction in SA->UseSlots. 884034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// 885034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesenvoid RAGreedy::calcPrevSlots() { 886034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const SmallVectorImpl<SlotIndex> &Uses = SA->UseSlots; 887034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen PrevSlot.clear(); 888034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen PrevSlot.reserve(Uses.size()); 889034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen for (unsigned i = 0, e = Uses.size(); i != e; ++i) { 890034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const MachineInstr *MI = Indexes->getInstructionFromIndex(Uses[i]); 891034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen PrevSlot.push_back(getPrevMappedIndex(MI).getDefIndex()); 892034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 893034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen} 894034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 895034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// nextSplitPoint - Find the next index into SA->UseSlots > i such that it may 896034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// be beneficial to split before UseSlots[i]. 897034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// 898034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// 0 is always a valid split point 899034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesenunsigned RAGreedy::nextSplitPoint(unsigned i) { 900034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const SmallVectorImpl<SlotIndex> &Uses = SA->UseSlots; 901034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const unsigned Size = Uses.size(); 902034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen assert(i != Size && "No split points after the end"); 903034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Allow split before i when Uses[i] is not adjacent to the previous use. 904034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen while (++i != Size && PrevSlot[i].getBaseIndex() <= Uses[i-1].getBaseIndex()) 905034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen ; 906034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen return i; 907034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen} 908034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 909034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// tryLocalSplit - Try to split VirtReg into smaller intervals inside its only 910034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// basic block. 911034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// 912034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesenunsigned RAGreedy::tryLocalSplit(LiveInterval &VirtReg, AllocationOrder &Order, 913034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen SmallVectorImpl<LiveInterval*> &NewVRegs) { 914034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen assert(SA->LiveBlocks.size() == 1 && "Not a local interval"); 915034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const SplitAnalysis::BlockInfo &BI = SA->LiveBlocks.front(); 916034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 917034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Note that it is possible to have an interval that is live-in or live-out 918034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // while only covering a single block - A phi-def can use undef values from 919034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // predecessors, and the block could be a single-block loop. 920034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // We don't bother doing anything clever about such a case, we simply assume 921034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // that the interval is continuous from FirstUse to LastUse. We should make 922034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // sure that we don't do anything illegal to such an interval, though. 923034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 924034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const SmallVectorImpl<SlotIndex> &Uses = SA->UseSlots; 925034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (Uses.size() <= 2) 926034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen return 0; 927034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const unsigned NumGaps = Uses.size()-1; 928034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 929034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen DEBUG({ 930034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen dbgs() << "tryLocalSplit: "; 931034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen for (unsigned i = 0, e = Uses.size(); i != e; ++i) 932034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen dbgs() << ' ' << SA->UseSlots[i]; 933034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen dbgs() << '\n'; 934034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen }); 935034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 936034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // For every use, find the previous mapped non-copy instruction. 937034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // We use this to detect valid split points, and to estimate new interval 938034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // sizes. 939034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen calcPrevSlots(); 940034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 941034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen unsigned BestBefore = NumGaps; 942034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen unsigned BestAfter = 0; 943034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen float BestDiff = 0; 944034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 94540a42a2ccaaa19a109667ed7abf224cc8733cd9cJakob Stoklund Olesen const float blockFreq = SpillPlacer->getBlockFrequency(BI.MBB->getNumber()); 946034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen SmallVector<float, 8> GapWeight; 947034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 948034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen Order.rewind(); 949034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen while (unsigned PhysReg = Order.next()) { 950034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Keep track of the largest spill weight that would need to be evicted in 951034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // order to make use of PhysReg between UseSlots[i] and UseSlots[i+1]. 952034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen calcGapWeights(PhysReg, GapWeight); 953034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 954034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Try to find the best sequence of gaps to close. 955034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // The new spill weight must be larger than any gap interference. 956034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 957034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // We will split before Uses[SplitBefore] and after Uses[SplitAfter]. 958034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen unsigned SplitBefore = 0, SplitAfter = nextSplitPoint(1) - 1; 959034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 960034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // MaxGap should always be max(GapWeight[SplitBefore..SplitAfter-1]). 961034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // It is the spill weight that needs to be evicted. 962034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen float MaxGap = GapWeight[0]; 963034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen for (unsigned i = 1; i != SplitAfter; ++i) 964034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen MaxGap = std::max(MaxGap, GapWeight[i]); 965034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 966034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen for (;;) { 967034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Live before/after split? 968034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const bool LiveBefore = SplitBefore != 0 || BI.LiveIn; 969034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const bool LiveAfter = SplitAfter != NumGaps || BI.LiveOut; 970034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 971034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen DEBUG(dbgs() << PrintReg(PhysReg, TRI) << ' ' 972034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen << Uses[SplitBefore] << '-' << Uses[SplitAfter] 973034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen << " i=" << MaxGap); 974034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 975034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Stop before the interval gets so big we wouldn't be making progress. 976034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (!LiveBefore && !LiveAfter) { 977034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen DEBUG(dbgs() << " all\n"); 978034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen break; 979034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 980034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Should the interval be extended or shrunk? 981034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen bool Shrink = true; 982034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (MaxGap < HUGE_VALF) { 983034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Estimate the new spill weight. 984034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // 985034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Each instruction reads and writes the register, except the first 986034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // instr doesn't read when !FirstLive, and the last instr doesn't write 987034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // when !LastLive. 988034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // 989034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // We will be inserting copies before and after, so the total number of 990034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // reads and writes is 2 * EstUses. 991034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // 992034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const unsigned EstUses = 2*(SplitAfter - SplitBefore) + 993034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 2*(LiveBefore + LiveAfter); 994034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 995034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Try to guess the size of the new interval. This should be trivial, 996034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // but the slot index of an inserted copy can be a lot smaller than the 997034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // instruction it is inserted before if there are many dead indexes 998034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // between them. 999034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // 1000034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // We measure the distance from the instruction before SplitBefore to 1001034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // get a conservative estimate. 1002034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // 1003034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // The final distance can still be different if inserting copies 1004034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // triggers a slot index renumbering. 1005034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // 1006034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const float EstWeight = normalizeSpillWeight(blockFreq * EstUses, 1007034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen PrevSlot[SplitBefore].distance(Uses[SplitAfter])); 1008034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Would this split be possible to allocate? 1009034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Never allocate all gaps, we wouldn't be making progress. 1010034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen float Diff = EstWeight - MaxGap; 1011034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen DEBUG(dbgs() << " w=" << EstWeight << " d=" << Diff); 1012034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (Diff > 0) { 1013034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen Shrink = false; 1014034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (Diff > BestDiff) { 1015034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen DEBUG(dbgs() << " (best)"); 1016034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen BestDiff = Diff; 1017034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen BestBefore = SplitBefore; 1018034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen BestAfter = SplitAfter; 1019034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1020034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1021034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1022034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1023034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Try to shrink. 1024034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (Shrink) { 1025034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen SplitBefore = nextSplitPoint(SplitBefore); 1026034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (SplitBefore < SplitAfter) { 1027034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen DEBUG(dbgs() << " shrink\n"); 1028034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Recompute the max when necessary. 1029034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (GapWeight[SplitBefore - 1] >= MaxGap) { 1030034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen MaxGap = GapWeight[SplitBefore]; 1031034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen for (unsigned i = SplitBefore + 1; i != SplitAfter; ++i) 1032034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen MaxGap = std::max(MaxGap, GapWeight[i]); 1033034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1034034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen continue; 1035034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1036034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen MaxGap = 0; 1037034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1038034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1039034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Try to extend the interval. 1040034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (SplitAfter >= NumGaps) { 1041034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen DEBUG(dbgs() << " end\n"); 1042034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen break; 1043034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1044034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1045034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen DEBUG(dbgs() << " extend\n"); 1046034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen for (unsigned e = nextSplitPoint(SplitAfter + 1) - 1; 1047034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen SplitAfter != e; ++SplitAfter) 1048034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen MaxGap = std::max(MaxGap, GapWeight[SplitAfter]); 1049034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen continue; 1050034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1051034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1052034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1053034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Didn't find any candidates? 1054034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (BestBefore == NumGaps) 1055034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen return 0; 1056034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1057034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen DEBUG(dbgs() << "Best local split range: " << Uses[BestBefore] 1058034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen << '-' << Uses[BestAfter] << ", " << BestDiff 1059034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen << ", " << (BestAfter - BestBefore + 1) << " instrs\n"); 1060034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 106192a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen LiveRangeEdit LREdit(VirtReg, NewVRegs, this); 1062bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen SE->reset(LREdit); 1063bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen 1064bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen SE->openIntv(); 1065bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen SlotIndex SegStart = SE->enterIntvBefore(Uses[BestBefore]); 1066bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen SlotIndex SegStop = SE->leaveIntvAfter(Uses[BestAfter]); 1067bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen SE->useIntv(SegStart, SegStop); 1068bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen SE->closeIntv(); 1069bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen SE->finish(); 107022a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen setStage(NewVRegs.begin(), NewVRegs.end(), RS_Local); 10710db841f9c2b9a25fb5ecb36e350d3a802c35654cJakob Stoklund Olesen ++NumLocalSplits; 1072034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1073034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen return 0; 1074034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen} 1075034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1076034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 1077ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen// Live Range Splitting 1078ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen//===----------------------------------------------------------------------===// 1079ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 1080ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen/// trySplit - Try to split VirtReg or one of its interferences, making it 1081ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen/// assignable. 1082ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen/// @return Physreg when VirtReg may be assigned and/or new NewVRegs. 1083ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesenunsigned RAGreedy::trySplit(LiveInterval &VirtReg, AllocationOrder &Order, 1084ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen SmallVectorImpl<LiveInterval*>&NewVRegs) { 1085034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Local intervals are handled separately. 1086a2ebf60ef2c434428af7f810b13327ab50245a67Jakob Stoklund Olesen if (LIS->intervalIsInOneMBB(VirtReg)) { 1087a2ebf60ef2c434428af7f810b13327ab50245a67Jakob Stoklund Olesen NamedRegionTimer T("Local Splitting", TimerGroupName, TimePassesIsEnabled); 108822a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen SA->analyze(&VirtReg); 1089034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen return tryLocalSplit(VirtReg, Order, NewVRegs); 1090a2ebf60ef2c434428af7f810b13327ab50245a67Jakob Stoklund Olesen } 1091a2ebf60ef2c434428af7f810b13327ab50245a67Jakob Stoklund Olesen 1092a2ebf60ef2c434428af7f810b13327ab50245a67Jakob Stoklund Olesen NamedRegionTimer T("Global Splitting", TimerGroupName, TimePassesIsEnabled); 1093ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 109422a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // Don't iterate global splitting. 109522a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen // Move straight to spilling if this range was produced by a global split. 109622a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen LiveRangeStage Stage = getStage(VirtReg); 109722a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen if (Stage >= RS_Block) 109822a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen return 0; 109922a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen 110022a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen SA->analyze(&VirtReg); 110122a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen 1102ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // First try to split around a region spanning multiple blocks. 110322a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen if (Stage < RS_Region) { 110422a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen unsigned PhysReg = tryRegionSplit(VirtReg, Order, NewVRegs); 110522a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen if (PhysReg || !NewVRegs.empty()) 110622a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen return PhysReg; 110722a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen } 1108ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 1109ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Then isolate blocks with multiple uses. 111022a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen if (Stage < RS_Block) { 111122a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen SplitAnalysis::BlockPtrSet Blocks; 111222a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen if (SA->getMultiUseBlocks(Blocks)) { 111392a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen LiveRangeEdit LREdit(VirtReg, NewVRegs, this); 1114bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen SE->reset(LREdit); 1115bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen SE->splitSingleBlocks(Blocks); 111622a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen setStage(NewVRegs.begin(), NewVRegs.end(), RS_Block); 111722a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen if (VerifyEnabled) 111822a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen MF->verify(this, "After splitting live range around basic blocks"); 111922a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen } 1120ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen } 1121ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 1122ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Don't assign any physregs. 1123ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen return 0; 1124ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen} 1125ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 1126ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 1127b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen//===----------------------------------------------------------------------===// 1128770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen// Main Entry Point 1129770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen//===----------------------------------------------------------------------===// 1130770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen 1131770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesenunsigned RAGreedy::selectOrSplit(LiveInterval &VirtReg, 1132ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen SmallVectorImpl<LiveInterval*> &NewVRegs) { 1133770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen // First try assigning a free register. 1134dd479e9769eceee9fcc34e2173376024f3aa3c5fJakob Stoklund Olesen AllocationOrder Order(VirtReg.reg, *VRM, ReservedRegs); 1135dd479e9769eceee9fcc34e2173376024f3aa3c5fJakob Stoklund Olesen while (unsigned PhysReg = Order.next()) { 1136770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen if (!checkPhysRegInterference(VirtReg, PhysReg)) 1137cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen return PhysReg; 1138cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen } 1139b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick 114098c8141b6d8fcbb9bd258ebcdd4171f55c5a8e9dJakob Stoklund Olesen if (unsigned PhysReg = tryEvict(VirtReg, Order, NewVRegs)) 114146c83c80c5737743c955ff007fa6409804a7abf0Jakob Stoklund Olesen return PhysReg; 1142b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick 1143ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen assert(NewVRegs.empty() && "Cannot append to existing NewVRegs"); 1144ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 1145107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen // The first time we see a live range, don't try to split or spill. 1146107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen // Wait until the second time, when all smaller ranges have been allocated. 1147107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen // This gives a better picture of the interference to split around. 1148eb29157d80847c207b77910bcd40a6a6c91ca5c5Jakob Stoklund Olesen LiveRangeStage Stage = getStage(VirtReg); 114922a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen if (Stage == RS_Original) { 1150eb29157d80847c207b77910bcd40a6a6c91ca5c5Jakob Stoklund Olesen LRStage[VirtReg.reg] = RS_Second; 1151c1655e1a3c3a566b91b0513b56d61b58da1e36baJakob Stoklund Olesen DEBUG(dbgs() << "wait for second round\n"); 1152107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen NewVRegs.push_back(&VirtReg); 1153107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen return 0; 1154107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen } 1155107d366df762c18294dc00f5de916f62672353ffJakob Stoklund Olesen 115622a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen assert(Stage < RS_Spill && "Cannot allocate after spilling"); 115722a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen 115846c83c80c5737743c955ff007fa6409804a7abf0Jakob Stoklund Olesen // Try splitting VirtReg or interferences. 1159ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen unsigned PhysReg = trySplit(VirtReg, Order, NewVRegs); 1160ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen if (PhysReg || !NewVRegs.empty()) 1161b64d92e29f38002e52a22fe36ea2d488968e3537Jakob Stoklund Olesen return PhysReg; 1162b64d92e29f38002e52a22fe36ea2d488968e3537Jakob Stoklund Olesen 1163770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen // Finally spill VirtReg itself. 1164770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen NamedRegionTimer T("Spiller", TimerGroupName, TimePassesIsEnabled); 116547dbf6cef761c25cfeb0aa7d624a6f98288bb96aJakob Stoklund Olesen LiveRangeEdit LRE(VirtReg, NewVRegs, this); 116647dbf6cef761c25cfeb0aa7d624a6f98288bb96aJakob Stoklund Olesen spiller().spill(LRE); 1167cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 1168c46570dc05851395829bef904bb6ddb1260400d1Jakob Stoklund Olesen if (VerifyEnabled) 1169c46570dc05851395829bef904bb6ddb1260400d1Jakob Stoklund Olesen MF->verify(this, "After spilling"); 1170c46570dc05851395829bef904bb6ddb1260400d1Jakob Stoklund Olesen 1171cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen // The live virtual register requesting allocation was spilled, so tell 1172cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen // the caller not to allocate anything during this round. 1173cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen return 0; 1174cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen} 1175cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 1176cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesenbool RAGreedy::runOnMachineFunction(MachineFunction &mf) { 1177cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen DEBUG(dbgs() << "********** GREEDY REGISTER ALLOCATION **********\n" 1178cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen << "********** Function: " 1179cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen << ((Value*)mf.getFunction())->getName() << '\n'); 1180cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 1181cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen MF = &mf; 1182af24964251e27c2dd863239ba66ffd967b593be5Jakob Stoklund Olesen if (VerifyEnabled) 118389cab93fe999f6d81b4b99a71ac797b7ecfec277Jakob Stoklund Olesen MF->verify(this, "Before greedy register allocator"); 1184af24964251e27c2dd863239ba66ffd967b593be5Jakob Stoklund Olesen 11854680dec5fb3a1b624f13ca9b2a555ca90a07973eJakob Stoklund Olesen RegAllocBase::init(getAnalysis<VirtRegMap>(), getAnalysis<LiveIntervals>()); 1186b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen Indexes = &getAnalysis<SlotIndexes>(); 1187f428eb6c1b09a2322b7a577b0bf2e49dd107bceaJakob Stoklund Olesen DomTree = &getAnalysis<MachineDominatorTree>(); 1188cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen ReservedRegs = TRI->getReservedRegs(*MF); 1189f6dff84d4e44d6c4a46c4f8a18e13c78f804547cJakob Stoklund Olesen SpillerInstance.reset(createInlineSpiller(*this, *MF, *VRM)); 1190d0bb5e2ca05d9c942223bf05e5940bb0c6cc9d3fJakob Stoklund Olesen Loops = &getAnalysis<MachineLoopInfo>(); 1191d0bb5e2ca05d9c942223bf05e5940bb0c6cc9d3fJakob Stoklund Olesen LoopRanges = &getAnalysis<MachineLoopRanges>(); 1192b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen Bundles = &getAnalysis<EdgeBundles>(); 1193b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen SpillPlacer = &getAnalysis<SpillPlacement>(); 1194b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 11951b847deb26b52051de39f4cbecd224c9fbd0d1c2Jakob Stoklund Olesen SA.reset(new SplitAnalysis(*VRM, *LIS, *Loops)); 1196bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen SE.reset(new SplitEditor(*SA, *LIS, *VRM, *DomTree)); 119722a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen LRStage.clear(); 119822a1df6bf24c188dd637a0bb2cf9a2648806b6b1Jakob Stoklund Olesen LRStage.resize(MRI->getNumVirtRegs()); 1199d0bb5e2ca05d9c942223bf05e5940bb0c6cc9d3fJakob Stoklund Olesen 1200cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen allocatePhysRegs(); 1201cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen addMBBLiveIns(MF); 12028a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen LIS->addKillFlags(); 1203cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 1204cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen // Run rewriter 1205533f58ecdd8a4732c2f0e149387c4d8d8d4142deJakob Stoklund Olesen { 1206533f58ecdd8a4732c2f0e149387c4d8d8d4142deJakob Stoklund Olesen NamedRegionTimer T("Rewriter", TimerGroupName, TimePassesIsEnabled); 1207ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen VRM->rewrite(Indexes); 1208533f58ecdd8a4732c2f0e149387c4d8d8d4142deJakob Stoklund Olesen } 1209cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 1210cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen // The pass output is in VirtRegMap. Release all the transient data. 1211cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen releaseMemory(); 1212cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 1213cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen return true; 1214cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen} 1215