[InstCombine] Fold select -> and/or using impliesPoison

[nikic]

Summary

We can fold a ? b : false to a & b if is_poison(b) implies that is_poison(a), at which point we're able to reuse all the usual fold on ands. In particular, this covers the very common case of icmp X, C && icmp X, C'.

This currently only has an effect if -instcombine-unsafe-select-transform=0.

[nikic]

With this patch applied, this is the impact on InstCombine after flipping the flag: https://gist.github.com/nikic/052815150762859dddaefde10f25374d We can see that there are still quite a few cases where we regress. However, many can be fixed by stronger impliesPoison handling. E.g. we're currently missing icmp X, Y && icmp X, Y and icmp (X & C), C2 && icmp (X, C'), C2'.

[aqjune]

LGTM
Yes, I see that such pattern is quite prevalent. I'll make a patch for this.

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

Instruction *InstCombinerImpl::visitSelectInst(SelectInst &SI) {
 
   if (Instruction *I = canonicalizeScalarSelectOfVecs(SI, *this))
     return I;
 
   CmpInst::Predicate Pred;
 
   if (SelType->isIntOrIntVectorTy(1) &&
       TrueVal->getType() == CondVal->getType()) {
-    if (EnableUnsafeSelectTransform && match(TrueVal, m_One())) {
+    if (match(TrueVal, m_One()) &&
+        (EnableUnsafeSelectTransform || impliesPoison(FalseVal, CondVal))) {
       // Change: A = select B, true, C --> A = or B, C
       return BinaryOperator::CreateOr(CondVal, FalseVal);
     }
-    if (EnableUnsafeSelectTransform && match(FalseVal, m_Zero())) {
+    if (match(FalseVal, m_Zero()) &&
+        (EnableUnsafeSelectTransform || impliesPoison(TrueVal, CondVal))) {
       // Change: A = select B, C, false --> A = and B, C
       return BinaryOperator::CreateAnd(CondVal, TrueVal);
     }
 
     // select a, false, b -> select !a, b, false
     if (match(TrueVal, m_Zero())) {
       Value *NotCond = Builder.CreateNot(CondVal, "not." + CondVal->getName());
       return SelectInst::Create(NotCond, FalseVal,

llvm/test/Transforms/InstCombine/select-and-or.ll

;
   ret i1 %res
 }
 
 ; Safe to convert to or due to poison implication.
 define i1 @logical_or_implies(i32 %x) {
 ; CHECK-LABEL: @logical_or_implies(
 ; CHECK-NEXT:    [[C1:%.*]] = icmp eq i32 [[X:%.*]], 0
 ; CHECK-NEXT:    [[C2:%.*]] = icmp eq i32 [[X]], 42
-; CHECK-NEXT:    [[RES:%.*]] = select i1 [[C1]], i1 true, i1 [[C2]]
+; CHECK-NEXT:    [[RES:%.*]] = or i1 [[C1]], [[C2]]
 ; CHECK-NEXT:    ret i1 [[RES]]
 ;
   %c1 = icmp eq i32 %x, 0
   %c2 = icmp eq i32 %x, 42
   %res = select i1 %c1, i1 true, i1 %c2
   ret i1 %res
 }
 
 ; Will fold after conversion to or.
 define i1 @logical_or_implies_folds(i32 %x) {
 ; CHECK-LABEL: @logical_or_implies_folds(
-; CHECK-NEXT:    [[C1:%.*]] = icmp slt i32 [[X:%.*]], 0
-; CHECK-NEXT:    [[C2:%.*]] = icmp sgt i32 [[X]], -1
-; CHECK-NEXT:    [[RES:%.*]] = select i1 [[C1]], i1 true, i1 [[C2]]
-; CHECK-NEXT:    ret i1 [[RES]]
+; CHECK-NEXT:    ret i1 true
 ;
   %c1 = icmp slt i32 %x, 0
   %c2 = icmp sge i32 %x, 0
   %res = select i1 %c1, i1 true, i1 %c2
   ret i1 %res
 }
 
 ; Safe to convert to and due to poison implication.
 define i1 @logical_and_implies(i32 %x) {
 ; CHECK-LABEL: @logical_and_implies(
 ; CHECK-NEXT:    [[C1:%.*]] = icmp ne i32 [[X:%.*]], 0
 ; CHECK-NEXT:    [[C2:%.*]] = icmp ne i32 [[X]], 42
-; CHECK-NEXT:    [[RES:%.*]] = select i1 [[C1]], i1 [[C2]], i1 false
+; CHECK-NEXT:    [[RES:%.*]] = and i1 [[C1]], [[C2]]
 ; CHECK-NEXT:    ret i1 [[RES]]
 ;
   %c1 = icmp ne i32 %x, 0
   %c2 = icmp ne i32 %x, 42
   %res = select i1 %c1, i1 %c2, i1 false
   ret i1 %res
 }
 
 ; Will fold after conversion to and.
 define i1 @logical_and_implies_folds(i32 %x) {
 ; CHECK-LABEL: @logical_and_implies_folds(
 ; CHECK-NEXT:    [[C1:%.*]] = icmp ugt i32 [[X:%.*]], 42
-; CHECK-NEXT:    [[C2:%.*]] = icmp ne i32 [[X]], 0
-; CHECK-NEXT:    [[RES:%.*]] = select i1 [[C1]], i1 [[C2]], i1 false
-; CHECK-NEXT:    ret i1 [[RES]]
+; CHECK-NEXT:    ret i1 [[C1]]
 ;
   %c1 = icmp ugt i32 %x, 42
   %c2 = icmp ne i32 %x, 0
   %res = select i1 %c1, i1 %c2, i1 false
   ret i1 %res
 }
 
 ; Noundef on condition has no effect.
 define i1 @logical_or_noundef_a(i1 noundef %a, i1 %b) {
 ; CHECK-LABEL: @logical_or_noundef_a(
 ; CHECK-NEXT:    [[RES:%.*]] = select i1 [[A:%.*]], i1 true, i1 [[B:%.*]]
 ; CHECK-NEXT:    ret i1 [[RES]]
 ;
   %res = select i1 %a, i1 true, i1 %b
   ret i1 %res
 }
 
 ; Noundef on false value allows conversion to or.
+; TODO: impliesPoison doesn't handle this yet.
 define i1 @logical_or_noundef_b(i1 %a, i1 noundef %b) {
 ; CHECK-LABEL: @logical_or_noundef_b(
 ; CHECK-NEXT:    [[RES:%.*]] = select i1 [[A:%.*]], i1 true, i1 [[B:%.*]]
 ; CHECK-NEXT:    ret i1 [[RES]]
 ;
   %res = select i1 %a, i1 true, i1 %b
   ret i1 %res
 }
 
 ; Noundef on condition has no effect.
 define i1 @logical_and_noundef_a(i1 noundef %a, i1 %b) {
 ; CHECK-LABEL: @logical_and_noundef_a(
 ; CHECK-NEXT:    [[RES:%.*]] = select i1 [[A:%.*]], i1 [[B:%.*]], i1 false
 ; CHECK-NEXT:    ret i1 [[RES]]
 ;
   %res = select i1 %a, i1 %b, i1 false
   ret i1 %res
 }
 
 ; Noundef on false value allows conversion to and.
+; TODO: impliesPoison doesn't handle this yet.
 define i1 @logical_and_noundef_b(i1 %a, i1 noundef %b) {
 ; CHECK-LABEL: @logical_and_noundef_b(
 ; CHECK-NEXT:    [[RES:%.*]] = select i1 [[A:%.*]], i1 [[B:%.*]], i1 false
 ; CHECK-NEXT:    ret i1 [[RES]]
 ;
   %res = select i1 %a, i1 %b, i1 false
   ret i1 %res
 }