RegAllocFast.cpp revision 844db9cc6f1a9458b60b8debeef3132f555dcd8f
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 381b2c761a9cc9a57b417c676f4bd97d11b6ba1869Jakob Stoklund Olesenstatic cl::opt<bool> VerifyFastRegalloc("verify-fast-regalloc", cl::Hidden, 391b2c761a9cc9a57b417c676f4bd97d11b6ba1869Jakob Stoklund Olesen cl::desc("Verify machine code before fast regalloc")); 401b2c761a9cc9a57b417c676f4bd97d11b6ba1869Jakob Stoklund Olesen 4100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund OlesenSTATISTIC(NumStores, "Number of stores added"); 4200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund OlesenSTATISTIC(NumLoads , "Number of loads added"); 438a65c510a4fa1245d101da6318618d025702028cJakob Stoklund OlesenSTATISTIC(NumCopies, "Number of copies coalesced"); 4400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 4500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesenstatic RegisterRegAlloc 4600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen fastRegAlloc("fast", "fast register allocator", createFastRegisterAllocator); 4700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 4800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesennamespace { 4900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen class RAFast : public MachineFunctionPass { 5000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen public: 5100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen static char ID; 527d4f25904de543b039a28eddbea3034a5d80e7f8Jakob Stoklund Olesen RAFast() : MachineFunctionPass(&ID), StackSlotForVirtReg(-1), 53e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen isBulkSpilling(false) {} 5400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen private: 5500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen const TargetMachine *TM; 5600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen MachineFunction *MF; 574bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen MachineRegisterInfo *MRI; 5800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen const TargetRegisterInfo *TRI; 5900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen const TargetInstrInfo *TII; 6000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 616fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen // Basic block currently being allocated. 626fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen MachineBasicBlock *MBB; 636fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen 6400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen // StackSlotForVirtReg - Maps virtual regs to the frame index where these 6500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen // values are spilled. 6600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen IndexedMap<int, VirtReg2IndexFunctor> StackSlotForVirtReg; 6700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 6876b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen // Everything we know about a live virtual register. 6976b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen struct LiveReg { 70210e2afcc74e8ce5102d13939b23040fafa71c09Jakob Stoklund Olesen MachineInstr *LastUse; // Last instr to use reg. 71210e2afcc74e8ce5102d13939b23040fafa71c09Jakob Stoklund Olesen unsigned PhysReg; // Currently held here. 72210e2afcc74e8ce5102d13939b23040fafa71c09Jakob Stoklund Olesen unsigned short LastOpNum; // OpNum on LastUse. 73210e2afcc74e8ce5102d13939b23040fafa71c09Jakob Stoklund Olesen bool Dirty; // Register needs spill. 7476b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen 75210e2afcc74e8ce5102d13939b23040fafa71c09Jakob Stoklund Olesen LiveReg(unsigned p=0) : LastUse(0), PhysReg(p), LastOpNum(0), 7601dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen Dirty(false) {} 7776b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen }; 7876b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen 7976b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen typedef DenseMap<unsigned, LiveReg> LiveRegMap; 8001dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen typedef LiveRegMap::value_type LiveRegEntry; 8176b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen 8276b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen // LiveVirtRegs - This map contains entries for each virtual register 8300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen // that is currently available in a physical register. 8476b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen LiveRegMap LiveVirtRegs; 8500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 86bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // RegState - Track the state of a physical register. 87bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen enum RegState { 88bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // A disabled register is not available for allocation, but an alias may 89bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // be in use. A register can only be moved out of the disabled state if 90bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // all aliases are disabled. 91bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen regDisabled, 92bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen 93bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // A free register is not currently in use and can be allocated 94bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // immediately without checking aliases. 95bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen regFree, 96bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen 97bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // A reserved register has been assigned expolicitly (e.g., setting up a 98bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // call parameter), and it remains reserved until it is used. 99bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen regReserved 10000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 101bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // A register state may also be a virtual register number, indication that 102bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // the physical register is currently allocated to a virtual register. In 10376b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen // that case, LiveVirtRegs contains the inverse mapping. 104bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen }; 105bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen 106bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // PhysRegState - One of the RegState enums, or a virtreg. 107bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen std::vector<unsigned> PhysRegState; 10800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 10900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen // UsedInInstr - BitVector of physregs that are used in the current 11000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen // instruction, and so cannot be allocated. 11100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen BitVector UsedInInstr; 11200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 113efa155fd6e3820495205a09f8b9f20390d126153Jakob Stoklund Olesen // Allocatable - vector of allocatable physical registers. 114efa155fd6e3820495205a09f8b9f20390d126153Jakob Stoklund Olesen BitVector Allocatable; 11500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 116e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen // isBulkSpilling - This flag is set when LiveRegMap will be cleared 117e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen // completely after spilling all live registers. LiveRegMap entries should 118e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen // not be erased. 119e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen bool isBulkSpilling; 1207d4f25904de543b039a28eddbea3034a5d80e7f8Jakob Stoklund Olesen 12100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen public: 12200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen virtual const char *getPassName() const { 12300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen return "Fast Register Allocator"; 12400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 12500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 12600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen virtual void getAnalysisUsage(AnalysisUsage &AU) const { 12700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen AU.setPreservesCFG(); 12800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen AU.addRequiredID(PHIEliminationID); 12900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen AU.addRequiredID(TwoAddressInstructionPassID); 13000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen MachineFunctionPass::getAnalysisUsage(AU); 13100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 13200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 13300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen private: 13400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen bool runOnMachineFunction(MachineFunction &Fn); 1356fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen void AllocateBasicBlock(); 13600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen int getStackSpaceFor(unsigned VirtReg, const TargetRegisterClass *RC); 1371e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen bool isLastUseOfLocalReg(MachineOperand&); 1381e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen 13901dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen void addKillFlag(const LiveReg&); 140844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen void killVirtReg(LiveRegMap::iterator); 141804291e31658d46fb1db5ecaf42b31950c02a6f2Jakob Stoklund Olesen void killVirtReg(unsigned VirtReg); 142844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen void spillVirtReg(MachineBasicBlock::iterator MI, LiveRegMap::iterator); 143e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen void spillVirtReg(MachineBasicBlock::iterator MI, unsigned VirtReg); 1444ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen 1454ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen void usePhysReg(MachineOperand&); 1466fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen void definePhysReg(MachineInstr *MI, unsigned PhysReg, RegState NewState); 14701dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen void assignVirtToPhysReg(LiveRegEntry &LRE, unsigned PhysReg); 14801dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen void allocVirtReg(MachineInstr *MI, LiveRegEntry &LRE, unsigned Hint); 14901dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen unsigned defineVirtReg(MachineInstr *MI, unsigned OpNum, 15001dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen unsigned VirtReg, unsigned Hint); 15101dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen unsigned reloadVirtReg(MachineInstr *MI, unsigned OpNum, 15201dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen unsigned VirtReg, unsigned Hint); 1536fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen void spillAll(MachineInstr *MI); 154bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen void setPhysReg(MachineOperand &MO, unsigned PhysReg); 15500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen }; 15600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen char RAFast::ID = 0; 15700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 15800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 15900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen/// getStackSpaceFor - This allocates space for the specified virtual register 16000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen/// to be held on the stack. 16100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesenint RAFast::getStackSpaceFor(unsigned VirtReg, const TargetRegisterClass *RC) { 16200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen // Find the location Reg would belong... 16300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen int SS = StackSlotForVirtReg[VirtReg]; 16400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen if (SS != -1) 16500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen return SS; // Already has space allocated? 16600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 16700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen // Allocate a new stack object for this spill location... 16800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen int FrameIdx = MF->getFrameInfo()->CreateSpillStackObject(RC->getSize(), 16900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen RC->getAlignment()); 17000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 17100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen // Assign the slot. 17200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen StackSlotForVirtReg[VirtReg] = FrameIdx; 17300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen return FrameIdx; 17400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 17500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 1761e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen/// isLastUseOfLocalReg - Return true if MO is the only remaining reference to 1771e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen/// its virtual register, and it is guaranteed to be a block-local register. 1781e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen/// 1791e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesenbool RAFast::isLastUseOfLocalReg(MachineOperand &MO) { 1801e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen // Check for non-debug uses or defs following MO. 1811e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen // This is the most likely way to fail - fast path it. 182844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen MachineOperand *Next = &MO; 183844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen while ((Next = Next->getNextOperandForReg())) 184844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen if (!Next->isDebug()) 1851e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen return false; 1861e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen 1871e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen // If the register has ever been spilled or reloaded, we conservatively assume 1881e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen // it is a global register used in multiple blocks. 1891e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen if (StackSlotForVirtReg[MO.getReg()] != -1) 1901e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen return false; 1911e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen 1921e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen // Check that the use/def chain has exactly one operand - MO. 1931e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen return &MRI->reg_nodbg_begin(MO.getReg()).getOperand() == &MO; 1941e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen} 1951e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen 196804291e31658d46fb1db5ecaf42b31950c02a6f2Jakob Stoklund Olesen/// addKillFlag - Set kill flags on last use of a virtual register. 19701dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesenvoid RAFast::addKillFlag(const LiveReg &LR) { 19801dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen if (!LR.LastUse) return; 19901dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen MachineOperand &MO = LR.LastUse->getOperand(LR.LastOpNum); 20001dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen if (MO.isDef()) 20101dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen MO.setIsDead(); 20201dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen else if (!LR.LastUse->isRegTiedToDefOperand(LR.LastOpNum)) 20301dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen MO.setIsKill(); 204804291e31658d46fb1db5ecaf42b31950c02a6f2Jakob Stoklund Olesen} 205804291e31658d46fb1db5ecaf42b31950c02a6f2Jakob Stoklund Olesen 206804291e31658d46fb1db5ecaf42b31950c02a6f2Jakob Stoklund Olesen/// killVirtReg - Mark virtreg as no longer available. 207844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesenvoid RAFast::killVirtReg(LiveRegMap::iterator LRI) { 208844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen addKillFlag(LRI->second); 209844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen const LiveReg &LR = LRI->second; 210844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen assert(PhysRegState[LR.PhysReg] == LRI->first && "Broken RegState mapping"); 211804291e31658d46fb1db5ecaf42b31950c02a6f2Jakob Stoklund Olesen PhysRegState[LR.PhysReg] = regFree; 212e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen // Erase from LiveVirtRegs unless we're spilling in bulk. 213e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen if (!isBulkSpilling) 214844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen LiveVirtRegs.erase(LRI); 21576b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen} 21676b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen 21776b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen/// killVirtReg - Mark virtreg as no longer available. 218bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesenvoid RAFast::killVirtReg(unsigned VirtReg) { 219bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen assert(TargetRegisterInfo::isVirtualRegister(VirtReg) && 220bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen "killVirtReg needs a virtual register"); 221844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen LiveRegMap::iterator LRI = LiveVirtRegs.find(VirtReg); 222844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen if (LRI != LiveVirtRegs.end()) 223844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen killVirtReg(LRI); 22400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 22500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 226bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen/// spillVirtReg - This method spills the value specified by VirtReg into the 227bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen/// corresponding stack slot if needed. If isKill is set, the register is also 228bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen/// killed. 229e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesenvoid RAFast::spillVirtReg(MachineBasicBlock::iterator MI, unsigned VirtReg) { 230bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen assert(TargetRegisterInfo::isVirtualRegister(VirtReg) && 231bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen "Spilling a physical register is illegal!"); 232844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen LiveRegMap::iterator LRI = LiveVirtRegs.find(VirtReg); 233844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen assert(LRI != LiveVirtRegs.end() && "Spilling unmapped virtual register"); 234844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen spillVirtReg(MI, LRI); 2357d4f25904de543b039a28eddbea3034a5d80e7f8Jakob Stoklund Olesen} 2367d4f25904de543b039a28eddbea3034a5d80e7f8Jakob Stoklund Olesen 2377d4f25904de543b039a28eddbea3034a5d80e7f8Jakob Stoklund Olesen/// spillVirtReg - Do the actual work of spilling. 2386fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesenvoid RAFast::spillVirtReg(MachineBasicBlock::iterator MI, 239844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen LiveRegMap::iterator LRI) { 240844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen LiveReg &LR = LRI->second; 241844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen assert(PhysRegState[LR.PhysReg] == LRI->first && "Broken RegState mapping"); 24276b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen 243210e2afcc74e8ce5102d13939b23040fafa71c09Jakob Stoklund Olesen if (LR.Dirty) { 244e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen // If this physreg is used by the instruction, we want to kill it on the 245e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen // instruction, not on the spill. 246844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen bool SpillKill = LR.LastUse != MI; 247210e2afcc74e8ce5102d13939b23040fafa71c09Jakob Stoklund Olesen LR.Dirty = false; 248844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen DEBUG(dbgs() << "Spilling %reg" << LRI->first 2497d4f25904de543b039a28eddbea3034a5d80e7f8Jakob Stoklund Olesen << " in " << TRI->getName(LR.PhysReg)); 250844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen const TargetRegisterClass *RC = MRI->getRegClass(LRI->first); 251844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen int FI = getStackSpaceFor(LRI->first, RC); 2526fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen DEBUG(dbgs() << " to stack slot #" << FI << "\n"); 253844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen TII->storeRegToStackSlot(*MBB, MI, LR.PhysReg, SpillKill, FI, RC, TRI); 25400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen ++NumStores; // Update statistics 25500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 256844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen if (SpillKill) 257210e2afcc74e8ce5102d13939b23040fafa71c09Jakob Stoklund Olesen LR.LastUse = 0; // Don't kill register again 258bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 259844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen killVirtReg(LRI); 26000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 26100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 262bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen/// spillAll - Spill all dirty virtregs without killing them. 2636fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesenvoid RAFast::spillAll(MachineInstr *MI) { 264e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen isBulkSpilling = true; 26576b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen for (LiveRegMap::iterator i = LiveVirtRegs.begin(), 26676b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen e = LiveVirtRegs.end(); i != e; ++i) 267e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen spillVirtReg(MI, i); 268e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen LiveVirtRegs.clear(); 269e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen isBulkSpilling = false; 270bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen} 27100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 2724ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen/// usePhysReg - Handle the direct use of a physical register. 2734ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen/// Check that the register is not used by a virtreg. 2744ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen/// Kill the physreg, marking it free. 2754ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen/// This may add implicit kills to MO->getParent() and invalidate MO. 2764ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesenvoid RAFast::usePhysReg(MachineOperand &MO) { 2774ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen unsigned PhysReg = MO.getReg(); 2784ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen assert(TargetRegisterInfo::isPhysicalRegister(PhysReg) && 2794ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen "Bad usePhysReg operand"); 2804ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen 2814ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen switch (PhysRegState[PhysReg]) { 282bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regDisabled: 283bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 284bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regReserved: 285bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen PhysRegState[PhysReg] = regFree; 2864ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen // Fall through 2874ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen case regFree: 2884ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen UsedInInstr.set(PhysReg); 2894ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen MO.setIsKill(); 290bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen return; 291bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen default: 2924ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen // The physreg was allocated to a virtual register. That means to value we 2934ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen // wanted has been clobbered. 2944ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen llvm_unreachable("Instruction uses an allocated register"); 29500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 29600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 2974ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen // Maybe a superregister is reserved? 298bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen for (const unsigned *AS = TRI->getAliasSet(PhysReg); 299bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned Alias = *AS; ++AS) { 3004ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen switch (PhysRegState[Alias]) { 301bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regDisabled: 302bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 303bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regReserved: 3044ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen assert(TRI->isSuperRegister(PhysReg, Alias) && 3054ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen "Instruction is not using a subregister of a reserved register"); 3064ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen // Leave the superregister in the working set. 307bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen PhysRegState[Alias] = regFree; 3084ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen UsedInInstr.set(Alias); 3094ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen MO.getParent()->addRegisterKilled(Alias, TRI, true); 3104ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen return; 3114ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen case regFree: 3124ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen if (TRI->isSuperRegister(PhysReg, Alias)) { 3134ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen // Leave the superregister in the working set. 3144ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen UsedInInstr.set(Alias); 3154ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen MO.getParent()->addRegisterKilled(Alias, TRI, true); 3164ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen return; 3174ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen } 3184ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen // Some other alias was in the working set - clear it. 3194ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen PhysRegState[Alias] = regDisabled; 320bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 321bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen default: 3224ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen llvm_unreachable("Instruction uses an alias of an allocated register"); 323bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 32400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 3254ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen 3264ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen // All aliases are disabled, bring register into working set. 3274ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen PhysRegState[PhysReg] = regFree; 3284ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen UsedInInstr.set(PhysReg); 3294ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen MO.setIsKill(); 33000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 33100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 3324ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen/// definePhysReg - Mark PhysReg as reserved or free after spilling any 3334ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen/// virtregs. This is very similar to defineVirtReg except the physreg is 3344ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen/// reserved instead of allocated. 3356fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesenvoid RAFast::definePhysReg(MachineInstr *MI, unsigned PhysReg, 3366fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen RegState NewState) { 3374ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen UsedInInstr.set(PhysReg); 338bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen switch (unsigned VirtReg = PhysRegState[PhysReg]) { 339bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regDisabled: 340bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 3414ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen default: 342e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen spillVirtReg(MI, VirtReg); 3434ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen // Fall through. 344bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regFree: 345bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regReserved: 3464ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen PhysRegState[PhysReg] = NewState; 347bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen return; 348bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 349bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen 3504ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen // This is a disabled register, disable all aliases. 3514ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen PhysRegState[PhysReg] = NewState; 352bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen for (const unsigned *AS = TRI->getAliasSet(PhysReg); 353bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned Alias = *AS; ++AS) { 3544ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen UsedInInstr.set(Alias); 355bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen switch (unsigned VirtReg = PhysRegState[Alias]) { 356bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regDisabled: 357bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 358bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen default: 359e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen spillVirtReg(MI, VirtReg); 3604ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen // Fall through. 3614ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen case regFree: 3624ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen case regReserved: 3634ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen PhysRegState[Alias] = regDisabled; 3644ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen if (TRI->isSuperRegister(PhysReg, Alias)) 3654ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen return; 366bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 367bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 368bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 369bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen} 37000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 3714ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen 37200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen/// assignVirtToPhysReg - This method updates local state so that we know 37300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen/// that PhysReg is the proper container for VirtReg now. The physical 37400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen/// register must not be used for anything else when this is called. 37500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen/// 37601dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesenvoid RAFast::assignVirtToPhysReg(LiveRegEntry &LRE, unsigned PhysReg) { 37701dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen DEBUG(dbgs() << "Assigning %reg" << LRE.first << " to " 378bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen << TRI->getName(PhysReg) << "\n"); 37901dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen PhysRegState[PhysReg] = LRE.first; 38001dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen assert(!LRE.second.PhysReg && "Already assigned a physreg"); 38101dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen LRE.second.PhysReg = PhysReg; 38200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 38300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 384bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen/// allocVirtReg - Allocate a physical register for VirtReg. 38501dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesenvoid RAFast::allocVirtReg(MachineInstr *MI, LiveRegEntry &LRE, unsigned Hint) { 386844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen const unsigned SpillCost = 100; 38701dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen const unsigned VirtReg = LRE.first; 38801dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen 389bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen assert(TargetRegisterInfo::isVirtualRegister(VirtReg) && 390bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen "Can only allocate virtual registers"); 39100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 3924bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen const TargetRegisterClass *RC = MRI->getRegClass(VirtReg); 393bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen TargetRegisterClass::iterator AOB = RC->allocation_order_begin(*MF); 394bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen TargetRegisterClass::iterator AOE = RC->allocation_order_end(*MF); 395bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen 3964bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen // Ignore invalid hints. 3974bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen if (Hint && (!TargetRegisterInfo::isPhysicalRegister(Hint) || 3982c13ab2bb840295ffba5f28bb1df7aa0b8d9736eChandler Carruth !RC->contains(Hint) || UsedInInstr.test(Hint) || 3992c13ab2bb840295ffba5f28bb1df7aa0b8d9736eChandler Carruth !Allocatable.test(Hint))) 4004bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen Hint = 0; 4014bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen 4024bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen // If there is no hint, peek at the first use of this register. 4034bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen if (!Hint && !MRI->use_nodbg_empty(VirtReg)) { 4044bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen MachineInstr &MI = *MRI->use_nodbg_begin(VirtReg); 4054bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen unsigned SrcReg, DstReg, SrcSubReg, DstSubReg; 4064bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen // Copy to physreg -> use physreg as hint. 4074bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen if (TII->isMoveInstr(MI, SrcReg, DstReg, SrcSubReg, DstSubReg) && 4084bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen SrcReg == VirtReg && TargetRegisterInfo::isPhysicalRegister(DstReg) && 409efa155fd6e3820495205a09f8b9f20390d126153Jakob Stoklund Olesen RC->contains(DstReg) && !UsedInInstr.test(DstReg) && 410efa155fd6e3820495205a09f8b9f20390d126153Jakob Stoklund Olesen Allocatable.test(DstReg)) { 4114bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen Hint = DstReg; 412c9c4dacd03a4b80d61ed6b9c6ffeb1b1f76b8d1cJakob Stoklund Olesen DEBUG(dbgs() << "%reg" << VirtReg << " gets hint from " << MI); 4134bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen } 4144bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen } 4154bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen 4164bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen // Take hint when possible. 4174bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen if (Hint) { 4184bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen assert(RC->contains(Hint) && !UsedInInstr.test(Hint) && 419efa155fd6e3820495205a09f8b9f20390d126153Jakob Stoklund Olesen Allocatable.test(Hint) && "Invalid hint should have been cleared"); 4204bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen switch(PhysRegState[Hint]) { 4214bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen case regDisabled: 4224bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen case regReserved: 4234bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen break; 4244bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen default: 425e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen spillVirtReg(MI, PhysRegState[Hint]); 4264bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen // Fall through. 4274bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen case regFree: 42801dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen return assignVirtToPhysReg(LRE, Hint); 4294bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen } 4304bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen } 4314bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen 432bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // First try to find a completely free register. 433bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned BestCost = 0, BestReg = 0; 434bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen bool hasDisabled = false; 435bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen for (TargetRegisterClass::iterator I = AOB; I != AOE; ++I) { 436bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned PhysReg = *I; 437bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen switch(PhysRegState[PhysReg]) { 438bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regDisabled: 439bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen hasDisabled = true; 440bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regReserved: 441bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen continue; 442bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regFree: 44376b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen if (!UsedInInstr.test(PhysReg)) 44401dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen return assignVirtToPhysReg(LRE, PhysReg); 445bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen continue; 446bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen default: 447bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Grab the first spillable register we meet. 448210e2afcc74e8ce5102d13939b23040fafa71c09Jakob Stoklund Olesen if (!BestReg && !UsedInInstr.test(PhysReg)) 449844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen BestReg = PhysReg, BestCost = SpillCost; 450bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen continue; 45100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 452bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 45300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 454c9c4dacd03a4b80d61ed6b9c6ffeb1b1f76b8d1cJakob Stoklund Olesen DEBUG(dbgs() << "Allocating %reg" << VirtReg << " from " << RC->getName() 455bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen << " candidate=" << TRI->getName(BestReg) << "\n"); 45600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 457bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Try to extend the working set for RC if there were any disabled registers. 458844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen if (hasDisabled && (!BestReg || BestCost >= SpillCost)) { 459bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen for (TargetRegisterClass::iterator I = AOB; I != AOE; ++I) { 460bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned PhysReg = *I; 461bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (PhysRegState[PhysReg] != regDisabled || UsedInInstr.test(PhysReg)) 462bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen continue; 46300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 464bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Calculate the cost of bringing PhysReg into the working set. 465bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned Cost=0; 466bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen bool Impossible = false; 467bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen for (const unsigned *AS = TRI->getAliasSet(PhysReg); 468bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned Alias = *AS; ++AS) { 469bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (UsedInInstr.test(Alias)) { 470bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen Impossible = true; 471bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 472bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 473bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen switch (PhysRegState[Alias]) { 474bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regDisabled: 475bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 476bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regReserved: 477bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen Impossible = true; 478bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 479bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regFree: 480bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen Cost++; 481bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 482bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen default: 483844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen Cost += SpillCost; 484bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 485bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 486bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 487bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (Impossible) continue; 488c9c4dacd03a4b80d61ed6b9c6ffeb1b1f76b8d1cJakob Stoklund Olesen DEBUG(dbgs() << "- candidate " << TRI->getName(PhysReg) 489bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen << " cost=" << Cost << "\n"); 490bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (!BestReg || Cost < BestCost) { 491bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen BestReg = PhysReg; 492bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen BestCost = Cost; 493844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen if (Cost < SpillCost) break; 494bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 495bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 49600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 49700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 498bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (BestReg) { 499bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // BestCost is 0 when all aliases are already disabled. 500bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (BestCost) { 501bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (PhysRegState[BestReg] != regDisabled) 502e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen spillVirtReg(MI, PhysRegState[BestReg]); 503bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen else { 504bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Make sure all aliases are disabled. 505bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen for (const unsigned *AS = TRI->getAliasSet(BestReg); 506bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned Alias = *AS; ++AS) { 507bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen switch (PhysRegState[Alias]) { 508bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regDisabled: 509bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen continue; 510bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regFree: 511bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen PhysRegState[Alias] = regDisabled; 512bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 513bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen default: 514e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen spillVirtReg(MI, PhysRegState[Alias]); 515bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen PhysRegState[Alias] = regDisabled; 516bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 517bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 518bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 519bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 52000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 52101dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen return assignVirtToPhysReg(LRE, BestReg); 522bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 52300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 524bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Nothing we can do. 525bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen std::string msg; 526bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen raw_string_ostream Msg(msg); 527bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen Msg << "Ran out of registers during register allocation!"; 528bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (MI->isInlineAsm()) { 529bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen Msg << "\nPlease check your inline asm statement for " 530bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen << "invalid constraints:\n"; 531bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen MI->print(Msg, TM); 532bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 533bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen report_fatal_error(Msg.str()); 53400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 53500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 536bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen/// defineVirtReg - Allocate a register for VirtReg and mark it as dirty. 5376fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesenunsigned RAFast::defineVirtReg(MachineInstr *MI, unsigned OpNum, 5386fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen unsigned VirtReg, unsigned Hint) { 539bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen assert(TargetRegisterInfo::isVirtualRegister(VirtReg) && 540bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen "Not a virtual register"); 541844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen LiveRegMap::iterator LRI; 54201dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen bool New; 543844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen tie(LRI, New) = LiveVirtRegs.insert(std::make_pair(VirtReg, LiveReg())); 544844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen LiveReg &LR = LRI->second; 54501dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen if (New) 546844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen allocVirtReg(MI, *LRI, Hint); 54701dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen else 54801dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen addKillFlag(LR); // Kill before redefine. 54901dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen assert(LR.PhysReg && "Register not assigned"); 550210e2afcc74e8ce5102d13939b23040fafa71c09Jakob Stoklund Olesen LR.LastUse = MI; 551210e2afcc74e8ce5102d13939b23040fafa71c09Jakob Stoklund Olesen LR.LastOpNum = OpNum; 552210e2afcc74e8ce5102d13939b23040fafa71c09Jakob Stoklund Olesen LR.Dirty = true; 553210e2afcc74e8ce5102d13939b23040fafa71c09Jakob Stoklund Olesen UsedInInstr.set(LR.PhysReg); 554210e2afcc74e8ce5102d13939b23040fafa71c09Jakob Stoklund Olesen return LR.PhysReg; 555bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen} 55600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 557bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen/// reloadVirtReg - Make sure VirtReg is available in a physreg and return it. 5586fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesenunsigned RAFast::reloadVirtReg(MachineInstr *MI, unsigned OpNum, 5596fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen unsigned VirtReg, unsigned Hint) { 560bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen assert(TargetRegisterInfo::isVirtualRegister(VirtReg) && 561bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen "Not a virtual register"); 562844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen LiveRegMap::iterator LRI; 56301dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen bool New; 564844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen tie(LRI, New) = LiveVirtRegs.insert(std::make_pair(VirtReg, LiveReg())); 565844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen LiveReg &LR = LRI->second; 56601dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen if (New) { 567844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen allocVirtReg(MI, *LRI, Hint); 5684bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen const TargetRegisterClass *RC = MRI->getRegClass(VirtReg); 569bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen int FrameIndex = getStackSpaceFor(VirtReg, RC); 570c9c4dacd03a4b80d61ed6b9c6ffeb1b1f76b8d1cJakob Stoklund Olesen DEBUG(dbgs() << "Reloading %reg" << VirtReg << " into " 57101dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen << TRI->getName(LR.PhysReg) << "\n"); 57201dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen TII->loadRegFromStackSlot(*MBB, MI, LR.PhysReg, FrameIndex, RC, TRI); 573bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen ++NumLoads; 57401dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen } else if (LR.Dirty) { 5751e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen MachineOperand &MO = MI->getOperand(OpNum); 5761e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen if (isLastUseOfLocalReg(MO)) { 5771e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen DEBUG(dbgs() << "Killing last use: " << MO << "\n"); 5781e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen MO.setIsKill(); 5791e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen } else if (MO.isKill()) { 5801e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen DEBUG(dbgs() << "Clearing dubious kill: " << MO << "\n"); 5811e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen MO.setIsKill(false); 5821e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen } 58300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 58401dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen assert(LR.PhysReg && "Register not assigned"); 585210e2afcc74e8ce5102d13939b23040fafa71c09Jakob Stoklund Olesen LR.LastUse = MI; 586210e2afcc74e8ce5102d13939b23040fafa71c09Jakob Stoklund Olesen LR.LastOpNum = OpNum; 587210e2afcc74e8ce5102d13939b23040fafa71c09Jakob Stoklund Olesen UsedInInstr.set(LR.PhysReg); 588210e2afcc74e8ce5102d13939b23040fafa71c09Jakob Stoklund Olesen return LR.PhysReg; 589bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen} 59000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 591bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen// setPhysReg - Change MO the refer the PhysReg, considering subregs. 592bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesenvoid RAFast::setPhysReg(MachineOperand &MO, unsigned PhysReg) { 593bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (unsigned Idx = MO.getSubReg()) { 594bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen MO.setReg(PhysReg ? TRI->getSubReg(PhysReg, Idx) : 0); 595bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen MO.setSubReg(0); 596bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } else 597bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen MO.setReg(PhysReg); 59800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 59900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 6006fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesenvoid RAFast::AllocateBasicBlock() { 6016fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen DEBUG(dbgs() << "\nAllocating " << *MBB); 60200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 603bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen PhysRegState.assign(TRI->getNumRegs(), regDisabled); 60476b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen assert(LiveVirtRegs.empty() && "Mapping not cleared form last block?"); 60500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 6066fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen MachineBasicBlock::iterator MII = MBB->begin(); 607bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen 608bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Add live-in registers as live. 6096fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen for (MachineBasicBlock::livein_iterator I = MBB->livein_begin(), 6106fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen E = MBB->livein_end(); I != E; ++I) 6116fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen definePhysReg(MII, *I, regReserved); 612bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen 6134ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen SmallVector<unsigned, 8> VirtKills, PhysDefs; 6147ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen SmallVector<MachineInstr*, 32> Coalesced; 61500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 61600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen // Otherwise, sequentially allocate each instruction in the MBB. 6176fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen while (MII != MBB->end()) { 61800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen MachineInstr *MI = MII++; 61900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen const TargetInstrDesc &TID = MI->getDesc(); 62000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen DEBUG({ 621c9c4dacd03a4b80d61ed6b9c6ffeb1b1f76b8d1cJakob Stoklund Olesen dbgs() << "\n>> " << *MI << "Regs:"; 622bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen for (unsigned Reg = 1, E = TRI->getNumRegs(); Reg != E; ++Reg) { 623bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (PhysRegState[Reg] == regDisabled) continue; 624bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen dbgs() << " " << TRI->getName(Reg); 625bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen switch(PhysRegState[Reg]) { 626bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regFree: 627bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 628bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regReserved: 629c9c4dacd03a4b80d61ed6b9c6ffeb1b1f76b8d1cJakob Stoklund Olesen dbgs() << "*"; 630bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 631bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen default: 632bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen dbgs() << "=%reg" << PhysRegState[Reg]; 633210e2afcc74e8ce5102d13939b23040fafa71c09Jakob Stoklund Olesen if (LiveVirtRegs[PhysRegState[Reg]].Dirty) 634bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen dbgs() << "*"; 63576b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen assert(LiveVirtRegs[PhysRegState[Reg]].PhysReg == Reg && 636bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen "Bad inverse map"); 637bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 638bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 639bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 64000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen dbgs() << '\n'; 64176b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen // Check that LiveVirtRegs is the inverse. 64276b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen for (LiveRegMap::iterator i = LiveVirtRegs.begin(), 64376b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen e = LiveVirtRegs.end(); i != e; ++i) { 644bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen assert(TargetRegisterInfo::isVirtualRegister(i->first) && 645bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen "Bad map key"); 64676b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen assert(TargetRegisterInfo::isPhysicalRegister(i->second.PhysReg) && 647bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen "Bad map value"); 64876b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen assert(PhysRegState[i->second.PhysReg] == i->first && 64976b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen "Bad inverse map"); 650bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 65100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen }); 65200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 653bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Debug values are not allowed to change codegen in any way. 654bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (MI->isDebugValue()) { 65500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 65600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen MachineOperand &MO = MI->getOperand(i); 657bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (!MO.isReg()) continue; 658bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned Reg = MO.getReg(); 659bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (!Reg || TargetRegisterInfo::isPhysicalRegister(Reg)) continue; 660844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen LiveRegMap::iterator LRI = LiveVirtRegs.find(Reg); 661844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen if (LRI != LiveVirtRegs.end()) 662844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen setPhysReg(MO, LRI->second.PhysReg); 66376b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen else 66476b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen MO.setReg(0); // We can't allocate a physreg for a DebugValue, sorry! 66500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 666bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Next instruction. 667bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen continue; 66800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 66900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 6704bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen // If this is a copy, we may be able to coalesce. 6714bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen unsigned CopySrc, CopyDst, CopySrcSub, CopyDstSub; 6724bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen if (!TII->isMoveInstr(*MI, CopySrc, CopyDst, CopySrcSub, CopyDstSub)) 6734bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen CopySrc = CopyDst = 0; 6744bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen 675bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Track registers used by instruction. 676bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen UsedInInstr.reset(); 677bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen PhysDefs.clear(); 67800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 679bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // First scan. 680bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Mark physreg uses and early clobbers as used. 681e97dda4fc58ee401ebb4aa9153d10f8ce8ba9a70Jakob Stoklund Olesen // Find the end of the virtreg operands 682e97dda4fc58ee401ebb4aa9153d10f8ce8ba9a70Jakob Stoklund Olesen unsigned VirtOpEnd = 0; 683bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 68400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen MachineOperand &MO = MI->getOperand(i); 685bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (!MO.isReg()) continue; 686bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned Reg = MO.getReg(); 687e97dda4fc58ee401ebb4aa9153d10f8ce8ba9a70Jakob Stoklund Olesen if (!Reg) continue; 688e97dda4fc58ee401ebb4aa9153d10f8ce8ba9a70Jakob Stoklund Olesen if (TargetRegisterInfo::isVirtualRegister(Reg)) { 689e97dda4fc58ee401ebb4aa9153d10f8ce8ba9a70Jakob Stoklund Olesen VirtOpEnd = i+1; 690e97dda4fc58ee401ebb4aa9153d10f8ce8ba9a70Jakob Stoklund Olesen continue; 691e97dda4fc58ee401ebb4aa9153d10f8ce8ba9a70Jakob Stoklund Olesen } 692efa155fd6e3820495205a09f8b9f20390d126153Jakob Stoklund Olesen if (!Allocatable.test(Reg)) continue; 693bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (MO.isUse()) { 6944ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen usePhysReg(MO); 695bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } else if (MO.isEarlyClobber()) { 6966fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen definePhysReg(MI, Reg, MO.isDead() ? regFree : regReserved); 697bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen PhysDefs.push_back(Reg); 69800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 69900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 70000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 701bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Second scan. 702bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Allocate virtreg uses and early clobbers. 703bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Collect VirtKills 704e97dda4fc58ee401ebb4aa9153d10f8ce8ba9a70Jakob Stoklund Olesen for (unsigned i = 0; i != VirtOpEnd; ++i) { 70500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen MachineOperand &MO = MI->getOperand(i); 706bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (!MO.isReg()) continue; 70700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen unsigned Reg = MO.getReg(); 708bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (!Reg || TargetRegisterInfo::isPhysicalRegister(Reg)) continue; 709bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (MO.isUse()) { 7106fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen unsigned PhysReg = reloadVirtReg(MI, i, Reg, CopyDst); 7117ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen CopySrc = (CopySrc == Reg || CopySrc == PhysReg) ? PhysReg : 0; 7124bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen setPhysReg(MO, PhysReg); 713bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (MO.isKill()) 714bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen VirtKills.push_back(Reg); 715bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } else if (MO.isEarlyClobber()) { 7166fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen unsigned PhysReg = defineVirtReg(MI, i, Reg, 0); 717bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen setPhysReg(MO, PhysReg); 718bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen PhysDefs.push_back(PhysReg); 71900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 72000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 72100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 722bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Process virtreg kills 723bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen for (unsigned i = 0, e = VirtKills.size(); i != e; ++i) 724bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen killVirtReg(VirtKills[i]); 725bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen VirtKills.clear(); 72600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 7274bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen MRI->addPhysRegsUsed(UsedInInstr); 72882b07dc4995d48065bd95affff4d8513a5cad4f2Jakob Stoklund Olesen 729bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Track registers defined by instruction - early clobbers at this point. 730bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen UsedInInstr.reset(); 731bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen for (unsigned i = 0, e = PhysDefs.size(); i != e; ++i) { 732bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned PhysReg = PhysDefs[i]; 733bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen UsedInInstr.set(PhysReg); 734bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen for (const unsigned *AS = TRI->getAliasSet(PhysReg); 735bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned Alias = *AS; ++AS) 736bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen UsedInInstr.set(Alias); 73700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 73800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 739bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Third scan. 740bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Allocate defs and collect dead defs. 74100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 74200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen MachineOperand &MO = MI->getOperand(i); 743bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (!MO.isReg() || !MO.isDef() || !MO.getReg()) continue; 744bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned Reg = MO.getReg(); 74500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 746bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (TargetRegisterInfo::isPhysicalRegister(Reg)) { 747efa155fd6e3820495205a09f8b9f20390d126153Jakob Stoklund Olesen if (!Allocatable.test(Reg)) continue; 7486fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen definePhysReg(MI, Reg, (MO.isImplicit() || MO.isDead()) ? 7496fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen regFree : regReserved); 750bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen continue; 75100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 7526fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen unsigned PhysReg = defineVirtReg(MI, i, Reg, CopySrc); 7537ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen if (MO.isDead()) { 7547ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen VirtKills.push_back(Reg); 7557ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen CopyDst = 0; // cancel coalescing; 7567ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen } else 7577ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen CopyDst = (CopyDst == Reg || CopyDst == PhysReg) ? PhysReg : 0; 7584bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen setPhysReg(MO, PhysReg); 75900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 76000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 761bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Spill all dirty virtregs before a call, in case of an exception. 762bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (TID.isCall()) { 763bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen DEBUG(dbgs() << " Spilling remaining registers before call.\n"); 7646fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen spillAll(MI); 76500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 76600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 767bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Process virtreg deads. 768bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen for (unsigned i = 0, e = VirtKills.size(); i != e; ++i) 769bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen killVirtReg(VirtKills[i]); 770bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen VirtKills.clear(); 771bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen 7724bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen MRI->addPhysRegsUsed(UsedInInstr); 773c9c4dacd03a4b80d61ed6b9c6ffeb1b1f76b8d1cJakob Stoklund Olesen 7747ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen if (CopyDst && CopyDst == CopySrc && CopyDstSub == CopySrcSub) { 7757ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen DEBUG(dbgs() << "-- coalescing: " << *MI); 7767ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen Coalesced.push_back(MI); 7777ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen } else { 7787ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen DEBUG(dbgs() << "<< " << *MI); 7797ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen } 78000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 78100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 782bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Spill all physical registers holding virtual registers now. 783e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen DEBUG(dbgs() << "Spilling live registers at end of block.\n"); 784e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen spillAll(MBB->getFirstTerminator()); 78500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 7867ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen // Erase all the coalesced copies. We are delaying it until now because 787e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen // LiveVirtRegs might refer to the instrs. 7887ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen for (unsigned i = 0, e = Coalesced.size(); i != e; ++i) 7896fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen MBB->erase(Coalesced[i]); 7908a65c510a4fa1245d101da6318618d025702028cJakob Stoklund Olesen NumCopies += Coalesced.size(); 7917ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen 7926fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen DEBUG(MBB->dump()); 79300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 79400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 79500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen/// runOnMachineFunction - Register allocate the whole function 79600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen/// 79700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesenbool RAFast::runOnMachineFunction(MachineFunction &Fn) { 798c9c4dacd03a4b80d61ed6b9c6ffeb1b1f76b8d1cJakob Stoklund Olesen DEBUG(dbgs() << "********** FAST REGISTER ALLOCATION **********\n" 799c9c4dacd03a4b80d61ed6b9c6ffeb1b1f76b8d1cJakob Stoklund Olesen << "********** Function: " 800c9c4dacd03a4b80d61ed6b9c6ffeb1b1f76b8d1cJakob Stoklund Olesen << ((Value*)Fn.getFunction())->getName() << '\n'); 8011b2c761a9cc9a57b417c676f4bd97d11b6ba1869Jakob Stoklund Olesen if (VerifyFastRegalloc) 802a0e618de5d9b40e5b5189c299086487e5ad767f2Jakob Stoklund Olesen Fn.verify(this, true); 80300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen MF = &Fn; 8044bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen MRI = &MF->getRegInfo(); 80500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen TM = &Fn.getTarget(); 80600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen TRI = TM->getRegisterInfo(); 80700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen TII = TM->getInstrInfo(); 80800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 80900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen UsedInInstr.resize(TRI->getNumRegs()); 810efa155fd6e3820495205a09f8b9f20390d126153Jakob Stoklund Olesen Allocatable = TRI->getAllocatableSet(*MF); 81100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 81200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen // initialize the virtual->physical register map to have a 'null' 81300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen // mapping for all virtual registers 8144bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen unsigned LastVirtReg = MRI->getLastVirtReg(); 81500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen StackSlotForVirtReg.grow(LastVirtReg); 81600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 81700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen // Loop over all of the basic blocks, eliminating virtual register references 8186fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen for (MachineFunction::iterator MBBi = Fn.begin(), MBBe = Fn.end(); 8196fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen MBBi != MBBe; ++MBBi) { 8206fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen MBB = &*MBBi; 8216fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen AllocateBasicBlock(); 8226fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen } 82300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 82482b07dc4995d48065bd95affff4d8513a5cad4f2Jakob Stoklund Olesen // Make sure the set of used physregs is closed under subreg operations. 8254bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen MRI->closePhysRegsUsed(*TRI); 82682b07dc4995d48065bd95affff4d8513a5cad4f2Jakob Stoklund Olesen 82700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen StackSlotForVirtReg.clear(); 82800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen return true; 82900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 83000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 83100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund OlesenFunctionPass *llvm::createFastRegisterAllocator() { 83200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen return new RAFast(); 83300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 834