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 {
FrameIndexScavengedInfo45     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:
RegScavenger()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.
forward(MachineBasicBlock::iterator I)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.
unprocess(MachineBasicBlock::iterator I)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.
skipTo(MachineBasicBlock::iterator I)103   void skipTo(MachineBasicBlock::iterator I) {
104     if (I == MachineBasicBlock::iterator(nullptr))
105       Tracking = false;
106     MBBI = I;
107   }
108 
getCurrentPosition()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.
addScavengingFrameIndex(int FI)125   void addScavengingFrameIndex(int FI) {
126     Scavenged.push_back(ScavengedInfo(FI));
127   }
128 
129   /// Query whether a frame index is a scavenging frame index.
isScavengingFrameIndex(int FI)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.
getScavengingFrameIndices(SmallVectorImpl<int> & A)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);
scavengeRegister(const TargetRegisterClass * RegClass,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".
isReserved(unsigned Reg)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   ///
setUsed(BitVector & RegUnits)166   void setUsed(BitVector &RegUnits) {
167     RegUnitsAvailable.reset(RegUnits);
168   }
setUnused(BitVector & RegUnits)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