RegAllocFast.cpp revision f3ea06b108d45c53dade87d6f1f48ac0a0e20562
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 121548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen enum { 122548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen spillClean = 1, 123548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen spillDirty = 100, 124548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen spillImpossible = ~0u 125548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen }; 12600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen public: 12700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen virtual const char *getPassName() const { 12800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen return "Fast Register Allocator"; 12900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 13000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 13100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen virtual void getAnalysisUsage(AnalysisUsage &AU) const { 13200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen AU.setPreservesCFG(); 13300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen AU.addRequiredID(PHIEliminationID); 13400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen AU.addRequiredID(TwoAddressInstructionPassID); 13500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen MachineFunctionPass::getAnalysisUsage(AU); 13600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 13700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 13800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen private: 13900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen bool runOnMachineFunction(MachineFunction &Fn); 1406fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen void AllocateBasicBlock(); 14100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen int getStackSpaceFor(unsigned VirtReg, const TargetRegisterClass *RC); 1421e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen bool isLastUseOfLocalReg(MachineOperand&); 1431e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen 14401dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen void addKillFlag(const LiveReg&); 145844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen void killVirtReg(LiveRegMap::iterator); 146804291e31658d46fb1db5ecaf42b31950c02a6f2Jakob Stoklund Olesen void killVirtReg(unsigned VirtReg); 147844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen void spillVirtReg(MachineBasicBlock::iterator MI, LiveRegMap::iterator); 148e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen void spillVirtReg(MachineBasicBlock::iterator MI, unsigned VirtReg); 1494ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen 1504ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen void usePhysReg(MachineOperand&); 1516fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen void definePhysReg(MachineInstr *MI, unsigned PhysReg, RegState NewState); 152548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen unsigned calcSpillCost(unsigned PhysReg) const; 15301dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen void assignVirtToPhysReg(LiveRegEntry &LRE, unsigned PhysReg); 15401dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen void allocVirtReg(MachineInstr *MI, LiveRegEntry &LRE, unsigned Hint); 155646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund Olesen LiveRegMap::iterator defineVirtReg(MachineInstr *MI, unsigned OpNum, 156646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund Olesen unsigned VirtReg, unsigned Hint); 157646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund Olesen LiveRegMap::iterator reloadVirtReg(MachineInstr *MI, unsigned OpNum, 158646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund Olesen unsigned VirtReg, unsigned Hint); 1596fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen void spillAll(MachineInstr *MI); 16041e1401de5cb8752fb9d06e65e62bfe97cc1304eJakob Stoklund Olesen bool setPhysReg(MachineOperand &MO, unsigned PhysReg); 16100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen }; 16200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen char RAFast::ID = 0; 16300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 16400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 16500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen/// getStackSpaceFor - This allocates space for the specified virtual register 16600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen/// to be held on the stack. 16700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesenint RAFast::getStackSpaceFor(unsigned VirtReg, const TargetRegisterClass *RC) { 16800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen // Find the location Reg would belong... 16900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen int SS = StackSlotForVirtReg[VirtReg]; 17000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen if (SS != -1) 17100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen return SS; // Already has space allocated? 17200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 17300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen // Allocate a new stack object for this spill location... 17400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen int FrameIdx = MF->getFrameInfo()->CreateSpillStackObject(RC->getSize(), 17500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen RC->getAlignment()); 17600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 17700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen // Assign the slot. 17800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen StackSlotForVirtReg[VirtReg] = FrameIdx; 17900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen return FrameIdx; 18000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 18100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 1821e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen/// isLastUseOfLocalReg - Return true if MO is the only remaining reference to 1831e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen/// its virtual register, and it is guaranteed to be a block-local register. 1841e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen/// 1851e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesenbool RAFast::isLastUseOfLocalReg(MachineOperand &MO) { 1861e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen // Check for non-debug uses or defs following MO. 1871e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen // This is the most likely way to fail - fast path it. 188844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen MachineOperand *Next = &MO; 189844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen while ((Next = Next->getNextOperandForReg())) 190844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen if (!Next->isDebug()) 1911e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen return false; 1921e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen 1931e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen // If the register has ever been spilled or reloaded, we conservatively assume 1941e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen // it is a global register used in multiple blocks. 1951e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen if (StackSlotForVirtReg[MO.getReg()] != -1) 1961e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen return false; 1971e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen 1981e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen // Check that the use/def chain has exactly one operand - MO. 1991e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen return &MRI->reg_nodbg_begin(MO.getReg()).getOperand() == &MO; 2001e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen} 2011e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen 202804291e31658d46fb1db5ecaf42b31950c02a6f2Jakob Stoklund Olesen/// addKillFlag - Set kill flags on last use of a virtual register. 20301dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesenvoid RAFast::addKillFlag(const LiveReg &LR) { 20401dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen if (!LR.LastUse) return; 20501dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen MachineOperand &MO = LR.LastUse->getOperand(LR.LastOpNum); 20601dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen if (MO.isDef()) 20701dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen MO.setIsDead(); 20801dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen else if (!LR.LastUse->isRegTiedToDefOperand(LR.LastOpNum)) 20901dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen MO.setIsKill(); 210804291e31658d46fb1db5ecaf42b31950c02a6f2Jakob Stoklund Olesen} 211804291e31658d46fb1db5ecaf42b31950c02a6f2Jakob Stoklund Olesen 212804291e31658d46fb1db5ecaf42b31950c02a6f2Jakob Stoklund Olesen/// killVirtReg - Mark virtreg as no longer available. 213844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesenvoid RAFast::killVirtReg(LiveRegMap::iterator LRI) { 214844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen addKillFlag(LRI->second); 215844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen const LiveReg &LR = LRI->second; 216844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen assert(PhysRegState[LR.PhysReg] == LRI->first && "Broken RegState mapping"); 217804291e31658d46fb1db5ecaf42b31950c02a6f2Jakob Stoklund Olesen PhysRegState[LR.PhysReg] = regFree; 218e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen // Erase from LiveVirtRegs unless we're spilling in bulk. 219e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen if (!isBulkSpilling) 220844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen LiveVirtRegs.erase(LRI); 22176b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen} 22276b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen 22376b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen/// killVirtReg - Mark virtreg as no longer available. 224bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesenvoid RAFast::killVirtReg(unsigned VirtReg) { 225bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen assert(TargetRegisterInfo::isVirtualRegister(VirtReg) && 226bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen "killVirtReg needs a virtual register"); 227844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen LiveRegMap::iterator LRI = LiveVirtRegs.find(VirtReg); 228844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen if (LRI != LiveVirtRegs.end()) 229844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen killVirtReg(LRI); 23000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 23100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 232bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen/// spillVirtReg - This method spills the value specified by VirtReg into the 233bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen/// corresponding stack slot if needed. If isKill is set, the register is also 234bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen/// killed. 235e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesenvoid RAFast::spillVirtReg(MachineBasicBlock::iterator MI, unsigned VirtReg) { 236bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen assert(TargetRegisterInfo::isVirtualRegister(VirtReg) && 237bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen "Spilling a physical register is illegal!"); 238844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen LiveRegMap::iterator LRI = LiveVirtRegs.find(VirtReg); 239844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen assert(LRI != LiveVirtRegs.end() && "Spilling unmapped virtual register"); 240844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen spillVirtReg(MI, LRI); 2417d4f25904de543b039a28eddbea3034a5d80e7f8Jakob Stoklund Olesen} 2427d4f25904de543b039a28eddbea3034a5d80e7f8Jakob Stoklund Olesen 2437d4f25904de543b039a28eddbea3034a5d80e7f8Jakob Stoklund Olesen/// spillVirtReg - Do the actual work of spilling. 2446fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesenvoid RAFast::spillVirtReg(MachineBasicBlock::iterator MI, 245844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen LiveRegMap::iterator LRI) { 246844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen LiveReg &LR = LRI->second; 247844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen assert(PhysRegState[LR.PhysReg] == LRI->first && "Broken RegState mapping"); 24876b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen 249210e2afcc74e8ce5102d13939b23040fafa71c09Jakob Stoklund Olesen if (LR.Dirty) { 250e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen // If this physreg is used by the instruction, we want to kill it on the 251e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen // instruction, not on the spill. 252844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen bool SpillKill = LR.LastUse != MI; 253210e2afcc74e8ce5102d13939b23040fafa71c09Jakob Stoklund Olesen LR.Dirty = false; 254844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen DEBUG(dbgs() << "Spilling %reg" << LRI->first 2557d4f25904de543b039a28eddbea3034a5d80e7f8Jakob Stoklund Olesen << " in " << TRI->getName(LR.PhysReg)); 256844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen const TargetRegisterClass *RC = MRI->getRegClass(LRI->first); 257844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen int FI = getStackSpaceFor(LRI->first, RC); 2586fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen DEBUG(dbgs() << " to stack slot #" << FI << "\n"); 259844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen TII->storeRegToStackSlot(*MBB, MI, LR.PhysReg, SpillKill, FI, RC, TRI); 26000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen ++NumStores; // Update statistics 26100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 262844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen if (SpillKill) 263210e2afcc74e8ce5102d13939b23040fafa71c09Jakob Stoklund Olesen LR.LastUse = 0; // Don't kill register again 264bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 265844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen killVirtReg(LRI); 26600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 26700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 268bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen/// spillAll - Spill all dirty virtregs without killing them. 2696fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesenvoid RAFast::spillAll(MachineInstr *MI) { 270f3ea06b108d45c53dade87d6f1f48ac0a0e20562Jakob Stoklund Olesen if (LiveVirtRegs.empty()) return; 271e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen isBulkSpilling = true; 27276b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen for (LiveRegMap::iterator i = LiveVirtRegs.begin(), 27376b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen e = LiveVirtRegs.end(); i != e; ++i) 274e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen spillVirtReg(MI, i); 275e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen LiveVirtRegs.clear(); 276e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen isBulkSpilling = false; 277bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen} 27800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 2794ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen/// usePhysReg - Handle the direct use of a physical register. 2804ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen/// Check that the register is not used by a virtreg. 2814ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen/// Kill the physreg, marking it free. 2824ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen/// This may add implicit kills to MO->getParent() and invalidate MO. 2834ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesenvoid RAFast::usePhysReg(MachineOperand &MO) { 2844ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen unsigned PhysReg = MO.getReg(); 2854ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen assert(TargetRegisterInfo::isPhysicalRegister(PhysReg) && 2864ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen "Bad usePhysReg operand"); 2874ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen 2884ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen switch (PhysRegState[PhysReg]) { 289bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regDisabled: 290bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 291bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regReserved: 292bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen PhysRegState[PhysReg] = regFree; 2934ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen // Fall through 2944ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen case regFree: 2954ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen UsedInInstr.set(PhysReg); 2964ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen MO.setIsKill(); 297bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen return; 298bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen default: 2994ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen // The physreg was allocated to a virtual register. That means to value we 3004ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen // wanted has been clobbered. 3014ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen llvm_unreachable("Instruction uses an allocated register"); 30200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 30300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 3044ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen // Maybe a superregister is reserved? 305bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen for (const unsigned *AS = TRI->getAliasSet(PhysReg); 306bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned Alias = *AS; ++AS) { 3074ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen switch (PhysRegState[Alias]) { 308bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regDisabled: 309bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 310bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regReserved: 3114ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen assert(TRI->isSuperRegister(PhysReg, Alias) && 3124ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen "Instruction is not using a subregister of a reserved register"); 3134ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen // Leave the superregister in the working set. 314bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen PhysRegState[Alias] = regFree; 3154ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen UsedInInstr.set(Alias); 3164ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen MO.getParent()->addRegisterKilled(Alias, TRI, true); 3174ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen return; 3184ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen case regFree: 3194ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen if (TRI->isSuperRegister(PhysReg, Alias)) { 3204ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen // Leave the superregister in the working set. 3214ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen UsedInInstr.set(Alias); 3224ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen MO.getParent()->addRegisterKilled(Alias, TRI, true); 3234ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen return; 3244ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen } 3254ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen // Some other alias was in the working set - clear it. 3264ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen PhysRegState[Alias] = regDisabled; 327bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 328bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen default: 3294ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen llvm_unreachable("Instruction uses an alias of an allocated register"); 330bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 33100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 3324ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen 3334ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen // All aliases are disabled, bring register into working set. 3344ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen PhysRegState[PhysReg] = regFree; 3354ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen UsedInInstr.set(PhysReg); 3364ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen MO.setIsKill(); 33700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 33800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 3394ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen/// definePhysReg - Mark PhysReg as reserved or free after spilling any 3404ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen/// virtregs. This is very similar to defineVirtReg except the physreg is 3414ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen/// reserved instead of allocated. 3426fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesenvoid RAFast::definePhysReg(MachineInstr *MI, unsigned PhysReg, 3436fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen RegState NewState) { 3444ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen UsedInInstr.set(PhysReg); 345bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen switch (unsigned VirtReg = PhysRegState[PhysReg]) { 346bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regDisabled: 347bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 3484ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen default: 349e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen spillVirtReg(MI, VirtReg); 3504ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen // Fall through. 351bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regFree: 352bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regReserved: 3534ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen PhysRegState[PhysReg] = NewState; 354bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen return; 355bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 356bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen 3574ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen // This is a disabled register, disable all aliases. 3584ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen PhysRegState[PhysReg] = NewState; 359bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen for (const unsigned *AS = TRI->getAliasSet(PhysReg); 360bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned Alias = *AS; ++AS) { 3614ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen UsedInInstr.set(Alias); 362bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen switch (unsigned VirtReg = PhysRegState[Alias]) { 363bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regDisabled: 364bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 365bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen default: 366e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen spillVirtReg(MI, VirtReg); 3674ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen // Fall through. 3684ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen case regFree: 3694ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen case regReserved: 3704ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen PhysRegState[Alias] = regDisabled; 3714ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen if (TRI->isSuperRegister(PhysReg, Alias)) 3724ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen return; 373bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 374bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 375bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 376bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen} 37700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 3784ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen 379548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen// calcSpillCost - Return the cost of spilling clearing out PhysReg and 380548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen// aliases so it is free for allocation. 381548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen// Returns 0 when PhysReg is free or disabled with all aliases disabled - it 382548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen// can be allocated directly. 383548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen// Returns spillImpossible when PhysReg or an alias can't be spilled. 384548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesenunsigned RAFast::calcSpillCost(unsigned PhysReg) const { 385548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen switch (unsigned VirtReg = PhysRegState[PhysReg]) { 386548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen case regDisabled: 387548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen break; 388548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen case regFree: 389548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen return 0; 390548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen case regReserved: 391548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen return spillImpossible; 392548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen default: 393548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen return LiveVirtRegs.lookup(VirtReg).Dirty ? spillDirty : spillClean; 394548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen } 395548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen 396548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen // This is a disabled register, add up const of aliases. 397548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen unsigned Cost = 0; 398548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen for (const unsigned *AS = TRI->getAliasSet(PhysReg); 399548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen unsigned Alias = *AS; ++AS) { 400548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen switch (unsigned VirtReg = PhysRegState[Alias]) { 401548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen case regDisabled: 402548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen break; 403548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen case regFree: 404548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen ++Cost; 405548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen break; 406548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen case regReserved: 407548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen return spillImpossible; 408548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen default: 409548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen Cost += LiveVirtRegs.lookup(VirtReg).Dirty ? spillDirty : spillClean; 410548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen break; 411548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen } 412548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen } 413548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen return Cost; 414548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen} 415548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen 416548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen 41700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen/// assignVirtToPhysReg - This method updates local state so that we know 41800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen/// that PhysReg is the proper container for VirtReg now. The physical 41900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen/// register must not be used for anything else when this is called. 42000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen/// 42101dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesenvoid RAFast::assignVirtToPhysReg(LiveRegEntry &LRE, unsigned PhysReg) { 42201dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen DEBUG(dbgs() << "Assigning %reg" << LRE.first << " to " 423bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen << TRI->getName(PhysReg) << "\n"); 42401dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen PhysRegState[PhysReg] = LRE.first; 42501dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen assert(!LRE.second.PhysReg && "Already assigned a physreg"); 42601dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen LRE.second.PhysReg = PhysReg; 42700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 42800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 429bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen/// allocVirtReg - Allocate a physical register for VirtReg. 43001dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesenvoid RAFast::allocVirtReg(MachineInstr *MI, LiveRegEntry &LRE, unsigned Hint) { 43101dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen const unsigned VirtReg = LRE.first; 43201dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen 433bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen assert(TargetRegisterInfo::isVirtualRegister(VirtReg) && 434bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen "Can only allocate virtual registers"); 43500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 4364bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen const TargetRegisterClass *RC = MRI->getRegClass(VirtReg); 437bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen 4384bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen // Ignore invalid hints. 4394bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen if (Hint && (!TargetRegisterInfo::isPhysicalRegister(Hint) || 4402c13ab2bb840295ffba5f28bb1df7aa0b8d9736eChandler Carruth !RC->contains(Hint) || UsedInInstr.test(Hint) || 4412c13ab2bb840295ffba5f28bb1df7aa0b8d9736eChandler Carruth !Allocatable.test(Hint))) 4424bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen Hint = 0; 4434bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen 4444bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen // Take hint when possible. 4454bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen if (Hint) { 4464bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen assert(RC->contains(Hint) && !UsedInInstr.test(Hint) && 447efa155fd6e3820495205a09f8b9f20390d126153Jakob Stoklund Olesen Allocatable.test(Hint) && "Invalid hint should have been cleared"); 448548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen switch(calcSpillCost(Hint)) { 4494bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen default: 450548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen definePhysReg(MI, Hint, regFree); 4514bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen // Fall through. 452548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen case 0: 45301dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen return assignVirtToPhysReg(LRE, Hint); 454548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen case spillImpossible: 455548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen break; 4564bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen } 4574bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen } 4584bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen 459548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen TargetRegisterClass::iterator AOB = RC->allocation_order_begin(*MF); 460548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen TargetRegisterClass::iterator AOE = RC->allocation_order_end(*MF); 461548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen 462bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // First try to find a completely free register. 463bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen for (TargetRegisterClass::iterator I = AOB; I != AOE; ++I) { 464bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned PhysReg = *I; 465548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen if (PhysRegState[PhysReg] == regFree && !UsedInInstr.test(PhysReg)) 466548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen return assignVirtToPhysReg(LRE, PhysReg); 467bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 46800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 469c9c4dacd03a4b80d61ed6b9c6ffeb1b1f76b8d1cJakob Stoklund Olesen DEBUG(dbgs() << "Allocating %reg" << VirtReg << " from " << RC->getName() 470548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen << "\n"); 471548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen 472548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen unsigned BestReg = 0, BestCost = spillImpossible; 473548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen for (TargetRegisterClass::iterator I = AOB; I != AOE; ++I) { 474548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen unsigned Cost = calcSpillCost(*I); 475f3ea06b108d45c53dade87d6f1f48ac0a0e20562Jakob Stoklund Olesen // Cost is 0 when all aliases are already disabled. 476f3ea06b108d45c53dade87d6f1f48ac0a0e20562Jakob Stoklund Olesen if (Cost == 0) 477f3ea06b108d45c53dade87d6f1f48ac0a0e20562Jakob Stoklund Olesen return assignVirtToPhysReg(LRE, *I); 478f3ea06b108d45c53dade87d6f1f48ac0a0e20562Jakob Stoklund Olesen if (Cost < BestCost) 479f3ea06b108d45c53dade87d6f1f48ac0a0e20562Jakob Stoklund Olesen BestReg = *I, BestCost = Cost; 48000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 48100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 482bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (BestReg) { 483f3ea06b108d45c53dade87d6f1f48ac0a0e20562Jakob Stoklund Olesen definePhysReg(MI, BestReg, regFree); 48401dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen return assignVirtToPhysReg(LRE, BestReg); 485bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 48600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 487bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Nothing we can do. 488bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen std::string msg; 489bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen raw_string_ostream Msg(msg); 490bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen Msg << "Ran out of registers during register allocation!"; 491bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (MI->isInlineAsm()) { 492bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen Msg << "\nPlease check your inline asm statement for " 493bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen << "invalid constraints:\n"; 494bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen MI->print(Msg, TM); 495bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 496bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen report_fatal_error(Msg.str()); 49700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 49800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 499bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen/// defineVirtReg - Allocate a register for VirtReg and mark it as dirty. 500646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund OlesenRAFast::LiveRegMap::iterator 501646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund OlesenRAFast::defineVirtReg(MachineInstr *MI, unsigned OpNum, 502646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund Olesen unsigned VirtReg, unsigned Hint) { 503bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen assert(TargetRegisterInfo::isVirtualRegister(VirtReg) && 504bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen "Not a virtual register"); 505844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen LiveRegMap::iterator LRI; 50601dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen bool New; 507844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen tie(LRI, New) = LiveVirtRegs.insert(std::make_pair(VirtReg, LiveReg())); 508844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen LiveReg &LR = LRI->second; 5090c9e4f5f3ff139733d74462a0ad5b94014e764a8Jakob Stoklund Olesen if (New) { 5100c9e4f5f3ff139733d74462a0ad5b94014e764a8Jakob Stoklund Olesen // If there is no hint, peek at the only use of this register. 5110c9e4f5f3ff139733d74462a0ad5b94014e764a8Jakob Stoklund Olesen if ((!Hint || !TargetRegisterInfo::isPhysicalRegister(Hint)) && 5120c9e4f5f3ff139733d74462a0ad5b94014e764a8Jakob Stoklund Olesen MRI->hasOneNonDBGUse(VirtReg)) { 5130c9e4f5f3ff139733d74462a0ad5b94014e764a8Jakob Stoklund Olesen unsigned SrcReg, DstReg, SrcSubReg, DstSubReg; 5140c9e4f5f3ff139733d74462a0ad5b94014e764a8Jakob Stoklund Olesen // It's a copy, use the destination register as a hint. 5150c9e4f5f3ff139733d74462a0ad5b94014e764a8Jakob Stoklund Olesen if (TII->isMoveInstr(*MRI->use_nodbg_begin(VirtReg), 5160c9e4f5f3ff139733d74462a0ad5b94014e764a8Jakob Stoklund Olesen SrcReg, DstReg, SrcSubReg, DstSubReg)) 5170c9e4f5f3ff139733d74462a0ad5b94014e764a8Jakob Stoklund Olesen Hint = DstReg; 5180c9e4f5f3ff139733d74462a0ad5b94014e764a8Jakob Stoklund Olesen } 519844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen allocVirtReg(MI, *LRI, Hint); 5200c9e4f5f3ff139733d74462a0ad5b94014e764a8Jakob Stoklund Olesen } else 52101dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen addKillFlag(LR); // Kill before redefine. 52201dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen assert(LR.PhysReg && "Register not assigned"); 523210e2afcc74e8ce5102d13939b23040fafa71c09Jakob Stoklund Olesen LR.LastUse = MI; 524210e2afcc74e8ce5102d13939b23040fafa71c09Jakob Stoklund Olesen LR.LastOpNum = OpNum; 525210e2afcc74e8ce5102d13939b23040fafa71c09Jakob Stoklund Olesen LR.Dirty = true; 526210e2afcc74e8ce5102d13939b23040fafa71c09Jakob Stoklund Olesen UsedInInstr.set(LR.PhysReg); 527646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund Olesen return LRI; 528bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen} 52900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 530bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen/// reloadVirtReg - Make sure VirtReg is available in a physreg and return it. 531646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund OlesenRAFast::LiveRegMap::iterator 532646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund OlesenRAFast::reloadVirtReg(MachineInstr *MI, unsigned OpNum, 533646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund Olesen unsigned VirtReg, unsigned Hint) { 534bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen assert(TargetRegisterInfo::isVirtualRegister(VirtReg) && 535bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen "Not a virtual register"); 536844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen LiveRegMap::iterator LRI; 53701dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen bool New; 538844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen tie(LRI, New) = LiveVirtRegs.insert(std::make_pair(VirtReg, LiveReg())); 539844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen LiveReg &LR = LRI->second; 540ac3e529831877cea609ed668f95b1dc06e34698cJakob Stoklund Olesen MachineOperand &MO = MI->getOperand(OpNum); 54101dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen if (New) { 542844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen allocVirtReg(MI, *LRI, Hint); 5434bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen const TargetRegisterClass *RC = MRI->getRegClass(VirtReg); 544bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen int FrameIndex = getStackSpaceFor(VirtReg, RC); 545c9c4dacd03a4b80d61ed6b9c6ffeb1b1f76b8d1cJakob Stoklund Olesen DEBUG(dbgs() << "Reloading %reg" << VirtReg << " into " 54601dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen << TRI->getName(LR.PhysReg) << "\n"); 54701dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen TII->loadRegFromStackSlot(*MBB, MI, LR.PhysReg, FrameIndex, RC, TRI); 548bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen ++NumLoads; 54901dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen } else if (LR.Dirty) { 5501e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen if (isLastUseOfLocalReg(MO)) { 5511e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen DEBUG(dbgs() << "Killing last use: " << MO << "\n"); 5521e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen MO.setIsKill(); 5531e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen } else if (MO.isKill()) { 5541e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen DEBUG(dbgs() << "Clearing dubious kill: " << MO << "\n"); 5551e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen MO.setIsKill(false); 5561e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen } 557ac3e529831877cea609ed668f95b1dc06e34698cJakob Stoklund Olesen } else if (MO.isKill()) { 558ac3e529831877cea609ed668f95b1dc06e34698cJakob Stoklund Olesen // We must remove kill flags from uses of reloaded registers because the 559ac3e529831877cea609ed668f95b1dc06e34698cJakob Stoklund Olesen // register would be killed immediately, and there might be a second use: 560ac3e529831877cea609ed668f95b1dc06e34698cJakob Stoklund Olesen // %foo = OR %x<kill>, %x 561ac3e529831877cea609ed668f95b1dc06e34698cJakob Stoklund Olesen // This would cause a second reload of %x into a different register. 562ac3e529831877cea609ed668f95b1dc06e34698cJakob Stoklund Olesen DEBUG(dbgs() << "Clearing clean kill: " << MO << "\n"); 563ac3e529831877cea609ed668f95b1dc06e34698cJakob Stoklund Olesen MO.setIsKill(false); 56400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 56501dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen assert(LR.PhysReg && "Register not assigned"); 566210e2afcc74e8ce5102d13939b23040fafa71c09Jakob Stoklund Olesen LR.LastUse = MI; 567210e2afcc74e8ce5102d13939b23040fafa71c09Jakob Stoklund Olesen LR.LastOpNum = OpNum; 568210e2afcc74e8ce5102d13939b23040fafa71c09Jakob Stoklund Olesen UsedInInstr.set(LR.PhysReg); 569646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund Olesen return LRI; 570bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen} 57100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 572bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen// setPhysReg - Change MO the refer the PhysReg, considering subregs. 57341e1401de5cb8752fb9d06e65e62bfe97cc1304eJakob Stoklund Olesen// This may invalidate MO if it is necessary to add implicit kills for a 57441e1401de5cb8752fb9d06e65e62bfe97cc1304eJakob Stoklund Olesen// superregister. 57541e1401de5cb8752fb9d06e65e62bfe97cc1304eJakob Stoklund Olesen// Return tru if MO kills its register. 57641e1401de5cb8752fb9d06e65e62bfe97cc1304eJakob Stoklund Olesenbool RAFast::setPhysReg(MachineOperand &MO, unsigned PhysReg) { 57741e1401de5cb8752fb9d06e65e62bfe97cc1304eJakob Stoklund Olesen if (!MO.getSubReg()) { 578bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen MO.setReg(PhysReg); 57941e1401de5cb8752fb9d06e65e62bfe97cc1304eJakob Stoklund Olesen return MO.isKill() || MO.isDead(); 58041e1401de5cb8752fb9d06e65e62bfe97cc1304eJakob Stoklund Olesen } 58141e1401de5cb8752fb9d06e65e62bfe97cc1304eJakob Stoklund Olesen 58241e1401de5cb8752fb9d06e65e62bfe97cc1304eJakob Stoklund Olesen // Handle subregister index. 58341e1401de5cb8752fb9d06e65e62bfe97cc1304eJakob Stoklund Olesen MO.setReg(PhysReg ? TRI->getSubReg(PhysReg, MO.getSubReg()) : 0); 58441e1401de5cb8752fb9d06e65e62bfe97cc1304eJakob Stoklund Olesen MO.setSubReg(0); 58541e1401de5cb8752fb9d06e65e62bfe97cc1304eJakob Stoklund Olesen if (MO.isUse()) { 58641e1401de5cb8752fb9d06e65e62bfe97cc1304eJakob Stoklund Olesen if (MO.isKill()) { 58741e1401de5cb8752fb9d06e65e62bfe97cc1304eJakob Stoklund Olesen MO.getParent()->addRegisterKilled(PhysReg, TRI, true); 58841e1401de5cb8752fb9d06e65e62bfe97cc1304eJakob Stoklund Olesen return true; 58941e1401de5cb8752fb9d06e65e62bfe97cc1304eJakob Stoklund Olesen } 59041e1401de5cb8752fb9d06e65e62bfe97cc1304eJakob Stoklund Olesen return false; 59141e1401de5cb8752fb9d06e65e62bfe97cc1304eJakob Stoklund Olesen } 59241e1401de5cb8752fb9d06e65e62bfe97cc1304eJakob Stoklund Olesen // A subregister def implicitly defines the whole physreg. 59341e1401de5cb8752fb9d06e65e62bfe97cc1304eJakob Stoklund Olesen if (MO.isDead()) { 59441e1401de5cb8752fb9d06e65e62bfe97cc1304eJakob Stoklund Olesen MO.getParent()->addRegisterDead(PhysReg, TRI, true); 59541e1401de5cb8752fb9d06e65e62bfe97cc1304eJakob Stoklund Olesen return true; 59641e1401de5cb8752fb9d06e65e62bfe97cc1304eJakob Stoklund Olesen } 59741e1401de5cb8752fb9d06e65e62bfe97cc1304eJakob Stoklund Olesen MO.getParent()->addRegisterDefined(PhysReg, TRI); 59841e1401de5cb8752fb9d06e65e62bfe97cc1304eJakob Stoklund Olesen return false; 59900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 60000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 6016fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesenvoid RAFast::AllocateBasicBlock() { 6026fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen DEBUG(dbgs() << "\nAllocating " << *MBB); 60300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 604bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen PhysRegState.assign(TRI->getNumRegs(), regDisabled); 60576b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen assert(LiveVirtRegs.empty() && "Mapping not cleared form last block?"); 60600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 6076fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen MachineBasicBlock::iterator MII = MBB->begin(); 608bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen 609bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Add live-in registers as live. 6106fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen for (MachineBasicBlock::livein_iterator I = MBB->livein_begin(), 6116fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen E = MBB->livein_end(); I != E; ++I) 6126fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen definePhysReg(MII, *I, regReserved); 613bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen 614ac3e529831877cea609ed668f95b1dc06e34698cJakob Stoklund Olesen SmallVector<unsigned, 8> PhysECs; 6157ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen SmallVector<MachineInstr*, 32> Coalesced; 61600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 61700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen // Otherwise, sequentially allocate each instruction in the MBB. 6186fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen while (MII != MBB->end()) { 61900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen MachineInstr *MI = MII++; 62000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen const TargetInstrDesc &TID = MI->getDesc(); 62100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen DEBUG({ 622c9c4dacd03a4b80d61ed6b9c6ffeb1b1f76b8d1cJakob Stoklund Olesen dbgs() << "\n>> " << *MI << "Regs:"; 623bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen for (unsigned Reg = 1, E = TRI->getNumRegs(); Reg != E; ++Reg) { 624bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (PhysRegState[Reg] == regDisabled) continue; 625bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen dbgs() << " " << TRI->getName(Reg); 626bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen switch(PhysRegState[Reg]) { 627bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regFree: 628bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 629bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regReserved: 630c9c4dacd03a4b80d61ed6b9c6ffeb1b1f76b8d1cJakob Stoklund Olesen dbgs() << "*"; 631bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 632bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen default: 633bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen dbgs() << "=%reg" << PhysRegState[Reg]; 634210e2afcc74e8ce5102d13939b23040fafa71c09Jakob Stoklund Olesen if (LiveVirtRegs[PhysRegState[Reg]].Dirty) 635bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen dbgs() << "*"; 63676b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen assert(LiveVirtRegs[PhysRegState[Reg]].PhysReg == Reg && 637bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen "Bad inverse map"); 638bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 639bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 640bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 64100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen dbgs() << '\n'; 64276b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen // Check that LiveVirtRegs is the inverse. 64376b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen for (LiveRegMap::iterator i = LiveVirtRegs.begin(), 64476b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen e = LiveVirtRegs.end(); i != e; ++i) { 645bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen assert(TargetRegisterInfo::isVirtualRegister(i->first) && 646bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen "Bad map key"); 64776b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen assert(TargetRegisterInfo::isPhysicalRegister(i->second.PhysReg) && 648bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen "Bad map value"); 64976b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen assert(PhysRegState[i->second.PhysReg] == i->first && 65076b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen "Bad inverse map"); 651bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 65200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen }); 65300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 654bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Debug values are not allowed to change codegen in any way. 655bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (MI->isDebugValue()) { 65600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 65700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen MachineOperand &MO = MI->getOperand(i); 658bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (!MO.isReg()) continue; 659bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned Reg = MO.getReg(); 660bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (!Reg || TargetRegisterInfo::isPhysicalRegister(Reg)) continue; 661844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen LiveRegMap::iterator LRI = LiveVirtRegs.find(Reg); 662844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen if (LRI != LiveVirtRegs.end()) 663844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen setPhysReg(MO, LRI->second.PhysReg); 66476b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen else 66576b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen MO.setReg(0); // We can't allocate a physreg for a DebugValue, sorry! 66600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 667bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Next instruction. 668bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen continue; 66900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 67000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 6714bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen // If this is a copy, we may be able to coalesce. 6724bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen unsigned CopySrc, CopyDst, CopySrcSub, CopyDstSub; 6734bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen if (!TII->isMoveInstr(*MI, CopySrc, CopyDst, CopySrcSub, CopyDstSub)) 6744bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen CopySrc = CopyDst = 0; 6754bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen 676bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Track registers used by instruction. 677bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen UsedInInstr.reset(); 678ac3e529831877cea609ed668f95b1dc06e34698cJakob Stoklund Olesen PhysECs.clear(); 67900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 680bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // First scan. 681bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Mark physreg uses and early clobbers as used. 682e97dda4fc58ee401ebb4aa9153d10f8ce8ba9a70Jakob Stoklund Olesen // Find the end of the virtreg operands 683e97dda4fc58ee401ebb4aa9153d10f8ce8ba9a70Jakob Stoklund Olesen unsigned VirtOpEnd = 0; 684bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 68500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen MachineOperand &MO = MI->getOperand(i); 686bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (!MO.isReg()) continue; 687bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned Reg = MO.getReg(); 688e97dda4fc58ee401ebb4aa9153d10f8ce8ba9a70Jakob Stoklund Olesen if (!Reg) continue; 689e97dda4fc58ee401ebb4aa9153d10f8ce8ba9a70Jakob Stoklund Olesen if (TargetRegisterInfo::isVirtualRegister(Reg)) { 690e97dda4fc58ee401ebb4aa9153d10f8ce8ba9a70Jakob Stoklund Olesen VirtOpEnd = i+1; 691e97dda4fc58ee401ebb4aa9153d10f8ce8ba9a70Jakob Stoklund Olesen continue; 692e97dda4fc58ee401ebb4aa9153d10f8ce8ba9a70Jakob Stoklund Olesen } 693efa155fd6e3820495205a09f8b9f20390d126153Jakob Stoklund Olesen if (!Allocatable.test(Reg)) continue; 694bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (MO.isUse()) { 6954ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen usePhysReg(MO); 696bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } else if (MO.isEarlyClobber()) { 6976fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen definePhysReg(MI, Reg, MO.isDead() ? regFree : regReserved); 698ac3e529831877cea609ed668f95b1dc06e34698cJakob Stoklund Olesen PhysECs.push_back(Reg); 69900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 70000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 70100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 702bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Second scan. 703bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Allocate virtreg uses and early clobbers. 704bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Collect VirtKills 705e97dda4fc58ee401ebb4aa9153d10f8ce8ba9a70Jakob Stoklund Olesen for (unsigned i = 0; i != VirtOpEnd; ++i) { 70600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen MachineOperand &MO = MI->getOperand(i); 707bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (!MO.isReg()) continue; 70800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen unsigned Reg = MO.getReg(); 709bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (!Reg || TargetRegisterInfo::isPhysicalRegister(Reg)) continue; 710bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (MO.isUse()) { 711646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund Olesen LiveRegMap::iterator LRI = reloadVirtReg(MI, i, Reg, CopyDst); 712646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund Olesen unsigned PhysReg = LRI->second.PhysReg; 7137ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen CopySrc = (CopySrc == Reg || CopySrc == PhysReg) ? PhysReg : 0; 71441e1401de5cb8752fb9d06e65e62bfe97cc1304eJakob Stoklund Olesen if (setPhysReg(MO, PhysReg)) 715646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund Olesen killVirtReg(LRI); 716bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } else if (MO.isEarlyClobber()) { 717646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund Olesen LiveRegMap::iterator LRI = defineVirtReg(MI, i, Reg, 0); 718646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund Olesen unsigned PhysReg = LRI->second.PhysReg; 719bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen setPhysReg(MO, PhysReg); 720ac3e529831877cea609ed668f95b1dc06e34698cJakob Stoklund Olesen PhysECs.push_back(PhysReg); 72100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 72200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 72300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 7244bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen MRI->addPhysRegsUsed(UsedInInstr); 72582b07dc4995d48065bd95affff4d8513a5cad4f2Jakob Stoklund Olesen 726bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Track registers defined by instruction - early clobbers at this point. 727bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen UsedInInstr.reset(); 728ac3e529831877cea609ed668f95b1dc06e34698cJakob Stoklund Olesen for (unsigned i = 0, e = PhysECs.size(); i != e; ++i) { 729ac3e529831877cea609ed668f95b1dc06e34698cJakob Stoklund Olesen unsigned PhysReg = PhysECs[i]; 730bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen UsedInInstr.set(PhysReg); 731bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen for (const unsigned *AS = TRI->getAliasSet(PhysReg); 732bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned Alias = *AS; ++AS) 733bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen UsedInInstr.set(Alias); 73400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 73500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 7364b6bbe885d851b1cfba2be9b5efc6365a2b7828aJakob Stoklund Olesen unsigned DefOpEnd = MI->getNumOperands(); 7374b6bbe885d851b1cfba2be9b5efc6365a2b7828aJakob Stoklund Olesen if (TID.isCall()) { 7384b6bbe885d851b1cfba2be9b5efc6365a2b7828aJakob Stoklund Olesen // Spill all virtregs before a call. This serves two purposes: 1. If an 7394b6bbe885d851b1cfba2be9b5efc6365a2b7828aJakob Stoklund Olesen // exception is thrown, the landing pad is going to expect to find registers 7404b6bbe885d851b1cfba2be9b5efc6365a2b7828aJakob Stoklund Olesen // in their spill slots, and 2. we don't have to wade through all the 7414b6bbe885d851b1cfba2be9b5efc6365a2b7828aJakob Stoklund Olesen // <imp-def> operands on the call instruction. 7424b6bbe885d851b1cfba2be9b5efc6365a2b7828aJakob Stoklund Olesen DefOpEnd = VirtOpEnd; 7434b6bbe885d851b1cfba2be9b5efc6365a2b7828aJakob Stoklund Olesen DEBUG(dbgs() << " Spilling remaining registers before call.\n"); 7444b6bbe885d851b1cfba2be9b5efc6365a2b7828aJakob Stoklund Olesen spillAll(MI); 7454b6bbe885d851b1cfba2be9b5efc6365a2b7828aJakob Stoklund Olesen } 7464b6bbe885d851b1cfba2be9b5efc6365a2b7828aJakob Stoklund Olesen 747bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Third scan. 748bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Allocate defs and collect dead defs. 7494b6bbe885d851b1cfba2be9b5efc6365a2b7828aJakob Stoklund Olesen for (unsigned i = 0; i != DefOpEnd; ++i) { 75000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen MachineOperand &MO = MI->getOperand(i); 751bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (!MO.isReg() || !MO.isDef() || !MO.getReg()) continue; 752bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned Reg = MO.getReg(); 75300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 754bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (TargetRegisterInfo::isPhysicalRegister(Reg)) { 755efa155fd6e3820495205a09f8b9f20390d126153Jakob Stoklund Olesen if (!Allocatable.test(Reg)) continue; 7566fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen definePhysReg(MI, Reg, (MO.isImplicit() || MO.isDead()) ? 7576fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen regFree : regReserved); 758bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen continue; 75900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 760646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund Olesen LiveRegMap::iterator LRI = defineVirtReg(MI, i, Reg, CopySrc); 761646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund Olesen unsigned PhysReg = LRI->second.PhysReg; 76241e1401de5cb8752fb9d06e65e62bfe97cc1304eJakob Stoklund Olesen if (setPhysReg(MO, PhysReg)) { 763646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund Olesen killVirtReg(LRI); 7647ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen CopyDst = 0; // cancel coalescing; 7657ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen } else 7667ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen CopyDst = (CopyDst == Reg || CopyDst == PhysReg) ? PhysReg : 0; 76700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 76800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 7694bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen MRI->addPhysRegsUsed(UsedInInstr); 770c9c4dacd03a4b80d61ed6b9c6ffeb1b1f76b8d1cJakob Stoklund Olesen 7717ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen if (CopyDst && CopyDst == CopySrc && CopyDstSub == CopySrcSub) { 7727ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen DEBUG(dbgs() << "-- coalescing: " << *MI); 7737ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen Coalesced.push_back(MI); 7747ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen } else { 7757ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen DEBUG(dbgs() << "<< " << *MI); 7767ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen } 77700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 77800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 779bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Spill all physical registers holding virtual registers now. 780e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen DEBUG(dbgs() << "Spilling live registers at end of block.\n"); 781e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen spillAll(MBB->getFirstTerminator()); 78200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 7837ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen // Erase all the coalesced copies. We are delaying it until now because 784e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen // LiveVirtRegs might refer to the instrs. 7857ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen for (unsigned i = 0, e = Coalesced.size(); i != e; ++i) 7866fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen MBB->erase(Coalesced[i]); 7878a65c510a4fa1245d101da6318618d025702028cJakob Stoklund Olesen NumCopies += Coalesced.size(); 7887ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen 7896fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen DEBUG(MBB->dump()); 79000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 79100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 79200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen/// runOnMachineFunction - Register allocate the whole function 79300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen/// 79400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesenbool RAFast::runOnMachineFunction(MachineFunction &Fn) { 795c9c4dacd03a4b80d61ed6b9c6ffeb1b1f76b8d1cJakob Stoklund Olesen DEBUG(dbgs() << "********** FAST REGISTER ALLOCATION **********\n" 796c9c4dacd03a4b80d61ed6b9c6ffeb1b1f76b8d1cJakob Stoklund Olesen << "********** Function: " 797c9c4dacd03a4b80d61ed6b9c6ffeb1b1f76b8d1cJakob Stoklund Olesen << ((Value*)Fn.getFunction())->getName() << '\n'); 7981b2c761a9cc9a57b417c676f4bd97d11b6ba1869Jakob Stoklund Olesen if (VerifyFastRegalloc) 799a0e618de5d9b40e5b5189c299086487e5ad767f2Jakob Stoklund Olesen Fn.verify(this, true); 80000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen MF = &Fn; 8014bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen MRI = &MF->getRegInfo(); 80200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen TM = &Fn.getTarget(); 80300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen TRI = TM->getRegisterInfo(); 80400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen TII = TM->getInstrInfo(); 80500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 80600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen UsedInInstr.resize(TRI->getNumRegs()); 807efa155fd6e3820495205a09f8b9f20390d126153Jakob Stoklund Olesen Allocatable = TRI->getAllocatableSet(*MF); 80800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 80900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen // initialize the virtual->physical register map to have a 'null' 81000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen // mapping for all virtual registers 8114bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen unsigned LastVirtReg = MRI->getLastVirtReg(); 81200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen StackSlotForVirtReg.grow(LastVirtReg); 81300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 81400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen // Loop over all of the basic blocks, eliminating virtual register references 8156fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen for (MachineFunction::iterator MBBi = Fn.begin(), MBBe = Fn.end(); 8166fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen MBBi != MBBe; ++MBBi) { 8176fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen MBB = &*MBBi; 8186fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen AllocateBasicBlock(); 8196fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen } 82000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 82182b07dc4995d48065bd95affff4d8513a5cad4f2Jakob Stoklund Olesen // Make sure the set of used physregs is closed under subreg operations. 8224bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen MRI->closePhysRegsUsed(*TRI); 82382b07dc4995d48065bd95affff4d8513a5cad4f2Jakob Stoklund Olesen 82400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen StackSlotForVirtReg.clear(); 82500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen return true; 82600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 82700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 82800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund OlesenFunctionPass *llvm::createFastRegisterAllocator() { 82900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen return new RAFast(); 83000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 831