[IR] Clean up dead instructions after simplifying a conditional branch

[foad]

Summary

Change BasicBlock::removePredecessor to optionally return a vector of
instructions which might be dead. Use this in ConstantFoldTerminator to
delete them if they are dead.

[jdoerfert]

llvm/lib/Transforms/Utils/Local.cpp

135

It seems unfortunate that we need to copy the vector. Do we believe there is another use case for MaybeDeadInstrs so we want it to take a Instruction vector?

[foad]

Like this? I had to include ValueHandle.h from BasicBlock.h. I don't know if that's acceptable.

[jdoerfert]

I find this better. It's opt-in and seems reasonable to me. @nhaehnle wdyt?

[nhaehnle]

This looks very reasonable to me.

llvm/lib/IR/BasicBlock.cpp

346–348

Nitpick: I think it's better to put braces around multi-line if-guarded statements.

[fhahn]

llvm/lib/Transforms/Utils/Local.cpp

107

Might be good to mention the change in behavior in the doc-comment (not sure why there's one here, should also be updated in the headeR)

476–477

Why change this to a dyn_cast? Looks like only Instructions are added in removePredecessor?

[foad]

llvm/lib/Transforms/Utils/Local.cpp

476–477

removePredecessor only adds Instructions, but then in some cases it will replaceAllUsesWith one of those Instructions with an arbitrary Value.

[fhahn]

llvm/lib/Transforms/Utils/Local.cpp

132

IIUC this function only deletes dead values if DeleteDeadConditions is true. Might be good to guard the new simplifications in a similar fashion.

476–477

Hm, it seems a bit unfortunate that we would add instructions that we immediately RAUW afterwards.

IIUC the only case where this would happen is where the incoming value for the removed predecessor is the original PN itself. Couldn't we simply not add the incoming instruction to DeadInsts? That seems like a cleaner solution and should be straight-forward.

[foad]

llvm/lib/Transforms/Utils/Local.cpp

132

Under the same flag or a different one? In any case my preference would be not to do this unless/until we really need it.

476–477

IIUC the only case where this would happen is where the incoming value for the removed predecessor is the original PN itself.

No, I think the problem occurs when we first visit PHI node A, one of whose inputs is PHI node B, which we add to MaybeDeadInstrs; and then we visit PHI node B and find that it hasConstantValue.

[fhahn]

llvm/lib/Transforms/Utils/Local.cpp

132

It would probably make sense to use the same flag. I assume there is a reason for making removing instructions conditional on an option (which defaults to false and some users set it to false). It seems like silently changing it to delete some other bits could trip over some existing users in obscure edge cases.

It might be that none of the users actually care of course. But in that case we should remove the flag altogether. In any case, I think the behavior should be documented.

476–477

Yeah that's another case, probably also possible to detect up-front. Anyways, it seems like we already allow non-instructions in DeadInsts in RecursivelyDeleteTriviallyDeadInstructions as well. Seems a bit odd to have something called DeadInsts containing non-instructions, but I guess that ship has sailed. Nevermind.

[uabelho]

Hi!

I wrote
https://bugs.llvm.org/show_bug.cgi?id=46343
about a crash that starts happening with this patch.

[jdoerfert]

In D80206#2095017, @uabelho wrote:

I wrote
https://bugs.llvm.org/show_bug.cgi?id=46343
about a crash that starts happening with this patch.

@foad, you look into this?

[foad]

In D80206#2096180, @jdoerfert wrote:

In D80206#2095017, @uabelho wrote:

I wrote
https://bugs.llvm.org/show_bug.cgi?id=46343
about a crash that starts happening with this patch.

@foad, you look into this?

I will. For the time being I reverted this commit in rG6fdd5a28b7840185d1f75d5702e7e2f3c4723b1c.

llvm/include/llvm/IR/BasicBlock.h

 #include "llvm/ADT/Twine.h"
 #include "llvm/ADT/ilist.h"
 #include "llvm/ADT/ilist_node.h"
 #include "llvm/ADT/iterator.h"
 #include "llvm/ADT/iterator_range.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/IR/SymbolTableListTraits.h"
 #include "llvm/IR/Value.h"
+#include "llvm/IR/ValueHandle.h"
 #include "llvm/Support/CBindingWrapping.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/Compiler.h"
 #include <cassert>
 #include <cstddef>
 #include <iterator>
 
 namespace llvm {
public:
   void dropAllReferences();
 
   /// Update PHI nodes in this BasicBlock before removal of predecessor \p Pred.
   /// Note that this function does not actually remove the predecessor.
   ///
   /// If \p KeepOneInputPHIs is true then don't remove PHIs that are left with
   /// zero or one incoming values, and don't simplify PHIs with all incoming
   /// values the same.
-  void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs = false);
+  ///
+  /// If \p MaybeDeadInstrs is not nullptr then whenever we drop a reference to
+  /// an instruction, append it to the vector. The caller should check whether
+  /// these instructions are now trivially dead, and if so delete them.
+  void
+  removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs = false,
+                    SmallVectorImpl<WeakTrackingVH> *MaybeDeadInstrs = nullptr);
 
   bool canSplitPredecessors() const;
 
   /// Split the basic block into two basic blocks at the specified instruction.
   ///
   /// Note that all instructions BEFORE the specified iterator stay as part of
   /// the original basic block, an unconditional branch is added to the original
   /// BB, and the rest of the instructions in the BB are moved to the new BB,

llvm/lib/IR/BasicBlock.cpp

 }
 
 /// Update PHI nodes in this BasicBlock before removal of predecessor \p Pred.
 /// Note that this function does not actually remove the predecessor.
 ///
 /// If \p KeepOneInputPHIs is true then don't remove PHIs that are left with
 /// zero or one incoming values, and don't simplify PHIs with all incoming
 /// values the same.
-void BasicBlock::removePredecessor(BasicBlock *Pred,
-                                   bool KeepOneInputPHIs) {
+///
+/// If \p MaybeDeadInstrs is not nullptr then whenever we drop a reference to
+/// an instruction, append it to the vector. The caller should check whether
+/// these instructions are now trivially dead, and if so delete them.
+void BasicBlock::removePredecessor(
+    BasicBlock *Pred, bool KeepOneInputPHIs,
+    SmallVectorImpl<WeakTrackingVH> *MaybeDeadInstrs) {
   // Use hasNUsesOrMore to bound the cost of this assertion for complex CFGs.
   assert((hasNUsesOrMore(16) ||
           find(pred_begin(this), pred_end(this), Pred) != pred_end(this)) &&
          "Pred is not a predecessor!");
 
   // Return early if there are no PHI nodes to update.
   if (!isa<PHINode>(begin()))
     return;
   unsigned NumPreds = cast<PHINode>(front()).getNumIncomingValues();
 
   // Update all PHI nodes.
   for (iterator II = begin(); isa<PHINode>(II);) {
     PHINode *PN = cast<PHINode>(II++);
-    PN->removeIncomingValue(Pred, !KeepOneInputPHIs);
+    Value *V = PN->removeIncomingValue(Pred);
+    if (MaybeDeadInstrs) {
+      if (auto *I = dyn_cast<Instruction>(V))
+        MaybeDeadInstrs->push_back(I);
+    }
     if (!KeepOneInputPHIs) {
       // If we have a single predecessor, removeIncomingValue erased the PHI
       // node itself.
       if (NumPreds > 1) {
         if (Value *PNV = PN->hasConstantValue()) {
           // Replace the PHI node with its constant value.
           PN->replaceAllUsesWith(PNV);
           PN->eraseFromParent();

llvm/lib/Transforms/Utils/Local.cpp

 //===----------------------------------------------------------------------===//
 //  Local constant propagation.
 //
 
 /// ConstantFoldTerminator - If a terminator instruction is predicated on a
 /// constant value, convert it into an unconditional branch to the constant
 /// destination.  This is a nontrivial operation because the successors of this
 /// basic block must have their PHI nodes updated.
 /// Also calls RecursivelyDeleteTriviallyDeadInstructions() on any branch/switch
 /// conditions and indirectbr addresses this might make dead if
 /// DeleteDeadConditions is true.
 bool llvm::ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions,
                                   const TargetLibraryInfo *TLI,
                                   DomTreeUpdater *DTU) {
   Instruction *T = BB->getTerminator();
   IRBuilder<> Builder(T);
 
   // Branch - See if we are conditional jumping on constant
   if (auto *BI = dyn_cast<BranchInst>(T)) {
     if (BI->isUnconditional()) return false;  // Can't optimize uncond branch
     BasicBlock *Dest1 = BI->getSuccessor(0);
     BasicBlock *Dest2 = BI->getSuccessor(1);
 
     if (auto *Cond = dyn_cast<ConstantInt>(BI->getCondition())) {
       // Are we branching on constant?
       // YES.  Change to unconditional branch...
       BasicBlock *Destination = Cond->getZExtValue() ? Dest1 : Dest2;
       BasicBlock *OldDest     = Cond->getZExtValue() ? Dest2 : Dest1;
 
       // Let the basic block know that we are letting go of it.  Based on this,
-      // it will adjust it's PHI nodes.
-      OldDest->removePredecessor(BB);
+      // it will adjust its PHI nodes.
+      SmallVector<WeakTrackingVH, 8> MaybeDeadInstrs;
+      OldDest->removePredecessor(BB, false, &MaybeDeadInstrs);
+      RecursivelyDeleteTriviallyDeadInstructionsPermissive(MaybeDeadInstrs,
+                                                           TLI);
 
       // Replace the conditional branch with an unconditional one.
       Builder.CreateBr(Destination);
       BI->eraseFromParent();
       if (DTU)
         DTU->applyUpdatesPermissive({{DominatorTree::Delete, BB, OldDest}});
       return true;
     }
 
     if (Dest2 == Dest1) {       // Conditional branch to same location?
bool llvm::RecursivelyDeleteTriviallyDeadInstructions(
   return true;
 }
 
 bool llvm::RecursivelyDeleteTriviallyDeadInstructionsPermissive(
     SmallVectorImpl<WeakTrackingVH> &DeadInsts, const TargetLibraryInfo *TLI,
     MemorySSAUpdater *MSSAU) {
   unsigned S = 0, E = DeadInsts.size(), Alive = 0;
   for (; S != E; ++S) {
-    auto *I = cast<Instruction>(DeadInsts[S]);
-    if (!isInstructionTriviallyDead(I)) {
+    auto *I = dyn_cast<Instruction>(DeadInsts[S]);
+    if (!I || !isInstructionTriviallyDead(I)) {
       DeadInsts[S] = nullptr;
       ++Alive;
     }
   }
   if (Alive == E)
     return false;
   RecursivelyDeleteTriviallyDeadInstructions(DeadInsts, TLI, MSSAU);
   return true;

llvm/test/Transforms/PGOProfile/chr.ll

 ; }
 ; return sum
 define i32 @test_chr_5(i32* %i, i32 %sum0) !prof !14 {
 ; CHECK-LABEL: @test_chr_5(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[TMP0:%.*]] = load i32, i32* [[I:%.*]], align 4
 ; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[TMP0]], 15
 ; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i32 [[TMP1]], 15
-; CHECK-NEXT:    br i1 [[TMP2]], label [[BB0:%.*]], label [[ENTRY_SPLIT_NONCHR:%.*]], !prof !15
-; CHECK:       bb0:
-; CHECK-NEXT:    [[TMP3:%.*]] = add i32 [[SUM0:%.*]], 85
-; CHECK-NEXT:    [[TMP4:%.*]] = add i32 [[SUM0]], 173
+; CHECK-NEXT:    br i1 [[TMP2]], label [[BB1:%.*]], label [[ENTRY_SPLIT_NONCHR:%.*]], !prof !15
+; CHECK:       bb1:
+; CHECK-NEXT:    [[TMP3:%.*]] = add i32 [[SUM0:%.*]], 173
 ; CHECK-NEXT:    br label [[BB3:%.*]]
 ; CHECK:       entry.split.nonchr:
-; CHECK-NEXT:    [[TMP5:%.*]] = and i32 [[TMP0]], 255
-; CHECK-NEXT:    [[TMP6:%.*]] = icmp eq i32 [[TMP5]], 0
-; CHECK-NEXT:    br i1 [[TMP6]], label [[BB3]], label [[BB0_NONCHR:%.*]], !prof !16
+; CHECK-NEXT:    [[TMP4:%.*]] = and i32 [[TMP0]], 255
+; CHECK-NEXT:    [[TMP5:%.*]] = icmp eq i32 [[TMP4]], 0
+; CHECK-NEXT:    br i1 [[TMP5]], label [[BB3]], label [[BB0_NONCHR:%.*]], !prof !16
 ; CHECK:       bb0.nonchr:
-; CHECK-NEXT:    [[TMP7:%.*]] = and i32 [[TMP0]], 1
-; CHECK-NEXT:    [[TMP8:%.*]] = icmp eq i32 [[TMP7]], 0
-; CHECK-NEXT:    [[TMP9:%.*]] = add i32 [[SUM0]], 42
-; CHECK-NEXT:    [[SUM1_NONCHR:%.*]] = select i1 [[TMP8]], i32 [[SUM0]], i32 [[TMP9]], !prof !16
-; CHECK-NEXT:    [[TMP10:%.*]] = and i32 [[TMP0]], 2
-; CHECK-NEXT:    [[TMP11:%.*]] = icmp eq i32 [[TMP10]], 0
-; CHECK-NEXT:    [[TMP12:%.*]] = add i32 [[SUM1_NONCHR]], 43
-; CHECK-NEXT:    [[SUM2_NONCHR:%.*]] = select i1 [[TMP11]], i32 [[SUM1_NONCHR]], i32 [[TMP12]], !prof !16
-; CHECK-NEXT:    [[TMP13:%.*]] = and i32 [[TMP0]], 4
-; CHECK-NEXT:    [[TMP14:%.*]] = icmp eq i32 [[TMP13]], 0
-; CHECK-NEXT:    [[TMP15:%.*]] = and i32 [[TMP0]], 8
-; CHECK-NEXT:    [[TMP16:%.*]] = icmp eq i32 [[TMP15]], 0
-; CHECK-NEXT:    [[SUM4_NONCHR_V:%.*]] = select i1 [[TMP16]], i32 44, i32 88
+; CHECK-NEXT:    [[TMP6:%.*]] = and i32 [[TMP0]], 1
+; CHECK-NEXT:    [[TMP7:%.*]] = icmp eq i32 [[TMP6]], 0
+; CHECK-NEXT:    [[TMP8:%.*]] = add i32 [[SUM0]], 42
+; CHECK-NEXT:    [[SUM1_NONCHR:%.*]] = select i1 [[TMP7]], i32 [[SUM0]], i32 [[TMP8]], !prof !16
+; CHECK-NEXT:    [[TMP9:%.*]] = and i32 [[TMP0]], 2
+; CHECK-NEXT:    [[TMP10:%.*]] = icmp eq i32 [[TMP9]], 0
+; CHECK-NEXT:    [[TMP11:%.*]] = add i32 [[SUM1_NONCHR]], 43
+; CHECK-NEXT:    [[SUM2_NONCHR:%.*]] = select i1 [[TMP10]], i32 [[SUM1_NONCHR]], i32 [[TMP11]], !prof !16
+; CHECK-NEXT:    [[TMP12:%.*]] = and i32 [[TMP0]], 4
+; CHECK-NEXT:    [[TMP13:%.*]] = icmp eq i32 [[TMP12]], 0
+; CHECK-NEXT:    [[TMP14:%.*]] = and i32 [[TMP0]], 8
+; CHECK-NEXT:    [[TMP15:%.*]] = icmp eq i32 [[TMP14]], 0
+; CHECK-NEXT:    [[SUM4_NONCHR_V:%.*]] = select i1 [[TMP15]], i32 44, i32 88
 ; CHECK-NEXT:    [[SUM4_NONCHR:%.*]] = add i32 [[SUM2_NONCHR]], [[SUM4_NONCHR_V]]
-; CHECK-NEXT:    [[SUM5_NONCHR:%.*]] = select i1 [[TMP14]], i32 [[SUM2_NONCHR]], i32 [[SUM4_NONCHR]], !prof !16
+; CHECK-NEXT:    [[SUM5_NONCHR:%.*]] = select i1 [[TMP13]], i32 [[SUM2_NONCHR]], i32 [[SUM4_NONCHR]], !prof !16
 ; CHECK-NEXT:    br label [[BB3]]
 ; CHECK:       bb3:
-; CHECK-NEXT:    [[SUM6:%.*]] = phi i32 [ [[TMP4]], [[BB0]] ], [ [[SUM0]], [[ENTRY_SPLIT_NONCHR]] ], [ [[SUM5_NONCHR]], [[BB0_NONCHR]] ]
+; CHECK-NEXT:    [[SUM6:%.*]] = phi i32 [ [[TMP3]], [[BB1]] ], [ [[SUM0]], [[ENTRY_SPLIT_NONCHR]] ], [ [[SUM5_NONCHR]], [[BB0_NONCHR]] ]
 ; CHECK-NEXT:    ret i32 [[SUM6]]
 ;
 entry:
   %0 = load i32, i32* %i
   %1 = and i32 %0, 255
   %2 = icmp eq i32 %1, 0
   br i1 %2, label %bb3, label %bb0, !prof !15
 

 ; CHECK-LABEL: @test_chr_5_1(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[TMP0:%.*]] = load i32, i32* [[I:%.*]], align 4
 ; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[SUM0:%.*]], 4
 ; CHECK-NEXT:    [[TMP2:%.*]] = icmp ne i32 [[TMP1]], 0
 ; CHECK-NEXT:    [[TMP3:%.*]] = and i32 [[TMP0]], 11
 ; CHECK-NEXT:    [[TMP4:%.*]] = icmp eq i32 [[TMP3]], 11
 ; CHECK-NEXT:    [[TMP5:%.*]] = and i1 [[TMP4]], [[TMP2]]
-; CHECK-NEXT:    br i1 [[TMP5]], label [[BB0:%.*]], label [[ENTRY_SPLIT_NONCHR:%.*]], !prof !15
-; CHECK:       bb0:
-; CHECK-NEXT:    [[TMP6:%.*]] = add i32 [[SUM0]], 85
-; CHECK-NEXT:    [[TMP7:%.*]] = add i32 [[SUM0]], 173
+; CHECK-NEXT:    br i1 [[TMP5]], label [[BB1:%.*]], label [[ENTRY_SPLIT_NONCHR:%.*]], !prof !15
+; CHECK:       bb1:
+; CHECK-NEXT:    [[TMP6:%.*]] = add i32 [[SUM0]], 173
 ; CHECK-NEXT:    br label [[BB3:%.*]]
 ; CHECK:       entry.split.nonchr:
-; CHECK-NEXT:    [[TMP8:%.*]] = and i32 [[TMP0]], 255
-; CHECK-NEXT:    [[TMP9:%.*]] = icmp eq i32 [[TMP8]], 0
-; CHECK-NEXT:    br i1 [[TMP9]], label [[BB3]], label [[BB0_NONCHR:%.*]], !prof !16
+; CHECK-NEXT:    [[TMP7:%.*]] = and i32 [[TMP0]], 255
+; CHECK-NEXT:    [[TMP8:%.*]] = icmp eq i32 [[TMP7]], 0
+; CHECK-NEXT:    br i1 [[TMP8]], label [[BB3]], label [[BB0_NONCHR:%.*]], !prof !16
 ; CHECK:       bb0.nonchr:
-; CHECK-NEXT:    [[TMP10:%.*]] = and i32 [[TMP0]], 1
-; CHECK-NEXT:    [[TMP11:%.*]] = icmp eq i32 [[TMP10]], 0
-; CHECK-NEXT:    [[TMP12:%.*]] = add i32 [[SUM0]], 42
-; CHECK-NEXT:    [[SUM1_NONCHR:%.*]] = select i1 [[TMP11]], i32 [[SUM0]], i32 [[TMP12]], !prof !16
-; CHECK-NEXT:    [[TMP13:%.*]] = and i32 [[TMP0]], 2
-; CHECK-NEXT:    [[TMP14:%.*]] = icmp eq i32 [[TMP13]], 0
-; CHECK-NEXT:    [[TMP15:%.*]] = add i32 [[SUM1_NONCHR]], 43
-; CHECK-NEXT:    [[SUM2_NONCHR:%.*]] = select i1 [[TMP14]], i32 [[SUM1_NONCHR]], i32 [[TMP15]], !prof !16
-; CHECK-NEXT:    [[TMP16:%.*]] = and i32 [[SUM0]], 4
-; CHECK-NEXT:    [[TMP17:%.*]] = icmp eq i32 [[TMP16]], 0
-; CHECK-NEXT:    [[TMP18:%.*]] = and i32 [[TMP0]], 8
-; CHECK-NEXT:    [[TMP19:%.*]] = icmp eq i32 [[TMP18]], 0
-; CHECK-NEXT:    [[SUM4_NONCHR_V:%.*]] = select i1 [[TMP19]], i32 44, i32 88
+; CHECK-NEXT:    [[TMP9:%.*]] = and i32 [[TMP0]], 1
+; CHECK-NEXT:    [[TMP10:%.*]] = icmp eq i32 [[TMP9]], 0
+; CHECK-NEXT:    [[TMP11:%.*]] = add i32 [[SUM0]], 42
+; CHECK-NEXT:    [[SUM1_NONCHR:%.*]] = select i1 [[TMP10]], i32 [[SUM0]], i32 [[TMP11]], !prof !16
+; CHECK-NEXT:    [[TMP12:%.*]] = and i32 [[TMP0]], 2
+; CHECK-NEXT:    [[TMP13:%.*]] = icmp eq i32 [[TMP12]], 0
+; CHECK-NEXT:    [[TMP14:%.*]] = add i32 [[SUM1_NONCHR]], 43
+; CHECK-NEXT:    [[SUM2_NONCHR:%.*]] = select i1 [[TMP13]], i32 [[SUM1_NONCHR]], i32 [[TMP14]], !prof !16
+; CHECK-NEXT:    [[TMP15:%.*]] = and i32 [[SUM0]], 4
+; CHECK-NEXT:    [[TMP16:%.*]] = icmp eq i32 [[TMP15]], 0
+; CHECK-NEXT:    [[TMP17:%.*]] = and i32 [[TMP0]], 8
+; CHECK-NEXT:    [[TMP18:%.*]] = icmp eq i32 [[TMP17]], 0
+; CHECK-NEXT:    [[SUM4_NONCHR_V:%.*]] = select i1 [[TMP18]], i32 44, i32 88
 ; CHECK-NEXT:    [[SUM4_NONCHR:%.*]] = add i32 [[SUM2_NONCHR]], [[SUM4_NONCHR_V]]
-; CHECK-NEXT:    [[SUM5_NONCHR:%.*]] = select i1 [[TMP17]], i32 [[SUM2_NONCHR]], i32 [[SUM4_NONCHR]], !prof !16
+; CHECK-NEXT:    [[SUM5_NONCHR:%.*]] = select i1 [[TMP16]], i32 [[SUM2_NONCHR]], i32 [[SUM4_NONCHR]], !prof !16
 ; CHECK-NEXT:    br label [[BB3]]
 ; CHECK:       bb3:
-; CHECK-NEXT:    [[SUM6:%.*]] = phi i32 [ [[TMP7]], [[BB0]] ], [ [[SUM0]], [[ENTRY_SPLIT_NONCHR]] ], [ [[SUM5_NONCHR]], [[BB0_NONCHR]] ]
+; CHECK-NEXT:    [[SUM6:%.*]] = phi i32 [ [[TMP6]], [[BB1]] ], [ [[SUM0]], [[ENTRY_SPLIT_NONCHR]] ], [ [[SUM5_NONCHR]], [[BB0_NONCHR]] ]
 ; CHECK-NEXT:    ret i32 [[SUM6]]
 ;
 entry:
   %0 = load i32, i32* %i
   %1 = and i32 %0, 255
   %2 = icmp eq i32 %1, 0
   br i1 %2, label %bb3, label %bb0, !prof !15
 

 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[I0:%.*]] = load i32, i32* [[I:%.*]], align 4
 ; CHECK-NEXT:    [[J0:%.*]] = load i32, i32* [[J:%.*]], align 4
 ; CHECK-NEXT:    [[V9:%.*]] = and i32 [[J0]], 4
 ; CHECK-NEXT:    [[V10:%.*]] = icmp ne i32 [[V9]], 0
 ; CHECK-NEXT:    [[TMP0:%.*]] = and i32 [[I0]], 10
 ; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i32 [[TMP0]], 10
 ; CHECK-NEXT:    [[TMP2:%.*]] = and i1 [[TMP1]], [[V10]]
-; CHECK-NEXT:    br i1 [[TMP2]], label [[BB0:%.*]], label [[ENTRY_SPLIT_NONCHR:%.*]], !prof !15
-; CHECK:       bb0:
-; CHECK-NEXT:    [[V8:%.*]] = add i32 [[SUM0:%.*]], 43
-; CHECK-NEXT:    [[V13:%.*]] = add i32 [[SUM0]], 131
+; CHECK-NEXT:    br i1 [[TMP2]], label [[BB1:%.*]], label [[ENTRY_SPLIT_NONCHR:%.*]], !prof !15
+; CHECK:       bb1:
+; CHECK-NEXT:    [[V13:%.*]] = add i32 [[SUM0:%.*]], 131
 ; CHECK-NEXT:    br label [[BB3:%.*]]
 ; CHECK:       entry.split.nonchr:
 ; CHECK-NEXT:    [[V1:%.*]] = and i32 [[I0]], 255
 ; CHECK-NEXT:    [[V2:%.*]] = icmp eq i32 [[V1]], 0
 ; CHECK-NEXT:    br i1 [[V2]], label [[BB3]], label [[BB0_NONCHR:%.*]], !prof !16
 ; CHECK:       bb0.nonchr:
 ; CHECK-NEXT:    [[V3_NONCHR:%.*]] = and i32 [[I0]], 2
 ; CHECK-NEXT:    [[V4_NONCHR:%.*]] = icmp eq i32 [[V3_NONCHR]], 0
 ; CHECK-NEXT:    [[V8_NONCHR:%.*]] = add i32 [[SUM0]], 43
 ; CHECK-NEXT:    [[SUM2_NONCHR:%.*]] = select i1 [[V4_NONCHR]], i32 [[SUM0]], i32 [[V8_NONCHR]], !prof !16
 ; CHECK-NEXT:    [[V9_NONCHR:%.*]] = and i32 [[J0]], 4
 ; CHECK-NEXT:    [[V10_NONCHR:%.*]] = icmp eq i32 [[V9_NONCHR]], 0
 ; CHECK-NEXT:    [[V11_NONCHR:%.*]] = and i32 [[I0]], 8
 ; CHECK-NEXT:    [[V12_NONCHR:%.*]] = icmp eq i32 [[V11_NONCHR]], 0
 ; CHECK-NEXT:    [[SUM4_NONCHR_V:%.*]] = select i1 [[V12_NONCHR]], i32 44, i32 88
 ; CHECK-NEXT:    [[SUM4_NONCHR:%.*]] = add i32 [[SUM2_NONCHR]], [[SUM4_NONCHR_V]]
 ; CHECK-NEXT:    [[SUM5_NONCHR:%.*]] = select i1 [[V10_NONCHR]], i32 [[SUM2_NONCHR]], i32 [[SUM4_NONCHR]], !prof !16
 ; CHECK-NEXT:    br label [[BB3]]
 ; CHECK:       bb3:
-; CHECK-NEXT:    [[SUM6:%.*]] = phi i32 [ [[V13]], [[BB0]] ], [ [[SUM0]], [[ENTRY_SPLIT_NONCHR]] ], [ [[SUM5_NONCHR]], [[BB0_NONCHR]] ]
+; CHECK-NEXT:    [[SUM6:%.*]] = phi i32 [ [[V13]], [[BB1]] ], [ [[SUM0]], [[ENTRY_SPLIT_NONCHR]] ], [ [[SUM5_NONCHR]], [[BB0_NONCHR]] ]
 ; CHECK-NEXT:    ret i32 [[SUM6]]
 ;
 entry:
   %i0 = load i32, i32* %i
   %j0 = load i32, i32* %j
   %v1 = and i32 %i0, 255
   %v2 = icmp eq i32 %v1, 0
   br i1 %v2, label %bb3, label %bb0, !prof !15

 ; sum6 = phi tmp4, sum0, sum2_nc, sum4_nc
 ; return sum6
 define i32 @test_chr_19(i32* %i, i32 %sum0) !prof !14 {
 ; CHECK-LABEL: @test_chr_19(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[TMP0:%.*]] = load i32, i32* [[I:%.*]], align 4
 ; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[TMP0]], 9
 ; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i32 [[TMP1]], 9
-; CHECK-NEXT:    br i1 [[TMP2]], label [[BB0:%.*]], label [[ENTRY_SPLIT_NONCHR:%.*]], !prof !15
-; CHECK:       bb0:
-; CHECK-NEXT:    [[TMP3:%.*]] = add i32 [[SUM0:%.*]], 85
-; CHECK-NEXT:    [[TMP4:%.*]] = add i32 [[SUM0]], 173
+; CHECK-NEXT:    br i1 [[TMP2]], label [[BB1:%.*]], label [[ENTRY_SPLIT_NONCHR:%.*]], !prof !15
+; CHECK:       bb1:
+; CHECK-NEXT:    [[TMP3:%.*]] = add i32 [[SUM0:%.*]], 173
 ; CHECK-NEXT:    br label [[BB3:%.*]]
 ; CHECK:       entry.split.nonchr:
-; CHECK-NEXT:    [[TMP5:%.*]] = and i32 [[TMP0]], 255
-; CHECK-NEXT:    [[TMP6:%.*]] = icmp eq i32 [[TMP5]], 0
-; CHECK-NEXT:    br i1 [[TMP6]], label [[BB3]], label [[BB0_NONCHR:%.*]], !prof !16
+; CHECK-NEXT:    [[TMP4:%.*]] = and i32 [[TMP0]], 255
+; CHECK-NEXT:    [[TMP5:%.*]] = icmp eq i32 [[TMP4]], 0
+; CHECK-NEXT:    br i1 [[TMP5]], label [[BB3]], label [[BB0_NONCHR:%.*]], !prof !16
 ; CHECK:       bb0.nonchr:
-; CHECK-NEXT:    [[TMP7:%.*]] = and i32 [[TMP0]], 1
-; CHECK-NEXT:    [[TMP8:%.*]] = icmp eq i32 [[TMP7]], 0
-; CHECK-NEXT:    [[TMP9:%.*]] = add i32 [[SUM0]], 85
-; CHECK-NEXT:    [[SUM2_NONCHR:%.*]] = select i1 [[TMP8]], i32 [[SUM0]], i32 [[TMP9]], !prof !16
-; CHECK-NEXT:    [[TMP10:%.*]] = and i32 [[TMP0]], 8
-; CHECK-NEXT:    [[TMP11:%.*]] = icmp eq i32 [[TMP10]], 0
-; CHECK-NEXT:    [[SUM4_NONCHR_V:%.*]] = select i1 [[TMP11]], i32 44, i32 88
+; CHECK-NEXT:    [[TMP6:%.*]] = and i32 [[TMP0]], 1
+; CHECK-NEXT:    [[TMP7:%.*]] = icmp eq i32 [[TMP6]], 0
+; CHECK-NEXT:    [[TMP8:%.*]] = add i32 [[SUM0]], 85
+; CHECK-NEXT:    [[SUM2_NONCHR:%.*]] = select i1 [[TMP7]], i32 [[SUM0]], i32 [[TMP8]], !prof !16
+; CHECK-NEXT:    [[TMP9:%.*]] = and i32 [[TMP0]], 8
+; CHECK-NEXT:    [[TMP10:%.*]] = icmp eq i32 [[TMP9]], 0
+; CHECK-NEXT:    [[SUM4_NONCHR_V:%.*]] = select i1 [[TMP10]], i32 44, i32 88
 ; CHECK-NEXT:    [[SUM4_NONCHR:%.*]] = add i32 [[SUM2_NONCHR]], [[SUM4_NONCHR_V]]
-; CHECK-NEXT:    [[SUM5_NONCHR:%.*]] = select i1 [[TMP8]], i32 [[SUM2_NONCHR]], i32 [[SUM4_NONCHR]], !prof !16
+; CHECK-NEXT:    [[SUM5_NONCHR:%.*]] = select i1 [[TMP7]], i32 [[SUM2_NONCHR]], i32 [[SUM4_NONCHR]], !prof !16
 ; CHECK-NEXT:    br label [[BB3]]
 ; CHECK:       bb3:
-; CHECK-NEXT:    [[SUM6:%.*]] = phi i32 [ [[TMP4]], [[BB0]] ], [ [[SUM0]], [[ENTRY_SPLIT_NONCHR]] ], [ [[SUM5_NONCHR]], [[BB0_NONCHR]] ]
+; CHECK-NEXT:    [[SUM6:%.*]] = phi i32 [ [[TMP3]], [[BB1]] ], [ [[SUM0]], [[ENTRY_SPLIT_NONCHR]] ], [ [[SUM5_NONCHR]], [[BB0_NONCHR]] ]
 ; CHECK-NEXT:    ret i32 [[SUM6]]
 ;
 entry:
   %0 = load i32, i32* %i
   %1 = and i32 %0, 255
   %2 = icmp eq i32 %1, 0
   br i1 %2, label %bb3, label %bb0, !prof !15