[DependenceAnalysis][PR56275] Normalize negative dependence analysis results
This patch is the first of the two-patch series (D130188, D130179) that
resolve PR56275 (https://github.com/llvm/llvm-project/issues/56275)
which is a missed opportunity, where a perfrectly valid case for loop
interchange failed interchange legality.
If the distance/direction vector produced by dependence analysis (DA) is
negative, it needs to be normalized (reversed). This patch provides helper
functions `isDirectionNegative()` and `normalize()` in DA that does the
normalization, and clients can query DA to do normalization if needed.
A pass option `<normalized-results>` is added to DependenceAnalysisPrinterPass,
and we leverage it to update DA test cases to make sure of test coverage. The
test cases added in `Banerjee.ll` shows that negative vectors are normalized
with `print<da><normalized-results>`.
Reviewed By: bmahjour, Meinersbur, #loopoptwg
Differential Revision: https://reviews.llvm.org/D130188
GitOrigin-RevId: 76be5549318a9e5aa3bdc2b3e0ae8ed5a16bfe59
diff --git a/include/llvm/Analysis/DependenceAnalysis.h b/include/llvm/Analysis/DependenceAnalysis.h
index a34afe9..0ea315a 100644
--- a/include/llvm/Analysis/DependenceAnalysis.h
+++ b/include/llvm/Analysis/DependenceAnalysis.h
@@ -158,6 +158,16 @@
/// particular level.
virtual const SCEV *getDistance(unsigned Level) const { 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; }
+
+ /// 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; }
+
/// isPeelFirst - Returns true if peeling the first iteration from
/// this loop will break this dependence.
virtual bool isPeelFirst(unsigned Level) const { return false; }
@@ -195,8 +205,10 @@
///
void dump(raw_ostream &OS) const;
- private:
+ protected:
Instruction *Src, *Dst;
+
+ private:
const Dependence *NextPredecessor = nullptr, *NextSuccessor = nullptr;
friend class DependenceInfo;
};
@@ -239,6 +251,16 @@
/// particular level.
const SCEV *getDistance(unsigned Level) 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;
+
+ /// 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;
+
/// isPeelFirst - Returns true if peeling the first iteration from
/// this loop will break this dependence.
bool isPeelFirst(unsigned Level) const override;
@@ -964,12 +986,15 @@
/// Printer pass to dump DA results.
struct DependenceAnalysisPrinterPass
: public PassInfoMixin<DependenceAnalysisPrinterPass> {
- DependenceAnalysisPrinterPass(raw_ostream &OS) : OS(OS) {}
+ DependenceAnalysisPrinterPass(raw_ostream &OS,
+ bool NormalizeResults = false)
+ : OS(OS), NormalizeResults(NormalizeResults) {}
PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM);
private:
raw_ostream &OS;
+ bool NormalizeResults;
}; // class DependenceAnalysisPrinterPass
/// Legacy pass manager pass to access dependence information
diff --git a/lib/Analysis/DependenceAnalysis.cpp b/lib/Analysis/DependenceAnalysis.cpp
index 3d2d84e..92d29a5 100644
--- a/lib/Analysis/DependenceAnalysis.cpp
+++ b/lib/Analysis/DependenceAnalysis.cpp
@@ -176,7 +176,8 @@
// Looks through the function, noting instructions that may access memory.
// Calls depends() on every possible pair and prints out the result.
// Ignores all other instructions.
-static void dumpExampleDependence(raw_ostream &OS, DependenceInfo *DA) {
+static void dumpExampleDependence(raw_ostream &OS, DependenceInfo *DA,
+ ScalarEvolution &SE, bool NormalizeResults) {
auto *F = DA->getFunction();
for (inst_iterator SrcI = inst_begin(F), SrcE = inst_end(F); SrcI != SrcE;
++SrcI) {
@@ -187,6 +188,9 @@
OS << "Src:" << *SrcI << " --> Dst:" << *DstI << "\n";
OS << " da analyze - ";
if (auto D = DA->depends(&*SrcI, &*DstI, true)) {
+ // Normalize negative direction vectors if required by clients.
+ if (NormalizeResults && D->normalize(&SE))
+ OS << "normalized - ";
D->dump(OS);
for (unsigned Level = 1; Level <= D->getLevels(); Level++) {
if (D->isSplitable(Level)) {
@@ -206,13 +210,16 @@
void DependenceAnalysisWrapperPass::print(raw_ostream &OS,
const Module *) const {
- dumpExampleDependence(OS, info.get());
+ dumpExampleDependence(OS, info.get(),
+ getAnalysis<ScalarEvolutionWrapperPass>().getSE(), false);
}
PreservedAnalyses
DependenceAnalysisPrinterPass::run(Function &F, FunctionAnalysisManager &FAM) {
OS << "'Dependence Analysis' for function '" << F.getName() << "':\n";
- dumpExampleDependence(OS, &FAM.getResult<DependenceAnalysis>(F));
+ dumpExampleDependence(OS, &FAM.getResult<DependenceAnalysis>(F),
+ FAM.getResult<ScalarEvolutionAnalysis>(F),
+ NormalizeResults);
return PreservedAnalyses::all();
}
@@ -265,6 +272,62 @@
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;
+}
+
+bool FullDependence::normalize(ScalarEvolution *SE) {
+ if (!isDirectionNegative())
+ return false;
+
+ LLVM_DEBUG(dbgs() << "Before normalizing negative direction vectors:\n";
+ dump(dbgs()););
+ std::swap(Src, Dst);
+ for (unsigned Level = 1; Level <= Levels; ++Level) {
+ unsigned char Direction = DV[Level - 1].Direction;
+ // Reverse the direction vector, this means LT becomes GT
+ // and GT becomes LT.
+ unsigned char RevDirection = Direction & Dependence::DVEntry::EQ;
+ if (Direction & Dependence::DVEntry::LT)
+ RevDirection |= Dependence::DVEntry::GT;
+ if (Direction & Dependence::DVEntry::GT)
+ RevDirection |= Dependence::DVEntry::LT;
+ DV[Level - 1].Direction = RevDirection;
+ // Reverse the dependence distance as well.
+ if (DV[Level - 1].Distance != nullptr)
+ DV[Level - 1].Distance =
+ SE->getNegativeSCEV(DV[Level - 1].Distance);
+ }
+
+ 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 level.
diff --git a/lib/Passes/PassBuilder.cpp b/lib/Passes/PassBuilder.cpp
index 42fde37..af18479 100644
--- a/lib/Passes/PassBuilder.cpp
+++ b/lib/Passes/PassBuilder.cpp
@@ -850,6 +850,11 @@
return Result;
}
+Expected<bool> parseDependenceAnalysisPrinterOptions(StringRef Params) {
+ return parseSinglePassOption(Params, "normalized-results",
+ "DependenceAnalysisPrinter");
+}
+
} // namespace
/// Tests whether a pass name starts with a valid prefix for a default pipeline
diff --git a/lib/Passes/PassRegistry.def b/lib/Passes/PassRegistry.def
index 7c29bff..ddff8a4 100644
--- a/lib/Passes/PassRegistry.def
+++ b/lib/Passes/PassRegistry.def
@@ -473,6 +473,13 @@
},
parseStackLifetimeOptions,
"may;must")
+FUNCTION_PASS_WITH_PARAMS("print<da>",
+ "DependenceAnalysisPrinterPass",
+ [](bool NormalizeResults) {
+ return DependenceAnalysisPrinterPass(dbgs(), NormalizeResults);
+ },
+ parseDependenceAnalysisPrinterOptions,
+ "normalized-results")
#undef FUNCTION_PASS_WITH_PARAMS
#ifndef LOOPNEST_PASS
diff --git a/test/Analysis/DependenceAnalysis/Banerjee.ll b/test/Analysis/DependenceAnalysis/Banerjee.ll
index 856a886..9d2b854 100644
--- a/test/Analysis/DependenceAnalysis/Banerjee.ll
+++ b/test/Analysis/DependenceAnalysis/Banerjee.ll
@@ -1,5 +1,7 @@
; RUN: opt < %s -disable-output -da-delinearize=false "-passes=print<da>" \
; RUN: -aa-pipeline=basic-aa 2>&1 | FileCheck %s
+; RUN: opt < %s -disable-output -da-delinearize=false -passes='print<da><normalized-results>' \
+; RUN: -aa-pipeline=basic-aa 2>&1 | FileCheck %s -check-prefix=NORMALIZE
; RUN: opt < %s -disable-output "-passes=print<da>" -aa-pipeline=basic-aa 2>&1 \
; RUN: | FileCheck %s -check-prefix=DELIN
@@ -23,6 +25,14 @@
; CHECK: da analyze - confused!
; CHECK: da analyze - none!
+; NORMALIZE: 'Dependence Analysis' for function 'banerjee0':
+; NORMALIZE: da analyze - none!
+; NORMALIZE: da analyze - flow [<= <>]!
+; NORMALIZE: da analyze - confused!
+; NORMALIZE: da analyze - none!
+; NORMALIZE: da analyze - confused!
+; NORMALIZE: da analyze - none!
+
; DELIN: 'Dependence Analysis' for function 'banerjee0':
; DELIN: da analyze - none!
; DELIN: da analyze - flow [<= <>]!
@@ -83,6 +93,14 @@
; CHECK: da analyze - confused!
; CHECK: da analyze - output [* *]!
+; NORMALIZE: 'Dependence Analysis' for function 'banerjee1':
+; NORMALIZE: da analyze - output [* *]!
+; NORMALIZE: da analyze - flow [* <>]!
+; NORMALIZE: da analyze - confused!
+; NORMALIZE: da analyze - input [* *]!
+; NORMALIZE: da analyze - confused!
+; NORMALIZE: da analyze - output [* *]!
+
; DELIN: 'Dependence Analysis' for function 'banerjee1':
; DELIN: da analyze - output [* *]!
; DELIN: da analyze - flow [* <>]!
@@ -158,6 +176,14 @@
; CHECK: da analyze - confused!
; CHECK: da analyze - none!
+; NORMALIZE: 'Dependence Analysis' for function 'banerjee2':
+; NORMALIZE: da analyze - none!
+; NORMALIZE: da analyze - none!
+; NORMALIZE: da analyze - confused!
+; NORMALIZE: da analyze - none!
+; NORMALIZE: da analyze - confused!
+; NORMALIZE: da analyze - none!
+
; DELIN: 'Dependence Analysis' for function 'banerjee2':
; DELIN: da analyze - none!
; DELIN: da analyze - none!
@@ -217,6 +243,14 @@
; CHECK: da analyze - confused!
; CHECK: da analyze - none!
+; NORMALIZE: 'Dependence Analysis' for function 'banerjee3':
+; NORMALIZE: da analyze - none!
+; NORMALIZE: da analyze - normalized - anti [< <]!
+; NORMALIZE: da analyze - confused!
+; NORMALIZE: da analyze - none!
+; NORMALIZE: da analyze - confused!
+; NORMALIZE: da analyze - none!
+
; DELIN: 'Dependence Analysis' for function 'banerjee3':
; DELIN: da analyze - none!
; DELIN: da analyze - flow [> >]!
@@ -276,6 +310,14 @@
; CHECK: da analyze - confused!
; CHECK: da analyze - none!
+; NORMALIZE: 'Dependence Analysis' for function 'banerjee4':
+; NORMALIZE: da analyze - none!
+; NORMALIZE: da analyze - none!
+; NORMALIZE: da analyze - confused!
+; NORMALIZE: da analyze - none!
+; NORMALIZE: da analyze - confused!
+; NORMALIZE: da analyze - none!
+
; DELIN: 'Dependence Analysis' for function 'banerjee4':
; DELIN: da analyze - none!
; DELIN: da analyze - none!
@@ -335,6 +377,14 @@
; CHECK: da analyze - confused!
; CHECK: da analyze - none!
+; NORMALIZE: 'Dependence Analysis' for function 'banerjee5':
+; NORMALIZE: da analyze - none!
+; NORMALIZE: da analyze - flow [< <]!
+; NORMALIZE: da analyze - confused!
+; NORMALIZE: da analyze - none!
+; NORMALIZE: da analyze - confused!
+; NORMALIZE: da analyze - none!
+
; DELIN: 'Dependence Analysis' for function 'banerjee5':
; DELIN: da analyze - none!
; DELIN: da analyze - flow [< <]!
@@ -394,6 +444,14 @@
; CHECK: da analyze - confused!
; CHECK: da analyze - none!
+; NORMALIZE: 'Dependence Analysis' for function 'banerjee6':
+; NORMALIZE: da analyze - none!
+; NORMALIZE: da analyze - normalized - anti [<= <>]!
+; NORMALIZE: da analyze - confused!
+; NORMALIZE: da analyze - none!
+; NORMALIZE: da analyze - confused!
+; NORMALIZE: da analyze - none!
+
; DELIN: 'Dependence Analysis' for function 'banerjee6':
; DELIN: da analyze - none!
; DELIN: da analyze - flow [=> <>]!
@@ -453,6 +511,14 @@
; CHECK: da analyze - confused!
; CHECK: da analyze - none!
+; NORMALIZE: 'Dependence Analysis' for function 'banerjee7':
+; NORMALIZE: da analyze - none!
+; NORMALIZE: da analyze - normalized - anti [< =>]!
+; NORMALIZE: da analyze - confused!
+; NORMALIZE: da analyze - none!
+; NORMALIZE: da analyze - confused!
+; NORMALIZE: da analyze - none!
+
; DELIN: 'Dependence Analysis' for function 'banerjee7':
; DELIN: da analyze - none!
; DELIN: da analyze - flow [> <=]!
@@ -512,6 +578,14 @@
; CHECK: da analyze - confused!
; CHECK: da analyze - none!
+; NORMALIZE: 'Dependence Analysis' for function 'banerjee8':
+; NORMALIZE: da analyze - none!
+; NORMALIZE: da analyze - normalized - anti [< <>]!
+; NORMALIZE: da analyze - confused!
+; NORMALIZE: da analyze - none!
+; NORMALIZE: da analyze - confused!
+; NORMALIZE: da analyze - none!
+
; DELIN: 'Dependence Analysis' for function 'banerjee8':
; DELIN: da analyze - none!
; DELIN: da analyze - flow [> <>]!
@@ -571,6 +645,14 @@
; CHECK: da analyze - confused!
; CHECK: da analyze - none!
+; NORMALIZE: 'Dependence Analysis' for function 'banerjee9':
+; NORMALIZE: da analyze - output [* *]!
+; NORMALIZE: da analyze - flow [<= =|<]!
+; NORMALIZE: da analyze - confused!
+; NORMALIZE: da analyze - none!
+; NORMALIZE: da analyze - confused!
+; NORMALIZE: da analyze - none!
+
; DELIN: 'Dependence Analysis' for function 'banerjee9':
; DELIN: da analyze - output [* *]!
; DELIN: da analyze - flow [<= =|<]!
@@ -631,6 +713,14 @@
; CHECK: da analyze - confused!
; CHECK: da analyze - none!
+; NORMALIZE: 'Dependence Analysis' for function 'banerjee10':
+; NORMALIZE: da analyze - none!
+; NORMALIZE: da analyze - flow [<> =]!
+; NORMALIZE: da analyze - confused!
+; NORMALIZE: da analyze - none!
+; NORMALIZE: da analyze - confused!
+; NORMALIZE: da analyze - none!
+
; DELIN: 'Dependence Analysis' for function 'banerjee10':
; DELIN: da analyze - none!
; DELIN: da analyze - flow [<> =]!
@@ -690,6 +780,14 @@
; CHECK: da analyze - confused!
; CHECK: da analyze - none!
+; NORMALIZE: 'Dependence Analysis' for function 'banerjee11':
+; NORMALIZE: da analyze - none!
+; NORMALIZE: da analyze - flow [<= <>]!
+; NORMALIZE: da analyze - confused!
+; NORMALIZE: da analyze - none!
+; NORMALIZE: da analyze - confused!
+; NORMALIZE: da analyze - none!
+
; DELIN: 'Dependence Analysis' for function 'banerjee11':
; DELIN: da analyze - none!
; DELIN: da analyze - flow [<= <>]!
@@ -749,6 +847,14 @@
; CHECK: da analyze - confused!
; CHECK: da analyze - none!
+; NORMALIZE: 'Dependence Analysis' for function 'banerjee12':
+; NORMALIZE: da analyze - none!
+; NORMALIZE: da analyze - flow [= <>]!
+; NORMALIZE: da analyze - confused!
+; NORMALIZE: da analyze - none!
+; NORMALIZE: da analyze - confused!
+; NORMALIZE: da analyze - none!
+
; DELIN: 'Dependence Analysis' for function 'banerjee12':
; DELIN: da analyze - none!
; DELIN: da analyze - flow [= <>]!
