Index: lib/Analysis/ScopInfo.cpp =================================================================== --- lib/Analysis/ScopInfo.cpp +++ lib/Analysis/ScopInfo.cpp @@ -63,6 +63,13 @@ 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 { public: @@ -164,6 +171,43 @@ __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 capute 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(OpS)) { + assert(OpAR->getStepRecurrence(SE)->isOne()); + + auto *OpARStart = OpAR->getStart(); + auto *OpARStep = OpAR->getStepRecurrence(SE); + + // Special case for [C]. + if (auto *OpARStartTR = dyn_cast(OpARStart)) { + OpARStart = OpARStartTR->getOperand(); + OpARStep = SE.getConstant(OpARStart->getType(), 1); + } + + auto *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(OpS)) + return isl_pw_aff_mod_val(visit(OpTR->getOperand()), + isl_val_int_from_si(Ctx, ModCst)); + llvm_unreachable("SCEVZeroExtendExpr not yet supported"); } @@ -263,7 +307,32 @@ } __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(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) { Index: lib/Support/SCEVValidator.cpp =================================================================== --- lib/Support/SCEVValidator.cpp +++ lib/Support/SCEVValidator.cpp @@ -82,7 +82,7 @@ std::vector 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()); } @@ -91,9 +91,10 @@ /// /// 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) { @@ -156,8 +157,37 @@ } class ValidatorResult visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr) { - ValidatorResult Op = visit(Expr->getOperand()); + // Pattern matching rules to capute 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(OpS)) { + auto *OpARStart = OpAR->getStart(); + + // Special case for [C]. + if (auto *OpARStartTR = dyn_cast(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(OpS)) { + ValidatorResult OpTRVR = visit(OpTR->getOperand()); + if (OpTRVR.isConstant()) + return OpTRVR; + } + + ValidatorResult Op = visit(OpS); switch (Op.getType()) { case SCEVType::INT: case SCEVType::PARAM: @@ -346,12 +376,27 @@ return ValidatorResult(SCEVType::INVALID); } - if (Instruction *I = dyn_cast(Expr->getValue())) + if (Instruction *I = dyn_cast(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"); Index: test/DeadCodeElimination/non-affine-affine-mix.ll =================================================================== --- test/DeadCodeElimination/non-affine-affine-mix.ll +++ test/DeadCodeElimination/non-affine-affine-mix.ll @@ -2,9 +2,9 @@ ; ; 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 @@ -16,45 +16,52 @@ ; 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.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.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 +for.body4: ; preds = %for.cond2 + br label %S2 -S2: - %arrayidx.2 = getelementptr inbounds i32* %A, i32 %i.2 - store i32 %i.2, i32* %arrayidx.2, align 4 - br label %for.inc.2 +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.inc.2: - %inc.2 = add nsw i32 %i.2, 1 - br label %for.cond.2 +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 } - Index: test/DeadCodeElimination/non-affine-but-modulo-and-affine-mix.ll =================================================================== --- test/DeadCodeElimination/non-affine-but-modulo-and-affine-mix.ll +++ test/DeadCodeElimination/non-affine-but-modulo-and-affine-mix.ll @@ -1,4 +1,4 @@ -; 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++) @@ -6,13 +6,7 @@ ; 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); Index: test/ScopDetect/non_affine_but_modulo_access.ll =================================================================== --- test/ScopDetect/non_affine_but_modulo_access.ll +++ test/ScopDetect/non_affine_but_modulo_access.ll @@ -1,18 +1,15 @@ -; 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 @@ -23,10 +20,14 @@ 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 Index: test/ScopDetect/non_affine_but_modulo_condition.ll =================================================================== --- /dev/null +++ test/ScopDetect/non_affine_but_modulo_condition.ll @@ -0,0 +1,80 @@ +; 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 +} Index: test/ScopInfo/NonAffine/non_affine_but_modulo_access_1023.ll =================================================================== --- /dev/null +++ test/ScopInfo/NonAffine/non_affine_but_modulo_access_1023.ll @@ -0,0 +1,57 @@ +; 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 +} Index: test/ScopInfo/NonAffine/non_affine_but_modulo_access_1024.ll =================================================================== --- /dev/null +++ test/ScopInfo/NonAffine/non_affine_but_modulo_access_1024.ll @@ -0,0 +1,57 @@ +; 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 +} Index: test/ScopInfo/NonAffine/non_affine_but_modulo_access_2.ll =================================================================== --- /dev/null +++ test/ScopInfo/NonAffine/non_affine_but_modulo_access_2.ll @@ -0,0 +1,42 @@ +; 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 +} Index: test/ScopInfo/NonAffine/non_affine_but_modulo_access_3.ll =================================================================== --- /dev/null +++ test/ScopInfo/NonAffine/non_affine_but_modulo_access_3.ll @@ -0,0 +1,57 @@ +; 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 +} Index: test/ScopInfo/NonAffine/non_affine_but_modulo_access_4.ll =================================================================== --- /dev/null +++ test/ScopInfo/NonAffine/non_affine_but_modulo_access_4.ll @@ -0,0 +1,57 @@ +; 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 +} Index: test/ScopInfo/NonAffine/non_affine_but_modulo_access_5.ll =================================================================== --- /dev/null +++ test/ScopInfo/NonAffine/non_affine_but_modulo_access_5.ll @@ -0,0 +1,57 @@ +; 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 +} Index: test/ScopInfo/NonAffine/non_affine_but_modulo_access_6.ll =================================================================== --- /dev/null +++ test/ScopInfo/NonAffine/non_affine_but_modulo_access_6.ll @@ -0,0 +1,57 @@ +; 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 +} Index: test/ScopInfo/NonAffine/non_affine_but_modulo_access_8.ll =================================================================== --- /dev/null +++ test/ScopInfo/NonAffine/non_affine_but_modulo_access_8.ll @@ -0,0 +1,57 @@ +; 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 +} Index: test/ScopInfo/NonAffine/non_affine_but_modulo_condition_2.ll =================================================================== --- /dev/null +++ test/ScopInfo/NonAffine/non_affine_but_modulo_condition_2.ll @@ -0,0 +1,97 @@ +; 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 +} Index: test/ScopInfo/NonAffine/non_affine_but_modulo_condition_3.ll =================================================================== --- /dev/null +++ test/ScopInfo/NonAffine/non_affine_but_modulo_condition_3.ll @@ -0,0 +1,52 @@ +; 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 +} Index: test/ScopInfo/NonAffine/non_affine_but_modulo_condition_4.ll =================================================================== --- /dev/null +++ test/ScopInfo/NonAffine/non_affine_but_modulo_condition_4.ll @@ -0,0 +1,96 @@ +; 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 +} Index: test/ScopInfo/NonAffine/non_affine_but_modulo_condition_5.ll =================================================================== --- /dev/null +++ test/ScopInfo/NonAffine/non_affine_but_modulo_condition_5.ll @@ -0,0 +1,52 @@ +; 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 +} Index: test/ScopInfo/NonAffine/non_affine_but_modulo_condition_8.ll =================================================================== --- /dev/null +++ test/ScopInfo/NonAffine/non_affine_but_modulo_condition_8.ll @@ -0,0 +1,96 @@ +; 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 +} Index: test/ScopInfo/non_affine_parametric_loop.ll =================================================================== --- /dev/null +++ test/ScopInfo/non_affine_parametric_loop.ll @@ -1,37 +0,0 @@ -; RUN: opt %loadPolly -basicaa -polly-scops -analyze -polly-allow-nonaffine < %s | FileCheck %s -target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128" -target triple = "x86_64-unknown-linux-gnu" - -; void foo(long n, double A[], int INDEX[]) { -; for (long i = 0; i < n; i++) -; A[INDEX[i]] = i; -; } - -define void @foo(i64 %n, double* noalias %A, i64* noalias %INDEX) { -entry: - br label %for.body - -for.body: - %i = phi i64 [ %inc, %for.body ], [ 0, %entry ] - %arrayidx = getelementptr inbounds i64* %INDEX, i64 %i - %val = load i64* %arrayidx - %arrayidx1 = getelementptr inbounds double* %A, i64 %val - store double 1.0, double* %arrayidx1 - %inc = add nsw i64 %i, 1 - %exitcond = icmp eq i64 %inc, %n - br i1 %exitcond, label %for.end, label %for.body - -for.end: - ret void -} - -; CHECK: p0: %n - -; CHECK: Domain -; CHECK: [n] -> { Stmt_for_body[i0] : i0 >= 0 and i0 <= -1 + n }; -; CHECK: Scattering -; CHECK: [n] -> { Stmt_for_body[i0] -> scattering[0, i0, 0] }; -; CHECK: ReadAccess -; CHECK: [n] -> { Stmt_for_body[i0] -> MemRef_INDEX[i0] }; -; CHECK: WriteAccess -; CHECK: [n] -> { Stmt_for_body[i0] -> MemRef_A[o0] }; Index: test/ScopInfo/reduction_alternating_base.ll =================================================================== --- test/ScopInfo/reduction_alternating_base.ll +++ test/ScopInfo/reduction_alternating_base.ll @@ -1,9 +1,9 @@ ; 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++)