[SimplifyCFG] FoldTwoEntryPHINode(): don't bailout on i1 PHI's if we can hoist a 'not' from incoming values

[lebedev.ri]

Summary

As it can be seen in the tests in D65143, even though we have formed an '@llvm.umul.with.overflow'
and got rid of potential for division-by-zero, the control flow remains, we still have that branch.

We have this condition:

// Don't fold i1 branches on PHIs which contain binary operators
// These can often be turned into switches and other things.
if (PN->getType()->isIntegerTy(1) &&
    (isa<BinaryOperator>(PN->getIncomingValue(0)) ||
     isa<BinaryOperator>(PN->getIncomingValue(1)) ||
     isa<BinaryOperator>(IfCond)))
  return false;

which was added back in rL121764 to help with select formation i think?

That check prevents us to flatten the CFG here, even though we know
we no longer need that guard and will be able to drop everything
but the '@llvm.umul.with.overflow' + not.

As it can be seen from tests, we end here because the not is being
sinked into the PHI's incoming values by InstCombine,
so we can't workaround this by hoisting it to after PHI.

Thus i suggest that we relax that check to not bailout if we'd get to hoist the not.

[lebedev.ri]

To be noted, i'm fixing this function in particular because it is the pass that folds the case witout not, in -O3
(llvm/test/Transforms/PhaseOrdering/unsigned-multiply-overflow-check.ll, will_not_overflow()).
I suppose the alternative approach would be to teach some other pass that it is okay to hoist this @llvm.umul.with.overflow here.

[lebedev.ri]

ping

[spatel]

This looks like a safe easing of the heuristic, so LGTM.
It would be nice if we could lift "IsFreeToInvert()" from InstCombine to some common location and reuse that here as a follow-up. That function goes further than what is proposed here, and I'm not sure how the extra clauses will interact with SimplifyCFG, so that requires some extra tests to see if it behaving as intended in relation this heuristic.

[lebedev.ri]

In D65147#1608214, @spatel wrote:

This looks like a safe easing of the heuristic, so LGTM.

Thank you for the review.

It would be nice if we could lift "IsFreeToInvert()" from InstCombine to some common location and reuse that here as a follow-up. That function goes further than what is proposed here, and I'm not sure how the extra clauses will interact with SimplifyCFG, so that requires some extra tests to see if it behaving as intended in relation this heuristic.

Yeah, they do similar things, but indeed it isn't obvious if it would be a good fit here.

[lebedev.ri]

Rebased, NFC.

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

static bool FoldTwoEntryPHINode(PHINode *PN, const TargetTransformInfo &TTI,
   }
 
   // If we folded the first phi, PN dangles at this point.  Refresh it.  If
   // we ran out of PHIs then we simplified them all.
   PN = dyn_cast<PHINode>(BB->begin());
   if (!PN)
     return true;
 
-  // Don't fold i1 branches on PHIs which contain binary operators.  These can
-  // often be turned into switches and other things.
+  // Return true if at least one of these is a 'not', and another is either
+  // a 'not' too, or a constant.
+  auto CanHoistNotFromBothValues = [](Value *V0, Value *V1) {
+    if (!match(V0, m_Not(m_Value())))
+      std::swap(V0, V1);
+    auto Invertible = m_CombineOr(m_Not(m_Value()), m_AnyIntegralConstant());
+    return match(V0, m_Not(m_Value())) && match(V1, Invertible);
+  };
+
+  // Don't fold i1 branches on PHIs which contain binary operators, unless one
+  // of the incoming values is an 'not' and another one is freely invertible.
+  // These can often be turned into switches and other things.
   if (PN->getType()->isIntegerTy(1) &&
       (isa<BinaryOperator>(PN->getIncomingValue(0)) ||
        isa<BinaryOperator>(PN->getIncomingValue(1)) ||
-       isa<BinaryOperator>(IfCond)))
+       isa<BinaryOperator>(IfCond)) &&
+      !CanHoistNotFromBothValues(PN->getIncomingValue(0),
+                                 PN->getIncomingValue(1)))
     return false;
 
   // If all PHI nodes are promotable, check to make sure that all instructions
   // in the predecessor blocks can be promoted as well. If not, we won't be able
   // to get rid of the control flow, so it's not worth promoting to select
   // instructions.
   BasicBlock *DomBlock = nullptr;
   BasicBlock *IfBlock1 = PN->getIncomingBlock(0);

llvm/test/Transforms/PhaseOrdering/unsigned-multiply-overflow-check.ll

 ; SIMPLIFYCFG-NEXT:    [[T3:%.*]] = udiv i64 -1, [[ARG]]
 ; SIMPLIFYCFG-NEXT:    [[T4:%.*]] = icmp ult i64 [[T3]], [[ARG1:%.*]]
 ; SIMPLIFYCFG-NEXT:    br label [[BB5]]
 ; SIMPLIFYCFG:       bb5:
 ; SIMPLIFYCFG-NEXT:    [[T6:%.*]] = phi i1 [ false, [[BB:%.*]] ], [ [[T4]], [[BB2]] ]
 ; SIMPLIFYCFG-NEXT:    [[T7:%.*]] = xor i1 [[T6]], true
 ; SIMPLIFYCFG-NEXT:    ret i1 [[T7]]
 ;
-; INSTCOMBINE-LABEL: @will_overflow(
-; INSTCOMBINE-NEXT:  bb:
-; INSTCOMBINE-NEXT:    [[T0:%.*]] = icmp eq i64 [[ARG:%.*]], 0
-; INSTCOMBINE-NEXT:    br i1 [[T0]], label [[BB5:%.*]], label [[BB2:%.*]]
-; INSTCOMBINE:       bb2:
-; INSTCOMBINE-NEXT:    [[UMUL:%.*]] = call { i64, i1 } @llvm.umul.with.overflow.i64(i64 [[ARG]], i64 [[ARG1:%.*]])
-; INSTCOMBINE-NEXT:    [[UMUL_OV:%.*]] = extractvalue { i64, i1 } [[UMUL]], 1
-; INSTCOMBINE-NEXT:    [[PHITMP:%.*]] = xor i1 [[UMUL_OV]], true
-; INSTCOMBINE-NEXT:    br label [[BB5]]
-; INSTCOMBINE:       bb5:
-; INSTCOMBINE-NEXT:    [[T6:%.*]] = phi i1 [ true, [[BB:%.*]] ], [ [[PHITMP]], [[BB2]] ]
-; INSTCOMBINE-NEXT:    ret i1 [[T6]]
+; INSTCOMBINEONLY-LABEL: @will_overflow(
+; INSTCOMBINEONLY-NEXT:  bb:
+; INSTCOMBINEONLY-NEXT:    [[T0:%.*]] = icmp eq i64 [[ARG:%.*]], 0
+; INSTCOMBINEONLY-NEXT:    br i1 [[T0]], label [[BB5:%.*]], label [[BB2:%.*]]
+; INSTCOMBINEONLY:       bb2:
+; INSTCOMBINEONLY-NEXT:    [[UMUL:%.*]] = call { i64, i1 } @llvm.umul.with.overflow.i64(i64 [[ARG]], i64 [[ARG1:%.*]])
+; INSTCOMBINEONLY-NEXT:    [[UMUL_OV:%.*]] = extractvalue { i64, i1 } [[UMUL]], 1
+; INSTCOMBINEONLY-NEXT:    [[PHITMP:%.*]] = xor i1 [[UMUL_OV]], true
+; INSTCOMBINEONLY-NEXT:    br label [[BB5]]
+; INSTCOMBINEONLY:       bb5:
+; INSTCOMBINEONLY-NEXT:    [[T6:%.*]] = phi i1 [ true, [[BB:%.*]] ], [ [[PHITMP]], [[BB2]] ]
+; INSTCOMBINEONLY-NEXT:    ret i1 [[T6]]
+;
+; INSTCOMBINESIMPLIFYCFGDEFAULT-LABEL: @will_overflow(
+; INSTCOMBINESIMPLIFYCFGDEFAULT-NEXT:  bb:
+; INSTCOMBINESIMPLIFYCFGDEFAULT-NEXT:    [[T0:%.*]] = icmp eq i64 [[ARG:%.*]], 0
+; INSTCOMBINESIMPLIFYCFGDEFAULT-NEXT:    br i1 [[T0]], label [[BB5:%.*]], label [[BB2:%.*]]
+; INSTCOMBINESIMPLIFYCFGDEFAULT:       bb2:
+; INSTCOMBINESIMPLIFYCFGDEFAULT-NEXT:    [[UMUL:%.*]] = call { i64, i1 } @llvm.umul.with.overflow.i64(i64 [[ARG]], i64 [[ARG1:%.*]])
+; INSTCOMBINESIMPLIFYCFGDEFAULT-NEXT:    [[UMUL_OV:%.*]] = extractvalue { i64, i1 } [[UMUL]], 1
+; INSTCOMBINESIMPLIFYCFGDEFAULT-NEXT:    [[PHITMP:%.*]] = xor i1 [[UMUL_OV]], true
+; INSTCOMBINESIMPLIFYCFGDEFAULT-NEXT:    br label [[BB5]]
+; INSTCOMBINESIMPLIFYCFGDEFAULT:       bb5:
+; INSTCOMBINESIMPLIFYCFGDEFAULT-NEXT:    [[T6:%.*]] = phi i1 [ true, [[BB:%.*]] ], [ [[PHITMP]], [[BB2]] ]
+; INSTCOMBINESIMPLIFYCFGDEFAULT-NEXT:    ret i1 [[T6]]
+;
+; INSTCOMBINESIMPLIFYCFGCOSTLYONLY-LABEL: @will_overflow(
+; INSTCOMBINESIMPLIFYCFGCOSTLYONLY-NEXT:  bb:
+; INSTCOMBINESIMPLIFYCFGCOSTLYONLY-NEXT:    [[T0:%.*]] = icmp eq i64 [[ARG:%.*]], 0
+; INSTCOMBINESIMPLIFYCFGCOSTLYONLY-NEXT:    [[UMUL:%.*]] = call { i64, i1 } @llvm.umul.with.overflow.i64(i64 [[ARG]], i64 [[ARG1:%.*]])
+; INSTCOMBINESIMPLIFYCFGCOSTLYONLY-NEXT:    [[UMUL_OV:%.*]] = extractvalue { i64, i1 } [[UMUL]], 1
+; INSTCOMBINESIMPLIFYCFGCOSTLYONLY-NEXT:    [[PHITMP:%.*]] = xor i1 [[UMUL_OV]], true
+; INSTCOMBINESIMPLIFYCFGCOSTLYONLY-NEXT:    [[T6:%.*]] = select i1 [[T0]], i1 true, i1 [[PHITMP]]
+; INSTCOMBINESIMPLIFYCFGCOSTLYONLY-NEXT:    ret i1 [[T6]]
+;
+; INSTCOMBINESIMPLIFYCFGCOSTLYINSTCOMBINE-LABEL: @will_overflow(
+; INSTCOMBINESIMPLIFYCFGCOSTLYINSTCOMBINE-NEXT:  bb:
+; INSTCOMBINESIMPLIFYCFGCOSTLYINSTCOMBINE-NEXT:    [[T0:%.*]] = icmp eq i64 [[ARG:%.*]], 0
+; INSTCOMBINESIMPLIFYCFGCOSTLYINSTCOMBINE-NEXT:    [[UMUL:%.*]] = call { i64, i1 } @llvm.umul.with.overflow.i64(i64 [[ARG]], i64 [[ARG1:%.*]])
+; INSTCOMBINESIMPLIFYCFGCOSTLYINSTCOMBINE-NEXT:    [[UMUL_OV:%.*]] = extractvalue { i64, i1 } [[UMUL]], 1
+; INSTCOMBINESIMPLIFYCFGCOSTLYINSTCOMBINE-NEXT:    [[PHITMP:%.*]] = xor i1 [[UMUL_OV]], true
+; INSTCOMBINESIMPLIFYCFGCOSTLYINSTCOMBINE-NEXT:    [[T6:%.*]] = or i1 [[T0]], [[PHITMP]]
+; INSTCOMBINESIMPLIFYCFGCOSTLYINSTCOMBINE-NEXT:    ret i1 [[T6]]
 ;
 bb:
   %t0 = icmp eq i64 %arg, 0
   br i1 %t0, label %bb5, label %bb2
 
 bb2:                                              ; preds = %bb
   %t3 = udiv i64 -1, %arg
   %t4 = icmp ult i64 %t3, %arg1
   br label %bb5
 
 bb5:                                              ; preds = %bb2, %bb
   %t6 = phi i1 [ false, %bb ], [ %t4, %bb2 ]
   %t7 = xor i1 %t6, true
   ret i1 %t7
 }

llvm/test/Transforms/SimplifyCFG/unsigned-multiplication-will-overflow.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -simplifycfg -S | FileCheck %s --check-prefixes=ALL,DEFAULT,FALLBACK0
 ; RUN: opt < %s -simplifycfg -phi-node-folding-threshold=2 -S | FileCheck %s --check-prefixes=ALL,DEFAULT,FALLBACK1
 ; RUN: opt < %s -simplifycfg -phi-node-folding-threshold=3 -S | FileCheck %s --check-prefixes=ALL,COSTLY
 
 ; This is checking that the multiplication does overflow, with a leftover
 ; guard against division-by-zero that was needed before InstCombine
 ; produced llvm.umul.with.overflow.
 
 define i1 @will_overflow(i64 %size, i64 %nmemb) {
-; ALL-LABEL: @will_overflow(
-; ALL-NEXT:  entry:
-; ALL-NEXT:    [[CMP:%.*]] = icmp eq i64 [[SIZE:%.*]], 0
-; ALL-NEXT:    br i1 [[CMP]], label [[LAND_END:%.*]], label [[LAND_RHS:%.*]]
-; ALL:       land.rhs:
-; ALL-NEXT:    [[UMUL:%.*]] = tail call { i64, i1 } @llvm.umul.with.overflow.i64(i64 [[SIZE]], i64 [[NMEMB:%.*]])
-; ALL-NEXT:    [[UMUL_OV:%.*]] = extractvalue { i64, i1 } [[UMUL]], 1
-; ALL-NEXT:    [[UMUL_NOT_OV:%.*]] = xor i1 [[UMUL_OV]], true
-; ALL-NEXT:    br label [[LAND_END]]
-; ALL:       land.end:
-; ALL-NEXT:    [[TMP0:%.*]] = phi i1 [ true, [[ENTRY:%.*]] ], [ [[UMUL_NOT_OV]], [[LAND_RHS]] ]
-; ALL-NEXT:    ret i1 [[TMP0]]
+; DEFAULT-LABEL: @will_overflow(
+; DEFAULT-NEXT:  entry:
+; DEFAULT-NEXT:    [[CMP:%.*]] = icmp eq i64 [[SIZE:%.*]], 0
+; DEFAULT-NEXT:    br i1 [[CMP]], label [[LAND_END:%.*]], label [[LAND_RHS:%.*]]
+; DEFAULT:       land.rhs:
+; DEFAULT-NEXT:    [[UMUL:%.*]] = tail call { i64, i1 } @llvm.umul.with.overflow.i64(i64 [[SIZE]], i64 [[NMEMB:%.*]])
+; DEFAULT-NEXT:    [[UMUL_OV:%.*]] = extractvalue { i64, i1 } [[UMUL]], 1
+; DEFAULT-NEXT:    [[UMUL_NOT_OV:%.*]] = xor i1 [[UMUL_OV]], true
+; DEFAULT-NEXT:    br label [[LAND_END]]
+; DEFAULT:       land.end:
+; DEFAULT-NEXT:    [[TMP0:%.*]] = phi i1 [ true, [[ENTRY:%.*]] ], [ [[UMUL_NOT_OV]], [[LAND_RHS]] ]
+; DEFAULT-NEXT:    ret i1 [[TMP0]]
+;
+; COSTLY-LABEL: @will_overflow(
+; COSTLY-NEXT:  entry:
+; COSTLY-NEXT:    [[CMP:%.*]] = icmp eq i64 [[SIZE:%.*]], 0
+; COSTLY-NEXT:    [[UMUL:%.*]] = tail call { i64, i1 } @llvm.umul.with.overflow.i64(i64 [[SIZE]], i64 [[NMEMB:%.*]])
+; COSTLY-NEXT:    [[UMUL_OV:%.*]] = extractvalue { i64, i1 } [[UMUL]], 1
+; COSTLY-NEXT:    [[UMUL_NOT_OV:%.*]] = xor i1 [[UMUL_OV]], true
+; COSTLY-NEXT:    [[TMP0:%.*]] = select i1 [[CMP]], i1 true, i1 [[UMUL_NOT_OV]]
+; COSTLY-NEXT:    ret i1 [[TMP0]]
 ;
 entry:
   %cmp = icmp eq i64 %size, 0
   br i1 %cmp, label %land.end, label %land.rhs
 
 land.rhs:                                         ; preds = %entry
   %umul = tail call { i64, i1 } @llvm.umul.with.overflow.i64(i64 %size, i64 %nmemb)
   %umul.ov = extractvalue { i64, i1 } %umul, 1