[InstCombine] use freeze to enable poison-safe logic->select fold

[spatel]

Summary

Without a freeze, this transform can leak poison to the output:
https://alive2.llvm.org/ce/z/GJuF9i

This makes the transform as uniform as possible, and it can help reduce patterns like issue #58313 (although that particular example probably still needs another transform).

There's a sibling transform just below this one that can be updated as a follow-up if this looks right.

[nikic]

LGTM. If you're looking for more missing logical and/or folds, I've left quite a few !IsLogical breadcrumbs in foldAndOrOfICmps()...

[spatel]

In D136527#3876994, @nikic wrote:

LGTM. If you're looking for more missing logical and/or folds, I've left quite a few !IsLogical breadcrumbs in foldAndOrOfICmps()...

Thanks! I was just trying to make sure that simple cases like in the bug report don't escape, so probably don't need to go too much further at the moment, but we'll see... :)

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

if (SelType->isIntOrIntVectorTy(1) && !isa<Constant>(CondVal) &&
     }
 
     if (match(TrueVal, m_One())) {
       Value *C;
 
       // (C && A) || (!C && B) --> sel C, A, B
       // (A && C) || (!C && B) --> sel C, A, B
       // (C && A) || (B && !C) --> sel C, A, B
-      // (A && C) || (B && !C) --> sel C, A, B (only with real 'and' ops)
+      // (A && C) || (B && !C) --> sel C, A, B (may require freeze)
       if (match(FalseVal, m_c_LogicalAnd(m_Not(m_Value(C)), m_Value(B))) &&
           match(CondVal, m_c_LogicalAnd(m_Specific(C), m_Value(A)))) {
         auto *SelCond = dyn_cast<SelectInst>(CondVal);
         auto *SelFVal = dyn_cast<SelectInst>(FalseVal);
-        if (!SelCond || !SelFVal ||
-            !match(SelFVal->getTrueValue(),
-                   m_Not(m_Specific(SelCond->getTrueValue()))))
-          return SelectInst::Create(C, A, B);
+        bool MayNeedFreeze = SelCond && SelFVal &&
+                             match(SelFVal->getTrueValue(),
+                                   m_Not(m_Specific(SelCond->getTrueValue())));
+        if (MayNeedFreeze)
+          C = Builder.CreateFreeze(C);
       }
 
       // (!C && A) || (C && B) --> sel C, B, A
       // (!C && A) || (B && C) --> sel C, B, A
       // TODO: Allow more commutes as with the previous fold.
       if (match(CondVal, m_LogicalAnd(m_Not(m_Value(C)), m_Value(A))) &&
           match(FalseVal, m_c_LogicalAnd(m_Specific(C), m_Value(B))))
         return SelectInst::Create(C, B, A);

llvm/test/Transforms/InstCombine/select-safe-transforms.ll

;
   %b = call i1 @gen1()
   %not = xor i1 %c, -1
   %and1 = and i1 %c, %a
   %and2 = and i1 %b, %not
   %or = select i1 %and1, i1 true, i1 %and2
   ret i1 %or
 }
 
-; This is not safe to transform if 'c' could be poison.
+; Freeze 'c' to prevent poison from leaking.
 
 define i1 @bools2_logical_commute3(i1 %a, i1 %b, i1 %c) {
 ; CHECK-LABEL: @bools2_logical_commute3(
-; CHECK-NEXT:    [[NOT:%.*]] = xor i1 [[C:%.*]], true
-; CHECK-NEXT:    [[AND1:%.*]] = select i1 [[A:%.*]], i1 [[C]], i1 false
-; CHECK-NEXT:    [[AND2:%.*]] = select i1 [[B:%.*]], i1 [[NOT]], i1 false
-; CHECK-NEXT:    [[OR:%.*]] = select i1 [[AND1]], i1 true, i1 [[AND2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = freeze i1 [[C:%.*]]
+; CHECK-NEXT:    [[OR:%.*]] = select i1 [[TMP1]], i1 [[A:%.*]], i1 [[B:%.*]]
 ; CHECK-NEXT:    ret i1 [[OR]]
 ;
   %not = xor i1 %c, -1
   %and1 = select i1 %a, i1 %c, i1 false
   %and2 = select i1 %b, i1 %not, i1 false
   %or = select i1 %and1, i1 true, i1 %and2
   ret i1 %or
 }
 
+; No freeze needed when 'c' is guaranteed not be poison.
+; Intermediate logic folds may already reduce this.
+
 define i1 @bools2_logical_commute3_nopoison(i1 %a, i1 %b, i1 noundef %c) {
 ; CHECK-LABEL: @bools2_logical_commute3_nopoison(
 ; CHECK-NEXT:    [[OR:%.*]] = select i1 [[C:%.*]], i1 [[A:%.*]], i1 [[B:%.*]]
 ; CHECK-NEXT:    ret i1 [[OR]]
 ;
   %not = xor i1 %c, -1
   %and1 = select i1 %a, i1 %c, i1 false
   %and2 = select i1 %b, i1 %not, i1 false