Index: llvm/lib/Transforms/Scalar/LoopInterchange.cpp =================================================================== --- llvm/lib/Transforms/Scalar/LoopInterchange.cpp +++ llvm/lib/Transforms/Scalar/LoopInterchange.cpp @@ -347,6 +347,7 @@ private: bool tightlyNested(Loop *Outer, Loop *Inner); + bool containsUnsafeInstructionsInInnerLoop(void); bool containsUnsafeInstructions(BasicBlock *BB); /// Discover induction and reduction PHIs in the header of \p L. Induction @@ -578,6 +579,37 @@ } // end anonymous namespace +/// Returns true if there are unsafe instructions above or below +/// the inner loop. +bool LoopInterchangeLegality::containsUnsafeInstructionsInInnerLoop() { + BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader(); + BasicBlock *InnerLoopExit = InnerLoop->getExitBlock(); + BasicBlock *OuterLoopHeader = OuterLoop->getHeader(); + BasicBlock *OuterLoopLatch = OuterLoop->getLoopLatch(); + + // Check loop preheader. + // In Transforms/LoopInterchange/lcssa-preheader.ll, the inner loop + // preheader has Zext instruction. + if (InnerLoopPreHeader != OuterLoopHeader) { + for (Instruction &I : *InnerLoopPreHeader) { + if (!isa(&I) && !isa(&I) && + !isa(&I)) + return true; + } + } + + // Check loop latch. + if (InnerLoopExit != OuterLoopLatch) { + for (Instruction &I : *InnerLoopExit) { + if (!isa(&I) && !isa(&I) && + !isa(&I)) + return true; + } + } + + return false; +} + bool LoopInterchangeLegality::containsUnsafeInstructions(BasicBlock *BB) { return any_of(*BB, [](const Instruction &I) { return I.mayHaveSideEffects() || I.mayReadFromMemory(); @@ -618,6 +650,12 @@ containsUnsafeInstructions(InnerLoopPreHeader)) return false; + // Check if the loops are tightly nested. + // Basically, if there are instructions that may be unsafe + // in the inner loop preheader and exit, suppress Loop-interchange. + if (containsUnsafeInstructionsInInnerLoop()) + return false; + LLVM_DEBUG(dbgs() << "Loops are perfectly nested\n"); // We have a perfect loop nest. return true; Index: llvm/test/Transforms/LoopInterchange/pr43797-lcssa-for-multiple-outer-loop-blocks.ll =================================================================== --- llvm/test/Transforms/LoopInterchange/pr43797-lcssa-for-multiple-outer-loop-blocks.ll +++ llvm/test/Transforms/LoopInterchange/pr43797-lcssa-for-multiple-outer-loop-blocks.ll @@ -1,48 +1,15 @@ ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py -; RUN: opt -loop-interchange -verify-loop-lcssa -S %s | FileCheck %s +; RUN: opt -loop-interchange -verify-loop-lcssa -pass-remarks-output=%t -S %s +; RUN: FileCheck %s --input-file %t --check-prefix REMARK ; Tests for PR43797. @wdtdr = external dso_local global [5 x [5 x double]], align 16 +; REMARK: NotTightlyNested + +;; Loops not tightly nested are not interchanged define void @test1() { -; CHECK-LABEL: @test1( -; CHECK-NEXT: entry: -; CHECK-NEXT: br label [[INNER_HEADER_PREHEADER:%.*]] -; CHECK: outer.header.preheader: -; CHECK-NEXT: br label [[OUTER_HEADER:%.*]] -; CHECK: outer.header: -; CHECK-NEXT: [[OUTER_IDX:%.*]] = phi i64 [ [[OUTER_IDX_INC:%.*]], [[OUTER_LATCH:%.*]] ], [ 0, [[OUTER_HEADER_PREHEADER:%.*]] ] -; CHECK-NEXT: [[ARRAYIDX8:%.*]] = getelementptr inbounds [5 x [5 x double]], [5 x [5 x double]]* @wdtdr, i64 0, i64 0, i64 [[OUTER_IDX]] -; CHECK-NEXT: br label [[INNER_HEADER_SPLIT:%.*]] -; CHECK: inner.header.preheader: -; CHECK-NEXT: br label [[INNER_HEADER:%.*]] -; CHECK: inner.header: -; CHECK-NEXT: [[INNER_IDX:%.*]] = phi i64 [ [[TMP3:%.*]], [[INNER_LATCH_SPLIT:%.*]] ], [ 0, [[INNER_HEADER_PREHEADER]] ] -; CHECK-NEXT: br label [[OUTER_HEADER_PREHEADER]] -; CHECK: inner.header.split: -; CHECK-NEXT: [[TMP0:%.*]] = load double, double* [[ARRAYIDX8]], align 8 -; CHECK-NEXT: store double undef, double* [[ARRAYIDX8]], align 8 -; CHECK-NEXT: br label [[INNER_LATCH:%.*]] -; CHECK: inner.latch: -; CHECK-NEXT: [[INNER_IDX_INC:%.*]] = add nsw i64 [[INNER_IDX]], 1 -; CHECK-NEXT: br label [[INNER_EXIT:%.*]] -; CHECK: inner.latch.split: -; CHECK-NEXT: [[TMP1:%.*]] = phi i64 [ [[OUTER_V:%.*]], [[OUTER_LATCH]] ] -; CHECK-NEXT: [[TMP2:%.*]] = phi i64 [ [[OUTER_IDX_INC]], [[OUTER_LATCH]] ] -; CHECK-NEXT: [[TMP3]] = add nsw i64 [[INNER_IDX]], 1 -; CHECK-NEXT: br i1 false, label [[INNER_HEADER]], label [[OUTER_EXIT:%.*]] -; CHECK: inner.exit: -; CHECK-NEXT: [[OUTER_V]] = add nsw i64 [[OUTER_IDX]], 1 -; CHECK-NEXT: br label [[OUTER_LATCH]] -; CHECK: outer.latch: -; CHECK-NEXT: [[OUTER_IDX_INC]] = add nsw i64 [[OUTER_IDX]], 1 -; CHECK-NEXT: br i1 false, label [[OUTER_HEADER]], label [[INNER_LATCH_SPLIT]] -; CHECK: outer.exit: -; CHECK-NEXT: [[EXIT1_LCSSA:%.*]] = phi i64 [ [[TMP1]], [[INNER_LATCH_SPLIT]] ] -; CHECK-NEXT: [[EXIT2_LCSSA:%.*]] = phi i64 [ [[TMP2]], [[INNER_LATCH_SPLIT]] ] -; CHECK-NEXT: ret void -; entry: br label %outer.header @@ -75,48 +42,10 @@ ret void } +; REMARK: NotTightlyNested + +;; Loops not tightly nested are not interchanged define void @test2(i1 %cond) { -; CHECK-LABEL: @test2( -; CHECK-NEXT: entry: -; CHECK-NEXT: br i1 [[COND:%.*]], label [[INNER_HEADER_PREHEADER:%.*]], label [[OUTER_EXIT:%.*]] -; CHECK: outer.header.preheader: -; CHECK-NEXT: br label [[OUTER_HEADER:%.*]] -; CHECK: outer.header: -; CHECK-NEXT: [[OUTER_IDX:%.*]] = phi i64 [ [[OUTER_IDX_INC:%.*]], [[OUTER_LATCH:%.*]] ], [ 0, [[OUTER_HEADER_PREHEADER:%.*]] ] -; CHECK-NEXT: [[ARRAYIDX8:%.*]] = getelementptr inbounds [5 x [5 x double]], [5 x [5 x double]]* @wdtdr, i64 0, i64 0, i64 [[OUTER_IDX]] -; CHECK-NEXT: br label [[INNER_HEADER_SPLIT:%.*]] -; CHECK: inner.header.preheader: -; CHECK-NEXT: br label [[INNER_HEADER:%.*]] -; CHECK: inner.header: -; CHECK-NEXT: [[INNER_IDX:%.*]] = phi i64 [ [[TMP3:%.*]], [[INNER_LATCH_SPLIT:%.*]] ], [ 0, [[INNER_HEADER_PREHEADER]] ] -; CHECK-NEXT: br label [[OUTER_HEADER_PREHEADER]] -; CHECK: inner.header.split: -; CHECK-NEXT: [[TMP0:%.*]] = load double, double* [[ARRAYIDX8]], align 8 -; CHECK-NEXT: store double undef, double* [[ARRAYIDX8]], align 8 -; CHECK-NEXT: br label [[INNER_LATCH:%.*]] -; CHECK: inner.latch: -; CHECK-NEXT: [[INNER_IDX_INC:%.*]] = add nsw i64 [[INNER_IDX]], 1 -; CHECK-NEXT: br label [[INNER_EXIT:%.*]] -; CHECK: inner.latch.split: -; CHECK-NEXT: [[TMP1:%.*]] = phi i64 [ [[OUTER_IDX_INC]], [[OUTER_LATCH]] ] -; CHECK-NEXT: [[TMP2:%.*]] = phi i64 [ [[OUTER_V:%.*]], [[OUTER_LATCH]] ] -; CHECK-NEXT: [[TMP3]] = add nsw i64 [[INNER_IDX]], 1 -; CHECK-NEXT: br i1 false, label [[INNER_HEADER]], label [[OUTER_EXIT_LOOPEXIT:%.*]] -; CHECK: inner.exit: -; CHECK-NEXT: [[OUTER_V]] = add nsw i64 [[OUTER_IDX]], 1 -; CHECK-NEXT: br label [[OUTER_LATCH]] -; CHECK: outer.latch: -; CHECK-NEXT: [[OUTER_IDX_INC]] = add nsw i64 [[OUTER_IDX]], 1 -; CHECK-NEXT: br i1 false, label [[OUTER_HEADER]], label [[INNER_LATCH_SPLIT]] -; CHECK: outer.exit.loopexit: -; CHECK-NEXT: [[OUTER_IDX_INC_LCSSA:%.*]] = phi i64 [ [[TMP1]], [[INNER_LATCH_SPLIT]] ] -; CHECK-NEXT: [[OUTER_V_LCSSA:%.*]] = phi i64 [ [[TMP2]], [[INNER_LATCH_SPLIT]] ] -; CHECK-NEXT: br label [[OUTER_EXIT]] -; CHECK: outer.exit: -; CHECK-NEXT: [[EXIT1_LCSSA:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[OUTER_V_LCSSA]], [[OUTER_EXIT_LOOPEXIT]] ] -; CHECK-NEXT: [[EXIT2_LCSSA:%.*]] = phi i64 [ 0, [[ENTRY]] ], [ [[OUTER_IDX_INC_LCSSA]], [[OUTER_EXIT_LOOPEXIT]] ] -; CHECK-NEXT: ret void -; entry: br i1 %cond, label %outer.header, label %outer.exit Index: llvm/test/Transforms/LoopInterchange/pr45743-move-from-inner-preheader.ll =================================================================== --- llvm/test/Transforms/LoopInterchange/pr45743-move-from-inner-preheader.ll +++ llvm/test/Transforms/LoopInterchange/pr45743-move-from-inner-preheader.ll @@ -3,44 +3,11 @@ @global = external local_unnamed_addr global [2 x [10 x i32]], align 16 +;; Loops not tightly nested are not interchanged ; We need to move %tmp4 from the inner loop pre header to the outer loop header ; before interchanging. define void @test1() local_unnamed_addr #0 { ; CHECK-LABEL: @test1( -; CHECK-NEXT: bb: -; CHECK-NEXT: br label [[INNER_PH:%.*]] -; CHECK: outer.header.preheader: -; CHECK-NEXT: br label [[OUTER_HEADER:%.*]] -; CHECK: outer.header: -; CHECK-NEXT: [[OUTER_IV:%.*]] = phi i64 [ [[OUTER_IV_NEXT:%.*]], [[OUTER_LATCH:%.*]] ], [ 0, [[OUTER_HEADER_PREHEADER:%.*]] ] -; CHECK-NEXT: [[INNER_RED:%.*]] = phi i32 [ [[OUTER_RED:%.*]], [[OUTER_HEADER_PREHEADER]] ], [ [[RED_NEXT:%.*]], [[OUTER_LATCH]] ] -; CHECK-NEXT: [[TMP4:%.*]] = add nsw i64 [[OUTER_IV]], 9 -; CHECK-NEXT: br label [[INNER_SPLIT1:%.*]] -; CHECK: inner.ph: -; CHECK-NEXT: br label [[INNER:%.*]] -; CHECK: inner: -; CHECK-NEXT: [[INNER_IV:%.*]] = phi i64 [ 0, [[INNER_PH]] ], [ [[TMP0:%.*]], [[INNER_SPLIT:%.*]] ] -; CHECK-NEXT: [[OUTER_RED]] = phi i32 [ [[RED_NEXT_LCSSA:%.*]], [[INNER_SPLIT]] ], [ 0, [[INNER_PH]] ] -; CHECK-NEXT: br label [[OUTER_HEADER_PREHEADER]] -; CHECK: inner.split1: -; CHECK-NEXT: [[PTR:%.*]] = getelementptr inbounds [2 x [10 x i32]], [2 x [10 x i32]]* @global, i64 0, i64 [[INNER_IV]], i64 [[TMP4]] -; CHECK-NEXT: store i32 0, i32* [[PTR]], align 4 -; CHECK-NEXT: [[RED_NEXT]] = or i32 [[INNER_RED]], 20 -; CHECK-NEXT: [[INNER_IV_NEXT:%.*]] = add nsw i64 [[INNER_IV]], 1 -; CHECK-NEXT: [[EC_1:%.*]] = icmp eq i64 [[INNER_IV_NEXT]], 400 -; CHECK-NEXT: br label [[OUTER_LATCH]] -; CHECK: inner.split: -; CHECK-NEXT: [[RED_NEXT_LCSSA]] = phi i32 [ [[RED_NEXT]], [[OUTER_LATCH]] ] -; CHECK-NEXT: [[TMP0]] = add nsw i64 [[INNER_IV]], 1 -; CHECK-NEXT: [[TMP1:%.*]] = icmp eq i64 [[TMP0]], 400 -; CHECK-NEXT: br i1 [[TMP1]], label [[EXIT:%.*]], label [[INNER]] -; CHECK: outer.latch: -; CHECK-NEXT: [[OUTER_IV_NEXT]] = add nsw i64 [[OUTER_IV]], 1 -; CHECK-NEXT: [[EC_2:%.*]] = icmp eq i64 [[OUTER_IV_NEXT]], 400 -; CHECK-NEXT: br i1 [[EC_2]], label [[INNER_SPLIT]], label [[OUTER_HEADER]] -; CHECK: exit: -; CHECK-NEXT: ret void -; bb: br label %outer.header