[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

2517

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

2519

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.

2531

RegionToScopMap;

2540

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

2549

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

2563

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

4876

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

4937

See above.

4962

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

4968

RegionToScopMap[R] = SB.getScop();

4974

It

Please take another look at the naming convention we use.

4987

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

2556–2557

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

lib/Analysis/ScopInfo.cpp

4876

I second that.

4951

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

2556–2557

Or remove the const_iterator.

[etherzhhb]

include/polly/ScopInfo.h

2539

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

2542–2545

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

4968

Or

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

4974

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

2540

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 Region to its Scop object for all the
+/// top level regions present in the function.
+/// This pass is designed to be used by other larger passes such as
+/// PolyhedralInfo function pass as currently it is not feasible to schedula a
+/// region pass from a function pass in LLVM.
+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 ScopInfo object for the given Region
+  Scop *getScop(Region *R) {
+    auto it = regionToScopMap.find(R);
+    if (it != regionToScopMap.end())
+      return it->second.get();
+    else
+      return nullptr;
+  }
+
+  const Scop *getScop(Region *R) const {
+    auto it = regionToScopMap.find(R);
+    if (it != regionToScopMap.end())
+      return it->second.get();
+    else
+      return nullptr;
+  }
+
+  iterator begin() { return regionToScopMap.begin(); }
+  iterator end() { return regionToScopMap.end(); }
+
+  /// @brief Calculate all the polyhedral scops for a given function.
+  bool runOnFunction(Function &F) override;
+
+  void releaseMemory() override {
+    for (auto &it : regionToScopMap) {
+      it.second.reset();
+    }
+    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->hasFeasibleRuntimeContext()) {
     if (scop->getMaxLoopDepth() > 0)
       ++RichScopFound;
   }
 
   emitOptimizationRemarkAnalysis(F->getContext(), DEBUG_TYPE, *F, End, Msg);
 }
 
 //===----------------------------------------------------------------------===//
+/// Implementation of ScopInfoRegionPass begins here.
+//
 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>();

 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)
+
+//===----------------------------------------------------------------------===//
+/// Implementation of ScopInfoRegion pass ends here.
+
+//===----------------------------------------------------------------------===//
+/// Implementation of ScopInfoWrapperPass begins here.
+//
+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>();
+  Region *R;
+
+  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 (ScopDetection::iterator I = SD.begin(), E = SD.end(); I != E; ++I) {
+    R = const_cast<Region *>(*I);
+    if (!SD.isMaxRegionInScop(*R))
+      continue;
+
+    ScopBuilder SB(R, AC, AA, DL, DT, LI, SD, SE);
+    regionToScopMap.insert(std::make_pair(R, SB.getScop()));
+  }
+  return false;
+}
+
+void ScopInfoWrapperPass::print(raw_ostream &OS, const Module *) const {
+  for (auto &it : regionToScopMap) {
+    if (it.second)
+      it.second->print(OS);
+  }
+}
+
+char ScopInfoWrapperPass::ID = 0;
+
+Pass *polly::createScopInfoWrapperPassPass() {
+  return new ScopInfoWrapperPass();
+}
+
+INITIALIZE_PASS_BEGIN(
+    ScopInfoWrapperPass, "polly-scops-all",
+    "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-scops-all",
+    "Polly - Create polyhedral description of all Scops of a function", false,
+    false)