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

[qcolombet]

lib/CodeGen/MachineCopyPropagation.cpp

55

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.

209

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

155

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.

194

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

146

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

146

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

155

Good catch! Should be fixed now.

209

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

[junbuml]

lib/CodeGen/MachineCopyPropagation.cpp

225

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

[MatzeB]

lib/CodeGen/MachineCopyPropagation.cpp

225

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

150

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

22–23

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

70

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

lib/CodeGen/MachineCopyPropagation.cpp

namespace {
 
   private:
     typedef SmallVector<unsigned, 4> DestList;
     typedef DenseMap<unsigned, DestList> SourceMap;
     typedef DenseMap<unsigned, MachineInstr*> Reg2MIMap;
 
     void SourceNoLongerAvailable(unsigned Reg);
     void CopyPropagateBlock(MachineBasicBlock &MBB);
+    bool eraseRedundantCopy(MachineInstr *MI, 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
if (TRI->isSubRegister(SrcSrc, Def)) {
     if (!SubIdx)
       return false;
     return SubIdx == TRI->getSubRegIndex(SrcDef, Src);
   }
 
   return false;
 }
 
+bool MachineCopyPropagation::eraseRedundantCopy(MachineInstr *MI,
+                                                unsigned Src, unsigned Def) {
+  Reg2MIMap::iterator CI = AvailCopyMap.find(Src);
+  if (CI != AvailCopyMap.end()) {
+    MachineInstr *CopyMI = CI->second;
+    if (!MRI->isReserved(Def) && isNopCopy(CopyMI, Def, Src, TRI) &&
+        (!MRI->isReserved(Src) ||
+         NoInterveningSideEffect(CopyMI, MI, Src))) {
+      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;
+      return true;
+    }
+  }
+  return false;
+}
+
 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) &&
-            (!MRI->isReserved(Src) ||
-             NoInterveningSideEffect(CopyMI, MI, Src))) {
-          // 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;
-        }
-      }
+      if (eraseRedundantCopy(MI, Src, Def))
+        continue;
+      // 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
+      if (eraseRedundantCopy(MI, Def, Src))
 
       // 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
       // ...

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

 # RUN: llc -march=x86 -run-pass machine-cp -o /dev/null %s 2>&1 | FileCheck %s
 
 --- |
   declare preserve_mostcc void @foo()
+  define void @copyprop0() { ret void }
   define void @copyprop1() { ret void }
+  define void @copyprop2() { ret void }
+...
+---
+# CHECK-LABEL: name: copyprop0
+# CHECK: bb.0:
+# CHECK-NEXT: %rax = COPY %rdi
+# CHECK-NOT: %rax = COPY %rdi
+# CHECK-NEXT: NOOP implicit %rax, implicit %rdi
+name: copyprop0
+body: |
+  bb.0:
+    %rax = COPY %rdi
+    %rax = COPY %rdi
+    NOOP implicit %rax, implicit %rdi
 ...
 ---
 # CHECK-LABEL: name: copyprop1
 # CHECK: bb.0:
 # CHECK-NEXT: %rax = COPY %rdi
 # CHECK-NEXT: CALL64pcrel32 @foo, csr_64_rt_mostregs, implicit %rsp, implicit-def %rsp
 # CHECK-NOT: %rdi = COPY %rax
 # CHECK-NEXT: NOOP implicit %rax, implicit %rdi
 name: copyprop1
 body: |
   bb.0:
     %rax = COPY %rdi
     CALL64pcrel32 @foo, csr_64_rt_mostregs, implicit %rsp, implicit-def %rsp
     %rdi = COPY %rax
     NOOP implicit %rax, implicit %rdi
 ...
+---
+# CHECK-LABEL: name: copyprop2
+# CHECK: bb.0:
+# CHECK-NEXT: %rax = COPY %rdi
+# CHECK-NEXT: CALL64pcrel32 @foo, csr_64_rt_mostregs, implicit %rsp, implicit-def %rsp
+# CHECK-NOT: %rax = COPY %rdi
+# CHECK-NEXT: NOOP implicit %rax, implicit %rdi
+name: copyprop2
+body: |
+  bb.0:
+    %rax = COPY %rdi
+    CALL64pcrel32 @foo, csr_64_rt_mostregs, implicit %rsp, implicit-def %rsp
+    %rax = COPY %rdi
+    NOOP implicit %rax, implicit %rdi
+...