Index: include/polly/ScopInfo.h =================================================================== --- include/polly/ScopInfo.h +++ include/polly/ScopInfo.h @@ -209,6 +209,11 @@ 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; Index: lib/Analysis/ScopInfo.cpp =================================================================== --- lib/Analysis/ScopInfo.cpp +++ lib/Analysis/ScopInfo.cpp @@ -300,6 +300,27 @@ 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) { @@ -511,6 +532,36 @@ 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), @@ -530,6 +581,8 @@ AccessRelation = isl_map_from_basic_map(createBasicAccessMap(Statement)); AccessRelation = isl_map_set_tuple_id(AccessRelation, isl_dim_out, BaseAddrId); + + computeBoundsOnAccessRelation(Access.getElemSizeInBytes()); return; } @@ -1221,7 +1274,6 @@ void Scop::addParameterBounds() { for (const auto &ParamID : ParameterIds) { - isl_val *V; int dim = ParamID.second; ConstantRange SRange = SE->getSignedRange(ParamID.first); @@ -1230,19 +1282,7 @@ 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); } } Index: test/ScopInfo/NonAffine/non_affine_access_with_range.ll =================================================================== --- /dev/null +++ test/ScopInfo/NonAffine/non_affine_access_with_range.ll @@ -0,0 +1,40 @@ +; RUN: opt %loadPolly -analyze < %s | FileCheck %s +; +; FIXME: Edit the run line and add checks! +; +; XFAIL: * +; +; void f(int *A, char c) { +; for (int i = 0; i < 1024; i++) +; A[i * c]++; +; } +; +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 +} Index: test/ScopInfo/NonAffine/non_affine_access_with_range_2.ll =================================================================== --- /dev/null +++ test/ScopInfo/NonAffine/non_affine_access_with_range_2.ll @@ -0,0 +1,53 @@ +; RUN: opt %loadPolly -analyze < %s | FileCheck %s +; +; FIXME: Edit the run line and add checks! +; +; XFAIL: * +; +; void f(int *A) { +; for (int i = 0; i < 128; i++) +; for (int j = 0; j < 16; j++) +; A[i * j]++; +; } +; +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 +} Index: test/ScopInfo/multidim_single_and_multidim_array.ll =================================================================== --- test/ScopInfo/multidim_single_and_multidim_array.ll +++ test/ScopInfo/multidim_single_and_multidim_array.ll @@ -24,7 +24,7 @@ ; 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 }; Index: test/ScopInfo/non_affine_access.ll =================================================================== --- test/ScopInfo/non_affine_access.ll +++ test/ScopInfo/non_affine_access.ll @@ -31,4 +31,4 @@ } ; 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 }; Index: test/ScopInfo/non_affine_parametric_loop.ll =================================================================== --- test/ScopInfo/non_affine_parametric_loop.ll +++ test/ScopInfo/non_affine_parametric_loop.ll @@ -34,4 +34,4 @@ ; 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 };