[InstCombine] Move an optimization from foldICmpAndConstConst to foldICmpUsingKnownBits

[craig.topper]

Summary

All this optimization cares about is knowing how many low bits of LHS is known to be zero and whether that means that the result is 0 or greater than the RHS constant. It doesn't matter where the zeros in the low bits came from. So we don't need to specifically look for an AND. Instead we can use known bits.

[craig.topper]

Forgot to add full context

[spatel]

LGTM.

Given that we're already calling computeKnownBits here, this seems ok. Is there a real motivating benchmark though? If so, I think you want to add a reduction of that, so we're less likely to lose it if/when there's a rewrite of instcombine.

Also, I commented on D38206 before I saw this patch, so this patch may make that comment moot. Although similar to this case, another test to check a less restricted version would be good if you've seen it in the real world.

[craig.topper]

This didn't come from any real benchmark. The one use restriction on foldICmpAndShift was something I saw in real code. Though it was with a ashr, so I still have another patch to come. Then while I was reviewing the nearby code I saw the missing inverse case on this transform which I fixed last week in D38065. But then I started thinking about it more and thought maybe we should handle any kind of zeros and not just zeros created by ands.

lib/Transforms/InstCombine/InstCombineCompares.cpp

if (match(Or, m_Or(m_Value(LShr), m_Value(A))) &&
       if (NewOr) {
         Value *NewAnd = Builder.CreateAnd(A, NewOr, And->getName());
         Cmp.setOperand(0, NewAnd);
         return &Cmp;
       }
     }
   }
 
-  // (X & C2) > C1 --> (X & C2) != 0, if any bit set in (X & C2) will produce a
- // result greater than C1. Also handle (X & C2) < C1 --> (X & C2) == 0.
-  if (!C2->isNullValue()) {
-    unsigned NumTZ = C2->countTrailingZeros();
-    if (Cmp.getPredicate() == ICmpInst::ICMP_UGT &&
-        NumTZ >= C1->getActiveBits()) {
-      Constant *Zero = Constant::getNullValue(And->getType());
-      return new ICmpInst(ICmpInst::ICMP_NE, And, Zero);
-    }
-    if (Cmp.getPredicate() == ICmpInst::ICMP_ULT &&
-        NumTZ >= C1->ceilLogBase2()) {
-      Constant *Zero = Constant::getNullValue(And->getType());
-      return new ICmpInst(ICmpInst::ICMP_EQ, And, Zero);
-    }
-  }
-
   return nullptr;
 }
 
 /// Fold icmp (and X, Y), C.
 Instruction *InstCombiner::foldICmpAndConstant(ICmpInst &Cmp,
                                                BinaryOperator *And,
                                                const APInt *C) {
   if (Instruction *I = foldICmpAndConstConst(Cmp, And, C))
case ICmpInst::ICMP_ULT: {
     if (Op1Min == Op0Max) // A <u B -> A != B if max(A) == min(B)
       return new ICmpInst(ICmpInst::ICMP_NE, Op0, Op1);
 
     if (Op1Min == Op1Max) {
       // A <u C -> A == C-1 if min(A)+1 == C
       if (Op1Min == Op0Min + 1)
         return new ICmpInst(ICmpInst::ICMP_EQ, Op0,
                             ConstantInt::get(Op0->getType(), Op1Min - 1));
+      // X <u C --> X == 0, if the number of zero bits in the bottom of X
+      // exceeds the log2 of C.
+      if (Op0Known.countMinTrailingZeros() >= Op1Min.ceilLogBase2())
+        return new ICmpInst(ICmpInst::ICMP_EQ, Op0,
+                            Constant::getNullValue(Op1->getType()));
     }
     break;
   }
   case ICmpInst::ICMP_UGT: {
     if (Op0Min.ugt(Op1Max)) // A >u B -> true if min(A) > max(B)
       return replaceInstUsesWith(I, ConstantInt::getTrue(I.getType()));
     if (Op0Max.ule(Op1Min)) // A >u B -> false if max(A) <= max(B)
       return replaceInstUsesWith(I, ConstantInt::getFalse(I.getType()));
     if (Op1Max == Op0Min) // A >u B -> A != B if min(A) == max(B)
       return new ICmpInst(ICmpInst::ICMP_NE, Op0, Op1);
 
     if (Op1Min == Op1Max) {
       // A >u C -> A == C+1 if max(a)-1 == C
       if (Op1Min == Op0Max - 1)
         return new ICmpInst(ICmpInst::ICMP_EQ, Op0,
                             ConstantInt::get(Op1->getType(), Op1Min + 1));
+      // X >u C --> X != 0, if the number of zero bits in the bottom of X
+      // exceeds the log2 of C.
+      if (Op0Known.countMinTrailingZeros() >= Op1Min.getActiveBits())
+        return new ICmpInst(ICmpInst::ICMP_NE, Op0,
+                            Constant::getNullValue(Op1->getType()));
     }
     break;
   }
   case ICmpInst::ICMP_SLT:
     if (Op0Max.slt(Op1Min)) // A <s B -> true if max(A) < min(C)
       return replaceInstUsesWith(I, ConstantInt::getTrue(I.getType()));
     if (Op0Min.sge(Op1Max)) // A <s B -> false if min(A) >= max(C)
       return replaceInstUsesWith(I, ConstantInt::getFalse(I.getType()));