This is an archive of the discontinued LLVM Phabricator instance.

Differential D127469

[InstCombine] Optimize lshr+shl+and conversion pattern
ClosedPublic

Authored by bcl5980 on Jun 9 2022, 8:09 PM.

Details

Reviewers
spatel
RKSimon
craig.topper
nikic
Commits
rG286198ff043a: [InstCombine] Optimize lshr+shl+and conversion pattern
Summary

if C1 and C3 are pow2 and Log2(C3) >= C2:

((C1 >> X) << C2) & C3 -> X == (Log2(C1)+C2-Log2(C3)) ? C3 : 0

https://alive2.llvm.org/ce/z/zvrkKF

Diff Detail

Unit TestsFailed

TimeTest
60,050 msx64 debian > MLIR.Examples/standalone::test.toy
60,040 msx64 debian > libFuzzer.libFuzzer::value-profile-load.test

Event Timeline

bcl5980 created this revision.Jun 9 2022, 8:09 PM
Herald added a project: Restricted Project. · View Herald TranscriptJun 9 2022, 8:09 PM
Herald added subscribers: StephenFan, hiraditya. · View Herald Transcript
bcl5980 requested review of this revision.Jun 9 2022, 8:09 PM
Herald added a project: Restricted Project. · View Herald TranscriptJun 9 2022, 8:09 PM
Herald added a subscriber: llvm-commits. · View Herald Transcript
bcl5980 updated this revision to Diff 435778.Jun 9 2022, 8:12 PM

update test

bcl5980 updated this revision to Diff 435783.Jun 9 2022, 8:40 PM
bcl5980 edited the summary of this revision. (Show Details)

C3 support non-uniform constant for shl+lshr and lshr+shl
update tests.

bcl5980 updated this revision to Diff 435791.Jun 9 2022, 8:58 PM

add nullptr check

Harbormaster completed remote builds in B169003: Diff 435791.Jun 9 2022, 9:57 PM
spatel added a comment.Jun 10 2022, 9:14 AM

I don't like increasing risk by combining what are really 2 independent changes into 1 patch.
Please go back to the earlier revision that only adds the new fold. We can ease the vector restrictions as a second step (I haven't seen any evidence that those cases matter, but it opens up more possibilities to miscompile in ways that are very hard to detect).

bcl5980 updated this revision to Diff 436141.Jun 11 2022, 7:10 AM

revert to diff2

bcl5980 edited the summary of this revision. (Show Details)Jun 11 2022, 7:11 AM
Harbormaster completed remote builds in B169241: Diff 436141.Jun 11 2022, 7:53 AM
spatel accepted this revision.Jun 13 2022, 7:23 AM

LGTM

This revision is now accepted and ready to land.Jun 13 2022, 7:23 AM
This revision was landed with ongoing or failed builds.Jun 13 2022, 8:06 PM
Closed by commit rG286198ff043a: [InstCombine] Optimize lshr+shl+and conversion pattern (authored by bcl5980). · Explain Why
This revision was automatically updated to reflect the committed changes.
bcl5980 added a commit: rG286198ff043a: [InstCombine] Optimize lshr+shl+and conversion pattern.

Revision Contents

PathSize
llvm/
lib/
Transforms/
InstCombine/
49 lines
test/
Transforms/
InstCombine/
20 lines

Diff 436141

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

Show First 20 Lines • Show All 1,909 Lines • ▼ Show 20 Lines if (match(Op0, m_OneUse(m_BinOp(BO))) && isNarrowableBinOpcode(BO)) {
Builder.CreateBinOp(BOpcode, TrY, X, BO->getName() + ".narrow"); Builder.CreateBinOp(BOpcode, TrY, X, BO->getName() + ".narrow");
return new ZExtInst(NewBO, Ty); return new ZExtInst(NewBO, Ty);
} }
} }
Constant *C1, *C2; Constant *C1, *C2;
const APInt *C3 = C; const APInt *C3 = C;
Value *X; Value *X;
if (C3->isPowerOf2() && if (C3->isPowerOf2()) {
match(Op0, m_OneUse(m_LShr(m_Shl(m_ImmConstant(C1), m_Value(X)), Constant *Log2C3 = ConstantInt::get(Ty, C3->countTrailingZeros());
if (match(Op0, m_OneUse(m_LShr(m_Shl(m_ImmConstant(C1), m_Value(X)),
m_ImmConstant(C2)))) && m_ImmConstant(C2)))) &&
match(C1, m_Power2())) { match(C1, m_Power2())) {
Constant *Log2C1 = ConstantExpr::getExactLogBase2(C1); Constant *Log2C1 = ConstantExpr::getExactLogBase2(C1);
Constant *Log2C3 = ConstantInt::get(Ty, C3->countTrailingZeros());
Constant *LshrC = ConstantExpr::getAdd(C2, Log2C3); Constant *LshrC = ConstantExpr::getAdd(C2, Log2C3);
KnownBits KnownLShrc = computeKnownBits(LshrC, 0, nullptr); KnownBits KnownLShrc = computeKnownBits(LshrC, 0, nullptr);
if (KnownLShrc.getMaxValue().ult(Width)) { if (KnownLShrc.getMaxValue().ult(Width)) {
// iff C1,C3 is pow2 and C2 + cttz(C3) < BitWidth: // iff C1,C3 is pow2 and C2 + cttz(C3) < BitWidth:
// ((C1 << X) >> C2) & C3 -> X == (cttz(C3)+C2-cttz(C1)) ? C3 : 0 // ((C1 << X) >> C2) & C3 -> X == (cttz(C3)+C2-cttz(C1)) ? C3 : 0
Constant *CmpC = ConstantExpr::getSub(LshrC, Log2C1); Constant *CmpC = ConstantExpr::getSub(LshrC, Log2C1);
Value *Cmp = Builder.CreateICmpEQ(X, CmpC); Value *Cmp = Builder.CreateICmpEQ(X, CmpC);
return SelectInst::Create(Cmp, ConstantInt::get(Ty, *C3), return SelectInst::Create(Cmp, ConstantInt::get(Ty, *C3),
ConstantInt::getNullValue(Ty)); ConstantInt::getNullValue(Ty));
} }
// TODO: Symmetrical case }
if (match(Op0, m_OneUse(m_Shl(m_LShr(m_ImmConstant(C1), m_Value(X)),
m_ImmConstant(C2)))) &&
match(C1, m_Power2())) {
Constant *Log2C1 = ConstantExpr::getExactLogBase2(C1);
Constant *Cmp =
ConstantExpr::getCompare(ICmpInst::ICMP_ULT, Log2C3, C2);
if (Cmp->isZeroValue()) {
// iff C1,C3 is pow2 and Log2(C3) >= C2: // iff C1,C3 is pow2 and Log2(C3) >= C2:
// ((C1 >> X) << C2) & C3 -> X == (cttz(C1)+C2-cttz(C3)) ? C3 : 0 // ((C1 >> X) << C2) & C3 -> X == (cttz(C1)+C2-cttz(C3)) ? C3 : 0
Constant *ShlC = ConstantExpr::getAdd(C2, Log2C1);
Constant *CmpC = ConstantExpr::getSub(ShlC, Log2C3);
Value *Cmp = Builder.CreateICmpEQ(X, CmpC);
return SelectInst::Create(Cmp, ConstantInt::get(Ty, *C3),
ConstantInt::getNullValue(Ty));
}
}
} }
} }
if (match(&I, m_And(m_OneUse(m_Shl(m_ZExt(m_Value(X)), m_Value(Y))), if (match(&I, m_And(m_OneUse(m_Shl(m_ZExt(m_Value(X)), m_Value(Y))),
m_SignMask())) && m_SignMask())) &&
match(Y, m_SpecificInt_ICMP( match(Y, m_SpecificInt_ICMP(
ICmpInst::Predicate::ICMP_EQ, ICmpInst::Predicate::ICMP_EQ,
APInt(Ty->getScalarSizeInBits(), APInt(Ty->getScalarSizeInBits(),
▲ Show 20 Lines • Show All 1,827 Lines • Show Last 20 Lines

llvm/test/Transforms/InstCombine/and.ll

Show First 20 Lines • Show All 2,060 Lines • ▼ Show 20 Lines;
%r = xor i16 %and, 8 %r = xor i16 %and, 8
ret i16 %r ret i16 %r
} }
; Log2(LshrC) + ShlC >= BitWidth ; Log2(LshrC) + ShlC >= BitWidth
define i16 @lshr_shl_pow2_const_case2(i16 %x) { define i16 @lshr_shl_pow2_const_case2(i16 %x) {
; CHECK-LABEL: @lshr_shl_pow2_const_case2( ; CHECK-LABEL: @lshr_shl_pow2_const_case2(
; CHECK-NEXT: [[LSHR1:%.*]] = lshr i16 8192, [[X:%.*]] ; CHECK-NEXT: [[TMP1:%.*]] = icmp eq i16 [[X:%.*]], 12
; CHECK-NEXT: [[SHL:%.*]] = shl i16 [[LSHR1]], 4 ; CHECK-NEXT: [[R:%.*]] = select i1 [[TMP1]], i16 32, i16 0
; CHECK-NEXT: [[R:%.*]] = and i16 [[SHL]], 32
; CHECK-NEXT: ret i16 [[R]] ; CHECK-NEXT: ret i16 [[R]]
; ;
%lshr1 = lshr i16 8192, %x %lshr1 = lshr i16 8192, %x
%shl = shl i16 %lshr1, 4 %shl = shl i16 %lshr1, 4
%r = and i16 %shl, 32 %r = and i16 %shl, 32
ret i16 %r ret i16 %r
} }
Show All 21 Lines;
%shl = shl i16 %lshr1, 4 %shl = shl i16 %lshr1, 4
call void @use16(i16 %shl) call void @use16(i16 %shl)
%r = and i16 %shl, 32 %r = and i16 %shl, 32
ret i16 %r ret i16 %r
} }
define <3 x i16> @lshr_shl_pow2_const_case1_uniform_vec(<3 x i16> %x) { define <3 x i16> @lshr_shl_pow2_const_case1_uniform_vec(<3 x i16> %x) {
; CHECK-LABEL: @lshr_shl_pow2_const_case1_uniform_vec( ; CHECK-LABEL: @lshr_shl_pow2_const_case1_uniform_vec(
; CHECK-NEXT: [[LSHR:%.*]] = lshr <3 x i16> <i16 8192, i16 8192, i16 8192>, [[X:%.*]] ; CHECK-NEXT: [[TMP1:%.*]] = icmp eq <3 x i16> [[X:%.*]], <i16 12, i16 12, i16 12>
; CHECK-NEXT: [[SHL:%.*]] = shl <3 x i16> [[LSHR]], <i16 6, i16 6, i16 6> ; CHECK-NEXT: [[R:%.*]] = select <3 x i1> [[TMP1]], <3 x i16> <i16 128, i16 128, i16 128>, <3 x i16> zeroinitializer
; CHECK-NEXT: [[R:%.*]] = and <3 x i16> [[SHL]], <i16 128, i16 128, i16 128>
; CHECK-NEXT: ret <3 x i16> [[R]] ; CHECK-NEXT: ret <3 x i16> [[R]]
; ;
%lshr = lshr <3 x i16> <i16 8192, i16 8192, i16 8192>, %x %lshr = lshr <3 x i16> <i16 8192, i16 8192, i16 8192>, %x
%shl = shl <3 x i16> %lshr, <i16 6, i16 6, i16 6> %shl = shl <3 x i16> %lshr, <i16 6, i16 6, i16 6>
%r = and <3 x i16> %shl, <i16 128, i16 128, i16 128> %r = and <3 x i16> %shl, <i16 128, i16 128, i16 128>
ret <3 x i16> %r ret <3 x i16> %r
} }
Show All 20 Lines;
%lshr = lshr <3 x i16> <i16 8192, i16 16384, i16 32768>, %x %lshr = lshr <3 x i16> <i16 8192, i16 16384, i16 32768>, %x
%shl = shl <3 x i16> %lshr, <i16 8, i16 5, i16 3> %shl = shl <3 x i16> %lshr, <i16 8, i16 5, i16 3>
%r = and <3 x i16> %shl, <i16 128, i16 256, i16 512> %r = and <3 x i16> %shl, <i16 128, i16 256, i16 512>
ret <3 x i16> %r ret <3 x i16> %r
} }
define <3 x i16> @lshr_shl_pow2_const_case1_undef1_vec(<3 x i16> %x) { define <3 x i16> @lshr_shl_pow2_const_case1_undef1_vec(<3 x i16> %x) {
; CHECK-LABEL: @lshr_shl_pow2_const_case1_undef1_vec( ; CHECK-LABEL: @lshr_shl_pow2_const_case1_undef1_vec(
; CHECK-NEXT: [[LSHR:%.*]] = lshr <3 x i16> <i16 undef, i16 8192, i16 8192>, [[X:%.*]] ; CHECK-NEXT: [[TMP1:%.*]] = icmp eq <3 x i16> [[X:%.*]], <i16 -1, i16 12, i16 12>
; CHECK-NEXT: [[SHL:%.*]] = shl <3 x i16> [[LSHR]], <i16 6, i16 6, i16 6> ; CHECK-NEXT: [[R:%.*]] = select <3 x i1> [[TMP1]], <3 x i16> <i16 128, i16 128, i16 128>, <3 x i16> zeroinitializer
; CHECK-NEXT: [[R:%.*]] = and <3 x i16> [[SHL]], <i16 128, i16 128, i16 128>
; CHECK-NEXT: ret <3 x i16> [[R]] ; CHECK-NEXT: ret <3 x i16> [[R]]
; ;
%lshr = lshr <3 x i16> <i16 undef, i16 8192, i16 8192>, %x %lshr = lshr <3 x i16> <i16 undef, i16 8192, i16 8192>, %x
%shl = shl <3 x i16> %lshr, <i16 6, i16 6, i16 6> %shl = shl <3 x i16> %lshr, <i16 6, i16 6, i16 6>
%r = and <3 x i16> %shl, <i16 128, i16 128, i16 128> %r = and <3 x i16> %shl, <i16 128, i16 128, i16 128>
ret <3 x i16> %r ret <3 x i16> %r
} }
define <3 x i16> @lshr_shl_pow2_const_case1_undef2_vec(<3 x i16> %x) { define <3 x i16> @lshr_shl_pow2_const_case1_undef2_vec(<3 x i16> %x) {
; CHECK-LABEL: @lshr_shl_pow2_const_case1_undef2_vec( ; CHECK-LABEL: @lshr_shl_pow2_const_case1_undef2_vec(
; CHECK-NEXT: [[LSHR:%.*]] = lshr <3 x i16> <i16 8192, i16 8192, i16 8192>, [[X:%.*]] ; CHECK-NEXT: [[TMP1:%.*]] = icmp eq <3 x i16> [[X:%.*]], <i16 undef, i16 12, i16 12>
; CHECK-NEXT: [[SHL:%.*]] = shl <3 x i16> [[LSHR]], <i16 undef, i16 6, i16 6> ; CHECK-NEXT: [[R:%.*]] = select <3 x i1> [[TMP1]], <3 x i16> <i16 128, i16 128, i16 128>, <3 x i16> zeroinitializer
; CHECK-NEXT: [[R:%.*]] = and <3 x i16> [[SHL]], <i16 128, i16 128, i16 128>
; CHECK-NEXT: ret <3 x i16> [[R]] ; CHECK-NEXT: ret <3 x i16> [[R]]
; ;
%lshr = lshr <3 x i16> <i16 8192, i16 8192, i16 8192>, %x %lshr = lshr <3 x i16> <i16 8192, i16 8192, i16 8192>, %x
%shl = shl <3 x i16> %lshr, <i16 undef, i16 6, i16 6> %shl = shl <3 x i16> %lshr, <i16 undef, i16 6, i16 6>
%r = and <3 x i16> %shl, <i16 128, i16 128, i16 128> %r = and <3 x i16> %shl, <i16 128, i16 128, i16 128>
ret <3 x i16> %r ret <3 x i16> %r
} }
Show All 12 Lines