MachineCopyPropagation: Keep scanning through instructions with regmasks

[qcolombet]

lib/CodeGen/MachineCopyPropagation.cpp

99

Period.

105

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

Update this comment, the end is no more relevant.

307

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

301–306

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

9

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.

22

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

98

Any reason why the two loops are not merged?

147

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

-verify-machineinstrs?

13

typo -> redundant

[junbuml]

lib/CodeGen/MachineCopyPropagation.cpp

73

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.

334

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

73

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

98

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

147

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

334

indeed, fixed.

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

1

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 :).

lib/CodeGen/MachineCopyPropagation.cpp

namespace {
   };
 }
 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);
       }
     }
   }
 }
 
 static bool NoInterveningSideEffect(const MachineInstr *CopyMI,
-                                    const MachineInstr *MI) {
+                                    const MachineInstr *MI, unsigned Reg) {
   const MachineBasicBlock *MBB = CopyMI->getParent();
   if (MI->getParent() != MBB)
     return false;
 
   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())
+    if (I->isTerminator())
       return false;
+    if (I->hasUnmodeledSideEffects() || I->isCall()) {
+      // Continue if the instruction explicitely preserves the register
+      // (calls often do)
+      bool RegIsPreserved = false;
+      for (const MachineOperand &MO : MI->operands()) {
+        if (MO.isRegMask() &&
+            !MachineOperand::clobbersPhysReg(MO.getRegMask(), Reg)) {
+          RegIsPreserved = true;
+          break;
+        }
+      }
+      if (!RegIsPreserved)
+        return false;
+    }
   }
   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.

 
 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) &&
-            (!MRI->isReserved(Src) || NoInterveningSideEffect(CopyMI, MI)) &&
-            isNopCopy(CopyMI, Def, Src, TRI)) {
+        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
           //
for (const MachineOperand &MO : MI->operands()) {
       // 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.
     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 (Reg2MIMap::iterator I = AvailCopyMap.begin(), E = AvailCopyMap.end(),
+           Next; I != E; I = Next) {
+        Next = std::next(I);
+        unsigned Reg = I->first;
+        if (RegMask->clobbersPhysReg(Reg))
+          AvailCopyMap.erase(I);
+      }
+      for (Reg2MIMap::iterator I = CopyMap.begin(), E = CopyMap.end(), Next;
+           I != E; I = Next) {
+        Next = std::next(I);
+        unsigned Reg = I->first;
+        if (RegMask->clobbersPhysReg(Reg))
+          CopyMap.erase(I);
+      }
+      for (SourceMap::iterator I = SrcMap.begin(), E = SrcMap.end(), Next;
+           I != E; I = Next) {
+        Next = std::next(I);
+        unsigned Reg = I->first;
+        if (RegMask->clobbersPhysReg(Reg)) {
+          const DestList &Defs = I->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);
+          }
+        }
+      }
     }
 
     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);
       }
 
       // If 'Reg' is previously source of a copy, it is no longer available for
       // copy propagation.
       SourceNoLongerAvailable(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) {
       assert(!MRI->isReserved(MaybeDead->getOperand(0).getReg()));
       MaybeDead->eraseFromParent();

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 @copyprop1() { ret void }
+...
+---
+# 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
+...