PR19958 wrong code at -O1 and above on x86_64-linux-gnu (InstCombine)

[suyog]

Summary

This patch rectifies icmp instruction combine problem seen because of previous optimization patch for 'ashr/lshr exact' as mentioned in bug 19958.
I admit i wrote the previous patch keeping only equality in mind (not considering all cases is bad practice, will be careful in future).

This patch for now handles 'icmp eq/ne' only for 'ashr/lsher exact'. Added relevant test cases.

For other icmp instructions, some observations:

define i1 @f(i32 %x) {

%y = lshr exact i32 8, %x
%cmp = icmp ult i32 %y, 2
ret i1 %cmp

}

Here, in above example, as %x increases, %y decreases and hence comparison with same icmp instruction was giving wrong output.

while in ,

define i1 @f(i32 %x) {

%y = lshr exact i32 -8, %x
%cmp = icmp ult i32 %y, -2
ret i1 %cmp

}

as %x increases, %y also increases mathematically. Hence comparison with same icmp instruction is fine in this case.

This was not captured in original patch and hence wrong output. This can be handled in following two ways:

1. if const1,const2 are both positive, then icmp instruction should be swapped (something like getSwappedPredicate()). if const1,const2 are both negative, then keep the icmp instruction as it is. Note : getInversePredicate() won't work.
2. if const1/const2 are both positive, swap the operands, keeping the icmp instruction as it is. No change if const1,const2 are both negative.

Note : Cases where const1 and const2 have opposite sign - one is positive other is negative are always true/false.

This is handled by simplifyicmp call and it never reaches our patch. I checked it with both ashr/lshr for this case.

I will verify if above two approaches for other icmp instructions are universally true for both ashr/lshr and come up with another patch.
Added a TODO for the same.

Please review this patch which handles equality for ashr/lshr exact.
Any comments/suggestions are most welcomed.

Thanks.

• Suyog

[spatel]

Please check for typos: lhsr -> lshr

[spatel]

I'm not sure what LLVM test case policy is, but I think it would be good to have contra-test cases too. Eg, a test case that doesn't specify 'exact', a test case that isn't eq/ne - these would ensure that your code is not firing when it wasn't intended. Also, can you include a 'ne' test?

[suyog]

Corrected typo.

Added test cases for

• exact ne
• no exact
• no ne/eq

Please help in reviewing if this looks good or any more test cases are required.

Thanks

• Suyog

[spatel]

Minor nit: fear the 80-column police
// (icmp eq/ne (ashr exact const2, A), const1) -> icmp eq/ne A, Log2(const2/const1)

This line's indentation looks wrong too:
return new ICmpInst(I.getPredicate(), A,

Major nit:
unsigned shift = Quotient.logBase2();

What if Quotient isn't power of 2?

I think this leads to miscompiled code:
$ cat 19958.ll
@a = common global i32 0, align 4
define i1 @main() {
%a = load i32* @a, align 4
%shr = lshr exact i32 80, %a
%cmp = icmp eq i32 %shr, 41 ; NOTE: non-power-of-2 comparison
ret i1 %cmp
}
$ ./opt 19958.ll -S | ./llc | ./clang -x assembler - -o a.out ; ./a.out ; echo $?
0
$ ./opt -instcombine 19958.ll -S | ./llc | ./clang -x assembler - -o a.out ; ./a.out ; echo $?
1

[spatel]

I like the additional test cases, but they would be better if the constants were at the limits rather than just random numbers in the middle of the possible values.

[suyog]

Thanks for the review.

Updated patch to handle exact division and exact log2. We were handling exact division and exact log2 for ashr in instsimplify, and not for lshr.

Now we are handling for both. Updated test cases which includes constants to the extreme limit and not something random in between.
Also took care of 80 lines clang-format. :)

Please help in reviewing the patch.

[suyog]

Gentle Ping !!

[suyog]

Gentle Ping !!

[spatel]

Sorry for the delay. LGTM...but considering that versions of this patch have caused miscompiles twice and I'm pretty new here, I think we should have someone with more instcombine experience give final approval in case I've missed anything.

[nicholas]

lib/Transforms/InstCombine/InstCombineCompares.cpp

2353

APInt::isMinValue() is faster than APInt::operator== even though it's less clear to read.

2354

APInt::sdivrem is as fast as a single sdiv or srem. Please use it then text the 'rem' results.

test/Transforms/InstCombine/icmp.ll

1427

The bugs from last time were due to icmp non-equality comparisons, right? Are those tests already in this code or should you be adding tests to make sure you don't miscompile those cases here?

[suyog]

Hi Duncan, Nick, Rafael, Sanjay,

I have modified the code to calculate shift by Log2(Const2) - Log2(Const1)
instead of Log2(Const2/Const1) to avoid expensive division operation as per Duncan's suggestion.
Also handled few more conditions for 0.
Added additional test cases as well.

(I am doing this for icmp eq/ne only for now,
other icmp instructions are TODO item as they need some verification)

Can you please help in reviewing this modified patch.

Your suggestions/comments are most awaited. :)

Thanks,
Suyog

[suyog]

Hi Duncan,

Thanks for your explanation. I have handled case for 'lshr' separately now in the patch attached.

I have combined the logic for ashr/lshr as well as exact/non-exact as most of the logic is same.
Wherever there are special cases, i have handled them separately. I have added the logic for the
cases which were handled by 'instsimplify' to keep the logical flow as discussed.

I have combined the logic, since the 'match' functions are expensive, same for the log,
and our whole point of calculating difference of log was to avoid expensive division operation.

Please help in reviewing the patch. Your comments/suggestions are most welcomed :)

[suyog]

Hi Duncan,

Thanks for your review.
Couldn't spot the miscompiles earlier because i didn't comment out
the 'simplify' call. Now i modified the code and tested almost every
combination.

I have modified the code as per your suggestions :

• Made comments short and crisp as per your suggestion.
• included lambda helper functions to return appropriate constant and icmp instruction.
• included logic for both constants -1 for ashr as suggested (In my opinion if both constants are equal and not -1, then final icmp would be icmp eq/ne A, 0. The Predicate won't get inversed and will remain same. You had suggested using lambda function here to get inversed predicate. Correct me if my analysis is wrong.)
• used 'bool IsAShr' to avoid recalculation.
• removed LShrOperator block which was causing miscompiles.
• removed unnecessary shl/lshr distinction for exact and non exact
• moved all test cases to new file icmp-ashr.ll
• used msb_high/low instead of +ve/-ve and opposite msb
• tried including all combinations of ne/eq + exact/non-exact + lshr/ashr

Please help in reviewing the patch.

Your comments/suggestions are valuable and most awaited. :)

Thanks,
Suyog

[suyog]

Hi Duncan,

Made changes as per your suggestions :

• Wrote the whole logic in separate function. Didn't make it 'static', took 'cue' from other 'Foldicmp' functions.
• Removed TODO, will probably raise a separate PR for it.
• Updated comments, removed extra braces.
• defined variables just before their use.

Can you please see if this looks good to you?
Your comments/suggestions are most welcomed.

Thanks,
Suyog

[suyog]

Hi Duncan, Nick

As there is no guidance in the coding standards,
i looked at few files in InstCombine and comment style in them and
i found it better to include braces, wherever there is a comment inside 'if'.

if ( ) {
// comment
}

I removed/didn't add braces where there is no comment and a single statement block.

Please see if this looks good to you !!

[suyog]

Accepting this as per review in
http://comments.gmane.org/gmane.comp.compilers.llvm.cvs/191371

[suyog]

Closed by commit rL213678 (authored by @suyog).

lib/Transforms/InstCombine/InstCombineCompares.cpp

Instruction *InstCombiner::visitICmpInst(ICmpInst &I) {
   unsigned Op1Cplxity = getComplexity(Op1);
 
   /// Orders the operands of the compare so that they are listed from most
   /// complex to least complex.  This puts constants before unary operators,
   /// before binary operators.
   if (Op0Cplxity < Op1Cplxity ||
         (Op0Cplxity == Op1Cplxity &&
          swapMayExposeCSEOpportunities(Op0, Op1))) {
     I.swapOperands();
     std::swap(Op0, Op1);
     Changed = true;
   }
 
   if (Value *V = SimplifyICmpInst(I.getPredicate(), Op0, Op1, DL))
     return ReplaceInstUsesWith(I, V);
 
   // comparing -val or val with non-zero is the same as just comparing val
   // ie, abs(val) != 0 -> val != 0
if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) {
 
     // (icmp ne/eq (sub A B) 0) -> (icmp ne/eq A, B)
     if (I.isEquality() && CI->isZero() &&
         match(Op0, m_Sub(m_Value(A), m_Value(B)))) {
       // (icmp cond A B) if cond is equality
       return new ICmpInst(I.getPredicate(), A, B);
     }
 
+    // PR19753:
+    // (icmp eq/ne (ashr/lshr const2, A), const1) ->
+    // (icmp eq/ne A, Log2(const2/const1)) ->
+    // (icmp eq/ne A, Log2(const2) - Log2(const1)).
+    // TODO : Handle this for other icmp instructions.
+    if (I.isEquality()) {
+      ConstantInt *CI2;
+      if (match(Op0, m_AShr(m_ConstantInt(CI2), m_Value(A))) ||
+          match(Op0, m_LShr(m_ConstantInt(CI2), m_Value(A)))) {
+        APInt AP1 = CI->getValue();
+        APInt AP2 = CI2->getValue();
+        int Shift;
+        if (!AP1) {
+          // if const1 = const2 = 0, return true.
+          if (!AP2)
+            return ReplaceInstUsesWith(I, ConstantInt::getTrue(I.getType()));
+          // if const1 = 0, const2 !=0 and right shift is 'exact',
+          // return false.
+          if (cast<BinaryOperator>(Op0)->isExact())
+            return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getType()));
+          // if const1 = 0, right shift is non-exact and const2 is -ve,
+          // return false.
+          if (AP2.isNegative())
+            return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getType()));
+          // if const1 = 0, shift is non-exact and const2 is +ve ->
+          // icmp ugt A, Log2(const2).
+          Shift = AP2.logBase2();
+          return new ICmpInst(I.ICMP_UGT, A,
+                              ConstantInt::get(A->getType(), Shift));
+        }
+
+        // Shifting 0 by any value gives 0.
+        if (!AP2)
+          return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getType()));
+
+        // if const1 = const2 -> icmp eq/ne A, 0
+        if (AP1 == AP2)
+          return new ICmpInst(I.getPredicate(), A,
+                              ConstantInt::getNullValue(A->getType()));
+
+        if (isa<AShrOperator>(Op0)) {
+          // const1 and const2 are sign opposite, arithmatic shift will retain
+          // sign and hence const2 will never equal const1.
+          if (AP1.isNegative() != AP2.isNegative())
+            return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getType()));
+          // Both the constants are negative, take their positive to calculate
+          // log.
+          if (AP1.isNegative()) {
+            AP1 = -AP1;
+            AP2 = -AP2;
+          }
+        }
+
+        if (isa<LShrOperator>(Op0)) {
+          // logical shift of const2 will be +ve which will not be equal
+          // to -ve const1.
+          if (AP1.isNegative())
+            return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getType()));
+          // const1 is +ve and const2 is -ve, logical shift of const2 may
+          // equal const1, hence take abs(AP2) to calculate log.
+          if (AP2.isNegative())
+            AP2 = -AP2;
+        }
+
+        // Now we have const1 = abs(const1) and const2 = abs(const2).
+        // If const1 is greater than const2,
+        // right shifting const2 will never equal to const1.
+        if (AP1.ugt(AP2))
+          return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getType()));
+
+        Shift = AP2.logBase2() - AP1.logBase2();
+
+        // if shift is 'exact', then use shl to check equality.
+        if ((cast<BinaryOperator>(Op0)->isExact()) && (AP1.shl(Shift) == AP2))
+          return new ICmpInst(I.getPredicate(), A,
+                              ConstantInt::get(A->getType(), Shift));
+        // Use lshr here, since we've canonicalized to +ve numbers.
+        if (AP1 == AP2.lshr(Shift))
+          return new ICmpInst(I.getPredicate(), A,
+                              ConstantInt::get(A->getType(), Shift));
+        // Shifting const2 will never be equal to const1, return false.
+        return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getType()));
+      }
+    }
+
     // If we have an icmp le or icmp ge instruction, turn it into the
     // appropriate icmp lt or icmp gt instruction.  This allows us to rely on
     // them being folded in the code below.  The SimplifyICmpInst code has
     // already handled the edge cases for us, so we just assert on them.
     switch (I.getPredicate()) {
     default: break;
     case ICmpInst::ICMP_ULE:
       assert(!CI->isMaxValue(false));                 // A <=u MAX -> TRUE

test/Transforms/InstCombine/icmp.ll

 ; CHECK-LABEL: @icmp_neg_cst_slt
 ; CHECK-NEXT: [[CMP:%[a-z0-9]+]] = icmp sgt i32 %a, 10
 ; CHECK-NEXT: ret i1 [[CMP]]
 define i1 @icmp_neg_cst_slt(i32 %a) {
   %1 = sub nsw i32 0, %a
   %2 = icmp slt i32 %1, -10
   ret i1 %2
 }
+
+; CHECK-LABEL: @exact_lshr_both_zero
+; CHECK-NEXT: ret i1 true
+define i1 @exact_lshr_both_zero(i32 %a) {
+  %shr = lshr exact i32 0, %a
+  %cmp = icmp eq i32 %shr, 0
+  ret i1 %cmp
+}
+
+; CHECK-LABEL: @exact_ashr_both_zero
+; CHECK-NEXT: ret i1 true
+define i1 @exact_ashr_both_zero(i32 %a) {
+  %shr = ashr exact i32 0, %a
+  %cmp = icmp eq i32 %shr, 0
+  ret i1 %cmp
+}
+
+; CHECK-LABEL: @nonexact_lshr_both_zero
+; CHECK-NEXT: ret i1 true
+define i1 @nonexact_lshr_both_zero(i32 %a) {
+  %shr = lshr i32 0, %a
+  %cmp = icmp eq i32 %shr, 0
+  ret i1 %cmp
+}
+
+; CHECK-LABEL: @nonexact_ashr_both_zero
+; CHECK-NEXT: ret i1 true
+define i1 @nonexact_ashr_both_zero(i32 %a) {
+  %shr = ashr i32 0, %a
+  %cmp = icmp eq i32 %shr, 0
+  ret i1 %cmp
+}
+
+; CHECK-LABEL: @exact_lshr_last_zero
+; CHECK-NEXT: ret i1 false
+define i1 @exact_lshr_last_zero(i32 %a) {
+  %shr = lshr exact i32 64, %a
+  %cmp = icmp eq i32 %shr, 0
+  ret i1 %cmp
+}
+
+; CHECK-LABEL: @exact_ashr_last_zero
+; CHECK-NEXT: ret i1 false
+define i1 @exact_ashr_last_zero(i32 %a) {
+  %shr = ashr exact i32 -2147483648, %a
+  %cmp = icmp eq i32 %shr, 0
+  ret i1 %cmp
+}
+
+; CHECK-LABEL: @nonexact_lshr_last_zero
+; CHECK-NEXT: ret i1 false
+define i1 @nonexact_lshr_last_zero(i32 %a) {
+  %shr = lshr i32 -2147483648, %a
+  %cmp = icmp eq i32 %shr, 0
+  ret i1 %cmp
+}
+
+; CHECK-LABEL: @nonexact_ashr_last_zero
+; CHECK-NEXT: ret i1 false
+define i1 @nonexact_ashr_last_zero(i32 %a) {
+  %shr = ashr i32 -2147483648, %a
+  %cmp = icmp eq i32 %shr, 0
+  ret i1 %cmp
+}
+
+; CHECK-LABEL: @lshr_first_positive_last_zero
+; CHECK-NEXT: icmp ugt i32 %a, 30
+define i1 @lshr_first_positive_last_zero(i32 %a) {
+  %shr = lshr i32 1073741824, %a
+  %cmp = icmp eq i32 %shr, 0
+  ret i1 %cmp
+}
+
+; CHECK-LABEL: @ashr_first_positive_second_zero
+; CHECK-NEXT: icmp ugt i32 %a, 30
+define i1 @ashr_first_positive_second_zero(i32 %a) {
+ %shr = ashr i32 1073741824, %a
+ %cmp = icmp eq i32 %shr, 0
+ ret i1 %cmp
+}
+
+; CHECK-LABEL: @lshr_first_zero
+; CHECK-NEXT: ret i1 false
+define i1 @lshr_first_zero(i32 %a) {
+  %shr = lshr i32 0, %a
+  %cmp = icmp eq i32 %shr, 2 
+  ret i1 %cmp
+}
+
+; CHECK-LABEL: @exact_ashr_both_equal
+; CHECK-NEXT: icmp ne i32 %a, 0
+define i1 @exact_ashr_both_equal(i32 %a) {
+ %shr = ashr exact i32 -2147483648, %a
+ %cmp = icmp ne i32 %shr, -2147483648
+ ret i1 %cmp
+}
+
+; CHECK-LABEL: @exact_lshr_both_equal
+; CHECK-NEXT: icmp eq i32 %a, 0
+define i1 @exact_lshr_both_equal(i32 %a) {
+ %shr = lshr exact i32 1073741824, %a
+ %cmp = icmp eq i32 %shr, 1073741824
+ ret i1 %cmp
+}
+
+; CHECK-LABEL: @exact_ashr_opposite_sign
+; CHECK-NEXT: ret i1 false
+define i1 @exact_ashr_opposite_sign(i32 %a) {
+  %shr = ashr exact i32 -2147483648, %a
+  %cmp = icmp eq i32 %shr, 1
+  ret i1 %cmp
+}
+
+; CHECK-LABEL: @ashr_opposite_sign
+; CHECK-NEXT: ret i1 false
+define i1 @ashr_opposite_sign(i32 %a) {
+  %shr = ashr i32 -2147483648, %a
+  %cmp = icmp eq i32 %shr, 1
+  ret i1 %cmp
+}
+
+; CHECK-LABEL: @exact_lshr_opposite_sign
+; CHECK-NEXT: icmp eq i32 %a, 31
+define i1 @exact_lshr_opposite_sign(i32 %a) {
+  %shr = lshr exact i32 -2147483648, %a
+  %cmp = icmp eq i32 %shr, 1 
+  ret i1 %cmp
+}
+
+; CHECK-LABEL: @lshr_opposite_sign
+; CHECK-NEXT: icmp eq i32 %a, 31
+define i1 @lshr_opposite_sign(i32 %a) {
+  %shr = lshr i32 -2147483648, %a
+  %cmp = icmp eq i32 %shr, 1
+  ret i1 %cmp
+}
+
+; CHECK-LABEL: @exact_ashr_eq
+; CHECK-NEXT: icmp eq i32 %a, 31
+define i1 @exact_ashr_eq(i32 %a) {
+ %shr = ashr exact i32 -2147483648, %a
+ %cmp = icmp eq i32 %shr, -1
+ ret i1 %cmp
+}
+
+; CHECK-LABEL: @exact_ashr_ne
+; CHECK-NEXT: icmp ne i32 %a, 31
+define i1 @exact_ashr_ne(i32 %a) {
+ %shr = ashr exact i32 -2147483648, %a
+ %cmp = icmp ne i32 %shr, -1
+ ret i1 %cmp
+}
+
+; CHECK-LABEL: @exact_lshr_eq
+; CHECK-NEXT: icmp eq i32 %a, 30
+define i1 @exact_lshr_eq(i32 %a) {
+ %shr = lshr exact i32 1073741824, %a
+ %cmp = icmp eq i32 %shr, 1
+ ret i1 %cmp
+}
+
+; CHECK-LABEL: @exact_lshr_ne
+; CHECK-NEXT: icmp ne i32 %a, 30
+define i1 @exact_lshr_ne(i32 %a) {
+ %shr = lshr exact i32 1073741824, %a
+ %cmp = icmp ne i32 %shr, 1
+ ret i1 %cmp
+}
+
+; CHECK-LABEL: @exact_lshr_ne_noexactdiv
+; CHECK-NEXT: ret i1 false
+define i1 @exact_lshr_ne_noexactdiv(i32 %a) {
+ %shr = lshr exact i32 80, %a
+ %cmp = icmp ne i32 %shr, 31
+ ret i1 %cmp
+}
+
+; CHECK-LABEL: @exact_ashr_ne_noexactdiv
+; CHECK-NEXT: ret i1 false
+define i1 @exact_ashr_ne_noexactdiv(i32 %a) {
+ %shr = ashr exact i32 -80, %a
+ %cmp = icmp ne i32 %shr, -41
+ ret i1 %cmp
+}
+
+; CHECK-LABEL: @exact_ashr_no_neeq
+; CHECK-NEXT: ashr exact i32 -30, %a
+; CHECK-NEXT: icmp ult i32 %shr, -15
+define i1 @exact_ashr_no_neeq(i32 %a) {
+ %shr = ashr exact i32 -30, %a
+ %cmp = icmp ult i32 %shr, -15
+ ret i1 %cmp
+}
+
+; CHECK-LABEL: @exact_lshr_no_neeq
+; CHECK-NEXT: lshr exact i32 1073741824, %a
+; CHECK-NEXT: icmp ugt i32 %shr, 1
+define i1 @exact_lshr_no_neeq(i32 %a) {
+ %shr = lshr exact i32 1073741824, %a
+ %cmp = icmp ugt i32 %shr, 1
+ ret i1 %cmp
+}