From 2a798853f86061ee34b3fa953560955164e370d3 Mon Sep 17 00:00:00 2001 From: Hongbin Zheng Date: Thu, 3 Mar 2016 08:15:33 +0000 Subject: [PATCH] Allow the client of DependenceInfo to obtain dependences at different granularities. llvm-svn: 262591 --- polly/include/polly/DependenceInfo.h | 38 +++++++++++---- polly/lib/Analysis/DependenceInfo.cpp | 71 +++++++++++++++++++---------- polly/lib/CodeGen/IslAst.cpp | 3 +- polly/lib/Exchange/JSONExporter.cpp | 3 +- polly/lib/Transform/DeadCodeElimination.cpp | 4 +- polly/lib/Transform/ScheduleOptimizer.cpp | 3 +- 6 files changed, 84 insertions(+), 38 deletions(-) diff --git a/polly/include/polly/DependenceInfo.h b/polly/include/polly/DependenceInfo.h index b8a6ec9..1654525 100644 --- a/polly/include/polly/DependenceInfo.h +++ b/polly/include/polly/DependenceInfo.h @@ -47,6 +47,16 @@ class MemoryAccess; /// compute for one SCoP. It also offers an interface that allows users to /// query only specific parts. struct Dependences { + // Granularities of the current dependence analysis + enum AnalyisLevel { + AL_Statement = 0, + // Distinguish accessed memory references in the same statement + AL_Reference, + // Distinguish memory access instances in the same statement + AL_Access, + + NumAnalysisLevels + }; /// @brief Map type for reduction dependences. using ReductionDependencesMapTy = DenseMap; @@ -141,10 +151,11 @@ struct Dependences { ~Dependences() { releaseMemory(); } private: - /// @brief Create an empty Dependences struct. - explicit Dependences(const std::shared_ptr &IslCtx) + /// @brief Create an empty dependences struct. + explicit Dependences(const std::shared_ptr &IslCtx, + AnalyisLevel Level) : RAW(nullptr), WAR(nullptr), WAW(nullptr), RED(nullptr), TC_RED(nullptr), - IslCtx(IslCtx) {} + IslCtx(IslCtx), Level(Level) {} /// @brief Calculate and add at the privatization dependences. void addPrivatizationDependences(); @@ -176,6 +187,9 @@ private: /// @brief Isl context from the SCoP. std::shared_ptr IslCtx; + + /// @brief Granularity of this dependence analysis + const AnalyisLevel Level; }; class DependenceInfo : public ScopPass { @@ -186,19 +200,27 @@ public: DependenceInfo() : ScopPass(ID) {} /// @brief Return the dependence information for the current SCoP. - const Dependences &getDependences() { return *D; } + /// + /// @param Level The granularity of dependence analysis result. + /// + /// @return The dependence analysis result + /// + const Dependences &getDependences(Dependences::AnalyisLevel Level); /// @brief Recompute dependences from schedule and memory accesses. - void recomputeDependences(); + const Dependences &recomputeDependences(Dependences::AnalyisLevel Level); /// @brief Compute the dependence information for the SCoP @p S. bool runOnScop(Scop &S) override; /// @brief Print the dependences for the given SCoP to @p OS. - void printScop(raw_ostream &OS, Scop &) const override { D->print(OS); } + void printScop(raw_ostream &OS, Scop &) const override; /// @brief Release the internal memory. - void releaseMemory() override { D.reset(); } + void releaseMemory() override { + for (auto &d : D) + d.reset(); + } /// @brief Register all analyses and transformation required. void getAnalysisUsage(AnalysisUsage &AU) const override; @@ -207,7 +229,7 @@ private: Scop *S; /// @brief Dependences struct for the current SCoP. - std::unique_ptr D; + std::unique_ptr D[Dependences::NumAnalysisLevels]; }; } // End polly namespace. diff --git a/polly/lib/Analysis/DependenceInfo.cpp b/polly/lib/Analysis/DependenceInfo.cpp index e34baa1..225d841 100644 --- a/polly/lib/Analysis/DependenceInfo.cpp +++ b/polly/lib/Analysis/DependenceInfo.cpp @@ -70,24 +70,19 @@ static cl::opt OptAnalysisType( cl::Hidden, cl::init(VALUE_BASED_ANALYSIS), cl::ZeroOrMore, cl::cat(PollyCategory)); -enum AnalyisLevel { - STATEMENT_LEVEL_ANALYSIS = 0, - REFERENCE_LEVEL_ANALYSIS, - ACCESS_LEVEL_ANALYSIS -}; -static cl::opt OptAnalysisLevel( +static cl::opt OptAnalysisLevel( "polly-dependences-analysis-level", cl::desc("The level of dependence analysis"), - cl::values(clEnumValN(STATEMENT_LEVEL_ANALYSIS, "statement-level", + cl::values(clEnumValN(Dependences::AL_Statement, "statement-level", "Statement-level analysis"), - clEnumValN(REFERENCE_LEVEL_ANALYSIS, "reference-level", + clEnumValN(Dependences::AL_Reference, "reference-level", "Memory reference level analysis that distinguish" " accessed references in the same statement"), - clEnumValN(ACCESS_LEVEL_ANALYSIS, "access-level", + clEnumValN(Dependences::AL_Access, "access-level", "Memory reference level analysis that distinguish" " access instructions in the same statement"), clEnumValEnd), - cl::Hidden, cl::init(STATEMENT_LEVEL_ANALYSIS), cl::ZeroOrMore, + cl::Hidden, cl::init(Dependences::AL_Statement), cl::ZeroOrMore, cl::cat(PollyCategory)); //===----------------------------------------------------------------------===// @@ -106,11 +101,11 @@ static __isl_give isl_map *tag(__isl_take isl_map *Relation, /// @brief Tag the @p Relation domain with either MA->getArrayId() or /// MA->getId() based on @p TagLevel static __isl_give isl_map *tag(__isl_take isl_map *Relation, MemoryAccess *MA, - AnalyisLevel TagLevel) { - if (TagLevel == REFERENCE_LEVEL_ANALYSIS) + Dependences::AnalyisLevel TagLevel) { + if (TagLevel == Dependences::AL_Reference) return tag(Relation, MA->getArrayId()); - if (TagLevel == ACCESS_LEVEL_ANALYSIS) + if (TagLevel == Dependences::AL_Access) return tag(Relation, MA->getId()); // No need to tag at the statement level. @@ -121,7 +116,8 @@ static __isl_give isl_map *tag(__isl_take isl_map *Relation, MemoryAccess *MA, static void collectInfo(Scop &S, isl_union_map **Read, isl_union_map **Write, isl_union_map **MayWrite, isl_union_map **AccessSchedule, - isl_union_map **StmtSchedule) { + isl_union_map **StmtSchedule, + Dependences::AnalyisLevel Level) { isl_space *Space = S.getParamSpace(); *Read = isl_union_map_empty(isl_space_copy(Space)); *Write = isl_union_map_empty(isl_space_copy(Space)); @@ -164,9 +160,9 @@ static void collectInfo(Scop &S, isl_union_map **Read, isl_union_map **Write, *AccessSchedule = isl_union_map_add_map(*AccessSchedule, Schedule); } else { - accdom = tag(accdom, MA, OptAnalysisLevel); - if (OptAnalysisLevel > STATEMENT_LEVEL_ANALYSIS) { - isl_map *Schedule = tag(Stmt.getSchedule(), MA, OptAnalysisLevel); + accdom = tag(accdom, MA, Level); + if (Level > Dependences::AL_Statement) { + isl_map *Schedule = tag(Stmt.getSchedule(), MA, Level); *StmtSchedule = isl_union_map_add_map(*StmtSchedule, Schedule); } } @@ -177,7 +173,7 @@ static void collectInfo(Scop &S, isl_union_map **Read, isl_union_map **Write, *Write = isl_union_map_add_map(*Write, accdom); } - if (OptAnalysisLevel == STATEMENT_LEVEL_ANALYSIS) + if (Level == Dependences::AL_Statement) *StmtSchedule = isl_union_map_add_map(*StmtSchedule, Stmt.getSchedule()); } @@ -336,7 +332,8 @@ void Dependences::calculateDependences(Scop &S) { DEBUG(dbgs() << "Scop: \n" << S << "\n"); - collectInfo(S, &Read, &Write, &MayWrite, &AccessSchedule, &StmtSchedule); + collectInfo(S, &Read, &Write, &MayWrite, &AccessSchedule, &StmtSchedule, + Level); DEBUG(dbgs() << "Read: " << Read << '\n'; dbgs() << "Write: " << Write << '\n'; @@ -348,7 +345,7 @@ void Dependences::calculateDependences(Scop &S) { isl_union_map_free(AccessSchedule); Schedule = S.getScheduleTree(); // Tag the schedule tree if we want fine-grain dependence info - if (OptAnalysisLevel > STATEMENT_LEVEL_ANALYSIS) { + if (Level > AL_Statement) { auto TaggedDom = isl_union_map_domain((isl_union_map_copy(StmtSchedule))); auto TaggedMap = isl_union_set_unwrap(TaggedDom); auto Tags = isl_union_map_domain_map_union_pw_multi_aff(TaggedMap); @@ -758,19 +755,43 @@ void Dependences::setReductionDependences(MemoryAccess *MA, isl_map *D) { ReductionDependences[MA] = D; } -void DependenceInfo::recomputeDependences() { - D.reset(new Dependences(S->getSharedIslCtx())); - D->calculateDependences(*S); +const Dependences & +DependenceInfo::getDependences(Dependences::AnalyisLevel Level) { + if (Dependences *d = D[Level].get()) + return *d; + + return recomputeDependences(Level); +} + +const Dependences & +DependenceInfo::recomputeDependences(Dependences::AnalyisLevel Level) { + D[Level].reset(new Dependences(S->getSharedIslCtx(), Level)); + D[Level]->calculateDependences(*S); + return *D[Level]; } bool DependenceInfo::runOnScop(Scop &ScopVar) { S = &ScopVar; - recomputeDependences(); return false; } +/// @brief Print the dependences for the given SCoP to @p OS. + +void polly::DependenceInfo::printScop(raw_ostream &OS, Scop &S) const { + if (auto d = D[OptAnalysisLevel].get()) { + d->print(OS); + return; + } + + // Otherwise create the dependences on-the-fly and print it + Dependences D(S.getSharedIslCtx(), OptAnalysisLevel); + D.calculateDependences(S); + D.print(OS); +} + void DependenceInfo::getAnalysisUsage(AnalysisUsage &AU) const { - ScopPass::getAnalysisUsage(AU); + AU.addRequiredTransitive(); + AU.setPreservesAll(); } char DependenceInfo::ID = 0; diff --git a/polly/lib/CodeGen/IslAst.cpp b/polly/lib/CodeGen/IslAst.cpp index 1c058ab..8f266b5 100644 --- a/polly/lib/CodeGen/IslAst.cpp +++ b/polly/lib/CodeGen/IslAst.cpp @@ -466,7 +466,8 @@ bool IslAstInfo::runOnScop(Scop &Scop) { S = &Scop; - const Dependences &D = getAnalysis().getDependences(); + const Dependences &D = + getAnalysis().getDependences(Dependences::AL_Statement); Ast = IslAst::create(&Scop, D); diff --git a/polly/lib/Exchange/JSONExporter.cpp b/polly/lib/Exchange/JSONExporter.cpp index e8afb77..5047f90 100644 --- a/polly/lib/Exchange/JSONExporter.cpp +++ b/polly/lib/Exchange/JSONExporter.cpp @@ -201,7 +201,8 @@ typedef Dependences::StatementToIslMapTy StatementToIslMapTy; bool JSONImporter::runOnScop(Scop &S) { Region &R = S.getRegion(); - const Dependences &D = getAnalysis().getDependences(); + const Dependences &D = + getAnalysis().getDependences(Dependences::AL_Statement); const DataLayout &DL = S.getRegion().getEntry()->getParent()->getParent()->getDataLayout(); diff --git a/polly/lib/Transform/DeadCodeElimination.cpp b/polly/lib/Transform/DeadCodeElimination.cpp index f8374d6..4fe6317 100644 --- a/polly/lib/Transform/DeadCodeElimination.cpp +++ b/polly/lib/Transform/DeadCodeElimination.cpp @@ -115,7 +115,7 @@ isl_union_set *DeadCodeElim::getLiveOut(Scop &S) { /// simplifies the life set with an affine hull. bool DeadCodeElim::eliminateDeadCode(Scop &S, int PreciseSteps) { DependenceInfo &DI = getAnalysis(); - const Dependences &D = DI.getDependences(); + const Dependences &D = DI.getDependences(Dependences::AL_Statement); if (!D.hasValidDependences()) return false; @@ -159,7 +159,7 @@ bool DeadCodeElim::eliminateDeadCode(Scop &S, int PreciseSteps) { // FIXME: We can probably avoid the recomputation of all dependences by // updating them explicitly. if (Changed) - DI.recomputeDependences(); + DI.recomputeDependences(Dependences::AL_Statement); return Changed; } diff --git a/polly/lib/Transform/ScheduleOptimizer.cpp b/polly/lib/Transform/ScheduleOptimizer.cpp index 77c339f..6702c53 100644 --- a/polly/lib/Transform/ScheduleOptimizer.cpp +++ b/polly/lib/Transform/ScheduleOptimizer.cpp @@ -462,7 +462,8 @@ bool IslScheduleOptimizer::runOnScop(Scop &S) { return false; } - const Dependences &D = getAnalysis().getDependences(); + const Dependences &D = + getAnalysis().getDependences(Dependences::AL_Statement); if (!D.hasValidDependences()) return false; -- 2.7.4