Index: llvm/include/llvm/Transforms/Scalar/JumpThreading.h =================================================================== --- llvm/include/llvm/Transforms/Scalar/JumpThreading.h +++ llvm/include/llvm/Transforms/Scalar/JumpThreading.h @@ -107,7 +107,7 @@ BPI.reset(); } - void FindLoopHeaders(Function &F); + bool FindLoopHeaders(Function &F); bool ProcessBlock(BasicBlock *BB); bool ThreadEdge(BasicBlock *BB, const SmallVectorImpl &PredBBs, BasicBlock *SuccBB); Index: llvm/lib/Transforms/Scalar/JumpThreading.cpp =================================================================== --- llvm/lib/Transforms/Scalar/JumpThreading.cpp +++ llvm/lib/Transforms/Scalar/JumpThreading.cpp @@ -363,14 +363,12 @@ SmallPtrSet Unreachable; assert(DTU && "DTU isn't passed into JumpThreading before using it."); assert(DTU->hasDomTree() && "JumpThreading relies on DomTree to proceed."); + bool EverChanged = FindLoopHeaders(F); DominatorTree &DT = DTU->getDomTree(); for (auto &BB : F) if (!DT.isReachableFromEntry(&BB)) Unreachable.insert(&BB); - FindLoopHeaders(F); - - bool EverChanged = false; bool Changed; do { Changed = false; @@ -540,12 +538,32 @@ /// within the loop (forming a nested loop). This simple analysis is not rich /// enough to track all of these properties and keep it up-to-date as the CFG /// mutates, so we don't allow any of these transformations. -void JumpThreadingPass::FindLoopHeaders(Function &F) { - SmallVector, 32> Edges; - FindFunctionBackedges(F, Edges); +bool JumpThreadingPass::FindLoopHeaders(Function &F) { + // FindFunctionBackedges() only examines the edges present in the IR and + // constant terminators can obscure the true loop headers of F. When + // JumpThreading eventually folds these terminators in ProcessBlock() it is + // non-trivial to re-run partial analysis to detect potentially new (correct) + // loop headers. We eliminate that issue here by converting all TIs that can + // be folded before detecting our loop headers. This also aids in removing + // dead code and potentially reducing the number of blocks we examine in the + // main JumpThreading loop. + bool Changed = false; + for (auto &BB : F) { + if (ConstantFoldTerminator(&BB, true, TLI, DTU)) { + Changed = true; + ++NumFolds; + LLVM_DEBUG(dbgs() << " FindLoopHeaders, in block '" << BB.getName() + << "' folded to new terminator: " << *BB.getTerminator() + << '\n'); + } + } + SmallVector, 32> Edges; + FindFunctionBackedges(F, Edges); for (const auto &Edge : Edges) LoopHeaders.insert(Edge.second); + + return Changed; } /// getKnownConstant - Helper method to determine if we can thread over a @@ -1100,11 +1118,16 @@ // other blocks. if (getKnownConstant(Condition, Preference)) { LLVM_DEBUG(dbgs() << " In block '" << BB->getName() - << "' folding terminator: " << *BB->getTerminator() + << "' trying to fold terminator: " << *BB->getTerminator() << '\n'); - ++NumFolds; - ConstantFoldTerminator(BB, true, nullptr, DTU); - return true; + if (ConstantFoldTerminator(BB, true, TLI, DTU)) { + ++NumFolds; + LLVM_DEBUG(dbgs() << " In block '" << BB->getName() + << "' folded to new terminator: " + << *BB->getTerminator() << '\n'); + return true; + } + return false; } Instruction *CondInst = dyn_cast(Condition); Index: llvm/test/Transforms/JumpThreading/pr15851_hang.ll =================================================================== --- llvm/test/Transforms/JumpThreading/pr15851_hang.ll +++ llvm/test/Transforms/JumpThreading/pr15851_hang.ll @@ -4,8 +4,8 @@ ; CHECK-LABEL: entry ; CHECK-NEXT: ret void ; -; JumpThreading must detect the next two blocks are unreachable from entry -; and leave them alone. A subsequent pass will remove them from @f. +; JumpThreading must detect the next two blocks are unreachable from entry. +; A subsequent pass will remove them from @f. ; ; CHECK: for.cond1: ; CHECK-NEXT: phi @@ -13,8 +13,7 @@ ; CHECK-NEXT: br i1 %cmp, label %for.body, label %for.cond1 ; CHECK: for.body: ; CHECK-NEXT: add -; CHECK-NEXT: icmp -; CHECK-NEXT: br i1 %a, label %for.cond1, label %for.cond1 +; CHECK-NEXT: br label %for.cond1 define void @f() { entry: Index: llvm/test/Transforms/JumpThreading/pr42085-loopheader-detection.ll =================================================================== --- /dev/null +++ llvm/test/Transforms/JumpThreading/pr42085-loopheader-detection.ll @@ -0,0 +1,46 @@ +; RUN: opt -S < %s -jump-threading | FileCheck %s +; PR42085: Do not thread any code in this example. +define i32 @test(i1 %ARG1, i1 %ARG2) { +; CHECK-NOT: {{.+}}.thread: +entry: + br label %pre_head + +pre_head: + %tmp = phi i32 [ 0, %entry ], [ %tmp10, %body1 ] + %tmp3 = phi i32 [ 0, %entry ], [ %tmp11, %body1 ] + %tmp4 = phi i32 [ 0, %entry ], [ %tmp11, %body1 ] + br label %head1 + +head1: + br i1 %ARG1, label %exit, label %head2 + +head2: + br i1 false, label %head3, label %body2 + +head3: + %tmp8 = add i32 %tmp3, 1 + br label %body1 + +body1: + %tmp10 = phi i32 [ %tmp, %head3 ], [ %tmp16, %latch2 ] + %tmp11 = phi i32 [ %tmp8, %head3 ], [ %tmp16, %latch2 ] + %tmp12 = icmp sgt i32 %tmp11, 1 + br i1 %tmp12, label %body2, label %pre_head + +body2: + %tmp14 = phi i32 [ %tmp10, %body1 ], [ %tmp, %head2 ] + %tmp15 = phi i32 [ %tmp11, %body1 ], [ %tmp3, %head2 ] + %tmp16 = add i32 %tmp14, 1 + br i1 %ARG2, label %exit, label %latch1 + +latch1: + %tmp18 = icmp sgt i32 %tmp16, 2 + br i1 %tmp18, label %exit, label %latch2 + +latch2: + br label %body1 + +exit: + %rc = phi i32 [ %tmp15, %body2 ], [ %tmp15, %latch1 ], [ -1, %head1 ] + ret i32 %rc +} Index: llvm/test/Transforms/JumpThreading/removed-use.ll =================================================================== --- llvm/test/Transforms/JumpThreading/removed-use.ll +++ llvm/test/Transforms/JumpThreading/removed-use.ll @@ -1,9 +1,9 @@ ; RUN: opt -S < %s -jump-threading | FileCheck %s ; CHECK-LABEL: @foo +; CHECK: entry: +; CHECK-NEXT: br label %bb6 ; CHECK: bb6: ; CHECK-NEXT: ret void -; CHECK: bb3: -; CHECK: br label %bb3 define void @foo() { entry: br i1 true, label %bb6, label %bb3 Index: llvm/test/Transforms/JumpThreading/select.ll =================================================================== --- llvm/test/Transforms/JumpThreading/select.ll +++ llvm/test/Transforms/JumpThreading/select.ll @@ -157,12 +157,12 @@ ; CHECK: test_switch_default ; CHECK: entry: ; CHECK: load -; CHECK: switch +; CHECK: br ; CHECK: [[THREADED:[A-Za-z.0-9]+]]: ; CHECK: store ; CHECK: br ; CHECK: L2: -; CHECK-SAME: preds = %entry, %entry +; CHECK-SAME: preds = %entry ; CHECK-NEXT: phi i32 define void @test_switch_default(i32* nocapture %status) nounwind { entry: