InstCombine: constant comparison involving ashr is wrongly simplified (PR20945).

[andreadb]

Summary

Example:

;;;;
define i32 @negative_constants(i32 %B) {
entry:

%shr = ashr i32 -9, %B
%cmp = icmp ne i32 %shr, -5
br i1 %cmp, label %if.then, label %return

if.then:

br label %return

return:

%retval = phi i32 [ 0, %if.then ], [ 42, %entry ]
ret i32 %retval

}
;;;

The instruction combiner wrongly thinks that statement 'ashr i32 -9, %B' can never evaluate to -5. Therefore, it wrongly assumes that %cmp would always be 'true' and the branch to 'if.then' would always be taken.

In this reproducible, if %B is equal to 1, then %cmp is 'false' (since %shr would be equal to -5).
Therefore, it is not safe to fold %cmp to 'true'. What instead should be done is converting the comparison between %shr and -5 into a comparison between %B and 1. This would allow us to get rid of the arithmetic shift (and eventually simplify the CFG folding the compare-and-branch into a single select of either 0 or 42).

This is a regression introduced by revision 213678. This bug seems to affect only the case where constants are both negative values.

Please let me know if ok to submit.

Thanks,
Andrea

[suyog]

Hi Andrea,

Thanks for pointing out the bug. I went through the code and the example and
i agree that we need to revert the canonicalization if both AP1 and AP2 are negative.
Your patch seems ok to me, though i would like others to approve it.

Also i had few suggestions for comments and test case in the patch which i noted inline
(feel free to edit if they seem good to you).

I would like Duncan to review this for final commit as we had worked on the original patch.

lib/Transforms/InstCombine/InstCombineCompares.cpp

1123

This comment can be made crisp. Something like - Revert the canonicalization if both AP1 and AP2 are negative,
as (-AP2 >> Shift == -AP1) is not equal to (AP2 >> Shift == AP1)

1126

This comment can be removed.

test/Transforms/InstCombine/icmp-shr.ll

704

This test case can be simplified (exclude if-else part as patch focuses on icmp result)

; CHECK-LABEL: @negative_constants(
; CHECK: icmp eq i32 %B, 1
define i1 @negative_constants(i32 %B) {
  %shr = ashr i32 -9, %B
  %cmp = icmp ne i32 %shr, -5
  ret i1 %cmp
}

[andreadb]

Hi Suyog,

Thanks for the useful comments/suggestions!
I will upload another patch soon.

lib/Transforms/InstCombine/InstCombineCompares.cpp

1123

Ah yes. I was not very happy about my original comment here... I like your suggestion. I will fix.

1126

I will fix it.

test/Transforms/InstCombine/icmp-shr.ll

704

True. I will upload a new patch with the simplified test case (I will also address the other comments).

[andreadb]

Updated patch that addresses the comments from Suyog.

[andreadb]

Hi Duncan,

Here is an updated patch which I think/hope addresses all your comments.

There is one main difference with respect to what you suggested (see below)

Then change this to:

if (!IsNegative && AP1.ugt(AP2))
  // Right-shifting won't increase the magnitude.
  return getConstant(false);

That check should also take into account the case where 'IsAShr' is false, AP2 is negative and AP1 is positive.
Otherwise, it would have failed for the following case:

{code}
define i1 @foo(i8 %a) {

%shr = lshr exact i8 -128, %a
%cmp = icmp eq i8 %shr, 1
ret i1 %cmp

}
{code}

Please let me know what you think.
Thanks,
Andrea

[andreadb]

I don't think that case exists. lshr deals with unsigned numbers.
There's no such thing as a negative unsigned number. For lshr, it's
easier to think about numbers as bitstrings.

Otherwise, it would have failed for the following case:

{code}
define i1 @foo(i8 %a) {
%shr = lshr exact i8 -128, %a
%cmp = icmp eq i8 %shr, 1
ret i1 %cmp
}
{code}

In binary, this translates to:

define i1 @foo(i8 %a) {
  %shr = lshr exact i8 0b10000000, %a
  %cmp = icmp eq i8 %shr, 0b00000001
  ret i1 %cmp
}

AFAICT, this transformation should produce:

define i1 @foo(i8 %a) {
  %cmp = icmp eq i8 %a, 7
  ret i1 %cmp
}

Does it do something else? What? Can you add this as a testcase?

Sorry, you are right.
That test does exactly what you said (i.e. it produces the compare between %a and 7).
Btw, that is from test 'icmp-shr.ll'. It is function @exact_lshr_eq_opposite_msb.
I think I was probably using the wrong compiler when I saw that test case failing.. sorry for the noise.

Please let me know what you think.
Thanks,
Andrea

http://reviews.llvm.org/D5356

Files:
lib/Transforms/InstCombine/InstCombineCompares.cpp
test/Transforms/InstCombine/icmp-shr.ll
<D5356.13759.patch>

+ if (!IsAShr) {
+ bool IsAP1Negative = AP1.isNegative();
+ bool IsAP2Negative = AP2.isNegative();
+ if (IsAP1Negative && IsAP2Negative)
+ Logical shift by a non-zero quantity always changes the sign bit of a
+ negative number.
+ return getConstant(false);
+ if (IsAP1Negative)
+ Logical shift never affects the sign of a positive number.
+ return getConstant(false);
+ if (!IsAP2Negative && AP1.ugt(AP2))
+ Right-shifting will not increase the value.
+ return getConstant(false);
+ }

This new logic doesn't make sense to me. Note that isNegative() just
tells you whether the MSB is set to 1. How is the MSB relevant here?
(It certainly isn't a sign bit.)

I agree it is not relevant.
Again, sorry for the confusion.

Here is an updated patch.
-Andrea

lib/Transforms/InstCombine/InstCombineCompares.cpp

Instruction *InstCombiner::FoldICmpCstShrCst(ICmpInst &I, Value *Op, Value *A,
   if (AP1 == AP2) {
     if (AP1.isAllOnesValue() && IsAShr) {
       // Arithmatic shift of -1 is always -1.
       return getConstant(true);
     }
     return getICmp(I.ICMP_EQ, A, ConstantInt::getNullValue(A->getType()));
   }
 
+  bool AreBothNegative = 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.
     if (AP1.isNegative()) {
       AP1 = -AP1;
       AP2 = -AP2;
+      AreBothNegative = true;
     }
   }
 
   if (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();
 
-  // Use lshr here, since we've canonicalized to +ve numbers.
-  if (AP1 == AP2.lshr(Shift))
+  // Revert the canonicalization before testing if shifting AP2
+  // by 'Shift' count we can get AP1. It is wrong to assume that:
+  //
+  //  (-AP2 >> Shift == -AP1)  ==> (AP2 >> Shift == AP1)
+  //
+  // Example, with:
+  //  AP2 = -9;
+  //  AP1 = -5;
+  //
+  // With 'Shift' equal to 1, we have that:
+  //   -9 >> 1  == -5
+  // but
+  //   9 >> 1 != 5.
+  bool CanFoldCompare = false;
+  if (AreBothNegative) {
+    // Undo the canonicalization.
+    AP1 = -AP1;
+    AP2 = -AP2;
+    CanFoldCompare = AP1 == AP2.ashr(Shift);
+  } else
+    CanFoldCompare = AP1 == AP2.lshr(Shift); 
+
+  if (CanFoldCompare)
     return getICmp(I.ICMP_EQ, A, ConstantInt::get(A->getType(), Shift));
 
   // Shifting const2 will never be equal to const1.
   return getConstant(false);
 }
 
 /// visitICmpInstWithInstAndIntCst - Handle "icmp (instr, intcst)".
 ///

test/Transforms/InstCombine/icmp-shr.ll

 
 ; CHECK-LABEL: @nonexact_ashr_ne_noexactlog
 ; CHECK-NEXT: ret i1 true
 define i1 @nonexact_ashr_ne_noexactlog(i8 %a) {
  %shr = ashr i8 -90, %a
  %cmp = icmp ne i8 %shr, -30
  ret i1 %cmp
 }
+
+; Don't try to fold the entire body of function @negative_constants into a
+; single `ret i32 0` statement.
+; If %B is equal to 1, then this function would return 42. That is because
+; expression `-9 >> B` evaluates to -5 only if %B is equal to 1.
+; As a consequence, the instruction combiner should never fold %cmp to true.
+; Instead, it should simplify the comparison between %shr and -5 emitting a
+; simpler comparison between %B and 1.
+; Later on, this would allow to further simplify the CFG and emit a single
+; 'select' instruction instead of a compare+branch.
+
+; CHECK-LABEL: @negative_constants(
+; CHECK: icmp eq i32 %B, 1
+define i32 @negative_constants(i32 %B) {
+entry:
+  %shr = ashr i32 -9, %B
+  %cmp = icmp ne i32 %shr, -5
+  br i1 %cmp, label %if.then, label %return
+
+if.then:
+  br label %return
+
+return:
+  %retval = phi i32 [ 0, %if.then ], [ 42, %entry ]
+  ret i32 %retval
+}
+