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

Regressed

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

43

Unwanted

[mkazantsev]

Some underlying transforms are missing it seems.

llvm/test/Transforms/InstCombine/select.ll

512–514

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

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

[mkazantsev]

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

43

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

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/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;
+
+  // TODO: This can be generalized for more than 2 inputs, but it will take
+  // more sophisticated dominance checks.
+  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;
+
+  assert(PN.getOperand(0) != PN.getOperand(1) &&
+         "Should have been simplified away!");
+
+  BasicBlock *TruePred = nullptr, *FalsePred = nullptr;
+  BasicBlock *BB = PN.getParent();
+  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 equivalent 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;
 
+  // Try to simplify this Phi using knowledge of control flow.
+  if (Value *V = SimplifyUsingControlFlow(*this, PN, DT))
+    return replaceInstUsesWith(PN, V);
+
   return nullptr;
 }

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

 declare void @dummy1(%struct.bitmap*, %struct.bitmap*, %struct.bitmap*, %struct.bitmap*, %struct.bitmap*, %struct.bitmap*)
 
 
 ;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-LABEL: CallSiteBB:
+;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/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 ]
+; TODO: Can be further optimized by removing select.
+; CHECK-NOT: %cond
+; CHECK:     %val = phi i32 [ %0, %bb1 ], [ 0, %entry ]
+; CHECK:     %res = select i1 %a, i32 %val, i32 0
     %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
+; CHECK:    ret i32 %res
     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:%.*]] = select i1 [[C]], i32 10, i32 20
+; 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:%.*]] = select i1 [[COND]], i32 10, i32 20
+; 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:%.*]] = select i1 [[C]], i32 [[A:%.*]], i32 [[B:%.*]]
+; 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:    [[C:%.*]] = phi i32 [ [[A:%.*]], [[JUMP]] ], [ [[B:%.*]], [[ENTRY:%.*]] ]
+; CHECK-NEXT:    [[S:%.*]] = select i1 [[COND]], i32 [[A]], i32 [[C]]
+; 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:    [[C:%.*]] = phi i32 [ [[A:%.*]], [[JUMP]] ], [ [[B:%.*]], [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    br label [[NEXT:%.*]]
 ; CHECK:       next:
-; CHECK-NEXT:    ret i32 [[P]]
+; CHECK-NEXT:    [[S:%.*]] = select i1 [[COND]], i32 [[A]], i32 [[C]]
+; 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:

 ; 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:

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

 ; ASSUMPTIONS-OFF-NEXT:    store volatile i64 -1, i64* [[PTR]], align 4
 ; ASSUMPTIONS-OFF-NEXT:    store volatile i64 -1, i64* [[PTR]], align 4
 ; ASSUMPTIONS-OFF-NEXT:    store volatile i64 3, i64* [[PTR]], align 4
 ; ASSUMPTIONS-OFF-NEXT:    ret void
 ;
 ; ASSUMPTIONS-ON-LABEL: @caller1(
 ; ASSUMPTIONS-ON-NEXT:    br i1 [[C:%.*]], label [[TRUE1:%.*]], label [[FALSE1:%.*]]
 ; ASSUMPTIONS-ON:       true1:
-; ASSUMPTIONS-ON-NEXT:    [[C_PR:%.*]] = phi i1 [ false, [[FALSE1]] ], [ true, [[TMP0:%.*]] ]
+; ASSUMPTIONS-ON-NEXT:    [[C_PR:%.*]] = phi i1 [ [[C]], [[FALSE1]] ], [ true, [[TMP0:%.*]] ]
 ; ASSUMPTIONS-ON-NEXT:    [[PTRINT:%.*]] = ptrtoint i64* [[PTR:%.*]] to i64
 ; ASSUMPTIONS-ON-NEXT:    [[MASKEDPTR:%.*]] = and i64 [[PTRINT]], 7
 ; ASSUMPTIONS-ON-NEXT:    [[MASKCOND:%.*]] = icmp eq i64 [[MASKEDPTR]], 0
 ; ASSUMPTIONS-ON-NEXT:    tail call void @llvm.assume(i1 [[MASKCOND]])
 ; ASSUMPTIONS-ON-NEXT:    store volatile i64 0, i64* [[PTR]], align 8
 ; ASSUMPTIONS-ON-NEXT:    store volatile i64 -1, i64* [[PTR]], align 8
 ; ASSUMPTIONS-ON-NEXT:    store volatile i64 -1, i64* [[PTR]], align 8
 ; ASSUMPTIONS-ON-NEXT:    store volatile i64 -1, i64* [[PTR]], align 8

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 ]