[Refactor] Replace RegionPasses by FunctionPasses

[jdoerfert]

Summary

The main change is the switch to function instead of region passes.
This will save compile time as we do not have to query the
TempScopInfo for each region anymore.  However, due to the changed
interface and the now explicit iteration over regions in a function
other adjustments were made too.

[jdoerfert]

lib/Analysis/ScopInfo.cpp

2005–2006

A Scops.pop_back() is missing here.

2026–2027

This line needs to be removed in order to loop again.

[jdoerfert]

Small fixes

[jdoerfert]

Allow multiple SCoPs in ScopPasses + fix tests

[jdoerfert]

I will cut this commit into pieces (as far as possible) but I wanted to get some initial feedback.

[grosser]

Hi Johannes,

what is the motivation and the impact of this change? The only motivation of this change you give in the commit message is compile time. Did you measure any significant improvements here? I personally think there are very good reasons to change/improve our pass infrastructure, but am surprised compile-time is the one and only that motivates your change.

I see two main reasons to work on the pass infrastructure:

1. Make it work with Chandler's new pass manager

Chandler's new pass manager uses caching to keep multiple analysis results. I believe when we perform changes to our pass infrastructure, we should try to make sure it will work with Chandler's new pass manager.
Besides his last PassManager talk, commits such as https://llvm.org/svn/llvm-project/llvm/trunk@226560 show the idea of using caching results.

2. Fix the LoopInfo/RegionInfo misconception

We currently assume ScopPasses on different regions do not affect each other. However, they indeed
affect each other, which means code-generating one scop may invalidate the next scop. Hence, we have some hacks in place to detect this invalidated scops. The (implicit) pass order change your patch brings does not seem to improve this in any way.

I am not saying your patch should solve those two issues, but maybe it is a good time to reason about this and at least understand if they will not negatively affect these changes (or possibly even help to solve some).

I added a couple of first comments to your patch, but before going further I would like to understand your intentions.

Cheers,
Tobias

include/polly/DependenceInfo.h

1

Needs update, if renamed.

24

Needs update, if renamed.

140

The idea of introducing an analysis result for each individual Scop
is very much in line with Chandler's new analysis infrastructure. However, to me it seem you only went half wayby leaving most functions on the pass itself. Looking at this, introducing per-scop-dependence objects seems to be an almost independent change.

include/polly/LinkAllPasses.h

31

I would personally not perform such renaming as part this patch, as it causes noise all over the place.

lib/Analysis/DependenceInfo.cpp

1

Needs updated if you want to perform renaming.

351

These are a lot of D.*? Would it make sense to make all this functionality part of the Dependences object/class.

453

I have the feeling passing the scop to each of this functions unnecessarily complicates the interface. Could we not just once ask for the dependences object of this scop and then work with it?

[jdoerfert]

Hey Tobias,

let me give you a short answer now and a more detailed one later:

• Compile time: We perform much better on large test with a lot of regions. Here are some examples after one lnt run for a release build.
  
  MultiSource/Benchmarks/tramp3d-v4/tramp3d-v4 -89.42% 345.5400 36.5533 - - SingleSource/Benchmarks/Misc-C++-EH/spirit -78.71% 33.4433 7.1200 - - MultiSource/Applications/kimwitu++/kc -71.26% 77.1700 22.1766 - - MultiSource/Benchmarks/MiBench/consumer-typeset/consumer-typeset -67.55% 65.2370 21.1667 - - SingleSource/UnitTests/DefaultInitDynArrays -50.00% 0.0200 0.0100 - - SingleSource/Benchmarks/Adobe-C++/simple_types_constant_folding -42.39% 8.6267 4.9700 - - MultiSource/Applications/sqlite3/sqlite3 -42.16% 60.4734 34.9800 - - MultiSource/Benchmarks/ASCI_Purple/SMG2000/smg2000 -39.79% 19.6970 11.8601 - - SingleSource/Regression/C++/EH/inlined_cleanup -38.34% 0.0433 0.0267 - - MultiSource/Applications/JM/ldecod/ldecod -37.42% 23.0533 14.4267 - - MultiSource/Applications/oggenc/oggenc -33.81% 24.6900 16.3433 - - SingleSource/Benchmarks/Stanford/Treesort -31.79% 0.0733 0.0500 - - MultiSource/Applications/lemon/lemon -30.80% 2.8467 1.9700 - - SingleSource/Benchmarks/Shootout/strcat -30.72% 0.0433 0.0300 - - MultiSource/Applications/JM/lencod/lencod -28.96% 39.8598 28.3167 - - MultiSource/Benchmarks/PAQ8p/paq8p -26.53% 4.6367 3.4067
  
  Note that for a debug build I more or less always time out on some of these benchmarks after 500s with the old pass system! I admit the changes (especially in the DependenceInfo pass) can be made even more efficient but that is an easy patch I can write afterwards.
• I don't know enough about the new pass manager to say how this change will affect it.
• SCoPs affecting each other are a misconception by design (at least in my opinion). We should make the code generation aware of that (e.g., do not split the exit block of a region at 3 different locations in Polly!). However, this change passes lnt and all unit tests and we detect exactly the same number of SCoPs, that is at least a hint that we can make function passes work. With scalar/phi code generation and without independent blocks and code prepare the impact of one SCoP on another should be even smaller.

I hope you reconsider this change, at least after I provide more accurate
numbers.

Best regards,

Johannes

• msg-20286-67.dat219 BDownload

[jdoerfert]

Hey Tobias,

I attached 2 lnt reports to this mail. The first (report_region.json)
was created using the current polly/master. The second
(report_function.json) was created with the region->function pass patch.
Note that this patch is not yet at its full capacity, however over the 3
runs I measured I got:

Performance Regressions  16
Performance Improvements  159
Unchanged Tests   817
Total Tests   992

Where as the execution time changes (only 8 in total) should be jitter.

The point I try to make here is, 3 runs with the region pass manager take

2:35:27 (3 runs region passes)

but 3 runs with the function pass manager only

2:07:48 (3 runs function passes)

hence we save ~18% of the lnt time (if I didn't do a stupid math mistake).

To be precise, we save compile time "only" for larger functions with small SCoP
coverage but we do not pay for it in any other case.

Does this convince you that region passes have a bad impact on compile time?

Best regards,

Johannes

• report_function.json548 KBDownload
• msg-7066-192.dat219 BDownload
• report_region.json548 KBDownload

[• zinob]

Johannes and Tobias,

We just discovered an issues with compiler time in the region pass manager. In particular in Release build where Name are not preserved

Lib/Analysis/RegionPass.cpp (86):
dumpPassInfo(P, EXECUTION_MSG, ON_REGION_MSG, CurrentRegion->getNameStr());

getNameStr() is very expensive because it LLVM construct a new Name. The compile-time issue you guys are seeing might be due to this issue.

Our fix right now is to pass empty string in release build. Toby, if you think this acceptable short term solution. Sanjin can submit a patch?

-Zino

[• zinob]

Ok we will post it shortly.

Zino

[grosser]

The patch Zino refers to was committed in 231485. It did not have a large impact on our LNT performance builders (which do not seem to even see the slowdown we try to address here). However, on my laptop I was able to reproduce this performance issue in a cmake release build and Zino's patch fixes it at least for tramp3d-v4 nicely. Johannes, could you check if there is still a performance issue that needs to be addressed?

lib/Transform/ScheduleOptimizer.cpp

58

Why are these renamed?

528

Is this rename intentional?

[jdoerfert]

• msg-29914-148.dat219 BDownload

[jdoerfert]

I will cut this commit into pieces (as far as possible) but I wanted to get some initial feedback.

In D7986#136089, @grosser wrote:

The patch Zino refers to was committed in 231485. It did not have a large impact on our LNT performance builders (which do not seem to even see the slowdown we try to address here). However, on my laptop I was able to reproduce this performance issue in a cmake release build and Zino's patch fixes it at least for tramp3d-v4 nicely. Johannes, could you check if there is still a performance issue that needs to be addressed?

How can the buildbots run e.g., tramp3d in 9sec when it takes for me with lnt
[1,2] >40sec for one of the source files alone. This is not new but they do
perform that good all the time... I'm puzzled here...

[1] --mllvm=-polly -clfag=-O3 in the cmd line options of the lnt runtest command

(Polly is linked into clang/opt)

[2] Alternatively the command with polly basically disabled (via polly-only-func):

/home/johannes/projects/polly/llvm-build/bin/clang++ -fno-exceptions -I/home/johannes/mysandbox/nt/test-2015-03-01_14-37-50/sample-0/MultiSource/Benchmarks/tramp3d-v4 -I/home/johannes/repos/llvm-test-suite/MultiSource/Benchmarks/tramp3d-v4 -I/home/johannes/repos/llvm-test-suite/include -I../../../include -D_GNU_SOURCE -D__STDC_LIMIT_MACROS -DNDEBUG -O3 -mllvm -polly -m64 -fomit-frame-pointer -c /home/johannes/repos/llvm-test-suite/MultiSource/Benchmarks/tramp3d-v4/tramp3d-v4.cpp -o /dev/null  -mllvm -polly-only-func=dsadsasadsa -mllvm -polly-allow-nonaffine-branches=false

[grosser]

In D7986#136089, @grosser wrote:

The patch Zino refers to was committed in 231485. It did not have a large impact on our LNT performance builders (which do not seem to even see the slowdown we try to address here). However, on my laptop I was able to reproduce this performance issue in a cmake release build and Zino's patch fixes it at least for tramp3d-v4 nicely. Johannes, could you check if there is still a performance issue that needs to be addressed?

How can the buildbots run e.g., tramp3d in 9sec when it takes for me with lnt
[1,2] >40sec for one of the source files alone. This is not new but they do
perform that good all the time... I'm puzzled here...

Looking at the buildbot history, it seems we never had compile-times below 35 seconds. Can you remember where you got these 9 seconds from?

http://llvm.org/perf/db_default/v4/nts/graph?highlight_run=27014&plot.1349=23.1349.1

Johannes, I also wonder what you plan to do with the patch here. It seems the original compile time issues that it meant to fix have been resolved. Are you still planning to submit this patch for other reasons or should we close this review for now?

[jdoerfert]

In D7986#175077, @grosser wrote:

Looking at the buildbot history, it seems we never had compile-times below 35 seconds. Can you remember where you got these 9 seconds from?

http://llvm.org/perf/db_default/v4/nts/graph?highlight_run=27014&plot.1349=23.1349.1

My comment is over 2 months old. I cannot remember where I got this number from. Maybe I missread something or I used a number of a local lnt run.

Johannes, I also wonder what you plan to do with the patch here. It seems the original compile time issues that it meant to fix have been resolved. Are you still planning to submit this patch for other reasons or should we close this review for now?

I'll close this as there doesn't seem any interest in it.

include/polly/CodeGen/IslAst.h

 #include "polly/ScopPass.h"
 
 #include "isl/ast.h"
 
 namespace llvm {
 class raw_ostream;
 }
 
+struct isl_pw_aff;
 struct isl_ast_node;
 struct isl_ast_expr;
 struct isl_ast_build;
 struct isl_union_map;
 struct isl_pw_multi_aff;
 
 namespace polly {
 class Scop;
 class IslAst;
 class MemoryAccess;
+class DependenceInfo;
 
 class IslAstInfo : public ScopPass {
 public:
   using MemoryAccessSet = SmallPtrSet<MemoryAccess *, 4>;
 
   /// @brief Payload information used to annotate an AST node.
   struct IslAstUserPayload {
     /// @brief Construct and initialize the payload.
struct IslAstUserPayload {
     /// @brief The build environment at the time this node was constructed.
     isl_ast_build *Build;
 
     /// @brief Set of accesses which break reduction dependences.
     MemoryAccessSet BrokenReductions;
   };
 
 private:
-  Scop *S;
-  IslAst *Ast;
+  /// @brief Mapping from SCoP to AST representation.
+  DenseMap<const Scop *, IslAst *> AstMap;
+
+  /// @brief The dependence info pass.
+  DependenceInfo *DI;
 
 public:
   static char ID;
-  IslAstInfo() : ScopPass(ID), S(nullptr), Ast(nullptr) {}
+  IslAstInfo() : ScopPass(ID) {}
 
   /// @brief Build the AST for the given SCoP @p S.
-  bool runOnScop(Scop &S);
+  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.
   ///
   /// Only if the run condition evaluates at run-time to a non-zero value, the
   /// assumptions that have been taken hold. If the run condition evaluates to
   /// zero/false some assumptions do not hold and the original code needs to
   /// be executed.
-  __isl_give isl_ast_expr *getRunCondition() const;
+  __isl_give isl_ast_expr *getRunCondition(Scop &S) const;
 
   /// @name Extract information attached to an isl ast (for) node.
   ///
   ///{
 
   /// @brief Get the complete payload attached to @p Node.
   static IslAstUserPayload *getNodePayload(__isl_keep isl_ast_node *Node);
 
public:
 
   /// @brief Get the nodes broken reductions or a nullptr if not available.
   static MemoryAccessSet *getBrokenReductions(__isl_keep isl_ast_node *Node);
 
   /// @brief Get the nodes build context or a nullptr if not available.
   static __isl_give isl_ast_build *getBuild(__isl_keep isl_ast_node *Node);
 
   ///}
-
-  virtual void getAnalysisUsage(AnalysisUsage &AU) const;
-  virtual void releaseMemory();
 };
 }
 
 namespace llvm {
 class PassRegistry;
 void initializeIslAstInfoPass(llvm::PassRegistry &);
 }
 #endif /* POLLY_ISL_AST_H */

include/polly/DependenceInfo.h

 //===------ polly/Dependences.h - Polyhedral dependency analysis *- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // Calculate the data dependency relations for a Scop using ISL.
 //
 // The integer set library (ISL) from Sven, has a integrated dependency analysis
 // to calculate data dependences. This pass takes advantage of this and
 // calculate those dependences a Scop.
 //
 // The dependences in this pass are exact in terms that for a specific read
 // statement instance only the last write statement instance is returned. In
 // case of may writes a set of possible write instances is returned. This
 // analysis will never produce redundant dependences.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef POLLY_DEPENDENCES_H
 #define POLLY_DEPENDENCES_H
 
 #include "polly/ScopPass.h"
 
 #include <map>
 #include "isl/ctx.h"
 
 struct isl_pw_aff;
 struct isl_union_map;
 struct isl_union_set;
 struct isl_map;
 struct isl_set;
 struct clast_for;
 
 using namespace llvm;
 
 namespace polly {
 
 class Scop;
 class ScopStmt;
 class MemoryAccess;
 
-class Dependences : public ScopPass {
+class DependenceInfo : public ScopPass {
 public:
   static char ID;
 
   /// @brief The type of the dependences.
   ///
   /// Reduction dependences are separated from RAW/WAW/WAR dependences because
   /// we can ignore them during the scheduling. This is the case since the order
   /// in which the reduction statements are executed does not matter. However,
enum Type {
     TYPE_RED = 1 << 3,
 
     // Transitive closure of the reduction dependences (& the reverse)
     TYPE_TC_RED = 1 << 4,
   };
 
   typedef std::map<ScopStmt *, isl_map *> StatementToIslMapTy;
 
-  Dependences();
+  /// @brief Pass constructor
+  DependenceInfo() : ScopPass(ID) {}
 
   /// @brief Check if a new scattering is valid.
   ///
   /// @param NewScattering The new scatterings
   ///
   /// @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.
   ///
   /// @param Schedule       The subset of the scattering space that we want to
   ///                       check.
   /// @param Deps           The dependences @p Schedule needs to respect.
   /// @param MinDistancePtr If not nullptr, the minimal dependence distance will
   ///                       be returned at the address of that pointer
   ///
   /// @return Returns true, if executing parallel the outermost dimension of
   ///         @p Schedule is valid according to the dependences @p Deps.
   bool isParallel(__isl_keep isl_union_map *Schedule,
                   __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;
   void releaseMemory() override;
   void getAnalysisUsage(AnalysisUsage &AU) const override;
 
 private:
-  Scop *S;
-
+  /// @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 Mapping from SCoPs to their dependence structs.
+  DenseMap<const Scop *, Dependences> DependenceMap;
+
+  /// @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 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,
                    isl_union_map **MayWrite, isl_union_map **AccessSchedule,
                    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

include/polly/LinkAllPasses.h

 class PassInfo;
 class PassRegistry;
 class RegionPass;
 }
 
 namespace polly {
 llvm::Pass *createCodePreparationPass();
 llvm::Pass *createDeadCodeElimPass();
-llvm::Pass *createDependencesPass();
+llvm::Pass *createDependenceInfoPass();
 llvm::Pass *createDOTOnlyPrinterPass();
 llvm::Pass *createDOTOnlyViewerPass();
 llvm::Pass *createDOTPrinterPass();
 llvm::Pass *createDOTViewerPass();
 llvm::Pass *createIndependentBlocksPass();
 llvm::Pass *createJSONExporterPass();
 llvm::Pass *createJSONImporterPass();
 #ifdef PLUTO_FOUND
PollyForcePassLinking() {
     // delete it all as dead code, even with whole program optimization,
     // yet is effectively a NO-OP. As the compiler isn't smart enough
     // to know that getenv() never returns -1, this will do the job.
     if (std::getenv("bar") != (char *)-1)
       return;
 
     polly::createCodePreparationPass();
     polly::createDeadCodeElimPass();
-    polly::createDependencesPass();
+    polly::createDependenceInfoPass();
     polly::createDOTOnlyPrinterPass();
     polly::createDOTOnlyViewerPass();
     polly::createDOTPrinterPass();
     polly::createDOTViewerPass();
     polly::createIndependentBlocksPass();
     polly::createJSONExporterPass();
     polly::createJSONImporterPass();
     polly::createScopDetectionPass();

include/polly/ScopInfo.h

 //
 //===----------------------------------------------------------------------===//
 
 #ifndef POLLY_SCOP_INFO_H
 #define POLLY_SCOP_INFO_H
 
 #include "polly/ScopDetection.h"
 
-#include "llvm/Analysis/RegionPass.h"
+#include "llvm/Pass.h"
 
 #include "isl/ctx.h"
 
 using namespace llvm;
 
 namespace llvm {
 class Loop;
 class LoopInfo;
private:
   /// In a program with int and float pointers annotated with tbaa information
   /// we would probably generate two alias groups, one for the int pointers and
   /// one for the float pointers.
   ///
   /// During code generation we will create a runtime alias check for each alias
   /// 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,
   /// it does not need to be represented as a polyhedral statement.
   ///
   /// @param BB The basic block to check
   /// @param tempScop TempScop returning further information regarding the Scop.
   ///
private:
   void printContext(raw_ostream &OS) const;
   void printStatements(raw_ostream &OS) const;
   void printAliasAssumptions(raw_ostream &OS) const;
   ///}
 
   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;
 
   /// @brief Get the count of parameters used in this Scop.
   ///
   /// @return The count of parameters used in this Scop.
   inline ParamVecType::size_type getNumParams() const {

 static inline raw_ostream &operator<<(raw_ostream &O, const Scop &scop) {
   scop.print(O);
   return O;
 }
 
 ///===---------------------------------------------------------------------===//
 /// @brief Build the Polly IR (Scop and ScopStmt) on a Region.
 ///
-class ScopInfo : public RegionPass {
-  //===-------------------------------------------------------------------===//
+class ScopInfo : public FunctionPass {
+public:
+  /// @brief Type for a vector of SCoPs.
+  using ScopVectorTy = SmallVector<Scop *, 4>;
+
+  /// @brief Iterator type for a SCoP vector.
+  using iterator = ScopVectorTy::iterator;
+  using const_iterator = ScopVectorTy::const_iterator;
+
+private:
   ScopInfo(const ScopInfo &) = delete;
   const ScopInfo &operator=(const ScopInfo &) = delete;
 
-  // The Scop
-  Scop *scop;
-  isl_ctx *ctx;
-
-  void clear() {
-    if (scop) {
-      delete scop;
-      scop = 0;
-    }
-  }
+  /// @brief The SCoPs build in this function.
+  ScopVectorTy Scops;
+
+  /// @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;
   //@}
 };
 
 } // end namespace polly
 
 namespace llvm {
 class PassRegistry;
 void initializeScopInfoPass(llvm::PassRegistry &);
 }
 
 #endif

include/polly/ScopPass.h

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

lib/Analysis/DependenceInfo.cpp

 //===- Dependences.cpp - Calculate dependency information for a Scop. -----===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // Calculate the data dependency relations for a Scop using ISL.
 //
 // The integer set library (ISL) from Sven, has a integrated dependency analysis
 // to calculate data dependences. This pass takes advantage of this and
 // calculate those dependences a Scop.
 //
 // The dependences in this pass are exact in terms that for a specific read
 // statement instance only the last write statement instance is returned. In
 // case of may writes a set of possible write instances is returned. This
 // analysis will never produce redundant dependences.
 //
 //===----------------------------------------------------------------------===//
 //
-#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>
 #include <isl/ctx.h>
 #include <isl/flow.h>
 #include <isl/map.h>
 #include <isl/options.h>
 #include <isl/set.h>
cl::values(clEnumValN(VALUE_BASED_ANALYSIS, "value-based",
                           "Exact dependences without transitive dependences"),
                clEnumValN(MEMORY_BASED_ANALYSIS, "memory-based",
                           "Overapproximation of dependences"),
                clEnumValEnd),
     cl::Hidden, cl::init(VALUE_BASED_ANALYSIS), cl::ZeroOrMore,
     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,
+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));
   *MayWrite = isl_union_map_empty(isl_space_copy(Space));
   *AccessSchedule = isl_union_map_empty(isl_space_copy(Space));
   *StmtSchedule = isl_union_map_empty(Space);
 
   SmallPtrSet<const Value *, 8> ReductionBaseValues;

 ///   WAW:
 ///     { S0[] -> S1[i0] : i0 >= 0 and i0 <= 1023;
 ///       S1[i0] -> S2[] : i0 >= 0 and i0 <= 1023}
 ///   RED:
 ///     { S1[i0] -> S1[1 + i0] : i0 >= 0 and i0 <= 1022 }
 ///
 /// 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);
   }
 
   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);
 
   Schedule =
       isl_union_map_union(AccessSchedule, isl_union_map_copy(StmtSchedule));
 
   Read = isl_union_map_coalesce(Read);
   Write = isl_union_map_coalesce(Write);
   MayWrite = isl_union_map_coalesce(MayWrite);
 
   long MaxOpsOld = isl_ctx_get_max_operations(S.getIslCtx());
   isl_ctx_set_max_operations(S.getIslCtx(), OptComputeOut);
   isl_options_set_on_error(S.getIslCtx(), ISL_ON_ERROR_CONTINUE);
 
   DEBUG(dbgs() << "Read: " << Read << "\n";
         dbgs() << "Write: " << Write << "\n";
         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;
 
     Empty = isl_union_map_empty(isl_union_map_get_space(Write));
     Write = isl_union_map_union(Write, isl_union_map_copy(MayWrite));
 
     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);
   }
 
   isl_union_map_free(MayWrite);
   isl_union_map_free(Write);
   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);
   isl_ctx_reset_operations(S.getIslCtx());
   isl_ctx_set_max_operations(S.getIslCtx(), MaxOpsOld);
 
   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";
     printScop(dbgs(), S);
     dbgs() << "\n";
   });
 
   // To handle reduction dependences we proceed as follows:
   // 1) Aggregate all possible reduction dependences, namely all self
   //    dependences on reduction like statements.
   // 2) Intersect them with the actual RAW & WAW dependences to the get the
   //    actual reduction dependences. This will ensure the load/store memory
   //    addresses were __identical__ in the two iterations of the statement.
   // 3) Relax the original RAW and WAW dependences by substracting the actual
   //    reduction dependences. Binary reductions (sum += A[i]) cause both, and
   //    the same, RAW and WAW dependences.
   // 4) Add the privatization dependences which are widened versions of
   //    already present dependences. They model the effect of manual
   //    privatization at the outermost possible place (namely after the last
   //    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())
         continue;
       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({
     dbgs() << "Final Wrapped Dependences:\n";
     printScop(dbgs(), S);
     dbgs() << "\n";
   });
 
   // RED_SIN is used to collect all reduction dependences again after we
   // 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
   // (wrapped space!). If so these dependences are caused by this memory access.
   // We then move this portion of reduction dependences back to the statement ->
   // statement space and add a mapping from the memory access to these
   // dependences.
   for (ScopStmt *Stmt : S) {
     for (MemoryAccess *MA : *Stmt) {
       if (!MA->isReductionLike())
         continue;
 
       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;
 
       isl_map *AccRedDep = isl_map_from_union_map(AccRedDepU);
       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";
     printScop(dbgs(), S);
     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";
     printScop(dbgs(), S);
     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);
-
-  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_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);
+
+  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);
 
   isl_space *ScatteringSpace = nullptr;
 
   for (ScopStmt *Stmt : S) {
     isl_map *StmtScat;
 

 // Parallelism test: if the distance is zero in all outer dimensions, then it
 // has to be zero in the current dimension as well.
 //
 // Implementation: first, translate dependences into time space, then force
 // outer dimensions to be equal. If the distance is zero in the current
 // 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,
+bool DependenceInfo::isParallel(isl_union_map *Schedule, isl_union_map *Deps,
                                 isl_pw_aff **MinDistancePtr) {
   isl_set *Deltas, *Distance;
   isl_map *ScheduleDeps;
   unsigned Dimension;
   bool IsParallel;
 
   Deps = isl_union_map_apply_range(Deps, isl_union_map_copy(Schedule));
   Deps = isl_union_map_apply_domain(Deps, isl_union_map_copy(Schedule));
 

 
 static void printDependencyMap(raw_ostream &OS, __isl_keep isl_union_map *DM) {
   if (DM)
     OS << DM << "\n";
   else
     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)

lib/Analysis/ScopInfo.cpp

 
 ScopStmt *Scop::getStmtForBasicBlock(BasicBlock *BB) const {
   const auto &StmtMapIt = StmtMap.find(BB);
   if (StmtMapIt == StmtMap.end())
     return nullptr;
   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>();
   AU.addRequired<AliasAnalysis>();
   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);
+
+    Scop *S = new Scop(*tempScop, LI, SE, SD, Ctx);
+
+    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");
 
-  if (!PollyUseRuntimeAliasChecks) {
-    // Statistics.
-    ++ScopFound;
-    if (scop->getMaxLoopDepth() > 0)
-      ++RichScopFound;
-    return false;
+      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.
-  if (scop->buildAliasGroups(AA)) {
     // 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");
+void ScopInfo::print(raw_ostream &OS, const Module *) const {
+  for (const Scop *S : *this)
+    S->print(OS);
+}
 
-  delete scop;
-  scop = nullptr;
-  return false;
+void ScopInfo::releaseMemory() {
+  for (Scop *S : Scops)
+    delete S;
+  Scops.clear();
 }
 
 char ScopInfo::ID = 0;
 
 Pass *polly::createScopInfoPass() { return new ScopInfo(); }
 
 INITIALIZE_PASS_BEGIN(ScopInfo, "polly-scops",
                       "Polly - Create polyhedral description of Scops", false,

lib/Analysis/ScopPass.cpp

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

lib/CMakeLists.txt

set (ISL_FILES
     External/isl/imath/imrat.c
     External/isl/imath/iprime.c
     External/isl/imath/pi.c
     External/isl/imath/rsamath.c
     )
 
 
 add_polly_library(Polly
-  Analysis/Dependences.cpp
+  Analysis/DependenceInfo.cpp
   Analysis/ScopDetection.cpp
   Analysis/ScopDetectionDiagnostic.cpp
   Analysis/ScopInfo.cpp
   Analysis/ScopGraphPrinter.cpp
   Analysis/ScopPass.cpp
   Analysis/TempScopInfo.cpp
   CodeGen/BlockGenerators.cpp
   ${ISL_CODEGEN_FILES}

lib/CodeGen/IslAst.cpp

 // for (c2 = max(0, ceild(n + m, 2); c2 <= min(511, floord(5 * n, 3)); c2++) {
 //   bb2(c2);
 // }
 //
 //===----------------------------------------------------------------------===//
 
 #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"
 #include "polly/Support/GICHelper.h"
 
 #include "llvm/Analysis/RegionInfo.h"
 #include "llvm/Support/Debug.h"
 

 static cl::opt<bool> NoEarlyExit(
     "polly-no-early-exit",
     cl::desc("Do not exit early if no benefit of the Polly version was found."),
     cl::Hidden, cl::init(false), cl::ZeroOrMore, cl::cat(PollyCategory));
 
 namespace polly {
 class IslAst {
 public:
-  IslAst(Scop *Scop, Dependences &D);
+  IslAst(Scop &S, DependenceInfo &D);
 
   ~IslAst();
 
   /// Print a source code representation of the program.
   void pprint(llvm::raw_ostream &OS);
 
   __isl_give isl_ast_node *getAst();
 
   /// @brief Get the run-time conditions for the Scop.
   __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.
 
 /// @brief Free an IslAstUserPayload object pointed to by @p Ptr
 static void freeIslAstUserPayload(void *Ptr) {
   delete ((IslAstInfo::IslAstUserPayload *)Ptr);
 }
 
 IslAstInfo::IslAstUserPayload::~IslAstUserPayload() {
   isl_ast_build_free(Build);
   isl_pw_aff_free(MinimalDependenceDistance);
 }
 
 /// @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;
 
   /// @brief The last iterator id created for the current SCoP.
   isl_id *LastForNodeId;
 };
 
static isl_printer *cbPrintFor(__isl_take isl_printer *Printer,
 
   isl_pw_aff_free(DD);
   return isl_ast_node_for_print(Node, Printer, Options);
 }
 
 /// @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;
 
   if (!NodeInfo->IsReductionParallel && !isl_union_map_free(Schedule))
     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));
     if (!D->isParallel(Schedule, RedDeps))
       NodeInfo->BrokenReductions.insert(MaRedPair.first);
   }
 
   isl_union_map_free(Schedule);
static __isl_give isl_id *astBuildBeforeFor(__isl_keep isl_ast_build *Build,
   IslAstUserPayload *Payload = new IslAstUserPayload();
   isl_id *Id = isl_id_alloc(isl_ast_build_get_ctx(Build), "", Payload);
   Id = isl_id_set_free_user(Id, freeIslAstUserPayload);
   BuildInfo->LastForNodeId = Id;
 
   // 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;
 }
 
 // This method is executed after the construction of a for node.
 //
 // It performs the following actions:
 //
astBuildAfterFor(__isl_take isl_ast_node *Node, __isl_keep isl_ast_build *Build,
   // Innermost loops that are surrounded by parallel loops have not yet been
   // tested for parallelism. Test them here to ensure we check all innermost
   // loops for parallelism.
   if (Payload->IsInnermost && BuildInfo->InParallelFor) {
     if (Payload->IsOutermostParallel)
       Payload->IsInnermostParallel = true;
     else
       Payload->IsInnermostParallel =
-          astScheduleDimIsParallel(Build, BuildInfo->Deps, Payload);
+          astScheduleDimIsParallel(Build, BuildInfo->S, BuildInfo->D, Payload);
   }
   if (Payload->IsOutermostParallel)
     BuildInfo->InParallelFor = false;
 
   isl_id_free(Id);
   return Node;
 }
 
 static __isl_give isl_ast_node *AtEachDomain(__isl_take isl_ast_node *Node,
                                              __isl_keep isl_ast_build *Build,
                                              void *User) {
   assert(!isl_ast_node_get_annotation(Node) && "Node already annotated");
 
   IslAstUserPayload *Payload = new IslAstUserPayload();
   isl_id *Id = isl_id_alloc(isl_ast_build_get_ctx(Build), "", Payload);
   Id = isl_id_set_free_user(Id, freeIslAstUserPayload);
 
   Payload->Build = isl_ast_build_copy(Build);
 
   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) {
         MinExpr =
             isl_ast_expr_address_of(isl_ast_build_access_from_pw_multi_aff(
                 Build, isl_pw_multi_aff_copy(AccIt0->first)));
         MaxExpr =
             isl_ast_expr_address_of(isl_ast_build_access_from_pw_multi_aff(

 
 /// @brief Simple cost analysis for a given SCoP
 ///
 /// TODO: Improve this analysis and extract it to make it usable in other
 ///       places too.
 ///       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,
                                               &BuildInfo);
     Build =
         isl_ast_build_set_after_each_for(Build, &astBuildAfterFor, &BuildInfo);
   }
 
-  buildRunCondition(Build);
+  buildRunCondition(Build, S);
 
   Root = isl_ast_build_ast_from_schedule(Build, Schedule);
 
   isl_ast_build_free(Build);
 }
 
 IslAst::~IslAst() {
   isl_ast_node_free(Root);
   isl_ast_expr_free(RunCondition);
 }
 
 __isl_give isl_ast_node *IslAst::getAst() { return isl_ast_node_copy(Root); }
 __isl_give isl_ast_expr *IslAst::getRunCondition() {
   return isl_ast_expr_copy(RunCondition);
 }
 
 void IslAstInfo::releaseMemory() {
-  if (Ast) {
-    delete Ast;
-    Ast = nullptr;
-  }
+  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) {
   isl_id *Id = isl_ast_node_get_annotation(Node);
   if (!Id)
     return nullptr;
   IslAstUserPayload *Payload = (IslAstUserPayload *)isl_id_get_user(Id);
   isl_id_free(Id);

 
 isl_ast_build *IslAstInfo::getBuild(__isl_keep isl_ast_node *Node) {
   IslAstUserPayload *Payload = getNodePayload(Node);
   return Payload ? Payload->Build : nullptr;
 }
 
 void IslAstInfo::printScop(raw_ostream &OS, Scop &S) const {
   isl_ast_print_options *Options;
-  isl_ast_node *RootNode = getAst();
+  isl_ast_node *RootNode = getAst(S);
   Function *F = S.getRegion().getEntry()->getParent();
 
   OS << ":: isl ast :: " << F->getName() << " :: " << S.getRegion().getNameStr()
      << "\n";
 
   if (!RootNode) {
     OS << ":: isl ast generation and code generation was skipped!\n\n";
     return;
   }
 
-  isl_ast_expr *RunCondition = getRunCondition();
+  isl_ast_expr *RunCondition = getRunCondition(S);
   char *RtCStr, *AstStr;
 
   Options = isl_ast_print_options_alloc(S.getIslCtx());
   Options = isl_ast_print_options_set_print_for(Options, cbPrintFor, nullptr);
 
   isl_printer *P = isl_printer_to_str(S.getIslCtx());
   P = isl_printer_print_ast_expr(P, RunCondition);
   RtCStr = isl_printer_get_str(P);
void IslAstInfo::printScop(raw_ostream &OS, Scop &S) const {
   isl_ast_node_free(RootNode);
   isl_printer_free(P);
 }
 
 void IslAstInfo::getAnalysisUsage(AnalysisUsage &AU) const {
   // Get the Common analysis usage of ScopPasses.
   ScopPass::getAnalysisUsage(AU);
   AU.addRequired<ScopInfo>();
-  AU.addRequired<Dependences>();
+  AU.addRequired<DependenceInfo>();
 }
 
 char IslAstInfo::ID = 0;
 
 Pass *polly::createIslAstInfoPass() { return new IslAstInfo(); }
 
 INITIALIZE_PASS_BEGIN(IslAstInfo, "polly-ast",
                       "Polly - Generate an AST of the SCoP (isl)", false,
                       false);
 INITIALIZE_PASS_DEPENDENCY(ScopInfo);
-INITIALIZE_PASS_DEPENDENCY(Dependences);
+INITIALIZE_PASS_DEPENDENCY(DependenceInfo);
 INITIALIZE_PASS_END(IslAstInfo, "polly-ast",
                     "Polly - Generate an AST from the SCoP (isl)", false, false)

lib/CodeGen/IslCodeGeneration.cpp

 //===----------------------------------------------------------------------===//
 #include "polly/Config/config.h"
 #include "polly/CodeGen/IslExprBuilder.h"
 #include "polly/CodeGen/BlockGenerators.h"
 #include "polly/CodeGen/CodeGeneration.h"
 #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"
 #include "polly/Support/ScopHelper.h"
 #include "polly/Support/SCEVValidator.h"
 #include "polly/TempScopInfo.h"
 
 #include "llvm/ADT/PostOrderIterator.h"
public:
   ScopAnnotator Annotator;
 
   /// @brief Build the runtime condition.
   ///
   /// Build the condition that evaluates at run-time to true iff all
   /// assumptions taken for the SCoP hold, and to false otherwise.
   ///
   /// @return A value evaluating to true/false if execution is save/unsafe.
-  Value *buildRTC(PollyIRBuilder &Builder, IslExprBuilder &ExprBuilder) {
+  Value *buildRTC(Scop &S, PollyIRBuilder &Builder,
+                  IslExprBuilder &ExprBuilder) {
     Builder.SetInsertPoint(Builder.GetInsertBlock()->getTerminator());
-    Value *RTC = ExprBuilder.create(AI->getRunCondition());
+    Value *RTC = ExprBuilder.create(AI->getRunCondition(S));
     if (!RTC->getType()->isIntegerTy(1))
       RTC = Builder.CreateIsNotNull(RTC);
     return RTC;
   }
 
   bool verifyGeneratedFunction(Scop &S, Function &F) {
     if (!verifyFunction(F))
       return false;
 
     DEBUG({
       errs() << "== ISL Codegen created an invalid function ==\n\n== The "
                 "SCoP ==\n";
       S.print(errs());
       errs() << "\n== The isl AST ==\n";
       AI->printScop(errs(), S);
       errs() << "\n== The invalid function ==\n";
       F.print(errs());
       errs() << "\n== The errors ==\n";
       verifyFunction(F, &errs());
     });
 
     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");
 
     // Build the alias scopes for annotations first.
     if (PollyAnnotateAliasScopes)
       Annotator.buildAliasScopes(S);
 
     BasicBlock *EnteringBB = simplifyRegion(&S, this);
     PollyIRBuilder Builder = createPollyIRBuilder(EnteringBB, Annotator);
 
     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());
 
     NodeBuilder.create(AstRoot);
 
     assert(!verifyGeneratedFunction(S, *EnteringBB->getParent()) &&
            "Verification of generated function failed");
     return true;
   }
 
   void printScop(raw_ostream &, Scop &) const override {}
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.addRequired<DataLayoutPass>();
     AU.addRequired<DominatorTreeWrapperPass>();
     AU.addRequired<IslAstInfo>();
     AU.addRequired<RegionInfoPass>();
     AU.addRequired<ScalarEvolution>();
     AU.addRequired<ScopDetection>();
     AU.addRequired<ScopInfo>();
     AU.addRequired<LoopInfoWrapperPass>();
 
-    AU.addPreserved<Dependences>();
+    AU.addPreserved<DependenceInfo>();
 
     AU.addPreserved<LoopInfoWrapperPass>();
     AU.addPreserved<DominatorTreeWrapperPass>();
     AU.addPreserved<IslAstInfo>();
     AU.addPreserved<ScopDetection>();
     AU.addPreserved<ScalarEvolution>();
 
     // FIXME: We do not yet add regions for the newly generated code to the
     //        region tree.
     AU.addPreserved<RegionInfoPass>();
     AU.addPreserved<TempScopInfo>();
     AU.addPreserved<ScopInfo>();
     AU.addPreservedID(IndependentBlocksID);
   }
 };
 }
 
 char IslCodeGeneration::ID = 1;
 
 Pass *polly::createIslCodeGenerationPass() { return new IslCodeGeneration(); }
 
 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);
 INITIALIZE_PASS_DEPENDENCY(ScalarEvolution);
 INITIALIZE_PASS_DEPENDENCY(ScopDetection);
 INITIALIZE_PASS_END(IslCodeGeneration, "polly-codegen-isl",
                     "Polly - Create LLVM-IR from SCoPs", false, false)

lib/Exchange/JSONExporter.cpp

 //===-- JSONExporter.cpp  - Export Scops as JSON  -------------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // Export the Scops build by ScopInfo pass as a JSON file.
 //
 //===----------------------------------------------------------------------===//
 
 #include "polly/LinkAllPasses.h"
-#include "polly/Dependences.h"
+#include "polly/DependenceInfo.h"
 #include "polly/Options.h"
 #include "polly/ScopInfo.h"
 #include "polly/ScopPass.h"
 
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/RegionInfo.h"
 #include "llvm/Support/FileSystem.h"
 #include "llvm/Support/MemoryBuffer.h"
ImportPostfix("polly-import-jscop-postfix",
                   cl::init(""), cl::cat(PollyCategory));
 
 struct JSONExporter : public ScopPass {
   static char ID;
   explicit JSONExporter() : ScopPass(ID) {}
 
   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 {
   static char ID;
   std::vector<std::string> newAccessStrings;
   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 {}
 };
 }
 
 char JSONExporter::ID = 0;
 std::string JSONExporter::getFileName(Scop &S) const {
   std::string FunctionName = S.getRegion().getEntry()->getParent()->getName();
   std::string FileName = FunctionName + "___" + S.getNameStr() + ".jscop";
   return FileName;

 void JSONImporter::printScop(raw_ostream &OS, Scop &S) const {
   S.print(OS);
   for (std::vector<std::string>::const_iterator I = newAccessStrings.begin(),
                                                 E = newAccessStrings.end();
        I != E; I++)
     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);
 
   std::string FunctionName = R.getEntry()->getParent()->getName();
   errs() << "Reading JScop '" << R.getNameStr() << "' in function '"
          << FunctionName << "' from '" << FileName << "'.\n";
   ErrorOr<std::unique_ptr<MemoryBuffer>> result =
for (Scop::iterator SI = S.begin(), SE = S.end(); SI != SE; ++SI) {
     // that stores the reference to the ScopStmt this scattering belongs to.
     m = isl_map_set_tuple_id(m, isl_dim_in,
                              isl_space_get_tuple_id(Space, isl_dim_set));
     isl_space_free(Space);
     NewScattering[*SI] = m;
     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)
       isl_map_free(SI->second);
     return false;
   }
 
   for (Scop::iterator SI = S.begin(), SE = S.end(); SI != SE; ++SI) {
for (Scop::iterator SI = S.begin(), SE = S.end(); SI != SE; ++SI) {
     statementIdx++;
   }
 
   return false;
 }
 
 void JSONImporter::getAnalysisUsage(AnalysisUsage &AU) const {
   ScopPass::getAnalysisUsage(AU);
-  AU.addRequired<Dependences>();
+  AU.addRequired<DependenceInfo>();
   AU.addRequired<DataLayoutPass>();
 }
 Pass *polly::createJSONImporterPass() { return new JSONImporter(); }
 
 INITIALIZE_PASS_BEGIN(JSONExporter, "polly-export-jscop",
                       "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)",
                     false, false)
 
 INITIALIZE_PASS_BEGIN(JSONImporter, "polly-import-jscop",
                       "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"
                     " (Reads a .jscop file for each Scop)",
                     false, false)

lib/Makefile

External/isl/isl_schedule_tree.c \
            External/isl/imath/pi.c \
            External/isl/imath/rsamath.c
 
 SOURCES= Polly.cpp \
    Support/GICHelper.cpp \
    Support/SCEVValidator.cpp \
    Support/RegisterPasses.cpp \
    Support/ScopHelper.cpp \
-   Analysis/Dependences.cpp \
+   Analysis/DependenceInfo.cpp \
    Analysis/ScopDetection.cpp \
    Analysis/ScopDetectionDiagnostic.cpp \
    Analysis/ScopInfo.cpp \
    Analysis/ScopGraphPrinter.cpp \
    Analysis/ScopPass.cpp \
    Analysis/TempScopInfo.cpp \
    CodeGen/BlockGenerators.cpp \
    CodeGen/LoopGenerators.cpp \

lib/Support/RegisterPasses.cpp

 // passes are registered such that the default behaviour of the compiler is not
 // changed, but that the flag '-polly' provided at optimization level '-O3'
 // enables additional polyhedral optimizations.
 //===----------------------------------------------------------------------===//
 
 #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"
 #include "polly/ScopInfo.h"
 #include "polly/TempScopInfo.h"
 #include "llvm/Analysis/CFGPrinter.h"
 #include "llvm/IR/LegacyPassManager.h"
 #include "llvm/Transforms/IPO/PassManagerBuilder.h"
static cl::opt<bool, true> XPollyAnnotateAliasScopes(
     cl::location(PollyAnnotateAliasScopes), cl::init(true), cl::ZeroOrMore,
     cl::cat(PollyCategory));
 
 namespace polly {
 void initializePollyPasses(PassRegistry &Registry) {
   initializeIslCodeGenerationPass(Registry);
   initializeCodePreparationPass(Registry);
   initializeDeadCodeElimPass(Registry);
-  initializeDependencesPass(Registry);
+  initializeDependenceInfoPass(Registry);
   initializeIndependentBlocksPass(Registry);
   initializeJSONExporterPass(Registry);
   initializeJSONImporterPass(Registry);
   initializeIslAstInfoPass(Registry);
   initializeIslScheduleOptimizerPass(Registry);
   initializePollyCanonicalizePass(Registry);
   initializeScopDetectionPass(Registry);
   initializeScopInfoPass(Registry);

lib/Transform/DeadCodeElimination.cpp

 //    for (i = 0; i < N; i++)
 //        arr[i] = i;
 //
 // The idea and the algorithm used was first implemented by Sven Verdoolaege in
 // the 'ppcg' tool.
 //
 //===----------------------------------------------------------------------===//
 
-#include "polly/Dependences.h"
+#include "polly/DependenceInfo.h"
 #include "polly/LinkAllPasses.h"
 #include "polly/ScopInfo.h"
 #include "llvm/Support/CommandLine.h"
 #include "isl/flow.h"
 #include "isl/set.h"
 #include "isl/map.h"
 #include "isl/union_map.h"
 

 
 class DeadCodeElim : public ScopPass {
 public:
   static char ID;
   explicit DeadCodeElim() : ScopPass(ID) {}
 
   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
   /// which we can not prove that there will be a later write that _must_
   /// overwrite the same memory location and is consequently the only one that
   /// is visible after the execution of the SCoP.
   ///
   isl_union_set *getLiveOut(Scop &S);

 /// o Assuming that the last write to each location is live.
 /// o Following each RAW dependency from a live iteration backwards and adding
 ///   that iteration to the live set.
 ///
 /// To ensure the set of live iterations does not get too complex we always
 /// combine a certain number of precise steps with one approximating step that
 /// simplifies the life set with an affine hull.
 bool DeadCodeElim::eliminateDeadCode(Scop &S, int PreciseSteps) {
-  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)
     Live = isl_union_set_affine_hull(Live);
 
   isl_union_set *OriginalDomain = S.getDomains();
   int Steps = 0;
   while (true) {
while (true) {
 
     Live = isl_union_set_intersect(Live, isl_union_set_copy(OriginalDomain));
   }
   isl_union_map_free(Dep);
   isl_union_set_free(OriginalDomain);
 
   bool Changed = S.restrictDomains(isl_union_set_coalesce(Live));
 
-  // FIXME: We can probably avoid the recomputation of all dependences by
+  // FIXME: We can probably avoid the recomputation of all DependenceInfo by
   // updating them explicitly.
   if (Changed)
-    D->recomputeDependences();
+    DI->recomputeDependences(S);
   return Changed;
 }
 
+void DeadCodeElim::initializeScopPass() { DI = &getAnalysis<DependenceInfo>(); }
+
 bool DeadCodeElim::runOnScop(Scop &S) {
   return eliminateDeadCode(S, DCEPreciseSteps);
 }
 
 void DeadCodeElim::printScop(raw_ostream &, Scop &) const {}
 
 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)

lib/Transform/ScheduleOptimizer.cpp

 #include "isl/aff.h"
 #include "isl/band.h"
 #include "isl/constraint.h"
 #include "isl/map.h"
 #include "isl/options.h"
 #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"
 #include "polly/Support/GICHelper.h"
 #include "llvm/Support/Debug.h"
 
 using namespace llvm;
 using namespace polly;
 
 #define DEBUG_TYPE "polly-opt-isl"
 
 namespace polly {
 bool DisablePollyTiling;
 }
 static cl::opt<bool, true>
     DisableTiling("polly-no-tiling",
                   cl::desc("Disable tiling in the scheduler"),
                   cl::location(polly::DisablePollyTiling), cl::init(false),
                   cl::ZeroOrMore, cl::cat(PollyCategory));
 
 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));
 
 static cl::opt<int> MaxConstantTerm(
     "polly-opt-max-constant-term",
     cl::desc("The maximal constant term allowed (-1 is unlimited)"), cl::Hidden,
     cl::init(20), cl::ZeroOrMore, cl::cat(PollyCategory));
 

 
 class IslScheduleOptimizer : public ScopPass {
 public:
   static char ID;
   explicit IslScheduleOptimizer() : ScopPass(ID) { LastSchedule = nullptr; }
 
   ~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.
   ///
   /// @param S           The SCoP we optimize.
   /// @param NewSchedule The new schedule we computed.
   ///
   /// @return True, if we believe @p NewSchedule is an improvement for @p S.
private:
   /// individual bands to the overall schedule. In case tiling is requested,
   /// the individual bands are tiled.
   static isl_union_map *getScheduleForBandList(isl_band_list *BandList);
 
   static isl_union_map *getScheduleMap(isl_schedule *Schedule);
 
   using llvm::Pass::doFinalization;
 
-  virtual bool doFinalization() override {
+  virtual bool doFinalization(Module &) override {
     isl_schedule_free(LastSchedule);
     LastSchedule = nullptr;
     return true;
   }
 };
 }
 
 char IslScheduleOptimizer::ID = 0;
bool IslScheduleOptimizer::isProfitableSchedule(
   // before/after the scheduling optimizer
   // (e.g., #stride-one accesses)
   isl_union_map *OldSchedule = S.getSchedule();
   bool changed = !isl_union_map_is_equal(OldSchedule, NewSchedule);
   isl_union_map_free(OldSchedule);
   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
   // loops present but not needed.
   if (S.getSize() == 0) {
     S.markAsOptimized();
     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();
 
   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.
   if (SimplifyDeps == "yes") {
     Validity = isl_union_map_gist_domain(Validity, isl_union_set_copy(Domain));
     Validity = isl_union_map_gist_range(Validity, isl_union_set_copy(Domain));
     Proximity =
         isl_union_map_gist_domain(Proximity, isl_union_set_copy(Domain));
void IslScheduleOptimizer::printScop(raw_ostream &OS, Scop &) const {
   ScheduleStr = isl_printer_get_str(p);
   isl_printer_free(p);
 
   OS << ScheduleStr << "\n";
 }
 
 void IslScheduleOptimizer::getAnalysisUsage(AnalysisUsage &AU) const {
   ScopPass::getAnalysisUsage(AU);
-  AU.addRequired<Dependences>();
+  AU.addRequired<DependenceInfo>();
 }
 
 Pass *polly::createIslScheduleOptimizerPass() {
   return new IslScheduleOptimizer();
 }
 
 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)

test/DependenceInfo/computeout.ll

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

test/DependenceInfo/do_pluto_matmult.ll

 ; 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 }

test/DependenceInfo/reduction_complex_location.ll

 ; 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
 }

test/DependenceInfo/reduction_dependences_equal_non_reduction_dependences.ll

 ; 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
 }

test/DependenceInfo/reduction_mixed_reduction_and_non_reduction_dependences.ll

 ; 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
 }

test/DependenceInfo/reduction_multiple_loops_array_sum.ll

 ; 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
 }

test/DependenceInfo/reduction_multiple_loops_array_sum_2.ll

 ; 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
 }

test/DependenceInfo/reduction_multiple_loops_array_sum_3.ll

 ; 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
 }

test/DependenceInfo/reduction_multiple_reductions.ll

 ; 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
 }

test/DependenceInfo/reduction_multiple_reductions_2.ll

 ; 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
 }

test/DependenceInfo/reduction_only_reduction_like_access.ll

 ; 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
 }

test/DependenceInfo/reduction_partially_escaping_intermediate_in_other_stmt.ll

 ; 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
 }

test/DependenceInfo/reduction_privatization_deps.ll

 ; 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
 }

test/DependenceInfo/reduction_privatization_deps_2.ll

 ; 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
 }

test/DependenceInfo/reduction_privatization_deps_3.ll

 ; 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
 }

test/DependenceInfo/reduction_privatization_deps_4.ll

 ; 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
 }

test/DependenceInfo/reduction_privatization_deps_5.ll

 ; 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
 }

test/DependenceInfo/reduction_simple_iv.ll

 ; 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
 }

test/DependenceInfo/reduction_simple_iv_debug_wrapped_dependences.ll

 ; 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
 }

test/DependenceInfo/reduction_simple_privatization_deps_2.ll

 ; 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
 }

test/DependenceInfo/reduction_simple_privatization_deps_w_parameter.ll

 ; 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
 }

test/DependenceInfo/reduction_two_reductions_different_rloops.ll

 ; 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
 }

test/DependenceInfo/sequential_loops.ll

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

test/Isl/CodeGen/MemAccess/simple_analyze.ll

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

test/Isl/CodeGen/simple_loop_non_single_exit.ll

-; 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) {
 ;   long i;
 ;   if (true)
 ;     for (i = 0; i < N; ++i)
 ;       A[i] = i;
 ; }
for.i:
   %exitcond = icmp eq i64 %indvar.next, %N
   br i1 %exitcond, label %return, label %for.i
 
 return:
   fence seq_cst
   ret void
 }
 
-; CHECK: Create LLVM-IR from SCoPs' for region: 'next => polly.merge_new_and_old'
+; CHECK: :: isl ast :: f :: next => return
 ; CHECK-CODE: polly.split_new_and_old
 ; CHECK-CODE: polly.merge_new_and_old

test/Isl/CodeGen/simple_loop_non_single_exit_2.ll

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

test/Isl/CodeGen/simple_non_single_entry.ll

-; RUN: opt %loadPolly -polly-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) {
 ;   long i;
 ;
 ;  if (true){
 ;    i = 0;
 ;    goto next;
for.i:
   %exitcond = icmp eq i64 %indvar.next, %N
   br i1 %exitcond, label %return, label %for.i
 
 return:
   fence seq_cst
   ret void
 }
 
-; CHECK: Create LLVM-IR from SCoPs' for region: 'next.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

test/Isl/CodeGen/single_loop_zero_iterations.ll

 if.else:                                          ; preds = %for.end
   br label %return
 
 return:                                           ; preds = %if.else, %if.then
   %retval.0 = phi i32 [ 0, %if.then ], [ 1, %if.else ] ; <i32> [#uses=1]
   ret i32 %retval.0
 }
 
-; 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);

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

 ; RUN: opt %loadPolly -polly-detect-unprofitable -polly-no-early-exit -polly-ast -analyze -polly-ignore-aliasing < %s | FileCheck %s 
 ; RUN: opt %loadPolly -polly-detect-unprofitable -polly-no-early-exit -polly-codegen-isl -polly-ignore-aliasing < %s
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 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);
 ; CHECK:       if (Scalar0.val.loadoutside >= 100)
 ; CHECK:         Stmt_for_1(0);
 ; CHECK:     }
 
-; CHECK: if (1)
-; CHECK:     Stmt_for_0(0);
-
 
 define void @foo(i32* %A) {
 entry:
   %Scalar0 = alloca i32
   br label %for.0
 
 for.0:
   %Scalar0.val = load i32, i32* %Scalar0

test/ScopInfo/aliasing_many_parameters_not_all_involved.ll

 ; RUN: opt %loadPolly -polly-detect-unprofitable -polly-scops -polly-code-generator=isl -polly-rtc-max-parameters=8 -analyze < %s | FileCheck %s --check-prefix=MAX8
 ; RUN: opt %loadPolly -polly-detect-unprofitable -polly-scops -polly-code-generator=isl -polly-rtc-max-parameters=7 -analyze < %s | FileCheck %s --check-prefix=MAX7
 ;
 ; Check that we allow this SCoP even though it has 10 parameters involved in posisbly aliasing accesses.
 ; However, only 7 are involved in accesses through B, 8 through C and none in accesses through A.
 ;
-; MAX8:       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) {
 ;      for (int i = 0; i < 1024; i++)
 ;        A[i] = B[p1] - B[p2] + B[-p3] - B[p4] + B[p5] - B[-p6] + B[p7] - C[p3] +
 ;               C[-p4] - C[p5] + C[p6] - C[-p7] + C[p8] - C[p9] + C[-p10];
 ;    }
 ;

test/ScopInfo/integers.ll

entry:
   br label %bb
 
 bb:
   %indvar = phi i1024 [ 0, %entry ], [ %indvar.next, %bb ]
   %scevgep = getelementptr i1024, i1024* %a, i1024 %indvar
   store i1024 %indvar, i1024* %scevgep, align 8
   %indvar.next = add nsw i1024 %indvar, 1
   %exitcond = icmp eq i1024 %indvar, 123456000000000000000000000
-; CHECK:  'bb => return' in function 'f'
+; CHECK: Function: f
+; CHECK: Region: %bb---%return
 ; CHECK: i0 <= 123456000000000000000000000
   br i1 %exitcond, label %return, label %bb
 
 return:
   ret void
 }
 
 ; Normal positive integer
 define void @f2(i32* nocapture %a) nounwind {
 entry:
   br label %bb
 
 bb:
   %indvar = phi i32 [ 0, %entry ], [ %indvar.next, %bb ]
   %scevgep = getelementptr i32, i32* %a, i32 %indvar
   store i32 %indvar, i32* %scevgep, align 8
   %indvar.next = add nsw i32 %indvar, 1
   %exitcond = icmp eq i32 %indvar, 123456
-; CHECK:  'bb => return' in function 'f2'
+; CHECK: Function: f2
+; CHECK: Region: %bb---%return
 ; CHECK: i0 <= 123456
   br i1 %exitcond, label %return, label %bb
 
 return:
   ret void
 }
 
 ; Normal negative integer
 define void @f3(i32* nocapture %a, i32 %n) nounwind {
 entry:
   br label %bb
 
 bb:
   %indvar = phi i32 [ 0, %entry ], [ %indvar.next, %bb ]
   %scevgep = getelementptr i32, i32* %a, i32 %indvar
   store i32 %indvar, i32* %scevgep, align 8
   %indvar.next = add nsw i32 %indvar, 1
   %sub = sub i32 %n, 123456
   %exitcond = icmp eq i32 %indvar, %sub
-; CHECK:  'bb => return' in function 'f3'
+; CHECK: Function: f3
+; CHECK: Region: %bb---%return
 ; CHECK: -123456
   br i1 %exitcond, label %return, label %bb
 
 return:
   ret void
 }
 
 ; Large negative integer
 define void @f4(i1024* nocapture %a, i1024 %n) nounwind {
 entry:
   br label %bb
 
 bb:
   %indvar = phi i1024 [ 0, %entry ], [ %indvar.next, %bb ]
   %scevgep = getelementptr i1024, i1024* %a, i1024 %indvar
   store i1024 %indvar, i1024* %scevgep, align 8
   %indvar.next = add nsw i1024 %indvar, 1
   %sub = sub i1024 %n, 123456000000000000000000000000000000
-; CHECK:  'bb => return' in function 'f4'
+; CHECK: Function: f4
+; CHECK: Region: %bb---%return
 ; CHECK: -123456000000000000000000000000000000
   %exitcond = icmp eq i1024 %indvar, %sub
   br i1 %exitcond, label %return, label %bb
 
 return:
   ret void
 }
 
 define void @f5(i1023* nocapture %a, i1023 %n) nounwind {
 entry:
   br label %bb
 
 bb:
   %indvar = phi i1023 [ 0, %entry ], [ %indvar.next, %bb ]
   %scevgep = getelementptr i1023, i1023* %a, i1023 %indvar
   store i1023 %indvar, i1023* %scevgep, align 8
   %indvar.next = add nsw i1023 %indvar, 1
   %sub = sub i1023 %n, 123456000000000000000000000000000000
-; CHECK:  'bb => return' in function 'f5'
+; CHECK: Function: f5
+; CHECK: Region: %bb---%return
 ; CHECK: -123456000000000000000000000000000000
   %exitcond = icmp eq i1023 %indvar, %sub
   br i1 %exitcond, label %return, label %bb
 
 return:
   ret void
 }
 
 ; Tiny negative integer
 define void @f6(i3* nocapture %a, i3 %n) nounwind {
 entry:
   br label %bb
 
 bb:
   %indvar = phi i3 [ 0, %entry ], [ %indvar.next, %bb ]
   %scevgep = getelementptr i3, i3* %a, i3 %indvar
   store i3 %indvar, i3* %scevgep, align 8
   %indvar.next = add nsw i3 %indvar, 1
   %sub = sub i3 %n, 3
-; CHECK:  'bb => return' in function 'f6'
+; CHECK: Function: f6
+; CHECK: Region: %bb---%return
 ; CHECK: -3
   %exitcond = icmp eq i3 %indvar, %sub
   br i1 %exitcond, label %return, label %bb
 
 return:
   ret void
 }

test/ScopInfo/undef_in_cond.ll

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