[DAG] Fold shuffle(bop(shuffle(x,y),shuffle(z,w)),bop(shuffle(a,b),shuffle(c,d)))

[RKSimon]

Summary

Attempt to fold from a shuffle of a pair of binops to a binop of shuffles, as long as one/both of the binop sources are also shuffles that can be merged with the outer shuffle. This should guarantee that we remove one binop without introducing any additional shuffles.

Technically there's potential for a merged shuffle's lowering to be poorer than the original shuffle, but it could also be better, and I'm not seeing any regressions as long as we keep the 'don't merge splats' rule already present in MergeInnerShuffle.

This expands and generalizes an existing X86 combine and attempts to merge either of each binop's sources (with an on-the-fly commutation of the shuffle mask) - we couldn't do that in the x86 version as it had to stay in a form that DAGCombine's MergeInnerShuffle would still recognise.

[RKSimon]

ping?

[pengfei]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

20981

Will the merge break some thing like expection handling? E.g. Under strict FP model, we should make sure no unexpected expections raised by the masked elements.

20983

Can we use a variable to save N->getOperand(0/1)? They are used many times later.

20984

Should it be isCommutativeBinOp for Op10 and Op11?

21002–21005

Can we use a lambda expression to save the repeated code?

21007

How about both Op00 and Op10 are VECTOR_SHUFFLE? Do we miss the chance for Op10?

[RKSimon]

Reuse existing getOperand() variables.

Explicitly check that the binop source operands are the same type as the shuffle results.

[RKSimon]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

20981

We're pushing the shuffle(binop(x,y),binop(z,w)) -> binop(shuffle(x,y),shuffle(z,w)) - so we shouldn't be calling binop on any vector element that it wasn't already. The only danger is if the outer shuffle mask will introduce any undefined elements that the binop can't handle. I'll add a check that ensures we don't merge to a shuffle mask that introduces undefined elements.

21007

We don't change LHS/RHS ordering of any binop elements so we should be OK.

[RKSimon]

Don't merge shuffles if it would introduce any undefined elements

[pengfei]

I didn't verify the generated binary, but the math LGTM.

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

21072

It seems all BinOps have the same VT between inputs and output. Nevertheless, I think we could still be able to do the merge even if they have different VTs.

21083

Nit, can we use a lambda expression like below to simplify the 4 checks

auto canMergeInnerShuffle = [&](bool LeftOp, bool Commute) {
  SDValue Op0 = LeftOp ? Op00 : Op01;
  SDValue Op1 = LeftOp ? Op10 : Op11;
  SDValue &SV0 = LeftOp ? LeftSV0 : RightSV0;
  SDValue &SV1 = LeftOp ? LeftSV1 : RightSV1;
  SmallVector<int, 4> &Mask = LeftOp ? LeftMask : RightMask;
  if (Commute)
    std::swap(Op0, Op1);
  return Op0.getOpcode() == ISD::VECTOR_SHUFFLE &&
         N0->isOnlyUserOf(Op0.getNode()) &&
         MergeInnerShuffle(Commute, SVN, cast<ShuffleVectorSDNode>(Op0), Op1,
                           TLI, SV0, SV1, Mask) &&
         llvm::none_of(Mask, [](int M) { return M < 0; });
};
if (canMergeInnerShuffle(true, false) || canMergeInnerShuffle(true, true)) {
  LeftMerged = true;
} else {
  LeftMask.assign(SVN->getMask().begin(), SVN->getMask().end());
  LeftSV0 = Op00, LeftSV1 = Op10;
}
...

[saugustine]

Unfortunately, this commit causes a segfault with the test case below. I'm intend to revert it shortly.

typedef long b __attribute__((__vector_size__(16)));
b *d;
b e;
b __attribute__((__always_inline__)) c(b h, b i) {
  return (__attribute__((__vector_size__(8 * sizeof(short)))) short)h + i;
}
j() {
  b k, l, m, n, o[6], p, q;
  m = d[5];
  b r = m;
  b s = f(r, 8);
  q = s;
  l = d[1];
  p = l;
  t(q);
  n = c(m, l);
  o[1] = c(s, f(p, 8));
  k = __builtin_shufflevector(n, o[1], 0, 2);
  e = __builtin_ia32_psrlwi128(k, j);
}

./bin/clang -cc1 -triple x86_64-grtev4-linux-gnu -emit-obj -O1 -std=c99 test.c

PLEASE submit a bug report to https://bugs.llvm.org/ and include the crash backtrace, preprocessed source, and associated run script.
Stack dump:
0. Program arguments: ./bin/clang -cc1 -triple x86_64-grtev4-linux-gnu -emit-obj -O1 -std=c99 /usr/local/google/home/saugustine/tmp/test.c

1. <eof> parser at end of file
2. Code generation
3. Running pass 'Function Pass Manager' on module '.../tmp/test.c'.
4. Running pass 'X86 DAG->DAG Instruction Selection' on function '@j' #0 0x00000000048d250a llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) .../llvm-new/llvm-project/llvm/lib/Support/Unix/Signals.inc:565:11 #1 0x00000000048d26db PrintStackTraceSignalHandler(void*) .../llvm-new/llvm-project/llvm/lib/Support/Unix/Signals.inc:632:1 #2 0x00000000048d0ccb llvm::sys::RunSignalHandlers() .../llvm-new/llvm-project/llvm/lib/Support/Signals.cpp:70:5 #3 0x00000000048d2e51 SignalHandler(int) .../llvm-new/llvm-project/llvm/lib/Support/Unix/Signals.inc:407:1 #4 0x00007f522cedf140 __restore_rt (/lib/x86_64-linux-gnu/libpthread.so.0+0x14140) #5 0x0000000001592ec8 llvm::SDNode::getValueType(unsigned int) const .../llvm-new/llvm-project/llvm/include/llvm/CodeGen/SelectionDAGNodes.h:959:5 #6 0x00000000015930ab llvm::SDValue::getValueType() const .../llvm-new/llvm-project/llvm/include/llvm/CodeGen/SelectionDAGNodes.h:1114:16 #7 0x0000000005fe59a6 llvm::SelectionDAG::getVectorShuffle(llvm::EVT, llvm::SDLoc const&, llvm::SDValue, llvm::SDValue, llvm::ArrayRef<int>) .../llvm-new/llvm-project/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp:1731:3 #8 0x0000000005e9e6c6 (anonymous namespace)::DAGCombiner::visitVECTOR_SHUFFLE(llvm::SDNode*) .../llvm-new/llvm-project/llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp:21125:19 #9 0x0000000005e4d240 (anonymous namespace)::DAGCombiner::visit(llvm::SDNode*) .../llvm-new/llvm-project/llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp:1716:40

#10 0x0000000005e4c298 (anonymous namespace)::DAGCombiner::combine(llvm::SDNode*) .../llvm-new/llvm-project/llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp:1747:10
#11 0x0000000005e4b880 (anonymous namespace)::DAGCombiner::Run(llvm::CombineLevel) .../llvm-new/llvm-project/llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp:1555:18
#12 0x0000000005e4b14f llvm::SelectionDAG::Combine(llvm::CombineLevel, llvm::AAResults*, llvm::CodeGenOpt::Level) .../llvm-new/llvm-project/llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp:22906:3
#13 0x000000000604f24e llvm::SelectionDAGISel::CodeGenAndEmitDAG() .../llvm-new/llvm-project/llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp:795:3
#14 0x000000000604edcf llvm::SelectionDAGISel::SelectBasicBlock(llvm::ilist_iterator<llvm::ilist_detail::node_options<llvm::Instruction, false, false, void>, false, true>, llvm::ilist_iterator<llvm::ilist_detail::node_options<llvm::Instruction, false, false, void>, false, true>, bool&) .../llvm-new/llvm-project/llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp:711:1
#15 0x000000000604e832 llvm::SelectionDAGISel::SelectAllBasicBlocks(llvm::Function const&) .../llvm-new/llvm-project/llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp:0:7
#16 0x000000000604bb9f llvm::SelectionDAGISel::runOnMachineFunction(llvm::MachineFunction&) .../llvm-new/llvm-project/llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp:505:3
#17 0x0000000002bc4ae1 (anonymous namespace)::X86DAGToDAGISel::runOnMachineFunction(llvm::MachineFunction&) .../llvm-new/llvm-project/llvm/lib/Target/X86/X86ISelDAGToDAG.cpp:193:7
#18 0x0000000003676747 llvm::MachineFunctionPass::runOnFunction(llvm::Function&) .../llvm-new/llvm-project/llvm/lib/CodeGen/MachineFunctionPass.cpp:72:8
#19 0x0000000003cec2fc llvm::FPPassManager::runOnFunction(llvm::Function&) .../llvm-new/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:1434:23
#20 0x0000000003cf1475 llvm::FPPassManager::runOnModule(llvm::Module&) .../llvm-new/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:1480:16
#21 0x0000000003ceccc4 (anonymous namespace)::MPPassManager::runOnModule(llvm::Module&) .../llvm-new/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:1549:23
#22 0x0000000003cec7e8 llvm::legacy::PassManagerImpl::run(llvm::Module&) .../llvm-new/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:540:16
#23 0x0000000003cf1781 llvm::legacy::PassManager::run(llvm::Module&) .../llvm-new/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:1676:3
#24 0x0000000004cf67b5 (anonymous namespace)::EmitAssemblyHelper::EmitAssemblyWithNewPassManager(clang::BackendAction, std::unique_ptr<llvm::raw_pwrite_stream, std::default_delete<llvm::raw_pwrite_stream> >) .../llvm-new/llvm-project/clang/lib/CodeGen/BackendUtil.cpp:1439:3
#25 0x0000000004cf3f07 clang::EmitBackendOutput(clang::DiagnosticsEngine&, clang::HeaderSearchOptions const&, clang::CodeGenOptions const&, clang::TargetOptions const&, clang::LangOptions const&, llvm::DataLayout const&, llvm::Module*, clang::BackendAction, std::unique_ptr<llvm::raw_pwrite_stream, std::default_delete<llvm::raw_pwrite_stream> >) .../llvm-new/llvm-project/clang/lib/CodeGen/BackendUtil.cpp:1601:5
#26 0x00000000061acec9 clang::BackendConsumer::HandleTranslationUnit(clang::ASTContext&) .../llvm-new/llvm-project/clang/lib/CodeGen/CodeGenAction.cpp:344:7
#27 0x0000000007f5fd2e clang::ParseAST(clang::Sema&, bool, bool) .../llvm-new/llvm-project/clang/lib/Parse/ParseAST.cpp:178:12
#28 0x00000000056d13a2 clang::ASTFrontendAction::ExecuteAction() .../llvm-new/llvm-project/clang/lib/Frontend/FrontendAction.cpp:1058:1
#29 0x00000000061a8869 clang::CodeGenAction::ExecuteAction() .../llvm-new/llvm-project/clang/lib/CodeGen/CodeGenAction.cpp:1083:5
#30 0x00000000056d0d68 clang::FrontendAction::Execute() .../llvm-new/llvm-project/clang/lib/Frontend/FrontendAction.cpp:953:7
#31 0x000000000560a028 clang::CompilerInstance::ExecuteAction(clang::FrontendAction&) .../llvm-new/llvm-project/clang/lib/Frontend/CompilerInstance.cpp:949:23
#32 0x000000000588dbb6 clang::ExecuteCompilerInvocation(clang::CompilerInstance*) .../llvm-new/llvm-project/clang/lib/FrontendTool/ExecuteCompilerInvocation.cpp:278:8
#33 0x000000000142cf0d cc1_main(llvm::ArrayRef<char const*>, char const*, void*) .../llvm-new/llvm-project/clang/tools/driver/cc1_main.cpp:246:13
#34 0x000000000141f759 ExecuteCC1Tool(llvm::SmallVectorImpl<char const*>&) .../llvm-new/llvm-project/clang/tools/driver/driver.cpp:330:5
#35 0x000000000141e8ee main .../llvm-new/llvm-project/clang/tools/driver/driver.cpp:407:5
#36 0x00007f522c9a2d0a __libc_start_main ./csu/../csu/libc-start.c:308:16
#37 0x000000000141e09a _start (./bin/clang+0x141e09a)
Segmentation fault

[saugustine]

Reverted in 5aa8f4c0843a68a24cb37dce5c0248c849d7d476

[RKSimon]

@saugustine OK - I don't suppose you managed to get the IR (reduced or otherwise) please?

[saugustine]

this is as small as llvm-reduce makes the ir:

./bin/llc --mtriple x86_64-grtev4-linux-gnu -O1 $1

; ModuleID = '/usr/local/google/home/saugustine/tmp/test.ll'
source_filename = "/usr/local/google/home/saugustine/tmp/test.c"
target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-grtev4-linux-gnu"

define dso_local i32 @j() {
entry:

%0 = load <2 x i64>, <2 x i64>* undef, align 16, !tbaa !0
%psrldq = shufflevector <16 x i8> undef, <16 x i8> <i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 poison, i8 poison, i8 poison, i8 poison, i8 poison, i8 poison, i8 poison, i8 poison>, <16 x i32> <i32 8, i32 9, i32 10, i32 11, i32 12, i32 13, i32 14, i32 15, i32 16, i32 17, i32 18, i32 19, i32 20, i32 21, i32 22, i32 23>
%1 = load <2 x i64>, <2 x i64>* undef, align 16, !tbaa !0
%2 = bitcast <2 x i64> %0 to <8 x i16>
%3 = bitcast <2 x i64> %1 to <8 x i16>
%add.i = add <8 x i16> %3, %2
%4 = bitcast <8 x i16> %add.i to <2 x i64>
%5 = bitcast <16 x i8> %psrldq to <8 x i16>
%6 = bitcast <2 x i64> %1 to <8 x i16>
%7 = shufflevector <8 x i16> %6, <8 x i16> poison, <8 x i32> <i32 4, i32 5, i32 6, i32 7, i32 undef, i32 undef, i32 undef, i32 undef>
%add.i24 = add <8 x i16> %7, %5
%8 = bitcast <8 x i16> %add.i24 to <2 x i64>
%shuffle = shufflevector <2 x i64> %4, <2 x i64> %8, <2 x i32> <i32 0, i32 2>
%9 = bitcast <2 x i64> %shuffle to <8 x i16>
%10 = call <8 x i16> @llvm.x86.sse2.psrli.w(<8 x i16> %9, i32 ptrtoint (i32 ()* @j to i32))
store <8 x i16> %10, <8 x i16>* undef, align 16, !tbaa !0
ret i32 undef

}

; Function Attrs: nounwind readnone
declare <8 x i16> @llvm.x86.sse2.psrli.w(<8 x i16>, i32) #0

attributes #0 = { nounwind readnone }

!0 = !{!1, !1, i64 0}
!1 = !{!"omnipotent char", !2, i64 0}
!2 = !{!"Simple C/C++ TBAA"}

[RKSimon]

Thanks @saugustine I somehow managed to lose a null check in one the refactors......

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

if (N0.getOpcode() == ISD::VECTOR_SHUFFLE &&
         cast<ShuffleVectorSDNode>(N0)->isSplat() &&
         !cast<ShuffleVectorSDNode>(N1)->isSplat()) {
       return DAG.getCommutedVectorShuffle(*SVN);
     }
   }
 
   // Compute the combined shuffle mask for a shuffle with SV0 as the first
   // operand, and SV1 as the second operand.
-  // i.e. Merge SVN(OtherSVN, N1) -> shuffle(SV0, SV1, Mask).
+  // i.e. Merge SVN(OtherSVN, N1) -> shuffle(SV0, SV1, Mask) iff Commute = false
+  //      Merge SVN(N1, OtherSVN) -> shuffle(SV0, SV1, Mask') iff Commute = true
   auto MergeInnerShuffle =
-      [NumElts, &VT](ShuffleVectorSDNode *SVN, ShuffleVectorSDNode *OtherSVN,
-                     SDValue N1, const TargetLowering &TLI, SDValue &SV0,
-                     SDValue &SV1, SmallVectorImpl<int> &Mask) -> bool {
+      [NumElts, &VT](bool Commute, ShuffleVectorSDNode *SVN,
+                     ShuffleVectorSDNode *OtherSVN, SDValue N1,
+                     const TargetLowering &TLI, SDValue &SV0, SDValue &SV1,
+                     SmallVectorImpl<int> &Mask) -> bool {
     // Don't try to fold splats; they're likely to simplify somehow, or they
     // might be free.
     if (OtherSVN->isSplat())
       return false;
 
     SV0 = SV1 = SDValue();
     Mask.clear();
 
     for (unsigned i = 0; i != NumElts; ++i) {
       int Idx = SVN->getMaskElt(i);
       if (Idx < 0) {
         // Propagate Undef.
         Mask.push_back(Idx);
         continue;
       }
 
+      if (Commute)
+        Idx = (Idx < (int)NumElts) ? (Idx + NumElts) : (Idx - NumElts);
+
       SDValue CurrentVec;
       if (Idx < (int)NumElts) {
         // This shuffle index refers to the inner shuffle N0. Lookup the inner
         // shuffle mask to identify which vector is actually referenced.
         Idx = OtherSVN->getMaskElt(Idx);
         if (Idx < 0) {
           // Propagate Undef.
           Mask.push_back(Idx);
for (unsigned i = 0; i != NumElts; ++i) {
       Idx = Idx % NumElts;
       if (!SV0.getNode() || SV0 == CurrentVec) {
         // Ok. CurrentVec is the left hand side.
         // Update the mask accordingly.
         SV0 = CurrentVec;
         Mask.push_back(Idx);
         continue;
       }
       if (!SV1.getNode() || SV1 == CurrentVec) {
         // Ok. CurrentVec is the right hand side.
         // Update the mask accordingly.
         SV1 = CurrentVec;
         Mask.push_back(Idx + NumElts);
         continue;
       }
 
       // Last chance - see if the vector is another shuffle and if it
       // uses one of the existing candidate shuffle ops.
       if (auto *CurrentSVN = dyn_cast<ShuffleVectorSDNode>(CurrentVec)) {
         int InnerIdx = CurrentSVN->getMaskElt(Idx);
         if (InnerIdx < 0) {
           Mask.push_back(-1);
           continue;
         }
         SDValue InnerVec = (InnerIdx < (int)NumElts)
                                ? CurrentSVN->getOperand(0)
                                : CurrentSVN->getOperand(1);
         if (InnerVec.isUndef()) {
           Mask.push_back(-1);
           continue;
         }
         InnerIdx %= NumElts;
         if (InnerVec == SV0) {
           Mask.push_back(InnerIdx);
           continue;
         }
         if (InnerVec == SV1) {
           Mask.push_back(InnerIdx + NumElts);
           continue;
         }
       }
 
       // Bail out if we cannot convert the shuffle pair into a single shuffle.
if (N0.getOpcode() == ISD::VECTOR_SHUFFLE && N->isOnlyUserOf(N0.getNode()) &&
     // The incoming shuffle must be of the same type as the result of the
     // current shuffle.
     auto *OtherSV = cast<ShuffleVectorSDNode>(N0);
     assert(OtherSV->getOperand(0).getValueType() == VT &&
            "Shuffle types don't match");
 
     SDValue SV0, SV1;
     SmallVector<int, 4> Mask;
-    if (MergeInnerShuffle(SVN, OtherSV, N1, TLI, SV0, SV1, Mask)) {
+    if (MergeInnerShuffle(false, SVN, OtherSV, N1, TLI, SV0, SV1, Mask)) {
       // Check if all indices in Mask are Undef. In case, propagate Undef.
       if (llvm::all_of(Mask, [](int M) { return M < 0; }))
         return DAG.getUNDEF(VT);
 
       return DAG.getVectorShuffle(VT, SDLoc(N), SV0 ? SV0 : DAG.getUNDEF(VT),
                                   SV1 ? SV1 : DAG.getUNDEF(VT), Mask);
     }
   }
 
+  // Merge shuffles through binops if we are able to merge it with at least one
+  // other shuffles.
+  // shuffle(bop(shuffle(x,y),shuffle(z,w)),bop(shuffle(a,b),shuffle(c,d)))
+  if (Level < AfterLegalizeDAG && TLI.isTypeLegal(VT)) {
+    unsigned SrcOpcode = N0.getOpcode();
+    if (SrcOpcode == N1.getOpcode() && TLI.isBinOp(SrcOpcode) &&
+        N->isOnlyUserOf(N0.getNode()) && N->isOnlyUserOf(N1.getNode())) {
+      SDValue Op00 = N0.getOperand(0);
+      SDValue Op10 = N1.getOperand(0);
+      SDValue Op01 = N0.getOperand(1);
+      SDValue Op11 = N1.getOperand(1);
+      // TODO: We might be able to relax the VT check but we don't currently
+      // have any isBinOp() that has different result/ops VTs so play safe until
+      // we have test coverage.
+      if (Op00.getValueType() == VT && Op10.getValueType() == VT &&
+          Op01.getValueType() == VT && Op11.getValueType() == VT &&
+          (Op00.getOpcode() == ISD::VECTOR_SHUFFLE ||
+           Op10.getOpcode() == ISD::VECTOR_SHUFFLE ||
+           Op01.getOpcode() == ISD::VECTOR_SHUFFLE ||
+           Op11.getOpcode() == ISD::VECTOR_SHUFFLE)) {
+        auto CanMergeInnerShuffle = [&](SDValue &SV0, SDValue &SV1,
+                                        SmallVectorImpl<int> &Mask, bool LeftOp,
+                                        bool Commute) {
+          SDValue InnerN = Commute ? N1 : N0;
+          SDValue Op0 = LeftOp ? Op00 : Op01;
+          SDValue Op1 = LeftOp ? Op10 : Op11;
+          if (Commute)
+            std::swap(Op0, Op1);
+          return Op0.getOpcode() == ISD::VECTOR_SHUFFLE &&
+                 InnerN->isOnlyUserOf(Op0.getNode()) &&
+                 MergeInnerShuffle(Commute, SVN, cast<ShuffleVectorSDNode>(Op0),
+                                   Op1, TLI, SV0, SV1, Mask) &&
+                 llvm::none_of(Mask, [](int M) { return M < 0; });
+        };
+
+        // Ensure we don't increase the number of shuffles - we must merge a
+        // shuffle from at least one of the LHS and RHS ops.
+        bool MergedLeft = false;
+        SDValue LeftSV0, LeftSV1;
+        SmallVector<int, 4> LeftMask;
+        if (CanMergeInnerShuffle(LeftSV0, LeftSV1, LeftMask, true, false) ||
+            CanMergeInnerShuffle(LeftSV0, LeftSV1, LeftMask, true, true)) {
+          MergedLeft = true;
+        } else {
+          LeftMask.assign(SVN->getMask().begin(), SVN->getMask().end());
+          LeftSV0 = Op00, LeftSV1 = Op10;
+        }
+
+        bool MergedRight = false;
+        SDValue RightSV0, RightSV1;
+        SmallVector<int, 4> RightMask;
+        if (CanMergeInnerShuffle(RightSV0, RightSV1, RightMask, false, false) ||
+            CanMergeInnerShuffle(RightSV0, RightSV1, RightMask, false, true)) {
+          MergedRight = true;
+        } else {
+          RightMask.assign(SVN->getMask().begin(), SVN->getMask().end());
+          RightSV0 = Op01, RightSV1 = Op11;
+        }
+
+        if (MergedLeft || MergedRight) {
+          SDLoc DL(N);
+          SDValue LHS =
+              DAG.getVectorShuffle(VT, DL, LeftSV0, LeftSV1, LeftMask);
+          SDValue RHS =
+              DAG.getVectorShuffle(VT, DL, RightSV0, RightSV1, RightMask);
+          return DAG.getNode(SrcOpcode, DL, VT, LHS, RHS);
+        }
+      }
+    }
+  }
+
   if (SDValue V = foldShuffleOfConcatUndefs(SVN, DAG))
     return V;
 
   return SDValue();
 }
 
 SDValue DAGCombiner::visitSCALAR_TO_VECTOR(SDNode *N) {
   SDValue InVal = N->getOperand(0);

llvm/lib/Target/X86/X86ISelLowering.cpp

static SDValue combineShuffle(SDNode *N, SelectionDAG &DAG,
   EVT VT = N->getValueType(0);
   const TargetLowering &TLI = DAG.getTargetLoweringInfo();
   if (TLI.isTypeLegal(VT)) {
     if (SDValue AddSub = combineShuffleToAddSubOrFMAddSub(N, Subtarget, DAG))
       return AddSub;
 
     if (SDValue HAddSub = foldShuffleOfHorizOp(N, DAG))
       return HAddSub;
-
-    // Merge shuffles through binops if its likely we'll be able to merge it
-    // with other shuffles (as long as they aren't splats).
-    // shuffle(bop(shuffle(x,y),shuffle(z,w)),bop(shuffle(a,b),shuffle(c,d)))
-    // TODO: We might be able to move this to DAGCombiner::visitVECTOR_SHUFFLE.
-    if (auto *SVN = dyn_cast<ShuffleVectorSDNode>(N)) {
-      unsigned SrcOpcode = N->getOperand(0).getOpcode();
-      if (SrcOpcode == N->getOperand(1).getOpcode() && TLI.isBinOp(SrcOpcode) &&
-          N->isOnlyUserOf(N->getOperand(0).getNode()) &&
-          N->isOnlyUserOf(N->getOperand(1).getNode())) {
-        SDValue Op00 = N->getOperand(0).getOperand(0);
-        SDValue Op10 = N->getOperand(1).getOperand(0);
-        SDValue Op01 = N->getOperand(0).getOperand(1);
-        SDValue Op11 = N->getOperand(1).getOperand(1);
-        auto *SVN00 = dyn_cast<ShuffleVectorSDNode>(Op00);
-        auto *SVN10 = dyn_cast<ShuffleVectorSDNode>(Op10);
-        auto *SVN01 = dyn_cast<ShuffleVectorSDNode>(Op01);
-        auto *SVN11 = dyn_cast<ShuffleVectorSDNode>(Op11);
-        if (((SVN00 && !SVN00->isSplat()) || (SVN10 && !SVN10->isSplat())) &&
-            ((SVN01 && !SVN01->isSplat()) || (SVN11 && !SVN11->isSplat()))) {
-          SDLoc DL(N);
-          ArrayRef<int> Mask = SVN->getMask();
-          SDValue LHS = DAG.getVectorShuffle(VT, DL, Op00, Op10, Mask);
-          SDValue RHS = DAG.getVectorShuffle(VT, DL, Op01, Op11, Mask);
-          return DAG.getNode(SrcOpcode, DL, VT, LHS, RHS);
-        }
-      }
-    }
   }
 
   // Attempt to combine into a vector load/broadcast.
   if (SDValue LD = combineToConsecutiveLoads(VT, SDValue(N, 0), dl, DAG,
                                              Subtarget, true))
     return LD;
 
   // For AVX2, we sometimes want to combine

llvm/test/CodeGen/X86/bitcast-and-setcc-256.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc < %s -mtriple=x86_64-unknown-unknown -mattr=+SSE2 | FileCheck %s --check-prefix=SSE2-SSSE3
 ; RUN: llc < %s -mtriple=x86_64-unknown-unknown -mattr=+SSSE3 | FileCheck %s --check-prefix=SSE2-SSSE3
 ; RUN: llc < %s -mtriple=x86_64-unknown-unknown -mattr=+avx | FileCheck %s --check-prefixes=AVX12,AVX1
 ; RUN: llc < %s -mtriple=x86_64-unknown-unknown -mattr=+avx2 | FileCheck %s --check-prefixes=AVX12,AVX2
 ; RUN: llc < %s -mtriple=x86_64-unknown-unknown -mattr=+avx512f,+avx512vl | FileCheck %s --check-prefix=AVX512F
 ; RUN: llc < %s -mtriple=x86_64-unknown-unknown -mattr=+avx512f,+avx512vl,+avx512bw | FileCheck %s --check-prefix=AVX512BW
 
 define i4 @v4i64(<4 x i64> %a, <4 x i64> %b, <4 x i64> %c, <4 x i64> %d) {
 ; SSE2-SSSE3-LABEL: v4i64:
 ; SSE2-SSSE3:       # %bb.0:
-; SSE2-SSSE3-NEXT:    movdqa {{.*#+}} xmm8 = [2147483648,2147483648]
-; SSE2-SSSE3-NEXT:    pxor %xmm8, %xmm3
-; SSE2-SSSE3-NEXT:    pxor %xmm8, %xmm1
-; SSE2-SSSE3-NEXT:    movdqa %xmm1, %xmm9
-; SSE2-SSSE3-NEXT:    pcmpgtd %xmm3, %xmm9
+; SSE2-SSSE3-NEXT:    movdqa {{.*#+}} xmm9 = [2147483648,2147483648]
+; SSE2-SSSE3-NEXT:    pxor %xmm9, %xmm3
+; SSE2-SSSE3-NEXT:    pxor %xmm9, %xmm1
+; SSE2-SSSE3-NEXT:    movdqa %xmm1, %xmm10
+; SSE2-SSSE3-NEXT:    pcmpgtd %xmm3, %xmm10
+; SSE2-SSSE3-NEXT:    pxor %xmm9, %xmm2
+; SSE2-SSSE3-NEXT:    pxor %xmm9, %xmm0
+; SSE2-SSSE3-NEXT:    movdqa %xmm0, %xmm8
+; SSE2-SSSE3-NEXT:    pcmpgtd %xmm2, %xmm8
+; SSE2-SSSE3-NEXT:    movdqa %xmm8, %xmm11
+; SSE2-SSSE3-NEXT:    shufps {{.*#+}} xmm11 = xmm11[0,2],xmm10[0,2]
 ; SSE2-SSSE3-NEXT:    pcmpeqd %xmm3, %xmm1
-; SSE2-SSSE3-NEXT:    pshufd {{.*#+}} xmm1 = xmm1[1,1,3,3]
-; SSE2-SSSE3-NEXT:    pand %xmm9, %xmm1
-; SSE2-SSSE3-NEXT:    pshufd {{.*#+}} xmm3 = xmm9[1,1,3,3]
-; SSE2-SSSE3-NEXT:    por %xmm1, %xmm3
-; SSE2-SSSE3-NEXT:    pxor %xmm8, %xmm2
-; SSE2-SSSE3-NEXT:    pxor %xmm8, %xmm0
-; SSE2-SSSE3-NEXT:    movdqa %xmm0, %xmm1
-; SSE2-SSSE3-NEXT:    pcmpgtd %xmm2, %xmm1
 ; SSE2-SSSE3-NEXT:    pcmpeqd %xmm2, %xmm0
-; SSE2-SSSE3-NEXT:    pshufd {{.*#+}} xmm2 = xmm0[1,1,3,3]
-; SSE2-SSSE3-NEXT:    pand %xmm1, %xmm2
-; SSE2-SSSE3-NEXT:    pshufd {{.*#+}} xmm0 = xmm1[1,1,3,3]
-; SSE2-SSSE3-NEXT:    por %xmm2, %xmm0
-; SSE2-SSSE3-NEXT:    shufps {{.*#+}} xmm0 = xmm0[0,2],xmm3[0,2]
-; SSE2-SSSE3-NEXT:    pxor %xmm8, %xmm7
-; SSE2-SSSE3-NEXT:    pxor %xmm8, %xmm5
-; SSE2-SSSE3-NEXT:    movdqa %xmm5, %xmm1
-; SSE2-SSSE3-NEXT:    pcmpgtd %xmm7, %xmm1
+; SSE2-SSSE3-NEXT:    shufps {{.*#+}} xmm0 = xmm0[1,3],xmm1[1,3]
+; SSE2-SSSE3-NEXT:    andps %xmm11, %xmm0
+; SSE2-SSSE3-NEXT:    shufps {{.*#+}} xmm8 = xmm8[1,3],xmm10[1,3]
+; SSE2-SSSE3-NEXT:    orps %xmm0, %xmm8
+; SSE2-SSSE3-NEXT:    pxor %xmm9, %xmm7
+; SSE2-SSSE3-NEXT:    pxor %xmm9, %xmm5
+; SSE2-SSSE3-NEXT:    movdqa %xmm5, %xmm0
+; SSE2-SSSE3-NEXT:    pcmpgtd %xmm7, %xmm0
+; SSE2-SSSE3-NEXT:    pxor %xmm9, %xmm6
+; SSE2-SSSE3-NEXT:    pxor %xmm9, %xmm4
+; SSE2-SSSE3-NEXT:    movdqa %xmm4, %xmm1
+; SSE2-SSSE3-NEXT:    pcmpgtd %xmm6, %xmm1
+; SSE2-SSSE3-NEXT:    movdqa %xmm1, %xmm2
+; SSE2-SSSE3-NEXT:    shufps {{.*#+}} xmm2 = xmm2[0,2],xmm0[0,2]
 ; SSE2-SSSE3-NEXT:    pcmpeqd %xmm7, %xmm5
-; SSE2-SSSE3-NEXT:    pshufd {{.*#+}} xmm2 = xmm5[1,1,3,3]
-; SSE2-SSSE3-NEXT:    pand %xmm1, %xmm2
-; SSE2-SSSE3-NEXT:    pshufd {{.*#+}} xmm1 = xmm1[1,1,3,3]
-; SSE2-SSSE3-NEXT:    por %xmm2, %xmm1
-; SSE2-SSSE3-NEXT:    pxor %xmm8, %xmm6
-; SSE2-SSSE3-NEXT:    pxor %xmm8, %xmm4
-; SSE2-SSSE3-NEXT:    movdqa %xmm4, %xmm2
-; SSE2-SSSE3-NEXT:    pcmpgtd %xmm6, %xmm2
 ; SSE2-SSSE3-NEXT:    pcmpeqd %xmm6, %xmm4
-; SSE2-SSSE3-NEXT:    pshufd {{.*#+}} xmm3 = xmm4[1,1,3,3]
-; SSE2-SSSE3-NEXT:    pand %xmm2, %xmm3
-; SSE2-SSSE3-NEXT:    pshufd {{.*#+}} xmm2 = xmm2[1,1,3,3]
-; SSE2-SSSE3-NEXT:    por %xmm3, %xmm2
-; SSE2-SSSE3-NEXT:    shufps {{.*#+}} xmm2 = xmm2[0,2],xmm1[0,2]
-; SSE2-SSSE3-NEXT:    andps %xmm0, %xmm2
-; SSE2-SSSE3-NEXT:    movmskps %xmm2, %eax
+; SSE2-SSSE3-NEXT:    shufps {{.*#+}} xmm4 = xmm4[1,3],xmm5[1,3]
+; SSE2-SSSE3-NEXT:    andps %xmm2, %xmm4
+; SSE2-SSSE3-NEXT:    shufps {{.*#+}} xmm1 = xmm1[1,3],xmm0[1,3]
+; SSE2-SSSE3-NEXT:    orps %xmm4, %xmm1
+; SSE2-SSSE3-NEXT:    andps %xmm8, %xmm1
+; SSE2-SSSE3-NEXT:    movmskps %xmm1, %eax
 ; SSE2-SSSE3-NEXT:    # kill: def $al killed $al killed $eax
 ; SSE2-SSSE3-NEXT:    retq
 ;
 ; AVX1-LABEL: v4i64:
 ; AVX1:       # %bb.0:
 ; AVX1-NEXT:    vextractf128 $1, %ymm3, %xmm4
 ; AVX1-NEXT:    vextractf128 $1, %ymm2, %xmm5
 ; AVX1-NEXT:    vpcmpgtq %xmm4, %xmm5, %xmm4

llvm/test/CodeGen/X86/promote-cmp.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc < %s -mtriple=x86_64-- -mattr=+sse2   | FileCheck %s --check-prefix=SSE2
 ; RUN: llc < %s -mtriple=x86_64-- -mattr=+sse4.2 | FileCheck %s --check-prefix=SSE4
 ; RUN: llc < %s -mtriple=x86_64-- -mattr=+avx    | FileCheck %s --check-prefix=AVX1
 ; RUN: llc < %s -mtriple=x86_64-- -mattr=+avx2   | FileCheck %s --check-prefix=AVX2
 
 define <4 x i64> @PR45808(<4 x i64> %0, <4 x i64> %1) {
 ; SSE2-LABEL: PR45808:
 ; SSE2:       # %bb.0:
 ; SSE2-NEXT:    movdqa {{.*#+}} xmm4 = [2147483648,2147483648]
-; SSE2-NEXT:    movdqa %xmm3, %xmm5
-; SSE2-NEXT:    pxor %xmm4, %xmm5
+; SSE2-NEXT:    movdqa %xmm3, %xmm9
+; SSE2-NEXT:    pxor %xmm4, %xmm9
 ; SSE2-NEXT:    movdqa %xmm1, %xmm6
 ; SSE2-NEXT:    pxor %xmm4, %xmm6
-; SSE2-NEXT:    movdqa %xmm6, %xmm7
-; SSE2-NEXT:    pcmpgtd %xmm5, %xmm7
-; SSE2-NEXT:    pcmpeqd %xmm5, %xmm6
-; SSE2-NEXT:    pshufd {{.*#+}} xmm5 = xmm6[1,1,3,3]
-; SSE2-NEXT:    pand %xmm7, %xmm5
-; SSE2-NEXT:    pshufd {{.*#+}} xmm6 = xmm7[1,1,3,3]
-; SSE2-NEXT:    por %xmm5, %xmm6
-; SSE2-NEXT:    movdqa %xmm2, %xmm5
-; SSE2-NEXT:    pxor %xmm4, %xmm5
+; SSE2-NEXT:    movdqa %xmm6, %xmm8
+; SSE2-NEXT:    pcmpgtd %xmm9, %xmm8
+; SSE2-NEXT:    movdqa %xmm2, %xmm7
+; SSE2-NEXT:    pxor %xmm4, %xmm7
 ; SSE2-NEXT:    pxor %xmm0, %xmm4
-; SSE2-NEXT:    movdqa %xmm4, %xmm7
-; SSE2-NEXT:    pcmpgtd %xmm5, %xmm7
-; SSE2-NEXT:    pcmpeqd %xmm5, %xmm4
+; SSE2-NEXT:    movdqa %xmm4, %xmm5
+; SSE2-NEXT:    pcmpgtd %xmm7, %xmm5
+; SSE2-NEXT:    movdqa %xmm5, %xmm10
+; SSE2-NEXT:    shufps {{.*#+}} xmm10 = xmm10[0,2],xmm8[0,2]
+; SSE2-NEXT:    pcmpeqd %xmm9, %xmm6
+; SSE2-NEXT:    pcmpeqd %xmm7, %xmm4
+; SSE2-NEXT:    shufps {{.*#+}} xmm4 = xmm4[1,3],xmm6[1,3]
+; SSE2-NEXT:    andps %xmm10, %xmm4
+; SSE2-NEXT:    shufps {{.*#+}} xmm5 = xmm5[1,3],xmm8[1,3]
+; SSE2-NEXT:    orps %xmm4, %xmm5
+; SSE2-NEXT:    pshufd {{.*#+}} xmm4 = xmm5[2,1,3,3]
+; SSE2-NEXT:    pxor {{.*}}(%rip), %xmm5
+; SSE2-NEXT:    psllq $63, %xmm4
+; SSE2-NEXT:    psrad $31, %xmm4
 ; SSE2-NEXT:    pshufd {{.*#+}} xmm4 = xmm4[1,1,3,3]
-; SSE2-NEXT:    pand %xmm7, %xmm4
-; SSE2-NEXT:    pshufd {{.*#+}} xmm5 = xmm7[1,1,3,3]
-; SSE2-NEXT:    por %xmm4, %xmm5
-; SSE2-NEXT:    pshufd {{.*#+}} xmm4 = xmm5[0,2,2,3]
-; SSE2-NEXT:    pxor {{.*}}(%rip), %xmm4
-; SSE2-NEXT:    psllq $63, %xmm6
-; SSE2-NEXT:    psrad $31, %xmm6
-; SSE2-NEXT:    pshufd {{.*#+}} xmm5 = xmm6[1,1,3,3]
-; SSE2-NEXT:    pand %xmm5, %xmm1
-; SSE2-NEXT:    pandn %xmm3, %xmm5
-; SSE2-NEXT:    por %xmm5, %xmm1
-; SSE2-NEXT:    pshufd {{.*#+}} xmm3 = xmm4[0,1,1,3]
+; SSE2-NEXT:    pand %xmm4, %xmm1
+; SSE2-NEXT:    pandn %xmm3, %xmm4
+; SSE2-NEXT:    por %xmm4, %xmm1
+; SSE2-NEXT:    pshufd {{.*#+}} xmm3 = xmm5[0,1,1,3]
 ; SSE2-NEXT:    psllq $63, %xmm3
 ; SSE2-NEXT:    psrad $31, %xmm3
 ; SSE2-NEXT:    pshufd {{.*#+}} xmm3 = xmm3[1,1,3,3]
 ; SSE2-NEXT:    pand %xmm3, %xmm0
 ; SSE2-NEXT:    pandn %xmm2, %xmm3
 ; SSE2-NEXT:    por %xmm3, %xmm0
 ; SSE2-NEXT:    retq
 ;