From 3258443195f7574206dd90f7a67959a252737c51 Mon Sep 17 00:00:00 2001 From: David Majnemer Date: Fri, 16 May 2014 17:14:03 +0000 Subject: [PATCH] InstSimplify: Improve handling of ashr/lshr Summary: Analyze the range of values produced by ashr/lshr cst, %V when it is being used in an icmp. Reviewers: nicholas Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D3774 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@209000 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Analysis/InstructionSimplify.cpp | 22 +++++++++++++- test/Transforms/InstSimplify/compare.ll | 40 +++++++++++++++++++++++++ 2 files changed, 61 insertions(+), 1 deletion(-) diff --git a/lib/Analysis/InstructionSimplify.cpp b/lib/Analysis/InstructionSimplify.cpp index 4cad81b1398..3684fda854f 100644 --- a/lib/Analysis/InstructionSimplify.cpp +++ b/lib/Analysis/InstructionSimplify.cpp @@ -2001,7 +2001,7 @@ static Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS, // Many binary operators with constant RHS have easy to compute constant // range. Use them to check whether the comparison is a tautology. - uint32_t Width = CI->getBitWidth(); + unsigned Width = CI->getBitWidth(); APInt Lower = APInt(Width, 0); APInt Upper = APInt(Width, 0); ConstantInt *CI2; @@ -2038,6 +2038,13 @@ static Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS, APInt NegOne = APInt::getAllOnesValue(Width); if (CI2->getValue().ult(Width)) Upper = NegOne.lshr(CI2->getValue()) + 1; + } else if (match(LHS, m_LShr(m_ConstantInt(CI2), m_Value()))) { + // 'lshr CI2, x' produces [CI2 >> (Width-1), CI2]. + unsigned ShiftAmount = Width - 1; + if (!CI2->isZero() && cast(LHS)->isExact()) + ShiftAmount = CI2->getValue().countTrailingZeros(); + Lower = CI2->getValue().lshr(ShiftAmount); + Upper = CI2->getValue() + 1; } else if (match(LHS, m_AShr(m_Value(), m_ConstantInt(CI2)))) { // 'ashr x, CI2' produces [INT_MIN >> CI2, INT_MAX >> CI2]. APInt IntMin = APInt::getSignedMinValue(Width); @@ -2046,6 +2053,19 @@ static Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS, Lower = IntMin.ashr(CI2->getValue()); Upper = IntMax.ashr(CI2->getValue()) + 1; } + } else if (match(LHS, m_AShr(m_ConstantInt(CI2), m_Value()))) { + unsigned ShiftAmount = Width - 1; + if (!CI2->isZero() && cast(LHS)->isExact()) + ShiftAmount = CI2->getValue().countTrailingZeros(); + if (CI2->isNegative()) { + // 'ashr CI2, x' produces [CI2, CI2 >> (Width-1)] + Lower = CI2->getValue(); + Upper = CI2->getValue().ashr(ShiftAmount) + 1; + } else { + // 'ashr CI2, x' produces [CI2 >> (Width-1), CI2] + Lower = CI2->getValue().ashr(ShiftAmount); + Upper = CI2->getValue() + 1; + } } else if (match(LHS, m_Or(m_Value(), m_ConstantInt(CI2)))) { // 'or x, CI2' produces [CI2, UINT_MAX]. Lower = CI2->getValue(); diff --git a/test/Transforms/InstSimplify/compare.ll b/test/Transforms/InstSimplify/compare.ll index 0e270bbe0f9..1a62e27dd8c 100644 --- a/test/Transforms/InstSimplify/compare.ll +++ b/test/Transforms/InstSimplify/compare.ll @@ -826,3 +826,43 @@ define i1 @compare_dividend(i32 %a) { ; CHECK-LABEL: @compare_dividend ; CHECK-NEXT: ret i1 false } + +define i1 @lshr_ugt_false(i32 %a) { + %shr = lshr i32 1, %a + %cmp = icmp ugt i32 %shr, 1 + ret i1 %cmp +; CHECK-LABEL: @lshr_ugt_false +; CHECK-NEXT: ret i1 false +} + +define i1 @exact_lshr_ugt_false(i32 %a) { + %shr = lshr exact i32 30, %a + %cmp = icmp ult i32 %shr, 15 + ret i1 %cmp +; CHECK-LABEL: @exact_lshr_ugt_false +; CHECK-NEXT: ret i1 false +} + +define i1 @lshr_sgt_false(i32 %a) { + %shr = lshr i32 1, %a + %cmp = icmp sgt i32 %shr, 1 + ret i1 %cmp +; CHECK-LABEL: @lshr_sgt_false +; CHECK-NEXT: ret i1 false +} + +define i1 @ashr_sgt_false(i32 %a) { + %shr = ashr i32 -30, %a + %cmp = icmp sgt i32 %shr, -1 + ret i1 %cmp +; CHECK-LABEL: @ashr_sgt_false +; CHECK-NEXT: ret i1 false +} + +define i1 @exact_ashr_sgt_false(i32 %a) { + %shr = ashr exact i32 -30, %a + %cmp = icmp sgt i32 %shr, -15 + ret i1 %cmp +; CHECK-LABEL: @exact_ashr_sgt_false +; CHECK-NEXT: ret i1 false +} -- 2.34.1