isl_union_map_compute_flow: return accesses with no source

And similarly for isl_flow_get_no_source.
Before, we would return the iterations where those accesses occur,
but if more than one element is accessed from within the same iteration,
then this does not provide enough information.

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

diff --git a/doc/user.pod b/doc/user.pod
index 6b9b1d6..ac5b6bf 100644 (file)
--- a/doc/user.pod
+++ b/doc/user.pod
@@ -62,6 +62,11 @@ to C<isl/header.h>.
 =item * The functions C<isl_printer_print_basic_set> and
 C<isl_printer_print_basic_map> no longer print a newline.
 
+=item * The functions C<isl_flow_get_no_source>
+and C<isl_union_map_compute_flow> now return
+the accesses for which no source could be found instead of
+the iterations where those accesses occur.
+
 =back
 
 =head1 Installation
@@ -2403,7 +2408,7 @@ then value based dependence analysis is performed.
                int (*fn)(__isl_take isl_map *dep, int must,
                          void *dep_user, void *user),
                void *user);
-       __isl_give isl_set *isl_flow_get_no_source(
+       __isl_give isl_map *isl_flow_get_no_source(
                __isl_keep isl_flow *deps, int must);
        void isl_flow_free(__isl_take isl_flow *deps);
 
@@ -2441,16 +2446,16 @@ called explicitly, because it is called implicitly by
 C<isl_access_info_compute_flow>.
 
 The result of the dependence analysis is collected in an
-C<isl_flow>.  There may be elements in the domain of
+C<isl_flow>.  There may be elements of
 the sink access for which no preceding source access could be
 found or for which all preceding sources are I<may> accesses.
-The sets of these elements can be obtained through
+The relations containing these elements can be obtained through
 calls to C<isl_flow_get_no_source>, the first with C<must> set
 and the second with C<must> unset.
 In the case of standard flow dependence analysis,
 with the sink a read and the sources I<must> writes,
-the first set corresponds to the reads from uninitialized
-array elements and the second set is empty.
+the first relation corresponds to the reads from uninitialized
+array elements and the second relation is empty.
 The actual flow dependences can be extracted using
 C<isl_flow_foreach>.  This function will call the user-specified
 callback function C<fn> for each B<non-empty> dependence between
@@ -2477,14 +2482,16 @@ by the following function.
                __isl_take isl_union_map *schedule,
                __isl_give isl_union_map **must_dep,
                __isl_give isl_union_map **may_dep,
-               __isl_give isl_union_set **must_no_source,
-               __isl_give isl_union_set **may_no_source);
+               __isl_give isl_union_map **must_no_source,
+               __isl_give isl_union_map **may_no_source);
 
 The arrays are identified by the tuple names of the ranges
 of the accesses.  The iteration domains by the tuple names
 of the domains of the accesses and of the schedule.
 The relative order of the iteration domains is given by the
-schedule.  Any of C<must_dep>, C<may_dep>, C<must_no_source>
+schedule.  The relations returned through C<must_no_source>
+and C<may_no_source> are subsets of C<sink>.
+Any of C<must_dep>, C<may_dep>, C<must_no_source>
 or C<may_no_source> may be C<NULL>, but a C<NULL> value for
 any of the other arguments is treated as an error.
 

diff --git a/include/isl/flow.h b/include/isl/flow.h
index 9394094..839f142 100644 (file)
--- a/include/isl/flow.h
+++ b/include/isl/flow.h
@@ -31,7 +31,7 @@ __isl_give isl_flow *isl_access_info_compute_flow(__isl_take isl_access_info *ac
 int isl_flow_foreach(__isl_keep isl_flow *deps,
        int (*fn)(__isl_take isl_map *dep, int must, void *dep_user, void *user),
        void *user);
-__isl_give isl_set *isl_flow_get_no_source(__isl_keep isl_flow *deps, int must);
+__isl_give isl_map *isl_flow_get_no_source(__isl_keep isl_flow *deps, int must);
 void isl_flow_free(__isl_take isl_flow *deps);
 
 int isl_union_map_compute_flow(__isl_take isl_union_map *sink,
@@ -39,8 +39,8 @@ int isl_union_map_compute_flow(__isl_take isl_union_map *sink,
        __isl_take isl_union_map *may_source,
        __isl_take isl_union_map *schedule,
        __isl_give isl_union_map **must_dep, __isl_give isl_union_map **may_dep,
-       __isl_give isl_union_set **must_no_source,
-       __isl_give isl_union_set **may_no_source);
+       __isl_give isl_union_map **must_no_source,
+       __isl_give isl_union_map **may_no_source);
 
 #if defined(__cplusplus)
 }

diff --git a/isl_flow.c b/isl_flow.c
index 3d5aabb..9a269b2 100644 (file)
--- a/isl_flow.c
+++ b/isl_flow.c
@@ -42,8 +42,8 @@ struct isl_access_info {
 
 /* A structure containing the output of dependence analysis:
  * - n_source dependences
- * - a subset of the sink for which definitely no source could be found
- * - a subset of the sink for which possibly no source could be found
+ * - a wrapped subset of the sink for which definitely no source could be found
+ * - a wrapped subset of the sink for which possibly no source could be found
  */
 struct isl_flow {
        isl_set                 *must_no_source;
@@ -323,15 +323,15 @@ int isl_flow_foreach(__isl_keep isl_flow *deps,
 
 /* Return a copy of the subset of the sink for which no source could be found.
  */
-__isl_give isl_set *isl_flow_get_no_source(__isl_keep isl_flow *deps, int must)
+__isl_give isl_map *isl_flow_get_no_source(__isl_keep isl_flow *deps, int must)
 {
        if (!deps)
                return NULL;
        
        if (must)
-               return isl_set_copy(deps->must_no_source);
+               return isl_set_unwrap(isl_set_copy(deps->must_no_source));
        else
-               return isl_set_copy(deps->may_no_source);
+               return isl_set_unwrap(isl_set_copy(deps->may_no_source));
 }
 
 void isl_flow_free(__isl_take isl_flow *deps)
@@ -894,10 +894,6 @@ __isl_give isl_flow *isl_access_info_compute_flow(__isl_take isl_access_info *ac
                if (!res->dep[j].map)
                        goto error2;
        }
-       res->must_no_source = isl_set_apply(res->must_no_source,
-                                       isl_map_copy(domain_map));
-       res->may_no_source = isl_set_apply(res->may_no_source,
-                                       isl_map_copy(domain_map));
        if (!res->must_no_source || !res->may_no_source)
                goto error2;
 
@@ -980,8 +976,8 @@ struct isl_compute_flow_data {
        isl_union_map *may_source;
        isl_union_map *must_dep;
        isl_union_map *may_dep;
-       isl_union_set *must_no_source;
-       isl_union_set *may_no_source;
+       isl_union_map *must_no_source;
+       isl_union_map *may_no_source;
 
        int count;
        int must;
@@ -1140,10 +1136,10 @@ static int compute_flow(__isl_take isl_map *map, void *user)
        if (!flow)
                goto error;
 
-       data->must_no_source = isl_union_set_union(data->must_no_source,
-                   isl_union_set_from_set(isl_set_copy(flow->must_no_source)));
-       data->may_no_source = isl_union_set_union(data->may_no_source,
-                   isl_union_set_from_set(isl_set_copy(flow->may_no_source)));
+       data->must_no_source = isl_union_map_union(data->must_no_source,
+                   isl_union_map_from_map(isl_flow_get_no_source(flow, 1)));
+       data->may_no_source = isl_union_map_union(data->may_no_source,
+                   isl_union_map_from_map(isl_flow_get_no_source(flow, 0)));
 
        for (i = 0; i < flow->n_source; ++i) {
                isl_union_map *dep;
@@ -1201,8 +1197,8 @@ int isl_union_map_compute_flow(__isl_take isl_union_map *sink,
        __isl_take isl_union_map *may_source,
        __isl_take isl_union_map *schedule,
        __isl_give isl_union_map **must_dep, __isl_give isl_union_map **may_dep,
-       __isl_give isl_union_set **must_no_source,
-       __isl_give isl_union_set **may_no_source)
+       __isl_give isl_union_map **must_no_source,
+       __isl_give isl_union_map **may_no_source)
 {
        isl_dim *dim;
        isl_union_map *range_map = NULL;
@@ -1233,9 +1229,9 @@ int isl_union_map_compute_flow(__isl_take isl_union_map *sink,
                isl_union_map_empty(isl_dim_copy(dim)) : NULL;
        data.may_dep = may_dep ? isl_union_map_empty(isl_dim_copy(dim)) : NULL;
        data.must_no_source = must_no_source ?
-               isl_union_set_empty(isl_dim_copy(dim)) : NULL;
+               isl_union_map_empty(isl_dim_copy(dim)) : NULL;
        data.may_no_source = may_no_source ?
-               isl_union_set_empty(isl_dim_copy(dim)) : NULL;
+               isl_union_map_empty(isl_dim_copy(dim)) : NULL;
 
        isl_dim_free(dim);
 
@@ -1261,13 +1257,13 @@ int isl_union_map_compute_flow(__isl_take isl_union_map *sink,
                *may_dep = data.may_dep;
        }
        if (must_no_source) {
-               data.must_no_source = isl_union_set_apply(data.must_no_source,
-                                       isl_union_map_copy(range_map));
+               data.must_no_source = isl_union_map_apply_domain(
+                       data.must_no_source, isl_union_map_copy(range_map));
                *must_no_source = data.must_no_source;
        }
        if (may_no_source) {
-               data.may_no_source = isl_union_set_apply(data.may_no_source,
-                                       isl_union_map_copy(range_map));
+               data.may_no_source = isl_union_map_apply_domain(
+                       data.may_no_source, isl_union_map_copy(range_map));
                *may_no_source = data.may_no_source;
        }
 
@@ -1281,8 +1277,8 @@ error:
        isl_union_map_free(may_source);
        isl_union_map_free(data.must_dep);
        isl_union_map_free(data.may_dep);
-       isl_union_set_free(data.must_no_source);
-       isl_union_set_free(data.may_no_source);
+       isl_union_map_free(data.must_no_source);
+       isl_union_map_free(data.may_no_source);
 
        if (must_dep)
                *must_dep = NULL;