[CodeGen] Add new function unionImplicitOps() to union implicit register

[ZhangKang]

Summary

The function MachineInstr::copyImplicitOps(MachineFunction &MF, const MachineInstr &MI) and MachineInstrBuilder::copyImplicitOps(const MachineInstr &OtherMI) will copy all implicit ops from Src_MI to Dst_MI.

When the Src_MI and Dst_MI has the same implicit ops, if we still call copyImplicitOps(), we will get some redundant implicit reg.

For example:
The Src_MI is:

BLR implicit $lr, implicit $rm, implicit killed $r3

The Dst_MI is:

BCLR $cr5lt, implicit $lr, implicit $rm

After calling Dst_MI.copyImplicitOps(Src_MI), we will get:

BCLR $cr5lt, implicit $lr, implicit $rm, implicit $lr, implicit $rm, implicit killed $r3

On the some targets like PowerPC, it's obvious that the second implicit $lr, implicit $rm is redundant, should be removed.
The right result should be:

BCLR $cr5lt, implicit $lr, implicit $rm, implicit killed $r3

The function copyImplicitOps() should skip those implicit operands which both Src_MI and Dst_MI have.

This patch is to add a new parameter SkipDuplicated for copyImplicitOps(), so we can choose whether we need skip those duplicated operands.

[lebedev.ri]

Passing-by remark: i feel like while the patch description really explains
what is happening in this patch, it does not mention at all
*why* all this is happening, why this shouldn't be happening, etc.

[arsenm]

I agree this is a workaround

[ZhangKang]

Rebase and fix the format.

[ZhangKang]

In D78010#1977637, @lebedev.ri wrote:

Passing-by remark: i feel like while the patch description really explains
what is happening in this patch, it does not mention at all
*why* all this is happening, why this shouldn't be happening, etc.

Have updated the summary to show *why* all this is happening, why this shouldn't be happening.

[steven.zhang]

In D78010#1977637, @lebedev.ri wrote:

Passing-by remark: i feel like while the patch description really explains
what is happening in this patch, it does not mention at all
*why* all this is happening, why this shouldn't be happening, etc.

For now, copyImplicitOps will blindly copy all the implicit ops no matter if we already have that implicit op. My understanding is that, we won't have any benefit if there is duplicate implicit operands. As this is a helper function to copy the implicit operands, I would suggest that, don't add a new parameter, just don't do the copy if it has. Does it make sense ?

[lkail]

For now, copyImplicitOps will blindly copy all the implicit ops no matter if we already have that implicit op. My understanding is that, we won't have any benefit if there is duplicate implicit operands. As this is a helper function to copy the implicit operands, I would suggest that, don't add a new parameter, just don't do the copy if it has. Does it make sense ?

I think it should apply to most register-based targets, I have no idea if it applies to stack-based targets, like webassembly.

[lebedev.ri]

In D78010#1979599, @steven.zhang wrote:

In D78010#1977637, @lebedev.ri wrote:

Passing-by remark: i feel like while the patch description really explains
what is happening in this patch, it does not mention at all
*why* all this is happening, why this shouldn't be happening, etc.

For now, copyImplicitOps will blindly copy all the implicit ops no matter if we already have that implicit op. My understanding is that, we won't have any benefit if there is duplicate implicit operands. As this is a helper function to copy the implicit operands, I would suggest that, don't add a new parameter, just don't do the copy if it has. Does it make sense ?

That would make more sense to me, yes.

[nemanjai]

I think that the question that needs to be answered is whether the duplicated implicit operands were intended or if they were just an oversight. If they were intended, we should understand that intention and see if it still makes sense and if anything relies on it. If it was just an oversight, we should see if anything relies on it or whether we are free to change the semantics.
In any case, if we do need to keep the existing semantics, I would much rather have separate functions to achieve the different semantics. Perhaps copyImplicitOperands() should remain as-is and we should add something like unionImplicitOperands() that would create the union that you describe here.

llvm/lib/CodeGen/MachineInstr.cpp

1430

Won't this throw assertions on regmasks? And what should the behaviour actually be on multiple regmasks?

[arsenm]

llvm/lib/CodeGen/MachineInstr.cpp

1430

This O(N^2) loop over operands isn't great

[ZhangKang]

In D78010#1980249, @nemanjai wrote:

I think that the question that needs to be answered is whether the duplicated implicit operands were intended or if they were just an oversight. If they were intended, we should understand that intention and see if it still makes sense and if anything relies on it. If it was just an oversight, we should see if anything relies on it or whether we are free to change the semantics.
In any case, if we do need to keep the existing semantics, I would much rather have separate functions to achieve the different semantics. Perhaps copyImplicitOperands() should remain as-is and we should add something like unionImplicitOperands() that would create the union that you describe here.

I have create a new function unionImplicitOperands(), it will skip those same implicit register and not support the RegMask operand.

llvm/lib/CodeGen/MachineInstr.cpp

1430

I will use a set to let the time complexity of finding same register to O(logN).

1430

Yes, it should throw assertion for RegMask. Because if an instruction has RegMask operand, it said some registers we can't use, it may use in callee. We can't simply copy RegMask or union RegMask from one instruction to another instruction

[ZhangKang]

add new function unionImplicitOps()

[lkail]

This comment was removed by lkail.

[lkail]

llvm/lib/CodeGen/MachineInstr.cpp

1446

Shall we just put this assertion after where MO is defined?

1455

Same as above.

[ZhangKang]

Move the assert before if condition.

[steven.zhang]

llvm/lib/CodeGen/MachineInstr.cpp

1440

Can we use the for range ?

[ZhangKang]

Using range-for to instead for-loop.

[ZhangKang]

llvm/lib/CodeGen/MachineInstr.cpp

1440

Done.

[steven.zhang]

llvm/lib/CodeGen/MachineInstr.cpp

1443

So, we don't need the isImplicit check any more.

[ZhangKang]

Remove the isImplicit().

[ZhangKang]

llvm/lib/CodeGen/MachineInstr.cpp

1443

Done.

[arsenm]

llvm/lib/Target/PowerPC/PPCEarlyReturn.cpp

80–81

Do you just want to setDesc here instead? It seems to me you expect the same implicit operands before and after in the test, and just want to change the opcode

[lkail]

llvm/test/CodeGen/PowerPC/early-ret.mir

112

Is there any instruction define $v2 between the last instruction of bb.0.entry and current one missing from check lines?

[ZhangKang]

llvm/lib/Target/PowerPC/PPCEarlyReturn.cpp

80–81

In fact, I have another patch https://reviews.llvm.org/D76042 to use setDesc(). I have set the patch D76042 be Change Planed.
In fact, if we use setDesc(), it means that we have assumed that the old instruction's implicit operands are same with the new instruction's.

If this patch can be approved, I will abandoned the patch D76042. I think use unionImplicitOps is better， it doesn't assume that the old instruction's implicit operands are same with the new instruction's.

llvm/test/CodeGen/PowerPC/early-ret.mir

112

No, no instruction is missing.

[steven.zhang]

llvm/lib/CodeGen/MachineInstr.cpp

1441

The assertion here is not needed. What we really need to care about is the regmask in the MI that we want to union. In fact, it is not hard to handle the case with regmask. I am ok to leave it as limitation.

[ZhangKang]

Remove the assert for src regmask operand.

[arsenm]

llvm/lib/Target/PowerPC/PPCEarlyReturn.cpp

80–81

There's no reason to not rely on this assumption though. I can imagine a use for unionImplicitOps, but not for contexts such as this

[ZhangKang]

llvm/lib/Target/PowerPC/PPCEarlyReturn.cpp

80–81

I have removed calling unionImplicitOps() in PPCEarlyReturn.cpp here, and enabled the patch D76042 to use setDesc() to fix the bug in PPCEarlyReturn.cpp as you suggested.
Now there is no scene to call unionImplicitOps().

[ZhangKang]

Remove call unionImplicitOps() in PPCEarlyReturn.cpp.

[ZhangKang]

@arsenm , I have removed calling unionImplicitOps() in PPCEarlyReturn.cpp.
Now there is no scene to call unionImplicitOps().
Do you think I should abandon this patch?

[arsenm]

In D78010#2029073, @ZhangKang wrote:

@arsenm , I have removed calling unionImplicitOps() in PPCEarlyReturn.cpp.
Now there is no scene to call unionImplicitOps().
Do you think I should abandon this patch?

Yes, unless there's a concrete use case (I can maybe imagine one, but I wouldn't encourage use of this without a better idea)

[ZhangKang]

No concrete use case, abandoned it.

llvm/include/llvm/CodeGen/MachineInstr.h

   /// Return a valid size if the instruction is a folded restore instruction.
   Optional<unsigned>
   getFoldedRestoreSize(const TargetInstrInfo *TII) const;
 
   /// Copy implicit register operands from specified
   /// instruction to this instruction.
   void copyImplicitOps(MachineFunction &MF, const MachineInstr &MI);
 
+  /// Union implicit register operands from specified
+  /// instruction to this instruction.
+  void unionImplicitOps(MachineFunction &MF, const MachineInstr &MI);
+
   /// Debugging support
   /// @{
   /// Determine the generic type to be printed (if needed) on uses and defs.
   LLT getTypeToPrint(unsigned OpIdx, SmallBitVector &PrintedTypes,
                      const MachineRegisterInfo &MRI) const;
 
   /// Return true when an instruction has tied register that can't be determined
   /// by the instruction's descriptor. This is useful for MIR printing, to

llvm/include/llvm/CodeGen/MachineInstrBuilder.h

public:
 
   /// Copy all the implicit operands from OtherMI onto this one.
   const MachineInstrBuilder &
   copyImplicitOps(const MachineInstr &OtherMI) const {
     MI->copyImplicitOps(*MF, OtherMI);
     return *this;
   }
 
+  /// Union all the implicit operands from OtherMI onto this one.
+  const MachineInstrBuilder &
+  unionImplicitOps(const MachineInstr &OtherMI) const {
+    MI->unionImplicitOps(*MF, OtherMI);
+    return *this;
+  }
+
   bool constrainAllUses(const TargetInstrInfo &TII,
                         const TargetRegisterInfo &TRI,
                         const RegisterBankInfo &RBI) const {
     return constrainSelectedInstRegOperands(*MI, TII, TRI, RBI);
   }
 };
 
 /// Builder interface. Specify how to create the initial instruction itself.

llvm/lib/CodeGen/MachineInstr.cpp

 #include "llvm/CodeGen/MachineInstr.h"
 #include "llvm/ADT/APFloat.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/FoldingSet.h"
 #include "llvm/ADT/Hashing.h"
 #include "llvm/ADT/None.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallBitVector.h"
+#include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/SmallString.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/Loads.h"
 #include "llvm/Analysis/MemoryLocation.h"
 #include "llvm/CodeGen/GlobalISel/RegisterBank.h"
 #include "llvm/CodeGen/MachineBasicBlock.h"
 #include "llvm/CodeGen/MachineFrameInfo.h"

 /// copyImplicitOps - Copy implicit register operands from specified
 /// instruction to this instruction.
 void MachineInstr::copyImplicitOps(MachineFunction &MF,
                                    const MachineInstr &MI) {
   for (unsigned i = MI.getDesc().getNumOperands(), e = MI.getNumOperands();
        i != e; ++i) {
     const MachineOperand &MO = MI.getOperand(i);
     if ((MO.isReg() && MO.isImplicit()) || MO.isRegMask())
       addOperand(MF, MO);
   }
 }
 
+/// unionImplicitOps - Union implicit register operands from specified
+/// instruction to this instruction. The instruction shouldn't have RegMask
+/// operand.
+void MachineInstr::unionImplicitOps(MachineFunction &MF,
+                                    const MachineInstr &MI) {
+  SmallSet<Register, 8> ImpRegSet;
+  for (const MachineOperand &MO : implicit_operands()) {
+    assert(!MO.isRegMask() && "Don't support union for RegMask operand");
+
+    if (MO.isReg())
+      ImpRegSet.insert(MO.getReg());
+  }
+
+  for (const MachineOperand &MO : MI.implicit_operands()) {
+    assert(!MO.isRegMask() && "Don't support union for RegMask operand");
+
+    if (MO.isReg() && !ImpRegSet.count(MO.getReg()))
+      addOperand(MF, MO);
+  }
+}
+
 bool MachineInstr::hasComplexRegisterTies() const {
   const MCInstrDesc &MCID = getDesc();
   for (unsigned I = 0, E = getNumOperands(); I < E; ++I) {
     const auto &Operand = getOperand(I);
     if (!Operand.isReg() || Operand.isDef())
       // Ignore the defined registers as MCID marks only the uses as tied.
       continue;
     int ExpectedTiedIdx = MCID.getOperandConstraint(I, MCOI::TIED_TO);
     int TiedIdx = Operand.isTied() ? int(findTiedOperandIdx(I)) : -1;

llvm/lib/Target/PowerPC/PPCEarlyReturn.cpp

bool processBlock(MachineBasicBlock &ReturnMBB) {
         for (MachineBasicBlock::iterator J = (*PI)->getLastNonDebugInstr();;) {
           if (J == (*PI)->end())
             break;
 
           if (J->getOpcode() == PPC::B) {
             if (J->getOperand(0).getMBB() == &ReturnMBB) {
               // This is an unconditional branch to the return. Replace the
               // branch with a blr.
               BuildMI(**PI, J, J->getDebugLoc(), TII->get(I->getOpcode()))
-                  .copyImplicitOps(*I);
+                  .unionImplicitOps(*I);
               MachineBasicBlock::iterator K = J--;
               K->eraseFromParent();
               BlockChanged = true;
               ++NumBLR;
               continue;
             }
           } else if (J->getOpcode() == PPC::BCC) {
             if (J->getOperand(2).getMBB() == &ReturnMBB) {
               // This is a conditional branch to the return. Replace the branch
               // with a bclr.
               BuildMI(**PI, J, J->getDebugLoc(), TII->get(PPC::BCCLR))
                   .addImm(J->getOperand(0).getImm())
                   .addReg(J->getOperand(1).getReg())
-                  .copyImplicitOps(*I);
+                  .unionImplicitOps(*I);
               MachineBasicBlock::iterator K = J--;
               K->eraseFromParent();
               BlockChanged = true;
               ++NumBCLR;
               continue;
             }
           } else if (J->getOpcode() == PPC::BC || J->getOpcode() == PPC::BCn) {
             if (J->getOperand(1).getMBB() == &ReturnMBB) {
               // This is a conditional branch to the return. Replace the branch
               // with a bclr.
               BuildMI(
                   **PI, J, J->getDebugLoc(),
                   TII->get(J->getOpcode() == PPC::BC ? PPC::BCLR : PPC::BCLRn))
                   .addReg(J->getOperand(0).getReg())
-                  .copyImplicitOps(*I);
+                  .unionImplicitOps(*I);
               MachineBasicBlock::iterator K = J--;
               K->eraseFromParent();
               BlockChanged = true;
               ++NumBCLR;
               continue;
             }
           } else if (J->isBranch()) {
             if (J->isIndirectBranch()) {

llvm/test/CodeGen/PowerPC/early-ret-verify.mir

bb.3:
     renamable $cr5lt = CRAND killed renamable $cr0eq, killed renamable $cr1lt, implicit $cr1, implicit $cr0
     BCn killed renamable $cr5lt, %bb.2
   
   bb.4:
     BLR implicit $lr, implicit $rm
 
   ; CHECK-LABEL: testEarlyRet
   ; CHECK: bb.0.entry:
-  ; CHECK:   BCLR $cr5lt, implicit $lr, implicit $rm, implicit $lr, implicit $rm
+  ; CHECK:   BCLR $cr5lt, implicit $lr, implicit $rm
   ; CHECK: bb.1:
   ; CHECK:   renamable $r3 = IMPLICIT_DEF
   ; CHECK:   renamable $r4 = IMPLICIT_DEF
   ; CHECK: bb.2:
   ; CHECK:   $r5 = OR $r4, $r4
   ; CHECK:   renamable $r4 = ADDIC killed $r4, 1, implicit-def $carry
   ; CHECK:   $r6 = OR $r3, $r3
   ; CHECK:   renamable $r3 = ADDZE killed $r3, implicit-def dead $carry, implicit killed $carry

llvm/test/CodeGen/PowerPC/early-ret.mir

bb.2.entry:
     liveins: $r3, $r4, $cr0eq, $cr0lt, $cr0un, $cr0, $cr0gt, $r3, $r3, $r4, $r3, $cr0gt
 
     BLR implicit $lr, implicit $rm, implicit killed $r3
 
   ; CHECK-LABEL: name: testBLR
   ; CHECK: bb.0.entry:
   ; CHECK:   renamable $cr0 = CMPWI renamable $r3, 0
   ; CHECK:   BC killed renamable $cr0gt, %bb.1
-  ; CHECK:   BLR implicit $lr, implicit $rm, implicit $lr, implicit $rm, implicit killed $r3
+  ; CHECK:   BLR implicit $lr, implicit $rm, implicit killed $r3
   ; CHECK: bb.1.entry:
   ; CHECK:   renamable $r3 = ADDI killed renamable $r4, 0
   ; CHECK:   BLR implicit $lr, implicit $rm, implicit killed $r3
 ...
 
 
 ---
 name:            testBCLRn
body:             |
   bb.3:
     liveins: $v2
 
     BLR implicit $lr, implicit $rm, implicit killed $v2
 
   ; CHECK-LABEL: name: testBCLR
   ; CHECK: bb.0.entry:
   ; CHECK:   renamable $cr0 = FCMPUS killed renamable $f3, killed renamable $f4
-  ; CHECK:   BCLR $cr0eq, implicit $lr, implicit $rm, implicit $lr, implicit $rm, implicit killed $v2
+  ; CHECK:   BCLR $cr0eq, implicit $lr, implicit $rm, implicit killed $v2
   ; CHECK: bb.1.entry:
   ; CHECK:   renamable $cr0 = FCMPUS killed renamable $f1, killed renamable $f2
   ; CHECK:   BCLRn killed renamable $cr0eq, implicit $lr, implicit $rm, implicit killed $v2
   ; CHECK: bb.2:
   ; CHECK:   $v2 = VOR killed $v3, $v3
   ; CHECK:   BLR implicit $lr, implicit $rm, implicit killed $v2
 ...
 
 
 ---
 name:            testBCCLR
body:             |
 
   bb.2:
     BLR implicit $lr, implicit $rm
 
   ; CHECK-LABEL: name: testBCCLR
   ; CHECK: bb.0.entry:
   ; CHECK: renamable $r4 = LI 0
   ; CHECK: renamable $cr0 = CMPLWI killed renamable $r4, 0
-  ; CHECK: BCCLR 68, $cr0, implicit $lr, implicit $rm, implicit $lr, implicit $rm
+  ; CHECK: BCCLR 68, $cr0, implicit $lr, implicit $rm
   ; CHECK: bb.1:
-  ; CHECK: BCCLR 68, $cr0, implicit $lr, implicit $rm, implicit $lr, implicit $rm
+  ; CHECK: BCCLR 68, $cr0, implicit $lr, implicit $rm
   ; CHECK: BLR implicit $lr, implicit $rm
 ...