diff --git a/llvm/include/llvm/Analysis/DependenceAnalysis.h b/llvm/include/llvm/Analysis/DependenceAnalysis.h --- a/llvm/include/llvm/Analysis/DependenceAnalysis.h +++ b/llvm/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(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/llvm/lib/Analysis/DependenceAnalysis.cpp b/llvm/lib/Analysis/DependenceAnalysis.cpp --- a/llvm/lib/Analysis/DependenceAnalysis.cpp +++ b/llvm/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().getSE(), false); } PreservedAnalyses DependenceAnalysisPrinterPass::run(Function &F, FunctionAnalysisManager &FAM) { OS << "'Dependence Analysis' for function '" << F.getName() << "':\n"; - dumpExampleDependence(OS, &FAM.getResult(F)); + dumpExampleDependence(OS, &FAM.getResult(F), + FAM.getResult(F), + NormalizeResults); return PreservedAnalyses::all(); } @@ -265,6 +272,62 @@ DV = std::make_unique(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/llvm/lib/Passes/PassBuilder.cpp b/llvm/lib/Passes/PassBuilder.cpp --- a/llvm/lib/Passes/PassBuilder.cpp +++ b/llvm/lib/Passes/PassBuilder.cpp @@ -850,6 +850,11 @@ return Result; } +Expected 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/llvm/lib/Passes/PassRegistry.def b/llvm/lib/Passes/PassRegistry.def --- a/llvm/lib/Passes/PassRegistry.def +++ b/llvm/lib/Passes/PassRegistry.def @@ -473,6 +473,13 @@ }, parseStackLifetimeOptions, "may;must") +FUNCTION_PASS_WITH_PARAMS("print", + "DependenceAnalysisPrinterPass", + [](bool NormalizeResults) { + return DependenceAnalysisPrinterPass(dbgs(), NormalizeResults); + }, + parseDependenceAnalysisPrinterOptions, + "normalized-results") #undef FUNCTION_PASS_WITH_PARAMS #ifndef LOOPNEST_PASS diff --git a/llvm/test/Analysis/DependenceAnalysis/Banerjee.ll b/llvm/test/Analysis/DependenceAnalysis/Banerjee.ll --- a/llvm/test/Analysis/DependenceAnalysis/Banerjee.ll +++ b/llvm/test/Analysis/DependenceAnalysis/Banerjee.ll @@ -1,5 +1,7 @@ ; RUN: opt < %s -disable-output -da-delinearize=false "-passes=print" \ ; RUN: -aa-pipeline=basic-aa 2>&1 | FileCheck %s +; RUN: opt < %s -disable-output -da-delinearize=false -passes='print' \ +; RUN: -aa-pipeline=basic-aa 2>&1 | FileCheck %s -check-prefix=NORMALIZE ; RUN: opt < %s -disable-output "-passes=print" -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 [= <>]!