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; } + + /// 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. + 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; + + /// 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. + 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; 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,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 (NormalizePrintedResults && D->normalize(&SE)) + OS << "normalized - "; D->dump(OS); for (unsigned Level = 1; Level <= D->getLevels(); Level++) { if (D->isSplitable(Level)) { @@ -206,13 +214,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 +275,56 @@ DV = std::make_unique(CommonLevels); } +bool FullDependence::isDirectionNegative() const { + for (unsigned Level = 1; Level <= Levels; ++Level) { + auto 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; + // Extract the last three bits that represents the direction, and reverse + // those bits. This essentially reverses the direction. + Direction = (Direction & 0x07); + // Based on the bit representation of "direction", it is sufficient to reverse + // those bits in order to handle however complex directions, e,g. the example + // below. + // Result of bit-reversal: + // LT 001 <=> GT 100 + // EQ 010 <=> EQ 010 + // LE 011 <=> GE 110 + // NE 101 <=> NE 101 + // ALL 111 <=> ALL 111 + // If the direction is "flow [>= <>]", after bit reversal it becomes + // "anti [<= <>]" + Direction = + (Direction & 0x04) >> 2 | (Direction & 0x01) << 2 | (Direction & 0x02); + DV[Level - 1].Direction = Direction; + // 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. @@ -427,7 +487,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 [= <>]!