Fix constant-folding of overflowing arithmetic ops on vectors

[LemonBoy]

Summary

Feeding vector values to InstCombiner::OptimizeOverflowCheck produces a scalar boolean flag if it proves the overflow check can be eliminated.
This causes InstCombiner::CreateOverflowTuple to crash as it correctly expects a vector of i1 values instead.

[LemonBoy]

Oh well, it turns out the results are evaluated according to all the elements so it's ok to splat it.

[nikic]

Doesn't the same issue apply to the isNeutralValue branch?

[lebedev.ri]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

4607

This seems like wrong granularity.
I think there should be some method that would return an appropriate i1 or vector of i1 type,
which you'd then just pass into ConstantInt::getFalse()/ConstantInt::getTrue().

[LemonBoy]

Fix the neutral value code path too.

[LemonBoy]

Doesn't the same issue apply to the isNeutralValue branch?

Duh, fixed that too.

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

4607

That's the prettiest way to get a constant i1xN vector I found. I'm not too familiar with the internal LLVM APIs so suggestions are more than welcome.

[LemonBoy]

Cleaned up the true/false building parts.
Added a note about LLVM not detecting if signed multiplication overflow, not much of a problem and can be fixed later.

[lebedev.ri]

Looks good to me, thanks.

[LemonBoy]

Looks good to me, thanks.

Great, can you commit this on my behalf? I have no commit access.

@hans Is it too early to request this patch to be included in 11.0.1?

[LemonBoy]

Ping?

[lebedev.ri]

In D89628#2342684, @LemonBoy wrote:

Looks good to me, thanks.

Great, can you commit this on my behalf? I have no commit access.

@hans Is it too early to request this patch to be included in 11.0.1?

Please specify the Author: name <[e-mail]> to be used for the commit.

[LemonBoy]

In D89628#2358994, @lebedev.ri wrote:

In D89628#2342684, @LemonBoy wrote:

Looks good to me, thanks.

Great, can you commit this on my behalf? I have no commit access.

@hans Is it too early to request this patch to be included in 11.0.1?

Please specify the Author: name <[e-mail]> to be used for the commit.

The name is LemonBoy, you can get the mail from running git log --author=LemonBoy in the LLVM repo.
TIA

[majnemer]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

4590–4592

I think this can be simplified to CmpInst::makeCmpResultType(LHS->getType())

[LemonBoy]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

4590–4592

Yup, I didn't use that because this is not the result of a comparison despite having the same type as one.

[LemonBoy]

sigh
Ping?

[lebedev.ri]

Terribly sorry for that, landed now.
Please just get commit access yourself :)

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

if (OrigI.isCommutative() && isa<Constant>(LHS) && !isa<Constant>(RHS))
     std::swap(LHS, RHS);
 
   // If the overflow check was an add followed by a compare, the insertion point
   // may be pointing to the compare.  We want to insert the new instructions
   // before the add in case there are uses of the add between the add and the
   // compare.
   Builder.SetInsertPoint(&OrigI);
 
+  Type *OverflowTy = Type::getInt1Ty(LHS->getContext());
+  if (auto *LHSTy = dyn_cast<VectorType>(LHS->getType()))
+    OverflowTy = VectorType::get(OverflowTy, LHSTy->getElementCount());
+
   if (isNeutralValue(BinaryOp, RHS)) {
     Result = LHS;
-    Overflow = Builder.getFalse();
+    Overflow = ConstantInt::getFalse(OverflowTy);
     return true;
   }
 
   switch (computeOverflow(BinaryOp, IsSigned, LHS, RHS, &OrigI)) {
     case OverflowResult::MayOverflow:
       return false;
     case OverflowResult::AlwaysOverflowsLow:
     case OverflowResult::AlwaysOverflowsHigh:
       Result = Builder.CreateBinOp(BinaryOp, LHS, RHS);
       Result->takeName(&OrigI);
-      Overflow = Builder.getTrue();
+      Overflow = ConstantInt::getTrue(OverflowTy);
       return true;
     case OverflowResult::NeverOverflows:
       Result = Builder.CreateBinOp(BinaryOp, LHS, RHS);
       Result->takeName(&OrigI);
-      Overflow = Builder.getFalse();
+      Overflow = ConstantInt::getFalse(OverflowTy);
       if (auto *Inst = dyn_cast<Instruction>(Result)) {
         if (IsSigned)
           Inst->setHasNoSignedWrap();
         else
           Inst->setHasNoUnsignedWrap();
       }
       return true;
   }

llvm/test/Transforms/InstCombine/with_overflow.ll

 ; CHECK-NEXT:    [[A:%.*]] = call { i8, i1 } @llvm.smul.with.overflow.i8(i8 [[Y]], i8 2)
 ; CHECK-NEXT:    ret { i8, i1 } [[A]]
 ;
   %c = icmp sgt i8 %x, 100
   %y = select i1 %c, i8 %x, i8 100
   %a = call { i8, i1 } @llvm.smul.with.overflow.i8(i8 %y, i8 2)
   ret { i8, i1 } %a
 }
+
+declare { <4 x i8>, <4 x i1> } @llvm.sadd.with.overflow.v4i8(<4 x i8>, <4 x i8>)
+declare { <4 x i8>, <4 x i1> } @llvm.uadd.with.overflow.v4i8(<4 x i8>, <4 x i8>)
+declare { <4 x i8>, <4 x i1> } @llvm.ssub.with.overflow.v4i8(<4 x i8>, <4 x i8>)
+declare { <4 x i8>, <4 x i1> } @llvm.usub.with.overflow.v4i8(<4 x i8>, <4 x i8>)
+declare { <4 x i8>, <4 x i1> } @llvm.smul.with.overflow.v4i8(<4 x i8>, <4 x i8>)
+declare { <4 x i8>, <4 x i1> } @llvm.umul.with.overflow.v4i8(<4 x i8>, <4 x i8>)
+
+; Always overflow
+
+define { <4 x i8>, <4 x i1> } @always_sadd_const_vector() nounwind {
+; CHECK-LABEL: @always_sadd_const_vector(
+; CHECK-NEXT:    ret { <4 x i8>, <4 x i1> } { <4 x i8> <i8 -128, i8 -128, i8 -128, i8 -128>, <4 x i1> <i1 true, i1 true, i1 true, i1 true> }
+;
+  %x = call { <4 x i8>, <4 x i1> } @llvm.sadd.with.overflow.v4i8(<4 x i8> <i8 127, i8 127, i8 127, i8 127>, <4 x i8> <i8 1, i8 1, i8 1, i8 1>)
+  ret { <4 x i8>, <4 x i1> } %x
+}
+
+define { <4 x i8>, <4 x i1> } @always_uadd_const_vector() nounwind {
+; CHECK-LABEL: @always_uadd_const_vector(
+; CHECK-NEXT:    ret { <4 x i8>, <4 x i1> } { <4 x i8> zeroinitializer, <4 x i1> <i1 true, i1 true, i1 true, i1 true> }
+;
+  %x = call { <4 x i8>, <4 x i1> } @llvm.uadd.with.overflow.v4i8(<4 x i8> <i8 255, i8 255, i8 255, i8 255>, <4 x i8> <i8 1, i8 1, i8 1, i8 1>)
+  ret { <4 x i8>, <4 x i1> } %x
+}
+
+define { <4 x i8>, <4 x i1> } @always_ssub_const_vector() nounwind {
+; CHECK-LABEL: @always_ssub_const_vector(
+; CHECK-NEXT:    ret { <4 x i8>, <4 x i1> } { <4 x i8> <i8 127, i8 127, i8 127, i8 127>, <4 x i1> <i1 true, i1 true, i1 true, i1 true> }
+;
+  %x = call { <4 x i8>, <4 x i1> } @llvm.ssub.with.overflow.v4i8(<4 x i8> <i8 -128, i8 -128, i8 -128, i8 -128>, <4 x i8> <i8 1, i8 1, i8 1, i8 1>)
+  ret { <4 x i8>, <4 x i1> } %x
+}
+
+define { <4 x i8>, <4 x i1> } @always_usub_const_vector() nounwind {
+; CHECK-LABEL: @always_usub_const_vector(
+; CHECK-NEXT:    ret { <4 x i8>, <4 x i1> } { <4 x i8> <i8 -1, i8 -1, i8 -1, i8 -1>, <4 x i1> <i1 true, i1 true, i1 true, i1 true> }
+;
+  %x = call { <4 x i8>, <4 x i1> } @llvm.usub.with.overflow.v4i8(<4 x i8> <i8 0, i8 0, i8 0, i8 0>, <4 x i8> <i8 1, i8 1, i8 1, i8 1>)
+  ret { <4 x i8>, <4 x i1> } %x
+}
+
+; NOTE: LLVM doesn't (yet) detect the multiplication always results in a overflow
+define { <4 x i8>, <4 x i1> } @always_smul_const_vector() nounwind {
+; CHECK-LABEL: @always_smul_const_vector(
+; CHECK-NEXT:    [[X:%.*]] = call { <4 x i8>, <4 x i1> } @llvm.smul.with.overflow.v4i8(<4 x i8> <i8 127, i8 127, i8 127, i8 127>, <4 x i8> <i8 3, i8 3, i8 3, i8 3>)
+; CHECK-NEXT:    ret { <4 x i8>, <4 x i1> } [[X]]
+;
+  %x = call { <4 x i8>, <4 x i1> } @llvm.smul.with.overflow.v4i8(<4 x i8> <i8 127, i8 127, i8 127, i8 127>, <4 x i8> <i8 3, i8 3, i8 3, i8 3>)
+  ret { <4 x i8>, <4 x i1> } %x
+}
+
+define { <4 x i8>, <4 x i1> } @always_umul_const_vector() nounwind {
+; CHECK-LABEL: @always_umul_const_vector(
+; CHECK-NEXT:    ret { <4 x i8>, <4 x i1> } { <4 x i8> <i8 -3, i8 -3, i8 -3, i8 -3>, <4 x i1> <i1 true, i1 true, i1 true, i1 true> }
+;
+  %x = call { <4 x i8>, <4 x i1> } @llvm.umul.with.overflow.v4i8(<4 x i8> <i8 255, i8 255, i8 255, i8 255>, <4 x i8> <i8 3, i8 3, i8 3, i8 3>)
+  ret { <4 x i8>, <4 x i1> } %x
+}
+
+; Never overflow
+
+define { <4 x i8>, <4 x i1> } @never_sadd_const_vector() nounwind {
+; CHECK-LABEL: @never_sadd_const_vector(
+; CHECK-NEXT:    ret { <4 x i8>, <4 x i1> } { <4 x i8> <i8 -50, i8 -10, i8 0, i8 60>, <4 x i1> zeroinitializer }
+;
+  %x = call { <4 x i8>, <4 x i1> } @llvm.sadd.with.overflow.v4i8(<4 x i8> <i8 -10, i8 -20, i8 30, i8 40>, <4 x i8> <i8 -40, i8 10, i8 -30, i8 20>)
+  ret { <4 x i8>, <4 x i1> } %x
+}
+
+define { <4 x i8>, <4 x i1> } @never_uadd_const_vector() nounwind {
+; CHECK-LABEL: @never_uadd_const_vector(
+; CHECK-NEXT:    ret { <4 x i8>, <4 x i1> } { <4 x i8> <i8 32, i8 64, i8 96, i8 48>, <4 x i1> zeroinitializer }
+;
+  %x = call { <4 x i8>, <4 x i1> } @llvm.uadd.with.overflow.v4i8(<4 x i8> <i8 0, i8 32, i8 64, i8 16>, <4 x i8> <i8 32, i8 32, i8 32, i8 32>)
+  ret { <4 x i8>, <4 x i1> } %x
+}
+
+define { <4 x i8>, <4 x i1> } @never_ssub_const_vector() nounwind {
+; CHECK-LABEL: @never_ssub_const_vector(
+; CHECK-NEXT:    ret { <4 x i8>, <4 x i1> } { <4 x i8> <i8 0, i8 10, i8 20, i8 30>, <4 x i1> zeroinitializer }
+;
+  %x = call { <4 x i8>, <4 x i1> } @llvm.ssub.with.overflow.v4i8(<4 x i8> <i8 -10, i8 -10, i8 -10, i8 -10>, <4 x i8> <i8 -10, i8 -20, i8 -30, i8 -40>)
+  ret { <4 x i8>, <4 x i1> } %x
+}
+
+define { <4 x i8>, <4 x i1> } @never_usub_const_vector() nounwind {
+; CHECK-LABEL: @never_usub_const_vector(
+; CHECK-NEXT:    ret { <4 x i8>, <4 x i1> } { <4 x i8> <i8 127, i8 -1, i8 0, i8 -2>, <4 x i1> zeroinitializer }
+;
+  %x = call { <4 x i8>, <4 x i1> } @llvm.usub.with.overflow.v4i8(<4 x i8> <i8 255, i8 255, i8 255, i8 255>, <4 x i8> <i8 128, i8 0, i8 255, i8 1>)
+  ret { <4 x i8>, <4 x i1> } %x
+}
+
+define { <4 x i8>, <4 x i1> } @never_smul_const_vector() nounwind {
+; CHECK-LABEL: @never_smul_const_vector(
+; CHECK-NEXT:    ret { <4 x i8>, <4 x i1> } { <4 x i8> <i8 -54, i8 -18, i8 -60, i8 -90>, <4 x i1> zeroinitializer }
+;
+  %x = call { <4 x i8>, <4 x i1> } @llvm.smul.with.overflow.v4i8(<4 x i8> <i8 -6, i8 -6, i8 -6, i8 -6>, <4 x i8> <i8 9, i8 3, i8 10, i8 15>)
+  ret { <4 x i8>, <4 x i1> } %x
+}
+
+define { <4 x i8>, <4 x i1> } @never_umul_const_vector() nounwind {
+; CHECK-LABEL: @never_umul_const_vector(
+; CHECK-NEXT:    ret { <4 x i8>, <4 x i1> } { <4 x i8> <i8 -31, i8 120, i8 60, i8 30>, <4 x i1> zeroinitializer }
+;
+  %x = call { <4 x i8>, <4 x i1> } @llvm.umul.with.overflow.v4i8(<4 x i8> <i8 15, i8 15, i8 15, i8 15>, <4 x i8> <i8 15, i8 8, i8 4, i8 2>)
+  ret { <4 x i8>, <4 x i1> } %x
+}
+
+; Neutral value
+
+define { <4 x i8>, <4 x i1> } @neutral_sadd_const_vector() nounwind {
+; CHECK-LABEL: @neutral_sadd_const_vector(
+; CHECK-NEXT:    ret { <4 x i8>, <4 x i1> } { <4 x i8> <i8 1, i8 2, i8 3, i8 4>, <4 x i1> zeroinitializer }
+;
+  %x = call { <4 x i8>, <4 x i1> } @llvm.sadd.with.overflow.v4i8(<4 x i8> <i8 1, i8 2, i8 3, i8 4>, <4 x i8> <i8 0, i8 0, i8 0, i8 0>)
+  ret { <4 x i8>, <4 x i1> } %x
+}
+
+define { <4 x i8>, <4 x i1> } @neutral_uadd_const_vector() nounwind {
+; CHECK-LABEL: @neutral_uadd_const_vector(
+; CHECK-NEXT:    ret { <4 x i8>, <4 x i1> } { <4 x i8> <i8 1, i8 2, i8 3, i8 4>, <4 x i1> zeroinitializer }
+;
+  %x = call { <4 x i8>, <4 x i1> } @llvm.uadd.with.overflow.v4i8(<4 x i8> <i8 1, i8 2, i8 3, i8 4>, <4 x i8> <i8 0, i8 0, i8 0, i8 0>)
+  ret { <4 x i8>, <4 x i1> } %x
+}
+
+define { <4 x i8>, <4 x i1> } @neutral_ssub_const_vector() nounwind {
+; CHECK-LABEL: @neutral_ssub_const_vector(
+; CHECK-NEXT:    ret { <4 x i8>, <4 x i1> } { <4 x i8> <i8 1, i8 2, i8 3, i8 4>, <4 x i1> zeroinitializer }
+;
+  %x = call { <4 x i8>, <4 x i1> } @llvm.ssub.with.overflow.v4i8(<4 x i8> <i8 1, i8 2, i8 3, i8 4>, <4 x i8> <i8 0, i8 0, i8 0, i8 0>)
+  ret { <4 x i8>, <4 x i1> } %x
+}
+
+define { <4 x i8>, <4 x i1> } @neutral_usub_const_vector() nounwind {
+; CHECK-LABEL: @neutral_usub_const_vector(
+; CHECK-NEXT:    ret { <4 x i8>, <4 x i1> } { <4 x i8> <i8 1, i8 2, i8 3, i8 4>, <4 x i1> zeroinitializer }
+;
+  %x = call { <4 x i8>, <4 x i1> } @llvm.usub.with.overflow.v4i8(<4 x i8> <i8 1, i8 2, i8 3, i8 4>, <4 x i8> <i8 0, i8 0, i8 0, i8 0>)
+  ret { <4 x i8>, <4 x i1> } %x
+}
+
+define { <4 x i8>, <4 x i1> } @neutral_smul_const_vector() nounwind {
+; CHECK-LABEL: @neutral_smul_const_vector(
+; CHECK-NEXT:    ret { <4 x i8>, <4 x i1> } { <4 x i8> <i8 1, i8 2, i8 3, i8 4>, <4 x i1> zeroinitializer }
+;
+  %x = call { <4 x i8>, <4 x i1> } @llvm.smul.with.overflow.v4i8(<4 x i8> <i8 1, i8 2, i8 3, i8 4>, <4 x i8> <i8 1, i8 1, i8 1, i8 1>)
+  ret { <4 x i8>, <4 x i1> } %x
+}
+
+define { <4 x i8>, <4 x i1> } @neutral_umul_const_vector() nounwind {
+; CHECK-LABEL: @neutral_umul_const_vector(
+; CHECK-NEXT:    ret { <4 x i8>, <4 x i1> } { <4 x i8> <i8 1, i8 2, i8 3, i8 4>, <4 x i1> zeroinitializer }
+;
+  %x = call { <4 x i8>, <4 x i1> } @llvm.umul.with.overflow.v4i8(<4 x i8> <i8 1, i8 2, i8 3, i8 4>, <4 x i8> <i8 1, i8 1, i8 1, i8 1>)
+  ret { <4 x i8>, <4 x i1> } %x
+}