[InstCombine] Sink pure instructions down to return and unreachable blocks

[mkazantsev]

Summary

If the only user of Instr is in a return or unreachable block, we can
sink Instr to the`User` safely (unless it reads/writes memory).
Return or unreachable blocks are guaranteed to execute zero
or one time, and Instr always dominates User, so they either will
be executed together (execution of User always implies execution
of Instr) or not executed at all.

[jdoerfert]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

3453

This is not correct for things that throw, things that synchronize, e.g., warp shuffles on GPUs, (and things that loop forever once we have a way to disable forward propagation guarantee).

Please add a readnone call test to expose the above. You can probably ask I->isSafeToRemove() && !I->mayReadFromMemory() to determine if it can be moved. Effectively, we might actually remove it from a path that does not end in the user instruction. If the path ends in the user instruction, the fact that we could remove it does mean the value is not interfering with something else. It also doesn't read memory, so we are good.

We still have to fix isSafeToRemove wrt. the syncs and endless loops I mentioned above but that is a separate issue.

---

Nit: Dominance relation broken?

[mkazantsev]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

3453

This is not correct for things that throw, things that synchronize, e.g., warp shuffles on GPUs, (and things that loop forever once we have a way to disable forward propagation guarantee).

These things are checked inside TryToSinkInstruction. It only sinks non-side-effecting things.

[mkazantsev]

Fixed dominance check message. As for side-effecting, non-finishing etc. instructions, all comment applies to existing sinking as well, and this check is being done inside of TryToSinkInstruction.

[mkazantsev]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

3448

This can actually be reduced to mayReadMemory, but writes will be rejected in TryToSinkInstruction anyways.

[jdoerfert]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

3448

I see. I think we should adjust the comment.

Maybe we should not test the instruction at all and instead extend the TryToSink logic.
TryToSink does the test side-effect test already and it can also deal with instructions reading memory, though only when sink to the successor. If this logic is in there we know what tests to apply and which ones not. We also have a clearer path forward for extensions. Maybe I miss a reason to keep the logic here?

3453

Agreed on the side-effects (which include throwing). The shuffles are a separate mess that is not part of this patch. looping forever is not yet a well defined semantic but UB so we are also good on that front. After reading the comment I was not looking into the TryToSink.

[mkazantsev]

Move memory read check to where it truly belongs - inside TryToSinkInstruction.

[mkazantsev]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

3448

You are right, this check should be in TryToSinkInstruction. I just moved it there.

[mkazantsev]

Fixed typo in block comparison.

[mkazantsev]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

3453

Actually I'm not sure about "looping forever", it is UB in C++ but I don't remember if LLVM has any conclusive answer whether it is UB in it or not. Anyways, this problem with infinite looping exists in current code as well.

[jdoerfert]

Thanks for the changes and explanations so far! I added another comment.

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

3309

I first thought:
This is more restrictive than you want it to be.
DestBlock != I->getParent()->getUniqueSuccessor is what u want.
(There is even a less strict restriction but that is more complicated.)
That allows DestBlock to have multiple predecessors (maybe add at test).

Then I realized this is also the test outside. Though, I still think the above is what we want here.

3453

The "de-facto" answer for now is we assume forward progress guarantees (in various places). The full story is more complicated but hopefully we'll clean it up with an attribute soon. Anyway, not relevant here ;)

---

You can also do: Terminator->getNumSuccessors() == 0;

[mkazantsev]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

3309

This is not true. We don't want to sink from A to C in case:

A    B
 \  /
  C

because BC may be a hot path and A is "nearly never executed" block.

[mkazantsev]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

3309

Maybe the example above will be more clear like this:

A
| 
C<-|
|  |
B--|

Though, we want to sink from A to either B or C in case

  A
 /  \
B    C

[mkazantsev]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

3453

You can also do: Terminator->getNumSuccessors() == 0;

I think it's true, but I'd rather keep it as is to make it absolutely obvious what we are doing.

[jdoerfert]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

3309

(I guess I should not look at code tired. Since I'm still doing it, please continue to be patient with me.)

The first version of this was not checking the relation, right?

Now, could we check the UserInst to be not a PHI to avoid the problematic cases and allow

 [I]
 / \
[] []
 \ /
 [ = .. I]
`

Do we want that?

[mkazantsev]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

3309

UserInst being a Phi is a special case. General rule for InstCombine is that it does not increase number of instructions (unless it gives some clear benefits). If user in the block below is a phi, we cannot sink I without duplication. We are not doing this.

Do we want that?

For loads - we don't, and the only reason of this is that [] is a potentially big piece of code that needs a full-scale alias analysis. InstCombine is supposed to be lightweight and it's not doing that.

For not loads - my patch will handle this (supposed that user block ends with return).

[mkazantsev]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

3309

Actually, if I is a Phi, and user block does not have other inputs except for those that use I - maybe we could sink, but it's going FAAAR beyond the scope of this patch. :)

[jdoerfert]

If the two tests I mentioned are added and work as expected, I think this is OK. I'm a little worried we move in one case where we shouldn't without the PHI user logic I describe below.

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

3309

The idea was that if the unique user of I (in the return block) is *not* a PHI, I must dominate the user and therefore it is executed at least as often as the user. If that is true, and I does not read memory (among other things) it is beneficial to move it regardless of the unique predecessor thing. If you wanted to prevent that, wouldn't you need the predecessor check for all instructions, not only the ones that may read, in order to *prevent moving* what I describe above. Asked differently, is %a below moved? (It is not right now: https://godbolt.org/z/Y5BxGQ)

bb0:
  %a = add i32 %arg0, 1
  br i1 %c, label %bb1, label %bb2
bb1:
  br label %bb3
bb2:
  br label %bb3
bb3:
  %p = phi i32 [0, %bb1], [1, %bb2]
  %r = add i32 %p, %a
  ret i32 %r

I'd say we want the movement but we need a test.

---

We should also have this as a test: https://godbolt.org/z/U8KrtS
It shows the argument you made earlier, don't sink into more often executed block.

[mkazantsev]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

3309

Ok, I will add these tests.

[mkazantsev]

Added tests.

[asbirlea]

FWIW, the added tests look good.

I don't really see how the case of not sinking from A when A and B blocks merge in C can happen, if this applies for non-memory instructions only. But if it can, having a test for this would be good too.

[mkazantsev]

In D80120#2048216, @asbirlea wrote:

FWIW, the added tests look good.

I don't really see how the case of not sinking from A when A and B blocks merge in C can happen, if this applies for non-memory instructions only. But if it can, having a test for this would be good too.

The only case where this may theoretically happen is shown in test_05_neg. The Phi in return block bb3 initiates sinking from bb0 to bb2, but it gets rejected because bb2 has 2 preds. Another example of that (with non-phi instruction in ret block) is just not possible in SSA.

[asbirlea]

In D80120#2048273, @mkazantsev wrote:

In D80120#2048216, @asbirlea wrote:

FWIW, the added tests look good.

I don't really see how the case of not sinking from A when A and B blocks merge in C can happen, if this applies for non-memory instructions only. But if it can, having a test for this would be good too.

The only case where this may theoretically happen is shown in test_05_neg. The Phi in return block bb3 initiates sinking from bb0 to bb2, but it gets rejected because bb2 has 2 preds. Another example of that (with non-phi instruction in ret block) is just not possible in SSA.

Right! I could not think of a case without a loop. Thank you for confirming!
This lgtm. Leaving the final review to @jdoerfert.

[jdoerfert]

LGTM. Thanks!

[mkazantsev]

Thanks!

[maxim-kuvyrkov]

Hi @mkazantsev ,
Linaro benchmarking CI flagged this patch as increases code-size of SPEC2k6's 401.bzip2 by 3% on ARM (Thumb2 mode) and by 5% on AArch64. This happens at -Os -flto.

Would you please check if this triggers a corner-case in your patch or something else that we can easily fix?

Thanks!

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

static bool TryToSinkInstruction(Instruction *I, BasicBlock *DestBlock) {
   }
   // We can only sink load instructions if there is nothing between the load and
   // the end of block that could change the value.
   if (I->mayReadFromMemory()) {
     for (BasicBlock::iterator Scan = I->getIterator(),
                               E = I->getParent()->end();
          Scan != E; ++Scan)
       if (Scan->mayWriteToMemory())
         return false;
   }
 
   I->dropDroppableUses([DestBlock](const Use *U) {
     if (auto *I = dyn_cast<Instruction>(U->getUser()))
       return I->getParent() != DestBlock;
     return true;
   });
   /// FIXME: We could remove droppable uses that are not dominated by
if (!I->use_empty() &&
         ++NumConstProp;
         if (isInstructionTriviallyDead(I, &TLI))
           eraseInstFromFunction(*I);
         MadeIRChange = true;
         continue;
       }
     }
 
-    // See if we can trivially sink this instruction to a successor basic block.
+    // See if we can trivially sink this instruction to its user if we can
+    // prove that the successor is not executed more frequently than our block.
     if (EnableCodeSinking)
       if (Use *SingleUse = I->getSingleUndroppableUse()) {
         BasicBlock *BB = I->getParent();
         Instruction *UserInst = cast<Instruction>(SingleUse->getUser());
         BasicBlock *UserParent;
 
         // Get the block the use occurs in.
         if (PHINode *PN = dyn_cast<PHINode>(UserInst))
           UserParent = PN->getIncomingBlock(*SingleUse);
         else
           UserParent = UserInst->getParent();
 
         if (UserParent != BB) {
           // See if the user is one of our successors that has only one
           // predecessor, so that we don't have to split the critical edge.
-          if (UserParent->getUniquePredecessor() == BB) {
+          bool ShouldSink = UserParent->getUniquePredecessor() == BB;
+          // Another option where we can sink is a block that ends with a
+          // terminator that does not pass control to other block (such as
+          // return or unreachable). In this case:
+          //   - I dominates the User (by SSA form);
+          //   - the User will be executed at most once.
+          // So sinking I down to User is always profitable or neutral.
+          // Only do it if I may not read or write memory to avoid dealing
+          // with alias analysis.
+          if (!ShouldSink && !I->mayReadOrWriteMemory()) {
+            auto *Term = UserParent->getTerminator();
+            ShouldSink = isa<ReturnInst>(Term) || isa<UnreachableInst>(Term);
+          }
+          if (ShouldSink) {
+            assert(DT.dominates(BB, UserParent) &&
+                   "Dominance relation broken?");
             // Okay, the CFG is simple enough, try to sink this instruction.
             if (TryToSinkInstruction(I, UserParent)) {
               LLVM_DEBUG(dbgs() << "IC: Sink: " << *I << '\n');
               MadeIRChange = true;
               // We'll add uses of the sunk instruction below, but since sinking
               // can expose opportunities for it's *operands* add them to the
               // worklist
               for (Use &U : I->operands())

llvm/test/Transforms/InstCombine/insert-extract-shuffle.ll

 
 ; PR26354: https://llvm.org/bugs/show_bug.cgi?id=26354
 ; Don't create a shufflevector if we know that we're not going to replace the insertelement.
 
 define double @pr26354(<2 x double>* %tmp, i1 %B) {
 ; CHECK-LABEL: @pr26354(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[LD:%.*]] = load <2 x double>, <2 x double>* [[TMP:%.*]], align 16
-; CHECK-NEXT:    [[E1:%.*]] = extractelement <2 x double> [[LD]], i32 0
 ; CHECK-NEXT:    br i1 [[B:%.*]], label [[IF:%.*]], label [[END:%.*]]
 ; CHECK:       if:
 ; CHECK-NEXT:    [[E2:%.*]] = extractelement <2 x double> [[LD]], i32 1
 ; CHECK-NEXT:    [[I1:%.*]] = insertelement <4 x double> <double 0.000000e+00, double 0.000000e+00, double 0.000000e+00, double undef>, double [[E2]], i32 3
 ; CHECK-NEXT:    br label [[END]]
 ; CHECK:       end:
 ; CHECK-NEXT:    [[PH:%.*]] = phi <4 x double> [ undef, [[ENTRY:%.*]] ], [ [[I1]], [[IF]] ]
+; CHECK-NEXT:    [[E1:%.*]] = extractelement <2 x double> [[LD]], i32 0
 ; CHECK-NEXT:    [[E3:%.*]] = extractelement <4 x double> [[PH]], i32 1
 ; CHECK-NEXT:    [[MU:%.*]] = fmul double [[E1]], [[E3]]
 ; CHECK-NEXT:    ret double [[MU]]
 ;
 
 entry:
   %ld = load <2 x double>, <2 x double>* %tmp
   %e1 = extractelement <2 x double> %ld, i32 0

llvm/test/Transforms/InstCombine/overflow.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -instcombine < %s | FileCheck %s
 ; <rdar://problem/8558713>
 
 declare void @throwAnExceptionOrWhatever()
 
 define i32 @test1(i32 %a, i32 %b) nounwind ssp {
 ; CHECK-LABEL: @test1(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[SADD:%.*]] = call { i32, i1 } @llvm.sadd.with.overflow.i32(i32 [[B:%.*]], i32 [[A:%.*]])
-; CHECK-NEXT:    [[SADD_RESULT:%.*]] = extractvalue { i32, i1 } [[SADD]], 0
 ; CHECK-NEXT:    [[TMP0:%.*]] = extractvalue { i32, i1 } [[SADD]], 1
 ; CHECK-NEXT:    br i1 [[TMP0]], label [[IF_THEN:%.*]], label [[IF_END:%.*]]
 ; CHECK:       if.then:
 ; CHECK-NEXT:    tail call void @throwAnExceptionOrWhatever() #2
 ; CHECK-NEXT:    br label [[IF_END]]
 ; CHECK:       if.end:
+; CHECK-NEXT:    [[SADD_RESULT:%.*]] = extractvalue { i32, i1 } [[SADD]], 0
 ; CHECK-NEXT:    ret i32 [[SADD_RESULT]]
 ;
 entry:
   %conv = sext i32 %a to i64
   %conv2 = sext i32 %b to i64
   %add = add nsw i64 %conv2, %conv
   %add.off = add i64 %add, 2147483648
   %0 = icmp ugt i64 %add.off, 4294967295

llvm/test/Transforms/InstCombine/sink_to_unreachable.ll

unreached:
   call void @use(i32 %comparator)
   unreachable
 
 exit:
   ret void
 }
 
 
-; TODO: %comparator and %signed can be sunk down to unreachable just as in
-; test above.
 define void @test_02(i32 %x, i32 %y) {
 ; CHECK-LABEL: @test_02(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[C1:%.*]] = icmp eq i32 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[C2:%.*]] = icmp slt i32 [[X]], [[Y]]
-; CHECK-NEXT:    [[SIGNED:%.*]] = select i1 [[C2]], i32 -1, i32 1
-; CHECK-NEXT:    [[COMPARATOR:%.*]] = select i1 [[C1]], i32 0, i32 [[SIGNED]]
+; CHECK-NEXT:    [[C2:%.*]] = icmp slt i32 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    br i1 [[C2]], label [[EXIT:%.*]], label [[MEDIUM:%.*]]
 ; CHECK:       medium:
 ; CHECK-NEXT:    [[C3:%.*]] = icmp sgt i32 [[X]], [[Y]]
 ; CHECK-NEXT:    br i1 [[C3]], label [[EXIT]], label [[UNREACHED:%.*]]
 ; CHECK:       unreached:
+; CHECK-NEXT:    [[C1:%.*]] = icmp eq i32 [[X]], [[Y]]
+; CHECK-NEXT:    [[SIGNED:%.*]] = select i1 [[C2]], i32 -1, i32 1
+; CHECK-NEXT:    [[COMPARATOR:%.*]] = select i1 [[C1]], i32 0, i32 [[SIGNED]]
 ; CHECK-NEXT:    call void @use(i32 [[COMPARATOR]])
 ; CHECK-NEXT:    unreachable
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %c1 = icmp eq i32 %x, %y
   %c2 = icmp slt i32 %x, %y
   %signed = select i1 %c2, i32 -1, i32 1
   %comparator = select i1 %c1, i32 0, i32 %signed
   br i1 %c2, label %exit, label %medium
 
 medium:
   %c3 = icmp sgt i32 %x, %y
   br i1 %c3, label %exit, label %unreached
 
 unreached:
   call void @use(i32 %comparator)
   unreachable
 
 exit:
   ret void
 }
+
+define i32 @test_03(i32 %x, i32 %y) {
+; CHECK-LABEL: @test_03(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[C2:%.*]] = icmp slt i32 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    br i1 [[C2]], label [[EXIT:%.*]], label [[MEDIUM:%.*]]
+; CHECK:       medium:
+; CHECK-NEXT:    [[C3:%.*]] = icmp sgt i32 [[X]], [[Y]]
+; CHECK-NEXT:    br i1 [[C3]], label [[EXIT]], label [[UNREACHED:%.*]]
+; CHECK:       unreached:
+; CHECK-NEXT:    [[C1:%.*]] = icmp eq i32 [[X]], [[Y]]
+; CHECK-NEXT:    [[SIGNED:%.*]] = select i1 [[C2]], i32 -1, i32 1
+; CHECK-NEXT:    [[COMPARATOR:%.*]] = select i1 [[C1]], i32 0, i32 [[SIGNED]]
+; CHECK-NEXT:    ret i32 [[COMPARATOR]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret i32 0
+;
+entry:
+  %c1 = icmp eq i32 %x, %y
+  %c2 = icmp slt i32 %x, %y
+  %signed = select i1 %c2, i32 -1, i32 1
+  %comparator = select i1 %c1, i32 0, i32 %signed
+  br i1 %c2, label %exit, label %medium
+
+medium:
+  %c3 = icmp sgt i32 %x, %y
+  br i1 %c3, label %exit, label %unreached
+
+unreached:
+  ret i32 %comparator
+
+exit:
+  ret i32 0
+}

llvm/test/Transforms/PGOProfile/chr.ll

 ;   if ((j0 & 8) != 0)
 ;     foo()
 ; }
 ; return sum
 define i32 @test_chr_7_1(i32* %i, i32* %j, i32 %sum0) !prof !14 {
 ; CHECK-LABEL: @test_chr_7_1(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[I0:%.*]] = load i32, i32* [[I:%.*]], align 4
-; CHECK-NEXT:    [[V3:%.*]] = and i32 [[I0]], 2
-; CHECK-NEXT:    [[V4:%.*]] = icmp eq i32 [[V3]], 0
-; CHECK-NEXT:    [[V8:%.*]] = add i32 [[SUM0:%.*]], 43
-; CHECK-NEXT:    [[SUM2:%.*]] = select i1 [[V4]], i32 [[SUM0]], i32 [[V8]], !prof !16
 ; CHECK-NEXT:    call void @foo()
 ; CHECK-NEXT:    [[J0:%.*]] = load i32, i32* [[J:%.*]], align 4
 ; CHECK-NEXT:    [[TMP0:%.*]] = and i32 [[J0]], 12
 ; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i32 [[TMP0]], 12
 ; CHECK-NEXT:    br i1 [[TMP1]], label [[BB0:%.*]], label [[ENTRY_SPLIT_NONCHR:%.*]], !prof !15
 ; CHECK:       bb0:
 ; CHECK-NEXT:    call void @foo()
 ; CHECK-NEXT:    call void @foo()
 ; CHECK-NEXT:    br label [[BB3:%.*]]
 ; CHECK:       entry.split.nonchr:
 ; CHECK-NEXT:    [[V9:%.*]] = and i32 [[J0]], 4
 ; CHECK-NEXT:    [[V10:%.*]] = icmp eq i32 [[V9]], 0
 ; CHECK-NEXT:    br i1 [[V10]], label [[BB1_NONCHR:%.*]], label [[BB0_NONCHR:%.*]], !prof !16
 ; CHECK:       bb0.nonchr:
 ; CHECK-NEXT:    call void @foo()
 ; CHECK-NEXT:    br label [[BB1_NONCHR]]
 ; CHECK:       bb1.nonchr:
 ; CHECK-NEXT:    [[V11_NONCHR:%.*]] = and i32 [[J0]], 8
 ; CHECK-NEXT:    [[V12_NONCHR:%.*]] = icmp eq i32 [[V11_NONCHR]], 0
 ; CHECK-NEXT:    br i1 [[V12_NONCHR]], label [[BB3]], label [[BB2_NONCHR:%.*]], !prof !16
 ; CHECK:       bb2.nonchr:
 ; CHECK-NEXT:    call void @foo()
 ; CHECK-NEXT:    br label [[BB3]]
 ; CHECK:       bb3:
+; CHECK-NEXT:    [[V3:%.*]] = and i32 [[I0]], 2
+; CHECK-NEXT:    [[V4:%.*]] = icmp eq i32 [[V3]], 0
+; CHECK-NEXT:    [[V8:%.*]] = add i32 [[SUM0:%.*]], 43
+; CHECK-NEXT:    [[SUM2:%.*]] = select i1 [[V4]], i32 [[SUM0]], i32 [[V8]], !prof !16
 ; CHECK-NEXT:    ret i32 [[SUM2]]
 ;
 entry:
   %i0 = load i32, i32* %i
   %v3 = and i32 %i0, 2
   %v4 = icmp eq i32 %v3, 0
   %v8 = add i32 %sum0, 43
   %sum2 = select i1 %v4, i32 %sum0, i32 %v8, !prof !15

 ; CHECK-NEXT:    call void @foo()
 ; CHECK-NEXT:    br label [[BB1]]
 ; CHECK:       bb1:
 ; CHECK-NEXT:    [[J0:%.*]] = load i32, i32* [[J:%.*]], align 4
 ; CHECK-NEXT:    [[V6:%.*]] = and i32 [[I0]], 2
 ; CHECK-NEXT:    [[V4:%.*]] = icmp eq i32 [[V6]], [[J0]]
 ; CHECK-NEXT:    [[V8:%.*]] = add i32 [[SUM0:%.*]], 43
 ; CHECK-NEXT:    [[SUM2:%.*]] = select i1 [[V4]], i32 [[SUM0]], i32 [[V8]], !prof !16
-; CHECK-NEXT:    [[V5:%.*]] = icmp eq i32 [[I0]], [[SUM2]]
-; CHECK-NEXT:    [[SUM3:%.*]] = select i1 [[V5]], i32 [[SUM2]], i32 [[V8]], !prof !16
 ; CHECK-NEXT:    call void @foo()
 ; CHECK-NEXT:    [[V9:%.*]] = and i32 [[I0]], 4
 ; CHECK-NEXT:    [[V10:%.*]] = icmp eq i32 [[V9]], 0
 ; CHECK-NEXT:    br i1 [[V10]], label [[BB3:%.*]], label [[BB2:%.*]]
 ; CHECK:       bb2:
 ; CHECK-NEXT:    call void @foo()
 ; CHECK-NEXT:    br label [[BB3]]
 ; CHECK:       bb3:
+; CHECK-NEXT:    [[V5:%.*]] = icmp eq i32 [[I0]], [[SUM2]]
+; CHECK-NEXT:    [[SUM3:%.*]] = select i1 [[V5]], i32 [[SUM2]], i32 [[V8]], !prof !16
 ; CHECK-NEXT:    [[V11:%.*]] = add i32 [[I0]], [[SUM3]]
 ; CHECK-NEXT:    ret i32 [[V11]]
 ;
 entry:
   %i0 = load i32, i32* %i
   %v0 = icmp eq i32 %z, 0
   %v1 = icmp ne i32 %z, 1
   %v2 = select i1 %v1, i1 %pred, i1 true, !prof !15

 
 bb10:
   ret i32 45
 }
 
 ; Test a case with a really long use-def chains. This test checks that it's not
 ; really slow and doesn't appear to be hanging.
 define i64 @test_chr_22(i1 %i, i64* %j, i64 %v0) !prof !14 {
+; CHECK-LABEL: @test_chr_22(
+; CHECK-NEXT:  bb0:
+; CHECK-NEXT:    [[V1:%.*]] = add i64 [[V0:%.*]], 3
+; CHECK-NEXT:    [[V2:%.*]] = add i64 [[V1]], [[V0]]
+; CHECK-NEXT:    [[C1:%.*]] = icmp slt i64 [[V2]], 100
+; CHECK-NEXT:    [[V300:%.*]] = mul i64 [[V2]], -8647960034816487527
+; CHECK-NEXT:    [[V301:%.*]] = icmp ne i64 [[V300]], 100
+; CHECK-NEXT:    [[TMP0:%.*]] = and i1 [[C1]], [[V301]]
+; CHECK-NEXT:    br i1 [[TMP0]], label [[BB0_SPLIT:%.*]], label [[BB0_SPLIT_NONCHR:%.*]], !prof !15
+; CHECK:       bb0.split:
+; CHECK-NEXT:    [[V299:%.*]] = mul i64 [[V2]], 7860086430977039991
+; CHECK-NEXT:    store i64 [[V299]], i64* [[J:%.*]], align 4
+; CHECK-NEXT:    ret i64 99
+; CHECK:       bb0.split.nonchr:
+; CHECK-NEXT:    [[V300_NONCHR:%.*]] = mul i64 [[V2]], -8647960034816487527
+; CHECK-NEXT:    [[V301_NONCHR:%.*]] = icmp eq i64 [[V300_NONCHR]], 100
+; CHECK-NEXT:    [[V302_NONCHR_V:%.*]] = select i1 [[V301_NONCHR]], i64 1938697607916024098, i64 7860086430977039991, !prof !16
+; CHECK-NEXT:    [[V302_NONCHR:%.*]] = mul i64 [[V2]], [[V302_NONCHR_V]]
+; CHECK-NEXT:    store i64 [[V302_NONCHR]], i64* [[J]], align 4
+; CHECK-NEXT:    ret i64 99
+;
 bb0:
   %v1 = add i64 %v0, 3
   %v2 = add i64 %v1, %v0
   %c1 = icmp sgt i64 %v2, 99
   %v3 = select i1 %c1, i64 %v1, i64 %v2, !prof !15
   %v4 = add i64 %v2, %v2
   %v5 = add i64 %v4, %v2
   %v6 = add i64 %v5, %v4
bb0:
   ret i64 99
 }
 
 ; Test a case with a really long use-def chains. This test checks that it's not
 ; really slow and doesn't appear to be hanging. This is different from
 ; test_chr_22 in that it has nested control structures (multiple scopes) and
 ; covers additional code.
 define i64 @test_chr_23(i64 %v0) !prof !14 {
+; CHECK-LABEL: @test_chr_23(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = mul i64 [[V0:%.*]], 50
+; CHECK-NEXT:    [[V10:%.*]] = icmp ne i64 [[TMP0]], -50
+; CHECK-NEXT:    ret i64 99
+;
 entry:
   %v1 = add i64 %v0, 3
   %v2 = add i64 %v1, %v1
   %v3 = add i64 %v2, %v1
   %v4 = add i64 %v2, %v3
   %v5 = add i64 %v4, %v2
   %v6 = add i64 %v5, %v4
   %v7 = add i64 %v6, %v5
body.9:
   br label %end
 
 end:
   ret i64 99
 }
 
 ; Test to not crash upon a 0:0 branch_weight metadata.
 define void @test_chr_24(i32* %i) !prof !14 {
+; CHECK-LABEL: @test_chr_24(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = load i32, i32* [[I:%.*]], align 4
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[TMP0]], 1
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i32 [[TMP1]], 0
+; CHECK-NEXT:    br i1 [[TMP2]], label [[BB1:%.*]], label [[BB0:%.*]], !prof !21
+; CHECK:       bb0:
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    br label [[BB1]]
+; CHECK:       bb1:
+; CHECK-NEXT:    [[TMP3:%.*]] = and i32 [[TMP0]], 2
+; CHECK-NEXT:    [[TMP4:%.*]] = icmp eq i32 [[TMP3]], 0
+; CHECK-NEXT:    br i1 [[TMP4]], label [[BB3:%.*]], label [[BB2:%.*]], !prof !21
+; CHECK:       bb2:
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    ret void
+;
 entry:
   %0 = load i32, i32* %i
   %1 = and i32 %0, 1
   %2 = icmp eq i32 %1, 0
   br i1 %2, label %bb1, label %bb0, !prof !17
 
 bb0:
   call void @foo()

llvm/test/Transforms/SimplifyCFG/merge-cond-stores.ll

 
 ; This should get if-converted.
 define i32 @test_diamond_simple(i32* %p, i32* %q, i32 %a, i32 %b) {
 ; CHECK-LABEL: @test_diamond_simple(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[X1:%.*]] = icmp eq i32 [[A:%.*]], 0
 ; CHECK-NEXT:    [[Z2:%.*]] = select i1 [[X1]], i32 [[B:%.*]], i32 0
 ; CHECK-NEXT:    [[X2:%.*]] = icmp eq i32 [[B]], 0
-; CHECK-NEXT:    [[Z4:%.*]] = select i1 [[X2]], i32 [[Z2]], i32 3
 ; CHECK-NEXT:    [[TMP0:%.*]] = or i32 [[A]], [[B]]
 ; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i32 [[TMP0]], 0
 ; CHECK-NEXT:    br i1 [[TMP1]], label [[TMP3:%.*]], label [[TMP2:%.*]]
 ; CHECK:       2:
 ; CHECK-NEXT:    [[SIMPLIFYCFG_MERGE:%.*]] = select i1 [[X2]], i32 [[Z2]], i32 1
 ; CHECK-NEXT:    store i32 [[SIMPLIFYCFG_MERGE]], i32* [[P:%.*]], align 4
 ; CHECK-NEXT:    br label [[TMP3]]
 ; CHECK:       3:
+; CHECK-NEXT:    [[Z4:%.*]] = select i1 [[X2]], i32 [[Z2]], i32 3
 ; CHECK-NEXT:    ret i32 [[Z4]]
 ;
 entry:
   %x1 = icmp eq i32 %a, 0
   br i1 %x1, label %no1, label %yes1
 
 yes1:
   store i32 0, i32* %p