LLVM  12.0.0git
MachineCopyPropagation.cpp
Go to the documentation of this file.
1 //===- MachineCopyPropagation.cpp - Machine Copy Propagation Pass ---------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This is an extremely simple MachineInstr-level copy propagation pass.
10 //
11 // This pass forwards the source of COPYs to the users of their destinations
12 // when doing so is legal. For example:
13 //
14 // %reg1 = COPY %reg0
15 // ...
16 // ... = OP %reg1
17 //
18 // If
19 // - %reg0 has not been clobbered by the time of the use of %reg1
20 // - the register class constraints are satisfied
21 // - the COPY def is the only value that reaches OP
22 // then this pass replaces the above with:
23 //
24 // %reg1 = COPY %reg0
25 // ...
26 // ... = OP %reg0
27 //
28 // This pass also removes some redundant COPYs. For example:
29 //
30 // %R1 = COPY %R0
31 // ... // No clobber of %R1
32 // %R0 = COPY %R1 <<< Removed
33 //
34 // or
35 //
36 // %R1 = COPY %R0
37 // ... // No clobber of %R0
38 // %R1 = COPY %R0 <<< Removed
39 //
40 // or
41 //
42 // $R0 = OP ...
43 // ... // No read/clobber of $R0 and $R1
44 // $R1 = COPY $R0 // $R0 is killed
45 // Replace $R0 with $R1 and remove the COPY
46 // $R1 = OP ...
47 // ...
48 //
49 //===----------------------------------------------------------------------===//
50 
51 #include "llvm/ADT/DenseMap.h"
52 #include "llvm/ADT/STLExtras.h"
53 #include "llvm/ADT/SetVector.h"
54 #include "llvm/ADT/SmallSet.h"
55 #include "llvm/ADT/SmallVector.h"
56 #include "llvm/ADT/Statistic.h"
67 #include "llvm/InitializePasses.h"
68 #include "llvm/MC/MCRegisterInfo.h"
69 #include "llvm/Pass.h"
70 #include "llvm/Support/Debug.h"
73 #include <cassert>
74 #include <iterator>
75 
76 using namespace llvm;
77 
78 #define DEBUG_TYPE "machine-cp"
79 
80 STATISTIC(NumDeletes, "Number of dead copies deleted");
81 STATISTIC(NumCopyForwards, "Number of copy uses forwarded");
82 STATISTIC(NumCopyBackwardPropagated, "Number of copy defs backward propagated");
83 DEBUG_COUNTER(FwdCounter, "machine-cp-fwd",
84  "Controls which register COPYs are forwarded");
85 
86 namespace {
87 
88 class CopyTracker {
89  struct CopyInfo {
92  bool Avail;
93  };
94 
96 
97 public:
98  /// Mark all of the given registers and their subregisters as unavailable for
99  /// copying.
100  void markRegsUnavailable(ArrayRef<unsigned> Regs,
101  const TargetRegisterInfo &TRI) {
102  for (unsigned Reg : Regs) {
103  // Source of copy is no longer available for propagation.
104  for (MCRegUnitIterator RUI(Reg, &TRI); RUI.isValid(); ++RUI) {
105  auto CI = Copies.find(*RUI);
106  if (CI != Copies.end())
107  CI->second.Avail = false;
108  }
109  }
110  }
111 
112  /// Remove register from copy maps.
113  void invalidateRegister(unsigned Reg, const TargetRegisterInfo &TRI) {
114  // Since Reg might be a subreg of some registers, only invalidate Reg is not
115  // enough. We have to find the COPY defines Reg or registers defined by Reg
116  // and invalidate all of them.
117  SmallSet<unsigned, 8> RegsToInvalidate;
118  RegsToInvalidate.insert(Reg);
119  for (MCRegUnitIterator RUI(Reg, &TRI); RUI.isValid(); ++RUI) {
120  auto I = Copies.find(*RUI);
121  if (I != Copies.end()) {
122  if (MachineInstr *MI = I->second.MI) {
123  RegsToInvalidate.insert(MI->getOperand(0).getReg());
124  RegsToInvalidate.insert(MI->getOperand(1).getReg());
125  }
126  RegsToInvalidate.insert(I->second.DefRegs.begin(),
127  I->second.DefRegs.end());
128  }
129  }
130  for (unsigned InvalidReg : RegsToInvalidate)
131  for (MCRegUnitIterator RUI(InvalidReg, &TRI); RUI.isValid(); ++RUI)
132  Copies.erase(*RUI);
133  }
134 
135  /// Clobber a single register, removing it from the tracker's copy maps.
136  void clobberRegister(unsigned Reg, const TargetRegisterInfo &TRI) {
137  for (MCRegUnitIterator RUI(Reg, &TRI); RUI.isValid(); ++RUI) {
138  auto I = Copies.find(*RUI);
139  if (I != Copies.end()) {
140  // When we clobber the source of a copy, we need to clobber everything
141  // it defined.
142  markRegsUnavailable(I->second.DefRegs, TRI);
143  // When we clobber the destination of a copy, we need to clobber the
144  // whole register it defined.
145  if (MachineInstr *MI = I->second.MI)
146  markRegsUnavailable({MI->getOperand(0).getReg()}, TRI);
147  // Now we can erase the copy.
148  Copies.erase(I);
149  }
150  }
151  }
152 
153  /// Add this copy's registers into the tracker's copy maps.
154  void trackCopy(MachineInstr *MI, const TargetRegisterInfo &TRI) {
155  assert(MI->isCopy() && "Tracking non-copy?");
156 
157  Register Def = MI->getOperand(0).getReg();
158  Register Src = MI->getOperand(1).getReg();
159 
160  // Remember Def is defined by the copy.
161  for (MCRegUnitIterator RUI(Def, &TRI); RUI.isValid(); ++RUI)
162  Copies[*RUI] = {MI, {}, true};
163 
164  // Remember source that's copied to Def. Once it's clobbered, then
165  // it's no longer available for copy propagation.
166  for (MCRegUnitIterator RUI(Src, &TRI); RUI.isValid(); ++RUI) {
167  auto I = Copies.insert({*RUI, {nullptr, {}, false}});
168  auto &Copy = I.first->second;
169  if (!is_contained(Copy.DefRegs, Def))
170  Copy.DefRegs.push_back(Def);
171  }
172  }
173 
174  bool hasAnyCopies() {
175  return !Copies.empty();
176  }
177 
178  MachineInstr *findCopyForUnit(unsigned RegUnit, const TargetRegisterInfo &TRI,
179  bool MustBeAvailable = false) {
180  auto CI = Copies.find(RegUnit);
181  if (CI == Copies.end())
182  return nullptr;
183  if (MustBeAvailable && !CI->second.Avail)
184  return nullptr;
185  return CI->second.MI;
186  }
187 
188  MachineInstr *findCopyDefViaUnit(unsigned RegUnit,
189  const TargetRegisterInfo &TRI) {
190  auto CI = Copies.find(RegUnit);
191  if (CI == Copies.end())
192  return nullptr;
193  if (CI->second.DefRegs.size() != 1)
194  return nullptr;
195  MCRegUnitIterator RUI(CI->second.DefRegs[0], &TRI);
196  return findCopyForUnit(*RUI, TRI, true);
197  }
198 
199  MachineInstr *findAvailBackwardCopy(MachineInstr &I, unsigned Reg,
200  const TargetRegisterInfo &TRI) {
201  MCRegUnitIterator RUI(Reg, &TRI);
202  MachineInstr *AvailCopy = findCopyDefViaUnit(*RUI, TRI);
203  if (!AvailCopy ||
204  !TRI.isSubRegisterEq(AvailCopy->getOperand(1).getReg(), Reg))
205  return nullptr;
206 
207  Register AvailSrc = AvailCopy->getOperand(1).getReg();
208  Register AvailDef = AvailCopy->getOperand(0).getReg();
209  for (const MachineInstr &MI :
211  for (const MachineOperand &MO : MI.operands())
212  if (MO.isRegMask())
213  // FIXME: Shall we simultaneously invalidate AvailSrc or AvailDef?
214  if (MO.clobbersPhysReg(AvailSrc) || MO.clobbersPhysReg(AvailDef))
215  return nullptr;
216 
217  return AvailCopy;
218  }
219 
220  MachineInstr *findAvailCopy(MachineInstr &DestCopy, unsigned Reg,
221  const TargetRegisterInfo &TRI) {
222  // We check the first RegUnit here, since we'll only be interested in the
223  // copy if it copies the entire register anyway.
224  MCRegUnitIterator RUI(Reg, &TRI);
225  MachineInstr *AvailCopy =
226  findCopyForUnit(*RUI, TRI, /*MustBeAvailable=*/true);
227  if (!AvailCopy ||
228  !TRI.isSubRegisterEq(AvailCopy->getOperand(0).getReg(), Reg))
229  return nullptr;
230 
231  // Check that the available copy isn't clobbered by any regmasks between
232  // itself and the destination.
233  Register AvailSrc = AvailCopy->getOperand(1).getReg();
234  Register AvailDef = AvailCopy->getOperand(0).getReg();
235  for (const MachineInstr &MI :
236  make_range(AvailCopy->getIterator(), DestCopy.getIterator()))
237  for (const MachineOperand &MO : MI.operands())
238  if (MO.isRegMask())
239  if (MO.clobbersPhysReg(AvailSrc) || MO.clobbersPhysReg(AvailDef))
240  return nullptr;
241 
242  return AvailCopy;
243  }
244 
245  void clear() {
246  Copies.clear();
247  }
248 };
249 
250 class MachineCopyPropagation : public MachineFunctionPass {
251  const TargetRegisterInfo *TRI;
252  const TargetInstrInfo *TII;
253  const MachineRegisterInfo *MRI;
254 
255 public:
256  static char ID; // Pass identification, replacement for typeid
257 
258  MachineCopyPropagation() : MachineFunctionPass(ID) {
260  }
261 
262  void getAnalysisUsage(AnalysisUsage &AU) const override {
263  AU.setPreservesCFG();
265  }
266 
267  bool runOnMachineFunction(MachineFunction &MF) override;
268 
269  MachineFunctionProperties getRequiredProperties() const override {
272  }
273 
274 private:
275  typedef enum { DebugUse = false, RegularUse = true } DebugType;
276 
277  void ClobberRegister(unsigned Reg);
278  void ReadRegister(unsigned Reg, MachineInstr &Reader,
279  DebugType DT);
280  void ForwardCopyPropagateBlock(MachineBasicBlock &MBB);
281  void BackwardCopyPropagateBlock(MachineBasicBlock &MBB);
282  bool eraseIfRedundant(MachineInstr &Copy, unsigned Src, unsigned Def);
283  void forwardUses(MachineInstr &MI);
284  void propagateDefs(MachineInstr &MI);
285  bool isForwardableRegClassCopy(const MachineInstr &Copy,
286  const MachineInstr &UseI, unsigned UseIdx);
287  bool isBackwardPropagatableRegClassCopy(const MachineInstr &Copy,
288  const MachineInstr &UseI,
289  unsigned UseIdx);
290  bool hasImplicitOverlap(const MachineInstr &MI, const MachineOperand &Use);
291 
292  /// Candidates for deletion.
293  SmallSetVector<MachineInstr *, 8> MaybeDeadCopies;
294 
295  /// Multimap tracking debug users in current BB
297 
298  CopyTracker Tracker;
299 
300  bool Changed;
301 };
302 
303 } // end anonymous namespace
304 
306 
308 
309 INITIALIZE_PASS(MachineCopyPropagation, DEBUG_TYPE,
310  "Machine Copy Propagation Pass", false, false)
311 
312 void MachineCopyPropagation::ReadRegister(unsigned Reg, MachineInstr &Reader,
313  DebugType DT) {
314  // If 'Reg' is defined by a copy, the copy is no longer a candidate
315  // for elimination. If a copy is "read" by a debug user, record the user
316  // for propagation.
317  for (MCRegUnitIterator RUI(Reg, TRI); RUI.isValid(); ++RUI) {
318  if (MachineInstr *Copy = Tracker.findCopyForUnit(*RUI, *TRI)) {
319  if (DT == RegularUse) {
320  LLVM_DEBUG(dbgs() << "MCP: Copy is used - not dead: "; Copy->dump());
321  MaybeDeadCopies.remove(Copy);
322  } else {
323  CopyDbgUsers[Copy].push_back(&Reader);
324  }
325  }
326  }
327 }
328 
329 /// Return true if \p PreviousCopy did copy register \p Src to register \p Def.
330 /// This fact may have been obscured by sub register usage or may not be true at
331 /// all even though Src and Def are subregisters of the registers used in
332 /// PreviousCopy. e.g.
333 /// isNopCopy("ecx = COPY eax", AX, CX) == true
334 /// isNopCopy("ecx = COPY eax", AH, CL) == false
335 static bool isNopCopy(const MachineInstr &PreviousCopy, unsigned Src,
336  unsigned Def, const TargetRegisterInfo *TRI) {
337  Register PreviousSrc = PreviousCopy.getOperand(1).getReg();
338  Register PreviousDef = PreviousCopy.getOperand(0).getReg();
339  if (Src == PreviousSrc) {
340  assert(Def == PreviousDef);
341  return true;
342  }
343  if (!TRI->isSubRegister(PreviousSrc, Src))
344  return false;
345  unsigned SubIdx = TRI->getSubRegIndex(PreviousSrc, Src);
346  return SubIdx == TRI->getSubRegIndex(PreviousDef, Def);
347 }
348 
349 /// Remove instruction \p Copy if there exists a previous copy that copies the
350 /// register \p Src to the register \p Def; This may happen indirectly by
351 /// copying the super registers.
352 bool MachineCopyPropagation::eraseIfRedundant(MachineInstr &Copy, unsigned Src,
353  unsigned Def) {
354  // Avoid eliminating a copy from/to a reserved registers as we cannot predict
355  // the value (Example: The sparc zero register is writable but stays zero).
356  if (MRI->isReserved(Src) || MRI->isReserved(Def))
357  return false;
358 
359  // Search for an existing copy.
360  MachineInstr *PrevCopy = Tracker.findAvailCopy(Copy, Def, *TRI);
361  if (!PrevCopy)
362  return false;
363 
364  // Check that the existing copy uses the correct sub registers.
365  if (PrevCopy->getOperand(0).isDead())
366  return false;
367  if (!isNopCopy(*PrevCopy, Src, Def, TRI))
368  return false;
369 
370  LLVM_DEBUG(dbgs() << "MCP: copy is a NOP, removing: "; Copy.dump());
371 
372  // Copy was redundantly redefining either Src or Def. Remove earlier kill
373  // flags between Copy and PrevCopy because the value will be reused now.
374  assert(Copy.isCopy());
375  Register CopyDef = Copy.getOperand(0).getReg();
376  assert(CopyDef == Src || CopyDef == Def);
377  for (MachineInstr &MI :
378  make_range(PrevCopy->getIterator(), Copy.getIterator()))
379  MI.clearRegisterKills(CopyDef, TRI);
380 
381  Copy.eraseFromParent();
382  Changed = true;
383  ++NumDeletes;
384  return true;
385 }
386 
387 bool MachineCopyPropagation::isBackwardPropagatableRegClassCopy(
388  const MachineInstr &Copy, const MachineInstr &UseI, unsigned UseIdx) {
389  Register Def = Copy.getOperand(0).getReg();
390 
391  if (const TargetRegisterClass *URC =
392  UseI.getRegClassConstraint(UseIdx, TII, TRI))
393  return URC->contains(Def);
394 
395  // We don't process further if UseI is a COPY, since forward copy propagation
396  // should handle that.
397  return false;
398 }
399 
400 /// Decide whether we should forward the source of \param Copy to its use in
401 /// \param UseI based on the physical register class constraints of the opcode
402 /// and avoiding introducing more cross-class COPYs.
403 bool MachineCopyPropagation::isForwardableRegClassCopy(const MachineInstr &Copy,
404  const MachineInstr &UseI,
405  unsigned UseIdx) {
406 
407  Register CopySrcReg = Copy.getOperand(1).getReg();
408 
409  // If the new register meets the opcode register constraints, then allow
410  // forwarding.
411  if (const TargetRegisterClass *URC =
412  UseI.getRegClassConstraint(UseIdx, TII, TRI))
413  return URC->contains(CopySrcReg);
414 
415  if (!UseI.isCopy())
416  return false;
417 
418  /// COPYs don't have register class constraints, so if the user instruction
419  /// is a COPY, we just try to avoid introducing additional cross-class
420  /// COPYs. For example:
421  ///
422  /// RegClassA = COPY RegClassB // Copy parameter
423  /// ...
424  /// RegClassB = COPY RegClassA // UseI parameter
425  ///
426  /// which after forwarding becomes
427  ///
428  /// RegClassA = COPY RegClassB
429  /// ...
430  /// RegClassB = COPY RegClassB
431  ///
432  /// so we have reduced the number of cross-class COPYs and potentially
433  /// introduced a nop COPY that can be removed.
434  const TargetRegisterClass *UseDstRC =
435  TRI->getMinimalPhysRegClass(UseI.getOperand(0).getReg());
436 
437  const TargetRegisterClass *SuperRC = UseDstRC;
438  for (TargetRegisterClass::sc_iterator SuperRCI = UseDstRC->getSuperClasses();
439  SuperRC; SuperRC = *SuperRCI++)
440  if (SuperRC->contains(CopySrcReg))
441  return true;
442 
443  return false;
444 }
445 
446 /// Check that \p MI does not have implicit uses that overlap with it's \p Use
447 /// operand (the register being replaced), since these can sometimes be
448 /// implicitly tied to other operands. For example, on AMDGPU:
449 ///
450 /// V_MOVRELS_B32_e32 %VGPR2, %M0<imp-use>, %EXEC<imp-use>, %VGPR2_VGPR3_VGPR4_VGPR5<imp-use>
451 ///
452 /// the %VGPR2 is implicitly tied to the larger reg operand, but we have no
453 /// way of knowing we need to update the latter when updating the former.
454 bool MachineCopyPropagation::hasImplicitOverlap(const MachineInstr &MI,
455  const MachineOperand &Use) {
456  for (const MachineOperand &MIUse : MI.uses())
457  if (&MIUse != &Use && MIUse.isReg() && MIUse.isImplicit() &&
458  MIUse.isUse() && TRI->regsOverlap(Use.getReg(), MIUse.getReg()))
459  return true;
460 
461  return false;
462 }
463 
464 /// Look for available copies whose destination register is used by \p MI and
465 /// replace the use in \p MI with the copy's source register.
466 void MachineCopyPropagation::forwardUses(MachineInstr &MI) {
467  if (!Tracker.hasAnyCopies())
468  return;
469 
470  // Look for non-tied explicit vreg uses that have an active COPY
471  // instruction that defines the physical register allocated to them.
472  // Replace the vreg with the source of the active COPY.
473  for (unsigned OpIdx = 0, OpEnd = MI.getNumOperands(); OpIdx < OpEnd;
474  ++OpIdx) {
475  MachineOperand &MOUse = MI.getOperand(OpIdx);
476  // Don't forward into undef use operands since doing so can cause problems
477  // with the machine verifier, since it doesn't treat undef reads as reads,
478  // so we can end up with a live range that ends on an undef read, leading to
479  // an error that the live range doesn't end on a read of the live range
480  // register.
481  if (!MOUse.isReg() || MOUse.isTied() || MOUse.isUndef() || MOUse.isDef() ||
482  MOUse.isImplicit())
483  continue;
484 
485  if (!MOUse.getReg())
486  continue;
487 
488  // Check that the register is marked 'renamable' so we know it is safe to
489  // rename it without violating any constraints that aren't expressed in the
490  // IR (e.g. ABI or opcode requirements).
491  if (!MOUse.isRenamable())
492  continue;
493 
494  MachineInstr *Copy = Tracker.findAvailCopy(MI, MOUse.getReg(), *TRI);
495  if (!Copy)
496  continue;
497 
498  Register CopyDstReg = Copy->getOperand(0).getReg();
499  const MachineOperand &CopySrc = Copy->getOperand(1);
500  Register CopySrcReg = CopySrc.getReg();
501 
502  // FIXME: Don't handle partial uses of wider COPYs yet.
503  if (MOUse.getReg() != CopyDstReg) {
504  LLVM_DEBUG(
505  dbgs() << "MCP: FIXME! Not forwarding COPY to sub-register use:\n "
506  << MI);
507  continue;
508  }
509 
510  // Don't forward COPYs of reserved regs unless they are constant.
511  if (MRI->isReserved(CopySrcReg) && !MRI->isConstantPhysReg(CopySrcReg))
512  continue;
513 
514  if (!isForwardableRegClassCopy(*Copy, MI, OpIdx))
515  continue;
516 
517  if (hasImplicitOverlap(MI, MOUse))
518  continue;
519 
520  // Check that the instruction is not a copy that partially overwrites the
521  // original copy source that we are about to use. The tracker mechanism
522  // cannot cope with that.
523  if (MI.isCopy() && MI.modifiesRegister(CopySrcReg, TRI) &&
524  !MI.definesRegister(CopySrcReg)) {
525  LLVM_DEBUG(dbgs() << "MCP: Copy source overlap with dest in " << MI);
526  continue;
527  }
528 
529  if (!DebugCounter::shouldExecute(FwdCounter)) {
530  LLVM_DEBUG(dbgs() << "MCP: Skipping forwarding due to debug counter:\n "
531  << MI);
532  continue;
533  }
534 
535  LLVM_DEBUG(dbgs() << "MCP: Replacing " << printReg(MOUse.getReg(), TRI)
536  << "\n with " << printReg(CopySrcReg, TRI)
537  << "\n in " << MI << " from " << *Copy);
538 
539  MOUse.setReg(CopySrcReg);
540  if (!CopySrc.isRenamable())
541  MOUse.setIsRenamable(false);
542 
543  LLVM_DEBUG(dbgs() << "MCP: After replacement: " << MI << "\n");
544 
545  // Clear kill markers that may have been invalidated.
546  for (MachineInstr &KMI :
547  make_range(Copy->getIterator(), std::next(MI.getIterator())))
548  KMI.clearRegisterKills(CopySrcReg, TRI);
549 
550  ++NumCopyForwards;
551  Changed = true;
552  }
553 }
554 
555 void MachineCopyPropagation::ForwardCopyPropagateBlock(MachineBasicBlock &MBB) {
556  LLVM_DEBUG(dbgs() << "MCP: ForwardCopyPropagateBlock " << MBB.getName()
557  << "\n");
558 
559  for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); I != E; ) {
560  MachineInstr *MI = &*I;
561  ++I;
562 
563  // Analyze copies (which don't overlap themselves).
564  if (MI->isCopy() && !TRI->regsOverlap(MI->getOperand(0).getReg(),
565  MI->getOperand(1).getReg())) {
566  Register Def = MI->getOperand(0).getReg();
567  Register Src = MI->getOperand(1).getReg();
568 
571  "MachineCopyPropagation should be run after register allocation!");
572 
573  // The two copies cancel out and the source of the first copy
574  // hasn't been overridden, eliminate the second one. e.g.
575  // %ecx = COPY %eax
576  // ... nothing clobbered eax.
577  // %eax = COPY %ecx
578  // =>
579  // %ecx = COPY %eax
580  //
581  // or
582  //
583  // %ecx = COPY %eax
584  // ... nothing clobbered eax.
585  // %ecx = COPY %eax
586  // =>
587  // %ecx = COPY %eax
588  if (eraseIfRedundant(*MI, Def, Src) || eraseIfRedundant(*MI, Src, Def))
589  continue;
590 
591  forwardUses(*MI);
592 
593  // Src may have been changed by forwardUses()
594  Src = MI->getOperand(1).getReg();
595 
596  // If Src is defined by a previous copy, the previous copy cannot be
597  // eliminated.
598  ReadRegister(Src, *MI, RegularUse);
599  for (const MachineOperand &MO : MI->implicit_operands()) {
600  if (!MO.isReg() || !MO.readsReg())
601  continue;
602  Register Reg = MO.getReg();
603  if (!Reg)
604  continue;
605  ReadRegister(Reg, *MI, RegularUse);
606  }
607 
608  LLVM_DEBUG(dbgs() << "MCP: Copy is a deletion candidate: "; MI->dump());
609 
610  // Copy is now a candidate for deletion.
611  if (!MRI->isReserved(Def))
612  MaybeDeadCopies.insert(MI);
613 
614  // If 'Def' is previously source of another copy, then this earlier copy's
615  // source is no longer available. e.g.
616  // %xmm9 = copy %xmm2
617  // ...
618  // %xmm2 = copy %xmm0
619  // ...
620  // %xmm2 = copy %xmm9
621  Tracker.clobberRegister(Def, *TRI);
622  for (const MachineOperand &MO : MI->implicit_operands()) {
623  if (!MO.isReg() || !MO.isDef())
624  continue;
625  Register Reg = MO.getReg();
626  if (!Reg)
627  continue;
628  Tracker.clobberRegister(Reg, *TRI);
629  }
630 
631  Tracker.trackCopy(MI, *TRI);
632 
633  continue;
634  }
635 
636  // Clobber any earlyclobber regs first.
637  for (const MachineOperand &MO : MI->operands())
638  if (MO.isReg() && MO.isEarlyClobber()) {
639  Register Reg = MO.getReg();
640  // If we have a tied earlyclobber, that means it is also read by this
641  // instruction, so we need to make sure we don't remove it as dead
642  // later.
643  if (MO.isTied())
644  ReadRegister(Reg, *MI, RegularUse);
645  Tracker.clobberRegister(Reg, *TRI);
646  }
647 
648  forwardUses(*MI);
649 
650  // Not a copy.
652  const MachineOperand *RegMask = nullptr;
653  for (const MachineOperand &MO : MI->operands()) {
654  if (MO.isRegMask())
655  RegMask = &MO;
656  if (!MO.isReg())
657  continue;
658  Register Reg = MO.getReg();
659  if (!Reg)
660  continue;
661 
663  "MachineCopyPropagation should be run after register allocation!");
664 
665  if (MO.isDef() && !MO.isEarlyClobber()) {
666  Defs.push_back(Reg);
667  continue;
668  } else if (MO.readsReg())
669  ReadRegister(Reg, *MI, MO.isDebug() ? DebugUse : RegularUse);
670  }
671 
672  // The instruction has a register mask operand which means that it clobbers
673  // a large set of registers. Treat clobbered registers the same way as
674  // defined registers.
675  if (RegMask) {
676  // Erase any MaybeDeadCopies whose destination register is clobbered.
678  MaybeDeadCopies.begin();
679  DI != MaybeDeadCopies.end();) {
680  MachineInstr *MaybeDead = *DI;
681  Register Reg = MaybeDead->getOperand(0).getReg();
682  assert(!MRI->isReserved(Reg));
683 
684  if (!RegMask->clobbersPhysReg(Reg)) {
685  ++DI;
686  continue;
687  }
688 
689  LLVM_DEBUG(dbgs() << "MCP: Removing copy due to regmask clobbering: ";
690  MaybeDead->dump());
691 
692  // Make sure we invalidate any entries in the copy maps before erasing
693  // the instruction.
694  Tracker.clobberRegister(Reg, *TRI);
695 
696  // erase() will return the next valid iterator pointing to the next
697  // element after the erased one.
698  DI = MaybeDeadCopies.erase(DI);
699  MaybeDead->eraseFromParent();
700  Changed = true;
701  ++NumDeletes;
702  }
703  }
704 
705  // Any previous copy definition or reading the Defs is no longer available.
706  for (unsigned Reg : Defs)
707  Tracker.clobberRegister(Reg, *TRI);
708  }
709 
710  // If MBB doesn't have successors, delete the copies whose defs are not used.
711  // If MBB does have successors, then conservative assume the defs are live-out
712  // since we don't want to trust live-in lists.
713  if (MBB.succ_empty()) {
714  for (MachineInstr *MaybeDead : MaybeDeadCopies) {
715  LLVM_DEBUG(dbgs() << "MCP: Removing copy due to no live-out succ: ";
716  MaybeDead->dump());
717  assert(!MRI->isReserved(MaybeDead->getOperand(0).getReg()));
718 
719  // Update matching debug values, if any.
720  assert(MaybeDead->isCopy());
721  unsigned SrcReg = MaybeDead->getOperand(1).getReg();
722  MRI->updateDbgUsersToReg(SrcReg, CopyDbgUsers[MaybeDead]);
723 
724  MaybeDead->eraseFromParent();
725  Changed = true;
726  ++NumDeletes;
727  }
728  }
729 
730  MaybeDeadCopies.clear();
731  CopyDbgUsers.clear();
732  Tracker.clear();
733 }
734 
736  const MachineRegisterInfo &MRI) {
737  assert(MI.isCopy() && "MI is expected to be a COPY");
738  Register Def = MI.getOperand(0).getReg();
739  Register Src = MI.getOperand(1).getReg();
740 
741  if (!Def || !Src)
742  return false;
743 
744  if (MRI.isReserved(Def) || MRI.isReserved(Src))
745  return false;
746 
747  return MI.getOperand(1).isRenamable() && MI.getOperand(1).isKill();
748 }
749 
750 void MachineCopyPropagation::propagateDefs(MachineInstr &MI) {
751  if (!Tracker.hasAnyCopies())
752  return;
753 
754  for (unsigned OpIdx = 0, OpEnd = MI.getNumOperands(); OpIdx != OpEnd;
755  ++OpIdx) {
756  MachineOperand &MODef = MI.getOperand(OpIdx);
757 
758  if (!MODef.isReg() || MODef.isUse())
759  continue;
760 
761  // Ignore non-trivial cases.
762  if (MODef.isTied() || MODef.isUndef() || MODef.isImplicit())
763  continue;
764 
765  if (!MODef.getReg())
766  continue;
767 
768  // We only handle if the register comes from a vreg.
769  if (!MODef.isRenamable())
770  continue;
771 
772  MachineInstr *Copy =
773  Tracker.findAvailBackwardCopy(MI, MODef.getReg(), *TRI);
774  if (!Copy)
775  continue;
776 
777  Register Def = Copy->getOperand(0).getReg();
778  Register Src = Copy->getOperand(1).getReg();
779 
780  if (MODef.getReg() != Src)
781  continue;
782 
783  if (!isBackwardPropagatableRegClassCopy(*Copy, MI, OpIdx))
784  continue;
785 
786  if (hasImplicitOverlap(MI, MODef))
787  continue;
788 
789  LLVM_DEBUG(dbgs() << "MCP: Replacing " << printReg(MODef.getReg(), TRI)
790  << "\n with " << printReg(Def, TRI) << "\n in "
791  << MI << " from " << *Copy);
792 
793  MODef.setReg(Def);
794  MODef.setIsRenamable(Copy->getOperand(0).isRenamable());
795 
796  LLVM_DEBUG(dbgs() << "MCP: After replacement: " << MI << "\n");
797  MaybeDeadCopies.insert(Copy);
798  Changed = true;
799  ++NumCopyBackwardPropagated;
800  }
801 }
802 
803 void MachineCopyPropagation::BackwardCopyPropagateBlock(
804  MachineBasicBlock &MBB) {
805  LLVM_DEBUG(dbgs() << "MCP: BackwardCopyPropagateBlock " << MBB.getName()
806  << "\n");
807 
808  for (MachineBasicBlock::reverse_iterator I = MBB.rbegin(), E = MBB.rend();
809  I != E;) {
810  MachineInstr *MI = &*I;
811  ++I;
812 
813  // Ignore non-trivial COPYs.
814  if (MI->isCopy() && MI->getNumOperands() == 2 &&
815  !TRI->regsOverlap(MI->getOperand(0).getReg(),
816  MI->getOperand(1).getReg())) {
817 
818  Register Def = MI->getOperand(0).getReg();
819  Register Src = MI->getOperand(1).getReg();
820 
821  // Unlike forward cp, we don't invoke propagateDefs here,
822  // just let forward cp do COPY-to-COPY propagation.
823  if (isBackwardPropagatableCopy(*MI, *MRI)) {
824  Tracker.invalidateRegister(Src, *TRI);
825  Tracker.invalidateRegister(Def, *TRI);
826  Tracker.trackCopy(MI, *TRI);
827  continue;
828  }
829  }
830 
831  // Invalidate any earlyclobber regs first.
832  for (const MachineOperand &MO : MI->operands())
833  if (MO.isReg() && MO.isEarlyClobber()) {
834  Register Reg = MO.getReg();
835  if (!Reg)
836  continue;
837  Tracker.invalidateRegister(Reg, *TRI);
838  }
839 
840  propagateDefs(*MI);
841  for (const MachineOperand &MO : MI->operands()) {
842  if (!MO.isReg())
843  continue;
844 
845  if (!MO.getReg())
846  continue;
847 
848  if (MO.isDef())
849  Tracker.invalidateRegister(MO.getReg(), *TRI);
850 
851  if (MO.readsReg())
852  Tracker.invalidateRegister(MO.getReg(), *TRI);
853  }
854  }
855 
856  for (auto *Copy : MaybeDeadCopies) {
857  Copy->eraseFromParent();
858  ++NumDeletes;
859  }
860 
861  MaybeDeadCopies.clear();
862  CopyDbgUsers.clear();
863  Tracker.clear();
864 }
865 
866 bool MachineCopyPropagation::runOnMachineFunction(MachineFunction &MF) {
867  if (skipFunction(MF.getFunction()))
868  return false;
869 
870  Changed = false;
871 
872  TRI = MF.getSubtarget().getRegisterInfo();
873  TII = MF.getSubtarget().getInstrInfo();
874  MRI = &MF.getRegInfo();
875 
876  for (MachineBasicBlock &MBB : MF) {
877  BackwardCopyPropagateBlock(MBB);
878  ForwardCopyPropagateBlock(MBB);
879  }
880 
881  return Changed;
882 }
static bool clobbersPhysReg(const uint32_t *RegMask, MCRegister PhysReg)
clobbersPhysReg - Returns true if this RegMask clobbers PhysReg.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
bool contains(unsigned Reg) const
Return true if the specified register is included in this register class.
bool isReserved(Register PhysReg) const
isReserved - Returns true when PhysReg is a reserved register.
This class represents lattice values for constants.
Definition: AllocatorList.h:23
iterator_range< mop_iterator > uses()
Returns a range that includes all operands that are register uses.
Definition: MachineInstr.h:603
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
void push_back(const T &Elt)
Definition: SmallVector.h:246
This provides a very simple, boring adaptor for a begin and end iterator into a range type...
unsigned Reg
STATISTIC(NumFunctions, "Total number of functions")
unsigned const TargetRegisterInfo * TRI
Printable printReg(Register Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)
Prints virtual and physical registers with or without a TRI instance.
iterator_range< mop_iterator > operands()
Definition: MachineInstr.h:559
void setIsRenamable(bool Val=true)
Function & getFunction()
Return the LLVM function that this machine code represents.
MachineBasicBlock & MBB
INITIALIZE_PASS(MachineCopyPropagation, DEBUG_TYPE, "Machine Copy Propagation Pass", false, false) void MachineCopyPropagation
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:207
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
const HexagonInstrInfo * TII
const TargetRegisterClass * getRegClassConstraint(unsigned OpIdx, const TargetInstrInfo *TII, const TargetRegisterInfo *TRI) const
Compute the static register class constraint for operand OpIdx.
unsigned getNumOperands() const
Retuns the total number of operands.
Definition: MachineInstr.h:459
A Use represents the edge between a Value definition and its users.
Definition: Use.h:44
void eraseFromParent()
Unlink &#39;this&#39; from the containing basic block and delete it.
This file provides an implementation of debug counters.
const TargetRegisterClass *const * sc_iterator
DEBUG_COUNTER(FwdCounter, "machine-cp-fwd", "Controls which register COPYs are forwarded")
bool regsOverlap(Register regA, Register regB) const
Returns true if the two registers are equal or alias each other.
unsigned getSubRegIndex(MCRegister RegNo, MCRegister SubRegNo) const
For a given register pair, return the sub-register index if the second register is a sub-register of ...
iterator begin()
Get an iterator to the beginning of the SetVector.
Definition: SetVector.h:82
void setReg(Register Reg)
Change the register this operand corresponds to.
virtual const TargetInstrInfo * getInstrInfo() const
reverse_iterator rend()
reverse_iterator rbegin()
TargetInstrInfo - Interface to description of machine instruction set.
#define DEBUG_TYPE
sc_iterator getSuperClasses() const
Returns a NULL-terminated list of super-classes.
unsigned const MachineRegisterInfo * MRI
StringRef getName() const
Return the name of the corresponding LLVM basic block, or an empty string.
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
Represent the analysis usage information of a pass.
bool definesRegister(Register Reg, const TargetRegisterInfo *TRI=nullptr) const
Return true if the MachineInstr fully defines the specified register.
self_iterator getIterator()
Definition: ilist_node.h:81
static bool shouldExecute(unsigned CounterName)
Definition: DebugCounter.h:74
std::pair< NoneType, bool > insert(const T &V)
insert - Insert an element into the set if it isn&#39;t already there.
Definition: SmallSet.h:180
char & MachineCopyPropagationID
MachineCopyPropagation - This pass performs copy propagation on machine instructions.
bool isCopy() const
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
bool isSubRegisterEq(MCRegister RegA, MCRegister RegB) const
Returns true if RegB is a sub-register of RegA or if RegB == RegA.
void initializeMachineCopyPropagationPass(PassRegistry &)
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:302
const TargetRegisterClass * getMinimalPhysRegClass(MCRegister Reg, MVT VT=MVT::Other) const
Returns the Register Class of a physical register of the given type, picking the most sub register cl...
MachineOperand class - Representation of each machine instruction operand.
bool modifiesRegister(Register Reg, const TargetRegisterInfo *TRI) const
Return true if the MachineInstr modifies (fully define or partially define) the specified register...
SI Lower i1 Copies
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:253
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
bool isSubRegister(MCRegister RegA, MCRegister RegB) const
Returns true if RegB is a sub-register of RegA.
bool isValid() const
isValid - returns true if this iterator is not yet at the end.
bool isRenamable() const
isRenamable - Returns true if this register may be renamed, i.e.
iterator_range< mop_iterator > implicit_operands()
Definition: MachineInstr.h:573
static void clear(coro::Shape &Shape)
Definition: Coroutines.cpp:225
MachineRegisterInfo - Keep track of information for virtual and physical registers, including vreg register classes, use/def chains for registers, etc.
MachineFunctionProperties & set(Property P)
static bool isBackwardPropagatableCopy(MachineInstr &MI, const MachineRegisterInfo &MRI)
Representation of each machine instruction.
Definition: MachineInstr.h:62
reverse_self_iterator getReverseIterator()
Definition: ilist_node.h:84
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
#define I(x, y, z)
Definition: MD5.cpp:59
bool isReg() const
isReg - Tests if this is a MO_Register operand.
DebugType
Definition: COFF.h:650
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
Definition: Register.h:71
static bool isNopCopy(const MachineInstr &PreviousCopy, unsigned Src, unsigned Def, const TargetRegisterInfo *TRI)
Return true if PreviousCopy did copy register Src to register Def.
IRTranslator LLVM IR MI
Register getReg() const
getReg - Returns the register number.
#define LLVM_DEBUG(X)
Definition: Debug.h:122
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:466
void clearRegisterKills(Register Reg, const TargetRegisterInfo *RegInfo)
Clear all kill flags affecting Reg.
void updateDbgUsersToReg(Register Reg, ArrayRef< MachineInstr *> Users) const
updateDbgUsersToReg - Update a collection of DBG_VALUE instructions to refer to the designated regist...
bool isConstantPhysReg(MCRegister PhysReg) const
Returns true if PhysReg is unallocatable and constant throughout the function.
Properties which a MachineFunction may have at a given point in time.
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
bool isImplicit() const
bool is_contained(R &&Range, const E &Element)
Wrapper function around std::find to detect if an element exists in a container.
Definition: STLExtras.h:1549