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
|
//===-- SimpleRegisterCoalescing.h - Register Coalescing --------*- C++ -*-===//
//
// The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file implements a simple register copy coalescing phase.
//
//===----------------------------------------------------------------------===//
#ifndef LLVM_CODEGEN_SIMPLE_REGISTER_COALESCING_H
#define LLVM_CODEGEN_SIMPLE_REGISTER_COALESCING_H
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/LiveInterval.h"
#include "llvm/CodeGen/LiveIntervalAnalysis.h"
#include "llvm/CodeGen/RegisterCoalescer.h"
#include "llvm/ADT/BitVector.h"
#include "llvm/ADT/IndexedMap.h"
#include <queue>
namespace llvm {
class SimpleRegisterCoalescing;
class LiveVariables;
class MRegisterInfo;
class TargetInstrInfo;
class VirtRegMap;
class MachineLoopInfo;
/// CopyRec - Representation for copy instructions in coalescer queue.
///
struct CopyRec {
MachineInstr *MI;
unsigned SrcReg, DstReg;
unsigned LoopDepth;
bool isBackEdge;
CopyRec(MachineInstr *mi, unsigned src, unsigned dst, unsigned depth,
bool be)
: MI(mi), SrcReg(src), DstReg(dst), LoopDepth(depth), isBackEdge(be) {};
};
template<class SF> class JoinPriorityQueue;
/// CopyRecSort - Sorting function for coalescer queue.
///
struct CopyRecSort : public std::binary_function<CopyRec,CopyRec,bool> {
JoinPriorityQueue<CopyRecSort> *JPQ;
explicit CopyRecSort(JoinPriorityQueue<CopyRecSort> *jpq) : JPQ(jpq) {}
CopyRecSort(const CopyRecSort &RHS) : JPQ(RHS.JPQ) {}
bool operator()(CopyRec left, CopyRec right) const;
};
/// JoinQueue - A priority queue of copy instructions the coalescer is
/// going to process.
template<class SF>
class JoinPriorityQueue {
SimpleRegisterCoalescing *Rc;
std::priority_queue<CopyRec, std::vector<CopyRec>, SF> Queue;
public:
explicit JoinPriorityQueue(SimpleRegisterCoalescing *rc)
: Rc(rc), Queue(SF(this)) {}
bool empty() const { return Queue.empty(); }
void push(CopyRec R) { Queue.push(R); }
CopyRec pop() {
if (empty()) return CopyRec(0, 0, 0, 0, false);
CopyRec R = Queue.top();
Queue.pop();
return R;
}
// Callbacks to SimpleRegisterCoalescing.
unsigned getRepIntervalSize(unsigned Reg);
};
class SimpleRegisterCoalescing : public MachineFunctionPass,
public RegisterCoalescer {
MachineFunction* mf_;
const TargetMachine* tm_;
const MRegisterInfo* mri_;
const TargetInstrInfo* tii_;
LiveIntervals *li_;
LiveVariables *lv_;
const MachineLoopInfo* loopInfo;
BitVector allocatableRegs_;
DenseMap<const TargetRegisterClass*, BitVector> allocatableRCRegs_;
/// r2rMap_ - Map from register to its representative register.
///
IndexedMap<unsigned> r2rMap_;
/// r2rRevMap_ - Reverse of r2rRevMap_, i.e. Map from register to all
/// the registers it represent.
IndexedMap<std::vector<unsigned> > r2rRevMap_;
/// JoinQueue - A priority queue of copy instructions the coalescer is
/// going to process.
JoinPriorityQueue<CopyRecSort> *JoinQueue;
/// JoinedLIs - Keep track which register intervals have been coalesced
/// with other intervals.
BitVector JoinedLIs;
/// SubRegIdxes - Keep track of sub-register and indexes.
///
SmallVector<std::pair<unsigned, unsigned>, 32> SubRegIdxes;
/// JoinedCopies - Keep track of copies eliminated due to coalescing.
///
SmallPtrSet<MachineInstr*, 32> JoinedCopies;
public:
static char ID; // Pass identifcation, replacement for typeid
SimpleRegisterCoalescing() : MachineFunctionPass((intptr_t)&ID) {}
struct InstrSlots {
enum {
LOAD = 0,
USE = 1,
DEF = 2,
STORE = 3,
NUM = 4
};
};
virtual void getAnalysisUsage(AnalysisUsage &AU) const;
virtual void releaseMemory();
/// runOnMachineFunction - pass entry point
virtual bool runOnMachineFunction(MachineFunction&);
bool coalesceFunction(MachineFunction &mf, RegallocQuery &) {
// This runs as an independent pass, so don't do anything.
return false;
};
/// getRepIntervalSize - Called from join priority queue sorting function.
/// It returns the size of the interval that represent the given register.
unsigned getRepIntervalSize(unsigned Reg) {
Reg = rep(Reg);
if (!li_->hasInterval(Reg))
return 0;
return li_->getInterval(Reg).getSize();
}
/// print - Implement the dump method.
virtual void print(std::ostream &O, const Module* = 0) const;
void print(std::ostream *O, const Module* M = 0) const {
if (O) print(*O, M);
}
private:
/// joinIntervals - join compatible live intervals
void joinIntervals();
/// CopyCoalesceInMBB - Coalesce copies in the specified MBB, putting
/// copies that cannot yet be coalesced into the "TryAgain" list.
void CopyCoalesceInMBB(MachineBasicBlock *MBB,
std::vector<CopyRec> &TryAgain);
/// JoinCopy - Attempt to join intervals corresponding to SrcReg/DstReg,
/// which are the src/dst of the copy instruction CopyMI. This returns true
/// if the copy was successfully coalesced away. If it is not currently
/// possible to coalesce this interval, but it may be possible if other
/// things get coalesced, then it returns true by reference in 'Again'.
bool JoinCopy(CopyRec TheCopy, bool &Again);
/// JoinIntervals - Attempt to join these two intervals. On failure, this
/// returns false. Otherwise, if one of the intervals being joined is a
/// physreg, this method always canonicalizes DestInt to be it. The output
/// "SrcInt" will not have been modified, so we can use this information
/// below to update aliases.
bool JoinIntervals(LiveInterval &LHS, LiveInterval &RHS, bool &Swapped);
/// SimpleJoin - Attempt to join the specified interval into this one. The
/// caller of this method must guarantee that the RHS only contains a single
/// value number and that the RHS is not defined by a copy from this
/// interval. This returns false if the intervals are not joinable, or it
/// joins them and returns true.
bool SimpleJoin(LiveInterval &LHS, LiveInterval &RHS);
/// Return true if the two specified registers belong to different
/// register classes. The registers may be either phys or virt regs.
bool differingRegisterClasses(unsigned RegA, unsigned RegB) const;
bool AdjustCopiesBackFrom(LiveInterval &IntA, LiveInterval &IntB,
MachineInstr *CopyMI);
/// AddSubRegIdxPairs - Recursively mark all the registers represented by the
/// specified register as sub-registers. The recursion level is expected to be
/// shallow.
void AddSubRegIdxPairs(unsigned Reg, unsigned SubIdx);
/// isBackEdgeCopy - Returns true if CopyMI is a back edge copy.
///
bool isBackEdgeCopy(MachineInstr *CopyMI, unsigned DstReg);
/// lastRegisterUse - Returns the last use of the specific register between
/// cycles Start and End. It also returns the use operand by reference. It
/// returns NULL if there are no uses.
MachineInstr *lastRegisterUse(unsigned Start, unsigned End, unsigned Reg,
MachineOperand *&MOU);
/// findDefOperand - Returns the MachineOperand that is a def of the specific
/// register. It returns NULL if the def is not found.
MachineOperand *findDefOperand(MachineInstr *MI, unsigned Reg);
/// unsetRegisterKill - Unset IsKill property of all uses of the specific
/// register of the specific instruction.
void unsetRegisterKill(MachineInstr *MI, unsigned Reg);
/// unsetRegisterKills - Unset IsKill property of all uses of specific register
/// between cycles Start and End.
void unsetRegisterKills(unsigned Start, unsigned End, unsigned Reg);
/// hasRegisterDef - True if the instruction defines the specific register.
///
bool hasRegisterDef(MachineInstr *MI, unsigned Reg);
/// rep - returns the representative of this register
unsigned rep(unsigned Reg) {
unsigned Rep = r2rMap_[Reg];
if (Rep)
return r2rMap_[Reg] = rep(Rep);
return Reg;
}
void printRegName(unsigned reg) const;
};
} // End llvm namespace
#endif
|