OpenMP codegen: support generation of multi-dimensional access functions

When computing the index expressions for new, multi-dimensional memory accesses
these new index expressions may reference original llvm::Values that are not
transfered into the OpenMP subfunction. Using GlobalMap we now replace
references to such values with the rewritten values that have e.g. been passed
to the OpenMP subfunction.

llvm-svn: 246923

4 files changed, 92 insertions, 5 deletions

diff --git a/polly/include/polly/CodeGen/IslExprBuilder.h b/polly/include/polly/CodeGen/IslExprBuilder.h
index c08e9cc75da..b1011347b5c 100644
--- a/polly/include/polly/CodeGen/IslExprBuilder.h
+++ b/polly/include/polly/CodeGen/IslExprBuilder.h
@@ -81,6 +81,7 @@ class IslExprBuilder {
 public:
   /// @brief A map from isl_ids to llvm::Values.
   typedef llvm::MapVector<isl_id *, llvm::Value *> IDToValueTy;
+  typedef llvm::DenseMap<const llvm::Value *, llvm::Value *> ValueToValueMap;
 
   /// @brief Construct an IslExprBuilder.
   ///
@@ -93,10 +94,11 @@ public:
   ///                  specifies the LLVM-IR Values that correspond to these
   ///                  parameters and variables.
   IslExprBuilder(Scop &S, PollyIRBuilder &Builder, IDToValueTy &IDToValue,
-                 const llvm::DataLayout &DL, llvm::ScalarEvolution &SE,
-                 llvm::DominatorTree &DT, llvm::LoopInfo &LI)
-      : S(S), Builder(Builder), IDToValue(IDToValue), DL(DL), SE(SE), DT(DT),
-        LI(LI) {}
+                 ValueToValueMap &GlobalMap, const llvm::DataLayout &DL,
+                 llvm::ScalarEvolution &SE, llvm::DominatorTree &DT,
+                 llvm::LoopInfo &LI)
+      : S(S), Builder(Builder), IDToValue(IDToValue), GlobalMap(GlobalMap),
+        DL(DL), SE(SE), DT(DT), LI(LI) {}
 
   /// @brief Create LLVM-IR for an isl_ast_expr[ession].
   ///
@@ -127,6 +129,7 @@ private:
 
   PollyIRBuilder &Builder;
   IDToValueTy &IDToValue;
+  ValueToValueMap &GlobalMap;
 
   const llvm::DataLayout &DL;
   llvm::ScalarEvolution &SE;
diff --git a/polly/include/polly/CodeGen/IslNodeBuilder.h b/polly/include/polly/CodeGen/IslNodeBuilder.h
index 6f0268eba52..221d8bd0e08 100644
--- a/polly/include/polly/CodeGen/IslNodeBuilder.h
+++ b/polly/include/polly/CodeGen/IslNodeBuilder.h
@@ -31,7 +31,7 @@ public:
                  const DataLayout &DL, LoopInfo &LI, ScalarEvolution &SE,
                  DominatorTree &DT, Scop &S)
       : S(S), Builder(Builder), Annotator(Annotator),
-        ExprBuilder(S, Builder, IDToValue, DL, SE, DT, LI),
+        ExprBuilder(S, Builder, IDToValue, ValueMap, DL, SE, DT, LI),
         BlockGen(Builder, LI, SE, DT, ScalarMap, PHIOpMap, EscapeMap, ValueMap,
                  &ExprBuilder),
         RegionGen(BlockGen), P(P), DL(DL), LI(LI), SE(SE), DT(DT) {}
diff --git a/polly/lib/CodeGen/IslExprBuilder.cpp b/polly/lib/CodeGen/IslExprBuilder.cpp
index 3eb64884ca9..01512867ebb 100644
--- a/polly/lib/CodeGen/IslExprBuilder.cpp
+++ b/polly/lib/CodeGen/IslExprBuilder.cpp
@@ -112,6 +112,10 @@ Value *IslExprBuilder::createAccessAddress(isl_ast_expr *Expr) {
 
   const ScopArrayInfo *SAI = ScopArrayInfo::getFromId(BaseId);
   Base = SAI->getBasePtr();
+
+  if (auto NewBase = GlobalMap.lookup(Base))
+    Base = NewBase;
+
   assert(Base->getType()->isPointerTy() && "Access base should be a pointer");
   StringRef BaseName = Base->getName();
 
@@ -148,6 +152,8 @@ Value *IslExprBuilder::createAccessAddress(isl_ast_expr *Expr) {
       break;
 
     const SCEV *DimSCEV = SAI->getDimensionSize(u - 1);
+
+    DimSCEV = SCEVParameterRewriter::rewrite(DimSCEV, SE, GlobalMap);
     Value *DimSize =
         expandCodeFor(S, SE, DL, "polly", DimSCEV, DimSCEV->getType(),
                       Builder.GetInsertPoint());
diff --git a/polly/test/Isl/CodeGen/OpenMP/new_multidim_access.ll b/polly/test/Isl/CodeGen/OpenMP/new_multidim_access.ll
new file mode 100644
index 00000000000..bba5f0c3642
--- /dev/null
+++ b/polly/test/Isl/CodeGen/OpenMP/new_multidim_access.ll
@@ -0,0 +1,78 @@
+; RUN: opt %loadPolly -polly-import-jscop -polly-import-jscop-dir=%S \
+; RUN:                -analyze < %s | FileCheck %s
+
+; RUN: opt %loadPolly -polly-import-jscop -polly-import-jscop-dir=%S \
+; RUN:                -polly-codegen -polly-no-early-exit -S < %s \
+; RUN:                -polly-parallel \
+; RUN:                | FileCheck %s -check-prefix=IR
+
+;    void new_multidim_access(long n, long m, float A[][m]) {
+;      for (long i = 0; i < n; i++)
+;        for (long j = 0; j < 100; j++)
+;          A[i][2 * j] += i + j;
+;    }
+
+; CHECK:  ReadAccess :=       [Reduction Type: NONE] [Scalar: 0]
+; CHECK:         [n, m] -> { Stmt_bb4[i0, i1] -> MemRef_A[i0, 2i1] };
+; CHECK:    new: [n, m] -> { Stmt_bb4[i0, i1] -> MemRef_A[i0, 13 + i1] };
+; CHECK:  MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK:         [n, m] -> { Stmt_bb4[i0, i1] -> MemRef_A[i0, 2i1] };
+; CHECK:    new: [n, m] -> { Stmt_bb4[i0, i1] -> MemRef_A[i0, 43 + i1] };
+
+; IR: %polly.access.mul. = mul i64 %polly.indvar, %3
+; IR: %11 = add nsw i64 %polly.indvar5, 13
+; IR: %polly.access.add. = add i64 %polly.access.mul., %11
+; IR: %polly.access. = getelementptr float, float* %5, i64 %polly.access.add.
+; IR: %tmp10_p_scalar_ = load float, float* %polly.access., align 4, !alias.scope !0, !noalias !2, !llvm.mem.parallel_loop_access !3
+
+; IR: %polly.access.mul.9 = mul i64 %polly.indvar, %3
+; IR: %12 = add nsw i64 %polly.indvar5, 43
+; IR: %polly.access.add.10 = add i64 %polly.access.mul.9, %12
+; IR: %polly.access.11 = getelementptr float, float* %5, i64 %polly.access.add.10
+; IR: store float %p_tmp11, float* %polly.access.11, align 4, !alias.scope !0, !noalias !2, !llvm.mem.parallel_loop_access !3
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @new_multidim_access(i64 %n, i64 %m, float* %A) {
+bb:
+  br label %bb1
+
+bb1:                                              ; preds = %bb15, %bb
+  %i.0 = phi i64 [ 0, %bb ], [ %tmp16, %bb15 ]
+  %tmp = icmp slt i64 %i.0, %n
+  br i1 %tmp, label %bb2, label %bb17
+
+bb2:                                              ; preds = %bb1
+  br label %bb3
+
+bb3:                                              ; preds = %bb12, %bb2
+  %j.0 = phi i64 [ 0, %bb2 ], [ %tmp13, %bb12 ]
+  %exitcond = icmp ne i64 %j.0, 100
+  br i1 %exitcond, label %bb4, label %bb14
+
+bb4:                                              ; preds = %bb3
+  %tmp5 = add nsw i64 %i.0, %j.0
+  %tmp6 = sitofp i64 %tmp5 to float
+  %tmp7 = shl nsw i64 %j.0, 1
+  %tmp8 = mul nsw i64 %i.0, %m
+  %.sum = add i64 %tmp8, %tmp7
+  %tmp9 = getelementptr inbounds float, float* %A, i64 %.sum
+  %tmp10 = load float, float* %tmp9, align 4
+  %tmp11 = fadd float %tmp10, %tmp6
+  store float %tmp11, float* %tmp9, align 4
+  br label %bb12
+
+bb12:                                             ; preds = %bb4
+  %tmp13 = add nsw i64 %j.0, 1
+  br label %bb3
+
+bb14:                                             ; preds = %bb3
+  br label %bb15
+
+bb15:                                             ; preds = %bb14
+  %tmp16 = add nsw i64 %i.0, 1
+  br label %bb1
+
+bb17:                                             ; preds = %bb1
+  ret void
+}