[SLP]Fix emission of int division with some undef vector subelements.

[ABataev]

Summary

If it is legal and profitable to vectorize integer division operations
and some of the operands are undefs, need to replace these undefs in the
vector operands elements with some actual values. Otherwise, such
division operations will be replaced by the vector poison values in the
instcombiner. It leads to incorrect llvm ir per https://llvm.org/docs/LangRef.html#poisonvalues. According to this document "Vector elements may be independently poisoned. Therefore, transforms on instructions such as shufflevector must be careful to propagate poison across values or elements only as allowed by the original code."

[vporpo]

I am not sure I understand why you are trying to get rid of the undef operands. Could you provide a code example that shows the issue?

[lebedev.ri]

In D114375#3147241, @vporpo wrote:

I am not sure I understand why you are trying to get rid of the undef operands. Could you provide a code example that shows the issue?

+1

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

6

This is *NOT* a miscompile: https://alive2.llvm.org/ce/z/iMu-eF

[ABataev]

In D114375#3147241, @vporpo wrote:

I am not sure I understand why you are trying to get rid of the undef operands. Could you provide a code example that shows the issue?

The test test/Transforms/SLPVectorizer/X86/arith-div-undef.ll shows the problem. We have a gather of sdivs results, 2 of them are poisonous. And generally speaking, this gather shall end up with a vector <poison, sdiv1, sdiv2, sdiv3, poison, sdiv4, sdiv5, sdiv6>. But instead, the compiler generates just <8 x i32> poison. I think this result is more poisonous than the original one. Extract from lane 1, for example, should be different for these results.

Here is an example with just instcombiner https://godbolt.org/z/9rxesoM47

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

6

Yes, also checked it via alive but not sure if alive is correct here.

[lebedev.ri]

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

6

https://llvm.org/docs/LangRef.html#sdiv-instruction
"Division by zero is undefined behavior. For vectors,
if any element of the divisor is zero,
the operation has undefined behavior. "

https://alive2.llvm.org/ce/z/mZvBXL

[ABataev]

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

6

Yep, thought about this. But thought that a buildvector has different behavior. Probably here the whole program becomes UB after division by undef.

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

case Instruction::Xor: {
         reorderInputsAccordingToOpcode(VL, Left, Right, *DL, *SE, *this);
         TE->setOperand(0, Left);
         TE->setOperand(1, Right);
         buildTree_rec(Left, Depth + 1, {TE, 0});
         buildTree_rec(Right, Depth + 1, {TE, 1});
         return;
       }
 
-      TE->setOperandsInOrder();
-      for (unsigned i = 0, e = VL0->getNumOperands(); i < e; ++i) {
-        ValueList Operands;
+      SmallVector<ValueList> Operands(VL0->getNumOperands());
+      for (unsigned I = 0, Ops = VL0->getNumOperands(); I < Ops; ++I) {
+        Operands[I].reserve(VL.size());
         // Prepare the operand vector.
-        for (Value *V : VL)
-          Operands.push_back(cast<Instruction>(V)->getOperand(i));
-
-        buildTree_rec(Operands, Depth + 1, {TE, i});
+        for (Value *V : VL) {
+          auto *Op = cast<Instruction>(V)->getOperand(I);
+          if (isa<UndefValue>(Op) && BinaryOperator::isIntDivRem(ShuffleOrOp)) {
+            // Need to replace undefs with actual values for integer division
+            // operations, otherwise instcombiner transforms such instructions
+            // to poison values.
+            // Just try to find the first non-undef operand, if any, otherwise
+            // use undef if all values are undefs.
+            const auto *It = find_if(VL, [I](Value *V) {
+              return isa<Instruction>(V) &&
+                     !isa<UndefValue>(cast<Instruction>(V)->getOperand(I));
+            });
+            if (It != VL.end())
+              Op = cast<Instruction>(*It)->getOperand(I);
           }
+          Operands[I].push_back(Op);
+        }
+        TE->setOperand(I, Operands[I]);
+      }
+      for (unsigned I = 0, Ops = VL0->getNumOperands(); I < Ops; ++I)
+        buildTree_rec(Operands[I], Depth + 1, {TE, I});
       return;
     }
     case Instruction::GetElementPtr: {
       // We don't combine GEPs with complicated (nested) indexing.
       for (Value *V : VL) {
         if (cast<Instruction>(V)->getNumOperands() != 2) {
           LLVM_DEBUG(dbgs() << "SLP: not-vectorizable GEP (nested indexes).\n");
           BS.cancelScheduling(VL, VL0);

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:    [[TMP1:%.*]] = sdiv <8 x i32> [[A:%.*]], <i32 4, i32 4, i32 8, i32 16, i32 4, i32 4, i32 8, i32 16>
+; CHECK-NEXT:    ret <8 x i32> [[TMP1]]
 ;
   %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

llvm/test/Transforms/SLPVectorizer/X86/shrink_after_reorder2.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -o - -slp-vectorizer -mtriple=x86_64-unknown-linux-gnu < %s | FileCheck %s
 
 %class.e = type { i32, i32 }
 %struct.a = type { i32, i32, i32, i32 }
 
 define void @foo(%class.e* %this, %struct.a* %p, i32 %add7) {
 ; CHECK-LABEL: @foo(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[B:%.*]] = getelementptr inbounds [[STRUCT_A:%.*]], %struct.a* [[P:%.*]], i64 0, i32 0
 ; CHECK-NEXT:    [[C:%.*]] = getelementptr inbounds [[STRUCT_A]], %struct.a* [[P]], i64 0, i32 1
 ; CHECK-NEXT:    [[O:%.*]] = getelementptr inbounds [[STRUCT_A]], %struct.a* [[P]], i64 0, i32 2
 ; CHECK-NEXT:    [[D:%.*]] = getelementptr inbounds [[STRUCT_A]], %struct.a* [[P]], i64 0, i32 3
 ; CHECK-NEXT:    [[H:%.*]] = getelementptr inbounds [[CLASS_E:%.*]], %class.e* [[THIS:%.*]], i64 0, i32 1
 ; CHECK-NEXT:    [[G:%.*]] = getelementptr inbounds [[CLASS_E]], %class.e* [[THIS]], i64 0, i32 0
-; CHECK-NEXT:    [[TMP0:%.*]] = insertelement <2 x i32> <i32 poison, i32 undef>, i32 [[ADD7:%.*]], i32 0
-; CHECK-NEXT:    [[TMP1:%.*]] = sdiv <2 x i32> [[TMP0]], <i32 2, i32 2>
-; CHECK-NEXT:    [[SHUFFLE:%.*]] = shufflevector <2 x i32> [[TMP1]], <2 x i32> poison, <4 x i32> <i32 1, i32 1, i32 0, i32 0>
+; CHECK-NEXT:    [[TMP0:%.*]] = insertelement <2 x i32> poison, i32 [[ADD7:%.*]], i32 0
+; CHECK-NEXT:    [[TMP1:%.*]] = insertelement <2 x i32> [[TMP0]], i32 [[ADD7]], i32 1
+; CHECK-NEXT:    [[TMP2:%.*]] = sdiv <2 x i32> [[TMP1]], <i32 2, i32 2>
+; CHECK-NEXT:    [[SHUFFLE:%.*]] = shufflevector <2 x i32> [[TMP2]], <2 x i32> poison, <4 x i32> <i32 1, i32 1, i32 0, i32 0>
 ; CHECK-NEXT:    switch i32 undef, label [[SW_EPILOG:%.*]] [
 ; CHECK-NEXT:    i32 0, label [[SW_BB:%.*]]
 ; CHECK-NEXT:    i32 2, label [[SW_BB]]
 ; CHECK-NEXT:    ]
 ; CHECK:       sw.bb:
-; CHECK-NEXT:    [[TMP2:%.*]] = bitcast i32* [[G]] to <2 x i32>*
-; CHECK-NEXT:    [[TMP3:%.*]] = load <2 x i32>, <2 x i32>* [[TMP2]], align 4
+; CHECK-NEXT:    [[TMP3:%.*]] = bitcast i32* [[G]] to <2 x i32>*
+; CHECK-NEXT:    [[TMP4:%.*]] = load <2 x i32>, <2 x i32>* [[TMP3]], align 4
 ; CHECK-NEXT:    [[SHRINK_SHUFFLE:%.*]] = shufflevector <4 x i32> [[SHUFFLE]], <4 x i32> poison, <2 x i32> <i32 2, i32 0>
-; CHECK-NEXT:    [[TMP4:%.*]] = xor <2 x i32> [[SHRINK_SHUFFLE]], <i32 -1, i32 -1>
-; CHECK-NEXT:    [[TMP5:%.*]] = add <2 x i32> [[TMP3]], [[TMP4]]
+; CHECK-NEXT:    [[TMP5:%.*]] = xor <2 x i32> [[SHRINK_SHUFFLE]], <i32 -1, i32 -1>
+; CHECK-NEXT:    [[TMP6:%.*]] = add <2 x i32> [[TMP4]], [[TMP5]]
 ; CHECK-NEXT:    br label [[SW_EPILOG]]
 ; CHECK:       sw.epilog:
-; CHECK-NEXT:    [[TMP6:%.*]] = phi <2 x i32> [ undef, [[ENTRY:%.*]] ], [ [[TMP5]], [[SW_BB]] ]
-; CHECK-NEXT:    [[SHUFFLE1:%.*]] = shufflevector <2 x i32> [[TMP6]], <2 x i32> poison, <4 x i32> <i32 1, i32 1, i32 0, i32 0>
-; CHECK-NEXT:    [[TMP7:%.*]] = sub <4 x i32> poison, [[SHUFFLE]]
-; CHECK-NEXT:    [[TMP8:%.*]] = add <4 x i32> [[TMP7]], [[SHUFFLE1]]
-; CHECK-NEXT:    [[TMP9:%.*]] = bitcast i32* [[B]] to <4 x i32>*
-; CHECK-NEXT:    store <4 x i32> [[TMP8]], <4 x i32>* [[TMP9]], align 4
+; CHECK-NEXT:    [[TMP7:%.*]] = phi <2 x i32> [ undef, [[ENTRY:%.*]] ], [ [[TMP6]], [[SW_BB]] ]
+; CHECK-NEXT:    [[SHUFFLE1:%.*]] = shufflevector <2 x i32> [[TMP7]], <2 x i32> poison, <4 x i32> <i32 1, i32 1, i32 0, i32 0>
+; CHECK-NEXT:    [[TMP8:%.*]] = sub <4 x i32> poison, [[SHUFFLE]]
+; CHECK-NEXT:    [[TMP9:%.*]] = add <4 x i32> [[TMP8]], [[SHUFFLE1]]
+; CHECK-NEXT:    [[TMP10:%.*]] = bitcast i32* [[B]] to <4 x i32>*
+; CHECK-NEXT:    store <4 x i32> [[TMP9]], <4 x i32>* [[TMP10]], align 4
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %b = getelementptr inbounds %struct.a, %struct.a* %p, i64 0, i32 0
   %c = getelementptr inbounds %struct.a, %struct.a* %p, i64 0, i32 1
   %o = getelementptr inbounds %struct.a, %struct.a* %p, i64 0, i32 2
   %d = getelementptr inbounds %struct.a, %struct.a* %p, i64 0, i32 3
   %h = getelementptr inbounds %class.e, %class.e* %this, i64 0, i32 1