[MachineCopyPropagation] Rework how we manage RegMask clobbers

[bogner]

Summary

Instead of updating the CopyTracker's maps each time we come across a
RegMask, defer checking for this kind of interference until we're
actually trying to propagate a copy. This avoids the need to
repeatedly iterate over maps in the cases where we don't end up doing
any work.

This is a slight compile time improvement for MachineCopyPropagation
as is, but it also enables a much bigger improvement that I'll follow
up with soon.

[MatzeB]

LGTM

lib/CodeGen/MachineCopyPropagation.cpp

263 ↗

(On Diff #166516)

Can you add a comment here along the lines of "we haven't checked regmasks yet, do this now".

Can this be expressed as range based for? (something like `for (const MachineInstr &MI : make_range(PrevCopy->getIterator(), Copy.getIterator()))`?

266–273 ↗

(On Diff #166516)

why not just check the regmask operand inside the loop? Should make the code simpler and get away with the artifical restriction to a single regmask operand per instruction (not that there is any sensible usecase for multiple but anyway...)

[bogner]

I'd accidentally sent an old version of the patch for the review originally, which didn't quite work. This one is correct and also incorporates Matthias's feedback.

[bogner]

lib/CodeGen/MachineCopyPropagation.cpp

263 ↗

(On Diff #166516)

Done and done. I'm not entirely convinced the range-for is any more readable in this case, but it isn't worse either.

575–577 ↗

(On Diff #166772)

This was missing in the version of the patch I uploaded before, which led to use-after-frees.

[MatzeB]

I'm convinced now the clobbering works correctly because as clobberRegister does not just clobber the register at hand but the whole destination register of the copy touched by the COPY at hand.
LGTM

[bogner]

In D52370#1244084, @MatzeB wrote:

I'm convinced now the clobbering works correctly because as clobberRegister does not just clobber the register at hand but the whole destination register of the copy touched by the COPY at hand.
LGTM

Was this meant for D52374? You already LGTM'd this one ;)

llvm/trunk/lib/CodeGen/MachineCopyPropagation.cpp

public:
   void markRegsUnavailable(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)
         AvailCopyMap.erase(*SR);
     }
   }
 
-  /// Remove any entry in the tracker's copy maps 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.
-  void removeClobberedRegs(const MachineOperand &RegMask,
-                           const TargetRegisterInfo &TRI) {
-    auto RemoveFromMap = [&RegMask](Reg2MIMap &Map) {
-      for (Reg2MIMap::iterator I = Map.begin(), E = Map.end(), Next; I != E;
-           I = Next) {
-        Next = std::next(I);
-        if (RegMask.clobbersPhysReg(I->first))
-          Map.erase(I);
-      }
-    };
-    RemoveFromMap(AvailCopyMap);
-    RemoveFromMap(CopyMap);
-
-    for (SourceMap::iterator I = SrcMap.begin(), E = SrcMap.end(), Next; I != E;
-         I = Next) {
-      Next = std::next(I);
-      if (RegMask.clobbersPhysReg(I->first)) {
-        markRegsUnavailable(I->second, TRI);
-        SrcMap.erase(I);
-      }
-    }
-  }
-
   /// Clobber a single register, removing it from the tracker's copy maps.
   void clobberRegister(unsigned Reg, const TargetRegisterInfo &TRI) {
     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()) {
void trackCopy(MachineInstr *Copy, const TargetRegisterInfo &TRI) {
     // it's no longer available for copy propagation.
     RegList &DestList = SrcMap[Src];
     if (!is_contained(DestList, Def))
       DestList.push_back(Def);
   }
 
   bool hasAvailableCopies() { return !AvailCopyMap.empty(); }
 
-  MachineInstr *findAvailCopy(unsigned Reg) {
+  MachineInstr *findAvailCopy(MachineInstr &DestCopy, unsigned Reg) {
     auto CI = AvailCopyMap.find(Reg);
-    if (CI != AvailCopyMap.end())
-      return CI->second;
+    if (CI == AvailCopyMap.end())
       return nullptr;
+    MachineInstr &AvailCopy = *CI->second;
+
+    // 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;
   }
 
   MachineInstr *findCopy(unsigned Reg) {
     auto CI = CopyMap.find(Reg);
     if (CI != CopyMap.end())
       return CI->second;
     return nullptr;
   }

 bool MachineCopyPropagation::eraseIfRedundant(MachineInstr &Copy, unsigned Src,
                                               unsigned Def) {
   // Avoid eliminating a copy from/to a reserved registers as we cannot predict
   // the value (Example: The sparc zero register is writable but stays zero).
   if (MRI->isReserved(Src) || MRI->isReserved(Def))
     return false;
 
   // Search for an existing copy.
-  MachineInstr *PrevCopy = Tracker.findAvailCopy(Def);
+  MachineInstr *PrevCopy = Tracker.findAvailCopy(Copy, Def);
   if (!PrevCopy)
     return false;
 
   // Check that the existing copy uses the correct sub registers.
   if (PrevCopy->getOperand(0).isDead())
     return false;
   if (!isNopCopy(*PrevCopy, Src, Def, TRI))
     return false;
if (!MOUse.getReg())
       continue;
 
     // Check that the register is marked 'renamable' so we know it is safe to
     // rename it without violating any constraints that aren't expressed in the
     // IR (e.g. ABI or opcode requirements).
     if (!MOUse.isRenamable())
       continue;
 
-    MachineInstr *Copy = Tracker.findAvailCopy(MOUse.getReg());
+    MachineInstr *Copy = Tracker.findAvailCopy(MI, MOUse.getReg());
     if (!Copy)
       continue;
 
     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.
if (RegMask) {
         if (!RegMask->clobbersPhysReg(Reg)) {
           ++DI;
           continue;
         }
 
         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);
         MaybeDead->eraseFromParent();
         Changed = true;
         ++NumDeletes;
       }
-
-      Tracker.removeClobberedRegs(*RegMask, *TRI);
     }
 
     // Any previous copy definition or reading the Defs is no longer available.
     for (unsigned Reg : Defs)
       Tracker.clobberRegister(Reg, *TRI);
   }
 
   // If MBB doesn't have successors, delete the copies whose defs are not used.