https://github.com/kasuga-fj updated https://github.com/llvm/llvm-project/pull/202092
>From 1f7c5f112d884c5223aa6b613eb5958faab19bc5 Mon Sep 17 00:00:00 2001 From: Ryotaro Kasuga <[email protected]> Date: Sun, 7 Jun 2026 08:00:03 +0900 Subject: [PATCH] [LoopInterchange] Reject interchange when AnyOf reduction exists --- .../lib/Transforms/Scalar/LoopInterchange.cpp | 17 +++++++++- .../LoopInterchange/reduction-anyof.ll | 32 ++++++------------- .../reductions-non-wrapped-operations.ll | 9 ++++-- 3 files changed, 32 insertions(+), 26 deletions(-) diff --git a/llvm/lib/Transforms/Scalar/LoopInterchange.cpp b/llvm/lib/Transforms/Scalar/LoopInterchange.cpp index e235249e83475..cb1327b75260f 100644 --- a/llvm/lib/Transforms/Scalar/LoopInterchange.cpp +++ b/llvm/lib/Transforms/Scalar/LoopInterchange.cpp @@ -1010,9 +1010,24 @@ static bool checkReductionKind(Loop *L, PHINode *PHI, case RecurKind::SMax: case RecurKind::UMin: case RecurKind::UMax: - case RecurKind::AnyOf: return true; + // Interchanging the loops that contain AnyOf reduction is not always legal. + // Especially, when the result value of the AnyOf is not loop-invariant with + // respect to the outer loop, interchanging may change the semantics. The + // following is an example of such case: + // int A = {{ 1, 0 }, { 0, 1 }}; + // int red = 0; + // for (int i = 0; i < 2; i++) + // for (int j = 0; j < 2; j++) + // red = (A[j][i] == 0) ? i + 1 : red; + // + // TODO: We may be able to support interchanging loops with AnyOf reduction + // by checking the operand of the reduction is loop-invariant with respect + // to the outer loop as well. + case RecurKind::AnyOf: + return false; + // Changing the order of floating-point operations may alter the results. If // a certain instruction has the ninf flag, it means that reordering can // produce a poison value, which may lead to undefined behavior. To prevent diff --git a/llvm/test/Transforms/LoopInterchange/reduction-anyof.ll b/llvm/test/Transforms/LoopInterchange/reduction-anyof.ll index 9346e76db2a60..edb8403908537 100644 --- a/llvm/test/Transforms/LoopInterchange/reduction-anyof.ll +++ b/llvm/test/Transforms/LoopInterchange/reduction-anyof.ll @@ -14,46 +14,34 @@ ; In the original code, the final value of `red` is 2, but if the loops are ; interchanged, the final value of `red` becomes 1. ; -; FIXME: The loops are now interchanged. -; define i8 @reduce_anyof(ptr %A) { ; CHECK-LABEL: define i8 @reduce_anyof( ; CHECK-SAME: ptr [[A:%.*]]) { -; CHECK-NEXT: [[FOR_I_HEADER_PREHEADER:.*:]] -; CHECK-NEXT: br label %[[FOR_I_HEADER:.*]] -; CHECK: [[FOR_I_HEADER_PREHEADER1:.*]]: +; CHECK-NEXT: [[FOR_I_HEADER_PREHEADER1:.*]]: ; CHECK-NEXT: br label %[[FOR_I_HEADER1:.*]] ; CHECK: [[FOR_I_HEADER1]]: -; CHECK-NEXT: [[I:%.*]] = phi i64 [ [[I_INC:%.*]], %[[FOR_I_LATCH:.*]] ], [ 0, %[[FOR_I_HEADER_PREHEADER1]] ] -; CHECK-NEXT: [[RED:%.*]] = phi i8 [ [[SEL:%.*]], %[[FOR_I_LATCH]] ], [ [[RED_OUTER:%.*]], %[[FOR_I_HEADER_PREHEADER1]] ] +; CHECK-NEXT: [[I:%.*]] = phi i64 [ 0, %[[FOR_I_HEADER_PREHEADER1]] ], [ [[I_INC:%.*]], %[[FOR_I_LATCH:.*]] ] +; CHECK-NEXT: [[RED_OUTER:%.*]] = phi i8 [ 0, %[[FOR_I_HEADER_PREHEADER1]] ], [ [[RED_LCSSA:%.*]], %[[FOR_I_LATCH]] ] ; CHECK-NEXT: [[ADD:%.*]] = add i64 [[I]], 1 ; CHECK-NEXT: [[ADD8:%.*]] = trunc i64 [[ADD]] to i8 ; CHECK-NEXT: br label %[[FOR_J_SPLIT1:.*]] -; CHECK: [[FOR_I_HEADER]]: -; CHECK-NEXT: br label %[[FOR_J:.*]] -; CHECK: [[FOR_J]]: -; CHECK-NEXT: [[J:%.*]] = phi i64 [ [[TMP2:%.*]], %[[FOR_J_SPLIT2:.*]] ], [ 0, %[[FOR_I_HEADER]] ] -; CHECK-NEXT: [[RED_OUTER]] = phi i8 [ [[RED_LCSSA:%.*]], %[[FOR_J_SPLIT2]] ], [ 0, %[[FOR_I_HEADER]] ] -; CHECK-NEXT: br label %[[FOR_I_HEADER_PREHEADER1]] ; CHECK: [[FOR_J_SPLIT1]]: +; CHECK-NEXT: [[J:%.*]] = phi i64 [ 0, %[[FOR_I_HEADER1]] ], [ [[TMP2:%.*]], %[[FOR_J_SPLIT1]] ] +; CHECK-NEXT: [[RED:%.*]] = phi i8 [ [[RED_OUTER]], %[[FOR_I_HEADER1]] ], [ [[SEL:%.*]], %[[FOR_J_SPLIT1]] ] ; CHECK-NEXT: [[ARRAYIDX:%.*]] = getelementptr inbounds [2 x i8], ptr [[A]], i64 [[J]], i64 [[I]] ; CHECK-NEXT: [[LV:%.*]] = load i8, ptr [[ARRAYIDX]], align 4 ; CHECK-NEXT: [[CMP:%.*]] = icmp eq i8 [[LV]], 0 ; CHECK-NEXT: [[SEL]] = select i1 [[CMP]], i8 [[ADD8]], i8 [[RED]] -; CHECK-NEXT: [[TMP0:%.*]] = add i64 [[J]], 1 -; CHECK-NEXT: [[TMP1:%.*]] = icmp eq i64 [[TMP0]], 2 -; CHECK-NEXT: br label %[[FOR_I_LATCH]] -; CHECK: [[FOR_J_SPLIT2]]: -; CHECK-NEXT: [[RED_LCSSA]] = phi i8 [ [[SEL]], %[[FOR_I_LATCH]] ] ; CHECK-NEXT: [[TMP2]] = add i64 [[J]], 1 ; CHECK-NEXT: [[TMP3:%.*]] = icmp eq i64 [[TMP2]], 2 -; CHECK-NEXT: br i1 [[TMP3]], label %[[FOR_J_SPLIT:.*]], label %[[FOR_J]] +; CHECK-NEXT: br i1 [[TMP3]], label %[[FOR_I_LATCH]], label %[[FOR_J_SPLIT1]] ; CHECK: [[FOR_I_LATCH]]: +; CHECK-NEXT: [[RED_LCSSA]] = phi i8 [ [[SEL]], %[[FOR_J_SPLIT1]] ] ; CHECK-NEXT: [[I_INC]] = add i64 [[I]], 1 ; CHECK-NEXT: [[EC_I:%.*]] = icmp eq i64 [[I_INC]], 2 -; CHECK-NEXT: br i1 [[EC_I]], label %[[FOR_J_SPLIT2]], label %[[FOR_I_HEADER1]] -; CHECK: [[FOR_J_SPLIT]]: -; CHECK-NEXT: [[RES:%.*]] = phi i8 [ [[RED_LCSSA]], %[[FOR_J_SPLIT2]] ] +; CHECK-NEXT: br i1 [[EC_I]], label %[[FOR_J_SPLIT2:.*]], label %[[FOR_I_HEADER1]] +; CHECK: [[FOR_J_SPLIT2]]: +; CHECK-NEXT: [[RES:%.*]] = phi i8 [ [[RED_LCSSA]], %[[FOR_I_LATCH]] ] ; CHECK-NEXT: ret i8 [[RES]] ; entry: diff --git a/llvm/test/Transforms/LoopInterchange/reductions-non-wrapped-operations.ll b/llvm/test/Transforms/LoopInterchange/reductions-non-wrapped-operations.ll index f5c6ad7889366..a1404b83cea4a 100644 --- a/llvm/test/Transforms/LoopInterchange/reductions-non-wrapped-operations.ll +++ b/llvm/test/Transforms/LoopInterchange/reductions-non-wrapped-operations.ll @@ -293,17 +293,20 @@ exit: } -; Check that interchanging the loops is legal for the any-of reduction. +; Interchanging the loops with AnyOf reduction is not necessarily legal. In +; this case it should be legal, but we conservatively reject it at the moment. ; ; int any_of = 0; ; for (int i = 0; i < 2; i++) ; for (int j = 0; j < 2; j++) ; any_of = (A[j][i] == 42) ? 1 : any_of; -; CHECK: --- !Pass +; CHECK: --- !Missed ; CHECK-NEXT: Pass: loop-interchange -; CHECK-NEXT: Name: Interchanged +; CHECK-NEXT: Name: UnsupportedPHIOuter ; CHECK-NEXT: Function: reduction_anyof +; CHECK-NEXT: Args: +; CHECK-NEXT: - String: Only outer loops with induction or reduction PHI nodes define void @reduction_anyof(ptr %A) { entry: br label %for.i.header _______________________________________________ llvm-branch-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
