[PowerPC] Eliminate redundant register copys after register allocation

[inouehrs]

Summary

This patch add a PPC-specific path after register allocation to eliminate redundancy related register copies among physical registers.

So far, we eliminate the following two types of redundant register copys.

1. intra-BB redundant register copy

li Y, 0          li X, 0  (any instruction, not limited to li)
mr X, Y    =>    (erase mr)
..               ..

2. inter-BB partially redundant register copy

          BB1--------                             BB1--------
          | ..      |                             | ..      |
          | mr Y, X |                             | (erase) |
          | ..      |                             | ..      |
  with    -----------                    with     -----------
  1 pred /     |                         1 pred  /     |
BB--------     |      BB--------      BB---------      |      BB---------
| ..     |     |      | ..     |  =>  | mr Y, X |      |      | ..      |
| ..     |     |      | ..     |      | ..      |      |      | mr X, Y |
----------     |      ----------      -----------      |      -----------
               |     /  with                           |     /  with
          BB2--------   1 succ                    BB2--------   1 succ
          | ..      |                             | ..      |
          | mr X, Y |                             | (erase) |
          | ..      |                             | ..      |
          -----------                             -----------

[nemanjai]

I think that the main loop definitely needs to be re-written and made more readable and easier to follow. To me, it seems like it does too much. It spans nearly 250 lines and does a whole bunch of analyses and transformations.
Could you extract functionality into easy-to-read functions that perform individual things so that the flow is easier to follow?

Also, would it be appropriate to make this target-independent and do it perhaps in MachineCopyPropagation? Perhaps Geoff can comment on that since he's done something similar that he is still working on improvements for in order to finally commit it.

lib/Target/PowerPC/PPCPostRAPeephole.cpp

61 ↗

(On Diff #121249)

If we're adding a new peephole, it likely won't only be used for this one purpose. A more general name might be in order.

100 ↗

(On Diff #121249)

This seems a bit fragile. I'm not sure there's any hard guarantee that the flag will be on the last source operand.

142 ↗

(On Diff #121249)

These loops as well as a check for whether the instruction is a call seem a little odd. Why is it inadequate to use MachineInstr::readsRegister() and MachineInstr::modifiesRegister() for these purposes. Given the TRI, they should return the correct value for any instruction (including calls).

[inouehrs]

• changed a new pass name
• code simplified

[inouehrs]

If we're adding a new peephole, it likely won't only be used for this one purpose. A more general name might be in order.

I changed the pass name. Do you have any suggestion on an alternative name?

This seems a bit fragile. I'm not sure there's any hard guarantee that the flag will be on the last source operand.

I modified to check the flag for both input operands.

These loops as well as a check for whether the instruction is a call seem a little odd. Why is it inadequate to use MachineInstr::readsRegister() and MachineInstr::modifiesRegister() for these purposes. Given the TRI, they should return the correct value for any instruction (including calls).

readsRegister checks whether the instruction reads the specified register or its super register, but it does not check about sub register access. I need to check sub register access for safety.

[nemanjai]

In D39536#917677, @inouehrs wrote:

If we're adding a new peephole, it likely won't only be used for this one purpose. A more general name might be in order.

I changed the pass name. Do you have any suggestion on an alternative name?

If you agree that this would likely be used for other purposes, why not just name it PPCPostRAPeephole? Otherwise if you think this will likely only be used for this purpose, I suppose the name is fine.

This seems a bit fragile. I'm not sure there's any hard guarantee that the flag will be on the last source operand.

I modified to check the flag for both input operands.

Thanks.

These loops as well as a check for whether the instruction is a call seem a little odd. Why is it inadequate to use MachineInstr::readsRegister() and MachineInstr::modifiesRegister() for these purposes. Given the TRI, they should return the correct value for any instruction (including calls).

readsRegister checks whether the instruction reads the specified register or its super register, but it does not check about sub register access. I need to check sub register access for safety.

Hmm.. that certainly doesn't seem to be the case by just looking at the implementation. There's a check for Found = TRI->regsOverlap(MOReg, Reg); and I would assume this would return true for any overlap. But of course, this is based on just a cursory look at the code and I may be missing something.

[gberry]

I'm not sure adding a new pass that relies on kill flags is a good idea, since I believe they are slowly being phased out.
Also, if you stop using kill flags I believe you will need something like https://reviews.llvm.org/D39400 in order to avoid removing copies whose defs are needed for ABI/ISA reasons that aren't captured in the MI representation.

[inouehrs]

• rewrote without using kill flags as @gberry suggested.
• slightly increased coverage to support opportunity addressed by D39785.
• refactored to reduce duplicated code.

[inouehrs]

@gberry Thank you for the suggestions. I updated the implementation not to use kill flags.
Also, I updated not to optimize reg copies around ABI-dependent special registers such as stack pointer.
Additionally, the current version avoids optimization for specific ABI-dependent opcode (GETtlsldADDR), but I will use isRenamable flag after D39400 is merged.

[MatzeB]

Is this like the existing MachineCopyPropagation pass but working accross multiple blocks? Would D30751 solve your problem as well?

[inouehrs]

In D39536#926354, @MatzeB wrote:

Is this like the existing MachineCopyPropagation pass but working accross multiple blocks? Would D30751 solve your problem as well?

The two optimization are mostly disjoint.
Copy source forwarding optimizes

mr 3, 4
addi 5, 3, 1

to

mr 3, 4
addi 5, 4, 1

but this optimization intends to rewrite

addi 4, 3, 1 
mr 3, 4

to

addi 3, 3, 1

or eliminate

mr 4, 3
mr 3, 4

[gberry]

In D39536#927450, @inouehrs wrote:

In D39536#926354, @MatzeB wrote:

Is this like the existing MachineCopyPropagation pass but working accross multiple blocks? Would D30751 solve your problem as well?

The two optimization are mostly disjoint.
Copy source forwarding optimizes

mr 3, 4
addi 5, 3, 1

to

mr 3, 4
addi 5, 4, 1

but this optimization intends to rewrite

addi 4, 3, 1 
mr 3, 4

to

addi 3, 3, 1

or eliminate

mr 4, 3
mr 3, 4

FWIW, the MachineCopyPropagation already handles eliminating the second COPY in the second case above, and could fairly easily be extended to handle the other cases once the change to mark MachineOperands as renamable lands. It is currently limited to single block though. It also only currently deals with instructions whose opcode is COPY (i.e. it doesn't handle other target specific copy operations). I don't see any reason why all of these things couldn't be added to MachineCopyPropagation eventually, but I don't want to hold up your change because it might be made redundant later, especially since I can;t commit to making these extensions to MachineCopyProp.

[inouehrs]

@gberry Thank you for the comment!
Many redundant register copies (e.g. about 2/3 of the intra-BB redundancies) are generated by optimizers executed after COPYs are expanded to real instructions. To catch them, this optimization is run just before code emission.
So, MachineCopyPropagation, which is executed just after register allocation, may not be able to catch these opportunities.
(For example, when I run this pass just after pseudo instruction expansion, optimizations happen 7780 times during the bootstrap while they happen 10255 times if the pass is executed at the very last of the compilation.)

[inouehrs]

minor touch up in comments and formatting

[jtony]

lib/Target/PowerPC/PPCRegCopyElim.cpp

102

There are some other instructions which are equivalent to MR, do we want to handle them too in this patch? Some examples: ADDI Rx,Ry, 0 and ORI Rx,Ry,0

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

48

Minor nit: I know this is auto generated test cases, but this line can be simplified away. Similarly line 1 and line 54.

[inouehrs]

lib/Target/PowerPC/PPCRegCopyElim.cpp

102

I picked these instructions since they are emitted for PPC::COPY. Do you see ADDI Rx,Ry, 0 or ORI Rx,Ry,0 frequently? If so, I will add that opcode here.

[hfinkel]

Is this something that RDF copy propagation would do for us as well? @kparzysz might know. FWIW, if this is something that RDF would help with, I'd rather see our efforts put there rather than recreating a less-powerful version of that infrastructure just for this specific case.

lib/Target/PowerPC/PPCRegCopyElim.cpp

268

X2 is not always special (in leaf functions, it might be allocatable). You can check using:

MF->getRegInfo().isAllocatable(PPC::X2) or !getReservedRegs(*MF).test(PPC::X2) or similar.

[nemanjai]

Now that https://reviews.llvm.org/rL323991 has actually landed, can you re-evaluate whether this patch is still applicable and if so, whether it needs any changes. Also, have you looked into Hal's suggestion?

[inouehrs]

• check the reserved register using getReservedRegs instead of own check.
• rebased to the latest code

[inouehrs]

In D39536#996106, @nemanjai wrote:

Now that https://reviews.llvm.org/rL323991 has actually landed, can you re-evaluate whether this patch is still applicable and if so, whether it needs any changes. Also, have you looked into Hal's suggestion?

As long as I tested, COPY source forwarding (rL323991) does not affect this optimization. The number of optimizations happen in this pass are mostly unchanged by enabling/disabling the COPY source forwarding (11730 with COPY source forwarding and 11242 without COPY source forwarding during the bootstrap test).

Also, I updated the patch to address Hal's suggestion.

[inouehrs]

lib/Target/PowerPC/PPCRegCopyElim.cpp

268

Thank you so much for the suggestion. I totally replaced my own check with getReservedRegs (not only for X2). It makes the code cleaner.

[syzaara]

lib/Target/PowerPC/PPCRegCopyElim.cpp

12

s/copys/copies

87

Is this an old comment you forgot to remove? I don't see anything related to IsKill in this function.

121

I think this flow would be more clear if written like:

if (MO.isReg() && TRI->isSuperOrSubRegisterEq(MO.getReg(), Reg)) {
    if (MO.isUse())
        return false;
    else if(MO.isDef() ||  (MO.isRegMask() && MO.clobbersPhysReg(Reg)))
        SrcKilled = true; // we may still have use of Reg in this MI
}

134

s/seccessor/successor

173

Since findRegisterDefOperandIdx already checks for SrcReg, do we need to check DefMO.getReg() == SrcReg here?

196

MO.isUse() would be more clear

210

It seems confusing that we check for registers being equal with isSuperOrSubRegisterEq and then again with if (MO.getReg() == SrcReg).
Can we rewrite to something like:

if (MO.getReg() == SrcReg)
   TmpOperands.push_back(&MO);
else if (TRI->isSuperOrSubRegisterEq(MO.getReg(), SrcReg)) {
   IsClobbered = true;
   return nullptr;
}

314

This is repeated below for the second case on line 443
However, the second case also sets Simplified = CurrentInstrErased which doesn't seem to be set here.
Can this be rewritten in a way that we only have to do this in one place for both cases?

339

Can we put these checks of pred_size/DstLive/control flow for which we just continue into a separate function and do something like:

if (!controlFlowSupported())
    continue;

[syzaara]

lib/Target/PowerPC/PPCRegCopyElim.cpp

285

I'm finding this difficult to follow since there is a lot happening in the loop. Can we extract out more functionality into functions? From what I understand, maybe we can do something like:

if (DefMI)
   Simplified |= eliminateIntraBBCopy
else if (controlFlowSupported())
   Simplified |= elimanteInterBBCopy

[inouehrs]

• addressed comments from @syzaara
• rebased to the lates tcode and fix a failing test case

[inouehrs]

lib/Target/PowerPC/PPCRegCopyElim.cpp

121

They are calling different methods isSuperOrSubRegisterEq and isSubRegisterEq, but I gave a try to make the control flow clearer.

173

Yes, it intends to confirm that it is not sub/super register.

210

Fixed.
Originally, I intended to make the if-statement parallel as

• isSuperOrSubRegisterEq for DstReg
• isSuperOrSubRegisterEq for SrcReg

285

I hope it becomes easier to follow now.

[syzaara]

lib/Target/PowerPC/PPCRegCopyElim.cpp

81

I don't see any uses of TII, but there are uses of TRI. Maybe replace this with TRI?

431

Can we change this to

if (!isRegCopy(CopyMI, SrcMO, DstMO))
   continue;

so that we don't have to nest the rest of the code.

455

It seems a little messy to me for this function to have a parameter for OperandsToRewrite1. I wonder if it would be better to have another function like getOperandsToRewrite which we can call on line 482 after we know that we have erased an instruction.

[inouehrs]

• addresses @syzaara 's comments

[inouehrs]

lib/Target/PowerPC/PPCRegCopyElim.cpp

81

Removed TII. I do not add TRI as a member since TRI must be passed among static functions anyway.

455

To implement getOperandsToRewrite helper, we need to do almost same (potentially costly) iteration again in the helper. So I have not do this yet.

lib/Target/PowerPC/CMakeLists.txt

add_llvm_target(PowerPCCodeGen
   PPCTOCRegDeps.cpp
   PPCTLSDynamicCall.cpp
   PPCVSXCopy.cpp
   PPCReduceCRLogicals.cpp
   PPCVSXFMAMutate.cpp
   PPCVSXSwapRemoval.cpp
   PPCExpandISEL.cpp
   PPCPreEmitPeephole.cpp
+  PPCRegCopyElim.cpp
   )
 
 add_subdirectory(AsmParser)
 add_subdirectory(Disassembler)
 add_subdirectory(InstPrinter)
 add_subdirectory(TargetInfo)
 add_subdirectory(MCTargetDesc)

lib/Target/PowerPC/PPC.h

#endif
   FunctionPass *createPPCBranchSelectionPass();
   FunctionPass *createPPCBranchCoalescingPass();
   FunctionPass *createPPCQPXLoadSplatPass();
   FunctionPass *createPPCISelDag(PPCTargetMachine &TM, CodeGenOpt::Level OL);
   FunctionPass *createPPCTLSDynamicCallPass();
   FunctionPass *createPPCBoolRetToIntPass();
   FunctionPass *createPPCExpandISELPass();
   FunctionPass *createPPCPreEmitPeepholePass();
+  FunctionPass *createPPCRegCopyElimPass();
   void LowerPPCMachineInstrToMCInst(const MachineInstr *MI, MCInst &OutMI,
                                     AsmPrinter &AP, bool isDarwin);
   bool LowerPPCMachineOperandToMCOperand(const MachineOperand &MO,
                                          MCOperand &OutMO, AsmPrinter &AP,
                                          bool isDarwin);
 
   void initializePPCVSXFMAMutatePass(PassRegistry&);
   void initializePPCBoolRetToIntPass(PassRegistry&);
   void initializePPCExpandISELPass(PassRegistry &);
   void initializePPCPreEmitPeepholePass(PassRegistry &);
   void initializePPCTLSDynamicCallPass(PassRegistry &);
   void initializePPCMIPeepholePass(PassRegistry&);
+  void initializePPCRegCopyElimPass(PassRegistry &);
   extern char &PPCVSXFMAMutateID;
 
   namespace PPCII {
     
   /// Target Operand Flag enum.
   enum TOF {
     //===------------------------------------------------------------------===//
     // PPC Specific MachineOperand flags.

lib/Target/PowerPC/PPCRegCopyElim.cpp

+//===----- PPCRegCopyElim.cpp -- Redundant Register Copy Elimination -----===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===---------------------------------------------------------------------===//
+//
+// This pass aims to eliminate redundancy related to physical registers
+// after the register allocation.
+// So far, we eliminate the following two types of redundant register copys.
+//
+// 1) intra-BB redundant register copy
+//   li Y, 0          li X, 0
+//   mr X, Y    =>    (erase mr)
+//   ..               ..
+// 2) inter-BB partially redundant register copy
+//            BB1--------                             BB1--------
+//            | ..      |                             | ..      |
+//            | mr Y, X |                             | (erase) |
+//            | ..      |                             | ..      |
+//    with    -----------                    with     -----------
+//    1 pred /     |                         1 pred  /     |
+//  BB--------     |      BB--------      BB---------      |      BB---------
+//  | ..     |     |      | ..     |  =>  | mr Y, X |      |      | ..      |
+//  | ..     |     |      | ..     |      | ..      |      |      | mr X, Y |
+//  ----------     |      ----------      -----------      |      -----------
+//                 |     /  with                           |     /  with
+//            BB2--------   1 succ                    BB2--------   1 succ
+//            | ..      |                             | ..      |
+//            | mr X, Y |                             | (erase) |
+//            | ..      |                             | ..      |
+//            -----------                             -----------
+//
+//===---------------------------------------------------------------------===//
+
+#include "PPCInstrBuilder.h"
+#include "PPCTargetMachine.h"
+
+using namespace llvm;
+
+#define DEBUG_TYPE "ppc-regcopy-elim"
+
+namespace {
+
+struct PPCRegCopyElim : public MachineFunctionPass {
+
+  static char ID;
+  const PPCInstrInfo *TII;
+  MachineFunction *MF;
+
+  PPCRegCopyElim() : MachineFunctionPass(ID) {
+    initializePPCRegCopyElimPass(*PassRegistry::getPassRegistry());
+  }
+
+private:
+  // Initialize class variables.
+  void initialize(MachineFunction &MFParm);
+
+  // Perform peepholes.
+  bool eliminateRedundantRegCopy(void);
+
+public:
+  // Main entry point for this pass.
+  bool runOnMachineFunction(MachineFunction &MF) override {
+    if (skipFunction(MF.getFunction()))
+      return false;
+    initialize(MF);
+    bool Simplified = false;
+
+    Simplified |= eliminateRedundantRegCopy();
+    return Simplified;
+  }
+};
+
+// Initialize class variables.
+void PPCRegCopyElim::initialize(MachineFunction &MFParm) {
+  MF = &MFParm;
+  TII = MF->getSubtarget<PPCSubtarget>().getInstrInfo();
+  DEBUG(dbgs() <<
+        "*** PowerPC Redundant Register Copy Elimination pass ***\n\n");
+}
+
+// If MI is a register copy, this method returns true and set
+// source and destination operands in SrcOperand and DstOperand.
+// When IsKill is true, this method returns true only if the src operand
+// has kill flag set.
+static bool isRegCopy(MachineInstr &MI, MachineOperand* &SrcOperand,
+                      MachineOperand* &DstOperand) {
+  // Refer PPCInstrInfo::copyPhysReg to find opcodes used for copying
+  // the value in a physical register for each register class.
+  // Currently we do not optimize VSX registers (copied by xxlor),
+  // which may involve different register types, i.e. FPR and VRF.
+  unsigned Opc = MI.getOpcode();
+  if (Opc == PPC::FMR) {
+    DstOperand = &MI.getOperand(0);
+    SrcOperand = &MI.getOperand(1);
+    return true;
+  }
+  if ((Opc == PPC::OR8 || Opc == PPC::OR || Opc == PPC::VOR) &&
+      MI.getOperand(1).getReg() == MI.getOperand(2).getReg()) {
+    DstOperand = &MI.getOperand(0);
+    SrcOperand = &MI.getOperand(1);
+    return true;
+  }
+  return false;
+}
+
+// Returns true if MI is the last user of Reg.
+// The result should be equivalent with kill flag.
+static bool isLastUse(MachineInstr &MI, unsigned Reg,
+                      const TargetRegisterInfo *TRI) {
+  MachineBasicBlock *MBB = MI.getParent();
+  MachineBasicBlock::iterator MBBI = MI, MBBIE = MBB->end();
+  for (MBBI++; MBBI != MBBIE; MBBI++) {
+    if (MBBI->isDebugValue())
+      continue;
+    bool SrcKilled = false;
+    for (auto &MO : MBBI->operands()) {
+      if (MO.isReg() && !MO.isDef() &&
+          TRI->isSuperOrSubRegisterEq(MO.getReg(), Reg))
+        return false;
+
+      if ((MO.isReg() && MO.isDef() &&
+           TRI->isSubRegisterEq(MO.getReg(), Reg)) ||
+          (MO.isRegMask() && MO.clobbersPhysReg(Reg)))
+        SrcKilled = true; // we may still have use of Reg in this MI
+    }
+    if (SrcKilled)
+      return true;
+  }
+
+  // We look for Reg in the seccessor BB liveins.
+  for (auto &SuccMBB : MBB->successors())
+    for (auto &LiveIn : SuccMBB->liveins())
+      if (TRI->isSuperOrSubRegisterEq(LiveIn.PhysReg, Reg))
+        return false;
+
+  return true;
+}
+
+// We cannot optimize instructions with some special opcode or inline asm.
+static bool isUnsafeToOptimize(MachineInstr &MI) {
+  if (MI.isInlineAsm())
+    return true;
+  unsigned Opcode = MI.getOpcode();
+  if (Opcode == PPC::GETtlsldADDR || Opcode == PPC::GETtlsldADDR32)
+    return true;
+  return false;
+}
+
+// We iterate backward to find the def of SrcReg.
+// This returns pointer for the MI defining SrcReg (or nullptr if not found.)
+static MachineInstr*
+findDefBackward(MachineBasicBlock::reverse_iterator &MBBRI,
+                MachineBasicBlock &MBB, unsigned DstReg, unsigned SrcReg,
+                bool &IsClobbered, bool &IsDstUsed,
+                SmallVector<MachineOperand*, 8> &OperandsToRewrite,
+                const TargetRegisterInfo *TRI) {
+  IsDstUsed = false;
+  MachineBasicBlock::reverse_iterator MBBRIE = MBB.rend();
+  SmallVector<MachineOperand*, 2> TmpOperands;
+  for (; MBBRI != MBBRIE; MBBRI++) {
+    if (MBBRI->isDebugValue())
+      continue;
+
+    // If this instruction defines source reg of copy, this is the
+    // target for our optimization.
+    int Idx = MBBRI->findRegisterDefOperandIdx(SrcReg, false, true, TRI);
+    if (Idx != -1) {
+      MachineOperand &DefMO = MBBRI->getOperand(Idx);
+      if (DefMO.isReg() && DefMO.getReg() == SrcReg &&
+          !DefMO.isTied() && !DefMO.isImplicit() &&
+          !isUnsafeToOptimize(*MBBRI)) {
+        IsClobbered = false;
+        return &(*MBBRI);
+      }
+      else {
+        IsClobbered = true;
+        return nullptr;
+      }
+    }
+
+    // If this instruction conflicts with the reg copy, we give up here.
+    // MachineInstr->readsRegister() cannot be used since it does not catch
+    // accesses to a sub-register.
+    for (auto &MO : MBBRI->operands()) {
+      if (MO.isRegMask() && (MO.clobbersPhysReg(SrcReg) ||
+                             MO.clobbersPhysReg(DstReg))) {
+        IsClobbered = true;
+        return nullptr;
+      }
+      if (MO.isReg()) {
+        if (TRI->isSuperOrSubRegisterEq(MO.getReg(), DstReg)) {
+          if (!MO.isDef())
+            IsDstUsed = true;
+          else {
+            IsClobbered = true;
+            return nullptr;
+          }
+        }
+        if (TRI->isSuperOrSubRegisterEq(MO.getReg(), SrcReg)) {
+          // If this instruction uses source register of register copy,
+          // we need to remember the operand to replace it with destination
+          // register of copy. For example:
+          //   li r4, 1            li r3, 1
+          //   cmplwi r4, 0   ->   cmplwi r3, 0
+          //   mr r3, r4           (erase mr)
+          if (MO.getReg() == SrcReg)
+            TmpOperands.push_back(&MO);
+          else {
+            IsClobbered = true;
+            return nullptr;
+          }
+        }
+      }
+    }
+
+    if (!TmpOperands.empty()) {
+      OperandsToRewrite.append(TmpOperands.begin(), TmpOperands.end());
+      TmpOperands.clear();
+    }
+  }
+  IsClobbered = false;
+  return nullptr;
+}
+
+bool PPCRegCopyElim::eliminateRedundantRegCopy(void) {
+  const PPCSubtarget *PPCSubTarget = &MF->getSubtarget<PPCSubtarget>();
+  const PPCRegisterInfo *TRI = PPCSubTarget->getRegisterInfo();
+  bool Simplified = false;
+
+  auto ResetKillFlags = [](MachineInstr *MI, unsigned Reg) {
+    for (auto &MO : MI->uses())
+      if (MO.isReg() && MO.getReg() == Reg)
+        MO.setIsKill(false);
+  };
+
+  SmallPtrSet<MachineBasicBlock *, 32> WorkSet;
+  for (MachineBasicBlock &MBB : *MF)
+    WorkSet.insert(&MBB);
+
+  while (!WorkSet.empty()) {
+    MachineBasicBlock & MBB = **(WorkSet.begin());
+    WorkSet.erase(&MBB);
+    SmallPtrSet<MachineInstr *, 16> Visited;
+    bool CurrentInstrErased = false;
+    do {
+      CurrentInstrErased = false;
+      for (MachineInstr &CopyMI : MBB) {
+        if (CopyMI.isDebugValue())
+          continue;
+
+        MachineOperand *SrcMO = nullptr, *DstMO = nullptr;
+        if (isRegCopy(CopyMI, SrcMO, DstMO)) {
+          // We avoid processing same MI twice when we re-iterate this BB.
+          if (!Visited.insert(&CopyMI).second)
+            continue;
+
+          unsigned DstReg = DstMO->getReg();
+          unsigned SrcReg = SrcMO->getReg();
+
+          // We do not optimize instruction based on reserved registers, such as
+          // the stack pointer or the frame pointer.
+          auto ReservedRegs = TRI->getReservedRegs(*MF);
+          if (ReservedRegs.test(SrcReg) || ReservedRegs.test(DstReg))
+            continue;
+
+          MachineInstr *DefMI = nullptr;
+          bool IsClobbered = false;
+          SmallVector<MachineOperand*, 8> OperandsToRewrite1;
+
+          // We iterate instructions backward to find the def of the source
+          // of register copy or instructions conflicting with register copy
+          // (e.g. instructions that use destination reg of copy).
+          bool IsDstUsed = false;
+          MachineBasicBlock::reverse_iterator MBBRI = CopyMI;
+          DefMI = findDefBackward(++MBBRI, MBB, DstReg, SrcReg,
+                                  IsClobbered, IsDstUsed, OperandsToRewrite1, TRI);
+          if (IsClobbered)
+            continue;
+
+          // Def for the source of the register copy is found in the BB.
+          if (DefMI) {
+            if (!IsDstUsed) {
+              // We optimize within this block if possible.
+              bool IsKill = isLastUse(CopyMI, SrcReg, TRI);
+              // We can eliminate a redundant reg copy pair.
+              if (isRegCopy(*DefMI, SrcMO, DstMO) &&
+                  DefMI->getOpcode() == CopyMI.getOpcode() &&
+                  SrcReg == DstMO->getReg() && DstReg == SrcMO->getReg()) {
+                if (IsKill)
+                  DefMI->eraseFromParent();
+                else
+                  ResetKillFlags(DefMI, DstReg);
+              }
+              else {
+                // If the SrcReg of reg copy will not be used,
+                // we avoid register copy by modifing the def or SrcReg.
+                if (!IsKill)
+                  continue;
+                int DefIdx = DefMI->findRegisterDefOperandIdx(SrcReg, false, true, TRI);
+                assert(DefIdx != -1 && "DefMI does not have corresponding operand");
+                DefMI->getOperand(DefIdx).setReg(DstReg);
+              }
+
+              DEBUG(dbgs() << "Eliminating redundant register copy:\n");
+              DEBUG(CopyMI.dump());
+
+              CopyMI.eraseFromParent();
+              for (auto &MO : OperandsToRewrite1)
+                MO->setReg(DstReg);
+              CurrentInstrErased = true;
+              break;
+            }
+            continue;
+          }
+
+          // If no def and no conflicting instruction is found in this BB,
+          // from here, we handle redundancy among multiple BBs.
+          // We currently support following CFGs.
+          //
+          //         Pred1MBB
+          //          /  |    /
+          //   (SideMBB) | (Pred2MBB)
+          //        /    |  /
+          //            MBB
+          //
+          // 1) MBB doesn't have more than two predecessors.
+          // 2) Pred1MBB doesn't have more than two successors.
+          // 3) SideMBB and Pred2MBB are optional.
+          // 4) Pred2MBB has only one successor (MBB).
+          // 5) SideMBB has only one predecessor (Pred1MBB).
+          // 6) SideMBB and Pred2MBB may be the same BB.
+
+          // So far, we do not optimize if this BB has more than two
+          // predecessors not to increase the number of total instructions.
+          if (MBB.pred_size() > 2)
+            continue;
+
+          // Our optimization uses DstReg instead of SrcReg to bring data
+          // among BBs, so we need to confirm DstReg is not already used.
+          bool DstLive = false;
+          for (auto &LiveIn : MBB.liveins())
+            if (TRI->isSuperOrSubRegisterEq(LiveIn.PhysReg, DstReg)) {
+              DstLive = true;
+              break;
+            }
+          if (DstLive)
+            continue;
+
+          auto FirstPredBB = MBB.pred_begin();
+          for (auto &Pred1MBB : MBB.predecessors()) {
+            // We check the control flow among BBs before iterating.
+            // If the BBs does not match the above patterns we support,
+            // we give up here.
+            MachineBasicBlock *Pred2MBB = nullptr, *SideMBB = nullptr;
+            if (Pred1MBB->succ_size() > 2)
+              continue;
+            if (MBB.pred_size() == 2) {
+              Pred2MBB = (Pred1MBB == *FirstPredBB) ? *(FirstPredBB + 1):
+                                                      * FirstPredBB;
+              if (Pred2MBB->succ_size() > 1)
+                continue;
+            }
+            if (Pred1MBB->succ_size() == 2) {
+              auto FirstSuccBB = Pred1MBB->succ_begin();
+              SideMBB = (&MBB == *FirstSuccBB) ? *(FirstSuccBB + 1):
+                                                 * FirstSuccBB;
+              if (SideMBB->pred_size() > 1)
+                continue;
+            }
+
+            // As we did for the current MBB, we iterate instructions backward
+            // to find the def of the source of register copy, starting from
+            // the end of the BB.
+            DefMI = nullptr;
+            SmallVector<MachineOperand*, 8> OperandsToRewrite2;
+            MachineBasicBlock::reverse_iterator MBBRI = Pred1MBB->rbegin();
+            DefMI = findDefBackward(MBBRI, *Pred1MBB, DstReg, SrcReg,
+                                    IsClobbered, IsDstUsed, OperandsToRewrite2,
+                                    TRI);
+
+            // We keep going iff the def of the reg copy is another reg copy
+            // with reversed src and dst.
+            if (!(DefMI && isRegCopy(*DefMI, SrcMO, DstMO) &&
+                  DefMI->getOpcode() == CopyMI.getOpcode() &&
+                  SrcReg == DstMO->getReg() && DstReg == SrcMO->getReg()))
+              continue;
+
+            DEBUG(dbgs() << "Optimizing partially redundant reg copy pair:\n");
+            DEBUG(DefMI->dump());
+            DEBUG(CopyMI.dump());
+
+            // Here, we have found a partially redundant register copy pair.
+            // If the SrcReg of second reg copy is not used after it,
+            // we can eliminate or move both reg copy instructions;
+            // i.e. if we have SideMBB, we copy the first reg copy to its entry.
+            // Otherwise, we can erase it.
+            bool IsKill = isLastUse(CopyMI, SrcReg, TRI);
+            if (IsKill) {
+              if (SideMBB) {
+                SideMBB->splice(SideMBB->getFirstNonDebugInstr(), Pred1MBB,
+                                MachineBasicBlock::iterator(DefMI));
+                SideMBB->removeLiveIn(SrcReg);
+                if (!SideMBB->isLiveIn(DstReg))
+                  SideMBB->addLiveIn(DstReg);
+              }
+              else
+                DefMI->eraseFromParent();
+            }
+
+            // We move the second reg copy to Pred2MBB by inserting before
+            // the first terminator instructions (or at the end if no
+            // terminator in the BB).
+            if (Pred2MBB) {
+              MachineBasicBlock::iterator T = Pred2MBB->getFirstTerminator();
+              if (T == Pred2MBB->end())
+                Pred2MBB->push_back(MBB.remove(&CopyMI));
+              else
+                Pred2MBB->splice(T, &MBB, MachineBasicBlock::iterator(CopyMI));
+              // The copied register copy may be further optimized.
+              // So we will optimize this basic block later again.
+              WorkSet.insert(Pred2MBB);
+            }
+            else
+              CopyMI.eraseFromParent();
+
+            if (IsKill)
+              MBB.removeLiveIn(SrcReg);
+            MBB.addLiveIn(DstReg);
+
+            // We touch up some operands if we have found any.
+            for (auto &MO : OperandsToRewrite1)
+              MO->setReg(DstReg);
+            for (auto &MO : OperandsToRewrite2)
+              MO->setReg(DstReg);
+
+            if (!IsKill && DefMI->killsRegister(DstReg))
+              ResetKillFlags(DefMI, DstReg);
+
+            CurrentInstrErased = true;
+            break;
+          }
+
+          Simplified = CurrentInstrErased;
+          // If the current instruction has been eliminated,
+          // we cannot continue iteration, so restart it.
+          if (CurrentInstrErased)
+            break;
+        }
+      }
+    } while(CurrentInstrErased);
+  }
+  return Simplified;
+}
+
+} // end default namespace
+
+INITIALIZE_PASS_BEGIN(PPCRegCopyElim, DEBUG_TYPE,
+                   "PowerPC Redundant Register Copy Elimination", false, false)
+INITIALIZE_PASS_END(PPCRegCopyElim, DEBUG_TYPE,
+                   "PowerPC Redundant Register Copy Elimination", false, false)
+
+char PPCRegCopyElim::ID = 0;
+FunctionPass*
+llvm::createPPCRegCopyElimPass() { return new PPCRegCopyElim(); }

lib/Target/PowerPC/PPCTargetMachine.cpp

 static cl::
 opt<bool> DisableQPXLoadSplat("disable-ppc-qpx-load-splat", cl::Hidden,
                               cl::desc("Disable QPX load splat simplification"));
 
 static cl::
 opt<bool> DisableMIPeephole("disable-ppc-peephole", cl::Hidden,
                             cl::desc("Disable machine peepholes for PPC"));
 
+static cl::
+opt<bool> DisableRegCopyElim("disable-ppc-regcopy-elim", cl::Hidden,
+                        cl::desc("Disable register copy elimination for PPC"));
+
 static cl::opt<bool>
 EnableGEPOpt("ppc-gep-opt", cl::Hidden,
              cl::desc("Enable optimizations on complex GEPs"),
              cl::init(true));
 
 static cl::opt<bool>
 EnablePrefetch("enable-ppc-prefetching",
                   cl::desc("disable software prefetching on PPC"),
extern "C" void LLVMInitializePowerPCTarget() {
   RegisterTargetMachine<PPCTargetMachine> C(getThePPC64LETarget());
 
   PassRegistry &PR = *PassRegistry::getPassRegistry();
   initializePPCBoolRetToIntPass(PR);
   initializePPCExpandISELPass(PR);
   initializePPCPreEmitPeepholePass(PR);
   initializePPCTLSDynamicCallPass(PR);
   initializePPCMIPeepholePass(PR);
+  initializePPCRegCopyElimPass(PR);
 }
 
 /// Return the datalayout string of a subtarget.
 static std::string getDataLayoutString(const Triple &T) {
   bool is64Bit = T.getArch() == Triple::ppc64 || T.getArch() == Triple::ppc64le;
   std::string Ret;
 
   // Most PPC* platforms are big endian, PPC64LE is little endian.
if (!DisableQPXLoadSplat)
       addPass(createPPCQPXLoadSplatPass());
   }
 }
 
 void PPCPassConfig::addPreEmitPass() {
   addPass(createPPCPreEmitPeepholePass());
   addPass(createPPCExpandISELPass());
 
-  if (getOptLevel() != CodeGenOpt::None)
+  if (getOptLevel() != CodeGenOpt::None) {
+    // We try to eliminate redundant register copies among physical registers.
+    if (!DisableRegCopyElim)
+      addPass(createPPCRegCopyElimPass());
+
     addPass(createPPCEarlyReturnPass(), false);
+  }
+
   // Must run branch selection immediately preceding the asm printer.
   addPass(createPPCBranchSelectionPass(), false);
 }
 
 TargetTransformInfo
 PPCTargetMachine::getTargetTransformInfo(const Function &F) {
   return TargetTransformInfo(PPCTTIImpl(this, F));
 }

test/CodeGen/PowerPC/redundant_regcopy.ll

+; RUN: llc < %s -O2 -verify-machineinstrs -mtriple=powerpc64le-unknown-linux-gnu | FileCheck %s
+
+define i8* @func1(i8* %a, i1 %b) {
+; CHECK-LABEL: @func1
+; CHECK: bc
+; CHECK: # %bb.1
+; CHECK: mr 30, 3
+; CHECK: bl callee
+; CHECK: mr 3, 30
+; CHECK: .LBB0_2:
+; CHECK:  blr
+entry:
+  br i1 %b, label %exit, label %foo
+
+foo:
+  call void @callee()
+  br label %exit
+
+exit:
+  ret i8* %a
+}
+
+declare void @callee()

test/CodeGen/PowerPC/redundant_regcopy_1.mir

+# test for BB-local register copy elimination
+# RUN: llc -run-pass ppc-regcopy-elim -verify-machineinstrs -o - %s | FileCheck %s
+
+--- |
+  target datalayout = "E-m:e-i64:64-n32:64"
+  target triple = "powerpc64le-unknown-linux-gnu"
+  define signext i32 @func(i32 signext %i) {
+  entry:
+    ret i32 %i
+  }
+
+...
+---
+name:            func
+alignment:       2
+exposesReturnsTwice: false
+legalized:       false
+regBankSelected: false
+selected:        false
+tracksRegLiveness: true
+liveins:
+  - { reg: '$x3' }
+frameInfo:
+  isFrameAddressTaken: false
+  isReturnAddressTaken: false
+  hasStackMap:     false
+  hasPatchPoint:   false
+  stackSize:       0
+  offsetAdjustment: 0
+  maxAlignment:    0
+  adjustsStack:    false
+  hasCalls:        false
+  maxCallFrameSize: 0
+  hasOpaqueSPAdjustment: false
+  hasVAStart:      false
+  hasMustTailInVarArgFunc: false
+body:             |
+  bb.0.entry:
+    liveins: $x3
+
+    ; CHECK-LABEL: bb.0.entry:
+    ; CHECK: $x3 = ADDI8 killed $x3, 1
+    ; CHECK-NOT: OR8
+    $x4 = ADDI8 killed $x3, 1
+    $cr0 = CMPLDI $x4, 0
+    $x3 = OR8 $x4, killed $x4
+
+...
+

test/CodeGen/PowerPC/redundant_regcopy_2.mir

+# test for BB-local register copy elimination
+# RUN: llc -run-pass ppc-regcopy-elim -verify-machineinstrs -o - %s | FileCheck %s
+
+--- |
+  target datalayout = "E-m:e-i64:64-n32:64"
+  target triple = "powerpc64le-unknown-linux-gnu"
+  define i8* @func(i8* %a, i1 %b) {
+  entry:
+    br i1 %b, label %exit, label %foo
+  
+  foo:                                              ; preds = %entry
+    br label %exit
+  
+  exit:                                             ; preds = %foo, %entry
+    ret i8* %a
+  }
+  
+...
+---
+name:            func
+alignment:       2
+exposesReturnsTwice: false
+legalized:       false
+regBankSelected: false
+selected:        false
+tracksRegLiveness: true
+liveins:
+  - { reg: '$x3' }
+frameInfo:
+  isFrameAddressTaken: false
+  isReturnAddressTaken: false
+  hasStackMap:     false
+  hasPatchPoint:   false
+  stackSize:       0
+  offsetAdjustment: 0
+  maxAlignment:    0
+  adjustsStack:    false
+  hasCalls:        false
+  maxCallFrameSize: 0
+  hasOpaqueSPAdjustment: false
+  hasVAStart:      false
+  hasMustTailInVarArgFunc: false
+body:             |
+  bb.0.entry:
+    successors: %bb.2.exit, %bb.1.foo
+    liveins: $x3
+
+    ; CHECK-LABEL: bb.0.entry:
+    ; CHECK-NOT: OR8
+    ; CHECK: $cr0 = CMPLDI $x3, 0
+    $x4 = OR8 $x3, $x3
+    $cr0 = CMPLDI $x3, 0
+    BCC 76, killed $cr0, %bb.2.exit
+    B %bb.1.foo
+    
+  bb.1.foo:
+    liveins: $x4
+
+    ; CHECK-LABEL: bb.1.foo:
+    ; CHECK: $x4 = OR8 $x3, $x3
+    ; CHECK: $x3 = ADDI8 $x4, 123
+    $x4 = ADDI8 $x4, 123
+    B %bb.2.exit
+
+  bb.2.exit:
+    liveins: $x4
+    ; CHECK-LABEL: bb.2.exit:
+    ; CHECK-NOT: OR8
+    ; CHECK: BLR8
+    $cr0 = CMPLDI $x4, 0
+    $x3 = OR8 $x4, killed $x4
+    BLR8 implicit $lr8, implicit $rm
+
+...
+

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:   -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
+; 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*)
+