[InstCombine] prevent possible miscompile with negate+sdiv of vector op

[spatel]

Summary

// 0 - (X sdiv C)  -> (X sdiv -C)  provided the negation doesn't overflow.

This fold has been around for many years and nobody noticed the potential vector miscompile from overflow until today...
So it seems unlikely that there's much demand for a vector sdiv optimization on arbitrary vector constants, so just limit the matching to splat constants to avoid the possible bug.

[shchenz]

LGTM for this patch.

But should we also consider about the following pattern in file test/Transforms/InstCombine/div.ll

define <2 x i64> @test34(<2 x i64> %x) {
; CHECK-LABEL: @test34(
; CHECK-NEXT:    [[DIV:%.*]] = sdiv exact <2 x i64> [[X:%.*]], <i64 -3, i64 -4>
; CHECK-NEXT:    ret <2 x i64> [[DIV]]
;
  %neg = sub nsw <2 x i64> zeroinitializer, %x
  %div = sdiv exact <2 x i64> %neg, <i64 3, i64 4>
  ret <2 x i64> %div
}

This one is sdiv (neg(%x), constant), it should have same issue, right? But I think this should be another issue about sdiv combination?

[lebedev.ri]

This LG, thank you!

In D60426#1459186, @shchenz wrote:

LGTM for this patch.

But should we also consider about the following pattern in file test/Transforms/InstCombine/div.ll

define <2 x i64> @test34(<2 x i64> %x) {
; CHECK-LABEL: @test34(
; CHECK-NEXT:    [[DIV:%.*]] = sdiv exact <2 x i64> [[X:%.*]], <i64 -3, i64 -4>
; CHECK-NEXT:    ret <2 x i64> [[DIV]]
;
  %neg = sub nsw <2 x i64> zeroinitializer, %x
  %div = sdiv exact <2 x i64> %neg, <i64 3, i64 4>
  ret <2 x i64> %div
}

This one is sdiv (neg(%x), constant), it should have same issue, right? But I think this should be another issue about sdiv combination?

Yes, that seems to have the same general problem.
https://godbolt.org/z/vPVHmh

llvm/test/Transforms/InstCombine/div.ll

820 ↗

(On Diff #194218)

Could also add a test for SINT_MIN (yes, i have seen the next test here)

[spatel]

llvm/test/Transforms/InstCombine/div.ll

820 ↗

(On Diff #194218)

Do you mean a splat of SINT_MIN (that's above here) or something else?

[lebedev.ri]

llvm/test/Transforms/InstCombine/div.ll

820 ↗

(On Diff #194218)

I actually initially misread @negate_sdiv_vec_signed_min_elt, i thought it was:

define <2 x i8> @negate_sdiv_vec_signed_min_and_one_elt(<2 x i8> %x) {
  %div = sdiv <2 x i8> %x, <i8 1, i8 -128>
  %neg = sub <2 x i8> zeroinitializer, %div
  ret <2 x i8> %neg
}

and i was going to suggest to add the test that is already in @negate_sdiv_vec_signed_min_elt.
So now i guess i'd suggest maybe adding test from this comment.

[spatel]

llvm/test/Transforms/InstCombine/div.ll

820 ↗

(On Diff #194218)

Thanks - will do.

And I'll make a similar code change for the other buggy pattern matcher if that looks like the same problem.

llvm/trunk/lib/Transforms/InstCombine/InstCombineAddSub.cpp

if (match(Op1, m_Sub(m_Value(Y), m_Value(Z))))
                                       Builder.CreateSub(Z, Y, Op1->getName()));
 
     // (X - (X & Y))   -->   (X & ~Y)
     if (match(Op1, m_c_And(m_Value(Y), m_Specific(Op0))))
       return BinaryOperator::CreateAnd(Op0,
                                   Builder.CreateNot(Y, Y->getName() + ".not"));
 
     // 0 - (X sdiv C)  -> (X sdiv -C)  provided the negation doesn't overflow.
-    if (match(Op1, m_SDiv(m_Value(X), m_Constant(C))) && match(Op0, m_Zero()) &&
-        C->isNotMinSignedValue() && !C->isOneValue()) {
-      auto *BO = BinaryOperator::CreateSDiv(X, ConstantExpr::getNeg(C));
+    // TODO: This could be extended to match arbitrary vector constants.
+    const APInt *DivC;
+    if (match(Op0, m_Zero()) && match(Op1, m_SDiv(m_Value(X), m_APInt(DivC))) &&
+        !DivC->isMinSignedValue() && *DivC != 1) {
+      Constant *NegDivC = ConstantInt::get(I.getType(), -(*DivC));
+      Instruction *BO = BinaryOperator::CreateSDiv(X, NegDivC);
       BO->setIsExact(cast<BinaryOperator>(Op1)->isExact());
       return BO;
     }
 
     // 0 - (X << Y)  -> (-X << Y)   when X is freely negatable.
     if (match(Op1, m_Shl(m_Value(X), m_Value(Y))) && match(Op0, m_Zero()))
       if (Value *XNeg = dyn_castNegVal(X))
         return BinaryOperator::CreateShl(XNeg, Y);

llvm/trunk/test/Transforms/InstCombine/div.ll

 ;
   %div = sdiv exact i32 %x, 3
   %neg = sub nsw i32 0, %div
   ret i32 %neg
 }
 
 define <2 x i64> @test_exact_vec(<2 x i64> %x) {
 ; CHECK-LABEL: @test_exact_vec(
-; CHECK-NEXT:    [[NEG:%.*]] = sdiv exact <2 x i64> [[X:%.*]], <i64 -3, i64 -4>
+; CHECK-NEXT:    [[DIV:%.*]] = sdiv exact <2 x i64> [[X:%.*]], <i64 3, i64 4>
+; CHECK-NEXT:    [[NEG:%.*]] = sub nsw <2 x i64> zeroinitializer, [[DIV]]
 ; CHECK-NEXT:    ret <2 x i64> [[NEG]]
 ;
   %div = sdiv exact <2 x i64> %x, <i64 3, i64 4>
   %neg = sub nsw <2 x i64> zeroinitializer, %div
   ret <2 x i64> %neg
 }
 
 ; Constant is safe to negate.
;
   %neg = sub <2 x i8> zeroinitializer, %div
   ret <2 x i8> %neg
 }
 
 ; Division by -1 may be UB for any element of a vector.
 
 define <2 x i8> @negate_sdiv_vec_one_element(<2 x i8> %x) {
 ; CHECK-LABEL: @negate_sdiv_vec_one_element(
-; CHECK-NEXT:    [[NEG:%.*]] = sdiv <2 x i8> [[X:%.*]], <i8 1, i8 -1>
+; CHECK-NEXT:    [[DIV:%.*]] = sdiv <2 x i8> [[X:%.*]], <i8 -1, i8 1>
+; CHECK-NEXT:    [[NEG:%.*]] = sub <2 x i8> zeroinitializer, [[DIV]]
 ; CHECK-NEXT:    ret <2 x i8> [[NEG]]
 ;
   %div = sdiv <2 x i8> %x, <i8 -1, i8 1>
   %neg = sub <2 x i8> zeroinitializer, %div
   ret <2 x i8> %neg
 }
 
-; Division by -1 may be UB and can't negate signed-min.
+; Can't negate signed-min constant for any element of a vector.
 
 define <2 x i8> @negate_sdiv_vec_signed_min_elt(<2 x i8> %x) {
 ; CHECK-LABEL: @negate_sdiv_vec_signed_min_elt(
 ; CHECK-NEXT:    [[DIV:%.*]] = sdiv <2 x i8> [[X:%.*]], <i8 -1, i8 -128>
 ; CHECK-NEXT:    [[NEG:%.*]] = sub <2 x i8> zeroinitializer, [[DIV]]
 ; CHECK-NEXT:    ret <2 x i8> [[NEG]]
 ;
   %div = sdiv <2 x i8> %x, <i8 -1, i8 -128>
   %neg = sub <2 x i8> zeroinitializer, %div
   ret <2 x i8> %neg
 }
 
-; Can't negate signed-min constant for any element of a vector.
+; Division by -1 may be UB and can't negate signed-min.
 
 define <2 x i8> @negate_sdiv_vec_signed_min_and_one_elt(<2 x i8> %x) {
 ; CHECK-LABEL: @negate_sdiv_vec_signed_min_and_one_elt(
 ; CHECK-NEXT:    [[DIV:%.*]] = sdiv <2 x i8> [[X:%.*]], <i8 1, i8 -128>
 ; CHECK-NEXT:    [[NEG:%.*]] = sub <2 x i8> zeroinitializer, [[DIV]]
 ; CHECK-NEXT:    ret <2 x i8> [[NEG]]
 ;
   %div = sdiv <2 x i8> %x, <i8 1, i8 -128>