11553Srgrimes//===-- RegAllocFast.cpp - A fast register allocator for debug code -------===// 21553Srgrimes// 31553Srgrimes// The LLVM Compiler Infrastructure 41553Srgrimes// 51553Srgrimes// This file is distributed under the University of Illinois Open Source 61553Srgrimes// License. See LICENSE.TXT for details. 71553Srgrimes// 81553Srgrimes//===----------------------------------------------------------------------===// 91553Srgrimes// 101553Srgrimes// This register allocator allocates registers to a basic block at a time, 111553Srgrimes// attempting to keep values in registers and reusing registers as appropriate. 121553Srgrimes// 131553Srgrimes//===----------------------------------------------------------------------===// 141553Srgrimes 151553Srgrimes#define DEBUG_TYPE "regalloc" 161553Srgrimes#include "llvm/CodeGen/Passes.h" 171553Srgrimes#include "llvm/ADT/DenseMap.h" 181553Srgrimes#include "llvm/ADT/IndexedMap.h" 191553Srgrimes#include "llvm/ADT/STLExtras.h" 201553Srgrimes#include "llvm/ADT/SmallSet.h" 211553Srgrimes#include "llvm/ADT/SmallVector.h" 221553Srgrimes#include "llvm/ADT/SparseSet.h" 231553Srgrimes#include "llvm/ADT/Statistic.h" 241553Srgrimes#include "llvm/CodeGen/MachineFrameInfo.h" 251553Srgrimes#include "llvm/CodeGen/MachineFunctionPass.h" 261553Srgrimes#include "llvm/CodeGen/MachineInstr.h" 271553Srgrimes#include "llvm/CodeGen/MachineInstrBuilder.h" 281553Srgrimes#include "llvm/CodeGen/MachineRegisterInfo.h" 291553Srgrimes#include "llvm/CodeGen/RegAllocRegistry.h" 301553Srgrimes#include "llvm/CodeGen/RegisterClassInfo.h" 311553Srgrimes#include "llvm/IR/BasicBlock.h" 321553Srgrimes#include "llvm/Support/CommandLine.h" 331553Srgrimes#include "llvm/Support/Debug.h" 341553Srgrimes#include "llvm/Support/ErrorHandling.h" 351553Srgrimes#include "llvm/Support/raw_ostream.h" 361553Srgrimes#include "llvm/Target/TargetInstrInfo.h" 371553Srgrimes#include "llvm/Target/TargetMachine.h" 3829529Scharnier#include <algorithm> 391553Srgrimesusing namespace llvm; 401553Srgrimes 411553SrgrimesSTATISTIC(NumStores, "Number of stores added"); 421553SrgrimesSTATISTIC(NumLoads , "Number of loads added"); 431553SrgrimesSTATISTIC(NumCopies, "Number of copies coalesced"); 4429529Scharnier 451553Srgrimesstatic RegisterRegAlloc 4629529Scharnier fastRegAlloc("fast", "fast register allocator", createFastRegisterAllocator); 4729529Scharnier 4850479Speternamespace { 491553Srgrimes class RAFast : public MachineFunctionPass { 501553Srgrimes public: 511553Srgrimes static char ID; 521553Srgrimes RAFast() : MachineFunctionPass(ID), StackSlotForVirtReg(-1), 531553Srgrimes isBulkSpilling(false) {} 541553Srgrimes private: 551553Srgrimes const TargetMachine *TM; 561553Srgrimes MachineFunction *MF; 571553Srgrimes MachineRegisterInfo *MRI; 581553Srgrimes const TargetRegisterInfo *TRI; 5929529Scharnier const TargetInstrInfo *TII; 6029529Scharnier RegisterClassInfo RegClassInfo; 611553Srgrimes 621553Srgrimes // Basic block currently being allocated. 6329529Scharnier MachineBasicBlock *MBB; 641553Srgrimes 6529529Scharnier // StackSlotForVirtReg - Maps virtual regs to the frame index where these 661553Srgrimes // values are spilled. 6729529Scharnier IndexedMap<int, VirtReg2IndexFunctor> StackSlotForVirtReg; 681553Srgrimes 691553Srgrimes // Everything we know about a live virtual register. 701553Srgrimes struct LiveReg { 711553Srgrimes MachineInstr *LastUse; // Last instr to use reg. 7287596Smikeh unsigned VirtReg; // Virtual register number. 7387596Smikeh unsigned PhysReg; // Currently held here. 7487596Smikeh unsigned short LastOpNum; // OpNum on LastUse. 751553Srgrimes bool Dirty; // Register needs spill. 761553Srgrimes 771553Srgrimes explicit LiveReg(unsigned v) 781553Srgrimes : LastUse(0), VirtReg(v), PhysReg(0), LastOpNum(0), Dirty(false) {} 791553Srgrimes 801553Srgrimes unsigned getSparseSetIndex() const { 811553Srgrimes return TargetRegisterInfo::virtReg2Index(VirtReg); 821553Srgrimes } 8329529Scharnier }; 841553Srgrimes 851553Srgrimes typedef SparseSet<LiveReg> LiveRegMap; 8699800Salfred 8799800Salfred // LiveVirtRegs - This map contains entries for each virtual register 8899800Salfred // that is currently available in a physical register. 8999800Salfred LiveRegMap LiveVirtRegs; 9099800Salfred 9199800Salfred DenseMap<unsigned, SmallVector<MachineInstr *, 4> > LiveDbgValueMap; 9299800Salfred 9399800Salfred // RegState - Track the state of a physical register. 9499800Salfred enum RegState { 9599800Salfred // A disabled register is not available for allocation, but an alias may 9699800Salfred // be in use. A register can only be moved out of the disabled state if 9799800Salfred // all aliases are disabled. 9899800Salfred regDisabled, 9999800Salfred 10029529Scharnier // A free register is not currently in use and can be allocated 10129529Scharnier // immediately without checking aliases. 1021553Srgrimes regFree, 1031553Srgrimes 1041553Srgrimes // A reserved register has been assigned explicitly (e.g., setting up a 1051553Srgrimes // call parameter), and it remains reserved until it is used. 1061553Srgrimes regReserved 1071553Srgrimes 1081553Srgrimes // A register state may also be a virtual register number, indication that 10914961Smpp // the physical register is currently allocated to a virtual register. In 11014961Smpp // that case, LiveVirtRegs contains the inverse mapping. 1111553Srgrimes }; 11284081Syar 11314961Smpp // PhysRegState - One of the RegState enums, or a virtreg. 1141553Srgrimes std::vector<unsigned> PhysRegState; 1151553Srgrimes 1161553Srgrimes // Set of register units. 11729529Scharnier typedef SparseSet<unsigned> UsedInInstrSet; 11829529Scharnier 1191553Srgrimes // Set of register units that are used in the current instruction, and so 12084081Syar // cannot be allocated. 1211553Srgrimes UsedInInstrSet UsedInInstr; 12284081Syar 12384081Syar // Mark a physreg as used in this instruction. 12484081Syar void markRegUsedInInstr(unsigned PhysReg) { 1251553Srgrimes for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) 1261553Srgrimes UsedInInstr.insert(*Units); 1271553Srgrimes } 1281553Srgrimes 1291553Srgrimes // Check if a physreg or any of its aliases are used in this instruction. 1301553Srgrimes bool isRegUsedInInstr(unsigned PhysReg) const { 1311553Srgrimes for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) 1321553Srgrimes if (UsedInInstr.count(*Units)) 1331553Srgrimes return true; 1341553Srgrimes return false; 1351553Srgrimes } 1361553Srgrimes 1371553Srgrimes // SkippedInstrs - Descriptors of instructions whose clobber list was 1381553Srgrimes // ignored because all registers were spilled. It is still necessary to 1391553Srgrimes // mark all the clobbered registers as used by the function. 1401553Srgrimes SmallPtrSet<const MCInstrDesc*, 4> SkippedInstrs; 1411553Srgrimes 1421553Srgrimes // isBulkSpilling - This flag is set when LiveRegMap will be cleared 1431553Srgrimes // completely after spilling all live registers. LiveRegMap entries should 1441553Srgrimes // not be erased. 1451553Srgrimes bool isBulkSpilling; 1461553Srgrimes 14784081Syar enum LLVM_ENUM_INT_TYPE(unsigned) { 1481553Srgrimes spillClean = 1, 1491553Srgrimes spillDirty = 100, 1501553Srgrimes spillImpossible = ~0u 1511553Srgrimes }; 1521553Srgrimes public: 15314961Smpp virtual const char *getPassName() const { 15414961Smpp return "Fast Register Allocator"; 15514961Smpp } 15614961Smpp 15714961Smpp virtual void getAnalysisUsage(AnalysisUsage &AU) const { 15829529Scharnier AU.setPreservesCFG(); 15929529Scharnier MachineFunctionPass::getAnalysisUsage(AU); 16029529Scharnier } 16114961Smpp 16214961Smpp private: 16314961Smpp bool runOnMachineFunction(MachineFunction &Fn); 16414961Smpp void AllocateBasicBlock(); 16514961Smpp void handleThroughOperands(MachineInstr *MI, 16614961Smpp SmallVectorImpl<unsigned> &VirtDead); 16714961Smpp int getStackSpaceFor(unsigned VirtReg, const TargetRegisterClass *RC); 16814961Smpp bool isLastUseOfLocalReg(MachineOperand&); 16914961Smpp 17014961Smpp void addKillFlag(const LiveReg&); 1711553Srgrimes void killVirtReg(LiveRegMap::iterator); 1721553Srgrimes void killVirtReg(unsigned VirtReg); 1731553Srgrimes void spillVirtReg(MachineBasicBlock::iterator MI, LiveRegMap::iterator); 1741553Srgrimes void spillVirtReg(MachineBasicBlock::iterator MI, unsigned VirtReg); 1751553Srgrimes 1761553Srgrimes void usePhysReg(MachineOperand&); 1771553Srgrimes void definePhysReg(MachineInstr *MI, unsigned PhysReg, RegState NewState); 1781553Srgrimes unsigned calcSpillCost(unsigned PhysReg) const; 1791553Srgrimes void assignVirtToPhysReg(LiveReg&, unsigned PhysReg); 18084081Syar LiveRegMap::iterator findLiveVirtReg(unsigned VirtReg) { 1811553Srgrimes return LiveVirtRegs.find(TargetRegisterInfo::virtReg2Index(VirtReg)); 1821553Srgrimes } 1834782Sache LiveRegMap::const_iterator findLiveVirtReg(unsigned VirtReg) const { 1841553Srgrimes return LiveVirtRegs.find(TargetRegisterInfo::virtReg2Index(VirtReg)); 1851553Srgrimes } 18628431Sjlemon LiveRegMap::iterator assignVirtToPhysReg(unsigned VReg, unsigned PhysReg); 18728431Sjlemon LiveRegMap::iterator allocVirtReg(MachineInstr *MI, LiveRegMap::iterator, 1881553Srgrimes unsigned Hint); 1891553Srgrimes LiveRegMap::iterator defineVirtReg(MachineInstr *MI, unsigned OpNum, 1901553Srgrimes unsigned VirtReg, unsigned Hint); 1911553Srgrimes LiveRegMap::iterator reloadVirtReg(MachineInstr *MI, unsigned OpNum, 1921553Srgrimes unsigned VirtReg, unsigned Hint); 19384081Syar void spillAll(MachineBasicBlock::iterator MI); 1941553Srgrimes bool setPhysReg(MachineInstr *MI, unsigned OpNum, unsigned PhysReg); 1951553Srgrimes }; 1964782Sache char RAFast::ID = 0; 1971553Srgrimes} 1981553Srgrimes 1991553Srgrimes/// getStackSpaceFor - This allocates space for the specified virtual register 2001553Srgrimes/// to be held on the stack. 2011553Srgrimesint RAFast::getStackSpaceFor(unsigned VirtReg, const TargetRegisterClass *RC) { 2021553Srgrimes // Find the location Reg would belong... 2031553Srgrimes int SS = StackSlotForVirtReg[VirtReg]; 2041553Srgrimes if (SS != -1) 20529529Scharnier return SS; // Already has space allocated? 2061553Srgrimes 2071553Srgrimes // Allocate a new stack object for this spill location... 20829529Scharnier int FrameIdx = MF->getFrameInfo()->CreateSpillStackObject(RC->getSize(), 20984081Syar RC->getAlignment()); 21084081Syar 21184081Syar // Assign the slot. 21284081Syar StackSlotForVirtReg[VirtReg] = FrameIdx; 2131553Srgrimes return FrameIdx; 2141553Srgrimes} 2151553Srgrimes 2161553Srgrimes/// isLastUseOfLocalReg - Return true if MO is the only remaining reference to 2171553Srgrimes/// its virtual register, and it is guaranteed to be a block-local register. 2181553Srgrimes/// 2191553Srgrimesbool RAFast::isLastUseOfLocalReg(MachineOperand &MO) { 2201553Srgrimes // If the register has ever been spilled or reloaded, we conservatively assume 22129529Scharnier // it is a global register used in multiple blocks. 2221553Srgrimes if (StackSlotForVirtReg[MO.getReg()] != -1) 22387596Smikeh return false; 2241553Srgrimes 2251553Srgrimes // Check that the use/def chain has exactly one operand - MO. 2261553Srgrimes MachineRegisterInfo::reg_nodbg_iterator I = MRI->reg_nodbg_begin(MO.getReg()); 2271553Srgrimes if (&I.getOperand() != &MO) 2281553Srgrimes return false; 2291553Srgrimes return ++I == MRI->reg_nodbg_end(); 2301553Srgrimes} 2311553Srgrimes 2321553Srgrimes/// addKillFlag - Set kill flags on last use of a virtual register. 23329529Scharniervoid RAFast::addKillFlag(const LiveReg &LR) { 2341553Srgrimes if (!LR.LastUse) return; 23529529Scharnier MachineOperand &MO = LR.LastUse->getOperand(LR.LastOpNum); 2361553Srgrimes if (MO.isUse() && !LR.LastUse->isRegTiedToDefOperand(LR.LastOpNum)) { 2371553Srgrimes if (MO.getReg() == LR.PhysReg) 23829529Scharnier MO.setIsKill(); 2391553Srgrimes else 24029529Scharnier LR.LastUse->addRegisterKilled(LR.PhysReg, TRI, true); 2411553Srgrimes } 2421553Srgrimes} 24329529Scharnier 2441553Srgrimes/// killVirtReg - Mark virtreg as no longer available. 2451553Srgrimesvoid RAFast::killVirtReg(LiveRegMap::iterator LRI) { 2461553Srgrimes addKillFlag(*LRI); 2471553Srgrimes assert(PhysRegState[LRI->PhysReg] == LRI->VirtReg && 2481553Srgrimes "Broken RegState mapping"); 2491553Srgrimes PhysRegState[LRI->PhysReg] = regFree; 2501553Srgrimes // Erase from LiveVirtRegs unless we're spilling in bulk. 2511553Srgrimes if (!isBulkSpilling) 2521553Srgrimes LiveVirtRegs.erase(LRI); 2531553Srgrimes} 25484081Syar 2551553Srgrimes/// killVirtReg - Mark virtreg as no longer available. 2561553Srgrimesvoid RAFast::killVirtReg(unsigned VirtReg) { 25784081Syar assert(TargetRegisterInfo::isVirtualRegister(VirtReg) && 2581553Srgrimes "killVirtReg needs a virtual register"); 2591553Srgrimes LiveRegMap::iterator LRI = findLiveVirtReg(VirtReg); 2601553Srgrimes if (LRI != LiveVirtRegs.end()) 2611553Srgrimes killVirtReg(LRI); 2621553Srgrimes} 2631553Srgrimes 2641553Srgrimes/// spillVirtReg - This method spills the value specified by VirtReg into the 2651553Srgrimes/// corresponding stack slot if needed. 2661553Srgrimesvoid RAFast::spillVirtReg(MachineBasicBlock::iterator MI, unsigned VirtReg) { 2671553Srgrimes assert(TargetRegisterInfo::isVirtualRegister(VirtReg) && 2681553Srgrimes "Spilling a physical register is illegal!"); 26929529Scharnier LiveRegMap::iterator LRI = findLiveVirtReg(VirtReg); 27084081Syar assert(LRI != LiveVirtRegs.end() && "Spilling unmapped virtual register"); 27184081Syar spillVirtReg(MI, LRI); 27284081Syar} 2731553Srgrimes 2741553Srgrimes/// spillVirtReg - Do the actual work of spilling. 2751553Srgrimesvoid RAFast::spillVirtReg(MachineBasicBlock::iterator MI, 2761553Srgrimes LiveRegMap::iterator LRI) { 2771553Srgrimes LiveReg &LR = *LRI; 27829529Scharnier assert(PhysRegState[LR.PhysReg] == LRI->VirtReg && "Broken RegState mapping"); 27929529Scharnier 2801553Srgrimes if (LR.Dirty) { 2811553Srgrimes // If this physreg is used by the instruction, we want to kill it on the 2821553Srgrimes // instruction, not on the spill. 28329529Scharnier bool SpillKill = LR.LastUse != MI; 2841553Srgrimes LR.Dirty = false; 2851553Srgrimes DEBUG(dbgs() << "Spilling " << PrintReg(LRI->VirtReg, TRI) 2861553Srgrimes << " in " << PrintReg(LR.PhysReg, TRI)); 2871553Srgrimes const TargetRegisterClass *RC = MRI->getRegClass(LRI->VirtReg); 2881553Srgrimes int FI = getStackSpaceFor(LRI->VirtReg, RC); 28929529Scharnier DEBUG(dbgs() << " to stack slot #" << FI << "\n"); 2901553Srgrimes TII->storeRegToStackSlot(*MBB, MI, LR.PhysReg, SpillKill, FI, RC, TRI); 2911553Srgrimes ++NumStores; // Update statistics 2921553Srgrimes 29329529Scharnier // If this register is used by DBG_VALUE then insert new DBG_VALUE to 2941553Srgrimes // identify spilled location as the place to find corresponding variable's 2951553Srgrimes // value. 2961553Srgrimes SmallVectorImpl<MachineInstr *> &LRIDbgValues = 2971553Srgrimes LiveDbgValueMap[LRI->VirtReg]; 2981553Srgrimes for (unsigned li = 0, le = LRIDbgValues.size(); li != le; ++li) { 2991553Srgrimes MachineInstr *DBG = LRIDbgValues[li]; 3001553Srgrimes const MDNode *MDPtr = DBG->getOperand(2).getMetadata(); 3011553Srgrimes bool IsIndirect = DBG->isIndirectDebugValue(); 3021553Srgrimes uint64_t Offset = IsIndirect ? DBG->getOperand(1).getImm() : 0; 3031553Srgrimes DebugLoc DL; 3041553Srgrimes if (MI == MBB->end()) { 3051553Srgrimes // If MI is at basic block end then use last instruction's location. 3061553Srgrimes MachineBasicBlock::iterator EI = MI; 3071553Srgrimes DL = (--EI)->getDebugLoc(); 3081553Srgrimes } else 3091553Srgrimes DL = MI->getDebugLoc(); 3101553Srgrimes MachineBasicBlock *MBB = DBG->getParent(); 3111553Srgrimes MachineInstr *NewDV = 3121553Srgrimes BuildMI(*MBB, MI, DL, TII->get(TargetOpcode::DBG_VALUE)) 3131553Srgrimes .addFrameIndex(FI).addImm(Offset).addMetadata(MDPtr); 31429529Scharnier (void)NewDV; 3151553Srgrimes DEBUG(dbgs() << "Inserting debug info due to spill:" << "\n" << *NewDV); 3161553Srgrimes } 3171553Srgrimes // Now this register is spilled there is should not be any DBG_VALUE 3181553Srgrimes // pointing to this register because they are all pointing to spilled value 3191553Srgrimes // now. 3201553Srgrimes LRIDbgValues.clear(); 3211553Srgrimes if (SpillKill) 3221553Srgrimes LR.LastUse = 0; // Don't kill register again 3231553Srgrimes } 3241553Srgrimes killVirtReg(LRI); 3251553Srgrimes} 3261553Srgrimes 3271553Srgrimes/// spillAll - Spill all dirty virtregs without killing them. 3281553Srgrimesvoid RAFast::spillAll(MachineBasicBlock::iterator MI) { 3291553Srgrimes if (LiveVirtRegs.empty()) return; 3301553Srgrimes isBulkSpilling = true; 3311553Srgrimes // The LiveRegMap is keyed by an unsigned (the virtreg number), so the order 3321553Srgrimes // of spilling here is deterministic, if arbitrary. 3331553Srgrimes for (LiveRegMap::iterator i = LiveVirtRegs.begin(), e = LiveVirtRegs.end(); 3341553Srgrimes i != e; ++i) 3351553Srgrimes spillVirtReg(MI, i); 3361553Srgrimes LiveVirtRegs.clear(); 33729529Scharnier isBulkSpilling = false; 3381553Srgrimes} 3391553Srgrimes 3401553Srgrimes/// usePhysReg - Handle the direct use of a physical register. 3411553Srgrimes/// Check that the register is not used by a virtreg. 3421553Srgrimes/// Kill the physreg, marking it free. 3431553Srgrimes/// This may add implicit kills to MO->getParent() and invalidate MO. 3441553Srgrimesvoid RAFast::usePhysReg(MachineOperand &MO) { 3451553Srgrimes unsigned PhysReg = MO.getReg(); 3461553Srgrimes assert(TargetRegisterInfo::isPhysicalRegister(PhysReg) && 3471553Srgrimes "Bad usePhysReg operand"); 3481553Srgrimes markRegUsedInInstr(PhysReg); 3491553Srgrimes switch (PhysRegState[PhysReg]) { 3501553Srgrimes case regDisabled: 35129529Scharnier break; 3521553Srgrimes case regReserved: 3531553Srgrimes PhysRegState[PhysReg] = regFree; 3541553Srgrimes // Fall through 3551553Srgrimes case regFree: 35629529Scharnier MO.setIsKill(); 3571553Srgrimes return; 3581553Srgrimes default: 3591553Srgrimes // The physreg was allocated to a virtual register. That means the value we 3601553Srgrimes // wanted has been clobbered. 3611553Srgrimes llvm_unreachable("Instruction uses an allocated register"); 3621553Srgrimes } 3631553Srgrimes 3641553Srgrimes // Maybe a superregister is reserved? 3651553Srgrimes for (MCRegAliasIterator AI(PhysReg, TRI, false); AI.isValid(); ++AI) { 36629529Scharnier unsigned Alias = *AI; 36787596Smikeh switch (PhysRegState[Alias]) { 36887596Smikeh case regDisabled: 3691553Srgrimes break; 3701553Srgrimes case regReserved: 37187596Smikeh assert(TRI->isSuperRegister(PhysReg, Alias) && 3721553Srgrimes "Instruction is not using a subregister of a reserved register"); 3731553Srgrimes // Leave the superregister in the working set. 3741553Srgrimes PhysRegState[Alias] = regFree; 3751553Srgrimes MO.getParent()->addRegisterKilled(Alias, TRI, true); 3761553Srgrimes return; 3771553Srgrimes case regFree: 37829529Scharnier if (TRI->isSuperRegister(PhysReg, Alias)) { 3791553Srgrimes // Leave the superregister in the working set. 3801553Srgrimes MO.getParent()->addRegisterKilled(Alias, TRI, true); 3811553Srgrimes return; 3821553Srgrimes } 3831553Srgrimes // Some other alias was in the working set - clear it. 3841553Srgrimes PhysRegState[Alias] = regDisabled; 38529529Scharnier break; 3861553Srgrimes default: 3871553Srgrimes llvm_unreachable("Instruction uses an alias of an allocated register"); 3881553Srgrimes } 38987596Smikeh } 3901553Srgrimes 3911553Srgrimes // All aliases are disabled, bring register into working set. 3921553Srgrimes PhysRegState[PhysReg] = regFree; 3931553Srgrimes MO.setIsKill(); 3941553Srgrimes} 3951553Srgrimes 39687596Smikeh/// definePhysReg - Mark PhysReg as reserved or free after spilling any 39729529Scharnier/// virtregs. This is very similar to defineVirtReg except the physreg is 3981553Srgrimes/// reserved instead of allocated. 39987596Smikehvoid RAFast::definePhysReg(MachineInstr *MI, unsigned PhysReg, 4001553Srgrimes RegState NewState) { 40187596Smikeh markRegUsedInInstr(PhysReg); 4021553Srgrimes switch (unsigned VirtReg = PhysRegState[PhysReg]) { 4031553Srgrimes case regDisabled: 4041553Srgrimes break; 4051553Srgrimes default: 4061553Srgrimes spillVirtReg(MI, VirtReg); 4071553Srgrimes // Fall through. 4081553Srgrimes case regFree: 40929529Scharnier case regReserved: 4101553Srgrimes PhysRegState[PhysReg] = NewState; 4111553Srgrimes return; 4121553Srgrimes } 4131553Srgrimes 4141553Srgrimes // This is a disabled register, disable all aliases. 4151553Srgrimes PhysRegState[PhysReg] = NewState; 4161553Srgrimes for (MCRegAliasIterator AI(PhysReg, TRI, false); AI.isValid(); ++AI) { 4171553Srgrimes unsigned Alias = *AI; 4181553Srgrimes switch (unsigned VirtReg = PhysRegState[Alias]) { 4191553Srgrimes case regDisabled: 4201553Srgrimes break; 42129529Scharnier default: 42229529Scharnier spillVirtReg(MI, VirtReg); 4231553Srgrimes // Fall through. 4241553Srgrimes case regFree: 42567794Sgallatin case regReserved: 4261553Srgrimes PhysRegState[Alias] = regDisabled; 4278325Sbde if (TRI->isSuperRegister(PhysReg, Alias)) 4288325Sbde return; 4298325Sbde break; 43067794Sgallatin } 43167794Sgallatin } 43267794Sgallatin} 43367794Sgallatin 43467794Sgallatin 4351553Srgrimes// calcSpillCost - Return the cost of spilling clearing out PhysReg and 4361553Srgrimes// aliases so it is free for allocation. 4371553Srgrimes// Returns 0 when PhysReg is free or disabled with all aliases disabled - it 4381553Srgrimes// can be allocated directly. 4391553Srgrimes// Returns spillImpossible when PhysReg or an alias can't be spilled. 4401553Srgrimesunsigned RAFast::calcSpillCost(unsigned PhysReg) const { 4411553Srgrimes if (isRegUsedInInstr(PhysReg)) { 4421553Srgrimes DEBUG(dbgs() << PrintReg(PhysReg, TRI) << " is already used in instr.\n"); 44329529Scharnier return spillImpossible; 4444782Sache } 4451553Srgrimes switch (unsigned VirtReg = PhysRegState[PhysReg]) { 4464782Sache case regDisabled: 4471553Srgrimes break; 4481553Srgrimes case regFree: 4491553Srgrimes return 0; 45067794Sgallatin case regReserved: 45167794Sgallatin DEBUG(dbgs() << PrintReg(VirtReg, TRI) << " corresponding " 4521553Srgrimes << PrintReg(PhysReg, TRI) << " is reserved already.\n"); 4531553Srgrimes return spillImpossible; 4541553Srgrimes default: { 4551553Srgrimes LiveRegMap::const_iterator I = findLiveVirtReg(VirtReg); 4561553Srgrimes assert(I != LiveVirtRegs.end() && "Missing VirtReg entry"); 4574782Sache return I->Dirty ? spillDirty : spillClean; 4581553Srgrimes } 45929529Scharnier } 4601553Srgrimes 4611553Srgrimes // This is a disabled register, add up cost of aliases. 4621553Srgrimes DEBUG(dbgs() << PrintReg(PhysReg, TRI) << " is disabled.\n"); 4631553Srgrimes unsigned Cost = 0; 4641553Srgrimes for (MCRegAliasIterator AI(PhysReg, TRI, false); AI.isValid(); ++AI) { 4651553Srgrimes unsigned Alias = *AI; 4661553Srgrimes switch (unsigned VirtReg = PhysRegState[Alias]) { 4671553Srgrimes case regDisabled: 4681553Srgrimes break; 46929529Scharnier case regFree: 4701553Srgrimes ++Cost; 4711553Srgrimes break; 4721553Srgrimes case regReserved: 47329529Scharnier return spillImpossible; 4741553Srgrimes default: { 4751553Srgrimes LiveRegMap::const_iterator I = findLiveVirtReg(VirtReg); 4761553Srgrimes assert(I != LiveVirtRegs.end() && "Missing VirtReg entry"); 47767794Sgallatin Cost += I->Dirty ? spillDirty : spillClean; 47867794Sgallatin break; 4791553Srgrimes } 48029529Scharnier } 4811553Srgrimes } 4821553Srgrimes return Cost; 48367794Sgallatin} 48467794Sgallatin 48567794Sgallatin 4861553Srgrimes/// assignVirtToPhysReg - This method updates local state so that we know 48729529Scharnier/// that PhysReg is the proper container for VirtReg now. The physical 4881553Srgrimes/// register must not be used for anything else when this is called. 4891553Srgrimes/// 4901553Srgrimesvoid RAFast::assignVirtToPhysReg(LiveReg &LR, unsigned PhysReg) { 49167794Sgallatin DEBUG(dbgs() << "Assigning " << PrintReg(LR.VirtReg, TRI) << " to " 49267794Sgallatin << PrintReg(PhysReg, TRI) << "\n"); 4931553Srgrimes PhysRegState[PhysReg] = LR.VirtReg; 49429529Scharnier assert(!LR.PhysReg && "Already assigned a physreg"); 4951553Srgrimes LR.PhysReg = PhysReg; 4961553Srgrimes} 49767794Sgallatin 49867794SgallatinRAFast::LiveRegMap::iterator 49967794SgallatinRAFast::assignVirtToPhysReg(unsigned VirtReg, unsigned PhysReg) { 5001553Srgrimes LiveRegMap::iterator LRI = findLiveVirtReg(VirtReg); 5011553Srgrimes assert(LRI != LiveVirtRegs.end() && "VirtReg disappeared"); 5021553Srgrimes assignVirtToPhysReg(*LRI, PhysReg); 5031553Srgrimes return LRI; 5041553Srgrimes} 5051553Srgrimes 5061553Srgrimes/// allocVirtReg - Allocate a physical register for VirtReg. 5071553SrgrimesRAFast::LiveRegMap::iterator RAFast::allocVirtReg(MachineInstr *MI, 5081553Srgrimes LiveRegMap::iterator LRI, 5091553Srgrimes unsigned Hint) { 5101553Srgrimes const unsigned VirtReg = LRI->VirtReg; 5111553Srgrimes 5121553Srgrimes assert(TargetRegisterInfo::isVirtualRegister(VirtReg) && 5131553Srgrimes "Can only allocate virtual registers"); 5141553Srgrimes 5151553Srgrimes const TargetRegisterClass *RC = MRI->getRegClass(VirtReg); 5161553Srgrimes 5171553Srgrimes // Ignore invalid hints. 5181553Srgrimes if (Hint && (!TargetRegisterInfo::isPhysicalRegister(Hint) || 5191553Srgrimes !RC->contains(Hint) || !MRI->isAllocatable(Hint))) 5201553Srgrimes Hint = 0; 5211553Srgrimes 5221553Srgrimes // Take hint when possible. 5231553Srgrimes if (Hint) { 5241553Srgrimes // Ignore the hint if we would have to spill a dirty register. 5251553Srgrimes unsigned Cost = calcSpillCost(Hint); 5261553Srgrimes if (Cost < spillDirty) { 5271553Srgrimes if (Cost) 5281553Srgrimes definePhysReg(MI, Hint, regFree); 52929529Scharnier // definePhysReg may kill virtual registers and modify LiveVirtRegs. 5301553Srgrimes // That invalidates LRI, so run a new lookup for VirtReg. 5311553Srgrimes return assignVirtToPhysReg(VirtReg, Hint); 5321553Srgrimes } 5331553Srgrimes } 5341553Srgrimes 5351553Srgrimes ArrayRef<MCPhysReg> AO = RegClassInfo.getOrder(RC); 5361553Srgrimes 5371553Srgrimes // First try to find a completely free register. 5381553Srgrimes for (ArrayRef<MCPhysReg>::iterator I = AO.begin(), E = AO.end(); I != E; ++I){ 5391553Srgrimes unsigned PhysReg = *I; 5401553Srgrimes if (PhysRegState[PhysReg] == regFree && !isRegUsedInInstr(PhysReg)) { 5411553Srgrimes assignVirtToPhysReg(*LRI, PhysReg); 5421553Srgrimes return LRI; 5431553Srgrimes } 5441553Srgrimes } 5451553Srgrimes 5461553Srgrimes DEBUG(dbgs() << "Allocating " << PrintReg(VirtReg) << " from " 5471553Srgrimes << RC->getName() << "\n"); 5481553Srgrimes 5491553Srgrimes unsigned BestReg = 0, BestCost = spillImpossible; 5501553Srgrimes for (ArrayRef<MCPhysReg>::iterator I = AO.begin(), E = AO.end(); I != E; ++I){ 5511553Srgrimes unsigned Cost = calcSpillCost(*I); 5521553Srgrimes DEBUG(dbgs() << "\tRegister: " << PrintReg(*I, TRI) << "\n"); 55329529Scharnier DEBUG(dbgs() << "\tCost: " << Cost << "\n"); 5541553Srgrimes DEBUG(dbgs() << "\tBestCost: " << BestCost << "\n"); 5551553Srgrimes // Cost is 0 when all aliases are already disabled. 5561553Srgrimes if (Cost == 0) { 5571553Srgrimes assignVirtToPhysReg(*LRI, *I); 5581553Srgrimes return LRI; 5591553Srgrimes } 5601553Srgrimes if (Cost < BestCost) 5611553Srgrimes BestReg = *I, BestCost = Cost; 5621553Srgrimes } 5631553Srgrimes 56429529Scharnier if (BestReg) { 56529529Scharnier definePhysReg(MI, BestReg, regFree); 5661553Srgrimes // definePhysReg may kill virtual registers and modify LiveVirtRegs. 5671553Srgrimes // That invalidates LRI, so run a new lookup for VirtReg. 5681553Srgrimes return assignVirtToPhysReg(VirtReg, BestReg); 5691553Srgrimes } 5701553Srgrimes 5711553Srgrimes // Nothing we can do. Report an error and keep going with a bad allocation. 5721553Srgrimes if (MI->isInlineAsm()) 5731553Srgrimes MI->emitError("inline assembly requires more registers than available"); 5741553Srgrimes else 5751553Srgrimes MI->emitError("ran out of registers during register allocation"); 5761553Srgrimes definePhysReg(MI, *AO.begin(), regFree); 5771553Srgrimes return assignVirtToPhysReg(VirtReg, *AO.begin()); 5781553Srgrimes} 5791553Srgrimes 5801553Srgrimes/// defineVirtReg - Allocate a register for VirtReg and mark it as dirty. 5811553SrgrimesRAFast::LiveRegMap::iterator 58229529ScharnierRAFast::defineVirtReg(MachineInstr *MI, unsigned OpNum, 5834782Sache unsigned VirtReg, unsigned Hint) { 5841553Srgrimes assert(TargetRegisterInfo::isVirtualRegister(VirtReg) && 5854782Sache "Not a virtual register"); 5861553Srgrimes LiveRegMap::iterator LRI; 5871553Srgrimes bool New; 5881553Srgrimes tie(LRI, New) = LiveVirtRegs.insert(LiveReg(VirtReg)); 5891553Srgrimes if (New) { 5901553Srgrimes // If there is no hint, peek at the only use of this register. 5911553Srgrimes if ((!Hint || !TargetRegisterInfo::isPhysicalRegister(Hint)) && 59267794Sgallatin MRI->hasOneNonDBGUse(VirtReg)) { 5931553Srgrimes const MachineInstr &UseMI = *MRI->use_nodbg_begin(VirtReg); 5941553Srgrimes // It's a copy, use the destination register as a hint. 5954782Sache if (UseMI.isCopyLike()) 5961553Srgrimes Hint = UseMI.getOperand(0).getReg(); 59729529Scharnier } 5981553Srgrimes LRI = allocVirtReg(MI, LRI, Hint); 5991553Srgrimes } else if (LRI->LastUse) { 6001553Srgrimes // Redefining a live register - kill at the last use, unless it is this 6011553Srgrimes // instruction defining VirtReg multiple times. 6021553Srgrimes if (LRI->LastUse != MI || LRI->LastUse->getOperand(LRI->LastOpNum).isUse()) 6031553Srgrimes addKillFlag(*LRI); 6041553Srgrimes } 6051553Srgrimes assert(LRI->PhysReg && "Register not assigned"); 6061553Srgrimes LRI->LastUse = MI; 60729529Scharnier LRI->LastOpNum = OpNum; 6081553Srgrimes LRI->Dirty = true; 6091553Srgrimes markRegUsedInInstr(LRI->PhysReg); 6101553Srgrimes return LRI; 61129529Scharnier} 6121553Srgrimes 6131553Srgrimes/// reloadVirtReg - Make sure VirtReg is available in a physreg and return it. 6141553SrgrimesRAFast::LiveRegMap::iterator 6158325SbdeRAFast::reloadVirtReg(MachineInstr *MI, unsigned OpNum, 61667794Sgallatin unsigned VirtReg, unsigned Hint) { 6171553Srgrimes assert(TargetRegisterInfo::isVirtualRegister(VirtReg) && 61829529Scharnier "Not a virtual register"); 6191553Srgrimes LiveRegMap::iterator LRI; 6201553Srgrimes bool New; 62167794Sgallatin tie(LRI, New) = LiveVirtRegs.insert(LiveReg(VirtReg)); 62267794Sgallatin MachineOperand &MO = MI->getOperand(OpNum); 6231553Srgrimes if (New) { 6241553Srgrimes LRI = allocVirtReg(MI, LRI, Hint); 6251553Srgrimes const TargetRegisterClass *RC = MRI->getRegClass(VirtReg); 6261553Srgrimes int FrameIndex = getStackSpaceFor(VirtReg, RC); 6271553Srgrimes DEBUG(dbgs() << "Reloading " << PrintReg(VirtReg, TRI) << " into " 6281553Srgrimes << PrintReg(LRI->PhysReg, TRI) << "\n"); 6291553Srgrimes TII->loadRegFromStackSlot(*MBB, MI, LRI->PhysReg, FrameIndex, RC, TRI); 6301553Srgrimes ++NumLoads; 6311553Srgrimes } else if (LRI->Dirty) { 6321553Srgrimes if (isLastUseOfLocalReg(MO)) { 6331553Srgrimes DEBUG(dbgs() << "Killing last use: " << MO << "\n"); 6341553Srgrimes if (MO.isUse()) 6351553Srgrimes MO.setIsKill(); 6361553Srgrimes else 6371553Srgrimes MO.setIsDead(); 6381553Srgrimes } else if (MO.isKill()) { 6391553Srgrimes DEBUG(dbgs() << "Clearing dubious kill: " << MO << "\n"); 6401553Srgrimes MO.setIsKill(false); 6411553Srgrimes } else if (MO.isDead()) { 6421553Srgrimes DEBUG(dbgs() << "Clearing dubious dead: " << MO << "\n"); 6431553Srgrimes MO.setIsDead(false); 6441553Srgrimes } 6451553Srgrimes } else if (MO.isKill()) { 6461553Srgrimes // We must remove kill flags from uses of reloaded registers because the 6471553Srgrimes // register would be killed immediately, and there might be a second use: 6481553Srgrimes // %foo = OR %x<kill>, %x 6491553Srgrimes // This would cause a second reload of %x into a different register. 6501553Srgrimes DEBUG(dbgs() << "Clearing clean kill: " << MO << "\n"); 6511553Srgrimes MO.setIsKill(false); 6521553Srgrimes } else if (MO.isDead()) { 6531553Srgrimes DEBUG(dbgs() << "Clearing clean dead: " << MO << "\n"); 6541553Srgrimes MO.setIsDead(false); 6551553Srgrimes } 65687596Smikeh assert(LRI->PhysReg && "Register not assigned"); 65787596Smikeh LRI->LastUse = MI; 6581553Srgrimes LRI->LastOpNum = OpNum; 6591553Srgrimes markRegUsedInInstr(LRI->PhysReg); 6601553Srgrimes return LRI; 66187596Smikeh} 66287596Smikeh 66387596Smikeh// setPhysReg - Change operand OpNum in MI the refer the PhysReg, considering 66487596Smikeh// subregs. This may invalidate any operand pointers. 66587596Smikeh// Return true if the operand kills its register. 66687596Smikehbool RAFast::setPhysReg(MachineInstr *MI, unsigned OpNum, unsigned PhysReg) { 66787596Smikeh MachineOperand &MO = MI->getOperand(OpNum); 66887596Smikeh bool Dead = MO.isDead(); 66987596Smikeh if (!MO.getSubReg()) { 6701553Srgrimes MO.setReg(PhysReg); 67187596Smikeh return MO.isKill() || Dead; 6721553Srgrimes } 6731553Srgrimes 6741553Srgrimes // Handle subregister index. 6751553Srgrimes MO.setReg(PhysReg ? TRI->getSubReg(PhysReg, MO.getSubReg()) : 0); 6761553Srgrimes MO.setSubReg(0); 6771553Srgrimes 67829529Scharnier // A kill flag implies killing the full register. Add corresponding super 67987596Smikeh // register kill. 68087596Smikeh if (MO.isKill()) { 6811553Srgrimes MI->addRegisterKilled(PhysReg, TRI, true); 6821553Srgrimes return true; 6831553Srgrimes } 6841553Srgrimes 6851553Srgrimes // A <def,read-undef> of a sub-register requires an implicit def of the full 68687596Smikeh // register. 6871553Srgrimes if (MO.isDef() && MO.isUndef()) 68887596Smikeh MI->addRegisterDefined(PhysReg, TRI); 6891553Srgrimes 69087596Smikeh return Dead; 6911553Srgrimes} 69287596Smikeh 6931553Srgrimes// Handle special instruction operand like early clobbers and tied ops when 6941553Srgrimes// there are additional physreg defines. 6951553Srgrimesvoid RAFast::handleThroughOperands(MachineInstr *MI, 6961553Srgrimes SmallVectorImpl<unsigned> &VirtDead) { 6971553Srgrimes DEBUG(dbgs() << "Scanning for through registers:"); 6981553Srgrimes SmallSet<unsigned, 8> ThroughRegs; 6991553Srgrimes for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 7001553Srgrimes MachineOperand &MO = MI->getOperand(i); 7011553Srgrimes if (!MO.isReg()) continue; 7021553Srgrimes unsigned Reg = MO.getReg(); 7031553Srgrimes if (!TargetRegisterInfo::isVirtualRegister(Reg)) 70429529Scharnier continue; 7051553Srgrimes if (MO.isEarlyClobber() || MI->isRegTiedToDefOperand(i) || 7061553Srgrimes (MO.getSubReg() && MI->readsVirtualRegister(Reg))) { 7071553Srgrimes if (ThroughRegs.insert(Reg)) 7081553Srgrimes DEBUG(dbgs() << ' ' << PrintReg(Reg)); 7091553Srgrimes } 7101553Srgrimes } 7111553Srgrimes 7121553Srgrimes // If any physreg defines collide with preallocated through registers, 7131553Srgrimes // we must spill and reallocate. 7141553Srgrimes DEBUG(dbgs() << "\nChecking for physdef collisions.\n"); 7151553Srgrimes for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 7161553Srgrimes MachineOperand &MO = MI->getOperand(i); 7171553Srgrimes if (!MO.isReg() || !MO.isDef()) continue; 7181553Srgrimes unsigned Reg = MO.getReg(); 71929529Scharnier if (!Reg || !TargetRegisterInfo::isPhysicalRegister(Reg)) continue; 7201553Srgrimes markRegUsedInInstr(Reg); 72187596Smikeh for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) { 7221553Srgrimes if (ThroughRegs.count(PhysRegState[*AI])) 72387596Smikeh definePhysReg(MI, *AI, regFree); 7241553Srgrimes } 7251553Srgrimes } 7261553Srgrimes 7271553Srgrimes SmallVector<unsigned, 8> PartialDefs; 7281553Srgrimes DEBUG(dbgs() << "Allocating tied uses.\n"); 72929529Scharnier for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 7301553Srgrimes MachineOperand &MO = MI->getOperand(i); 7311553Srgrimes if (!MO.isReg()) continue; 7321553Srgrimes unsigned Reg = MO.getReg(); 7331553Srgrimes if (!TargetRegisterInfo::isVirtualRegister(Reg)) continue; 7341553Srgrimes if (MO.isUse()) { 7351553Srgrimes unsigned DefIdx = 0; 73629529Scharnier if (!MI->isRegTiedToDefOperand(i, &DefIdx)) continue; 7371553Srgrimes DEBUG(dbgs() << "Operand " << i << "("<< MO << ") is tied to operand " 7381553Srgrimes << DefIdx << ".\n"); 7391553Srgrimes LiveRegMap::iterator LRI = reloadVirtReg(MI, i, Reg, 0); 7401553Srgrimes unsigned PhysReg = LRI->PhysReg; 7411553Srgrimes setPhysReg(MI, i, PhysReg); 7421553Srgrimes // Note: we don't update the def operand yet. That would cause the normal 74329529Scharnier // def-scan to attempt spilling. 7441553Srgrimes } else if (MO.getSubReg() && MI->readsVirtualRegister(Reg)) { 7451553Srgrimes DEBUG(dbgs() << "Partial redefine: " << MO << "\n"); 7461553Srgrimes // Reload the register, but don't assign to the operand just yet. 7471553Srgrimes // That would confuse the later phys-def processing pass. 7481553Srgrimes LiveRegMap::iterator LRI = reloadVirtReg(MI, i, Reg, 0); 7491553Srgrimes PartialDefs.push_back(LRI->PhysReg); 7501553Srgrimes } 7511553Srgrimes } 7521553Srgrimes 7531553Srgrimes DEBUG(dbgs() << "Allocating early clobbers.\n"); 75429529Scharnier for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 7551553Srgrimes MachineOperand &MO = MI->getOperand(i); 7561553Srgrimes if (!MO.isReg()) continue; 7571553Srgrimes unsigned Reg = MO.getReg(); 7581553Srgrimes if (!TargetRegisterInfo::isVirtualRegister(Reg)) continue; 7591553Srgrimes if (!MO.isEarlyClobber()) 7601553Srgrimes continue; 7611553Srgrimes // Note: defineVirtReg may invalidate MO. 7621553Srgrimes LiveRegMap::iterator LRI = defineVirtReg(MI, i, Reg, 0); 7631553Srgrimes unsigned PhysReg = LRI->PhysReg; 7641553Srgrimes if (setPhysReg(MI, i, PhysReg)) 7651553Srgrimes VirtDead.push_back(Reg); 7661553Srgrimes } 7671553Srgrimes 7681553Srgrimes // Restore UsedInInstr to a state usable for allocating normal virtual uses. 7691553Srgrimes UsedInInstr.clear(); 7701553Srgrimes for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 771 MachineOperand &MO = MI->getOperand(i); 772 if (!MO.isReg() || (MO.isDef() && !MO.isEarlyClobber())) continue; 773 unsigned Reg = MO.getReg(); 774 if (!Reg || !TargetRegisterInfo::isPhysicalRegister(Reg)) continue; 775 DEBUG(dbgs() << "\tSetting " << PrintReg(Reg, TRI) 776 << " as used in instr\n"); 777 markRegUsedInInstr(Reg); 778 } 779 780 // Also mark PartialDefs as used to avoid reallocation. 781 for (unsigned i = 0, e = PartialDefs.size(); i != e; ++i) 782 markRegUsedInInstr(PartialDefs[i]); 783} 784 785void RAFast::AllocateBasicBlock() { 786 DEBUG(dbgs() << "\nAllocating " << *MBB); 787 788 PhysRegState.assign(TRI->getNumRegs(), regDisabled); 789 assert(LiveVirtRegs.empty() && "Mapping not cleared from last block?"); 790 791 MachineBasicBlock::iterator MII = MBB->begin(); 792 793 // Add live-in registers as live. 794 for (MachineBasicBlock::livein_iterator I = MBB->livein_begin(), 795 E = MBB->livein_end(); I != E; ++I) 796 if (MRI->isAllocatable(*I)) 797 definePhysReg(MII, *I, regReserved); 798 799 SmallVector<unsigned, 8> VirtDead; 800 SmallVector<MachineInstr*, 32> Coalesced; 801 802 // Otherwise, sequentially allocate each instruction in the MBB. 803 while (MII != MBB->end()) { 804 MachineInstr *MI = MII++; 805 const MCInstrDesc &MCID = MI->getDesc(); 806 DEBUG({ 807 dbgs() << "\n>> " << *MI << "Regs:"; 808 for (unsigned Reg = 1, E = TRI->getNumRegs(); Reg != E; ++Reg) { 809 if (PhysRegState[Reg] == regDisabled) continue; 810 dbgs() << " " << TRI->getName(Reg); 811 switch(PhysRegState[Reg]) { 812 case regFree: 813 break; 814 case regReserved: 815 dbgs() << "*"; 816 break; 817 default: { 818 dbgs() << '=' << PrintReg(PhysRegState[Reg]); 819 LiveRegMap::iterator I = findLiveVirtReg(PhysRegState[Reg]); 820 assert(I != LiveVirtRegs.end() && "Missing VirtReg entry"); 821 if (I->Dirty) 822 dbgs() << "*"; 823 assert(I->PhysReg == Reg && "Bad inverse map"); 824 break; 825 } 826 } 827 } 828 dbgs() << '\n'; 829 // Check that LiveVirtRegs is the inverse. 830 for (LiveRegMap::iterator i = LiveVirtRegs.begin(), 831 e = LiveVirtRegs.end(); i != e; ++i) { 832 assert(TargetRegisterInfo::isVirtualRegister(i->VirtReg) && 833 "Bad map key"); 834 assert(TargetRegisterInfo::isPhysicalRegister(i->PhysReg) && 835 "Bad map value"); 836 assert(PhysRegState[i->PhysReg] == i->VirtReg && "Bad inverse map"); 837 } 838 }); 839 840 // Debug values are not allowed to change codegen in any way. 841 if (MI->isDebugValue()) { 842 bool ScanDbgValue = true; 843 while (ScanDbgValue) { 844 ScanDbgValue = false; 845 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 846 MachineOperand &MO = MI->getOperand(i); 847 if (!MO.isReg()) continue; 848 unsigned Reg = MO.getReg(); 849 if (!TargetRegisterInfo::isVirtualRegister(Reg)) continue; 850 LiveRegMap::iterator LRI = findLiveVirtReg(Reg); 851 if (LRI != LiveVirtRegs.end()) 852 setPhysReg(MI, i, LRI->PhysReg); 853 else { 854 int SS = StackSlotForVirtReg[Reg]; 855 if (SS == -1) { 856 // We can't allocate a physreg for a DebugValue, sorry! 857 DEBUG(dbgs() << "Unable to allocate vreg used by DBG_VALUE"); 858 MO.setReg(0); 859 } 860 else { 861 // Modify DBG_VALUE now that the value is in a spill slot. 862 bool IsIndirect = MI->isIndirectDebugValue(); 863 uint64_t Offset = IsIndirect ? MI->getOperand(1).getImm() : 0; 864 const MDNode *MDPtr = 865 MI->getOperand(MI->getNumOperands()-1).getMetadata(); 866 DebugLoc DL = MI->getDebugLoc(); 867 MachineBasicBlock *MBB = MI->getParent(); 868 MachineInstr *NewDV = BuildMI(*MBB, MBB->erase(MI), DL, 869 TII->get(TargetOpcode::DBG_VALUE)) 870 .addFrameIndex(SS).addImm(Offset).addMetadata(MDPtr); 871 DEBUG(dbgs() << "Modifying debug info due to spill:" 872 << "\t" << *NewDV); 873 // Scan NewDV operands from the beginning. 874 MI = NewDV; 875 ScanDbgValue = true; 876 break; 877 } 878 } 879 LiveDbgValueMap[Reg].push_back(MI); 880 } 881 } 882 // Next instruction. 883 continue; 884 } 885 886 // If this is a copy, we may be able to coalesce. 887 unsigned CopySrc = 0, CopyDst = 0, CopySrcSub = 0, CopyDstSub = 0; 888 if (MI->isCopy()) { 889 CopyDst = MI->getOperand(0).getReg(); 890 CopySrc = MI->getOperand(1).getReg(); 891 CopyDstSub = MI->getOperand(0).getSubReg(); 892 CopySrcSub = MI->getOperand(1).getSubReg(); 893 } 894 895 // Track registers used by instruction. 896 UsedInInstr.clear(); 897 898 // First scan. 899 // Mark physreg uses and early clobbers as used. 900 // Find the end of the virtreg operands 901 unsigned VirtOpEnd = 0; 902 bool hasTiedOps = false; 903 bool hasEarlyClobbers = false; 904 bool hasPartialRedefs = false; 905 bool hasPhysDefs = false; 906 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 907 MachineOperand &MO = MI->getOperand(i); 908 // Make sure MRI knows about registers clobbered by regmasks. 909 if (MO.isRegMask()) { 910 MRI->addPhysRegsUsedFromRegMask(MO.getRegMask()); 911 continue; 912 } 913 if (!MO.isReg()) continue; 914 unsigned Reg = MO.getReg(); 915 if (!Reg) continue; 916 if (TargetRegisterInfo::isVirtualRegister(Reg)) { 917 VirtOpEnd = i+1; 918 if (MO.isUse()) { 919 hasTiedOps = hasTiedOps || 920 MCID.getOperandConstraint(i, MCOI::TIED_TO) != -1; 921 } else { 922 if (MO.isEarlyClobber()) 923 hasEarlyClobbers = true; 924 if (MO.getSubReg() && MI->readsVirtualRegister(Reg)) 925 hasPartialRedefs = true; 926 } 927 continue; 928 } 929 if (!MRI->isAllocatable(Reg)) continue; 930 if (MO.isUse()) { 931 usePhysReg(MO); 932 } else if (MO.isEarlyClobber()) { 933 definePhysReg(MI, Reg, (MO.isImplicit() || MO.isDead()) ? 934 regFree : regReserved); 935 hasEarlyClobbers = true; 936 } else 937 hasPhysDefs = true; 938 } 939 940 // The instruction may have virtual register operands that must be allocated 941 // the same register at use-time and def-time: early clobbers and tied 942 // operands. If there are also physical defs, these registers must avoid 943 // both physical defs and uses, making them more constrained than normal 944 // operands. 945 // Similarly, if there are multiple defs and tied operands, we must make 946 // sure the same register is allocated to uses and defs. 947 // We didn't detect inline asm tied operands above, so just make this extra 948 // pass for all inline asm. 949 if (MI->isInlineAsm() || hasEarlyClobbers || hasPartialRedefs || 950 (hasTiedOps && (hasPhysDefs || MCID.getNumDefs() > 1))) { 951 handleThroughOperands(MI, VirtDead); 952 // Don't attempt coalescing when we have funny stuff going on. 953 CopyDst = 0; 954 // Pretend we have early clobbers so the use operands get marked below. 955 // This is not necessary for the common case of a single tied use. 956 hasEarlyClobbers = true; 957 } 958 959 // Second scan. 960 // Allocate virtreg uses. 961 for (unsigned i = 0; i != VirtOpEnd; ++i) { 962 MachineOperand &MO = MI->getOperand(i); 963 if (!MO.isReg()) continue; 964 unsigned Reg = MO.getReg(); 965 if (!TargetRegisterInfo::isVirtualRegister(Reg)) continue; 966 if (MO.isUse()) { 967 LiveRegMap::iterator LRI = reloadVirtReg(MI, i, Reg, CopyDst); 968 unsigned PhysReg = LRI->PhysReg; 969 CopySrc = (CopySrc == Reg || CopySrc == PhysReg) ? PhysReg : 0; 970 if (setPhysReg(MI, i, PhysReg)) 971 killVirtReg(LRI); 972 } 973 } 974 975 for (UsedInInstrSet::iterator 976 I = UsedInInstr.begin(), E = UsedInInstr.end(); I != E; ++I) 977 MRI->setRegUnitUsed(*I); 978 979 // Track registers defined by instruction - early clobbers and tied uses at 980 // this point. 981 UsedInInstr.clear(); 982 if (hasEarlyClobbers) { 983 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 984 MachineOperand &MO = MI->getOperand(i); 985 if (!MO.isReg()) continue; 986 unsigned Reg = MO.getReg(); 987 if (!Reg || !TargetRegisterInfo::isPhysicalRegister(Reg)) continue; 988 // Look for physreg defs and tied uses. 989 if (!MO.isDef() && !MI->isRegTiedToDefOperand(i)) continue; 990 markRegUsedInInstr(Reg); 991 } 992 } 993 994 unsigned DefOpEnd = MI->getNumOperands(); 995 if (MI->isCall()) { 996 // Spill all virtregs before a call. This serves two purposes: 1. If an 997 // exception is thrown, the landing pad is going to expect to find 998 // registers in their spill slots, and 2. we don't have to wade through 999 // all the <imp-def> operands on the call instruction. 1000 DefOpEnd = VirtOpEnd; 1001 DEBUG(dbgs() << " Spilling remaining registers before call.\n"); 1002 spillAll(MI); 1003 1004 // The imp-defs are skipped below, but we still need to mark those 1005 // registers as used by the function. 1006 SkippedInstrs.insert(&MCID); 1007 } 1008 1009 // Third scan. 1010 // Allocate defs and collect dead defs. 1011 for (unsigned i = 0; i != DefOpEnd; ++i) { 1012 MachineOperand &MO = MI->getOperand(i); 1013 if (!MO.isReg() || !MO.isDef() || !MO.getReg() || MO.isEarlyClobber()) 1014 continue; 1015 unsigned Reg = MO.getReg(); 1016 1017 if (TargetRegisterInfo::isPhysicalRegister(Reg)) { 1018 if (!MRI->isAllocatable(Reg)) continue; 1019 definePhysReg(MI, Reg, (MO.isImplicit() || MO.isDead()) ? 1020 regFree : regReserved); 1021 continue; 1022 } 1023 LiveRegMap::iterator LRI = defineVirtReg(MI, i, Reg, CopySrc); 1024 unsigned PhysReg = LRI->PhysReg; 1025 if (setPhysReg(MI, i, PhysReg)) { 1026 VirtDead.push_back(Reg); 1027 CopyDst = 0; // cancel coalescing; 1028 } else 1029 CopyDst = (CopyDst == Reg || CopyDst == PhysReg) ? PhysReg : 0; 1030 } 1031 1032 // Kill dead defs after the scan to ensure that multiple defs of the same 1033 // register are allocated identically. We didn't need to do this for uses 1034 // because we are crerating our own kill flags, and they are always at the 1035 // last use. 1036 for (unsigned i = 0, e = VirtDead.size(); i != e; ++i) 1037 killVirtReg(VirtDead[i]); 1038 VirtDead.clear(); 1039 1040 for (UsedInInstrSet::iterator 1041 I = UsedInInstr.begin(), E = UsedInInstr.end(); I != E; ++I) 1042 MRI->setRegUnitUsed(*I); 1043 1044 if (CopyDst && CopyDst == CopySrc && CopyDstSub == CopySrcSub) { 1045 DEBUG(dbgs() << "-- coalescing: " << *MI); 1046 Coalesced.push_back(MI); 1047 } else { 1048 DEBUG(dbgs() << "<< " << *MI); 1049 } 1050 } 1051 1052 // Spill all physical registers holding virtual registers now. 1053 DEBUG(dbgs() << "Spilling live registers at end of block.\n"); 1054 spillAll(MBB->getFirstTerminator()); 1055 1056 // Erase all the coalesced copies. We are delaying it until now because 1057 // LiveVirtRegs might refer to the instrs. 1058 for (unsigned i = 0, e = Coalesced.size(); i != e; ++i) 1059 MBB->erase(Coalesced[i]); 1060 NumCopies += Coalesced.size(); 1061 1062 DEBUG(MBB->dump()); 1063} 1064 1065/// runOnMachineFunction - Register allocate the whole function 1066/// 1067bool RAFast::runOnMachineFunction(MachineFunction &Fn) { 1068 DEBUG(dbgs() << "********** FAST REGISTER ALLOCATION **********\n" 1069 << "********** Function: " << Fn.getName() << '\n'); 1070 MF = &Fn; 1071 MRI = &MF->getRegInfo(); 1072 TM = &Fn.getTarget(); 1073 TRI = TM->getRegisterInfo(); 1074 TII = TM->getInstrInfo(); 1075 MRI->freezeReservedRegs(Fn); 1076 RegClassInfo.runOnMachineFunction(Fn); 1077 UsedInInstr.clear(); 1078 UsedInInstr.setUniverse(TRI->getNumRegUnits()); 1079 1080 assert(!MRI->isSSA() && "regalloc requires leaving SSA"); 1081 1082 // initialize the virtual->physical register map to have a 'null' 1083 // mapping for all virtual registers 1084 StackSlotForVirtReg.resize(MRI->getNumVirtRegs()); 1085 LiveVirtRegs.setUniverse(MRI->getNumVirtRegs()); 1086 1087 // Loop over all of the basic blocks, eliminating virtual register references 1088 for (MachineFunction::iterator MBBi = Fn.begin(), MBBe = Fn.end(); 1089 MBBi != MBBe; ++MBBi) { 1090 MBB = &*MBBi; 1091 AllocateBasicBlock(); 1092 } 1093 1094 // Add the clobber lists for all the instructions we skipped earlier. 1095 for (SmallPtrSet<const MCInstrDesc*, 4>::const_iterator 1096 I = SkippedInstrs.begin(), E = SkippedInstrs.end(); I != E; ++I) 1097 if (const uint16_t *Defs = (*I)->getImplicitDefs()) 1098 while (*Defs) 1099 MRI->setPhysRegUsed(*Defs++); 1100 1101 // All machine operands and other references to virtual registers have been 1102 // replaced. Remove the virtual registers. 1103 MRI->clearVirtRegs(); 1104 1105 SkippedInstrs.clear(); 1106 StackSlotForVirtReg.clear(); 1107 LiveDbgValueMap.clear(); 1108 return true; 1109} 1110 1111FunctionPass *llvm::createFastRegisterAllocator() { 1112 return new RAFast(); 1113} 1114