[Polly] Added support for modulo accesses

[jdoerfert]

Summary

The support is limited to signed modulo access expressions with a
constant right hand side, e.g., A[i % 2]. Test cases are modified
according to this new feature and two new test cases to test the
functionality are added. A test case for not yet supported modulo
conditions is added too.

[jdoerfert]

Updated version with more test cases

[jdoerfert]

Updated version with more test cases

[jdoerfert]

Adjustments to catch different SCEV representations of modulo expressions

[simbuerg]

I have some stylistic comments inline, the rest looks good to me.

lib/Analysis/ScopInfo.cpp

179

capture

188

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

191

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

192

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

292

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

lib/Support/SCEVValidator.cpp

173

capture

184

I would use the type here.

361–375

Consistency: auto?

[jdoerfert]

Thanks for the feedback,.. you're right all the time, I should be more consistent.

I'll fix everything and commit it then.

[jdoerfert]

Closed by commit rL215684 (authored by @jdoerfert).

include/polly/LinkAllPasses.h

 llvm::Pass *createScopDetectionPass();
 llvm::Pass *createScopInfoPass();
 llvm::Pass *createIslAstInfoPass();
 llvm::Pass *createIslCodeGenerationPass();
 llvm::Pass *createIslScheduleOptimizerPass();
 llvm::Pass *createTempScopInfoPass();
 
 #ifdef SCOPLIB_FOUND
-llvm::Pass *createPoccPass();
 llvm::Pass *createScopLibExporterPass();
 llvm::Pass *createScopLibImporterPass();
 #endif
 
 extern char &IndependentBlocksID;
 extern char &CodePreparationID;
 }
 

 #endif
     polly::createPollyCanonicalizePass();
     polly::createIslAstInfoPass();
     polly::createIslCodeGenerationPass();
     polly::createIslScheduleOptimizerPass();
     polly::createTempScopInfoPass();
 
 #ifdef SCOPLIB_FOUND
-    polly::createPoccPass();
     polly::createScopLibExporterPass();
     polly::createScopLibImporterPass();
 #endif
   }
 } PollyForcePassLinking; // Force link by creating a global definition.
 }
 
 namespace llvm {
 class PassRegistry;
 #ifdef CLOOG_FOUND
 void initializeCodeGenerationPass(llvm::PassRegistry &);
 #endif
 void initializeCodePreparationPass(llvm::PassRegistry &);
 void initializeDeadCodeElimPass(llvm::PassRegistry &);
 void initializeIndependentBlocksPass(llvm::PassRegistry &);
 void initializeJSONExporterPass(llvm::PassRegistry &);
 void initializeJSONImporterPass(llvm::PassRegistry &);
 void initializeIslAstInfoPass(llvm::PassRegistry &);
 void initializeIslCodeGenerationPass(llvm::PassRegistry &);
 void initializeIslScheduleOptimizerPass(llvm::PassRegistry &);
 #ifdef PLUTO_FOUND
 void initializePlutoOptimizerPass(llvm::PassRegistry &);
 #endif
 void initializePollyCanonicalizePass(llvm::PassRegistry &);
-#ifdef SCOPLIB_FOUND
-void initializePoccPass(llvm::PassRegistry &);
-#endif
 void initializePollyIndVarSimplifyPass(llvm::PassRegistry &);
 }
 
 #endif

lib/Analysis/ScopInfo.cpp

 // Multiplicative reductions can be disabled seperately as these kind of
 // operations can overflow easily. Additive reductions and bit operations
 // are in contrast pretty stable.
 static cl::opt<bool> DisableMultiplicativeReductions(
     "polly-disable-multiplicative-reductions",
     cl::desc("Disable multiplicative reductions"), cl::Hidden, cl::ZeroOrMore,
     cl::init(false), cl::cat(PollyCategory));
 
+static int extractAffine(__isl_take isl_set *Set, __isl_take isl_aff *Aff,
+                         void *User) {
+  *((isl_aff **)(User)) = Aff;
+  isl_set_free(Set);
+  return 0;
+}
+
 /// Translate a 'const SCEV *' expression in an isl_pw_aff.
 struct SCEVAffinator : public SCEVVisitor<SCEVAffinator, isl_pw_aff *> {
 public:
   /// @brief Translate a 'const SCEV *' to an isl_pw_aff.
   ///
   /// @param Stmt The location at which the scalar evolution expression
   ///             is evaluated.
   /// @param Expr The expression that is translated.

 
 __isl_give isl_pw_aff *
 SCEVAffinator::visitTruncateExpr(const SCEVTruncateExpr *Expr) {
   llvm_unreachable("SCEVTruncateExpr not yet supported");
 }
 
 __isl_give isl_pw_aff *
 SCEVAffinator::visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr) {
+
+  // Explicitly check for expressions of the following form:
+  //   i % 2^C
+  // which could either be a srem (%) expressions or an and (&) expressions.
+  // The srem (%) versions are caught by visitUnknown, the and (&) versions
+  // are expressed as
+  //   zext iC {0,+,1}<%for_i>
+  // by scalar evolution.
+  const SCEV *OpS = Expr->getOperand();
+  if (auto *OpAR = dyn_cast<SCEVAddRecExpr>(OpS)) {
+    if (OpAR->getStart()->isZero() &&
+        OpAR->getStepRecurrence(*S->getSE())->isOne()) {
+      unsigned ModCst = 1 << OpAR->getType()->getScalarSizeInBits();
+      return isl_pw_aff_mod_val(visitAddRecExpr(OpAR),
+                                isl_val_int_from_si(Ctx, ModCst));
+    }
+  }
+
   llvm_unreachable("SCEVZeroExtendExpr not yet supported");
 }
 
 __isl_give isl_pw_aff *
 SCEVAffinator::visitSignExtendExpr(const SCEVSignExtendExpr *Expr) {
   // Assuming the value is signed, a sign extension is basically a noop.
   // TODO: Reconsider this as soon as we support unsigned values.
   return visit(Expr->getOperand());
 }
__isl_give isl_pw_aff *SCEVAffinator::visitSMaxExpr(const SCEVSMaxExpr *Expr) {
   return Max;
 }
 
 __isl_give isl_pw_aff *SCEVAffinator::visitUMaxExpr(const SCEVUMaxExpr *Expr) {
   llvm_unreachable("SCEVUMaxExpr not yet supported");
 }
 
 __isl_give isl_pw_aff *SCEVAffinator::visitUnknown(const SCEVUnknown *Expr) {
-  llvm_unreachable("Unknowns are always parameters");
+  Value *Unknown = Expr->getValue();
+  if (BinaryOperator *BO = dyn_cast<BinaryOperator>(Unknown)) {
+    isl_pw_aff *RHS, *LHS;
+    isl_aff *RHSAff;
+    isl_val *RHSVal;
+
+    assert(BO->getOpcode() == Instruction::SRem &&
+           "Binary operator unknowns are always signed modulo expressions");
+    LHS = visit(S->getSE()->getSCEV(BO->getOperand(0)));
+    RHS = visit(S->getSE()->getSCEV(BO->getOperand(1)));
+    assert(isl_pw_aff_is_cst(RHS) &&
+           "Modulo expressions are only valid for a constant right hand side");
+    assert(isl_pw_aff_n_piece(RHS) == 1 &&
+           "Modulo expressions are only valid for a non split right hand side");
+    isl_pw_aff_foreach_piece(RHS, extractAffine, &RHSAff);
+    assert(isl_aff_is_cst(RHSAff) &&
+           "Modulo expressions are only valid for a constant right hand side");
+    RHSVal = isl_aff_get_constant_val(RHSAff);
+
+    isl_pw_aff_free(RHS);
+    isl_aff_free(RHSAff);
+
+    return isl_pw_aff_mod_val(LHS, RHSVal);
+  }
+
+  llvm_unreachable("Unknowns are always parameters or modulo expressions");
 }
 
 int SCEVAffinator::getLoopDepth(const Loop *L) {
   Loop *outerLoop = S->getRegion().outermostLoopInRegion(const_cast<Loop *>(L));
   assert(outerLoop && "Scop does not contain this loop");
   return L->getLoopDepth() - outerLoop->getLoopDepth();
 }
 

lib/CMakeLists.txt

 
 if (GPU_CODEGEN)
   set (GPGPU_CODEGEN_FILES
        CodeGen/PTXGenerator.cpp)
 endif (GPU_CODEGEN)
 
 if (SCOPLIB_FOUND)
   set(POLLY_SCOPLIB_FILES
-      Transform/Pocc.cpp
       Exchange/ScopLib.cpp
       Exchange/ScopLibExporter.cpp
       Exchange/ScopLibImporter.cpp)
 endif (SCOPLIB_FOUND)
 
 add_polly_library(Polly
   Analysis/Dependences.cpp
   Analysis/ScopDetection.cpp

lib/Makefile

 
 ifeq ($(PLUTO_FOUND), yes)
 POLLY_PLUTO_FILES= Transform/Pluto.cpp
 endif
 
 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 \
                    CodeGen/IslExprBuilder.cpp \
                    CodeGen/IslCodeGeneration.cpp
 
 POLLY_JSON_FILES= JSON/json_reader.cpp \
       JSON/json_value.cpp \

lib/Support/RegisterPasses.cpp

static cl::opt<bool>
     PollyEnabled("polly", cl::desc("Enable the polly optimizer (only at -O3)"),
                  cl::init(false), cl::ZeroOrMore, cl::cat(PollyCategory));
 
 enum OptimizerChoice {
   OPTIMIZER_NONE,
 #ifdef PLUTO_FOUND
   OPTIMIZER_PLUTO,
 #endif
-#ifdef SCOPLIB_FOUND
-  OPTIMIZER_POCC,
-#endif
   OPTIMIZER_ISL
 };
 
 static cl::opt<OptimizerChoice> Optimizer(
     "polly-optimizer", cl::desc("Select the scheduling optimizer"),
     cl::values(
         clEnumValN(OPTIMIZER_NONE, "none", "No optimizer"),
 #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,
     cl::cat(PollyCategory));
 
 enum CodeGenChoice {
 #ifdef CLOOG_FOUND
   CODEGEN_CLOOG,
#endif
   initializeCodePreparationPass(Registry);
   initializeDeadCodeElimPass(Registry);
   initializeDependencesPass(Registry);
   initializeIndependentBlocksPass(Registry);
   initializeJSONExporterPass(Registry);
   initializeJSONImporterPass(Registry);
   initializeIslAstInfoPass(Registry);
   initializeIslScheduleOptimizerPass(Registry);
-#ifdef SCOPLIB_FOUND
-  initializePoccPass(Registry);
-#endif
   initializePollyIndVarSimplifyPass(Registry);
   initializePollyCanonicalizePass(Registry);
   initializeScopDetectionPass(Registry);
   initializeScopInfoPass(Registry);
   initializeTempScopInfoPass(Registry);
 }
 
 /// @brief Register Polly passes such that they form a polyhedral optimizer.

 ///
 /// Besides this core functionality, we optionally schedule passes that provide
 /// a graphical view of the scops (Polly[Only]Viewer, Polly[Only]Printer), that
 /// allow the export/import of the polyhedral representation
 /// (JSCON[Exporter|Importer]) or that show the cfg after code generation.
 ///
 /// 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.
 /// It is also possible to run Polly with no optimizer. This mode is mainly
 /// provided to analyze the run and compile time changes caused by the
 /// scheduling optimizer.
 ///
 /// Polly supports both CLooG (http://www.cloog.org) as well as the isl internal
static void registerPollyPasses(llvm::PassManagerBase &PM) {
 
   if (DeadCodeElim)
     PM.add(polly::createDeadCodeElimPass());
 
   switch (Optimizer) {
   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());
     break;
 #endif
 
   case OPTIMIZER_ISL:
     PM.add(polly::createIslScheduleOptimizerPass());

lib/Support/SCEVValidator.cpp

class ValidatorResult visitTruncateExpr(const SCEVTruncateExpr *Expr) {
     case SCEVType::INVALID:
       return Op;
     }
 
     llvm_unreachable("Unknown SCEVType");
   }
 
   class ValidatorResult visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr) {
-    ValidatorResult Op = visit(Expr->getOperand());
+    const SCEV *OpS = Expr->getOperand();
+    ValidatorResult Op = visit(OpS);
+
+    // Explicitly check for expressions of the following form:
+    //   i % 2^C
+    // which could either be a srem (%) expressions or an and (&) expressions.
+    // The srem (%) versions are caught by visitUnknown, the and (&) versions
+    // are expressed as
+    //   zext iC {0,+,1}<%for_i>
+    // by scalar evolution.
+    if (auto *OpAR = dyn_cast<SCEVAddRecExpr>(OpS))
+      if (OpAR->getStart()->isZero() && OpAR->getStepRecurrence(SE)->isOne())
+        return Op;
 
     switch (Op.getType()) {
     case SCEVType::INT:
     case SCEVType::PARAM:
       // We currently do not represent a truncate expression as an affine
       // expression. If it is constant during Scop execution, we treat it as a
       // parameter.
       return ValidatorResult(SCEVType::PARAM, Expr);
     case SCEVType::IV:
       DEBUG(dbgs() << "INVALID: ZeroExtend of SCEVType::IV expression");
       return ValidatorResult(SCEVType::INVALID);
     case SCEVType::INVALID:
       return Op;
     }
 
     llvm_unreachable("Unknown SCEVType");
   }
 
   class ValidatorResult visitSignExtendExpr(const SCEVSignExtendExpr *Expr) {
     // We currently allow only signed SCEV expressions. In the case of a
     // signed value, a sign extend is a noop.
if (!Expr->getType()->isIntegerTy()) {
       return ValidatorResult(SCEVType::INVALID);
     }
 
     if (isa<UndefValue>(V)) {
       DEBUG(dbgs() << "INVALID: UnknownExpr references an undef value");
       return ValidatorResult(SCEVType::INVALID);
     }
 
-    if (Instruction *I = dyn_cast<Instruction>(Expr->getValue()))
+    if (Instruction *I = dyn_cast<Instruction>(Expr->getValue())) {
+      if (I->getOpcode() == Instruction::SRem) {
+
+        ValidatorResult Op0 = visit(SE.getSCEV(I->getOperand(0)));
+        if (!Op0.isValid())
+          return ValidatorResult(SCEVType::INVALID);
+
+        ValidatorResult Op1 = visit(SE.getSCEV(I->getOperand(1)));
+        if (!Op1.isValid() || !Op1.isINT())
+          return ValidatorResult(SCEVType::INVALID);
+
+        Op0.merge(Op1);
+        return Op0;
+      }
+
       if (R->contains(I)) {
         DEBUG(dbgs() << "INVALID: UnknownExpr references an instruction "
                         "within the region\n");
         return ValidatorResult(SCEVType::INVALID);
       }
+    }
 
     if (BaseAddress == V) {
       DEBUG(dbgs() << "INVALID: UnknownExpr references BaseAddress\n");
       return ValidatorResult(SCEVType::INVALID);
     }
 
     return ValidatorResult(SCEVType::PARAM, Expr);
   }

lib/Transform/Pocc.cpp

-//===- 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 <memory>
-#include <system_error>
-
-using namespace llvm;
-using namespace polly;
-
-#define DEBUG_TYPE "polly-opt-pocc"
-
-static cl::opt<std::string> 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<const char *> 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<Dependences>();
-
-  // 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<llvm::StringRef> 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<MemoryBuffer> stdoutBuffer;
-  std::unique_ptr<MemoryBuffer> 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<Dependences>();
-}
-
-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 */

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

 ; RUN: opt %loadPolly -polly-allow-nonaffine -polly-dce -polly-ast -analyze < %s | FileCheck %s
 ;
 ;    void f(int *A) {
 ;      for (int i = 0; i < 1024; i++)
-; S1:    A[i % 2] = i;
+; S1:    A[i ^ 2] = i;
 ;      for (int i = 0; i < 1024; i++)
-; S2:    A[i2] = i;
+; S2:    A[i] = i;
 ;    }
 
 ; We unfortunately do need to execute all iterations of S1, as we do not know
 ; the size of A and as a result S1 may write for example to A[1024], which
 ; is not overwritten by S2.
 
 ; CHECK: for (int c1 = 0; c1 <= 1023; c1 += 1)
 ; CHECK:   Stmt_S1(c1);
 ; CHECK: for (int c1 = 0; c1 <= 1023; c1 += 1)
 ; CHECK:   Stmt_S2(c1);
 
-target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-n32-S64"
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 define void @f(i32* %A) {
 entry:
   br label %for.cond
 
-for.cond:
+for.cond:                                         ; preds = %for.inc, %entry
   %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
-  %exitcond = icmp ne i32 %i.0, 1024
-  br i1 %exitcond, label %S1, label %next
+  %exitcond1 = icmp ne i32 %i.0, 1024
+  br i1 %exitcond1, label %for.body, label %for.end
 
-S1:
-  %rem = srem i32 %i.0, 2
-  %arrayidx = getelementptr inbounds i32* %A, i32 %rem
+for.body:                                         ; preds = %for.cond
+  br label %S1
+
+S1:                                               ; preds = %for.body
+  %xor = xor i32 %i.0, 2
+  %idxprom = sext i32 %xor to i64
+  %arrayidx = getelementptr inbounds i32* %A, i64 %idxprom
   store i32 %i.0, i32* %arrayidx, align 4
   br label %for.inc
 
-for.inc:
+for.inc:                                          ; preds = %S1
   %inc = add nsw i32 %i.0, 1
   br label %for.cond
 
-next:
- br label %for.cond.2
+for.end:                                          ; preds = %for.cond
+  br label %for.cond2
 
-for.cond.2:
-  %i.2 = phi i32 [ 0, %next ], [ %inc.2, %for.inc.2 ]
-  %exitcond.2 = icmp ne i32 %i.2, 1024
-  br i1 %exitcond.2, label %S2, label %for.end
-
-S2:
-  %arrayidx.2 = getelementptr inbounds i32* %A, i32 %i.2
-  store i32 %i.2, i32* %arrayidx.2, align 4
-  br label %for.inc.2
-
-for.inc.2:
-  %inc.2 = add nsw i32 %i.2, 1
-  br label %for.cond.2
+for.cond2:                                        ; preds = %for.inc7, %for.end
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc7 ], [ 0, %for.end ]
+  %exitcond = icmp ne i64 %indvars.iv, 1024
+  br i1 %exitcond, label %for.body4, label %for.end9
+
+for.body4:                                        ; preds = %for.cond2
+  br label %S2
+
+S2:                                               ; preds = %for.body4
+  %arrayidx6 = getelementptr inbounds i32* %A, i64 %indvars.iv
+  %tmp = trunc i64 %indvars.iv to i32
+  store i32 %tmp, i32* %arrayidx6, align 4
+  br label %for.inc7
+
+for.inc7:                                         ; preds = %S2
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %for.cond2
 
-for.end:
+for.end9:                                         ; preds = %for.cond2
   ret void
 }
-

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

-; RUN: opt %loadPolly -polly-allow-nonaffine -polly-dce -polly-ast -analyze < %s | FileCheck %s
+; RUN: opt %loadPolly -polly-dce -polly-ast -analyze < %s | FileCheck %s
 ;
 ;    void f(int *A) {
 ;      for (int i = 0; i < 1024; i++)
 ; S1:    A[i % 2] = i;
 ;      for (int i = 0; i < 1024; i++)
 ; S2:    A[i2] = i;
 ;    }
-
-; We unfortunately do need to execute all iterations of S1, as we do not know
-; the size of A and as a result S1 may write for example to A[1024], which
-; is not overwritten by S2.
-
-; CHECK: for (int c1 = 0; c1 <= 1023; c1 += 1)
-; CHECK:   Stmt_S1(c1);
+;
 ; CHECK: for (int c1 = 0; c1 <= 1023; c1 += 1)
 ; CHECK:   Stmt_S2(c1);
 
 target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-n32-S64"
 
 define void @f(i32* %A) {
 entry:
   br label %for.cond

test/ScopDetect/non_affine_but_modulo_access.ll

-; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+; RUN: opt %loadPolly -polly-detect -analyze < %s | FileCheck %s
 ;
-; FIXME: We cannot detect this SCoP yet but as soon as we can we should check
-;        that the reduction is detected!
+; CHECK: Valid Region for Scop:
 ;
-; CHECK-NOT: Scattering
-;
-;    void f(int *A) {
+;    void jd(int *A) {
 ;      for (int i = 0; i < 1024; i++)
-;        A[i % 2] += i;
+;        A[i % 2] = A[i % 2 + 1];
 ;    }
 ;
-target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-n32-S64"
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
-define void @f(i32* %A) {
+define void @jd(i32* %A) {
 entry:
   br label %for.cond
 
 for.cond:                                         ; preds = %for.inc, %entry
   %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
   %exitcond = icmp ne i32 %i.0, 1024
   br i1 %exitcond, label %for.body, label %for.end
 
 for.body:                                         ; preds = %for.cond
   %rem = srem i32 %i.0, 2
-  %arrayidx = getelementptr inbounds i32* %A, i32 %rem
+  %add = add nsw i32 %rem, 1
+  %idxprom = sext i32 %add to i64
+  %arrayidx = getelementptr inbounds i32* %A, i64 %idxprom
   %tmp = load i32* %arrayidx, align 4
-  %add = add nsw i32 %tmp, %i.0
-  store i32 %add, i32* %arrayidx, align 4
+  %rem1 = srem i32 %i.0, 2
+  %idxprom2 = sext i32 %rem1 to i64
+  %arrayidx3 = getelementptr inbounds i32* %A, i64 %idxprom2
+  store i32 %tmp, i32* %arrayidx3, align 4
   br label %for.inc
 
 for.inc:                                          ; preds = %for.body
   %inc = add nsw i32 %i.0, 1
   br label %for.cond
 
 for.end:                                          ; preds = %for.cond
   ret void
 }

test/ScopDetect/non_affine_but_modulo_condition.ll

+; RUN: opt %loadPolly -polly-detect -analyze < %s | FileCheck %s
+;
+; CHECK: jd_and
+; CHECK: Valid Region for Scop:
+; CHECK: jd_srem
+; CHECK: Valid Region for Scop:
+;
+;    void jd(int *A) {
+;      for (int i = 0; i < 1024; i++)
+;        if (i % 2)
+;          A[i] += 1;
+;    }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @jd_and(i32* %A) {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry ]
+  %exitcond = icmp ne i64 %indvars.iv, 1024
+  br i1 %exitcond, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %tmp = trunc i64 %indvars.iv to i32
+  %rem1 = and i32 %tmp, 1
+  %tobool = icmp eq i32 %rem1, 0
+  br i1 %tobool, label %if.end, label %if.then
+
+if.then:                                          ; preds = %for.body
+  %arrayidx = getelementptr inbounds i32* %A, i64 %indvars.iv
+  %tmp2 = load i32* %arrayidx, align 4
+  %add = add nsw i32 %tmp2, 1
+  store i32 %add, i32* %arrayidx, align 4
+  br label %if.end
+
+if.end:                                           ; preds = %for.body, %if.then
+  br label %for.inc
+
+for.inc:                                          ; preds = %if.end
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}
+
+define void @jd_srem(i32* %A) {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry ]
+  %exitcond = icmp ne i64 %indvars.iv, 1024
+  br i1 %exitcond, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %tmp = trunc i64 %indvars.iv to i32
+  %rem1 = srem i32 %tmp, 2
+  %tobool = icmp eq i32 %rem1, 0
+  br i1 %tobool, label %if.end, label %if.then
+
+if.then:                                          ; preds = %for.body
+  %arrayidx = getelementptr inbounds i32* %A, i64 %indvars.iv
+  %tmp2 = load i32* %arrayidx, align 4
+  %add = add nsw i32 %tmp2, 1
+  store i32 %add, i32* %arrayidx, align 4
+  br label %if.end
+
+if.end:                                           ; preds = %for.body, %if.then
+  br label %for.inc
+
+for.inc:                                          ; preds = %if.end
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}

test/ScopInfo/non_affine_but_modulo_access_2.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+;
+;    void jd(int *A) {
+;      for (int i = 0; i < 1024; i++)
+;        A[i % 2] = A[i % 2 + 1];
+;    }
+;
+; CHECK: ReadAccess := [Reduction Type: NONE]
+; CHECK:     { Stmt_for_body[i0] -> MemRef_A[o0] : exists (e0 = floor((-1 - i0 + o0)/2): 2e0 = -1 - i0 + o0 and o0 >= 1 and o0 <= 2) };
+; CHECK: MustWriteAccess :=  [Reduction Type: NONE]
+; CHECK:     { Stmt_for_body[i0] -> MemRef_A[o0] : exists (e0 = floor((-i0 + o0)/2): 2e0 = -i0 + o0 and o0 >= 0 and o0 <= 1) };
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @jd(i32* %A) {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
+  %exitcond = icmp ne i32 %i.0, 1024
+  br i1 %exitcond, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %rem = srem i32 %i.0, 2
+  %add = add nsw i32 %rem, 1
+  %idxprom = sext i32 %add to i64
+  %arrayidx = getelementptr inbounds i32* %A, i64 %idxprom
+  %tmp = load i32* %arrayidx, align 4
+  %rem1 = and i32 %i.0, 1
+  %idxprom2 = sext i32 %rem1 to i64
+  %arrayidx3 = getelementptr inbounds i32* %A, i64 %idxprom2
+  store i32 %tmp, i32* %arrayidx3, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body
+  %inc = add nsw i32 %i.0, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}

test/ScopInfo/non_affine_but_modulo_access_3.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+;
+;    void jd(int *A, int c) {
+;      for (int i = 0; i < 1024; i++)
+;        A[i % 3] = A[(i + 1) % 3] + A[c % 3] + A[(i - c) % 3];
+;    }
+;
+; CHECK: ReadAccess := [Reduction Type: NONE]
+; CHECK:     [c] -> { Stmt_for_body[i0] -> MemRef_A[o0] : exists (e0 = floor((-1 - i0 + o0)/3): 3e0 = -1 - i0 + o0 and o0 >= 0 and o0 <= 2) };
+; CHECK: ReadAccess := [Reduction Type: NONE]
+; CHECK:     [c] -> { Stmt_for_body[i0] -> MemRef_A[o0] : exists (e0 = floor((-c + o0)/3): 3e0 = -c + o0 and o0 >= 0 and o0 <= 2) };
+; CHECK: ReadAccess := [Reduction Type: NONE]
+; CHECK:     [c] -> { Stmt_for_body[i0] -> MemRef_A[o0] : exists (e0 = floor((-2c - i0 + o0)/3): 3e0 = -2c - i0 + o0 and o0 >= 0 and o0 <= 2) };
+; CHECK: MustWriteAccess :=  [Reduction Type: NONE]
+; CHECK:     [c] -> { Stmt_for_body[i0] -> MemRef_A[o0] : exists (e0 = floor((-i0 + o0)/3): 3e0 = -i0 + o0 and o0 >= 0 and o0 <= 2) };
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @jd(i32* %A, i32 %c) {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
+  %exitcond = icmp ne i32 %i.0, 1024
+  br i1 %exitcond, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %add = add nsw i32 %i.0, 1
+  %rem = srem i32 %add, 3
+  %idxprom = sext i32 %rem to i64
+  %arrayidx = getelementptr inbounds i32* %A, i64 %idxprom
+  %tmp = load i32* %arrayidx, align 4
+  %rem1 = srem i32 %c, 3
+  %idxprom2 = sext i32 %rem1 to i64
+  %arrayidx3 = getelementptr inbounds i32* %A, i64 %idxprom2
+  %tmp1 = load i32* %arrayidx3, align 4
+  %add4 = add nsw i32 %tmp, %tmp1
+  %sub = sub nsw i32 %i.0, %c
+  %rem5 = srem i32 %sub, 3
+  %idxprom6 = sext i32 %rem5 to i64
+  %arrayidx7 = getelementptr inbounds i32* %A, i64 %idxprom6
+  %tmp2 = load i32* %arrayidx7, align 4
+  %add8 = add nsw i32 %add4, %tmp2
+  %rem9 = srem i32 %i.0, 3
+  %idxprom10 = sext i32 %rem9 to i64
+  %arrayidx11 = getelementptr inbounds i32* %A, i64 %idxprom10
+  store i32 %add8, i32* %arrayidx11, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body
+  %inc = add nsw i32 %i.0, 1
+  br label %for.cond
+
+for.end:
+  ret void
+}

test/ScopInfo/non_affine_but_modulo_access_4.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+;
+;    void jd(int *A, int c) {
+;      for (int i = 0; i < 1024; i++)
+;        A[i % 4] = A[(i + 1) % 4] + A[c % 4] + A[(i - c) % 4];
+;    }
+;
+; CHECK: ReadAccess := [Reduction Type: NONE]
+; CHECK:     [c] -> { Stmt_for_body[i0] -> MemRef_A[o0] : exists (e0 = floor((-1 - i0 + o0)/4): 4e0 = -1 - i0 + o0 and o0 >= 0 and o0 <= 3) };
+; CHECK: ReadAccess := [Reduction Type: NONE]
+; CHECK:     [c] -> { Stmt_for_body[i0] -> MemRef_A[o0] : exists (e0 = floor((-c + o0)/4): 4e0 = -c + o0 and o0 >= 0 and o0 <= 3) };
+; CHECK: ReadAccess := [Reduction Type: NONE]
+; CHECK:     [c] -> { Stmt_for_body[i0] -> MemRef_A[o0] : exists (e0 = floor((-3c - i0 + o0)/4): 4e0 = -3c - i0 + o0 and o0 >= 0 and o0 <= 3) };
+; CHECK: MustWriteAccess :=  [Reduction Type: NONE]
+; CHECK:     [c] -> { Stmt_for_body[i0] -> MemRef_A[o0] : exists (e0 = floor((-i0 + o0)/4): 4e0 = -i0 + o0 and o0 >= 0 and o0 <= 3) };
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @jd(i32* %A, i32 %c) {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
+  %exitcond = icmp ne i32 %i.0, 1024
+  br i1 %exitcond, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %add = add nsw i32 %i.0, 1
+  %rem = srem i32 %add, 4
+  %idxprom = sext i32 %rem to i64
+  %arrayidx = getelementptr inbounds i32* %A, i64 %idxprom
+  %tmp = load i32* %arrayidx, align 4
+  %rem1 = srem i32 %c, 4
+  %idxprom2 = sext i32 %rem1 to i64
+  %arrayidx3 = getelementptr inbounds i32* %A, i64 %idxprom2
+  %tmp1 = load i32* %arrayidx3, align 4
+  %add4 = add nsw i32 %tmp, %tmp1
+  %sub = sub nsw i32 %i.0, %c
+  %rem5 = srem i32 %sub, 4
+  %idxprom6 = sext i32 %rem5 to i64
+  %arrayidx7 = getelementptr inbounds i32* %A, i64 %idxprom6
+  %tmp2 = load i32* %arrayidx7, align 4
+  %add8 = add nsw i32 %add4, %tmp2
+  %rem9 = srem i32 %i.0, 4
+  %idxprom10 = sext i32 %rem9 to i64
+  %arrayidx11 = getelementptr inbounds i32* %A, i64 %idxprom10
+  store i32 %add8, i32* %arrayidx11, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body
+  %inc = add nsw i32 %i.0, 1
+  br label %for.cond
+
+for.end:
+  ret void
+}

test/ScopInfo/non_affine_but_modulo_access_5.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+;
+;    void jd(int *A, int c) {
+;      for (int i = 0; i < 1024; i++)
+;        A[i % 5] = A[(i + 1) % 5] + A[c % 5] + A[(i - c) % 5];
+;    }
+;
+; CHECK: ReadAccess := [Reduction Type: NONE]
+; CHECK:     [c] -> { Stmt_for_body[i0] -> MemRef_A[o0] : exists (e0 = floor((-1 - i0 + o0)/5): 5e0 = -1 - i0 + o0 and o0 >= 0 and o0 <= 4) };
+; CHECK: ReadAccess := [Reduction Type: NONE]
+; CHECK:     [c] -> { Stmt_for_body[i0] -> MemRef_A[o0] : exists (e0 = floor((-c + o0)/5): 5e0 = -c + o0 and o0 >= 0 and o0 <= 4) };
+; CHECK: ReadAccess := [Reduction Type: NONE]
+; CHECK:     [c] -> { Stmt_for_body[i0] -> MemRef_A[o0] : exists (e0 = floor((-4c - i0 + o0)/5): 5e0 = -4c - i0 + o0 and o0 >= 0 and o0 <= 4) };
+; CHECK: MustWriteAccess :=  [Reduction Type: NONE]
+; CHECK:     [c] -> { Stmt_for_body[i0] -> MemRef_A[o0] : exists (e0 = floor((-i0 + o0)/5): 5e0 = -i0 + o0 and o0 >= 0 and o0 <= 4) };
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @jd(i32* %A, i32 %c) {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
+  %exitcond = icmp ne i32 %i.0, 1024
+  br i1 %exitcond, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %add = add nsw i32 %i.0, 1
+  %rem = srem i32 %add, 5
+  %idxprom = sext i32 %rem to i64
+  %arrayidx = getelementptr inbounds i32* %A, i64 %idxprom
+  %tmp = load i32* %arrayidx, align 4
+  %rem1 = srem i32 %c, 5
+  %idxprom2 = sext i32 %rem1 to i64
+  %arrayidx3 = getelementptr inbounds i32* %A, i64 %idxprom2
+  %tmp1 = load i32* %arrayidx3, align 4
+  %add4 = add nsw i32 %tmp, %tmp1
+  %sub = sub nsw i32 %i.0, %c
+  %rem5 = srem i32 %sub, 5
+  %idxprom6 = sext i32 %rem5 to i64
+  %arrayidx7 = getelementptr inbounds i32* %A, i64 %idxprom6
+  %tmp2 = load i32* %arrayidx7, align 4
+  %add8 = add nsw i32 %add4, %tmp2
+  %rem9 = srem i32 %i.0, 5
+  %idxprom10 = sext i32 %rem9 to i64
+  %arrayidx11 = getelementptr inbounds i32* %A, i64 %idxprom10
+  store i32 %add8, i32* %arrayidx11, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body
+  %inc = add nsw i32 %i.0, 1
+  br label %for.cond
+
+for.end:
+  ret void
+}

test/ScopInfo/non_affine_but_modulo_access_6.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+;
+;    void jd(int *A, int c) {
+;      for (int i = 0; i < 1024; i++)
+;        A[i % 6] = A[(i + 1) % 6] + A[c % 6] + A[(i - c) % 6];
+;    }
+;
+; CHECK: ReadAccess := [Reduction Type: NONE]
+; CHECK:     [c] -> { Stmt_for_body[i0] -> MemRef_A[o0] : exists (e0 = floor((-1 - i0 + o0)/6): 6e0 = -1 - i0 + o0 and o0 >= 0 and o0 <= 5) };
+; CHECK: ReadAccess := [Reduction Type: NONE]
+; CHECK:     [c] -> { Stmt_for_body[i0] -> MemRef_A[o0] : exists (e0 = floor((-c + o0)/6): 6e0 = -c + o0 and o0 >= 0 and o0 <= 5) };
+; CHECK: ReadAccess := [Reduction Type: NONE]
+; CHECK:     [c] -> { Stmt_for_body[i0] -> MemRef_A[o0] : exists (e0 = floor((-5c - i0 + o0)/6): 6e0 = -5c - i0 + o0 and o0 >= 0 and o0 <= 5) };
+; CHECK: MustWriteAccess :=  [Reduction Type: NONE]
+; CHECK:     [c] -> { Stmt_for_body[i0] -> MemRef_A[o0] : exists (e0 = floor((-i0 + o0)/6): 6e0 = -i0 + o0 and o0 >= 0 and o0 <= 5) };
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @jd(i32* %A, i32 %c) {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
+  %exitcond = icmp ne i32 %i.0, 1024
+  br i1 %exitcond, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %add = add nsw i32 %i.0, 1
+  %rem = srem i32 %add, 6
+  %idxprom = sext i32 %rem to i64
+  %arrayidx = getelementptr inbounds i32* %A, i64 %idxprom
+  %tmp = load i32* %arrayidx, align 4
+  %rem1 = srem i32 %c, 6
+  %idxprom2 = sext i32 %rem1 to i64
+  %arrayidx3 = getelementptr inbounds i32* %A, i64 %idxprom2
+  %tmp1 = load i32* %arrayidx3, align 4
+  %add4 = add nsw i32 %tmp, %tmp1
+  %sub = sub nsw i32 %i.0, %c
+  %rem5 = srem i32 %sub, 6
+  %idxprom6 = sext i32 %rem5 to i64
+  %arrayidx7 = getelementptr inbounds i32* %A, i64 %idxprom6
+  %tmp2 = load i32* %arrayidx7, align 4
+  %add8 = add nsw i32 %add4, %tmp2
+  %rem9 = srem i32 %i.0, 6
+  %idxprom10 = sext i32 %rem9 to i64
+  %arrayidx11 = getelementptr inbounds i32* %A, i64 %idxprom10
+  store i32 %add8, i32* %arrayidx11, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body
+  %inc = add nsw i32 %i.0, 1
+  br label %for.cond
+
+for.end:
+  ret void
+}

test/ScopInfo/non_affine_but_modulo_condition_2.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+;
+;    void jd(int *A) {
+;      for (int i = 0; i < 1024; i++)
+;        if (i % 2)
+;          A[i] += 1;
+;    }
+;
+; CHECK: Function: jd_and
+; CHECK:   Stmt_if_then
+; CHECK:     Domain :=
+; CHECK:         { Stmt_if_then[i0] : exists (e0 = floor((-1 + i0)/2): 2e0 = -1 + i0 and i0 >= 0 and i0 <= 1023) };
+; CHECK:     Scattering :=
+; CHECK:         { Stmt_if_then[i0] -> scattering[0, i0, 0] };
+; CHECK:     ReadAccess := [Reduction Type: +]
+; CHECK:         { Stmt_if_then[i0] -> MemRef_A[i0] };
+; CHECK:     MustWriteAccess :=  [Reduction Type: +]
+; CHECK:         { Stmt_if_then[i0] -> MemRef_A[i0] };
+;
+; CHECK: Function: jd_srem
+; CHECK:   Stmt_if_then
+; CHECK:     Domain :=
+; CHECK:         { Stmt_if_then[i0] : exists (e0 = floor((-1 + i0)/2): 2e0 = -1 + i0 and i0 >= 0 and i0 <= 1023) };
+; CHECK:     Scattering :=
+; CHECK:         { Stmt_if_then[i0] -> scattering[0, i0, 0] };
+; CHECK:     ReadAccess := [Reduction Type: +]
+; CHECK:         { Stmt_if_then[i0] -> MemRef_A[i0] };
+; CHECK:     MustWriteAccess :=  [Reduction Type: +]
+; CHECK:         { Stmt_if_then[i0] -> MemRef_A[i0] };
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @jd_and(i32* %A) {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry ]
+  %exitcond = icmp ne i64 %indvars.iv, 1024
+  br i1 %exitcond, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %tmp = trunc i64 %indvars.iv to i32
+  %rem1 = and i32 %tmp, 1
+  %tobool = icmp eq i32 %rem1, 0
+  br i1 %tobool, label %if.end, label %if.then
+
+if.then:                                          ; preds = %for.body
+  %arrayidx = getelementptr inbounds i32* %A, i64 %indvars.iv
+  %tmp2 = load i32* %arrayidx, align 4
+  %add = add nsw i32 %tmp2, 1
+  store i32 %add, i32* %arrayidx, align 4
+  br label %if.end
+
+if.end:                                           ; preds = %for.body, %if.then
+  br label %for.inc
+
+for.inc:                                          ; preds = %if.end
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}
+
+define void @jd_srem(i32* %A) {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry ]
+  %exitcond = icmp ne i64 %indvars.iv, 1024
+  br i1 %exitcond, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %tmp = trunc i64 %indvars.iv to i32
+  %rem1 = srem i32 %tmp, 2
+  %tobool = icmp eq i32 %rem1, 0
+  br i1 %tobool, label %if.end, label %if.then
+
+if.then:                                          ; preds = %for.body
+  %arrayidx = getelementptr inbounds i32* %A, i64 %indvars.iv
+  %tmp2 = load i32* %arrayidx, align 4
+  %add = add nsw i32 %tmp2, 1
+  store i32 %add, i32* %arrayidx, align 4
+  br label %if.end
+
+if.end:                                           ; preds = %for.body, %if.then
+  br label %for.inc
+
+for.inc:                                          ; preds = %if.end
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}

test/ScopInfo/non_affine_but_modulo_condition_3.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+;
+;    void jd(int *A) {
+;      for (int i = 0; i < 1024; i++)
+;        if (i % 3)
+;          A[i] += 1;
+;    }
+;
+; CHECK: Function: jd_srem
+; CHECK:   Stmt_if_then
+; CHECK:     Domain :=
+; CHECK:         { Stmt_if_then[i0] : exists (e0 = floor((i0)/3): i0 >= 0 and i0 <= 1023 and 3e0 <= -1 + i0 and 3e0 >= -2 + i0) };
+; CHECK:     Scattering :=
+; CHECK:         { Stmt_if_then[i0] -> scattering[0, i0, 0] };
+; CHECK:     ReadAccess := [Reduction Type: +]
+; CHECK:         { Stmt_if_then[i0] -> MemRef_A[i0] };
+; CHECK:     MustWriteAccess :=  [Reduction Type: +]
+; CHECK:         { Stmt_if_then[i0] -> MemRef_A[i0] };
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @jd_srem(i32* %A) {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry ]
+  %exitcond = icmp ne i64 %indvars.iv, 1024
+  br i1 %exitcond, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %rem = srem i64 %indvars.iv, 3
+  %tobool = icmp eq i64 %rem, 0
+  br i1 %tobool, label %if.end, label %if.then
+
+if.then:                                          ; preds = %for.body
+  %arrayidx = getelementptr inbounds i32* %A, i64 %indvars.iv
+  %tmp2 = load i32* %arrayidx, align 4
+  %add = add nsw i32 %tmp2, 1
+  store i32 %add, i32* %arrayidx, align 4
+  br label %if.end
+
+if.end:                                           ; preds = %for.body, %if.then
+  br label %for.inc
+
+for.inc:                                          ; preds = %if.end
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}

test/ScopInfo/non_affine_but_modulo_condition_4.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+;
+;    void jd(int *A) {
+;      for (int i = 0; i < 1024; i++)
+;        if (i % 4)
+;          A[i] += 1;
+;    }
+;
+; CHECK: Function: jd_and
+; CHECK:   Stmt_if_then
+; CHECK:     Domain :=
+; CHECK:         { Stmt_if_then[i0] : exists (e0 = floor((i0)/4): i0 >= 0 and i0 <= 1023 and 4e0 <= -1 + i0 and 4e0 >= -3 + i0) };
+; CHECK:     Scattering :=
+; CHECK:         { Stmt_if_then[i0] -> scattering[0, i0, 0] };
+; CHECK:     ReadAccess := [Reduction Type: +]
+; CHECK:         { Stmt_if_then[i0] -> MemRef_A[i0] };
+; CHECK:     MustWriteAccess :=  [Reduction Type: +]
+; CHECK:         { Stmt_if_then[i0] -> MemRef_A[i0] };
+;
+; CHECK: Function: jd_srem
+; CHECK:   Stmt_if_then
+; CHECK:     Domain :=
+; CHECK:         { Stmt_if_then[i0] : exists (e0 = floor((i0)/4): i0 >= 0 and i0 <= 1023 and 4e0 <= -1 + i0 and 4e0 >= -3 + i0) };
+; CHECK:     Scattering :=
+; CHECK:         { Stmt_if_then[i0] -> scattering[0, i0, 0] };
+; CHECK:     ReadAccess := [Reduction Type: +]
+; CHECK:         { Stmt_if_then[i0] -> MemRef_A[i0] };
+; CHECK:     MustWriteAccess :=  [Reduction Type: +]
+; CHECK:         { Stmt_if_then[i0] -> MemRef_A[i0] };
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @jd_and(i32* %A) {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry ]
+  %exitcond = icmp ne i64 %indvars.iv, 1024
+  br i1 %exitcond, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %tmp = trunc i64 %indvars.iv to i32
+  %rem1 = and i32 %tmp, 3
+  %tobool = icmp eq i32 %rem1, 0
+  br i1 %tobool, label %if.end, label %if.then
+
+if.then:                                          ; preds = %for.body
+  %arrayidx = getelementptr inbounds i32* %A, i64 %indvars.iv
+  %tmp2 = load i32* %arrayidx, align 4
+  %add = add nsw i32 %tmp2, 1
+  store i32 %add, i32* %arrayidx, align 4
+  br label %if.end
+
+if.end:                                           ; preds = %for.body, %if.then
+  br label %for.inc
+
+for.inc:                                          ; preds = %if.end
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}
+
+define void @jd_srem(i32* %A) {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry ]
+  %exitcond = icmp ne i64 %indvars.iv, 1024
+  br i1 %exitcond, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %rem = srem i64 %indvars.iv, 4
+  %tobool = icmp eq i64 %rem, 0
+  br i1 %tobool, label %if.end, label %if.then
+
+if.then:                                          ; preds = %for.body
+  %arrayidx = getelementptr inbounds i32* %A, i64 %indvars.iv
+  %tmp2 = load i32* %arrayidx, align 4
+  %add = add nsw i32 %tmp2, 1
+  store i32 %add, i32* %arrayidx, align 4
+  br label %if.end
+
+if.end:                                           ; preds = %for.body, %if.then
+  br label %for.inc
+
+for.inc:                                          ; preds = %if.end
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}

test/ScopInfo/non_affine_but_modulo_condition_5.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+;
+;    void jd(int *A) {
+;      for (int i = 0; i < 1024; i++)
+;        if (i % 5)
+;          A[i] += 1;
+;    }
+;
+; CHECK: Function: jd_srem
+; CHECK:   Stmt_if_then
+; CHECK:     Domain :=
+; CHECK:         { Stmt_if_then[i0] : exists (e0 = floor((i0)/5): i0 >= 0 and i0 <= 1023 and 5e0 <= -1 + i0 and 5e0 >= -4 + i0) };
+; CHECK:     Scattering :=
+; CHECK:         { Stmt_if_then[i0] -> scattering[0, i0, 0] };
+; CHECK:     ReadAccess := [Reduction Type: +]
+; CHECK:         { Stmt_if_then[i0] -> MemRef_A[i0] };
+; CHECK:     MustWriteAccess :=  [Reduction Type: +]
+; CHECK:         { Stmt_if_then[i0] -> MemRef_A[i0] };
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @jd_srem(i32* %A) {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry ]
+  %exitcond = icmp ne i64 %indvars.iv, 1024
+  br i1 %exitcond, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %rem = srem i64 %indvars.iv, 5
+  %tobool = icmp eq i64 %rem, 0
+  br i1 %tobool, label %if.end, label %if.then
+
+if.then:                                          ; preds = %for.body
+  %arrayidx = getelementptr inbounds i32* %A, i64 %indvars.iv
+  %tmp2 = load i32* %arrayidx, align 4
+  %add = add nsw i32 %tmp2, 1
+  store i32 %add, i32* %arrayidx, align 4
+  br label %if.end
+
+if.end:                                           ; preds = %for.body, %if.then
+  br label %for.inc
+
+for.inc:                                          ; preds = %if.end
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}

test/ScopInfo/non_affine_but_modulo_condition_8.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+;
+;    void jd(int *A) {
+;      for (int i = 0; i < 1024; i++)
+;        if (i % 8)
+;          A[i] += 1;
+;    }
+;
+; CHECK: Function: jd_and
+; CHECK:   Stmt_if_then
+; CHECK:     Domain :=
+; CHECK:         { Stmt_if_then[i0] : exists (e0 = floor((i0)/8): i0 >= 0 and i0 <= 1023 and 8e0 <= -1 + i0 and 8e0 >= -7 + i0) };
+; CHECK:     Scattering :=
+; CHECK:         { Stmt_if_then[i0] -> scattering[0, i0, 0] };
+; CHECK:     ReadAccess := [Reduction Type: +]
+; CHECK:         { Stmt_if_then[i0] -> MemRef_A[i0] };
+; CHECK:     MustWriteAccess :=  [Reduction Type: +]
+; CHECK:         { Stmt_if_then[i0] -> MemRef_A[i0] };
+;
+; CHECK: Function: jd_srem
+; CHECK:   Stmt_if_then
+; CHECK:     Domain :=
+; CHECK:         { Stmt_if_then[i0] : exists (e0 = floor((i0)/8): i0 >= 0 and i0 <= 1023 and 8e0 <= -1 + i0 and 8e0 >= -7 + i0) };
+; CHECK:     Scattering :=
+; CHECK:         { Stmt_if_then[i0] -> scattering[0, i0, 0] };
+; CHECK:     ReadAccess := [Reduction Type: +]
+; CHECK:         { Stmt_if_then[i0] -> MemRef_A[i0] };
+; CHECK:     MustWriteAccess :=  [Reduction Type: +]
+; CHECK:         { Stmt_if_then[i0] -> MemRef_A[i0] };
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @jd_and(i32* %A) {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry ]
+  %exitcond = icmp ne i64 %indvars.iv, 1024
+  br i1 %exitcond, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %tmp = trunc i64 %indvars.iv to i32
+  %rem1 = and i32 %tmp, 7
+  %tobool = icmp eq i32 %rem1, 0
+  br i1 %tobool, label %if.end, label %if.then
+
+if.then:                                          ; preds = %for.body
+  %arrayidx = getelementptr inbounds i32* %A, i64 %indvars.iv
+  %tmp2 = load i32* %arrayidx, align 4
+  %add = add nsw i32 %tmp2, 1
+  store i32 %add, i32* %arrayidx, align 4
+  br label %if.end
+
+if.end:                                           ; preds = %for.body, %if.then
+  br label %for.inc
+
+for.inc:                                          ; preds = %if.end
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}
+
+define void @jd_srem(i32* %A) {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry ]
+  %exitcond = icmp ne i64 %indvars.iv, 1024
+  br i1 %exitcond, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %rem = srem i64 %indvars.iv, 8
+  %tobool = icmp eq i64 %rem, 0
+  br i1 %tobool, label %if.end, label %if.then
+
+if.then:                                          ; preds = %for.body
+  %arrayidx = getelementptr inbounds i32* %A, i64 %indvars.iv
+  %tmp2 = load i32* %arrayidx, align 4
+  %add = add nsw i32 %tmp2, 1
+  store i32 %add, i32* %arrayidx, align 4
+  br label %if.end
+
+if.end:                                           ; preds = %for.body, %if.then
+  br label %for.inc
+
+for.inc:                                          ; preds = %if.end
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}

test/ScopInfo/reduction_alternating_base.ll

 ; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
 ;
-; FIXME: We cannot detect this SCoP yet but as soon as we can we should check
-;        that the reduction is detected!
-;
-; CHECK-NOT: Scattering
+; CHECK: ReadAccess := [Reduction Type: +]
+; CHECK:   { Stmt_for_body[i0] -> MemRef_A[o0] : exists (e0 = floor((-i0 + o0)/2): 2e0 = -i0 + o0 and o0 <= 1 and o0 >= 0) };
+; CHECK: MustWriteAccess :=  [Reduction Type: +]
+; CHECK:   { Stmt_for_body[i0] -> MemRef_A[o0] : exists (e0 = floor((-i0 + o0)/2): 2e0 = -i0 + o0 and o0 <= 1 and o0 >= 0) };
 ;
 ;    void f(int *A) {
 ;      for (int i = 0; i < 1024; i++)
 ;        A[i % 2] += i;
 ;    }
 ;
 target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-n32-S64"