[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

capture

188

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

191

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

192

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

292

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

lib/Support/SCEVValidator.cpp

173

capture

184

I would use the type here.

361–375

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).

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) {
+
+  // Explicitly check for expressions of the following form:
+  //   i % 2^C
+  // which could either be a srem (%) expressions or an and (&) expressions.
+  // The srem (%) versions are caught by visitUnknown, the and (&) versions
+  // are expressed as
+  //   zext iC {0,+,1}<%for_i>
+  // by scalar evolution.
+  const SCEV *OpS = Expr->getOperand();
+  if (auto *OpAR = dyn_cast<SCEVAddRecExpr>(OpS)) {
+    if (OpAR->getStart()->isZero() &&
+        OpAR->getStepRecurrence(*S->getSE())->isOne()) {
+      unsigned ModCst = 1 << OpAR->getType()->getScalarSizeInBits();
+      return isl_pw_aff_mod_val(visitAddRecExpr(OpAR),
+                                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 (BinaryOperator *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

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());
+    const SCEV *OpS = Expr->getOperand();
+    ValidatorResult Op = visit(OpS);
+
+    // Explicitly check for expressions of the following form:
+    //   i % 2^C
+    // which could either be a srem (%) expressions or an and (&) expressions.
+    // The srem (%) versions are caught by visitUnknown, the and (&) versions
+    // are expressed as
+    //   zext iC {0,+,1}<%for_i>
+    // by scalar evolution.
+    if (auto *OpAR = dyn_cast<SCEVAddRecExpr>(OpS))
+      if (OpAR->getStart()->isZero() && OpAR->getStepRecurrence(SE)->isOne())
+        return Op;
 
     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:
       DEBUG(dbgs() << "INVALID: ZeroExtend of SCEVType::IV expression");
       return ValidatorResult(SCEVType::INVALID);
     case SCEVType::INVALID:
       return Op;
     }
 
     llvm_unreachable("Unknown SCEVType");
   }
 
   class ValidatorResult visitSignExtendExpr(const SCEVSignExtendExpr *Expr) {
     // We currently allow only signed SCEV expressions. In the case of a
     // signed value, a sign extend is a noop.
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 (Instruction *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/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/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/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/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/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/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/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/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/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/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/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"