[MachineCopyPropagation] Expose more dead copies across instructions with regmasks

[junbuml]

Summary

When encountering instructions with regmasks, instead of cleaning up all the
elements in MaybeDeadCopies map, remove only the instructions erased. By keeping
more instruction in MaybeDeadCopies, this change will expose more dead copies
across instructions with regmasks.

[qcolombet]

Hi Jun,

Although I can see how this helps, I wonder if the additional complexity is worth.
Indeed, what cases do we catch here that are not handled by DCE?

Cheers,
-Quentin

[junbuml]

Let me try to grep where this change is applied in spec tests.

[junbuml]

In my quick test for spec2006 in cortex-a57, I can see that this change is applied in :
xalancbmk, dealII, omnetpp, soplex, namd.

With -O3, I can see that 177 and 330 movs are removed in xalancbmk and dealII, respectively.
Most of them looks like :

mov x20, x0 
bl                           
mov x20, x0

into

bl 
mov x20, x0

[qcolombet]

That may just mean we need to run an additional DCE pass somewhere else.

Where does the dead move come from?

[MatzeB]

While I also would not expect to hit this often (I am surprised you found an instance in the SPEC at all), I think this change is small enough and very much in the spirit of the existing MachineCopyProp code, so why not go with it? The current patch however is invalid:

lib/CodeGen/MachineCopyPropagation.cpp

288–306

It seems to me like SmallSetVector::remove() invalidates all iterators into the structure (as it removes elements from an underlying vector and the iterators are just iterators into that vector). May be a good idea to add a SmallSetVector erase(iterator) method that gives returns you a valid iterator similar to SmallVector::erase() or we need a way to deal with it here.

[qcolombet]

I think this change is small enough and very much in the spirit of the existing MachineCopyProp code, so why not go with it?

I am fine with the code going in, but I want to root cause why we need it in the first place.
Indeed, I would rather not introduce code that lives just because of the mir test.

[junbuml]

From my test with spec, the dead copies are just exposed in this pass. In the code below, the second copy is removed as a NOP copy after then the first copy remain just as a dead copy because we currently clear MaybeDeadCopies when encountering an instruction with regmask.

%X19<def> = COPY %X0
%X0<def> = COPY %X19<kill>
BL <ga:@_Unwind_Resume>, %X0<imp-use>

I think removing only the instruction erased is just the right way to follow the original intention of MaybeDeadCopies.

lib/CodeGen/MachineCopyPropagation.cpp

288–306

For me, it seems fine to use remove(), which erase in underlying set_ first and then in vector_, since we actually iterate using vector_ and increase our iterator (DI) right after assigning the current iterator to MaybeDead.

[MatzeB]

lib/CodeGen/MachineCopyPropagation.cpp

288–306

increasing the iterator first and then removing works fine for llvm::DenseMap, llvm::SmallPtrSet, etc. but not for vectors!
I rechecked this: std::vector::erase() invalidates all iterators that point to the removed element or behind it including the end() iterator. llvm::SmallVector should behave the same in that respect.

(Just think about a typical vector implementation, iterators are just pointers into the array when you remove elements everything behind will be moved forward, a loop like above will make you miss the element after the one you removed in case of the end you will even wander off into memory behind the vector)

[junbuml]

lib/CodeGen/MachineCopyPropagation.cpp

288–306

Thanks for correcting me.

The easiest way to fix in here would be to store the instructions we want to remove in a separate small vector and then erase all of them separately. If it doesn't make sense, I may see if I can add erase() method in SmallSetVector.

[qcolombet]

Thanks Jun for checking where the copy came from.
That being said, isn't this case already handled?
And if it is not, could you add a test case for it. None of the test cases you are adding reproduce that example.

Thanks,
-Quentin

[junbuml]

Added test case as Quentin commented.

[junbuml]

lib/CodeGen/MachineCopyPropagation.cpp

288–306

Modified the way I iterate the loop; do not increase the iterator when removing an element.

[qcolombet]

Hi Jun,

Thanks for the additional test case.

The iteration in the loop still looks problematic to me. See my inlined comment.

Thanks,
-Quentin

lib/CodeGen/MachineCopyPropagation.cpp

288–306

This is not clear to me how the iterator makes progress when we remove an element now.
Could you explain what I am missing, please?

[junbuml]

lib/CodeGen/MachineCopyPropagation.cpp

288–306

Erasing an element will causes the vector to relocate all the elements after the erased one to their new positions; like one element shift left. So the current iterator will point the right next element after erasing.

[qcolombet]

lib/CodeGen/MachineCopyPropagation.cpp

288–306

Is this something the API guarantee?
I was under the impression that although you are right about this behavior, we are actually abusing it by taking advantage of undocumented feature.

Put differently we shouldn’t rely on that behavior unless the API guarantees it. I think this is what Matthias wanted you to go with the additional erase method, i.e., a method what does what you want and is properly documented.

[junbuml]

lib/CodeGen/MachineCopyPropagation.cpp

288–306

Okay, I see your point. To be clear let me add a new erase method in SmallSetVector which will return the next element we need to iterate after erasing.

Thanks Quentin for revisiting this.

[junbuml]

Used the new erase() method added in D18281.

[MatzeB]

LGTM

lib/CodeGen/MachineCopyPropagation.cpp

289–290

can these two lines get merged to a single one? (Ignore this if they are actually need more than 80 columns when combined).

[junbuml]

Thanks Matthias for the review.
This will be committed after committing D18281.

lib/CodeGen/MachineCopyPropagation.cpp

289–290

Combining these two lines do not require more than 80 columns, but this is what clang-format suggested.

[MatzeB]

lib/CodeGen/MachineCopyPropagation.cpp

289–290

Odd. But feel free to leave it as is then.

[junbuml]

Committed in r264462.
Thanks Matthias for the review.

lib/CodeGen/MachineCopyPropagation.cpp

for (const MachineOperand &MO : MI->operands()) {
         Defs.push_back(Reg);
     }
 
     // The instruction has a register mask operand which means that it clobbers
     // 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) {
+      for (SmallSetVector<MachineInstr *, 8>::iterator DI =
+               MaybeDeadCopies.begin();
+           DI != MaybeDeadCopies.end();) {
+        MachineInstr *MaybeDead = *DI;
         unsigned Reg = MaybeDead->getOperand(0).getReg();
         assert(!MRI->isReserved(Reg));
-        if (!RegMask->clobbersPhysReg(Reg))
+
+        if (!RegMask->clobbersPhysReg(Reg)) {
+          ++DI;
           continue;
+        }
+
         DEBUG(dbgs() << "MCP: Removing copy due to regmask clobbering: ";
               MaybeDead->dump());
+
+        // erase() will returns the next valid iterator pointing to the next
+        // element after the erased one.
+        DI = MaybeDeadCopies.erase(DI);
         MaybeDead->eraseFromParent();
         Changed = true;
         ++NumDeletes;
       }
-      MaybeDeadCopies.clear();
 
       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);
bool MachineCopyPropagation::runOnMachineFunction(MachineFunction &MF) {
   TII = MF.getSubtarget().getInstrInfo();
   MRI = &MF.getRegInfo();
 
   for (MachineBasicBlock &MBB : MF)
     CopyPropagateBlock(MBB);
 
   return Changed;
 }
+

test/CodeGen/MIR/AArch64/machine-dead-copy.mir

+
+# RUN: llc -mtriple=aarch64-none-linux-gnu -run-pass machine-cp  -verify-machineinstrs  -o /dev/null %s 2>&1 | FileCheck %s
+
+--- |
+  define i32 @copyprop1(i32 %a, i32 %b) { ret i32 %a }
+  define i32 @copyprop2(i32 %a, i32 %b) { ret i32 %a }
+  define i32 @copyprop3(i32 %a, i32 %b) { ret i32 %a }
+  define i32 @copyprop4(i32 %a, i32 %b) { ret i32 %a }
+  declare i32 @foo(i32)
+...
+---
+# The first copy is dead copy which is not used.
+# CHECK-LABEL: name: copyprop1
+# CHECK: bb.0:
+# CHECK-NOT: %w20 = COPY
+name:            copyprop1
+body:             |
+  bb.0:
+    liveins: %w0,  %w1
+    %w20 = COPY %w1
+    BL @foo, csr_aarch64_aapcs, implicit %w0, implicit-def %w0
+    RET_ReallyLR implicit %w0
+...
+---
+# The first copy is not a dead copy which is used in the second copy after the
+# call.
+# CHECK-LABEL: name: copyprop2
+# CHECK: bb.0:
+# CHECK: %w20 = COPY
+name:            copyprop2
+body:             |
+  bb.0:
+    liveins: %w0,  %w1
+    %w20 = COPY %w1
+    BL @foo, csr_aarch64_aapcs, implicit %w0, implicit-def %w0
+    %w0 = COPY %w20
+    RET_ReallyLR implicit %w0
+...
+---
+# Both the first and second copy are dead copies which are not used.
+# CHECK-LABEL: name: copyprop3
+# CHECK: bb.0:
+# CHECK-NOT: COPY
+name:            copyprop3
+body:             |
+  bb.0:
+    liveins: %w0,  %w1
+    %w20 = COPY %w1
+    BL @foo, csr_aarch64_aapcs, implicit %w0, implicit-def %w0
+    %w20 = COPY %w0
+    RET_ReallyLR implicit %w0
+...
+# The second copy is removed as a NOP copy, after then the first copy become
+# dead which should be removed as well.
+# CHECK-LABEL: name: copyprop4
+# CHECK: bb.0:
+# CHECK-NOT: COPY
+name:            copyprop4
+body:             |
+  bb.0:
+    liveins: %w0,  %w1
+    %w20 = COPY %w0
+    %w0 = COPY %w20
+    BL @foo, csr_aarch64_aapcs, implicit %w0, implicit-def %w0
+    RET_ReallyLR implicit %w0
+...
+