[Polly] Added support for modulo expressions

[jdoerfert]

Summary

The support is limited to signed modulo access and condition
expressions with a constant right hand side, e.g., A[i % 2] or
A[i % 9]. Test cases are modified according to this new feature and
new test cases are added.

[jdoerfert]

rebased

[grosser]

I looked through the test files and I have the feeling there is a some redundancy. For example, the following files are identical, except for the constants used:

non_affine_but_modulo_access_1023.ll
non_affine_but_modulo_access_3.ll
non_affine_but_modulo_access_4.ll
non_affine_but_modulo_access_5.ll
non_affine_but_modulo_access_6.ll

non_affine_but_modulo_loop_bound_constant_7.ll
non_affine_but_modulo_loop_bound_constant_9.ll
non_affine_but_modulo_loop_bound_parameter.ll

non_affine_but_modulo_condition_3.ll
non_affine_but_modulo_condition_5.ll

non_affine_but_modulo_condition_4.ll
non_affine_but_modulo_condition_8.ll

Test coverage in general is good, but my feeling is that these tests may not increase test coverage, but rather distract from the test that cover the relevant cases.

lib/Analysis/ScopInfo.cpp

76

This would not be needed, if we just focus on constants in the RHS. (see below)

192

This can be folded into the if below.

201

This can be folded into the if above.

207

The operand of this truncate expression and correspondingly the dividend of this remainder operation can become negative. It may be worth a test case (example attached) and a comment on why aff_mod_val models this pattern
correctly despite the fact that for negative dividends of the srem expression, it is not the right choice.

negative-dividend-in-and-modulo.ll3 KBDownload

310

I like the idea of extending our analysis across unknowns. This is indeed a very nice approach.

326

This is a lot of code, just to get a constant. Assuming we run an instruction simplification pass before Polly, can it really happen that RHS is not an explicit constant? If we assume the RHS is always a constant, we could simplify this by directly converting BO->getOperand(1) to an isl_pw_aff.

Also, as previously discussed, the use of isl's aff_mod_val() is incorrect for cases where the LHS is negative, as the semantics of isl_aff_mod and srem differ.

lib/Support/SCEVValidator.cpp

98

The change of the return type does not seem to be used in this patch.

Moving class -> const is an obvious improvement. As it is unrelated to the patch, I would suggest to commit it directly as "obvious".

386

It would be nice to add a corresponding DEBUG statement to this INVALID instruction, which explains why the statement is refused (this is done consistently in this class).

389

Is the "!Op1.isValid() ||" part here needed?

Also, the patch refuses this piece of code which was previously accepted:

void foo(float *A, long a, long b) {
	for (long i = 0; i < (a % b); i++)
		A[i] = 1;
}

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

9

Great that you preserve this file.

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

15

Maybe make this a CHECK-NOT: Stmt_S1?

test/ScopDetect/non_affine_but_modulo_access.ll

7

Nice that we can detect this now!

test/ScopInfo/NonAffine/indirect_array_write.ll

8

Is this in any way related to modulos? If not and this just makes the filename more understandable, this could be committed separately.

test/ScopInfo/NonAffine/non_affine_but_modulo_condition_8.ll

14

The test cases fail ATM for me, because of the additional '0's in the scattering

test/ScopInfo/NonAffine/non_affine_but_modulo_loop_bound_constant_7.ll

16

Interesting. I like this test case.

test/ScopInfo/reduction_alternating_base.ll

12

Nice!

[jdoerfert]

I added some comments and will change than patch accordingly. I will also split two smaller parts and remove some test cases for which I unfortunately can't remember the exact reason I added them. Anyway, thanks for the review.

lib/Analysis/ScopInfo.cpp

207

I'll add that.

326

The second concern is important and I will correct that. Regarding the first, I'm not sure, maybe if we check this in the ScopDetection we can just assume a constant RHS here. I'm not sure which is better and do not have any arguments for one or another, so we should just choose one. (Or we do a isa<ConstantInt>(BO->getOperand(1)) here?)

lib/Support/SCEVValidator.cpp

98

This was an artifact (I used it at some point but apperently I changed it again). I will commit the const part and forget about the return type

386

I can change this to return Op0 if to make it clear that the DEBUG message was already produced in the recursive step.
Or did I miss something?

389

Good points. I'll address both.

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

15

Agreed.

test/ScopInfo/NonAffine/non_affine_but_modulo_condition_8.ll

14

I'll change it ...

[grosser]

In D5293#113209, @jdoerfert wrote:

I added some comments and will change than patch accordingly. I will also split two smaller parts and remove some test cases for which I unfortunately can't remember the exact reason I added them. Anyway, thanks for the review.

Hi Johannes,

I updated and committed a first part of this patch in r240518 containing only the support for the srem instruction and incorporating the changes we discussed here.

Best,
Tobias

[grosser]

Hi Johannes,

I am still waiting for feedback on this patch. I already added some of the code into Polly, but especially the power-of-two test cases do not work yet and would be worth adding. In case you find time to complete this patch, this would be great.

[grosser]

Hi Johannes,

as you did not update this patch since a while, it seems to not be of interest at the moment. To clean up my patch review log I remove myself as a reviewer. Feel free to add me again when you get back to this.

Best,
Tobias

lib/Analysis/ScopInfo.cpp

static cl::opt<bool> DisableMultiplicativeReductions(
     cl::desc("Disable multiplicative reductions"), cl::Hidden, cl::ZeroOrMore,
     cl::init(false), cl::cat(PollyCategory));
 
 static cl::opt<unsigned> RunTimeChecksMaxParameters(
     "polly-rtc-max-parameters",
     cl::desc("The maximal number of parameters allowed in RTCs."), cl::Hidden,
     cl::ZeroOrMore, cl::init(8), 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();
 }
 

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:
       OS << "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)) {
+      if (R->contains(OpAR->getLoop())) {
+        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() || Expr->getType()->isPointerTy())) {
       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);
   }

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

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

-; RUN: opt %loadPolly -polly-allow-nonaffine -polly-dce -polly-ast -analyze < %s | FileCheck %s
+; 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;
 ;    }
-
-; 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"
 
 define void @f(i32* %A) {
 entry:
   br label %for.cond

test/ScopDetect/non_affine_but_modulo_access.ll

-; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+; RUN: opt %loadPolly -polly-detect -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: Valid Region for Scop:
 ;
-; CHECK-NOT: Scattering
-;
-;    void f(int *A) {
+;    void jd(int *A) {
 ;      for (int i = 0; i < 1024; i++)
-;        A[i % 2] += i;
+;        A[i % 2] = A[i % 2 + 1];
 ;    }
 ;
-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) {
+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
-  %arrayidx = getelementptr inbounds i32* %A, i32 %rem
+  %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
-  %add = add nsw i32 %tmp, %i.0
-  store i32 %add, 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
 }

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

test/ScopInfo/NonAffine/non_affine_but_modulo_loop_bound_constant_7.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+;
+; FIXME:
+;   Negative test since independent blocks will cause Scalar Evolution
+;   to fail recognizing the inner loop bound.
+; TODO:
+;   Use the loop bounds before independent blocks instead of failing.
+;
+; CHECK-NOT: Function: jd
+;
+;    void jd(int *A) {
+;      for (int i = 0; i < 1024; i++)
+;        for (int j = 0; j < i % 7; j++)
+;          A[i] = 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.inc4, %entry
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc4 ], [ 0, %entry ]
+  %exitcond = icmp ne i64 %indvars.iv, 1024
+  br i1 %exitcond, label %for.body, label %for.end6
+
+for.body:                                         ; preds = %for.cond
+  %rem = srem i64 %indvars.iv, 7
+  br label %for.cond1
+
+for.cond1:                                        ; preds = %for.inc, %for.body
+  %j.0 = phi i64 [ 0, %for.body ], [ %inc, %for.inc ]
+  %cmp2 = icmp slt i64 %j.0, %rem
+  br i1 %cmp2, label %for.body3, label %for.end
+
+for.body3:                                        ; preds = %for.cond1
+  %arrayidx = getelementptr inbounds i32* %A, i64 %indvars.iv
+  store i32 1, i32* %arrayidx, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body3
+  %inc = add nsw i64 %j.0, 1
+  br label %for.cond1
+
+for.end:                                          ; preds = %for.cond1
+  br label %for.inc4
+
+for.inc4:                                         ; preds = %for.end
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %for.cond
+
+for.end6:                                         ; preds = %for.cond
+  ret void
+}

test/ScopInfo/NonAffine/non_affine_but_modulo_loop_bound_constant_8.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+;
+; CHECK: Stmt_for_body3
+; CHECK:   Domain :=
+; CHECK:       { Stmt_for_body3[i0, i1] : exists (e0 = floor((i0)/8): i0 >= 0 and i0 <= 1023 and i1 >= 0 and 8e0 <= i0 and 8e0 >= -7 + i0 and 8e0 <= -1 + i0 - i1) };
+; CHECK:   Scattering :=
+; CHECK:       { Stmt_for_body3[i0, i1] -> scattering[0, i0, 0, i1, 0] };
+; CHECK:   MustWriteAccess :=  [Reduction Type: NONE]
+; CHECK:       { Stmt_for_body3[i0, i1] -> MemRef_A[i0] };
+;
+;    void jd(int *A) {
+;      for (int i = 0; i < 1024; i++)
+;        for (int j = 0; j < i % 8; j++)
+;          A[i] = 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.inc4, %entry
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc4 ], [ 0, %entry ]
+  %exitcond = icmp ne i64 %indvars.iv, 1024
+  br i1 %exitcond, label %for.body, label %for.end6
+
+for.body:                                         ; preds = %for.cond
+  %rem = and i64 %indvars.iv, 7
+  br label %for.cond1
+
+for.cond1:                                        ; preds = %for.inc, %for.body
+  %j.0 = phi i64 [ 0, %for.body ], [ %inc, %for.inc ]
+  %cmp2 = icmp slt i64 %j.0, %rem
+  br i1 %cmp2, label %for.body3, label %for.end
+
+for.body3:                                        ; preds = %for.cond1
+  %arrayidx = getelementptr inbounds i32* %A, i64 %indvars.iv
+  store i32 1, i32* %arrayidx, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body3
+  %inc = add nsw i64 %j.0, 1
+  br label %for.cond1
+
+for.end:                                          ; preds = %for.cond1
+  br label %for.inc4
+
+for.inc4:                                         ; preds = %for.end
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %for.cond
+
+for.end6:                                         ; preds = %for.cond
+  ret void
+}

test/ScopInfo/NonAffine/non_affine_but_modulo_loop_bound_constant_9.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+;
+; FIXME:
+;   Negative test since independent blocks will cause Scalar Evolution
+;   to fail recognizing the inner loop bound.
+; TODO:
+;   Use the loop bounds before independent blocks instead of failing.
+;
+; CHECK-NOT: Function: jd
+;
+;    void jd(int *A) {
+;      for (int i = 0; i < 1024; i++)
+;        for (int j = 0; j < i % 9; j++)
+;          A[i] = 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.inc4, %entry
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc4 ], [ 0, %entry ]
+  %exitcond = icmp ne i64 %indvars.iv, 1024
+  br i1 %exitcond, label %for.body, label %for.end6
+
+for.body:                                         ; preds = %for.cond
+  %rem = srem i64 %indvars.iv, 9
+  br label %for.cond1
+
+for.cond1:                                        ; preds = %for.inc, %for.body
+  %j.0 = phi i64 [ 0, %for.body ], [ %inc, %for.inc ]
+  %cmp2 = icmp slt i64 %j.0, %rem
+  br i1 %cmp2, label %for.body3, label %for.end
+
+for.body3:                                        ; preds = %for.cond1
+  %arrayidx = getelementptr inbounds i32* %A, i64 %indvars.iv
+  store i32 1, i32* %arrayidx, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body3
+  %inc = add nsw i64 %j.0, 1
+  br label %for.cond1
+
+for.end:                                          ; preds = %for.cond1
+  br label %for.inc4
+
+for.inc4:                                         ; preds = %for.end
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %for.cond
+
+for.end6:                                         ; preds = %for.cond
+  ret void
+}

test/ScopInfo/NonAffine/non_affine_but_modulo_loop_bound_parameter.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+;
+; FIXME:
+;   Negative test since independent blocks will cause Scalar Evolution
+;   to fail recognizing the inner loop bound.
+; TODO:
+;   Use the loop bounds before independent blocks instead of failing.
+;
+; CHECK-NOT: Function: jd
+;
+;    void jd(int *A, int c) {
+;      for (int i = 0; i < 1024; i++)
+;        for (int j = 0; j < i % c; j++)
+;          A[i] = 1;
+;    }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @jd(i32* %A, i64 %c) {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc4, %entry
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc4 ], [ 0, %entry ]
+  %exitcond = icmp ne i64 %indvars.iv, 1024
+  br i1 %exitcond, label %for.body, label %for.end6
+
+for.body:                                         ; preds = %for.cond
+  %rem = srem i64 %indvars.iv, %c
+  br label %for.cond1
+
+for.cond1:                                        ; preds = %for.inc, %for.body
+  %j.0 = phi i64 [ 0, %for.body ], [ %inc, %for.inc ]
+  %cmp2 = icmp slt i64 %j.0, %rem
+  br i1 %cmp2, label %for.body3, label %for.end
+
+for.body3:                                        ; preds = %for.cond1
+  %arrayidx = getelementptr inbounds i32* %A, i64 %indvars.iv
+  store i32 1, i32* %arrayidx, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body3
+  %inc = add nsw i64 %j.0, 1
+  br label %for.cond1
+
+for.end:                                          ; preds = %for.cond1
+  br label %for.inc4
+
+for.inc4:                                         ; preds = %for.end
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %for.cond
+
+for.end6:                                         ; preds = %for.cond
+  ret void
+}

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[i0] };
-; CHECK: ReadAccess
-; CHECK:   [n] -> { Stmt_for_body[i0] -> MemRef_INDEX[i0] };
-; CHECK: WriteAccess
-; CHECK:   [n] -> { Stmt_for_body[i0] -> MemRef_A[o0] };

test/ScopInfo/outer_loop_add_rec_zext.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+;
+; Verify that we do not mistakenly assume the zero extend expression in the
+; loop bound is a modulo expression. It is not (or not equivalent) since the
+; loop %for.cond is outside the SCoP.
+;
+; CHECK: Region: %for.cond1---%for.end
+; CHECK: p0: (zext i32 {-2,+,1}<%for.cond> to i64)
+;
+;    void f();
+;    void jd(int *A) {
+;      for (int i = 0; i < 1024; i++) {
+;        for (int j = 0; j < (unsinged long)i; j++)
+;          A[j] = 1;
+;        f();
+;      }
+;    }
+;
+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.inc4, %entry
+  %indvars.iv1 = phi i32 [ %indvars.iv.next2, %for.inc4 ], [ 0, %entry ]
+  %indvars.iv12 = add i32 %indvars.iv1, -2
+  %indvars.iv1.zext = zext i32 %indvars.iv12 to i64
+  %indvars.iv1.zext2 = add i64 %indvars.iv1.zext, 1
+  %exitcond3 = icmp ne i32 %indvars.iv1, 1024
+  br i1 %exitcond3, label %for.body, label %for.end6
+
+for.body:                                         ; preds = %for.cond
+  br label %for.cond1
+
+for.cond1:                                        ; preds = %for.inc, %for.body
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %for.body ]
+  br label %for.body3
+
+for.body3:                                        ; preds = %for.cond1
+  %arrayidx = getelementptr inbounds i32* %A, i64 %indvars.iv
+  store i32 1, i32* %arrayidx, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body3
+  %indvars.iv.next = add i64 %indvars.iv, 1
+  %exitcond = icmp ne i64 %indvars.iv.next, %indvars.iv1.zext2
+  br i1 %exitcond, label %for.cond1, label %for.end
+
+for.end:                                          ; preds = %for.cond1
+  call void (...)* @f() #2
+  br label %for.inc4
+
+for.inc4:                                         ; preds = %for.end
+  %indvars.iv.next2 = add i32 %indvars.iv1, 1
+  br label %for.cond
+
+for.end6:                                         ; preds = %for.cond
+  ret void
+}
+
+declare void @f(...)

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"
 
 define void @f(i32* %A) {
 entry:
   br label %for.cond
 
 for.cond:                                         ; preds = %for.inc, %entry
   %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]