From e70449400f27b65d0222c054a2a463bfd973ded0 Mon Sep 17 00:00:00 2001 From: Johannes Doerfert Date: Tue, 24 Feb 2015 11:58:30 +0000 Subject: [PATCH] Add ScalarEvolution bounds to non-affine access functions llvm-svn: 230328 --- polly/include/polly/ScopInfo.h | 5 ++ polly/lib/Analysis/ScopInfo.cpp | 68 +++++++++++++++++----- .../NonAffine/non_affine_access_with_range.ll | 41 +++++++++++++ .../NonAffine/non_affine_access_with_range_2.ll | 54 +++++++++++++++++ .../ScopInfo/multidim_single_and_multidim_array.ll | 2 +- polly/test/ScopInfo/non_affine_access.ll | 2 +- polly/test/ScopInfo/non_affine_parametric_loop.ll | 2 +- 7 files changed, 157 insertions(+), 17 deletions(-) create mode 100644 polly/test/ScopInfo/NonAffine/non_affine_access_with_range.ll create mode 100644 polly/test/ScopInfo/NonAffine/non_affine_access_with_range_2.ll diff --git a/polly/include/polly/ScopInfo.h b/polly/include/polly/ScopInfo.h index 043ce1e..f60ddbc 100644 --- a/polly/include/polly/ScopInfo.h +++ b/polly/include/polly/ScopInfo.h @@ -209,6 +209,11 @@ private: void assumeNoOutOfBound(const IRAccess &Access); + /// @brief Compute bounds on an over approximated access relation. + /// + /// @param ElementSize The size of one element accessed. + void computeBoundsOnAccessRelation(unsigned ElementSize); + /// @brief Get the original access function as read from IR. isl_map *getOriginalAccessRelation() const; diff --git a/polly/lib/Analysis/ScopInfo.cpp b/polly/lib/Analysis/ScopInfo.cpp index cce635e..1c5a977 100644 --- a/polly/lib/Analysis/ScopInfo.cpp +++ b/polly/lib/Analysis/ScopInfo.cpp @@ -299,6 +299,27 @@ int SCEVAffinator::getLoopDepth(const Loop *L) { return L->getLoopDepth() - outerLoop->getLoopDepth(); } +/// @brief Add the bounds of @p Range to the set @p S for dimension @p dim. +static __isl_give isl_set *addRangeBoundsToSet(__isl_take isl_set *S, + const ConstantRange &Range, + int dim, + enum isl_dim_type type) { + isl_val *V; + isl_ctx *ctx = isl_set_get_ctx(S); + + V = isl_valFromAPInt(ctx, Range.getLower(), true); + isl_set *SLB = isl_set_lower_bound_val(isl_set_copy(S), type, dim, V); + + V = isl_valFromAPInt(ctx, Range.getUpper(), true); + V = isl_val_sub_ui(V, 1); + isl_set *SUB = isl_set_upper_bound_val(S, type, dim, V); + + if (Range.isSignWrappedSet()) + return isl_set_union(SLB, SUB); + else + return isl_set_intersect(SLB, SUB); +} + ScopArrayInfo::ScopArrayInfo(Value *BasePtr, Type *AccessType, isl_ctx *Ctx, const SmallVector &DimensionSizes) : BasePtr(BasePtr), AccessType(AccessType), DimensionSizes(DimensionSizes) { @@ -510,6 +531,36 @@ void MemoryAccess::assumeNoOutOfBound(const IRAccess &Access) { isl_space_free(Space); } +void MemoryAccess::computeBoundsOnAccessRelation(unsigned ElementSize) { + ScalarEvolution *SE = Statement->getParent()->getSE(); + + Value *Ptr = getPointerOperand(*getAccessInstruction()); + if (!Ptr || !SE->isSCEVable(Ptr->getType())) + return; + + auto *PtrSCEV = SE->getSCEV(Ptr); + if (isa(PtrSCEV)) + return; + + auto *BasePtrSCEV = SE->getPointerBase(PtrSCEV); + if (BasePtrSCEV && !isa(BasePtrSCEV)) + PtrSCEV = SE->getMinusSCEV(PtrSCEV, BasePtrSCEV); + + const ConstantRange &Range = SE->getSignedRange(PtrSCEV); + if (Range.isFullSet()) + return; + + unsigned BW = Range.getBitWidth(); + auto Min = Range.getSignedMin().sdiv(APInt(BW, ElementSize, false)); + auto Max = (Range.getSignedMax() - APInt(BW, 1, false)) + .sdiv(APInt(BW, ElementSize, false)); + + isl_set *AccessRange = isl_map_range(isl_map_copy(AccessRelation)); + AccessRange = + addRangeBoundsToSet(AccessRange, ConstantRange(Min, Max), 0, isl_dim_set); + AccessRelation = isl_map_intersect_range(AccessRelation, AccessRange); +} + MemoryAccess::MemoryAccess(const IRAccess &Access, Instruction *AccInst, ScopStmt *Statement, const ScopArrayInfo *SAI) : AccType(getMemoryAccessType(Access)), Statement(Statement), Inst(AccInst), @@ -529,6 +580,8 @@ MemoryAccess::MemoryAccess(const IRAccess &Access, Instruction *AccInst, AccessRelation = isl_map_from_basic_map(createBasicAccessMap(Statement)); AccessRelation = isl_map_set_tuple_id(AccessRelation, isl_dim_out, BaseAddrId); + + computeBoundsOnAccessRelation(Access.getElemSizeInBytes()); return; } @@ -1188,7 +1241,6 @@ void Scop::buildContext() { void Scop::addParameterBounds() { for (const auto &ParamID : ParameterIds) { - isl_val *V; int dim = ParamID.second; ConstantRange SRange = SE->getSignedRange(ParamID.first); @@ -1197,19 +1249,7 @@ void Scop::addParameterBounds() { if (SRange.isFullSet()) continue; - V = isl_valFromAPInt(IslCtx, SRange.getLower(), true); - isl_set *ContextLB = - isl_set_lower_bound_val(isl_set_copy(Context), isl_dim_param, dim, V); - - V = isl_valFromAPInt(IslCtx, SRange.getUpper(), true); - V = isl_val_sub_ui(V, 1); - isl_set *ContextUB = - isl_set_upper_bound_val(Context, isl_dim_param, dim, V); - - if (SRange.isSignWrappedSet()) - Context = isl_set_union(ContextLB, ContextUB); - else - Context = isl_set_intersect(ContextLB, ContextUB); + Context = addRangeBoundsToSet(Context, SRange, dim, isl_dim_param); } } diff --git a/polly/test/ScopInfo/NonAffine/non_affine_access_with_range.ll b/polly/test/ScopInfo/NonAffine/non_affine_access_with_range.ll new file mode 100644 index 0000000..1a50900 --- /dev/null +++ b/polly/test/ScopInfo/NonAffine/non_affine_access_with_range.ll @@ -0,0 +1,41 @@ +; RUN: opt %loadPolly -polly-detect-unprofitable -polly-scops -polly-allow-nonaffine -analyze < %s | FileCheck %s +; +; void f(int *A, char c) { +; for (int i = 0; i < 1024; i++) +; A[i * c]++; +; } +; +; CHECK: ReadAccess := [Reduction Type: +] [Scalar: 0] +; CHECK: { Stmt_bb2[i0] -> MemRef_A[o0] : o0 <= 261115 and o0 >= -3 }; +; CHECK: MayWriteAccess := [Reduction Type: +] [Scalar: 0] +; CHECK: { Stmt_bb2[i0] -> MemRef_A[o0] : o0 <= 261115 and o0 >= -3 }; +; +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" + +define void @f(i32* %A, i8 %c) { +bb: + br label %bb1 + +bb1: ; preds = %bb8, %bb + %indvars.iv = phi i64 [ %indvars.iv.next, %bb8 ], [ 0, %bb ] + %exitcond = icmp ne i64 %indvars.iv, 1024 + br i1 %exitcond, label %bb2, label %bb9 + +bb2: ; preds = %bb1 + %tmp = zext i8 %c to i32 + %tmp3 = zext i32 %tmp to i64 + %tmp4 = mul nuw nsw i64 %indvars.iv, %tmp3 + %tmp4b = add nsw nuw i64 %tmp4, -3 + %tmp5 = getelementptr inbounds i32* %A, i64 %tmp4b + %tmp6 = load i32* %tmp5, align 4 + %tmp7 = add nsw i32 %tmp6, 1 + store i32 %tmp7, i32* %tmp5, align 4 + br label %bb8 + +bb8: ; preds = %bb2 + %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 + br label %bb1 + +bb9: ; preds = %bb1 + ret void +} diff --git a/polly/test/ScopInfo/NonAffine/non_affine_access_with_range_2.ll b/polly/test/ScopInfo/NonAffine/non_affine_access_with_range_2.ll new file mode 100644 index 0000000..e186b6f --- /dev/null +++ b/polly/test/ScopInfo/NonAffine/non_affine_access_with_range_2.ll @@ -0,0 +1,54 @@ +; RUN: opt %loadPolly -polly-detect-unprofitable -polly-scops -polly-allow-nonaffine -analyze < %s | FileCheck %s +; +; void f(int *A) { +; for (int i = 0; i < 128; i++) +; for (int j = 0; j < 16; j++) +; A[i * j]++; +; } +; +; CHECK: ReadAccess := [Reduction Type: +] [Scalar: 0] +; CHECK: { Stmt_bb7[i0, i1] -> MemRef_A[o0] : o0 <= 2046 and o0 >= 0 }; +; CHECK: MayWriteAccess := [Reduction Type: +] [Scalar: 0] +; CHECK: { Stmt_bb7[i0, i1] -> MemRef_A[o0] : o0 <= 2046 and o0 >= 0 }; +; +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" + +define void @f(i32* %A) { +bb: + br label %bb4 + +bb4: ; preds = %bb13, %bb + %indvars.iv1 = phi i64 [ %indvars.iv.next2, %bb13 ], [ 0, %bb ] + %exitcond3 = icmp ne i64 %indvars.iv1, 128 + br i1 %exitcond3, label %bb5, label %bb14 + +bb5: ; preds = %bb4 + br label %bb6 + +bb6: ; preds = %bb11, %bb5 + %indvars.iv = phi i64 [ %indvars.iv.next, %bb11 ], [ 0, %bb5 ] + %exitcond = icmp ne i64 %indvars.iv, 16 + br i1 %exitcond, label %bb7, label %bb12 + +bb7: ; preds = %bb6 + %tmp = mul nsw i64 %indvars.iv1, %indvars.iv + %tmp8 = getelementptr inbounds i32* %A, i64 %tmp + %tmp9 = load i32* %tmp8, align 4 + %tmp10 = add nsw i32 %tmp9, 1 + store i32 %tmp10, i32* %tmp8, align 4 + br label %bb11 + +bb11: ; preds = %bb7 + %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 + br label %bb6 + +bb12: ; preds = %bb6 + br label %bb13 + +bb13: ; preds = %bb12 + %indvars.iv.next2 = add nuw nsw i64 %indvars.iv1, 1 + br label %bb4 + +bb14: ; preds = %bb4 + ret void +} diff --git a/polly/test/ScopInfo/multidim_single_and_multidim_array.ll b/polly/test/ScopInfo/multidim_single_and_multidim_array.ll index c0965f6f..d8b0c881 100644 --- a/polly/test/ScopInfo/multidim_single_and_multidim_array.ll +++ b/polly/test/ScopInfo/multidim_single_and_multidim_array.ll @@ -24,7 +24,7 @@ target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" ; NONAFFINE: Statements { ; NONAFFINE: Stmt_for_i_1 ; NONAFFINE: MayWriteAccess := [Reduction Type: NONE] -; NONAFFINE: [n, p_1] -> { Stmt_for_i_1[i0] -> MemRef_X[o0] }; +; 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 }; diff --git a/polly/test/ScopInfo/non_affine_access.ll b/polly/test/ScopInfo/non_affine_access.ll index c5e40e1..29cdecb 100644 --- a/polly/test/ScopInfo/non_affine_access.ll +++ b/polly/test/ScopInfo/non_affine_access.ll @@ -31,4 +31,4 @@ for.end: ; preds = %for.body } ; CHECK-NOT: Stmt_for_body -; NONAFFINE: { Stmt_for_body[i0] -> MemRef_A[o0] }; +; NONAFFINE: { Stmt_for_body[i0] -> MemRef_A[o0] : o0 >= -1152921504606846976 and o0 <= 1152921504606846973 }; diff --git a/polly/test/ScopInfo/non_affine_parametric_loop.ll b/polly/test/ScopInfo/non_affine_parametric_loop.ll index 3815de9..5a5d76e 100644 --- a/polly/test/ScopInfo/non_affine_parametric_loop.ll +++ b/polly/test/ScopInfo/non_affine_parametric_loop.ll @@ -34,4 +34,4 @@ for.end: ; CHECK: ReadAccess ; CHECK: [n] -> { Stmt_for_body[i0] -> MemRef_INDEX[i0] }; ; CHECK: WriteAccess -; CHECK: [n] -> { Stmt_for_body[i0] -> MemRef_A[o0] }; +; CHECK: [n] -> { Stmt_for_body[i0] -> MemRef_A[o0] : o0 >= -1152921504606846976 and o0 <= 1152921504606846973 }; -- 2.7.4