MachineCopyPropagation: Catch copies of the form A<-B;A<-B

[qcolombet]

lib/CodeGen/MachineCopyPropagation.cpp

56

Please document this function.
Although based on the uses, I found Src and Def being confusing because they do not actually represent the source and destination of MI.

208

Unless I am missing something, the previous comment is a plain copy of the previous one, whereas what you want is:

//  %ECX<def> = COPY %EAX
//  ... nothing clobbered EAX.
//  %ECX<def> = COPY %EAX

I.e., same def and src for both copies.

That being said, it seems strange to me that we have to support the full reg case that you exposed in the example. Indeed, this does not look like a copy propagation, but, like you said, a redundant copy. In other words, I would have expected we catch this in MachineCSE and if this is not the case, I believe it makes more sense to understand why and do it thereI.
Anyhow, MachineCSE would still be useful in cases where sub register are involved. I.e., I am fine with the code living here, but we would need a test case with sub register.
E.g.,
eax = ecx
al = cl

[arsenm]

Does this obsolete r248611?

[qcolombet]

Hi Matt,

No, this is complementary to r248611 because one works before regalloc and the other after.

Cheers,
-Quentin

[junbuml]

lib/CodeGen/MachineCopyPropagation.cpp

168

Cleaning kill for Def is not always correct. In the second call for eraseRedundantCopy() below, MI's Src is passed as the second parameter, which is Def here, but we need to clean kill for MI's Def instead of MI's Src.

193

Looks like the first eraseRedundantCopy() is for :

%A = COPY %B

:

%B = COPY %A,
while the second eraseRedundantCopy() is for :

%A = COPY %B

:

%A = COPY %B.
So, it will good to have comment for each.

[junbuml]

lib/CodeGen/MachineCopyPropagation.cpp

159

In MRI->isReserved(Def), we should use the actual register defined in MI, instead of the Def passed as a parameter. In case of the second call for eraseRedundantCopy() below in line 209, MI's Src is passed as Def here.

[MatzeB]

New versions addressing comments, cleaning up the code, improving comments and extending the tests.

[MatzeB]

Update revision which turns an assert in isNopCopy back to an if() and adjusts two AMDGPU testcases to the improved copy elimination.

[MatzeB]

lib/CodeGen/MachineCopyPropagation.cpp

159

I think we cannot eliminate any copy to/from a reserved reg, that's what I put in place now.

168

Good catch! Should be fixed now.

208

I reorganized the whole comment hope it is easier to understand now.

[junbuml]

lib/CodeGen/MachineCopyPropagation.cpp

211

Shouldn't we need to add !MRI->isReserved(Src) as well ?

[MatzeB]

lib/CodeGen/MachineCopyPropagation.cpp

211

This is fine. Elminating a redundant copy of a reserved register is bad because you either write to a reserved register which may have effects you don't know about so you just cannot erase the write, or the redundant copy reads from a reserved register in which case we cannot be sure that is still has the previous value.

In the case of a dead copy reading form a reserved register we do not care though: We don't know the value that is read but nobody reads the value produced by the dead copy anyway.

[junbuml]

lib/CodeGen/MachineCopyPropagation.cpp

125

Would it make sense to give an exception when Src is zero register? In AArch64, I can see redundant zero copies after RA like :

%X8<def> = COPY %XZR
STRXui %X8<kill>, <fi#36>, 0
%X8<def> = COPY %XZR
STRXui %X8<kill>, <fi#34>, 0

[qcolombet]

Hi Jun,

I’d rather not start messing with reserved registers in a generic way.

If you want to catch your example, maybe this is something you can teach in the AArch64RedundantCopyElimination pass.

Cheers,
-Quentin

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

17

Didn’t you fixed those typos in a previous commit?!
Forgot to rebase maybe?

[junbuml]

I’d rather not start messing with reserved registers in a generic way.
If you want to catch your example, maybe this is something you can teach in the AArch64RedundantCopyElimination pass.

Make sense to me.

[MatzeB]

In D17475#361922, @qcolombet wrote:

Hi Jun,

I’d rather not start messing with reserved registers in a generic way.

If you want to catch your example, maybe this is something you can teach in the AArch64RedundantCopyElimination pass.

Cheers,
-Quentin

Uh, I think this has probably worked before and fails after my changes, I don't want to cause regressions here...

[junbuml]

Uh, I think this has probably worked before and fails after my changes, I don't want to cause regressions here...

I don't think the case I mentioned above was handled even before your patch.

[MatzeB]

In D17475#362009, @junbuml wrote:

Uh, I think this has probably worked before and fails after my changes, I don't want to cause regressions here...

I don't think the case I mentioned above was handled even before your patch.

You are right, this wasn't possible before of course, because it was an A<-B; A<-B pattern.

I just discussed this a bit with Quentin and we think that eliminating the second copy in an "A<-B; A<-B" is invalid if B is a reserved register, because we cannot be sure that we are actually reading the same value. For an example look at ARM32s PC register. I'll probably take a few minutes to create a patch that adds some comments to TargetRegisterInfo that define what reserved registers mean.

[gberry]

Couldn't you add a check for isConstantPhysReg() to handle the case Jun mentioned?

[llvm-commits]

That’ll work, though it should be a follow-up patch IMO.

Q.

[junbuml]

Adding isConstantPhysReg() would be good in this pass. As far as I check, however, isConstantPhysReg() returns false for WZR and XZR in AArch64, which I think we need to fix (Bug 25457).

[MatzeB]

In D17475#362089, @junbuml wrote:

Adding isConstantPhysReg() would be good in this pass. As far as I check, however, isConstantPhysReg() returns false for WZR and XZR in AArch64, which I think we need to fix (Bug 25457).

Yes let's do this one in follow up commits. Is it okay to push this one?

[junbuml]

This looks good to me, assuming other reviewers are OK with adding isConstantPhysReg() in a follow-up patch.

[MatzeB]

In D17475#362150, @junbuml wrote:

This looks good to me, assuming other reviewers are OK with adding isConstantPhysReg() in a follow-up patch.

I'm not convinced that isConstantPhysReg() is the answer. This function currently simply checks whether there is more than one definition for a register. This still does not allow us to assume the same value for arbitrary reserved registers IMO (think of the PC register on ARM) it would also fail if we have more than 1 write of the zero registers (not sure about ARM but on sparc it is common to write to the zero register). See also the llvm-dev I just posted about unallocatable/reserved registers.

[qcolombet]

LGTM plus maybe a test for reserved registers (i.e., don’t do anything for those).

Q.

test/CodeGen/AMDGPU/llvm.amdgcn.rsq.clamp.ll

34 ↗

(On Diff #48874)

I guess this is the rebase messing around.

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

184

Could you add a test with Reserved register for both cases source and destination?

lib/CodeGen/MachineCopyPropagation.cpp

public:
     typedef SmallVector<unsigned, 4> RegList;
     typedef DenseMap<unsigned, RegList> SourceMap;
     typedef DenseMap<unsigned, MachineInstr*> Reg2MIMap;
 
   private:
     void ClobberCopySources(const RegList &Defs);
     void ClobberRegister(unsigned Reg);
     void CopyPropagateBlock(MachineBasicBlock &MBB);
+    bool eraseIfRedundant(MachineInstr &Copy, unsigned Src, unsigned Def);
 
     /// Candidates for deletion.
     SmallSetVector<MachineInstr*, 8> MaybeDeadCopies;
     /// Def -> available copies map.
     Reg2MIMap AvailCopyMap;
     /// Def -> copies map.
     Reg2MIMap CopyMap;
     /// Src -> Def map
void MachineCopyPropagation::ClobberRegister(unsigned Reg) {
   }
 
   for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) {
     CopyMap.erase(*AI);
     AvailCopyMap.erase(*AI);
   }
 }
 
-/// 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
-/// But not
-/// ecx = mov eax
-/// al  = mov ch
-static bool isNopCopy(const MachineInstr *CopyMI, unsigned Def, unsigned Src,
-                      const TargetRegisterInfo *TRI) {
-  unsigned SrcSrc = CopyMI->getOperand(1).getReg();
-  if (Def == SrcSrc)
+/// Return true if \p PreviousCopy did copy register \p Src to register \p Def.
+/// This fact may have been obscured by sub register usage or may not be true at
+/// all even though Src and Def are subregisters of the registers used in
+/// PreviousCopy. e.g.
+/// isNopCopy("ecx = COPY eax", AX, CX) == true
+/// isNopCopy("ecx = COPY eax", AH, CL) == false
+static bool isNopCopy(const MachineInstr &PreviousCopy, unsigned Src,
+                      unsigned Def, const TargetRegisterInfo *TRI) {
+  unsigned PreviousSrc = PreviousCopy.getOperand(1).getReg();
+  unsigned PreviousDef = PreviousCopy.getOperand(0).getReg();
+  if (Src == PreviousSrc) {
+    assert(Def == PreviousDef);
     return true;
-  if (TRI->isSubRegister(SrcSrc, Def)) {
-    unsigned SrcDef = CopyMI->getOperand(0).getReg();
-    unsigned SubIdx = TRI->getSubRegIndex(SrcSrc, Def);
-    if (!SubIdx)
-      return false;
-    return SubIdx == TRI->getSubRegIndex(SrcDef, Src);
   }
+  assert(TRI->isSubRegister(PreviousSrc, Src));
+  unsigned SubIdx = TRI->getSubRegIndex(PreviousSrc, Src);
+  return SubIdx == TRI->getSubRegIndex(PreviousDef, Def);
+}
+
+/// Remove instruction \p Copy if there exists a previous copy that copies the
+/// register \p Src to the register \p Def; This may happen indirectly by
+/// copying the super registers.
+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.
+  Reg2MIMap::iterator CI = AvailCopyMap.find(Def);
+  if (CI == AvailCopyMap.end())
+    return false;
 
+  // Check that the existing copy uses the correct sub registers.
+  MachineInstr &PrevCopy = *CI->second;
+  if (!isNopCopy(PrevCopy, Src, Def, TRI))
     return false;
+
+  DEBUG(dbgs() << "MCP: copy is a NOP, removing: "; Copy.dump());
+
+  // Copy was redundantly redefining either Src or Def. Remove earlier kill
+  // flags between Copy and PrevCopy because the value will be reused now.
+  assert(Copy.isCopy());
+  unsigned CopyDef = Copy.getOperand(0).getReg();
+  assert(CopyDef == Src || CopyDef == Def);
+  for (MachineInstr &MI :
+       make_range(PrevCopy.getIterator(), Copy.getIterator()))
+    MI.clearRegisterKills(CopyDef, TRI);
+
+  Copy.eraseFromParent();
+  Changed = true;
+  ++NumDeletes;
+  return true;
 }
 
 static void removeClobberedRegsFromMap(MachineCopyPropagation::Reg2MIMap &Map,
                                        const MachineOperand &RegMask) {
   for (MachineCopyPropagation::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::CopyPropagateBlock(MachineBasicBlock &MBB) {
   DEBUG(dbgs() << "MCP: CopyPropagateBlock " << MBB.getName() << "\n");
 
   for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); I != E; ) {
     MachineInstr *MI = &*I;
     ++I;
 
     if (MI->isCopy()) {
       unsigned Def = MI->getOperand(0).getReg();
       unsigned Src = MI->getOperand(1).getReg();
 
       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) && 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
-          //
-          // Also avoid eliminating a copy from reserved registers unless the
-          // definition is proven not clobbered. e.g.
-          // %RSP<def> = COPY %RAX
-          // CALL
-          // %RAX<def> = COPY %RSP
-
-          DEBUG(dbgs() << "MCP: copy is a NOP, removing: "; MI->dump());
-
-          // Clear any kills of Def between CopyMI and MI. This extends the
-          // live range.
-          for (MachineInstr &MMI
-               : make_range(CopyMI->getIterator(), MI->getIterator()))
-            MMI.clearRegisterKills(Def, TRI);
-
-          MI->eraseFromParent();
-          Changed = true;
-          ++NumDeletes;
-          continue;
-        }
-      }
+      //  %ECX<def> = COPY %EAX
+      // or
+      //
+      //  %ECX<def> = COPY %EAX
+      //  ... nothing clobbered EAX.
+      //  %ECX<def> = COPY %EAX
+      // =>
+      //  %ECX<def> = COPY %EAX
+      if (eraseIfRedundant(*MI, Def, Src) || eraseIfRedundant(*MI, Src, Def))
 
       // If Src is defined by a previous copy, the previous copy cannot be
       // eliminated.
       for (MCRegAliasIterator AI(Src, TRI, true); AI.isValid(); ++AI) {
         Reg2MIMap::iterator CI = CopyMap.find(*AI);
         if (CI != CopyMap.end()) {
           DEBUG(dbgs() << "MCP: Copy is no longer dead: "; CI->second->dump());
           MaybeDeadCopies.remove(CI->second);
         }
       }
 
       DEBUG(dbgs() << "MCP: Copy is a deletion candidate: "; MI->dump());
 
       // Copy is now a candidate for deletion.
       if (!MRI->isReserved(Def))
         MaybeDeadCopies.insert(MI);
 
       // 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
       ClobberRegister(Def);
 
       // 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.
-      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;

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

-# RUN: llc -march=x86 -run-pass machine-cp -o /dev/null %s 2>&1 | FileCheck %s
+# RUN: llc -march=x86 -run-pass machine-cp -verify-machineinstrs -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 @copyprop1() { ret void }
+  define void @copyprop2() { ret void }
   define void @nocopyprop0() { ret void }
   define void @nocopyprop1() { ret void }
+  define void @nocopyprop2() { ret void }
+  define void @nocopyprop3() { ret void }
 ...
 ---
 # The second copy is redundand 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
     CALL64pcrel32 @foo, csr_64_rt_mostregs
     NOOP implicit killed %edi
     %rdi = COPY %rax
     NOOP implicit %rax, implicit %rdi
 ...
 ---
+# The 2nd copy is redundant; The call preserves the source and dest register.
+# CHECK-LABEL: name: copyprop1
+# CHECK: bb.0:
+# CHECK-NEXT: %rax = COPY %rdi
+# CHECK-NEXT: NOOP implicit %rax
+# CHECK-NEXT: NOOP implicit %rax, implicit %rdi
+name: copyprop1
+body: |
+  bb.0:
+    %rax = COPY %rdi
+    NOOP implicit killed %rax
+    %rax = COPY %rdi
+    NOOP implicit %rax, implicit %rdi
+...
+---
+# CHECK-LABEL: name: copyprop2
+# CHECK: bb.0:
+# CHECK-NEXT: %rax = COPY %rdi
+# CHECK-NEXT: NOOP implicit %ax
+# CHECK-NEXT: CALL64pcrel32 @foo, csr_64_rt_mostregs
+# CHECK-NOT: %rax = COPY %rdi
+# CHECK-NEXT: NOOP implicit %rax, implicit %rdi
+name: copyprop2
+body: |
+  bb.0:
+    %rax = COPY %rdi
+    NOOP implicit killed %ax
+    CALL64pcrel32 @foo, csr_64_rt_mostregs
+    %rax = COPY %rdi
+    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: nocopyprop1
 body: |
   bb.0:
     %rbp = COPY %rax
     CALL64pcrel32 @foo, csr_64, implicit %rax, implicit %rbp
     %rax = COPY %rbp
     NOOP implicit %rax, implicit %rbp
 ...
+---
+# The second copy is not redundant if the source register (%rax) is clobbered
+# even if the dest (%rbp) is not.
+# CHECK-LABEL: name: nocopyprop2
+# CHECK: bb.0:
+# CHECK-NEXT: %rax = COPY %rbp
+# CHECK-NEXT: CALL64pcrel32 @foo, csr_64, implicit %rax, implicit %rbp
+# CHECK-NEXT: %rax = COPY %rbp
+# CHECK-NEXT: NOOP implicit %rax, implicit %rbp
+name: nocopyprop2
+body: |
+  bb.0:
+    %rax = COPY %rbp
+    CALL64pcrel32 @foo, csr_64, implicit %rax, implicit %rbp
+    %rax = COPY %rbp
+    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: nocopyprop3
+# CHECK: bb.0:
+# CHECK-NEXT: %rbp = COPY %rax
+# CHECK-NEXT: CALL64pcrel32 @foo, csr_64, implicit %rax, implicit %rbp
+# CHECK-NEXT: %rbp = COPY %rax
+# CHECK-NEXT: NOOP implicit %rax, implicit %rbp
+name: nocopyprop3
+body: |
+  bb.0:
+    %rbp = COPY %rax
+    CALL64pcrel32 @foo, csr_64, implicit %rax, implicit %rbp
+    %rbp = COPY %rax
+    NOOP implicit %rax, implicit %rbp
+...