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 availbale 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 /// Tracking - True if RegScavenger is currently tracking the liveness of 40 /// registers. 41 bool Tracking; 42 43 /// Information on scavenged registers (held in a spill slot). 44 struct ScavengedInfo { 45 ScavengedInfo(int FI = -1) : FrameIndex(FI), Reg(0), Restore(nullptr) {} 46 47 /// A spill slot used for scavenging a register post register allocation. 48 int FrameIndex; 49 50 /// If non-zero, the specific register is currently being 51 /// scavenged. That is, it is spilled to this scavenging stack slot. 52 unsigned Reg; 53 54 /// The instruction that restores the scavenged register from stack. 55 const MachineInstr *Restore; 56 }; 57 58 /// A vector of information on scavenged registers. 59 SmallVector<ScavengedInfo, 2> Scavenged; 60 61 /// RegUnitsAvailable - The current state of each reg unit immediatelly 62 /// before MBBI. One bit per register unit. If bit is not set it means any 63 /// register containing that register unit is currently being used. 64 BitVector RegUnitsAvailable; 65 66 // These BitVectors are only used internally to forward(). They are members 67 // to avoid frequent reallocations. 68 BitVector KillRegUnits, DefRegUnits; 69 BitVector TmpRegUnits; 70 71 public: 72 RegScavenger() 73 : MBB(nullptr), NumRegUnits(0), Tracking(false) {} 74 75 /// enterBasicBlock - Start tracking liveness from the begin of the specific 76 /// basic block. 77 void enterBasicBlock(MachineBasicBlock *mbb); 78 79 /// initRegState - allow resetting register state info for multiple 80 /// passes over/within the same function. 81 void initRegState(); 82 83 /// forward - Move the internal MBB iterator and update register states. 84 void forward(); 85 86 /// forward - Move the internal MBB iterator and update register states until 87 /// it has processed the specific iterator. 88 void forward(MachineBasicBlock::iterator I) { 89 if (!Tracking && MBB->begin() != I) forward(); 90 while (MBBI != I) forward(); 91 } 92 93 /// Invert the behavior of forward() on the current instruction (undo the 94 /// changes to the available registers made by forward()). 95 void unprocess(); 96 97 /// Unprocess instructions until you reach the provided iterator. 98 void unprocess(MachineBasicBlock::iterator I) { 99 while (MBBI != I) unprocess(); 100 } 101 102 /// skipTo - Move the internal MBB iterator but do not update register states. 103 void skipTo(MachineBasicBlock::iterator I) { 104 if (I == MachineBasicBlock::iterator(nullptr)) 105 Tracking = false; 106 MBBI = I; 107 } 108 109 MachineBasicBlock::iterator getCurrentPosition() const { 110 return MBBI; 111 } 112 113 /// isRegUsed - return if a specific register is currently used. 114 bool isRegUsed(unsigned Reg, bool includeReserved = true) const; 115 116 /// getRegsAvailable - Return all available registers in the register class 117 /// in Mask. 118 BitVector getRegsAvailable(const TargetRegisterClass *RC); 119 120 /// FindUnusedReg - Find a unused register of the specified register class. 121 /// Return 0 if none is found. 122 unsigned FindUnusedReg(const TargetRegisterClass *RegClass) const; 123 124 /// Add a scavenging frame index. 125 void addScavengingFrameIndex(int FI) { 126 Scavenged.push_back(ScavengedInfo(FI)); 127 } 128 129 /// Query whether a frame index is a scavenging frame index. 130 bool isScavengingFrameIndex(int FI) const { 131 for (SmallVectorImpl<ScavengedInfo>::const_iterator I = Scavenged.begin(), 132 IE = Scavenged.end(); I != IE; ++I) 133 if (I->FrameIndex == FI) 134 return true; 135 136 return false; 137 } 138 139 /// Get an array of scavenging frame indices. 140 void getScavengingFrameIndices(SmallVectorImpl<int> &A) const { 141 for (SmallVectorImpl<ScavengedInfo>::const_iterator I = Scavenged.begin(), 142 IE = Scavenged.end(); I != IE; ++I) 143 if (I->FrameIndex >= 0) 144 A.push_back(I->FrameIndex); 145 } 146 147 /// scavengeRegister - Make a register of the specific register class 148 /// available and do the appropriate bookkeeping. SPAdj is the stack 149 /// adjustment due to call frame, it's passed along to eliminateFrameIndex(). 150 /// Returns the scavenged register. 151 unsigned scavengeRegister(const TargetRegisterClass *RegClass, 152 MachineBasicBlock::iterator I, int SPAdj); 153 unsigned scavengeRegister(const TargetRegisterClass *RegClass, int SPAdj) { 154 return scavengeRegister(RegClass, MBBI, SPAdj); 155 } 156 157 /// setRegUsed - Tell the scavenger a register is used. 158 /// 159 void setRegUsed(unsigned Reg); 160 private: 161 /// isReserved - Returns true if a register is reserved. It is never "unused". 162 bool isReserved(unsigned Reg) const { return MRI->isReserved(Reg); } 163 164 /// setUsed / setUnused - Mark the state of one or a number of register units. 165 /// 166 void setUsed(BitVector &RegUnits) { 167 RegUnitsAvailable.reset(RegUnits); 168 } 169 void setUnused(BitVector &RegUnits) { 170 RegUnitsAvailable |= RegUnits; 171 } 172 173 /// Processes the current instruction and fill the KillRegUnits and 174 /// DefRegUnits bit vectors. 175 void determineKillsAndDefs(); 176 177 /// Add all Reg Units that Reg contains to BV. 178 void addRegUnits(BitVector &BV, unsigned Reg); 179 180 /// findSurvivorReg - Return the candidate register that is unused for the 181 /// longest after StartMI. UseMI is set to the instruction where the search 182 /// stopped. 183 /// 184 /// No more than InstrLimit instructions are inspected. 185 unsigned findSurvivorReg(MachineBasicBlock::iterator StartMI, 186 BitVector &Candidates, 187 unsigned InstrLimit, 188 MachineBasicBlock::iterator &UseMI); 189 190 }; 191 192 } // End llvm namespace 193 194 #endif 195
