[Refactor] Replace RegionPasses by FunctionPasses

[jdoerfert]

Summary

The main change is the switch to function instead of region passes.

However, due to the changed interface and the fact that analysis now
run on multiple SCoPs before their results are queried, other
adjustments were needed. These additional changes include:
  - Allow passes to handle multiple SCoPs at once, e.g., map the SCoPs
    to the information formerly stored as members in the pass.
  - Parametrize functions with the SCoP in question as there is not
    only one at a time anymore.
  - Update the tests not to look for the region pass manager output
  - Add a explicit ScopPass initialization function that is called
    once per function. This way analysis passes do not need to be
    queried for each SCoP.
  - Remap values between SCoPs in a function correctly.

---

There is a unit test failing because we split the region and that causes
dominance problems for other SCoPs. However, I'll wait till we fix the two
open dominance bugs (including the region splitting one) before I fix this.

[grosser]

As I already mentioned in discussions on the mailing list, I am concerned about moving to function passes, as building up all scops ahead of time then code generating the first may invalidate later scops. We had this problem maybe two years ago, which is why we moved away from this first-build-all-then-codegen-all model. I could see us using a different approach then what we do today, but I think there are various possible approaches that we should consider:

1. Model All - Then build all, but leave pass structure as today (this patch)
2. Have a single function pass that iteratively schedules scop detection / scop modeling / code generation just using library calls to implement this functionality
3. Keep the pass structure, but use on-demand scop modeling and caching similar to how the new pass manager caches objects.

It is not yet clear to me which approach is the best and I assume that the new pass manger will affect the decisions we take. Hence I suggest two things:

1. Most of the changes in ScopInfo go very much in a direction that will be useful for all of these approaches. What we want is to have a class that constructs a scop for a region and returns a scop object that is not connected with the ScopInfo pass. I suggest to introduce such a class to ensure that most of these changes do not bitrot and to reduce the diff needed to play around with these solutions.

2. I suggest to look into the new pass manager infrastructure and use this as a testbed to experiment with these different solutions. This should give us both necessary knowledge about the new pass manager as well as confidence on the stability of the different approaches without breaking the current behavior.

[Meinersbur]

To add to the discussion: In a Polly phone call, Zino discussed that we might go directly to CallGraphSCCPass, as fair as I remember to do something with inlining.

This would also allow us to generate code into a newly created function s.t. we do not need to modify the original code before all transformations are done (also to get rid of the exit block PHI during code generation).

[• zinob]

Johannes, what is the motivation to have this past?

[grosser]

Hi Johannes,

it seems first parts of this patch have been addressed with some of Utpal's recent commits and there is more work you and Utpal are doing that is going in the very same direction. Would it make sense to close this review and continue the discussion in the new reviews?

PS: Currently trying to clean up some of the review history

[jdoerfert]

Abandoned and redone in the GSoC.

include/polly/CodeGen/BlockGenerators.h

public:
   Value *getOrCreateAlloca(const ScopArrayInfo *Array);
 
   /// @brief Finalize the code generation for the SCoP @p S.
   ///
   /// This will initialize and finalize the scalar variables we demoted during
   /// the code generation.
   ///
   /// @see createScalarInitialization(Scop &)
-  /// @see createScalarFinalization(Region &)
-  void finalizeSCoP(Scop &S);
+  /// @see createScalarFinalization(Region &, ValueMapT &)
+  void finalizeSCoP(Scop &S, ValueMapT &InterScopMap);
 
   /// @brief An empty destructor
   virtual ~BlockGenerator(){};
 
   BlockGenerator(const BlockGenerator &) = default;
 
 protected:
   PollyIRBuilder &Builder;
protected:
   /// @param S The scop for which to generate the exiting PHI nodes.
   void createExitPHINodeMerges(Scop &S);
 
   /// @brief Promote the values of demoted scalars after the SCoP.
   ///
   /// If a scalar value was used outside the SCoP we need to promote the value
   /// stored in the memory cell allocated for that scalar and combine it with
   /// the original value in the non-optimized SCoP.
-  void createScalarFinalization(Region &R);
+  void createScalarFinalization(Region &R, ValueMapT &InterScopMap);
 
   /// @brief Try to synthesize a new value
   ///
   /// Given an old value, we try to synthesize it in a new context from its
   /// original SCEV expression. We start from the original SCEV expression,
   /// then replace outdated parameter and loop references, and finally
   /// expand it to code that computes this updated expression.
   ///

include/polly/CodeGen/IslAst.h

 struct isl_ast_build;
 struct isl_union_map;
 struct isl_pw_multi_aff;
 
 namespace polly {
 class Scop;
 class IslAst;
 class MemoryAccess;
+class DependenceInfo;
 
 class IslAstInfo : public ScopPass {
 public:
   using MemoryAccessSet = SmallPtrSet<MemoryAccess *, 4>;
 
   /// @brief Payload information used to annotate an AST node.
   struct IslAstUserPayload {
     /// @brief Construct and initialize the payload.
struct IslAstUserPayload {
     /// @brief The build environment at the time this node was constructed.
     isl_ast_build *Build;
 
     /// @brief Set of accesses which break reduction dependences.
     MemoryAccessSet BrokenReductions;
   };
 
 private:
-  Scop *S;
-  IslAst *Ast;
+  /// @brief Mapping from SCoP to AST representation.
+  DenseMap<const Scop *, IslAst *> AstMap;
+
+  /// @brief The dependence info pass.
+  DependenceInfo *DI;
 
 public:
   static char ID;
-  IslAstInfo() : ScopPass(ID), S(nullptr), Ast(nullptr) {}
+  IslAstInfo() : ScopPass(ID) {}
 
   /// @brief Build the AST for the given SCoP @p S.
   bool runOnScop(Scop &S) override;
 
   /// @brief Register all analyses and transformation required.
   void getAnalysisUsage(AnalysisUsage &AU) const override;
 
   /// @brief Release the internal memory.
   void releaseMemory() override;
 
+  /// @brief Initializer called once per function.
+  void initializeScopPass() override;
+
   /// @brief Print a source code representation of the program.
   void printScop(llvm::raw_ostream &OS, Scop &S) const override;
 
-  /// @brief Return a copy of the AST root node.
-  __isl_give isl_ast_node *getAst() const;
+  /// @brief Return a copy of the AST root node for the SCoP @p S.
+  __isl_give isl_ast_node *getAst(Scop &S) const;
 
   /// @brief Get the run condition.
   ///
   /// Only if the run condition evaluates at run-time to a non-zero value, the
   /// assumptions that have been taken hold. If the run condition evaluates to
   /// zero/false some assumptions do not hold and the original code needs to
   /// be executed.
-  __isl_give isl_ast_expr *getRunCondition() const;
+  __isl_give isl_ast_expr *getRunCondition(Scop &S) const;
 
   /// @name Extract information attached to an isl ast (for) node.
   ///
   ///{
 
   /// @brief Get the complete payload attached to @p Node.
   static IslAstUserPayload *getNodePayload(__isl_keep isl_ast_node *Node);
 

include/polly/CodeGen/IslNodeBuilder.h

 struct isl_ast_node;
 struct isl_ast_build;
 struct isl_union_map;
 
 class IslNodeBuilder {
 public:
   IslNodeBuilder(PollyIRBuilder &Builder, ScopAnnotator &Annotator, Pass *P,
                  const DataLayout &DL, LoopInfo &LI, ScalarEvolution &SE,
-                 DominatorTree &DT, Scop &S)
+                 DominatorTree &DT, Scop &S, ValueMapT &InterScopMap)
       : S(S), Builder(Builder), Annotator(Annotator),
         ExprBuilder(S, Builder, IDToValue, ValueMap, DL, SE, DT, LI),
+        ValueMap(InterScopMap), InterScopMap(InterScopMap),
         BlockGen(Builder, LI, SE, DT, ScalarMap, PHIOpMap, EscapeMap, ValueMap,
                  &ExprBuilder),
         RegionGen(BlockGen), P(P), DL(DL), LI(LI), SE(SE), DT(DT) {}
 
   virtual ~IslNodeBuilder() {}
 
   void addParameters(__isl_take isl_set *Context);
   void create(__isl_take isl_ast_node *Node);
 
   /// @brief Preload all memory loads that are invariant.
   void preloadInvariantLoads();
 
   /// @brief Finalize code generation for the SCoP @p S.
   ///
   /// @see BlockGenerator::finalizeSCoP(Scop &S)
-  void finalizeSCoP(Scop &S) { BlockGen.finalizeSCoP(S); }
+  void finalizeSCoP(Scop &S) { BlockGen.finalizeSCoP(S, InterScopMap); }
 
   IslExprBuilder &getExprBuilder() { return ExprBuilder; }
 
   /// @brief Get the associated block generator.
   ///
   /// @return A referecne to the associated block generator.
   BlockGenerator &getBlockGenerator() { return BlockGen; }
 
 protected:
   Scop &S;
   PollyIRBuilder &Builder;
   ScopAnnotator &Annotator;
 
   IslExprBuilder ExprBuilder;
 
+  /// A set of Value -> Value remappings to apply when generating new code.
+  ///
+  /// When generating new code for a ScopStmt this map is used to map certain
+  /// llvm::Values to new llvm::Values.
+  ValueMapT ValueMap;
+
   /// @brief Maps used by the block and region generator to demote scalars.
   ///
   ///@{
 
   /// @brief See BlockGenerator::ScalarMap.
   BlockGenerator::ScalarAllocaMapTy ScalarMap;
 
   /// @brief See BlockGenerator::PhiOpMap.
   BlockGenerator::ScalarAllocaMapTy PHIOpMap;
 
   /// @brief See BlockGenerator::EscapeMap.
   BlockGenerator::EscapeUsersAllocaMapTy EscapeMap;
 
+  /// @brief Map to resolve changes to cached SCEVs in other SCoPs.
+  ValueMapT &InterScopMap;
+
   ///@}
 
   /// @brief The generator used to copy a basic block.
   BlockGenerator BlockGen;
 
   /// @brief The generator used to copy a non-affine region.
   RegionGenerator RegionGen;
 
protected:
   ///
   /// This function generates code for a given SCEV expression. It generated
   /// code is emmitted at the end of the basic block our Builder currently
   /// points to and the resulting value is returned.
   ///
   /// @param Expr The expression to code generate.
   llvm::Value *generateSCEV(const SCEV *Expr);
 
-  /// A set of Value -> Value remappings to apply when generating new code.
-  ///
-  /// When generating new code for a ScopStmt this map is used to map certain
-  /// llvm::Values to new llvm::Values.
-  ValueMapT ValueMap;
-
   /// @brief Materialize code for @p Id if it was not done before.
   void materializeValue(__isl_take isl_id *Id);
 
   /// @brief Materialize parameters of @p Set.
   ///
   /// @param All If not set only parameters referred to by the constraints in
   ///            @p Set will be materialized, otherwise all.
   void materializeParameters(__isl_take isl_set *Set, bool All);

include/polly/DependenceInfo.h

enum Type {
 
     // Reduction dependences
     TYPE_RED = 1 << 3,
 
     // Transitive closure of the reduction dependences (& the reverse)
     TYPE_TC_RED = 1 << 4,
   };
 
+  /// @brief Create an empty dependences struct.
+  Dependences()
+      : RAW(nullptr), WAR(nullptr), WAW(nullptr), RED(nullptr),
+        TC_RED(nullptr) {}
+
+  /// @brief Destructor that will free internal objects.
+  ~Dependences() { releaseMemory(); }
+
   /// @brief Get the dependences of type @p Kinds.
   ///
   /// @param Kinds This integer defines the different kinds of dependences
   ///              that will be returned. To return more than one kind, the
   ///              different kinds are 'ored' together.
   __isl_give isl_union_map *getDependences(int Kinds) const;
 
   /// @brief Report if valid dependences are available.
struct Dependences {
 
   /// @brief Allow the DependenceInfo access to private members and methods.
   ///
   /// To restict access to the internal state only the DependenceInfo class
   /// is able to call or modify a dependences struct.
   friend class DependenceInfo;
 
 private:
-  /// @brief Create an empty dependences struct.
-  Dependences()
-      : RAW(nullptr), WAR(nullptr), WAW(nullptr), RED(nullptr),
-        TC_RED(nullptr) {}
-
-  /// @brief Destructor that will free internal objects.
-  ~Dependences() { releaseMemory(); }
-
   /// @brief Calculate and add at the privatization dependences.
   void addPrivatizationDependences();
 
   /// @brief Calculate the dependences for a certain SCoP @p S.
   void calculateDependences(Scop &S);
 
   /// @brief Set the reduction dependences for @p MA to @p Deps.
   void setReductionDependences(MemoryAccess *MA, __isl_take isl_map *Deps);

 
 class DependenceInfo : public ScopPass {
 public:
   static char ID;
 
   /// @brief Construct a new DependenceInfo pass.
   DependenceInfo() : ScopPass(ID) {}
 
-  /// @brief Return the dependence information for the current SCoP.
-  const Dependences &getDependences() { return D; }
+  /// @brief Return the dependence information for the given SCoP @p S
+  const Dependences &getDependences(Scop &S) const {
+    assert(DependenceMap.count(&S) && "Dependences for given SCoP not found");
+    return DependenceMap.find(&S)->getSecond();
+  }
 
-  /// @brief Recompute dependences from schedule and memory accesses.
-  void recomputeDependences();
+  /// @brief Return the dependence information for the given SCoP @p S
+  Dependences &getDependences(Scop &S) {
+    assert(DependenceMap.count(&S) && "Dependences for given SCoP not found");
+    return DependenceMap.find(&S)->getSecond();
+  }
 
-  /// @brief Compute the dependence information for the SCoP @p S.
-  bool runOnScop(Scop &S) override;
+  /// @brief Recompute dependences from schedule and memory accesses.
+  void recomputeDependences(Scop &S);
 
-  /// @brief Print the dependences for the given SCoP to @p OS.
-  void printScop(raw_ostream &OS, Scop &) const override { D.print(OS); }
+  /// @brief Initializer called once per function.
+  void initializeScopPass() override {}
 
-  /// @brief Release the internal memory.
-  void releaseMemory() override { D.releaseMemory(); }
+  /// @brief Print the dependences for the given SCoP @p S to @p OS.
+  void printScop(raw_ostream &OS, Scop &S) const override;
 
-  /// @brief Register all analyses and transformation required.
+  bool runOnScop(Scop &S) override;
+  void releaseMemory() override;
   void getAnalysisUsage(AnalysisUsage &AU) const override;
 
 private:
-  Scop *S;
-
-  /// @brief Dependences struct for the current SCoP.
-  Dependences D;
+  /// @brief Mapping from SCoPs to their dependence structs.
+  DenseMap<const Scop *, Dependences> DependenceMap;
 };
 
 } // End polly namespace.
 
 namespace llvm {
 class PassRegistry;
 void initializeDependenceInfoPass(llvm::PassRegistry &);
 }
 
 #endif

include/polly/ScopDetection.h

public:
   std::string regionIsInvalidBecause(const Region *R) const;
 
   /// @name Maximum Region In Scops Iterators
   ///
   /// These iterators iterator over all maximum region in Scops of this
   /// function.
   //@{
   typedef RegionSet::iterator iterator;
-  typedef RegionSet::const_iterator const_iterator;
 
   iterator begin() { return ValidRegions.begin(); }
   iterator end() { return ValidRegions.end(); }
-
-  const_iterator begin() const { return ValidRegions.begin(); }
-  const_iterator end() const { return ValidRegions.end(); }
   //@}
 
   /// @name Reject log iterators
   ///
   /// These iterators iterate over the logs of all rejected regions of this
   //  function.
   //@{
   typedef std::map<const Region *, RejectLog>::iterator reject_iterator;

include/polly/ScopInfo.h

 
 #ifndef POLLY_SCOP_INFO_H
 #define POLLY_SCOP_INFO_H
 
 #include "polly/ScopDetection.h"
 #include "polly/Support/SCEVAffinator.h"
 
 #include "llvm/ADT/MapVector.h"
-#include "llvm/Analysis/RegionPass.h"
 #include "isl/aff.h"
+
+#include "llvm/Analysis/RegionPass.h"
+#include "llvm/Pass.h"
+
 #include "isl/ctx.h"
 
 #include <deque>
 #include <forward_list>
 
 using namespace llvm;
 
 namespace llvm {

 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 : public FunctionPass {
+public:
+  /// @brief Type for a vector of SCoPs.
+  using ScopVectorTy = SmallVector<Scop *, 4>;
+
+  /// @brief Iterator type for a SCoP vector.
+  using iterator = ScopVectorTy::iterator;
+  using const_iterator = ScopVectorTy::const_iterator;
+
+private:
   ScopInfo(const ScopInfo &) = delete;
   const ScopInfo &operator=(const ScopInfo &) = delete;
 
   // The ScalarEvolution to help building Scop.
   ScalarEvolution *SE;
 
   // LoopInfo for information about loops
   LoopInfo *LI;
 
   // The AliasAnalysis to build AliasSetTracker.
   AliasAnalysis *AA;
 
   // Valid Regions for Scop
   ScopDetection *SD;
 
   // Target data for element size computing.
   const DataLayout *TD;
 
   // Access function of statements (currently BasicBlocks) .
   //
   // This owns all the MemoryAccess objects of the Scop created in this pass. It
   // must live until #scop is deleted.
   AccFuncMapType AccFuncMap;
 
-  // The Scop
-  Scop *scop;
-  isl_ctx *ctx;
-
-  /// @brief Return the SCoP region that is currently processed.
-  Region *getRegion() const {
-    if (!scop)
-      return nullptr;
-    return &scop->getRegion();
-  }
+  /// @brief The SCoPs build in this function.
+  ScopVectorTy Scops;
 
-  // Clear the context.
-  void clear();
+  /// @brief The isl contexts for each SCoP created.
+  SmallVector<isl_ctx *, 16> IslCtxs;
 
-  // Build the SCoP for Region @p R.
-  void buildScop(Region &R, DominatorTree &DT);
+  /// @brief Build the SCoP for Region @p R.
+  Scop *buildScop(Region &R, DominatorTree &DT);
 
   /// @brief Build an instance of MemoryAccess from the Load/Store instruction.
   ///
+  /// @param S          The SCoP currently build.
   /// @param Inst       The Load/Store instruction that access the memory
   /// @param L          The parent loop of the instruction
-  /// @param R          The region on which to build the data access dictionary.
   /// @param BoxedLoops The set of loops that are overapproximated in @p R.
   /// @param ScopRIL    The required invariant loads equivalence classes.
-  void buildMemoryAccess(Instruction *Inst, Loop *L, Region *R,
+  void buildMemoryAccess(Scop &S, Instruction *Inst, Loop *L,
                          const ScopDetection::BoxedLoopsSetTy *BoxedLoops,
                          const InvariantLoadsSetTy &ScopRIL);
 
   /// @brief Analyze and extract the cross-BB scalar dependences (or,
   ///        dataflow dependencies) of an instruction.
   ///
+  /// @param S                  The SCoP currently build.
   /// @param Inst               The instruction to be analyzed
-  /// @param R                  The SCoP region
   /// @param NonAffineSubRegion The non affine sub-region @p Inst is in.
   ///
   /// @return     True if the Instruction is used in other BB and a scalar write
   ///             Access is required.
-  bool buildScalarDependences(Instruction *Inst, Region *R,
+  bool buildScalarDependences(Scop &S, Instruction *Inst,
                               Region *NonAffineSubRegio);
 
   /// @brief Create MemoryAccesses for the given PHI node in the given region.
   ///
+  /// @param S                  The SCoP currently build.
   /// @param PHI                The PHI node to be handled
-  /// @param R                  The SCoP region
   /// @param NonAffineSubRegion The non affine sub-region @p PHI is in.
   /// @param IsExitBlock        Flag to indicate that @p PHI is in the exit BB.
-  void buildPHIAccesses(PHINode *PHI, Region &R, Region *NonAffineSubRegion,
+  void buildPHIAccesses(Scop &S, PHINode *PHI, Region *NonAffineSubRegion,
                         bool IsExitBlock = false);
 
   /// @brief Build the access functions for the subregion @p SR.
   ///
-  /// @param R  The SCoP region.
+  /// @param S  The SCoP currently build.
   /// @param SR A subregion of @p R.
-  void buildAccessFunctions(Region &R, Region &SR);
+  void buildAccessFunctions(Scop &S, Region &SR);
 
   /// @brief Create ScopStmt for all BBs and non-affine subregions of @p SR.
   ///
   /// Some of the statments might be optimized away later when they do not
   /// access any memory and thus have no effect.
-  void buildStmts(Region &SR);
+  void buildStmts(Scop &S, Region &SR);
 
   /// @brief Build the access functions for the basic block @p BB
   ///
-  /// @param R                  The SCoP region.
+  /// @param S                  The SCoP currently build.
   /// @param BB                 A basic block in @p R.
   /// @param NonAffineSubRegion The non affine sub-region @p BB is in.
   /// @param IsExitBlock        Flag to indicate that @p BB is in the exit BB.
-  void buildAccessFunctions(Region &R, BasicBlock &BB,
+  void buildAccessFunctions(Scop &S, BasicBlock &BB,
                             Region *NonAffineSubRegion = nullptr,
                             bool IsExitBlock = false);
 
   /// @brief Create a new MemoryAccess object and add it to #AccFuncMap.
   ///
+  /// @param S           The SCoP currently build.
   /// @param BB          The block where the access takes place.
   /// @param Inst        The instruction doing the access. It is not necessarily
   ///                    inside @p BB.
   /// @param Type        The kind of access.
   /// @param BaseAddress The accessed array's base address.
   /// @param ElemBytes   Size of accessed array element.
   /// @param Affine      Whether all subscripts are affine expressions.
   /// @param AccessValue Value read or written.
   /// @param Subscripts  Access subscripts per dimension.
   /// @param Sizes       The array diminsion's sizes.
   /// @param Origin      Purpose of this access.
-  void addMemoryAccess(BasicBlock *BB, Instruction *Inst,
+  void addMemoryAccess(Scop &S, BasicBlock *BB, Instruction *Inst,
                        MemoryAccess::AccessType Type, Value *BaseAddress,
                        unsigned ElemBytes, bool Affine, Value *AccessValue,
                        ArrayRef<const SCEV *> Subscripts,
                        ArrayRef<const SCEV *> Sizes,
                        MemoryAccess::AccessOrigin Origin);
 
   /// @brief Create a MemoryAccess that represents either a LoadInst or
   /// StoreInst.
   ///
+  /// @param S           The SCoP currently build.
   /// @param MemAccInst  The LoadInst or StoreInst.
   /// @param Type        The kind of access.
   /// @param BaseAddress The accessed array's base address.
   /// @param ElemBytes   Size of accessed array element.
   /// @param IsAffine    Whether all subscripts are affine expressions.
   /// @param Subscripts  Access subscripts per dimension.
   /// @param Sizes       The array dimension's sizes.
   /// @param AccessValue Value read or written.
   /// @see AccessOrigin
-  void addExplicitAccess(Instruction *MemAccInst, MemoryAccess::AccessType Type,
-                         Value *BaseAddress, unsigned ElemBytes, bool IsAffine,
+  void addExplicitAccess(Scop &S, Instruction *MemAccInst,
+                         MemoryAccess::AccessType Type, Value *BaseAddress,
+                         unsigned ElemBytes, bool IsAffine,
                          ArrayRef<const SCEV *> Subscripts,
                          ArrayRef<const SCEV *> Sizes, Value *AccessValue);
 
   /// @brief Create a MemoryAccess for writing an llvm::Value.
   ///
   /// The access will be created at the @p Value's definition.
   ///
+  /// @param S     The SCoP currently build.
   /// @param Value The value to be written.
   /// @see addScalarReadAccess()
   /// @see AccessOrigin
-  void addScalarWriteAccess(Instruction *Value);
+  void addScalarWriteAccess(Scop &S, Instruction *Value);
 
   /// @brief Create a MemoryAccess for reloading an llvm::Value.
   ///
   /// Use this overload only for non-PHI instructions.
   ///
+  /// @param S     The SCoP currently build.
   /// @param Value The scalar expected to be loaded.
   /// @param User  User of the scalar; this is where the access is added.
   /// @see addScalarWriteAccess()
   /// @see AccessOrigin
-  void addScalarReadAccess(Value *Value, Instruction *User);
+  void addScalarReadAccess(Scop &S, Value *Value, Instruction *User);
 
   /// @brief Create a MemoryAccess for reloading an llvm::Value.
   ///
   /// This is for PHINodes using the scalar. As we model it, the used value must
   /// be available at the incoming block instead of when hitting the
   /// instruction.
   ///
+  /// @param S      The SCoP currently build.
   /// @param Value  The scalar expected to be loaded.
   /// @param User   The PHI node referencing @p Value.
   /// @param UserBB Incoming block for the incoming @p Value.
   /// @see addPHIWriteAccess()
   /// @see addScalarWriteAccess()
   /// @see AccessOrigin
-  void addScalarReadAccess(Value *Value, PHINode *User, BasicBlock *UserBB);
+  void addScalarReadAccess(Scop &S, Value *Value, PHINode *User,
+                           BasicBlock *UserBB);
 
   /// @brief Create a write MemoryAccess for the incoming block of a phi node.
   ///
   /// Each of the incoming blocks write their incoming value to be picked in the
   /// phi's block.
   ///
+  /// @param S             The SCoP currently build.
   /// @param PHI           PHINode under consideration.
   /// @param IncomingBlock Some predecessor block.
   /// @param IncomingValue @p PHI's value when coming from @p IncomingBlock.
   /// @param IsExitBlock   When true, uses the .s2a alloca instead of the
   ///                      .phiops one. Required for values escaping through a
   ///                      PHINode in the SCoP region's exit block.
   /// @see addPHIReadAccess()
   /// @see AccessOrigin
-  void addPHIWriteAccess(PHINode *PHI, BasicBlock *IncomingBlock,
+  void addPHIWriteAccess(Scop &S, PHINode *PHI, BasicBlock *IncomingBlock,
                          Value *IncomingValue, bool IsExitBlock);
 
   /// @brief Create a MemoryAccess for reading the value of a phi.
   ///
   /// The modeling assumes that all incoming blocks write their incoming value
   /// to the same location. Thus, this access will read the incoming block's
   /// value as instructed by this @p PHI.
   ///
+  /// @param S   The SCoP currently build.
   /// @param PHI PHINode under consideration; the READ access will be added
   /// here.
   /// @see addPHIWriteAccess()
   /// @see AccessOrigin
-  void addPHIReadAccess(PHINode *PHI);
+  void addPHIReadAccess(Scop &S, PHINode *PHI);
 
 public:
   static char ID;
-  explicit ScopInfo();
+  ScopInfo() : FunctionPass(ID) {}
   ~ScopInfo();
 
-  /// @brief Try to build the Polly IR of static control part on the current
-  ///        SESE-Region.
+  /// @brief Iterator interface to access all SCoPs in this function.
   ///
-  /// @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; }
-  const Scop *getScop() const { return scop; }
+  ///{
+  iterator begin() { return Scops.begin(); }
+  iterator end() { return Scops.end(); }
+  const_iterator begin() const { return Scops.begin(); }
+  const_iterator end() const { return Scops.end(); }
+  ///}
 
-  /// @name RegionPass interface
+  /// @name FunctionPass 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;
+  virtual bool runOnFunction(Function &F) override;
+  virtual void getAnalysisUsage(AnalysisUsage &AU) const override;
+  virtual void releaseMemory() override;
+  virtual void print(raw_ostream &OS, const Module *) const override;
   //@}
 };
 
 } // end namespace polly
 
 namespace llvm {
 class PassRegistry;
 void initializeScopInfoPass(llvm::PassRegistry &);
 }
 
 #endif

include/polly/ScopPass.h

 //===--------- ScopPass.h - Pass for Static Control Parts --------*-C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
-// This file defines the ScopPass class.  ScopPasses are just RegionPasses,
+// This file defines the ScopPass class. ScopPasses are just FunctionPasses,
 // except they operate on Polly IR (Scop and ScopStmt) built by ScopInfo Pass.
 // Because they operate on Polly IR, not the LLVM IR, ScopPasses are not allowed
 // to modify the LLVM IR. Due to this limitation, the ScopPass class takes
 // care of declaring that no LLVM passes are invalidated.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef POLLY_SCOP_PASS_H
 #define POLLY_SCOP_PASS_H
 
-#include "llvm/Analysis/RegionPass.h"
+#include "llvm/Pass.h"
 
 using namespace llvm;
 
 struct isl_ctx;
 
 namespace polly {
 class Scop;
+class ScopInfo;
 
-/// ScopPass - This class adapts the RegionPass interface to allow convenient
+/// ScopPass - This class adapts the FunctionPass interface to allow convenient
 /// creation of passes that operate on the Polly IR. Instead of overriding
-/// runOnRegion, subclasses override runOnScop.
-class ScopPass : public RegionPass {
-  Scop *S;
+/// runOnFunction, subclasses override runOnScop.
+class ScopPass : public FunctionPass {
+
+  /// @brief The ScopInfo class that builds the SCoPs.
+  ScopInfo *SI;
 
 protected:
-  explicit ScopPass(char &ID) : RegionPass(ID), S(0) {}
+  explicit ScopPass(char &ID) : FunctionPass(ID) {}
 
-  /// runOnScop - This method must be overloaded to perform the
-  /// desired Polyhedral transformation or analysis.
-  ///
+  /// @brief Run method for all ScopPass subclasses. Called for each SCoP once.
   virtual bool runOnScop(Scop &S) = 0;
 
+  /// @brief Initialization method run once per function.
+  ///
+  /// This allows ScopPass subclasses to initialize members like analysis passes
+  /// once per function instead of once per SCoP.
+  virtual void initializeScopPass() = 0;
+
   /// @brief Print method for SCoPs.
   virtual void printScop(raw_ostream &OS, Scop &S) const {};
 
-  /// getAnalysisUsage - Subclasses that override getAnalysisUsage
-  /// must call this.
-  ///
+  /// @brief Subclasses that override getAnalysisUsage must call this.
   virtual void getAnalysisUsage(AnalysisUsage &AU) const override;
 
 private:
-  bool runOnRegion(Region *R, RGPassManager &RGM) override;
+  bool runOnFunction(Function &F) override;
   void print(raw_ostream &OS, const Module *) const override;
 };
 
 } // End llvm namespace
 
 #endif

lib/Analysis/DependenceInfo.cpp

 //
 //===----------------------------------------------------------------------===//
 //
 #include "polly/DependenceInfo.h"
 #include "polly/LinkAllPasses.h"
 #include "polly/Options.h"
 #include "polly/ScopInfo.h"
 #include "polly/Support/GICHelper.h"
+
+#include "llvm/Analysis/RegionInfo.h"
 #include "llvm/Support/Debug.h"
 #include <isl/aff.h>
 #include <isl/ctx.h>
 #include <isl/flow.h>
 #include <isl/map.h>
 #include <isl/options.h>
 #include <isl/schedule.h>
 #include <isl/set.h>

 }
 
 void Dependences::setReductionDependences(MemoryAccess *MA, isl_map *D) {
   assert(ReductionDependences.count(MA) == 0 &&
          "Reduction dependences set twice!");
   ReductionDependences[MA] = D;
 }
 
-void DependenceInfo::recomputeDependences() {
-  releaseMemory();
-  D.calculateDependences(*S);
+void DependenceInfo::releaseMemory() { DependenceMap.clear(); }
+
+void DependenceInfo::recomputeDependences(Scop &S) {
+  Dependences &D = getDependences(S);
+  D.releaseMemory();
+  D.calculateDependences(S);
 }
 
-bool DependenceInfo::runOnScop(Scop &ScopVar) {
-  S = &ScopVar;
-  recomputeDependences();
+bool DependenceInfo::runOnScop(Scop &S) {
+  Dependences &D = DependenceMap[&S];
+  D.calculateDependences(S);
   return false;
 }
 
+void DependenceInfo::printScop(raw_ostream &OS, Scop &S) const {
+  OS << "Dependences for region: " << S.getRegion() << "\n";
+  getDependences(S).print(OS);
+}
+
 void DependenceInfo::getAnalysisUsage(AnalysisUsage &AU) const {
   ScopPass::getAnalysisUsage(AU);
 }
 
 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_END(DependenceInfo, "polly-dependences",
                     "Polly - Calculate dependences", false, false)

lib/Analysis/ScopInfo.cpp

 int Scop::getRelativeLoopDepth(const Loop *L) const {
   Loop *OuterLoop =
       L ? R.outermostLoopInRegion(const_cast<Loop *>(L)) : nullptr;
   if (!OuterLoop)
     return -1;
   return L->getLoopDepth() - OuterLoop->getLoopDepth();
 }
 
-void ScopInfo::buildPHIAccesses(PHINode *PHI, Region &R,
+void ScopInfo::buildPHIAccesses(Scop &S, PHINode *PHI,
                                 Region *NonAffineSubRegion, bool IsExitBlock) {
 
   // 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.
-  if (!IsExitBlock && canSynthesize(PHI, LI, SE, &R))
+  if (!IsExitBlock && canSynthesize(PHI, LI, SE, &S.getRegion()))
     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);
     BasicBlock *OpBB = PHI->getIncomingBlock(u);
 
     // Do not build scalar dependences inside a non-affine subregion.
     if (NonAffineSubRegion && NonAffineSubRegion->contains(OpBB))
       continue;
 
     OnlyNonAffineSubRegionOperands = false;
 
-    if (!R.contains(OpBB))
+    if (!S.getRegion().contains(OpBB))
       continue;
 
     Instruction *OpI = dyn_cast<Instruction>(Op);
     if (OpI) {
       BasicBlock *OpIBB = OpI->getParent();
       // As we pretend there is a use (or more precise a write) of OpI in OpBB
       // we have to insert a scalar dependence from the definition of OpI to
       // OpBB if the definition is not in OpBB.
-      if (scop->getStmtForBasicBlock(OpIBB) !=
-          scop->getStmtForBasicBlock(OpBB)) {
-        addScalarReadAccess(OpI, PHI, OpBB);
-        addScalarWriteAccess(OpI);
+      if (S.getStmtForBasicBlock(OpIBB) != S.getStmtForBasicBlock(OpBB)) {
+        addScalarReadAccess(S, OpI, PHI, OpBB);
+        addScalarWriteAccess(S, OpI);
       }
     } else if (ModelReadOnlyScalars && !isa<Constant>(Op)) {
-      addScalarReadAccess(Op, PHI, OpBB);
+      addScalarReadAccess(S, Op, PHI, OpBB);
     }
 
-    addPHIWriteAccess(PHI, OpBB, Op, IsExitBlock);
+    addPHIWriteAccess(S, PHI, OpBB, Op, IsExitBlock);
   }
 
   if (!OnlyNonAffineSubRegionOperands && !IsExitBlock) {
-    addPHIReadAccess(PHI);
+    addPHIReadAccess(S, PHI);
   }
 }
 
-bool ScopInfo::buildScalarDependences(Instruction *Inst, Region *R,
+bool ScopInfo::buildScalarDependences(Scop &S, Instruction *Inst,
                                       Region *NonAffineSubRegion) {
+  Region *R = &S.getRegion();
   bool canSynthesizeInst = canSynthesize(Inst, LI, SE, R);
   if (isIgnoredIntrinsic(Inst))
     return false;
 
   bool AnyCrossStmtUse = false;
   BasicBlock *ParentBB = Inst->getParent();
 
   for (User *U : Inst->users()) {
if (isa<PHINode>(UI))
       continue;
 
     // Now U is used in another statement.
     AnyCrossStmtUse = true;
 
     // Do not build a read access that is not in the current SCoP
     // Use the def instruction as base address of the MemoryAccess, so that it
     // will become the name of the scalar access in the polyhedral form.
-    addScalarReadAccess(Inst, UI);
+    addScalarReadAccess(S, Inst, UI);
   }
 
   if (ModelReadOnlyScalars && !isa<PHINode>(Inst)) {
     for (Value *Op : Inst->operands()) {
       if (canSynthesize(Op, LI, SE, R))
         continue;
 
       if (Instruction *OpInst = dyn_cast<Instruction>(Op))
         if (R->contains(OpInst))
           continue;
 
       if (isa<Constant>(Op))
         continue;
 
-      addScalarReadAccess(Op, Inst);
+      addScalarReadAccess(S, Op, Inst);
     }
   }
 
   return AnyCrossStmtUse;
 }
 
 extern MapInsnToMemAcc InsnToMemAcc;
 
 void ScopInfo::buildMemoryAccess(
-    Instruction *Inst, Loop *L, Region *R,
+    Scop &S, Instruction *Inst, Loop *L,
     const ScopDetection::BoxedLoopsSetTy *BoxedLoops,
     const InvariantLoadsSetTy &ScopRIL) {
+
   unsigned Size;
   Type *SizeType;
   Value *Val;
   enum MemoryAccess::AccessType Type;
+  Region *R = &S.getRegion();
 
   if (LoadInst *Load = dyn_cast<LoadInst>(Inst)) {
     SizeType = Load->getType();
     Size = TD->getTypeStoreSize(SizeType);
     Type = MemoryAccess::READ;
     Val = Load;
   } else {
     StoreInst *Store = cast<StoreInst>(Inst);
if (auto *GEP = dyn_cast<GetElementPtrInst>(NewAddress)) {
 
       if (AllAffineSubcripts && Sizes.size() > 0) {
         for (auto V : Sizes)
           SizesSCEV.push_back(SE->getSCEV(ConstantInt::get(
               IntegerType::getInt64Ty(BasePtr->getContext()), V)));
         SizesSCEV.push_back(SE->getSCEV(ConstantInt::get(
             IntegerType::getInt64Ty(BasePtr->getContext()), Size)));
 
-        addExplicitAccess(Inst, Type, BasePointer->getValue(), Size, true,
+        addExplicitAccess(S, Inst, Type, BasePointer->getValue(), Size, true,
                           Subscripts, SizesSCEV, Val);
         return;
       }
     }
   }
 
   auto AccItr = InsnToMemAcc.find(Inst);
   if (PollyDelinearize && AccItr != InsnToMemAcc.end()) {
-    addExplicitAccess(Inst, Type, BasePointer->getValue(), Size, true,
+    addExplicitAccess(S, Inst, Type, BasePointer->getValue(), Size, true,
                       AccItr->second.DelinearizedSubscripts,
                       AccItr->second.Shape->DelinearizedSizes, Val);
     return;
   }
 
   // Check if the access depends on a loop contained in a non-affine subregion.
   bool isVariantInNonAffineLoop = false;
   if (BoxedLoops) {
void ScopInfo::buildMemoryAccess(
   // FIXME: Size of the number of bytes of an array element, not the number of
   // elements as probably intended here.
   const SCEV *SizeSCEV =
       SE->getConstant(TD->getIntPtrType(Inst->getContext()), Size);
 
   if (!IsAffine && Type == MemoryAccess::MUST_WRITE)
     Type = MemoryAccess::MAY_WRITE;
 
-  addExplicitAccess(Inst, Type, BasePointer->getValue(), Size, IsAffine,
+  addExplicitAccess(S, Inst, Type, BasePointer->getValue(), Size, IsAffine,
                     ArrayRef<const SCEV *>(AccessFunction),
                     ArrayRef<const SCEV *>(SizeSCEV), Val);
 }
 
-void ScopInfo::buildAccessFunctions(Region &R, Region &SR) {
+void ScopInfo::buildAccessFunctions(Scop &S, Region &SR) {
 
-  if (SD->isNonAffineSubRegion(&SR, &R)) {
+  if (SD->isNonAffineSubRegion(&SR, &S.getRegion())) {
     for (BasicBlock *BB : SR.blocks())
-      buildAccessFunctions(R, *BB, &SR);
+      buildAccessFunctions(S, *BB, &SR);
     return;
   }
 
   for (auto I = SR.element_begin(), E = SR.element_end(); I != E; ++I)
     if (I->isSubRegion())
-      buildAccessFunctions(R, *I->getNodeAs<Region>());
+      buildAccessFunctions(S, *I->getNodeAs<Region>());
     else
-      buildAccessFunctions(R, *I->getNodeAs<BasicBlock>());
+      buildAccessFunctions(S, *I->getNodeAs<BasicBlock>());
 }
 
-void ScopInfo::buildStmts(Region &SR) {
-  Region *R = getRegion();
+void ScopInfo::buildStmts(Scop &S, Region &SR) {
+  Region *R = &S.getRegion();
 
   if (SD->isNonAffineSubRegion(&SR, R)) {
-    scop->addScopStmt(nullptr, &SR);
+    S.addScopStmt(nullptr, &SR);
     return;
   }
 
   for (auto I = SR.element_begin(), E = SR.element_end(); I != E; ++I)
     if (I->isSubRegion())
-      buildStmts(*I->getNodeAs<Region>());
+      buildStmts(S, *I->getNodeAs<Region>());
     else
-      scop->addScopStmt(I->getNodeAs<BasicBlock>(), nullptr);
+      S.addScopStmt(I->getNodeAs<BasicBlock>(), nullptr);
 }
 
-void ScopInfo::buildAccessFunctions(Region &R, BasicBlock &BB,
+void ScopInfo::buildAccessFunctions(Scop &S, BasicBlock &BB,
                                     Region *NonAffineSubRegion,
                                     bool IsExitBlock) {
+  Region *R = &S.getRegion();
   Loop *L = LI->getLoopFor(&BB);
 
   // The set of loops contained in non-affine subregions that are part of R.
-  const ScopDetection::BoxedLoopsSetTy *BoxedLoops = SD->getBoxedLoops(&R);
+  const ScopDetection::BoxedLoopsSetTy *BoxedLoops = SD->getBoxedLoops(R);
 
   // The set of loads that are required to be invariant.
-  auto &ScopRIL = *SD->getRequiredInvariantLoads(&R);
+  auto &ScopRIL = *SD->getRequiredInvariantLoads(R);
 
   for (BasicBlock::iterator I = BB.begin(), E = --BB.end(); I != E; ++I) {
     Instruction *Inst = I;
 
     PHINode *PHI = dyn_cast<PHINode>(Inst);
     if (PHI)
-      buildPHIAccesses(PHI, R, NonAffineSubRegion, IsExitBlock);
+      buildPHIAccesses(S, PHI, NonAffineSubRegion, IsExitBlock);
 
     // For the exit block we stop modeling after the last PHI node.
     if (!PHI && IsExitBlock)
       break;
 
     // TODO: At this point we only know that elements of ScopRIL have to be
     //       invariant and will be hoisted for the SCoP to be processed. Though,
     //       there might be other invariant accesses that will be hoisted and
     //       that would allow to make a non-affine access affine.
     if (isa<LoadInst>(Inst) || isa<StoreInst>(Inst))
-      buildMemoryAccess(Inst, L, &R, BoxedLoops, ScopRIL);
+      buildMemoryAccess(S, Inst, L, BoxedLoops, ScopRIL);
 
     if (isIgnoredIntrinsic(Inst))
       continue;
 
     // Do not build scalar dependences for required invariant loads as we will
     // hoist them later on anyway or drop the SCoP if we cannot.
     if (ScopRIL.count(dyn_cast<LoadInst>(Inst)))
       continue;
 
-    if (buildScalarDependences(Inst, &R, NonAffineSubRegion)) {
+    if (buildScalarDependences(S, Inst, NonAffineSubRegion)) {
       if (!isa<StoreInst>(Inst))
-        addScalarWriteAccess(Inst);
+        addScalarWriteAccess(S, Inst);
     }
   }
 }
 
-void ScopInfo::addMemoryAccess(BasicBlock *BB, Instruction *Inst,
+void ScopInfo::addMemoryAccess(Scop &S, BasicBlock *BB, Instruction *Inst,
                                MemoryAccess::AccessType Type,
                                Value *BaseAddress, unsigned ElemBytes,
                                bool Affine, Value *AccessValue,
                                ArrayRef<const SCEV *> Subscripts,
                                ArrayRef<const SCEV *> Sizes,
                                MemoryAccess::AccessOrigin Origin) {
-  ScopStmt *Stmt = scop->getStmtForBasicBlock(BB);
+  ScopStmt *Stmt = S.getStmtForBasicBlock(BB);
 
   // Do not create a memory access for anything not in the SCoP. It would be
   // ignored anyway.
   if (!Stmt)
     return;
 
   AccFuncSetType &AccList = AccFuncMap[BB];
   size_t Identifier = AccList.size();
 
   Value *BaseAddr = BaseAddress;
   std::string BaseName = getIslCompatibleName("MemRef_", BaseAddr, "");
 
   std::string IdName = "__polly_array_ref_" + std::to_string(Identifier);
-  isl_id *Id = isl_id_alloc(ctx, IdName.c_str(), nullptr);
+  isl_id *Id = isl_id_alloc(IslCtxs.back(), IdName.c_str(), nullptr);
 
   bool isApproximated =
       Stmt->isRegionStmt() && (Stmt->getRegion()->getEntry() != BB);
   if (isApproximated && Type == MemoryAccess::MUST_WRITE)
     Type = MemoryAccess::MAY_WRITE;
 
   AccList.emplace_back(Stmt, Inst, Id, Type, BaseAddress, ElemBytes, Affine,
                        Subscripts, Sizes, AccessValue, Origin, BaseName);
   Stmt->addAccess(&AccList.back());
 }
 
-void ScopInfo::addExplicitAccess(
-    Instruction *MemAccInst, MemoryAccess::AccessType Type, Value *BaseAddress,
-    unsigned ElemBytes, bool IsAffine, ArrayRef<const SCEV *> Subscripts,
-    ArrayRef<const SCEV *> Sizes, Value *AccessValue) {
+void ScopInfo::addExplicitAccess(Scop &S, Instruction *MemAccInst,
+                                 MemoryAccess::AccessType Type,
+                                 Value *BaseAddress, unsigned ElemBytes,
+                                 bool IsAffine,
+                                 ArrayRef<const SCEV *> Subscripts,
+                                 ArrayRef<const SCEV *> Sizes,
+                                 Value *AccessValue) {
   assert(isa<LoadInst>(MemAccInst) || isa<StoreInst>(MemAccInst));
   assert(isa<LoadInst>(MemAccInst) == (Type == MemoryAccess::READ));
-  addMemoryAccess(MemAccInst->getParent(), MemAccInst, Type, BaseAddress,
+  addMemoryAccess(S, MemAccInst->getParent(), MemAccInst, Type, BaseAddress,
                   ElemBytes, IsAffine, AccessValue, Subscripts, Sizes,
                   MemoryAccess::EXPLICIT);
 }
-void ScopInfo::addScalarWriteAccess(Instruction *Value) {
-  addMemoryAccess(Value->getParent(), Value, MemoryAccess::MUST_WRITE, Value, 1,
-                  true, Value, ArrayRef<const SCEV *>(),
+void ScopInfo::addScalarWriteAccess(Scop &S, Instruction *Value) {
+  addMemoryAccess(S, Value->getParent(), Value, MemoryAccess::MUST_WRITE, Value,
+                  1, true, Value, ArrayRef<const SCEV *>(),
                   ArrayRef<const SCEV *>(), MemoryAccess::SCALAR);
 }
-void ScopInfo::addScalarReadAccess(Value *Value, Instruction *User) {
+void ScopInfo::addScalarReadAccess(Scop &S, Value *Value, Instruction *User) {
   assert(!isa<PHINode>(User));
-  addMemoryAccess(User->getParent(), User, MemoryAccess::READ, Value, 1, true,
-                  Value, ArrayRef<const SCEV *>(), ArrayRef<const SCEV *>(),
-                  MemoryAccess::SCALAR);
+  addMemoryAccess(S, User->getParent(), User, MemoryAccess::READ, Value, 1,
+                  true, Value, ArrayRef<const SCEV *>(),
+                  ArrayRef<const SCEV *>(), MemoryAccess::SCALAR);
 }
-void ScopInfo::addScalarReadAccess(Value *Value, PHINode *User,
+void ScopInfo::addScalarReadAccess(Scop &S, Value *Value, PHINode *User,
                                    BasicBlock *UserBB) {
-  addMemoryAccess(UserBB, User, MemoryAccess::READ, Value, 1, true, Value,
+  addMemoryAccess(S, UserBB, User, MemoryAccess::READ, Value, 1, true, Value,
                   ArrayRef<const SCEV *>(), ArrayRef<const SCEV *>(),
                   MemoryAccess::SCALAR);
 }
-void ScopInfo::addPHIWriteAccess(PHINode *PHI, BasicBlock *IncomingBlock,
+void ScopInfo::addPHIWriteAccess(Scop &S, PHINode *PHI,
+                                 BasicBlock *IncomingBlock,
                                  Value *IncomingValue, bool IsExitBlock) {
-  addMemoryAccess(IncomingBlock, IncomingBlock->getTerminator(),
+  addMemoryAccess(S, IncomingBlock, IncomingBlock->getTerminator(),
                   MemoryAccess::MUST_WRITE, PHI, 1, true, IncomingValue,
                   ArrayRef<const SCEV *>(), ArrayRef<const SCEV *>(),
                   IsExitBlock ? MemoryAccess::SCALAR : MemoryAccess::PHI);
 }
-void ScopInfo::addPHIReadAccess(PHINode *PHI) {
-  addMemoryAccess(PHI->getParent(), PHI, MemoryAccess::READ, PHI, 1, true, PHI,
-                  ArrayRef<const SCEV *>(), ArrayRef<const SCEV *>(),
+void ScopInfo::addPHIReadAccess(Scop &S, PHINode *PHI) {
+  addMemoryAccess(S, PHI->getParent(), PHI, MemoryAccess::READ, PHI, 1, true,
+                  PHI, ArrayRef<const SCEV *>(), ArrayRef<const SCEV *>(),
                   MemoryAccess::PHI);
 }
 
-void ScopInfo::buildScop(Region &R, DominatorTree &DT) {
+Scop *ScopInfo::buildScop(Region &R, DominatorTree &DT) {
+
+  isl_ctx *Ctx = isl_ctx_alloc();
+  isl_options_set_on_error(Ctx, ISL_ON_ERROR_ABORT);
+  IslCtxs.push_back(Ctx);
+
   unsigned MaxLoopDepth = getMaxLoopDepthInRegion(R, *LI, *SD);
-  scop = new Scop(R, AccFuncMap, *SD, *SE, DT, *LI, ctx, MaxLoopDepth);
+  Scop *S = new Scop(R, AccFuncMap, *SD, *SE, DT, *LI, Ctx, MaxLoopDepth);
 
-  buildStmts(R);
-  buildAccessFunctions(R, R);
+  buildStmts(*S, R);
+  buildAccessFunctions(*S, 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 (!R.getExitingBlock())
-    buildAccessFunctions(R, *R.getExit(), nullptr, /* IsExitBlock */ true);
+    buildAccessFunctions(*S, *R.getExit(), nullptr, /* IsExitBlock */ true);
 
-  scop->init(*AA);
+  S->init(*AA);
+  return S;
 }
 
-void ScopInfo::print(raw_ostream &OS, const Module *) const {
-  if (!scop) {
-    OS << "Invalid Scop!\n";
-    return;
-  }
+bool ScopInfo::runOnFunction(Function &F) {
+  SD = &getAnalysis<ScopDetection>();
+
+  SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
+  LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
+  AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
+  TD = &F.getParent()->getDataLayout();
+  DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
 
-  scop->print(OS);
+  for (ScopDetection::iterator I = SD->begin(), E = SD->end(); I != E; ++I) {
+    const Region *R = *I;
+    if (!SD->isMaxRegionInScop(*R))
+      continue;
+
+    Scop *S = buildScop(const_cast<Region &>(*R), DT);
+    DEBUG(S->print(dbgs()));
+
+    if (!S->hasFeasibleRuntimeContext()) {
+      delete S;
+      continue;
     }
 
-void ScopInfo::clear() {
-  AccFuncMap.clear();
-  if (scop) {
-    delete scop;
-    scop = 0;
+    Scops.push_back(S);
+
+    // Statistics.
+    ++ScopFound;
+    if (S->getMaxLoopDepth() > 0)
+      ++RichScopFound;
   }
+  return false;
 }
 
-//===----------------------------------------------------------------------===//
-ScopInfo::ScopInfo() : RegionPass(ID), scop(0) {
-  ctx = isl_ctx_alloc();
-  isl_options_set_on_error(ctx, ISL_ON_ERROR_ABORT);
+void ScopInfo::print(raw_ostream &OS, const Module *) const {
+  for (const Scop *S : *this)
+    S->print(OS);
+}
+
+void ScopInfo::releaseMemory() {
+  AccFuncMap.clear();
+
+  for (const Scop *S : *this)
+    delete S;
+  Scops.clear();
 }
 
 ScopInfo::~ScopInfo() {
-  clear();
-  isl_ctx_free(ctx);
+  releaseMemory();
+
+  for (isl_ctx *Ctx : IslCtxs)
+    isl_ctx_free(Ctx);
+  IslCtxs.clear();
 }
 
 void ScopInfo::getAnalysisUsage(AnalysisUsage &AU) const {
+  AU.addRequiredTransitive<RegionInfoPass>();
   AU.addRequired<LoopInfoWrapperPass>();
-  AU.addRequired<RegionInfoPass>();
   AU.addRequired<DominatorTreeWrapperPass>();
   AU.addRequiredTransitive<ScalarEvolutionWrapperPass>();
   AU.addRequiredTransitive<ScopDetection>();
   AU.addRequired<AAResultsWrapperPass>();
   AU.setPreservesAll();
 }
 
-bool ScopInfo::runOnRegion(Region *R, RGPassManager &RGM) {
-  SD = &getAnalysis<ScopDetection>();
-
-  if (!SD->isMaxRegionInScop(*R))
-    return false;
-
-  Function *F = R->getEntry()->getParent();
-  SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
-  LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
-  AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
-  TD = &F->getParent()->getDataLayout();
-  DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
-
-  buildScop(*R, DT);
-
-  DEBUG(scop->print(dbgs()));
-
-  if (scop->isEmpty() || !scop->hasFeasibleRuntimeContext()) {
-    delete scop;
-    scop = nullptr;
-    return false;
-  }
-
-  // Statistics.
-  ++ScopFound;
-  if (scop->getMaxLoopDepth() > 0)
-    ++RichScopFound;
-  return false;
-}
-
 char ScopInfo::ID = 0;
 
 Pass *polly::createScopInfoPass() { return new ScopInfo(); }
 
 INITIALIZE_PASS_BEGIN(ScopInfo, "polly-scops",
                       "Polly - Create polyhedral description of Scops", false,
                       false);
 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass);
 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",
                     "Polly - Create polyhedral description of Scops", false,
                     false)

lib/Analysis/ScopPass.cpp

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

lib/CodeGen/BlockGenerators.cpp

if (Inst && isa<PHINode>(Inst))
       continue;
 
     ValueMapT EmptyMap;
     Builder.CreateStore(Array->getBasePtr(),
                         getOrCreateScalarAlloca(Array->getBasePtr()));
   }
 }
 
-void BlockGenerator::createScalarFinalization(Region &R) {
+void BlockGenerator::createScalarFinalization(Region &R,
+                                              ValueMapT &InterScopMap) {
   // The exit block of the __unoptimized__ region.
   BasicBlock *ExitBB = R.getExitingBlock();
   // The merge block __just after__ the region and the optimized region.
   BasicBlock *MergeBB = R.getExit();
 
   // The exit block of the __optimized__ region.
   BasicBlock *OptExitBB = *(pred_begin(MergeBB));
   if (OptExitBB == ExitBB)
PHINode *MergePHI = PHINode::Create(EscapeInst->getType(), 2,
                                         EscapeInst->getName() + ".merge");
     MergePHI->insertBefore(MergeBB->getFirstInsertionPt());
 
     // Add the respective values to the merge PHI.
     MergePHI->addIncoming(EscapeInstReload, OptExitBB);
     MergePHI->addIncoming(EscapeInst, ExitBB);
 
     // The information of scalar evolution about the escaping instruction needs
-    // to be revoked so the new merged instruction will be used.
-    if (SE.isSCEVable(EscapeInst->getType()))
+    // to be updated so the new merged instruction will be used in other SCoPs.
+    if (SE.isSCEVable(EscapeInst->getType())) {
       SE.forgetValue(EscapeInst);
+      InterScopMap[EscapeInst] = MergePHI;
+    }
 
     // Replace all uses of the demoted instruction with the merge PHI.
     for (Instruction *EUser : EscapeUsers)
       EUser->replaceUsesOfWith(EscapeInst, MergePHI);
   }
 }
 
 void BlockGenerator::findOutsideUsers(Scop &S) {
for (auto &Pair : S.arrays()) {
     MergePHI->insertBefore(MergeBB->getFirstInsertionPt());
     MergePHI->addIncoming(Reload, OptExitBB);
     MergePHI->addIncoming(OriginalValue, ExitBB);
     int Idx = PHI->getBasicBlockIndex(MergeBB);
     PHI->setIncomingValue(Idx, MergePHI);
   }
 }
 
-void BlockGenerator::finalizeSCoP(Scop &S) {
+void BlockGenerator::finalizeSCoP(Scop &S, ValueMapT &VMap) {
   findOutsideUsers(S);
   createScalarInitialization(S);
   createExitPHINodeMerges(S);
-  createScalarFinalization(S.getRegion());
+  createScalarFinalization(S.getRegion(), VMap);
 }
 
 VectorBlockGenerator::VectorBlockGenerator(BlockGenerator &BlockGen,
                                            std::vector<LoopToScevMapT> &VLTS,
                                            isl_map *Schedule)
     : BlockGenerator(BlockGen), VLTS(VLTS), Schedule(Schedule) {
   assert(Schedule && "No statement domain provided");
 }

lib/CodeGen/CodeGeneration.cpp

 #include "polly/DependenceInfo.h"
 #include "polly/LinkAllPasses.h"
 #include "polly/ScopInfo.h"
 #include "polly/Support/ScopHelper.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/BasicAliasAnalysis.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/PostDominators.h"
+#include "llvm/Analysis/RegionInfo.h"
 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/Verifier.h"
 #include "llvm/Support/Debug.h"
 
 using namespace polly;
 using namespace llvm;
 
public:
   ///{
   LoopInfo *LI;
   IslAstInfo *AI;
   DominatorTree *DT;
   ScalarEvolution *SE;
   RegionInfo *RI;
   ///}
 
+  /// @brief Mapping from escaping scevable values to the new merged ones.
+  ///
+  /// We build code for the SCoPs in a function one after another, thus there
+  /// can be a use in a later SCoP of a value defined in a former one. In such
+  /// cases we map the used value to the merged value at the end of the
+  /// optimized former region. This is necessary because we cache SCEVs in the
+  /// later SCoPs that would otherwise reference value that do not dominate the
+  /// later SCoP any more.
+  ValueMapT InterScopMap;
+
   /// @brief Build the runtime condition.
   ///
   /// Build the condition that evaluates at run-time to true iff all
   /// assumptions taken for the SCoP hold, and to false otherwise.
   ///
   /// @return A value evaluating to true/false if execution is save/unsafe.
-  Value *buildRTC(PollyIRBuilder &Builder, IslExprBuilder &ExprBuilder) {
+  Value *buildRTC(Scop &S, PollyIRBuilder &Builder,
+                  IslExprBuilder &ExprBuilder) {
     Builder.SetInsertPoint(Builder.GetInsertBlock()->getTerminator());
-    Value *RTC = ExprBuilder.create(AI->getRunCondition());
+    Value *RTC = ExprBuilder.create(AI->getRunCondition(S));
     if (!RTC->getType()->isIntegerTy(1))
       RTC = Builder.CreateIsNotNull(RTC);
     return RTC;
   }
 
   bool verifyGeneratedFunction(Scop &S, Function &F) {
     if (!verifyFunction(F))
       return false;
for (BasicBlock &BB : *F) {
         continue;
 
       RI->setRegionFor(&BB, ParentRegion);
     }
   }
 
   /// @brief Generate LLVM-IR for the SCoP @p S.
   bool runOnScop(Scop &S) override {
-    AI = &getAnalysis<IslAstInfo>();
 
     // Check if we created an isl_ast root node, otherwise exit.
-    isl_ast_node *AstRoot = AI->getAst();
+    isl_ast_node *AstRoot = AI->getAst(S);
     if (!AstRoot)
       return false;
 
-    LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
-    DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
-    SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
-    DL = &S.getRegion().getEntry()->getParent()->getParent()->getDataLayout();
-    RI = &getAnalysis<RegionInfoPass>().getRegionInfo();
     Region *R = &S.getRegion();
     assert(!R->isTopLevelRegion() && "Top level regions are not supported");
 
     ScopAnnotator Annotator;
     Annotator.buildAliasScopes(S);
 
     simplifyRegion(R, DT, LI, RI);
     assert(R->isSimple());
     BasicBlock *EnteringBB = S.getRegion().getEnteringBlock();
     assert(EnteringBB);
     PollyIRBuilder Builder = createPollyIRBuilder(EnteringBB, Annotator);
 
-    IslNodeBuilder NodeBuilder(Builder, Annotator, this, *DL, *LI, *SE, *DT, S);
+    DL = &S.getRegion().getEntry()->getParent()->getParent()->getDataLayout();
+    IslNodeBuilder NodeBuilder(Builder, Annotator, this, *DL, *LI, *SE, *DT, S,
+                               InterScopMap);
 
     // Only build the run-time condition and parameters _after_ having
     // introduced the conditional branch. This is important as the conditional
     // branch will guard the original scop from new induction variables that
     // the SCEVExpander may introduce while code generating the parameters and
     // which may introduce scalar dependences that prevent us from correctly
     // code generating this scop.
     BasicBlock *StartBlock =
         executeScopConditionally(S, this, Builder.getTrue());
     auto SplitBlock = StartBlock->getSinglePredecessor();
 
     // First generate code for the hoisted invariant loads and transitively the
     // parameters they reference. Afterwards, for the remaining parameters that
     // might reference the hoisted loads. Finally, build the runtime check
     // that might reference both hoisted loads as well as parameters.
     Builder.SetInsertPoint(SplitBlock->getTerminator());
     NodeBuilder.preloadInvariantLoads();
     NodeBuilder.addParameters(S.getContext());
 
-    Value *RTC = buildRTC(Builder, NodeBuilder.getExprBuilder());
+    Value *RTC = buildRTC(S, Builder, NodeBuilder.getExprBuilder());
     Builder.GetInsertBlock()->getTerminator()->setOperand(0, RTC);
     Builder.SetInsertPoint(StartBlock->begin());
 
     NodeBuilder.create(AstRoot);
 
     NodeBuilder.finalizeSCoP(S);
     fixRegionInfo(EnteringBB->getParent(), R->getParent());
 
     assert(!verifyGeneratedFunction(S, *EnteringBB->getParent()) &&
            "Verification of generated function failed");
     return true;
   }
 
+  /// @brief Initializer called once per function.
+  void initializeScopPass() override {
+    AI = &getAnalysis<IslAstInfo>();
+    LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
+    DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
+    SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
+    RI = &getAnalysis<RegionInfoPass>().getRegionInfo();
+  }
+
   /// @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<LoopInfoWrapperPass>();
+    AU.addRequiredTransitive<ScopInfo>();
 
     AU.addPreserved<DependenceInfo>();
 
     AU.addPreserved<AAResultsWrapperPass>();
     AU.addPreserved<BasicAAWrapperPass>();
     AU.addPreserved<LoopInfoWrapperPass>();
     AU.addPreserved<DominatorTreeWrapperPass>();
     AU.addPreserved<GlobalsAAWrapperPass>();

lib/CodeGen/IslAst.cpp

 }
 
 __isl_give isl_ast_node *IslAst::getAst() { return isl_ast_node_copy(Root); }
 __isl_give isl_ast_expr *IslAst::getRunCondition() {
   return isl_ast_expr_copy(RunCondition);
 }
 
 void IslAstInfo::releaseMemory() {
-  if (Ast) {
-    delete Ast;
-    Ast = nullptr;
-  }
-}
-
-bool IslAstInfo::runOnScop(Scop &Scop) {
-  if (Ast)
-    delete Ast;
+  DeleteContainerSeconds(AstMap);
+  AstMap.clear();
 
-  S = &Scop;
+void IslAstInfo::initializeScopPass() { DI = &getAnalysis<DependenceInfo>(); }
 
-  const Dependences &D = getAnalysis<DependenceInfo>().getDependences();
+bool IslAstInfo::runOnScop(Scop &S) {
 
-  Ast = IslAst::create(&Scop, D);
+  const Dependences &D = DI->getDependences(S);
+  AstMap[&S] = IslAst::create(&S, D);
 
-  DEBUG(printScop(dbgs(), Scop));
+  DEBUG(printScop(dbgs(), S));
   return false;
 }
 
-__isl_give isl_ast_node *IslAstInfo::getAst() const { return Ast->getAst(); }
-__isl_give isl_ast_expr *IslAstInfo::getRunCondition() const {
-  return Ast->getRunCondition();
+__isl_give isl_ast_node *IslAstInfo::getAst(Scop &S) const {
+  IslAst *AST = AstMap.lookup(&S);
+  assert(AST && "AST for given SCoP not found!");
+  return AST->getAst();
+}
+
+__isl_give isl_ast_expr *IslAstInfo::getRunCondition(Scop &S) const {
+  IslAst *AST = AstMap.lookup(&S);
+  assert(AST && "AST for given SCoP not found!");
+  return AST->getRunCondition();
 }
 
 IslAstUserPayload *IslAstInfo::getNodePayload(__isl_keep isl_ast_node *Node) {
   isl_id *Id = isl_ast_node_get_annotation(Node);
   if (!Id)
     return nullptr;
   IslAstUserPayload *Payload = (IslAstUserPayload *)isl_id_get_user(Id);
   isl_id_free(Id);

 
 isl_ast_build *IslAstInfo::getBuild(__isl_keep isl_ast_node *Node) {
   IslAstUserPayload *Payload = getNodePayload(Node);
   return Payload ? Payload->Build : nullptr;
 }
 
 void IslAstInfo::printScop(raw_ostream &OS, Scop &S) const {
   isl_ast_print_options *Options;
-  isl_ast_node *RootNode = getAst();
+  isl_ast_node *RootNode = getAst(S);
   Function *F = S.getRegion().getEntry()->getParent();
 
   OS << ":: isl ast :: " << F->getName() << " :: " << S.getRegion().getNameStr()
      << "\n";
 
   if (!RootNode) {
     OS << ":: isl ast generation and code generation was skipped!\n\n";
     OS << ":: This is either because no useful optimizations could be applied "
           "(use -polly-process-unprofitable to enforce code generation) or "
           "because earlier passes such as dependence analysis timed out (use "
           "-polly-dependences-computeout=0 to set dependence analysis timeout "
           "to infinity)\n\n";
     return;
   }
 
-  isl_ast_expr *RunCondition = getRunCondition();
+  isl_ast_expr *RunCondition = getRunCondition(S);
   char *RtCStr, *AstStr;
 
   Options = isl_ast_print_options_alloc(S.getIslCtx());
   Options = isl_ast_print_options_set_print_for(Options, cbPrintFor, nullptr);
 
   isl_printer *P = isl_printer_to_str(S.getIslCtx());
   P = isl_printer_print_ast_expr(P, RunCondition);
   RtCStr = isl_printer_get_str(P);
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<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(DependenceInfo);
 INITIALIZE_PASS_END(IslAstInfo, "polly-ast",
                     "Polly - Generate an AST from the SCoP (isl)", false, false)

lib/CodeGen/IslExprBuilder.cpp

 //===------ IslExprBuilder.cpp ----- Code generate isl AST expressions ----===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 //===----------------------------------------------------------------------===//
 
 #include "polly/CodeGen/IslExprBuilder.h"
 #include "polly/ScopInfo.h"
 #include "polly/Support/GICHelper.h"
 #include "polly/Support/ScopHelper.h"
+
+#include "llvm/Analysis/ScalarEvolutionExpander.h"
+#include "llvm/IR/Dominators.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 
 using namespace llvm;
 using namespace polly;
 
 Type *IslExprBuilder::getWidestType(Type *T1, Type *T2) {
   assert(isa<IntegerType>(T1) && isa<IntegerType>(T2));

lib/CodeGen/IslNodeBuilder.cpp

 #include "polly/ScopInfo.h"
 #include "polly/Support/GICHelper.h"
 #include "polly/Support/SCEVValidator.h"
 #include "polly/Support/ScopHelper.h"
 #include "llvm/ADT/PostOrderIterator.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/PostDominators.h"
+#include "llvm/Analysis/RegionInfo.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/Verifier.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 #include "isl/aff.h"
 #include "isl/ast.h"

lib/Exchange/JSONExporter.cpp

struct JSONExporter : public ScopPass {
   /// @brief Export the SCoP @p S to a JSON file.
   bool runOnScop(Scop &S) override;
 
   /// @brief Print the SCoP @p S as it is exported.
   void printScop(raw_ostream &OS, Scop &S) const override;
 
   /// @brief Register all analyses and transformation required.
   void getAnalysisUsage(AnalysisUsage &AU) const override;
+
+  /// @brief Initializer called once per function.
+  void initializeScopPass() override {}
 };
 
 struct JSONImporter : public ScopPass {
   static char ID;
   std::vector<std::string> newAccessStrings;
   explicit JSONImporter() : ScopPass(ID) {}
 
   std::string getFileName(Scop &S) const;
 
   /// @brief Import new access functions for SCoP @p S from a JSON file.
   bool runOnScop(Scop &S) override;
 
   /// @brief Print the SCoP @p S and the imported access functions.
   void printScop(raw_ostream &OS, Scop &S) const override;
 
   /// @brief Register all analyses and transformation required.
   void getAnalysisUsage(AnalysisUsage &AU) const override;
+
+  /// @brief Initializer called once per function.
+  void initializeScopPass() override {}
 };
 }
 
 char JSONExporter::ID = 0;
 std::string JSONExporter::getFileName(Scop &S) const {
   std::string FunctionName = S.getRegion().getEntry()->getParent()->getName();
   std::string FileName = FunctionName + "___" + S.getNameStr() + ".jscop";
   return FileName;
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.addRequiredTransitive<ScopInfo>();
 }
 
 Pass *polly::createJSONExporterPass() { return new JSONExporter(); }
 
 char JSONImporter::ID = 0;
 std::string JSONImporter::getFileName(Scop &S) const {
   std::string FunctionName = S.getRegion().getEntry()->getParent()->getName();
   std::string FileName = FunctionName + "___" + S.getNameStr() + ".jscop";
for (std::vector<std::string>::const_iterator I = newAccessStrings.begin(),
        I != E; I++)
     OS << "New access function '" << *I << "'detected in JSCOP file\n";
 }
 
 typedef Dependences::StatementToIslMapTy StatementToIslMapTy;
 
 bool JSONImporter::runOnScop(Scop &S) {
   Region &R = S.getRegion();
-  const Dependences &D = getAnalysis<DependenceInfo>().getDependences();
+  const Dependences &D = getAnalysis<DependenceInfo>().getDependences(S);
   const DataLayout &DL =
       S.getRegion().getEntry()->getParent()->getParent()->getDataLayout();
 
   std::string FileName = ImportDir + "/" + getFileName(S);
 
   std::string FunctionName = R.getEntry()->getParent()->getName();
   errs() << "Reading JScop '" << R.getNameStr() << "' in function '"
          << FunctionName << "' from '" << FileName << "'.\n";

lib/Support/SCEVAffinator.cpp

 //
 //===----------------------------------------------------------------------===//
 
 #include "polly/Support/SCEVAffinator.h"
 #include "polly/ScopInfo.h"
 #include "polly/Support/GICHelper.h"
 #include "polly/Support/SCEVValidator.h"
 #include "polly/Support/ScopHelper.h"
+#include "llvm/Analysis/RegionInfo.h"
 #include "isl/aff.h"
 #include "isl/local_space.h"
 #include "isl/set.h"
 #include "isl/val.h"
 
 using namespace llvm;
 using namespace polly;
 

lib/Transform/DeadCodeElimination.cpp

 class DeadCodeElim : public ScopPass {
 public:
   static char ID;
   explicit DeadCodeElim() : ScopPass(ID) {}
 
   /// @brief Remove dead iterations from the schedule of @p S.
   bool runOnScop(Scop &S) override;
 
+  /// @brief Initializer called once per function.
+  void initializeScopPass() override;
+
   /// @brief Register all analyses and transformation required.
   void getAnalysisUsage(AnalysisUsage &AU) const override;
 
 private:
+  /// @brief The dependence info pass.
+  DependenceInfo *DI;
+
   /// @brief Return the set of live iterations.
   ///
   /// The set of live iterations are all iterations that write to memory and for
   /// which we can not prove that there will be a later write that _must_
   /// overwrite the same memory location and is consequently the only one that
   /// is visible after the execution of the SCoP.
   ///
   isl_union_set *getLiveOut(Scop &S);

 /// o Following each RAW dependency from a live iteration backwards and adding
 ///   that iteration to the live set.
 ///
 /// To ensure the set of live iterations does not get too complex we always
 /// combine a certain number of precise steps with one approximating step that
 /// simplifies the life set with an affine hull.
 bool DeadCodeElim::eliminateDeadCode(Scop &S, int PreciseSteps) {
   DependenceInfo &DI = getAnalysis<DependenceInfo>();
-  const Dependences &D = DI.getDependences();
+  const Dependences &D = DI.getDependences(S);
 
   if (!D.hasValidDependences())
     return false;
 
   isl_union_set *Live = getLiveOut(S);
   isl_union_map *Dep =
       D.getDependences(Dependences::TYPE_RAW | Dependences::TYPE_RED);
   Dep = isl_union_map_reverse(Dep);
while (true) {
 
     Live = isl_union_set_intersect(Live, isl_union_set_copy(OriginalDomain));
   }
   isl_union_map_free(Dep);
   isl_union_set_free(OriginalDomain);
 
   bool Changed = S.restrictDomains(isl_union_set_coalesce(Live));
 
-  // FIXME: We can probably avoid the recomputation of all dependences by
+  // FIXME: We can probably avoid the recomputation of all DependenceInfo by
   // updating them explicitly.
   if (Changed)
-    DI.recomputeDependences();
+    DI.recomputeDependences(S);
   return Changed;
 }
 
+void DeadCodeElim::initializeScopPass() { DI = &getAnalysis<DependenceInfo>(); }
+
 bool DeadCodeElim::runOnScop(Scop &S) {
   return eliminateDeadCode(S, DCEPreciseSteps);
 }
 
 void DeadCodeElim::getAnalysisUsage(AnalysisUsage &AU) const {
   ScopPass::getAnalysisUsage(AU);
   AU.addRequired<DependenceInfo>();
 }

lib/Transform/ScheduleOptimizer.cpp

public:
   static char ID;
   explicit IslScheduleOptimizer() : ScopPass(ID) { LastSchedule = nullptr; }
 
   ~IslScheduleOptimizer() { isl_schedule_free(LastSchedule); }
 
   /// @brief Optimize the schedule of the SCoP @p S.
   bool runOnScop(Scop &S) override;
 
+  /// @brief Initializer called once per function.
+  void initializeScopPass() override;
+
   /// @brief Print the new schedule for the SCoP @p S.
   void printScop(raw_ostream &OS, Scop &S) const override;
 
   /// @brief Register all analyses and transformation required.
   void getAnalysisUsage(AnalysisUsage &AU) const override;
 
   /// @brief Release the internal memory.
   void releaseMemory() override {
     isl_schedule_free(LastSchedule);
     LastSchedule = nullptr;
   }
 
 private:
   isl_schedule *LastSchedule;
+
+  /// @brief The dependence info pass.
+  DependenceInfo *DI;
 };
 }
 
 char IslScheduleOptimizer::ID = 0;
 
+void IslScheduleOptimizer::initializeScopPass() {
+  DI = &getAnalysis<DependenceInfo>();
+}
+
 bool IslScheduleOptimizer::runOnScop(Scop &S) {
 
   // Skip empty SCoPs but still allow code generation as it will delete the
   // loops present but not needed.
   if (S.getSize() == 0) {
     S.markAsOptimized();
     return false;
   }
 
-  const Dependences &D = getAnalysis<DependenceInfo>().getDependences();
-
+  const Dependences &D = DI->getDependences(S);
   if (!D.hasValidDependences())
     return false;
 
   isl_schedule_free(LastSchedule);
   LastSchedule = nullptr;
 
   // Build input data.
   int ValidityKinds =

test/DependenceInfo/computeout.ll

S3:
   %indvar.next.3 = add i64 %indvar.3, 1
   %exitcond.3 = icmp ne i64 %indvar.next.3, 200
   br i1 %exitcond.3, label %S3 , label %exit.3
 
 exit.3:
   ret void
 }
 
-; VALUE: region: 'S1 => exit.3' in function 'sequential_writes':
+; VALUE: function 'sequential_writes'
+; VALUE: for region: S1 => exit.3
 ; VALUE:   RAW dependences:
 ; VALUE:     {  }
 ; VALUE:   WAR dependences:
 ; VALUE:     {  }
 ; VALUE:   WAW dependences:
 ; VALUE:     {
 ; VALUE:       Stmt_S1[i0] -> Stmt_S2[i0] : i0 <= 9 and i0 >= 0;
 ; VALUE:       Stmt_S2[i0] -> Stmt_S3[i0] : i0 <= 9 and i0 >= 0;
 ; VALUE:       Stmt_S1[i0] -> Stmt_S3[i0] : i0 <= 99 and i0 >= 10
 ; VALUE:     }
 
-; TIMEOUT: region: 'S1 => exit.3' in function 'sequential_writes':
+; TIMEOUT: function 'sequential_writes'
+; TIMEOUT: for region: S1 => exit.3
 ; TIMEOUT:   RAW dependences:
 ; TIMEOUT:     n/a
 ; TIMEOUT:   WAR dependences:
 ; TIMEOUT:     n/a
 ; TIMEOUT:   WAW dependences:
 ; TIMEOUT:     n/a

test/DependenceInfo/sequential_loops.ll

S3:
   %indvar.next.3 = add i64 %indvar.3, 1
   %exitcond.3 = icmp ne i64 %indvar.next.3, 200
   br i1 %exitcond.3, label %S3 , label %exit.3
 
 exit.3:
   ret void
 }
 
-; VALUE-LABEL: region: 'S1 => exit.3' in function 'sequential_writes':
+; VALUE: for function 'sequential_writes'
+; VALUE: region: S1 => exit.3
 ; VALUE:   RAW dependences:
 ; VALUE:     {  }
 ; VALUE:   WAR dependences:
 ; VALUE:     {  }
 ; VALUE:   WAW dependences:
 ; VALUE:     {
 ; VALUE:       Stmt_S1[i0] -> Stmt_S2[i0] : i0 <= 9 and i0 >= 0;
 ; VALUE:       Stmt_S2[i0] -> Stmt_S3[i0] : i0 <= 9 and i0 >= 0;
 ; VALUE:       Stmt_S1[i0] -> Stmt_S3[i0] : i0 <= 99 and i0 >= 10
 ; VALUE:     }
 
-; MEMORY-LABEL: region: 'S1 => exit.3' in function 'sequential_writes':
+; MEMORY: for function 'sequential_writes'
+; MEMORY: region: S1 => exit.3
 ; MEMORY:   RAW dependences:
 ; MEMORY:     {  }
 ; MEMORY:   WAR dependences:
 ; MEMORY:     {  }
 ; MEMORY:   WAW dependences:
 ; MEMORY:     {
 ; MEMORY:       Stmt_S1[i0] -> Stmt_S2[i0] : i0 <= 9 and i0 >= 0;
 ; MEMORY:       Stmt_S2[i0] -> Stmt_S3[i0] : i0 <= 9 and i0 >= 0;
S3:
   %indvar.next.3 = add i64 %indvar.3, 1
   %exitcond.3 = icmp ne i64 %indvar.next.3, 200
   br i1 %exitcond.3, label %S3 , label %exit.3
 
 exit.3:
   ret void
 }
 
-; VALUE-LABEL: region: 'S1 => exit.3' in function 'read_after_writes':
+; VALUE: for function 'read_after_writes'
+; VALUE: region: S1 => exit.3
 ; VALUE:   RAW dependences:
 ; VALUE:     {
 ; VALUE:       Stmt_S2[i0] -> Stmt_S3[i0] : i0 <= 9 and i0 >= 0;
 ; VALUE:       Stmt_S1[i0] -> Stmt_S3[i0] : i0 <= 99 and i0 >= 10
 ; VALUE:     }
 ; VALUE:   WAR dependences:
 ; VALUE:     {  }
 ; VALUE:   WAW dependences:
 ; VALUE:     {
 ; VALUE:       Stmt_S1[i0] -> Stmt_S2[i0] : i0 <= 9 and i0 >= 0
 ; VALUE:     }
 
-; MEMORY-LABEL: region: 'S1 => exit.3' in function 'read_after_writes':
+; MEMORY: for function 'read_after_writes'
+; MEMORY: region: S1 => exit.3
 ; MEMORY:   RAW dependences:
 ; MEMORY:     {
 ; MEMORY:       Stmt_S2[i0] -> Stmt_S3[i0] : i0 <= 9 and i0 >= 0;
 ; MEMORY:       Stmt_S1[i0] -> Stmt_S3[i0] : i0 <= 99 and i0 >= 0
 ; MEMORY:     }
 ; MEMORY:   WAR dependences:
 ; MEMORY:     {  }
 ; MEMORY:   WAW dependences:
S3:
   %indvar.next.3 = add i64 %indvar.3, 1
   %exitcond.3 = icmp ne i64 %indvar.next.3, 200
   br i1 %exitcond.3, label %S3 , label %exit.3
 
 exit.3:
   ret void
 }
 
-; VALUE-LABEL: region: 'S1 => exit.3' in function 'write_after_read':
+; VALUE: for function 'write_after_read'
+; VALUE: region: S1 => exit.3
 ; VALUE:   RAW dependences:
 ; VALUE:     {
 ; VALUE:     }
 ; VALUE:   WAR dependences:
 ; VALUE:     {
 ; VALUE:       Stmt_S1[i0] -> Stmt_S2[i0] : i0 <= 9 and i0 >= 0;
 ; VALUE:       Stmt_S1[i0] -> Stmt_S3[i0] : i0 <= 99 and i0 >= 10
 ; VALUE:     }
 ; VALUE:   WAW dependences:
 ; VALUE:     {
 ; VALUE:       Stmt_S2[i0] -> Stmt_S3[i0] : i0 <= 9 and i0 >= 0
 ; VALUE:     }
 
-; MEMORY-LABEL: region: 'S1 => exit.3' in function 'write_after_read':
+; MEMORY: for function 'write_after_read'
+; MEMORY: region: S1 => exit.3
 ; MEMORY:   RAW dependences:
 ; MEMORY:     {
 ; MEMORY:     }
 ; MEMORY:   WAR dependences:
 ; MEMORY:     {
 ; MEMORY:        Stmt_S1[i0] -> Stmt_S2[i0] : i0 <= 9 and i0 >= 0;
 ; MEMORY:        Stmt_S1[i0] -> Stmt_S3[i0] : i0 <= 99 and i0 >= 0
 ; MEMORY:     }
S2:
   %indvar.next.2 = add i64 %indvar.2, 1
   %exitcond.2 = icmp ne i64 %indvar.next.2, 10
   br i1 %exitcond.2, label %S2, label %exit.2
 
 exit.2:
   ret void
 }
 
-; VALUE: region: 'S1 => exit.2' in function 'parametric_offset':
+; VALUE: for function 'parametric_offset'
+; VALUE: region: S1 => exit.2
 ; VALUE:   RAW dependences:
 ; VALUE:     [p] -> {
 ; VALUE:       Stmt_S1[i0] -> Stmt_S2[-p + i0] :
 ; VALUE-DAG:           i0 >= p
 ; VALUE-DAG:           i0 <= 9 + p
 ; VALUE-DAG:           i0 <= 99
 ; VALUE-DAG:           i0 >= 0
 ; VALUE:     }
 ; VALUE:   WAR dependences:
 ; VALUE:     [p] -> {
 ; VALUE:     }
 ; VALUE:   WAW dependences:
 ; VALUE:     [p] -> {
 ; VALUE:     }
 
-; MEMORY: region: 'S1 => exit.2' in function 'parametric_offset':
+; MEMORY: for function 'parametric_offset'
+; MEMORY: region: S1 => exit.2
 ; MEMORY:   RAW dependences:
 ; MEMORY:     [p] -> {
 ; MEMORY:       Stmt_S1[i0] -> Stmt_S2[-p + i0] :
 ; MEMORY:           i0 >= p and i0 <= 99 and i0 >= 0 and i0 <= 9 + p
 ; MEMORY:     }
 ; MEMORY:   WAR dependences:
 ; MEMORY:     [p] -> {
 ; MEMORY:     }
 ; MEMORY:   WAW dependences:
 ; MEMORY:     [p] -> {
 ; MEMORY:     }

test/Isl/CodeGen/MemAccess/simple_analyze.ll

 for.end14:                                        ; preds = %for.cond4
   ret i32 0
 }
 ; CHECK-DAG: New access function '{ Stmt_for_body7[i0] -> MemRef_B[0] }'detected in JSCOP file
 ; CHECK-DAG: New access function '{ Stmt_for_body[i0] -> MemRef_A[0] }'detected in JSCOP file
 
 ; Verify that the new access function (see above) is actually used during vector code generation.
 
+; JSCOPVEC:  store i32 0, i32* getelementptr inbounds ([100 x i32], [100 x i32]* @A, i32 0, i32 0)
+; JSCOPVEC:  store i32 1, i32* getelementptr inbounds ([100 x i32], [100 x i32]* @A, i32 0, i32 0)
+; JSCOPVEC:  store i32 2, i32* getelementptr inbounds ([100 x i32], [100 x i32]* @A, i32 0, i32 0)
+; JSCOPVEC:  store i32 3, i32* getelementptr inbounds ([100 x i32], [100 x i32]* @A, i32 0, i32 0)
+; JSCOPVEC:  store i32 4, i32* getelementptr inbounds ([100 x i32], [100 x i32]* @A, i32 0, i32 0)
+; JSCOPVEC:  store i32 5, i32* getelementptr inbounds ([100 x i32], [100 x i32]* @A, i32 0, i32 0)
+; JSCOPVEC:  store i32 6, i32* getelementptr inbounds ([100 x i32], [100 x i32]* @A, i32 0, i32 0)
+; JSCOPVEC:  store i32 7, i32* getelementptr inbounds ([100 x i32], [100 x i32]* @A, i32 0, i32 0)
+; JSCOPVEC:  store i32 8, i32* getelementptr inbounds ([100 x i32], [100 x i32]* @A, i32 0, i32 0)
+; JSCOPVEC:  store i32 9, i32* getelementptr inbounds ([100 x i32], [100 x i32]* @A, i32 0, i32 0)
+; JSCOPVEC:  store i32 10, i32* getelementptr inbounds ([100 x i32], [100 x i32]* @A, i32 0, i32 0)
+; JSCOPVEC:  store i32 11, i32* getelementptr inbounds ([100 x i32], [100 x i32]* @A, i32 0, i32 0)
+
 ; JSCOPVEC:  store i32 0, i32* getelementptr inbounds ([100 x i32], [100 x i32]* @B, i32 0, i32 0)
 ; JSCOPVEC:  store i32 1, i32* getelementptr inbounds ([100 x i32], [100 x i32]* @B, i32 0, i32 0)
 ; JSCOPVEC:  store i32 2, i32* getelementptr inbounds ([100 x i32], [100 x i32]* @B, i32 0, i32 0)
 ; JSCOPVEC:  store i32 3, i32* getelementptr inbounds ([100 x i32], [100 x i32]* @B, i32 0, i32 0)
 ; JSCOPVEC:  store i32 4, i32* getelementptr inbounds ([100 x i32], [100 x i32]* @B, i32 0, i32 0)
 ; JSCOPVEC:  store i32 5, i32* getelementptr inbounds ([100 x i32], [100 x i32]* @B, i32 0, i32 0)
 ; JSCOPVEC:  store i32 6, i32* getelementptr inbounds ([100 x i32], [100 x i32]* @B, i32 0, i32 0)
 ; JSCOPVEC:  store i32 7, i32* getelementptr inbounds ([100 x i32], [100 x i32]* @B, i32 0, i32 0)
 ; JSCOPVEC:  store i32 8, i32* getelementptr inbounds ([100 x i32], [100 x i32]* @B, i32 0, i32 0)
 ; JSCOPVEC:  store i32 9, i32* getelementptr inbounds ([100 x i32], [100 x i32]* @B, i32 0, i32 0)
 ; JSCOPVEC:  store i32 10, i32* getelementptr inbounds ([100 x i32], [100 x i32]* @B, i32 0, i32 0)
 ; JSCOPVEC:  store i32 11, i32* getelementptr inbounds ([100 x i32], [100 x i32]* @B, i32 0, i32 0)
 
-; JSCOPVEC:  store i32 0, i32* getelementptr inbounds ([100 x i32], [100 x i32]* @A, i32 0, i32 0)
-; JSCOPVEC:  store i32 1, i32* getelementptr inbounds ([100 x i32], [100 x i32]* @A, i32 0, i32 0)
-; JSCOPVEC:  store i32 2, i32* getelementptr inbounds ([100 x i32], [100 x i32]* @A, i32 0, i32 0)
-; JSCOPVEC:  store i32 3, i32* getelementptr inbounds ([100 x i32], [100 x i32]* @A, i32 0, i32 0)
-; JSCOPVEC:  store i32 4, i32* getelementptr inbounds ([100 x i32], [100 x i32]* @A, i32 0, i32 0)
-; JSCOPVEC:  store i32 5, i32* getelementptr inbounds ([100 x i32], [100 x i32]* @A, i32 0, i32 0)
-; JSCOPVEC:  store i32 6, i32* getelementptr inbounds ([100 x i32], [100 x i32]* @A, i32 0, i32 0)
-; JSCOPVEC:  store i32 7, i32* getelementptr inbounds ([100 x i32], [100 x i32]* @A, i32 0, i32 0)
-; JSCOPVEC:  store i32 8, i32* getelementptr inbounds ([100 x i32], [100 x i32]* @A, i32 0, i32 0)
-; JSCOPVEC:  store i32 9, i32* getelementptr inbounds ([100 x i32], [100 x i32]* @A, i32 0, i32 0)
-; JSCOPVEC:  store i32 10, i32* getelementptr inbounds ([100 x i32], [100 x i32]* @A, i32 0, i32 0)
-; JSCOPVEC:  store i32 11, i32* getelementptr inbounds ([100 x i32], [100 x i32]* @A, i32 0, i32 0)

test/Isl/CodeGen/invariant_load_escaping_second_scop.ll

 ;
 ;      fence();
 ;
 ;      do {
 ; P:     A[i]++;
 ;      } while (i++ < x / 2);
 ;    }
 ;
-; CHECK:      polly.start:
+; CHECK:      polly.start6:
 ; CHECK-NEXT:   sext i32 %tmp.merge to i64
 ;
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 define void @f(i32* %A, i32* %B) {
 entry:
   br label %stmt.S
 

test/Isl/CodeGen/simple_loop_non_single_exit.ll

-; RUN: opt %loadPolly -polly-codegen -analyze < %s | FileCheck %s
+; RUN: opt %loadPolly -polly-ast -analyze < %s | FileCheck %s
 ; RUN: opt %loadPolly -polly-codegen -S < %s | FileCheck %s -check-prefix=CHECK-CODE
 
 ; void f(long A[], long N) {
 ;   long i;
 ;   if (true)
 ;     for (i = 0; i < N; ++i)
 ;       A[i] = i;
 ; }
for.i:
   %exitcond = icmp eq i64 %indvar.next, %N
   br i1 %exitcond, label %return, label %for.i
 
 return:
   fence seq_cst
   ret void
 }
 
-; CHECK: Create LLVM-IR from SCoPs' for region: 'next => polly.merge_new_and_old'
+; CHECK: :: isl ast :: f :: next => return
 ; CHECK-CODE: polly.split_new_and_old
 ; CHECK-CODE: polly.merge_new_and_old

test/Isl/CodeGen/simple_loop_non_single_exit_2.ll

-; RUN: opt %loadPolly -polly-codegen -analyze < %s | FileCheck %s
+; RUN: opt %loadPolly -polly-ast -analyze < %s | FileCheck %s
 ; RUN: opt %loadPolly -polly-codegen -S < %s | FileCheck %s -check-prefix=CHECK-CODE
 
 ; void f(long A[], long N) {
 ;   long i;
 ;   if (true)
 ;     if (true)
 ;       for (i = 0; i < N; ++i)
 ;         A[i] = i;
for.i:
   %exitcond = icmp eq i64 %indvar.next, %N
   br i1 %exitcond, label %return, label %for.i
 
 return:
   fence seq_cst
   ret void
 }
 
-; CHECK: Create LLVM-IR from SCoPs' for region: 'for.i => return'
+; CHECK: :: isl ast :: f :: next => return
 ; CHECK-CODE: polly.split_new_and_old
 ; CHECK-CODE: polly.merge_new_and_old

test/Isl/CodeGen/simple_non_single_entry.ll

-; RUN: opt %loadPolly -polly-codegen -analyze < %s | FileCheck %s
+; RUN: opt %loadPolly -polly-ast -analyze < %s | FileCheck %s
 ; RUN: opt %loadPolly -polly-codegen -S < %s | FileCheck %s -check-prefix=CHECK-CODE
 
 ; void f(long A[], long N) {
 ;   long i;
 ;
 ;  if (true){
 ;    i = 0;
 ;    goto next;
for.i:
   %exitcond = icmp eq i64 %indvar.next, %N
   br i1 %exitcond, label %return, label %for.i
 
 return:
   fence seq_cst
   ret void
 }
 
-; CHECK: Create LLVM-IR from SCoPs' for region: 'next => polly.merge_new_and_old'
+; CHECK: :: isl ast :: f :: next => for.i
 ; CHECK-CODE: polly.split_new_and_old
 ; CHECK-CODE: polly.merge_new_and_old

test/Isl/CodeGen/single_loop_zero_iterations.ll

 if.else:                                          ; preds = %for.end
   br label %return
 
 return:                                           ; preds = %if.else, %if.then
   %retval.0 = phi i32 [ 0, %if.then ], [ 1, %if.else ] ; <i32> [#uses=1]
   ret i32 %retval.0
 }
 
-; SCALAR: for region: 'for.cond => for.end' in function 'main':
 ; SCALAR-NOT:   Stmt_for_body(0);

test/Isl/CodeGen/two-scops-in-row.ll

 
 ; RUN: opt %loadPolly -polly-ast -analyze -polly-ignore-aliasing < %s | FileCheck %s -check-prefix=SCALAR
 ; RUN: opt %loadPolly -polly-codegen -polly-ignore-aliasing -disable-output < %s
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
+; SCALAR: if (1)
+; SCALAR:     Stmt_for_0(0);
+
 ; SCALAR: if (
 ; SCALAR:     {
 ; SCALAR:       Stmt_for_1(0);
 ; SCALAR:       for (int c0 = 1; c0 <= -Scalar0.val + 99; c0 += 1)
 ; SCALAR:         Stmt_for_1(c0);
 ; SCALAR:     }
 
-; SCALAR: if (1)
-; SCALAR:     Stmt_for_0(0);
-
-
 define void @foo(i32* %A) {
 entry:
   %Scalar0 = alloca i32
   br label %for.0
 
 for.0:
   %Scalar0.val = load i32, i32* %Scalar0
   store i32 1, i32* %Scalar0

test/ScopInfo/aliasing_many_parameters_not_all_involved.ll

 ; RUN: opt %loadPolly -polly-scops -polly-code-generator=isl -polly-rtc-max-parameters=8 -analyze < %s | FileCheck %s --check-prefix=MAX8
 ; RUN: opt %loadPolly -polly-scops -polly-code-generator=isl -polly-rtc-max-parameters=7 -analyze < %s | FileCheck %s --check-prefix=MAX7
 ;
 ; Check that we allow this SCoP even though it has 10 parameters involved in posisbly aliasing accesses.
 ; However, only 7 are involved in accesses through B, 8 through C and none in accesses through A.
 ;
-; MAX8-LABEL:       Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'for.cond => for.end' in function 'jd':
-; MAX8:  Function: jd
-
-; MAX7-LABEL:       Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'for.cond => for.end' in function 'jd':
-; MAX7:  Invalid Scop!
+; MAX8:     Function: jd
+;
+; MAX7-NOT: Function: jd
 ;
 ;    void jd(int *A, int *B, int *C, long p1, long p2, long p3, long p4, long p5,
 ;            long p6, long p7, long p8, long p9, long p10) {
 ;      for (int i = 0; i < 1024; i++)
 ;        A[i] = B[p1] - B[p2] + B[-p3] - B[p4] + B[p5] - B[-p6] + B[p7] - C[p3] +
 ;               C[-p4] - C[p5] + C[p6] - C[-p7] + C[p8] - C[p9] + C[-p10];
 ;    }
 ;

test/ScopInfo/cond_in_loop.ll

bb3:                                              ; preds = %bb2, %bb1
   %3 = add nsw i64 %1, 1                          ; <i64> [#uses=2]
   %exitcond = icmp eq i64 %3, %M                  ; <i1> [#uses=1]
   br i1 %exitcond, label %return, label %bb
 
 return:                                           ; preds = %bb3, %entry
   ret void
 }
 
-; CHECK-LABEL: Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'bb => return' in function 'f':
-; CHECK-NEXT:      Function: f
+; CHECK:         Function: f
 ; CHECK-NEXT:      Region: %bb---%return

test/ScopInfo/integers.ll

 ; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
 
 ; Check that we correctly convert integers to isl values.
 
 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"
 
 ; Large positive integer
 define void @f(i1024* nocapture %a) nounwind {
 entry:
   br label %bb
 
 bb:
   %indvar = phi i1024 [ 0, %entry ], [ %indvar.next, %bb ]
   store i1024 %indvar, i1024* %a, align 8
   %indvar.next = add nsw i1024 %indvar, 1
   %exitcond = icmp eq i1024 %indvar, 123456000000000000000000000
-; CHECK:  'bb => return' in function 'f'
+; CHECK: Function: f
+; CHECK: Region: %bb---%return
 ; CHECK: i0 <= 123456000000000000000000000
   br i1 %exitcond, label %return, label %bb
 
 return:
   ret void
 }
 
 ; Normal positive integer
 define void @f2(i32* nocapture %a) nounwind {
 entry:
   br label %bb
 
 bb:
   %indvar = phi i32 [ 0, %entry ], [ %indvar.next, %bb ]
   %scevgep = getelementptr i32, i32* %a, i32 %indvar
   store i32 %indvar, i32* %scevgep, align 8
   %indvar.next = add nsw i32 %indvar, 1
   %exitcond = icmp eq i32 %indvar, 123456
-; CHECK:  'bb => return' in function 'f2'
+; CHECK: Function: f2
+; CHECK: Region: %bb---%return
 ; CHECK: i0 <= 123456
   br i1 %exitcond, label %return, label %bb
 
 return:
   ret void
 }
 
 ; Normal negative integer
 define void @f3(i32* nocapture %a, i32 %n) nounwind {
 entry:
   br label %bb
 
 bb:
   %indvar = phi i32 [ 0, %entry ], [ %indvar.next, %bb ]
   %scevgep = getelementptr i32, i32* %a, i32 %indvar
   store i32 %indvar, i32* %scevgep, align 8
   %indvar.next = add nsw i32 %indvar, 1
   %sub = sub i32 %n, 123456
   %exitcond = icmp eq i32 %indvar, %sub
-; CHECK:  'bb => return' in function 'f3'
+; CHECK: Function: f3
+; CHECK: Region: %bb---%return
 ; CHECK: -123456
   br i1 %exitcond, label %return, label %bb
 
 return:
   ret void
 }
 
 ; Large negative integer
 define void @f4(i1024* nocapture %a, i1024 %n) nounwind {
 entry:
   br label %bb
 
 bb:
   %indvar = phi i1024 [ 0, %entry ], [ %indvar.next, %bb ]
   %scevgep = getelementptr i1024, i1024* %a, i1024 %indvar
   store i1024 %indvar, i1024* %scevgep, align 8
   %indvar.next = add nsw i1024 %indvar, 1
   %sub = sub i1024 %n, 123456000000000000000000000000000000
-; CHECK:  'bb => return' in function 'f4'
+; CHECK: Function: f4
+; CHECK: Region: %bb---%return
 ; CHECK: -123456000000000000000000000000000000
   %exitcond = icmp eq i1024 %indvar, %sub
   br i1 %exitcond, label %return, label %bb
 
 return:
   ret void
 }
 
 define void @f5(i1023* nocapture %a, i1023 %n) nounwind {
 entry:
   br label %bb
 
 bb:
   %indvar = phi i1023 [ 0, %entry ], [ %indvar.next, %bb ]
   %scevgep = getelementptr i1023, i1023* %a, i1023 %indvar
   store i1023 %indvar, i1023* %scevgep, align 8
   %indvar.next = add nsw i1023 %indvar, 1
   %sub = sub i1023 %n, 123456000000000000000000000000000000
-; CHECK:  'bb => return' in function 'f5'
+; CHECK: Function: f5
+; CHECK: Region: %bb---%return
 ; CHECK: -123456000000000000000000000000000000
   %exitcond = icmp eq i1023 %indvar, %sub
   br i1 %exitcond, label %return, label %bb
 
 return:
   ret void
 }
 
 ; Tiny negative integer
 define void @f6(i3* nocapture %a, i3 %n) nounwind {
 entry:
   br label %bb
 
 bb:
   %indvar = phi i3 [ 0, %entry ], [ %indvar.next, %bb ]
   %scevgep = getelementptr i3, i3* %a, i3 %indvar
   store i3 %indvar, i3* %scevgep, align 8
   %indvar.next = add nsw i3 %indvar, 1
   %sub = sub i3 %n, 3
-; CHECK:  'bb => return' in function 'f6'
+; CHECK: Function: f6
+; CHECK: Region: %bb---%return
 ; CHECK: -3
   %exitcond = icmp eq i3 %indvar, %sub
   br i1 %exitcond, label %return, label %bb
 
 return:
   ret void
 }

test/ScopInfo/undef_in_cond.ll

 
 bb3:                                              ; preds = %bb2, %bb1, %bb
   br label %bb14
 
 bb14:                                             ; preds = %bb5, %bb4, %bb3, %entry
   ret void
 }
 
-; CHECK: Invalid Scop!
+; CHECK-NOT: Statements