Index: lib/Transforms/Utils/LoopUtils.cpp =================================================================== --- lib/Transforms/Utils/LoopUtils.cpp +++ lib/Transforms/Utils/LoopUtils.cpp @@ -55,18 +55,24 @@ auto Cleanup = make_scope_exit([&] { InLoopPredecessors.clear(); }); // See if there are any non-loop predecessors of this exit block and - // keep track of the in-loop predecessors. + // keep track of the unique in-loop predecessors. bool IsDedicatedExit = true; + SmallPtrSet PushedBlocks; for (auto *PredBB : predecessors(BB)) if (L->contains(PredBB)) { if (isa(PredBB->getTerminator())) // We cannot rewrite exiting edges from an indirectbr. return false; - InLoopPredecessors.push_back(PredBB); + // Switch-like insts may have duplicate edges. + if (!PushedBlocks.count(PredBB)) { + InLoopPredecessors.push_back(PredBB); + PushedBlocks.insert(PredBB); + } } else { IsDedicatedExit = false; } + PushedBlocks.clear(); assert(!InLoopPredecessors.empty() && "Must have *some* loop predecessor!"); @@ -74,9 +80,41 @@ if (IsDedicatedExit) return false; + // With nested loops, the inner loop might exit to the header of an + // enclosing loop, and the in-loop-predecessor is a latch for that + // enclosing loop. If we insert a block between the latch and the header, + // that block becomes the new latch. Any loop metadata from the old latch + // needs to be moved to the new one. + MDNode *OuterLoopMD = nullptr; + + // If the exit block is a header of a different loop, get that loop's + // metadata before we split the block. + if (LI->isLoopHeader(BB)) + OuterLoopMD = LI->getLoopFor(BB)->getLoopID(); + auto *NewExitBB = SplitBlockPredecessors( BB, InLoopPredecessors, ".loopexit", DT, LI, nullptr, PreserveLCSSA); + // If OuterLoopMD is non-null, we know that the exit block BB is a + // loop header for a different loop, with metadata on its back edges. + // If NewExitBB is a member of that loop, then NewExitBB is a latch, + // and the loop's metadata needs to be copied to NewExitBB. + if (NewExitBB && OuterLoopMD && + LI->getLoopFor(NewExitBB) == LI->getLoopFor(BB)) { + // The preds of NewExitBB are all former latches of the outer loop. + // Remove their metadata. + for (auto *PredLoopBB : InLoopPredecessors) { + Instruction *TI = PredLoopBB->getTerminator(); + // All the latches should have the same metadata (ensured by + // getLoopID()). + assert(TI->getMetadata(LLVMContext::MD_loop) == OuterLoopMD && + "exit edge to other loop doesn't contain expected metadata"); + TI->setMetadata(LLVMContext::MD_loop, nullptr); + } + NewExitBB->getTerminator()->setMetadata(LLVMContext::MD_loop, + OuterLoopMD); + } + if (!NewExitBB) LLVM_DEBUG( dbgs() << "WARNING: Can't create a dedicated exit block for loop: " Index: test/Transforms/LoopSimplify/preserve-llvm-loop-metadata2.ll =================================================================== --- /dev/null +++ test/Transforms/LoopSimplify/preserve-llvm-loop-metadata2.ll @@ -0,0 +1,48 @@ +; RUN: opt -S -loop-simplify < %s | FileCheck %s + +; Two-loop nest with llvm.loop metadata on each loop. +; inner.header exits to outer.header. inner.header is a latch for the outer +; loop, and contains the outer loop's metadata. +; After loop-simplify, a new block "outer.header.loopexit" is created between +; inner.header and outer.header. The metadata from inner.header must be moved +; to the new block, as the new block becomes the outer loop latch. +; The metadata on the inner loop's latch should be untouched. + +; CHECK: outer.header.loopexit: +; CHECK-NEXT: llvm.loop [[UJAMTAG:.*]] +; CHECK-NOT: br i1 {{.*}}, label {{.*}}, label %outer.header.loopexit, !llvm.loop +; CHECK: br label %inner.header, !llvm.loop [[UNROLLTAG:.*]] + +; CHECK: distinct !{[[UJAMTAG]], [[UJAM:.*]]} +; CHECK: [[UJAM]] = !{!"llvm.loop.unroll_and_jam.count", i32 17} +; CHECK: distinct !{[[UNROLLTAG]], [[UNROLL:.*]]} +; CHECK: [[UNROLL]] = !{!"llvm.loop.unroll.count", i32 1} + + +define dso_local void @loopnest() local_unnamed_addr #0 { +entry: + br label %outer.header + +outer.header: ; preds = %inner.header, %entry + %ii.0 = phi i64 [ 2, %entry ], [ %add, %inner.header ] + %cmp = icmp ult i64 %ii.0, 64 + br i1 %cmp, label %inner.header, label %outer.header.cleanup + +outer.header.cleanup: ; preds = %outer.header + ret void + +inner.header: ; preds = %outer.header, %inner.body + %j.0 = phi i64 [ %add10, %inner.body ], [ %ii.0, %outer.header ] + %add = add nuw nsw i64 %ii.0, 16 + %cmp2 = icmp ult i64 %j.0, %add + br i1 %cmp2, label %inner.body, label %outer.header, !llvm.loop !2 + +inner.body: ; preds = %inner.header + %add10 = add nuw nsw i64 %j.0, 1 + br label %inner.header, !llvm.loop !4 +} + +!2 = distinct !{!2, !3} +!3 = !{!"llvm.loop.unroll_and_jam.count", i32 17} +!4 = distinct !{!4, !5} +!5 = !{!"llvm.loop.unroll.count", i32 1} Index: test/Transforms/LoopSimplify/preserve-llvm-loop-metadata3.ll =================================================================== --- /dev/null +++ test/Transforms/LoopSimplify/preserve-llvm-loop-metadata3.ll @@ -0,0 +1,58 @@ +; RUN: opt -S -loop-simplify < %s | FileCheck %s + +; Two-loop nest with llvm.loop metadata on each loop. +; inner.header exits to outer.header. inner.header is a latch for the outer +; loop, and contains the outer loop's metadata. +; The latch contains a switch instruction with duplicate edges. +; After loop-simplify, a new block "outer.header.loopexit" is created between +; inner.header and outer.header. Both exit paths from the switch need +; to be changed to point to the new exit block. +; The metadata from inner.header must be moved to the new block, as +; the new block becomes the outer loop latch. +; The metadata on the inner loop's latch should be untouched. + +; CHECK: outer.header.loopexit: +; CHECK-NEXT: llvm.loop [[UJAMTAG:.*]] +; CHECK: switch {{.*}}, label %inner.body [ +; CHECK-NEXT: i64 0, label %outer.header.loopexit +; CHECK-NEXT: i64 1, label %outer.header.loopexit +; CHECK-NOT: ], !llvm.loop +; CHECK: br label %inner.header, !llvm.loop [[UNROLLTAG:.*]] + +; CHECK: distinct !{[[UJAMTAG]], [[UJAM:.*]]} +; CHECK: [[UJAM]] = !{!"llvm.loop.unroll_and_jam.count", i32 17} +; CHECK: distinct !{[[UNROLLTAG]], [[UNROLL:.*]]} +; CHECK: [[UNROLL]] = !{!"llvm.loop.unroll.count", i32 1} + + +define dso_local void @loopnest() local_unnamed_addr #0 { +entry: + br label %outer.header + +outer.header: ; preds = %entry, %inner.header, %inner.header + %ii.0 = phi i64 [ 0, %entry ], [ %add, %inner.header ], [ %add, %inner.header ] + %cmp = icmp ult i64 %ii.0, 64 + br i1 %cmp, label %inner.header, label %outer.header.cleanup + +outer.header.cleanup: ; preds = %outer.header + ret void + +inner.header: ; preds = %outer.header, %inner.body + %j.0 = phi i64 [ %add10, %inner.body ], [ %ii.0, %outer.header ] + %add = add nuw nsw i64 %ii.0, 16 + %sub = sub i64 %add, %j.0 +; corner case: latch to outer loop is switch with duplicate edges + switch i64 %sub, label %inner.body [ + i64 0, label %outer.header + i64 1, label %outer.header + ], !llvm.loop !2 + +inner.body: ; preds = %inner.header + %add10 = add nuw nsw i64 %j.0, 1 + br label %inner.header, !llvm.loop !4 +} + +!2 = distinct !{!2, !3} +!3 = !{!"llvm.loop.unroll_and_jam.count", i32 17} +!4 = distinct !{!4, !5} +!5 = !{!"llvm.loop.unroll.count", i32 1}