0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1 //===- MachineCopyPropagation.cpp - Machine Copy Propagation Pass ---------===//
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2 //
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
3 // The LLVM Compiler Infrastructure
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
4 //
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
5 // This file is distributed under the University of Illinois Open Source
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
6 // License. See LICENSE.TXT for details.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
7 //
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
8 //===----------------------------------------------------------------------===//
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
9 //
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
10 // This is an extremely simple MachineInstr-level copy propagation pass.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
11 //
|
|
134
|
12 // This pass forwards the source of COPYs to the users of their destinations
|
|
|
13 // when doing so is legal. For example:
|
|
|
14 //
|
|
|
15 // %reg1 = COPY %reg0
|
|
|
16 // ...
|
|
|
17 // ... = OP %reg1
|
|
|
18 //
|
|
|
19 // If
|
|
|
20 // - %reg0 has not been clobbered by the time of the use of %reg1
|
|
|
21 // - the register class constraints are satisfied
|
|
|
22 // - the COPY def is the only value that reaches OP
|
|
|
23 // then this pass replaces the above with:
|
|
|
24 //
|
|
|
25 // %reg1 = COPY %reg0
|
|
|
26 // ...
|
|
|
27 // ... = OP %reg0
|
|
|
28 //
|
|
|
29 // This pass also removes some redundant COPYs. For example:
|
|
|
30 //
|
|
|
31 // %R1 = COPY %R0
|
|
|
32 // ... // No clobber of %R1
|
|
|
33 // %R0 = COPY %R1 <<< Removed
|
|
|
34 //
|
|
|
35 // or
|
|
|
36 //
|
|
|
37 // %R1 = COPY %R0
|
|
|
38 // ... // No clobber of %R0
|
|
|
39 // %R1 = COPY %R0 <<< Removed
|
|
|
40 //
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
41 //===----------------------------------------------------------------------===//
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
42
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
43 #include "llvm/ADT/DenseMap.h"
|
|
121
|
44 #include "llvm/ADT/STLExtras.h"
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
45 #include "llvm/ADT/SetVector.h"
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
46 #include "llvm/ADT/SmallVector.h"
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
47 #include "llvm/ADT/Statistic.h"
|
|
121
|
48 #include "llvm/ADT/iterator_range.h"
|
|
|
49 #include "llvm/CodeGen/MachineBasicBlock.h"
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
50 #include "llvm/CodeGen/MachineFunction.h"
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
51 #include "llvm/CodeGen/MachineFunctionPass.h"
|
|
121
|
52 #include "llvm/CodeGen/MachineInstr.h"
|
|
|
53 #include "llvm/CodeGen/MachineOperand.h"
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
54 #include "llvm/CodeGen/MachineRegisterInfo.h"
|
|
134
|
55 #include "llvm/CodeGen/TargetInstrInfo.h"
|
|
|
56 #include "llvm/CodeGen/TargetRegisterInfo.h"
|
|
|
57 #include "llvm/CodeGen/TargetSubtargetInfo.h"
|
|
121
|
58 #include "llvm/MC/MCRegisterInfo.h"
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
59 #include "llvm/Pass.h"
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
60 #include "llvm/Support/Debug.h"
|
|
134
|
61 #include "llvm/Support/DebugCounter.h"
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
62 #include "llvm/Support/raw_ostream.h"
|
|
121
|
63 #include <cassert>
|
|
|
64 #include <iterator>
|
|
|
65
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
66 using namespace llvm;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
67
|
|
121
|
68 #define DEBUG_TYPE "machine-cp"
|
|
77
|
69
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
70 STATISTIC(NumDeletes, "Number of dead copies deleted");
|
|
134
|
71 STATISTIC(NumCopyForwards, "Number of copy uses forwarded");
|
|
|
72 DEBUG_COUNTER(FwdCounter, "machine-cp-fwd",
|
|
|
73 "Controls which register COPYs are forwarded");
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
74
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
75 namespace {
|
|
121
|
76
|
|
|
77 using RegList = SmallVector<unsigned, 4>;
|
|
|
78 using SourceMap = DenseMap<unsigned, RegList>;
|
|
|
79 using Reg2MIMap = DenseMap<unsigned, MachineInstr *>;
|
|
120
|
80
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
81 class MachineCopyPropagation : public MachineFunctionPass {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
82 const TargetRegisterInfo *TRI;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
83 const TargetInstrInfo *TII;
|
|
120
|
84 const MachineRegisterInfo *MRI;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
85
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
86 public:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
87 static char ID; // Pass identification, replacement for typeid
|
|
121
|
88
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
89 MachineCopyPropagation() : MachineFunctionPass(ID) {
|
|
120
|
90 initializeMachineCopyPropagationPass(*PassRegistry::getPassRegistry());
|
|
|
91 }
|
|
|
92
|
|
|
93 void getAnalysisUsage(AnalysisUsage &AU) const override {
|
|
|
94 AU.setPreservesCFG();
|
|
|
95 MachineFunctionPass::getAnalysisUsage(AU);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
96 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
97
|
|
77
|
98 bool runOnMachineFunction(MachineFunction &MF) override;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
99
|
|
120
|
100 MachineFunctionProperties getRequiredProperties() const override {
|
|
|
101 return MachineFunctionProperties().set(
|
|
|
102 MachineFunctionProperties::Property::NoVRegs);
|
|
|
103 }
|
|
|
104
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
105 private:
|
|
120
|
106 void ClobberRegister(unsigned Reg);
|
|
121
|
107 void ReadRegister(unsigned Reg);
|
|
120
|
108 void CopyPropagateBlock(MachineBasicBlock &MBB);
|
|
|
109 bool eraseIfRedundant(MachineInstr &Copy, unsigned Src, unsigned Def);
|
|
134
|
110 void forwardUses(MachineInstr &MI);
|
|
|
111 bool isForwardableRegClassCopy(const MachineInstr &Copy,
|
|
|
112 const MachineInstr &UseI, unsigned UseIdx);
|
|
|
113 bool hasImplicitOverlap(const MachineInstr &MI, const MachineOperand &Use);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
114
|
|
120
|
115 /// Candidates for deletion.
|
|
|
116 SmallSetVector<MachineInstr*, 8> MaybeDeadCopies;
|
|
121
|
117
|
|
120
|
118 /// Def -> available copies map.
|
|
|
119 Reg2MIMap AvailCopyMap;
|
|
121
|
120
|
|
120
|
121 /// Def -> copies map.
|
|
|
122 Reg2MIMap CopyMap;
|
|
121
|
123
|
|
120
|
124 /// Src -> Def map
|
|
|
125 SourceMap SrcMap;
|
|
121
|
126
|
|
120
|
127 bool Changed;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
128 };
|
|
121
|
129
|
|
|
130 } // end anonymous namespace
|
|
|
131
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
132 char MachineCopyPropagation::ID = 0;
|
|
121
|
133
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
134 char &llvm::MachineCopyPropagationID = MachineCopyPropagation::ID;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
135
|
|
121
|
136 INITIALIZE_PASS(MachineCopyPropagation, DEBUG_TYPE,
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
137 "Machine Copy Propagation Pass", false, false)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
138
|
|
120
|
139 /// Remove any entry in \p Map where the register is a subregister or equal to
|
|
|
140 /// a register contained in \p Regs.
|
|
|
141 static void removeRegsFromMap(Reg2MIMap &Map, const RegList &Regs,
|
|
|
142 const TargetRegisterInfo &TRI) {
|
|
|
143 for (unsigned Reg : Regs) {
|
|
|
144 // Source of copy is no longer available for propagation.
|
|
|
145 for (MCSubRegIterator SR(Reg, &TRI, true); SR.isValid(); ++SR)
|
|
|
146 Map.erase(*SR);
|
|
|
147 }
|
|
|
148 }
|
|
|
149
|
|
|
150 /// Remove any entry in \p Map that is marked clobbered in \p RegMask.
|
|
|
151 /// The map will typically have a lot fewer entries than the regmask clobbers,
|
|
|
152 /// so this is more efficient than iterating the clobbered registers and calling
|
|
|
153 /// ClobberRegister() on them.
|
|
|
154 static void removeClobberedRegsFromMap(Reg2MIMap &Map,
|
|
|
155 const MachineOperand &RegMask) {
|
|
|
156 for (Reg2MIMap::iterator I = Map.begin(), E = Map.end(), Next; I != E;
|
|
|
157 I = Next) {
|
|
|
158 Next = std::next(I);
|
|
|
159 unsigned Reg = I->first;
|
|
|
160 if (RegMask.clobbersPhysReg(Reg))
|
|
|
161 Map.erase(I);
|
|
|
162 }
|
|
|
163 }
|
|
|
164
|
|
|
165 void MachineCopyPropagation::ClobberRegister(unsigned Reg) {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
166 for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) {
|
|
120
|
167 CopyMap.erase(*AI);
|
|
|
168 AvailCopyMap.erase(*AI);
|
|
|
169
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
170 SourceMap::iterator SI = SrcMap.find(*AI);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
171 if (SI != SrcMap.end()) {
|
|
120
|
172 removeRegsFromMap(AvailCopyMap, SI->second, *TRI);
|
|
|
173 SrcMap.erase(SI);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
174 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
175 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
176 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
177
|
|
121
|
178 void MachineCopyPropagation::ReadRegister(unsigned Reg) {
|
|
|
179 // If 'Reg' is defined by a copy, the copy is no longer a candidate
|
|
|
180 // for elimination.
|
|
|
181 for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) {
|
|
|
182 Reg2MIMap::iterator CI = CopyMap.find(*AI);
|
|
|
183 if (CI != CopyMap.end()) {
|
|
|
184 DEBUG(dbgs() << "MCP: Copy is used - not dead: "; CI->second->dump());
|
|
|
185 MaybeDeadCopies.remove(CI->second);
|
|
|
186 }
|
|
|
187 }
|
|
|
188 }
|
|
|
189
|
|
120
|
190 /// Return true if \p PreviousCopy did copy register \p Src to register \p Def.
|
|
|
191 /// This fact may have been obscured by sub register usage or may not be true at
|
|
|
192 /// all even though Src and Def are subregisters of the registers used in
|
|
|
193 /// PreviousCopy. e.g.
|
|
|
194 /// isNopCopy("ecx = COPY eax", AX, CX) == true
|
|
|
195 /// isNopCopy("ecx = COPY eax", AH, CL) == false
|
|
|
196 static bool isNopCopy(const MachineInstr &PreviousCopy, unsigned Src,
|
|
|
197 unsigned Def, const TargetRegisterInfo *TRI) {
|
|
|
198 unsigned PreviousSrc = PreviousCopy.getOperand(1).getReg();
|
|
|
199 unsigned PreviousDef = PreviousCopy.getOperand(0).getReg();
|
|
|
200 if (Src == PreviousSrc) {
|
|
|
201 assert(Def == PreviousDef);
|
|
|
202 return true;
|
|
|
203 }
|
|
|
204 if (!TRI->isSubRegister(PreviousSrc, Src))
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
205 return false;
|
|
120
|
206 unsigned SubIdx = TRI->getSubRegIndex(PreviousSrc, Src);
|
|
|
207 return SubIdx == TRI->getSubRegIndex(PreviousDef, Def);
|
|
|
208 }
|
|
|
209
|
|
|
210 /// Remove instruction \p Copy if there exists a previous copy that copies the
|
|
|
211 /// register \p Src to the register \p Def; This may happen indirectly by
|
|
|
212 /// copying the super registers.
|
|
|
213 bool MachineCopyPropagation::eraseIfRedundant(MachineInstr &Copy, unsigned Src,
|
|
|
214 unsigned Def) {
|
|
|
215 // Avoid eliminating a copy from/to a reserved registers as we cannot predict
|
|
|
216 // the value (Example: The sparc zero register is writable but stays zero).
|
|
|
217 if (MRI->isReserved(Src) || MRI->isReserved(Def))
|
|
|
218 return false;
|
|
|
219
|
|
|
220 // Search for an existing copy.
|
|
|
221 Reg2MIMap::iterator CI = AvailCopyMap.find(Def);
|
|
|
222 if (CI == AvailCopyMap.end())
|
|
|
223 return false;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
224
|
|
120
|
225 // Check that the existing copy uses the correct sub registers.
|
|
|
226 MachineInstr &PrevCopy = *CI->second;
|
|
134
|
227 if (PrevCopy.getOperand(0).isDead())
|
|
|
228 return false;
|
|
120
|
229 if (!isNopCopy(PrevCopy, Src, Def, TRI))
|
|
|
230 return false;
|
|
|
231
|
|
|
232 DEBUG(dbgs() << "MCP: copy is a NOP, removing: "; Copy.dump());
|
|
|
233
|
|
|
234 // Copy was redundantly redefining either Src or Def. Remove earlier kill
|
|
|
235 // flags between Copy and PrevCopy because the value will be reused now.
|
|
|
236 assert(Copy.isCopy());
|
|
|
237 unsigned CopyDef = Copy.getOperand(0).getReg();
|
|
|
238 assert(CopyDef == Src || CopyDef == Def);
|
|
|
239 for (MachineInstr &MI :
|
|
|
240 make_range(PrevCopy.getIterator(), Copy.getIterator()))
|
|
|
241 MI.clearRegisterKills(CopyDef, TRI);
|
|
|
242
|
|
|
243 Copy.eraseFromParent();
|
|
|
244 Changed = true;
|
|
|
245 ++NumDeletes;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
246 return true;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
247 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
248
|
|
134
|
249 /// Decide whether we should forward the source of \param Copy to its use in
|
|
|
250 /// \param UseI based on the physical register class constraints of the opcode
|
|
|
251 /// and avoiding introducing more cross-class COPYs.
|
|
|
252 bool MachineCopyPropagation::isForwardableRegClassCopy(const MachineInstr &Copy,
|
|
|
253 const MachineInstr &UseI,
|
|
|
254 unsigned UseIdx) {
|
|
|
255
|
|
|
256 unsigned CopySrcReg = Copy.getOperand(1).getReg();
|
|
|
257
|
|
|
258 // If the new register meets the opcode register constraints, then allow
|
|
|
259 // forwarding.
|
|
|
260 if (const TargetRegisterClass *URC =
|
|
|
261 UseI.getRegClassConstraint(UseIdx, TII, TRI))
|
|
|
262 return URC->contains(CopySrcReg);
|
|
|
263
|
|
|
264 if (!UseI.isCopy())
|
|
|
265 return false;
|
|
|
266
|
|
|
267 /// COPYs don't have register class constraints, so if the user instruction
|
|
|
268 /// is a COPY, we just try to avoid introducing additional cross-class
|
|
|
269 /// COPYs. For example:
|
|
|
270 ///
|
|
|
271 /// RegClassA = COPY RegClassB // Copy parameter
|
|
|
272 /// ...
|
|
|
273 /// RegClassB = COPY RegClassA // UseI parameter
|
|
|
274 ///
|
|
|
275 /// which after forwarding becomes
|
|
|
276 ///
|
|
|
277 /// RegClassA = COPY RegClassB
|
|
|
278 /// ...
|
|
|
279 /// RegClassB = COPY RegClassB
|
|
|
280 ///
|
|
|
281 /// so we have reduced the number of cross-class COPYs and potentially
|
|
|
282 /// introduced a nop COPY that can be removed.
|
|
|
283 const TargetRegisterClass *UseDstRC =
|
|
|
284 TRI->getMinimalPhysRegClass(UseI.getOperand(0).getReg());
|
|
|
285
|
|
|
286 const TargetRegisterClass *SuperRC = UseDstRC;
|
|
|
287 for (TargetRegisterClass::sc_iterator SuperRCI = UseDstRC->getSuperClasses();
|
|
|
288 SuperRC; SuperRC = *SuperRCI++)
|
|
|
289 if (SuperRC->contains(CopySrcReg))
|
|
|
290 return true;
|
|
|
291
|
|
|
292 return false;
|
|
|
293 }
|
|
|
294
|
|
|
295 /// Check that \p MI does not have implicit uses that overlap with it's \p Use
|
|
|
296 /// operand (the register being replaced), since these can sometimes be
|
|
|
297 /// implicitly tied to other operands. For example, on AMDGPU:
|
|
|
298 ///
|
|
|
299 /// V_MOVRELS_B32_e32 %VGPR2, %M0<imp-use>, %EXEC<imp-use>, %VGPR2_VGPR3_VGPR4_VGPR5<imp-use>
|
|
|
300 ///
|
|
|
301 /// the %VGPR2 is implicitly tied to the larger reg operand, but we have no
|
|
|
302 /// way of knowing we need to update the latter when updating the former.
|
|
|
303 bool MachineCopyPropagation::hasImplicitOverlap(const MachineInstr &MI,
|
|
|
304 const MachineOperand &Use) {
|
|
|
305 for (const MachineOperand &MIUse : MI.uses())
|
|
|
306 if (&MIUse != &Use && MIUse.isReg() && MIUse.isImplicit() &&
|
|
|
307 MIUse.isUse() && TRI->regsOverlap(Use.getReg(), MIUse.getReg()))
|
|
|
308 return true;
|
|
|
309
|
|
|
310 return false;
|
|
|
311 }
|
|
|
312
|
|
|
313 /// Look for available copies whose destination register is used by \p MI and
|
|
|
314 /// replace the use in \p MI with the copy's source register.
|
|
|
315 void MachineCopyPropagation::forwardUses(MachineInstr &MI) {
|
|
|
316 if (AvailCopyMap.empty())
|
|
|
317 return;
|
|
|
318
|
|
|
319 // Look for non-tied explicit vreg uses that have an active COPY
|
|
|
320 // instruction that defines the physical register allocated to them.
|
|
|
321 // Replace the vreg with the source of the active COPY.
|
|
|
322 for (unsigned OpIdx = 0, OpEnd = MI.getNumOperands(); OpIdx < OpEnd;
|
|
|
323 ++OpIdx) {
|
|
|
324 MachineOperand &MOUse = MI.getOperand(OpIdx);
|
|
|
325 // Don't forward into undef use operands since doing so can cause problems
|
|
|
326 // with the machine verifier, since it doesn't treat undef reads as reads,
|
|
|
327 // so we can end up with a live range that ends on an undef read, leading to
|
|
|
328 // an error that the live range doesn't end on a read of the live range
|
|
|
329 // register.
|
|
|
330 if (!MOUse.isReg() || MOUse.isTied() || MOUse.isUndef() || MOUse.isDef() ||
|
|
|
331 MOUse.isImplicit())
|
|
|
332 continue;
|
|
|
333
|
|
|
334 if (!MOUse.getReg())
|
|
|
335 continue;
|
|
|
336
|
|
|
337 // Check that the register is marked 'renamable' so we know it is safe to
|
|
|
338 // rename it without violating any constraints that aren't expressed in the
|
|
|
339 // IR (e.g. ABI or opcode requirements).
|
|
|
340 if (!MOUse.isRenamable())
|
|
|
341 continue;
|
|
|
342
|
|
|
343 auto CI = AvailCopyMap.find(MOUse.getReg());
|
|
|
344 if (CI == AvailCopyMap.end())
|
|
|
345 continue;
|
|
|
346
|
|
|
347 MachineInstr &Copy = *CI->second;
|
|
|
348 unsigned CopyDstReg = Copy.getOperand(0).getReg();
|
|
|
349 const MachineOperand &CopySrc = Copy.getOperand(1);
|
|
|
350 unsigned CopySrcReg = CopySrc.getReg();
|
|
|
351
|
|
|
352 // FIXME: Don't handle partial uses of wider COPYs yet.
|
|
|
353 if (MOUse.getReg() != CopyDstReg) {
|
|
|
354 DEBUG(dbgs() << "MCP: FIXME! Not forwarding COPY to sub-register use:\n "
|
|
|
355 << MI);
|
|
|
356 continue;
|
|
|
357 }
|
|
|
358
|
|
|
359 // Don't forward COPYs of reserved regs unless they are constant.
|
|
|
360 if (MRI->isReserved(CopySrcReg) && !MRI->isConstantPhysReg(CopySrcReg))
|
|
|
361 continue;
|
|
|
362
|
|
|
363 if (!isForwardableRegClassCopy(Copy, MI, OpIdx))
|
|
|
364 continue;
|
|
|
365
|
|
|
366 if (hasImplicitOverlap(MI, MOUse))
|
|
|
367 continue;
|
|
|
368
|
|
|
369 if (!DebugCounter::shouldExecute(FwdCounter)) {
|
|
|
370 DEBUG(dbgs() << "MCP: Skipping forwarding due to debug counter:\n "
|
|
|
371 << MI);
|
|
|
372 continue;
|
|
|
373 }
|
|
|
374
|
|
|
375 DEBUG(dbgs() << "MCP: Replacing " << printReg(MOUse.getReg(), TRI)
|
|
|
376 << "\n with " << printReg(CopySrcReg, TRI) << "\n in "
|
|
|
377 << MI << " from " << Copy);
|
|
|
378
|
|
|
379 MOUse.setReg(CopySrcReg);
|
|
|
380 if (!CopySrc.isRenamable())
|
|
|
381 MOUse.setIsRenamable(false);
|
|
|
382
|
|
|
383 DEBUG(dbgs() << "MCP: After replacement: " << MI << "\n");
|
|
|
384
|
|
|
385 // Clear kill markers that may have been invalidated.
|
|
|
386 for (MachineInstr &KMI :
|
|
|
387 make_range(Copy.getIterator(), std::next(MI.getIterator())))
|
|
|
388 KMI.clearRegisterKills(CopySrcReg, TRI);
|
|
|
389
|
|
|
390 ++NumCopyForwards;
|
|
|
391 Changed = true;
|
|
|
392 }
|
|
|
393 }
|
|
|
394
|
|
120
|
395 void MachineCopyPropagation::CopyPropagateBlock(MachineBasicBlock &MBB) {
|
|
77
|
396 DEBUG(dbgs() << "MCP: CopyPropagateBlock " << MBB.getName() << "\n");
|
|
|
397
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
398 for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); I != E; ) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
399 MachineInstr *MI = &*I;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
400 ++I;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
401
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
402 if (MI->isCopy()) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
403 unsigned Def = MI->getOperand(0).getReg();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
404 unsigned Src = MI->getOperand(1).getReg();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
405
|
|
120
|
406 assert(!TargetRegisterInfo::isVirtualRegister(Def) &&
|
|
|
407 !TargetRegisterInfo::isVirtualRegister(Src) &&
|
|
|
408 "MachineCopyPropagation should be run after register allocation!");
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
409
|
|
120
|
410 // The two copies cancel out and the source of the first copy
|
|
|
411 // hasn't been overridden, eliminate the second one. e.g.
|
|
134
|
412 // %ecx = COPY %eax
|
|
|
413 // ... nothing clobbered eax.
|
|
|
414 // %eax = COPY %ecx
|
|
120
|
415 // =>
|
|
134
|
416 // %ecx = COPY %eax
|
|
120
|
417 //
|
|
|
418 // or
|
|
|
419 //
|
|
134
|
420 // %ecx = COPY %eax
|
|
|
421 // ... nothing clobbered eax.
|
|
|
422 // %ecx = COPY %eax
|
|
120
|
423 // =>
|
|
134
|
424 // %ecx = COPY %eax
|
|
120
|
425 if (eraseIfRedundant(*MI, Def, Src) || eraseIfRedundant(*MI, Src, Def))
|
|
|
426 continue;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
427
|
|
134
|
428 forwardUses(*MI);
|
|
|
429
|
|
|
430 // Src may have been changed by forwardUses()
|
|
|
431 Src = MI->getOperand(1).getReg();
|
|
|
432
|
|
120
|
433 // If Src is defined by a previous copy, the previous copy cannot be
|
|
|
434 // eliminated.
|
|
121
|
435 ReadRegister(Src);
|
|
|
436 for (const MachineOperand &MO : MI->implicit_operands()) {
|
|
|
437 if (!MO.isReg() || !MO.readsReg())
|
|
|
438 continue;
|
|
|
439 unsigned Reg = MO.getReg();
|
|
|
440 if (!Reg)
|
|
|
441 continue;
|
|
|
442 ReadRegister(Reg);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
443 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
444
|
|
77
|
445 DEBUG(dbgs() << "MCP: Copy is a deletion candidate: "; MI->dump());
|
|
|
446
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
447 // Copy is now a candidate for deletion.
|
|
120
|
448 if (!MRI->isReserved(Def))
|
|
|
449 MaybeDeadCopies.insert(MI);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
450
|
|
120
|
451 // If 'Def' is previously source of another copy, then this earlier copy's
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
452 // source is no longer available. e.g.
|
|
134
|
453 // %xmm9 = copy %xmm2
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
454 // ...
|
|
134
|
455 // %xmm2 = copy %xmm0
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
456 // ...
|
|
134
|
457 // %xmm2 = copy %xmm9
|
|
120
|
458 ClobberRegister(Def);
|
|
121
|
459 for (const MachineOperand &MO : MI->implicit_operands()) {
|
|
|
460 if (!MO.isReg() || !MO.isDef())
|
|
|
461 continue;
|
|
|
462 unsigned Reg = MO.getReg();
|
|
|
463 if (!Reg)
|
|
|
464 continue;
|
|
|
465 ClobberRegister(Reg);
|
|
|
466 }
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
467
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
468 // Remember Def is defined by the copy.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
469 for (MCSubRegIterator SR(Def, TRI, /*IncludeSelf=*/true); SR.isValid();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
470 ++SR) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
471 CopyMap[*SR] = MI;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
472 AvailCopyMap[*SR] = MI;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
473 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
474
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
475 // Remember source that's copied to Def. Once it's clobbered, then
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
476 // it's no longer available for copy propagation.
|
|
120
|
477 RegList &DestList = SrcMap[Src];
|
|
|
478 if (!is_contained(DestList, Def))
|
|
121
|
479 DestList.push_back(Def);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
480
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
481 continue;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
482 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
483
|
|
134
|
484 // Clobber any earlyclobber regs first.
|
|
|
485 for (const MachineOperand &MO : MI->operands())
|
|
|
486 if (MO.isReg() && MO.isEarlyClobber()) {
|
|
|
487 unsigned Reg = MO.getReg();
|
|
|
488 // If we have a tied earlyclobber, that means it is also read by this
|
|
|
489 // instruction, so we need to make sure we don't remove it as dead
|
|
|
490 // later.
|
|
|
491 if (MO.isTied())
|
|
|
492 ReadRegister(Reg);
|
|
|
493 ClobberRegister(Reg);
|
|
|
494 }
|
|
|
495
|
|
|
496 forwardUses(*MI);
|
|
|
497
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
498 // Not a copy.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
499 SmallVector<unsigned, 2> Defs;
|
|
120
|
500 const MachineOperand *RegMask = nullptr;
|
|
|
501 for (const MachineOperand &MO : MI->operands()) {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
502 if (MO.isRegMask())
|
|
120
|
503 RegMask = &MO;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
504 if (!MO.isReg())
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
505 continue;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
506 unsigned Reg = MO.getReg();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
507 if (!Reg)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
508 continue;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
509
|
|
120
|
510 assert(!TargetRegisterInfo::isVirtualRegister(Reg) &&
|
|
|
511 "MachineCopyPropagation should be run after register allocation!");
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
512
|
|
134
|
513 if (MO.isDef() && !MO.isEarlyClobber()) {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
514 Defs.push_back(Reg);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
515 continue;
|
|
121
|
516 } else if (MO.readsReg())
|
|
|
517 ReadRegister(Reg);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
518 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
519
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
520 // The instruction has a register mask operand which means that it clobbers
|
|
120
|
521 // a large set of registers. Treat clobbered registers the same way as
|
|
|
522 // defined registers.
|
|
|
523 if (RegMask) {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
524 // Erase any MaybeDeadCopies whose destination register is clobbered.
|
|
120
|
525 for (SmallSetVector<MachineInstr *, 8>::iterator DI =
|
|
|
526 MaybeDeadCopies.begin();
|
|
|
527 DI != MaybeDeadCopies.end();) {
|
|
|
528 MachineInstr *MaybeDead = *DI;
|
|
|
529 unsigned Reg = MaybeDead->getOperand(0).getReg();
|
|
|
530 assert(!MRI->isReserved(Reg));
|
|
|
531
|
|
|
532 if (!RegMask->clobbersPhysReg(Reg)) {
|
|
|
533 ++DI;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
534 continue;
|
|
120
|
535 }
|
|
|
536
|
|
77
|
537 DEBUG(dbgs() << "MCP: Removing copy due to regmask clobbering: ";
|
|
120
|
538 MaybeDead->dump());
|
|
|
539
|
|
|
540 // erase() will return the next valid iterator pointing to the next
|
|
|
541 // element after the erased one.
|
|
|
542 DI = MaybeDeadCopies.erase(DI);
|
|
|
543 MaybeDead->eraseFromParent();
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
544 Changed = true;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
545 ++NumDeletes;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
546 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
547
|
|
120
|
548 removeClobberedRegsFromMap(AvailCopyMap, *RegMask);
|
|
|
549 removeClobberedRegsFromMap(CopyMap, *RegMask);
|
|
|
550 for (SourceMap::iterator I = SrcMap.begin(), E = SrcMap.end(), Next;
|
|
|
551 I != E; I = Next) {
|
|
|
552 Next = std::next(I);
|
|
|
553 if (RegMask->clobbersPhysReg(I->first)) {
|
|
|
554 removeRegsFromMap(AvailCopyMap, I->second, *TRI);
|
|
|
555 SrcMap.erase(I);
|
|
|
556 }
|
|
|
557 }
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
558 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
559
|
|
120
|
560 // Any previous copy definition or reading the Defs is no longer available.
|
|
|
561 for (unsigned Reg : Defs)
|
|
|
562 ClobberRegister(Reg);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
563 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
564
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
565 // If MBB doesn't have successors, delete the copies whose defs are not used.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
566 // If MBB does have successors, then conservative assume the defs are live-out
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
567 // since we don't want to trust live-in lists.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
568 if (MBB.succ_empty()) {
|
|
120
|
569 for (MachineInstr *MaybeDead : MaybeDeadCopies) {
|
|
134
|
570 DEBUG(dbgs() << "MCP: Removing copy due to no live-out succ: ";
|
|
|
571 MaybeDead->dump());
|
|
120
|
572 assert(!MRI->isReserved(MaybeDead->getOperand(0).getReg()));
|
|
|
573 MaybeDead->eraseFromParent();
|
|
|
574 Changed = true;
|
|
|
575 ++NumDeletes;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
576 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
577 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
578
|
|
120
|
579 MaybeDeadCopies.clear();
|
|
|
580 AvailCopyMap.clear();
|
|
|
581 CopyMap.clear();
|
|
|
582 SrcMap.clear();
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
583 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
584
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
585 bool MachineCopyPropagation::runOnMachineFunction(MachineFunction &MF) {
|
|
134
|
586 if (skipFunction(MF.getFunction()))
|
|
77
|
587 return false;
|
|
|
588
|
|
120
|
589 Changed = false;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
590
|
|
77
|
591 TRI = MF.getSubtarget().getRegisterInfo();
|
|
|
592 TII = MF.getSubtarget().getInstrInfo();
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
593 MRI = &MF.getRegInfo();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
594
|
|
120
|
595 for (MachineBasicBlock &MBB : MF)
|
|
|
596 CopyPropagateBlock(MBB);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
597
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
598 return Changed;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
599 }
|
