https://github.com/kasuga-fj updated https://github.com/llvm/llvm-project/pull/203240
>From 2a1767cc7d4476037ad9b41192b310ec3857d884 Mon Sep 17 00:00:00 2001 From: Ryotaro Kasuga <[email protected]> Date: Thu, 11 Jun 2026 09:09:40 +0000 Subject: [PATCH] [LoopInterchange] Add test for extra reduction use in inner loop (NFC) --- .../reduction-extra-use-in-inner-loop.ll | 281 ++++++++++++++++++ 1 file changed, 281 insertions(+) create mode 100644 llvm/test/Transforms/LoopInterchange/reduction-extra-use-in-inner-loop.ll diff --git a/llvm/test/Transforms/LoopInterchange/reduction-extra-use-in-inner-loop.ll b/llvm/test/Transforms/LoopInterchange/reduction-extra-use-in-inner-loop.ll new file mode 100644 index 0000000000000..12493e954444f --- /dev/null +++ b/llvm/test/Transforms/LoopInterchange/reduction-extra-use-in-inner-loop.ll @@ -0,0 +1,281 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 6 +; RUN: opt < %s -passes=loop-interchange -loop-interchange-profitabilities=ignore -S | FileCheck %s + +; sum = 0; +; for (i = 0, sum_i = sum; i < 2; i++) +; for (j = 0; j < 2; j++) { +; sum += A[j][i]; +; B[j][i] = sum_i; +; } +; +; Interchanging the loops will become as follows: +; +; sum = 0; +; for (j = 0, sum_j = sum; j < 2; j++) +; for (i = 0; i < 2; i++) { +; sum += A[j][i]; +; B[j][i] = sum_j; +; } +; +; This is invalid transformation. Consider the case when `A` is as follows: +; +; A = {{ 0, 0 }, { 1, 1 }} +; +; In this case, `sum_i` evolves 0 -> 1, while `sum_j` evolves 0 -> 0. +; +define i8 @extra_reduction_use_in_inner0(ptr noalias %A, ptr noalias %B) { +; CHECK-LABEL: define i8 @extra_reduction_use_in_inner0( +; CHECK-SAME: ptr noalias [[A:%.*]], ptr noalias [[B:%.*]]) { +; CHECK-NEXT: [[INNER_PREHEADER:.*:]] +; CHECK-NEXT: br label %[[INNER:.*]] +; CHECK: [[OUTER_HEADER_PREHEADER1:.*]]: +; CHECK-NEXT: br label %[[OUTER_HEADER_PREHEADER:.*]] +; CHECK: [[OUTER_HEADER_PREHEADER]]: +; CHECK-NEXT: [[I:%.*]] = phi i64 [ [[I_NEXT:%.*]], %[[OUTER_LATCH:.*]] ], [ 0, %[[OUTER_HEADER_PREHEADER1]] ] +; CHECK-NEXT: [[SUM_INNER:%.*]] = phi i8 [ [[SUM_NEXT:%.*]], %[[OUTER_LATCH]] ], [ [[SUM:%.*]], %[[OUTER_HEADER_PREHEADER1]] ] +; CHECK-NEXT: br label %[[INNER_SPLIT1:.*]] +; CHECK: [[INNER]]: +; CHECK-NEXT: br label %[[INNER1:.*]] +; CHECK: [[INNER1]]: +; CHECK-NEXT: [[J:%.*]] = phi i64 [ [[TMP2:%.*]], %[[INNER_SPLIT:.*]] ], [ 0, %[[INNER]] ] +; CHECK-NEXT: [[SUM]] = phi i8 [ [[SUM_LCSSA:%.*]], %[[INNER_SPLIT]] ], [ 0, %[[INNER]] ] +; CHECK-NEXT: br label %[[OUTER_HEADER_PREHEADER1]] +; CHECK: [[INNER_SPLIT1]]: +; CHECK-NEXT: [[GEP_A:%.*]] = getelementptr [2 x i8], ptr [[A]], i64 [[J]], i64 [[I]] +; CHECK-NEXT: [[A:%.*]] = load i8, ptr [[GEP_A]], align 1 +; CHECK-NEXT: [[SUM_NEXT]] = add i8 [[SUM_INNER]], [[A]] +; CHECK-NEXT: [[GEP_B:%.*]] = getelementptr [2 x i8], ptr [[B]], i64 [[J]], i64 [[I]] +; CHECK-NEXT: store i8 [[SUM]], ptr [[GEP_B]], align 1 +; CHECK-NEXT: [[TMP0:%.*]] = add i64 [[J]], 1 +; CHECK-NEXT: [[TMP1:%.*]] = icmp eq i64 [[TMP0]], 2 +; CHECK-NEXT: br label %[[OUTER_LATCH]] +; CHECK: [[INNER_SPLIT]]: +; CHECK-NEXT: [[SUM_LCSSA]] = phi i8 [ [[SUM_NEXT]], %[[OUTER_LATCH]] ] +; CHECK-NEXT: [[TMP2]] = add i64 [[J]], 1 +; CHECK-NEXT: [[TMP3:%.*]] = icmp eq i64 [[TMP2]], 2 +; CHECK-NEXT: br i1 [[TMP3]], label %[[EXIT:.*]], label %[[INNER1]] +; CHECK: [[OUTER_LATCH]]: +; CHECK-NEXT: [[I_NEXT]] = add i64 [[I]], 1 +; CHECK-NEXT: [[EC_I:%.*]] = icmp eq i64 [[I_NEXT]], 2 +; CHECK-NEXT: br i1 [[EC_I]], label %[[INNER_SPLIT]], label %[[OUTER_HEADER_PREHEADER]] +; CHECK: [[EXIT]]: +; CHECK-NEXT: [[RES:%.*]] = phi i8 [ [[SUM_LCSSA]], %[[INNER_SPLIT]] ] +; CHECK-NEXT: ret i8 [[RES]] +; +entry: + br label %outer.header + +outer.header: + %i = phi i64 [ 0, %entry ], [ %i.next, %outer.latch ] + %sum.outer = phi i8 [ 0, %entry ], [ %sum.lcssa, %outer.latch ] + br label %inner + +inner: + %j = phi i64 [ 0, %outer.header ], [ %j.next, %inner ] + %sum.inner = phi i8 [ %sum.outer, %outer.header ], [ %sum.inner.next, %inner ] + %gep.A = getelementptr [2 x i8], ptr %A, i64 %j, i64 %i + %a = load i8, ptr %gep.A + %sum.inner.next = add i8 %sum.inner, %a + %gep.B = getelementptr [2 x i8], ptr %B, i64 %j, i64 %i + store i8 %sum.outer, ptr %gep.B + %j.next = add i64 %j, 1 + %ec.j = icmp eq i64 %j.next, 2 + br i1 %ec.j, label %outer.latch, label %inner + +outer.latch: + %sum.lcssa = phi i8 [ %sum.inner.next, %inner ] + %i.next = add i64 %i, 1 + %ec.i = icmp eq i64 %i.next, 2 + br i1 %ec.i, label %exit, label %outer.header + +exit: + %res = phi i8 [ %sum.lcssa, %outer.latch ] + ret i8 %res +} + +; sum = 0; +; for (i = 0; i < 2; i++) +; for (j = 0; j < 2; j++) { +; sum += A[j][i]; +; B[j][i] = sum; +; } +; +; Interchanging the loops will become as follows: +; +; sum = 0; +; for (j = 0; j < 2; j++) +; for (i = 0; i < 2; i++) { +; sum += A[j][i]; +; B[j][i] = sum; +; } +; +; This is invalid transformation. Consider the case when `A` is as follows: +; +; A = {{ 0, 1 }, { 0, 0 }} +; +; In this case, in the original loops, `sum` evolves 0 -> 0 -> 1 -> 1, while in +; the interchanged loops, `sum` evolves 0 -> 1 -> 1 -> 1 +; +define i8 @extra_reduction_use_in_inner1(ptr noalias %A, ptr noalias %B) { +; CHECK-LABEL: define i8 @extra_reduction_use_in_inner1( +; CHECK-SAME: ptr noalias [[A:%.*]], ptr noalias [[B:%.*]]) { +; CHECK-NEXT: [[ENTRY:.*]]: +; CHECK-NEXT: br label %[[OUTER_HEADER:.*]] +; CHECK: [[OUTER_HEADER]]: +; CHECK-NEXT: [[I:%.*]] = phi i64 [ 0, %[[ENTRY]] ], [ [[I_NEXT:%.*]], %[[OUTER_LATCH:.*]] ] +; CHECK-NEXT: [[SUM_OUTER:%.*]] = phi i8 [ 0, %[[ENTRY]] ], [ [[SUM_LCSSA:%.*]], %[[OUTER_LATCH]] ] +; CHECK-NEXT: br label %[[INNER:.*]] +; CHECK: [[INNER]]: +; CHECK-NEXT: [[J:%.*]] = phi i64 [ 0, %[[OUTER_HEADER]] ], [ [[J_NEXT:%.*]], %[[INNER]] ] +; CHECK-NEXT: [[SUM_INNER:%.*]] = phi i8 [ [[SUM_OUTER]], %[[OUTER_HEADER]] ], [ [[SUM_NEXT:%.*]], %[[INNER]] ] +; CHECK-NEXT: [[GEP_A:%.*]] = getelementptr [2 x i8], ptr [[A]], i64 [[J]], i64 [[I]] +; CHECK-NEXT: [[A:%.*]] = load i8, ptr [[GEP_A]], align 1 +; CHECK-NEXT: [[SUM_NEXT]] = add i8 [[SUM_INNER]], [[A]] +; CHECK-NEXT: [[GEP_B:%.*]] = getelementptr [2 x i8], ptr [[B]], i64 [[J]], i64 [[I]] +; CHECK-NEXT: store i8 [[SUM_NEXT]], ptr [[GEP_B]], align 1 +; CHECK-NEXT: [[J_NEXT]] = add i64 [[J]], 1 +; CHECK-NEXT: [[EC_J:%.*]] = icmp eq i64 [[J_NEXT]], 2 +; CHECK-NEXT: br i1 [[EC_J]], label %[[OUTER_LATCH]], label %[[INNER]] +; CHECK: [[OUTER_LATCH]]: +; CHECK-NEXT: [[SUM_LCSSA]] = phi i8 [ [[SUM_NEXT]], %[[INNER]] ] +; CHECK-NEXT: [[I_NEXT]] = add i64 [[I]], 1 +; CHECK-NEXT: [[EC_I:%.*]] = icmp eq i64 [[I_NEXT]], 2 +; CHECK-NEXT: br i1 [[EC_I]], label %[[EXIT:.*]], label %[[OUTER_HEADER]] +; CHECK: [[EXIT]]: +; CHECK-NEXT: [[RES:%.*]] = phi i8 [ [[SUM_LCSSA]], %[[OUTER_LATCH]] ] +; CHECK-NEXT: ret i8 [[RES]] +; +entry: + br label %outer.header + +outer.header: + %i = phi i64 [ 0, %entry ], [ %i.next, %outer.latch ] + %sum.outer = phi i8 [ 0, %entry ], [ %sum.lcssa, %outer.latch ] + br label %inner + +inner: + %j = phi i64 [ 0, %outer.header ], [ %j.next, %inner ] + %sum.inner = phi i8 [ %sum.outer, %outer.header ], [ %sum.inner.next, %inner ] + %gep.A = getelementptr [2 x i8], ptr %A, i64 %j, i64 %i + %a = load i8, ptr %gep.A + %sum.inner.next = add i8 %sum.inner, %a + %gep.B = getelementptr [2 x i8], ptr %B, i64 %j, i64 %i + store i8 %sum.inner.next, ptr %gep.B + %j.next = add i64 %j, 1 + %ec.j = icmp eq i64 %j.next, 2 + br i1 %ec.j, label %outer.latch, label %inner + +outer.latch: + %sum.lcssa = phi i8 [ %sum.inner.next, %inner ] + %i.next = add i64 %i, 1 + %ec.i = icmp eq i64 %i.next, 2 + br i1 %ec.i, label %exit, label %outer.header + +exit: + %res = phi i8 [ %sum.lcssa, %outer.latch ] + ret i8 %res +} + +; sum = 0; +; for (i = 0, sum_i = sum; i < 2; i++) +; for (j = 0; j < 2; j++) +; for (k = 0; k < 2; k++) { +; sum += A[j][i]; +; B[j][i] = sum_i; +; } +; +; In this case, interchanging the j-loop and the k-loop is legal. +; +define i8 @extra_reduction_use_in_inner2(ptr noalias %A, ptr noalias %B) { +; CHECK-LABEL: define i8 @extra_reduction_use_in_inner2( +; CHECK-SAME: ptr noalias [[A:%.*]], ptr noalias [[B:%.*]]) { +; CHECK-NEXT: [[ENTRY:.*]]: +; CHECK-NEXT: br label %[[OUTER_HEADER:.*]] +; CHECK: [[OUTER_HEADER]]: +; CHECK-NEXT: [[I:%.*]] = phi i64 [ 0, %[[ENTRY]] ], [ [[I_NEXT:%.*]], %[[OUTER_LATCH:.*]] ] +; CHECK-NEXT: [[SUM_OUTER:%.*]] = phi i8 [ 0, %[[ENTRY]] ], [ [[SUM_OUTER_LCSSA:%.*]], %[[OUTER_LATCH]] ] +; CHECK-NEXT: br label %[[MIDDLE_HEADER_PREHEADER:.*]] +; CHECK: [[MIDDLE_HEADER_PREHEADER]]: +; CHECK-NEXT: br label %[[MIDDLE_HEADER:.*]] +; CHECK: [[MIDDLE_HEADER]]: +; CHECK-NEXT: [[J:%.*]] = phi i64 [ [[TMP2:%.*]], %[[MIDDLE_LATCH_SPLIT:.*]] ], [ 0, %[[MIDDLE_HEADER_PREHEADER]] ] +; CHECK-NEXT: [[SUM_MIDDLE:%.*]] = phi i8 [ [[SUM_MIDDLE_LCSSA:%.*]], %[[MIDDLE_LATCH_SPLIT]] ], [ [[SUM_OUTER]], %[[MIDDLE_HEADER_PREHEADER]] ] +; CHECK-NEXT: br label %[[INNER_PREHEADER:.*]] +; CHECK: [[INNER_PREHEADER]]: +; CHECK-NEXT: br label %[[INNER:.*]] +; CHECK: [[INNER]]: +; CHECK-NEXT: [[K:%.*]] = phi i64 [ [[TMP0:%.*]], %[[INNER_SPLIT:.*]] ], [ 0, %[[INNER_PREHEADER]] ] +; CHECK-NEXT: [[SUM_INNER:%.*]] = phi i8 [ [[SUM_INNER_NEXT:%.*]], %[[INNER_SPLIT]] ], [ [[SUM_MIDDLE]], %[[INNER_PREHEADER]] ] +; CHECK-NEXT: br label %[[INNER_SPLIT1:.*]] +; CHECK: [[INNER_SPLIT1]]: +; CHECK-NEXT: [[GEP_A:%.*]] = getelementptr [2 x [2 x i8]], ptr [[A]], i64 [[K]], i64 [[J]], i64 [[I]] +; CHECK-NEXT: [[A:%.*]] = load i8, ptr [[GEP_A]], align 1 +; CHECK-NEXT: [[SUM_INNER_NEXT]] = add i8 [[SUM_INNER]], [[A]] +; CHECK-NEXT: [[GEP_B:%.*]] = getelementptr [2 x [2 x i8]], ptr [[B]], i64 [[K]], i64 [[J]], i64 [[I]] +; CHECK-NEXT: store i8 [[SUM_OUTER]], ptr [[GEP_B]], align 1 +; CHECK-NEXT: [[K_NEXT:%.*]] = add i64 [[K]], 1 +; CHECK-NEXT: [[EC_K:%.*]] = icmp eq i64 [[K_NEXT]], 2 +; CHECK-NEXT: br label %[[MIDDLE_LATCH:.*]] +; CHECK: [[INNER_SPLIT]]: +; CHECK-NEXT: [[TMP0]] = add i64 [[K]], 1 +; CHECK-NEXT: [[TMP1:%.*]] = icmp eq i64 [[TMP0]], 2 +; CHECK-NEXT: br i1 [[TMP1]], label %[[MIDDLE_LATCH_SPLIT]], label %[[INNER]] +; CHECK: [[MIDDLE_LATCH]]: +; CHECK-NEXT: [[J_NEXT:%.*]] = add i64 [[J]], 1 +; CHECK-NEXT: [[EC_J:%.*]] = icmp eq i64 [[J_NEXT]], 2 +; CHECK-NEXT: br label %[[INNER_SPLIT]] +; CHECK: [[MIDDLE_LATCH_SPLIT]]: +; CHECK-NEXT: [[SUM_MIDDLE_LCSSA]] = phi i8 [ [[SUM_INNER_NEXT]], %[[INNER_SPLIT]] ] +; CHECK-NEXT: [[TMP2]] = add i64 [[J]], 1 +; CHECK-NEXT: [[TMP3:%.*]] = icmp eq i64 [[TMP2]], 2 +; CHECK-NEXT: br i1 [[TMP3]], label %[[OUTER_LATCH]], label %[[MIDDLE_HEADER]] +; CHECK: [[OUTER_LATCH]]: +; CHECK-NEXT: [[SUM_OUTER_LCSSA]] = phi i8 [ [[SUM_MIDDLE_LCSSA]], %[[MIDDLE_LATCH_SPLIT]] ] +; CHECK-NEXT: [[I_NEXT]] = add i64 [[I]], 1 +; CHECK-NEXT: [[EC_I:%.*]] = icmp eq i64 [[I_NEXT]], 2 +; CHECK-NEXT: br i1 [[EC_I]], label %[[EXIT:.*]], label %[[OUTER_HEADER]] +; CHECK: [[EXIT]]: +; CHECK-NEXT: [[RES:%.*]] = phi i8 [ [[SUM_OUTER_LCSSA]], %[[OUTER_LATCH]] ] +; CHECK-NEXT: ret i8 [[RES]] +; +entry: + br label %outer.header + +outer.header: + %i = phi i64 [ 0, %entry ], [ %i.next, %outer.latch ] + %sum.outer = phi i8 [ 0, %entry ], [ %sum.outer.lcssa, %outer.latch ] + br label %middle.header + +middle.header: + %j = phi i64 [ 0, %outer.header ], [ %j.next, %middle.latch ] + %sum.middle = phi i8 [ %sum.outer, %outer.header ], [ %sum.middle.lcssa, %middle.latch ] + br label %inner + +inner: + %k = phi i64 [ 0, %middle.header ], [ %k.next, %inner ] + %sum.inner = phi i8 [ %sum.middle, %middle.header ], [ %sum.inner.next, %inner ] + %gep.A = getelementptr [2 x [2 x i8]], ptr %A, i64 %k, i64 %j, i64 %i + %a = load i8, ptr %gep.A + %sum.inner.next = add i8 %sum.inner, %a + %gep.B = getelementptr [2 x [2 x i8]], ptr %B, i64 %k, i64 %j, i64 %i + store i8 %sum.outer, ptr %gep.B + %k.next = add i64 %k, 1 + %ec.k = icmp eq i64 %k.next, 2 + br i1 %ec.k, label %middle.latch, label %inner + +middle.latch: + %sum.middle.lcssa = phi i8 [ %sum.inner.next, %inner ] + %j.next = add i64 %j, 1 + %ec.j = icmp eq i64 %j.next, 2 + br i1 %ec.j, label %outer.latch, label %middle.header + +outer.latch: + %sum.outer.lcssa = phi i8 [ %sum.middle.lcssa, %middle.latch ] + %i.next = add i64 %i, 1 + %ec.i = icmp eq i64 %i.next, 2 + br i1 %ec.i, label %exit, label %outer.header + +exit: + %res = phi i8 [ %sum.outer.lcssa, %outer.latch ] + ret i8 %res +} _______________________________________________ llvm-branch-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
