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
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
|
//===-- llvm/CodeGen/MachineRegisterInfo.h ----------------------*- C++ -*-===//
//
// The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file defines the MachineRegisterInfo class.
//
//===----------------------------------------------------------------------===//
#ifndef LLVM_CODEGEN_MACHINEREGISTERINFO_H
#define LLVM_CODEGEN_MACHINEREGISTERINFO_H
#include "llvm/Target/TargetRegisterInfo.h"
#include "llvm/ADT/BitVector.h"
#include <vector>
namespace llvm {
/// MachineRegisterInfo - Keep track of information for virtual and physical
/// registers, including vreg register classes, use/def chains for registers,
/// etc.
class MachineRegisterInfo {
/// VRegInfo - Information we keep for each virtual register. The entries in
/// this vector are actually converted to vreg numbers by adding the
/// TargetRegisterInfo::FirstVirtualRegister delta to their index.
///
/// Each element in this list contains the register class of the vreg and the
/// start of the use/def list for the register.
std::vector<std::pair<const TargetRegisterClass*, MachineOperand*> > VRegInfo;
/// RegClassVRegMap - This vector acts as a map from TargetRegisterClass to
/// virtual registers. For each target register class, it keeps a list of
/// virtual registers belonging to the class.
std::vector<std::vector<unsigned> > RegClass2VRegMap;
/// RegAllocHints - This vector records register allocation hints for virtual
/// registers. For each virtual register, it keeps a register and hint type
/// pair making up the allocation hint. Hint type is target specific except
/// for the value 0 which means the second value of the pair is the preferred
/// register for allocation. For example, if the hint is <0, 1024>, it means
/// the allocator should prefer the physical register allocated to the virtual
/// register of the hint.
std::vector<std::pair<unsigned, unsigned> > RegAllocHints;
/// PhysRegUseDefLists - This is an array of the head of the use/def list for
/// physical registers.
MachineOperand **PhysRegUseDefLists;
/// UsedPhysRegs - This is a bit vector that is computed and set by the
/// register allocator, and must be kept up to date by passes that run after
/// register allocation (though most don't modify this). This is used
/// so that the code generator knows which callee save registers to save and
/// for other target specific uses.
BitVector UsedPhysRegs;
/// LiveIns/LiveOuts - Keep track of the physical registers that are
/// livein/liveout of the function. Live in values are typically arguments in
/// registers, live out values are typically return values in registers.
/// LiveIn values are allowed to have virtual registers associated with them,
/// stored in the second element.
std::vector<std::pair<unsigned, unsigned> > LiveIns;
std::vector<unsigned> LiveOuts;
MachineRegisterInfo(const MachineRegisterInfo&); // DO NOT IMPLEMENT
void operator=(const MachineRegisterInfo&); // DO NOT IMPLEMENT
public:
explicit MachineRegisterInfo(const TargetRegisterInfo &TRI);
~MachineRegisterInfo();
//===--------------------------------------------------------------------===//
// Register Info
//===--------------------------------------------------------------------===//
/// reg_begin/reg_end - Provide iteration support to walk over all definitions
/// and uses of a register within the MachineFunction that corresponds to this
/// MachineRegisterInfo object.
template<bool Uses, bool Defs, bool SkipDebug>
class defusechain_iterator;
/// reg_iterator/reg_begin/reg_end - Walk all defs and uses of the specified
/// register.
typedef defusechain_iterator<true,true,false> reg_iterator;
reg_iterator reg_begin(unsigned RegNo) const {
return reg_iterator(getRegUseDefListHead(RegNo));
}
static reg_iterator reg_end() { return reg_iterator(0); }
/// reg_empty - Return true if there are no instructions using or defining the
/// specified register (it may be live-in).
bool reg_empty(unsigned RegNo) const { return reg_begin(RegNo) == reg_end(); }
/// def_iterator/def_begin/def_end - Walk all defs of the specified register.
typedef defusechain_iterator<false,true,false> def_iterator;
def_iterator def_begin(unsigned RegNo) const {
return def_iterator(getRegUseDefListHead(RegNo));
}
static def_iterator def_end() { return def_iterator(0); }
/// def_empty - Return true if there are no instructions defining the
/// specified register (it may be live-in).
bool def_empty(unsigned RegNo) const { return def_begin(RegNo) == def_end(); }
/// use_iterator/use_begin/use_end - Walk all uses of the specified register.
typedef defusechain_iterator<true,false,false> use_iterator;
use_iterator use_begin(unsigned RegNo) const {
return use_iterator(getRegUseDefListHead(RegNo));
}
static use_iterator use_end() { return use_iterator(0); }
/// use_empty - Return true if there are no instructions using the specified
/// register.
bool use_empty(unsigned RegNo) const { return use_begin(RegNo) == use_end(); }
/// hasOneUse - Return true if there is exactly one instruction using the
/// specified register.
bool hasOneUse(unsigned RegNo) const;
/// use_nodbg_iterator/use_nodbg_begin/use_nodbg_end - Walk all uses of the
/// specified register, skipping those marked as Debug.
typedef defusechain_iterator<true,false,true> use_nodbg_iterator;
use_nodbg_iterator use_nodbg_begin(unsigned RegNo) const {
return use_nodbg_iterator(getRegUseDefListHead(RegNo));
}
static use_nodbg_iterator use_nodbg_end() { return use_nodbg_iterator(0); }
/// use_nodbg_empty - Return true if there are no non-Debug instructions
/// using the specified register.
bool use_nodbg_empty(unsigned RegNo) const {
return use_nodbg_begin(RegNo) == use_nodbg_end();
}
/// hasOneNonDBGUse - Return true if there is exactly one non-Debug
/// instruction using the specified register.
bool hasOneNonDBGUse(unsigned RegNo) const;
/// replaceRegWith - Replace all instances of FromReg with ToReg in the
/// machine function. This is like llvm-level X->replaceAllUsesWith(Y),
/// except that it also changes any definitions of the register as well.
void replaceRegWith(unsigned FromReg, unsigned ToReg);
/// getRegUseDefListHead - Return the head pointer for the register use/def
/// list for the specified virtual or physical register.
MachineOperand *&getRegUseDefListHead(unsigned RegNo) {
if (RegNo < TargetRegisterInfo::FirstVirtualRegister)
return PhysRegUseDefLists[RegNo];
RegNo -= TargetRegisterInfo::FirstVirtualRegister;
return VRegInfo[RegNo].second;
}
MachineOperand *getRegUseDefListHead(unsigned RegNo) const {
if (RegNo < TargetRegisterInfo::FirstVirtualRegister)
return PhysRegUseDefLists[RegNo];
RegNo -= TargetRegisterInfo::FirstVirtualRegister;
return VRegInfo[RegNo].second;
}
/// getVRegDef - Return the machine instr that defines the specified virtual
/// register or null if none is found. This assumes that the code is in SSA
/// form, so there should only be one definition.
MachineInstr *getVRegDef(unsigned Reg) const;
/// clearKillFlags - Iterate over all the uses of the given register and
/// clear the kill flag from the MachineOperand. This function is used by
/// optimization passes which extend register lifetimes and need only
/// preserve conservative kill flag information.
void clearKillFlags(unsigned Reg) const;
#ifndef NDEBUG
void dumpUses(unsigned RegNo) const;
#endif
//===--------------------------------------------------------------------===//
// Virtual Register Info
//===--------------------------------------------------------------------===//
/// getRegClass - Return the register class of the specified virtual register.
///
const TargetRegisterClass *getRegClass(unsigned Reg) const {
Reg -= TargetRegisterInfo::FirstVirtualRegister;
assert(Reg < VRegInfo.size() && "Invalid vreg!");
return VRegInfo[Reg].first;
}
/// setRegClass - Set the register class of the specified virtual register.
///
void setRegClass(unsigned Reg, const TargetRegisterClass *RC);
/// createVirtualRegister - Create and return a new virtual register in the
/// function with the specified register class.
///
unsigned createVirtualRegister(const TargetRegisterClass *RegClass);
/// getLastVirtReg - Return the highest currently assigned virtual register.
///
unsigned getLastVirtReg() const {
return (unsigned)VRegInfo.size()+TargetRegisterInfo::FirstVirtualRegister-1;
}
/// getRegClassVirtRegs - Return the list of virtual registers of the given
/// target register class.
std::vector<unsigned> &getRegClassVirtRegs(const TargetRegisterClass *RC) {
return RegClass2VRegMap[RC->getID()];
}
/// setRegAllocationHint - Specify a register allocation hint for the
/// specified virtual register.
void setRegAllocationHint(unsigned Reg, unsigned Type, unsigned PrefReg) {
Reg -= TargetRegisterInfo::FirstVirtualRegister;
assert(Reg < VRegInfo.size() && "Invalid vreg!");
RegAllocHints[Reg].first = Type;
RegAllocHints[Reg].second = PrefReg;
}
/// getRegAllocationHint - Return the register allocation hint for the
/// specified virtual register.
std::pair<unsigned, unsigned>
getRegAllocationHint(unsigned Reg) const {
Reg -= TargetRegisterInfo::FirstVirtualRegister;
assert(Reg < VRegInfo.size() && "Invalid vreg!");
return RegAllocHints[Reg];
}
//===--------------------------------------------------------------------===//
// Physical Register Use Info
//===--------------------------------------------------------------------===//
/// isPhysRegUsed - Return true if the specified register is used in this
/// function. This only works after register allocation.
bool isPhysRegUsed(unsigned Reg) const { return UsedPhysRegs[Reg]; }
/// setPhysRegUsed - Mark the specified register used in this function.
/// This should only be called during and after register allocation.
void setPhysRegUsed(unsigned Reg) { UsedPhysRegs[Reg] = true; }
/// addPhysRegsUsed - Mark the specified registers used in this function.
/// This should only be called during and after register allocation.
void addPhysRegsUsed(const BitVector &Regs) { UsedPhysRegs |= Regs; }
/// setPhysRegUnused - Mark the specified register unused in this function.
/// This should only be called during and after register allocation.
void setPhysRegUnused(unsigned Reg) { UsedPhysRegs[Reg] = false; }
/// closePhysRegsUsed - Expand UsedPhysRegs to its transitive closure over
/// subregisters. That means that if R is used, so are all subregisters.
void closePhysRegsUsed(const TargetRegisterInfo&);
//===--------------------------------------------------------------------===//
// LiveIn/LiveOut Management
//===--------------------------------------------------------------------===//
/// addLiveIn/Out - Add the specified register as a live in/out. Note that it
/// is an error to add the same register to the same set more than once.
void addLiveIn(unsigned Reg, unsigned vreg = 0) {
LiveIns.push_back(std::make_pair(Reg, vreg));
}
void addLiveOut(unsigned Reg) { LiveOuts.push_back(Reg); }
// Iteration support for live in/out sets. These sets are kept in sorted
// order by their register number.
typedef std::vector<std::pair<unsigned,unsigned> >::const_iterator
livein_iterator;
typedef std::vector<unsigned>::const_iterator liveout_iterator;
livein_iterator livein_begin() const { return LiveIns.begin(); }
livein_iterator livein_end() const { return LiveIns.end(); }
bool livein_empty() const { return LiveIns.empty(); }
liveout_iterator liveout_begin() const { return LiveOuts.begin(); }
liveout_iterator liveout_end() const { return LiveOuts.end(); }
bool liveout_empty() const { return LiveOuts.empty(); }
bool isLiveIn(unsigned Reg) const;
bool isLiveOut(unsigned Reg) const;
/// getLiveInPhysReg - If VReg is a live-in virtual register, return the
/// corresponding live-in physical register.
unsigned getLiveInPhysReg(unsigned VReg) const;
/// EmitLiveInCopies - Emit copies to initialize livein virtual registers
/// into the given entry block.
void EmitLiveInCopies(MachineBasicBlock *EntryMBB,
const TargetRegisterInfo &TRI,
const TargetInstrInfo &TII);
private:
void HandleVRegListReallocation();
public:
/// defusechain_iterator - This class provides iterator support for machine
/// operands in the function that use or define a specific register. If
/// ReturnUses is true it returns uses of registers, if ReturnDefs is true it
/// returns defs. If neither are true then you are silly and it always
/// returns end(). If SkipDebug is true it skips uses marked Debug
/// when incrementing.
template<bool ReturnUses, bool ReturnDefs, bool SkipDebug>
class defusechain_iterator
: public std::iterator<std::forward_iterator_tag, MachineInstr, ptrdiff_t> {
MachineOperand *Op;
explicit defusechain_iterator(MachineOperand *op) : Op(op) {
// If the first node isn't one we're interested in, advance to one that
// we are interested in.
if (op) {
if ((!ReturnUses && op->isUse()) ||
(!ReturnDefs && op->isDef()) ||
(SkipDebug && op->isDebug()))
++*this;
}
}
friend class MachineRegisterInfo;
public:
typedef std::iterator<std::forward_iterator_tag,
MachineInstr, ptrdiff_t>::reference reference;
typedef std::iterator<std::forward_iterator_tag,
MachineInstr, ptrdiff_t>::pointer pointer;
defusechain_iterator(const defusechain_iterator &I) : Op(I.Op) {}
defusechain_iterator() : Op(0) {}
bool operator==(const defusechain_iterator &x) const {
return Op == x.Op;
}
bool operator!=(const defusechain_iterator &x) const {
return !operator==(x);
}
/// atEnd - return true if this iterator is equal to reg_end() on the value.
bool atEnd() const { return Op == 0; }
// Iterator traversal: forward iteration only
defusechain_iterator &operator++() { // Preincrement
assert(Op && "Cannot increment end iterator!");
Op = Op->getNextOperandForReg();
// If this is an operand we don't care about, skip it.
while (Op && ((!ReturnUses && Op->isUse()) ||
(!ReturnDefs && Op->isDef()) ||
(SkipDebug && Op->isDebug())))
Op = Op->getNextOperandForReg();
return *this;
}
defusechain_iterator operator++(int) { // Postincrement
defusechain_iterator tmp = *this; ++*this; return tmp;
}
MachineOperand &getOperand() const {
assert(Op && "Cannot dereference end iterator!");
return *Op;
}
/// getOperandNo - Return the operand # of this MachineOperand in its
/// MachineInstr.
unsigned getOperandNo() const {
assert(Op && "Cannot dereference end iterator!");
return Op - &Op->getParent()->getOperand(0);
}
// Retrieve a reference to the current operand.
MachineInstr &operator*() const {
assert(Op && "Cannot dereference end iterator!");
return *Op->getParent();
}
MachineInstr *operator->() const {
assert(Op && "Cannot dereference end iterator!");
return Op->getParent();
}
};
};
} // End llvm namespace
#endif
|