1193323Sed//===-- RegisterScavenging.h - Machine register scavenging ------*- C++ -*-===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// This file declares the machine register scavenger class. It can provide 11193323Sed// information such as unused register at any point in a machine basic block. 12193323Sed// It also provides a mechanism to make registers availbale by evicting them 13193323Sed// to spill slots. 14193323Sed// 15193323Sed//===----------------------------------------------------------------------===// 16193323Sed 17249423Sdim#ifndef LLVM_CODEGEN_REGISTERSCAVENGING_H 18249423Sdim#define LLVM_CODEGEN_REGISTERSCAVENGING_H 19193323Sed 20249423Sdim#include "llvm/ADT/BitVector.h" 21193323Sed#include "llvm/CodeGen/MachineBasicBlock.h" 22243830Sdim#include "llvm/CodeGen/MachineRegisterInfo.h" 23193323Sed 24193323Sednamespace llvm { 25193323Sed 26193323Sedclass MachineRegisterInfo; 27193323Sedclass TargetRegisterInfo; 28193323Sedclass TargetInstrInfo; 29193323Sedclass TargetRegisterClass; 30193323Sed 31193323Sedclass RegScavenger { 32193323Sed const TargetRegisterInfo *TRI; 33193323Sed const TargetInstrInfo *TII; 34193323Sed MachineRegisterInfo* MRI; 35193323Sed MachineBasicBlock *MBB; 36193323Sed MachineBasicBlock::iterator MBBI; 37193323Sed unsigned NumPhysRegs; 38193323Sed 39193323Sed /// Tracking - True if RegScavenger is currently tracking the liveness of 40193323Sed /// registers. 41193323Sed bool Tracking; 42193323Sed 43249423Sdim /// Information on scavenged registers (held in a spill slot). 44249423Sdim struct ScavengedInfo { 45249423Sdim ScavengedInfo(int FI = -1) : FrameIndex(FI), Reg(0), Restore(NULL) {} 46193323Sed 47249423Sdim /// A spill slot used for scavenging a register post register allocation. 48249423Sdim int FrameIndex; 49193323Sed 50249423Sdim /// If non-zero, the specific register is currently being 51249423Sdim /// scavenged. That is, it is spilled to this scavenging stack slot. 52249423Sdim unsigned Reg; 53193323Sed 54249423Sdim /// The instruction that restores the scavenged register from stack. 55249423Sdim const MachineInstr *Restore; 56249423Sdim }; 57193323Sed 58249423Sdim /// A vector of information on scavenged registers. 59249423Sdim SmallVector<ScavengedInfo, 2> Scavenged; 60249423Sdim 61193323Sed /// CalleeSavedrRegs - A bitvector of callee saved registers for the target. 62193323Sed /// 63193323Sed BitVector CalleeSavedRegs; 64193323Sed 65193323Sed /// RegsAvailable - The current state of all the physical registers immediately 66193323Sed /// before MBBI. One bit per physical register. If bit is set that means it's 67193323Sed /// available, unset means the register is currently being used. 68193323Sed BitVector RegsAvailable; 69193323Sed 70234353Sdim // These BitVectors are only used internally to forward(). They are members 71234353Sdim // to avoid frequent reallocations. 72234353Sdim BitVector KillRegs, DefRegs; 73234353Sdim 74193323Sedpublic: 75193323Sed RegScavenger() 76249423Sdim : MBB(NULL), NumPhysRegs(0), Tracking(false) {} 77193323Sed 78193323Sed /// enterBasicBlock - Start tracking liveness from the begin of the specific 79193323Sed /// basic block. 80193323Sed void enterBasicBlock(MachineBasicBlock *mbb); 81193323Sed 82198090Srdivacky /// initRegState - allow resetting register state info for multiple 83198090Srdivacky /// passes over/within the same function. 84198090Srdivacky void initRegState(); 85198090Srdivacky 86198090Srdivacky /// forward - Move the internal MBB iterator and update register states. 87193323Sed void forward(); 88193323Sed 89198090Srdivacky /// forward - Move the internal MBB iterator and update register states until 90198090Srdivacky /// it has processed the specific iterator. 91193323Sed void forward(MachineBasicBlock::iterator I) { 92193323Sed if (!Tracking && MBB->begin() != I) forward(); 93193323Sed while (MBBI != I) forward(); 94193323Sed } 95193323Sed 96249423Sdim /// Invert the behavior of forward() on the current instruction (undo the 97249423Sdim /// changes to the available registers made by forward()). 98249423Sdim void unprocess(); 99249423Sdim 100249423Sdim /// Unprocess instructions until you reach the provided iterator. 101249423Sdim void unprocess(MachineBasicBlock::iterator I) { 102249423Sdim while (MBBI != I) unprocess(); 103249423Sdim } 104249423Sdim 105193323Sed /// skipTo - Move the internal MBB iterator but do not update register states. 106249423Sdim void skipTo(MachineBasicBlock::iterator I) { 107249423Sdim if (I == MachineBasicBlock::iterator(NULL)) 108249423Sdim Tracking = false; 109249423Sdim MBBI = I; 110249423Sdim } 111193323Sed 112249423Sdim MachineBasicBlock::iterator getCurrentPosition() const { 113249423Sdim return MBBI; 114249423Sdim } 115249423Sdim 116193323Sed /// getRegsUsed - return all registers currently in use in used. 117193323Sed void getRegsUsed(BitVector &used, bool includeReserved); 118193323Sed 119210299Sed /// getRegsAvailable - Return all available registers in the register class 120210299Sed /// in Mask. 121221345Sdim BitVector getRegsAvailable(const TargetRegisterClass *RC); 122210299Sed 123193323Sed /// FindUnusedReg - Find a unused register of the specified register class. 124198090Srdivacky /// Return 0 if none is found. 125198090Srdivacky unsigned FindUnusedReg(const TargetRegisterClass *RegClass) const; 126193323Sed 127249423Sdim /// Add a scavenging frame index. 128249423Sdim void addScavengingFrameIndex(int FI) { 129249423Sdim Scavenged.push_back(ScavengedInfo(FI)); 130249423Sdim } 131193323Sed 132249423Sdim /// Query whether a frame index is a scavenging frame index. 133249423Sdim bool isScavengingFrameIndex(int FI) const { 134263508Sdim for (SmallVectorImpl<ScavengedInfo>::const_iterator I = Scavenged.begin(), 135249423Sdim IE = Scavenged.end(); I != IE; ++I) 136249423Sdim if (I->FrameIndex == FI) 137249423Sdim return true; 138249423Sdim 139249423Sdim return false; 140249423Sdim } 141249423Sdim 142249423Sdim /// Get an array of scavenging frame indices. 143249423Sdim void getScavengingFrameIndices(SmallVectorImpl<int> &A) const { 144263508Sdim for (SmallVectorImpl<ScavengedInfo>::const_iterator I = Scavenged.begin(), 145249423Sdim IE = Scavenged.end(); I != IE; ++I) 146249423Sdim if (I->FrameIndex >= 0) 147249423Sdim A.push_back(I->FrameIndex); 148249423Sdim } 149249423Sdim 150193323Sed /// scavengeRegister - Make a register of the specific register class 151193323Sed /// available and do the appropriate bookkeeping. SPAdj is the stack 152193323Sed /// adjustment due to call frame, it's passed along to eliminateFrameIndex(). 153193323Sed /// Returns the scavenged register. 154193323Sed unsigned scavengeRegister(const TargetRegisterClass *RegClass, 155193323Sed MachineBasicBlock::iterator I, int SPAdj); 156193323Sed unsigned scavengeRegister(const TargetRegisterClass *RegClass, int SPAdj) { 157193323Sed return scavengeRegister(RegClass, MBBI, SPAdj); 158193323Sed } 159193323Sed 160198090Srdivacky /// setUsed - Tell the scavenger a register is used. 161198090Srdivacky /// 162198090Srdivacky void setUsed(unsigned Reg); 163193323Sedprivate: 164198090Srdivacky /// isReserved - Returns true if a register is reserved. It is never "unused". 165243830Sdim bool isReserved(unsigned Reg) const { return MRI->isReserved(Reg); } 166193323Sed 167249423Sdim /// isUsed - Test if a register is currently being used. When called by the 168249423Sdim /// isAliasUsed function, we only check isReserved if this is the original 169249423Sdim /// register, not an alias register. 170198090Srdivacky /// 171249423Sdim bool isUsed(unsigned Reg, bool CheckReserved = true) const { 172249423Sdim return !RegsAvailable.test(Reg) || (CheckReserved && isReserved(Reg)); 173234353Sdim } 174198090Srdivacky 175198090Srdivacky /// isAliasUsed - Is Reg or an alias currently in use? 176198090Srdivacky bool isAliasUsed(unsigned Reg) const; 177198090Srdivacky 178198090Srdivacky /// setUsed / setUnused - Mark the state of one or a number of registers. 179198090Srdivacky /// 180198090Srdivacky void setUsed(BitVector &Regs) { 181234353Sdim RegsAvailable.reset(Regs); 182198090Srdivacky } 183198090Srdivacky void setUnused(BitVector &Regs) { 184198090Srdivacky RegsAvailable |= Regs; 185198090Srdivacky } 186198090Srdivacky 187249423Sdim /// Processes the current instruction and fill the KillRegs and DefRegs bit 188249423Sdim /// vectors. 189249423Sdim void determineKillsAndDefs(); 190249423Sdim 191198090Srdivacky /// Add Reg and all its sub-registers to BV. 192198090Srdivacky void addRegWithSubRegs(BitVector &BV, unsigned Reg); 193198090Srdivacky 194210299Sed /// findSurvivorReg - Return the candidate register that is unused for the 195210299Sed /// longest after StartMI. UseMI is set to the instruction where the search 196210299Sed /// stopped. 197210299Sed /// 198210299Sed /// No more than InstrLimit instructions are inspected. 199210299Sed unsigned findSurvivorReg(MachineBasicBlock::iterator StartMI, 200198090Srdivacky BitVector &Candidates, 201198090Srdivacky unsigned InstrLimit, 202198090Srdivacky MachineBasicBlock::iterator &UseMI); 203198090Srdivacky 204193323Sed}; 205198090Srdivacky 206193323Sed} // End llvm namespace 207193323Sed 208193323Sed#endif 209