[DAGCombine] RFC: Recognise any_extend_vector_inreg and truncation style shuffle masks

[RKSimon]

Summary

During legalization we are often creating shuffles (via a build_vector scalarization stage) that are "any_extend_vector_inreg" style masks, and also other masks that are the equivalent of "truncate_vector_inreg" (if we had such a thing).

This RFC is an attempt to match these cases to help undo the effects of just leaving shuffle lowering to handle it - which typically means we lose track of the undefined elements of the shuffles resulting in an unnecessary extension+truncation stage for widened illegal types.

The 2011-10-21-widen-cmp.ll regression can be fixed by making SIGN_EXTEND_VECTOR_IN_REG legal in SSE instead of lowering them to X86ISD::VSEXT (PR31712). An alternative could be to improve target-specific DemandedElts handling at the DAG level (not a small amount of work....).

The regressions encountered in D28537 would be fixed by this.

[RKSimon]

Ping? Any comments?

[delena]

You can, probably, add more test cases for extension of <8 x i8> to <8 x i16>. You work with illegal types, right?

[RKSimon]

In D29454#670646, @delena wrote:

You can, probably, add more test cases for extension of <8 x i8> to <8 x i16>. You work with illegal types, right?

These are proving very tricky to match in any testable way - the difference being that integer types get promoted while float types get widened. Only widening results in the truncate_vector_inreg(*_extend_vector_inreg()) patterns, It IS possible for promotions to generate something like truncate_vector_inreg(BINOP(*_extend_vector_inreg(), *_extend_vector_inreg())) which could be matched in a later patch?

[delena]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

14268 ↗

(On Diff #86812)

I don't understand why do you need this check.
You check Mask in IsTruncate(), it should be enough.

14276 ↗

(On Diff #86812)

I'd check at the beginning, before IsTruncate().
if (N00.getValueType().getSizeInBits() != VT.getSizeInBits())

return SDValue();

[RKSimon]

Addressed Elena's comments.

[delena]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

14243 ↗

(On Diff #88723)

This check can be removed.

14245 ↗

(On Diff #88723)

lower case function name: isAnyExtend

14250 ↗

(On Diff #88723)

Is !LegalOperations important?

[RKSimon]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

14245 ↗

(On Diff #88723)

Ah - missed that thanks - we're not very consistent when it comes to these.....

14250 ↗

(On Diff #88723)

For these cases yes - currently ISD::ANY_EXTEND_VECTOR_INREG isn't supported by any targets as a legal/custom operation but should be soon.

[RKSimon]

Removed check - was just there as an 'early out' check but was getting in the way.

[delena]

LGTM, after changing function names to lower case.

llvm/trunk/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

SDValue DAGCombiner::visitSIGN_EXTEND_INREG(SDNode *N) {
   // if x is small enough.
   if (N0.getOpcode() == ISD::SIGN_EXTEND || N0.getOpcode() == ISD::ANY_EXTEND) {
     SDValue N00 = N0.getOperand(0);
     if (N00.getScalarValueSizeInBits() <= EVTBits &&
         (!LegalOperations || TLI.isOperationLegal(ISD::SIGN_EXTEND, VT)))
       return DAG.getNode(ISD::SIGN_EXTEND, SDLoc(N), VT, N00, N1);
   }
 
+  // fold (sext_in_reg (*_extend_vector_inreg x)) -> (sext_vector_in_reg x)
+  if ((N0.getOpcode() == ISD::ANY_EXTEND_VECTOR_INREG ||
+       N0.getOpcode() == ISD::SIGN_EXTEND_VECTOR_INREG ||
+       N0.getOpcode() == ISD::ZERO_EXTEND_VECTOR_INREG) &&
+      N0.getOperand(0).getScalarValueSizeInBits() == EVTBits) {
+    if (!LegalOperations ||
+        TLI.isOperationLegal(ISD::SIGN_EXTEND_VECTOR_INREG, VT))
+      return DAG.getSignExtendVectorInReg(N0.getOperand(0), SDLoc(N), VT);
+  }
+
   // fold (sext_in_reg (zext x)) -> (sext x)
   // iff we are extending the source sign bit.
   if (N0.getOpcode() == ISD::ZERO_EXTEND) {
     SDValue N00 = N0.getOperand(0);
     if (N00.getScalarValueSizeInBits() == EVTBits &&
         (!LegalOperations || TLI.isOperationLegal(ISD::SIGN_EXTEND, VT)))
       return DAG.getNode(ISD::SIGN_EXTEND, SDLoc(N), VT, N00, N1);
   }
static SDValue combineShuffleOfScalars(ShuffleVectorSDNode *SVN,
   if (SVT != VT.getScalarType())
     for (SDValue &Op : Ops)
       Op = TLI.isZExtFree(Op.getValueType(), SVT)
                ? DAG.getZExtOrTrunc(Op, SDLoc(SVN), SVT)
                : DAG.getSExtOrTrunc(Op, SDLoc(SVN), SVT);
   return DAG.getBuildVector(VT, SDLoc(SVN), Ops);
 }
 
+// Match shuffles that can be converted to any_vector_extend_in_reg.
+// This is often generated during legalization.
+// e.g. v4i32 <0,u,1,u> -> (v2i64 any_vector_extend_in_reg(v4i32 src))
+// TODO Add support for ZERO_EXTEND_VECTOR_INREG when we have a test case.
+SDValue combineShuffleToVectorExtend(ShuffleVectorSDNode *SVN,
+                                     SelectionDAG &DAG,
+                                     const TargetLowering &TLI,
+                                     bool LegalOperations) {
+  EVT VT = SVN->getValueType(0);
+  bool IsBigEndian = DAG.getDataLayout().isBigEndian();
+
+  // TODO Add support for big-endian when we have a test case.
+  if (!VT.isInteger() || IsBigEndian)
+    return SDValue();
+
+  unsigned NumElts = VT.getVectorNumElements();
+  unsigned EltSizeInBits = VT.getScalarSizeInBits();
+  ArrayRef<int> Mask = SVN->getMask();
+  SDValue N0 = SVN->getOperand(0);
+
+  // shuffle<0,-1,1,-1> == (v2i64 anyextend_vector_inreg(v4i32))
+  auto isAnyExtend = [&Mask, &NumElts](unsigned Scale) {
+    for (unsigned i = 0; i != NumElts; ++i) {
+      if (Mask[i] < 0)
+        continue;
+      if ((i % Scale) == 0 && Mask[i] == (i / Scale))
+        continue;
+      return false;
+    }
+    return true;
+  };
+
+  // Attempt to match a '*_extend_vector_inreg' shuffle, we just search for
+  // power-of-2 extensions as they are the most likely.
+  for (unsigned Scale = 2; Scale < NumElts; Scale *= 2) {
+    if (!isAnyExtend(Scale))
+      continue;
+
+    EVT OutSVT = EVT::getIntegerVT(*DAG.getContext(), EltSizeInBits * Scale);
+    EVT OutVT = EVT::getVectorVT(*DAG.getContext(), OutSVT, NumElts / Scale);
+    if (!LegalOperations ||
+        TLI.isOperationLegalOrCustom(ISD::ANY_EXTEND_VECTOR_INREG, OutVT))
+      return DAG.getBitcast(VT,
+                            DAG.getAnyExtendVectorInReg(N0, SDLoc(SVN), OutVT));
+  }
+
+  return SDValue();
+}
+
+// Detect 'truncate_vector_inreg' style shuffles that pack the lower parts of
+// each source element of a large type into the lowest elements of a smaller
+// destination type. This is often generated during legalization.
+// If the source node itself was a '*_extend_vector_inreg' node then we should
+// then be able to remove it.
+SDValue combineTruncationShuffle(ShuffleVectorSDNode *SVN, SelectionDAG &DAG) {
+  EVT VT = SVN->getValueType(0);
+  bool IsBigEndian = DAG.getDataLayout().isBigEndian();
+
+  // TODO Add support for big-endian when we have a test case.
+  if (!VT.isInteger() || IsBigEndian)
+    return SDValue();
+
+  SDValue N0 = SVN->getOperand(0);
+  while (N0.getOpcode() == ISD::BITCAST)
+    N0 = N0.getOperand(0);
+
+  unsigned Opcode = N0.getOpcode();
+  if (Opcode != ISD::ANY_EXTEND_VECTOR_INREG &&
+      Opcode != ISD::SIGN_EXTEND_VECTOR_INREG &&
+      Opcode != ISD::ZERO_EXTEND_VECTOR_INREG)
+    return SDValue();
+
+  SDValue N00 = N0.getOperand(0);
+  ArrayRef<int> Mask = SVN->getMask();
+  unsigned NumElts = VT.getVectorNumElements();
+  unsigned EltSizeInBits = VT.getScalarSizeInBits();
+  unsigned ExtSrcSizeInBits = N00.getScalarValueSizeInBits();
+
+  // (v4i32 truncate_vector_inreg(v2i64)) == shuffle<0,2-1,-1>
+  // (v8i16 truncate_vector_inreg(v4i32)) == shuffle<0,2,4,6,-1,-1,-1,-1>
+  // (v8i16 truncate_vector_inreg(v2i64)) == shuffle<0,4,-1,-1,-1,-1,-1,-1>
+  auto isTruncate = [&Mask, &NumElts](unsigned Scale) {
+    for (unsigned i = 0; i != NumElts; ++i) {
+      if (Mask[i] < 0)
+        continue;
+      if ((i * Scale) < NumElts && Mask[i] == (i * Scale))
+        continue;
+      return false;
+    }
+    return true;
+  };
+
+  // At the moment we just handle the case where we've truncated back to the
+  // same size as before the extension.
+  // TODO: handle more extension/truncation cases as cases arise.
+  if (EltSizeInBits != ExtSrcSizeInBits)
+    return SDValue();
+
+  // Attempt to match a 'truncate_vector_inreg' shuffle, we just search for
+  // power-of-2 truncations as they are the most likely.
+  for (unsigned Scale = 2; Scale < NumElts; Scale *= 2)
+    if (isTruncate(Scale))
+      return DAG.getBitcast(VT, N00);
+
+  return SDValue();
+}
+
 SDValue DAGCombiner::visitVECTOR_SHUFFLE(SDNode *N) {
   EVT VT = N->getValueType(0);
   unsigned NumElts = VT.getVectorNumElements();
 
   SDValue N0 = N->getOperand(0);
   SDValue N1 = N->getOperand(1);
 
   assert(N0.getValueType() == VT && "Vector shuffle must be normalized in DAG");
SDValue DAGCombiner::visitVECTOR_SHUFFLE(SDNode *N) {
   }
 
   // There are various patterns used to build up a vector from smaller vectors,
   // subvectors, or elements. Scan chains of these and replace unused insertions
   // or components with undef.
   if (SDValue S = simplifyShuffleOperands(SVN, N0, N1, DAG))
     return S;
 
+  // Match shuffles that can be converted to any_vector_extend_in_reg.
+  if (SDValue V = combineShuffleToVectorExtend(SVN, DAG, TLI, LegalOperations))
+    return V;
+
+  // Combine "truncate_vector_in_reg" style shuffles.
+  if (SDValue V = combineTruncationShuffle(SVN, DAG))
+    return V;
+
   if (N0.getOpcode() == ISD::CONCAT_VECTORS &&
       Level < AfterLegalizeVectorOps &&
       (N1.isUndef() ||
       (N1.getOpcode() == ISD::CONCAT_VECTORS &&
        N0.getOperand(0).getValueType() == N1.getOperand(0).getValueType()))) {
     if (SDValue V = partitionShuffleOfConcats(N, DAG))
       return V;
   }

llvm/trunk/test/CodeGen/X86/2011-10-21-widen-cmp.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc < %s -mtriple=x86_64-unknown-linux-gnu -mcpu=corei7 | FileCheck %s
 
 ; Check that a <4 x float> compare is generated and that we are
 ; not stuck in an endless loop.
 
 define void @cmp_2_floats(<2 x float> %a, <2 x float> %b) {
 ; CHECK-LABEL: cmp_2_floats:
 ; CHECK:       # BB#0: # %entry
 ; CHECK-NEXT:    movaps %xmm0, %xmm2
 ; CHECK-NEXT:    cmpordps %xmm0, %xmm0
-; CHECK-NEXT:    insertps {{.*#+}} xmm0 = xmm0[0,1],zero,xmm0[1]
+; CHECK-NEXT:    pmovsxdq %xmm0, %xmm0
+; CHECK-NEXT:    pshufd {{.*#+}} xmm0 = xmm0[0,2,2,3]
 ; CHECK-NEXT:    pslld $31, %xmm0
 ; CHECK-NEXT:    blendvps %xmm0, %xmm2, %xmm1
 ; CHECK-NEXT:    movlps %xmm1, (%rax)
 ; CHECK-NEXT:    retq
 entry:
   %0 = fcmp oeq <2 x float> undef, undef
   %1 = select <2 x i1> %0, <2 x float> %a, <2 x float> %b
   store <2 x float> %1, <2 x float>* undef

llvm/trunk/test/CodeGen/X86/avx512-cvt.ll

; VLNODQ-NEXT:    retq
   ret <4 x double> %1
 }
 
 define <2 x float> @sitofp_2i1_float(<2 x float> %a) {
 ; NOVL-LABEL: sitofp_2i1_float:
 ; NOVL:       ## BB#0:
 ; NOVL-NEXT:    vxorps %xmm1, %xmm1, %xmm1
 ; NOVL-NEXT:    vcmpltps %xmm0, %xmm1, %xmm0
-; NOVL-NEXT:    vinsertps {{.*#+}} xmm0 = xmm0[0,1],zero,xmm0[1]
 ; NOVL-NEXT:    vcvtdq2ps %xmm0, %xmm0
 ; NOVL-NEXT:    retq
 ;
 ; VLDQ-LABEL: sitofp_2i1_float:
 ; VLDQ:       ## BB#0:
 ; VLDQ-NEXT:    vxorps %xmm1, %xmm1, %xmm1
 ; VLDQ-NEXT:    vcmpltps %xmm0, %xmm1, %k0
 ; VLDQ-NEXT:    vpmovm2d %k0, %xmm0

llvm/trunk/test/CodeGen/X86/avx512-vec-cmp.ll

; SKX-NEXT:    retq
   %1 = zext <2 x i1> %mask to <2 x i64>
   ret <2 x i64> %1
 }
 
 define <2 x i64> @test46(<2 x float> %x, <2 x float> %y) #0 {
 ; KNL-LABEL: test46:
 ; KNL:       ## BB#0:
 ; KNL-NEXT:    vcmpeqps %xmm1, %xmm0, %xmm0
-; KNL-NEXT:    vxorps %xmm1, %xmm1, %xmm1
-; KNL-NEXT:    vunpcklps {{.*#+}} xmm0 = xmm1[0],xmm0[0],xmm1[1],xmm0[1]
-; KNL-NEXT:    vpsrad $31, %xmm0, %xmm1
-; KNL-NEXT:    vmovshdup {{.*#+}} xmm0 = xmm0[1,1,3,3]
-; KNL-NEXT:    vpblendd {{.*#+}} xmm0 = xmm0[0],xmm1[1],xmm0[2],xmm1[3]
+; KNL-NEXT:    vpmovsxdq %xmm0, %xmm0
 ; KNL-NEXT:    vpand {{.*}}(%rip), %xmm0, %xmm0
 ; KNL-NEXT:    retq
 ;
 ; SKX-LABEL: test46:
 ; SKX:       ## BB#0:
 ; SKX-NEXT:    vcmpeqps %xmm1, %xmm0, %k1
 ; SKX-NEXT:    vmovdqa64 {{.*}}(%rip), %xmm0 {%k1} {z}
 ; SKX-NEXT:    retq
   %mask = fcmp oeq <2 x float> %x, %y
   %1 = zext <2 x i1> %mask to <2 x i64>
   ret <2 x i64> %1
 }

llvm/trunk/test/CodeGen/X86/sse-minmax.ll

 }
 
 define <2 x float> @test_maxps_illegal_v2f32(<2 x float> %x, <2 x float> %y)  {
 ; STRICT-LABEL: test_maxps_illegal_v2f32:
 ; STRICT:       # BB#0:
 ; STRICT-NEXT:    movaps %xmm0, %xmm2
 ; STRICT-NEXT:    movaps %xmm1, %xmm0
 ; STRICT-NEXT:    cmpleps %xmm2, %xmm0
-; STRICT-NEXT:    insertps {{.*#+}} xmm0 = xmm0[0,1],zero,xmm0[1]
-; STRICT-NEXT:    pslld $31, %xmm0
 ; STRICT-NEXT:    blendvps %xmm0, %xmm2, %xmm1
 ; STRICT-NEXT:    movaps %xmm1, %xmm0
 ; STRICT-NEXT:    retq
 ;
 ; RELAX-LABEL: test_maxps_illegal_v2f32:
 ; RELAX:       # BB#0:
 ; RELAX-NEXT:    maxps %xmm1, %xmm0
 ; RELAX-NEXT:    retq
   %max_is_x = fcmp oge <2 x float> %x, %y
   %max = select <2 x i1> %max_is_x, <2 x float> %x, <2 x float> %y
   ret <2 x float> %max
 }
 
 define <2 x float> @test_minps_illegal_v2f32(<2 x float> %x, <2 x float> %y)  {
 ; STRICT-LABEL: test_minps_illegal_v2f32:
 ; STRICT:       # BB#0:
 ; STRICT-NEXT:    movaps %xmm0, %xmm2
 ; STRICT-NEXT:    cmpleps %xmm1, %xmm0
-; STRICT-NEXT:    insertps {{.*#+}} xmm0 = xmm0[0,1],zero,xmm0[1]
-; STRICT-NEXT:    pslld $31, %xmm0
 ; STRICT-NEXT:    blendvps %xmm0, %xmm2, %xmm1
 ; STRICT-NEXT:    movaps %xmm1, %xmm0
 ; STRICT-NEXT:    retq
 ;
 ; RELAX-LABEL: test_minps_illegal_v2f32:
 ; RELAX:       # BB#0:
 ; RELAX-NEXT:    minps %xmm1, %xmm0
 ; RELAX-NEXT:    retq