Index: llvm/include/llvm/Analysis/DependenceAnalysis.h =================================================================== --- llvm/include/llvm/Analysis/DependenceAnalysis.h +++ 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 and return the newly constructed dependence + /// result. Normalization is done by reversing Src and Dst, plus reversing + /// the dependence directions and distances in the vector. + virtual std::unique_ptr normalize(ScalarEvolution *SE) { return nullptr; } + /// 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 and return the newly constructed dependence + /// result. Normalization is done by reversing Src and Dst, plus reversing + /// the dependence directions and distances in the vector. + std::unique_ptr 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; Index: llvm/lib/Analysis/DependenceAnalysis.cpp =================================================================== --- llvm/lib/Analysis/DependenceAnalysis.cpp +++ llvm/lib/Analysis/DependenceAnalysis.cpp @@ -121,6 +121,10 @@ cl::desc("Maximum depth allowed for the recursive algorithm used to " "explore MIV direction vectors.")); +static cl::opt NormalizePrintedResults( + "da-print-normalized-results", cl::init(false), cl::Hidden, + cl::desc("Normalize the direction and distance vectors to make " + "them non-negative.")); //===----------------------------------------------------------------------===// // basics @@ -176,7 +180,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) { auto *F = DA->getFunction(); for (inst_iterator SrcI = inst_begin(F), SrcE = inst_end(F); SrcI != SrcE; ++SrcI) { @@ -187,6 +192,11 @@ 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 (NormalizePrintedResults && D->isDirectionNegative()) { + D = D->normalize(&SE); + OS << "normalized - "; + } D->dump(OS); for (unsigned Level = 1; Level <= D->getLevels(); Level++) { if (D->isSplitable(Level)) { @@ -206,13 +216,15 @@ void DependenceAnalysisWrapperPass::print(raw_ostream &OS, const Module *) const { - dumpExampleDependence(OS, info.get()); + dumpExampleDependence(OS, info.get(), + getAnalysis().getSE()); } 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)); return PreservedAnalyses::all(); } @@ -265,6 +277,67 @@ 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; +} + +std::unique_ptr FullDependence::normalize(ScalarEvolution *SE) { + if (!isDirectionNegative()) + return nullptr; + + LLVM_DEBUG(dbgs() << "Before normalizing negative direction vectors:\n"; + dump(dbgs());); + // Create a new FullDependence object with normalized dependence vectors + // to return. + FullDependence Result(this->Dst, this->Src, this->LoopIndependent, + this->Levels); + Result.Consistent = this->Consistent; + for (unsigned Level = 1; Level <= Result.Levels; ++Level) { + Result.DV[Level - 1] = this->DV[Level - 1]; + unsigned char Direction = Result.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; + Result.DV[Level - 1].Direction = RevDirection; + // Reverse the dependence distance as well. + if (Result.DV[Level - 1].Distance != nullptr) + Result.DV[Level - 1].Distance = + SE->getNegativeSCEV(Result.DV[Level - 1].Distance); + } + + LLVM_DEBUG(dbgs() << "After normalizing negative direction vectors:\n"; + Result.dump(dbgs());); + return std::make_unique(std::move(Result)); +} + // The rest are simple getters that hide the implementation. // getDirection - Returns the direction associated with a particular level. @@ -427,7 +500,6 @@ } #endif - // Updates X with the intersection // of the Constraints X and Y. Returns true if X has changed. // Corresponds to Figure 4 from the paper Index: llvm/test/Analysis/DependenceAnalysis/Banerjee.ll =================================================================== --- llvm/test/Analysis/DependenceAnalysis/Banerjee.ll +++ 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: -da-print-normalized-results=true -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 [= <>]!