vendor/llvm/llvm-trunk-r351319

1 files changed, 167 insertions, 129 deletions

diff --git a/lib/CodeGen/MachineCopyPropagation.cpp b/lib/CodeGen/MachineCopyPropagation.cpp
index 3bf8147a06c3..19879fe89007 100644
--- a/lib/CodeGen/MachineCopyPropagation.cpp
+++ b/lib/CodeGen/MachineCopyPropagation.cpp
@@ -74,58 +74,154 @@ DEBUG_COUNTER(FwdCounter, "machine-cp-fwd",
 
 namespace {
 
-using RegList = SmallVector<unsigned, 4>;
-using SourceMap = DenseMap<unsigned, RegList>;
-using Reg2MIMap = DenseMap<unsigned, MachineInstr *>;
-
-  class MachineCopyPropagation : public MachineFunctionPass {
-    const TargetRegisterInfo *TRI;
-    const TargetInstrInfo *TII;
-    const MachineRegisterInfo *MRI;
-
-  public:
-    static char ID; // Pass identification, replacement for typeid
+class CopyTracker {
+  struct CopyInfo {
+    MachineInstr *MI;
+    SmallVector<unsigned, 4> DefRegs;
+    bool Avail;
+  };
 
-    MachineCopyPropagation() : MachineFunctionPass(ID) {
-      initializeMachineCopyPropagationPass(*PassRegistry::getPassRegistry());
+  DenseMap<unsigned, CopyInfo> Copies;
+
+public:
+  /// Mark all of the given registers and their subregisters as unavailable for
+  /// copying.
+  void markRegsUnavailable(ArrayRef<unsigned> Regs,
+                           const TargetRegisterInfo &TRI) {
+    for (unsigned Reg : Regs) {
+      // Source of copy is no longer available for propagation.
+      for (MCRegUnitIterator RUI(Reg, &TRI); RUI.isValid(); ++RUI) {
+        auto CI = Copies.find(*RUI);
+        if (CI != Copies.end())
+          CI->second.Avail = false;
+      }
     }
+  }
 
-    void getAnalysisUsage(AnalysisUsage &AU) const override {
-      AU.setPreservesCFG();
-      MachineFunctionPass::getAnalysisUsage(AU);
+  /// Clobber a single register, removing it from the tracker's copy maps.
+  void clobberRegister(unsigned Reg, const TargetRegisterInfo &TRI) {
+    for (MCRegUnitIterator RUI(Reg, &TRI); RUI.isValid(); ++RUI) {
+      auto I = Copies.find(*RUI);
+      if (I != Copies.end()) {
+        // When we clobber the source of a copy, we need to clobber everything
+        // it defined.
+        markRegsUnavailable(I->second.DefRegs, TRI);
+        // When we clobber the destination of a copy, we need to clobber the
+        // whole register it defined.
+        if (MachineInstr *MI = I->second.MI)
+          markRegsUnavailable({MI->getOperand(0).getReg()}, TRI);
+        // Now we can erase the copy.
+        Copies.erase(I);
+      }
     }
+  }
+
+  /// Add this copy's registers into the tracker's copy maps.
+  void trackCopy(MachineInstr *MI, const TargetRegisterInfo &TRI) {
+    assert(MI->isCopy() && "Tracking non-copy?");
+
+    unsigned Def = MI->getOperand(0).getReg();
+    unsigned Src = MI->getOperand(1).getReg();
 
-    bool runOnMachineFunction(MachineFunction &MF) override;
+    // Remember Def is defined by the copy.
+    for (MCRegUnitIterator RUI(Def, &TRI); RUI.isValid(); ++RUI)
+      Copies[*RUI] = {MI, {}, true};
 
-    MachineFunctionProperties getRequiredProperties() const override {
-      return MachineFunctionProperties().set(
-          MachineFunctionProperties::Property::NoVRegs);
+    // Remember source that's copied to Def. Once it's clobbered, then
+    // it's no longer available for copy propagation.
+    for (MCRegUnitIterator RUI(Src, &TRI); RUI.isValid(); ++RUI) {
+      auto I = Copies.insert({*RUI, {nullptr, {}, false}});
+      auto &Copy = I.first->second;
+      if (!is_contained(Copy.DefRegs, Def))
+        Copy.DefRegs.push_back(Def);
     }
+  }
+
+  bool hasAnyCopies() {
+    return !Copies.empty();
+  }
 
-  private:
-    void ClobberRegister(unsigned Reg);
-    void ReadRegister(unsigned Reg);
-    void CopyPropagateBlock(MachineBasicBlock &MBB);
-    bool eraseIfRedundant(MachineInstr &Copy, unsigned Src, unsigned Def);
-    void forwardUses(MachineInstr &MI);
-    bool isForwardableRegClassCopy(const MachineInstr &Copy,
-                                   const MachineInstr &UseI, unsigned UseIdx);
-    bool hasImplicitOverlap(const MachineInstr &MI, const MachineOperand &Use);
+  MachineInstr *findCopyForUnit(unsigned RegUnit, const TargetRegisterInfo &TRI,
+                         bool MustBeAvailable = false) {
+    auto CI = Copies.find(RegUnit);
+    if (CI == Copies.end())
+      return nullptr;
+    if (MustBeAvailable && !CI->second.Avail)
+      return nullptr;
+    return CI->second.MI;
+  }
 
-    /// Candidates for deletion.
-    SmallSetVector<MachineInstr*, 8> MaybeDeadCopies;
+  MachineInstr *findAvailCopy(MachineInstr &DestCopy, unsigned Reg,
+                              const TargetRegisterInfo &TRI) {
+    // We check the first RegUnit here, since we'll only be interested in the
+    // copy if it copies the entire register anyway.
+    MCRegUnitIterator RUI(Reg, &TRI);
+    MachineInstr *AvailCopy =
+        findCopyForUnit(*RUI, TRI, /*MustBeAvailable=*/true);
+    if (!AvailCopy ||
+        !TRI.isSubRegisterEq(AvailCopy->getOperand(0).getReg(), Reg))
+      return nullptr;
+
+    // Check that the available copy isn't clobbered by any regmasks between
+    // itself and the destination.
+    unsigned AvailSrc = AvailCopy->getOperand(1).getReg();
+    unsigned AvailDef = AvailCopy->getOperand(0).getReg();
+    for (const MachineInstr &MI :
+         make_range(AvailCopy->getIterator(), DestCopy.getIterator()))
+      for (const MachineOperand &MO : MI.operands())
+        if (MO.isRegMask())
+          if (MO.clobbersPhysReg(AvailSrc) || MO.clobbersPhysReg(AvailDef))
+            return nullptr;
+
+    return AvailCopy;
+  }
 
-    /// Def -> available copies map.
-    Reg2MIMap AvailCopyMap;
+  void clear() {
+    Copies.clear();
+  }
+};
 
-    /// Def -> copies map.
-    Reg2MIMap CopyMap;
+class MachineCopyPropagation : public MachineFunctionPass {
+  const TargetRegisterInfo *TRI;
+  const TargetInstrInfo *TII;
+  const MachineRegisterInfo *MRI;
 
-    /// Src -> Def map
-    SourceMap SrcMap;
+public:
+  static char ID; // Pass identification, replacement for typeid
 
-    bool Changed;
-  };
+  MachineCopyPropagation() : MachineFunctionPass(ID) {
+    initializeMachineCopyPropagationPass(*PassRegistry::getPassRegistry());
+  }
+
+  void getAnalysisUsage(AnalysisUsage &AU) const override {
+    AU.setPreservesCFG();
+    MachineFunctionPass::getAnalysisUsage(AU);
+  }
+
+  bool runOnMachineFunction(MachineFunction &MF) override;
+
+  MachineFunctionProperties getRequiredProperties() const override {
+    return MachineFunctionProperties().set(
+        MachineFunctionProperties::Property::NoVRegs);
+  }
+
+private:
+  void ClobberRegister(unsigned Reg);
+  void ReadRegister(unsigned Reg);
+  void CopyPropagateBlock(MachineBasicBlock &MBB);
+  bool eraseIfRedundant(MachineInstr &Copy, unsigned Src, unsigned Def);
+  void forwardUses(MachineInstr &MI);
+  bool isForwardableRegClassCopy(const MachineInstr &Copy,
+                                 const MachineInstr &UseI, unsigned UseIdx);
+  bool hasImplicitOverlap(const MachineInstr &MI, const MachineOperand &Use);
+
+  /// Candidates for deletion.
+  SmallSetVector<MachineInstr *, 8> MaybeDeadCopies;
+
+  CopyTracker Tracker;
+
+  bool Changed;
+};
 
 } // end anonymous namespace
 
@@ -136,54 +232,13 @@ char &llvm::MachineCopyPropagationID = MachineCopyPropagation::ID;
 INITIALIZE_PASS(MachineCopyPropagation, DEBUG_TYPE,
                 "Machine Copy Propagation Pass", false, false)
 
-/// Remove any entry in \p Map where the register is a subregister or equal to
-/// a register contained in \p Regs.
-static void removeRegsFromMap(Reg2MIMap &Map, const RegList &Regs,
-                              const TargetRegisterInfo &TRI) {
-  for (unsigned Reg : Regs) {
-    // Source of copy is no longer available for propagation.
-    for (MCSubRegIterator SR(Reg, &TRI, true); SR.isValid(); ++SR)
-      Map.erase(*SR);
-  }
-}
-
-/// Remove any entry in \p Map that is marked clobbered in \p RegMask.
-/// The map will typically have a lot fewer entries than the regmask clobbers,
-/// so this is more efficient than iterating the clobbered registers and calling
-/// ClobberRegister() on them.
-static void removeClobberedRegsFromMap(Reg2MIMap &Map,
-                                       const MachineOperand &RegMask) {
-  for (Reg2MIMap::iterator I = Map.begin(), E = Map.end(), Next; I != E;
-       I = Next) {
-    Next = std::next(I);
-    unsigned Reg = I->first;
-    if (RegMask.clobbersPhysReg(Reg))
-      Map.erase(I);
-  }
-}
-
-void MachineCopyPropagation::ClobberRegister(unsigned Reg) {
-  for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) {
-    CopyMap.erase(*AI);
-    AvailCopyMap.erase(*AI);
-
-    SourceMap::iterator SI = SrcMap.find(*AI);
-    if (SI != SrcMap.end()) {
-      removeRegsFromMap(AvailCopyMap, SI->second, *TRI);
-      SrcMap.erase(SI);
-    }
-  }
-}
-
 void MachineCopyPropagation::ReadRegister(unsigned Reg) {
   // If 'Reg' is defined by a copy, the copy is no longer a candidate
   // for elimination.
-  for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) {
-    Reg2MIMap::iterator CI = CopyMap.find(*AI);
-    if (CI != CopyMap.end()) {
-      LLVM_DEBUG(dbgs() << "MCP: Copy is used - not dead: ";
-                 CI->second->dump());
-      MaybeDeadCopies.remove(CI->second);
+  for (MCRegUnitIterator RUI(Reg, TRI); RUI.isValid(); ++RUI) {
+    if (MachineInstr *Copy = Tracker.findCopyForUnit(*RUI, *TRI)) {
+      LLVM_DEBUG(dbgs() << "MCP: Copy is used - not dead: "; Copy->dump());
+      MaybeDeadCopies.remove(Copy);
     }
   }
 }
@@ -219,15 +274,14 @@ bool MachineCopyPropagation::eraseIfRedundant(MachineInstr &Copy, unsigned Src,
     return false;
 
   // Search for an existing copy.
-  Reg2MIMap::iterator CI = AvailCopyMap.find(Def);
-  if (CI == AvailCopyMap.end())
+  MachineInstr *PrevCopy = Tracker.findAvailCopy(Copy, Def, *TRI);
+  if (!PrevCopy)
     return false;
 
   // Check that the existing copy uses the correct sub registers.
-  MachineInstr &PrevCopy = *CI->second;
-  if (PrevCopy.getOperand(0).isDead())
+  if (PrevCopy->getOperand(0).isDead())
     return false;
-  if (!isNopCopy(PrevCopy, Src, Def, TRI))
+  if (!isNopCopy(*PrevCopy, Src, Def, TRI))
     return false;
 
   LLVM_DEBUG(dbgs() << "MCP: copy is a NOP, removing: "; Copy.dump());
@@ -238,7 +292,7 @@ bool MachineCopyPropagation::eraseIfRedundant(MachineInstr &Copy, unsigned Src,
   unsigned CopyDef = Copy.getOperand(0).getReg();
   assert(CopyDef == Src || CopyDef == Def);
   for (MachineInstr &MI :
-       make_range(PrevCopy.getIterator(), Copy.getIterator()))
+       make_range(PrevCopy->getIterator(), Copy.getIterator()))
     MI.clearRegisterKills(CopyDef, TRI);
 
   Copy.eraseFromParent();
@@ -314,7 +368,7 @@ bool MachineCopyPropagation::hasImplicitOverlap(const MachineInstr &MI,
 /// Look for available copies whose destination register is used by \p MI and
 /// replace the use in \p MI with the copy's source register.
 void MachineCopyPropagation::forwardUses(MachineInstr &MI) {
-  if (AvailCopyMap.empty())
+  if (!Tracker.hasAnyCopies())
     return;
 
   // Look for non-tied explicit vreg uses that have an active COPY
@@ -341,13 +395,12 @@ void MachineCopyPropagation::forwardUses(MachineInstr &MI) {
     if (!MOUse.isRenamable())
       continue;
 
-    auto CI = AvailCopyMap.find(MOUse.getReg());
-    if (CI == AvailCopyMap.end())
+    MachineInstr *Copy = Tracker.findAvailCopy(MI, MOUse.getReg(), *TRI);
+    if (!Copy)
       continue;
 
-    MachineInstr &Copy = *CI->second;
-    unsigned CopyDstReg = Copy.getOperand(0).getReg();
-    const MachineOperand &CopySrc = Copy.getOperand(1);
+    unsigned CopyDstReg = Copy->getOperand(0).getReg();
+    const MachineOperand &CopySrc = Copy->getOperand(1);
     unsigned CopySrcReg = CopySrc.getReg();
 
     // FIXME: Don't handle partial uses of wider COPYs yet.
@@ -362,7 +415,7 @@ void MachineCopyPropagation::forwardUses(MachineInstr &MI) {
     if (MRI->isReserved(CopySrcReg) && !MRI->isConstantPhysReg(CopySrcReg))
       continue;
 
-    if (!isForwardableRegClassCopy(Copy, MI, OpIdx))
+    if (!isForwardableRegClassCopy(*Copy, MI, OpIdx))
       continue;
 
     if (hasImplicitOverlap(MI, MOUse))
@@ -376,7 +429,7 @@ void MachineCopyPropagation::forwardUses(MachineInstr &MI) {
 
     LLVM_DEBUG(dbgs() << "MCP: Replacing " << printReg(MOUse.getReg(), TRI)
                       << "\n     with " << printReg(CopySrcReg, TRI)
-                      << "\n     in " << MI << "     from " << Copy);
+                      << "\n     in " << MI << "     from " << *Copy);
 
     MOUse.setReg(CopySrcReg);
     if (!CopySrc.isRenamable())
@@ -386,7 +439,7 @@ void MachineCopyPropagation::forwardUses(MachineInstr &MI) {
 
     // Clear kill markers that may have been invalidated.
     for (MachineInstr &KMI :
-         make_range(Copy.getIterator(), std::next(MI.getIterator())))
+         make_range(Copy->getIterator(), std::next(MI.getIterator())))
       KMI.clearRegisterKills(CopySrcReg, TRI);
 
     ++NumCopyForwards;
@@ -459,28 +512,17 @@ void MachineCopyPropagation::CopyPropagateBlock(MachineBasicBlock &MBB) {
       // %xmm2 = copy %xmm0
       // ...
       // %xmm2 = copy %xmm9
-      ClobberRegister(Def);
+      Tracker.clobberRegister(Def, *TRI);
       for (const MachineOperand &MO : MI->implicit_operands()) {
         if (!MO.isReg() || !MO.isDef())
           continue;
         unsigned Reg = MO.getReg();
         if (!Reg)
           continue;
-        ClobberRegister(Reg);
+        Tracker.clobberRegister(Reg, *TRI);
       }
 
-      // Remember Def is defined by the copy.
-      for (MCSubRegIterator SR(Def, TRI, /*IncludeSelf=*/true); SR.isValid();
-           ++SR) {
-        CopyMap[*SR] = MI;
-        AvailCopyMap[*SR] = MI;
-      }
-
-      // Remember source that's copied to Def. Once it's clobbered, then
-      // it's no longer available for copy propagation.
-      RegList &DestList = SrcMap[Src];
-      if (!is_contained(DestList, Def))
-          DestList.push_back(Def);
+      Tracker.trackCopy(MI, *TRI);
 
       continue;
     }
@@ -494,7 +536,7 @@ void MachineCopyPropagation::CopyPropagateBlock(MachineBasicBlock &MBB) {
         // later.
         if (MO.isTied())
           ReadRegister(Reg);
-        ClobberRegister(Reg);
+        Tracker.clobberRegister(Reg, *TRI);
       }
 
     forwardUses(*MI);
@@ -541,6 +583,10 @@ void MachineCopyPropagation::CopyPropagateBlock(MachineBasicBlock &MBB) {
         LLVM_DEBUG(dbgs() << "MCP: Removing copy due to regmask clobbering: ";
                    MaybeDead->dump());
 
+        // Make sure we invalidate any entries in the copy maps before erasing
+        // the instruction.
+        Tracker.clobberRegister(Reg, *TRI);
+
         // erase() will return the next valid iterator pointing to the next
         // element after the erased one.
         DI = MaybeDeadCopies.erase(DI);
@@ -548,22 +594,11 @@ void MachineCopyPropagation::CopyPropagateBlock(MachineBasicBlock &MBB) {
         Changed = true;
         ++NumDeletes;
       }
-
-      removeClobberedRegsFromMap(AvailCopyMap, *RegMask);
-      removeClobberedRegsFromMap(CopyMap, *RegMask);
-      for (SourceMap::iterator I = SrcMap.begin(), E = SrcMap.end(), Next;
-           I != E; I = Next) {
-        Next = std::next(I);
-        if (RegMask->clobbersPhysReg(I->first)) {
-          removeRegsFromMap(AvailCopyMap, I->second, *TRI);
-          SrcMap.erase(I);
-        }
-      }
     }
 
     // Any previous copy definition or reading the Defs is no longer available.
     for (unsigned Reg : Defs)
-      ClobberRegister(Reg);
+      Tracker.clobberRegister(Reg, *TRI);
   }
 
   // If MBB doesn't have successors, delete the copies whose defs are not used.
@@ -574,6 +609,11 @@ void MachineCopyPropagation::CopyPropagateBlock(MachineBasicBlock &MBB) {
       LLVM_DEBUG(dbgs() << "MCP: Removing copy due to no live-out succ: ";
                  MaybeDead->dump());
       assert(!MRI->isReserved(MaybeDead->getOperand(0).getReg()));
+
+      // Update matching debug values.
+      assert(MaybeDead->isCopy());
+      MaybeDead->changeDebugValuesDefReg(MaybeDead->getOperand(1).getReg());
+
       MaybeDead->eraseFromParent();
       Changed = true;
       ++NumDeletes;
@@ -581,9 +621,7 @@ void MachineCopyPropagation::CopyPropagateBlock(MachineBasicBlock &MBB) {
   }
 
   MaybeDeadCopies.clear();
-  AvailCopyMap.clear();
-  CopyMap.clear();
-  SrcMap.clear();
+  Tracker.clear();
 }
 
 bool MachineCopyPropagation::runOnMachineFunction(MachineFunction &MF) {