[Polly][GSoC 2016]New function pass ScopInfoWrapperPass

[cs14mtech11017]

Summary

This patch adds a new function pass ScopInfoWrapperPass so that the polyhedral description of a region, the SCoP,
can be constructed and used in a function pass.

Depends on D20831

[jdoerfert]

include/polly/ScopInfo.h

2526

Why top level regions? I don't think that is true.

2528

what is a "larger pass"? Maybe just replace this by sth like:

This pass is an alternative to the ScopInfoRegionPass in order to avoid a region pass manager.

2540

RegionToScopMap;

2549

Scop *getScop(Region *R) const {
  return RegionToScopMap.lookup();
}

2558

You don't need this function, the above should be enough.

2572

What's the point of the unique_ptr if we treat them as raw_ptrs anyway?

If I am not mistaken you can remove this loop and only clear the map. The unique_ptrs should automatically call delete on the Scops they point to.

lib/Analysis/ScopInfo.cpp

4886

I don't like such lines, if nobody is in favour of them I would say we do not introduce them.

4945

See above.

4970

for (auto R : SD) { ... }

4976

RegionToScopMap[R] = SB.getScop();

4982

It

Please take another look at the naming convention we use.

4995

polly-scops-all sounds more like "detect unprofitable scops" than "detect scops in a function scope". I would call it -polly-scops-function or -polly-function-scops or somehing similar..

[Meinersbur]

include/polly/ScopInfo.h

2565–2566

You declared a const_iterator type. Can you also define const begin() and end()?

lib/Analysis/ScopInfo.cpp

4886

I second that.

4959

Can you use inline declarations when possible?

auto *R = const_cast<Region *>(*I);

[jdoerfert]

Please add some test (e.g., add run lines for this pass).

include/polly/ScopInfo.h

2565–2566

Or remove the const_iterator.

[etherzhhb]

include/polly/ScopInfo.h

2548

Could we document what happened if a children region of a SCoP region is passed to this function?

Supposed we built Scop S0 for Region R_0, and R_0 has a child (contains) R_1.

What I am getting if I call getScop(R_1)?

2551–2554

These if-else could written as the following to reduce indent:

if (it != regionToScopMap.end())
  return it->second.get();

return nullptr;

lib/Analysis/ScopInfo.cpp

4976

Or

bool Inserted = RegionToScopMap.insert(std::make_pair(R, SB.getScop())).second;
assert(Inserted && "Building Scop for the same region twice!");
(void) Inserted;

4982

http://llvm.org/docs/CodingStandards.html

[cs14mtech11017]

Thank you for your inputs. I have updated the patch accordingly.
Please let me know if this set of test cases is not enough.

include/polly/ScopInfo.h

2549

RegionToScopMap.lookup() does not support unique_ptr.

[grosser]

No technical input. Just wanted to say thank you for everybody helping with reviewing these patches. This really goes very well.

include/polly/LinkAllPasses.h

 llvm::Pass *createDOTOnlyViewerPass();
 llvm::Pass *createDOTPrinterPass();
 llvm::Pass *createDOTViewerPass();
 llvm::Pass *createJSONExporterPass();
 llvm::Pass *createJSONImporterPass();
 llvm::Pass *createPollyCanonicalizePass();
 llvm::Pass *createScopDetectionPass();
 llvm::Pass *createScopInfoRegionPassPass();
+llvm::Pass *createScopInfoWrapperPassPass();
 llvm::Pass *createIslAstInfoPass();
 llvm::Pass *createCodeGenerationPass();
 llvm::Pass *createIslScheduleOptimizerPass();
 
 extern char &CodePreparationID;
 }
 
 namespace {

include/polly/ScopInfo.h

public:
 
   void releaseMemory() override { S.reset(); }
 
   void print(raw_ostream &O, const Module *M = nullptr) const override;
 
   void getAnalysisUsage(AnalysisUsage &AU) const override;
 };
 
+//===----------------------------------------------------------------------===//
+/// @brief The legacy pass manager's analysis pass to compute scop information
+///        for the whole function.
+///
+/// This pass will maintain a map of the maximal region within a scop to its
+/// scop object for all the feasible scops present in a function.
+/// This pass is an alternative to the ScopInfoRegionPass in order to avoid a
+/// region pass manager.
+class ScopInfoWrapperPass : public FunctionPass {
+
+public:
+  using RegionToScopMapTy = DenseMap<Region *, std::unique_ptr<Scop>>;
+  using iterator = RegionToScopMapTy::iterator;
+  using const_iterator = RegionToScopMapTy::const_iterator;
+
+private:
+  /// @brief A map of Region to its Scop object containing
+  ///        Polly IR of static control part
+  RegionToScopMapTy RegionToScopMap;
+
+public:
+  static char ID; // Pass identification, replacement for typeid
+
+  ScopInfoWrapperPass() : FunctionPass(ID) {}
+  ~ScopInfoWrapperPass() {}
+
+  /// @brief Get the Scop object for the given Region
+  ///
+  /// @return If the given region is the maximal region within a scop, return
+  ///         the scop object. If the given region is a subregion, return a
+  ///         nullptr. Top level region containing the entry block of a function
+  ///         is not considered in the scop creation.
+  Scop *getScop(Region *R) const {
+    auto MapIt = RegionToScopMap.find(R);
+    if (MapIt != RegionToScopMap.end())
+      return MapIt->second.get();
+    return nullptr;
+  }
+
+  iterator begin() { return RegionToScopMap.begin(); }
+  iterator end() { return RegionToScopMap.end(); }
+  const_iterator begin() const { return RegionToScopMap.begin(); }
+  const_iterator end() const { return RegionToScopMap.end(); }
+
+  /// @brief Calculate all the polyhedral scops for a given function.
+  bool runOnFunction(Function &F) override;
+
+  void releaseMemory() override { RegionToScopMap.clear(); }
+
+  void print(raw_ostream &O, const Module *M = nullptr) const override;
+
+  void getAnalysisUsage(AnalysisUsage &AU) const override;
+};
+
 } // end namespace polly
 
 namespace llvm {
 class PassRegistry;
 void initializeScopInfoRegionPassPass(llvm::PassRegistry &);
+void initializeScopInfoWrapperPassPass(llvm::PassRegistry &);
 }
 
 #endif

lib/Analysis/ScopInfo.cpp

if (scop->getMaxLoopDepth() > 0)
       ++RichScopFound;
   }
 
   emitOptimizationRemarkAnalysis(F->getContext(), DEBUG_TYPE, *F, End, Msg);
 }
 
 //===----------------------------------------------------------------------===//
 void ScopInfoRegionPass::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.addRequired<LoopInfoWrapperPass>();
   AU.addRequired<RegionInfoPass>();
   AU.addRequired<DominatorTreeWrapperPass>();
   AU.addRequiredTransitive<ScalarEvolutionWrapperPass>();
   AU.addRequiredTransitive<ScopDetection>();
   AU.addRequired<AAResultsWrapperPass>();
   AU.addRequired<AssumptionCacheTracker>();
   AU.setPreservesAll();
 }

 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass);
 INITIALIZE_PASS_DEPENDENCY(RegionInfoPass);
 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass);
 INITIALIZE_PASS_DEPENDENCY(ScopDetection);
 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass);
 INITIALIZE_PASS_END(ScopInfoRegionPass, "polly-scops",
                     "Polly - Create polyhedral description of Scops", false,
                     false)
+
+//===----------------------------------------------------------------------===//
+void ScopInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
+  AU.addRequired<LoopInfoWrapperPass>();
+  AU.addRequired<RegionInfoPass>();
+  AU.addRequired<DominatorTreeWrapperPass>();
+  AU.addRequiredTransitive<ScalarEvolutionWrapperPass>();
+  AU.addRequiredTransitive<ScopDetection>();
+  AU.addRequired<AAResultsWrapperPass>();
+  AU.addRequired<AssumptionCacheTracker>();
+  AU.setPreservesAll();
+}
+
+bool ScopInfoWrapperPass::runOnFunction(Function &F) {
+  auto &SD = getAnalysis<ScopDetection>();
+
+  auto &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
+  auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
+  auto &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
+  auto const &DL = F.getParent()->getDataLayout();
+  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
+  auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
+
+  /// Create polyhedral descripton of scops for all the valid regions of a
+  /// function.
+  for (auto &It : SD) {
+    Region *R = const_cast<Region *>(It);
+    if (!SD.isMaxRegionInScop(*R))
+      continue;
+
+    ScopBuilder SB(R, AC, AA, DL, DT, LI, SD, SE);
+    bool Inserted =
+        RegionToScopMap.insert(std::make_pair(R, SB.getScop())).second;
+    assert(Inserted && "Building Scop for the same region twice!");
+    (void)Inserted;
+  }
+  return false;
+}
+
+void ScopInfoWrapperPass::print(raw_ostream &OS, const Module *) const {
+  for (auto &It : RegionToScopMap) {
+    if (It.second)
+      It.second->print(OS);
+    else
+      OS << "Invalid Scop!\n";
+  }
+}
+
+char ScopInfoWrapperPass::ID = 0;
+
+Pass *polly::createScopInfoWrapperPassPass() {
+  return new ScopInfoWrapperPass();
+}
+
+INITIALIZE_PASS_BEGIN(
+    ScopInfoWrapperPass, "polly-function-scops",
+    "Polly - Create polyhedral description of all Scops of a function", false,
+    false);
+INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass);
+INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker);
+INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass);
+INITIALIZE_PASS_DEPENDENCY(RegionInfoPass);
+INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass);
+INITIALIZE_PASS_DEPENDENCY(ScopDetection);
+INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass);
+INITIALIZE_PASS_END(
+    ScopInfoWrapperPass, "polly-function-scops",
+    "Polly - Create polyhedral description of all Scops of a function", false,
+    false)

lib/Support/RegisterPasses.cpp

void initializePollyPasses(PassRegistry &Registry) {
   initializeDependenceInfoPass(Registry);
   initializeJSONExporterPass(Registry);
   initializeJSONImporterPass(Registry);
   initializeIslAstInfoPass(Registry);
   initializeIslScheduleOptimizerPass(Registry);
   initializePollyCanonicalizePass(Registry);
   initializeScopDetectionPass(Registry);
   initializeScopInfoRegionPassPass(Registry);
+  initializeScopInfoWrapperPassPass(Registry);
   initializeCodegenCleanupPass(Registry);
 }
 
 /// @brief Register Polly passes such that they form a polyhedral optimizer.
 ///
 /// The individual Polly passes are registered in the pass manager such that
 /// they form a full polyhedral optimizer. The flow of the optimizer starts with
 /// a set of preparing transformations that canonicalize the LLVM-IR such that

test/ScopInfo/assume_gep_bounds.ll

 ; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+; RUN: opt %loadPolly -polly-function-scops -analyze < %s | FileCheck %s
 
 ;    void foo(float A[][20][30], long n, long m, long p) {
 ;      for (long i = 0; i < n; i++)
 ;        for (long j = 0; j < m; j++)
 ;          for (long k = 0; k < p; k++)
 ;            A[i][j][k] = i + j + k;
 ;    }
 

test/ScopInfo/constant_factor_in_parameter.ll

 ; RUN: opt %loadPolly -analyze -polly-scops < %s | FileCheck %s
+; RUN: opt %loadPolly -analyze -polly-function-scops < %s | FileCheck %s
 ;
 ; Check that the constant part of the N * M * 4 expression is not part of the
 ; parameter but explicit in the access function. This can avoid existentially
 ; quantified variables, e.g., when computing the stride.
 ;
 ; CHECK: p1: (%N * %M)
 ; CHECK: [N, p_1] -> { Stmt_for_body[i0] -> MemRef_A[4p_1 + i0] };
 ;

test/ScopInfo/invariant_load_loop_ub.ll

 ; RUN: opt %loadPolly -polly-scops -polly-process-unprofitable -analyze < %s | FileCheck %s
+; RUN: opt %loadPolly -polly-function-scops -polly-process-unprofitable -analyze < %s | FileCheck %s
 ;
 ; CHECK: Invariant Accesses:
 ; CHECK-NEXT: ReadAccess := [Reduction Type: NONE] [Scalar: 0]
 ; CHECK-NEXT:   { Stmt_bb1[i0] -> MemRef_UB[0] };
 ;
 ;    void f(int *A, int *UB) {
 ;      for (int i = 0; i < *UB; i++)
 ;        A[i] = 0;

test/ScopInfo/loop_affine_bound_0.ll

 ; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+; RUN: opt %loadPolly -polly-function-scops -analyze < %s | FileCheck %s
 
 ; void f(long a[][128], long N, long M) {
 ;   long i, j;
 ;   for (j = 0; j < (4*N + 7*M +3); ++j)
 ;     for (i = 0; i < (5*N + 2); ++i)
 ;       a[j][i] = 0
 ;   }
 

test/ScopInfo/loop_affine_bound_1.ll

 ; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+; RUN: opt %loadPolly -polly-function-scops -analyze < %s | FileCheck %s
 
 ;void f(long a[][128], long N, long M) {
 ;  long i, j;
 ;  for (j = 0; j < (4*N + 7*M +3); ++j)
 ;    for (i = j; i < (5*N + 2); ++i)
 ;        ...
 ;}
 

test/ScopInfo/loop_affine_bound_2.ll

 ; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+; RUN: opt %loadPolly -polly-function-scops -analyze < %s | FileCheck %s
 
 ; void f(long a[][128], long N, long M) {
 ;   long i, j;
 ;   for (j = 0; j < (4*N + 7*M +3); ++j)
 ;     for (i = (7*j + 6*M -9); i < (3*j + 5*N + 2) ; ++i)
 ;         a[i][j] = 0;
 ; }
 

test/ScopInfo/multidim_2d-diagonal-matrix.ll

 ; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+; RUN: opt %loadPolly -polly-function-scops -analyze < %s | FileCheck %s
 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-S128"
 
 ; Derived from the following code:
 ;
 ; void foo(long n, double A[n][n]) {
 ;   for (long i = 0; i < n; i++)
 ;     A[i][i] = 1.0;
 ; }

test/ScopInfo/multidim_many_references.ll

 ; RUN: opt %loadPolly -polly-scops -analyze -polly-ignore-aliasing < %s | FileCheck %s
+; RUN: opt %loadPolly -polly-function-scops -analyze -polly-ignore-aliasing < %s | FileCheck %s
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 ; typedef struct Mat {
 ;   float* data;
 ;   long rows;
 ;   long cols;
 ;   long deps;

test/ScopInfo/multidim_nested_start_integer.ll

 ; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+; RUN: opt %loadPolly -polly-function-scops -analyze < %s | FileCheck %s
 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-S128"
 
 ; void foo(long n, long m, long o, double A[n][m][o]) {
 ;   for (long i = 0; i < n - 3; i++)
 ;     for (long j = 4; j < m; j++)
 ;       for (long k = 0; k < o - 7; k++)
 ;         A[i+3][j-4][k+7] = 1.0;
 ; }

test/ScopInfo/multidim_single_and_multidim_array.ll

 ; RUN: opt %loadPolly -polly-scops -polly-delinearize=false -analyze < %s | FileCheck %s
 ; RUN: opt %loadPolly -polly-scops -polly-delinearize=false -polly-allow-nonaffine -analyze < %s | FileCheck %s --check-prefix=NONAFFINE
 ; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s --check-prefix=DELIN
 ; RUN: opt %loadPolly -polly-scops -polly-allow-nonaffine -analyze < %s | FileCheck %s --check-prefix=DELIN
+; RUN: opt %loadPolly -polly-function-scops -polly-delinearize=false -analyze < %s | FileCheck %s
+; RUN: opt %loadPolly -polly-function-scops -polly-delinearize=false -polly-allow-nonaffine -analyze < %s | FileCheck %s --check-prefix=NONAFFINE
+; RUN: opt %loadPolly -polly-function-scops -analyze < %s | FileCheck %s --check-prefix=DELIN
+; RUN: opt %loadPolly -polly-function-scops -polly-allow-nonaffine -analyze < %s | FileCheck %s --check-prefix=DELIN
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 ; void single-and-multi-dimensional-array(long n,float X[n][n]) {
 ;  for (long i1 = 0; i1 < n; i1++)
 ;    X[i1][0] = 1;
 ;
 ;  for (long i2 = 0; i2 < n; i2++)

test/ScopInfo/non_affine_region_3.ll

 ; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+; RUN: opt %loadPolly -polly-function-scops -analyze < %s | FileCheck %s
 ;
 ; Verify the scalar x defined in a non-affine subregion is written as it
 ; escapes the region. In this test the two conditionals inside the region
 ; are expressed as one PHI nodes with three incoming values.
 ;
 ;    void f(int *A, int b) {
 ;      for (int i = 0; i < 1024; i++) {
 ;        int x = 0;

test/ScopInfo/reduction_two_identical_reads.ll

 ; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+; RUN: opt %loadPolly -polly-function-scops -analyze < %s | FileCheck %s
 ;
 ; CHECK: Reduction Type: NONE
 ;
 ; Check that we do not mark these accesses as reduction like.
 ; We do this for the case the loads are modelt with the same LLVM-IR value and
 ; for the case there are different LLVM-IR values.
 ;
 ;    void f(int *A) {

test/ScopInfo/scalar_to_array.ll

 ; RUN: opt %loadPolly -basicaa -polly-scops -analyze < %s | FileCheck %s
+; RUN: opt %loadPolly -basicaa -polly-function-scops -analyze < %s | FileCheck %s
 
 ; ModuleID = 'scalar_to_array.ll'
 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"
 
 @A = common global [1024 x float] zeroinitializer, align 8
 
 ; Terminating loops without side-effects will be optimzied away, hence
 ; detecting a scop would be pointless.

test/ScopInfo/test-wrapping-in-condition.ll

 ; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+; RUN: opt %loadPolly -polly-function-scops -analyze < %s | FileCheck %s
 ;
 ; CHECK:    Invalid Context:
 ; CHECK:        [N] -> {  : N >= 129 }
 ;
 ;    #include <stdlib.h>
 ;    #include <stdio.h>
 ;
 ;    void __attribute__((noinline)) foo(float *A, long N) {