This is an archive of the discontinued LLVM Phabricator instance.

Differential D139997

[InstCombine] complete (X << Z) / (Y << Z) --> X / Y
ClosedPublic

Authored by Chenbing.Zheng on Dec 14 2022, 12:14 AM.

Details

Reviewers
spatel
RKSimon
benshi001
Commits
rGbff1f8c79bee: [InstCombine] complete (X << Z) / (Y << Z) --> X / Y
Summary

Add one more situation for this fold
For unsigned div, 'nsw' on both shifts + 'nuw' on the dividend.

Alive2: https://alive2.llvm.org/ce/z/sELF76

Diff Detail

Unit TestsFailed

TimeTest
60,040 msx64 debian > libFuzzer.libFuzzer::minimize_crash.test

Event Timeline

Chenbing.Zheng created this revision.Dec 14 2022, 12:14 AM
Herald added a project: Restricted Project. · View Herald TranscriptDec 14 2022, 12:14 AM
Herald added a subscriber: hiraditya. · View Herald Transcript
Chenbing.Zheng requested review of this revision.Dec 14 2022, 12:14 AM
Herald added subscribers: llvm-commits, jacquesguan. · View Herald TranscriptDec 14 2022, 12:14 AM
Harbormaster completed remote builds in B203030: Diff 482728.Dec 14 2022, 1:11 AM
spatel accepted this revision.Dec 16 2022, 5:01 AM

LGTM - thanks!

This revision is now accepted and ready to land.Dec 16 2022, 5:01 AM
This revision was landed with ongoing or failed builds.Dec 22 2022, 7:57 PM
Closed by commit rGbff1f8c79bee: [InstCombine] complete (X << Z) / (Y << Z) --> X / Y (authored by Chenbing.Zheng, committed by benshi001). · Explain Why
This revision was automatically updated to reflect the committed changes.
benshi001 added a commit: rGbff1f8c79bee: [InstCombine] complete (X << Z) / (Y << Z) --> X / Y.

Revision Contents

PathSize
llvm/
lib/
Transforms/
InstCombine/
8 lines
test/
Transforms/
InstCombine/
6 lines

Diff 482728

llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp

Show First 20 Lines • Show All 882 Lines • ▼ Show 20 Linesstatic Instruction *foldIDivShl(BinaryOperator &I,
// With appropriate no-wrap constraints, remove a common factor in the // With appropriate no-wrap constraints, remove a common factor in the
// dividend and divisor that is disguised as a left-shift amount. // dividend and divisor that is disguised as a left-shift amount.
if (match(Op0, m_Shl(m_Value(X), m_Value(Z))) && if (match(Op0, m_Shl(m_Value(X), m_Value(Z))) &&
match(Op1, m_Shl(m_Value(Y), m_Specific(Z)))) { match(Op1, m_Shl(m_Value(Y), m_Specific(Z)))) {
auto *Shl0 = cast<OverflowingBinaryOperator>(Op0); auto *Shl0 = cast<OverflowingBinaryOperator>(Op0);
auto *Shl1 = cast<OverflowingBinaryOperator>(Op1); auto *Shl1 = cast<OverflowingBinaryOperator>(Op1);
// For unsigned div, we need 'nuw' on both shifts. // For unsigned div, we need 'nuw' on both shifts or
// 'nsw' on both shifts + 'nuw' on the dividend.
// (X << Z) / (Y << Z) --> X / Y // (X << Z) / (Y << Z) --> X / Y
if (!IsSigned && Shl0->hasNoUnsignedWrap() && Shl1->hasNoUnsignedWrap()) if (!IsSigned &&
((Shl0->hasNoUnsignedWrap() && Shl1->hasNoUnsignedWrap()) ||
(Shl0->hasNoUnsignedWrap() && Shl0->hasNoSignedWrap() &&
Shl1->hasNoSignedWrap())))
Ret = BinaryOperator::CreateUDiv(X, Y); Ret = BinaryOperator::CreateUDiv(X, Y);
// For signed div, we need 'nsw' on both shifts + 'nuw' on the divisor. // For signed div, we need 'nsw' on both shifts + 'nuw' on the divisor.
// (X << Z) / (Y << Z) --> X / Y // (X << Z) / (Y << Z) --> X / Y
if (IsSigned && Shl0->hasNoSignedWrap() && Shl1->hasNoSignedWrap() && if (IsSigned && Shl0->hasNoSignedWrap() && Shl1->hasNoSignedWrap() &&
Shl1->hasNoUnsignedWrap()) Shl1->hasNoUnsignedWrap())
Ret = BinaryOperator::CreateSDiv(X, Y); Ret = BinaryOperator::CreateSDiv(X, Y);
} }
▲ Show 20 Lines • Show All 930 Lines • Show Last 20 Lines

llvm/test/Transforms/InstCombine/div-shift.ll

Show First 20 Lines • Show All 945 Lines • ▼ Show 20 Lines
; CHECK-NEXT: ret i8 [[D]] ; CHECK-NEXT: ret i8 [[D]]
; ;
%xz = shl nsw i8 %x, %z %xz = shl nsw i8 %x, %z
%yz = shl nuw i8 %y, %z %yz = shl nuw i8 %y, %z
%d = udiv i8 %xz, %yz %d = udiv i8 %xz, %yz
ret i8 %d ret i8 %d
} }
; TODO: This could fold.
define i8 @udiv_shl_shl_nuw_nsw2(i8 %x, i8 %y, i8 %z) { define i8 @udiv_shl_shl_nuw_nsw2(i8 %x, i8 %y, i8 %z) {
; CHECK-LABEL: @udiv_shl_shl_nuw_nsw2( ; CHECK-LABEL: @udiv_shl_shl_nuw_nsw2(
; CHECK-NEXT: [[XZ:%.*]] = shl nuw nsw i8 [[X:%.*]], [[Z:%.*]] ; CHECK-NEXT: [[D:%.*]] = udiv i8 [[X:%.*]], [[Y:%.*]]
; CHECK-NEXT: [[YZ:%.*]] = shl nsw i8 [[Y:%.*]], [[Z]]
; CHECK-NEXT: [[D:%.*]] = udiv i8 [[XZ]], [[YZ]]
; CHECK-NEXT: ret i8 [[D]] ; CHECK-NEXT: ret i8 [[D]]
; ;
%xz = shl nuw nsw i8 %x, %z %xz = shl nuw nsw i8 %x, %z
%yz = shl nsw i8 %y, %z %yz = shl nsw i8 %y, %z
%d = udiv i8 %xz, %yz %d = udiv i8 %xz, %yz
ret i8 %d ret i8 %d
} }
Show All 13 Lines