https://github.com/kasuga-fj updated https://github.com/llvm/llvm-project/pull/193481
>From 4f1a3362d2464fdddb3aac18c4f7f1c82a377b53 Mon Sep 17 00:00:00 2001 From: Ryotaro Kasuga <[email protected]> Date: Wed, 22 Apr 2026 11:48:40 +0000 Subject: [PATCH] [LoopInterchange] Change the cost model to interchange `[* =]` --- .../lib/Transforms/Scalar/LoopInterchange.cpp | 35 +++++++- .../LoopInterchange/dependency-all-eq.ll | 83 +++++++------------ 2 files changed, 63 insertions(+), 55 deletions(-) diff --git a/llvm/lib/Transforms/Scalar/LoopInterchange.cpp b/llvm/lib/Transforms/Scalar/LoopInterchange.cpp index bf21b371157bd..6873c6e99ed64 100644 --- a/llvm/lib/Transforms/Scalar/LoopInterchange.cpp +++ b/llvm/lib/Transforms/Scalar/LoopInterchange.cpp @@ -1666,10 +1666,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. + BasePtr2Score[BasePtr].second = true; + 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. + BasePtr2Score[BasePtr].first = true; + 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: {{.*}} _______________________________________________ llvm-branch-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
