[GSoC 2016][Polly][Refactor] Decouple SCoP building logic from pass

[cs14mtech11017]

Summary

Decoupled SCoP creation and pass logic.

1. Created a new pass ScopInfoRegionPass. As name suggests, it is a region pass and it is there to preserve compatibility with our existing Polly passes.
2. ScopInfoRegionPass will return ScopInfo object, which actually builds the SCoP object.

[jdoerfert]

I added some comments and change requests. Additionally, could you use "arc diff" to create a revision or alternatively add "-U99999" to the "diff" options such that we get context between the chunks that were changes? Thanks!

include/polly/ScopInfo.h

2478 ↗

(On Diff #58888)

I wondered why this method takes arguments already passed to the constructor and I needed to check the code. Two things:

1. Please add a field for the AssumptionCache reference.
2. The createScopInfo() function should be either: a) private and called "initialize" or "init" b) inlined into the constructor

2482 ↗

(On Diff #58888)

Remove the virtual please.

2498 ↗

(On Diff #58888)

I don't know why you need a unique_ptr here but I don't care to much about it.

2510 ↗

(On Diff #58888)

I would not return a reference here because there is no way to know that SI is actually not null. Please return the SI pointer.

lib/Analysis/ScopInfo.cpp

4869 ↗

(On Diff #58888)

can you move this check to the runOnRegion method below?

lib/Analysis/ScopPass.cpp

23 ↗

(On Diff #58888)

I would change the interface such that getScopInfo might return a nullptr. At the moment I don't care if ScopInfo.getScop() returns a pointer or a reference but the latter might be possible.

[cs14mtech11017]

• Decouple Scop building logic from pass logic
• Removed createScopInfo function and inlined code into ScopInfo constructor.

[cs14mtech11017]

I have done the changes you requested. Have arc for the new patch.

include/polly/ScopInfo.h

2476–2478 ↗

(On Diff #58888)

Ok, removed this function and inlined code into the constructor.

2482 ↗

(On Diff #58888)

Removed. thanks for pointing that out.

2498 ↗

(On Diff #58888)

As this is an analysis pass, I think it is better for memory management. Don't have to track all the pointer uses.

2510 ↗

(On Diff #58888)

Ok. After making the change at 4896, this makes sense.

lib/Analysis/ScopInfo.cpp

4869 ↗

(On Diff #58888)

Done. Also removed this function and inlined code into constructor.

[jdoerfert]

The missing print will fix the last unit test. Other than that LGTM. Tobias announced comments, thus let's wait for him.

lib/Analysis/ScopInfo.cpp

4920 ↗

(On Diff #58943)

else
  OS << "Invalid Scop!\n";

[grosser]

Hi Utpal,

thank you for looking into this! As Johannes said, the patch looks generally good. I mostly have minor comments.

Also, I would suggest to look after this commit into the memory management of ScopInfo/ScopBuilder. It seems unnecessary to keep it around after the scop was constructed just to keep a pointer to the scop. I would prefer to just have it return the scop object and (or a unique_ptr to it) and not keep any state after the scop has been constructed.

Best,
Tobias

include/polly/ScopInfo.h

2250 ↗

(On Diff #58943)

Would it make sense to call this ScopBuilder? This seems more descriptive.

You can probably do this in a follow-up commit.

2476 ↗

(On Diff #58943)

The releaseMemory method does not seem to be needed any more, no?

2478 ↗

(On Diff #58943)

Why is a print method needed here? We could just get the scop and print it directly, no?

lib/Analysis/ScopPass.cpp

23 ↗

(On Diff #58943)

Johannes, I do not understand this comment/change? Why do we need to expose ScopInfo/ScopBuilder? Either getScop() returns a scop or a nullptr? That seems all the functionality we need, right?

[jdoerfert]

In D20770#443542, @grosser wrote:

Also, I would suggest to look after this commit into the memory management of ScopInfo/ScopBuilder. It seems unnecessary to keep it around after the scop was constructed just to keep a pointer to the scop. I would prefer to just have it return the scop object and (or a unique_ptr to it) and not keep any state after the scop has been constructed.

We can do that now or afterwards but it sounds like a good idea.

lib/Analysis/ScopPass.cpp

23 ↗

(On Diff #58943)

Ok, fair enough. We can get rid of the indirection completely (same argument as I used to justify the reference return argument for ScopInfo.getScop(), once a ScopInfo/ScopBuilder is created there should always be a Scop).

@Utpal, can you please replace ScopInfoRegionPass::getScopInfo with a ScopInfoRegionPasS::getScop function?

[cs14mtech11017]

include/polly/ScopInfo.h

2250 ↗

(On Diff #58943)

I was in the intuition of making least possible changes to the existing code base.
Please suggest changes that you feel will be better in general.

If I am not wrong, we do not need to change the files names of ScopInfo.h and ScopInfo.cpp right? Changing only class name is makes sense.

[grosser]

cs14mtech11017 added inline comments.

Comment at: include/polly/ScopInfo.h:2250
@@ -2249,3 +2249,3 @@
/// @brief Build the Polly IR (Scop and ScopStmt) on a Region.
-class ScopInfo : public RegionPass {

//===-------------------------------------------------------------------===//

---

grosser wrote:

Would it make sense to call this ScopBuilder? This seems more descriptive.

You can probably do this in a follow-up commit.

I was in the intuition of making least possible changes to the existing code base.
Please suggest changes that you feel will be better in general.

Yes. As this renaming is purely mechanical it is probably better to do
it in a subsequent change.

If I am not wrong, we do not need to change the files names of ScopInfo.h and ScopInfo.cpp right? Changing only class name is makes sense.

No. I don't think we need to.

Best,
Tobias

[cs14mtech11017]

• Removed releaseMemory and print functions from ScopInfo class as they are not required any more.

[cs14mtech11017]

Hello Tobias,

Most of the changes you suggested are done. Removed releaseMemory and print functions, removed exposing ScopInfo object and now returning just the scop object.
I will push class renaming change from ScopInfo to ScopBuilder and memory management changes in a separate patch.

[grosser]

LGTM.

polly/trunk/include/polly/LinkAllPasses.h

 llvm::Pass *createDOTOnlyPrinterPass();
 llvm::Pass *createDOTOnlyViewerPass();
 llvm::Pass *createDOTPrinterPass();
 llvm::Pass *createDOTViewerPass();
 llvm::Pass *createJSONExporterPass();
 llvm::Pass *createJSONImporterPass();
 llvm::Pass *createPollyCanonicalizePass();
 llvm::Pass *createScopDetectionPass();
-llvm::Pass *createScopInfoPass();
+llvm::Pass *createScopInfoRegionPassPass();
 llvm::Pass *createIslAstInfoPass();
 llvm::Pass *createCodeGenerationPass();
 llvm::Pass *createIslScheduleOptimizerPass();
 
 extern char &CodePreparationID;
 }
 
 namespace {
PollyForcePassLinking() {
     polly::createDependenceInfoPass();
     polly::createDOTOnlyPrinterPass();
     polly::createDOTOnlyViewerPass();
     polly::createDOTPrinterPass();
     polly::createDOTViewerPass();
     polly::createJSONExporterPass();
     polly::createJSONImporterPass();
     polly::createScopDetectionPass();
-    polly::createScopInfoPass();
+    polly::createScopInfoRegionPassPass();
     polly::createPollyCanonicalizePass();
     polly::createIslAstInfoPass();
     polly::createCodeGenerationPass();
     polly::createIslScheduleOptimizerPass();
   }
 } PollyForcePassLinking; // Force link by creating a global definition.
 }
 

polly/trunk/include/polly/ScopInfo.h

 
 /// @brief Print Scop scop to raw_ostream O.
 static inline raw_ostream &operator<<(raw_ostream &O, const Scop &scop) {
   scop.print(O);
   return O;
 }
 
 /// @brief Build the Polly IR (Scop and ScopStmt) on a Region.
-class ScopInfo : public RegionPass {
+class ScopInfo {
   //===-------------------------------------------------------------------===//
   ScopInfo(const ScopInfo &) = delete;
   const ScopInfo &operator=(const ScopInfo &) = delete;
 
   /// @brief The AliasAnalysis to build AliasSetTracker.
-  AliasAnalysis *AA;
+  AliasAnalysis &AA;
 
   /// @brief Target data for element size computing.
-  const DataLayout *DL;
+  const DataLayout &DL;
 
   /// @brief DominatorTree to reason about guaranteed execution.
-  DominatorTree *DT;
+  DominatorTree &DT;
 
   /// @brief LoopInfo for information about loops
-  LoopInfo *LI;
+  LoopInfo &LI;
 
   /// @biref Valid Regions for Scop
-  ScopDetection *SD;
+  ScopDetection &SD;
 
   /// @brief The ScalarEvolution to help building Scop.
-  ScalarEvolution *SE;
+  ScalarEvolution &SE;
 
   /// @brief Set of instructions that might read any memory location.
   SmallVector<Instruction *, 16> GlobalReads;
 
   /// @brief Set of all accessed array base pointers.
   SmallSetVector<Value *, 16> ArrayBasePointers;
 
   // The Scop
class ScopInfo {
   /// @param PHI PHINode under consideration; the READ access will be added
   /// here.
   ///
   /// @see ensurePHIWrite()
   /// @see ScopArrayInfo::MemoryKind
   void addPHIReadAccess(PHINode *PHI);
 
 public:
-  static char ID;
-  explicit ScopInfo();
-  ~ScopInfo();
+  explicit ScopInfo(Region *R, AssumptionCache &AC, AliasAnalysis &AA,
+                    const DataLayout &DL, DominatorTree &DT, LoopInfo &LI,
+                    ScopDetection &SD, ScalarEvolution &SE);
+  ~ScopInfo() {}
 
   /// @brief Try to build the Polly IR of static control part on the current
   ///        SESE-Region.
   ///
   /// @return If the current region is a valid for a static control part,
   ///         return the Polly IR representing this static control part,
   ///         return null otherwise.
   Scop *getScop() { return scop.get(); }
   const Scop *getScop() const { return scop.get(); }
+};
 
-  /// @name RegionPass interface
-  //@{
-  virtual bool runOnRegion(Region *R, RGPassManager &RGM);
-  virtual void getAnalysisUsage(AnalysisUsage &AU) const;
-  virtual void releaseMemory() { clear(); }
-  virtual void print(raw_ostream &OS, const Module *) const;
-  //@}
+/// @brief The legacy pass manager's analysis pass to compute scop information
+///        for a region.
+class ScopInfoRegionPass : public RegionPass {
+  /// @brief The ScopInfo pointer which is used to construct a Scop.
+  std::unique_ptr<ScopInfo> SI;
+
+public:
+  static char ID; // Pass identification, replacement for typeid
+
+  ScopInfoRegionPass() : RegionPass(ID) {}
+  ~ScopInfoRegionPass() {}
+
+  /// @brief Build ScopInfo object, which constructs Polly IR of static control
+  ///        part for the current SESE-Region.
+  ///
+  /// @return Return Scop for the current Region.
+  Scop *getScop() {
+    if (SI)
+      return SI.get()->getScop();
+    else
+      return nullptr;
+  }
+  const Scop *getScop() const {
+    if (SI)
+      return SI.get()->getScop();
+    else
+      return nullptr;
+  }
+
+  /// @brief Calculate the polyhedral scop information for a given Region.
+  bool runOnRegion(Region *R, RGPassManager &RGM) override;
+
+  void releaseMemory() override { SI.reset(); }
+
+  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 initializeScopInfoPass(llvm::PassRegistry &);
+void initializeScopInfoRegionPassPass(llvm::PassRegistry &);
 }
 
 #endif

polly/trunk/lib/Analysis/DependenceInfo.cpp

void polly::DependenceInfo::printScop(raw_ostream &OS, Scop &S) const {
 
   // Otherwise create the dependences on-the-fly and print it
   Dependences D(S.getSharedIslCtx(), OptAnalysisLevel);
   D.calculateDependences(S);
   D.print(OS);
 }
 
 void DependenceInfo::getAnalysisUsage(AnalysisUsage &AU) const {
-  AU.addRequiredTransitive<ScopInfo>();
+  AU.addRequiredTransitive<ScopInfoRegionPass>();
   AU.setPreservesAll();
 }
 
 char DependenceInfo::ID = 0;
 
 Pass *polly::createDependenceInfoPass() { return new DependenceInfo(); }
 
 INITIALIZE_PASS_BEGIN(DependenceInfo, "polly-dependences",
                       "Polly - Calculate dependences", false, false);
-INITIALIZE_PASS_DEPENDENCY(ScopInfo);
+INITIALIZE_PASS_DEPENDENCY(ScopInfoRegionPass);
 INITIALIZE_PASS_END(DependenceInfo, "polly-dependences",
                     "Polly - Calculate dependences", false, false)

polly/trunk/lib/Analysis/ScopInfo.cpp

void ScopInfo::buildPHIAccesses(PHINode *PHI, Region *NonAffineSubRegion,
   // PHI nodes that are in the exit block of the region, hence if IsExitBlock is
   // true, are not modeled as ordinary PHI nodes as they are not part of the
   // region. However, we model the operands in the predecessor blocks that are
   // part of the region as regular scalar accesses.
 
   // If we can synthesize a PHI we can skip it, however only if it is in
   // the region. If it is not it can only be in the exit block of the region.
   // In this case we model the operands but not the PHI itself.
-  auto *Scope = LI->getLoopFor(PHI->getParent());
-  if (!IsExitBlock && canSynthesize(PHI, *scop, LI, SE, Scope))
+  auto *Scope = LI.getLoopFor(PHI->getParent());
+  if (!IsExitBlock && canSynthesize(PHI, *scop, &LI, &SE, Scope))
     return;
 
   // PHI nodes are modeled as if they had been demoted prior to the SCoP
   // detection. Hence, the PHI is a load of a new memory location in which the
   // incoming value was written at the end of the incoming basic block.
   bool OnlyNonAffineSubRegionOperands = true;
   for (unsigned u = 0; u < PHI->getNumIncomingValues(); u++) {
     Value *Op = PHI->getIncomingValue(u);
for (Use &U : Inst->uses()) {
     }
   }
 }
 
 bool ScopInfo::buildAccessMultiDimFixed(MemAccInst Inst, Loop *L) {
   Value *Val = Inst.getValueOperand();
   Type *ElementType = Val->getType();
   Value *Address = Inst.getPointerOperand();
-  const SCEV *AccessFunction = SE->getSCEVAtScope(Address, L);
+  const SCEV *AccessFunction = SE.getSCEVAtScope(Address, L);
   const SCEVUnknown *BasePointer =
-      dyn_cast<SCEVUnknown>(SE->getPointerBase(AccessFunction));
+      dyn_cast<SCEVUnknown>(SE.getPointerBase(AccessFunction));
   enum MemoryAccess::AccessType AccType =
       isa<LoadInst>(Inst) ? MemoryAccess::READ : MemoryAccess::MUST_WRITE;
 
   if (auto *BitCast = dyn_cast<BitCastInst>(Address)) {
     auto *Src = BitCast->getOperand(0);
     auto *SrcTy = Src->getType();
     auto *DstTy = BitCast->getType();
     // Do not try to delinearize non-sized (opaque) pointers.
     if ((SrcTy->isPointerTy() && !SrcTy->getPointerElementType()->isSized()) ||
         (DstTy->isPointerTy() && !DstTy->getPointerElementType()->isSized())) {
       return false;
     }
     if (SrcTy->isPointerTy() && DstTy->isPointerTy() &&
-        DL->getTypeAllocSize(SrcTy->getPointerElementType()) ==
-            DL->getTypeAllocSize(DstTy->getPointerElementType()))
+        DL.getTypeAllocSize(SrcTy->getPointerElementType()) ==
+            DL.getTypeAllocSize(DstTy->getPointerElementType()))
       Address = Src;
   }
 
   auto *GEP = dyn_cast<GetElementPtrInst>(Address);
   if (!GEP)
     return false;
 
   std::vector<const SCEV *> Subscripts;
   std::vector<int> Sizes;
-  std::tie(Subscripts, Sizes) = getIndexExpressionsFromGEP(GEP, *SE);
+  std::tie(Subscripts, Sizes) = getIndexExpressionsFromGEP(GEP, SE);
   auto *BasePtr = GEP->getOperand(0);
 
   if (auto *BasePtrCast = dyn_cast<BitCastInst>(BasePtr))
     BasePtr = BasePtrCast->getOperand(0);
 
   // Check for identical base pointers to ensure that we do not miss index
   // offsets that have been added before this GEP is applied.
   if (BasePtr != BasePointer->getValue())
     return false;
 
   std::vector<const SCEV *> SizesSCEV;
 
   const InvariantLoadsSetTy &ScopRIL = scop->getRequiredInvariantLoads();
   for (auto *Subscript : Subscripts) {
     InvariantLoadsSetTy AccessILS;
-    if (!isAffineExpr(&scop->getRegion(), L, Subscript, *SE, &AccessILS))
+    if (!isAffineExpr(&scop->getRegion(), L, Subscript, SE, &AccessILS))
       return false;
 
     for (LoadInst *LInst : AccessILS)
       if (!ScopRIL.count(LInst))
         return false;
   }
 
   if (Sizes.empty())
     return false;
 
   for (auto V : Sizes)
-    SizesSCEV.push_back(SE->getSCEV(
+    SizesSCEV.push_back(SE.getSCEV(
         ConstantInt::get(IntegerType::getInt64Ty(BasePtr->getContext()), V)));
 
   addArrayAccess(Inst, AccType, BasePointer->getValue(), ElementType, true,
                  Subscripts, SizesSCEV, Val);
   return true;
 }
 
 bool ScopInfo::buildAccessMultiDimParam(MemAccInst Inst, Loop *L) {
   if (!PollyDelinearize)
     return false;
 
   Value *Address = Inst.getPointerOperand();
   Value *Val = Inst.getValueOperand();
   Type *ElementType = Val->getType();
-  unsigned ElementSize = DL->getTypeAllocSize(ElementType);
+  unsigned ElementSize = DL.getTypeAllocSize(ElementType);
   enum MemoryAccess::AccessType AccType =
       isa<LoadInst>(Inst) ? MemoryAccess::READ : MemoryAccess::MUST_WRITE;
 
-  const SCEV *AccessFunction = SE->getSCEVAtScope(Address, L);
+  const SCEV *AccessFunction = SE.getSCEVAtScope(Address, L);
   const SCEVUnknown *BasePointer =
-      dyn_cast<SCEVUnknown>(SE->getPointerBase(AccessFunction));
+      dyn_cast<SCEVUnknown>(SE.getPointerBase(AccessFunction));
 
   assert(BasePointer && "Could not find base pointer");
 
   auto &InsnToMemAcc = scop->getInsnToMemAccMap();
   auto AccItr = InsnToMemAcc.find(Inst);
   if (AccItr == InsnToMemAcc.end())
     return false;
 

 }
 
 bool ScopInfo::buildAccessMemIntrinsic(MemAccInst Inst, Loop *L) {
   auto *MemIntr = dyn_cast_or_null<MemIntrinsic>(Inst);
 
   if (MemIntr == nullptr)
     return false;
 
-  auto *LengthVal = SE->getSCEVAtScope(MemIntr->getLength(), L);
+  auto *LengthVal = SE.getSCEVAtScope(MemIntr->getLength(), L);
   assert(LengthVal);
 
   // Check if the length val is actually affine or if we overapproximate it
   InvariantLoadsSetTy AccessILS;
   const InvariantLoadsSetTy &ScopRIL = scop->getRequiredInvariantLoads();
   bool LengthIsAffine =
-      isAffineExpr(&scop->getRegion(), L, LengthVal, *SE, &AccessILS);
+      isAffineExpr(&scop->getRegion(), L, LengthVal, SE, &AccessILS);
   for (LoadInst *LInst : AccessILS)
     if (!ScopRIL.count(LInst))
       LengthIsAffine = false;
   if (!LengthIsAffine)
     LengthVal = nullptr;
 
   auto *DestPtrVal = MemIntr->getDest();
   assert(DestPtrVal);
 
-  auto *DestAccFunc = SE->getSCEVAtScope(DestPtrVal, L);
+  auto *DestAccFunc = SE.getSCEVAtScope(DestPtrVal, L);
   assert(DestAccFunc);
   // Ignore accesses to "NULL".
   // TODO: We could use this to optimize the region further, e.g., intersect
   //       the context with
   //          isl_set_complement(isl_set_params(getDomain()))
   //       as we know it would be undefined to execute this instruction anyway.
   if (DestAccFunc->isZero())
     return true;
 
-  auto *DestPtrSCEV = dyn_cast<SCEVUnknown>(SE->getPointerBase(DestAccFunc));
+  auto *DestPtrSCEV = dyn_cast<SCEVUnknown>(SE.getPointerBase(DestAccFunc));
   assert(DestPtrSCEV);
-  DestAccFunc = SE->getMinusSCEV(DestAccFunc, DestPtrSCEV);
+  DestAccFunc = SE.getMinusSCEV(DestAccFunc, DestPtrSCEV);
   addArrayAccess(Inst, MemoryAccess::MUST_WRITE, DestPtrSCEV->getValue(),
                  IntegerType::getInt8Ty(DestPtrVal->getContext()), false,
                  {DestAccFunc, LengthVal}, {}, Inst.getValueOperand());
 
   auto *MemTrans = dyn_cast<MemTransferInst>(MemIntr);
   if (!MemTrans)
     return true;
 
   auto *SrcPtrVal = MemTrans->getSource();
   assert(SrcPtrVal);
 
-  auto *SrcAccFunc = SE->getSCEVAtScope(SrcPtrVal, L);
+  auto *SrcAccFunc = SE.getSCEVAtScope(SrcPtrVal, L);
   assert(SrcAccFunc);
   // Ignore accesses to "NULL".
   // TODO: See above TODO
   if (SrcAccFunc->isZero())
     return true;
 
-  auto *SrcPtrSCEV = dyn_cast<SCEVUnknown>(SE->getPointerBase(SrcAccFunc));
+  auto *SrcPtrSCEV = dyn_cast<SCEVUnknown>(SE.getPointerBase(SrcAccFunc));
   assert(SrcPtrSCEV);
-  SrcAccFunc = SE->getMinusSCEV(SrcAccFunc, SrcPtrSCEV);
+  SrcAccFunc = SE.getMinusSCEV(SrcAccFunc, SrcPtrSCEV);
   addArrayAccess(Inst, MemoryAccess::READ, SrcPtrSCEV->getValue(),
                  IntegerType::getInt8Ty(SrcPtrVal->getContext()), false,
                  {SrcAccFunc, LengthVal}, {}, Inst.getValueOperand());
 
   return true;
 }
 
 bool ScopInfo::buildAccessCallInst(MemAccInst Inst, Loop *L) {
   auto *CI = dyn_cast_or_null<CallInst>(Inst);
 
   if (CI == nullptr)
     return false;
 
   if (CI->doesNotAccessMemory() || isIgnoredIntrinsic(CI))
     return true;
 
   bool ReadOnly = false;
-  auto *AF = SE->getConstant(IntegerType::getInt64Ty(CI->getContext()), 0);
+  auto *AF = SE.getConstant(IntegerType::getInt64Ty(CI->getContext()), 0);
   auto *CalledFunction = CI->getCalledFunction();
-  switch (AA->getModRefBehavior(CalledFunction)) {
+  switch (AA.getModRefBehavior(CalledFunction)) {
   case llvm::FMRB_UnknownModRefBehavior:
     llvm_unreachable("Unknown mod ref behaviour cannot be represented.");
   case llvm::FMRB_DoesNotAccessMemory:
     return true;
   case llvm::FMRB_OnlyReadsMemory:
     GlobalReads.push_back(CI);
     return true;
   case llvm::FMRB_OnlyReadsArgumentPointees:
     ReadOnly = true;
   // Fall through
   case llvm::FMRB_OnlyAccessesArgumentPointees:
     auto AccType = ReadOnly ? MemoryAccess::READ : MemoryAccess::MAY_WRITE;
     for (const auto &Arg : CI->arg_operands()) {
       if (!Arg->getType()->isPointerTy())
         continue;
 
-      auto *ArgSCEV = SE->getSCEVAtScope(Arg, L);
+      auto *ArgSCEV = SE.getSCEVAtScope(Arg, L);
       if (ArgSCEV->isZero())
         continue;
 
-      auto *ArgBasePtr = cast<SCEVUnknown>(SE->getPointerBase(ArgSCEV));
+      auto *ArgBasePtr = cast<SCEVUnknown>(SE.getPointerBase(ArgSCEV));
       addArrayAccess(Inst, AccType, ArgBasePtr->getValue(),
                      ArgBasePtr->getType(), false, {AF}, {}, CI);
     }
     return true;
   }
 
   return true;
 }
 
 void ScopInfo::buildAccessSingleDim(MemAccInst Inst, Loop *L) {
   Value *Address = Inst.getPointerOperand();
   Value *Val = Inst.getValueOperand();
   Type *ElementType = Val->getType();
   enum MemoryAccess::AccessType AccType =
       isa<LoadInst>(Inst) ? MemoryAccess::READ : MemoryAccess::MUST_WRITE;
 
-  const SCEV *AccessFunction = SE->getSCEVAtScope(Address, L);
+  const SCEV *AccessFunction = SE.getSCEVAtScope(Address, L);
   const SCEVUnknown *BasePointer =
-      dyn_cast<SCEVUnknown>(SE->getPointerBase(AccessFunction));
+      dyn_cast<SCEVUnknown>(SE.getPointerBase(AccessFunction));
 
   assert(BasePointer && "Could not find base pointer");
-  AccessFunction = SE->getMinusSCEV(AccessFunction, BasePointer);
+  AccessFunction = SE.getMinusSCEV(AccessFunction, BasePointer);
 
   // Check if the access depends on a loop contained in a non-affine subregion.
   bool isVariantInNonAffineLoop = false;
   SetVector<const Loop *> Loops;
   auto &BoxedLoops = scop->getBoxedLoops();
   findLoops(AccessFunction, Loops);
   for (const Loop *L : Loops)
     if (BoxedLoops.count(L))
       isVariantInNonAffineLoop = true;
 
   InvariantLoadsSetTy AccessILS;
   bool IsAffine =
       !isVariantInNonAffineLoop &&
-      isAffineExpr(&scop->getRegion(), L, AccessFunction, *SE, &AccessILS);
+      isAffineExpr(&scop->getRegion(), L, AccessFunction, SE, &AccessILS);
 
   const InvariantLoadsSetTy &ScopRIL = scop->getRequiredInvariantLoads();
   for (LoadInst *LInst : AccessILS)
     if (!ScopRIL.count(LInst))
       IsAffine = false;
 
   if (!IsAffine && AccType == MemoryAccess::MUST_WRITE)
     AccType = MemoryAccess::MAY_WRITE;
for (auto I = SR.element_begin(), E = SR.element_end(); I != E; ++I)
     else
       scop->addScopStmt(I->getNodeAs<BasicBlock>(), nullptr);
 }
 
 void ScopInfo::buildAccessFunctions(BasicBlock &BB, Region *NonAffineSubRegion,
                                     bool IsExitBlock) {
   // We do not build access functions for error blocks, as they may contain
   // instructions we can not model.
-  if (isErrorBlock(BB, scop->getRegion(), *LI, *DT) && !IsExitBlock)
+  if (isErrorBlock(BB, scop->getRegion(), LI, DT) && !IsExitBlock)
     return;
 
-  Loop *L = LI->getLoopFor(&BB);
+  Loop *L = LI.getLoopFor(&BB);
 
   for (Instruction &Inst : BB) {
     PHINode *PHI = dyn_cast<PHINode>(&Inst);
     if (PHI)
       buildPHIAccesses(PHI, NonAffineSubRegion, IsExitBlock);
 
     // For the exit block we stop modeling after the last PHI node.
     if (!PHI && IsExitBlock)
MemoryAccess *ScopInfo::addMemoryAccess(BasicBlock *BB, Instruction *Inst,
   if (Stmt->isBlockStmt())
     isKnownMustAccess = true;
 
   if (Stmt->isRegionStmt()) {
     // Accesses that dominate the exit block of a non-affine region are always
     // executed. In non-affine regions there may exist MK_Values that do not
     // dominate the exit. MK_Values will always dominate the exit and MK_PHIs
     // only if there is at most one PHI_WRITE in the non-affine region.
-    if (DT->dominates(BB, Stmt->getRegion()->getExit()))
+    if (DT.dominates(BB, Stmt->getRegion()->getExit()))
       isKnownMustAccess = true;
   }
 
   // Non-affine PHI writes do not "happen" at a particular instruction, but
   // after exiting the statement. Therefore they are guaranteed execute and
   // overwrite the old value.
   if (Kind == ScopArrayInfo::MK_PHI || Kind == ScopArrayInfo::MK_ExitPHI)
     isKnownMustAccess = true;
void ScopInfo::ensureValueRead(Value *V, BasicBlock *UserBB) {
 
   // There cannot be an "access" for literal constants. BasicBlock references
   // (jump destinations) also never change.
   if ((isa<Constant>(V) && !isa<GlobalVariable>(V)) || isa<BasicBlock>(V))
     return;
 
   // If the instruction can be synthesized and the user is in the region we do
   // not need to add a value dependences.
-  auto *Scope = LI->getLoopFor(UserBB);
-  if (canSynthesize(V, *scop, LI, SE, Scope))
+  auto *Scope = LI.getLoopFor(UserBB);
+  if (canSynthesize(V, *scop, &LI, &SE, Scope))
     return;
 
   // Do not build scalar dependences for required invariant loads as we will
   // hoist them later on anyway or drop the SCoP if we cannot.
   auto &ScopRIL = scop->getRequiredInvariantLoads();
   if (ScopRIL.count(dyn_cast<LoadInst>(V)))
     return;
 

 
 void ScopInfo::addPHIReadAccess(PHINode *PHI) {
   addMemoryAccess(PHI->getParent(), PHI, MemoryAccess::READ, PHI,
                   PHI->getType(), true, PHI, ArrayRef<const SCEV *>(),
                   ArrayRef<const SCEV *>(), ScopArrayInfo::MK_PHI);
 }
 
 void ScopInfo::buildScop(Region &R, AssumptionCache &AC) {
-  scop.reset(new Scop(R, *SE, *LI, *SD->getDetectionContext(&R)));
+  scop.reset(new Scop(R, SE, LI, *SD.getDetectionContext(&R)));
 
   buildStmts(R);
   buildAccessFunctions(R);
 
   // In case the region does not have an exiting block we will later (during
   // code generation) split the exit block. This will move potential PHI nodes
   // from the current exit block into the new region exiting block. Hence, PHI
   // nodes that are at this point not part of the region will be.
   // To handle these PHI nodes later we will now model their operands as scalar
   // accesses. Note that we do not model anything in the exit block if we have
   // an exiting block in the region, as there will not be any splitting later.
   if (!scop->hasSingleExitEdge())
     buildAccessFunctions(*R.getExit(), nullptr,
                          /* IsExitBlock */ true);
 
   // Create memory accesses for global reads since all arrays are now known.
-  auto *AF = SE->getConstant(IntegerType::getInt64Ty(SE->getContext()), 0);
+  auto *AF = SE.getConstant(IntegerType::getInt64Ty(SE.getContext()), 0);
   for (auto *GlobalRead : GlobalReads)
     for (auto *BP : ArrayBasePointers)
       addArrayAccess(MemAccInst(GlobalRead), MemoryAccess::READ, BP,
                      BP->getType(), false, {AF}, {}, GlobalRead);
 
-  scop->init(*AA, AC, *DT, *LI);
-}
-
-void ScopInfo::print(raw_ostream &OS, const Module *) const {
-  if (!scop) {
-    OS << "Invalid Scop!\n";
-    return;
-  }
-
-  scop->print(OS);
+  scop->init(AA, AC, DT, LI);
 }
 
-void ScopInfo::clear() { scop.reset(); }
-
-//===----------------------------------------------------------------------===//
-ScopInfo::ScopInfo() : RegionPass(ID) {}
-
-ScopInfo::~ScopInfo() { clear(); }
-
-void ScopInfo::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 ScopInfo::runOnRegion(Region *R, RGPassManager &RGM) {
-  SD = &getAnalysis<ScopDetection>();
-
-  if (!SD->isMaxRegionInScop(*R))
-    return false;
+ScopInfo::ScopInfo(Region *R, AssumptionCache &AC, AliasAnalysis &AA,
+                   const DataLayout &DL, DominatorTree &DT, LoopInfo &LI,
+                   ScopDetection &SD, ScalarEvolution &SE)
+    : AA(AA), DL(DL), DT(DT), LI(LI), SD(SD), SE(SE) {
 
   Function *F = R->getEntry()->getParent();
-  SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
-  LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
-  AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
-  DL = &F->getParent()->getDataLayout();
-  DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
-  auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(*F);
 
   DebugLoc Beg, End;
   getDebugLocations(getBBPairForRegion(R), Beg, End);
   std::string Msg = "SCoP begins here.";
   emitOptimizationRemarkAnalysis(F->getContext(), DEBUG_TYPE, *F, Beg, Msg);
 
   buildScop(*R, AC);
 
   DEBUG(scop->print(dbgs()));
 
   if (!scop->hasFeasibleRuntimeContext()) {
     Msg = "SCoP ends here but was dismissed.";
     scop.reset();
   } else {
     Msg = "SCoP ends here.";
     ++ScopFound;
     if (scop->getMaxLoopDepth() > 0)
       ++RichScopFound;
   }
 
   emitOptimizationRemarkAnalysis(F->getContext(), DEBUG_TYPE, *F, End, Msg);
+}
 
+void ScopInfo::clear() { scop.reset(); }
+
+//===----------------------------------------------------------------------===//
+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();
+}
+
+bool ScopInfoRegionPass::runOnRegion(Region *R, RGPassManager &RGM) {
+  auto &SD = getAnalysis<ScopDetection>();
+
+  if (!SD.isMaxRegionInScop(*R))
     return false;
+
+  Function *F = R->getEntry()->getParent();
+  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);
+
+  SI.reset(new ScopInfo(R, AC, AA, DL, DT, LI, SD, SE));
+  return false;
+}
+
+void ScopInfoRegionPass::print(raw_ostream &OS, const Module *) const {
+  Scop *scop;
+  if (SI) {
+    if ((scop = SI->getScop())) {
+      scop->print(OS);
+      return;
+    }
+  }
+  OS << "Invalid Scop!\n";
 }
 
-char ScopInfo::ID = 0;
+char ScopInfoRegionPass::ID = 0;
 
-Pass *polly::createScopInfoPass() { return new ScopInfo(); }
+Pass *polly::createScopInfoRegionPassPass() { return new ScopInfoRegionPass(); }
 
-INITIALIZE_PASS_BEGIN(ScopInfo, "polly-scops",
+INITIALIZE_PASS_BEGIN(ScopInfoRegionPass, "polly-scops",
                       "Polly - Create polyhedral description of Scops", 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(ScopInfo, "polly-scops",
+INITIALIZE_PASS_END(ScopInfoRegionPass, "polly-scops",
                     "Polly - Create polyhedral description of Scops", false,
                     false)

polly/trunk/lib/Analysis/ScopPass.cpp

 #include "polly/ScopInfo.h"
 
 using namespace llvm;
 using namespace polly;
 
 bool ScopPass::runOnRegion(Region *R, RGPassManager &RGM) {
   S = nullptr;
 
-  if ((S = getAnalysis<ScopInfo>().getScop()))
+  if ((S = getAnalysis<ScopInfoRegionPass>().getScop()))
     return runOnScop(*S);
 
   return false;
 }
 
 void ScopPass::print(raw_ostream &OS, const Module *M) const {
   if (S)
     printScop(OS, *S);
 }
 
 void ScopPass::getAnalysisUsage(AnalysisUsage &AU) const {
-  AU.addRequired<ScopInfo>();
+  AU.addRequired<ScopInfoRegionPass>();
   AU.setPreservesAll();
 }

polly/trunk/lib/CodeGen/CodeGeneration.cpp

public:
 
   /// @brief Register all analyses and transformation required.
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.addRequired<DominatorTreeWrapperPass>();
     AU.addRequired<IslAstInfo>();
     AU.addRequired<RegionInfoPass>();
     AU.addRequired<ScalarEvolutionWrapperPass>();
     AU.addRequired<ScopDetection>();
-    AU.addRequired<ScopInfo>();
+    AU.addRequired<ScopInfoRegionPass>();
     AU.addRequired<LoopInfoWrapperPass>();
 
     AU.addPreserved<DependenceInfo>();
 
     AU.addPreserved<AAResultsWrapperPass>();
     AU.addPreserved<BasicAAWrapperPass>();
     AU.addPreserved<LoopInfoWrapperPass>();
     AU.addPreserved<DominatorTreeWrapperPass>();
     AU.addPreserved<GlobalsAAWrapperPass>();
     AU.addPreserved<PostDominatorTreeWrapperPass>();
     AU.addPreserved<IslAstInfo>();
     AU.addPreserved<ScopDetection>();
     AU.addPreserved<ScalarEvolutionWrapperPass>();
     AU.addPreserved<SCEVAAWrapperPass>();
 
     // FIXME: We do not yet add regions for the newly generated code to the
     //        region tree.
     AU.addPreserved<RegionInfoPass>();
-    AU.addPreserved<ScopInfo>();
+    AU.addPreserved<ScopInfoRegionPass>();
   }
 };
 }
 
 char CodeGeneration::ID = 1;
 
 Pass *polly::createCodeGenerationPass() { return new CodeGeneration(); }
 

polly/trunk/lib/CodeGen/IslAst.cpp

void IslAstInfo::printScop(raw_ostream &OS, Scop &S) const {
   isl_union_map_free(Schedule);
   isl_ast_node_free(RootNode);
   isl_printer_free(P);
 }
 
 void IslAstInfo::getAnalysisUsage(AnalysisUsage &AU) const {
   // Get the Common analysis usage of ScopPasses.
   ScopPass::getAnalysisUsage(AU);
-  AU.addRequired<ScopInfo>();
+  AU.addRequired<ScopInfoRegionPass>();
   AU.addRequired<DependenceInfo>();
 }
 
 char IslAstInfo::ID = 0;
 
 Pass *polly::createIslAstInfoPass() { return new IslAstInfo(); }
 
 INITIALIZE_PASS_BEGIN(IslAstInfo, "polly-ast",
                       "Polly - Generate an AST of the SCoP (isl)", false,
                       false);
-INITIALIZE_PASS_DEPENDENCY(ScopInfo);
+INITIALIZE_PASS_DEPENDENCY(ScopInfoRegionPass);
 INITIALIZE_PASS_DEPENDENCY(DependenceInfo);
 INITIALIZE_PASS_END(IslAstInfo, "polly-ast",
                     "Polly - Generate an AST from the SCoP (isl)", false, false)

polly/trunk/lib/Exchange/JSONExporter.cpp

bool JSONExporter::runOnScop(Scop &S) {
   errs() << "  error opening file for writing!\n";
   F.os().clear_error();
 
   return false;
 }
 
 void JSONExporter::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.setPreservesAll();
-  AU.addRequired<ScopInfo>();
+  AU.addRequired<ScopInfoRegionPass>();
 }
 
 Pass *polly::createJSONExporterPass() { return new JSONExporter(); }
 
 char JSONImporter::ID = 0;
 std::string JSONImporter::getFileName(Scop &S) const {
   std::string FunctionName = S.getFunction().getName();
   std::string FileName = FunctionName + "___" + S.getNameStr() + ".jscop";

polly/trunk/lib/Support/RegisterPasses.cpp

void initializePollyPasses(PassRegistry &Registry) {
   initializeDeadCodeElimPass(Registry);
   initializeDependenceInfoPass(Registry);
   initializeJSONExporterPass(Registry);
   initializeJSONImporterPass(Registry);
   initializeIslAstInfoPass(Registry);
   initializeIslScheduleOptimizerPass(Registry);
   initializePollyCanonicalizePass(Registry);
   initializeScopDetectionPass(Registry);
-  initializeScopInfoPass(Registry);
+  initializeScopInfoRegionPassPass(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
if (PollyViewer)
     PM.add(polly::createDOTViewerPass());
   if (PollyOnlyViewer)
     PM.add(polly::createDOTOnlyViewerPass());
   if (PollyPrinter)
     PM.add(polly::createDOTPrinterPass());
   if (PollyOnlyPrinter)
     PM.add(polly::createDOTOnlyPrinterPass());
 
-  PM.add(polly::createScopInfoPass());
+  PM.add(polly::createScopInfoRegionPassPass());
 
   if (ImportJScop)
     PM.add(polly::createJSONImporterPass());
 
   if (DeadCodeElim)
     PM.add(polly::createDeadCodeElimPass());
 
   switch (Optimizer) {

polly/trunk/lib/Transform/DeadCodeElimination.cpp

void DeadCodeElim::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.addRequired<DependenceInfo>();
 }
 
 Pass *polly::createDeadCodeElimPass() { return new DeadCodeElim(); }
 
 INITIALIZE_PASS_BEGIN(DeadCodeElim, "polly-dce",
                       "Polly - Remove dead iterations", false, false)
 INITIALIZE_PASS_DEPENDENCY(DependenceInfo)
-INITIALIZE_PASS_DEPENDENCY(ScopInfo)
+INITIALIZE_PASS_DEPENDENCY(ScopInfoRegionPass)
 INITIALIZE_PASS_END(DeadCodeElim, "polly-dce", "Polly - Remove dead iterations",
                     false, false)

polly/trunk/lib/Transform/ScheduleOptimizer.cpp

 
 Pass *polly::createIslScheduleOptimizerPass() {
   return new IslScheduleOptimizer();
 }
 
 INITIALIZE_PASS_BEGIN(IslScheduleOptimizer, "polly-opt-isl",
                       "Polly - Optimize schedule of SCoP", false, false);
 INITIALIZE_PASS_DEPENDENCY(DependenceInfo);
-INITIALIZE_PASS_DEPENDENCY(ScopInfo);
+INITIALIZE_PASS_DEPENDENCY(ScopInfoRegionPass);
 INITIALIZE_PASS_END(IslScheduleOptimizer, "polly-opt-isl",
                     "Polly - Optimize schedule of SCoP", false, false)