Index: include/polly/CodeGen/IslAst.h
===================================================================
--- include/polly/CodeGen/IslAst.h
+++ include/polly/CodeGen/IslAst.h
@@ -31,6 +31,7 @@
 class raw_ostream;
 }
 
+struct isl_pw_aff;
 struct isl_ast_node;
 struct isl_ast_expr;
 struct isl_ast_build;
@@ -41,6 +42,7 @@
 class Scop;
 class IslAst;
 class MemoryAccess;
+class DependenceInfo;
 
 class IslAstInfo : public ScopPass {
 public:
@@ -80,21 +82,32 @@
   };
 
 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);
+  bool runOnScop(Scop &S) 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;
+  void printScop(llvm::raw_ostream &OS, Scop &S) const override;
+
+  /// @brief Called after each function to trigger memory release.
+  void releaseMemory() override;
 
-  /// @brief Return a copy of the AST root node.
-  __isl_give isl_ast_node *getAst() const;
+  void getAnalysisUsage(AnalysisUsage &AU) const override;
+
+  /// @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.
   ///
@@ -102,7 +115,7 @@
   /// 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.
   ///
@@ -143,9 +156,6 @@
   static __isl_give isl_ast_build *getBuild(__isl_keep isl_ast_node *Node);
 
   ///}
-
-  virtual void getAnalysisUsage(AnalysisUsage &AU) const;
-  virtual void releaseMemory();
 };
 }
 
Index: include/polly/DependenceInfo.h
===================================================================
--- include/polly/DependenceInfo.h
+++ include/polly/DependenceInfo.h
@@ -43,7 +43,7 @@
 class ScopStmt;
 class MemoryAccess;
 
-class Dependences : public ScopPass {
+class DependenceInfo : public ScopPass {
 public:
   static char ID;
 
@@ -77,7 +77,8 @@
 
   typedef std::map<ScopStmt *, isl_map *> StatementToIslMapTy;
 
-  Dependences();
+  /// @brief Pass constructor
+  DependenceInfo() : ScopPass(ID) {}
 
   /// @brief Check if a new scattering is valid.
   ///
@@ -85,7 +86,7 @@
   ///
   /// @return bool True if the new scattering is valid, false it it reverses
   ///              dependences.
-  bool isValidScattering(StatementToIslMapTy *NewScatterings);
+  bool isValidScattering(Scop &S, StatementToIslMapTy *NewScatterings);
 
   /// @brief Check if a partial schedule is parallel wrt to @p Deps.
   ///
@@ -101,28 +102,33 @@
                   __isl_take isl_union_map *Deps,
                   __isl_give isl_pw_aff **MinDistancePtr = nullptr);
 
-  /// @brief Get the dependences in this Scop.
+  /// @brief Get the dependences for the given SCoP @p S.
   ///
+  /// @param S     The SCoP for which we should return the dependences.
   /// @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_union_map *getDependences(int Kinds);
+  isl_union_map *getDependences(Scop &S, int Kinds);
 
-  /// @brief Report if valid dependences are available.
-  bool hasValidDependences();
+  /// @brief Report if valid dependences are available for the given SCoP @p S.
+  bool hasValidDependences(Scop &S);
 
   /// @brief Return the reduction dependences caused by @p MA.
   ///
   /// @return The reduction dependences caused by @p MA or nullptr if None.
-  __isl_give isl_map *getReductionDependences(MemoryAccess *MA);
+  __isl_give isl_map *getReductionDependences(Scop &S, MemoryAccess *MA);
 
   /// @brief Return the reduction dependences mapped by the causing @p MA.
-  const DenseMap<MemoryAccess *, isl_map *> &getReductionDependences() const {
-    return ReductionDependences;
+  const DenseMap<MemoryAccess *, isl_map *> &getReductionDependences(Scop &S) {
+    const Dependences &D = getDependences(S);
+    return D.ReductionDependences;
   }
 
   /// @brief Recompute dependences from schedule and memory accesses.
-  void recomputeDependences();
+  void recomputeDependences(Scop &S);
+
+  /// @brief Initializer called once per function.
+  void initializeScopPass() override {}
 
   bool runOnScop(Scop &S) override;
   void printScop(raw_ostream &OS, Scop &S) const override;
@@ -130,21 +136,57 @@
   void getAnalysisUsage(AnalysisUsage &AU) const override;
 
 private:
-  Scop *S;
-
-  /// @brief The different kinds of dependences we calculate.
-  isl_union_map *RAW;
-  isl_union_map *WAR;
-  isl_union_map *WAW;
+  /// @brief Struct type to remember all kinds of dependences for a SCoP.
+  struct Dependences {
+    /// @brief The different kinds of dependences we calculate.
+    isl_union_map *RAW;
+    isl_union_map *WAR;
+    isl_union_map *WAW;
+
+    /// @brief The map of reduction dependences
+    isl_union_map *RED = nullptr;
+
+    /// @brief The (reverse) transitive closure of reduction dependences
+    isl_union_map *TC_RED = nullptr;
+
+    /// @brief Map from memory accesses to their reduction dependences.
+    DenseMap<MemoryAccess *, isl_map *> ReductionDependences;
+
+    /// @brief Create an empty dependence struct.
+    Dependences()
+        : RAW(nullptr), WAR(nullptr), WAW(nullptr), RED(nullptr),
+          TC_RED(nullptr) {}
+
+    /// @brief Create a dependence struct by moving all members of @p Other.
+    Dependences(Dependences &&Other)
+        : RAW(Other.RAW), WAR(Other.WAR), WAW(Other.WAW), RED(Other.RED),
+          TC_RED(Other.TC_RED),
+          ReductionDependences(std::move(Other.ReductionDependences)) {
+      Other.RAW = Other.WAR = Other.WAW = Other.RED = Other.TC_RED = nullptr;
+      Other.ReductionDependences.clear();
+    }
+
+    /// @brief Free the objects associated with this dependence struct.
+    void releaseMemory();
+
+    /// @brief Destructor to free internal objects.
+    ~Dependences() { releaseMemory(); }
+  };
 
-  /// @brief The map of reduction dependences
-  isl_union_map *RED = nullptr;
+  /// @brief Mapping from SCoPs to their dependence structs.
+  DenseMap<const Scop *, Dependences> DependenceMap;
 
-  /// @brief The (reverse) transitive closure of reduction dependences
-  isl_union_map *TC_RED = nullptr;
+  /// @brief Return the const dependence struct for a 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 Map from memory accesses to their reduction dependences.
-  DenseMap<MemoryAccess *, isl_map *> ReductionDependences;
+  /// @brief Return the dependence struct for a given SCoP @p S.
+  Dependences &getDependences(Scop &S) {
+    assert(DependenceMap.count(&S) && "Dependences for given SCoP not found");
+    return DependenceMap.find(&S)->getSecond();
+  }
 
   /// @brief Collect information about the SCoP.
   void collectInfo(Scop &S, isl_union_map **Read, isl_union_map **Write,
@@ -152,20 +194,21 @@
                    isl_union_map **StmtSchedule);
 
   /// @brief Calculate and add at the privatization dependences
-  void addPrivatizationDependences();
+  void addPrivatizationDependences(Scop &S);
 
   /// @brief Calculate the dependences for a certain SCoP.
   void calculateDependences(Scop &S);
 
   /// @brief Set the reduction dependences for @p MA to @p Deps.
-  void setReductionDependences(MemoryAccess *MA, __isl_take isl_map *Deps);
+  void setReductionDependences(Scop &S, MemoryAccess *MA,
+                               __isl_take isl_map *Deps);
 };
 
 } // End polly namespace.
 
 namespace llvm {
 class PassRegistry;
-void initializeDependencesPass(llvm::PassRegistry &);
+void initializeDependenceInfoPass(llvm::PassRegistry &);
 }
 
 #endif
Index: include/polly/LinkAllPasses.h
===================================================================
--- include/polly/LinkAllPasses.h
+++ include/polly/LinkAllPasses.h
@@ -28,7 +28,7 @@
 namespace polly {
 llvm::Pass *createCodePreparationPass();
 llvm::Pass *createDeadCodeElimPass();
-llvm::Pass *createDependencesPass();
+llvm::Pass *createDependenceInfoPass();
 llvm::Pass *createDOTOnlyPrinterPass();
 llvm::Pass *createDOTOnlyViewerPass();
 llvm::Pass *createDOTPrinterPass();
@@ -63,7 +63,7 @@
 
     polly::createCodePreparationPass();
     polly::createDeadCodeElimPass();
-    polly::createDependencesPass();
+    polly::createDependenceInfoPass();
     polly::createDOTOnlyPrinterPass();
     polly::createDOTOnlyViewerPass();
     polly::createDOTPrinterPass();
Index: include/polly/ScopInfo.h
===================================================================
--- include/polly/ScopInfo.h
+++ include/polly/ScopInfo.h
@@ -22,7 +22,7 @@
 
 #include "polly/ScopDetection.h"
 
-#include "llvm/Analysis/RegionPass.h"
+#include "llvm/Pass.h"
 
 #include "isl/ctx.h"
 
@@ -740,11 +740,6 @@
   /// group to ensure the SCoP is executed in an alias free environment.
   MinMaxVectorVectorTy MinMaxAliasGroups;
 
-  /// Create the static control part with a region, max loop depth of this
-  /// region and parameters used in this region.
-  Scop(TempScop &TempScop, LoopInfo &LI, ScalarEvolution &SE, ScopDetection &SD,
-       isl_ctx *ctx);
-
   /// @brief Check if a basic block is trivial.
   ///
   /// A trivial basic block does not contain any useful calculation. Therefore,
@@ -799,6 +794,11 @@
   friend class ScopInfo;
 
 public:
+  /// Create the static control part with a region, max loop depth of this
+  /// region and parameters used in this region.
+  Scop(TempScop &TempScop, LoopInfo &LI, ScalarEvolution &SE, ScopDetection &SD,
+       isl_ctx *ctx);
+
   ~Scop();
 
   ScalarEvolution *getSE() const;
@@ -1005,47 +1005,45 @@
 ///===---------------------------------------------------------------------===//
 /// @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 Scop
-  Scop *scop;
-  isl_ctx *ctx;
+  /// @brief The SCoPs build in this function.
+  ScopVectorTy Scops;
 
-  void clear() {
-    if (scop) {
-      delete scop;
-      scop = 0;
-    }
-  }
+  /// @brief The isl contexts for each SCoP created.
+  SmallVector<isl_ctx *, 16> IslCtxs;
 
 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 {
-    if (scop)
-      scop->print(OS);
-    else
-      OS << "Invalid Scop!\n";
-  }
+  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;
   //@}
 };
 
Index: include/polly/ScopPass.h
===================================================================
--- include/polly/ScopPass.h
+++ include/polly/ScopPass.h
@@ -18,7 +18,7 @@
 #ifndef POLLY_SCOP_PASS_H
 #define POLLY_SCOP_PASS_H
 
-#include "llvm/Analysis/RegionPass.h"
+#include "llvm/Pass.h"
 
 using namespace llvm;
 
@@ -26,21 +26,28 @@
 
 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 = 0;
 
@@ -50,7 +57,7 @@
   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;
 };
 
Index: lib/Analysis/DependenceInfo.cpp
===================================================================
--- lib/Analysis/DependenceInfo.cpp
+++ lib/Analysis/DependenceInfo.cpp
@@ -20,11 +20,13 @@
 //
 //===----------------------------------------------------------------------===//
 //
-#include "polly/Dependences.h"
+#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>
@@ -63,12 +65,12 @@
     cl::cat(PollyCategory));
 
 //===----------------------------------------------------------------------===//
-Dependences::Dependences() : ScopPass(ID) { RAW = WAR = WAW = nullptr; }
 
-void Dependences::collectInfo(Scop &S, isl_union_map **Read,
-                              isl_union_map **Write, isl_union_map **MayWrite,
-                              isl_union_map **AccessSchedule,
-                              isl_union_map **StmtSchedule) {
+void DependenceInfo::collectInfo(Scop &S, isl_union_map **Read,
+                                 isl_union_map **Write,
+                                 isl_union_map **MayWrite,
+                                 isl_union_map **AccessSchedule,
+                                 isl_union_map **StmtSchedule) {
   isl_space *Space = S.getParamSpace();
   *Read = isl_union_map_empty(isl_space_copy(Space));
   *Write = isl_union_map_empty(isl_space_copy(Space));
@@ -173,41 +175,43 @@
 ///
 /// Note: This function also computes the (reverse) transitive closure of the
 ///       reduction dependences.
-void Dependences::addPrivatizationDependences() {
+void DependenceInfo::addPrivatizationDependences(Scop &S) {
   isl_union_map *PrivRAW, *PrivWAW, *PrivWAR;
 
+  Dependences &D = getDependences(S);
+
   // The transitive closure might be over approximated, thus could lead to
   // dependency cycles in the privatization dependences. To make sure this
   // will not happen we remove all negative dependences after we computed
   // the transitive closure.
-  TC_RED = isl_union_map_transitive_closure(isl_union_map_copy(RED), 0);
+  D.TC_RED = isl_union_map_transitive_closure(isl_union_map_copy(D.RED), 0);
 
   // FIXME: Apply the current schedule instead of assuming the identity schedule
   //        here. The current approach is only valid as long as we compute the
   //        dependences only with the initial (identity schedule). Any other
   //        schedule could change "the direction of the backward dependences" we
   //        want to eliminate here.
-  isl_union_set *UDeltas = isl_union_map_deltas(isl_union_map_copy(TC_RED));
+  isl_union_set *UDeltas = isl_union_map_deltas(isl_union_map_copy(D.TC_RED));
   isl_union_set *Universe = isl_union_set_universe(isl_union_set_copy(UDeltas));
   isl_union_set *Zero = isl_union_set_empty(isl_union_set_get_space(Universe));
   isl_union_set_foreach_set(Universe, fixSetToZero, &Zero);
   isl_union_map *NonPositive = isl_union_set_lex_le_union_set(UDeltas, Zero);
 
-  TC_RED = isl_union_map_subtract(TC_RED, NonPositive);
+  D.TC_RED = isl_union_map_subtract(D.TC_RED, NonPositive);
 
-  TC_RED = isl_union_map_union(
-      TC_RED, isl_union_map_reverse(isl_union_map_copy(TC_RED)));
-  TC_RED = isl_union_map_coalesce(TC_RED);
+  D.TC_RED = isl_union_map_union(
+      D.TC_RED, isl_union_map_reverse(isl_union_map_copy(D.TC_RED)));
+  D.TC_RED = isl_union_map_coalesce(D.TC_RED);
 
-  isl_union_map **Maps[] = {&RAW, &WAW, &WAR};
+  isl_union_map **Maps[] = {&D.RAW, &D.WAW, &D.WAR};
   isl_union_map **PrivMaps[] = {&PrivRAW, &PrivWAW, &PrivWAR};
   for (unsigned u = 0; u < 3; u++) {
     isl_union_map **Map = Maps[u], **PrivMap = PrivMaps[u];
 
     *PrivMap = isl_union_map_apply_range(isl_union_map_copy(*Map),
-                                         isl_union_map_copy(TC_RED));
+                                         isl_union_map_copy(D.TC_RED));
     *PrivMap = isl_union_map_union(
-        *PrivMap, isl_union_map_apply_range(isl_union_map_copy(TC_RED),
+        *PrivMap, isl_union_map_apply_range(isl_union_map_copy(D.TC_RED),
                                             isl_union_map_copy(*Map)));
 
     *Map = isl_union_map_union(*Map, *PrivMap);
@@ -216,10 +220,11 @@
   isl_union_set_free(Universe);
 }
 
-void Dependences::calculateDependences(Scop &S) {
+void DependenceInfo::calculateDependences(Scop &S) {
   isl_union_map *Read, *Write, *MayWrite, *AccessSchedule, *StmtSchedule,
       *Schedule;
 
+  Dependences &D = getDependences(S);
   DEBUG(dbgs() << "Scop: \n" << S << "\n");
 
   collectInfo(S, &Read, &Write, &MayWrite, &AccessSchedule, &StmtSchedule);
@@ -240,19 +245,15 @@
         dbgs() << "MayWrite: " << MayWrite << "\n";
         dbgs() << "Schedule: " << Schedule << "\n");
 
-  // The pointers below will be set by the subsequent calls to
-  // isl_union_map_compute_flow.
-  RAW = WAW = WAR = RED = nullptr;
-
   if (OptAnalysisType == VALUE_BASED_ANALYSIS) {
     isl_union_map_compute_flow(
         isl_union_map_copy(Read), isl_union_map_copy(Write),
-        isl_union_map_copy(MayWrite), isl_union_map_copy(Schedule), &RAW,
+        isl_union_map_copy(MayWrite), isl_union_map_copy(Schedule), &D.RAW,
         nullptr, nullptr, nullptr);
 
     isl_union_map_compute_flow(
         isl_union_map_copy(Write), isl_union_map_copy(Write),
-        isl_union_map_copy(Read), isl_union_map_copy(Schedule), &WAW, &WAR,
+        isl_union_map_copy(Read), isl_union_map_copy(Schedule), &D.WAW, &D.WAR,
         nullptr, nullptr);
   } else {
     isl_union_map *Empty;
@@ -262,18 +263,18 @@
 
     isl_union_map_compute_flow(
         isl_union_map_copy(Read), isl_union_map_copy(Empty),
-        isl_union_map_copy(Write), isl_union_map_copy(Schedule), nullptr, &RAW,
-        nullptr, nullptr);
+        isl_union_map_copy(Write), isl_union_map_copy(Schedule), nullptr,
+        &D.RAW, nullptr, nullptr);
 
     isl_union_map_compute_flow(
         isl_union_map_copy(Write), isl_union_map_copy(Empty),
-        isl_union_map_copy(Read), isl_union_map_copy(Schedule), nullptr, &WAR,
+        isl_union_map_copy(Read), isl_union_map_copy(Schedule), nullptr, &D.WAR,
         nullptr, nullptr);
 
     isl_union_map_compute_flow(
         isl_union_map_copy(Write), isl_union_map_copy(Empty),
-        isl_union_map_copy(Write), isl_union_map_copy(Schedule), nullptr, &WAW,
-        nullptr, nullptr);
+        isl_union_map_copy(Write), isl_union_map_copy(Schedule), nullptr,
+        &D.WAW, nullptr, nullptr);
     isl_union_map_free(Empty);
   }
 
@@ -282,15 +283,15 @@
   isl_union_map_free(Read);
   isl_union_map_free(Schedule);
 
-  RAW = isl_union_map_coalesce(RAW);
-  WAW = isl_union_map_coalesce(WAW);
-  WAR = isl_union_map_coalesce(WAR);
+  D.RAW = isl_union_map_coalesce(D.RAW);
+  D.WAW = isl_union_map_coalesce(D.WAW);
+  D.WAR = isl_union_map_coalesce(D.WAR);
 
   if (isl_ctx_last_error(S.getIslCtx()) == isl_error_quota) {
-    isl_union_map_free(RAW);
-    isl_union_map_free(WAW);
-    isl_union_map_free(WAR);
-    RAW = WAW = WAR = nullptr;
+    isl_union_map_free(D.RAW);
+    isl_union_map_free(D.WAW);
+    isl_union_map_free(D.WAR);
+    D.RAW = D.WAW = D.WAR = nullptr;
     isl_ctx_reset_error(S.getIslCtx());
   }
   isl_options_set_on_error(S.getIslCtx(), ISL_ON_ERROR_ABORT);
@@ -299,12 +300,12 @@
 
   isl_union_map *STMT_RAW, *STMT_WAW, *STMT_WAR;
   STMT_RAW = isl_union_map_intersect_domain(
-      isl_union_map_copy(RAW),
+      isl_union_map_copy(D.RAW),
       isl_union_map_domain(isl_union_map_copy(StmtSchedule)));
   STMT_WAW = isl_union_map_intersect_domain(
-      isl_union_map_copy(WAW),
+      isl_union_map_copy(D.WAW),
       isl_union_map_domain(isl_union_map_copy(StmtSchedule)));
-  STMT_WAR = isl_union_map_intersect_domain(isl_union_map_copy(WAR),
+  STMT_WAR = isl_union_map_intersect_domain(isl_union_map_copy(D.WAR),
                                             isl_union_map_domain(StmtSchedule));
   DEBUG({
     dbgs() << "Wrapped Dependences:\n";
@@ -327,7 +328,7 @@
   //    write and before the first access to a reduction location).
 
   // Step 1)
-  RED = isl_union_map_empty(isl_union_map_get_space(RAW));
+  D.RED = isl_union_map_empty(isl_union_map_get_space(D.RAW));
   for (ScopStmt *Stmt : S) {
     for (MemoryAccess *MA : *Stmt) {
       if (!MA->isReductionLike())
@@ -335,22 +336,22 @@
       isl_set *AccDomW = isl_map_wrap(MA->getAccessRelation());
       isl_map *Identity =
           isl_map_from_domain_and_range(isl_set_copy(AccDomW), AccDomW);
-      RED = isl_union_map_add_map(RED, Identity);
+      D.RED = isl_union_map_add_map(D.RED, Identity);
     }
   }
 
   // Step 2)
-  RED = isl_union_map_intersect(RED, isl_union_map_copy(RAW));
-  RED = isl_union_map_intersect(RED, isl_union_map_copy(WAW));
+  D.RED = isl_union_map_intersect(D.RED, isl_union_map_copy(D.RAW));
+  D.RED = isl_union_map_intersect(D.RED, isl_union_map_copy(D.WAW));
 
-  if (!isl_union_map_is_empty(RED)) {
+  if (!isl_union_map_is_empty(D.RED)) {
 
     // Step 3)
-    RAW = isl_union_map_subtract(RAW, isl_union_map_copy(RED));
-    WAW = isl_union_map_subtract(WAW, isl_union_map_copy(RED));
+    D.RAW = isl_union_map_subtract(D.RAW, isl_union_map_copy(D.RED));
+    D.WAW = isl_union_map_subtract(D.WAW, isl_union_map_copy(D.RED));
 
     // Step 4)
-    addPrivatizationDependences();
+    addPrivatizationDependences(S);
   }
 
   DEBUG({
@@ -363,7 +364,7 @@
   // split them according to the causing memory accesses. The current assumption
   // is that our method of splitting will not have any leftovers. In the end
   // we validate this assumption until we have more confidence in this method.
-  isl_union_map *RED_SIN = isl_union_map_empty(isl_union_map_get_space(RAW));
+  isl_union_map *RED_SIN = isl_union_map_empty(isl_union_map_get_space(D.RAW));
 
   // For each reduction like memory access, check if there are reduction
   // dependences with the access relation of the memory access as a domain
@@ -378,7 +379,7 @@
 
       isl_set *AccDomW = isl_map_wrap(MA->getAccessRelation());
       isl_union_map *AccRedDepU = isl_union_map_intersect_domain(
-          isl_union_map_copy(TC_RED), isl_union_set_from_set(AccDomW));
+          isl_union_map_copy(D.TC_RED), isl_union_set_from_set(AccDomW));
       if (isl_union_map_is_empty(AccRedDepU) && !isl_union_map_free(AccRedDepU))
         continue;
 
@@ -386,20 +387,20 @@
       RED_SIN = isl_union_map_add_map(RED_SIN, isl_map_copy(AccRedDep));
       AccRedDep = isl_map_zip(AccRedDep);
       AccRedDep = isl_set_unwrap(isl_map_domain(AccRedDep));
-      setReductionDependences(MA, AccRedDep);
+      setReductionDependences(S, MA, AccRedDep);
     }
   }
 
-  assert(isl_union_map_is_equal(RED_SIN, TC_RED) &&
+  assert(isl_union_map_is_equal(RED_SIN, D.TC_RED) &&
          "Intersecting the reduction dependence domain with the wrapped access "
          "relation is not enough, we need to loosen the access relation also");
   isl_union_map_free(RED_SIN);
 
-  RAW = isl_union_map_zip(RAW);
-  WAW = isl_union_map_zip(WAW);
-  WAR = isl_union_map_zip(WAR);
-  RED = isl_union_map_zip(RED);
-  TC_RED = isl_union_map_zip(TC_RED);
+  D.RAW = isl_union_map_zip(D.RAW);
+  D.WAW = isl_union_map_zip(D.WAW);
+  D.WAR = isl_union_map_zip(D.WAR);
+  D.RED = isl_union_map_zip(D.RED);
+  D.TC_RED = isl_union_map_zip(D.TC_RED);
 
   DEBUG({
     dbgs() << "Zipped Dependences:\n";
@@ -407,11 +408,11 @@
     dbgs() << "\n";
   });
 
-  RAW = isl_union_set_unwrap(isl_union_map_domain(RAW));
-  WAW = isl_union_set_unwrap(isl_union_map_domain(WAW));
-  WAR = isl_union_set_unwrap(isl_union_map_domain(WAR));
-  RED = isl_union_set_unwrap(isl_union_map_domain(RED));
-  TC_RED = isl_union_set_unwrap(isl_union_map_domain(TC_RED));
+  D.RAW = isl_union_set_unwrap(isl_union_map_domain(D.RAW));
+  D.WAW = isl_union_set_unwrap(isl_union_map_domain(D.WAW));
+  D.WAR = isl_union_set_unwrap(isl_union_map_domain(D.WAR));
+  D.RED = isl_union_set_unwrap(isl_union_map_domain(D.RED));
+  D.TC_RED = isl_union_set_unwrap(isl_union_map_domain(D.TC_RED));
 
   DEBUG({
     dbgs() << "Unwrapped Dependences:\n";
@@ -419,37 +420,37 @@
     dbgs() << "\n";
   });
 
-  RAW = isl_union_map_union(RAW, STMT_RAW);
-  WAW = isl_union_map_union(WAW, STMT_WAW);
-  WAR = isl_union_map_union(WAR, STMT_WAR);
+  D.RAW = isl_union_map_union(D.RAW, STMT_RAW);
+  D.WAW = isl_union_map_union(D.WAW, STMT_WAW);
+  D.WAR = isl_union_map_union(D.WAR, STMT_WAR);
 
-  RAW = isl_union_map_coalesce(RAW);
-  WAW = isl_union_map_coalesce(WAW);
-  WAR = isl_union_map_coalesce(WAR);
-  RED = isl_union_map_coalesce(RED);
-  TC_RED = isl_union_map_coalesce(TC_RED);
+  D.RAW = isl_union_map_coalesce(D.RAW);
+  D.WAW = isl_union_map_coalesce(D.WAW);
+  D.WAR = isl_union_map_coalesce(D.WAR);
+  D.RED = isl_union_map_coalesce(D.RED);
+  D.TC_RED = isl_union_map_coalesce(D.TC_RED);
 
   DEBUG(printScop(dbgs(), S));
 }
 
-void Dependences::recomputeDependences() {
-  releaseMemory();
-  calculateDependences(*S);
+void DependenceInfo::recomputeDependences(Scop &S) {
+  Dependences &D = DependenceMap[&S];
+  D.releaseMemory();
+  calculateDependences(S);
 }
 
-bool Dependences::runOnScop(Scop &ScopVar) {
-  S = &ScopVar;
-  recomputeDependences();
+bool DependenceInfo::runOnScop(Scop &S) {
+  recomputeDependences(S);
   return false;
 }
 
-bool Dependences::isValidScattering(StatementToIslMapTy *NewScattering) {
-  Scop &S = *this->S;
-
+bool DependenceInfo::isValidScattering(Scop &S,
+                                       StatementToIslMapTy *NewScattering) {
   if (LegalityCheckDisabled)
     return true;
 
-  isl_union_map *Dependences = getDependences(TYPE_RAW | TYPE_WAW | TYPE_WAR);
+  isl_union_map *Dependences =
+      getDependences(S, TYPE_RAW | TYPE_WAW | TYPE_WAR);
   isl_space *Space = S.getParamSpace();
   isl_union_map *Scattering = isl_union_map_empty(Space);
 
@@ -501,8 +502,8 @@
 // dimension, then the loop is parallel. The distance is zero in the current
 // dimension if it is a subset of a map with equal values for the current
 // dimension.
-bool Dependences::isParallel(isl_union_map *Schedule, isl_union_map *Deps,
-                             isl_pw_aff **MinDistancePtr) {
+bool DependenceInfo::isParallel(isl_union_map *Schedule, isl_union_map *Deps,
+                                isl_pw_aff **MinDistancePtr) {
   isl_set *Deltas, *Distance;
   isl_map *ScheduleDeps;
   unsigned Dimension;
@@ -556,82 +557,90 @@
     OS << "n/a\n";
 }
 
-void Dependences::printScop(raw_ostream &OS, Scop &) const {
+void DependenceInfo::printScop(raw_ostream &OS, Scop &S) const {
+  const Dependences &D = getDependences(S);
+
+  OS << "Dependences for region: " << S.getRegion() << "\n";
   OS << "\tRAW dependences:\n\t\t";
-  printDependencyMap(OS, RAW);
+  printDependencyMap(OS, D.RAW);
   OS << "\tWAR dependences:\n\t\t";
-  printDependencyMap(OS, WAR);
+  printDependencyMap(OS, D.WAR);
   OS << "\tWAW dependences:\n\t\t";
-  printDependencyMap(OS, WAW);
+  printDependencyMap(OS, D.WAW);
   OS << "\tReduction dependences:\n\t\t";
-  printDependencyMap(OS, RED);
+  printDependencyMap(OS, D.RED);
   OS << "\tTransitive closure of reduction dependences:\n\t\t";
-  printDependencyMap(OS, TC_RED);
+  printDependencyMap(OS, D.TC_RED);
 }
 
-void Dependences::releaseMemory() {
+void DependenceInfo::releaseMemory() { DependenceMap.clear(); }
+
+void DependenceInfo::Dependences::releaseMemory() {
   isl_union_map_free(RAW);
   isl_union_map_free(WAR);
   isl_union_map_free(WAW);
   isl_union_map_free(RED);
   isl_union_map_free(TC_RED);
 
-  RED = RAW = WAR = WAW = TC_RED = nullptr;
-
   for (auto &ReductionDeps : ReductionDependences)
     isl_map_free(ReductionDeps.second);
-  ReductionDependences.clear();
 }
 
-isl_union_map *Dependences::getDependences(int Kinds) {
-  assert(hasValidDependences() && "No valid dependences available");
-  isl_space *Space = isl_union_map_get_space(RAW);
+isl_union_map *DependenceInfo::getDependences(Scop &S, int Kinds) {
+  assert(hasValidDependences(S) && "No valid dependences available");
+
+  Dependences &D = getDependences(S);
+  isl_space *Space = isl_union_map_get_space(D.RAW);
   isl_union_map *Deps = isl_union_map_empty(Space);
 
   if (Kinds & TYPE_RAW)
-    Deps = isl_union_map_union(Deps, isl_union_map_copy(RAW));
+    Deps = isl_union_map_union(Deps, isl_union_map_copy(D.RAW));
 
   if (Kinds & TYPE_WAR)
-    Deps = isl_union_map_union(Deps, isl_union_map_copy(WAR));
+    Deps = isl_union_map_union(Deps, isl_union_map_copy(D.WAR));
 
   if (Kinds & TYPE_WAW)
-    Deps = isl_union_map_union(Deps, isl_union_map_copy(WAW));
+    Deps = isl_union_map_union(Deps, isl_union_map_copy(D.WAW));
 
   if (Kinds & TYPE_RED)
-    Deps = isl_union_map_union(Deps, isl_union_map_copy(RED));
+    Deps = isl_union_map_union(Deps, isl_union_map_copy(D.RED));
 
   if (Kinds & TYPE_TC_RED)
-    Deps = isl_union_map_union(Deps, isl_union_map_copy(TC_RED));
+    Deps = isl_union_map_union(Deps, isl_union_map_copy(D.TC_RED));
 
   Deps = isl_union_map_coalesce(Deps);
   Deps = isl_union_map_detect_equalities(Deps);
   return Deps;
 }
 
-bool Dependences::hasValidDependences() {
-  return (RAW != nullptr) && (WAR != nullptr) && (WAW != nullptr);
+bool DependenceInfo::hasValidDependences(Scop &S) {
+  Dependences &D = getDependences(S);
+  return (D.RAW != nullptr) && (D.WAR != nullptr) && (D.WAW != nullptr);
 }
 
-isl_map *Dependences::getReductionDependences(MemoryAccess *MA) {
-  return isl_map_copy(ReductionDependences[MA]);
+isl_map *DependenceInfo::getReductionDependences(Scop &S, MemoryAccess *MA) {
+  Dependences &D = getDependences(S);
+  return isl_map_copy(D.ReductionDependences[MA]);
 }
 
-void Dependences::setReductionDependences(MemoryAccess *MA, isl_map *D) {
-  assert(ReductionDependences.count(MA) == 0 &&
+void DependenceInfo::setReductionDependences(Scop &S, MemoryAccess *MA,
+                                             isl_map *Deps) {
+  Dependences &D = getDependences(S);
+  assert(D.ReductionDependences.count(MA) == 0 &&
          "Reduction dependences set twice!");
-  ReductionDependences[MA] = D;
+  D.ReductionDependences[MA] = Deps;
 }
 
-void Dependences::getAnalysisUsage(AnalysisUsage &AU) const {
+void DependenceInfo::getAnalysisUsage(AnalysisUsage &AU) const {
   ScopPass::getAnalysisUsage(AU);
 }
 
-char Dependences::ID = 0;
+char DependenceInfo::ID = 0;
 
-Pass *polly::createDependencesPass() { return new Dependences(); }
+Pass *polly::createDependenceInfoPass() { return new DependenceInfo(); }
 
-INITIALIZE_PASS_BEGIN(Dependences, "polly-dependences",
+INITIALIZE_PASS_BEGIN(DependenceInfo, "polly-dependences",
                       "Polly - Calculate dependences", false, false);
 INITIALIZE_PASS_DEPENDENCY(ScopInfo);
-INITIALIZE_PASS_END(Dependences, "polly-dependences",
+INITIALIZE_PASS_END(DependenceInfo, "polly-dependences",
                     "Polly - Calculate dependences", false, false)
Index: lib/Analysis/ScopInfo.cpp
===================================================================
--- lib/Analysis/ScopInfo.cpp
+++ lib/Analysis/ScopInfo.cpp
@@ -1968,20 +1968,14 @@
   return StmtMapIt->second;
 }
 
-//===----------------------------------------------------------------------===//
-ScopInfo::ScopInfo() : RegionPass(ID), scop(0) {
-  ctx = isl_ctx_alloc();
-  isl_options_set_on_error(ctx, ISL_ON_ERROR_ABORT);
-}
-
 ScopInfo::~ScopInfo() {
-  clear();
-  isl_ctx_free(ctx);
+  for (isl_ctx *Ctx : IslCtxs)
+    isl_ctx_free(Ctx);
 }
 
 void ScopInfo::getAnalysisUsage(AnalysisUsage &AU) const {
+  AU.addRequiredTransitive<RegionInfoPass>();
   AU.addRequired<LoopInfoWrapperPass>();
-  AU.addRequired<RegionInfoPass>();
   AU.addRequired<ScalarEvolution>();
   AU.addRequired<ScopDetection>();
   AU.addRequired<TempScopInfo>();
@@ -1989,53 +1983,63 @@
   AU.setPreservesAll();
 }
 
-bool ScopInfo::runOnRegion(Region *R, RGPassManager &RGM) {
+bool ScopInfo::runOnFunction(Function &F) {
   LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
   AliasAnalysis &AA = getAnalysis<AliasAnalysis>();
   ScopDetection &SD = getAnalysis<ScopDetection>();
   ScalarEvolution &SE = getAnalysis<ScalarEvolution>();
 
-  TempScop *tempScop = getAnalysis<TempScopInfo>().getTempScop(R);
+  for (ScopDetection::iterator I = SD.begin(), E = SD.end(); I != E; ++I) {
+    const Region *R = *I;
+    if (!SD.isMaxRegionInScop(*R))
+      continue;
 
-  // This region is no Scop.
-  if (!tempScop) {
-    scop = nullptr;
-    return false;
-  }
+    TempScop *tempScop = getAnalysis<TempScopInfo>().getTempScop(R);
+    assert(tempScop && "A valid region should have a TempScop");
 
-  scop = new Scop(*tempScop, LI, SE, SD, ctx);
+    isl_ctx *Ctx = isl_ctx_alloc();
+    isl_options_set_on_error(Ctx, ISL_ON_ERROR_ABORT);
+    IslCtxs.push_back(Ctx);
 
-  if (!PollyUseRuntimeAliasChecks) {
-    // Statistics.
-    ++ScopFound;
-    if (scop->getMaxLoopDepth() > 0)
-      ++RichScopFound;
-    return false;
-  }
+    Scop *S = new Scop(*tempScop, LI, SE, SD, Ctx);
 
-  // If a problem occurs while building the alias groups we need to delete
-  // this SCoP and pretend it wasn't valid in the first place.
-  if (scop->buildAliasGroups(AA)) {
+    if (PollyUseRuntimeAliasChecks && !S->buildAliasGroups(AA)) {
+      DEBUG(dbgs() << "\n\nNOTE: Run time checks for " << S->getNameStr()
+                   << " could not be created as the number of parameters "
+                      "involved is too high. The SCoP will be "
+                      "dismissed.\nUse:\n\t--polly-rtc-max-parameters=X\nto "
+                      "adjust the maximal number of parameters but be advised "
+                      "that the compile time might increase "
+                      "exponentially.\n\n");
+
+      delete S;
+      continue;
+    }
+
+    Scops.push_back(S);
+
+    // If a problem occurs while building the alias groups we need to delete
+    // this SCoP and pretend it wasn't valid in the first place.
     // Statistics.
     ++ScopFound;
-    if (scop->getMaxLoopDepth() > 0)
+    if (S->getMaxLoopDepth() > 0)
       ++RichScopFound;
-    return false;
   }
 
-  DEBUG(dbgs()
-        << "\n\nNOTE: Run time checks for " << scop->getNameStr()
-        << " could not be created as the number of parameters involved is too "
-           "high. The SCoP will be "
-           "dismissed.\nUse:\n\t--polly-rtc-max-parameters=X\nto adjust the "
-           "maximal number of parameters but be advised that the compile time "
-           "might increase exponentially.\n\n");
-
-  delete scop;
-  scop = nullptr;
   return false;
 }
 
+void ScopInfo::print(raw_ostream &OS, const Module *) const {
+  for (const Scop *S : *this)
+    S->print(OS);
+}
+
+void ScopInfo::releaseMemory() {
+  for (Scop *S : Scops)
+    delete S;
+  Scops.clear();
+}
+
 char ScopInfo::ID = 0;
 
 Pass *polly::createScopInfoPass() { return new ScopInfo(); }
Index: lib/Analysis/ScopPass.cpp
===================================================================
--- lib/Analysis/ScopPass.cpp
+++ lib/Analysis/ScopPass.cpp
@@ -17,17 +17,19 @@
 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);
 }
 
Index: lib/CMakeLists.txt
===================================================================
--- lib/CMakeLists.txt
+++ lib/CMakeLists.txt
@@ -104,7 +104,7 @@
 
 
 add_polly_library(Polly
-  Analysis/Dependences.cpp
+  Analysis/DependenceInfo.cpp
   Analysis/ScopDetection.cpp
   Analysis/ScopDetectionDiagnostic.cpp
   Analysis/ScopInfo.cpp
Index: lib/CodeGen/IslAst.cpp
===================================================================
--- lib/CodeGen/IslAst.cpp
+++ lib/CodeGen/IslAst.cpp
@@ -21,7 +21,7 @@
 
 #include "polly/CodeGen/CodeGeneration.h"
 #include "polly/CodeGen/IslAst.h"
-#include "polly/Dependences.h"
+#include "polly/DependenceInfo.h"
 #include "polly/LinkAllPasses.h"
 #include "polly/Options.h"
 #include "polly/ScopInfo.h"
@@ -73,7 +73,7 @@
 namespace polly {
 class IslAst {
 public:
-  IslAst(Scop *Scop, Dependences &D);
+  IslAst(Scop &S, DependenceInfo &D);
 
   ~IslAst();
 
@@ -86,11 +86,10 @@
   __isl_give isl_ast_expr *getRunCondition();
 
 private:
-  Scop *S;
   isl_ast_node *Root;
   isl_ast_expr *RunCondition;
 
-  void buildRunCondition(__isl_keep isl_ast_build *Build);
+  void buildRunCondition(__isl_keep isl_ast_build *Build, Scop &S);
 };
 } // End namespace polly.
 
@@ -107,11 +106,14 @@
 /// @brief Temporary information used when building the ast.
 struct AstBuildUserInfo {
   /// @brief Construct and initialize the helper struct for AST creation.
-  AstBuildUserInfo()
-      : Deps(nullptr), InParallelFor(false), LastForNodeId(nullptr) {}
+  AstBuildUserInfo(Scop &S)
+      : S(S), D(nullptr), InParallelFor(false), LastForNodeId(nullptr) {}
+
+  /// @brief The current SCoP.
+  Scop &S;
 
   /// @brief The dependence information used for the parallelism check.
-  Dependences *Deps;
+  DependenceInfo *D;
 
   /// @brief Flag to indicate that we are inside a parallel for node.
   bool InParallelFor;
@@ -189,28 +191,30 @@
 /// @brief Check if the current scheduling dimension is parallel
 ///
 /// In case the dimension is parallel we also check if any reduction
-/// dependences is broken when we exploit this parallelism. If so,
-/// @p IsReductionParallel will be set to true. The reduction dependences we use
+/// DependenceInfo is broken when we exploit this parallelism. If so,
+/// @p IsReductionParallel will be set to true. The reduction DependenceInfo we
+/// use
 /// to check are actually the union of the transitive closure of the initial
-/// reduction dependences together with their reveresal. Even though these
-/// dependences connect all iterations with each other (thus they are cyclic)
+/// reduction DependenceInfo together with their reveresal. Even though these
+/// DependenceInfo connect all iterations with each other (thus they are cyclic)
 /// we can perform the parallelism check as we are only interested in a zero
 /// (or non-zero) dependence distance on the dimension in question.
-static bool astScheduleDimIsParallel(__isl_keep isl_ast_build *Build,
-                                     Dependences *D,
+static bool astScheduleDimIsParallel(__isl_keep isl_ast_build *Build, Scop &S,
+                                     DependenceInfo *D,
                                      IslAstUserPayload *NodeInfo) {
-  if (!D->hasValidDependences())
+  if (!D->hasValidDependences(S))
     return false;
 
   isl_union_map *Schedule = isl_ast_build_get_schedule(Build);
-  isl_union_map *Deps = D->getDependences(
-      Dependences::TYPE_RAW | Dependences::TYPE_WAW | Dependences::TYPE_WAR);
+  isl_union_map *Deps =
+      D->getDependences(S, DependenceInfo::TYPE_RAW | DependenceInfo::TYPE_WAW |
+                               DependenceInfo::TYPE_WAR);
 
   if (!D->isParallel(Schedule, Deps, &NodeInfo->MinimalDependenceDistance) &&
       !isl_union_map_free(Schedule))
     return false;
 
-  isl_union_map *RedDeps = D->getDependences(Dependences::TYPE_TC_RED);
+  isl_union_map *RedDeps = D->getDependences(S, DependenceInfo::TYPE_TC_RED);
   if (!D->isParallel(Schedule, RedDeps))
     NodeInfo->IsReductionParallel = true;
 
@@ -218,8 +222,8 @@
     return true;
 
   // Annotate reduction parallel nodes with the memory accesses which caused the
-  // reduction dependences parallel execution of the node conflicts with.
-  for (const auto &MaRedPair : D->getReductionDependences()) {
+  // reduction DependenceInfo parallel execution of the node conflicts with.
+  for (const auto &MaRedPair : D->getReductionDependences(S)) {
     if (!MaRedPair.second)
       continue;
     RedDeps = isl_union_map_from_map(isl_map_copy(MaRedPair.second));
@@ -249,7 +253,7 @@
   // Test for parallelism only if we are not already inside a parallel loop
   if (!BuildInfo->InParallelFor)
     BuildInfo->InParallelFor = Payload->IsOutermostParallel =
-        astScheduleDimIsParallel(Build, BuildInfo->Deps, Payload);
+        astScheduleDimIsParallel(Build, BuildInfo->S, BuildInfo->D, Payload);
 
   return Id;
 }
@@ -282,7 +286,7 @@
       Payload->IsInnermostParallel = true;
     else
       Payload->IsInnermostParallel =
-          astScheduleDimIsParallel(Build, BuildInfo->Deps, Payload);
+          astScheduleDimIsParallel(Build, BuildInfo->S, BuildInfo->D, Payload);
   }
   if (Payload->IsOutermostParallel)
     BuildInfo->InParallelFor = false;
@@ -305,17 +309,17 @@
   return isl_ast_node_set_annotation(Node, Id);
 }
 
-void IslAst::buildRunCondition(__isl_keep isl_ast_build *Build) {
+void IslAst::buildRunCondition(__isl_keep isl_ast_build *Build, Scop &S) {
   // The conditions that need to be checked at run-time for this scop are
   // available as an isl_set in the AssumedContext from which we can directly
   // derive a run-time condition.
-  RunCondition = isl_ast_build_expr_from_set(Build, S->getAssumedContext());
+  RunCondition = isl_ast_build_expr_from_set(Build, S.getAssumedContext());
 
   // Create the alias checks from the minimal/maximal accesses in each alias
   // group. This operation is by construction quadratic in the number of
   // elements in each alias group.
   isl_ast_expr *NonAliasGroup, *MinExpr, *MaxExpr;
-  for (const Scop::MinMaxVectorTy *MinMaxAccesses : S->getAliasGroups()) {
+  for (const Scop::MinMaxVectorTy *MinMaxAccesses : S.getAliasGroups()) {
     auto AccEnd = MinMaxAccesses->end();
     for (auto AccIt0 = MinMaxAccesses->begin(); AccIt0 != AccEnd; ++AccIt0) {
       for (auto AccIt1 = AccIt0 + 1; AccIt1 != AccEnd; ++AccIt1) {
@@ -347,48 +351,47 @@
 ///       In order to improve the cost model we could either keep track of
 ///       performed optimizations (e.g., tiling) or compute properties on the
 ///       original as well as optimized SCoP (e.g., #stride-one-accesses).
-static bool benefitsFromPolly(Scop *Scop, bool PerformParallelTest) {
+static bool benefitsFromPolly(Scop &S, bool PerformParallelTest) {
 
   // First check the user choice.
   if (NoEarlyExit)
     return true;
 
   // Check if nothing interesting happened.
-  if (!PerformParallelTest && !Scop->isOptimized() &&
-      Scop->getAliasGroups().empty())
+  if (!PerformParallelTest && !S.isOptimized() && S.getAliasGroups().empty())
     return false;
 
   // The default assumption is that Polly improves the code.
   return true;
 }
 
-IslAst::IslAst(Scop *Scop, Dependences &D)
-    : S(Scop), Root(nullptr), RunCondition(nullptr) {
+IslAst::IslAst(Scop &S, DependenceInfo &D)
+    : Root(nullptr), RunCondition(nullptr) {
 
   bool PerformParallelTest = PollyParallel || DetectParallel ||
                              PollyVectorizerChoice != VECTORIZER_NONE;
 
   // Skip AST and code generation if there was no benefit achieved.
-  if (!benefitsFromPolly(Scop, PerformParallelTest))
+  if (!benefitsFromPolly(S, PerformParallelTest))
     return;
 
-  isl_ctx *Ctx = S->getIslCtx();
+  isl_ctx *Ctx = S.getIslCtx();
   isl_options_set_ast_build_atomic_upper_bound(Ctx, true);
   isl_ast_build *Build;
-  AstBuildUserInfo BuildInfo;
+  AstBuildUserInfo BuildInfo(S);
 
   if (UseContext)
-    Build = isl_ast_build_from_context(S->getContext());
+    Build = isl_ast_build_from_context(S.getContext());
   else
-    Build = isl_ast_build_from_context(isl_set_universe(S->getParamSpace()));
+    Build = isl_ast_build_from_context(isl_set_universe(S.getParamSpace()));
 
   Build = isl_ast_build_set_at_each_domain(Build, AtEachDomain, nullptr);
 
   isl_union_map *Schedule =
-      isl_union_map_intersect_domain(S->getSchedule(), S->getDomains());
+      isl_union_map_intersect_domain(S.getSchedule(), S.getDomains());
 
   if (PerformParallelTest) {
-    BuildInfo.Deps = &D;
+    BuildInfo.D = &D;
     BuildInfo.InParallelFor = 0;
 
     Build = isl_ast_build_set_before_each_for(Build, &astBuildBeforeFor,
@@ -397,7 +400,7 @@
         isl_ast_build_set_after_each_for(Build, &astBuildAfterFor, &BuildInfo);
   }
 
-  buildRunCondition(Build);
+  buildRunCondition(Build, S);
 
   Root = isl_ast_build_ast_from_schedule(Build, Schedule);
 
@@ -415,29 +418,32 @@
 }
 
 void IslAstInfo::releaseMemory() {
-  if (Ast) {
-    delete Ast;
-    Ast = nullptr;
-  }
+  for (const auto &AstMapPair : AstMap)
+    delete AstMapPair.getSecond();
+  AstMap.clear();
 }
 
-bool IslAstInfo::runOnScop(Scop &Scop) {
-  if (Ast)
-    delete Ast;
+void IslAstInfo::initializeScopPass() { DI = &getAnalysis<DependenceInfo>(); }
 
-  S = &Scop;
+bool IslAstInfo::runOnScop(Scop &S) {
 
-  Dependences &D = getAnalysis<Dependences>();
+  AstMap[&S] = new IslAst(S, *DI);
 
-  Ast = new IslAst(&Scop, D);
+  DEBUG(printScop(dbgs(), S));
 
-  DEBUG(printScop(dbgs(), Scop));
   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) {
@@ -519,7 +525,7 @@
 
 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()
@@ -530,7 +536,7 @@
     return;
   }
 
-  isl_ast_expr *RunCondition = getRunCondition();
+  isl_ast_expr *RunCondition = getRunCondition(S);
   char *RtCStr, *AstStr;
 
   Options = isl_ast_print_options_alloc(S.getIslCtx());
@@ -567,7 +573,7 @@
   // Get the Common analysis usage of ScopPasses.
   ScopPass::getAnalysisUsage(AU);
   AU.addRequired<ScopInfo>();
-  AU.addRequired<Dependences>();
+  AU.addRequired<DependenceInfo>();
 }
 
 char IslAstInfo::ID = 0;
@@ -578,6 +584,6 @@
                       "Polly - Generate an AST of the SCoP (isl)", false,
                       false);
 INITIALIZE_PASS_DEPENDENCY(ScopInfo);
-INITIALIZE_PASS_DEPENDENCY(Dependences);
+INITIALIZE_PASS_DEPENDENCY(DependenceInfo);
 INITIALIZE_PASS_END(IslAstInfo, "polly-ast",
                     "Polly - Generate an AST from the SCoP (isl)", false, false)
Index: lib/CodeGen/IslCodeGeneration.cpp
===================================================================
--- lib/CodeGen/IslCodeGeneration.cpp
+++ lib/CodeGen/IslCodeGeneration.cpp
@@ -25,7 +25,7 @@
 #include "polly/CodeGen/IslAst.h"
 #include "polly/CodeGen/LoopGenerators.h"
 #include "polly/CodeGen/Utils.h"
-#include "polly/Dependences.h"
+#include "polly/DependenceInfo.h"
 #include "polly/LinkAllPasses.h"
 #include "polly/ScopInfo.h"
 #include "polly/Support/GICHelper.h"
@@ -913,9 +913,10 @@
   /// 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;
@@ -940,18 +941,21 @@
     return true;
   }
 
-  bool runOnScop(Scop &S) override {
+  /// @brief Initializer called once per function.
+  void initializeScopPass() override {
     AI = &getAnalysis<IslAstInfo>();
-
-    // Check if we created an isl_ast root node, otherwise exit.
-    isl_ast_node *AstRoot = AI->getAst();
-    if (!AstRoot)
-      return false;
-
     LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
     DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
     SE = &getAnalysis<ScalarEvolution>();
     DL = &getAnalysis<DataLayoutPass>().getDataLayout();
+  }
+
+  bool runOnScop(Scop &S) override {
+
+    // Check if we created an isl_ast root node, otherwise exit.
+    isl_ast_node *AstRoot = AI->getAst(S);
+    if (!AstRoot)
+      return false;
 
     assert(!S.getRegion().isTopLevelRegion() &&
            "Top level regions are not supported");
@@ -966,7 +970,7 @@
     IslNodeBuilder NodeBuilder(Builder, Annotator, this, *DL, *LI, *SE, *DT, S);
     NodeBuilder.addParameters(S.getContext());
 
-    Value *RTC = buildRTC(Builder, NodeBuilder.getExprBuilder());
+    Value *RTC = buildRTC(S, Builder, NodeBuilder.getExprBuilder());
     BasicBlock *StartBlock = executeScopConditionally(S, this, RTC);
     Builder.SetInsertPoint(StartBlock->begin());
 
@@ -989,7 +993,7 @@
     AU.addRequired<ScopInfo>();
     AU.addRequired<LoopInfoWrapperPass>();
 
-    AU.addPreserved<Dependences>();
+    AU.addPreserved<DependenceInfo>();
 
     AU.addPreserved<LoopInfoWrapperPass>();
     AU.addPreserved<DominatorTreeWrapperPass>();
@@ -1013,7 +1017,6 @@
 
 INITIALIZE_PASS_BEGIN(IslCodeGeneration, "polly-codegen-isl",
                       "Polly - Create LLVM-IR from SCoPs", false, false);
-INITIALIZE_PASS_DEPENDENCY(Dependences);
 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass);
 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass);
 INITIALIZE_PASS_DEPENDENCY(RegionInfoPass);
Index: lib/Exchange/JSONExporter.cpp
===================================================================
--- lib/Exchange/JSONExporter.cpp
+++ lib/Exchange/JSONExporter.cpp
@@ -12,7 +12,7 @@
 //===----------------------------------------------------------------------===//
 
 #include "polly/LinkAllPasses.h"
-#include "polly/Dependences.h"
+#include "polly/DependenceInfo.h"
 #include "polly/Options.h"
 #include "polly/ScopInfo.h"
 #include "polly/ScopPass.h"
@@ -61,9 +61,12 @@
 
   std::string getFileName(Scop &S) const;
   Json::Value getJSON(Scop &S) const;
-  virtual bool runOnScop(Scop &S);
-  void printScop(raw_ostream &OS, Scop &S) const;
-  void getAnalysisUsage(AnalysisUsage &AU) const;
+  bool runOnScop(Scop &S) override;
+  void printScop(raw_ostream &OS, Scop &S) const override;
+  void getAnalysisUsage(AnalysisUsage &AU) const override;
+
+  /// @brief Initializer called once per function.
+  void initializeScopPass() override {}
 };
 
 struct JSONImporter : public ScopPass {
@@ -72,9 +75,12 @@
   explicit JSONImporter() : ScopPass(ID) {}
 
   std::string getFileName(Scop &S) const;
-  virtual bool runOnScop(Scop &S);
-  void printScop(raw_ostream &OS, Scop &S) const;
-  void getAnalysisUsage(AnalysisUsage &AU) const;
+  bool runOnScop(Scop &S) override;
+  void printScop(raw_ostream &OS, Scop &S) const override;
+  void getAnalysisUsage(AnalysisUsage &AU) const override;
+
+  /// @brief Initializer called once per function.
+  void initializeScopPass() override {}
 };
 }
 
@@ -178,11 +184,11 @@
     OS << "New access function '" << *I << "'detected in JSCOP file\n";
 }
 
-typedef Dependences::StatementToIslMapTy StatementToIslMapTy;
+typedef DependenceInfo::StatementToIslMapTy StatementToIslMapTy;
 
 bool JSONImporter::runOnScop(Scop &S) {
   Region &R = S.getRegion();
-  Dependences *D = &getAnalysis<Dependences>();
+  DependenceInfo *D = &getAnalysis<DependenceInfo>();
   const DataLayout &DL = getAnalysis<DataLayoutPass>().getDataLayout();
 
   std::string FileName = ImportDir + "/" + getFileName(S);
@@ -239,9 +245,10 @@
     index++;
   }
 
-  if (!D->isValidScattering(&NewScattering)) {
-    errs() << "JScop file contains a scattering that changes the "
-           << "dependences. Use -disable-polly-legality to continue anyways\n";
+  if (!D->isValidScattering(S, &NewScattering)) {
+    errs()
+        << "JScop file contains a scattering that changes the "
+        << "DependenceInfo. Use -disable-polly-legality to continue anyways\n";
     for (StatementToIslMapTy::iterator SI = NewScattering.begin(),
                                        SE = NewScattering.end();
          SI != SE; ++SI)
@@ -355,7 +362,7 @@
 
 void JSONImporter::getAnalysisUsage(AnalysisUsage &AU) const {
   ScopPass::getAnalysisUsage(AU);
-  AU.addRequired<Dependences>();
+  AU.addRequired<DependenceInfo>();
   AU.addRequired<DataLayoutPass>();
 }
 Pass *polly::createJSONImporterPass() { return new JSONImporter(); }
@@ -364,7 +371,7 @@
                       "Polly - Export Scops as JSON"
                       " (Writes a .jscop file for each Scop)",
                       false, false);
-INITIALIZE_PASS_DEPENDENCY(Dependences)
+INITIALIZE_PASS_DEPENDENCY(DependenceInfo)
 INITIALIZE_PASS_END(JSONExporter, "polly-export-jscop",
                     "Polly - Export Scops as JSON"
                     " (Writes a .jscop file for each Scop)",
@@ -374,7 +381,7 @@
                       "Polly - Import Scops from JSON"
                       " (Reads a .jscop file for each Scop)",
                       false, false);
-INITIALIZE_PASS_DEPENDENCY(Dependences)
+INITIALIZE_PASS_DEPENDENCY(DependenceInfo)
 INITIALIZE_PASS_DEPENDENCY(DataLayoutPass)
 INITIALIZE_PASS_END(JSONImporter, "polly-import-jscop",
                     "Polly - Import Scops from JSON"
Index: lib/Makefile
===================================================================
--- lib/Makefile
+++ lib/Makefile
@@ -119,7 +119,7 @@
 	 Support/SCEVValidator.cpp \
 	 Support/RegisterPasses.cpp \
 	 Support/ScopHelper.cpp \
-	 Analysis/Dependences.cpp \
+	 Analysis/DependenceInfo.cpp \
 	 Analysis/ScopDetection.cpp \
 	 Analysis/ScopDetectionDiagnostic.cpp \
 	 Analysis/ScopInfo.cpp \
Index: lib/Support/RegisterPasses.cpp
===================================================================
--- lib/Support/RegisterPasses.cpp
+++ lib/Support/RegisterPasses.cpp
@@ -22,7 +22,7 @@
 #include "polly/RegisterPasses.h"
 #include "polly/Canonicalization.h"
 #include "polly/CodeGen/CodeGeneration.h"
-#include "polly/Dependences.h"
+#include "polly/DependenceInfo.h"
 #include "polly/LinkAllPasses.h"
 #include "polly/Options.h"
 #include "polly/ScopDetection.h"
@@ -142,7 +142,7 @@
   initializeIslCodeGenerationPass(Registry);
   initializeCodePreparationPass(Registry);
   initializeDeadCodeElimPass(Registry);
-  initializeDependencesPass(Registry);
+  initializeDependenceInfoPass(Registry);
   initializeIndependentBlocksPass(Registry);
   initializeJSONExporterPass(Registry);
   initializeJSONImporterPass(Registry);
Index: lib/Transform/DeadCodeElimination.cpp
===================================================================
--- lib/Transform/DeadCodeElimination.cpp
+++ lib/Transform/DeadCodeElimination.cpp
@@ -32,7 +32,7 @@
 //
 //===----------------------------------------------------------------------===//
 
-#include "polly/Dependences.h"
+#include "polly/DependenceInfo.h"
 #include "polly/LinkAllPasses.h"
 #include "polly/ScopInfo.h"
 #include "llvm/Support/CommandLine.h"
@@ -60,10 +60,16 @@
 
   bool runOnScop(Scop &S) override;
 
+  /// @brief Initializer called once per function.
+  void initializeScopPass() override;
+
   void printScop(raw_ostream &OS, Scop &S) const override;
   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
@@ -112,14 +118,12 @@
 /// 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) {
-  Dependences *D = &getAnalysis<Dependences>();
-
-  if (!D->hasValidDependences())
+  if (!DI->hasValidDependences(S))
     return false;
 
   isl_union_set *Live = getLiveOut(S);
-  isl_union_map *Dep =
-      D->getDependences(Dependences::TYPE_RAW | Dependences::TYPE_RED);
+  isl_union_map *Dep = DI->getDependences(S, DependenceInfo::TYPE_RAW |
+                                                 DependenceInfo::TYPE_RED);
   Dep = isl_union_map_reverse(Dep);
 
   if (PreciseSteps == -1)
@@ -153,13 +157,15 @@
 
   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)
-    D->recomputeDependences();
+    DI->recomputeDependences(S);
   return Changed;
 }
 
+void DeadCodeElim::initializeScopPass() { DI = &getAnalysis<DependenceInfo>(); }
+
 bool DeadCodeElim::runOnScop(Scop &S) {
   return eliminateDeadCode(S, DCEPreciseSteps);
 }
@@ -168,14 +174,14 @@
 
 void DeadCodeElim::getAnalysisUsage(AnalysisUsage &AU) const {
   ScopPass::getAnalysisUsage(AU);
-  AU.addRequired<Dependences>();
+  AU.addRequired<DependenceInfo>();
 }
 
 Pass *polly::createDeadCodeElimPass() { return new DeadCodeElim(); }
 
 INITIALIZE_PASS_BEGIN(DeadCodeElim, "polly-dce",
                       "Polly - Remove dead iterations", false, false)
-INITIALIZE_PASS_DEPENDENCY(Dependences)
+INITIALIZE_PASS_DEPENDENCY(DependenceInfo)
 INITIALIZE_PASS_DEPENDENCY(ScopInfo)
 INITIALIZE_PASS_END(DeadCodeElim, "polly-dce", "Polly - Remove dead iterations",
                     false, false)
Index: lib/Transform/ScheduleOptimizer.cpp
===================================================================
--- lib/Transform/ScheduleOptimizer.cpp
+++ lib/Transform/ScheduleOptimizer.cpp
@@ -26,7 +26,7 @@
 #include "isl/schedule.h"
 #include "isl/space.h"
 #include "polly/CodeGen/CodeGeneration.h"
-#include "polly/Dependences.h"
+#include "polly/DependenceInfo.h"
 #include "polly/LinkAllPasses.h"
 #include "polly/Options.h"
 #include "polly/ScopInfo.h"
@@ -49,13 +49,13 @@
 
 static cl::opt<std::string>
     OptimizeDeps("polly-opt-optimize-only",
-                 cl::desc("Only a certain kind of dependences (all/raw)"),
+                 cl::desc("Only a certain kind of DependenceInfo (all/raw)"),
                  cl::Hidden, cl::init("all"), cl::ZeroOrMore,
                  cl::cat(PollyCategory));
 
 static cl::opt<std::string>
     SimplifyDeps("polly-opt-simplify-deps",
-                 cl::desc("Dependences should be simplified (yes/no)"),
+                 cl::desc("DependenceInfo should be simplified (yes/no)"),
                  cl::Hidden, cl::init("yes"), cl::ZeroOrMore,
                  cl::cat(PollyCategory));
 
@@ -99,11 +99,17 @@
 
   ~IslScheduleOptimizer() { isl_schedule_free(LastSchedule); }
 
+  /// @brief Initializer called once per function.
+  void initializeScopPass() override;
+
   bool runOnScop(Scop &S) override;
   void printScop(raw_ostream &OS, Scop &S) const override;
   void getAnalysisUsage(AnalysisUsage &AU) const override;
 
 private:
+  /// @brief The dependence info pass.
+  DependenceInfo *DI;
+
   isl_schedule *LastSchedule;
 
   /// @brief Decide if the @p NewSchedule is profitable for @p S.
@@ -204,7 +210,7 @@
 
   using llvm::Pass::doFinalization;
 
-  virtual bool doFinalization() override {
+  virtual bool doFinalization(Module &) override {
     isl_schedule_free(LastSchedule);
     LastSchedule = nullptr;
     return true;
@@ -472,6 +478,10 @@
   return changed;
 }
 
+void IslScheduleOptimizer::initializeScopPass() {
+  DI = &getAnalysis<DependenceInfo>();
+}
+
 bool IslScheduleOptimizer::runOnScop(Scop &S) {
 
   // Skip empty SCoPs but still allow code generation as it will delete the
@@ -481,29 +491,27 @@
     return false;
   }
 
-  Dependences *D = &getAnalysis<Dependences>();
-
-  if (!D->hasValidDependences())
+  if (!DI->hasValidDependences(S))
     return false;
 
   isl_schedule_free(LastSchedule);
   LastSchedule = nullptr;
 
   // Build input data.
-  int ValidityKinds =
-      Dependences::TYPE_RAW | Dependences::TYPE_WAR | Dependences::TYPE_WAW;
+  int ValidityKinds = DependenceInfo::TYPE_RAW | DependenceInfo::TYPE_WAR |
+                      DependenceInfo::TYPE_WAW;
   int ProximityKinds;
 
   if (OptimizeDeps == "all")
-    ProximityKinds =
-        Dependences::TYPE_RAW | Dependences::TYPE_WAR | Dependences::TYPE_WAW;
+    ProximityKinds = DependenceInfo::TYPE_RAW | DependenceInfo::TYPE_WAR |
+                     DependenceInfo::TYPE_WAW;
   else if (OptimizeDeps == "raw")
-    ProximityKinds = Dependences::TYPE_RAW;
+    ProximityKinds = DependenceInfo::TYPE_RAW;
   else {
     errs() << "Do not know how to optimize for '" << OptimizeDeps << "'"
-           << " Falling back to optimizing all dependences.\n";
-    ProximityKinds =
-        Dependences::TYPE_RAW | Dependences::TYPE_WAR | Dependences::TYPE_WAW;
+           << " Falling back to optimizing all DependenceInfo.\n";
+    ProximityKinds = DependenceInfo::TYPE_RAW | DependenceInfo::TYPE_WAR |
+                     DependenceInfo::TYPE_WAW;
   }
 
   isl_union_set *Domain = S.getDomains();
@@ -511,13 +519,13 @@
   if (!Domain)
     return false;
 
-  isl_union_map *Validity = D->getDependences(ValidityKinds);
-  isl_union_map *Proximity = D->getDependences(ProximityKinds);
+  isl_union_map *Validity = DI->getDependences(S, ValidityKinds);
+  isl_union_map *Proximity = DI->getDependences(S, ProximityKinds);
 
-  // Simplify the dependences by removing the constraints introduced by the
+  // Simplify the DependenceInfo by removing the constraints introduced by the
   // domains. This can speed up the scheduling time significantly, as large
-  // constant coefficients will be removed from the dependences. The
-  // introduction of some additional dependences reduces the possible
+  // constant coefficients will be removed from the DependenceInfo. The
+  // introduction of some additional DependenceInfo reduces the possible
   // transformations, but in most cases, such transformation do not seem to be
   // interesting anyway. In some cases this option may stop the scheduler to
   // find any schedule.
@@ -648,7 +656,7 @@
 
 void IslScheduleOptimizer::getAnalysisUsage(AnalysisUsage &AU) const {
   ScopPass::getAnalysisUsage(AU);
-  AU.addRequired<Dependences>();
+  AU.addRequired<DependenceInfo>();
 }
 
 Pass *polly::createIslScheduleOptimizerPass() {
@@ -657,7 +665,7 @@
 
 INITIALIZE_PASS_BEGIN(IslScheduleOptimizer, "polly-opt-isl",
                       "Polly - Optimize schedule of SCoP", false, false);
-INITIALIZE_PASS_DEPENDENCY(Dependences);
+INITIALIZE_PASS_DEPENDENCY(DependenceInfo);
 INITIALIZE_PASS_DEPENDENCY(ScopInfo);
 INITIALIZE_PASS_END(IslScheduleOptimizer, "polly-opt-isl",
                     "Polly - Optimize schedule of SCoP", false, false)
Index: test/DependenceInfo/computeout.ll
===================================================================
--- test/DependenceInfo/computeout.ll
+++ test/DependenceInfo/computeout.ll
@@ -51,7 +51,8 @@
   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:
@@ -63,7 +64,8 @@
 ; VALUE:       Stmt_S1[i0] -> Stmt_S3[i0] : i0 >= 10 and i0 <= 99
 ; 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:
Index: test/DependenceInfo/sequential_loops.ll
===================================================================
--- test/DependenceInfo/sequential_loops.ll
+++ test/DependenceInfo/sequential_loops.ll
@@ -51,7 +51,8 @@
   ret void
 }
 
-; VALUE: 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:
@@ -63,7 +64,8 @@
 ; VALUE:       Stmt_S1[i0] -> Stmt_S3[i0] : i0 >= 10 and i0 <= 99
 ; VALUE:     }
 
-; MEMORY: 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:
@@ -126,7 +128,8 @@
   ret void
 }
 
-; VALUE: 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 >= 0 and i0 <= 9;
@@ -139,7 +142,8 @@
 ; VALUE:       Stmt_S1[i0] -> Stmt_S2[i0] : i0 >= 0 and i0 <= 9
 ; VALUE:     }
 
-; MEMORY: 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;
@@ -203,7 +207,8 @@
   ret void
 }
 
-; VALUE: 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:     }
@@ -217,7 +222,8 @@
 ; VALUE:       Stmt_S2[i0] -> Stmt_S3[i0] : i0 >= 0 and i0 <= 9
 ; VALUE:     }
 
-; MEMORY: 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:     }
@@ -269,7 +275,8 @@
   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] :
@@ -282,7 +289,8 @@
 ; 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] :
Index: test/Dependences/do_pluto_matmult.ll
===================================================================
--- /dev/null
+++ test/Dependences/do_pluto_matmult.ll
@@ -1,81 +0,0 @@
-; RUN: opt %loadPolly -polly-detect-unprofitable -basicaa -polly-dependences -analyze -polly-dependences-analysis-type=value-based < %s | FileCheck %s -check-prefix=VALUE
-; RUN: opt %loadPolly -polly-detect-unprofitable -basicaa -polly-dependences -analyze -polly-dependences-analysis-type=memory-based -polly-delinearize < %s | FileCheck %s -check-prefix=MEMORY
-
-target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"
-target triple = "x86_64-unknown-linux-gnu"
-
-%struct._IO_FILE = type { i32, i8*, i8*, i8*, i8*, i8*, i8*, i8*, i8*, i8*, i8*, i8*, %struct._IO_marker*, %struct._IO_FILE*, i32, i32, i64, i16, i8, [1 x i8], i8*, i64, i8*, i8*, i8*, i8*, i64, i32, [20 x i8] }
-%struct._IO_marker = type { %struct._IO_marker*, %struct._IO_FILE*, i32 }
-
-@A = common global [36 x [49 x double]] zeroinitializer, align 8 ; <[36 x [49 x double]]*> [#uses=3]
-@B = common global [36 x [49 x double]] zeroinitializer, align 8 ; <[36 x [49 x double]]*> [#uses=3]
-@C = common global [36 x [49 x double]] zeroinitializer, align 8 ; <[36 x [49 x double]]*> [#uses=4]
-
-define void @do_pluto_matmult() nounwind {
-entry:
-  fence seq_cst
-  br label %do.body
-
-do.body:                                          ; preds = %do.cond42, %entry
-  %indvar3 = phi i64 [ %indvar.next4, %do.cond42 ], [ 0, %entry ] ; <i64> [#uses=3]
-  br label %do.body1
-
-do.body1:                                         ; preds = %do.cond36, %do.body
-  %indvar1 = phi i64 [ %indvar.next2, %do.cond36 ], [ 0, %do.body ] ; <i64> [#uses=3]
-  %arrayidx5 = getelementptr [36 x [49 x double]], [36 x [49 x double]]* @C, i64 0, i64 %indvar3, i64 %indvar1 ; <double*> [#uses=2]
-  br label %do.body2
-
-do.body2:                                         ; preds = %do.cond, %do.body1
-  %indvar = phi i64 [ %indvar.next, %do.cond ], [ 0, %do.body1 ] ; <i64> [#uses=3]
-  %arrayidx13 = getelementptr [36 x [49 x double]], [36 x [49 x double]]* @A, i64 0, i64 %indvar3, i64 %indvar ; <double*> [#uses=1]
-  %arrayidx22 = getelementptr [36 x [49 x double]], [36 x [49 x double]]* @B, i64 0, i64 %indvar, i64 %indvar1 ; <double*> [#uses=1]
-  %tmp6 = load double, double* %arrayidx5                 ; <double> [#uses=1]
-  %mul = fmul double 1.000000e+00, %tmp6          ; <double> [#uses=1]
-  %tmp14 = load double, double* %arrayidx13               ; <double> [#uses=1]
-  %mul15 = fmul double 1.000000e+00, %tmp14       ; <double> [#uses=1]
-  %tmp23 = load double, double* %arrayidx22               ; <double> [#uses=1]
-  %mul24 = fmul double %mul15, %tmp23             ; <double> [#uses=1]
-  %add = fadd double %mul, %mul24                 ; <double> [#uses=1]
-  store double %add, double* %arrayidx5
-  br label %do.cond
-
-do.cond:                                          ; preds = %do.body2
-  %indvar.next = add i64 %indvar, 1               ; <i64> [#uses=2]
-  %exitcond = icmp ne i64 %indvar.next, 36        ; <i1> [#uses=1]
-  br i1 %exitcond, label %do.body2, label %do.end
-
-do.end:                                           ; preds = %do.cond
-  br label %do.cond36
-
-do.cond36:                                        ; preds = %do.end
-  %indvar.next2 = add i64 %indvar1, 1             ; <i64> [#uses=2]
-  %exitcond5 = icmp ne i64 %indvar.next2, 36      ; <i1> [#uses=1]
-  br i1 %exitcond5, label %do.body1, label %do.end39
-
-do.end39:                                         ; preds = %do.cond36
-  br label %do.cond42
-
-do.cond42:                                        ; preds = %do.end39
-  %indvar.next4 = add i64 %indvar3, 1             ; <i64> [#uses=2]
-  %exitcond6 = icmp ne i64 %indvar.next4, 36      ; <i1> [#uses=1]
-  br i1 %exitcond6, label %do.body, label %do.end45
-
-do.end45:                                         ; preds = %do.cond42
-  fence seq_cst
-  ret void
-}
-
-; VALUE: RAW dependences:
-; VALUE: { Stmt_do_body2[i0, i1, i2] -> Stmt_do_body2[i0, i1, 1 + i2] : i0 >= 0 and i0 <= 35 and i1 >= 0 and i1 <= 35 and i2 >= 0 and i2 <= 34 }
-; VALUE: WAR dependences:
-; VALUE: {  }
-; VALUE: WAW dependences:
-; VALUE: { Stmt_do_body2[i0, i1, i2] -> Stmt_do_body2[i0, i1, 1 + i2] : i0 <= 35 and i0 >= 0 and i1 <= 35 and i1 >= 0 and i2 <= 34 and i2 >= 0 }
-
-
-; MEMORY: RAW dependences:
-; MEMORY:  { Stmt_do_body2[i0, i1, i2] -> Stmt_do_body2[i0, i1, o2] : i0 <= 35 and i0 >= 0 and i1 <= 35 and i1 >= 0 and i2 >= 0 and o2 >= 1 + i2 and o2 <= 35 and o2 >= 0 }
-; MEMORY: WAR dependences:
-; MEMORY:  { Stmt_do_body2[i0, i1, i2] -> Stmt_do_body2[i0, i1, o2] : i0 <= 35 and i0 >= 0 and i1 <= 35 and i1 >= 0 and i2 >= 0 and o2 >= 1 + i2 and o2 <= 35 and o2 >= 0 }
-; MEMORY: WAW dependences:
-; MEMORY:  { Stmt_do_body2[i0, i1, i2] -> Stmt_do_body2[i0, i1, o2] : i0 <= 35 and i0 >= 0 and i1 <= 35 and i1 >= 0 and i2 >= 0 and o2 >= 1 + i2 and o2 <= 35 and o2 >= 0 }
Index: test/Dependences/reduction_complex_location.ll
===================================================================
--- /dev/null
+++ test/Dependences/reduction_complex_location.ll
@@ -1,59 +0,0 @@
-; RUN: opt -basicaa %loadPolly -polly-detect-unprofitable -polly-dependences -analyze < %s | FileCheck %s
-;
-; CHECK: RAW dependences:
-; CHECK:   {  }
-; CHECK: WAR dependences:
-; CHECK:   {  }
-; CHECK: WAW dependences:
-; CHECK:   {  }
-; CHECK: Reduction dependences:
-; CHECK:   { Stmt_for_body3[i0, i1] -> Stmt_for_body3[2 + i0, -1 + i1] : i0 <= 97 and i0 >= 0 and i1 <= 99 and i1 >= 1 }
-;
-; void f(int *sum) {
-;   for (int i = 0; i < 100; i++)
-;     for (int j = 0; j < 100; j++)
-;       sum[i+j*2] += j * i;
-; }
-target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-n32-S64"
-
-define void @f(i32* %sum) {
-entry:
-  br label %for.cond
-
-for.cond:                                         ; preds = %for.inc6, %entry
-  %i.0 = phi i32 [ 0, %entry ], [ %inc7, %for.inc6 ]
-  %exitcond1 = icmp ne i32 %i.0, 100
-  br i1 %exitcond1, label %for.body, label %for.end8
-
-for.body:                                         ; preds = %for.cond
-  br label %for.cond1
-
-for.cond1:                                        ; preds = %for.inc, %for.body
-  %j.0 = phi i32 [ 0, %for.body ], [ %inc, %for.inc ]
-  %exitcond = icmp ne i32 %j.0, 100
-  br i1 %exitcond, label %for.body3, label %for.end
-
-for.body3:                                        ; preds = %for.cond1
-  %mul = mul nsw i32 %j.0, %i.0
-  %mul4 = shl nsw i32 %j.0, 1
-  %add = add nsw i32 %i.0, %mul4
-  %arrayidx = getelementptr inbounds i32, i32* %sum, i32 %add
-  %tmp = load i32, i32* %arrayidx, align 4
-  %add5 = add nsw i32 %tmp, %mul
-  store i32 %add5, i32* %arrayidx, align 4
-  br label %for.inc
-
-for.inc:                                          ; preds = %for.body3
-  %inc = add nsw i32 %j.0, 1
-  br label %for.cond1
-
-for.end:                                          ; preds = %for.cond1
-  br label %for.inc6
-
-for.inc6:                                         ; preds = %for.end
-  %inc7 = add nsw i32 %i.0, 1
-  br label %for.cond
-
-for.end8:                                         ; preds = %for.cond
-  ret void
-}
Index: test/Dependences/reduction_dependences_equal_non_reduction_dependences.ll
===================================================================
--- /dev/null
+++ test/Dependences/reduction_dependences_equal_non_reduction_dependences.ll
@@ -1,62 +0,0 @@
-; RUN: opt %loadPolly -polly-detect-unprofitable -basicaa -polly-dependences -analyze < %s | FileCheck %s
-;
-; This loopnest contains a reduction which imposes the same dependences as the
-; accesses to the array A. We need to ensure we keep the dependences of A.
-;
-; CHECK: RAW dependences:
-; CHECK:   { Stmt_for_body[i0] -> Stmt_for_body[1 + i0] : i0 >= 0 and i0 <= 1022 }
-; CHECK: WAR dependences:
-; CHECK:   {  }
-; CHECK: WAW dependences:
-; CHECK:   { Stmt_for_body[i0] -> Stmt_for_body[1 + i0] : i0 <= 1022 and i0 >= 0 }
-; CHECK: Reduction dependences:
-; CHECK:   { Stmt_for_body[i0] -> Stmt_for_body[1 + i0] : i0 <= 1022 and i0 >= 0 }
-;
-;
-;    void AandSum(int *restrict sum, int *restrict A) {
-;      for (int i = 0; i < 1024; i++) {
-;        A[i] = A[i] + A[i - 1];
-;        A[i - 1] = A[i] + A[i - 2];
-;        *sum += i;
-;      }
-;    }
-;
-target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-n32-S64"
-
-define void @AandSum(i32* noalias %sum, i32* noalias %A) {
-entry:
-  br label %for.cond
-
-for.cond:                                         ; preds = %for.inc, %entry
-  %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
-  %exitcond = icmp ne i32 %i.0, 1024
-  br i1 %exitcond, label %for.body, label %for.end
-
-for.body:                                         ; preds = %for.cond
-  %arrayidx = getelementptr inbounds i32, i32* %A, i32 %i.0
-  %tmp = load i32, i32* %arrayidx, align 4
-  %sub = add nsw i32 %i.0, -1
-  %arrayidx1 = getelementptr inbounds i32, i32* %A, i32 %sub
-  %tmp1 = load i32, i32* %arrayidx1, align 4
-  %add = add nsw i32 %tmp, %tmp1
-  %arrayidx2 = getelementptr inbounds i32, i32* %A, i32 %i.0
-  store i32 %add, i32* %arrayidx2, align 4
-  %sub4 = add nsw i32 %i.0, -2
-  %arrayidx5 = getelementptr inbounds i32, i32* %A, i32 %sub4
-  %tmp2 = load i32, i32* %arrayidx5, align 4
-  %add6 = add nsw i32 %add, %tmp2
-  %sub7 = add nsw i32 %i.0, -1
-  %arrayidx8 = getelementptr inbounds i32, i32* %A, i32 %sub7
-  store i32 %add6, i32* %arrayidx8, align 4
-  %tmp3 = load i32, i32* %sum, align 4
-  %add9 = add nsw i32 %tmp3, %i.0
-  store i32 %add9, i32* %sum, align 4
-  br label %for.inc
-
-for.inc:                                          ; preds = %for.body
-  %inc = add nsw i32 %i.0, 1
-  br label %for.cond
-
-for.end:                                          ; preds = %for.cond
-  ret void
-}
Index: test/Dependences/reduction_mixed_reduction_and_non_reduction_dependences.ll
===================================================================
--- /dev/null
+++ test/Dependences/reduction_mixed_reduction_and_non_reduction_dependences.ll
@@ -1,59 +0,0 @@
-; RUN: opt %loadPolly -polly-detect-unprofitable -polly-dependences -analyze < %s | FileCheck %s
-;
-; CHECK: RAW dependences:
-; CHECK-DAG: Stmt_for_body3[i0, i1] -> Stmt_for_body3[i0 + i1, o1] : i1 <= 1023 - i0 and i1 >= 0 and i1 <= 1 and i0 >= 0 and o1 <= 511 and o1 >= 1 
-; CHECK: WAR dependences:
-; CHECK:   {  }
-; CHECK: WAW dependences:
-; CHECK-DAG: Stmt_for_body3[i0, i1] -> Stmt_for_body3[1 + i0, -1 + i1] : i0 <= 1022 and i0 >= 0 and i1 <= 511 and i1 >= 2
-; CHECK-DAG: Stmt_for_body3[i0, 2] -> Stmt_for_body3[2 + i0, 0] : i0 <= 1021 and i0 >= 0
-; CHECK: Reduction dependences:
-; CHECK:   { Stmt_for_body3[i0, 1] -> Stmt_for_body3[1 + i0, 0] : i0 <= 1022 and i0 >= 0 }
-;
-; void f(int *sum) {
-;   for (int i = 0; i < 1024; i++)
-;     for (int j = 0; j < 512; j++)
-;       sum[i + j] = sum[i] + 3;
-; }
-target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-n32-S64"
-
-define void @f(i32* %sum) {
-entry:
-  br label %for.cond
-
-for.cond:                                         ; preds = %for.inc6, %entry
-  %i.0 = phi i32 [ 0, %entry ], [ %inc7, %for.inc6 ]
-  %exitcond1 = icmp ne i32 %i.0, 1024
-  br i1 %exitcond1, label %for.body, label %for.end8
-
-for.body:                                         ; preds = %for.cond
-  br label %for.cond1
-
-for.cond1:                                        ; preds = %for.inc, %for.body
-  %j.0 = phi i32 [ 0, %for.body ], [ %inc, %for.inc ]
-  %exitcond = icmp ne i32 %j.0, 512
-  br i1 %exitcond, label %for.body3, label %for.end
-
-for.body3:                                        ; preds = %for.cond1
-  %arrayidx = getelementptr inbounds i32, i32* %sum, i32 %i.0
-  %tmp = load i32, i32* %arrayidx, align 4
-  %add = add nsw i32 %tmp, 3
-  %add4 = add nsw i32 %i.0, %j.0
-  %arrayidx5 = getelementptr inbounds i32, i32* %sum, i32 %add4
-  store i32 %add, i32* %arrayidx5, align 4
-  br label %for.inc
-
-for.inc:                                          ; preds = %for.body3
-  %inc = add nsw i32 %j.0, 1
-  br label %for.cond1
-
-for.end:                                          ; preds = %for.cond1
-  br label %for.inc6
-
-for.inc6:                                         ; preds = %for.end
-  %inc7 = add nsw i32 %i.0, 1
-  br label %for.cond
-
-for.end8:                                         ; preds = %for.cond
-  ret void
-}
Index: test/Dependences/reduction_multiple_loops_array_sum.ll
===================================================================
--- /dev/null
+++ test/Dependences/reduction_multiple_loops_array_sum.ll
@@ -1,77 +0,0 @@
-; RUN: opt -basicaa %loadPolly -polly-detect-unprofitable -polly-dependences -analyze < %s | FileCheck %s
-;
-; Verify that only the inner reduction like accesses cause reduction dependences
-;
-; CHECK: Reduction dependences:
-; CHECK:   { Stmt_for_body3[i0, i1] -> Stmt_for_body3[i0, 1 + i1] : i0 <= 99 and i0 >= 0 and i1 <= 98 and i1 >= 0 }
-;
-; void f(int * restrict A, int * restrict sum) {
-;   int i, j, k;
-;   for (i = 0; i < 100; i++) {
-;     *sum *= 7;
-;     for (j = 0; j < 100; j++) {
-;       *sum += A[i+j];
-;       for (k = 0; k< 100; k++) {}
-;     }
-;   }
-; }
-target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-n32-S64"
-
-define void @f(i32* noalias %A, i32* noalias %sum) {
-entry:
-  br label %for.cond
-
-for.cond:                                         ; preds = %for.inc11, %entry
-  %i.0 = phi i32 [ 0, %entry ], [ %inc12, %for.inc11 ]
-  %exitcond2 = icmp ne i32 %i.0, 100
-  br i1 %exitcond2, label %for.body, label %for.end13
-
-for.body:                                         ; preds = %for.cond
-  %tmp = load i32, i32* %sum, align 4
-  %mul = mul nsw i32 %tmp, 7
-  store i32 %mul, i32* %sum, align 4
-  br label %for.cond1
-
-for.cond1:                                        ; preds = %for.inc8, %for.body
-  %j.0 = phi i32 [ 0, %for.body ], [ %inc9, %for.inc8 ]
-  %exitcond1 = icmp ne i32 %j.0, 100
-  br i1 %exitcond1, label %for.body3, label %for.end10
-
-for.body3:                                        ; preds = %for.cond1
-  %add = add nsw i32 %i.0, %j.0
-  %arrayidx = getelementptr inbounds i32, i32* %A, i32 %add
-  %tmp3 = load i32, i32* %arrayidx, align 4
-  %tmp4 = load i32, i32* %sum, align 4
-  %add4 = add nsw i32 %tmp4, %tmp3
-  store i32 %add4, i32* %sum, align 4
-  br label %for.cond5
-
-for.cond5:                                        ; preds = %for.inc, %for.body3
-  %k.0 = phi i32 [ 0, %for.body3 ], [ %inc, %for.inc ]
-  %exitcond = icmp ne i32 %k.0, 100
-  br i1 %exitcond, label %for.body7, label %for.end
-
-for.body7:                                        ; preds = %for.cond5
-  br label %for.inc
-
-for.inc:                                          ; preds = %for.body7
-  %inc = add nsw i32 %k.0, 1
-  br label %for.cond5
-
-for.end:                                          ; preds = %for.cond5
-  br label %for.inc8
-
-for.inc8:                                         ; preds = %for.end
-  %inc9 = add nsw i32 %j.0, 1
-  br label %for.cond1
-
-for.end10:                                        ; preds = %for.cond1
-  br label %for.inc11
-
-for.inc11:                                        ; preds = %for.end10
-  %inc12 = add nsw i32 %i.0, 1
-  br label %for.cond
-
-for.end13:                                        ; preds = %for.cond
-  ret void
-}
Index: test/Dependences/reduction_multiple_loops_array_sum_2.ll
===================================================================
--- /dev/null
+++ test/Dependences/reduction_multiple_loops_array_sum_2.ll
@@ -1,79 +0,0 @@
-; RUN: opt %loadPolly -polly-detect-unprofitable -polly-dependences -analyze -basicaa < %s | FileCheck %s
-;
-; CHECK: RAW dependences:
-; CHECK:   {  }
-; CHECK: WAR dependences:
-; CHECK:   {  }
-; CHECK: WAW dependences:
-; CHECK:   {  }
-; CHECK: Reduction dependences:
-; CHECK-DAG: Stmt_for_body3[i0, i1] -> Stmt_for_body3[i0, 1 + i1] : i0 <= 99 and i0 >= 0 and i1 <= 98 and i1 >= 0
-; CHECK-DAG: Stmt_for_body3[i0, 99] -> Stmt_for_body3[1 + i0, 0] : i0 <= 98 and i0 >= 0
-;
-; int f(int * restrict A, int * restrict sum) {
-;   int i, j, k;
-;   for (i = 0; i < 100; i++) {
-;     for (j = 0; j < 100; j++) {
-;       sum += A[i+j];
-;       for (k = 0; k< 100; k++) {}
-;     }
-;   }
-;   return sum;
-; }
-target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-n32-S64"
-
-define void @f(i32* noalias %A, i32* noalias %sum) {
-entry:
-  br label %for.cond
-
-for.cond:                                         ; preds = %for.inc11, %entry
-  %i.0 = phi i32 [ 0, %entry ], [ %inc12, %for.inc11 ]
-  %exitcond2 = icmp ne i32 %i.0, 100
-  br i1 %exitcond2, label %for.body, label %for.end13
-
-for.body:                                         ; preds = %for.cond
-  br label %for.cond1
-
-for.cond1:                                        ; preds = %for.inc8, %for.body
-  %j.0 = phi i32 [ 0, %for.body ], [ %inc9, %for.inc8 ]
-  %exitcond1 = icmp ne i32 %j.0, 100
-  br i1 %exitcond1, label %for.body3, label %for.end10
-
-for.body3:                                        ; preds = %for.cond1
-  %add = add nsw i32 %i.0, %j.0
-  %arrayidx = getelementptr inbounds i32, i32* %A, i32 %add
-  %tmp3 = load i32, i32* %arrayidx, align 4
-  %tmp4 = load i32, i32* %sum, align 4
-  %add4 = add nsw i32 %tmp4, %tmp3
-  store i32 %add4, i32* %sum, align 4
-  br label %for.cond5
-
-for.cond5:                                        ; preds = %for.inc, %for.body3
-  %k.0 = phi i32 [ 0, %for.body3 ], [ %inc, %for.inc ]
-  %exitcond = icmp ne i32 %k.0, 100
-  br i1 %exitcond, label %for.body7, label %for.end
-
-for.body7:                                        ; preds = %for.cond5
-  br label %for.inc
-
-for.inc:                                          ; preds = %for.body7
-  %inc = add nsw i32 %k.0, 1
-  br label %for.cond5
-
-for.end:                                          ; preds = %for.cond5
-  br label %for.inc8
-
-for.inc8:                                         ; preds = %for.end
-  %inc9 = add nsw i32 %j.0, 1
-  br label %for.cond1
-
-for.end10:                                        ; preds = %for.cond1
-  br label %for.inc11
-
-for.inc11:                                        ; preds = %for.end10
-  %inc12 = add nsw i32 %i.0, 1
-  br label %for.cond
-
-for.end13:                                        ; preds = %for.cond
-  ret void
-}
Index: test/Dependences/reduction_multiple_loops_array_sum_3.ll
===================================================================
--- /dev/null
+++ test/Dependences/reduction_multiple_loops_array_sum_3.ll
@@ -1,73 +0,0 @@
-; RUN: opt %loadPolly -polly-detect-unprofitable -polly-dependences -analyze -basicaa < %s | FileCheck %s
-;
-; CHECK: Reduction dependences:
-; CHECK:   { Stmt_for_inc[i0, i1] -> Stmt_for_inc[i0, 1 + i1] : i0 <= 99 and i0 >= 0 and i1 <= 98 and i1 >= 0 }
-;
-; int f(int * __restrict__ A) {
-;   int i, j, sum = 0;
-;   for (k = 0; k < 37; k = g(k)) {
-;     for (i = 0; i < 100; i++) {
-;       sum *= 2;
-;       for (j = 0; j < 100; j++) {
-;         sum += A[i+j];
-;       }
-;     }
-;   }
-;   return sum;
-; }
-target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
-
-declare i64 @g(i64)
-
-define i32 @f(i32* noalias %A) {
-entry:
-  %sum.04.reg2mem = alloca i32
-  %sum.12.reg2mem = alloca i32
-  br label %entry.split
-
-entry.split:                                      ; preds = %entry
-  store i32 0, i32* %sum.04.reg2mem
-  br label %for.body_outer_split
-
-for.body_outer_split:                             ; preds = %entry.split, %for.inc5
-  %indvars.ivK = phi i64 [ 0, %entry.split ], [ %incK, %for.bos2 ]
-  br label %for.body_outer
-
-for.body_outer:                                   ; preds = %for.body_outer_split
-  %incK = call i64 @g(i64 %indvars.ivK)
-  %exitcondK = icmp eq i64 %incK, 100
-  br i1 %exitcondK, label %for.end7, label %for.body
-
-for.body:                                         ; preds = %for.inc5, %for.body_outer
-  %indvars.iv23 = phi i64 [ 0, %for.body_outer ], [ %3, %for.inc5 ]
-  %sum.04.reload = load i32, i32* %sum.04.reg2mem
-  %mul = shl nsw i32 %sum.04.reload, 1
-  store i32 %mul, i32* %sum.12.reg2mem
-  br label %for.inc
-
-for.inc:                                          ; preds = %for.inc, %for.body
-  %indvars.iv1 = phi i64 [ 0, %for.body ], [ %1, %for.inc ]
-  %sum.12.reload = load i32, i32* %sum.12.reg2mem
-  %0 = add i64 %indvars.iv23, %indvars.iv1
-  %arrayidx = getelementptr i32, i32* %A, i64 %0
-  %tmp5 = load i32, i32* %arrayidx, align 4
-  %add4 = add nsw i32 %tmp5, %sum.12.reload
-  %1 = add nuw nsw i64 %indvars.iv1, 1
-  %exitcond1 = icmp eq i64 %1, 100
-  store i32 %add4, i32* %sum.12.reg2mem
-  br i1 %exitcond1, label %for.inc5, label %for.inc
-
-for.inc5:                                         ; preds = %for.inc
-  %2 = load i32, i32* %sum.12.reg2mem
-  %3 = add nuw nsw i64 %indvars.iv23, 1
-  %exitcond2 = icmp eq i64 %3, 100
-  store i32 %2, i32* %sum.04.reg2mem
-  br i1 %exitcond2, label %for.bos2, label %for.body
-
-for.bos2:
-  br label %for.body_outer_split
-
-for.end7:                                         ; preds = %for.inc5
-  %4 = load i32, i32* %sum.04.reg2mem
-  ret i32 %4
-}
Index: test/Dependences/reduction_multiple_reductions.ll
===================================================================
--- /dev/null
+++ test/Dependences/reduction_multiple_reductions.ll
@@ -1,59 +0,0 @@
-; RUN: opt %loadPolly -polly-detect-unprofitable -basicaa -polly-dependences -analyze < %s | FileCheck %s
-;
-; Verify we do not have dependences between the if and the else clause
-;
-; CHECK: RAW dependences:
-; CHECK:   {  }
-; CHECK: WAR dependences:
-; CHECK:   {  }
-; CHECK: WAW dependences:
-; CHECK:   {  }
-; CHECK: Reduction dependences:
-; CHECK-DAG: Stmt_if_then[i0] -> Stmt_if_then[1 + i0] : i0 <= 510 and i0 >= 0
-; CHECK-DAG: Stmt_if_else[i0] -> Stmt_if_else[1 + i0] : i0 <= 1022 and i0 >= 512
-;
-; void f(int *restrict sum, int *restrict prod) {
-;   for (int i = 0; i < 1024; i++)
-;     if (i < 512)
-;       *sum += i;
-;     else
-;       *prod *= i;
-; }
-;
-target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-n32-S64"
-
-define void @f(i32* noalias %sum, i32* noalias %prod)  {
-entry:
-  br label %for.cond
-
-for.cond:                                         ; preds = %for.inc, %entry
-  %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
-  %exitcond = icmp ne i32 %i.0, 1024
-  br i1 %exitcond, label %for.body, label %for.end
-
-for.body:                                         ; preds = %for.cond
-  %cmp1 = icmp slt i32 %i.0, 512
-  br i1 %cmp1, label %if.then, label %if.else
-
-if.then:                                          ; preds = %for.body
-  %tmp = load i32, i32* %sum, align 4
-  %add = add nsw i32 %tmp, %i.0
-  store i32 %add, i32* %sum, align 4
-  br label %if.end
-
-if.else:                                          ; preds = %for.body
-  %tmp1 = load i32, i32* %prod, align 4
-  %mul = mul nsw i32 %tmp1, %i.0
-  store i32 %mul, i32* %prod, align 4
-  br label %if.end
-
-if.end:                                           ; preds = %if.else, %if.then
-  br label %for.inc
-
-for.inc:                                          ; preds = %if.end
-  %inc = add nsw i32 %i.0, 1
-  br label %for.cond
-
-for.end:                                          ; preds = %for.cond
-  ret void
-}
Index: test/Dependences/reduction_multiple_reductions_2.ll
===================================================================
--- /dev/null
+++ test/Dependences/reduction_multiple_reductions_2.ll
@@ -1,110 +0,0 @@
-; RUN: opt %loadPolly -polly-detect-unprofitable -basicaa -polly-dependences -analyze < %s | FileCheck %s
-;
-; CHECK: RAW dependences:
-; CHECK-DAG: Stmt_S2[i0, i1] -> Stmt_S3[i0] : i0 <= 1023 and i0 >= 0 and i1 <= 1023 and i1 >= 0
-; CHECK-DAG: Stmt_S3[i0] -> Stmt_S0[1 + i0] : i0 <= 1022 and i0 >= 0
-; CHECK-DAG: Stmt_S0[i0] -> Stmt_S1[i0, o1] : i0 <= 1023 and i0 >= 0 and o1 <= 1023 and o1 >= 0
-; These are the important RAW dependences, as they need to originate/end in only one iteration:
-; CHECK-DAG: Stmt_S1[i0, 1023] -> Stmt_S2[i0, o1] : i0 <= 1023 and i0 >= 0 and o1 <= 1023 and o1 >= 0
-; CHECK-DAG: Stmt_S1[i0, i1] -> Stmt_S2[i0, 0] : i0 <= 1023 and i0 >= 0 and i1 <= 1022 and i1 >= 0
-; CHECK: WAR dependences:
-; CHECK:   {  }
-; CHECK: WAW dependences:
-; CHECK-DAG: Stmt_S2[i0, i1] -> Stmt_S3[i0] : i0 <= 1023 and i0 >= 0 and i1 <= 1023 and i1 >= 0
-; CHECK-DAG: Stmt_S3[i0] -> Stmt_S0[1 + i0] : i0 <= 1022 and i0 >= 0
-; CHECK-DAG: Stmt_S0[i0] -> Stmt_S1[i0, o1] : i0 <= 1023 and i0 >= 0 and o1 <= 1023 and o1 >= 0
-; These are the important WAW dependences, as they need to originate/end in only one iteration:
-; CHECK-DAG: Stmt_S1[i0, 1023] -> Stmt_S2[i0, o1] : i0 <= 1023 and i0 >= 0 and o1 <= 1023 and o1 >= 0
-; CHECK-DAG: Stmt_S1[i0, i1] -> Stmt_S2[i0, 0] : i0 <= 1023 and i0 >= 0 and i1 <= 1022 and i1 >= 0
-; CHECK: Reduction dependences:
-; CHECK-DAG:  Stmt_S1[i0, i1] -> Stmt_S1[i0, 1 + i1] : i0 <= 1023 and i0 >= 0 and i1 <= 1022 and i1 >= 0
-; CHECK-DAG:  Stmt_S2[i0, i1] -> Stmt_S2[i0, 1 + i1] : i0 <= 1023 and i0 >= 0 and i1 <= 1022 and i1 >= 0
-;
-;    void f(int *restrict red) {
-;      for (int j = 0; j < 1024; j++) {
-; S0:    *red = 42 + *red * 5;
-;        for (int i = 0; i < 1024; i++)
-; S1:      *red *= i;
-;        for (int i = 0; i < 1024; i++)
-; S2:      *red += i;
-; S3:    *red = 42 + *red * 7;
-;      }
-;    }
-;
-target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-n32-S64"
-
-define void @f(i32* noalias %red)  {
-entry:
-  br label %for.cond
-
-for.cond:                                         ; preds = %for.inc15, %entry
-  %j.0 = phi i32 [ 0, %entry ], [ %inc16, %for.inc15 ]
-  %exitcond2 = icmp ne i32 %j.0, 1024
-  br i1 %exitcond2, label %for.body, label %for.end17
-
-for.body:                                         ; preds = %for.cond
-  br label %S0
-
-S0:                                               ; preds = %for.body
-  %tmp = load i32, i32* %red, align 4
-  %mul = mul nsw i32 %tmp, 5
-  %add = add nsw i32 %mul, 42
-  store i32 %add, i32* %red, align 4
-  br label %for.cond1
-
-for.cond1:                                        ; preds = %for.inc, %S0
-  %i.0 = phi i32 [ 0, %S0 ], [ %inc, %for.inc ]
-  %exitcond = icmp ne i32 %i.0, 1024
-  br i1 %exitcond, label %for.body3, label %for.end
-
-for.body3:                                        ; preds = %for.cond1
-  br label %S1
-
-S1:                                               ; preds = %for.body3
-  %tmp3 = load i32, i32* %red, align 4
-  %mul4 = mul nsw i32 %tmp3, %i.0
-  store i32 %mul4, i32* %red, align 4
-  br label %for.inc
-
-for.inc:                                          ; preds = %S1
-  %inc = add nsw i32 %i.0, 1
-  br label %for.cond1
-
-for.end:                                          ; preds = %for.cond1
-  br label %for.cond6
-
-for.cond6:                                        ; preds = %for.inc10, %for.end
-  %i5.0 = phi i32 [ 0, %for.end ], [ %inc11, %for.inc10 ]
-  %exitcond1 = icmp ne i32 %i5.0, 1024
-  br i1 %exitcond1, label %for.body8, label %for.end12
-
-for.body8:                                        ; preds = %for.cond6
-  br label %S2
-
-S2:                                               ; preds = %for.body8
-  %tmp4 = load i32, i32* %red, align 4
-  %add9 = add nsw i32 %tmp4, %i5.0
-  store i32 %add9, i32* %red, align 4
-  br label %for.inc10
-
-for.inc10:                                        ; preds = %S2
-  %inc11 = add nsw i32 %i5.0, 1
-  br label %for.cond6
-
-for.end12:                                        ; preds = %for.cond6
-  br label %S3
-
-S3:                                               ; preds = %for.end12
-  %tmp5 = load i32, i32* %red, align 4
-  %mul13 = mul nsw i32 %tmp5, 7
-  %add14 = add nsw i32 %mul13, 42
-  store i32 %add14, i32* %red, align 4
-  br label %for.inc15
-
-for.inc15:                                        ; preds = %S3
-  %inc16 = add nsw i32 %j.0, 1
-  br label %for.cond
-
-for.end17:                                        ; preds = %for.cond
-  ret void
-}
Index: test/Dependences/reduction_only_reduction_like_access.ll
===================================================================
--- /dev/null
+++ test/Dependences/reduction_only_reduction_like_access.ll
@@ -1,44 +0,0 @@
-; RUN: opt %loadPolly -polly-detect-unprofitable -polly-dependences -analyze < %s | FileCheck %s
-;
-; FIXME: Change the comment once we allow different pointers
-; The statement is "almost" reduction like but should not yield any reduction dependences
-;
-; We are limited to binary reductions at the moment and this is not one.
-; There are never at least two iterations which read __and__ write to the same
-; location, thus we won't find the RAW and WAW dependences of a reduction,
-; thus we should not find Reduction dependences.
-;
-; CHECK:  Reduction dependences:
-; CHECK:    {  }
-;
-; void f(int *sum) {
-;   for (int i = 0; i < 100; i++)
-;     sum[i] = sum[99-i] + i;
-; }
-target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-n32-S64"
-
-define void @f(i32* %sum) {
-entry:
-  br label %for.cond
-
-for.cond:                                         ; preds = %for.inc, %entry
-  %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
-  %exitcond = icmp ne i32 %i.0, 100
-  br i1 %exitcond, label %for.body, label %for.end
-
-for.body:                                         ; preds = %for.cond
-  %sub = sub nsw i32 99, %i.0
-  %arrayidx = getelementptr inbounds i32, i32* %sum, i32 %sub
-  %tmp = load i32, i32* %arrayidx, align 4
-  %add = add nsw i32 %tmp, %i.0
-  %arrayidx1 = getelementptr inbounds i32, i32* %sum, i32 %i.0
-  store i32 %add, i32* %arrayidx1, align 4
-  br label %for.inc
-
-for.inc:                                          ; preds = %for.body
-  %inc = add nsw i32 %i.0, 1
-  br label %for.cond
-
-for.end:                                          ; preds = %for.cond
-  ret void
-}
Index: test/Dependences/reduction_partially_escaping_intermediate_in_other_stmt.ll
===================================================================
--- /dev/null
+++ test/Dependences/reduction_partially_escaping_intermediate_in_other_stmt.ll
@@ -1,69 +0,0 @@
-; RUN: opt %loadPolly -polly-detect-unprofitable -polly-dependences -analyze -basicaa < %s | FileCheck %s
-;
-; CHECK: Reduction dependences:
-; CHECK:   [N] -> { Stmt_for_body3[i0, i1] -> Stmt_for_body3[i0, 1 + i1] : i0 <= 1023 and i0 >= 0 and i1 <= 1022 and i1 >= 0 and i1 >= 1024 - N + i0 }
-;
-; void f(int N, int * restrict sums, int * restrict escape) {
-;   for (int i = 0; i < 1024; i++) {
-;     for (int j = 0; j < 1024; j++) {
-;       sums[i] += 5;
-;       if (N - i + j < 1024)
-;         escape[N - i + j] = sums[i];
-;     }
-;   }
-; }
-target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-n32-S64"
-
-define void @f(i32 %N, i32* noalias %sums, i32* noalias %escape) {
-entry:
-  br label %for.cond
-
-for.cond:                                         ; preds = %for.inc10, %entry
-  %i.0 = phi i32 [ 0, %entry ], [ %inc11, %for.inc10 ]
-  %exitcond1 = icmp ne i32 %i.0, 1024
-  br i1 %exitcond1, label %for.body, label %for.end12
-
-for.body:                                         ; preds = %for.cond
-  br label %for.cond1
-
-for.cond1:                                        ; preds = %for.inc, %for.body
-  %j.0 = phi i32 [ 0, %for.body ], [ %inc, %for.inc ]
-  %exitcond = icmp ne i32 %j.0, 1024
-  br i1 %exitcond, label %for.body3, label %for.end
-
-for.body3:                                        ; preds = %for.cond1
-  %arrayidx = getelementptr inbounds i32, i32* %sums, i32 %i.0
-  %tmp = load i32, i32* %arrayidx, align 4
-  %add = add nsw i32 %tmp, 5
-  store i32 %add, i32* %arrayidx, align 4
-  %sub = sub nsw i32 %N, %i.0
-  %add4 = add nsw i32 %sub, %j.0
-  %cmp5 = icmp slt i32 %add4, 1024
-  br i1 %cmp5, label %if.then, label %if.end
-
-if.then:                                          ; preds = %for.body3
-  %arrayidx6 = getelementptr inbounds i32, i32* %sums, i32 %i.0
-  %tmp2 = load i32, i32* %arrayidx6, align 4
-  %sub7 = sub nsw i32 %N, %i.0
-  %add8 = add nsw i32 %sub7, %j.0
-  %arrayidx9 = getelementptr inbounds i32, i32* %escape, i32 %add8
-  store i32 %tmp2, i32* %arrayidx9, align 4
-  br label %if.end
-
-if.end:                                           ; preds = %if.then, %for.body3
-  br label %for.inc
-
-for.inc:                                          ; preds = %if.end
-  %inc = add nsw i32 %j.0, 1
-  br label %for.cond1
-
-for.end:                                          ; preds = %for.cond1
-  br label %for.inc10
-
-for.inc10:                                        ; preds = %for.end
-  %inc11 = add nsw i32 %i.0, 1
-  br label %for.cond
-
-for.end12:                                        ; preds = %for.cond
-  ret void
-}
Index: test/Dependences/reduction_privatization_deps.ll
===================================================================
--- /dev/null
+++ test/Dependences/reduction_privatization_deps.ll
@@ -1,111 +0,0 @@
-; RUN: opt %loadPolly -polly-detect-unprofitable -basicaa -polly-dependences -analyze < %s | FileCheck %s
-;
-; CHECK:      RAW dependences:
-; CHECK-DAG:    Stmt_S0[i0] -> Stmt_S1[o0, i0 - o0] : i0 <= 1023 and o0 >= 0 and o0 <= i0
-; CHECK-DAG:     Stmt_S1[i0, i1] -> Stmt_S2[-1 + i0 + i1] : i1 <= 1023 and i1 >= 0 and i1 >= 1 - i0 and i0 >= 0 and i0 <= 1023 and i1 <= 1024 - i0 
-; CHECK:      WAR dependences:
-; CHECK-DAG:    Stmt_S2[i0] -> Stmt_S2[1 + i0] : i0 <= 1022 and i0 >= 0
-; CHECK-DAG:    Stmt_S1[i0, i1] -> Stmt_S2[i0 + i1] : i1 <= 1023 - i0 and i1 >= 0 and i1 >= 1 - i0 and i0 >= 0 }
-; CHECK:      WAW dependences:
-; CHECK-DAG:    Stmt_S0[i0] -> Stmt_S1[o0, i0 - o0] : i0 <= 1023 and o0 >= 0 and o0 <= i0
-; CHECK-DAG:    Stmt_S1[0, 0] -> Stmt_S2[0]
-; CHECK:      Reduction dependences:
-; CHECK-DAG:    Stmt_S1[i0, i1] -> Stmt_S1[1 + i0, -1 + i1] : i0 <= 1022 and i0 >= 0 and i1 <= 1023 and i1 >= 1
-;
-;    void f(int *sum) {
-;      for (int i = 0; i < 1024; i++)
-; S0:    sum[i] = 0;
-;      for (int i = 0; i < 1024; i++)
-;        for (int j = 0; j < 1024; j++)
-; S1:      sum[i + j] += i;
-;      for (int i = 0; i < 1024; i++)
-; S2:    sum[i] = sum[i + 1] * 3;
-;    }
-target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-n32-S64"
-
-define void @f(i32* %sum)  {
-entry:
-  br label %for.cond
-
-for.cond:                                         ; preds = %for.inc, %entry
-  %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
-  %exitcond3 = icmp ne i32 %i.0, 1024
-  br i1 %exitcond3, label %for.body, label %for.end
-
-for.body:                                         ; preds = %for.cond
-  br label %S0
-
-S0:                                               ; preds = %for.body
-  %arrayidx = getelementptr inbounds i32, i32* %sum, i32 %i.0
-  store i32 0, i32* %arrayidx, align 4
-  br label %for.inc
-
-for.inc:                                          ; preds = %S0
-  %inc = add nsw i32 %i.0, 1
-  br label %for.cond
-
-for.end:                                          ; preds = %for.cond
-  br label %for.cond2
-
-for.cond2:                                        ; preds = %for.inc13, %for.end
-  %i1.0 = phi i32 [ 0, %for.end ], [ %inc14, %for.inc13 ]
-  %exitcond2 = icmp ne i32 %i1.0, 1024
-  br i1 %exitcond2, label %for.body4, label %for.end15
-
-for.body4:                                        ; preds = %for.cond2
-  br label %for.cond5
-
-for.cond5:                                        ; preds = %for.inc10, %for.body4
-  %j.0 = phi i32 [ 0, %for.body4 ], [ %inc11, %for.inc10 ]
-  %exitcond1 = icmp ne i32 %j.0, 1024
-  br i1 %exitcond1, label %for.body7, label %for.end12
-
-for.body7:                                        ; preds = %for.cond5
-  br label %S1
-
-S1:                                               ; preds = %for.body7
-  %add = add nsw i32 %i1.0, %j.0
-  %arrayidx8 = getelementptr inbounds i32, i32* %sum, i32 %add
-  %tmp = load i32, i32* %arrayidx8, align 4
-  %add9 = add nsw i32 %tmp, %i1.0
-  store i32 %add9, i32* %arrayidx8, align 4
-  br label %for.inc10
-
-for.inc10:                                        ; preds = %S1
-  %inc11 = add nsw i32 %j.0, 1
-  br label %for.cond5
-
-for.end12:                                        ; preds = %for.cond5
-  br label %for.inc13
-
-for.inc13:                                        ; preds = %for.end12
-  %inc14 = add nsw i32 %i1.0, 1
-  br label %for.cond2
-
-for.end15:                                        ; preds = %for.cond2
-  br label %for.cond17
-
-for.cond17:                                       ; preds = %for.inc23, %for.end15
-  %i16.0 = phi i32 [ 0, %for.end15 ], [ %inc24, %for.inc23 ]
-  %exitcond = icmp ne i32 %i16.0, 1024
-  br i1 %exitcond, label %for.body19, label %for.end25
-
-for.body19:                                       ; preds = %for.cond17
-  br label %S2
-
-S2:                                               ; preds = %for.body19
-  %add20 = add nsw i32 %i16.0, 1
-  %arrayidx21 = getelementptr inbounds i32, i32* %sum, i32 %add20
-  %tmp4 = load i32, i32* %arrayidx21, align 4
-  %mul = mul nsw i32 %tmp4, 3
-  %arrayidx22 = getelementptr inbounds i32, i32* %sum, i32 %i16.0
-  store i32 %mul, i32* %arrayidx22, align 4
-  br label %for.inc23
-
-for.inc23:                                        ; preds = %S2
-  %inc24 = add nsw i32 %i16.0, 1
-  br label %for.cond17
-
-for.end25:                                        ; preds = %for.cond17
-  ret void
-}
Index: test/Dependences/reduction_privatization_deps_2.ll
===================================================================
--- /dev/null
+++ test/Dependences/reduction_privatization_deps_2.ll
@@ -1,86 +0,0 @@
-; RUN: opt %loadPolly -polly-detect-unprofitable -polly-dependences -analyze < %s | FileCheck %s
-;
-; We have privatization dependences from a textually later statement to a
-; textually earlier one, but the dependences still go forward in time.
-;
-;  CHECK: RAW dependences:
-;  CHECK-DAG:  Stmt_S3[i0] -> Stmt_S2[1 + i0, o1] : i0 <= 97 and i0 >= 0 and o1 <= 99 and o1 >= 0
-;  CHECK-DAG:  Stmt_S1[i0] -> Stmt_S3[i0] : i0 <= 98 and i0 >= 0
-;  CHECK: WAR dependences:
-;  CHECK:   {  }
-;  CHECK: WAW dependences:
-;  CHECK-DAG:  Stmt_S3[i0] -> Stmt_S2[1 + i0, o1] : i0 <= 97 and i0 >= 0 and o1 <= 99 and o1 >= 0
-;  CHECK-DAG:  Stmt_S1[i0] -> Stmt_S3[i0] : i0 <= 98 and i0 >= 0
-;  CHECK: Reduction dependences:
-;  CHECK:   { Stmt_S2[i0, i1] -> Stmt_S2[i0, 1 + i1] : i0 <= 98 and i0 >= 0 and i1 <= 98 and i1 >= 0 }
-;
-;    void f(int *sum) {
-;      int i, j;
-;      for (i = 0; i < 99; i++) {
-; S1:    sum[i + 1] += 42;
-;        for (j = 0; j < 100; j++)
-; S2:      sum[i] += i * j;
-; S3:    sum[i + 1] += 7;
-;      }
-;    }
-;
-target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-n32-S64"
-
-define void @f(i32* %sum)  {
-entry:
-  br label %for.cond
-
-for.cond:                                         ; preds = %for.inc10, %entry
-  %i.0 = phi i32 [ 0, %entry ], [ %inc11, %for.inc10 ]
-  %exitcond1 = icmp ne i32 %i.0, 99
-  br i1 %exitcond1, label %for.body, label %for.end12
-
-for.body:                                         ; preds = %for.cond
-  br label %S1
-
-S1:                                               ; preds = %for.body
-  %add = add nsw i32 %i.0, 1
-  %arrayidx = getelementptr inbounds i32, i32* %sum, i32 %add
-  %tmp = load i32, i32* %arrayidx, align 4
-  %add1 = add nsw i32 %tmp, 42
-  store i32 %add1, i32* %arrayidx, align 4
-  br label %for.cond2
-
-for.cond2:                                        ; preds = %for.inc, %S1
-  %j.0 = phi i32 [ 0, %S1 ], [ %inc, %for.inc ]
-  %exitcond = icmp ne i32 %j.0, 100
-  br i1 %exitcond, label %for.body4, label %for.end
-
-for.body4:                                        ; preds = %for.cond2
-  br label %S2
-
-S2:                                               ; preds = %for.body4
-  %mul = mul nsw i32 %i.0, %j.0
-  %arrayidx5 = getelementptr inbounds i32, i32* %sum, i32 %i.0
-  %tmp2 = load i32, i32* %arrayidx5, align 4
-  %add6 = add nsw i32 %tmp2, %mul
-  store i32 %add6, i32* %arrayidx5, align 4
-  br label %for.inc
-
-for.inc:                                          ; preds = %S2
-  %inc = add nsw i32 %j.0, 1
-  br label %for.cond2
-
-for.end:                                          ; preds = %for.cond2
-  br label %S3
-
-S3:                                               ; preds = %for.end
-  %add7 = add nsw i32 %i.0, 1
-  %arrayidx8 = getelementptr inbounds i32, i32* %sum, i32 %add7
-  %tmp3 = load i32, i32* %arrayidx8, align 4
-  %add9 = add nsw i32 %tmp3, 7
-  store i32 %add9, i32* %arrayidx8, align 4
-  br label %for.inc10
-
-for.inc10:                                        ; preds = %S3
-  %inc11 = add nsw i32 %i.0, 1
-  br label %for.cond
-
-for.end12:                                        ; preds = %for.cond
-  ret void
-}
Index: test/Dependences/reduction_privatization_deps_3.ll
===================================================================
--- /dev/null
+++ test/Dependences/reduction_privatization_deps_3.ll
@@ -1,87 +0,0 @@
-; RUN: opt %loadPolly -polly-detect-unprofitable -polly-dependences -analyze < %s | FileCheck %s
-;
-;  CHECK: RAW dependences:
-;  CHECK-DAG:  Stmt_S2[i0, i1] -> Stmt_S3[o0] : o0 <= 1 and i1 <= 1 - i0 and o0 <= 1 + i0 - i1 and o0 >= 1 - i1
-;  CHECK-DAG:  Stmt_S3[i0] -> Stmt_S2[o0, 1 - i0] : i0 <= 1 and i0 >= 0 and o0 >= 1 + i0 and o0 <= 98
-;  CHECK-DAG:  Stmt_S1[i0] -> Stmt_S3[2 + i0] : i0 <= 96 and i0 >= 0
-;  CHECK: WAR dependences:
-;  CHECK:   {  }
-;  CHECK: WAW dependences:
-;  CHECK-DAG:  Stmt_S2[i0, i1] -> Stmt_S3[o0] : o0 <= 1 and i1 <= 1 - i0 and o0 <= 1 + i0 - i1 and o0 >= 1 - i1
-;  CHECK-DAG:  Stmt_S3[i0] -> Stmt_S2[o0, 1 - i0] : i0 <= 1 and i0 >= 0 and o0 >= 1 + i0 and o0 <= 98
-;  CHECK-DAG:  Stmt_S1[i0] -> Stmt_S3[2 + i0] : i0 <= 96 and i0 >= 0
-;  CHECK: Reduction dependences:
-;  CHECK-DAG:  Stmt_S2[i0, i1] -> Stmt_S2[1 + i0, i1] : i0 <= 97 and i0 >= 0 and i1 <= 98 - i0 and i1 >= 0 and i1 >= 2 - i0
-;  CHECK-DAG:  Stmt_S2[0, 0] -> Stmt_S2[1, 0]
-;
-;    void f(int *sum) {
-;      int i, j;
-;      for (i = 0; i < 99; i++) {
-; S1:    sum[i + 1] += 42;
-;        for (j = i; j < 100; j++)
-; S2:      sum[i - j] += i * j;
-; S3:    sum[i - 1] += 7;
-;      }
-;    }
-;
-target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-n32-S64"
-
-define void @f(i32* %sum)  {
-entry:
-  br label %for.cond
-
-for.cond:                                         ; preds = %for.inc10, %entry
-  %i.0 = phi i32 [ 0, %entry ], [ %inc11, %for.inc10 ]
-  %exitcond1 = icmp ne i32 %i.0, 99
-  br i1 %exitcond1, label %for.body, label %for.end12
-
-for.body:                                         ; preds = %for.cond
-  br label %S1
-
-S1:                                               ; preds = %for.body
-  %add = add nsw i32 %i.0, 1
-  %arrayidx = getelementptr inbounds i32, i32* %sum, i32 %add
-  %tmp = load i32, i32* %arrayidx, align 4
-  %add1 = add nsw i32 %tmp, 42
-  store i32 %add1, i32* %arrayidx, align 4
-  br label %for.cond2
-
-for.cond2:                                        ; preds = %for.inc, %S1
-  %j.0 = phi i32 [ %i.0, %S1 ], [ %inc, %for.inc ]
-  %exitcond = icmp ne i32 %j.0, 100
-  br i1 %exitcond, label %for.body4, label %for.end
-
-for.body4:                                        ; preds = %for.cond2
-  br label %S2
-
-S2:                                               ; preds = %for.body4
-  %mul = mul nsw i32 %i.0, %j.0
-  %sub = sub nsw i32 %i.0, %j.0
-  %arrayidx5 = getelementptr inbounds i32, i32* %sum, i32 %sub
-  %tmp2 = load i32, i32* %arrayidx5, align 4
-  %add6 = add nsw i32 %tmp2, %mul
-  store i32 %add6, i32* %arrayidx5, align 4
-  br label %for.inc
-
-for.inc:                                          ; preds = %S2
-  %inc = add nsw i32 %j.0, 1
-  br label %for.cond2
-
-for.end:                                          ; preds = %for.cond2
-  br label %S3
-
-S3:                                               ; preds = %for.end
-  %sub7 = add nsw i32 %i.0, -1
-  %arrayidx8 = getelementptr inbounds i32, i32* %sum, i32 %sub7
-  %tmp3 = load i32, i32* %arrayidx8, align 4
-  %add9 = add nsw i32 %tmp3, 7
-  store i32 %add9, i32* %arrayidx8, align 4
-  br label %for.inc10
-
-for.inc10:                                        ; preds = %S3
-  %inc11 = add nsw i32 %i.0, 1
-  br label %for.cond
-
-for.end12:                                        ; preds = %for.cond
-  ret void
-}
Index: test/Dependences/reduction_privatization_deps_4.ll
===================================================================
--- /dev/null
+++ test/Dependences/reduction_privatization_deps_4.ll
@@ -1,84 +0,0 @@
-; RUN: opt %loadPolly -polly-detect-unprofitable -polly-dependences -analyze < %s | FileCheck %s
-;
-; CHECK:     RAW dependences:
-; CHECK-DAG:   Stmt_S2[i0, i1] -> Stmt_S1[i1] : i0 >= 0 and i1 >= 1 + i0 and i1 <= 98
-; CHECK-DAG:   Stmt_S1[i0] -> Stmt_S2[i0, i0] : i0 <= 98 and i0 >= 0
-; CHECK-DAG:   Stmt_S2[i0, i0] -> Stmt_S3[i0] : i0 <= 98 and i0 >= 0
-; CHECK-DAG:   Stmt_S3[i0] -> Stmt_S2[o0, i0] : i0 >= 0 and o0 >= 1 + i0 and o0 <= 98
-; CHECK:     WAR dependences:
-; CHECK-DAG:    {  }
-; CHECK:     WAW dependences:
-; CHECK-DAG:   Stmt_S2[i0, i1] -> Stmt_S1[i1] : i0 >= 0 and i1 >= 1 + i0 and i1 <= 98
-; CHECK-DAG:   Stmt_S1[i0] -> Stmt_S2[i0, i0] : i0 <= 98 and i0 >= 0
-; CHECK-DAG:   Stmt_S2[i0, i0] -> Stmt_S3[i0] : i0 <= 98 and i0 >= 0
-; CHECK-DAG:   Stmt_S3[i0] -> Stmt_S2[o0, i0] : i0 >= 0 and o0 >= 1 + i0 and o0 <= 98
-; CHECK:     Reduction dependences:
-; CHECK-DAG:    { Stmt_S2[i0, i1] -> Stmt_S2[1 + i0, i1] : (i0 >= 0 and i1 >= 2 + i0 and i1 <= 99) or (i0 <= 97 and i1 >= 0 and i1 <= -1 + i0) }
-;
-;    void f(int *sum) {
-;      for (int i = 0; i < 99; i++) {
-; S1:    sum[i] += 42;
-;        for (int j = 0; j < 100; j++)
-; S2:      sum[j] += i * j;
-; S3:    sum[i] += 7;
-;      }
-;    }
-;
-target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-n32-S64"
-
-define void @f(i32* %sum)  {
-entry:
-  br label %for.cond
-
-for.cond:                                         ; preds = %for.inc8, %entry
-  %i.0 = phi i32 [ 0, %entry ], [ %inc9, %for.inc8 ]
-  %exitcond1 = icmp ne i32 %i.0, 99
-  br i1 %exitcond1, label %for.body, label %for.end10
-
-for.body:                                         ; preds = %for.cond
-  br label %S1
-
-S1:                                               ; preds = %for.body
-  %arrayidx = getelementptr inbounds i32, i32* %sum, i32 %i.0
-  %tmp = load i32, i32* %arrayidx, align 4
-  %add = add nsw i32 %tmp, 42
-  store i32 %add, i32* %arrayidx, align 4
-  br label %for.cond1
-
-for.cond1:                                        ; preds = %for.inc, %S1
-  %j.0 = phi i32 [ 0, %S1 ], [ %inc, %for.inc ]
-  %exitcond = icmp ne i32 %j.0, 100
-  br i1 %exitcond, label %for.body3, label %for.end
-
-for.body3:                                        ; preds = %for.cond1
-  br label %S2
-
-S2:                                               ; preds = %for.body3
-  %mul = mul nsw i32 %i.0, %j.0
-  %arrayidx4 = getelementptr inbounds i32, i32* %sum, i32 %j.0
-  %tmp2 = load i32, i32* %arrayidx4, align 4
-  %add5 = add nsw i32 %tmp2, %mul
-  store i32 %add5, i32* %arrayidx4, align 4
-  br label %for.inc
-
-for.inc:                                          ; preds = %S2
-  %inc = add nsw i32 %j.0, 1
-  br label %for.cond1
-
-for.end:                                          ; preds = %for.cond1
-  br label %S3
-
-S3:                                               ; preds = %for.end
-  %arrayidx6 = getelementptr inbounds i32, i32* %sum, i32 %i.0
-  %tmp3 = load i32, i32* %arrayidx6, align 4
-  %add7 = add nsw i32 %tmp3, 7
-  store i32 %add7, i32* %arrayidx6, align 4
-  br label %for.inc8
-
-for.inc8:                                         ; preds = %S3
-  %inc9 = add nsw i32 %i.0, 1
-  br label %for.cond
-
-for.end10:                                        ; preds = %for.cond
-  ret void
-}
Index: test/Dependences/reduction_privatization_deps_5.ll
===================================================================
--- /dev/null
+++ test/Dependences/reduction_privatization_deps_5.ll
@@ -1,88 +0,0 @@
-; RUN: opt %loadPolly -polly-detect-unprofitable -polly-dependences -analyze < %s | FileCheck %s
-;
-; CHECK:     RAW dependences:
-; CHECK-DAG:   Stmt_S2[i0, 0] -> Stmt_S1[1 + i0, 0] : i0 <= 97 and i0 >= 0
-; CHECK-DAG:   Stmt_S1[i0, 0] -> Stmt_S2[i0, 0] : i0 <= 98 and i0 >= 0
-; CHECK:     WAR dependences:
-; CHECK-DAG:   {  }
-; CHECK:     WAW dependences:
-; CHECK-DAG:   Stmt_S2[i0, 0] -> Stmt_S1[1 + i0, 0] : i0 <= 97 and i0 >= 0
-; CHECK-DAG:   Stmt_S1[i0, 0] -> Stmt_S2[i0, 0] : i0 <= 98 and i0 >= 0
-; CHECK:     Reduction dependences:
-; CHECK-DAG:   { Stmt_S2[i0, i1] -> Stmt_S2[1 + i0, i1] : i0 <= 97 and i0 >= 0 and i1 <= 99 and i1 >= 1 }
-;
-;    void f(int *sum) {
-;      for (int i = 0; i < 99; i++) {
-;        for (int j = 0; j < 1; j++)
-; S1:      sum[j] += 42;
-;        for (int j = 0; j < 100; j++)
-; S2:      sum[j] += i * j;
-;      }
-;    }
-;
-target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-n32-S64"
-
-define void @f(i32* %sum)  {
-entry:
-  br label %for.cond
-
-for.cond:                                         ; preds = %for.inc12, %entry
-  %i.0 = phi i32 [ 0, %entry ], [ %inc13, %for.inc12 ]
-  %exitcond2 = icmp ne i32 %i.0, 99
-  br i1 %exitcond2, label %for.body, label %for.end14
-
-for.body:                                         ; preds = %for.cond
-  br label %for.cond1
-
-for.cond1:                                        ; preds = %for.inc, %for.body
-  %j.0 = phi i32 [ 0, %for.body ], [ %inc, %for.inc ]
-  %exitcond = icmp ne i32 %j.0, 1
-  br i1 %exitcond, label %for.body3, label %for.end
-
-for.body3:                                        ; preds = %for.cond1
-  br label %S1
-
-S1:                                               ; preds = %for.body3
-  %arrayidx = getelementptr inbounds i32, i32* %sum, i32 %j.0
-  %tmp = load i32, i32* %arrayidx, align 4
-  %add = add nsw i32 %tmp, 42
-  store i32 %add, i32* %arrayidx, align 4
-  br label %for.inc
-
-for.inc:                                          ; preds = %S1
-  %inc = add nsw i32 %j.0, 1
-  br label %for.cond1
-
-for.end:                                          ; preds = %for.cond1
-  br label %for.cond4
-
-for.cond4:                                        ; preds = %for.inc9, %for.end
-  %j.1 = phi i32 [ 0, %for.end ], [ %inc10, %for.inc9 ]
-  %exitcond1 = icmp ne i32 %j.1, 100
-  br i1 %exitcond1, label %for.body6, label %for.end11
-
-for.body6:                                        ; preds = %for.cond4
-  br label %S2
-
-S2:                                               ; preds = %for.body6
-  %mul = mul nsw i32 %i.0, %j.1
-  %arrayidx7 = getelementptr inbounds i32, i32* %sum, i32 %j.1
-  %tmp3 = load i32, i32* %arrayidx7, align 4
-  %add8 = add nsw i32 %tmp3, %mul
-  store i32 %add8, i32* %arrayidx7, align 4
-  br label %for.inc9
-
-for.inc9:                                         ; preds = %S2
-  %inc10 = add nsw i32 %j.1, 1
-  br label %for.cond4
-
-for.end11:                                        ; preds = %for.cond4
-  br label %for.inc12
-
-for.inc12:                                        ; preds = %for.end11
-  %inc13 = add nsw i32 %i.0, 1
-  br label %for.cond
-
-for.end14:                                        ; preds = %for.cond
-  ret void
-}
Index: test/Dependences/reduction_simple_iv.ll
===================================================================
--- /dev/null
+++ test/Dependences/reduction_simple_iv.ll
@@ -1,40 +0,0 @@
-; RUN: opt %loadPolly -polly-detect-unprofitable -polly-dependences -analyze < %s | FileCheck %s
-;
-; CHECK:  RAW dependences:
-; CHECK:    {  }
-; CHECK:  WAR dependences:
-; CHECK:    {  }
-; CHECK:  WAW dependences:
-; CHECK:    {  }
-; CHECK:  Reduction dependences:
-; CHECK:    { Stmt_for_cond[i0] -> Stmt_for_cond[1 + i0] : i0 <= 99 and i0 >= 0 }
-;
-; void f(int* sum) {
-;   for (int i = 0; i <= 100; i++)
-;     sum += i * 3;
-; }
-target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-n32-S64"
-
-define void @f(i32* %sum) {
-entry:
-  br label %entry.split1
-
-entry.split1:                                     ; preds = %entry
-  br label %entry.split
-
-entry.split:                                      ; preds = %entry.split1
-  br label %for.cond
-
-for.cond:                                         ; preds = %for.cond, %entry.split
-  %i1.0 = phi i32 [ 0, %entry.split ], [ %inc, %for.cond ]
-  %sum.reload = load i32, i32* %sum
-  %mul = mul nsw i32 %i1.0, 3
-  %add = add nsw i32 %sum.reload, %mul
-  %inc = add nsw i32 %i1.0, 1
-  store i32 %add, i32* %sum
-  %cmp = icmp slt i32 %i1.0, 100
-  br i1 %cmp, label %for.cond, label %for.end
-
-for.end:                                          ; preds = %for.cond
-  ret void
-}
Index: test/Dependences/reduction_simple_iv_debug_wrapped_dependences.ll
===================================================================
--- /dev/null
+++ test/Dependences/reduction_simple_iv_debug_wrapped_dependences.ll
@@ -1,84 +0,0 @@
-; RUN: opt %loadPolly -polly-detect-unprofitable -polly-dependences -analyze -debug-only=polly-dependence 2>&1 < %s | FileCheck %s
-;
-; REQUIRES: asserts
-;
-; CHECK: Read: { [Stmt_for_cond[i0] -> MemRef_sum[0]] -> MemRef_sum[0] : i0 >= 0 and i0 <= 100 }
-; CHECK: Write: { [Stmt_for_cond[i0] -> MemRef_sum[0]] -> MemRef_sum[0] : i0 >= 0 and i0 <= 100 }
-; CHECK: Schedule: {
-; CHECK-DAG: [Stmt_for_cond[i0] -> MemRef_sum[0]] -> [i0] : i0 <= 100 and i0 >= 0
-; CHECK-DAG: Stmt_for_cond[i0] -> [i0]
-; CHECK: }
-; CHECK: Wrapped Dependences:
-; CHECK: RAW dependences:
-; CHECK:   { [Stmt_for_cond[i0] -> MemRef_sum[0]] -> [Stmt_for_cond[1 + i0] -> MemRef_sum[0]] : i0 <= 99 and i0 >= 0 }
-; CHECK: WAR dependences:
-; CHECK:   {  }
-; CHECK: WAW dependences:
-; CHECK:   { [Stmt_for_cond[i0] -> MemRef_sum[0]] -> [Stmt_for_cond[1 + i0] -> MemRef_sum[0]] : i0 <= 99 and i0 >= 0 }
-; CHECK: Reduction dependences:
-; CHECK:   n/a
-; CHECK: Final Wrapped Dependences:
-; CHECK: RAW dependences:
-; CHECK:   {  }
-; CHECK: WAR dependences:
-; CHECK:   {  }
-; CHECK: WAW dependences:
-; CHECK:   {  }
-; CHECK: Reduction dependences:
-; CHECK:   { [Stmt_for_cond[i0] -> MemRef_sum[0]] -> [Stmt_for_cond[1 + i0] -> MemRef_sum[0]] : i0 <= 99 and i0 >= 0 }
-; CHECK: Zipped Dependences:
-; CHECK: RAW dependences:
-; CHECK:   {  }
-; CHECK: WAR dependences:
-; CHECK:   {  }
-; CHECK: WAW dependences:
-; CHECK:   {  }
-; CHECK: Reduction dependences:
-; CHECK:   { [Stmt_for_cond[i0] -> Stmt_for_cond[1 + i0]] -> [MemRef_sum[0] -> MemRef_sum[0]] : i0 <= 99 and i0 >= 0 }
-; CHECK: Unwrapped Dependences:
-; CHECK: RAW dependences:
-; CHECK:   {  }
-; CHECK: WAR dependences:
-; CHECK:   {  }
-; CHECK: WAW dependences:
-; CHECK:   {  }
-; CHECK: Reduction dependences:
-; CHECK:   { Stmt_for_cond[i0] -> Stmt_for_cond[1 + i0] : i0 <= 99 and i0 >= 0 }
-; CHECK: RAW dependences:
-; CHECK:   {  }
-; CHECK: WAR dependences:
-; CHECK:   {  }
-; CHECK: WAW dependences:
-; CHECK:   {  }
-; CHECK: Reduction dependences:
-; CHECK:   { Stmt_for_cond[i0] -> Stmt_for_cond[1 + i0] : i0 <= 99 and i0 >= 0 }
-;
-; void f(int* sum) {
-;   for (int i = 0; i <= 100; i++)
-;     sum += i * 3;
-; }
-target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-n32-S64"
-
-define void @f(i32* %sum) {
-entry:
-  br label %entry.split1
-
-entry.split1:                                     ; preds = %entry
-  br label %entry.split
-
-entry.split:                                      ; preds = %entry.split1
-  br label %for.cond
-
-for.cond:                                         ; preds = %for.cond, %entry.split
-  %i1.0 = phi i32 [ 0, %entry.split ], [ %inc, %for.cond ]
-  %sum.reload = load i32, i32* %sum
-  %mul = mul nsw i32 %i1.0, 3
-  %add = add nsw i32 %sum.reload, %mul
-  %inc = add nsw i32 %i1.0, 1
-  store i32 %add, i32* %sum
-  %cmp = icmp slt i32 %i1.0, 100
-  br i1 %cmp, label %for.cond, label %for.end
-
-for.end:                                          ; preds = %for.cond
-  ret void
-}
Index: test/Dependences/reduction_simple_privatization_deps_2.ll
===================================================================
--- /dev/null
+++ test/Dependences/reduction_simple_privatization_deps_2.ll
@@ -1,79 +0,0 @@
-; RUN: opt %loadPolly -polly-detect-unprofitable -polly-dependences -analyze < %s | FileCheck %s
-;
-; CHECK:      RAW dependences:
-; CHECK-DAG:    Stmt_S1[i0, i1] -> Stmt_S2[i0] : i0 <= 99 and i0 >= 0 and i1 <= 99 and i1 >= 0
-; CHECK-DAG:    Stmt_S0[i0] -> Stmt_S1[i0, o1] : i0 <= 99 and i0 >= 0 and o1 <= 99 and o1 >= 0
-; CHECK-DAG:    Stmt_S2[i0] -> Stmt_S0[1 + i0] : i0 <= 98 and i0 >= 0
-; CHECK:      WAR dependences:
-; CHECK-DAG:     {  }
-; CHECK:      WAW dependences:
-; CHECK-DAG:    Stmt_S1[i0, i1] -> Stmt_S2[i0] : i0 <= 99 and i0 >= 0 and i1 <= 99 and i1 >= 0
-; CHECK-DAG:    Stmt_S0[i0] -> Stmt_S1[i0, o1] : i0 <= 99 and i0 >= 0 and o1 <= 99 and o1 >= 0
-; CHECK-DAG:    Stmt_S2[i0] -> Stmt_S0[1 + i0] : i0 <= 98 and i0 >= 0
-; CHECK:      Reduction dependences:
-; CHECK-DAG:    Stmt_S1[i0, i1] -> Stmt_S1[i0, 1 + i1] : i0 <= 99 and i0 >= 0 and i1 <= 98 and i1 >= 0
-;
-;    void f(int *sum) {
-;      for (int i = 0; i < 100; i++) {
-; S0:    *sum *= 42;
-;        for (int j = 0; j < 100; j++)
-; S1:      *sum += i * j;
-; S2:    *sum *= 7;
-;      }
-;    }
-;
-target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-n32-S64"
-
-define void @f(i32* %sum)  {
-entry:
-  br label %for.cond
-
-for.cond:                                         ; preds = %for.inc6, %entry
-  %i.0 = phi i32 [ 0, %entry ], [ %inc7, %for.inc6 ]
-  %exitcond1 = icmp ne i32 %i.0, 100
-  br i1 %exitcond1, label %for.body, label %for.end8
-
-for.body:                                         ; preds = %for.cond
-  br label %S0
-
-S0:                                               ; preds = %for.body
-  %tmp = load i32, i32* %sum, align 4
-  %mul = mul nsw i32 %tmp, 42
-  store i32 %mul, i32* %sum, align 4
-  br label %for.cond1
-
-for.cond1:                                        ; preds = %for.inc, %S0
-  %j.0 = phi i32 [ 0, %S0 ], [ %inc, %for.inc ]
-  %exitcond = icmp ne i32 %j.0, 100
-  br i1 %exitcond, label %for.body3, label %for.end
-
-for.body3:                                        ; preds = %for.cond1
-  br label %S1
-
-S1:                                               ; preds = %for.body3
-  %mul4 = mul nsw i32 %i.0, %j.0
-  %tmp2 = load i32, i32* %sum, align 4
-  %add = add nsw i32 %tmp2, %mul4
-  store i32 %add, i32* %sum, align 4
-  br label %for.inc
-
-for.inc:                                          ; preds = %S1
-  %inc = add nsw i32 %j.0, 1
-  br label %for.cond1
-
-for.end:                                          ; preds = %for.cond1
-  br label %S2
-
-S2:                                               ; preds = %for.end
-  %tmp3 = load i32, i32* %sum, align 4
-  %mul5 = mul nsw i32 %tmp3, 7
-  store i32 %mul5, i32* %sum, align 4
-  br label %for.inc6
-
-for.inc6:                                         ; preds = %S2
-  %inc7 = add nsw i32 %i.0, 1
-  br label %for.cond
-
-for.end8:                                         ; preds = %for.cond
-  ret void
-}
Index: test/Dependences/reduction_simple_privatization_deps_w_parameter.ll
===================================================================
--- /dev/null
+++ test/Dependences/reduction_simple_privatization_deps_w_parameter.ll
@@ -1,59 +0,0 @@
-; RUN: opt %loadPolly -polly-detect-unprofitable -polly-dependences -analyze < %s | FileCheck %s
-;
-; CHECK:      RAW dependences:
-; CHECK-DAG:    Stmt_S0[] -> Stmt_S1[o0] : N >= 11 and o0 <= 1023 and o0 >= 0
-; CHECK-DAG:    Stmt_S1[i0] -> Stmt_S2[] : N >= 11 and i0 <= 1023 and i0 >= 0
-; CHECK:      WAR dependences:
-; CHECK:       [N] -> {  }
-; CHECK:      WAW dependences:
-; CHECK-DAG:    Stmt_S0[] -> Stmt_S1[o0] : N >= 11 and o0 <= 1023 and o0 >= 0
-; CHECK-DAG:    Stmt_S1[i0] -> Stmt_S2[] : N >= 11 and i0 <= 1023 and i0 >= 0
-; CHECK:   Reduction dependences:
-; CHECK:        Stmt_S1[i0] -> Stmt_S1[1 + i0] : N >= 11 and i0 <= 1022 and i0 >= 0
-;
-;    void f(int *sum, int N) {
-;      if (N >= 10) {
-; S0:    *sum = 0;
-;        for (int i = 0; i < 1024; i++)
-; S1:      *sum += i;
-; S2:    *sum = *sum * 3;
-;      }
-;    }
-target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-n32-S64"
-
-define void @f(i32* %sum, i32 %N) {
-entry:
-  br label %entry.1
-
-entry.1:
-  %excond = icmp sgt i32 %N, 10
-  br i1 %excond, label %S0, label %f.end
-
-S0:
-  store i32 0, i32* %sum, align 4
-  br label %for.cond
-
-for.cond:                                         ; preds = %for.inc, %S0
-  %i.0 = phi i32 [ 0, %S0 ], [ %inc, %for.inc ]
-  %exitcond = icmp ne i32 %i.0, 1024
-  br i1 %exitcond, label %S1, label %S2
-
-S1:                                               ; preds = %for.cond
-  %tmp = load i32, i32* %sum, align 4
-  %add = add nsw i32 %tmp, %i.0
-  store i32 %add, i32* %sum, align 4
-  br label %for.inc
-
-for.inc:                                          ; preds = %S1
-  %inc = add nsw i32 %i.0, 1
-  br label %for.cond
-
-S2:                                               ; preds = %for.cond
-  %tmp1 = load i32, i32* %sum, align 4
-  %mul = mul nsw i32 %tmp1, 3
-  store i32 %mul, i32* %sum, align 4
-  br label %f.end
-
-f.end:
-  ret void
-}
Index: test/Dependences/reduction_two_reductions_different_rloops.ll
===================================================================
--- /dev/null
+++ test/Dependences/reduction_two_reductions_different_rloops.ll
@@ -1,72 +0,0 @@
-; RUN: opt %loadPolly -polly-detect-unprofitable -basicaa -polly-dependences -analyze < %s | FileCheck %s
-;
-; CHECK: RAW dependences:
-; CHECK:   {  }
-; CHECK: WAR dependences:
-; CHECK:   {  }
-; CHECK: WAW dependences:
-; CHECK:   {  }
-; CHECK: Reduction dependences:
-; CHECK-DAG: Stmt_for_body3[i0, i1] -> Stmt_for_body3[o0, 1 + i0 + i1 - o0] : o0 <= 1 + i0 and o0 >= i0 and o0 <= 1023 and i0 >= 0 and i1 >= 0 and o0 >= -1022 + i0 + i1
-;
-; void f(int *restrict A, int *restrict B, int *restrict Values) {
-;   for (int i = 0; i < 1024; i++) {
-;     for (int j = 0; j < 1024; j++) {
-;       A[i] += Values[i + j - 1];
-;       B[j] += Values[i + j + 42];
-;     }
-;   }
-; }
-;
-target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-n32-S64"
-
-define void @f(i32* noalias %A, i32* noalias %B, i32* noalias %Values)  {
-entry:
-  br label %for.cond
-
-for.cond:                                         ; preds = %for.inc11, %entry
-  %i.0 = phi i32 [ 0, %entry ], [ %inc12, %for.inc11 ]
-  %exitcond1 = icmp ne i32 %i.0, 1024
-  br i1 %exitcond1, label %for.body, label %for.end13
-
-for.body:                                         ; preds = %for.cond
-  br label %for.cond1
-
-for.cond1:                                        ; preds = %for.inc, %for.body
-  %j.0 = phi i32 [ 0, %for.body ], [ %inc, %for.inc ]
-  %exitcond = icmp ne i32 %j.0, 1024
-  br i1 %exitcond, label %for.body3, label %for.end
-
-for.body3:                                        ; preds = %for.cond1
-  %add = add nsw i32 %i.0, %j.0
-  %sub = add nsw i32 %add, -1
-  %arrayidx = getelementptr inbounds i32, i32* %Values, i32 %sub
-  %tmp = load i32, i32* %arrayidx, align 4
-  %arrayidx4 = getelementptr inbounds i32, i32* %A, i32 %i.0
-  %tmp2 = load i32, i32* %arrayidx4, align 4
-  %add5 = add nsw i32 %tmp2, %tmp
-  store i32 %add5, i32* %arrayidx4, align 4
-  %add6 = add nsw i32 %i.0, %j.0
-  %add7 = add nsw i32 %add6, 42
-  %arrayidx8 = getelementptr inbounds i32, i32* %Values, i32 %add7
-  %tmp3 = load i32, i32* %arrayidx8, align 4
-  %arrayidx9 = getelementptr inbounds i32, i32* %B, i32 %j.0
-  %tmp4 = load i32, i32* %arrayidx9, align 4
-  %add10 = add nsw i32 %tmp4, %tmp3
-  store i32 %add10, i32* %arrayidx9, align 4
-  br label %for.inc
-
-for.inc:                                          ; preds = %for.body3
-  %inc = add nsw i32 %j.0, 1
-  br label %for.cond1
-
-for.end:                                          ; preds = %for.cond1
-  br label %for.inc11
-
-for.inc11:                                        ; preds = %for.end
-  %inc12 = add nsw i32 %i.0, 1
-  br label %for.cond
-
-for.end13:                                        ; preds = %for.cond
-  ret void
-}
Index: test/Isl/CodeGen/MemAccess/simple_analyze.ll
===================================================================
--- test/Isl/CodeGen/MemAccess/simple_analyze.ll
+++ test/Isl/CodeGen/MemAccess/simple_analyze.ll
@@ -48,6 +48,18 @@
 ; 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]* @A, i32 0, i32 0)
+; JSCOPVEC:  store i32 1, i32* getelementptr inbounds ([100 x i32]* @A, i32 0, i32 0)
+; JSCOPVEC:  store i32 2, i32* getelementptr inbounds ([100 x i32]* @A, i32 0, i32 0)
+; JSCOPVEC:  store i32 3, i32* getelementptr inbounds ([100 x i32]* @A, i32 0, i32 0)
+; JSCOPVEC:  store i32 4, i32* getelementptr inbounds ([100 x i32]* @A, i32 0, i32 0)
+; JSCOPVEC:  store i32 5, i32* getelementptr inbounds ([100 x i32]* @A, i32 0, i32 0)
+; JSCOPVEC:  store i32 6, i32* getelementptr inbounds ([100 x i32]* @A, i32 0, i32 0)
+; JSCOPVEC:  store i32 7, i32* getelementptr inbounds ([100 x i32]* @A, i32 0, i32 0)
+; JSCOPVEC:  store i32 8, i32* getelementptr inbounds ([100 x i32]* @A, i32 0, i32 0)
+; JSCOPVEC:  store i32 9, i32* getelementptr inbounds ([100 x i32]* @A, i32 0, i32 0)
+; JSCOPVEC:  store i32 10, i32* getelementptr inbounds ([100 x i32]* @A, i32 0, i32 0)
+; JSCOPVEC:  store i32 11, i32* getelementptr inbounds ([100 x i32]* @A, i32 0, i32 0)
 
 ; JSCOPVEC:  store i32 0, i32* getelementptr inbounds ([100 x i32]* @B, i32 0, i32 0)
 ; JSCOPVEC:  store i32 1, i32* getelementptr inbounds ([100 x i32]* @B, i32 0, i32 0)
@@ -62,15 +74,3 @@
 ; JSCOPVEC:  store i32 10, i32* getelementptr inbounds ([100 x i32]* @B, i32 0, i32 0)
 ; JSCOPVEC:  store i32 11, i32* getelementptr inbounds ([100 x i32]* @B, i32 0, i32 0)
 
-; JSCOPVEC:  store i32 0, i32* getelementptr inbounds ([100 x i32]* @A, i32 0, i32 0)
-; JSCOPVEC:  store i32 1, i32* getelementptr inbounds ([100 x i32]* @A, i32 0, i32 0)
-; JSCOPVEC:  store i32 2, i32* getelementptr inbounds ([100 x i32]* @A, i32 0, i32 0)
-; JSCOPVEC:  store i32 3, i32* getelementptr inbounds ([100 x i32]* @A, i32 0, i32 0)
-; JSCOPVEC:  store i32 4, i32* getelementptr inbounds ([100 x i32]* @A, i32 0, i32 0)
-; JSCOPVEC:  store i32 5, i32* getelementptr inbounds ([100 x i32]* @A, i32 0, i32 0)
-; JSCOPVEC:  store i32 6, i32* getelementptr inbounds ([100 x i32]* @A, i32 0, i32 0)
-; JSCOPVEC:  store i32 7, i32* getelementptr inbounds ([100 x i32]* @A, i32 0, i32 0)
-; JSCOPVEC:  store i32 8, i32* getelementptr inbounds ([100 x i32]* @A, i32 0, i32 0)
-; JSCOPVEC:  store i32 9, i32* getelementptr inbounds ([100 x i32]* @A, i32 0, i32 0)
-; JSCOPVEC:  store i32 10, i32* getelementptr inbounds ([100 x i32]* @A, i32 0, i32 0)
-; JSCOPVEC:  store i32 11, i32* getelementptr inbounds ([100 x i32]* @A, i32 0, i32 0)
Index: test/Isl/CodeGen/simple_loop_non_single_exit.ll
===================================================================
--- test/Isl/CodeGen/simple_loop_non_single_exit.ll
+++ test/Isl/CodeGen/simple_loop_non_single_exit.ll
@@ -1,4 +1,4 @@
-; RUN: opt %loadPolly -polly-detect-unprofitable -polly-no-early-exit -polly-codegen-isl -analyze < %s | FileCheck %s
+; RUN: opt %loadPolly -polly-detect-unprofitable -polly-no-early-exit -polly-ast -analyze < %s | FileCheck %s
 ; RUN: opt %loadPolly -polly-detect-unprofitable -polly-no-early-exit -polly-codegen-isl -S < %s | FileCheck %s -check-prefix=CHECK-CODE
 
 ; void f(long A[], long N) {
@@ -32,6 +32,6 @@
   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
Index: test/Isl/CodeGen/simple_loop_non_single_exit_2.ll
===================================================================
--- test/Isl/CodeGen/simple_loop_non_single_exit_2.ll
+++ test/Isl/CodeGen/simple_loop_non_single_exit_2.ll
@@ -1,4 +1,4 @@
-; RUN: opt %loadPolly -polly-detect-unprofitable -polly-no-early-exit -polly-codegen-isl -analyze < %s | FileCheck %s
+; RUN: opt %loadPolly -polly-detect-unprofitable -polly-no-early-exit -polly-ast -analyze < %s | FileCheck %s
 ; RUN: opt %loadPolly -polly-detect-unprofitable -polly-no-early-exit -polly-codegen-isl -S < %s | FileCheck %s -check-prefix=CHECK-CODE
 
 ; void f(long A[], long N) {
@@ -33,6 +33,6 @@
   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
Index: test/Isl/CodeGen/simple_non_single_entry.ll
===================================================================
--- test/Isl/CodeGen/simple_non_single_entry.ll
+++ test/Isl/CodeGen/simple_non_single_entry.ll
@@ -1,4 +1,4 @@
-; RUN: opt %loadPolly -polly-detect-unprofitable -polly-no-early-exit -polly-detect-scops-in-regions-without-loops -polly-codegen-isl -analyze < %s | FileCheck %s
+; RUN: opt %loadPolly -polly-detect-unprofitable -polly-no-early-exit -polly-detect-scops-in-regions-without-loops -polly-ast -analyze < %s | FileCheck %s
 ; RUN: opt %loadPolly -polly-detect-unprofitable -polly-no-early-exit -polly-detect-scops-in-regions-without-loops -polly-codegen-isl -S < %s | FileCheck %s -check-prefix=CHECK-CODE
 
 ; void f(long A[], long N) {
@@ -66,6 +66,6 @@
   ret void
 }
 
-; CHECK: Create LLVM-IR from SCoPs' for region: 'next.split => polly.merge_new_and_old'
+; CHECK: :: isl ast :: f :: next => for.i.head1
 ; CHECK-CODE: polly.split_new_and_old
 ; CHECK-CODE: polly.merge_new_and_old
Index: test/Isl/CodeGen/single_loop_zero_iterations.ll
===================================================================
--- test/Isl/CodeGen/single_loop_zero_iterations.ll
+++ test/Isl/CodeGen/single_loop_zero_iterations.ll
@@ -65,5 +65,5 @@
   ret i32 %retval.0
 }
 
-; CHECK: for region: 'for.cond => for.end.region' in function 'main':
+; CHECK:       :: isl ast :: main :: for.cond => for.end.region
 ; CHECK-NOT:   Stmt_for_body(0);
Index: test/Isl/CodeGen/two-scops-in-row.ll
===================================================================
--- test/Isl/CodeGen/two-scops-in-row.ll
+++ test/Isl/CodeGen/two-scops-in-row.ll
@@ -4,6 +4,9 @@
 target triple = "x86_64-unknown-linux-gnu"
 
 ; CHECK: if (1)
+; CHECK:     Stmt_for_0(0);
+
+; CHECK: if (1)
 ; CHECK:     {
 ; CHECK:       for (int c0 = 0; c0 <= -Scalar0.val.loadoutside + 99; c0 += 1)
 ; CHECK:         Stmt_for_1(c0);
@@ -11,9 +14,6 @@
 ; CHECK:         Stmt_for_1(0);
 ; CHECK:     }
 
-; CHECK: if (1)
-; CHECK:     Stmt_for_0(0);
-
 
 define void @foo(i32* %A) {
 entry:
Index: test/ScopInfo/aliasing_many_parameters_not_all_involved.ll
===================================================================
--- test/ScopInfo/aliasing_many_parameters_not_all_involved.ll
+++ test/ScopInfo/aliasing_many_parameters_not_all_involved.ll
@@ -4,11 +4,9 @@
 ; 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:       Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'for.cond => for.end' in function 'jd':
-; MAX8-NEXT:  Function: jd
+; MAX8:     Function: jd
 
-; MAX7:       Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'for.cond => for.end' in function 'jd':
-; MAX7-NEXT:  Invalid Scop!
+; 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) {
Index: test/ScopInfo/integers.ll
===================================================================
--- test/ScopInfo/integers.ll
+++ test/ScopInfo/integers.ll
@@ -16,7 +16,8 @@
   store i1024 %indvar, i1024* %scevgep, 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
 
@@ -35,7 +36,8 @@
   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
 
@@ -55,7 +57,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
 
@@ -74,7 +77,8 @@
   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
@@ -93,7 +97,8 @@
   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
@@ -113,7 +118,8 @@
   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
Index: test/ScopInfo/undef_in_cond.ll
===================================================================
--- test/ScopInfo/undef_in_cond.ll
+++ test/ScopInfo/undef_in_cond.ll
@@ -20,4 +20,4 @@
   ret void
 }
 
-; CHECK: Invalid Scop!
+; CHECK-NOT: Statements