Add ScalarEvolution bounds to non-affine access functions

[grosser]

LGTM.

test/ScopInfo/NonAffine/non_affine_access_with_range.ll

4

Leftover fixme?

test/ScopInfo/NonAffine/non_affine_access_with_range_2.ll

4

Leftover fixme?

[jdoerfert]

Commited in r230328.

[sebpop]

LGTM

lib/Analysis/ScopInfo.cpp

307

Please use capital letters for variable names: Dim, Type, Ctx.

320

No need of "else" after return.

include/polly/ScopInfo.h

private:
   /// @brief The access instruction of this memory access.
   Instruction *Inst;
 
   /// Updated access relation read from JSCOP file.
   isl_map *newAccessRelation;
 
   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;
 
   /// @brief Return the space in which the access relation lives in.
   __isl_give isl_space *getOriginalAccessRelationSpace() const;
 
   /// @brief Get the new access function imported or set by a pass
   isl_map *getNewAccessRelation() const;

lib/Analysis/ScopInfo.cpp

 }
 
 int SCEVAffinator::getLoopDepth(const Loop *L) {
   Loop *outerLoop = S->getRegion().outermostLoopInRegion(const_cast<Loop *>(L));
   assert(outerLoop && "Scop does not contain this loop");
   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<const SCEV *, 4> &DimensionSizes)
     : BasePtr(BasePtr), AccessType(AccessType), DimensionSizes(DimensionSizes) {
   const std::string BasePtrName = getIslCompatibleName("MemRef_", BasePtr, "");
   Id = isl_id_alloc(Ctx, BasePtrName.c_str(), this);
 }
 
 ScopArrayInfo::~ScopArrayInfo() { isl_id_free(Id); }
void MemoryAccess::assumeNoOutOfBound(const IRAccess &Access) {
   Outside = isl_set_apply(Outside, isl_map_reverse(getAccessRelation()));
   Outside = isl_set_intersect(Outside, Statement->getDomain());
   Outside = isl_set_params(Outside);
   Outside = isl_set_complement(Outside);
   Statement->getParent()->addAssumption(Outside);
   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<SCEVCouldNotCompute>(PtrSCEV))
+    return;
+
+  auto *BasePtrSCEV = SE->getPointerBase(PtrSCEV);
+  if (BasePtrSCEV && !isa<SCEVCouldNotCompute>(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),
       newAccessRelation(nullptr) {
 
   isl_ctx *Ctx = Statement->getIslCtx();
   BaseAddr = Access.getBase();
   BaseName = getIslCompatibleName("MemRef_", getBaseAddr(), "");
 
   isl_id *BaseAddrId = SAI->getBasePtrId();
 
   if (!Access.isAffine()) {
     // We overapproximate non-affine accesses with a possible access to the
     // whole array. For read accesses it does not make a difference, if an
     // access must or may happen. However, for write accesses it is important to
     // differentiate between writes that must happen and writes that may happen.
     AccessRelation = isl_map_from_basic_map(createBasicAccessMap(Statement));
     AccessRelation =
         isl_map_set_tuple_id(AccessRelation, isl_dim_out, BaseAddrId);
+
+    computeBoundsOnAccessRelation(Access.getElemSizeInBytes());
     return;
   }
 
   isl_space *Space = isl_space_alloc(Ctx, 0, Statement->getNumIterators(), 0);
   AccessRelation = isl_map_universe(Space);
 
   for (int i = 0, Size = Access.Subscripts.size(); i < Size; ++i) {
     isl_pw_aff *Affine =

 void Scop::buildContext() {
   isl_space *Space = isl_space_params_alloc(IslCtx, 0);
   Context = isl_set_universe(isl_space_copy(Space));
   AssumedContext = isl_set_universe(Space);
 }
 
 void Scop::addParameterBounds() {
   for (const auto &ParamID : ParameterIds) {
-    isl_val *V;
     int dim = ParamID.second;
 
     ConstantRange SRange = SE->getSignedRange(ParamID.first);
 
     // TODO: Find a case where the full set is actually helpful.
     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);
   }
 }
 
 void Scop::realignParams() {
   // Add all parameters into a common model.
   isl_space *Space = isl_space_params_alloc(IslCtx, ParameterIds.size());
 
   for (const auto &ParamID : ParameterIds) {

test/ScopInfo/NonAffine/non_affine_access_with_range.ll

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

test/ScopInfo/NonAffine/non_affine_access_with_range_2.ll

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

test/ScopInfo/multidim_single_and_multidim_array.ll

 
 ; CHECK-NOT: Stmt_for_i_1
 
 ; NONAFFINE: p0: %n
 ; NONAFFINE: p1: (4 * (-1 + %n) * %n)
 ; 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 };
 
 ; DELIN: Stmt_for_i_1
 ; DELIN:   MustWriteAccess :=
 ; DELIN:      [n] -> { Stmt_for_i_1[i0] -> MemRef_X[i0, 0] };
 ; DELIN: Stmt_for_i_2

test/ScopInfo/non_affine_access.ll

for.body:                                         ; preds = %entry.split, %for.body
   %exitcond = icmp ne i64 %indvar.next, 1024
   br i1 %exitcond, label %for.body, label %for.end
 
 for.end:                                          ; preds = %for.body
   ret void
 }
 
 ; 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 };

test/ScopInfo/non_affine_parametric_loop.ll

 
 ; CHECK: Domain
 ; CHECK:   [n] -> { Stmt_for_body[i0] : i0 >= 0 and i0 <= -1 + n };
 ; CHECK: Scattering
 ; CHECK:   [n] -> { Stmt_for_body[i0] -> [i0] };
 ; 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 };