This is an archive of the discontinued LLVM Phabricator instance.

Differential D89628

Fix constant-folding of overflowing arithmetic ops on vectors
ClosedPublic

Authored by LemonBoy on Oct 17 2020, 10:42 AM.

Details

Reviewers
RKSimon
lebedev.ri
majnemer
Commits
rG42732d33cc7f: [InstCombine] Fix constant-folding of overflowing arithmetic ops on vectors
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.

Diff Detail

Event Timeline

LemonBoy created this revision.Oct 17 2020, 10:42 AM
Herald added subscribers: llvm-commits, hiraditya. · View Herald TranscriptOct 17 2020, 10:42 AM
LemonBoy requested review of this revision.Oct 17 2020, 10:42 AM
Harbormaster completed remote builds in B75428: Diff 298837.Oct 17 2020, 11:16 AM
LemonBoy updated this revision to Diff 298846.Oct 17 2020, 12:03 PM

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

nikic added a subscriber: nikic.Oct 17 2020, 12:07 PM

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

lebedev.ri added inline comments.Oct 17 2020, 12:13 PM
llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
4599

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 updated this revision to Diff 298850.Oct 17 2020, 1:30 PM

Fix the neutral value code path too.

LemonBoy added a comment.Oct 17 2020, 1:33 PM

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

Duh, fixed that too.

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
4599

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 updated this revision to Diff 299425.Oct 20 2020, 11:20 AM

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 accepted this revision.Oct 20 2020, 11:24 AM

Looks good to me, thanks.

This revision is now accepted and ready to land.Oct 20 2020, 11:24 AM
LemonBoy added a subscriber: hans.Oct 20 2020, 1:40 PM

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 added a comment.Oct 28 2020, 6:31 AM

Ping?

lebedev.ri added a comment.Oct 28 2020, 6:44 AM
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@ma.il> to be used for the commit.

LemonBoy added a comment.Oct 28 2020, 6:52 AM
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@ma.il> 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

LemonBoy retitled this revision from Don't fold overflowing arithmetic ops on vectors to Fix constant-folding of overflowing arithmetic ops on vectors.Oct 31 2020, 6:45 AM
LemonBoy edited the summary of this revision. (Show Details)
majnemer added inline comments.Oct 31 2020, 9:27 AM
llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
4582–4584

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

LemonBoy added inline comments.Oct 31 2020, 10:15 AM
llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
4582–4584

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

LemonBoy added a comment.Nov 9 2020, 3:36 AM

sigh
Ping?

Closed by commit rG42732d33cc7f: [InstCombine] Fix constant-folding of overflowing arithmetic ops on vectors (authored by LemonBoy, committed by lebedev.ri). · Explain WhyNov 9 2020, 3:50 AM
This revision was automatically updated to reflect the committed changes.
lebedev.ri added a commit: rG42732d33cc7f: [InstCombine] Fix constant-folding of overflowing arithmetic ops on vectors.
lebedev.ri added a comment.Nov 9 2020, 3:50 AM

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

Revision Contents

PathSize
llvm/
lib/
Transforms/
InstCombine/
10 lines
test/
Transforms/
InstCombine/
159 lines

Diff 299425

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

Show First 20 Lines • Show All 4,573 Lines • ▼ Show 20 Lines if (OrigI.isCommutative() && isa<Constant>(LHS) && !isa<Constant>(RHS))
std::swap(LHS, RHS); std::swap(LHS, RHS);
// If the overflow check was an add followed by a compare, the insertion point // 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 // 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 // before the add in case there are uses of the add between the add and the
// compare. // compare.
Builder.SetInsertPoint(&OrigI); Builder.SetInsertPoint(&OrigI);
Type *OverflowTy = Type::getInt1Ty(LHS->getContext());
if (auto *LHSTy = dyn_cast<VectorType>(LHS->getType()))
OverflowTy = VectorType::get(OverflowTy, LHSTy->getElementCount());
majnemerUnsubmitted
Not Done
ReplyInline Actions

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

majnemer: I think this can be simplified to `CmpInst::makeCmpResultType(LHS->getType())`
LemonBoyAuthorUnsubmitted
Done
ReplyInline Actions

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

LemonBoy: Yup, I didn't use that because this is not the result of a comparison despite having the same…
if (isNeutralValue(BinaryOp, RHS)) { if (isNeutralValue(BinaryOp, RHS)) {
Result = LHS; Result = LHS;
Overflow = Builder.getFalse(); Overflow = ConstantInt::getFalse(OverflowTy);
return true; return true;
} }
switch (computeOverflow(BinaryOp, IsSigned, LHS, RHS, &OrigI)) { switch (computeOverflow(BinaryOp, IsSigned, LHS, RHS, &OrigI)) {
case OverflowResult::MayOverflow: case OverflowResult::MayOverflow:
return false; return false;
case OverflowResult::AlwaysOverflowsLow: case OverflowResult::AlwaysOverflowsLow:
case OverflowResult::AlwaysOverflowsHigh: case OverflowResult::AlwaysOverflowsHigh:
Result = Builder.CreateBinOp(BinaryOp, LHS, RHS); Result = Builder.CreateBinOp(BinaryOp, LHS, RHS);
Result->takeName(&OrigI); Result->takeName(&OrigI);
Overflow = Builder.getTrue(); Overflow = ConstantInt::getTrue(OverflowTy);
lebedev.riUnsubmitted
Not Done
ReplyInline Actions

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().

lebedev.ri: This seems like wrong granularity. I think there should be some method that would return an…
LemonBoyAuthorUnsubmitted
Done
ReplyInline Actions

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: That's the prettiest way to get a constant `i1xN` vector I found. I'm not too familiar with the…
return true; return true;
case OverflowResult::NeverOverflows: case OverflowResult::NeverOverflows:
Result = Builder.CreateBinOp(BinaryOp, LHS, RHS); Result = Builder.CreateBinOp(BinaryOp, LHS, RHS);
Result->takeName(&OrigI); Result->takeName(&OrigI);
Overflow = Builder.getFalse(); Overflow = ConstantInt::getFalse(OverflowTy);
if (auto *Inst = dyn_cast<Instruction>(Result)) { if (auto *Inst = dyn_cast<Instruction>(Result)) {
if (IsSigned) if (IsSigned)
Inst->setHasNoSignedWrap(); Inst->setHasNoSignedWrap();
else else
Inst->setHasNoUnsignedWrap(); Inst->setHasNoUnsignedWrap();
} }
return true; return true;
} }
▲ Show 20 Lines • Show All 1,698 Lines • Show Last 20 Lines

llvm/test/Transforms/InstCombine/with_overflow.ll

Show First 20 Lines • Show All 591 Lines • ▼ Show 20 Lines
; CHECK-NEXT: [[A:%.*]] = call { i8, i1 } @llvm.smul.with.overflow.i8(i8 [[Y]], i8 2) ; CHECK-NEXT: [[A:%.*]] = call { i8, i1 } @llvm.smul.with.overflow.i8(i8 [[Y]], i8 2)
; CHECK-NEXT: ret { i8, i1 } [[A]] ; CHECK-NEXT: ret { i8, i1 } [[A]]
; ;
%c = icmp sgt i8 %x, 100 %c = icmp sgt i8 %x, 100
%y = select i1 %c, i8 %x, i8 100 %y = select i1 %c, i8 %x, i8 100
%a = call { i8, i1 } @llvm.smul.with.overflow.i8(i8 %y, i8 2) %a = call { i8, i1 } @llvm.smul.with.overflow.i8(i8 %y, i8 2)
ret { i8, i1 } %a 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
}