llvmorg-github-actions[bot] wrote:
<!--LLVM PR SUMMARY COMMENT--> @llvm/pr-subscribers-llvm-transforms Author: Ryotaro Kasuga (kasuga-fj) <details> <summary>Changes</summary> In the legality check, there is a routine to detect and verify the induction variables of the inner loop. However, the validation was insufficient, specifically when the step values of the induction variables are not loop-invariant with respect to the outer loop. This patch adds an additional check to ensure that the step values of those induction variables are also loop-invariant with respect to the outer loop. Fixes #<!-- -->202383 and #<!-- -->202401. --- Full diff: https://github.com/llvm/llvm-project/pull/202751.diff 2 Files Affected: - (modified) llvm/lib/Transforms/Scalar/LoopInterchange.cpp (+17-8) - (modified) llvm/test/Transforms/LoopInterchange/inner-induciton-step-is-not-invariant.ll (+20-48) ``````````diff diff --git a/llvm/lib/Transforms/Scalar/LoopInterchange.cpp b/llvm/lib/Transforms/Scalar/LoopInterchange.cpp index cb1327b75260f..adf65c81b678c 100644 --- a/llvm/lib/Transforms/Scalar/LoopInterchange.cpp +++ b/llvm/lib/Transforms/Scalar/LoopInterchange.cpp @@ -461,9 +461,12 @@ class LoopInterchangeLegality { bool canInterchangeLoops(unsigned InnerLoopId, unsigned OuterLoopId, CharMatrix &DepMatrix); - /// Discover induction PHIs in the header of \p L. Induction - /// PHIs are added to \p Inductions. - bool findInductions(Loop *L, SmallVectorImpl<PHINode *> &Inductions); + /// Discover induction PHIs in the header of \p Inner. Induction PHIs are + /// added to \p Inductions. Return true if all induction PHIs in the header of + /// \p Inner have a step value which is invariant with respect to \p Outer, + /// and at least one such induction PHI is found. + bool findInductions(Loop *Outer, Loop *Inner, + SmallVectorImpl<PHINode *> &Inductions); /// Check if the loop structure is understood. We do not handle triangular /// loops for now. @@ -1370,11 +1373,17 @@ bool LoopInterchangeLegality::currentLimitations() { } bool LoopInterchangeLegality::findInductions( - Loop *L, SmallVectorImpl<PHINode *> &Inductions) { - for (PHINode &PHI : L->getHeader()->phis()) { + Loop *OuterLoop, Loop *InnerLoop, SmallVectorImpl<PHINode *> &Inductions) { + for (PHINode &PHI : InnerLoop->getHeader()->phis()) { InductionDescriptor ID; - if (InductionDescriptor::isInductionPHI(&PHI, L, SE, ID)) - Inductions.push_back(&PHI); + if (!InductionDescriptor::isInductionPHI(&PHI, InnerLoop, SE, ID)) + continue; + const SCEV *Step = ID.getStep(); + if (!SE->isLoopInvariant(Step, OuterLoop)) { + Inductions.clear(); + return false; + } + Inductions.push_back(&PHI); } return !Inductions.empty(); } @@ -1524,7 +1533,7 @@ bool LoopInterchangeLegality::canInterchangeLoops(unsigned InnerLoopId, return false; } - if (!findInductions(InnerLoop, InnerLoopInductions)) { + if (!findInductions(OuterLoop, InnerLoop, InnerLoopInductions)) { LLVM_DEBUG(dbgs() << "Could not find inner loop induction variables.\n"); return false; } 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 ; `````````` </details> https://github.com/llvm/llvm-project/pull/202751 _______________________________________________ llvm-branch-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
