This is an archive of the discontinued LLVM Phabricator instance.

Differential D47041

[ValueTracking] Teach computeKnownBits that the result of an absolute value pattern that uses nsw flag is always positive.
ClosedPublic

Authored by craig.topper on May 17 2018, 5:04 PM.

Details

Reviewers
spatel
efriedma
Commits
rG8f77dcadffe0: Recommit r333226 "[ValueTracking] Teach computeKnownBits that the result of an…
rG49f23fe349fb: [ValueTracking] Teach computeKnownBits that the result of an absolute value…
rL333300: Recommit r333226 "[ValueTracking] Teach computeKnownBits that the result of an…
rL333226: [ValueTracking] Teach computeKnownBits that the result of an absolute value…
Summary

If the nsw flag is used in the absolute value then it is undefined for INT_MIN. For all other value it will produce a positive number. So we can assume the result is positive.

This breaks some InstCombine abs/nabs combining tests because we simplify the second compare from known bits rather than as the whole pattern. Looks like we can probably fix it by adding a neg+abs/nabs combine to just swap the select operands. Need to check alive to make sure there are no corner cases.

Diff Detail

Repository
rL LLVM

Event Timeline

craig.topper created this revision.May 17 2018, 5:04 PM
efriedma added inline comments.May 17 2018, 5:19 PM
lib/Analysis/ValueTracking.cpp
1086 ↗(On Diff #147411)

Can you write a similar pattern for SPF_NABS?

We could save a bit of computation by not calling ComputeKnownBits on both x and -x, but it's probably not worth bothering...

craig.topper added inline comments.May 17 2018, 6:34 PM
lib/Analysis/ValueTracking.cpp
1086 ↗(On Diff #147411)

I don't think SPF_NABS has a sign bit guarantee. NABS of 0 is still 0. NABS of anything else is negative.

dmgreen added a subscriber: dmgreen.May 18 2018, 5:10 AM
dmgreen added inline comments.
lib/Analysis/ValueTracking.cpp
1085 ↗(On Diff #147411)

Can't RHS be a const?

spatel mentioned this in D47076: [InstCombine] choose 1 form of abs and nabs as canonical.May 18 2018, 9:24 AM
craig.topper added a parent revision: D47037: [EarlyCSE] Improve EarlyCSE of some absolute value cases..May 18 2018, 11:26 AM
craig.topper added inline comments.
lib/Analysis/ValueTracking.cpp
1085 ↗(On Diff #147411)

This patch is dependent on another patch where I made matchSelectPattern return the negation portion in RHS. Previously it always returned a 0, 1, or -1 constant which was failry useless.

spatel mentioned this in rL332819: [InstCombine] choose 1 form of abs and nabs as canonical.May 20 2018, 7:27 AM
craig.topper updated this revision to Diff 148111.May 22 2018, 2:59 PM

Add a combine to negate ABS/NABS to recover the broken tests.

craig.topper updated this revision to Diff 148113.May 22 2018, 3:07 PM

Add a simple test case to show (abs(x)) > 0 is always true.

craig.topper added a comment.May 22 2018, 3:12 PM

That should have said abs(x) >= 0 is always true.

spatel added inline comments.May 22 2018, 3:34 PM
lib/Transforms/InstCombine/InstCombineAddSub.cpp
1636–1637 ↗(On Diff #148113)

We should copy and then swapProfMetadata for the new select rather than dropping that. Alternatively, we could swap the operands and metadata on the existing select and return it. Since we're checking hasOneUse(), I think it's ok to recycle.

This part can be a separate commit with independent tests like:

define i8 @negate_abs(i8 %x) {
  %n = sub i8 0, %x
  %c = icmp slt i8 %x, 0
  %s = select i1 %c, i8 %n, i8 %x
  %r = sub i8 0, %s
  ret i8 %r
}

define <2 x i8> @negate_nabs(<2 x i8> %x) {
  %n = sub <2 x i8> zeroinitializer, %x
  %c = icmp slt <2 x i8> %x, zeroinitializer
  %s = select <2 x i1> %c, <2 x i8> %x, <2 x i8> %n
  %r = sub <2 x i8> zeroinitializer, %s
  ret <2 x i8> %r
}
spatel added a comment.May 22 2018, 4:01 PM

On 2nd thought, we're not actually changing the implicit branch here, so this should just propagate the metadata of the existing select.

craig.topper mentioned this in D47236: [InstCombine] Negate ABS/NABS patterns by swapping the select operands to remove the negation.May 22 2018, 4:44 PM
craig.topper updated this revision to Diff 148247.May 23 2018, 10:43 AM

Rebase to remvoe the InstCombine changes that were split off to another patch and have now been committed

spatel accepted this revision.May 24 2018, 2:13 PM

LGTM.

This revision is now accepted and ready to land.May 24 2018, 2:13 PM
Closed by commit rL333226: [ValueTracking] Teach computeKnownBits that the result of an absolute value… (authored by ctopper). · Explain WhyMay 24 2018, 2:27 PM
This revision was automatically updated to reflect the committed changes.
vitalybuka reopened this revision.May 25 2018, 11:30 AM
vitalybuka added a subscriber: vitalybuka.

Reverted in r333253

This revision is now accepted and ready to land.May 25 2018, 11:30 AM
vitalybuka added a comment.May 25 2018, 11:31 AM

It should be safe to reland after r333295

Closed by commit rL333300: Recommit r333226 "[ValueTracking] Teach computeKnownBits that the result of an… (authored by ctopper). · Explain WhyMay 25 2018, 12:22 PM
This revision was automatically updated to reflect the committed changes.
spatel mentioned this in D47831: [DAGCombiner] Recognize more patterns for ABS.Jun 6 2018, 11:40 AM
spatel mentioned this in D53844: [InstSimplify] fold icmp based on range of abs/nabs.Oct 29 2018, 3:45 PM
spatel mentioned this in rL345717: [InstSimplify] fold icmp based on range of abs/nabs.Oct 31 2018, 6:28 AM

Revision Contents

PathSize
llvm/
trunk/
lib/
Analysis/
6 lines
test/
Transforms/
InstCombine/
11 lines
16 lines

Diff 148649

llvm/trunk/lib/Analysis/ValueTracking.cpp

Show First 20 Lines • Show All 1,072 Lines • ▼ Show 20 Lines if (SPF == SPF_SMAX) {
// leading one bits. // leading one bits.
MaxHighOnes = MaxHighOnes =
std::max(Known.countMinLeadingOnes(), Known2.countMinLeadingOnes()); std::max(Known.countMinLeadingOnes(), Known2.countMinLeadingOnes());
} else if (SPF == SPF_UMIN) { } else if (SPF == SPF_UMIN) {
// We can derive an upper bound on the result by taking the max of the // We can derive an upper bound on the result by taking the max of the
// leading zero bits. // leading zero bits.
MaxHighZeros = MaxHighZeros =
std::max(Known.countMinLeadingZeros(), Known2.countMinLeadingZeros()); std::max(Known.countMinLeadingZeros(), Known2.countMinLeadingZeros());
} else if (SPF == SPF_ABS) {
// RHS from matchSelectPattern returns the negation part of abs pattern.
// If the negate has an NSW flag we can assume the sign bit of the result
// will be 0 because that makes abs(INT_MIN) undefined.
if (cast<Instruction>(RHS)->hasNoSignedWrap())
MaxHighZeros = 1;
} }
// Only known if known in both the LHS and RHS. // Only known if known in both the LHS and RHS.
Known.One &= Known2.One; Known.One &= Known2.One;
Known.Zero &= Known2.Zero; Known.Zero &= Known2.Zero;
if (MaxHighOnes > 0) if (MaxHighOnes > 0)
Known.One.setHighBits(MaxHighOnes); Known.One.setHighBits(MaxHighOnes);
if (MaxHighZeros > 0) if (MaxHighZeros > 0)
▲ Show 20 Lines • Show All 3,986 Lines • Show Last 20 Lines

llvm/trunk/test/Transforms/InstCombine/abs-1.ll

Show First 20 Lines • Show All 287 Lines • ▼ Show 20 Lines
; CHECK-NEXT: ret <2 x i8> [[S]] ; CHECK-NEXT: ret <2 x i8> [[S]]
; ;
%n = sub <2 x i8> zeroinitializer, %x %n = sub <2 x i8> zeroinitializer, %x
%c = icmp slt <2 x i8> %x, zeroinitializer %c = icmp slt <2 x i8> %x, zeroinitializer
%s = select <2 x i1> %c, <2 x i8> %x, <2 x i8> %n %s = select <2 x i1> %c, <2 x i8> %x, <2 x i8> %n
%r = sub <2 x i8> zeroinitializer, %s %r = sub <2 x i8> zeroinitializer, %s
ret <2 x i8> %r ret <2 x i8> %r
} }
define i1 @abs_must_be_positive(i32 %x) {
; CHECK-LABEL: @abs_must_be_positive(
; CHECK-NEXT: ret i1 true
;
%negx = sub nsw i32 0, %x
%c = icmp sge i32 %x, 0
%sel = select i1 %c, i32 %x, i32 %negx
%c2 = icmp sge i32 %sel, 0
ret i1 %c2
}

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

Show First 20 Lines • Show All 927 Lines • ▼ Show 20 Lines;
%cond18 = select i1 %cmp1, i32 %sub9, i32 %cond %cond18 = select i1 %cmp1, i32 %sub9, i32 %cond
ret i32 %cond18 ret i32 %cond18
} }
define i32 @nabs_abs_x09(i32 %x) { define i32 @nabs_abs_x09(i32 %x) {
; CHECK-LABEL: @nabs_abs_x09( ; CHECK-LABEL: @nabs_abs_x09(
; CHECK-NEXT: [[CMP:%.*]] = icmp slt i32 [[X:%.*]], 0 ; CHECK-NEXT: [[CMP:%.*]] = icmp slt i32 [[X:%.*]], 0
; CHECK-NEXT: [[SUB:%.*]] = sub nsw i32 0, [[X]] ; CHECK-NEXT: [[SUB:%.*]] = sub nsw i32 0, [[X]]
; CHECK-NEXT: [[COND1:%.*]] = select i1 [[CMP]], i32 [[X]], i32 [[SUB]] ; CHECK-NEXT: [[COND:%.*]] = select i1 [[CMP]], i32 [[X]], i32 [[SUB]]
; CHECK-NEXT: ret i32 [[COND1]] ; CHECK-NEXT: ret i32 [[COND]]
; ;
%cmp = icmp sgt i32 %x, -1 %cmp = icmp sgt i32 %x, -1
%sub = sub nsw i32 0, %x %sub = sub nsw i32 0, %x
%cond = select i1 %cmp, i32 %x, i32 %sub %cond = select i1 %cmp, i32 %x, i32 %sub
%cmp1 = icmp slt i32 %cond, 0 %cmp1 = icmp slt i32 %cond, 0
%sub16 = sub nsw i32 0, %cond %sub16 = sub nsw i32 0, %cond
%cond18 = select i1 %cmp1, i32 %cond, i32 %sub16 %cond18 = select i1 %cmp1, i32 %cond, i32 %sub16
ret i32 %cond18 ret i32 %cond18
} }
define i32 @nabs_abs_x10(i32 %x) { define i32 @nabs_abs_x10(i32 %x) {
; CHECK-LABEL: @nabs_abs_x10( ; CHECK-LABEL: @nabs_abs_x10(
; CHECK-NEXT: [[CMP:%.*]] = icmp slt i32 [[X:%.*]], 0 ; CHECK-NEXT: [[CMP:%.*]] = icmp slt i32 [[X:%.*]], 0
; CHECK-NEXT: [[SUB:%.*]] = sub nsw i32 0, [[X]] ; CHECK-NEXT: [[SUB:%.*]] = sub nsw i32 0, [[X]]
; CHECK-NEXT: [[COND1:%.*]] = select i1 [[CMP]], i32 [[X]], i32 [[SUB]] ; CHECK-NEXT: [[COND:%.*]] = select i1 [[CMP]], i32 [[X]], i32 [[SUB]]
; CHECK-NEXT: ret i32 [[COND1]] ; CHECK-NEXT: ret i32 [[COND]]
; ;
%cmp = icmp sgt i32 %x, 0 %cmp = icmp sgt i32 %x, 0
%sub = sub nsw i32 0, %x %sub = sub nsw i32 0, %x
%cond = select i1 %cmp, i32 %x, i32 %sub %cond = select i1 %cmp, i32 %x, i32 %sub
%cmp1 = icmp slt i32 %cond, 0 %cmp1 = icmp slt i32 %cond, 0
%sub16 = sub nsw i32 0, %cond %sub16 = sub nsw i32 0, %cond
%cond18 = select i1 %cmp1, i32 %cond, i32 %sub16 %cond18 = select i1 %cmp1, i32 %cond, i32 %sub16
ret i32 %cond18 ret i32 %cond18
} }
define i32 @nabs_abs_x11(i32 %x) { define i32 @nabs_abs_x11(i32 %x) {
; CHECK-LABEL: @nabs_abs_x11( ; CHECK-LABEL: @nabs_abs_x11(
; CHECK-NEXT: [[CMP:%.*]] = icmp slt i32 [[X:%.*]], 0 ; CHECK-NEXT: [[CMP:%.*]] = icmp slt i32 [[X:%.*]], 0
; CHECK-NEXT: [[SUB:%.*]] = sub nsw i32 0, [[X]] ; CHECK-NEXT: [[SUB:%.*]] = sub nsw i32 0, [[X]]
; CHECK-NEXT: [[COND1:%.*]] = select i1 [[CMP]], i32 [[X]], i32 [[SUB]] ; CHECK-NEXT: [[COND:%.*]] = select i1 [[CMP]], i32 [[X]], i32 [[SUB]]
; CHECK-NEXT: ret i32 [[COND1]] ; CHECK-NEXT: ret i32 [[COND]]
; ;
%cmp = icmp slt i32 %x, 0 %cmp = icmp slt i32 %x, 0
%sub = sub nsw i32 0, %x %sub = sub nsw i32 0, %x
%cond = select i1 %cmp, i32 %sub, i32 %x %cond = select i1 %cmp, i32 %sub, i32 %x
%cmp1 = icmp slt i32 %cond, 0 %cmp1 = icmp slt i32 %cond, 0
%sub16 = sub nsw i32 0, %cond %sub16 = sub nsw i32 0, %cond
%cond18 = select i1 %cmp1, i32 %cond, i32 %sub16 %cond18 = select i1 %cmp1, i32 %cond, i32 %sub16
ret i32 %cond18 ret i32 %cond18
} }
define i32 @nabs_abs_x12(i32 %x) { define i32 @nabs_abs_x12(i32 %x) {
; CHECK-LABEL: @nabs_abs_x12( ; CHECK-LABEL: @nabs_abs_x12(
; CHECK-NEXT: [[CMP:%.*]] = icmp slt i32 [[X:%.*]], 0 ; CHECK-NEXT: [[CMP:%.*]] = icmp slt i32 [[X:%.*]], 0
; CHECK-NEXT: [[SUB:%.*]] = sub nsw i32 0, [[X]] ; CHECK-NEXT: [[SUB:%.*]] = sub nsw i32 0, [[X]]
; CHECK-NEXT: [[COND1:%.*]] = select i1 [[CMP]], i32 [[X]], i32 [[SUB]] ; CHECK-NEXT: [[COND:%.*]] = select i1 [[CMP]], i32 [[X]], i32 [[SUB]]
; CHECK-NEXT: ret i32 [[COND1]] ; CHECK-NEXT: ret i32 [[COND]]
; ;
%cmp = icmp slt i32 %x, 1 %cmp = icmp slt i32 %x, 1
%sub = sub nsw i32 0, %x %sub = sub nsw i32 0, %x
%cond = select i1 %cmp, i32 %sub, i32 %x %cond = select i1 %cmp, i32 %sub, i32 %x
%cmp1 = icmp slt i32 %cond, 0 %cmp1 = icmp slt i32 %cond, 0
%sub16 = sub nsw i32 0, %cond %sub16 = sub nsw i32 0, %cond
%cond18 = select i1 %cmp1, i32 %cond, i32 %sub16 %cond18 = select i1 %cmp1, i32 %cond, i32 %sub16
ret i32 %cond18 ret i32 %cond18
▲ Show 20 Lines • Show All 66 Lines • Show Last 20 Lines