[Polly] Make TempScopInfo a RegionPass

[Meinersbur]

Summary

This modifies the order in which Polly passes are executed.

Assuming a function has two scops (A and B), the order before was:

FunctionPassManager:

ScopDetection
IndependentBlocks
TempScopInfo for A and B
RegionPassManager:
  ScopInfo for A
  DependenceInfo for A
  IslScheduleOptimizer for A
  IslAstInfo for A
  CodeGeneration for A
  ScopInfo for B
  DependenceInfo for B
  IslScheduleOptimizer for B
  IslAstInfo for B
  CodeGeneration for B

After this patch:

FunctionPassManager:

ScopDetection
IndependentBlocks
RegionPassManager:
  TempScopInfo for A
  ScopInfo for A
  DependenceInfo for A
  IslScheduleOptimizer for A
  IslAstInfo for A
  CodeGeneration for A
  TempScopInfo for B
  ScopInfo for B
  DependenceInfo for B
  IslScheduleOptimizer for B
  IslAstInfo for B
  CodeGeneration for B

TempScopInfo for B might store information and references to the IR that CodeGeneration for A might modify. Changing the order ensures that the IR is not modified from the analysis of a region until code generation.

This is a preparation for allowing PHI nodes in exit blocks which are entries for different regions. CodeGeneration would "steal" each other's PHI nodes.

[Meinersbur]

The planned removal/merging of TempScopInfo will effectively do the same.

[grosser]

LGTM, if this passes LNT.

Tobias

[Meinersbur]

It does ; can you accept it if it's OK? Otherwise Arcanist refuses.

include/polly/TempScopInfo.h

void printDetail(raw_ostream &OS, ScalarEvolution *SE, LoopInfo *LI,
                    const Region *Reg, unsigned ind) const;
 };
 
 typedef std::map<const Region *, TempScop *> TempScopMapType;
 //===----------------------------------------------------------------------===//
 /// @brief The Function Pass to extract temporary information for Static control
 ///        part in llvm function.
 ///
-class TempScopInfo : public FunctionPass {
+class TempScopInfo : public RegionPass {
   //===-------------------------------------------------------------------===//
   TempScopInfo(const TempScopInfo &) = delete;
   const TempScopInfo &operator=(const TempScopInfo &) = delete;
 
   // The ScalarEvolution to help building Scop.
   ScalarEvolution *SE;
 
   // LoopInfo for information about loops
class TempScopInfo : public RegionPass {
 
   // Access function of statements (currently BasicBlocks) .
   AccFuncMapType AccFuncMap;
 
   // Pre-created zero for the scalar accesses, with it we do not need create a
   // zero scev every time when we need it.
   const SCEV *ZeroOffset;
 
-  // Mapping regions to the corresponding Scop in current function.
-  TempScopMapType TempScops;
+  // The TempScop for this region.
+  TempScop *TempScopOfRegion;
 
   // Clear the context.
   void clear();
 
   /// @brief Build condition constrains to BBs in a valid Scop.
   ///
   /// @param BB The BasicBlock to build condition constrains
   /// @param R  The region for the current TempScop.
class TempScopInfo : public RegionPass {
   /// @param R                  The SCoP region.
   /// @param BB                 A basic block in @p R.
   /// @param NonAffineSubRegion The non affine sub-region @p BB is in.
   void buildAccessFunctions(Region &R, BasicBlock &BB,
                             Region *NonAffineSubRegion = nullptr);
 
 public:
   static char ID;
-  explicit TempScopInfo() : FunctionPass(ID) {}
+  explicit TempScopInfo() : RegionPass(ID), TempScopOfRegion(nullptr) {}
   ~TempScopInfo();
 
-  /// @brief Get the temporay Scop information in LLVM IR represent
-  ///        for Region R.
+  /// @brief Get the temporay Scop information in LLVM IR for this region.
   ///
   /// @return The Scop information in LLVM IR represent.
-  TempScop *getTempScop(const Region *R) const;
+  TempScop *getTempScop() const;
 
-  /// @name FunctionPass interface
+  /// @name RegionPass interface
   //@{
   virtual void getAnalysisUsage(AnalysisUsage &AU) const;
   virtual void releaseMemory() { clear(); }
-  virtual bool runOnFunction(Function &F);
+  virtual bool runOnRegion(Region *R, RGPassManager &RGM);
   virtual void print(raw_ostream &OS, const Module *) const;
   //@}
 };
 
 } // end namespace polly
 
 namespace llvm {
 class PassRegistry;
 void initializeTempScopInfoPass(llvm::PassRegistry &);
 }
 
 #endif

lib/Analysis/ScopInfo.cpp

 }
 
 bool ScopInfo::runOnRegion(Region *R, RGPassManager &RGM) {
   LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
   AliasAnalysis &AA = getAnalysis<AliasAnalysis>();
   ScopDetection &SD = getAnalysis<ScopDetection>();
   ScalarEvolution &SE = getAnalysis<ScalarEvolution>();
 
-  TempScop *tempScop = getAnalysis<TempScopInfo>().getTempScop(R);
+  TempScop *tempScop = getAnalysis<TempScopInfo>().getTempScop();
 
   // This region is no Scop.
   if (!tempScop) {
     scop = nullptr;
     return false;
   }
 
   scop = Scop::createFromTempScop(*tempScop, LI, SE, SD, ctx);

lib/Analysis/TempScopInfo.cpp

TempScop *TempScopInfo::buildTempScop(Region &R) {
   buildAccessFunctions(R, R);
 
   for (const auto &BB : R.blocks())
     buildCondition(BB, R);
 
   return TScop;
 }
 
-TempScop *TempScopInfo::getTempScop(const Region *R) const {
-  TempScopMapType::const_iterator at = TempScops.find(R);
-  return at == TempScops.end() ? 0 : at->second;
-}
+TempScop *TempScopInfo::getTempScop() const { return TempScopOfRegion; }
 
 void TempScopInfo::print(raw_ostream &OS, const Module *) const {
-  for (TempScopMapType::const_iterator I = TempScops.begin(),
-                                       E = TempScops.end();
-       I != E; ++I)
-    I->second->print(OS, SE, LI);
+  if (TempScopOfRegion)
+    TempScopOfRegion->print(OS, SE, LI);
 }
 
-bool TempScopInfo::runOnFunction(Function &F) {
+bool TempScopInfo::runOnRegion(Region *R, RGPassManager &RGM) {
+  SD = &getAnalysis<ScopDetection>();
+
+  if (!SD->isMaxRegionInScop(*R))
+    return false;
+
+  Function *F = R->getEntry()->getParent();
   DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
   PDT = &getAnalysis<PostDominatorTree>();
   SE = &getAnalysis<ScalarEvolution>();
   LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
-  SD = &getAnalysis<ScopDetection>();
   AA = &getAnalysis<AliasAnalysis>();
-  TD = &F.getParent()->getDataLayout();
-  ZeroOffset = SE->getConstant(TD->getIntPtrType(F.getContext()), 0);
+  TD = &F->getParent()->getDataLayout();
+  ZeroOffset = SE->getConstant(TD->getIntPtrType(F->getContext()), 0);
 
-  for (ScopDetection::iterator I = SD->begin(), E = SD->end(); I != E; ++I) {
-    if (!SD->isMaxRegionInScop(**I))
-      continue;
-    Region *R = const_cast<Region *>(*I);
-    TempScops.insert(std::make_pair(R, buildTempScop(*R)));
-  }
+  assert(!TempScopOfRegion && "Build the TempScop only once");
+  TempScopOfRegion = buildTempScop(*R);
 
   return false;
 }
 
 void TempScopInfo::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.addRequiredTransitive<DominatorTreeWrapperPass>();
   AU.addRequiredTransitive<PostDominatorTree>();
   AU.addRequiredTransitive<LoopInfoWrapperPass>();
   AU.addRequiredTransitive<ScalarEvolution>();
   AU.addRequiredTransitive<ScopDetection>();
   AU.addRequiredID(IndependentBlocksID);
   AU.addRequired<AliasAnalysis>();
   AU.setPreservesAll();
 }
 
 TempScopInfo::~TempScopInfo() { clear(); }
 
 void TempScopInfo::clear() {
   BBConds.clear();
   AccFuncMap.clear();
-  DeleteContainerSeconds(TempScops);
-  TempScops.clear();
+  if (TempScopOfRegion)
+    delete TempScopOfRegion;
+  TempScopOfRegion = nullptr;
 }
 
 //===----------------------------------------------------------------------===//
 // TempScop information extraction pass implement
 char TempScopInfo::ID = 0;
 
 Pass *polly::createTempScopInfoPass() { return new TempScopInfo(); }
 

lib/CodeGen/CodeGeneration.cpp

 #include "polly/DependenceInfo.h"
 #include "polly/LinkAllPasses.h"
 #include "polly/ScopInfo.h"
 #include "polly/Support/ScopHelper.h"
 #include "polly/TempScopInfo.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/Verifier.h"
 #include "llvm/Support/Debug.h"
+#include "llvm/Analysis/PostDominators.h"
 
 using namespace polly;
 using namespace llvm;
 
 #define DEBUG_TYPE "polly-codegen"
 
 namespace {
 class CodeGeneration : public ScopPass {
void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.addRequired<ScopDetection>();
     AU.addRequired<ScopInfo>();
     AU.addRequired<LoopInfoWrapperPass>();
 
     AU.addPreserved<DependenceInfo>();
 
     AU.addPreserved<LoopInfoWrapperPass>();
     AU.addPreserved<DominatorTreeWrapperPass>();
+    AU.addPreserved<PostDominatorTree>();
     AU.addPreserved<IslAstInfo>();
     AU.addPreserved<ScopDetection>();
     AU.addPreserved<ScalarEvolution>();
 
     // FIXME: We do not yet add regions for the newly generated code to the
     //        region tree.
     AU.addPreserved<RegionInfoPass>();
     AU.addPreserved<TempScopInfo>();