llvm/lib/CodeGen/MachineCopyPropagation.cpp

   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"
  57 #include "llvm/ADT/iterator_range.h"
  58 #include "llvm/CodeGen/MachineBasicBlock.h"
  59 #include "llvm/CodeGen/MachineFunction.h"
  60 #include "llvm/CodeGen/MachineFunctionPass.h"
  61 #include "llvm/CodeGen/MachineInstr.h"
  62 #include "llvm/CodeGen/MachineOperand.h"
  63 #include "llvm/CodeGen/MachineRegisterInfo.h"
  64 #include "llvm/CodeGen/TargetInstrInfo.h"
  65 #include "llvm/CodeGen/TargetRegisterInfo.h"
  66 #include "llvm/CodeGen/TargetSubtargetInfo.h"
  67 #include "llvm/InitializePasses.h"
  68 #include "llvm/MC/MCRegisterInfo.h"
  69 #include "llvm/Pass.h"
  70 #include "llvm/Support/Debug.h"
  71 #include "llvm/Support/DebugCounter.h"
  72 #include "llvm/Support/raw_ostream.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 {
  90     MachineInstr *MI;
  91     SmallVector<MCRegister, 4> DefRegs;
  92     bool Avail;
  93   };
  94
  95   DenseMap<MCRegister, CopyInfo> Copies;
  96
  97 public:
  98   /// Mark all of the given registers and their subregisters as unavailable for
  99   /// copying.
 100   void markRegsUnavailable(ArrayRef<MCRegister> Regs,
 101                            const TargetRegisterInfo &TRI) {
 102     for (MCRegister 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(MCRegister 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<MCRegister, 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().asMCReg());
 124           RegsToInvalidate.insert(MI->getOperand(1).getReg().asMCReg());
 125         }
 126         RegsToInvalidate.insert(I->second.DefRegs.begin(),
 127                                 I->second.DefRegs.end());
 128       }
 129     }
 130     for (MCRegister 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(MCRegister 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().asMCReg()}, 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     MCRegister Def = MI->getOperand(0).getReg().asMCReg();
 158     MCRegister Src = MI->getOperand(1).getReg().asMCReg();
 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(MCRegister RegUnit,
 179                                 const TargetRegisterInfo &TRI,
 180                                 bool MustBeAvailable = false) {
 181     auto CI = Copies.find(RegUnit);
 182     if (CI == Copies.end())
 183       return nullptr;
 184     if (MustBeAvailable && !CI->second.Avail)
 185       return nullptr;
 186     return CI->second.MI;
 187   }
 188
 189   MachineInstr *findCopyDefViaUnit(MCRegister RegUnit,
 190                                    const TargetRegisterInfo &TRI) {
 191     auto CI = Copies.find(RegUnit);
 192     if (CI == Copies.end())
 193       return nullptr;
 194     if (CI->second.DefRegs.size() != 1)
 195       return nullptr;
 196     MCRegUnitIterator RUI(CI->second.DefRegs[0], &TRI);
 197     return findCopyForUnit(*RUI, TRI, true);
 198   }
 199
 200   MachineInstr *findAvailBackwardCopy(MachineInstr &I, MCRegister Reg,
 201                                       const TargetRegisterInfo &TRI) {
 202     MCRegUnitIterator RUI(Reg, &TRI);
 203     MachineInstr *AvailCopy = findCopyDefViaUnit(*RUI, TRI);
 204     if (!AvailCopy ||
 205         !TRI.isSubRegisterEq(AvailCopy->getOperand(1).getReg(), Reg))
 206       return nullptr;
 207
 208     Register AvailSrc = AvailCopy->getOperand(1).getReg();
 209     Register AvailDef = AvailCopy->getOperand(0).getReg();
 210     for (const MachineInstr &MI :
 211          make_range(AvailCopy->getReverseIterator(), I.getReverseIterator()))
 212       for (const MachineOperand &MO : MI.operands())
 213         if (MO.isRegMask())
 214           // FIXME: Shall we simultaneously invalidate AvailSrc or AvailDef?
 215           if (MO.clobbersPhysReg(AvailSrc) || MO.clobbersPhysReg(AvailDef))
 216             return nullptr;
 217
 218     return AvailCopy;
 219   }
 220
 221   MachineInstr *findAvailCopy(MachineInstr &DestCopy, MCRegister Reg,
 222                               const TargetRegisterInfo &TRI) {
 223     // We check the first RegUnit here, since we'll only be interested in the
 224     // copy if it copies the entire register anyway.
 225     MCRegUnitIterator RUI(Reg, &TRI);
 226     MachineInstr *AvailCopy =
 227         findCopyForUnit(*RUI, TRI, /*MustBeAvailable=*/true);
 228     if (!AvailCopy ||
 229         !TRI.isSubRegisterEq(AvailCopy->getOperand(0).getReg(), Reg))
 230       return nullptr;
 231
 232     // Check that the available copy isn't clobbered by any regmasks between
 233     // itself and the destination.
 234     Register AvailSrc = AvailCopy->getOperand(1).getReg();
 235     Register AvailDef = AvailCopy->getOperand(0).getReg();
 236     for (const MachineInstr &MI :
 237          make_range(AvailCopy->getIterator(), DestCopy.getIterator()))
 238       for (const MachineOperand &MO : MI.operands())
 239         if (MO.isRegMask())
 240           if (MO.clobbersPhysReg(AvailSrc) || MO.clobbersPhysReg(AvailDef))
 241             return nullptr;
 242
 243     return AvailCopy;
 244   }
 245
 246   void clear() {
 247     Copies.clear();
 248   }
 249 };
 250
 251 class MachineCopyPropagation : public MachineFunctionPass {
 252   const TargetRegisterInfo *TRI;
 253   const TargetInstrInfo *TII;
 254   const MachineRegisterInfo *MRI;
 255
 256 public:
 257   static char ID; // Pass identification, replacement for typeid
 258
 259   MachineCopyPropagation() : MachineFunctionPass(ID) {
 260     initializeMachineCopyPropagationPass(*PassRegistry::getPassRegistry());
 261   }
 262
 263   void getAnalysisUsage(AnalysisUsage &AU) const override {
 264     AU.setPreservesCFG();
 265     MachineFunctionPass::getAnalysisUsage(AU);
 266   }
 267
 268   bool runOnMachineFunction(MachineFunction &MF) override;
 269
 270   MachineFunctionProperties getRequiredProperties() const override {
 271     return MachineFunctionProperties().set(
 272         MachineFunctionProperties::Property::NoVRegs);
 273   }
 274
 275 private:
 276   typedef enum { DebugUse = false, RegularUse = true } DebugType;
 277
 278   void ReadRegister(MCRegister Reg, MachineInstr &Reader, DebugType DT);
 279   void ForwardCopyPropagateBlock(MachineBasicBlock &MBB);
 280   void BackwardCopyPropagateBlock(MachineBasicBlock &MBB);
 281   bool eraseIfRedundant(MachineInstr &Copy, MCRegister Src, MCRegister Def);
 282   void forwardUses(MachineInstr &MI);
 283   void propagateDefs(MachineInstr &MI);
 284   bool isForwardableRegClassCopy(const MachineInstr &Copy,
 285                                  const MachineInstr &UseI, unsigned UseIdx);
 286   bool isBackwardPropagatableRegClassCopy(const MachineInstr &Copy,
 287                                           const MachineInstr &UseI,
 288                                           unsigned UseIdx);
 289   bool hasImplicitOverlap(const MachineInstr &MI, const MachineOperand &Use);
 290   bool hasOverlappingMultipleDef(const MachineInstr &MI,
 291                                  const MachineOperand &MODef, Register Def);
 292
 293   /// Candidates for deletion.
 294   SmallSetVector<MachineInstr *, 8> MaybeDeadCopies;
 295
 296   /// Multimap tracking debug users in current BB
 297   DenseMap<MachineInstr *, SmallSet<MachineInstr *, 2>> CopyDbgUsers;
 298
 299   CopyTracker Tracker;
 300
 301   bool Changed;
 302 };
 303
 304 } // end anonymous namespace
 305
 306 char MachineCopyPropagation::ID = 0;
 307
 308 char &llvm::MachineCopyPropagationID = MachineCopyPropagation::ID;
 309
 310 INITIALIZE_PASS(MachineCopyPropagation, DEBUG_TYPE,
 311                 "Machine Copy Propagation Pass", false, false)
 312
 313 void MachineCopyPropagation::ReadRegister(MCRegister Reg, MachineInstr &Reader,
 314                                           DebugType DT) {
 315   // If 'Reg' is defined by a copy, the copy is no longer a candidate
 316   // for elimination. If a copy is "read" by a debug user, record the user
 317   // for propagation.
 318   for (MCRegUnitIterator RUI(Reg, TRI); RUI.isValid(); ++RUI) {
 319     if (MachineInstr *Copy = Tracker.findCopyForUnit(*RUI, *TRI)) {
 320       if (DT == RegularUse) {
 321         LLVM_DEBUG(dbgs() << "MCP: Copy is used - not dead: "; Copy->dump());
 322         MaybeDeadCopies.remove(Copy);
 323       } else {
 324         CopyDbgUsers[Copy].insert(&Reader);
 325       }
 326     }
 327   }
 328 }
 329
 330 /// Return true if \p PreviousCopy did copy register \p Src to register \p Def.
 331 /// This fact may have been obscured by sub register usage or may not be true at
 332 /// all even though Src and Def are subregisters of the registers used in
 333 /// PreviousCopy. e.g.
 334 /// isNopCopy("ecx = COPY eax", AX, CX) == true
 335 /// isNopCopy("ecx = COPY eax", AH, CL) == false
 336 static bool isNopCopy(const MachineInstr &PreviousCopy, MCRegister Src,
 337                       MCRegister Def, const TargetRegisterInfo *TRI) {
 338   MCRegister PreviousSrc = PreviousCopy.getOperand(1).getReg().asMCReg();
 339   MCRegister PreviousDef = PreviousCopy.getOperand(0).getReg().asMCReg();
 340   if (Src == PreviousSrc && Def == PreviousDef)
 341     return true;
 342   if (!TRI->isSubRegister(PreviousSrc, Src))
 343     return false;
 344   unsigned SubIdx = TRI->getSubRegIndex(PreviousSrc, Src);
 345   return SubIdx == TRI->getSubRegIndex(PreviousDef, Def);
 346 }
 347
 348 /// Remove instruction \p Copy if there exists a previous copy that copies the
 349 /// register \p Src to the register \p Def; This may happen indirectly by
 350 /// copying the super registers.
 351 bool MachineCopyPropagation::eraseIfRedundant(MachineInstr &Copy,
 352                                               MCRegister Src, MCRegister Def) {
 353   // Avoid eliminating a copy from/to a reserved registers as we cannot predict
 354   // the value (Example: The sparc zero register is writable but stays zero).
 355   if (MRI->isReserved(Src) || MRI->isReserved(Def))
 356     return false;
 357
 358   // Search for an existing copy.
 359   MachineInstr *PrevCopy = Tracker.findAvailCopy(Copy, Def, *TRI);
 360   if (!PrevCopy)
 361     return false;
 362
 363   // Check that the existing copy uses the correct sub registers.
 364   if (PrevCopy->getOperand(0).isDead())
 365     return false;
 366   if (!isNopCopy(*PrevCopy, Src, Def, TRI))
 367     return false;
 368
 369   LLVM_DEBUG(dbgs() << "MCP: copy is a NOP, removing: "; Copy.dump());
 370
 371   // Copy was redundantly redefining either Src or Def. Remove earlier kill
 372   // flags between Copy and PrevCopy because the value will be reused now.
 373   assert(Copy.isCopy());
 374   Register CopyDef = Copy.getOperand(0).getReg();
 375   assert(CopyDef == Src || CopyDef == Def);
 376   for (MachineInstr &MI :
 377        make_range(PrevCopy->getIterator(), Copy.getIterator()))
 378     MI.clearRegisterKills(CopyDef, TRI);
 379
 380   Copy.eraseFromParent();
 381   Changed = true;
 382   ++NumDeletes;
 383   return true;
 384 }
 385
 386 bool MachineCopyPropagation::isBackwardPropagatableRegClassCopy(
 387     const MachineInstr &Copy, const MachineInstr &UseI, unsigned UseIdx) {
 388   Register Def = Copy.getOperand(0).getReg();
 389
 390   if (const TargetRegisterClass *URC =
 391           UseI.getRegClassConstraint(UseIdx, TII, TRI))
 392     return URC->contains(Def);
 393
 394   // We don't process further if UseI is a COPY, since forward copy propagation
 395   // should handle that.
 396   return false;
 397 }
 398
 399 /// Decide whether we should forward the source of \param Copy to its use in
 400 /// \param UseI based on the physical register class constraints of the opcode
 401 /// and avoiding introducing more cross-class COPYs.
 402 bool MachineCopyPropagation::isForwardableRegClassCopy(const MachineInstr &Copy,
 403                                                        const MachineInstr &UseI,
 404                                                        unsigned UseIdx) {
 405
 406   Register CopySrcReg = Copy.getOperand(1).getReg();
 407
 408   // If the new register meets the opcode register constraints, then allow
 409   // forwarding.
 410   if (const TargetRegisterClass *URC =
 411           UseI.getRegClassConstraint(UseIdx, TII, TRI))
 412     return URC->contains(CopySrcReg);
 413
 414   if (!UseI.isCopy())
 415     return false;
 416
 417   const TargetRegisterClass *CopySrcRC =
 418       TRI->getMinimalPhysRegClass(CopySrcReg);
 419   const TargetRegisterClass *UseDstRC =
 420       TRI->getMinimalPhysRegClass(UseI.getOperand(0).getReg());
 421   const TargetRegisterClass *CrossCopyRC = TRI->getCrossCopyRegClass(CopySrcRC);
 422
 423   // If cross copy register class is not the same as copy source register class
 424   // then it is not possible to copy the register directly and requires a cross
 425   // register class copy. Fowarding this copy without checking register class of
 426   // UseDst may create additional cross register copies when expanding the copy
 427   // instruction in later passes.
 428   if (CopySrcRC != CrossCopyRC) {
 429     const TargetRegisterClass *CopyDstRC =
 430         TRI->getMinimalPhysRegClass(Copy.getOperand(0).getReg());
 431
 432     // Check if UseDstRC matches the necessary register class to copy from
 433     // CopySrc's register class. If so then forwarding the copy will not
 434     // introduce any cross-class copys. Else if CopyDstRC matches then keep the
 435     // copy and do not forward. If neither UseDstRC or CopyDstRC matches then
 436     // we may need a cross register copy later but we do not worry about it
 437     // here.
 438     if (UseDstRC != CrossCopyRC && CopyDstRC == CrossCopyRC)
 439       return false;
 440   }
 441
 442   /// COPYs don't have register class constraints, so if the user instruction
 443   /// is a COPY, we just try to avoid introducing additional cross-class
 444   /// COPYs.  For example:
 445   ///
 446   ///   RegClassA = COPY RegClassB  // Copy parameter
 447   ///   ...
 448   ///   RegClassB = COPY RegClassA  // UseI parameter
 449   ///
 450   /// which after forwarding becomes
 451   ///
 452   ///   RegClassA = COPY RegClassB
 453   ///   ...
 454   ///   RegClassB = COPY RegClassB
 455   ///
 456   /// so we have reduced the number of cross-class COPYs and potentially
 457   /// introduced a nop COPY that can be removed.
 458   const TargetRegisterClass *SuperRC = UseDstRC;
 459   for (TargetRegisterClass::sc_iterator SuperRCI = UseDstRC->getSuperClasses();
 460        SuperRC; SuperRC = *SuperRCI++)
 461     if (SuperRC->contains(CopySrcReg))
 462       return true;
 463
 464   return false;
 465 }
 466
 467 /// Check that \p MI does not have implicit uses that overlap with it's \p Use
 468 /// operand (the register being replaced), since these can sometimes be
 469 /// implicitly tied to other operands.  For example, on AMDGPU:
 470 ///
 471 /// V_MOVRELS_B32_e32 %VGPR2, %M0<imp-use>, %EXEC<imp-use>, %VGPR2_VGPR3_VGPR4_VGPR5<imp-use>
 472 ///
 473 /// the %VGPR2 is implicitly tied to the larger reg operand, but we have no
 474 /// way of knowing we need to update the latter when updating the former.
 475 bool MachineCopyPropagation::hasImplicitOverlap(const MachineInstr &MI,
 476                                                 const MachineOperand &Use) {
 477   for (const MachineOperand &MIUse : MI.uses())
 478     if (&MIUse != &Use && MIUse.isReg() && MIUse.isImplicit() &&
 479         MIUse.isUse() && TRI->regsOverlap(Use.getReg(), MIUse.getReg()))
 480       return true;
 481
 482   return false;
 483 }
 484
 485 /// For an MI that has multiple definitions, check whether \p MI has
 486 /// a definition that overlaps with another of its definitions.
 487 /// For example, on ARM: umull   r9, r9, lr, r0
 488 /// The umull instruction is unpredictable unless RdHi and RdLo are different.
 489 bool MachineCopyPropagation::hasOverlappingMultipleDef(
 490     const MachineInstr &MI, const MachineOperand &MODef, Register Def) {
 491   for (const MachineOperand &MIDef : MI.defs()) {
 492     if ((&MIDef != &MODef) && MIDef.isReg() &&
 493         TRI->regsOverlap(Def, MIDef.getReg()))
 494       return true;
 495   }
 496
 497   return false;
 498 }
 499
 500 /// Look for available copies whose destination register is used by \p MI and
 501 /// replace the use in \p MI with the copy's source register.
 502 void MachineCopyPropagation::forwardUses(MachineInstr &MI) {
 503   if (!Tracker.hasAnyCopies())
 504     return;
 505
 506   // Look for non-tied explicit vreg uses that have an active COPY
 507   // instruction that defines the physical register allocated to them.
 508   // Replace the vreg with the source of the active COPY.
 509   for (unsigned OpIdx = 0, OpEnd = MI.getNumOperands(); OpIdx < OpEnd;
 510        ++OpIdx) {
 511     MachineOperand &MOUse = MI.getOperand(OpIdx);
 512     // Don't forward into undef use operands since doing so can cause problems
 513     // with the machine verifier, since it doesn't treat undef reads as reads,
 514     // so we can end up with a live range that ends on an undef read, leading to
 515     // an error that the live range doesn't end on a read of the live range
 516     // register.
 517     if (!MOUse.isReg() || MOUse.isTied() || MOUse.isUndef() || MOUse.isDef() ||
 518         MOUse.isImplicit())
 519       continue;
 520
 521     if (!MOUse.getReg())
 522       continue;
 523
 524     // Check that the register is marked 'renamable' so we know it is safe to
 525     // rename it without violating any constraints that aren't expressed in the
 526     // IR (e.g. ABI or opcode requirements).
 527     if (!MOUse.isRenamable())
 528       continue;
 529
 530     MachineInstr *Copy =
 531         Tracker.findAvailCopy(MI, MOUse.getReg().asMCReg(), *TRI);
 532     if (!Copy)
 533       continue;
 534
 535     Register CopyDstReg = Copy->getOperand(0).getReg();
 536     const MachineOperand &CopySrc = Copy->getOperand(1);
 537     Register CopySrcReg = CopySrc.getReg();
 538
 539     // FIXME: Don't handle partial uses of wider COPYs yet.
 540     if (MOUse.getReg() != CopyDstReg) {
 541       LLVM_DEBUG(
 542           dbgs() << "MCP: FIXME! Not forwarding COPY to sub-register use:\n  "
 543                  << MI);
 544       continue;
 545     }
 546
 547     // Don't forward COPYs of reserved regs unless they are constant.
 548     if (MRI->isReserved(CopySrcReg) && !MRI->isConstantPhysReg(CopySrcReg))
 549       continue;
 550
 551     if (!isForwardableRegClassCopy(*Copy, MI, OpIdx))
 552       continue;
 553
 554     if (hasImplicitOverlap(MI, MOUse))
 555       continue;
 556
 557     // Check that the instruction is not a copy that partially overwrites the
 558     // original copy source that we are about to use. The tracker mechanism
 559     // cannot cope with that.
 560     if (MI.isCopy() && MI.modifiesRegister(CopySrcReg, TRI) &&
 561         !MI.definesRegister(CopySrcReg)) {
 562       LLVM_DEBUG(dbgs() << "MCP: Copy source overlap with dest in " << MI);
 563       continue;
 564     }
 565
 566     if (!DebugCounter::shouldExecute(FwdCounter)) {
 567       LLVM_DEBUG(dbgs() << "MCP: Skipping forwarding due to debug counter:\n  "
 568                         << MI);
 569       continue;
 570     }
 571
 572     LLVM_DEBUG(dbgs() << "MCP: Replacing " << printReg(MOUse.getReg(), TRI)
 573                       << "\n     with " << printReg(CopySrcReg, TRI)
 574                       << "\n     in " << MI << "     from " << *Copy);
 575
 576     MOUse.setReg(CopySrcReg);
 577     if (!CopySrc.isRenamable())
 578       MOUse.setIsRenamable(false);
 579     MOUse.setIsUndef(CopySrc.isUndef());
 580
 581     LLVM_DEBUG(dbgs() << "MCP: After replacement: " << MI << "\n");
 582
 583     // Clear kill markers that may have been invalidated.
 584     for (MachineInstr &KMI :
 585          make_range(Copy->getIterator(), std::next(MI.getIterator())))
 586       KMI.clearRegisterKills(CopySrcReg, TRI);
 587
 588     ++NumCopyForwards;
 589     Changed = true;
 590   }
 591 }
 592
 593 void MachineCopyPropagation::ForwardCopyPropagateBlock(MachineBasicBlock &MBB) {
 594   LLVM_DEBUG(dbgs() << "MCP: ForwardCopyPropagateBlock " << MBB.getName()
 595                     << "\n");
 596
 597   for (MachineInstr &MI : llvm::make_early_inc_range(MBB)) {
 598     // Analyze copies (which don't overlap themselves).
 599     if (MI.isCopy() && !TRI->regsOverlap(MI.getOperand(0).getReg(),
 600                                          MI.getOperand(1).getReg())) {
 601       assert(MI.getOperand(0).getReg().isPhysical() &&
 602              MI.getOperand(1).getReg().isPhysical() &&
 603              "MachineCopyPropagation should be run after register allocation!");
 604
 605       MCRegister Def = MI.getOperand(0).getReg().asMCReg();
 606       MCRegister Src = MI.getOperand(1).getReg().asMCReg();
 607
 608       // The two copies cancel out and the source of the first copy
 609       // hasn't been overridden, eliminate the second one. e.g.
 610       //  %ecx = COPY %eax
 611       //  ... nothing clobbered eax.
 612       //  %eax = COPY %ecx
 613       // =>
 614       //  %ecx = COPY %eax
 615       //
 616       // or
 617       //
 618       //  %ecx = COPY %eax
 619       //  ... nothing clobbered eax.
 620       //  %ecx = COPY %eax
 621       // =>
 622       //  %ecx = COPY %eax
 623       if (eraseIfRedundant(MI, Def, Src) || eraseIfRedundant(MI, Src, Def))
 624         continue;
 625
 626       forwardUses(MI);
 627
 628       // Src may have been changed by forwardUses()
 629       Src = MI.getOperand(1).getReg().asMCReg();
 630
 631       // If Src is defined by a previous copy, the previous copy cannot be
 632       // eliminated.
 633       ReadRegister(Src, MI, RegularUse);
 634       for (const MachineOperand &MO : MI.implicit_operands()) {
 635         if (!MO.isReg() || !MO.readsReg())
 636           continue;
 637         MCRegister Reg = MO.getReg().asMCReg();
 638         if (!Reg)
 639           continue;
 640         ReadRegister(Reg, MI, RegularUse);
 641       }
 642
 643       LLVM_DEBUG(dbgs() << "MCP: Copy is a deletion candidate: "; MI.dump());
 644
 645       // Copy is now a candidate for deletion.
 646       if (!MRI->isReserved(Def))
 647         MaybeDeadCopies.insert(&MI);
 648
 649       // If 'Def' is previously source of another copy, then this earlier copy's
 650       // source is no longer available. e.g.
 651       // %xmm9 = copy %xmm2
 652       // ...
 653       // %xmm2 = copy %xmm0
 654       // ...
 655       // %xmm2 = copy %xmm9
 656       Tracker.clobberRegister(Def, *TRI);
 657       for (const MachineOperand &MO : MI.implicit_operands()) {
 658         if (!MO.isReg() || !MO.isDef())
 659           continue;
 660         MCRegister Reg = MO.getReg().asMCReg();
 661         if (!Reg)
 662           continue;
 663         Tracker.clobberRegister(Reg, *TRI);
 664       }
 665
 666       Tracker.trackCopy(&MI, *TRI);
 667
 668       continue;
 669     }
 670
 671     // Clobber any earlyclobber regs first.
 672     for (const MachineOperand &MO : MI.operands())
 673       if (MO.isReg() && MO.isEarlyClobber()) {
 674         MCRegister Reg = MO.getReg().asMCReg();
 675         // If we have a tied earlyclobber, that means it is also read by this
 676         // instruction, so we need to make sure we don't remove it as dead
 677         // later.
 678         if (MO.isTied())
 679           ReadRegister(Reg, MI, RegularUse);
 680         Tracker.clobberRegister(Reg, *TRI);
 681       }
 682
 683     forwardUses(MI);
 684
 685     // Not a copy.
 686     SmallVector<Register, 2> Defs;
 687     const MachineOperand *RegMask = nullptr;
 688     for (const MachineOperand &MO : MI.operands()) {
 689       if (MO.isRegMask())
 690         RegMask = &MO;
 691       if (!MO.isReg())
 692         continue;
 693       Register Reg = MO.getReg();
 694       if (!Reg)
 695         continue;
 696
 697       assert(!Reg.isVirtual() &&
 698              "MachineCopyPropagation should be run after register allocation!");
 699
 700       if (MO.isDef() && !MO.isEarlyClobber()) {
 701         Defs.push_back(Reg.asMCReg());
 702         continue;
 703       } else if (MO.readsReg())
 704         ReadRegister(Reg.asMCReg(), MI, MO.isDebug() ? DebugUse : RegularUse);
 705     }
 706
 707     // The instruction has a register mask operand which means that it clobbers
 708     // a large set of registers.  Treat clobbered registers the same way as
 709     // defined registers.
 710     if (RegMask) {
 711       // Erase any MaybeDeadCopies whose destination register is clobbered.
 712       for (SmallSetVector<MachineInstr *, 8>::iterator DI =
 713                MaybeDeadCopies.begin();
 714            DI != MaybeDeadCopies.end();) {
 715         MachineInstr *MaybeDead = *DI;
 716         MCRegister Reg = MaybeDead->getOperand(0).getReg().asMCReg();
 717         assert(!MRI->isReserved(Reg));
 718
 719         if (!RegMask->clobbersPhysReg(Reg)) {
 720           ++DI;
 721           continue;
 722         }
 723
 724         LLVM_DEBUG(dbgs() << "MCP: Removing copy due to regmask clobbering: ";
 725                    MaybeDead->dump());
 726
 727         // Make sure we invalidate any entries in the copy maps before erasing
 728         // the instruction.
 729         Tracker.clobberRegister(Reg, *TRI);
 730
 731         // erase() will return the next valid iterator pointing to the next
 732         // element after the erased one.
 733         DI = MaybeDeadCopies.erase(DI);
 734         MaybeDead->eraseFromParent();
 735         Changed = true;
 736         ++NumDeletes;
 737       }
 738     }
 739
 740     // Any previous copy definition or reading the Defs is no longer available.
 741     for (MCRegister Reg : Defs)
 742       Tracker.clobberRegister(Reg, *TRI);
 743   }
 744
 745   // If MBB doesn't have successors, delete the copies whose defs are not used.
 746   // If MBB does have successors, then conservative assume the defs are live-out
 747   // since we don't want to trust live-in lists.
 748   if (MBB.succ_empty()) {
 749     for (MachineInstr *MaybeDead : MaybeDeadCopies) {
 750       LLVM_DEBUG(dbgs() << "MCP: Removing copy due to no live-out succ: ";
 751                  MaybeDead->dump());
 752       assert(!MRI->isReserved(MaybeDead->getOperand(0).getReg()));
 753
 754       // Update matching debug values, if any.
 755       assert(MaybeDead->isCopy());
 756       Register SrcReg = MaybeDead->getOperand(1).getReg();
 757       Register DestReg = MaybeDead->getOperand(0).getReg();
 758       SmallVector<MachineInstr *> MaybeDeadDbgUsers(
 759           CopyDbgUsers[MaybeDead].begin(), CopyDbgUsers[MaybeDead].end());
 760       MRI->updateDbgUsersToReg(DestReg.asMCReg(), SrcReg.asMCReg(),
 761                                MaybeDeadDbgUsers);
 762
 763       MaybeDead->eraseFromParent();
 764       Changed = true;
 765       ++NumDeletes;
 766     }
 767   }
 768
 769   MaybeDeadCopies.clear();
 770   CopyDbgUsers.clear();
 771   Tracker.clear();
 772 }
 773
 774 static bool isBackwardPropagatableCopy(MachineInstr &MI,
 775                                        const MachineRegisterInfo &MRI) {
 776   assert(MI.isCopy() && "MI is expected to be a COPY");
 777   Register Def = MI.getOperand(0).getReg();
 778   Register Src = MI.getOperand(1).getReg();
 779
 780   if (!Def || !Src)
 781     return false;
 782
 783   if (MRI.isReserved(Def) || MRI.isReserved(Src))
 784     return false;
 785
 786   return MI.getOperand(1).isRenamable() && MI.getOperand(1).isKill();
 787 }
 788
 789 void MachineCopyPropagation::propagateDefs(MachineInstr &MI) {
 790   if (!Tracker.hasAnyCopies())
 791     return;
 792
 793   for (unsigned OpIdx = 0, OpEnd = MI.getNumOperands(); OpIdx != OpEnd;
 794        ++OpIdx) {
 795     MachineOperand &MODef = MI.getOperand(OpIdx);
 796
 797     if (!MODef.isReg() || MODef.isUse())
 798       continue;
 799
 800     // Ignore non-trivial cases.
 801     if (MODef.isTied() || MODef.isUndef() || MODef.isImplicit())
 802       continue;
 803
 804     if (!MODef.getReg())
 805       continue;
 806
 807     // We only handle if the register comes from a vreg.
 808     if (!MODef.isRenamable())
 809       continue;
 810
 811     MachineInstr *Copy =
 812         Tracker.findAvailBackwardCopy(MI, MODef.getReg().asMCReg(), *TRI);
 813     if (!Copy)
 814       continue;
 815
 816     Register Def = Copy->getOperand(0).getReg();
 817     Register Src = Copy->getOperand(1).getReg();
 818
 819     if (MODef.getReg() != Src)
 820       continue;
 821
 822     if (!isBackwardPropagatableRegClassCopy(*Copy, MI, OpIdx))
 823       continue;
 824
 825     if (hasImplicitOverlap(MI, MODef))
 826       continue;
 827
 828     if (hasOverlappingMultipleDef(MI, MODef, Def))
 829       continue;
 830
 831     LLVM_DEBUG(dbgs() << "MCP: Replacing " << printReg(MODef.getReg(), TRI)
 832                       << "\n     with " << printReg(Def, TRI) << "\n     in "
 833                       << MI << "     from " << *Copy);
 834
 835     MODef.setReg(Def);
 836     MODef.setIsRenamable(Copy->getOperand(0).isRenamable());
 837
 838     LLVM_DEBUG(dbgs() << "MCP: After replacement: " << MI << "\n");
 839     MaybeDeadCopies.insert(Copy);
 840     Changed = true;
 841     ++NumCopyBackwardPropagated;
 842   }
 843 }
 844
 845 void MachineCopyPropagation::BackwardCopyPropagateBlock(
 846     MachineBasicBlock &MBB) {
 847   LLVM_DEBUG(dbgs() << "MCP: BackwardCopyPropagateBlock " << MBB.getName()
 848                     << "\n");
 849
 850   for (MachineInstr &MI : llvm::make_early_inc_range(llvm::reverse(MBB))) {
 851     // Ignore non-trivial COPYs.
 852     if (MI.isCopy() && MI.getNumOperands() == 2 &&
 853         !TRI->regsOverlap(MI.getOperand(0).getReg(),
 854                           MI.getOperand(1).getReg())) {
 855
 856       MCRegister Def = MI.getOperand(0).getReg().asMCReg();
 857       MCRegister Src = MI.getOperand(1).getReg().asMCReg();
 858
 859       // Unlike forward cp, we don't invoke propagateDefs here,
 860       // just let forward cp do COPY-to-COPY propagation.
 861       if (isBackwardPropagatableCopy(MI, *MRI)) {
 862         Tracker.invalidateRegister(Src, *TRI);
 863         Tracker.invalidateRegister(Def, *TRI);
 864         Tracker.trackCopy(&MI, *TRI);
 865         continue;
 866       }
 867     }
 868
 869     // Invalidate any earlyclobber regs first.
 870     for (const MachineOperand &MO : MI.operands())
 871       if (MO.isReg() && MO.isEarlyClobber()) {
 872         MCRegister Reg = MO.getReg().asMCReg();
 873         if (!Reg)
 874           continue;
 875         Tracker.invalidateRegister(Reg, *TRI);
 876       }
 877
 878     propagateDefs(MI);
 879     for (const MachineOperand &MO : MI.operands()) {
 880       if (!MO.isReg())
 881         continue;
 882
 883       if (!MO.getReg())
 884         continue;
 885
 886       if (MO.isDef())
 887         Tracker.invalidateRegister(MO.getReg().asMCReg(), *TRI);
 888
 889       if (MO.readsReg()) {
 890         if (MO.isDebug()) {
 891           //  Check if the register in the debug instruction is utilized
 892           // in a copy instruction, so we can update the debug info if the
 893           // register is changed.
 894           for (MCRegUnitIterator RUI(MO.getReg().asMCReg(), TRI); RUI.isValid();
 895                ++RUI) {
 896             if (auto *Copy = Tracker.findCopyDefViaUnit(*RUI, *TRI)) {
 897               CopyDbgUsers[Copy].insert(&MI);
 898             }
 899           }
 900         } else {
 901           Tracker.invalidateRegister(MO.getReg().asMCReg(), *TRI);
 902         }
 903       }
 904     }
 905   }
 906
 907   for (auto *Copy : MaybeDeadCopies) {
 908
 909     Register Src = Copy->getOperand(1).getReg();
 910     Register Def = Copy->getOperand(0).getReg();
 911     SmallVector<MachineInstr *> MaybeDeadDbgUsers(CopyDbgUsers[Copy].begin(),
 912                                                   CopyDbgUsers[Copy].end());
 913
 914     MRI->updateDbgUsersToReg(Src.asMCReg(), Def.asMCReg(), MaybeDeadDbgUsers);
 915     Copy->eraseFromParent();
 916     ++NumDeletes;
 917   }
 918
 919   MaybeDeadCopies.clear();
 920   CopyDbgUsers.clear();
 921   Tracker.clear();
 922 }
 923
 924 bool MachineCopyPropagation::runOnMachineFunction(MachineFunction &MF) {
 925   if (skipFunction(MF.getFunction()))
 926     return false;
 927
 928   Changed = false;
 929
 930   TRI = MF.getSubtarget().getRegisterInfo();
 931   TII = MF.getSubtarget().getInstrInfo();
 932   MRI = &MF.getRegInfo();
 933
 934   for (MachineBasicBlock &MBB : MF) {
 935     BackwardCopyPropagateBlock(MBB);
 936     ForwardCopyPropagateBlock(MBB);
 937   }
 938
 939   return Changed;
 940 }