[InstSimplify] ExpandBinOp should fold an expression only when it's safe

[aqjune]

Summary

ExpandBinOp folds (A op' B) op C by transforming it into
(A op C) op' (B op C) first, simplifying the two subexpressions
(say the result as L and R), and folding L op' R if possible.

However, if C contains undef, this results in making undef have two different
values whereas the original expression may not;
as a simplest case, transforming undef * (1 + 1) into undef + undef isn't
safe, because the former one is an even whereas the latter one is any number.

This patch makes ExpandBinOp fold only when it's safe.

1. If either L or R is special in that L op' ? or ? op' R always folds into a constant, it is safe to fold the expression to the constant.

2. If C is never undef or poison, it is safe.

After this patch, transformation https://reviews.llvm.org/D83360#2146539 does not happen
after D83360 is enabled.

At https://reviews.llvm.org/D83360#2146539 , I proposed making InstSimplify
remember to which value undefs are folded & use the cached value if the undef
is met again.
My plan was to implement this solution by adding a static ValueOrUse class
(so we can distinguish undefs by Use) and letting InstSimplify's functions
use it instead of Value. But, it had several problems.

1. If InstSimplify fails to simplify values, the record of folded undefs should be rewinded at function returns. Doing this all over InstSimplify is error-prone and easy to miss.

2. Sometimes the value that undef is folded isn't just a constant. For example, if undef + 1 <= X is folded into true, the undef is folded into either -1 or a random number between [0, X-1]. Recording this isn't trivial.

3. Constant folding can fold undefs too. This causes changes in the relevant libraries.

4. Finally, if InstSimplify becomes smart enough, this still can cause miscompilation. For example, if InstSimplify skims through instructions in the same basic block and find equivalent expressions, a miscompilation can happen without explicit folding of undefs.

Another approach that I tried was to simply
stopping undef folds when called from ExpandBinOp recursively.
However, this also required a nontrivial change because two
UndefValue instances compare equal, leading to undesirable foldings like
undef - undef --> 0.
Also, it still does not resolve the possible miscompilation problem.

[aqjune]

Running SPEC2017rate using testsuite with -O3, LTO Enabled shows negligible impact on the quality of generated code (less than 0.15% slowdown)

CINT2017rate.csv1 KBDownload

CFP2017rate.csv1 KBDownload

[aqjune]

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

208

According to this comment, this test is simply for checking whether there is no assertion failure.

[spatel]

How about reducing the code duplication with a preliminary clean-up patch?

diff --git a/llvm/lib/Analysis/InstructionSimplify.cpp b/llvm/lib/Analysis/InstructionSimplify.cpp
index 8fbcee84a15..22b1dac8d65 100644
--- a/llvm/lib/Analysis/InstructionSimplify.cpp
+++ b/llvm/lib/Analysis/InstructionSimplify.cpp
@@ -228,64 +228,54 @@ static bool valueDominatesPHI(Value *V, PHINode *P, const DominatorTree *DT) {
   return false;
 }

-/// Simplify "A op (B op' C)" by distributing op over op', turning it into
-/// "(A op B) op' (A op C)".  Here "op" is given by Opcode and "op'" is
-/// given by OpcodeToExpand, while "A" corresponds to LHS and "B op' C" to RHS.
-/// Also performs the transform "(A op' B) op C" -> "(A op C) op' (B op C)".
-/// Returns the simplified value, or null if no simplification was performed.
-static Value *ExpandBinOp(Instruction::BinaryOps Opcode, Value *LHS, Value *RHS,
-                          Instruction::BinaryOps OpcodeToExpand,
+/// Try to simplify a binary operator of form "V op OtherOp" where V is
+/// "(B0 opex B1)" by distributing 'op' across 'opex' as
+/// "(B0 op OtherOp) opex (B1 op OtherOp)".
+static Value *expandBinOp(Instruction::BinaryOps Opcode, Value *V,
+                          Value *OtherOp, Instruction::BinaryOps OpcodeToExpand,
                           const SimplifyQuery &Q, unsigned MaxRecurse) {
-  // Recursion is always used, so bail out at once if we already hit the limit.
-  if (!MaxRecurse--)
+  auto *B = dyn_cast<BinaryOperator>(V);
+  if (!B || B->getOpcode() != OpcodeToExpand)
+    return nullptr;
+  Value *B0 = B->getOperand(0), *B1 = B->getOperand(1);
+  Value *L = SimplifyBinOp(Opcode, B0, OtherOp, Q, MaxRecurse);
+  if (!L)
+    return nullptr;
+  Value *R = SimplifyBinOp(Opcode, B1, OtherOp, Q, MaxRecurse);
+  if (!R)
     return nullptr;

-  // Check whether the expression has the form "(A op' B) op C".
-  if (BinaryOperator *Op0 = dyn_cast<BinaryOperator>(LHS))
-    if (Op0->getOpcode() == OpcodeToExpand) {
-      // It does!  Try turning it into "(A op C) op' (B op C)".
-      Value *A = Op0->getOperand(0), *B = Op0->getOperand(1), *C = RHS;
-      // Do "A op C" and "B op C" both simplify?
-      if (Value *L = SimplifyBinOp(Opcode, A, C, Q, MaxRecurse))
-        if (Value *R = SimplifyBinOp(Opcode, B, C, Q, MaxRecurse)) {
-          // They do! Return "L op' R" if it simplifies or is already available.
-          // If "L op' R" equals "A op' B" then "L op' R" is just the LHS.
-          if ((L == A && R == B) || (Instruction::isCommutative(OpcodeToExpand)
-                                     && L == B && R == A)) {
-            ++NumExpand;
-            return LHS;
-          }
-          // Otherwise return "L op' R" if it simplifies.
-          if (Value *V = SimplifyBinOp(OpcodeToExpand, L, R, Q, MaxRecurse)) {
-            ++NumExpand;
-            return V;
-          }
-        }
-    }
+  // Does the expanded pair of binops simplify to the existing binop?
+  if ((L == B0 && R == B1) ||
+      (Instruction::isCommutative(OpcodeToExpand) && L == B1 && R == B0)) {
+    ++NumExpand;
+    return B;
+  }

-  // Check whether the expression has the form "A op (B op' C)".
-  if (BinaryOperator *Op1 = dyn_cast<BinaryOperator>(RHS))
-    if (Op1->getOpcode() == OpcodeToExpand) {
-      // It does!  Try turning it into "(A op B) op' (A op C)".
-      Value *A = LHS, *B = Op1->getOperand(0), *C = Op1->getOperand(1);
-      // Do "A op B" and "A op C" both simplify?
-      if (Value *L = SimplifyBinOp(Opcode, A, B, Q, MaxRecurse))
-        if (Value *R = SimplifyBinOp(Opcode, A, C, Q, MaxRecurse)) {
-          // They do! Return "L op' R" if it simplifies or is already available.
-          // If "L op' R" equals "B op' C" then "L op' R" is just the RHS.
-          if ((L == B && R == C) || (Instruction::isCommutative(OpcodeToExpand)
-                                     && L == C && R == B)) {
-            ++NumExpand;
-            return RHS;
-          }
-          // Otherwise return "L op' R" if it simplifies.
-          if (Value *V = SimplifyBinOp(OpcodeToExpand, L, R, Q, MaxRecurse)) {
-            ++NumExpand;
-            return V;
-          }
-        }
-    }
+  // Otherwise, return "L op' R" if it simplifies.
+  Value *S = SimplifyBinOp(OpcodeToExpand, L, R, Q, MaxRecurse);
+  if (!S)
+    return nullptr;

+  ++NumExpand;
+  return S;
+}
+
+/// Try to simplify binops of form "A op (B op' C)" or the commuted variant by
+/// distributing op over op'.
+static Value *expandCommutativeBinOp(Instruction::BinaryOps Opcode,
+                                     Value *L, Value *R,
+                                     Instruction::BinaryOps OpcodeToExpand,
+                                     const SimplifyQuery &Q,
+                                     unsigned MaxRecurse) {
+  // Recursion is always used, so bail out at once if we already hit the limit.
+  if (!MaxRecurse--)
+    return nullptr;
+
+  if (Value *V = expandBinOp(Opcode, L, R, OpcodeToExpand, Q, MaxRecurse))
+    return V;
+  if (Value *V = expandBinOp(Opcode, R, L, OpcodeToExpand, Q, MaxRecurse))
+    return V;
   return nullptr;
 }

@@ -901,8 +891,8 @@ static Value *SimplifyMulInst(Value *Op0, Value *Op1, const SimplifyQuery &Q,
     return V;

   // Mul distributes over Add. Try some generic simplifications based on this.
-  if (Value *V = ExpandBinOp(Instruction::Mul, Op0, Op1, Instruction::Add,
-                             Q, MaxRecurse))
+  if (Value *V = expandCommutativeBinOp(Instruction::Mul, Op0, Op1,
+                                        Instruction::Add, Q, MaxRecurse))
     return V;

   // If the operation is with the result of a select instruction, check whether
@@ -2095,13 +2085,13 @@ static Value *SimplifyAndInst(Value *Op0, Value *Op1, const SimplifyQuery &Q,
     return V;

   // And distributes over Or.  Try some generic simplifications based on this.
-  if (Value *V = ExpandBinOp(Instruction::And, Op0, Op1, Instruction::Or,
-                             Q, MaxRecurse))
+  if (Value *V = expandCommutativeBinOp(Instruction::And, Op0, Op1,
+                                        Instruction::Or, Q, MaxRecurse))
     return V;

   // And distributes over Xor.  Try some generic simplifications based on this.
-  if (Value *V = ExpandBinOp(Instruction::And, Op0, Op1, Instruction::Xor,
-                             Q, MaxRecurse))
+  if (Value *V = expandCommutativeBinOp(Instruction::And, Op0, Op1,
+                                        Instruction::Xor, Q, MaxRecurse))
     return V;

   // If the operation is with the result of a select instruction, check whether
@@ -2253,8 +2243,8 @@ static Value *SimplifyOrInst(Value *Op0, Value *Op1, const SimplifyQuery &Q,
     return V;

   // Or distributes over And.  Try some generic simplifications based on this.
-  if (Value *V = ExpandBinOp(Instruction::Or, Op0, Op1, Instruction::And, Q,
-                             MaxRecurse))
+  if (Value *V = expandCommutativeBinOp(Instruction::Or, Op0, Op1,
+                                        Instruction::And, Q, MaxRecurse))
     return V;

   // If the operation is with the result of a select instruction, check whether

[aqjune]

@spatel Hi, yes, it sounds great.
I'm fine with updating this patch after the patch is landed.

[spatel]

In D84250#2168995, @aqjune wrote:

@spatel Hi, yes, it sounds great.
I'm fine with updating this patch after the patch is landed.

Refactoring committed here:
rG7485e924121

[aqjune]

Rebase

[spatel]

We need some tests pre-committed within InstSimplify to show this working (disabling simplify) for each opcode?

llvm/lib/Analysis/InstructionSimplify.cpp

231–234

Could we adapt this existing analysis function?

/// Return the absorbing element for the given binary
/// operation, i.e. a constant C such that X op C = C and C op X = C for
/// every X.  For example, this returns zero for integer multiplication.
/// It returns null if the operator doesn't have an absorbing element.
static Constant *getBinOpAbsorber(unsigned Opcode, Type *Ty);

[aqjune]

• Use getBinOpAbsorber
• Add tests

I couldn't find a test that was previously optimized but now unoptimized,
except when & and ^ are combined.

[spatel]

I tried to find other examples where this could happen, and I can't find anything else either.
So I think this just needs some minor changes.
However, Alive2 does not show the "f_dontfold" test example or my reduced candidate test as incorrect - is that a bug for Alive2?
https://alive2.llvm.org/ce/z/dbGLzN

llvm/lib/Analysis/InstructionSimplify.cpp

231

Can say "This function returns..." to make it independent of the actual function name.
Use "///" to create documentation comment.

249

Formatting for function name: "Fold..." -> "fold..."

255–258

Is this dead code? The current callers of expandBinOp only have "OpcodeToExpand" possiblities for:
Instruction::Add
Instruction::And
Instruction::Or
Instruction::Xor

If that is correct, maybe we want to just make it a 'TODO' comment?
If not, we could still simplify the code to something like:

if (BinaryOperator::isShift(Op) && match(L, m_Zero()))

llvm/test/Transforms/InstSimplify/distribute.ll

4

I was confused by this example because the 'x' in the code comment is not the same as the 'x' in the test.
How about reducing the example to:

define i4 @expand_and_xor(i4 %x, i4 %y) {
  %notx = xor i4 %x, -1
  %a = and i4 %notx, %y
  %nota = xor i4 %a, -1
  %result = and i4 %x, %nota
  ret i4 %result
}

[aqjune]

In D84250#2187305, @spatel wrote:

I tried to find other examples where this could happen, and I can't find anything else either.
So I think this just needs some minor changes.
However, Alive2 does not show the "f_dontfold" test example or my reduced candidate test as incorrect - is that a bug for Alive2?
https://alive2.llvm.org/ce/z/dbGLzN

f_dontfold simply shows that the patch prevents the folding; it is still correct to fold the expression. I'll leave TODO there.
I'll update this patch to reflect the comments.

[aqjune]

Reflect comments

[aqjune]

In D84250#2187367, @aqjune wrote:

In D84250#2187305, @spatel wrote:

I tried to find other examples where this could happen, and I can't find anything else either.
So I think this just needs some minor changes.
However, Alive2 does not show the "f_dontfold" test example or my reduced candidate test as incorrect - is that a bug for Alive2?
https://alive2.llvm.org/ce/z/dbGLzN

f_dontfold simply shows that the patch prevents the folding; it is still correct to fold the expression. I'll leave TODO there.
I'll update this patch to reflect the comments.

I understood the question; the comments in distribute.ll were wrong. The transformations are valid even if x is undef. I fixed the comments.

[nikic]

Assuming D84792 lands, would performing the two SimplifyBinOp queries for L and R with CanUseUndef=false solve this problem as well? I would prefer that if it works.

[spatel]

It's not clear to me how these all of the undef safety features will come together, but this looks correct and unlikely to cause regressions, so LGTM.

[aqjune]

In D84250#2187617, @nikic wrote:

Assuming D84792 lands, would performing the two SimplifyBinOp queries for L and R with CanUseUndef=false solve this problem as well? I would prefer that if it works.

I think there is a trade-off between full correctness and performance. If InstSimplify can be arbitrarily smart in the future, simply blocking the transformation as shown in this patch seems to be the right way IMO.
For example, InstSimplify in the future can iterate over the BB and find equivalent instructions (as GVN does): in this case, a miscompilation can still happen, because distributivity can lead to replacing 2 * x with x + x.
Also, another concern that I had with bringing the can-undef-fold flag was that the change was global: whenever we add a new optimization to InstSimplify, it should consider whether CanUseUndef was correctly considered (maybe ConstantFolding, too?).

However, InstSimplify may not need to be very smart, and the cost of maintenance may not be very big in practice as well.
I am willing to follow the result of discussion.

[kazu]

Friendly ping.

Is there something left to improve in this patch? I'm asking this because a fix for https://bugs.llvm.org/show_bug.cgi?id=46940 builds on this fix, so I'd like to see this patch checked in if there is no pending issues. Thanks!

[echristo]

I think that we should revert the original patch for now since we have a
known miscompile and a chain of fixes are required to fix it.

As far as whether or not we can cause problems downstream from an
instcombine change - it's true, and unfortunately those need to be fixed
before we can have the instcombine as well if we find them.

Thanks!

[aqjune]

Should we go to D84792's direction?
If it is, I think we should mention that it is a workaround for the miscompilations including PR33165, and it can still be problematic in theory but chose to do it for performance.

[spatel]

In D84250#2202732, @aqjune wrote:

Should we go to D84792's direction?
If it is, I think we should mention that it is a workaround for the miscompilations including PR33165, and it can still be problematic in theory but chose to do it for performance.

I don't have a preference, but others said they would like go with D84792, so let's do that.

[aqjune]

In D84250#2202791, @spatel wrote:

I don't have a preference, but others said they would like go with D84792, so let's do that.

Well, okay. It is moving toward being more correct anyway, so it's good.

In D84250#2201322, @kazu wrote:

Is there something left to improve in this patch? I'm asking this because a fix for https://bugs.llvm.org/show_bug.cgi?id=46940 builds on this fix, so I'd like to see this patch checked in if there is no pending issues. Thanks!

Hello @kazu, sorry for making a confusion.
If D84792 lands, you can instead try calling SimplifyBinOp with giving false to SQ.CanUseUndef and check whether the bug disappears.

llvm/lib/Analysis/InstructionSimplify.cpp

 //===- InstructionSimplify.cpp - Fold instruction operands ----------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
static bool valueDominatesPHI(Value *V, PHINode *P, const DominatorTree *DT) {
   // then it obviously dominates all phi nodes.
   if (I->getParent() == &I->getFunction()->getEntryBlock() &&
       !isa<InvokeInst>(I) && !isa<CallBrInst>(I))
     return true;
 
   return false;
 }
 
+// CanFoldToConstantUsingOneOperand returns a constant after folding "L Op R"
+// after using only one of L or R, but not both.
+// Formally, it returns a constant X s.t. "L Op Y --> X" or "Y Op R --> X" holds
+//   for any Y (E --> V means E can be simplifed to V).
+//
+// ex)  Given "0 & R", X is 0.
+// ex2) Given "L | -1", X is -1.
+// ex3) Given "0 + 0", there is no such X.
+//
+// If L or R is undef, whenever undef in L is chosen to be a specific
+// constant, it should be assumed that R's value has changed (and vice versa).
+//
+// ex4) Given "undef + 0", X cannot be 0: if L = undef is chosen to be 0,
+//      R cannot be 0 anymore.
+// ex5) Given "undef + undef", X cannot be 0: If L = undef is chosen to be 0,
+//      R may have changed into 1, causing X to be 1.
+// ex6) Given "undef & R", X is 0. If L = undef is chosen to be 0, the result
+//      is 0 regardless of R.
+static Constant *FoldUsingOneOperand(Instruction::BinaryOps Op, Value *L,
+                                     Value *R) {
+  if (auto C = ConstantExpr::getBinOpAbsorber(Op, L->getType())) {
+    if (L == C || R == C || isa<UndefValue>(L) || isa<UndefValue>(R))
+      return C;
+  }
+  switch (Op) {
+  case Instruction::Shl:
+  case Instruction::AShr:
+  case Instruction::LShr:
+    // If L is zero, we can always fold the result into zero.
+    // (If shiftamt >= LHS's bitwidth, the result is poison, but it can be
+    //  folded into zero)
+    return match(L, m_Zero()) ? Constant::getNullValue(L->getType()) : nullptr;
+  default:
+    break;
+  }
+  return nullptr;
+}
+
 /// Try to simplify a binary operator of form "V op OtherOp" where V is
 /// "(B0 opex B1)" by distributing 'op' across 'opex' as
 /// "(B0 op OtherOp) opex (B1 op OtherOp)".
 static Value *expandBinOp(Instruction::BinaryOps Opcode, Value *V,
                           Value *OtherOp, Instruction::BinaryOps OpcodeToExpand,
                           const SimplifyQuery &Q, unsigned MaxRecurse) {
   auto *B = dyn_cast<BinaryOperator>(V);
   if (!B || B->getOpcode() != OpcodeToExpand)
     return nullptr;
   Value *B0 = B->getOperand(0), *B1 = B->getOperand(1);
   Value *L = SimplifyBinOp(Opcode, B0, OtherOp, Q, MaxRecurse);
   if (!L)
     return nullptr;
   Value *R = SimplifyBinOp(Opcode, B1, OtherOp, Q, MaxRecurse);
   if (!R)
     return nullptr;
 
+  // If OtherOp contains undef in its subexpression, the undef should be folded
+  // into the same constant by the two previous SimplifyBinOp calls.
+  // Implementing this 'entanglement' is non-trivial, however.
+  // So, use a simpler approach instead:
+  // (1) If "L Op' R" can be folded into a constant by using only L
+  //     or R, fold it. This is valid because undef folds from either
+  //     "(B0 op OtherOp)" or "(B1 op OtherOp)" are considered, but not both.
+  if (Constant *Res = FoldUsingOneOperand(OpcodeToExpand, L, R)) {
+    ++NumExpand;
+    return Res;
+  }
+  // (2) If OtherOp may be undef or poison, give up.
+  if (!isGuaranteedNotToBeUndefOrPoison(OtherOp, Q.CxtI, Q.DT))
+    return nullptr;
+
   // Does the expanded pair of binops simplify to the existing binop?
   if ((L == B0 && R == B1) ||
       (Instruction::isCommutative(OpcodeToExpand) && L == B1 && R == B0)) {
     ++NumExpand;
     return B;
   }
 
   // Otherwise, return "L op' R" if it simplifies.

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

;
   %and = and <2 x i1> %cmp1, %cmp2
   ret <2 x i1> %and
 }
 
 ; This is a fuzzer-generated test that would assert because
 ; we'd get into foldAndOfICmps() without running InstSimplify
 ; on an 'and' that should have been killed. It's not obvious
 ; why, but removing anything hides the bug, hence the long test.
 
 define void @simplify_before_foldAndOfICmps() {
 ; CHECK-LABEL: @simplify_before_foldAndOfICmps(
 ; CHECK-NEXT:    [[A8:%.*]] = alloca i16, align 2
 ; CHECK-NEXT:    [[L7:%.*]] = load i16, i16* [[A8]], align 2
 ; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i16 [[L7]], -1
 ; CHECK-NEXT:    [[B11:%.*]] = zext i1 [[TMP1]] to i16
 ; CHECK-NEXT:    [[C10:%.*]] = icmp ugt i16 [[L7]], [[B11]]
 ; CHECK-NEXT:    [[C5:%.*]] = icmp slt i16 [[L7]], 1
 ; CHECK-NEXT:    [[C11:%.*]] = icmp ne i16 [[L7]], 0
 ; CHECK-NEXT:    [[C7:%.*]] = icmp slt i16 [[L7]], 0
 ; CHECK-NEXT:    [[B15:%.*]] = xor i1 [[C7]], [[C10]]
 ; CHECK-NEXT:    [[B19:%.*]] = xor i1 [[C11]], [[B15]]
-; CHECK-NEXT:    [[TMP2:%.*]] = and i1 [[C10]], [[C5]]
-; CHECK-NEXT:    [[C3:%.*]] = and i1 [[TMP2]], [[B19]]
-; CHECK-NEXT:    [[TMP3:%.*]] = xor i1 [[C10]], true
-; CHECK-NEXT:    [[C18:%.*]] = or i1 [[C7]], [[TMP3]]
-; CHECK-NEXT:    [[TMP4:%.*]] = sext i1 [[C3]] to i64
-; CHECK-NEXT:    [[G26:%.*]] = getelementptr i1, i1* null, i64 [[TMP4]]
+; CHECK-NEXT:    [[TMP2:%.*]] = xor i1 [[C11]], true
+; CHECK-NEXT:    [[C6:%.*]] = or i1 [[B19]], [[TMP2]]
+; CHECK-NEXT:    [[TMP3:%.*]] = and i1 [[C10]], [[C5]]
+; CHECK-NEXT:    [[C3:%.*]] = and i1 [[TMP3]], [[C6]]
+; CHECK-NEXT:    [[TMP4:%.*]] = xor i1 [[C10]], true
+; CHECK-NEXT:    [[C18:%.*]] = or i1 [[C7]], [[TMP4]]
+; CHECK-NEXT:    [[TMP5:%.*]] = sext i1 [[C3]] to i64
+; CHECK-NEXT:    [[G26:%.*]] = getelementptr i1, i1* null, i64 [[TMP5]]
 ; CHECK-NEXT:    store i16 [[L7]], i16* undef, align 2
 ; CHECK-NEXT:    store i1 [[C18]], i1* undef, align 1
 ; CHECK-NEXT:    store i1* [[G26]], i1** undef, align 8
 ; CHECK-NEXT:    ret void
 ;
   %A8 = alloca i16
   %L7 = load i16, i16* %A8
   %G21 = getelementptr i16, i16* %A8, i8 -1

llvm/test/Transforms/InstSimplify/distribute.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -instsimplify -S | FileCheck %s
 
+; A transformation (x op y) op' z -> (x op' z) op (y op' z) is incorrect in
+; general. After z is copied, each instance of undefs in z may be instantiated
+; into different values.
+; The tranformation is correct if z is never undef.
+; In @f, since x is never undef, %result can be optimized to x.
+;
 ; %result = x & (1 ^ sel) = (x & 1) ^ (x & sel)
 ;         = x ^ (select cond, false, false)
 ;         = x ^ false = x
 ;
 define i1 @f(i1 %cond, i1 noundef %x, i1 %y, i1 %z) {
 ; CHECK-LABEL: @f(
 ; CHECK-NEXT:    ret i1 [[X:%.*]]
 ;
   %notx = xor i1 %x, 1
   %lhs = and i1 %notx, %y
   %rhs = and i1 %notx, %z
   %sel = select i1 %cond, i1 %lhs, i1 %rhs
   %op1 = xor i1 1, %sel
   %result = and i1 %x, %op1
   ret i1 %result
 }
 
 define i1 @f_dontfold(i1 %cond, i1 %x, i1 %y, i1 %z) {
 ; CHECK-LABEL: @f_dontfold(
-; CHECK-NEXT:    ret i1 [[X:%.*]]
+; CHECK-NEXT:    [[NOTX:%.*]] = xor i1 [[X:%.*]], true
+; CHECK-NEXT:    [[LHS:%.*]] = and i1 [[NOTX]], [[Y:%.*]]
+; CHECK-NEXT:    [[RHS:%.*]] = and i1 [[NOTX]], [[Z:%.*]]
+; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[COND:%.*]], i1 [[LHS]], i1 [[RHS]]
+; CHECK-NEXT:    [[OP1:%.*]] = xor i1 true, [[SEL]]
+; CHECK-NEXT:    [[RESULT:%.*]] = and i1 [[X]], [[OP1]]
+; CHECK-NEXT:    ret i1 [[RESULT]]
 ;
   %notx = xor i1 %x, 1
   %lhs = and i1 %notx, %y
   %rhs = and i1 %notx, %z
   %sel = select i1 %cond, i1 %lhs, i1 %rhs
   %op1 = xor i1 1, %sel
   %result = and i1 %x, %op1
   ret i1 %result
 }