Index: llvm/include/llvm/Analysis/DependenceAnalysis.h =================================================================== --- llvm/include/llvm/Analysis/DependenceAnalysis.h +++ llvm/include/llvm/Analysis/DependenceAnalysis.h @@ -269,8 +269,7 @@ class DependenceInfo { public: DependenceInfo(Function *F, AAResults *AA, ScalarEvolution *SE, - LoopInfo *LI) - : AA(AA), SE(SE), LI(LI), F(F) {} + LoopInfo *LI, bool NeedsNormalization = false); /// Handle transitive invalidation when the cached analysis results go away. bool invalidate(Function &F, const PreservedAnalyses &PA, @@ -335,6 +334,7 @@ ScalarEvolution *SE; LoopInfo *LI; Function *F; + bool NeedsNormalization; /// Subscript - This private struct represents a pair of subscripts from /// a pair of potentially multi-dimensional array references. We use a @@ -948,6 +948,16 @@ /// checkDstSubscript to avoid duplicate code bool checkSubscript(const SCEV *Expr, const Loop *LoopNest, SmallBitVector &Loops, bool IsSrc); + + /// Check if the direction vector is negative. A negative direction + /// vector means Src and Dst are reversed in the actual program. + bool isDirectionNegative(Dependence &Result) const; + + /// Under the circumtances that 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. + void normalize(FullDependence &Result); }; // class DependenceInfo /// AnalysisPass to compute dependence information in a function 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 NormalizeResults( + "da-normalize-results", cl::init(false), cl::Hidden, + cl::desc("Normalize the direction and distance vectors to make " + "them non-negative.")); //===----------------------------------------------------------------------===// // basics @@ -427,6 +431,11 @@ } #endif +DependenceInfo::DependenceInfo(Function *F, AAResults *AA, ScalarEvolution *SE, + LoopInfo *LI, bool NeedsNormalization) + : AA(AA), SE(SE), LI(LI), F(F) { + this->NeedsNormalization = NeedsNormalization || NormalizeResults.getValue(); +} // Updates X with the intersection // of the Constraints X and Y. Returns true if X has changed. @@ -3908,6 +3917,10 @@ return nullptr; } + // Normalize negative direction vectors if required by clients. + if (NeedsNormalization && isDirectionNegative(Result)) + normalize(Result); + return std::make_unique(std::move(Result)); } @@ -4136,3 +4149,43 @@ llvm_unreachable("somehow reached end of routine"); return nullptr; } + +bool DependenceInfo::isDirectionNegative(Dependence &Result) const { + for (unsigned Level = 1; Level <= CommonLevels; ++Level) { + if (Result.getDirection(Level) == Dependence::DVEntry::EQ) + continue; + if (Result.getDirection(Level) == Dependence::DVEntry::LT || + Result.getDirection(Level) == Dependence::DVEntry::LE) + return false; + if (Result.getDirection(Level) == Dependence::DVEntry::GT || + Result.getDirection(Level) == Dependence::DVEntry::GE) + return true; + return false; + } + return false; +} + +void DependenceInfo::normalize(FullDependence &Result) { + LLVM_DEBUG(dbgs() << "Before normalizing negative direction vectors:\n"; + Result.dump(dbgs());); + + std::swap(Result.Src, Result.Dst); + for (unsigned Level = 1; Level <= CommonLevels; ++Level) { + unsigned char Direction = Result.getDirection(Level); + // Extract the last three bits that represents the direction, and reverse + // those bits. This essentially reverses the direction. + Direction = (Direction & 0x07); + Direction = + (Direction & 0x04) >> 2 | (Direction & 0x01) << 2 | (Direction & 0x02); + Result.DV[Level - 1].Direction = + (Result.DV[Level - 1].Direction & 0xF8) | Direction; + // 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; +} \ No newline at end of file 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-normalize-results -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 - 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 - 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 - 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 - 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 [= <>]!