Line data Source code
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 : /// \file
11 : /// This file declares the machine register scavenger class. It can provide
12 : /// information such as unused register at any point in a machine basic block.
13 : /// It also provides a mechanism to make registers available by evicting them
14 : /// to spill slots.
15 : //
16 : //===----------------------------------------------------------------------===//
17 :
18 : #ifndef LLVM_CODEGEN_REGISTERSCAVENGING_H
19 : #define LLVM_CODEGEN_REGISTERSCAVENGING_H
20 :
21 : #include "llvm/ADT/BitVector.h"
22 : #include "llvm/ADT/SmallVector.h"
23 : #include "llvm/CodeGen/LiveRegUnits.h"
24 : #include "llvm/CodeGen/MachineBasicBlock.h"
25 : #include "llvm/CodeGen/MachineRegisterInfo.h"
26 : #include "llvm/MC/LaneBitmask.h"
27 :
28 : namespace llvm {
29 :
30 : class MachineInstr;
31 : class TargetInstrInfo;
32 : class TargetRegisterClass;
33 : class TargetRegisterInfo;
34 :
35 : class RegScavenger {
36 : const TargetRegisterInfo *TRI;
37 : const TargetInstrInfo *TII;
38 : MachineRegisterInfo* MRI;
39 : MachineBasicBlock *MBB = nullptr;
40 : MachineBasicBlock::iterator MBBI;
41 : unsigned NumRegUnits = 0;
42 :
43 : /// True if RegScavenger is currently tracking the liveness of registers.
44 : bool Tracking = false;
45 :
46 : /// Information on scavenged registers (held in a spill slot).
47 : struct ScavengedInfo {
48 1301 : ScavengedInfo(int FI = -1) : FrameIndex(FI) {}
49 :
50 : /// A spill slot used for scavenging a register post register allocation.
51 : int FrameIndex;
52 :
53 : /// If non-zero, the specific register is currently being
54 : /// scavenged. That is, it is spilled to this scavenging stack slot.
55 : unsigned Reg = 0;
56 :
57 : /// The instruction that restores the scavenged register from stack.
58 : const MachineInstr *Restore = nullptr;
59 : };
60 :
61 : /// A vector of information on scavenged registers.
62 : SmallVector<ScavengedInfo, 2> Scavenged;
63 :
64 : LiveRegUnits LiveUnits;
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 38536 : RegScavenger() = default;
73 :
74 : /// Start tracking liveness from the begin of basic block \p MBB.
75 : void enterBasicBlock(MachineBasicBlock &MBB);
76 :
77 : /// Start tracking liveness from the end of basic block \p MBB.
78 : /// Use backward() to move towards the beginning of the block. This is
79 : /// preferred to enterBasicBlock() and forward() because it does not depend
80 : /// on the presence of kill flags.
81 : void enterBasicBlockEnd(MachineBasicBlock &MBB);
82 :
83 : /// Move the internal MBB iterator and update register states.
84 : void forward();
85 :
86 : /// Move the internal MBB iterator and update register states until
87 : /// it has processed the specific iterator.
88 4992 : void forward(MachineBasicBlock::iterator I) {
89 4992 : if (!Tracking && MBB->begin() != I) forward();
90 10323 : while (MBBI != I) forward();
91 4992 : }
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 : /// Update internal register state and move MBB iterator backwards.
103 : /// Contrary to unprocess() this method gives precise results even in the
104 : /// absence of kill flags.
105 : void backward();
106 :
107 : /// Call backward() as long as the internal iterator does not point to \p I.
108 : void backward(MachineBasicBlock::iterator I) {
109 80564 : while (MBBI != I)
110 39527 : backward();
111 : }
112 :
113 : /// Move the internal MBB iterator but do not update register states.
114 : void skipTo(MachineBasicBlock::iterator I) {
115 : if (I == MachineBasicBlock::iterator(nullptr))
116 : Tracking = false;
117 : MBBI = I;
118 : }
119 :
120 : MachineBasicBlock::iterator getCurrentPosition() const { return MBBI; }
121 :
122 : /// Return if a specific register is currently used.
123 : bool isRegUsed(unsigned Reg, bool includeReserved = true) const;
124 :
125 : /// Return all available registers in the register class in Mask.
126 : BitVector getRegsAvailable(const TargetRegisterClass *RC);
127 :
128 : /// Find an unused register of the specified register class.
129 : /// Return 0 if none is found.
130 : unsigned FindUnusedReg(const TargetRegisterClass *RC) const;
131 :
132 : /// Add a scavenging frame index.
133 : void addScavengingFrameIndex(int FI) {
134 1185 : Scavenged.push_back(ScavengedInfo(FI));
135 : }
136 :
137 : /// Query whether a frame index is a scavenging frame index.
138 : bool isScavengingFrameIndex(int FI) const {
139 4213 : for (SmallVectorImpl<ScavengedInfo>::const_iterator I = Scavenged.begin(),
140 22807 : IE = Scavenged.end(); I != IE; ++I)
141 4774 : if (I->FrameIndex == FI)
142 : return true;
143 :
144 : return false;
145 : }
146 :
147 : /// Get an array of scavenging frame indices.
148 66332 : void getScavengingFrameIndices(SmallVectorImpl<int> &A) const {
149 1294 : for (SmallVectorImpl<ScavengedInfo>::const_iterator I = Scavenged.begin(),
150 67626 : IE = Scavenged.end(); I != IE; ++I)
151 1294 : if (I->FrameIndex >= 0)
152 553 : A.push_back(I->FrameIndex);
153 66332 : }
154 :
155 : /// Make a register of the specific register class
156 : /// available and do the appropriate bookkeeping. SPAdj is the stack
157 : /// adjustment due to call frame, it's passed along to eliminateFrameIndex().
158 : /// Returns the scavenged register.
159 : /// This is deprecated as it depends on the quality of the kill flags being
160 : /// present; Use scavengeRegisterBackwards() instead!
161 : unsigned scavengeRegister(const TargetRegisterClass *RC,
162 : MachineBasicBlock::iterator I, int SPAdj);
163 : unsigned scavengeRegister(const TargetRegisterClass *RegClass, int SPAdj) {
164 0 : return scavengeRegister(RegClass, MBBI, SPAdj);
165 : }
166 :
167 : /// Make a register of the specific register class available from the current
168 : /// position backwards to the place before \p To. If \p RestoreAfter is true
169 : /// this includes the instruction following the current position.
170 : /// SPAdj is the stack adjustment due to call frame, it's passed along to
171 : /// eliminateFrameIndex().
172 : /// Returns the scavenged register.
173 : unsigned scavengeRegisterBackwards(const TargetRegisterClass &RC,
174 : MachineBasicBlock::iterator To,
175 : bool RestoreAfter, int SPAdj);
176 :
177 : /// Tell the scavenger a register is used.
178 : void setRegUsed(unsigned Reg, LaneBitmask LaneMask = LaneBitmask::getAll());
179 :
180 : private:
181 : /// Returns true if a register is reserved. It is never "unused".
182 0 : bool isReserved(unsigned Reg) const { return MRI->isReserved(Reg); }
183 :
184 : /// setUsed / setUnused - Mark the state of one or a number of register units.
185 : ///
186 : void setUsed(const BitVector &RegUnits) {
187 : LiveUnits.addUnits(RegUnits);
188 : }
189 : void setUnused(const BitVector &RegUnits) {
190 : LiveUnits.removeUnits(RegUnits);
191 : }
192 :
193 : /// Processes the current instruction and fill the KillRegUnits and
194 : /// DefRegUnits bit vectors.
195 : void determineKillsAndDefs();
196 :
197 : /// Add all Reg Units that Reg contains to BV.
198 : void addRegUnits(BitVector &BV, unsigned Reg);
199 :
200 : /// Remove all Reg Units that \p Reg contains from \p BV.
201 : void removeRegUnits(BitVector &BV, unsigned Reg);
202 :
203 : /// Return the candidate register that is unused for the longest after
204 : /// StartMI. UseMI is set to the instruction where the search stopped.
205 : ///
206 : /// No more than InstrLimit instructions are inspected.
207 : unsigned findSurvivorReg(MachineBasicBlock::iterator StartMI,
208 : BitVector &Candidates,
209 : unsigned InstrLimit,
210 : MachineBasicBlock::iterator &UseMI);
211 :
212 : /// Initialize RegisterScavenger.
213 : void init(MachineBasicBlock &MBB);
214 :
215 : /// Mark live-in registers of basic block as used.
216 : void setLiveInsUsed(const MachineBasicBlock &MBB);
217 :
218 : /// Spill a register after position \p After and reload it before position
219 : /// \p UseMI.
220 : ScavengedInfo &spill(unsigned Reg, const TargetRegisterClass &RC, int SPAdj,
221 : MachineBasicBlock::iterator Before,
222 : MachineBasicBlock::iterator &UseMI);
223 : };
224 :
225 : /// Replaces all frame index virtual registers with physical registers. Uses the
226 : /// register scavenger to find an appropriate register to use.
227 : void scavengeFrameVirtualRegs(MachineFunction &MF, RegScavenger &RS);
228 :
229 : } // end namespace llvm
230 :
231 : #endif // LLVM_CODEGEN_REGISTERSCAVENGING_H
|
