[PowerPC] Remove redundant register copies in late peephole

[nemanjai]

Summary

In a number of cases, we will end up with redundant register copies quite late in the pipeline (i.e. after AADB, etc.).
A sequence such as this:

mr r30, r3
...        # no clobbering of r30 or r3
mr r3, r30 # this is redundant

Earlier passes sometimes leave sequences such as this behind because the sequence in between clobbers r3, but AADB will rewrite it.

[inouehrs]

lib/Target/PowerPC/PPCPreEmitPeephole.cpp

80

Do you eliminate only the second mr, not both mrs?
We have additional opportunity to erase first mr by rewriting uses of r3 with r30.

[nemanjai]

lib/Target/PowerPC/PPCPreEmitPeephole.cpp

80

This isn't safe to do in general. The motivating test case for example has a call. That call needs the value to be in r3, so I can't just tell it to use r30.

[hfinkel]

This is fine except that it's O(N^2). Can you please either rewrite this to do a scan first to collect candidate pairs and then check them (which I'd prefer) or add a threshold for the forward search (which would be okay too: given a sufficiently large BB, the chances of having these opportunities with a large separation seems low).

[stefanp]

lib/Target/PowerPC/PPCPreEmitPeephole.cpp

90

Once the second mr is deleted the first mr could become a trivially dead instruction. (It is certainly not guaranteed to be dead but it is possible that it is dead.) Is there a pass after this to clean that up? I think this is just pre-emit so I don't think there is anything else after this.

It may be worth doing a quick test to see if the first mr is dead once we have removed the second one.

130

Maybe a silly question but...
I don't understand why these flags are being cleared.
In this case MI is the first mr instruction. So from what I see:

mr r30, r3

The r30 is being overwritten but the r3 is only a use. Why would these flags even be set to true in the first place for r3?

test/CodeGen/PowerPC/remove-cyclic-mr.ll

21

I'm debating if this test is over-specified.
We are testing

mr 30, 3
... 
mr 3, 30

Do we need anything above the first mr and below the second mr?
I just don't want this test to fail every now and then when we change something in scheduling or register allocation (or any other pass that might make the code a little different.)

lib/Target/PowerPC/PPCPreEmitPeephole.cpp

 using namespace llvm;
 
 #define DEBUG_TYPE "ppc-pre-emit-peephole"
 
 STATISTIC(NumRRConvertedInPreEmit,
           "Number of r+r instructions converted to r+i in pre-emit peephole");
 STATISTIC(NumRemovedInPreEmit,
           "Number of instructions deleted in pre-emit peephole");
+STATISTIC(NumRedundantPairsFound,
+          "Number of redundant pair instructions found in pre-emit peephole");
 
 static cl::opt<bool>
 RunPreEmitPeephole("ppc-late-peephole", cl::Hidden, cl::init(false),
                    cl::desc("Run pre-emit peephole optimizations."));
 
 namespace {
   class PPCPreEmitPeephole : public MachineFunctionPass {
+    MachineInstr *hasRedundantPair(MachineInstr &MI) const;
   public:
     static char ID;
     PPCPreEmitPeephole() : MachineFunctionPass(ID) {
       initializePPCPreEmitPeepholePass(*PassRegistry::getPassRegistry());
     }
 
     void getAnalysisUsage(AnalysisUsage &AU) const override {
       MachineFunctionPass::getAnalysisUsage(AU);
     }
 
     MachineFunctionProperties getRequiredProperties() const override {
       return MachineFunctionProperties().set(
           MachineFunctionProperties::Property::NoVRegs);
     }
 
     bool runOnMachineFunction(MachineFunction &MF) override {
       if (skipFunction(*MF.getFunction()) || !RunPreEmitPeephole)
         return false;
       bool Changed = false;
       const PPCInstrInfo *TII = MF.getSubtarget<PPCSubtarget>().getInstrInfo();
       SmallVector<MachineInstr *, 4> InstrsToErase;
       for (MachineBasicBlock &MBB : MF) {
         for (MachineInstr &MI : MBB) {
           MachineInstr *DefMIToErase = nullptr;
+          MachineInstr *RedundantPairMI = nullptr;
           if (TII->convertToImmediateForm(MI, &DefMIToErase)) {
             Changed = true;
             NumRRConvertedInPreEmit++;
             DEBUG(dbgs() << "Converted instruction to imm form: ");
             DEBUG(MI.dump());
             if (DefMIToErase) {
               InstrsToErase.push_back(DefMIToErase);
             }
+          } else if ((RedundantPairMI = hasRedundantPair(MI))) {
+            InstrsToErase.push_back(RedundantPairMI);
+            NumRedundantPairsFound++;
           }
         }
       }
       for (MachineInstr *MI : InstrsToErase) {
         DEBUG(dbgs() << "PPC pre-emit peephole: erasing instruction: ");
         DEBUG(MI->dump());
+        assert(MI->getParent() &&
+               "The same instruction marked redundant multiple times?");
         MI->eraseFromParent();
         NumRemovedInPreEmit++;
       }
       return Changed;
     }
   };
+
+  // For now, only handle mr X, Y -> mr Y, X with no clobber of Y in between
+  // as that is the only pattern known to come up.
+  MachineInstr *PPCPreEmitPeephole::hasRedundantPair(MachineInstr &MI) const {
+    unsigned Opc = MI.getOpcode();
+
+    // If this isn't an mr, return null.
+    if ((Opc != PPC::OR && Opc != PPC::OR8) ||
+        MI.getOperand(1).getReg() != MI.getOperand(2).getReg())
+      return nullptr;
+
+    unsigned DestReg = MI.getOperand(0).getReg();
+    unsigned SrcReg = MI.getOperand(1).getReg();
+    const MachineRegisterInfo *MRI = &MI.getParent()->getParent()->getRegInfo();
+    const TargetRegisterInfo *TRI = MRI->getTargetRegisterInfo();
+
+    MachineBasicBlock::iterator StartIt = MI, EndIt = MI.getParent()->end();
+    StartIt++;
+    for (; StartIt != EndIt; ++StartIt) {
+      // If we encounter an instruction that clobbers the destination,
+      // any subsequent copy of the original destination won't be copying
+      // the same register, return null.
+      if (StartIt->modifiesRegister(DestReg, TRI))
+        return nullptr;
+
+      // If we find an instruction that clobbers the source register, it is
+      // redundant if it's a copy from the original destination and we haven't
+      // exited above.
+      if (StartIt->modifiesRegister(SrcReg, TRI)) {
+        if (StartIt->getOpcode() != Opc ||
+            StartIt->getOperand(1).getReg() != DestReg ||
+            StartIt->getOperand(2).getReg() != DestReg)
+          return nullptr;
+
+        // Clear the kill flags from the original instruction.
+        MI.getOperand(1).setIsKill(false);
+        MI.getOperand(2).setIsKill(false);
+        return &*StartIt;
+      }
+    }
+    return nullptr;
+  }
 }
 
 INITIALIZE_PASS(PPCPreEmitPeephole, DEBUG_TYPE, "PowerPC Pre-Emit Peephole",
                 false, false)
 char PPCPreEmitPeephole::ID = 0;
 
 FunctionPass *llvm::createPPCPreEmitPeepholePass() {
   return new PPCPreEmitPeephole();
 }

test/CodeGen/PowerPC/remove-cyclic-mr.ll

+; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
+; RUN: llc < %s -mtriple=powerpc64le-unknown-unknown -mcpu=pwr8 \
+; RUN:   -ppc-late-peephole -verify-machineinstrs | FileCheck %s
+%struct.x0 = type { i8 }
+
+@.str = private unnamed_addr constant [1 x i8] zeroinitializer, align 1
+
+define void @_Z2x6v() {
+; CHECK-LABEL: _Z2x6v:
+; CHECK:       # BB#0: # %entry
+; CHECK-NEXT:    mflr 0
+; CHECK-NEXT:    std 0, 16(1)
+; CHECK-NEXT:    stdu 1, -64(1)
+; CHECK-NEXT:    .cfi_def_cfa_offset 64
+; CHECK-NEXT:    .cfi_offset lr, 16
+; CHECK-NEXT:    .cfi_offset r30, -16
+; CHECK-NEXT:    addi 3, 1, 40
+; CHECK-NEXT:    std 30, 48(1) # 8-byte Folded Spill
+; CHECK-NEXT:    bl _ZN2x02x1Ev
+; CHECK-NEXT:    nop
+; CHECK-NEXT:    mr 30, 3
+; CHECK-NEXT:    addis 12, 2, .L.str@toc@ha
+; CHECK-NEXT:    addi 4, 12, .L.str@toc@l
+; Note: previously there was an mr 3, 30 here.
+; CHECK-NEXT:    bl _ZN2x02x4EPKc
+; CHECK-NEXT:    nop
+; CHECK-NEXT:    li 4, 0
+; CHECK-NEXT:    mr 3, 30
+; CHECK-NEXT:    bl _ZN2x0lsIiEEvT_
+; CHECK-NEXT:    nop
+; CHECK-NEXT:    ld 30, 48(1) # 8-byte Folded Reload
+; CHECK-NEXT:    addi 1, 1, 64
+; CHECK-NEXT:    ld 0, 16(1)
+; CHECK-NEXT:    mtlr 0
+; CHECK-NEXT:    blr
+entry:
+  %ref.tmp = alloca %struct.x0, align 1
+  %0 = getelementptr inbounds %struct.x0, %struct.x0* %ref.tmp, i64 0, i32 0
+  call void @llvm.lifetime.start.p0i8(i64 1, i8* nonnull %0)
+  %call = call dereferenceable(1) %struct.x0* @_ZN2x02x1Ev(%struct.x0* nonnull %ref.tmp)
+  call void @_ZN2x02x4EPKc(%struct.x0* nonnull %call, i8* nonnull getelementptr inbounds ([1 x i8], [1 x i8]* @.str, i64 0, i64 0))
+  call void @_ZN2x0lsIiEEvT_(%struct.x0* nonnull %call, i32 signext 0)
+  call void @llvm.lifetime.end.p0i8(i64 1, i8* nonnull %0)
+  ret void
+}
+
+; Function Attrs: argmemonly nounwind
+declare void @llvm.lifetime.start.p0i8(i64, i8* nocapture)
+
+declare dereferenceable(1) %struct.x0* @_ZN2x02x1Ev(%struct.x0*)
+
+declare void @_ZN2x0lsIiEEvT_(%struct.x0*, i32 signext)
+
+; Function Attrs: argmemonly nounwind
+declare void @llvm.lifetime.end.p0i8(i64, i8* nocapture)
+
+declare void @_ZN2x02x4EPKc(%struct.x0*, i8*)