196fa612373e258120d351ed14361f964ad22f99dEvan Cheng//===-- RegisterScavenging.h - Machine register scavenging ------*- C++ -*-===// 296fa612373e258120d351ed14361f964ad22f99dEvan Cheng// 396fa612373e258120d351ed14361f964ad22f99dEvan Cheng// The LLVM Compiler Infrastructure 496fa612373e258120d351ed14361f964ad22f99dEvan Cheng// 57ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// This file is distributed under the University of Illinois Open Source 67ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// License. See LICENSE.TXT for details. 796fa612373e258120d351ed14361f964ad22f99dEvan Cheng// 896fa612373e258120d351ed14361f964ad22f99dEvan Cheng//===----------------------------------------------------------------------===// 996fa612373e258120d351ed14361f964ad22f99dEvan Cheng// 1096fa612373e258120d351ed14361f964ad22f99dEvan Cheng// This file declares the machine register scavenger class. It can provide 1196fa612373e258120d351ed14361f964ad22f99dEvan Cheng// information such as unused register at any point in a machine basic block. 1296fa612373e258120d351ed14361f964ad22f99dEvan Cheng// It also provides a mechanism to make registers availbale by evicting them 1396fa612373e258120d351ed14361f964ad22f99dEvan Cheng// to spill slots. 1496fa612373e258120d351ed14361f964ad22f99dEvan Cheng// 1596fa612373e258120d351ed14361f964ad22f99dEvan Cheng//===----------------------------------------------------------------------===// 1696fa612373e258120d351ed14361f964ad22f99dEvan Cheng 17674be02d525d4e24bc6943ed9274958c580bcfbcJakub Staszak#ifndef LLVM_CODEGEN_REGISTERSCAVENGING_H 18674be02d525d4e24bc6943ed9274958c580bcfbcJakub Staszak#define LLVM_CODEGEN_REGISTERSCAVENGING_H 1996fa612373e258120d351ed14361f964ad22f99dEvan Cheng 20255f89faee13dc491cb64fbeae3c763e7e2ea4e6Chandler Carruth#include "llvm/ADT/BitVector.h" 2196fa612373e258120d351ed14361f964ad22f99dEvan Cheng#include "llvm/CodeGen/MachineBasicBlock.h" 22fb9ebbf236974beac31705eaeb9f50ab585af6abJakob Stoklund Olesen#include "llvm/CodeGen/MachineRegisterInfo.h" 2396fa612373e258120d351ed14361f964ad22f99dEvan Cheng 2496fa612373e258120d351ed14361f964ad22f99dEvan Chengnamespace llvm { 2596fa612373e258120d351ed14361f964ad22f99dEvan Cheng 26c5ea2010c06fa6a2eaac17e493fbfe8a042e132aEvan Chengclass MachineRegisterInfo; 276f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohmanclass TargetRegisterInfo; 28b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Chengclass TargetInstrInfo; 2996fa612373e258120d351ed14361f964ad22f99dEvan Chengclass TargetRegisterClass; 3096fa612373e258120d351ed14361f964ad22f99dEvan Cheng 3196fa612373e258120d351ed14361f964ad22f99dEvan Chengclass RegScavenger { 32d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng const TargetRegisterInfo *TRI; 33d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng const TargetInstrInfo *TII; 34d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng MachineRegisterInfo* MRI; 3596fa612373e258120d351ed14361f964ad22f99dEvan Cheng MachineBasicBlock *MBB; 3696fa612373e258120d351ed14361f964ad22f99dEvan Cheng MachineBasicBlock::iterator MBBI; 3796fa612373e258120d351ed14361f964ad22f99dEvan Cheng unsigned NumPhysRegs; 3896fa612373e258120d351ed14361f964ad22f99dEvan Cheng 39898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng /// Tracking - True if RegScavenger is currently tracking the liveness of 40898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng /// registers. 41898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng bool Tracking; 42bb6fb3357d6c1e9ffb15de4893e59e3bbdd600a3Evan Cheng 43dc3beb90178fc316f63790812b22201884eaa017Hal Finkel /// Information on scavenged registers (held in a spill slot). 44dc3beb90178fc316f63790812b22201884eaa017Hal Finkel struct ScavengedInfo { 45df23a60fa6ce053511388e1bccca5900757e1aacHal Finkel ScavengedInfo(int FI = -1) : FrameIndex(FI), Reg(0), Restore(NULL) {} 46b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 47dc3beb90178fc316f63790812b22201884eaa017Hal Finkel /// A spill slot used for scavenging a register post register allocation. 48dc3beb90178fc316f63790812b22201884eaa017Hal Finkel int FrameIndex; 49b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 50dc3beb90178fc316f63790812b22201884eaa017Hal Finkel /// If non-zero, the specific register is currently being 51dc3beb90178fc316f63790812b22201884eaa017Hal Finkel /// scavenged. That is, it is spilled to this scavenging stack slot. 52dc3beb90178fc316f63790812b22201884eaa017Hal Finkel unsigned Reg; 53dc3beb90178fc316f63790812b22201884eaa017Hal Finkel 54dc3beb90178fc316f63790812b22201884eaa017Hal Finkel /// The instruction that restores the scavenged register from stack. 55dc3beb90178fc316f63790812b22201884eaa017Hal Finkel const MachineInstr *Restore; 56dc3beb90178fc316f63790812b22201884eaa017Hal Finkel }; 57dc3beb90178fc316f63790812b22201884eaa017Hal Finkel 58dc3beb90178fc316f63790812b22201884eaa017Hal Finkel /// A vector of information on scavenged registers. 59dc3beb90178fc316f63790812b22201884eaa017Hal Finkel SmallVector<ScavengedInfo, 2> Scavenged; 60d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng 61d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng /// CalleeSavedrRegs - A bitvector of callee saved registers for the target. 62d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng /// 63d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng BitVector CalleeSavedRegs; 64d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng 65c6b9ef80a890fcf75f18cabc3fe2d5f9ef2faaf5Dale Johannesen /// RegsAvailable - The current state of all the physical registers immediately 6696fa612373e258120d351ed14361f964ad22f99dEvan Cheng /// before MBBI. One bit per physical register. If bit is set that means it's 6796fa612373e258120d351ed14361f964ad22f99dEvan Cheng /// available, unset means the register is currently being used. 68c6b9ef80a890fcf75f18cabc3fe2d5f9ef2faaf5Dale Johannesen BitVector RegsAvailable; 6996fa612373e258120d351ed14361f964ad22f99dEvan Cheng 709f946a24d9e69559d1e0aeb6d128c2fa19846c92Jakob Stoklund Olesen // These BitVectors are only used internally to forward(). They are members 719f946a24d9e69559d1e0aeb6d128c2fa19846c92Jakob Stoklund Olesen // to avoid frequent reallocations. 729f946a24d9e69559d1e0aeb6d128c2fa19846c92Jakob Stoklund Olesen BitVector KillRegs, DefRegs; 739f946a24d9e69559d1e0aeb6d128c2fa19846c92Jakob Stoklund Olesen 7496fa612373e258120d351ed14361f964ad22f99dEvan Chengpublic: 75bb6fb3357d6c1e9ffb15de4893e59e3bbdd600a3Evan Cheng RegScavenger() 76dc3beb90178fc316f63790812b22201884eaa017Hal Finkel : MBB(NULL), NumPhysRegs(0), Tracking(false) {} 77bb6fb3357d6c1e9ffb15de4893e59e3bbdd600a3Evan Cheng 7828654b6205acc56863cdf988eed3e345da11eca3Evan Cheng /// enterBasicBlock - Start tracking liveness from the begin of the specific 7928654b6205acc56863cdf988eed3e345da11eca3Evan Cheng /// basic block. 8028654b6205acc56863cdf988eed3e345da11eca3Evan Cheng void enterBasicBlock(MachineBasicBlock *mbb); 8196fa612373e258120d351ed14361f964ad22f99dEvan Cheng 82e0161ea1050fd4107f3307b1e25b3aac02c2ba16John Mosby /// initRegState - allow resetting register state info for multiple 83e0161ea1050fd4107f3307b1e25b3aac02c2ba16John Mosby /// passes over/within the same function. 84e0161ea1050fd4107f3307b1e25b3aac02c2ba16John Mosby void initRegState(); 85e0161ea1050fd4107f3307b1e25b3aac02c2ba16John Mosby 8631f5591c91d4c012901018013aba19b0015fa6a0Jakob Stoklund Olesen /// forward - Move the internal MBB iterator and update register states. 8796fa612373e258120d351ed14361f964ad22f99dEvan Cheng void forward(); 8896fa612373e258120d351ed14361f964ad22f99dEvan Cheng 8931f5591c91d4c012901018013aba19b0015fa6a0Jakob Stoklund Olesen /// forward - Move the internal MBB iterator and update register states until 9031f5591c91d4c012901018013aba19b0015fa6a0Jakob Stoklund Olesen /// it has processed the specific iterator. 91bb6fb3357d6c1e9ffb15de4893e59e3bbdd600a3Evan Cheng void forward(MachineBasicBlock::iterator I) { 925b200d8a133a07af1f7802025bd5a58a1cdd544dDan Gohman if (!Tracking && MBB->begin() != I) forward(); 93bb6fb3357d6c1e9ffb15de4893e59e3bbdd600a3Evan Cheng while (MBBI != I) forward(); 94bb6fb3357d6c1e9ffb15de4893e59e3bbdd600a3Evan Cheng } 95ed570dedad945e1fe9a4bfeaa47276d875f1feedEvan Cheng 962e80991a7712d51f7637513703fc896f93eea252Hal Finkel /// Invert the behavior of forward() on the current instruction (undo the 972e80991a7712d51f7637513703fc896f93eea252Hal Finkel /// changes to the available registers made by forward()). 982e80991a7712d51f7637513703fc896f93eea252Hal Finkel void unprocess(); 992e80991a7712d51f7637513703fc896f93eea252Hal Finkel 1002e80991a7712d51f7637513703fc896f93eea252Hal Finkel /// Unprocess instructions until you reach the provided iterator. 1012e80991a7712d51f7637513703fc896f93eea252Hal Finkel void unprocess(MachineBasicBlock::iterator I) { 1022e80991a7712d51f7637513703fc896f93eea252Hal Finkel while (MBBI != I) unprocess(); 1032e80991a7712d51f7637513703fc896f93eea252Hal Finkel } 1042e80991a7712d51f7637513703fc896f93eea252Hal Finkel 105f262b355593100c6e0fc629b03c76ab0b1e2d915Evan Cheng /// skipTo - Move the internal MBB iterator but do not update register states. 1068846129f6eb58982a2cac22306c8c9b586084475Hal Finkel void skipTo(MachineBasicBlock::iterator I) { 1078846129f6eb58982a2cac22306c8c9b586084475Hal Finkel if (I == MachineBasicBlock::iterator(NULL)) 1088846129f6eb58982a2cac22306c8c9b586084475Hal Finkel Tracking = false; 1098846129f6eb58982a2cac22306c8c9b586084475Hal Finkel MBBI = I; 1108846129f6eb58982a2cac22306c8c9b586084475Hal Finkel } 111f262b355593100c6e0fc629b03c76ab0b1e2d915Evan Cheng 1122e80991a7712d51f7637513703fc896f93eea252Hal Finkel MachineBasicBlock::iterator getCurrentPosition() const { 1132e80991a7712d51f7637513703fc896f93eea252Hal Finkel return MBBI; 1142e80991a7712d51f7637513703fc896f93eea252Hal Finkel } 1152e80991a7712d51f7637513703fc896f93eea252Hal Finkel 11669cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen /// getRegsUsed - return all registers currently in use in used. 11769cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen void getRegsUsed(BitVector &used, bool includeReserved); 11869cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen 119d9642faf7c66273eb3a8d99e5fa6b542da5374ddJim Grosbach /// getRegsAvailable - Return all available registers in the register class 120d9642faf7c66273eb3a8d99e5fa6b542da5374ddJim Grosbach /// in Mask. 12127ea9999e84dfb1e6c2baf06ec27a92f12753917Jim Grosbach BitVector getRegsAvailable(const TargetRegisterClass *RC); 122d9642faf7c66273eb3a8d99e5fa6b542da5374ddJim Grosbach 12396fa612373e258120d351ed14361f964ad22f99dEvan Cheng /// FindUnusedReg - Find a unused register of the specified register class. 124c0823fe7c679ca8f7d1667a310c2fca97b9402d5Jakob Stoklund Olesen /// Return 0 if none is found. 125c0823fe7c679ca8f7d1667a310c2fca97b9402d5Jakob Stoklund Olesen unsigned FindUnusedReg(const TargetRegisterClass *RegClass) const; 12696fa612373e258120d351ed14361f964ad22f99dEvan Cheng 127dc3beb90178fc316f63790812b22201884eaa017Hal Finkel /// Add a scavenging frame index. 128dc3beb90178fc316f63790812b22201884eaa017Hal Finkel void addScavengingFrameIndex(int FI) { 129dc3beb90178fc316f63790812b22201884eaa017Hal Finkel Scavenged.push_back(ScavengedInfo(FI)); 130dc3beb90178fc316f63790812b22201884eaa017Hal Finkel } 131dc3beb90178fc316f63790812b22201884eaa017Hal Finkel 132dc3beb90178fc316f63790812b22201884eaa017Hal Finkel /// Query whether a frame index is a scavenging frame index. 133dc3beb90178fc316f63790812b22201884eaa017Hal Finkel bool isScavengingFrameIndex(int FI) const { 134d0a3916e430201d0179c723e4ebdd9bf4f0ee02bEric Christopher for (SmallVectorImpl<ScavengedInfo>::const_iterator I = Scavenged.begin(), 135dc3beb90178fc316f63790812b22201884eaa017Hal Finkel IE = Scavenged.end(); I != IE; ++I) 136dc3beb90178fc316f63790812b22201884eaa017Hal Finkel if (I->FrameIndex == FI) 137dc3beb90178fc316f63790812b22201884eaa017Hal Finkel return true; 138dc3beb90178fc316f63790812b22201884eaa017Hal Finkel 139dc3beb90178fc316f63790812b22201884eaa017Hal Finkel return false; 140dc3beb90178fc316f63790812b22201884eaa017Hal Finkel } 141dc3beb90178fc316f63790812b22201884eaa017Hal Finkel 142dc3beb90178fc316f63790812b22201884eaa017Hal Finkel /// Get an array of scavenging frame indices. 143dc3beb90178fc316f63790812b22201884eaa017Hal Finkel void getScavengingFrameIndices(SmallVectorImpl<int> &A) const { 144d0a3916e430201d0179c723e4ebdd9bf4f0ee02bEric Christopher for (SmallVectorImpl<ScavengedInfo>::const_iterator I = Scavenged.begin(), 145dc3beb90178fc316f63790812b22201884eaa017Hal Finkel IE = Scavenged.end(); I != IE; ++I) 146df23a60fa6ce053511388e1bccca5900757e1aacHal Finkel if (I->FrameIndex >= 0) 147df23a60fa6ce053511388e1bccca5900757e1aacHal Finkel A.push_back(I->FrameIndex); 148dc3beb90178fc316f63790812b22201884eaa017Hal Finkel } 149b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 150b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng /// scavengeRegister - Make a register of the specific register class 151a09f0d4ab76725827d1c4e737b99ff15ba454cbcEvan Cheng /// available and do the appropriate bookkeeping. SPAdj is the stack 152a09f0d4ab76725827d1c4e737b99ff15ba454cbcEvan Cheng /// adjustment due to call frame, it's passed along to eliminateFrameIndex(). 153a09f0d4ab76725827d1c4e737b99ff15ba454cbcEvan Cheng /// Returns the scavenged register. 154b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng unsigned scavengeRegister(const TargetRegisterClass *RegClass, 155a09f0d4ab76725827d1c4e737b99ff15ba454cbcEvan Cheng MachineBasicBlock::iterator I, int SPAdj); 156a09f0d4ab76725827d1c4e737b99ff15ba454cbcEvan Cheng unsigned scavengeRegister(const TargetRegisterClass *RegClass, int SPAdj) { 157a09f0d4ab76725827d1c4e737b99ff15ba454cbcEvan Cheng return scavengeRegister(RegClass, MBBI, SPAdj); 158b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng } 159b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 160b58f498f7502e7e1833decbbbb4df771367c7341Jim Grosbach /// setUsed - Tell the scavenger a register is used. 161b58f498f7502e7e1833decbbbb4df771367c7341Jim Grosbach /// 162b58f498f7502e7e1833decbbbb4df771367c7341Jim Grosbach void setUsed(unsigned Reg); 16396fa612373e258120d351ed14361f964ad22f99dEvan Chengprivate: 164e689ce626ce1d0022f70fb4a85113590bbdbb5e9Jakob Stoklund Olesen /// isReserved - Returns true if a register is reserved. It is never "unused". 165fb9ebbf236974beac31705eaeb9f50ab585af6abJakob Stoklund Olesen bool isReserved(unsigned Reg) const { return MRI->isReserved(Reg); } 166e689ce626ce1d0022f70fb4a85113590bbdbb5e9Jakob Stoklund Olesen 1674823be3be1d87632fbd51ce8e51a58ee5e44b115Chad Rosier /// isUsed - Test if a register is currently being used. When called by the 1684823be3be1d87632fbd51ce8e51a58ee5e44b115Chad Rosier /// isAliasUsed function, we only check isReserved if this is the original 1694823be3be1d87632fbd51ce8e51a58ee5e44b115Chad Rosier /// register, not an alias register. 170e689ce626ce1d0022f70fb4a85113590bbdbb5e9Jakob Stoklund Olesen /// 1714823be3be1d87632fbd51ce8e51a58ee5e44b115Chad Rosier bool isUsed(unsigned Reg, bool CheckReserved = true) const { 1724823be3be1d87632fbd51ce8e51a58ee5e44b115Chad Rosier return !RegsAvailable.test(Reg) || (CheckReserved && isReserved(Reg)); 173cf14613455bc32b6a17821808595263e061335bcJakob Stoklund Olesen } 174e689ce626ce1d0022f70fb4a85113590bbdbb5e9Jakob Stoklund Olesen 175e689ce626ce1d0022f70fb4a85113590bbdbb5e9Jakob Stoklund Olesen /// isAliasUsed - Is Reg or an alias currently in use? 176e689ce626ce1d0022f70fb4a85113590bbdbb5e9Jakob Stoklund Olesen bool isAliasUsed(unsigned Reg) const; 177e689ce626ce1d0022f70fb4a85113590bbdbb5e9Jakob Stoklund Olesen 178e689ce626ce1d0022f70fb4a85113590bbdbb5e9Jakob Stoklund Olesen /// setUsed / setUnused - Mark the state of one or a number of registers. 179e689ce626ce1d0022f70fb4a85113590bbdbb5e9Jakob Stoklund Olesen /// 180e689ce626ce1d0022f70fb4a85113590bbdbb5e9Jakob Stoklund Olesen void setUsed(BitVector &Regs) { 1819f946a24d9e69559d1e0aeb6d128c2fa19846c92Jakob Stoklund Olesen RegsAvailable.reset(Regs); 182e689ce626ce1d0022f70fb4a85113590bbdbb5e9Jakob Stoklund Olesen } 183e689ce626ce1d0022f70fb4a85113590bbdbb5e9Jakob Stoklund Olesen void setUnused(BitVector &Regs) { 184e689ce626ce1d0022f70fb4a85113590bbdbb5e9Jakob Stoklund Olesen RegsAvailable |= Regs; 185e689ce626ce1d0022f70fb4a85113590bbdbb5e9Jakob Stoklund Olesen } 186d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng 1872e80991a7712d51f7637513703fc896f93eea252Hal Finkel /// Processes the current instruction and fill the KillRegs and DefRegs bit 1882e80991a7712d51f7637513703fc896f93eea252Hal Finkel /// vectors. 1892e80991a7712d51f7637513703fc896f93eea252Hal Finkel void determineKillsAndDefs(); 1902e80991a7712d51f7637513703fc896f93eea252Hal Finkel 191dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen /// Add Reg and all its sub-registers to BV. 192dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen void addRegWithSubRegs(BitVector &BV, unsigned Reg); 193dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen 194b113cf2fedaf290242939c8f8c6f7e1438d46024Jim Grosbach /// findSurvivorReg - Return the candidate register that is unused for the 195b113cf2fedaf290242939c8f8c6f7e1438d46024Jim Grosbach /// longest after StartMI. UseMI is set to the instruction where the search 196b113cf2fedaf290242939c8f8c6f7e1438d46024Jim Grosbach /// stopped. 197b113cf2fedaf290242939c8f8c6f7e1438d46024Jim Grosbach /// 198b113cf2fedaf290242939c8f8c6f7e1438d46024Jim Grosbach /// No more than InstrLimit instructions are inspected. 199b113cf2fedaf290242939c8f8c6f7e1438d46024Jim Grosbach unsigned findSurvivorReg(MachineBasicBlock::iterator StartMI, 200b113cf2fedaf290242939c8f8c6f7e1438d46024Jim Grosbach BitVector &Candidates, 201b113cf2fedaf290242939c8f8c6f7e1438d46024Jim Grosbach unsigned InstrLimit, 202b113cf2fedaf290242939c8f8c6f7e1438d46024Jim Grosbach MachineBasicBlock::iterator &UseMI); 203b113cf2fedaf290242939c8f8c6f7e1438d46024Jim Grosbach 20496fa612373e258120d351ed14361f964ad22f99dEvan Cheng}; 205dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen 20696fa612373e258120d351ed14361f964ad22f99dEvan Cheng} // End llvm namespace 20796fa612373e258120d351ed14361f964ad22f99dEvan Cheng 20896fa612373e258120d351ed14361f964ad22f99dEvan Cheng#endif 209