From a34cab9be72f0e4b8e03838aad617d34c7c48063 Mon Sep 17 00:00:00 2001
From: Andrea Di Biagio <Andrea_DiBiagio@sn.scee.net>
Date: Wed, 17 Sep 2014 11:32:31 +0000
Subject: [PATCH] [InstCombine] Fix wrong folding of constant comparison
 involving ahsr and negative quantities (PR20945).

Example:
define i1 @foo(i32 %a) {
  %shr = ashr i32 -9, %a
  %cmp = icmp ne i32 %shr, -5
  ret i1 %cmp
}

Before this fix, the instruction combiner wrongly thought that %shr
could have never been equal to -5. Therefore, %cmp was always folded to 'true'.
However, when %a is equal to 1, then %cmp evaluates to 'false'. Therefore,
in this example, it is not valid to fold %cmp to 'true'.
The problem was only affecting the case where the comparison was between
negative quantities where one of the quantities was obtained from arithmetic
shift of a negative constant.

This patch fixes the problem with the wrong folding (fixes PR20945).
With this patch, the 'icmp' from the example is now simplified to a
comparison between %a and 1. This still allows us to get rid of the arithmetic
shift (%shr).



git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@217950 91177308-0d34-0410-b5e6-96231b3b80d8
---
 .../InstCombine/InstCombineCompares.cpp       | 22 +++++++++++--------
 test/Transforms/InstCombine/icmp-shr.ll       | 15 +++++++++++++
 2 files changed, 28 insertions(+), 9 deletions(-)

diff --git a/lib/Transforms/InstCombine/InstCombineCompares.cpp b/lib/Transforms/InstCombine/InstCombineCompares.cpp
index e1c72430d7e..00623b1cbf6 100644
--- a/lib/Transforms/InstCombine/InstCombineCompares.cpp
+++ b/lib/Transforms/InstCombine/InstCombineCompares.cpp
@@ -1085,29 +1085,33 @@ Instruction *InstCombiner::FoldICmpCstShrCst(ICmpInst &I, Value *Op, Value *A,
     return getICmp(I.ICMP_EQ, A, ConstantInt::getNullValue(A->getType()));
   }
 
+  bool IsNegative = false;
   if (IsAShr) {
     if (AP1.isNegative() != AP2.isNegative()) {
       // Arithmetic shift will never change the sign.
       return getConstant(false);
     }
-    // Both the constants are negative, take their positive to calculate
-    // log.
+    // Both the constants are negative, take their positive to calculate log.
     if (AP1.isNegative()) {
-      AP1 = -AP1;
-      AP2 = -AP2;
+      if (AP1.slt(AP2))
+        // Right-shifting won't increase the magnitude.
+        return getConstant(false);
+      IsNegative = true;
     }
   }
 
-  if (AP1.ugt(AP2)) {
+  if (!IsNegative && AP1.ugt(AP2))
     // Right-shifting will not increase the value.
     return getConstant(false);
-  }
 
   // Get the distance between the highest bit that's set.
-  int Shift = AP2.logBase2() - AP1.logBase2();
+  int Shift;
+  if (IsNegative)
+    Shift = (-AP2).logBase2() - (-AP1).logBase2();
+  else
+    Shift = AP2.logBase2() - AP1.logBase2();
 
-  // Use lshr here, since we've canonicalized to +ve numbers.
-  if (AP1 == AP2.lshr(Shift))
+  if (IsAShr ? AP1 == AP2.ashr(Shift) : AP1 == AP2.lshr(Shift))
     return getICmp(I.ICMP_EQ, A, ConstantInt::get(A->getType(), Shift));
 
   // Shifting const2 will never be equal to const1.
diff --git a/test/Transforms/InstCombine/icmp-shr.ll b/test/Transforms/InstCombine/icmp-shr.ll
index 36490e5d10a..41009d24c31 100644
--- a/test/Transforms/InstCombine/icmp-shr.ll
+++ b/test/Transforms/InstCombine/icmp-shr.ll
@@ -675,3 +675,18 @@ define i1 @nonexact_ashr_ne_noexactlog(i8 %a) {
  %cmp = icmp ne i8 %shr, -30
  ret i1 %cmp
 }
+
+; Don't try to fold the entire body of function @PR20945 into a
+; single `ret i1 true` statement.
+; If %B is equal to 1, then this function would return false.
+; As a consequence, the instruction combiner is not allowed to fold %cmp
+; to 'true'. Instead, it should replace %cmp with a simpler comparison
+; between %B and 1.
+
+; CHECK-LABEL: @PR20945(
+; CHECK: icmp ne i32 %B, 1
+define i1 @PR20945(i32 %B) {
+  %shr = ashr i32 -9, %B
+  %cmp = icmp ne i32 %shr, -5
+  ret i1 %cmp
+}
-- 
2.34.1