diff options
21 files changed, 1161 insertions, 34 deletions
diff --git a/polly/lib/Analysis/ScopInfo.cpp b/polly/lib/Analysis/ScopInfo.cpp index 963aa80bdd5..50d5ac5f90c 100644 --- a/polly/lib/Analysis/ScopInfo.cpp +++ b/polly/lib/Analysis/ScopInfo.cpp @@ -63,6 +63,13 @@ static cl::opt<bool> DisableMultiplicativeReductions( 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: @@ -164,6 +171,42 @@ SCEVAffinator::visitTruncateExpr(const SCEVTruncateExpr *Expr) { __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"); } @@ -263,7 +306,32 @@ __isl_give isl_pw_aff *SCEVAffinator::visitUMaxExpr(const SCEVUMaxExpr *Expr) { } __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) { diff --git a/polly/lib/Support/SCEVValidator.cpp b/polly/lib/Support/SCEVValidator.cpp index 3a8895f6cad..e11c9e09fcf 100644 --- a/polly/lib/Support/SCEVValidator.cpp +++ b/polly/lib/Support/SCEVValidator.cpp @@ -82,7 +82,7 @@ public: 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()); } @@ -91,9 +91,10 @@ public: /// /// 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 @@ public: } class ValidatorResult visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr) { - ValidatorResult Op = visit(Expr->getOperand()); + // Pattern matching rules to capture some bit and modulo computations: + // + // EXP % 2^C <==> + // [A] (i + c) & (2^C - 1) ==> zext iC {c,+,1}<%for_i> to IXX + // [B] (p + q) & (2^C - 1) ==> zext iC (trunc iXX %p_add_q to iC) to iXX + // [C] (i + p) & (2^C - 1) ==> zext iC {p & (2^C - 1),+,1}<%for_i> to iXX + // ==> zext iC {trunc iXX %p to iC,+,1}<%for_i> to + + // Check for [A] and [C]. + const SCEV *OpS = Expr->getOperand(); + if (auto *OpAR = dyn_cast<SCEVAddRecExpr>(OpS)) { + const SCEV *OpARStart = OpAR->getStart(); + + // Special case for [C]. + if (auto *OpARStartTR = dyn_cast<SCEVTruncateExpr>(OpARStart)) + OpARStart = OpARStartTR->getOperand(); + + ValidatorResult OpARStartVR = visit(OpARStart); + if (OpARStartVR.isConstant() && OpAR->getStepRecurrence(SE)->isOne()) + return OpARStartVR; + } + + // Check for [B]. + if (auto *OpTR = dyn_cast<SCEVTruncateExpr>(OpS)) { + ValidatorResult OpTRVR = visit(OpTR->getOperand()); + if (OpTRVR.isConstant()) + return OpTRVR; + } + + ValidatorResult Op = visit(OpS); switch (Op.getType()) { case SCEVType::INT: case SCEVType::PARAM: @@ -346,12 +376,27 @@ public: 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"); diff --git a/polly/test/DeadCodeElimination/non-affine-affine-mix.ll b/polly/test/DeadCodeElimination/non-affine-affine-mix.ll index 24b04a14084..c4880211f3d 100644 --- a/polly/test/DeadCodeElimination/non-affine-affine-mix.ll +++ b/polly/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 } - diff --git a/polly/test/DeadCodeElimination/non-affine-but-modulo-and-affine-mix.ll b/polly/test/DeadCodeElimination/non-affine-but-modulo-and-affine-mix.ll new file mode 100644 index 00000000000..85638a3169b --- /dev/null +++ b/polly/test/DeadCodeElimination/non-affine-but-modulo-and-affine-mix.ll @@ -0,0 +1,54 @@ +; RUN: opt %loadPolly -polly-dce -polly-ast -analyze < %s | FileCheck %s +; +; void f(int *A) { +; for (int i = 0; i < 1024; i++) +; S1: A[i % 2] = i; +; for (int i = 0; i < 1024; i++) +; S2: A[i2] = i; +; } +; +; CHECK: for (int c1 = 0; c1 <= 1023; c1 += 1) +; CHECK: Stmt_S2(c1); + +target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-n32-S64" + +define void @f(i32* %A) { +entry: + br label %for.cond + +for.cond: + %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ] + %exitcond = icmp ne i32 %i.0, 1024 + br i1 %exitcond, label %S1, label %next + +S1: + %rem = srem i32 %i.0, 2 + %arrayidx = getelementptr inbounds i32* %A, i32 %rem + store i32 %i.0, i32* %arrayidx, align 4 + br label %for.inc + +for.inc: + %inc = add nsw i32 %i.0, 1 + br label %for.cond + +next: + br label %for.cond.2 + +for.cond.2: + %i.2 = phi i32 [ 0, %next ], [ %inc.2, %for.inc.2 ] + %exitcond.2 = icmp ne i32 %i.2, 1024 + br i1 %exitcond.2, label %S2, label %for.end + +S2: + %arrayidx.2 = getelementptr inbounds i32* %A, i32 %i.2 + store i32 %i.2, i32* %arrayidx.2, align 4 + br label %for.inc.2 + +for.inc.2: + %inc.2 = add nsw i32 %i.2, 1 + br label %for.cond.2 + +for.end: + ret void +} + diff --git a/polly/test/ScopDetect/non_affine_but_modulo_access.ll b/polly/test/ScopDetect/non_affine_but_modulo_access.ll new file mode 100644 index 00000000000..3c04af58774 --- /dev/null +++ b/polly/test/ScopDetect/non_affine_but_modulo_access.ll @@ -0,0 +1,39 @@ +; RUN: opt %loadPolly -polly-detect -analyze < %s | FileCheck %s +; +; CHECK: Valid Region for Scop: +; +; void jd(int *A) { +; for (int i = 0; i < 1024; i++) +; A[i % 2] = A[i % 2 + 1]; +; } +; +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" + +define void @jd(i32* %A) { +entry: + br label %for.cond + +for.cond: ; preds = %for.inc, %entry + %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ] + %exitcond = icmp ne i32 %i.0, 1024 + br i1 %exitcond, label %for.body, label %for.end + +for.body: ; preds = %for.cond + %rem = srem i32 %i.0, 2 + %add = add nsw i32 %rem, 1 + %idxprom = sext i32 %add to i64 + %arrayidx = getelementptr inbounds i32* %A, i64 %idxprom + %tmp = load i32* %arrayidx, align 4 + %rem1 = srem i32 %i.0, 2 + %idxprom2 = sext i32 %rem1 to i64 + %arrayidx3 = getelementptr inbounds i32* %A, i64 %idxprom2 + store i32 %tmp, i32* %arrayidx3, align 4 + br label %for.inc + +for.inc: ; preds = %for.body + %inc = add nsw i32 %i.0, 1 + br label %for.cond + +for.end: ; preds = %for.cond + ret void +} diff --git a/polly/test/ScopDetect/non_affine_but_modulo_condition.ll b/polly/test/ScopDetect/non_affine_but_modulo_condition.ll new file mode 100644 index 00000000000..f09be356eb2 --- /dev/null +++ b/polly/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 +} diff --git a/polly/test/ScopInfo/non_affine_parametric_loop.ll b/polly/test/ScopInfo/NonAffine/indirect_array_write.ll index 766fe9e648e..766fe9e648e 100644 --- a/polly/test/ScopInfo/non_affine_parametric_loop.ll +++ b/polly/test/ScopInfo/NonAffine/indirect_array_write.ll diff --git a/polly/test/ScopInfo/NonAffine/non_affine_but_modulo_access_1023.ll b/polly/test/ScopInfo/NonAffine/non_affine_but_modulo_access_1023.ll new file mode 100644 index 00000000000..d7cd4eebabe --- /dev/null +++ b/polly/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 +} diff --git a/polly/test/ScopInfo/NonAffine/non_affine_but_modulo_access_1024.ll b/polly/test/ScopInfo/NonAffine/non_affine_but_modulo_access_1024.ll new file mode 100644 index 00000000000..aea22a601f3 --- /dev/null +++ b/polly/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 +} diff --git a/polly/test/ScopInfo/NonAffine/non_affine_but_modulo_access_2.ll b/polly/test/ScopInfo/NonAffine/non_affine_but_modulo_access_2.ll new file mode 100644 index 00000000000..c2aa5121043 --- /dev/null +++ b/polly/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 +} diff --git a/polly/test/ScopInfo/NonAffine/non_affine_but_modulo_access_3.ll b/polly/test/ScopInfo/NonAffine/non_affine_but_modulo_access_3.ll new file mode 100644 index 00000000000..b86924007d2 --- /dev/null +++ b/polly/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 +} diff --git a/polly/test/ScopInfo/NonAffine/non_affine_but_modulo_access_4.ll b/polly/test/ScopInfo/NonAffine/non_affine_but_modulo_access_4.ll new file mode 100644 index 00000000000..99472020af8 --- /dev/null +++ b/polly/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 +} diff --git a/polly/test/ScopInfo/NonAffine/non_affine_but_modulo_access_5.ll b/polly/test/ScopInfo/NonAffine/non_affine_but_modulo_access_5.ll new file mode 100644 index 00000000000..7cdb23c794e --- /dev/null +++ b/polly/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 +} diff --git a/polly/test/ScopInfo/NonAffine/non_affine_but_modulo_access_6.ll b/polly/test/ScopInfo/NonAffine/non_affine_but_modulo_access_6.ll new file mode 100644 index 00000000000..b23208d1571 --- /dev/null +++ b/polly/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 +} diff --git a/polly/test/ScopInfo/NonAffine/non_affine_but_modulo_access_8.ll b/polly/test/ScopInfo/NonAffine/non_affine_but_modulo_access_8.ll new file mode 100644 index 00000000000..b5a92349007 --- /dev/null +++ b/polly/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 +} diff --git a/polly/test/ScopInfo/NonAffine/non_affine_but_modulo_condition_2.ll b/polly/test/ScopInfo/NonAffine/non_affine_but_modulo_condition_2.ll new file mode 100644 index 00000000000..9a9e02e6d94 --- /dev/null +++ b/polly/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 +} diff --git a/polly/test/ScopInfo/NonAffine/non_affine_but_modulo_condition_3.ll b/polly/test/ScopInfo/NonAffine/non_affine_but_modulo_condition_3.ll new file mode 100644 index 00000000000..bdef141f40e --- /dev/null +++ b/polly/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 +} diff --git a/polly/test/ScopInfo/NonAffine/non_affine_but_modulo_condition_4.ll b/polly/test/ScopInfo/NonAffine/non_affine_but_modulo_condition_4.ll new file mode 100644 index 00000000000..d6470d8795c --- /dev/null +++ b/polly/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 +} diff --git a/polly/test/ScopInfo/NonAffine/non_affine_but_modulo_condition_5.ll b/polly/test/ScopInfo/NonAffine/non_affine_but_modulo_condition_5.ll new file mode 100644 index 00000000000..856c156ca36 --- /dev/null +++ b/polly/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 +} diff --git a/polly/test/ScopInfo/NonAffine/non_affine_but_modulo_condition_8.ll b/polly/test/ScopInfo/NonAffine/non_affine_but_modulo_condition_8.ll new file mode 100644 index 00000000000..b8a35dcac62 --- /dev/null +++ b/polly/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 +} diff --git a/polly/test/ScopInfo/reduction_alternating_base.ll b/polly/test/ScopInfo/reduction_alternating_base.ll index ce98f01c4aa..0c3c4e2d6d6 100644 --- a/polly/test/ScopInfo/reduction_alternating_base.ll +++ b/polly/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++) |
