[Polly] [DependenceInfo] Less restrictive matrix-multiplication pattern match

[bollu]

Summary

The surrounding code should make sure that the weakened
dependence check for matrix multiplication like operations will work.

This generalises the check to work in more cases than before.

[grosser]

Great. Can you add a RUN line that enables memory based dependences to show that this actually works. Also please mention in the commit log that the pattern matching does currently not work for memory based dependence.

[bollu]

This doesn't work for memory based analysis:
When we do memory based analysis, we have widened RAW, WAR, and WAW dependence. However, RED dependences are not widened. This leads to a case where the schedule is still restricted by WAR and WAW dependences.

	WAR dependences:
		{ Stmt_for_body6[i0, i1, i2] -> Stmt_for_body6[i0, i1, o2] : 0 <= i0 <= 2999 and 0 <= i1 <= 2999 and 0 <= i2 <= 2999 and 0 <= o2 <= 2999 and (o2 >= 2 or (i2 <= 2997 and o2 <= 2998)) }
	WAW dependences:
		{ Stmt_for_body6[i0, i1, i2] -> Stmt_for_body6[i0, i1, o2] : 0 <= i0 <= 2999 and 0 <= i1 <= 2999 and 0 <= i2 <= 2999 and 0 <= o2 <= 2999 and (o2 >= 2 or (i2 <= 2997 and o2 <= 2998)) }
	Reduction dependences:
		{ Stmt_for_body6[i0, i1, i2] -> Stmt_for_body6[i0, i1, 1 + i2] : 0 <= i0 <= 2999 and 0 <= i1 <= 2999 and 0 <= i2 <= 2998 }
	Transitive closure of reduction dependences:
		{ Stmt_for_body6[i0, i1, i2] -> Stmt_for_body6[i0, i1, o2] : 0 <= i0 <= 2999 and 0 <= i1 <= 2999 and ((i2 >= 0 and i2 < o2 <= 2999) or (i2 <= 2999 and 0 <= o2 < i2)) }

lib/Transform/ScheduleOptimizer.cpp

static bool containsOnlyMatrMultAcc(__isl_keep isl_map *PartialSchedule,
   isl_map_free(MapJ);
   isl_map_free(MapK);
   return true;
 }
 
 /// Check for dependencies corresponding to the matrix multiplication.
 ///
 /// Check that there is only true dependence of the form
-/// S(..., k, ...) -> S(..., k + 1, …), where S is the SCoP statement
+/// S(..., k, ...) -> S(..., k + <constant>, …), where S is the SCoP statement
 /// represented by @p Schedule and k is @p Pos. Such a dependence corresponds
 /// to the dependency produced by the matrix multiplication.
 ///
 /// @param  Schedule The schedule of the SCoP statement.
 /// @param  D The SCoP dependencies.
 /// @param  Pos The parameter to desribe an acceptable true dependence.
 ///             In case it has a negative value, try to determine its
 ///             acceptable value.
 /// @return True in case dependencies correspond to the matrix multiplication
 ///         and false, otherwise.
 static bool containsOnlyMatMulDep(__isl_keep isl_map *Schedule,
                                   const Dependences *D, int &Pos) {
   auto *Dep = D->getDependences(Dependences::TYPE_RAW);
   auto *Red = D->getDependences(Dependences::TYPE_RED);
   if (Red)
     Dep = isl_union_map_union(Dep, Red);
   auto *DomainSpace = isl_space_domain(isl_map_get_space(Schedule));
   auto *Space = isl_space_map_from_domain_and_range(isl_space_copy(DomainSpace),
                                                     DomainSpace);
   auto *Deltas = isl_map_deltas(isl_union_map_extract_map(Dep, Space));
   isl_union_map_free(Dep);
   int DeltasDimNum = isl_set_dim(Deltas, isl_dim_set);
   for (int i = 0; i < DeltasDimNum; i++) {
+    // check for any constant delta
     auto *Val = isl_set_plain_get_val_if_fixed(Deltas, isl_dim_set, i);
     Pos = Pos < 0 && isl_val_is_one(Val) ? i : Pos;
-    if (isl_val_is_nan(Val) ||
-        !(isl_val_is_zero(Val) || (i == Pos && isl_val_is_one(Val)))) {
+    if (!isl_val_is_zero(Val) && i != Pos) {
       isl_val_free(Val);
       isl_set_free(Deltas);
       return false;
     }
     isl_val_free(Val);
   }
   isl_set_free(Deltas);
   if (DeltasDimNum == 0 || Pos < 0)