RegAllocFast.cpp revision 273f7e42994a5bce0614d04d96dbfdf05fd652e5
100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen//===-- RegAllocFast.cpp - A fast register allocator for debug code -------===// 200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen// 300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen// The LLVM Compiler Infrastructure 400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen// 500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen// This file is distributed under the University of Illinois Open Source 600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen// License. See LICENSE.TXT for details. 700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen// 800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen//===----------------------------------------------------------------------===// 900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen// 1000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen// This register allocator allocates registers to a basic block at a time, 1100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen// attempting to keep values in registers and reusing registers as appropriate. 1200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen// 1300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen//===----------------------------------------------------------------------===// 1400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 1500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#define DEBUG_TYPE "regalloc" 1600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include "llvm/BasicBlock.h" 1700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include "llvm/CodeGen/MachineFunctionPass.h" 1800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include "llvm/CodeGen/MachineInstr.h" 1900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include "llvm/CodeGen/MachineFrameInfo.h" 2000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include "llvm/CodeGen/MachineRegisterInfo.h" 2100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include "llvm/CodeGen/Passes.h" 2200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include "llvm/CodeGen/RegAllocRegistry.h" 2300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include "llvm/Target/TargetInstrInfo.h" 2400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include "llvm/Target/TargetMachine.h" 2500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include "llvm/Support/CommandLine.h" 2600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include "llvm/Support/Debug.h" 2700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include "llvm/Support/ErrorHandling.h" 2800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include "llvm/Support/raw_ostream.h" 2900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include "llvm/ADT/DenseMap.h" 3000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include "llvm/ADT/IndexedMap.h" 3100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include "llvm/ADT/SmallSet.h" 3200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include "llvm/ADT/SmallVector.h" 3300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include "llvm/ADT/Statistic.h" 3400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include "llvm/ADT/STLExtras.h" 3500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include <algorithm> 3600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesenusing namespace llvm; 3700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 3800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund OlesenSTATISTIC(NumStores, "Number of stores added"); 3900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund OlesenSTATISTIC(NumLoads , "Number of loads added"); 408a65c510a4fa1245d101da6318618d025702028cJakob Stoklund OlesenSTATISTIC(NumCopies, "Number of copies coalesced"); 4100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 4200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesenstatic RegisterRegAlloc 4300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen fastRegAlloc("fast", "fast register allocator", createFastRegisterAllocator); 4400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 4500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesennamespace { 4600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen class RAFast : public MachineFunctionPass { 4700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen public: 4800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen static char ID; 497d4f25904de543b039a28eddbea3034a5d80e7f8Jakob Stoklund Olesen RAFast() : MachineFunctionPass(&ID), StackSlotForVirtReg(-1), 50e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen isBulkSpilling(false) {} 5100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen private: 5200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen const TargetMachine *TM; 5300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen MachineFunction *MF; 544bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen MachineRegisterInfo *MRI; 5500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen const TargetRegisterInfo *TRI; 5600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen const TargetInstrInfo *TII; 5700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 586fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen // Basic block currently being allocated. 596fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen MachineBasicBlock *MBB; 606fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen 6100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen // StackSlotForVirtReg - Maps virtual regs to the frame index where these 6200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen // values are spilled. 6300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen IndexedMap<int, VirtReg2IndexFunctor> StackSlotForVirtReg; 6400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 6576b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen // Everything we know about a live virtual register. 6676b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen struct LiveReg { 67210e2afcc74e8ce5102d13939b23040fafa71c09Jakob Stoklund Olesen MachineInstr *LastUse; // Last instr to use reg. 68210e2afcc74e8ce5102d13939b23040fafa71c09Jakob Stoklund Olesen unsigned PhysReg; // Currently held here. 69210e2afcc74e8ce5102d13939b23040fafa71c09Jakob Stoklund Olesen unsigned short LastOpNum; // OpNum on LastUse. 70210e2afcc74e8ce5102d13939b23040fafa71c09Jakob Stoklund Olesen bool Dirty; // Register needs spill. 7176b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen 72210e2afcc74e8ce5102d13939b23040fafa71c09Jakob Stoklund Olesen LiveReg(unsigned p=0) : LastUse(0), PhysReg(p), LastOpNum(0), 7301dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen Dirty(false) {} 7476b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen }; 7576b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen 7676b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen typedef DenseMap<unsigned, LiveReg> LiveRegMap; 7701dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen typedef LiveRegMap::value_type LiveRegEntry; 7876b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen 7976b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen // LiveVirtRegs - This map contains entries for each virtual register 8000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen // that is currently available in a physical register. 8176b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen LiveRegMap LiveVirtRegs; 8200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 83bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // RegState - Track the state of a physical register. 84bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen enum RegState { 85bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // A disabled register is not available for allocation, but an alias may 86bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // be in use. A register can only be moved out of the disabled state if 87bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // all aliases are disabled. 88bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen regDisabled, 89bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen 90bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // A free register is not currently in use and can be allocated 91bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // immediately without checking aliases. 92bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen regFree, 93bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen 94bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // A reserved register has been assigned expolicitly (e.g., setting up a 95bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // call parameter), and it remains reserved until it is used. 96bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen regReserved 9700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 98bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // A register state may also be a virtual register number, indication that 99bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // the physical register is currently allocated to a virtual register. In 10076b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen // that case, LiveVirtRegs contains the inverse mapping. 101bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen }; 102bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen 103bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // PhysRegState - One of the RegState enums, or a virtreg. 104bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen std::vector<unsigned> PhysRegState; 10500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 10600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen // UsedInInstr - BitVector of physregs that are used in the current 10700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen // instruction, and so cannot be allocated. 10800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen BitVector UsedInInstr; 10900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 110efa155fd6e3820495205a09f8b9f20390d126153Jakob Stoklund Olesen // Allocatable - vector of allocatable physical registers. 111efa155fd6e3820495205a09f8b9f20390d126153Jakob Stoklund Olesen BitVector Allocatable; 11200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 1136de07178e1e6445080bf4f7704e274c5f219ff70Jakob Stoklund Olesen // SkippedInstrs - Descriptors of instructions whose clobber list was ignored 1146de07178e1e6445080bf4f7704e274c5f219ff70Jakob Stoklund Olesen // because all registers were spilled. It is still necessary to mark all the 1156de07178e1e6445080bf4f7704e274c5f219ff70Jakob Stoklund Olesen // clobbered registers as used by the function. 1166de07178e1e6445080bf4f7704e274c5f219ff70Jakob Stoklund Olesen SmallPtrSet<const TargetInstrDesc*, 4> SkippedInstrs; 1176de07178e1e6445080bf4f7704e274c5f219ff70Jakob Stoklund Olesen 118e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen // isBulkSpilling - This flag is set when LiveRegMap will be cleared 119e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen // completely after spilling all live registers. LiveRegMap entries should 120e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen // not be erased. 121e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen bool isBulkSpilling; 1227d4f25904de543b039a28eddbea3034a5d80e7f8Jakob Stoklund Olesen 123548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen enum { 124548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen spillClean = 1, 125548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen spillDirty = 100, 126548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen spillImpossible = ~0u 127548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen }; 12800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen public: 12900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen virtual const char *getPassName() const { 13000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen return "Fast Register Allocator"; 13100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 13200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 13300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen virtual void getAnalysisUsage(AnalysisUsage &AU) const { 13400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen AU.setPreservesCFG(); 13500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen AU.addRequiredID(PHIEliminationID); 13600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen AU.addRequiredID(TwoAddressInstructionPassID); 13700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen MachineFunctionPass::getAnalysisUsage(AU); 13800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 13900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 14000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen private: 14100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen bool runOnMachineFunction(MachineFunction &Fn); 1426fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen void AllocateBasicBlock(); 143d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen void handleThroughOperands(MachineInstr *MI, 144d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen SmallVectorImpl<unsigned> &VirtDead); 14500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen int getStackSpaceFor(unsigned VirtReg, const TargetRegisterClass *RC); 1461e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen bool isLastUseOfLocalReg(MachineOperand&); 1471e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen 14801dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen void addKillFlag(const LiveReg&); 149844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen void killVirtReg(LiveRegMap::iterator); 150804291e31658d46fb1db5ecaf42b31950c02a6f2Jakob Stoklund Olesen void killVirtReg(unsigned VirtReg); 151844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen void spillVirtReg(MachineBasicBlock::iterator MI, LiveRegMap::iterator); 152e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen void spillVirtReg(MachineBasicBlock::iterator MI, unsigned VirtReg); 1534ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen 1544ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen void usePhysReg(MachineOperand&); 1556fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen void definePhysReg(MachineInstr *MI, unsigned PhysReg, RegState NewState); 156548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen unsigned calcSpillCost(unsigned PhysReg) const; 15701dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen void assignVirtToPhysReg(LiveRegEntry &LRE, unsigned PhysReg); 15801dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen void allocVirtReg(MachineInstr *MI, LiveRegEntry &LRE, unsigned Hint); 159646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund Olesen LiveRegMap::iterator defineVirtReg(MachineInstr *MI, unsigned OpNum, 160646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund Olesen unsigned VirtReg, unsigned Hint); 161646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund Olesen LiveRegMap::iterator reloadVirtReg(MachineInstr *MI, unsigned OpNum, 162646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund Olesen unsigned VirtReg, unsigned Hint); 1636fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen void spillAll(MachineInstr *MI); 1640eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen bool setPhysReg(MachineInstr *MI, unsigned OpNum, unsigned PhysReg); 16500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen }; 16600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen char RAFast::ID = 0; 16700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 16800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 16900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen/// getStackSpaceFor - This allocates space for the specified virtual register 17000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen/// to be held on the stack. 17100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesenint RAFast::getStackSpaceFor(unsigned VirtReg, const TargetRegisterClass *RC) { 17200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen // Find the location Reg would belong... 17300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen int SS = StackSlotForVirtReg[VirtReg]; 17400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen if (SS != -1) 17500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen return SS; // Already has space allocated? 17600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 17700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen // Allocate a new stack object for this spill location... 17800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen int FrameIdx = MF->getFrameInfo()->CreateSpillStackObject(RC->getSize(), 17900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen RC->getAlignment()); 18000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 18100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen // Assign the slot. 18200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen StackSlotForVirtReg[VirtReg] = FrameIdx; 18300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen return FrameIdx; 18400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 18500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 1861e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen/// isLastUseOfLocalReg - Return true if MO is the only remaining reference to 1871e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen/// its virtual register, and it is guaranteed to be a block-local register. 1881e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen/// 1891e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesenbool RAFast::isLastUseOfLocalReg(MachineOperand &MO) { 1901e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen // Check for non-debug uses or defs following MO. 1911e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen // This is the most likely way to fail - fast path it. 192844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen MachineOperand *Next = &MO; 193844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen while ((Next = Next->getNextOperandForReg())) 194844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen if (!Next->isDebug()) 1951e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen return false; 1961e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen 1971e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen // If the register has ever been spilled or reloaded, we conservatively assume 1981e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen // it is a global register used in multiple blocks. 1991e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen if (StackSlotForVirtReg[MO.getReg()] != -1) 2001e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen return false; 2011e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen 2021e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen // Check that the use/def chain has exactly one operand - MO. 2031e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen return &MRI->reg_nodbg_begin(MO.getReg()).getOperand() == &MO; 2041e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen} 2051e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen 206804291e31658d46fb1db5ecaf42b31950c02a6f2Jakob Stoklund Olesen/// addKillFlag - Set kill flags on last use of a virtual register. 20701dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesenvoid RAFast::addKillFlag(const LiveReg &LR) { 20801dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen if (!LR.LastUse) return; 20901dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen MachineOperand &MO = LR.LastUse->getOperand(LR.LastOpNum); 210d32e735ae6e3fbebcae9a23d7cda091770bb3a14Jakob Stoklund Olesen if (MO.isUse() && !LR.LastUse->isRegTiedToDefOperand(LR.LastOpNum)) { 211d32e735ae6e3fbebcae9a23d7cda091770bb3a14Jakob Stoklund Olesen if (MO.getReg() == LR.PhysReg) 2120eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen MO.setIsKill(); 2130eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen else 2140eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen LR.LastUse->addRegisterKilled(LR.PhysReg, TRI, true); 2150eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen } 216804291e31658d46fb1db5ecaf42b31950c02a6f2Jakob Stoklund Olesen} 217804291e31658d46fb1db5ecaf42b31950c02a6f2Jakob Stoklund Olesen 218804291e31658d46fb1db5ecaf42b31950c02a6f2Jakob Stoklund Olesen/// killVirtReg - Mark virtreg as no longer available. 219844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesenvoid RAFast::killVirtReg(LiveRegMap::iterator LRI) { 220844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen addKillFlag(LRI->second); 221844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen const LiveReg &LR = LRI->second; 222844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen assert(PhysRegState[LR.PhysReg] == LRI->first && "Broken RegState mapping"); 223804291e31658d46fb1db5ecaf42b31950c02a6f2Jakob Stoklund Olesen PhysRegState[LR.PhysReg] = regFree; 224e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen // Erase from LiveVirtRegs unless we're spilling in bulk. 225e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen if (!isBulkSpilling) 226844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen LiveVirtRegs.erase(LRI); 22776b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen} 22876b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen 22976b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen/// killVirtReg - Mark virtreg as no longer available. 230bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesenvoid RAFast::killVirtReg(unsigned VirtReg) { 231bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen assert(TargetRegisterInfo::isVirtualRegister(VirtReg) && 232bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen "killVirtReg needs a virtual register"); 233844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen LiveRegMap::iterator LRI = LiveVirtRegs.find(VirtReg); 234844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen if (LRI != LiveVirtRegs.end()) 235844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen killVirtReg(LRI); 23600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 23700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 238bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen/// spillVirtReg - This method spills the value specified by VirtReg into the 239bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen/// corresponding stack slot if needed. If isKill is set, the register is also 240bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen/// killed. 241e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesenvoid RAFast::spillVirtReg(MachineBasicBlock::iterator MI, unsigned VirtReg) { 242bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen assert(TargetRegisterInfo::isVirtualRegister(VirtReg) && 243bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen "Spilling a physical register is illegal!"); 244844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen LiveRegMap::iterator LRI = LiveVirtRegs.find(VirtReg); 245844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen assert(LRI != LiveVirtRegs.end() && "Spilling unmapped virtual register"); 246844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen spillVirtReg(MI, LRI); 2477d4f25904de543b039a28eddbea3034a5d80e7f8Jakob Stoklund Olesen} 2487d4f25904de543b039a28eddbea3034a5d80e7f8Jakob Stoklund Olesen 2497d4f25904de543b039a28eddbea3034a5d80e7f8Jakob Stoklund Olesen/// spillVirtReg - Do the actual work of spilling. 2506fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesenvoid RAFast::spillVirtReg(MachineBasicBlock::iterator MI, 251844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen LiveRegMap::iterator LRI) { 252844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen LiveReg &LR = LRI->second; 253844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen assert(PhysRegState[LR.PhysReg] == LRI->first && "Broken RegState mapping"); 25476b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen 255210e2afcc74e8ce5102d13939b23040fafa71c09Jakob Stoklund Olesen if (LR.Dirty) { 256e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen // If this physreg is used by the instruction, we want to kill it on the 257e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen // instruction, not on the spill. 258844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen bool SpillKill = LR.LastUse != MI; 259210e2afcc74e8ce5102d13939b23040fafa71c09Jakob Stoklund Olesen LR.Dirty = false; 260844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen DEBUG(dbgs() << "Spilling %reg" << LRI->first 2617d4f25904de543b039a28eddbea3034a5d80e7f8Jakob Stoklund Olesen << " in " << TRI->getName(LR.PhysReg)); 262844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen const TargetRegisterClass *RC = MRI->getRegClass(LRI->first); 263844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen int FI = getStackSpaceFor(LRI->first, RC); 2646fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen DEBUG(dbgs() << " to stack slot #" << FI << "\n"); 265844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen TII->storeRegToStackSlot(*MBB, MI, LR.PhysReg, SpillKill, FI, RC, TRI); 26600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen ++NumStores; // Update statistics 26700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 268844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen if (SpillKill) 269210e2afcc74e8ce5102d13939b23040fafa71c09Jakob Stoklund Olesen LR.LastUse = 0; // Don't kill register again 270bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 271844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen killVirtReg(LRI); 27200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 27300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 274bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen/// spillAll - Spill all dirty virtregs without killing them. 2756fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesenvoid RAFast::spillAll(MachineInstr *MI) { 276f3ea06b108d45c53dade87d6f1f48ac0a0e20562Jakob Stoklund Olesen if (LiveVirtRegs.empty()) return; 277e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen isBulkSpilling = true; 2782997985b4cafc2a1e562819a2f3e0c6abe5fb223Jakob Stoklund Olesen // The LiveRegMap is keyed by an unsigned (the virtreg number), so the order 2792997985b4cafc2a1e562819a2f3e0c6abe5fb223Jakob Stoklund Olesen // of spilling here is deterministic, if arbitrary. 2802997985b4cafc2a1e562819a2f3e0c6abe5fb223Jakob Stoklund Olesen for (LiveRegMap::iterator i = LiveVirtRegs.begin(), e = LiveVirtRegs.end(); 2812997985b4cafc2a1e562819a2f3e0c6abe5fb223Jakob Stoklund Olesen i != e; ++i) 282e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen spillVirtReg(MI, i); 283e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen LiveVirtRegs.clear(); 284e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen isBulkSpilling = false; 285bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen} 28600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 2874ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen/// usePhysReg - Handle the direct use of a physical register. 2884ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen/// Check that the register is not used by a virtreg. 2894ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen/// Kill the physreg, marking it free. 2904ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen/// This may add implicit kills to MO->getParent() and invalidate MO. 2914ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesenvoid RAFast::usePhysReg(MachineOperand &MO) { 2924ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen unsigned PhysReg = MO.getReg(); 2934ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen assert(TargetRegisterInfo::isPhysicalRegister(PhysReg) && 2944ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen "Bad usePhysReg operand"); 2954ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen 2964ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen switch (PhysRegState[PhysReg]) { 297bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regDisabled: 298bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 299bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regReserved: 300bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen PhysRegState[PhysReg] = regFree; 3014ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen // Fall through 3024ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen case regFree: 3034ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen UsedInInstr.set(PhysReg); 3044ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen MO.setIsKill(); 305bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen return; 306bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen default: 3074ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen // The physreg was allocated to a virtual register. That means to value we 3084ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen // wanted has been clobbered. 3094ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen llvm_unreachable("Instruction uses an allocated register"); 31000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 31100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 3124ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen // Maybe a superregister is reserved? 313bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen for (const unsigned *AS = TRI->getAliasSet(PhysReg); 314bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned Alias = *AS; ++AS) { 3154ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen switch (PhysRegState[Alias]) { 316bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regDisabled: 317bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 318bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regReserved: 3194ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen assert(TRI->isSuperRegister(PhysReg, Alias) && 3204ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen "Instruction is not using a subregister of a reserved register"); 3214ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen // Leave the superregister in the working set. 322bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen PhysRegState[Alias] = regFree; 3234ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen UsedInInstr.set(Alias); 3244ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen MO.getParent()->addRegisterKilled(Alias, TRI, true); 3254ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen return; 3264ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen case regFree: 3274ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen if (TRI->isSuperRegister(PhysReg, Alias)) { 3284ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen // Leave the superregister in the working set. 3294ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen UsedInInstr.set(Alias); 3304ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen MO.getParent()->addRegisterKilled(Alias, TRI, true); 3314ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen return; 3324ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen } 3334ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen // Some other alias was in the working set - clear it. 3344ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen PhysRegState[Alias] = regDisabled; 335bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 336bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen default: 3374ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen llvm_unreachable("Instruction uses an alias of an allocated register"); 338bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 33900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 3404ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen 3414ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen // All aliases are disabled, bring register into working set. 3424ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen PhysRegState[PhysReg] = regFree; 3434ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen UsedInInstr.set(PhysReg); 3444ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen MO.setIsKill(); 34500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 34600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 3474ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen/// definePhysReg - Mark PhysReg as reserved or free after spilling any 3484ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen/// virtregs. This is very similar to defineVirtReg except the physreg is 3494ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen/// reserved instead of allocated. 3506fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesenvoid RAFast::definePhysReg(MachineInstr *MI, unsigned PhysReg, 3516fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen RegState NewState) { 3524ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen UsedInInstr.set(PhysReg); 353bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen switch (unsigned VirtReg = PhysRegState[PhysReg]) { 354bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regDisabled: 355bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 3564ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen default: 357e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen spillVirtReg(MI, VirtReg); 3584ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen // Fall through. 359bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regFree: 360bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regReserved: 3614ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen PhysRegState[PhysReg] = NewState; 362bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen return; 363bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 364bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen 3654ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen // This is a disabled register, disable all aliases. 3664ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen PhysRegState[PhysReg] = NewState; 367bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen for (const unsigned *AS = TRI->getAliasSet(PhysReg); 368bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned Alias = *AS; ++AS) { 3694ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen UsedInInstr.set(Alias); 370bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen switch (unsigned VirtReg = PhysRegState[Alias]) { 371bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regDisabled: 372bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 373bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen default: 374e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen spillVirtReg(MI, VirtReg); 3754ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen // Fall through. 3764ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen case regFree: 3774ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen case regReserved: 3784ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen PhysRegState[Alias] = regDisabled; 3794ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen if (TRI->isSuperRegister(PhysReg, Alias)) 3804ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen return; 381bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 382bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 383bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 384bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen} 38500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 3864ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen 387548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen// calcSpillCost - Return the cost of spilling clearing out PhysReg and 388548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen// aliases so it is free for allocation. 389548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen// Returns 0 when PhysReg is free or disabled with all aliases disabled - it 390548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen// can be allocated directly. 391548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen// Returns spillImpossible when PhysReg or an alias can't be spilled. 392548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesenunsigned RAFast::calcSpillCost(unsigned PhysReg) const { 393b8acb7be804c8c537f2475f3a24303a0b37ab107Jakob Stoklund Olesen if (UsedInInstr.test(PhysReg)) 394b8acb7be804c8c537f2475f3a24303a0b37ab107Jakob Stoklund Olesen return spillImpossible; 395548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen switch (unsigned VirtReg = PhysRegState[PhysReg]) { 396548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen case regDisabled: 397548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen break; 398548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen case regFree: 399548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen return 0; 400548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen case regReserved: 401548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen return spillImpossible; 402548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen default: 403548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen return LiveVirtRegs.lookup(VirtReg).Dirty ? spillDirty : spillClean; 404548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen } 405548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen 406548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen // This is a disabled register, add up const of aliases. 407548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen unsigned Cost = 0; 408548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen for (const unsigned *AS = TRI->getAliasSet(PhysReg); 409548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen unsigned Alias = *AS; ++AS) { 410b8acb7be804c8c537f2475f3a24303a0b37ab107Jakob Stoklund Olesen if (UsedInInstr.test(Alias)) 411b8acb7be804c8c537f2475f3a24303a0b37ab107Jakob Stoklund Olesen return spillImpossible; 412548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen switch (unsigned VirtReg = PhysRegState[Alias]) { 413548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen case regDisabled: 414548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen break; 415548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen case regFree: 416548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen ++Cost; 417548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen break; 418548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen case regReserved: 419548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen return spillImpossible; 420548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen default: 421548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen Cost += LiveVirtRegs.lookup(VirtReg).Dirty ? spillDirty : spillClean; 422548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen break; 423548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen } 424548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen } 425548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen return Cost; 426548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen} 427548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen 428548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen 42900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen/// assignVirtToPhysReg - This method updates local state so that we know 43000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen/// that PhysReg is the proper container for VirtReg now. The physical 43100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen/// register must not be used for anything else when this is called. 43200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen/// 43301dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesenvoid RAFast::assignVirtToPhysReg(LiveRegEntry &LRE, unsigned PhysReg) { 43401dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen DEBUG(dbgs() << "Assigning %reg" << LRE.first << " to " 435bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen << TRI->getName(PhysReg) << "\n"); 43601dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen PhysRegState[PhysReg] = LRE.first; 43701dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen assert(!LRE.second.PhysReg && "Already assigned a physreg"); 43801dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen LRE.second.PhysReg = PhysReg; 43900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 44000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 441bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen/// allocVirtReg - Allocate a physical register for VirtReg. 44201dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesenvoid RAFast::allocVirtReg(MachineInstr *MI, LiveRegEntry &LRE, unsigned Hint) { 44301dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen const unsigned VirtReg = LRE.first; 44401dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen 445bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen assert(TargetRegisterInfo::isVirtualRegister(VirtReg) && 446bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen "Can only allocate virtual registers"); 44700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 4484bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen const TargetRegisterClass *RC = MRI->getRegClass(VirtReg); 449bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen 4504bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen // Ignore invalid hints. 4514bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen if (Hint && (!TargetRegisterInfo::isPhysicalRegister(Hint) || 452b8acb7be804c8c537f2475f3a24303a0b37ab107Jakob Stoklund Olesen !RC->contains(Hint) || !Allocatable.test(Hint))) 4534bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen Hint = 0; 4544bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen 4554bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen // Take hint when possible. 4564bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen if (Hint) { 457548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen switch(calcSpillCost(Hint)) { 4584bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen default: 459548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen definePhysReg(MI, Hint, regFree); 4604bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen // Fall through. 461548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen case 0: 46201dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen return assignVirtToPhysReg(LRE, Hint); 463548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen case spillImpossible: 464548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen break; 4654bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen } 4664bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen } 4674bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen 468548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen TargetRegisterClass::iterator AOB = RC->allocation_order_begin(*MF); 469548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen TargetRegisterClass::iterator AOE = RC->allocation_order_end(*MF); 470548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen 471bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // First try to find a completely free register. 472bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen for (TargetRegisterClass::iterator I = AOB; I != AOE; ++I) { 473bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned PhysReg = *I; 474548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen if (PhysRegState[PhysReg] == regFree && !UsedInInstr.test(PhysReg)) 475548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen return assignVirtToPhysReg(LRE, PhysReg); 476bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 47700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 478c9c4dacd03a4b80d61ed6b9c6ffeb1b1f76b8d1cJakob Stoklund Olesen DEBUG(dbgs() << "Allocating %reg" << VirtReg << " from " << RC->getName() 479548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen << "\n"); 480548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen 481548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen unsigned BestReg = 0, BestCost = spillImpossible; 482548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen for (TargetRegisterClass::iterator I = AOB; I != AOE; ++I) { 483548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen unsigned Cost = calcSpillCost(*I); 484f3ea06b108d45c53dade87d6f1f48ac0a0e20562Jakob Stoklund Olesen // Cost is 0 when all aliases are already disabled. 485f3ea06b108d45c53dade87d6f1f48ac0a0e20562Jakob Stoklund Olesen if (Cost == 0) 486f3ea06b108d45c53dade87d6f1f48ac0a0e20562Jakob Stoklund Olesen return assignVirtToPhysReg(LRE, *I); 487f3ea06b108d45c53dade87d6f1f48ac0a0e20562Jakob Stoklund Olesen if (Cost < BestCost) 488f3ea06b108d45c53dade87d6f1f48ac0a0e20562Jakob Stoklund Olesen BestReg = *I, BestCost = Cost; 48900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 49000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 491bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (BestReg) { 492f3ea06b108d45c53dade87d6f1f48ac0a0e20562Jakob Stoklund Olesen definePhysReg(MI, BestReg, regFree); 49301dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen return assignVirtToPhysReg(LRE, BestReg); 494bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 49500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 496bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Nothing we can do. 497bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen std::string msg; 498bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen raw_string_ostream Msg(msg); 499bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen Msg << "Ran out of registers during register allocation!"; 500bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (MI->isInlineAsm()) { 501bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen Msg << "\nPlease check your inline asm statement for " 502bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen << "invalid constraints:\n"; 503bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen MI->print(Msg, TM); 504bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 505bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen report_fatal_error(Msg.str()); 50600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 50700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 508bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen/// defineVirtReg - Allocate a register for VirtReg and mark it as dirty. 509646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund OlesenRAFast::LiveRegMap::iterator 510646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund OlesenRAFast::defineVirtReg(MachineInstr *MI, unsigned OpNum, 511646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund Olesen unsigned VirtReg, unsigned Hint) { 512bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen assert(TargetRegisterInfo::isVirtualRegister(VirtReg) && 513bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen "Not a virtual register"); 514844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen LiveRegMap::iterator LRI; 51501dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen bool New; 516844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen tie(LRI, New) = LiveVirtRegs.insert(std::make_pair(VirtReg, LiveReg())); 517844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen LiveReg &LR = LRI->second; 5180c9e4f5f3ff139733d74462a0ad5b94014e764a8Jakob Stoklund Olesen if (New) { 5190c9e4f5f3ff139733d74462a0ad5b94014e764a8Jakob Stoklund Olesen // If there is no hint, peek at the only use of this register. 5200c9e4f5f3ff139733d74462a0ad5b94014e764a8Jakob Stoklund Olesen if ((!Hint || !TargetRegisterInfo::isPhysicalRegister(Hint)) && 5210c9e4f5f3ff139733d74462a0ad5b94014e764a8Jakob Stoklund Olesen MRI->hasOneNonDBGUse(VirtReg)) { 522273f7e42994a5bce0614d04d96dbfdf05fd652e5Jakob Stoklund Olesen const MachineInstr &UseMI = *MRI->use_nodbg_begin(VirtReg); 5230c9e4f5f3ff139733d74462a0ad5b94014e764a8Jakob Stoklund Olesen unsigned SrcReg, DstReg, SrcSubReg, DstSubReg; 5240c9e4f5f3ff139733d74462a0ad5b94014e764a8Jakob Stoklund Olesen // It's a copy, use the destination register as a hint. 525273f7e42994a5bce0614d04d96dbfdf05fd652e5Jakob Stoklund Olesen if (UseMI.isCopyLike()) 526273f7e42994a5bce0614d04d96dbfdf05fd652e5Jakob Stoklund Olesen Hint = UseMI.getOperand(0).getReg(); 527273f7e42994a5bce0614d04d96dbfdf05fd652e5Jakob Stoklund Olesen else if (TII->isMoveInstr(UseMI, SrcReg, DstReg, SrcSubReg, DstSubReg)) 5280c9e4f5f3ff139733d74462a0ad5b94014e764a8Jakob Stoklund Olesen Hint = DstReg; 5290c9e4f5f3ff139733d74462a0ad5b94014e764a8Jakob Stoklund Olesen } 530844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen allocVirtReg(MI, *LRI, Hint); 531d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen } else if (LR.LastUse) { 5320eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen // Redefining a live register - kill at the last use, unless it is this 5330eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen // instruction defining VirtReg multiple times. 5340eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen if (LR.LastUse != MI || LR.LastUse->getOperand(LR.LastOpNum).isUse()) 5350eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen addKillFlag(LR); 5360eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen } 53701dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen assert(LR.PhysReg && "Register not assigned"); 538210e2afcc74e8ce5102d13939b23040fafa71c09Jakob Stoklund Olesen LR.LastUse = MI; 539210e2afcc74e8ce5102d13939b23040fafa71c09Jakob Stoklund Olesen LR.LastOpNum = OpNum; 540210e2afcc74e8ce5102d13939b23040fafa71c09Jakob Stoklund Olesen LR.Dirty = true; 541210e2afcc74e8ce5102d13939b23040fafa71c09Jakob Stoklund Olesen UsedInInstr.set(LR.PhysReg); 542646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund Olesen return LRI; 543bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen} 54400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 545bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen/// reloadVirtReg - Make sure VirtReg is available in a physreg and return it. 546646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund OlesenRAFast::LiveRegMap::iterator 547646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund OlesenRAFast::reloadVirtReg(MachineInstr *MI, unsigned OpNum, 548646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund Olesen unsigned VirtReg, unsigned Hint) { 549bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen assert(TargetRegisterInfo::isVirtualRegister(VirtReg) && 550bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen "Not a virtual register"); 551844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen LiveRegMap::iterator LRI; 55201dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen bool New; 553844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen tie(LRI, New) = LiveVirtRegs.insert(std::make_pair(VirtReg, LiveReg())); 554844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen LiveReg &LR = LRI->second; 555ac3e529831877cea609ed668f95b1dc06e34698cJakob Stoklund Olesen MachineOperand &MO = MI->getOperand(OpNum); 55601dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen if (New) { 557844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen allocVirtReg(MI, *LRI, Hint); 5584bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen const TargetRegisterClass *RC = MRI->getRegClass(VirtReg); 559bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen int FrameIndex = getStackSpaceFor(VirtReg, RC); 560c9c4dacd03a4b80d61ed6b9c6ffeb1b1f76b8d1cJakob Stoklund Olesen DEBUG(dbgs() << "Reloading %reg" << VirtReg << " into " 56101dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen << TRI->getName(LR.PhysReg) << "\n"); 56201dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen TII->loadRegFromStackSlot(*MBB, MI, LR.PhysReg, FrameIndex, RC, TRI); 563bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen ++NumLoads; 56401dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen } else if (LR.Dirty) { 5651e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen if (isLastUseOfLocalReg(MO)) { 5661e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen DEBUG(dbgs() << "Killing last use: " << MO << "\n"); 567d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen if (MO.isUse()) 568d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen MO.setIsKill(); 569d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen else 570d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen MO.setIsDead(); 5711e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen } else if (MO.isKill()) { 5721e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen DEBUG(dbgs() << "Clearing dubious kill: " << MO << "\n"); 5731e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen MO.setIsKill(false); 574d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen } else if (MO.isDead()) { 575d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen DEBUG(dbgs() << "Clearing dubious dead: " << MO << "\n"); 576d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen MO.setIsDead(false); 5771e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen } 578ac3e529831877cea609ed668f95b1dc06e34698cJakob Stoklund Olesen } else if (MO.isKill()) { 579ac3e529831877cea609ed668f95b1dc06e34698cJakob Stoklund Olesen // We must remove kill flags from uses of reloaded registers because the 580ac3e529831877cea609ed668f95b1dc06e34698cJakob Stoklund Olesen // register would be killed immediately, and there might be a second use: 581ac3e529831877cea609ed668f95b1dc06e34698cJakob Stoklund Olesen // %foo = OR %x<kill>, %x 582ac3e529831877cea609ed668f95b1dc06e34698cJakob Stoklund Olesen // This would cause a second reload of %x into a different register. 583ac3e529831877cea609ed668f95b1dc06e34698cJakob Stoklund Olesen DEBUG(dbgs() << "Clearing clean kill: " << MO << "\n"); 584ac3e529831877cea609ed668f95b1dc06e34698cJakob Stoklund Olesen MO.setIsKill(false); 585d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen } else if (MO.isDead()) { 586d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen DEBUG(dbgs() << "Clearing clean dead: " << MO << "\n"); 587d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen MO.setIsDead(false); 58800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 58901dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen assert(LR.PhysReg && "Register not assigned"); 590210e2afcc74e8ce5102d13939b23040fafa71c09Jakob Stoklund Olesen LR.LastUse = MI; 591210e2afcc74e8ce5102d13939b23040fafa71c09Jakob Stoklund Olesen LR.LastOpNum = OpNum; 592210e2afcc74e8ce5102d13939b23040fafa71c09Jakob Stoklund Olesen UsedInInstr.set(LR.PhysReg); 593646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund Olesen return LRI; 594bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen} 59500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 5960eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen// setPhysReg - Change operand OpNum in MI the refer the PhysReg, considering 5970eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen// subregs. This may invalidate any operand pointers. 5980eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen// Return true if the operand kills its register. 5990eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesenbool RAFast::setPhysReg(MachineInstr *MI, unsigned OpNum, unsigned PhysReg) { 6000eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen MachineOperand &MO = MI->getOperand(OpNum); 60141e1401de5cb8752fb9d06e65e62bfe97cc1304eJakob Stoklund Olesen if (!MO.getSubReg()) { 602bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen MO.setReg(PhysReg); 60341e1401de5cb8752fb9d06e65e62bfe97cc1304eJakob Stoklund Olesen return MO.isKill() || MO.isDead(); 60441e1401de5cb8752fb9d06e65e62bfe97cc1304eJakob Stoklund Olesen } 60541e1401de5cb8752fb9d06e65e62bfe97cc1304eJakob Stoklund Olesen 60641e1401de5cb8752fb9d06e65e62bfe97cc1304eJakob Stoklund Olesen // Handle subregister index. 60741e1401de5cb8752fb9d06e65e62bfe97cc1304eJakob Stoklund Olesen MO.setReg(PhysReg ? TRI->getSubReg(PhysReg, MO.getSubReg()) : 0); 60841e1401de5cb8752fb9d06e65e62bfe97cc1304eJakob Stoklund Olesen MO.setSubReg(0); 609d32e735ae6e3fbebcae9a23d7cda091770bb3a14Jakob Stoklund Olesen 610d32e735ae6e3fbebcae9a23d7cda091770bb3a14Jakob Stoklund Olesen // A kill flag implies killing the full register. Add corresponding super 611d32e735ae6e3fbebcae9a23d7cda091770bb3a14Jakob Stoklund Olesen // register kill. 612d32e735ae6e3fbebcae9a23d7cda091770bb3a14Jakob Stoklund Olesen if (MO.isKill()) { 613d32e735ae6e3fbebcae9a23d7cda091770bb3a14Jakob Stoklund Olesen MI->addRegisterKilled(PhysReg, TRI, true); 61441e1401de5cb8752fb9d06e65e62bfe97cc1304eJakob Stoklund Olesen return true; 61541e1401de5cb8752fb9d06e65e62bfe97cc1304eJakob Stoklund Olesen } 616d32e735ae6e3fbebcae9a23d7cda091770bb3a14Jakob Stoklund Olesen return MO.isDead(); 61700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 61800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 619d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen// Handle special instruction operand like early clobbers and tied ops when 620d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen// there are additional physreg defines. 621d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesenvoid RAFast::handleThroughOperands(MachineInstr *MI, 622d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen SmallVectorImpl<unsigned> &VirtDead) { 623d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen DEBUG(dbgs() << "Scanning for through registers:"); 624d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen SmallSet<unsigned, 8> ThroughRegs; 625d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 626d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen MachineOperand &MO = MI->getOperand(i); 627d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen if (!MO.isReg()) continue; 628d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen unsigned Reg = MO.getReg(); 629d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen if (!Reg || TargetRegisterInfo::isPhysicalRegister(Reg)) continue; 630d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen if (MO.isEarlyClobber() || MI->isRegTiedToDefOperand(i) || 631d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen (MO.getSubReg() && MI->readsVirtualRegister(Reg))) { 632d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen if (ThroughRegs.insert(Reg)) 633d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen DEBUG(dbgs() << " %reg" << Reg); 634d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen } 635d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen } 636d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen 637d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen // If any physreg defines collide with preallocated through registers, 638d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen // we must spill and reallocate. 639d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen DEBUG(dbgs() << "\nChecking for physdef collisions.\n"); 640d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 641d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen MachineOperand &MO = MI->getOperand(i); 642d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen if (!MO.isReg() || !MO.isDef()) continue; 643d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen unsigned Reg = MO.getReg(); 644d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen if (!Reg || !TargetRegisterInfo::isPhysicalRegister(Reg)) continue; 645d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen UsedInInstr.set(Reg); 646d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen if (ThroughRegs.count(PhysRegState[Reg])) 647d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen definePhysReg(MI, Reg, regFree); 648d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS) { 649d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen UsedInInstr.set(*AS); 650d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen if (ThroughRegs.count(PhysRegState[*AS])) 651d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen definePhysReg(MI, *AS, regFree); 652d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen } 653d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen } 654d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen 655d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen SmallVector<unsigned, 8> PartialDefs; 656d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen DEBUG(dbgs() << "Allocating tied uses and early clobbers.\n"); 657d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 658d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen MachineOperand &MO = MI->getOperand(i); 659d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen if (!MO.isReg()) continue; 660d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen unsigned Reg = MO.getReg(); 661d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen if (!Reg || TargetRegisterInfo::isPhysicalRegister(Reg)) continue; 662d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen if (MO.isUse()) { 663d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen unsigned DefIdx = 0; 664d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen if (!MI->isRegTiedToDefOperand(i, &DefIdx)) continue; 665d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen DEBUG(dbgs() << "Operand " << i << "("<< MO << ") is tied to operand " 666d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen << DefIdx << ".\n"); 667d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen LiveRegMap::iterator LRI = reloadVirtReg(MI, i, Reg, 0); 668d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen unsigned PhysReg = LRI->second.PhysReg; 669d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen setPhysReg(MI, i, PhysReg); 670d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen // Note: we don't update the def operand yet. That would cause the normal 671d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen // def-scan to attempt spilling. 672d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen } else if (MO.getSubReg() && MI->readsVirtualRegister(Reg)) { 673d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen DEBUG(dbgs() << "Partial redefine: " << MO << "\n"); 674d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen // Reload the register, but don't assign to the operand just yet. 675d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen // That would confuse the later phys-def processing pass. 676d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen LiveRegMap::iterator LRI = reloadVirtReg(MI, i, Reg, 0); 677d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen PartialDefs.push_back(LRI->second.PhysReg); 678d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen } else if (MO.isEarlyClobber()) { 679d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen // Note: defineVirtReg may invalidate MO. 680d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen LiveRegMap::iterator LRI = defineVirtReg(MI, i, Reg, 0); 681d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen unsigned PhysReg = LRI->second.PhysReg; 682d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen if (setPhysReg(MI, i, PhysReg)) 683d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen VirtDead.push_back(Reg); 684d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen } 685d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen } 686d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen 687d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen // Restore UsedInInstr to a state usable for allocating normal virtual uses. 688d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen UsedInInstr.reset(); 689d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 690d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen MachineOperand &MO = MI->getOperand(i); 691d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen if (!MO.isReg() || (MO.isDef() && !MO.isEarlyClobber())) continue; 692d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen unsigned Reg = MO.getReg(); 693d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen if (!Reg || !TargetRegisterInfo::isPhysicalRegister(Reg)) continue; 694d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen UsedInInstr.set(Reg); 695d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS) 696d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen UsedInInstr.set(*AS); 697d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen } 698d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen 699d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen // Also mark PartialDefs as used to avoid reallocation. 700d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen for (unsigned i = 0, e = PartialDefs.size(); i != e; ++i) 701d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen UsedInInstr.set(PartialDefs[i]); 702d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen} 703d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen 7046fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesenvoid RAFast::AllocateBasicBlock() { 7056fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen DEBUG(dbgs() << "\nAllocating " << *MBB); 70600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 707bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen PhysRegState.assign(TRI->getNumRegs(), regDisabled); 70876b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen assert(LiveVirtRegs.empty() && "Mapping not cleared form last block?"); 70900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 7106fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen MachineBasicBlock::iterator MII = MBB->begin(); 711bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen 712bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Add live-in registers as live. 7136fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen for (MachineBasicBlock::livein_iterator I = MBB->livein_begin(), 7146fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen E = MBB->livein_end(); I != E; ++I) 7156fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen definePhysReg(MII, *I, regReserved); 716bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen 717d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen SmallVector<unsigned, 8> VirtDead; 7187ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen SmallVector<MachineInstr*, 32> Coalesced; 71900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 72000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen // Otherwise, sequentially allocate each instruction in the MBB. 7216fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen while (MII != MBB->end()) { 72200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen MachineInstr *MI = MII++; 72300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen const TargetInstrDesc &TID = MI->getDesc(); 72400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen DEBUG({ 725c9c4dacd03a4b80d61ed6b9c6ffeb1b1f76b8d1cJakob Stoklund Olesen dbgs() << "\n>> " << *MI << "Regs:"; 726bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen for (unsigned Reg = 1, E = TRI->getNumRegs(); Reg != E; ++Reg) { 727bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (PhysRegState[Reg] == regDisabled) continue; 728bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen dbgs() << " " << TRI->getName(Reg); 729bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen switch(PhysRegState[Reg]) { 730bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regFree: 731bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 732bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regReserved: 733c9c4dacd03a4b80d61ed6b9c6ffeb1b1f76b8d1cJakob Stoklund Olesen dbgs() << "*"; 734bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 735bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen default: 736bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen dbgs() << "=%reg" << PhysRegState[Reg]; 737210e2afcc74e8ce5102d13939b23040fafa71c09Jakob Stoklund Olesen if (LiveVirtRegs[PhysRegState[Reg]].Dirty) 738bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen dbgs() << "*"; 73976b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen assert(LiveVirtRegs[PhysRegState[Reg]].PhysReg == Reg && 740bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen "Bad inverse map"); 741bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 742bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 743bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 74400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen dbgs() << '\n'; 74576b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen // Check that LiveVirtRegs is the inverse. 74676b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen for (LiveRegMap::iterator i = LiveVirtRegs.begin(), 74776b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen e = LiveVirtRegs.end(); i != e; ++i) { 748bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen assert(TargetRegisterInfo::isVirtualRegister(i->first) && 749bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen "Bad map key"); 75076b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen assert(TargetRegisterInfo::isPhysicalRegister(i->second.PhysReg) && 751bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen "Bad map value"); 75276b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen assert(PhysRegState[i->second.PhysReg] == i->first && 75376b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen "Bad inverse map"); 754bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 75500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen }); 75600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 757bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Debug values are not allowed to change codegen in any way. 758bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (MI->isDebugValue()) { 75900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 76000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen MachineOperand &MO = MI->getOperand(i); 761bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (!MO.isReg()) continue; 762bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned Reg = MO.getReg(); 763bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (!Reg || TargetRegisterInfo::isPhysicalRegister(Reg)) continue; 764844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen LiveRegMap::iterator LRI = LiveVirtRegs.find(Reg); 765844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen if (LRI != LiveVirtRegs.end()) 7660eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen setPhysReg(MI, i, LRI->second.PhysReg); 76776b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen else 76876b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen MO.setReg(0); // We can't allocate a physreg for a DebugValue, sorry! 76900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 770bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Next instruction. 771bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen continue; 77200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 77300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 7744bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen // If this is a copy, we may be able to coalesce. 7754bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen unsigned CopySrc, CopyDst, CopySrcSub, CopyDstSub; 776273f7e42994a5bce0614d04d96dbfdf05fd652e5Jakob Stoklund Olesen if (MI->isCopy()) { 777273f7e42994a5bce0614d04d96dbfdf05fd652e5Jakob Stoklund Olesen CopyDst = MI->getOperand(0).getReg(); 778273f7e42994a5bce0614d04d96dbfdf05fd652e5Jakob Stoklund Olesen CopySrc = MI->getOperand(1).getReg(); 779273f7e42994a5bce0614d04d96dbfdf05fd652e5Jakob Stoklund Olesen CopyDstSub = MI->getOperand(0).getSubReg(); 780273f7e42994a5bce0614d04d96dbfdf05fd652e5Jakob Stoklund Olesen CopySrcSub = MI->getOperand(1).getSubReg(); 781273f7e42994a5bce0614d04d96dbfdf05fd652e5Jakob Stoklund Olesen } else if (!TII->isMoveInstr(*MI, CopySrc, CopyDst, CopySrcSub, CopyDstSub)) 7824bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen CopySrc = CopyDst = 0; 7834bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen 784bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Track registers used by instruction. 785bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen UsedInInstr.reset(); 78600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 787bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // First scan. 788bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Mark physreg uses and early clobbers as used. 789e97dda4fc58ee401ebb4aa9153d10f8ce8ba9a70Jakob Stoklund Olesen // Find the end of the virtreg operands 790e97dda4fc58ee401ebb4aa9153d10f8ce8ba9a70Jakob Stoklund Olesen unsigned VirtOpEnd = 0; 791d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen bool hasTiedOps = false; 792d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen bool hasEarlyClobbers = false; 793d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen bool hasPartialRedefs = false; 794d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen bool hasPhysDefs = false; 795bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 79600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen MachineOperand &MO = MI->getOperand(i); 797bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (!MO.isReg()) continue; 798bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned Reg = MO.getReg(); 799e97dda4fc58ee401ebb4aa9153d10f8ce8ba9a70Jakob Stoklund Olesen if (!Reg) continue; 800e97dda4fc58ee401ebb4aa9153d10f8ce8ba9a70Jakob Stoklund Olesen if (TargetRegisterInfo::isVirtualRegister(Reg)) { 801e97dda4fc58ee401ebb4aa9153d10f8ce8ba9a70Jakob Stoklund Olesen VirtOpEnd = i+1; 802d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen if (MO.isUse()) { 803d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen hasTiedOps = hasTiedOps || 804d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen TID.getOperandConstraint(i, TOI::TIED_TO) != -1; 805d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen } else { 806d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen if (MO.isEarlyClobber()) 807d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen hasEarlyClobbers = true; 808d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen if (MO.getSubReg() && MI->readsVirtualRegister(Reg)) 809d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen hasPartialRedefs = true; 810d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen } 811e97dda4fc58ee401ebb4aa9153d10f8ce8ba9a70Jakob Stoklund Olesen continue; 812e97dda4fc58ee401ebb4aa9153d10f8ce8ba9a70Jakob Stoklund Olesen } 813efa155fd6e3820495205a09f8b9f20390d126153Jakob Stoklund Olesen if (!Allocatable.test(Reg)) continue; 814bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (MO.isUse()) { 8154ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen usePhysReg(MO); 816bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } else if (MO.isEarlyClobber()) { 81775ac4d9c2dfb22f84da25dec03df7a07f3dad1faJakob Stoklund Olesen definePhysReg(MI, Reg, (MO.isImplicit() || MO.isDead()) ? 81875ac4d9c2dfb22f84da25dec03df7a07f3dad1faJakob Stoklund Olesen regFree : regReserved); 819d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen hasEarlyClobbers = true; 820d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen } else 821d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen hasPhysDefs = true; 822d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen } 823d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen 824d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen // The instruction may have virtual register operands that must be allocated 825d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen // the same register at use-time and def-time: early clobbers and tied 826d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen // operands. If there are also physical defs, these registers must avoid 827d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen // both physical defs and uses, making them more constrained than normal 828d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen // operands. 829d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen // We didn't detect inline asm tied operands above, so just make this extra 830d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen // pass for all inline asm. 831d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen if (MI->isInlineAsm() || hasEarlyClobbers || hasPartialRedefs || 832d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen (hasTiedOps && hasPhysDefs)) { 833d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen handleThroughOperands(MI, VirtDead); 834d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen // Don't attempt coalescing when we have funny stuff going on. 835d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen CopyDst = 0; 83600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 83700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 838bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Second scan. 839d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen // Allocate virtreg uses. 840e97dda4fc58ee401ebb4aa9153d10f8ce8ba9a70Jakob Stoklund Olesen for (unsigned i = 0; i != VirtOpEnd; ++i) { 84100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen MachineOperand &MO = MI->getOperand(i); 842bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (!MO.isReg()) continue; 84300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen unsigned Reg = MO.getReg(); 844bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (!Reg || TargetRegisterInfo::isPhysicalRegister(Reg)) continue; 845bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (MO.isUse()) { 846646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund Olesen LiveRegMap::iterator LRI = reloadVirtReg(MI, i, Reg, CopyDst); 847646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund Olesen unsigned PhysReg = LRI->second.PhysReg; 8487ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen CopySrc = (CopySrc == Reg || CopySrc == PhysReg) ? PhysReg : 0; 8490eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen if (setPhysReg(MI, i, PhysReg)) 850646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund Olesen killVirtReg(LRI); 85100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 85200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 85300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 8544bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen MRI->addPhysRegsUsed(UsedInInstr); 85582b07dc4995d48065bd95affff4d8513a5cad4f2Jakob Stoklund Olesen 856bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Track registers defined by instruction - early clobbers at this point. 857bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen UsedInInstr.reset(); 858d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen if (hasEarlyClobbers) { 859d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 860d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen MachineOperand &MO = MI->getOperand(i); 861d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen if (!MO.isReg() || !MO.isDef()) continue; 862d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen unsigned Reg = MO.getReg(); 863d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen if (!Reg || !TargetRegisterInfo::isPhysicalRegister(Reg)) continue; 864d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen UsedInInstr.set(Reg); 865d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS) 866d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen UsedInInstr.set(*AS); 867d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen } 86800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 86900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 8704b6bbe885d851b1cfba2be9b5efc6365a2b7828aJakob Stoklund Olesen unsigned DefOpEnd = MI->getNumOperands(); 8714b6bbe885d851b1cfba2be9b5efc6365a2b7828aJakob Stoklund Olesen if (TID.isCall()) { 8724b6bbe885d851b1cfba2be9b5efc6365a2b7828aJakob Stoklund Olesen // Spill all virtregs before a call. This serves two purposes: 1. If an 8734b6bbe885d851b1cfba2be9b5efc6365a2b7828aJakob Stoklund Olesen // exception is thrown, the landing pad is going to expect to find registers 8744b6bbe885d851b1cfba2be9b5efc6365a2b7828aJakob Stoklund Olesen // in their spill slots, and 2. we don't have to wade through all the 8754b6bbe885d851b1cfba2be9b5efc6365a2b7828aJakob Stoklund Olesen // <imp-def> operands on the call instruction. 8764b6bbe885d851b1cfba2be9b5efc6365a2b7828aJakob Stoklund Olesen DefOpEnd = VirtOpEnd; 8774b6bbe885d851b1cfba2be9b5efc6365a2b7828aJakob Stoklund Olesen DEBUG(dbgs() << " Spilling remaining registers before call.\n"); 8784b6bbe885d851b1cfba2be9b5efc6365a2b7828aJakob Stoklund Olesen spillAll(MI); 8796de07178e1e6445080bf4f7704e274c5f219ff70Jakob Stoklund Olesen 8806de07178e1e6445080bf4f7704e274c5f219ff70Jakob Stoklund Olesen // The imp-defs are skipped below, but we still need to mark those 8816de07178e1e6445080bf4f7704e274c5f219ff70Jakob Stoklund Olesen // registers as used by the function. 8826de07178e1e6445080bf4f7704e274c5f219ff70Jakob Stoklund Olesen SkippedInstrs.insert(&TID); 8834b6bbe885d851b1cfba2be9b5efc6365a2b7828aJakob Stoklund Olesen } 8844b6bbe885d851b1cfba2be9b5efc6365a2b7828aJakob Stoklund Olesen 885bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Third scan. 886bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Allocate defs and collect dead defs. 8874b6bbe885d851b1cfba2be9b5efc6365a2b7828aJakob Stoklund Olesen for (unsigned i = 0; i != DefOpEnd; ++i) { 88800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen MachineOperand &MO = MI->getOperand(i); 88975ac4d9c2dfb22f84da25dec03df7a07f3dad1faJakob Stoklund Olesen if (!MO.isReg() || !MO.isDef() || !MO.getReg() || MO.isEarlyClobber()) 89075ac4d9c2dfb22f84da25dec03df7a07f3dad1faJakob Stoklund Olesen continue; 891bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned Reg = MO.getReg(); 89200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 893bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (TargetRegisterInfo::isPhysicalRegister(Reg)) { 894efa155fd6e3820495205a09f8b9f20390d126153Jakob Stoklund Olesen if (!Allocatable.test(Reg)) continue; 8956fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen definePhysReg(MI, Reg, (MO.isImplicit() || MO.isDead()) ? 8966fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen regFree : regReserved); 897bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen continue; 89800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 899646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund Olesen LiveRegMap::iterator LRI = defineVirtReg(MI, i, Reg, CopySrc); 900646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund Olesen unsigned PhysReg = LRI->second.PhysReg; 9010eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen if (setPhysReg(MI, i, PhysReg)) { 9020eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen VirtDead.push_back(Reg); 9037ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen CopyDst = 0; // cancel coalescing; 9047ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen } else 9057ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen CopyDst = (CopyDst == Reg || CopyDst == PhysReg) ? PhysReg : 0; 90600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 90700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 9080eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen // Kill dead defs after the scan to ensure that multiple defs of the same 9090eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen // register are allocated identically. We didn't need to do this for uses 9100eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen // because we are crerating our own kill flags, and they are always at the 9110eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen // last use. 9120eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen for (unsigned i = 0, e = VirtDead.size(); i != e; ++i) 9130eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen killVirtReg(VirtDead[i]); 9140eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen VirtDead.clear(); 9150eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen 9164bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen MRI->addPhysRegsUsed(UsedInInstr); 917c9c4dacd03a4b80d61ed6b9c6ffeb1b1f76b8d1cJakob Stoklund Olesen 9187ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen if (CopyDst && CopyDst == CopySrc && CopyDstSub == CopySrcSub) { 9197ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen DEBUG(dbgs() << "-- coalescing: " << *MI); 9207ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen Coalesced.push_back(MI); 9217ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen } else { 9227ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen DEBUG(dbgs() << "<< " << *MI); 9237ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen } 92400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 92500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 926bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Spill all physical registers holding virtual registers now. 927e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen DEBUG(dbgs() << "Spilling live registers at end of block.\n"); 928e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen spillAll(MBB->getFirstTerminator()); 92900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 9307ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen // Erase all the coalesced copies. We are delaying it until now because 931e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen // LiveVirtRegs might refer to the instrs. 9327ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen for (unsigned i = 0, e = Coalesced.size(); i != e; ++i) 9336fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen MBB->erase(Coalesced[i]); 9348a65c510a4fa1245d101da6318618d025702028cJakob Stoklund Olesen NumCopies += Coalesced.size(); 9357ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen 9366fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen DEBUG(MBB->dump()); 93700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 93800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 93900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen/// runOnMachineFunction - Register allocate the whole function 94000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen/// 94100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesenbool RAFast::runOnMachineFunction(MachineFunction &Fn) { 942c9c4dacd03a4b80d61ed6b9c6ffeb1b1f76b8d1cJakob Stoklund Olesen DEBUG(dbgs() << "********** FAST REGISTER ALLOCATION **********\n" 943c9c4dacd03a4b80d61ed6b9c6ffeb1b1f76b8d1cJakob Stoklund Olesen << "********** Function: " 944c9c4dacd03a4b80d61ed6b9c6ffeb1b1f76b8d1cJakob Stoklund Olesen << ((Value*)Fn.getFunction())->getName() << '\n'); 94500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen MF = &Fn; 9464bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen MRI = &MF->getRegInfo(); 94700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen TM = &Fn.getTarget(); 94800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen TRI = TM->getRegisterInfo(); 94900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen TII = TM->getInstrInfo(); 95000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 95100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen UsedInInstr.resize(TRI->getNumRegs()); 952efa155fd6e3820495205a09f8b9f20390d126153Jakob Stoklund Olesen Allocatable = TRI->getAllocatableSet(*MF); 95300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 95400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen // initialize the virtual->physical register map to have a 'null' 95500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen // mapping for all virtual registers 9564bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen unsigned LastVirtReg = MRI->getLastVirtReg(); 95700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen StackSlotForVirtReg.grow(LastVirtReg); 95800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 95900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen // Loop over all of the basic blocks, eliminating virtual register references 9606fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen for (MachineFunction::iterator MBBi = Fn.begin(), MBBe = Fn.end(); 9616fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen MBBi != MBBe; ++MBBi) { 9626fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen MBB = &*MBBi; 9636fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen AllocateBasicBlock(); 9646fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen } 96500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 96682b07dc4995d48065bd95affff4d8513a5cad4f2Jakob Stoklund Olesen // Make sure the set of used physregs is closed under subreg operations. 9674bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen MRI->closePhysRegsUsed(*TRI); 96882b07dc4995d48065bd95affff4d8513a5cad4f2Jakob Stoklund Olesen 9696de07178e1e6445080bf4f7704e274c5f219ff70Jakob Stoklund Olesen // Add the clobber lists for all the instructions we skipped earlier. 9706de07178e1e6445080bf4f7704e274c5f219ff70Jakob Stoklund Olesen for (SmallPtrSet<const TargetInstrDesc*, 4>::const_iterator 9716de07178e1e6445080bf4f7704e274c5f219ff70Jakob Stoklund Olesen I = SkippedInstrs.begin(), E = SkippedInstrs.end(); I != E; ++I) 9726de07178e1e6445080bf4f7704e274c5f219ff70Jakob Stoklund Olesen if (const unsigned *Defs = (*I)->getImplicitDefs()) 9736de07178e1e6445080bf4f7704e274c5f219ff70Jakob Stoklund Olesen while (*Defs) 9746de07178e1e6445080bf4f7704e274c5f219ff70Jakob Stoklund Olesen MRI->setPhysRegUsed(*Defs++); 9756de07178e1e6445080bf4f7704e274c5f219ff70Jakob Stoklund Olesen 9766de07178e1e6445080bf4f7704e274c5f219ff70Jakob Stoklund Olesen SkippedInstrs.clear(); 97700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen StackSlotForVirtReg.clear(); 97800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen return true; 97900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 98000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 98100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund OlesenFunctionPass *llvm::createFastRegisterAllocator() { 98200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen return new RAFast(); 98300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 984