DAGcombiner: Handle correctly non-splat power of 2 -1 divisor

[RKSimon]

Summary

The combine added in commit 329525 overlooked the case where
one, but not all, of the divisor elements is -1.
-1 is the only power of two value for which the sdiv expansion recipe
breaks.

Fixes pr37119

[zvi]

Minor improvement: No need for the select if there are no negatives

[RKSimon]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

2964

Do you need the getSplatBuildVector? I think DAG.getAllOnesConstant can accept a vector type:

DAG.getAllOnesConstant(DL, VT)

[RKSimon]

@zvi Any movement on this? I can commandeer if you're still busy.

[RKSimon]

In D45806#1109593, @RKSimon wrote:

@zvi Any movement on this? I can commandeer if you're still busy.

@zvi I'm going to commandeer this and get it finished if you don't mind.

[RKSimon]

Commandeering as @zvi is busy with other things

[RKSimon]

Refactored the patch to blend the special case values in at the end of the pow2 calculations.

I'll add the SignedMin case in a followup but I wanted to keep this patch focussed on the -1 divisor case.

[zvi]

Sorry for not being responsive. Won't have time to work on this, so thanks @RKSimon for taking charge.

[efriedma]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

15–1

Not really relevant to this review, but I think KnownNegatives is dead.

16

Instead of separate special cases for 1 and -1, could you move the special case for 1 before the result is negated? Would probably result in a little less code for vectors like <1, -1, 2, -2>

20

I'm not sure you actually need a special case for MIN_SIGNED; I think r335720 solved the issue.

[RKSimon]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

16

I'll look at this next

20

I think you're right - I'll leave the IsPowerOfTwo early out in for now but won't need to add a special case selection.

[RKSimon]

Merged the 2 negations together as suggested by @efriedma

[efriedma]

I think you can save a blend by emitting one select for both "1" and "-1"? (SDValue IsOneOrAllOnes = DAG.getNode(ISD::OR, VT, IsAllOnes, IsOne); etc.)

[RKSimon]

Nice catch! Merged -1/+1 blending into single op.

[efriedma]

LGTM

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

 //===- DAGCombiner.cpp - Implement a DAG node combiner --------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This pass combines dag nodes to form fewer, simpler DAG nodes.  It can be run
 // both before and after the DAG is legalized.
 //
 // This pass is not a substitute for the LLVM IR instcombine pass. This pass is
 // primarily intended to handle simplification opportunities that are implicit
 // in the LLVM IR and exposed by the various codegen lowering phases.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/ADT/APFloat.h"
 #include "llvm/ADT/APInt.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/None.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallBitVector.h"
 #include "llvm/ADT/SmallPtrSet.h"
if (!N->getFlags().hasExact() &&
     AddToWorklist(Sign.getNode());
 
     // Add (N0 < 0) ? abs2 - 1 : 0;
     SDValue Srl = DAG.getNode(ISD::SRL, DL, VT, Sign, Inexact);
     SDValue Add = DAG.getNode(ISD::ADD, DL, VT, N0, Srl);
     AddToWorklist(Srl.getNode());
     AddToWorklist(Add.getNode()); // Divide by pow2
     SDValue Sra = DAG.getNode(ISD::SRA, DL, VT, Add, C1);
+    // Handle the special case where any of the divisor elements is -1.
+    // The rounding correction will result in the respective elements being
+    // undef. No shifting is needed for -1, so we can bypass the undefs by
+    // adding a select. The scalar and splat cases were already handled earlier,
+    // so we only need to handle non-splat vector divisors.
+    // FIXME: Use a SELECT_CC once we improve SELECT_CC constant-folding.
+    if (VT.isVector())
+      Sra = DAG.getSelect(
+          DL, VT,
+          DAG.getSetCC(
+              DL, VT, N1,
+              DAG.getSplatBuildVector(
+                  VT, DL, DAG.getAllOnesConstant(DL, VT.getScalarType())),
+              ISD::SETEQ),
+          N0, Sra);
 
     // If dividing by a positive value, we're done. Otherwise, the result must
     // be negated.
     if (KnownNegatives.none())
       return Sra;
 
     AddToWorklist(Sra.getNode());
     SDValue Sub =
         DAG.getNode(ISD::SUB, DL, VT, DAG.getConstant(0, DL, VT), Sra);
     // If all shift amount elements are negative, we're done.
     if (KnownNegatives.all())
       return Sub;
 
     // Shift amount has both positive and negative elements.
     assert(VT.isVector() && !N0C &&
            "Expecting a non-splat vector shift amount");
 
     SmallVector<SDValue, 64> VSelectMask;
     for (int i = 0, e = VT.getVectorNumElements(); i < e; ++i)
       VSelectMask.push_back(
           DAG.getConstant(KnownNegatives[i] ? -1 : 0, DL, MVT::i1));
 
     SDValue Mask =
         DAG.getBuildVector(EVT::getVectorVT(*DAG.getContext(), MVT::i1,
                                             VT.getVectorElementCount()),
                            DL, VSelectMask);
     return DAG.getNode(ISD::VSELECT, DL, VT, Mask, Sub, Sra);

test/CodeGen/X86/combine-sdiv.ll

 
 define <4 x i32> @combine_vec_sdiv_by_pow2b_undef3(<4 x i32> %x) {
 ; CHECK-LABEL: combine_vec_sdiv_by_pow2b_undef3:
 ; CHECK:       # %bb.0:
 ; CHECK-NEXT:    retq
   %1 = sdiv <4 x i32> %x, <i32 undef, i32 -4, i32 undef, i32 16>
   ret <4 x i32> %1
 }
+
+; PR37119
+define <16 x i8> @non_splat_minus_one_divisor_0(<16 x i8> %A) {
+; SSE-LABEL: non_splat_minus_one_divisor_0:
+; SSE:       # %bb.0:
+; SSE-NEXT:    movdqa %xmm0, %xmm1
+; SSE-NEXT:    pxor %xmm2, %xmm2
+; SSE-NEXT:    psubb %xmm0, %xmm2
+; SSE-NEXT:    movaps {{.*#+}} xmm0 = [0,0,255,0,0,0,255,0,0,255,255,255,255,255,255,255]
+; SSE-NEXT:    pblendvb %xmm0, %xmm1, %xmm2
+; SSE-NEXT:    movdqa %xmm2, %xmm0
+; SSE-NEXT:    retq
+;
+; AVX1-LABEL: non_splat_minus_one_divisor_0:
+; AVX1:       # %bb.0:
+; AVX1-NEXT:    vpxor %xmm1, %xmm1, %xmm1
+; AVX1-NEXT:    vpsubb %xmm0, %xmm1, %xmm1
+; AVX1-NEXT:    vmovdqa {{.*#+}} xmm2 = [0,0,255,0,0,0,255,0,0,255,255,255,255,255,255,255]
+; AVX1-NEXT:    vpblendvb %xmm2, %xmm0, %xmm1, %xmm0
+; AVX1-NEXT:    retq
+;
+; AVX2-LABEL: non_splat_minus_one_divisor_0:
+; AVX2:       # %bb.0:
+; AVX2-NEXT:    vpxor %xmm1, %xmm1, %xmm1
+; AVX2-NEXT:    vpsubb %xmm0, %xmm1, %xmm1
+; AVX2-NEXT:    vmovdqa {{.*#+}} xmm2 = [0,0,255,0,0,0,255,0,0,255,255,255,255,255,255,255]
+; AVX2-NEXT:    vpblendvb %xmm2, %xmm0, %xmm1, %xmm0
+; AVX2-NEXT:    retq
+;
+; AVX512F-LABEL: non_splat_minus_one_divisor_0:
+; AVX512F:       # %bb.0:
+; AVX512F-NEXT:    vpxor %xmm1, %xmm1, %xmm1
+; AVX512F-NEXT:    vpsubb %xmm0, %xmm1, %xmm1
+; AVX512F-NEXT:    vmovdqa {{.*#+}} xmm2 = [0,0,255,0,0,0,255,0,0,255,255,255,255,255,255,255]
+; AVX512F-NEXT:    vpblendvb %xmm2, %xmm0, %xmm1, %xmm0
+; AVX512F-NEXT:    retq
+;
+; AVX512BW-LABEL: non_splat_minus_one_divisor_0:
+; AVX512BW:       # %bb.0:
+; AVX512BW-NEXT:    vpxor %xmm1, %xmm1, %xmm1
+; AVX512BW-NEXT:    movw $443, %ax # imm = 0x1BB
+; AVX512BW-NEXT:    kmovd %eax, %k1
+; AVX512BW-NEXT:    vpsubb %xmm0, %xmm1, %xmm0 {%k1}
+; AVX512BW-NEXT:    retq
+;
+; XOP-LABEL: non_splat_minus_one_divisor_0:
+; XOP:       # %bb.0:
+; XOP-NEXT:    vpxor %xmm1, %xmm1, %xmm1
+; XOP-NEXT:    vpsubb %xmm0, %xmm1, %xmm1
+; XOP-NEXT:    vmovdqa {{.*#+}} xmm2 = [0,0,255,0,0,0,255,0,0,255,255,255,255,255,255,255]
+; XOP-NEXT:    vpblendvb %xmm2, %xmm0, %xmm1, %xmm0
+; XOP-NEXT:    retq
+  %div = sdiv <16 x i8> %A, <i8 -1, i8 -1, i8 1, i8 -1, i8 -1, i8 -1, i8 1, i8 -1, i8 -1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1>
+  ret <16 x i8> %div
+}
+
+define <4 x i32> @non_splat_minus_one_divisor_1(<4 x i32> %A) {
+; SSE-LABEL: non_splat_minus_one_divisor_1:
+; SSE:       # %bb.0:
+; SSE-NEXT:    movdqa %xmm0, %xmm2
+; SSE-NEXT:    psrld $31, %xmm2
+; SSE-NEXT:    pxor %xmm3, %xmm3
+; SSE-NEXT:    pblendw {{.*#+}} xmm2 = xmm3[0,1,2,3],xmm2[4,5,6,7]
+; SSE-NEXT:    paddd %xmm0, %xmm2
+; SSE-NEXT:    movdqa %xmm2, %xmm1
+; SSE-NEXT:    psrad $1, %xmm1
+; SSE-NEXT:    pblendw {{.*#+}} xmm1 = xmm2[0,1,2,3],xmm1[4,5,6,7]
+; SSE-NEXT:    pblendw {{.*#+}} xmm1 = xmm0[0,1],xmm1[2,3,4,5,6,7]
+; SSE-NEXT:    psubd %xmm1, %xmm3
+; SSE-NEXT:    pblendw {{.*#+}} xmm1 = xmm3[0,1],xmm1[2,3,4,5],xmm3[6,7]
+; SSE-NEXT:    movdqa %xmm1, %xmm0
+; SSE-NEXT:    retq
+;
+; AVX1-LABEL: non_splat_minus_one_divisor_1:
+; AVX1:       # %bb.0:
+; AVX1-NEXT:    vpsrld $31, %xmm0, %xmm1
+; AVX1-NEXT:    vpxor %xmm2, %xmm2, %xmm2
+; AVX1-NEXT:    vpblendw {{.*#+}} xmm1 = xmm2[0,1,2,3],xmm1[4,5,6,7]
+; AVX1-NEXT:    vpaddd %xmm1, %xmm0, %xmm1
+; AVX1-NEXT:    vpsrad $1, %xmm1, %xmm3
+; AVX1-NEXT:    vpblendw {{.*#+}} xmm1 = xmm1[0,1,2,3],xmm3[4,5,6,7]
+; AVX1-NEXT:    vpblendw {{.*#+}} xmm0 = xmm0[0,1],xmm1[2,3,4,5,6,7]
+; AVX1-NEXT:    vpsubd %xmm0, %xmm2, %xmm1
+; AVX1-NEXT:    vpblendw {{.*#+}} xmm0 = xmm1[0,1],xmm0[2,3,4,5],xmm1[6,7]
+; AVX1-NEXT:    retq
+;
+; AVX2ORLATER-LABEL: non_splat_minus_one_divisor_1:
+; AVX2ORLATER:       # %bb.0:
+; AVX2ORLATER-NEXT:    vpsrad $31, %xmm0, %xmm1
+; AVX2ORLATER-NEXT:    vpsrlvd {{.*}}(%rip), %xmm1, %xmm1
+; AVX2ORLATER-NEXT:    vpaddd %xmm1, %xmm0, %xmm1
+; AVX2ORLATER-NEXT:    vpsravd {{.*}}(%rip), %xmm1, %xmm1
+; AVX2ORLATER-NEXT:    vpblendd {{.*#+}} xmm0 = xmm0[0],xmm1[1,2,3]
+; AVX2ORLATER-NEXT:    vpxor %xmm1, %xmm1, %xmm1
+; AVX2ORLATER-NEXT:    vpsubd %xmm0, %xmm1, %xmm1
+; AVX2ORLATER-NEXT:    vpblendd {{.*#+}} xmm0 = xmm1[0],xmm0[1,2],xmm1[3]
+; AVX2ORLATER-NEXT:    retq
+;
+; XOP-LABEL: non_splat_minus_one_divisor_1:
+; XOP:       # %bb.0:
+; XOP-NEXT:    vpsrad $31, %xmm0, %xmm1
+; XOP-NEXT:    vpshld {{.*}}(%rip), %xmm1, %xmm1
+; XOP-NEXT:    vpaddd %xmm1, %xmm0, %xmm1
+; XOP-NEXT:    vpshad {{.*}}(%rip), %xmm1, %xmm1
+; XOP-NEXT:    vpblendw {{.*#+}} xmm0 = xmm0[0,1],xmm1[2,3,4,5,6,7]
+; XOP-NEXT:    vpxor %xmm1, %xmm1, %xmm1
+; XOP-NEXT:    vpsubd %xmm0, %xmm1, %xmm1
+; XOP-NEXT:    vpblendw {{.*#+}} xmm0 = xmm1[0,1],xmm0[2,3,4,5],xmm1[6,7]
+; XOP-NEXT:    retq
+  %div = sdiv <4 x i32> %A, <i32 -1, i32 1, i32 2, i32 -2>
+  ret <4 x i32> %div
+}