[SimplifyCFG] Update FoldBranchToCommonDest to be poison-safe

[aqjune]

Summary

This patch makes FoldBranchToCommonDest merge branch conditions into select i1 rather than and/or i1 when it is called by SimplifyCFG.
It is known that merging conditions into and/or is poison-unsafe, and this is towards making things *more* correct by removing possible miscompilations.
Currently, InstCombine simply consumes these selects into and/or of i1 (which is also unsafe), so the visible effect would be very small. The unsafe select -> and/or transformation will be removed in the future.
There has been efforts for updating optimizations to support the select form as well, and they are linked to D93065.

The safe transformation is fired when it is called by SimplifyCFG only. This is done by setting the new PoisonSafe argument as true.
Another place that calls FoldBranchToCommonDest is LoopSimplify. PoisonSafe flag is set to false in this case because enabling it has a nontrivial impact in performance because SCEV is more conservative with select form and InductiveRangeCheckElimination isn't aware of select form of and/or i1.

[aqjune]

Fix test

[aqjune]

llvm/lib/Target/BPF/BPFAdjustOpt.cpp

118 ↗

(On Diff #317793)

This update was needed to support llvm/test/CodeGen/BPF/adjust-opt-icmp1.ll .

[aqjune]

Another place that calls FoldBranchToCommonDest is LoopSimplify. I think this will have a nontrivial impact since SCEV is more conservative in this case.

Enabling PoisonSafe when called by LoopSimplify requires performance evaluation.
For any patches that require experiment, I'd like to write on Feb; right now I don't have enough bandwidth.

[aqjune]

Ping
I'd like to leave the select i1 -> and/or folding in InstCombine as a single point where such transformation happens. This patch is a step to it.

[lebedev.ri]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

3075–3086

This needs changing, too

[aqjune]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

3075–3086

The created selects are semantically equivalent to and/or - but would it be more correct to count them as having select costs? (I'm not familiar with the instruction cost things)

[aqjune]

Rebase

[aqjune]

Combined with D97756, running LLVM test suite using -O3 emits 20 (among 1978) assembly files differently from the vanilla clang (main branch).
Among 20 diffs, 17 are due to the swapped operand or variable renaming (which causes diffs in comments).
2 are due to EarlyCSE treating select and and/or i1 differently (speculative), 1 due to SimplifyCFG::FoldBranchToCommonDest.
I believe the overall impact is minor ATM, and my upcoming fixes will fix all of these.

Turning on PoisonUnsafe flag for LoopSimplify creates quite a few more unoptimized assemblies, and this should be enabled after further updates.

[aqjune]

clang-format

[nikic]

Sorry for the delay. This LG with a nit, but please land this only after the loop unswitch change.

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

2970

Why do we need NewCondV and NewCond? setCondition should accept a Value without the Instruction cast.

[nikic]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

2970

Actually, one more note: What do you think about adding an impliesPoison check here? Otherwise, we may have a phase ordering issue for passes that run between SimplifyCFG and InstCombine, where one creates logical and/or and the other converts to binary. It's not a problem for folds performed by InstCombine itself, but there could be regressions for and/or folds by InstSimplify that can't happen in the meantime. Possibly this could also help LoopSimplify?

[aqjune]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

2970

This is a great idea!
Cast is not necessary, yes. I'll fix it.

[aqjune]

Use impliesPoison, remove cast

[lebedev.ri]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

2970

Please add a FIXME: remove once select form is canonical

[aqjune]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

2970

Safely folding select into and/or helps SCEV do further analysis: https://reviews.llvm.org/D93065#2472644 I think it might be a good idea to fold select to and/or whenever it is correct.

[nikic]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

2965

I would write this as bool UseBinOp = !PoisonSafe || impliesPoison(BICond, PBI->getCondition()); rather than a separate if. Or inline the condition entirely.

[mehdi_amini]

Reverted in 8d5a981a135a ; clang seems to miscompile LLVM. Provided some reproduction in the revert commit message.

[aqjune]

In D95026#2610334, @mehdi_amini wrote:

Reverted in 8d5a981a135a ; clang seems to miscompile LLVM. Provided some reproduction in the revert commit message.

Thank you, I'll look into it.

[aqjune]

I could reproduce the failures from two-stage build and submitted a bug report: https://bugs.llvm.org/show_bug.cgi?id=49495

Consider this code snippet:

vector<ty> v; // empty
ty* b = v.begin(), *e = v.end()
if (b != e && b < (e - 1))
  // reverse items in [b, e)

After the patch, LLVM was optimizing it into

vector<ty> v; // empty
ty* b = v.begin(), *e = v.end()
if (b < (e - 1))
  // reverse items in [b, e)

But this is wrong. Since v is empty, v.begin() and v.end() can return NULL. e - 1 raises overflow, hence the branch is taken, which is wrong.

PopulateLoopsDFS<llvm::BasicBlock, llvm::Loop>::insertIntoLoop was containing a code snippet that looked like this.

[nickdesaulniers]

Hello friends, it seems the reland of this (5c2e50b5d2412f4e1fdb48bce04917e1b6a29cf9) exposed what looks like either a regression or optimization opportunity in clang-13.
https://github.com/llvm/llvm-project/issues/53861
PTAL

llvm/include/llvm/IR/IRBuilder.h

Value *CreateBinOp(Instruction::BinaryOps Opc,
                      MDNode *FPMathTag = nullptr) {
     if (Value *V = foldConstant(Opc, LHS, RHS, Name)) return V;
     Instruction *BinOp = BinaryOperator::Create(Opc, LHS, RHS);
     if (isa<FPMathOperator>(BinOp))
       setFPAttrs(BinOp, FPMathTag, FMF);
     return Insert(BinOp, Name);
   }
 
+  Value *CreateLogicalAnd(Value *Cond1, Value *Cond2, const Twine &Name = "") {
+    assert(Cond2->getType()->isIntOrIntVectorTy(1));
+    return CreateSelect(Cond1, Cond2,
+                        ConstantInt::getNullValue(Cond2->getType()), Name);
+  }
+
+  Value *CreateLogicalOr(Value *Cond1, Value *Cond2, const Twine &Name = "") {
+    assert(Cond2->getType()->isIntOrIntVectorTy(1));
+    return CreateSelect(Cond1, ConstantInt::getAllOnesValue(Cond2->getType()),
+                        Cond2, Name);
+  }
+
   CallInst *CreateConstrainedFPBinOp(
       Intrinsic::ID ID, Value *L, Value *R, Instruction *FMFSource = nullptr,
       const Twine &Name = "", MDNode *FPMathTag = nullptr,
       Optional<RoundingMode> Rounding = None,
       Optional<fp::ExceptionBehavior> Except = None);
 
   Value *CreateNeg(Value *V, const Twine &Name = "",
                    bool HasNUW = false, bool HasNSW = false) {

llvm/include/llvm/Transforms/Utils/Local.h

 /// This function is used to flatten a CFG. For example, it uses parallel-and
 /// and parallel-or mode to collapse if-conditions and merge if-regions with
 /// identical statements.
 bool FlattenCFG(BasicBlock *BB, AAResults *AA = nullptr);
 
 /// If this basic block is ONLY a setcc and a branch, and if a predecessor
 /// branches to us and one of our successors, fold the setcc into the
 /// predecessor and use logical operations to pick the right destination.
+/// If PoisonSafe is true, use select i1 rather than and/or i1 to successfully
+/// block unexpected propagation of poison when merging the branches. This is
+/// set to false by default when used by LoopSimplify for performance, but this
+/// should be turned on by default.
 bool FoldBranchToCommonDest(BranchInst *BI, llvm::DomTreeUpdater *DTU = nullptr,
                             MemorySSAUpdater *MSSAU = nullptr,
                             const TargetTransformInfo *TTI = nullptr,
-                            unsigned BonusInstThreshold = 1);
+                            unsigned BonusInstThreshold = 1,
+                            bool PoisonSafe = false);
 
 /// This function takes a virtual register computed by an Instruction and
 /// replaces it with a slot in the stack frame, allocated via alloca.
 /// This allows the CFG to be changed around without fear of invalidating the
 /// SSA information for the value. It returns the pointer to the alloca inserted
 /// to create a stack slot for X.
 AllocaInst *DemoteRegToStack(Instruction &X,
                              bool VolatileLoads = false,

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

else if (PBI->getSuccessor(0) == BI->getSuccessor(1))
     return {{Instruction::And, true}};
   else if (PBI->getSuccessor(1) == BI->getSuccessor(0))
     return {{Instruction::Or, true}};
   return None;
 }
 
 static bool PerformBranchToCommonDestFolding(BranchInst *BI, BranchInst *PBI,
                                              DomTreeUpdater *DTU,
-                                             MemorySSAUpdater *MSSAU) {
+                                             MemorySSAUpdater *MSSAU,
+                                             bool PoisonSafe) {
   BasicBlock *BB = BI->getParent();
   BasicBlock *PredBlock = PBI->getParent();
 
   // Determine if the two branches share a common destination.
   Instruction::BinaryOps Opc;
   bool InvertPredCond;
   std::tie(Opc, InvertPredCond) =
       *CheckIfCondBranchesShareCommonDestination(BI, PBI);
static bool PerformBranchToCommonDestFolding(BranchInst *BI, BranchInst *PBI,
   if (MDNode *LoopMD = BI->getMetadata(LLVMContext::MD_loop))
     PBI->setMetadata(LLVMContext::MD_loop, LoopMD);
 
   ValueToValueMapTy VMap; // maps original values to cloned values
   CloneInstructionsIntoPredecessorBlockAndUpdateSSAUses(BB, PredBlock, VMap);
 
   // Now that the Cond was cloned into the predecessor basic block,
   // or/and the two conditions together.
-  Instruction *NewCond = cast<Instruction>(Builder.CreateBinOp(
-      Opc, PBI->getCondition(), VMap[BI->getCondition()], "or.cond"));
+  Value *NewCond = nullptr;
+  Value *BICond = VMap[BI->getCondition()];
+  bool UseBinOp = true;
+  if (PoisonSafe)
+    UseBinOp = impliesPoison(BICond, PBI->getCondition());
+
+  if (UseBinOp)
+    NewCond = Builder.CreateBinOp(Opc, PBI->getCondition(), BICond, "or.cond");
+  else
+    NewCond =
+        Opc == Instruction::And
+            ? Builder.CreateLogicalAnd(PBI->getCondition(), BICond, "or.cond")
+            : Builder.CreateLogicalOr(PBI->getCondition(), BICond, "or.cond");
   PBI->setCondition(NewCond);
 
   // Copy any debug value intrinsics into the end of PredBlock.
   for (Instruction &I : *BB) {
     if (isa<DbgInfoIntrinsic>(I)) {
       Instruction *NewI = I.clone();
       RemapInstruction(NewI, VMap,
                        RF_NoModuleLevelChanges | RF_IgnoreMissingLocals);
       NewI->insertBefore(PBI);
     }
   }
 
   ++NumFoldBranchToCommonDest;
   return true;
 }
 
 /// If this basic block is simple enough, and if a predecessor branches to us
 /// and one of our successors, fold the block into the predecessor and use
 /// logical operations to pick the right destination.
 bool llvm::FoldBranchToCommonDest(BranchInst *BI, DomTreeUpdater *DTU,
                                   MemorySSAUpdater *MSSAU,
                                   const TargetTransformInfo *TTI,
-                                  unsigned BonusInstThreshold) {
+                                  unsigned BonusInstThreshold,
+                                  bool PoisonSafe) {
   // If this block ends with an unconditional branch,
   // let SpeculativelyExecuteBB() deal with it.
   if (!BI->isConditional())
     return false;
 
   BasicBlock *BB = BI->getParent();
 
   const unsigned PredCount = pred_size(BB);
for (BasicBlock *PredBlock : predecessors(BB)) {
     // Determine if the two branches share a common destination.
     Instruction::BinaryOps Opc;
     bool InvertPredCond;
     if (auto Recepie = CheckIfCondBranchesShareCommonDestination(BI, PBI))
       std::tie(Opc, InvertPredCond) = *Recepie;
     else
       continue;
 
     // Check the cost of inserting the necessary logic before performing the
     // transformation.
     if (TTI) {
       Type *Ty = BI->getCondition()->getType();
       InstructionCost Cost = TTI->getArithmeticInstrCost(Opc, Ty, CostKind);
       if (InvertPredCond && (!PBI->getCondition()->hasOneUse() ||
           !isa<CmpInst>(PBI->getCondition())))
         Cost += TTI->getArithmeticInstrCost(Instruction::Xor, Ty, CostKind);
 
       if (Cost > BranchFoldThreshold)
         continue;
     }
 
-    return PerformBranchToCommonDestFolding(BI, PBI, DTU, MSSAU);
+    return PerformBranchToCommonDestFolding(BI, PBI, DTU, MSSAU, PoisonSafe);
   }
   return Changed;
 }
 
 // If there is only one store in BB1 and BB2, return it, otherwise return
 // nullptr.
 static StoreInst *findUniqueStoreInBlocks(BasicBlock *BB1, BasicBlock *BB2) {
   StoreInst *S = nullptr;
if (I->isTerminator() && TryToMergeLandingPad(LPad, BI, BB, DTU))
       return true;
   }
 
   // If this basic block is ONLY a compare and a branch, and if a predecessor
   // branches to us and our successor, fold the comparison into the
   // predecessor and use logical operations to update the incoming value
   // for PHI nodes in common successor.
   if (FoldBranchToCommonDest(BI, DTU, /*MSSAU=*/nullptr, &TTI,
-                             Options.BonusInstThreshold))
+                             Options.BonusInstThreshold, true))
     return requestResimplify();
   return false;
 }
 
 static BasicBlock *allPredecessorsComeFromSameSource(BasicBlock *BB) {
   BasicBlock *PredPred = nullptr;
   for (auto *P : predecessors(BB)) {
     BasicBlock *PPred = P->getSinglePredecessor();
if (Imp) {
     RecursivelyDeleteTriviallyDeadInstructions(OldCond);
     return requestResimplify();
   }
 
   // If this basic block is ONLY a compare and a branch, and if a predecessor
   // branches to us and one of our successors, fold the comparison into the
   // predecessor and use logical operations to pick the right destination.
   if (FoldBranchToCommonDest(BI, DTU, /*MSSAU=*/nullptr, &TTI,
-                             Options.BonusInstThreshold))
+                             Options.BonusInstThreshold, true))
     return requestResimplify();
 
   // We have a conditional branch to two blocks that are only reachable
   // from BI.  We know that the condbr dominates the two blocks, so see if
   // there is any identical code in the "then" and "else" blocks.  If so, we
   // can hoist it up to the branching block.
   if (BI->getSuccessor(0)->getSinglePredecessor()) {
     if (BI->getSuccessor(1)->getSinglePredecessor()) {

llvm/test/Transforms/PGOProfile/chr.ll

 ; return i0 + sum3
 define i32 @test_chr_14(i32* %i, i32* %j, i32 %sum0, i1 %pred, i32 %z) !prof !14 {
 ; CHECK-LABEL: @test_chr_14(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[I0:%.*]] = load i32, i32* [[I:%.*]], align 4
 ; CHECK-NEXT:    [[V1:%.*]] = icmp ne i32 [[Z:%.*]], 1
 ; CHECK-NEXT:    [[V0:%.*]] = icmp eq i32 [[Z]], 0
 ; CHECK-NEXT:    [[V3_NONCHR:%.*]] = and i1 [[V0]], [[PRED:%.*]]
-; CHECK-NEXT:    [[OR_COND:%.*]] = and i1 [[V1]], [[V3_NONCHR]]
+; CHECK-NEXT:    [[OR_COND:%.*]] = select i1 [[V1]], i1 [[V3_NONCHR]], i1 false
 ; CHECK-NEXT:    br i1 [[OR_COND]], label [[BB0_NONCHR:%.*]], label [[BB1:%.*]], !prof !19
 ; CHECK:       bb0.nonchr:
 ; CHECK-NEXT:    call void @foo()
 ; CHECK-NEXT:    br label [[BB1]]
 ; CHECK:       bb1:
 ; CHECK-NEXT:    [[J0:%.*]] = load i32, i32* [[J:%.*]], align 4
 ; CHECK-NEXT:    [[V6:%.*]] = and i32 [[I0]], 2
 ; CHECK-NEXT:    [[V4:%.*]] = icmp ne i32 [[V6]], [[J0]]

llvm/test/Transforms/SimplifyCFG/ARM/branch-fold-threshold.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -mtriple=thumbv8m.main %s -simplifycfg -simplifycfg-require-and-preserve-domtree=1 -S | FileCheck %s --check-prefix=CHECK --check-prefix=THUMB
 ; RUN: opt -mtriple=thumbv8a %s -simplifycfg -simplifycfg-require-and-preserve-domtree=1 -S | FileCheck %s --check-prefix=CHECK --check-prefix=THUMB
 ; RUN: opt -mtriple=armv8a %s -simplifycfg -simplifycfg-require-and-preserve-domtree=1 -S | FileCheck %s --check-prefix=CHECK --check-prefix=ARM
 
 define i32 @foo(i32 %a, i32 %b, i32 %c, i32 %d, i32* %input) {
 ; CHECK-LABEL: @foo(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp sle i32 [[D:%.*]], 3
 ; CHECK-NEXT:    [[ADD:%.*]] = add nsw i32 [[C:%.*]], [[A:%.*]]
 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i32 [[ADD]], [[B:%.*]]
-; CHECK-NEXT:    [[OR_COND:%.*]] = and i1 [[CMP]], [[CMP1]]
+; CHECK-NEXT:    [[OR_COND:%.*]] = select i1 [[CMP]], i1 [[CMP1]], i1 false
 ; CHECK-NEXT:    br i1 [[OR_COND]], label [[COND_FALSE:%.*]], label [[COND_END:%.*]]
 ; CHECK:       cond.false:
 ; CHECK-NEXT:    [[TMP0:%.*]] = load i32, i32* [[INPUT:%.*]], align 4
 ; CHECK-NEXT:    br label [[COND_END]]
 ; CHECK:       cond.end:
 ; CHECK-NEXT:    [[COND:%.*]] = phi i32 [ [[TMP0]], [[COND_FALSE]] ], [ 0, [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    ret i32 [[COND]]
 ;

 }
 
 define i32 @foo_minsize(i32 %a, i32 %b, i32 %c, i32 %d, i32* %input) #0 {
 ; CHECK-LABEL: @foo_minsize(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp sle i32 [[D:%.*]], 3
 ; CHECK-NEXT:    [[ADD:%.*]] = add nsw i32 [[C:%.*]], [[A:%.*]]
 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i32 [[ADD]], [[B:%.*]]
-; CHECK-NEXT:    [[OR_COND:%.*]] = and i1 [[CMP]], [[CMP1]]
+; CHECK-NEXT:    [[OR_COND:%.*]] = select i1 [[CMP]], i1 [[CMP1]], i1 false
 ; CHECK-NEXT:    br i1 [[OR_COND]], label [[COND_FALSE:%.*]], label [[COND_END:%.*]]
 ; CHECK:       cond.false:
 ; CHECK-NEXT:    [[TMP0:%.*]] = load i32, i32* [[INPUT:%.*]], align 4
 ; CHECK-NEXT:    br label [[COND_END]]
 ; CHECK:       cond.end:
 ; CHECK-NEXT:    [[COND:%.*]] = phi i32 [ [[TMP0]], [[COND_FALSE]] ], [ 0, [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    ret i32 [[COND]]
 ;

 }
 
 define i32 @foo_minsize_i64(i64 %a, i64 %b, i64 %c, i64 %d, i32* %input) #0 {
 ; CHECK-LABEL: @foo_minsize_i64(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp sle i64 [[D:%.*]], 3
 ; CHECK-NEXT:    [[ADD:%.*]] = add nsw i64 [[C:%.*]], [[A:%.*]]
 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i64 [[ADD]], [[B:%.*]]
-; CHECK-NEXT:    [[OR_COND:%.*]] = and i1 [[CMP]], [[CMP1]]
+; CHECK-NEXT:    [[OR_COND:%.*]] = select i1 [[CMP]], i1 [[CMP1]], i1 false
 ; CHECK-NEXT:    br i1 [[OR_COND]], label [[COND_FALSE:%.*]], label [[COND_END:%.*]]
 ; CHECK:       cond.false:
 ; CHECK-NEXT:    [[TMP0:%.*]] = load i32, i32* [[INPUT:%.*]], align 4
 ; CHECK-NEXT:    br label [[COND_END]]
 ; CHECK:       cond.end:
 ; CHECK-NEXT:    [[COND:%.*]] = phi i32 [ [[TMP0]], [[COND_FALSE]] ], [ 0, [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    ret i32 [[COND]]
 ;

 }
 
 define i32 @or_predicate(i32 %a, i32 %b, i32 %c, i32 %d, i32* %input) {
 ; CHECK-LABEL: @or_predicate(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i32 [[D:%.*]], 3
 ; CHECK-NEXT:    [[ADD:%.*]] = add nsw i32 [[C:%.*]], [[A:%.*]]
 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i32 [[ADD]], [[B:%.*]]
-; CHECK-NEXT:    [[OR_COND:%.*]] = or i1 [[CMP]], [[CMP1]]
+; CHECK-NEXT:    [[OR_COND:%.*]] = select i1 [[CMP]], i1 true, i1 [[CMP1]]
 ; CHECK-NEXT:    br i1 [[OR_COND]], label [[COND_END:%.*]], label [[COND_FALSE:%.*]]
 ; CHECK:       cond.false:
 ; CHECK-NEXT:    [[TMP0:%.*]] = load i32, i32* [[INPUT:%.*]], align 4
 ; CHECK-NEXT:    br label [[COND_END]]
 ; CHECK:       cond.end:
 ; CHECK-NEXT:    [[COND:%.*]] = phi i32 [ [[TMP0]], [[COND_FALSE]] ], [ 0, [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    ret i32 [[COND]]
 ;

 }
 
 define i32 @or_invert_predicate(i32 %a, i32 %b, i32 %c, i32 %d, i32* %input) {
 ; CHECK-LABEL: @or_invert_predicate(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp sle i32 [[D:%.*]], 3
 ; CHECK-NEXT:    [[ADD:%.*]] = add nsw i32 [[C:%.*]], [[A:%.*]]
 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i32 [[ADD]], [[B:%.*]]
-; CHECK-NEXT:    [[OR_COND:%.*]] = or i1 [[CMP]], [[CMP1]]
+; CHECK-NEXT:    [[OR_COND:%.*]] = select i1 [[CMP]], i1 true, i1 [[CMP1]]
 ; CHECK-NEXT:    br i1 [[OR_COND]], label [[COND_END:%.*]], label [[COND_FALSE:%.*]]
 ; CHECK:       cond.false:
 ; CHECK-NEXT:    [[TMP0:%.*]] = load i32, i32* [[INPUT:%.*]], align 4
 ; CHECK-NEXT:    br label [[COND_END]]
 ; CHECK:       cond.end:
 ; CHECK-NEXT:    [[COND:%.*]] = phi i32 [ [[TMP0]], [[COND_FALSE]] ], [ 0, [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    ret i32 [[COND]]
 ;

 ; THUMB-NEXT:    [[COND:%.*]] = phi i32 [ [[TMP0]], [[COND_FALSE]] ], [ 0, [[LOR_LHS_FALSE]] ], [ 0, [[ENTRY:%.*]] ]
 ; THUMB-NEXT:    ret i32 [[COND]]
 ;
 ; ARM-LABEL: @or_predicate_minsize(
 ; ARM-NEXT:  entry:
 ; ARM-NEXT:    [[CMP:%.*]] = icmp sgt i32 [[D:%.*]], 3
 ; ARM-NEXT:    [[ADD:%.*]] = add nsw i32 [[C:%.*]], [[A:%.*]]
 ; ARM-NEXT:    [[CMP1:%.*]] = icmp slt i32 [[ADD]], [[B:%.*]]
-; ARM-NEXT:    [[OR_COND:%.*]] = or i1 [[CMP]], [[CMP1]]
+; ARM-NEXT:    [[OR_COND:%.*]] = select i1 [[CMP]], i1 true, i1 [[CMP1]]
 ; ARM-NEXT:    br i1 [[OR_COND]], label [[COND_END:%.*]], label [[COND_FALSE:%.*]]
 ; ARM:       cond.false:
 ; ARM-NEXT:    [[TMP0:%.*]] = load i32, i32* [[INPUT:%.*]], align 4
 ; ARM-NEXT:    br label [[COND_END]]
 ; ARM:       cond.end:
 ; ARM-NEXT:    [[COND:%.*]] = phi i32 [ [[TMP0]], [[COND_FALSE]] ], [ 0, [[ENTRY:%.*]] ]
 ; ARM-NEXT:    ret i32 [[COND]]
 ;

 ; THUMB-NEXT:    [[COND:%.*]] = phi i32 [ [[TMP0]], [[COND_FALSE]] ], [ 0, [[LOR_LHS_FALSE]] ], [ 0, [[ENTRY:%.*]] ]
 ; THUMB-NEXT:    ret i32 [[COND]]
 ;
 ; ARM-LABEL: @or_invert_predicate_minsize(
 ; ARM-NEXT:  entry:
 ; ARM-NEXT:    [[CMP:%.*]] = icmp sle i32 [[D:%.*]], 3
 ; ARM-NEXT:    [[ADD:%.*]] = add nsw i32 [[C:%.*]], [[A:%.*]]
 ; ARM-NEXT:    [[CMP1:%.*]] = icmp slt i32 [[ADD]], [[B:%.*]]
-; ARM-NEXT:    [[OR_COND:%.*]] = or i1 [[CMP]], [[CMP1]]
+; ARM-NEXT:    [[OR_COND:%.*]] = select i1 [[CMP]], i1 true, i1 [[CMP1]]
 ; ARM-NEXT:    br i1 [[OR_COND]], label [[COND_END:%.*]], label [[COND_FALSE:%.*]]
 ; ARM:       cond.false:
 ; ARM-NEXT:    [[TMP0:%.*]] = load i32, i32* [[INPUT:%.*]], align 4
 ; ARM-NEXT:    br label [[COND_END]]
 ; ARM:       cond.end:
 ; ARM-NEXT:    [[COND:%.*]] = phi i32 [ [[TMP0]], [[COND_FALSE]] ], [ 0, [[ENTRY:%.*]] ]
 ; ARM-NEXT:    ret i32 [[COND]]
 ;

 }
 
 define i32 @or_xor_predicate(i32 %a, i32 %b, i32 %c, i32 %d, i32* %input, i1 %cmp) {
 ; CHECK-LABEL: @or_xor_predicate(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP_NOT:%.*]] = xor i1 [[CMP:%.*]], true
 ; CHECK-NEXT:    [[ADD:%.*]] = add nsw i32 [[C:%.*]], [[A:%.*]]
 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i32 [[ADD]], [[B:%.*]]
-; CHECK-NEXT:    [[OR_COND:%.*]] = or i1 [[CMP_NOT]], [[CMP1]]
+; CHECK-NEXT:    [[OR_COND:%.*]] = select i1 [[CMP_NOT]], i1 true, i1 [[CMP1]]
 ; CHECK-NEXT:    br i1 [[OR_COND]], label [[COND_END:%.*]], label [[COND_FALSE:%.*]]
 ; CHECK:       cond.false:
 ; CHECK-NEXT:    [[TMP0:%.*]] = load i32, i32* [[INPUT:%.*]], align 4
 ; CHECK-NEXT:    br label [[COND_END]]
 ; CHECK:       cond.end:
 ; CHECK-NEXT:    [[COND:%.*]] = phi i32 [ [[TMP0]], [[COND_FALSE]] ], [ 0, [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    ret i32 [[COND]]
 ;

 ; THUMB-NEXT:    [[COND:%.*]] = phi i32 [ [[TMP0]], [[COND_FALSE]] ], [ 0, [[LOR_LHS_FALSE]] ], [ 0, [[ENTRY:%.*]] ]
 ; THUMB-NEXT:    ret i32 [[COND]]
 ;
 ; ARM-LABEL: @or_xor_predicate_minsize(
 ; ARM-NEXT:  entry:
 ; ARM-NEXT:    [[CMP_NOT:%.*]] = xor i1 [[CMP:%.*]], true
 ; ARM-NEXT:    [[ADD:%.*]] = add nsw i32 [[C:%.*]], [[A:%.*]]
 ; ARM-NEXT:    [[CMP1:%.*]] = icmp slt i32 [[ADD]], [[B:%.*]]
-; ARM-NEXT:    [[OR_COND:%.*]] = or i1 [[CMP_NOT]], [[CMP1]]
+; ARM-NEXT:    [[OR_COND:%.*]] = select i1 [[CMP_NOT]], i1 true, i1 [[CMP1]]
 ; ARM-NEXT:    br i1 [[OR_COND]], label [[COND_END:%.*]], label [[COND_FALSE:%.*]]
 ; ARM:       cond.false:
 ; ARM-NEXT:    [[TMP0:%.*]] = load i32, i32* [[INPUT:%.*]], align 4
 ; ARM-NEXT:    br label [[COND_END]]
 ; ARM:       cond.end:
 ; ARM-NEXT:    [[COND:%.*]] = phi i32 [ [[TMP0]], [[COND_FALSE]] ], [ 0, [[ENTRY:%.*]] ]
 ; ARM-NEXT:    ret i32 [[COND]]
 ;

 }
 
 define i32 @and_xor(i32 %a, i32 %b, i32 %c, i32 %d, i32* %input, i1 %cmp) {
 ; CHECK-LABEL: @and_xor(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP_NOT:%.*]] = xor i1 [[CMP:%.*]], true
 ; CHECK-NEXT:    [[ADD:%.*]] = add nsw i32 [[C:%.*]], [[A:%.*]]
 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i32 [[ADD]], [[B:%.*]]
-; CHECK-NEXT:    [[OR_COND:%.*]] = and i1 [[CMP_NOT]], [[CMP1]]
+; CHECK-NEXT:    [[OR_COND:%.*]] = select i1 [[CMP_NOT]], i1 [[CMP1]], i1 false
 ; CHECK-NEXT:    br i1 [[OR_COND]], label [[COND_FALSE:%.*]], label [[COND_END:%.*]]
 ; CHECK:       cond.false:
 ; CHECK-NEXT:    [[TMP0:%.*]] = load i32, i32* [[INPUT:%.*]], align 4
 ; CHECK-NEXT:    br label [[COND_END]]
 ; CHECK:       cond.end:
 ; CHECK-NEXT:    [[COND:%.*]] = phi i32 [ [[TMP0]], [[COND_FALSE]] ], [ 0, [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    ret i32 [[COND]]
 ;

 ; THUMB-NEXT:    [[COND:%.*]] = phi i32 [ [[TMP0]], [[COND_FALSE]] ], [ 0, [[LOR_LHS_FALSE]] ], [ 0, [[ENTRY:%.*]] ]
 ; THUMB-NEXT:    ret i32 [[COND]]
 ;
 ; ARM-LABEL: @and_xor_minsize(
 ; ARM-NEXT:  entry:
 ; ARM-NEXT:    [[CMP_NOT:%.*]] = xor i1 [[CMP:%.*]], true
 ; ARM-NEXT:    [[ADD:%.*]] = add nsw i32 [[C:%.*]], [[A:%.*]]
 ; ARM-NEXT:    [[CMP1:%.*]] = icmp slt i32 [[ADD]], [[B:%.*]]
-; ARM-NEXT:    [[OR_COND:%.*]] = and i1 [[CMP_NOT]], [[CMP1]]
+; ARM-NEXT:    [[OR_COND:%.*]] = select i1 [[CMP_NOT]], i1 [[CMP1]], i1 false
 ; ARM-NEXT:    br i1 [[OR_COND]], label [[COND_FALSE:%.*]], label [[COND_END:%.*]]
 ; ARM:       cond.false:
 ; ARM-NEXT:    [[TMP0:%.*]] = load i32, i32* [[INPUT:%.*]], align 4
 ; ARM-NEXT:    br label [[COND_END]]
 ; ARM:       cond.end:
 ; ARM-NEXT:    [[COND:%.*]] = phi i32 [ [[TMP0]], [[COND_FALSE]] ], [ 0, [[ENTRY:%.*]] ]
 ; ARM-NEXT:    ret i32 [[COND]]
 ;

llvm/test/Transforms/SimplifyCFG/annotations.ll

 ; RUN: opt -simplifycfg -simplifycfg-require-and-preserve-domtree=1 -S %s | FileCheck --match-full-lines %s
 
 ; The branch in %cont has !annotation metadata. Make sure generated AND
 ; has !annotation metadata.
 define i32 @test_preserve_and(i8* %a, i8* %b, i8* %c, i8* %d) {
 ; CHECK-LABEL: define {{.*}} @test_preserve_and({{.*}}
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp ult i8* [[A:%.*]], [[B:%.*]], !annotation !0
 ; CHECK-NEXT:    [[C_2:%.*]] = icmp uge i8* [[C:%.*]], [[D:%.*]], !annotation !0
-; CHECK-NEXT:    [[OR_COND:%.*]] = and i1 [[C_1]], [[C_2]], !annotation !0
+; CHECK-NEXT:    [[OR_COND:%.*]] = select i1 [[C_1]], i1 [[C_2]], i1 false, !annotation !0
 ; CHECK-NEXT:    br i1 [[OR_COND]], label [[CONT1:%.*]], label [[TRAP:%.*]], !annotation !0
 ; CHECK:       trap: ; preds = %entry
 ; CHECK-NEXT:    call void @fn1()
 ; CHECK-NEXT:    unreachable
 ; CHECK:       cont1: ; preds = %entry
 ; CHECK-NEXT:    call void @fn2()
 ; CHECK-NEXT:    ret i32 0
 ;

 
 ; The branch in %cont has !annotation metadata. Make sure generated OR
 ; has !annotation metadata.
 define i32 @test_preserve_or(i8* %a, i8* %b, i8* %c, i8* %d) {
 ; CHECK-LABEL: define {{.*}} @test_preserve_or({{.*}}
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp uge i8* [[A:%.*]], [[B:%.*]], !annotation !0
 ; CHECK-NEXT:    [[C_2:%.*]] = icmp uge i8* [[C:%.*]], [[D:%.*]], !annotation !0
-; CHECK-NEXT:    [[OR_COND:%.*]] = or i1 [[C_1]], [[C_2]], !annotation !0
+; CHECK-NEXT:    [[OR_COND:%.*]] = select i1 [[C_1]], i1 true, i1 [[C_2]], !annotation !0
 ; CHECK-NEXT:    br i1 [[OR_COND]], label [[TRAP:%.*]], label [[CONT1:%.*]], !annotation !0
 ; CHECK:       trap: ; preds = %entry
 ; CHECK-NEXT:    call void @fn1()
 ; CHECK-NEXT:    unreachable
 ; CHECK:       cont1:  ; preds = %entry
 ; CHECK-NEXT:    call void @fn2()
 ; CHECK-NEXT:    ret i32 0
 ;

 ; and OR have !annotation metadata.
 define i32 @test_preserve_or_not(i8* %a, i8* %b, i8* %c, i8* %d) {
 ; CHECK-LABEL: define {{.*}} @test_preserve_or_not({{.*}}
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp ult i8* [[A:%.*]], [[B:%.*]], !annotation !0
 ; CHECK-NEXT:    [[C_2:%.*]] = xor i1 [[C_1]], true
 ; CHECK-NEXT:    [[C_2_NOT:%.*]] = xor i1 [[C_2]], true, !annotation !0
 ; CHECK-NEXT:    [[C_3:%.*]] = icmp uge i8* [[C:%.*]], [[D:%.*]], !annotation !0
-; CHECK-NEXT:    [[OR_COND:%.*]] = or i1 [[C_2_NOT]], [[C_3]], !annotation !0
+; CHECK-NEXT:    [[OR_COND:%.*]] = select i1 [[C_2_NOT]], i1 true, i1 [[C_3]], !annotation !0
 ; CHECK-NEXT:    br i1 [[OR_COND]], label [[TRAP:%.*]], label [[CONT1:%.*]], !annotation !0
 ; CHECK:       trap: ; preds = %entry
 ; CHECK-NEXT:    call void @fn1()
 ; CHECK-NEXT:    unreachable
 ; CHECK:       cont1:  ; preds = %entry
 ; CHECK-NEXT:    call void @fn2()
 ; CHECK-NEXT:    ret i32 0
 ;

 ; and OR do not have !annotation metadata.
 define i32 @test_or_not_no_annotation(i8* %a, i8* %b, i8* %c, i8* %d) {
 ; CHECK-LABEL: define {{.*}} @test_or_not_no_annotation({{.*}}
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp ult i8* [[A:%.*]], [[B:%.*]], !annotation !0
 ; CHECK-NEXT:    [[C_2:%.*]] = xor i1 [[C_1]], true
 ; CHECK-NEXT:    [[C_2_NOT:%.*]] = xor i1 [[C_2]], true
 ; CHECK-NEXT:    [[C_3:%.*]] = icmp uge i8* [[C:%.*]], [[D:%.*]], !annotation !0
-; CHECK-NEXT:    [[OR_COND:%.*]] = or i1 [[C_2_NOT]], [[C_3]]
+; CHECK-NEXT:    [[OR_COND:%.*]] = select i1 [[C_2_NOT]], i1 true, i1 [[C_3]]
 ; CHECK-NEXT:    br i1 [[OR_COND]], label [[TRAP:%.*]], label [[CONT1:%.*]], !annotation !0
 ; CHECK:       trap: ; preds = %entry
 ; CHECK-NEXT:    call void @fn1()
 ; CHECK-NEXT:    unreachable
 ; CHECK:       cont1:  ; preds = %entry
 ; CHECK-NEXT:    call void @fn2()
 ; CHECK-NEXT:    ret i32 0
 ;

llvm/test/Transforms/SimplifyCFG/common-dest-folding.ll

 ; RUN: opt < %s -simplifycfg -simplifycfg-require-and-preserve-domtree=1 -S | FileCheck %s
 
 ;CHECK: @foo
 ;CHECK: and i32 %c1, %k
 ;CHECK: icmp eq i32
 ;CHECK: and i32 %c2, %k
 ;CHECK: icmp eq i32
-;CHECK: or i1
+;CHECK: select i1 {{.*}}, i1 true,
 ;CHECK: ret
 define i32 @foo(i32 %k, i32 %c1, i32 %c2) {
   %1 = and i32 %c1, %k
   %2 = icmp eq i32 %1, 0
   br i1 %2, label %8, label %3
 
 ; <label>:3                                       ; preds = %0
   %4 = and i32 %c2, %k

llvm/test/Transforms/SimplifyCFG/fold-branch-to-common-dest.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -S -simplifycfg -simplifycfg-require-and-preserve-domtree=1 -bonus-inst-threshold=10 | FileCheck %s
 
 declare void @sideeffect0()
 declare void @sideeffect1()
 declare void @sideeffect2()
 declare void @use8(i8)
 declare i1 @gen1()
 
 ; Basic cases, blocks have nothing other than the comparison itself.
 
 define void @one_pred(i8 %v0, i8 %v1) {
 ; CHECK-LABEL: @one_pred(
 ; CHECK-NEXT:  pred:
 ; CHECK-NEXT:    [[C0:%.*]] = icmp eq i8 [[V0:%.*]], 0
 ; CHECK-NEXT:    [[C1:%.*]] = icmp eq i8 [[V1:%.*]], 0
-; CHECK-NEXT:    [[OR_COND:%.*]] = and i1 [[C0]], [[C1]]
+; CHECK-NEXT:    [[OR_COND:%.*]] = select i1 [[C0]], i1 [[C1]], i1 false
 ; CHECK-NEXT:    br i1 [[OR_COND]], label [[FINAL_LEFT:%.*]], label [[FINAL_RIGHT:%.*]]
 ; CHECK:       final_left:
 ; CHECK-NEXT:    call void @sideeffect0()
 ; CHECK-NEXT:    ret void
 ; CHECK:       final_right:
 ; CHECK-NEXT:    call void @sideeffect1()
 ; CHECK-NEXT:    ret void
 ;

 define void @two_preds(i8 %v0, i8 %v1, i8 %v2, i8 %v3) {
 ; CHECK-LABEL: @two_preds(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[C0:%.*]] = icmp eq i8 [[V0:%.*]], 0
 ; CHECK-NEXT:    br i1 [[C0]], label [[PRED0:%.*]], label [[PRED1:%.*]]
 ; CHECK:       pred0:
 ; CHECK-NEXT:    [[C1:%.*]] = icmp eq i8 [[V1:%.*]], 0
 ; CHECK-NEXT:    [[C3_OLD:%.*]] = icmp eq i8 [[V3:%.*]], 0
-; CHECK-NEXT:    [[OR_COND1:%.*]] = or i1 [[C1]], [[C3_OLD]]
+; CHECK-NEXT:    [[OR_COND1:%.*]] = select i1 [[C1]], i1 true, i1 [[C3_OLD]]
 ; CHECK-NEXT:    br i1 [[OR_COND1]], label [[FINAL_LEFT:%.*]], label [[FINAL_RIGHT:%.*]]
 ; CHECK:       pred1:
 ; CHECK-NEXT:    [[C2:%.*]] = icmp eq i8 [[V2:%.*]], 0
 ; CHECK-NEXT:    [[C3:%.*]] = icmp eq i8 [[V3]], 0
-; CHECK-NEXT:    [[OR_COND:%.*]] = and i1 [[C2]], [[C3]]
+; CHECK-NEXT:    [[OR_COND:%.*]] = select i1 [[C2]], i1 [[C3]], i1 false
 ; CHECK-NEXT:    br i1 [[OR_COND]], label [[FINAL_LEFT]], label [[FINAL_RIGHT]]
 ; CHECK:       final_left:
 ; CHECK-NEXT:    call void @sideeffect0()
 ; CHECK-NEXT:    ret void
 ; CHECK:       final_right:
 ; CHECK-NEXT:    call void @sideeffect1()
 ; CHECK-NEXT:    ret void
 ;

 ; More complex case, there's an extra op that is safe to execute unconditionally.
 
 define void @one_pred_with_extra_op(i8 %v0, i8 %v1) {
 ; CHECK-LABEL: @one_pred_with_extra_op(
 ; CHECK-NEXT:  pred:
 ; CHECK-NEXT:    [[C0:%.*]] = icmp eq i8 [[V0:%.*]], 0
 ; CHECK-NEXT:    [[V1_ADJ:%.*]] = add i8 [[V0]], [[V1:%.*]]
 ; CHECK-NEXT:    [[C1:%.*]] = icmp eq i8 [[V1_ADJ]], 0
-; CHECK-NEXT:    [[OR_COND:%.*]] = and i1 [[C0]], [[C1]]
+; CHECK-NEXT:    [[OR_COND:%.*]] = select i1 [[C0]], i1 [[C1]], i1 false
 ; CHECK-NEXT:    br i1 [[OR_COND]], label [[FINAL_LEFT:%.*]], label [[FINAL_RIGHT:%.*]]
 ; CHECK:       final_left:
 ; CHECK-NEXT:    call void @sideeffect0()
 ; CHECK-NEXT:    ret void
 ; CHECK:       final_right:
 ; CHECK-NEXT:    call void @sideeffect1()
 ; CHECK-NEXT:    ret void
 ;

 ; CHECK-LABEL: @two_preds_with_extra_op(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[C0:%.*]] = icmp eq i8 [[V0:%.*]], 0
 ; CHECK-NEXT:    br i1 [[C0]], label [[PRED0:%.*]], label [[PRED1:%.*]]
 ; CHECK:       pred0:
 ; CHECK-NEXT:    [[C1:%.*]] = icmp eq i8 [[V1:%.*]], 0
 ; CHECK-NEXT:    [[V3_ADJ_OLD:%.*]] = add i8 [[V1]], [[V2:%.*]]
 ; CHECK-NEXT:    [[C3_OLD:%.*]] = icmp eq i8 [[V3_ADJ_OLD]], 0
-; CHECK-NEXT:    [[OR_COND1:%.*]] = or i1 [[C1]], [[C3_OLD]]
+; CHECK-NEXT:    [[OR_COND1:%.*]] = select i1 [[C1]], i1 true, i1 [[C3_OLD]]
 ; CHECK-NEXT:    br i1 [[OR_COND1]], label [[FINAL_LEFT:%.*]], label [[FINAL_RIGHT:%.*]]
 ; CHECK:       pred1:
 ; CHECK-NEXT:    [[C2:%.*]] = icmp eq i8 [[V2]], 0
 ; CHECK-NEXT:    [[V3_ADJ:%.*]] = add i8 [[V1]], [[V2]]
 ; CHECK-NEXT:    [[C3:%.*]] = icmp eq i8 [[V3_ADJ]], 0
-; CHECK-NEXT:    [[OR_COND:%.*]] = and i1 [[C2]], [[C3]]
+; CHECK-NEXT:    [[OR_COND:%.*]] = select i1 [[C2]], i1 [[C3]], i1 false
 ; CHECK-NEXT:    br i1 [[OR_COND]], label [[FINAL_LEFT]], label [[FINAL_RIGHT]]
 ; CHECK:       final_left:
 ; CHECK-NEXT:    call void @sideeffect0()
 ; CHECK-NEXT:    ret void
 ; CHECK:       final_right:
 ; CHECK-NEXT:    call void @sideeffect1()
 ; CHECK-NEXT:    ret void
 ;

 
 define void @one_pred_with_extra_op_multiuse(i8 %v0, i8 %v1) {
 ; CHECK-LABEL: @one_pred_with_extra_op_multiuse(
 ; CHECK-NEXT:  pred:
 ; CHECK-NEXT:    [[C0:%.*]] = icmp eq i8 [[V0:%.*]], 0
 ; CHECK-NEXT:    [[V1_ADJ:%.*]] = add i8 [[V0]], [[V1:%.*]]
 ; CHECK-NEXT:    [[V1_ADJ_ADJ:%.*]] = add i8 [[V1_ADJ]], [[V1_ADJ]]
 ; CHECK-NEXT:    [[C1:%.*]] = icmp eq i8 [[V1_ADJ_ADJ]], 0
-; CHECK-NEXT:    [[OR_COND:%.*]] = and i1 [[C0]], [[C1]]
+; CHECK-NEXT:    [[OR_COND:%.*]] = select i1 [[C0]], i1 [[C1]], i1 false
 ; CHECK-NEXT:    br i1 [[OR_COND]], label [[FINAL_LEFT:%.*]], label [[FINAL_RIGHT:%.*]]
 ; CHECK:       final_left:
 ; CHECK-NEXT:    call void @sideeffect0()
 ; CHECK-NEXT:    ret void
 ; CHECK:       final_right:
 ; CHECK-NEXT:    call void @sideeffect1()
 ; CHECK-NEXT:    ret void
 ;

 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[C0:%.*]] = icmp eq i8 [[V0:%.*]], 0
 ; CHECK-NEXT:    br i1 [[C0]], label [[PRED0:%.*]], label [[PRED1:%.*]]
 ; CHECK:       pred0:
 ; CHECK-NEXT:    [[C1:%.*]] = icmp eq i8 [[V1:%.*]], 0
 ; CHECK-NEXT:    [[V3_ADJ_OLD:%.*]] = add i8 [[V1]], [[V2:%.*]]
 ; CHECK-NEXT:    [[V3_ADJ_ADJ_OLD:%.*]] = add i8 [[V3_ADJ_OLD]], [[V3_ADJ_OLD]]
 ; CHECK-NEXT:    [[C3_OLD:%.*]] = icmp eq i8 [[V3_ADJ_ADJ_OLD]], 0
-; CHECK-NEXT:    [[OR_COND1:%.*]] = or i1 [[C1]], [[C3_OLD]]
+; CHECK-NEXT:    [[OR_COND1:%.*]] = select i1 [[C1]], i1 true, i1 [[C3_OLD]]
 ; CHECK-NEXT:    br i1 [[OR_COND1]], label [[FINAL_LEFT:%.*]], label [[FINAL_RIGHT:%.*]]
 ; CHECK:       pred1:
 ; CHECK-NEXT:    [[C2:%.*]] = icmp eq i8 [[V2]], 0
 ; CHECK-NEXT:    [[V3_ADJ:%.*]] = add i8 [[V1]], [[V2]]
 ; CHECK-NEXT:    [[V3_ADJ_ADJ:%.*]] = add i8 [[V3_ADJ]], [[V3_ADJ]]
 ; CHECK-NEXT:    [[C3:%.*]] = icmp eq i8 [[V3_ADJ_ADJ]], 0
-; CHECK-NEXT:    [[OR_COND:%.*]] = and i1 [[C2]], [[C3]]
+; CHECK-NEXT:    [[OR_COND:%.*]] = select i1 [[C2]], i1 [[C3]], i1 false
 ; CHECK-NEXT:    br i1 [[OR_COND]], label [[FINAL_LEFT]], label [[FINAL_RIGHT]]
 ; CHECK:       final_left:
 ; CHECK-NEXT:    call void @sideeffect0()
 ; CHECK-NEXT:    ret void
 ; CHECK:       final_right:
 ; CHECK-NEXT:    call void @sideeffect1()
 ; CHECK-NEXT:    ret void
 ;

 ; and said op is live-out.
 
 define void @one_pred_with_extra_op_liveout(i8 %v0, i8 %v1) {
 ; CHECK-LABEL: @one_pred_with_extra_op_liveout(
 ; CHECK-NEXT:  pred:
 ; CHECK-NEXT:    [[C0:%.*]] = icmp eq i8 [[V0:%.*]], 0
 ; CHECK-NEXT:    [[V1_ADJ:%.*]] = add i8 [[V0]], [[V1:%.*]]
 ; CHECK-NEXT:    [[C1:%.*]] = icmp eq i8 [[V1_ADJ]], 0
-; CHECK-NEXT:    [[OR_COND:%.*]] = and i1 [[C0]], [[C1]]
+; CHECK-NEXT:    [[OR_COND:%.*]] = select i1 [[C0]], i1 [[C1]], i1 false
 ; CHECK-NEXT:    br i1 [[OR_COND]], label [[FINAL_LEFT:%.*]], label [[FINAL_RIGHT:%.*]]
 ; CHECK:       final_left:
 ; CHECK-NEXT:    call void @sideeffect0()
 ; CHECK-NEXT:    call void @use8(i8 [[V1_ADJ]])
 ; CHECK-NEXT:    ret void
 ; CHECK:       final_right:
 ; CHECK-NEXT:    call void @sideeffect1()
 ; CHECK-NEXT:    ret void
final_right:
   ret void
 }
 define void @one_pred_with_extra_op_liveout_multiuse(i8 %v0, i8 %v1) {
 ; CHECK-LABEL: @one_pred_with_extra_op_liveout_multiuse(
 ; CHECK-NEXT:  pred:
 ; CHECK-NEXT:    [[C0:%.*]] = icmp eq i8 [[V0:%.*]], 0
 ; CHECK-NEXT:    [[V1_ADJ:%.*]] = add i8 [[V0]], [[V1:%.*]]
 ; CHECK-NEXT:    [[C1:%.*]] = icmp eq i8 [[V1_ADJ]], 0
-; CHECK-NEXT:    [[OR_COND:%.*]] = and i1 [[C0]], [[C1]]
+; CHECK-NEXT:    [[OR_COND:%.*]] = select i1 [[C0]], i1 [[C1]], i1 false
 ; CHECK-NEXT:    br i1 [[OR_COND]], label [[FINAL_LEFT:%.*]], label [[FINAL_RIGHT:%.*]]
 ; CHECK:       final_left:
 ; CHECK-NEXT:    call void @sideeffect0()
 ; CHECK-NEXT:    call void @use8(i8 [[V1_ADJ]])
 ; CHECK-NEXT:    call void @use8(i8 [[V1_ADJ]])
 ; CHECK-NEXT:    ret void
 ; CHECK:       final_right:
 ; CHECK-NEXT:    call void @sideeffect1()

 ; CHECK-LABEL: @one_pred_with_extra_op_liveout_distant_phi(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[C0:%.*]] = icmp eq i8 [[V0:%.*]], 0
 ; CHECK-NEXT:    br i1 [[C0]], label [[PRED:%.*]], label [[LEFT_END:%.*]]
 ; CHECK:       pred:
 ; CHECK-NEXT:    [[C1:%.*]] = icmp eq i8 [[V1:%.*]], 0
 ; CHECK-NEXT:    [[V2_ADJ:%.*]] = add i8 [[V0]], [[V1]]
 ; CHECK-NEXT:    [[C2:%.*]] = icmp eq i8 [[V2_ADJ]], 0
-; CHECK-NEXT:    [[OR_COND:%.*]] = and i1 [[C1]], [[C2]]
+; CHECK-NEXT:    [[OR_COND:%.*]] = select i1 [[C1]], i1 [[C2]], i1 false
 ; CHECK-NEXT:    br i1 [[OR_COND]], label [[FINAL_LEFT:%.*]], label [[FINAL_RIGHT:%.*]]
 ; CHECK:       final_left:
 ; CHECK-NEXT:    call void @sideeffect0()
 ; CHECK-NEXT:    call void @use8(i8 [[V2_ADJ]])
 ; CHECK-NEXT:    br label [[LEFT_END]]
 ; CHECK:       left_end:
 ; CHECK-NEXT:    [[MERGE_LEFT:%.*]] = phi i8 [ [[V2_ADJ]], [[FINAL_LEFT]] ], [ 0, [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    call void @sideeffect1()

 ; CHECK-NEXT:    br i1 [[C0]], label [[PRED0:%.*]], label [[PRED1:%.*]]
 ; CHECK:       pred0:
 ; CHECK-NEXT:    [[C1:%.*]] = icmp eq i8 [[V1:%.*]], 0
 ; CHECK-NEXT:    br i1 [[C1]], label [[FINAL_LEFT:%.*]], label [[DISPATCH:%.*]]
 ; CHECK:       pred1:
 ; CHECK-NEXT:    [[C2:%.*]] = icmp eq i8 [[V2:%.*]], 0
 ; CHECK-NEXT:    [[V3_ADJ:%.*]] = add i8 [[V1]], [[V2]]
 ; CHECK-NEXT:    [[C3:%.*]] = icmp eq i8 [[V3_ADJ]], 0
-; CHECK-NEXT:    [[OR_COND:%.*]] = and i1 [[C2]], [[C3]]
+; CHECK-NEXT:    [[OR_COND:%.*]] = select i1 [[C2]], i1 [[C3]], i1 false
 ; CHECK-NEXT:    br i1 [[OR_COND]], label [[FINAL_LEFT]], label [[FINAL_RIGHT:%.*]]
 ; CHECK:       dispatch:
 ; CHECK-NEXT:    [[V3_ADJ_OLD:%.*]] = add i8 [[V1]], [[V2]]
 ; CHECK-NEXT:    [[C3_OLD:%.*]] = icmp eq i8 [[V3_ADJ_OLD]], 0
 ; CHECK-NEXT:    br i1 [[C3_OLD]], label [[FINAL_LEFT]], label [[FINAL_RIGHT]]
 ; CHECK:       final_left:
 ; CHECK-NEXT:    [[MERGE_LEFT:%.*]] = phi i8 [ [[V3_ADJ_OLD]], [[DISPATCH]] ], [ 0, [[PRED0]] ], [ [[V3_ADJ]], [[PRED1]] ]
 ; CHECK-NEXT:    call void @use8(i8 [[MERGE_LEFT]])

 ; CHECK-NEXT:    br i1 [[C0]], label [[PRED0:%.*]], label [[PRED1:%.*]]
 ; CHECK:       pred0:
 ; CHECK-NEXT:    [[C1:%.*]] = icmp eq i8 [[V1:%.*]], 0
 ; CHECK-NEXT:    br i1 [[C1]], label [[FINAL_LEFT:%.*]], label [[DISPATCH:%.*]]
 ; CHECK:       pred1:
 ; CHECK-NEXT:    [[C2:%.*]] = icmp eq i8 [[V2:%.*]], 0
 ; CHECK-NEXT:    [[V3_ADJ:%.*]] = add i8 [[V1]], [[V2]]
 ; CHECK-NEXT:    [[C3:%.*]] = icmp eq i8 [[V3_ADJ]], 0
-; CHECK-NEXT:    [[OR_COND:%.*]] = and i1 [[C2]], [[C3]]
+; CHECK-NEXT:    [[OR_COND:%.*]] = select i1 [[C2]], i1 [[C3]], i1 false
 ; CHECK-NEXT:    br i1 [[OR_COND]], label [[FINAL_LEFT]], label [[FINAL_RIGHT:%.*]]
 ; CHECK:       dispatch:
 ; CHECK-NEXT:    [[V3_ADJ_OLD:%.*]] = add i8 [[V1]], [[V2]]
 ; CHECK-NEXT:    [[C3_OLD:%.*]] = icmp eq i8 [[V3_ADJ_OLD]], 0
 ; CHECK-NEXT:    br i1 [[C3_OLD]], label [[FINAL_LEFT]], label [[FINAL_RIGHT]]
 ; CHECK:       final_left:
 ; CHECK-NEXT:    [[MERGE_LEFT:%.*]] = phi i8 [ [[V3_ADJ_OLD]], [[DISPATCH]] ], [ 0, [[PRED0]] ], [ [[V3_ADJ]], [[PRED1]] ]
 ; CHECK-NEXT:    [[MERGE_LEFT_2:%.*]] = phi i8 [ [[V3_ADJ_OLD]], [[DISPATCH]] ], [ 42, [[PRED0]] ], [ [[V3_ADJ]], [[PRED1]] ]

 ; and said op is live-out, and it is only used externally.
 
 define void @one_pred_with_extra_op_eexternally_used_only(i8 %v0, i8 %v1) {
 ; CHECK-LABEL: @one_pred_with_extra_op_eexternally_used_only(
 ; CHECK-NEXT:  pred:
 ; CHECK-NEXT:    [[C0:%.*]] = icmp eq i8 [[V0:%.*]], 0
 ; CHECK-NEXT:    [[V1_ADJ:%.*]] = add i8 [[V0]], [[V1:%.*]]
 ; CHECK-NEXT:    [[C1:%.*]] = icmp eq i8 [[V1]], 0
-; CHECK-NEXT:    [[OR_COND:%.*]] = and i1 [[C0]], [[C1]]
+; CHECK-NEXT:    [[OR_COND:%.*]] = select i1 [[C0]], i1 [[C1]], i1 false
 ; CHECK-NEXT:    br i1 [[OR_COND]], label [[FINAL_LEFT:%.*]], label [[FINAL_RIGHT:%.*]]
 ; CHECK:       final_left:
 ; CHECK-NEXT:    call void @sideeffect0()
 ; CHECK-NEXT:    call void @use8(i8 [[V1_ADJ]])
 ; CHECK-NEXT:    ret void
 ; CHECK:       final_right:
 ; CHECK-NEXT:    call void @sideeffect1()
 ; CHECK-NEXT:    ret void
final_right:
   ret void
 }
 define void @one_pred_with_extra_op_externally_used_only_multiuse(i8 %v0, i8 %v1) {
 ; CHECK-LABEL: @one_pred_with_extra_op_externally_used_only_multiuse(
 ; CHECK-NEXT:  pred:
 ; CHECK-NEXT:    [[C0:%.*]] = icmp eq i8 [[V0:%.*]], 0
 ; CHECK-NEXT:    [[V1_ADJ:%.*]] = add i8 [[V0]], [[V1:%.*]]
 ; CHECK-NEXT:    [[C1:%.*]] = icmp eq i8 [[V1]], 0
-; CHECK-NEXT:    [[OR_COND:%.*]] = and i1 [[C0]], [[C1]]
+; CHECK-NEXT:    [[OR_COND:%.*]] = select i1 [[C0]], i1 [[C1]], i1 false
 ; CHECK-NEXT:    br i1 [[OR_COND]], label [[FINAL_LEFT:%.*]], label [[FINAL_RIGHT:%.*]]
 ; CHECK:       final_left:
 ; CHECK-NEXT:    call void @sideeffect0()
 ; CHECK-NEXT:    call void @use8(i8 [[V1_ADJ]])
 ; CHECK-NEXT:    call void @use8(i8 [[V1_ADJ]])
 ; CHECK-NEXT:    ret void
 ; CHECK:       final_right:
 ; CHECK-NEXT:    call void @sideeffect1()

 ; CHECK-NEXT:    br i1 [[C0]], label [[PRED0:%.*]], label [[PRED1:%.*]]
 ; CHECK:       pred0:
 ; CHECK-NEXT:    [[C1:%.*]] = icmp eq i8 [[V1:%.*]], 0
 ; CHECK-NEXT:    br i1 [[C1]], label [[FINAL_LEFT:%.*]], label [[DISPATCH:%.*]]
 ; CHECK:       pred1:
 ; CHECK-NEXT:    [[C2:%.*]] = icmp eq i8 [[V2:%.*]], 0
 ; CHECK-NEXT:    [[V3_ADJ:%.*]] = add i8 [[V1]], [[V2]]
 ; CHECK-NEXT:    [[C3:%.*]] = icmp eq i8 [[V3:%.*]], 0
-; CHECK-NEXT:    [[OR_COND:%.*]] = and i1 [[C2]], [[C3]]
+; CHECK-NEXT:    [[OR_COND:%.*]] = select i1 [[C2]], i1 [[C3]], i1 false
 ; CHECK-NEXT:    br i1 [[OR_COND]], label [[FINAL_LEFT]], label [[FINAL_RIGHT:%.*]]
 ; CHECK:       dispatch:
 ; CHECK-NEXT:    [[V3_ADJ_OLD:%.*]] = add i8 [[V1]], [[V2]]
 ; CHECK-NEXT:    [[C3_OLD:%.*]] = icmp eq i8 [[V3]], 0
 ; CHECK-NEXT:    br i1 [[C3_OLD]], label [[FINAL_LEFT]], label [[FINAL_RIGHT]]
 ; CHECK:       final_left:
 ; CHECK-NEXT:    [[MERGE_LEFT:%.*]] = phi i8 [ [[V3_ADJ_OLD]], [[DISPATCH]] ], [ 0, [[PRED0]] ], [ [[V3_ADJ]], [[PRED1]] ]
 ; CHECK-NEXT:    call void @use8(i8 [[MERGE_LEFT]])

 ; CHECK-NEXT:    br i1 [[C0]], label [[PRED0:%.*]], label [[PRED1:%.*]]
 ; CHECK:       pred0:
 ; CHECK-NEXT:    [[C1:%.*]] = icmp eq i8 [[V1:%.*]], 0
 ; CHECK-NEXT:    br i1 [[C1]], label [[FINAL_LEFT:%.*]], label [[DISPATCH:%.*]]
 ; CHECK:       pred1:
 ; CHECK-NEXT:    [[C2:%.*]] = icmp eq i8 [[V2:%.*]], 0
 ; CHECK-NEXT:    [[V3_ADJ:%.*]] = add i8 [[V1]], [[V2]]
 ; CHECK-NEXT:    [[C3:%.*]] = icmp eq i8 [[V3:%.*]], 0
-; CHECK-NEXT:    [[OR_COND:%.*]] = and i1 [[C2]], [[C3]]
+; CHECK-NEXT:    [[OR_COND:%.*]] = select i1 [[C2]], i1 [[C3]], i1 false
 ; CHECK-NEXT:    br i1 [[OR_COND]], label [[FINAL_LEFT]], label [[FINAL_RIGHT:%.*]]
 ; CHECK:       dispatch:
 ; CHECK-NEXT:    [[V3_ADJ_OLD:%.*]] = add i8 [[V1]], [[V2]]
 ; CHECK-NEXT:    [[C3_OLD:%.*]] = icmp eq i8 [[V3]], 0
 ; CHECK-NEXT:    br i1 [[C3_OLD]], label [[FINAL_LEFT]], label [[FINAL_RIGHT]]
 ; CHECK:       final_left:
 ; CHECK-NEXT:    [[MERGE_LEFT:%.*]] = phi i8 [ [[V3_ADJ_OLD]], [[DISPATCH]] ], [ 0, [[PRED0]] ], [ [[V3_ADJ]], [[PRED1]] ]
 ; CHECK-NEXT:    [[MERGE_LEFT_2:%.*]] = phi i8 [ [[V3_ADJ_OLD]], [[DISPATCH]] ], [ 42, [[PRED0]] ], [ [[V3_ADJ]], [[PRED1]] ]

 ; CHECK-LABEL: @one_pred_with_extra_op_externally_used_only_after_cond_distant_phi(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[C0:%.*]] = icmp eq i8 [[V0:%.*]], 0
 ; CHECK-NEXT:    br i1 [[C0]], label [[PRED:%.*]], label [[LEFT_END:%.*]]
 ; CHECK:       pred:
 ; CHECK-NEXT:    [[C1:%.*]] = icmp eq i8 [[V1:%.*]], 0
 ; CHECK-NEXT:    [[C3:%.*]] = icmp eq i8 [[V3:%.*]], 0
 ; CHECK-NEXT:    [[V2_ADJ:%.*]] = add i8 [[V4:%.*]], [[V5:%.*]]
-; CHECK-NEXT:    [[OR_COND:%.*]] = and i1 [[C1]], [[C3]]
+; CHECK-NEXT:    [[OR_COND:%.*]] = select i1 [[C1]], i1 [[C3]], i1 false
 ; CHECK-NEXT:    br i1 [[OR_COND]], label [[FINAL_LEFT:%.*]], label [[FINAL_RIGHT:%.*]]
 ; CHECK:       final_left:
 ; CHECK-NEXT:    call void @sideeffect0()
 ; CHECK-NEXT:    call void @use8(i8 [[V2_ADJ]])
 ; CHECK-NEXT:    br label [[LEFT_END]]
 ; CHECK:       left_end:
 ; CHECK-NEXT:    [[MERGE_LEFT:%.*]] = phi i8 [ [[V2_ADJ]], [[FINAL_LEFT]] ], [ 0, [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    call void @sideeffect1()

 ; CHECK-NEXT:    br i1 [[C0]], label [[PRED0:%.*]], label [[PRED1:%.*]]
 ; CHECK:       pred0:
 ; CHECK-NEXT:    [[C1:%.*]] = icmp eq i8 [[V1:%.*]], 0
 ; CHECK-NEXT:    br i1 [[C1]], label [[FINAL_LEFT:%.*]], label [[DISPATCH:%.*]]
 ; CHECK:       pred1:
 ; CHECK-NEXT:    [[C2:%.*]] = icmp eq i8 [[V2:%.*]], 0
 ; CHECK-NEXT:    [[C3:%.*]] = icmp eq i8 [[V3:%.*]], 0
 ; CHECK-NEXT:    [[V3_ADJ:%.*]] = add i8 [[V4:%.*]], [[V5:%.*]]
-; CHECK-NEXT:    [[OR_COND:%.*]] = and i1 [[C2]], [[C3]]
+; CHECK-NEXT:    [[OR_COND:%.*]] = select i1 [[C2]], i1 [[C3]], i1 false
 ; CHECK-NEXT:    br i1 [[OR_COND]], label [[FINAL_LEFT]], label [[FINAL_RIGHT:%.*]]
 ; CHECK:       dispatch:
 ; CHECK-NEXT:    [[C3_OLD:%.*]] = icmp eq i8 [[V3]], 0
 ; CHECK-NEXT:    [[V3_ADJ_OLD:%.*]] = add i8 [[V4]], [[V5]]
 ; CHECK-NEXT:    br i1 [[C3_OLD]], label [[FINAL_LEFT]], label [[FINAL_RIGHT]]
 ; CHECK:       final_left:
 ; CHECK-NEXT:    [[MERGE_LEFT:%.*]] = phi i8 [ [[V3_ADJ_OLD]], [[DISPATCH]] ], [ 0, [[PRED0]] ], [ [[V3_ADJ]], [[PRED1]] ]
 ; CHECK-NEXT:    call void @use8(i8 [[MERGE_LEFT]])

 ; CHECK-NEXT:    [[DEC_OLD:%.*]] = add i8 [[COUNTDOWN]], -1
 ; CHECK-NEXT:    [[CMP_NOT_OLD:%.*]] = icmp eq i8 [[COUNTDOWN]], 0
 ; CHECK-NEXT:    br i1 [[CMP_NOT_OLD]], label [[IF_END_LOOPEXIT:%.*]], label [[FOR_BODYTHREAD_PRE_SPLIT]]
 ; CHECK:       if.then:
 ; CHECK-NEXT:    [[C2:%.*]] = call i1 @gen1()
 ; CHECK-NEXT:    [[C2_NOT:%.*]] = xor i1 [[C2]], true
 ; CHECK-NEXT:    [[DEC:%.*]] = add i8 [[COUNTDOWN]], -1
 ; CHECK-NEXT:    [[CMP_NOT:%.*]] = icmp eq i8 [[COUNTDOWN]], 0
-; CHECK-NEXT:    [[OR_COND:%.*]] = or i1 [[C2_NOT]], [[CMP_NOT]]
+; CHECK-NEXT:    [[OR_COND:%.*]] = select i1 [[C2_NOT]], i1 true, i1 [[CMP_NOT]]
 ; CHECK-NEXT:    br i1 [[OR_COND]], label [[IF_END_LOOPEXIT]], label [[FOR_BODYTHREAD_PRE_SPLIT]]
 ; CHECK:       for.bodythread-pre-split:
 ; CHECK-NEXT:    [[DEC_MERGE]] = phi i8 [ [[DEC]], [[IF_THEN]] ], [ [[DEC_OLD]], [[FOR_INC]] ]
 ; CHECK-NEXT:    call void @sideeffect0()
 ; CHECK-NEXT:    br label [[FOR_BODY]]
 ; CHECK:       if.end.loopexit:
 ; CHECK-NEXT:    ret void
 ;

 ; CHECK-NEXT:    [[DEC_OLD:%.*]] = add i8 [[COUNTDOWN]], -1
 ; CHECK-NEXT:    [[CMP_NOT_OLD:%.*]] = icmp eq i8 [[COUNTDOWN]], 0
 ; CHECK-NEXT:    br i1 [[CMP_NOT_OLD]], label [[IF_END_LOOPEXIT:%.*]], label [[FOR_BODYTHREAD_PRE_SPLIT]]
 ; CHECK:       if.then:
 ; CHECK-NEXT:    [[C2:%.*]] = call i1 @gen1()
 ; CHECK-NEXT:    [[C2_NOT:%.*]] = xor i1 [[C2]], true
 ; CHECK-NEXT:    [[DEC:%.*]] = add i8 [[COUNTDOWN]], -1
 ; CHECK-NEXT:    [[CMP_NOT:%.*]] = icmp eq i8 [[COUNTDOWN]], 0
-; CHECK-NEXT:    [[OR_COND:%.*]] = or i1 [[C2_NOT]], [[CMP_NOT]]
+; CHECK-NEXT:    [[OR_COND:%.*]] = select i1 [[C2_NOT]], i1 true, i1 [[CMP_NOT]]
 ; CHECK-NEXT:    br i1 [[OR_COND]], label [[IF_END_LOOPEXIT]], label [[FOR_BODYTHREAD_PRE_SPLIT]]
 ; CHECK:       for.bodythread-pre-split:
 ; CHECK-NEXT:    [[DEC_MERGE]] = phi i8 [ [[DEC_OLD]], [[FOR_INC]] ], [ [[DEC_MERGE]], [[FOR_BODYTHREAD_PRE_SPLIT_LOOPBACK:%.*]] ], [ [[DEC]], [[IF_THEN]] ]
 ; CHECK-NEXT:    [[SHOULD_LOOPBACK:%.*]] = phi i1 [ true, [[FOR_INC]] ], [ false, [[FOR_BODYTHREAD_PRE_SPLIT_LOOPBACK]] ], [ true, [[IF_THEN]] ]
 ; CHECK-NEXT:    [[DO_LOOPBACK:%.*]] = and i1 [[SHOULD_LOOPBACK]], [[ENABLE_LOOPBACK:%.*]]
 ; CHECK-NEXT:    call void @sideeffect0()
 ; CHECK-NEXT:    br i1 [[DO_LOOPBACK]], label [[FOR_BODYTHREAD_PRE_SPLIT_LOOPBACK]], label [[FOR_BODY]]
 ; CHECK:       for.bodythread-pre-split.loopback:

llvm/test/Transforms/SimplifyCFG/fold-debug-location.ll

 ; All instructions involved in folding have the same !dbg location. Make sure
 ; they are preserved.
 define void @dbg_all_equal(i32 %k, i32 %c1, i32 %c2) !dbg !17 {
 ; CHECK-LABEL: define {{.+}} @dbg_all_equal({{.+}}
 ; CHECK-NEXT:    [[A1:%[a-z0-9]+]] = and i32 %c1, %k, !dbg [[DBG:![0-9]+]]
 ; CHECK-NEXT:    [[C1:%[a-z0-9]+]] = icmp eq i32 [[A1]], 0, !dbg [[DBG]]
 ; CHECK-NEXT:    [[A2:%[a-z0-9]+]] = and i32 %c2, %k, !dbg [[DBG]]
 ; CHECK-NEXT:    [[C2:%[a-z0-9]+]] = icmp eq i32 [[A2]], 0, !dbg [[DBG]]
-; CHECK-NEXT:    [[OR:%[.a-z0-9]+]] = or i1 [[C1]], [[C2]], !dbg [[DBG]]
+; CHECK-NEXT:    [[OR:%[.a-z0-9]+]] = select i1 [[C1]], i1 true, i1 [[C2]], !dbg [[DBG]]
 ; CHECK-NEXT:    br i1 [[OR]], label {{.+}}, label {{.+}}, !dbg [[DBG]]
 ;
   %1 = and i32 %c1, %k, !dbg !18
   %2 = icmp eq i32 %1, 0, !dbg !18
   br i1 %2, label %8, label %3, !dbg !18
 
 3:
   %4 = and i32 %c2, %k, !dbg !18

llvm/test/Transforms/SimplifyCFG/preserve-branchweights.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -simplifycfg -simplifycfg-require-and-preserve-domtree=1 -S -o - < %s | FileCheck %s
 
 declare void @helper(i32)
 
 define void @test1(i1 %a, i1 %b) {
 ; CHECK-LABEL: @test1(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[A_NOT:%.*]] = xor i1 [[A:%.*]], true
 ; CHECK-NEXT:    [[C:%.*]] = or i1 [[B:%.*]], false
-; CHECK-NEXT:    [[OR_COND:%.*]] = and i1 [[A_NOT]], [[C]]
+; CHECK-NEXT:    [[OR_COND:%.*]] = select i1 [[A_NOT]], i1 [[C]], i1 false
 ; CHECK-NEXT:    br i1 [[OR_COND]], label [[Z:%.*]], label [[Y:%.*]], !prof !0
 ; CHECK:       Y:
 ; CHECK-NEXT:    call void @helper(i32 0)
 ; CHECK-NEXT:    ret void
 ; CHECK:       Z:
 ; CHECK-NEXT:    call void @helper(i32 1)
 ; CHECK-NEXT:    ret void
 ;

 
 ; Make sure the metadata name string is "branch_weights" before propagating it.
 
 define void @fake_weights(i1 %a, i1 %b) {
 ; CHECK-LABEL: @fake_weights(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[A_NOT:%.*]] = xor i1 [[A:%.*]], true
 ; CHECK-NEXT:    [[C:%.*]] = or i1 [[B:%.*]], false
-; CHECK-NEXT:    [[OR_COND:%.*]] = and i1 [[A_NOT]], [[C]]
+; CHECK-NEXT:    [[OR_COND:%.*]] = select i1 [[A_NOT]], i1 [[C]], i1 false
 ; CHECK-NEXT:    br i1 [[OR_COND]], label [[Z:%.*]], label [[Y:%.*]], !prof !1
 ; CHECK:       Y:
 ; CHECK-NEXT:    call void @helper(i32 0)
 ; CHECK-NEXT:    ret void
 ; CHECK:       Z:
 ; CHECK-NEXT:    call void @helper(i32 1)
 ; CHECK-NEXT:    ret void
 ;
Z:
   call void @helper(i32 1)
   ret void
 }
 
 define void @test2(i1 %a, i1 %b) {
 ; CHECK-LABEL: @test2(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[C:%.*]] = or i1 [[B:%.*]], false
-; CHECK-NEXT:    [[OR_COND:%.*]] = and i1 [[A:%.*]], [[C]]
+; CHECK-NEXT:    [[OR_COND:%.*]] = select i1 [[A:%.*]], i1 [[C]], i1 false
 ; CHECK-NEXT:    br i1 [[OR_COND]], label [[Z:%.*]], label [[Y:%.*]], !prof !2
 ; CHECK:       Y:
 ; CHECK-NEXT:    call void @helper(i32 0)
 ; CHECK-NEXT:    ret void
 ; CHECK:       Z:
 ; CHECK-NEXT:    call void @helper(i32 1)
 ; CHECK-NEXT:    ret void
 ;
Z:
   call void @helper(i32 1)
   ret void
 }
 
 define void @test3(i1 %a, i1 %b) {
 ; CHECK-LABEL: @test3(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[C:%.*]] = or i1 [[B:%.*]], false
-; CHECK-NEXT:    [[OR_COND:%.*]] = and i1 [[A:%.*]], [[C]]
+; CHECK-NEXT:    [[OR_COND:%.*]] = select i1 [[A:%.*]], i1 [[C]], i1 false
 ; CHECK-NEXT:    br i1 [[OR_COND]], label [[Z:%.*]], label [[Y:%.*]], !prof !1
 ; CHECK:       Y:
 ; CHECK-NEXT:    call void @helper(i32 0)
 ; CHECK-NEXT:    ret void
 ; CHECK:       Z:
 ; CHECK-NEXT:    call void @helper(i32 1)
 ; CHECK-NEXT:    ret void
 ;
Z:
   call void @helper(i32 1)
   ret void
 }
 
 define void @test4(i1 %a, i1 %b) {
 ; CHECK-LABEL: @test4(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[C:%.*]] = or i1 [[B:%.*]], false
-; CHECK-NEXT:    [[OR_COND:%.*]] = and i1 [[A:%.*]], [[C]]
+; CHECK-NEXT:    [[OR_COND:%.*]] = select i1 [[A:%.*]], i1 [[C]], i1 false
 ; CHECK-NEXT:    br i1 [[OR_COND]], label [[Z:%.*]], label [[Y:%.*]], !prof !1
 ; CHECK:       Y:
 ; CHECK-NEXT:    call void @helper(i32 0)
 ; CHECK-NEXT:    ret void
 ; CHECK:       Z:
 ; CHECK-NEXT:    call void @helper(i32 1)
 ; CHECK-NEXT:    ret void
 ;
sw.epilog:
   ret void
 }
 
 ;; This test is based on test1 but swapped the targets of the second branch.
 define void @test1_swap(i1 %a, i1 %b) {
 ; CHECK-LABEL: @test1_swap(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[C:%.*]] = or i1 [[B:%.*]], false
-; CHECK-NEXT:    [[OR_COND:%.*]] = or i1 [[A:%.*]], [[C]]
+; CHECK-NEXT:    [[OR_COND:%.*]] = select i1 [[A:%.*]], i1 true, i1 [[C]]
 ; CHECK-NEXT:    br i1 [[OR_COND]], label [[Y:%.*]], label [[Z:%.*]], !prof !5
 ; CHECK:       Y:
 ; CHECK-NEXT:    call void @helper(i32 0)
 ; CHECK-NEXT:    ret void
 ; CHECK:       Z:
 ; CHECK-NEXT:    call void @helper(i32 1)
 ; CHECK-NEXT:    ret void
 ;

 ; CHECK-NEXT:  for.cond:
 ; CHECK-NEXT:    br label [[FOR_COND2:%.*]]
 ; CHECK:       for.cond2:
 ; CHECK-NEXT:    [[I_1:%.*]] = phi i32 [ [[INC19:%.*]], [[FOR_INC:%.*]] ], [ 0, [[FOR_COND:%.*]] ]
 ; CHECK-NEXT:    [[BIT_0:%.*]] = phi i32 [ [[SHL:%.*]], [[FOR_INC]] ], [ 1, [[FOR_COND]] ]
 ; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp eq i32 [[BIT_0]], 0
 ; CHECK-NEXT:    [[V3:%.*]] = load i32, i32* @max_regno, align 4
 ; CHECK-NEXT:    [[CMP4:%.*]] = icmp eq i32 [[I_1]], [[V3]]
-; CHECK-NEXT:    [[OR_COND:%.*]] = or i1 [[TOBOOL]], [[CMP4]]
+; CHECK-NEXT:    [[OR_COND:%.*]] = select i1 [[TOBOOL]], i1 true, i1 [[CMP4]]
 ; CHECK-NEXT:    br i1 [[OR_COND]], label [[FOR_EXIT:%.*]], label [[FOR_INC]], !prof !11
 ; CHECK:       for.inc:
 ; CHECK-NEXT:    [[SHL]] = shl i32 [[BIT_0]], 1
 ; CHECK-NEXT:    [[INC19]] = add nsw i32 [[I_1]], 1
 ; CHECK-NEXT:    br label [[FOR_COND2]]
 ; CHECK:       for.exit:
 ; CHECK-NEXT:    ret void
 ;

llvm/test/Transforms/SimplifyCFG/switch_create-custom-dl.ll

return:                                           ; preds = %if.end, %if.then
   %retval.0 = phi i32 [ 1, %if.then ], [ 0, %if.end ]
   ret i32 %retval.0
 
 }
 
 define void @test12() nounwind {
 ; CHECK-LABEL: @test12(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[DOTOLD:%.*]] = icmp eq i32 undef, undef
-; CHECK-NEXT:    br i1 [[DOTOLD]], label [[BB55_US_US:%.*]], label [[MALFORMED:%.*]]
+; CHECK-NEXT:    [[A_OLD:%.*]] = icmp eq i32 undef, undef
+; CHECK-NEXT:    br i1 [[A_OLD]], label [[BB55_US_US:%.*]], label [[MALFORMED:%.*]]
 ; CHECK:       bb55.us.us:
 ; CHECK-NEXT:    [[B:%.*]] = icmp ugt i32 undef, undef
 ; CHECK-NEXT:    [[A:%.*]] = icmp eq i32 undef, undef
 ; CHECK-NEXT:    [[OR_COND:%.*]] = or i1 [[B]], [[A]]
 ; CHECK-NEXT:    br i1 [[OR_COND]], label [[BB55_US_US]], label [[MALFORMED]]
 ; CHECK:       malformed:
 ; CHECK-NEXT:    ret void
 ;