[InstCombine] Disable unsafe select transform behind a flag

[nikic]

Summary

This disables the poison-unsafe select -> and/or transform behind a flag (we continue to perform the fold by default). This is intended to simplify testing while we add support for the select pattern. Otherwise, there's no way to test InstCombine-related changes, as InstCombine would just canonicalize it away.

This only disables the main select -> and/or transform. A number of related ones are instead changed to canonicalize to the a ? b : false and a ? true : b forms which represent and/or respectively. This requires a bit of care to avoid infinite loops, as we do not want !a ? b : false to be converted into a ? false : b.

The basic idea here is the same as D93065, this just keeps it behind a flag, and retains the canonicalizations.

[aqjune]

I'm fine with this flag.
@congzhe What do you think? If this lands, you can simply check your benchmark's performance with this flag disabled.

[aqjune]

What do you think about using D78152 to allow select -> and/or when it's safe (maybe in a separate patch)?

select x, y, false -> and x, y is safe if impliesPoison(y, x) holds because it guarantees that there is no such case that x is non-poison and y is poison.
The transformation is safe if x and y are non-poison: see https://alive2.llvm.org/ce/z/3X6bkc

I think this will allow many useful optimizations in InstCombine/InstSimplify working on and/or.

llvm/include/llvm/Transforms/InstCombine/InstCombiner.h

public:
 
   llvm::Optional<std::pair<
       CmpInst::Predicate,
       Constant *>> static getFlippedStrictnessPredicateAndConstant(CmpInst::
                                                                        Predicate
                                                                            Pred,
                                                                    Constant *C);
 
+  static bool shouldAvoidAbsorbingNotIntoSelect(const SelectInst &SI) {
+    // a ? b : false and a ? true : b are the canonical form of logical and/or.
+    // This includes !a ? b : false and !a ? true : b. Absorbing the not into
+    // the select by swapping operands would break recognition of this pattern
+    // in other analyses, so don't do that.
+    return match(&SI, PatternMatch::m_LogicalAnd(PatternMatch::m_Value(),
+                                                 PatternMatch::m_Value())) ||
+           match(&SI, PatternMatch::m_LogicalOr(PatternMatch::m_Value(),
+                                                PatternMatch::m_Value()));
+  }
+
   /// Return true if the specified value is free to invert (apply ~ to).
   /// This happens in cases where the ~ can be eliminated.  If WillInvertAllUses
   /// is true, work under the assumption that the caller intends to remove all
   /// uses of V and only keep uses of ~V.
   ///
   /// See also: canFreelyInvertAllUsersOf()
   static bool isFreeToInvert(Value *V, bool WillInvertAllUses) {
     // ~(~(X)) -> X.
for (Use &U : V->uses()) {
       if (U.getUser() == IgnoredUser)
         continue; // Don't consider this user.
 
       auto *I = cast<Instruction>(U.getUser());
       switch (I->getOpcode()) {
       case Instruction::Select:
         if (U.getOperandNo() != 0) // Only if the value is used as select cond.
           return false;
+        if (shouldAvoidAbsorbingNotIntoSelect(*cast<SelectInst>(I)))
+          return false;
         break;
       case Instruction::Br:
         assert(U.getOperandNo() == 0 && "Must be branching on that value.");
         break; // Free to invert by swapping true/false values/destinations.
       case Instruction::Xor: // Can invert 'xor' if it's a 'not', by ignoring
                              // it.
         if (!match(I, m_Not(PatternMatch::m_Value())))
           return false; // Not a 'not'.

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

 #include <cassert>
 #include <utility>
 
 using namespace llvm;
 using namespace PatternMatch;
 
 #define DEBUG_TYPE "instcombine"
 
+/// FIXME: Enabled by default until the pattern is supported well.
+static cl::opt<bool> EnableUnsafeSelectTransform(
+    "instcombine-unsafe-select-transform", cl::init(true),
+    cl::desc("Enable poison-unsafe select to and/or transform"));
+
 static Value *createMinMax(InstCombiner::BuilderTy &Builder,
                            SelectPatternFlavor SPF, Value *A, Value *B) {
   CmpInst::Predicate Pred = getMinMaxPred(SPF);
   assert(CmpInst::isIntPredicate(Pred) && "Expected integer predicate");
   return Builder.CreateSelect(Builder.CreateICmp(Pred, A, B), A, B);
 }
 
 /// Replace a select operand based on an equality comparison with the identity
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 (match(TrueVal, m_One())) {
+    if (EnableUnsafeSelectTransform && match(TrueVal, m_One())) {
       // Change: A = select B, true, C --> A = or B, C
       return BinaryOperator::CreateOr(CondVal, FalseVal);
     }
-    if (match(TrueVal, m_Zero())) {
-      // Change: A = select B, false, C --> A = and !B, C
-      Value *NotCond = Builder.CreateNot(CondVal, "not." + CondVal->getName());
-      return BinaryOperator::CreateAnd(NotCond, FalseVal);
-    }
-    if (match(FalseVal, m_Zero())) {
+    if (EnableUnsafeSelectTransform && match(FalseVal, m_Zero())) {
       // 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,
+                                ConstantInt::getFalse(SelType));
+    }
+    // select a, b, true -> select !a, true, b
     if (match(FalseVal, m_One())) {
-      // Change: A = select B, C, true --> A = or !B, C
       Value *NotCond = Builder.CreateNot(CondVal, "not." + CondVal->getName());
-      return BinaryOperator::CreateOr(NotCond, TrueVal);
+      return SelectInst::Create(NotCond, ConstantInt::getTrue(SelType),
+                                TrueVal);
     }
 
-    // select a, a, b  -> a | b
-    // select a, b, a  -> a & b
+    // select a, a, b -> select a, true, b
     if (CondVal == TrueVal)
-      return BinaryOperator::CreateOr(CondVal, FalseVal);
+      return replaceOperand(SI, 1, ConstantInt::getTrue(SelType));
+    // select a, b, a -> select a, b, false
     if (CondVal == FalseVal)
-      return BinaryOperator::CreateAnd(CondVal, TrueVal);
+      return replaceOperand(SI, 2, ConstantInt::getFalse(SelType));
 
-    // select a, ~a, b -> (~a) & b
-    // select a, b, ~a -> (~a) | b
+    // select a, !a, b -> select !a, b, false
     if (match(TrueVal, m_Not(m_Specific(CondVal))))
-      return BinaryOperator::CreateAnd(TrueVal, FalseVal);
+      return SelectInst::Create(TrueVal, FalseVal,
+                                ConstantInt::getFalse(SelType));
+    // select a, b, !a -> select !a, true, b
     if (match(FalseVal, m_Not(m_Specific(CondVal))))
-      return BinaryOperator::CreateOr(TrueVal, FalseVal);
+      return SelectInst::Create(FalseVal, ConstantInt::getTrue(SelType),
+                                TrueVal);
   }
 
   // Selecting between two integer or vector splat integer constants?
   //
   // Note that we don't handle a scalar select of vectors:
   // select i1 %c, <2 x i8> <1, 1>, <2 x i8> <0, 0>
   // because that may need 3 instructions to splat the condition value:
   // extend, insertelement, shufflevector.
if (auto *FalseBOSI = dyn_cast<SelectInst>(FalseBO->getOperand(1))) {
         replaceOperand(*FalseBO, 1, FalseBOSI->getFalseValue());
         Worklist.push(FalseBO);
         return &SI;
       }
     }
   }
 
   Value *NotCond;
-  if (match(CondVal, m_Not(m_Value(NotCond)))) {
+  if (match(CondVal, m_Not(m_Value(NotCond))) &&
+      !InstCombiner::shouldAvoidAbsorbingNotIntoSelect(SI)) {
     replaceOperand(SI, 0, NotCond);
     SI.swapValues();
     SI.swapProfMetadata();
     return &SI;
   }
 
   if (Instruction *I = foldVectorSelect(SI))
     return I;

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

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -S -instcombine -instcombine-unsafe-select-transform=0 < %s | FileCheck %s
+
+; Should not be converted to "and", which has different poison semantics.
+define i1 @logical_and(i1 %a, i1 %b) {
+; CHECK-LABEL: @logical_and(
+; 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
+}
+
+; Should not be converted to "or", which has different poison semantics.
+define i1 @logical_or(i1 %a, i1 %b) {
+; CHECK-LABEL: @logical_or(
+; 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
+}
+; Canonicalize to logical and form, even if that requires adding a "not".
+define i1 @logical_and_not(i1 %a, i1 %b) {
+; CHECK-LABEL: @logical_and_not(
+; CHECK-NEXT:    [[NOT_A:%.*]] = xor i1 [[A:%.*]], true
+; CHECK-NEXT:    [[RES:%.*]] = select i1 [[NOT_A]], i1 [[B:%.*]], i1 false
+; CHECK-NEXT:    ret i1 [[RES]]
+;
+  %res = select i1 %a, i1 false, i1 %b
+  ret i1 %res
+}
+
+; Canonicalize to logical or form, even if that requires adding a "not".
+define i1 @logical_or_not(i1 %a, i1 %b) {
+; CHECK-LABEL: @logical_or_not(
+; CHECK-NEXT:    [[NOT_A:%.*]] = xor i1 [[A:%.*]], true
+; CHECK-NEXT:    [[RES:%.*]] = select i1 [[NOT_A]], i1 true, i1 [[B:%.*]]
+; CHECK-NEXT:    ret i1 [[RES]]
+;
+  %res = select i1 %a, i1 %b, i1 true
+  ret i1 %res
+}
+
+; These are variants where condition or !condition is used to represent true
+; or false in one of the select arms. It should be canonicalized to the
+; constants.
+
+define i1 @logical_and_cond_reuse(i1 %a, i1 %b) {
+; CHECK-LABEL: @logical_and_cond_reuse(
+; CHECK-NEXT:    [[RES:%.*]] = select i1 [[A:%.*]], i1 [[B:%.*]], i1 false
+; CHECK-NEXT:    ret i1 [[RES]]
+;
+  %res = select i1 %a, i1 %b, i1 %a
+  ret i1 %res
+}
+
+define i1 @logical_or_cond_reuse(i1 %a, i1 %b) {
+; CHECK-LABEL: @logical_or_cond_reuse(
+; CHECK-NEXT:    [[RES:%.*]] = select i1 [[A:%.*]], i1 true, i1 [[B:%.*]]
+; CHECK-NEXT:    ret i1 [[RES]]
+;
+  %res = select i1 %a, i1 %a, i1 %b
+  ret i1 %res
+}
+
+define i1 @logical_and_not_cond_reuse(i1 %a, i1 %b) {
+; CHECK-LABEL: @logical_and_not_cond_reuse(
+; CHECK-NEXT:    [[A_NOT:%.*]] = xor i1 [[A:%.*]], true
+; CHECK-NEXT:    [[RES:%.*]] = select i1 [[A_NOT]], i1 true, i1 [[B:%.*]]
+; CHECK-NEXT:    ret i1 [[RES]]
+;
+  %a.not = xor i1 %a, true
+  %res = select i1 %a, i1 %b, i1 %a.not
+  ret i1 %res
+}
+
+define i1 @logical_or_not_cond_reuse(i1 %a, i1 %b) {
+; CHECK-LABEL: @logical_or_not_cond_reuse(
+; CHECK-NEXT:    [[A_NOT:%.*]] = xor i1 [[A:%.*]], true
+; CHECK-NEXT:    [[RES:%.*]] = select i1 [[A_NOT]], i1 [[B:%.*]], i1 false
+; CHECK-NEXT:    ret i1 [[RES]]
+;
+  %a.not = xor i1 %a, true
+  %res = select i1 %a, i1 %a.not, i1 %b
+  ret i1 %res
+}