Allow multidimensional accesses in the IslExprBuilder.

  This resolved the issues with delinearized accesses that might alias,
  thus delinearization doesn't deactivate runtime alias checks anymore.

Differential Revision: http://reviews.llvm.org/D5614

llvm-svn: 219078

5 files changed, 123 insertions, 19 deletions

diff --git a/polly/include/polly/CodeGen/IslExprBuilder.h b/polly/include/polly/CodeGen/IslExprBuilder.h
index 99991fd28c2..eec45dd2cd4 100644
--- a/polly/include/polly/CodeGen/IslExprBuilder.h
+++ b/polly/include/polly/CodeGen/IslExprBuilder.h
@@ -18,6 +18,10 @@
 
 #include <map>
 
+namespace llvm {
+class SCEVExpander;
+}
+
 namespace polly {
 
 /// @brief LLVM-IR generator for isl_ast_expr[essions]
@@ -89,8 +93,11 @@ public:
   ///                  variables (identified by an isl_id). The IDTOValue map
   ///                  specifies the LLVM-IR Values that correspond to these
   ///                  parameters and variables.
-  IslExprBuilder(PollyIRBuilder &Builder, IDToValueTy &IDToValue)
-      : Builder(Builder), IDToValue(IDToValue) {}
+  /// @param Expander  A SCEVExpander to create the indices for multi
+  ///                  dimensional accesses.
+  IslExprBuilder(PollyIRBuilder &Builder, IDToValueTy &IDToValue,
+                 llvm::SCEVExpander &Expander)
+      : Builder(Builder), IDToValue(IDToValue), Expander(Expander) {}
 
   /// @brief Create LLVM-IR for an isl_ast_expr[ession].
   ///
@@ -120,6 +127,9 @@ private:
   PollyIRBuilder &Builder;
   std::map<isl_id *, llvm::Value *> &IDToValue;
 
+  /// @brief A SCEVExpander to translate dimension sizes to llvm values.
+  llvm::SCEVExpander &Expander;
+
   llvm::Value *createOp(__isl_take isl_ast_expr *Expr);
   llvm::Value *createOpUnary(__isl_take isl_ast_expr *Expr);
   llvm::Value *createOpAccess(__isl_take isl_ast_expr *Expr);
diff --git a/polly/lib/Analysis/ScopDetection.cpp b/polly/lib/Analysis/ScopDetection.cpp
index ac20cd8d285..e25d76e15b0 100644
--- a/polly/lib/Analysis/ScopDetection.cpp
+++ b/polly/lib/Analysis/ScopDetection.cpp
@@ -202,12 +202,6 @@ ScopDetection::ScopDetection() : FunctionPass(ID) {
     return;
   }
 
-  if (PollyDelinearize) {
-    DEBUG(errs() << "WARNING: We disable runtime alias checks as "
-                    "delinearization is enabled.\n");
-    PollyUseRuntimeAliasChecks = false;
-  }
-
   if (AllowNonAffine) {
     DEBUG(errs() << "WARNING: We disable runtime alias checks as non affine "
                     "accesses are enabled.\n");
diff --git a/polly/lib/CodeGen/IslCodeGeneration.cpp b/polly/lib/CodeGen/IslCodeGeneration.cpp
index 7b4b76091c0..d72298b54eb 100644
--- a/polly/lib/CodeGen/IslCodeGeneration.cpp
+++ b/polly/lib/CodeGen/IslCodeGeneration.cpp
@@ -57,8 +57,12 @@ class IslNodeBuilder {
 public:
   IslNodeBuilder(PollyIRBuilder &Builder, ScopAnnotator &Annotator, Pass *P,
                  LoopInfo &LI, ScalarEvolution &SE, DominatorTree &DT)
-      : Builder(Builder), Annotator(Annotator), ExprBuilder(Builder, IDToValue),
-        P(P), LI(LI), SE(SE), DT(DT) {}
+      : Builder(Builder), Annotator(Annotator),
+        Rewriter(new SCEVExpander(SE, "polly")),
+        ExprBuilder(Builder, IDToValue, *Rewriter), P(P), LI(LI), SE(SE),
+        DT(DT) {}
+
+  ~IslNodeBuilder() { delete Rewriter; }
 
   /// @brief Add the mappings from array id's to array llvm::Value's.
   void addMemoryAccesses(Scop &S);
@@ -69,6 +73,10 @@ public:
 private:
   PollyIRBuilder &Builder;
   ScopAnnotator &Annotator;
+
+  /// @brief A SCEVExpander to create llvm values from SCEVs.
+  SCEVExpander *Rewriter;
+
   IslExprBuilder ExprBuilder;
   Pass *P;
   LoopInfo &LI;
@@ -532,7 +540,6 @@ void IslNodeBuilder::create(__isl_take isl_ast_node *Node) {
 }
 
 void IslNodeBuilder::addParameters(__isl_take isl_set *Context) {
-  SCEVExpander Rewriter(SE, "polly");
 
   for (unsigned i = 0; i < isl_set_dim(Context, isl_dim_param); ++i) {
     isl_id *Id;
@@ -544,7 +551,7 @@ void IslNodeBuilder::addParameters(__isl_take isl_set *Context) {
     Scev = (const SCEV *)isl_id_get_user(Id);
     T = dyn_cast<IntegerType>(Scev->getType());
     InsertLocation = --(Builder.GetInsertBlock()->end());
-    Value *V = Rewriter.expandCodeFor(Scev, T, InsertLocation);
+    Value *V = Rewriter->expandCodeFor(Scev, T, InsertLocation);
     IDToValue[Id] = V;
 
     isl_id_free(Id);
diff --git a/polly/lib/CodeGen/IslExprBuilder.cpp b/polly/lib/CodeGen/IslExprBuilder.cpp
index 4ccdb003d34..158288dca46 100644
--- a/polly/lib/CodeGen/IslExprBuilder.cpp
+++ b/polly/lib/CodeGen/IslExprBuilder.cpp
@@ -14,6 +14,7 @@
 #include "polly/ScopInfo.h"
 #include "polly/Support/GICHelper.h"
 
+#include "llvm/Analysis/ScalarEvolutionExpander.h"
 #include "llvm/Support/Debug.h"
 
 using namespace llvm;
@@ -100,10 +101,6 @@ Value *IslExprBuilder::createAccessAddress(isl_ast_expr *Expr) {
   assert(isl_ast_expr_get_op_n_arg(Expr) >= 2 &&
          "We need at least two operands to create a member access.");
 
-  // TODO: Support for multi-dimensional array.
-  assert(isl_ast_expr_get_op_n_arg(Expr) == 2 &&
-         "Multidimensional access functions are not supported yet");
-
   Value *Base, *IndexOp, *Access;
   isl_ast_expr *BaseExpr;
   isl_id *BaseId;
@@ -121,9 +118,27 @@ Value *IslExprBuilder::createAccessAddress(isl_ast_expr *Expr) {
     Base = Builder.CreateBitCast(Base, SAI->getType(),
                                  "polly.access.cast." + BaseName);
 
-  IndexOp = create(isl_ast_expr_get_op_arg(Expr, 1));
-  assert(IndexOp->getType()->isIntegerTy() &&
-         "Access index should be an integer");
+  IndexOp = nullptr;
+  for (unsigned u = 1, e = isl_ast_expr_get_op_n_arg(Expr); u < e; u++) {
+    Value *NextIndex = create(isl_ast_expr_get_op_arg(Expr, u));
+    assert(NextIndex->getType()->isIntegerTy() &&
+           "Access index should be an integer");
+
+    if (!IndexOp)
+      IndexOp = NextIndex;
+    else
+      IndexOp = Builder.CreateAdd(IndexOp, NextIndex);
+
+    // For every but the last dimension multiply the size, for the last
+    // dimension we can exit the loop.
+    if (u + 1 >= e)
+      break;
+
+    const SCEV *DimSCEV = SAI->getDimensionSize(u - 1);
+    Value *DimSize = Expander.expandCodeFor(DimSCEV, IndexOp->getType(),
+                                            Builder.GetInsertPoint());
+    IndexOp = Builder.CreateMul(IndexOp, DimSize);
+  }
 
   Access = Builder.CreateGEP(Base, IndexOp, "polly.access." + BaseName);
 
diff --git a/polly/test/Isl/CodeGen/aliasing_multidimensional_access.ll b/polly/test/Isl/CodeGen/aliasing_multidimensional_access.ll
new file mode 100644
index 00000000000..06306ceb07e
--- /dev/null
+++ b/polly/test/Isl/CodeGen/aliasing_multidimensional_access.ll
@@ -0,0 +1,78 @@
+; RUN: opt %loadPolly -S -polly-codegen-isl -polly-code-generator=isl -polly-delinearize < %s | FileCheck %s
+;
+; Check that we calculate the maximal access into array A correctly.
+;
+; CHECK:  %[[TMP0:[._0-9a-zA-Z]*]] = mul i64 99, %m
+; CHECK:  %[[TMP1:[._0-9a-zA-Z]*]] = add i64 %[[TMP0]], 149
+; CHECK:  %[[TMP2:[._0-9a-zA-Z]*]] = mul i64 %[[TMP1]], %p
+; CHECK:  %[[TMP3:[._0-9a-zA-Z]*]] = add i64 %[[TMP2]], 150
+; CHECK:  %polly.access.A{{[0-9]*}} = getelementptr double* %A, i64 %[[TMP3]]
+;
+;    void foo(long n, long m, long p, double A[n][m][p], int *B) {
+;      for (long i = 0; i < 100; i++)
+;        for (long j = 0; j < 150; j++)
+;          for (long k = 0; k < 150; k++)
+;            A[i][j][k] = B[k];
+;    }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @foo(i64 %n, i64 %m, i64 %p, double* %A, i32* %B) {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc13, %entry
+  %i.0 = phi i64 [ 0, %entry ], [ %inc14, %for.inc13 ]
+  %exitcond2 = icmp ne i64 %i.0, 100
+  br i1 %exitcond2, label %for.body, label %for.end15
+
+for.body:                                         ; preds = %for.cond
+  br label %for.cond1
+
+for.cond1:                                        ; preds = %for.inc10, %for.body
+  %j.0 = phi i64 [ 0, %for.body ], [ %inc11, %for.inc10 ]
+  %exitcond1 = icmp ne i64 %j.0, 150
+  br i1 %exitcond1, label %for.body3, label %for.end12
+
+for.body3:                                        ; preds = %for.cond1
+  br label %for.cond4
+
+for.cond4:                                        ; preds = %for.inc, %for.body3
+  %k.0 = phi i64 [ 0, %for.body3 ], [ %inc, %for.inc ]
+  %exitcond = icmp ne i64 %k.0, 150
+  br i1 %exitcond, label %for.body6, label %for.end
+
+for.body6:                                        ; preds = %for.cond4
+  %arrayidx = getelementptr inbounds i32* %B, i64 %k.0
+  %tmp3 = load i32* %arrayidx, align 2
+  %conv = sitofp i32 %tmp3 to double
+  %tmp4 = mul nuw i64 %m, %p
+  %tmp5 = mul nsw i64 %i.0, %tmp4
+  %tmp6 = mul nsw i64 %j.0, %p
+  %arrayidx7.sum = add i64 %tmp5, %tmp6
+  %arrayidx8.sum = add i64 %arrayidx7.sum, %k.0
+  %arrayidx9 = getelementptr inbounds double* %A, i64 %arrayidx8.sum
+  store double %conv, double* %arrayidx9, align 8
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body6
+  %inc = add nsw i64 %k.0, 1
+  br label %for.cond4
+
+for.end:                                          ; preds = %for.cond4
+  br label %for.inc10
+
+for.inc10:                                        ; preds = %for.end
+  %inc11 = add nsw i64 %j.0, 1
+  br label %for.cond1
+
+for.end12:                                        ; preds = %for.cond1
+  br label %for.inc13
+
+for.inc13:                                        ; preds = %for.end12
+  %inc14 = add nsw i64 %i.0, 1
+  br label %for.cond
+
+for.end15:                                        ; preds = %for.cond
+  ret void
+}