RegAllocGreedy.cpp revision 6ce219ec64088fc4ee550afbb6cd30621fbba27e
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" 16cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "LiveIntervalUnion.h" 17cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "RegAllocBase.h" 18cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "Spiller.h" 19cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "VirtRegMap.h" 20cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "VirtRegRewriter.h" 21cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "llvm/Analysis/AliasAnalysis.h" 22cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "llvm/Function.h" 23cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "llvm/PassAnalysisSupport.h" 24cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "llvm/CodeGen/CalcSpillWeights.h" 25cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "llvm/CodeGen/LiveIntervalAnalysis.h" 26cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "llvm/CodeGen/LiveStackAnalysis.h" 27cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "llvm/CodeGen/MachineFunctionPass.h" 28cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "llvm/CodeGen/MachineLoopInfo.h" 29cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "llvm/CodeGen/MachineRegisterInfo.h" 30cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "llvm/CodeGen/Passes.h" 31cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "llvm/CodeGen/RegAllocRegistry.h" 32cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "llvm/CodeGen/RegisterCoalescer.h" 33cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "llvm/Target/TargetOptions.h" 34cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "llvm/Support/Debug.h" 35cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "llvm/Support/ErrorHandling.h" 36cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen#include "llvm/Support/raw_ostream.h" 37cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 38cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesenusing namespace llvm; 39cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 40cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesenstatic RegisterRegAlloc greedyRegAlloc("greedy", "greedy register allocator", 41cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen createGreedyRegisterAllocator); 42cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 43cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesennamespace { 44cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesenclass RAGreedy : public MachineFunctionPass, public RegAllocBase { 45cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen // context 46cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen MachineFunction *MF; 47cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen const TargetMachine *TM; 48cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen MachineRegisterInfo *MRI; 49cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 50cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen BitVector ReservedRegs; 51cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 52cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen // analyses 53cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen LiveStacks *LS; 54cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 55cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen // state 56cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen std::auto_ptr<Spiller> SpillerInstance; 57cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 58cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesenpublic: 59cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen RAGreedy(); 60cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 61cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen /// Return the pass name. 62cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen virtual const char* getPassName() const { 63cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen return "Basic Register Allocator"; 64cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen } 65cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 66cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen /// RAGreedy analysis usage. 67cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen virtual void getAnalysisUsage(AnalysisUsage &AU) const; 68cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 69cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen virtual void releaseMemory(); 70cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 71cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen virtual Spiller &spiller() { return *SpillerInstance; } 72cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 7390c1d7ddfc65654f7efe72d56cad65d1af9e6b2aJakob Stoklund Olesen virtual float getPriority(LiveInterval *LI); 74d0bec3e62c98b1f0ef3a41db8f95599b2014c131Jakob Stoklund Olesen 75cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen virtual unsigned selectOrSplit(LiveInterval &VirtReg, 76cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen SmallVectorImpl<LiveInterval*> &SplitVRegs); 77cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 78cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen /// Perform register allocation. 79cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen virtual bool runOnMachineFunction(MachineFunction &mf); 80cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 81cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen static char ID; 82b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick 83b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trickprivate: 846ce219ec64088fc4ee550afbb6cd30621fbba27eJakob Stoklund Olesen bool checkUncachedInterference(LiveInterval &, unsigned); 85b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick bool reassignVReg(LiveInterval &InterferingVReg, unsigned OldPhysReg); 86b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick bool reassignInterferences(LiveInterval &VirtReg, unsigned PhysReg); 87cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen}; 88cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen} // end anonymous namespace 89cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 90cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesenchar RAGreedy::ID = 0; 91cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 92cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund OlesenFunctionPass* llvm::createGreedyRegisterAllocator() { 93cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen return new RAGreedy(); 94cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen} 95cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 96cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund OlesenRAGreedy::RAGreedy(): MachineFunctionPass(ID) { 97cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen initializeLiveIntervalsPass(*PassRegistry::getPassRegistry()); 98cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen initializeSlotIndexesPass(*PassRegistry::getPassRegistry()); 99cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen initializeStrongPHIEliminationPass(*PassRegistry::getPassRegistry()); 100cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen initializeRegisterCoalescerAnalysisGroup(*PassRegistry::getPassRegistry()); 101cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen initializeCalculateSpillWeightsPass(*PassRegistry::getPassRegistry()); 102cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen initializeLiveStacksPass(*PassRegistry::getPassRegistry()); 103cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry()); 104cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen initializeMachineLoopInfoPass(*PassRegistry::getPassRegistry()); 105cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen initializeVirtRegMapPass(*PassRegistry::getPassRegistry()); 106cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen} 107cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 108cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesenvoid RAGreedy::getAnalysisUsage(AnalysisUsage &AU) const { 109cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.setPreservesCFG(); 110cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addRequired<AliasAnalysis>(); 111cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addPreserved<AliasAnalysis>(); 112cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addRequired<LiveIntervals>(); 113cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addPreserved<SlotIndexes>(); 114cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen if (StrongPHIElim) 115cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addRequiredID(StrongPHIEliminationID); 116cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addRequiredTransitive<RegisterCoalescer>(); 117cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addRequired<CalculateSpillWeights>(); 118cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addRequired<LiveStacks>(); 119cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addPreserved<LiveStacks>(); 120cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addRequiredID(MachineDominatorsID); 121cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addPreservedID(MachineDominatorsID); 122cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addRequired<MachineLoopInfo>(); 123cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addPreserved<MachineLoopInfo>(); 124cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addRequired<VirtRegMap>(); 125cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen AU.addPreserved<VirtRegMap>(); 126cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen MachineFunctionPass::getAnalysisUsage(AU); 127cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen} 128cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 129cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesenvoid RAGreedy::releaseMemory() { 130cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen SpillerInstance.reset(0); 131cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen RegAllocBase::releaseMemory(); 132cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen} 133cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 13490c1d7ddfc65654f7efe72d56cad65d1af9e6b2aJakob Stoklund Olesenfloat RAGreedy::getPriority(LiveInterval *LI) { 13590c1d7ddfc65654f7efe72d56cad65d1af9e6b2aJakob Stoklund Olesen float Priority = LI->weight; 13690c1d7ddfc65654f7efe72d56cad65d1af9e6b2aJakob Stoklund Olesen 13790c1d7ddfc65654f7efe72d56cad65d1af9e6b2aJakob Stoklund Olesen // Prioritize hinted registers so they are allocated first. 13890c1d7ddfc65654f7efe72d56cad65d1af9e6b2aJakob Stoklund Olesen std::pair<unsigned, unsigned> Hint; 13990c1d7ddfc65654f7efe72d56cad65d1af9e6b2aJakob Stoklund Olesen if (Hint.first || Hint.second) { 14090c1d7ddfc65654f7efe72d56cad65d1af9e6b2aJakob Stoklund Olesen // The hint can be target specific, a virtual register, or a physreg. 14190c1d7ddfc65654f7efe72d56cad65d1af9e6b2aJakob Stoklund Olesen Priority *= 2; 14290c1d7ddfc65654f7efe72d56cad65d1af9e6b2aJakob Stoklund Olesen 14390c1d7ddfc65654f7efe72d56cad65d1af9e6b2aJakob Stoklund Olesen // Prefer physreg hints above anything else. 14490c1d7ddfc65654f7efe72d56cad65d1af9e6b2aJakob Stoklund Olesen if (Hint.first == 0 && TargetRegisterInfo::isPhysicalRegister(Hint.second)) 14590c1d7ddfc65654f7efe72d56cad65d1af9e6b2aJakob Stoklund Olesen Priority *= 2; 14690c1d7ddfc65654f7efe72d56cad65d1af9e6b2aJakob Stoklund Olesen } 14790c1d7ddfc65654f7efe72d56cad65d1af9e6b2aJakob Stoklund Olesen return Priority; 14890c1d7ddfc65654f7efe72d56cad65d1af9e6b2aJakob Stoklund Olesen} 14990c1d7ddfc65654f7efe72d56cad65d1af9e6b2aJakob Stoklund Olesen 1506ce219ec64088fc4ee550afbb6cd30621fbba27eJakob Stoklund Olesen// Check interference without using the cache. 1516ce219ec64088fc4ee550afbb6cd30621fbba27eJakob Stoklund Olesenbool RAGreedy::checkUncachedInterference(LiveInterval &VirtReg, 1526ce219ec64088fc4ee550afbb6cd30621fbba27eJakob Stoklund Olesen unsigned PhysReg) { 1536ce219ec64088fc4ee550afbb6cd30621fbba27eJakob Stoklund Olesen LiveIntervalUnion::Query subQ(&VirtReg, &PhysReg2LiveUnion[PhysReg]); 1546ce219ec64088fc4ee550afbb6cd30621fbba27eJakob Stoklund Olesen if (subQ.checkInterference()) 1556ce219ec64088fc4ee550afbb6cd30621fbba27eJakob Stoklund Olesen return true; 1566ce219ec64088fc4ee550afbb6cd30621fbba27eJakob Stoklund Olesen for (const unsigned *AliasI = TRI->getAliasSet(PhysReg); *AliasI; ++AliasI) { 1576ce219ec64088fc4ee550afbb6cd30621fbba27eJakob Stoklund Olesen subQ.init(&VirtReg, &PhysReg2LiveUnion[*AliasI]); 1586ce219ec64088fc4ee550afbb6cd30621fbba27eJakob Stoklund Olesen if (subQ.checkInterference()) 1596ce219ec64088fc4ee550afbb6cd30621fbba27eJakob Stoklund Olesen return true; 1606ce219ec64088fc4ee550afbb6cd30621fbba27eJakob Stoklund Olesen } 1616ce219ec64088fc4ee550afbb6cd30621fbba27eJakob Stoklund Olesen return false; 1626ce219ec64088fc4ee550afbb6cd30621fbba27eJakob Stoklund Olesen} 1636ce219ec64088fc4ee550afbb6cd30621fbba27eJakob Stoklund Olesen 164b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick// Attempt to reassign this virtual register to a different physical register. 165b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick// 166b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick// FIXME: we are not yet caching these "second-level" interferences discovered 167b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick// in the sub-queries. These interferences can change with each call to 168b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick// selectOrSplit. However, we could implement a "may-interfere" cache that 169b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick// could be conservatively dirtied when we reassign or split. 170b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick// 171b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick// FIXME: This may result in a lot of alias queries. We could summarize alias 172b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick// live intervals in their parent register's live union, but it's messy. 173b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trickbool RAGreedy::reassignVReg(LiveInterval &InterferingVReg, 174b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick unsigned OldPhysReg) { 175b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick assert(OldPhysReg == VRM->getPhys(InterferingVReg.reg) && 176b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick "inconsistent phys reg assigment"); 177b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick 178b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick const TargetRegisterClass *TRC = MRI->getRegClass(InterferingVReg.reg); 179b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick for (TargetRegisterClass::iterator I = TRC->allocation_order_begin(*MF), 180b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick E = TRC->allocation_order_end(*MF); 181b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick I != E; ++I) { 182b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick unsigned PhysReg = *I; 183ff092faffb85410b0013fb70bc991bb98b5663a5Jakob Stoklund Olesen if (PhysReg == OldPhysReg || ReservedRegs.test(PhysReg)) 184b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick continue; 185b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick 1866ce219ec64088fc4ee550afbb6cd30621fbba27eJakob Stoklund Olesen if (checkUncachedInterference(InterferingVReg, PhysReg)) 187b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick continue; 188b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick 189b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick DEBUG(dbgs() << "reassigning: " << InterferingVReg << " from " << 190b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick TRI->getName(OldPhysReg) << " to " << TRI->getName(PhysReg) << '\n'); 191b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick 192b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick // Reassign the interfering virtual reg to this physical reg. 193b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick PhysReg2LiveUnion[OldPhysReg].extract(InterferingVReg); 194b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick VRM->clearVirt(InterferingVReg.reg); 195b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick VRM->assignVirt2Phys(InterferingVReg.reg, PhysReg); 196b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick PhysReg2LiveUnion[PhysReg].unify(InterferingVReg); 197b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick 198b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick return true; 199b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick } 200b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick return false; 201b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick} 202b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick 203b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick// Collect all virtual regs currently assigned to PhysReg that interfere with 204b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick// VirtReg. 205b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick// 206b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick// Currently, for simplicity, we only attempt to reassign a single interference 207b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick// within the same register class. 208b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trickbool RAGreedy::reassignInterferences(LiveInterval &VirtReg, unsigned PhysReg) { 209b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick LiveIntervalUnion::Query &Q = query(VirtReg, PhysReg); 210b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick 211b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick // Limit the interference search to one interference. 212b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick Q.collectInterferingVRegs(1); 213b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick assert(Q.interferingVRegs().size() == 1 && 214b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick "expected at least one interference"); 215b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick 216b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick // Do not attempt reassignment unless we find only a single interference. 217b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick if (!Q.seenAllInterferences()) 218b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick return false; 219b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick 220b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick // Don't allow any interferences on aliases. 221b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick for (const unsigned *AliasI = TRI->getAliasSet(PhysReg); *AliasI; ++AliasI) { 222b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick if (query(VirtReg, *AliasI).checkInterference()) 223b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick return false; 224b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick } 225b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick 226b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick return reassignVReg(*Q.interferingVRegs()[0], PhysReg); 227b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick} 228b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick 229cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesenunsigned RAGreedy::selectOrSplit(LiveInterval &VirtReg, 230cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen SmallVectorImpl<LiveInterval*> &SplitVRegs) { 231cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen // Populate a list of physical register spill candidates. 232b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick SmallVector<unsigned, 8> PhysRegSpillCands, ReassignCands; 233cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 234cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen // Check for an available register in this class. 235cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen const TargetRegisterClass *TRC = MRI->getRegClass(VirtReg.reg); 236cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen DEBUG(dbgs() << "RegClass: " << TRC->getName() << ' '); 237cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 23890c1d7ddfc65654f7efe72d56cad65d1af9e6b2aJakob Stoklund Olesen // Preferred physical register computed from hints. 23990c1d7ddfc65654f7efe72d56cad65d1af9e6b2aJakob Stoklund Olesen unsigned Hint = VRM->getRegAllocPref(VirtReg.reg); 24090c1d7ddfc65654f7efe72d56cad65d1af9e6b2aJakob Stoklund Olesen 24190c1d7ddfc65654f7efe72d56cad65d1af9e6b2aJakob Stoklund Olesen // Try a hinted allocation. 24290c1d7ddfc65654f7efe72d56cad65d1af9e6b2aJakob Stoklund Olesen if (Hint && !ReservedRegs.test(Hint) && TRC->contains(Hint) && 24390c1d7ddfc65654f7efe72d56cad65d1af9e6b2aJakob Stoklund Olesen checkPhysRegInterference(VirtReg, Hint) == 0) 24490c1d7ddfc65654f7efe72d56cad65d1af9e6b2aJakob Stoklund Olesen return Hint; 24590c1d7ddfc65654f7efe72d56cad65d1af9e6b2aJakob Stoklund Olesen 246cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen for (TargetRegisterClass::iterator I = TRC->allocation_order_begin(*MF), 247cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen E = TRC->allocation_order_end(*MF); 248cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen I != E; ++I) { 249cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 250cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen unsigned PhysReg = *I; 251cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen if (ReservedRegs.test(PhysReg)) continue; 252cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 253cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen // Check interference and as a side effect, intialize queries for this 254cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen // VirtReg and its aliases. 255b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick unsigned InterfReg = checkPhysRegInterference(VirtReg, PhysReg); 256b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick if (InterfReg == 0) { 257cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen // Found an available register. 258cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen return PhysReg; 259cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen } 2609b0c4f8af3e303c85ddb5ff0ee2c8e27a4d77203Jakob Stoklund Olesen assert(!VirtReg.empty() && "Empty VirtReg has interference"); 261b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick LiveInterval *InterferingVirtReg = 262b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick Queries[InterfReg].firstInterference().liveUnionPos().value(); 263cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 264b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick // The current VirtReg must either be spillable, or one of its interferences 265cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen // must have less spill weight. 266b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick if (InterferingVirtReg->weight < VirtReg.weight ) { 267b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick // For simplicity, only consider reassigning registers in the same class. 268b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick if (InterfReg == PhysReg) 269b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick ReassignCands.push_back(PhysReg); 270b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick else 271b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick PhysRegSpillCands.push_back(PhysReg); 272cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen } 273cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen } 274b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick 275b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick // Try to reassign interfering physical register. Priority among 276b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick // PhysRegSpillCands does not matter yet, because the reassigned virtual 277b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick // registers will still be assigned to physical registers. 278b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick for (SmallVectorImpl<unsigned>::iterator PhysRegI = ReassignCands.begin(), 279b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick PhysRegE = ReassignCands.end(); PhysRegI != PhysRegE; ++PhysRegI) { 280b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick if (reassignInterferences(VirtReg, *PhysRegI)) 281b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick // Reassignment successfull. The caller may allocate now to this PhysReg. 282b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick return *PhysRegI; 283b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick } 284b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick 285b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick PhysRegSpillCands.insert(PhysRegSpillCands.end(), ReassignCands.begin(), 286b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick ReassignCands.end()); 287b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick 288cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen // Try to spill another interfering reg with less spill weight. 289cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen // 290b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick // FIXME: do this in two steps: (1) check for unspillable interferences while 291b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick // accumulating spill weight; (2) spill the interferences with lowest 292b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick // aggregate spill weight. 293cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen for (SmallVectorImpl<unsigned>::iterator PhysRegI = PhysRegSpillCands.begin(), 294cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen PhysRegE = PhysRegSpillCands.end(); PhysRegI != PhysRegE; ++PhysRegI) { 295cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 296cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen if (!spillInterferences(VirtReg, *PhysRegI, SplitVRegs)) continue; 297cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 298cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen assert(checkPhysRegInterference(VirtReg, *PhysRegI) == 0 && 299cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen "Interference after spill."); 300cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen // Tell the caller to allocate to this newly freed physical register. 301cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen return *PhysRegI; 302cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen } 303b853e6c3702149cdbbd6fa404334e3ba0055641aAndrew Trick 304cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen // No other spill candidates were found, so spill the current VirtReg. 305cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen DEBUG(dbgs() << "spilling: " << VirtReg << '\n'); 306cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen SmallVector<LiveInterval*, 1> pendingSpills; 307cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 308cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen spiller().spill(&VirtReg, SplitVRegs, pendingSpills); 309cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 310cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen // The live virtual register requesting allocation was spilled, so tell 311cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen // the caller not to allocate anything during this round. 312cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen return 0; 313cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen} 314cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 315cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesenbool RAGreedy::runOnMachineFunction(MachineFunction &mf) { 316cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen DEBUG(dbgs() << "********** GREEDY REGISTER ALLOCATION **********\n" 317cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen << "********** Function: " 318cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen << ((Value*)mf.getFunction())->getName() << '\n'); 319cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 320cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen MF = &mf; 321cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen TM = &mf.getTarget(); 322cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen MRI = &mf.getRegInfo(); 323cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 324cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen const TargetRegisterInfo *TRI = TM->getRegisterInfo(); 325cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen RegAllocBase::init(*TRI, getAnalysis<VirtRegMap>(), 326cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen getAnalysis<LiveIntervals>()); 327cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 328cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen ReservedRegs = TRI->getReservedRegs(*MF); 329cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen SpillerInstance.reset(createSpiller(*this, *MF, *VRM)); 330cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen allocatePhysRegs(); 331cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen addMBBLiveIns(MF); 332cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 333cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen // Run rewriter 334cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen std::auto_ptr<VirtRegRewriter> rewriter(createVirtRegRewriter()); 335cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen rewriter->runOnMachineFunction(*MF, *VRM, LIS); 336cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 337cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen // The pass output is in VirtRegMap. Release all the transient data. 338cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen releaseMemory(); 339cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 340cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen return true; 341cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen} 342cba2e06d525b723849cd8e1f083eb1e59a494b4eJakob Stoklund Olesen 343