[LVI][CVP] Handle (x | y) < C style conditions

[nikic]

Summary

InstCombine converts conditions like (x < C) && (y < C) into (x | y) < C. This teaches LVI to recognize that in this case, it can infer either x < C or y < C along the edge.

This fixes the issue reported at https://github.com/rust-lang/rust/issues/73827.

[spatel]

llvm/lib/Analysis/LazyValueInfo.cpp

1106

These transforms only work when C is a low-bit mask or power-of-2 (depending on predicate)?
https://alive2.llvm.org/ce/z/pmF7PF

[nikic]

llvm/lib/Analysis/LazyValueInfo.cpp

1106

Ah, to be clear, this is not an equivalence, only an implication. If (x | y) < 9 we know that both x < 9 and y < 9, but if we know that x < 9 and y < 9, it does not follow that (x | y) < 9 (which is what the alive proof is showing). Here, we only care about implication in one direction.

[spatel]

llvm/lib/Analysis/LazyValueInfo.cpp

1106

Modify/add tests with arbitrary constants to make that more obvious then? I missed the relationship because we're using '7' in all cases.

[nikic]

Change tests to use magic number 42, rather than something that looks like a bit mask.

[spatel]

LGTM

llvm/lib/Analysis/LazyValueInfo.cpp

if (Value *V = SimplifyExtractValueInst(
           EVI->getModule()->getDataLayout()))
     return getBlockValue(V, BB);
 
   LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()
                     << "' - overdefined (unknown extractvalue).\n");
   return ValueLatticeElement::getOverdefined();
 }
 
-static bool matchICmpOperand(const APInt *&Offset, Value *LHS, Value *Val) {
+static bool matchICmpOperand(const APInt *&Offset, Value *LHS, Value *Val,
+                             ICmpInst::Predicate Pred) {
   if (LHS == Val)
     return true;
 
   // Handle range checking idiom produced by InstCombine. We will subtract the
   // offset from the allowed range for RHS in this case.
   if (match(LHS, m_Add(m_Specific(Val), m_APInt(Offset))))
     return true;
 
+  // If (x | y) < C, then (x < C) && (y < C).
+  if (match(LHS, m_c_Or(m_Specific(Val), m_Value())) &&
+      (Pred == ICmpInst::ICMP_ULT || Pred == ICmpInst::ICMP_ULE))
+    return true;
+
+  // If (x & y) > C, then (x > C) && (y > C).
+  if (match(LHS, m_c_And(m_Specific(Val), m_Value())) &&
+      (Pred == ICmpInst::ICMP_UGT || Pred == ICmpInst::ICMP_UGE))
+    return true;
+
   return false;
 }
 
 static ValueLatticeElement getValueFromICmpCondition(Value *Val, ICmpInst *ICI,
                                                      bool isTrueDest) {
   Value *LHS = ICI->getOperand(0);
   Value *RHS = ICI->getOperand(1);
 
if (ICI->isEquality() && LHS == Val) {
         return ValueLatticeElement::getNot(cast<Constant>(RHS));
     }
   }
 
   if (!Val->getType()->isIntegerTy())
     return ValueLatticeElement::getOverdefined();
 
   const APInt *Offset = nullptr;
-  if (!matchICmpOperand(Offset, LHS, Val)) {
+  if (!matchICmpOperand(Offset, LHS, Val, EdgePred)) {
     std::swap(LHS, RHS);
     EdgePred = CmpInst::getSwappedPredicate(EdgePred);
-    if (!matchICmpOperand(Offset, LHS, Val))
+    if (!matchICmpOperand(Offset, LHS, Val, EdgePred))
       return ValueLatticeElement::getOverdefined();
   }
 
   // Calculate the range of values that are allowed by the comparison.
   ConstantRange RHSRange(RHS->getType()->getIntegerBitWidth(),
                          /*isFullSet=*/true);
   if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS))
     RHSRange = ConstantRange(CI->getValue());

llvm/test/Transforms/CorrelatedValuePropagation/icmp.ll

 
 define void @test_icmp_or_ult(i32 %a, i32 %b) {
 ; CHECK-LABEL: @test_icmp_or_ult(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[OR:%.*]] = or i32 [[A:%.*]], [[B:%.*]]
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i32 [[OR]], 42
 ; CHECK-NEXT:    br i1 [[CMP]], label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]]
 ; CHECK:       if.true:
-; CHECK-NEXT:    [[CMP2:%.*]] = icmp ult i32 [[A]], 42
-; CHECK-NEXT:    call void @check1(i1 [[CMP2]])
-; CHECK-NEXT:    [[CMP3:%.*]] = icmp ult i32 [[B]], 42
-; CHECK-NEXT:    call void @check1(i1 [[CMP3]])
+; CHECK-NEXT:    call void @check1(i1 true)
+; CHECK-NEXT:    call void @check1(i1 true)
 ; CHECK-NEXT:    ret void
 ; CHECK:       if.false:
 ; CHECK-NEXT:    [[CMP4:%.*]] = icmp uge i32 [[A]], 42
 ; CHECK-NEXT:    call void @check1(i1 [[CMP4]])
 ; CHECK-NEXT:    [[CMP5:%.*]] = icmp uge i32 [[B]], 42
 ; CHECK-NEXT:    call void @check1(i1 [[CMP5]])
 ; CHECK-NEXT:    ret void
 ;

 
 define void @test_icmp_or_ule(i32 %a, i32 %b) {
 ; CHECK-LABEL: @test_icmp_or_ule(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[OR:%.*]] = or i32 [[A:%.*]], [[B:%.*]]
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ule i32 [[OR]], 42
 ; CHECK-NEXT:    br i1 [[CMP]], label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]]
 ; CHECK:       if.true:
-; CHECK-NEXT:    [[CMP2:%.*]] = icmp ule i32 [[A]], 42
-; CHECK-NEXT:    call void @check1(i1 [[CMP2]])
-; CHECK-NEXT:    [[CMP3:%.*]] = icmp ule i32 [[B]], 42
-; CHECK-NEXT:    call void @check1(i1 [[CMP3]])
+; CHECK-NEXT:    call void @check1(i1 true)
+; CHECK-NEXT:    call void @check1(i1 true)
 ; CHECK-NEXT:    ret void
 ; CHECK:       if.false:
 ; CHECK-NEXT:    [[CMP4:%.*]] = icmp ugt i32 [[A]], 42
 ; CHECK-NEXT:    call void @check1(i1 [[CMP4]])
 ; CHECK-NEXT:    [[CMP5:%.*]] = icmp ugt i32 [[B]], 42
 ; CHECK-NEXT:    call void @check1(i1 [[CMP5]])
 ; CHECK-NEXT:    ret void
 ;

 ; CHECK-NEXT:    br i1 [[CMP]], label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]]
 ; CHECK:       if.true:
 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp ugt i32 [[A]], 42
 ; CHECK-NEXT:    call void @check1(i1 [[CMP2]])
 ; CHECK-NEXT:    [[CMP3:%.*]] = icmp ugt i32 [[B]], 42
 ; CHECK-NEXT:    call void @check1(i1 [[CMP3]])
 ; CHECK-NEXT:    ret void
 ; CHECK:       if.false:
-; CHECK-NEXT:    [[CMP4:%.*]] = icmp ule i32 [[A]], 42
-; CHECK-NEXT:    call void @check1(i1 [[CMP4]])
-; CHECK-NEXT:    [[CMP5:%.*]] = icmp ule i32 [[B]], 42
-; CHECK-NEXT:    call void @check1(i1 [[CMP5]])
+; CHECK-NEXT:    call void @check1(i1 true)
+; CHECK-NEXT:    call void @check1(i1 true)
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %or = or i32 %a, %b
   %cmp = icmp ugt i32 %or, 42
   br i1 %cmp, label %if.true, label %if.false
 
 if.true:

 ; CHECK-NEXT:    br i1 [[CMP]], label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]]
 ; CHECK:       if.true:
 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp uge i32 [[A]], 42
 ; CHECK-NEXT:    call void @check1(i1 [[CMP2]])
 ; CHECK-NEXT:    [[CMP3:%.*]] = icmp uge i32 [[B]], 42
 ; CHECK-NEXT:    call void @check1(i1 [[CMP3]])
 ; CHECK-NEXT:    ret void
 ; CHECK:       if.false:
-; CHECK-NEXT:    [[CMP4:%.*]] = icmp ult i32 [[A]], 42
-; CHECK-NEXT:    call void @check1(i1 [[CMP4]])
-; CHECK-NEXT:    [[CMP5:%.*]] = icmp ult i32 [[B]], 42
-; CHECK-NEXT:    call void @check1(i1 [[CMP5]])
+; CHECK-NEXT:    call void @check1(i1 true)
+; CHECK-NEXT:    call void @check1(i1 true)
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %or = or i32 %a, %b
   %cmp = icmp uge i32 %or, 42
   br i1 %cmp, label %if.true, label %if.false
 
 if.true:

 
 define void @test_icmp_and_ugt(i32 %a, i32 %b) {
 ; CHECK-LABEL: @test_icmp_and_ugt(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[AND:%.*]] = and i32 [[A:%.*]], [[B:%.*]]
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ugt i32 [[AND]], 42
 ; CHECK-NEXT:    br i1 [[CMP]], label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]]
 ; CHECK:       if.true:
-; CHECK-NEXT:    [[CMP2:%.*]] = icmp ugt i32 [[A]], 42
-; CHECK-NEXT:    call void @check1(i1 [[CMP2]])
-; CHECK-NEXT:    [[CMP3:%.*]] = icmp ugt i32 [[B]], 42
-; CHECK-NEXT:    call void @check1(i1 [[CMP3]])
+; CHECK-NEXT:    call void @check1(i1 true)
+; CHECK-NEXT:    call void @check1(i1 true)
 ; CHECK-NEXT:    ret void
 ; CHECK:       if.false:
 ; CHECK-NEXT:    [[CMP4:%.*]] = icmp ule i32 [[A]], 42
 ; CHECK-NEXT:    call void @check1(i1 [[CMP4]])
 ; CHECK-NEXT:    [[CMP5:%.*]] = icmp ule i32 [[B]], 42
 ; CHECK-NEXT:    call void @check1(i1 [[CMP5]])
 ; CHECK-NEXT:    ret void
 ;

 
 define void @test_icmp_and_uge(i32 %a, i32 %b) {
 ; CHECK-LABEL: @test_icmp_and_uge(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[AND:%.*]] = and i32 [[A:%.*]], [[B:%.*]]
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp uge i32 [[AND]], 42
 ; CHECK-NEXT:    br i1 [[CMP]], label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]]
 ; CHECK:       if.true:
-; CHECK-NEXT:    [[CMP2:%.*]] = icmp uge i32 [[A]], 42
-; CHECK-NEXT:    call void @check1(i1 [[CMP2]])
-; CHECK-NEXT:    [[CMP3:%.*]] = icmp uge i32 [[B]], 42
-; CHECK-NEXT:    call void @check1(i1 [[CMP3]])
+; CHECK-NEXT:    call void @check1(i1 true)
+; CHECK-NEXT:    call void @check1(i1 true)
 ; CHECK-NEXT:    ret void
 ; CHECK:       if.false:
 ; CHECK-NEXT:    [[CMP4:%.*]] = icmp ult i32 [[A]], 42
 ; CHECK-NEXT:    call void @check1(i1 [[CMP4]])
 ; CHECK-NEXT:    [[CMP5:%.*]] = icmp ult i32 [[B]], 42
 ; CHECK-NEXT:    call void @check1(i1 [[CMP5]])
 ; CHECK-NEXT:    ret void
 ;

 ; CHECK-NEXT:    br i1 [[CMP]], label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]]
 ; CHECK:       if.true:
 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp ult i32 [[A]], 42
 ; CHECK-NEXT:    call void @check1(i1 [[CMP2]])
 ; CHECK-NEXT:    [[CMP3:%.*]] = icmp ult i32 [[B]], 42
 ; CHECK-NEXT:    call void @check1(i1 [[CMP3]])
 ; CHECK-NEXT:    ret void
 ; CHECK:       if.false:
-; CHECK-NEXT:    [[CMP4:%.*]] = icmp uge i32 [[A]], 42
-; CHECK-NEXT:    call void @check1(i1 [[CMP4]])
-; CHECK-NEXT:    [[CMP5:%.*]] = icmp uge i32 [[B]], 42
-; CHECK-NEXT:    call void @check1(i1 [[CMP5]])
+; CHECK-NEXT:    call void @check1(i1 true)
+; CHECK-NEXT:    call void @check1(i1 true)
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %and = and i32 %a, %b
   %cmp = icmp ult i32 %and, 42
   br i1 %cmp, label %if.true, label %if.false
 
 if.true: