diff --git a/llvm/lib/Transforms/Scalar/LoopInterchange.cpp b/llvm/lib/Transforms/Scalar/LoopInterchange.cpp --- a/llvm/lib/Transforms/Scalar/LoopInterchange.cpp +++ b/llvm/lib/Transforms/Scalar/LoopInterchange.cpp @@ -412,7 +412,6 @@ private: bool adjustLoopLinks(); - void adjustLoopPreheaders(); bool adjustLoopBranches(); Loop *OuterLoop; @@ -580,6 +579,12 @@ LIT.transform(); LLVM_DEBUG(dbgs() << "Loops interchanged.\n"); LoopsInterchanged++; + + assert(InnerLoop->isLCSSAForm(*DT) && + "Inner loop not left in LCSSA form after loop interchange!"); + assert(OuterLoop->isLCSSAForm(*DT) && + "Outer loop not left in LCSSA form after loop interchange!"); + return true; } }; @@ -1319,6 +1324,23 @@ FromBB->getTerminator()->getIterator()); } +/// Swap instructions between \p BB1 and \p BB2 but keep terminators intact. +static void swapBBContents(BasicBlock *BB1, BasicBlock *BB2) { + // Save all non-terminator instructions of BB1 into TempInstrs and unlink them + // from BB1 afterwards. + auto Iter = map_range(*BB1, [](Instruction &I) { return &I; }); + SmallVector TempInstrs(Iter.begin(), std::prev(Iter.end())); + for (Instruction *I : TempInstrs) + I->removeFromParent(); + + // Move instructions from BB2 to BB1. + moveBBContents(BB2, BB1->getTerminator()); + + // Move instructions from TempInstrs to BB2. + for (Instruction *I : TempInstrs) + I->insertBefore(BB2->getTerminator()); +} + // Update BI to jump to NewBB instead of OldBB. Records updates to the // dominator tree in DTUpdates. If \p MustUpdateOnce is true, assert that // \p OldBB is exactly once in BI's successor list. @@ -1578,30 +1600,17 @@ return true; } -void LoopInterchangeTransform::adjustLoopPreheaders() { - // We have interchanged the preheaders so we need to interchange the data in - // the preheader as well. - // This is because the content of inner preheader was previously executed - // inside the outer loop. - BasicBlock *OuterLoopPreHeader = OuterLoop->getLoopPreheader(); - BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader(); - BasicBlock *OuterLoopHeader = OuterLoop->getHeader(); - BranchInst *InnerTermBI = - cast(InnerLoopPreHeader->getTerminator()); - - // These instructions should now be executed inside the loop. - // Move instruction into a new block after outer header. - moveBBContents(InnerLoopPreHeader, OuterLoopHeader->getTerminator()); - // These instructions were not executed previously in the loop so move them to - // the older inner loop preheader. - moveBBContents(OuterLoopPreHeader, InnerTermBI); -} - bool LoopInterchangeTransform::adjustLoopLinks() { // Adjust all branches in the inner and outer loop. bool Changed = adjustLoopBranches(); - if (Changed) - adjustLoopPreheaders(); + if (Changed) { + // We have interchanged the preheaders so we need to interchange the data in + // the preheaders as well. This is because the content of the inner + // preheader was previously executed inside the outer loop. + BasicBlock *OuterLoopPreHeader = OuterLoop->getLoopPreheader(); + BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader(); + swapBBContents(OuterLoopPreHeader, InnerLoopPreHeader); + } return Changed; } diff --git a/llvm/test/Transforms/LoopInterchange/lcssa-preheader.ll b/llvm/test/Transforms/LoopInterchange/lcssa-preheader.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Transforms/LoopInterchange/lcssa-preheader.ll @@ -0,0 +1,103 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; RUN: opt < %s -basicaa -loop-interchange -pass-remarks-missed='loop-interchange' -verify-loop-lcssa -S | FileCheck %s + +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" + +; void foo(int n, int m) { +; int temp[16][16]; +; int res[16][16]; +; for(int i = 0; i < n; i++) { +; for(int j = 0; j < m; j++) +; res[j][i] = temp[j][i]; +; } +; } + +define void @lcssa_08(i32 %n, i32 %m) { +; CHECK-LABEL: @lcssa_08( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[TEMP:%.*]] = alloca [16 x [16 x i32]], align 4 +; CHECK-NEXT: [[RES:%.*]] = alloca [16 x [16 x i32]], align 4 +; CHECK-NEXT: [[CMP24:%.*]] = icmp sgt i32 [[N:%.*]], 0 +; CHECK-NEXT: br i1 [[CMP24]], label [[INNER_PREHEADER:%.*]], label [[FOR_COND_CLEANUP:%.*]] +; CHECK: outer.preheader: +; CHECK-NEXT: [[WIDE_TRIP_COUNT:%.*]] = zext i32 [[M:%.*]] to i64 +; CHECK-NEXT: br label [[OUTER_HEADER:%.*]] +; CHECK: outer.header: +; CHECK-NEXT: [[INDVARS_IV27:%.*]] = phi i64 [ 0, [[OUTER_PREHEADER:%.*]] ], [ [[INDVARS_IV_NEXT28:%.*]], [[OUTER_LATCH:%.*]] ] +; CHECK-NEXT: [[CMP222:%.*]] = icmp sgt i32 [[M]], 0 +; CHECK-NEXT: br i1 [[CMP222]], label [[INNER_FOR_BODY_SPLIT1:%.*]], label [[OUTER_CRIT_EDGE:%.*]] +; CHECK: inner.preheader: +; CHECK-NEXT: [[WIDE_TRIP_COUNT29:%.*]] = zext i32 [[N]] to i64 +; CHECK-NEXT: br label [[INNER_FOR_BODY:%.*]] +; CHECK: inner.for.body: +; CHECK-NEXT: [[INDVARS_IV:%.*]] = phi i64 [ 0, [[INNER_PREHEADER]] ], [ [[TMP1:%.*]], [[INNER_FOR_BODY_SPLIT:%.*]] ] +; CHECK-NEXT: br label [[OUTER_PREHEADER]] +; CHECK: inner.for.body.split1: +; CHECK-NEXT: [[ARRAYIDX6:%.*]] = getelementptr inbounds [16 x [16 x i32]], [16 x [16 x i32]]* [[TEMP]], i64 0, i64 [[INDVARS_IV]], i64 [[INDVARS_IV27]] +; CHECK-NEXT: [[TMP0:%.*]] = load i32, i32* [[ARRAYIDX6]], align 4 +; CHECK-NEXT: [[ARRAYIDX8:%.*]] = getelementptr inbounds [16 x [16 x i32]], [16 x [16 x i32]]* [[RES]], i64 0, i64 [[INDVARS_IV]], i64 [[INDVARS_IV27]] +; CHECK-NEXT: store i32 [[TMP0]], i32* [[ARRAYIDX8]], align 4 +; CHECK-NEXT: [[INDVARS_IV_NEXT:%.*]] = add nuw nsw i64 [[INDVARS_IV]], 1 +; CHECK-NEXT: [[EXITCOND:%.*]] = icmp ne i64 [[INDVARS_IV_NEXT]], [[WIDE_TRIP_COUNT]] +; CHECK-NEXT: br label [[INNER_CRIT_EDGE:%.*]] +; CHECK: inner.for.body.split: +; CHECK-NEXT: [[TMP1]] = add nuw nsw i64 [[INDVARS_IV]], 1 +; CHECK-NEXT: [[TMP2:%.*]] = icmp ne i64 [[TMP1]], [[WIDE_TRIP_COUNT]] +; CHECK-NEXT: br i1 [[TMP2]], label [[INNER_FOR_BODY]], label [[OUTER_CRIT_EDGE]] +; CHECK: inner.crit_edge: +; CHECK-NEXT: br label [[OUTER_LATCH]] +; CHECK: outer.latch: +; CHECK-NEXT: [[INDVARS_IV_NEXT28]] = add nuw nsw i64 [[INDVARS_IV27]], 1 +; CHECK-NEXT: [[EXITCOND30:%.*]] = icmp ne i64 [[INDVARS_IV_NEXT28]], [[WIDE_TRIP_COUNT29]] +; CHECK-NEXT: br i1 [[EXITCOND30]], label [[OUTER_HEADER]], label [[INNER_FOR_BODY_SPLIT]] +; CHECK: outer.crit_edge: +; CHECK-NEXT: br label [[FOR_COND_CLEANUP]] +; CHECK: for.cond.cleanup: +; CHECK-NEXT: ret void +; +entry: + %temp = alloca [16 x [16 x i32]], align 4 + %res = alloca [16 x [16 x i32]], align 4 + %cmp24 = icmp sgt i32 %n, 0 + br i1 %cmp24, label %outer.preheader, label %for.cond.cleanup + +outer.preheader: ; preds = %entry + %wide.trip.count29 = zext i32 %n to i64 + br label %outer.header + +outer.header: ; preds = %outer.preheader, %outer.latch + %indvars.iv27 = phi i64 [ 0, %outer.preheader ], [ %indvars.iv.next28, %outer.latch ] + %cmp222 = icmp sgt i32 %m, 0 + br i1 %cmp222, label %inner.preheader, label %outer.latch + +inner.preheader: ; preds = %outer.header + ; When inner.preheader becomes the outer preheader, do not move + ; %wide.trip.count into the inner loop header lest LCSSA break + ; (if %wide.trip.count gets moved, its use is now outside the inner loop). + %wide.trip.count = zext i32 %m to i64 + br label %inner.for.body + +inner.for.body: ; preds = %inner.preheader, %inner.for.body + %indvars.iv = phi i64 [ 0, %inner.preheader ], [ %indvars.iv.next, %inner.for.body ] + %arrayidx6 = getelementptr inbounds [16 x [16 x i32]], [16 x [16 x i32]]* %temp, i64 0, i64 %indvars.iv, i64 %indvars.iv27 + %0 = load i32, i32* %arrayidx6, align 4 + %arrayidx8 = getelementptr inbounds [16 x [16 x i32]], [16 x [16 x i32]]* %res, i64 0, i64 %indvars.iv, i64 %indvars.iv27 + store i32 %0, i32* %arrayidx8, align 4 + %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 + %exitcond = icmp ne i64 %indvars.iv.next, %wide.trip.count + br i1 %exitcond, label %inner.for.body, label %inner.crit_edge + +inner.crit_edge: ; preds = %inner.for.body + br label %outer.latch + +outer.latch: ; preds = %inner.crit_edge, %outer.header + %indvars.iv.next28 = add nuw nsw i64 %indvars.iv27, 1 + %exitcond30 = icmp ne i64 %indvars.iv.next28, %wide.trip.count29 + br i1 %exitcond30, label %outer.header, label %outer.crit_edge + +outer.crit_edge: ; preds = %outer.latch + br label %for.cond.cleanup + +for.cond.cleanup: ; preds = %outer.crit_edge, %entry + ret void +}