[SimplifyCFG] Allow SimplifyCFG hoisting to skip over non-matching instructions

[chill]

Summary

SimplifyCFG does some common code hoisting, which is limited to hoisting a
sequence of identical instruction in identical order and stops at the first
non-identical instruction.

This patch allows hoisting instruction pairs over same-length sequences of
non-matching instructions. The linear asymptotic complexity of the algorithm
stays the same, there's an extra parameter simplifycfg-hoist-common-skip-limit
serving to limit compilation time and/or the size of the hoisted live ranges.

The patch improves SPECv6/525.x264_r by about 10%.

[nikic]

I think you need to be more careful about the side effects here. You generally need to distinguish control flow effects from memory effects. For example, if you skip over an instruction that is not must-exec (i.e. not nothrow or not willreturn), and then want to hoist a udiv (which is side-effect free, but not generally speculatable), then that is illegal and I don't think you currently handle this correctly.

On a more general note, this skipping of non-identical instructions in lock-step seems kind of ... random? It isn't obvious to me why we would typically expect there to be sequences of different instructions that just happen to have the same length.

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

1439

Why can Instruction::mayHaveSideEffects() not be used?

1449

Wrong comment indentation here and below.

1456

What does this have to do with the single predecessor? Doesn't this generally hold?

[chill]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

1456

Indeed.

[chill]

In D129370#3638912, @nikic wrote:

I think you need to be more careful about the side effects here. You generally need to distinguish control flow effects from memory effects. For example, if you skip over an instruction that is not must-exec (i.e. not nothrow or not willreturn), and then want to hoist a udiv (which is side-effect free, but not generally speculatable), then that is illegal and I don't think you currently handle this correctly.

Thanks for the review, I think I have fixed those issues.

On a more general note, this skipping of non-identical instructions in lock-step seems kind of ... random? It isn't obvious to me why we would typically expect there to be sequences of different instructions that just happen to have the same length.

Indeed, it relies on ... luck, but that applies to the original function as well, isn't it ?

And it turns out, it happens: when compiling llvm-test-suite, the HoistThenElseCodeToIf triggers 3206 times, of these
722 times at least one instruction pair was hoisted over at least one non-matching pair (stats collected as in https://reviews.llvm.org/D129551)

[chill]

In D129370#3644789, @chill wrote:

And it turns out, it happens: when compiling llvm-test-suite, the HoistThenElseCodeToIf triggers 3206 times, of these
722 times at least one instruction pair was hoisted over at least one non-matching pair (stats collected as in https://reviews.llvm.org/D129551)

TBH, some of those might be identical pairs of debug intrinsics, which aren't very interesting.

[chill]

Ping?

[fhahn]

In D129370#3644789, @chill wrote:

In D129370#3638912, @nikic wrote:

I think you need to be more careful about the side effects here. You generally need to distinguish control flow effects from memory effects. For example, if you skip over an instruction that is not must-exec (i.e. not nothrow or not willreturn), and then want to hoist a udiv (which is side-effect free, but not generally speculatable), then that is illegal and I don't think you currently handle this correctly.

Thanks for the review, I think I have fixed those issues.

It looks like we are missing test-coverage for at least some of those case. Could you add extra tests to cover the checks you added?

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

76

the test case can be further simplified, e.g. there's no need to load & compare here. instead the condition can simplify be passed as argument.

Similarly, there's no need to return an i32 from the function or have multiple diverging instructions in the blocks.

[chill]

Ping?

[dmgreen]

I would probably have just bailed out if it reached an instruction with side-effects, but as far as I can see this seems like it should be OK.

LGMT

[nikic]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

1572

This check should not be present (likely rebase mistake).

1645

This check is still incorrect. Consider this example:

define i16 @f7(i1 %c, ptr %a, ptr %b) {
; CHECK-LABEL: @f7(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    store i16 0, ptr [[B:%.*]], align 2
; CHECK-NEXT:    br i1 [[C:%.*]], label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]]
; CHECK:       if.then:
; CHECK-NEXT:    [[VA:%.*]] = load i16, ptr [[A:%.*]], align 2
; CHECK-NEXT:    br label [[IF_END:%.*]]
; CHECK:       if.else:
; CHECK-NEXT:    [[VB:%.*]] = load i16, ptr [[B]], align 2
; CHECK-NEXT:    br label [[IF_END]]
; CHECK:       if.end:
; CHECK-NEXT:    [[V:%.*]] = phi i16 [ [[VA]], [[IF_THEN]] ], [ [[VB]], [[IF_ELSE]] ]
; CHECK-NEXT:    ret i16 [[V]]
;
entry:
  br i1 %c, label %if.then, label %if.else

if.then:
  %va = load i16, ptr %a, align 2
  store i16 0, ptr %b, align 2
  br label %if.end

if.else:
  %vb = load i16, ptr %b, align 2
  store i16 0, ptr %b, align 2
  br label %if.end

if.end:
  %v = phi i16 [ %va, %if.then ], [ %vb, %if.else ]
  ret i16 %v
}

You are currently hoisting the store above the loads.

What you want to check here is mayReadOrWriteMemory, not mayHaveSideEffects. (The non-memory effects are modeled by the other check now).

[chill]

Thanks, I'll have look.

[nikic]

LGTM

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

1433

instructins -> instructions

[chill]

Thanks!

[hans]

Heads up that we're seeing test failures in Chromium that bisect to this: https://bugs.chromium.org/p/chromium/issues/detail?id=1361629

We're still investigating, just adding an early note in case others have also hit problems.

[aeubanks]

this looks to be hoisting llvm.stacksave past a previous alloca inalloca which breaks win32 (inalloca docs). trying to come up with a reduced repro

[aeubanks]

In D129370#3784781, @aeubanks wrote:

this looks to be hoisting llvm.stacksave past a previous alloca inalloca which breaks win32 (inalloca docs). trying to come up with a reduced repro

https://reviews.llvm.org/D133730

[foad]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

1584

Leaving these return instructions in the isIdenticalToWhenDefined case seems wrong, since it means that instructions that are identical but fail this check are treated more pessimistically than instructions that are not identical.

[chill]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

1584

You mean ,in that case we should enter that part where we skip over those calls, increment
NumSkipped and continue (i.e. the part that starts at line 1638 below)?

Yeah, makes sense.

[chill]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

1584

OTOH, a musttail call can only be followed by a ret or a bitcast.

I guess I don't understand what we are missing here ...

[foad]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

1584

I didn't really mean this specific return, I meant all of the returns from here down to line 1595. D149365 fixes them all and shows a case where it improves handling of convergent calls.

[chill]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

1584

Yeah, I saw the other patch. Thanks!

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

static cl::opt<unsigned> TwoEntryPHINodeFoldingThreshold(
     cl::desc("Control the maximal total instruction cost that we are willing "
              "to speculatively execute to fold a 2-entry PHI node into a "
              "select (default = 4)"));
 
 static cl::opt<bool>
     HoistCommon("simplifycfg-hoist-common", cl::Hidden, cl::init(true),
                 cl::desc("Hoist common instructions up to the parent block"));
 
+static cl::opt<unsigned>
+    HoistCommonSkipLimit("simplifycfg-hoist-common-skip-limit", cl::Hidden,
+                         cl::init(20),
+                         cl::desc("Allow reordering across at most this many "
+                                  "instructions when hoisting"));
+
 static cl::opt<bool>
     SinkCommon("simplifycfg-sink-common", cl::Hidden, cl::init(true),
                cl::desc("Sink common instructions down to the end block"));
 
 static cl::opt<bool> HoistCondStores(
     "simplifycfg-hoist-cond-stores", cl::Hidden, cl::init(true),
     cl::desc("Hoist conditional stores if an unconditional store precedes"));
 
for (const PHINode &PN : Succ->phis()) {
       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.
+enum SkipFlags {
+  SkipReadMem = 1,
+  SkipSideEffect = 2,
+  SkipImplicitControlFlow = 4
+};
+
+static unsigned skippedInstrFlags(Instruction *I) {
+  unsigned Flags = 0;
+  if (I->mayReadFromMemory())
+    Flags |= SkipReadMem;
+  if (I->mayHaveSideEffects())
+    Flags |= SkipSideEffect;
+  if (!isGuaranteedToTransferExecutionToSuccessor(I))
+    Flags |= SkipImplicitControlFlow;
+  return Flags;
+}
+
+// Returns true if it is safe to reorder an instruction across preceding
+// instructions in a basic block.
+static bool isSafeToHoistInstr(Instruction *I, unsigned Flags) {
+  // Don't reorder a store over a load.
+  if ((Flags & SkipReadMem) && I->mayWriteToMemory())
+    return false;
+
+  // If we have seen an instruction with side effects, it's unsafe to reorder an
+  // instruction which reads memory or itself has side effects.
+  if ((Flags & SkipSideEffect) &&
+      (I->mayReadFromMemory() || I->mayHaveSideEffects()))
+    return false;
+
+  // Reordering across an instruction which does not necessarily transfer
+  // control to the next instruction is speculation.
+  if ((Flags & SkipImplicitControlFlow) && !isSafeToSpeculativelyExecute(I))
+    return false;
+
+  // It's also unsafe/illegal to hoist an instruction above its instruction
+  // operands
+  BasicBlock *BB = I->getParent();
+  for (Value *Op : I->operands()) {
+    if (auto *J = dyn_cast<Instruction>(Op))
+      if (J->getParent() == BB)
+        return false;
+  }
+
+  return true;
+}
+
 static bool passingValueIsAlwaysUndefined(Value *V, Instruction *I, bool PtrValueMayBeModified = false);
 
 /// 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,
                                            const TargetTransformInfo &TTI,
                                            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
   // such, we currently just scan for obviously identical instructions in an
-  // identical order.
+  // 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
 
   // 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())
     return false;
 
   BasicBlock::iterator BB1_Itr = BB1->begin();
   BasicBlock::iterator BB2_Itr = BB2->begin();
 
   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) || !I1->isIdenticalToWhenDefined(I2))
+  if (isa<PHINode>(I1))
     return false;
 
   BasicBlock *BIParent = BI->getParent();
 
   bool Changed = false;
 
   auto _ = make_scope_exit([&]() {
     if (Changed)
if (EqTermsOnly) {
     if (!I1NonDbg->isIdenticalToWhenDefined(I2NonDbg))
       return false;
     if (!I1NonDbg->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.
   }
 
-  do {
+  // 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;
+
+  for (;;) {
     // If we are hoisting the terminator instruction, don't move one (making a
     // broken BB), instead clone it, and remove BI.
-    if (I1->isTerminator())
+    if (I1->isTerminator() || I2->isTerminator()) {
+      // If any instructions remain in the block, we cannot hoist terminators.
+      if (NumSkipped || !I1->isIdenticalToWhenDefined(I2))
+        return Changed;
       goto HoistTerminator;
+    }
+
+    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 (!isSafeToHoistInstr(I1, SkipFlagsBB1) ||
+          !isSafeToHoistInstr(I2, SkipFlagsBB2))
+        return Changed;
 
-    // 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 a return.
+      // 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
+      // a return.
       auto *C1 = dyn_cast<CallInst>(I1);
       auto *C2 = dyn_cast<CallInst>(I2);
       if (C1 && C2)
         if (C1->isMustTailCall() != C2->isMustTailCall())
           return Changed;
 
       if (!TTI.isProfitableToHoist(I1) || !TTI.isProfitableToHoist(I2))
         return Changed;
 
       // If any of the two call sites has nomerge attribute, stop hoisting.
       if (const auto *CB1 = dyn_cast<CallBase>(I1))
         if (CB1->cannotMerge())
           return Changed;
       if (const auto *CB2 = dyn_cast<CallBase>(I2))
         if (CB2->cannotMerge())
           return Changed;
 
       if (isa<DbgInfoIntrinsic>(I1) || isa<DbgInfoIntrinsic>(I2)) {
-      assert (isa<DbgInfoIntrinsic>(I1) && isa<DbgInfoIntrinsic>(I2));
+        assert(isa<DbgInfoIntrinsic>(I1) && isa<DbgInfoIntrinsic>(I2));
         // 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->getInstList().splice(BI->getIterator(),
-                                     BB1->getInstList(), I1);
-      BIParent->getInstList().splice(BI->getIterator(),
-                                     BB2->getInstList(), I2);
-      Changed = true;
+        BIParent->getInstList().splice(BI->getIterator(), BB1->getInstList(),
+                                       I1);
+        BIParent->getInstList().splice(BI->getIterator(), BB2->getInstList(),
+                                       I2);
       } 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->getInstList().splice(BI->getIterator(),
-                                     BB1->getInstList(), I1);
+        // 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->getInstList().splice(BI->getIterator(), BB1->getInstList(),
+                                       I1);
         if (!I2->use_empty())
           I2->replaceAllUsesWith(I1);
         I1->andIRFlags(I2);
         unsigned KnownIDs[] = {LLVMContext::MD_tbaa,
                                LLVMContext::MD_range,
                                LLVMContext::MD_fpmath,
                                LLVMContext::MD_invariant_load,
                                LLVMContext::MD_nonnull,
                                LLVMContext::MD_invariant_group,
                                LLVMContext::MD_align,
                                LLVMContext::MD_dereferenceable,
                                LLVMContext::MD_dereferenceable_or_null,
                                LLVMContext::MD_mem_parallel_loop_access,
                                LLVMContext::MD_access_group,
                                LLVMContext::MD_preserve_access_index};
         combineMetadata(I1, I2, KnownIDs, 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();
-      Changed = true;
       }
+      Changed = true;
       ++NumHoistCommonInstrs;
+    } 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);
+      ++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++;
     }
-  } while (I1->isIdenticalToWhenDefined(I2));
+  }
 
-  return true;
+  return Changed;
 
 HoistTerminator:
   // It may not be possible to hoist an invoke.
   // FIXME: Can we define a safety predicate for CallBr?
   if (isa<InvokeInst>(I1) && !isSafeToHoistInvoke(BB1, BB2, I1, I2))
     return Changed;
 
   // TODO: callbr hoisting currently disabled pending further study.

llvm/test/Transforms/SimplifyCFG/hoist-common-skip-limit.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -S --passes='simplifycfg<hoist-common-insts>' -simplifycfg-hoist-common-skip-limit=0 %s | FileCheck %s --check-prefix=LIMIT0
+; RUN: opt -S --passes='simplifycfg<hoist-common-insts>' -simplifycfg-hoist-common-skip-limit=1 %s | FileCheck %s --check-prefix=LIMIT1
+; RUN: opt -S --passes='simplifycfg<hoist-common-insts>' -simplifycfg-hoist-common-skip-limit=2 %s | FileCheck %s --check-prefix=LIMIT2
+
+define void @f(i1 %c, ptr nocapture noundef %d, ptr nocapture noundef readonly %m, ptr nocapture noundef readonly %b) {
+; LIMIT0-LABEL: @f(
+; LIMIT0-NEXT:  entry:
+; LIMIT0-NEXT:    [[TMP0:%.*]] = load i16, ptr [[B:%.*]], align 2
+; LIMIT0-NEXT:    br i1 [[C:%.*]], label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]]
+; LIMIT0:       if.then:
+; LIMIT0-NEXT:    call void @no_side_effects0()
+; LIMIT0-NEXT:    [[ADD:%.*]] = add nsw i16 [[TMP0]], 1
+; LIMIT0-NEXT:    [[TMP1:%.*]] = load i16, ptr [[M:%.*]], align 2
+; LIMIT0-NEXT:    [[U:%.*]] = add i16 [[ADD]], [[TMP1]]
+; LIMIT0-NEXT:    br label [[IF_END:%.*]]
+; LIMIT0:       if.else:
+; LIMIT0-NEXT:    call void @no_side_effects1()
+; LIMIT0-NEXT:    [[SUB:%.*]] = sub nsw i16 [[TMP0]], 1
+; LIMIT0-NEXT:    [[TMP2:%.*]] = load i16, ptr [[M]], align 2
+; LIMIT0-NEXT:    [[V:%.*]] = add i16 [[SUB]], [[TMP2]]
+; LIMIT0-NEXT:    br label [[IF_END]]
+; LIMIT0:       if.end:
+; LIMIT0-NEXT:    [[UV:%.*]] = phi i16 [ [[V]], [[IF_ELSE]] ], [ [[U]], [[IF_THEN]] ]
+; LIMIT0-NEXT:    store i16 [[UV]], ptr [[D:%.*]], align 2
+; LIMIT0-NEXT:    ret void
+;
+; LIMIT1-LABEL: @f(
+; LIMIT1-NEXT:  entry:
+; LIMIT1-NEXT:    [[TMP0:%.*]] = load i16, ptr [[B:%.*]], align 2
+; LIMIT1-NEXT:    br i1 [[C:%.*]], label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]]
+; LIMIT1:       if.then:
+; LIMIT1-NEXT:    call void @no_side_effects0()
+; LIMIT1-NEXT:    [[ADD:%.*]] = add nsw i16 [[TMP0]], 1
+; LIMIT1-NEXT:    [[TMP1:%.*]] = load i16, ptr [[M:%.*]], align 2
+; LIMIT1-NEXT:    [[U:%.*]] = add i16 [[ADD]], [[TMP1]]
+; LIMIT1-NEXT:    br label [[IF_END:%.*]]
+; LIMIT1:       if.else:
+; LIMIT1-NEXT:    call void @no_side_effects1()
+; LIMIT1-NEXT:    [[SUB:%.*]] = sub nsw i16 [[TMP0]], 1
+; LIMIT1-NEXT:    [[TMP2:%.*]] = load i16, ptr [[M]], align 2
+; LIMIT1-NEXT:    [[V:%.*]] = add i16 [[SUB]], [[TMP2]]
+; LIMIT1-NEXT:    br label [[IF_END]]
+; LIMIT1:       if.end:
+; LIMIT1-NEXT:    [[UV:%.*]] = phi i16 [ [[V]], [[IF_ELSE]] ], [ [[U]], [[IF_THEN]] ]
+; LIMIT1-NEXT:    store i16 [[UV]], ptr [[D:%.*]], align 2
+; LIMIT1-NEXT:    ret void
+;
+; LIMIT2-LABEL: @f(
+; LIMIT2-NEXT:  entry:
+; LIMIT2-NEXT:    [[TMP0:%.*]] = load i16, ptr [[B:%.*]], align 2
+; LIMIT2-NEXT:    [[TMP1:%.*]] = load i16, ptr [[M:%.*]], align 2
+; LIMIT2-NEXT:    br i1 [[C:%.*]], label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]]
+; LIMIT2:       if.then:
+; LIMIT2-NEXT:    call void @no_side_effects0()
+; LIMIT2-NEXT:    [[ADD:%.*]] = add nsw i16 [[TMP0]], 1
+; LIMIT2-NEXT:    [[U:%.*]] = add i16 [[ADD]], [[TMP1]]
+; LIMIT2-NEXT:    br label [[IF_END:%.*]]
+; LIMIT2:       if.else:
+; LIMIT2-NEXT:    call void @no_side_effects1()
+; LIMIT2-NEXT:    [[SUB:%.*]] = sub nsw i16 [[TMP0]], 1
+; LIMIT2-NEXT:    [[V:%.*]] = add i16 [[SUB]], [[TMP1]]
+; LIMIT2-NEXT:    br label [[IF_END]]
+; LIMIT2:       if.end:
+; LIMIT2-NEXT:    [[UV:%.*]] = phi i16 [ [[V]], [[IF_ELSE]] ], [ [[U]], [[IF_THEN]] ]
+; LIMIT2-NEXT:    store i16 [[UV]], ptr [[D:%.*]], align 2
+; LIMIT2-NEXT:    ret void
+;
+entry:
+  br i1 %c, label %if.then, label %if.else
+
+if.then:
+  %0 = load i16, ptr %b, align 2
+  call void @no_side_effects0()
+  %add = add nsw i16 %0, 1
+  %1 = load i16, ptr %m, align 2
+  %u = add i16 %add, %1
+  br label %if.end
+
+if.else:
+  %2 = load i16, ptr %b, align 2
+  call void @no_side_effects1()
+  %sub = sub nsw i16 %2, 1
+  %3 = load i16, ptr %m, align 2
+  %v = add i16 %sub, %3
+  br label %if.end
+
+if.end:
+  %uv = phi i16 [ %v, %if.else ], [ %u, %if.then ]
+  store i16 %uv, ptr %d, align 2
+  ret void
+}
+
+declare void @side_effects0()
+declare void @side_effects1()
+declare void @no_side_effects0() readonly nounwind willreturn
+declare void @no_side_effects1() readonly nounwind willreturn

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

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -S --passes='simplifycfg<hoist-common-insts>' %s | FileCheck %s
+
+;; Check that the two loads are hoisted to the common predecessor, skipping
+;; over the add/sub instructions.
+
+define void @f0(i1 %c, ptr nocapture noundef %d, ptr nocapture noundef readonly %m,  ptr nocapture noundef readonly %b) {
+; CHECK-LABEL: @f0(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = load i16, ptr [[B:%.*]], align 2
+; CHECK-NEXT:    [[TMP1:%.*]] = load i16, ptr [[M:%.*]], align 2
+; CHECK-NEXT:    br i1 [[C:%.*]], label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    [[ADD:%.*]] = add nsw i16 [[TMP0]], 1
+; CHECK-NEXT:    [[U:%.*]] = add i16 [[ADD]], [[TMP1]]
+; CHECK-NEXT:    br label [[IF_END:%.*]]
+; CHECK:       if.else:
+; CHECK-NEXT:    [[SUB:%.*]] = sub nsw i16 [[TMP0]], 1
+; CHECK-NEXT:    [[TMP2:%.*]] = add i16 [[SUB]], 3
+; CHECK-NEXT:    [[V:%.*]] = add i16 [[SUB]], [[TMP2]]
+; CHECK-NEXT:    br label [[IF_END]]
+; CHECK:       if.end:
+; CHECK-NEXT:    [[UV:%.*]] = phi i16 [ [[V]], [[IF_ELSE]] ], [ [[U]], [[IF_THEN]] ]
+; CHECK-NEXT:    store i16 [[UV]], ptr [[D:%.*]], align 2
+; CHECK-NEXT:    ret void
+;
+entry:
+  br i1 %c, label %if.then, label %if.else
+
+if.then:
+  %0 = load i16, ptr %b, align 2
+  %add = add nsw i16 %0, 1
+  %1 = load i16, ptr %m, align 2
+  %u = add i16 %add, %1
+  br label %if.end
+
+if.else:
+  %2 = load i16, ptr %b, align 2
+  %sub = sub nsw i16 %2, 1
+  %3 = load i16, ptr %m, align 2
+  %4 = add i16 %sub, 3
+  %v = add i16 %sub, %4
+  br label %if.end
+
+if.end:
+  %uv = phi i16 [ %v, %if.else ], [ %u, %if.then ]
+  store i16 %uv, ptr %d, align 2
+  ret void
+}
+
+
+;; Check some instructions (e.g. add) can be reordered across instructions with side
+;; effects, while others (e.g. load) can't.
+define void @f2(i1 %c, ptr nocapture noundef %d, ptr nocapture noundef readonly %m, ptr nocapture noundef readonly %b) {
+; CHECK-LABEL: @f2(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = load i16, ptr [[B:%.*]], align 2
+; CHECK-NEXT:    [[ADD_0:%.*]] = add nsw i16 [[TMP0]], 1
+; CHECK-NEXT:    br i1 [[C:%.*]], label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    call void @side_effects0()
+; CHECK-NEXT:    [[TMP1:%.*]] = load i16, ptr [[M:%.*]], align 2
+; CHECK-NEXT:    [[U:%.*]] = add i16 [[ADD_0]], [[TMP1]]
+; CHECK-NEXT:    br label [[IF_END:%.*]]
+; CHECK:       if.else:
+; CHECK-NEXT:    call void @no_side_effects0()
+; CHECK-NEXT:    [[TMP2:%.*]] = load i16, ptr [[M]], align 2
+; CHECK-NEXT:    [[V:%.*]] = add i16 [[ADD_0]], [[TMP2]]
+; CHECK-NEXT:    br label [[IF_END]]
+; CHECK:       if.end:
+; CHECK-NEXT:    [[UV:%.*]] = phi i16 [ [[V]], [[IF_ELSE]] ], [ [[U]], [[IF_THEN]] ]
+; CHECK-NEXT:    store i16 [[UV]], ptr [[D:%.*]], align 2
+; CHECK-NEXT:    ret void
+;
+entry:
+  br i1 %c, label %if.then, label %if.else
+
+if.then:
+  %0 = load i16, ptr %b, align 2
+  call void @side_effects0()
+  %add.0 = add nsw i16 %0, 1
+  %1 = load i16, ptr %m, align 2
+  %u = add i16 %add.0, %1
+  br label %if.end
+
+if.else:
+  %2 = load i16, ptr %b, align 2
+  call void @no_side_effects0()
+  %add.1 = add nsw i16 %2, 1
+  %3 = load i16, ptr %m, align 2
+  %v = add i16 %add.1, %3
+  br label %if.end
+
+if.end:
+  %uv = phi i16 [ %v, %if.else ], [ %u, %if.then ]
+  store i16 %uv, ptr %d, align 2
+  ret void
+}
+
+
+;; Check indeed it was the side effects that prevented hoisting the load
+;; in the previous test.
+define void @f3(i1 %c, ptr nocapture noundef %d, ptr nocapture noundef readonly %m, ptr nocapture noundef readonly %b) {
+; CHECK-LABEL: @f3(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = load i16, ptr [[B:%.*]], align 2
+; CHECK-NEXT:    [[ADD_0:%.*]] = add nsw i16 [[TMP0]], 1
+; CHECK-NEXT:    [[TMP1:%.*]] = load i16, ptr [[M:%.*]], align 2
+; CHECK-NEXT:    [[U:%.*]] = add i16 [[ADD_0]], [[TMP1]]
+; CHECK-NEXT:    br i1 [[C:%.*]], label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    call void @no_side_effects0()
+; CHECK-NEXT:    br label [[IF_END:%.*]]
+; CHECK:       if.else:
+; CHECK-NEXT:    call void @no_side_effects1()
+; CHECK-NEXT:    br label [[IF_END]]
+; CHECK:       if.end:
+; CHECK-NEXT:    store i16 [[U]], ptr [[D:%.*]], align 2
+; CHECK-NEXT:    ret void
+;
+entry:
+  br i1 %c, label %if.then, label %if.else
+
+if.then:
+  %0 = load i16, ptr %b, align 2
+  call void @no_side_effects0()
+  %add.0 = add nsw i16 %0, 1
+  %1 = load i16, ptr %m, align 2
+  %u = add i16 %add.0, %1
+  br label %if.end
+
+if.else:
+  %2 = load i16, ptr %b, align 2
+  call void @no_side_effects1()
+  %add.1 = add nsw i16 %2, 1
+  %3 = load i16, ptr %m, align 2
+  %v = add i16 %add.1, %3
+  br label %if.end
+
+if.end:
+  %uv = phi i16 [ %v, %if.else ], [ %u, %if.then ]
+  store i16 %uv, ptr %d, align 2
+  ret void
+}
+
+;; Check some instructions (e.g. sdiv) are not speculatively executed.
+
+;; Division by non-zero constant OK to speculate ...
+define void @f4(i1 %c, ptr nocapture noundef %d, ptr nocapture noundef readonly %m, ptr nocapture noundef readonly %b) {
+; CHECK-LABEL: @f4(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = load i16, ptr [[B:%.*]], align 2
+; CHECK-NEXT:    [[DIV_0:%.*]] = sdiv i16 [[TMP0]], 2
+; CHECK-NEXT:    [[U:%.*]] = add i16 [[DIV_0]], [[TMP0]]
+; CHECK-NEXT:    br i1 [[C:%.*]], label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    call void @side_effects0()
+; CHECK-NEXT:    br label [[IF_END:%.*]]
+; CHECK:       if.else:
+; CHECK-NEXT:    call void @side_effects1()
+; CHECK-NEXT:    br label [[IF_END]]
+; CHECK:       if.end:
+; CHECK-NEXT:    store i16 [[U]], ptr [[D:%.*]], align 2
+; CHECK-NEXT:    ret void
+;
+entry:
+  br i1 %c, label %if.then, label %if.else
+
+if.then:
+  %0 = load i16, ptr %b, align 2
+  call void @side_effects0()
+  %div.0 = sdiv i16 %0, 2
+  %u = add i16 %div.0, %0
+  br label %if.end
+
+if.else:
+  %1 = load i16, ptr %b, align 2
+  call void @side_effects1()
+  %div.1 = sdiv i16 %1, 2
+  %v = add i16 %div.1, %1
+  br label %if.end
+
+if.end:
+  %uv = phi i16 [ %v, %if.else ], [ %u, %if.then ]
+  store i16 %uv, ptr %d, align 2
+  ret void
+}
+
+;; ... but not a general division ...
+define void @f5(i1 %c, ptr nocapture noundef %d, ptr nocapture noundef readonly %m, ptr nocapture noundef readonly %b) {
+; CHECK-LABEL: @f5(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = load i16, ptr [[B:%.*]], align 2
+; CHECK-NEXT:    br i1 [[C:%.*]], label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    call void @side_effects0()
+; CHECK-NEXT:    [[DIV_0:%.*]] = sdiv i16 211, [[TMP0]]
+; CHECK-NEXT:    [[U:%.*]] = add i16 [[DIV_0]], [[TMP0]]
+; CHECK-NEXT:    br label [[IF_END:%.*]]
+; CHECK:       if.else:
+; CHECK-NEXT:    call void @side_effects1()
+; CHECK-NEXT:    [[DIV_1:%.*]] = sdiv i16 211, [[TMP0]]
+; CHECK-NEXT:    [[V:%.*]] = add i16 [[DIV_1]], [[TMP0]]
+; CHECK-NEXT:    br label [[IF_END]]
+; CHECK:       if.end:
+; CHECK-NEXT:    [[UV:%.*]] = phi i16 [ [[V]], [[IF_ELSE]] ], [ [[U]], [[IF_THEN]] ]
+; CHECK-NEXT:    store i16 [[UV]], ptr [[D:%.*]], align 2
+; CHECK-NEXT:    ret void
+;
+entry:
+  br i1 %c, label %if.then, label %if.else
+
+if.then:
+  %0 = load i16, ptr %b, align 2
+  call void @side_effects0()
+  %div.0 = sdiv i16 211, %0
+  %u = add i16 %div.0, %0
+  br label %if.end
+
+if.else:
+  %1 = load i16, ptr %b, align 2
+  call void @side_effects1()
+  %div.1 = sdiv i16 211, %1
+  %v = add i16 %div.1, %1
+  br label %if.end
+
+if.end:
+  %uv = phi i16 [ %v, %if.else ], [ %u, %if.then ]
+  store i16 %uv, ptr %d, align 2
+  ret void
+}
+
+;; ... and it's also OK to hoist the division when there's no speculation happening.
+define void @f6(i1 %c, ptr nocapture noundef %d, ptr nocapture noundef readonly %m, ptr nocapture noundef readonly %b) {
+; CHECK-LABEL: @f6(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = load i16, ptr [[B:%.*]], align 2
+; CHECK-NEXT:    [[DIV_0:%.*]] = sdiv i16 211, [[TMP0]]
+; CHECK-NEXT:    [[U:%.*]] = add i16 [[DIV_0]], [[TMP0]]
+; CHECK-NEXT:    br i1 [[C:%.*]], label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    call void @no_side_effects0()
+; CHECK-NEXT:    br label [[IF_END:%.*]]
+; CHECK:       if.else:
+; CHECK-NEXT:    call void @no_side_effects1()
+; CHECK-NEXT:    br label [[IF_END]]
+; CHECK:       if.end:
+; CHECK-NEXT:    store i16 [[U]], ptr [[D:%.*]], align 2
+; CHECK-NEXT:    ret void
+;
+entry:
+  br i1 %c, label %if.then, label %if.else
+
+if.then:
+  %0 = load i16, ptr %b, align 2
+  call void @no_side_effects0()
+  %div.0 = sdiv i16 211, %0
+  %u = add i16 %div.0, %0
+  br label %if.end
+
+if.else:
+  %1 = load i16, ptr %b, align 2
+  call void @no_side_effects1()
+  %div.1 = sdiv i16 211, %1
+  %v = add i16 %div.1, %1
+  br label %if.end
+
+if.end:
+  %uv = phi i16 [ %v, %if.else ], [ %u, %if.then ]
+  store i16 %uv, ptr %d, align 2
+  ret void
+}
+
+;; No reorder of store over a load.
+define i16 @f7(i1 %c, ptr %a, ptr %b) {
+; CHECK-LABEL: @f7(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[C:%.*]], label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    [[VA:%.*]] = load i16, ptr [[A:%.*]], align 2
+; CHECK-NEXT:    store i16 0, ptr [[B:%.*]], align 2
+; CHECK-NEXT:    br label [[IF_END:%.*]]
+; CHECK:       if.else:
+; CHECK-NEXT:    [[VB:%.*]] = load i16, ptr [[B]], align 2
+; CHECK-NEXT:    store i16 0, ptr [[B]], align 2
+; CHECK-NEXT:    br label [[IF_END]]
+; CHECK:       if.end:
+; CHECK-NEXT:    [[V:%.*]] = phi i16 [ [[VA]], [[IF_THEN]] ], [ [[VB]], [[IF_ELSE]] ]
+; CHECK-NEXT:    ret i16 [[V]]
+;
+entry:
+  br i1 %c, label %if.then, label %if.else
+
+if.then:
+  %va = load i16, ptr %a, align 2
+  store i16 0, ptr %b, align 2
+  br label %if.end
+
+if.else:
+  %vb = load i16, ptr %b, align 2
+  store i16 0, ptr %b, align 2
+  br label %if.end
+
+if.end:
+  %v = phi i16 [ %va, %if.then ], [ %vb, %if.else ]
+  ret i16 %v
+}
+
+;; Can reorder load over another load
+define i16 @f8(i1 %cond, ptr %a, ptr %b, ptr %c) {
+; CHECK-LABEL: @f8(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[C_0:%.*]] = load i16, ptr [[C:%.*]], align 2
+; CHECK-NEXT:    br i1 [[COND:%.*]], label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    [[VA:%.*]] = load i16, ptr [[A:%.*]], align 2
+; CHECK-NEXT:    br label [[IF_END:%.*]]
+; CHECK:       if.else:
+; CHECK-NEXT:    [[VB:%.*]] = load i16, ptr [[B:%.*]], align 2
+; CHECK-NEXT:    br label [[IF_END]]
+; CHECK:       if.end:
+; CHECK-NEXT:    [[V:%.*]] = phi i16 [ [[VA]], [[IF_THEN]] ], [ [[VB]], [[IF_ELSE]] ]
+; CHECK-NEXT:    [[U:%.*]] = phi i16 [ [[C_0]], [[IF_THEN]] ], [ [[C_0]], [[IF_ELSE]] ]
+; CHECK-NEXT:    [[W:%.*]] = add i16 [[V]], [[U]]
+; CHECK-NEXT:    ret i16 [[W]]
+;
+entry:
+  br i1 %cond, label %if.then, label %if.else
+
+if.then:
+  %va = load i16, ptr %a, align 2
+  %c.0 = load i16, ptr %c
+  br label %if.end
+
+if.else:
+  %vb = load i16, ptr %b, align 2
+  %c.1 = load i16, ptr %c
+  br label %if.end
+
+if.end:
+  %v = phi i16 [ %va, %if.then ], [ %vb, %if.else ]
+  %u = phi i16 [ %c.0, %if.then ], [ %c.1, %if.else ]
+
+  %w = add i16 %v, %u
+
+  ret i16 %w
+}
+
+;; Currently won't reorder volatile and non-volatile loads.
+define i16 @f9(i1 %cond, ptr %a, ptr %b, ptr %c) {
+; CHECK-LABEL: @f9(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[COND:%.*]], label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    [[VA:%.*]] = load volatile i16, ptr [[A:%.*]], align 2
+; CHECK-NEXT:    [[C_0:%.*]] = load i16, ptr [[C:%.*]], align 2
+; CHECK-NEXT:    br label [[IF_END:%.*]]
+; CHECK:       if.else:
+; CHECK-NEXT:    [[VB:%.*]] = load i16, ptr [[B:%.*]], align 2
+; CHECK-NEXT:    [[C_1:%.*]] = load i16, ptr [[C]], align 2
+; CHECK-NEXT:    br label [[IF_END]]
+; CHECK:       if.end:
+; CHECK-NEXT:    [[V:%.*]] = phi i16 [ [[VA]], [[IF_THEN]] ], [ [[VB]], [[IF_ELSE]] ]
+; CHECK-NEXT:    [[U:%.*]] = phi i16 [ [[C_0]], [[IF_THEN]] ], [ [[C_1]], [[IF_ELSE]] ]
+; CHECK-NEXT:    [[W:%.*]] = add i16 [[V]], [[U]]
+; CHECK-NEXT:    ret i16 [[W]]
+;
+entry:
+  br i1 %cond, label %if.then, label %if.else
+
+if.then:
+  %va = load volatile i16, ptr %a, align 2
+  %c.0 = load i16, ptr %c
+  br label %if.end
+
+if.else:
+  %vb = load i16, ptr %b, align 2
+  %c.1 = load i16, ptr %c
+  br label %if.end
+
+if.end:
+  %v = phi i16 [ %va, %if.then ], [ %vb, %if.else ]
+  %u = phi i16 [ %c.0, %if.then ], [ %c.1, %if.else ]
+
+  %w = add i16 %v, %u
+
+  ret i16 %w
+}
+
+declare void @side_effects0()
+declare void @side_effects1()
+declare void @no_side_effects0() readonly nounwind willreturn
+declare void @no_side_effects1() readonly nounwind willreturn