[Polly][GSoC 2016][WIP]New function pass DependenceInfoWrapperPass

[cs14mtech11017]

Summary

This patch addresses -
#A new function pass to compute polyhedral dependences. This is required to avoid region pass manager
#Stores a map of Scop to Dependence object of all the scops present in a function. By default, access wise dependences are stored.

This is work in progress. Need reviews and comments to make it better.

Depends on D20962

[grosser]

Dear Utpal,

thanks for working on this. The general direction looks good. I leave the more detailed review to Johannes, Ether and whoever else has some input.

Best,
Tobias

[jdoerfert]

Please look at the comments and add some test cases as you did with the scopinfo function pass.

include/polly/DependenceInfo.h

243 ↗

(On Diff #59957)

Move this to the private section of the class please.

250 ↗

(On Diff #59957)

@param S

lib/Analysis/DependenceInfo.cpp

808 ↗

(On Diff #59957)

I am still not a fan of these lines and you introduce 2 of them in this patch. Could you remove them or do you think they really help?

825 ↗

(On Diff #59957)

assertion message seems odd.

And why cant we recompute dependences for the same SCoP? Isn't that what this function is all about?

837 ↗

(On Diff #59957)

Empty line + @brief comment in the cpp file.

polly/trunk/include/polly/DependenceInfo.h

struct Dependences {
   bool isValidSchedule(Scop &S, StatementToIslMapTy *NewSchedules) const;
 
   /// @brief Print the stored dependence information.
   void print(llvm::raw_ostream &OS) const;
 
   /// @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(); }
 
 private:
   /// @brief Create an empty dependences struct.
   explicit Dependences(const std::shared_ptr<isl_ctx> &IslCtx,
                        AnalyisLevel Level)

 
 private:
   Scop *S;
 
   /// @brief Dependences struct for the current SCoP.
   std::unique_ptr<Dependences> 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<Scop *, std::unique_ptr<Dependences>>;
+
+  /// @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

polly/trunk/include/polly/LinkAllPasses.h

 class PassRegistry;
 class RegionPass;
 } // namespace llvm
 
 namespace polly {
 llvm::Pass *createCodePreparationPass();
 llvm::Pass *createDeadCodeElimPass();
 llvm::Pass *createDependenceInfoPass();
+llvm::Pass *createDependenceInfoWrapperPassPass();
 llvm::Pass *createDOTOnlyPrinterPass();
 llvm::Pass *createDOTOnlyViewerPass();
 llvm::Pass *createDOTPrinterPass();
 llvm::Pass *createDOTViewerPass();
 llvm::Pass *createJSONExporterPass();
 llvm::Pass *createJSONImporterPass();
 llvm::Pass *createPollyCanonicalizePass();
 llvm::Pass *createScopDetectionPass();

polly/trunk/lib/Analysis/DependenceInfo.cpp

 
 Pass *polly::createDependenceInfoPass() { return new DependenceInfo(); }
 
 INITIALIZE_PASS_BEGIN(DependenceInfo, "polly-dependences",
                       "Polly - Calculate dependences", false, false);
 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<Dependences> 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<ScopInfoWrapperPass>();
+  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<ScopInfoWrapperPass>();
+  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)

polly/trunk/lib/Support/RegisterPasses.cpp

CFGPrinter("polly-view-cfg",
                cl::Hidden, cl::init(false), cl::cat(PollyCategory));
 
 namespace polly {
 void initializePollyPasses(PassRegistry &Registry) {
   initializeCodeGenerationPass(Registry);
   initializeCodePreparationPass(Registry);
   initializeDeadCodeElimPass(Registry);
   initializeDependenceInfoPass(Registry);
+  initializeDependenceInfoWrapperPassPass(Registry);
   initializeJSONExporterPass(Registry);
   initializeJSONImporterPass(Registry);
   initializeIslAstInfoPass(Registry);
   initializeIslScheduleOptimizerPass(Registry);
   initializePollyCanonicalizePass(Registry);
   initializeScopDetectionPass(Registry);
   initializeScopInfoRegionPassPass(Registry);
   initializeScopInfoWrapperPassPass(Registry);

polly/trunk/test/DependenceInfo/computeout.ll

 ; 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++ )
 ; S1:   A[i] = 2;
 ;
 ;     for (i = 0; i < 10; i++ )
 ; S2:   A[i]  = 5;
 ;

 
 ; VALUE:      RAW dependences:
 ; VALUE-NEXT:     {  }
 ; VALUE-NEXT: WAR dependences:
 ; VALUE-NEXT:     {  }
 ; 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:
 ; TIMEOUT-NEXT:     n/a
 ; TIMEOUT-NEXT: WAW dependences:
 ; TIMEOUT-NEXT:     n/a

polly/trunk/test/DependenceInfo/different_schedule_dimensions.ll

 ; 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] }
 ; CHECK: WAR dependences:
 ; CHECK:   {  }
 ; CHECK: WAW dependences:
 ; CHECK:   { Stmt_bb3[0] -> Stmt_bb10[0] }
 ; 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) {
 bb:
   br label %bb2
 
 bb2:                                              ; preds = %bb
   br label %bb3

polly/trunk/test/DependenceInfo/do_pluto_matmult.ll

 ; 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"
 
 %struct._IO_FILE = type { i32, i8*, i8*, i8*, i8*, i8*, i8*, i8*, i8*, i8*, i8*, i8*, %struct._IO_marker*, %struct._IO_FILE*, i32, i32, i64, i16, i8, [1 x i8], i8*, i64, i8*, i8*, i8*, i8*, i64, i32, [20 x i8] }
 %struct._IO_marker = type { %struct._IO_marker*, %struct._IO_FILE*, i32 }
 
 @A = common global [36 x [49 x double]] zeroinitializer, align 8 ; <[36 x [49 x double]]*> [#uses=3]
 @B = common global [36 x [49 x double]] zeroinitializer, align 8 ; <[36 x [49 x double]]*> [#uses=3]

 ; VALUE-NEXT:     { Stmt_do_body2[i0, i1, i2] -> Stmt_do_body2[i0, i1, 1 + i2] : 0 <= i0 <= 35 and 0 <= i1 <= 35 and 0 <= i2 <= 34 }
 
 ; MEMORY:      RAW 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 }
 ; MEMORY-NEXT: WAR 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 }
 ; 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 }

polly/trunk/test/DependenceInfo/fine_grain_dep_0.ll

 ; 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 }
 ; REF-NEXT: WAR dependences:
 ; REF-NEXT:     {  }
 ; REF-NEXT: WAW dependences:
 ; REF-NEXT:     {  }
 ; REF-NEXT: Reduction dependences: