[WIP][SimplifyCFG] Replace FoldTwoEntryPHINode i1 hack with a different hack.

[efriedma]

Summary

Both of these hacks are designed to handle @test9 in llvm/test/Transforms/SimplifyCFG/switch_create.ll (and a duplicate copy of the test in switch_create-custom-dl.ll). There are side-effects on a couple other tests, but nothing really significant, as far as I can tell, except for two-entry-phi-node.ll.

The new test two-entry-phi-node.ll seems to test i1 heuristic itself, but doesn't really give any hint why we want that heuristic.

I'd appreciate any feedback if this makes sense, or if anyone has testcases that showcase the practical effects of the heuristic. I have an internal testcase where killing off the i1 heuristic helps, but it's not in a state where I can post it.

(See also discussion at https://reviews.llvm.org/rG5419b671375c)

[lebedev.ri]

I like this, it's far less fragile,
but as https://bugs.llvm.org/show_bug.cgi?id=51149 reports,
there are some bad performance concerns with FoldTwoEntryPHINode,
and in fact i just tuned/fixed heuristic in rG7ef6f019090f3979fa345105b9ac95ac589c6cf9
to workaround them.

Presumably FoldTwoEntryPHINode is missing some other profitability check.
Not sure about plain build, but we could at least try to use branch weights.

[efriedma]

As far as I can tell, there's nothing specifically wrong with flattening i1 values. Maybe we're slightly underestimating the cost of some of these i1 logic ops on x86? The more general issue is some combination of flattening the CFG too aggressively, and not unflattening aggressively enough before SelectionDAG, I think. Unfortunately, that's a delicate area to mess with; any change will inevitably break something.

[lebedev.ri]

In D106593#2898008, @efriedma wrote:

As far as I can tell, there's nothing specifically wrong with flattening i1 values. Maybe we're slightly underestimating the cost of some of these i1 logic ops on x86? The more general issue is some combination of flattening the CFG too aggressively, and not unflattening aggressively enough before SelectionDAG, I think. Unfortunately, that's a delicate area to mess with; any change will inevitably break something.

I agree with everything said above.

[efriedma]

I guess, then, the question is what order we want to do things in. Do we land this essentially as-is, then try to come up with a more reliable way to handle the cases that fall out? Or do we put this on hold until we have improvements to cost estimation and/or CFG unflattening?

[lebedev.ri]

In D106593#2898508, @efriedma wrote:

I guess, then, the question is what order we want to do things in. Do we land this essentially as-is, then try to come up with a more reliable way to handle the cases that fall out? Or do we put this on hold until we have improvements to cost estimation and/or CFG unflattening?

If this goes in as-is right now, @wmi will re-raise https://bugs.llvm.org/show_bug.cgi?id=51149
If that's fine, then let's do it, else i guess we need to try to do some legwork first.
Let me see if i can add some branch weights checks to these transforms first.

[lebedev.ri]

Since we'll probably be unfortunate enough to have to deal with perf regressions anyways,
my plan is to merge FoldTwoEntryPHINode and SpeculativelyExecuteBB enhancing their collective functionality
and dropping the hacks.

[efriedma]

This is obsolete, I think.

[lebedev.ri]

In D106593#3357676, @efriedma wrote:

This is obsolete, I think.

Funny enough, i just looked at removing that hack yesterday, and it breaks quite a lot of tests,
including that one phase ordering one about function merging.

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

class SimplifyCFGOpt {
   bool SimplifyTerminatorOnSelect(Instruction *OldTerm, Value *Cond,
                                   BasicBlock *TrueBB, BasicBlock *FalseBB,
                                   uint32_t TrueWeight, uint32_t FalseWeight);
   bool SimplifyBranchOnICmpChain(BranchInst *BI, IRBuilder<> &Builder,
                                  const DataLayout &DL);
   bool SimplifySwitchOnSelect(SwitchInst *SI, SelectInst *Select);
   bool SimplifyIndirectBrOnSelect(IndirectBrInst *IBI, SelectInst *SI);
   bool TurnSwitchRangeIntoICmp(SwitchInst *SI, IRBuilder<> &Builder);
+  bool FoldTwoEntryPHINode(PHINode *PN, IRBuilder<> &FoldingBuilder);
 
 public:
   SimplifyCFGOpt(const TargetTransformInfo &TTI, DomTreeUpdater *DTU,
                  const DataLayout &DL, ArrayRef<WeakVH> LoopHeaders,
                  const SimplifyCFGOptions &Opts)
       : TTI(TTI), DTU(DTU), DL(DL), LoopHeaders(LoopHeaders), Options(Opts) {
     assert((!DTU || !DTU->hasPostDomTree()) &&
            "SimplifyCFG is not yet capable of maintaining validity of a "
for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
     return FoldCondBranchOnPHI(BI, DTU, DL, AC) || true;
   }
 
   return false;
 }
 
 /// Given a BB that starts with the specified two-entry PHI node,
 /// see if we can eliminate it.
-static bool FoldTwoEntryPHINode(PHINode *PN, const TargetTransformInfo &TTI,
-                                DomTreeUpdater *DTU, const DataLayout &DL) {
+bool SimplifyCFGOpt::FoldTwoEntryPHINode(PHINode *PN, IRBuilder<> &FoldingBuilder) {
   // Ok, this is a two entry PHI node.  Check to see if this is a simple "if
   // statement", which has a very simple dominance structure.  Basically, we
   // are trying to find the condition that is being branched on, which
   // subsequently causes this merge to happen.  We really want control
   // dependence information for this check, but simplifycfg can't keep it up
   // to date, and this catches most of the cases we care about anyway.
   BasicBlock *BB = PN->getParent();
 
bool SimplifyCFGOpt::FoldTwoEntryPHINode(PHINode *PN, IRBuilder<> &FoldingBuilder) {
   }
 
   // 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;
 
-  // 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 or
-  // (possibly inverted) select form of or/ands,  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.
-  auto IsBinOpOrAnd = [](Value *V) {
-    return match(
-        V, m_CombineOr(
-               m_BinOp(),
-               m_CombineOr(m_Select(m_Value(), m_ImmConstant(), m_Value()),
-                           m_Select(m_Value(), m_Value(), m_ImmConstant()))));
-  };
-  if (PN->getType()->isIntegerTy(1) &&
-      (IsBinOpOrAnd(PN->getIncomingValue(0)) ||
-       IsBinOpOrAnd(PN->getIncomingValue(1)) || IsBinOpOrAnd(IfCond)) &&
-      !CanHoistNotFromBothValues(PN->getIncomingValue(0),
-                                 PN->getIncomingValue(1)))
-    return Changed;
-
   // 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);
   BasicBlock *IfBlock2 = PN->getIncomingBlock(1);
   if (cast<BranchInst>(IfBlock1->getTerminator())->isConditional()) {
for (BasicBlock::iterator I = IfBlock2->begin(); !I->isTerminator(); ++I)
         // This is not an aggressive instruction that we can promote.
         // Because of this, we won't be able to get rid of the control flow, so
         // the xform is not worth it.
         return Changed;
       }
   }
   assert(DomBlock && "Failed to find root DomBlock");
 
+  if (BranchInst *DomBI = dyn_cast<BranchInst>(DomBlock->getTerminator())) {
+    // Prefer to form a switch instruction over flattening an if statement.
+    if (Options.SimplifyCondBranch && DomBI->isConditional() &&
+        SimplifyBranchOnICmpChain(DomBI, FoldingBuilder, DL))
+      return true;
+  }
+
   // If either of the blocks has it's address taken, we can't do this fold.
   if ((IfBlock1 && IfBlock1->hasAddressTaken()) ||
       (IfBlock2 && IfBlock2->hasAddressTaken()))
     return Changed;
 
   LLVM_DEBUG(dbgs() << "FOUND IF CONDITION!  " << *IfCond
                     << "  T: " << IfTrue->getName()
                     << "  F: " << IfFalse->getName() << "\n");
bool SimplifyCFGOpt::simplifyOnceImpl(BasicBlock *BB) {
 
   IRBuilder<> Builder(BB);
 
   if (Options.FoldTwoEntryPHINode) {
     // If there is a trivial two-entry PHI node in this basic block, and we can
     // eliminate it, do so now.
     if (auto *PN = dyn_cast<PHINode>(BB->begin()))
       if (PN->getNumIncomingValues() == 2)
-        Changed |= FoldTwoEntryPHINode(PN, TTI, DTU, DL);
+        Changed |= FoldTwoEntryPHINode(PN, Builder);
   }
 
   Instruction *Terminator = BB->getTerminator();
   Builder.SetInsertPoint(Terminator);
   switch (Terminator->getOpcode()) {
   case Instruction::Br:
     Changed |= simplifyBranch(cast<BranchInst>(Terminator), Builder);
     break;

llvm/test/CodeGen/Hexagon/pred-simp.ll

-; RUN: llc -march=hexagon -O2 < %s | FileCheck %s
-; CHECK-NOT: not(
-
-target triple = "hexagon"
-
-; Function Attrs: nounwind readnone
-define i32 @f0(i32 %a0, i32 %a1) #0 {
-b0:
-  %v0 = icmp slt i32 %a0, %a1
-  %v1 = add nsw i32 %a1, %a0
-  %v2 = icmp sgt i32 %v1, 10
-  %v3 = icmp eq i1 %v0, false
-  %v4 = or i1 %v3, %v2
-  br i1 %v4, label %b2, label %b1
-
-b1:                                               ; preds = %b0
-  %v5 = mul nsw i32 %a0, 2
-  %v6 = icmp sgt i32 %v5, %a1
-  br label %b2
-
-b2:                                               ; preds = %b1, %b0
-  %v7 = phi i1 [ %v6, %b1 ], [ true, %b0 ]
-  %v8 = zext i1 %v7 to i32
-  ret i32 %v8
-}
-
-attributes #0 = { nounwind readnone }

llvm/test/Transforms/PhaseOrdering/X86/vector-reductions.ll

 ; CHECK-LABEL: @cmp_lt_gt(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[FNEG:%.*]] = fneg double [[B:%.*]]
 ; CHECK-NEXT:    [[ADD:%.*]] = fsub double [[C:%.*]], [[B]]
 ; CHECK-NEXT:    [[MUL:%.*]] = fmul double [[A:%.*]], 2.000000e+00
 ; CHECK-NEXT:    [[DIV:%.*]] = fdiv double [[ADD]], [[MUL]]
 ; CHECK-NEXT:    [[SUB:%.*]] = fsub double [[FNEG]], [[C]]
 ; CHECK-NEXT:    [[DIV3:%.*]] = fdiv double [[SUB]], [[MUL]]
-; CHECK-NEXT:    [[CMP:%.*]] = fcmp olt double [[DIV]], 0x3EB0C6F7A0B5ED8D
-; CHECK-NEXT:    [[CMP4:%.*]] = fcmp olt double [[DIV3]], 0x3EB0C6F7A0B5ED8D
-; CHECK-NEXT:    [[OR_COND:%.*]] = select i1 [[CMP]], i1 [[CMP4]], i1 false
-; CHECK-NEXT:    br i1 [[OR_COND]], label [[COMMON_RET:%.*]], label [[LOR_LHS_FALSE:%.*]]
-; CHECK:       common.ret:
-; CHECK-NEXT:    [[COMMON_RET_OP:%.*]] = phi i1 [ [[OR_COND1:%.*]], [[LOR_LHS_FALSE]] ], [ false, [[ENTRY:%.*]] ]
-; CHECK-NEXT:    ret i1 [[COMMON_RET_OP]]
-; CHECK:       lor.lhs.false:
+; CHECK-NEXT:    [[CMP:%.*]] = fcmp uge double [[DIV]], 0x3EB0C6F7A0B5ED8D
+; CHECK-NEXT:    [[CMP4:%.*]] = fcmp uge double [[DIV3]], 0x3EB0C6F7A0B5ED8D
+; CHECK-NEXT:    [[OR_COND:%.*]] = select i1 [[CMP]], i1 true, i1 [[CMP4]]
 ; CHECK-NEXT:    [[CMP5:%.*]] = fcmp ule double [[DIV]], 1.000000e+00
 ; CHECK-NEXT:    [[CMP7:%.*]] = fcmp ule double [[DIV3]], 1.000000e+00
-; CHECK-NEXT:    [[OR_COND1]] = select i1 [[CMP5]], i1 true, i1 [[CMP7]]
-; CHECK-NEXT:    br label [[COMMON_RET]]
+; CHECK-NEXT:    [[OR_COND1:%.*]] = select i1 [[CMP5]], i1 true, i1 [[CMP7]]
+; CHECK-NEXT:    [[COMMON_RET_OP:%.*]] = select i1 [[OR_COND]], i1 [[OR_COND1]], i1 false
+; CHECK-NEXT:    ret i1 [[COMMON_RET_OP]]
 ;
 entry:
   %fneg = fneg double %b
   %add = fadd double %fneg, %c
   %mul = fmul double 2.0, %a
   %div = fdiv double %add, %mul
   %fneg1 = fneg double %b
   %sub = fsub double %fneg1, %c

llvm/test/Transforms/SimplifyCFG/two-entry-phi-node.ll

+; XFAIL: *
 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -S -simplifycfg -simplifycfg-require-and-preserve-domtree=1 | FileCheck %s
 
 declare void @sideeffect0()
 declare void @sideeffect1()
 declare void @sideeffect2()
 declare void @use8(i8)
 declare i1 @gen1()