[SLP] Don't allow Div/Rem as alternate opcodes

[a.elovikov]

Summary

We don't have control/verify what will be the RHS of the division, so it might
happen to be zero, causing UB.

[ABataev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

427–429

Do you really need it here? It does not check anything for casts.

[vporpo]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

414–415

Does this cover the case where VL[0] is invalid? Maybe add a test for it?

[a.elovikov]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

427–429

If that helper routine was checking for casts, I would have placed the call to it into the condition on line 426, similar to the check on line 414. But since it doesn't, there is no reason to do that there. On the other hand, if later some cast would become invalid, that condition on line 426 must be changed and the assert states exactly that.

In other words, this assert verifies exactly that - the check does not list casts as invalid.

[a.elovikov]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

414–415

I believe the second function in the LIT test verifies that - I have urem in the index 0 there.

[ABataev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

386

What about float point ops?

[a.elovikov]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

386

FP subclasses of llvm::Instruction rely on default floating point environment, so shouldn't throw. If FP operation can produce a signaling NaN it should be represented as constrained intrinsic (via CallInst), which I doubt is handled in this file and should probably bailout for other reasons earlier. At least, I don't see calls to TLI->isFunctionVectorizable in this file.

As such, I'm not aware of any existing issues in this regard. I'll be happy to update the code if you can point me which ones aren't valid and why.

[ABataev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

386

I was just asking if you're sure about it - fine.

[RKSimon]

This (and D72739) should be in 10.0 - please can you raise a bug and block https://bugs.llvm.org/show_bug.cgi?id=44555

[a.elovikov]

In D72740#1822003, @RKSimon wrote:

This (and D72739) should be in 10.0 - please can you raise a bug and block https://bugs.llvm.org/show_bug.cgi?id=44555

Submitted https://bugs.llvm.org/show_bug.cgi?id=44559 and blocked https://bugs.llvm.org/show_bug.cgi?id=44555 with it.

[a.elovikov]

Ping. I don't see any comments that require action on my side.

[ABataev]

LG

[hans]

Cherry-picked to 10.x in 029140ee1ca99e23558c774bb23257a4ea796069

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

 /// OpValue.
 static Value *isOneOf(const InstructionsState &S, Value *Op) {
   auto *I = dyn_cast<Instruction>(Op);
   if (I && S.isOpcodeOrAlt(I))
     return Op;
   return S.OpValue;
 }
 
+/// \returns true if \p Opcode is allowed as part of of the main/alternate
+/// instruction for SLP vectorization.
+///
+/// Example of unsupported opcode is SDIV that can potentially cause UB if the
+/// "shuffled out" lane would result in division by zero.
+static bool isValidForAlternation(unsigned Opcode) {
+  if (Instruction::isIntDivRem(Opcode))
+    return false;
+
+  return true;
+}
+
 /// \returns analysis of the Instructions in \p VL described in
 /// InstructionsState, the Opcode that we suppose the whole list
 /// could be vectorized even if its structure is diverse.
 static InstructionsState getSameOpcode(ArrayRef<Value *> VL,
                                        unsigned BaseIndex = 0) {
   // Make sure these are all Instructions.
   if (llvm::any_of(VL, [](Value *V) { return !isa<Instruction>(V); }))
     return InstructionsState(VL[BaseIndex], nullptr, nullptr);
 
   bool IsCastOp = isa<CastInst>(VL[BaseIndex]);
   bool IsBinOp = isa<BinaryOperator>(VL[BaseIndex]);
   unsigned Opcode = cast<Instruction>(VL[BaseIndex])->getOpcode();
   unsigned AltOpcode = Opcode;
   unsigned AltIndex = BaseIndex;
 
   // Check for one alternate opcode from another BinaryOperator.
   // TODO - generalize to support all operators (types, calls etc.).
   for (int Cnt = 0, E = VL.size(); Cnt < E; Cnt++) {
     unsigned InstOpcode = cast<Instruction>(VL[Cnt])->getOpcode();
     if (IsBinOp && isa<BinaryOperator>(VL[Cnt])) {
       if (InstOpcode == Opcode || InstOpcode == AltOpcode)
         continue;
-      if (Opcode == AltOpcode) {
+      if (Opcode == AltOpcode && isValidForAlternation(InstOpcode) &&
+          isValidForAlternation(Opcode)) {
         AltOpcode = InstOpcode;
         AltIndex = Cnt;
         continue;
       }
     } else if (IsCastOp && isa<CastInst>(VL[Cnt])) {
       Type *Ty0 = cast<Instruction>(VL[BaseIndex])->getOperand(0)->getType();
       Type *Ty1 = cast<Instruction>(VL[Cnt])->getOperand(0)->getType();
       if (Ty0 == Ty1) {
         if (InstOpcode == Opcode || InstOpcode == AltOpcode)
           continue;
         if (Opcode == AltOpcode) {
+          assert(isValidForAlternation(Opcode) &&
+                 isValidForAlternation(InstOpcode) &&
+                 "Cast isn't safe for alternation, logic needs to be updated!");
           AltOpcode = InstOpcode;
           AltIndex = Cnt;
           continue;
         }
       }
     } else if (InstOpcode == Opcode || InstOpcode == AltOpcode)
       continue;
     return InstructionsState(VL[BaseIndex], nullptr, nullptr);

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

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -slp-vectorizer -slp-threshold=-200 -mtriple=x86_64-unknown-linux -mcpu=core-avx2 -S | FileCheck %s
 
 define void @test_add_sdiv(i32 *%arr1, i32 *%arr2, i32 %a0, i32 %a1, i32 %a2, i32 %a3) {
 ; CHECK-LABEL: @test_add_sdiv(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[GEP1_0:%.*]] = getelementptr i32, i32* [[ARR1:%.*]], i32 0
 ; CHECK-NEXT:    [[GEP1_1:%.*]] = getelementptr i32, i32* [[ARR1]], i32 1
 ; CHECK-NEXT:    [[GEP1_2:%.*]] = getelementptr i32, i32* [[ARR1]], i32 2
 ; CHECK-NEXT:    [[GEP1_3:%.*]] = getelementptr i32, i32* [[ARR1]], i32 3
 ; CHECK-NEXT:    [[GEP2_0:%.*]] = getelementptr i32, i32* [[ARR2:%.*]], i32 0
 ; CHECK-NEXT:    [[GEP2_1:%.*]] = getelementptr i32, i32* [[ARR2]], i32 1
 ; CHECK-NEXT:    [[GEP2_2:%.*]] = getelementptr i32, i32* [[ARR2]], i32 2
 ; CHECK-NEXT:    [[GEP2_3:%.*]] = getelementptr i32, i32* [[ARR2]], i32 3
-; CHECK-NEXT:    [[TMP0:%.*]] = bitcast i32* [[GEP1_0]] to <4 x i32>*
-; CHECK-NEXT:    [[TMP1:%.*]] = load <4 x i32>, <4 x i32>* [[TMP0]], align 4
-; CHECK-NEXT:    [[TMP2:%.*]] = insertelement <4 x i32> undef, i32 [[A0:%.*]], i32 0
-; CHECK-NEXT:    [[TMP3:%.*]] = insertelement <4 x i32> [[TMP2]], i32 [[A1:%.*]], i32 1
-; CHECK-NEXT:    [[TMP4:%.*]] = insertelement <4 x i32> [[TMP3]], i32 [[A2:%.*]], i32 2
-; CHECK-NEXT:    [[TMP5:%.*]] = insertelement <4 x i32> [[TMP4]], i32 [[A3:%.*]], i32 3
-; CHECK-NEXT:    [[TMP6:%.*]] = add nsw <4 x i32> [[TMP5]], <i32 1146, i32 146, i32 42, i32 0>
-; CHECK-NEXT:    [[TMP7:%.*]] = add nsw <4 x i32> [[TMP1]], [[TMP6]]
-
-;; FIXME: Last lane of TMP6 may contain zero (if %a3 is zero). In such case, the
-;; next instruction would cause division by zero resulting in SIGFPE during
-;; execution.
-; CHECK-NEXT:    [[TMP8:%.*]] = sdiv <4 x i32> [[TMP1]], [[TMP6]]
-
-; CHECK-NEXT:    [[TMP9:%.*]] = shufflevector <4 x i32> [[TMP7]], <4 x i32> [[TMP8]], <4 x i32> <i32 0, i32 1, i32 6, i32 3>
-; CHECK-NEXT:    [[TMP10:%.*]] = bitcast i32* [[GEP2_0]] to <4 x i32>*
-; CHECK-NEXT:    store <4 x i32> [[TMP9]], <4 x i32>* [[TMP10]], align 4
+; CHECK-NEXT:    [[V0:%.*]] = load i32, i32* [[GEP1_0]]
+; CHECK-NEXT:    [[V1:%.*]] = load i32, i32* [[GEP1_1]]
+; CHECK-NEXT:    [[V2:%.*]] = load i32, i32* [[GEP1_2]]
+; CHECK-NEXT:    [[V3:%.*]] = load i32, i32* [[GEP1_3]]
+; CHECK-NEXT:    [[Y0:%.*]] = add nsw i32 [[A0:%.*]], 1146
+; CHECK-NEXT:    [[Y1:%.*]] = add nsw i32 [[A1:%.*]], 146
+; CHECK-NEXT:    [[Y2:%.*]] = add nsw i32 [[A2:%.*]], 42
+; CHECK-NEXT:    [[Y3:%.*]] = add nsw i32 [[A3:%.*]], 0
+; CHECK-NEXT:    [[RES0:%.*]] = add nsw i32 [[V0]], [[Y0]]
+; CHECK-NEXT:    [[RES1:%.*]] = add nsw i32 [[V1]], [[Y1]]
+; CHECK-NEXT:    [[RES2:%.*]] = sdiv i32 [[V2]], [[Y2]]
+; CHECK-NEXT:    [[RES3:%.*]] = add nsw i32 [[V3]], [[Y3]]
+; CHECK-NEXT:    store i32 [[RES0]], i32* [[GEP2_0]]
+; CHECK-NEXT:    store i32 [[RES1]], i32* [[GEP2_1]]
+; CHECK-NEXT:    store i32 [[RES2]], i32* [[GEP2_2]]
+; CHECK-NEXT:    store i32 [[RES3]], i32* [[GEP2_3]]
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %gep1.0 = getelementptr i32, i32* %arr1, i32 0
   %gep1.1 = getelementptr i32, i32* %arr1, i32 1
   %gep1.2 = getelementptr i32, i32* %arr1, i32 2
   %gep1.3 = getelementptr i32, i32* %arr1, i32 3
   %gep2.0 = getelementptr i32, i32* %arr2, i32 0

 ; CHECK-NEXT:    [[GEP1_0:%.*]] = getelementptr i32, i32* [[ARR1:%.*]], i32 0
 ; CHECK-NEXT:    [[GEP1_1:%.*]] = getelementptr i32, i32* [[ARR1]], i32 1
 ; CHECK-NEXT:    [[GEP1_2:%.*]] = getelementptr i32, i32* [[ARR1]], i32 2
 ; CHECK-NEXT:    [[GEP1_3:%.*]] = getelementptr i32, i32* [[ARR1]], i32 3
 ; CHECK-NEXT:    [[GEP2_0:%.*]] = getelementptr i32, i32* [[ARR2:%.*]], i32 0
 ; CHECK-NEXT:    [[GEP2_1:%.*]] = getelementptr i32, i32* [[ARR2]], i32 1
 ; CHECK-NEXT:    [[GEP2_2:%.*]] = getelementptr i32, i32* [[ARR2]], i32 2
 ; CHECK-NEXT:    [[GEP2_3:%.*]] = getelementptr i32, i32* [[ARR2]], i32 3
-; CHECK-NEXT:    [[TMP0:%.*]] = bitcast i32* [[GEP1_0]] to <4 x i32>*
-; CHECK-NEXT:    [[TMP1:%.*]] = load <4 x i32>, <4 x i32>* [[TMP0]], align 4
-; CHECK-NEXT:    [[TMP2:%.*]] = insertelement <4 x i32> undef, i32 [[A0:%.*]], i32 0
-; CHECK-NEXT:    [[TMP3:%.*]] = insertelement <4 x i32> [[TMP2]], i32 [[A1:%.*]], i32 1
-; CHECK-NEXT:    [[TMP4:%.*]] = insertelement <4 x i32> [[TMP3]], i32 [[A2:%.*]], i32 2
-; CHECK-NEXT:    [[TMP5:%.*]] = insertelement <4 x i32> [[TMP4]], i32 [[A3:%.*]], i32 3
-; CHECK-NEXT:    [[TMP6:%.*]] = add nsw <4 x i32> [[TMP5]], <i32 1146, i32 146, i32 42, i32 0>
-
-;; FIXME: Last lane of TMP6 may contain zero (if %a3 is zero). In such case, the
-;; next instruction would cause division by zero resulting in SIGFPE during
-;; execution.
-; CHECK-NEXT:    [[TMP7:%.*]] = urem <4 x i32> [[TMP1]], [[TMP6]]
-
-; CHECK-NEXT:    [[TMP8:%.*]] = add nsw <4 x i32> [[TMP1]], [[TMP6]]
-; CHECK-NEXT:    [[TMP9:%.*]] = shufflevector <4 x i32> [[TMP7]], <4 x i32> [[TMP8]], <4 x i32> <i32 0, i32 1, i32 2, i32 7>
-; CHECK-NEXT:    [[TMP10:%.*]] = bitcast i32* [[GEP2_0]] to <4 x i32>*
-; CHECK-NEXT:    store <4 x i32> [[TMP9]], <4 x i32>* [[TMP10]], align 4
+; CHECK-NEXT:    [[V0:%.*]] = load i32, i32* [[GEP1_0]]
+; CHECK-NEXT:    [[V1:%.*]] = load i32, i32* [[GEP1_1]]
+; CHECK-NEXT:    [[V2:%.*]] = load i32, i32* [[GEP1_2]]
+; CHECK-NEXT:    [[V3:%.*]] = load i32, i32* [[GEP1_3]]
+; CHECK-NEXT:    [[Y0:%.*]] = add nsw i32 [[A0:%.*]], 1146
+; CHECK-NEXT:    [[Y1:%.*]] = add nsw i32 [[A1:%.*]], 146
+; CHECK-NEXT:    [[Y2:%.*]] = add nsw i32 [[A2:%.*]], 42
+; CHECK-NEXT:    [[Y3:%.*]] = add nsw i32 [[A3:%.*]], 0
+; CHECK-NEXT:    [[RES0:%.*]] = urem i32 [[V0]], [[Y0]]
+; CHECK-NEXT:    [[RES1:%.*]] = urem i32 [[V1]], [[Y1]]
+; CHECK-NEXT:    [[RES2:%.*]] = urem i32 [[V2]], [[Y2]]
+; CHECK-NEXT:    [[RES3:%.*]] = add nsw i32 [[V3]], [[Y3]]
+; CHECK-NEXT:    store i32 [[RES0]], i32* [[GEP2_0]]
+; CHECK-NEXT:    store i32 [[RES1]], i32* [[GEP2_1]]
+; CHECK-NEXT:    store i32 [[RES2]], i32* [[GEP2_2]]
+; CHECK-NEXT:    store i32 [[RES3]], i32* [[GEP2_3]]
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %gep1.0 = getelementptr i32, i32* %arr1, i32 0
   %gep1.1 = getelementptr i32, i32* %arr1, i32 1
   %gep1.2 = getelementptr i32, i32* %arr1, i32 2
   %gep1.3 = getelementptr i32, i32* %arr1, i32 3
   %gep2.0 = getelementptr i32, i32* %arr2, i32 0