[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–513

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–513

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/lib/Transforms/InstCombine/InstCombinePHI.cpp

Instruction *InstCombiner::SliceUpIllegalIntegerPHI(PHINode &FirstPhi) {
   // Replace all the remaining uses of the PHI nodes (self uses and the lshrs)
   // with undefs.
   Value *Undef = UndefValue::get(FirstPhi.getType());
   for (unsigned i = 1, e = PHIsToSlice.size(); i != e; ++i)
     replaceInstUsesWith(*PHIsToSlice[i], Undef);
   return replaceInstUsesWith(FirstPhi, Undef);
 }
 
+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;
+}
+
 // PHINode simplification
 //
 Instruction *InstCombiner::visitPHINode(PHINode &PN) {
   if (Value *V = SimplifyInstruction(&PN, SQ.getWithInstruction(&PN)))
     return replaceInstUsesWith(PN, V);
 
   if (Instruction *Result = FoldPHIArgZextsIntoPHI(PN))
     return Result;
Instruction *InstCombiner::visitPHINode(PHINode &PN) {
   // it is only used by trunc or trunc(lshr) operations.  If so, we split the
   // PHI into the various pieces being extracted.  This sort of thing is
   // introduced when SROA promotes an aggregate to a single large integer type.
   if (PN.getType()->isIntegerTy() &&
       !DL.isLegalInteger(PN.getType()->getPrimitiveSizeInBits()))
     if (Instruction *Res = SliceUpIllegalIntegerPHI(PN))
       return Res;
 
+  // Ultimately, try to replace this Phi with a dominating condition.
+  if (auto *V = SimplifyUsingControlFlow(*this, PN, DT))
+    return replaceInstUsesWith(PN, V);
+
   return nullptr;
 }

llvm/test/Transforms/CallSiteSplitting/callsite-split.ll

 
 
 ;CHECK-LABEL: @caller2
 ;CHECK-LABEL: Top.split:
 ;CHECK: call void @dummy4()
 ;CHECK-LABEL: NextCond.split:
 ;CHECK: call void @dummy3()
 ;CheCK-LABEL: CallSiteBB:
-;CHECK: %phi.call = phi i1 [ true, %NextCond.split ], [ false, %Top.split ]
-;CHECK: call void @foo(i1 %phi.call)
+;CHECK: [[NEG:%.*]] = xor i1 %tobool1, true
+;CHECK: call void @foo(i1 [[NEG]])
 define void @caller2(i1 %c, %struct.bitmap* %a_elt, %struct.bitmap* %b_elt, %struct.bitmap* %c_elt) {
 entry:
   br label %Top
 
 Top:
   %tobool1 = icmp eq %struct.bitmap* %a_elt, %b_elt
   br i1 %tobool1, label %CallSiteBB, label %NextCond
 

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/icmp-constant-phi.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -instcombine -S | FileCheck %s
 ; RUN: opt < %s -passes=instcombine -S | FileCheck %s
 
 define i1 @test_eq(i1 %cond) {
 ; CHECK-LABEL: @test_eq(
 ; 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:    [[COMPARE:%.*]] = phi i1 [ true, [[IF_FALSE]] ], [ false, [[IF_TRUE]] ]
 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 ; CHECK:       exit:
-; CHECK-NEXT:    ret i1 [[COMPARE]]
+; 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-LABEL: @test_slt(
 ; 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:    [[COMPARE:%.*]] = phi i1 [ false, [[IF_FALSE]] ], [ true, [[IF_TRUE]] ]
 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 ; CHECK:       exit:
-; CHECK-NEXT:    ret i1 [[COMPARE]]
+; 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_ne(
 ; 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:    [[COMPARE:%.*]] = phi i1 [ false, [[IF_FALSE]] ], [ true, [[IF_TRUE]] ]
 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 ; CHECK:       exit:
-; CHECK-NEXT:    ret i1 [[COMPARE]]
+; CHECK-NEXT:    ret i1 [[COND]]
 ;
 entry:
   br i1 %cond, label %if.true, label %if.false
 
 if.true:
   br label %merge
 
 if.false:

llvm/test/Transforms/InstCombine/phi.ll

entry:
     br i1 %a, label %bb1, label %bb2
 
 bb1:        ; preds = %entry
     %0 = tail call i32 @ext()        ; <i32> [#uses=1]
     br label %bb2
 
 bb2:        ; preds = %bb1, %entry
     %cond = phi i1 [ true, %bb1 ], [ false, %entry ]        ; <i1> [#uses=1]
-; CHECK-NOT: %val = phi i32 [ %0, %bb1 ], [ 0, %entry ]
+; CHECK-NOT: phi i1
+; CHECK:     %res = phi i32 [ %0, %bb1 ], [ 0, %entry ]
+; CHECK:     ret i32 %res
     %val = phi i32 [ %0, %bb1 ], [ 0, %entry ]        ; <i32> [#uses=1]
     %res = select i1 %cond, i32 %val, i32 0        ; <i32> [#uses=1]
-; CHECK: ret i32 %cond
     ret i32 %res
 }
 
 define i1 @test18(i1 %cond) {
   %zero = alloca i32
   %one = alloca i32
   br i1 %cond, label %true, label %false
 true:

llvm/test/Transforms/InstCombine/select.ll

 
 define i32 @test25(i1 %c)  {
 ; CHECK-LABEL: @test25(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[JUMP:%.*]], label [[RET:%.*]]
 ; CHECK:       jump:
 ; CHECK-NEXT:    br label [[RET]]
 ; CHECK:       ret:
-; CHECK-NEXT:    [[A:%.*]] = phi i32 [ 10, [[JUMP]] ], [ 20, [[ENTRY:%.*]] ]
-; CHECK-NEXT:    ret i32 [[A]]
+; CHECK-NEXT:    [[B:%.*]] = phi i32 [ 10, [[JUMP]] ], [ 20, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    ret i32 [[B]]
 ;
 entry:
   br i1 %c, label %jump, label %ret
 jump:
   br label %ret
 ret:
   %a = phi i1 [true, %jump], [false, %entry]
   %b = select i1 %a, i32 10, i32 20
   ret i32 %b
 }
 
 define i32 @test26(i1 %cond)  {
 ; CHECK-LABEL: @test26(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[COND:%.*]], label [[JUMP:%.*]], label [[RET:%.*]]
 ; CHECK:       jump:
 ; CHECK-NEXT:    br label [[RET]]
 ; CHECK:       ret:
-; CHECK-NEXT:    [[A:%.*]] = phi i32 [ 20, [[ENTRY:%.*]] ], [ 10, [[JUMP]] ]
-; CHECK-NEXT:    ret i32 [[A]]
+; CHECK-NEXT:    [[B:%.*]] = phi i32 [ 10, [[JUMP]] ], [ 20, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    ret i32 [[B]]
 ;
 entry:
   br i1 %cond, label %jump, label %ret
 jump:
   %c = or i1 false, false
   br label %ret
 ret:
   %a = phi i1 [true, %entry], [%c, %jump]
   %b = select i1 %a, i32 20, i32 10
   ret i32 %b
 }
 
 define i32 @test27(i1 %c, i32 %A, i32 %B)  {
 ; CHECK-LABEL: @test27(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[JUMP:%.*]], label [[RET:%.*]]
 ; CHECK:       jump:
 ; CHECK-NEXT:    br label [[RET]]
 ; CHECK:       ret:
-; CHECK-NEXT:    [[P:%.*]] = phi i32 [ [[A:%.*]], [[JUMP]] ], [ [[B:%.*]], [[ENTRY:%.*]] ]
-; CHECK-NEXT:    ret i32 [[P]]
+; CHECK-NEXT:    [[S:%.*]] = phi i32 [ [[A:%.*]], [[JUMP]] ], [ [[B:%.*]], [[ENTRY:%.*]] ]
+; CHECK-NEXT:    ret i32 [[S]]
 ;
 entry:
   br i1 %c, label %jump, label %ret
 jump:
   br label %ret
 ret:
   %p = phi i1 [true, %jump], [false, %entry]
   %s = select i1 %p, i32 %A, i32 %B
   ret i32 %s
 }
 
 define i32 @test28(i1 %cond, i32 %A, i32 %B)  {
 ; CHECK-LABEL: @test28(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[COND:%.*]], label [[JUMP:%.*]], label [[RET:%.*]]
 ; CHECK:       jump:
 ; CHECK-NEXT:    br label [[RET]]
 ; CHECK:       ret:
-; CHECK-NEXT:    [[P:%.*]] = phi i32 [ [[A:%.*]], [[JUMP]] ], [ [[B:%.*]], [[ENTRY:%.*]] ]
-; CHECK-NEXT:    ret i32 [[P]]
+; CHECK-NEXT:    [[S:%.*]] = phi i32 [ [[A:%.*]], [[JUMP]] ], [ [[B:%.*]], [[ENTRY:%.*]] ]
+; CHECK-NEXT:    ret i32 [[S]]
 ;
 entry:
   br i1 %cond, label %jump, label %ret
 jump:
   br label %ret
 ret:
   %c = phi i32 [%A, %jump], [%B, %entry]
   %p = phi i1 [true, %jump], [false, %entry]
   %s = select i1 %p, i32 %A, i32 %c
   ret i32 %s
 }
 
 define i32 @test29(i1 %cond, i32 %A, i32 %B)  {
 ; CHECK-LABEL: @test29(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[COND:%.*]], label [[JUMP:%.*]], label [[RET:%.*]]
 ; CHECK:       jump:
 ; CHECK-NEXT:    br label [[RET]]
 ; CHECK:       ret:
-; CHECK-NEXT:    [[P:%.*]] = phi i32 [ [[A:%.*]], [[JUMP]] ], [ [[B:%.*]], [[ENTRY:%.*]] ]
+; CHECK-NEXT:    [[S:%.*]] = phi i32 [ [[A:%.*]], [[JUMP]] ], [ [[B:%.*]], [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    br label [[NEXT:%.*]]
 ; CHECK:       next:
-; CHECK-NEXT:    ret i32 [[P]]
+; CHECK-NEXT:    ret i32 [[S]]
 ;
 entry:
   br i1 %cond, label %jump, label %ret
 jump:
   br label %ret
 ret:
   %c = phi i32 [%A, %jump], [%B, %entry]
   %p = phi i1 [true, %jump], [false, %entry]

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:
   br label %merge
 
 merge:
   %ret = phi i1 [true, %if.true], [false, %if.false]
   ret i1 %ret
 }
 
-; TODO: Simplify to "ret !cond".
 define i1 @test_inverted_implication(i1 %cond) {
 ; 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:
   br label %merge
 
 merge:
   %ret = phi i1 [false, %if.true], [true, %if.false]
   ret i1 %ret
 }
 
-; TODO: Simplify to "ret cond".
 define i1 @test_direct_implication_complex_cfg(i1 %cond, i32 %cnt1) {
 ; CHECK-LABEL: @test_direct_implication_complex_cfg(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[COND:%.*]], label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]]
 ; CHECK:       if.true:
 ; CHECK-NEXT:    br label [[LOOP1:%.*]]
 ; CHECK:       loop1:
 ; CHECK-NEXT:    [[IV1:%.*]] = phi i32 [ 0, [[IF_TRUE]] ], [ [[IV1_NEXT:%.*]], [[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 [ 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:
   %iv1 = phi i32 [0, %if.true], [%iv1.next, %loop1]
   %iv1.next = add i32 %iv1, 1
   %loop.cond.1 = icmp slt i32 %iv1.next, %cnt1
   br i1 %loop.cond.1, label %loop1, label %if.true.end
 
 if.true.end:
   br label %merge
 
 if.false:
   br label %merge
 
 merge:
   %ret = phi i1 [true, %if.true.end], [false, %if.false]
   ret i1 %ret
 }
 
-; TODO: Simplify to "ret !cond".
 define i1 @test_inverted_implication_complex_cfg(i1 %cond, i32 %cnt1) {
 ; CHECK-LABEL: @test_inverted_implication_complex_cfg(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[COND:%.*]], label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]]
 ; CHECK:       if.true:
 ; CHECK-NEXT:    br label [[LOOP1:%.*]]
 ; CHECK:       loop1:
 ; CHECK-NEXT:    [[IV1:%.*]] = phi i32 [ 0, [[IF_TRUE]] ], [ [[IV1_NEXT:%.*]], [[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:

llvm/test/Transforms/PhaseOrdering/simplifycfg-options.ll

 ; ALL-NEXT:    [[TMP0:%.*]] = load i32, i32* [[ARRAYIDX]], align 4
 ; ALL-NEXT:    [[CMP:%.*]] = icmp eq i32 [[OR]], [[TMP0]]
 ; ALL-NEXT:    br i1 [[CMP]], label [[IF_END:%.*]], label [[IF_THEN:%.*]]
 ; ALL:       if.then:
 ; ALL-NEXT:    store i32 [[OR]], i32* [[ARRAYIDX]], align 4
 ; ALL-NEXT:    call void @foo()
 ; ALL-NEXT:    br label [[IF_END]]
 ; ALL:       if.end:
-; ALL-NEXT:    [[CHANGED_1_OFF0:%.*]] = phi i1 [ true, [[IF_THEN]] ], [ false, [[ENTRY:%.*]] ]
-; ALL-NEXT:    [[TMP1:%.*]] = load i32, i32* [[C]], align 4
-; ALL-NEXT:    [[CMP_1:%.*]] = icmp eq i32 [[OR]], [[TMP1]]
+; ALL-NEXT:    [[TMP1:%.*]] = xor i1 [[CMP]], true
+; ALL-NEXT:    [[TMP2:%.*]] = load i32, i32* [[C]], align 4
+; ALL-NEXT:    [[CMP_1:%.*]] = icmp eq i32 [[OR]], [[TMP2]]
 ; ALL-NEXT:    br i1 [[CMP_1]], label [[IF_END_1:%.*]], label [[IF_THEN_1:%.*]]
 ; ALL:       if.then.1:
 ; ALL-NEXT:    store i32 [[OR]], i32* [[C]], align 4
 ; ALL-NEXT:    call void @foo()
 ; ALL-NEXT:    br label [[IF_END_1]]
 ; ALL:       if.end.1:
-; ALL-NEXT:    [[CHANGED_1_OFF0_1:%.*]] = phi i1 [ true, [[IF_THEN_1]] ], [ [[CHANGED_1_OFF0]], [[IF_END]] ]
+; ALL-NEXT:    [[CHANGED_1_OFF0_1:%.*]] = phi i1 [ true, [[IF_THEN_1]] ], [ [[TMP1]], [[IF_END]] ]
 ; ALL-NEXT:    ret i1 [[CHANGED_1_OFF0_1]]
 ;
 entry:
   br label %for.cond
 
 for.cond:
   %i.0 = phi i32 [ 2, %entry ], [ %dec, %if.end ]
   %changed.0.off0 = phi i1 [ false, %entry ], [ %changed.1.off0, %if.end ]