[Polly] Allow multidimensional accesses in the IslExprBuilder.

[jdoerfert]

Summary

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

[grosser]

Very nice (both the itself patch and the fact that it exists)

One miner stylistic comment. Feel free to adapt it or not.

lib/Analysis/ScopDetection.cpp

210

Nice!!

lib/CodeGen/IslCodeGeneration.cpp

58–65

Instead of using new * here, could we change the type to "SCEVExpander Rewriter" and
ititialize it with "Rewriter(SE, "polly"))"? This would remove the need for the delete &Rewriter?

lib/CodeGen/IslExprBuilder.cpp

106

Nice!

[jdoerfert]

updated according to comments

[jdoerfert]

Closed by commit rL219078 (authored by @jdoerfert).

include/polly/CodeGen/IslExprBuilder.h

 #define POLLY_ISL_EXPR_BUILDER_H
 
 #include "polly/CodeGen/IRBuilder.h"
 
 #include "isl/ast.h"
 
 #include <map>
 
+namespace llvm {
+class SCEVExpander;
+}
+
 namespace polly {
 
 /// @brief LLVM-IR generator for isl_ast_expr[essions]
 ///
 /// This generator generates LLVM-IR that performs the computation described by
 /// an isl_ast_expr[ession].
 ///
 /// Example:
public:
   /// @param Builder The IRBuilder used to construct the isl_ast_expr[ession].
   ///                The insert location of this IRBuilder defines WHERE the
   ///                corresponding LLVM-IR is generated.
   ///
   /// @param IDToValue The isl_ast_expr[ession] may reference parameters or
   ///                  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].
   ///
   /// @param Expr The ast expression for which we generate LLVM-IR.
   ///
   /// @return The llvm::Value* containing the result of the computation.
   llvm::Value *create(__isl_take isl_ast_expr *Expr);
 
public:
   /// @param Expr The expression for which to find the type.
   /// @return The type with which the expression should be computed.
   llvm::IntegerType *getType(__isl_keep isl_ast_expr *Expr);
 
 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);
   llvm::Value *createOpBin(__isl_take isl_ast_expr *Expr);
   llvm::Value *createOpNAry(__isl_take isl_ast_expr *Expr);
   llvm::Value *createOpSelect(__isl_take isl_ast_expr *Expr);
   llvm::Value *createOpICmp(__isl_take isl_ast_expr *Expr);
   llvm::Value *createOpBoolean(__isl_take isl_ast_expr *Expr);
   llvm::Value *createId(__isl_take isl_ast_expr *Expr);
   llvm::Value *createInt(__isl_take isl_ast_expr *Expr);
   llvm::Value *createOpAddressOf(__isl_take isl_ast_expr *Expr);
   llvm::Value *createAccessAddress(__isl_take isl_ast_expr *Expr);
 };
 }
 
 #endif

lib/Analysis/ScopDetection.cpp

if (!PollyUseRuntimeAliasChecks)
     return;
 
   // Disable runtime alias checks if we ignore aliasing all together.
   if (IgnoreAliasing) {
     PollyUseRuntimeAliasChecks = false;
     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");
     PollyUseRuntimeAliasChecks = false;
   }
 
 #ifdef CLOOG_FOUND
   if (PollyCodeGenChoice == CODEGEN_CLOOG) {

lib/CodeGen/IslCodeGeneration.cpp

 
 using namespace polly;
 using namespace llvm;
 
 #define DEBUG_TYPE "polly-codegen-isl"
 
 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);
   void addParameters(__isl_take isl_set *Context);
   void create(__isl_take isl_ast_node *Node);
   IslExprBuilder &getExprBuilder() { return ExprBuilder; }
 
 private:
   PollyIRBuilder &Builder;
   ScopAnnotator &Annotator;
+
+  /// @brief A SCEVExpander to create llvm values from SCEVs.
+  SCEVExpander *Rewriter;
+
   IslExprBuilder ExprBuilder;
   Pass *P;
   LoopInfo &LI;
   ScalarEvolution &SE;
   DominatorTree &DT;
 
   // This maps an isl_id* to the Value* it has in the generated program. For now
   // on, the only isl_ids that are stored here are the newly calculated loop
case isl_ast_node_block:
     createBlock(Node);
     return;
   }
 
   llvm_unreachable("Unknown isl_ast_node type");
 }
 
 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;
     const SCEV *Scev;
     IntegerType *T;
     Instruction *InsertLocation;
 
     Id = isl_set_get_dim_id(Context, isl_dim_param, i);
     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);
   }
 
   isl_set_free(Context);
 }
 

lib/CodeGen/IslExprBuilder.cpp

 //===------ IslExprBuilder.cpp ----- Code generate isl AST expressions ----===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 //===----------------------------------------------------------------------===//
 
 #include "polly/CodeGen/IslExprBuilder.h"
 
 #include "polly/ScopInfo.h"
 #include "polly/Support/GICHelper.h"
 
+#include "llvm/Analysis/ScalarEvolutionExpander.h"
 #include "llvm/Support/Debug.h"
 
 using namespace llvm;
 using namespace polly;
 
 Type *IslExprBuilder::getWidestType(Type *T1, Type *T2) {
   assert(isa<IntegerType>(T1) && isa<IntegerType>(T2));
 

 Value *IslExprBuilder::createAccessAddress(isl_ast_expr *Expr) {
   assert(isl_ast_expr_get_type(Expr) == isl_ast_expr_op &&
          "isl ast expression not of type isl_ast_op");
   assert(isl_ast_expr_get_op_type(Expr) == isl_ast_op_access &&
          "not an access isl ast expression");
   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;
 
   BaseExpr = isl_ast_expr_get_op_arg(Expr, 0);
   BaseId = isl_ast_expr_get_id(BaseExpr);
   isl_ast_expr_free(BaseExpr);
 
   const ScopArrayInfo *SAI = ScopArrayInfo::getFromId(BaseId);
   Base = SAI->getBasePtr();
   assert(Base->getType()->isPointerTy() && "Access base should be a pointer");
   const Twine &BaseName = Base->getName();
 
   if (Base->getType() != SAI->getType())
     Base = Builder.CreateBitCast(Base, SAI->getType(),
                                  "polly.access.cast." + BaseName);
 
-  IndexOp = create(isl_ast_expr_get_op_arg(Expr, 1));
-  assert(IndexOp->getType()->isIntegerTy() &&
+  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);
 
   isl_ast_expr_free(Expr);
   return Access;
 }
 
 Value *IslExprBuilder::createOpAccess(isl_ast_expr *Expr) {
   Value *Addr = createAccessAddress(Expr);

test/Isl/CodeGen/aliasing_multidimensional_access.ll

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