[DAG] SelectionDAG::getNode(N1,N2) - detect N2 constant vector splats as well as scalars

[RKSimon]

Summary

We already perform some basic folds (add/sub with zero etc.) on scalar types, this patch adds some basic support for constant splats as well in a few cases (we can add more with future test coverage).

In the cases I've enabled, we can handle buildvector implicit truncation as we're not creating new constant nodes from the vector types - we're just returning existing nodes. This allows us to get a number of extra cases in the aarch64 tests.

I haven't enabled support for undefs in buildvector splats, as we're often checking for zero/allones patterns that return the original constant and we shouldn't be returning undef elements in some of these cases - we can enable this later if we're OK with creating new constants.

[craig.topper]

llvm/test/CodeGen/AArch64/neon-bitwise-instructions.ll

825

Checking my understanding. This happened before because vselect expansion created twos Ands and an Or. One of the Ands constant folded immediately. Then custom legalization for Or created a special AArch64ISD::ORRi. This all occurred inside of legalize vector ops.

There's no DAG combine for AArch64ISD::ORRi to catch this after legalize vector ops.

Your patch fixes this because the Or will be simplified when it is created.

[RKSimon]

llvm/test/CodeGen/AArch64/neon-bitwise-instructions.ll

825

That matches what I think is going on as well - in all the cases here, by avoiding creating an unnecessary node, we're changing the order of node evaluation just enough to stop getting caught in a deadend.

This is a preliminary fix necessary to improve PTEST codgen where we're failing to fold the PCMPEQ(X,0) -> SUB(X,0) -> X in time.

[craig.topper]

LGTM

[david-arm]

llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp

5634

I wonder if this is also not canonicalising constant vector splats to the RHS as well? Not saying you should fix this in your patch though - its just an observation!

[craig.topper]

llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp

5634

Despite it's name it does handle ISD::SPLAT_VECTOR. Is that what you meant?

[david-arm]

llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp

5634

Yeah. Oh well that's a bit confusing then. :(

[vitalybuka]

llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp

5649

@RKSimon After this patch we see something that appears false msan report

cc @eugenis

We have a basic block

182:                                              ; preds = %82
  %183 = call <32 x i16> @llvm.x86.avx512.packusdw.512(<16 x i32> %176, <16 x i32> poison) #28, !dbg !276
  %184 = and <32 x i16> %183, zeroinitializer, !dbg !277
  %185 = or <32 x i16> zeroinitializer, %184, !dbg !277
  %186 = or <32 x i16> %185, <i16 0, i16 0, i16 0, i16 0, i16 poison, i16 poison, i16 poison, i16 poison, i16 0, i16 0, i16 0, i16 0, i16 poison, i16 poison, i16 poison, i16 poison, i16 0, i16 0, i16 0, i16 0, i16 poison, i16 poison, i16 poison, i16 poison, i16 0, i16 0, i16 0, i16 0, i16 poison, i16 poison, i16 poison, i16 poison>, !dbg !277
  %187 = and <32 x i16> %183, <i16 32767, i16 32767, i16 32767, i16 32767, i16 poison, i16 poison, i16 poison, i16 poison, i16 32767, i16 32767, i16 32767, i16 32767, i16 poison, i16 poison, i16 poison, i16 poison, i16 32767, i16 32767, i16 32767, i16 32767, i16 poison, i16 poison, i16 poison, i16 poison, i16 32767, i16 32767, i16 32767, i16 32767, i16 poison, i16 poison, i16 poison, i16 poison>, !dbg !277
  %188 = bitcast <32 x i16> %186 to i512, !dbg !277
  %_mscmp34 = icmp ne i512 %188, 0, !dbg !277
  br i1 %_mscmp34, label %189, label %190, !dbg !277, !prof !27

before the patch

bb.4 (%ir-block.182):
; predecessors: %bb.2
  successors: %bb.5, %bb.6

  %291:vr512 = IMPLICIT_DEF
  %290:vr512 = VPACKUSDWZrr %1:vr512, killed %291:vr512, debug-location !276; ./third_party/highway/hwy/ops/x86_512-inl.h:3056:30 @[ ./third_party/highway/hwy/examples/skeleton.cc:62:18 ]
  %292:vr512 = VMOVDQA64Zrm $rip, 1, $noreg, %const.1, $noreg, debug-location !277 :: (load (s512) from constant-pool); ./third_party/highway/hwy/ops/x86_512-inl.h:3066:29 @[ ./third_party/highway/hwy/examples/skeleton.cc:62:18 ]
  %2:vr512 = VPANDQZrr killed %290:vr512, killed %292:vr512, debug-location !277; ./third_party/highway/hwy/ops/x86_512-inl.h:3066:29 @[ ./third_party/highway/hwy/examples/skeleton.cc:62:18 ]
  %293:gr8 = MOV8ri 1
  TEST8rr %293:gr8, %293:gr8, implicit-def $eflags, debug-location !277; ./third_party/highway/hwy/ops/x86_512-inl.h:3066:29 @[ ./third_party/highway/hwy/examples/skeleton.cc:62:18 ]
  JCC_1 %bb.6, 5, implicit $eflags, debug-location !277; ./third_party/highway/hwy/ops/x86_512-inl.h:3066:29 @[ ./third_party/highway/hwy/examples/skeleton.cc:62:18 ]
  JMP_1 %bb.5, debug-location !277; ./third_party/highway/hwy/ops/x86_512-inl.h:3066:29 @[ ./third_party/highway/hwy/examples/skeleton.cc:62:18 ]

now it's

bb.4 (%ir-block.182):
; predecessors: %bb.2
  successors: %bb.5, %bb.6

  %291:vr512 = IMPLICIT_DEF
  %290:vr512 = VPACKUSDWZrr %1:vr512, killed %291:vr512, debug-location !276; ./third_party/highway/hwy/ops/x86_512-inl.h:3056:30 @[ ./third_party/highway/hwy/examples/skeleton.cc:62:18 ]
  %292:vr512 = VMOVDQA64Zrm $rip, 1, $noreg, %const.1, $noreg, debug-location !277 :: (load (s512) from constant-pool); ./third_party/highway/hwy/ops/x86_512-inl.h:3066:29 @[ ./third_party/highway/hwy/examples/skeleton.cc:62:18 ]
  %2:vr512 = VPANDQZrr killed %290:vr512, killed %292:vr512, debug-location !277; ./third_party/highway/hwy/ops/x86_512-inl.h:3066:29 @[ ./third_party/highway/hwy/examples/skeleton.cc:62:18 ]
  %293:gr32 = MOV32r0 implicit-def dead $eflags
  %294:gr8 = COPY %293.sub_8bit:gr32
  TEST8rr %294:gr8, %294:gr8, implicit-def $eflags, debug-location !277; ./third_party/highway/hwy/ops/x86_512-inl.h:3066:29 @[ ./third_party/highway/hwy/examples/skeleton.cc:62:18 ]
  JCC_1 %bb.6, 5, implicit $eflags, debug-location !277; ./third_party/highway/hwy/ops/x86_512-inl.h:3066:29 @[ ./third_party/highway/hwy/examples/skeleton.cc:62:18 ]
  JMP_1 %bb.5, debug-location !277; ./third_party/highway/hwy/ops/x86_512-inl.h:3066:29 @[ ./third_party/highway/hwy/examples/skeleton.cc:62:18 ]

[RKSimon]

@vitalybuka Do you have a better repro? I can't tell from your post whether its something to do with this patch or its just unearthed another existing issue

[RKSimon]

What we might have done is uncovered an existing inconsistency with or with undef folding: https://gcc.godbolt.org/z/e6aPfe3Ye which effects later folds, such as the bitcasting (bitcast <32 x i16> to i512).

define i64 @xx(<2 x i64> %a0) {
  %s = sub <2 x i64> %a0, %a0
  %r = or <2 x i64> <i64 0, i64 undef>, %s
  %x = extractelement <2 x i64> %r, i32 1
  ret i64 %x
}

instcombine:
define i64 @xx(<2 x i64> %a0) {
  ret i64 undef
}

llc:
xx:
        movq    $-1, %rax
        retq

[RKSimon]

@vitalybuka Any luck with a repro?

[vitalybuka]

In D118264#3324337, @RKSimon wrote:

@vitalybuka Any luck with a repro?

Sorry, busy with other stuff. I'll reply today.
I assume IR is needed, not source c++?

[vitalybuka]

In D118264#3324337, @RKSimon wrote:

@vitalybuka Any luck with a repro?

Repro is here https://reviews.llvm.org/P8280

[RKSimon]

In D118264#3324466, @vitalybuka wrote:

In D118264#3324337, @RKSimon wrote:

@vitalybuka Any luck with a repro?

Sorry, busy with other stuff. I'll reply today.
I assume IR is needed, not source c++?

I can investigate the change in folding in the DAG, but what I'm particularly interested in is how we ended up with %235 - the vector OR with a constant-with-poison - that then gets bitcast to a i512 scalar for a comparison. I'm assuming a SimplifyDemandedVectorElts call or something?

	231:                                              ; preds = %115
	  %232 = call <32 x i16> @llvm.x86.avx512.packusdw.512(<16 x i32> %223, <16 x i32> poison) #14
	  %233 = and <32 x i16> %232, zeroinitializer
	  %234 = or <32 x i16> zeroinitializer, %233
	  %235 = or <32 x i16> %234, <i16 0, i16 0, i16 0, i16 0, i16 poison, i16 poison, i16 poison, i16 poison, i16 0, i16 0, i16 0, i16 0, i16 poison, i16 poison, i16 poison, i16 poison, i16 0, i16 0, i16 0, i16 0, i16 poison, i16 poison, i16 poison, i16 poison, i16 0, i16 0, i16 0, i16 0, i16 poison, i16 poison, i16 poison, i16 poison>
	  %236 = and <32 x i16> %232, <i16 32767, i16 32767, i16 32767, i16 32767, i16 poison, i16 poison, i16 poison, i16 poison, i16 32767, i16 32767, i16 32767, i16 32767, i16 poison, i16 poison, i16 poison, i16 poison, i16 32767, i16 32767, i16 32767, i16 32767, i16 poison, i16 poison, i16 poison, i16 poison, i16 32767, i16 32767, i16 32767, i16 32767, i16 poison, i16 poison, i16 poison, i16 poison>
	  %237 = bitcast <32 x i16> %235 to i512
	  %238 = icmp ne i512 %237, 0
	  br i1 %238, label %239, label %240, !prof !10

[RKSimon]

@vitalybuka I've raised https://github.com/llvm/llvm-project/issues/53901 to investigate this

llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp

 
 SDValue SelectionDAG::getNode(unsigned Opcode, const SDLoc &DL, EVT VT,
                               SDValue N1, SDValue N2, const SDNodeFlags Flags) {
   assert(N1.getOpcode() != ISD::DELETED_NODE &&
          N2.getOpcode() != ISD::DELETED_NODE &&
          "Operand is DELETED_NODE!");
   // Canonicalize constant to RHS if commutative.
   if (TLI->isCommutativeBinOp(Opcode)) {
     bool IsN1C = isConstantIntBuildVectorOrConstantInt(N1);
     bool IsN2C = isConstantIntBuildVectorOrConstantInt(N2);
     bool IsN1CFP = isConstantFPBuildVectorOrConstantFP(N1);
     bool IsN2CFP = isConstantFPBuildVectorOrConstantFP(N2);
     if ((IsN1C && !IsN2C) || (IsN1CFP && !IsN2CFP))
       std::swap(N1, N2);
   }
 
-  ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
-  ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2);
+  auto *N1C = dyn_cast<ConstantSDNode>(N1);
+  auto *N2C = dyn_cast<ConstantSDNode>(N2);
+
+  // Don't allow undefs in vector splats - we might be returning N2 when folding
+  // to zero etc.
+  ConstantSDNode *N2CV =
+      isConstOrConstSplat(N2, /*AllowUndefs*/ false, /*AllowTruncation*/ true);
 
   switch (Opcode) {
   default: break;
   case ISD::TokenFactor:
     assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
            N2.getValueType() == MVT::Other && "Invalid token factor!");
     // Fold trivial token factors.
     if (N1.getOpcode() == ISD::EntryToken) return N2;
     if (N2.getOpcode() == ISD::EntryToken) return N1;
case ISD::CONCAT_VECTORS: {
     break;
   }
   case ISD::AND:
     assert(VT.isInteger() && "This operator does not apply to FP types!");
     assert(N1.getValueType() == N2.getValueType() &&
            N1.getValueType() == VT && "Binary operator types must match!");
     // (X & 0) -> 0.  This commonly occurs when legalizing i64 values, so it's
     // worth handling here.
-    if (N2C && N2C->isZero())
+    if (N2CV && N2CV->isZero())
       return N2;
-    if (N2C && N2C->isAllOnes()) // X & -1 -> X
+    if (N2CV && N2CV->isAllOnes()) // X & -1 -> X
       return N1;
     break;
   case ISD::OR:
   case ISD::XOR:
   case ISD::ADD:
   case ISD::SUB:
     assert(VT.isInteger() && "This operator does not apply to FP types!");
     assert(N1.getValueType() == N2.getValueType() &&
            N1.getValueType() == VT && "Binary operator types must match!");
     // (X ^|+- 0) -> X.  This commonly occurs when legalizing i64 values, so
     // it's worth handling here.
-    if (N2C && N2C->isZero())
+    if (N2CV && N2CV->isZero())
       return N1;
     if ((Opcode == ISD::ADD || Opcode == ISD::SUB) && VT.isVector() &&
         VT.getVectorElementType() == MVT::i1)
       return getNode(ISD::XOR, DL, VT, N1, N2);
     break;
   case ISD::MUL:
     assert(VT.isInteger() && "This operator does not apply to FP types!");
     assert(N1.getValueType() == N2.getValueType() &&
assert(N2.getValueType().getScalarSizeInBits() >=
                Log2_32_Ceil(VT.getScalarSizeInBits()) &&
            "Invalid use of small shift amount with oversized value!");
 
     // Always fold shifts of i1 values so the code generator doesn't need to
     // handle them.  Since we know the size of the shift has to be less than the
     // size of the value, the shift/rotate count is guaranteed to be zero.
     if (VT == MVT::i1)
       return N1;
-    if (N2C && N2C->isZero())
+    if (N2CV && N2CV->isZero())
       return N1;
     break;
   case ISD::FP_ROUND:
     assert(VT.isFloatingPoint() &&
            N1.getValueType().isFloatingPoint() &&
            VT.bitsLE(N1.getValueType()) &&
            N2C && (N2C->getZExtValue() == 0 || N2C->getZExtValue() == 1) &&
            "Invalid FP_ROUND!");

llvm/test/CodeGen/AArch64/neon-bitwise-instructions.ll

; CHECK-NEXT:    ret
   ret <4 x i32> %4
 }
 
 define <8 x i8> @vselect_constant_cond_zero_v8i8(<8 x i8> %a) {
 ; CHECK-LABEL: vselect_constant_cond_zero_v8i8:
 ; CHECK:       // %bb.0:
 ; CHECK-NEXT:    movi d1, #0x00000000ff00ff
 ; CHECK-NEXT:    and v0.8b, v0.8b, v1.8b
-; CHECK-NEXT:    orr v0.2s, #0
 ; CHECK-NEXT:    ret
   %b = select <8 x i1> <i1 true, i1 false, i1 true, i1 false, i1 false, i1 false, i1 false, i1 false>, <8 x i8> %a, <8 x i8> zeroinitializer
   ret <8 x i8> %b
 }
 
 define <4 x i16> @vselect_constant_cond_zero_v4i16(<4 x i16> %a) {
 ; CHECK-LABEL: vselect_constant_cond_zero_v4i16:
 ; CHECK:       // %bb.0:
 ; CHECK-NEXT:    movi d1, #0xffff00000000ffff
 ; CHECK-NEXT:    and v0.8b, v0.8b, v1.8b
-; CHECK-NEXT:    orr v0.2s, #0
 ; CHECK-NEXT:    ret
   %b = select <4 x i1> <i1 true, i1 false, i1 false, i1 true>, <4 x i16> %a, <4 x i16> zeroinitializer
   ret <4 x i16> %b
 }
 
 define <4 x i32> @vselect_constant_cond_zero_v4i32(<4 x i32> %a) {
 ; CHECK-LABEL: vselect_constant_cond_zero_v4i32:
 ; CHECK:       // %bb.0:
 ; CHECK-NEXT:    adrp x8, .LCPI85_0
 ; CHECK-NEXT:    ldr q1, [x8, :lo12:.LCPI85_0]
 ; CHECK-NEXT:    and v0.16b, v0.16b, v1.16b
-; CHECK-NEXT:    orr v0.4s, #0
 ; CHECK-NEXT:    ret
   %b = select <4 x i1> <i1 true, i1 false, i1 false, i1 true>, <4 x i32> %a, <4 x i32> zeroinitializer
   ret <4 x i32> %b
 }
 
 define <8 x i8> @vselect_constant_cond_v8i8(<8 x i8> %a, <8 x i8> %b) {
 ; CHECK-LABEL: vselect_constant_cond_v8i8:
 ; CHECK:       // %bb.0:

llvm/test/CodeGen/ARM/2013-07-29-vector-or-combine.ll

 ; RUN: llc < %s -mcpu=cortex-a8 -arm-atomic-cfg-tidy=0 | FileCheck %s
 ; ModuleID = 'bugpoint-reduced-simplified.bc'
 target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:64:128-a0:0:64-n32-S64"
 target triple = "armv7--linux-gnueabi"
 
 ; CHECK-LABEL: function
 define void @function() {
 ; CHECK: cmp r0, #0
 ; CHECK: bxne lr
-; CHECK: vmov.i32 q8, #0xff0000
 entry:
   br i1 undef, label %vector.body, label %for.end
 
-; CHECK: vld1.32 {d18, d19}, [r0]
-; CHECK: vand q10, q9, q8
-; CHECK: vbic.i16 q9, #0xff
-; CHECK: vorr q9, q9, q10
-; CHECK: vst1.32 {d18, d19}, [r0]
+; CHECK: vld1.32 {d16, d17}, [r0]
+; CHECK: vbic.i32 q8, #0xff
+; CHECK: vorr q8, q8, q9
+; CHECK: vst1.32 {d16, d17}, [r0]
 vector.body:
   %wide.load = load <4 x i32>, <4 x i32>* undef, align 4
   %0 = and <4 x i32> %wide.load, <i32 -16711936, i32 -16711936, i32 -16711936, i32 -16711936>
   %1 = sub <4 x i32> %wide.load, zeroinitializer
   %2 = and <4 x i32> %1, <i32 16711680, i32 16711680, i32 16711680, i32 16711680>
   %3 = or <4 x i32> %0, <i32 1, i32 2, i32 3, i32 4>
   %4 = or <4 x i32> %3, %2
   store <4 x i32> %4, <4 x i32>* undef, align 4
   br label %vector.body
 
 for.end:
   ret void
 }
 

llvm/test/CodeGen/X86/vec_smulo.ll

 ; SSE41-NEXT:    movmskps %xmm0, %eax
 ; SSE41-NEXT:    psrad $31, %xmm0
 ; SSE41-NEXT:    movb %al, (%rdi)
 ; SSE41-NEXT:    retq
 ;
 ; AVX-LABEL: smulo_v4i1:
 ; AVX:       # %bb.0:
 ; AVX-NEXT:    vpand %xmm1, %xmm0, %xmm0
-; AVX-NEXT:    vpslld $31, %xmm0, %xmm0
-; AVX-NEXT:    vmovmskps %xmm0, %eax
-; AVX-NEXT:    vpsrad $31, %xmm0, %xmm0
+; AVX-NEXT:    vpslld $31, %xmm0, %xmm1
+; AVX-NEXT:    vpsrad $31, %xmm1, %xmm0
+; AVX-NEXT:    vmovmskps %xmm1, %eax
 ; AVX-NEXT:    movb %al, (%rdi)
 ; AVX-NEXT:    retq
 ;
 ; AVX512F-LABEL: smulo_v4i1:
 ; AVX512F:       # %bb.0:
 ; AVX512F-NEXT:    vpand %xmm1, %xmm0, %xmm0
 ; AVX512F-NEXT:    vpslld $31, %xmm0, %xmm0
 ; AVX512F-NEXT:    vptestmd %xmm0, %xmm0, %k0