This is an archive of the discontinued LLVM Phabricator instance.

Differential D157307

[ValueTracking] Add support for `fshl`/`fshr` in `isKnownToBeAPowerOfTwo`
ClosedPublic

Authored by goldstein.w.n on Aug 7 2023, 10:47 AM.

Details

Reviewers
nikic
Allen
Commits
rG4f818daca64c: [ValueTracking] Add support for `fshl`/`fshr` in `isKnownToBeAPowerOfTwo`
Summary

If the funnel shifts are rotates (op0 == op1) then the number of 1s/0s
don't change so we can just look through op0/op1.

Proofs: https://alive2.llvm.org/ce/z/Pja5yu

Diff Detail

Unit TestsFailed

TimeTest
60,030 msx64 debian > MLIR.Examples/standalone::test.toy

Event Timeline

goldstein.w.n created this revision.Aug 7 2023, 10:47 AM
Herald added a project: Restricted Project. · View Herald TranscriptAug 7 2023, 10:47 AM
Herald added subscribers: StephenFan, hiraditya. · View Herald Transcript
goldstein.w.n requested review of this revision.Aug 7 2023, 10:47 AM
Herald added a project: Restricted Project. · View Herald TranscriptAug 7 2023, 10:47 AM
Herald added a subscriber: llvm-commits. · View Herald Transcript
Harbormaster completed remote builds in B250838: Diff 547854.Aug 7 2023, 10:49 AM
goldstein.w.n added a child revision: D157308: [ValueTracking] Add support for `mul` in `isKnownToBeAPowerOfTwo`.Aug 7 2023, 10:50 AM
goldstein.w.n added a parent revision: D157306: [ValueTracking] Add support for `bswap` and `bitreverse` in `isKnownToBeAPowerOfTwo`.
nikic accepted this revision.Aug 7 2023, 11:26 AM

LGTM

This revision is now accepted and ready to land.Aug 7 2023, 11:26 AM
goldstein.w.n updated this revision to Diff 547890.Aug 7 2023, 11:48 AM

Rebase

Harbormaster completed remote builds in B250871: Diff 547890.Aug 7 2023, 4:02 PM
goldstein.w.n updated this revision to Diff 548701.Aug 9 2023, 11:30 AM

Rebase

This revision was landed with ongoing or failed builds.Aug 9 2023, 12:45 PM
Closed by commit rG4f818daca64c: [ValueTracking] Add support for `fshl`/`fshr` in `isKnownToBeAPowerOfTwo` (authored by goldstein.w.n). · Explain Why
This revision was automatically updated to reflect the committed changes.
goldstein.w.n added a commit: rG4f818daca64c: [ValueTracking] Add support for `fshl`/`fshr` in `isKnownToBeAPowerOfTwo`.
Harbormaster completed remote builds in B251444: Diff 548701.Aug 9 2023, 2:52 PM

Revision Contents

PathSize
llvm/
lib/
Analysis/
6 lines
test/
Analysis/
ValueTracking/
10 lines

Diff 548701

llvm/lib/Analysis/ValueTracking.cpp

  • This file is larger than 256 KB, so syntax highlighting is disabled by default.
Show First 20 Lines • Show All 2,131 Lines • ▼ Show 20 Lines if (auto *II = dyn_cast<IntrinsicInst>(I)) {
case Intrinsic::smin: case Intrinsic::smin:
return isKnownToBeAPowerOfTwo(II->getArgOperand(1), OrZero, Depth, Q) && return isKnownToBeAPowerOfTwo(II->getArgOperand(1), OrZero, Depth, Q) &&
isKnownToBeAPowerOfTwo(II->getArgOperand(0), OrZero, Depth, Q); isKnownToBeAPowerOfTwo(II->getArgOperand(0), OrZero, Depth, Q);
// bswap/bitreverse just move around bits, but don't change any 1s/0s // bswap/bitreverse just move around bits, but don't change any 1s/0s
// thus dont change pow2/non-pow2 status. // thus dont change pow2/non-pow2 status.
case Intrinsic::bitreverse: case Intrinsic::bitreverse:
case Intrinsic::bswap: case Intrinsic::bswap:
return isKnownToBeAPowerOfTwo(II->getArgOperand(0), OrZero, Depth, Q); return isKnownToBeAPowerOfTwo(II->getArgOperand(0), OrZero, Depth, Q);
case Intrinsic::fshr:
case Intrinsic::fshl:
// If Op0 == Op1, this is a rotate. is_pow2(rotate(x, y)) == is_pow2(x)
if (II->getArgOperand(0) == II->getArgOperand(1))
return isKnownToBeAPowerOfTwo(II->getArgOperand(0), OrZero, Depth, Q);
break;
default: default:
break; break;
} }
} }
return false; return false;
} }
default: default:
return false; return false;
▲ Show 20 Lines • Show All 6,668 Lines • Show Last 20 Lines

llvm/test/Analysis/ValueTracking/known-power-of-two.ll

Show First 20 Lines • Show All 208 Lines • ▼ Show 20 Lines;
ret i1 %r ret i1 %r
} }
define i16 @fshl_is_pow2_or_zero(i16 %x, i16 %y, i16 %z) { define i16 @fshl_is_pow2_or_zero(i16 %x, i16 %y, i16 %z) {
; CHECK-LABEL: define i16 @fshl_is_pow2_or_zero ; CHECK-LABEL: define i16 @fshl_is_pow2_or_zero
; CHECK-SAME: (i16 [[X:%.*]], i16 [[Y:%.*]], i16 [[Z:%.*]]) { ; CHECK-SAME: (i16 [[X:%.*]], i16 [[Y:%.*]], i16 [[Z:%.*]]) {
; CHECK-NEXT: [[XP2:%.*]] = shl i16 4, [[X]] ; CHECK-NEXT: [[XP2:%.*]] = shl i16 4, [[X]]
; CHECK-NEXT: [[XX:%.*]] = call i16 @llvm.fshl.i16(i16 [[XP2]], i16 [[XP2]], i16 [[Z]]) ; CHECK-NEXT: [[XX:%.*]] = call i16 @llvm.fshl.i16(i16 [[XP2]], i16 [[XP2]], i16 [[Z]])
; CHECK-NEXT: [[R:%.*]] = urem i16 [[Y]], [[XX]] ; CHECK-NEXT: [[TMP1:%.*]] = add i16 [[XX]], -1
; CHECK-NEXT: [[R:%.*]] = and i16 [[TMP1]], [[Y]]
; CHECK-NEXT: ret i16 [[R]] ; CHECK-NEXT: ret i16 [[R]]
; ;
%xp2 = shl i16 4, %x %xp2 = shl i16 4, %x
%xx = call i16 @llvm.fshl.i16(i16 %xp2, i16 %xp2, i16 %z) %xx = call i16 @llvm.fshl.i16(i16 %xp2, i16 %xp2, i16 %z)
%r = urem i16 %y, %xx %r = urem i16 %y, %xx
ret i16 %r ret i16 %r
} }
Show All 31 Lines
} }
define i1 @fshl_is_pow2(i16 %x, i16 %y, i16 %z) { define i1 @fshl_is_pow2(i16 %x, i16 %y, i16 %z) {
; CHECK-LABEL: define i1 @fshl_is_pow2 ; CHECK-LABEL: define i1 @fshl_is_pow2
; CHECK-SAME: (i16 [[X:%.*]], i16 [[Y:%.*]], i16 [[Z:%.*]]) { ; CHECK-SAME: (i16 [[X:%.*]], i16 [[Y:%.*]], i16 [[Z:%.*]]) {
; CHECK-NEXT: [[XP2:%.*]] = shl nuw i16 1, [[X]] ; CHECK-NEXT: [[XP2:%.*]] = shl nuw i16 1, [[X]]
; CHECK-NEXT: [[XX:%.*]] = call i16 @llvm.fshl.i16(i16 [[XP2]], i16 [[XP2]], i16 [[Z]]) ; CHECK-NEXT: [[XX:%.*]] = call i16 @llvm.fshl.i16(i16 [[XP2]], i16 [[XP2]], i16 [[Z]])
; CHECK-NEXT: [[AND:%.*]] = and i16 [[XX]], [[Y]] ; CHECK-NEXT: [[AND:%.*]] = and i16 [[XX]], [[Y]]
; CHECK-NEXT: [[R:%.*]] = icmp eq i16 [[AND]], [[XX]] ; CHECK-NEXT: [[R:%.*]] = icmp ne i16 [[AND]], 0
; CHECK-NEXT: ret i1 [[R]] ; CHECK-NEXT: ret i1 [[R]]
; ;
%xp2 = shl i16 1, %x %xp2 = shl i16 1, %x
%xx = call i16 @llvm.fshl.i16(i16 %xp2, i16 %xp2, i16 %z) %xx = call i16 @llvm.fshl.i16(i16 %xp2, i16 %xp2, i16 %z)
%and = and i16 %y, %xx %and = and i16 %y, %xx
%r = icmp eq i16 %and, %xx %r = icmp eq i16 %and, %xx
ret i1 %r ret i1 %r
Show All 16 Lines;
ret i1 %r ret i1 %r
} }
define i16 @fshr_is_pow2_or_zero(i16 %x, i16 %y, i16 %z) { define i16 @fshr_is_pow2_or_zero(i16 %x, i16 %y, i16 %z) {
; CHECK-LABEL: define i16 @fshr_is_pow2_or_zero ; CHECK-LABEL: define i16 @fshr_is_pow2_or_zero
; CHECK-SAME: (i16 [[X:%.*]], i16 [[Y:%.*]], i16 [[Z:%.*]]) { ; CHECK-SAME: (i16 [[X:%.*]], i16 [[Y:%.*]], i16 [[Z:%.*]]) {
; CHECK-NEXT: [[XP2:%.*]] = shl i16 4, [[X]] ; CHECK-NEXT: [[XP2:%.*]] = shl i16 4, [[X]]
; CHECK-NEXT: [[XX:%.*]] = call i16 @llvm.fshr.i16(i16 [[XP2]], i16 [[XP2]], i16 [[Z]]) ; CHECK-NEXT: [[XX:%.*]] = call i16 @llvm.fshr.i16(i16 [[XP2]], i16 [[XP2]], i16 [[Z]])
; CHECK-NEXT: [[R:%.*]] = urem i16 [[Y]], [[XX]] ; CHECK-NEXT: [[TMP1:%.*]] = add i16 [[XX]], -1
; CHECK-NEXT: [[R:%.*]] = and i16 [[TMP1]], [[Y]]
; CHECK-NEXT: ret i16 [[R]] ; CHECK-NEXT: ret i16 [[R]]
; ;
%xp2 = shl i16 4, %x %xp2 = shl i16 4, %x
%xx = call i16 @llvm.fshr.i16(i16 %xp2, i16 %xp2, i16 %z) %xx = call i16 @llvm.fshr.i16(i16 %xp2, i16 %xp2, i16 %z)
%r = urem i16 %y, %xx %r = urem i16 %y, %xx
ret i16 %r ret i16 %r
} }
Show All 31 Lines
} }
define i1 @fshr_is_pow2(i16 %x, i16 %y, i16 %z) { define i1 @fshr_is_pow2(i16 %x, i16 %y, i16 %z) {
; CHECK-LABEL: define i1 @fshr_is_pow2 ; CHECK-LABEL: define i1 @fshr_is_pow2
; CHECK-SAME: (i16 [[X:%.*]], i16 [[Y:%.*]], i16 [[Z:%.*]]) { ; CHECK-SAME: (i16 [[X:%.*]], i16 [[Y:%.*]], i16 [[Z:%.*]]) {
; CHECK-NEXT: [[XP2:%.*]] = shl nuw i16 1, [[X]] ; CHECK-NEXT: [[XP2:%.*]] = shl nuw i16 1, [[X]]
; CHECK-NEXT: [[XX:%.*]] = call i16 @llvm.fshr.i16(i16 [[XP2]], i16 [[XP2]], i16 [[Z]]) ; CHECK-NEXT: [[XX:%.*]] = call i16 @llvm.fshr.i16(i16 [[XP2]], i16 [[XP2]], i16 [[Z]])
; CHECK-NEXT: [[AND:%.*]] = and i16 [[XX]], [[Y]] ; CHECK-NEXT: [[AND:%.*]] = and i16 [[XX]], [[Y]]
; CHECK-NEXT: [[R:%.*]] = icmp eq i16 [[AND]], [[XX]] ; CHECK-NEXT: [[R:%.*]] = icmp ne i16 [[AND]], 0
; CHECK-NEXT: ret i1 [[R]] ; CHECK-NEXT: ret i1 [[R]]
; ;
%xp2 = shl i16 1, %x %xp2 = shl i16 1, %x
%xx = call i16 @llvm.fshr.i16(i16 %xp2, i16 %xp2, i16 %z) %xx = call i16 @llvm.fshr.i16(i16 %xp2, i16 %xp2, i16 %z)
%and = and i16 %y, %xx %and = and i16 %y, %xx
%r = icmp eq i16 %and, %xx %r = icmp eq i16 %and, %xx
ret i1 %r ret i1 %r
▲ Show 20 Lines • Show All 289 Lines • Show Last 20 Lines