RegAllocGreedy.cpp revision ba05c01dabc40373760a20c874103fc58d4377f0
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 46cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesenusing namespace llvm; 47cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 480db841f9c2b9a25fb5ecb36e350d3a802c35654cJakob Stoklund OlesenSTATISTIC(NumGlobalSplits, "Number of split global live ranges"); 490db841f9c2b9a25fb5ecb36e350d3a802c35654cJakob Stoklund OlesenSTATISTIC(NumLocalSplits, "Number of split local live ranges"); 500db841f9c2b9a25fb5ecb36e350d3a802c35654cJakob Stoklund OlesenSTATISTIC(NumReassigned, "Number of interferences reassigned"); 510db841f9c2b9a25fb5ecb36e350d3a802c35654cJakob Stoklund OlesenSTATISTIC(NumEvicted, "Number of interferences evicted"); 520db841f9c2b9a25fb5ecb36e350d3a802c35654cJakob Stoklund Olesen 53cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesenstatic RegisterRegAlloc greedyRegAlloc("greedy", "greedy register allocator", 54cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen createGreedyRegisterAllocator); 55cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 56cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesennamespace { 57cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesenclass RAGreedy : public MachineFunctionPass, public RegAllocBase { 58cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen // context 59cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen MachineFunction *MF; 60cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen BitVector ReservedRegs; 61cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 62cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen // analyses 63b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen SlotIndexes *Indexes; 64cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen LiveStacks *LS; 65f428eb6c1b09a2322b7a577b0bf2e49dd107bceaJakob Stoklund Olesen MachineDominatorTree *DomTree; 66d0bb5e2ca05d9c942223bf05e5940bb0c6cc9d3fJakob Stoklund Olesen MachineLoopInfo *Loops; 67d0bb5e2ca05d9c942223bf05e5940bb0c6cc9d3fJakob Stoklund Olesen MachineLoopRanges *LoopRanges; 68b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen EdgeBundles *Bundles; 69b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen SpillPlacement *SpillPlacer; 70f428eb6c1b09a2322b7a577b0bf2e49dd107bceaJakob Stoklund Olesen 71cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen // state 72cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen std::auto_ptr<Spiller> SpillerInstance; 73d0bb5e2ca05d9c942223bf05e5940bb0c6cc9d3fJakob Stoklund Olesen std::auto_ptr<SplitAnalysis> SA; 74cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 75b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen // splitting state. 76b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 77b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen /// All basic blocks where the current register is live. 78b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen SmallVector<SpillPlacement::BlockConstraint, 8> SpillConstraints; 79b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 80034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen /// For every instruction in SA->UseSlots, store the previous non-copy 81034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen /// instruction. 82034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen SmallVector<SlotIndex, 8> PrevSlot; 83034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 84cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesenpublic: 85cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen RAGreedy(); 86cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 87cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen /// Return the pass name. 88cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen virtual const char* getPassName() const { 89533f58ecdd8a4732c2f0e149387c4d8d8d4142deJakob Stoklund Olesen return "Greedy Register Allocator"; 90cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen } 91cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 92cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen /// RAGreedy analysis usage. 93cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen virtual void getAnalysisUsage(AnalysisUsage &AU) const; 94cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 95cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen virtual void releaseMemory(); 96cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 97cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen virtual Spiller &spiller() { return *SpillerInstance; } 98cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 9990c1d7ddfc65654f7efe72d56cad65d1af9e6b2aJakob Stoklund Olesen virtual float getPriority(LiveInterval *LI); 100d0bec3e62c98b1f0ef3a41db8f95599b2014c131Jakob Stoklund Olesen 101ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen virtual unsigned selectOrSplit(LiveInterval&, 102ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen SmallVectorImpl<LiveInterval*>&); 103cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 104cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen /// Perform register allocation. 105cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen virtual bool runOnMachineFunction(MachineFunction &mf); 106cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 107cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen static char ID; 108b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick 109b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trickprivate: 11046c83c80c5737743c955ff007fa6409804a7abf0Jakob Stoklund Olesen bool checkUncachedInterference(LiveInterval&, unsigned); 11146c83c80c5737743c955ff007fa6409804a7abf0Jakob Stoklund Olesen LiveInterval *getSingleInterference(LiveInterval&, unsigned); 112b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick bool reassignVReg(LiveInterval &InterferingVReg, unsigned OldPhysReg); 113770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen float calcInterferenceWeight(LiveInterval&, unsigned); 114b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen float calcInterferenceInfo(LiveInterval&, unsigned); 115b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen float calcGlobalSplitCost(const BitVector&); 116ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen void splitAroundRegion(LiveInterval&, unsigned, const BitVector&, 117ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen SmallVectorImpl<LiveInterval*>&); 118034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen void calcGapWeights(unsigned, SmallVectorImpl<float>&); 119034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen SlotIndex getPrevMappedIndex(const MachineInstr*); 120034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen void calcPrevSlots(); 121034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen unsigned nextSplitPoint(unsigned); 122b64d92e29f38002e52a22fe36ea2d488968e3537Jakob Stoklund Olesen 1232710638db2eb84cd7eefb8bb9a1b7e5c49413d45Jakob Stoklund Olesen unsigned tryReassignOrEvict(LiveInterval&, AllocationOrder&, 1242710638db2eb84cd7eefb8bb9a1b7e5c49413d45Jakob Stoklund Olesen SmallVectorImpl<LiveInterval*>&); 125b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen unsigned tryRegionSplit(LiveInterval&, AllocationOrder&, 126b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen SmallVectorImpl<LiveInterval*>&); 127034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen unsigned tryLocalSplit(LiveInterval&, AllocationOrder&, 128034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen SmallVectorImpl<LiveInterval*>&); 129b64d92e29f38002e52a22fe36ea2d488968e3537Jakob Stoklund Olesen unsigned trySplit(LiveInterval&, AllocationOrder&, 130b64d92e29f38002e52a22fe36ea2d488968e3537Jakob Stoklund Olesen SmallVectorImpl<LiveInterval*>&); 131770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen unsigned trySpillInterferences(LiveInterval&, AllocationOrder&, 132770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen SmallVectorImpl<LiveInterval*>&); 133cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen}; 134cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen} // end anonymous namespace 135cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 136cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesenchar RAGreedy::ID = 0; 137cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 138cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund OlesenFunctionPass* llvm::createGreedyRegisterAllocator() { 139cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen return new RAGreedy(); 140cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen} 141cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 142cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund OlesenRAGreedy::RAGreedy(): MachineFunctionPass(ID) { 143b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen initializeSlotIndexesPass(*PassRegistry::getPassRegistry()); 144cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen initializeLiveIntervalsPass(*PassRegistry::getPassRegistry()); 145cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen initializeSlotIndexesPass(*PassRegistry::getPassRegistry()); 146cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen initializeStrongPHIEliminationPass(*PassRegistry::getPassRegistry()); 147cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen initializeRegisterCoalescerAnalysisGroup(*PassRegistry::getPassRegistry()); 148cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen initializeCalculateSpillWeightsPass(*PassRegistry::getPassRegistry()); 149cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen initializeLiveStacksPass(*PassRegistry::getPassRegistry()); 150cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry()); 151cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen initializeMachineLoopInfoPass(*PassRegistry::getPassRegistry()); 152d0bb5e2ca05d9c942223bf05e5940bb0c6cc9d3fJakob Stoklund Olesen initializeMachineLoopRangesPass(*PassRegistry::getPassRegistry()); 153cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen initializeVirtRegMapPass(*PassRegistry::getPassRegistry()); 154b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen initializeEdgeBundlesPass(*PassRegistry::getPassRegistry()); 155b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen initializeSpillPlacementPass(*PassRegistry::getPassRegistry()); 156cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen} 157cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 158cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesenvoid RAGreedy::getAnalysisUsage(AnalysisUsage &AU) const { 159cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.setPreservesCFG(); 160cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addRequired<AliasAnalysis>(); 161cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addPreserved<AliasAnalysis>(); 162cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addRequired<LiveIntervals>(); 163b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen AU.addRequired<SlotIndexes>(); 164cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addPreserved<SlotIndexes>(); 165cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen if (StrongPHIElim) 166cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addRequiredID(StrongPHIEliminationID); 167cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addRequiredTransitive<RegisterCoalescer>(); 168cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addRequired<CalculateSpillWeights>(); 169cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addRequired<LiveStacks>(); 170cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addPreserved<LiveStacks>(); 171f428eb6c1b09a2322b7a577b0bf2e49dd107bceaJakob Stoklund Olesen AU.addRequired<MachineDominatorTree>(); 172f428eb6c1b09a2322b7a577b0bf2e49dd107bceaJakob Stoklund Olesen AU.addPreserved<MachineDominatorTree>(); 173cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addRequired<MachineLoopInfo>(); 174cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addPreserved<MachineLoopInfo>(); 175d0bb5e2ca05d9c942223bf05e5940bb0c6cc9d3fJakob Stoklund Olesen AU.addRequired<MachineLoopRanges>(); 176d0bb5e2ca05d9c942223bf05e5940bb0c6cc9d3fJakob Stoklund Olesen AU.addPreserved<MachineLoopRanges>(); 177cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addRequired<VirtRegMap>(); 178cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addPreserved<VirtRegMap>(); 179b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen AU.addRequired<EdgeBundles>(); 180b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen AU.addRequired<SpillPlacement>(); 181cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen MachineFunctionPass::getAnalysisUsage(AU); 182cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen} 183cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 184cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesenvoid RAGreedy::releaseMemory() { 185cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen SpillerInstance.reset(0); 186cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen RegAllocBase::releaseMemory(); 187cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen} 188cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 18990c1d7ddfc65654f7efe72d56cad65d1af9e6b2aJakob Stoklund Olesenfloat RAGreedy::getPriority(LiveInterval *LI) { 19090c1d7ddfc65654f7efe72d56cad65d1af9e6b2aJakob Stoklund Olesen float Priority = LI->weight; 19190c1d7ddfc65654f7efe72d56cad65d1af9e6b2aJakob Stoklund Olesen 19290c1d7ddfc65654f7efe72d56cad65d1af9e6b2aJakob Stoklund Olesen // Prioritize hinted registers so they are allocated first. 19390c1d7ddfc65654f7efe72d56cad65d1af9e6b2aJakob Stoklund Olesen std::pair<unsigned, unsigned> Hint; 19490c1d7ddfc65654f7efe72d56cad65d1af9e6b2aJakob Stoklund Olesen if (Hint.first || Hint.second) { 19590c1d7ddfc65654f7efe72d56cad65d1af9e6b2aJakob Stoklund Olesen // The hint can be target specific, a virtual register, or a physreg. 19690c1d7ddfc65654f7efe72d56cad65d1af9e6b2aJakob Stoklund Olesen Priority *= 2; 19790c1d7ddfc65654f7efe72d56cad65d1af9e6b2aJakob Stoklund Olesen 19890c1d7ddfc65654f7efe72d56cad65d1af9e6b2aJakob Stoklund Olesen // Prefer physreg hints above anything else. 19990c1d7ddfc65654f7efe72d56cad65d1af9e6b2aJakob Stoklund Olesen if (Hint.first == 0 && TargetRegisterInfo::isPhysicalRegister(Hint.second)) 20090c1d7ddfc65654f7efe72d56cad65d1af9e6b2aJakob Stoklund Olesen Priority *= 2; 20190c1d7ddfc65654f7efe72d56cad65d1af9e6b2aJakob Stoklund Olesen } 20290c1d7ddfc65654f7efe72d56cad65d1af9e6b2aJakob Stoklund Olesen return Priority; 20390c1d7ddfc65654f7efe72d56cad65d1af9e6b2aJakob Stoklund Olesen} 20490c1d7ddfc65654f7efe72d56cad65d1af9e6b2aJakob Stoklund Olesen 205770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen 206770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen//===----------------------------------------------------------------------===// 207770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen// Register Reassignment 208770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen//===----------------------------------------------------------------------===// 209770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen 2106ce219ec64088fc4ee550afbb6cd30621fbba27eJakob Stoklund Olesen// Check interference without using the cache. 2116ce219ec64088fc4ee550afbb6cd30621fbba27eJakob Stoklund Olesenbool RAGreedy::checkUncachedInterference(LiveInterval &VirtReg, 2126ce219ec64088fc4ee550afbb6cd30621fbba27eJakob Stoklund Olesen unsigned PhysReg) { 213257c556d85ba949a1ccff99cd7d1e58417aa6e33Jakob Stoklund Olesen for (const unsigned *AliasI = TRI->getOverlaps(PhysReg); *AliasI; ++AliasI) { 214257c556d85ba949a1ccff99cd7d1e58417aa6e33Jakob Stoklund Olesen LiveIntervalUnion::Query subQ(&VirtReg, &PhysReg2LiveUnion[*AliasI]); 2156ce219ec64088fc4ee550afbb6cd30621fbba27eJakob Stoklund Olesen if (subQ.checkInterference()) 2166ce219ec64088fc4ee550afbb6cd30621fbba27eJakob Stoklund Olesen return true; 2176ce219ec64088fc4ee550afbb6cd30621fbba27eJakob Stoklund Olesen } 2186ce219ec64088fc4ee550afbb6cd30621fbba27eJakob Stoklund Olesen return false; 2196ce219ec64088fc4ee550afbb6cd30621fbba27eJakob Stoklund Olesen} 2206ce219ec64088fc4ee550afbb6cd30621fbba27eJakob Stoklund Olesen 22146c83c80c5737743c955ff007fa6409804a7abf0Jakob Stoklund Olesen/// getSingleInterference - Return the single interfering virtual register 22246c83c80c5737743c955ff007fa6409804a7abf0Jakob Stoklund Olesen/// assigned to PhysReg. Return 0 if more than one virtual register is 22346c83c80c5737743c955ff007fa6409804a7abf0Jakob Stoklund Olesen/// interfering. 22446c83c80c5737743c955ff007fa6409804a7abf0Jakob Stoklund OlesenLiveInterval *RAGreedy::getSingleInterference(LiveInterval &VirtReg, 22546c83c80c5737743c955ff007fa6409804a7abf0Jakob Stoklund Olesen unsigned PhysReg) { 226257c556d85ba949a1ccff99cd7d1e58417aa6e33Jakob Stoklund Olesen // Check physreg and aliases. 22746c83c80c5737743c955ff007fa6409804a7abf0Jakob Stoklund Olesen LiveInterval *Interference = 0; 228257c556d85ba949a1ccff99cd7d1e58417aa6e33Jakob Stoklund Olesen for (const unsigned *AliasI = TRI->getOverlaps(PhysReg); *AliasI; ++AliasI) { 22946c83c80c5737743c955ff007fa6409804a7abf0Jakob Stoklund Olesen LiveIntervalUnion::Query &Q = query(VirtReg, *AliasI); 23046c83c80c5737743c955ff007fa6409804a7abf0Jakob Stoklund Olesen if (Q.checkInterference()) { 231d84de8cf62991597c15e948ecb121ad0233ba4ecJakob Stoklund Olesen if (Interference) 23246c83c80c5737743c955ff007fa6409804a7abf0Jakob Stoklund Olesen return 0; 23346c83c80c5737743c955ff007fa6409804a7abf0Jakob Stoklund Olesen Q.collectInterferingVRegs(1); 234d84de8cf62991597c15e948ecb121ad0233ba4ecJakob Stoklund Olesen if (!Q.seenAllInterferences()) 235d84de8cf62991597c15e948ecb121ad0233ba4ecJakob Stoklund Olesen return 0; 23646c83c80c5737743c955ff007fa6409804a7abf0Jakob Stoklund Olesen Interference = Q.interferingVRegs().front(); 23746c83c80c5737743c955ff007fa6409804a7abf0Jakob Stoklund Olesen } 23846c83c80c5737743c955ff007fa6409804a7abf0Jakob Stoklund Olesen } 23946c83c80c5737743c955ff007fa6409804a7abf0Jakob Stoklund Olesen return Interference; 24046c83c80c5737743c955ff007fa6409804a7abf0Jakob Stoklund Olesen} 24146c83c80c5737743c955ff007fa6409804a7abf0Jakob Stoklund Olesen 242b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick// Attempt to reassign this virtual register to a different physical register. 243b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick// 244b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick// FIXME: we are not yet caching these "second-level" interferences discovered 245b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick// in the sub-queries. These interferences can change with each call to 246b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick// selectOrSplit. However, we could implement a "may-interfere" cache that 247b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick// could be conservatively dirtied when we reassign or split. 248b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick// 249b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick// FIXME: This may result in a lot of alias queries. We could summarize alias 250b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick// live intervals in their parent register's live union, but it's messy. 251b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trickbool RAGreedy::reassignVReg(LiveInterval &InterferingVReg, 25246c83c80c5737743c955ff007fa6409804a7abf0Jakob Stoklund Olesen unsigned WantedPhysReg) { 25346c83c80c5737743c955ff007fa6409804a7abf0Jakob Stoklund Olesen assert(TargetRegisterInfo::isVirtualRegister(InterferingVReg.reg) && 25446c83c80c5737743c955ff007fa6409804a7abf0Jakob Stoklund Olesen "Can only reassign virtual registers"); 25546c83c80c5737743c955ff007fa6409804a7abf0Jakob Stoklund Olesen assert(TRI->regsOverlap(WantedPhysReg, VRM->getPhys(InterferingVReg.reg)) && 256b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick "inconsistent phys reg assigment"); 257b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick 258dd479e9769eceee9fcc34e2173376024f3aa3c5fJakob Stoklund Olesen AllocationOrder Order(InterferingVReg.reg, *VRM, ReservedRegs); 259dd479e9769eceee9fcc34e2173376024f3aa3c5fJakob Stoklund Olesen while (unsigned PhysReg = Order.next()) { 26046c83c80c5737743c955ff007fa6409804a7abf0Jakob Stoklund Olesen // Don't reassign to a WantedPhysReg alias. 26146c83c80c5737743c955ff007fa6409804a7abf0Jakob Stoklund Olesen if (TRI->regsOverlap(PhysReg, WantedPhysReg)) 262b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick continue; 263b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick 2646ce219ec64088fc4ee550afbb6cd30621fbba27eJakob Stoklund Olesen if (checkUncachedInterference(InterferingVReg, PhysReg)) 265b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick continue; 266b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick 267b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick // Reassign the interfering virtual reg to this physical reg. 26846c83c80c5737743c955ff007fa6409804a7abf0Jakob Stoklund Olesen unsigned OldAssign = VRM->getPhys(InterferingVReg.reg); 26946c83c80c5737743c955ff007fa6409804a7abf0Jakob Stoklund Olesen DEBUG(dbgs() << "reassigning: " << InterferingVReg << " from " << 27046c83c80c5737743c955ff007fa6409804a7abf0Jakob Stoklund Olesen TRI->getName(OldAssign) << " to " << TRI->getName(PhysReg) << '\n'); 2712710638db2eb84cd7eefb8bb9a1b7e5c49413d45Jakob Stoklund Olesen unassign(InterferingVReg, OldAssign); 2722710638db2eb84cd7eefb8bb9a1b7e5c49413d45Jakob Stoklund Olesen assign(InterferingVReg, PhysReg); 2730db841f9c2b9a25fb5ecb36e350d3a802c35654cJakob Stoklund Olesen ++NumReassigned; 274b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick return true; 275b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick } 276b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick return false; 277b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick} 278b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick 2792710638db2eb84cd7eefb8bb9a1b7e5c49413d45Jakob Stoklund Olesen/// tryReassignOrEvict - Try to reassign a single interferences to a different 2802710638db2eb84cd7eefb8bb9a1b7e5c49413d45Jakob Stoklund Olesen/// physreg, or evict a single interference with a lower spill weight. 28146c83c80c5737743c955ff007fa6409804a7abf0Jakob Stoklund Olesen/// @param VirtReg Currently unassigned virtual register. 28246c83c80c5737743c955ff007fa6409804a7abf0Jakob Stoklund Olesen/// @param Order Physregs to try. 28346c83c80c5737743c955ff007fa6409804a7abf0Jakob Stoklund Olesen/// @return Physreg to assign VirtReg, or 0. 2842710638db2eb84cd7eefb8bb9a1b7e5c49413d45Jakob Stoklund Olesenunsigned RAGreedy::tryReassignOrEvict(LiveInterval &VirtReg, 2852710638db2eb84cd7eefb8bb9a1b7e5c49413d45Jakob Stoklund Olesen AllocationOrder &Order, 2862710638db2eb84cd7eefb8bb9a1b7e5c49413d45Jakob Stoklund Olesen SmallVectorImpl<LiveInterval*> &NewVRegs){ 28746c83c80c5737743c955ff007fa6409804a7abf0Jakob Stoklund Olesen NamedRegionTimer T("Reassign", TimerGroupName, TimePassesIsEnabled); 2882710638db2eb84cd7eefb8bb9a1b7e5c49413d45Jakob Stoklund Olesen 2892710638db2eb84cd7eefb8bb9a1b7e5c49413d45Jakob Stoklund Olesen // Keep track of the lightest single interference seen so far. 2902710638db2eb84cd7eefb8bb9a1b7e5c49413d45Jakob Stoklund Olesen float BestWeight = VirtReg.weight; 2912710638db2eb84cd7eefb8bb9a1b7e5c49413d45Jakob Stoklund Olesen LiveInterval *BestVirt = 0; 2922710638db2eb84cd7eefb8bb9a1b7e5c49413d45Jakob Stoklund Olesen unsigned BestPhys = 0; 2932710638db2eb84cd7eefb8bb9a1b7e5c49413d45Jakob Stoklund Olesen 29446c83c80c5737743c955ff007fa6409804a7abf0Jakob Stoklund Olesen Order.rewind(); 2952710638db2eb84cd7eefb8bb9a1b7e5c49413d45Jakob Stoklund Olesen while (unsigned PhysReg = Order.next()) { 2962710638db2eb84cd7eefb8bb9a1b7e5c49413d45Jakob Stoklund Olesen LiveInterval *InterferingVReg = getSingleInterference(VirtReg, PhysReg); 2972710638db2eb84cd7eefb8bb9a1b7e5c49413d45Jakob Stoklund Olesen if (!InterferingVReg) 2982710638db2eb84cd7eefb8bb9a1b7e5c49413d45Jakob Stoklund Olesen continue; 2992710638db2eb84cd7eefb8bb9a1b7e5c49413d45Jakob Stoklund Olesen if (TargetRegisterInfo::isPhysicalRegister(InterferingVReg->reg)) 3002710638db2eb84cd7eefb8bb9a1b7e5c49413d45Jakob Stoklund Olesen continue; 3012710638db2eb84cd7eefb8bb9a1b7e5c49413d45Jakob Stoklund Olesen if (reassignVReg(*InterferingVReg, PhysReg)) 30246c83c80c5737743c955ff007fa6409804a7abf0Jakob Stoklund Olesen return PhysReg; 3032710638db2eb84cd7eefb8bb9a1b7e5c49413d45Jakob Stoklund Olesen 3042710638db2eb84cd7eefb8bb9a1b7e5c49413d45Jakob Stoklund Olesen // Cannot reassign, is this an eviction candidate? 3052710638db2eb84cd7eefb8bb9a1b7e5c49413d45Jakob Stoklund Olesen if (InterferingVReg->weight < BestWeight) { 3062710638db2eb84cd7eefb8bb9a1b7e5c49413d45Jakob Stoklund Olesen BestVirt = InterferingVReg; 3072710638db2eb84cd7eefb8bb9a1b7e5c49413d45Jakob Stoklund Olesen BestPhys = PhysReg; 3082710638db2eb84cd7eefb8bb9a1b7e5c49413d45Jakob Stoklund Olesen BestWeight = InterferingVReg->weight; 3092710638db2eb84cd7eefb8bb9a1b7e5c49413d45Jakob Stoklund Olesen } 3102710638db2eb84cd7eefb8bb9a1b7e5c49413d45Jakob Stoklund Olesen } 3112710638db2eb84cd7eefb8bb9a1b7e5c49413d45Jakob Stoklund Olesen 3122710638db2eb84cd7eefb8bb9a1b7e5c49413d45Jakob Stoklund Olesen // Nothing reassigned, can we evict a lighter single interference? 3132710638db2eb84cd7eefb8bb9a1b7e5c49413d45Jakob Stoklund Olesen if (BestVirt) { 3142710638db2eb84cd7eefb8bb9a1b7e5c49413d45Jakob Stoklund Olesen DEBUG(dbgs() << "evicting lighter " << *BestVirt << '\n'); 3152710638db2eb84cd7eefb8bb9a1b7e5c49413d45Jakob Stoklund Olesen unassign(*BestVirt, VRM->getPhys(BestVirt->reg)); 3160db841f9c2b9a25fb5ecb36e350d3a802c35654cJakob Stoklund Olesen ++NumEvicted; 3172710638db2eb84cd7eefb8bb9a1b7e5c49413d45Jakob Stoklund Olesen NewVRegs.push_back(BestVirt); 3182710638db2eb84cd7eefb8bb9a1b7e5c49413d45Jakob Stoklund Olesen return BestPhys; 3192710638db2eb84cd7eefb8bb9a1b7e5c49413d45Jakob Stoklund Olesen } 3202710638db2eb84cd7eefb8bb9a1b7e5c49413d45Jakob Stoklund Olesen 32146c83c80c5737743c955ff007fa6409804a7abf0Jakob Stoklund Olesen return 0; 322b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick} 323b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick 324770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen 325770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen//===----------------------------------------------------------------------===// 326b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen// Region Splitting 327b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen//===----------------------------------------------------------------------===// 328b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 329b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen/// calcInterferenceInfo - Compute per-block outgoing and ingoing constraints 330b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen/// when considering interference from PhysReg. Also compute an optimistic local 331b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen/// cost of this interference pattern. 332b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen/// 333b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen/// The final cost of a split is the local cost + global cost of preferences 334b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen/// broken by SpillPlacement. 335b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen/// 336b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesenfloat RAGreedy::calcInterferenceInfo(LiveInterval &VirtReg, unsigned PhysReg) { 337b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen // Reset interference dependent info. 338f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen SpillConstraints.resize(SA->LiveBlocks.size()); 339f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen for (unsigned i = 0, e = SA->LiveBlocks.size(); i != e; ++i) { 340f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen SplitAnalysis::BlockInfo &BI = SA->LiveBlocks[i]; 341b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen SpillPlacement::BlockConstraint &BC = SpillConstraints[i]; 342f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen BC.Number = BI.MBB->getNumber(); 343b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen BC.Entry = (BI.Uses && BI.LiveIn) ? 344b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen SpillPlacement::PrefReg : SpillPlacement::DontCare; 345b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen BC.Exit = (BI.Uses && BI.LiveOut) ? 346b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen SpillPlacement::PrefReg : SpillPlacement::DontCare; 347b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen BI.OverlapEntry = BI.OverlapExit = false; 348b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen } 349b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 350b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen // Add interference info from each PhysReg alias. 351b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen for (const unsigned *AI = TRI->getOverlaps(PhysReg); *AI; ++AI) { 352b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen if (!query(VirtReg, *AI).checkInterference()) 353b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen continue; 354b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen LiveIntervalUnion::SegmentIter IntI = 355b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen PhysReg2LiveUnion[*AI].find(VirtReg.beginIndex()); 356b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen if (!IntI.valid()) 357b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen continue; 358b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 359a50c539b7a9e74597da34bfaea5429a48481f18bJakob Stoklund Olesen // Determine which blocks have interference live in or after the last split 360a50c539b7a9e74597da34bfaea5429a48481f18bJakob Stoklund Olesen // point. 361f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen for (unsigned i = 0, e = SA->LiveBlocks.size(); i != e; ++i) { 362f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen SplitAnalysis::BlockInfo &BI = SA->LiveBlocks[i]; 363b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen SpillPlacement::BlockConstraint &BC = SpillConstraints[i]; 364b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen SlotIndex Start, Stop; 365b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen tie(Start, Stop) = Indexes->getMBBRange(BI.MBB); 366b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 367b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen // Skip interference-free blocks. 368b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen if (IntI.start() >= Stop) 369b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen continue; 370b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 371a50c539b7a9e74597da34bfaea5429a48481f18bJakob Stoklund Olesen // Is the interference live-in? 372a50c539b7a9e74597da34bfaea5429a48481f18bJakob Stoklund Olesen if (BI.LiveIn) { 373a50c539b7a9e74597da34bfaea5429a48481f18bJakob Stoklund Olesen IntI.advanceTo(Start); 374a50c539b7a9e74597da34bfaea5429a48481f18bJakob Stoklund Olesen if (!IntI.valid()) 375a50c539b7a9e74597da34bfaea5429a48481f18bJakob Stoklund Olesen break; 376a50c539b7a9e74597da34bfaea5429a48481f18bJakob Stoklund Olesen if (IntI.start() <= Start) 377a50c539b7a9e74597da34bfaea5429a48481f18bJakob Stoklund Olesen BC.Entry = SpillPlacement::MustSpill; 378a50c539b7a9e74597da34bfaea5429a48481f18bJakob Stoklund Olesen } 379b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 380a50c539b7a9e74597da34bfaea5429a48481f18bJakob Stoklund Olesen // Is the interference overlapping the last split point? 381a50c539b7a9e74597da34bfaea5429a48481f18bJakob Stoklund Olesen if (BI.LiveOut) { 382a50c539b7a9e74597da34bfaea5429a48481f18bJakob Stoklund Olesen if (IntI.stop() < BI.LastSplitPoint) 38363935420ef1c323b9d9276eadc0ab74ee86a25b5Jakob Stoklund Olesen IntI.advanceTo(BI.LastSplitPoint.getPrevSlot()); 384a50c539b7a9e74597da34bfaea5429a48481f18bJakob Stoklund Olesen if (!IntI.valid()) 385a50c539b7a9e74597da34bfaea5429a48481f18bJakob Stoklund Olesen break; 386a50c539b7a9e74597da34bfaea5429a48481f18bJakob Stoklund Olesen if (IntI.start() < Stop) 387a50c539b7a9e74597da34bfaea5429a48481f18bJakob Stoklund Olesen BC.Exit = SpillPlacement::MustSpill; 388a50c539b7a9e74597da34bfaea5429a48481f18bJakob Stoklund Olesen } 389a50c539b7a9e74597da34bfaea5429a48481f18bJakob Stoklund Olesen } 390b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 391a50c539b7a9e74597da34bfaea5429a48481f18bJakob Stoklund Olesen // Rewind iterator and check other interferences. 392a50c539b7a9e74597da34bfaea5429a48481f18bJakob Stoklund Olesen IntI.find(VirtReg.beginIndex()); 393f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen for (unsigned i = 0, e = SA->LiveBlocks.size(); i != e; ++i) { 394f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen SplitAnalysis::BlockInfo &BI = SA->LiveBlocks[i]; 395a50c539b7a9e74597da34bfaea5429a48481f18bJakob Stoklund Olesen SpillPlacement::BlockConstraint &BC = SpillConstraints[i]; 396a50c539b7a9e74597da34bfaea5429a48481f18bJakob Stoklund Olesen SlotIndex Start, Stop; 397a50c539b7a9e74597da34bfaea5429a48481f18bJakob Stoklund Olesen tie(Start, Stop) = Indexes->getMBBRange(BI.MBB); 398a50c539b7a9e74597da34bfaea5429a48481f18bJakob Stoklund Olesen 399a50c539b7a9e74597da34bfaea5429a48481f18bJakob Stoklund Olesen // Skip interference-free blocks. 400a50c539b7a9e74597da34bfaea5429a48481f18bJakob Stoklund Olesen if (IntI.start() >= Stop) 401a50c539b7a9e74597da34bfaea5429a48481f18bJakob Stoklund Olesen continue; 402a50c539b7a9e74597da34bfaea5429a48481f18bJakob Stoklund Olesen 403a50c539b7a9e74597da34bfaea5429a48481f18bJakob Stoklund Olesen // Handle transparent blocks with interference separately. 404a50c539b7a9e74597da34bfaea5429a48481f18bJakob Stoklund Olesen // Transparent blocks never incur any fixed cost. 405a50c539b7a9e74597da34bfaea5429a48481f18bJakob Stoklund Olesen if (BI.LiveThrough && !BI.Uses) { 406a50c539b7a9e74597da34bfaea5429a48481f18bJakob Stoklund Olesen IntI.advanceTo(Start); 407b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen if (!IntI.valid()) 408b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen break; 409a50c539b7a9e74597da34bfaea5429a48481f18bJakob Stoklund Olesen if (IntI.start() >= Stop) 410a50c539b7a9e74597da34bfaea5429a48481f18bJakob Stoklund Olesen continue; 411a50c539b7a9e74597da34bfaea5429a48481f18bJakob Stoklund Olesen 412a50c539b7a9e74597da34bfaea5429a48481f18bJakob Stoklund Olesen if (BC.Entry != SpillPlacement::MustSpill) 413a50c539b7a9e74597da34bfaea5429a48481f18bJakob Stoklund Olesen BC.Entry = SpillPlacement::PrefSpill; 414a50c539b7a9e74597da34bfaea5429a48481f18bJakob Stoklund Olesen if (BC.Exit != SpillPlacement::MustSpill) 415a50c539b7a9e74597da34bfaea5429a48481f18bJakob Stoklund Olesen BC.Exit = SpillPlacement::PrefSpill; 416b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen continue; 417b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen } 418b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 419b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen // Now we only have blocks with uses left. 420b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen // Check if the interference overlaps the uses. 421b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen assert(BI.Uses && "Non-transparent block without any uses"); 422b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 423b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen // Check interference on entry. 424b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen if (BI.LiveIn && BC.Entry != SpillPlacement::MustSpill) { 425b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen IntI.advanceTo(Start); 426b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen if (!IntI.valid()) 427b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen break; 428b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen // Not live in, but before the first use. 429a50c539b7a9e74597da34bfaea5429a48481f18bJakob Stoklund Olesen if (IntI.start() < BI.FirstUse) 430b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen BC.Entry = SpillPlacement::PrefSpill; 431b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen } 432b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 433b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen // Does interference overlap the uses in the entry segment 434b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen // [FirstUse;Kill)? 435b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen if (BI.LiveIn && !BI.OverlapEntry) { 436b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen IntI.advanceTo(BI.FirstUse); 437b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen if (!IntI.valid()) 438b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen break; 439b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen // A live-through interval has no kill. 440b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen // Check [FirstUse;LastUse) instead. 441b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen if (IntI.start() < (BI.LiveThrough ? BI.LastUse : BI.Kill)) 442b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen BI.OverlapEntry = true; 443b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen } 444b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 445b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen // Does interference overlap the uses in the exit segment [Def;LastUse)? 446b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen if (BI.LiveOut && !BI.LiveThrough && !BI.OverlapExit) { 447b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen IntI.advanceTo(BI.Def); 448b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen if (!IntI.valid()) 449b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen break; 450b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen if (IntI.start() < BI.LastUse) 451b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen BI.OverlapExit = true; 452b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen } 453b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 454b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen // Check interference on exit. 455b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen if (BI.LiveOut && BC.Exit != SpillPlacement::MustSpill) { 456b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen // Check interference between LastUse and Stop. 457b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen if (BC.Exit != SpillPlacement::PrefSpill) { 458b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen IntI.advanceTo(BI.LastUse); 459b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen if (!IntI.valid()) 460b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen break; 461b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen if (IntI.start() < Stop) 462b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen BC.Exit = SpillPlacement::PrefSpill; 463b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen } 464b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen } 465b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen } 466b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen } 467b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 468b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen // Accumulate a local cost of this interference pattern. 469b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen float LocalCost = 0; 470f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen for (unsigned i = 0, e = SA->LiveBlocks.size(); i != e; ++i) { 471f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen SplitAnalysis::BlockInfo &BI = SA->LiveBlocks[i]; 472b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen if (!BI.Uses) 473b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen continue; 474b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen SpillPlacement::BlockConstraint &BC = SpillConstraints[i]; 475b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen unsigned Inserts = 0; 476b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 477b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen // Do we need spill code for the entry segment? 478b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen if (BI.LiveIn) 479b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen Inserts += BI.OverlapEntry || BC.Entry != SpillPlacement::PrefReg; 480b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 481b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen // For the exit segment? 482b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen if (BI.LiveOut) 483b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen Inserts += BI.OverlapExit || BC.Exit != SpillPlacement::PrefReg; 484b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 485b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen // The local cost of spill code in this block is the block frequency times 486b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen // the number of spill instructions inserted. 487b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen if (Inserts) 488b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen LocalCost += Inserts * SpillPlacer->getBlockFrequency(BI.MBB); 489b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen } 490b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen DEBUG(dbgs() << "Local cost of " << PrintReg(PhysReg, TRI) << " = " 491b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen << LocalCost << '\n'); 492b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen return LocalCost; 493b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen} 494b5fa9333431673aac2ced8dea80152349a85cf6fJakob 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 497b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen/// interference pattern in SpillConstraints. 498b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen/// 499b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesenfloat RAGreedy::calcGlobalSplitCost(const BitVector &LiveBundles) { 500b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen float GlobalCost = 0; 501f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen for (unsigned i = 0, e = SpillConstraints.size(); i != e; ++i) { 502b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen SpillPlacement::BlockConstraint &BC = SpillConstraints[i]; 503b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen unsigned Inserts = 0; 504b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen // Broken entry preference? 505b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen Inserts += LiveBundles[Bundles->getBundle(BC.Number, 0)] != 506b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen (BC.Entry == SpillPlacement::PrefReg); 507b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen // Broken exit preference? 508b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen Inserts += LiveBundles[Bundles->getBundle(BC.Number, 1)] != 509b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen (BC.Exit == SpillPlacement::PrefReg); 510b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen if (Inserts) 511f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen GlobalCost += 512f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen Inserts * SpillPlacer->getBlockFrequency(SA->LiveBlocks[i].MBB); 513b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen } 514b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen DEBUG(dbgs() << "Global cost = " << GlobalCost << '\n'); 515b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen return GlobalCost; 516b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen} 517b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 518ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen/// splitAroundRegion - Split VirtReg around the region determined by 519ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen/// LiveBundles. Make an effort to avoid interference from PhysReg. 520ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen/// 521ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen/// The 'register' interval is going to contain as many uses as possible while 522ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen/// avoiding interference. The 'stack' interval is the complement constructed by 523ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen/// SplitEditor. It will contain the rest. 524ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen/// 525ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesenvoid RAGreedy::splitAroundRegion(LiveInterval &VirtReg, unsigned PhysReg, 526ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen const BitVector &LiveBundles, 527ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen SmallVectorImpl<LiveInterval*> &NewVRegs) { 528ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen DEBUG({ 529ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen dbgs() << "Splitting around region for " << PrintReg(PhysReg, TRI) 530ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen << " with bundles"; 531ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen for (int i = LiveBundles.find_first(); i>=0; i = LiveBundles.find_next(i)) 532ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen dbgs() << " EB#" << i; 533ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen dbgs() << ".\n"; 534ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen }); 535ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 536ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // First compute interference ranges in the live blocks. 537ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen typedef std::pair<SlotIndex, SlotIndex> IndexPair; 538ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen SmallVector<IndexPair, 8> InterferenceRanges; 539f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen InterferenceRanges.resize(SA->LiveBlocks.size()); 540ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen for (const unsigned *AI = TRI->getOverlaps(PhysReg); *AI; ++AI) { 541ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen if (!query(VirtReg, *AI).checkInterference()) 542ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen continue; 543ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen LiveIntervalUnion::SegmentIter IntI = 544ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen PhysReg2LiveUnion[*AI].find(VirtReg.beginIndex()); 545ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen if (!IntI.valid()) 546ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen continue; 547f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen for (unsigned i = 0, e = SA->LiveBlocks.size(); i != e; ++i) { 548f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen const SplitAnalysis::BlockInfo &BI = SA->LiveBlocks[i]; 549ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen IndexPair &IP = InterferenceRanges[i]; 550ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen SlotIndex Start, Stop; 551ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen tie(Start, Stop) = Indexes->getMBBRange(BI.MBB); 552ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Skip interference-free blocks. 553ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen if (IntI.start() >= Stop) 554ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen continue; 555ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 556ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // First interference in block. 557ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen if (BI.LiveIn) { 558ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen IntI.advanceTo(Start); 559ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen if (!IntI.valid()) 560ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen break; 5612dfbb3e9125aa0a66feab7a7638815b57da85968Jakob Stoklund Olesen if (IntI.start() >= Stop) 5622dfbb3e9125aa0a66feab7a7638815b57da85968Jakob Stoklund Olesen continue; 563ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen if (!IP.first.isValid() || IntI.start() < IP.first) 564ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen IP.first = IntI.start(); 565ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen } 566ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 567ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Last interference in block. 568ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen if (BI.LiveOut) { 569ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen IntI.advanceTo(Stop); 570ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen if (!IntI.valid() || IntI.start() >= Stop) 571ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen --IntI; 5722dfbb3e9125aa0a66feab7a7638815b57da85968Jakob Stoklund Olesen if (IntI.stop() <= Start) 5732dfbb3e9125aa0a66feab7a7638815b57da85968Jakob Stoklund Olesen continue; 574ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen if (!IP.second.isValid() || IntI.stop() > IP.second) 575ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen IP.second = IntI.stop(); 576ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen } 577ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen } 578ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen } 579ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 580ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen SmallVector<LiveInterval*, 4> SpillRegs; 581ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen LiveRangeEdit LREdit(VirtReg, NewVRegs, SpillRegs); 582ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen SplitEditor SE(*SA, *LIS, *VRM, *DomTree, LREdit); 583ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 584ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Create the main cross-block interval. 585ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen SE.openIntv(); 586ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 587ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // First add all defs that are live out of a block. 588f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen for (unsigned i = 0, e = SA->LiveBlocks.size(); i != e; ++i) { 589f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen SplitAnalysis::BlockInfo &BI = SA->LiveBlocks[i]; 590ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen bool RegIn = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 0)]; 591ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen bool RegOut = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 1)]; 592ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 593ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Should the register be live out? 594ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen if (!BI.LiveOut || !RegOut) 595ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen continue; 596ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 597ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen IndexPair &IP = InterferenceRanges[i]; 598ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen SlotIndex Start, Stop; 599ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen tie(Start, Stop) = Indexes->getMBBRange(BI.MBB); 600ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 601ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " -> EB#" 6022dfbb3e9125aa0a66feab7a7638815b57da85968Jakob Stoklund Olesen << Bundles->getBundle(BI.MBB->getNumber(), 1) 6032dfbb3e9125aa0a66feab7a7638815b57da85968Jakob Stoklund Olesen << " intf [" << IP.first << ';' << IP.second << ')'); 6042dfbb3e9125aa0a66feab7a7638815b57da85968Jakob Stoklund Olesen 6052dfbb3e9125aa0a66feab7a7638815b57da85968Jakob Stoklund Olesen // The interference interval should either be invalid or overlap MBB. 6062dfbb3e9125aa0a66feab7a7638815b57da85968Jakob Stoklund Olesen assert((!IP.first.isValid() || IP.first < Stop) && "Bad interference"); 6072dfbb3e9125aa0a66feab7a7638815b57da85968Jakob Stoklund Olesen assert((!IP.second.isValid() || IP.second > Start) && "Bad interference"); 608ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 609ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Check interference leaving the block. 6102dfbb3e9125aa0a66feab7a7638815b57da85968Jakob Stoklund Olesen if (!IP.second.isValid()) { 611ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Block is interference-free. 612ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen DEBUG(dbgs() << ", no interference"); 613ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen if (!BI.Uses) { 614ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen assert(BI.LiveThrough && "No uses, but not live through block?"); 615ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Block is live-through without interference. 616ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen DEBUG(dbgs() << ", no uses" 617ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen << (RegIn ? ", live-through.\n" : ", stack in.\n")); 618ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen if (!RegIn) 619ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen SE.enterIntvAtEnd(*BI.MBB); 620ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen continue; 621ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen } 622ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen if (!BI.LiveThrough) { 623ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen DEBUG(dbgs() << ", not live-through.\n"); 624207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen SE.useIntv(SE.enterIntvBefore(BI.Def), Stop); 625ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen continue; 626ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen } 627ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen if (!RegIn) { 628ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Block is live-through, but entry bundle is on the stack. 629ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Reload just before the first use. 630ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen DEBUG(dbgs() << ", not live-in, enter before first use.\n"); 631207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen SE.useIntv(SE.enterIntvBefore(BI.FirstUse), Stop); 632ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen continue; 633ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen } 634ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen DEBUG(dbgs() << ", live-through.\n"); 635ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen continue; 636ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen } 637ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 638ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Block has interference. 639ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen DEBUG(dbgs() << ", interference to " << IP.second); 640fe3f99f95c7c9ceaac3ceebbea31e40cfbc157e3Jakob Stoklund Olesen 641fe3f99f95c7c9ceaac3ceebbea31e40cfbc157e3Jakob Stoklund Olesen if (!BI.LiveThrough && IP.second <= BI.Def) { 642fe3f99f95c7c9ceaac3ceebbea31e40cfbc157e3Jakob Stoklund Olesen // The interference doesn't reach the outgoing segment. 643fe3f99f95c7c9ceaac3ceebbea31e40cfbc157e3Jakob Stoklund Olesen DEBUG(dbgs() << " doesn't affect def from " << BI.Def << '\n'); 644fe3f99f95c7c9ceaac3ceebbea31e40cfbc157e3Jakob Stoklund Olesen SE.useIntv(BI.Def, Stop); 645fe3f99f95c7c9ceaac3ceebbea31e40cfbc157e3Jakob Stoklund Olesen continue; 646fe3f99f95c7c9ceaac3ceebbea31e40cfbc157e3Jakob Stoklund Olesen } 647fe3f99f95c7c9ceaac3ceebbea31e40cfbc157e3Jakob Stoklund Olesen 648fe3f99f95c7c9ceaac3ceebbea31e40cfbc157e3Jakob Stoklund Olesen 649ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen if (!BI.Uses) { 650ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // No uses in block, avoid interference by reloading as late as possible. 651ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen DEBUG(dbgs() << ", no uses.\n"); 652de71095a1a930eee81696d5770cdce46d3e19a61Jakob Stoklund Olesen SlotIndex SegStart = SE.enterIntvAtEnd(*BI.MBB); 653de71095a1a930eee81696d5770cdce46d3e19a61Jakob Stoklund Olesen assert(SegStart >= IP.second && "Couldn't avoid interference"); 654ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen continue; 655ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen } 656fe3f99f95c7c9ceaac3ceebbea31e40cfbc157e3Jakob Stoklund Olesen 6578a2bbdeee24b40da6187199658646d04329c139eJakob Stoklund Olesen if (IP.second.getBoundaryIndex() < BI.LastUse) { 658ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // There are interference-free uses at the end of the block. 659ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Find the first use that can get the live-out register. 660c0de99571297720a37ae405c77fb2ef4aaf00ccdJakob Stoklund Olesen SmallVectorImpl<SlotIndex>::const_iterator UI = 661fe3f99f95c7c9ceaac3ceebbea31e40cfbc157e3Jakob Stoklund Olesen std::lower_bound(SA->UseSlots.begin(), SA->UseSlots.end(), 662fe3f99f95c7c9ceaac3ceebbea31e40cfbc157e3Jakob Stoklund Olesen IP.second.getBoundaryIndex()); 663c0de99571297720a37ae405c77fb2ef4aaf00ccdJakob Stoklund Olesen assert(UI != SA->UseSlots.end() && "Couldn't find last use"); 664c0de99571297720a37ae405c77fb2ef4aaf00ccdJakob Stoklund Olesen SlotIndex Use = *UI; 665c0de99571297720a37ae405c77fb2ef4aaf00ccdJakob Stoklund Olesen assert(Use <= BI.LastUse && "Couldn't find last use"); 6668a2bbdeee24b40da6187199658646d04329c139eJakob Stoklund Olesen // Only attempt a split befroe the last split point. 6678a2bbdeee24b40da6187199658646d04329c139eJakob Stoklund Olesen if (Use.getBaseIndex() <= BI.LastSplitPoint) { 6688a2bbdeee24b40da6187199658646d04329c139eJakob Stoklund Olesen DEBUG(dbgs() << ", free use at " << Use << ".\n"); 6698a2bbdeee24b40da6187199658646d04329c139eJakob Stoklund Olesen SlotIndex SegStart = SE.enterIntvBefore(Use); 6708a2bbdeee24b40da6187199658646d04329c139eJakob Stoklund Olesen assert(SegStart >= IP.second && "Couldn't avoid interference"); 6718a2bbdeee24b40da6187199658646d04329c139eJakob Stoklund Olesen assert(SegStart < BI.LastSplitPoint && "Impossible split point"); 6728a2bbdeee24b40da6187199658646d04329c139eJakob Stoklund Olesen SE.useIntv(SegStart, Stop); 6738a2bbdeee24b40da6187199658646d04329c139eJakob Stoklund Olesen continue; 6748a2bbdeee24b40da6187199658646d04329c139eJakob Stoklund Olesen } 675ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen } 676ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 677ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Interference is after the last use. 678ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen DEBUG(dbgs() << " after last use.\n"); 679de71095a1a930eee81696d5770cdce46d3e19a61Jakob Stoklund Olesen SlotIndex SegStart = SE.enterIntvAtEnd(*BI.MBB); 680de71095a1a930eee81696d5770cdce46d3e19a61Jakob Stoklund Olesen assert(SegStart >= IP.second && "Couldn't avoid interference"); 681ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen } 682ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 683ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Now all defs leading to live bundles are handled, do everything else. 684f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen for (unsigned i = 0, e = SA->LiveBlocks.size(); i != e; ++i) { 685f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen SplitAnalysis::BlockInfo &BI = SA->LiveBlocks[i]; 686ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen bool RegIn = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 0)]; 687ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen bool RegOut = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 1)]; 688ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 689ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Is the register live-in? 690ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen if (!BI.LiveIn || !RegIn) 691ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen continue; 692ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 693ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // We have an incoming register. Check for interference. 694ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen IndexPair &IP = InterferenceRanges[i]; 695ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen SlotIndex Start, Stop; 696ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen tie(Start, Stop) = Indexes->getMBBRange(BI.MBB); 697ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 698ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen DEBUG(dbgs() << "EB#" << Bundles->getBundle(BI.MBB->getNumber(), 0) 699ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen << " -> BB#" << BI.MBB->getNumber()); 700ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 701ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Check interference entering the block. 7022dfbb3e9125aa0a66feab7a7638815b57da85968Jakob Stoklund Olesen if (!IP.first.isValid()) { 703ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Block is interference-free. 704ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen DEBUG(dbgs() << ", no interference"); 705ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen if (!BI.Uses) { 706ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen assert(BI.LiveThrough && "No uses, but not live through block?"); 707ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Block is live-through without interference. 708ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen if (RegOut) { 709ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen DEBUG(dbgs() << ", no uses, live-through.\n"); 710ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen SE.useIntv(Start, Stop); 711ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen } else { 712ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen DEBUG(dbgs() << ", no uses, stack-out.\n"); 713ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen SE.leaveIntvAtTop(*BI.MBB); 714ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen } 715ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen continue; 716ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen } 717ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen if (!BI.LiveThrough) { 718ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen DEBUG(dbgs() << ", killed in block.\n"); 719207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen SE.useIntv(Start, SE.leaveIntvAfter(BI.Kill)); 720ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen continue; 721ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen } 722ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen if (!RegOut) { 723ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Block is live-through, but exit bundle is on the stack. 724ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Spill immediately after the last use. 7255c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen if (BI.LastUse < BI.LastSplitPoint) { 7265c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen DEBUG(dbgs() << ", uses, stack-out.\n"); 7275c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen SE.useIntv(Start, SE.leaveIntvAfter(BI.LastUse)); 7285c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen continue; 7295c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen } 7305c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen // The last use is after the last split point, it is probably an 7315c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen // indirect jump. 7325c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen DEBUG(dbgs() << ", uses at " << BI.LastUse << " after split point " 7335c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen << BI.LastSplitPoint << ", stack-out.\n"); 73423cd57c29926189ad9d7b2b208024645870884adJakob Stoklund Olesen SlotIndex SegEnd = SE.leaveIntvBefore(BI.LastSplitPoint); 73523cd57c29926189ad9d7b2b208024645870884adJakob Stoklund Olesen SE.useIntv(Start, SegEnd); 7365c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen // Run a double interval from the split to the last use. 7375c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen // This makes it possible to spill the complement without affecting the 7385c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen // indirect branch. 7395c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen SE.overlapIntv(SegEnd, BI.LastUse); 740ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen continue; 741ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen } 742ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Register is live-through. 743ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen DEBUG(dbgs() << ", uses, live-through.\n"); 744ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen SE.useIntv(Start, Stop); 745ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen continue; 746ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen } 747ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 748ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Block has interference. 749ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen DEBUG(dbgs() << ", interference from " << IP.first); 750fe3f99f95c7c9ceaac3ceebbea31e40cfbc157e3Jakob Stoklund Olesen 751fe3f99f95c7c9ceaac3ceebbea31e40cfbc157e3Jakob Stoklund Olesen if (!BI.LiveThrough && IP.first >= BI.Kill) { 752fe3f99f95c7c9ceaac3ceebbea31e40cfbc157e3Jakob Stoklund Olesen // The interference doesn't reach the outgoing segment. 753fe3f99f95c7c9ceaac3ceebbea31e40cfbc157e3Jakob Stoklund Olesen DEBUG(dbgs() << " doesn't affect kill at " << BI.Kill << '\n'); 754fe3f99f95c7c9ceaac3ceebbea31e40cfbc157e3Jakob Stoklund Olesen SE.useIntv(Start, BI.Kill); 755fe3f99f95c7c9ceaac3ceebbea31e40cfbc157e3Jakob Stoklund Olesen continue; 756fe3f99f95c7c9ceaac3ceebbea31e40cfbc157e3Jakob Stoklund Olesen } 757fe3f99f95c7c9ceaac3ceebbea31e40cfbc157e3Jakob Stoklund Olesen 758ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen if (!BI.Uses) { 759ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // No uses in block, avoid interference by spilling as soon as possible. 760ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen DEBUG(dbgs() << ", no uses.\n"); 761de71095a1a930eee81696d5770cdce46d3e19a61Jakob Stoklund Olesen SlotIndex SegEnd = SE.leaveIntvAtTop(*BI.MBB); 762de71095a1a930eee81696d5770cdce46d3e19a61Jakob Stoklund Olesen assert(SegEnd <= IP.first && "Couldn't avoid interference"); 763ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen continue; 764ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen } 765fe3f99f95c7c9ceaac3ceebbea31e40cfbc157e3Jakob Stoklund Olesen if (IP.first.getBaseIndex() > BI.FirstUse) { 766ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // There are interference-free uses at the beginning of the block. 767ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Find the last use that can get the register. 768c0de99571297720a37ae405c77fb2ef4aaf00ccdJakob Stoklund Olesen SmallVectorImpl<SlotIndex>::const_iterator UI = 769fe3f99f95c7c9ceaac3ceebbea31e40cfbc157e3Jakob Stoklund Olesen std::lower_bound(SA->UseSlots.begin(), SA->UseSlots.end(), 770fe3f99f95c7c9ceaac3ceebbea31e40cfbc157e3Jakob Stoklund Olesen IP.first.getBaseIndex()); 771c0de99571297720a37ae405c77fb2ef4aaf00ccdJakob Stoklund Olesen assert(UI != SA->UseSlots.begin() && "Couldn't find first use"); 772c0de99571297720a37ae405c77fb2ef4aaf00ccdJakob Stoklund Olesen SlotIndex Use = (--UI)->getBoundaryIndex(); 773c0de99571297720a37ae405c77fb2ef4aaf00ccdJakob Stoklund Olesen DEBUG(dbgs() << ", free use at " << *UI << ".\n"); 774de71095a1a930eee81696d5770cdce46d3e19a61Jakob Stoklund Olesen SlotIndex SegEnd = SE.leaveIntvAfter(Use); 775de71095a1a930eee81696d5770cdce46d3e19a61Jakob Stoklund Olesen assert(SegEnd <= IP.first && "Couldn't avoid interference"); 776de71095a1a930eee81696d5770cdce46d3e19a61Jakob Stoklund Olesen SE.useIntv(Start, SegEnd); 777ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen continue; 778ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen } 779ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 780ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Interference is before the first use. 781ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen DEBUG(dbgs() << " before first use.\n"); 782de71095a1a930eee81696d5770cdce46d3e19a61Jakob Stoklund Olesen SlotIndex SegEnd = SE.leaveIntvAtTop(*BI.MBB); 783de71095a1a930eee81696d5770cdce46d3e19a61Jakob Stoklund Olesen assert(SegEnd <= IP.first && "Couldn't avoid interference"); 784ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen } 785ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 786ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen SE.closeIntv(); 787ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 788ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // FIXME: Should we be more aggressive about splitting the stack region into 789ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // per-block segments? The current approach allows the stack region to 790ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // separate into connected components. Some components may be allocatable. 791ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen SE.finish(); 7920db841f9c2b9a25fb5ecb36e350d3a802c35654cJakob Stoklund Olesen ++NumGlobalSplits; 793ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 7949b3d24bf3d4663bfaf98eb97a94081e07a3f62daJakob Stoklund Olesen if (VerifyEnabled) { 795ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen MF->verify(this, "After splitting live range around region"); 7969b3d24bf3d4663bfaf98eb97a94081e07a3f62daJakob Stoklund Olesen 7979b3d24bf3d4663bfaf98eb97a94081e07a3f62daJakob Stoklund Olesen#ifndef NDEBUG 7989b3d24bf3d4663bfaf98eb97a94081e07a3f62daJakob Stoklund Olesen // Make sure that at least one of the new intervals can allocate to PhysReg. 7999b3d24bf3d4663bfaf98eb97a94081e07a3f62daJakob Stoklund Olesen // That was the whole point of splitting the live range. 8009b3d24bf3d4663bfaf98eb97a94081e07a3f62daJakob Stoklund Olesen bool found = false; 8019b3d24bf3d4663bfaf98eb97a94081e07a3f62daJakob Stoklund Olesen for (LiveRangeEdit::iterator I = LREdit.begin(), E = LREdit.end(); I != E; 8029b3d24bf3d4663bfaf98eb97a94081e07a3f62daJakob Stoklund Olesen ++I) 8039b3d24bf3d4663bfaf98eb97a94081e07a3f62daJakob Stoklund Olesen if (!checkUncachedInterference(**I, PhysReg)) { 8049b3d24bf3d4663bfaf98eb97a94081e07a3f62daJakob Stoklund Olesen found = true; 8059b3d24bf3d4663bfaf98eb97a94081e07a3f62daJakob Stoklund Olesen break; 8069b3d24bf3d4663bfaf98eb97a94081e07a3f62daJakob Stoklund Olesen } 8079b3d24bf3d4663bfaf98eb97a94081e07a3f62daJakob Stoklund Olesen assert(found && "No allocatable intervals after pointless splitting"); 8089b3d24bf3d4663bfaf98eb97a94081e07a3f62daJakob Stoklund Olesen#endif 8099b3d24bf3d4663bfaf98eb97a94081e07a3f62daJakob Stoklund Olesen } 810ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen} 811ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 812b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesenunsigned RAGreedy::tryRegionSplit(LiveInterval &VirtReg, AllocationOrder &Order, 813b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen SmallVectorImpl<LiveInterval*> &NewVRegs) { 814b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen BitVector LiveBundles, BestBundles; 815b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen float BestCost = 0; 816b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen unsigned BestReg = 0; 817b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen Order.rewind(); 818b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen while (unsigned PhysReg = Order.next()) { 819b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen float Cost = calcInterferenceInfo(VirtReg, PhysReg); 820b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen if (BestReg && Cost >= BestCost) 821b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen continue; 822ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 823ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen SpillPlacer->placeSpills(SpillConstraints, LiveBundles); 824ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // No live bundles, defer to splitSingleBlocks(). 825ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen if (!LiveBundles.any()) 826ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen continue; 827ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 828ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen Cost += calcGlobalSplitCost(LiveBundles); 829b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen if (!BestReg || Cost < BestCost) { 830b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen BestReg = PhysReg; 831b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen BestCost = Cost; 832b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen BestBundles.swap(LiveBundles); 833b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen } 834b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen } 835ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 836ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen if (!BestReg) 837ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen return 0; 838ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 839ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen splitAroundRegion(VirtReg, BestReg, BestBundles, NewVRegs); 840b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen return 0; 841b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen} 842b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 843ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 844ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen//===----------------------------------------------------------------------===// 845034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen// Local Splitting 846034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 847034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 848034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 849034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// calcGapWeights - Compute the maximum spill weight that needs to be evicted 850034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// in order to use PhysReg between two entries in SA->UseSlots. 851034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// 852034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// GapWeight[i] represents the gap between UseSlots[i] and UseSlots[i+1]. 853034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// 854034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesenvoid RAGreedy::calcGapWeights(unsigned PhysReg, 855034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen SmallVectorImpl<float> &GapWeight) { 856034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen assert(SA->LiveBlocks.size() == 1 && "Not a local interval"); 857034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const SplitAnalysis::BlockInfo &BI = SA->LiveBlocks.front(); 858034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const SmallVectorImpl<SlotIndex> &Uses = SA->UseSlots; 859034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const unsigned NumGaps = Uses.size()-1; 860034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 861034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Start and end points for the interference check. 862034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen SlotIndex StartIdx = BI.LiveIn ? BI.FirstUse.getBaseIndex() : BI.FirstUse; 863034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen SlotIndex StopIdx = BI.LiveOut ? BI.LastUse.getBoundaryIndex() : BI.LastUse; 864034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 865034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen GapWeight.assign(NumGaps, 0.0f); 866034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 867034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Add interference from each overlapping register. 868034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen for (const unsigned *AI = TRI->getOverlaps(PhysReg); *AI; ++AI) { 869034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (!query(const_cast<LiveInterval&>(SA->getParent()), *AI) 870034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen .checkInterference()) 871034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen continue; 872034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 873034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // We know that VirtReg is a continuous interval from FirstUse to LastUse, 874034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // so we don't need InterferenceQuery. 875034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // 876034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Interference that overlaps an instruction is counted in both gaps 877034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // surrounding the instruction. The exception is interference before 878034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // StartIdx and after StopIdx. 879034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // 880034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen LiveIntervalUnion::SegmentIter IntI = PhysReg2LiveUnion[*AI].find(StartIdx); 881034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen for (unsigned Gap = 0; IntI.valid() && IntI.start() < StopIdx; ++IntI) { 882034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Skip the gaps before IntI. 883034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen while (Uses[Gap+1].getBoundaryIndex() < IntI.start()) 884034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (++Gap == NumGaps) 885034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen break; 886034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (Gap == NumGaps) 887034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen break; 888034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 889034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Update the gaps covered by IntI. 890034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const float weight = IntI.value()->weight; 891034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen for (; Gap != NumGaps; ++Gap) { 892034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen GapWeight[Gap] = std::max(GapWeight[Gap], weight); 893034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (Uses[Gap+1].getBaseIndex() >= IntI.stop()) 894034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen break; 895034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 896034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (Gap == NumGaps) 897034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen break; 898034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 899034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 900034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen} 901034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 902034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// getPrevMappedIndex - Return the slot index of the last non-copy instruction 903034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// before MI that has a slot index. If MI is the first mapped instruction in 904034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// its block, return the block start index instead. 905034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// 906034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund OlesenSlotIndex RAGreedy::getPrevMappedIndex(const MachineInstr *MI) { 907034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen assert(MI && "Missing MachineInstr"); 908034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const MachineBasicBlock *MBB = MI->getParent(); 909034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen MachineBasicBlock::const_iterator B = MBB->begin(), I = MI; 910034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen while (I != B) 911034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (!(--I)->isDebugValue() && !I->isCopy()) 912034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen return Indexes->getInstructionIndex(I); 913034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen return Indexes->getMBBStartIdx(MBB); 914034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen} 915034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 916034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// calcPrevSlots - Fill in the PrevSlot array with the index of the previous 917034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// real non-copy instruction for each instruction in SA->UseSlots. 918034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// 919034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesenvoid RAGreedy::calcPrevSlots() { 920034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const SmallVectorImpl<SlotIndex> &Uses = SA->UseSlots; 921034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen PrevSlot.clear(); 922034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen PrevSlot.reserve(Uses.size()); 923034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen for (unsigned i = 0, e = Uses.size(); i != e; ++i) { 924034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const MachineInstr *MI = Indexes->getInstructionFromIndex(Uses[i]); 925034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen PrevSlot.push_back(getPrevMappedIndex(MI).getDefIndex()); 926034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 927034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen} 928034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 929034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// nextSplitPoint - Find the next index into SA->UseSlots > i such that it may 930034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// be beneficial to split before UseSlots[i]. 931034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// 932034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// 0 is always a valid split point 933034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesenunsigned RAGreedy::nextSplitPoint(unsigned i) { 934034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const SmallVectorImpl<SlotIndex> &Uses = SA->UseSlots; 935034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const unsigned Size = Uses.size(); 936034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen assert(i != Size && "No split points after the end"); 937034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Allow split before i when Uses[i] is not adjacent to the previous use. 938034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen while (++i != Size && PrevSlot[i].getBaseIndex() <= Uses[i-1].getBaseIndex()) 939034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen ; 940034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen return i; 941034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen} 942034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 943034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// tryLocalSplit - Try to split VirtReg into smaller intervals inside its only 944034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// basic block. 945034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen/// 946034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesenunsigned RAGreedy::tryLocalSplit(LiveInterval &VirtReg, AllocationOrder &Order, 947034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen SmallVectorImpl<LiveInterval*> &NewVRegs) { 948034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen assert(SA->LiveBlocks.size() == 1 && "Not a local interval"); 949034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const SplitAnalysis::BlockInfo &BI = SA->LiveBlocks.front(); 950034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 951034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Note that it is possible to have an interval that is live-in or live-out 952034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // while only covering a single block - A phi-def can use undef values from 953034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // predecessors, and the block could be a single-block loop. 954034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // We don't bother doing anything clever about such a case, we simply assume 955034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // that the interval is continuous from FirstUse to LastUse. We should make 956034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // sure that we don't do anything illegal to such an interval, though. 957034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 958034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const SmallVectorImpl<SlotIndex> &Uses = SA->UseSlots; 959034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (Uses.size() <= 2) 960034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen return 0; 961034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const unsigned NumGaps = Uses.size()-1; 962034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 963034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen DEBUG({ 964034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen dbgs() << "tryLocalSplit: "; 965034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen for (unsigned i = 0, e = Uses.size(); i != e; ++i) 966034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen dbgs() << ' ' << SA->UseSlots[i]; 967034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen dbgs() << '\n'; 968034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen }); 969034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 970034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // For every use, find the previous mapped non-copy instruction. 971034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // We use this to detect valid split points, and to estimate new interval 972034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // sizes. 973034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen calcPrevSlots(); 974034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 975034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen unsigned BestBefore = NumGaps; 976034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen unsigned BestAfter = 0; 977034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen float BestDiff = 0; 978034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 979034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const float blockFreq = SpillPlacer->getBlockFrequency(BI.MBB); 980034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen SmallVector<float, 8> GapWeight; 981034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 982034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen Order.rewind(); 983034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen while (unsigned PhysReg = Order.next()) { 984034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Keep track of the largest spill weight that would need to be evicted in 985034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // order to make use of PhysReg between UseSlots[i] and UseSlots[i+1]. 986034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen calcGapWeights(PhysReg, GapWeight); 987034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 988034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Try to find the best sequence of gaps to close. 989034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // The new spill weight must be larger than any gap interference. 990034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 991034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // We will split before Uses[SplitBefore] and after Uses[SplitAfter]. 992034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen unsigned SplitBefore = 0, SplitAfter = nextSplitPoint(1) - 1; 993034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 994034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // MaxGap should always be max(GapWeight[SplitBefore..SplitAfter-1]). 995034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // It is the spill weight that needs to be evicted. 996034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen float MaxGap = GapWeight[0]; 997034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen for (unsigned i = 1; i != SplitAfter; ++i) 998034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen MaxGap = std::max(MaxGap, GapWeight[i]); 999034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1000034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen for (;;) { 1001034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Live before/after split? 1002034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const bool LiveBefore = SplitBefore != 0 || BI.LiveIn; 1003034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const bool LiveAfter = SplitAfter != NumGaps || BI.LiveOut; 1004034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1005034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen DEBUG(dbgs() << PrintReg(PhysReg, TRI) << ' ' 1006034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen << Uses[SplitBefore] << '-' << Uses[SplitAfter] 1007034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen << " i=" << MaxGap); 1008034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1009034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Stop before the interval gets so big we wouldn't be making progress. 1010034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (!LiveBefore && !LiveAfter) { 1011034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen DEBUG(dbgs() << " all\n"); 1012034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen break; 1013034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1014034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Should the interval be extended or shrunk? 1015034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen bool Shrink = true; 1016034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (MaxGap < HUGE_VALF) { 1017034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Estimate the new spill weight. 1018034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // 1019034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Each instruction reads and writes the register, except the first 1020034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // instr doesn't read when !FirstLive, and the last instr doesn't write 1021034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // when !LastLive. 1022034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // 1023034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // We will be inserting copies before and after, so the total number of 1024034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // reads and writes is 2 * EstUses. 1025034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // 1026034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const unsigned EstUses = 2*(SplitAfter - SplitBefore) + 1027034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 2*(LiveBefore + LiveAfter); 1028034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1029034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Try to guess the size of the new interval. This should be trivial, 1030034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // but the slot index of an inserted copy can be a lot smaller than the 1031034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // instruction it is inserted before if there are many dead indexes 1032034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // between them. 1033034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // 1034034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // We measure the distance from the instruction before SplitBefore to 1035034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // get a conservative estimate. 1036034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // 1037034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // The final distance can still be different if inserting copies 1038034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // triggers a slot index renumbering. 1039034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // 1040034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const float EstWeight = normalizeSpillWeight(blockFreq * EstUses, 1041034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen PrevSlot[SplitBefore].distance(Uses[SplitAfter])); 1042034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Would this split be possible to allocate? 1043034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Never allocate all gaps, we wouldn't be making progress. 1044034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen float Diff = EstWeight - MaxGap; 1045034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen DEBUG(dbgs() << " w=" << EstWeight << " d=" << Diff); 1046034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (Diff > 0) { 1047034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen Shrink = false; 1048034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (Diff > BestDiff) { 1049034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen DEBUG(dbgs() << " (best)"); 1050034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen BestDiff = Diff; 1051034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen BestBefore = SplitBefore; 1052034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen BestAfter = SplitAfter; 1053034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1054034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1055034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1056034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1057034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Try to shrink. 1058034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (Shrink) { 1059034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen SplitBefore = nextSplitPoint(SplitBefore); 1060034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (SplitBefore < SplitAfter) { 1061034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen DEBUG(dbgs() << " shrink\n"); 1062034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Recompute the max when necessary. 1063034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (GapWeight[SplitBefore - 1] >= MaxGap) { 1064034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen MaxGap = GapWeight[SplitBefore]; 1065034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen for (unsigned i = SplitBefore + 1; i != SplitAfter; ++i) 1066034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen MaxGap = std::max(MaxGap, GapWeight[i]); 1067034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1068034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen continue; 1069034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1070034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen MaxGap = 0; 1071034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1072034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1073034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Try to extend the interval. 1074034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (SplitAfter >= NumGaps) { 1075034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen DEBUG(dbgs() << " end\n"); 1076034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen break; 1077034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1078034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1079034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen DEBUG(dbgs() << " extend\n"); 1080034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen for (unsigned e = nextSplitPoint(SplitAfter + 1) - 1; 1081034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen SplitAfter != e; ++SplitAfter) 1082034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen MaxGap = std::max(MaxGap, GapWeight[SplitAfter]); 1083034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen continue; 1084034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1085034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen } 1086034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1087034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Didn't find any candidates? 1088034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen if (BestBefore == NumGaps) 1089034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen return 0; 1090034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1091034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen DEBUG(dbgs() << "Best local split range: " << Uses[BestBefore] 1092034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen << '-' << Uses[BestAfter] << ", " << BestDiff 1093034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen << ", " << (BestAfter - BestBefore + 1) << " instrs\n"); 1094034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1095034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen SmallVector<LiveInterval*, 4> SpillRegs; 1096034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen LiveRangeEdit LREdit(VirtReg, NewVRegs, SpillRegs); 1097034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen SplitEditor SE(*SA, *LIS, *VRM, *DomTree, LREdit); 1098034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1099034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen SE.openIntv(); 1100034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen SlotIndex SegStart = SE.enterIntvBefore(Uses[BestBefore]); 1101034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen SlotIndex SegStop = SE.leaveIntvAfter(Uses[BestAfter]); 1102034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen SE.useIntv(SegStart, SegStop); 1103034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen SE.closeIntv(); 1104034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen SE.finish(); 11050db841f9c2b9a25fb5ecb36e350d3a802c35654cJakob Stoklund Olesen ++NumLocalSplits; 1106034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1107034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen return 0; 1108034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen} 1109034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1110034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 1111ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen// Live Range Splitting 1112ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen//===----------------------------------------------------------------------===// 1113ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 1114ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen/// trySplit - Try to split VirtReg or one of its interferences, making it 1115ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen/// assignable. 1116ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen/// @return Physreg when VirtReg may be assigned and/or new NewVRegs. 1117ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesenunsigned RAGreedy::trySplit(LiveInterval &VirtReg, AllocationOrder &Order, 1118ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen SmallVectorImpl<LiveInterval*>&NewVRegs) { 1119ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen NamedRegionTimer T("Splitter", TimerGroupName, TimePassesIsEnabled); 1120ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen SA->analyze(&VirtReg); 1121ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 1122034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen // Local intervals are handled separately. 1123ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen if (LIS->intervalIsInOneMBB(VirtReg)) 1124034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen return tryLocalSplit(VirtReg, Order, NewVRegs); 1125ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 1126ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // First try to split around a region spanning multiple blocks. 1127ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen unsigned PhysReg = tryRegionSplit(VirtReg, Order, NewVRegs); 1128ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen if (PhysReg || !NewVRegs.empty()) 1129ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen return PhysReg; 1130ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 1131ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Then isolate blocks with multiple uses. 1132ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen SplitAnalysis::BlockPtrSet Blocks; 1133ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen if (SA->getMultiUseBlocks(Blocks)) { 1134ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen SmallVector<LiveInterval*, 4> SpillRegs; 1135ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen LiveRangeEdit LREdit(VirtReg, NewVRegs, SpillRegs); 1136ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen SplitEditor(*SA, *LIS, *VRM, *DomTree, LREdit).splitSingleBlocks(Blocks); 1137207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen if (VerifyEnabled) 1138207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen MF->verify(this, "After splitting live range around basic blocks"); 1139ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen } 1140ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 1141ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen // Don't assign any physregs. 1142ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen return 0; 1143ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen} 1144ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 1145ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 1146b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen//===----------------------------------------------------------------------===// 1147770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen// Spilling 1148770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen//===----------------------------------------------------------------------===// 1149770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen 1150770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen/// calcInterferenceWeight - Calculate the combined spill weight of 1151770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen/// interferences when assigning VirtReg to PhysReg. 1152770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesenfloat RAGreedy::calcInterferenceWeight(LiveInterval &VirtReg, unsigned PhysReg){ 1153770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen float Sum = 0; 1154770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen for (const unsigned *AI = TRI->getOverlaps(PhysReg); *AI; ++AI) { 1155770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen LiveIntervalUnion::Query &Q = query(VirtReg, *AI); 1156770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen Q.collectInterferingVRegs(); 1157770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen if (Q.seenUnspillableVReg()) 1158770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen return HUGE_VALF; 1159770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen for (unsigned i = 0, e = Q.interferingVRegs().size(); i != e; ++i) 1160770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen Sum += Q.interferingVRegs()[i]->weight; 1161770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen } 1162770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen return Sum; 1163770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen} 1164770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen 1165770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen/// trySpillInterferences - Try to spill interfering registers instead of the 1166770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen/// current one. Only do it if the accumulated spill weight is smaller than the 1167770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen/// current spill weight. 1168770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesenunsigned RAGreedy::trySpillInterferences(LiveInterval &VirtReg, 1169770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen AllocationOrder &Order, 1170770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen SmallVectorImpl<LiveInterval*> &NewVRegs) { 1171770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen NamedRegionTimer T("Spill Interference", TimerGroupName, TimePassesIsEnabled); 1172770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen unsigned BestPhys = 0; 11732aea490e163b53e966d693285c17c1a934db5e8dDuncan Sands float BestWeight = 0; 1174770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen 1175770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen Order.rewind(); 1176770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen while (unsigned PhysReg = Order.next()) { 1177770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen float Weight = calcInterferenceWeight(VirtReg, PhysReg); 1178770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen if (Weight == HUGE_VALF || Weight >= VirtReg.weight) 1179770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen continue; 1180770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen if (!BestPhys || Weight < BestWeight) 1181770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen BestPhys = PhysReg, BestWeight = Weight; 1182770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen } 1183770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen 1184770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen // No candidates found. 1185770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen if (!BestPhys) 1186770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen return 0; 1187770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen 1188770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen // Collect all interfering registers. 1189770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen SmallVector<LiveInterval*, 8> Spills; 1190770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen for (const unsigned *AI = TRI->getOverlaps(BestPhys); *AI; ++AI) { 1191770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen LiveIntervalUnion::Query &Q = query(VirtReg, *AI); 1192770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen Spills.append(Q.interferingVRegs().begin(), Q.interferingVRegs().end()); 1193770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen for (unsigned i = 0, e = Q.interferingVRegs().size(); i != e; ++i) { 1194770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen LiveInterval *VReg = Q.interferingVRegs()[i]; 11952710638db2eb84cd7eefb8bb9a1b7e5c49413d45Jakob Stoklund Olesen unassign(*VReg, *AI); 1196770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen } 1197770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen } 1198770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen 1199770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen // Spill them all. 1200770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen DEBUG(dbgs() << "spilling " << Spills.size() << " interferences with weight " 1201770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen << BestWeight << '\n'); 1202770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen for (unsigned i = 0, e = Spills.size(); i != e; ++i) 1203770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen spiller().spill(Spills[i], NewVRegs, Spills); 1204770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen return BestPhys; 1205770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen} 1206770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen 1207770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen 1208770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen//===----------------------------------------------------------------------===// 1209770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen// Main Entry Point 1210770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen//===----------------------------------------------------------------------===// 1211770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen 1212770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesenunsigned RAGreedy::selectOrSplit(LiveInterval &VirtReg, 1213ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen SmallVectorImpl<LiveInterval*> &NewVRegs) { 1214770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen // First try assigning a free register. 1215dd479e9769eceee9fcc34e2173376024f3aa3c5fJakob Stoklund Olesen AllocationOrder Order(VirtReg.reg, *VRM, ReservedRegs); 1216dd479e9769eceee9fcc34e2173376024f3aa3c5fJakob Stoklund Olesen while (unsigned PhysReg = Order.next()) { 1217770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen if (!checkPhysRegInterference(VirtReg, PhysReg)) 1218cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen return PhysReg; 1219cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen } 1220b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick 122146c83c80c5737743c955ff007fa6409804a7abf0Jakob Stoklund Olesen // Try to reassign interferences. 12222710638db2eb84cd7eefb8bb9a1b7e5c49413d45Jakob Stoklund Olesen if (unsigned PhysReg = tryReassignOrEvict(VirtReg, Order, NewVRegs)) 122346c83c80c5737743c955ff007fa6409804a7abf0Jakob Stoklund Olesen return PhysReg; 1224b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick 1225ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen assert(NewVRegs.empty() && "Cannot append to existing NewVRegs"); 1226ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen 122746c83c80c5737743c955ff007fa6409804a7abf0Jakob Stoklund Olesen // Try splitting VirtReg or interferences. 1228ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen unsigned PhysReg = trySplit(VirtReg, Order, NewVRegs); 1229ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen if (PhysReg || !NewVRegs.empty()) 1230b64d92e29f38002e52a22fe36ea2d488968e3537Jakob Stoklund Olesen return PhysReg; 1231b64d92e29f38002e52a22fe36ea2d488968e3537Jakob Stoklund Olesen 1232cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen // Try to spill another interfering reg with less spill weight. 1233ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen PhysReg = trySpillInterferences(VirtReg, Order, NewVRegs); 1234770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen if (PhysReg) 1235770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen return PhysReg; 1236b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick 1237770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen // Finally spill VirtReg itself. 1238770d42de3b7643b2b4f835f32e3a16275b9fbdbaJakob Stoklund Olesen NamedRegionTimer T("Spiller", TimerGroupName, TimePassesIsEnabled); 1239cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen SmallVector<LiveInterval*, 1> pendingSpills; 1240ccdb3fcef9aeb9f683cd738afbe1cd961bb0c1efJakob Stoklund Olesen spiller().spill(&VirtReg, NewVRegs, pendingSpills); 1241cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 1242cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen // The live virtual register requesting allocation was spilled, so tell 1243cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen // the caller not to allocate anything during this round. 1244cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen return 0; 1245cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen} 1246cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 1247cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesenbool RAGreedy::runOnMachineFunction(MachineFunction &mf) { 1248cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen DEBUG(dbgs() << "********** GREEDY REGISTER ALLOCATION **********\n" 1249cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen << "********** Function: " 1250cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen << ((Value*)mf.getFunction())->getName() << '\n'); 1251cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 1252cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen MF = &mf; 1253af24964251e27c2dd863239ba66ffd967b593be5Jakob Stoklund Olesen if (VerifyEnabled) 125489cab93fe999f6d81b4b99a71ac797b7ecfec277Jakob Stoklund Olesen MF->verify(this, "Before greedy register allocator"); 1255af24964251e27c2dd863239ba66ffd967b593be5Jakob Stoklund Olesen 12564680dec5fb3a1b624f13ca9b2a555ca90a07973eJakob Stoklund Olesen RegAllocBase::init(getAnalysis<VirtRegMap>(), getAnalysis<LiveIntervals>()); 1257b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen Indexes = &getAnalysis<SlotIndexes>(); 1258f428eb6c1b09a2322b7a577b0bf2e49dd107bceaJakob Stoklund Olesen DomTree = &getAnalysis<MachineDominatorTree>(); 1259cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen ReservedRegs = TRI->getReservedRegs(*MF); 1260f6dff84d4e44d6c4a46c4f8a18e13c78f804547cJakob Stoklund Olesen SpillerInstance.reset(createInlineSpiller(*this, *MF, *VRM)); 1261d0bb5e2ca05d9c942223bf05e5940bb0c6cc9d3fJakob Stoklund Olesen Loops = &getAnalysis<MachineLoopInfo>(); 1262d0bb5e2ca05d9c942223bf05e5940bb0c6cc9d3fJakob Stoklund Olesen LoopRanges = &getAnalysis<MachineLoopRanges>(); 1263b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen Bundles = &getAnalysis<EdgeBundles>(); 1264b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen SpillPlacer = &getAnalysis<SpillPlacement>(); 1265b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 1266d0bb5e2ca05d9c942223bf05e5940bb0c6cc9d3fJakob Stoklund Olesen SA.reset(new SplitAnalysis(*MF, *LIS, *Loops)); 1267d0bb5e2ca05d9c942223bf05e5940bb0c6cc9d3fJakob Stoklund Olesen 1268cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen allocatePhysRegs(); 1269cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen addMBBLiveIns(MF); 12708a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen LIS->addKillFlags(); 1271cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 1272cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen // Run rewriter 1273533f58ecdd8a4732c2f0e149387c4d8d8d4142deJakob Stoklund Olesen { 1274533f58ecdd8a4732c2f0e149387c4d8d8d4142deJakob Stoklund Olesen NamedRegionTimer T("Rewriter", TimerGroupName, TimePassesIsEnabled); 1275ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen VRM->rewrite(Indexes); 1276533f58ecdd8a4732c2f0e149387c4d8d8d4142deJakob Stoklund Olesen } 1277cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 1278cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen // The pass output is in VirtRegMap. Release all the transient data. 1279cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen releaseMemory(); 1280cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 1281cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen return true; 1282cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen} 1283