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 43b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng /// ScavengingFrameIndex - Special spill slot used for scavenging a register 44b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng /// post register allocation. 45b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng int ScavengingFrameIndex; 46b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 47b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng /// ScavengedReg - If none zero, the specific register is currently being 48b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng /// scavenged. That is, it is spilled to the special scavenging stack slot. 49b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng unsigned ScavengedReg; 50b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 51b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng /// ScavengedRC - Register class of the scavenged register. 52b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng /// 53b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng const TargetRegisterClass *ScavengedRC; 54b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 55d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng /// ScavengeRestore - Instruction that restores the scavenged register from 56d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng /// stack. 57d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng const MachineInstr *ScavengeRestore; 58d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng 59d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng /// CalleeSavedrRegs - A bitvector of callee saved registers for the target. 60d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng /// 61d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng BitVector CalleeSavedRegs; 62d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng 63c6b9ef80a890fcf75f18cabc3fe2d5f9ef2faaf5Dale Johannesen /// RegsAvailable - The current state of all the physical registers immediately 6496fa612373e258120d351ed14361f964ad22f99dEvan Cheng /// before MBBI. One bit per physical register. If bit is set that means it's 6596fa612373e258120d351ed14361f964ad22f99dEvan Cheng /// available, unset means the register is currently being used. 66c6b9ef80a890fcf75f18cabc3fe2d5f9ef2faaf5Dale Johannesen BitVector RegsAvailable; 6796fa612373e258120d351ed14361f964ad22f99dEvan Cheng 689f946a24d9e69559d1e0aeb6d128c2fa19846c92Jakob Stoklund Olesen // These BitVectors are only used internally to forward(). They are members 699f946a24d9e69559d1e0aeb6d128c2fa19846c92Jakob Stoklund Olesen // to avoid frequent reallocations. 709f946a24d9e69559d1e0aeb6d128c2fa19846c92Jakob Stoklund Olesen BitVector KillRegs, DefRegs; 719f946a24d9e69559d1e0aeb6d128c2fa19846c92Jakob Stoklund Olesen 7296fa612373e258120d351ed14361f964ad22f99dEvan Chengpublic: 73bb6fb3357d6c1e9ffb15de4893e59e3bbdd600a3Evan Cheng RegScavenger() 74b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng : MBB(NULL), NumPhysRegs(0), Tracking(false), 7581975f6dfd9d306d0ea7ce3ef22561c949de9af9Dan Gohman ScavengingFrameIndex(-1), ScavengedReg(0), ScavengedRC(NULL) {} 76bb6fb3357d6c1e9ffb15de4893e59e3bbdd600a3Evan Cheng 7728654b6205acc56863cdf988eed3e345da11eca3Evan Cheng /// enterBasicBlock - Start tracking liveness from the begin of the specific 7828654b6205acc56863cdf988eed3e345da11eca3Evan Cheng /// basic block. 7928654b6205acc56863cdf988eed3e345da11eca3Evan Cheng void enterBasicBlock(MachineBasicBlock *mbb); 8096fa612373e258120d351ed14361f964ad22f99dEvan Cheng 81e0161ea1050fd4107f3307b1e25b3aac02c2ba16John Mosby /// initRegState - allow resetting register state info for multiple 82e0161ea1050fd4107f3307b1e25b3aac02c2ba16John Mosby /// passes over/within the same function. 83e0161ea1050fd4107f3307b1e25b3aac02c2ba16John Mosby void initRegState(); 84e0161ea1050fd4107f3307b1e25b3aac02c2ba16John Mosby 8531f5591c91d4c012901018013aba19b0015fa6a0Jakob Stoklund Olesen /// forward - Move the internal MBB iterator and update register states. 8696fa612373e258120d351ed14361f964ad22f99dEvan Cheng void forward(); 8796fa612373e258120d351ed14361f964ad22f99dEvan Cheng 8831f5591c91d4c012901018013aba19b0015fa6a0Jakob Stoklund Olesen /// forward - Move the internal MBB iterator and update register states until 8931f5591c91d4c012901018013aba19b0015fa6a0Jakob Stoklund Olesen /// it has processed the specific iterator. 90bb6fb3357d6c1e9ffb15de4893e59e3bbdd600a3Evan Cheng void forward(MachineBasicBlock::iterator I) { 915b200d8a133a07af1f7802025bd5a58a1cdd544dDan Gohman if (!Tracking && MBB->begin() != I) forward(); 92bb6fb3357d6c1e9ffb15de4893e59e3bbdd600a3Evan Cheng while (MBBI != I) forward(); 93bb6fb3357d6c1e9ffb15de4893e59e3bbdd600a3Evan Cheng } 94ed570dedad945e1fe9a4bfeaa47276d875f1feedEvan Cheng 95f262b355593100c6e0fc629b03c76ab0b1e2d915Evan Cheng /// skipTo - Move the internal MBB iterator but do not update register states. 96f262b355593100c6e0fc629b03c76ab0b1e2d915Evan Cheng /// 97f262b355593100c6e0fc629b03c76ab0b1e2d915Evan Cheng void skipTo(MachineBasicBlock::iterator I) { MBBI = I; } 98f262b355593100c6e0fc629b03c76ab0b1e2d915Evan Cheng 9969cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen /// getRegsUsed - return all registers currently in use in used. 10069cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen void getRegsUsed(BitVector &used, bool includeReserved); 10169cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen 102d9642faf7c66273eb3a8d99e5fa6b542da5374ddJim Grosbach /// getRegsAvailable - Return all available registers in the register class 103d9642faf7c66273eb3a8d99e5fa6b542da5374ddJim Grosbach /// in Mask. 10427ea9999e84dfb1e6c2baf06ec27a92f12753917Jim Grosbach BitVector getRegsAvailable(const TargetRegisterClass *RC); 105d9642faf7c66273eb3a8d99e5fa6b542da5374ddJim Grosbach 10696fa612373e258120d351ed14361f964ad22f99dEvan Cheng /// FindUnusedReg - Find a unused register of the specified register class. 107c0823fe7c679ca8f7d1667a310c2fca97b9402d5Jakob Stoklund Olesen /// Return 0 if none is found. 108c0823fe7c679ca8f7d1667a310c2fca97b9402d5Jakob Stoklund Olesen unsigned FindUnusedReg(const TargetRegisterClass *RegClass) const; 10996fa612373e258120d351ed14361f964ad22f99dEvan Cheng 110b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng /// setScavengingFrameIndex / getScavengingFrameIndex - accessor and setter of 111b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng /// ScavengingFrameIndex. 112b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng void setScavengingFrameIndex(int FI) { ScavengingFrameIndex = FI; } 113b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng int getScavengingFrameIndex() const { return ScavengingFrameIndex; } 114b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 115b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng /// scavengeRegister - Make a register of the specific register class 116a09f0d4ab76725827d1c4e737b99ff15ba454cbcEvan Cheng /// available and do the appropriate bookkeeping. SPAdj is the stack 117a09f0d4ab76725827d1c4e737b99ff15ba454cbcEvan Cheng /// adjustment due to call frame, it's passed along to eliminateFrameIndex(). 118a09f0d4ab76725827d1c4e737b99ff15ba454cbcEvan Cheng /// Returns the scavenged register. 119b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng unsigned scavengeRegister(const TargetRegisterClass *RegClass, 120a09f0d4ab76725827d1c4e737b99ff15ba454cbcEvan Cheng MachineBasicBlock::iterator I, int SPAdj); 121a09f0d4ab76725827d1c4e737b99ff15ba454cbcEvan Cheng unsigned scavengeRegister(const TargetRegisterClass *RegClass, int SPAdj) { 122a09f0d4ab76725827d1c4e737b99ff15ba454cbcEvan Cheng return scavengeRegister(RegClass, MBBI, SPAdj); 123b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng } 124b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 125b58f498f7502e7e1833decbbbb4df771367c7341Jim Grosbach /// setUsed - Tell the scavenger a register is used. 126b58f498f7502e7e1833decbbbb4df771367c7341Jim Grosbach /// 127b58f498f7502e7e1833decbbbb4df771367c7341Jim Grosbach void setUsed(unsigned Reg); 12896fa612373e258120d351ed14361f964ad22f99dEvan Chengprivate: 129e689ce626ce1d0022f70fb4a85113590bbdbb5e9Jakob Stoklund Olesen /// isReserved - Returns true if a register is reserved. It is never "unused". 130fb9ebbf236974beac31705eaeb9f50ab585af6abJakob Stoklund Olesen bool isReserved(unsigned Reg) const { return MRI->isReserved(Reg); } 131e689ce626ce1d0022f70fb4a85113590bbdbb5e9Jakob Stoklund Olesen 1324823be3be1d87632fbd51ce8e51a58ee5e44b115Chad Rosier /// isUsed - Test if a register is currently being used. When called by the 1334823be3be1d87632fbd51ce8e51a58ee5e44b115Chad Rosier /// isAliasUsed function, we only check isReserved if this is the original 1344823be3be1d87632fbd51ce8e51a58ee5e44b115Chad Rosier /// register, not an alias register. 135e689ce626ce1d0022f70fb4a85113590bbdbb5e9Jakob Stoklund Olesen /// 1364823be3be1d87632fbd51ce8e51a58ee5e44b115Chad Rosier bool isUsed(unsigned Reg, bool CheckReserved = true) const { 1374823be3be1d87632fbd51ce8e51a58ee5e44b115Chad Rosier return !RegsAvailable.test(Reg) || (CheckReserved && isReserved(Reg)); 138cf14613455bc32b6a17821808595263e061335bcJakob Stoklund Olesen } 139e689ce626ce1d0022f70fb4a85113590bbdbb5e9Jakob Stoklund Olesen 140e689ce626ce1d0022f70fb4a85113590bbdbb5e9Jakob Stoklund Olesen /// isAliasUsed - Is Reg or an alias currently in use? 141e689ce626ce1d0022f70fb4a85113590bbdbb5e9Jakob Stoklund Olesen bool isAliasUsed(unsigned Reg) const; 142e689ce626ce1d0022f70fb4a85113590bbdbb5e9Jakob Stoklund Olesen 143e689ce626ce1d0022f70fb4a85113590bbdbb5e9Jakob Stoklund Olesen /// setUsed / setUnused - Mark the state of one or a number of registers. 144e689ce626ce1d0022f70fb4a85113590bbdbb5e9Jakob Stoklund Olesen /// 145e689ce626ce1d0022f70fb4a85113590bbdbb5e9Jakob Stoklund Olesen void setUsed(BitVector &Regs) { 1469f946a24d9e69559d1e0aeb6d128c2fa19846c92Jakob Stoklund Olesen RegsAvailable.reset(Regs); 147e689ce626ce1d0022f70fb4a85113590bbdbb5e9Jakob Stoklund Olesen } 148e689ce626ce1d0022f70fb4a85113590bbdbb5e9Jakob Stoklund Olesen void setUnused(BitVector &Regs) { 149e689ce626ce1d0022f70fb4a85113590bbdbb5e9Jakob Stoklund Olesen RegsAvailable |= Regs; 150e689ce626ce1d0022f70fb4a85113590bbdbb5e9Jakob Stoklund Olesen } 151d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng 152dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen /// Add Reg and all its sub-registers to BV. 153dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen void addRegWithSubRegs(BitVector &BV, unsigned Reg); 154dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen 155b113cf2fedaf290242939c8f8c6f7e1438d46024Jim Grosbach /// findSurvivorReg - Return the candidate register that is unused for the 156b113cf2fedaf290242939c8f8c6f7e1438d46024Jim Grosbach /// longest after StartMI. UseMI is set to the instruction where the search 157b113cf2fedaf290242939c8f8c6f7e1438d46024Jim Grosbach /// stopped. 158b113cf2fedaf290242939c8f8c6f7e1438d46024Jim Grosbach /// 159b113cf2fedaf290242939c8f8c6f7e1438d46024Jim Grosbach /// No more than InstrLimit instructions are inspected. 160b113cf2fedaf290242939c8f8c6f7e1438d46024Jim Grosbach unsigned findSurvivorReg(MachineBasicBlock::iterator StartMI, 161b113cf2fedaf290242939c8f8c6f7e1438d46024Jim Grosbach BitVector &Candidates, 162b113cf2fedaf290242939c8f8c6f7e1438d46024Jim Grosbach unsigned InstrLimit, 163b113cf2fedaf290242939c8f8c6f7e1438d46024Jim Grosbach MachineBasicBlock::iterator &UseMI); 164b113cf2fedaf290242939c8f8c6f7e1438d46024Jim Grosbach 16596fa612373e258120d351ed14361f964ad22f99dEvan Cheng}; 166dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen 16796fa612373e258120d351ed14361f964ad22f99dEvan Cheng} // End llvm namespace 16896fa612373e258120d351ed14361f964ad22f99dEvan Cheng 16996fa612373e258120d351ed14361f964ad22f99dEvan Cheng#endif 170