RegAllocFast.cpp revision 8c70ea47fae6d61441d150cbe9431cf5e06222e5
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" 165d20c3152bd7fe91eda1b58a5eb6da7067874c61Jakob Stoklund Olesen#include "RegisterClassInfo.h" 1700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include "llvm/BasicBlock.h" 1800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include "llvm/CodeGen/MachineFunctionPass.h" 1900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include "llvm/CodeGen/MachineInstr.h" 20459a36bd34809ffc5d74de79b3e46f6e02e5184fDevang Patel#include "llvm/CodeGen/MachineInstrBuilder.h" 2100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include "llvm/CodeGen/MachineFrameInfo.h" 2200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include "llvm/CodeGen/MachineRegisterInfo.h" 2300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include "llvm/CodeGen/Passes.h" 2400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include "llvm/CodeGen/RegAllocRegistry.h" 2500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include "llvm/Target/TargetInstrInfo.h" 2600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include "llvm/Target/TargetMachine.h" 2700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include "llvm/Support/CommandLine.h" 2800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include "llvm/Support/Debug.h" 2900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include "llvm/Support/ErrorHandling.h" 3000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include "llvm/Support/raw_ostream.h" 3100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include "llvm/ADT/DenseMap.h" 3200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include "llvm/ADT/IndexedMap.h" 3300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include "llvm/ADT/SmallSet.h" 3400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include "llvm/ADT/SmallVector.h" 35a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen#include "llvm/ADT/SparseSet.h" 3600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include "llvm/ADT/Statistic.h" 3700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include "llvm/ADT/STLExtras.h" 3800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include <algorithm> 3900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesenusing namespace llvm; 4000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 4100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund OlesenSTATISTIC(NumStores, "Number of stores added"); 4200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund OlesenSTATISTIC(NumLoads , "Number of loads added"); 438a65c510a4fa1245d101da6318618d025702028cJakob Stoklund OlesenSTATISTIC(NumCopies, "Number of copies coalesced"); 4400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 4500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesenstatic RegisterRegAlloc 4600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen fastRegAlloc("fast", "fast register allocator", createFastRegisterAllocator); 4700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 4800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesennamespace { 4900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen class RAFast : public MachineFunctionPass { 5000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen public: 5100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen static char ID; 5290c579de5a383cee278acc3f7e7b9d0a656e6a35Owen Anderson RAFast() : MachineFunctionPass(ID), StackSlotForVirtReg(-1), 538dd26253f54247e77e5accfdd70e7b4bf27b39c2Andrew Trick isBulkSpilling(false) {} 5400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen private: 5500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen const TargetMachine *TM; 5600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen MachineFunction *MF; 574bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen MachineRegisterInfo *MRI; 5800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen const TargetRegisterInfo *TRI; 5900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen const TargetInstrInfo *TII; 605d20c3152bd7fe91eda1b58a5eb6da7067874c61Jakob Stoklund Olesen RegisterClassInfo RegClassInfo; 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. 72a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen unsigned VirtReg; // Virtual register number. 73210e2afcc74e8ce5102d13939b23040fafa71c09Jakob Stoklund Olesen unsigned PhysReg; // Currently held here. 74210e2afcc74e8ce5102d13939b23040fafa71c09Jakob Stoklund Olesen unsigned short LastOpNum; // OpNum on LastUse. 75210e2afcc74e8ce5102d13939b23040fafa71c09Jakob Stoklund Olesen bool Dirty; // Register needs spill. 7676b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen 77a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen explicit LiveReg(unsigned v) 78a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen : LastUse(0), VirtReg(v), PhysReg(0), LastOpNum(0), Dirty(false) {} 79a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen 80c0ccb8bb17028fe0dda139c0972c0125d10e6053Andrew Trick unsigned getSparseSetIndex() const { 81a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen return TargetRegisterInfo::virtReg2Index(VirtReg); 82a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen } 8376b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen }; 8476b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen 85a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen typedef SparseSet<LiveReg> LiveRegMap; 8676b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen 8776b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen // LiveVirtRegs - This map contains entries for each virtual register 8800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen // that is currently available in a physical register. 8976b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen LiveRegMap LiveVirtRegs; 9000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 9172d9b0e4fce90a635af5c80cb6992ac639279d59Devang Patel DenseMap<unsigned, SmallVector<MachineInstr *, 4> > LiveDbgValueMap; 92459a36bd34809ffc5d74de79b3e46f6e02e5184fDevang Patel 93bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // RegState - Track the state of a physical register. 94bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen enum RegState { 95bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // A disabled register is not available for allocation, but an alias may 96bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // be in use. A register can only be moved out of the disabled state if 97bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // all aliases are disabled. 98bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen regDisabled, 99bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen 100bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // A free register is not currently in use and can be allocated 101bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // immediately without checking aliases. 102bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen regFree, 103bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen 104d8a16241229a6d3f761e2e9fd19cbe08e614f113Evan Cheng // A reserved register has been assigned explicitly (e.g., setting up a 105bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // call parameter), and it remains reserved until it is used. 106bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen regReserved 10700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 108bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // A register state may also be a virtual register number, indication that 109bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // the physical register is currently allocated to a virtual register. In 11076b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen // that case, LiveVirtRegs contains the inverse mapping. 111bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen }; 112bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen 113bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // PhysRegState - One of the RegState enums, or a virtreg. 114bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen std::vector<unsigned> PhysRegState; 11500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 11600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen // UsedInInstr - BitVector of physregs that are used in the current 11700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen // instruction, and so cannot be allocated. 11800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen BitVector UsedInInstr; 11900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 12007cb689d6260b78861d829bb05b188e1558c528eJim Grosbach // SkippedInstrs - Descriptors of instructions whose clobber list was 12107cb689d6260b78861d829bb05b188e1558c528eJim Grosbach // ignored because all registers were spilled. It is still necessary to 12207cb689d6260b78861d829bb05b188e1558c528eJim Grosbach // mark all the clobbered registers as used by the function. 123e837dead3c8dc3445ef6a0e2322179c57e264a13Evan Cheng SmallPtrSet<const MCInstrDesc*, 4> SkippedInstrs; 1246de07178e1e6445080bf4f7704e274c5f219ff70Jakob Stoklund Olesen 125e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen // isBulkSpilling - This flag is set when LiveRegMap will be cleared 126e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen // completely after spilling all live registers. LiveRegMap entries should 127e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen // not be erased. 128e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen bool isBulkSpilling; 1297d4f25904de543b039a28eddbea3034a5d80e7f8Jakob Stoklund Olesen 130548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen enum { 131548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen spillClean = 1, 132548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen spillDirty = 100, 133548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen spillImpossible = ~0u 134548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen }; 13500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen public: 13600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen virtual const char *getPassName() const { 13700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen return "Fast Register Allocator"; 13800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 13900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 14000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen virtual void getAnalysisUsage(AnalysisUsage &AU) const { 14100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen AU.setPreservesCFG(); 14200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen MachineFunctionPass::getAnalysisUsage(AU); 14300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 14400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 14500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen private: 14600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen bool runOnMachineFunction(MachineFunction &Fn); 1476fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen void AllocateBasicBlock(); 148d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen void handleThroughOperands(MachineInstr *MI, 149d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen SmallVectorImpl<unsigned> &VirtDead); 15000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen int getStackSpaceFor(unsigned VirtReg, const TargetRegisterClass *RC); 1511e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen bool isLastUseOfLocalReg(MachineOperand&); 1521e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen 15301dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen void addKillFlag(const LiveReg&); 154844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen void killVirtReg(LiveRegMap::iterator); 155804291e31658d46fb1db5ecaf42b31950c02a6f2Jakob Stoklund Olesen void killVirtReg(unsigned VirtReg); 156844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen void spillVirtReg(MachineBasicBlock::iterator MI, LiveRegMap::iterator); 157e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen void spillVirtReg(MachineBasicBlock::iterator MI, unsigned VirtReg); 1584ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen 1594ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen void usePhysReg(MachineOperand&); 1606fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen void definePhysReg(MachineInstr *MI, unsigned PhysReg, RegState NewState); 161548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen unsigned calcSpillCost(unsigned PhysReg) const; 162a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen void assignVirtToPhysReg(LiveReg&, unsigned PhysReg); 163a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen LiveRegMap::iterator findLiveVirtReg(unsigned VirtReg) { 164a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen return LiveVirtRegs.find(TargetRegisterInfo::virtReg2Index(VirtReg)); 165a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen } 166a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen LiveRegMap::const_iterator findLiveVirtReg(unsigned VirtReg) const { 167a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen return LiveVirtRegs.find(TargetRegisterInfo::virtReg2Index(VirtReg)); 168a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen } 169a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen LiveRegMap::iterator assignVirtToPhysReg(unsigned VReg, unsigned PhysReg); 170a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen LiveRegMap::iterator allocVirtReg(MachineInstr *MI, LiveRegMap::iterator, 171a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen unsigned Hint); 172646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund Olesen LiveRegMap::iterator defineVirtReg(MachineInstr *MI, unsigned OpNum, 173646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund Olesen unsigned VirtReg, unsigned Hint); 174646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund Olesen LiveRegMap::iterator reloadVirtReg(MachineInstr *MI, unsigned OpNum, 175646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund Olesen unsigned VirtReg, unsigned Hint); 1766fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen void spillAll(MachineInstr *MI); 1770eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen bool setPhysReg(MachineInstr *MI, unsigned OpNum, unsigned PhysReg); 178b3d58474c83499621ae1e2d76dc87587910abe55Andrew Trick void addRetOperands(MachineBasicBlock *MBB); 17900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen }; 18000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen char RAFast::ID = 0; 18100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 18200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 18300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen/// getStackSpaceFor - This allocates space for the specified virtual register 18400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen/// to be held on the stack. 18500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesenint RAFast::getStackSpaceFor(unsigned VirtReg, const TargetRegisterClass *RC) { 18600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen // Find the location Reg would belong... 18700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen int SS = StackSlotForVirtReg[VirtReg]; 18800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen if (SS != -1) 18900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen return SS; // Already has space allocated? 19000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 19100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen // Allocate a new stack object for this spill location... 19200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen int FrameIdx = MF->getFrameInfo()->CreateSpillStackObject(RC->getSize(), 19300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen RC->getAlignment()); 19400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 19500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen // Assign the slot. 19600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen StackSlotForVirtReg[VirtReg] = FrameIdx; 19700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen return FrameIdx; 19800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 19900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 2001e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen/// isLastUseOfLocalReg - Return true if MO is the only remaining reference to 2011e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen/// its virtual register, and it is guaranteed to be a block-local register. 2021e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen/// 2031e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesenbool RAFast::isLastUseOfLocalReg(MachineOperand &MO) { 2041e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen // Check for non-debug uses or defs following MO. 2051e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen // This is the most likely way to fail - fast path it. 206844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen MachineOperand *Next = &MO; 207844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen while ((Next = Next->getNextOperandForReg())) 208844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen if (!Next->isDebug()) 2091e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen return false; 2101e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen 2111e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen // If the register has ever been spilled or reloaded, we conservatively assume 2121e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen // it is a global register used in multiple blocks. 2131e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen if (StackSlotForVirtReg[MO.getReg()] != -1) 2141e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen return false; 2151e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen 2161e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen // Check that the use/def chain has exactly one operand - MO. 2171e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen return &MRI->reg_nodbg_begin(MO.getReg()).getOperand() == &MO; 2181e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen} 2191e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen 220804291e31658d46fb1db5ecaf42b31950c02a6f2Jakob Stoklund Olesen/// addKillFlag - Set kill flags on last use of a virtual register. 22101dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesenvoid RAFast::addKillFlag(const LiveReg &LR) { 22201dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen if (!LR.LastUse) return; 22301dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen MachineOperand &MO = LR.LastUse->getOperand(LR.LastOpNum); 224d32e735ae6e3fbebcae9a23d7cda091770bb3a14Jakob Stoklund Olesen if (MO.isUse() && !LR.LastUse->isRegTiedToDefOperand(LR.LastOpNum)) { 225d32e735ae6e3fbebcae9a23d7cda091770bb3a14Jakob Stoklund Olesen if (MO.getReg() == LR.PhysReg) 2260eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen MO.setIsKill(); 2270eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen else 2280eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen LR.LastUse->addRegisterKilled(LR.PhysReg, TRI, true); 2290eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen } 230804291e31658d46fb1db5ecaf42b31950c02a6f2Jakob Stoklund Olesen} 231804291e31658d46fb1db5ecaf42b31950c02a6f2Jakob Stoklund Olesen 232804291e31658d46fb1db5ecaf42b31950c02a6f2Jakob Stoklund Olesen/// killVirtReg - Mark virtreg as no longer available. 233844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesenvoid RAFast::killVirtReg(LiveRegMap::iterator LRI) { 234a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen addKillFlag(*LRI); 23591ba63d230bfc3e035d2851d039e08f34f0b9bbdJakob Stoklund Olesen assert(PhysRegState[LRI->PhysReg] == LRI->VirtReg && 23691ba63d230bfc3e035d2851d039e08f34f0b9bbdJakob Stoklund Olesen "Broken RegState mapping"); 237a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen PhysRegState[LRI->PhysReg] = regFree; 238e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen // Erase from LiveVirtRegs unless we're spilling in bulk. 239e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen if (!isBulkSpilling) 240844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen LiveVirtRegs.erase(LRI); 24176b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen} 24276b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen 24376b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen/// killVirtReg - Mark virtreg as no longer available. 244bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesenvoid RAFast::killVirtReg(unsigned VirtReg) { 245bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen assert(TargetRegisterInfo::isVirtualRegister(VirtReg) && 246bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen "killVirtReg needs a virtual register"); 247a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen LiveRegMap::iterator LRI = findLiveVirtReg(VirtReg); 248844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen if (LRI != LiveVirtRegs.end()) 249844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen killVirtReg(LRI); 25000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 25100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 252bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen/// spillVirtReg - This method spills the value specified by VirtReg into the 25324a1182184336c088f70e86191ebda47df629bebEli Friedman/// corresponding stack slot if needed. 254e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesenvoid RAFast::spillVirtReg(MachineBasicBlock::iterator MI, unsigned VirtReg) { 255bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen assert(TargetRegisterInfo::isVirtualRegister(VirtReg) && 256bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen "Spilling a physical register is illegal!"); 257a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen LiveRegMap::iterator LRI = findLiveVirtReg(VirtReg); 258844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen assert(LRI != LiveVirtRegs.end() && "Spilling unmapped virtual register"); 259844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen spillVirtReg(MI, LRI); 2607d4f25904de543b039a28eddbea3034a5d80e7f8Jakob Stoklund Olesen} 2617d4f25904de543b039a28eddbea3034a5d80e7f8Jakob Stoklund Olesen 2627d4f25904de543b039a28eddbea3034a5d80e7f8Jakob Stoklund Olesen/// spillVirtReg - Do the actual work of spilling. 2636fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesenvoid RAFast::spillVirtReg(MachineBasicBlock::iterator MI, 264844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen LiveRegMap::iterator LRI) { 265a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen LiveReg &LR = *LRI; 266a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen assert(PhysRegState[LR.PhysReg] == LRI->VirtReg && "Broken RegState mapping"); 26776b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen 268210e2afcc74e8ce5102d13939b23040fafa71c09Jakob Stoklund Olesen if (LR.Dirty) { 269e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen // If this physreg is used by the instruction, we want to kill it on the 270e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen // instruction, not on the spill. 271844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen bool SpillKill = LR.LastUse != MI; 272210e2afcc74e8ce5102d13939b23040fafa71c09Jakob Stoklund Olesen LR.Dirty = false; 273a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen DEBUG(dbgs() << "Spilling " << PrintReg(LRI->VirtReg, TRI) 2744314268128be6d54c9a7f0709680e5a5b40f3ab3Jakob Stoklund Olesen << " in " << PrintReg(LR.PhysReg, TRI)); 275a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen const TargetRegisterClass *RC = MRI->getRegClass(LRI->VirtReg); 276a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen int FI = getStackSpaceFor(LRI->VirtReg, RC); 2776fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen DEBUG(dbgs() << " to stack slot #" << FI << "\n"); 278844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen TII->storeRegToStackSlot(*MBB, MI, LR.PhysReg, SpillKill, FI, RC, TRI); 27900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen ++NumStores; // Update statistics 28000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 28107cb689d6260b78861d829bb05b188e1558c528eJim Grosbach // If this register is used by DBG_VALUE then insert new DBG_VALUE to 282459a36bd34809ffc5d74de79b3e46f6e02e5184fDevang Patel // identify spilled location as the place to find corresponding variable's 283459a36bd34809ffc5d74de79b3e46f6e02e5184fDevang Patel // value. 284a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen SmallVector<MachineInstr *, 4> &LRIDbgValues = 285a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen LiveDbgValueMap[LRI->VirtReg]; 28672d9b0e4fce90a635af5c80cb6992ac639279d59Devang Patel for (unsigned li = 0, le = LRIDbgValues.size(); li != le; ++li) { 28772d9b0e4fce90a635af5c80cb6992ac639279d59Devang Patel MachineInstr *DBG = LRIDbgValues[li]; 28807cb689d6260b78861d829bb05b188e1558c528eJim Grosbach const MDNode *MDPtr = 289459a36bd34809ffc5d74de79b3e46f6e02e5184fDevang Patel DBG->getOperand(DBG->getNumOperands()-1).getMetadata(); 290459a36bd34809ffc5d74de79b3e46f6e02e5184fDevang Patel int64_t Offset = 0; 291459a36bd34809ffc5d74de79b3e46f6e02e5184fDevang Patel if (DBG->getOperand(1).isImm()) 292459a36bd34809ffc5d74de79b3e46f6e02e5184fDevang Patel Offset = DBG->getOperand(1).getImm(); 29331defcf2349916ac759be33baaa4060703fd78dfDevang Patel DebugLoc DL; 29431defcf2349916ac759be33baaa4060703fd78dfDevang Patel if (MI == MBB->end()) { 29531defcf2349916ac759be33baaa4060703fd78dfDevang Patel // If MI is at basic block end then use last instruction's location. 29631defcf2349916ac759be33baaa4060703fd78dfDevang Patel MachineBasicBlock::iterator EI = MI; 29731defcf2349916ac759be33baaa4060703fd78dfDevang Patel DL = (--EI)->getDebugLoc(); 29831defcf2349916ac759be33baaa4060703fd78dfDevang Patel } 29931defcf2349916ac759be33baaa4060703fd78dfDevang Patel else 30031defcf2349916ac759be33baaa4060703fd78dfDevang Patel DL = MI->getDebugLoc(); 30107cb689d6260b78861d829bb05b188e1558c528eJim Grosbach if (MachineInstr *NewDV = 302459a36bd34809ffc5d74de79b3e46f6e02e5184fDevang Patel TII->emitFrameIndexDebugValue(*MF, FI, Offset, MDPtr, DL)) { 303459a36bd34809ffc5d74de79b3e46f6e02e5184fDevang Patel MachineBasicBlock *MBB = DBG->getParent(); 304459a36bd34809ffc5d74de79b3e46f6e02e5184fDevang Patel MBB->insert(MI, NewDV); 305459a36bd34809ffc5d74de79b3e46f6e02e5184fDevang Patel DEBUG(dbgs() << "Inserting debug info due to spill:" << "\n" << *NewDV); 306459a36bd34809ffc5d74de79b3e46f6e02e5184fDevang Patel } 307459a36bd34809ffc5d74de79b3e46f6e02e5184fDevang Patel } 30891ba63d230bfc3e035d2851d039e08f34f0b9bbdJakob Stoklund Olesen // Now this register is spilled there is should not be any DBG_VALUE 30991ba63d230bfc3e035d2851d039e08f34f0b9bbdJakob Stoklund Olesen // pointing to this register because they are all pointing to spilled value 31091ba63d230bfc3e035d2851d039e08f34f0b9bbdJakob Stoklund Olesen // now. 3116f373a87cba3b0c88bc76bf1d03ee5f81143764fDevang Patel LRIDbgValues.clear(); 312844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen if (SpillKill) 313210e2afcc74e8ce5102d13939b23040fafa71c09Jakob Stoklund Olesen LR.LastUse = 0; // Don't kill register again 314bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 315844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen killVirtReg(LRI); 31600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 31700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 318bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen/// spillAll - Spill all dirty virtregs without killing them. 3196fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesenvoid RAFast::spillAll(MachineInstr *MI) { 320f3ea06b108d45c53dade87d6f1f48ac0a0e20562Jakob Stoklund Olesen if (LiveVirtRegs.empty()) return; 321e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen isBulkSpilling = true; 3222997985b4cafc2a1e562819a2f3e0c6abe5fb223Jakob Stoklund Olesen // The LiveRegMap is keyed by an unsigned (the virtreg number), so the order 3232997985b4cafc2a1e562819a2f3e0c6abe5fb223Jakob Stoklund Olesen // of spilling here is deterministic, if arbitrary. 3242997985b4cafc2a1e562819a2f3e0c6abe5fb223Jakob Stoklund Olesen for (LiveRegMap::iterator i = LiveVirtRegs.begin(), e = LiveVirtRegs.end(); 3252997985b4cafc2a1e562819a2f3e0c6abe5fb223Jakob Stoklund Olesen i != e; ++i) 326e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen spillVirtReg(MI, i); 327e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen LiveVirtRegs.clear(); 328e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen isBulkSpilling = false; 329bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen} 33000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 3314ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen/// usePhysReg - Handle the direct use of a physical register. 3324ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen/// Check that the register is not used by a virtreg. 3334ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen/// Kill the physreg, marking it free. 3344ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen/// This may add implicit kills to MO->getParent() and invalidate MO. 3354ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesenvoid RAFast::usePhysReg(MachineOperand &MO) { 3364ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen unsigned PhysReg = MO.getReg(); 3374ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen assert(TargetRegisterInfo::isPhysicalRegister(PhysReg) && 3384ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen "Bad usePhysReg operand"); 3394ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen 3404ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen switch (PhysRegState[PhysReg]) { 341bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regDisabled: 342bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 343bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regReserved: 344bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen PhysRegState[PhysReg] = regFree; 3454ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen // Fall through 3464ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen case regFree: 3474ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen UsedInInstr.set(PhysReg); 3484ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen MO.setIsKill(); 349bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen return; 350bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen default: 351f299da8ec3fee88a1b275560a7f94be4cf10d089Eric Christopher // The physreg was allocated to a virtual register. That means the value we 3524ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen // wanted has been clobbered. 3534ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen llvm_unreachable("Instruction uses an allocated register"); 35400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 35500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 3564ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen // Maybe a superregister is reserved? 357e4fd907e72a599eddfa7a81eac4366b5b82523e3Craig Topper for (const uint16_t *AS = TRI->getAliasSet(PhysReg); 358bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned Alias = *AS; ++AS) { 3594ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen switch (PhysRegState[Alias]) { 360bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regDisabled: 361bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 362bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regReserved: 3634ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen assert(TRI->isSuperRegister(PhysReg, Alias) && 3644ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen "Instruction is not using a subregister of a reserved register"); 3654ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen // Leave the superregister in the working set. 366bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen PhysRegState[Alias] = regFree; 3674ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen UsedInInstr.set(Alias); 3684ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen MO.getParent()->addRegisterKilled(Alias, TRI, true); 3694ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen return; 3704ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen case regFree: 3714ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen if (TRI->isSuperRegister(PhysReg, Alias)) { 3724ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen // Leave the superregister in the working set. 3734ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen UsedInInstr.set(Alias); 3744ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen MO.getParent()->addRegisterKilled(Alias, TRI, true); 3754ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen return; 3764ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen } 3774ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen // Some other alias was in the working set - clear it. 3784ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen PhysRegState[Alias] = regDisabled; 379bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 380bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen default: 3814ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen llvm_unreachable("Instruction uses an alias of an allocated register"); 382bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 38300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 3844ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen 3854ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen // All aliases are disabled, bring register into working set. 3864ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen PhysRegState[PhysReg] = regFree; 3874ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen UsedInInstr.set(PhysReg); 3884ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen MO.setIsKill(); 38900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 39000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 3914ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen/// definePhysReg - Mark PhysReg as reserved or free after spilling any 3924ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen/// virtregs. This is very similar to defineVirtReg except the physreg is 3934ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen/// reserved instead of allocated. 3946fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesenvoid RAFast::definePhysReg(MachineInstr *MI, unsigned PhysReg, 3956fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen RegState NewState) { 3964ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen UsedInInstr.set(PhysReg); 397bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen switch (unsigned VirtReg = PhysRegState[PhysReg]) { 398bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regDisabled: 399bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 4004ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen default: 401e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen spillVirtReg(MI, VirtReg); 4024ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen // Fall through. 403bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regFree: 404bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regReserved: 4054ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen PhysRegState[PhysReg] = NewState; 406bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen return; 407bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 408bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen 4094ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen // This is a disabled register, disable all aliases. 4104ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen PhysRegState[PhysReg] = NewState; 411e4fd907e72a599eddfa7a81eac4366b5b82523e3Craig Topper for (const uint16_t *AS = TRI->getAliasSet(PhysReg); 412bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned Alias = *AS; ++AS) { 413bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen switch (unsigned VirtReg = PhysRegState[Alias]) { 414bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regDisabled: 415bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 416bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen default: 417e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen spillVirtReg(MI, VirtReg); 4184ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen // Fall through. 4194ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen case regFree: 4204ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen case regReserved: 4214ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen PhysRegState[Alias] = regDisabled; 4224ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen if (TRI->isSuperRegister(PhysReg, Alias)) 4234ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen return; 424bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 425bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 426bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 427bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen} 42800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 4294ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen 430548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen// calcSpillCost - Return the cost of spilling clearing out PhysReg and 431548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen// aliases so it is free for allocation. 432548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen// Returns 0 when PhysReg is free or disabled with all aliases disabled - it 433548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen// can be allocated directly. 434548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen// Returns spillImpossible when PhysReg or an alias can't be spilled. 435548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesenunsigned RAFast::calcSpillCost(unsigned PhysReg) const { 4360b756349a718e046abba84c316877a682eb0ff2fEric Christopher if (UsedInInstr.test(PhysReg)) { 43727ce3b96e51887995f94d8c78a6c7e79bf7cdcddJakob Stoklund Olesen DEBUG(dbgs() << PrintReg(PhysReg, TRI) << " is already used in instr.\n"); 438b8acb7be804c8c537f2475f3a24303a0b37ab107Jakob Stoklund Olesen return spillImpossible; 4390b756349a718e046abba84c316877a682eb0ff2fEric Christopher } 440548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen switch (unsigned VirtReg = PhysRegState[PhysReg]) { 441548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen case regDisabled: 442548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen break; 443548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen case regFree: 444548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen return 0; 445548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen case regReserved: 44627ce3b96e51887995f94d8c78a6c7e79bf7cdcddJakob Stoklund Olesen DEBUG(dbgs() << PrintReg(VirtReg, TRI) << " corresponding " 44727ce3b96e51887995f94d8c78a6c7e79bf7cdcddJakob Stoklund Olesen << PrintReg(PhysReg, TRI) << " is reserved already.\n"); 448548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen return spillImpossible; 449a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen default: { 450a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen LiveRegMap::const_iterator I = findLiveVirtReg(VirtReg); 451a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen assert(I != LiveVirtRegs.end() && "Missing VirtReg entry"); 452a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen return I->Dirty ? spillDirty : spillClean; 453a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen } 454548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen } 455548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen 456bbfc3b30986ff89487350cade99ea7c90e2c8165Eric Christopher // This is a disabled register, add up cost of aliases. 45727ce3b96e51887995f94d8c78a6c7e79bf7cdcddJakob Stoklund Olesen DEBUG(dbgs() << PrintReg(PhysReg, TRI) << " is disabled.\n"); 458548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen unsigned Cost = 0; 459e4fd907e72a599eddfa7a81eac4366b5b82523e3Craig Topper for (const uint16_t *AS = TRI->getAliasSet(PhysReg); 460548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen unsigned Alias = *AS; ++AS) { 461d31df87f41891c9ea459282c666c6e1cab9bd4c7Eric Christopher if (UsedInInstr.test(Alias)) 462d31df87f41891c9ea459282c666c6e1cab9bd4c7Eric Christopher return spillImpossible; 463548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen switch (unsigned VirtReg = PhysRegState[Alias]) { 464548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen case regDisabled: 465548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen break; 466548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen case regFree: 467548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen ++Cost; 468548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen break; 469548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen case regReserved: 470548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen return spillImpossible; 471a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen default: { 472a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen LiveRegMap::const_iterator I = findLiveVirtReg(VirtReg); 473a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen assert(I != LiveVirtRegs.end() && "Missing VirtReg entry"); 474a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen Cost += I->Dirty ? spillDirty : spillClean; 475548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen break; 476548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen } 477a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen } 478548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen } 479548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen return Cost; 480548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen} 481548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen 482548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen 48300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen/// assignVirtToPhysReg - This method updates local state so that we know 48400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen/// that PhysReg is the proper container for VirtReg now. The physical 48500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen/// register must not be used for anything else when this is called. 48600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen/// 487a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesenvoid RAFast::assignVirtToPhysReg(LiveReg &LR, unsigned PhysReg) { 488a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen DEBUG(dbgs() << "Assigning " << PrintReg(LR.VirtReg, TRI) << " to " 4894314268128be6d54c9a7f0709680e5a5b40f3ab3Jakob Stoklund Olesen << PrintReg(PhysReg, TRI) << "\n"); 490a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen PhysRegState[PhysReg] = LR.VirtReg; 491a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen assert(!LR.PhysReg && "Already assigned a physreg"); 492a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen LR.PhysReg = PhysReg; 493a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen} 494a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen 495a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund OlesenRAFast::LiveRegMap::iterator 496a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund OlesenRAFast::assignVirtToPhysReg(unsigned VirtReg, unsigned PhysReg) { 497a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen LiveRegMap::iterator LRI = findLiveVirtReg(VirtReg); 498a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen assert(LRI != LiveVirtRegs.end() && "VirtReg disappeared"); 499a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen assignVirtToPhysReg(*LRI, PhysReg); 500a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen return LRI; 50100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 50200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 503bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen/// allocVirtReg - Allocate a physical register for VirtReg. 504a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund OlesenRAFast::LiveRegMap::iterator RAFast::allocVirtReg(MachineInstr *MI, 505a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen LiveRegMap::iterator LRI, 506a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen unsigned Hint) { 507a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen const unsigned VirtReg = LRI->VirtReg; 50801dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen 509bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen assert(TargetRegisterInfo::isVirtualRegister(VirtReg) && 510bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen "Can only allocate virtual registers"); 51100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 5124bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen const TargetRegisterClass *RC = MRI->getRegClass(VirtReg); 513bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen 5144bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen // Ignore invalid hints. 5154bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen if (Hint && (!TargetRegisterInfo::isPhysicalRegister(Hint) || 516448ab3ab395ffc9e7fc04d2d6afb41fcac74070dJakob Stoklund Olesen !RC->contains(Hint) || !RegClassInfo.isAllocatable(Hint))) 5174bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen Hint = 0; 5184bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen 5194bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen // Take hint when possible. 5204bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen if (Hint) { 5215e5ed4457749995b46d46e9769e657fcc0818e2cJakob Stoklund Olesen // Ignore the hint if we would have to spill a dirty register. 5225e5ed4457749995b46d46e9769e657fcc0818e2cJakob Stoklund Olesen unsigned Cost = calcSpillCost(Hint); 5235e5ed4457749995b46d46e9769e657fcc0818e2cJakob Stoklund Olesen if (Cost < spillDirty) { 5245e5ed4457749995b46d46e9769e657fcc0818e2cJakob Stoklund Olesen if (Cost) 5255e5ed4457749995b46d46e9769e657fcc0818e2cJakob Stoklund Olesen definePhysReg(MI, Hint, regFree); 526a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen // definePhysReg may kill virtual registers and modify LiveVirtRegs. 527a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen // That invalidates LRI, so run a new lookup for VirtReg. 528a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen return assignVirtToPhysReg(VirtReg, Hint); 5294bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen } 5304bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen } 5314bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen 5325d20c3152bd7fe91eda1b58a5eb6da7067874c61Jakob Stoklund Olesen ArrayRef<unsigned> AO = RegClassInfo.getOrder(RC); 533548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen 534bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // First try to find a completely free register. 5355d20c3152bd7fe91eda1b58a5eb6da7067874c61Jakob Stoklund Olesen for (ArrayRef<unsigned>::iterator I = AO.begin(), E = AO.end(); I != E; ++I) { 536bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned PhysReg = *I; 537a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen if (PhysRegState[PhysReg] == regFree && !UsedInInstr.test(PhysReg)) { 538a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen assignVirtToPhysReg(*LRI, PhysReg); 539a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen return LRI; 540a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen } 541bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 54200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 5434314268128be6d54c9a7f0709680e5a5b40f3ab3Jakob Stoklund Olesen DEBUG(dbgs() << "Allocating " << PrintReg(VirtReg) << " from " 5444314268128be6d54c9a7f0709680e5a5b40f3ab3Jakob Stoklund Olesen << RC->getName() << "\n"); 545548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen 546548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen unsigned BestReg = 0, BestCost = spillImpossible; 5475d20c3152bd7fe91eda1b58a5eb6da7067874c61Jakob Stoklund Olesen for (ArrayRef<unsigned>::iterator I = AO.begin(), E = AO.end(); I != E; ++I) { 548548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen unsigned Cost = calcSpillCost(*I); 54927ce3b96e51887995f94d8c78a6c7e79bf7cdcddJakob Stoklund Olesen DEBUG(dbgs() << "\tRegister: " << PrintReg(*I, TRI) << "\n"); 5500b756349a718e046abba84c316877a682eb0ff2fEric Christopher DEBUG(dbgs() << "\tCost: " << Cost << "\n"); 5510b756349a718e046abba84c316877a682eb0ff2fEric Christopher DEBUG(dbgs() << "\tBestCost: " << BestCost << "\n"); 552f3ea06b108d45c53dade87d6f1f48ac0a0e20562Jakob Stoklund Olesen // Cost is 0 when all aliases are already disabled. 553a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen if (Cost == 0) { 554a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen assignVirtToPhysReg(*LRI, *I); 555a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen return LRI; 556a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen } 557f3ea06b108d45c53dade87d6f1f48ac0a0e20562Jakob Stoklund Olesen if (Cost < BestCost) 558f3ea06b108d45c53dade87d6f1f48ac0a0e20562Jakob Stoklund Olesen BestReg = *I, BestCost = Cost; 55900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 56000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 561bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (BestReg) { 562f3ea06b108d45c53dade87d6f1f48ac0a0e20562Jakob Stoklund Olesen definePhysReg(MI, BestReg, regFree); 563a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen // definePhysReg may kill virtual registers and modify LiveVirtRegs. 564a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen // That invalidates LRI, so run a new lookup for VirtReg. 565a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen return assignVirtToPhysReg(VirtReg, BestReg); 566bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 56700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 5689d812a2805161665d56a78734da98b58f39ce0fcJakob Stoklund Olesen // Nothing we can do. Report an error and keep going with a bad allocation. 5699d812a2805161665d56a78734da98b58f39ce0fcJakob Stoklund Olesen MI->emitError("ran out of registers during register allocation"); 5709d812a2805161665d56a78734da98b58f39ce0fcJakob Stoklund Olesen definePhysReg(MI, *AO.begin(), regFree); 571a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen return assignVirtToPhysReg(VirtReg, *AO.begin()); 57200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 57300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 574bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen/// defineVirtReg - Allocate a register for VirtReg and mark it as dirty. 575646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund OlesenRAFast::LiveRegMap::iterator 576646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund OlesenRAFast::defineVirtReg(MachineInstr *MI, unsigned OpNum, 577646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund Olesen unsigned VirtReg, unsigned Hint) { 578bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen assert(TargetRegisterInfo::isVirtualRegister(VirtReg) && 579bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen "Not a virtual register"); 580844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen LiveRegMap::iterator LRI; 58101dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen bool New; 582a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen tie(LRI, New) = LiveVirtRegs.insert(LiveReg(VirtReg)); 5830c9e4f5f3ff139733d74462a0ad5b94014e764a8Jakob Stoklund Olesen if (New) { 5840c9e4f5f3ff139733d74462a0ad5b94014e764a8Jakob Stoklund Olesen // If there is no hint, peek at the only use of this register. 5850c9e4f5f3ff139733d74462a0ad5b94014e764a8Jakob Stoklund Olesen if ((!Hint || !TargetRegisterInfo::isPhysicalRegister(Hint)) && 5860c9e4f5f3ff139733d74462a0ad5b94014e764a8Jakob Stoklund Olesen MRI->hasOneNonDBGUse(VirtReg)) { 587273f7e42994a5bce0614d04d96dbfdf05fd652e5Jakob Stoklund Olesen const MachineInstr &UseMI = *MRI->use_nodbg_begin(VirtReg); 5880c9e4f5f3ff139733d74462a0ad5b94014e764a8Jakob Stoklund Olesen // It's a copy, use the destination register as a hint. 589273f7e42994a5bce0614d04d96dbfdf05fd652e5Jakob Stoklund Olesen if (UseMI.isCopyLike()) 590273f7e42994a5bce0614d04d96dbfdf05fd652e5Jakob Stoklund Olesen Hint = UseMI.getOperand(0).getReg(); 5910c9e4f5f3ff139733d74462a0ad5b94014e764a8Jakob Stoklund Olesen } 592a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen LRI = allocVirtReg(MI, LRI, Hint); 593a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen } else if (LRI->LastUse) { 5940eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen // Redefining a live register - kill at the last use, unless it is this 5950eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen // instruction defining VirtReg multiple times. 596a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen if (LRI->LastUse != MI || LRI->LastUse->getOperand(LRI->LastOpNum).isUse()) 597a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen addKillFlag(*LRI); 5980eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen } 599a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen assert(LRI->PhysReg && "Register not assigned"); 600a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen LRI->LastUse = MI; 601a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen LRI->LastOpNum = OpNum; 602a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen LRI->Dirty = true; 603a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen UsedInInstr.set(LRI->PhysReg); 604646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund Olesen return LRI; 605bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen} 60600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 607bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen/// reloadVirtReg - Make sure VirtReg is available in a physreg and return it. 608646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund OlesenRAFast::LiveRegMap::iterator 609646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund OlesenRAFast::reloadVirtReg(MachineInstr *MI, unsigned OpNum, 610646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund Olesen unsigned VirtReg, unsigned Hint) { 611bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen assert(TargetRegisterInfo::isVirtualRegister(VirtReg) && 612bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen "Not a virtual register"); 613844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen LiveRegMap::iterator LRI; 61401dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen bool New; 615a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen tie(LRI, New) = LiveVirtRegs.insert(LiveReg(VirtReg)); 616ac3e529831877cea609ed668f95b1dc06e34698cJakob Stoklund Olesen MachineOperand &MO = MI->getOperand(OpNum); 61701dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen if (New) { 618a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen LRI = allocVirtReg(MI, LRI, Hint); 6194bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen const TargetRegisterClass *RC = MRI->getRegClass(VirtReg); 620bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen int FrameIndex = getStackSpaceFor(VirtReg, RC); 6214314268128be6d54c9a7f0709680e5a5b40f3ab3Jakob Stoklund Olesen DEBUG(dbgs() << "Reloading " << PrintReg(VirtReg, TRI) << " into " 622a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen << PrintReg(LRI->PhysReg, TRI) << "\n"); 623a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen TII->loadRegFromStackSlot(*MBB, MI, LRI->PhysReg, FrameIndex, RC, TRI); 624bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen ++NumLoads; 625a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen } else if (LRI->Dirty) { 6261e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen if (isLastUseOfLocalReg(MO)) { 6271e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen DEBUG(dbgs() << "Killing last use: " << MO << "\n"); 628d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen if (MO.isUse()) 629d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen MO.setIsKill(); 630d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen else 631d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen MO.setIsDead(); 6321e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen } else if (MO.isKill()) { 6331e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen DEBUG(dbgs() << "Clearing dubious kill: " << MO << "\n"); 6341e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen MO.setIsKill(false); 635d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen } else if (MO.isDead()) { 636d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen DEBUG(dbgs() << "Clearing dubious dead: " << MO << "\n"); 637d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen MO.setIsDead(false); 6381e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen } 639ac3e529831877cea609ed668f95b1dc06e34698cJakob Stoklund Olesen } else if (MO.isKill()) { 640ac3e529831877cea609ed668f95b1dc06e34698cJakob Stoklund Olesen // We must remove kill flags from uses of reloaded registers because the 641ac3e529831877cea609ed668f95b1dc06e34698cJakob Stoklund Olesen // register would be killed immediately, and there might be a second use: 642ac3e529831877cea609ed668f95b1dc06e34698cJakob Stoklund Olesen // %foo = OR %x<kill>, %x 643ac3e529831877cea609ed668f95b1dc06e34698cJakob Stoklund Olesen // This would cause a second reload of %x into a different register. 644ac3e529831877cea609ed668f95b1dc06e34698cJakob Stoklund Olesen DEBUG(dbgs() << "Clearing clean kill: " << MO << "\n"); 645ac3e529831877cea609ed668f95b1dc06e34698cJakob Stoklund Olesen MO.setIsKill(false); 646d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen } else if (MO.isDead()) { 647d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen DEBUG(dbgs() << "Clearing clean dead: " << MO << "\n"); 648d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen MO.setIsDead(false); 64900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 650a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen assert(LRI->PhysReg && "Register not assigned"); 651a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen LRI->LastUse = MI; 652a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen LRI->LastOpNum = OpNum; 653a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen UsedInInstr.set(LRI->PhysReg); 654646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund Olesen return LRI; 655bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen} 65600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 6570eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen// setPhysReg - Change operand OpNum in MI the refer the PhysReg, considering 6580eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen// subregs. This may invalidate any operand pointers. 6590eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen// Return true if the operand kills its register. 6600eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesenbool RAFast::setPhysReg(MachineInstr *MI, unsigned OpNum, unsigned PhysReg) { 6610eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen MachineOperand &MO = MI->getOperand(OpNum); 6626565a709702995fa8a5e659269d6cda134383be7Jakob Stoklund Olesen bool Dead = MO.isDead(); 66341e1401de5cb8752fb9d06e65e62bfe97cc1304eJakob Stoklund Olesen if (!MO.getSubReg()) { 664bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen MO.setReg(PhysReg); 6656565a709702995fa8a5e659269d6cda134383be7Jakob Stoklund Olesen return MO.isKill() || Dead; 66641e1401de5cb8752fb9d06e65e62bfe97cc1304eJakob Stoklund Olesen } 66741e1401de5cb8752fb9d06e65e62bfe97cc1304eJakob Stoklund Olesen 66841e1401de5cb8752fb9d06e65e62bfe97cc1304eJakob Stoklund Olesen // Handle subregister index. 66941e1401de5cb8752fb9d06e65e62bfe97cc1304eJakob Stoklund Olesen MO.setReg(PhysReg ? TRI->getSubReg(PhysReg, MO.getSubReg()) : 0); 67041e1401de5cb8752fb9d06e65e62bfe97cc1304eJakob Stoklund Olesen MO.setSubReg(0); 671d32e735ae6e3fbebcae9a23d7cda091770bb3a14Jakob Stoklund Olesen 672d32e735ae6e3fbebcae9a23d7cda091770bb3a14Jakob Stoklund Olesen // A kill flag implies killing the full register. Add corresponding super 673d32e735ae6e3fbebcae9a23d7cda091770bb3a14Jakob Stoklund Olesen // register kill. 674d32e735ae6e3fbebcae9a23d7cda091770bb3a14Jakob Stoklund Olesen if (MO.isKill()) { 675d32e735ae6e3fbebcae9a23d7cda091770bb3a14Jakob Stoklund Olesen MI->addRegisterKilled(PhysReg, TRI, true); 67641e1401de5cb8752fb9d06e65e62bfe97cc1304eJakob Stoklund Olesen return true; 67741e1401de5cb8752fb9d06e65e62bfe97cc1304eJakob Stoklund Olesen } 6784d10829e1296b7aea0455e000fc318b147182c1cJakob Stoklund Olesen 6794d10829e1296b7aea0455e000fc318b147182c1cJakob Stoklund Olesen // A <def,read-undef> of a sub-register requires an implicit def of the full 6804d10829e1296b7aea0455e000fc318b147182c1cJakob Stoklund Olesen // register. 6814d10829e1296b7aea0455e000fc318b147182c1cJakob Stoklund Olesen if (MO.isDef() && MO.isUndef()) 6824d10829e1296b7aea0455e000fc318b147182c1cJakob Stoklund Olesen MI->addRegisterDefined(PhysReg, TRI); 6834d10829e1296b7aea0455e000fc318b147182c1cJakob Stoklund Olesen 6846565a709702995fa8a5e659269d6cda134383be7Jakob Stoklund Olesen return Dead; 68500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 68600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 687d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen// Handle special instruction operand like early clobbers and tied ops when 688d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen// there are additional physreg defines. 689d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesenvoid RAFast::handleThroughOperands(MachineInstr *MI, 690d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen SmallVectorImpl<unsigned> &VirtDead) { 691d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen DEBUG(dbgs() << "Scanning for through registers:"); 692d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen SmallSet<unsigned, 8> ThroughRegs; 693d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 694d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen MachineOperand &MO = MI->getOperand(i); 695d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen if (!MO.isReg()) continue; 696d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen unsigned Reg = MO.getReg(); 697c9df025e33ac435adb3b3318d237c36ca7cec659Jakob Stoklund Olesen if (!TargetRegisterInfo::isVirtualRegister(Reg)) 698c9df025e33ac435adb3b3318d237c36ca7cec659Jakob Stoklund Olesen continue; 699d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen if (MO.isEarlyClobber() || MI->isRegTiedToDefOperand(i) || 700d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen (MO.getSubReg() && MI->readsVirtualRegister(Reg))) { 701d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen if (ThroughRegs.insert(Reg)) 7024314268128be6d54c9a7f0709680e5a5b40f3ab3Jakob Stoklund Olesen DEBUG(dbgs() << ' ' << PrintReg(Reg)); 703d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen } 704d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen } 705d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen 706d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen // If any physreg defines collide with preallocated through registers, 707d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen // we must spill and reallocate. 708d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen DEBUG(dbgs() << "\nChecking for physdef collisions.\n"); 709d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 710d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen MachineOperand &MO = MI->getOperand(i); 711d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen if (!MO.isReg() || !MO.isDef()) continue; 712d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen unsigned Reg = MO.getReg(); 713d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen if (!Reg || !TargetRegisterInfo::isPhysicalRegister(Reg)) continue; 7148c70ea47fae6d61441d150cbe9431cf5e06222e5Jakob Stoklund Olesen for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) { 7158c70ea47fae6d61441d150cbe9431cf5e06222e5Jakob Stoklund Olesen UsedInInstr.set(*AI); 7168c70ea47fae6d61441d150cbe9431cf5e06222e5Jakob Stoklund Olesen if (ThroughRegs.count(PhysRegState[*AI])) 7178c70ea47fae6d61441d150cbe9431cf5e06222e5Jakob Stoklund Olesen definePhysReg(MI, *AI, regFree); 718d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen } 719d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen } 720d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen 721d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen SmallVector<unsigned, 8> PartialDefs; 722254a13282c97469973b4fa8cc0e110ed6160642cRafael Espindola DEBUG(dbgs() << "Allocating tied uses.\n"); 723d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 724d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen MachineOperand &MO = MI->getOperand(i); 725d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen if (!MO.isReg()) continue; 726d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen unsigned Reg = MO.getReg(); 727c9df025e33ac435adb3b3318d237c36ca7cec659Jakob Stoklund Olesen if (!TargetRegisterInfo::isVirtualRegister(Reg)) continue; 728d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen if (MO.isUse()) { 729d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen unsigned DefIdx = 0; 730d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen if (!MI->isRegTiedToDefOperand(i, &DefIdx)) continue; 731d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen DEBUG(dbgs() << "Operand " << i << "("<< MO << ") is tied to operand " 732d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen << DefIdx << ".\n"); 733d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen LiveRegMap::iterator LRI = reloadVirtReg(MI, i, Reg, 0); 734a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen unsigned PhysReg = LRI->PhysReg; 735d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen setPhysReg(MI, i, PhysReg); 736d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen // Note: we don't update the def operand yet. That would cause the normal 737d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen // def-scan to attempt spilling. 738d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen } else if (MO.getSubReg() && MI->readsVirtualRegister(Reg)) { 739d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen DEBUG(dbgs() << "Partial redefine: " << MO << "\n"); 740d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen // Reload the register, but don't assign to the operand just yet. 741d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen // That would confuse the later phys-def processing pass. 742d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen LiveRegMap::iterator LRI = reloadVirtReg(MI, i, Reg, 0); 743a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen PartialDefs.push_back(LRI->PhysReg); 744d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen } 745d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen } 746d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen 747254a13282c97469973b4fa8cc0e110ed6160642cRafael Espindola DEBUG(dbgs() << "Allocating early clobbers.\n"); 748254a13282c97469973b4fa8cc0e110ed6160642cRafael Espindola for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 749254a13282c97469973b4fa8cc0e110ed6160642cRafael Espindola MachineOperand &MO = MI->getOperand(i); 750254a13282c97469973b4fa8cc0e110ed6160642cRafael Espindola if (!MO.isReg()) continue; 751254a13282c97469973b4fa8cc0e110ed6160642cRafael Espindola unsigned Reg = MO.getReg(); 752254a13282c97469973b4fa8cc0e110ed6160642cRafael Espindola if (!TargetRegisterInfo::isVirtualRegister(Reg)) continue; 753254a13282c97469973b4fa8cc0e110ed6160642cRafael Espindola if (!MO.isEarlyClobber()) 754254a13282c97469973b4fa8cc0e110ed6160642cRafael Espindola continue; 755254a13282c97469973b4fa8cc0e110ed6160642cRafael Espindola // Note: defineVirtReg may invalidate MO. 756254a13282c97469973b4fa8cc0e110ed6160642cRafael Espindola LiveRegMap::iterator LRI = defineVirtReg(MI, i, Reg, 0); 757a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen unsigned PhysReg = LRI->PhysReg; 758254a13282c97469973b4fa8cc0e110ed6160642cRafael Espindola if (setPhysReg(MI, i, PhysReg)) 759254a13282c97469973b4fa8cc0e110ed6160642cRafael Espindola VirtDead.push_back(Reg); 760254a13282c97469973b4fa8cc0e110ed6160642cRafael Espindola } 761254a13282c97469973b4fa8cc0e110ed6160642cRafael Espindola 762d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen // Restore UsedInInstr to a state usable for allocating normal virtual uses. 763ee72651df4b783c973bb682bef7eab2ff9a703e2Jim Grosbach UsedInInstr.reset(); 764d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 765d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen MachineOperand &MO = MI->getOperand(i); 766d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen if (!MO.isReg() || (MO.isDef() && !MO.isEarlyClobber())) continue; 767d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen unsigned Reg = MO.getReg(); 768d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen if (!Reg || !TargetRegisterInfo::isPhysicalRegister(Reg)) continue; 76927ce3b96e51887995f94d8c78a6c7e79bf7cdcddJakob Stoklund Olesen DEBUG(dbgs() << "\tSetting " << PrintReg(Reg, TRI) 77027ce3b96e51887995f94d8c78a6c7e79bf7cdcddJakob Stoklund Olesen << " as used in instr\n"); 771d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen UsedInInstr.set(Reg); 772d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen } 773d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen 774d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen // Also mark PartialDefs as used to avoid reallocation. 775d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen for (unsigned i = 0, e = PartialDefs.size(); i != e; ++i) 776d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen UsedInInstr.set(PartialDefs[i]); 777d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen} 778d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen 779b3d58474c83499621ae1e2d76dc87587910abe55Andrew Trick/// addRetOperand - ensure that a return instruction has an operand for each 780b3d58474c83499621ae1e2d76dc87587910abe55Andrew Trick/// value live out of the function. 781b3d58474c83499621ae1e2d76dc87587910abe55Andrew Trick/// 782b3d58474c83499621ae1e2d76dc87587910abe55Andrew Trick/// Things marked both call and return are tail calls; do not do this for them. 783b3d58474c83499621ae1e2d76dc87587910abe55Andrew Trick/// The tail callee need not take the same registers as input that it produces 784b3d58474c83499621ae1e2d76dc87587910abe55Andrew Trick/// as output, and there are dependencies for its input registers elsewhere. 785b3d58474c83499621ae1e2d76dc87587910abe55Andrew Trick/// 786b3d58474c83499621ae1e2d76dc87587910abe55Andrew Trick/// FIXME: This should be done as part of instruction selection, and this helper 787b3d58474c83499621ae1e2d76dc87587910abe55Andrew Trick/// should be deleted. Until then, we use custom logic here to create the proper 788b3d58474c83499621ae1e2d76dc87587910abe55Andrew Trick/// operand under all circumstances. We can't use addRegisterKilled because that 789b3d58474c83499621ae1e2d76dc87587910abe55Andrew Trick/// doesn't make sense for undefined values. We can't simply avoid calling it 790b3d58474c83499621ae1e2d76dc87587910abe55Andrew Trick/// for undefined values, because we must ensure that the operand always exists. 791b3d58474c83499621ae1e2d76dc87587910abe55Andrew Trickvoid RAFast::addRetOperands(MachineBasicBlock *MBB) { 792b3d58474c83499621ae1e2d76dc87587910abe55Andrew Trick if (MBB->empty() || !MBB->back().isReturn() || MBB->back().isCall()) 793b3d58474c83499621ae1e2d76dc87587910abe55Andrew Trick return; 79400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 795b3d58474c83499621ae1e2d76dc87587910abe55Andrew Trick MachineInstr *MI = &MBB->back(); 796b3d58474c83499621ae1e2d76dc87587910abe55Andrew Trick 797b3d58474c83499621ae1e2d76dc87587910abe55Andrew Trick for (MachineRegisterInfo::liveout_iterator 798b3d58474c83499621ae1e2d76dc87587910abe55Andrew Trick I = MBB->getParent()->getRegInfo().liveout_begin(), 799b3d58474c83499621ae1e2d76dc87587910abe55Andrew Trick E = MBB->getParent()->getRegInfo().liveout_end(); I != E; ++I) { 800b3d58474c83499621ae1e2d76dc87587910abe55Andrew Trick unsigned Reg = *I; 801b3d58474c83499621ae1e2d76dc87587910abe55Andrew Trick assert(TargetRegisterInfo::isPhysicalRegister(Reg) && 802b3d58474c83499621ae1e2d76dc87587910abe55Andrew Trick "Cannot have a live-out virtual register."); 803b3d58474c83499621ae1e2d76dc87587910abe55Andrew Trick 804b3d58474c83499621ae1e2d76dc87587910abe55Andrew Trick bool hasDef = PhysRegState[Reg] == regReserved; 805b3d58474c83499621ae1e2d76dc87587910abe55Andrew Trick 806b3d58474c83499621ae1e2d76dc87587910abe55Andrew Trick // Check if this register already has an operand. 807b3d58474c83499621ae1e2d76dc87587910abe55Andrew Trick bool Found = false; 808b3d58474c83499621ae1e2d76dc87587910abe55Andrew Trick for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 809b3d58474c83499621ae1e2d76dc87587910abe55Andrew Trick MachineOperand &MO = MI->getOperand(i); 810b3d58474c83499621ae1e2d76dc87587910abe55Andrew Trick if (!MO.isReg() || !MO.isUse()) 811b3d58474c83499621ae1e2d76dc87587910abe55Andrew Trick continue; 812b3d58474c83499621ae1e2d76dc87587910abe55Andrew Trick 813b3d58474c83499621ae1e2d76dc87587910abe55Andrew Trick unsigned OperReg = MO.getReg(); 814ab78e20ce085763b4fc9948eaa715fb7e49341c8Andrew Trick if (!TargetRegisterInfo::isPhysicalRegister(OperReg)) 815ab78e20ce085763b4fc9948eaa715fb7e49341c8Andrew Trick continue; 816ab78e20ce085763b4fc9948eaa715fb7e49341c8Andrew Trick 817ab78e20ce085763b4fc9948eaa715fb7e49341c8Andrew Trick if (OperReg == Reg || TRI->isSuperRegister(OperReg, Reg)) { 818ab78e20ce085763b4fc9948eaa715fb7e49341c8Andrew Trick // If the ret already has an operand for this physreg or a superset, 819ab78e20ce085763b4fc9948eaa715fb7e49341c8Andrew Trick // don't duplicate it. Set the kill flag if the value is defined. 820ab78e20ce085763b4fc9948eaa715fb7e49341c8Andrew Trick if (hasDef && !MO.isKill()) 821ab78e20ce085763b4fc9948eaa715fb7e49341c8Andrew Trick MO.setIsKill(); 822ab78e20ce085763b4fc9948eaa715fb7e49341c8Andrew Trick Found = true; 823ab78e20ce085763b4fc9948eaa715fb7e49341c8Andrew Trick break; 824b3d58474c83499621ae1e2d76dc87587910abe55Andrew Trick } 825c57ef561423f1ac7f2db5b1840d5681f18a4c0c8Nick Lewycky } 826b3d58474c83499621ae1e2d76dc87587910abe55Andrew Trick if (!Found) 827b3d58474c83499621ae1e2d76dc87587910abe55Andrew Trick MI->addOperand(MachineOperand::CreateReg(Reg, 828b3d58474c83499621ae1e2d76dc87587910abe55Andrew Trick false /*IsDef*/, 829b3d58474c83499621ae1e2d76dc87587910abe55Andrew Trick true /*IsImp*/, 830b3d58474c83499621ae1e2d76dc87587910abe55Andrew Trick hasDef/*IsKill*/)); 831c57ef561423f1ac7f2db5b1840d5681f18a4c0c8Nick Lewycky } 832b3d58474c83499621ae1e2d76dc87587910abe55Andrew Trick} 833b3d58474c83499621ae1e2d76dc87587910abe55Andrew Trick 834b3d58474c83499621ae1e2d76dc87587910abe55Andrew Trickvoid RAFast::AllocateBasicBlock() { 835b3d58474c83499621ae1e2d76dc87587910abe55Andrew Trick DEBUG(dbgs() << "\nAllocating " << *MBB); 836c57ef561423f1ac7f2db5b1840d5681f18a4c0c8Nick Lewycky 837bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen PhysRegState.assign(TRI->getNumRegs(), regDisabled); 838a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen assert(LiveVirtRegs.empty() && "Mapping not cleared from last block?"); 83900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 8406fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen MachineBasicBlock::iterator MII = MBB->begin(); 841bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen 842bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Add live-in registers as live. 8436fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen for (MachineBasicBlock::livein_iterator I = MBB->livein_begin(), 8446fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen E = MBB->livein_end(); I != E; ++I) 845448ab3ab395ffc9e7fc04d2d6afb41fcac74070dJakob Stoklund Olesen if (RegClassInfo.isAllocatable(*I)) 8469d4b51b696e27b9c061955d4c76f9dbff529b143Jakob Stoklund Olesen definePhysReg(MII, *I, regReserved); 847bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen 848d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen SmallVector<unsigned, 8> VirtDead; 8497ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen SmallVector<MachineInstr*, 32> Coalesced; 85000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 85100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen // Otherwise, sequentially allocate each instruction in the MBB. 8526fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen while (MII != MBB->end()) { 85300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen MachineInstr *MI = MII++; 854e837dead3c8dc3445ef6a0e2322179c57e264a13Evan Cheng const MCInstrDesc &MCID = MI->getDesc(); 85500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen DEBUG({ 856c9c4dacd03a4b80d61ed6b9c6ffeb1b1f76b8d1cJakob Stoklund Olesen dbgs() << "\n>> " << *MI << "Regs:"; 857bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen for (unsigned Reg = 1, E = TRI->getNumRegs(); Reg != E; ++Reg) { 858bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (PhysRegState[Reg] == regDisabled) continue; 859bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen dbgs() << " " << TRI->getName(Reg); 860bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen switch(PhysRegState[Reg]) { 861bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regFree: 862bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 863bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regReserved: 864c9c4dacd03a4b80d61ed6b9c6ffeb1b1f76b8d1cJakob Stoklund Olesen dbgs() << "*"; 865bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 866a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen default: { 8674314268128be6d54c9a7f0709680e5a5b40f3ab3Jakob Stoklund Olesen dbgs() << '=' << PrintReg(PhysRegState[Reg]); 868a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen LiveRegMap::iterator I = findLiveVirtReg(PhysRegState[Reg]); 869a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen assert(I != LiveVirtRegs.end() && "Missing VirtReg entry"); 870a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen if (I->Dirty) 871bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen dbgs() << "*"; 872a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen assert(I->PhysReg == Reg && "Bad inverse map"); 873bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 874bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 875a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen } 876bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 87700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen dbgs() << '\n'; 87876b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen // Check that LiveVirtRegs is the inverse. 87976b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen for (LiveRegMap::iterator i = LiveVirtRegs.begin(), 88076b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen e = LiveVirtRegs.end(); i != e; ++i) { 881a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen assert(TargetRegisterInfo::isVirtualRegister(i->VirtReg) && 882bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen "Bad map key"); 883a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen assert(TargetRegisterInfo::isPhysicalRegister(i->PhysReg) && 884bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen "Bad map value"); 885a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen assert(PhysRegState[i->PhysReg] == i->VirtReg && "Bad inverse map"); 886bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 88700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen }); 88800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 889bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Debug values are not allowed to change codegen in any way. 890bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (MI->isDebugValue()) { 89158b8176ed39038240984c0966fef847fe37c86c1Devang Patel bool ScanDbgValue = true; 89258b8176ed39038240984c0966fef847fe37c86c1Devang Patel while (ScanDbgValue) { 89358b8176ed39038240984c0966fef847fe37c86c1Devang Patel ScanDbgValue = false; 89458b8176ed39038240984c0966fef847fe37c86c1Devang Patel for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 89558b8176ed39038240984c0966fef847fe37c86c1Devang Patel MachineOperand &MO = MI->getOperand(i); 89658b8176ed39038240984c0966fef847fe37c86c1Devang Patel if (!MO.isReg()) continue; 89758b8176ed39038240984c0966fef847fe37c86c1Devang Patel unsigned Reg = MO.getReg(); 898c9df025e33ac435adb3b3318d237c36ca7cec659Jakob Stoklund Olesen if (!TargetRegisterInfo::isVirtualRegister(Reg)) continue; 899a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen LiveRegMap::iterator LRI = findLiveVirtReg(Reg); 90058b8176ed39038240984c0966fef847fe37c86c1Devang Patel if (LRI != LiveVirtRegs.end()) 901a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen setPhysReg(MI, i, LRI->PhysReg); 9027a029b6d7e58cb0f1010f14d99d7661e387cfb54Devang Patel else { 90358b8176ed39038240984c0966fef847fe37c86c1Devang Patel int SS = StackSlotForVirtReg[Reg]; 9044bafda9618f9dfa9edc8da08bb3001ef2d1a9b68Devang Patel if (SS == -1) { 90507cb689d6260b78861d829bb05b188e1558c528eJim Grosbach // We can't allocate a physreg for a DebugValue, sorry! 9064bafda9618f9dfa9edc8da08bb3001ef2d1a9b68Devang Patel DEBUG(dbgs() << "Unable to allocate vreg used by DBG_VALUE"); 90707cb689d6260b78861d829bb05b188e1558c528eJim Grosbach MO.setReg(0); 9084bafda9618f9dfa9edc8da08bb3001ef2d1a9b68Devang Patel } 90958b8176ed39038240984c0966fef847fe37c86c1Devang Patel else { 91058b8176ed39038240984c0966fef847fe37c86c1Devang Patel // Modify DBG_VALUE now that the value is in a spill slot. 911459a36bd34809ffc5d74de79b3e46f6e02e5184fDevang Patel int64_t Offset = MI->getOperand(1).getImm(); 91207cb689d6260b78861d829bb05b188e1558c528eJim Grosbach const MDNode *MDPtr = 91358b8176ed39038240984c0966fef847fe37c86c1Devang Patel MI->getOperand(MI->getNumOperands()-1).getMetadata(); 91458b8176ed39038240984c0966fef847fe37c86c1Devang Patel DebugLoc DL = MI->getDebugLoc(); 91507cb689d6260b78861d829bb05b188e1558c528eJim Grosbach if (MachineInstr *NewDV = 91658b8176ed39038240984c0966fef847fe37c86c1Devang Patel TII->emitFrameIndexDebugValue(*MF, SS, Offset, MDPtr, DL)) { 91707cb689d6260b78861d829bb05b188e1558c528eJim Grosbach DEBUG(dbgs() << "Modifying debug info due to spill:" << 91807cb689d6260b78861d829bb05b188e1558c528eJim Grosbach "\t" << *MI); 91958b8176ed39038240984c0966fef847fe37c86c1Devang Patel MachineBasicBlock *MBB = MI->getParent(); 92058b8176ed39038240984c0966fef847fe37c86c1Devang Patel MBB->insert(MBB->erase(MI), NewDV); 92158b8176ed39038240984c0966fef847fe37c86c1Devang Patel // Scan NewDV operands from the beginning. 92258b8176ed39038240984c0966fef847fe37c86c1Devang Patel MI = NewDV; 92358b8176ed39038240984c0966fef847fe37c86c1Devang Patel ScanDbgValue = true; 92458b8176ed39038240984c0966fef847fe37c86c1Devang Patel break; 9254bafda9618f9dfa9edc8da08bb3001ef2d1a9b68Devang Patel } else { 92607cb689d6260b78861d829bb05b188e1558c528eJim Grosbach // We can't allocate a physreg for a DebugValue; sorry! 9274bafda9618f9dfa9edc8da08bb3001ef2d1a9b68Devang Patel DEBUG(dbgs() << "Unable to allocate vreg used by DBG_VALUE"); 92807cb689d6260b78861d829bb05b188e1558c528eJim Grosbach MO.setReg(0); 9294bafda9618f9dfa9edc8da08bb3001ef2d1a9b68Devang Patel } 93058b8176ed39038240984c0966fef847fe37c86c1Devang Patel } 9317a029b6d7e58cb0f1010f14d99d7661e387cfb54Devang Patel } 932d2df64f56970aa07d2d8733543e4baf6c7009e91Devang Patel LiveDbgValueMap[Reg].push_back(MI); 9337a029b6d7e58cb0f1010f14d99d7661e387cfb54Devang Patel } 93400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 935bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Next instruction. 936bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen continue; 93700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 93800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 9394bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen // If this is a copy, we may be able to coalesce. 94004c528a0c86ddf3d6a70681f72e1b2ec07b0b53aJakob Stoklund Olesen unsigned CopySrc = 0, CopyDst = 0, CopySrcSub = 0, CopyDstSub = 0; 941273f7e42994a5bce0614d04d96dbfdf05fd652e5Jakob Stoklund Olesen if (MI->isCopy()) { 942273f7e42994a5bce0614d04d96dbfdf05fd652e5Jakob Stoklund Olesen CopyDst = MI->getOperand(0).getReg(); 943273f7e42994a5bce0614d04d96dbfdf05fd652e5Jakob Stoklund Olesen CopySrc = MI->getOperand(1).getReg(); 944273f7e42994a5bce0614d04d96dbfdf05fd652e5Jakob Stoklund Olesen CopyDstSub = MI->getOperand(0).getSubReg(); 945273f7e42994a5bce0614d04d96dbfdf05fd652e5Jakob Stoklund Olesen CopySrcSub = MI->getOperand(1).getSubReg(); 94604c528a0c86ddf3d6a70681f72e1b2ec07b0b53aJakob Stoklund Olesen } 9474bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen 948bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Track registers used by instruction. 949ee72651df4b783c973bb682bef7eab2ff9a703e2Jim Grosbach UsedInInstr.reset(); 95000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 951bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // First scan. 952bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Mark physreg uses and early clobbers as used. 953e97dda4fc58ee401ebb4aa9153d10f8ce8ba9a70Jakob Stoklund Olesen // Find the end of the virtreg operands 954e97dda4fc58ee401ebb4aa9153d10f8ce8ba9a70Jakob Stoklund Olesen unsigned VirtOpEnd = 0; 955d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen bool hasTiedOps = false; 956d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen bool hasEarlyClobbers = false; 957d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen bool hasPartialRedefs = false; 958d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen bool hasPhysDefs = false; 959bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 96000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen MachineOperand &MO = MI->getOperand(i); 961bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (!MO.isReg()) continue; 962bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned Reg = MO.getReg(); 963e97dda4fc58ee401ebb4aa9153d10f8ce8ba9a70Jakob Stoklund Olesen if (!Reg) continue; 964e97dda4fc58ee401ebb4aa9153d10f8ce8ba9a70Jakob Stoklund Olesen if (TargetRegisterInfo::isVirtualRegister(Reg)) { 965e97dda4fc58ee401ebb4aa9153d10f8ce8ba9a70Jakob Stoklund Olesen VirtOpEnd = i+1; 966d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen if (MO.isUse()) { 967d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen hasTiedOps = hasTiedOps || 968e837dead3c8dc3445ef6a0e2322179c57e264a13Evan Cheng MCID.getOperandConstraint(i, MCOI::TIED_TO) != -1; 969d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen } else { 970d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen if (MO.isEarlyClobber()) 971d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen hasEarlyClobbers = true; 972d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen if (MO.getSubReg() && MI->readsVirtualRegister(Reg)) 973d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen hasPartialRedefs = true; 974d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen } 975e97dda4fc58ee401ebb4aa9153d10f8ce8ba9a70Jakob Stoklund Olesen continue; 976e97dda4fc58ee401ebb4aa9153d10f8ce8ba9a70Jakob Stoklund Olesen } 977448ab3ab395ffc9e7fc04d2d6afb41fcac74070dJakob Stoklund Olesen if (!RegClassInfo.isAllocatable(Reg)) continue; 978bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (MO.isUse()) { 9794ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen usePhysReg(MO); 980bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } else if (MO.isEarlyClobber()) { 98175ac4d9c2dfb22f84da25dec03df7a07f3dad1faJakob Stoklund Olesen definePhysReg(MI, Reg, (MO.isImplicit() || MO.isDead()) ? 98275ac4d9c2dfb22f84da25dec03df7a07f3dad1faJakob Stoklund Olesen regFree : regReserved); 983d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen hasEarlyClobbers = true; 984d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen } else 985d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen hasPhysDefs = true; 986d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen } 987d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen 988d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen // The instruction may have virtual register operands that must be allocated 989d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen // the same register at use-time and def-time: early clobbers and tied 990d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen // operands. If there are also physical defs, these registers must avoid 991d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen // both physical defs and uses, making them more constrained than normal 992d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen // operands. 99307cb689d6260b78861d829bb05b188e1558c528eJim Grosbach // Similarly, if there are multiple defs and tied operands, we must make 99407cb689d6260b78861d829bb05b188e1558c528eJim Grosbach // sure the same register is allocated to uses and defs. 995d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen // We didn't detect inline asm tied operands above, so just make this extra 996d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen // pass for all inline asm. 997d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen if (MI->isInlineAsm() || hasEarlyClobbers || hasPartialRedefs || 998e837dead3c8dc3445ef6a0e2322179c57e264a13Evan Cheng (hasTiedOps && (hasPhysDefs || MCID.getNumDefs() > 1))) { 999d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen handleThroughOperands(MI, VirtDead); 1000d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen // Don't attempt coalescing when we have funny stuff going on. 1001d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen CopyDst = 0; 10024bd94f7bbe2ed6e0d83d03b06c0d20bb346abecaJakob Stoklund Olesen // Pretend we have early clobbers so the use operands get marked below. 10034bd94f7bbe2ed6e0d83d03b06c0d20bb346abecaJakob Stoklund Olesen // This is not necessary for the common case of a single tied use. 10044bd94f7bbe2ed6e0d83d03b06c0d20bb346abecaJakob Stoklund Olesen hasEarlyClobbers = true; 100500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 100600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 1007bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Second scan. 1008d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen // Allocate virtreg uses. 1009e97dda4fc58ee401ebb4aa9153d10f8ce8ba9a70Jakob Stoklund Olesen for (unsigned i = 0; i != VirtOpEnd; ++i) { 101000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen MachineOperand &MO = MI->getOperand(i); 1011bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (!MO.isReg()) continue; 101200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen unsigned Reg = MO.getReg(); 1013c9df025e33ac435adb3b3318d237c36ca7cec659Jakob Stoklund Olesen if (!TargetRegisterInfo::isVirtualRegister(Reg)) continue; 1014bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (MO.isUse()) { 1015646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund Olesen LiveRegMap::iterator LRI = reloadVirtReg(MI, i, Reg, CopyDst); 1016a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen unsigned PhysReg = LRI->PhysReg; 10177ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen CopySrc = (CopySrc == Reg || CopySrc == PhysReg) ? PhysReg : 0; 10180eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen if (setPhysReg(MI, i, PhysReg)) 1019646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund Olesen killVirtReg(LRI); 102000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 102100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 102200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 10234bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen MRI->addPhysRegsUsed(UsedInInstr); 102482b07dc4995d48065bd95affff4d8513a5cad4f2Jakob Stoklund Olesen 10254bd94f7bbe2ed6e0d83d03b06c0d20bb346abecaJakob Stoklund Olesen // Track registers defined by instruction - early clobbers and tied uses at 10264bd94f7bbe2ed6e0d83d03b06c0d20bb346abecaJakob Stoklund Olesen // this point. 1027ee72651df4b783c973bb682bef7eab2ff9a703e2Jim Grosbach UsedInInstr.reset(); 1028d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen if (hasEarlyClobbers) { 1029d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 1030d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen MachineOperand &MO = MI->getOperand(i); 10314bd94f7bbe2ed6e0d83d03b06c0d20bb346abecaJakob Stoklund Olesen if (!MO.isReg()) continue; 1032d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen unsigned Reg = MO.getReg(); 1033d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen if (!Reg || !TargetRegisterInfo::isPhysicalRegister(Reg)) continue; 10344bd94f7bbe2ed6e0d83d03b06c0d20bb346abecaJakob Stoklund Olesen // Look for physreg defs and tied uses. 10354bd94f7bbe2ed6e0d83d03b06c0d20bb346abecaJakob Stoklund Olesen if (!MO.isDef() && !MI->isRegTiedToDefOperand(i)) continue; 10368c70ea47fae6d61441d150cbe9431cf5e06222e5Jakob Stoklund Olesen for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) 10378c70ea47fae6d61441d150cbe9431cf5e06222e5Jakob Stoklund Olesen UsedInInstr.set(*AI); 1038d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen } 103900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 104000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 10414b6bbe885d851b1cfba2be9b5efc6365a2b7828aJakob Stoklund Olesen unsigned DefOpEnd = MI->getNumOperands(); 10425a96b3dad2f634c9081c8b2b6c2575441dc5a2bdEvan Cheng if (MI->isCall()) { 10434b6bbe885d851b1cfba2be9b5efc6365a2b7828aJakob Stoklund Olesen // Spill all virtregs before a call. This serves two purposes: 1. If an 104407cb689d6260b78861d829bb05b188e1558c528eJim Grosbach // exception is thrown, the landing pad is going to expect to find 104507cb689d6260b78861d829bb05b188e1558c528eJim Grosbach // registers in their spill slots, and 2. we don't have to wade through 104607cb689d6260b78861d829bb05b188e1558c528eJim Grosbach // all the <imp-def> operands on the call instruction. 10474b6bbe885d851b1cfba2be9b5efc6365a2b7828aJakob Stoklund Olesen DefOpEnd = VirtOpEnd; 10484b6bbe885d851b1cfba2be9b5efc6365a2b7828aJakob Stoklund Olesen DEBUG(dbgs() << " Spilling remaining registers before call.\n"); 10494b6bbe885d851b1cfba2be9b5efc6365a2b7828aJakob Stoklund Olesen spillAll(MI); 10506de07178e1e6445080bf4f7704e274c5f219ff70Jakob Stoklund Olesen 10516de07178e1e6445080bf4f7704e274c5f219ff70Jakob Stoklund Olesen // The imp-defs are skipped below, but we still need to mark those 10526de07178e1e6445080bf4f7704e274c5f219ff70Jakob Stoklund Olesen // registers as used by the function. 1053e837dead3c8dc3445ef6a0e2322179c57e264a13Evan Cheng SkippedInstrs.insert(&MCID); 10544b6bbe885d851b1cfba2be9b5efc6365a2b7828aJakob Stoklund Olesen } 10554b6bbe885d851b1cfba2be9b5efc6365a2b7828aJakob Stoklund Olesen 1056bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Third scan. 1057bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Allocate defs and collect dead defs. 10584b6bbe885d851b1cfba2be9b5efc6365a2b7828aJakob Stoklund Olesen for (unsigned i = 0; i != DefOpEnd; ++i) { 105900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen MachineOperand &MO = MI->getOperand(i); 106075ac4d9c2dfb22f84da25dec03df7a07f3dad1faJakob Stoklund Olesen if (!MO.isReg() || !MO.isDef() || !MO.getReg() || MO.isEarlyClobber()) 106175ac4d9c2dfb22f84da25dec03df7a07f3dad1faJakob Stoklund Olesen continue; 1062bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned Reg = MO.getReg(); 106300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 1064bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (TargetRegisterInfo::isPhysicalRegister(Reg)) { 1065448ab3ab395ffc9e7fc04d2d6afb41fcac74070dJakob Stoklund Olesen if (!RegClassInfo.isAllocatable(Reg)) continue; 10666fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen definePhysReg(MI, Reg, (MO.isImplicit() || MO.isDead()) ? 10676fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen regFree : regReserved); 1068bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen continue; 106900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 1070646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund Olesen LiveRegMap::iterator LRI = defineVirtReg(MI, i, Reg, CopySrc); 1071a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen unsigned PhysReg = LRI->PhysReg; 10720eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen if (setPhysReg(MI, i, PhysReg)) { 10730eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen VirtDead.push_back(Reg); 10747ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen CopyDst = 0; // cancel coalescing; 10757ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen } else 10767ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen CopyDst = (CopyDst == Reg || CopyDst == PhysReg) ? PhysReg : 0; 107700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 107800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 10790eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen // Kill dead defs after the scan to ensure that multiple defs of the same 10800eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen // register are allocated identically. We didn't need to do this for uses 10810eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen // because we are crerating our own kill flags, and they are always at the 10820eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen // last use. 10830eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen for (unsigned i = 0, e = VirtDead.size(); i != e; ++i) 10840eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen killVirtReg(VirtDead[i]); 10850eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen VirtDead.clear(); 10860eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen 10874bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen MRI->addPhysRegsUsed(UsedInInstr); 1088c9c4dacd03a4b80d61ed6b9c6ffeb1b1f76b8d1cJakob Stoklund Olesen 10897ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen if (CopyDst && CopyDst == CopySrc && CopyDstSub == CopySrcSub) { 10907ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen DEBUG(dbgs() << "-- coalescing: " << *MI); 10917ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen Coalesced.push_back(MI); 10927ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen } else { 10937ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen DEBUG(dbgs() << "<< " << *MI); 10947ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen } 109500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 109600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 1097bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Spill all physical registers holding virtual registers now. 1098e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen DEBUG(dbgs() << "Spilling live registers at end of block.\n"); 1099e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen spillAll(MBB->getFirstTerminator()); 110000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 11017ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen // Erase all the coalesced copies. We are delaying it until now because 1102e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen // LiveVirtRegs might refer to the instrs. 11037ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen for (unsigned i = 0, e = Coalesced.size(); i != e; ++i) 11046fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen MBB->erase(Coalesced[i]); 11058a65c510a4fa1245d101da6318618d025702028cJakob Stoklund Olesen NumCopies += Coalesced.size(); 11067ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen 1107b3d58474c83499621ae1e2d76dc87587910abe55Andrew Trick // addRetOperands must run after we've seen all defs in this block. 1108b3d58474c83499621ae1e2d76dc87587910abe55Andrew Trick addRetOperands(MBB); 1109b3d58474c83499621ae1e2d76dc87587910abe55Andrew Trick 11106fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen DEBUG(MBB->dump()); 111100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 111200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 111300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen/// runOnMachineFunction - Register allocate the whole function 111400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen/// 111500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesenbool RAFast::runOnMachineFunction(MachineFunction &Fn) { 1116c9c4dacd03a4b80d61ed6b9c6ffeb1b1f76b8d1cJakob Stoklund Olesen DEBUG(dbgs() << "********** FAST REGISTER ALLOCATION **********\n" 1117c9c4dacd03a4b80d61ed6b9c6ffeb1b1f76b8d1cJakob Stoklund Olesen << "********** Function: " 1118c9c4dacd03a4b80d61ed6b9c6ffeb1b1f76b8d1cJakob Stoklund Olesen << ((Value*)Fn.getFunction())->getName() << '\n'); 111900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen MF = &Fn; 11204bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen MRI = &MF->getRegInfo(); 112100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen TM = &Fn.getTarget(); 112200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen TRI = TM->getRegisterInfo(); 112300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen TII = TM->getInstrInfo(); 1124d9e5c764bfea339fc5082bf17e558db959fd6d28Jakob Stoklund Olesen MRI->freezeReservedRegs(Fn); 11255d20c3152bd7fe91eda1b58a5eb6da7067874c61Jakob Stoklund Olesen RegClassInfo.runOnMachineFunction(Fn); 112600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen UsedInInstr.resize(TRI->getNumRegs()); 112700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 11288dd26253f54247e77e5accfdd70e7b4bf27b39c2Andrew Trick assert(!MRI->isSSA() && "regalloc requires leaving SSA"); 11298dd26253f54247e77e5accfdd70e7b4bf27b39c2Andrew Trick 113000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen // initialize the virtual->physical register map to have a 'null' 113100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen // mapping for all virtual registers 113242e9c963921776cb498c33b6c6c03f29971316f3Jakob Stoklund Olesen StackSlotForVirtReg.resize(MRI->getNumVirtRegs()); 1133a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen LiveVirtRegs.setUniverse(MRI->getNumVirtRegs()); 113400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 113500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen // Loop over all of the basic blocks, eliminating virtual register references 11366fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen for (MachineFunction::iterator MBBi = Fn.begin(), MBBe = Fn.end(); 11376fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen MBBi != MBBe; ++MBBi) { 11386fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen MBB = &*MBBi; 11396fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen AllocateBasicBlock(); 11406fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen } 114100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 11426de07178e1e6445080bf4f7704e274c5f219ff70Jakob Stoklund Olesen // Add the clobber lists for all the instructions we skipped earlier. 1143e837dead3c8dc3445ef6a0e2322179c57e264a13Evan Cheng for (SmallPtrSet<const MCInstrDesc*, 4>::const_iterator 11446de07178e1e6445080bf4f7704e274c5f219ff70Jakob Stoklund Olesen I = SkippedInstrs.begin(), E = SkippedInstrs.end(); I != E; ++I) 1145fac259814923d091942b230e7bd002a8d1130bc3Craig Topper if (const uint16_t *Defs = (*I)->getImplicitDefs()) 11466de07178e1e6445080bf4f7704e274c5f219ff70Jakob Stoklund Olesen while (*Defs) 11476de07178e1e6445080bf4f7704e274c5f219ff70Jakob Stoklund Olesen MRI->setPhysRegUsed(*Defs++); 11486de07178e1e6445080bf4f7704e274c5f219ff70Jakob Stoklund Olesen 114919273aec441411b4d571fdb87c6daa0fbe7a33a0Andrew Trick // All machine operands and other references to virtual registers have been 115019273aec441411b4d571fdb87c6daa0fbe7a33a0Andrew Trick // replaced. Remove the virtual registers. 115119273aec441411b4d571fdb87c6daa0fbe7a33a0Andrew Trick MRI->clearVirtRegs(); 115219273aec441411b4d571fdb87c6daa0fbe7a33a0Andrew Trick 11536de07178e1e6445080bf4f7704e274c5f219ff70Jakob Stoklund Olesen SkippedInstrs.clear(); 115400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen StackSlotForVirtReg.clear(); 1155459a36bd34809ffc5d74de79b3e46f6e02e5184fDevang Patel LiveDbgValueMap.clear(); 115600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen return true; 115700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 115800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 115900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund OlesenFunctionPass *llvm::createFastRegisterAllocator() { 116000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen return new RAFast(); 116100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 1162