This is an archive of the discontinued LLVM Phabricator instance.

Differential D157306

[ValueTracking] Add support for `bswap` and `bitreverse` in `isKnownToBeAPowerOfTwo`
ClosedPublic

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

Details

Reviewers
nikic
Allen
Commits
rG6f4d660d7faa: [ValueTracking] Add support for `bswap` and `bitreverse` in…
Summary

Both of these intrinsics don't change the number of 1s/0s so we can
look directly through them.

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

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 B250836: Diff 547852.Aug 7 2023, 10:48 AM
goldstein.w.n added a child revision: D157307: [ValueTracking] Add support for `fshl`/`fshr` in `isKnownToBeAPowerOfTwo`.Aug 7 2023, 10:50 AM
goldstein.w.n added a parent revision: D157305: [ValueTracking] Use switch for Intrinsics in `isKnownToBePowerOfTwo`; NFC.
nikic accepted this revision.Aug 7 2023, 11:23 AM

LGTM

This revision is now accepted and ready to land.Aug 7 2023, 11:23 AM
goldstein.w.n updated this revision to Diff 547889.Aug 7 2023, 11:47 AM

Rebase

Harbormaster completed remote builds in B250870: Diff 547889.Aug 7 2023, 4:14 PM
goldstein.w.n updated this revision to Diff 548700.Aug 9 2023, 11:29 AM

Rebase

This revision was landed with ongoing or failed builds.Aug 9 2023, 12:45 PM
Closed by commit rG6f4d660d7faa: [ValueTracking] Add support for `bswap` and `bitreverse` in… (authored by goldstein.w.n). · Explain Why
This revision was automatically updated to reflect the committed changes.
goldstein.w.n added a commit: rG6f4d660d7faa: [ValueTracking] Add support for `bswap` and `bitreverse` in….
Harbormaster completed remote builds in B251443: Diff 548700.Aug 9 2023, 3:04 PM

Revision Contents

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

Diff 547889

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,133 Lines • ▼ Show 20 Lines case Instruction::Call: {
if (auto *II = dyn_cast<IntrinsicInst>(I)) { if (auto *II = dyn_cast<IntrinsicInst>(I)) {
switch (II->getIntrinsicID()) { switch (II->getIntrinsicID()) {
case Intrinsic::umax: case Intrinsic::umax:
case Intrinsic::smax: case Intrinsic::smax:
case Intrinsic::umin: case Intrinsic::umin:
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
// thus dont change pow2/non-pow2 status.
case Intrinsic::bitreverse:
case Intrinsic::bswap:
return isKnownToBeAPowerOfTwo(II->getArgOperand(0), OrZero, Depth, Q);
default: default:
break; break;
} }
} }
return false; return false;
} }
default: default:
return false; return false;
▲ Show 20 Lines • Show All 6,675 Lines • Show Last 20 Lines

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

Show First 20 Lines • Show All 78 Lines • ▼ Show 20 Lines;
ret i1 %r ret i1 %r
} }
define i16 @bswap_is_pow2_or_zero(i16 %x, i16 %y) { define i16 @bswap_is_pow2_or_zero(i16 %x, i16 %y) {
; CHECK-LABEL: define i16 @bswap_is_pow2_or_zero ; CHECK-LABEL: define i16 @bswap_is_pow2_or_zero
; CHECK-SAME: (i16 [[X:%.*]], i16 [[Y:%.*]]) { ; CHECK-SAME: (i16 [[X:%.*]], i16 [[Y:%.*]]) {
; CHECK-NEXT: [[XP2:%.*]] = shl i16 4, [[X]] ; CHECK-NEXT: [[XP2:%.*]] = shl i16 4, [[X]]
; CHECK-NEXT: [[XX:%.*]] = call i16 @llvm.bswap.i16(i16 [[XP2]]) ; CHECK-NEXT: [[XX:%.*]] = call i16 @llvm.bswap.i16(i16 [[XP2]])
; 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.bswap.i16(i16 %xp2) %xx = call i16 @llvm.bswap.i16(i16 %xp2)
%r = urem i16 %y, %xx %r = urem i16 %y, %xx
ret i16 %r ret i16 %r
} }
Show All 14 Lines
} }
define i1 @bswap_is_pow2(i16 %x, i16 %y) { define i1 @bswap_is_pow2(i16 %x, i16 %y) {
; CHECK-LABEL: define i1 @bswap_is_pow2 ; CHECK-LABEL: define i1 @bswap_is_pow2
; CHECK-SAME: (i16 [[X:%.*]], i16 [[Y:%.*]]) { ; CHECK-SAME: (i16 [[X:%.*]], i16 [[Y:%.*]]) {
; CHECK-NEXT: [[XP2:%.*]] = shl nuw i16 1, [[X]] ; CHECK-NEXT: [[XP2:%.*]] = shl nuw i16 1, [[X]]
; CHECK-NEXT: [[XX:%.*]] = call i16 @llvm.bswap.i16(i16 [[XP2]]) ; CHECK-NEXT: [[XX:%.*]] = call i16 @llvm.bswap.i16(i16 [[XP2]])
; 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.bswap.i16(i16 %xp2) %xx = call i16 @llvm.bswap.i16(i16 %xp2)
%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 @bitreverse_is_pow2_or_zero(i16 %x, i16 %y) { define i16 @bitreverse_is_pow2_or_zero(i16 %x, i16 %y) {
; CHECK-LABEL: define i16 @bitreverse_is_pow2_or_zero ; CHECK-LABEL: define i16 @bitreverse_is_pow2_or_zero
; CHECK-SAME: (i16 [[X:%.*]], i16 [[Y:%.*]]) { ; CHECK-SAME: (i16 [[X:%.*]], i16 [[Y:%.*]]) {
; CHECK-NEXT: [[XP2:%.*]] = shl i16 4, [[X]] ; CHECK-NEXT: [[XP2:%.*]] = shl i16 4, [[X]]
; CHECK-NEXT: [[XX:%.*]] = call i16 @llvm.bitreverse.i16(i16 [[XP2]]) ; CHECK-NEXT: [[XX:%.*]] = call i16 @llvm.bitreverse.i16(i16 [[XP2]])
; CHECK-NEXT: [[R:%.*]] = urem i16 [[Y]], [[XX]] ; CHECK-NEXT: [[TMP1:%.*]] = add nsw 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.bitreverse.i16(i16 %xp2) %xx = call i16 @llvm.bitreverse.i16(i16 %xp2)
%r = urem i16 %y, %xx %r = urem i16 %y, %xx
ret i16 %r ret i16 %r
} }
Show All 14 Lines
} }
define i1 @bitreverse_is_pow2(i16 %x, i16 %y) { define i1 @bitreverse_is_pow2(i16 %x, i16 %y) {
; CHECK-LABEL: define i1 @bitreverse_is_pow2 ; CHECK-LABEL: define i1 @bitreverse_is_pow2
; CHECK-SAME: (i16 [[X:%.*]], i16 [[Y:%.*]]) { ; CHECK-SAME: (i16 [[X:%.*]], i16 [[Y:%.*]]) {
; CHECK-NEXT: [[XP2:%.*]] = shl nuw i16 1, [[X]] ; CHECK-NEXT: [[XP2:%.*]] = shl nuw i16 1, [[X]]
; CHECK-NEXT: [[XX:%.*]] = call i16 @llvm.bitreverse.i16(i16 [[XP2]]) ; CHECK-NEXT: [[XX:%.*]] = call i16 @llvm.bitreverse.i16(i16 [[XP2]])
; 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.bitreverse.i16(i16 %xp2) %xx = call i16 @llvm.bitreverse.i16(i16 %xp2)
%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 451 Lines • Show Last 20 Lines