llvmorg-github-actions[bot] wrote:
<!--LLVM PR SUMMARY COMMENT-->
@llvm/pr-subscribers-llvm-transforms
Author: Ryotaro Kasuga (kasuga-fj)
<details>
<summary>Changes</summary>
This patch modifies the cost model to interchange loops with `[* =]`
dependency. This pattern typically appears when the induction variable of the
outer loop is not used within the loop body, for example:
```c
for (repeat=0; repeat<N; repeat++)
for (i=0; i<M; i++)
A[i]++;
```
Interchanging these loops yields:
```c
for (i=0; i<M; i++)
for (repeat=0; repeat<N; repeat++)
A[i]++;
```
This transformation improves spatial locality.
One downside of this transformation is that the innermost loop is no longer
vectorizable. Ideally, this interchange should be applied after vectorization.
---
Full diff: https://github.com/llvm/llvm-project/pull/193481.diff
2 Files Affected:
- (modified) llvm/lib/Transforms/Scalar/LoopInterchange.cpp (+33-2)
- (modified) llvm/test/Transforms/LoopInterchange/dependency-all-eq.ll (+30-53)
``````````diff
diff --git a/llvm/lib/Transforms/Scalar/LoopInterchange.cpp
b/llvm/lib/Transforms/Scalar/LoopInterchange.cpp
index 46ec9cf8ce4ac..a670a153410be 100644
--- a/llvm/lib/Transforms/Scalar/LoopInterchange.cpp
+++ b/llvm/lib/Transforms/Scalar/LoopInterchange.cpp
@@ -1760,10 +1760,41 @@ int LoopInterchangeProfitability::getInstrOrderCost() {
std::optional<const SCEV *> InnerCoeff =
getAddRecCoefficient(*SE, Access, InnerLoop);
- if (!OuterCoeff.has_value() || !*OuterCoeff || !InnerCoeff.has_value() ||
- !*InnerCoeff)
+ if (!OuterCoeff.has_value() || !InnerCoeff.has_value())
continue;
+ if (!*OuterCoeff && !*InnerCoeff)
+ continue;
+
+ if (!*OuterCoeff && *InnerCoeff) {
+ // If we find a coefficient for the inner loop but no coefficient for
+ // the outer loop, then the access is of the form like:
+ //
+ // for (i=0; i<N; i++)
+ // for (j=0; j<M; j++)
+ // A[j] = ...;
+ //
+ // In this case, we treat it as a bad order, since interchanging the
+ // loops would make the access loop invariant with respect to the inner
+ // loop (the i-loop), which would improve locality.
+ BadBasePtrs.insert(BasePtr);
+ continue;
+ }
+
+ if (*OuterCoeff && !*InnerCoeff) {
+ // If we find a coefficient for the outer loop but no coefficient for
+ // the inner loop, then the access is of the form like:
+ //
+ // for (i=0; i<N; i++)
+ // for (j=0; j<M; j++)
+ // A[i] = ...;
+ //
+ // Due to the same reason as the previous case, we regard it as a good
+ // order.
+ GoodBasePtrs.insert(BasePtr);
+ continue;
+ }
+
// This heuristic assumes that a smaller step recurrence implies that the
// induction variable corresponding to the loop is used in the inner
// dimension of the array. Placing such a loop in the inner position
would
diff --git a/llvm/test/Transforms/LoopInterchange/dependency-all-eq.ll
b/llvm/test/Transforms/LoopInterchange/dependency-all-eq.ll
index 489dd88ca48c7..1902f48d8ee25 100644
--- a/llvm/test/Transforms/LoopInterchange/dependency-all-eq.ll
+++ b/llvm/test/Transforms/LoopInterchange/dependency-all-eq.ll
@@ -13,57 +13,36 @@
;
define void @all_eq(ptr %A) {
-; CHECK-PROFIT-INSTORDER-LABEL: define void @all_eq(
-; CHECK-PROFIT-INSTORDER-SAME: ptr [[A:%.*]]) {
-; CHECK-PROFIT-INSTORDER-NEXT: [[ENTRY:.*]]:
-; CHECK-PROFIT-INSTORDER-NEXT: br label %[[LOOP_I_HEADER:.*]]
-; CHECK-PROFIT-INSTORDER: [[LOOP_I_HEADER]]:
-; CHECK-PROFIT-INSTORDER-NEXT: [[I:%.*]] = phi i64 [ 0, %[[ENTRY]] ], [
[[I_INC:%.*]], %[[LOOP_I_LATCH:.*]] ]
-; CHECK-PROFIT-INSTORDER-NEXT: br label %[[LOOP_J:.*]]
-; CHECK-PROFIT-INSTORDER: [[LOOP_J]]:
-; CHECK-PROFIT-INSTORDER-NEXT: [[J:%.*]] = phi i64 [ 0, %[[LOOP_I_HEADER]]
], [ [[J_INC:%.*]], %[[LOOP_J]] ]
-; CHECK-PROFIT-INSTORDER-NEXT: [[GEP:%.*]] = getelementptr i8, ptr [[A]],
i64 [[J]]
-; CHECK-PROFIT-INSTORDER-NEXT: store i8 0, ptr [[GEP]], align 1
-; CHECK-PROFIT-INSTORDER-NEXT: [[J_INC]] = add i64 [[J]], 1
-; CHECK-PROFIT-INSTORDER-NEXT: [[EC_J:%.*]] = icmp eq i64 [[J_INC]], 100
-; CHECK-PROFIT-INSTORDER-NEXT: br i1 [[EC_J]], label %[[LOOP_I_LATCH]],
label %[[LOOP_J]]
-; CHECK-PROFIT-INSTORDER: [[LOOP_I_LATCH]]:
-; CHECK-PROFIT-INSTORDER-NEXT: [[I_INC]] = add i64 [[I]], 1
-; CHECK-PROFIT-INSTORDER-NEXT: [[EC_I:%.*]] = icmp eq i64 [[I_INC]], 100
-; CHECK-PROFIT-INSTORDER-NEXT: br i1 [[EC_I]], label %[[EXIT:.*]], label
%[[LOOP_I_HEADER]]
-; CHECK-PROFIT-INSTORDER: [[EXIT]]:
-; CHECK-PROFIT-INSTORDER-NEXT: ret void
-;
-; CHECK-PROFIT-IGNORE-LABEL: define void @all_eq(
-; CHECK-PROFIT-IGNORE-SAME: ptr [[A:%.*]]) {
-; CHECK-PROFIT-IGNORE-NEXT: [[ENTRY:.*:]]
-; CHECK-PROFIT-IGNORE-NEXT: br label %[[LOOP_J_PREHEADER:.*]]
-; CHECK-PROFIT-IGNORE: [[LOOP_I_HEADER_PREHEADER:.*]]:
-; CHECK-PROFIT-IGNORE-NEXT: br label %[[LOOP_I_HEADER:.*]]
-; CHECK-PROFIT-IGNORE: [[LOOP_I_HEADER]]:
-; CHECK-PROFIT-IGNORE-NEXT: [[I:%.*]] = phi i64 [ [[I_INC:%.*]],
%[[LOOP_I_LATCH:.*]] ], [ 0, %[[LOOP_I_HEADER_PREHEADER]] ]
-; CHECK-PROFIT-IGNORE-NEXT: br label %[[LOOP_J_SPLIT1:.*]]
-; CHECK-PROFIT-IGNORE: [[LOOP_J_PREHEADER]]:
-; CHECK-PROFIT-IGNORE-NEXT: br label %[[LOOP_J:.*]]
-; CHECK-PROFIT-IGNORE: [[LOOP_J]]:
-; CHECK-PROFIT-IGNORE-NEXT: [[J:%.*]] = phi i64 [ [[TMP0:%.*]],
%[[LOOP_J_SPLIT:.*]] ], [ 0, %[[LOOP_J_PREHEADER]] ]
-; CHECK-PROFIT-IGNORE-NEXT: br label %[[LOOP_I_HEADER_PREHEADER]]
-; CHECK-PROFIT-IGNORE: [[LOOP_J_SPLIT1]]:
-; CHECK-PROFIT-IGNORE-NEXT: [[GEP:%.*]] = getelementptr i8, ptr [[A]], i64
[[J]]
-; CHECK-PROFIT-IGNORE-NEXT: store i8 0, ptr [[GEP]], align 1
-; CHECK-PROFIT-IGNORE-NEXT: [[J_INC:%.*]] = add i64 [[J]], 1
-; CHECK-PROFIT-IGNORE-NEXT: [[EC_J:%.*]] = icmp eq i64 [[J_INC]], 100
-; CHECK-PROFIT-IGNORE-NEXT: br label %[[LOOP_I_LATCH]]
-; CHECK-PROFIT-IGNORE: [[LOOP_J_SPLIT]]:
-; CHECK-PROFIT-IGNORE-NEXT: [[TMP0]] = add i64 [[J]], 1
-; CHECK-PROFIT-IGNORE-NEXT: [[TMP1:%.*]] = icmp eq i64 [[TMP0]], 100
-; CHECK-PROFIT-IGNORE-NEXT: br i1 [[TMP1]], label %[[EXIT:.*]], label
%[[LOOP_J]]
-; CHECK-PROFIT-IGNORE: [[LOOP_I_LATCH]]:
-; CHECK-PROFIT-IGNORE-NEXT: [[I_INC]] = add i64 [[I]], 1
-; CHECK-PROFIT-IGNORE-NEXT: [[EC_I:%.*]] = icmp eq i64 [[I_INC]], 100
-; CHECK-PROFIT-IGNORE-NEXT: br i1 [[EC_I]], label %[[LOOP_J_SPLIT]], label
%[[LOOP_I_HEADER]]
-; CHECK-PROFIT-IGNORE: [[EXIT]]:
-; CHECK-PROFIT-IGNORE-NEXT: ret void
+; CHECK-LABEL: define void @all_eq(
+; CHECK-SAME: ptr [[A:%.*]]) {
+; CHECK-NEXT: [[ENTRY:.*:]]
+; CHECK-NEXT: br label %[[LOOP_J_PREHEADER:.*]]
+; CHECK: [[LOOP_I_HEADER_PREHEADER:.*]]:
+; CHECK-NEXT: br label %[[LOOP_I_HEADER:.*]]
+; CHECK: [[LOOP_I_HEADER]]:
+; CHECK-NEXT: [[I:%.*]] = phi i64 [ [[I_INC:%.*]], %[[LOOP_I_LATCH:.*]] ],
[ 0, %[[LOOP_I_HEADER_PREHEADER]] ]
+; CHECK-NEXT: br label %[[LOOP_J_SPLIT1:.*]]
+; CHECK: [[LOOP_J_PREHEADER]]:
+; CHECK-NEXT: br label %[[LOOP_J:.*]]
+; CHECK: [[LOOP_J]]:
+; CHECK-NEXT: [[J:%.*]] = phi i64 [ [[TMP0:%.*]], %[[LOOP_J_SPLIT:.*]] ], [
0, %[[LOOP_J_PREHEADER]] ]
+; CHECK-NEXT: br label %[[LOOP_I_HEADER_PREHEADER]]
+; CHECK: [[LOOP_J_SPLIT1]]:
+; CHECK-NEXT: [[GEP:%.*]] = getelementptr i8, ptr [[A]], i64 [[J]]
+; CHECK-NEXT: store i8 0, ptr [[GEP]], align 1
+; CHECK-NEXT: [[J_INC:%.*]] = add i64 [[J]], 1
+; CHECK-NEXT: [[EC_J:%.*]] = icmp eq i64 [[J_INC]], 100
+; CHECK-NEXT: br label %[[LOOP_I_LATCH]]
+; CHECK: [[LOOP_J_SPLIT]]:
+; CHECK-NEXT: [[TMP0]] = add i64 [[J]], 1
+; CHECK-NEXT: [[TMP1:%.*]] = icmp eq i64 [[TMP0]], 100
+; CHECK-NEXT: br i1 [[TMP1]], label %[[EXIT:.*]], label %[[LOOP_J]]
+; CHECK: [[LOOP_I_LATCH]]:
+; CHECK-NEXT: [[I_INC]] = add i64 [[I]], 1
+; CHECK-NEXT: [[EC_I:%.*]] = icmp eq i64 [[I_INC]], 100
+; CHECK-NEXT: br i1 [[EC_I]], label %[[LOOP_J_SPLIT]], label
%[[LOOP_I_HEADER]]
+; CHECK: [[EXIT]]:
+; CHECK-NEXT: ret void
;
entry:
br label %loop.i.header
@@ -174,5 +153,3 @@ loop.i.latch:
exit:
ret void
}
-;; NOTE: These prefixes are unused and the list is autogenerated. Do not add
tests below this line:
-; CHECK: {{.*}}
``````````
</details>
https://github.com/llvm/llvm-project/pull/193481
_______________________________________________
llvm-branch-commits mailing list
[email protected]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
