MachineCopyPropagation: Keep scanning through instructions with regmasks

[qcolombet]

lib/CodeGen/MachineCopyPropagation.cpp

99 ↗

(On Diff #48572)

Period.

105 ↗

(On Diff #48572)

Although I doubt it happens in practice, MIs might have several RegMask operands.
(After scanning through the uses of getRegMask(), it looks to me that this pass is the only one that would do wrong thing with several regmasks. It happened before this patch, e.g., line 238, and thus we can fix as a follow-up patch.)
Can’t we just return false if Reg is clobbered instead of checking if it is preserved?

278 ↗

(On Diff #48572)

Update this comment, the end is no more relevant.

307 ↗

(On Diff #48572)

We could factorize the two previous loops into a helper function.

[MatzeB]

This is an updated version which simply removes the NoInterveningSideEffects(). From the commit description:

This also simplifies the code by removing the overly conservative
NoInterveningSideEffect() function. This function checked:

• That the two copies belong to the same block: We only process one block at a time and clear our maps in between it is impossible to find a copy from a different block.
• There is no terminator between the two copy instructions: This is not allowed anyway (the MachineVerifier would complain)
• Does not have instructions with hasUnmodeledSideEffects() or isCall() set: Even for those instructuction we must have all clobbers/defs of registers explicit as an operand. If the register is explicitely clobbered we would never come to the point of checking for NoInterveningSideEffect() anyway.

(I also checked this with a temporary build of the test-suite with all
potentially failing conditions in NoInterveningSideEffect() turned into
asserts)

[junbuml]

lib/CodeGen/MachineCopyPropagation.cpp

281–286 ↗

(On Diff #48771)

This code looks same as the last part of SourceNoLongerAvailable(). We could make a helper function shared in here and in SourceNoLongerAvailable().

[qcolombet]

Hi Matthias,

Nice clean up.

Looks good to me, modulo my inlined comments for the test cases.
Please also look into Jun's comment.

Thanks,
-Quentin

test/CodeGen/X86/machine-copy-prop.mir

8 ↗

(On Diff #48771)

Could you add a comment on what this function is testing?
Something pretty obvious like check that copy propagation manages to propagate across calls when the registers are preserved.

21 ↗

(On Diff #48771)

Add another test where the copy cannot be propagated because of clobbered registers.

[MatzeB]

New revision which splits SourceNoLongerAvailable() into two new functions: ClobberCopySources(), ClobberRegister() so the code that is now in ClobberCopySources() can be reused for the regmask case.
The tests have also been extended to cover negative cases and check for kill flag clearing.

[qcolombet]

lib/CodeGen/MachineCopyPropagation.cpp

93 ↗

(On Diff #48855)

Any reason why the two loops are not merged?

129 ↗

(On Diff #48855)

I was wondering if it would be more efficient to traverse the clobbered registers and erase the entries in the map accordingly, but I figured the map is usually pretty small.
Maybe add a comment on that so that we don't have to think about it when we come across the code again.

test/CodeGen/X86/machine-copy-prop.mir

1 ↗

(On Diff #48855)

-verify-machineinstrs?

13 ↗

(On Diff #48855)

typo -> redundant

[junbuml]

lib/CodeGen/MachineCopyPropagation.cpp

74 ↗

(On Diff #48855)

I doubt if this method name well describe what it does. For me this method seems simply erase all (sub)regs in RegList from AvailCopyMap.

286 ↗

(On Diff #48855)

Maybe ?

if (RegMask->clobbersPhysReg(I->first)) {
  ClobberCopySources(I->second);
  SrcMap.erase(I);
}

[MatzeB]

Thanks for the reviews. New version addressing the comments.

lib/CodeGen/MachineCopyPropagation.cpp

74 ↗

(On Diff #48855)

Renamed it to removeRegsFromMap() and transformed it into a static function similar to removeClobberedRegsFromMap()

93 ↗

(On Diff #48855)

No, they previously just haven't been that close together and not 100% the same, so I didn't see it.

129 ↗

(On Diff #48855)

Yes that it is indeed the reason, I will add a comment.

286 ↗

(On Diff #48855)

indeed, fixed.

test/CodeGen/X86/machine-copy-prop.mir

1 ↗

(On Diff #48855)

Turned out -verify-machineinstrs is a separate pass and won't run anyway when "llc -run-pass XXX" is used. Fixing that is for another commit.

[qcolombet]

Even more LGTM now :).

llvm/trunk/lib/CodeGen/MachineCopyPropagation.cpp

 #include "llvm/Target/TargetSubtargetInfo.h"
 using namespace llvm;
 
 #define DEBUG_TYPE "codegen-cp"
 
 STATISTIC(NumDeletes, "Number of dead copies deleted");
 
 namespace {
+  typedef SmallVector<unsigned, 4> RegList;
+  typedef DenseMap<unsigned, RegList> SourceMap;
+  typedef DenseMap<unsigned, MachineInstr*> Reg2MIMap;
+
   class MachineCopyPropagation : public MachineFunctionPass {
     const TargetRegisterInfo *TRI;
     const TargetInstrInfo *TII;
     const MachineRegisterInfo *MRI;
 
   public:
     static char ID; // Pass identification, replacement for typeid
     MachineCopyPropagation() : MachineFunctionPass(ID) {
       initializeMachineCopyPropagationPass(*PassRegistry::getPassRegistry());
     }
 
     bool runOnMachineFunction(MachineFunction &MF) override;
 
   private:
-    typedef SmallVector<unsigned, 4> DestList;
-    typedef DenseMap<unsigned, DestList> SourceMap;
-    typedef DenseMap<unsigned, MachineInstr*> Reg2MIMap;
-
-    void SourceNoLongerAvailable(unsigned Reg);
+    void ClobberRegister(unsigned Reg);
     void CopyPropagateBlock(MachineBasicBlock &MBB);
 
     /// Candidates for deletion.
     SmallSetVector<MachineInstr*, 8> MaybeDeadCopies;
     /// Def -> available copies map.
     Reg2MIMap AvailCopyMap;
     /// Def -> copies map.
     Reg2MIMap CopyMap;
     /// Src -> Def map
     SourceMap SrcMap;
     bool Changed;
   };
 }
 char MachineCopyPropagation::ID = 0;
 char &llvm::MachineCopyPropagationID = MachineCopyPropagation::ID;
 
 INITIALIZE_PASS(MachineCopyPropagation, "machine-cp",
                 "Machine Copy Propagation Pass", false, false)
 
-void MachineCopyPropagation::SourceNoLongerAvailable(unsigned Reg) {
-  for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) {
-    SourceMap::iterator SI = SrcMap.find(*AI);
-    if (SI != SrcMap.end()) {
-      const DestList& Defs = SI->second;
-      for (unsigned MappedDef : Defs) {
-        // Source of copy is no longer available for propagation.
-        for (MCSubRegIterator SR(MappedDef, TRI, true); SR.isValid(); ++SR)
-          AvailCopyMap.erase(*SR);
-      }
-    }
+/// 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) {
+    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);
   }
 }
 
-static bool NoInterveningSideEffect(const MachineInstr *CopyMI,
-                                    const MachineInstr *MI) {
-  const MachineBasicBlock *MBB = CopyMI->getParent();
-  if (MI->getParent() != MBB)
-    return false;
+void MachineCopyPropagation::ClobberRegister(unsigned Reg) {
+  for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) {
+    CopyMap.erase(*AI);
+    AvailCopyMap.erase(*AI);
 
-  for (MachineBasicBlock::const_iterator I = std::next(CopyMI->getIterator()),
-       E = MBB->end(), E2 = MI->getIterator(); I != E && I != E2; ++I) {
-    if (I->hasUnmodeledSideEffects() || I->isCall() ||
-        I->isTerminator())
-      return false;
+    SourceMap::iterator SI = SrcMap.find(*AI);
+    if (SI != SrcMap.end()) {
+      removeRegsFromMap(AvailCopyMap, SI->second, *TRI);
+      SrcMap.erase(SI);
+    }
   }
-  return true;
 }
 
 /// isNopCopy - Return true if the specified copy is really a nop. That is
 /// if the source of the copy is the same of the definition of the copy that
 /// supplied the source. If the source of the copy is a sub-register than it
 /// must check the sub-indices match. e.g.
 /// ecx = mov eax
 /// al  = mov cl
if (MI->isCopy()) {
 
       assert(!TargetRegisterInfo::isVirtualRegister(Def) &&
              !TargetRegisterInfo::isVirtualRegister(Src) &&
              "MachineCopyPropagation should be run after register allocation!");
 
       DenseMap<unsigned, MachineInstr*>::iterator CI = AvailCopyMap.find(Src);
       if (CI != AvailCopyMap.end()) {
         MachineInstr *CopyMI = CI->second;
-        if (!MRI->isReserved(Def) &&
-            (!MRI->isReserved(Src) || NoInterveningSideEffect(CopyMI, MI)) &&
-            isNopCopy(CopyMI, Def, Src, TRI)) {
+        if (!MRI->isReserved(Def) && isNopCopy(CopyMI, Def, Src, TRI)) {
           // The two copies cancel out and the source of the first copy
           // hasn't been overridden, eliminate the second one. e.g.
           //  %ECX<def> = COPY %EAX<kill>
           //  ... nothing clobbered EAX.
           //  %EAX<def> = COPY %ECX
           // =>
           //  %ECX<def> = COPY %EAX
           //
if (MI->isCopy()) {
 
       // If 'Def' is previously source of another copy, then this earlier copy's
       // source is no longer available. e.g.
       // %xmm9<def> = copy %xmm2
       // ...
       // %xmm2<def> = copy %xmm0
       // ...
       // %xmm2<def> = copy %xmm9
-      SourceNoLongerAvailable(Def);
+      ClobberRegister(Def);
 
       // Remember Def is defined by the copy.
-      // ... Make sure to clear the def maps of aliases first.
-      for (MCRegAliasIterator AI(Def, TRI, false); AI.isValid(); ++AI) {
-        CopyMap.erase(*AI);
-        AvailCopyMap.erase(*AI);
-      }
       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.
-      SmallVectorImpl<unsigned> &DestList = SrcMap[Src];
+      RegList &DestList = SrcMap[Src];
       if (std::find(DestList.begin(), DestList.end(), Def) == DestList.end())
         DestList.push_back(Def);
 
       continue;
     }
 
     // Not a copy.
     SmallVector<unsigned, 2> Defs;
for (const MachineOperand &MO : MI->operands()) {
       // The backends are allowed to do whatever they want with undef value
       // and we cannot be sure this register will not be rewritten to break
       // some false dependencies for the hardware for instance.
       if (MO.isUndef())
         Defs.push_back(Reg);
     }
 
     // The instruction has a register mask operand which means that it clobbers
-    // a large set of registers.  It is possible to use the register mask to
-    // prune the available copies, but treat it like a basic block boundary for
-    // now.
+    // a large set of registers.  Treat clobbered registers the same way as
+    // defined registers.
     if (RegMask) {
       // Erase any MaybeDeadCopies whose destination register is clobbered.
       for (MachineInstr *MaybeDead : MaybeDeadCopies) {
         unsigned Reg = MaybeDead->getOperand(0).getReg();
         assert(!MRI->isReserved(Reg));
         if (!RegMask->clobbersPhysReg(Reg))
           continue;
         DEBUG(dbgs() << "MCP: Removing copy due to regmask clobbering: ";
               MaybeDead->dump());
         MaybeDead->eraseFromParent();
         Changed = true;
         ++NumDeletes;
       }
-
-      // Clear all data structures as if we were beginning a new basic block.
       MaybeDeadCopies.clear();
-      AvailCopyMap.clear();
-      CopyMap.clear();
-      SrcMap.clear();
-      continue;
-    }
 
-    for (unsigned Reg : Defs) {
-      // No longer defined by a copy.
-      for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) {
-        CopyMap.erase(*AI);
-        AvailCopyMap.erase(*AI);
-      }
+      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);
+        }
+      }
 
-      // If 'Reg' is previously source of a copy, it is no longer available for
-      // copy propagation.
-      SourceNoLongerAvailable(Reg);
+    // Any previous copy definition or reading the Defs is no longer available.
+    for (unsigned Reg : Defs) {
+      ClobberRegister(Reg);
     }
   }
 
   // If MBB doesn't have successors, delete the copies whose defs are not used.
   // If MBB does have successors, then conservative assume the defs are live-out
   // since we don't want to trust live-in lists.
   if (MBB.succ_empty()) {
     for (MachineInstr *MaybeDead : MaybeDeadCopies) {

llvm/trunk/test/CodeGen/X86/machine-copy-prop.mir

-# RUN: llc -march=x86 -run-pass machine-cp -verify-machineinstrs -o /dev/null %s 2>&1 | FileCheck %s
+# RUN: llc -march=x86 -run-pass machine-cp -o /dev/null %s 2>&1 | FileCheck %s
 
 --- |
   declare void @foo()
   define void @copyprop_remove_kill0() { ret void }
   define void @copyprop_remove_kill1() { ret void }
   define void @copyprop_remove_kill2() { ret void }
+  define void @copyprop0() { ret void }
+  define void @nocopyprop0() { ret void }
+  define void @nocopyprop1() { ret void }
 ...
 ---
-# The second copy is redundand and will be removed, check that we also remove
+# The second copy is redundant and will be removed, check that we also remove
 # the kill flag of intermediate instructions.
 # CHECK-LABEL: name: copyprop_remove_kill0
 # CHECK: bb.0:
 # CHECK-NEXT: %rax = COPY %rdi
 # CHECK-NEXT: NOOP implicit %rdi
 # CHECK-NOT: COPY
 # CHECK-NEXT: NOOP implicit %rax, implicit %rdi
 name: copyprop_remove_kill0
 body: |
   bb.0:
     %rax = COPY %rdi
     NOOP implicit killed %rdi
     %rdi = COPY %rax
     NOOP implicit %rax, implicit %rdi
 ...
 ---
-# The second copy is redundand and will be removed, check that we also remove
+# The second copy is redundant and will be removed, check that we also remove
 # the kill flag of intermediate instructions.
 # CHECK-LABEL: name: copyprop_remove_kill1
 # CHECK: bb.0:
 # CHECK-NEXT: %rax = COPY %rdi
 # CHECK-NEXT: NOOP implicit %edi
 # CHECK-NOT: COPY
 # CHECK-NEXT: NOOP implicit %rax, implicit %rdi
 name: copyprop_remove_kill1
 body: |
   bb.0:
     %rax = COPY %rdi
     NOOP implicit killed %edi
     %rdi = COPY %rax
     NOOP implicit %rax, implicit %rdi
 ...
 ---
-# The second copy is redundand and will be removed, check that we also remove
+# The second copy is redundant and will be removed, check that we also remove
 # the kill flag of intermediate instructions.
 # CHECK-LABEL: name: copyprop_remove_kill2
 # CHECK: bb.0:
 # CHECK-NEXT: %ax = COPY %di
 # CHECK-NEXT: NOOP implicit %rdi
 # CHECK-NOT: COPY
 # CHECK-NEXT: NOOP implicit %rax, implicit %rdi
 name: copyprop_remove_kill2
 body: |
   bb.0:
     %ax = COPY %di
     NOOP implicit killed %rdi
     %di = COPY %ax
     NOOP implicit %rax, implicit %rdi
 ...
+---
+# The second copy is redundant; the call preserves the source and dest register.
+# CHECK-LABEL: name: copyprop0
+# CHECK: bb.0:
+# CHECK-NEXT: %rax = COPY %rdi
+# CHECK-NEXT: CALL64pcrel32 @foo, csr_64_rt_mostregs
+# CHECK-NEXT: NOOP implicit %edi
+# CHECK-NOT: COPY
+# CHECK-NEXT: NOOP implicit %rax, implicit %rdi
+name: copyprop0
+body: |
+  bb.0:
+    %rax = COPY %rdi
+    CALL64pcrel32 @foo, csr_64_rt_mostregs
+    NOOP implicit killed %edi
+    %rdi = COPY %rax
+    NOOP implicit %rax, implicit %rdi
+...
+---
+# The second copy is not redundant if the source register (%rax) is clobbered
+# even if the dest (%rbp) is not.
+# CHECK-LABEL: name: nocopyprop0
+# CHECK: bb.0:
+# CHECK-NEXT: %rax = COPY %rbp
+# CHECK-NEXT: CALL64pcrel32 @foo, csr_64, implicit %rax, implicit %rbp
+# CHECK-NEXT: %rbp = COPY %rax
+# CHECK-NEXT: NOOP implicit %rax, implicit %rbp
+name: nocopyprop0
+body: |
+  bb.0:
+    %rax = COPY %rbp
+    CALL64pcrel32 @foo, csr_64, implicit %rax, implicit %rbp
+    %rbp = COPY %rax
+    NOOP implicit %rax, implicit %rbp
+...
+---
+# The second copy is not redundant if the dest register (%rax) is clobbered
+# even if the source (%rbp) is not.
+# CHECK-LABEL: name: nocopyprop1
+# CHECK: bb.0:
+# CHECK-NEXT: %rbp = COPY %rax
+# CHECK-NEXT: CALL64pcrel32 @foo, csr_64, implicit %rax, implicit %rbp
+# CHECK-NEXT: %rax = COPY %rbp
+# CHECK-NEXT: NOOP implicit %rax, implicit %rbp
+name: nocopyprop1
+body: |
+  bb.0:
+    %rbp = COPY %rax
+    CALL64pcrel32 @foo, csr_64, implicit %rax, implicit %rbp
+    %rax = COPY %rbp
+    NOOP implicit %rax, implicit %rbp
+...