https://github.com/kasuga-fj created https://github.com/llvm/llvm-project/pull/206959
None >From 8ce2cf75c62a41e8082bdeb8fa47add27dfabbd8 Mon Sep 17 00:00:00 2001 From: Ryotaro Kasuga <[email protected]> Date: Wed, 1 Jul 2026 11:43:14 +0000 Subject: [PATCH] [DA] Move isDirectionNegative and normalize into LoopInterchange --- .../llvm/Analysis/DependenceAnalysis.h | 20 -------- llvm/lib/Analysis/DependenceAnalysis.cpp | 43 ---------------- .../lib/Transforms/Scalar/LoopInterchange.cpp | 49 ++++++++++++++++++- .../Analysis/DependenceAnalysis/Banerjee.ll | 8 +-- 4 files changed, 52 insertions(+), 68 deletions(-) diff --git a/llvm/include/llvm/Analysis/DependenceAnalysis.h b/llvm/include/llvm/Analysis/DependenceAnalysis.h index 490fd4520746f..258a5f0e8ab79 100644 --- a/llvm/include/llvm/Analysis/DependenceAnalysis.h +++ b/llvm/include/llvm/Analysis/DependenceAnalysis.h @@ -165,20 +165,10 @@ class LLVM_ABI Dependence { return nullptr; } - /// Check if the direction vector is negative. A negative direction - /// vector means Src and Dst are reversed in the actual program. - virtual bool isDirectionNegative() const { return false; } - /// Negate the dependence by swapping the source and destination, and /// reversing the direction and distance information. virtual void negate(ScalarEvolution &SE) {} - /// 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. - virtual bool normalize(ScalarEvolution *SE) { return false; } - /// inSameSDLoops - Returns true if this level is an SameSD level, i.e., /// performed across two separate loop nests that have the Same Iteration and /// Depth. @@ -275,18 +265,8 @@ class LLVM_ABI FullDependence final : public Dependence { /// particular common or SameSD level. const SCEV *getDistance(unsigned Level, bool SameSD = false) const override; - /// Check if the direction vector is negative. A negative direction - /// vector means Src and Dst are reversed in the actual program. - bool isDirectionNegative() const override; - void negate(ScalarEvolution &SE) override; - /// 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(ScalarEvolution *SE) override; - /// inSameSDLoops - Returns true if this level is an SameSD level, i.e., /// performed across two separate loop nests that have the Same Iteration and /// Depth. diff --git a/llvm/lib/Analysis/DependenceAnalysis.cpp b/llvm/lib/Analysis/DependenceAnalysis.cpp index 9d5a555fb8998..f0d1c60c2cfa4 100644 --- a/llvm/lib/Analysis/DependenceAnalysis.cpp +++ b/llvm/lib/Analysis/DependenceAnalysis.cpp @@ -329,9 +329,6 @@ static void dumpExampleDependence(raw_ostream &OS, DependenceInfo *DA, } #endif - // Normalize negative direction vectors if required by clients. - if (NormalizeResults && D->normalize(&SE)) - OS << "normalized - "; D->dump(OS); } else OS << "none!\n"; @@ -401,34 +398,6 @@ FullDependence::FullDependence(Instruction *Source, Instruction *Destination, DV = std::make_unique<DVEntry[]>(CommonLevels); } -// 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. -bool FullDependence::isDirectionNegative() const { - for (unsigned Level = 1; Level <= Levels; ++Level) { - unsigned char Direction = DV[Level - 1].Direction; - if (Direction == Dependence::DVEntry::EQ) - continue; - if (Direction == Dependence::DVEntry::GT || - Direction == Dependence::DVEntry::GE) - return true; - return false; - } - return false; -} - void FullDependence::negate(ScalarEvolution &SE) { std::swap(Src, Dst); for (unsigned Level = 1; Level <= Levels; ++Level) { @@ -447,18 +416,6 @@ void FullDependence::negate(ScalarEvolution &SE) { } } -bool FullDependence::normalize(ScalarEvolution *SE) { - if (!isDirectionNegative()) - return false; - - LLVM_DEBUG(dbgs() << "Before normalizing negative direction vectors:\n"; - dump(dbgs());); - negate(*SE); - LLVM_DEBUG(dbgs() << "After normalizing negative direction vectors:\n"; - dump(dbgs());); - return true; -} - // The rest are simple getters that hide the implementation. // getDirection - Returns the direction associated with a particular common or diff --git a/llvm/lib/Transforms/Scalar/LoopInterchange.cpp b/llvm/lib/Transforms/Scalar/LoopInterchange.cpp index 96a4e4d54c6f8..c139a28e10d05 100644 --- a/llvm/lib/Transforms/Scalar/LoopInterchange.cpp +++ b/llvm/lib/Transforms/Scalar/LoopInterchange.cpp @@ -166,6 +166,53 @@ 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) { + for (unsigned Level = 1; Level <= D.getLevels(); ++Level) { + unsigned char Direction = D.getDirection(Level); + if (Direction == Dependence::DVEntry::EQ) + continue; + if (Direction == Dependence::DVEntry::GT || + Direction == Dependence::DVEntry::GE) + return true; + return false; + } + 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, @@ -230,7 +277,7 @@ static bool populateDependencyMatrix(CharMatrix &DepMatrix, unsigned Level, assert(D->isOrdered() && "Expected an output, flow or anti dep."); // If the direction vector is negative, normalize it to // make it non-negative. - if (D->normalize(SE)) + if (normalize(&*D, SE)) LLVM_DEBUG(dbgs() << "Negative dependence vector normalized.\n"); LLVM_DEBUG(StringRef DepType = D->isFlow() ? "flow" : D->isAnti() ? "anti" : "output"; diff --git a/llvm/test/Analysis/DependenceAnalysis/Banerjee.ll b/llvm/test/Analysis/DependenceAnalysis/Banerjee.ll index bb89ad55554ff..de7546337e4c7 100644 --- a/llvm/test/Analysis/DependenceAnalysis/Banerjee.ll +++ b/llvm/test/Analysis/DependenceAnalysis/Banerjee.ll @@ -306,7 +306,7 @@ define void @banerjee3(ptr %A, ptr %B, i64 %m, i64 %n) nounwind uwtable ssp { ; NORMALIZE-NEXT: Src: store i64 0, ptr %arrayidx, align 8 --> Dst: store i64 0, ptr %arrayidx, align 8 ; NORMALIZE-NEXT: da analyze - none! ; NORMALIZE-NEXT: Src: store i64 0, ptr %arrayidx, align 8 --> Dst: %0 = load i64, ptr %arrayidx7, align 8 -; NORMALIZE-NEXT: da analyze - normalized - anti [< <]! +; NORMALIZE-NEXT: da analyze - flow [> >]! ; NORMALIZE-NEXT: Src: store i64 0, ptr %arrayidx, align 8 --> Dst: store i64 %0, ptr %B.addr.11, align 8 ; NORMALIZE-NEXT: da analyze - confused! ; NORMALIZE-NEXT: Src: %0 = load i64, ptr %arrayidx7, align 8 --> Dst: %0 = load i64, ptr %arrayidx7, align 8 @@ -561,7 +561,7 @@ define void @banerjee6(ptr %A, ptr %B, i64 %m, i64 %n) nounwind uwtable ssp { ; NORMALIZE-NEXT: Src: store i64 0, ptr %arrayidx, align 8 --> Dst: store i64 0, ptr %arrayidx, align 8 ; NORMALIZE-NEXT: da analyze - none! ; NORMALIZE-NEXT: Src: store i64 0, ptr %arrayidx, align 8 --> Dst: %0 = load i64, ptr %arrayidx7, align 8 -; NORMALIZE-NEXT: da analyze - normalized - anti [<= <>]! +; NORMALIZE-NEXT: da analyze - flow [=> <>]! ; NORMALIZE-NEXT: Src: store i64 0, ptr %arrayidx, align 8 --> Dst: store i64 %0, ptr %B.addr.11, align 8 ; NORMALIZE-NEXT: da analyze - confused! ; NORMALIZE-NEXT: Src: %0 = load i64, ptr %arrayidx7, align 8 --> Dst: %0 = load i64, ptr %arrayidx7, align 8 @@ -646,7 +646,7 @@ define void @banerjee7(ptr %A, ptr %B, i64 %m, i64 %n) nounwind uwtable ssp { ; NORMALIZE-NEXT: Src: store i64 0, ptr %arrayidx, align 8 --> Dst: store i64 0, ptr %arrayidx, align 8 ; NORMALIZE-NEXT: da analyze - none! ; NORMALIZE-NEXT: Src: store i64 0, ptr %arrayidx, align 8 --> Dst: %0 = load i64, ptr %arrayidx7, align 8 -; NORMALIZE-NEXT: da analyze - normalized - anti [< =>]! +; NORMALIZE-NEXT: da analyze - flow [> <=]! ; NORMALIZE-NEXT: Src: store i64 0, ptr %arrayidx, align 8 --> Dst: store i64 %0, ptr %B.addr.11, align 8 ; NORMALIZE-NEXT: da analyze - confused! ; NORMALIZE-NEXT: Src: %0 = load i64, ptr %arrayidx7, align 8 --> Dst: %0 = load i64, ptr %arrayidx7, align 8 @@ -731,7 +731,7 @@ define void @banerjee8(ptr %A, ptr %B, i64 %m, i64 %n) nounwind uwtable ssp { ; NORMALIZE-NEXT: Src: store i64 0, ptr %arrayidx, align 8 --> Dst: store i64 0, ptr %arrayidx, align 8 ; NORMALIZE-NEXT: da analyze - none! ; NORMALIZE-NEXT: Src: store i64 0, ptr %arrayidx, align 8 --> Dst: %0 = load i64, ptr %arrayidx7, align 8 -; NORMALIZE-NEXT: da analyze - normalized - anti [< <>]! +; NORMALIZE-NEXT: da analyze - flow [> <>]! ; NORMALIZE-NEXT: Src: store i64 0, ptr %arrayidx, align 8 --> Dst: store i64 %0, ptr %B.addr.11, align 8 ; NORMALIZE-NEXT: da analyze - confused! ; NORMALIZE-NEXT: Src: %0 = load i64, ptr %arrayidx7, align 8 --> Dst: %0 = load i64, ptr %arrayidx7, align 8 _______________________________________________ llvm-branch-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
