From f71abec661ea716c84e35ac4b41ee5abcccc134a Mon Sep 17 00:00:00 2001 From: Alexey Zhikhartsev Date: Fri, 13 Mar 2020 15:15:11 -0400 Subject: [PATCH] [LoopInterchange] Fix interchanging contents of preheader BBs Summary: Previously LCSSA was getting broken by placing instructions into the (newly) inner *header* instead of the *pre*header. Fixes PR43474 Reviewers: fhahn Reviewed By: fhahn Subscribers: hiraditya, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D75943 --- llvm/lib/Transforms/Scalar/LoopInterchange.cpp | 53 ++++++----- .../Transforms/LoopInterchange/lcssa-preheader.ll | 103 +++++++++++++++++++++ 2 files changed, 134 insertions(+), 22 deletions(-) create mode 100644 llvm/test/Transforms/LoopInterchange/lcssa-preheader.ll diff --git a/llvm/lib/Transforms/Scalar/LoopInterchange.cpp b/llvm/lib/Transforms/Scalar/LoopInterchange.cpp index 6ce2d06..15addc0 100644 --- a/llvm/lib/Transforms/Scalar/LoopInterchange.cpp +++ b/llvm/lib/Transforms/Scalar/LoopInterchange.cpp @@ -412,7 +412,6 @@ public: private: bool adjustLoopLinks(); - void adjustLoopPreheaders(); bool adjustLoopBranches(); Loop *OuterLoop; @@ -580,6 +579,12 @@ struct LoopInterchange : public LoopPass { 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 @@ static void moveBBContents(BasicBlock *FromBB, Instruction *InsertBefore) { 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 @@ bool LoopInterchangeTransform::adjustLoopBranches() { 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 index 0000000..9e6a064 --- /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 +} -- 2.7.4