[SimplifyCFG] Hoist common instructions on Switch.

[DianQK]

Summary

Sink common instructions are not always performance friendly. We need to implement hoist common instructions on switch instruction to solve the following problem:

define i1 @foo(i64 %a, i64 %b, i64 %c, i64 %d) {
start:
  %test = icmp eq i64 %a, %d
  br i1 %test, label %switch_bb, label %exit

switch_bb:                                        ; preds = %start
  switch i64 %a, label %bb0 [
    i64 1, label %bb1
    i64 2, label %bb2
  ]

bb0:                                              ; preds = %switch_bb
  %0 = icmp eq i64 %b, %c
  br label %exit

bb1:                                              ; preds = %switch_bb
  %1 = icmp eq i64 %b, %c
  br label %exit

bb2:                                              ; preds = %switch_bb
  %2 = icmp eq i64 %b, %c
  br label %exit

exit:                                             ; preds = %bb2, %bb1, %bb0, %start
  %result = phi i1 [ false, %start ], [ %0, %bb0 ], [ %1, %bb1 ], [ %2, %bb2 ]
  ret i1 %result
}

The pre-commit test is D156617.

[DianQK]

Added isSafeToHoistInstr check, but still need to fix patchable-function-entry-bti.ll failure.

[nikic]

Is it possible to instead generalize the HoistThenElseCodeToIf() transform to not require exactly two successors, so it can support switch as well?

[DianQK]

In D155711#4517725, @nikic wrote:

Is it possible to instead generalize the HoistThenElseCodeToIf() transform to not require exactly two successors, so it can support switch as well?

I considered that possibility. I'm concerned that this might have an impact on compile time for the two successors.
But it's more a question of whether the reordering and debug instructions can be more profitable for the switch instruction.
Using the same analysis on multiple successors can become more complex. Too long compile time?
But adding some options to control these behaviors may be appropriate. So I'll give it a new try.

Also, I feel like checking if the debug command is the same is a bit much.

[DianQK]

Maybe I need to know more about D84108.

[DianQK]

Now we can work with the unreachable instruction.
I will try to merge a generic hoist common instructions and add some test cases.

[DianQK]

Merge hoist common instructions, except that the termination instruction is not completed.

[DianQK]

Add the hoistCommonCodeFromSuccessors method as a generic hoist common code implementation.
The existing test cases look like they all pass. More test cases for the switch statement may need to be added.
There may be some duplicate calculations that can be eliminated, such as shouldHoistCommonInstructions. But I think most of the code is done.

[XChy]

Nice work to me! Just some nits here.
Can you create two patches to better show the difference before/after transform?
The first patch includes your unoptimized testcases without the fold. (Your first commit)
The second patch includes your optimized testcases and your code for the fold. (Your second commit, which is based on your first commit)
And then let the first patch be the parent revision of the second patch through "Edit Related Revisions".

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

1549

Omit the braces of single-statement if/for.

llvm/test/Transforms/SimplifyCFG/hoist-common-code.ll

97

More positive/negative tests are needed.

[DianQK]

Split test cases and code changes into two commits.

[DianQK]

Remove redundant header files.

[DianQK]

In D155711#4544449, @XChy wrote:

Nice work to me! Just some nits here.
Can you create two patches to better show the difference before/after transform?
The first patch includes your unoptimized testcases without the fold. (Your first commit)
The second patch includes your optimized testcases and your code for the fold. (Your second commit, which is based on your first commit)
And then let the first patch be the parent revision of the second patch through "Edit Related Revisions".

Thanks, I tried it out.
Too busy this weekend to update this patch. But I've split the patch into two. It should look better now.
I should think carefully about test cases.

[DianQK]

Add more tests.

[DianQK]

Fixes backend-optimization-failure.cpp.
We should examine all instructions during each iteration to confirm the presence of a terminating one.

[DianQK]

Allows to hoist the side effect instruction.

[XChy]

LGTM. May commit it if no changes are requested by others in one day.

[nikic]

This looks pretty good to me. Only significant concern I have is the unreachable handling, which doesn't look quite correct to me.

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

1531

1556–1557

instuctions -> instructions

Also this sounds like it's a count of instructions, while this is really a SkipFlags bitmask.

1591–1597

1597

Unless I'm missing something, I don't think this code is correct in the case where instructions are skipped. E.g. if the block is something like call @not_willreturn; unreachable and we skip over the first instruction and then see the unreachable, it would not be correct to ignore this successor. Is there a test for this?

I think you need to do the removal of unreachable blocks before the main loop, so you only handle the case where there is only unreachable in the block, not any other instructions.

1617

I think this may misbehave in the following case: You have BB1 and BB2 with same debug info and BB3 with different. Then BB1 and BB3 will skip it, but BB2 won't.

So I think you want to first do a check whether all are identical, and then skip or not skip debug info.

1628

Omit braces for single line body.

1646

Could use all_of here.

1682

This == 0 on a statistic doesn't really make sense to me... This is a global variable, not just for this run of the function.

1700

Why does this use a set rather than a vector?

1753

Omit braces for one line if.

1763

SmallVector

1768

Can always use the second code path? Should also work for branches.

7152

Leftover?

[DianQK]

Thanks to @XChy and @nikic. I apologize for making so many code issues. (T.T)

[DianQK]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

1597

I moved this before the main loop to keep it simple. simplifyUnreachable and EarlyCSE have finished for this.

[DianQK]

Remove more braces.
Change remove_if to erase_if.

[DianQK]

Due to my rebase issue, re-update.

Probably due to my rebase last night causing https://reviews.llvm.org/D155711?vs=555039&id=555207#change-46AmBA3PEORL to get weird.

The full diff looks fine.

[DianQK]

ping @nikic
Will you continue to review here? Or should I migrate to GitHub?

[nikic]

This looks fine to me, but I think this is currently missing tests for the "hoist not first instruction" case for switch? We should have at least basic tests that this is supported and side effects are checked.

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

1571

I'd move this variable below the following if check (to before for (;;)).

1578

"hoist the instruction at the rest" -> "hoist instructions from the rest"?

1595

Drop llvm:: prefix.

1596

You are using iterator_range(SuccIterBegin, SuccIters.end()) in a lot of places. I think it may make sense to create a variable for this?

There is also make_first_range() to iterate over .first.

[DianQK]

Update as suggested.

[DianQK]

In D155711#4647910, @nikic wrote:

This looks fine to me, but I think this is currently missing tests for the "hoist not first instruction" case for switch? We should have at least basic tests that this is supported and side effects are checked.

Thanks. I added the switch variant to hoist-common-skip.ll.

[nikic]

LGTM, thanks!

[MaskRay]

Early heads-up we internally have identified a crash due to this change.

[MaskRay]

In D155711#4648928, @MaskRay wrote:

Early heads-up we internally have identified a crash due to this change.

I will try giving a reproduce later, but am reverting this now.

musttail call must precede a ret with an optional bitcast

[MaskRay]

In D155711#4648971, @MaskRay wrote:

In D155711#4648928, @MaskRay wrote:

Early heads-up we internally have identified a crash due to this change.

I will try giving a reproduce later, but am reverting this now.

musttail call must precede a ret with an optional bitcast

% cat x.ll
source_filename = "<stdin>"
target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"

define ptr @ham(ptr %arg, ptr %arg1, ptr %arg2, i64 %arg3, ptr %arg4, i64 %arg5) {
bb:
  %load = load i16, ptr %arg, align 2
  %and = and i16 %load, 1
  %icmp = icmp eq i16 %and, 0
  br i1 %icmp, label %bb7, label %bb6

bb6:                                              ; preds = %bb
  ret ptr null

bb7:                                              ; preds = %bb
  switch i16 %load, label %bb13 [
    i16 0, label %bb8
    i16 1, label %bb9
    i16 2, label %bb11
  ]

bb8:                                              ; preds = %bb7
  %call = musttail call ptr @zot(ptr %arg, ptr %arg1, ptr %arg2, i64 %arg3, ptr %arg4, i64 %arg5)
  ret ptr %call

bb9:                                              ; preds = %bb7
  %call10 = musttail call ptr @zot(ptr %arg, ptr %arg1, ptr %arg2, i64 %arg3, ptr %arg4, i64 %arg5)
  ret ptr %call10

bb11:                                             ; preds = %bb7
  %call12 = musttail call ptr @zot(ptr %arg, ptr %arg1, ptr %arg2, i64 %arg3, ptr %arg4, i64 %arg5)
  ret ptr %call12

bb13:                                             ; preds = %bb7
  unreachable
}

declare ptr @zot(ptr, ptr, ptr, i64, ptr, i64)
% opt -O2 -S < x.ll
musttail call must precede a ret with an optional bitcast
  %call = musttail call ptr @zot(ptr nonnull %arg, ptr %arg1, ptr %arg2, i64 %arg3, ptr %arg4, i64 %arg5)
LLVM ERROR: Broken module found, compilation aborted!
PLEASE submit a bug report to https://github.com/llvm/llvm-project/issues/ and include the crash backtrace.
...

[DianQK]

In D155711#4648971, @MaskRay wrote:

In D155711#4648928, @MaskRay wrote:

Early heads-up we internally have identified a crash due to this change.

I will try giving a reproduce later, but am reverting this now.

musttail call must precede a ret with an optional bitcast

Okay. Thank you for the reproduce.

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

class SimplifyCFGOpt {
   bool simplifyIndirectBr(IndirectBrInst *IBI);
   bool simplifyBranch(BranchInst *Branch, IRBuilder<> &Builder);
   bool simplifyUncondBranch(BranchInst *BI, IRBuilder<> &Builder);
   bool simplifyCondBranch(BranchInst *BI, IRBuilder<> &Builder);
 
   bool tryToSimplifyUncondBranchWithICmpInIt(ICmpInst *ICI,
                                              IRBuilder<> &Builder);
 
-  bool HoistThenElseCodeToIf(BranchInst *BI, bool EqTermsOnly);
+  bool hoistCommonCodeFromSuccessors(BasicBlock *BB, bool EqTermsOnly);
+  bool hoistSuccIdenticalTerminatorToSwitchOrIf(
+      Instruction *TI, Instruction *I1,
+      SmallVectorImpl<Instruction *> &OtherSuccTIs);
   bool SpeculativelyExecuteBB(BranchInst *BI, BasicBlock *ThenBB);
   bool SimplifyTerminatorOnSelect(Instruction *OldTerm, Value *Cond,
                                   BasicBlock *TrueBB, BasicBlock *FalseBB,
                                   uint32_t TrueWeight, uint32_t FalseWeight);
   bool SimplifyBranchOnICmpChain(BranchInst *BI, IRBuilder<> &Builder,
                                  const DataLayout &DL);
   bool SimplifySwitchOnSelect(SwitchInst *SI, SelectInst *Select);
   bool SimplifyIndirectBrOnSelect(IndirectBrInst *IBI, SelectInst *SI);
while (!Preds.empty()) {
 
     PerformValueComparisonIntoPredecessorFolding(TI, CV, PTI, Builder);
     Changed = true;
   }
   return Changed;
 }
 
 // If we would need to insert a select that uses the value of this invoke
-// (comments in HoistThenElseCodeToIf explain why we would need to do this), we
-// can't hoist the invoke, as there is nowhere to put the select in this case.
+// (comments in hoistSuccIdenticalTerminatorToSwitchOrIf explain why we would
+// need to do this), we can't hoist the invoke, as there is nowhere to put the
+// select in this case.
 static bool isSafeToHoistInvoke(BasicBlock *BB1, BasicBlock *BB2,
                                 Instruction *I1, Instruction *I2) {
   for (BasicBlock *Succ : successors(BB1)) {
     for (const PHINode &PN : Succ->phis()) {
       Value *BB1V = PN.getIncomingValueForBlock(BB1);
       Value *BB2V = PN.getIncomingValueForBlock(BB2);
       if (BB1V != BB2V && (BB1V == I1 || BB2V == I2)) {
         return false;
       }
     }
   }
   return true;
 }
 
-// Get interesting characteristics of instructions that `HoistThenElseCodeToIf`
-// didn't hoist. They restrict what kind of instructions can be reordered
-// across.
+// Get interesting characteristics of instructions that
+// `hoistCommonCodeFromSuccessors` didn't hoist. They restrict what kind of
+// instructions can be reordered across.
 enum SkipFlags {
   SkipReadMem = 1,
   SkipSideEffect = 2,
   SkipImplicitControlFlow = 4
 };
 
 static unsigned skippedInstrFlags(Instruction *I) {
   unsigned Flags = 0;
if (auto *J = dyn_cast<Instruction>(Op))
         return false;
   }
 
   return true;
 }
 
 static bool passingValueIsAlwaysUndefined(Value *V, Instruction *I, bool PtrValueMayBeModified = false);
 
-/// Helper function for HoistThenElseCodeToIf. Return true if identical
+/// Helper function for hoistCommonCodeFromSuccessors. Return true if identical
 /// instructions \p I1 and \p I2 can and should be hoisted.
 static bool shouldHoistCommonInstructions(Instruction *I1, Instruction *I2,
                                           const TargetTransformInfo &TTI) {
   // If we're going to hoist a call, make sure that the two instructions
   // we're commoning/hoisting are both marked with musttail, or neither of
   // them is marked as such. Otherwise, we might end up in a situation where
   // we hoist from a block where the terminator is a `ret` to a block where
   // the terminator is a `br`, and `musttail` calls expect to be followed by
if (CB1->cannotMerge() || CB1->isConvergent())
       return false;
   if (const auto *CB2 = dyn_cast<CallBase>(I2))
     if (CB2->cannotMerge() || CB2->isConvergent())
       return false;
 
   return true;
 }
 
-/// Given a conditional branch that goes to BB1 and BB2, hoist any common code
-/// in the two blocks up into the branch block. The caller of this function
-/// guarantees that BI's block dominates BB1 and BB2. If EqTermsOnly is given,
-/// only perform hoisting in case both blocks only contain a terminator. In that
-/// case, only the original BI will be replaced and selects for PHIs are added.
-bool SimplifyCFGOpt::HoistThenElseCodeToIf(BranchInst *BI, bool EqTermsOnly) {
+/// Hoist any common code in the successor blocks up into the block. This
+/// function guarantees that BB dominates all successors. If EqTermsOnly is
+/// given, only perform hoisting in case both blocks only contain a terminator.
+/// In that case, only the original BI will be replaced and selects for PHIs are
+/// added.
+bool SimplifyCFGOpt::hoistCommonCodeFromSuccessors(BasicBlock *BB,
+                                                   bool EqTermsOnly) {
   // This does very trivial matching, with limited scanning, to find identical
-  // instructions in the two blocks.  In particular, we don't want to get into
-  // O(M*N) situations here where M and N are the sizes of BB1 and BB2.  As
+  // instructions in the two blocks. In particular, we don't want to get into
+  // O(N1*N2*...) situations here where Ni are the sizes of these successors. As
   // such, we currently just scan for obviously identical instructions in an
   // identical order, possibly separated by the same number of non-identical
   // instructions.
-  BasicBlock *BB1 = BI->getSuccessor(0); // The true destination.
-  BasicBlock *BB2 = BI->getSuccessor(1); // The false destination
+  unsigned int SuccSize = succ_size(BB);
+  if (SuccSize < 2)
+    return false;
 
   // If either of the blocks has it's address taken, then we can't do this fold,
   // because the code we'd hoist would no longer run when we jump into the block
   // by it's address.
-  if (BB1->hasAddressTaken() || BB2->hasAddressTaken())
+  for (auto *Succ : successors(BB))
+    if (Succ->hasAddressTaken() || !Succ->getSinglePredecessor())
       return false;
 
-  BasicBlock::iterator BB1_Itr = BB1->begin();
-  BasicBlock::iterator BB2_Itr = BB2->begin();
+  auto *TI = BB->getTerminator();
 
-  Instruction *I1 = &*BB1_Itr++, *I2 = &*BB2_Itr++;
-  // Skip debug info if it is not identical.
-  DbgInfoIntrinsic *DBI1 = dyn_cast<DbgInfoIntrinsic>(I1);
-  DbgInfoIntrinsic *DBI2 = dyn_cast<DbgInfoIntrinsic>(I2);
-  if (!DBI1 || !DBI2 || !DBI1->isIdenticalToWhenDefined(DBI2)) {
-    while (isa<DbgInfoIntrinsic>(I1))
-      I1 = &*BB1_Itr++;
-    while (isa<DbgInfoIntrinsic>(I2))
-      I2 = &*BB2_Itr++;
-  }
-  if (isa<PHINode>(I1))
+  // The second of pair is a SkipFlags bitmask.
+  using SuccIterPair = std::pair<BasicBlock::iterator, unsigned>;
+  SmallVector<SuccIterPair, 8> SuccIters;
+  for (auto *Succ : successors(BB)) {
+    BasicBlock::iterator SuccItr = Succ->begin();
+    if (isa<PHINode>(*SuccItr))
       return false;
-
-  BasicBlock *BIParent = BI->getParent();
-
-  bool Changed = false;
-
-  auto _ = make_scope_exit([&]() {
-    if (Changed)
-      ++NumHoistCommonCode;
-  });
+    SuccIters.push_back(SuccIterPair(SuccItr, 0));
+  }
 
   // Check if only hoisting terminators is allowed. This does not add new
   // instructions to the hoist location.
   if (EqTermsOnly) {
     // Skip any debug intrinsics, as they are free to hoist.
-    auto *I1NonDbg = &*skipDebugIntrinsics(I1->getIterator());
-    auto *I2NonDbg = &*skipDebugIntrinsics(I2->getIterator());
-    if (!I1NonDbg->isIdenticalToWhenDefined(I2NonDbg))
-      return false;
-    if (!I1NonDbg->isTerminator())
+    for (auto &SuccIter : SuccIters) {
+      auto *INonDbg = &*skipDebugIntrinsics(SuccIter.first);
+      if (!INonDbg->isTerminator())
         return false;
+    }
     // Now we know that we only need to hoist debug intrinsics and the
     // terminator. Let the loop below handle those 2 cases.
   }
 
+  bool Changed = false;
+
   // Count how many instructions were not hoisted so far. There's a limit on how
   // many instructions we skip, serving as a compilation time control as well as
   // preventing excessive increase of life ranges.
   unsigned NumSkipped = 0;
-
-  // Record any skipped instuctions that may read memory, write memory or have
-  // side effects, or have implicit control flow.
-  unsigned SkipFlagsBB1 = 0;
-  unsigned SkipFlagsBB2 = 0;
+  // If we find an unreachable instruction at the beginning of a basic block, we
+  // can still hoist the instruction at the rest of the basic blocks.
+  if (SuccIters.size() > 2) {
+    llvm::erase_if(SuccIters, [](const auto &Pair) {
+      return isa<UnreachableInst>(Pair.first);
+    });
+    if (SuccIters.size() < 2)
+      return Changed;
+  }
 
   for (;;) {
+    auto *SuccIterBegin = SuccIters.begin();
+    auto &BB1Itr = *SuccIterBegin++;
+
+    Instruction *I1 = &*BB1Itr.first;
+    auto *BB1 = I1->getParent();
+
+    // Skip debug info if it is not identical.
+    bool AllDbgInstsAreIdentical = llvm::all_of(
+        iterator_range(SuccIterBegin, SuccIters.end()), [I1](const auto &Pair) {
+          Instruction *I2 = &*Pair.first;
+          return I1->isIdenticalToWhenDefined(I2);
+        });
+    if (!AllDbgInstsAreIdentical) {
+      while (isa<DbgInfoIntrinsic>(I1))
+        I1 = &*++BB1Itr.first;
+      for (auto &SuccIter : iterator_range(SuccIterBegin, SuccIters.end())) {
+        Instruction *I2 = &*SuccIter.first;
+        while (isa<DbgInfoIntrinsic>(I2))
+          I2 = &*++SuccIter.first;
+      }
+    }
+
+    bool AllInstsAreIdentical = true;
+    bool HasTerminator = I1->isTerminator();
+    for (auto &SuccIter : iterator_range(SuccIterBegin, SuccIters.end())) {
+      Instruction *I2 = &*SuccIter.first;
+      HasTerminator |= I2->isTerminator();
+      if (AllInstsAreIdentical && !I1->isIdenticalToWhenDefined(I2))
+        AllInstsAreIdentical = false;
+    }
+
     // If we are hoisting the terminator instruction, don't move one (making a
     // broken BB), instead clone it, and remove BI.
-    if (I1->isTerminator() || I2->isTerminator()) {
+    if (HasTerminator) {
       // If any instructions remain in the block, we cannot hoist terminators.
-      if (NumSkipped || !I1->isIdenticalToWhenDefined(I2))
+      if (NumSkipped || SuccSize != SuccIters.size() || !AllInstsAreIdentical)
         return Changed;
-      goto HoistTerminator;
+      SmallVector<Instruction *, 8> Insts;
+      for (auto &SuccIter : iterator_range(SuccIterBegin, SuccIters.end()))
+        Insts.push_back(&*SuccIter.first);
+      return hoistSuccIdenticalTerminatorToSwitchOrIf(TI, I1, Insts) || Changed;
     }
 
-    if (I1->isIdenticalToWhenDefined(I2) &&
-        // Even if the instructions are identical, it may not be safe to hoist
-        // them if we have skipped over instructions with side effects or their
-        // operands weren't hoisted.
+    if (AllInstsAreIdentical) {
+      unsigned SkipFlagsBB1 = BB1Itr.second;
+      AllInstsAreIdentical =
           isSafeToHoistInstr(I1, SkipFlagsBB1) &&
-        isSafeToHoistInstr(I2, SkipFlagsBB2) &&
-        shouldHoistCommonInstructions(I1, I2, TTI)) {
-      if (isa<DbgInfoIntrinsic>(I1) || isa<DbgInfoIntrinsic>(I2)) {
-        assert(isa<DbgInfoIntrinsic>(I1) && isa<DbgInfoIntrinsic>(I2));
+          llvm::all_of(iterator_range(SuccIterBegin, SuccIters.end()),
+                       [=](const auto &Pair) {
+                         Instruction *I2 = &*Pair.first;
+                         unsigned SkipFlagsBB2 = Pair.second;
+                         // Even if the instructions are identical, it may not
+                         // be safe to hoist them if we have skipped over
+                         // instructions with side effects or their operands
+                         // weren't hoisted.
+                         return isSafeToHoistInstr(I2, SkipFlagsBB2) &&
+                                shouldHoistCommonInstructions(I1, I2, TTI);
+                       });
+    }
+
+    if (AllInstsAreIdentical) {
+      BB1Itr.first++;
+      if (isa<DbgInfoIntrinsic>(I1)) {
         // The debug location is an integral part of a debug info intrinsic
         // and can't be separated from it or replaced.  Instead of attempting
         // to merge locations, simply hoist both copies of the intrinsic.
-        BIParent->splice(BI->getIterator(), BB1, I1->getIterator());
-        BIParent->splice(BI->getIterator(), BB2, I2->getIterator());
+        BB->splice(TI->getIterator(), BB1, I1->getIterator());
+        for (auto &SuccIter : iterator_range(SuccIterBegin, SuccIters.end())) {
+          auto *I2 = &*SuccIter.first++;
+          assert(isa<DbgInfoIntrinsic>(I2));
+          BB->splice(TI->getIterator(), I2->getParent(), I2->getIterator());
+        }
       } else {
         // For a normal instruction, we just move one to right before the
         // branch, then replace all uses of the other with the first.  Finally,
         // we remove the now redundant second instruction.
-        BIParent->splice(BI->getIterator(), BB1, I1->getIterator());
+        BB->splice(TI->getIterator(), BB1, I1->getIterator());
+        for (auto &SuccIter : iterator_range(SuccIterBegin, SuccIters.end())) {
+          Instruction *I2 = &*SuccIter.first++;
+          assert(I2 != I1);
           if (!I2->use_empty())
             I2->replaceAllUsesWith(I1);
           I1->andIRFlags(I2);
           combineMetadataForCSE(I1, I2, true);
 
           // I1 and I2 are being combined into a single instruction.  Its debug
           // location is the merged locations of the original instructions.
           I1->applyMergedLocation(I1->getDebugLoc(), I2->getDebugLoc());
-
           I2->eraseFromParent();
         }
+      }
+      if (!Changed)
+        NumHoistCommonCode += SuccIters.size();
       Changed = true;
-      ++NumHoistCommonInstrs;
+      NumHoistCommonInstrs += SuccIters.size();
     } else {
       if (NumSkipped >= HoistCommonSkipLimit)
         return Changed;
       // We are about to skip over a pair of non-identical instructions. Record
       // if any have characteristics that would prevent reordering instructions
       // across them.
-      SkipFlagsBB1 |= skippedInstrFlags(I1);
-      SkipFlagsBB2 |= skippedInstrFlags(I2);
+      for (auto &SuccIter : SuccIters) {
+        Instruction *I = &*SuccIter.first++;
+        SuccIter.second |= skippedInstrFlags(I);
+      }
       ++NumSkipped;
     }
-
-    I1 = &*BB1_Itr++;
-    I2 = &*BB2_Itr++;
-    // Skip debug info if it is not identical.
-    DbgInfoIntrinsic *DBI1 = dyn_cast<DbgInfoIntrinsic>(I1);
-    DbgInfoIntrinsic *DBI2 = dyn_cast<DbgInfoIntrinsic>(I2);
-    if (!DBI1 || !DBI2 || !DBI1->isIdenticalToWhenDefined(DBI2)) {
-      while (isa<DbgInfoIntrinsic>(I1))
-        I1 = &*BB1_Itr++;
-      while (isa<DbgInfoIntrinsic>(I2))
-        I2 = &*BB2_Itr++;
-    }
-  }
 
-  return Changed;
+bool SimplifyCFGOpt::hoistSuccIdenticalTerminatorToSwitchOrIf(
+    Instruction *TI, Instruction *I1,
+    SmallVectorImpl<Instruction *> &OtherSuccTIs) {
+
+  auto *BI = dyn_cast<BranchInst>(TI);
+
+  bool Changed = false;
+  BasicBlock *TIParent = TI->getParent();
+  BasicBlock *BB1 = I1->getParent();
+
+  // Use only for an if statement.
+  auto *I2 = *OtherSuccTIs.begin();
+  auto *BB2 = I2->getParent();
+  if (BI) {
+    assert(OtherSuccTIs.size() == 1);
+    assert(BI->getSuccessor(0) == I1->getParent());
+    assert(BI->getSuccessor(1) == I2->getParent());
+  }
 
-HoistTerminator:
-  // It may not be possible to hoist an invoke.
+  // In the case of an if statement, we try to hoist an invoke.
   // FIXME: Can we define a safety predicate for CallBr?
-  if (isa<InvokeInst>(I1) && !isSafeToHoistInvoke(BB1, BB2, I1, I2))
-    return Changed;
+  // FIXME: Test case llvm/test/Transforms/SimplifyCFG/2009-06-15-InvokeCrash.ll
+  // removed in 4c923b3b3fd0ac1edebf0603265ca3ba51724937 commit?
+  if (isa<InvokeInst>(I1) && (!BI || !isSafeToHoistInvoke(BB1, BB2, I1, I2)))
+    return false;
 
   // TODO: callbr hoisting currently disabled pending further study.
   if (isa<CallBrInst>(I1))
-    return Changed;
+    return false;
 
   for (BasicBlock *Succ : successors(BB1)) {
     for (PHINode &PN : Succ->phis()) {
       Value *BB1V = PN.getIncomingValueForBlock(BB1);
-      Value *BB2V = PN.getIncomingValueForBlock(BB2);
+      for (Instruction *OtherSuccTI : OtherSuccTIs) {
+        Value *BB2V = PN.getIncomingValueForBlock(OtherSuccTI->getParent());
         if (BB1V == BB2V)
           continue;
 
-      // Check for passingValueIsAlwaysUndefined here because we would rather
-      // eliminate undefined control flow then converting it to a select.
-      if (passingValueIsAlwaysUndefined(BB1V, &PN) ||
+        // In the case of an if statement, check for
+        // passingValueIsAlwaysUndefined here because we would rather eliminate
+        // undefined control flow then converting it to a select.
+        if (!BI || passingValueIsAlwaysUndefined(BB1V, &PN) ||
             passingValueIsAlwaysUndefined(BB2V, &PN))
-        return Changed;
+          return false;
+      }
     }
   }
 
   // Okay, it is safe to hoist the terminator.
   Instruction *NT = I1->clone();
-  NT->insertInto(BIParent, BI->getIterator());
+  NT->insertInto(TIParent, TI->getIterator());
   if (!NT->getType()->isVoidTy()) {
     I1->replaceAllUsesWith(NT);
-    I2->replaceAllUsesWith(NT);
+    for (Instruction *OtherSuccTI : OtherSuccTIs)
+      OtherSuccTI->replaceAllUsesWith(NT);
     NT->takeName(I1);
   }
   Changed = true;
-  ++NumHoistCommonInstrs;
+  NumHoistCommonInstrs += OtherSuccTIs.size() + 1;
 
   // Ensure terminator gets a debug location, even an unknown one, in case
   // it involves inlinable calls.
-  NT->applyMergedLocation(I1->getDebugLoc(), I2->getDebugLoc());
+  SmallVector<DILocation *, 4> Locs;
+  Locs.push_back(I1->getDebugLoc());
+  for (auto *OtherSuccTI : OtherSuccTIs)
+    Locs.push_back(OtherSuccTI->getDebugLoc());
+  NT->setDebugLoc(DILocation::getMergedLocations(Locs));
 
   // PHIs created below will adopt NT's merged DebugLoc.
   IRBuilder<NoFolder> Builder(NT);
 
-  // Hoisting one of the terminators from our successor is a great thing.
-  // Unfortunately, the successors of the if/else blocks may have PHI nodes in
-  // them.  If they do, all PHI entries for BB1/BB2 must agree for all PHI
-  // nodes, so we insert select instruction to compute the final result.
+  // In the case of an if statement, hoisting one of the terminators from our
+  // successor is a great thing. Unfortunately, the successors of the if/else
+  // blocks may have PHI nodes in them.  If they do, all PHI entries for BB1/BB2
+  // must agree for all PHI nodes, so we insert select instruction to compute
+  // the final result.
+  if (BI) {
     std::map<std::pair<Value *, Value *>, SelectInst *> InsertedSelects;
     for (BasicBlock *Succ : successors(BB1)) {
       for (PHINode &PN : Succ->phis()) {
         Value *BB1V = PN.getIncomingValueForBlock(BB1);
         Value *BB2V = PN.getIncomingValueForBlock(BB2);
         if (BB1V == BB2V)
           continue;
 
         // These values do not agree.  Insert a select instruction before NT
         // that determines the right value.
         SelectInst *&SI = InsertedSelects[std::make_pair(BB1V, BB2V)];
         if (!SI) {
           // Propagate fast-math-flags from phi node to its replacement select.
           IRBuilder<>::FastMathFlagGuard FMFGuard(Builder);
           if (isa<FPMathOperator>(PN))
             Builder.setFastMathFlags(PN.getFastMathFlags());
 
-        SI = cast<SelectInst>(
-            Builder.CreateSelect(BI->getCondition(), BB1V, BB2V,
-                                 BB1V->getName() + "." + BB2V->getName(), BI));
+          SI = cast<SelectInst>(Builder.CreateSelect(
+              BI->getCondition(), BB1V, BB2V,
         }
 
         // Make the PHI node use the select for all incoming values for BB1/BB2
         for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
           if (PN.getIncomingBlock(i) == BB1 || PN.getIncomingBlock(i) == BB2)
             PN.setIncomingValue(i, SI);
       }
     }
+  }
 
   SmallVector<DominatorTree::UpdateType, 4> Updates;
 
   // Update any PHI nodes in our new successors.
   for (BasicBlock *Succ : successors(BB1)) {
-    AddPredecessorToBlock(Succ, BIParent, BB1);
+    AddPredecessorToBlock(Succ, TIParent, BB1);
     if (DTU)
-      Updates.push_back({DominatorTree::Insert, BIParent, Succ});
+      Updates.push_back({DominatorTree::Insert, TIParent, Succ});
   }
 
   if (DTU)
-    for (BasicBlock *Succ : successors(BI))
-      Updates.push_back({DominatorTree::Delete, BIParent, Succ});
+    for (BasicBlock *Succ : successors(TI))
+      Updates.push_back({DominatorTree::Delete, TIParent, Succ});
 
-  EraseTerminatorAndDCECond(BI);
+  EraseTerminatorAndDCECond(TI);
   if (DTU)
     DTU->applyUpdates(Updates);
   return Changed;
 }
 
 // Check lifetime markers.
 static bool isLifeTimeMarker(const Instruction *I) {
   if (auto II = dyn_cast<IntrinsicInst>(I)) {
TargetTransformInfo::TargetCostKind CostKind =
     ? TargetTransformInfo::TCK_CodeSize
     : TargetTransformInfo::TCK_SizeAndLatency;
 
   bool HaveRewritablePHIs = false;
   for (PHINode &PN : EndBB->phis()) {
     Value *OrigV = PN.getIncomingValueForBlock(BB);
     Value *ThenV = PN.getIncomingValueForBlock(ThenBB);
 
-    // FIXME: Try to remove some of the duplication with HoistThenElseCodeToIf.
-    // Skip PHIs which are trivial.
+    // FIXME: Try to remove some of the duplication with
+    // hoistCommonCodeFromSuccessors. Skip PHIs which are trivial.
     if (ThenV == OrigV)
       continue;
 
     Cost += TTI.getCmpSelInstrCost(Instruction::Select, PN.getType(), nullptr,
                                    CmpInst::BAD_ICMP_PREDICATE, CostKind);
 
     // Don't convert to selects if we could remove undefined behavior instead.
     if (passingValueIsAlwaysUndefined(OrigV, &PN) ||
bool SimplifyCFGOpt::simplifySwitch(SwitchInst *SI, IRBuilder<> &Builder) {
   // optimisation pipeline.
   if (Options.ConvertSwitchToLookupTable &&
       SwitchToLookupTable(SI, Builder, DTU, DL, TTI))
     return requestResimplify();
 
   if (ReduceSwitchRange(SI, Builder, DL, TTI))
     return requestResimplify();
 
+  if (HoistCommon &&
+      hoistCommonCodeFromSuccessors(SI->getParent(), !Options.HoistCommonInsts))
+    return requestResimplify();
+
   return false;
 }
 
 bool SimplifyCFGOpt::simplifyIndirectBr(IndirectBrInst *IBI) {
   BasicBlock *BB = IBI->getParent();
   bool Changed = false;
 
   // Eliminate redundant destinations.
if (Options.SpeculateBlocks &&
     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()) {
-      if (HoistCommon && HoistThenElseCodeToIf(BI, !Options.HoistCommonInsts))
+      if (HoistCommon && hoistCommonCodeFromSuccessors(
+                             BI->getParent(), !Options.HoistCommonInsts))
         return requestResimplify();
     } else {
       // If Successor #1 has multiple preds, we may be able to conditionally
       // execute Successor #0 if it branches to Successor #1.
       Instruction *Succ0TI = BI->getSuccessor(0)->getTerminator();
       if (Succ0TI->getNumSuccessors() == 1 &&
           Succ0TI->getSuccessor(0) == BI->getSuccessor(1))
         if (SpeculativelyExecuteBB(BI, BI->getSuccessor(0)))
           return requestResimplify();
     }

llvm/test/CodeGen/AArch64/patchable-function-entry-bti.ll

 entry:
   switch i64 %v, label %sw.bb0 [
     i64 1, label %sw.bb1
     i64 2, label %sw.bb2
     i64 3, label %sw.bb3
     i64 4, label %sw.bb4
   ]
 sw.bb0:
-  call void asm sideeffect "", ""()
+  call void asm sideeffect "nop", ""()
   ret void
 sw.bb1:
   call void asm sideeffect "", ""()
   ret void
 sw.bb2:
   call void asm sideeffect "", ""()
   ret void
 sw.bb3:

llvm/test/Transforms/SimplifyCFG/HoistCode.ll

T:              ; preds = %0
   ret void
 F:              ; preds = %0
   store i32 7, ptr %P
   ret void
 }
 
 define void @foo_switch(i64 %C, ptr %P) {
 ; CHECK-LABEL: @foo_switch(
-; CHECK-NEXT:    switch i64 [[C:%.*]], label [[BB0:%.*]] [
-; CHECK-NEXT:    i64 1, label [[BB1:%.*]]
-; CHECK-NEXT:    i64 2, label [[BB2:%.*]]
-; CHECK-NEXT:    ]
-; CHECK:       common.ret:
-; CHECK-NEXT:    ret void
-; CHECK:       bb0:
+; CHECK-NEXT:  common.ret:
 ; CHECK-NEXT:    store i32 7, ptr [[P:%.*]], align 4
-; CHECK-NEXT:    br label [[COMMON_RET:%.*]]
-; CHECK:       bb1:
-; CHECK-NEXT:    store i32 7, ptr [[P]], align 4
-; CHECK-NEXT:    br label [[COMMON_RET]]
-; CHECK:       bb2:
-; CHECK-NEXT:    store i32 7, ptr [[P]], align 4
-; CHECK-NEXT:    br label [[COMMON_RET]]
+; CHECK-NEXT:    ret void
 ;
   switch i64 %C, label %bb0 [
   i64 1, label %bb1
   i64 2, label %bb2
   ]
 bb0:              ; preds = %0
   store i32 7, ptr %P
   ret void

llvm/test/Transforms/SimplifyCFG/hoist-common-code-with-unreachable.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -passes='simplifycfg<hoist-common-insts;no-sink-common-insts>' -simplifycfg-require-and-preserve-domtree=1 -S | FileCheck %s
 
 define i1 @common_instr_with_unreachable(i64 %a, i64 %b, i64 %c) {
 ; CHECK-LABEL: @common_instr_with_unreachable(
 ; CHECK-NEXT:  start:
-; CHECK-NEXT:    switch i64 [[A:%.*]], label [[UNREACHABLE:%.*]] [
-; CHECK-NEXT:    i64 0, label [[BB0:%.*]]
-; CHECK-NEXT:    i64 1, label [[BB1:%.*]]
-; CHECK-NEXT:    i64 2, label [[BB2:%.*]]
-; CHECK-NEXT:    ]
-; CHECK:       unreachable:
-; CHECK-NEXT:    unreachable
-; CHECK:       bb0:
 ; CHECK-NEXT:    [[TMP0:%.*]] = icmp eq i64 [[B:%.*]], [[C:%.*]]
-; CHECK-NEXT:    br label [[EXIT:%.*]]
-; CHECK:       bb1:
-; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i64 [[B]], [[C]]
-; CHECK-NEXT:    br label [[EXIT]]
-; CHECK:       bb2:
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i64 [[B]], [[C]]
-; CHECK-NEXT:    br label [[EXIT]]
-; CHECK:       exit:
-; CHECK-NEXT:    [[RESULT:%.*]] = phi i1 [ [[TMP0]], [[BB0]] ], [ [[TMP1]], [[BB1]] ], [ [[TMP2]], [[BB2]] ]
-; CHECK-NEXT:    ret i1 [[RESULT]]
+; CHECK-NEXT:    ret i1 [[TMP0]]
 ;
 start:
   switch i64 %a, label %unreachable [
   i64 0, label %bb0
   i64 1, label %bb1
   i64 2, label %bb2
   ]
 

 exit:                                             ; preds = %bb2, %bb1, %bb0
   %result = phi i1 [ %0, %bb0 ], [ %1, %bb1 ], [ %2, %bb2 ]
   ret i1 %result
 }
 
 define i1 @common_instr_with_unreachable_2(i64 %a, i64 %b, i64 %c) {
 ; CHECK-LABEL: @common_instr_with_unreachable_2(
 ; CHECK-NEXT:  start:
-; CHECK-NEXT:    switch i64 [[A:%.*]], label [[BB1:%.*]] [
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp eq i64 [[B:%.*]], [[C:%.*]]
+; CHECK-NEXT:    ret i1 [[TMP0]]
+;
+start:
+  switch i64 %a, label %bb1 [
+  i64 0, label %bb0
+  i64 1, label %unreachable
+  i64 2, label %bb2
+  ]
+
+unreachable:
+  unreachable
+
+bb0:                                              ; preds = %start
+  %0 = icmp eq i64 %b, %c
+  br label %exit
+
+bb1:                                              ; preds = %start
+  %1 = icmp eq i64 %b, %c
+  br label %exit
+
+bb2:                                              ; preds = %start
+  %2 = icmp eq i64 %b, %c
+  br label %exit
+
+exit:                                             ; preds = %bb2, %bb1, %bb0
+  %result = phi i1 [ %0, %bb0 ], [ %1, %bb1 ], [ %2, %bb2 ]
+  ret i1 %result
+}
+
+declare void @no_return()
+declare void @foo()
+
+define i1 @not_only_unreachable(i64 %a, i64 %b, i64 %c) {
+; CHECK-LABEL: @not_only_unreachable(
+; CHECK-NEXT:  start:
+; CHECK-NEXT:    switch i64 [[A:%.*]], label [[UNREACHABLE:%.*]] [
 ; CHECK-NEXT:    i64 0, label [[BB0:%.*]]
+; CHECK-NEXT:    i64 1, label [[BB1:%.*]]
 ; CHECK-NEXT:    i64 2, label [[BB2:%.*]]
 ; CHECK-NEXT:    ]
+; CHECK:       unreachable:
+; CHECK-NEXT:    call void @no_return()
+; CHECK-NEXT:    unreachable
 ; CHECK:       bb0:
 ; CHECK-NEXT:    [[TMP0:%.*]] = icmp eq i64 [[B:%.*]], [[C:%.*]]
+; CHECK-NEXT:    call void @foo()
 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 ; CHECK:       bb1:
 ; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i64 [[B]], [[C]]
+; CHECK-NEXT:    call void @foo()
 ; CHECK-NEXT:    br label [[EXIT]]
 ; CHECK:       bb2:
 ; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i64 [[B]], [[C]]
+; CHECK-NEXT:    call void @foo()
 ; CHECK-NEXT:    br label [[EXIT]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[RESULT:%.*]] = phi i1 [ [[TMP0]], [[BB0]] ], [ [[TMP1]], [[BB1]] ], [ [[TMP2]], [[BB2]] ]
 ; CHECK-NEXT:    ret i1 [[RESULT]]
 ;
 start:
-  switch i64 %a, label %bb1 [
+  switch i64 %a, label %unreachable [
   i64 0, label %bb0
-  i64 1, label %unreachable
+  i64 1, label %bb1
   i64 2, label %bb2
   ]
 
 unreachable:
+  call void @no_return()
   unreachable
 
 bb0:                                              ; preds = %start
   %0 = icmp eq i64 %b, %c
+  call void @foo()
   br label %exit
 
 bb1:                                              ; preds = %start
   %1 = icmp eq i64 %b, %c
+  call void @foo()
   br label %exit
 
 bb2:                                              ; preds = %start
   %2 = icmp eq i64 %b, %c
+  call void @foo()
   br label %exit
 
 exit:                                             ; preds = %bb2, %bb1, %bb0
   %result = phi i1 [ %0, %bb0 ], [ %1, %bb1 ], [ %2, %bb2 ]
   ret i1 %result
 }

llvm/test/Transforms/SimplifyCFG/hoist-common-code.ll

F:              ; preds = %0
   store i32 1, ptr %Q
   %B = load i32, ptr %Q               ; <i32> [#uses=1]
   call void @bar( i32 %B )
   ret void
 }
 
 define void @test_switch(i64 %i, ptr %Q) {
 ; CHECK-LABEL: @test_switch(
-; CHECK-NEXT:    switch i64 [[I:%.*]], label [[BB0:%.*]] [
-; CHECK-NEXT:    i64 1, label [[BB1:%.*]]
-; CHECK-NEXT:    i64 2, label [[BB2:%.*]]
-; CHECK-NEXT:    ]
-; CHECK:       common.ret:
-; CHECK-NEXT:    ret void
-; CHECK:       bb0:
+; CHECK-NEXT:  common.ret:
 ; CHECK-NEXT:    store i32 1, ptr [[Q:%.*]], align 4
 ; CHECK-NEXT:    [[A:%.*]] = load i32, ptr [[Q]], align 4
 ; CHECK-NEXT:    call void @bar(i32 [[A]])
-; CHECK-NEXT:    br label [[COMMON_RET:%.*]]
-; CHECK:       bb1:
-; CHECK-NEXT:    store i32 1, ptr [[Q]], align 4
-; CHECK-NEXT:    [[B:%.*]] = load i32, ptr [[Q]], align 4
-; CHECK-NEXT:    call void @bar(i32 [[B]])
-; CHECK-NEXT:    br label [[COMMON_RET]]
-; CHECK:       bb2:
-; CHECK-NEXT:    store i32 1, ptr [[Q]], align 4
-; CHECK-NEXT:    [[C:%.*]] = load i32, ptr [[Q]], align 4
-; CHECK-NEXT:    call void @bar(i32 [[C]])
-; CHECK-NEXT:    br label [[COMMON_RET]]
+; CHECK-NEXT:    ret void
 ;
   switch i64 %i, label %bb0 [
   i64 1, label %bb1
   i64 2, label %bb2
   ]
 bb0:              ; preds = %0
   store i32 1, ptr %Q
   %A = load i32, ptr %Q               ; <i32> [#uses=1]
   call void @bar( i32 %A )
   ret void
 bb1:              ; preds = %0
   store i32 1, ptr %Q
   %B = load i32, ptr %Q               ; <i32> [#uses=1]
   call void @bar( i32 %B )
   ret void
 bb2:              ; preds = %0
   store i32 1, ptr %Q
   %C = load i32, ptr %Q               ; <i32> [#uses=1]
   call void @bar( i32 %C )
   ret void
 }
 
-define i1 @common_instr_on_switch(i64 %a, i64 %b, i64 %c) unnamed_addr {
-; CHECK-LABEL: @common_instr_on_switch(
-; CHECK-NEXT:  start:
-; CHECK-NEXT:    switch i64 [[A:%.*]], label [[BB0:%.*]] [
+; We ensure that we examine all instructions during each iteration to confirm the presence of a terminating one.
+define void @test_switch_reach_terminator(i64 %i, ptr %p) {
+; CHECK-LABEL: @test_switch_reach_terminator(
+; CHECK-NEXT:    switch i64 [[I:%.*]], label [[BB0:%.*]] [
 ; CHECK-NEXT:    i64 1, label [[BB1:%.*]]
-; CHECK-NEXT:    i64 2, label [[BB2:%.*]]
+; CHECK-NEXT:    i64 2, label [[COMMON_RET:%.*]]
 ; CHECK-NEXT:    ]
+; CHECK:       common.ret:
+; CHECK-NEXT:    ret void
 ; CHECK:       bb0:
-; CHECK-NEXT:    [[TMP0:%.*]] = icmp eq i64 [[B:%.*]], [[C:%.*]]
-; CHECK-NEXT:    br label [[EXIT:%.*]]
+; CHECK-NEXT:    store i32 1, ptr [[P:%.*]], align 4
+; CHECK-NEXT:    br label [[COMMON_RET]]
 ; CHECK:       bb1:
-; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i64 [[B]], [[C]]
-; CHECK-NEXT:    br label [[EXIT]]
-; CHECK:       bb2:
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i64 [[B]], [[C]]
-; CHECK-NEXT:    br label [[EXIT]]
-; CHECK:       exit:
-; CHECK-NEXT:    [[RESULT:%.*]] = phi i1 [ [[TMP0]], [[BB0]] ], [ [[TMP1]], [[BB1]] ], [ [[TMP2]], [[BB2]] ]
-; CHECK-NEXT:    ret i1 [[RESULT]]
+; CHECK-NEXT:    store i32 2, ptr [[P]], align 4
+; CHECK-NEXT:    br label [[COMMON_RET]]
+;
+  switch i64 %i, label %bb0 [
+  i64 1, label %bb1
+  i64 2, label %bb2
+  ]
+bb0:              ; preds = %0
+  store i32 1, ptr %p
+  ret void
+bb1:              ; preds = %0
+  store i32 2, ptr %p
+  ret void
+bb2:              ; preds = %0
+  ret void
+}
+
+define i1 @common_instr_on_switch(i64 %a, i64 %b, i64 %c) unnamed_addr {
+; CHECK-LABEL: @common_instr_on_switch(
+; CHECK-NEXT:  start:
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp eq i64 [[B:%.*]], [[C:%.*]]
+; CHECK-NEXT:    ret i1 [[TMP0]]
 ;
 start:
   switch i64 %a, label %bb0 [
   i64 1, label %bb1
   i64 2, label %bb2
   ]
 
 bb0:                                              ; preds = %start
   %0 = icmp eq i64 %b, %c
   br label %exit
 
 bb1:                                              ; preds = %start
   %1 = icmp eq i64 %b, %c
   br label %exit
 

llvm/test/Transforms/SimplifyCFG/hoist-with-metadata.ll

else:
   %e = load i8, ptr %p, !range !1
   br label %out
 out:
   ret void
 }
 
 define void @hoist_range_switch(i64 %i, ptr %p) {
 ; CHECK-LABEL: @hoist_range_switch(
-; CHECK-NEXT:    switch i64 [[I:%.*]], label [[BB0:%.*]] [
-; CHECK-NEXT:    i64 1, label [[BB1:%.*]]
-; CHECK-NEXT:    i64 2, label [[BB2:%.*]]
-; CHECK-NEXT:    ]
-; CHECK:       bb0:
+; CHECK-NEXT:  out:
 ; CHECK-NEXT:    [[T:%.*]] = load i8, ptr [[P:%.*]], align 1, !range [[RNG1:![0-9]+]]
-; CHECK-NEXT:    br label [[OUT:%.*]]
-; CHECK:       bb1:
-; CHECK-NEXT:    [[E:%.*]] = load i8, ptr [[P]], align 1, !range [[RNG2:![0-9]+]]
-; CHECK-NEXT:    br label [[OUT]]
-; CHECK:       bb2:
-; CHECK-NEXT:    [[F:%.*]] = load i8, ptr [[P]], align 1, !range [[RNG3:![0-9]+]]
-; CHECK-NEXT:    br label [[OUT]]
-; CHECK:       out:
 ; CHECK-NEXT:    ret void
 ;
   switch i64 %i, label %bb0 [
   i64 1, label %bb1
   i64 2, label %bb2
   ]
 bb0:
   %t = load i8, ptr %p, !range !0
   br label %out
 bb1:
   %e = load i8, ptr %p, !range !1
   br label %out
 bb2:
   %f = load i8, ptr %p, !range !3
   br label %out
 out:
   ret void
 }
 
 define void @hoist_both_noundef(i1 %c, ptr %p) {
 ; CHECK-LABEL: @hoist_both_noundef(
 ; CHECK-NEXT:  if:
-; CHECK-NEXT:    [[T:%.*]] = load i8, ptr [[P:%.*]], align 1, !noundef !4
+; CHECK-NEXT:    [[T:%.*]] = load i8, ptr [[P:%.*]], align 1, !noundef !2
 ; CHECK-NEXT:    ret void
 ;
 if:
   br i1 %c, label %then, label %else
 
 then:
   %t = load i8, ptr %p, !noundef !2
   br label %out
 
 else:
   %e = load i8, ptr %p, !noundef !2
   br label %out
 
 out:
   ret void
 }
 
 
 define void @hoist_both_noundef_switch(i64 %i, ptr %p) {
 ; CHECK-LABEL: @hoist_both_noundef_switch(
-; CHECK-NEXT:    switch i64 [[I:%.*]], label [[BB0:%.*]] [
-; CHECK-NEXT:    i64 1, label [[BB1:%.*]]
-; CHECK-NEXT:    i64 2, label [[BB2:%.*]]
-; CHECK-NEXT:    ]
-; CHECK:       bb0:
-; CHECK-NEXT:    [[T:%.*]] = load i8, ptr [[P:%.*]], align 1, !noundef !4
-; CHECK-NEXT:    br label [[OUT:%.*]]
-; CHECK:       bb1:
-; CHECK-NEXT:    [[E:%.*]] = load i8, ptr [[P]], align 1, !noundef !4
-; CHECK-NEXT:    br label [[OUT]]
-; CHECK:       bb2:
-; CHECK-NEXT:    [[F:%.*]] = load i8, ptr [[P]], align 1, !noundef !4
-; CHECK-NEXT:    br label [[OUT]]
-; CHECK:       out:
+; CHECK-NEXT:  out:
+; CHECK-NEXT:    [[T:%.*]] = load i8, ptr [[P:%.*]], align 1, !noundef !2
 ; CHECK-NEXT:    ret void
 ;
   switch i64 %i, label %bb0 [
   i64 1, label %bb1
   i64 2, label %bb2
   ]
 bb0:
   %t = load i8, ptr %p, !noundef !2
else:
   br label %out
 
 out:
   ret void
 }
 
 define void @hoist_one_noundef_switch(i64 %i, ptr %p) {
 ; CHECK-LABEL: @hoist_one_noundef_switch(
-; CHECK-NEXT:    switch i64 [[I:%.*]], label [[BB0:%.*]] [
-; CHECK-NEXT:    i64 1, label [[BB1:%.*]]
-; CHECK-NEXT:    i64 2, label [[BB2:%.*]]
-; CHECK-NEXT:    ]
-; CHECK:       bb0:
-; CHECK-NEXT:    [[T:%.*]] = load i8, ptr [[P:%.*]], align 1, !noundef !4
-; CHECK-NEXT:    br label [[OUT:%.*]]
-; CHECK:       bb1:
-; CHECK-NEXT:    [[E:%.*]] = load i8, ptr [[P]], align 1
-; CHECK-NEXT:    br label [[OUT]]
-; CHECK:       bb2:
-; CHECK-NEXT:    [[F:%.*]] = load i8, ptr [[P]], align 1, !noundef !4
-; CHECK-NEXT:    br label [[OUT]]
-; CHECK:       out:
+; CHECK-NEXT:  out:
+; CHECK-NEXT:    [[T:%.*]] = load i8, ptr [[P:%.*]], align 1
 ; CHECK-NEXT:    ret void
 ;
   switch i64 %i, label %bb0 [
   i64 1, label %bb1
   i64 2, label %bb2
   ]
 bb0:
   %t = load i8, ptr %p, !noundef !2
   br label %out
 bb1:
   %e = load i8, ptr %p
   br label %out
 bb2:
   %f = load i8, ptr %p, !noundef !2
   br label %out
 out:
   ret void
 }
 
 define void @hoist_dereferenceable(i1 %c, ptr %p) {
 ; CHECK-LABEL: @hoist_dereferenceable(
 ; CHECK-NEXT:  if:
-; CHECK-NEXT:    [[T:%.*]] = load ptr, ptr [[P:%.*]], align 8, !dereferenceable !5
+; CHECK-NEXT:    [[T:%.*]] = load ptr, ptr [[P:%.*]], align 8, !dereferenceable !3
 ; CHECK-NEXT:    ret void
 ;
 if:
   br i1 %c, label %then, label %else
 then:
   %t = load ptr, ptr %p, !dereferenceable !{i64 10}
   br label %out
 else:
   %e = load ptr, ptr %p, !dereferenceable !{i64 20}
   br label %out
 out:
   ret void
 }
 
 define void @hoist_dereferenceable_switch(i64 %i, ptr %p) {
 ; CHECK-LABEL: @hoist_dereferenceable_switch(
-; CHECK-NEXT:    switch i64 [[I:%.*]], label [[BB0:%.*]] [
-; CHECK-NEXT:    i64 1, label [[BB1:%.*]]
-; CHECK-NEXT:    i64 2, label [[BB2:%.*]]
-; CHECK-NEXT:    ]
-; CHECK:       bb0:
-; CHECK-NEXT:    [[T:%.*]] = load ptr, ptr [[P:%.*]], align 8, !dereferenceable !5
-; CHECK-NEXT:    br label [[OUT:%.*]]
-; CHECK:       bb1:
-; CHECK-NEXT:    [[E:%.*]] = load ptr, ptr [[P]], align 8, !dereferenceable !6
-; CHECK-NEXT:    br label [[OUT]]
-; CHECK:       bb2:
-; CHECK-NEXT:    [[F:%.*]] = load ptr, ptr [[P]], align 8, !dereferenceable !7
-; CHECK-NEXT:    br label [[OUT]]
-; CHECK:       out:
+; CHECK-NEXT:  out:
+; CHECK-NEXT:    [[T:%.*]] = load ptr, ptr [[P:%.*]], align 8, !dereferenceable !3
 ; CHECK-NEXT:    ret void
 ;
   switch i64 %i, label %bb0 [
   i64 1, label %bb1
   i64 2, label %bb2
   ]
 bb0:
   %t = load ptr, ptr %p, !dereferenceable !{i64 10}
   br label %out
 bb1:
   %e = load ptr, ptr %p, !dereferenceable !{i64 20}
   br label %out
 bb2:
   %f = load ptr, ptr %p, !dereferenceable !{i64 30}
   br label %out
 out:
   ret void
 }
 
 define void @hoist_dereferenceable_or_null(i1 %c, ptr %p) {
 ; CHECK-LABEL: @hoist_dereferenceable_or_null(
 ; CHECK-NEXT:  if:
-; CHECK-NEXT:    [[T:%.*]] = load ptr, ptr [[P:%.*]], align 8, !dereferenceable_or_null !5
+; CHECK-NEXT:    [[T:%.*]] = load ptr, ptr [[P:%.*]], align 8, !dereferenceable_or_null !3
 ; CHECK-NEXT:    ret void
 ;
 if:
   br i1 %c, label %then, label %else
 then:
   %t = load ptr, ptr %p, !dereferenceable_or_null !{i64 20}
   br label %out
 else:
   %e = load ptr, ptr %p, !dereferenceable_or_null !{i64 10}
   br label %out
 out:
   ret void
 }
 
 define void @hoist_dereferenceable_or_null_switch(i64 %i, ptr %p) {
 ; CHECK-LABEL: @hoist_dereferenceable_or_null_switch(
-; CHECK-NEXT:    switch i64 [[I:%.*]], label [[BB0:%.*]] [
-; CHECK-NEXT:    i64 1, label [[BB1:%.*]]
-; CHECK-NEXT:    i64 2, label [[BB2:%.*]]
-; CHECK-NEXT:    ]
-; CHECK:       bb0:
-; CHECK-NEXT:    [[T:%.*]] = load ptr, ptr [[P:%.*]], align 8, !dereferenceable_or_null !6
-; CHECK-NEXT:    br label [[OUT:%.*]]
-; CHECK:       bb1:
-; CHECK-NEXT:    [[E:%.*]] = load ptr, ptr [[P]], align 8, !dereferenceable_or_null !5
-; CHECK-NEXT:    br label [[OUT]]
-; CHECK:       bb2:
-; CHECK-NEXT:    [[F:%.*]] = load ptr, ptr [[P]], align 8, !dereferenceable_or_null !7
-; CHECK-NEXT:    br label [[OUT]]
-; CHECK:       out:
+; CHECK-NEXT:  out:
+; CHECK-NEXT:    [[T:%.*]] = load ptr, ptr [[P:%.*]], align 8, !dereferenceable_or_null !3
 ; CHECK-NEXT:    ret void
 ;
   switch i64 %i, label %bb0 [
   i64 1, label %bb1
   i64 2, label %bb2
   ]
 bb0:
   %t = load ptr, ptr %p, !dereferenceable_or_null !{i64 20}
   br label %out
 bb1:
   %e = load ptr, ptr %p, !dereferenceable_or_null !{i64 10}
   br label %out
 bb2:
   %f = load ptr, ptr %p, !dereferenceable_or_null !{i64 30}
   br label %out
 out:
   ret void
 }
 
 ; !range violation only returns poison, and is thus safe to speculate.
 define i32 @speculate_range(i1 %c, ptr dereferenceable(8) align 8 %p) {
 ; CHECK-LABEL: @speculate_range(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[V:%.*]] = load i32, ptr [[P:%.*]], align 4, !range [[RNG8:![0-9]+]]
+; CHECK-NEXT:    [[V:%.*]] = load i32, ptr [[P:%.*]], align 4, !range [[RNG4:![0-9]+]]
 ; CHECK-NEXT:    [[SPEC_SELECT:%.*]] = select i1 [[C:%.*]], i32 [[V]], i32 0
 ; CHECK-NEXT:    ret i32 [[SPEC_SELECT]]
 ;
 entry:
   br i1 %c, label %if, label %join
 
 if:
   %v = load i32, ptr %p, !range !{i32 0, i32 10}
   br label %join
 
 join:
   %phi = phi i32 [ %v, %if ], [ 0, %entry ]
   ret i32 %phi
 }
 
 ; !nonnull is safe to speculate, but !noundef is not, as the latter causes
 ; immediate undefined behavior.
 define ptr @speculate_nonnull(i1 %c, ptr dereferenceable(8) align 8 %p) {
 ; CHECK-LABEL: @speculate_nonnull(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[V:%.*]] = load ptr, ptr [[P:%.*]], align 8, !nonnull !4
+; CHECK-NEXT:    [[V:%.*]] = load ptr, ptr [[P:%.*]], align 8, !nonnull !2
 ; CHECK-NEXT:    [[SPEC_SELECT:%.*]] = select i1 [[C:%.*]], ptr [[V]], ptr null
 ; CHECK-NEXT:    ret ptr [[SPEC_SELECT]]
 ;
 entry:
   br i1 %c, label %if, label %join
 
 if:
   %v = load ptr, ptr %p, !nonnull !{}, !noundef !{}
   br label %join
 
 join:
   %phi = phi ptr [ %v, %if ], [ null, %entry ]
   ret ptr %phi
 }
 
 ; !align is safe to speculate, but !dereferenceable is not, as the latter causes
 ; immediate undefined behavior.
 define ptr @speculate_align(i1 %c, ptr dereferenceable(8) align 8 %p) {
 ; CHECK-LABEL: @speculate_align(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[V:%.*]] = load ptr, ptr [[P:%.*]], align 8, !align !9
+; CHECK-NEXT:    [[V:%.*]] = load ptr, ptr [[P:%.*]], align 8, !align !5
 ; CHECK-NEXT:    [[SPEC_SELECT:%.*]] = select i1 [[C:%.*]], ptr [[V]], ptr null
 ; CHECK-NEXT:    ret ptr [[SPEC_SELECT]]
 ;
 entry:
   br i1 %c, label %if, label %join
 
 if:
   %v = load ptr, ptr %p, !align !{i64 4}, !dereferenceable !{i64 4}
   br label %join
 
 join:
   %phi = phi ptr [ %v, %if ], [ null, %entry ]
   ret ptr %phi
 }
 
 define void @hoist_fpmath(i1 %c, double %x) {
 ; CHECK-LABEL: @hoist_fpmath(
 ; CHECK-NEXT:  if:
-; CHECK-NEXT:    [[T:%.*]] = fadd double [[X:%.*]], 1.000000e+00, !fpmath !10
+; CHECK-NEXT:    [[T:%.*]] = fadd double [[X:%.*]], 1.000000e+00, !fpmath !6
 ; CHECK-NEXT:    ret void
 ;
 if:
   br i1 %c, label %then, label %else
 then:
   %t = fadd double %x, 1.0, !fpmath !{ float 2.5 }
   br label %out
 else:
   %e = fadd double %x, 1.0, !fpmath !{ float 5.0 }
   br label %out
 out:
   ret void
 }
 
 define void @hoist_fpmath_switch(i64 %i, double %x) {
 ; CHECK-LABEL: @hoist_fpmath_switch(
-; CHECK-NEXT:    switch i64 [[I:%.*]], label [[BB0:%.*]] [
-; CHECK-NEXT:    i64 1, label [[BB1:%.*]]
-; CHECK-NEXT:    i64 2, label [[BB2:%.*]]
-; CHECK-NEXT:    ]
-; CHECK:       bb0:
-; CHECK-NEXT:    [[T:%.*]] = fadd double [[X:%.*]], 1.000000e+00, !fpmath !10
-; CHECK-NEXT:    br label [[OUT:%.*]]
-; CHECK:       bb1:
-; CHECK-NEXT:    [[E:%.*]] = fadd double [[X]], 1.000000e+00, !fpmath !11
-; CHECK-NEXT:    br label [[OUT]]
-; CHECK:       bb2:
-; CHECK-NEXT:    [[F:%.*]] = fadd double [[X]], 1.000000e+00, !fpmath !12
-; CHECK-NEXT:    br label [[OUT]]
-; CHECK:       out:
+; CHECK-NEXT:  out:
+; CHECK-NEXT:    [[T:%.*]] = fadd double [[X:%.*]], 1.000000e+00, !fpmath !6
 ; CHECK-NEXT:    ret void
 ;
   switch i64 %i, label %bb0 [
   i64 1, label %bb1
   i64 2, label %bb2
   ]
 bb0:
   %t = fadd double %x, 1.0, !fpmath !{ float 2.5 }

 }
 
 !0 = !{ i8 0, i8 1 }
 !1 = !{ i8 3, i8 5 }
 !2 = !{}
 !3 = !{ i8 7, i8 9 }
 ;.
 ; CHECK: [[RNG0]] = !{i8 0, i8 1, i8 3, i8 5}
-; CHECK: [[RNG1]] = !{i8 0, i8 1}
-; CHECK: [[RNG2]] = !{i8 3, i8 5}
-; CHECK: [[RNG3]] = !{i8 7, i8 9}
-; CHECK: [[META4:![0-9]+]] = !{}
-; CHECK: [[META5:![0-9]+]] = !{i64 10}
-; CHECK: [[META6:![0-9]+]] = !{i64 20}
-; CHECK: [[META7:![0-9]+]] = !{i64 30}
-; CHECK: [[RNG8]] = !{i32 0, i32 10}
-; CHECK: [[META9:![0-9]+]] = !{i64 4}
-; CHECK: [[META10:![0-9]+]] = !{float 2.500000e+00}
-; CHECK: [[META11:![0-9]+]] = !{float 5.000000e+00}
-; CHECK: [[META12:![0-9]+]] = !{float 7.500000e+00}
+; CHECK: [[RNG1]] = !{i8 0, i8 1, i8 3, i8 5, i8 7, i8 9}
+; CHECK: [[META2:![0-9]+]] = !{}
+; CHECK: [[META3:![0-9]+]] = !{i64 10}
+; CHECK: [[RNG4]] = !{i32 0, i32 10}
+; CHECK: [[META5:![0-9]+]] = !{i64 4}
+; CHECK: [[META6:![0-9]+]] = !{float 2.500000e+00}
 ;.