Index: llvm/lib/Transforms/Scalar/JumpThreading.cpp =================================================================== --- llvm/lib/Transforms/Scalar/JumpThreading.cpp +++ llvm/lib/Transforms/Scalar/JumpThreading.cpp @@ -419,7 +419,9 @@ bool Changed; do { Changed = false; - for (auto &BB : F) { + auto BBList = &(F.getBasicBlockList()); + auto FuncRevIter = make_range(BBList->rbegin(), BBList->rend()); + for (auto &BB : FuncRevIter) { if (Unreachable.count(&BB)) continue; while (processBlock(&BB)) // Thread all of the branches we can over BB. Index: llvm/test/Analysis/LazyValueAnalysis/lvi-after-jumpthreading.ll =================================================================== --- llvm/test/Analysis/LazyValueAnalysis/lvi-after-jumpthreading.ll +++ llvm/test/Analysis/LazyValueAnalysis/lvi-after-jumpthreading.ll @@ -19,11 +19,11 @@ ; CHECK-LABEL: backedge: ; 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: ; LatticeVal for: ' %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]' in BB: '%backedge' is: constantrange<0, -2147483648> +; CHECK-NEXT: ; LatticeVal for: ' %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]' in BB: '%exit' is: constantrange<399, 2147483647> ; 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.next = add nsw i32 %iv, 1' in BB: '%exit' is: constantrange<400, 401> +; CHECK-NEXT: ; LatticeVal for: ' %iv.next = add nsw i32 %iv, 1' in BB: '%backedge' is: constantrange<1, -2147483648> +; CHECK-NEXT: ; LatticeVal for: ' %iv.next = add nsw i32 %iv, 1' in BB: '%exit' is: constantrange<400, -2147483648> ; 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: '%exit' is: constantrange<0, -1> Index: llvm/test/Transforms/CallSiteSplitting/callsite-split.ll =================================================================== --- llvm/test/Transforms/CallSiteSplitting/callsite-split.ll +++ llvm/test/Transforms/CallSiteSplitting/callsite-split.ll @@ -10,9 +10,9 @@ ;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: call void @dummy2(%struct.bitmap* %a_elt) +;CHECK: br {{.*}} label %Cond.i +;CHECK-LABEL: Cond.i: +;CHECK-NEXT: call void @dummy2(%struct.bitmap* %a_elt) define void @caller(i1 %c, %struct.bitmap* %a_elt, %struct.bitmap* %b_elt) { entry: Index: llvm/test/Transforms/JumpThreading/PR33357-lvi-recursion.ll =================================================================== --- llvm/test/Transforms/JumpThreading/PR33357-lvi-recursion.ll +++ llvm/test/Transforms/JumpThreading/PR33357-lvi-recursion.ll @@ -1,14 +1,10 @@ ; RUN: opt -S -jump-threading -verify -o - %s | FileCheck %s +; This test checks that we dont infinitely recurse when a +; binary operator references itself. @a = external global i16, align 1 ; CHECK-LABEL: f -; CHECK: bb6: -; CHECK: bb2: -; CHECK: bb3: -; CHECK-NOT: bb0: -; CHECK-NOT: bb1: -; CHECK-NOT: bb4: -; CHECK-NOT: bb5: +; CHECK: [[OP:%.*]] = and i1 [[OP]], undef define void @f(i32 %p1) { bb0: %0 = icmp eq i32 %p1, 0 Index: llvm/test/Transforms/JumpThreading/implied-cond.ll =================================================================== --- llvm/test/Transforms/JumpThreading/implied-cond.ll +++ llvm/test/Transforms/JumpThreading/implied-cond.ll @@ -100,7 +100,7 @@ ; 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 Index: llvm/test/Transforms/JumpThreading/lvi-tristate.ll =================================================================== --- llvm/test/Transforms/JumpThreading/lvi-tristate.ll +++ llvm/test/Transforms/JumpThreading/lvi-tristate.ll @@ -7,8 +7,8 @@ ; CHECK-NEXT: bb: ; CHECK-NEXT: [[TMP:%.*]] = and i32 undef, 1073741823 ; CHECK-NEXT: [[COND:%.*]] = icmp eq i32 [[TMP]], 5 -; CHECK-NEXT: br i1 [[COND]], label [[BB10:%.*]], label [[BB13:%.*]] -; CHECK: bb10: +; CHECK-NEXT: br i1 [[COND]], label [[BB7_THREAD:%.*]], label [[BB13:%.*]] +; CHECK: bb7.thread: ; CHECK-NEXT: tail call void @ham() ; CHECK-NEXT: br label [[BB13]] ; CHECK: bb13: Index: llvm/test/Transforms/JumpThreading/pr22086.ll =================================================================== --- llvm/test/Transforms/JumpThreading/pr22086.ll +++ llvm/test/Transforms/JumpThreading/pr22086.ll @@ -1,13 +1,17 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py ; RUN: opt -S -jump-threading < %s | FileCheck %s -; CHECK-LABEL: @f( -; CHECK-LABEL: entry: -; CHECK-NEXT: br label %[[loop:.*]] -; CHECK: [[loop]]: -; CHECK-NEXT: br label %[[loop]] - define void @f() { +; CHECK-LABEL: @f( +; CHECK-NEXT: entry: +; CHECK-NEXT: br label [[LOR_RHS:%.*]] +; CHECK: lor.rhs: +; CHECK-NEXT: [[G_1:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ 0, [[LOR_RHS]] ] +; CHECK-NEXT: [[SEXT:%.*]] = shl i32 [[G_1]], 16 +; CHECK-NEXT: [[CONV20:%.*]] = ashr exact i32 [[SEXT]], 16 +; CHECK-NEXT: br label [[LOR_RHS]] +; entry: br label %for.cond1 Index: llvm/test/Transforms/JumpThreading/pr36133.ll =================================================================== --- llvm/test/Transforms/JumpThreading/pr36133.ll +++ llvm/test/Transforms/JumpThreading/pr36133.ll @@ -5,13 +5,14 @@ ; CHECK-LABEL: @foo ; CHECK-LABEL: bb: ; CHECK: icmp eq -; CHECK-NEXT: br i1 %tmp1, label %bb7, label %bb7 +; CHECK-NEXT: br i1 %tmp1, label %bb7, label %bb2 bb: %tmp = load i8*, i8** @global, align 8 %tmp1 = icmp eq i8* %tmp, null br i1 %tmp1, label %bb3, label %bb2 -; CHECK-NOT: bb2: +; CHECK: bb2: +; CHECK-NEXT: br label %bb7 bb2: br label %bb3 Index: llvm/test/Transforms/JumpThreading/pr40992-indirectbr-folding.ll =================================================================== --- llvm/test/Transforms/JumpThreading/pr40992-indirectbr-folding.ll +++ llvm/test/Transforms/JumpThreading/pr40992-indirectbr-folding.ll @@ -1,6 +1,6 @@ ; RUN: opt -S < %s -jump-threading | FileCheck %s -; PR40992: Do not incorrectly fold %bb5 into an unconditional br to %bb7. +; PR40992: Do not incorrectly fold %bb5 into an unconditional br to %bb7, bb6 is fine. ; Also verify we correctly thread %bb1 -> %bb7 when %c is false. define i32 @jtbr(i1 %v1, i1 %v2, i1 %v3) { @@ -17,7 +17,7 @@ ; CHECK: bb2: ; CHECK-NEXT: select -; CHECK-NEXT: indirectbr i8* %ba, [label %bb3, label %bb5] +; CHECK-NEXT: indirectbr i8* %ba, [label %bb3, label %bb6] bb2: %ba = select i1 %v3, i8* blockaddress(@jtbr, %bb3), i8* blockaddress(@jtbr, %bb4) indirectbr i8* %ba, [label %bb3, label %bb4] @@ -30,7 +30,7 @@ bb4: br label %bb5 -; CHECK: bb5: +; CHECK-NOT: bb5: bb5: br i1 %c, label %bb6, label %bb7 Index: llvm/test/Transforms/JumpThreading/pr46857-callbr.ll =================================================================== --- llvm/test/Transforms/JumpThreading/pr46857-callbr.ll +++ llvm/test/Transforms/JumpThreading/pr46857-callbr.ll @@ -7,8 +7,8 @@ ; CHECK-NEXT: br i1 [[ARG:%.*]], label [[BB7:%.*]], label [[BB4:%.*]] ; CHECK: bb4: ; CHECK-NEXT: callbr void asm sideeffect "", "!i"() -; CHECK-NEXT: to label [[BB7_THR_COMM:%.*]] [label %bb7.thr_comm] -; CHECK: bb7.thr_comm: +; CHECK-NEXT: to label [[BB6:%.*]] [label %bb6] +; CHECK: bb6: ; CHECK-NEXT: [[I91:%.*]] = xor i1 [[ARG2:%.*]], [[ARG]] ; CHECK-NEXT: br i1 [[I91]], label [[BB11:%.*]], label [[BB11]] ; CHECK: bb7: @@ -16,8 +16,8 @@ ; CHECK-NEXT: [[I9:%.*]] = xor i1 [[I]], [[ARG]] ; CHECK-NEXT: br i1 [[I9]], label [[BB11]], label [[BB11]] ; CHECK: bb11: -; CHECK-NEXT: [[I93:%.*]] = phi i1 [ [[I91]], [[BB7_THR_COMM]] ], [ [[I9]], [[BB7]] ], [ [[I91]], [[BB7_THR_COMM]] ], [ [[I9]], [[BB7]] ] -; CHECK-NEXT: ret i1 [[I93]] +; CHECK-NEXT: [[I92:%.*]] = phi i1 [ [[I91]], [[BB6]] ], [ [[I91]], [[BB6]] ], [ [[I9]], [[BB7]] ], [ [[I9]], [[BB7]] ] +; CHECK-NEXT: ret i1 [[I92]] ; bb: br i1 %arg, label %bb3, label %bb4 Index: llvm/test/Transforms/JumpThreading/select.ll =================================================================== --- llvm/test/Transforms/JumpThreading/select.ll +++ llvm/test/Transforms/JumpThreading/select.ll @@ -472,22 +472,22 @@ ; CHECK-NEXT: entry: ; CHECK-NEXT: [[ADD3:%.*]] = add nsw i32 [[J:%.*]], 2 ; CHECK-NEXT: [[CMP_I:%.*]] = icmp slt i32 [[U:%.*]], [[V:%.*]] -; CHECK-NEXT: br i1 [[CMP_I]], label [[DOTEXIT:%.*]], label [[COND_FALSE_I:%.*]] +; CHECK-NEXT: br i1 [[CMP_I]], label [[DOTEXIT_THREAD:%.*]], label [[COND_FALSE_I:%.*]] ; CHECK: cond.false.i: ; CHECK-NEXT: [[CMP4_I:%.*]] = icmp sgt i32 [[U]], [[V]] -; CHECK-NEXT: br i1 [[CMP4_I]], label [[DOTEXIT]], label [[COND_FALSE_6_I:%.*]] +; CHECK-NEXT: br i1 [[CMP4_I]], label [[DOTEXIT_THREAD]], label [[COND_FALSE_6_I:%.*]] ; CHECK: cond.false.6.i: ; CHECK-NEXT: [[CMP8_I:%.*]] = icmp slt i32 [[W:%.*]], [[X:%.*]] -; CHECK-NEXT: br i1 [[CMP8_I]], label [[DOTEXIT]], label [[COND_FALSE_10_I:%.*]] +; CHECK-NEXT: br i1 [[CMP8_I]], label [[DOTEXIT_THREAD]], label [[COND_FALSE_10_I:%.*]] ; CHECK: cond.false.10.i: ; CHECK-NEXT: [[CMP13_I:%.*]] = icmp sgt i32 [[W]], [[X]] -; CHECK-NEXT: br i1 [[CMP13_I]], label [[DOTEXIT]], label [[COND_FALSE_15_I:%.*]] +; CHECK-NEXT: br i1 [[CMP13_I]], label [[DOTEXIT_THREAD]], label [[COND_FALSE_15_I:%.*]] ; CHECK: cond.false.15.i: ; CHECK-NEXT: [[CMP19_I:%.*]] = icmp sge i32 [[Y:%.*]], [[Z:%.*]] ; CHECK-NEXT: [[CONV:%.*]] = zext i1 [[CMP19_I]] to i32 -; CHECK-NEXT: br label [[DOTEXIT]] -; CHECK: .exit: -; CHECK-NEXT: [[TMP0:%.*]] = phi i32 [ [[J]], [[COND_FALSE_10_I]] ], [ [[CONV]], [[COND_FALSE_15_I]] ], [ 1, [[COND_FALSE_6_I]] ], [ 3, [[COND_FALSE_I]] ], [ 2, [[ENTRY:%.*]] ] +; CHECK-NEXT: br label [[DOTEXIT_THREAD]] +; CHECK: .exit.thread: +; CHECK-NEXT: [[TMP0:%.*]] = phi i32 [ [[CONV]], [[COND_FALSE_15_I]] ], [ 1, [[COND_FALSE_6_I]] ], [ 3, [[COND_FALSE_I]] ], [ 2, [[ENTRY:%.*]] ], [ [[J]], [[COND_FALSE_10_I]] ] ; CHECK-NEXT: ret i32 [[TMP0]] ; entry: Index: llvm/test/Transforms/JumpThreading/static-profile.ll =================================================================== --- llvm/test/Transforms/JumpThreading/static-profile.ll +++ llvm/test/Transforms/JumpThreading/static-profile.ll @@ -89,22 +89,24 @@ eq_1: call void @bar() br label %check_2 -; Verify the new edge: -; CHECK: check_2.thread: -; 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 +; CHECK: check_2: ; No metadata: -; CHECK: br i1 %cond2, label %eq_2, label %check_3{{$}} +; CHECK: br i1 %cond2, label %check_3.thread, label %check_3{{$}} + +; Verify the new edge: +; CHECK: check_2.thread: +; CHECK-NEXT: call void @bar() +; CHECK-NEXT: br label %latch eq_2: call void @bar() br label %check_3 ; Verify the new edge: -; CHECK: eq_2: +; CHECK: check_3.thread: ; CHECK-NEXT: call void @bar() ; CHECK-NEXT: br label %latch Index: llvm/test/Transforms/JumpThreading/thread-loads.ll =================================================================== --- llvm/test/Transforms/JumpThreading/thread-loads.ll +++ llvm/test/Transforms/JumpThreading/thread-loads.ll @@ -111,10 +111,13 @@ ; CHECK-NEXT: [[TMP0:%.*]] = bitcast i8** [[X:%.*]] to i32** ; CHECK-NEXT: [[TMP1:%.*]] = load i32*, i32** [[TMP0]], align 8 ; CHECK-NEXT: [[TMP2:%.*]] = bitcast i32* [[TMP1]] to i8* -; CHECK-NEXT: br i1 [[F:%.*]], label [[IF_END57:%.*]], label [[IF_END57]] +; CHECK-NEXT: br i1 [[F:%.*]], label [[IF_END57:%.*]], label [[IF_THEN56:%.*]] +; CHECK: if.then56: +; CHECK-NEXT: [[TMP3:%.*]] = bitcast i32* [[TMP1]] to i8* +; CHECK-NEXT: br label [[IF_END57]] ; CHECK: if.end57: -; CHECK-NEXT: [[TMP3:%.*]] = phi i8* [ [[TMP2]], [[ENTRY:%.*]] ], [ [[TMP2]], [[ENTRY]] ] -; CHECK-NEXT: [[TOBOOL59:%.*]] = icmp eq i8* [[TMP3]], null +; CHECK-NEXT: [[TMP4:%.*]] = phi i8* [ [[TMP3]], [[IF_THEN56]] ], [ [[TMP2]], [[ENTRY:%.*]] ] +; CHECK-NEXT: [[TOBOOL59:%.*]] = icmp eq i8* [[TMP4]], null ; CHECK-NEXT: br i1 [[TOBOOL59]], label [[RETURN:%.*]], label [[IF_THEN60:%.*]] ; CHECK: if.then60: ; CHECK-NEXT: ret i32 42 @@ -683,7 +686,6 @@ } -; CHECK: [[RNG4]] = !{i32 0, i32 1} !0 = !{!3, !3, i64 0} !1 = !{!"omnipotent char", !2} Index: llvm/test/Transforms/JumpThreading/unreachable-loops.ll =================================================================== --- llvm/test/Transforms/JumpThreading/unreachable-loops.ll +++ llvm/test/Transforms/JumpThreading/unreachable-loops.ll @@ -100,10 +100,6 @@ ; CHECK-LABEL: @PR48362( ; CHECK-NEXT: cleanup.cont1500: ; CHECK-NEXT: unreachable -; CHECK: if.end1733: -; CHECK-NEXT: [[I82:%.*]] = load i32, i32* undef, align 1 -; CHECK-NEXT: [[TOBOOL1731_NOT:%.*]] = icmp eq i32 [[I82]], 0 -; CHECK-NEXT: br label [[IF_END1733:%.*]] ; cleanup1491: ; preds = %for.body1140 switch i32 0, label %cleanup2343.loopexit4 [