This is an archive of the discontinued LLVM Phabricator instance.

Differential D147296

[InstCombine] Add support for max(a,b) + min(a,b) => a + b.
ClosedPublic

Authored by skatkov on Mar 30 2023, 8:50 PM.

Details

Reviewers
spatel
nikic
lebedev.ri
RKSimon
dantrushin
mkazantsev
fhahn
efriedma
goldstein.w.n
Commits
rG624973806c56: [InstCombine] Add support for max(a,b) + min(a,b) => a + b. Re-land.
rGb86a06ef284f: [InstCombine] Add support for max(a,b) + min(a,b) => a + b.
Summary

The same optimization for

max(a,b) * min(a,b) => a * b

is added.

Correctness check:
uadd: https://alive2.llvm.org/ce/z/2rXDek
sadd: https://alive2.llvm.org/ce/z/zNu_er
uadd + nuw/nsw: https://alive2.llvm.org/ce/z/EaiNjB
sadd + nuw/nsw: https://alive2.llvm.org/ce/z/w_2Nrs

umul: https://alive2.llvm.org/ce/z/dgXRLr
smul: https://alive2.llvm.org/ce/z/hBjGzz
umul + nuw/nsw: https://alive2.llvm.org/ce/z/EaiNjB
smul + nuw/nsw: https://alive2.llvm.org/ce/z/87MNeS

Diff Detail

Event Timeline

skatkov created this revision.Mar 30 2023, 8:50 PM
Herald added a project: Restricted Project. · View Herald TranscriptMar 30 2023, 8:50 PM
Herald added subscribers: StephenFan, hiraditya. · View Herald Transcript
skatkov requested review of this revision.Mar 30 2023, 8:50 PM
Herald added a project: Restricted Project. · View Herald TranscriptMar 30 2023, 8:50 PM
skatkov updated this revision to Diff 509895.Mar 30 2023, 9:14 PM

remove redundant m_c to safe a compile time a bit.

Harbormaster completed remote builds in B222911: Diff 509895.Mar 30 2023, 10:02 PM
goldstein.w.n added a subscriber: goldstein.w.n.Mar 30 2023, 11:09 PM

Please add alive2 links for the proofs for {mul, add} x {smin/smax, umin/umax}.

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp
1596

Can you move this to before nuw/nsw flags are set (L1557).

1602

I think you can also preserve nuw and nsw flags.
https://alive2.llvm.org/ce/z/EaiNjB

likewise in the mul case:
https://alive2.llvm.org/ce/z/sV3tnG

llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
486

Can you move this before I is potentially modified and Changed is set (before L474).

llvm/test/Transforms/InstCombine/add-min-max.ll
2

Can you split the tests into a seperate patch so we can see the diff this patch results in?

llvm/test/Transforms/InstCombine/mul-min-max.ll
10

This (along with other tests) are misnamed. ('add' -> 'mul')

skatkov updated this revision to Diff 509939.Mar 31 2023, 1:23 AM
skatkov edited the summary of this revision. (Show Details)

Thank you very much for review.

skatkov marked 5 inline comments as done.Mar 31 2023, 1:24 AM
Harbormaster completed remote builds in B222938: Diff 509939.Mar 31 2023, 3:26 AM
skatkov added a comment.Apr 4 2023, 7:03 PM

ping

goldstein.w.n accepted this revision.Apr 4 2023, 7:33 PM

LGTM.

I'm not a maintainer so give it a day or so before pushing so others have a chance to look it over if they want.

This revision is now accepted and ready to land.Apr 4 2023, 7:33 PM
skatkov added a comment.Apr 4 2023, 7:39 PM
In D147296#4244914, @goldstein.w.n wrote:

LGTM.

I'm not a maintainer so give it a day or so before pushing so others have a chance to look it over if they want.

Sure, Thank a lot for review.

skatkov updated this revision to Diff 510988.Apr 4 2023, 8:36 PM

NFC update - use of BinaryOperator::CreateWithCopiedFlags utility instead of manually copying flags.

Harbormaster completed remote builds in B223718: Diff 510988.Apr 4 2023, 9:04 PM
This revision was landed with ongoing or failed builds.Apr 6 2023, 8:49 PM
Closed by commit rGb86a06ef284f: [InstCombine] Add support for max(a,b) + min(a,b) => a + b. (authored by skatkov). · Explain Why
This revision was automatically updated to reflect the committed changes.
skatkov added a commit: rGb86a06ef284f: [InstCombine] Add support for max(a,b) + min(a,b) => a + b..
skatkov added a reverting change: rG4665f3c8387e: Revert "[InstCombine] Add support for max(a,b) + min(a,b) => a + b.".Apr 6 2023, 9:16 PM
skatkov added a commit: rG624973806c56: [InstCombine] Add support for max(a,b) + min(a,b) => a + b. Re-land..Apr 6 2023, 10:06 PM

Revision Contents

PathSize
llvm/
lib/
Transforms/
InstCombine/
9 lines
9 lines
test/
Transforms/
InstCombine/
59 lines
59 lines

Diff 509892

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

Show First 20 Lines • Show All 1,587 Lines • ▼ Show 20 LinesInstruction *InstCombinerImpl::visitAdd(BinaryOperator &I) {
// ctpop(A) + ctpop(B) => ctpop(A | B) if A and B have no bits set in common. // ctpop(A) + ctpop(B) => ctpop(A | B) if A and B have no bits set in common.
if (match(LHS, m_OneUse(m_Intrinsic<Intrinsic::ctpop>(m_Value(A)))) && if (match(LHS, m_OneUse(m_Intrinsic<Intrinsic::ctpop>(m_Value(A)))) &&
match(RHS, m_OneUse(m_Intrinsic<Intrinsic::ctpop>(m_Value(B)))) && match(RHS, m_OneUse(m_Intrinsic<Intrinsic::ctpop>(m_Value(B)))) &&
haveNoCommonBitsSet(A, B, DL, &AC, &I, &DT)) haveNoCommonBitsSet(A, B, DL, &AC, &I, &DT))
return replaceInstUsesWith( return replaceInstUsesWith(
I, Builder.CreateIntrinsic(Intrinsic::ctpop, {I.getType()}, I, Builder.CreateIntrinsic(Intrinsic::ctpop, {I.getType()},
{Builder.CreateOr(A, B)})); {Builder.CreateOr(A, B)}));
// min(A, B) + max(A, B) => A + B.
goldstein.w.nUnsubmitted
Done
ReplyInline Actions

Can you move this to before nuw/nsw flags are set (L1557).

goldstein.w.n: Can you move this to before nuw/nsw flags are set (L1557).
if (match(&I, match_combine_or(
m_c_Add(m_c_SMax(m_Value(A), m_Value(B)),
m_c_SMin(m_Deferred(A), m_Deferred(B))),
m_c_Add(m_c_UMax(m_Value(A), m_Value(B)),
m_c_UMin(m_Deferred(A), m_Deferred(B)))))) {
return BinaryOperator::CreateAdd(A, B);
goldstein.w.nUnsubmitted
Done
ReplyInline Actions

I think you can also preserve nuw and nsw flags.
https://alive2.llvm.org/ce/z/EaiNjB

likewise in the mul case:
https://alive2.llvm.org/ce/z/sV3tnG

goldstein.w.n: I think you can also preserve `nuw` and `nsw` flags. https://alive2.llvm.org/ce/z/EaiNjB…
}
return Changed ? &I : nullptr; return Changed ? &I : nullptr;
} }
/// Eliminate an op from a linear interpolation (lerp) pattern. /// Eliminate an op from a linear interpolation (lerp) pattern.
static Instruction *factorizeLerp(BinaryOperator &I, static Instruction *factorizeLerp(BinaryOperator &I,
InstCombiner::BuilderTy &Builder) { InstCombiner::BuilderTy &Builder) {
Value *X, *Y, *Z; Value *X, *Y, *Z;
if (!match(&I, m_c_FAdd(m_OneUse(m_c_FMul(m_Value(Y), if (!match(&I, m_c_FAdd(m_OneUse(m_c_FMul(m_Value(Y),
▲ Show 20 Lines • Show All 1,123 Lines • Show Last 20 Lines

llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp

Show First 20 Lines • Show All 476 Lines • ▼ Show 20 Lines if (!HasNSW && willNotOverflowSignedMul(Op0, Op1, I)) {
I.setHasNoSignedWrap(true); I.setHasNoSignedWrap(true);
} }
if (!HasNUW && willNotOverflowUnsignedMul(Op0, Op1, I)) { if (!HasNUW && willNotOverflowUnsignedMul(Op0, Op1, I)) {
Changed = true; Changed = true;
I.setHasNoUnsignedWrap(true); I.setHasNoUnsignedWrap(true);
} }
// min(X, Y) * max(X, Y) => X * Y.
if (match(&I, match_combine_or(
goldstein.w.nUnsubmitted
Done
ReplyInline Actions

Can you move this before I is potentially modified and Changed is set (before L474).

goldstein.w.n: Can you move this before `I` is potentially modified and `Changed` is set (before L474).
m_c_Mul(m_c_SMax(m_Value(X), m_Value(Y)),
m_c_SMin(m_Deferred(X), m_Deferred(Y))),
m_c_Mul(m_c_UMax(m_Value(X), m_Value(Y)),
m_c_UMin(m_Deferred(X), m_Deferred(Y)))))) {
return BinaryOperator::CreateMul(X, Y);
}
return Changed ? &I : nullptr; return Changed ? &I : nullptr;
} }
Instruction *InstCombinerImpl::foldFPSignBitOps(BinaryOperator &I) { Instruction *InstCombinerImpl::foldFPSignBitOps(BinaryOperator &I) {
BinaryOperator::BinaryOps Opcode = I.getOpcode(); BinaryOperator::BinaryOps Opcode = I.getOpcode();
assert((Opcode == Instruction::FMul || Opcode == Instruction::FDiv) && assert((Opcode == Instruction::FMul || Opcode == Instruction::FDiv) &&
"Expected fmul or fdiv"); "Expected fmul or fdiv");
▲ Show 20 Lines • Show All 1,473 Lines • Show Last 20 Lines

llvm/test/Transforms/InstCombine/add-min-max.ll

  • This file was added.
; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
; RUN: opt < %s -passes=instcombine -S | FileCheck %s
goldstein.w.nUnsubmitted
Done
ReplyInline Actions

Can you split the tests into a seperate patch so we can see the diff this patch results in?

goldstein.w.n: Can you split the tests into a seperate patch so we can see the diff this patch results in?
declare i32 @llvm.smax.i32(i32 %a, i32 %b)
declare i32 @llvm.smin.i32(i32 %a, i32 %b)
declare i32 @llvm.umax.i32(i32 %a, i32 %b)
declare i32 @llvm.umin.i32(i32 %a, i32 %b)
define i32 @uadd_min_max(i32 %a, i32 %b) {
; CHECK-LABEL: @uadd_min_max(
; CHECK-NEXT: entry:
; CHECK-NEXT: [[RES:%.*]] = add i32 [[A:%.*]], [[B:%.*]]
; CHECK-NEXT: ret i32 [[RES]]
;
entry:
%max = call i32 @llvm.umax.i32(i32 %a, i32 %b)
%min = call i32 @llvm.umin.i32(i32 %a, i32 %b)
%res = add i32 %min, %max
ret i32 %res
}
define i32 @uadd_min_max_comm(i32 %a, i32 %b) {
; CHECK-LABEL: @uadd_min_max_comm(
; CHECK-NEXT: entry:
; CHECK-NEXT: [[RES:%.*]] = add i32 [[B:%.*]], [[A:%.*]]
; CHECK-NEXT: ret i32 [[RES]]
;
entry:
%max = call i32 @llvm.umax.i32(i32 %b, i32 %a)
%min = call i32 @llvm.umin.i32(i32 %a, i32 %b)
%res = add i32 %min, %max
ret i32 %res
}
define i32 @sadd_min_max(i32 %a, i32 %b) {
; CHECK-LABEL: @sadd_min_max(
; CHECK-NEXT: entry:
; CHECK-NEXT: [[RES:%.*]] = add i32 [[A:%.*]], [[B:%.*]]
; CHECK-NEXT: ret i32 [[RES]]
;
entry:
%max = call i32 @llvm.smax.i32(i32 %a, i32 %b)
%min = call i32 @llvm.smin.i32(i32 %a, i32 %b)
%res = add i32 %min, %max
ret i32 %res
}
define i32 @sadd_min_max_comm(i32 %a, i32 %b) {
; CHECK-LABEL: @sadd_min_max_comm(
; CHECK-NEXT: entry:
; CHECK-NEXT: [[RES:%.*]] = add i32 [[B:%.*]], [[A:%.*]]
; CHECK-NEXT: ret i32 [[RES]]
;
entry:
%max = call i32 @llvm.smax.i32(i32 %b, i32 %a)
%min = call i32 @llvm.smin.i32(i32 %a, i32 %b)
%res = add i32 %min, %max
ret i32 %res
}

llvm/test/Transforms/InstCombine/mul-min-max.ll

  • This file was added.
; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
; RUN: opt < %s -passes=instcombine -S | FileCheck %s
declare i32 @llvm.smax.i32(i32 %a, i32 %b)
declare i32 @llvm.smin.i32(i32 %a, i32 %b)
declare i32 @llvm.umax.i32(i32 %a, i32 %b)
declare i32 @llvm.umin.i32(i32 %a, i32 %b)
define i32 @uadd_min_max(i32 %a, i32 %b) {
; CHECK-LABEL: @uadd_min_max(
goldstein.w.nUnsubmitted
Done
ReplyInline Actions

This (along with other tests) are misnamed. ('add' -> 'mul')

goldstein.w.n: This (along with other tests) are misnamed. ('add' -> 'mul')
; CHECK-NEXT: entry:
; CHECK-NEXT: [[RES:%.*]] = mul i32 [[A:%.*]], [[B:%.*]]
; CHECK-NEXT: ret i32 [[RES]]
;
entry:
%max = call i32 @llvm.umax.i32(i32 %a, i32 %b)
%min = call i32 @llvm.umin.i32(i32 %a, i32 %b)
%res = mul i32 %min, %max
ret i32 %res
}
define i32 @uadd_min_max_comm(i32 %a, i32 %b) {
; CHECK-LABEL: @uadd_min_max_comm(
; CHECK-NEXT: entry:
; CHECK-NEXT: [[RES:%.*]] = mul i32 [[B:%.*]], [[A:%.*]]
; CHECK-NEXT: ret i32 [[RES]]
;
entry:
%max = call i32 @llvm.umax.i32(i32 %b, i32 %a)
%min = call i32 @llvm.umin.i32(i32 %a, i32 %b)
%res = mul i32 %min, %max
ret i32 %res
}
define i32 @sadd_min_max(i32 %a, i32 %b) {
; CHECK-LABEL: @sadd_min_max(
; CHECK-NEXT: entry:
; CHECK-NEXT: [[RES:%.*]] = mul i32 [[A:%.*]], [[B:%.*]]
; CHECK-NEXT: ret i32 [[RES]]
;
entry:
%max = call i32 @llvm.smax.i32(i32 %a, i32 %b)
%min = call i32 @llvm.smin.i32(i32 %a, i32 %b)
%res = mul i32 %min, %max
ret i32 %res
}
define i32 @sadd_min_max_comm(i32 %a, i32 %b) {
; CHECK-LABEL: @sadd_min_max_comm(
; CHECK-NEXT: entry:
; CHECK-NEXT: [[RES:%.*]] = mul i32 [[B:%.*]], [[A:%.*]]
; CHECK-NEXT: ret i32 [[RES]]
;
entry:
%max = call i32 @llvm.smax.i32(i32 %b, i32 %a)
%min = call i32 @llvm.smin.i32(i32 %a, i32 %b)
%res = mul i32 %min, %max
ret i32 %res
}