Index: include/polly/LinkAllPasses.h =================================================================== --- include/polly/LinkAllPasses.h +++ include/polly/LinkAllPasses.h @@ -54,7 +54,6 @@ llvm::Pass *createTempScopInfoPass(); #ifdef SCOPLIB_FOUND -llvm::Pass *createPoccPass(); llvm::Pass *createScopLibExporterPass(); llvm::Pass *createScopLibImporterPass(); #endif @@ -101,7 +100,6 @@ polly::createTempScopInfoPass(); #ifdef SCOPLIB_FOUND - polly::createPoccPass(); polly::createScopLibExporterPass(); polly::createScopLibImporterPass(); #endif @@ -126,9 +124,6 @@ void initializePlutoOptimizerPass(llvm::PassRegistry &); #endif void initializePollyCanonicalizePass(llvm::PassRegistry &); -#ifdef SCOPLIB_FOUND -void initializePoccPass(llvm::PassRegistry &); -#endif void initializePollyIndVarSimplifyPass(llvm::PassRegistry &); } 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,24 @@ __isl_give isl_pw_aff * SCEVAffinator::visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr) { + + // Explicitly check for expressions of the following form: + // i % 2^C + // which could either be a srem (%) expressions or an and (&) expressions. + // The srem (%) versions are caught by visitUnknown, the and (&) versions + // are expressed as + // zext iC {0,+,1}<%for_i> + // by scalar evolution. + const SCEV *OpS = Expr->getOperand(); + if (auto *OpAR = dyn_cast(OpS)) { + if (OpAR->getStart()->isZero() && + OpAR->getStepRecurrence(*S->getSE())->isOne()) { + unsigned ModCst = 1 << OpAR->getType()->getScalarSizeInBits(); + return isl_pw_aff_mod_val(visitAddRecExpr(OpAR), + isl_val_int_from_si(Ctx, ModCst)); + } + } + llvm_unreachable("SCEVZeroExtendExpr not yet supported"); } @@ -263,7 +288,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/CMakeLists.txt =================================================================== --- lib/CMakeLists.txt +++ lib/CMakeLists.txt @@ -28,7 +28,6 @@ if (SCOPLIB_FOUND) set(POLLY_SCOPLIB_FILES - Transform/Pocc.cpp Exchange/ScopLib.cpp Exchange/ScopLibExporter.cpp Exchange/ScopLibImporter.cpp) Index: lib/Makefile =================================================================== --- lib/Makefile +++ lib/Makefile @@ -34,8 +34,7 @@ ifeq ($(SCOPLIB_FOUND), yes) POLLY_SCOPLIB_FILES= Exchange/ScopLib.cpp \ Exchange/ScopLibExporter.cpp \ - Exchange/ScopLibImporter.cpp \ - Transform/Pocc.cpp + Exchange/ScopLibImporter.cpp endif ISL_CODEGEN_FILES= CodeGen/IslAst.cpp \ Index: lib/Support/RegisterPasses.cpp =================================================================== --- lib/Support/RegisterPasses.cpp +++ lib/Support/RegisterPasses.cpp @@ -51,9 +51,6 @@ #ifdef PLUTO_FOUND OPTIMIZER_PLUTO, #endif -#ifdef SCOPLIB_FOUND - OPTIMIZER_POCC, -#endif OPTIMIZER_ISL }; @@ -64,9 +61,6 @@ #ifdef PLUTO_FOUND clEnumValN(OPTIMIZER_PLUTO, "pluto", "The Pluto scheduling optimizer"), #endif -#ifdef SCOPLIB_FOUND - clEnumValN(OPTIMIZER_POCC, "pocc", "The PoCC scheduling optimizer"), -#endif clEnumValN(OPTIMIZER_ISL, "isl", "The isl scheduling optimizer"), clEnumValEnd), cl::Hidden, cl::init(OPTIMIZER_ISL), cl::ZeroOrMore, @@ -169,9 +163,6 @@ initializeJSONImporterPass(Registry); initializeIslAstInfoPass(Registry); initializeIslScheduleOptimizerPass(Registry); -#ifdef SCOPLIB_FOUND - initializePoccPass(Registry); -#endif initializePollyIndVarSimplifyPass(Registry); initializePollyCanonicalizePass(Registry); initializeScopDetectionPass(Registry); @@ -198,7 +189,7 @@ /// /// For certain parts of the Polly optimizer, several alternatives are provided: /// -/// As scheduling optimizer we support PoCC (http://pocc.sourceforge.net), PLUTO +/// As scheduling optimizer we support PLUTO /// (http://pluto-compiler.sourceforge.net) as well as the isl scheduling /// optimizer (http://freecode.com/projects/isl). The isl optimizer is the /// default optimizer. @@ -233,12 +224,6 @@ case OPTIMIZER_NONE: break; /* Do nothing */ -#ifdef SCOPLIB_FOUND - case OPTIMIZER_POCC: - PM.add(polly::createPoccPass()); - break; -#endif - #ifdef PLUTO_FOUND case OPTIMIZER_PLUTO: PM.add(polly::createPlutoOptimizerPass()); Index: lib/Support/SCEVValidator.cpp =================================================================== --- lib/Support/SCEVValidator.cpp +++ lib/Support/SCEVValidator.cpp @@ -156,7 +156,19 @@ } class ValidatorResult visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr) { - ValidatorResult Op = visit(Expr->getOperand()); + const SCEV *OpS = Expr->getOperand(); + ValidatorResult Op = visit(OpS); + + // Explicitly check for expressions of the following form: + // i % 2^C + // which could either be a srem (%) expressions or an and (&) expressions. + // The srem (%) versions are caught by visitUnknown, the and (&) versions + // are expressed as + // zext iC {0,+,1}<%for_i> + // by scalar evolution. + if (auto *OpAR = dyn_cast(OpS)) + if (OpAR->getStart()->isZero() && OpAR->getStepRecurrence(SE)->isOne()) + return Op; switch (Op.getType()) { case SCEVType::INT: @@ -346,12 +358,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: lib/Transform/Pocc.cpp =================================================================== --- lib/Transform/Pocc.cpp +++ /dev/null @@ -1,282 +0,0 @@ -//===- Pocc.cpp - Pocc interface ----------------------------------------===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// Pocc[1] interface. -// -// Pocc, the polyhedral compilation collection is a collection of polyhedral -// tools. It is used as an optimizer in polly -// -// [1] http://www-roc.inria.fr/~pouchet/software/pocc/ -// -//===----------------------------------------------------------------------===// - -#include "polly/LinkAllPasses.h" - -#ifdef SCOPLIB_FOUND -#include "polly/CodeGen/CodeGeneration.h" -#include "polly/Dependences.h" -#include "polly/Options.h" -#include "polly/ScheduleOptimizer.h" -#include "polly/ScopInfo.h" -#include "polly/ScopLib.h" -#include "llvm/Support/Debug.h" -#include "llvm/Support/Path.h" -#include "llvm/Support/Program.h" -#include "llvm/Support/MemoryBuffer.h" -#include "llvm/ADT/SmallString.h" - -#include "isl/space.h" -#include "isl/map.h" -#include "isl/constraint.h" - -#include -#include - -using namespace llvm; -using namespace polly; - -#define DEBUG_TYPE "polly-opt-pocc" - -static cl::opt PlutoFuse("pluto-fuse", cl::desc(""), cl::Hidden, - cl::value_desc("Set fuse mode of Pluto"), - cl::init("maxfuse"), - cl::cat(PollyCategory)); - -namespace { - -class Pocc : public ScopPass { - SmallString<128> PlutoStderr; - SmallString<128> PlutoStdout; - std::vector arguments; - -public: - static char ID; - explicit Pocc() : ScopPass(ID) {} - - std::string getFileName(Region *R) const; - virtual bool runOnScop(Scop &S); - void printScop(llvm::raw_ostream &OS) const; - void getAnalysisUsage(AnalysisUsage &AU) const; - -private: - bool runTransform(Scop &S); -}; -} - -char Pocc::ID = 0; -bool Pocc::runTransform(Scop &S) { - Dependences *D = &getAnalysis(); - - // Create the scop file. - SmallString<128> TempDir; - SmallString<128> ScopFile; - llvm::sys::path::system_temp_directory(/*erasedOnReboot=*/true, TempDir); - ScopFile = TempDir; - llvm::sys::path::append(ScopFile, "polly.scop"); - - FILE *F = fopen(ScopFile.c_str(), "w"); - - arguments.clear(); - - if (!F) { - errs() << "Cannot open file: " << TempDir.c_str() << "\n"; - errs() << "Skipping export.\n"; - return false; - } - - ScopLib scoplib(&S); - scoplib.print(F); - fclose(F); - - // Execute pocc - std::string pocc = sys::FindProgramByName("pocc"); - - arguments.push_back("pocc"); - arguments.push_back("--read-scop"); - arguments.push_back(ScopFile.c_str()); - arguments.push_back("--pluto-tile-scat"); - arguments.push_back("--candl-dep-isl-simp"); - arguments.push_back("--cloogify-scheds"); - arguments.push_back("--output-scop"); - arguments.push_back("--pluto"); - arguments.push_back("--pluto-bounds"); - arguments.push_back("10"); - arguments.push_back("--pluto-fuse"); - - arguments.push_back(PlutoFuse.c_str()); - - if (!DisablePollyTiling) - arguments.push_back("--pluto-tile"); - - if (PollyVectorizerChoice != VECTORIZER_NONE) - arguments.push_back("--pluto-prevector"); - - arguments.push_back(0); - - PlutoStdout = TempDir; - llvm::sys::path::append(PlutoStdout, "pluto.stdout"); - PlutoStderr = TempDir; - llvm::sys::path::append(PlutoStderr, "pluto.stderr"); - - std::vector Redirect; - Redirect.push_back(0); - Redirect.push_back(PlutoStdout.c_str()); - Redirect.push_back(PlutoStderr.c_str()); - - sys::ExecuteAndWait(pocc, &arguments[0], 0, - (const llvm::StringRef **)&Redirect[0]); - - // Read the created scop file - SmallString<128> NewScopFile; - NewScopFile = TempDir; - llvm::sys::path::append(NewScopFile, "polly.pocc.c.scop"); - - FILE *poccFile = fopen(NewScopFile.c_str(), "r"); - ScopLib newScoplib(&S, poccFile, D); - - if (!newScoplib.updateScattering()) { - errs() << "Failure when calculating the optimization with " - "the following command: "; - for (const char *Arg : arguments) - if (Arg) - errs() << " " << Arg; - errs() << "\n"; - return false; - } else - fclose(poccFile); - - if (PollyVectorizerChoice == VECTORIZER_NONE) - return false; - - // Find the innermost dimension that is not a constant dimension. This - // dimension will be vectorized. - unsigned scatterDims = S.getScatterDim(); - int lastLoop = scatterDims - 1; - - while (lastLoop) { - bool isSingleValued = true; - - for (ScopStmt *Stmt : S) { - isl_map *scat = Stmt->getScattering(); - isl_map *projected = isl_map_project_out(scat, isl_dim_out, lastLoop, - scatterDims - lastLoop); - - if (!isl_map_is_bijective(projected)) { - isSingleValued = false; - break; - } - } - - if (!isSingleValued) - break; - - lastLoop--; - } - - // Strip mine the innermost loop. - for (ScopStmt *Stmt : S) { - isl_map *scat = Stmt->getScattering(); - int scatDims = Stmt->getNumScattering(); - isl_space *Space = isl_space_alloc(S.getIslCtx(), S.getNumParams(), - scatDims, scatDims + 1); - isl_basic_map *map = isl_basic_map_universe(isl_space_copy(Space)); - isl_local_space *LSpace = isl_local_space_from_space(Space); - - for (int i = 0; i <= lastLoop - 1; i++) { - isl_constraint *c = isl_equality_alloc(isl_local_space_copy(LSpace)); - - isl_constraint_set_coefficient_si(c, isl_dim_in, i, 1); - isl_constraint_set_coefficient_si(c, isl_dim_out, i, -1); - - map = isl_basic_map_add_constraint(map, c); - } - - for (int i = lastLoop; i < scatDims; i++) { - isl_constraint *c = isl_equality_alloc(isl_local_space_copy(LSpace)); - - isl_constraint_set_coefficient_si(c, isl_dim_in, i, 1); - isl_constraint_set_coefficient_si(c, isl_dim_out, i + 1, -1); - - map = isl_basic_map_add_constraint(map, c); - } - - isl_constraint *c; - - int vectorWidth = 4; - c = isl_inequality_alloc(isl_local_space_copy(LSpace)); - isl_constraint_set_coefficient_si(c, isl_dim_out, lastLoop, -vectorWidth); - isl_constraint_set_coefficient_si(c, isl_dim_out, lastLoop + 1, 1); - map = isl_basic_map_add_constraint(map, c); - - c = isl_inequality_alloc(LSpace); - isl_constraint_set_coefficient_si(c, isl_dim_out, lastLoop, vectorWidth); - isl_constraint_set_coefficient_si(c, isl_dim_out, lastLoop + 1, -1); - isl_constraint_set_constant_si(c, vectorWidth - 1); - map = isl_basic_map_add_constraint(map, c); - - isl_map *transform = isl_map_from_basic_map(map); - transform = isl_map_set_tuple_name(transform, isl_dim_out, "scattering"); - transform = isl_map_set_tuple_name(transform, isl_dim_in, "scattering"); - - scat = isl_map_apply_range(scat, isl_map_copy(transform)); - Stmt->setScattering(scat); - } - - return false; -} -bool Pocc::runOnScop(Scop &S) { - bool Result = runTransform(S); - DEBUG(printScop(dbgs())); - - return Result; -} - -void Pocc::printScop(raw_ostream &OS) const { - std::unique_ptr stdoutBuffer; - std::unique_ptr stderrBuffer; - - OS << "Command line: "; - - for (const char *Arg : arguments) - if (Arg) - OS << " " << Arg; - - OS << "\n"; - - if (std::error_code ec = - MemoryBuffer::getFile(PlutoStdout.str(), stdoutBuffer)) - OS << "Could not open pocc stdout file: " + ec.message() << "\n"; - else { - OS << "pocc stdout: " << stdoutBuffer->getBufferIdentifier() << "\n"; - OS << stdoutBuffer->getBuffer() << "\n"; - } - - if (std::error_code ec = - MemoryBuffer::getFile(PlutoStderr.str(), stderrBuffer)) - OS << "Could not open pocc stderr file: " + ec.message() << "\n"; - else { - OS << "pocc stderr: " << PlutoStderr << "\n"; - OS << stderrBuffer->getBuffer() << "\n"; - } -} - -void Pocc::getAnalysisUsage(AnalysisUsage &AU) const { - ScopPass::getAnalysisUsage(AU); - AU.addRequired(); -} - -Pass *polly::createPoccPass() { return new Pocc(); } - -INITIALIZE_PASS_BEGIN(Pocc, "polly-opt-pocc", - "Polly - Optimize the scop using pocc", false, false); -INITIALIZE_PASS_DEPENDENCY(Dependences); -INITIALIZE_PASS_DEPENDENCY(ScopInfo); -INITIALIZE_PASS_END(Pocc, "polly-opt-pocc", - "Polly - Optimize the scop using pocc", false, false) -#endif /* SCOPLIB_FOUND */ 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/non_affine_but_modulo_access_2.ll =================================================================== --- /dev/null +++ test/ScopInfo/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/non_affine_but_modulo_access_3.ll =================================================================== --- /dev/null +++ test/ScopInfo/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/non_affine_but_modulo_access_4.ll =================================================================== --- /dev/null +++ test/ScopInfo/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/non_affine_but_modulo_access_5.ll =================================================================== --- /dev/null +++ test/ScopInfo/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/non_affine_but_modulo_access_6.ll =================================================================== --- /dev/null +++ test/ScopInfo/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/non_affine_but_modulo_condition_2.ll =================================================================== --- /dev/null +++ test/ScopInfo/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/non_affine_but_modulo_condition_3.ll =================================================================== --- /dev/null +++ test/ScopInfo/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/non_affine_but_modulo_condition_4.ll =================================================================== --- /dev/null +++ test/ScopInfo/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/non_affine_but_modulo_condition_5.ll =================================================================== --- /dev/null +++ test/ScopInfo/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/non_affine_but_modulo_condition_8.ll =================================================================== --- /dev/null +++ test/ScopInfo/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/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++)