[PatternMatch][LVI] Handle select-form and/or in LVI

[nikic]

Summary

Following the discussion in D93065, this adds m_LogicalAnd() and m_LogicalOr() matchers, that match A && B and A || B logical operations, either as bitwise operations or select expressions. As an example usage, LVI is adapted to use these matchers for its condition reasoning.

The plan here is to switch other parts of LLVM that reason about and/or of conditions to also support the select forms, and then merge D93065 (or some close variant) to disable the incorrect select -> and/or transform.

[aqjune]

LGTM

Limited to this patch, using LogicalAnd/LogicalOr is sound, because if the branch is taken/not taken, 'select x, y, false' is equivalent to 'and x, y' and also 'select x, true, y' is to 'or x, y'.

llvm/include/llvm/IR/PatternMatch.h

template <typename ITy> bool match(ITy *V) {
     return false;
   }
 };
 
 inline VScaleVal_match m_VScale(const DataLayout &DL) {
   return VScaleVal_match(DL);
 }
 
+template <typename LHS, typename RHS, unsigned Opcode>
+struct LogicalOp_match {
+  LHS L;
+  RHS R;
+
+  LogicalOp_match(const LHS &L, const RHS &R) : L(L), R(R) {}
+
+  template <typename T> bool match(T *V) {
+    if (auto *I = dyn_cast<Instruction>(V)) {
+      if (!I->getType()->isIntOrIntVectorTy(1))
+        return false;
+
+      if (I->getOpcode() == Opcode && L.match(I->getOperand(0)) &&
+          R.match(I->getOperand(1)))
+        return true;
+
+      if (auto *SI = dyn_cast<SelectInst>(I)) {
+        if (Opcode == Instruction::And) {
+          if (const auto *C = dyn_cast<Constant>(SI->getFalseValue()))
+            if (C->isNullValue() && L.match(SI->getCondition()) &&
+                R.match(SI->getTrueValue()))
+              return true;
+        } else {
+          assert(Opcode == Instruction::Or);
+          if (const auto *C = dyn_cast<Constant>(SI->getTrueValue()))
+            if (C->isOneValue() && L.match(SI->getCondition()) &&
+                R.match(SI->getFalseValue()))
+              return true;
+        }
+      }
+    }
+
+    return false;
+  }
+};
+
+/// Matches L && R either in the form of L & R or L ? R : false.
+/// Note that the latter form is poison-blocking.
+template <typename LHS, typename RHS>
+inline LogicalOp_match<LHS, RHS, Instruction::And>
+m_LogicalAnd(const LHS &L, const RHS &R) {
+  return LogicalOp_match<LHS, RHS, Instruction::And>(L, R);
+}
+
+/// Matches L || R either in the form of L | R or L ? true : R.
+/// Note that the latter form is poison-blocking.
+template <typename LHS, typename RHS>
+inline LogicalOp_match<LHS, RHS, Instruction::Or>
+m_LogicalOr(const LHS &L, const RHS &R) {
+  return LogicalOp_match<LHS, RHS, Instruction::Or>(L, R);
+}
+
 } // end namespace PatternMatch
 } // end namespace llvm
 
 #endif // LLVM_IR_PATTERNMATCH_H

llvm/lib/Analysis/LazyValueInfo.cpp

if (auto *EVI = dyn_cast<ExtractValueInst>(Cond))
     if (auto *WO = dyn_cast<WithOverflowInst>(EVI->getAggregateOperand()))
       if (EVI->getNumIndices() == 1 && *EVI->idx_begin() == 1)
         return getValueFromOverflowCondition(Val, WO, isTrueDest);
 
   // Handle conditions in the form of (cond1 && cond2), we know that on the
   // true dest path both of the conditions hold. Similarly for conditions of
   // the form (cond1 || cond2), we know that on the false dest path neither
   // condition holds.
-  BinaryOperator *BO = dyn_cast<BinaryOperator>(Cond);
-  if (!BO || (isTrueDest && BO->getOpcode() != BinaryOperator::And) ||
-             (!isTrueDest && BO->getOpcode() != BinaryOperator::Or))
+  Value *L, *R;
+  if (isTrueDest ? !match(Cond, m_LogicalAnd(m_Value(L), m_Value(R)))
+                 : !match(Cond, m_LogicalOr(m_Value(L), m_Value(R))))
     return ValueLatticeElement::getOverdefined();
 
   // Prevent infinite recursion if Cond references itself as in this example:
   //  Cond: "%tmp4 = and i1 %tmp4, undef"
   //    BL: "%tmp4 = and i1 %tmp4, undef"
   //    BR: "i1 undef"
-  Value *BL = BO->getOperand(0);
-  Value *BR = BO->getOperand(1);
-  if (BL == Cond || BR == Cond)
+  if (L == Cond || R == Cond)
     return ValueLatticeElement::getOverdefined();
 
-  return intersect(getValueFromCondition(Val, BL, isTrueDest, Visited),
-                   getValueFromCondition(Val, BR, isTrueDest, Visited));
+  return intersect(getValueFromCondition(Val, L, isTrueDest, Visited),
+                   getValueFromCondition(Val, R, isTrueDest, Visited));
 }
 
 static ValueLatticeElement
 getValueFromCondition(Value *Val, Value *Cond, bool isTrueDest,
                       SmallDenseMap<Value*, ValueLatticeElement> &Visited) {
   auto I = Visited.find(Cond);
   if (I != Visited.end())
     return I->second;

llvm/test/Transforms/CorrelatedValuePropagation/basic.ll

 define void @select_and(i32 %a, i1* %p) {
 ; CHECK-LABEL: @select_and(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp sgt i32 [[A:%.*]], -10
 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp slt i32 [[A]], 10
 ; CHECK-NEXT:    [[AND:%.*]] = select i1 [[CMP1]], i1 [[CMP2]], i1 false
 ; CHECK-NEXT:    br i1 [[AND]], label [[GUARD:%.*]], label [[EXIT:%.*]]
 ; CHECK:       guard:
-; CHECK-NEXT:    [[C1:%.*]] = icmp sgt i32 [[A]], 20
-; CHECK-NEXT:    store i1 [[C1]], i1* [[P:%.*]], align 1
-; CHECK-NEXT:    [[C2:%.*]] = icmp slt i32 [[A]], -20
-; CHECK-NEXT:    store i1 [[C2]], i1* [[P]], align 1
+; CHECK-NEXT:    store i1 false, i1* [[P:%.*]], align 1
+; CHECK-NEXT:    store i1 false, i1* [[P]], align 1
 ; CHECK-NEXT:    br label [[EXIT]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %cmp1 = icmp sgt i32 %a, -10
   %cmp2 = icmp slt i32 %a, 10
   %and = select i1 %cmp1, i1 %cmp2, i1 false

 define void @select_or(i32 %a, i1* %p) {
 ; CHECK-LABEL: @select_or(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i32 [[A:%.*]], -10
 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp sgt i32 [[A]], 10
 ; CHECK-NEXT:    [[OR:%.*]] = select i1 [[CMP1]], i1 true, i1 [[CMP2]]
 ; CHECK-NEXT:    br i1 [[OR]], label [[EXIT:%.*]], label [[GUARD:%.*]]
 ; CHECK:       guard:
-; CHECK-NEXT:    [[C1:%.*]] = icmp sgt i32 [[A]], 20
-; CHECK-NEXT:    store i1 [[C1]], i1* [[P:%.*]], align 1
-; CHECK-NEXT:    [[C2:%.*]] = icmp slt i32 [[A]], -20
-; CHECK-NEXT:    store i1 [[C2]], i1* [[P]], align 1
+; CHECK-NEXT:    store i1 false, i1* [[P:%.*]], align 1
+; CHECK-NEXT:    store i1 false, i1* [[P]], align 1
 ; CHECK-NEXT:    br label [[EXIT]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %cmp1 = icmp slt i32 %a, -10
   %cmp2 = icmp sgt i32 %a, 10
   %or = select i1 %cmp1, i1 true, i1 %cmp2