https://github.com/kasuga-fj updated https://github.com/llvm/llvm-project/pull/202751
>From 49765269b8445ef93128875e1a1ee1383649878e Mon Sep 17 00:00:00 2001 From: Ryotaro Kasuga <[email protected]> Date: Wed, 10 Jun 2026 04:41:33 +0900 Subject: [PATCH 1/2] [LoopInterchange] Reject if inner loop IV has outer-variant step --- .../lib/Transforms/Scalar/LoopInterchange.cpp | 8 ++- .../inner-induciton-step-is-not-invariant.ll | 68 ++++++------------- 2 files changed, 27 insertions(+), 49 deletions(-) diff --git a/llvm/lib/Transforms/Scalar/LoopInterchange.cpp b/llvm/lib/Transforms/Scalar/LoopInterchange.cpp index 543f527941b29..26fbf8a5f51e2 100644 --- a/llvm/lib/Transforms/Scalar/LoopInterchange.cpp +++ b/llvm/lib/Transforms/Scalar/LoopInterchange.cpp @@ -1251,8 +1251,14 @@ bool LoopInterchangeLegality::checkInductionsAndReductions(Loop *OuterLoop) { for (PHINode &PHI : CurLoop->getHeader()->phis()) { InductionDescriptor ID; if (InductionDescriptor::isInductionPHI(&PHI, CurLoop, SE, ID)) { - if (CurLoop == InnerLoop) + if (CurLoop == InnerLoop) { + const SCEV *Step = ID.getStep(); + if (!SE->isLoopInvariant(Step, OuterLoop)) { + InnerLoopInductions.clear(); + return false; + } InnerLoopInductions.push_back(&PHI); + } continue; } diff --git a/llvm/test/Transforms/LoopInterchange/inner-induciton-step-is-not-invariant.ll b/llvm/test/Transforms/LoopInterchange/inner-induciton-step-is-not-invariant.ll index 37bc9266942ed..f5960c7400cc8 100644 --- a/llvm/test/Transforms/LoopInterchange/inner-induciton-step-is-not-invariant.ll +++ b/llvm/test/Transforms/LoopInterchange/inner-induciton-step-is-not-invariant.ll @@ -10,43 +10,29 @@ ; for (j = 0, k = 0; k < 16 + i; j++, k += i) ; A[8*j + i] += 1; ; -; FIXME: This is now interchanged. -; define void @step_of_k_is_i_0(ptr %A) { ; CHECK-LABEL: define void @step_of_k_is_i_0( ; CHECK-SAME: ptr [[A:%.*]]) { -; CHECK-NEXT: [[ENTRY:.*:]] -; CHECK-NEXT: br label %[[OUTER_HEADER:.*]] -; CHECK: [[OUTER_HEADER_PREHEADER:.*]]: -; CHECK-NEXT: br label %[[INNER:.*]] -; CHECK: [[INNER]]: -; CHECK-NEXT: [[I:%.*]] = phi i64 [ [[I_NEXT:%.*]], %[[OUTER_LATCH:.*]] ], [ 1, %[[OUTER_HEADER_PREHEADER]] ] -; CHECK-NEXT: br label %[[INNER_SPLIT1:.*]] -; CHECK: [[OUTER_HEADER]]: +; CHECK-NEXT: [[OUTER_HEADER:.*]]: ; CHECK-NEXT: br label %[[INNER1:.*]] ; CHECK: [[INNER1]]: -; CHECK-NEXT: [[J:%.*]] = phi i64 [ [[TMP1:%.*]], %[[INNER_SPLIT:.*]] ], [ 0, %[[OUTER_HEADER]] ] -; CHECK-NEXT: [[K:%.*]] = phi i64 [ [[TMP0:%.*]], %[[INNER_SPLIT]] ], [ 0, %[[OUTER_HEADER]] ] -; CHECK-NEXT: br label %[[OUTER_HEADER_PREHEADER]] -; CHECK: [[INNER_SPLIT1]]: +; CHECK-NEXT: [[I:%.*]] = phi i64 [ 1, %[[OUTER_HEADER]] ], [ [[I_NEXT:%.*]], %[[OUTER_LATCH:.*]] ] +; CHECK-NEXT: br label %[[OUTER_HEADER_PREHEADER:.*]] +; CHECK: [[OUTER_HEADER_PREHEADER]]: +; CHECK-NEXT: [[J:%.*]] = phi i64 [ 0, %[[INNER1]] ], [ [[J_NEXT:%.*]], %[[OUTER_HEADER_PREHEADER]] ] +; CHECK-NEXT: [[K:%.*]] = phi i64 [ 0, %[[INNER1]] ], [ [[K_NEXT:%.*]], %[[OUTER_HEADER_PREHEADER]] ] ; CHECK-NEXT: [[GEP:%.*]] = getelementptr [8 x i8], ptr [[A]], i64 [[J]], i64 [[I]] ; CHECK-NEXT: [[OLD:%.*]] = load i8, ptr [[GEP]], align 1 ; CHECK-NEXT: [[NEW:%.*]] = add i8 [[OLD]], 1 ; CHECK-NEXT: store i8 [[NEW]], ptr [[GEP]], align 1 -; CHECK-NEXT: [[J_NEXT:%.*]] = add i64 [[J]], 1 -; CHECK-NEXT: [[K_NEXT:%.*]] = add i64 [[K]], [[I]] -; CHECK-NEXT: [[EC_INNER_NOT:%.*]] = icmp slt i64 [[K]], 16 -; CHECK-NEXT: br label %[[OUTER_LATCH]] -; CHECK: [[INNER_SPLIT]]: -; CHECK-NEXT: [[I_LCSSA:%.*]] = phi i64 [ [[I]], %[[OUTER_LATCH]] ] -; CHECK-NEXT: [[TMP0]] = add i64 [[K]], [[I_LCSSA]] -; CHECK-NEXT: [[TMP1]] = add i64 [[J]], 1 +; CHECK-NEXT: [[J_NEXT]] = add i64 [[J]], 1 +; CHECK-NEXT: [[K_NEXT]] = add i64 [[K]], [[I]] ; CHECK-NEXT: [[TMP2:%.*]] = icmp slt i64 [[K]], 16 -; CHECK-NEXT: br i1 [[TMP2]], label %[[INNER1]], label %[[EXIT:.*]] +; CHECK-NEXT: br i1 [[TMP2]], label %[[OUTER_HEADER_PREHEADER]], label %[[OUTER_LATCH]] ; CHECK: [[OUTER_LATCH]]: ; CHECK-NEXT: [[I_NEXT]] = add i64 [[I]], 1 ; CHECK-NEXT: [[CMP_I:%.*]] = icmp slt i64 [[I_NEXT]], 8 -; CHECK-NEXT: br i1 [[CMP_I]], label %[[INNER]], label %[[INNER_SPLIT]] +; CHECK-NEXT: br i1 [[CMP_I]], label %[[INNER1]], label %[[EXIT:.*]] ; CHECK: [[EXIT]]: ; CHECK-NEXT: ret void ; @@ -82,41 +68,27 @@ exit: ; for (j = 0, k = 0; j < 30; j++, k += i) ; A[i][j] = k; ; -; FIXME: This is now interchanged. -; define void @step_ok_k_is_i_1(ptr %A) { ; CHECK-LABEL: define void @step_ok_k_is_i_1( ; CHECK-SAME: ptr [[A:%.*]]) { -; CHECK-NEXT: [[ENTRY:.*:]] -; CHECK-NEXT: br label %[[OUTER_HEADER:.*]] -; CHECK: [[OUTER_HEADER_PREHEADER:.*]]: -; CHECK-NEXT: br label %[[INNER:.*]] -; CHECK: [[INNER]]: -; CHECK-NEXT: [[I:%.*]] = phi i64 [ [[I_NEXT:%.*]], %[[OUTER_LATCH:.*]] ], [ 0, %[[OUTER_HEADER_PREHEADER]] ] -; CHECK-NEXT: br label %[[INNER_SPLIT1:.*]] -; CHECK: [[OUTER_HEADER]]: +; CHECK-NEXT: [[OUTER_HEADER:.*]]: ; CHECK-NEXT: br label %[[INNER1:.*]] ; CHECK: [[INNER1]]: -; CHECK-NEXT: [[J:%.*]] = phi i64 [ [[TMP1:%.*]], %[[INNER_SPLIT:.*]] ], [ 0, %[[OUTER_HEADER]] ] -; CHECK-NEXT: [[K:%.*]] = phi i64 [ [[TMP0:%.*]], %[[INNER_SPLIT]] ], [ 0, %[[OUTER_HEADER]] ] -; CHECK-NEXT: br label %[[OUTER_HEADER_PREHEADER]] -; CHECK: [[INNER_SPLIT1]]: +; CHECK-NEXT: [[I:%.*]] = phi i64 [ 0, %[[OUTER_HEADER]] ], [ [[I_NEXT:%.*]], %[[OUTER_LATCH:.*]] ] +; CHECK-NEXT: br label %[[OUTER_HEADER_PREHEADER:.*]] +; CHECK: [[OUTER_HEADER_PREHEADER]]: +; CHECK-NEXT: [[J:%.*]] = phi i64 [ 0, %[[INNER1]] ], [ [[J_NEXT:%.*]], %[[OUTER_HEADER_PREHEADER]] ] +; CHECK-NEXT: [[K:%.*]] = phi i64 [ 0, %[[INNER1]] ], [ [[K_NEXT:%.*]], %[[OUTER_HEADER_PREHEADER]] ] ; CHECK-NEXT: [[GEP:%.*]] = getelementptr inbounds [40 x i64], ptr [[A]], i64 [[I]], i64 [[J]] ; CHECK-NEXT: store i64 [[K]], ptr [[GEP]], align 4 -; CHECK-NEXT: [[J_NEXT:%.*]] = add i64 [[J]], 1 -; CHECK-NEXT: [[K_NEXT:%.*]] = add i64 [[K]], [[I]] -; CHECK-NEXT: [[EC_INNER:%.*]] = icmp eq i64 [[J]], 30 -; CHECK-NEXT: br label %[[OUTER_LATCH]] -; CHECK: [[INNER_SPLIT]]: -; CHECK-NEXT: [[I_LCSSA:%.*]] = phi i64 [ [[I]], %[[OUTER_LATCH]] ] -; CHECK-NEXT: [[TMP0]] = add i64 [[K]], [[I_LCSSA]] -; CHECK-NEXT: [[TMP1]] = add i64 [[J]], 1 +; CHECK-NEXT: [[J_NEXT]] = add i64 [[J]], 1 +; CHECK-NEXT: [[K_NEXT]] = add i64 [[K]], [[I]] ; CHECK-NEXT: [[TMP2:%.*]] = icmp eq i64 [[J]], 30 -; CHECK-NEXT: br i1 [[TMP2]], label %[[EXIT:.*]], label %[[INNER1]] +; CHECK-NEXT: br i1 [[TMP2]], label %[[OUTER_LATCH]], label %[[OUTER_HEADER_PREHEADER]] ; CHECK: [[OUTER_LATCH]]: ; CHECK-NEXT: [[I_NEXT]] = add i64 [[I]], 1 ; CHECK-NEXT: [[EC_I:%.*]] = icmp eq i64 [[I_NEXT]], 6 -; CHECK-NEXT: br i1 [[EC_I]], label %[[INNER_SPLIT]], label %[[INNER]] +; CHECK-NEXT: br i1 [[EC_I]], label %[[EXIT:.*]], label %[[INNER1]] ; CHECK: [[EXIT]]: ; CHECK-NEXT: ret void ; >From 534e92a0310b0d10057a1f60e9fafbfeb0ebf583 Mon Sep 17 00:00:00 2001 From: Ryotaro Kasuga <[email protected]> Date: Thu, 11 Jun 2026 11:29:11 +0000 Subject: [PATCH 2/2] address review --- llvm/lib/Transforms/Scalar/LoopInterchange.cpp | 4 +--- 1 file changed, 1 insertion(+), 3 deletions(-) diff --git a/llvm/lib/Transforms/Scalar/LoopInterchange.cpp b/llvm/lib/Transforms/Scalar/LoopInterchange.cpp index 26fbf8a5f51e2..d4cb7a3fc0130 100644 --- a/llvm/lib/Transforms/Scalar/LoopInterchange.cpp +++ b/llvm/lib/Transforms/Scalar/LoopInterchange.cpp @@ -1253,10 +1253,8 @@ bool LoopInterchangeLegality::checkInductionsAndReductions(Loop *OuterLoop) { if (InductionDescriptor::isInductionPHI(&PHI, CurLoop, SE, ID)) { if (CurLoop == InnerLoop) { const SCEV *Step = ID.getStep(); - if (!SE->isLoopInvariant(Step, OuterLoop)) { - InnerLoopInductions.clear(); + if (!SE->isLoopInvariant(Step, OuterLoop)) return false; - } InnerLoopInductions.push_back(&PHI); } continue; _______________________________________________ llvm-branch-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
