[InstCombine] Simplify boolean Phis with const inputs using CFG

[mkazantsev]

Summary

This patch adds simplification for pattern:

  if (cond)
  /       \
 ...      ...
  \       /
p = phi [true] [false]
...
br p, succ_1, succ_2

If we can prove that top block's branches dominate respective
inputs of a block that has a Phi with constant inputs, we can
use the branch condition (maybe inverted) instead of Phi.
This will make proofs of implication for further jump threading
more transparent.

[mkazantsev]

Found some bugs internally, need to investigate.

[mkazantsev]

False alarm.

[xbolva00]

llvm/test/Transforms/InstCombine/select.ll

512 ↗

(On Diff #269518)

Regressed

llvm/test/Transforms/PhaseOrdering/inlining-alignment-assumptions.ll

43 ↗

(On Diff #269518)

Unwanted

[mkazantsev]

Some underlying transforms are missing it seems.

llvm/test/Transforms/InstCombine/select.ll

512 ↗

(On Diff #269518)

Because we are missing the respective transform for select. I can implement it first I guess...

[mkazantsev]

llvm/test/Transforms/PhaseOrdering/inlining-alignment-assumptions.ll

43 ↗

(On Diff #269518)

SimplifyCFG does something stupid here it seems. Not related to InstCombine.

[mkazantsev]

llvm/test/Transforms/PhaseOrdering/inlining-alignment-assumptions.ll

43 ↗

(On Diff #269518)

Added a test on that:

./test/Transforms/SimplifyCFG/unprofitable-pr.ll

SimplifyCFG bases its choice on block size, and sometimes does something particularly stupid.

[mkazantsev]

llvm/test/Transforms/PhaseOrdering/inlining-alignment-assumptions.ll

43 ↗

(On Diff #269518)

Fixed at https://reviews.llvm.org/D81835

[mkazantsev]

Fixed underlying bug, limited transform for branch/ret arguments only (yet it might be expanded further).

[nikic]

Why is this being limited to phis used in ret and br?

[mkazantsev]

In D81375#2096608, @nikic wrote:

Why is this being limited to phis used in ret and br?

There is a problem with selects:

  if (cond)
  /       \
 ...      ...
  \       /
p = phi [true] [false]
s = select p, v1, v2

The way how InstCombine currently works will turn it into

  if (cond)
  /       \
 ...      ...
  \       /
s = select cond, v1, v2

instead of

  if (cond)
  /       \
 ...      ...
  \       /
s = phi [v1] [v2]

This limitation is temporarily, until we know how to fix this (and maybe other similar) cases.

[mkazantsev]

Maybe it makes sense to implement transform for select first, and then lift limitation on branches & returns.

[mkazantsev]

@nikic please take a look at https://reviews.llvm.org/D82005. I will repace this one on top of it once it's merged, so we should no longer have problems with selects.

[mkazantsev]

Rebased on top of underlying fixes.

[xbolva00]

llvm/test/Transforms/InstCombine/simple_phi_condition.ll

4

Remove

[nikic]

Now that the other issues have been fixed, change this back to start at the phi node, rather than return/branch?

[mkazantsev]

Err, you're right @nikic. Will do.

[mkazantsev]

Still missing cases found for selects... It's getting not worth it.

[mkazantsev]

At least 2 another transforms for selects are missing that we need to avoid regressions. I'm depreoritizing this as these efforts don't pay off.

[mkazantsev]

At last!

[xbolva00]

Looks nice!

[mkazantsev]

Looks like some clang tests need update too...

[mkazantsev]

One of clang tests shown that we are still missing some case...

[mkazantsev]

SimplifyCFG's attempts to perform PR are outrageously stupid. It re-inserts (worse version of) removed Phi in order to perform threading, but does not actually thread. I'll fix it separately, it's not blocking this one (it inserts phi anyway, just now it's worse).

[mkazantsev]

Follow-up fix for one of clang tests: https://reviews.llvm.org/D83936

[kazu]

Would you mind if I revert this patch temporarily? This patch makes it easier to trigger bugs like https://bugs.llvm.org/show_bug.cgi?id=46940. Although I don't think this patch itself is the root cause, reverting this patch would allow me to fix the bug above while the compiler is in a more usable state. Thanks!

llvm/include/llvm/IR/Dominators.h

public:
   bool dominates(const Instruction *Def, const BasicBlock *BB) const;
 
   /// Return true if an edge dominates a use.
   ///
   /// If BBE is not a unique edge between start and end of the edge, it can
   /// never dominate the use.
   bool dominates(const BasicBlockEdge &BBE, const Use &U) const;
   bool dominates(const BasicBlockEdge &BBE, const BasicBlock *BB) const;
+  /// Returns true if edge \p BBE1 dominates edge \p BBE2.
+  bool dominates(const BasicBlockEdge &BBE1, const BasicBlockEdge &BBE2) const;
 
   // Ensure base class overloads are visible.
   using Base::isReachableFromEntry;
 
   /// Provide an overload for a Use.
   bool isReachableFromEntry(const Use &U) const;
 
   // Pop up a GraphViz/gv window with the Dominator Tree rendered using `dot`.

llvm/lib/IR/Dominators.cpp

bool DominatorTree::isReachableFromEntry(const Use &U) const {
   // PHI nodes use their operands on their incoming edges.
   if (PHINode *PN = dyn_cast<PHINode>(I))
     return isReachableFromEntry(PN->getIncomingBlock(U));
 
   // Everything else uses their operands in their own block.
   return isReachableFromEntry(I->getParent());
 }
 
+// Edge BBE1 dominates edge BBE2 if they match or BBE1 dominates start of BBE2.
+bool DominatorTree::dominates(const BasicBlockEdge &BBE1,
+                              const BasicBlockEdge &BBE2) const {
+  if (BBE1.getStart() == BBE2.getStart() && BBE1.getEnd() == BBE2.getEnd())
+    return true;
+  return dominates(BBE1, BBE2.getStart());
+}
+
 //===----------------------------------------------------------------------===//
 //  DominatorTreeAnalysis and related pass implementations
 //===----------------------------------------------------------------------===//
 //
 // This implements the DominatorTreeAnalysis which is used with the new pass
 // manager. It also implements some methods from utility passes.
 //
 //===----------------------------------------------------------------------===//

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

 }
 
 static bool isMustTailCall(Value *V) {
   if (auto *CI = dyn_cast<CallInst>(V))
     return CI->isMustTailCall();
   return false;
 }
 
+static Value *SimplifyUsingControlFlow(InstCombiner &Self, PHINode &PN,
+                                       const DominatorTree &DT) {
+  // Simplify the following patterns:
+  //       if (cond)
+  //       /       \
+  //      ...      ...
+  //       \       /
+  //    phi [true] [false]
+  if (!PN.getType()->isIntegerTy(1))
+    return nullptr;
+
+  if (PN.getNumOperands() != 2)
+    return nullptr;
+
+  // Make sure all inputs are constants.
+  if (!all_of(PN.operands(), [](Value *V) { return isa<ConstantInt>(V); }))
+    return nullptr;
+
+  BasicBlock *BB = PN.getParent();
+  // Do not bother with unreachable instructions.
+  if (!DT.isReachableFromEntry(BB))
+    return nullptr;
+
+  // Same inputs.
+  if (PN.getOperand(0) == PN.getOperand(1))
+    return PN.getOperand(0);
+
+  BasicBlock *TruePred = nullptr, *FalsePred = nullptr;
+  for (auto *Pred : predecessors(BB)) {
+    auto *Input = cast<ConstantInt>(PN.getIncomingValueForBlock(Pred));
+    if (Input->isAllOnesValue())
+      TruePred = Pred;
+    else
+      FalsePred = Pred;
+  }
+  assert(TruePred && FalsePred && "Must be!");
+
+  // Check which edge of the dominator dominates the true input. If it is the
+  // false edge, we should invert the condition.
+  auto *IDom = DT.getNode(BB)->getIDom()->getBlock();
+  auto *BI = dyn_cast<BranchInst>(IDom->getTerminator());
+  if (!BI || BI->isUnconditional())
+    return nullptr;
+
+  // Check that edges outgoing from the idom's terminators dominate respective
+  // inputs of the Phi.
+  BasicBlockEdge TrueOutEdge(IDom, BI->getSuccessor(0));
+  BasicBlockEdge FalseOutEdge(IDom, BI->getSuccessor(1));
+
+  BasicBlockEdge TrueIncEdge(TruePred, BB);
+  BasicBlockEdge FalseIncEdge(FalsePred, BB);
+
+  auto *Cond = BI->getCondition();
+  if (DT.dominates(TrueOutEdge, TrueIncEdge) &&
+      DT.dominates(FalseOutEdge, FalseIncEdge))
+    // This Phi is actually equivalent to branching condition of IDom.
+    return Cond;
+  else if (DT.dominates(TrueOutEdge, FalseIncEdge) &&
+           DT.dominates(FalseOutEdge, TrueIncEdge)) {
+    // This Phi is actually opposite to branching condition of IDom. We invert
+    // the condition that will potentially open up some opportunities for
+    // sinking.
+    Self.Builder.SetInsertPoint(BB->getFirstNonPHI());
+    return Self.Builder.CreateNot(Cond);
+  }
+
+  return nullptr;
+}
+
 Instruction *InstCombiner::visitReturnInst(ReturnInst &RI) {
   if (RI.getNumOperands() == 0) // ret void
     return nullptr;
 
   Value *ResultOp = RI.getOperand(0);
   Type *VTy = ResultOp->getType();
   if (!VTy->isIntegerTy() || isa<Constant>(ResultOp))
     return nullptr;
 
   // Don't replace result of musttail calls.
   if (isMustTailCall(ResultOp))
     return nullptr;
 
+  // See if we can replace a Phi with constant inputs with condition of another
+  // dominating branch.
+  if (auto *PN = dyn_cast<PHINode>(ResultOp))
+    if (Value *V = SimplifyUsingControlFlow(*this, *PN, DT))
+      return replaceOperand(RI, 0, V);
+
   // There might be assume intrinsics dominating this return that completely
   // determine the value. If so, constant fold it.
   KnownBits Known = computeKnownBits(ResultOp, 0, &RI);
   if (Known.isConstant())
     return replaceOperand(RI, 0,
         Constant::getIntegerValue(VTy, Known.getConstant()));
 
   return nullptr;
if (match(&BI, m_Br(m_OneUse(m_Cmp(Pred, m_Value(), m_Value())),
     // Swap destinations and condition.
     CmpInst *Cond = cast<CmpInst>(BI.getCondition());
     Cond->setPredicate(CmpInst::getInversePredicate(Pred));
     BI.swapSuccessors();
     Worklist.push(Cond);
     return &BI;
   }
 
+  // See if we can replace a Phi with constant inputs with condition of another
+  // dominating branch.
+  if (auto *PN = dyn_cast<PHINode>(BI.getCondition()))
+    if (Value *V = SimplifyUsingControlFlow(*this, *PN, DT))
+      return replaceOperand(BI, 0, V);
+
   return nullptr;
 }
 
 Instruction *InstCombiner::visitSwitchInst(SwitchInst &SI) {
   Value *Cond = SI.getCondition();
   Value *Op0;
   ConstantInt *AddRHS;
   if (match(Cond, m_Add(m_Value(Op0), m_ConstantInt(AddRHS)))) {

llvm/test/Transforms/InstCombine/branch.ll

 ; CHECK-NEXT:    ret i32 [[X:%.*]]
 ;
   %y = icmp eq i32 27, ptrtoint(i8* @global to i32)
   br i1 %y, label %patatino, label %patatino
 patatino:
   ret i32 %x
 }
 
-; TODO: Simplify this to "ret cond".
 define i1 @test01(i1 %cond) {
 ; CHECK-LABEL: @test01(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[COND:%.*]], label [[IF_TRUE_1:%.*]], label [[IF_FALSE_1:%.*]]
 ; CHECK:       if.true.1:
 ; CHECK-NEXT:    br label [[MERGE_1:%.*]]
 ; CHECK:       if.false.1:
 ; CHECK-NEXT:    br label [[MERGE_1]]
 ; CHECK:       merge.1:
-; CHECK-NEXT:    [[MERGE_COND_1:%.*]] = phi i1 [ true, [[IF_TRUE_1]] ], [ false, [[IF_FALSE_1]] ]
-; CHECK-NEXT:    br i1 [[MERGE_COND_1]], label [[IF_TRUE_2:%.*]], label [[IF_FALSE_2:%.*]]
+; CHECK-NEXT:    br i1 [[COND]], label [[IF_TRUE_2:%.*]], label [[IF_FALSE_2:%.*]]
 ; CHECK:       if.true.2:
 ; CHECK-NEXT:    br label [[MERGE_2:%.*]]
 ; CHECK:       if.false.2:
 ; CHECK-NEXT:    br label [[MERGE_2]]
 ; CHECK:       merge.2:
-; CHECK-NEXT:    [[MERGE_COND_2:%.*]] = phi i1 [ true, [[IF_TRUE_2]] ], [ false, [[IF_FALSE_2]] ]
-; CHECK-NEXT:    ret i1 [[MERGE_COND_2]]
+; CHECK-NEXT:    ret i1 [[COND]]
 ;
 entry:
   br i1 %cond, label %if.true.1, label %if.false.1
 
 if.true.1:
   br label %merge.1
 
 if.false.1:

 if.false.2:
   br label  %merge.2
 
 merge.2:
   %merge.cond.2 = phi i1 [true, %if.true.2], [false, %if.false.2]
   ret i1 %merge.cond.2
 }
 
-; TODO: Simplify this to "ret %cond".
 define i1 @test02(i1 %cond) {
 ; CHECK-LABEL: @test02(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[COND:%.*]], label [[IF_TRUE_1:%.*]], label [[IF_FALSE_1:%.*]]
 ; CHECK:       if.true.1:
 ; CHECK-NEXT:    br label [[MERGE_1:%.*]]
 ; CHECK:       if.false.1:
 ; CHECK-NEXT:    br label [[MERGE_1]]
 ; CHECK:       merge.1:
-; CHECK-NEXT:    [[MERGE_COND_1:%.*]] = phi i1 [ false, [[IF_TRUE_1]] ], [ true, [[IF_FALSE_1]] ]
-; CHECK-NEXT:    br i1 [[MERGE_COND_1]], label [[IF_TRUE_2:%.*]], label [[IF_FALSE_2:%.*]]
+; CHECK-NEXT:    br i1 [[COND]], label [[IF_FALSE_2:%.*]], label [[IF_TRUE_2:%.*]]
 ; CHECK:       if.true.2:
 ; CHECK-NEXT:    br label [[MERGE_2:%.*]]
 ; CHECK:       if.false.2:
 ; CHECK-NEXT:    br label [[MERGE_2]]
 ; CHECK:       merge.2:
-; CHECK-NEXT:    [[MERGE_COND_2:%.*]] = phi i1 [ false, [[IF_TRUE_2]] ], [ true, [[IF_FALSE_2]] ]
-; CHECK-NEXT:    ret i1 [[MERGE_COND_2]]
+; CHECK-NEXT:    ret i1 [[COND]]
 ;
 entry:
   br i1 %cond, label %if.true.1, label %if.false.1
 
 if.true.1:
   br label %merge.1
 
 if.false.1:

llvm/test/Transforms/InstCombine/simple_phi_condition.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S < %s -instcombine | FileCheck %s
 ; RUN: opt -S < %s -passes=instcombine | FileCheck %s
 
 ; TODO: Simplify to "ret cond".
 define i1 @test_direct_implication(i1 %cond) {
 ; CHECK-LABEL: @test_direct_implication(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[COND:%.*]], label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]]
 ; CHECK:       if.true:
 ; CHECK-NEXT:    br label [[MERGE:%.*]]
 ; CHECK:       if.false:
 ; CHECK-NEXT:    br label [[MERGE]]
 ; CHECK:       merge:
-; CHECK-NEXT:    [[RET:%.*]] = phi i1 [ true, [[IF_TRUE]] ], [ false, [[IF_FALSE]] ]
-; CHECK-NEXT:    ret i1 [[RET]]
+; CHECK-NEXT:    ret i1 [[COND]]
 ;
 entry:
   br i1 %cond, label %if.true, label %if.false
 
 if.true:
   br label %merge
 
 if.false:

 ; CHECK-LABEL: @test_inverted_implication(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[COND:%.*]], label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]]
 ; CHECK:       if.true:
 ; CHECK-NEXT:    br label [[MERGE:%.*]]
 ; CHECK:       if.false:
 ; CHECK-NEXT:    br label [[MERGE]]
 ; CHECK:       merge:
-; CHECK-NEXT:    [[RET:%.*]] = phi i1 [ false, [[IF_TRUE]] ], [ true, [[IF_FALSE]] ]
-; CHECK-NEXT:    ret i1 [[RET]]
+; CHECK-NEXT:    [[TMP0:%.*]] = xor i1 [[COND]], true
+; CHECK-NEXT:    ret i1 [[TMP0]]
 ;
 entry:
   br i1 %cond, label %if.true, label %if.false
 
 if.true:
   br label %merge
 
 if.false:

 ; CHECK-NEXT:    [[IV1_NEXT]] = add i32 [[IV1]], 1
 ; CHECK-NEXT:    [[LOOP_COND_1:%.*]] = icmp slt i32 [[IV1_NEXT]], [[CNT1:%.*]]
 ; CHECK-NEXT:    br i1 [[LOOP_COND_1]], label [[LOOP1]], label [[IF_TRUE_END:%.*]]
 ; CHECK:       if.true.end:
 ; CHECK-NEXT:    br label [[MERGE:%.*]]
 ; CHECK:       if.false:
 ; CHECK-NEXT:    br label [[MERGE]]
 ; CHECK:       merge:
-; CHECK-NEXT:    [[RET:%.*]] = phi i1 [ true, [[IF_TRUE_END]] ], [ false, [[IF_FALSE]] ]
-; CHECK-NEXT:    ret i1 [[RET]]
+; CHECK-NEXT:    ret i1 [[COND]]
 ;
 entry:
   br i1 %cond, label %if.true, label %if.false
 
 if.true:
   br label %loop1
 
 loop1:

 ; CHECK-NEXT:    [[IV1_NEXT]] = add i32 [[IV1]], 1
 ; CHECK-NEXT:    [[LOOP_COND_1:%.*]] = icmp slt i32 [[IV1_NEXT]], [[CNT1:%.*]]
 ; CHECK-NEXT:    br i1 [[LOOP_COND_1]], label [[LOOP1]], label [[IF_TRUE_END:%.*]]
 ; CHECK:       if.true.end:
 ; CHECK-NEXT:    br label [[MERGE:%.*]]
 ; CHECK:       if.false:
 ; CHECK-NEXT:    br label [[MERGE]]
 ; CHECK:       merge:
-; CHECK-NEXT:    [[RET:%.*]] = phi i1 [ false, [[IF_TRUE_END]] ], [ true, [[IF_FALSE]] ]
-; CHECK-NEXT:    ret i1 [[RET]]
+; CHECK-NEXT:    [[TMP0:%.*]] = xor i1 [[COND]], true
+; CHECK-NEXT:    ret i1 [[TMP0]]
 ;
 entry:
   br i1 %cond, label %if.true, label %if.false
 
 if.true:
   br label %loop1
 
 loop1: