GlobalISel: Reimplement moreElementsVectorDst

[arsenm]

Summary

Use pad with undef and unmerge with unused results. This is annoyingly
similar to several other places in LegalizerHelper, but they're all
slightly different.

[paquette]

Maybe I'm missing something obvious here, but why is this preferable to the original implementation?

[arsenm]

In D73940#1857447, @paquette wrote:

Maybe I'm missing something obvious here, but why is this preferable to the original implementation?

merge/unmerge with even sized pieces is nicer to deal with than insert/extract with arbitrary, odd sized pieces. The legalization and artifact combiner for them are also way better developed than the handling for extract and inserts. We currently have multiple different strategies of the more elements/fewer elements. Some of them only handle even breakdowns some awkwardly handle odd cases, and some do the general widening technique like this. I'm trying to consolidate on the one strategy, since it's the most flexible and least likely to break (although all the extra padding instructions and registers seems a bit wasteful in the extreme cases)

[arsenm]

In D73940#1857484, @arsenm wrote:

In D73940#1857447, @paquette wrote:

Maybe I'm missing something obvious here, but why is this preferable to the original implementation?

merge/unmerge with even sized pieces is nicer to deal with than insert/extract with arbitrary, odd sized pieces. The legalization and artifact combiner for them are also way better developed than the handling for extract and inserts. We currently have multiple different strategies of the more elements/fewer elements. Some of them only handle even breakdowns some awkwardly handle odd cases, and some do the general widening technique like this. I'm trying to consolidate on the one strategy, since it's the most flexible and least likely to break (although all the extra padding instructions and registers seems a bit wasteful in the extreme cases)

Also when I posted the original legalizations for most of these, I got comments preferring this way

[arsenm]

Rebase tests

[Petar.Avramovic]

This looks like a good candidate for new LegalizeAction ( MoreElementsLCM or something more appropriate ) that could be preferable more elements option for targets that support G_CONCAT_VECTORS and G_UNMERGE_VALUES for large vector sizes (large enough to hold LCM(WideTy, OrigTy) ).
Current algorithm seems to be designed for targets that prefer not to deal with vector types larger then WideTy. It would be difficult for them to deal with G_CONCAT_VECTORS and G_UNMERGE_VALUES that are not legal and likely hard to combine since they have different small LLTs.

[arsenm]

In D73940#1861817, @Petar.Avramovic wrote:

This looks like a good candidate for new LegalizeAction ( MoreElementsLCM or something more appropriate ) that could be preferable more elements option for targets that support G_CONCAT_VECTORS and G_UNMERGE_VALUES for large vector sizes (large enough to hold LCM(WideTy, OrigTy) ).

I think we should limit the number of legalize actions. Have two separate actions that accomplish the same thing, but one sometimes works or not is a confusing state to be in.

Current algorithm seems to be designed for targets that prefer not to deal with vector types larger then WideTy. It would be difficult for them to deal with G_CONCAT_VECTORS and G_UNMERGE_VALUES that are not legal and likely hard to combine since they have different small LLTs.

I'm not sure what you mean. Do you have an example? The artifact combiner already handles unmerging from a concat_vector with a mixed number of elements

[Petar.Avramovic]

If not a new LegalizeAction maybe some other way ( like one more argument ) for targets to chose whether to create G_EXTRACT or CONCAT_VECTORS + G_UNMERGE_VALUES ?
I am not that familiar with the problem we are dealing here, but shouldn't insert + extract that are created during moreElements combine away like anyext + trunc for widen scalar ?
So this would be extract + insert into implicit def -> copy extract source if it had same type like implicit def (this is 3 instruction combine). Might that fix some of the problems?

llvm/lib/CodeGen/GlobalISel/LegalizerHelper.cpp

1460

nit: there should be one more dead def here

// %0:_(<3 x s32>), %4:_(<3 x s32>), %5:_(<3 x s32>), %6:_(<3 x s32>) = G_UNMERGE_VALUES %3

llvm/test/CodeGen/AMDGPU/GlobalISel/legalize-and.mir

360–361 ↗

(On Diff #242768)

The artifact combiner already handles unmerging from a concat_vector with a mixed number of elements

In some nice cases yes, here however

if (NumDefs % NumMergeRegs != 0)
  return false;

4 % 3 != 0

Anyway this is probably equivalent to <3xs16> G_EXTRACT from first <4xs16> in G_CONCAT_VECTORS since unmerge created 3 more dead defs. That is what we had before this patch. This works because combiner didn't combine artifacts and they are legal.
If combiner was able to combine G_UNMERGE_VALUES + CONCAT_VECTORS it would ruin work done by moreElements. There was some discussion in some patch review that targets should also be able to chose which combines to use like they chose how to legalize. That might be useful here.

[arsenm]

In D73940#1862043, @Petar.Avramovic wrote:

If not a new LegalizeAction maybe some other way ( like one more argument ) for targets to chose whether to create G_EXTRACT or CONCAT_VECTORS + G_UNMERGE_VALUES ?
I am not that familiar with the problem we are dealing here, but shouldn't insert + extract that are created during moreElements combine away like anyext + trunc for widen scalar ?
So this would be extract + insert into implicit def -> copy extract source if it had same type like implicit def (this is 3 instruction combine). Might that fix some of the problems?

I think that this has the same fundamental problem of dealing with mismatched source and result types, while also having more options for irregularity. The advantage of this is how it composes with moreElementsVector on source operands. For sources, there's a bigger advantage from actually performing all operations on the requested type, rather than having a weird leftover piece with a different type with an irregular insert. A def and use changing to the same number of elements, or an common multiple between them, should be the common case which will fold out nicely with the unmarke

In D73940#1862043, @Petar.Avramovic wrote:

If not a new LegalizeAction maybe some other way ( like one more argument ) for targets to chose whether to create G_EXTRACT or CONCAT_VECTORS + G_UNMERGE_VALUES ?

I think this is not a place to add target customization. This is a core decision of how the legalizer deals with vectors. I've pretty much come to the conclusion that G_INSERT/G_EXTRACT are kind of terrible, and the generic legalizer should never produce them. They're too free-form to be really useful. You can't enforce many properties on them in the verifier, and anywhere you would want to do anything with them would require more complicated checks on the operands than the other legalization artifacts. It would generally be simpler to have the common properties implicit in the opcode.

In this particular situation, we should probably have an equivalent of the old ISD::EXTRACT_SUBVECTOR. The expansion for that would look like the code in this patch, creating the unmerge with padding operands. Your custom legalization could then choose to use a different expansion for G_EXTRACT_SUBVECTOR. I think the path forward here is to go ahead with this strategy as a first step. A further cleanup would be to introduce the new artifact, and then move this expansion into the lowering decision for it.

[arsenm]

Rebase and fix comment

[arsenm]

ping

[arsenm]

Fix backwards diff

[arsenm]

ping

[arsenm]

ping

[arsenm]

ping

[arsenm]

Rebase and somehow lost test changes from last diff

[arsenm]

ping

[paquette]

This has been sitting for a while, and I can't see anything wrong with it. I think @arsenm's justification makes sense, so I'm just going to go ahead and give this a LGTM.

@Petar.Avramovic, is that okay with you?

[arsenm]

1782fbbc69482e76eee8af203694bb771a44c921

llvm/include/llvm/CodeGen/GlobalISel/LegalizerHelper.h

public:
   /// Legalize a single operand \p OpIdx of the machine instruction \p MI as a
   /// use by inserting a G_BITCAST to \p CastTy
   void bitcastSrc(MachineInstr &MI, LLT CastTy, unsigned OpIdx);
 
   /// Legalize a single operand \p OpIdx of the machine instruction \p MI as a
   /// def by inserting a G_BITCAST from \p CastTy
   void bitcastDst(MachineInstr &MI, LLT CastTy, unsigned OpIdx);
 
+  /// Widen \p OrigReg to \p WideTy by merging to a wider type, padding with
+  /// G_IMPLICIT_DEF, and producing dead results.
+  Register widenWithUnmerge(LLT WideTy, Register OrigReg);
+
 private:
   LegalizeResult
   widenScalarMergeValues(MachineInstr &MI, unsigned TypeIdx, LLT WideTy);
   LegalizeResult
   widenScalarUnmergeValues(MachineInstr &MI, unsigned TypeIdx, LLT WideTy);
   LegalizeResult
   widenScalarExtract(MachineInstr &MI, unsigned TypeIdx, LLT WideTy);
   LegalizeResult

llvm/lib/CodeGen/GlobalISel/LegalizerHelper.cpp

void LegalizerHelper::narrowScalarDst(MachineInstr &MI, LLT NarrowTy,
   MIRBuilder.setInsertPt(MIRBuilder.getMBB(), ++MIRBuilder.getInsertPt());
   MIRBuilder.buildInstr(ExtOpcode, {MO}, {DstTrunc});
   MO.setReg(DstTrunc);
 }
 
 void LegalizerHelper::moreElementsVectorDst(MachineInstr &MI, LLT WideTy,
                                             unsigned OpIdx) {
   MachineOperand &MO = MI.getOperand(OpIdx);
-  Register DstExt = MRI.createGenericVirtualRegister(WideTy);
   MIRBuilder.setInsertPt(MIRBuilder.getMBB(), ++MIRBuilder.getInsertPt());
-  MIRBuilder.buildExtract(MO, DstExt, 0);
-  MO.setReg(DstExt);
+  MO.setReg(widenWithUnmerge(WideTy, MO.getReg()));
 }
 
 void LegalizerHelper::moreElementsVectorSrc(MachineInstr &MI, LLT MoreTy,
                                             unsigned OpIdx) {
   MachineOperand &MO = MI.getOperand(OpIdx);
 
   LLT OldTy = MRI.getType(MO.getReg());
   unsigned OldElts = OldTy.getNumElements();
if (DstTy.getSizeInBits() == WideDstTy.getSizeInBits()) {
     auto FinalMerge = MIRBuilder.buildMerge(WideDstTy, NewMergeRegs);
     MIRBuilder.buildTrunc(DstReg, FinalMerge.getReg(0));
   }
 
   MI.eraseFromParent();
   return Legalized;
 }
 
+Register LegalizerHelper::widenWithUnmerge(LLT WideTy, Register OrigReg) {
+  Register WideReg = MRI.createGenericVirtualRegister(WideTy);
+  LLT OrigTy = MRI.getType(OrigReg);
+  LLT LCMTy = getLCMType(WideTy, OrigTy);
+
+  const int NumMergeParts = LCMTy.getSizeInBits() / WideTy.getSizeInBits();
+  const int NumUnmergeParts = LCMTy.getSizeInBits() / OrigTy.getSizeInBits();
+
+  Register UnmergeSrc = WideReg;
+
+  // Create a merge to the LCM type, padding with undef
+  // %0:_(<3 x s32>) = G_FOO => <4 x s32>
+  // =>
+  // %1:_(<4 x s32>) = G_FOO
+  // %2:_(<4 x s32>) = G_IMPLICIT_DEF
+  // %3:_(<12 x s32>) = G_CONCAT_VECTORS %1, %2, %2
+  // %0:_(<3 x s32>), %4:_, %5:_, %6:_ = G_UNMERGE_VALUES %3
+  if (NumMergeParts > 1) {
+    Register Undef = MIRBuilder.buildUndef(WideTy).getReg(0);
+    SmallVector<Register, 8> MergeParts(NumMergeParts, Undef);
+    MergeParts[0] = WideReg;
+    UnmergeSrc = MIRBuilder.buildMerge(LCMTy, MergeParts).getReg(0);
+  }
+
+  // Unmerge to the original register and pad with dead defs.
+  SmallVector<Register, 8> UnmergeResults(NumUnmergeParts);
+  UnmergeResults[0] = OrigReg;
+  for (int I = 1; I != NumUnmergeParts; ++I)
+    UnmergeResults[I] = MRI.createGenericVirtualRegister(OrigTy);
+
+  MIRBuilder.buildUnmerge(UnmergeResults, UnmergeSrc);
+  return WideReg;
+}
+
 LegalizerHelper::LegalizeResult
 LegalizerHelper::widenScalarUnmergeValues(MachineInstr &MI, unsigned TypeIdx,
                                           LLT WideTy) {
   if (TypeIdx != 0)
     return UnableToLegalize;
 
   int NumDst = MI.getNumOperands() - 1;
   Register SrcReg = MI.getOperand(NumDst).getReg();