atmnpatel updated this revision to Diff 297069. atmnpatel added a comment. Herald added a project: clang. Herald added a subscriber: cfe-commits.
Fixes. Repository: rG LLVM Github Monorepo CHANGES SINCE LAST ACTION https://reviews.llvm.org/D86844/new/ https://reviews.llvm.org/D86844 Files: clang/test/Misc/loop-opt-setup.c llvm/include/llvm/Analysis/LoopInfo.h llvm/include/llvm/Analysis/LoopInfoImpl.h llvm/include/llvm/Transforms/Utils/LoopUtils.h llvm/lib/Transforms/Scalar/LoopDeletion.cpp llvm/lib/Transforms/Utils/LoopUtils.cpp llvm/test/Other/loop-deletion-printer.ll llvm/test/Other/loop-pm-invalidation.ll llvm/test/Transforms/LICM/2003-02-27-PreheaderProblem.ll llvm/test/Transforms/LoopDeletion/2017-07-11-incremental-dt.ll llvm/test/Transforms/LoopDeletion/basic-remark.ll llvm/test/Transforms/LoopDeletion/diundef.ll llvm/test/Transforms/LoopDeletion/invalidation.ll llvm/test/Transforms/LoopDeletion/multiple-exit-conditions.ll llvm/test/Transforms/LoopDeletion/multiple-exits.ll llvm/test/Transforms/LoopDeletion/mustprogress.ll llvm/test/Transforms/LoopDeletion/unreachable-loops.ll llvm/test/Transforms/LoopDeletion/use-in-unreachable.ll llvm/test/Transforms/SCCP/calltest.ll llvm/test/Transforms/SimpleLoopUnswitch/pr37888.ll
Index: llvm/test/Transforms/SimpleLoopUnswitch/pr37888.ll =================================================================== --- llvm/test/Transforms/SimpleLoopUnswitch/pr37888.ll +++ llvm/test/Transforms/SimpleLoopUnswitch/pr37888.ll @@ -7,7 +7,7 @@ target triple = "x86_64-unknown-linux-gnu" -define void @pr37888() { +define void @pr37888() willreturn { ; CHECK-LABEL: define void @pr37888() entry: %tobool = icmp ne i16 undef, 0 Index: llvm/test/Transforms/SCCP/calltest.ll =================================================================== --- llvm/test/Transforms/SCCP/calltest.ll +++ llvm/test/Transforms/SCCP/calltest.ll @@ -4,7 +4,7 @@ %empty = type {} declare %empty @has_side_effects() -define double @test_0(i32 %param) { +define double @test_0(i32 %param) willreturn { ; CHECK-LABEL: @test_0( ; CHECK-NOT: br entry: Index: llvm/test/Transforms/LoopDeletion/use-in-unreachable.ll =================================================================== --- llvm/test/Transforms/LoopDeletion/use-in-unreachable.ll +++ llvm/test/Transforms/LoopDeletion/use-in-unreachable.ll @@ -3,7 +3,7 @@ ; Checking that possible users of instruction from the loop in ; unreachable blocks are handled. -define i64 @foo() { +define i64 @foo() willreturn { entry: br label %invloop ; CHECK-LABEL-NOT: invloop Index: llvm/test/Transforms/LoopDeletion/unreachable-loops.ll =================================================================== --- llvm/test/Transforms/LoopDeletion/unreachable-loops.ll +++ llvm/test/Transforms/LoopDeletion/unreachable-loops.ll @@ -216,7 +216,7 @@ ; Show recursive deletion of loops. Since we start with subloops and progress outward ; to parent loop, we first delete the loop L2. Now loop L1 becomes a non-loop since it's backedge ; from L2's preheader to L1's exit block is never taken. So, L1 gets deleted as well. -define void @test8(i64 %n) { +define void @test8(i64 %n) #0 { ; CHECK-LABEL: test8 ; CHECK-LABEL: entry: ; CHECK-NEXT: br label %exit @@ -318,7 +318,7 @@ ; deleted. ; In the next iteration, since L2 is never executed and has no subloops, we delete ; L2 as well. Finally, the outermost loop L1 is deleted. -define void @test11(i64 %n) { +define void @test11(i64 %n) #0 { ; CHECK-LABEL: test11 ; CHECK-LABEL: entry: ; CHECK-NEXT: br label %exit @@ -355,7 +355,7 @@ ; 2 edges from a single exiting block to the exit block. -define i64 @test12(i64 %n){ +define i64 @test12(i64 %n) #0 { ;CHECK-LABEL: @test12 ; CHECK-NOT: L1: ; CHECK-NOT: L1Latch: @@ -392,7 +392,7 @@ } ; multiple edges to exit block from the same exiting blocks -define i64 @test13(i64 %n) { +define i64 @test13(i64 %n) #0 { ; CHECK-LABEL: @test13 ; CHECK-NOT: L1: ; CHECK-NOT: L1Latch: @@ -433,3 +433,5 @@ %y.phi = phi i64 [ 10, %L1Block ], [ 10, %L1Block ], [ %y.next, %L1 ], [ 30, %L1Latch ], [ 30, %L1Latch ] ret i64 %y.phi } + +attributes #0 = { willreturn } Index: llvm/test/Transforms/LoopDeletion/mustprogress.ll =================================================================== --- /dev/null +++ llvm/test/Transforms/LoopDeletion/mustprogress.ll @@ -0,0 +1,237 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --function-signature --check-attributes +; RUN: opt < %s -loop-deletion -S | FileCheck %s + +;; Original C Code: +;; void unknown_tripcount_mustprogress_attr_mustprogress_loopmd(int a, int b) { +;; for (; a < b;) ; +;; for (;;) ; +;; } + +define void @unknown_tripcount_mustprogress_attr_mustprogress_loopmd(i32 %a, i32 %b) #0 { +; CHECK: Function Attrs: mustprogress +; CHECK-LABEL: define {{[^@]+}}@unknown_tripcount_mustprogress_attr_mustprogress_loopmd +; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]]) [[ATTR0:#.*]] { +; CHECK-NEXT: entry: +; CHECK-NEXT: br label [[FOR_END:%.*]] +; CHECK: for.end: +; CHECK-NEXT: unreachable +; +entry: + br label %for.cond +for.cond: + %cmp = icmp slt i32 %a, %b + br i1 %cmp, label %for.body, label %for.end +for.body: + br label %for.cond, !llvm.loop !2 +for.end: + br label %for.cond1 +for.cond1: + br label %for.cond1 +} + +;; Original C Code: +;; void unknown_tripcount_mustprogress_attr_no_mustprogress_loopmd(int a, int b) { +;; for (; a < b;) ; +;; for (;;) ; +;; } +;; => Removed mustprogress loop attribute + +define void @unknown_tripcount_mustprogress_attr_no_mustprogess_loopmd(i32 %a, i32 %b) #0 { +; CHECK: Function Attrs: mustprogress +; CHECK-LABEL: define {{[^@]+}}@unknown_tripcount_mustprogress_attr_no_mustprogess_loopmd +; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]]) [[ATTR0]] { +; CHECK-NEXT: entry: +; CHECK-NEXT: br label [[FOR_END:%.*]] +; CHECK: for.end: +; CHECK-NEXT: unreachable +; +entry: + br label %for.cond +for.cond: + %cmp = icmp slt i32 %a, %b + br i1 %cmp, label %for.body, label %for.end +for.body: + br label %for.cond +for.end: + br label %for.cond1 +for.cond1: + br label %for.cond1 +} + +;; Original C Code: +;; void known_tripcount_no_mustprogress_attr_no_mustprogress_loopmd() { +;; for (int i = 0; i < 5; i++) ; +;; } + +define void @known_tripcount_no_mustprogress_attr_no_mustprogress_loopmd() { +; CHECK-LABEL: define {{[^@]+}}@known_tripcount_no_mustprogress_attr_no_mustprogress_loopmd() { +; CHECK-NEXT: entry: +; CHECK-NEXT: br label [[FOR_END:%.*]] +; CHECK: for.end: +; CHECK-NEXT: ret void +; +entry: + br label %for.cond +for.cond: + %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ] + %cmp = icmp slt i32 %i.0, 5 + br i1 %cmp, label %for.body, label %for.end +for.body: + br label %for.inc +for.inc: + %inc = add nsw i32 %i.0, 1 + br label %for.cond +for.end: + ret void +} + +;; Original C Code: +;; void known_tripcount_no_mustprogress_attr_mustprogress_loopmd() { +;; for (int i = 0; i < 5; i++) ; +;; } +;; => Added mustprogress loop attribute + +define void @known_tripcount_no_mustprogress_attr_mustprogress_loopmd() { +; CHECK-LABEL: define {{[^@]+}}@known_tripcount_no_mustprogress_attr_mustprogress_loopmd() { +; CHECK-NEXT: entry: +; CHECK-NEXT: br label [[FOR_END:%.*]] +; CHECK: for.end: +; CHECK-NEXT: ret void +; +entry: + br label %for.cond +for.cond: + %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ] + %cmp = icmp slt i32 %i.0, 5 + br i1 %cmp, label %for.body, label %for.end +for.body: + br label %for.inc +for.inc: + %inc = add nsw i32 %i.0, 1 + br label %for.cond, !llvm.loop !4 +for.end: + ret void +} + +;; Original C Code: +;; void known_tripcount_mustprogress_attr_no_mustprogress_loopmd() { +;; for (int i = 0; i < 5; i++) ; +;; } +;; => Added mustprogress function attribute + +define void @known_tripcount_mustprogress_attr_no_mustprogress_loopmd() #0 { +; CHECK: Function Attrs: mustprogress +; CHECK-LABEL: define {{[^@]+}}@known_tripcount_mustprogress_attr_no_mustprogress_loopmd +; CHECK-SAME: () [[ATTR0]] { +; CHECK-NEXT: entry: +; CHECK-NEXT: br label [[FOR_END:%.*]] +; CHECK: for.end: +; CHECK-NEXT: ret void +; +entry: + br label %for.cond +for.cond: + %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ] + %cmp = icmp slt i32 %i.0, 5 + br i1 %cmp, label %for.body, label %for.end +for.body: + br label %for.inc +for.inc: + %inc = add nsw i32 %i.0, 1 + br label %for.cond +for.end: + ret void +} + +;; Original C Code: +;; void known_tripcount_mustprogress_attr_mustprogress_loopmd() { +;; for (int i = 0; i < 5; i++) ; +;; } +;; => Added mustprogress function and mustprogress loop attribute + +define void @known_tripcount_mustprogress_attr_mustprogress_loopmd() #0 { +; CHECK: Function Attrs: mustprogress +; CHECK-LABEL: define {{[^@]+}}@known_tripcount_mustprogress_attr_mustprogress_loopmd +; CHECK-SAME: () [[ATTR0]] { +; CHECK-NEXT: entry: +; CHECK-NEXT: br label [[FOR_END:%.*]] +; CHECK: for.end: +; CHECK-NEXT: ret void +; +entry: + br label %for.cond +for.cond: + %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ] + %cmp = icmp slt i32 %i.0, 5 + br i1 %cmp, label %for.body, label %for.end +for.body: + br label %for.inc +for.inc: + %inc = add nsw i32 %i.0, 1 + br label %for.cond, !llvm.loop !5 +for.end: + ret void +} + +;; Original C Code: +;; void unknown_tripcount_no_mustprogress_attr_mustprogress_loopmd(int a, int b) { +;; for (; a < b;) ; +;; } +;; => Added mustprogress loop attribute + +define void @unknown_tripcount_no_mustprogress_attr_mustprogress_loopmd(i32 %a, i32 %b) { +; CHECK-LABEL: define {{[^@]+}}@unknown_tripcount_no_mustprogress_attr_mustprogress_loopmd +; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]]) { +; CHECK-NEXT: entry: +; CHECK-NEXT: br label [[FOR_END:%.*]] +; CHECK: for.end: +; CHECK-NEXT: ret void +; +entry: + br label %for.cond +for.cond: + %cmp = icmp slt i32 %a, %b + br i1 %cmp, label %for.body, label %for.end +for.body: + br label %for.cond, !llvm.loop !6 +for.end: + ret void +} + +;; Original C Code: +;; void unknown_tripcount_no_mustprogress_attr_no_mustprogress_loopmd(int a, int b) { +;; for (; a < b;) ; +;; } + +define void @unknown_tripcount_no_mustprogress_attr_no_mustprogress_loopmd(i32 %a, i32 %b) { +; CHECK-LABEL: define {{[^@]+}}@unknown_tripcount_no_mustprogress_attr_no_mustprogress_loopmd +; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]]) { +; CHECK-NEXT: entry: +; CHECK-NEXT: br label [[FOR_COND:%.*]] +; CHECK: for.cond: +; CHECK-NEXT: [[CMP:%.*]] = icmp slt i32 [[A]], [[B]] +; CHECK-NEXT: br i1 [[CMP]], label [[FOR_BODY:%.*]], label [[FOR_END:%.*]] +; CHECK: for.body: +; CHECK-NEXT: br label [[FOR_COND]] +; CHECK: for.end: +; CHECK-NEXT: ret void +; +entry: + br label %for.cond +for.cond: + %cmp = icmp slt i32 %a, %b + br i1 %cmp, label %for.body, label %for.end +for.body: + br label %for.cond +for.end: + ret void +} + +; CHECK: attributes [[ATTR0]] = { mustprogress } + +attributes #0 = { mustprogress } +!2 = distinct !{!2, !3} +!3 = !{!"llvm.loop.mustprogress"} +!4 = distinct !{!4, !3} +!5 = distinct !{!5, !3} +!6 = distinct !{!6, !3} Index: llvm/test/Transforms/LoopDeletion/multiple-exits.ll =================================================================== --- llvm/test/Transforms/LoopDeletion/multiple-exits.ll +++ llvm/test/Transforms/LoopDeletion/multiple-exits.ll @@ -10,7 +10,7 @@ ; RUN: opt < %s -passes=loop-deletion -S | FileCheck %s --check-prefixes=CHECK,AFTER -define void @foo(i64 %n, i64 %m) nounwind { +define void @foo(i64 %n, i64 %m) #0 { ; CHECK-LABEL: @foo( entry: @@ -43,7 +43,7 @@ ; CHECK-NEXT: ret void } -define i64 @bar(i64 %n, i64 %m, i64 %maybe_zero) nounwind { +define i64 @bar(i64 %n, i64 %m, i64 %maybe_zero) #0 { ; CHECK-LABEL: @bar( entry: @@ -95,7 +95,7 @@ ; This function has a loop which looks like @bar's but that cannot be deleted ; because which path we exit through determines which value is selected. -define i64 @baz(i64 %n, i64 %m, i64 %maybe_zero) nounwind { +define i64 @baz(i64 %n, i64 %m, i64 %maybe_zero) #0 { ; CHECK-LABEL: @baz( entry: @@ -136,3 +136,5 @@ ; CHECK-NEXT: %[[X:.*]] = phi i64 [ 12, %bb ], [ 10, %bb2 ], [ 10, %bb3 ] ; CHECK-NEXT: ret i64 %[[X]] } + +attributes #0 = { nounwind willreturn } \ No newline at end of file Index: llvm/test/Transforms/LoopDeletion/multiple-exit-conditions.ll =================================================================== --- llvm/test/Transforms/LoopDeletion/multiple-exit-conditions.ll +++ llvm/test/Transforms/LoopDeletion/multiple-exit-conditions.ll @@ -11,7 +11,7 @@ ; CHECK: return: ; CHECK-NEXT: ret void -define void @foo(i64 %n, i64 %m) nounwind { +define void @foo(i64 %n, i64 %m) nounwind willreturn { entry: br label %bb Index: llvm/test/Transforms/LoopDeletion/invalidation.ll =================================================================== --- llvm/test/Transforms/LoopDeletion/invalidation.ll +++ llvm/test/Transforms/LoopDeletion/invalidation.ll @@ -8,7 +8,7 @@ ; RUN: | FileCheck %s --check-prefixes=CHECK,AFTER -define void @foo(i64 %n, i64 %m) nounwind { +define void @foo(i64 %n, i64 %m) nounwind willreturn { ; CHECK-LABEL: @foo( entry: Index: llvm/test/Transforms/LoopDeletion/diundef.ll =================================================================== --- llvm/test/Transforms/LoopDeletion/diundef.ll +++ llvm/test/Transforms/LoopDeletion/diundef.ll @@ -5,7 +5,7 @@ @a = common local_unnamed_addr global i32 0, align 4, !dbg !0 -define i32 @b() local_unnamed_addr !dbg !12 { +define i32 @b() local_unnamed_addr willreturn !dbg !12 { entry: call void @llvm.dbg.value(metadata i32 0, metadata !16, metadata !DIExpression()), !dbg !17 br label %for.cond, !dbg !18 Index: llvm/test/Transforms/LoopDeletion/basic-remark.ll =================================================================== --- llvm/test/Transforms/LoopDeletion/basic-remark.ll +++ llvm/test/Transforms/LoopDeletion/basic-remark.ll @@ -10,7 +10,7 @@ ; CHECK-NEXT: Args: ; CHECK-NEXT: - String: Loop deleted because it is invariant ; CHECK-NEXT: ... -define i32 @main() local_unnamed_addr #0 { +define i32 @main() local_unnamed_addr willreturn { entry: br label %for.cond, !dbg !9 Index: llvm/test/Transforms/LoopDeletion/2017-07-11-incremental-dt.ll =================================================================== --- llvm/test/Transforms/LoopDeletion/2017-07-11-incremental-dt.ll +++ llvm/test/Transforms/LoopDeletion/2017-07-11-incremental-dt.ll @@ -14,7 +14,7 @@ ; DT: [3] %for.body ; DT: [4] %for.cond3.loopexit -define i32 @fn1() { +define i32 @fn1() willreturn { entry: br label %for.cond Index: llvm/test/Transforms/LICM/2003-02-27-PreheaderProblem.ll =================================================================== --- llvm/test/Transforms/LICM/2003-02-27-PreheaderProblem.ll +++ llvm/test/Transforms/LICM/2003-02-27-PreheaderProblem.ll @@ -6,7 +6,7 @@ ; RUN: opt < %s -licm -loop-deletion -simplifycfg -S | \ ; RUN: not grep "br " -define i32 @main(i32 %argc) { +define i32 @main(i32 %argc) willreturn { ; <label>:0 br label %bb5 bb5: ; preds = %bb5, %0 Index: llvm/test/Other/loop-pm-invalidation.ll =================================================================== --- llvm/test/Other/loop-pm-invalidation.ll +++ llvm/test/Other/loop-pm-invalidation.ll @@ -227,7 +227,7 @@ ret void } -define void @dead_loop() { +define void @dead_loop() willreturn { ; CHECK-LOOP-INV: Starting {{.*}}Function pass manager run ; CHECK-LOOP-INV-NEXT: Starting {{.*}}Function pass manager run ; CHECK-LOOP-INV-NEXT: Running pass: LoopSimplifyPass Index: llvm/test/Other/loop-deletion-printer.ll =================================================================== --- llvm/test/Other/loop-deletion-printer.ll +++ llvm/test/Other/loop-deletion-printer.ll @@ -14,7 +14,7 @@ ; DELETED-BUT-PRINTED: IR Dump {{.*}}LoopDeletionPass {{.*invalidated:}} ; DELETED-BUT-PRINTED-NOT: IR Dump {{.*}}LoopInstSimplifyPass -define void @deleteme() { +define void @deleteme() willreturn { entry: br label %loop loop: Index: llvm/lib/Transforms/Utils/LoopUtils.cpp =================================================================== --- llvm/lib/Transforms/Utils/LoopUtils.cpp +++ llvm/lib/Transforms/Utils/LoopUtils.cpp @@ -63,6 +63,7 @@ static const char *LLVMLoopDisableNonforced = "llvm.loop.disable_nonforced"; static const char *LLVMLoopDisableLICM = "llvm.licm.disable"; +static const char *LLVMLoopMustProgress = "llvm.loop.mustprogress"; bool llvm::formDedicatedExitBlocks(Loop *L, DominatorTree *DT, LoopInfo *LI, MemorySSAUpdater *MSSAU, @@ -404,6 +405,10 @@ return getBooleanLoopAttribute(L, LLVMLoopDisableLICM); } +bool llvm::hasMustProgress(const Loop *L) { + return getBooleanLoopAttribute(L, LLVMLoopMustProgress); +} + TransformationMode llvm::hasUnrollTransformation(Loop *L) { if (getBooleanLoopAttribute(L, "llvm.loop.unroll.disable")) return TM_SuppressedByUser; @@ -542,10 +547,6 @@ if (SE) SE->forgetLoop(L); - auto *ExitBlock = L->getUniqueExitBlock(); - assert(ExitBlock && "Should have a unique exit block!"); - assert(L->hasDedicatedExits() && "Loop should have dedicated exits!"); - auto *OldBr = dyn_cast<BranchInst>(Preheader->getTerminator()); assert(OldBr && "Preheader must end with a branch"); assert(OldBr->isUnconditional() && "Preheader must have a single successor"); @@ -575,59 +576,73 @@ // deleting the backedge of the outer loop). If the outer loop is indeed a // non-loop, it will be deleted in a future iteration of loop deletion pass. IRBuilder<> Builder(OldBr); - Builder.CreateCondBr(Builder.getFalse(), L->getHeader(), ExitBlock); - // Remove the old branch. The conditional branch becomes a new terminator. - OldBr->eraseFromParent(); - - // Rewrite phis in the exit block to get their inputs from the Preheader - // instead of the exiting block. - for (PHINode &P : ExitBlock->phis()) { - // Set the zero'th element of Phi to be from the preheader and remove all - // other incoming values. Given the loop has dedicated exits, all other - // incoming values must be from the exiting blocks. - int PredIndex = 0; - P.setIncomingBlock(PredIndex, Preheader); - // Removes all incoming values from all other exiting blocks (including - // duplicate values from an exiting block). - // Nuke all entries except the zero'th entry which is the preheader entry. - // NOTE! We need to remove Incoming Values in the reverse order as done - // below, to keep the indices valid for deletion (removeIncomingValues - // updates getNumIncomingValues and shifts all values down into the operand - // being deleted). - for (unsigned i = 0, e = P.getNumIncomingValues() - 1; i != e; ++i) - P.removeIncomingValue(e - i, false); - - assert((P.getNumIncomingValues() == 1 && - P.getIncomingBlock(PredIndex) == Preheader) && - "Should have exactly one value and that's from the preheader!"); - } - DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager); - if (DT) { - DTU.applyUpdates({{DominatorTree::Insert, Preheader, ExitBlock}}); - if (MSSA) { - MSSAU->applyUpdates({{DominatorTree::Insert, Preheader, ExitBlock}}, *DT); - if (VerifyMemorySSA) - MSSA->verifyMemorySSA(); + auto *ExitBlock = L->getUniqueExitBlock(); + if (L->getNumExitBlocks() == 0) { + // If this loop does not have an exit block, we can still remove the loop + // and replace the Preheader with an Unreachable. + Builder.SetInsertPoint(OldBr); + Builder.CreateUnreachable(); + Preheader->getTerminator()->eraseFromParent(); + } else { + assert(ExitBlock && "Should have a unique exit block!"); + assert(L->hasDedicatedExits() && "Loop should have dedicated exits!"); + + Builder.CreateCondBr(Builder.getFalse(), L->getHeader(), ExitBlock); + // Remove the old branch. The conditional branch becomes a new terminator. + OldBr->eraseFromParent(); + + // Rewrite phis in the exit block to get their inputs from the Preheader + // instead of the exiting block. + for (PHINode &P : ExitBlock->phis()) { + // Set the zero'th element of Phi to be from the preheader and remove all + // other incoming values. Given the loop has dedicated exits, all other + // incoming values must be from the exiting blocks. + int PredIndex = 0; + P.setIncomingBlock(PredIndex, Preheader); + // Removes all incoming values from all other exiting blocks (including + // duplicate values from an exiting block). + // Nuke all entries except the zero'th entry which is the preheader entry. + // NOTE! We need to remove Incoming Values in the reverse order as done + // below, to keep the indices valid for deletion (removeIncomingValues + // updates getNumIncomingValues and shifts all values down into the + // operand being deleted). + for (unsigned i = 0, e = P.getNumIncomingValues() - 1; i != e; ++i) + P.removeIncomingValue(e - i, false); + + assert((P.getNumIncomingValues() == 1 && + P.getIncomingBlock(PredIndex) == Preheader) && + "Should have exactly one value and that's from the preheader!"); + } + + DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager); + if (DT) { + DTU.applyUpdates({{DominatorTree::Insert, Preheader, ExitBlock}}); + if (MSSA) { + MSSAU->applyUpdates({{DominatorTree::Insert, Preheader, ExitBlock}}, + *DT); + if (VerifyMemorySSA) + MSSA->verifyMemorySSA(); + } } - } - // Disconnect the loop body by branching directly to its exit. - Builder.SetInsertPoint(Preheader->getTerminator()); - Builder.CreateBr(ExitBlock); - // Remove the old branch. - Preheader->getTerminator()->eraseFromParent(); - - if (DT) { - DTU.applyUpdates({{DominatorTree::Delete, Preheader, L->getHeader()}}); - if (MSSA) { - MSSAU->applyUpdates({{DominatorTree::Delete, Preheader, L->getHeader()}}, - *DT); - SmallSetVector<BasicBlock *, 8> DeadBlockSet(L->block_begin(), - L->block_end()); - MSSAU->removeBlocks(DeadBlockSet); - if (VerifyMemorySSA) - MSSA->verifyMemorySSA(); + // Disconnect the loop body by branching directly to its exit. + Builder.SetInsertPoint(Preheader->getTerminator()); + Builder.CreateBr(ExitBlock); + // Remove the old branch. + Preheader->getTerminator()->eraseFromParent(); + + if (DT) { + DTU.applyUpdates({{DominatorTree::Delete, Preheader, L->getHeader()}}); + if (MSSA) { + MSSAU->applyUpdates( + {{DominatorTree::Delete, Preheader, L->getHeader()}}, *DT); + SmallSetVector<BasicBlock *, 8> DeadBlockSet(L->block_begin(), + L->block_end()); + MSSAU->removeBlocks(DeadBlockSet); + if (VerifyMemorySSA) + MSSA->verifyMemorySSA(); + } } } @@ -674,15 +689,17 @@ // Since debug values in the loop have been deleted, inserting an undef // dbg.value truncates the range of any dbg.value before the loop where the // loop used to be. This is particularly important for constant values. - DIBuilder DIB(*ExitBlock->getModule()); - Instruction *InsertDbgValueBefore = ExitBlock->getFirstNonPHI(); - assert(InsertDbgValueBefore && - "There should be a non-PHI instruction in exit block, else these " - "instructions will have no parent."); - for (auto *DVI : DeadDebugInst) - DIB.insertDbgValueIntrinsic(UndefValue::get(Builder.getInt32Ty()), - DVI->getVariable(), DVI->getExpression(), - DVI->getDebugLoc(), InsertDbgValueBefore); + if (ExitBlock) { + DIBuilder DIB(*ExitBlock->getModule()); + Instruction *InsertDbgValueBefore = ExitBlock->getFirstNonPHI(); + assert(InsertDbgValueBefore && + "There should be a non-PHI instruction in exit block, else these " + "instructions will have no parent."); + for (auto *DVI : DeadDebugInst) + DIB.insertDbgValueIntrinsic(UndefValue::get(Builder.getInt32Ty()), + DVI->getVariable(), DVI->getExpression(), + DVI->getDebugLoc(), InsertDbgValueBefore); + } // Remove the block from the reference counting scheme, so that we can // delete it freely later. Index: llvm/lib/Transforms/Scalar/LoopDeletion.cpp =================================================================== --- llvm/lib/Transforms/Scalar/LoopDeletion.cpp +++ llvm/lib/Transforms/Scalar/LoopDeletion.cpp @@ -53,26 +53,28 @@ // of the loop. bool AllEntriesInvariant = true; bool AllOutgoingValuesSame = true; - for (PHINode &P : ExitBlock->phis()) { - Value *incoming = P.getIncomingValueForBlock(ExitingBlocks[0]); - - // Make sure all exiting blocks produce the same incoming value for the exit - // block. If there are different incoming values for different exiting - // blocks, then it is impossible to statically determine which value should - // be used. - AllOutgoingValuesSame = - all_of(makeArrayRef(ExitingBlocks).slice(1), [&](BasicBlock *BB) { - return incoming == P.getIncomingValueForBlock(BB); - }); - - if (!AllOutgoingValuesSame) - break; - - if (Instruction *I = dyn_cast<Instruction>(incoming)) - if (!L->makeLoopInvariant(I, Changed, Preheader->getTerminator())) { - AllEntriesInvariant = false; + if (L->getNumExitBlocks() != 0) { + for (PHINode &P : ExitBlock->phis()) { + Value *incoming = P.getIncomingValueForBlock(ExitingBlocks[0]); + + // Make sure all exiting blocks produce the same incoming value for the + // exit block. If there are different incoming values for different + // exiting blocks, then it is impossible to statically determine which + // value should be used. + AllOutgoingValuesSame = + all_of(makeArrayRef(ExitingBlocks).slice(1), [&](BasicBlock *BB) { + return incoming == P.getIncomingValueForBlock(BB); + }); + + if (!AllOutgoingValuesSame) break; - } + + if (Instruction *I = dyn_cast<Instruction>(incoming)) + if (!L->makeLoopInvariant(I, Changed, Preheader->getTerminator())) { + AllEntriesInvariant = false; + break; + } + } } if (Changed) @@ -193,7 +195,7 @@ // be in the situation of needing to be able to solve statically which exit // block will be branched to, or trying to preserve the branching logic in // a loop invariant manner. - if (!ExitBlock) { + if (!ExitBlock && L->getNumExitBlocks() != 0) { LLVM_DEBUG(dbgs() << "Deletion requires single exit block\n"); return LoopDeletionResult::Unmodified; } @@ -208,8 +210,10 @@ // Don't remove loops for which we can't solve the trip count. // They could be infinite, in which case we'd be changing program behavior. const SCEV *S = SE.getConstantMaxBackedgeTakenCount(L); - if (isa<SCEVCouldNotCompute>(S)) { - LLVM_DEBUG(dbgs() << "Could not compute SCEV MaxBackedgeTakenCount.\n"); + if (isa<SCEVCouldNotCompute>(S) && + !L->getHeader()->getParent()->mustProgress() && !hasMustProgress(L)) { + LLVM_DEBUG(dbgs() << "Could not compute SCEV MaxBackedgeTakenCount and was " + "not required to make progress.\n"); return Changed ? LoopDeletionResult::Modified : LoopDeletionResult::Unmodified; } Index: llvm/include/llvm/Transforms/Utils/LoopUtils.h =================================================================== --- llvm/include/llvm/Transforms/Utils/LoopUtils.h +++ llvm/include/llvm/Transforms/Utils/LoopUtils.h @@ -229,6 +229,9 @@ /// Look for the loop attribute that disables the LICM transformation heuristics. bool hasDisableLICMTransformsHint(const Loop *L); +/// Look for the loop attribute that requires progress within the loop. +bool hasMustProgress(const Loop *L); + /// The mode sets how eager a transformation should be applied. enum TransformationMode { /// The pass can use heuristics to determine whether a transformation should Index: llvm/include/llvm/Analysis/LoopInfoImpl.h =================================================================== --- llvm/include/llvm/Analysis/LoopInfoImpl.h +++ llvm/include/llvm/Analysis/LoopInfoImpl.h @@ -135,6 +135,13 @@ return nullptr; } +template <class BlockT, class LoopT> +unsigned LoopBase<BlockT, LoopT>::getNumExitBlocks() const { + SmallVector<BlockT *, 8> UniqueExitBlocks; + getUniqueExitBlocks(UniqueExitBlocks); + return UniqueExitBlocks.size(); +} + /// getExitEdges - Return all pairs of (_inside_block_,_outside_block_). template <class BlockT, class LoopT> void LoopBase<BlockT, LoopT>::getExitEdges( Index: llvm/include/llvm/Analysis/LoopInfo.h =================================================================== --- llvm/include/llvm/Analysis/LoopInfo.h +++ llvm/include/llvm/Analysis/LoopInfo.h @@ -302,6 +302,8 @@ /// Otherwise return null. BlockT *getUniqueExitBlock() const; + unsigned getNumExitBlocks() const; + /// Edge type. typedef std::pair<BlockT *, BlockT *> Edge; Index: clang/test/Misc/loop-opt-setup.c =================================================================== --- clang/test/Misc/loop-opt-setup.c +++ clang/test/Misc/loop-opt-setup.c @@ -23,8 +23,8 @@ --num_active; } -// Check br i1 to make sure the loop is gone, there will still be a label branch for the infinite loop. +// Check br i1 to make sure the loop is gone, there will be no loop here. // CHECK-LABEL: Helper -// CHECK: br label +// CHECK: entry: // CHECK-NOT: br i1 -// CHECK: br label +// CHECK-NEXT: ret void
_______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits