Index: include/polly/Support/SCEVValidator.h
===================================================================
--- include/polly/Support/SCEVValidator.h
+++ include/polly/Support/SCEVValidator.h
@@ -51,6 +51,15 @@
 getParamsInAffineExpr(const llvm::Region *R, const llvm::SCEV *Expression,
                       llvm::ScalarEvolution &SE,
                       const llvm::Value *BaseAddress = 0);
+
+/// @brief Extract the constant factors from the multiplaction @p M.
+///
+/// @param M  A SCEV multipilcation.
+/// @param SE The ScalarEvolution analysis to create new SCEVs.
+///
+/// @returns The constant factor in @p M and the rest of @p M.
+std::pair<const llvm::SCEV *, const llvm::SCEV *>
+extractConstantFactor(const llvm::SCEV *M, llvm::ScalarEvolution &SE);
 }
 
 #endif
Index: lib/Analysis/ScopInfo.cpp
===================================================================
--- lib/Analysis/ScopInfo.cpp
+++ lib/Analysis/ScopInfo.cpp
@@ -194,22 +194,11 @@
 }
 
 __isl_give isl_pw_aff *SCEVAffinator::visitMulExpr(const SCEVMulExpr *Expr) {
-  isl_pw_aff *Product = visit(Expr->getOperand(0));
-
-  for (int i = 1, e = Expr->getNumOperands(); i < e; ++i) {
-    isl_pw_aff *NextOperand = visit(Expr->getOperand(i));
-
-    if (!isl_pw_aff_is_cst(Product) && !isl_pw_aff_is_cst(NextOperand)) {
-      isl_pw_aff_free(Product);
-      isl_pw_aff_free(NextOperand);
-      return nullptr;
-    }
-
-    Product = isl_pw_aff_mul(Product, NextOperand);
-  }
-
-  // TODO: Check for NSW and NUW.
-  return Product;
+  // Divide Expr into a constant part and the rest. Then visit both and multiply
+  // the result to obtain the representation for Expr.
+  auto ConstantAndLeftOverPair = extractConstantFactor(Expr, *S->getSE());
+  return isl_pw_aff_mul(visit(ConstantAndLeftOverPair.first),
+                        visit(ConstantAndLeftOverPair.second));
 }
 
 __isl_give isl_pw_aff *SCEVAffinator::visitUDivExpr(const SCEVUDivExpr *Expr) {
@@ -1246,6 +1235,7 @@
 
 void Scop::addParams(std::vector<const SCEV *> NewParameters) {
   for (const SCEV *Parameter : NewParameters) {
+    Parameter = extractConstantFactor(Parameter, *SE).second;
     if (ParameterIds.find(Parameter) != ParameterIds.end())
       continue;
 
Index: lib/Support/SCEVValidator.cpp
===================================================================
--- lib/Support/SCEVValidator.cpp
+++ lib/Support/SCEVValidator.cpp
@@ -562,4 +562,23 @@
 
   return Result.getParameters();
 }
+
+std::pair<const SCEV *, const SCEV *>
+extractConstantFactor(const SCEV *S, ScalarEvolution &SE) {
+
+  const SCEV *LeftOver = SE.getConstant(S->getType(), 1);
+  const SCEV *ConstPart = SE.getConstant(S->getType(), 1);
+
+  const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(S);
+  if (!M)
+    return std::make_pair(ConstPart, S);
+
+  for (const SCEV *Op : M->operands())
+    if (isa<SCEVConstant>(Op))
+      ConstPart = SE.getMulExpr(ConstPart, Op);
+    else
+      LeftOver = SE.getMulExpr(LeftOver, Op);
+
+  return std::make_pair(ConstPart, LeftOver);
+}
 }
Index: test/ScopInfo/constant_factor_in_parameter.ll
===================================================================
--- /dev/null
+++ test/ScopInfo/constant_factor_in_parameter.ll
@@ -0,0 +1,43 @@
+; RUN: opt %loadPolly -analyze -polly-scops -polly-detect-unprofitable < %s | FileCheck %s
+;
+; Check that the constant part of the N * M * 4 expression is not part of the
+; parameter but explicit in the access function. This can avoid existenially
+; quantified variables, e.g., when computing the stride.
+;
+; CHECK: p1: (%N * %M)
+; CHECK: [N, p_1] -> { Stmt_for_body[i0] -> MemRef_A[4p_1 + i0] };
+;
+;    void f(int *A, int N, int M) {
+;      for (int i = 0; i < N; i++)
+;        A[i + N * M * 4] = i;
+;    }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @f(i32* %A, i32 %N, i32 %M) {
+entry:
+  %tmp = sext i32 %N to i64
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry ]
+  %cmp = icmp slt i64 %indvars.iv, %tmp
+  br i1 %cmp, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %mul = mul nsw i32 %N, %M
+  %mul2 = mul nsw i32 %mul, 4
+  %tmp2 = sext i32 %mul2 to i64
+  %tmp3 = add nsw i64 %indvars.iv, %tmp2
+  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %tmp3
+  %tmp4 = trunc i64 %indvars.iv to i32
+  store i32 %tmp4, i32* %arrayidx, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}
Index: test/ScopInfo/multidim_single_and_multidim_array.ll
===================================================================
--- test/ScopInfo/multidim_single_and_multidim_array.ll
+++ test/ScopInfo/multidim_single_and_multidim_array.ll
@@ -20,14 +20,14 @@
 ; CHECK-NOT: Stmt_for_i_1
 
 ; NONAFFINE: p0: %n
-; NONAFFINE: p1: (4 * (-1 + %n) * %n)
+; NONAFFINE: p1: ((-1 + %n) * %n)
 ; NONAFFINE: Statements {
 ; NONAFFINE:   Stmt_for_i_1
 ; NONAFFINE:         MayWriteAccess :=   [Reduction Type: NONE]
 ; NONAFFINE:             [n, p_1] -> { Stmt_for_i_1[i0] -> MemRef_X[o0] : o0 >= -2305843009213693952 and o0 <= 2305843009213693949 };
 ; NONAFFINE:   Stmt_for_i_2
 ; NONAFFINE:         MustWriteAccess :=  [Reduction Type: NONE]
-; NONAFFINE:             [n, p_1] -> { Stmt_for_i_2[i0] -> MemRef_X[o0] : 4o0 = p_1 + 4i0 };
+; NONAFFINE:             [n, p_1] -> { Stmt_for_i_2[i0] -> MemRef_X[p_1 + i0] };
 
 ; DELIN: Stmt_for_i_1
 ; DELIN:   MustWriteAccess :=