From 7015a5c54b53d8d2297a3aa38bc32aab167bdcfc Mon Sep 17 00:00:00 2001 From: Roman Lebedev Date: Sun, 20 Oct 2019 20:52:06 +0000 Subject: [PATCH] [InstCombine] conditional sign-extend of high-bit-extract: 'or' pattern. In this pattern, all the "magic" bits that we'd `add` are all high sign bits, and in the value we'd be adding to they are all unset, not unexpectedly, so we can have an `or` there: https://rise4fun.com/Alive/ups It is possible that `haveNoCommonBitsSet()` should be taught about this pattern so that we never have an `add` variant, but the reasoning would need to be recursive (because of that `select`), so i'm not really sure that would be worth it just yet. llvm-svn: 375378 --- .../Transforms/InstCombine/InstCombineAddSub.cpp | 35 +++++++++++----------- .../Transforms/InstCombine/InstCombineAndOrXor.cpp | 4 +++ .../Transforms/InstCombine/InstCombineInternal.h | 2 ++ ...riable-length-signext-after-high-bit-extract.ll | 6 ++-- 4 files changed, 26 insertions(+), 21 deletions(-) diff --git a/llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp b/llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp index 5d306cd..77907cc 100644 --- a/llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp +++ b/llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp @@ -1097,10 +1097,11 @@ static Instruction *foldToUnsignedSaturatedAdd(BinaryOperator &I) { return nullptr; } -static Instruction * -canonicalizeCondSignextOfHighBitExtractToSignextHighBitExtract( - BinaryOperator &I, InstCombiner::BuilderTy &Builder) { +Instruction * +InstCombiner::canonicalizeCondSignextOfHighBitExtractToSignextHighBitExtract( + BinaryOperator &I) { assert((I.getOpcode() == Instruction::Add || + I.getOpcode() == Instruction::Or || I.getOpcode() == Instruction::Sub) && "Expecting add/sub instruction"); @@ -1114,7 +1115,7 @@ canonicalizeCondSignextOfHighBitExtractToSignextHighBitExtract( m_Value(Select)))) return nullptr; - // `add` is commutative; but for `sub`, "select" *must* be on RHS. + // `add`/`or` is commutative; but for `sub`, "select" *must* be on RHS. if (I.getOpcode() == Instruction::Sub && I.getOperand(1) != Select) return nullptr; @@ -1140,13 +1141,13 @@ canonicalizeCondSignextOfHighBitExtractToSignextHighBitExtract( X->getType()->getScalarSizeInBits())))) return nullptr; - // Sign-extending value can be sign-extended itself if we `add` it, - // or zero-extended if we `sub`tract it. + // Sign-extending value can be zero-extended if we `sub`tract it, + // or sign-extended otherwise. auto SkipExtInMagic = [&I](Value *&V) { - if (I.getOpcode() == Instruction::Add) - match(V, m_SExtOrSelf(m_Value(V))); - else + if (I.getOpcode() == Instruction::Sub) match(V, m_ZExtOrSelf(m_Value(V))); + else + match(V, m_SExtOrSelf(m_Value(V))); }; // Now, finally validate the sign-extending magic. @@ -1169,7 +1170,7 @@ canonicalizeCondSignextOfHighBitExtractToSignextHighBitExtract( if (!ShouldSignext) std::swap(SignExtendingValue, Zero); - // If we should not perform sign-extension then we must add/subtract zero. + // If we should not perform sign-extension then we must add/or/subtract zero. if (!match(Zero, m_Zero())) return nullptr; // Otherwise, it should be some constant, left-shifted by the same NBits we @@ -1181,10 +1182,10 @@ canonicalizeCondSignextOfHighBitExtractToSignextHighBitExtract( m_Shl(m_Constant(SignExtendingValueBaseConstant), m_ZExtOrSelf(m_Specific(NBits))))) return nullptr; - // If we `add`, then the constant should be all-ones, else it should be one. - if (I.getOpcode() == Instruction::Add - ? !match(SignExtendingValueBaseConstant, m_AllOnes()) - : !match(SignExtendingValueBaseConstant, m_One())) + // If we `sub`, then the constant should be one, else it should be all-ones. + if (I.getOpcode() == Instruction::Sub + ? !match(SignExtendingValueBaseConstant, m_One()) + : !match(SignExtendingValueBaseConstant, m_AllOnes())) return nullptr; auto *NewAShr = BinaryOperator::CreateAShr(X, LowBitsToSkip, @@ -1403,8 +1404,7 @@ Instruction *InstCombiner::visitAdd(BinaryOperator &I) { return V; if (Instruction *V = - canonicalizeCondSignextOfHighBitExtractToSignextHighBitExtract( - I, Builder)) + canonicalizeCondSignextOfHighBitExtractToSignextHighBitExtract(I)) return V; if (Instruction *SatAdd = foldToUnsignedSaturatedAdd(I)) @@ -2006,8 +2006,7 @@ Instruction *InstCombiner::visitSub(BinaryOperator &I) { } if (Instruction *V = - canonicalizeCondSignextOfHighBitExtractToSignextHighBitExtract( - I, Builder)) + canonicalizeCondSignextOfHighBitExtractToSignextHighBitExtract(I)) return V; if (Instruction *Ext = narrowMathIfNoOverflow(I)) diff --git a/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp b/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp index db5095b..4a30b60 100644 --- a/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp +++ b/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp @@ -2725,6 +2725,10 @@ Instruction *InstCombiner::visitOr(BinaryOperator &I) { } } + if (Instruction *V = + canonicalizeCondSignextOfHighBitExtractToSignextHighBitExtract(I)) + return V; + return nullptr; } diff --git a/llvm/lib/Transforms/InstCombine/InstCombineInternal.h b/llvm/lib/Transforms/InstCombine/InstCombineInternal.h index 4519dc0..74881a5 100644 --- a/llvm/lib/Transforms/InstCombine/InstCombineInternal.h +++ b/llvm/lib/Transforms/InstCombine/InstCombineInternal.h @@ -393,6 +393,8 @@ public: Value *reassociateShiftAmtsOfTwoSameDirectionShifts( BinaryOperator *Sh0, const SimplifyQuery &SQ, bool AnalyzeForSignBitExtraction = false); + Instruction *canonicalizeCondSignextOfHighBitExtractToSignextHighBitExtract( + BinaryOperator &I); Instruction *foldVariableSignZeroExtensionOfVariableHighBitExtract( BinaryOperator &OldAShr); Instruction *visitAShr(BinaryOperator &I); diff --git a/llvm/test/Transforms/InstCombine/conditional-variable-length-signext-after-high-bit-extract.ll b/llvm/test/Transforms/InstCombine/conditional-variable-length-signext-after-high-bit-extract.ll index 3dc1fd2..cb4d38d 100644 --- a/llvm/test/Transforms/InstCombine/conditional-variable-length-signext-after-high-bit-extract.ll +++ b/llvm/test/Transforms/InstCombine/conditional-variable-length-signext-after-high-bit-extract.ll @@ -57,7 +57,7 @@ define i32 @t0_notrunc_or(i32 %data, i32 %nbits) { ; CHECK-NEXT: call void @use1(i1 [[SHOULD_SIGNEXT]]) ; CHECK-NEXT: call void @use32(i32 [[ALL_BITS_EXCEPT_LOW_NBITS]]) ; CHECK-NEXT: call void @use32(i32 [[MAGIC]]) -; CHECK-NEXT: [[SIGNEXTENDED:%.*]] = or i32 [[HIGH_BITS_EXTRACTED]], [[MAGIC]] +; CHECK-NEXT: [[SIGNEXTENDED:%.*]] = ashr i32 [[DATA]], [[LOW_BITS_TO_SKIP]] ; CHECK-NEXT: ret i32 [[SIGNEXTENDED]] ; %low_bits_to_skip = sub i32 32, %nbits @@ -152,14 +152,14 @@ define i32 @t2_trunc_or(i64 %data, i32 %nbits) { ; CHECK-NEXT: [[HIGH_BITS_EXTRACTED:%.*]] = trunc i64 [[HIGH_BITS_EXTRACTED_WIDE]] to i32 ; CHECK-NEXT: [[SHOULD_SIGNEXT:%.*]] = icmp slt i64 [[DATA]], 0 ; CHECK-NEXT: [[ALL_BITS_EXCEPT_LOW_NBITS:%.*]] = shl i32 -1, [[NBITS]] -; CHECK-NEXT: [[MAGIC:%.*]] = select i1 [[SHOULD_SIGNEXT]], i32 [[ALL_BITS_EXCEPT_LOW_NBITS]], i32 0 ; CHECK-NEXT: call void @use32(i32 [[LOW_BITS_TO_SKIP]]) ; CHECK-NEXT: call void @use64(i64 [[LOW_BITS_TO_SKIP_WIDE]]) ; CHECK-NEXT: call void @use64(i64 [[HIGH_BITS_EXTRACTED_WIDE]]) ; CHECK-NEXT: call void @use32(i32 [[HIGH_BITS_EXTRACTED]]) ; CHECK-NEXT: call void @use1(i1 [[SHOULD_SIGNEXT]]) ; CHECK-NEXT: call void @use32(i32 [[ALL_BITS_EXCEPT_LOW_NBITS]]) -; CHECK-NEXT: [[SIGNEXTENDED:%.*]] = or i32 [[MAGIC]], [[HIGH_BITS_EXTRACTED]] +; CHECK-NEXT: [[TMP1:%.*]] = ashr i64 [[DATA]], [[LOW_BITS_TO_SKIP_WIDE]] +; CHECK-NEXT: [[SIGNEXTENDED:%.*]] = trunc i64 [[TMP1]] to i32 ; CHECK-NEXT: ret i32 [[SIGNEXTENDED]] ; %low_bits_to_skip = sub i32 64, %nbits -- 2.7.4