[GlobalISel] LegalizationArtifactCombiner: Fix a bug in tryCombineMerges

[volkan]

Summary

Like COPY instructions explained in D70616, we don't check the constraints
when combining G_UNMERGE_VALUES. Use the same logic used in D70616 to check
if registers can be replaced, or a COPY instruction needs to be built.

[volkan]

@Petar.Avramovic Could you take a look at the failing Mips tests?

[aditya_nandakumar]

llvm/include/llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h

431

I think we're going to see this pattern multiple places. It would be unfortunate if we replicate this everywhere. I'd rather generate copies always and let the Combiner clean up redundant copies. Alternatively we could make a common function and make sure it's used everywhere (say replaceRegWithNewReg or something).

[Petar.Avramovic]

RegbankSelect doesn't track newly created instruction and I had to set reg bank manually. Here is the patch that sets regbank for newly created COPY instructions

D70564_mips.diff196 KBDownload

.

llvm/include/llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h

431

As far as I understand COPY should turn to cross bank move instruction.
Considering all the places where LegalizationArtifactCombiner is used now I think that replaceRegWithNewRegOrCopy should do the following:

• both FromReg and ToReg have different concrete bank/class: build copy (this is a cross regbank move).
• FromReg has bank/class ToReg does not: set ToReg's bank to Bank and MRI.replaceRegWith(FromReg, ToReg). If there is a regbank conflict here regBankSelect will find about it and make copy when it reaches ToReg. There is good chance we didn't need this copy so don't generate one.

%ToReg = G_ABC
%123 = G_MERGE %ToReg, ToReg1, ToReg2
%FromReg(Bank) , FromReg1, FromReg2 ... = G_UNMERGE %123
... = G_XYZ %FromReg(Bank)
-> 
%ToReg(Bank) = G_ABC
... = G_XYZ %ToReg(Bank)

• ToReg has bank FromReg does not: just MRI.replaceRegWith(FromReg, ToReg). ToReg will keep its bank. If we made copy here it would only have bank for use register and regbankselect would set same bank to def register (that copy is not cross regbank move).

%ToReg(Bank) = G_ABC 
%123 = G_MERGE  %ToReg, ToReg1, ToReg2
%FromReg , FromReg1, FromReg2 ... = G_UNMERGE %123
... = G_XYZ %FromReg
-> 
%ToReg(Bank) = G_ABC
... = G_XYZ %ToReg(Bank)

• otherwise FromReg and ToReg have same(or don't have one at all) class/bank: MRI.replaceRegWith(FromReg, ToReg) is fine.

In summary don't make copy if its likely to be redundant(i.e. not a cross register bank move). Also I we could use replaceRegWithNewRegOrCopy in all places where COPY is made during legalizer to reduce number or generated COPYs , e.g. MachineIRBuilder::buildAnyExtOrTrunc (used in trunc+anyext combine).

llvm/test/CodeGen/AArch64/GlobalISel/artifact-combine-merge-with-constraints.mir

2 ↗

(On Diff #230524)

What is the motivation for this in legalizer?
To my understanding Legalizer should not be aware of register banks. Do you have some tests that run through the full globalisel pipeline and require this change to work?

[volkan]

In D70564#1756698, @Petar.Avramovic wrote:

RegbankSelect doesn't track newly created instruction and I had to set reg bank manually. Here is the patch that sets regbank for newly created COPY instructions

D70564_mips.diff196 KBDownload

.

Thanks, I'll update the patch.

llvm/include/llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h

431

I'll add a separate function for this and try to eliminate redundant COPY instructions.

llvm/test/CodeGen/AArch64/GlobalISel/artifact-combine-merge-with-constraints.mir

2 ↗

(On Diff #230524)

What is the motivation for this in legalizer?

The patch doesn't do anything special in the legalizer. This tests is running legalizer because LegalizationArtifactCombiner is a part of the legalizer pass.

To my understanding Legalizer should not be aware of register banks.

I don't think that's the case. It's possible to build target instructions with register constraints in (or before) the legalizer.

Do you have some tests that run through the full globalisel pipeline and require this change to work?

I don't have any other tests as this is failing on our out-of-tree target, but I'm not sure why we need a test case running the whole pipeline.

[volkan]

In D70564#1757046, @volkan wrote:

In D70564#1756698, @Petar.Avramovic wrote:

RegbankSelect doesn't track newly created instruction and I had to set reg bank manually. Here is the patch that sets regbank for newly created COPY instructions

D70564_mips.diff196 KBDownload

.

Thanks, I'll update the patch.

Actually, I think Mips changes should be a separate commit. Could you create a differential revision for it?

llvm/include/llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h

431

Looks like we need to fix CombinerHelper::matchCombineCopy too. I'll create a differential revision for it first, then we share the same code.

[volkan]

llvm/include/llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h

431

Created D70616.

[volkan]

• Added a function called canReplaceReg to share the code.
• Added a function called replaceRegOrBuildCopy that tries to replace the registers if the constraints match, and builds a COPY otherwise.

[aditya_nandakumar]

llvm/include/llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h

289

We should probably be notifying the observer here...

[volkan]

• Notify the observer when replacing registers.

[volkan]

llvm/include/llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h

289

Right, updated the patch.

[Petar.Avramovic]

With removed xfail from tests, this looks good to me. I would like to hear if other reviewers have comments.

llvm/include/llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h

285

Where will we use replaceRegOrBuildCopy so it has to be static?
I think that eventually Observer should end up as field in LegalizationArtifactCombiner like in LegalizerHelper. There are a few LLVM_DEBUG(dbgs() << ".. Combine MI: " << MI;); around and Observer could handle them.

llvm/test/CodeGen/Mips/GlobalISel/regbankselect/long_ambiguous_chain_s32.mir

3–6 ↗

(On Diff #230734)

With updated patch there are no changes in regbankselect tests, you can remove XFAIL. Register we are replacing in combine has no constraints.

[volkan]

llvm/include/llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h

285

I'm not sure if we need to have a separate function for this, I added it based on the initial review. I can move this logic into tryCombineMerges as an alternative. Regarding the observer, it makes sense to pass the observer to simplify the functions, but it probably shouldn't be a part of this change. Also, I'm not sure if we still want to keep LegalizationArtifactCombiner as discussed in D65894.

llvm/test/CodeGen/Mips/GlobalISel/regbankselect/long_ambiguous_chain_s32.mir

3–6 ↗

(On Diff #230734)

I'll do that, thanks!

[volkan]

• Removed XFAILs.

[paquette]

llvm/include/llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h

289

I think we can simplify the logic a bit here:

if (!llvm::canReplaceReg(DstReg, SrcReg, MRI) {
   Builder.buildCopy(DstReg, SrcReg);
   return;
}

SmallVector<MachineInstr *, 4> UseMIs;
// ...

llvm/lib/CodeGen/GlobalISel/Utils.cpp

165

Redundant comment?

172

Don't need to check both DstTy.isValid() and SrcTy.isValid(), since DstTy.isValid() == SrcTy.isValid() at this point.

[volkan]

• Rebased and updated based on the feedback.

[arsenm]

llvm/lib/CodeGen/GlobalISel/Utils.cpp

162

You can do .isPhysical()

171–172

This still looks redundant to me. (DstTy.isValid() != SrcTy.isValid()) is implied by DstTy != SrcTy

175–178

Just check getRegClassOrRegBank(Src) == getRegClassOrRegBank(Dst)?

183–185

Check these first and short circuit the source checks?

183–185

This can also use getRegClassOrRegBank instead of checking the two separately?

[volkan]

• Simplified llvm::canReplaceReg(..).

[arsenm]

LGTK

[arsenm]

llvm/lib/CodeGen/GlobalISel/Utils.cpp

168–171

You can fold this into return x || (...

[volkan]

• Simplified llvm::canReplaceReg(..) a bit more.

[volkan]

Committed in 187686a22f97662c981b9bffb998b6010ae1c401.

llvm/include/llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h

case TargetOpcode::G_CONCAT_VECTORS: {
       // require more intermediate unmerges.
       if (ConvertOp == TargetOpcode::G_TRUNC)
         return DestTy.getSizeInBits() <= OpEltSize;
       return DestTy.getSizeInBits() >= OpEltSize;
     }
     }
   }
 
+  /// Try to replace DstReg with SrcReg or build a COPY instruction
+  /// depending on the register constraints.
+  static void replaceRegOrBuildCopy(Register DstReg, Register SrcReg,
+                                    MachineRegisterInfo &MRI,
+                                    MachineIRBuilder &Builder,
+                                    SmallVectorImpl<Register> &UpdatedDefs,
+                                    GISelObserverWrapper &Observer) {
+    if (!llvm::canReplaceReg(DstReg, SrcReg, MRI)) {
+      Builder.buildCopy(DstReg, SrcReg);
+      UpdatedDefs.push_back(DstReg);
+      return;
+    }
+    SmallVector<MachineInstr *, 4> UseMIs;
+    // Get the users and notify the observer before replacing.
+    for (auto &UseMI : MRI.use_instructions(DstReg)) {
+      UseMIs.push_back(&UseMI);
+      Observer.changingInstr(UseMI);
+    }
+    // Replace the registers.
+    MRI.replaceRegWith(DstReg, SrcReg);
+    UpdatedDefs.push_back(SrcReg);
+    // Notify the observer that we changed the instructions.
+    for (auto *UseMI : UseMIs)
+      Observer.changedInstr(*UseMI);
+  }
+
   bool tryCombineMerges(MachineInstr &MI,
                         SmallVectorImpl<MachineInstr *> &DeadInsts,
-                        SmallVectorImpl<Register> &UpdatedDefs) {
+                        SmallVectorImpl<Register> &UpdatedDefs,
+                        GISelObserverWrapper &Observer) {
     assert(MI.getOpcode() == TargetOpcode::G_UNMERGE_VALUES);
 
     unsigned NumDefs = MI.getNumOperands() - 1;
     MachineInstr *SrcDef =
         getDefIgnoringCopies(MI.getOperand(NumDefs).getReg(), MRI);
     if (!SrcDef)
       return false;
 
if (NumMergeRegs < NumDefs) {
         markInstAndDefDead(MI, *MergeI, DeadInsts);
         return true;
       }
 
       assert(DestTy == MergeSrcTy &&
              "Bitcast and the other kinds of conversions should "
              "have happened earlier");
 
+      Builder.setInstr(MI);
       for (unsigned Idx = 0; Idx < NumDefs; ++Idx) {
-        Register NewDef = MergeI->getOperand(Idx + 1).getReg();
-        MRI.replaceRegWith(MI.getOperand(Idx).getReg(), NewDef);
-        UpdatedDefs.push_back(NewDef);
+        Register DstReg = MI.getOperand(Idx).getReg();
+        Register SrcReg = MergeI->getOperand(Idx + 1).getReg();
+        replaceRegOrBuildCopy(DstReg, SrcReg, MRI, Builder, UpdatedDefs,
+                              Observer);
       }
     }
 
     markInstAndDefDead(MI, *MergeI, DeadInsts);
     return true;
   }
 
   static bool isMergeLikeOpcode(unsigned Opc) {
     switch (Opc) {
case TargetOpcode::G_ANYEXT:
       break;
     case TargetOpcode::G_ZEXT:
       Changed = tryCombineZExt(MI, DeadInsts, UpdatedDefs);
       break;
     case TargetOpcode::G_SEXT:
       Changed = tryCombineSExt(MI, DeadInsts, UpdatedDefs);
       break;
     case TargetOpcode::G_UNMERGE_VALUES:
-      Changed = tryCombineMerges(MI, DeadInsts, UpdatedDefs);
+      Changed = tryCombineMerges(MI, DeadInsts, UpdatedDefs, WrapperObserver);
       break;
     case TargetOpcode::G_EXTRACT:
       Changed = tryCombineExtract(MI, DeadInsts, UpdatedDefs);
       break;
     case TargetOpcode::G_TRUNC:
       Changed = tryCombineTrunc(MI, DeadInsts, UpdatedDefs);
       if (!Changed) {
         // Try to combine truncates away even if they are legal. As all artifact

llvm/include/llvm/CodeGen/GlobalISel/Utils.h

 ///
 // FIXME: Not all instructions have the same number of operands. We should
 // probably expose a constrain helper per operand and let the target selector
 // constrain individual registers, like fast-isel.
 bool constrainSelectedInstRegOperands(MachineInstr &I,
                                       const TargetInstrInfo &TII,
                                       const TargetRegisterInfo &TRI,
                                       const RegisterBankInfo &RBI);
+
+/// Check if DstReg can be replaced with SrcReg depending on the register
+/// constraints.
+bool canReplaceReg(Register DstReg, Register SrcReg, MachineRegisterInfo &MRI);
+
 /// Check whether an instruction \p MI is dead: it only defines dead virtual
 /// registers, and doesn't have other side effects.
 bool isTriviallyDead(const MachineInstr &MI, const MachineRegisterInfo &MRI);
 
 /// Report an ISel error as a missed optimization remark to the LLVMContext's
 /// diagnostic stream.  Set the FailedISel MachineFunction property.
 void reportGISelFailure(MachineFunction &MF, const TargetPassConfig &TPC,
                         MachineOptimizationRemarkEmitter &MORE,

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

bool CombinerHelper::tryCombineCopy(MachineInstr &MI) {
   }
   return false;
 }
 bool CombinerHelper::matchCombineCopy(MachineInstr &MI) {
   if (MI.getOpcode() != TargetOpcode::COPY)
     return false;
   Register DstReg = MI.getOperand(0).getReg();
   Register SrcReg = MI.getOperand(1).getReg();
-
-  // Give up if either DstReg or SrcReg  is a physical register.
-  if (Register::isPhysicalRegister(DstReg) ||
-      Register::isPhysicalRegister(SrcReg))
-    return false;
-
-  // Give up the types don't match.
-  LLT DstTy = MRI.getType(DstReg);
-  LLT SrcTy = MRI.getType(SrcReg);
-  // Give up if one has a valid LLT, but the other doesn't.
-  if (DstTy.isValid() != SrcTy.isValid())
-    return false;
-  // Give up if the types don't match.
-  if (DstTy.isValid() && SrcTy.isValid() && DstTy != SrcTy)
-    return false;
-
-  // Get the register banks and classes.
-  const RegisterBank *DstBank = MRI.getRegBankOrNull(DstReg);
-  const RegisterBank *SrcBank = MRI.getRegBankOrNull(SrcReg);
-  const TargetRegisterClass *DstRC = MRI.getRegClassOrNull(DstReg);
-  const TargetRegisterClass *SrcRC = MRI.getRegClassOrNull(SrcReg);
-
-  // Replace if the register constraints match.
-  if ((SrcRC == DstRC) && (SrcBank == DstBank))
-    return true;
-  // Replace if DstReg has no constraints.
-  if (!DstBank && !DstRC)
-    return true;
-
-  return false;
+  return canReplaceReg(DstReg, SrcReg, MRI);
 }
 void CombinerHelper::applyCombineCopy(MachineInstr &MI) {
   Register DstReg = MI.getOperand(0).getReg();
   Register SrcReg = MI.getOperand(1).getReg();
   MI.eraseFromParent();
   replaceRegWith(MRI, DstReg, SrcReg);
 }
 

llvm/lib/CodeGen/GlobalISel/Utils.cpp

if (MO.isUse()) {
       int DefIdx = I.getDesc().getOperandConstraint(OpI, MCOI::TIED_TO);
       if (DefIdx != -1 && !I.isRegTiedToUseOperand(DefIdx))
         I.tieOperands(DefIdx, OpI);
     }
   }
   return true;
 }
 
+bool llvm::canReplaceReg(Register DstReg, Register SrcReg,
+                         MachineRegisterInfo &MRI) {
+  // Give up if either DstReg or SrcReg  is a physical register.
+  if (DstReg.isPhysical() || SrcReg.isPhysical())
+    return false;
+  // Give up if the types don't match.
+  if (MRI.getType(DstReg) != MRI.getType(SrcReg))
+    return false;
+  // Replace if either DstReg has no constraints or the register
+  // constraints match.
+  return !MRI.getRegClassOrRegBank(DstReg) ||
+         MRI.getRegClassOrRegBank(DstReg) == MRI.getRegClassOrRegBank(SrcReg);
+}
+
 bool llvm::isTriviallyDead(const MachineInstr &MI,
                            const MachineRegisterInfo &MRI) {
   // If we can move an instruction, we can remove it.  Otherwise, it has
   // a side-effect of some sort.
   bool SawStore = false;
   if (!MI.isSafeToMove(/*AA=*/nullptr, SawStore) && !MI.isPHI())
     return false;
 
   // Instructions without side-effects are dead iff they only define dead vregs.
   for (auto &MO : MI.operands()) {
     if (!MO.isReg() || !MO.isDef())
       continue;
 
     Register Reg = MO.getReg();
     if (Register::isPhysicalRegister(Reg) || !MRI.use_nodbg_empty(Reg))
       return false;
   }
   return true;
 }
 
 void llvm::reportGISelFailure(MachineFunction &MF, const TargetPassConfig &TPC,
                               MachineOptimizationRemarkEmitter &MORE,

llvm/lib/Target/Mips/MipsRegisterBankInfo.cpp

void MipsRegisterBankInfo::setRegBank(MachineInstr &MI,
   }
   default:
     llvm_unreachable("Unexpected opcode.");
   }
 }
 
 static void
 combineAwayG_UNMERGE_VALUES(LegalizationArtifactCombiner &ArtCombiner,
-                            MachineInstr &MI) {
+                            MachineInstr &MI, GISelObserverWrapper &Observer) {
   SmallVector<Register, 4> UpdatedDefs;
   SmallVector<MachineInstr *, 2> DeadInstrs;
-  ArtCombiner.tryCombineMerges(MI, DeadInstrs, UpdatedDefs);
+  ArtCombiner.tryCombineMerges(MI, DeadInstrs, UpdatedDefs, Observer);
   for (MachineInstr *DeadMI : DeadInstrs)
     DeadMI->eraseFromParent();
 }
 
 void MipsRegisterBankInfo::applyMappingImpl(
     const OperandsMapper &OpdMapper) const {
   MachineInstr &MI = OpdMapper.getMI();
   InstListTy NewInstrs;
case TargetOpcode::G_IMPLICIT_DEF: {
     Helper.narrowScalar(MI, 0, LLT::scalar(32));
     // Handle new instructions.
     while (!NewInstrs.empty()) {
       MachineInstr *NewMI = NewInstrs.pop_back_val();
       // This is new G_UNMERGE that was created during narrowScalar and will
       // not be considered for regbank selection. RegBankSelect for mips
       // visits/makes corresponding G_MERGE first. Combine them here.
       if (NewMI->getOpcode() == TargetOpcode::G_UNMERGE_VALUES)
-        combineAwayG_UNMERGE_VALUES(ArtCombiner, *NewMI);
+        combineAwayG_UNMERGE_VALUES(ArtCombiner, *NewMI, WrapperObserver);
       // This G_MERGE will be combined away when its corresponding G_UNMERGE
       // gets regBankSelected.
       else if (NewMI->getOpcode() == TargetOpcode::G_MERGE_VALUES)
         continue;
       else
         // Manually set register banks for def operands to 32 bit gprb.
         setRegBank(*NewMI, MRI);
     }
     return;
   }
   case TargetOpcode::G_UNMERGE_VALUES:
-    combineAwayG_UNMERGE_VALUES(ArtCombiner, MI);
+    combineAwayG_UNMERGE_VALUES(ArtCombiner, MI, WrapperObserver);
     return;
   default:
     break;
   }
 
   return applyDefaultMapping(OpdMapper);
 }

llvm/test/CodeGen/AArch64/GlobalISel/artifact-combine-unmerge.mir

+# NOTE: Assertions have been autogenerated by utils/update_mir_test_checks.py
+# RUN: llc -o - -march=aarch64 -run-pass=legalizer %s | FileCheck %s
+
+# Make sure we don't lose the register bank constraints when
+# artifact combining G_UNMERGE_VALUES instructions.
+---
+name:            test_none_none
+body:             |
+  bb.0.entry:
+    ; CHECK-LABEL: name: test_none_none
+    ; CHECK: [[COPY:%[0-9]+]]:_(s32) = COPY $w0
+    ; CHECK: [[COPY1:%[0-9]+]]:_(s32) = COPY $w1
+    ; CHECK: $w0 = COPY [[COPY]](s32)
+    ; CHECK: $w1 = COPY [[COPY1]](s32)
+    %0:_(s32) = COPY $w0
+    %1:_(s32) = COPY $w1
+    %2:_(s64) = G_MERGE_VALUES %0(s32), %1
+    %3:_(s32), %4:_(s32) = G_UNMERGE_VALUES %2(s64)
+    $w0 = COPY %3(s32)
+    $w1 = COPY %4(s32)
+...
+---
+name:            test_gpr_none
+body:             |
+  bb.0.entry:
+    ; CHECK-LABEL: name: test_gpr_none
+    ; CHECK: [[COPY:%[0-9]+]]:gpr(s32) = COPY $w0
+    ; CHECK: [[COPY1:%[0-9]+]]:gpr(s32) = COPY $w1
+    ; CHECK: $w0 = COPY [[COPY]](s32)
+    ; CHECK: $w1 = COPY [[COPY1]](s32)
+    %0:gpr(s32) = COPY $w0
+    %1:gpr(s32) = COPY $w1
+    %2:_(s64) = G_MERGE_VALUES %0(s32), %1
+    %3:_(s32), %4:_(s32) = G_UNMERGE_VALUES %2(s64)
+    $w0 = COPY %3(s32)
+    $w1 = COPY %4(s32)
+...
+---
+name:            test_none_gpr
+body:             |
+  bb.0.entry:
+    ; CHECK-LABEL: name: test_none_gpr
+    ; CHECK: [[COPY:%[0-9]+]]:_(s32) = COPY $w0
+    ; CHECK: [[COPY1:%[0-9]+]]:_(s32) = COPY $w1
+    ; CHECK: [[COPY2:%[0-9]+]]:gpr(s32) = COPY [[COPY]](s32)
+    ; CHECK: [[COPY3:%[0-9]+]]:gpr(s32) = COPY [[COPY1]](s32)
+    ; CHECK: $w0 = COPY [[COPY2]](s32)
+    ; CHECK: $w1 = COPY [[COPY3]](s32)
+    %0:_(s32) = COPY $w0
+    %1:_(s32) = COPY $w1
+    %2:_(s64) = G_MERGE_VALUES %0(s32), %1
+    %3:gpr(s32), %4:gpr(s32) = G_UNMERGE_VALUES %2(s64)
+    $w0 = COPY %3(s32)
+    $w1 = COPY %4(s32)
+...
+---
+name:            test_fpr_gpr
+body:             |
+  bb.0.entry:
+    ; CHECK-LABEL: name: test_fpr_gpr
+    ; CHECK: [[COPY:%[0-9]+]]:fpr(s32) = COPY $w0
+    ; CHECK: [[COPY1:%[0-9]+]]:fpr(s32) = COPY $w1
+    ; CHECK: [[COPY2:%[0-9]+]]:gpr(s32) = COPY [[COPY]](s32)
+    ; CHECK: [[COPY3:%[0-9]+]]:gpr(s32) = COPY [[COPY1]](s32)
+    ; CHECK: $w0 = COPY [[COPY2]](s32)
+    ; CHECK: $w1 = COPY [[COPY3]](s32)
+    %0:fpr(s32) = COPY $w0
+    %1:fpr(s32) = COPY $w1
+    %2:_(s64) = G_MERGE_VALUES %0(s32), %1
+    %3:gpr(s32), %4:gpr(s32) = G_UNMERGE_VALUES %2(s64)
+    $w0 = COPY %3(s32)
+    $w1 = COPY %4(s32)
+...