[SLP] Don't vectorize div/rem with undef denominators

[RKSimon]

Summary

If any of the elements contains a DIV/REM node that is likely to fold to undef, then don't vectorize with it as it'll poison the entire vector.

I'm not certain if this IR can actually occur going into SLP or not, but we have tests for it, and I encountered further cases while altering the costs to try and fix the regressions in D111968.

[lebedev.ri]

llvm/test/Transforms/SLPVectorizer/X86/arith-div-undef.ll

16

This is an immediate UB https://alive2.llvm.org/ce/z/uKOdmW

[lebedev.ri]

llvm/test/Transforms/SLPVectorizer/X86/arith-div-undef.ll

16

(better link: https://alive2.llvm.org/ce/z/oD8gjC)

[RKSimon]

llvm/test/Transforms/SLPVectorizer/X86/arith-div-undef.ll

16

Although https://alive2.llvm.org/ce/z/ma3VyM shows that this patch isn't incorrect either

[lebedev.ri]

llvm/test/Transforms/SLPVectorizer/X86/arith-div-undef.ll

16

Sure, like with all UB we are free to make any refinement to the UB.
My comment is that this test case is just broken and can be optimized into system("dd if=/dev/zero of=/dev/sda");.

[ABataev]

llvm/test/Transforms/SLPVectorizer/X86/arith-div-undef.ll

16

I think we can just terminate SLP pass in this case

[lebedev.ri]

This review seems to be stuck/dead, consider abandoning if no longer relevant.

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

case Instruction::FCmp: {
         }
       }
       TE->setOperand(0, Left);
       TE->setOperand(1, Right);
       buildTree_rec(Left, Depth + 1, {TE, 0});
       buildTree_rec(Right, Depth + 1, {TE, 1});
       return;
     }
+    case Instruction::UDiv:
+    case Instruction::SDiv:
+    case Instruction::URem:
+    case Instruction::SRem: {
+      if (any_of(VL, [](Value *V) {
+            return isa<UndefValue>(cast<Instruction>(V)->getOperand(1));
+          })) {
+        BS.cancelScheduling(VL, VL0);
+        newTreeEntry(VL, None /*not vectorized*/, S, UserTreeIdx,
+                     ReuseShuffleIndicies);
+        LLVM_DEBUG(dbgs() << "SLP: DIV/REM contains UNDEF denominators.\n");
+        return;
+      }
+      LLVM_FALLTHROUGH;
+    }
     case Instruction::Select:
     case Instruction::FNeg:
     case Instruction::Add:
     case Instruction::FAdd:
     case Instruction::Sub:
     case Instruction::FSub:
     case Instruction::Mul:
     case Instruction::FMul:
-    case Instruction::UDiv:
-    case Instruction::SDiv:
     case Instruction::FDiv:
-    case Instruction::URem:
-    case Instruction::SRem:
     case Instruction::FRem:
     case Instruction::Shl:
     case Instruction::LShr:
     case Instruction::AShr:
     case Instruction::And:
     case Instruction::Or:
     case Instruction::Xor: {
       TreeEntry *TE = newTreeEntry(VL, Bundle /*vectorized*/, S, UserTreeIdx,

llvm/test/Transforms/SLPVectorizer/X86/arith-div-undef.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -mtriple=x86_64-unknown -slp-vectorizer -instcombine -S -slp-threshold=-10000 | FileCheck %s
 
 define <8 x i32> @sdiv_v8i32_undefs(<8 x i32> %a) {
 ; CHECK-LABEL: @sdiv_v8i32_undefs(
-; CHECK-NEXT:    ret <8 x i32> poison
+; CHECK-NEXT:    [[A1:%.*]] = extractelement <8 x i32> [[A:%.*]], i32 1
+; CHECK-NEXT:    [[A5:%.*]] = extractelement <8 x i32> [[A]], i32 5
+; CHECK-NEXT:    [[AB1:%.*]] = sdiv i32 [[A1]], 4
+; CHECK-NEXT:    [[TMP1:%.*]] = shufflevector <8 x i32> [[A]], <8 x i32> undef, <2 x i32> <i32 2, i32 3>
+; CHECK-NEXT:    [[TMP2:%.*]] = sdiv <2 x i32> [[TMP1]], <i32 8, i32 16>
+; CHECK-NEXT:    [[AB5:%.*]] = sdiv i32 [[A5]], 4
+; CHECK-NEXT:    [[TMP3:%.*]] = shufflevector <8 x i32> [[A]], <8 x i32> undef, <2 x i32> <i32 6, i32 7>
+; CHECK-NEXT:    [[TMP4:%.*]] = sdiv <2 x i32> [[TMP3]], <i32 8, i32 16>
+; CHECK-NEXT:    [[R1:%.*]] = insertelement <8 x i32> poison, i32 [[AB1]], i32 1
+; CHECK-NEXT:    [[TMP5:%.*]] = shufflevector <2 x i32> [[TMP2]], <2 x i32> poison, <8 x i32> <i32 0, i32 1, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef>
+; CHECK-NEXT:    [[R32:%.*]] = shufflevector <8 x i32> [[R1]], <8 x i32> [[TMP5]], <8 x i32> <i32 undef, i32 1, i32 8, i32 9, i32 undef, i32 undef, i32 undef, i32 undef>
+; CHECK-NEXT:    [[R5:%.*]] = insertelement <8 x i32> [[R32]], i32 [[AB5]], i32 5
+; CHECK-NEXT:    [[TMP6:%.*]] = shufflevector <2 x i32> [[TMP4]], <2 x i32> poison, <8 x i32> <i32 0, i32 1, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef>
+; CHECK-NEXT:    [[R71:%.*]] = shufflevector <8 x i32> [[R5]], <8 x i32> [[TMP6]], <8 x i32> <i32 undef, i32 1, i32 2, i32 3, i32 undef, i32 5, i32 8, i32 9>
+; CHECK-NEXT:    ret <8 x i32> [[R71]]
 ;
   %a0 = extractelement <8 x i32> %a, i32 0
   %a1 = extractelement <8 x i32> %a, i32 1
   %a2 = extractelement <8 x i32> %a, i32 2
   %a3 = extractelement <8 x i32> %a, i32 3
   %a4 = extractelement <8 x i32> %a, i32 4
   %a5 = extractelement <8 x i32> %a, i32 5
   %a6 = extractelement <8 x i32> %a, i32 6
   %a7 = extractelement <8 x i32> %a, i32 7
   %ab0 = sdiv i32 %a0, undef
   %ab1 = sdiv i32 %a1, 4
   %ab2 = sdiv i32 %a2, 8
   %ab3 = sdiv i32 %a3, 16
   %ab4 = sdiv i32 %a4, undef
   %ab5 = sdiv i32 %a5, 4
   %ab6 = sdiv i32 %a6, 8
   %ab7 = sdiv i32 %a7, 16
   %r0 = insertelement <8 x i32> poison, i32 %ab0, i32 0