RegAllocFast.cpp revision f299da8ec3fee88a1b275560a7f94be4cf10d089
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" 19459a36bd34809ffc5d74de79b3e46f6e02e5184fDevang Patel#include "llvm/CodeGen/MachineInstrBuilder.h" 2000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include "llvm/CodeGen/MachineFrameInfo.h" 2100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include "llvm/CodeGen/MachineRegisterInfo.h" 2200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include "llvm/CodeGen/Passes.h" 2300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include "llvm/CodeGen/RegAllocRegistry.h" 2400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include "llvm/Target/TargetInstrInfo.h" 2500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include "llvm/Target/TargetMachine.h" 2600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include "llvm/Support/CommandLine.h" 2700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include "llvm/Support/Debug.h" 2800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include "llvm/Support/ErrorHandling.h" 2900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include "llvm/Support/raw_ostream.h" 3000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include "llvm/ADT/DenseMap.h" 3100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include "llvm/ADT/IndexedMap.h" 3200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include "llvm/ADT/SmallSet.h" 3300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include "llvm/ADT/SmallVector.h" 3400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include "llvm/ADT/Statistic.h" 3500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include "llvm/ADT/STLExtras.h" 3600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include <algorithm> 3700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesenusing namespace llvm; 3800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 3900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund OlesenSTATISTIC(NumStores, "Number of stores added"); 4000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund OlesenSTATISTIC(NumLoads , "Number of loads added"); 418a65c510a4fa1245d101da6318618d025702028cJakob Stoklund OlesenSTATISTIC(NumCopies, "Number of copies coalesced"); 4200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 4300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesenstatic RegisterRegAlloc 4400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen fastRegAlloc("fast", "fast register allocator", createFastRegisterAllocator); 4500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 4600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesennamespace { 4700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen class RAFast : public MachineFunctionPass { 4800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen public: 4900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen static char ID; 5090c579de5a383cee278acc3f7e7b9d0a656e6a35Owen Anderson RAFast() : MachineFunctionPass(ID), StackSlotForVirtReg(-1), 51081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson isBulkSpilling(false) { 52081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializePHIEliminationPass(*PassRegistry::getPassRegistry()); 53081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeTwoAddressInstructionPassPass(*PassRegistry::getPassRegistry()); 54081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson } 5500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen private: 5600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen const TargetMachine *TM; 5700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen MachineFunction *MF; 584bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen MachineRegisterInfo *MRI; 5900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen const TargetRegisterInfo *TRI; 6000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen const TargetInstrInfo *TII; 6100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 626fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen // Basic block currently being allocated. 636fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen MachineBasicBlock *MBB; 646fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen 6500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen // StackSlotForVirtReg - Maps virtual regs to the frame index where these 6600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen // values are spilled. 6700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen IndexedMap<int, VirtReg2IndexFunctor> StackSlotForVirtReg; 6800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 6976b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen // Everything we know about a live virtual register. 7076b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen struct LiveReg { 71210e2afcc74e8ce5102d13939b23040fafa71c09Jakob Stoklund Olesen MachineInstr *LastUse; // Last instr to use reg. 72210e2afcc74e8ce5102d13939b23040fafa71c09Jakob Stoklund Olesen unsigned PhysReg; // Currently held here. 73210e2afcc74e8ce5102d13939b23040fafa71c09Jakob Stoklund Olesen unsigned short LastOpNum; // OpNum on LastUse. 74210e2afcc74e8ce5102d13939b23040fafa71c09Jakob Stoklund Olesen bool Dirty; // Register needs spill. 7576b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen 76210e2afcc74e8ce5102d13939b23040fafa71c09Jakob Stoklund Olesen LiveReg(unsigned p=0) : LastUse(0), PhysReg(p), LastOpNum(0), 7701dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen Dirty(false) {} 7876b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen }; 7976b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen 8076b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen typedef DenseMap<unsigned, LiveReg> LiveRegMap; 8101dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen typedef LiveRegMap::value_type LiveRegEntry; 8276b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen 8376b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen // LiveVirtRegs - This map contains entries for each virtual register 8400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen // that is currently available in a physical register. 8576b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen LiveRegMap LiveVirtRegs; 8600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 87459a36bd34809ffc5d74de79b3e46f6e02e5184fDevang Patel DenseMap<unsigned, MachineInstr *> LiveDbgValueMap; 88459a36bd34809ffc5d74de79b3e46f6e02e5184fDevang Patel 89bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // RegState - Track the state of a physical register. 90bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen enum RegState { 91bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // A disabled register is not available for allocation, but an alias may 92bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // be in use. A register can only be moved out of the disabled state if 93bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // all aliases are disabled. 94bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen regDisabled, 95bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen 96bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // A free register is not currently in use and can be allocated 97bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // immediately without checking aliases. 98bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen regFree, 99bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen 100bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // A reserved register has been assigned expolicitly (e.g., setting up a 101bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // call parameter), and it remains reserved until it is used. 102bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen regReserved 10300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 104bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // A register state may also be a virtual register number, indication that 105bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // the physical register is currently allocated to a virtual register. In 10676b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen // that case, LiveVirtRegs contains the inverse mapping. 107bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen }; 108bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen 109bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // PhysRegState - One of the RegState enums, or a virtreg. 110bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen std::vector<unsigned> PhysRegState; 11100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 11200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen // UsedInInstr - BitVector of physregs that are used in the current 11300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen // instruction, and so cannot be allocated. 11400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen BitVector UsedInInstr; 11500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 116efa155fd6e3820495205a09f8b9f20390d126153Jakob Stoklund Olesen // Allocatable - vector of allocatable physical registers. 117efa155fd6e3820495205a09f8b9f20390d126153Jakob Stoklund Olesen BitVector Allocatable; 11800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 11907cb689d6260b78861d829bb05b188e1558c528eJim Grosbach // SkippedInstrs - Descriptors of instructions whose clobber list was 12007cb689d6260b78861d829bb05b188e1558c528eJim Grosbach // ignored because all registers were spilled. It is still necessary to 12107cb689d6260b78861d829bb05b188e1558c528eJim Grosbach // mark all the clobbered registers as used by the function. 1226de07178e1e6445080bf4f7704e274c5f219ff70Jakob Stoklund Olesen SmallPtrSet<const TargetInstrDesc*, 4> SkippedInstrs; 1236de07178e1e6445080bf4f7704e274c5f219ff70Jakob Stoklund Olesen 124e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen // isBulkSpilling - This flag is set when LiveRegMap will be cleared 125e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen // completely after spilling all live registers. LiveRegMap entries should 126e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen // not be erased. 127e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen bool isBulkSpilling; 1287d4f25904de543b039a28eddbea3034a5d80e7f8Jakob Stoklund Olesen 129548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen enum { 130548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen spillClean = 1, 131548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen spillDirty = 100, 132548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen spillImpossible = ~0u 133548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen }; 13400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen public: 13500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen virtual const char *getPassName() const { 13600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen return "Fast Register Allocator"; 13700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 13800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 13900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen virtual void getAnalysisUsage(AnalysisUsage &AU) const { 14000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen AU.setPreservesCFG(); 14100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen AU.addRequiredID(PHIEliminationID); 14200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen AU.addRequiredID(TwoAddressInstructionPassID); 14300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen MachineFunctionPass::getAnalysisUsage(AU); 14400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 14500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 14600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen private: 14700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen bool runOnMachineFunction(MachineFunction &Fn); 1486fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen void AllocateBasicBlock(); 149d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen void handleThroughOperands(MachineInstr *MI, 150d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen SmallVectorImpl<unsigned> &VirtDead); 15100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen int getStackSpaceFor(unsigned VirtReg, const TargetRegisterClass *RC); 1521e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen bool isLastUseOfLocalReg(MachineOperand&); 1531e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen 15401dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen void addKillFlag(const LiveReg&); 155844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen void killVirtReg(LiveRegMap::iterator); 156804291e31658d46fb1db5ecaf42b31950c02a6f2Jakob Stoklund Olesen void killVirtReg(unsigned VirtReg); 157844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen void spillVirtReg(MachineBasicBlock::iterator MI, LiveRegMap::iterator); 158e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen void spillVirtReg(MachineBasicBlock::iterator MI, unsigned VirtReg); 1594ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen 1604ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen void usePhysReg(MachineOperand&); 1616fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen void definePhysReg(MachineInstr *MI, unsigned PhysReg, RegState NewState); 162548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen unsigned calcSpillCost(unsigned PhysReg) const; 16301dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen void assignVirtToPhysReg(LiveRegEntry &LRE, unsigned PhysReg); 16401dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen void allocVirtReg(MachineInstr *MI, LiveRegEntry &LRE, unsigned Hint); 165646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund Olesen LiveRegMap::iterator defineVirtReg(MachineInstr *MI, unsigned OpNum, 166646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund Olesen unsigned VirtReg, unsigned Hint); 167646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund Olesen LiveRegMap::iterator reloadVirtReg(MachineInstr *MI, unsigned OpNum, 168646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund Olesen unsigned VirtReg, unsigned Hint); 1696fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen void spillAll(MachineInstr *MI); 1700eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen bool setPhysReg(MachineInstr *MI, unsigned OpNum, unsigned PhysReg); 17100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen }; 17200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen char RAFast::ID = 0; 17300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 17400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 17500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen/// getStackSpaceFor - This allocates space for the specified virtual register 17600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen/// to be held on the stack. 17700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesenint RAFast::getStackSpaceFor(unsigned VirtReg, const TargetRegisterClass *RC) { 17800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen // Find the location Reg would belong... 17900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen int SS = StackSlotForVirtReg[VirtReg]; 18000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen if (SS != -1) 18100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen return SS; // Already has space allocated? 18200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 18300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen // Allocate a new stack object for this spill location... 18400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen int FrameIdx = MF->getFrameInfo()->CreateSpillStackObject(RC->getSize(), 18500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen RC->getAlignment()); 18600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 18700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen // Assign the slot. 18800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen StackSlotForVirtReg[VirtReg] = FrameIdx; 18900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen return FrameIdx; 19000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 19100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 1921e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen/// isLastUseOfLocalReg - Return true if MO is the only remaining reference to 1931e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen/// its virtual register, and it is guaranteed to be a block-local register. 1941e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen/// 1951e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesenbool RAFast::isLastUseOfLocalReg(MachineOperand &MO) { 1961e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen // Check for non-debug uses or defs following MO. 1971e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen // This is the most likely way to fail - fast path it. 198844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen MachineOperand *Next = &MO; 199844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen while ((Next = Next->getNextOperandForReg())) 200844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen if (!Next->isDebug()) 2011e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen return false; 2021e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen 2031e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen // If the register has ever been spilled or reloaded, we conservatively assume 2041e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen // it is a global register used in multiple blocks. 2051e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen if (StackSlotForVirtReg[MO.getReg()] != -1) 2061e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen return false; 2071e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen 2081e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen // Check that the use/def chain has exactly one operand - MO. 2091e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen return &MRI->reg_nodbg_begin(MO.getReg()).getOperand() == &MO; 2101e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen} 2111e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen 212804291e31658d46fb1db5ecaf42b31950c02a6f2Jakob Stoklund Olesen/// addKillFlag - Set kill flags on last use of a virtual register. 21301dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesenvoid RAFast::addKillFlag(const LiveReg &LR) { 21401dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen if (!LR.LastUse) return; 21501dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen MachineOperand &MO = LR.LastUse->getOperand(LR.LastOpNum); 216d32e735ae6e3fbebcae9a23d7cda091770bb3a14Jakob Stoklund Olesen if (MO.isUse() && !LR.LastUse->isRegTiedToDefOperand(LR.LastOpNum)) { 217d32e735ae6e3fbebcae9a23d7cda091770bb3a14Jakob Stoklund Olesen if (MO.getReg() == LR.PhysReg) 2180eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen MO.setIsKill(); 2190eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen else 2200eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen LR.LastUse->addRegisterKilled(LR.PhysReg, TRI, true); 2210eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen } 222804291e31658d46fb1db5ecaf42b31950c02a6f2Jakob Stoklund Olesen} 223804291e31658d46fb1db5ecaf42b31950c02a6f2Jakob Stoklund Olesen 224804291e31658d46fb1db5ecaf42b31950c02a6f2Jakob Stoklund Olesen/// killVirtReg - Mark virtreg as no longer available. 225844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesenvoid RAFast::killVirtReg(LiveRegMap::iterator LRI) { 226844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen addKillFlag(LRI->second); 227844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen const LiveReg &LR = LRI->second; 228844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen assert(PhysRegState[LR.PhysReg] == LRI->first && "Broken RegState mapping"); 229804291e31658d46fb1db5ecaf42b31950c02a6f2Jakob Stoklund Olesen PhysRegState[LR.PhysReg] = regFree; 230e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen // Erase from LiveVirtRegs unless we're spilling in bulk. 231e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen if (!isBulkSpilling) 232844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen LiveVirtRegs.erase(LRI); 23376b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen} 23476b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen 23576b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen/// killVirtReg - Mark virtreg as no longer available. 236bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesenvoid RAFast::killVirtReg(unsigned VirtReg) { 237bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen assert(TargetRegisterInfo::isVirtualRegister(VirtReg) && 238bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen "killVirtReg needs a virtual register"); 239844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen LiveRegMap::iterator LRI = LiveVirtRegs.find(VirtReg); 240844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen if (LRI != LiveVirtRegs.end()) 241844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen killVirtReg(LRI); 24200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 24300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 244bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen/// spillVirtReg - This method spills the value specified by VirtReg into the 24524a1182184336c088f70e86191ebda47df629bebEli Friedman/// corresponding stack slot if needed. 246e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesenvoid RAFast::spillVirtReg(MachineBasicBlock::iterator MI, unsigned VirtReg) { 247bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen assert(TargetRegisterInfo::isVirtualRegister(VirtReg) && 248bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen "Spilling a physical register is illegal!"); 249844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen LiveRegMap::iterator LRI = LiveVirtRegs.find(VirtReg); 250844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen assert(LRI != LiveVirtRegs.end() && "Spilling unmapped virtual register"); 251844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen spillVirtReg(MI, LRI); 2527d4f25904de543b039a28eddbea3034a5d80e7f8Jakob Stoklund Olesen} 2537d4f25904de543b039a28eddbea3034a5d80e7f8Jakob Stoklund Olesen 2547d4f25904de543b039a28eddbea3034a5d80e7f8Jakob Stoklund Olesen/// spillVirtReg - Do the actual work of spilling. 2556fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesenvoid RAFast::spillVirtReg(MachineBasicBlock::iterator MI, 256844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen LiveRegMap::iterator LRI) { 257844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen LiveReg &LR = LRI->second; 258844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen assert(PhysRegState[LR.PhysReg] == LRI->first && "Broken RegState mapping"); 25976b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen 260210e2afcc74e8ce5102d13939b23040fafa71c09Jakob Stoklund Olesen if (LR.Dirty) { 261e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen // If this physreg is used by the instruction, we want to kill it on the 262e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen // instruction, not on the spill. 263844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen bool SpillKill = LR.LastUse != MI; 264210e2afcc74e8ce5102d13939b23040fafa71c09Jakob Stoklund Olesen LR.Dirty = false; 265844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen DEBUG(dbgs() << "Spilling %reg" << LRI->first 2667d4f25904de543b039a28eddbea3034a5d80e7f8Jakob Stoklund Olesen << " in " << TRI->getName(LR.PhysReg)); 267844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen const TargetRegisterClass *RC = MRI->getRegClass(LRI->first); 268844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen int FI = getStackSpaceFor(LRI->first, RC); 2696fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen DEBUG(dbgs() << " to stack slot #" << FI << "\n"); 270844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen TII->storeRegToStackSlot(*MBB, MI, LR.PhysReg, SpillKill, FI, RC, TRI); 27100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen ++NumStores; // Update statistics 27200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 27307cb689d6260b78861d829bb05b188e1558c528eJim Grosbach // If this register is used by DBG_VALUE then insert new DBG_VALUE to 274459a36bd34809ffc5d74de79b3e46f6e02e5184fDevang Patel // identify spilled location as the place to find corresponding variable's 275459a36bd34809ffc5d74de79b3e46f6e02e5184fDevang Patel // value. 276459a36bd34809ffc5d74de79b3e46f6e02e5184fDevang Patel if (MachineInstr *DBG = LiveDbgValueMap.lookup(LRI->first)) { 27707cb689d6260b78861d829bb05b188e1558c528eJim Grosbach const MDNode *MDPtr = 278459a36bd34809ffc5d74de79b3e46f6e02e5184fDevang Patel DBG->getOperand(DBG->getNumOperands()-1).getMetadata(); 279459a36bd34809ffc5d74de79b3e46f6e02e5184fDevang Patel int64_t Offset = 0; 280459a36bd34809ffc5d74de79b3e46f6e02e5184fDevang Patel if (DBG->getOperand(1).isImm()) 281459a36bd34809ffc5d74de79b3e46f6e02e5184fDevang Patel Offset = DBG->getOperand(1).getImm(); 28231defcf2349916ac759be33baaa4060703fd78dfDevang Patel DebugLoc DL; 28331defcf2349916ac759be33baaa4060703fd78dfDevang Patel if (MI == MBB->end()) { 28431defcf2349916ac759be33baaa4060703fd78dfDevang Patel // If MI is at basic block end then use last instruction's location. 28531defcf2349916ac759be33baaa4060703fd78dfDevang Patel MachineBasicBlock::iterator EI = MI; 28631defcf2349916ac759be33baaa4060703fd78dfDevang Patel DL = (--EI)->getDebugLoc(); 28731defcf2349916ac759be33baaa4060703fd78dfDevang Patel } 28831defcf2349916ac759be33baaa4060703fd78dfDevang Patel else 28931defcf2349916ac759be33baaa4060703fd78dfDevang Patel DL = MI->getDebugLoc(); 29007cb689d6260b78861d829bb05b188e1558c528eJim Grosbach if (MachineInstr *NewDV = 291459a36bd34809ffc5d74de79b3e46f6e02e5184fDevang Patel TII->emitFrameIndexDebugValue(*MF, FI, Offset, MDPtr, DL)) { 292459a36bd34809ffc5d74de79b3e46f6e02e5184fDevang Patel MachineBasicBlock *MBB = DBG->getParent(); 293459a36bd34809ffc5d74de79b3e46f6e02e5184fDevang Patel MBB->insert(MI, NewDV); 294459a36bd34809ffc5d74de79b3e46f6e02e5184fDevang Patel DEBUG(dbgs() << "Inserting debug info due to spill:" << "\n" << *NewDV); 295459a36bd34809ffc5d74de79b3e46f6e02e5184fDevang Patel LiveDbgValueMap[LRI->first] = NewDV; 296459a36bd34809ffc5d74de79b3e46f6e02e5184fDevang Patel } 297459a36bd34809ffc5d74de79b3e46f6e02e5184fDevang Patel } 298844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen if (SpillKill) 299210e2afcc74e8ce5102d13939b23040fafa71c09Jakob Stoklund Olesen LR.LastUse = 0; // Don't kill register again 300bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 301844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen killVirtReg(LRI); 30200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 30300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 304bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen/// spillAll - Spill all dirty virtregs without killing them. 3056fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesenvoid RAFast::spillAll(MachineInstr *MI) { 306f3ea06b108d45c53dade87d6f1f48ac0a0e20562Jakob Stoklund Olesen if (LiveVirtRegs.empty()) return; 307e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen isBulkSpilling = true; 3082997985b4cafc2a1e562819a2f3e0c6abe5fb223Jakob Stoklund Olesen // The LiveRegMap is keyed by an unsigned (the virtreg number), so the order 3092997985b4cafc2a1e562819a2f3e0c6abe5fb223Jakob Stoklund Olesen // of spilling here is deterministic, if arbitrary. 3102997985b4cafc2a1e562819a2f3e0c6abe5fb223Jakob Stoklund Olesen for (LiveRegMap::iterator i = LiveVirtRegs.begin(), e = LiveVirtRegs.end(); 3112997985b4cafc2a1e562819a2f3e0c6abe5fb223Jakob Stoklund Olesen i != e; ++i) 312e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen spillVirtReg(MI, i); 313e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen LiveVirtRegs.clear(); 314e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen isBulkSpilling = false; 315bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen} 31600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 3174ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen/// usePhysReg - Handle the direct use of a physical register. 3184ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen/// Check that the register is not used by a virtreg. 3194ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen/// Kill the physreg, marking it free. 3204ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen/// This may add implicit kills to MO->getParent() and invalidate MO. 3214ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesenvoid RAFast::usePhysReg(MachineOperand &MO) { 3224ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen unsigned PhysReg = MO.getReg(); 3234ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen assert(TargetRegisterInfo::isPhysicalRegister(PhysReg) && 3244ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen "Bad usePhysReg operand"); 3254ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen 3264ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen switch (PhysRegState[PhysReg]) { 327bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regDisabled: 328bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 329bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regReserved: 330bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen PhysRegState[PhysReg] = regFree; 3314ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen // Fall through 3324ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen case regFree: 3334ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen UsedInInstr.set(PhysReg); 3344ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen MO.setIsKill(); 335bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen return; 336bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen default: 337f299da8ec3fee88a1b275560a7f94be4cf10d089Eric Christopher // The physreg was allocated to a virtual register. That means the value we 3384ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen // wanted has been clobbered. 3394ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen llvm_unreachable("Instruction uses an allocated register"); 34000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 34100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 3424ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen // Maybe a superregister is reserved? 343bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen for (const unsigned *AS = TRI->getAliasSet(PhysReg); 344bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned Alias = *AS; ++AS) { 3454ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen switch (PhysRegState[Alias]) { 346bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regDisabled: 347bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 348bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regReserved: 3494ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen assert(TRI->isSuperRegister(PhysReg, Alias) && 3504ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen "Instruction is not using a subregister of a reserved register"); 3514ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen // Leave the superregister in the working set. 352bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen PhysRegState[Alias] = regFree; 3534ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen UsedInInstr.set(Alias); 3544ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen MO.getParent()->addRegisterKilled(Alias, TRI, true); 3554ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen return; 3564ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen case regFree: 3574ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen if (TRI->isSuperRegister(PhysReg, Alias)) { 3584ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen // Leave the superregister in the working set. 3594ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen UsedInInstr.set(Alias); 3604ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen MO.getParent()->addRegisterKilled(Alias, TRI, true); 3614ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen return; 3624ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen } 3634ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen // Some other alias was in the working set - clear it. 3644ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen PhysRegState[Alias] = regDisabled; 365bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 366bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen default: 3674ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen llvm_unreachable("Instruction uses an alias of an allocated register"); 368bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 36900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 3704ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen 3714ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen // All aliases are disabled, bring register into working set. 3724ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen PhysRegState[PhysReg] = regFree; 3734ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen UsedInInstr.set(PhysReg); 3744ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen MO.setIsKill(); 37500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 37600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 3774ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen/// definePhysReg - Mark PhysReg as reserved or free after spilling any 3784ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen/// virtregs. This is very similar to defineVirtReg except the physreg is 3794ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen/// reserved instead of allocated. 3806fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesenvoid RAFast::definePhysReg(MachineInstr *MI, unsigned PhysReg, 3816fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen RegState NewState) { 3824ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen UsedInInstr.set(PhysReg); 383bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen switch (unsigned VirtReg = PhysRegState[PhysReg]) { 384bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regDisabled: 385bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 3864ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen default: 387e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen spillVirtReg(MI, VirtReg); 3884ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen // Fall through. 389bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regFree: 390bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regReserved: 3914ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen PhysRegState[PhysReg] = NewState; 392bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen return; 393bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 394bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen 3954ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen // This is a disabled register, disable all aliases. 3964ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen PhysRegState[PhysReg] = NewState; 397bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen for (const unsigned *AS = TRI->getAliasSet(PhysReg); 398bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned Alias = *AS; ++AS) { 3994ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen UsedInInstr.set(Alias); 400bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen switch (unsigned VirtReg = PhysRegState[Alias]) { 401bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regDisabled: 402bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 403bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen default: 404e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen spillVirtReg(MI, VirtReg); 4054ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen // Fall through. 4064ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen case regFree: 4074ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen case regReserved: 4084ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen PhysRegState[Alias] = regDisabled; 4094ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen if (TRI->isSuperRegister(PhysReg, Alias)) 4104ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen return; 411bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 412bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 413bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 414bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen} 41500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 4164ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen 417548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen// calcSpillCost - Return the cost of spilling clearing out PhysReg and 418548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen// aliases so it is free for allocation. 419548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen// Returns 0 when PhysReg is free or disabled with all aliases disabled - it 420548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen// can be allocated directly. 421548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen// Returns spillImpossible when PhysReg or an alias can't be spilled. 422548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesenunsigned RAFast::calcSpillCost(unsigned PhysReg) const { 423b8acb7be804c8c537f2475f3a24303a0b37ab107Jakob Stoklund Olesen if (UsedInInstr.test(PhysReg)) 424b8acb7be804c8c537f2475f3a24303a0b37ab107Jakob Stoklund Olesen return spillImpossible; 425548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen switch (unsigned VirtReg = PhysRegState[PhysReg]) { 426548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen case regDisabled: 427548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen break; 428548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen case regFree: 429548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen return 0; 430548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen case regReserved: 431548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen return spillImpossible; 432548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen default: 433548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen return LiveVirtRegs.lookup(VirtReg).Dirty ? spillDirty : spillClean; 434548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen } 435548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen 436548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen // This is a disabled register, add up const of aliases. 437548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen unsigned Cost = 0; 438548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen for (const unsigned *AS = TRI->getAliasSet(PhysReg); 439548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen unsigned Alias = *AS; ++AS) { 440b8acb7be804c8c537f2475f3a24303a0b37ab107Jakob Stoklund Olesen if (UsedInInstr.test(Alias)) 441b8acb7be804c8c537f2475f3a24303a0b37ab107Jakob Stoklund Olesen return spillImpossible; 442548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen switch (unsigned VirtReg = PhysRegState[Alias]) { 443548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen case regDisabled: 444548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen break; 445548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen case regFree: 446548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen ++Cost; 447548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen break; 448548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen case regReserved: 449548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen return spillImpossible; 450548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen default: 451548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen Cost += LiveVirtRegs.lookup(VirtReg).Dirty ? spillDirty : spillClean; 452548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen break; 453548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen } 454548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen } 455548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen return Cost; 456548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen} 457548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen 458548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen 45900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen/// assignVirtToPhysReg - This method updates local state so that we know 46000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen/// that PhysReg is the proper container for VirtReg now. The physical 46100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen/// register must not be used for anything else when this is called. 46200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen/// 46301dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesenvoid RAFast::assignVirtToPhysReg(LiveRegEntry &LRE, unsigned PhysReg) { 46401dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen DEBUG(dbgs() << "Assigning %reg" << LRE.first << " to " 465bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen << TRI->getName(PhysReg) << "\n"); 46601dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen PhysRegState[PhysReg] = LRE.first; 46701dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen assert(!LRE.second.PhysReg && "Already assigned a physreg"); 46801dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen LRE.second.PhysReg = PhysReg; 46900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 47000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 471bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen/// allocVirtReg - Allocate a physical register for VirtReg. 47201dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesenvoid RAFast::allocVirtReg(MachineInstr *MI, LiveRegEntry &LRE, unsigned Hint) { 47301dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen const unsigned VirtReg = LRE.first; 47401dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen 475bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen assert(TargetRegisterInfo::isVirtualRegister(VirtReg) && 476bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen "Can only allocate virtual registers"); 47700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 4784bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen const TargetRegisterClass *RC = MRI->getRegClass(VirtReg); 479bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen 4804bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen // Ignore invalid hints. 4814bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen if (Hint && (!TargetRegisterInfo::isPhysicalRegister(Hint) || 482b8acb7be804c8c537f2475f3a24303a0b37ab107Jakob Stoklund Olesen !RC->contains(Hint) || !Allocatable.test(Hint))) 4834bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen Hint = 0; 4844bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen 4854bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen // Take hint when possible. 4864bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen if (Hint) { 487548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen switch(calcSpillCost(Hint)) { 4884bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen default: 489548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen definePhysReg(MI, Hint, regFree); 4904bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen // Fall through. 491548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen case 0: 49201dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen return assignVirtToPhysReg(LRE, Hint); 493548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen case spillImpossible: 494548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen break; 4954bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen } 4964bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen } 4974bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen 498548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen TargetRegisterClass::iterator AOB = RC->allocation_order_begin(*MF); 499548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen TargetRegisterClass::iterator AOE = RC->allocation_order_end(*MF); 500548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen 501bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // First try to find a completely free register. 502bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen for (TargetRegisterClass::iterator I = AOB; I != AOE; ++I) { 503bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned PhysReg = *I; 504ee72651df4b783c973bb682bef7eab2ff9a703e2Jim Grosbach if (PhysRegState[PhysReg] == regFree && !UsedInInstr.test(PhysReg) && 505ee72651df4b783c973bb682bef7eab2ff9a703e2Jim Grosbach Allocatable.test(PhysReg)) 506548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen return assignVirtToPhysReg(LRE, PhysReg); 507bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 50800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 509c9c4dacd03a4b80d61ed6b9c6ffeb1b1f76b8d1cJakob Stoklund Olesen DEBUG(dbgs() << "Allocating %reg" << VirtReg << " from " << RC->getName() 510548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen << "\n"); 511548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen 512548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen unsigned BestReg = 0, BestCost = spillImpossible; 513548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen for (TargetRegisterClass::iterator I = AOB; I != AOE; ++I) { 514ee72651df4b783c973bb682bef7eab2ff9a703e2Jim Grosbach if (!Allocatable.test(*I)) 515ee72651df4b783c973bb682bef7eab2ff9a703e2Jim Grosbach continue; 516548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen unsigned Cost = calcSpillCost(*I); 517f3ea06b108d45c53dade87d6f1f48ac0a0e20562Jakob Stoklund Olesen // Cost is 0 when all aliases are already disabled. 518f3ea06b108d45c53dade87d6f1f48ac0a0e20562Jakob Stoklund Olesen if (Cost == 0) 519f3ea06b108d45c53dade87d6f1f48ac0a0e20562Jakob Stoklund Olesen return assignVirtToPhysReg(LRE, *I); 520f3ea06b108d45c53dade87d6f1f48ac0a0e20562Jakob Stoklund Olesen if (Cost < BestCost) 521f3ea06b108d45c53dade87d6f1f48ac0a0e20562Jakob Stoklund Olesen BestReg = *I, BestCost = Cost; 52200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 52300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 524bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (BestReg) { 525f3ea06b108d45c53dade87d6f1f48ac0a0e20562Jakob Stoklund Olesen definePhysReg(MI, BestReg, regFree); 52601dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen return assignVirtToPhysReg(LRE, BestReg); 527bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 52800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 529bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Nothing we can do. 530bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen std::string msg; 531bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen raw_string_ostream Msg(msg); 532bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen Msg << "Ran out of registers during register allocation!"; 533bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (MI->isInlineAsm()) { 534bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen Msg << "\nPlease check your inline asm statement for " 535bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen << "invalid constraints:\n"; 536bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen MI->print(Msg, TM); 537bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 538bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen report_fatal_error(Msg.str()); 53900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 54000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 541bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen/// defineVirtReg - Allocate a register for VirtReg and mark it as dirty. 542646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund OlesenRAFast::LiveRegMap::iterator 543646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund OlesenRAFast::defineVirtReg(MachineInstr *MI, unsigned OpNum, 544646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund Olesen unsigned VirtReg, unsigned Hint) { 545bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen assert(TargetRegisterInfo::isVirtualRegister(VirtReg) && 546bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen "Not a virtual register"); 547844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen LiveRegMap::iterator LRI; 54801dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen bool New; 549844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen tie(LRI, New) = LiveVirtRegs.insert(std::make_pair(VirtReg, LiveReg())); 550844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen LiveReg &LR = LRI->second; 5510c9e4f5f3ff139733d74462a0ad5b94014e764a8Jakob Stoklund Olesen if (New) { 5520c9e4f5f3ff139733d74462a0ad5b94014e764a8Jakob Stoklund Olesen // If there is no hint, peek at the only use of this register. 5530c9e4f5f3ff139733d74462a0ad5b94014e764a8Jakob Stoklund Olesen if ((!Hint || !TargetRegisterInfo::isPhysicalRegister(Hint)) && 5540c9e4f5f3ff139733d74462a0ad5b94014e764a8Jakob Stoklund Olesen MRI->hasOneNonDBGUse(VirtReg)) { 555273f7e42994a5bce0614d04d96dbfdf05fd652e5Jakob Stoklund Olesen const MachineInstr &UseMI = *MRI->use_nodbg_begin(VirtReg); 5560c9e4f5f3ff139733d74462a0ad5b94014e764a8Jakob Stoklund Olesen // It's a copy, use the destination register as a hint. 557273f7e42994a5bce0614d04d96dbfdf05fd652e5Jakob Stoklund Olesen if (UseMI.isCopyLike()) 558273f7e42994a5bce0614d04d96dbfdf05fd652e5Jakob Stoklund Olesen Hint = UseMI.getOperand(0).getReg(); 5590c9e4f5f3ff139733d74462a0ad5b94014e764a8Jakob Stoklund Olesen } 560844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen allocVirtReg(MI, *LRI, Hint); 561d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen } else if (LR.LastUse) { 5620eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen // Redefining a live register - kill at the last use, unless it is this 5630eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen // instruction defining VirtReg multiple times. 5640eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen if (LR.LastUse != MI || LR.LastUse->getOperand(LR.LastOpNum).isUse()) 5650eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen addKillFlag(LR); 5660eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen } 56701dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen assert(LR.PhysReg && "Register not assigned"); 568210e2afcc74e8ce5102d13939b23040fafa71c09Jakob Stoklund Olesen LR.LastUse = MI; 569210e2afcc74e8ce5102d13939b23040fafa71c09Jakob Stoklund Olesen LR.LastOpNum = OpNum; 570210e2afcc74e8ce5102d13939b23040fafa71c09Jakob Stoklund Olesen LR.Dirty = true; 571210e2afcc74e8ce5102d13939b23040fafa71c09Jakob Stoklund Olesen UsedInInstr.set(LR.PhysReg); 572646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund Olesen return LRI; 573bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen} 57400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 575bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen/// reloadVirtReg - Make sure VirtReg is available in a physreg and return it. 576646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund OlesenRAFast::LiveRegMap::iterator 577646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund OlesenRAFast::reloadVirtReg(MachineInstr *MI, unsigned OpNum, 578646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund Olesen unsigned VirtReg, unsigned Hint) { 579bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen assert(TargetRegisterInfo::isVirtualRegister(VirtReg) && 580bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen "Not a virtual register"); 581844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen LiveRegMap::iterator LRI; 58201dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen bool New; 583844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen tie(LRI, New) = LiveVirtRegs.insert(std::make_pair(VirtReg, LiveReg())); 584844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen LiveReg &LR = LRI->second; 585ac3e529831877cea609ed668f95b1dc06e34698cJakob Stoklund Olesen MachineOperand &MO = MI->getOperand(OpNum); 58601dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen if (New) { 587844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen allocVirtReg(MI, *LRI, Hint); 5884bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen const TargetRegisterClass *RC = MRI->getRegClass(VirtReg); 589bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen int FrameIndex = getStackSpaceFor(VirtReg, RC); 590c9c4dacd03a4b80d61ed6b9c6ffeb1b1f76b8d1cJakob Stoklund Olesen DEBUG(dbgs() << "Reloading %reg" << VirtReg << " into " 59101dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen << TRI->getName(LR.PhysReg) << "\n"); 59201dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen TII->loadRegFromStackSlot(*MBB, MI, LR.PhysReg, FrameIndex, RC, TRI); 593bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen ++NumLoads; 59401dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen } else if (LR.Dirty) { 5951e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen if (isLastUseOfLocalReg(MO)) { 5961e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen DEBUG(dbgs() << "Killing last use: " << MO << "\n"); 597d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen if (MO.isUse()) 598d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen MO.setIsKill(); 599d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen else 600d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen MO.setIsDead(); 6011e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen } else if (MO.isKill()) { 6021e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen DEBUG(dbgs() << "Clearing dubious kill: " << MO << "\n"); 6031e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen MO.setIsKill(false); 604d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen } else if (MO.isDead()) { 605d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen DEBUG(dbgs() << "Clearing dubious dead: " << MO << "\n"); 606d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen MO.setIsDead(false); 6071e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen } 608ac3e529831877cea609ed668f95b1dc06e34698cJakob Stoklund Olesen } else if (MO.isKill()) { 609ac3e529831877cea609ed668f95b1dc06e34698cJakob Stoklund Olesen // We must remove kill flags from uses of reloaded registers because the 610ac3e529831877cea609ed668f95b1dc06e34698cJakob Stoklund Olesen // register would be killed immediately, and there might be a second use: 611ac3e529831877cea609ed668f95b1dc06e34698cJakob Stoklund Olesen // %foo = OR %x<kill>, %x 612ac3e529831877cea609ed668f95b1dc06e34698cJakob Stoklund Olesen // This would cause a second reload of %x into a different register. 613ac3e529831877cea609ed668f95b1dc06e34698cJakob Stoklund Olesen DEBUG(dbgs() << "Clearing clean kill: " << MO << "\n"); 614ac3e529831877cea609ed668f95b1dc06e34698cJakob Stoklund Olesen MO.setIsKill(false); 615d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen } else if (MO.isDead()) { 616d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen DEBUG(dbgs() << "Clearing clean dead: " << MO << "\n"); 617d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen MO.setIsDead(false); 61800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 61901dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen assert(LR.PhysReg && "Register not assigned"); 620210e2afcc74e8ce5102d13939b23040fafa71c09Jakob Stoklund Olesen LR.LastUse = MI; 621210e2afcc74e8ce5102d13939b23040fafa71c09Jakob Stoklund Olesen LR.LastOpNum = OpNum; 622210e2afcc74e8ce5102d13939b23040fafa71c09Jakob Stoklund Olesen UsedInInstr.set(LR.PhysReg); 623646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund Olesen return LRI; 624bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen} 62500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 6260eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen// setPhysReg - Change operand OpNum in MI the refer the PhysReg, considering 6270eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen// subregs. This may invalidate any operand pointers. 6280eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen// Return true if the operand kills its register. 6290eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesenbool RAFast::setPhysReg(MachineInstr *MI, unsigned OpNum, unsigned PhysReg) { 6300eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen MachineOperand &MO = MI->getOperand(OpNum); 63141e1401de5cb8752fb9d06e65e62bfe97cc1304eJakob Stoklund Olesen if (!MO.getSubReg()) { 632bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen MO.setReg(PhysReg); 63341e1401de5cb8752fb9d06e65e62bfe97cc1304eJakob Stoklund Olesen return MO.isKill() || MO.isDead(); 63441e1401de5cb8752fb9d06e65e62bfe97cc1304eJakob Stoklund Olesen } 63541e1401de5cb8752fb9d06e65e62bfe97cc1304eJakob Stoklund Olesen 63641e1401de5cb8752fb9d06e65e62bfe97cc1304eJakob Stoklund Olesen // Handle subregister index. 63741e1401de5cb8752fb9d06e65e62bfe97cc1304eJakob Stoklund Olesen MO.setReg(PhysReg ? TRI->getSubReg(PhysReg, MO.getSubReg()) : 0); 63841e1401de5cb8752fb9d06e65e62bfe97cc1304eJakob Stoklund Olesen MO.setSubReg(0); 639d32e735ae6e3fbebcae9a23d7cda091770bb3a14Jakob Stoklund Olesen 640d32e735ae6e3fbebcae9a23d7cda091770bb3a14Jakob Stoklund Olesen // A kill flag implies killing the full register. Add corresponding super 641d32e735ae6e3fbebcae9a23d7cda091770bb3a14Jakob Stoklund Olesen // register kill. 642d32e735ae6e3fbebcae9a23d7cda091770bb3a14Jakob Stoklund Olesen if (MO.isKill()) { 643d32e735ae6e3fbebcae9a23d7cda091770bb3a14Jakob Stoklund Olesen MI->addRegisterKilled(PhysReg, TRI, true); 64441e1401de5cb8752fb9d06e65e62bfe97cc1304eJakob Stoklund Olesen return true; 64541e1401de5cb8752fb9d06e65e62bfe97cc1304eJakob Stoklund Olesen } 646d32e735ae6e3fbebcae9a23d7cda091770bb3a14Jakob Stoklund Olesen return MO.isDead(); 64700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 64800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 649d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen// Handle special instruction operand like early clobbers and tied ops when 650d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen// there are additional physreg defines. 651d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesenvoid RAFast::handleThroughOperands(MachineInstr *MI, 652d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen SmallVectorImpl<unsigned> &VirtDead) { 653d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen DEBUG(dbgs() << "Scanning for through registers:"); 654d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen SmallSet<unsigned, 8> ThroughRegs; 655d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 656d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen MachineOperand &MO = MI->getOperand(i); 657d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen if (!MO.isReg()) continue; 658d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen unsigned Reg = MO.getReg(); 659d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen if (!Reg || TargetRegisterInfo::isPhysicalRegister(Reg)) continue; 660d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen if (MO.isEarlyClobber() || MI->isRegTiedToDefOperand(i) || 661d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen (MO.getSubReg() && MI->readsVirtualRegister(Reg))) { 662d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen if (ThroughRegs.insert(Reg)) 663d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen DEBUG(dbgs() << " %reg" << Reg); 664d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen } 665d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen } 666d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen 667d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen // If any physreg defines collide with preallocated through registers, 668d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen // we must spill and reallocate. 669d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen DEBUG(dbgs() << "\nChecking for physdef collisions.\n"); 670d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 671d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen MachineOperand &MO = MI->getOperand(i); 672d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen if (!MO.isReg() || !MO.isDef()) continue; 673d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen unsigned Reg = MO.getReg(); 674d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen if (!Reg || !TargetRegisterInfo::isPhysicalRegister(Reg)) continue; 675d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen UsedInInstr.set(Reg); 676d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen if (ThroughRegs.count(PhysRegState[Reg])) 677d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen definePhysReg(MI, Reg, regFree); 678d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS) { 679d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen UsedInInstr.set(*AS); 680d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen if (ThroughRegs.count(PhysRegState[*AS])) 681d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen definePhysReg(MI, *AS, regFree); 682d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen } 683d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen } 684d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen 685d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen SmallVector<unsigned, 8> PartialDefs; 686d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen DEBUG(dbgs() << "Allocating tied uses and early clobbers.\n"); 687d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 688d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen MachineOperand &MO = MI->getOperand(i); 689d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen if (!MO.isReg()) continue; 690d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen unsigned Reg = MO.getReg(); 691d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen if (!Reg || TargetRegisterInfo::isPhysicalRegister(Reg)) continue; 692d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen if (MO.isUse()) { 693d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen unsigned DefIdx = 0; 694d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen if (!MI->isRegTiedToDefOperand(i, &DefIdx)) continue; 695d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen DEBUG(dbgs() << "Operand " << i << "("<< MO << ") is tied to operand " 696d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen << DefIdx << ".\n"); 697d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen LiveRegMap::iterator LRI = reloadVirtReg(MI, i, Reg, 0); 698d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen unsigned PhysReg = LRI->second.PhysReg; 699d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen setPhysReg(MI, i, PhysReg); 700d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen // Note: we don't update the def operand yet. That would cause the normal 701d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen // def-scan to attempt spilling. 702d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen } else if (MO.getSubReg() && MI->readsVirtualRegister(Reg)) { 703d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen DEBUG(dbgs() << "Partial redefine: " << MO << "\n"); 704d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen // Reload the register, but don't assign to the operand just yet. 705d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen // That would confuse the later phys-def processing pass. 706d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen LiveRegMap::iterator LRI = reloadVirtReg(MI, i, Reg, 0); 707d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen PartialDefs.push_back(LRI->second.PhysReg); 708d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen } else if (MO.isEarlyClobber()) { 709d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen // Note: defineVirtReg may invalidate MO. 710d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen LiveRegMap::iterator LRI = defineVirtReg(MI, i, Reg, 0); 711d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen unsigned PhysReg = LRI->second.PhysReg; 712d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen if (setPhysReg(MI, i, PhysReg)) 713d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen VirtDead.push_back(Reg); 714d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen } 715d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen } 716d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen 717d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen // Restore UsedInInstr to a state usable for allocating normal virtual uses. 718ee72651df4b783c973bb682bef7eab2ff9a703e2Jim Grosbach UsedInInstr.reset(); 719d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 720d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen MachineOperand &MO = MI->getOperand(i); 721d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen if (!MO.isReg() || (MO.isDef() && !MO.isEarlyClobber())) continue; 722d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen unsigned Reg = MO.getReg(); 723d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen if (!Reg || !TargetRegisterInfo::isPhysicalRegister(Reg)) continue; 724d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen UsedInInstr.set(Reg); 725d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS) 726d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen UsedInInstr.set(*AS); 727d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen } 728d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen 729d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen // Also mark PartialDefs as used to avoid reallocation. 730d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen for (unsigned i = 0, e = PartialDefs.size(); i != e; ++i) 731d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen UsedInInstr.set(PartialDefs[i]); 732d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen} 733d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen 7346fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesenvoid RAFast::AllocateBasicBlock() { 7356fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen DEBUG(dbgs() << "\nAllocating " << *MBB); 73600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 737bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen PhysRegState.assign(TRI->getNumRegs(), regDisabled); 73876b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen assert(LiveVirtRegs.empty() && "Mapping not cleared form last block?"); 73900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 7406fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen MachineBasicBlock::iterator MII = MBB->begin(); 741bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen 742bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Add live-in registers as live. 7436fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen for (MachineBasicBlock::livein_iterator I = MBB->livein_begin(), 7446fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen E = MBB->livein_end(); I != E; ++I) 7459d4b51b696e27b9c061955d4c76f9dbff529b143Jakob Stoklund Olesen if (Allocatable.test(*I)) 7469d4b51b696e27b9c061955d4c76f9dbff529b143Jakob Stoklund Olesen definePhysReg(MII, *I, regReserved); 747bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen 748d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen SmallVector<unsigned, 8> VirtDead; 7497ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen SmallVector<MachineInstr*, 32> Coalesced; 75000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 75100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen // Otherwise, sequentially allocate each instruction in the MBB. 7526fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen while (MII != MBB->end()) { 75300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen MachineInstr *MI = MII++; 75400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen const TargetInstrDesc &TID = MI->getDesc(); 75500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen DEBUG({ 756c9c4dacd03a4b80d61ed6b9c6ffeb1b1f76b8d1cJakob Stoklund Olesen dbgs() << "\n>> " << *MI << "Regs:"; 757bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen for (unsigned Reg = 1, E = TRI->getNumRegs(); Reg != E; ++Reg) { 758bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (PhysRegState[Reg] == regDisabled) continue; 759bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen dbgs() << " " << TRI->getName(Reg); 760bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen switch(PhysRegState[Reg]) { 761bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regFree: 762bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 763bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regReserved: 764c9c4dacd03a4b80d61ed6b9c6ffeb1b1f76b8d1cJakob Stoklund Olesen dbgs() << "*"; 765bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 766bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen default: 767bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen dbgs() << "=%reg" << PhysRegState[Reg]; 768210e2afcc74e8ce5102d13939b23040fafa71c09Jakob Stoklund Olesen if (LiveVirtRegs[PhysRegState[Reg]].Dirty) 769bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen dbgs() << "*"; 77076b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen assert(LiveVirtRegs[PhysRegState[Reg]].PhysReg == Reg && 771bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen "Bad inverse map"); 772bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 773bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 774bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 77500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen dbgs() << '\n'; 77676b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen // Check that LiveVirtRegs is the inverse. 77776b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen for (LiveRegMap::iterator i = LiveVirtRegs.begin(), 77876b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen e = LiveVirtRegs.end(); i != e; ++i) { 779bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen assert(TargetRegisterInfo::isVirtualRegister(i->first) && 780bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen "Bad map key"); 78176b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen assert(TargetRegisterInfo::isPhysicalRegister(i->second.PhysReg) && 782bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen "Bad map value"); 78376b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen assert(PhysRegState[i->second.PhysReg] == i->first && 78476b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen "Bad inverse map"); 785bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 78600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen }); 78700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 788bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Debug values are not allowed to change codegen in any way. 789bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (MI->isDebugValue()) { 79058b8176ed39038240984c0966fef847fe37c86c1Devang Patel bool ScanDbgValue = true; 79158b8176ed39038240984c0966fef847fe37c86c1Devang Patel while (ScanDbgValue) { 79258b8176ed39038240984c0966fef847fe37c86c1Devang Patel ScanDbgValue = false; 79358b8176ed39038240984c0966fef847fe37c86c1Devang Patel for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 79458b8176ed39038240984c0966fef847fe37c86c1Devang Patel MachineOperand &MO = MI->getOperand(i); 79558b8176ed39038240984c0966fef847fe37c86c1Devang Patel if (!MO.isReg()) continue; 79658b8176ed39038240984c0966fef847fe37c86c1Devang Patel unsigned Reg = MO.getReg(); 79758b8176ed39038240984c0966fef847fe37c86c1Devang Patel if (!Reg || TargetRegisterInfo::isPhysicalRegister(Reg)) continue; 798459a36bd34809ffc5d74de79b3e46f6e02e5184fDevang Patel LiveDbgValueMap[Reg] = MI; 79958b8176ed39038240984c0966fef847fe37c86c1Devang Patel LiveRegMap::iterator LRI = LiveVirtRegs.find(Reg); 80058b8176ed39038240984c0966fef847fe37c86c1Devang Patel if (LRI != LiveVirtRegs.end()) 80158b8176ed39038240984c0966fef847fe37c86c1Devang Patel setPhysReg(MI, i, LRI->second.PhysReg); 8027a029b6d7e58cb0f1010f14d99d7661e387cfb54Devang Patel else { 80358b8176ed39038240984c0966fef847fe37c86c1Devang Patel int SS = StackSlotForVirtReg[Reg]; 8044bafda9618f9dfa9edc8da08bb3001ef2d1a9b68Devang Patel if (SS == -1) { 80507cb689d6260b78861d829bb05b188e1558c528eJim Grosbach // We can't allocate a physreg for a DebugValue, sorry! 8064bafda9618f9dfa9edc8da08bb3001ef2d1a9b68Devang Patel DEBUG(dbgs() << "Unable to allocate vreg used by DBG_VALUE"); 80707cb689d6260b78861d829bb05b188e1558c528eJim Grosbach MO.setReg(0); 8084bafda9618f9dfa9edc8da08bb3001ef2d1a9b68Devang Patel } 80958b8176ed39038240984c0966fef847fe37c86c1Devang Patel else { 81058b8176ed39038240984c0966fef847fe37c86c1Devang Patel // Modify DBG_VALUE now that the value is in a spill slot. 811459a36bd34809ffc5d74de79b3e46f6e02e5184fDevang Patel int64_t Offset = MI->getOperand(1).getImm(); 81207cb689d6260b78861d829bb05b188e1558c528eJim Grosbach const MDNode *MDPtr = 81358b8176ed39038240984c0966fef847fe37c86c1Devang Patel MI->getOperand(MI->getNumOperands()-1).getMetadata(); 81458b8176ed39038240984c0966fef847fe37c86c1Devang Patel DebugLoc DL = MI->getDebugLoc(); 81507cb689d6260b78861d829bb05b188e1558c528eJim Grosbach if (MachineInstr *NewDV = 81658b8176ed39038240984c0966fef847fe37c86c1Devang Patel TII->emitFrameIndexDebugValue(*MF, SS, Offset, MDPtr, DL)) { 81707cb689d6260b78861d829bb05b188e1558c528eJim Grosbach DEBUG(dbgs() << "Modifying debug info due to spill:" << 81807cb689d6260b78861d829bb05b188e1558c528eJim Grosbach "\t" << *MI); 81958b8176ed39038240984c0966fef847fe37c86c1Devang Patel MachineBasicBlock *MBB = MI->getParent(); 82058b8176ed39038240984c0966fef847fe37c86c1Devang Patel MBB->insert(MBB->erase(MI), NewDV); 82158b8176ed39038240984c0966fef847fe37c86c1Devang Patel // Scan NewDV operands from the beginning. 82258b8176ed39038240984c0966fef847fe37c86c1Devang Patel MI = NewDV; 82358b8176ed39038240984c0966fef847fe37c86c1Devang Patel ScanDbgValue = true; 82458b8176ed39038240984c0966fef847fe37c86c1Devang Patel break; 8254bafda9618f9dfa9edc8da08bb3001ef2d1a9b68Devang Patel } else { 82607cb689d6260b78861d829bb05b188e1558c528eJim Grosbach // We can't allocate a physreg for a DebugValue; sorry! 8274bafda9618f9dfa9edc8da08bb3001ef2d1a9b68Devang Patel DEBUG(dbgs() << "Unable to allocate vreg used by DBG_VALUE"); 82807cb689d6260b78861d829bb05b188e1558c528eJim Grosbach MO.setReg(0); 8294bafda9618f9dfa9edc8da08bb3001ef2d1a9b68Devang Patel } 83058b8176ed39038240984c0966fef847fe37c86c1Devang Patel } 8317a029b6d7e58cb0f1010f14d99d7661e387cfb54Devang Patel } 8327a029b6d7e58cb0f1010f14d99d7661e387cfb54Devang Patel } 83300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 834bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Next instruction. 835bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen continue; 83600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 83700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 8384bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen // If this is a copy, we may be able to coalesce. 83904c528a0c86ddf3d6a70681f72e1b2ec07b0b53aJakob Stoklund Olesen unsigned CopySrc = 0, CopyDst = 0, CopySrcSub = 0, CopyDstSub = 0; 840273f7e42994a5bce0614d04d96dbfdf05fd652e5Jakob Stoklund Olesen if (MI->isCopy()) { 841273f7e42994a5bce0614d04d96dbfdf05fd652e5Jakob Stoklund Olesen CopyDst = MI->getOperand(0).getReg(); 842273f7e42994a5bce0614d04d96dbfdf05fd652e5Jakob Stoklund Olesen CopySrc = MI->getOperand(1).getReg(); 843273f7e42994a5bce0614d04d96dbfdf05fd652e5Jakob Stoklund Olesen CopyDstSub = MI->getOperand(0).getSubReg(); 844273f7e42994a5bce0614d04d96dbfdf05fd652e5Jakob Stoklund Olesen CopySrcSub = MI->getOperand(1).getSubReg(); 84504c528a0c86ddf3d6a70681f72e1b2ec07b0b53aJakob Stoklund Olesen } 8464bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen 847bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Track registers used by instruction. 848ee72651df4b783c973bb682bef7eab2ff9a703e2Jim Grosbach UsedInInstr.reset(); 84900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 850bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // First scan. 851bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Mark physreg uses and early clobbers as used. 852e97dda4fc58ee401ebb4aa9153d10f8ce8ba9a70Jakob Stoklund Olesen // Find the end of the virtreg operands 853e97dda4fc58ee401ebb4aa9153d10f8ce8ba9a70Jakob Stoklund Olesen unsigned VirtOpEnd = 0; 854d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen bool hasTiedOps = false; 855d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen bool hasEarlyClobbers = false; 856d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen bool hasPartialRedefs = false; 857d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen bool hasPhysDefs = false; 858bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 85900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen MachineOperand &MO = MI->getOperand(i); 860bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (!MO.isReg()) continue; 861bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned Reg = MO.getReg(); 862e97dda4fc58ee401ebb4aa9153d10f8ce8ba9a70Jakob Stoklund Olesen if (!Reg) continue; 863e97dda4fc58ee401ebb4aa9153d10f8ce8ba9a70Jakob Stoklund Olesen if (TargetRegisterInfo::isVirtualRegister(Reg)) { 864e97dda4fc58ee401ebb4aa9153d10f8ce8ba9a70Jakob Stoklund Olesen VirtOpEnd = i+1; 865d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen if (MO.isUse()) { 866d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen hasTiedOps = hasTiedOps || 867d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen TID.getOperandConstraint(i, TOI::TIED_TO) != -1; 868d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen } else { 869d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen if (MO.isEarlyClobber()) 870d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen hasEarlyClobbers = true; 871d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen if (MO.getSubReg() && MI->readsVirtualRegister(Reg)) 872d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen hasPartialRedefs = true; 873d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen } 874e97dda4fc58ee401ebb4aa9153d10f8ce8ba9a70Jakob Stoklund Olesen continue; 875e97dda4fc58ee401ebb4aa9153d10f8ce8ba9a70Jakob Stoklund Olesen } 876efa155fd6e3820495205a09f8b9f20390d126153Jakob Stoklund Olesen if (!Allocatable.test(Reg)) continue; 877bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (MO.isUse()) { 8784ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen usePhysReg(MO); 879bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } else if (MO.isEarlyClobber()) { 88075ac4d9c2dfb22f84da25dec03df7a07f3dad1faJakob Stoklund Olesen definePhysReg(MI, Reg, (MO.isImplicit() || MO.isDead()) ? 88175ac4d9c2dfb22f84da25dec03df7a07f3dad1faJakob Stoklund Olesen regFree : regReserved); 882d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen hasEarlyClobbers = true; 883d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen } else 884d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen hasPhysDefs = true; 885d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen } 886d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen 887d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen // The instruction may have virtual register operands that must be allocated 888d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen // the same register at use-time and def-time: early clobbers and tied 889d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen // operands. If there are also physical defs, these registers must avoid 890d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen // both physical defs and uses, making them more constrained than normal 891d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen // operands. 89207cb689d6260b78861d829bb05b188e1558c528eJim Grosbach // Similarly, if there are multiple defs and tied operands, we must make 89307cb689d6260b78861d829bb05b188e1558c528eJim Grosbach // sure the same register is allocated to uses and defs. 894d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen // We didn't detect inline asm tied operands above, so just make this extra 895d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen // pass for all inline asm. 896d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen if (MI->isInlineAsm() || hasEarlyClobbers || hasPartialRedefs || 8974bd94f7bbe2ed6e0d83d03b06c0d20bb346abecaJakob Stoklund Olesen (hasTiedOps && (hasPhysDefs || TID.getNumDefs() > 1))) { 898d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen handleThroughOperands(MI, VirtDead); 899d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen // Don't attempt coalescing when we have funny stuff going on. 900d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen CopyDst = 0; 9014bd94f7bbe2ed6e0d83d03b06c0d20bb346abecaJakob Stoklund Olesen // Pretend we have early clobbers so the use operands get marked below. 9024bd94f7bbe2ed6e0d83d03b06c0d20bb346abecaJakob Stoklund Olesen // This is not necessary for the common case of a single tied use. 9034bd94f7bbe2ed6e0d83d03b06c0d20bb346abecaJakob Stoklund Olesen hasEarlyClobbers = true; 90400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 90500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 906bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Second scan. 907d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen // Allocate virtreg uses. 908e97dda4fc58ee401ebb4aa9153d10f8ce8ba9a70Jakob Stoklund Olesen for (unsigned i = 0; i != VirtOpEnd; ++i) { 90900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen MachineOperand &MO = MI->getOperand(i); 910bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (!MO.isReg()) continue; 91100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen unsigned Reg = MO.getReg(); 912bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (!Reg || TargetRegisterInfo::isPhysicalRegister(Reg)) continue; 913bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (MO.isUse()) { 914646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund Olesen LiveRegMap::iterator LRI = reloadVirtReg(MI, i, Reg, CopyDst); 915646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund Olesen unsigned PhysReg = LRI->second.PhysReg; 9167ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen CopySrc = (CopySrc == Reg || CopySrc == PhysReg) ? PhysReg : 0; 9170eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen if (setPhysReg(MI, i, PhysReg)) 918646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund Olesen killVirtReg(LRI); 91900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 92000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 92100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 9224bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen MRI->addPhysRegsUsed(UsedInInstr); 92382b07dc4995d48065bd95affff4d8513a5cad4f2Jakob Stoklund Olesen 9244bd94f7bbe2ed6e0d83d03b06c0d20bb346abecaJakob Stoklund Olesen // Track registers defined by instruction - early clobbers and tied uses at 9254bd94f7bbe2ed6e0d83d03b06c0d20bb346abecaJakob Stoklund Olesen // this point. 926ee72651df4b783c973bb682bef7eab2ff9a703e2Jim Grosbach UsedInInstr.reset(); 927d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen if (hasEarlyClobbers) { 928d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 929d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen MachineOperand &MO = MI->getOperand(i); 9304bd94f7bbe2ed6e0d83d03b06c0d20bb346abecaJakob Stoklund Olesen if (!MO.isReg()) continue; 931d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen unsigned Reg = MO.getReg(); 932d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen if (!Reg || !TargetRegisterInfo::isPhysicalRegister(Reg)) continue; 9334bd94f7bbe2ed6e0d83d03b06c0d20bb346abecaJakob Stoklund Olesen // Look for physreg defs and tied uses. 9344bd94f7bbe2ed6e0d83d03b06c0d20bb346abecaJakob Stoklund Olesen if (!MO.isDef() && !MI->isRegTiedToDefOperand(i)) continue; 935d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen UsedInInstr.set(Reg); 936d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS) 937d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen UsedInInstr.set(*AS); 938d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen } 93900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 94000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 9414b6bbe885d851b1cfba2be9b5efc6365a2b7828aJakob Stoklund Olesen unsigned DefOpEnd = MI->getNumOperands(); 9424b6bbe885d851b1cfba2be9b5efc6365a2b7828aJakob Stoklund Olesen if (TID.isCall()) { 9434b6bbe885d851b1cfba2be9b5efc6365a2b7828aJakob Stoklund Olesen // Spill all virtregs before a call. This serves two purposes: 1. If an 94407cb689d6260b78861d829bb05b188e1558c528eJim Grosbach // exception is thrown, the landing pad is going to expect to find 94507cb689d6260b78861d829bb05b188e1558c528eJim Grosbach // registers in their spill slots, and 2. we don't have to wade through 94607cb689d6260b78861d829bb05b188e1558c528eJim Grosbach // all the <imp-def> operands on the call instruction. 9474b6bbe885d851b1cfba2be9b5efc6365a2b7828aJakob Stoklund Olesen DefOpEnd = VirtOpEnd; 9484b6bbe885d851b1cfba2be9b5efc6365a2b7828aJakob Stoklund Olesen DEBUG(dbgs() << " Spilling remaining registers before call.\n"); 9494b6bbe885d851b1cfba2be9b5efc6365a2b7828aJakob Stoklund Olesen spillAll(MI); 9506de07178e1e6445080bf4f7704e274c5f219ff70Jakob Stoklund Olesen 9516de07178e1e6445080bf4f7704e274c5f219ff70Jakob Stoklund Olesen // The imp-defs are skipped below, but we still need to mark those 9526de07178e1e6445080bf4f7704e274c5f219ff70Jakob Stoklund Olesen // registers as used by the function. 9536de07178e1e6445080bf4f7704e274c5f219ff70Jakob Stoklund Olesen SkippedInstrs.insert(&TID); 9544b6bbe885d851b1cfba2be9b5efc6365a2b7828aJakob Stoklund Olesen } 9554b6bbe885d851b1cfba2be9b5efc6365a2b7828aJakob Stoklund Olesen 956bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Third scan. 957bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Allocate defs and collect dead defs. 9584b6bbe885d851b1cfba2be9b5efc6365a2b7828aJakob Stoklund Olesen for (unsigned i = 0; i != DefOpEnd; ++i) { 95900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen MachineOperand &MO = MI->getOperand(i); 96075ac4d9c2dfb22f84da25dec03df7a07f3dad1faJakob Stoklund Olesen if (!MO.isReg() || !MO.isDef() || !MO.getReg() || MO.isEarlyClobber()) 96175ac4d9c2dfb22f84da25dec03df7a07f3dad1faJakob Stoklund Olesen continue; 962bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned Reg = MO.getReg(); 96300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 964bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (TargetRegisterInfo::isPhysicalRegister(Reg)) { 965efa155fd6e3820495205a09f8b9f20390d126153Jakob Stoklund Olesen if (!Allocatable.test(Reg)) continue; 9666fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen definePhysReg(MI, Reg, (MO.isImplicit() || MO.isDead()) ? 9676fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen regFree : regReserved); 968bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen continue; 96900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 970646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund Olesen LiveRegMap::iterator LRI = defineVirtReg(MI, i, Reg, CopySrc); 971646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund Olesen unsigned PhysReg = LRI->second.PhysReg; 9720eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen if (setPhysReg(MI, i, PhysReg)) { 9730eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen VirtDead.push_back(Reg); 9747ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen CopyDst = 0; // cancel coalescing; 9757ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen } else 9767ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen CopyDst = (CopyDst == Reg || CopyDst == PhysReg) ? PhysReg : 0; 97700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 97800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 9790eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen // Kill dead defs after the scan to ensure that multiple defs of the same 9800eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen // register are allocated identically. We didn't need to do this for uses 9810eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen // because we are crerating our own kill flags, and they are always at the 9820eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen // last use. 9830eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen for (unsigned i = 0, e = VirtDead.size(); i != e; ++i) 9840eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen killVirtReg(VirtDead[i]); 9850eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen VirtDead.clear(); 9860eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen 9874bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen MRI->addPhysRegsUsed(UsedInInstr); 988c9c4dacd03a4b80d61ed6b9c6ffeb1b1f76b8d1cJakob Stoklund Olesen 9897ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen if (CopyDst && CopyDst == CopySrc && CopyDstSub == CopySrcSub) { 9907ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen DEBUG(dbgs() << "-- coalescing: " << *MI); 9917ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen Coalesced.push_back(MI); 9927ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen } else { 9937ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen DEBUG(dbgs() << "<< " << *MI); 9947ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen } 99500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 99600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 997bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Spill all physical registers holding virtual registers now. 998e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen DEBUG(dbgs() << "Spilling live registers at end of block.\n"); 999e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen spillAll(MBB->getFirstTerminator()); 100000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 10017ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen // Erase all the coalesced copies. We are delaying it until now because 1002e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen // LiveVirtRegs might refer to the instrs. 10037ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen for (unsigned i = 0, e = Coalesced.size(); i != e; ++i) 10046fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen MBB->erase(Coalesced[i]); 10058a65c510a4fa1245d101da6318618d025702028cJakob Stoklund Olesen NumCopies += Coalesced.size(); 10067ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen 10076fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen DEBUG(MBB->dump()); 100800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 100900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 101000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen/// runOnMachineFunction - Register allocate the whole function 101100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen/// 101200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesenbool RAFast::runOnMachineFunction(MachineFunction &Fn) { 1013c9c4dacd03a4b80d61ed6b9c6ffeb1b1f76b8d1cJakob Stoklund Olesen DEBUG(dbgs() << "********** FAST REGISTER ALLOCATION **********\n" 1014c9c4dacd03a4b80d61ed6b9c6ffeb1b1f76b8d1cJakob Stoklund Olesen << "********** Function: " 1015c9c4dacd03a4b80d61ed6b9c6ffeb1b1f76b8d1cJakob Stoklund Olesen << ((Value*)Fn.getFunction())->getName() << '\n'); 101600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen MF = &Fn; 10174bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen MRI = &MF->getRegInfo(); 101800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen TM = &Fn.getTarget(); 101900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen TRI = TM->getRegisterInfo(); 102000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen TII = TM->getInstrInfo(); 102100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 102200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen UsedInInstr.resize(TRI->getNumRegs()); 1023efa155fd6e3820495205a09f8b9f20390d126153Jakob Stoklund Olesen Allocatable = TRI->getAllocatableSet(*MF); 102400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 102500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen // initialize the virtual->physical register map to have a 'null' 102600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen // mapping for all virtual registers 10274bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen unsigned LastVirtReg = MRI->getLastVirtReg(); 102800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen StackSlotForVirtReg.grow(LastVirtReg); 102900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 103000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen // Loop over all of the basic blocks, eliminating virtual register references 10316fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen for (MachineFunction::iterator MBBi = Fn.begin(), MBBe = Fn.end(); 10326fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen MBBi != MBBe; ++MBBi) { 10336fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen MBB = &*MBBi; 10346fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen AllocateBasicBlock(); 10356fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen } 103600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 103782b07dc4995d48065bd95affff4d8513a5cad4f2Jakob Stoklund Olesen // Make sure the set of used physregs is closed under subreg operations. 10384bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen MRI->closePhysRegsUsed(*TRI); 103982b07dc4995d48065bd95affff4d8513a5cad4f2Jakob Stoklund Olesen 10406de07178e1e6445080bf4f7704e274c5f219ff70Jakob Stoklund Olesen // Add the clobber lists for all the instructions we skipped earlier. 10416de07178e1e6445080bf4f7704e274c5f219ff70Jakob Stoklund Olesen for (SmallPtrSet<const TargetInstrDesc*, 4>::const_iterator 10426de07178e1e6445080bf4f7704e274c5f219ff70Jakob Stoklund Olesen I = SkippedInstrs.begin(), E = SkippedInstrs.end(); I != E; ++I) 10436de07178e1e6445080bf4f7704e274c5f219ff70Jakob Stoklund Olesen if (const unsigned *Defs = (*I)->getImplicitDefs()) 10446de07178e1e6445080bf4f7704e274c5f219ff70Jakob Stoklund Olesen while (*Defs) 10456de07178e1e6445080bf4f7704e274c5f219ff70Jakob Stoklund Olesen MRI->setPhysRegUsed(*Defs++); 10466de07178e1e6445080bf4f7704e274c5f219ff70Jakob Stoklund Olesen 10476de07178e1e6445080bf4f7704e274c5f219ff70Jakob Stoklund Olesen SkippedInstrs.clear(); 104800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen StackSlotForVirtReg.clear(); 1049459a36bd34809ffc5d74de79b3e46f6e02e5184fDevang Patel LiveDbgValueMap.clear(); 105000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen return true; 105100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 105200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 105300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund OlesenFunctionPass *llvm::createFastRegisterAllocator() { 105400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen return new RAFast(); 105500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 1056