Index: polly/trunk/include/polly/CodeGen/IslExprBuilder.h =================================================================== --- polly/trunk/include/polly/CodeGen/IslExprBuilder.h +++ polly/trunk/include/polly/CodeGen/IslExprBuilder.h @@ -18,6 +18,10 @@ #include +namespace llvm { +class SCEVExpander; +} + namespace polly { /// @brief LLVM-IR generator for isl_ast_expr[essions] @@ -89,8 +93,11 @@ /// 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 @@ PollyIRBuilder &Builder; std::map &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); Index: polly/trunk/lib/Analysis/ScopDetection.cpp =================================================================== --- polly/trunk/lib/Analysis/ScopDetection.cpp +++ polly/trunk/lib/Analysis/ScopDetection.cpp @@ -202,12 +202,6 @@ 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"); Index: polly/trunk/lib/CodeGen/IslCodeGeneration.cpp =================================================================== --- polly/trunk/lib/CodeGen/IslCodeGeneration.cpp +++ polly/trunk/lib/CodeGen/IslCodeGeneration.cpp @@ -57,8 +57,12 @@ 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 @@ 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::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 @@ Scev = (const SCEV *)isl_id_get_user(Id); T = dyn_cast(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); Index: polly/trunk/lib/CodeGen/IslExprBuilder.cpp =================================================================== --- polly/trunk/lib/CodeGen/IslExprBuilder.cpp +++ polly/trunk/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 @@ 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 @@ 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); Index: polly/trunk/test/Isl/CodeGen/aliasing_multidimensional_access.ll =================================================================== --- polly/trunk/test/Isl/CodeGen/aliasing_multidimensional_access.ll +++ polly/trunk/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 +}