diff --git a/isl_flow.c b/isl_flow.c
--- a/isl_flow.c
+++ b/isl_flow.c
* and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
*/
+#include <isl/val.h>
+#include <isl/space.h>
#include <isl/set.h>
#include <isl/map.h>
#include <isl/union_set.h>
#include <isl/flow.h>
#include <isl/schedule_node.h>
#include <isl_sort.h>
+#include <isl/stream.h>
enum isl_restriction_type {
isl_restriction_type_empty,
int must;
};
+typedef isl_bool (*isl_access_coscheduled)(void *first, void *second);
+
/* A structure containing the input for dependence analysis:
* - a sink
* - n_must + n_may (<= max_source) sources
* - a function for determining the relative order of sources and sink
+ * - an optional function "coscheduled" for determining whether sources
+ * may be coscheduled. If "coscheduled" is NULL, then the sources
+ * are assumed not to be coscheduled.
* The must sources are placed before the may sources.
*
* domain_map is an auxiliary map that maps the sink access relation
isl_map *domain_map;
struct isl_labeled_map sink;
isl_access_level_before level_before;
+ isl_access_coscheduled coscheduled;
isl_access_restrict restrict_fn;
void *restrict_user;
return NULL;
}
+/* A helper struct carrying the isl_access_info and an error condition.
+ */
+struct access_sort_info {
+ isl_access_info *access_info;
+ int error;
+};
+
/* Return -n, 0 or n (with n a positive value), depending on whether
* the source access identified by p1 should be sorted before, together
* or after that identified by p2.
* If not, we try to order the two statements based on the description
* of the iteration domains. This results in an arbitrary, but fairly
* stable ordering.
+ *
+ * In case of an error, sort_info.error is set to true and all elements are
+ * reported to be equal.
*/
static int access_sort_cmp(const void *p1, const void *p2, void *user)
{
- isl_access_info *acc = user;
+ struct access_sort_info *sort_info = user;
+ isl_access_info *acc = sort_info->access_info;
+
+ if (sort_info->error)
+ return 0;
+
const struct isl_labeled_map *i1, *i2;
int level1, level2;
uint32_t h1, h2;
i2 = (const struct isl_labeled_map *) p2;
level1 = acc->level_before(i1->data, i2->data);
+ if (level1 < 0)
+ goto error;
if (level1 % 2)
return -1;
level2 = acc->level_before(i2->data, i1->data);
+ if (level2 < 0)
+ goto error;
if (level2 % 2)
return 1;
h1 = isl_map_get_hash(i1->map);
h2 = isl_map_get_hash(i2->map);
return h1 > h2 ? 1 : h1 < h2 ? -1 : 0;
+error:
+ sort_info->error = 1;
+ return 0;
}
/* Sort the must source accesses in their textual order.
static __isl_give isl_access_info *isl_access_info_sort_sources(
__isl_take isl_access_info *acc)
{
+ struct access_sort_info sort_info;
+
+ sort_info.access_info = acc;
+ sort_info.error = 0;
+
if (!acc)
return NULL;
if (acc->n_must <= 1)
return acc;
if (isl_sort(acc->source, acc->n_must, sizeof(struct isl_labeled_map),
- access_sort_cmp, acc) < 0)
+ access_sort_cmp, &sort_info) < 0)
+ return isl_access_info_free(acc);
+ if (sort_info.error)
return isl_access_info_free(acc);
return acc;
dep->n_source = n;
for (i = 0; i < acc->n_must; ++i) {
- isl_space *dim;
- dim = space_align_and_join(
+ isl_space *space;
+ space = space_align_and_join(
isl_map_get_space(acc->source[i].map),
isl_space_reverse(isl_map_get_space(acc->sink.map)));
- dep->dep[2 * i].map = isl_map_empty(dim);
+ dep->dep[2 * i].map = isl_map_empty(space);
dep->dep[2 * i + 1].map = isl_map_copy(dep->dep[2 * i].map);
dep->dep[2 * i].data = acc->source[i].data;
dep->dep[2 * i + 1].data = acc->source[i].data;
goto error;
}
for (i = acc->n_must; i < acc->n_must + acc->n_may; ++i) {
- isl_space *dim;
- dim = space_align_and_join(
+ isl_space *space;
+ space = space_align_and_join(
isl_map_get_space(acc->source[i].map),
isl_space_reverse(isl_map_get_space(acc->sink.map)));
- dep->dep[acc->n_must + i].map = isl_map_empty(dim);
+ dep->dep[acc->n_must + i].map = isl_map_empty(space);
dep->dep[acc->n_must + i].data = acc->source[i].data;
dep->dep[acc->n_must + i].must = 0;
if (!dep->dep[acc->n_must + i].map)
@@ -481,12 +519,12 @@ __isl_give isl_map *isl_flow_get_no_source(__isl_keep isl_flow *deps, int must)
return isl_set_unwrap(isl_set_copy(deps->may_no_source));
}
-void isl_flow_free(__isl_take isl_flow *deps)
+__isl_null isl_flow *isl_flow_free(__isl_take isl_flow *deps)
{
int i;
if (!deps)
- return;
+ return NULL;
isl_set_free(deps->must_no_source);
isl_set_free(deps->may_no_source);
if (deps->dep) {
free(deps->dep);
}
free(deps);
+
+ return NULL;
}
isl_ctx *isl_flow_get_ctx(__isl_keep isl_flow *deps)
* be greater than the loop iterator of the range at the last
* of the level/2 shared loops, i.e., loop level/2 - 1.
*/
-static __isl_give isl_map *after_at_level(__isl_take isl_space *dim, int level)
+static __isl_give isl_map *after_at_level(__isl_take isl_space *space,
+ int level)
{
struct isl_basic_map *bmap;
if (level % 2)
- bmap = isl_basic_map_equal(dim, level/2);
+ bmap = isl_basic_map_equal(space, level/2);
else
- bmap = isl_basic_map_more_at(dim, level/2 - 1);
+ bmap = isl_basic_map_more_at(space, level/2 - 1);
return isl_map_from_basic_map(bmap);
}
int k, int after_level,
struct isl_set **empty)
{
- isl_space *dim;
+ isl_space *space;
struct isl_set *set_C;
struct isl_map *read_map;
struct isl_map *write_map;
write_map = isl_map_reverse(write_map);
dep_map = isl_map_apply_range(read_map, write_map);
- dim = space_align_and_join(isl_map_get_space(acc->source[k].map),
+ space = space_align_and_join(isl_map_get_space(acc->source[k].map),
isl_space_reverse(isl_map_get_space(acc->source[j].map)));
- after_write = after_at_level(dim, after_level);
+ after_write = after_at_level(space, after_level);
after_write = isl_map_apply_range(after_write, old_map);
after_write = isl_map_reverse(after_write);
dep_map = isl_map_intersect(dep_map, after_write);
*
* If temp_rel[j] is empty, then there can be no improvement and
* we return immediately.
+ *
+ * This function returns isl_stat_ok in case it was executed successfully and
+ * isl_stat_error in case of errors during the execution of this function.
*/
-static int intermediate_sources(__isl_keep isl_access_info *acc,
+static isl_stat intermediate_sources(__isl_keep isl_access_info *acc,
struct isl_map **temp_rel, int j, int sink_level)
{
int k, level;
- int depth = 2 * isl_map_dim(acc->source[j].map, isl_dim_in) + 1;
+ isl_size n_in = isl_map_dim(acc->source[j].map, isl_dim_in);
+ int depth = 2 * n_in + 1;
+ if (n_in < 0)
+ return isl_stat_error;
if (isl_map_plain_is_empty(temp_rel[j]))
- return 0;
+ return isl_stat_ok;
for (k = j - 1; k >= 0; --k) {
int plevel, plevel2;
plevel = acc->level_before(acc->source[k].data, acc->sink.data);
+ if (plevel < 0)
+ return isl_stat_error;
if (!can_precede_at_level(plevel, sink_level))
continue;
plevel2 = acc->level_before(acc->source[j].data,
acc->source[k].data);
+ if (plevel2 < 0)
+ return isl_stat_error;
for (level = sink_level; level <= depth; ++level) {
struct isl_map *T;
}
}
- return 0;
+ return isl_stat_ok;
}
/* Compute all iterations of may source j that precedes the sink at the given
__isl_take isl_map *old_map,
int j, int before_level, int k, int after_level)
{
- isl_space *dim;
+ isl_space *space;
isl_set *set_C;
isl_map *read_map;
isl_map *write_map;
write_map = isl_map_reverse(write_map);
dep_map = isl_map_apply_range(read_map, write_map);
- dim = isl_space_join(isl_map_get_space(acc->source[acc->n_must + j].map),
+ space = isl_space_join(isl_map_get_space(
+ acc->source[acc->n_must + j].map),
isl_space_reverse(isl_map_get_space(acc->source[k].map)));
- after_write = after_at_level(dim, after_level);
+ after_write = after_at_level(space, after_level);
after_write = isl_map_apply_range(after_write, old_map);
after_write = isl_map_reverse(after_write);
dep_map = isl_map_intersect(dep_map, after_write);
int j, int sink_level)
{
int k, level;
- int depth = 2 * isl_map_dim(acc->source[acc->n_must + j].map,
- isl_dim_in) + 1;
+ isl_size n_in = isl_map_dim(acc->source[acc->n_must + j].map,
+ isl_dim_in);
+ int depth = 2 * n_in + 1;
+ if (n_in < 0)
+ return isl_map_free(map);
for (k = 0; k < acc->n_must; ++k) {
int plevel;
plevel = acc->level_before(acc->source[k].data,
acc->source[acc->n_must + j].data);
+ if (plevel < 0)
+ return isl_map_free(map);
for (level = sink_level; level <= depth; ++level) {
isl_map *T;
return map;
}
+/* Given a dependence relation "old_map" between a must-source and the sink,
+ * return a subset of the dependences, augmented with instances
+ * of the source at position "pos" in "acc" that are coscheduled
+ * with the must-source and that access the same element.
+ * That is, if the input lives in a space T -> K, then the output
+ * lives in the space [T -> S] -> K, with S the space of source "pos", and
+ * the domain factor of the domain product is a subset of the input.
+ * The sources are considered to be coscheduled if they have the same values
+ * for the initial "depth" coordinates.
+ *
+ * First construct a dependence relation S -> K and a mapping
+ * between coscheduled sources T -> S.
+ * The second is combined with the original dependence relation T -> K
+ * to form a relation in T -> [S -> K], which is subsequently
+ * uncurried to [T -> S] -> K.
+ * This result is then intersected with the dependence relation S -> K
+ * to form the output.
+ *
+ * In case a negative depth is given, NULL is returned to indicate an error.
+ */
+static __isl_give isl_map *coscheduled_source(__isl_keep isl_access_info *acc,
+ __isl_keep isl_map *old_map, int pos, int depth)
+{
+ isl_space *space;
+ isl_set *set_C;
+ isl_map *read_map;
+ isl_map *write_map;
+ isl_map *dep_map;
+ isl_map *equal;
+ isl_map *map;
+
+ if (depth < 0)
+ return NULL;
+
+ set_C = isl_map_range(isl_map_copy(old_map));
+ read_map = isl_map_copy(acc->sink.map);
+ read_map = isl_map_intersect_domain(read_map, set_C);
+ write_map = isl_map_copy(acc->source[pos].map);
+ dep_map = isl_map_domain_product(write_map, read_map);
+ dep_map = isl_set_unwrap(isl_map_domain(dep_map));
+ space = isl_space_join(isl_map_get_space(old_map),
+ isl_space_reverse(isl_map_get_space(dep_map)));
+ equal = isl_map_from_basic_map(isl_basic_map_equal(space, depth));
+ map = isl_map_range_product(equal, isl_map_copy(old_map));
+ map = isl_map_uncurry(map);
+ map = isl_map_intersect_domain_factor_range(map, dep_map);
+
+ return map;
+}
+
+/* After the dependences derived from a must-source have been computed
+ * at a certain level, check if any of the sources of the must-dependences
+ * may be coscheduled with other sources.
+ * If they are any such sources, then there is no way of determining
+ * which of the sources actually comes last and the must-dependences
+ * need to be turned into may-dependences, while dependences from
+ * the other sources need to be added to the may-dependences as well.
+ * "acc" describes the sources and a callback for checking whether
+ * two sources may be coscheduled. If acc->coscheduled is NULL then
+ * the sources are assumed not to be coscheduled.
+ * "must_rel" and "may_rel" describe the must and may-dependence relations
+ * computed at the current level for the must-sources. Some of the dependences
+ * may be moved from "must_rel" to "may_rel".
+ * "flow" contains all dependences computed so far (apart from those
+ * in "must_rel" and "may_rel") and may be updated with additional
+ * dependences derived from may-sources.
+ *
+ * In particular, consider all the must-sources with a non-empty
+ * dependence relation in "must_rel". They are considered in reverse
+ * order because that is the order in which they are considered in the caller.
+ * If any of the must-sources are coscheduled, then the last one
+ * is the one that will have a corresponding dependence relation.
+ * For each must-source i, consider both all the previous must-sources
+ * and all the may-sources. If any of those may be coscheduled with
+ * must-source i, then compute the coscheduled instances that access
+ * the same memory elements. The result is a relation [T -> S] -> K.
+ * The projection onto T -> K is a subset of the must-dependence relation
+ * that needs to be turned into may-dependences.
+ * The projection onto S -> K needs to be added to the may-dependences
+ * of source S.
+ * Since a given must-source instance may be coscheduled with several
+ * other source instances, the dependences that need to be turned
+ * into may-dependences are first collected and only actually removed
+ * from the must-dependences after all other sources have been considered.
+ */
+static __isl_give isl_flow *handle_coscheduled(__isl_keep isl_access_info *acc,
+ __isl_keep isl_map **must_rel, __isl_keep isl_map **may_rel,
+ __isl_take isl_flow *flow)
+{
+ int i, j;
+
+ if (!acc->coscheduled)
+ return flow;
+ for (i = acc->n_must - 1; i >= 0; --i) {
+ isl_map *move;
+
+ if (isl_map_plain_is_empty(must_rel[i]))
+ continue;
+ move = isl_map_empty(isl_map_get_space(must_rel[i]));
+ for (j = i - 1; j >= 0; --j) {
+ int depth;
+ isl_bool coscheduled;
+ isl_map *map, *factor;
+
+ coscheduled = acc->coscheduled(acc->source[i].data,
+ acc->source[j].data);
+ if (coscheduled < 0) {
+ isl_map_free(move);
+ return isl_flow_free(flow);
+ }
+ if (!coscheduled)
+ continue;
+ depth = acc->level_before(acc->source[i].data,
+ acc->source[j].data) / 2;
+ map = coscheduled_source(acc, must_rel[i], j, depth);
+ factor = isl_map_domain_factor_range(isl_map_copy(map));
+ may_rel[j] = isl_map_union(may_rel[j], factor);
+ map = isl_map_domain_factor_domain(map);
+ move = isl_map_union(move, map);
+ }
+ for (j = 0; j < acc->n_may; ++j) {
+ int depth, pos;
+ isl_bool coscheduled;
+ isl_map *map, *factor;
+
+ pos = acc->n_must + j;
+ coscheduled = acc->coscheduled(acc->source[i].data,
+ acc->source[pos].data);
+ if (coscheduled < 0) {
+ isl_map_free(move);
+ return isl_flow_free(flow);
+ }
+ if (!coscheduled)
+ continue;
+ depth = acc->level_before(acc->source[i].data,
+ acc->source[pos].data) / 2;
+ map = coscheduled_source(acc, must_rel[i], pos, depth);
+ factor = isl_map_domain_factor_range(isl_map_copy(map));
+ pos = 2 * acc->n_must + j;
+ flow->dep[pos].map = isl_map_union(flow->dep[pos].map,
+ factor);
+ map = isl_map_domain_factor_domain(map);
+ move = isl_map_union(move, map);
+ }
+ must_rel[i] = isl_map_subtract(must_rel[i], isl_map_copy(move));
+ may_rel[i] = isl_map_union(may_rel[i], move);
+ }
+
+ return flow;
+}
+
/* Compute dependences for the case where all accesses are "may"
* accesses, which boils down to computing memory based dependences.
* The generic algorithm would also work in this case, but it would
for (i = 0; i < acc->n_may; ++i) {
int plevel;
int is_before;
- isl_space *dim;
+ isl_space *space;
isl_map *before;
isl_map *dep;
plevel = acc->level_before(acc->source[i].data, acc->sink.data);
+ if (plevel < 0)
+ goto error;
+
is_before = plevel & 1;
plevel >>= 1;
- dim = isl_map_get_space(res->dep[i].map);
+ space = isl_map_get_space(res->dep[i].map);
if (is_before)
- before = isl_map_lex_le_first(dim, plevel);
+ before = isl_map_lex_le_first(space, plevel);
else
- before = isl_map_lex_lt_first(dim, plevel);
+ before = isl_map_lex_lt_first(space, plevel);
dep = isl_map_apply_range(isl_map_copy(acc->source[i].map),
isl_map_reverse(isl_map_copy(acc->sink.map)));
dep = isl_map_intersect(dep, before);
res->must_no_source = mustdo;
return res;
+error:
+ isl_set_free(mustdo);
+ isl_set_free(maydo);
+ isl_flow_free(res);
+ return NULL;
}
/* Compute dependences for the case where there is at least one
* need to be considered. These iterations are split into those that
* haven't been matched to any source access (mustdo) and those that have only
* been matched to may accesses (maydo).
- * At the end of each level, we also consider the may accesses.
+ * At the end of each level, must-sources and may-sources that are coscheduled
+ * with the sources of the must-dependences at that level are considered.
+ * If any coscheduled instances are found, then corresponding may-dependences
+ * are added and the original must-dependences are turned into may-dependences.
+ * Afterwards, the may accesses that occur after must-dependence sources
+ * are considered.
* In particular, we consider may accesses that precede the remaining
* sink iterations, moving elements from mustdo to maydo when appropriate,
* and may accesses that occur between a must source and a sink of any
isl_set *mustdo = NULL;
isl_set *maydo = NULL;
int level, j;
+ isl_size n_in;
int depth;
isl_map **must_rel = NULL;
isl_map **may_rel = NULL;
goto error;
ctx = isl_map_get_ctx(acc->sink.map);
- depth = 2 * isl_map_dim(acc->sink.map, isl_dim_in) + 1;
+ n_in = isl_map_dim(acc->sink.map, isl_dim_in);
+ if (n_in < 0)
+ goto error;
+ depth = 2 * n_in + 1;
mustdo = isl_map_domain(isl_map_copy(acc->sink.map));
maydo = isl_set_empty(isl_set_get_space(mustdo));
if (!mustdo || !maydo)
if (isl_set_plain_is_empty(mustdo))
goto done;
- must_rel = isl_alloc_array(ctx, struct isl_map *, acc->n_must);
- may_rel = isl_alloc_array(ctx, struct isl_map *, acc->n_must);
+ must_rel = isl_calloc_array(ctx, struct isl_map *, acc->n_must);
+ may_rel = isl_calloc_array(ctx, struct isl_map *, acc->n_must);
if (!must_rel || !may_rel)
goto error;
plevel = acc->level_before(acc->source[j].data,
acc->sink.data);
+ if (plevel < 0)
+ goto error;
if (!can_precede_at_level(plevel, level))
continue;
must_rel[j] = isl_map_union_disjoint(must_rel[j], T);
mustdo = rest;
- intermediate_sources(acc, must_rel, j, level);
+ if (intermediate_sources(acc, must_rel, j, level) < 0)
+ goto error;
T = last_source(acc, maydo, j, level, &rest);
may_rel[j] = isl_map_union_disjoint(may_rel[j], T);
maydo = rest;
- intermediate_sources(acc, may_rel, j, level);
+ if (intermediate_sources(acc, may_rel, j, level) < 0)
+ goto error;
if (isl_set_plain_is_empty(mustdo) &&
isl_set_plain_is_empty(maydo))
plevel = acc->level_before(acc->source[j].data,
acc->sink.data);
+ if (plevel < 0)
+ goto error;
if (!can_precede_at_level(plevel, level))
continue;
- intermediate_sources(acc, must_rel, j, level);
- intermediate_sources(acc, may_rel, j, level);
+ if (intermediate_sources(acc, must_rel, j, level) < 0)
+ goto error;
+ if (intermediate_sources(acc, may_rel, j, level) < 0)
+ goto error;
}
+ res = handle_coscheduled(acc, must_rel, may_rel, res);
+ if (!res)
+ goto error;
+
for (j = 0; j < acc->n_may; ++j) {
int plevel;
isl_map *T;
plevel = acc->level_before(acc->source[acc->n_must + j].data,
acc->sink.data);
+ if (plevel < 0)
+ goto error;
if (!can_precede_at_level(plevel, level))
continue;
res->may_no_source = maydo;
return res;
error:
+ if (must_rel)
+ for (j = 0; j < acc->n_must; ++j)
+ isl_map_free(must_rel[j]);
+ if (may_rel)
+ for (j = 0; j < acc->n_must; ++j)
+ isl_map_free(may_rel[j]);
isl_flow_free(res);
isl_set_free(mustdo);
isl_set_free(maydo);
__isl_keep isl_map *map)
{
isl_ctx *ctx;
- isl_space *dim;
+ isl_space *space;
struct isl_sched_info *info;
- int i, n;
+ int i;
+ isl_size n;
if (!map)
return NULL;
- dim = isl_space_unwrap(isl_space_domain(isl_map_get_space(map)));
- if (!dim)
+ space = isl_space_unwrap(isl_space_domain(isl_map_get_space(map)));
+ if (!space)
+ return NULL;
+ n = isl_space_dim(space, isl_dim_in);
+ isl_space_free(space);
+ if (n < 0)
return NULL;
- n = isl_space_dim(dim, isl_dim_in);
- isl_space_free(dim);
ctx = isl_map_get_ctx(map);
info = isl_alloc_type(ctx, struct isl_sched_info);
* "isl_access_sink" represents the sink accesses.
* "isl_access_must_source" represents the definite source accesses.
* "isl_access_may_source" represents the possible source accesses.
+ * "isl_access_kill" represents the kills.
*
* isl_access_sink is sometimes treated differently and
* should therefore appear first.
isl_access_sink,
isl_access_must_source,
isl_access_may_source,
+ isl_access_kill,
isl_access_end
};
@@ -1285,45 +1535,72 @@ isl_ctx *isl_union_access_info_get_ctx(__isl_keep isl_union_access_info *access)
return isl_union_map_get_ctx(access->access[isl_access_sink]);
}
-/* Create a new isl_union_access_info with the given sink accesses and
- * and no other accesses or schedule information.
+/* Construct an empty (invalid) isl_union_access_info object.
+ * The caller is responsible for setting the sink access relation and
+ * initializing all the other fields, e.g., by calling
+ * isl_union_access_info_init.
+ */
+static __isl_give isl_union_access_info *isl_union_access_info_alloc(
+ isl_ctx *ctx)
+{
+ return isl_calloc_type(ctx, isl_union_access_info);
+}
+
+/* Initialize all the fields of "info", except the sink access relation,
+ * which is assumed to have been set by the caller.
*
* By default, we use the schedule field of the isl_union_access_info,
* but this may be overridden by a call
* to isl_union_access_info_set_schedule_map.
*/
-__isl_give isl_union_access_info *isl_union_access_info_from_sink(
- __isl_take isl_union_map *sink)
+static __isl_give isl_union_access_info *isl_union_access_info_init(
+ __isl_take isl_union_access_info *info)
{
- isl_ctx *ctx;
isl_space *space;
isl_union_map *empty;
- isl_union_access_info *access;
enum isl_access_type i;
- if (!sink)
+ if (!info)
return NULL;
- ctx = isl_union_map_get_ctx(sink);
- access = isl_alloc_type(ctx, isl_union_access_info);
- if (!access)
- goto error;
+ if (!info->access[isl_access_sink])
+ return isl_union_access_info_free(info);
- space = isl_union_map_get_space(sink);
+ space = isl_union_map_get_space(info->access[isl_access_sink]);
empty = isl_union_map_empty(isl_space_copy(space));
- access->access[isl_access_sink] = sink;
for (i = isl_access_sink + 1; i < isl_access_end; ++i)
- access->access[i] = isl_union_map_copy(empty);
+ if (!info->access[i])
+ info->access[i] = isl_union_map_copy(empty);
isl_union_map_free(empty);
- access->schedule = isl_schedule_empty(space);
- access->schedule_map = NULL;
+ if (!info->schedule && !info->schedule_map)
+ info->schedule = isl_schedule_empty(isl_space_copy(space));
+ isl_space_free(space);
- for (i = isl_access_sink; i < isl_access_end; ++i)
- if (!access->access[i])
- return isl_union_access_info_free(access);
- if (!access->schedule)
- return isl_union_access_info_free(access);
+ for (i = isl_access_sink + 1; i < isl_access_end; ++i)
+ if (!info->access[i])
+ return isl_union_access_info_free(info);
+ if (!info->schedule && !info->schedule_map)
+ return isl_union_access_info_free(info);
- return access;
+ return info;
+}
+
+/* Create a new isl_union_access_info with the given sink accesses and
+ * and no other accesses or schedule information.
+ */
+__isl_give isl_union_access_info *isl_union_access_info_from_sink(
+ __isl_take isl_union_map *sink)
+{
+ isl_ctx *ctx;
+ isl_union_access_info *access;
+
+ if (!sink)
+ return NULL;
+ ctx = isl_union_map_get_ctx(sink);
+ access = isl_union_access_info_alloc(ctx);
+ if (!access)
+ goto error;
+ access->access[isl_access_sink] = sink;
+ return isl_union_access_info_init(access);
error:
isl_union_map_free(sink);
return NULL;
may_source);
}
+/* Replace the kills of "info" by "kill".
+ */
+__isl_give isl_union_access_info *isl_union_access_info_set_kill(
+ __isl_take isl_union_access_info *info, __isl_take isl_union_map *kill)
+{
+ return isl_union_access_info_set(info, isl_access_kill, kill);
+}
+
+/* Return the access relation of type "type" of "info".
+ */
+static __isl_give isl_union_map *isl_union_access_info_get(
+ __isl_keep isl_union_access_info *info, enum isl_access_type type)
+{
+ if (!info)
+ return NULL;
+ return isl_union_map_copy(info->access[type]);
+}
+
+/* Return the definite source accesses of "info".
+ */
+__isl_give isl_union_map *isl_union_access_info_get_must_source(
+ __isl_keep isl_union_access_info *info)
+{
+ return isl_union_access_info_get(info, isl_access_must_source);
+}
+
+/* Return the possible source accesses of "info".
+ */
+__isl_give isl_union_map *isl_union_access_info_get_may_source(
+ __isl_keep isl_union_access_info *info)
+{
+ return isl_union_access_info_get(info, isl_access_may_source);
+}
+
+/* Return the kills of "info".
+ */
+__isl_give isl_union_map *isl_union_access_info_get_kill(
+ __isl_keep isl_union_access_info *info)
+{
+ return isl_union_access_info_get(info, isl_access_kill);
+}
+
+/* Does "info" specify any kills?
+ */
+static isl_bool isl_union_access_has_kill(
+ __isl_keep isl_union_access_info *info)
+{
+ isl_bool empty;
+
+ if (!info)
+ return isl_bool_error;
+ empty = isl_union_map_is_empty(info->access[isl_access_kill]);
+ return isl_bool_not(empty);
+}
+
/* Replace the schedule of "access" by "schedule".
* Also free the schedule_map in case it was set last.
*/
return copy;
}
-/* Print a key-value pair of a YAML mapping to "p",
- * with key "name" and value "umap".
- */
-static __isl_give isl_printer *print_union_map_field(__isl_take isl_printer *p,
- const char *name, __isl_keep isl_union_map *umap)
-{
- p = isl_printer_print_str(p, name);
- p = isl_printer_yaml_next(p);
- p = isl_printer_print_str(p, "\"");
- p = isl_printer_print_union_map(p, umap);
- p = isl_printer_print_str(p, "\"");
- p = isl_printer_yaml_next(p);
-
- return p;
-}
+#undef BASE
+#define BASE union_map
+#include "print_yaml_field_templ.c"
/* An enumeration of the various keys that may appear in a YAML mapping
* of an isl_union_access_info object.
@@ -1455,11 +1775,14 @@ static __isl_give isl_printer *print_union_map_field(__isl_take isl_printer *p,
* as the access relation types in isl_access_type.
*/
enum isl_ai_key {
+ isl_ai_key_error = -1,
isl_ai_key_sink = isl_access_sink,
isl_ai_key_must_source = isl_access_must_source,
isl_ai_key_may_source = isl_access_may_source,
+ isl_ai_key_kill = isl_access_kill,
isl_ai_key_schedule_map,
isl_ai_key_schedule,
+ isl_ai_key_end
};
/* Textual representations of the YAML keys for an isl_union_access_info
[isl_ai_key_sink] = "sink",
[isl_ai_key_must_source] = "must_source",
[isl_ai_key_may_source] = "may_source",
+ [isl_ai_key_kill] = "kill",
[isl_ai_key_schedule_map] = "schedule_map",
[isl_ai_key_schedule] = "schedule",
};
if (empty)
return p;
}
- return print_union_map_field(p, key_str[type], info->access[type]);
+ return print_yaml_field_union_map(p, key_str[type], info->access[type]);
}
/* Print the information contained in "access" to "p".
p = isl_printer_print_schedule(p, access->schedule);
p = isl_printer_yaml_next(p);
} else {
- p = print_union_map_field(p, key_str[isl_ai_key_schedule_map],
- access->schedule_map);
+ p = print_yaml_field_union_map(p,
+ key_str[isl_ai_key_schedule_map], access->schedule_map);
}
p = isl_printer_yaml_end_mapping(p);
return s;
}
+#undef KEY
+#define KEY enum isl_ai_key
+#undef KEY_ERROR
+#define KEY_ERROR isl_ai_key_error
+#undef KEY_END
+#define KEY_END isl_ai_key_end
+#undef KEY_STR
+#define KEY_STR key_str
+#undef KEY_EXTRACT
+#define KEY_EXTRACT extract_key
+#undef KEY_GET
+#define KEY_GET get_key
+#include "extract_key.c"
+
+#undef BASE
+#define BASE union_map
+#include "read_in_string_templ.c"
+
+/* Read an isl_union_access_info object from "s".
+ *
+ * Start off with an empty (invalid) isl_union_access_info object and
+ * then fill up the fields based on the input.
+ * The input needs to contain at least a description of the sink
+ * access relation as well as some form of schedule.
+ * The other access relations are set to empty relations
+ * by isl_union_access_info_init if they are not specified in the input.
+ */
+__isl_give isl_union_access_info *isl_stream_read_union_access_info(
+ isl_stream *s)
+{
+ isl_ctx *ctx;
+ isl_union_access_info *info;
+ isl_bool more;
+ int sink_set = 0;
+ int schedule_set = 0;
+
+ if (isl_stream_yaml_read_start_mapping(s) < 0)
+ return NULL;
+
+ ctx = isl_stream_get_ctx(s);
+ info = isl_union_access_info_alloc(ctx);
+ while ((more = isl_stream_yaml_next(s)) == isl_bool_true) {
+ enum isl_ai_key key;
+ enum isl_access_type type;
+ isl_union_map *access, *schedule_map;
+ isl_schedule *schedule;
+
+ key = get_key(s);
+ if (isl_stream_yaml_next(s) < 0)
+ return isl_union_access_info_free(info);
+ switch (key) {
+ case isl_ai_key_end:
+ case isl_ai_key_error:
+ return isl_union_access_info_free(info);
+ case isl_ai_key_sink:
+ sink_set = 1;
+ case isl_ai_key_must_source:
+ case isl_ai_key_may_source:
+ case isl_ai_key_kill:
+ type = (enum isl_access_type) key;
+ access = read_union_map(s);
+ info = isl_union_access_info_set(info, type, access);
+ if (!info)
+ return NULL;
+ break;
+ case isl_ai_key_schedule_map:
+ schedule_set = 1;
+ schedule_map = read_union_map(s);
+ info = isl_union_access_info_set_schedule_map(info,
+ schedule_map);
+ if (!info)
+ return NULL;
+ break;
+ case isl_ai_key_schedule:
+ schedule_set = 1;
+ schedule = isl_stream_read_schedule(s);
+ info = isl_union_access_info_set_schedule(info,
+ schedule);
+ if (!info)
+ return NULL;
+ break;
+ }
+ }
+ if (more < 0)
+ return isl_union_access_info_free(info);
+
+ if (isl_stream_yaml_read_end_mapping(s) < 0)
+ return isl_union_access_info_free(info);
+
+ if (!sink_set) {
+ isl_stream_error(s, NULL, "no sink specified");
+ return isl_union_access_info_free(info);
+ }
+
+ if (!schedule_set) {
+ isl_stream_error(s, NULL, "no schedule specified");
+ return isl_union_access_info_free(info);
+ }
+
+ return isl_union_access_info_init(info);
+}
+
+/* Read an isl_union_access_info object from the file "input".
+ */
+__isl_give isl_union_access_info *isl_union_access_info_read_from_file(
+ isl_ctx *ctx, FILE *input)
+{
+ isl_stream *s;
+ isl_union_access_info *access;
+
+ s = isl_stream_new_file(ctx, input);
+ if (!s)
+ return NULL;
+ access = isl_stream_read_union_access_info(s);
+ isl_stream_free(s);
+
+ return access;
+}
+
/* Update the fields of "access" such that they all have the same parameters,
* keeping in mind that the schedule_map field may be NULL and ignoring
* the schedule field.
static isl_stat count_matching_array(__isl_take isl_map *map, void *user)
{
int eq;
- isl_space *dim;
+ isl_space *space;
struct isl_compute_flow_data *data;
data = (struct isl_compute_flow_data *)user;
- dim = isl_space_range(isl_map_get_space(map));
+ space = isl_space_range(isl_map_get_space(map));
- eq = isl_space_is_equal(dim, data->dim);
+ eq = isl_space_is_equal(space, data->dim);
- isl_space_free(dim);
+ isl_space_free(space);
isl_map_free(map);
if (eq < 0)
static isl_stat collect_matching_array(__isl_take isl_map *map, void *user)
{
int eq;
- isl_space *dim;
+ isl_space *space;
struct isl_sched_info *info;
struct isl_compute_flow_data *data;
data = (struct isl_compute_flow_data *)user;
- dim = isl_space_range(isl_map_get_space(map));
+ space = isl_space_range(isl_map_get_space(map));
- eq = isl_space_is_equal(dim, data->dim);
+ eq = isl_space_is_equal(space, data->dim);
- isl_space_free(dim);
+ isl_space_free(space);
if (eq < 0)
goto error;
{
struct isl_sched_info *info1 = first;
struct isl_sched_info *info2 = second;
- int n1, n2;
+ isl_size n1, n2;
int i;
n1 = isl_vec_size(info1->cst);
n2 = isl_vec_size(info2->cst);
+ if (n1 < 0 || n2 < 0)
+ return -1;
if (n2 < n1)
n1 = n2;
return 2 * n1;
}
+/* Check if the given two accesses may be coscheduled.
+ * If so, return isl_bool_true. Otherwise return isl_bool_false.
+ *
+ * Two accesses may only be coscheduled if the fixed schedule
+ * coordinates have the same values.
+ */
+static isl_bool coscheduled(void *first, void *second)
+{
+ struct isl_sched_info *info1 = first;
+ struct isl_sched_info *info2 = second;
+ isl_size n1, n2;
+ int i;
+
+ n1 = isl_vec_size(info1->cst);
+ n2 = isl_vec_size(info2->cst);
+ if (n1 < 0 || n2 < 0)
+ return isl_bool_error;
+
+ if (n2 < n1)
+ n1 = n2;
+
+ for (i = 0; i < n1; ++i) {
+ int cmp;
+
+ if (!info1->is_cst[i])
+ continue;
+ if (!info2->is_cst[i])
+ continue;
+ cmp = isl_vec_cmp_element(info1->cst, info2->cst, i);
+ if (cmp != 0)
+ return isl_bool_false;
+ }
+
+ return isl_bool_true;
+}
+
/* Given a sink access, look for all the source accesses that access
* the same array and perform dataflow analysis on them using
* isl_access_info_compute_flow_core.
if (!data->sink_info || (data->count && !data->source_info) ||
!data->accesses)
goto error;
+ data->accesses->coscheduled = &coscheduled;
data->count = 0;
data->must = 1;
if (isl_union_map_foreach_map(data->must_source,
return isl_stat_error;
}
+/* Add the kills of "info" to the must-sources.
+ */
+static __isl_give isl_union_access_info *
+isl_union_access_info_add_kill_to_must_source(
+ __isl_take isl_union_access_info *info)
+{
+ isl_union_map *must, *kill;
+
+ must = isl_union_access_info_get_must_source(info);
+ kill = isl_union_access_info_get_kill(info);
+ must = isl_union_map_union(must, kill);
+ return isl_union_access_info_set_must_source(info, must);
+}
+
+/* Drop dependences from "flow" that purely originate from kills.
+ * That is, only keep those dependences that originate from
+ * the original must-sources "must" and/or the original may-sources "may".
+ * In particular, "must" contains the must-sources from before
+ * the kills were added and "may" contains the may-source from before
+ * the kills were removed.
+ *
+ * The dependences are of the form
+ *
+ * Source -> [Sink -> Data]
+ *
+ * Only those dependences are kept where the Source -> Data part
+ * is a subset of the original may-sources or must-sources.
+ * Of those, only the must-dependences that intersect with the must-sources
+ * remain must-dependences.
+ * If there is some overlap between the may-sources and the must-sources,
+ * then the may-dependences and must-dependences may also overlap.
+ * This should be fine since the may-dependences are only kept
+ * disjoint from the must-dependences for the isl_union_map_compute_flow
+ * interface. This interface does not support kills, so it will
+ * not end up calling this function.
+ */
+static __isl_give isl_union_flow *isl_union_flow_drop_kill_source(
+ __isl_take isl_union_flow *flow, __isl_take isl_union_map *must,
+ __isl_take isl_union_map *may)
+{
+ isl_union_map *move;
+
+ if (!flow)
+ goto error;
+ move = isl_union_map_copy(flow->must_dep);
+ move = isl_union_map_intersect_range_factor_range(move,
+ isl_union_map_copy(may));
+ may = isl_union_map_union(may, isl_union_map_copy(must));
+ flow->may_dep = isl_union_map_intersect_range_factor_range(
+ flow->may_dep, may);
+ flow->must_dep = isl_union_map_intersect_range_factor_range(
+ flow->must_dep, must);
+ flow->may_dep = isl_union_map_union(flow->may_dep, move);
+ if (!flow->must_dep || !flow->may_dep)
+ return isl_union_flow_free(flow);
+
+ return flow;
+error:
+ isl_union_map_free(must);
+ isl_union_map_free(may);
+ return NULL;
+}
+
/* Remove the must accesses from the may accesses.
*
* A must access always trumps a may access, so there is no need
isl_union_set *domain;
isl_union_map *umap;
isl_bool r = isl_bool_false;
+ isl_size n;
if (isl_schedule_node_get_type(node) != isl_schedule_node_leaf)
return isl_bool_true;
umap = isl_union_map_copy(data->access->access[isl_access_sink]);
umap = isl_union_map_intersect_domain(umap, isl_union_set_copy(domain));
- data->n_sink += isl_union_map_n_map(umap);
+ data->n_sink += n = isl_union_map_n_map(umap);
isl_union_map_free(umap);
- if (!umap)
+ if (n < 0)
r = isl_bool_error;
umap = isl_union_map_copy(data->access->access[isl_access_must_source]);
umap = isl_union_map_intersect_domain(umap, isl_union_set_copy(domain));
- data->n_source += isl_union_map_n_map(umap);
+ data->n_source += n = isl_union_map_n_map(umap);
isl_union_map_free(umap);
- if (!umap)
+ if (n < 0)
r = isl_bool_error;
umap = isl_union_map_copy(data->access->access[isl_access_may_source]);
umap = isl_union_map_intersect_domain(umap, isl_union_set_copy(domain));
- data->n_source += isl_union_map_n_map(umap);
+ data->n_source += n = isl_union_map_n_map(umap);
isl_union_map_free(umap);
- if (!umap)
+ if (n < 0)
r = isl_bool_error;
isl_union_set_free(domain);
isl_schedule_node *node1 = first;
isl_schedule_node *node2 = second;
isl_schedule_node *shared;
- int depth;
+ isl_size depth;
int before = 0;
shared = isl_schedule_node_get_shared_ancestor(node1, node2);
- if (!shared)
+ depth = isl_schedule_node_get_schedule_depth(shared);
+ if (depth < 0) {
+ isl_schedule_node_free(shared);
return -1;
+ }
- depth = isl_schedule_node_get_schedule_depth(shared);
if (isl_schedule_node_get_type(shared) == isl_schedule_node_sequence) {
- int pos1, pos2;
+ isl_size pos1, pos2;
pos1 = isl_schedule_node_get_ancestor_child_position(node1,
shared);
pos2 = isl_schedule_node_get_ancestor_child_position(node2,
shared);
+ if (pos1 < 0 || pos2 < 0) {
+ isl_schedule_node_free(shared);
+ return -1;
+ }
before = pos1 < pos2;
}
return 2 * depth + before;
}
+/* Check if the given two accesses may be coscheduled.
+ * If so, return isl_bool_true. Otherwise return isl_bool_false.
+ *
+ * Two accesses may only be coscheduled if they appear in the same leaf.
+ */
+static isl_bool coscheduled_node(void *first, void *second)
+{
+ isl_schedule_node *node1 = first;
+ isl_schedule_node *node2 = second;
+
+ return isl_bool_ok(node1 == node2);
+}
+
/* Add the scheduled sources from "data" that access
* the same data space as "sink" to "access".
*/
access = isl_access_info_alloc(isl_map_copy(sink->access), sink->node,
&before_node, data->n_source);
+ if (access)
+ access->coscheduled = &coscheduled_node;
access = add_matching_sources(access, sink, data);
flow = access_info_compute_flow_core(access);
* map domain elements of access->{may,must)_source to
* domain elements of access->sink.
*
+ * If any kills have been specified, then they are treated as
+ * must-sources internally. Any dependence that purely derives
+ * from an original kill is removed from the output.
+ *
* We check whether the schedule is available as a schedule tree
* or a schedule map and call the corresponding function to perform
* the analysis.
__isl_give isl_union_flow *isl_union_access_info_compute_flow(
__isl_take isl_union_access_info *access)
{
+ isl_bool has_kill;
+ isl_union_map *must = NULL, *may = NULL;
+ isl_union_flow *flow;
+
+ has_kill = isl_union_access_has_kill(access);
+ if (has_kill < 0)
+ goto error;
+ if (has_kill) {
+ must = isl_union_access_info_get_must_source(access);
+ may = isl_union_access_info_get_may_source(access);
+ }
+ access = isl_union_access_info_add_kill_to_must_source(access);
access = isl_union_access_info_normalize(access);
if (!access)
- return NULL;
+ goto error;
if (access->schedule)
- return compute_flow_schedule(access);
+ flow = compute_flow_schedule(access);
else
- return compute_flow_union_map(access);
+ flow = compute_flow_union_map(access);
+ if (has_kill)
+ flow = isl_union_flow_drop_kill_source(flow, must, may);
+ return flow;
+error:
+ isl_union_access_info_free(access);
+ isl_union_map_free(must);
+ isl_union_map_free(may);
+ return NULL;
}
/* Print the information contained in "flow" to "p".
p = isl_printer_yaml_start_mapping(p);
umap = isl_union_flow_get_full_must_dependence(flow);
- p = print_union_map_field(p, "must_dependence", umap);
+ p = print_yaml_field_union_map(p, "must_dependence", umap);
isl_union_map_free(umap);
umap = isl_union_flow_get_full_may_dependence(flow);
- p = print_union_map_field(p, "may_dependence", umap);
+ p = print_yaml_field_union_map(p, "may_dependence", umap);
isl_union_map_free(umap);
- p = print_union_map_field(p, "must_no_source", flow->must_no_source);
+ p = print_yaml_field_union_map(p, "must_no_source",
+ flow->must_no_source);
umap = isl_union_flow_get_may_no_source(flow);
- p = print_union_map_field(p, "may_no_source", umap);
+ p = print_yaml_field_union_map(p, "may_no_source", umap);
isl_union_map_free(umap);
p = isl_printer_yaml_end_mapping(p);