[InstCombineCompares] Added shl optimization for the instruction - icmp eq/ne (shl Const2, A), Const1

[ankur29.garg]

Summary

Hi,
The following patch implements the optimization for the instructions of the type:
icmp eq/ne (shl Const2, A), Const1

Such instructions can be converted to:
icmp eq/ne A, (TrailingZeros(Const1) - TrailingZeros(Const2))

This handles only the equality operators for now. Other operators need to be handled.

This patch is related to the http://reviews.llvm.org/D4068. The D4068 implements this optimization for ashr/lshr operators. The following patch implements the optimization for shl operator.

Please help in reviewing it.

Thanks.
Ankur

[ankur29.garg]

• 201410181249427_0EB565ZP.gif12 KBDownload

[ankur29.garg]

---

llvm-commits mailing list
[e-mail]
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

• 201410181249427_0EB565ZP.gif12 KBDownload

[majnemer]

All of the test cases you have here that return a constant are already handled by InstSimplify (which is run as part of InstCombine) so you aren't really testing them. Please do not complicate the code by handling impossible cases.

lib/Transforms/InstCombine/InstCombineCompares.cpp

1149

This should be unsigned. You should also save the result so it can be reused later on. This isn't always efficient to calculate.

1152

Run clang format here.

test/Transforms/InstCombine/icmp.ll

1424–1428

This is already handled by InstSimplify.

1432–1436

This is already handled by InstSimplify.

1449–1453

This is already handled by InstSimplify.

1466–1470

This is already handled by InstSimplify.

[ankur29.garg]

Hi David,
Thanks for the review.
I have made the changes as per your comments.

I have removed all those test cases, which were not being tested with this code. Also, I have removed the code for handling such cases and instead inserted an assertion.

Please review the updated revision.

Thanks.

[majnemer]

lib/Transforms/InstCombine/InstCombineCompares.cpp

1145

This should be named Zeros. Also, please reuse this for the calculation on line 1158.

1147–1150

I'd remove the braces around this.

1153–1164

These cases can be merged:

if (Shift >= 0 && AP2.shl(Shift) == AP1)
  return getICmp(I.ICMP_EQ, A, ConstantInt::get(A->getType(), Shift));

[ankur29.garg]

Hi David,
I have made the changes as per your comments.

Please review the updated revision.
Thanks.

[majnemer]

I sat down and proved it with Alive:

Name: 1
Pre: C2 != 0 && C1 == 0 && countTrailingZeros(C2) != 0
 %shl = shl i8 C2, %a
 %cmp = icmp eq i8 %shl, C1
=>
 %cmp = icmp uge i8 %a, width(%a) - countTrailingZeros(C2)

Name: 2
Pre: C2 != 0 && C1 == C2
 %shl = shl i8 C2, %a
 %cmp = icmp eq i8 %shl, C1
=>
 %cmp = icmp eq i8 %a, 0

Name: 3
Pre: C2 != 0 && C1 != C2 && C1 != 0 && countTrailingZeros(C1) > countTrailingZeros(C2) && (C2 << (countTrailingZeros(C1) - countTrailingZeros(C2)) == C1)
 %shl = shl i8 C2, %a
 %cmp = icmp eq i8 %shl, C1
=>
 %cmp = icmp eq i8 %a, countTrailingZeros(C1) - countTrailingZeros(C2)

Name: 4
Pre: C2 != 0 && C1 != C2 && C1 != 0 && !(countTrailingZeros(C1) > countTrailingZeros(C2) && (C2 << (countTrailingZeros(C1) - countTrailingZeros(C2)) == C1))
 %shl = shl i8 C2, %a
 %cmp = icmp eq i8 %shl, C1
=>
 %cmp = i1 false

LGTM is conditional on addressing the variable name change.

lib/Transforms/InstCombine/InstCombineCompares.cpp

1145

Can we name this something like AP2TrailingZeros?

[ankur29.garg]

Hi David,
Thanks for reviewing the patch.

I have renamed the variable 'Zeros' to 'AP2TrailingZeros' as per your comments.

Also, Can you please commit this patch, as I don't have commit access.

Thanks.

[majnemer]

Commited as rL220162.

lib/Transforms/InstCombine/InstCombine.h

                               ConstantInt *DivRHS);
   Instruction *FoldICmpCstShrCst(ICmpInst &I, Value *Op, Value *A,
                                  ConstantInt *CI1, ConstantInt *CI2);
+  Instruction *FoldICmpCstShlCst(ICmpInst &I, Value *Op, Value *A,
+                                 ConstantInt *CI1, ConstantInt *CI2);
   Instruction *FoldICmpAddOpCst(Instruction &ICI, Value *X, ConstantInt *CI,
                                 ICmpInst::Predicate Pred);
   Instruction *FoldGEPICmp(GEPOperator *GEPLHS, Value *RHS,

lib/Transforms/InstCombine/InstCombineCompares.cpp

   return getConstant(false);
 }
 
+/// FoldICmpCstShlCst - Handle "(icmp eq/ne (shl const2, A), const1)" ->
+/// (icmp eq/ne A, TrailingZeros(const1) - TrailingZeros(const2)).
+Instruction *InstCombiner::FoldICmpCstShlCst(ICmpInst &I, Value *Op, Value *A,
+                                             ConstantInt *CI1,
+                                             ConstantInt *CI2) {
+  assert(I.isEquality() && "Cannot fold icmp gt/lt");
+
+  auto getConstant = [&I, this](bool IsTrue) {
+    if (I.getPredicate() == I.ICMP_NE)
+      IsTrue = !IsTrue;
+    return ReplaceInstUsesWith(I, ConstantInt::get(I.getType(), IsTrue));
+  };
+
+  auto getICmp = [&I](CmpInst::Predicate Pred, Value *LHS, Value *RHS) {
+    if (I.getPredicate() == I.ICMP_NE)
+      Pred = CmpInst::getInversePredicate(Pred);
+    return new ICmpInst(Pred, LHS, RHS);
+  };
+
+  APInt AP1 = CI1->getValue();
+  APInt AP2 = CI2->getValue();
+
+  assert(AP2 != 0 && "Handled in InstSimplify");
+
+  unsigned AP2TrailingZeros = AP2.countTrailingZeros();
+
+  if (!AP1 && AP2TrailingZeros != 0)
+    return getICmp(I.ICMP_UGE, A,
+                   ConstantInt::get(A->getType(), AP2.getBitWidth() - AP2TrailingZeros));
+
+  if (AP1 == AP2)
+    return getICmp(I.ICMP_EQ, A, ConstantInt::getNullValue(A->getType()));
+
+  // Get the distance between the lowest bits that are set.
+  int Shift = AP1.countTrailingZeros() - AP2TrailingZeros;
+
+  if (Shift > 0 && AP2.shl(Shift) == AP1)
+    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,

               cast<ConstantInt>(ConstantExpr::getShl(AndCst, ShAmt));
             ConstantInt *ShiftedRHSCst =
               cast<ConstantInt>(ConstantExpr::getShl(RHS, ShAmt));
            
             if (!ShiftedAndCst->isNegative() && !ShiftedRHSCst->isNegative())
               CanFold = true;
           }

                           Builder->getInt(CI->getValue()-1));
     }
 
-    // (icmp eq/ne (ashr/lshr const2, A), const1)
     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)))) {
+        // (icmp eq/ne (ashr/lshr const2, A), const1)
         return FoldICmpCstShrCst(I, Op0, A, CI, CI2);
       }
+      else if (match(Op0, m_Shl(m_ConstantInt(CI2), m_Value(A)))) {
+        // (icmp eq/ne (shl const2, A), const1)
+        return FoldICmpCstShlCst(I, Op0, A, CI, CI2);
+      }
     }
 
     // If this comparison is a normal comparison, it demands all

test/Transforms/InstCombine/icmp.ll

   %ret = icmp ne i32 %and, 0
   ret i1 %ret
 }
+
+; CHECK-LABEL: @shl_ap1_zero_ap2_non_zero_2
+; CHECK-NEXT: %cmp = icmp ugt i32 %a, 29
+; CHECK-NEXT: ret i1 %cmp
+define i1 @shl_ap1_zero_ap2_non_zero_2(i32 %a) {
+ %shl = shl i32 4, %a
+ %cmp = icmp eq i32 %shl, 0
+ ret i1 %cmp
+}
+
+; CHECK-LABEL: @shl_ap1_zero_ap2_non_zero_4
+; CHECK-NEXT: %cmp = icmp ugt i32 %a, 30
+; CHECK-NEXT: ret i1 %cmp
+define i1 @shl_ap1_zero_ap2_non_zero_4(i32 %a) {
+ %shl = shl i32 -2, %a
+ %cmp = icmp eq i32 %shl, 0
+ ret i1 %cmp
+}
+
+; CHECK-LABEL: @shl_ap1_non_zero_ap2_non_zero_both_positive
+; CHECK-NEXT: %cmp = icmp eq i32 %a, 0
+; CHECK-NEXT: ret i1 %cmp
+define i1 @shl_ap1_non_zero_ap2_non_zero_both_positive(i32 %a) {
+ %shl = shl i32 50, %a
+ %cmp = icmp eq i32 %shl, 50
+ ret i1 %cmp
+}
+
+; CHECK-LABEL: @shl_ap1_non_zero_ap2_non_zero_both_negative
+; CHECK-NEXT: %cmp = icmp eq i32 %a, 0
+; CHECK-NEXT: ret i1 %cmp
+define i1 @shl_ap1_non_zero_ap2_non_zero_both_negative(i32 %a) {
+ %shl = shl i32 -50, %a
+ %cmp = icmp eq i32 %shl, -50
+ ret i1 %cmp
+}
+
+; CHECK-LABEL: @shl_ap1_non_zero_ap2_non_zero_ap1_1
+; CHECK-NEXT: ret i1 false
+define i1 @shl_ap1_non_zero_ap2_non_zero_ap1_1(i32 %a) {
+ %shl = shl i32 50, %a
+ %cmp = icmp eq i32 %shl, 25
+ ret i1 %cmp
+}
+
+; CHECK-LABEL: @shl_ap1_non_zero_ap2_non_zero_ap1_2
+; CHECK-NEXT: %cmp = icmp eq i32 %a, 1
+; CHECK-NEXT: ret i1 %cmp
+define i1 @shl_ap1_non_zero_ap2_non_zero_ap1_2(i32 %a) {
+ %shl = shl i32 25, %a
+ %cmp = icmp eq i32 %shl, 50
+ ret i1 %cmp
+}
+
+; CHECK-LABEL: @shl_ap1_non_zero_ap2_non_zero_ap1_3
+; CHECK-NEXT: ret i1 false
+define i1 @shl_ap1_non_zero_ap2_non_zero_ap1_3(i32 %a) {
+ %shl = shl i32 26, %a
+ %cmp = icmp eq i32 %shl, 50
+ ret i1 %cmp
+}