[Polly] [DependenceInfo] Fix isParallel: accept dependences comprised of different spaces.

[bollu]

Summary

• Sometimes, isParallel can receive dependences that are a union_map of

different looking spaces in the maps that correspond to it.

• Code assumed that the isl_union_map of Dependences could be merged into

one isl_map.

• Fix code so that we append dummy dimensions to equalize the spaces of

all isl_maps so that the merge is possible.

[bollu]

• minimize test case. Testcase is much more readable now.

[Meinersbur]

lib/Analysis/DependenceInfo.cpp

830–831

This adds unrestricted dimensions, i.e. the result is not bounded or single-valued anymore. Not a property a scatter function should have.

Btw, padding with constant 0 is also not generally safe. The other more-dimensional schedule can have positive and/or negative coordinates in the additional dimensions.

833–836

It might be more elegant to initialize info->map with an empty isl_union_map. An advantage is that you don't need special cases when the union_map you are iterating over is empty.

856–858

Did you consider using isl::union_map::foreach_map? It allows you to use C++11-style closures and a lot of boilerplate code.

893

In your test case, I get the following Schedule:

{ Stmt_for_body_inner[i0, i1] -> [o0, o1] : o0 = i0 and o1 = i1; Stmt_for_body[i0] -> [o0, o1, o2] : o0 = i0 and o1 = 0 and o2 = 0 }

I.e. one 2-dimensional and a 3-dimensional scatter space. As far as I know, this should not occur. How did this happen?

test/DependenceInfo/is_parallel_irregular_deps.ll

6

Use < %s instead of %s. Reason.

Even for testing crashes, Polly's regression test have some minimal CHECK to ensure that we don't regress to something trivial, e.g. a do-nothing bail-out. Suggestion:

CHECK: for.body:     Loop is not parallel.
CHECK: for.body.inner:       Loop is parallel.

[bollu]

lib/Analysis/DependenceInfo.cpp

893

Hm, that's strange. I'll check. Perhaps it flattened dimensions that were wrapped which increased the total dimensionality?

This entire flattening business is ugly.

test/DependenceInfo/is_parallel_irregular_deps.ll

6

I see, thank you for the pointer.

[bollu]

@Meinersbur: I checked where the schedule is being generated from, and I have a couple questions. Could you please take a look?

lib/Analysis/DependenceInfo.cpp

830–831

In that case, how should I transform it to obtain a correct schedule? Would simply equating the extra dimensions to 0 work?

I'm not sure what you mean by:

The other more-dimensional schedule can have positive and/or negative coordinates in the additional dimensions.

How? since we are manually adding the extra dimensions, are those not automatically zeroed out? I would assume the map looks like this:

f: F^n -> F^(n + 1)
f((a_1, a_2, ..., a_n)) = (a_1, a_2, ..., a_n, 0)

am I mistaken?

893

Just to clarify, by "scatter space" you're referring to the output space of the schedule, right?

The original schedule is this:

child: 
  child: 
    sequence: 
      - 
        filter: "{ Stmt_for_body[i0] }"
      - 
        child: 
          schedule: "[{ Stmt_for_body_inner[i0, i1] -> [(i1)] }]"
        filter: "{ Stmt_for_body_inner[i0, i1] }"
  schedule: "[{ Stmt_for_body[i0] -> [(i0)]; Stmt_for_body_inner[i0, i1] -> [(i0)] }]"
domain: "{ Stmt_for_body[i0] : 0 <= i0 <= 199; Stmt_for_body_inner[i0, i1] : 0 <= i0 <= 199 and 0 <= i1 <= 199 }"

The schedule that is passed to this function arrives from PolyhedralInfo::getScheduleForLoop.

This is called in PolyhedralInfo::checkParallel.

It looks like I need to check why PolyhedralInfo::getScheduleForLoop is generating schedules whose output dimensions don't match?

[annanay25]

lib/Analysis/DependenceInfo.cpp

893

PolyhedralInfo::getScheduleForLoop is generating schedules for 2 statements in its SCoP => one with a 2D scatter space and the other with a 3D scatter space.

This instruction -

ScheduleMap = isl_map_project_out(ScheduleMap, isl_dim_out, CurrDim + 1, MaxDim - CurrDim - 1);

would project the map onto MaxDim - CurrDim - 1 dimensional space which would be 1 and 2, for the two statements, respectively.

So, AFAIU this is correct behavior, but we need a way to canonicalize the generated spaces to the same dimension.

[Meinersbur]

lib/Analysis/DependenceInfo.cpp

830–831

Think of a statement and its domain and schedule of:

{ StmtA[i0] : -1 <= i0 <= 1 }
{ StmtA[i0] -> [0, i0] }

If you know have a second stmt

{ StmtB[] }
{ StmtB[] -> [0] }

and pad it with zero

{ StmtB[] -> [0, 0] }

The execution order would be

StmtA[-1]
StmtB[0], StmtA[0] (in parallel, if legal at all)
StmtA[1]

So we placed StmtB somewhere arbitrarily between StmtA instances.

Now, it is unclear what the relative execution order of StmtA and StmtB actually should be. I suggest to not generate such things in the first place, i.e. fix the bug in whoever calls isParallel and add an assertion that checks that there is just one schedule space.

Now it seems that Polly normalizes domains and schedules to start with 0. If that is contractual, then we still have StmtA[0] and StmtB[] in an undefined order. So you could pad with -1 to ensure that the padded schedule functions are executed before the non-padded ones. But be that, we violate that contract (that scatter dimensions are always >= 0).

893

Thank you Annanay.

isl_map_project_out removes information from the schedule, the inner dimensions of the scatter function.

By construction, these should be irrelevant. However, there is a reason why they are there in the first place: To make the schedule range lexicographically comparable. PolyhedralInfo::getScheduleForLoop removes that comparability and I don't see the motivation for that.

It is hard/impossible to restore the comparability without assuming that the removed dimensions are irrelevant.

Instead of deleting the dimensions and then trying to restore them, why not keeping them in the first place?

[bollu]

lib/Analysis/DependenceInfo.cpp

893

right, I'll look into fixing getScheduleForLoop in that case.
Thanks, the discussion helped clear this up :)

lib/Analysis/DependenceInfo.cpp

bool Dependences::isValidSchedule(Scop &S,
 
   isl_map *NonPositive = isl_set_lex_le_set(Deltas, Zero);
   bool IsValid = isl_map_is_empty(NonPositive);
   isl_map_free(NonPositive);
 
   return IsValid;
 }
 
+// Find the maximum number of input or output dimensions among all isl_maps
+// in a isl_union_map. Used as a callback for isl_union_map_foreach_map.
+// @see unifyDepsMap
+static isl_stat findMaxDimsCount(__isl_take isl_map *map, void *user) {
+  assert(user && "Expected valid pointer to store max dimension count.");
+  unsigned *Maxdims = (unsigned *)user;
+
+  unsigned NInDims = isl_map_dim(map, isl_dim_in);
+  unsigned NOutDims = isl_map_dim(map, isl_dim_out);
+  isl_map_free(map);
+
+  *Maxdims = std::max(*Maxdims, NInDims);
+  *Maxdims = std::max(*Maxdims, NOutDims);
+
+  return isl_stat_ok;
+}
+
+// Helper struct used to store information used by
+// appendInputDimsAndUnion.
+// @see appendInputDimsAndUnion
+struct AlignInputsMapInfo {
+  // Number of input & dimensions that is expected for an isl_map;
+  unsigned NExpectedDims;
+
+  // Final isl_union_map that is a concatenation of all the isl_maps
+  // appendInputDimsAndUnion is run on.
+  isl_union_map *out;
+
+  AlignInputsMapInfo() : NExpectedDims(0), out(nullptr){};
+};
+
+// Pad each isl_map with dimensions such that they all have the
+// same number of input & output dimensions. Used as callback for
+// isl_union_map_foreach_map.
+// @see unifyDepsMap
+static isl_stat appendInputDimsAndUnion(__isl_take isl_map *map, void *user) {
+  AlignInputsMapInfo *info = (AlignInputsMapInfo *)(user);
+  assert(info && "expected valid user pointer");
+
+  unsigned InN = isl_map_dim(map, isl_dim_in);
+  unsigned OutN = isl_map_dim(map, isl_dim_out);
+
+  assert(
+      InN <= info->NExpectedDims &&
+      "Found map with more than maximum number of expected input dimensions.");
+
+  assert(
+      OutN <= info->NExpectedDims &&
+      "Found map with more than maximum number of expected output dimensions.");
+
+  // TODO: I don't fully understand the implications of doing this,
+  // since isl_map_add_dims flattens the map. However, I believe that it
+  // is okay to flatten dependences over a schedule.
+  map = isl_map_add_dims(map, isl_dim_in, info->NExpectedDims - InN);
+  map = isl_map_add_dims(map, isl_dim_out, info->NExpectedDims - OutN);
+
+  if (!info->out)
+    info->out = isl_union_map_from_map(map);
+  else
+    info->out = isl_union_map_union(info->out, isl_union_map_from_map(map));
+
+  return isl_stat_ok;
+}
+
+// The isl_maps that comprise of the Deps may have different dimensions
+// per isl_map. We need to force them to have the same number of dimensions
+// since we wish to unify this into an isl_map. So, we figure out what
+// the maximum number of dimensions are, and we pad each isl_map's input
+// and output dimensions to be the same number throughout the isl_union_map.
+//
+// We expect that the number of input and output dimensions for each map in Deps
+// to be equal, since they represent dependences.
+//
+// Postcondition:
+//    forall m, n \in out,
+//      dim_in(n) = dim_in(m) = dim_out(n) = dim_out(m)
+// @see Dependences::isParallel
+static isl_map *unifyDepsMap(isl_union_map *Deps) {
+  AlignInputsMapInfo info;
+  isl_union_map_foreach_map(Deps, &findMaxDimsCount, &info.NExpectedDims);
+
+  isl_union_map_foreach_map(Deps, &appendInputDimsAndUnion, &info);
+  isl_union_map_free(Deps);
+  Deps = info.out;
+
+  return isl_map_from_union_map(Deps);
+}
+
 // Check if the current scheduling dimension is parallel.
 //
 // We check for parallelism by verifying that the loop does not carry any
 // dependences.
 //
 // Parallelism test: if the distance is zero in all outer dimensions, then it
 // has to be zero in the current dimension as well.
 //
bool Dependences::isParallel(isl_union_map *Schedule, isl_union_map *Deps,
   Deps = isl_union_map_apply_range(Deps, isl_union_map_copy(Schedule));
   Deps = isl_union_map_apply_domain(Deps, isl_union_map_copy(Schedule));
 
   if (isl_union_map_is_empty(Deps)) {
     isl_union_map_free(Deps);
     return true;
   }
 
-  ScheduleDeps = isl_map_from_union_map(Deps);
+  ScheduleDeps = unifyDepsMap(Deps);
   Dimension = isl_map_dim(ScheduleDeps, isl_dim_out) - 1;
 
   for (unsigned i = 0; i < Dimension; i++)
     ScheduleDeps = isl_map_equate(ScheduleDeps, isl_dim_out, i, isl_dim_in, i);
 
   Deltas = isl_map_deltas(ScheduleDeps);
   Distance = isl_set_universe(isl_set_get_space(Deltas));
 

test/DependenceInfo/is_parallel_irregular_deps.ll

+; This contains dependences which do not generate the same space
+; when called with -poyhedral-info. This tests that we unify these
+; correctly, and not crash by calling isl_map_from_union_map directly.
+
+
+; RUN: opt %loadPolly -polyhedral-info -polly-check-parallel -analyze %s
+
+; static const int N = 200;
+; 
+; void crash(int A[N]) {
+;   int i = 0, j = 0;
+;   for (i = 0; i < N; i++) {
+;       A[i] = 0;
+; 
+;     for (j = 0; j < N; j++)
+;         A[j] = 42;
+;   }
+; }
+  
+
+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-apple-macosx10.11.0"
+
+define void @crash(i32* %A) {
+entry.split:
+  br label %for.body
+ 
+for.body:                                         ; preds =  %for.inc
+  %indvars.iv3 = phi i64 [ 0, %entry.split ], [ %indvars.iv.next4, %for.inc ]
+  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %indvars.iv3
+  store i32 0, i32* %arrayidx, align 4
+  br label %for.body.inner
+
+for.body.inner:                                        ; preds = %for.body, %for.body.inner
+  %indvars.iv = phi i64 [ 0, %for.body ], [ %indvars.iv.next, %for.body.inner ]
+  %arrayidx5 = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
+  store i32 42, i32* %arrayidx5, align 4
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %exitcond = icmp ne i64 %indvars.iv.next, 200
+  br i1 %exitcond, label %for.body.inner, label %for.inc
+
+for.inc:                                         ; preds = %for.body.inner
+  %indvars.iv.next4 = add nuw nsw i64 %indvars.iv3, 1
+  %exitcond5 = icmp ne i64 %indvars.iv.next4, 200
+  br i1 %exitcond5, label %for.body, label %for.end
+
+for.end:                                         ; preds = %for.inc
+  ret void
+}