[Polly][PoC] Approximate the parameters when creating runtime alias checks.

[grosser]

Hi Johannes,

thanks for your proof of concept.

It seems you left out the code generation support, such that after this patch the test cases start to crash. This is probably intentional, but I would like to note this to avoid misunderstandings.

Regarding the patch, there are two questions that need to be checked:

1) Is it correct?

For the following code:

void foo(float *A, float *B, long N, long p1) {                                  
        for (long i = 0; i < 100; i++)                                           
                B[i] = A[i - p1];                                                
}

I get the following exception:

isl/isl_tab_pip.c:491: unbounded optimum

Introducing a single new parameter that is smaller or larger than all parameters does not work in case you have negative coefficients for certain parameters.

2) What do we loose with this over-approximation?

Do you know what kind of simple cases we would now refuse? Are those exceptional cases or pretty common ones?

My feeling is that we might loose some rather basic cases. To fix this, we could possibly try to detect them and then use this approximation. However, maybe just detecting the possibly complicated cases and blindly bailing out would already good enough for now.

I remember you recently used isl_set_involves_dims() in the "[Polly] Find all loops involved in now innermost ones." patch. Maybe we can use this one here to count the number of parameter dimensions involved in a certain access set and bail out if more than X parameters are involved?

[jdoerfert]

In D5441#4, @grosser wrote:

It seems you left out the code generation support, such that after this patch the test cases start to crash. This is probably intentional, but I would like to note this to avoid misunderstandings.

Yes, I left out codegen and this was intentional :)

Regarding the patch, there are two questions that need to be checked:

1) Is it correct?

For the following code:

void foo(float *A, float *B, long N, long p1) {                                  
        for (long i = 0; i < 100; i++)                                           
                B[i] = A[i - p1];                                                
}

I get the following exception:

isl/isl_tab_pip.c:491: unbounded optimum

Introducing a single new parameter that is smaller or larger than all parameters does not work in case you have negative coefficients for certain parameters.

True, the min/max parameter should only be greater then all negative/positive ones respectively. If both are present we shouldn't relate the real parameter with the fake one and do not project it out.

2) What do we loose with this over-approximation?

Do you know what kind of simple cases we would now refuse? Are those exceptional cases or pretty common ones?

I don't but exactly.

My feeling is that we might loose some rather basic cases. To fix this, we could possibly try to detect them and then use this approximation. However, maybe just detecting the possibly complicated cases and blindly bailing out would already good enough for now.

Bail seems more and more to be the option to choose.

I remember you recently used isl_set_involves_dims() in the "[Polly] Find all loops involved in now innermost ones." patch. Maybe we can use this one here to count the number of parameter dimensions involved in a certain access set and bail out if more than X parameters are involved?

We could and we would need to check each the signs of parameter somehow. Only positive ones can be aproximated by Pmax and only negative ones by some Pmin for the maximum computation and the other way around for the minimum computation. If after approximation to many parameters remain we would need to bail again.

[jdoerfert]

Postponed until we find a usecase and a good heuristic.

lib/Analysis/ScopInfo.cpp

void Scop::simplifyAssumedContext() {
   AssumedContext =
       isl_set_gist_params(AssumedContext, isl_union_set_params(getDomains()));
 }
 
 /// @brief Add the minimal/maximal access in @p Set to @p User.
 static int buildMinMaxAccess(__isl_take isl_set *Set, void *User) {
   Scop::MinMaxVectorTy *MinMaxAccesses = (Scop::MinMaxVectorTy *)User;
   isl_pw_multi_aff *MinPMA, *MaxPMA;
+  isl_set *SetMax, *SetMin;
   isl_pw_aff *LastDimAff;
+  isl_id *MaxId, *MinId;
+  isl_constraint *C;
   isl_aff *OneAff;
-  unsigned Pos;
+  unsigned MPos, Pos;
 
-  MinPMA = isl_set_lexmin_pw_multi_aff(isl_set_copy(Set));
-  MaxPMA = isl_set_lexmax_pw_multi_aff(isl_set_copy(Set));
+  MPos = isl_set_n_param(Set);
+  SetMax = isl_set_copy(Set);
+  SetMin = isl_set_copy(Set);
+  SetMax = isl_set_add_dims(SetMax, isl_dim_param, 1);
+  SetMin = isl_set_add_dims(SetMin, isl_dim_param, 1);
+  MaxId = isl_id_alloc(isl_set_get_ctx(Set), "PMax", 0);
+  MinId = isl_id_alloc(isl_set_get_ctx(Set), "PMin", 0);
+  SetMax = isl_set_set_dim_id(SetMax, isl_dim_param, MPos, MaxId);
+  SetMin = isl_set_set_dim_id(SetMin, isl_dim_param, MPos, MinId);
+  for (unsigned u = 0; u < MPos; u++) {
+    C = isl_inequality_alloc(
+        isl_local_space_from_space(isl_set_get_space(SetMax)));
+    C = isl_constraint_set_coefficient_si(C, isl_dim_param, MPos, 1);
+    C = isl_constraint_set_coefficient_si(C, isl_dim_param, u, -1);
+    SetMax = isl_set_add_constraint(SetMax, C);
+    C = isl_inequality_alloc(
+        isl_local_space_from_space(isl_set_get_space(SetMin)));
+    C = isl_constraint_set_coefficient_si(C, isl_dim_param, MPos, -1);
+    C = isl_constraint_set_coefficient_si(C, isl_dim_param, u, 1);
+    SetMin = isl_set_add_constraint(SetMin, C);
+  }
+  SetMax = isl_set_project_out(SetMax, isl_dim_param, 0, MPos);
+  SetMin = isl_set_project_out(SetMin, isl_dim_param, 0, MPos);
+  MaxPMA = isl_set_lexmax_pw_multi_aff(SetMax);
+  MinPMA = isl_set_lexmin_pw_multi_aff(SetMin);
 
   // Adjust the last dimension of the maximal access by one as we want to
   // enclose the accessed memory region by MinPMA and MaxPMA. The pointer
   // we test during code generation might now point after the end of the
   // allocated array but we will never dereference it anyway.
   assert(isl_pw_multi_aff_dim(MaxPMA, isl_dim_out) &&
          "Assumed at least one output dimension");
   Pos = isl_pw_multi_aff_dim(MaxPMA, isl_dim_out) - 1;

test/ScopInfo/aliasing_many_parameters.ll

+; RUN: opt %loadPolly -polly-code-generator=isl -polly-scops -analyze < %s | FileCheck %s
+;
+; CHECK: <[PMin] -> { MemRef_A[(0)] }, [PMax] -> { MemRef_A[(100)] }> <[PMin] -> { MemRef_B[(PMin)] }, [PMax] -> { MemRef_B[(100 + PMax)] }>
+;
+; void foo(float *A, float *B,
+;   long p1,
+;   long p2,
+;   long p3,
+;   long p4,
+;   long p5,
+;   long p6,
+;   long p7,
+;   long p8,
+;   long p9,
+;   long p10,
+;   long p11,
+;   long p12) {
+;   for (long i = 0; i < 100; i++) {
+;     A[i] =
+;   B[i + p1] +
+;   B[i + p2] +
+;   B[i + p3] +
+;   B[i + p4] +
+;   B[i + p5] +
+;   B[i + p6] +
+;   B[i + p7] +
+;   B[i + p8] +
+;   B[i + p9] +
+;   B[i + p10] +
+;   B[i + p11] +
+;   B[i + p12];
+;   }
+; }
+;
+; Computing the minimal and maximal element accessed in B is very expensive.
+; Expressing the minimal element itself yields a rather complex isl_pw_aff which
+; looks as follows:
+; { ...
+;   MemRef_B[(100 + p11)] : p2 <= -1 + p1 and p3 <= -1 + p1 and p4 <= -1 + p1
+;                           and p5 <= -1 + p1 and p6 <= -1 + p1 and
+;                           p7 <= -1 + p1 and p8 <= -1 + p1 and p9 <= -1 + p1
+;                           and p10 <= -1 + p1 and p11 >= p1 and
+;                           p12 <= -1 + p11;
+;   MemRef_B[(100 + p12)] : p2 <= -1 + p1 and p3 <= -1 + p1 and p4 <= -1 + p1
+;                           and p5 <= -1 + p1 and p6 <= -1 + p1 and
+;                           p7 <= -1 + p1 and p8 <= -1 + p1 and p9 <= -1 + p1
+;                           and p10 <= -1 + p1 and p11 <= -1 + p1 and p12 >= p1;
+;
+; and this isl_pw_aff is then 1:1 translated into a isl ast expression.
+;
+; In the best case, we would create a run-time check such as:
+;
+; if (B[99 + max(p1, p2, p3, p4, p5, p6, p7, p8, p9, p10, p11, p12)] < A[0]
+;     || A[99] B[min(p0, p1, p2, p3, p4, p5, p6, p7, p8, p9]))
+;
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+; Function Attrs: nounwind uwtable
+define void @foo(float* %A, float* %B, i64 %p1, i64 %p2, i64 %p3, i64 %p4, i64 %p5, i64 %p6, i64 %p7, i64 %p8, i64 %p9, i64 %p10, i64 %p11, i64 %p12) #0 {
+entry:
+  br label %entry.split
+
+entry.split:                                      ; preds = %entry
+  br label %for.body
+
+for.body:                                         ; preds = %entry.split, %for.body
+  %i.01 = phi i64 [ 0, %entry.split ], [ %tmp25, %for.body ]
+  %tmp = add i64 %p1, %i.01
+  %arrayidx = getelementptr float* %B, i64 %tmp
+  %tmp2 = add i64 %p2, %i.01
+  %arrayidx2 = getelementptr float* %B, i64 %tmp2
+  %tmp3 = add i64 %p3, %i.01
+  %arrayidx5 = getelementptr float* %B, i64 %tmp3
+  %tmp4 = add i64 %p4, %i.01
+  %arrayidx8 = getelementptr float* %B, i64 %tmp4
+  %tmp5 = add i64 %p5, %i.01
+  %arrayidx11 = getelementptr float* %B, i64 %tmp5
+  %tmp6 = add i64 %p6, %i.01
+  %arrayidx14 = getelementptr float* %B, i64 %tmp6
+  %tmp7 = add i64 %p7, %i.01
+  %arrayidx17 = getelementptr float* %B, i64 %tmp7
+  %tmp8 = add i64 %p8, %i.01
+  %arrayidx20 = getelementptr float* %B, i64 %tmp8
+  %tmp9 = add i64 %p9, %i.01
+  %arrayidx23 = getelementptr float* %B, i64 %tmp9
+  %tmp10 = add i64 %p10, %i.01
+  %arrayidx26 = getelementptr float* %B, i64 %tmp10
+  %tmp11 = add i64 %p11, %i.01
+  %arrayidx29 = getelementptr float* %B, i64 %tmp11
+  %tmp12 = add i64 %p12, %i.01
+  %arrayidx32 = getelementptr float* %B, i64 %tmp12
+  %arrayidx34 = getelementptr float* %A, i64 %i.01
+  %tmp13 = load float* %arrayidx, align 4
+  %tmp14 = load float* %arrayidx2, align 4
+  %add3 = fadd float %tmp13, %tmp14
+  %tmp15 = load float* %arrayidx5, align 4
+  %add6 = fadd float %add3, %tmp15
+  %tmp16 = load float* %arrayidx8, align 4
+  %add9 = fadd float %add6, %tmp16
+  %tmp17 = load float* %arrayidx11, align 4
+  %add12 = fadd float %add9, %tmp17
+  %tmp18 = load float* %arrayidx14, align 4
+  %add15 = fadd float %add12, %tmp18
+  %tmp19 = load float* %arrayidx17, align 4
+  %add18 = fadd float %add15, %tmp19
+  %tmp20 = load float* %arrayidx20, align 4
+  %add21 = fadd float %add18, %tmp20
+  %tmp21 = load float* %arrayidx23, align 4
+  %add24 = fadd float %add21, %tmp21
+  %tmp22 = load float* %arrayidx26, align 4
+  %add27 = fadd float %add24, %tmp22
+  %tmp23 = load float* %arrayidx29, align 4
+  %add30 = fadd float %add27, %tmp23
+  %tmp24 = load float* %arrayidx32, align 4
+  %add33 = fadd float %add30, %tmp24
+  store float %add33, float* %arrayidx34, align 4
+  %tmp25 = add nsw i64 %i.01, 1
+  %exitcond = icmp ne i64 %tmp25, 100
+  br i1 %exitcond, label %for.body, label %for.end
+
+for.end:                                          ; preds = %for.body
+  ret void
+}