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" 16d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/CodeGen/Passes.h" 17d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/DenseMap.h" 18d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/IndexedMap.h" 19d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/STLExtras.h" 20d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/SmallSet.h" 21d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/SmallVector.h" 22d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/SparseSet.h" 23d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/Statistic.h" 24d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/CodeGen/MachineFrameInfo.h" 2500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include "llvm/CodeGen/MachineFunctionPass.h" 2600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include "llvm/CodeGen/MachineInstr.h" 27459a36bd34809ffc5d74de79b3e46f6e02e5184fDevang Patel#include "llvm/CodeGen/MachineInstrBuilder.h" 2800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include "llvm/CodeGen/MachineRegisterInfo.h" 2900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include "llvm/CodeGen/RegAllocRegistry.h" 301525260b3e50cc578939ef41b60609689eecfdd2Andrew Trick#include "llvm/CodeGen/RegisterClassInfo.h" 310b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/BasicBlock.h" 3200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include "llvm/Support/CommandLine.h" 3300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include "llvm/Support/Debug.h" 3400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include "llvm/Support/ErrorHandling.h" 3500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include "llvm/Support/raw_ostream.h" 36d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Target/TargetInstrInfo.h" 37d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Target/TargetMachine.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 116601158a18e325879b224bd1979d824407ed98bc7Jakob Stoklund Olesen // Set of register units. 117d7ea7d5cd7518788dea698d38023959480c8263aJakob Stoklund Olesen typedef SparseSet<unsigned> UsedInInstrSet; 118d7ea7d5cd7518788dea698d38023959480c8263aJakob Stoklund Olesen 119601158a18e325879b224bd1979d824407ed98bc7Jakob Stoklund Olesen // Set of register units that are used in the current instruction, and so 120601158a18e325879b224bd1979d824407ed98bc7Jakob Stoklund Olesen // cannot be allocated. 121d7ea7d5cd7518788dea698d38023959480c8263aJakob Stoklund Olesen UsedInInstrSet UsedInInstr; 12200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 123601158a18e325879b224bd1979d824407ed98bc7Jakob Stoklund Olesen // Mark a physreg as used in this instruction. 124601158a18e325879b224bd1979d824407ed98bc7Jakob Stoklund Olesen void markRegUsedInInstr(unsigned PhysReg) { 125601158a18e325879b224bd1979d824407ed98bc7Jakob Stoklund Olesen for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) 126601158a18e325879b224bd1979d824407ed98bc7Jakob Stoklund Olesen UsedInInstr.insert(*Units); 127601158a18e325879b224bd1979d824407ed98bc7Jakob Stoklund Olesen } 128601158a18e325879b224bd1979d824407ed98bc7Jakob Stoklund Olesen 129601158a18e325879b224bd1979d824407ed98bc7Jakob Stoklund Olesen // Check if a physreg or any of its aliases are used in this instruction. 130601158a18e325879b224bd1979d824407ed98bc7Jakob Stoklund Olesen bool isRegUsedInInstr(unsigned PhysReg) const { 131601158a18e325879b224bd1979d824407ed98bc7Jakob Stoklund Olesen for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) 132601158a18e325879b224bd1979d824407ed98bc7Jakob Stoklund Olesen if (UsedInInstr.count(*Units)) 133601158a18e325879b224bd1979d824407ed98bc7Jakob Stoklund Olesen return true; 134601158a18e325879b224bd1979d824407ed98bc7Jakob Stoklund Olesen return false; 135601158a18e325879b224bd1979d824407ed98bc7Jakob Stoklund Olesen } 136601158a18e325879b224bd1979d824407ed98bc7Jakob Stoklund Olesen 13707cb689d6260b78861d829bb05b188e1558c528eJim Grosbach // SkippedInstrs - Descriptors of instructions whose clobber list was 13807cb689d6260b78861d829bb05b188e1558c528eJim Grosbach // ignored because all registers were spilled. It is still necessary to 13907cb689d6260b78861d829bb05b188e1558c528eJim Grosbach // mark all the clobbered registers as used by the function. 140e837dead3c8dc3445ef6a0e2322179c57e264a13Evan Cheng SmallPtrSet<const MCInstrDesc*, 4> SkippedInstrs; 1416de07178e1e6445080bf4f7704e274c5f219ff70Jakob Stoklund Olesen 142e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen // isBulkSpilling - This flag is set when LiveRegMap will be cleared 143e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen // completely after spilling all live registers. LiveRegMap entries should 144e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen // not be erased. 145e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen bool isBulkSpilling; 1467d4f25904de543b039a28eddbea3034a5d80e7f8Jakob Stoklund Olesen 147548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen enum { 148548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen spillClean = 1, 149548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen spillDirty = 100, 150548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen spillImpossible = ~0u 151548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen }; 15200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen public: 15300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen virtual const char *getPassName() const { 15400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen return "Fast Register Allocator"; 15500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 15600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 15700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen virtual void getAnalysisUsage(AnalysisUsage &AU) const { 15800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen AU.setPreservesCFG(); 15900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen MachineFunctionPass::getAnalysisUsage(AU); 16000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 16100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 16200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen private: 16300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen bool runOnMachineFunction(MachineFunction &Fn); 1646fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen void AllocateBasicBlock(); 165d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen void handleThroughOperands(MachineInstr *MI, 166d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen SmallVectorImpl<unsigned> &VirtDead); 16700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen int getStackSpaceFor(unsigned VirtReg, const TargetRegisterClass *RC); 1681e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen bool isLastUseOfLocalReg(MachineOperand&); 1691e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen 17001dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen void addKillFlag(const LiveReg&); 171844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen void killVirtReg(LiveRegMap::iterator); 172804291e31658d46fb1db5ecaf42b31950c02a6f2Jakob Stoklund Olesen void killVirtReg(unsigned VirtReg); 173844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen void spillVirtReg(MachineBasicBlock::iterator MI, LiveRegMap::iterator); 174e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen void spillVirtReg(MachineBasicBlock::iterator MI, unsigned VirtReg); 1754ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen 1764ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen void usePhysReg(MachineOperand&); 1776fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen void definePhysReg(MachineInstr *MI, unsigned PhysReg, RegState NewState); 178548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen unsigned calcSpillCost(unsigned PhysReg) const; 179a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen void assignVirtToPhysReg(LiveReg&, unsigned PhysReg); 180a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen LiveRegMap::iterator findLiveVirtReg(unsigned VirtReg) { 181a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen return LiveVirtRegs.find(TargetRegisterInfo::virtReg2Index(VirtReg)); 182a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen } 183a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen LiveRegMap::const_iterator findLiveVirtReg(unsigned VirtReg) const { 184a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen return LiveVirtRegs.find(TargetRegisterInfo::virtReg2Index(VirtReg)); 185a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen } 186a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen LiveRegMap::iterator assignVirtToPhysReg(unsigned VReg, unsigned PhysReg); 187a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen LiveRegMap::iterator allocVirtReg(MachineInstr *MI, LiveRegMap::iterator, 188a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen unsigned Hint); 189646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund Olesen LiveRegMap::iterator defineVirtReg(MachineInstr *MI, unsigned OpNum, 190646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund Olesen unsigned VirtReg, unsigned Hint); 191646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund Olesen LiveRegMap::iterator reloadVirtReg(MachineInstr *MI, unsigned OpNum, 192646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund Olesen unsigned VirtReg, unsigned Hint); 193bab24216cc77477d475e9d2ae18e275c5b2054a3Akira Hatanaka void spillAll(MachineBasicBlock::iterator MI); 1940eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen bool setPhysReg(MachineInstr *MI, unsigned OpNum, unsigned PhysReg); 19500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen }; 19600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen char RAFast::ID = 0; 19700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 19800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 19900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen/// getStackSpaceFor - This allocates space for the specified virtual register 20000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen/// to be held on the stack. 20100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesenint RAFast::getStackSpaceFor(unsigned VirtReg, const TargetRegisterClass *RC) { 20200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen // Find the location Reg would belong... 20300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen int SS = StackSlotForVirtReg[VirtReg]; 20400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen if (SS != -1) 20500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen return SS; // Already has space allocated? 20600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 20700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen // Allocate a new stack object for this spill location... 20800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen int FrameIdx = MF->getFrameInfo()->CreateSpillStackObject(RC->getSize(), 20900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen RC->getAlignment()); 21000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 21100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen // Assign the slot. 21200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen StackSlotForVirtReg[VirtReg] = FrameIdx; 21300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen return FrameIdx; 21400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 21500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 2161e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen/// isLastUseOfLocalReg - Return true if MO is the only remaining reference to 2171e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen/// its virtual register, and it is guaranteed to be a block-local register. 2181e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen/// 2191e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesenbool RAFast::isLastUseOfLocalReg(MachineOperand &MO) { 2201e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen // If the register has ever been spilled or reloaded, we conservatively assume 2211e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen // it is a global register used in multiple blocks. 2221e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen if (StackSlotForVirtReg[MO.getReg()] != -1) 2231e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen return false; 2241e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen 2251e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen // Check that the use/def chain has exactly one operand - MO. 2264e6966266a6dbbd560e11f68e6a5ff3fd35c130dJakob Stoklund Olesen MachineRegisterInfo::reg_nodbg_iterator I = MRI->reg_nodbg_begin(MO.getReg()); 2274e6966266a6dbbd560e11f68e6a5ff3fd35c130dJakob Stoklund Olesen if (&I.getOperand() != &MO) 2284e6966266a6dbbd560e11f68e6a5ff3fd35c130dJakob Stoklund Olesen return false; 2294e6966266a6dbbd560e11f68e6a5ff3fd35c130dJakob Stoklund Olesen return ++I == MRI->reg_nodbg_end(); 2301e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen} 2311e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen 232804291e31658d46fb1db5ecaf42b31950c02a6f2Jakob Stoklund Olesen/// addKillFlag - Set kill flags on last use of a virtual register. 23301dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesenvoid RAFast::addKillFlag(const LiveReg &LR) { 23401dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen if (!LR.LastUse) return; 23501dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen MachineOperand &MO = LR.LastUse->getOperand(LR.LastOpNum); 236d32e735ae6e3fbebcae9a23d7cda091770bb3a14Jakob Stoklund Olesen if (MO.isUse() && !LR.LastUse->isRegTiedToDefOperand(LR.LastOpNum)) { 237d32e735ae6e3fbebcae9a23d7cda091770bb3a14Jakob Stoklund Olesen if (MO.getReg() == LR.PhysReg) 2380eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen MO.setIsKill(); 2390eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen else 2400eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen LR.LastUse->addRegisterKilled(LR.PhysReg, TRI, true); 2410eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen } 242804291e31658d46fb1db5ecaf42b31950c02a6f2Jakob Stoklund Olesen} 243804291e31658d46fb1db5ecaf42b31950c02a6f2Jakob Stoklund Olesen 244804291e31658d46fb1db5ecaf42b31950c02a6f2Jakob Stoklund Olesen/// killVirtReg - Mark virtreg as no longer available. 245844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesenvoid RAFast::killVirtReg(LiveRegMap::iterator LRI) { 246a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen addKillFlag(*LRI); 24791ba63d230bfc3e035d2851d039e08f34f0b9bbdJakob Stoklund Olesen assert(PhysRegState[LRI->PhysReg] == LRI->VirtReg && 24891ba63d230bfc3e035d2851d039e08f34f0b9bbdJakob Stoklund Olesen "Broken RegState mapping"); 249a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen PhysRegState[LRI->PhysReg] = regFree; 250e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen // Erase from LiveVirtRegs unless we're spilling in bulk. 251e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen if (!isBulkSpilling) 252844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen LiveVirtRegs.erase(LRI); 25376b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen} 25476b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen 25576b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen/// killVirtReg - Mark virtreg as no longer available. 256bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesenvoid RAFast::killVirtReg(unsigned VirtReg) { 257bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen assert(TargetRegisterInfo::isVirtualRegister(VirtReg) && 258bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen "killVirtReg needs a virtual register"); 259a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen LiveRegMap::iterator LRI = findLiveVirtReg(VirtReg); 260844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen if (LRI != LiveVirtRegs.end()) 261844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen killVirtReg(LRI); 26200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 26300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 264bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen/// spillVirtReg - This method spills the value specified by VirtReg into the 26524a1182184336c088f70e86191ebda47df629bebEli Friedman/// corresponding stack slot if needed. 266e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesenvoid RAFast::spillVirtReg(MachineBasicBlock::iterator MI, unsigned VirtReg) { 267bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen assert(TargetRegisterInfo::isVirtualRegister(VirtReg) && 268bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen "Spilling a physical register is illegal!"); 269a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen LiveRegMap::iterator LRI = findLiveVirtReg(VirtReg); 270844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen assert(LRI != LiveVirtRegs.end() && "Spilling unmapped virtual register"); 271844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen spillVirtReg(MI, LRI); 2727d4f25904de543b039a28eddbea3034a5d80e7f8Jakob Stoklund Olesen} 2737d4f25904de543b039a28eddbea3034a5d80e7f8Jakob Stoklund Olesen 2747d4f25904de543b039a28eddbea3034a5d80e7f8Jakob Stoklund Olesen/// spillVirtReg - Do the actual work of spilling. 2756fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesenvoid RAFast::spillVirtReg(MachineBasicBlock::iterator MI, 276844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen LiveRegMap::iterator LRI) { 277a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen LiveReg &LR = *LRI; 278a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen assert(PhysRegState[LR.PhysReg] == LRI->VirtReg && "Broken RegState mapping"); 27976b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen 280210e2afcc74e8ce5102d13939b23040fafa71c09Jakob Stoklund Olesen if (LR.Dirty) { 281e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen // If this physreg is used by the instruction, we want to kill it on the 282e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen // instruction, not on the spill. 283844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen bool SpillKill = LR.LastUse != MI; 284210e2afcc74e8ce5102d13939b23040fafa71c09Jakob Stoklund Olesen LR.Dirty = false; 285a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen DEBUG(dbgs() << "Spilling " << PrintReg(LRI->VirtReg, TRI) 2864314268128be6d54c9a7f0709680e5a5b40f3ab3Jakob Stoklund Olesen << " in " << PrintReg(LR.PhysReg, TRI)); 287a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen const TargetRegisterClass *RC = MRI->getRegClass(LRI->VirtReg); 288a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen int FI = getStackSpaceFor(LRI->VirtReg, RC); 2896fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen DEBUG(dbgs() << " to stack slot #" << FI << "\n"); 290844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen TII->storeRegToStackSlot(*MBB, MI, LR.PhysReg, SpillKill, FI, RC, TRI); 29100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen ++NumStores; // Update statistics 29200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 29307cb689d6260b78861d829bb05b188e1558c528eJim Grosbach // If this register is used by DBG_VALUE then insert new DBG_VALUE to 294459a36bd34809ffc5d74de79b3e46f6e02e5184fDevang Patel // identify spilled location as the place to find corresponding variable's 295459a36bd34809ffc5d74de79b3e46f6e02e5184fDevang Patel // value. 296a0ec3f9b7b826b9b40b80199923b664bad808cceCraig Topper SmallVectorImpl<MachineInstr *> &LRIDbgValues = 297a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen LiveDbgValueMap[LRI->VirtReg]; 29872d9b0e4fce90a635af5c80cb6992ac639279d59Devang Patel for (unsigned li = 0, le = LRIDbgValues.size(); li != le; ++li) { 29972d9b0e4fce90a635af5c80cb6992ac639279d59Devang Patel MachineInstr *DBG = LRIDbgValues[li]; 3006d9dbd5526e3161db884fc4fe99c278bb59ccc19David Blaikie const MDNode *MDPtr = DBG->getOperand(2).getMetadata(); 3013517640443f0b5224e2a6414c246ac60016ee9d4Adrian Prantl bool IsIndirect = DBG->getOperand(1).isImm(); // Register-indirect value? 30243ae5e85f829df883dd364c0b9612bbe90f3ad97Adrian Prantl uint64_t Offset = IsIndirect ? DBG->getOperand(1).getImm() : 0; 30331defcf2349916ac759be33baaa4060703fd78dfDevang Patel DebugLoc DL; 30431defcf2349916ac759be33baaa4060703fd78dfDevang Patel if (MI == MBB->end()) { 30531defcf2349916ac759be33baaa4060703fd78dfDevang Patel // If MI is at basic block end then use last instruction's location. 30631defcf2349916ac759be33baaa4060703fd78dfDevang Patel MachineBasicBlock::iterator EI = MI; 30731defcf2349916ac759be33baaa4060703fd78dfDevang Patel DL = (--EI)->getDebugLoc(); 3086d9dbd5526e3161db884fc4fe99c278bb59ccc19David Blaikie } else 30931defcf2349916ac759be33baaa4060703fd78dfDevang Patel DL = MI->getDebugLoc(); 3106d9dbd5526e3161db884fc4fe99c278bb59ccc19David Blaikie MachineBasicBlock *MBB = DBG->getParent(); 3116d9dbd5526e3161db884fc4fe99c278bb59ccc19David Blaikie MachineInstr *NewDV = 3126d9dbd5526e3161db884fc4fe99c278bb59ccc19David Blaikie BuildMI(*MBB, MI, DL, TII->get(TargetOpcode::DBG_VALUE)) 3136d9dbd5526e3161db884fc4fe99c278bb59ccc19David Blaikie .addFrameIndex(FI).addImm(Offset).addMetadata(MDPtr); 3146d9dbd5526e3161db884fc4fe99c278bb59ccc19David Blaikie (void)NewDV; 3156d9dbd5526e3161db884fc4fe99c278bb59ccc19David Blaikie DEBUG(dbgs() << "Inserting debug info due to spill:" << "\n" << *NewDV); 316459a36bd34809ffc5d74de79b3e46f6e02e5184fDevang Patel } 31791ba63d230bfc3e035d2851d039e08f34f0b9bbdJakob Stoklund Olesen // Now this register is spilled there is should not be any DBG_VALUE 31891ba63d230bfc3e035d2851d039e08f34f0b9bbdJakob Stoklund Olesen // pointing to this register because they are all pointing to spilled value 31991ba63d230bfc3e035d2851d039e08f34f0b9bbdJakob Stoklund Olesen // now. 3206f373a87cba3b0c88bc76bf1d03ee5f81143764fDevang Patel LRIDbgValues.clear(); 321844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen if (SpillKill) 322210e2afcc74e8ce5102d13939b23040fafa71c09Jakob Stoklund Olesen LR.LastUse = 0; // Don't kill register again 323bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 324844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen killVirtReg(LRI); 32500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 32600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 327bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen/// spillAll - Spill all dirty virtregs without killing them. 328bab24216cc77477d475e9d2ae18e275c5b2054a3Akira Hatanakavoid RAFast::spillAll(MachineBasicBlock::iterator MI) { 329f3ea06b108d45c53dade87d6f1f48ac0a0e20562Jakob Stoklund Olesen if (LiveVirtRegs.empty()) return; 330e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen isBulkSpilling = true; 3312997985b4cafc2a1e562819a2f3e0c6abe5fb223Jakob Stoklund Olesen // The LiveRegMap is keyed by an unsigned (the virtreg number), so the order 3322997985b4cafc2a1e562819a2f3e0c6abe5fb223Jakob Stoklund Olesen // of spilling here is deterministic, if arbitrary. 3332997985b4cafc2a1e562819a2f3e0c6abe5fb223Jakob Stoklund Olesen for (LiveRegMap::iterator i = LiveVirtRegs.begin(), e = LiveVirtRegs.end(); 3342997985b4cafc2a1e562819a2f3e0c6abe5fb223Jakob Stoklund Olesen i != e; ++i) 335e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen spillVirtReg(MI, i); 336e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen LiveVirtRegs.clear(); 337e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen isBulkSpilling = false; 338bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen} 33900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 3404ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen/// usePhysReg - Handle the direct use of a physical register. 3414ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen/// Check that the register is not used by a virtreg. 3424ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen/// Kill the physreg, marking it free. 3434ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen/// This may add implicit kills to MO->getParent() and invalidate MO. 3444ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesenvoid RAFast::usePhysReg(MachineOperand &MO) { 3454ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen unsigned PhysReg = MO.getReg(); 3464ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen assert(TargetRegisterInfo::isPhysicalRegister(PhysReg) && 3474ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen "Bad usePhysReg operand"); 348601158a18e325879b224bd1979d824407ed98bc7Jakob Stoklund Olesen markRegUsedInInstr(PhysReg); 3494ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen switch (PhysRegState[PhysReg]) { 350bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regDisabled: 351bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 352bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regReserved: 353bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen PhysRegState[PhysReg] = regFree; 3544ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen // Fall through 3554ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen case regFree: 3564ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen MO.setIsKill(); 357bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen return; 358bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen default: 359f299da8ec3fee88a1b275560a7f94be4cf10d089Eric Christopher // The physreg was allocated to a virtual register. That means the value we 3604ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen // wanted has been clobbered. 3614ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen llvm_unreachable("Instruction uses an allocated register"); 36200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 36300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 3644ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen // Maybe a superregister is reserved? 365396618b43a85e12d290a90b181c6af5d7c0c5f11Jakob Stoklund Olesen for (MCRegAliasIterator AI(PhysReg, TRI, false); AI.isValid(); ++AI) { 366396618b43a85e12d290a90b181c6af5d7c0c5f11Jakob Stoklund Olesen unsigned Alias = *AI; 3674ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen switch (PhysRegState[Alias]) { 368bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regDisabled: 369bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 370bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regReserved: 3714ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen assert(TRI->isSuperRegister(PhysReg, Alias) && 3724ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen "Instruction is not using a subregister of a reserved register"); 3734ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen // Leave the superregister in the working set. 374bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen PhysRegState[Alias] = regFree; 3754ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen MO.getParent()->addRegisterKilled(Alias, TRI, true); 3764ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen return; 3774ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen case regFree: 3784ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen if (TRI->isSuperRegister(PhysReg, Alias)) { 3794ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen // Leave the superregister in the working set. 3804ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen MO.getParent()->addRegisterKilled(Alias, TRI, true); 3814ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen return; 3824ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen } 3834ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen // Some other alias was in the working set - clear it. 3844ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen PhysRegState[Alias] = regDisabled; 385bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 386bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen default: 3874ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen llvm_unreachable("Instruction uses an alias of an allocated register"); 388bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 38900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 3904ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen 3914ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen // All aliases are disabled, bring register into working set. 3924ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen PhysRegState[PhysReg] = regFree; 3934ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen MO.setIsKill(); 39400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 39500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 3964ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen/// definePhysReg - Mark PhysReg as reserved or free after spilling any 3974ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen/// virtregs. This is very similar to defineVirtReg except the physreg is 3984ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen/// reserved instead of allocated. 3996fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesenvoid RAFast::definePhysReg(MachineInstr *MI, unsigned PhysReg, 4006fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen RegState NewState) { 401601158a18e325879b224bd1979d824407ed98bc7Jakob Stoklund Olesen markRegUsedInInstr(PhysReg); 402bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen switch (unsigned VirtReg = PhysRegState[PhysReg]) { 403bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regDisabled: 404bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 4054ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen default: 406e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen spillVirtReg(MI, VirtReg); 4074ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen // Fall through. 408bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regFree: 409bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regReserved: 4104ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen PhysRegState[PhysReg] = NewState; 411bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen return; 412bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 413bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen 4144ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen // This is a disabled register, disable all aliases. 4154ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen PhysRegState[PhysReg] = NewState; 416396618b43a85e12d290a90b181c6af5d7c0c5f11Jakob Stoklund Olesen for (MCRegAliasIterator AI(PhysReg, TRI, false); AI.isValid(); ++AI) { 417396618b43a85e12d290a90b181c6af5d7c0c5f11Jakob Stoklund Olesen unsigned Alias = *AI; 418bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen switch (unsigned VirtReg = PhysRegState[Alias]) { 419bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regDisabled: 420bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 421bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen default: 422e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen spillVirtReg(MI, VirtReg); 4234ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen // Fall through. 4244ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen case regFree: 4254ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen case regReserved: 4264ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen PhysRegState[Alias] = regDisabled; 4274ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen if (TRI->isSuperRegister(PhysReg, Alias)) 4284ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen return; 429bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 430bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 431bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 432bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen} 43300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 4344ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen 435548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen// calcSpillCost - Return the cost of spilling clearing out PhysReg and 436548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen// aliases so it is free for allocation. 437548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen// Returns 0 when PhysReg is free or disabled with all aliases disabled - it 438548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen// can be allocated directly. 439548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen// Returns spillImpossible when PhysReg or an alias can't be spilled. 440548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesenunsigned RAFast::calcSpillCost(unsigned PhysReg) const { 441601158a18e325879b224bd1979d824407ed98bc7Jakob Stoklund Olesen if (isRegUsedInInstr(PhysReg)) { 44227ce3b96e51887995f94d8c78a6c7e79bf7cdcddJakob Stoklund Olesen DEBUG(dbgs() << PrintReg(PhysReg, TRI) << " is already used in instr.\n"); 443b8acb7be804c8c537f2475f3a24303a0b37ab107Jakob Stoklund Olesen return spillImpossible; 4440b756349a718e046abba84c316877a682eb0ff2fEric Christopher } 445548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen switch (unsigned VirtReg = PhysRegState[PhysReg]) { 446548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen case regDisabled: 447548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen break; 448548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen case regFree: 449548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen return 0; 450548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen case regReserved: 45127ce3b96e51887995f94d8c78a6c7e79bf7cdcddJakob Stoklund Olesen DEBUG(dbgs() << PrintReg(VirtReg, TRI) << " corresponding " 45227ce3b96e51887995f94d8c78a6c7e79bf7cdcddJakob Stoklund Olesen << PrintReg(PhysReg, TRI) << " is reserved already.\n"); 453548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen return spillImpossible; 454a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen default: { 455a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen LiveRegMap::const_iterator I = findLiveVirtReg(VirtReg); 456a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen assert(I != LiveVirtRegs.end() && "Missing VirtReg entry"); 457a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen return I->Dirty ? spillDirty : spillClean; 458a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen } 459548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen } 460548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen 461bbfc3b30986ff89487350cade99ea7c90e2c8165Eric Christopher // This is a disabled register, add up cost of aliases. 46227ce3b96e51887995f94d8c78a6c7e79bf7cdcddJakob Stoklund Olesen DEBUG(dbgs() << PrintReg(PhysReg, TRI) << " is disabled.\n"); 463548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen unsigned Cost = 0; 464396618b43a85e12d290a90b181c6af5d7c0c5f11Jakob Stoklund Olesen for (MCRegAliasIterator AI(PhysReg, TRI, false); AI.isValid(); ++AI) { 465396618b43a85e12d290a90b181c6af5d7c0c5f11Jakob Stoklund Olesen unsigned Alias = *AI; 466548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen switch (unsigned VirtReg = PhysRegState[Alias]) { 467548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen case regDisabled: 468548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen break; 469548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen case regFree: 470548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen ++Cost; 471548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen break; 472548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen case regReserved: 473548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen return spillImpossible; 474a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen default: { 475a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen LiveRegMap::const_iterator I = findLiveVirtReg(VirtReg); 476a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen assert(I != LiveVirtRegs.end() && "Missing VirtReg entry"); 477a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen Cost += I->Dirty ? spillDirty : spillClean; 478548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen break; 479548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen } 480a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen } 481548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen } 482548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen return Cost; 483548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen} 484548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen 485548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen 48600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen/// assignVirtToPhysReg - This method updates local state so that we know 48700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen/// that PhysReg is the proper container for VirtReg now. The physical 48800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen/// register must not be used for anything else when this is called. 48900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen/// 490a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesenvoid RAFast::assignVirtToPhysReg(LiveReg &LR, unsigned PhysReg) { 491a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen DEBUG(dbgs() << "Assigning " << PrintReg(LR.VirtReg, TRI) << " to " 4924314268128be6d54c9a7f0709680e5a5b40f3ab3Jakob Stoklund Olesen << PrintReg(PhysReg, TRI) << "\n"); 493a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen PhysRegState[PhysReg] = LR.VirtReg; 494a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen assert(!LR.PhysReg && "Already assigned a physreg"); 495a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen LR.PhysReg = PhysReg; 496a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen} 497a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen 498a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund OlesenRAFast::LiveRegMap::iterator 499a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund OlesenRAFast::assignVirtToPhysReg(unsigned VirtReg, unsigned PhysReg) { 500a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen LiveRegMap::iterator LRI = findLiveVirtReg(VirtReg); 501a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen assert(LRI != LiveVirtRegs.end() && "VirtReg disappeared"); 502a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen assignVirtToPhysReg(*LRI, PhysReg); 503a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen return LRI; 50400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 50500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 506bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen/// allocVirtReg - Allocate a physical register for VirtReg. 507a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund OlesenRAFast::LiveRegMap::iterator RAFast::allocVirtReg(MachineInstr *MI, 508a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen LiveRegMap::iterator LRI, 509a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen unsigned Hint) { 510a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen const unsigned VirtReg = LRI->VirtReg; 51101dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen 512bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen assert(TargetRegisterInfo::isVirtualRegister(VirtReg) && 513bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen "Can only allocate virtual registers"); 51400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 5154bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen const TargetRegisterClass *RC = MRI->getRegClass(VirtReg); 516bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen 5174bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen // Ignore invalid hints. 5184bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen if (Hint && (!TargetRegisterInfo::isPhysicalRegister(Hint) || 51914d1dd95c7c969e07defebb6fe65df2fae1b30cfJakob Stoklund Olesen !RC->contains(Hint) || !MRI->isAllocatable(Hint))) 5204bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen Hint = 0; 5214bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen 5224bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen // Take hint when possible. 5234bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen if (Hint) { 5245e5ed4457749995b46d46e9769e657fcc0818e2cJakob Stoklund Olesen // Ignore the hint if we would have to spill a dirty register. 5255e5ed4457749995b46d46e9769e657fcc0818e2cJakob Stoklund Olesen unsigned Cost = calcSpillCost(Hint); 5265e5ed4457749995b46d46e9769e657fcc0818e2cJakob Stoklund Olesen if (Cost < spillDirty) { 5275e5ed4457749995b46d46e9769e657fcc0818e2cJakob Stoklund Olesen if (Cost) 5285e5ed4457749995b46d46e9769e657fcc0818e2cJakob Stoklund Olesen definePhysReg(MI, Hint, regFree); 529a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen // definePhysReg may kill virtual registers and modify LiveVirtRegs. 530a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen // That invalidates LRI, so run a new lookup for VirtReg. 531a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen return assignVirtToPhysReg(VirtReg, Hint); 5324bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen } 5334bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen } 5344bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen 53539b5c0c049a19c7a7feffc9506da07923cc136e4Jakob Stoklund Olesen ArrayRef<MCPhysReg> AO = RegClassInfo.getOrder(RC); 536548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen 537bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // First try to find a completely free register. 53839b5c0c049a19c7a7feffc9506da07923cc136e4Jakob Stoklund Olesen for (ArrayRef<MCPhysReg>::iterator I = AO.begin(), E = AO.end(); I != E; ++I){ 539bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned PhysReg = *I; 540601158a18e325879b224bd1979d824407ed98bc7Jakob Stoklund Olesen if (PhysRegState[PhysReg] == regFree && !isRegUsedInInstr(PhysReg)) { 541a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen assignVirtToPhysReg(*LRI, PhysReg); 542a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen return LRI; 543a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen } 544bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 54500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 5464314268128be6d54c9a7f0709680e5a5b40f3ab3Jakob Stoklund Olesen DEBUG(dbgs() << "Allocating " << PrintReg(VirtReg) << " from " 5474314268128be6d54c9a7f0709680e5a5b40f3ab3Jakob Stoklund Olesen << RC->getName() << "\n"); 548548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen 549548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen unsigned BestReg = 0, BestCost = spillImpossible; 55039b5c0c049a19c7a7feffc9506da07923cc136e4Jakob Stoklund Olesen for (ArrayRef<MCPhysReg>::iterator I = AO.begin(), E = AO.end(); I != E; ++I){ 551548643c573d53950e28e9e810cd0454ba9a21af0Jakob Stoklund Olesen unsigned Cost = calcSpillCost(*I); 55227ce3b96e51887995f94d8c78a6c7e79bf7cdcddJakob Stoklund Olesen DEBUG(dbgs() << "\tRegister: " << PrintReg(*I, TRI) << "\n"); 5530b756349a718e046abba84c316877a682eb0ff2fEric Christopher DEBUG(dbgs() << "\tCost: " << Cost << "\n"); 5540b756349a718e046abba84c316877a682eb0ff2fEric Christopher DEBUG(dbgs() << "\tBestCost: " << BestCost << "\n"); 555f3ea06b108d45c53dade87d6f1f48ac0a0e20562Jakob Stoklund Olesen // Cost is 0 when all aliases are already disabled. 556a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen if (Cost == 0) { 557a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen assignVirtToPhysReg(*LRI, *I); 558a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen return LRI; 559a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen } 560f3ea06b108d45c53dade87d6f1f48ac0a0e20562Jakob Stoklund Olesen if (Cost < BestCost) 561f3ea06b108d45c53dade87d6f1f48ac0a0e20562Jakob Stoklund Olesen BestReg = *I, BestCost = Cost; 56200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 56300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 564bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (BestReg) { 565f3ea06b108d45c53dade87d6f1f48ac0a0e20562Jakob Stoklund Olesen definePhysReg(MI, BestReg, regFree); 566a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen // definePhysReg may kill virtual registers and modify LiveVirtRegs. 567a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen // That invalidates LRI, so run a new lookup for VirtReg. 568a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen return assignVirtToPhysReg(VirtReg, BestReg); 569bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 57000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 5719d812a2805161665d56a78734da98b58f39ce0fcJakob Stoklund Olesen // Nothing we can do. Report an error and keep going with a bad allocation. 5729d812a2805161665d56a78734da98b58f39ce0fcJakob Stoklund Olesen MI->emitError("ran out of registers during register allocation"); 5739d812a2805161665d56a78734da98b58f39ce0fcJakob Stoklund Olesen definePhysReg(MI, *AO.begin(), regFree); 574a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen return assignVirtToPhysReg(VirtReg, *AO.begin()); 57500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 57600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 577bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen/// defineVirtReg - Allocate a register for VirtReg and mark it as dirty. 578646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund OlesenRAFast::LiveRegMap::iterator 579646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund OlesenRAFast::defineVirtReg(MachineInstr *MI, unsigned OpNum, 580646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund Olesen unsigned VirtReg, unsigned Hint) { 581bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen assert(TargetRegisterInfo::isVirtualRegister(VirtReg) && 582bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen "Not a virtual register"); 583844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen LiveRegMap::iterator LRI; 58401dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen bool New; 585a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen tie(LRI, New) = LiveVirtRegs.insert(LiveReg(VirtReg)); 5860c9e4f5f3ff139733d74462a0ad5b94014e764a8Jakob Stoklund Olesen if (New) { 5870c9e4f5f3ff139733d74462a0ad5b94014e764a8Jakob Stoklund Olesen // If there is no hint, peek at the only use of this register. 5880c9e4f5f3ff139733d74462a0ad5b94014e764a8Jakob Stoklund Olesen if ((!Hint || !TargetRegisterInfo::isPhysicalRegister(Hint)) && 5890c9e4f5f3ff139733d74462a0ad5b94014e764a8Jakob Stoklund Olesen MRI->hasOneNonDBGUse(VirtReg)) { 590273f7e42994a5bce0614d04d96dbfdf05fd652e5Jakob Stoklund Olesen const MachineInstr &UseMI = *MRI->use_nodbg_begin(VirtReg); 5910c9e4f5f3ff139733d74462a0ad5b94014e764a8Jakob Stoklund Olesen // It's a copy, use the destination register as a hint. 592273f7e42994a5bce0614d04d96dbfdf05fd652e5Jakob Stoklund Olesen if (UseMI.isCopyLike()) 593273f7e42994a5bce0614d04d96dbfdf05fd652e5Jakob Stoklund Olesen Hint = UseMI.getOperand(0).getReg(); 5940c9e4f5f3ff139733d74462a0ad5b94014e764a8Jakob Stoklund Olesen } 595a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen LRI = allocVirtReg(MI, LRI, Hint); 596a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen } else if (LRI->LastUse) { 5970eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen // Redefining a live register - kill at the last use, unless it is this 5980eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen // instruction defining VirtReg multiple times. 599a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen if (LRI->LastUse != MI || LRI->LastUse->getOperand(LRI->LastOpNum).isUse()) 600a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen addKillFlag(*LRI); 6010eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen } 602a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen assert(LRI->PhysReg && "Register not assigned"); 603a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen LRI->LastUse = MI; 604a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen LRI->LastOpNum = OpNum; 605a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen LRI->Dirty = true; 606601158a18e325879b224bd1979d824407ed98bc7Jakob Stoklund Olesen markRegUsedInInstr(LRI->PhysReg); 607646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund Olesen return LRI; 608bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen} 60900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 610bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen/// reloadVirtReg - Make sure VirtReg is available in a physreg and return it. 611646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund OlesenRAFast::LiveRegMap::iterator 612646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund OlesenRAFast::reloadVirtReg(MachineInstr *MI, unsigned OpNum, 613646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund Olesen unsigned VirtReg, unsigned Hint) { 614bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen assert(TargetRegisterInfo::isVirtualRegister(VirtReg) && 615bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen "Not a virtual register"); 616844db9cc6f1a9458b60b8debeef3132f555dcd8fJakob Stoklund Olesen LiveRegMap::iterator LRI; 61701dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen bool New; 618a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen tie(LRI, New) = LiveVirtRegs.insert(LiveReg(VirtReg)); 619ac3e529831877cea609ed668f95b1dc06e34698cJakob Stoklund Olesen MachineOperand &MO = MI->getOperand(OpNum); 62001dcbf850732790fe7d5b5ed23426d535b07f316Jakob Stoklund Olesen if (New) { 621a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen LRI = allocVirtReg(MI, LRI, Hint); 6224bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen const TargetRegisterClass *RC = MRI->getRegClass(VirtReg); 623bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen int FrameIndex = getStackSpaceFor(VirtReg, RC); 6244314268128be6d54c9a7f0709680e5a5b40f3ab3Jakob Stoklund Olesen DEBUG(dbgs() << "Reloading " << PrintReg(VirtReg, TRI) << " into " 625a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen << PrintReg(LRI->PhysReg, TRI) << "\n"); 626a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen TII->loadRegFromStackSlot(*MBB, MI, LRI->PhysReg, FrameIndex, RC, TRI); 627bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen ++NumLoads; 628a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen } else if (LRI->Dirty) { 6291e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen if (isLastUseOfLocalReg(MO)) { 6301e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen DEBUG(dbgs() << "Killing last use: " << MO << "\n"); 631d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen if (MO.isUse()) 632d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen MO.setIsKill(); 633d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen else 634d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen MO.setIsDead(); 6351e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen } else if (MO.isKill()) { 6361e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen DEBUG(dbgs() << "Clearing dubious kill: " << MO << "\n"); 6371e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen MO.setIsKill(false); 638d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen } else if (MO.isDead()) { 639d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen DEBUG(dbgs() << "Clearing dubious dead: " << MO << "\n"); 640d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen MO.setIsDead(false); 6411e03ff42433afe3a9ffad2765b537f10db3aa921Jakob Stoklund Olesen } 642ac3e529831877cea609ed668f95b1dc06e34698cJakob Stoklund Olesen } else if (MO.isKill()) { 643ac3e529831877cea609ed668f95b1dc06e34698cJakob Stoklund Olesen // We must remove kill flags from uses of reloaded registers because the 644ac3e529831877cea609ed668f95b1dc06e34698cJakob Stoklund Olesen // register would be killed immediately, and there might be a second use: 645ac3e529831877cea609ed668f95b1dc06e34698cJakob Stoklund Olesen // %foo = OR %x<kill>, %x 646ac3e529831877cea609ed668f95b1dc06e34698cJakob Stoklund Olesen // This would cause a second reload of %x into a different register. 647ac3e529831877cea609ed668f95b1dc06e34698cJakob Stoklund Olesen DEBUG(dbgs() << "Clearing clean kill: " << MO << "\n"); 648ac3e529831877cea609ed668f95b1dc06e34698cJakob Stoklund Olesen MO.setIsKill(false); 649d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen } else if (MO.isDead()) { 650d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen DEBUG(dbgs() << "Clearing clean dead: " << MO << "\n"); 651d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen MO.setIsDead(false); 65200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 653a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen assert(LRI->PhysReg && "Register not assigned"); 654a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen LRI->LastUse = MI; 655a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen LRI->LastOpNum = OpNum; 656601158a18e325879b224bd1979d824407ed98bc7Jakob Stoklund Olesen markRegUsedInInstr(LRI->PhysReg); 657646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund Olesen return LRI; 658bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen} 65900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 6600eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen// setPhysReg - Change operand OpNum in MI the refer the PhysReg, considering 6610eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen// subregs. This may invalidate any operand pointers. 6620eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen// Return true if the operand kills its register. 6630eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesenbool RAFast::setPhysReg(MachineInstr *MI, unsigned OpNum, unsigned PhysReg) { 6640eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen MachineOperand &MO = MI->getOperand(OpNum); 6656565a709702995fa8a5e659269d6cda134383be7Jakob Stoklund Olesen bool Dead = MO.isDead(); 66641e1401de5cb8752fb9d06e65e62bfe97cc1304eJakob Stoklund Olesen if (!MO.getSubReg()) { 667bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen MO.setReg(PhysReg); 6686565a709702995fa8a5e659269d6cda134383be7Jakob Stoklund Olesen return MO.isKill() || Dead; 66941e1401de5cb8752fb9d06e65e62bfe97cc1304eJakob Stoklund Olesen } 67041e1401de5cb8752fb9d06e65e62bfe97cc1304eJakob Stoklund Olesen 67141e1401de5cb8752fb9d06e65e62bfe97cc1304eJakob Stoklund Olesen // Handle subregister index. 67241e1401de5cb8752fb9d06e65e62bfe97cc1304eJakob Stoklund Olesen MO.setReg(PhysReg ? TRI->getSubReg(PhysReg, MO.getSubReg()) : 0); 67341e1401de5cb8752fb9d06e65e62bfe97cc1304eJakob Stoklund Olesen MO.setSubReg(0); 674d32e735ae6e3fbebcae9a23d7cda091770bb3a14Jakob Stoklund Olesen 675d32e735ae6e3fbebcae9a23d7cda091770bb3a14Jakob Stoklund Olesen // A kill flag implies killing the full register. Add corresponding super 676d32e735ae6e3fbebcae9a23d7cda091770bb3a14Jakob Stoklund Olesen // register kill. 677d32e735ae6e3fbebcae9a23d7cda091770bb3a14Jakob Stoklund Olesen if (MO.isKill()) { 678d32e735ae6e3fbebcae9a23d7cda091770bb3a14Jakob Stoklund Olesen MI->addRegisterKilled(PhysReg, TRI, true); 67941e1401de5cb8752fb9d06e65e62bfe97cc1304eJakob Stoklund Olesen return true; 68041e1401de5cb8752fb9d06e65e62bfe97cc1304eJakob Stoklund Olesen } 6814d10829e1296b7aea0455e000fc318b147182c1cJakob Stoklund Olesen 6824d10829e1296b7aea0455e000fc318b147182c1cJakob Stoklund Olesen // A <def,read-undef> of a sub-register requires an implicit def of the full 6834d10829e1296b7aea0455e000fc318b147182c1cJakob Stoklund Olesen // register. 6844d10829e1296b7aea0455e000fc318b147182c1cJakob Stoklund Olesen if (MO.isDef() && MO.isUndef()) 6854d10829e1296b7aea0455e000fc318b147182c1cJakob Stoklund Olesen MI->addRegisterDefined(PhysReg, TRI); 6864d10829e1296b7aea0455e000fc318b147182c1cJakob Stoklund Olesen 6876565a709702995fa8a5e659269d6cda134383be7Jakob Stoklund Olesen return Dead; 68800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 68900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 690d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen// Handle special instruction operand like early clobbers and tied ops when 691d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen// there are additional physreg defines. 692d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesenvoid RAFast::handleThroughOperands(MachineInstr *MI, 693d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen SmallVectorImpl<unsigned> &VirtDead) { 694d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen DEBUG(dbgs() << "Scanning for through registers:"); 695d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen SmallSet<unsigned, 8> ThroughRegs; 696d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 697d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen MachineOperand &MO = MI->getOperand(i); 698d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen if (!MO.isReg()) continue; 699d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen unsigned Reg = MO.getReg(); 700c9df025e33ac435adb3b3318d237c36ca7cec659Jakob Stoklund Olesen if (!TargetRegisterInfo::isVirtualRegister(Reg)) 701c9df025e33ac435adb3b3318d237c36ca7cec659Jakob Stoklund Olesen continue; 702d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen if (MO.isEarlyClobber() || MI->isRegTiedToDefOperand(i) || 703d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen (MO.getSubReg() && MI->readsVirtualRegister(Reg))) { 704d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen if (ThroughRegs.insert(Reg)) 7054314268128be6d54c9a7f0709680e5a5b40f3ab3Jakob Stoklund Olesen DEBUG(dbgs() << ' ' << PrintReg(Reg)); 706d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen } 707d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen } 708d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen 709d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen // If any physreg defines collide with preallocated through registers, 710d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen // we must spill and reallocate. 711d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen DEBUG(dbgs() << "\nChecking for physdef collisions.\n"); 712d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 713d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen MachineOperand &MO = MI->getOperand(i); 714d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen if (!MO.isReg() || !MO.isDef()) continue; 715d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen unsigned Reg = MO.getReg(); 716d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen if (!Reg || !TargetRegisterInfo::isPhysicalRegister(Reg)) continue; 717601158a18e325879b224bd1979d824407ed98bc7Jakob Stoklund Olesen markRegUsedInInstr(Reg); 7188c70ea47fae6d61441d150cbe9431cf5e06222e5Jakob Stoklund Olesen for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) { 7198c70ea47fae6d61441d150cbe9431cf5e06222e5Jakob Stoklund Olesen if (ThroughRegs.count(PhysRegState[*AI])) 7208c70ea47fae6d61441d150cbe9431cf5e06222e5Jakob Stoklund Olesen definePhysReg(MI, *AI, regFree); 721d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen } 722d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen } 723d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen 724d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen SmallVector<unsigned, 8> PartialDefs; 725254a13282c97469973b4fa8cc0e110ed6160642cRafael Espindola DEBUG(dbgs() << "Allocating tied uses.\n"); 726d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 727d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen MachineOperand &MO = MI->getOperand(i); 728d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen if (!MO.isReg()) continue; 729d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen unsigned Reg = MO.getReg(); 730c9df025e33ac435adb3b3318d237c36ca7cec659Jakob Stoklund Olesen if (!TargetRegisterInfo::isVirtualRegister(Reg)) continue; 731d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen if (MO.isUse()) { 732d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen unsigned DefIdx = 0; 733d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen if (!MI->isRegTiedToDefOperand(i, &DefIdx)) continue; 734d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen DEBUG(dbgs() << "Operand " << i << "("<< MO << ") is tied to operand " 735d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen << DefIdx << ".\n"); 736d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen LiveRegMap::iterator LRI = reloadVirtReg(MI, i, Reg, 0); 737a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen unsigned PhysReg = LRI->PhysReg; 738d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen setPhysReg(MI, i, PhysReg); 739d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen // Note: we don't update the def operand yet. That would cause the normal 740d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen // def-scan to attempt spilling. 741d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen } else if (MO.getSubReg() && MI->readsVirtualRegister(Reg)) { 742d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen DEBUG(dbgs() << "Partial redefine: " << MO << "\n"); 743d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen // Reload the register, but don't assign to the operand just yet. 744d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen // That would confuse the later phys-def processing pass. 745d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen LiveRegMap::iterator LRI = reloadVirtReg(MI, i, Reg, 0); 746a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen PartialDefs.push_back(LRI->PhysReg); 747d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen } 748d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen } 749d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen 750254a13282c97469973b4fa8cc0e110ed6160642cRafael Espindola DEBUG(dbgs() << "Allocating early clobbers.\n"); 751254a13282c97469973b4fa8cc0e110ed6160642cRafael Espindola for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 752254a13282c97469973b4fa8cc0e110ed6160642cRafael Espindola MachineOperand &MO = MI->getOperand(i); 753254a13282c97469973b4fa8cc0e110ed6160642cRafael Espindola if (!MO.isReg()) continue; 754254a13282c97469973b4fa8cc0e110ed6160642cRafael Espindola unsigned Reg = MO.getReg(); 755254a13282c97469973b4fa8cc0e110ed6160642cRafael Espindola if (!TargetRegisterInfo::isVirtualRegister(Reg)) continue; 756254a13282c97469973b4fa8cc0e110ed6160642cRafael Espindola if (!MO.isEarlyClobber()) 757254a13282c97469973b4fa8cc0e110ed6160642cRafael Espindola continue; 758254a13282c97469973b4fa8cc0e110ed6160642cRafael Espindola // Note: defineVirtReg may invalidate MO. 759254a13282c97469973b4fa8cc0e110ed6160642cRafael Espindola LiveRegMap::iterator LRI = defineVirtReg(MI, i, Reg, 0); 760a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen unsigned PhysReg = LRI->PhysReg; 761254a13282c97469973b4fa8cc0e110ed6160642cRafael Espindola if (setPhysReg(MI, i, PhysReg)) 762254a13282c97469973b4fa8cc0e110ed6160642cRafael Espindola VirtDead.push_back(Reg); 763254a13282c97469973b4fa8cc0e110ed6160642cRafael Espindola } 764254a13282c97469973b4fa8cc0e110ed6160642cRafael Espindola 765d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen // Restore UsedInInstr to a state usable for allocating normal virtual uses. 766d7ea7d5cd7518788dea698d38023959480c8263aJakob Stoklund Olesen UsedInInstr.clear(); 767d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 768d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen MachineOperand &MO = MI->getOperand(i); 769d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen if (!MO.isReg() || (MO.isDef() && !MO.isEarlyClobber())) continue; 770d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen unsigned Reg = MO.getReg(); 771d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen if (!Reg || !TargetRegisterInfo::isPhysicalRegister(Reg)) continue; 77227ce3b96e51887995f94d8c78a6c7e79bf7cdcddJakob Stoklund Olesen DEBUG(dbgs() << "\tSetting " << PrintReg(Reg, TRI) 77327ce3b96e51887995f94d8c78a6c7e79bf7cdcddJakob Stoklund Olesen << " as used in instr\n"); 774601158a18e325879b224bd1979d824407ed98bc7Jakob Stoklund Olesen markRegUsedInInstr(Reg); 775d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen } 776d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen 777d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen // Also mark PartialDefs as used to avoid reallocation. 778d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen for (unsigned i = 0, e = PartialDefs.size(); i != e; ++i) 779601158a18e325879b224bd1979d824407ed98bc7Jakob Stoklund Olesen markRegUsedInInstr(PartialDefs[i]); 780d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen} 781d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen 782b3d58474c83499621ae1e2d76dc87587910abe55Andrew Trickvoid RAFast::AllocateBasicBlock() { 783b3d58474c83499621ae1e2d76dc87587910abe55Andrew Trick DEBUG(dbgs() << "\nAllocating " << *MBB); 784c57ef561423f1ac7f2db5b1840d5681f18a4c0c8Nick Lewycky 785bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen PhysRegState.assign(TRI->getNumRegs(), regDisabled); 786a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen assert(LiveVirtRegs.empty() && "Mapping not cleared from last block?"); 78700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 7886fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen MachineBasicBlock::iterator MII = MBB->begin(); 789bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen 790bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Add live-in registers as live. 7916fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen for (MachineBasicBlock::livein_iterator I = MBB->livein_begin(), 7926fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen E = MBB->livein_end(); I != E; ++I) 79314d1dd95c7c969e07defebb6fe65df2fae1b30cfJakob Stoklund Olesen if (MRI->isAllocatable(*I)) 7949d4b51b696e27b9c061955d4c76f9dbff529b143Jakob Stoklund Olesen definePhysReg(MII, *I, regReserved); 795bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen 796d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen SmallVector<unsigned, 8> VirtDead; 7977ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen SmallVector<MachineInstr*, 32> Coalesced; 79800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 79900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen // Otherwise, sequentially allocate each instruction in the MBB. 8006fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen while (MII != MBB->end()) { 80100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen MachineInstr *MI = MII++; 802e837dead3c8dc3445ef6a0e2322179c57e264a13Evan Cheng const MCInstrDesc &MCID = MI->getDesc(); 80300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen DEBUG({ 804c9c4dacd03a4b80d61ed6b9c6ffeb1b1f76b8d1cJakob Stoklund Olesen dbgs() << "\n>> " << *MI << "Regs:"; 805bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen for (unsigned Reg = 1, E = TRI->getNumRegs(); Reg != E; ++Reg) { 806bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (PhysRegState[Reg] == regDisabled) continue; 807bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen dbgs() << " " << TRI->getName(Reg); 808bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen switch(PhysRegState[Reg]) { 809bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regFree: 810bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 811bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regReserved: 812c9c4dacd03a4b80d61ed6b9c6ffeb1b1f76b8d1cJakob Stoklund Olesen dbgs() << "*"; 813bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 814a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen default: { 8154314268128be6d54c9a7f0709680e5a5b40f3ab3Jakob Stoklund Olesen dbgs() << '=' << PrintReg(PhysRegState[Reg]); 816a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen LiveRegMap::iterator I = findLiveVirtReg(PhysRegState[Reg]); 817a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen assert(I != LiveVirtRegs.end() && "Missing VirtReg entry"); 818a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen if (I->Dirty) 819bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen dbgs() << "*"; 820a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen assert(I->PhysReg == Reg && "Bad inverse map"); 821bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 822bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 823a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen } 824bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 82500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen dbgs() << '\n'; 82676b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen // Check that LiveVirtRegs is the inverse. 82776b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen for (LiveRegMap::iterator i = LiveVirtRegs.begin(), 82876b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen e = LiveVirtRegs.end(); i != e; ++i) { 829a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen assert(TargetRegisterInfo::isVirtualRegister(i->VirtReg) && 830bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen "Bad map key"); 831a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen assert(TargetRegisterInfo::isPhysicalRegister(i->PhysReg) && 832bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen "Bad map value"); 833a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen assert(PhysRegState[i->PhysReg] == i->VirtReg && "Bad inverse map"); 834bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 83500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen }); 83600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 837bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Debug values are not allowed to change codegen in any way. 838bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (MI->isDebugValue()) { 83958b8176ed39038240984c0966fef847fe37c86c1Devang Patel bool ScanDbgValue = true; 84058b8176ed39038240984c0966fef847fe37c86c1Devang Patel while (ScanDbgValue) { 84158b8176ed39038240984c0966fef847fe37c86c1Devang Patel ScanDbgValue = false; 84258b8176ed39038240984c0966fef847fe37c86c1Devang Patel for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 84358b8176ed39038240984c0966fef847fe37c86c1Devang Patel MachineOperand &MO = MI->getOperand(i); 84458b8176ed39038240984c0966fef847fe37c86c1Devang Patel if (!MO.isReg()) continue; 84558b8176ed39038240984c0966fef847fe37c86c1Devang Patel unsigned Reg = MO.getReg(); 846c9df025e33ac435adb3b3318d237c36ca7cec659Jakob Stoklund Olesen if (!TargetRegisterInfo::isVirtualRegister(Reg)) continue; 847a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen LiveRegMap::iterator LRI = findLiveVirtReg(Reg); 84858b8176ed39038240984c0966fef847fe37c86c1Devang Patel if (LRI != LiveVirtRegs.end()) 849a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen setPhysReg(MI, i, LRI->PhysReg); 8507a029b6d7e58cb0f1010f14d99d7661e387cfb54Devang Patel else { 85158b8176ed39038240984c0966fef847fe37c86c1Devang Patel int SS = StackSlotForVirtReg[Reg]; 8524bafda9618f9dfa9edc8da08bb3001ef2d1a9b68Devang Patel if (SS == -1) { 85307cb689d6260b78861d829bb05b188e1558c528eJim Grosbach // We can't allocate a physreg for a DebugValue, sorry! 8544bafda9618f9dfa9edc8da08bb3001ef2d1a9b68Devang Patel DEBUG(dbgs() << "Unable to allocate vreg used by DBG_VALUE"); 85507cb689d6260b78861d829bb05b188e1558c528eJim Grosbach MO.setReg(0); 8564bafda9618f9dfa9edc8da08bb3001ef2d1a9b68Devang Patel } 85758b8176ed39038240984c0966fef847fe37c86c1Devang Patel else { 85858b8176ed39038240984c0966fef847fe37c86c1Devang Patel // Modify DBG_VALUE now that the value is in a spill slot. 85943ae5e85f829df883dd364c0b9612bbe90f3ad97Adrian Prantl bool IsIndirect = MI->getOperand(1).isImm(); 86043ae5e85f829df883dd364c0b9612bbe90f3ad97Adrian Prantl uint64_t Offset = IsIndirect ? MI->getOperand(1).getImm() : 0; 86107cb689d6260b78861d829bb05b188e1558c528eJim Grosbach const MDNode *MDPtr = 86258b8176ed39038240984c0966fef847fe37c86c1Devang Patel MI->getOperand(MI->getNumOperands()-1).getMetadata(); 86358b8176ed39038240984c0966fef847fe37c86c1Devang Patel DebugLoc DL = MI->getDebugLoc(); 8646d9dbd5526e3161db884fc4fe99c278bb59ccc19David Blaikie MachineBasicBlock *MBB = MI->getParent(); 8656d9dbd5526e3161db884fc4fe99c278bb59ccc19David Blaikie MachineInstr *NewDV = BuildMI(*MBB, MBB->erase(MI), DL, 8666d9dbd5526e3161db884fc4fe99c278bb59ccc19David Blaikie TII->get(TargetOpcode::DBG_VALUE)) 8676d9dbd5526e3161db884fc4fe99c278bb59ccc19David Blaikie .addFrameIndex(SS).addImm(Offset).addMetadata(MDPtr); 8686d9dbd5526e3161db884fc4fe99c278bb59ccc19David Blaikie DEBUG(dbgs() << "Modifying debug info due to spill:" 8696d9dbd5526e3161db884fc4fe99c278bb59ccc19David Blaikie << "\t" << *NewDV); 8706d9dbd5526e3161db884fc4fe99c278bb59ccc19David Blaikie // Scan NewDV operands from the beginning. 8716d9dbd5526e3161db884fc4fe99c278bb59ccc19David Blaikie MI = NewDV; 8726d9dbd5526e3161db884fc4fe99c278bb59ccc19David Blaikie ScanDbgValue = true; 8736d9dbd5526e3161db884fc4fe99c278bb59ccc19David Blaikie break; 87458b8176ed39038240984c0966fef847fe37c86c1Devang Patel } 8757a029b6d7e58cb0f1010f14d99d7661e387cfb54Devang Patel } 876d2df64f56970aa07d2d8733543e4baf6c7009e91Devang Patel LiveDbgValueMap[Reg].push_back(MI); 8777a029b6d7e58cb0f1010f14d99d7661e387cfb54Devang Patel } 87800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 879bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Next instruction. 880bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen continue; 88100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 88200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 8834bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen // If this is a copy, we may be able to coalesce. 88404c528a0c86ddf3d6a70681f72e1b2ec07b0b53aJakob Stoklund Olesen unsigned CopySrc = 0, CopyDst = 0, CopySrcSub = 0, CopyDstSub = 0; 885273f7e42994a5bce0614d04d96dbfdf05fd652e5Jakob Stoklund Olesen if (MI->isCopy()) { 886273f7e42994a5bce0614d04d96dbfdf05fd652e5Jakob Stoklund Olesen CopyDst = MI->getOperand(0).getReg(); 887273f7e42994a5bce0614d04d96dbfdf05fd652e5Jakob Stoklund Olesen CopySrc = MI->getOperand(1).getReg(); 888273f7e42994a5bce0614d04d96dbfdf05fd652e5Jakob Stoklund Olesen CopyDstSub = MI->getOperand(0).getSubReg(); 889273f7e42994a5bce0614d04d96dbfdf05fd652e5Jakob Stoklund Olesen CopySrcSub = MI->getOperand(1).getSubReg(); 89004c528a0c86ddf3d6a70681f72e1b2ec07b0b53aJakob Stoklund Olesen } 8914bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen 892bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Track registers used by instruction. 893d7ea7d5cd7518788dea698d38023959480c8263aJakob Stoklund Olesen UsedInInstr.clear(); 89400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 895bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // First scan. 896bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Mark physreg uses and early clobbers as used. 897e97dda4fc58ee401ebb4aa9153d10f8ce8ba9a70Jakob Stoklund Olesen // Find the end of the virtreg operands 898e97dda4fc58ee401ebb4aa9153d10f8ce8ba9a70Jakob Stoklund Olesen unsigned VirtOpEnd = 0; 899d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen bool hasTiedOps = false; 900d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen bool hasEarlyClobbers = false; 901d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen bool hasPartialRedefs = false; 902d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen bool hasPhysDefs = false; 903bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 90400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen MachineOperand &MO = MI->getOperand(i); 9057979b24e5cd4a99db6af3fcd66d9f514f02d11dbChad Rosier // Make sure MRI knows about registers clobbered by regmasks. 9067979b24e5cd4a99db6af3fcd66d9f514f02d11dbChad Rosier if (MO.isRegMask()) { 9077979b24e5cd4a99db6af3fcd66d9f514f02d11dbChad Rosier MRI->addPhysRegsUsedFromRegMask(MO.getRegMask()); 9087979b24e5cd4a99db6af3fcd66d9f514f02d11dbChad Rosier continue; 9097979b24e5cd4a99db6af3fcd66d9f514f02d11dbChad Rosier } 910bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (!MO.isReg()) continue; 911bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned Reg = MO.getReg(); 912e97dda4fc58ee401ebb4aa9153d10f8ce8ba9a70Jakob Stoklund Olesen if (!Reg) continue; 913e97dda4fc58ee401ebb4aa9153d10f8ce8ba9a70Jakob Stoklund Olesen if (TargetRegisterInfo::isVirtualRegister(Reg)) { 914e97dda4fc58ee401ebb4aa9153d10f8ce8ba9a70Jakob Stoklund Olesen VirtOpEnd = i+1; 915d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen if (MO.isUse()) { 916d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen hasTiedOps = hasTiedOps || 917e837dead3c8dc3445ef6a0e2322179c57e264a13Evan Cheng MCID.getOperandConstraint(i, MCOI::TIED_TO) != -1; 918d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen } else { 919d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen if (MO.isEarlyClobber()) 920d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen hasEarlyClobbers = true; 921d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen if (MO.getSubReg() && MI->readsVirtualRegister(Reg)) 922d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen hasPartialRedefs = true; 923d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen } 924e97dda4fc58ee401ebb4aa9153d10f8ce8ba9a70Jakob Stoklund Olesen continue; 925e97dda4fc58ee401ebb4aa9153d10f8ce8ba9a70Jakob Stoklund Olesen } 92614d1dd95c7c969e07defebb6fe65df2fae1b30cfJakob Stoklund Olesen if (!MRI->isAllocatable(Reg)) continue; 927bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (MO.isUse()) { 9284ed10826833701b14064f55b6514289e0a7ff5efJakob Stoklund Olesen usePhysReg(MO); 929bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } else if (MO.isEarlyClobber()) { 93075ac4d9c2dfb22f84da25dec03df7a07f3dad1faJakob Stoklund Olesen definePhysReg(MI, Reg, (MO.isImplicit() || MO.isDead()) ? 93175ac4d9c2dfb22f84da25dec03df7a07f3dad1faJakob Stoklund Olesen regFree : regReserved); 932d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen hasEarlyClobbers = true; 933d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen } else 934d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen hasPhysDefs = true; 935d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen } 936d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen 937d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen // The instruction may have virtual register operands that must be allocated 938d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen // the same register at use-time and def-time: early clobbers and tied 939d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen // operands. If there are also physical defs, these registers must avoid 940d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen // both physical defs and uses, making them more constrained than normal 941d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen // operands. 94207cb689d6260b78861d829bb05b188e1558c528eJim Grosbach // Similarly, if there are multiple defs and tied operands, we must make 94307cb689d6260b78861d829bb05b188e1558c528eJim Grosbach // sure the same register is allocated to uses and defs. 944d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen // We didn't detect inline asm tied operands above, so just make this extra 945d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen // pass for all inline asm. 946d1303d2a66241c70e0e35dac371636c883235df8Jakob Stoklund Olesen if (MI->isInlineAsm() || hasEarlyClobbers || hasPartialRedefs || 947e837dead3c8dc3445ef6a0e2322179c57e264a13Evan Cheng (hasTiedOps && (hasPhysDefs || MCID.getNumDefs() > 1))) { 948d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen handleThroughOperands(MI, VirtDead); 949d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen // Don't attempt coalescing when we have funny stuff going on. 950d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen CopyDst = 0; 9514bd94f7bbe2ed6e0d83d03b06c0d20bb346abecaJakob Stoklund Olesen // Pretend we have early clobbers so the use operands get marked below. 9524bd94f7bbe2ed6e0d83d03b06c0d20bb346abecaJakob Stoklund Olesen // This is not necessary for the common case of a single tied use. 9534bd94f7bbe2ed6e0d83d03b06c0d20bb346abecaJakob Stoklund Olesen hasEarlyClobbers = true; 95400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 95500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 956bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Second scan. 957d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen // Allocate virtreg uses. 958e97dda4fc58ee401ebb4aa9153d10f8ce8ba9a70Jakob Stoklund Olesen for (unsigned i = 0; i != VirtOpEnd; ++i) { 95900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen MachineOperand &MO = MI->getOperand(i); 960bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (!MO.isReg()) continue; 96100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen unsigned Reg = MO.getReg(); 962c9df025e33ac435adb3b3318d237c36ca7cec659Jakob Stoklund Olesen if (!TargetRegisterInfo::isVirtualRegister(Reg)) continue; 963bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (MO.isUse()) { 964646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund Olesen LiveRegMap::iterator LRI = reloadVirtReg(MI, i, Reg, CopyDst); 965a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen unsigned PhysReg = LRI->PhysReg; 9667ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen CopySrc = (CopySrc == Reg || CopySrc == PhysReg) ? PhysReg : 0; 9670eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen if (setPhysReg(MI, i, PhysReg)) 968646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund Olesen killVirtReg(LRI); 96900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 97000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 97100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 972d7ea7d5cd7518788dea698d38023959480c8263aJakob Stoklund Olesen for (UsedInInstrSet::iterator 973d7ea7d5cd7518788dea698d38023959480c8263aJakob Stoklund Olesen I = UsedInInstr.begin(), E = UsedInInstr.end(); I != E; ++I) 974601158a18e325879b224bd1979d824407ed98bc7Jakob Stoklund Olesen MRI->setRegUnitUsed(*I); 97582b07dc4995d48065bd95affff4d8513a5cad4f2Jakob Stoklund Olesen 9764bd94f7bbe2ed6e0d83d03b06c0d20bb346abecaJakob Stoklund Olesen // Track registers defined by instruction - early clobbers and tied uses at 9774bd94f7bbe2ed6e0d83d03b06c0d20bb346abecaJakob Stoklund Olesen // this point. 978d7ea7d5cd7518788dea698d38023959480c8263aJakob Stoklund Olesen UsedInInstr.clear(); 979d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen if (hasEarlyClobbers) { 980d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 981d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen MachineOperand &MO = MI->getOperand(i); 9824bd94f7bbe2ed6e0d83d03b06c0d20bb346abecaJakob Stoklund Olesen if (!MO.isReg()) continue; 983d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen unsigned Reg = MO.getReg(); 984d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen if (!Reg || !TargetRegisterInfo::isPhysicalRegister(Reg)) continue; 9854bd94f7bbe2ed6e0d83d03b06c0d20bb346abecaJakob Stoklund Olesen // Look for physreg defs and tied uses. 9864bd94f7bbe2ed6e0d83d03b06c0d20bb346abecaJakob Stoklund Olesen if (!MO.isDef() && !MI->isRegTiedToDefOperand(i)) continue; 987601158a18e325879b224bd1979d824407ed98bc7Jakob Stoklund Olesen markRegUsedInInstr(Reg); 988d843b3925fdc275b262ddc2ff8fabc8c98f9a5a0Jakob Stoklund Olesen } 98900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 99000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 9914b6bbe885d851b1cfba2be9b5efc6365a2b7828aJakob Stoklund Olesen unsigned DefOpEnd = MI->getNumOperands(); 9925a96b3dad2f634c9081c8b2b6c2575441dc5a2bdEvan Cheng if (MI->isCall()) { 9934b6bbe885d851b1cfba2be9b5efc6365a2b7828aJakob Stoklund Olesen // Spill all virtregs before a call. This serves two purposes: 1. If an 99407cb689d6260b78861d829bb05b188e1558c528eJim Grosbach // exception is thrown, the landing pad is going to expect to find 99507cb689d6260b78861d829bb05b188e1558c528eJim Grosbach // registers in their spill slots, and 2. we don't have to wade through 99607cb689d6260b78861d829bb05b188e1558c528eJim Grosbach // all the <imp-def> operands on the call instruction. 9974b6bbe885d851b1cfba2be9b5efc6365a2b7828aJakob Stoklund Olesen DefOpEnd = VirtOpEnd; 9984b6bbe885d851b1cfba2be9b5efc6365a2b7828aJakob Stoklund Olesen DEBUG(dbgs() << " Spilling remaining registers before call.\n"); 9994b6bbe885d851b1cfba2be9b5efc6365a2b7828aJakob Stoklund Olesen spillAll(MI); 10006de07178e1e6445080bf4f7704e274c5f219ff70Jakob Stoklund Olesen 10016de07178e1e6445080bf4f7704e274c5f219ff70Jakob Stoklund Olesen // The imp-defs are skipped below, but we still need to mark those 10026de07178e1e6445080bf4f7704e274c5f219ff70Jakob Stoklund Olesen // registers as used by the function. 1003e837dead3c8dc3445ef6a0e2322179c57e264a13Evan Cheng SkippedInstrs.insert(&MCID); 10044b6bbe885d851b1cfba2be9b5efc6365a2b7828aJakob Stoklund Olesen } 10054b6bbe885d851b1cfba2be9b5efc6365a2b7828aJakob Stoklund Olesen 1006bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Third scan. 1007bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Allocate defs and collect dead defs. 10084b6bbe885d851b1cfba2be9b5efc6365a2b7828aJakob Stoklund Olesen for (unsigned i = 0; i != DefOpEnd; ++i) { 100900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen MachineOperand &MO = MI->getOperand(i); 101075ac4d9c2dfb22f84da25dec03df7a07f3dad1faJakob Stoklund Olesen if (!MO.isReg() || !MO.isDef() || !MO.getReg() || MO.isEarlyClobber()) 101175ac4d9c2dfb22f84da25dec03df7a07f3dad1faJakob Stoklund Olesen continue; 1012bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned Reg = MO.getReg(); 101300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 1014bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (TargetRegisterInfo::isPhysicalRegister(Reg)) { 101514d1dd95c7c969e07defebb6fe65df2fae1b30cfJakob Stoklund Olesen if (!MRI->isAllocatable(Reg)) continue; 10166fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen definePhysReg(MI, Reg, (MO.isImplicit() || MO.isDead()) ? 10176fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen regFree : regReserved); 1018bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen continue; 101900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 1020646dd7c899ea213301e193a25536a4bceebf7937Jakob Stoklund Olesen LiveRegMap::iterator LRI = defineVirtReg(MI, i, Reg, CopySrc); 1021a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen unsigned PhysReg = LRI->PhysReg; 10220eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen if (setPhysReg(MI, i, PhysReg)) { 10230eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen VirtDead.push_back(Reg); 10247ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen CopyDst = 0; // cancel coalescing; 10257ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen } else 10267ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen CopyDst = (CopyDst == Reg || CopyDst == PhysReg) ? PhysReg : 0; 102700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 102800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 10290eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen // Kill dead defs after the scan to ensure that multiple defs of the same 10300eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen // register are allocated identically. We didn't need to do this for uses 10310eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen // because we are crerating our own kill flags, and they are always at the 10320eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen // last use. 10330eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen for (unsigned i = 0, e = VirtDead.size(); i != e; ++i) 10340eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen killVirtReg(VirtDead[i]); 10350eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen VirtDead.clear(); 10360eeb05c969c6c314ca7991a10627451762787e2dJakob Stoklund Olesen 1037d7ea7d5cd7518788dea698d38023959480c8263aJakob Stoklund Olesen for (UsedInInstrSet::iterator 1038d7ea7d5cd7518788dea698d38023959480c8263aJakob Stoklund Olesen I = UsedInInstr.begin(), E = UsedInInstr.end(); I != E; ++I) 1039601158a18e325879b224bd1979d824407ed98bc7Jakob Stoklund Olesen MRI->setRegUnitUsed(*I); 1040c9c4dacd03a4b80d61ed6b9c6ffeb1b1f76b8d1cJakob Stoklund Olesen 10417ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen if (CopyDst && CopyDst == CopySrc && CopyDstSub == CopySrcSub) { 10427ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen DEBUG(dbgs() << "-- coalescing: " << *MI); 10437ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen Coalesced.push_back(MI); 10447ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen } else { 10457ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen DEBUG(dbgs() << "<< " << *MI); 10467ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen } 104700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 104800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 1049bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Spill all physical registers holding virtual registers now. 1050e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen DEBUG(dbgs() << "Spilling live registers at end of block.\n"); 1051e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen spillAll(MBB->getFirstTerminator()); 105200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 10537ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen // Erase all the coalesced copies. We are delaying it until now because 1054e6aba837974f7d2539efad9a09fe06b4d1566e5dJakob Stoklund Olesen // LiveVirtRegs might refer to the instrs. 10557ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen for (unsigned i = 0, e = Coalesced.size(); i != e; ++i) 10566fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen MBB->erase(Coalesced[i]); 10578a65c510a4fa1245d101da6318618d025702028cJakob Stoklund Olesen NumCopies += Coalesced.size(); 10587ff82e1501c416552125f77a62edebe576e469b0Jakob Stoklund Olesen 10596fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen DEBUG(MBB->dump()); 106000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 106100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 106200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen/// runOnMachineFunction - Register allocate the whole function 106300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen/// 106400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesenbool RAFast::runOnMachineFunction(MachineFunction &Fn) { 1065c9c4dacd03a4b80d61ed6b9c6ffeb1b1f76b8d1cJakob Stoklund Olesen DEBUG(dbgs() << "********** FAST REGISTER ALLOCATION **********\n" 1066986d76d7b3844b9a2f3d01a48975952749267a93David Blaikie << "********** Function: " << Fn.getName() << '\n'); 106700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen MF = &Fn; 10684bf4bafcced902ee6d58a90486768f08a3795d02Jakob Stoklund Olesen MRI = &MF->getRegInfo(); 106900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen TM = &Fn.getTarget(); 107000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen TRI = TM->getRegisterInfo(); 107100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen TII = TM->getInstrInfo(); 107218bb0545ff79b85ef424e95e2170e3a06f11b735Chad Rosier MRI->freezeReservedRegs(Fn); 10735d20c3152bd7fe91eda1b58a5eb6da7067874c61Jakob Stoklund Olesen RegClassInfo.runOnMachineFunction(Fn); 1074d7ea7d5cd7518788dea698d38023959480c8263aJakob Stoklund Olesen UsedInInstr.clear(); 1075601158a18e325879b224bd1979d824407ed98bc7Jakob Stoklund Olesen UsedInInstr.setUniverse(TRI->getNumRegUnits()); 107600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 10778dd26253f54247e77e5accfdd70e7b4bf27b39c2Andrew Trick assert(!MRI->isSSA() && "regalloc requires leaving SSA"); 10788dd26253f54247e77e5accfdd70e7b4bf27b39c2Andrew Trick 107900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen // initialize the virtual->physical register map to have a 'null' 108000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen // mapping for all virtual registers 108142e9c963921776cb498c33b6c6c03f29971316f3Jakob Stoklund Olesen StackSlotForVirtReg.resize(MRI->getNumVirtRegs()); 1082a240743ad954c657015b3ee3631e30fd6a2e86b2Jakob Stoklund Olesen LiveVirtRegs.setUniverse(MRI->getNumVirtRegs()); 108300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 108400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen // Loop over all of the basic blocks, eliminating virtual register references 10856fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen for (MachineFunction::iterator MBBi = Fn.begin(), MBBe = Fn.end(); 10866fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen MBBi != MBBe; ++MBBi) { 10876fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen MBB = &*MBBi; 10886fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen AllocateBasicBlock(); 10896fb69d85e9576445e98c4114ee7064deb4476712Jakob Stoklund Olesen } 109000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 10916de07178e1e6445080bf4f7704e274c5f219ff70Jakob Stoklund Olesen // Add the clobber lists for all the instructions we skipped earlier. 1092e837dead3c8dc3445ef6a0e2322179c57e264a13Evan Cheng for (SmallPtrSet<const MCInstrDesc*, 4>::const_iterator 10936de07178e1e6445080bf4f7704e274c5f219ff70Jakob Stoklund Olesen I = SkippedInstrs.begin(), E = SkippedInstrs.end(); I != E; ++I) 1094fac259814923d091942b230e7bd002a8d1130bc3Craig Topper if (const uint16_t *Defs = (*I)->getImplicitDefs()) 10956de07178e1e6445080bf4f7704e274c5f219ff70Jakob Stoklund Olesen while (*Defs) 10966de07178e1e6445080bf4f7704e274c5f219ff70Jakob Stoklund Olesen MRI->setPhysRegUsed(*Defs++); 10976de07178e1e6445080bf4f7704e274c5f219ff70Jakob Stoklund Olesen 109819273aec441411b4d571fdb87c6daa0fbe7a33a0Andrew Trick // All machine operands and other references to virtual registers have been 109919273aec441411b4d571fdb87c6daa0fbe7a33a0Andrew Trick // replaced. Remove the virtual registers. 110019273aec441411b4d571fdb87c6daa0fbe7a33a0Andrew Trick MRI->clearVirtRegs(); 110119273aec441411b4d571fdb87c6daa0fbe7a33a0Andrew Trick 11026de07178e1e6445080bf4f7704e274c5f219ff70Jakob Stoklund Olesen SkippedInstrs.clear(); 110300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen StackSlotForVirtReg.clear(); 1104459a36bd34809ffc5d74de79b3e46f6e02e5184fDevang Patel LiveDbgValueMap.clear(); 110500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen return true; 110600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 110700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 110800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund OlesenFunctionPass *llvm::createFastRegisterAllocator() { 110900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen return new RAFast(); 111000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 1111