[DAGCombiner] Peek through vector concats when trying to combine shuffles.

[deadalnix]

Summary

This combine showed up as needed when exploring the regression when processing the DAG in topological order.

[deadalnix]

Rebase and ping.

[lebedev.ri]

This is desperately missing some comments explaining what is going on.

[deadalnix]

Add a few comments

[xbolva00]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

16510 ↗

(On Diff #226018)

SDValue Op :

?

16512 ↗

(On Diff #226018)

O is similar to 0.

So ‘Op’?

[deadalnix]

O => Op

[lebedev.ri]

Okay, this seems pretty unusual, but correct.
Would be good for @RKSimon to take a look, but LGTM.

I don't have comments as to the algorithm, but i find
the comments/variable names to be somewhat confusing.
Some 'recommendations':

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

16472–16473 ↗

(On Diff #226092)

... where shuffle operands may be CONCAT_VECTORS.

16478 ↗

(On Diff #226092)

I forget, by now Mask.size() == Vec.getValueType().getVectorNumElements()?

16487 ↗

(On Diff #226092)

This is no longer X offset, this is what was most confusing to me.
I think this needs to be renamed to something else.

16513–16514 ↗

(On Diff #226092)

I think this needs a defensive/explanatory assert that by the end
of the loop ArgOffset is back to the original value of ArgOffset.

[RKSimon]

LGTM - I was thinking that combineX86ShufflesRecursively could handle this but its probably better to get it dealt with before lowering happens.

[deadalnix]

Address some of the comments

[deadalnix]

Alright, this is the first time I have to commit something with the new github process, and I have to admit, I do not know how to do it - or if I can do it at all. Running git llvm push ask me for a username and password, and my old one do not work. What's the next step for me here?

[lebedev.ri]

In D68195#1757811, @deadalnix wrote:

Alright, this is the first time I have to commit something with the new github process, and I have to admit, I do not know how to do it - or if I can do it at all. Running git llvm push ask me for a username and password, and my old one do not work. What's the next step for me here?

Did you ever pushed anything to github before, to any other repository?
Did you clone https://github.com/llvm/llvm-project/ via HTTPS or SSH? (should be former!)
It is likely asking for your github login and password.

You may *really* want to follow https://help.github.com/en/github/authenticating-to-github/creating-a-personal-access-token-for-the-command-line to create credentials with which you can *only* commit, but do nothing else

[deadalnix]

In D68195#1757817, @lebedev.ri wrote:

In D68195#1757811, @deadalnix wrote:

Alright, this is the first time I have to commit something with the new github process, and I have to admit, I do not know how to do it - or if I can do it at all. Running git llvm push ask me for a username and password, and my old one do not work. What's the next step for me here?

Did you ever pushed anything to github before, to any other repository?
Did you clone https://github.com/llvm/llvm-project/ via HTTPS or SSH? (should be former!)
It is likely asking for your github login and password.

You may *really* want to follow https://help.github.com/en/github/authenticating-to-github/creating-a-personal-access-token-for-the-command-line to create credentials with which you can *only* commit, but do nothing else

Hi,

Thanks for helping me out here. So I did commit on LLVM using the pre-github workflow (using git-svn), and did commit to github before in my own projects. I did not yet use the intersection of the two.

Here is what I'm getting when I'm trying to push that patch:

$ git llvm push
`git fetch https://github.com/llvm/llvm-project.git master` printed to stderr:
From https://github.com/llvm/llvm-project
 * branch                    master     -> FETCH_HEAD
Pushing 1 commit:
  0252f080c7c [DAGCombiner] Peek through vector concats when trying to combine shuffles.
Username for 'https://github.com': deadalnix
Password for 'https://[e-mail]':
`git push https://github.com/llvm/llvm-project.git 0252f080c7c01e7493c7d6c9bb9ed8701469c4a8:master` returned 128
remote: Permission to llvm/llvm-project.git denied to deadalnix.
fatal: unable to access 'https://github.com/llvm/llvm-project.git/': The requested URL returned error: 403

I tried to generate a token as suggested, and tried different permission settings for the token, including granting all permission to make sure there wasn't something I was missing, and I always get the same result.

[xbolva00]

I cant find your nick here: https://llvm.org/viewvc/llvm-project/meta/trunk/github-usernames.txt?view=markup .

"If you had commit access to SVN and would like to request commit access to GitHub, please email llvm-admin with your SVN username and GitHub username."

[e-mail]

[lebedev.ri]

In D68195#1757901, @xbolva00 wrote:

I cant find your nick here: https://llvm.org/viewvc/llvm-project/meta/trunk/github-usernames.txt?view=markup .

"If you had commit access to SVN and would like to request commit access to GitHub, please email llvm-admin with your SVN username and GitHub username."

[e-mail]

That indeed would be my next guess

[deadalnix]

That is indeed the step I was missing. Thanks everybody for getting me up to speed.

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

SDValue St1 =
       DAG.getStore(St0, DL, Hi, Ptr,
                    ST->getPointerInfo().getWithOffset(HalfValBitSize / 8),
                    Alignment / 2, MMOFlags, AAInfo);
   return St1;
 }
 
 /// Convert a disguised subvector insertion into a shuffle:
 SDValue DAGCombiner::combineInsertEltToShuffle(SDNode *N, unsigned InsIndex) {
+  assert(N->getOpcode() == ISD::INSERT_VECTOR_ELT &&
+         "Expected extract_vector_elt");
   SDValue InsertVal = N->getOperand(1);
   SDValue Vec = N->getOperand(0);
 
-  // (insert_vector_elt (vector_shuffle X, Y), (extract_vector_elt X, N), InsIndex)
-  //   --> (vector_shuffle X, Y)
+  // (insert_vector_elt (vector_shuffle X, Y), (extract_vector_elt X, N),
+  // InsIndex)
+  //   --> (vector_shuffle X, Y) and variations where shuffle operands may be
+  //   CONCAT_VECTORS.
   if (Vec.getOpcode() == ISD::VECTOR_SHUFFLE && Vec.hasOneUse() &&
       InsertVal.getOpcode() == ISD::EXTRACT_VECTOR_ELT &&
       isa<ConstantSDNode>(InsertVal.getOperand(1))) {
     ShuffleVectorSDNode *SVN = cast<ShuffleVectorSDNode>(Vec.getNode());
     ArrayRef<int> Mask = SVN->getMask();
 
     SDValue X = Vec.getOperand(0);
     SDValue Y = Vec.getOperand(1);
 
     // Vec's operand 0 is using indices from 0 to N-1 and
     // operand 1 from N to 2N - 1, where N is the number of
     // elements in the vectors.
-    int XOffset = -1;
-    if (InsertVal.getOperand(0) == X) {
-      XOffset = 0;
-    } else if (InsertVal.getOperand(0) == Y) {
-      XOffset = X.getValueType().getVectorNumElements();
+    SDValue InsertVal0 = InsertVal.getOperand(0);
+    int ElementOffset = -1;
+
+    // We explore the inputs of the shuffle in order to see if we find the
+    // source of the extract_vector_elt. If so, we can use it to modify the
+    // shuffle rather than perform an insert_vector_elt.
+    SmallVector<std::pair<int, SDValue>, 8> ArgWorkList;
+    ArgWorkList.emplace_back(Mask.size(), Y);
+    ArgWorkList.emplace_back(0, X);
+
+    while (!ArgWorkList.empty()) {
+      int ArgOffset;
+      SDValue ArgVal;
+      std::tie(ArgOffset, ArgVal) = ArgWorkList.pop_back_val();
+
+      if (ArgVal == InsertVal0) {
+        ElementOffset = ArgOffset;
+        break;
+      }
+
+      // Peek through concat_vector.
+      if (ArgVal.getOpcode() == ISD::CONCAT_VECTORS) {
+        int CurrentArgOffset =
+            ArgOffset + ArgVal.getValueType().getVectorNumElements();
+        int Step = ArgVal.getOperand(0).getValueType().getVectorNumElements();
+        for (SDValue Op : reverse(ArgVal->ops())) {
+          CurrentArgOffset -= Step;
+          ArgWorkList.emplace_back(CurrentArgOffset, Op);
+        }
+
+        // Make sure we went through all the elements and did not screw up index
+        // computation.
+        assert(CurrentArgOffset == ArgOffset);
+      }
     }
 
-    if (XOffset != -1) {
+    if (ElementOffset != -1) {
       SmallVector<int, 16> NewMask(Mask.begin(), Mask.end());
 
       auto *ExtrIndex = cast<ConstantSDNode>(InsertVal.getOperand(1));
-      NewMask[InsIndex] = XOffset + ExtrIndex->getZExtValue();
+      NewMask[InsIndex] = ElementOffset + ExtrIndex->getZExtValue();
       assert(NewMask[InsIndex] <
                  (int)(2 * Vec.getValueType().getVectorNumElements()) &&
              NewMask[InsIndex] >= 0 && "NewMask[InsIndex] is out of bound");
 
       SDValue LegalShuffle =
               TLI.buildLegalVectorShuffle(Vec.getValueType(), SDLoc(N), X,
                                           Y, NewMask, DAG);
       if (LegalShuffle)

llvm/test/CodeGen/X86/vector-shuffle-combining.ll

; AVX-NEXT:    retq
   %6 = insertelement <8 x i16> %5, i16 %a4, i32 6
   %7 = insertelement <8 x i16> %6, i16 %b15, i32 7
   ret <8 x i16> %7
 }
 
 define <8 x i16> @shuffle_extract_concat_insert(<4 x i16> %lhsa, <4 x i16> %rhsa, <8 x i16> %b) {
 ; SSE2-LABEL: shuffle_extract_concat_insert:
 ; SSE2:       # %bb.0:
-; SSE2-NEXT:    movd %xmm1, %eax
-; SSE2-NEXT:    pextrw $2, %xmm1, %ecx
-; SSE2-NEXT:    pextrw $5, %xmm2, %edx
-; SSE2-NEXT:    pextrw $7, %xmm2, %esi
-; SSE2-NEXT:    punpcklwd {{.*#+}} xmm0 = xmm0[0],xmm2[0],xmm0[1],xmm2[1],xmm0[2],xmm2[2],xmm0[3],xmm2[3]
-; SSE2-NEXT:    pshufhw {{.*#+}} xmm0 = xmm0[0,1,2,3,4,7,6,7]
+; SSE2-NEXT:    punpcklqdq {{.*#+}} xmm0 = xmm0[0],xmm1[0]
+; SSE2-NEXT:    pshuflw {{.*#+}} xmm0 = xmm0[0,2,2,3,4,5,6,7]
+; SSE2-NEXT:    pshufhw {{.*#+}} xmm0 = xmm0[0,1,2,3,4,6,6,7]
 ; SSE2-NEXT:    pshufd {{.*#+}} xmm0 = xmm0[0,2,2,3]
-; SSE2-NEXT:    pshuflw {{.*#+}} xmm0 = xmm0[2,1,0,3,4,5,6,7]
-; SSE2-NEXT:    pinsrw $4, %ecx, %xmm0
-; SSE2-NEXT:    pinsrw $5, %edx, %xmm0
-; SSE2-NEXT:    pinsrw $6, %eax, %xmm0
-; SSE2-NEXT:    pinsrw $7, %esi, %xmm0
+; SSE2-NEXT:    pshuflw {{.*#+}} xmm0 = xmm0[1,0,3,2,4,5,6,7]
+; SSE2-NEXT:    pshuflw {{.*#+}} xmm1 = xmm2[0,3,2,3,4,5,6,7]
+; SSE2-NEXT:    pshufhw {{.*#+}} xmm1 = xmm1[0,1,2,3,7,5,6,7]
+; SSE2-NEXT:    pshufd {{.*#+}} xmm1 = xmm1[0,2,2,3]
+; SSE2-NEXT:    pshuflw {{.*#+}} xmm1 = xmm1[0,1,3,2,4,5,6,7]
+; SSE2-NEXT:    punpcklwd {{.*#+}} xmm0 = xmm0[0],xmm1[0],xmm0[1],xmm1[1],xmm0[2],xmm1[2],xmm0[3],xmm1[3]
 ; SSE2-NEXT:    retq
 ;
 ; SSSE3-LABEL: shuffle_extract_concat_insert:
 ; SSSE3:       # %bb.0:
-; SSSE3-NEXT:    pextrw $2, %xmm1, %eax
-; SSSE3-NEXT:    pextrw $5, %xmm2, %ecx
-; SSSE3-NEXT:    pextrw $7, %xmm2, %edx
-; SSSE3-NEXT:    movd %xmm1, %esi
+; SSSE3-NEXT:    punpcklqdq {{.*#+}} xmm0 = xmm0[0],xmm1[0]
+; SSSE3-NEXT:    pshufb {{.*#+}} xmm0 = xmm0[4,5,0,1,12,13,8,9,8,9,12,13,12,13,14,15]
+; SSSE3-NEXT:    pshufb {{.*#+}} xmm2 = xmm2[0,1,6,7,10,11,14,15,14,15,10,11,12,13,14,15]
 ; SSSE3-NEXT:    punpcklwd {{.*#+}} xmm0 = xmm0[0],xmm2[0],xmm0[1],xmm2[1],xmm0[2],xmm2[2],xmm0[3],xmm2[3]
-; SSSE3-NEXT:    pshufb {{.*#+}} xmm0 = xmm0[8,9,2,3,0,1,14,15,8,9,14,15,12,13,14,15]
-; SSSE3-NEXT:    pinsrw $4, %eax, %xmm0
-; SSSE3-NEXT:    pinsrw $5, %ecx, %xmm0
-; SSSE3-NEXT:    pinsrw $6, %esi, %xmm0
-; SSSE3-NEXT:    pinsrw $7, %edx, %xmm0
 ; SSSE3-NEXT:    retq
 ;
 ; SSE41-LABEL: shuffle_extract_concat_insert:
 ; SSE41:       # %bb.0:
-; SSE41-NEXT:    movd %xmm1, %eax
-; SSE41-NEXT:    pextrw $2, %xmm1, %ecx
+; SSE41-NEXT:    punpcklqdq {{.*#+}} xmm0 = xmm0[0],xmm1[0]
+; SSE41-NEXT:    pshufb {{.*#+}} xmm0 = xmm0[4,5,0,1,12,13,8,9,8,9,12,13,12,13,14,15]
+; SSE41-NEXT:    pshufb {{.*#+}} xmm2 = xmm2[0,1,6,7,10,11,14,15,14,15,10,11,12,13,14,15]
 ; SSE41-NEXT:    punpcklwd {{.*#+}} xmm0 = xmm0[0],xmm2[0],xmm0[1],xmm2[1],xmm0[2],xmm2[2],xmm0[3],xmm2[3]
-; SSE41-NEXT:    pshufb {{.*#+}} xmm0 = xmm0[8,9,2,3,0,1,14,15,8,9,14,15,12,13,14,15]
-; SSE41-NEXT:    pinsrw $4, %ecx, %xmm0
-; SSE41-NEXT:    pblendw {{.*#+}} xmm0 = xmm0[0,1,2,3,4],xmm2[5],xmm0[6,7]
-; SSE41-NEXT:    pinsrw $6, %eax, %xmm0
-; SSE41-NEXT:    pblendw {{.*#+}} xmm0 = xmm0[0,1,2,3,4,5,6],xmm2[7]
 ; SSE41-NEXT:    retq
 ;
 ; AVX-LABEL: shuffle_extract_concat_insert:
 ; AVX:       # %bb.0:
-; AVX-NEXT:    vmovd %xmm1, %eax
-; AVX-NEXT:    vpextrw $2, %xmm1, %ecx
-; AVX-NEXT:    vpunpcklwd {{.*#+}} xmm0 = xmm0[0],xmm2[0],xmm0[1],xmm2[1],xmm0[2],xmm2[2],xmm0[3],xmm2[3]
-; AVX-NEXT:    vpshufb {{.*#+}} xmm0 = xmm0[8,9,2,3,0,1,14,15,8,9,14,15,12,13,14,15]
-; AVX-NEXT:    vpinsrw $4, %ecx, %xmm0, %xmm0
-; AVX-NEXT:    vpblendw {{.*#+}} xmm0 = xmm0[0,1,2,3,4],xmm2[5],xmm0[6,7]
-; AVX-NEXT:    vpinsrw $6, %eax, %xmm0, %xmm0
-; AVX-NEXT:    vpblendw {{.*#+}} xmm0 = xmm0[0,1,2,3,4,5,6],xmm2[7]
+; AVX-NEXT:    vpunpcklqdq {{.*#+}} xmm0 = xmm0[0],xmm1[0]
+; AVX-NEXT:    vpshufb {{.*#+}} xmm0 = xmm0[4,5,0,1,12,13,8,9,8,9,12,13,12,13,14,15]
+; AVX-NEXT:    vpshufb {{.*#+}} xmm1 = xmm2[0,1,6,7,10,11,14,15,14,15,10,11,12,13,14,15]
+; AVX-NEXT:    vpunpcklwd {{.*#+}} xmm0 = xmm0[0],xmm1[0],xmm0[1],xmm1[1],xmm0[2],xmm1[2],xmm0[3],xmm1[3]
 ; AVX-NEXT:    retq
   %a = shufflevector <4 x i16> %lhsa, <4 x i16> %rhsa, <8 x i32> <i32 0, i32 1, i32 2, i32 3, i32 4, i32 5, i32 6, i32 7>
   %a0 = extractelement <8 x i16> %a, i32 0
   %a4 = extractelement <8 x i16> %a, i32 4
   %a6 = extractelement <8 x i16> %a, i32 6
   %b11 = extractelement <8 x i16> %b, i32 3
   %b13 = extractelement <8 x i16> %b, i32 5
   %b15 = extractelement <8 x i16> %b, i32 7