[LoopInterchange] Bail out when finding a dependency with all `*` elements by kasuga-fj · Pull Request #149049 · llvm/llvm-project

kasuga-fj · 2025-07-16T09:39:16Z

If a direction vector with all * elements, like [* * *], is present, it indicates that none of the loop pairs are legal to interchange. In such cases, continuing the analysis is meaningless.
This patch introduces a check to detect such direction vectors and exits early when one is found. This slightly reduces compile time.

llvmbot · 2025-07-16T09:43:00Z

@llvm/pr-subscribers-llvm-transforms

Author: Ryotaro Kasuga (kasuga-fj)

Changes

Full diff: https://github.com/llvm/llvm-project/pull/149049.diff

6 Files Affected:

(modified) llvm/lib/Transforms/Scalar/LoopInterchange.cpp (+12)
(added) llvm/test/Transforms/LoopInterchange/bail-out-all-deps.ll (+45)
(modified) llvm/test/Transforms/LoopInterchange/confused-dependence.ll (+10-6)
(modified) llvm/test/Transforms/LoopInterchange/legality-for-scalar-deps.ll (+5-5)
(modified) llvm/test/Transforms/LoopInterchange/loop-interchange-optimization-remarks.ll (+3-3)
(modified) llvm/test/Transforms/LoopInterchange/unique-dep-matrix.ll (+1-2)

diff --git a/llvm/lib/Transforms/Scalar/LoopInterchange.cpp b/llvm/lib/Transforms/Scalar/LoopInterchange.cpp
index a5008907b9014..68ecf37f90628 100644
--- a/llvm/lib/Transforms/Scalar/LoopInterchange.cpp
+++ b/llvm/lib/Transforms/Scalar/LoopInterchange.cpp
@@ -221,6 +221,18 @@ static bool populateDependencyMatrix(CharMatrix &DepMatrix, unsigned Level,
           Dep.push_back('I');
         }
 
+        // If there is a direction vector with all entries being '*', we cannot
+        // prove the legality of the interchange for arbitrary pairs of loops.
+        // Exit early in this case to save compile time.
+        if (all_of(Dep, [](char C) { return C == '*'; })) {
+          ORE->emit([&]() {
+            return OptimizationRemarkMissed(DEBUG_TYPE, "Dependence",
+                                            L->getStartLoc(), L->getHeader())
+                   << "All loops have dependencies in all directions.";
+          });
+          return false;
+        }
+
         // Make sure we only add unique entries to the dependency matrix.
         if (Seen.insert(StringRef(Dep.data(), Dep.size())).second)
           DepMatrix.push_back(Dep);
diff --git a/llvm/test/Transforms/LoopInterchange/bail-out-all-deps.ll b/llvm/test/Transforms/LoopInterchange/bail-out-all-deps.ll
new file mode 100644
index 0000000000000..e22d17e5f5400
--- /dev/null
+++ b/llvm/test/Transforms/LoopInterchange/bail-out-all-deps.ll
@@ -0,0 +1,45 @@
+; RUN: opt < %s -passes=loop-interchange -pass-remarks-output=%t \
+; RUN:     -disable-output
+; RUN: FileCheck -input-file %t %s
+
+; Check that loop interchange bail out early when all loops have dependencies
+; in (potentially) all directions.
+;
+; for (int i = 0; i < 4; i++)
+;   for (int j = 0; j < 4; j++)
+;     A[i & val][j & val] = 42;
+
+; CHECK:      --- !Missed
+; CHECK-NEXT: Pass:            loop-interchange
+; CHECK-NEXT: Name:            Dependence
+; CHECK-NEXT: Function:        f
+; CHECK-NEXT: Args:
+; CHECK-NEXT:   - String:          All loops have dependencies in all directions.
+; CHECK-NEXT: ...
+define void @f(ptr %A, i32 %val) {
+entry:
+  br label %for.i.header
+
+for.i.header:
+  %i = phi i32 [ 0, %entry ], [ %i.next, %for.i.latch ]
+  %subscript.0 = and i32 %i, %val
+  %i2 = mul i32 %i, %i
+  br label %for.j
+
+for.j:
+  %j = phi i32 [ 0, %for.i.header ], [ %j.next, %for.j ]
+  %subscript.1 = and i32 %j, %val
+  %idx = getelementptr inbounds [4 x [4 x i32]], ptr %A, i32 0, i32 %subscript.0, i32 %subscript.1
+  store i32 42, ptr %idx, align 4
+  %j.next = add i32 %j, 1
+  %j.exit = icmp eq i32 %j.next, 4
+  br i1 %j.exit, label %for.i.latch, label %for.j
+
+for.i.latch:
+  %i.next = add i32 %i, 1
+  %i.exit = icmp eq i32 %i.next, 4
+  br i1 %i.exit, label %exit, label %for.i.header
+
+exit:
+  ret void
+}
diff --git a/llvm/test/Transforms/LoopInterchange/confused-dependence.ll b/llvm/test/Transforms/LoopInterchange/confused-dependence.ll
index 49b7b0e4797b8..94080949f0af8 100644
--- a/llvm/test/Transforms/LoopInterchange/confused-dependence.ll
+++ b/llvm/test/Transforms/LoopInterchange/confused-dependence.ll
@@ -1,6 +1,6 @@
-; REQUIRES: asserts
-; RUN: opt < %s -passes=loop-interchange -verify-dom-info -verify-loop-info \
-; RUN:     -disable-output -debug 2>&1 | FileCheck %s
+; RUN: opt < %s -passes=loop-interchange -pass-remarks-output=%t \
+; RUN:     -disable-output
+; RUN: FileCheck -input-file %t %s
 
 ;; In the following case, p0 and p1 may alias, so the direction vector must be [* *].
 ;;
@@ -10,9 +10,13 @@
 ;;       p0[4 * i + j] = p1[4 * j + i];
 ;; }
 
-; CHECK:      Dependency matrix before interchange:
-; CHECK-NEXT: * *
-; CHECK-NEXT: Processing InnerLoopId = 1 and OuterLoopId = 0
+; CHECK:      --- !Missed
+; CHECK-NEXT: Pass:            loop-interchange
+; CHECK-NEXT: Name:            Dependence
+; CHECK-NEXT: Function:        may_alias
+; CHECK-NEXT: Args:
+; CHECK-NEXT:   - String:          All loops have dependencies in all directions.
+; CHECK-NEXT: ...
 define void @may_alias(ptr %p0, ptr %p1) {
 entry:
   br label %for.i.header
diff --git a/llvm/test/Transforms/LoopInterchange/legality-for-scalar-deps.ll b/llvm/test/Transforms/LoopInterchange/legality-for-scalar-deps.ll
index c30f9a399fed8..5f4a8486d9ad7 100644
--- a/llvm/test/Transforms/LoopInterchange/legality-for-scalar-deps.ll
+++ b/llvm/test/Transforms/LoopInterchange/legality-for-scalar-deps.ll
@@ -21,13 +21,13 @@
 ; CHECK-NEXT: Name:            Dependence
 ; CHECK-NEXT: Function:        issue46867
 ; CHECK-NEXT: Args:
-; CHECK-NEXT:  - String:       Cannot interchange loops due to dependences.
+; CHECK-NEXT:  - String:          All loops have dependencies in all directions.
 ; CHECK:      --- !Missed
 ; CHECK-NEXT: Pass:            loop-interchange
 ; CHECK-NEXT: Name:            Dependence
 ; CHECK-NEXT: Function:        issue46867
 ; CHECK-NEXT: Args:
-; CHECK-NEXT:  - String:       Cannot interchange loops due to dependences.
+; CHECK-NEXT:  - String:          All loops have dependencies in all directions.
 define void @issue46867(ptr noundef captures(none) %s, i32 noundef %c, ptr noundef readonly captures(none) %ff) {
 entry:
   %tobool7.not = icmp eq i32 %c, 0
@@ -121,7 +121,7 @@ land.end:
 ; CHECK-NEXT: Name:            Dependence
 ; CHECK-NEXT: Function:        issue47401
 ; CHECK-NEXT: Args:
-; CHECK-NEXT:  - String:       Cannot interchange loops due to dependences.
+; CHECK-NEXT:  - String:          All loops have dependencies in all directions.
 define void @issue47401(ptr noundef writeonly captures(none) %e, ptr noundef readonly captures(none) %bb) {
 entry:
   br label %for.cond1.preheader
@@ -175,7 +175,7 @@ land.end:
 ; CHECK-NEXT: Name:            Dependence
 ; CHECK-NEXT: Function:        issue47295
 ; CHECK-NEXT: Args:
-; CHECK-NEXT:  - String:       Cannot interchange loops due to dependences.
+; CHECK-NEXT:  - String:          All loops have dependencies in all directions.
 define void @issue47295(ptr noundef captures(none) %f, ptr noundef writeonly captures(none) %cc) {
 entry:
   br label %for.cond1.preheader
@@ -221,7 +221,7 @@ for.body4:
 ; CHECK-NEXT: Name:            Dependence
 ; CHECK-NEXT: Function:        issue54176
 ; CHECK-NEXT: Args:
-; CHECK-NEXT:  - String:       Cannot interchange loops due to dependences.
+; CHECK-NEXT:  - String:          All loops have dependencies in all directions.
 define void @issue54176(i32 noundef %n, i32 noundef %m, ptr noundef captures(none) %aa, ptr noundef readonly captures(none) %bb, ptr noundef writeonly captures(none) %cc) {
 
 entry:
diff --git a/llvm/test/Transforms/LoopInterchange/loop-interchange-optimization-remarks.ll b/llvm/test/Transforms/LoopInterchange/loop-interchange-optimization-remarks.ll
index 73a566a310157..14836ba73433d 100644
--- a/llvm/test/Transforms/LoopInterchange/loop-interchange-optimization-remarks.ll
+++ b/llvm/test/Transforms/LoopInterchange/loop-interchange-optimization-remarks.ll
@@ -71,7 +71,7 @@ for.end19:
 ; CHECK-NEXT: Name:            Dependence
 ; CHECK-NEXT: Function:        test01
 ; CHECK-NEXT: Args:
-; CHECK-NEXT:   - String:          Cannot interchange loops due to dependences.
+; CHECK-NEXT:   - String:          All loops have dependencies in all directions.
 ; CHECK-NEXT: ...
 
 ; DELIN: --- !Analysis
@@ -147,7 +147,7 @@ define void @test02(i32 %k, i32 %N) {
 ; CHECK-NEXT: Name:            Dependence
 ; CHECK-NEXT: Function:        test02
 ; CHECK-NEXT: Args:
-; CHECK-NEXT:   - String:          Cannot interchange loops due to dependences.
+; CHECK-NEXT:   - String:          All loops have dependencies in all directions.
 ; CHECK-NEXT: ...
 
 ; DELIN: --- !Analysis
@@ -290,7 +290,7 @@ for.end17:
 ; CHECK-NEXT: Name:            Dependence
 ; CHECK-NEXT: Function:        test04
 ; CHECK-NEXT: Args:
-; CHECK-NEXT:   - String:          Cannot interchange loops due to dependences.
+; CHECK-NEXT:   - String:          All loops have dependencies in all directions.
 ; CHECK-NEXT: ...
 
 ; DELIN: --- !Missed
diff --git a/llvm/test/Transforms/LoopInterchange/unique-dep-matrix.ll b/llvm/test/Transforms/LoopInterchange/unique-dep-matrix.ll
index 68089b43121c5..3af9e7304e3be 100644
--- a/llvm/test/Transforms/LoopInterchange/unique-dep-matrix.ll
+++ b/llvm/test/Transforms/LoopInterchange/unique-dep-matrix.ll
@@ -2,14 +2,13 @@
 ; RUN: opt < %s -passes=loop-interchange -S -debug 2>&1 | FileCheck %s
 
 ; CHECK:       Dependency matrix before interchange:
-; CHECK-NEXT:  * *
 ; CHECK-NEXT:  = *
 ; CHECK-NEXT:  < *
 ; CHECK-NEXT:  Processing InnerLoopId
 
 ; This example is taken from github issue #54176
 ;
-define void @foo(i32 noundef %n, i32 noundef %m, ptr nocapture noundef %aa, ptr nocapture noundef readonly %bb, ptr nocapture noundef writeonly %cc) {
+define void @foo(i32 noundef %n, i32 noundef %m, ptr nocapture noundef noalias %aa, ptr nocapture noundef readonly noalias %bb, ptr nocapture noundef writeonly noalias %cc) {
 entry:
   %arrayidx7 = getelementptr inbounds i8, ptr %aa, i64 512
   br label %for.cond1.preheader

kasuga-fj · 2025-07-16T09:50:59Z

compile-time improvements: https://llvm-compile-time-tracker.com/compare.php?from=23e0caaa5d346bdc16ee579504b90a723771860a&to=2cba425f2096f8314bc064fe7d42700dec193ed6&stat=instructions:u

kasuga-fj · 2025-07-16T09:53:03Z

-; CHECK:      Dependency matrix before interchange:
-; CHECK-NEXT: * *
-; CHECK-NEXT: Processing InnerLoopId = 1 and OuterLoopId = 0
+; CHECK:      --- !Missed
+; CHECK-NEXT: Pass:            loop-interchange
+; CHECK-NEXT: Name:            Dependence
+; CHECK-NEXT: Function:        may_alias
+; CHECK-NEXT: Args:
+; CHECK-NEXT:   - String:          All loops have dependencies in all directions.
+; CHECK-NEXT: ...


Changed because the previous CHECK directives check the debug outputs, which are no longer printed due to this change.

kasuga-fj · 2025-07-16T09:54:50Z

-; CHECK-NEXT:  * *
 ; CHECK-NEXT:  = *
 ; CHECK-NEXT:  < *
 ; CHECK-NEXT:  Processing InnerLoopId

 ; This example is taken from github issue #54176
 ;
-define void @foo(i32 noundef %n, i32 noundef %m, ptr nocapture noundef %aa, ptr nocapture noundef readonly %bb, ptr nocapture noundef writeonly %cc) {
+define void @foo(i32 noundef %n, i32 noundef %m, ptr nocapture noundef noalias %aa, ptr nocapture noundef readonly noalias %bb, ptr nocapture noundef writeonly noalias %cc) {


Added noalias to all ptr arguments to eliminate the * * dependency.

kasuga-fj · 2025-08-07T13:16:24Z

Ping

madhur13490 · 2025-09-25T08:05:13Z

+        // If there is a direction vector with all entries being '*', we cannot
+        // prove the legality of the interchange for arbitrary pairs of loops.
+        // Exit early in this case to save compile time.
+        if (all_of(Dep, [](char C) { return C == '*'; })) {


Can be reworded to the following for clarity.

// If all the elements of any direction vector have only '*', legality can't be proven.
// Exit early to save compile time.

fixed, thanks

madhur13490

LGTM except slight rewording of the comment.

* main: (502 commits) GlobalISel: Adjust insert point when expanding G_[SU]DIVREM (llvm#160683) [LV] Add coverage for fixing-up scalar resume values (llvm#160492) AMDGPU: Convert wave_any test to use update_mc_test_checks [LV] Add partial reduction tests multiplying extend with constants. Revert "[MLIR] Implement remark emitting policies in MLIR" (llvm#160681) [NFC][InstSimplify] Refactor fminmax-folds.ll test (llvm#160504) [LoongArch] Pre-commit tests for [x]vldi instructions with special constant splats (llvm#159228) [BOLT] Fix dwarf5-dwoid-no-dwoname.s (llvm#160676) [lldb][test] Refactor and expand TestMemoryRegionDirtyPages.py (llvm#156035) [gn build] Port 833d5f0 AMDGPU: Ensure both wavesize features are not set (llvm#159234) [LoopInterchange] Bail out when finding a dependency with all `*` elements (llvm#149049) [libc++] Avoid constructing additional objects when using map::at (llvm#157866) [lldb][test] Make hex prefix optional in DWARF union types test [X86] Add missing prefixes to trunc-sat tests (llvm#160662) [AMDGPU] Fix vector legalization for bf16 valu ops (llvm#158439) [LoongArch][NFC] Pre-commit tests for `[x]vadda.{b/h/w/d}` [mlir][tosa] Relax constraint on matmul verifier requiring equal operand types (llvm#155799) [clang][Sema] Accept gnu format attributes (llvm#160255) [LoongArch][NFC] Add tests for element extraction from binary add operation (llvm#159725) ...

…ments (llvm#149049) If a direction vector with all `*` elements, like `[* * *]`, is present, it indicates that none of the loop pairs are legal to interchange. In such cases, continuing the analysis is meaningless. This patch introduces a check to detect such direction vectors and exits early when one is found. This slightly reduces compile time.

[LoopInterchange] Exit early when all loops have deps in all directions

24a7257

llvmbot added the llvm:transforms label Jul 16, 2025

kasuga-fj commented Jul 16, 2025

View reviewed changes

kasuga-fj requested review from madhur13490 and sjoerdmeijer July 16, 2025 09:55

Merge branch 'main' into feature/loop-interchange-early-exit

144582a

kasuga-fj changed the title ~~[LoopInterchange] Exit early when all loops have deps in all directions~~ [LoopInterchange] Bail out when finding a dependency with all * elements Sep 25, 2025

kasuga-fj added 2 commits September 25, 2025 07:21

Merge branch 'main' into loop-interchange-early-exit

5502f32

fix test

c51edff

kasuga-fj requested a review from Meinersbur September 25, 2025 07:30

madhur13490 reviewed Sep 25, 2025

View reviewed changes

madhur13490 approved these changes Sep 25, 2025

View reviewed changes

adjust comment

0e4e759

kasuga-fj enabled auto-merge (squash) September 25, 2025 09:05

kasuga-fj merged commit 2c3453a into llvm:main Sep 25, 2025
9 checks passed

kasuga-fj deleted the loop-interchange-early-exit branch September 25, 2025 09:37

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

[LoopInterchange] Bail out when finding a dependency with all `*` elements#149049

[LoopInterchange] Bail out when finding a dependency with all `*` elements#149049
kasuga-fj merged 5 commits intollvm:mainfrom
kasuga-fj:loop-interchange-early-exit

kasuga-fj commented Jul 16, 2025 •

edited

Loading

Uh oh!

llvmbot commented Jul 16, 2025

Uh oh!

kasuga-fj commented Jul 16, 2025

Uh oh!

kasuga-fj Jul 16, 2025 •

edited

Loading

Uh oh!

kasuga-fj Jul 16, 2025

Uh oh!

kasuga-fj commented Aug 7, 2025

Uh oh!

madhur13490 Sep 25, 2025

Uh oh!

kasuga-fj Sep 25, 2025

Uh oh!

madhur13490 left a comment

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

Conversation

kasuga-fj commented Jul 16, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

llvmbot commented Jul 16, 2025

Uh oh!

kasuga-fj commented Jul 16, 2025

Uh oh!

kasuga-fj Jul 16, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

kasuga-fj Jul 16, 2025

Choose a reason for hiding this comment

Uh oh!

kasuga-fj commented Aug 7, 2025

Uh oh!

madhur13490 Sep 25, 2025

Choose a reason for hiding this comment

Uh oh!

kasuga-fj Sep 25, 2025

Choose a reason for hiding this comment

Uh oh!

madhur13490 left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

kasuga-fj commented Jul 16, 2025 •

edited

Loading

kasuga-fj Jul 16, 2025 •

edited

Loading