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