[JumpThreading] Replace MergeBasicBlockIntoOnlyPred() with MergeBlockIntoPredecessor()

[brzycki]

Summary

In D48202 the helper function MergeBasicBlockIntoOnlyPred() was removed from llvm with the exception of JumpThreading. @asbirlea asked me to look at it for this final case. This patch replaces the last remaining usage of MergeBasicBlockIntoOnlyPred() with MergeBlockIntoPredecessor(). (I didn't fully remove the function and its test cases. I consider that work for a separate patch.)

This is a bit more complex than a simple function replacement for the following reasons:

1. MergeBlockIntoPredecessor() may return false and not perform the merge while MergeBasicBlockIntoOnlyPred() always performed the action.
2. The checks in MergeBlockIntoPredecessor() are slightly different.
3. MergeBlockIntoPredecessor() does block hoisting. This was by far the biggest change and caused several re-labeling of blocks in test cases.
4. In a few test cases the hoisting prevented existing checks from detecting trivially dead code from the existing logic in ProcessBlock.
5. A bug in MergeBlockIntoPredecessor() causing DTU asserts, fixed with D58444.

Passes make-check on x86_64, test-suite on x86_64. I see nominal gains of a few percent overall on compile_time in test-suite and test-suite with CTmark. The benchmark execution times are on par, indicating this change (should be) a no-op for emitted IR.

Note: This diff relies on D58444 being comitted first. Without it test-suite benchmarks cause compiler asserts.

Finally, there is one instance in the test cases, lvi-after-jumpthreading.ll where hoisting causes the loss of valuable LVI information. There is no API to inform LVI two blocks have been merged other than deleting the merged block and (potentially) deleting the block that was merged into. It would be nice to have an LVI API similar to LVI->threadEdge(...) to prevent such metadata loss. Ideally it'd be a parameter to MergeBlockIntoPredecessor().

[asbirlea]

Thank you for working on this!
I can only comment on the changes in the testcases which looks exactly as expected considering the blocks now being merge in the other direction.

I will default the approval to someone familiar with JumpThreading.

[brzycki]

Bump. Reviews or feedback would be appreciated.

[brzycki]

Rebase patchset to tip.

[brzycki]

Rebase to tip. Reviews or comments are very much appreciated.

[asbirlea]

LGTM.

[brzycki]

Thank you @asbirlea for the review. I'll rebase, verify everything looks ok, and commit. Hopefully in the next 7-10 days based on my current work load.

[brzycki]

I must abandon this revision as my current employer has not authorized me to contribute to LLVM.

llvm/lib/Transforms/Scalar/JumpThreading.cpp

bool JumpThreadingPass::runImpl(Function &F, TargetLibraryInfo *TLI_,
 
   FindLoopHeaders(F);
 
   bool EverChanged = false;
   bool Changed;
   do {
     Changed = false;
     for (auto &BB : F) {
-      if (Unreachable.count(&BB))
+      if (Unreachable.count(&BB) || DTU->isBBPendingDeletion(&BB))
         continue;
       while (ProcessBlock(&BB)) // Thread all of the branches we can over BB.
         Changed = true;
       // Stop processing BB if it's the entry or is now deleted. The following
       // routines attempt to eliminate BB and locating a suitable replacement
       // for the entry is non-trivial.
       if (&BB == &F.getEntryBlock() || DTU->isBBPendingDeletion(&BB))
         continue;
if (NumPreds < MinNumPreds) {
       MinSucc = i;
       MinNumPreds = NumPreds;
     }
   }
 
   return MinSucc;
 }
 
-static bool hasAddressTakenAndUsed(BasicBlock *BB) {
-  if (!BB->hasAddressTaken()) return false;
-
-  // If the block has its address taken, it may be a tree of dead constants
-  // hanging off of it.  These shouldn't keep the block alive.
-  BlockAddress *BA = BlockAddress::get(BB);
-  BA->removeDeadConstantUsers();
-  return !BA->use_empty();
-}
-
 /// ProcessBlock - If there are any predecessors whose control can be threaded
 /// through to a successor, transform them now.
 bool JumpThreadingPass::ProcessBlock(BasicBlock *BB) {
   // If the block is trivially dead, just return and let the caller nuke it.
   // This simplifies other transformations.
   if (DTU->isBBPendingDeletion(BB) ||
       (pred_empty(BB) && BB != &BB->getParent()->getEntryBlock()))
     return false;
 
   // If this block has a single predecessor, and if that pred has a single
   // successor, merge the blocks.  This encourages recursive jump threading
   // because now the condition in this block can be threaded through
   // predecessors of our predecessor block.
   if (BasicBlock *SinglePred = BB->getSinglePredecessor()) {
     const Instruction *TI = SinglePred->getTerminator();
-    if (!TI->isExceptionalTerminator() && TI->getNumSuccessors() == 1 &&
-        SinglePred != BB && !hasAddressTakenAndUsed(BB)) {
-      // If SinglePred was a loop header, BB becomes one.
-      if (LoopHeaders.erase(SinglePred))
-        LoopHeaders.insert(BB);
-
+    if (!TI->isExceptionalTerminator() && TI->getNumSuccessors() == 1) {
+      if (pred_empty(SinglePred) &&
+          SinglePred != &SinglePred->getParent()->getEntryBlock()) {
+        // We have the following IR shape where SinglePred isn't the entry BB:
+        //   SinglePred:       ; No predecessors!
+        //     ...
+        //     br label %BB
+        //   BB:               ; preds = %SinglePred
+        //     ...
+        //     br label %BB2
+        // Don't bother merging these blocks. SinglePred and BB are dead code
+        // and need to be deleted.
+        LoopHeaders.erase(SinglePred);
         LVI->eraseBlock(SinglePred);
-      MergeBasicBlockIntoOnlyPred(BB, DTU);
+        DeleteDeadBlock(SinglePred, DTU);
+        LoopHeaders.erase(BB);
+        LVI->eraseBlock(BB);
+        DeleteDeadBlock(BB, DTU);
+        return true;
+      }
 
-      // Now that BB is merged into SinglePred (i.e. SinglePred Code followed by
-      // BB code within one basic block `BB`), we need to invalidate the LVI
-      // information associated with BB, because the LVI information need not be
-      // true for all of BB after the merge. For example,
-      // Before the merge, LVI info and code is as follows:
-      // SinglePred: <LVI info1 for %p val>
-      // %y = use of %p
-      // call @exit() // need not transfer execution to successor.
-      // assume(%p) // from this point on %p is true
-      // br label %BB
-      // BB: <LVI info2 for %p val, i.e. %p is true>
-      // %x = use of %p
-      // br label exit
-      //
-      // Note that this LVI info for blocks BB and SinglPred is correct for %p
-      // (info2 and info1 respectively). After the merge and the deletion of the
-      // LVI info1 for SinglePred. We have the following code:
-      // BB: <LVI info2 for %p val>
-      // %y = use of %p
-      // call @exit()
-      // assume(%p)
-      // %x = use of %p <-- LVI info2 is correct from here onwards.
-      // br label exit
-      // LVI info2 for BB is incorrect at the beginning of BB.
-
-      // Invalidate LVI information for BB if the LVI is not provably true for
-      // all of BB.
-      if (!isGuaranteedToTransferExecutionToSuccessor(BB))
-        LVI->eraseBlock(BB);
+      if (BB->hasAddressTaken()) {
+        // If BB only has dead constant users its address isn't really taken.
+        // Eliminate them before the merge attempt of BB into SinglePred.
+        BlockAddress *BA = BlockAddress::get(BB);
+        BA->removeDeadConstantUsers();
+      }
+
+      if (MergeBlockIntoPredecessor(BB, DTU)) {
+        // NOTE: BB is still valid when DTU uses the Lazy update strategy.
+        // In Lazy mode BB isn't really deleted until the DTU class is issued
+        // a flush() event.
+
+        // If BB was a loop header, SinglePred becomes one.
+        if (LoopHeaders.erase(BB))
+          LoopHeaders.insert(SinglePred);
+
+        // Invalidate LVI for BB: the block has been merged into SinglePred.
+        LVI->eraseBlock(BB);
+
+        // The LVI metadata associated with the newly merged SinglePred may not
+        // be valid in cases where execution is not guaranteed to follow to all
+        // successors in the new SinglePred.  For example:
+        //   SinglePred:       ; LVI_SinglePred for value %p
+        //     %y = use of %p
+        //     ...
+        //     br label %BB
+        //   BB:               ; LVI_BB for value %p
+        //     ...
+        //     call @exit()    ; May not transfer execution to successor.
+        //     %x = use of %p
+        // This merges into:
+        //   SinglePred:       ; LVI_SinglePred for value %p
+        //     %y = use of %p
+        //     ...
+        //     call @exit()    ; May not transfer execution to successor.
+        //     %x = use of %p
+        // The LVI_SinglePred data is no longer sufficient for value %p.
+        if (!isGuaranteedToTransferExecutionToSuccessor(SinglePred))
+          LVI->eraseBlock(SinglePred);
+
         return true;
       }
     }
+  }
 
   if (TryToUnfoldSelectInCurrBB(BB))
     return true;
 
   // Look if we can propagate guards to predecessors.
   if (HasGuards && ProcessGuards(BB))
     return true;
 

llvm/test/Analysis/LazyValueAnalysis/lvi-after-jumpthreading.ll

 define i8 @test1(i32 %a, i32 %length) {
 ; CHECK-LABEL: LVI for function 'test1':
 entry:
 ; CHECK-LABEL: entry:
 ; CHECK-NEXT:    ; LatticeVal for: 'i32 %a' is: overdefined
 ; CHECK-NEXT:    ; LatticeVal for: 'i32 %length' is: overdefined
   br label %loop
 
-; CHECK-LABEL: backedge:
+; CHECK-LABEL: loop:
 ; CHECK-NEXT:     ; LatticeVal for: 'i32 %a' is: overdefined
 ; CHECK-NEXT:     ; LatticeVal for: 'i32 %length' is: overdefined
-; CHECK-NEXT:     ; LatticeVal for: '  %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]' in BB: '%backedge' is: constantrange<0, 400>
-; CHECK-NEXT:     ; LatticeVal for: '  %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]' in BB: '%exit' is: constantrange<399, 400>
-; CHECK-NEXT:  %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]
-; CHECK-NEXT:     ; LatticeVal for: '  %iv.next = add nsw i32 %iv, 1' in BB: '%backedge' is: constantrange<1, 401>
+; CHECK-NEXT:     ; LatticeVal for: '  %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop ]' in BB: '%loop' is: constantrange<-2147483648, 400>
+; CHECK-NEXT:     ; LatticeVal for: '  %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop ]' in BB: '%exit' is: constantrange<399, 400>
+; CHECK-NEXT:  %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop ]
+; CHECK-NEXT:     ; LatticeVal for: '  %iv.next = add nsw i32 %iv, 1' in BB: '%loop' is: constantrange<-2147483647, 401>
 ; CHECK-NEXT:     ; LatticeVal for: '  %iv.next = add nsw i32 %iv, 1' in BB: '%exit' is: constantrange<400, 401>
 ; CHECK-NEXT:  %iv.next = add nsw i32 %iv, 1
-; CHECK-NEXT:     ; LatticeVal for: '  %cont = icmp slt i32 %iv.next, 400' in BB: '%backedge' is: overdefined
+; CHECK-NEXT:     ; LatticeVal for: '  %cont = icmp slt i32 %iv.next, 400' in BB: '%loop' is: overdefined
 ; CHECK-NEXT:     ; LatticeVal for: '  %cont = icmp slt i32 %iv.next, 400' in BB: '%exit' is: constantrange<0, -1>
 ; CHECK-NEXT:  %cont = icmp slt i32 %iv.next, 400
-; CHECK-NOT: loop
+; CHECK-NOT: backedge
 loop:
   %iv = phi i32 [0, %entry], [%iv.next, %backedge]
   %cnd = icmp sge i32 %iv, 0
   br i1 %cnd, label %backedge, label %exit
 
 backedge:
   %iv.next = add nsw i32 %iv, 1
   %cont = icmp slt i32 %iv.next, 400

 ; Merging cont block into do block. Make sure that we do not incorrectly have the cont
 ; LVI info as LVI info for the beginning of do block. LVI info for %i is Range[0,1)
 ; at beginning of cont Block, which is incorrect at the beginning of do block.
 define i32 @test3(i32 %i, i1 %f, i32 %n) {
 ; CHECK-LABEL: LVI for function 'test3':
 ; CHECK-LABEL: entry
 ; CHECK:  ; LatticeVal for: 'i32 %i' is: overdefined
 ; CHECK: %c = icmp ne i32 %i, -2134 
-; CHECK: br i1 %c, label %cont, label %exit
+; CHECK: br i1 %c, label %do, label %exit
 entry:
   %c = icmp ne i32 %i, -2134
   br i1 %c, label %do, label %exit
 
 exit:
   %c1 = icmp ne i32 %i, -42
   br i1 %c1, label %exit2, label %exit
 
-; CHECK-LABEL: cont:
+; CHECK-LABEL: do:
 ; Here cont is merged to do and i is any value except -2134.
 ; i is not the single value: zero.
 ; CHECK-NOT:  ; LatticeVal for: 'i32 %i' is: constantrange<0, 1>
 ; CHECK:      ; LatticeVal for: 'i32 %i' is: constantrange<-2133, -2134>
-; CHECK:      ; LatticeVal for: '  %cond.0 = icmp sgt i32 %i, 0' in BB: '%cont' is: overdefined
+; CHECK:      ; LatticeVal for: '  %cond.0 = icmp sgt i32 %i, 0' in BB: '%do' is: overdefined
 ; CHECK:   %cond.0 = icmp sgt i32 %i, 0
 ; CHECK:   %consume = call i32 @consume
 ; CHECK:   %cond = icmp eq i32 %i, 0
 ; CHECK:   call void (i1, ...) @llvm.experimental.guard(i1 %cond)
 ; CHECK:   %cond.3 = icmp sgt i32 %i, %n
 ; CHECK:   br i1 %cond.3, label %exit2, label %exit
 cont:
   %cond.3 = icmp sgt i32 %i, %n

llvm/test/Transforms/CallSiteSplitting/callsite-split.ll

 ; RUN: opt < %s -callsite-splitting -inline -instcombine -jump-threading -S | FileCheck %s
 ; RUN: opt < %s  -passes='function(callsite-splitting),cgscc(inline),function(instcombine,jump-threading)' -S | FileCheck %s
 
 target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128"
 target triple = "aarch64-linaro-linux-gnueabi"
 
 %struct.bitmap = type { i32, %struct.bitmap* }
 
 ;CHECK-LABEL: @caller
 ;CHECK-LABEL: Top.split:
 ;CHECK: call void @callee(%struct.bitmap* null, %struct.bitmap* null, %struct.bitmap* %b_elt, i1 false)
 ;CHECK-LABEL: NextCond:
-;CHECK: br {{.*}} label %callee.exit
-;CHECK-LABEL: callee.exit:
+;CHECK: br {{.*}} label %Cond.i
+;CHECK-LABEL: Cond.i:
 ;CHECK: call void @dummy2(%struct.bitmap* %a_elt)
 
 define void @caller(i1 %c, %struct.bitmap* %a_elt, %struct.bitmap* %b_elt) {
 entry:
   br label %Top
 
 Top:
   %tobool1 = icmp eq %struct.bitmap* %a_elt, null

llvm/test/Transforms/JumpThreading/PR33357-lvi-recursion.ll

 ; RUN: opt -S -jump-threading -verify -o - %s | FileCheck %s
 @a = external global i16, align 1
 
 ; CHECK-LABEL: f
-; CHECK: bb6:
-; CHECK: bb2:
+; CHECK: bb0:
 ; CHECK: bb3:
-; CHECK-NOT: bb0:
+; CHECK: bb4:
 ; CHECK-NOT: bb1:
-; CHECK-NOT: bb4:
+; CHECK-NOT: bb2:
 ; CHECK-NOT: bb5:
+; CHECK-NOT: bb6:
 define void @f(i32 %p1) {
 bb0:
   %0 = icmp eq i32 %p1, 0
   br i1 undef, label %bb6, label %bb1
 
 bb1:
   br label %bb2
 

llvm/test/Transforms/JumpThreading/and-and-cond.ll

 ; RUN: opt < %s -jump-threading -mem2reg -instcombine -simplifycfg  -S | FileCheck %s
 
 declare i32 @f1()
 declare i32 @f2()
 declare void @f3()
 
 define i32 @test(i1 %cond, i1 %cond2, i1 %cond3) {
 ; CHECK: test
   br i1 %cond, label %T1, label %F1
 
-; CHECK-NOT: T1:
 T1:
+; CHECK: T1:
+; CHECK: %v1 = call i32 @f1()
+; CHECK-NEXT: %D = and i1 %cond2, %cond3
+; CHECK-NEXT: br i1 %D
   %v1 = call i32 @f1()
   br label %Merge
 
+; CHECK-NOT: Merge:
+
 F1:
   %v2 = call i32 @f2()
   br label %Merge
 
 Merge:
-; CHECK: Merge:
-; CHECK: %v1 = call i32 @f1()
-; CHECK-NEXT: %D = and i1 %cond2, %cond3
-; CHECK-NEXT: br i1 %D
   %A = phi i1 [true, %T1], [false, %F1]
   %B = phi i32 [%v1, %T1], [%v2, %F1]
   %C = and i1 %A, %cond2
   %D = and i1 %C, %cond3
   br i1 %D, label %T2, label %F2
 
 T2:
   call void @f3()
   ret i32 %B
 
 F2:
   ret i32 %B
 }

llvm/test/Transforms/JumpThreading/and-cond.ll

 ; RUN: opt < %s -jump-threading -mem2reg -instcombine -simplifycfg  -S | FileCheck %s
 
 declare i32 @f1()
 declare i32 @f2()
 declare void @f3()
 
 define i32 @test(i1 %cond, i1 %cond2) {
 ; CHECK: test
   br i1 %cond, label %T1, label %F1
 
-; CHECK-NOT: T1
 T1:
+; CHECK: T1:
+; CHECK: %v1 = call i32 @f1()
+; CHECK-NEXT: br i1 %cond2
   %v1 = call i32 @f1()
   br label %Merge
 
+; CHECK-NOT: Merge
+
 F1:
   %v2 = call i32 @f2()
   br label %Merge
 
 Merge:
-; CHECK: Merge:
-; CHECK: %v1 = call i32 @f1()
-; CHECK-NEXT: br i1 %cond2
   %A = phi i1 [true, %T1], [false, %F1]
   %B = phi i32 [%v1, %T1], [%v2, %F1]
   %C = and i1 %A, %cond2
   br i1 %C, label %T2, label %F2
 
 T2:
   call void @f3()
   ret i32 %B
 
 F2:
   ret i32 %B
 }

llvm/test/Transforms/JumpThreading/assume-edge-dom.ll

 ; RUN: opt -S -jump-threading < %s | FileCheck %s
 
 declare i8* @escape()
 declare void @llvm.assume(i1)
 
 define i1 @test1(i1 %cond) {
 entry:
     br i1 %cond, label %taken, label %not_taken
 
 ; CHECK-LABEL: @test1
-; CHECK: br i1 %cond, label %no, label %yes
+; CHECK: br i1 %cond, label %taken, label %not_taken
 ; CHECK: ret i1 true
 
 taken:
     %res1 = call i8* @escape()
     %a = icmp eq i8* %res1, null
     tail call void @llvm.assume(i1 %a)
     br label %done
 not_taken:

llvm/test/Transforms/JumpThreading/basic.ll

F1:
   br label %Merge
 
 Merge:
   %A = phi i1 [true, %T1], [false, %F1]
   %B = phi i32 [%v1, %T1], [%v2, %F1]
   br i1 %A, label %T2, label %F2
 
 T2:
-; CHECK: T2:
+; CHECK: T1:
 ; CHECK: ret i32 %v1
   call void @f3()
   ret i32 %B
 
 F2:
-; CHECK: F2:
+; CHECK: F1:
 ; CHECK: ret i32 %v2
   ret i32 %B
 }
 
 
 ;; cond is known false on Entry -> F1 edge!
 define i32 @test2(i1 %cond) {
 ; CHECK-LABEL: @test2(

 ;; Lexically duplicated conditionals should be threaded.
 
 
 define i32 @test6(i32 %A) {
 ; CHECK-LABEL: @test6(
   %tmp455 = icmp eq i32 %A, 42
   br i1 %tmp455, label %BB1, label %BB2
 
-; CHECK: call i32 @f2()
-; CHECK-NEXT: ret i32 3
-
 ; CHECK: call i32 @f1()
 ; CHECK-NOT: br
 ; CHECK: call void @f3()
 ; CHECK-NOT: br
 ; CHECK: ret i32 4
 
+; CHECK: call i32 @f2()
+; CHECK-NEXT: ret i32 3
+
 BB2:
   call i32 @f1()
   br label %BB1
 
 
 BB1:
   %tmp459 = icmp eq i32 %A, 42
   br i1 %tmp459, label %BB3, label %BB4

 
 Merge:
   %B = phi i32 [%v1, %Entry], [%v2, %F1]
         %M = icmp ne i32 %B, %v1
         %N = icmp eq i32 %B, 47
         %O = and i1 %M, %N
   br i1 %O, label %T2, label %F2
 
-; CHECK: Merge:
+; CHECK: F1:
 ; CHECK-NOT: phi
 ; CHECK-NEXT:   %v2 = call i32 @f2()
 
 T2:
   call void @f3()
   ret i32 %B
 
 F2:
   ret i32 %B
 ; CHECK: F2:
 ; CHECK-NEXT: phi i32
 }
 
 
 declare i1 @test8a()
 
 define i32 @test8b(i1 %cond, i1 %cond2) {
 ; CHECK-LABEL: @test8b(
 T0:
         %A = call i1 @test8a()
   br i1 %A, label %T1, label %F1
 
 ; CHECK: T0:
 ; CHECK-NEXT: call
-; CHECK-NEXT: br i1 %A, label %T1, label %Y
+; CHECK-NEXT: br i1 %A, label %T1, label %F1
 
 T1:
         %B = call i1 @test8a()
   br i1 %B, label %T2, label %F1
 
 ; CHECK: T1:
 ; CHECK-NEXT: call
-; CHECK-NEXT: br i1 %B, label %T2, label %Y
+; CHECK-NEXT: br i1 %B, label %T2, label %F1
 T2:
         %C = call i1 @test8a()
   br i1 %cond, label %T3, label %F1
 
 ; CHECK: T2:
 ; CHECK-NEXT: call
-; CHECK-NEXT: br i1 %cond, label %T3, label %Y
+; CHECK-NEXT: br i1 %cond, label %T3, label %F1
 T3:
         ret i32 0
 
 F1:
         %D = phi i32 [0, %T0], [0, %T1], [1, %T2]
         %E = icmp eq i32 %D, 1
         %F = and i1 %E, %cond
   br i1 %F, label %X, label %Y

 define i32 @test9(i1 %cond, i1 %cond2) {
 Entry:
 ; CHECK-LABEL: @test9(
   %v1 = call i32 @f1()
   br i1 %cond, label %Merge, label %F1
 
 ; CHECK: Entry:
 ; CHECK-NEXT:  %v1 = call i32 @f1()
-; CHECK-NEXT:  br i1 %cond, label %F2, label %Merge
+; CHECK-NEXT:  br i1 %cond, label %F2, label %F1
 
 F1:
   %v2 = call i32 @f2()
   br label %Merge
 
 Merge:
   %B = phi i32 [%v1, %Entry], [%v2, %F1]
         %M = icmp eq i32 %B, %v1
         %M1 = xor i1 %M, 1
         %N = icmp eq i32 %B, 47
         %O = and i1 %M1, %N
   br i1 %O, label %T2, label %F2
 
-; CHECK: Merge:
+; CHECK: F1:
 ; CHECK-NOT: phi
 ; CHECK-NEXT:   %v2 = call i32 @f2()
 
 T2:
   %Q = zext i1 %M to i32
   ret i32 %Q
 
 F2:
   ret i32 %B
 ; CHECK: F2:
 ; CHECK-NEXT: phi i32
 }
 
 
 
 ; CHECK: @test10
 declare i32 @test10f1()
 declare i32 @test10f2()
 declare void @test10f3()
 
 ;; Non-local condition threading.
 define i32 @test10g(i1 %cond) {
 ; CHECK-LABEL: @test10g(
-; CHECK-NEXT:   br i1 %cond, label %T2, label %F2
+; CHECK-NEXT:   br i1 %cond, label %T1, label %F1
         br i1 %cond, label %T1, label %F1
 
 T1:
         %v1 = call i32 @test10f1()
         br label %Merge
 
 ; CHECK: %v1 = call i32 @test10f1()
 ; CHECK-NEXT: call void @f3()

 define void @test12(i32 %A) {
 ; CHECK-LABEL: @test12(
 entry:
   %cond = icmp eq i32 %A, 0
   br i1 %cond, label %bb, label %bb1
 ; Should branch to the return block instead of through BB1.
 ; CHECK: entry:
 ; CHECK-NEXT: %cond = icmp eq i32 %A, 0
-; CHECK-NEXT: br i1 %cond, label %bb1, label %return
+; CHECK-NEXT: br i1 %cond, label %bb, label %return
 
 bb:
   %B = call i32 @test10f2()
   br label %bb1
 
 bb1:
   %C = phi i32 [ %A, %entry ], [ %B, %bb ]
   %cond4 = icmp eq i32 %C, 0
   br i1 %cond4, label %bb2, label %return
 
-; CHECK: bb1:
+; CHECK: bb:
 ; CHECK-NEXT: %B = call i32 @test10f2()
 ; CHECK-NEXT: %cond4 = icmp eq i32 %B, 0
 ; CHECK-NEXT: br i1 %cond4, label %bb2, label %return
 
 bb2:
   %D = call i32 @test10f2()
   ret void
 
Merge:
   br i1 %N, label %T2, label %F2
 
 T2:
   ret i32 123
 
 F2:
   ret i32 %v1
 
-; CHECK:   br i1 %cond, label %F2, label %Merge
+; CHECK:   br i1 %cond, label %F2, label %F1
 
-; CHECK:      Merge:
+; CHECK:      F1:
 ; CHECK-NEXT:   %M = icmp eq i32 %v1, 192
 ; CHECK-NEXT:   %N = xor i1 %cond2, %M
 ; CHECK-NEXT:   br i1 %N, label %T2, label %F2
 }
 
 ; CHECK-LABEL: @test14(
 define i32 @test14(i32 %in) {
 entry:
   %A = icmp eq i32 %in, 0
-; CHECK: br i1 %A, label %right_ret, label %merge
+; CHECK: br i1 %A, label %right_ret, label %right
   br i1 %A, label %left, label %right
 
+; CHECK-NOT: merge:
+
 ; CHECK-NOT: left:
 left:
   br label %merge
 
-; CHECK-NOT: right:
 right:
   %B = call i32 @f1()
   br label %merge
 
 merge:
 ; CHECK-NOT: %C = phi i32 [%in, %left], [%B, %right]
   %C = phi i32 [%in, %left], [%B, %right]
   %D = add i32 %C, 1

 
 ;;; Verify that we can handle constraint propagation through cast.
 define i32 @test16(i1 %cond) {
 Entry:
 ; CHECK-LABEL: @test16(
   br i1 %cond, label %Merge, label %F1
 
 ; CHECK: Entry:
-; CHECK-NEXT:  br i1 %cond, label %F2, label %Merge
+; CHECK-NEXT:  br i1 %cond, label %F2, label %F1
 
 F1:
   %v1 = call i32 @f1()
   br label %Merge
 
 Merge:
   %B = phi i32 [0, %Entry], [%v1, %F1]
   %M = icmp eq i32 %B, 0
   %M1 = zext i1 %M to i32
   %N = icmp eq i32 %M1, 0
   br i1 %N, label %T2, label %F2
 
-; CHECK: Merge:
+; CHECK: F1:
 ; CHECK-NOT: phi
 ; CHECK-NEXT:   %v1 = call i32 @f1()
 
 T2:
   %Q = call i32 @f2()
   ret i32 %Q
 
 F2:

llvm/test/Transforms/JumpThreading/bb-unreachable-from-entry.ll

 ; RUN: opt -S < %s -jump-threading | FileCheck %s
 ; CHECK-LABEL: @foo
-; CHECK-NEXT: exit2:
+; CHECK-NEXT: entry:
 ; CHECK-NEXT: ret void
 define void @foo() {
 entry:
   br label %bb1
 
 entry2:
   br label %bb1
 

llvm/test/Transforms/JumpThreading/combine-metadata.ll

 ; RUN: opt < %s -jump-threading -S | FileCheck %s
 
 target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:128:128"
 target triple = "i386-apple-darwin7"
 
 declare void @use(i32 *)
 
 ; Check that we propagate nonnull to dominated loads, when we find an available
 ; loaded value.
 ; CHECK-LABEL: @test1(
-; CHECK-LABEL: ret1:
+; CHECK-LABEL: d3.thread:
 ; CHECK-NEXT: %[[p1:.*]] = load i32*, i32** %ptr
 ; CHECK-NOT: !nonnull
 ; CHECK-NEXT: store i32 1, i32* %[[p1]]
 ; CHECK-NEXT: tail call void @use(i32* null)
 ; CHECK-NEXT: ret void
 
-; CHECK-LABEL: ret2:
+; CHECK-LABEL: d1:
 ; CHECK-NEXT: %[[p2:.*]] = load i32*, i32** %ptr, !nonnull !0
 ; CHECK: tail call void @use(i32* %[[p2]])
 ; CHECK-NEXT: ret void
 define void @test1(i32** %ptr, i1 %c) {
   br i1 %c, label %d1, label %d2
 
 d1:
   %p1 = load i32*, i32** %ptr, !nonnull !0

 ; Check that we propagate nonnull to dominated loads, when we find an available
 ; loaded value.
 ; CHECK-LABEL: @test2(
 ; CHECK-LABEL: d3.thread:
 ; CHECK-NEXT: %[[p1:.*]] = load i32*, i32** %ptr, !nonnull !0
 ; CHECK-NEXT: store i32 1, i32* %[[p1]]
 ; CHECK-NEXT: br label %ret1
 
-; CHECK-LABEL: d3:
+; CHECK-LABEL: d1:
 ; CHECK-NEXT: %[[p_cmp:.*]] = load i32*, i32** %ptr
 ; CHECK-NEXT: %[[p2:.*]] = load i32*, i32** %ptr, !nonnull !0
 ; CHECK-NEXT: store i32 1, i32* %[[p2]]
 ; CHECK-NEXT: icmp eq i32* %[[p_cmp]], null
 define void @test2(i32** %ptr, i1 %c) {
   br i1 %c, label %d1, label %d2
 
 d1:

llvm/test/Transforms/JumpThreading/fold-not-thread.ll

L2:
   call void @f3()
   ret void
 }
 
 ; Make sure we can fold this branch ... We will not be able to thread it as
 ; L0 is too big to duplicate. L2 is the unreachable block here.
 ;
 ; CHECK-LABEL: @test_br_folding_not_threading(
-; CHECK: L1:
+; CHECK: L0:
 ; CHECK: call i32 @f2()
 ; CHECK: call void @f3()
 ; CHECK-NEXT: ret void
 ; CHECK-NOT: br
 ; CHECK: L3:
 define void @test_br_folding_not_threading(i1 %cond) nounwind {
 entry:
   br i1 %cond, label %L0, label %L3 

 }
 
 
 ; Make sure we can fold this branch ... We will not be able to thread it as
 ; L0 is too big to duplicate. L2 is the unreachable block here.
 ; With more than 1 predecessors.
 ;
 ; CHECK-LABEL: @test_br_folding_not_threading_multiple_preds(
-; CHECK: L1:
+; CHECK: L0:
 ; CHECK: call i32 @f2()
 ; CHECK: call void @f3()
 ; CHECK-NEXT: ret void
 ; CHECK-NOT: br
 ; CHECK: L3:
 define void @test_br_folding_not_threading_multiple_preds(i1 %condx, i1 %cond) nounwind {
 entry:
   br i1 %condx, label %X0, label %X1

 ; Make sure we can fold this branch ... We will not be able to thread it as
 ; L0 is too big to duplicate.
 ; We do not attempt to rewrite the indirectbr target here, but we still take
 ; its target after L0 into account and that enables us to fold.
 ;
 ; L2 is the unreachable block here.
 ; 
 ; CHECK-LABEL: @test_br_folding_not_threading_indirect_branch(
-; CHECK: L1:
+; CHECK: L0:
 ; CHECK: call i32 @f2()
 ; CHECK: call void @f3()
 ; CHECK-NEXT: ret void
 ; CHECK-NOT: br
 ; CHECK: L3:
 define void @test_br_folding_not_threading_indirect_branch(i1 %condx, i1 %cond) nounwind {
 entry:
   br i1 %condx, label %X0, label %X1

llvm/test/Transforms/JumpThreading/guards.ll

 ; RUN: opt < %s -jump-threading -dce -S | FileCheck %s
 
 declare void @llvm.experimental.guard(i1, ...)
 
 declare i32 @f1()
 declare i32 @f2()
 
 define i32 @branch_implies_guard(i32 %a) {
 ; CHECK-LABEL: @branch_implies_guard(
   %cond = icmp slt i32 %a, 10
   br i1 %cond, label %T1, label %F1
 
 T1:
-; CHECK:       T1.split
+; CHECK:       T1
 ; CHECK:         %v1 = call i32 @f1()
 ; CHECK-NEXT:    %retVal
 ; CHECK-NEXT:    br label %Merge
   %v1 = call i32 @f1()
   br label %Merge
 
 F1:
-; CHECK:       F1.split
+; CHECK:       F1
 ; CHECK:         %v2 = call i32 @f2()
 ; CHECK-NEXT:    %retVal
 ; CHECK-NEXT:    %condGuard
 ; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 %condGuard
 ; CHECK-NEXT:    br label %Merge
   %v2 = call i32 @f2()
   br label %Merge
 
 Merge:
 ; CHECK:       Merge
 ; CHECK-NOT:     call void(i1, ...) @llvm.experimental.guard(
   %retPhi = phi i32 [ %v1, %T1 ], [ %v2, %F1 ]
   %retVal = add i32 %retPhi, 10
   %condGuard = icmp slt i32 %a, 20
   call void(i1, ...) @llvm.experimental.guard(i1 %condGuard) [ "deopt"() ]
   ret i32 %retVal
 }
 
 define i32 @not_branch_implies_guard(i32 %a) {
 ; CHECK-LABEL: @not_branch_implies_guard(
   %cond = icmp slt i32 %a, 20
   br i1 %cond, label %T1, label %F1
 
 T1:
-; CHECK:       T1.split:
+; CHECK:       T1:
 ; CHECK-NEXT:    %v1 = call i32 @f1()
 ; CHECK-NEXT:    %retVal
 ; CHECK-NEXT:    %condGuard
 ; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 %condGuard
 ; CHECK-NEXT:    br label %Merge
   %v1 = call i32 @f1()
   br label %Merge
 
 F1:
-; CHECK:       F1.split:
+; CHECK:       F1:
 ; CHECK-NEXT:   %v2 = call i32 @f2()
 ; CHECK-NEXT:   %retVal
 ; CHECK-NEXT:   br label %Merge
   %v2 = call i32 @f2()
   br label %Merge
 
 Merge:
 ; CHECK:       Merge

 ; CHECK-LABEL: @not_a_diamond2(
   br label %Parent
 
 Merge:
   call void(i1, ...) @llvm.experimental.guard(i1 %cond1)[ "deopt"() ]
   ret void
 
 Pred:
-; CHECK-NEXT:  Pred:
+; CHECK-NEXT:  Parent:
 ; CHECK-NEXT:    switch i32 %a, label %Exit
   switch i32 %a, label %Exit [
     i32 10, label %Merge
     i32 20, label %Merge
   ]
 
 Parent:
   br label %Pred
BB2:
   ret void
 }
 
 declare void @f(i1)
 ; Same as dont_fold_guard1 but use switch instead of branch.
 ; triggers source code `ProcessThreadableEdges`.
 define void @dont_fold_guard4(i1 %cmp1, i32 %i) nounwind {
 ; CHECK-LABEL: dont_fold_guard4 
-; CHECK-LABEL: L2:
+; CHECK-LABEL: L0:
 ; CHECK-NEXT: %cmp = icmp eq i32 %i, 0 
 ; CHECK-NEXT: guard(i1 %cmp)
 ; CHECK-NEXT: dummy(i1 true)
 ; CHECK-NEXT: @f(i1 true)
 ; CHECK-NEXT: ret void
 entry:
   br i1 %cmp1, label %L0, label %L3 
 L0:

llvm/test/Transforms/JumpThreading/header-succ.ll

 ; CHECK-LABEL: @jump_threading_loopheader
 top:
     br label %entry
 
 entry:
     %ind = phi i32 [0, %top], [%nextind, %latch]
     %nextind = add i32 %ind, 1
     %cmp = icmp ule i32 %ind, 10
-; CHECK: br i1 %cmp, label %latch, label %exit
+; CHECK: br i1 %cmp, label %body, label %exit
     br i1 %cmp, label %body, label %latch
 
 body:
     call void @opaque_body()
 ; CHECK: br label %entry
     br label %latch
 
 latch:

 ; CHECK-LABEL: @jump_threading_loopheader2
 top:
     br label %entry
 
 entry:
     %ind = phi i32 [0, %top], [%nextind, %latch]
     %nextind = add i32 %ind, 1
     %cmp = icmp ule i32 %ind, 10
-; CHECK: br i1 %cmp, label %exit, label %latch
+; CHECK: br i1 %cmp, label %body, label %latch
     br i1 %cmp, label %body, label %latch
 
 body:
     call void @opaque_body()
 ; CHECK: br label %entry
     br label %latch
 
 latch:

 ; CHECK-LABEL: @jump_threading_loopheader3
 top:
     br label %entry
 
 entry:
     %ind = phi i32 [0, %top], [%nextind, %latch]
     %nextind = add i32 %ind, 1
     %cmp = icmp ule i32 %ind, 10
-; CHECK: br i1 %cmp, label %latch, label %exit
+; CHECK: br i1 %cmp, label %body, label %exit
     br i1 %cmp, label %body, label %latch
 
 body:
     call void @opaque_body()
 ; CHECK: br label %entry
     br label %latch
 
 latch:
    %phi = phi i32 [undef, %entry], [0, %body]
    %cmp1 = icmp eq i32 %phi, 0
    br i1 %cmp1, label %entry, label %exit
 
 exit:
     ret void
 }

llvm/test/Transforms/JumpThreading/implied-cond.ll

 ; RUN: opt -jump-threading -S < %s | FileCheck %s
 
 declare void @side_effect(i32)
 
 define void @test0(i32 %i, i32 %len) {
 ; CHECK-LABEL: @test0(
  entry:
   call void @side_effect(i32 0)
   %i.inc = add nuw i32 %i, 1
   %c0 = icmp ult i32 %i.inc, %len
   br i1 %c0, label %left, label %right
 
  left:
 ; CHECK: entry:
-; CHECK: br i1 %c0, label %left0, label %right
+; CHECK: br i1 %c0, label %left, label %right
 
-; CHECK: left0:
+; CHECK: left:
 ; CHECK: call void @side_effect
 ; CHECK-NOT: br i1 %c1
 ; CHECK: call void @side_effect
   call void @side_effect(i32 0)
   %c1 = icmp ult i32 %i, %len
   br i1 %c1, label %left0, label %right
 
  left0:

  entry:
   call void @side_effect(i32 0)
   %i.inc = add nsw i32 %i, 1
   %c0 = icmp slt i32 %i.inc, %len
   br i1 %c0, label %left, label %right
 
  left:
 ; CHECK: entry:
-; CHECK: br i1 %c0, label %left0, label %right
+; CHECK: br i1 %c0, label %left, label %right
 
-; CHECK: left0:
+; CHECK: left:
 ; CHECK: call void @side_effect
 ; CHECK-NOT: br i1 %c1
 ; CHECK: call void @side_effect
   call void @side_effect(i32 0)
   %c1 = icmp slt i32 %i, %len
   br i1 %c1, label %left0, label %right
 
  left0:
   call void @side_effect(i32 0)
   ret void
 
  right:
   %t = phi i32 [ 1, %left ], [ 2, %entry ]
   call void @side_effect(i32 %t)
   ret void
 }
 
 define void @test2(i32 %i, i32 %len, i1* %c.ptr) {
 ; CHECK-LABEL: @test2(
 
 ; CHECK: entry:
 ; CHECK: br i1 %c0, label %cont, label %right
 ; CHECK: cont:
-; CHECK: br i1 %c, label %left0, label %right
-; CHECK: left0:
+; CHECK: br i1 %c, label %left, label %right
+; CHECK: left:
 ; CHECK: call void @side_effect(i32 0)
 ; CHECK: call void @side_effect(i32 0)
  entry:
   call void @side_effect(i32 0)
   %i.inc = add nsw i32 %i, 1
   %c0 = icmp slt i32 %i.inc, %len
   br i1 %c0, label %cont, label %right
 
right:
   %t = phi i32 [ 1, %left ], [ 2, %entry ], [ 3, %cont ]
   call void @side_effect(i32 %t)
   ret void
 }
 
 ; A s<= B implies A s> B is false.
 ; CHECK-LABEL: @test3(
 ; CHECK: entry:
-; CHECK: br i1 %cmp, label %if.end, label %if.end3
+; CHECK: br i1 %cmp, label %if.then, label %if.end3
 ; CHECK-NOT: br i1 %cmp1, label %if.then2, label %if.end
 ; CHECK-NOT: call void @side_effect(i32 0)
 ; CHECK: br label %if.end3
 ; CHECK: ret void
 
 define void @test3(i32 %a, i32 %b) {
 entry:
   %cmp = icmp sle i32 %a, %b

llvm/test/Transforms/JumpThreading/indirectbr.ll

 ; RUN: opt -S < %s -jump-threading | FileCheck %s
 
 ; Keep block addresses alive.
 @addresses = constant [4 x i8*] [
   i8* blockaddress(@test1, %L1), i8* blockaddress(@test1, %L2),
   i8* blockaddress(@test2, %L1), i8* blockaddress(@test2, %L2)
 ]
 
 declare void @bar()
 declare void @baz()
 
 
 
 ; Check basic jump threading for indirectbr instructions.
 
 ; CHECK: void @test1
-; CHECK: br i1 %tobool, label %L1, label %indirectgoto
-; CHECK-NOT: if.else:
-; CHECK: L1:
+; CHECK: br i1 %tobool, label %L1, label %if.else
 ; CHECK: indirectbr i8* %address, [label %L1, label %L2]
+; CHECK: L1:
+; CHECK-NOT: indirectgoto:
 define void @test1(i32 %i, i8* %address) nounwind {
 entry:
   %rem = srem i32 %i, 2
   %tobool = icmp ne i32 %rem, 0
   br i1 %tobool, label %indirectgoto, label %if.else
 
 if.else:                                          ; preds = %entry
   br label %indirectgoto

llvm/test/Transforms/JumpThreading/induction.ll

 ; RUN: opt -S -jump-threading < %s | FileCheck %s
 
 define i8 @test(i32 %a, i32 %length) {
 ; CHECK-LABEL: @test
 entry:
-; CHECK: br label %backedge
+; CHECK: br label %loop
   br label %loop
 
 loop:
-; CHECK-LABEL: backedge:
+; CHECK-LABEL: loop:
 ; CHECK: phi i32
-; CHECK: br i1 %cont, label %backedge, label %exit
+; CHECK: br i1 %cont, label %loop, label %exit
   %iv = phi i32 [0, %entry], [%iv.next, %backedge]
   ;; We can use an inductive argument to prove %iv is always positive
   %cnd = icmp sge i32 %iv, 0
   br i1 %cnd, label %backedge, label %exit
 
 backedge:
   %iv.next = add nsw i32 %iv, 1
   %cont = icmp slt i32 %iv.next, 400
   br i1 %cont, label %loop, label %exit
 exit:
   ret i8 0
 }
 

llvm/test/Transforms/JumpThreading/lvi-tristate.ll

 ; RUN: opt -jump-threading -simplifycfg -S < %s | FileCheck %s
-; CHECK-NOT: bb6:
+; CHECK-NOT: bb10:
 ; CHECK-NOT: bb7:
 ; CHECK-NOT: bb8:
 ; CHECK-NOT: bb11:
 ; CHECK-NOT: bb12:
 ; CHECK: bb:
 ; CHECK: bb2:
 ; CHECK: bb4:
-; CHECK: bb10:
+; CHECK: bb6:
 ; CHECK: bb13:
 declare void @ham()
 
 define void @hoge() {
 bb:
   %tmp = and i32 undef, 1073741823
   %tmp1 = icmp eq i32 %tmp, 2
   br i1 %tmp1, label %bb12, label %bb2

llvm/test/Transforms/JumpThreading/phi-known.ll

 entry:
   %cmp0 = icmp eq i8* %p, null
   br i1 %cmp0, label %exit, label %loop
 loop:
   %p1 = phi i8* [%p, %entry], [%p2, %backedge]
   %cmp1 = icmp eq i8* %p1, null
   br i1 %cmp1, label %exit, label %backedge
 backedge:
-; CHECK-LABEL: backedge:
+; CHECK-LABEL: loop:
 ; CHECK-NEXT: phi
 ; CHECK-NEXT: bitcast
 ; CHECK-NEXT: load
 ; CHECK-NEXT: cmp
 ; CHECK-NEXT: br 
-; CHECK-DAG: label %backedge
+; CHECK-DAG: label %loop
   %addr = bitcast i8* %p1 to i8**
   %p2 = load i8*, i8** %addr
   %cmp2 = icmp eq i8* %p2, null
   br i1 %cmp2, label %exit, label %loop
 exit:
   ret void
 }
 

llvm/test/Transforms/JumpThreading/range-compare.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ;RUN: opt < %s -jump-threading -S | FileCheck %s
 
 
 declare void @bar(...)
 declare void @baz(...)
 
 ; Make sure we thread the end of the bar block to the end of the function.
 define void @test1(i32 %x) {
 ; CHECK-LABEL: @test1(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i32 [[X:%.*]], 9
 ; CHECK-NEXT:    br i1 [[CMP]], label [[IF_END_THREAD:%.*]], label [[IF_END:%.*]]
-; CHECK:       if.end.thread:
+; CHECK:       if.then:
 ; CHECK-NEXT:    call void (...) @bar()
 ; CHECK-NEXT:    br label [[IF_END4:%.*]]
 ; CHECK:       if.end:
 ; CHECK-NEXT:    [[X_OFF:%.*]] = add i32 [[X]], -3
 ; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i32 [[X_OFF]], 5
 ; CHECK-NEXT:    br i1 [[TMP0]], label [[IF_THEN3:%.*]], label [[IF_END4]]
 ; CHECK:       if.then3:
 ; CHECK-NEXT:    call void (...) @baz()

 }
 
 ; Make sure we thread the false side of the first if to the end of the function.
 define void @test2(i32 %x) {
 ; CHECK-LABEL: @test2(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[X:%.*]], 9
 ; CHECK-NEXT:    br i1 [[CMP]], label [[IF_END:%.*]], label [[IF_END4:%.*]]
-; CHECK:       if.end:
+; CHECK:       if.then:
 ; CHECK-NEXT:    call void (...) @bar()
 ; CHECK-NEXT:    [[X_OFF:%.*]] = add i32 [[X]], -3
 ; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i32 [[X_OFF]], 5
 ; CHECK-NEXT:    br i1 [[TMP0]], label [[IF_THEN3:%.*]], label [[IF_END4]]
 ; CHECK:       if.then3:
 ; CHECK-NEXT:    call void (...) @baz()
 ; CHECK-NEXT:    br label [[IF_END4]]
 ; CHECK:       if.end4:

llvm/test/Transforms/JumpThreading/removed-use.ll

 ; RUN: opt -S < %s -jump-threading | FileCheck %s
 ; CHECK-LABEL: @foo
-; CHECK: bb6:
+; CHECK: entry:
 ; CHECK-NEXT: ret void
-; CHECK: bb3:
-; CHECK: br label %bb3
+; CHECK: bb5:
+; CHECK: br label %bb5
 define void @foo() {
 entry:
   br i1 true, label %bb6, label %bb3
 
 bb3:
   %x0 = phi i32 [ undef, %entry ], [ %x1, %bb5 ]
   %y  = and i64 undef, 1
   %p  = icmp ne i64 %y, 0

llvm/test/Transforms/JumpThreading/select.ll

 
 
 ; Jump threading of indirectbr with select as address.  Test increased
 ; duplication threshold for cases where indirectbr is being threaded
 ; through.
 
 ; CHECK-LABEL: @test_indirectbr_thresh(
 ; CHECK-NEXT: entry:
-; CHECK-NEXT: br i1 %cond, label %L1, label %L3
+; CHECK-NEXT: br i1 %cond, label %L0, label %L3
 ; CHECK-NOT: indirectbr
 define void @test_indirectbr_thresh(i1 %cond, i8* %address) nounwind {
 entry:
   br i1 %cond, label %L0, label %L3
 L0:
   %indirect.goto.dest = select i1 %cond, i8* blockaddress(@test_indirectbr_thresh, %L1), i8* %address
   call void @quux()
   call void @quux()
.exit:                                  ; preds = %entry, %cond.false.i, %cond.false.6.i, %cond.false.10.i, %cond.false.15.i
   %cond23.i = phi i1 [ false, %entry ], [ true, %cond.false.i ], [ false, %cond.false.6.i ], [ %phitmp, %cond.false.15.i ], [ true, %cond.false.10.i ]
   %j.add3 = select i1 %cond23.i, i32 %j, i32 %add3
   ret i32 %j.add3
 
 ; CHECK-LABEL: @unfold3
 ; CHECK: br i1 %cmp.i, label %.exit.thread2, label %cond.false.i
 ; CHECK: br i1 %cmp4.i, label %.exit.thread, label %cond.false.6.i
 ; CHECK: br i1 %cmp8.i, label %.exit.thread2, label %cond.false.10.i
-; CHECK: br i1 %cmp13.i, label %.exit.thread, label %.exit
+; CHECK: br i1 %cmp13.i, label %.exit.thread, label %cond.false.15.i
 ; CHECK: br i1 %phitmp, label %.exit.thread, label %.exit.thread2
 ; CHECK: br label %.exit.thread2
 }
 
 define i32 @unfold4(i32 %u, i32 %v, i32 %w, i32 %x, i32 %y, i32 %z, i32 %j) nounwind {
 entry:
   %add3 = add nsw i32 %j, 2
   %cmp.i = icmp slt i32 %u, %v
.exit:                                  ; preds = %entry, %cond.false.i, %cond.false.6.i, %cond.false.10.i, %cond.false.15.i
   %lnot.i18 = icmp eq i32 %cond23.i, 1
   %j.add3 = select i1 %lnot.i18, i32 %j, i32 %add3
   ret i32 %j.add3
 
 ; CHECK-LABEL: @unfold4
 ; CHECK: br i1 %cmp.i, label %.exit.thread, label %cond.false.i
 ; CHECK: br i1 %cmp4.i, label %.exit.thread3, label %cond.false.6.i
 ; CHECK: br i1 %cmp8.i, label %.exit.thread, label %cond.false.10.i
-; CHECK: br i1 %cmp13.i, label %.exit.thread3, label %.exit
+; CHECK: br i1 %cmp13.i, label %.exit.thread3, label %cond.false.15.i
 ; CHECK: br i1 %lnot.i18, label %.exit.thread, label %.exit.thread3
 ; CHECK: br label %.exit.thread3
 }
 
 define i32 @unfold5(i32 %u, i32 %v, i32 %w, i32 %x, i32 %y, i32 %z, i32 %j) nounwind {
 entry:
   %add3 = add nsw i32 %j, 2
   %cmp.i = icmp slt i32 %u, %v

llvm/test/Transforms/JumpThreading/static-profile.ll

entry:
   br i1 %enter_loop, label %exit, label %check_1, !prof !1
 ; CHECK: br i1 %enter_loop, label %exit, label %check_1, !prof !1
 
 check_1:
   %v = load i32, i32* %p
   %cond1 = icmp eq i32 %v, 1
   br i1 %cond1, label %eq_1, label %check_2
 ; No metadata:
-; CHECK:   br i1 %cond1, label %check_2.thread, label %check_2{{$}}
+; CHECK:   br i1 %cond1, label %eq_1, label %check_2{{$}}
 
 eq_1:
   call void @bar()
   br label %check_2
 ; Verify the new edge:
-; CHECK: check_2.thread:
+; CHECK: eq_1:
 ; CHECK-NEXT: call void @bar()
 ; CHECK-NEXT: br label %latch
 
 check_2:
   %cond2 = icmp eq i32 %v, 2
   br i1 %cond2, label %eq_2, label %check_3
 ; No metadata:
 ; CHECK: br i1 %cond2, label %eq_2, label %check_3{{$}}

llvm/test/Transforms/JumpThreading/thread-loads.ll

 ; RUN: opt < %s -jump-threading -S | FileCheck %s
 ; RUN: opt < %s -aa-pipeline=basic-aa -passes=jump-threading -S | FileCheck %s
 
 target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:128:128"
 target triple = "i386-apple-darwin7"
 
 ; Test that we can thread through the block with the partially redundant load (%2).
 ; rdar://6402033
 define i32 @test1(i32* %P) nounwind {
 ; CHECK-LABEL: @test1(
 entry:
   %0 = tail call i32 (...) @f1() nounwind    ; <i32> [#uses=1]
   %1 = icmp eq i32 %0, 0    ; <i1> [#uses=1]
   br i1 %1, label %bb1, label %bb
 
 bb:   ; preds = %entry
-; CHECK: bb1.thread:
+; CHECK: bb:
 ; CHECK: store
 ; CHECK: br label %bb3
   store i32 42, i32* %P, align 4
   br label %bb1
 
 bb1:    ; preds = %entry, %bb
   %res.0 = phi i32 [ 1, %bb ], [ 0, %entry ]    ; <i32> [#uses=2]
   %2 = load i32, i32* %P, align 4    ; <i32> [#uses=1]
   %3 = icmp sgt i32 %2, 36    ; <i1> [#uses=1]
   br i1 %3, label %bb3, label %bb2
 
 bb2:    ; preds = %bb1
   %4 = tail call i32 (...) @f2() nounwind    ; <i32> [#uses=0]
   ret i32 %res.0
 
 bb3:    ; preds = %bb1
 ; CHECK: bb3:
-; CHECK: %res.01 = phi i32 [ 1, %bb1.thread ], [ 0, %bb1 ]
+; CHECK: %res.01 = phi i32 [ 1, %bb ], [ 0, %bb1thread-pre-split ]
 ; CHECK: ret i32 %res.01
   ret i32 %res.0
 }
 
 declare i32 @f1(...)
 
 declare i32 @f2(...)
 
 
 ;; Check that we preserve TBAA information.
 ; rdar://11039258
 
 define i32 @test2(i32* %P) nounwind {
 ; CHECK-LABEL: @test2(
 entry:
   %0 = tail call i32 (...) @f1() nounwind    ; <i32> [#uses=1]
   %1 = icmp eq i32 %0, 0    ; <i1> [#uses=1]
   br i1 %1, label %bb1, label %bb
 
 bb:   ; preds = %entry
-; CHECK: bb1.thread:
+; CHECK: bb:
 ; CHECK: store{{.*}}, !tbaa !0
 ; CHECK: br label %bb3
   store i32 42, i32* %P, align 4, !tbaa !0
   br label %bb1
 
 bb1:    ; preds = %entry, %bb
   %res.0 = phi i32 [ 1, %bb ], [ 0, %entry ]
   %2 = load i32, i32* %P, align 4, !tbaa !0
   %3 = icmp sgt i32 %2, 36
   br i1 %3, label %bb3, label %bb2
 
 bb2:    ; preds = %bb1
   %4 = tail call i32 (...) @f2() nounwind
   ret i32 %res.0
 
 bb3:    ; preds = %bb1
 ; CHECK: bb3:
-; CHECK: %res.01 = phi i32 [ 1, %bb1.thread ], [ 0, %bb1 ]
+; CHECK: %res.01 = phi i32 [ 1, %bb ], [ 0, %bb1thread-pre-split ]
 ; CHECK: ret i32 %res.01
   ret i32 %res.0
 }
 
 define i32 @test3(i8** %x, i1 %f) {
 ; Correctly thread loads of different (but compatible) types, placing bitcasts
 ; as necessary in the predecessors. This is especially tricky because the same
 ; predecessor ends up with two entries in the PHI node and they must share

 define i32 @test4(i32* %P) {
 ; CHECK-LABEL: @test4(
 entry:
   %v0 = tail call i32 (...) @f1()
   %v1 = icmp eq i32 %v0, 0
   br i1 %v1, label %bb1, label %bb
 
 bb:
-; CHECK: bb1.thread:
+; CHECK: bb:
 ; CHECK: store atomic
 ; CHECK: br label %bb3
   store atomic i32 42, i32* %P unordered, align 4
   br label %bb1
 
 bb1:
-; CHECK: bb1:
+; CHECK: bb1thread-pre-split:
 ; CHECK-NOT: phi
 ; CHECK: load atomic
   %res.0 = phi i32 [ 1, %bb ], [ 0, %entry ]
   %v2 = load atomic i32, i32* %P unordered, align 4
   %v3 = icmp sgt i32 %v2, 36
   br i1 %v3, label %bb3, label %bb2
 
 bb2:
ret2:
   ret void
 }
 
 define i32 @fn_noalias(i1 %c2,i64* noalias %P, i64* noalias %P2) {
 ; CHECK-LABEL: @fn_noalias
 ; CHECK-LABEL: cond1:
 ; CHECK: %[[LD1:.*]] = load i64, i64* %P
 ; CHECK: br i1 %c, label %[[THREAD:.*]], label %end
-; CHECK-LABEL: cond2:
+; CHECK-LABEL: cond2thread-pre-split:
 ; CHECK: %[[LD2:.*]] = load i64, i64* %P
 ; CHECK-LABEL: cond3:
-; CHECK: %[[PHI:.*]] = phi i64 [ %[[LD1]], %[[THREAD]] ], [ %[[LD2]], %cond2 ]
+; CHECK: %[[PHI:.*]] = phi i64 [ %[[LD1]], %[[THREAD]] ], [ %[[LD2]], %cond2thread-pre-split ]
 ; CHECK: call void @fn3(i64 %[[PHI]])
 entry:
   br i1 %c2, label %cond2, label %cond1
 
 cond1:
   %l1 = load i64, i64* %P
   store i64 42, i64* %P2
   %c = icmp eq i64 %l1, 0

 define fastcc i32 @Search(i64 %idxprom.i, i64 %idxprom.i89, i32 %c) {
 ; CHECK-LABEL: @Search
 ; CHECK-LABEL: sw.bb.i:
 ; CHECK: %[[LD1:.*]] = load i32, i32* %arrayidx185, align 4
 ; CHECK: %[[C1:.*]] = icmp eq i32 %[[LD1]], 0
 ; CHECK: br i1 %[[C1]], label %sw.bb21.i.thread, label %if.then.i64
 ; CHECK-LABEL: sw.bb21.i.thread:
 ; CHECK: br label %[[THREAD_TO:.*]]
-; CHECK-LABEL: sw.bb21.i:
+; CHECK-LABEL: sw.bb21.ithread-pre-split:
 ; CHECK: %[[LD2:.*]] = load i32, i32* %arrayidx185, align 4
 ; CHECK: %[[C2:.*]] = icmp eq i32 %[[LD2]], 0
 ; CHECK:br i1 %[[C2]], label %[[THREAD_TO]], label %cleanup
 entry:
   %arrayidx185 = getelementptr inbounds [65 x i32], [65 x i32]* @hash_move, i64 0, i64 %idxprom.i
   %arrayidx307 = getelementptr inbounds [65 x i32], [65 x i32]* @current_move, i64 0, i64 %idxprom.i
   %arrayidx89 = getelementptr inbounds [65 x i32*], [65 x i32*]* @last, i64 0, i64 %idxprom.i
   %phase = getelementptr inbounds [65 x %struct.NEXT_MOVE], [65 x %struct.NEXT_MOVE]* @next_status, i64 0, i64 %idxprom.i, i32 0

 declare void @f67()
 declare void @Cleanup()
 declare void @f65()
 
 define i32 @fn_SinglePred(i1 %c2,i64* %P) {
 ; CHECK-LABEL: @fn_SinglePred
 ; CHECK-LABEL: entry:
 ; CHECK: %[[L1:.*]] = load i64, i64* %P
-; CHECK: br i1 %c, label %cond3, label %cond1
+; CHECK: br i1 %c, label %cond2.thread, label %cond1
+; CHECK-LABEL: cond2.thread:
+; CHECK: call void @fn2(i64 %l1)
+; CHECK: call void @fn3(i64 %l1)
 ; CHECK-LABEL: cond2:
 ; CHECK-NOT: load
 ; CHECK: %[[PHI:.*]] = phi i64 [ %[[L1]], %cond1 ]
 ; CHECK: call void @fn2(i64 %[[PHI]])
 ; CHECK: br label %end
-; CHECK-LABEL: cond3:
-; CHECK: call void @fn2(i64 %l1)
-; CHECK: call void @fn3(i64 %l1)
 
 entry:
   %l1 = load i64, i64* %P
   %c = icmp eq i64 %l1, 0
   br i1 %c, label %cond2, label %cond1
 
 cond1:
   br i1 %c2, label %cond2, label %end

 end:
   ret i32 0
 }
 
 define i32 @fn_SinglePredMultihop(i1 %c1, i1 %c2,i64* %P) {
 ; CHECK-LABEL: @fn_SinglePredMultihop
 ; CHECK-LABEL: entry:
 ; CHECK: %[[L1:.*]] = load i64, i64* %P
-; CHECK: br i1 %c0, label %cond3, label %cond0
+; CHECK: br i1 %c0, label %cond2.thread, label %cond0
+; CHECK-LABEL: cond2.thread:
+; CHECK: call void @fn2(i64 %l1)
+; CHECK: call void @fn3(i64 %l1)
 ; CHECK-LABEL: cond2:
 ; CHECK-NOT: load
 ; CHECK: %[[PHI:.*]] = phi i64 [ %[[L1]], %cond1 ]
 ; CHECK: call void @fn2(i64 %[[PHI]])
 ; CHECK: br label %end
-; CHECK-LABEL: cond3:
-; CHECK: call void @fn2(i64 %l1)
-; CHECK: call void @fn3(i64 %l1)
 
 entry:
   %l1 = load i64, i64* %P
   %c0 = icmp eq i64 %l1, 0
   br i1 %c0, label %cond2, label %cond0
 
 cond0:
   br i1 %c1, label %cond1, label %end

 declare void @fn3(i64)
 
 
 ; Make sure we phi-translate and make the partially redundant load in
 ; merge fully redudant and then we can jump-thread the block with the
 ; store.
 ;
 ; CHECK-LABEL: define i32 @phi_translate_partial_redundant_loads(i32, i32*, i32*
-; CHECK: merge.thread:
+; CHECK: left:
 ; CHECK: store
 ; CHECK: br label %left_x
 ;
 ; CHECK: left_x:
 ; CHECK-NEXT: ret i32 20
 define i32 @phi_translate_partial_redundant_loads(i32, i32*, i32*)  {
   %cmp0 = icmp ne i32 %0, 0
   br i1 %cmp0, label %left, label %right

llvm/test/Transforms/LoopUnroll/2011-08-09-PhiUpdate.ll

 
 ; Check that the loop exit merges values from all the iterations. This
 ; could be a tad fragile, but it's a good test.
 ;
 ; CHECK-LABEL: @foo(
 ; CHECK: return:
 ; CHECK: %retval.0 = phi i32 [ %tmp7.i, %land.lhs.true ], [ 0, %do.cond ], [ %tmp7.i.1, %land.lhs.true.1 ], [ 0, %do.cond.1 ], [ %tmp7.i.2, %land.lhs.true.2 ], [ 0, %do.cond.2 ], [ %tmp7.i.3, %land.lhs.true.3 ], [ 0, %do.cond.3 ]
 ; CHECK-NOT: @bar(
-; CHECK: bar.exit.3
+; CHECK: cond.true.i.3
 define i32 @foo() uwtable ssp align 2 {
 entry:
   br i1 undef, label %return, label %if.end
 
 if.end:                                           ; preds = %entry
   %call2 = call i32 @getval()
   br label %do.body
 

llvm/test/Transforms/NewGVN/pair_jumpthread.ll

 ;   return rc.second;
 ; }
 ; CHECK-LABEL: @testBI(
 ; CHECK:  _ZL6calleei.exit:
 ; CHECK:    [[PHIOFOPS:%.*]] = phi i64 [ 1, %if.then.i ], [ {{%.*}}, %if.else.i ]
 ; CHECK:    [[TOBOOL:%.*]] = icmp eq i64 [[PHIOFOPS]], 0
 ;
 ; CHECK-JT-LABEL: @testBI(
-; CHECK-JT:       _ZL6calleei.exit.thread:
+; CHECK-JT:       if.then.i:
 ;
 
 entry:
   %call.i = call signext i32 @dummy(i32 signext %v)
   %tobool.i = icmp eq i32 %call.i, 0
   br i1 %tobool.i, label %if.else.i, label %if.then.i
 
 if.then.i:                                        ; preds = %entry

 ;   return rc.first;
 ; }
 ; CHECK-LABEL: @testIB(
 ; CHECK:  _ZL6calleei.exit:
 ; CHECK:     [[PHIOFOPS:%.*]] = phi i64 [ 4294967296, %if.then.i ], [ {{%.*}}, %if.else.i ]
 ; CHECK:     [[TOBOOL:%.*]] = icmp eq i64 [[PHIOFOPS]], 0
 ;
 ; CHECK-JT-LABEL: @testIB(
-; CHECK-JT:       _ZL6calleei.exit.thread:
+; CHECK-JT:       if.then.i:
 ;
 
 entry:
   %call.i = call signext i32 @dummy(i32 signext %v)
   %tobool.i = icmp eq i32 %call.i, 0
   br i1 %tobool.i, label %if.else.i, label %if.then.i
 
 if.then.i:                                        ; preds = %entry

llvm/test/Transforms/PhaseOrdering/simplifycfg-options.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -O1 -S < %s                    | FileCheck %s --check-prefix=ALL --check-prefix=OLDPM
 ; RUN: opt -passes='default<O1>' -S < %s  | FileCheck %s --check-prefix=ALL --check-prefix=NEWPM
 
 ; Don't simplify unconditional branches from empty blocks in simplifyCFG
 ; until late in the pipeline because it can destroy canonical loop structure.
 
 define i1 @PR33605(i32 %a, i32 %b, i32* %c) {
 ; ALL-LABEL: @PR33605(
-; ALL-NEXT:  for.body:
+; ALL-NEXT:  entry:
 ; ALL-NEXT:    [[OR:%.*]] = or i32 [[B:%.*]], [[A:%.*]]
 ; ALL-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds i32, i32* [[C:%.*]], i64 1
 ; ALL-NEXT:    [[TMP0:%.*]] = load i32, i32* [[ARRAYIDX]], align 4
 ; ALL-NEXT:    [[CMP:%.*]] = icmp eq i32 [[OR]], [[TMP0]]
 ; ALL-NEXT:    br i1 [[CMP]], label [[IF_END:%.*]], label [[IF_THEN:%.*]]
 ; ALL:       if.then:
 ; ALL-NEXT:    store i32 [[OR]], i32* [[ARRAYIDX]], align 4
 ; ALL-NEXT:    tail call void @foo()