[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

245

Move this to the private section of the class please.

252

@param S

lib/Analysis/DependenceInfo.cpp

808

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

assertion message seems odd.

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

837

Empty line + @brief comment in the cpp file.

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

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();

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)

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);

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

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

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 }

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: