[Polly] [RFC] Allow the client of DependenceInfo to obtain dependences at different granularities.

[etherzhhb]

Summary

Also allow DependenceInfo generate dependence results at different granularities at the same time.

Please feel free to comment and suggest

[Meinersbur]

include/polly/DependenceInfo.h

58

For consistent naming, please refer to the LLVM style guide

lib/Analysis/DependenceInfo.cpp

793–794

ScopPass::getAnalysisUsage(AU)
adds
addRequired<ScopInfo>();
what you'd need with this change is
addRequiredTransitive<ScopInfo>();

To avoid transitive requirements, I suggest per-granularity DependenceInfo passes:
DependenceInfo(Dependences::AnalysisLevel) {}

[etherzhhb]

include/polly/DependenceInfo.h

58

will do

lib/Analysis/DependenceInfo.cpp

793–794

ScopPass::getAnalysisUsage(AU)
adds
addRequired<ScopInfo>();
what you'd need with this change is
addRequiredTransitive<ScopInfo>();

I am confused, could you explain a little bit?

I guess even with the previous DependenceInfo, we also need 'addRequiredTransitive<ScopInfo>();'

Otherwise, why the previous DependenceInfo do not need this, but this change need 'addRequiredTransitive<ScopInfo>();'?

793–794

To avoid transitive requirements, I suggest per-granularity DependenceInfo passes:
DependenceInfo(Dependences::AnalysisLevel) {}

This can also be done, but I need to figure out some implementation details.

[grosser]

To avoid transitive requirements, I suggest per-granularity DependenceInfo passes:
DependenceInfo(Dependences::AnalysisLevel) {}

This can also be done, but I need to figure out some implementation details.

I am not convinced per-granularity passes are the right thing. I would
personally probably just add functions to ask for the different
dependences and build them on-demand when they are requested to avoid
the permanent overhead of eagerly computing all dependences.

Best,
Tobias

[etherzhhb]

lib/Analysis/DependenceInfo.cpp

793–794

ScopPass::getAnalysisUsage(AU)
adds
addRequired<ScopInfo>();
what you'd need with this change is
addRequiredTransitive<ScopInfo>();

I am confused, could you explain a little bit?

I guess even with the previous DependenceInfo, we also need 'addRequiredTransitive<ScopInfo>();'

Otherwise, why the previous DependenceInfo do not need this, but this change need 'addRequiredTransitive<ScopInfo>();'?

I think I know why.

Because originally we compute Dependences in runOnScop, when we call printScop/getDependences, we simply return the calculated Dependences, the Scop do not need to present.

However, practically, all Scop analyses should "addRequiredTransitive<ScopInfo>();", since they are all calculated based on the Scop. If the Scop is invalided, the corresponding analysis results should also be invalided. Especially when the Scop is invalided by the transformations that change CFG and/or memory access behaviors.

[grosser]

I think I know why.

Because originally we compute Dependences in runOnScop, when we call printScop/getDependences, we simply return the calculated Dependences, the Scop do not need to present.

However, practically, all Scop analyses should "addRequiredTransitive<ScopInfo>();", since they are all calculated based on the Scop. If the Scop is invalided, the corresponding analysis results should also be invalided. Especially when the Scop is invalided by the transformations that change CFG and/or memory access behaviors.

Right. We should add RequiredTransitive. Feel free to change this.

Best,
Tobias

[etherzhhb]

Update based on the comments

[Meinersbur]

lib/Analysis/DependenceInfo.cpp

793–794

Apart from recomputeDependences() the DependenceInfo did not need the Scop anymore. All results were stored in isl_* structures.

However, the analysis results without having the ScopStmt, MemoryAccess they were computed from available might be not that useful, but it is not strictly necessary. So I guess, no problem with always using addRequiredTransitive<ScopInfo>(). Users of DependenceInfo will have a addRequired[Transitive]<ScopInfo>() anyway.

[etherzhhb]

lib/Analysis/DependenceInfo.cpp

793–794

Apart from recomputeDependences() the DependenceInfo did not need the Scop anymore. All results were stored in isl_* structures.

However, the analysis results without having the ScopStmt, MemoryAccess they were computed from available might be not that useful, but it is not strictly necessary. So I guess, no problem with always using addRequiredTransitive<ScopInfo>(). Users of DependenceInfo will have a addRequired[Transitive]<ScopInfo>() anyway.

One of the examples about using DependencesInfo without ScopStmt, MemoryAccess is an analysis pass for memory dependencies between llvm instructions based on the access-level dependences, the end users of such a pass is interested in Scop, but llvm instructions.

[grosser]

Hi ether,

this change looks generally good to me.

include/polly/DependenceInfo.h

222

Would clearing the full map also work?

[etherzhhb]

include/polly/DependenceInfo.h

222

D is an array, may be I should look at something like DeleteContainerPointers

[grosser]

Ah, OK. Then this is probably fine.

Best,
Tobias

[etherzhhb]

r262591

include/polly/DependenceInfo.h

 class MemoryAccess;
 
 /// @brief The accumulated dependence information for a SCoP.
 ///
 /// The Dependences struct holds all dependence information we collect and
 /// 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<MemoryAccess *, isl_map *>;
 
   /// @brief Map type to associate statements with schedules.
   using StatementToIslMapTy = DenseMap<ScopStmt *, isl_map *>;
 
   /// @brief The type of the dependences.
struct Dependences {
   /// To restrict access to the internal state, only the DependenceInfo class
   /// is able to call or modify a Dependences struct.
   friend class DependenceInfo;
 
   /// @brief Destructor that will free internal objects.
   ~Dependences() { releaseMemory(); }
 
 private:
-  /// @brief Create an empty Dependences struct.
-  explicit Dependences(const std::shared_ptr<isl_ctx> &IslCtx)
+  /// @brief Create an empty dependences struct.
+  explicit Dependences(const std::shared_ptr<isl_ctx> &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();
 
   /// @brief Calculate the dependences for a certain SCoP @p S.
   void calculateDependences(Scop &S);
 
   /// @brief Set the reduction dependences for @p MA to @p Deps.
private:
   /// @brief The (reverse) transitive closure of reduction dependences.
   isl_union_map *TC_RED;
 
   /// @brief Mapping from memory accesses to their reduction dependences.
   ReductionDependencesMapTy ReductionDependences;
 
   /// @brief Isl context from the SCoP.
   std::shared_ptr<isl_ctx> IslCtx;
+
+  /// @brief Granularity of this dependence analysis
+  const AnalyisLevel Level;
 };
 
 class DependenceInfo : public ScopPass {
 public:
   static char ID;
 
   /// @brief Construct a new DependenceInfo pass.
   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;
 
 private:
   Scop *S;
 
   /// @brief Dependences struct for the current SCoP.
-  std::unique_ptr<Dependences> D;
+  std::unique_ptr<Dependences> D[Dependences::NumAnalysisLevels];
 };
 
 } // End polly namespace.
 
 namespace llvm {
 class PassRegistry;
 void initializeDependenceInfoPass(llvm::PassRegistry &);
 }
 
 #endif

lib/Analysis/DependenceInfo.cpp

static cl::opt<enum AnalysisType> OptAnalysisType(
     cl::values(clEnumValN(VALUE_BASED_ANALYSIS, "value-based",
                           "Exact dependences without transitive dependences"),
                clEnumValN(MEMORY_BASED_ANALYSIS, "memory-based",
                           "Overapproximation of dependences"),
                clEnumValEnd),
     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<enum AnalyisLevel> OptAnalysisLevel(
+static cl::opt<Dependences::AnalyisLevel> 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));
 
 //===----------------------------------------------------------------------===//
 
 /// @brief Tag the @p Relation domain with @p TagId
 static __isl_give isl_map *tag(__isl_take isl_map *Relation,
                                __isl_take isl_id *TagId) {
   isl_space *Space = isl_map_get_space(Relation);
   Space = isl_space_drop_dims(Space, isl_dim_out, 0, isl_map_n_out(Relation));
   Space = isl_space_set_tuple_id(Space, isl_dim_out, TagId);
   isl_multi_aff *Tag = isl_multi_aff_domain_map(Space);
   Relation = isl_map_preimage_domain_multi_aff(Relation, Tag);
   return 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.
   return Relation;
 }
 
 /// @brief Collect information about the SCoP @p S.
 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));
   *MayWrite = isl_union_map_empty(isl_space_copy(Space));
   *AccessSchedule = isl_union_map_empty(isl_space_copy(Space));
   *StmtSchedule = isl_union_map_empty(Space);
 
   SmallPtrSet<const Value *, 8> ReductionBaseValues;
for (MemoryAccess *MA : Stmt) {
         isl_map *Schedule = Stmt.getSchedule();
         Schedule = isl_map_apply_domain(
             Schedule,
             isl_map_reverse(isl_map_domain_map(isl_map_copy(accdom))));
         accdom = isl_map_range_map(accdom);
 
         *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);
         }
       }
 
       if (MA->isRead())
         *Read = isl_union_map_add_map(*Read, accdom);
       else
         *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());
   }
 
   *StmtSchedule =
       isl_union_map_intersect_params(*StmtSchedule, S.getAssumedContext());
 
   *Read = isl_union_map_coalesce(*Read);
   *Write = isl_union_map_coalesce(*Write);

 }
 
 void Dependences::calculateDependences(Scop &S) {
   isl_union_map *Read, *Write, *MayWrite, *AccessSchedule, *StmtSchedule;
   isl_schedule *Schedule;
 
   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';
         dbgs() << "MayWrite: " << MayWrite << '\n';
         dbgs() << "AccessSchedule: " << AccessSchedule << '\n';
         dbgs() << "StmtSchedule: " << StmtSchedule << '\n';);
 
   if (isl_union_map_is_empty(AccessSchedule)) {
     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);
       Schedule = isl_schedule_pullback_union_pw_multi_aff(Schedule, Tags);
     }
   } else {
     auto *ScheduleMap =
         isl_union_map_union(AccessSchedule, isl_union_map_copy(StmtSchedule));

 }
 
 void Dependences::setReductionDependences(MemoryAccess *MA, isl_map *D) {
   assert(ReductionDependences.count(MA) == 0 &&
          "Reduction dependences set twice!");
   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<ScopInfo>();
+  AU.setPreservesAll();
 }
 
 char DependenceInfo::ID = 0;
 
 Pass *polly::createDependenceInfoPass() { return new DependenceInfo(); }
 
 INITIALIZE_PASS_BEGIN(DependenceInfo, "polly-dependences",
                       "Polly - Calculate dependences", false, false);
 INITIALIZE_PASS_DEPENDENCY(ScopInfo);
 INITIALIZE_PASS_END(DependenceInfo, "polly-dependences",
                     "Polly - Calculate dependences", false, false)

lib/CodeGen/IslAst.cpp

 }
 
 bool IslAstInfo::runOnScop(Scop &Scop) {
   if (Ast)
     delete Ast;
 
   S = &Scop;
 
-  const Dependences &D = getAnalysis<DependenceInfo>().getDependences();
+  const Dependences &D =
+      getAnalysis<DependenceInfo>().getDependences(Dependences::AL_Statement);
 
   Ast = IslAst::create(&Scop, D);
 
   DEBUG(printScop(dbgs(), Scop));
   return false;
 }
 
 __isl_give isl_ast_node *IslAstInfo::getAst() const { return Ast->getAst(); }

lib/Exchange/JSONExporter.cpp

for (std::vector<std::string>::const_iterator I = newAccessStrings.begin(),
        I != E; I++)
     OS << "New access function '" << *I << "'detected in JSCOP file\n";
 }
 
 typedef Dependences::StatementToIslMapTy StatementToIslMapTy;
 
 bool JSONImporter::runOnScop(Scop &S) {
   Region &R = S.getRegion();
-  const Dependences &D = getAnalysis<DependenceInfo>().getDependences();
+  const Dependences &D =
+      getAnalysis<DependenceInfo>().getDependences(Dependences::AL_Statement);
   const DataLayout &DL =
       S.getRegion().getEntry()->getParent()->getParent()->getDataLayout();
 
   std::string FileName = ImportDir + "/" + getFileName(S);
 
   std::string FunctionName = R.getEntry()->getParent()->getName();
   errs() << "Reading JScop '" << R.getNameStr() << "' in function '"
          << FunctionName << "' from '" << FileName << "'.\n";

lib/Transform/DeadCodeElimination.cpp

 /// o Following each RAW dependency from a live iteration backwards and adding
 ///   that iteration to the live set.
 ///
 /// To ensure the set of live iterations does not get too complex we always
 /// combine a certain number of precise steps with one approximating step that
 /// simplifies the life set with an affine hull.
 bool DeadCodeElim::eliminateDeadCode(Scop &S, int PreciseSteps) {
   DependenceInfo &DI = getAnalysis<DependenceInfo>();
-  const Dependences &D = DI.getDependences();
+  const Dependences &D = DI.getDependences(Dependences::AL_Statement);
 
   if (!D.hasValidDependences())
     return false;
 
   isl_union_set *Live = getLiveOut(S);
   isl_union_map *Dep =
       D.getDependences(Dependences::TYPE_RAW | Dependences::TYPE_RED);
   Dep = isl_union_map_reverse(Dep);
bool DeadCodeElim::eliminateDeadCode(Scop &S, int PreciseSteps) {
   isl_union_map_free(Dep);
   isl_union_set_free(OriginalDomain);
 
   bool Changed = S.restrictDomains(isl_union_set_coalesce(Live));
 
   // 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;
 }
 
 bool DeadCodeElim::runOnScop(Scop &S) {
   return eliminateDeadCode(S, DCEPreciseSteps);
 }
 
 void DeadCodeElim::getAnalysisUsage(AnalysisUsage &AU) const {

lib/Transform/ScheduleOptimizer.cpp

bool IslScheduleOptimizer::runOnScop(Scop &S) {
 
   // Skip empty SCoPs but still allow code generation as it will delete the
   // loops present but not needed.
   if (S.getSize() == 0) {
     S.markAsOptimized();
     return false;
   }
 
-  const Dependences &D = getAnalysis<DependenceInfo>().getDependences();
+  const Dependences &D =
+      getAnalysis<DependenceInfo>().getDependences(Dependences::AL_Statement);
 
   if (!D.hasValidDependences())
     return false;
 
   isl_schedule_free(LastSchedule);
   LastSchedule = nullptr;
 
   // Build input data.