[RFC] Move to schedule trees to store our schedule

[grosser]

Summary

Instead of modeling the schedule (execution order) of a piece of code as a flat
multi-dimensional mapping, we now retain the inherent tree structure of the
schedule. This makes the schedule a little bit more verbose, but the exposed
structure makes it both easier to work with and also faster to process.

Specifically, we can now easily walk the schedule tree to decide where to tile
loops, apply register tiling at the inner level and also perform full/partial
tile separation a lot easier.

This patch does not yet exploit these capabilities, but is mostly a 1-to-1
translation from flat schedules to schedule trees.

For more information see:

impact.gforge.inria.fr/impact2014/papers/impact2014-verdoolaege.pdf

XXX: This patch is not yet finished, but just a proof of concept.

Open Issues

• The dependence analysis for reductions does not yet work. Specifically, this patch does not yet support the computation of reduction dependences. The current approach uses flat schedules extensively. It might make sense to first change the way we model reductions (as may-writes as suggested by Sven) and only then add this patch.

Performance measurements

  0           1         2                 3
Before      Patch   Patch+64bit-int    NoPolly

gemm: 121ms 92ms 74ms 46ms
3mm: 600ms 340ms 203ms 60ms
NAS Parallel Benchmark (bt): 6m+ 1.2s 627ms 80ms

The performance compares

0) Polly trunk
1) Polly + this patch
2) Polly + this patch + 64bit integers
3) clang -O3 without Polly

The NAS benchmark seems to still have a performance problem. Adding/deriving
run-time assumptions seems to take a significant amount of time, making ScopInfo
with about 75% the most costly pass, whereas it commonly does not show up high
on the profile.

Example

Source Code

for (long i = 0; i < 100; i++) {

S1: A[i] += 1;

for (long j = 0; j < 100; j++)

S2: A[i+j] += 1;
S3: A[i] += 1;

}

Flat Schedule

{

Stmt_S1[i0]     -> [i0, 0, 0]: i0 >= 0 and i0 <= 99;
Stmt_S2[i0, i1] -> [i0, 1, i1]: i0 >= 0 and i0 <= 99 and i1 >= 0 and i1 <= 99
Stmt_S3[i0]     -> [i0, 2, 0]: i0 >= 0 and i0 <= 99

}

Schedule Tree

domain: "{ Stmt_S1[i0] : i0 >= 0 and i0 <= 99;

Stmt_S2[i0, i1] : i0 >= 0 and i0 <= 99 and i1 >= 0 and i1 <= 99;
Stmt_S3[i0] : i0 >= 0 and i0 <= 99 }"

child:

schedule: "[{ Stmt_S1[i0] -> [(i0)];
              Stmt_S2[i0, i1] -> [(i0)];
              Stmt_S3[i0] -> [(i0)];
            }]"
child:
  sequence:
  - filter: "{ Stmt_S1[i0] }"
  - filter: "{ Stmt_S2[i0, i1] }"
    child:
      schedule: "[{ Stmt_S2[i0, i1] -> [(i1)] }]"
  - filter: "{ Stmt_S3[i0] }"

[grosser]

Test comment to see if pollydev receives review messages.

If it does: have a look, this is the schedule-tree commit

[grosser]

The previous patch had some correctness issues slipping in, which invalidated
the original performance results. This patch should be more correct, but
again slower. We now convert from the schedule tree back to flat dependences
to allow our normal reduction dependence analysis to work.

[jdoerfert]

I'll work on the may write reduction dependences next week so we can integrate this.

[jdoerfert]

Already commited. Please close.

[grosser]

This has been integrated already.

include/polly/ScopInfo.h

 struct isl_id;
 struct isl_set;
 struct isl_union_set;
 struct isl_union_map;
 struct isl_space;
 struct isl_ast_build;
 struct isl_constraint;
 struct isl_pw_multi_aff;
+struct isl_schedule;
 
 namespace polly {
 
 class IRAccess;
 class Scop;
 class ScopStmt;
 class ScopInfo;
 class TempScop;
class ScopStmt {
   ///
   ///     Domain: 0 <= i <= 100 + b
   ///             0 <= j <= i
   ///
   /// A pair of statement and iteration vector (S, (5,3)) is called statement
   /// instance.
   isl_set *Domain;
 
-  /// The schedule map describes the execution order of the statement
-  /// instances.
-  ///
-  /// A statement and its iteration domain do not give any information about the
-  /// order in time in which the different statement instances are executed.
-  /// This information is provided by the schedule.
-  ///
-  /// The schedule maps every instance of each statement into a multi
-  /// dimensional schedule space. This space can be seen as a multi
-  /// dimensional clock.
-  ///
-  /// Example:
-  ///
-  /// <S,(5,4)>  may be mapped to (5,4) by this schedule:
-  ///
-  /// s0 = i (Year of execution)
-  /// s1 = j (Day of execution)
-  ///
-  /// or to (9, 20) by this schedule:
-  ///
-  /// s0 = i + j (Year of execution)
-  /// s1 = 20 (Day of execution)
-  ///
-  /// The order statement instances are executed is defined by the
-  /// schedule vectors they are mapped to. A statement instance
-  /// <A, (i, j, ..)> is executed before a statement instance <B, (i', ..)>, if
-  /// the schedule vector of A is lexicographic smaller than the schedule
-  /// vector of B.
-  isl_map *Schedule;
-
   /// The memory accesses of this statement.
   ///
   /// The only side effects of a statement are its memory accesses.
   typedef SmallVector<MemoryAccess *, 8> MemoryAccessVec;
   MemoryAccessVec MemAccs;
   std::map<const Instruction *, MemoryAccess *> InstructionToAccess;
 
   //@}
class ScopStmt {
   //@{
   __isl_give isl_set *buildConditionSet(const Comparison &Cmp);
   __isl_give isl_set *addConditionsToDomain(__isl_take isl_set *Domain,
                                             TempScop &tempScop,
                                             const Region &CurRegion);
   __isl_give isl_set *addLoopBoundsToDomain(__isl_take isl_set *Domain,
                                             TempScop &tempScop);
   __isl_give isl_set *buildDomain(TempScop &tempScop, const Region &CurRegion);
-  void buildSchedule(SmallVectorImpl<unsigned> &ScheduleVec);
 
   /// @brief Create the accesses for instructions in @p Block.
   ///
   /// @param tempScop       The template SCoP.
   /// @param Block          The basic block for which accesses should be
   ///                       created.
   /// @param isApproximated Flag to indicate blocks that might not be executed,
   ///                       hence for which write accesses need to be modeled as
class ScopStmt {
   /// or non-optimal run-time checks.
   void deriveAssumptionsFromGEP(GetElementPtrInst *Inst);
 
   /// @brief Scan @p Block and derive assumptions about parameter values.
   void deriveAssumptions(BasicBlock *Block);
 
   /// Create the ScopStmt from a BasicBlock.
   ScopStmt(Scop &parent, TempScop &tempScop, const Region &CurRegion,
-           BasicBlock &bb, SmallVectorImpl<Loop *> &NestLoops,
-           SmallVectorImpl<unsigned> &ScheduleVec);
+           BasicBlock &bb, SmallVectorImpl<Loop *> &NestLoops);
 
   /// Create an overapproximating ScopStmt for the region @p R.
   ScopStmt(Scop &parent, TempScop &tempScop, const Region &CurRegion, Region &R,
-           SmallVectorImpl<Loop *> &NestLoops,
-           SmallVectorImpl<unsigned> &ScheduleVec);
+           SmallVectorImpl<Loop *> &NestLoops);
 
   friend class Scop;
 
 public:
   ~ScopStmt();
 
   /// @brief Get an isl_ctx pointer.
   isl_ctx *getIslCtx() const;
public:
 
   /// @brief Get an isl string representing this domain.
   std::string getDomainStr() const;
 
   /// @brief Get the schedule function of this ScopStmt.
   ///
   /// @return The schedule function of this ScopStmt.
   __isl_give isl_map *getSchedule() const;
-  void setSchedule(__isl_take isl_map *Schedule);
 
   /// @brief Get an isl string representing this schedule.
   std::string getScheduleStr() const;
 
   /// @brief Get the BasicBlock represented by this ScopStmt (if any).
   ///
   /// @return The BasicBlock represented by this ScopStmt, or null if the
   ///         statement represents a region.
public:
 
   iterator begin() { return MemAccs.begin(); }
   iterator end() { return MemAccs.end(); }
   const_iterator begin() const { return MemAccs.begin(); }
   const_iterator end() const { return MemAccs.end(); }
 
   unsigned getNumParams() const;
   unsigned getNumIterators() const;
-  unsigned getNumSchedule() const;
 
   Scop *getParent() { return &Parent; }
   const Scop *getParent() const { return &Parent; }
 
   const char *getBaseName() const;
 
   /// @brief Set the isl AST build.
   void setAstBuild(__isl_keep isl_ast_build *B) { Build = B; }
private:
   ///
   /// When constructing a scop sometimes the exact representation of a statement
   /// or condition would be very complex, but there is a common case which is a
   /// lot simpler, but which is only valid under certain assumptions. The
   /// assumed context records the assumptions taken during the construction of
   /// this scop and that need to be code generated as a run-time test.
   isl_set *AssumedContext;
 
+  /// @brief The schedule of the SCoP
+  ///
+  /// The schedule of the SCoP describes the execution order of the statements
+  /// in the scop by assigning each statement instance a possibly
+  /// multi-dimensional execution time. The schedule is stored as a tree of
+  /// schedule nodes.
+  ///
+  /// The most common nodes in a schedule tree are so-called band nodes. Band
+  /// nodes map statement instances into a multi dimensional schedule space.
+  /// This space can be seen as a multi-dimensional clock.
+  ///
+  /// Example:
+  ///
+  /// <S,(5,4)>  may be mapped to (5,4) by this schedule:
+  ///
+  /// s0 = i (Year of execution)
+  /// s1 = j (Day of execution)
+  ///
+  /// or to (9, 20) by this schedule:
+  ///
+  /// s0 = i + j (Year of execution)
+  /// s1 = 20 (Day of execution)
+  ///
+  /// The order statement instances are executed is defined by the
+  /// schedule vectors they are mapped to. A statement instance
+  /// <A, (i, j, ..)> is executed before a statement instance <B, (i', ..)>, if
+  /// the schedule vector of A is lexicographic smaller than the schedule
+  /// vector of B.
+  ///
+  /// Besides band nodes, schedule trees contain additional nodes that specify
+  /// a textual ordering between two subtrees or filter nodes that filter the
+  /// set of statement instances that will be scheduled in a subtree. There
+  /// are also several other nodes. A full description of the different nodes
+  /// in a schedule tree is given in the isl manual.
+  isl_schedule *Schedule;
+
   /// @brief The set of minimal/maximal accesses for each alias group.
   ///
   /// When building runtime alias checks we look at all memory instructions and
   /// build so called alias groups. Each group contains a set of accesses to
   /// different base arrays which might alias with each other. However, between
   /// alias groups there is no aliasing possible.
   ///
   /// In a program with int and float pointers annotated with tbaa information
private:
   /// Either @p BB or @p R should be non-null. A new statement for the non-null
   /// argument will be created and added to the statement vector and map.
   ///
   /// @param BB         The basic block we build the statement for (or null)
   /// @param R          The region we build the statement for (or null).
   /// @param tempScop   The temp SCoP we use as model.
   /// @param CurRegion  The SCoP region.
   /// @param NestLoops  A vector of all surrounding loops.
-  /// @param Schedule   The position of the new statement as schedule.
-  void addScopStmt(BasicBlock *BB, Region *R, TempScop &tempScop,
-                   const Region &CurRegion, SmallVectorImpl<Loop *> &NestLoops,
-                   SmallVectorImpl<unsigned> &Schedule);
-
-  /// Build the Scop and Statement with precalculated scop information.
-  void buildScop(TempScop &TempScop, const Region &CurRegion,
-                 // Loops in Scop containing CurRegion
+  ScopStmt *addScopStmt(BasicBlock *BB, Region *R, TempScop &tempScop,
+                        const Region &CurRegion,
+                        SmallVectorImpl<Loop *> &NestLoops);
+
+  /// @brief Build Scop and ScopStmts from a given TempScop.
+  ///
+  /// @param TempScop  The temporary scop that is translated into an actual
+  ///                  scop.
+  /// @param CurRegion The subregion of the current scop that we are currently
+  ///                  translating.
+  /// @param NestLoop  The set of loops that surround the current subregion.
+  /// @param LI        The LoopInfo object.
+  /// @param SD        The ScopDetection object.
+  __isl_give isl_schedule *buildScop(TempScop &TempScop,
+                                     const Region &CurRegion,
                                      SmallVectorImpl<Loop *> &NestLoops,
-                 // The schedule numbers
-                 SmallVectorImpl<unsigned> &Schedule, LoopInfo &LI,
-                 ScopDetection &SD);
+                                     LoopInfo &LI, ScopDetection &SD);
 
   /// @name Helper function for printing the Scop.
   ///
   ///{
   void printContext(raw_ostream &OS) const;
   void printStatements(raw_ostream &OS) const;
   void printAliasAssumptions(raw_ostream &OS) const;
   ///}
public:
   inline const Region &getRegion() const { return R; }
   inline Region &getRegion() { return R; }
 
   /// @brief Get the maximum depth of the loop.
   ///
   /// @return The maximum depth of the loop.
   inline unsigned getMaxLoopDepth() const { return MaxLoopDepth; }
 
-  /// @brief Get the schedule dimension number of this Scop.
-  ///
-  /// @return The schedule dimension number of this Scop.
-  inline unsigned getScheduleDim() const {
-    unsigned maxScheduleDim = 0;
-
-    for (const_iterator SI = begin(), SE = end(); SI != SE; ++SI)
-      maxScheduleDim = std::max(maxScheduleDim, (*SI)->getNumSchedule());
-
-    return maxScheduleDim;
-  }
-
   /// @brief Mark the SCoP as optimized by the scheduler.
   void markAsOptimized() { IsOptimized = true; }
 
   /// @brief Check if the SCoP has been optimized by the scheduler.
   bool isOptimized() const { return IsOptimized; }
 
   /// @brief Get the name of this Scop.
   std::string getNameStr() const;
public:
   ///            to hold.
   void addAssumption(__isl_take isl_set *Set);
 
   /// @brief Build all alias groups for this SCoP.
   ///
   /// @returns True if __no__ error occurred, false otherwise.
   bool buildAliasGroups(AliasAnalysis &AA);
 
-  //// @brief Drop all constant dimensions from statment schedules.
-  ///
-  ///  Schedule dimensions that are constant accross the scop do not carry
-  ///  any information, but would cost compile time due to the increased number
-  ///  of schedule dimensions. To not pay this cost, we remove them.
-  void dropConstantScheduleDims();
-
   /// @brief Return all alias groups for this SCoP.
   const MinMaxVectorVectorTy &getAliasGroups() const {
     return MinMaxAliasGroups;
   }
 
   /// @brief Get an isl string representing the context.
   std::string getContextStr() const;
 
public:
   void dump() const;
 
   /// @brief Get the isl context of this static control part.
   ///
   /// @return The isl context of this static control part.
   isl_ctx *getIslCtx() const;
 
   /// @brief Get a union set containing the iteration domains of all statements.
-  __isl_give isl_union_set *getDomains();
+  __isl_give isl_union_set *getDomains() const;
 
   /// @brief Get a union map of all may-writes performed in the SCoP.
   __isl_give isl_union_map *getMayWrites();
 
   /// @brief Get a union map of all must-writes performed in the SCoP.
   __isl_give isl_union_map *getMustWrites();
 
   /// @brief Get a union map of all writes performed in the SCoP.
   __isl_give isl_union_map *getWrites();
 
   /// @brief Get a union map of all reads performed in the SCoP.
   __isl_give isl_union_map *getReads();
 
   /// @brief Get the schedule of all the statements in the SCoP.
-  __isl_give isl_union_map *getSchedule();
+  __isl_give isl_union_map *getSchedule() const;
+
+  /// @brief Get a schedule tree describing the schedule of all statements.
+  __isl_give isl_schedule *getScheduleTree() const;
+
+  /// @brief Update the current schedule
+  ///
+  /// @brief NewSchedule The new schedule (given as a flat union-map).
+  void setSchedule(__isl_take isl_union_map *NewSchedule);
+
+  /// @brief Update the current schedule
+  ///
+  /// @brief NewSchedule The new schedule (given as schedule tree).
+  void setScheduleTree(__isl_take isl_schedule *NewSchedule);
 
   /// @brief Intersects the domains of all statements in the SCoP.
   ///
   /// @return true if a change was made
   bool restrictDomains(__isl_take isl_union_set *Domain);
 };
 
 /// @brief Print Scop scop to raw_ostream O.

lib/Analysis/DependenceInfo.cpp

void Dependences::calculateDependences(Scop &S) {
   long MaxOpsOld = isl_ctx_get_max_operations(S.getIslCtx());
   if (OptComputeOut)
     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() << "MayWrite: " << MayWrite << "\n";
         dbgs() << "Schedule: " << ScheduleMap << "\n");
 
   RAW = WAW = WAR = RED = nullptr;
 
   auto *Schedule = isl_schedule_from_domain(
       isl_union_map_domain(isl_union_map_copy(ScheduleMap)));
   Schedule = isl_schedule_insert_partial_schedule(
       Schedule, isl_multi_union_pw_aff_from_union_map(ScheduleMap));

lib/Analysis/ScopInfo.cpp

 #include "isl/constraint.h"
 #include "isl/set.h"
 #include "isl/map.h"
 #include "isl/union_map.h"
 #include "isl/aff.h"
 #include "isl/printer.h"
 #include "isl/local_space.h"
 #include "isl/options.h"
+#include "isl/schedule_node.h"
+#include "isl/schedule.h"
 #include "isl/val.h"
 
 #include <sstream>
 #include <string>
 #include <vector>
 
 using namespace llvm;
 using namespace polly;

 
 void MemoryAccess::setNewAccessRelation(isl_map *newAccess) {
   isl_map_free(newAccessRelation);
   newAccessRelation = newAccess;
 }
 
 //===----------------------------------------------------------------------===//
 
-isl_map *ScopStmt::getSchedule() const { return isl_map_copy(Schedule); }
+isl_map *ScopStmt::getSchedule() const {
+  isl_set *Domain = getDomain();
+  if (isl_set_is_empty(Domain)) {
+    isl_set_free(Domain);
+    return isl_map_from_aff(
+        isl_aff_zero_on_domain(isl_local_space_from_space(getDomainSpace())));
+  }
+  auto *Schedule = getParent()->getSchedule();
+  Schedule = isl_union_map_intersect_domain(
+      Schedule, isl_union_set_from_set(isl_set_copy(Domain)));
+  if (isl_union_map_is_empty(Schedule)) {
+    isl_set_free(Domain);
+    isl_union_map_free(Schedule);
+    return isl_map_from_aff(
+        isl_aff_zero_on_domain(isl_local_space_from_space(getDomainSpace())));
+  }
+  auto *M = isl_map_from_union_map(Schedule);
+  M = isl_map_coalesce(M);
+  M = isl_map_gist_domain(M, Domain);
+  M = isl_map_coalesce(M);
+  return M;
+}
 
 void ScopStmt::restrictDomain(__isl_take isl_set *NewDomain) {
   assert(isl_set_is_subset(NewDomain, Domain) &&
          "New domain is not a subset of old domain!");
   isl_set_free(Domain);
   Domain = NewDomain;
-  Schedule = isl_map_intersect_domain(Schedule, isl_set_copy(Domain));
-}
-
-void ScopStmt::setSchedule(__isl_take isl_map *NewSchedule) {
-  assert(NewSchedule && "New schedule is nullptr");
-  isl_map_free(Schedule);
-  Schedule = NewSchedule;
-}
-
-void ScopStmt::buildSchedule(SmallVectorImpl<unsigned> &ScheduleVec) {
-  unsigned NbIterators = getNumIterators();
-  unsigned NbScheduleDims = Parent.getMaxLoopDepth() * 2 + 1;
-
-  isl_space *Space = isl_space_set_alloc(getIslCtx(), 0, NbScheduleDims);
-
-  Schedule = isl_map_from_domain_and_range(isl_set_universe(getDomainSpace()),
-                                           isl_set_universe(Space));
-
-  // Loop dimensions.
-  for (unsigned i = 0; i < NbIterators; ++i)
-    Schedule = isl_map_equate(Schedule, isl_dim_out, 2 * i + 1, isl_dim_in, i);
-
-  // Constant dimensions
-  for (unsigned i = 0; i < NbIterators + 1; ++i)
-    Schedule = isl_map_fix_si(Schedule, isl_dim_out, 2 * i, ScheduleVec[i]);
-
-  // Fill schedule dimensions.
-  for (unsigned i = 2 * NbIterators + 1; i < NbScheduleDims; ++i)
-    Schedule = isl_map_fix_si(Schedule, isl_dim_out, i, 0);
-
-  Schedule = isl_map_align_params(Schedule, Parent.getParamSpace());
 }
 
 void ScopStmt::buildAccesses(TempScop &tempScop, BasicBlock *Block,
                              bool isApproximated) {
   AccFuncSetType *AFS = tempScop.getAccessFunctions(Block);
   if (!AFS)
     return;
 
void ScopStmt::buildAccesses(TempScop &tempScop, BasicBlock *Block,
   }
 }
 
 void ScopStmt::realignParams() {
   for (MemoryAccess *MA : *this)
     MA->realignParams();
 
   Domain = isl_set_align_params(Domain, Parent.getParamSpace());
-  Schedule = isl_map_align_params(Schedule, Parent.getParamSpace());
 }
 
 __isl_give isl_set *ScopStmt::buildConditionSet(const Comparison &Comp) {
   isl_pw_aff *L = SCEVAffinator::getPwAff(this, Comp.getLHS());
   isl_pw_aff *R = SCEVAffinator::getPwAff(this, Comp.getRHS());
 
   switch (Comp.getPred()) {
   case ICmpInst::ICMP_EQ:

 
 void ScopStmt::deriveAssumptions(BasicBlock *Block) {
   for (Instruction &Inst : *Block)
     if (auto *GEP = dyn_cast<GetElementPtrInst>(&Inst))
       deriveAssumptionsFromGEP(GEP);
 }
 
 ScopStmt::ScopStmt(Scop &parent, TempScop &tempScop, const Region &CurRegion,
-                   Region &R, SmallVectorImpl<Loop *> &Nest,
-                   SmallVectorImpl<unsigned> &ScheduleVec)
+                   Region &R, SmallVectorImpl<Loop *> &Nest)
     : Parent(parent), BB(nullptr), R(&R), Build(nullptr),
       NestLoops(Nest.size()) {
   // Setup the induction variables.
   for (unsigned i = 0, e = Nest.size(); i < e; ++i)
     NestLoops[i] = Nest[i];
 
   BaseName = getIslCompatibleName("Stmt_(", R.getNameStr(), ")");
 
   Domain = buildDomain(tempScop, CurRegion);
-  buildSchedule(ScheduleVec);
 
   BasicBlock *EntryBB = R.getEntry();
   for (BasicBlock *Block : R.blocks()) {
     buildAccesses(tempScop, Block, Block != EntryBB);
     deriveAssumptions(Block);
   }
   checkForReductions();
 }
 
 ScopStmt::ScopStmt(Scop &parent, TempScop &tempScop, const Region &CurRegion,
-                   BasicBlock &bb, SmallVectorImpl<Loop *> &Nest,
-                   SmallVectorImpl<unsigned> &ScheduleVec)
+                   BasicBlock &bb, SmallVectorImpl<Loop *> &Nest)
     : Parent(parent), BB(&bb), R(nullptr), Build(nullptr),
       NestLoops(Nest.size()) {
   // Setup the induction variables.
   for (unsigned i = 0, e = Nest.size(); i < e; ++i)
     NestLoops[i] = Nest[i];
 
   BaseName = getIslCompatibleName("Stmt_", &bb, "");
 
   Domain = buildDomain(tempScop, CurRegion);
-  buildSchedule(ScheduleVec);
   buildAccesses(tempScop, BB);
   deriveAssumptions(BB);
   checkForReductions();
 }
 
 /// @brief Collect loads which might form a reduction chain with @p StoreMA
 ///
 /// Check if the stored value for @p StoreMA is a binary operator with one or
for (const auto &CandidatePair : Candidates) {
     CandidatePair.first->markAsReductionLike(RT);
     CandidatePair.second->markAsReductionLike(RT);
   }
 }
 
 std::string ScopStmt::getDomainStr() const { return stringFromIslObj(Domain); }
 
 std::string ScopStmt::getScheduleStr() const {
-  return stringFromIslObj(Schedule);
+  auto *S = getSchedule();
+  auto Str = stringFromIslObj(S);
+  isl_map_free(S);
+  return Str;
 }
 
 unsigned ScopStmt::getNumParams() const { return Parent.getNumParams(); }
 
 unsigned ScopStmt::getNumIterators() const { return NestLoops.size(); }
 
-unsigned ScopStmt::getNumSchedule() const {
-  return isl_map_dim(Schedule, isl_dim_out);
-}
-
 const char *ScopStmt::getBaseName() const { return BaseName.c_str(); }
 
 const Loop *ScopStmt::getLoopForDimension(unsigned Dimension) const {
   return NestLoops[Dimension];
 }
 
 isl_ctx *ScopStmt::getIslCtx() const { return Parent.getIslCtx(); }
 

 
 ScopStmt::~ScopStmt() {
   while (!MemAccs.empty()) {
     delete MemAccs.back();
     MemAccs.pop_back();
   }
 
   isl_set_free(Domain);
-  isl_map_free(Schedule);
 }
 
 void ScopStmt::print(raw_ostream &OS) const {
   OS << "\t" << getBaseName() << "\n";
   OS.indent(12) << "Domain :=\n";
 
   if (Domain) {
     OS.indent(16) << getDomainStr() << ";\n";
if (MaxLD == 0)
     return 1;
 
   assert(MinLD >= 1 && "Minimal loop depth should be at least one");
   assert(MaxLD >= MinLD &&
          "Maximal loop depth was smaller than mininaml loop depth?");
   return MaxLD - MinLD + 1;
 }
 
-void Scop::dropConstantScheduleDims() {
-  isl_union_map *FullSchedule = getSchedule();
-
-  if (isl_union_map_n_map(FullSchedule) == 0) {
-    isl_union_map_free(FullSchedule);
-    return;
-  }
-
-  isl_set *ScheduleSpace =
-      isl_set_from_union_set(isl_union_map_range(FullSchedule));
-  isl_map *DropDimMap = isl_set_identity(isl_set_copy(ScheduleSpace));
-
-  int NumDimsDropped = 0;
-  for (unsigned i = 0; i < isl_set_dim(ScheduleSpace, isl_dim_set); i += 2) {
-    isl_val *FixedVal =
-        isl_set_plain_get_val_if_fixed(ScheduleSpace, isl_dim_set, i);
-    if (isl_val_is_int(FixedVal)) {
-      DropDimMap =
-          isl_map_project_out(DropDimMap, isl_dim_out, i - NumDimsDropped, 1);
-      NumDimsDropped++;
-    }
-    isl_val_free(FixedVal);
-  }
-
-  for (auto *S : *this) {
-    isl_map *Schedule = S->getSchedule();
-    Schedule = isl_map_apply_range(Schedule, isl_map_copy(DropDimMap));
-    S->setSchedule(Schedule);
-  }
-  isl_set_free(ScheduleSpace);
-  isl_map_free(DropDimMap);
-}
-
 Scop::Scop(TempScop &tempScop, LoopInfo &LI, ScalarEvolution &ScalarEvolution,
            ScopDetection &SD, isl_ctx *Context)
     : SE(&ScalarEvolution), R(tempScop.getMaxRegion()), IsOptimized(false),
       MaxLoopDepth(getMaxLoopDepthInRegion(tempScop.getMaxRegion(), LI, SD)) {
   IslCtx = Context;
 
   buildContext();
 
   SmallVector<Loop *, 8> NestLoops;
-  SmallVector<unsigned, 8> Schedule;
-
-  Schedule.assign(MaxLoopDepth + 1, 0);
 
   // Build the iteration domain, access functions and schedule functions
   // traversing the region tree.
-  buildScop(tempScop, getRegion(), NestLoops, Schedule, LI, SD);
+  Schedule = buildScop(tempScop, getRegion(), NestLoops, LI, SD);
+  if (!Schedule)
+    Schedule = isl_schedule_empty(getParamSpace());
 
   realignParams();
   addParameterBounds();
   simplifyAssumedContext();
-  dropConstantScheduleDims();
 
   assert(NestLoops.empty() && "NestLoops not empty at top level!");
 }
 
 Scop::~Scop() {
   isl_set_free(Context);
   isl_set_free(AssumedContext);
+  isl_schedule_free(Schedule);
 
   // Free the statements;
   for (ScopStmt *Stmt : *this)
     delete Stmt;
 
   // Free the ScopArrayInfo objects.
   for (auto &ScopArrayInfoPair : ScopArrayInfoMap)
     delete ScopArrayInfoPair.second;
void Scop::print(raw_ostream &OS) const {
   printAliasAssumptions(OS);
   printStatements(OS.indent(4));
 }
 
 void Scop::dump() const { print(dbgs()); }
 
 isl_ctx *Scop::getIslCtx() const { return IslCtx; }
 
-__isl_give isl_union_set *Scop::getDomains() {
+__isl_give isl_union_set *Scop::getDomains() const {
   isl_union_set *Domain = isl_union_set_empty(getParamSpace());
 
   for (ScopStmt *Stmt : *this)
     Domain = isl_union_set_add_set(Domain, Stmt->getDomain());
 
   return Domain;
 }
 
for (MemoryAccess *MA : *Stmt) {
 
       AccessDomain = isl_map_intersect_domain(AccessDomain, Domain);
       Read = isl_union_map_add_map(Read, AccessDomain);
     }
   }
   return isl_union_map_coalesce(Read);
 }
 
-__isl_give isl_union_map *Scop::getSchedule() {
-  isl_union_map *Schedule = isl_union_map_empty(getParamSpace());
+__isl_give isl_union_map *Scop::getSchedule() const {
+  auto Tree = getScheduleTree();
+  auto S = isl_schedule_get_map(Tree);
+  isl_schedule_free(Tree);
+  return S;
+}
 
-  for (ScopStmt *Stmt : *this)
-    Schedule = isl_union_map_add_map(Schedule, Stmt->getSchedule());
+__isl_give isl_schedule *Scop::getScheduleTree() const {
+  return isl_schedule_intersect_domain(isl_schedule_copy(Schedule),
+                                       getDomains());
+}
 
-  return isl_union_map_coalesce(Schedule);
+void Scop::setSchedule(__isl_take isl_union_map *NewSchedule) {
+  auto *S = isl_schedule_from_domain(getDomains());
+  S = isl_schedule_insert_partial_schedule(
+      S, isl_multi_union_pw_aff_from_union_map(NewSchedule));
+  isl_schedule_free(Schedule);
+  Schedule = S;
+}
+
+void Scop::setScheduleTree(__isl_take isl_schedule *NewSchedule) {
+  isl_schedule_free(Schedule);
+  Schedule = NewSchedule;
 }
 
 bool Scop::restrictDomains(__isl_take isl_union_set *Domain) {
   bool Changed = false;
   for (ScopStmt *Stmt : *this) {
     isl_union_set *StmtDomain = isl_union_set_from_set(Stmt->getDomain());
     isl_union_set *NewStmtDomain = isl_union_set_intersect(
         isl_union_set_copy(StmtDomain), isl_union_set_copy(Domain));

 
 bool Scop::isTrivialBB(BasicBlock *BB, TempScop &tempScop) {
   if (tempScop.getAccessFunctions(BB))
     return false;
 
   return true;
 }
 
-void Scop::addScopStmt(BasicBlock *BB, Region *R, TempScop &tempScop,
+struct MapToDimensionDataTy {
+  int N;
+  isl_union_pw_multi_aff *Res;
+};
+
+// @brief Create a function that maps the elements of 'Set' to its N-th
+//        dimension.
+//
+// The result is added to 'User->Res'.
+//
+// @param Set The input set.
+// @param N   The dimension to map to.
+//
+// @returns   Zero if no error occurred, non-zero otherwise.
+static int mapToDimension_AddSet(__isl_take isl_set *Set, void *User) {
+  struct MapToDimensionDataTy *Data = (struct MapToDimensionDataTy *)User;
+  int Dim;
+  isl_space *Space;
+  isl_pw_multi_aff *PMA;
+
+  Dim = isl_set_dim(Set, isl_dim_set);
+  Space = isl_set_get_space(Set);
+  PMA = isl_pw_multi_aff_project_out_map(Space, isl_dim_set, Data->N,
+                                         Dim - Data->N);
+  if (Data->N > 1)
+    PMA = isl_pw_multi_aff_drop_dims(PMA, isl_dim_out, 0, Data->N - 1);
+  Data->Res = isl_union_pw_multi_aff_add_pw_multi_aff(Data->Res, PMA);
+
+  isl_set_free(Set);
+
+  return 0;
+}
+
+// @brief Create a function that maps the elements of Domain to their Nth
+//        dimension.
+//
+// @param Domain The set of elements to map.
+// @param N      The dimension to map to.
+static __isl_give isl_multi_union_pw_aff *
+mapToDimension(__isl_take isl_union_set *Domain, int N) {
+  struct MapToDimensionDataTy Data;
+  isl_space *Space;
+
+  Space = isl_union_set_get_space(Domain);
+  Data.N = N;
+  Data.Res = isl_union_pw_multi_aff_empty(Space);
+  if (isl_union_set_foreach_set(Domain, &mapToDimension_AddSet, &Data) < 0)
+    Data.Res = isl_union_pw_multi_aff_free(Data.Res);
+
+  isl_union_set_free(Domain);
+  return isl_multi_union_pw_aff_from_union_pw_multi_aff(Data.Res);
+}
+
+ScopStmt *Scop::addScopStmt(BasicBlock *BB, Region *R, TempScop &tempScop,
                             const Region &CurRegion,
-                       SmallVectorImpl<Loop *> &NestLoops,
-                       SmallVectorImpl<unsigned> &ScheduleVec) {
+                            SmallVectorImpl<Loop *> &NestLoops) {
   ScopStmt *Stmt;
 
   if (BB) {
-    Stmt =
-        new ScopStmt(*this, tempScop, CurRegion, *BB, NestLoops, ScheduleVec);
+    Stmt = new ScopStmt(*this, tempScop, CurRegion, *BB, NestLoops);
     StmtMap[BB] = Stmt;
   } else {
     assert(R && "Either a basic block or a region is needed to "
                 "create a new SCoP stmt.");
-    Stmt = new ScopStmt(*this, tempScop, CurRegion, *R, NestLoops, ScheduleVec);
+    Stmt = new ScopStmt(*this, tempScop, CurRegion, *R, NestLoops);
     for (BasicBlock *BB : R->blocks())
       StmtMap[BB] = Stmt;
   }
 
   // Insert all statements into the statement map and the statement vector.
   Stmts.push_back(Stmt);
 
-  // Increasing the Schedule function is OK for the moment, because
-  // we are using a depth first iterator and the program is well structured.
-  ++ScheduleVec[NestLoops.size()];
+  return Stmt;
 }
 
-void Scop::buildScop(TempScop &tempScop, const Region &CurRegion,
+__isl_give isl_schedule *Scop::buildScop(TempScop &tempScop,
+                                         const Region &CurRegion,
                                          SmallVectorImpl<Loop *> &NestLoops,
-                     SmallVectorImpl<unsigned> &ScheduleVec, LoopInfo &LI,
-                     ScopDetection &SD) {
-  if (SD.isNonAffineSubRegion(&CurRegion, &getRegion()))
-    return addScopStmt(nullptr, const_cast<Region *>(&CurRegion), tempScop,
-                       CurRegion, NestLoops, ScheduleVec);
+                                         LoopInfo &LI, ScopDetection &SD) {
+  if (SD.isNonAffineSubRegion(&CurRegion, &getRegion())) {
+    auto *Stmt = addScopStmt(nullptr, const_cast<Region *>(&CurRegion),
+                             tempScop, CurRegion, NestLoops);
+    auto *Domain = Stmt->getDomain();
+    return isl_schedule_from_domain(isl_union_set_from_set(Domain));
+  }
 
   Loop *L = castToLoop(CurRegion, LI);
 
   if (L)
     NestLoops.push_back(L);
 
   unsigned loopDepth = NestLoops.size();
-  assert(ScheduleVec.size() > loopDepth && "Schedule not big enough!");
+  isl_schedule *Schedule = nullptr;
 
   for (Region::const_element_iterator I = CurRegion.element_begin(),
                                       E = CurRegion.element_end();
-       I != E; ++I)
+       I != E; ++I) {
+    isl_schedule *StmtSchedule = nullptr;
     if (I->isSubRegion()) {
-      buildScop(tempScop, *I->getNodeAs<Region>(), NestLoops, ScheduleVec, LI,
-                SD);
+      StmtSchedule =
+          buildScop(tempScop, *I->getNodeAs<Region>(), NestLoops, LI, SD);
     } else {
       BasicBlock *BB = I->getNodeAs<BasicBlock>();
 
-      if (isTrivialBB(BB, tempScop))
+      if (isTrivialBB(BB, tempScop)) {
         continue;
+      } else {
+        auto *Stmt = addScopStmt(BB, nullptr, tempScop, CurRegion, NestLoops);
+        auto *Domain = Stmt->getDomain();
+        StmtSchedule = isl_schedule_from_domain(isl_union_set_from_set(Domain));
+      }
+    }
 
-      addScopStmt(BB, nullptr, tempScop, CurRegion, NestLoops, ScheduleVec);
-    }
+    if (!Schedule)
+      Schedule = StmtSchedule;
+    else if (StmtSchedule)
+      Schedule = isl_schedule_sequence(Schedule, StmtSchedule);
 
   if (!L)
-    return;
+    return Schedule;
+
+  auto *Domain = isl_schedule_get_domain(Schedule);
+  if (!isl_union_set_is_empty(Domain)) {
+    auto *MUPA = mapToDimension(isl_union_set_copy(Domain), loopDepth);
+    Schedule = isl_schedule_insert_partial_schedule(Schedule, MUPA);
+  }
+  isl_union_set_free(Domain);
 
-  // Exiting a loop region.
-  ScheduleVec[loopDepth] = 0;
   NestLoops.pop_back();
-  ++ScheduleVec[loopDepth - 1];
+  return Schedule;
 }
 
 ScopStmt *Scop::getStmtForBasicBlock(BasicBlock *BB) const {
   const auto &StmtMapIt = StmtMap.find(BB);
   if (StmtMapIt == StmtMap.end())
     return nullptr;
   return StmtMapIt->second;
 }

lib/CodeGen/IslAst.cpp

IslAst::IslAst(Scop *Scop, const Dependences &D)
 
   if (UseContext)
     Build = isl_ast_build_from_context(S->getContext());
   else
     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());
-
   if (PerformParallelTest) {
     BuildInfo.Deps = &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);
 
-  Root = isl_ast_build_ast_from_schedule(Build, Schedule);
+  Root = isl_ast_build_node_from_schedule(Build, S->getScheduleTree());
 
   isl_ast_build_free(Build);
 }
 
 IslAst::~IslAst() {
   isl_ast_node_free(Root);
   isl_ast_expr_free(RunCondition);
 }

lib/CodeGen/IslCodeGeneration.cpp

IslNodeBuilder::getUpperBound(__isl_keep isl_ast_node *For,
   isl_id_free(UBID);
 
   return UB;
 }
 
 unsigned IslNodeBuilder::getNumberOfIterations(__isl_keep isl_ast_node *For) {
   isl_union_map *Schedule = IslAstInfo::getSchedule(For);
   isl_set *LoopDomain = isl_set_from_union_set(isl_union_map_range(Schedule));
+  if (isl_set_is_wrapping(LoopDomain))
+    LoopDomain = isl_map_range(isl_set_unwrap(LoopDomain));
+
   int NumberOfIterations = polly::getNumberOfIterations(LoopDomain);
   if (NumberOfIterations == -1)
     return -1;
   return NumberOfIterations + 1;
 }
 
 struct FindValuesUser {
   LoopInfo &LI;

lib/Exchange/JSONExporter.cpp

errs() << "JScop file contains a schedule that changes the "
            << "dependences. Use -disable-polly-legality to continue anyways\n";
     for (StatementToIslMapTy::iterator SI = NewSchedule.begin(),
                                        SE = NewSchedule.end();
          SI != SE; ++SI)
       isl_map_free(SI->second);
     return false;
   }
 
+  auto ScheduleMap = isl_union_map_empty(S.getParamSpace());
   for (Scop::iterator SI = S.begin(), SE = S.end(); SI != SE; ++SI) {
     ScopStmt *Stmt = *SI;
 
     if (NewSchedule.find(Stmt) != NewSchedule.end())
-      Stmt->setSchedule(NewSchedule[Stmt]);
+      ScheduleMap = isl_union_map_add_map(ScheduleMap, NewSchedule[Stmt]);
+    else
+      ScheduleMap = isl_union_map_add_map(ScheduleMap, Stmt->getSchedule());
   }
 
+  S.setSchedule(ScheduleMap);
+
   int statementIdx = 0;
   for (Scop::iterator SI = S.begin(), SE = S.end(); SI != SE; ++SI) {
     ScopStmt *Stmt = *SI;
 
     int memoryAccessIdx = 0;
     for (MemoryAccess *MA : *Stmt) {
       Json::Value accesses = jscop["statements"][statementIdx]["accesses"]
                                   [memoryAccessIdx]["relation"];

lib/Transform/ScheduleOptimizer.cpp

private:
   ///
   ///  - Prevectorize the point loop of the tile
   ///      - if vectorization is enabled
   ///
   /// @param Node The schedule node to (possibly) optimize.
   /// @param User A pointer to forward some use information (currently unused).
   static isl_schedule_node *optimizeBand(isl_schedule_node *Node, void *User);
 
-  static __isl_give isl_union_map *
-  getScheduleMap(__isl_keep isl_schedule *Schedule);
+  /// @brief Apply post-scheduling transformations.
+  ///
+  /// This function applies a set of additional local transformations on the
+  /// schedule tree as it computed by the isl scheduler. Local transformations
+  /// applied include:
+  ///
+  ///   - Tiling
+  ///   - Prevectorization
+  ///
+  /// @param Schedule The schedule object post-transformations will be applied
+  ///                 on.
+  /// @returns        The transformed schedule.
+  static __isl_give isl_schedule *
+  addPostTransforms(__isl_take isl_schedule *Schedule);
 
   using llvm::Pass::doFinalization;
 
   virtual bool doFinalization() override {
     isl_schedule_free(LastSchedule);
     LastSchedule = nullptr;
     return true;
   }
isl_schedule_node *IslScheduleOptimizer::optimizeBand(isl_schedule_node *Node,
   }
 
   isl_schedule_node_free(Res);
   Res = isl_schedule_node_delete(Child);
   Res = isl_schedule_node_insert_partial_schedule(Res, ChildSchedule);
   return Res;
 }
 
-__isl_give isl_union_map *
-IslScheduleOptimizer::getScheduleMap(__isl_keep isl_schedule *Schedule) {
+__isl_give isl_schedule *
+IslScheduleOptimizer::addPostTransforms(__isl_take isl_schedule *Schedule) {
   isl_schedule_node *Root = isl_schedule_get_root(Schedule);
+  isl_schedule_free(Schedule);
   Root = isl_schedule_node_map_descendant(
       Root, IslScheduleOptimizer::optimizeBand, NULL);
-  auto ScheduleMap = isl_schedule_node_get_subtree_schedule_union_map(Root);
-  ScheduleMap = isl_union_map_detect_equalities(ScheduleMap);
+  auto S = isl_schedule_node_get_schedule(Root);
   isl_schedule_node_free(Root);
-  return ScheduleMap;
+  return S;
 }
 
 bool IslScheduleOptimizer::isProfitableSchedule(
     Scop &S, __isl_keep isl_union_map *NewSchedule) {
   // To understand if the schedule has been optimized we check if the schedule
   // has changed at all.
   // TODO: We can improve this by tracking if any necessarily beneficial
   // transformations have been performed. This can e.g. be tiling, loop
bool IslScheduleOptimizer::runOnScop(Scop &S) {
 
   // In cases the scheduler is not able to optimize the code, we just do not
   // touch the schedule.
   if (!Schedule)
     return false;
 
   DEBUG(dbgs() << "Schedule := " << stringFromIslObj(Schedule) << ";\n");
 
-  isl_union_map *NewSchedule = getScheduleMap(Schedule);
+  isl_schedule *NewSchedule = addPostTransforms(Schedule);
+  isl_union_map *NewScheduleMap = isl_schedule_get_map(NewSchedule);
 
   // Check if the optimizations performed were profitable, otherwise exit early.
-  if (!isProfitableSchedule(S, NewSchedule)) {
-    isl_schedule_free(Schedule);
-    isl_union_map_free(NewSchedule);
+  if (!isProfitableSchedule(S, NewScheduleMap)) {
+    isl_union_map_free(NewScheduleMap);
+    isl_schedule_free(NewSchedule);
     return false;
   }
-
+  S.setScheduleTree(NewSchedule);
   S.markAsOptimized();
 
-  for (ScopStmt *Stmt : S) {
-    isl_map *StmtSchedule;
-    isl_set *Domain = Stmt->getDomain();
-    isl_union_map *StmtBand;
-    StmtBand = isl_union_map_intersect_domain(isl_union_map_copy(NewSchedule),
-                                              isl_union_set_from_set(Domain));
-    if (isl_union_map_is_empty(StmtBand)) {
-      StmtSchedule = isl_map_from_domain(isl_set_empty(Stmt->getDomainSpace()));
-      isl_union_map_free(StmtBand);
-    } else {
-      assert(isl_union_map_n_map(StmtBand) == 1);
-      StmtSchedule = isl_map_from_union_map(StmtBand);
-    }
-
-    Stmt->setSchedule(StmtSchedule);
-  }
+  isl_union_map_free(NewScheduleMap);
 
-  isl_schedule_free(Schedule);
-  isl_union_map_free(NewSchedule);
   return false;
 }
 
 void IslScheduleOptimizer::printScop(raw_ostream &OS, Scop &) const {
   isl_printer *p;
   char *ScheduleStr;
 
   OS << "Calculated schedule:\n";

test/DeadCodeElimination/chained_iterations.ll

for.body.3:
   %indvar.next.3 = add i64 %indvar.3, 1
   %exitcond.3 = icmp ne i64 %indvar.next.3, 200
   br i1 %exitcond.3, label %for.body.3 , label %exit.3
 
 exit.3:
   ret void
 }
 
-; CHECK: for (int c1 = 0; c1 <= 199; c1 += 1)
-; CHECK:   Stmt_for_body_1(c1);
-; CHECK: for (int c1 = 0; c1 <= 199; c1 += 1)
-; CHECK:   Stmt_for_body_2(c1);
-; CHECK: for (int c1 = 0; c1 <= 199; c1 += 1)
-; CHECK:   Stmt_for_body_3(c1);
+; CHECK: for (int c0 = 0; c0 <= 199; c0 += 1)
+; CHECK:   Stmt_for_body_1(c0);
+; CHECK: for (int c0 = 0; c0 <= 199; c0 += 1)
+; CHECK:   Stmt_for_body_2(c0);
+; CHECK: for (int c0 = 0; c0 <= 199; c0 += 1)
+; CHECK:   Stmt_for_body_3(c0);
 
-; CHECK-DCE: for (int c1 = 0; c1 <= 199; c1 += 1)
-; CHECK-DCE:   Stmt_for_body_3(c1);
+; CHECK-DCE: for (int c0 = 0; c0 <= 199; c0 += 1)
+; CHECK-DCE:   Stmt_for_body_3(c0);
 

test/DeadCodeElimination/chained_iterations_2.ll

for.body.3:
   %indvar.next.3 = add i64 %indvar.3, 1
   %exitcond.3 = icmp ne i64 %indvar.next.3, 200
   br i1 %exitcond.3, label %for.body.3 , label %exit.3
 
 exit.3:
   ret void
 }
 
-; CHECK: for (int c1 = 0; c1 <= 199; c1 += 1)
-; CHECK:   Stmt_for_body_1(c1);
-; CHECK: for (int c1 = 0; c1 <= 199; c1 += 1)
-; CHECK:   Stmt_for_body_2(c1);
-; CHECK: for (int c1 = 0; c1 <= 199; c1 += 1)
-; CHECK:   Stmt_for_body_3(c1);
+; CHECK: for (int c0 = 0; c0 <= 199; c0 += 1)
+; CHECK:   Stmt_for_body_1(c0);
+; CHECK: for (int c0 = 0; c0 <= 199; c0 += 1)
+; CHECK:   Stmt_for_body_2(c0);
+; CHECK: for (int c0 = 0; c0 <= 199; c0 += 1)
+; CHECK:   Stmt_for_body_3(c0);
 
-; CHECK-DCE: for (int c1 = 0; c1 <= 199; c1 += 1)
-; CHECK-DCE:   Stmt_for_body_3(c1);
+; CHECK-DCE: for (int c0 = 0; c0 <= 199; c0 += 1)
+; CHECK-DCE:   Stmt_for_body_3(c0);

test/DeadCodeElimination/computeout.ll

S3:
   %exitcond.3 = icmp ne i64 %indvar.next.3, 200
   br i1 %exitcond.3, label %S3 , label %exit.3
 
 exit.3:
   ret void
 }
 
 ; CHECK-NOT: Stmt_S
-; CHECK: for (int c1 = 0; c1 <= 199; c1 += 1)
-; CHECK: Stmt_S3(c1);
+; CHECK: for (int c0 = 0; c0 <= 199; c0 += 1)
+; CHECK: Stmt_S3(c0);
 
-; TIMEOUT: for (int c1 = 0; c1 <= 99; c1 += 1)
-; TIMEOUT: Stmt_S1(c1);
-; TIMEOUT: for (int c1 = 0; c1 <= 9; c1 += 1)
-; TIMEOUT: Stmt_S2(c1);
-; TIMEOUT: for (int c1 = 0; c1 <= 199; c1 += 1)
-; TIMEOUT: Stmt_S3(c1);
+; TIMEOUT: for (int c0 = 0; c0 <= 99; c0 += 1)
+; TIMEOUT: Stmt_S1(c0);
+; TIMEOUT: for (int c0 = 0; c0 <= 9; c0 += 1)
+; TIMEOUT: Stmt_S2(c0);
+; TIMEOUT: for (int c0 = 0; c0 <= 199; c0 += 1)
+; TIMEOUT: Stmt_S3(c0);
 

test/DeadCodeElimination/dead_iteration_elimination.ll

for.body.4:
   %indvar.next.4 = add i64 %indvar.4, 1
   %exitcond.4 = icmp ne i64 %indvar.next.4, 10
   br i1 %exitcond.4, label %for.body.4, label %exit.4
 
 exit.4:
   ret void
 }
 
-; CHECK: for (int c1 = 50; c1 <= 99; c1 += 1)
-; CHECK:   Stmt_for_body_1(c1);
-; CHECK: for (int c1 = 110; c1 <= 199; c1 += 1)
-; CHECK:   Stmt_for_body_1(c1);
-; CHECK: for (int c1 = 0; c1 <= 49; c1 += 1)
-; CHECK:   Stmt_for_body_2(c1);
-; CHECK: for (int c1 = 0; c1 <= 69; c1 += 1)
-; CHECK:   Stmt_for_body_3(c1);
-; CHECK: for (int c1 = 0; c1 <= 9; c1 += 1)
+; CHECK: for (int c0 = 50; c0 <= 99; c0 += 1)
+; CHECK:   Stmt_for_body_1(c0);
+; CHECK: for (int c0 = 110; c0 <= 199; c0 += 1)
+; CHECK:   Stmt_for_body_1(c0);
+; CHECK: for (int c0 = 0; c0 <= 49; c0 += 1)
+; CHECK:   Stmt_for_body_2(c0);
+; CHECK: for (int c0 = 0; c0 <= 69; c0 += 1)
+; CHECK:   Stmt_for_body_3(c0);
+; CHECK: for (int c0 = 0; c0 <= 9; c0 += 1)

test/DeadCodeElimination/non-affine-affine-mix.ll

 ; RUN: opt %loadPolly -polly-detect-unprofitable -polly-allow-nonaffine -polly-dce -polly-ast -analyze -polly-no-early-exit < %s | FileCheck %s
 ;
 ;    void f(int *A) {
 ;      for (int i = 0; i < 1024; i++)
 ; S1:    A[i % 2] = i;
 ;      for (int i = 0; i < 1024; i++)
 ; S2:    A[i2] = i;
 ;    }
 
 ; We unfortunately do need to execute all iterations of S1, as we do not know
 ; the size of A and as a result S1 may write for example to A[1024], which
 ; is not overwritten by S2.
 
-; CHECK: for (int c1 = 0; c1 <= 1023; c1 += 1)
-; CHECK:   Stmt_S1(c1);
-; CHECK: for (int c1 = 0; c1 <= 1023; c1 += 1)
-; CHECK:   Stmt_S2(c1);
+; CHECK: for (int c0 = 0; c0 <= 1023; c0 += 1)
+; CHECK:   Stmt_S1(c0);
+; CHECK: for (int c0 = 0; c0 <= 1023; c0 += 1)
+; CHECK:   Stmt_S2(c0);
 
 target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-n32-S64"
 
 define void @f(i32* %A) {
 entry:
   br label %for.cond
 
 for.cond:

test/DeadCodeElimination/null_schedule.ll

for.body.2:
   %indvar.next.2 = add i64 %indvar.2, 1
   %exitcond.2 = icmp ne i64 %indvar.next.2, 200
   br i1 %exitcond.2, label %for.body.2, label %exit.3
 
 exit.3:
   ret void
 }
 
-; CHECK-DCE: for (int c1 = 0; c1 <= 199; c1 += 1)
-; CHECK-DCE:   Stmt_for_body_2(c1);
+; CHECK-DCE: for (int c0 = 0; c0 <= 199; c0 += 1)
+; CHECK-DCE:   Stmt_for_body_2(c0);

test/Isl/Ast/reduction_modulo_schedule_multiple_dimensions_4.ll

 ; RUN: opt %loadPolly -polly-detect-unprofitable -polly-import-jscop-dir=%S -polly-import-jscop -polly-ast -polly-ast-detect-parallel -analyze < %s | FileCheck %s
 ;
 ; Verify that the outer dimension doesnt't carry reduction dependences
 ;
 ; CHECK-NOT:#pragma known-parallel reduction
 ; CHECK:    #pragma known-parallel
 ; CHECK:    for (int c1 = 0; c1 < 2 * n; c1 += 1)
 ; CHECK:      #pragma simd reduction
-; CHECK:      for (int c3 = -1022; c3 <= 1023; c3 += 1) {
+; CHECK:      for (int c3 = -1023; c3 <= 1023; c3 += 1) {
 ; CHECK:        if (c3 <= 0 && c3 % 2 == 0) {
 ; CHECK:          Stmt_for_body3(c1, -c3);
 ; CHECK:        } else if (c3 >= 1 && (c3 - 1) % 2 == 0)
 ; CHECK:          Stmt_for_body3(c1, c3);
 ; CHECK:      }
 ;
 ;    void rmsmd4(int *A, long n) {
 ;      for (long i = 0; i < 2 * n; i++)

test/Isl/Ast/simple-run-time-condition.ll

 
 ; CHECK: if (
 ; CHECK: (o >= 1 && q <= 0 && m + q >= 0)
 ; CHECK: ||
 ; CHECK; (o <= 0 && m + q >= 100 && q <= 100)
 ; CHECK: )
 
 ; CHECK:     if (o >= 1) {
-; CHECK:       for (int c1 = 0; c1 < n; c1 += 1)
-; CHECK:         for (int c2 = 0; c2 < m; c2 += 1)
-; CHECK:           Stmt_for_j(c1, c2);
+; CHECK:       for (int c0 = 0; c0 < n; c0 += 1)
+; CHECK:         for (int c1 = 0; c1 < m; c1 += 1)
+; CHECK:           Stmt_for_j(c0, c1);
 ; CHECK:     } else
-; CHECK:       for (int c1 = 0; c1 < n; c1 += 1)
-; CHECK:         for (int c2 = 0; c2 < m; c2 += 1)
-; CHECK:           Stmt_for_j_1(c1, c2);
+; CHECK:       for (int c0 = 0; c0 < n; c0 += 1)
+; CHECK:         for (int c1 = 0; c1 < m; c1 += 1)
+; CHECK:           Stmt_for_j_1(c0, c1);
 
 ; CHECK: else
 ; CHECK:     {  /* original code */ }
 
 define void @foo(i64 %n, i64 %m, i64 %o, double* %A, i64 %p, i64 %q) {
 entry:
   br label %cond
 

test/Isl/CodeGen/loop_with_condition.ll

 ; <label>:28                                      ; preds = %27, %23, %17, %6
   %.0 = phi i32 [ 1, %6 ], [ 1, %17 ], [ 1, %23 ], [ 0, %27 ] ; <i32> [#uses=1]
   ret i32 %.0
 }
 
 declare void @llvm.memset.p0i8.i64(i8* nocapture, i8, i64, i32, i1) nounwind
 
 ; CHECK: for (int c0 = 0; c0 <= 1023; c0 += 1) {
-; CHECK:   if (c0 >= 513) {
-; CHECK:     Stmt_5(c0);
-; CHECK:   } else
+; CHECK:   if (c0 <= 512) {
 ; CHECK:     Stmt_4(c0);
+; CHECK:   } else
+; CHECK:     Stmt_5(c0);
 ; CHECK:   Stmt_6(c0);
 ; CHECK: }

test/Isl/CodeGen/loop_with_condition_2.ll

 ; RUN: opt %loadPolly -polly-detect-unprofitable -basicaa -polly-ast -polly-ast-detect-parallel -analyze < %s | FileCheck %s
 
 ; Verify that we actually detect this loop as the innermost loop even though
 ; there is a conditional inside.
 
 ; CHECK: #pragma simd
 ; CHECK: for (int c0 = 0; c0 <= 1023; c0 += 1) {
-; CHECK:   if (c0 >= m + 1025) {
-; CHECK:     Stmt_if_else(c0);
-; CHECK:   } else
+; CHECK:   if (m + 1024 >= c0) {
 ; CHECK:     Stmt_if_then(c0);
+; CHECK:   } else
+; CHECK:     Stmt_if_else(c0);
 ; CHECK:   Stmt_if_end(c0);
 ; CHECK: }
 
 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"
 
 @A = common global [1024 x i32] zeroinitializer, align 16
 @B = common global [1024 x i32] zeroinitializer, align 16
 

test/Isl/CodeGen/loop_with_condition_ineq.ll

 ; <label>:28                                      ; preds = %27, %23, %17, %6
   %.0 = phi i32 [ 1, %6 ], [ 1, %17 ], [ 1, %23 ], [ 0, %27 ] ; <i32> [#uses=1]
   ret i32 %.0
 }
 
 declare void @llvm.memset.p0i8.i64(i8* nocapture, i8, i64, i32, i1) nounwind
 
 ; CHECK: for (int c0 = 0; c0 <= 1023; c0 += 1) {
-; CHECK:   if (c0 >= 513) {
-; CHECK:     Stmt_4(c0);
-; CHECK:   } else if (c0 <= 511) {
+; CHECK:   if (c0 >= 513 || c0 <= 511) {
 ; CHECK:     Stmt_4(c0);
 ; CHECK:   } else
 ; CHECK:     Stmt_5(512);
 ; CHECK:   Stmt_6(c0);
 ; CHECK: }

test/Isl/CodeGen/loop_with_condition_nested.ll

 ; <label>:39                                      ; preds = %38, %33, %27, %19, %6
   %.0 = phi i32 [ 1, %6 ], [ 1, %19 ], [ 1, %27 ], [ 1, %33 ], [ 0, %38 ] ; <i32> [#uses=1]
   ret i32 %.0
 }
 
 declare void @llvm.memset.p0i8.i64(i8* nocapture, i8, i64, i32, i1) nounwind
 
 ; CHECK: for (int c0 = 0; c0 <= 1023; c0 += 1) {
-; CHECK:   if (c0 <= 20) {
-; CHECK:     Stmt_7(c0);
-; CHECK:   } else if (c0 <= 512)
+; CHECK:   if (c0 >= 21 && c0 <= 512) {
 ; CHECK:     Stmt_6(c0);
+; CHECK:   } else if (c0 <= 20)
+; CHECK:     Stmt_7(c0);
 ; CHECK:   Stmt_9(c0);
 ; CHECK: }
 
 ; LOOPS: Printing analysis 'Natural Loop Information' for function 'loop_with_condition':
 ; LOOPS: Loop at depth 1 containing: %1<header><exiting>,%2,%4,%7,%6,%8,%9,%10<latch>
 ; LOOPS: Loop at depth 1 containing:
 ; LOOPS: %polly.loop_header<header>,%polly.cond,%polly.merge,%polly.then,%polly.else,%polly.stmt.,%polly.cond3,%polly.merge4,%polly.then5,%polly.else6,%polly.stmt.7,%polly.stmt{{.*}}<latch><exiting>

test/Isl/CodeGen/sequential_loops.ll

 bb17:                                             ; preds = %bb16, %bb13, %bb7
   %.0 = phi i32 [ 1, %bb7 ], [ 1, %bb13 ], [ 0, %bb16 ]
   ret i32 %.0
 }
 
 declare void @llvm.memset.p0i8.i64(i8* nocapture, i8, i64, i32, i1) nounwind
 
 ; CHECK: {
-; CHECK:   for (int c1 = 0; c1 <= 511; c1 += 1)
-; CHECK:     Stmt_bb2(c1);
-; CHECK:   for (int c1 = 0; c1 <= 511; c1 += 1)
-; CHECK:     Stmt_bb6(c1);
+; CHECK:   for (int c0 = 0; c0 <= 511; c0 += 1)
+; CHECK:     Stmt_bb2(c0);
+; CHECK:   for (int c0 = 0; c0 <= 511; c0 += 1)
+; CHECK:     Stmt_bb6(c0);
 ; CHECK: }

test/ScheduleOptimizer/computeout.ll

 ; CHECK:   if (c0 <= 99) {
 ; CHECK:     Stmt_S1(c0);
 ; CHECK:     if (c0 <= 9)
 ; CHECK:       Stmt_S2(c0);
 ; CHECK:   }
 ; CHECK:   Stmt_S3(c0);
 ; CHECK: }
 
-; TIMEOUT: for (int c1 = 0; c1 <= 99; c1 += 1)
-; TIMEOUT: Stmt_S1(c1);
-; TIMEOUT: for (int c1 = 0; c1 <= 9; c1 += 1)
-; TIMEOUT: Stmt_S2(c1);
-; TIMEOUT: for (int c1 = 0; c1 <= 199; c1 += 1)
-; TIMEOUT: Stmt_S3(c1);
+; TIMEOUT: for (int c0 = 0; c0 <= 99; c0 += 1)
+; TIMEOUT: Stmt_S1(c0);
+; TIMEOUT: for (int c0 = 0; c0 <= 9; c0 += 1)
+; TIMEOUT: Stmt_S2(c0);
+; TIMEOUT: for (int c0 = 0; c0 <= 199; c0 += 1)
+; TIMEOUT: Stmt_S3(c0);
 

test/ScheduleOptimizer/line-tiling.ll

-; RUN: opt %loadPolly -polly-detect-unprofitable -polly-opt-isl -analyze -polly-no-tiling=0 -polly-ast -polly-tile-sizes=64,1 < %s | FileCheck %s
+; RUN: opt %loadPolly -polly-detect-unprofitable -polly-opt-isl -analyze -polly-ast -polly-tile-sizes=64,1 < %s | FileCheck %s
 
 ; CHECK: for (int c0 = 0; c0 <= 15; c0 += 1)
 ; CHECK:   for (int c1 = 0; c1 <= 511; c1 += 1)
 ; CHECK:     for (int c2 = 0; c2 <= 63; c2 += 1)
 ; CHECK:       Stmt_for_body3(64 * c0 + c2, c1);
 
 target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-n32-S64"
 

test/ScheduleOptimizer/one-dimensional-band.ll

-; RUN: opt %loadPolly -polly-opt-isl -polly-ast -analyze < %s | FileCheck %s
+; RUN: opt %loadPolly -polly-opt-isl -polly-ast -analyze -polly-no-early-exit < %s | FileCheck %s
 ;
 ;    void jacobi1d(long T, long N, float *A, float *B) {
 ;      long t, i, j;
 ;      for (t = 0; t < T; t++) {
 ;        for (i = 1; i < N - 1; i++)
 ;          B[i] = 0.33333 * (A[i - 1] + A[i] + A[i + 1]);
 ;        for (j = 1; j < N - 1; j++)
 ;          A[j] = 0.33333 * (B[i - 1] + B[i] + B[i + 1]);
 ;      }
 ;    }
 
 ; Verify that we do not tile bands that have just a single dimension.
 
 ; CHECK: for (int c0 = 0; c0 < T; c0 += 1) {
-; CHECK:   for (int c2 = 0; c2 < N - 2; c2 += 1)
-; CHECK:     Stmt_for_body3(c0, c2);
-; CHECK:   for (int c2 = 0; c2 < N - 2; c2 += 1)
-; CHECK:     Stmt_for_body15(c0, c2);
+; CHECK:   for (int c1 = 0; c1 < N - 2; c1 += 1)
+; CHECK:     Stmt_for_body3(c0, c1);
+; CHECK:   for (int c1 = 0; c1 < N - 2; c1 += 1)
+; CHECK:     Stmt_for_body15(c0, c1);
 ; CHECK: }
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 define void @jacobi1d(i64 %T, i64 %N, float* %A, float* %B) {
 entry:
   %tmp = add i64 %N, -1
   %tmp1 = icmp sgt i64 %tmp, 1

test/ScheduleOptimizer/prevectorization.ll

 
 for.end30:                                        ; preds = %for.inc28
   ret void
 }
 
 attributes #0 = { nounwind uwtable "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "stack-protector-buffer-size"="8" "unsafe-fp-math"="false" "use-soft-float"="false" }
 
 ; CHECK: #pragma known-parallel
-; CHECK: for (int c1 = 0; c1 <= 47; c1 += 1)
-; CHECK:   for (int c2 = 0; c2 <= 47; c2 += 1)
-; CHECK:     for (int c3 = 0; c3 <= 31; c3 += 1)
-; CHECK:       for (int c4 = 0; c4 <= 31; c4 += 4)
+; CHECK: for (int c0 = 0; c0 <= 47; c0 += 1)
+; CHECK:   for (int c1 = 0; c1 <= 47; c1 += 1)
+; CHECK:     for (int c2 = 0; c2 <= 31; c2 += 1)
+; CHECK:       for (int c3 = 0; c3 <= 31; c3 += 4)
 ; CHECK:         #pragma simd
-; CHECK:         for (int c5 = c4; c5 <= c4 + 3; c5 += 1)
-; CHECK:           Stmt_for_body3(32 * c1 + c3, 32 * c2 + c5);
+; CHECK:         for (int c4 = c3; c4 <= c3 + 3; c4 += 1)
+; CHECK:           Stmt_for_body3(32 * c0 + c2, 32 * c1 + c4);
 ; CHECK: #pragma known-parallel
-; CHECK: for (int c1 = 0; c1 <= 47; c1 += 1)
-; CHECK:   for (int c2 = 0; c2 <= 47; c2 += 1)
-; CHECK:     for (int c3 = 0; c3 <= 47; c3 += 1)
-; CHECK:       for (int c4 = 0; c4 <= 31; c4 += 1)
-; CHECK:         for (int c5 = 0; c5 <= 31; c5 += 4)
-; CHECK:           for (int c6 = 0; c6 <= 31; c6 += 1)
+; CHECK: for (int c0 = 0; c0 <= 47; c0 += 1)
+; CHECK:   for (int c1 = 0; c1 <= 47; c1 += 1)
+; CHECK:     for (int c2 = 0; c2 <= 47; c2 += 1)
+; CHECK:       for (int c3 = 0; c3 <= 31; c3 += 1)
+; CHECK:         for (int c4 = 0; c4 <= 31; c4 += 4)
+; CHECK:           for (int c5 = 0; c5 <= 31; c5 += 1)
 ; CHECK:             #pragma simd
-; CHECK:             for (int c7 = c5; c7 <= c5 + 3; c7 += 1)
-; CHECK:               Stmt_for_body8(32 * c1 + c4, 32 * c2 + c7, 32 * c3 + c6);
+; CHECK:             for (int c6 = c4; c6 <= c4 + 3; c6 += 1)
+; CHECK:               Stmt_for_body8(32 * c0 + c3, 32 * c1 + c6, 32 * c2 + c5);
 
 !llvm.ident = !{!0}
 
 !0 = !{!"clang version 3.5.0 "}

test/ScheduleOptimizer/rectangular-tiling.ll

 ; RUN: opt %loadPolly -polly-detect-unprofitable -polly-opt-isl -analyze -polly-ast -polly-tile-sizes=256,16 < %s | FileCheck %s
-; RUN: opt %loadPolly -polly-detect-unprofitable -polly-opt-isl -analyze -polly-no-tiling -polly-ast -polly-tile-sizes=256,16 < %s | FileCheck %s --check-prefix=NOTILING
+; RUN: opt %loadPolly -polly-detect-unprofitable -polly-opt-isl -analyze -polly-no-tiling -polly-ast -polly-tile-sizes=256,16 -polly-no-early-exit < %s | FileCheck %s --check-prefix=NOTILING
 
 ; CHECK: for (int c0 = 0; c0 <= 3; c0 += 1)
 ; CHECK:   for (int c1 = 0; c1 <= 31; c1 += 1)
 ; CHECK:     for (int c2 = 0; c2 <= 255; c2 += 1)
 ; CHECK:       for (int c3 = 0; c3 <= 15; c3 += 1)
 ; CHECK:         Stmt_for_body3(256 * c0 + c2, 16 * c1 + c3);
 
 ; NOTILING: for (int c0 = 0; c0 <= 1023; c0 += 1)

test/ScopInfo/NonAffine/non-affine-loop-condition-dependent-access_2.ll

 ; INNERMOST:    p4: {0,+,{0,+,4}<nuw><nsw><%bb11>}<%bb13>
 ; INNERMOST:    Alias Groups (0):
 ; INNERMOST:        n/a
 ; INNERMOST:    Statements {
 ; INNERMOST:      Stmt_bb16
 ; INNERMOST:            Domain :=
 ; INNERMOST:                [p_0, p_1, p_2, p_3, p_4] -> { Stmt_bb16[i0] : (i0 <= 1023 - p_1 and i0 >= 0 and i0 <= 1024 + p_0) or (i0 >= 0 and i0 >= 1025 - p_1 and i0 <= 1024 + p_0) };
 ; INNERMOST:            Schedule :=
-; INNERMOST:                [p_0, p_1, p_2, p_3, p_4] -> { Stmt_bb16[i0] -> [i0] };
+; INNERMOST:                [p_0, p_1, p_2, p_3, p_4] -> { Stmt_bb16[i0] -> [i0] : i0 >= 1025 - p_1 or i0 <= 1023 - p_1 };
 ; INNERMOST:            ReadAccess := [Reduction Type: NONE] [Scalar: 0]
 ; INNERMOST:                [p_0, p_1, p_2, p_3, p_4] -> { Stmt_bb16[i0] -> MemRef_A[o0] : 4o0 = p_2 };
 ; INNERMOST:            ReadAccess := [Reduction Type: NONE] [Scalar: 0]
 ; INNERMOST:                [p_0, p_1, p_2, p_3, p_4] -> { Stmt_bb16[i0] -> MemRef_A[o0] : 4o0 = p_3 };
 ; INNERMOST:            ReadAccess := [Reduction Type: +] [Scalar: 0]
 ; INNERMOST:                [p_0, p_1, p_2, p_3, p_4] -> { Stmt_bb16[i0] -> MemRef_A[o0] : 4o0 = p_4 + 4i0 };
 ; INNERMOST:            MustWriteAccess :=  [Reduction Type: +] [Scalar: 0]
 ; INNERMOST:                [p_0, p_1, p_2, p_3, p_4] -> { Stmt_bb16[i0] -> MemRef_A[o0] : 4o0 = p_4 + 4i0 };

test/ScopInfo/NonAffine/non_affine_loop_used_later.ll

 ; CHECK:    Assumed Context:
 ; CHECK:    [N] -> {  :  }
 ; CHECK:    p0: %N
 ; CHECK:    Alias Groups (0):
 ; CHECK:        n/a
 ; CHECK:    Statements {
 ; CHECK:      Stmt_bb2
 ; CHECK:            Domain :=
-; CHECK:                [N] -> { Stmt_bb2[i0] : i0 >= 0 and N >= 1 and i0 <= N; Stmt_bb2[0] : N <= 0 };
+; CHECK:                [N] -> { Stmt_bb2[i0] : i0 >= 0 and N >= 1 and i0 <= N; Stmt_bb2[0] : N <= 0 }
 ; CHECK:            Schedule :=
-; CHECK:                [N] -> { Stmt_bb2[i0] -> [i0, 0] };
+; CHECK:                [N] -> { Stmt_bb2[i0] -> [i0, 0] : i0 <= N and N >= 1; Stmt_bb2[0] -> [0, 0] : N <= 0 }
 ; CHECK:            ReadAccess := [Reduction Type: NONE] [Scalar: 1]
 ; CHECK:                [N] -> { Stmt_bb2[i0] -> MemRef_j_0[] };
 ; CHECK:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
 ; CHECK:                [N] -> { Stmt_bb2[i0] -> MemRef_j_0[] };
 ; CHECK:      Stmt_(bb4 => bb18)
 ; CHECK:            Domain :=
 ; CHECK:                [N] -> { Stmt_(bb4 => bb18)[i0] : i0 >= 0 and N >= 1 and i0 <= -1 + N };
 ; CHECK:            Schedule :=

test/ScopInfo/pointer-type-expressions.ll

 ; CHECK:  Stmt_store
 ; CHECK:        Domain :=
 ; CHECK:            [N, P] -> { Stmt_store[i0] :
 ; CHECK:              (P <= -1 and i0 >= 0 and i0 <= -1 + N)
 ; CHECK:                or
 ; CHECK:              (P >= 1 and i0 >= 0 and i0 <= -1 + N)
 ; CHECK:                   };
 ; CHECK:        Schedule :=
-; CHECK:            [N, P] -> { Stmt_store[i0] -> [i0] };
+; CHECK:            [N, P] -> { Stmt_store[i0] -> [i0] : P <= -1 or P >= 1 };
 ; CHECK:        MustWriteAccess := [Reduction Type: NONE]
 ; CHECK:            [N, P] -> { Stmt_store[i0] -> MemRef_a[i0] };