https://github.com/kasuga-fj updated https://github.com/llvm/llvm-project/pull/206960
>From f5f748a57d8b310df6f979999e1f1fa5a99c548b Mon Sep 17 00:00:00 2001 From: Ryotaro Kasuga <[email protected]> Date: Wed, 1 Jul 2026 12:04:51 +0000 Subject: [PATCH] [LoopInterchange] Change the way of direction vector normalization --- .../lib/Transforms/Scalar/LoopInterchange.cpp | 61 ++++++------------- .../LoopInterchange/dependency-all-neg-eq.ll | 36 +++++++---- 2 files changed, 42 insertions(+), 55 deletions(-) diff --git a/llvm/lib/Transforms/Scalar/LoopInterchange.cpp b/llvm/lib/Transforms/Scalar/LoopInterchange.cpp index c139a28e10d05..eea048f8fcad8 100644 --- a/llvm/lib/Transforms/Scalar/LoopInterchange.cpp +++ b/llvm/lib/Transforms/Scalar/LoopInterchange.cpp @@ -166,53 +166,27 @@ static bool inThisOrder(const Instruction *Src, const Instruction *Dst) { } #endif -/// Check if the direction vector is negative. A negative direction -/// vector means Src and Dst are reversed in the actual program. -/// -/// FIXME: in some cases the meaning of a negative direction vector -/// may not be straightforward, e.g., -/// for (int i = 0; i < 32; ++i) { -/// Src: A[i] = ...; -/// Dst: use(A[31 - i]); -/// } -/// The dependency is -/// flow { Src[i] -> Dst[31 - i] : when i >= 16 } and -/// anti { Dst[i] -> Src[31 - i] : when i < 16 }, -/// -- hence a [<>]. -/// As long as a dependence result contains '>' ('<>', '<=>', "*"), it -/// means that a reversed/normalized dependence needs to be considered -/// as well. Nevertheless, current isDirectionNegative() only returns -/// true with a '>' or '>=' dependency for ease of canonicalizing the -/// dependency vector, since the reverse of '<>', '<=>' and "*" is itself. -static bool isDirectionNegative(const Dependence &D) { +/// Return true if the dependence \p D should be negated. The decision is based +/// on the first element of the direction vector that contains exactly one of +/// the '<' or '>' directions. If such an element exists, the preferred +/// direction is '<' for the legality check. For instance, if the direction +/// vector is ['*', '>', '<'], it should be negated to ['*', '<', '>']. +static bool shouldNegateDependence(const Dependence &D) { for (unsigned Level = 1; Level <= D.getLevels(); ++Level) { unsigned char Direction = D.getDirection(Level); - if (Direction == Dependence::DVEntry::EQ) + bool HasLT = !!(Direction & Dependence::DVEntry::LT); + bool HasGT = !!(Direction & Dependence::DVEntry::GT); + if (HasLT == HasGT) continue; - if (Direction == Dependence::DVEntry::GT || - Direction == Dependence::DVEntry::GE) + if (HasLT) + return false; + if (HasGT) return true; - return false; + llvm_unreachable("Unexpected direction"); } return false; } -/// If the direction vector is negative, normalize the direction -/// vector to make it non-negative. Normalization is done by reversing -/// Src and Dst, plus reversing the dependence directions and distances -/// in the vector. -bool normalize(Dependence *D, ScalarEvolution *SE) { - if (!isDirectionNegative(*D)) - return false; - - LLVM_DEBUG(dbgs() << "Before normalizing negative direction vectors:\n"; - D->dump(dbgs());); - D->negate(*SE); - LLVM_DEBUG(dbgs() << "After normalizing negative direction vectors:\n"; - D->dump(dbgs());); - return true; -} - static bool populateDependencyMatrix(CharMatrix &DepMatrix, unsigned Level, Loop *L, DependenceInfo *DI, ScalarEvolution *SE, @@ -275,10 +249,11 @@ static bool populateDependencyMatrix(CharMatrix &DepMatrix, unsigned Level, // Track Output, Flow, and Anti dependencies. if (auto D = DI->depends(Src, Dst)) { assert(D->isOrdered() && "Expected an output, flow or anti dep."); - // If the direction vector is negative, normalize it to - // make it non-negative. - if (normalize(&*D, SE)) - LLVM_DEBUG(dbgs() << "Negative dependence vector normalized.\n"); + // Negate the dependence if it should be reversed. + if (shouldNegateDependence(*D)) { + D->negate(*SE); + LLVM_DEBUG(dbgs() << "Negate dependence vector.\n"); + } LLVM_DEBUG(StringRef DepType = D->isFlow() ? "flow" : D->isAnti() ? "anti" : "output"; dbgs() << "Found " << DepType diff --git a/llvm/test/Transforms/LoopInterchange/dependency-all-neg-eq.ll b/llvm/test/Transforms/LoopInterchange/dependency-all-neg-eq.ll index ab32ae55fc61d..c9a76ebf07d88 100644 --- a/llvm/test/Transforms/LoopInterchange/dependency-all-neg-eq.ll +++ b/llvm/test/Transforms/LoopInterchange/dependency-all-neg-eq.ll @@ -6,12 +6,8 @@ ; for (k = 0; k < 256; k++) ; A[j + 1][k] = A[j][k] + 1; ; -; The above loop nest has a direction vector of [* > =]. In principle, it is -; legal to interchange the j-loop and the k-loop, but at the moment the -; legality check doesn't handle such cases. -; -; FIXME: The direction vector of [* > =] should be normalized to [* < =] at the -; beginning. +; The above loop nest has a direction vector of [* > =]. Ensure that the j-loop +; and the k-loop are interchanged. The interchange was not applied in the past. ; define void @all_neg_eq(ptr %A) { @@ -23,22 +19,38 @@ define void @all_neg_eq(ptr %A) { ; CHECK-NEXT: [[I:%.*]] = phi i64 [ 0, %[[ENTRY]] ], [ [[I_INC:%.*]], %[[FOR_I_LATCH:.*]] ] ; CHECK-NEXT: br label %[[FOR_J_HEADER:.*]] ; CHECK: [[FOR_J_HEADER]]: -; CHECK-NEXT: [[J:%.*]] = phi i64 [ 0, %[[FOR_I_HEADER]] ], [ [[J_INC:%.*]], %[[FOR_J_LATCH:.*]] ] -; CHECK-NEXT: [[J_INC]] = add i64 [[J]], 1 +; CHECK-NEXT: br label %[[FOR_J_HEADER1:.*]] +; CHECK: [[FOR_J_HEADER1]]: +; CHECK-NEXT: [[J:%.*]] = phi i64 [ [[TMP2:%.*]], %[[FOR_J_LATCH_SPLIT:.*]] ], [ 0, %[[FOR_J_HEADER]] ] +; CHECK-NEXT: br label %[[FOR_K_PREHEADER:.*]] +; CHECK: [[FOR_J_HEADER_SPLIT:.*]]: +; CHECK-NEXT: [[J_INC:%.*]] = add i64 [[J]], 1 ; CHECK-NEXT: br label %[[FOR_K:.*]] +; CHECK: [[FOR_K_PREHEADER]]: +; CHECK-NEXT: br label %[[FOR_K1:.*]] +; CHECK: [[FOR_K1]]: +; CHECK-NEXT: [[K:%.*]] = phi i64 [ [[TMP0:%.*]], %[[FOR_K_SPLIT:.*]] ], [ 0, %[[FOR_K_PREHEADER]] ] +; CHECK-NEXT: br label %[[FOR_J_HEADER_SPLIT]] ; CHECK: [[FOR_K]]: -; CHECK-NEXT: [[K:%.*]] = phi i64 [ 0, %[[FOR_J_HEADER]] ], [ [[K_INC:%.*]], %[[FOR_K]] ] ; CHECK-NEXT: [[PTR_LOAD:%.*]] = getelementptr [256 x i8], ptr [[A]], i64 [[J]], i64 [[K]] ; CHECK-NEXT: [[LD:%.*]] = load i8, ptr [[PTR_LOAD]], align 1 ; CHECK-NEXT: [[ADD:%.*]] = add i8 [[LD]], 1 ; CHECK-NEXT: [[PTR_STORE:%.*]] = getelementptr [256 x i8], ptr [[A]], i64 [[J_INC]], i64 [[K]] ; CHECK-NEXT: store i8 [[ADD]], ptr [[PTR_STORE]], align 1 -; CHECK-NEXT: [[K_INC]] = add i64 [[K]], 1 +; CHECK-NEXT: [[K_INC:%.*]] = add i64 [[K]], 1 ; CHECK-NEXT: [[EC_K:%.*]] = icmp eq i64 [[K_INC]], 256 -; CHECK-NEXT: br i1 [[EC_K]], label %[[FOR_J_LATCH]], label %[[FOR_K]] +; CHECK-NEXT: br label %[[FOR_J_LATCH:.*]] +; CHECK: [[FOR_K_SPLIT]]: +; CHECK-NEXT: [[TMP0]] = add i64 [[K]], 1 +; CHECK-NEXT: [[TMP1:%.*]] = icmp eq i64 [[TMP0]], 256 +; CHECK-NEXT: br i1 [[TMP1]], label %[[FOR_J_LATCH_SPLIT]], label %[[FOR_K1]] ; CHECK: [[FOR_J_LATCH]]: ; CHECK-NEXT: [[EC_J:%.*]] = icmp eq i64 [[J_INC]], 255 -; CHECK-NEXT: br i1 [[EC_J]], label %[[FOR_I_LATCH]], label %[[FOR_J_HEADER]] +; CHECK-NEXT: br label %[[FOR_K_SPLIT]] +; CHECK: [[FOR_J_LATCH_SPLIT]]: +; CHECK-NEXT: [[TMP2]] = add i64 [[J]], 1 +; CHECK-NEXT: [[TMP3:%.*]] = icmp eq i64 [[TMP2]], 255 +; CHECK-NEXT: br i1 [[TMP3]], label %[[FOR_I_LATCH]], label %[[FOR_J_HEADER1]] ; CHECK: [[FOR_I_LATCH]]: ; CHECK-NEXT: [[I_INC]] = add i64 [[I]], 1 ; CHECK-NEXT: [[EC_I:%.*]] = icmp eq i64 [[I_INC]], 100 _______________________________________________ llvm-branch-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
