[Polly] Added support for modulo accesses

[jdoerfert]

Summary

The support is limited to signed modulo access expressions with a
constant right hand side, e.g., A[i % 2]. Test cases are modified
according to this new feature and two new test cases to test the
functionality are added. A test case for not yet supported modulo
conditions is added too.

[jdoerfert]

Updated version with more test cases

[jdoerfert]

Updated version with more test cases

[jdoerfert]

Adjustments to catch different SCEV representations of modulo expressions

[simbuerg]

I have some stylistic comments inline, the rest looks good to me.

lib/Analysis/ScopInfo.cpp

179 ↗

(On Diff #12403)

capture

188 ↗

(On Diff #12403)

Here 'auto' is ok, because I can infer the type from the context on the same line (imho).

191 ↗

(On Diff #12403)

I would use the type here instead of 'auto'.

192 ↗

(On Diff #12403)

I would use the type here instead of 'auto'.

311 ↗

(On Diff #12403)

Now you're not using 'auto', why?

lib/Support/SCEVValidator.cpp

161 ↗

(On Diff #12403)

capture

172 ↗

(On Diff #12403)

I would use the type here.

379 ↗

(On Diff #12403)

Consistency: auto?

[jdoerfert]

Thanks for the feedback,.. you're right all the time, I should be more consistent.

I'll fix everything and commit it then.

[jdoerfert]

Closed by commit rL215684 (authored by @jdoerfert).

polly/trunk/lib/Analysis/ScopInfo.cpp

 // Multiplicative reductions can be disabled seperately as these kind of
 // operations can overflow easily. Additive reductions and bit operations
 // are in contrast pretty stable.
 static cl::opt<bool> DisableMultiplicativeReductions(
     "polly-disable-multiplicative-reductions",
     cl::desc("Disable multiplicative reductions"), cl::Hidden, cl::ZeroOrMore,
     cl::init(false), cl::cat(PollyCategory));
 
+static int extractAffine(__isl_take isl_set *Set, __isl_take isl_aff *Aff,
+                         void *User) {
+  *((isl_aff **)(User)) = Aff;
+  isl_set_free(Set);
+  return 0;
+}
+
 /// Translate a 'const SCEV *' expression in an isl_pw_aff.
 struct SCEVAffinator : public SCEVVisitor<SCEVAffinator, isl_pw_aff *> {
 public:
   /// @brief Translate a 'const SCEV *' to an isl_pw_aff.
   ///
   /// @param Stmt The location at which the scalar evolution expression
   ///             is evaluated.
   /// @param Expr The expression that is translated.

 
 __isl_give isl_pw_aff *
 SCEVAffinator::visitTruncateExpr(const SCEVTruncateExpr *Expr) {
   llvm_unreachable("SCEVTruncateExpr not yet supported");
 }
 
 __isl_give isl_pw_aff *
 SCEVAffinator::visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr) {
+  ScalarEvolution &SE = *S->getSE();
+
+  const SCEV *OpS = Expr->getOperand();
+  unsigned ModCst = 1 << OpS->getType()->getScalarSizeInBits();
+
+  // Pattern matching rules to capture some bit and modulo computations:
+  //
+  //       EXP   %  2^C      <==>
+  // [A] (i + c) & (2^C - 1)  ==> zext iC {c,+,1}<%for_i> to IXX
+  // [B] (p + q) & (2^C - 1)  ==> zext iC (trunc iXX %p_add_q to iC) to iXX
+  // [C] (i + p) & (2^C - 1)  ==> zext iC {p & (2^C - 1),+,1}<%for_i> to iXX
+  //                          ==> zext iC {trunc iXX %p to iC,+,1}<%for_i> to
+
+  // Check for [A] and [C].
+  if (auto *OpAR = dyn_cast<SCEVAddRecExpr>(OpS)) {
+    assert(OpAR->getStepRecurrence(SE)->isOne());
+
+    const SCEV *OpARStart = OpAR->getStart();
+    const SCEV *OpARStep = OpAR->getStepRecurrence(SE);
+
+    // Special case for [C].
+    if (auto *OpARStartTR = dyn_cast<SCEVTruncateExpr>(OpARStart)) {
+      OpARStart = OpARStartTR->getOperand();
+      OpARStep = SE.getConstant(OpARStart->getType(), 1);
+    }
+
+    const SCEV *NewAR = SE.getAddRecExpr(OpARStart, OpARStep, OpAR->getLoop(),
+                                         OpAR->getNoWrapFlags());
+    return isl_pw_aff_mod_val(visit(NewAR), isl_val_int_from_si(Ctx, ModCst));
+  }
+
+  // Check for [B].
+  if (auto *OpTR = dyn_cast<SCEVTruncateExpr>(OpS))
+    return isl_pw_aff_mod_val(visit(OpTR->getOperand()),
+                              isl_val_int_from_si(Ctx, ModCst));
+
   llvm_unreachable("SCEVZeroExtendExpr not yet supported");
 }
 
 __isl_give isl_pw_aff *
 SCEVAffinator::visitSignExtendExpr(const SCEVSignExtendExpr *Expr) {
   // Assuming the value is signed, a sign extension is basically a noop.
   // TODO: Reconsider this as soon as we support unsigned values.
   return visit(Expr->getOperand());
__isl_give isl_pw_aff *SCEVAffinator::visitSMaxExpr(const SCEVSMaxExpr *Expr) {
   return Max;
 }
 
 __isl_give isl_pw_aff *SCEVAffinator::visitUMaxExpr(const SCEVUMaxExpr *Expr) {
   llvm_unreachable("SCEVUMaxExpr not yet supported");
 }
 
 __isl_give isl_pw_aff *SCEVAffinator::visitUnknown(const SCEVUnknown *Expr) {
-  llvm_unreachable("Unknowns are always parameters");
+  Value *Unknown = Expr->getValue();
+  if (auto *BO = dyn_cast<BinaryOperator>(Unknown)) {
+    isl_pw_aff *RHS, *LHS;
+    isl_aff *RHSAff;
+    isl_val *RHSVal;
+
+    assert(BO->getOpcode() == Instruction::SRem &&
+           "Binary operator unknowns are always signed modulo expressions");
+    LHS = visit(S->getSE()->getSCEV(BO->getOperand(0)));
+    RHS = visit(S->getSE()->getSCEV(BO->getOperand(1)));
+    assert(isl_pw_aff_is_cst(RHS) &&
+           "Modulo expressions are only valid for a constant right hand side");
+    assert(isl_pw_aff_n_piece(RHS) == 1 &&
+           "Modulo expressions are only valid for a non split right hand side");
+    isl_pw_aff_foreach_piece(RHS, extractAffine, &RHSAff);
+    assert(isl_aff_is_cst(RHSAff) &&
+           "Modulo expressions are only valid for a constant right hand side");
+    RHSVal = isl_aff_get_constant_val(RHSAff);
+
+    isl_pw_aff_free(RHS);
+    isl_aff_free(RHSAff);
+
+    return isl_pw_aff_mod_val(LHS, RHSVal);
+  }
+
+  llvm_unreachable("Unknowns are always parameters or modulo expressions");
 }
 
 int SCEVAffinator::getLoopDepth(const Loop *L) {
   Loop *outerLoop = S->getRegion().outermostLoopInRegion(const_cast<Loop *>(L));
   assert(outerLoop && "Scop does not contain this loop");
   return L->getLoopDepth() - outerLoop->getLoopDepth();
 }
 

polly/trunk/lib/Support/SCEVValidator.cpp

public:
 
   /// @brief Is the analyzed SCEV of Type PARAM.
   bool isPARAM() { return Type == SCEVType::PARAM; }
 
   /// @brief Get the parameters of this validator result.
   std::vector<const SCEV *> getParameters() { return Parameters; }
 
   /// @brief Add the parameters of Source to this result.
-  void addParamsFrom(class ValidatorResult &Source) {
+  void addParamsFrom(const ValidatorResult &Source) {
     Parameters.insert(Parameters.end(), Source.Parameters.begin(),
                       Source.Parameters.end());
   }
 
   /// @brief Merge a result.
   ///
   /// This means to merge the parameters and to set the Type to the most
   /// specific Type that matches both.
-  void merge(class ValidatorResult &ToMerge) {
+  ValidatorResult &merge(const ValidatorResult &ToMerge) {
     Type = std::max(Type, ToMerge.Type);
     addParamsFrom(ToMerge);
+    return *this;
   }
 
   void print(raw_ostream &OS) {
     switch (Type) {
     case SCEVType::INT:
       OS << "SCEVType::INT";
       break;
     case SCEVType::PARAM:
class ValidatorResult visitTruncateExpr(const SCEVTruncateExpr *Expr) {
     case SCEVType::INVALID:
       return Op;
     }
 
     llvm_unreachable("Unknown SCEVType");
   }
 
   class ValidatorResult visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr) {
-    ValidatorResult Op = visit(Expr->getOperand());
 
+    // Pattern matching rules to capture some bit and modulo computations:
+    //
+    //       EXP   %  2^C      <==>
+    // [A] (i + c) & (2^C - 1)  ==> zext iC {c,+,1}<%for_i> to IXX
+    // [B] (p + q) & (2^C - 1)  ==> zext iC (trunc iXX %p_add_q to iC) to iXX
+    // [C] (i + p) & (2^C - 1)  ==> zext iC {p & (2^C - 1),+,1}<%for_i> to iXX
+    //                          ==> zext iC {trunc iXX %p to iC,+,1}<%for_i> to
+
+    // Check for [A] and [C].
+    const SCEV *OpS = Expr->getOperand();
+    if (auto *OpAR = dyn_cast<SCEVAddRecExpr>(OpS)) {
+      const SCEV *OpARStart = OpAR->getStart();
+
+      // Special case for [C].
+      if (auto *OpARStartTR = dyn_cast<SCEVTruncateExpr>(OpARStart))
+        OpARStart = OpARStartTR->getOperand();
+
+      ValidatorResult OpARStartVR = visit(OpARStart);
+      if (OpARStartVR.isConstant() && OpAR->getStepRecurrence(SE)->isOne())
+        return OpARStartVR;
+    }
+
+    // Check for [B].
+    if (auto *OpTR = dyn_cast<SCEVTruncateExpr>(OpS)) {
+      ValidatorResult OpTRVR = visit(OpTR->getOperand());
+      if (OpTRVR.isConstant())
+        return OpTRVR;
+    }
+
+    ValidatorResult Op = visit(OpS);
     switch (Op.getType()) {
     case SCEVType::INT:
     case SCEVType::PARAM:
       // We currently do not represent a truncate expression as an affine
       // expression. If it is constant during Scop execution, we treat it as a
       // parameter.
       return ValidatorResult(SCEVType::PARAM, Expr);
     case SCEVType::IV:
if (!Expr->getType()->isIntegerTy()) {
       return ValidatorResult(SCEVType::INVALID);
     }
 
     if (isa<UndefValue>(V)) {
       DEBUG(dbgs() << "INVALID: UnknownExpr references an undef value");
       return ValidatorResult(SCEVType::INVALID);
     }
 
-    if (Instruction *I = dyn_cast<Instruction>(Expr->getValue()))
+    if (auto *I = dyn_cast<Instruction>(Expr->getValue())) {
+      if (I->getOpcode() == Instruction::SRem) {
+
+        ValidatorResult Op0 = visit(SE.getSCEV(I->getOperand(0)));
+        if (!Op0.isValid())
+          return ValidatorResult(SCEVType::INVALID);
+
+        ValidatorResult Op1 = visit(SE.getSCEV(I->getOperand(1)));
+        if (!Op1.isValid() || !Op1.isINT())
+          return ValidatorResult(SCEVType::INVALID);
+
+        Op0.merge(Op1);
+        return Op0;
+      }
+
       if (R->contains(I)) {
         DEBUG(dbgs() << "INVALID: UnknownExpr references an instruction "
                         "within the region\n");
         return ValidatorResult(SCEVType::INVALID);
       }
+    }
 
     if (BaseAddress == V) {
       DEBUG(dbgs() << "INVALID: UnknownExpr references BaseAddress\n");
       return ValidatorResult(SCEVType::INVALID);
     }
 
     return ValidatorResult(SCEVType::PARAM, Expr);
   }

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

 ; RUN: opt %loadPolly -polly-allow-nonaffine -polly-dce -polly-ast -analyze < %s | FileCheck %s
 ;
 ;    void f(int *A) {
 ;      for (int i = 0; i < 1024; i++)
-; S1:    A[i % 2] = i;
+; S1:    A[i ^ 2] = i;
 ;      for (int i = 0; i < 1024; i++)
-; S2:    A[i2] = i;
+; S2:    A[i] = 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);
 
-target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-n32-S64"
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 define void @f(i32* %A) {
 entry:
   br label %for.cond
 
-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 %S1, label %next
+  %exitcond1 = icmp ne i32 %i.0, 1024
+  br i1 %exitcond1, label %for.body, label %for.end
 
-S1:
-  %rem = srem i32 %i.0, 2
-  %arrayidx = getelementptr inbounds i32* %A, i32 %rem
+for.body:                                         ; preds = %for.cond
+  br label %S1
+
+S1:                                               ; preds = %for.body
+  %xor = xor i32 %i.0, 2
+  %idxprom = sext i32 %xor to i64
+  %arrayidx = getelementptr inbounds i32* %A, i64 %idxprom
   store i32 %i.0, i32* %arrayidx, align 4
   br label %for.inc
 
-for.inc:
+for.inc:                                          ; preds = %S1
   %inc = add nsw i32 %i.0, 1
   br label %for.cond
 
-next:
- br label %for.cond.2
+for.end:                                          ; preds = %for.cond
+  br label %for.cond2
 
-for.cond.2:
-  %i.2 = phi i32 [ 0, %next ], [ %inc.2, %for.inc.2 ]
-  %exitcond.2 = icmp ne i32 %i.2, 1024
-  br i1 %exitcond.2, label %S2, label %for.end
-
-S2:
-  %arrayidx.2 = getelementptr inbounds i32* %A, i32 %i.2
-  store i32 %i.2, i32* %arrayidx.2, align 4
-  br label %for.inc.2
-
-for.inc.2:
-  %inc.2 = add nsw i32 %i.2, 1
-  br label %for.cond.2
+for.cond2:                                        ; preds = %for.inc7, %for.end
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc7 ], [ 0, %for.end ]
+  %exitcond = icmp ne i64 %indvars.iv, 1024
+  br i1 %exitcond, label %for.body4, label %for.end9
+
+for.body4:                                        ; preds = %for.cond2
+  br label %S2
+
+S2:                                               ; preds = %for.body4
+  %arrayidx6 = getelementptr inbounds i32* %A, i64 %indvars.iv
+  %tmp = trunc i64 %indvars.iv to i32
+  store i32 %tmp, i32* %arrayidx6, align 4
+  br label %for.inc7
+
+for.inc7:                                         ; preds = %S2
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %for.cond2
 
-for.end:
+for.end9:                                         ; preds = %for.cond2
   ret void
 }
-

polly/trunk/test/DeadCodeElimination/non-affine-but-modulo-and-affine-mix.ll

+; RUN: opt %loadPolly -polly-dce -polly-ast -analyze < %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;
+;    }
+;
+; CHECK: for (int c1 = 0; c1 <= 1023; c1 += 1)
+; CHECK:   Stmt_S2(c1);
+
+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:
+  %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
+  %exitcond = icmp ne i32 %i.0, 1024
+  br i1 %exitcond, label %S1, label %next
+
+S1:
+  %rem = srem i32 %i.0, 2
+  %arrayidx = getelementptr inbounds i32* %A, i32 %rem
+  store i32 %i.0, i32* %arrayidx, align 4
+  br label %for.inc
+
+for.inc:
+  %inc = add nsw i32 %i.0, 1
+  br label %for.cond
+
+next:
+ br label %for.cond.2
+
+for.cond.2:
+  %i.2 = phi i32 [ 0, %next ], [ %inc.2, %for.inc.2 ]
+  %exitcond.2 = icmp ne i32 %i.2, 1024
+  br i1 %exitcond.2, label %S2, label %for.end
+
+S2:
+  %arrayidx.2 = getelementptr inbounds i32* %A, i32 %i.2
+  store i32 %i.2, i32* %arrayidx.2, align 4
+  br label %for.inc.2
+
+for.inc.2:
+  %inc.2 = add nsw i32 %i.2, 1
+  br label %for.cond.2
+
+for.end:
+  ret void
+}
+

polly/trunk/test/ScopDetect/non_affine_but_modulo_access.ll

+; RUN: opt %loadPolly -polly-detect -analyze < %s | FileCheck %s
+;
+; CHECK: Valid Region for Scop:
+;
+;    void jd(int *A) {
+;      for (int i = 0; i < 1024; i++)
+;        A[i % 2] = A[i % 2 + 1];
+;    }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @jd(i32* %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
+  %rem = srem i32 %i.0, 2
+  %add = add nsw i32 %rem, 1
+  %idxprom = sext i32 %add to i64
+  %arrayidx = getelementptr inbounds i32* %A, i64 %idxprom
+  %tmp = load i32* %arrayidx, align 4
+  %rem1 = srem i32 %i.0, 2
+  %idxprom2 = sext i32 %rem1 to i64
+  %arrayidx3 = getelementptr inbounds i32* %A, i64 %idxprom2
+  store i32 %tmp, i32* %arrayidx3, 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
+}

polly/trunk/test/ScopDetect/non_affine_but_modulo_condition.ll

+; RUN: opt %loadPolly -polly-detect -analyze < %s | FileCheck %s
+;
+; CHECK: jd_and
+; CHECK: Valid Region for Scop:
+; CHECK: jd_srem
+; CHECK: Valid Region for Scop:
+;
+;    void jd(int *A) {
+;      for (int i = 0; i < 1024; i++)
+;        if (i % 2)
+;          A[i] += 1;
+;    }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @jd_and(i32* %A) {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry ]
+  %exitcond = icmp ne i64 %indvars.iv, 1024
+  br i1 %exitcond, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %tmp = trunc i64 %indvars.iv to i32
+  %rem1 = and i32 %tmp, 1
+  %tobool = icmp eq i32 %rem1, 0
+  br i1 %tobool, label %if.end, label %if.then
+
+if.then:                                          ; preds = %for.body
+  %arrayidx = getelementptr inbounds i32* %A, i64 %indvars.iv
+  %tmp2 = load i32* %arrayidx, align 4
+  %add = add nsw i32 %tmp2, 1
+  store i32 %add, i32* %arrayidx, align 4
+  br label %if.end
+
+if.end:                                           ; preds = %for.body, %if.then
+  br label %for.inc
+
+for.inc:                                          ; preds = %if.end
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}
+
+define void @jd_srem(i32* %A) {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry ]
+  %exitcond = icmp ne i64 %indvars.iv, 1024
+  br i1 %exitcond, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %tmp = trunc i64 %indvars.iv to i32
+  %rem1 = srem i32 %tmp, 2
+  %tobool = icmp eq i32 %rem1, 0
+  br i1 %tobool, label %if.end, label %if.then
+
+if.then:                                          ; preds = %for.body
+  %arrayidx = getelementptr inbounds i32* %A, i64 %indvars.iv
+  %tmp2 = load i32* %arrayidx, align 4
+  %add = add nsw i32 %tmp2, 1
+  store i32 %add, i32* %arrayidx, align 4
+  br label %if.end
+
+if.end:                                           ; preds = %for.body, %if.then
+  br label %for.inc
+
+for.inc:                                          ; preds = %if.end
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}

polly/trunk/test/ScopInfo/NonAffine/indirect_array_write.ll

+; RUN: opt %loadPolly -basicaa -polly-scops -analyze -polly-allow-nonaffine < %s | FileCheck %s
+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-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+; void foo(long n, double A[], int INDEX[]) {
+;   for (long i = 0; i < n; i++)
+;     A[INDEX[i]] = i;
+; }
+
+define void @foo(i64 %n, double* noalias %A, i64* noalias %INDEX) {
+entry:
+  br label %for.body
+
+for.body:
+  %i = phi i64 [ %inc, %for.body ], [ 0, %entry ]
+  %arrayidx = getelementptr inbounds i64* %INDEX, i64 %i
+  %val = load i64* %arrayidx
+  %arrayidx1 = getelementptr inbounds double* %A, i64 %val
+  store double 1.0, double* %arrayidx1
+  %inc = add nsw i64 %i, 1
+  %exitcond = icmp eq i64 %inc, %n
+  br i1 %exitcond, label %for.end, label %for.body
+
+for.end:
+  ret void
+}
+
+; CHECK: p0: %n
+
+; CHECK: Domain
+; CHECK:   [n] -> { Stmt_for_body[i0] : i0 >= 0 and i0 <= -1 + n };
+; CHECK: Scattering
+; CHECK:   [n] -> { Stmt_for_body[i0] -> scattering[0, i0, 0] };
+; CHECK: ReadAccess
+; CHECK:   [n] -> { Stmt_for_body[i0] -> MemRef_INDEX[i0] };
+; CHECK: WriteAccess
+; CHECK:   [n] -> { Stmt_for_body[i0] -> MemRef_A[o0] };

polly/trunk/test/ScopInfo/NonAffine/non_affine_but_modulo_access_1023.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+;
+;    void jd(int *A, int c) {
+;      for (int i = 0; i < 1024; i++)
+;        A[i % 1023] = A[(i + 1) % 1023] + A[c % 1023] + A[(i - c) % 1023];
+;    }
+;
+; CHECK: ReadAccess := [Reduction Type: NONE]
+; CHECK:     [c] -> { Stmt_for_body[i0] -> MemRef_A[o0] : exists (e0 = floor((-1 - i0 + o0)/1023): 1023e0 = -1 - i0 + o0 and o0 >= 0 and o0 <= 1022) };
+; CHECK: ReadAccess := [Reduction Type: NONE]
+; CHECK:     [c] -> { Stmt_for_body[i0] -> MemRef_A[o0] : exists (e0 = floor((-c + o0)/1023): 1023e0 = -c + o0 and o0 >= 0 and o0 <= 1022) };
+; CHECK: ReadAccess := [Reduction Type: NONE]
+; CHECK:     [c] -> { Stmt_for_body[i0] -> MemRef_A[o0] : exists (e0 = floor((-1022c - i0 + o0)/1023): 1023e0 = -1022c - i0 + o0 and o0 >= 0 and o0 <= 1022) };
+; CHECK: MustWriteAccess :=  [Reduction Type: NONE]
+; CHECK:     [c] -> { Stmt_for_body[i0] -> MemRef_A[o0] : exists (e0 = floor((-i0 + o0)/1023): 1023e0 = -i0 + o0 and o0 >= 0 and o0 <= 1022) };
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @jd(i32* %A, i32 %c) {
+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
+  %add = add nsw i32 %i.0, 1
+  %rem = srem i32 %add, 1023
+  %idxprom = sext i32 %rem to i64
+  %arrayidx = getelementptr inbounds i32* %A, i64 %idxprom
+  %tmp = load i32* %arrayidx, align 4
+  %rem1 = srem i32 %c, 1023
+  %idxprom2 = sext i32 %rem1 to i64
+  %arrayidx3 = getelementptr inbounds i32* %A, i64 %idxprom2
+  %tmp1 = load i32* %arrayidx3, align 4
+  %add4 = add nsw i32 %tmp, %tmp1
+  %sub = sub nsw i32 %i.0, %c
+  %rem5 = srem i32 %sub, 1023
+  %idxprom6 = sext i32 %rem5 to i64
+  %arrayidx7 = getelementptr inbounds i32* %A, i64 %idxprom6
+  %tmp2 = load i32* %arrayidx7, align 4
+  %add8 = add nsw i32 %add4, %tmp2
+  %rem9 = srem i32 %i.0, 1023
+  %idxprom10 = sext i32 %rem9 to i64
+  %arrayidx11 = getelementptr inbounds i32* %A, i64 %idxprom10
+  store i32 %add8, i32* %arrayidx11, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body
+  %inc = add nsw i32 %i.0, 1
+  br label %for.cond
+
+for.end:
+  ret void
+}

polly/trunk/test/ScopInfo/NonAffine/non_affine_but_modulo_access_1024.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+;
+;    void jd(int *A, int c) {
+;      for (int i = 0; i < 1024; i++)
+;        A[i % 1024] = A[(i + 1) % 1024] + A[c % 1024] + A[(i - c) % 1024];
+;    }
+;
+; CHECK: ReadAccess := [Reduction Type: NONE]
+; CHECK:     [c] -> { Stmt_for_body[i0] -> MemRef_A[o0] : exists (e0 = floor((-1 - i0 + o0)/1024): 1024e0 = -1 - i0 + o0 and o0 >= 0 and o0 <= 1023) };
+; CHECK: ReadAccess := [Reduction Type: NONE]
+; CHECK:     [c] -> { Stmt_for_body[i0] -> MemRef_A[o0] : exists (e0 = floor((-c + o0)/1024): 1024e0 = -c + o0 and o0 >= 0 and o0 <= 1023) };
+; CHECK: ReadAccess := [Reduction Type: NONE]
+; CHECK:     [c] -> { Stmt_for_body[i0] -> MemRef_A[o0] : exists (e0 = floor((-1023c - i0 + o0)/1024): 1024e0 = -1023c - i0 + o0 and o0 >= 0 and o0 <= 1023) };
+; CHECK: MustWriteAccess :=  [Reduction Type: NONE]
+; CHECK:     [c] -> { Stmt_for_body[i0] -> MemRef_A[o0] : exists (e0 = floor((-i0 + o0)/1024): 1024e0 = -i0 + o0 and o0 >= 0 and o0 <= 1023) };
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @jd(i32* %A, i32 %c) {
+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
+  %add = add nsw i32 %i.0, 1
+  %rem = srem i32 %add, 1024
+  %idxprom = sext i32 %rem to i64
+  %arrayidx = getelementptr inbounds i32* %A, i64 %idxprom
+  %tmp = load i32* %arrayidx, align 4
+  %rem1 = srem i32 %c, 1024
+  %idxprom2 = sext i32 %rem1 to i64
+  %arrayidx3 = getelementptr inbounds i32* %A, i64 %idxprom2
+  %tmp1 = load i32* %arrayidx3, align 4
+  %add4 = add nsw i32 %tmp, %tmp1
+  %sub = sub nsw i32 %i.0, %c
+  %rem5 = and i32 %sub, 1023
+  %idxprom6 = sext i32 %rem5 to i64
+  %arrayidx7 = getelementptr inbounds i32* %A, i64 %idxprom6
+  %tmp2 = load i32* %arrayidx7, align 4
+  %add8 = add nsw i32 %add4, %tmp2
+  %rem9 = srem i32 %i.0, 1024
+  %idxprom10 = sext i32 %rem9 to i64
+  %arrayidx11 = getelementptr inbounds i32* %A, i64 %idxprom10
+  store i32 %add8, i32* %arrayidx11, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body
+  %inc = add nsw i32 %i.0, 1
+  br label %for.cond
+
+for.end:
+  ret void
+}

polly/trunk/test/ScopInfo/NonAffine/non_affine_but_modulo_access_2.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+;
+;    void jd(int *A) {
+;      for (int i = 0; i < 1024; i++)
+;        A[i % 2] = A[i % 2 + 1];
+;    }
+;
+; CHECK: ReadAccess := [Reduction Type: NONE]
+; CHECK:     { Stmt_for_body[i0] -> MemRef_A[o0] : exists (e0 = floor((-1 - i0 + o0)/2): 2e0 = -1 - i0 + o0 and o0 >= 1 and o0 <= 2) };
+; CHECK: MustWriteAccess :=  [Reduction Type: NONE]
+; CHECK:     { Stmt_for_body[i0] -> MemRef_A[o0] : exists (e0 = floor((-i0 + o0)/2): 2e0 = -i0 + o0 and o0 >= 0 and o0 <= 1) };
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @jd(i32* %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
+  %rem = srem i32 %i.0, 2
+  %add = add nsw i32 %rem, 1
+  %idxprom = sext i32 %add to i64
+  %arrayidx = getelementptr inbounds i32* %A, i64 %idxprom
+  %tmp = load i32* %arrayidx, align 4
+  %rem1 = and i32 %i.0, 1
+  %idxprom2 = sext i32 %rem1 to i64
+  %arrayidx3 = getelementptr inbounds i32* %A, i64 %idxprom2
+  store i32 %tmp, i32* %arrayidx3, 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
+}

polly/trunk/test/ScopInfo/NonAffine/non_affine_but_modulo_access_3.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+;
+;    void jd(int *A, int c) {
+;      for (int i = 0; i < 1024; i++)
+;        A[i % 3] = A[(i + 1) % 3] + A[c % 3] + A[(i - c) % 3];
+;    }
+;
+; CHECK: ReadAccess := [Reduction Type: NONE]
+; CHECK:     [c] -> { Stmt_for_body[i0] -> MemRef_A[o0] : exists (e0 = floor((-1 - i0 + o0)/3): 3e0 = -1 - i0 + o0 and o0 >= 0 and o0 <= 2) };
+; CHECK: ReadAccess := [Reduction Type: NONE]
+; CHECK:     [c] -> { Stmt_for_body[i0] -> MemRef_A[o0] : exists (e0 = floor((-c + o0)/3): 3e0 = -c + o0 and o0 >= 0 and o0 <= 2) };
+; CHECK: ReadAccess := [Reduction Type: NONE]
+; CHECK:     [c] -> { Stmt_for_body[i0] -> MemRef_A[o0] : exists (e0 = floor((-2c - i0 + o0)/3): 3e0 = -2c - i0 + o0 and o0 >= 0 and o0 <= 2) };
+; CHECK: MustWriteAccess :=  [Reduction Type: NONE]
+; CHECK:     [c] -> { Stmt_for_body[i0] -> MemRef_A[o0] : exists (e0 = floor((-i0 + o0)/3): 3e0 = -i0 + o0 and o0 >= 0 and o0 <= 2) };
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @jd(i32* %A, i32 %c) {
+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
+  %add = add nsw i32 %i.0, 1
+  %rem = srem i32 %add, 3
+  %idxprom = sext i32 %rem to i64
+  %arrayidx = getelementptr inbounds i32* %A, i64 %idxprom
+  %tmp = load i32* %arrayidx, align 4
+  %rem1 = srem i32 %c, 3
+  %idxprom2 = sext i32 %rem1 to i64
+  %arrayidx3 = getelementptr inbounds i32* %A, i64 %idxprom2
+  %tmp1 = load i32* %arrayidx3, align 4
+  %add4 = add nsw i32 %tmp, %tmp1
+  %sub = sub nsw i32 %i.0, %c
+  %rem5 = srem i32 %sub, 3
+  %idxprom6 = sext i32 %rem5 to i64
+  %arrayidx7 = getelementptr inbounds i32* %A, i64 %idxprom6
+  %tmp2 = load i32* %arrayidx7, align 4
+  %add8 = add nsw i32 %add4, %tmp2
+  %rem9 = srem i32 %i.0, 3
+  %idxprom10 = sext i32 %rem9 to i64
+  %arrayidx11 = getelementptr inbounds i32* %A, i64 %idxprom10
+  store i32 %add8, i32* %arrayidx11, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body
+  %inc = add nsw i32 %i.0, 1
+  br label %for.cond
+
+for.end:
+  ret void
+}

polly/trunk/test/ScopInfo/NonAffine/non_affine_but_modulo_access_4.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+;
+;    void jd(int *A, int c) {
+;      for (int i = 0; i < 1024; i++)
+;        A[i % 4] = A[(i + 1) % 4] + A[c % 4] + A[(i - c) % 4];
+;    }
+;
+; CHECK: ReadAccess := [Reduction Type: NONE]
+; CHECK:     [c] -> { Stmt_for_body[i0] -> MemRef_A[o0] : exists (e0 = floor((-1 - i0 + o0)/4): 4e0 = -1 - i0 + o0 and o0 >= 0 and o0 <= 3) };
+; CHECK: ReadAccess := [Reduction Type: NONE]
+; CHECK:     [c] -> { Stmt_for_body[i0] -> MemRef_A[o0] : exists (e0 = floor((-c + o0)/4): 4e0 = -c + o0 and o0 >= 0 and o0 <= 3) };
+; CHECK: ReadAccess := [Reduction Type: NONE]
+; CHECK:     [c] -> { Stmt_for_body[i0] -> MemRef_A[o0] : exists (e0 = floor((-3c - i0 + o0)/4): 4e0 = -3c - i0 + o0 and o0 >= 0 and o0 <= 3) };
+; CHECK: MustWriteAccess :=  [Reduction Type: NONE]
+; CHECK:     [c] -> { Stmt_for_body[i0] -> MemRef_A[o0] : exists (e0 = floor((-i0 + o0)/4): 4e0 = -i0 + o0 and o0 >= 0 and o0 <= 3) };
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @jd(i32* %A, i32 %c) {
+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
+  %add = add nsw i32 %i.0, 1
+  %rem = srem i32 %add, 4
+  %idxprom = sext i32 %rem to i64
+  %arrayidx = getelementptr inbounds i32* %A, i64 %idxprom
+  %tmp = load i32* %arrayidx, align 4
+  %rem1 = srem i32 %c, 4
+  %idxprom2 = sext i32 %rem1 to i64
+  %arrayidx3 = getelementptr inbounds i32* %A, i64 %idxprom2
+  %tmp1 = load i32* %arrayidx3, align 4
+  %add4 = add nsw i32 %tmp, %tmp1
+  %sub = sub nsw i32 %i.0, %c
+  %rem5 = srem i32 %sub, 4
+  %idxprom6 = sext i32 %rem5 to i64
+  %arrayidx7 = getelementptr inbounds i32* %A, i64 %idxprom6
+  %tmp2 = load i32* %arrayidx7, align 4
+  %add8 = add nsw i32 %add4, %tmp2
+  %rem9 = srem i32 %i.0, 4
+  %idxprom10 = sext i32 %rem9 to i64
+  %arrayidx11 = getelementptr inbounds i32* %A, i64 %idxprom10
+  store i32 %add8, i32* %arrayidx11, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body
+  %inc = add nsw i32 %i.0, 1
+  br label %for.cond
+
+for.end:
+  ret void
+}

polly/trunk/test/ScopInfo/NonAffine/non_affine_but_modulo_access_5.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+;
+;    void jd(int *A, int c) {
+;      for (int i = 0; i < 1024; i++)
+;        A[i % 5] = A[(i + 1) % 5] + A[c % 5] + A[(i - c) % 5];
+;    }
+;
+; CHECK: ReadAccess := [Reduction Type: NONE]
+; CHECK:     [c] -> { Stmt_for_body[i0] -> MemRef_A[o0] : exists (e0 = floor((-1 - i0 + o0)/5): 5e0 = -1 - i0 + o0 and o0 >= 0 and o0 <= 4) };
+; CHECK: ReadAccess := [Reduction Type: NONE]
+; CHECK:     [c] -> { Stmt_for_body[i0] -> MemRef_A[o0] : exists (e0 = floor((-c + o0)/5): 5e0 = -c + o0 and o0 >= 0 and o0 <= 4) };
+; CHECK: ReadAccess := [Reduction Type: NONE]
+; CHECK:     [c] -> { Stmt_for_body[i0] -> MemRef_A[o0] : exists (e0 = floor((-4c - i0 + o0)/5): 5e0 = -4c - i0 + o0 and o0 >= 0 and o0 <= 4) };
+; CHECK: MustWriteAccess :=  [Reduction Type: NONE]
+; CHECK:     [c] -> { Stmt_for_body[i0] -> MemRef_A[o0] : exists (e0 = floor((-i0 + o0)/5): 5e0 = -i0 + o0 and o0 >= 0 and o0 <= 4) };
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @jd(i32* %A, i32 %c) {
+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
+  %add = add nsw i32 %i.0, 1
+  %rem = srem i32 %add, 5
+  %idxprom = sext i32 %rem to i64
+  %arrayidx = getelementptr inbounds i32* %A, i64 %idxprom
+  %tmp = load i32* %arrayidx, align 4
+  %rem1 = srem i32 %c, 5
+  %idxprom2 = sext i32 %rem1 to i64
+  %arrayidx3 = getelementptr inbounds i32* %A, i64 %idxprom2
+  %tmp1 = load i32* %arrayidx3, align 4
+  %add4 = add nsw i32 %tmp, %tmp1
+  %sub = sub nsw i32 %i.0, %c
+  %rem5 = srem i32 %sub, 5
+  %idxprom6 = sext i32 %rem5 to i64
+  %arrayidx7 = getelementptr inbounds i32* %A, i64 %idxprom6
+  %tmp2 = load i32* %arrayidx7, align 4
+  %add8 = add nsw i32 %add4, %tmp2
+  %rem9 = srem i32 %i.0, 5
+  %idxprom10 = sext i32 %rem9 to i64
+  %arrayidx11 = getelementptr inbounds i32* %A, i64 %idxprom10
+  store i32 %add8, i32* %arrayidx11, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body
+  %inc = add nsw i32 %i.0, 1
+  br label %for.cond
+
+for.end:
+  ret void
+}

polly/trunk/test/ScopInfo/NonAffine/non_affine_but_modulo_access_6.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+;
+;    void jd(int *A, int c) {
+;      for (int i = 0; i < 1024; i++)
+;        A[i % 6] = A[(i + 1) % 6] + A[c % 6] + A[(i - c) % 6];
+;    }
+;
+; CHECK: ReadAccess := [Reduction Type: NONE]
+; CHECK:     [c] -> { Stmt_for_body[i0] -> MemRef_A[o0] : exists (e0 = floor((-1 - i0 + o0)/6): 6e0 = -1 - i0 + o0 and o0 >= 0 and o0 <= 5) };
+; CHECK: ReadAccess := [Reduction Type: NONE]
+; CHECK:     [c] -> { Stmt_for_body[i0] -> MemRef_A[o0] : exists (e0 = floor((-c + o0)/6): 6e0 = -c + o0 and o0 >= 0 and o0 <= 5) };
+; CHECK: ReadAccess := [Reduction Type: NONE]
+; CHECK:     [c] -> { Stmt_for_body[i0] -> MemRef_A[o0] : exists (e0 = floor((-5c - i0 + o0)/6): 6e0 = -5c - i0 + o0 and o0 >= 0 and o0 <= 5) };
+; CHECK: MustWriteAccess :=  [Reduction Type: NONE]
+; CHECK:     [c] -> { Stmt_for_body[i0] -> MemRef_A[o0] : exists (e0 = floor((-i0 + o0)/6): 6e0 = -i0 + o0 and o0 >= 0 and o0 <= 5) };
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @jd(i32* %A, i32 %c) {
+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
+  %add = add nsw i32 %i.0, 1
+  %rem = srem i32 %add, 6
+  %idxprom = sext i32 %rem to i64
+  %arrayidx = getelementptr inbounds i32* %A, i64 %idxprom
+  %tmp = load i32* %arrayidx, align 4
+  %rem1 = srem i32 %c, 6
+  %idxprom2 = sext i32 %rem1 to i64
+  %arrayidx3 = getelementptr inbounds i32* %A, i64 %idxprom2
+  %tmp1 = load i32* %arrayidx3, align 4
+  %add4 = add nsw i32 %tmp, %tmp1
+  %sub = sub nsw i32 %i.0, %c
+  %rem5 = srem i32 %sub, 6
+  %idxprom6 = sext i32 %rem5 to i64
+  %arrayidx7 = getelementptr inbounds i32* %A, i64 %idxprom6
+  %tmp2 = load i32* %arrayidx7, align 4
+  %add8 = add nsw i32 %add4, %tmp2
+  %rem9 = srem i32 %i.0, 6
+  %idxprom10 = sext i32 %rem9 to i64
+  %arrayidx11 = getelementptr inbounds i32* %A, i64 %idxprom10
+  store i32 %add8, i32* %arrayidx11, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body
+  %inc = add nsw i32 %i.0, 1
+  br label %for.cond
+
+for.end:
+  ret void
+}

polly/trunk/test/ScopInfo/NonAffine/non_affine_but_modulo_access_8.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+;
+;    void jd(int *A, int c) {
+;      for (int i = 0; i < 1024; i++)
+;        A[i % 8] = A[(i + 1) % 8] + A[c % 8] + A[(i - c) % 8];
+;    }
+;
+; CHECK: ReadAccess := [Reduction Type: NONE]
+; CHECK:     [c] -> { Stmt_for_body[i0] -> MemRef_A[o0] : exists (e0 = floor((-1 - i0 + o0)/8): 8e0 = -1 - i0 + o0 and o0 >= 0 and o0 <= 7) };
+; CHECK: ReadAccess := [Reduction Type: NONE]
+; CHECK:     [c] -> { Stmt_for_body[i0] -> MemRef_A[o0] : exists (e0 = floor((-c + o0)/8): 8e0 = -c + o0 and o0 >= 0 and o0 <= 7) };
+; CHECK: ReadAccess := [Reduction Type: NONE]
+; CHECK:     [c] -> { Stmt_for_body[i0] -> MemRef_A[o0] : exists (e0 = floor((-7c - i0 + o0)/8): 8e0 = -7c - i0 + o0 and o0 >= 0 and o0 <= 7) };
+; CHECK: MustWriteAccess :=  [Reduction Type: NONE]
+; CHECK:     [c] -> { Stmt_for_body[i0] -> MemRef_A[o0] : exists (e0 = floor((-i0 + o0)/8): 8e0 = -i0 + o0 and o0 >= 0 and o0 <= 7) };
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @jd(i32* %A, i32 %c) {
+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
+  %add = add nsw i32 %i.0, 1
+  %rem = and i32 %add, 7
+  %idxprom = sext i32 %rem to i64
+  %arrayidx = getelementptr inbounds i32* %A, i64 %idxprom
+  %tmp = load i32* %arrayidx, align 4
+  %rem1 = and i32 %c, 7
+  %idxprom2 = sext i32 %rem1 to i64
+  %arrayidx3 = getelementptr inbounds i32* %A, i64 %idxprom2
+  %tmp1 = load i32* %arrayidx3, align 4
+  %add4 = add nsw i32 %tmp, %tmp1
+  %sub = sub nsw i32 %i.0, %c
+  %rem5 = and i32 %sub, 7
+  %idxprom6 = sext i32 %rem5 to i64
+  %arrayidx7 = getelementptr inbounds i32* %A, i64 %idxprom6
+  %tmp2 = load i32* %arrayidx7, align 4
+  %add8 = add nsw i32 %add4, %tmp2
+  %rem9 = and i32 %i.0, 7
+  %idxprom10 = sext i32 %rem9 to i64
+  %arrayidx11 = getelementptr inbounds i32* %A, i64 %idxprom10
+  store i32 %add8, i32* %arrayidx11, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body
+  %inc = add nsw i32 %i.0, 1
+  br label %for.cond
+
+for.end:
+  ret void
+}

polly/trunk/test/ScopInfo/NonAffine/non_affine_but_modulo_condition_2.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+;
+;    void jd(int *A) {
+;      for (int i = 0; i < 1024; i++)
+;        if (i % 2)
+;          A[i] += 1;
+;    }
+;
+; CHECK: Function: jd_and
+; CHECK:   Stmt_if_then
+; CHECK:     Domain :=
+; CHECK:         { Stmt_if_then[i0] : exists (e0 = floor((-1 + i0)/2): 2e0 = -1 + i0 and i0 >= 0 and i0 <= 1023) };
+; CHECK:     Scattering :=
+; CHECK:         { Stmt_if_then[i0] -> scattering[0, i0, 0] };
+; CHECK:     ReadAccess := [Reduction Type: +]
+; CHECK:         { Stmt_if_then[i0] -> MemRef_A[i0] };
+; CHECK:     MustWriteAccess :=  [Reduction Type: +]
+; CHECK:         { Stmt_if_then[i0] -> MemRef_A[i0] };
+;
+; CHECK: Function: jd_srem
+; CHECK:   Stmt_if_then
+; CHECK:     Domain :=
+; CHECK:         { Stmt_if_then[i0] : exists (e0 = floor((-1 + i0)/2): 2e0 = -1 + i0 and i0 >= 0 and i0 <= 1023) };
+; CHECK:     Scattering :=
+; CHECK:         { Stmt_if_then[i0] -> scattering[0, i0, 0] };
+; CHECK:     ReadAccess := [Reduction Type: +]
+; CHECK:         { Stmt_if_then[i0] -> MemRef_A[i0] };
+; CHECK:     MustWriteAccess :=  [Reduction Type: +]
+; CHECK:         { Stmt_if_then[i0] -> MemRef_A[i0] };
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @jd_and(i32* %A) {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry ]
+  %exitcond = icmp ne i64 %indvars.iv, 1024
+  br i1 %exitcond, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %tmp = trunc i64 %indvars.iv to i32
+  %rem1 = and i32 %tmp, 1
+  %tobool = icmp eq i32 %rem1, 0
+  br i1 %tobool, label %if.end, label %if.then
+
+if.then:                                          ; preds = %for.body
+  %arrayidx = getelementptr inbounds i32* %A, i64 %indvars.iv
+  %tmp2 = load i32* %arrayidx, align 4
+  %add = add nsw i32 %tmp2, 1
+  store i32 %add, i32* %arrayidx, align 4
+  br label %if.end
+
+if.end:                                           ; preds = %for.body, %if.then
+  br label %for.inc
+
+for.inc:                                          ; preds = %if.end
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}
+
+define void @jd_srem(i32* %A) {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry ]
+  %exitcond = icmp ne i64 %indvars.iv, 1024
+  br i1 %exitcond, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %tmp = trunc i64 %indvars.iv to i32
+  %rem1 = srem i32 %tmp, 2
+  %tobool = icmp eq i32 %rem1, 0
+  br i1 %tobool, label %if.end, label %if.then
+
+if.then:                                          ; preds = %for.body
+  %arrayidx = getelementptr inbounds i32* %A, i64 %indvars.iv
+  %tmp2 = load i32* %arrayidx, align 4
+  %add = add nsw i32 %tmp2, 1
+  store i32 %add, i32* %arrayidx, align 4
+  br label %if.end
+
+if.end:                                           ; preds = %for.body, %if.then
+  br label %for.inc
+
+for.inc:                                          ; preds = %if.end
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}

polly/trunk/test/ScopInfo/NonAffine/non_affine_but_modulo_condition_3.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+;
+;    void jd(int *A) {
+;      for (int i = 0; i < 1024; i++)
+;        if (i % 3)
+;          A[i] += 1;
+;    }
+;
+; CHECK: Function: jd_srem
+; CHECK:   Stmt_if_then
+; CHECK:     Domain :=
+; CHECK:         { Stmt_if_then[i0] : exists (e0 = floor((i0)/3): i0 >= 0 and i0 <= 1023 and 3e0 <= -1 + i0 and 3e0 >= -2 + i0) };
+; CHECK:     Scattering :=
+; CHECK:         { Stmt_if_then[i0] -> scattering[0, i0, 0] };
+; CHECK:     ReadAccess := [Reduction Type: +]
+; CHECK:         { Stmt_if_then[i0] -> MemRef_A[i0] };
+; CHECK:     MustWriteAccess :=  [Reduction Type: +]
+; CHECK:         { Stmt_if_then[i0] -> MemRef_A[i0] };
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @jd_srem(i32* %A) {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry ]
+  %exitcond = icmp ne i64 %indvars.iv, 1024
+  br i1 %exitcond, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %rem = srem i64 %indvars.iv, 3
+  %tobool = icmp eq i64 %rem, 0
+  br i1 %tobool, label %if.end, label %if.then
+
+if.then:                                          ; preds = %for.body
+  %arrayidx = getelementptr inbounds i32* %A, i64 %indvars.iv
+  %tmp2 = load i32* %arrayidx, align 4
+  %add = add nsw i32 %tmp2, 1
+  store i32 %add, i32* %arrayidx, align 4
+  br label %if.end
+
+if.end:                                           ; preds = %for.body, %if.then
+  br label %for.inc
+
+for.inc:                                          ; preds = %if.end
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}

polly/trunk/test/ScopInfo/NonAffine/non_affine_but_modulo_condition_4.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+;
+;    void jd(int *A) {
+;      for (int i = 0; i < 1024; i++)
+;        if (i % 4)
+;          A[i] += 1;
+;    }
+;
+; CHECK: Function: jd_and
+; CHECK:   Stmt_if_then
+; CHECK:     Domain :=
+; CHECK:         { Stmt_if_then[i0] : exists (e0 = floor((i0)/4): i0 >= 0 and i0 <= 1023 and 4e0 <= -1 + i0 and 4e0 >= -3 + i0) };
+; CHECK:     Scattering :=
+; CHECK:         { Stmt_if_then[i0] -> scattering[0, i0, 0] };
+; CHECK:     ReadAccess := [Reduction Type: +]
+; CHECK:         { Stmt_if_then[i0] -> MemRef_A[i0] };
+; CHECK:     MustWriteAccess :=  [Reduction Type: +]
+; CHECK:         { Stmt_if_then[i0] -> MemRef_A[i0] };
+;
+; CHECK: Function: jd_srem
+; CHECK:   Stmt_if_then
+; CHECK:     Domain :=
+; CHECK:         { Stmt_if_then[i0] : exists (e0 = floor((i0)/4): i0 >= 0 and i0 <= 1023 and 4e0 <= -1 + i0 and 4e0 >= -3 + i0) };
+; CHECK:     Scattering :=
+; CHECK:         { Stmt_if_then[i0] -> scattering[0, i0, 0] };
+; CHECK:     ReadAccess := [Reduction Type: +]
+; CHECK:         { Stmt_if_then[i0] -> MemRef_A[i0] };
+; CHECK:     MustWriteAccess :=  [Reduction Type: +]
+; CHECK:         { Stmt_if_then[i0] -> MemRef_A[i0] };
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @jd_and(i32* %A) {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry ]
+  %exitcond = icmp ne i64 %indvars.iv, 1024
+  br i1 %exitcond, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %tmp = trunc i64 %indvars.iv to i32
+  %rem1 = and i32 %tmp, 3
+  %tobool = icmp eq i32 %rem1, 0
+  br i1 %tobool, label %if.end, label %if.then
+
+if.then:                                          ; preds = %for.body
+  %arrayidx = getelementptr inbounds i32* %A, i64 %indvars.iv
+  %tmp2 = load i32* %arrayidx, align 4
+  %add = add nsw i32 %tmp2, 1
+  store i32 %add, i32* %arrayidx, align 4
+  br label %if.end
+
+if.end:                                           ; preds = %for.body, %if.then
+  br label %for.inc
+
+for.inc:                                          ; preds = %if.end
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}
+
+define void @jd_srem(i32* %A) {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry ]
+  %exitcond = icmp ne i64 %indvars.iv, 1024
+  br i1 %exitcond, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %rem = srem i64 %indvars.iv, 4
+  %tobool = icmp eq i64 %rem, 0
+  br i1 %tobool, label %if.end, label %if.then
+
+if.then:                                          ; preds = %for.body
+  %arrayidx = getelementptr inbounds i32* %A, i64 %indvars.iv
+  %tmp2 = load i32* %arrayidx, align 4
+  %add = add nsw i32 %tmp2, 1
+  store i32 %add, i32* %arrayidx, align 4
+  br label %if.end
+
+if.end:                                           ; preds = %for.body, %if.then
+  br label %for.inc
+
+for.inc:                                          ; preds = %if.end
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}

polly/trunk/test/ScopInfo/NonAffine/non_affine_but_modulo_condition_5.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+;
+;    void jd(int *A) {
+;      for (int i = 0; i < 1024; i++)
+;        if (i % 5)
+;          A[i] += 1;
+;    }
+;
+; CHECK: Function: jd_srem
+; CHECK:   Stmt_if_then
+; CHECK:     Domain :=
+; CHECK:         { Stmt_if_then[i0] : exists (e0 = floor((i0)/5): i0 >= 0 and i0 <= 1023 and 5e0 <= -1 + i0 and 5e0 >= -4 + i0) };
+; CHECK:     Scattering :=
+; CHECK:         { Stmt_if_then[i0] -> scattering[0, i0, 0] };
+; CHECK:     ReadAccess := [Reduction Type: +]
+; CHECK:         { Stmt_if_then[i0] -> MemRef_A[i0] };
+; CHECK:     MustWriteAccess :=  [Reduction Type: +]
+; CHECK:         { Stmt_if_then[i0] -> MemRef_A[i0] };
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @jd_srem(i32* %A) {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry ]
+  %exitcond = icmp ne i64 %indvars.iv, 1024
+  br i1 %exitcond, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %rem = srem i64 %indvars.iv, 5
+  %tobool = icmp eq i64 %rem, 0
+  br i1 %tobool, label %if.end, label %if.then
+
+if.then:                                          ; preds = %for.body
+  %arrayidx = getelementptr inbounds i32* %A, i64 %indvars.iv
+  %tmp2 = load i32* %arrayidx, align 4
+  %add = add nsw i32 %tmp2, 1
+  store i32 %add, i32* %arrayidx, align 4
+  br label %if.end
+
+if.end:                                           ; preds = %for.body, %if.then
+  br label %for.inc
+
+for.inc:                                          ; preds = %if.end
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}

polly/trunk/test/ScopInfo/NonAffine/non_affine_but_modulo_condition_8.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+;
+;    void jd(int *A) {
+;      for (int i = 0; i < 1024; i++)
+;        if (i % 8)
+;          A[i] += 1;
+;    }
+;
+; CHECK: Function: jd_and
+; CHECK:   Stmt_if_then
+; CHECK:     Domain :=
+; CHECK:         { Stmt_if_then[i0] : exists (e0 = floor((i0)/8): i0 >= 0 and i0 <= 1023 and 8e0 <= -1 + i0 and 8e0 >= -7 + i0) };
+; CHECK:     Scattering :=
+; CHECK:         { Stmt_if_then[i0] -> scattering[0, i0, 0] };
+; CHECK:     ReadAccess := [Reduction Type: +]
+; CHECK:         { Stmt_if_then[i0] -> MemRef_A[i0] };
+; CHECK:     MustWriteAccess :=  [Reduction Type: +]
+; CHECK:         { Stmt_if_then[i0] -> MemRef_A[i0] };
+;
+; CHECK: Function: jd_srem
+; CHECK:   Stmt_if_then
+; CHECK:     Domain :=
+; CHECK:         { Stmt_if_then[i0] : exists (e0 = floor((i0)/8): i0 >= 0 and i0 <= 1023 and 8e0 <= -1 + i0 and 8e0 >= -7 + i0) };
+; CHECK:     Scattering :=
+; CHECK:         { Stmt_if_then[i0] -> scattering[0, i0, 0] };
+; CHECK:     ReadAccess := [Reduction Type: +]
+; CHECK:         { Stmt_if_then[i0] -> MemRef_A[i0] };
+; CHECK:     MustWriteAccess :=  [Reduction Type: +]
+; CHECK:         { Stmt_if_then[i0] -> MemRef_A[i0] };
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @jd_and(i32* %A) {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry ]
+  %exitcond = icmp ne i64 %indvars.iv, 1024
+  br i1 %exitcond, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %tmp = trunc i64 %indvars.iv to i32
+  %rem1 = and i32 %tmp, 7
+  %tobool = icmp eq i32 %rem1, 0
+  br i1 %tobool, label %if.end, label %if.then
+
+if.then:                                          ; preds = %for.body
+  %arrayidx = getelementptr inbounds i32* %A, i64 %indvars.iv
+  %tmp2 = load i32* %arrayidx, align 4
+  %add = add nsw i32 %tmp2, 1
+  store i32 %add, i32* %arrayidx, align 4
+  br label %if.end
+
+if.end:                                           ; preds = %for.body, %if.then
+  br label %for.inc
+
+for.inc:                                          ; preds = %if.end
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}
+
+define void @jd_srem(i32* %A) {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry ]
+  %exitcond = icmp ne i64 %indvars.iv, 1024
+  br i1 %exitcond, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %rem = srem i64 %indvars.iv, 8
+  %tobool = icmp eq i64 %rem, 0
+  br i1 %tobool, label %if.end, label %if.then
+
+if.then:                                          ; preds = %for.body
+  %arrayidx = getelementptr inbounds i32* %A, i64 %indvars.iv
+  %tmp2 = load i32* %arrayidx, align 4
+  %add = add nsw i32 %tmp2, 1
+  store i32 %add, i32* %arrayidx, align 4
+  br label %if.end
+
+if.end:                                           ; preds = %for.body, %if.then
+  br label %for.inc
+
+for.inc:                                          ; preds = %if.end
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}

polly/trunk/test/ScopInfo/non_affine_parametric_loop.ll

-; RUN: opt %loadPolly -basicaa -polly-scops -analyze -polly-allow-nonaffine < %s | FileCheck %s
-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-S128"
-target triple = "x86_64-unknown-linux-gnu"
-
-; void foo(long n, double A[], int INDEX[]) {
-;   for (long i = 0; i < n; i++)
-;     A[INDEX[i]] = i;
-; }
-
-define void @foo(i64 %n, double* noalias %A, i64* noalias %INDEX) {
-entry:
-  br label %for.body
-
-for.body:
-  %i = phi i64 [ %inc, %for.body ], [ 0, %entry ]
-  %arrayidx = getelementptr inbounds i64* %INDEX, i64 %i
-  %val = load i64* %arrayidx
-  %arrayidx1 = getelementptr inbounds double* %A, i64 %val
-  store double 1.0, double* %arrayidx1
-  %inc = add nsw i64 %i, 1
-  %exitcond = icmp eq i64 %inc, %n
-  br i1 %exitcond, label %for.end, label %for.body
-
-for.end:
-  ret void
-}
-
-; CHECK: p0: %n
-
-; CHECK: Domain
-; CHECK:   [n] -> { Stmt_for_body[i0] : i0 >= 0 and i0 <= -1 + n };
-; CHECK: Scattering
-; CHECK:   [n] -> { Stmt_for_body[i0] -> scattering[0, i0, 0] };
-; CHECK: ReadAccess
-; CHECK:   [n] -> { Stmt_for_body[i0] -> MemRef_INDEX[i0] };
-; CHECK: WriteAccess
-; CHECK:   [n] -> { Stmt_for_body[i0] -> MemRef_A[o0] };

polly/trunk/test/ScopInfo/reduction_alternating_base.ll

 ; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
 ;
-; FIXME: We cannot detect this SCoP yet but as soon as we can we should check
-;        that the reduction is detected!
-;
-; CHECK-NOT: Scattering
+; CHECK: ReadAccess := [Reduction Type: +]
+; CHECK:   { Stmt_for_body[i0] -> MemRef_A[o0] : exists (e0 = floor((-i0 + o0)/2): 2e0 = -i0 + o0 and o0 <= 1 and o0 >= 0) };
+; CHECK: MustWriteAccess :=  [Reduction Type: +]
+; CHECK:   { Stmt_for_body[i0] -> MemRef_A[o0] : exists (e0 = floor((-i0 + o0)/2): 2e0 = -i0 + o0 and o0 <= 1 and o0 >= 0) };
 ;
 ;    void f(int *A) {
 ;      for (int i = 0; i < 1024; i++)
 ;        A[i % 2] += i;
 ;    }
 ;
 target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-n32-S64"