[MIR][MachineCSE] Implementing proper MachineInstr::getNumExplicitDefs()

[rtereshin]

Summary

Apparently, MachineInstr class definition as well as pretty much all of
the machine passes assume that the only kind of MachineInstr's operands
that is variadic for variadic opcodes is explicit non-definitions.

In particular, this assumption is made by MachineInstr::defs(), uses(),
and explicit_uses() methods, as well as by MachineCSE pass.

The assumption is incorrect judging from at least TableGen backend
implementation, that recognizes variable_ops in OutOperandList, and the
very existence of G_UNMERGE_VALUES generic opcode, or ARM load multiple
instructions, all of which have variadic defs.

In particular, MachineCSE pass breaks MIR with CSE'able G_UNMERGE_VALUES
instructions in it.

This commit implements MachineInstr::getNumExplicitDefs() similar to
pre-existing MachineInstr::getNumExplicitOperands(), fixes
MachineInstr::defs(), uses(), and explicit_uses(), and fixes MachineCSE
pass.

As the issue addressed seems to affect only machine passes that could be
ran mid-GlobalISel pipeline at the moment, the other passes aren't fixed
by this commit, like MachineLICM: that could be done on per-pass basis
when (if ever) they get adopted for GlobalISel.

[rtereshin]

ping

[rtereshin]

This comment was removed by rtereshin.

[rtereshin]

This comment was removed by rtereshin.

[rtereshin]

ping

[rtereshin]

ping

[rtereshin]

Ping

[rtereshin]

Ping

[arsenm]

LGTM

include/llvm/CodeGen/MachineInstr.h

365 ↗

(On Diff #142472)

Somewhat related, I think these need to be renamed to explicit_defs(). I've fixed similar bugs before from not checking the implicit def physical registers

lib/CodeGen/MachineCSE.cpp

555–556 ↗

(On Diff #142472)

I would probably add a separate getNumDefs for this

lib/CodeGen/MachineInstr.cpp

528–529 ↗

(On Diff #142472)

Maybe needs a comment explaining implicit operands always follow explicit

[rtereshin]

include/llvm/CodeGen/MachineInstr.h

365 ↗

(On Diff #142472)

I agree, will make it a separate commit.

uses is also quite confusing, because it's actually [explicit uses, implicit defs, implicit uses] range and therefore iterating over it for uses needs to be guarded with additional checks, while all the other ranges are precise and don't need such checks.

Well, "precise" with an assumption that "use" means everything but a register definition, that is register uses, immediates, etc. Which is inconsistent with MachineOperand::isUse predicate that asserts isReg() along the way.

Looks like in practice the majority of MachineInstr clients just gave up and opted out to iterating over all of the operands and doing all the checks they deem necessary. Sadly.

lib/CodeGen/MachineCSE.cpp

555–556 ↗

(On Diff #142472)

Will do.

lib/CodeGen/MachineInstr.cpp

528–529 ↗

(On Diff #142472)

Will add.

llvm/trunk/include/llvm/CodeGen/MachineInstr.h

const MachineOperand& getOperand(unsigned i) const {
     assert(i < getNumOperands() && "getOperand() out of range!");
     return Operands[i];
   }
   MachineOperand& getOperand(unsigned i) {
     assert(i < getNumOperands() && "getOperand() out of range!");
     return Operands[i];
   }
 
+  /// Returns the total number of definitions.
+  unsigned getNumDefs() const {
+    return getNumExplicitDefs() + MCID->getNumImplicitDefs();
+  }
+
   /// Return true if operand \p OpIdx is a subregister index.
   bool isOperandSubregIdx(unsigned OpIdx) const {
     assert(getOperand(OpIdx).getType() == MachineOperand::MO_Immediate &&
            "Expected MO_Immediate operand type.");
     if (isExtractSubreg() && OpIdx == 2)
       return true;
     if (isInsertSubreg() && OpIdx == 3)
       return true;
     if (isRegSequence() && OpIdx > 1 && (OpIdx % 2) == 0)
       return true;
     if (isSubregToReg() && OpIdx == 3)
       return true;
     return false;
   }
 
   /// Returns the number of non-implicit operands.
   unsigned getNumExplicitOperands() const;
 
+  /// Returns the number of non-implicit definitions.
+  unsigned getNumExplicitDefs() const;
+
   /// iterator/begin/end - Iterate over all operands of a machine instruction.
   using mop_iterator = MachineOperand *;
   using const_mop_iterator = const MachineOperand *;
 
   mop_iterator operands_begin() { return Operands; }
   mop_iterator operands_end() { return Operands + NumOperands; }
 
   const_mop_iterator operands_begin() const { return Operands; }
public:
   }
   iterator_range<const_mop_iterator> implicit_operands() const {
     return make_range(explicit_operands().end(), operands_end());
   }
   /// Returns a range over all explicit operands that are register definitions.
   /// Implicit definition are not included!
   iterator_range<mop_iterator> defs() {
     return make_range(operands_begin(),
-                      operands_begin() + getDesc().getNumDefs());
+                      operands_begin() + getNumExplicitDefs());
   }
   /// \copydoc defs()
   iterator_range<const_mop_iterator> defs() const {
     return make_range(operands_begin(),
-                      operands_begin() + getDesc().getNumDefs());
+                      operands_begin() + getNumExplicitDefs());
   }
   /// Returns a range that includes all operands that are register uses.
   /// This may include unrelated operands which are not register uses.
   iterator_range<mop_iterator> uses() {
-    return make_range(operands_begin() + getDesc().getNumDefs(),
-                      operands_end());
+    return make_range(operands_begin() + getNumExplicitDefs(), operands_end());
   }
   /// \copydoc uses()
   iterator_range<const_mop_iterator> uses() const {
-    return make_range(operands_begin() + getDesc().getNumDefs(),
-                      operands_end());
+    return make_range(operands_begin() + getNumExplicitDefs(), operands_end());
   }
   iterator_range<mop_iterator> explicit_uses() {
-    return make_range(operands_begin() + getDesc().getNumDefs(),
-                      operands_begin() + getNumExplicitOperands() );
+    return make_range(operands_begin() + getNumExplicitDefs(),
+                      operands_begin() + getNumExplicitOperands());
   }
   iterator_range<const_mop_iterator> explicit_uses() const {
-    return make_range(operands_begin() + getDesc().getNumDefs(),
-                      operands_begin() + getNumExplicitOperands() );
+    return make_range(operands_begin() + getNumExplicitDefs(),
+                      operands_begin() + getNumExplicitOperands());
   }
 
   /// Returns the number of the operand iterator \p I points to.
   unsigned getOperandNo(const_mop_iterator I) const {
     return I - operands_begin();
   }
 
   /// Access to memory operands of the instruction

llvm/trunk/lib/CodeGen/MachineCSE.cpp

for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E; ) {
     // Found a common subexpression, eliminate it.
     unsigned CSVN = VNT.lookup(MI);
     MachineInstr *CSMI = Exps[CSVN];
     LLVM_DEBUG(dbgs() << "Examining: " << *MI);
     LLVM_DEBUG(dbgs() << "*** Found a common subexpression: " << *CSMI);
 
     // Check if it's profitable to perform this CSE.
     bool DoCSE = true;
-    unsigned NumDefs = MI->getDesc().getNumDefs() +
-                       MI->getDesc().getNumImplicitDefs();
+    unsigned NumDefs = MI->getNumDefs();
 
     for (unsigned i = 0, e = MI->getNumOperands(); NumDefs && i != e; ++i) {
       MachineOperand &MO = MI->getOperand(i);
       if (!MO.isReg() || !MO.isDef())
         continue;
       unsigned OldReg = MO.getReg();
       unsigned NewReg = CSMI->getOperand(i).getReg();
 

llvm/trunk/lib/CodeGen/MachineInstr.cpp

void MachineInstr::eraseFromParentAndMarkDBGValuesForRemoval() {
   MI->eraseFromParent();
 }
 
 void MachineInstr::eraseFromBundle() {
   assert(getParent() && "Not embedded in a basic block!");
   getParent()->erase_instr(this);
 }
 
-/// getNumExplicitOperands - Returns the number of non-implicit operands.
-///
 unsigned MachineInstr::getNumExplicitOperands() const {
   unsigned NumOperands = MCID->getNumOperands();
   if (!MCID->isVariadic())
     return NumOperands;
 
-  for (unsigned i = NumOperands, e = getNumOperands(); i != e; ++i) {
-    const MachineOperand &MO = getOperand(i);
-    if (!MO.isReg() || !MO.isImplicit())
-      NumOperands++;
+  for (unsigned I = NumOperands, E = getNumOperands(); I != E; ++I) {
+    const MachineOperand &MO = getOperand(I);
+    // The operands must always be in the following order:
+    // - explicit reg defs,
+    // - other explicit operands (reg uses, immediates, etc.),
+    // - implicit reg defs
+    // - implicit reg uses
+    if (MO.isReg() && MO.isImplicit())
+      break;
+    ++NumOperands;
   }
   return NumOperands;
 }
 
+unsigned MachineInstr::getNumExplicitDefs() const {
+  unsigned NumDefs = MCID->getNumDefs();
+  if (!MCID->isVariadic())
+    return NumDefs;
+
+  for (unsigned I = NumDefs, E = getNumOperands(); I != E; ++I) {
+    const MachineOperand &MO = getOperand(I);
+    if (!MO.isReg() || !MO.isDef() || MO.isImplicit())
+      break;
+    ++NumDefs;
+  }
+  return NumDefs;
+}
+
 void MachineInstr::bundleWithPred() {
   assert(!isBundledWithPred() && "MI is already bundled with its predecessor");
   setFlag(BundledPred);
   MachineBasicBlock::instr_iterator Pred = getIterator();
   --Pred;
   assert(!Pred->isBundledWithSucc() && "Inconsistent bundle flags");
   Pred->setFlag(BundledSucc);
 }

llvm/trunk/test/CodeGen/AArch64/GlobalISel/machine-cse-mid-pipeline.mir

bb.0:
     %0:gpr32 = COPY $w0
     %1:gpr32 = COPY $w1
     %2:gpr32 = ADDWrr %0, %1
     %3:gpr32 = COPY %2
     %4:gpr32 = ADDWrr %3, %3
     $w0 = COPY %4
     RET_ReallyLR implicit $w0
 ...
+---
+name:            variadic_defs_unmerge_vector
+legalized:       true
+regBankSelected: false
+selected:        false
+body:             |
+  ; CHECK-LABEL: name: variadic_defs_unmerge_vector
+  ; CHECK:      [[COPY:%[0-9]+]]:_(<4 x s16>) = COPY $d0
+  ; CHECK-NEXT: [[UV0:%[0-9]+]]:_(s16), [[UV1:%[0-9]+]]:_(s16), [[UV2:%[0-9]+]]:_(s16), [[UV3:%[0-9]+]]:_(s16) = G_UNMERGE_VALUES [[COPY]](<4 x s16>)
+  ; CHECK-NEXT: [[ANYEXT0:%[0-9]+]]:_(s32) = G_ANYEXT [[UV0]](s16)
+  ; CHECK-NEXT: [[ANYEXT1:%[0-9]+]]:_(s32) = G_ANYEXT [[UV1]](s16)
+  ; CHECK-NEXT: [[ANYEXT2:%[0-9]+]]:_(s32) = G_ANYEXT [[UV2]](s16)
+  ; CHECK-NEXT: [[ANYEXT3:%[0-9]+]]:_(s32) = G_ANYEXT [[UV3]](s16)
+  ; CHECK-NEXT: [[ADD0:%[0-9]+]]:_(s32) = G_ADD [[ANYEXT0]], [[ANYEXT1]]
+  ; CHECK-NEXT: [[ADD1:%[0-9]+]]:_(s32) = G_ADD [[ANYEXT2]], [[ANYEXT3]]
+  ; CHECK-NEXT: [[ADD2:%[0-9]+]]:_(s32) = G_ADD [[ADD0]], [[ADD1]]
+  ; CHECK-NEXT: $w0 = COPY [[ADD2]](s32)
+  ; CHECK-NEXT: RET_ReallyLR implicit $w0
+  bb.0:
+    %0 :_(<4 x s16>) = COPY $d0
+    %1 :_(s16), %2 :_(s16), %3 :_(s16), %4 :_(s16) = G_UNMERGE_VALUES %0(<4 x s16>)
+    %5 :_(s16), %6 :_(s16), %7 :_(s16), %8 :_(s16) = G_UNMERGE_VALUES %0(<4 x s16>)
+    %9 :_(s16), %10:_(s16), %11:_(s16), %12:_(s16) = G_UNMERGE_VALUES %0(<4 x s16>)
+    %13:_(s16), %14:_(s16), %15:_(s16), %16:_(s16) = G_UNMERGE_VALUES %0(<4 x s16>)
+    %17:_(s32) = G_ANYEXT %1 (s16)
+    %18:_(s32) = G_ANYEXT %6 (s16)
+    %19:_(s32) = G_ANYEXT %11(s16)
+    %20:_(s32) = G_ANYEXT %16(s16)
+    %21:_(s32) = G_ADD %17, %18
+    %22:_(s32) = G_ADD %19, %20
+    %23:_(s32) = G_ADD %21, %22
+    $w0 = COPY %23(s32)
+    RET_ReallyLR implicit $w0
+...
+---
+name:            variadic_defs_unmerge_scalar
+legalized:       true
+regBankSelected: false
+selected:        false
+body:             |
+  ; CHECK-LABEL: name: variadic_defs_unmerge_scalar
+  ; CHECK:      [[COPY:%[0-9]+]]:_(s64) = COPY $d0
+  ; CHECK-NEXT: [[UV0:%[0-9]+]]:_(s16), [[UV1:%[0-9]+]]:_(s16), [[UV2:%[0-9]+]]:_(s16), [[UV3:%[0-9]+]]:_(s16) = G_UNMERGE_VALUES [[COPY]](s64)
+  ; CHECK-NEXT: [[ANYEXT0:%[0-9]+]]:_(s32) = G_ANYEXT [[UV0]](s16)
+  ; CHECK-NEXT: [[ANYEXT1:%[0-9]+]]:_(s32) = G_ANYEXT [[UV1]](s16)
+  ; CHECK-NEXT: [[ANYEXT2:%[0-9]+]]:_(s32) = G_ANYEXT [[UV2]](s16)
+  ; CHECK-NEXT: [[ANYEXT3:%[0-9]+]]:_(s32) = G_ANYEXT [[UV3]](s16)
+  ; CHECK-NEXT: [[ADD0:%[0-9]+]]:_(s32) = G_ADD [[ANYEXT0]], [[ANYEXT1]]
+  ; CHECK-NEXT: [[ADD1:%[0-9]+]]:_(s32) = G_ADD [[ANYEXT2]], [[ANYEXT3]]
+  ; CHECK-NEXT: [[ADD2:%[0-9]+]]:_(s32) = G_ADD [[ADD0]], [[ADD1]]
+  ; CHECK-NEXT: $w0 = COPY [[ADD2]](s32)
+  ; CHECK-NEXT: RET_ReallyLR implicit $w0
+  bb.0:
+    %0 :_(s64) = COPY $d0
+    %1 :_(s16), %2 :_(s16), %3 :_(s16), %4 :_(s16) = G_UNMERGE_VALUES %0(s64)
+    %5 :_(s16), %6 :_(s16), %7 :_(s16), %8 :_(s16) = G_UNMERGE_VALUES %0(s64)
+    %9 :_(s16), %10:_(s16), %11:_(s16), %12:_(s16) = G_UNMERGE_VALUES %0(s64)
+    %13:_(s16), %14:_(s16), %15:_(s16), %16:_(s16) = G_UNMERGE_VALUES %0(s64)
+    %17:_(s32) = G_ANYEXT %1 (s16)
+    %18:_(s32) = G_ANYEXT %6 (s16)
+    %19:_(s32) = G_ANYEXT %11(s16)
+    %20:_(s32) = G_ANYEXT %16(s16)
+    %21:_(s32) = G_ADD %17, %18
+    %22:_(s32) = G_ADD %19, %20
+    %23:_(s32) = G_ADD %21, %22
+    $w0 = COPY %23(s32)
+    RET_ReallyLR implicit $w0
+...
+---
+name:            variadic_defs_unmerge_scalar_asym
+legalized:       true
+regBankSelected: false
+selected:        false
+body:             |
+  ; CHECK-LABEL: name: variadic_defs_unmerge_scalar_asym
+  ; CHECK:      [[COPY:%[0-9]+]]:_(s64) = COPY $d0
+  ; CHECK-NEXT: [[UV0:%[0-9]+]]:_(s16), [[UV1:%[0-9]+]]:_(s16), [[UV2:%[0-9]+]]:_(s16), [[UV3:%[0-9]+]]:_(s16) = G_UNMERGE_VALUES [[COPY]](s64)
+  ; CHECK-NEXT: [[UV01:%[0-9]+]]:_(s32), [[UV23:%[0-9]+]]:_(s32) = G_UNMERGE_VALUES [[COPY]](s64)
+  ; CHECK-NEXT: [[ANYEXT0:%[0-9]+]]:_(s32) = G_ANYEXT [[UV0]](s16)
+  ; CHECK-NEXT: [[ANYEXT1:%[0-9]+]]:_(s32) = G_ANYEXT [[UV1]](s16)
+  ; CHECK-NEXT: [[ADD0:%[0-9]+]]:_(s32) = G_ADD [[ANYEXT0]], [[ANYEXT1]]
+  ; CHECK-NEXT: [[ADD1:%[0-9]+]]:_(s32) = G_ADD [[UV01]], [[UV23]]
+  ; CHECK-NEXT: [[ADD2:%[0-9]+]]:_(s32) = G_ADD [[ADD0]], [[ADD1]]
+  ; CHECK-NEXT: $w0 = COPY [[ADD2]](s32)
+  ; CHECK-NEXT: RET_ReallyLR implicit $w0
+  bb.0:
+    %0 :_(s64) = COPY $d0
+    %1 :_(s16), %2 :_(s16), %3 :_(s16), %4 :_(s16) = G_UNMERGE_VALUES %0(s64)
+    %9 :_(s32), %10:_(s32) = G_UNMERGE_VALUES %0(s64)
+    %5 :_(s16), %6 :_(s16), %7 :_(s16), %8 :_(s16) = G_UNMERGE_VALUES %0(s64)
+    %11:_(s32), %12:_(s32) = G_UNMERGE_VALUES %0(s64)
+    %17:_(s32) = G_ANYEXT %1 (s16)
+    %18:_(s32) = G_ANYEXT %6 (s16)
+    %21:_(s32) = G_ADD %17, %18
+    %22:_(s32) = G_ADD %9,  %12
+    %23:_(s32) = G_ADD %21, %22
+    $w0 = COPY %23(s32)
+    RET_ReallyLR implicit $w0
+...