Index: polly/trunk/include/polly/DependenceInfo.h =================================================================== --- polly/trunk/include/polly/DependenceInfo.h +++ polly/trunk/include/polly/DependenceInfo.h @@ -141,11 +141,15 @@ /// @brief Dump the dependence information stored to the dbgs stream. void dump() const; + /// @brief Return the granularity of this dependence analysis. + AnalyisLevel getDependenceLevel() { return Level; } + /// @brief Allow the DependenceInfo access to private members and methods. /// /// To restrict access to the internal state, only the DependenceInfo class /// is able to call or modify a Dependences struct. friend class DependenceInfo; + friend class DependenceInfoWrapperPass; /// @brief Destructor that will free internal objects. ~Dependences() { releaseMemory(); } @@ -232,11 +236,52 @@ std::unique_ptr D[Dependences::NumAnalysisLevels]; }; +/// @brief Construct a new DependenceInfoWrapper pass. +class DependenceInfoWrapperPass : public FunctionPass { +public: + static char ID; + + /// @brief Construct a new DependenceInfoWrapper pass. + DependenceInfoWrapperPass() : FunctionPass(ID) {} + + /// @brief Return the dependence information for the given SCoP. + /// + /// @param S SCoP object. + /// @param Level The granularity of dependence analysis result. + /// + /// @return The dependence analysis result + /// + const Dependences &getDependences(Scop *S, Dependences::AnalyisLevel Level); + + /// @brief Recompute dependences from schedule and memory accesses. + const Dependences &recomputeDependences(Scop *S, + Dependences::AnalyisLevel Level); + + /// @brief Compute the dependence information on-the-fly for the function. + bool runOnFunction(Function &F) override; + + /// @brief Print the dependences for the current function to @p OS. + void print(raw_ostream &OS, const Module *M = nullptr) const override; + + /// @brief Release the internal memory. + void releaseMemory() override { ScopToDepsMap.clear(); } + + /// @brief Register all analyses and transformation required. + void getAnalysisUsage(AnalysisUsage &AU) const override; + +private: + using ScopToDepsMapTy = DenseMap>; + + /// @brief Scop to Dependence map for the current function. + ScopToDepsMapTy ScopToDepsMap; +}; + } // namespace polly namespace llvm { class PassRegistry; void initializeDependenceInfoPass(llvm::PassRegistry &); +void initializeDependenceInfoWrapperPassPass(llvm::PassRegistry &); } // namespace llvm #endif Index: polly/trunk/include/polly/LinkAllPasses.h =================================================================== --- polly/trunk/include/polly/LinkAllPasses.h +++ polly/trunk/include/polly/LinkAllPasses.h @@ -29,6 +29,7 @@ llvm::Pass *createCodePreparationPass(); llvm::Pass *createDeadCodeElimPass(); llvm::Pass *createDependenceInfoPass(); +llvm::Pass *createDependenceInfoWrapperPassPass(); llvm::Pass *createDOTOnlyPrinterPass(); llvm::Pass *createDOTOnlyViewerPass(); llvm::Pass *createDOTPrinterPass(); Index: polly/trunk/lib/Analysis/DependenceInfo.cpp =================================================================== --- polly/trunk/lib/Analysis/DependenceInfo.cpp +++ polly/trunk/lib/Analysis/DependenceInfo.cpp @@ -804,3 +804,59 @@ INITIALIZE_PASS_DEPENDENCY(ScopInfoRegionPass); INITIALIZE_PASS_END(DependenceInfo, "polly-dependences", "Polly - Calculate dependences", false, false) + +//===----------------------------------------------------------------------===// +const Dependences & +DependenceInfoWrapperPass::getDependences(Scop *S, + Dependences::AnalyisLevel Level) { + auto It = ScopToDepsMap.find(S); + if (It != ScopToDepsMap.end()) + if (It->second) { + if (It->second->getDependenceLevel() == Level) + return *It->second.get(); + } + return recomputeDependences(S, Level); +} + +const Dependences &DependenceInfoWrapperPass::recomputeDependences( + Scop *S, Dependences::AnalyisLevel Level) { + std::unique_ptr D(new Dependences(S->getSharedIslCtx(), Level)); + D->calculateDependences(*S); + auto Inserted = ScopToDepsMap.insert(std::make_pair(S, std::move(D))); + return *Inserted.first->second; +} + +bool DependenceInfoWrapperPass::runOnFunction(Function &F) { + auto &SI = getAnalysis(); + for (auto &It : SI) + recomputeDependences(It.second.get(), Dependences::AL_Access); + return false; +} + +void DependenceInfoWrapperPass::print(raw_ostream &OS, const Module *M) const { + for (auto &It : ScopToDepsMap) { + assert((It.first && It.second) && "Invalid Scop or Dependence object!\n"); + It.second->print(OS); + } +} + +void DependenceInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { + AU.addRequiredTransitive(); + AU.setPreservesAll(); +} + +char DependenceInfoWrapperPass::ID = 0; + +Pass *polly::createDependenceInfoWrapperPassPass() { + return new DependenceInfoWrapperPass(); +} + +INITIALIZE_PASS_BEGIN( + DependenceInfoWrapperPass, "polly-function-dependences", + "Polly - Calculate dependences for all the SCoPs of a function", false, + false) +INITIALIZE_PASS_DEPENDENCY(ScopInfoWrapperPass); +INITIALIZE_PASS_END( + DependenceInfoWrapperPass, "polly-function-dependences", + "Polly - Calculate dependences for all the SCoPs of a function", false, + false) Index: polly/trunk/lib/Support/RegisterPasses.cpp =================================================================== --- polly/trunk/lib/Support/RegisterPasses.cpp +++ polly/trunk/lib/Support/RegisterPasses.cpp @@ -148,6 +148,7 @@ initializeCodePreparationPass(Registry); initializeDeadCodeElimPass(Registry); initializeDependenceInfoPass(Registry); + initializeDependenceInfoWrapperPassPass(Registry); initializeJSONExporterPass(Registry); initializeJSONImporterPass(Registry); initializeIslAstInfoPass(Registry); Index: polly/trunk/test/DependenceInfo/computeout.ll =================================================================== --- polly/trunk/test/DependenceInfo/computeout.ll +++ polly/trunk/test/DependenceInfo/computeout.ll @@ -1,5 +1,7 @@ ; RUN: opt -S %loadPolly -polly-dependences -analyze < %s | FileCheck %s -check-prefix=VALUE +; RUN: opt -S %loadPolly -polly-function-dependences -analyze < %s | FileCheck %s -check-prefix=FUNC-VALUE ; RUN: opt -S %loadPolly -polly-dependences -analyze -polly-dependences-computeout=1 < %s | FileCheck %s -check-prefix=TIMEOUT +; RUN: opt -S %loadPolly -polly-function-dependences -analyze -polly-dependences-computeout=1 < %s | FileCheck %s -check-prefix=TIMEOUT target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64" ; for(i = 0; i < 100; i++ ) @@ -57,6 +59,13 @@ ; VALUE-NEXT: WAW dependences: ; VALUE-NEXT: { Stmt_S1[i0] -> Stmt_S2[i0] : 0 <= i0 <= 9; Stmt_S2[i0] -> Stmt_S3[i0] : 0 <= i0 <= 9; Stmt_S1[i0] -> Stmt_S3[i0] : 10 <= i0 <= 99 } +; FUNC-VALUE: RAW dependences: +; FUNC-VALUE-NEXT: { } +; FUNC-VALUE-NEXT: WAR dependences: +; FUNC-VALUE-NEXT: { } +; FUNC-VALUE-NEXT: WAW dependences: +; FUNC-VALUE-NEXT: { Stmt_S1[i0] -> Stmt_S2[i0] : 0 <= i0 <= 9; [Stmt_S1[i0] -> Stmt_S1_Write0_MemRef_A[]] -> [Stmt_S3[i0] -> Stmt_S3_Write0_MemRef_A[]] : 10 <= i0 <= 99; Stmt_S2[i0] -> Stmt_S3[i0] : 0 <= i0 <= 9; [Stmt_S2[i0] -> Stmt_S2_Write0_MemRef_A[]] -> [Stmt_S3[i0] -> Stmt_S3_Write0_MemRef_A[]] : 0 <= i0 <= 9; [Stmt_S1[i0] -> Stmt_S1_Write0_MemRef_A[]] -> [Stmt_S2[i0] -> Stmt_S2_Write0_MemRef_A[]] : 0 <= i0 <= 9; Stmt_S1[i0] -> Stmt_S3[i0] : 10 <= i0 <= 99 } + ; TIMEOUT: RAW dependences: ; TIMEOUT-NEXT: n/a ; TIMEOUT-NEXT: WAR dependences: Index: polly/trunk/test/DependenceInfo/different_schedule_dimensions.ll =================================================================== --- polly/trunk/test/DependenceInfo/different_schedule_dimensions.ll +++ polly/trunk/test/DependenceInfo/different_schedule_dimensions.ll @@ -1,5 +1,7 @@ ; RUN: opt -S %loadPolly -polly-dependences \ ; RUN: -analyze < %s | FileCheck %s +; RUN: opt -S %loadPolly -polly-function-dependences \ +; RUN: -analyze < %s | FileCheck %s -check-prefix=FUNC ; CHECK: RAW dependences: ; CHECK: { Stmt_bb9[0] -> Stmt_bb10[0] } @@ -10,6 +12,15 @@ ; CHECK: Reduction dependences: ; CHECK: { } +; FUNC: RAW dependences: +; FUNC-NEXT: { Stmt_bb9[0] -> Stmt_bb10[0]; [Stmt_bb9[0] -> Stmt_bb9_Write0_MemRef_tmp11[]] -> [Stmt_bb10[0] -> Stmt_bb10_Read0_MemRef_tmp11[]] } +; FUNC-NEXT: WAR dependences: +; FUNC-NEXT: { } +; FUNC-NEXT: WAW dependences: +; FUNC-NEXT: { Stmt_bb3[0] -> Stmt_bb10[0]; [Stmt_bb3[0] -> Stmt_bb3_Write1_MemRef_arg1[]] -> [Stmt_bb10[0] -> Stmt_bb10_Write1_MemRef_arg1[]] } +; FUNC-NEXT: Reduction dependences: +; FUNC-NEXT: { } + target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" define void @hoge(i32 %arg, [1024 x double]* %arg1) { Index: polly/trunk/test/DependenceInfo/do_pluto_matmult.ll =================================================================== --- polly/trunk/test/DependenceInfo/do_pluto_matmult.ll +++ polly/trunk/test/DependenceInfo/do_pluto_matmult.ll @@ -1,5 +1,7 @@ ; RUN: opt %loadPolly -basicaa -polly-dependences -analyze -polly-dependences-analysis-type=value-based < %s | FileCheck %s -check-prefix=VALUE ; RUN: opt %loadPolly -basicaa -polly-dependences -analyze -polly-dependences-analysis-type=memory-based < %s | FileCheck %s -check-prefix=MEMORY +; RUN: opt %loadPolly -basicaa -polly-function-dependences -analyze -polly-dependences-analysis-type=value-based < %s | FileCheck %s -check-prefix=FUNC-VALUE +; RUN: opt %loadPolly -basicaa -polly-function-dependences -analyze -polly-dependences-analysis-type=memory-based < %s | FileCheck %s -check-prefix=FUNC-MEMORY target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64" @@ -77,3 +79,17 @@ ; MEMORY-NEXT: { Stmt_do_body2[i0, i1, i2] -> Stmt_do_body2[i0, i1, o2] : 0 <= i0 <= 35 and 0 <= i1 <= 35 and i2 >= 0 and i2 < o2 <= 35 } ; MEMORY-NEXT: WAW dependences: ; MEMORY-NEXT: { Stmt_do_body2[i0, i1, i2] -> Stmt_do_body2[i0, i1, o2] : 0 <= i0 <= 35 and 0 <= i1 <= 35 and i2 >= 0 and i2 < o2 <= 35 } + +; FUNC-VALUE: RAW dependences: +; FUNC-VALUE-NEXT: { [Stmt_do_body2[i0, i1, i2] -> Stmt_do_body2_Write3_MemRef_C[]] -> [Stmt_do_body2[i0, i1, 1 + i2] -> Stmt_do_body2_Read0_MemRef_C[]] : 0 <= i0 <= 35 and 0 <= i1 <= 35 and 0 <= i2 <= 34; Stmt_do_body2[i0, i1, i2] -> Stmt_do_body2[i0, i1, 1 + i2] : 0 <= i0 <= 35 and 0 <= i1 <= 35 and 0 <= i2 <= 34 } +; FUNC-VALUE-NEXT: WAR dependences: +; FUNC-VALUE-NEXT: { } +; FUNC-VALUE-NEXT: WAW dependences: +; FUNC-VALUE-NEXT: { [Stmt_do_body2[i0, i1, i2] -> Stmt_do_body2_Write3_MemRef_C[]] -> [Stmt_do_body2[i0, i1, 1 + i2] -> Stmt_do_body2_Write3_MemRef_C[]] : 0 <= i0 <= 35 and 0 <= i1 <= 35 and 0 <= i2 <= 34; Stmt_do_body2[i0, i1, i2] -> Stmt_do_body2[i0, i1, 1 + i2] : 0 <= i0 <= 35 and 0 <= i1 <= 35 and 0 <= i2 <= 34 } + +; FUNC-MEMORY: RAW dependences: +; FUNC-MEMORY-NEXT: { [Stmt_do_body2[i0, i1, i2] -> Stmt_do_body2_Write3_MemRef_C[]] -> [Stmt_do_body2[i0, i1, o2] -> Stmt_do_body2_Read0_MemRef_C[]] : 0 <= i0 <= 35 and 0 <= i1 <= 35 and i2 >= 0 and i2 < o2 <= 35; Stmt_do_body2[i0, i1, i2] -> Stmt_do_body2[i0, i1, o2] : 0 <= i0 <= 35 and 0 <= i1 <= 35 and i2 >= 0 and i2 < o2 <= 35 } +; FUNC-MEMORY-NEXT: WAR dependences: +; FUNC-MEMORY-NEXT: { [Stmt_do_body2[i0, i1, i2] -> Stmt_do_body2_Read0_MemRef_C[]] -> [Stmt_do_body2[i0, i1, o2] -> Stmt_do_body2_Write3_MemRef_C[]] : 0 <= i0 <= 35 and 0 <= i1 <= 35 and i2 >= 0 and i2 < o2 <= 35; Stmt_do_body2[i0, i1, i2] -> Stmt_do_body2[i0, i1, o2] : 0 <= i0 <= 35 and 0 <= i1 <= 35 and i2 >= 0 and i2 < o2 <= 35 } +; FUNC-MEMORY-NEXT: WAW dependences: +; FUNC-MEMORY-NEXT: { [Stmt_do_body2[i0, i1, i2] -> Stmt_do_body2_Write3_MemRef_C[]] -> [Stmt_do_body2[i0, i1, o2] -> Stmt_do_body2_Write3_MemRef_C[]] : 0 <= i0 <= 35 and 0 <= i1 <= 35 and i2 >= 0 and i2 < o2 <= 35; Stmt_do_body2[i0, i1, i2] -> Stmt_do_body2[i0, i1, o2] : 0 <= i0 <= 35 and 0 <= i1 <= 35 and i2 >= 0 and i2 < o2 <= 35 } Index: polly/trunk/test/DependenceInfo/fine_grain_dep_0.ll =================================================================== --- polly/trunk/test/DependenceInfo/fine_grain_dep_0.ll +++ polly/trunk/test/DependenceInfo/fine_grain_dep_0.ll @@ -1,5 +1,6 @@ ; RUN: opt %loadPolly -polly-dependences -polly-dependences-analysis-type=value-based -polly-dependences-analysis-level=reference-wise -analyze < %s | FileCheck %s --check-prefix=REF ; RUN: opt %loadPolly -polly-dependences -polly-dependences-analysis-type=value-based -polly-dependences-analysis-level=access-wise -analyze < %s | FileCheck %s --check-prefix=ACC +; RUN: opt %loadPolly -polly-function-dependences -polly-dependences-analysis-type=value-based -polly-dependences-analysis-level=access-wise -analyze < %s | FileCheck %s --check-prefix=ACC ; ; REF: RAW dependences: ; REF-NEXT: [N] -> { [Stmt_for_body[i0] -> MemRef_a[]] -> [Stmt_for_body[4 + i0] -> MemRef_a[]] : 0 <= i0 <= -11 + N; [Stmt_for_body[i0] -> MemRef_b[]] -> [Stmt_for_body[6 + i0] -> MemRef_b[]] : 0 <= i0 <= -13 + N; Stmt_for_body[i0] -> Stmt_for_body[6 + i0] : 0 <= i0 <= -13 + N; Stmt_for_body[i0] -> Stmt_for_body[4 + i0] : 0 <= i0 <= -11 + N }