[InstCombine] Fix wrong folding of constant comparisons involving ashr and negative values (PR21222).

[andreadb]

Summary

Hi,

Here is a case where the instruction combiner wrongly folds an 'icmp' instruction.
;;
define i1 @test(i32 %B) {

%shr = ashr i32 -93, %B
%cmp = icmp eq i32 %shr, -2
ret i1 %cmp

}
;;

Function @test returns true when %B is equal to 6 (that is because -93 >> 6 = -2).
However, the Instruction Combiner wrongly thinks that there is no 'B' that solves equation: -93 >> B == -2.
Consequently, the entire body of function @test is wrongly folded into a return i1 false.

The problem is in the folding logic located in method InstCombiner::FoldICmpCstShrCst (InstCombineCompares.cpp) which wrongly computes the distance between two negative values.

With:

AP1 < 0
AP2 < 0
AP2 != 0
AP1 != 0
AP1 > AP2

The distance between AP2 and AP1 (i.e. the distance between the highest bits set) is wrongly computed as:

(-AP2).logBase2() - (-AP1).logBase2()

It should be computed instead taking the ones' complement of AP2 and AP1:

(~AP2).logBase2() - (~AP1).logBase2()

This patch fixes the problem with the wrong folding of icmp.

Please let me know if ok to submit.
Thanks!
Andrea

[suyog]

Hi Andrea,

Thanks for investigating and fixing the bug.
I agree with your point that distance should be calculated using one's compliment
instead of two's compliment.

LGTM.

Closed by commit rL219406 (authored by adibiagio).

llvm/trunk/lib/Transforms/InstCombine/InstCombineCompares.cpp

Instruction *InstCombiner::FoldICmpCstShrCst(ICmpInst &I, Value *Op, Value *A,
 
   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;
   if (IsNegative)
-    Shift = (-AP2).logBase2() - (-AP1).logBase2();
+    // Get the ones' complement of AP2 and AP1 when computing the distance.
+    Shift = (~AP2).logBase2() - (~AP1).logBase2();
   else
     Shift = AP2.logBase2() - AP1.logBase2();
 
   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.
   return getConstant(false);

llvm/trunk/test/Transforms/InstCombine/icmp-shr.ll

 
 ; 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
 }
+
+; CHECK-LABEL: @PR21222
+; CHECK: icmp eq i32 %B, 6
+define i1 @PR21222(i32 %B) {
+  %shr = ashr i32 -93, %B
+  %cmp = icmp eq i32 %shr, -2
+  ret i1 %cmp
+}