InstCombineCompare with constant return false if we know it is never going to be equal

[suyog]

Summary

Hi,

This patch implements optimization mentioned in
http://www.cs.utah.edu/~regehr/souper/output_6.html
where we know that when comparing with a constant whose trailing zero's are less than trailing zero's of LHS, it will never be equal.

C test case :
int a, b;
void fn1() { b = a * ~1 == 1; }

gcc output (X86):
fn1:
movl $0, b(%rip)
ret

LLVM output before patch(X86) at O2 optimization :
fn1: # @fn1
movl a(%rip), %eax
addl %eax, %eax
cmpl $-1, %eax
sete %al
movzbl %al, %eax
movl %eax, b(%rip)
retq

LLVM Output after patch (X86) at O2 optimization:
fn1:

movl	$0, b(%rip)

retq

Added test case for the same.
TODO : Generalize this for all constants, currently implemented for comparing with 1.

Please help in reviewing the patch.

[majnemer]

lib/Transforms/InstCombine/InstCombineCompares.cpp

2445 ↗

(On Diff #9687)

What about the ICmpInst::ICMP_NE case? We should be able to handle this case just as well.

Can we optimize any of the other predicates?

2451 ↗

(On Diff #9687)

If you always transform to true or false, you should probably move this to InstSimplify.

[suyog]

Hi David,

Thanks for your valuable comment.
As per your suggestions, i have now moved this code to InstSimplify. Also added code for ICMP_NE + test cases for both icmp instructions.

I will try to come up with logic for other icmp instructions in subsequent patches. I have for now added a TODO item for it.

Please help in reviewing the updated patch if it looks good to you.

[suyog]

Gentle Ping !!

[suyog]

Hi David, Duncan, all,

As per Duncan's suggestion, i have generalized this case, where now i am comparing the KnownBits of LHS and RHS.
If the KnownBits differ, then icmp eq always return false while icmp ne always returns true.

If a bit is known to be zero for A and known to be one for B then A and B cannot be equal.
Likewise, if a bit if known to be one for A and known to be zero for B then A != B.

Thus, if A_Known_Zero & B_Known_One != 0 then A != B. Same if A_Known_One & B_Known_Zero != 0.

I was getting one regression for "test/Transforms/InstCombine/align-2d-gep.ll" with my patch.
I have slightly modified this test case.

Earlier we were comparing a loop variable with 557 for exit condition. The loop variable was initialized to 0 and was being increased by 2.
Before my patch, there was no way to determine if " icmp eq i, 557" will be true or false.
However, now we have that logic, it was always evaluating to false, which made the loop exit condition false, making the inner loop as infinite.
I am now comparing with 556 instead of 557, which doesn't omit the exit condition. There is no regression now.

Please help in reviewing the patch.

Thanks!

[baldrick]

Hi Suyog,

+ If the KnownBits of LHS and RHS at same bit position differ,
+ LHS and RHS are not equal.

I think this comment is misleading. If KnownBitsLHS != KnownBitsRHS it doesn't
mean that LHS != RHS, but the comment seems to be saying that.

+ if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) {
+ uint32_t BitWidth = CI->getBitWidth();
+ APInt LHSKnownZero(BitWidth, 0, 1);

Why not just: APInt LHSKnownZero(BitWidth);

+ APInt LHSKnownOne(BitWidth, 0, 1);

Likewise here and below.

+ computeKnownBits(LHS, LHSKnownZero, LHSKnownOne);
+ APInt RHSKnownZero(BitWidth, 0, 1);
+ APInt RHSKnownOne(BitWidth, 0, 1);
+ computeKnownBits(RHS, RHSKnownZero, RHSKnownOne);
+ switch (Pred) {
+ // TODO: Handle for other icmp instructions.
+ default:
+ break;
+ case ICmpInst::ICMP_EQ: {
+ if (((LHSKnownOne & RHSKnownZero) != 0) ||
+ ((LHSKnownZero & RHSKnownOne) != 0))
+ return ConstantInt::getFalse(CI->getContext());
+ break;
+ }
+ case ICmpInst::ICMP_NE:
+ if (((LHSKnownOne & RHSKnownZero) != 0) ||
+ ((LHSKnownZero & RHSKnownOne) != 0))
+ return ConstantInt::getTrue(CI->getContext());
+ break;

These two cases could be unified:

case ICmpInst::ICMP_EQ:
case ICmpInst::ICMP_NE:
  if (((LHSKnownOne & RHSKnownZero) != 0) ||
      ((LHSKnownZero & RHSKnownOne) != 0))
    return Pred == ICmpInst::ICMP_EQ ?
      ConstantInt::getFalse(CI->getContext()) :
      ConstantInt::getTrue(CI->getContext());

Best wishes, Duncan.

[suyog]

This comment was removed by suyog.

[suyog]

Hi Duncan, David, all,

Thanks for the review.

I modified the comment as per Duncan's suggestion.
Please suggest if the comment is OK or suggest an appropriate comment.

Also re-factored code as per suggestion. Trimmed test cases to eliminate unnecessary code.

Please help in reviewing the patch. Suggestions/Comments/Modification are most awaited.

Thanks !

[suyog]

Gentle Ping !!

[suyog]

Gentle Ping !!

[nicholas]

computeKnownBits is really expensive. Please check ICmpInst::isEquality(Pred) before the rest of this logic. LGTM with that change.

[suyog]

Hi Nick,

updated patch as per your review.

1. Included check ICmpInst::isEquality(Pred) before the rest.
2. Moved the code lower down as per suggestion.

I think its fine to commit the change to test/Transforms/InstCombine/align-2d-gep.ll as
part of this patch only.

I dont have commit access, so please if you could commit it for me.
Meanwhile I will add test cases to the other two refactoring patches and get
back shortly.

Thanks,
Suyog

[suyog]

Committed as r211251 by Nick.

Thanks!

lib/Analysis/InstructionSimplify.cpp

if (isa<SExtInst>(LHS)) {
                 return V;
             break;
           }
         }
       }
     }
   }
 
+  // If a bit is known to be zero for A and known to be one for B,
+  // then A and B cannot be equal.
+  if (ICmpInst::isEquality(Pred)) {
+    if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) {
+      uint32_t BitWidth = CI->getBitWidth();
+      APInt LHSKnownZero(BitWidth, 0);
+      APInt LHSKnownOne(BitWidth, 0);
+      computeKnownBits(LHS, LHSKnownZero, LHSKnownOne);
+      APInt RHSKnownZero(BitWidth, 0);
+      APInt RHSKnownOne(BitWidth, 0);
+      computeKnownBits(RHS, RHSKnownZero, RHSKnownOne);
+      if (((LHSKnownOne & RHSKnownZero) != 0) ||
+          ((LHSKnownZero & RHSKnownOne) != 0))
+        return (Pred == ICmpInst::ICMP_EQ)
+                   ? ConstantInt::getFalse(CI->getContext())
+                   : ConstantInt::getTrue(CI->getContext());
+    }
+  }
+
   // Special logic for binary operators.
   BinaryOperator *LBO = dyn_cast<BinaryOperator>(LHS);
   BinaryOperator *RBO = dyn_cast<BinaryOperator>(RHS);
   if (MaxRecurse && (LBO || RBO)) {
     // Analyze the case when either LHS or RHS is an add instruction.
     Value *A = nullptr, *B = nullptr, *C = nullptr, *D = nullptr;
     // LHS = A + B (or A and B are null); RHS = C + D (or C and D are null).
     bool NoLHSWrapProblem = false, NoRHSWrapProblem = false;

test/Transforms/InstCombine/align-2d-gep.ll

bb1:
   %q = bitcast double* %t4 to <2 x double>*
   store <2 x double><double 0.0, double 0.0>, <2 x double>* %q, align 8
 
   %s4 = getelementptr [1001 x [20001 x double]]* @Awkward, i64 0, i64 %i, i64 %j
   %r = bitcast double* %s4 to <2 x double>*
   store <2 x double><double 0.0, double 0.0>, <2 x double>* %r, align 8
 
   %indvar.next = add i64 %j, 2
-  %exitcond = icmp eq i64 %indvar.next, 557
+  %exitcond = icmp eq i64 %indvar.next, 556
   br i1 %exitcond, label %bb11, label %bb1
 
 bb11:
   %indvar.next26 = add i64 %i, 1
   %exitcond27 = icmp eq i64 %indvar.next26, 991
   br i1 %exitcond27, label %return.split, label %bb7.outer
 
 return.split:
   ret void
 }

test/Transforms/InstSimplify/compare.ll

 define i1 @returns_nonnull() {
   %call = call nonnull i32* @returns_nonnull_helper()
   %cmp = icmp eq i32* %call, null
   ret i1 %cmp
 ; CHECK-LABEL: @returns_nonnull
 ; CHECK: ret i1 false
 }
 
+; If a bit is known to be zero for A and known to be one for B,
+; then A and B cannot be equal.
+define i1 @icmp_eq_const(i32 %a) nounwind {
+  %b = mul nsw i32 %a, -2
+  %c = icmp eq i32 %b, 1
+  ret i1 %c
+
+; CHECK-LABEL: @icmp_eq_const
+; CHECK-NEXT: ret i1 false 
+}
+
+define i1 @icmp_ne_const(i32 %a) nounwind {
+  %b = mul nsw i32 %a, -2
+  %c = icmp ne i32 %b, 1
+  ret i1 %c
+
+; CHECK-LABEL: @icmp_ne_const
+; CHECK-NEXT: ret i1 true
+}