1 //===-- RegisterScavenging.h - Machine register scavenging ------*- C++ -*-===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This file declares the machine register scavenger class. It can provide 11 // information such as unused register at any point in a machine basic block. 12 // It also provides a mechanism to make registers available by evicting them 13 // to spill slots. 14 // 15 //===----------------------------------------------------------------------===// 16 17 #ifndef LLVM_CODEGEN_REGISTERSCAVENGING_H 18 #define LLVM_CODEGEN_REGISTERSCAVENGING_H 19 20 #include "llvm/ADT/BitVector.h" 21 #include "llvm/CodeGen/MachineBasicBlock.h" 22 #include "llvm/CodeGen/MachineRegisterInfo.h" 23 24 namespace llvm { 25 26 class MachineRegisterInfo; 27 class TargetRegisterInfo; 28 class TargetInstrInfo; 29 class TargetRegisterClass; 30 31 class RegScavenger { 32 const TargetRegisterInfo *TRI; 33 const TargetInstrInfo *TII; 34 MachineRegisterInfo* MRI; 35 MachineBasicBlock *MBB; 36 MachineBasicBlock::iterator MBBI; 37 unsigned NumRegUnits; 38 39 /// True if RegScavenger is currently tracking the liveness of registers. 40 bool Tracking; 41 42 /// Information on scavenged registers (held in a spill slot). 43 struct ScavengedInfo { FrameIndexScavengedInfo44 ScavengedInfo(int FI = -1) : FrameIndex(FI), Reg(0), Restore(nullptr) {} 45 46 /// A spill slot used for scavenging a register post register allocation. 47 int FrameIndex; 48 49 /// If non-zero, the specific register is currently being 50 /// scavenged. That is, it is spilled to this scavenging stack slot. 51 unsigned Reg; 52 53 /// The instruction that restores the scavenged register from stack. 54 const MachineInstr *Restore; 55 }; 56 57 /// A vector of information on scavenged registers. 58 SmallVector<ScavengedInfo, 2> Scavenged; 59 60 /// The current state of each reg unit immediately before MBBI. 61 /// One bit per register unit. If bit is not set it means any 62 /// register containing that register unit is currently being used. 63 BitVector RegUnitsAvailable; 64 65 // These BitVectors are only used internally to forward(). They are members 66 // to avoid frequent reallocations. 67 BitVector KillRegUnits, DefRegUnits; 68 BitVector TmpRegUnits; 69 70 public: RegScavenger()71 RegScavenger() 72 : MBB(nullptr), NumRegUnits(0), Tracking(false) {} 73 74 /// Start tracking liveness from the begin of the specific basic block. 75 void enterBasicBlock(MachineBasicBlock *mbb); 76 77 /// Move the internal MBB iterator and update register states. 78 void forward(); 79 80 /// Move the internal MBB iterator and update register states until 81 /// it has processed the specific iterator. forward(MachineBasicBlock::iterator I)82 void forward(MachineBasicBlock::iterator I) { 83 if (!Tracking && MBB->begin() != I) forward(); 84 while (MBBI != I) forward(); 85 } 86 87 /// Invert the behavior of forward() on the current instruction (undo the 88 /// changes to the available registers made by forward()). 89 void unprocess(); 90 91 /// Unprocess instructions until you reach the provided iterator. unprocess(MachineBasicBlock::iterator I)92 void unprocess(MachineBasicBlock::iterator I) { 93 while (MBBI != I) unprocess(); 94 } 95 96 /// Move the internal MBB iterator but do not update register states. skipTo(MachineBasicBlock::iterator I)97 void skipTo(MachineBasicBlock::iterator I) { 98 if (I == MachineBasicBlock::iterator(nullptr)) 99 Tracking = false; 100 MBBI = I; 101 } 102 getCurrentPosition()103 MachineBasicBlock::iterator getCurrentPosition() const { return MBBI; } 104 105 /// Return if a specific register is currently used. 106 bool isRegUsed(unsigned Reg, bool includeReserved = true) const; 107 108 /// Return all available registers in the register class in Mask. 109 BitVector getRegsAvailable(const TargetRegisterClass *RC); 110 111 /// Find an unused register of the specified register class. 112 /// Return 0 if none is found. 113 unsigned FindUnusedReg(const TargetRegisterClass *RegClass) const; 114 115 /// Add a scavenging frame index. addScavengingFrameIndex(int FI)116 void addScavengingFrameIndex(int FI) { 117 Scavenged.push_back(ScavengedInfo(FI)); 118 } 119 120 /// Query whether a frame index is a scavenging frame index. isScavengingFrameIndex(int FI)121 bool isScavengingFrameIndex(int FI) const { 122 for (SmallVectorImpl<ScavengedInfo>::const_iterator I = Scavenged.begin(), 123 IE = Scavenged.end(); I != IE; ++I) 124 if (I->FrameIndex == FI) 125 return true; 126 127 return false; 128 } 129 130 /// Get an array of scavenging frame indices. getScavengingFrameIndices(SmallVectorImpl<int> & A)131 void getScavengingFrameIndices(SmallVectorImpl<int> &A) const { 132 for (SmallVectorImpl<ScavengedInfo>::const_iterator I = Scavenged.begin(), 133 IE = Scavenged.end(); I != IE; ++I) 134 if (I->FrameIndex >= 0) 135 A.push_back(I->FrameIndex); 136 } 137 138 /// Make a register of the specific register class 139 /// available and do the appropriate bookkeeping. SPAdj is the stack 140 /// adjustment due to call frame, it's passed along to eliminateFrameIndex(). 141 /// Returns the scavenged register. 142 unsigned scavengeRegister(const TargetRegisterClass *RegClass, 143 MachineBasicBlock::iterator I, int SPAdj); scavengeRegister(const TargetRegisterClass * RegClass,int SPAdj)144 unsigned scavengeRegister(const TargetRegisterClass *RegClass, int SPAdj) { 145 return scavengeRegister(RegClass, MBBI, SPAdj); 146 } 147 148 /// Tell the scavenger a register is used. 149 void setRegUsed(unsigned Reg, LaneBitmask LaneMask = ~0u); 150 private: 151 /// Returns true if a register is reserved. It is never "unused". isReserved(unsigned Reg)152 bool isReserved(unsigned Reg) const { return MRI->isReserved(Reg); } 153 154 /// setUsed / setUnused - Mark the state of one or a number of register units. 155 /// setUsed(BitVector & RegUnits)156 void setUsed(BitVector &RegUnits) { 157 RegUnitsAvailable.reset(RegUnits); 158 } setUnused(BitVector & RegUnits)159 void setUnused(BitVector &RegUnits) { 160 RegUnitsAvailable |= RegUnits; 161 } 162 163 /// Processes the current instruction and fill the KillRegUnits and 164 /// DefRegUnits bit vectors. 165 void determineKillsAndDefs(); 166 167 /// Add all Reg Units that Reg contains to BV. 168 void addRegUnits(BitVector &BV, unsigned Reg); 169 170 /// Return the candidate register that is unused for the longest after 171 /// StartMI. UseMI is set to the instruction where the search stopped. 172 /// 173 /// No more than InstrLimit instructions are inspected. 174 unsigned findSurvivorReg(MachineBasicBlock::iterator StartMI, 175 BitVector &Candidates, 176 unsigned InstrLimit, 177 MachineBasicBlock::iterator &UseMI); 178 179 /// Allow resetting register state info for multiple 180 /// passes over/within the same function. 181 void initRegState(); 182 }; 183 184 } // End llvm namespace 185 186 #endif 187