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

1126

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)

1129

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

1126

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

1129

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 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)) {
-    // Right-shifting will not increase the value.
+  if (!IsNegative && AP1.ugt(AP2))
+    // Right-shifting won't increase the magnitude.
     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.
   return getConstant(false);
 }
 
 /// visitICmpInstWithInstAndIntCst - Handle "icmp (instr, intcst)".
 ///
 Instruction *InstCombiner::visitICmpInstWithInstAndIntCst(ICmpInst &ICI,
                                                           Instruction *LHSI,
                                                           ConstantInt *RHS) {
   const APInt &RHSV = RHS->getValue();
 
   switch (LHSI->getOpcode()) {
   case Instruction::Trunc:
     if (ICI.isEquality() && LHSI->hasOneUse()) {
       // Simplify icmp eq (trunc x to i8), 42 -> icmp eq x, 42|highbits if all
       // of the high bits truncated out of x are known.
       unsigned DstBits = LHSI->getType()->getPrimitiveSizeInBits(),
              SrcBits = LHSI->getOperand(0)->getType()->getPrimitiveSizeInBits();
       APInt KnownZero(SrcBits, 0), KnownOne(SrcBits, 0);
       computeKnownBits(LHSI->getOperand(0), KnownZero, KnownOne, 0, &ICI);
 

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 @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
+}