Strip constant factors from parameters

[jdoerfert]

Summary

We will strip the constant factor of a parameter befor we add it to
the SCoP. As a result the access functions are simplified, e.g., for
the attached test case.

[grosser]

Hi Johannes,

this LGTM. I added some minor comments.

Tobias

include/polly/Support/SCEVValidator.h

55

multiplication

57

multiplication

lib/Analysis/ScopInfo.cpp

201

Maybe it is worth to adding a comment that explains why we can not get an infinitive recursion here, where ConstantAndLeftOverPair.second always contains a multiplication and on which we call visitMulExpr again. (The answer seems to be that in visit(Expr) we should stop and realize that the multiplication expression is a parameter expression.)

test/ScopInfo/constant_factor_in_parameter.ll

4

existentially

[jdoerfert]

Thanks, commited in r233501.

• msg-20045-78.dat219 BDownload

[jdoerfert]

commited in r233501.

include/polly/Support/SCEVValidator.h

 bool hasScalarDepsInsideRegion(const llvm::SCEV *S, const llvm::Region *R);
 bool isAffineExpr(const llvm::Region *R, const llvm::SCEV *Expression,
                   llvm::ScalarEvolution &SE,
                   const llvm::Value *BaseAddress = 0);
 std::vector<const llvm::SCEV *>
 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

lib/Analysis/ScopInfo.cpp

__isl_give isl_pw_aff *SCEVAffinator::visitAddExpr(const SCEVAddExpr *Expr) {
   }
 
   // TODO: Check for NSW and NUW.
 
   return Sum;
 }
 
 __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) {
   llvm_unreachable("SCEVUDivExpr not yet supported");
 }
 
 __isl_give isl_pw_aff *
 SCEVAffinator::visitAddRecExpr(const SCEVAddRecExpr *Expr) {

 void Scop::setContext(__isl_take isl_set *NewContext) {
   NewContext = isl_set_align_params(NewContext, isl_set_get_space(Context));
   isl_set_free(Context);
   Context = NewContext;
 }
 
 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;
 
     int dimension = Parameters.size();
 
     Parameters.push_back(Parameter);
     ParameterIds[Parameter] = dimension;
   }

lib/Support/SCEVValidator.cpp

std::vector<const SCEV *> getParamsInAffineExpr(const Region *R,
   if (isa<SCEVCouldNotCompute>(Expr))
     return std::vector<const SCEV *>();
 
   SCEVValidator Validator(R, SE, BaseAddress);
   ValidatorResult Result = Validator.visit(Expr);
 
   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);
+}
 }

test/ScopInfo/constant_factor_in_parameter.ll

+; 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
+}

test/ScopInfo/multidim_single_and_multidim_array.ll

 ;
 ; In previous versions of Polly, the second access was detected as single
 ; dimensional access whereas the first one was detected as multi-dimensional.
 ; This test case checks that we now consistently delinearize the array accesses.
 
 ; 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 :=
 ; DELIN:      [n] -> { Stmt_for_i_1[i0] -> MemRef_X[i0, 0] };
 ; DELIN: Stmt_for_i_2
 ; DELIN:   MustWriteAccess :=
 ; DELIN:      [n] -> { Stmt_for_i_2[i0] -> MemRef_X[-1 + n, i0] };