From 867f0c3c4d8c25c5cded2dd290a3fcfd92d98557 Mon Sep 17 00:00:00 2001 From: Sanjay Patel Date: Sun, 5 Apr 2020 08:51:29 -0400 Subject: [PATCH] [ValueTracking] enhance matching of smin/smax with 'not' operands The cmyk tests are based on the known regression that resulted from: rGf2fbdf76d8d0 So this improvement in analysis might be enough to restore that commit. --- llvm/lib/Analysis/ValueTracking.cpp | 39 ++++++++---- llvm/test/Transforms/InstCombine/max-of-nots.ll | 80 ++++++++++--------------- llvm/unittests/Analysis/ValueTrackingTest.cpp | 8 +-- 3 files changed, 62 insertions(+), 65 deletions(-) diff --git a/llvm/lib/Analysis/ValueTracking.cpp b/llvm/lib/Analysis/ValueTracking.cpp index d7ea47e..01025ab 100644 --- a/llvm/lib/Analysis/ValueTracking.cpp +++ b/llvm/lib/Analysis/ValueTracking.cpp @@ -5124,6 +5124,21 @@ static SelectPatternResult matchMinMaxOfMinMax(CmpInst::Predicate Pred, return {SPF_UNKNOWN, SPNB_NA, false}; } +/// If the input value is the result of a 'not' op, constant integer, or vector +/// splat of a constant integer, return the bitwise-not source value. +/// TODO: This could be extended to handle non-splat vector integer constants. +static Value *getNotValue(Value *V) { + Value *NotV; + if (match(V, m_Not(m_Value(NotV)))) + return NotV; + + const APInt *C; + if (match(V, m_APInt(C))) + return ConstantInt::get(V->getType(), ~(*C)); + + return nullptr; +} + /// Match non-obvious integer minimum and maximum sequences. static SelectPatternResult matchMinMax(CmpInst::Predicate Pred, Value *CmpLHS, Value *CmpRHS, @@ -5159,6 +5174,17 @@ static SelectPatternResult matchMinMax(CmpInst::Predicate Pred, match(TrueVal, m_NSWSub(m_Specific(CmpLHS), m_Specific(CmpRHS)))) return {Pred == CmpInst::ICMP_SGT ? SPF_SMAX : SPF_SMIN, SPNB_NA, false}; + // Look through 'not' ops to find disguised signed min/max. + // (X >s Y) ? ~X : ~Y ==> (~X SMIN(~X, ~Y) + // (X (~X >s ~Y) ? ~X : ~Y ==> SMAX(~X, ~Y) + if (CmpLHS == getNotValue(TrueVal) && CmpRHS == getNotValue(FalseVal)) + return {Pred == CmpInst::ICMP_SGT ? SPF_SMIN : SPF_SMAX, SPNB_NA, false}; + + // (X >s Y) ? ~Y : ~X ==> (~X SMAX(~Y, ~X) + // (X (~X >s ~Y) ? ~Y : ~X ==> SMIN(~Y, ~X) + if (CmpLHS == getNotValue(FalseVal) && CmpRHS == getNotValue(TrueVal)) + return {Pred == CmpInst::ICMP_SGT ? SPF_SMAX : SPF_SMIN, SPNB_NA, false}; + const APInt *C1; if (!match(CmpRHS, m_APInt(C1))) return {SPF_UNKNOWN, SPNB_NA, false}; @@ -5182,19 +5208,6 @@ static SelectPatternResult matchMinMax(CmpInst::Predicate Pred, return {CmpLHS == FalseVal ? SPF_UMAX : SPF_UMIN, SPNB_NA, false}; } - // Look through 'not' ops to find disguised signed min/max. - // (X >s C) ? ~X : ~C ==> (~X SMIN(~X, ~C) - // (X (~X >s ~C) ? ~X : ~C ==> SMAX(~X, ~C) - if (match(TrueVal, m_Not(m_Specific(CmpLHS))) && - match(FalseVal, m_APInt(C2)) && ~(*C1) == *C2) - return {Pred == CmpInst::ICMP_SGT ? SPF_SMIN : SPF_SMAX, SPNB_NA, false}; - - // (X >s C) ? ~C : ~X ==> (~X SMAX(~C, ~X) - // (X (~X >s ~C) ? ~C : ~X ==> SMIN(~C, ~X) - if (match(FalseVal, m_Not(m_Specific(CmpLHS))) && - match(TrueVal, m_APInt(C2)) && ~(*C1) == *C2) - return {Pred == CmpInst::ICMP_SGT ? SPF_SMAX : SPF_SMIN, SPNB_NA, false}; - return {SPF_UNKNOWN, SPNB_NA, false}; } diff --git a/llvm/test/Transforms/InstCombine/max-of-nots.ll b/llvm/test/Transforms/InstCombine/max-of-nots.ll index 9387908..3f4bd02 100644 --- a/llvm/test/Transforms/InstCombine/max-of-nots.ll +++ b/llvm/test/Transforms/InstCombine/max-of-nots.ll @@ -391,18 +391,14 @@ define void @cmyk(i8 %r, i8 %g, i8 %b) { define void @cmyk2(i8 %r, i8 %g, i8 %b) { ; CHECK-LABEL: @cmyk2( -; CHECK-NEXT: [[NOTR:%.*]] = xor i8 [[R:%.*]], -1 -; CHECK-NEXT: [[NOTG:%.*]] = xor i8 [[G:%.*]], -1 -; CHECK-NEXT: [[NOTB:%.*]] = xor i8 [[B:%.*]], -1 -; CHECK-NEXT: [[CMP_GR:%.*]] = icmp slt i8 [[G]], [[R]] -; CHECK-NEXT: [[CMP_BR:%.*]] = icmp slt i8 [[B]], [[R]] -; CHECK-NEXT: [[MIN_BR:%.*]] = select i1 [[CMP_BR]], i8 [[NOTR]], i8 [[NOTB]] -; CHECK-NEXT: [[CMP_BG:%.*]] = icmp slt i8 [[B]], [[G]] -; CHECK-NEXT: [[MIN_BG:%.*]] = select i1 [[CMP_BG]], i8 [[NOTG]], i8 [[NOTB]] -; CHECK-NEXT: [[K:%.*]] = select i1 [[CMP_GR]], i8 [[MIN_BR]], i8 [[MIN_BG]] -; CHECK-NEXT: [[CK:%.*]] = sub i8 [[NOTR]], [[K]] -; CHECK-NEXT: [[MK:%.*]] = sub i8 [[NOTG]], [[K]] -; CHECK-NEXT: [[YK:%.*]] = sub i8 [[NOTB]], [[K]] +; CHECK-NEXT: [[TMP1:%.*]] = icmp sgt i8 [[R:%.*]], [[B:%.*]] +; CHECK-NEXT: [[TMP2:%.*]] = select i1 [[TMP1]], i8 [[R]], i8 [[B]] +; CHECK-NEXT: [[TMP3:%.*]] = icmp sgt i8 [[TMP2]], [[G:%.*]] +; CHECK-NEXT: [[K_V:%.*]] = select i1 [[TMP3]], i8 [[TMP2]], i8 [[G]] +; CHECK-NEXT: [[K:%.*]] = xor i8 [[K_V]], -1 +; CHECK-NEXT: [[CK:%.*]] = sub i8 [[K_V]], [[R]] +; CHECK-NEXT: [[MK:%.*]] = sub i8 [[K_V]], [[G]] +; CHECK-NEXT: [[YK:%.*]] = sub i8 [[K_V]], [[B]] ; CHECK-NEXT: call void @use(i8 [[CK]], i8 [[MK]], i8 [[YK]], i8 [[K]]) ; CHECK-NEXT: ret void ; @@ -424,18 +420,14 @@ define void @cmyk2(i8 %r, i8 %g, i8 %b) { define void @cmyk3(i8 %r, i8 %g, i8 %b) { ; CHECK-LABEL: @cmyk3( -; CHECK-NEXT: [[NOTR:%.*]] = xor i8 [[R:%.*]], -1 -; CHECK-NEXT: [[NOTG:%.*]] = xor i8 [[G:%.*]], -1 -; CHECK-NEXT: [[NOTB:%.*]] = xor i8 [[B:%.*]], -1 -; CHECK-NEXT: [[CMP_GR:%.*]] = icmp slt i8 [[G]], [[R]] -; CHECK-NEXT: [[CMP_BR:%.*]] = icmp sgt i8 [[R]], [[B]] -; CHECK-NEXT: [[MIN_BR:%.*]] = select i1 [[CMP_BR]], i8 [[NOTR]], i8 [[NOTB]] -; CHECK-NEXT: [[CMP_BG:%.*]] = icmp slt i8 [[B]], [[G]] -; CHECK-NEXT: [[MIN_BG:%.*]] = select i1 [[CMP_BG]], i8 [[NOTG]], i8 [[NOTB]] -; CHECK-NEXT: [[K:%.*]] = select i1 [[CMP_GR]], i8 [[MIN_BR]], i8 [[MIN_BG]] -; CHECK-NEXT: [[CK:%.*]] = sub i8 [[NOTR]], [[K]] -; CHECK-NEXT: [[MK:%.*]] = sub i8 [[NOTG]], [[K]] -; CHECK-NEXT: [[YK:%.*]] = sub i8 [[NOTB]], [[K]] +; CHECK-NEXT: [[TMP1:%.*]] = icmp sgt i8 [[R:%.*]], [[B:%.*]] +; CHECK-NEXT: [[TMP2:%.*]] = select i1 [[TMP1]], i8 [[R]], i8 [[B]] +; CHECK-NEXT: [[TMP3:%.*]] = icmp sgt i8 [[TMP2]], [[G:%.*]] +; CHECK-NEXT: [[K_V:%.*]] = select i1 [[TMP3]], i8 [[TMP2]], i8 [[G]] +; CHECK-NEXT: [[K:%.*]] = xor i8 [[K_V]], -1 +; CHECK-NEXT: [[CK:%.*]] = sub i8 [[K_V]], [[R]] +; CHECK-NEXT: [[MK:%.*]] = sub i8 [[K_V]], [[G]] +; CHECK-NEXT: [[YK:%.*]] = sub i8 [[K_V]], [[B]] ; CHECK-NEXT: call void @use(i8 [[CK]], i8 [[MK]], i8 [[YK]], i8 [[K]]) ; CHECK-NEXT: ret void ; @@ -457,18 +449,14 @@ define void @cmyk3(i8 %r, i8 %g, i8 %b) { define void @cmyk4(i8 %r, i8 %g, i8 %b) { ; CHECK-LABEL: @cmyk4( -; CHECK-NEXT: [[NOTR:%.*]] = xor i8 [[R:%.*]], -1 -; CHECK-NEXT: [[NOTG:%.*]] = xor i8 [[G:%.*]], -1 -; CHECK-NEXT: [[NOTB:%.*]] = xor i8 [[B:%.*]], -1 -; CHECK-NEXT: [[CMP_GR:%.*]] = icmp slt i8 [[G]], [[R]] -; CHECK-NEXT: [[CMP_BR:%.*]] = icmp sgt i8 [[R]], [[B]] -; CHECK-NEXT: [[MIN_BR:%.*]] = select i1 [[CMP_BR]], i8 [[NOTR]], i8 [[NOTB]] -; CHECK-NEXT: [[CMP_BG:%.*]] = icmp sgt i8 [[G]], [[B]] -; CHECK-NEXT: [[MIN_BG:%.*]] = select i1 [[CMP_BG]], i8 [[NOTG]], i8 [[NOTB]] -; CHECK-NEXT: [[K:%.*]] = select i1 [[CMP_GR]], i8 [[MIN_BR]], i8 [[MIN_BG]] -; CHECK-NEXT: [[CK:%.*]] = sub i8 [[NOTR]], [[K]] -; CHECK-NEXT: [[MK:%.*]] = sub i8 [[NOTG]], [[K]] -; CHECK-NEXT: [[YK:%.*]] = sub i8 [[NOTB]], [[K]] +; CHECK-NEXT: [[TMP1:%.*]] = icmp sgt i8 [[R:%.*]], [[B:%.*]] +; CHECK-NEXT: [[TMP2:%.*]] = select i1 [[TMP1]], i8 [[R]], i8 [[B]] +; CHECK-NEXT: [[TMP3:%.*]] = icmp sgt i8 [[TMP2]], [[G:%.*]] +; CHECK-NEXT: [[K_V:%.*]] = select i1 [[TMP3]], i8 [[TMP2]], i8 [[G]] +; CHECK-NEXT: [[K:%.*]] = xor i8 [[K_V]], -1 +; CHECK-NEXT: [[CK:%.*]] = sub i8 [[K_V]], [[R]] +; CHECK-NEXT: [[MK:%.*]] = sub i8 [[K_V]], [[G]] +; CHECK-NEXT: [[YK:%.*]] = sub i8 [[K_V]], [[B]] ; CHECK-NEXT: call void @use(i8 [[CK]], i8 [[MK]], i8 [[YK]], i8 [[K]]) ; CHECK-NEXT: ret void ; @@ -490,18 +478,14 @@ define void @cmyk4(i8 %r, i8 %g, i8 %b) { define void @cmyk5(i8 %r, i8 %g, i8 %b) { ; CHECK-LABEL: @cmyk5( -; CHECK-NEXT: [[NOTR:%.*]] = xor i8 [[R:%.*]], -1 -; CHECK-NEXT: [[NOTG:%.*]] = xor i8 [[G:%.*]], -1 -; CHECK-NEXT: [[NOTB:%.*]] = xor i8 [[B:%.*]], -1 -; CHECK-NEXT: [[CMP_GR:%.*]] = icmp sgt i8 [[R]], [[G]] -; CHECK-NEXT: [[CMP_BR:%.*]] = icmp sgt i8 [[R]], [[B]] -; CHECK-NEXT: [[MIN_BR:%.*]] = select i1 [[CMP_BR]], i8 [[NOTR]], i8 [[NOTB]] -; CHECK-NEXT: [[CMP_BG:%.*]] = icmp sgt i8 [[G]], [[B]] -; CHECK-NEXT: [[MIN_BG:%.*]] = select i1 [[CMP_BG]], i8 [[NOTG]], i8 [[NOTB]] -; CHECK-NEXT: [[K:%.*]] = select i1 [[CMP_GR]], i8 [[MIN_BR]], i8 [[MIN_BG]] -; CHECK-NEXT: [[CK:%.*]] = sub i8 [[NOTR]], [[K]] -; CHECK-NEXT: [[MK:%.*]] = sub i8 [[NOTG]], [[K]] -; CHECK-NEXT: [[YK:%.*]] = sub i8 [[NOTB]], [[K]] +; CHECK-NEXT: [[TMP1:%.*]] = icmp sgt i8 [[R:%.*]], [[B:%.*]] +; CHECK-NEXT: [[TMP2:%.*]] = select i1 [[TMP1]], i8 [[R]], i8 [[B]] +; CHECK-NEXT: [[TMP3:%.*]] = icmp sgt i8 [[TMP2]], [[G:%.*]] +; CHECK-NEXT: [[K_V:%.*]] = select i1 [[TMP3]], i8 [[TMP2]], i8 [[G]] +; CHECK-NEXT: [[K:%.*]] = xor i8 [[K_V]], -1 +; CHECK-NEXT: [[CK:%.*]] = sub i8 [[K_V]], [[R]] +; CHECK-NEXT: [[MK:%.*]] = sub i8 [[K_V]], [[G]] +; CHECK-NEXT: [[YK:%.*]] = sub i8 [[K_V]], [[B]] ; CHECK-NEXT: call void @use(i8 [[CK]], i8 [[MK]], i8 [[YK]], i8 [[K]]) ; CHECK-NEXT: ret void ; diff --git a/llvm/unittests/Analysis/ValueTrackingTest.cpp b/llvm/unittests/Analysis/ValueTrackingTest.cpp index 7c7a21b..14a0da1 100644 --- a/llvm/unittests/Analysis/ValueTrackingTest.cpp +++ b/llvm/unittests/Analysis/ValueTrackingTest.cpp @@ -471,7 +471,7 @@ TEST_F(MatchSelectPatternTest, NotNotSMin) { " %A = select i1 %cmp, i8 %an, i8 %bn\n" " ret i8 %A\n" "}\n"); - expectPattern({SPF_UNKNOWN, SPNB_NA, false}); + expectPattern({SPF_SMIN, SPNB_NA, false}); } TEST_F(MatchSelectPatternTest, NotNotSMinSwap) { @@ -483,7 +483,7 @@ TEST_F(MatchSelectPatternTest, NotNotSMinSwap) { " %A = select i1 %cmp, i8 %bn, i8 %an\n" " ret i8 %A\n" "}\n"); - expectPattern({SPF_UNKNOWN, SPNB_NA, false}); + expectPattern({SPF_SMIN, SPNB_NA, false}); } TEST_F(MatchSelectPatternTest, NotNotSMax) { @@ -495,7 +495,7 @@ TEST_F(MatchSelectPatternTest, NotNotSMax) { " %A = select i1 %cmp, i8 %an, i8 %bn\n" " ret i8 %A\n" "}\n"); - expectPattern({SPF_UNKNOWN, SPNB_NA, false}); + expectPattern({SPF_SMAX, SPNB_NA, false}); } TEST_F(MatchSelectPatternTest, NotNotSMaxSwap) { @@ -507,7 +507,7 @@ TEST_F(MatchSelectPatternTest, NotNotSMaxSwap) { " %A = select i1 %cmp, i8 %bn, i8 %an\n" " ret i8 %A\n" "}\n"); - expectPattern({SPF_UNKNOWN, SPNB_NA, false}); + expectPattern({SPF_SMAX, SPNB_NA, false}); } TEST(ValueTracking, GuaranteedToTransferExecutionToSuccessor) { -- 2.7.4