[LVI] Handle `x & 0xfff0 == 0x1230` comparison

[antoniofrighetto]

Summary

LazyValueInfo now handles the comparison of a value when masked in a certain way with a constant. For example, for a 16-bit integer, we might have x & 0xfff0 == 0x1230. This is a typical situation produced by InstCombine to efficiently check if x is between [0x1230, 0x1240).

[nikic]

Tests?

llvm/lib/Analysis/LazyValueInfo.cpp

1137

Please integrate your code here. It's not super obvious to me in what way it extends the existing handling.

[antoniofrighetto]

Following thorough investigation, it turns out that the introduced interval range refinement has already been covered in db9d00c by @nikic. Closing this, sorry for the incident.

llvm/lib/Analysis/LazyValueInfo.cpp

static ValueLatticeElement getValueFromICmpCondition(Value *Val, ICmpInst *ICI,
                                                      bool isTrueDest) {
   Value *LHS = ICI->getOperand(0);
   Value *RHS = ICI->getOperand(1);
 
   // Get the predicate that must hold along the considered edge.
   CmpInst::Predicate EdgePred =
       isTrueDest ? ICI->getPredicate() : ICI->getInversePredicate();
 
-  if (isa<Constant>(RHS)) {
-    if (ICI->isEquality() && LHS == Val) {
+  if (isa<Constant>(RHS) && ICI->isEquality()) {
+    if (LHS == Val) {
+      // We know that V has the RHS constant if the edge predicate is equality.
       if (EdgePred == ICmpInst::ICMP_EQ)
         return ValueLatticeElement::get(cast<Constant>(RHS));
       else if (!isa<UndefValue>(RHS))
         return ValueLatticeElement::getNot(cast<Constant>(RHS));
     }
+
+    if (ConstantInt *CIRHS = dyn_cast<ConstantInt>(RHS)) {
+      ConstantInt *Mask;
+      if (match(LHS, m_And(m_Specific(Val), m_ConstantInt(Mask)))) {
+        const APInt &FixedBits = CIRHS->getValue();
+        APInt MaskValue = Mask->getValue();
+        MaskValue.flipAllBits();
+
+        if (MaskValue.isMask()) {
+          using VLE = ValueLatticeElement;
+          if ((MaskValue & FixedBits) == 0) {
+            if (EdgePred == ICmpInst::ICMP_EQ)
+              return VLE::getRange({FixedBits, FixedBits + MaskValue + 1});
+            else
+              return VLE::getRange({FixedBits + MaskValue + 1, FixedBits});
+          } else {
+            if (EdgePred == ICmpInst::ICMP_EQ)
+              return VLE();
+            else
+              return VLE::getOverdefined();
+          }
+        }
+      }
+    }
   }
 
   Type *Ty = Val->getType();
   if (!Ty->isIntegerTy())
     return ValueLatticeElement::getOverdefined();
 
   unsigned BitWidth = Ty->getScalarSizeInBits();
   APInt Offset(BitWidth, 0);
   if (matchICmpOperand(Offset, LHS, Val, EdgePred))
     return getValueFromSimpleICmpCondition(EdgePred, RHS, Offset);
 
   CmpInst::Predicate SwappedPred = CmpInst::getSwappedPredicate(EdgePred);
   if (matchICmpOperand(Offset, RHS, Val, SwappedPred))
     return getValueFromSimpleICmpCondition(SwappedPred, LHS, Offset);
 
   const APInt *Mask, *C;
   if (match(LHS, m_And(m_Specific(Val), m_APInt(Mask))) &&
       match(RHS, m_APInt(C))) {
     // If (Val & Mask) == C then all the masked bits are known and we can
     // compute a value range based on that.
     if (EdgePred == ICmpInst::ICMP_EQ) {
       KnownBits Known;
       Known.Zero = ~*C & *Mask;
       Known.One = *C & *Mask;
       return ValueLatticeElement::getRange(
           ConstantRange::fromKnownBits(Known, /*IsSigned*/ false));