Fix for bug 26465

[twoh]

Summary

For some cases, InstCombine replaces the sequence of xor/sub instruction followed by cmp instruction into a single cmp instruction. However, this replacement may result suboptimal result especially when the xor/sub has more than one use, as discussed in bug 26465 (https://llvm.org/bugs/show_bug.cgi?id=26465). This patch make the replacement happen only when xor/sub has only one use. Below are test codes for each case that addressed by this patch. For all cases below, instcombine pass does not change the original code at all when the fix is applied.

Case 1: ((xor A, ConstB) == ConstC) -> (A == (ConstB xor ConstC))

• test case

define zeroext i1 @foo(i32 %lhs, i32 %rhs) {
  %xor = xor i32 %lhs, 5
  %cmp1 = icmp eq i32 %xor, 10
  %cmp2 = icmp eq i32 %xor, %rhs
  %sel = or i1 %cmp1, %cmp2
  ret i1 %sel
}

• Output after instcombine without fix

define zeroext i1 @foo(i32 %lhs, i32 %rhs) {
  %xor = xor i32 %lhs, 5
  %cmp1 = icmp eq i32 %lhs, 15
  %cmp2 = icmp eq i32 %xor, %rhs
  %sel = or i1 %cmp1, %cmp2
  ret i1 %sel
}

Case 2: ((xor A, B) == 0) with (A == B)

• test case

define zeroext i1 @foo(i32 %lhs, i32 %rhs) {
  %xor = xor i32 %lhs, %rhs
  %cmp1 = icmp eq i32 %xor, 0
  %cmp2 = icmp eq i32 %xor, 32
  %sel = xor i1 %cmp1, %cmp2
  ret i1 %sel
}

• Output after instcombine without fix

define zeroext i1 @foo(i32 %lhs, i32 %rhs) {
  %xor = xor i32 %lhs, %rhs
  %cmp1 = icmp eq i32 %lhs, %rhs
  %cmp2 = icmp eq i32 %xor, 32
  %sel = xor i1 %cmp1, %cmp2
  ret i1 %sel
}

Case 3: ((sub A, B) == 0) -> (A == B)

• test case

define zeroext i1 @foo(i32 %lhs, i32 %rhs) {
  %sub = sub nsw i32 %lhs, %rhs
  %cmp1 = icmp eq i32 %sub, 0
  %cmp2 = icmp eq i32 %sub, 31
  %sel = or i1 %cmp1, %cmp2
  ret i1 %sel
}

• Output after instcombine without fix

define zeroext i1 @foo(i32 %lhs, i32 %rhs) {
  %sub = sub nsw i32 %lhs, %rhs
  %cmp1 = icmp eq i32 %lhs, %rhs
  %cmp2 = icmp eq i32 %sub, 31
  %sel = or i1 %cmp1, %cmp2
  ret i1 %sel
}

[majnemer]

Please add a FileCheck test.

[twoh]

FileCheck test added.

[spatel]

We need a test case for this path too?
// Replace ((sub A, B) != C) with (B != A-C) if A & C are constants.

Doesn't affect this patch, but in case you intend to continue working near this code: this function spans ~800 lines; I think it should be broken up at this point. :)

lib/Transforms/InstCombine/InstCombineCompares.cpp

2228–2229

I think this comment should be inside the 'if' clause to match the structure of the comment within the 'else if' clause.

[twoh]

Move the comment inside the 'if' clause.

@spatel, I don't think we need a test case for "Replace ((sub A, B) != C) with (B != A-C) if A & C are constants." in this diff, because only the order of if statements is changed for that case. Totally agree on you that the function is too long. Maybe a separate diff for that?

[spatel]

In D16915#345405, @twoh wrote:

@spatel, I don't think we need a test case for "Replace ((sub A, B) != C) with (B != A-C) if A & C are constants." in this diff, because only the order of if statements is changed for that case.

Ah, yes. I missed that the check for that case already exists.

Totally agree on you that the function is too long. Maybe a separate diff for that?

Certainly - that was just a suggestion to make future changes easier.

lib/Transforms/InstCombine/InstCombineCompares.cpp

2214–2215

Sorry - I missed this comment too. Please move it lower to match the format of the other cases.

[twoh]

Move the comment.

lib/Transforms/InstCombine/InstCombineCompares.cpp

2214–2215

Not at all. I should have checked this as well.

[spatel]

It must be Friday afternoon - I forgot to write 'LGTM' after accepting the revision.

[twoh]

Hello, how can I move forward with this bug? @hfinkel @majnemer Could you please take a look?

[spatel]

It's not explicit here:
http://llvm.org/docs/DeveloperPolicy.html#code-reviews
...but I think the generally accepted behavior is that you can commit after any one reviewer has accepted the patch.

So you can wait if you'd like further review, or you can commit now.

[twoh]

@spatel. Thank you for the reply. When I tried 'arc commit --revision D16915', it is said "Revision D16915 has not been accepted. Commit this revision anyway [y/N]?" so I though I need approvals from all assigned reviewers (The revision is marked as 'Needs review' on the Phabricator as well).

BTW, http://llvm.org/docs/DeveloperPolicy.html#code-reviews says only granted contributors can make a commit. As I have not been granted, not sure if it is okay for me to commit this diff directly.

[majnemer]

Committed in rL260695

lib/Transforms/InstCombine/InstCombineCompares.cpp

if (LHSI->hasOneUse() && isa<ConstantInt>(LHSI->getOperand(1)) &&
           // are correct using an SMT solver.
           if (!ICI.isSigned())
             CanFold = true;
           else {
             ConstantInt *ShiftedAndCst =
               cast<ConstantInt>(ConstantExpr::getShl(AndCst, ShAmt));
             ConstantInt *ShiftedRHSCst =
               cast<ConstantInt>(ConstantExpr::getShl(RHS, ShAmt));
-            
             if (!ShiftedAndCst->isNegative() && !ShiftedRHSCst->isNegative())
               CanFold = true;
           }
         }
 
         if (CanFold) {
           Constant *NewCst;
           if (ShiftOpcode == Instruction::Shl)
if (BinaryOperator *BO = dyn_cast<BinaryOperator>(LHSI)) {
             return new ICmpInst(ICI.getPredicate(), NegVal, BOp1);
           if (BO->hasOneUse()) {
             Value *Neg = Builder->CreateNeg(BOp1);
             Neg->takeName(BO);
             return new ICmpInst(ICI.getPredicate(), BOp0, Neg);
           }
         }
         break;
       case Instruction::Xor:
+        if (BO->hasOneUse()) {
+          if (Constant *BOC = dyn_cast<Constant>(BO->getOperand(1))) {
             // For the xor case, we can xor two constants together, eliminating
             // the explicit xor.
-        if (Constant *BOC = dyn_cast<Constant>(BO->getOperand(1))) {
             return new ICmpInst(ICI.getPredicate(), BO->getOperand(0),
-                              ConstantExpr::getXor(RHS, BOC));
           } else if (RHSV == 0) {
             // Replace ((xor A, B) != 0) with (A != B)
             return new ICmpInst(ICI.getPredicate(), BO->getOperand(0),
-                              BO->getOperand(1));
           }
+        }
         break;
       case Instruction::Sub:
-        // Replace ((sub A, B) != C) with (B != A-C) if A & C are constants.
+        if (BO->hasOneUse()) {
           if (ConstantInt *BOp0C = dyn_cast<ConstantInt>(BO->getOperand(0))) {
-          if (BO->hasOneUse())
+            // Replace ((sub A, B) != C) with (B != A-C) if A & C are constants.
             return new ICmpInst(ICI.getPredicate(), BO->getOperand(1),
-                                ConstantExpr::getSub(BOp0C, RHS));
           } else if (RHSV == 0) {
             // Replace ((sub A, B) != 0) with (A != B)
             return new ICmpInst(ICI.getPredicate(), BO->getOperand(0),
-                              BO->getOperand(1));
           }
+        }
         break;
       case Instruction::Or:
         // If bits are being or'd in that are not present in the constant we
         // are comparing against, then the comparison could never succeed!
         if (ConstantInt *BOC = dyn_cast<ConstantInt>(BO->getOperand(1))) {
           Constant *NotCI = ConstantExpr::getNot(RHS);
           if (!ConstantExpr::getAnd(BOC, NotCI)->isNullValue())
             return replaceInstUsesWith(ICI, Builder->getInt1(isICMP_NE));
if (I.isEquality()) {
     // equality compares as integer?
   }
 
   // Check to see that the input is converted from an integer type that is small
   // enough that preserves all bits.  TODO: check here for "known" sign bits.
   // This would allow us to handle (fptosi (x >>s 62) to float) if x is i64 f.e.
   unsigned InputSize = IntTy->getScalarSizeInBits();
 
-  // Following test does NOT adjust InputSize downwards for signed inputs, 
-  // because the most negative value still requires all the mantissa bits 
+  // Following test does NOT adjust InputSize downwards for signed inputs,
+  // because the most negative value still requires all the mantissa bits
   // to distinguish it from one less than that value.
   if ((int)InputSize > MantissaWidth) {
     // Conversion would lose accuracy. Check if loss can impact comparison.
     int Exp = ilogb(RHS);
     if (Exp == APFloat::IEK_Inf) {
       int MaxExponent = ilogb(APFloat::getLargest(RHS.getSemantics()));
-      if (MaxExponent < (int)InputSize - !LHSUnsigned) 
+      if (MaxExponent < (int)InputSize - !LHSUnsigned)
         // Conversion could create infinity.
         return nullptr;
     } else {
-      // Note that if RHS is zero or NaN, then Exp is negative 
+      // Note that if RHS is zero or NaN, then Exp is negative
       // and first condition is trivially false.
-      if (MantissaWidth <= Exp && Exp <= (int)InputSize - !LHSUnsigned) 
+      if (MantissaWidth <= Exp && Exp <= (int)InputSize - !LHSUnsigned)
         // Conversion could affect comparison.
         return nullptr;
     }
   }
 
   // Otherwise, we can potentially simplify the comparison.  We know that it
   // will always come through as an integer value and we know the constant is
   // not a NAN (it would have been previously simplified).

test/Transforms/InstCombine/prevent-cmp-merge.ll

+; RUN: opt < %s -instcombine -S | FileCheck %s
+;
+; This test makes sure that InstCombine does not replace the sequence of
+; xor/sub instruction followed by cmp instruction into a single cmp instruction
+; if there is more than one use of xor/sub. 
+
+define zeroext i1 @test1(i32 %lhs, i32 %rhs) {
+; CHECK-LABEL: @test1(
+; CHECK-NEXT: %xor = xor i32 %lhs, 5
+; CHECK-NEXT: %cmp1 = icmp eq i32 %xor, 10
+
+  %xor = xor i32 %lhs, 5
+  %cmp1 = icmp eq i32 %xor, 10
+  %cmp2 = icmp eq i32 %xor, %rhs
+  %sel = or i1 %cmp1, %cmp2
+  ret i1 %sel
+}
+
+define zeroext i1 @test2(i32 %lhs, i32 %rhs) {
+; CHECK-LABEL: @test2(
+; CHECK-NEXT: %xor = xor i32 %lhs, %rhs
+; CHECK-NEXT: %cmp1 = icmp eq i32 %xor, 0
+
+  %xor = xor i32 %lhs, %rhs
+  %cmp1 = icmp eq i32 %xor, 0
+  %cmp2 = icmp eq i32 %xor, 32
+  %sel = xor i1 %cmp1, %cmp2
+  ret i1 %sel
+}
+
+define zeroext i1 @test3(i32 %lhs, i32 %rhs) {
+; CHECK-LABEL: @test3(
+; CHECK-NEXT: %sub = sub nsw i32 %lhs, %rhs
+; CHECK-NEXT: %cmp1 = icmp eq i32 %sub, 0
+
+  %sub = sub nsw i32 %lhs, %rhs
+  %cmp1 = icmp eq i32 %sub, 0
+  %cmp2 = icmp eq i32 %sub, 31
+  %sel = or i1 %cmp1, %cmp2 
+  ret i1 %sel
+}