/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/lib/CodeGen/MachineCopyPropagation.cpp
Line | Count | Source (jump to first uncovered line) |
1 | | //===- MachineCopyPropagation.cpp - Machine Copy Propagation Pass ---------===// |
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 | | // This is an extremely simple MachineInstr-level copy propagation pass. |
11 | | // |
12 | | //===----------------------------------------------------------------------===// |
13 | | |
14 | | #include "llvm/ADT/DenseMap.h" |
15 | | #include "llvm/ADT/STLExtras.h" |
16 | | #include "llvm/ADT/SetVector.h" |
17 | | #include "llvm/ADT/SmallVector.h" |
18 | | #include "llvm/ADT/Statistic.h" |
19 | | #include "llvm/ADT/iterator_range.h" |
20 | | #include "llvm/CodeGen/MachineBasicBlock.h" |
21 | | #include "llvm/CodeGen/MachineFunction.h" |
22 | | #include "llvm/CodeGen/MachineFunctionPass.h" |
23 | | #include "llvm/CodeGen/MachineInstr.h" |
24 | | #include "llvm/CodeGen/MachineOperand.h" |
25 | | #include "llvm/CodeGen/MachineRegisterInfo.h" |
26 | | #include "llvm/MC/MCRegisterInfo.h" |
27 | | #include "llvm/Pass.h" |
28 | | #include "llvm/Support/Debug.h" |
29 | | #include "llvm/Support/raw_ostream.h" |
30 | | #include "llvm/Target/TargetInstrInfo.h" |
31 | | #include "llvm/Target/TargetRegisterInfo.h" |
32 | | #include "llvm/Target/TargetSubtargetInfo.h" |
33 | | #include <cassert> |
34 | | #include <iterator> |
35 | | |
36 | | using namespace llvm; |
37 | | |
38 | | #define DEBUG_TYPE "machine-cp" |
39 | | |
40 | | STATISTIC(NumDeletes, "Number of dead copies deleted"); |
41 | | |
42 | | namespace { |
43 | | |
44 | | using RegList = SmallVector<unsigned, 4>; |
45 | | using SourceMap = DenseMap<unsigned, RegList>; |
46 | | using Reg2MIMap = DenseMap<unsigned, MachineInstr *>; |
47 | | |
48 | | class MachineCopyPropagation : public MachineFunctionPass { |
49 | | const TargetRegisterInfo *TRI; |
50 | | const TargetInstrInfo *TII; |
51 | | const MachineRegisterInfo *MRI; |
52 | | |
53 | | public: |
54 | | static char ID; // Pass identification, replacement for typeid |
55 | | |
56 | 31.8k | MachineCopyPropagation() : MachineFunctionPass(ID) { |
57 | 31.8k | initializeMachineCopyPropagationPass(*PassRegistry::getPassRegistry()); |
58 | 31.8k | } |
59 | | |
60 | 31.8k | void getAnalysisUsage(AnalysisUsage &AU) const override { |
61 | 31.8k | AU.setPreservesCFG(); |
62 | 31.8k | MachineFunctionPass::getAnalysisUsage(AU); |
63 | 31.8k | } |
64 | | |
65 | | bool runOnMachineFunction(MachineFunction &MF) override; |
66 | | |
67 | 31.8k | MachineFunctionProperties getRequiredProperties() const override { |
68 | 31.8k | return MachineFunctionProperties().set( |
69 | 31.8k | MachineFunctionProperties::Property::NoVRegs); |
70 | 31.8k | } |
71 | | |
72 | | private: |
73 | | void ClobberRegister(unsigned Reg); |
74 | | void ReadRegister(unsigned Reg); |
75 | | void CopyPropagateBlock(MachineBasicBlock &MBB); |
76 | | bool eraseIfRedundant(MachineInstr &Copy, unsigned Src, unsigned Def); |
77 | | |
78 | | /// Candidates for deletion. |
79 | | SmallSetVector<MachineInstr*, 8> MaybeDeadCopies; |
80 | | |
81 | | /// Def -> available copies map. |
82 | | Reg2MIMap AvailCopyMap; |
83 | | |
84 | | /// Def -> copies map. |
85 | | Reg2MIMap CopyMap; |
86 | | |
87 | | /// Src -> Def map |
88 | | SourceMap SrcMap; |
89 | | |
90 | | bool Changed; |
91 | | }; |
92 | | |
93 | | } // end anonymous namespace |
94 | | |
95 | | char MachineCopyPropagation::ID = 0; |
96 | | |
97 | | char &llvm::MachineCopyPropagationID = MachineCopyPropagation::ID; |
98 | | |
99 | | INITIALIZE_PASS(MachineCopyPropagation, DEBUG_TYPE, |
100 | | "Machine Copy Propagation Pass", false, false) |
101 | | |
102 | | /// Remove any entry in \p Map where the register is a subregister or equal to |
103 | | /// a register contained in \p Regs. |
104 | | static void removeRegsFromMap(Reg2MIMap &Map, const RegList &Regs, |
105 | 1.51M | const TargetRegisterInfo &TRI) { |
106 | 1.53M | for (unsigned Reg : Regs) { |
107 | 1.53M | // Source of copy is no longer available for propagation. |
108 | 4.43M | for (MCSubRegIterator SR(Reg, &TRI, true); SR.isValid()4.43M ; ++SR2.89M ) |
109 | 2.89M | Map.erase(*SR); |
110 | 1.53M | } |
111 | 1.51M | } |
112 | | |
113 | | /// Remove any entry in \p Map that is marked clobbered in \p RegMask. |
114 | | /// The map will typically have a lot fewer entries than the regmask clobbers, |
115 | | /// so this is more efficient than iterating the clobbered registers and calling |
116 | | /// ClobberRegister() on them. |
117 | | static void removeClobberedRegsFromMap(Reg2MIMap &Map, |
118 | 4.50M | const MachineOperand &RegMask) { |
119 | 19.8M | for (Reg2MIMap::iterator I = Map.begin(), E = Map.end(), Next; I != E; |
120 | 15.3M | I = Next15.3M ) { |
121 | 15.3M | Next = std::next(I); |
122 | 15.3M | unsigned Reg = I->first; |
123 | 15.3M | if (RegMask.clobbersPhysReg(Reg)) |
124 | 8.63M | Map.erase(I); |
125 | 15.3M | } |
126 | 4.50M | } |
127 | | |
128 | 24.0M | void MachineCopyPropagation::ClobberRegister(unsigned Reg) { |
129 | 168M | for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid()168M ; ++AI144M ) { |
130 | 144M | CopyMap.erase(*AI); |
131 | 144M | AvailCopyMap.erase(*AI); |
132 | 144M | |
133 | 144M | SourceMap::iterator SI = SrcMap.find(*AI); |
134 | 144M | if (SI != SrcMap.end()144M ) { |
135 | 832k | removeRegsFromMap(AvailCopyMap, SI->second, *TRI); |
136 | 832k | SrcMap.erase(SI); |
137 | 832k | } |
138 | 144M | } |
139 | 24.0M | } |
140 | | |
141 | 32.8M | void MachineCopyPropagation::ReadRegister(unsigned Reg) { |
142 | 32.8M | // If 'Reg' is defined by a copy, the copy is no longer a candidate |
143 | 32.8M | // for elimination. |
144 | 225M | for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid()225M ; ++AI193M ) { |
145 | 193M | Reg2MIMap::iterator CI = CopyMap.find(*AI); |
146 | 193M | if (CI != CopyMap.end()193M ) { |
147 | 6.73M | DEBUG(dbgs() << "MCP: Copy is used - not dead: "; CI->second->dump()); |
148 | 6.73M | MaybeDeadCopies.remove(CI->second); |
149 | 6.73M | } |
150 | 193M | } |
151 | 32.8M | } |
152 | | |
153 | | /// Return true if \p PreviousCopy did copy register \p Src to register \p Def. |
154 | | /// This fact may have been obscured by sub register usage or may not be true at |
155 | | /// all even though Src and Def are subregisters of the registers used in |
156 | | /// PreviousCopy. e.g. |
157 | | /// isNopCopy("ecx = COPY eax", AX, CX) == true |
158 | | /// isNopCopy("ecx = COPY eax", AH, CL) == false |
159 | | static bool isNopCopy(const MachineInstr &PreviousCopy, unsigned Src, |
160 | 173k | unsigned Def, const TargetRegisterInfo *TRI) { |
161 | 173k | unsigned PreviousSrc = PreviousCopy.getOperand(1).getReg(); |
162 | 173k | unsigned PreviousDef = PreviousCopy.getOperand(0).getReg(); |
163 | 173k | if (Src == PreviousSrc173k ) { |
164 | 154k | assert(Def == PreviousDef); |
165 | 154k | return true; |
166 | 154k | } |
167 | 19.6k | if (19.6k !TRI->isSubRegister(PreviousSrc, Src)19.6k ) |
168 | 19.6k | return false; |
169 | 47 | unsigned SubIdx = TRI->getSubRegIndex(PreviousSrc, Src); |
170 | 47 | return SubIdx == TRI->getSubRegIndex(PreviousDef, Def); |
171 | 47 | } |
172 | | |
173 | | /// Remove instruction \p Copy if there exists a previous copy that copies the |
174 | | /// register \p Src to the register \p Def; This may happen indirectly by |
175 | | /// copying the super registers. |
176 | | bool MachineCopyPropagation::eraseIfRedundant(MachineInstr &Copy, unsigned Src, |
177 | 7.60M | unsigned Def) { |
178 | 7.60M | // Avoid eliminating a copy from/to a reserved registers as we cannot predict |
179 | 7.60M | // the value (Example: The sparc zero register is writable but stays zero). |
180 | 7.60M | if (MRI->isReserved(Src) || 7.60M MRI->isReserved(Def)7.10M ) |
181 | 1.00M | return false; |
182 | 6.60M | |
183 | 6.60M | // Search for an existing copy. |
184 | 6.60M | Reg2MIMap::iterator CI = AvailCopyMap.find(Def); |
185 | 6.60M | if (CI == AvailCopyMap.end()) |
186 | 6.42M | return false; |
187 | 173k | |
188 | 173k | // Check that the existing copy uses the correct sub registers. |
189 | 173k | MachineInstr &PrevCopy = *CI->second; |
190 | 173k | if (!isNopCopy(PrevCopy, Src, Def, TRI)) |
191 | 19.6k | return false; |
192 | 154k | |
193 | 154k | DEBUG154k (dbgs() << "MCP: copy is a NOP, removing: "; Copy.dump()); |
194 | 154k | |
195 | 154k | // Copy was redundantly redefining either Src or Def. Remove earlier kill |
196 | 154k | // flags between Copy and PrevCopy because the value will be reused now. |
197 | 154k | assert(Copy.isCopy()); |
198 | 154k | unsigned CopyDef = Copy.getOperand(0).getReg(); |
199 | 154k | assert(CopyDef == Src || CopyDef == Def); |
200 | 154k | for (MachineInstr &MI : |
201 | 154k | make_range(PrevCopy.getIterator(), Copy.getIterator())) |
202 | 639k | MI.clearRegisterKills(CopyDef, TRI); |
203 | 7.60M | |
204 | 7.60M | Copy.eraseFromParent(); |
205 | 7.60M | Changed = true; |
206 | 7.60M | ++NumDeletes; |
207 | 7.60M | return true; |
208 | 7.60M | } |
209 | | |
210 | 3.97M | void MachineCopyPropagation::CopyPropagateBlock(MachineBasicBlock &MBB) { |
211 | 3.97M | DEBUG(dbgs() << "MCP: CopyPropagateBlock " << MBB.getName() << "\n"); |
212 | 3.97M | |
213 | 28.1M | for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); I != E28.1M ; ) { |
214 | 24.2M | MachineInstr *MI = &*I; |
215 | 24.2M | ++I; |
216 | 24.2M | |
217 | 24.2M | if (MI->isCopy()24.2M ) { |
218 | 3.87M | unsigned Def = MI->getOperand(0).getReg(); |
219 | 3.87M | unsigned Src = MI->getOperand(1).getReg(); |
220 | 3.87M | |
221 | 3.87M | assert(!TargetRegisterInfo::isVirtualRegister(Def) && |
222 | 3.87M | !TargetRegisterInfo::isVirtualRegister(Src) && |
223 | 3.87M | "MachineCopyPropagation should be run after register allocation!"); |
224 | 3.87M | |
225 | 3.87M | // The two copies cancel out and the source of the first copy |
226 | 3.87M | // hasn't been overridden, eliminate the second one. e.g. |
227 | 3.87M | // %ECX<def> = COPY %EAX |
228 | 3.87M | // ... nothing clobbered EAX. |
229 | 3.87M | // %EAX<def> = COPY %ECX |
230 | 3.87M | // => |
231 | 3.87M | // %ECX<def> = COPY %EAX |
232 | 3.87M | // |
233 | 3.87M | // or |
234 | 3.87M | // |
235 | 3.87M | // %ECX<def> = COPY %EAX |
236 | 3.87M | // ... nothing clobbered EAX. |
237 | 3.87M | // %ECX<def> = COPY %EAX |
238 | 3.87M | // => |
239 | 3.87M | // %ECX<def> = COPY %EAX |
240 | 3.87M | if (eraseIfRedundant(*MI, Def, Src) || 3.87M eraseIfRedundant(*MI, Src, Def)3.72M ) |
241 | 154k | continue; |
242 | 3.72M | |
243 | 3.72M | // If Src is defined by a previous copy, the previous copy cannot be |
244 | 3.72M | // eliminated. |
245 | 3.72M | ReadRegister(Src); |
246 | 155k | for (const MachineOperand &MO : MI->implicit_operands()) { |
247 | 155k | if (!MO.isReg() || 155k !MO.readsReg()155k ) |
248 | 97.0k | continue; |
249 | 58.4k | unsigned Reg = MO.getReg(); |
250 | 58.4k | if (!Reg) |
251 | 0 | continue; |
252 | 58.4k | ReadRegister(Reg); |
253 | 58.4k | } |
254 | 3.72M | |
255 | 3.72M | DEBUG(dbgs() << "MCP: Copy is a deletion candidate: "; MI->dump()); |
256 | 3.72M | |
257 | 3.72M | // Copy is now a candidate for deletion. |
258 | 3.72M | if (!MRI->isReserved(Def)) |
259 | 3.72M | MaybeDeadCopies.insert(MI); |
260 | 3.72M | |
261 | 3.72M | // If 'Def' is previously source of another copy, then this earlier copy's |
262 | 3.72M | // source is no longer available. e.g. |
263 | 3.72M | // %xmm9<def> = copy %xmm2 |
264 | 3.72M | // ... |
265 | 3.72M | // %xmm2<def> = copy %xmm0 |
266 | 3.72M | // ... |
267 | 3.72M | // %xmm2<def> = copy %xmm9 |
268 | 3.72M | ClobberRegister(Def); |
269 | 155k | for (const MachineOperand &MO : MI->implicit_operands()) { |
270 | 155k | if (!MO.isReg() || 155k !MO.isDef()155k ) |
271 | 58.4k | continue; |
272 | 97.0k | unsigned Reg = MO.getReg(); |
273 | 97.0k | if (!Reg) |
274 | 0 | continue; |
275 | 97.0k | ClobberRegister(Reg); |
276 | 97.0k | } |
277 | 3.72M | |
278 | 3.72M | // Remember Def is defined by the copy. |
279 | 10.7M | for (MCSubRegIterator SR(Def, TRI, /*IncludeSelf=*/true); SR.isValid(); |
280 | 6.98M | ++SR6.98M ) { |
281 | 6.98M | CopyMap[*SR] = MI; |
282 | 6.98M | AvailCopyMap[*SR] = MI; |
283 | 6.98M | } |
284 | 3.72M | |
285 | 3.72M | // Remember source that's copied to Def. Once it's clobbered, then |
286 | 3.72M | // it's no longer available for copy propagation. |
287 | 3.72M | RegList &DestList = SrcMap[Src]; |
288 | 3.72M | if (!is_contained(DestList, Def)) |
289 | 3.05M | DestList.push_back(Def); |
290 | 3.87M | |
291 | 3.87M | continue; |
292 | 3.87M | } |
293 | 20.3M | |
294 | 20.3M | // Not a copy. |
295 | 20.3M | SmallVector<unsigned, 2> Defs; |
296 | 20.3M | const MachineOperand *RegMask = nullptr; |
297 | 75.4M | for (const MachineOperand &MO : MI->operands()) { |
298 | 75.4M | if (MO.isRegMask()) |
299 | 2.25M | RegMask = &MO; |
300 | 75.4M | if (!MO.isReg()) |
301 | 25.3M | continue; |
302 | 50.0M | unsigned Reg = MO.getReg(); |
303 | 50.0M | if (!Reg) |
304 | 734k | continue; |
305 | 49.3M | |
306 | 50.0M | assert(!TargetRegisterInfo::isVirtualRegister(Reg) && |
307 | 49.3M | "MachineCopyPropagation should be run after register allocation!"); |
308 | 49.3M | |
309 | 49.3M | if (MO.isDef()49.3M ) { |
310 | 20.2M | Defs.push_back(Reg); |
311 | 20.2M | continue; |
312 | 29.0M | } else if (29.0M MO.readsReg()29.0M ) |
313 | 29.0M | ReadRegister(Reg); |
314 | 75.4M | } |
315 | 20.3M | |
316 | 20.3M | // The instruction has a register mask operand which means that it clobbers |
317 | 20.3M | // a large set of registers. Treat clobbered registers the same way as |
318 | 20.3M | // defined registers. |
319 | 20.3M | if (RegMask20.3M ) { |
320 | 2.25M | // Erase any MaybeDeadCopies whose destination register is clobbered. |
321 | 2.25M | for (SmallSetVector<MachineInstr *, 8>::iterator DI = |
322 | 2.25M | MaybeDeadCopies.begin(); |
323 | 3.63M | DI != MaybeDeadCopies.end()3.63M ;) { |
324 | 1.38M | MachineInstr *MaybeDead = *DI; |
325 | 1.38M | unsigned Reg = MaybeDead->getOperand(0).getReg(); |
326 | 1.38M | assert(!MRI->isReserved(Reg)); |
327 | 1.38M | |
328 | 1.38M | if (!RegMask->clobbersPhysReg(Reg)1.38M ) { |
329 | 1.38M | ++DI; |
330 | 1.38M | continue; |
331 | 1.38M | } |
332 | 42 | |
333 | 42 | DEBUG42 (dbgs() << "MCP: Removing copy due to regmask clobbering: "; |
334 | 42 | MaybeDead->dump()); |
335 | 42 | |
336 | 42 | // erase() will return the next valid iterator pointing to the next |
337 | 42 | // element after the erased one. |
338 | 42 | DI = MaybeDeadCopies.erase(DI); |
339 | 42 | MaybeDead->eraseFromParent(); |
340 | 42 | Changed = true; |
341 | 42 | ++NumDeletes; |
342 | 42 | } |
343 | 2.25M | |
344 | 2.25M | removeClobberedRegsFromMap(AvailCopyMap, *RegMask); |
345 | 2.25M | removeClobberedRegsFromMap(CopyMap, *RegMask); |
346 | 2.25M | for (SourceMap::iterator I = SrcMap.begin(), E = SrcMap.end(), Next; |
347 | 6.43M | I != E6.43M ; I = Next4.18M ) { |
348 | 4.18M | Next = std::next(I); |
349 | 4.18M | if (RegMask->clobbersPhysReg(I->first)4.18M ) { |
350 | 678k | removeRegsFromMap(AvailCopyMap, I->second, *TRI); |
351 | 678k | SrcMap.erase(I); |
352 | 678k | } |
353 | 4.18M | } |
354 | 2.25M | } |
355 | 20.3M | |
356 | 20.3M | // Any previous copy definition or reading the Defs is no longer available. |
357 | 20.3M | for (unsigned Reg : Defs) |
358 | 20.2M | ClobberRegister(Reg); |
359 | 24.2M | } |
360 | 3.97M | |
361 | 3.97M | // If MBB doesn't have successors, delete the copies whose defs are not used. |
362 | 3.97M | // If MBB does have successors, then conservative assume the defs are live-out |
363 | 3.97M | // since we don't want to trust live-in lists. |
364 | 3.97M | if (MBB.succ_empty()3.97M ) { |
365 | 5.70k | for (MachineInstr *MaybeDead : MaybeDeadCopies) { |
366 | 5.70k | assert(!MRI->isReserved(MaybeDead->getOperand(0).getReg())); |
367 | 5.70k | MaybeDead->eraseFromParent(); |
368 | 5.70k | Changed = true; |
369 | 5.70k | ++NumDeletes; |
370 | 5.70k | } |
371 | 804k | } |
372 | 3.97M | |
373 | 3.97M | MaybeDeadCopies.clear(); |
374 | 3.97M | AvailCopyMap.clear(); |
375 | 3.97M | CopyMap.clear(); |
376 | 3.97M | SrcMap.clear(); |
377 | 3.97M | } |
378 | | |
379 | 587k | bool MachineCopyPropagation::runOnMachineFunction(MachineFunction &MF) { |
380 | 587k | if (skipFunction(*MF.getFunction())) |
381 | 44 | return false; |
382 | 587k | |
383 | 587k | Changed = false; |
384 | 587k | |
385 | 587k | TRI = MF.getSubtarget().getRegisterInfo(); |
386 | 587k | TII = MF.getSubtarget().getInstrInfo(); |
387 | 587k | MRI = &MF.getRegInfo(); |
388 | 587k | |
389 | 587k | for (MachineBasicBlock &MBB : MF) |
390 | 3.97M | CopyPropagateBlock(MBB); |
391 | 587k | |
392 | 587k | return Changed; |
393 | 587k | } |