[InstSimplify] Fold and/or using implied conditions

[nikic]

Summary

This adds two conjugated folds:

• A | B -> B if A implies B (https://alive2.llvm.org/ce/z/R6GU4j)
• A & B -> A if A implies B (https://alive2.llvm.org/ce/z/EGMqyy)

If A and B are icmps themselves, we will usually fold this through other logic already (though the tests show a couple additional cases we previously missed). However, isImpliedCond() also supports A being of the form X & Y, which allows us to handle cases like (X & Y) | B where X implies B. This addresses the regression from D125398.

Something that notably doesn't work yet is the (X | Y) & B case. This is due to an asymmetry in the isImpliedCondition() implementation that will have to be addressed separately.

[fhahn]

LGTM, thanks!

llvm/lib/Analysis/InstructionSimplify.cpp

2226

nit: might be good to have // A&B -> B where B implies A?

Not sure about the comments using A/B while the code using Op0/Op1. Might be good to keep things consistent, but A/B` seems nicer

llvm/lib/Analysis/InstructionSimplify.cpp

static Value *SimplifyAndInst(Value *Op0, Value *Op1, const SimplifyQuery &Q,
   // ((X | Y) ^ Y ) & ((X | Y) ^ X) --> 0
   BinaryOperator *Or;
   if (match(Op0, m_c_Xor(m_Value(X),
                          m_CombineAnd(m_BinOp(Or),
                                       m_c_Or(m_Deferred(X), m_Value(Y))))) &&
       match(Op1, m_c_Xor(m_Specific(Or), m_Specific(Y))))
     return Constant::getNullValue(Op0->getType());
 
+  if (Op0->getType()->isIntOrIntVectorTy(1)) {
+    // Op0&Op1 -> Op0 where Op0 implies Op1
+    if (isImpliedCondition(Op0, Op1, Q.DL).getValueOr(false))
+      return Op0;
+    // Op0&Op1 -> Op1 where Op1 implies Op0
+    if (isImpliedCondition(Op1, Op0, Q.DL).getValueOr(false))
+      return Op1;
+  }
+
   return nullptr;
 }
 
 Value *llvm::SimplifyAndInst(Value *Op0, Value *Op1, const SimplifyQuery &Q) {
   return ::SimplifyAndInst(Op0, Op1, Q, RecursionLimit);
 }
 
 static Value *simplifyOrLogic(Value *X, Value *Y) {
static Value *SimplifyOrInst(Value *Op0, Value *Op1, const SimplifyQuery &Q,
   }
 
   // If the operation is with the result of a phi instruction, check whether
   // operating on all incoming values of the phi always yields the same value.
   if (isa<PHINode>(Op0) || isa<PHINode>(Op1))
     if (Value *V = ThreadBinOpOverPHI(Instruction::Or, Op0, Op1, Q, MaxRecurse))
       return V;
 
+  if (Op0->getType()->isIntOrIntVectorTy(1)) {
+    // Op0|Op1 -> Op1 where Op0 implies Op1
+    if (isImpliedCondition(Op0, Op1, Q.DL).getValueOr(false))
+      return Op1;
+    // Op0|Op1 -> Op0 where Op1 implies Op0
+    if (isImpliedCondition(Op1, Op0, Q.DL).getValueOr(false))
+      return Op0;
+  }
+
   return nullptr;
 }
 
 Value *llvm::SimplifyOrInst(Value *Op0, Value *Op1, const SimplifyQuery &Q) {
   return ::SimplifyOrInst(Op0, Op1, Q, RecursionLimit);
 }
 
 /// Given operands for a Xor, see if we can fold the result.

llvm/test/Transforms/InstSimplify/and-icmps-same-ops.ll

;
   %cmp2 = icmp ule <2 x i8> %a, %b
   %and = and <2 x i1> %cmp1, %cmp2
   ret <2 x i1> %and
 }
 
 define i1 @ult_uge_swap(i8 %a, i8 %b) {
 ; CHECK-LABEL: @ult_uge_swap(
 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp ult i8 [[A:%.*]], [[B:%.*]]
-; CHECK-NEXT:    [[CMP2:%.*]] = icmp uge i8 [[B]], [[A]]
-; CHECK-NEXT:    [[AND:%.*]] = and i1 [[CMP1]], [[CMP2]]
-; CHECK-NEXT:    ret i1 [[AND]]
+; CHECK-NEXT:    ret i1 [[CMP1]]
 ;
   %cmp1 = icmp ult i8 %a, %b
   %cmp2 = icmp uge i8 %b, %a
   %and = and i1 %cmp1, %cmp2
   ret i1 %and
 }
 
 define i1 @ult_ult_swap(i8 %a, i8 %b) {

llvm/test/Transforms/InstSimplify/and-or-implied-cond.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -instsimplify < %s | FileCheck %s
 
 define i1 @or_implied(i8 %x, i1 %c) {
 ; CHECK-LABEL: @or_implied(
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[X:%.*]], 0
-; CHECK-NEXT:    [[CMP2:%.*]] = icmp ne i8 [[X]], 1
-; CHECK-NEXT:    [[AND:%.*]] = and i1 [[CMP]], [[C:%.*]]
-; CHECK-NEXT:    [[OR:%.*]] = or i1 [[AND]], [[CMP2]]
-; CHECK-NEXT:    ret i1 [[OR]]
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp ne i8 [[X:%.*]], 1
+; CHECK-NEXT:    ret i1 [[CMP2]]
 ;
   %cmp = icmp eq i8 %x, 0
   %cmp2 = icmp ne i8 %x, 1
   %and = and i1 %cmp, %c
   %or = or i1 %and, %cmp2
   ret i1 %or
 }
 
 define i1 @or_implied_comm1(i8 %x, i1 %c) {
 ; CHECK-LABEL: @or_implied_comm1(
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[X:%.*]], 0
-; CHECK-NEXT:    [[CMP2:%.*]] = icmp ne i8 [[X]], 1
-; CHECK-NEXT:    [[AND:%.*]] = and i1 [[CMP]], [[C:%.*]]
-; CHECK-NEXT:    [[OR:%.*]] = or i1 [[CMP2]], [[AND]]
-; CHECK-NEXT:    ret i1 [[OR]]
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp ne i8 [[X:%.*]], 1
+; CHECK-NEXT:    ret i1 [[CMP2]]
 ;
   %cmp = icmp eq i8 %x, 0
   %cmp2 = icmp ne i8 %x, 1
   %and = and i1 %cmp, %c
   %or = or i1 %cmp2, %and
   ret i1 %or
 }
 
 define i1 @or_implied_comm2(i8 %x, i1 %c) {
 ; CHECK-LABEL: @or_implied_comm2(
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[X:%.*]], 0
-; CHECK-NEXT:    [[CMP2:%.*]] = icmp ne i8 [[X]], 1
-; CHECK-NEXT:    [[AND:%.*]] = and i1 [[C:%.*]], [[CMP]]
-; CHECK-NEXT:    [[OR:%.*]] = or i1 [[AND]], [[CMP2]]
-; CHECK-NEXT:    ret i1 [[OR]]
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp ne i8 [[X:%.*]], 1
+; CHECK-NEXT:    ret i1 [[CMP2]]
 ;
   %cmp = icmp eq i8 %x, 0
   %cmp2 = icmp ne i8 %x, 1
   %and = and i1 %c, %cmp
   %or = or i1 %and, %cmp2
   ret i1 %or
 }
 
 define i1 @or_implied_comm3(i8 %x, i1 %c) {
 ; CHECK-LABEL: @or_implied_comm3(
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[X:%.*]], 0
-; CHECK-NEXT:    [[CMP2:%.*]] = icmp ne i8 [[X]], 1
-; CHECK-NEXT:    [[AND:%.*]] = and i1 [[C:%.*]], [[CMP]]
-; CHECK-NEXT:    [[OR:%.*]] = or i1 [[CMP2]], [[AND]]
-; CHECK-NEXT:    ret i1 [[OR]]
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp ne i8 [[X:%.*]], 1
+; CHECK-NEXT:    ret i1 [[CMP2]]
 ;
   %cmp = icmp eq i8 %x, 0
   %cmp2 = icmp ne i8 %x, 1
   %and = and i1 %c, %cmp
   %or = or i1 %cmp2, %and
   ret i1 %or
 }
 

llvm/test/Transforms/InstSimplify/or-icmps-same-ops.ll

;
   %cmp1 = icmp ult <2 x i8> %a, %b
   %cmp2 = icmp ule <2 x i8> %a, %b
   %or = or <2 x i1> %cmp1, %cmp2
   ret <2 x i1> %or
 }
 
 define i1 @ult_ne_swap(i8 %a, i8 %b) {
 ; CHECK-LABEL: @ult_ne_swap(
-; CHECK-NEXT:    [[CMP1:%.*]] = icmp ult i8 [[A:%.*]], [[B:%.*]]
-; CHECK-NEXT:    [[CMP2:%.*]] = icmp ne i8 [[B]], [[A]]
-; CHECK-NEXT:    [[OR:%.*]] = or i1 [[CMP1]], [[CMP2]]
-; CHECK-NEXT:    ret i1 [[OR]]
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp ne i8 [[B:%.*]], [[A:%.*]]
+; CHECK-NEXT:    ret i1 [[CMP2]]
 ;
   %cmp1 = icmp ult i8 %a, %b
   %cmp2 = icmp ne i8 %b, %a
   %or = or i1 %cmp1, %cmp2
   ret i1 %or
 }
 
 define i1 @ult_ule_swap(i8 %a, i8 %b) {
 ; CHECK-LABEL: @ult_ule_swap(
-; CHECK-NEXT:    [[CMP1:%.*]] = icmp ult i8 [[A:%.*]], [[B:%.*]]
-; CHECK-NEXT:    [[CMP2:%.*]] = icmp uge i8 [[B]], [[A]]
-; CHECK-NEXT:    [[OR:%.*]] = or i1 [[CMP1]], [[CMP2]]
-; CHECK-NEXT:    ret i1 [[OR]]
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp uge i8 [[B:%.*]], [[A:%.*]]
+; CHECK-NEXT:    ret i1 [[CMP2]]
 ;
   %cmp1 = icmp ult i8 %a, %b
   %cmp2 = icmp uge i8 %b, %a
   %or = or i1 %cmp1, %cmp2
   ret i1 %or
 }