/*
* Copyright 2011 INRIA Saclay
+ * Copyright 2012-2013 Ecole Normale Superieure
*
* Use of this software is governed by the MIT license
*
* Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
* Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
* 91893 Orsay, France
+ * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
*/
#include <isl_ctx_private.h>
#include <isl_sort.h>
#include <isl_schedule_private.h>
#include <isl_band_private.h>
-#include <isl_list_private.h>
#include <isl_options_private.h>
#include <isl_tarjan.h>
return entry->data;
}
-/* Check whether the dependence graph has an edge of the give type
+/* Check whether the dependence graph has an edge of the given type
* between the given two nodes.
*/
static int graph_has_edge(struct isl_sched_graph *graph,
"error in schedule construction", return -1);
}
+ isl_int_divexact(sol->el[1], sol->el[1], sol->el[0]);
if (isl_int_cmp_si(sol->el[1], n_edge) >= 0) {
isl_vec_free(sol);
isl_die(ctx, isl_error_unknown,
* Because of the way the schedule is constructed, we know that
* the position of the band inside the schedule of a node is the same
* for all active nodes.
+ *
+ * The partial schedule for the band is created before the children
+ * are created to that construct_band_list can refer to the partial
+ * schedule of the parent.
*/
static __isl_give isl_band *construct_band(__isl_keep isl_schedule *schedule,
__isl_keep isl_band *parent,
band->parent = parent;
for (i = 0; i < schedule->n; ++i)
- if (active[i] && schedule->node[i].n_band > band_nr + 1)
- break;
-
- if (i < schedule->n) {
- band->children = construct_band_list(schedule, band,
- band_nr + 1, active, n_active);
- if (!band->children)
- goto error;
- }
-
- for (i = 0; i < schedule->n; ++i)
if (active[i])
break;
if (!band->pma)
goto error;
+ for (i = 0; i < schedule->n; ++i)
+ if (active[i] && schedule->node[i].n_band > band_nr + 1)
+ break;
+
+ if (i < schedule->n) {
+ band->children = construct_band_list(schedule, band,
+ band_nr + 1, active, n_active);
+ if (!band->children)
+ goto error;
+ }
+
return band;
error:
isl_band_free(band);
return NULL;
}
+/* Internal data structure used inside cmp_band and pw_multi_aff_extract_int.
+ *
+ * r is set to a negative value if anything goes wrong.
+ *
+ * c1 stores the result of extract_int.
+ * c2 is a temporary value used inside cmp_band_in_ancestor.
+ * t is a temporary value used inside extract_int.
+ *
+ * first and equal are used inside extract_int.
+ * first is set if we are looking at the first isl_multi_aff inside
+ * the isl_union_pw_multi_aff.
+ * equal is set if all the isl_multi_affs have been equal so far.
+ */
+struct isl_cmp_band_data {
+ int r;
+
+ int first;
+ int equal;
+
+ isl_int t;
+ isl_int c1;
+ isl_int c2;
+};
+
+/* Check if "ma" assigns a constant value.
+ * Note that this function is only called on isl_multi_affs
+ * with a single output dimension.
+ *
+ * If "ma" assigns a constant value then we compare it to data->c1
+ * or assign it to data->c1 if this is the first isl_multi_aff we consider.
+ * If "ma" does not assign a constant value or if it assigns a value
+ * that is different from data->c1, then we set data->equal to zero
+ * and terminate the check.
+ */
+static int multi_aff_extract_int(__isl_take isl_set *set,
+ __isl_take isl_multi_aff *ma, void *user)
+{
+ isl_aff *aff;
+ struct isl_cmp_band_data *data = user;
+
+ aff = isl_multi_aff_get_aff(ma, 0);
+ data->r = isl_aff_is_cst(aff);
+ if (data->r >= 0 && data->r) {
+ isl_aff_get_constant(aff, &data->t);
+ if (data->first) {
+ isl_int_set(data->c1, data->t);
+ data->first = 0;
+ } else if (!isl_int_eq(data->c1, data->t))
+ data->equal = 0;
+ } else if (data->r >= 0 && !data->r)
+ data->equal = 0;
+
+ isl_aff_free(aff);
+ isl_set_free(set);
+ isl_multi_aff_free(ma);
+
+ if (data->r < 0)
+ return -1;
+ if (!data->equal)
+ return -1;
+ return 0;
+}
+
+/* This function is called for each isl_pw_multi_aff in
+ * the isl_union_pw_multi_aff checked by extract_int.
+ * Check all the isl_multi_affs inside "pma".
+ */
+static int pw_multi_aff_extract_int(__isl_take isl_pw_multi_aff *pma,
+ void *user)
+{
+ int r;
+
+ r = isl_pw_multi_aff_foreach_piece(pma, &multi_aff_extract_int, user);
+ isl_pw_multi_aff_free(pma);
+
+ return r;
+}
+
+/* Check if "upma" assigns a single constant value to its domain.
+ * If so, return 1 and store the result in data->c1.
+ * If not, return 0.
+ *
+ * A negative return value from isl_union_pw_multi_aff_foreach_pw_multi_aff
+ * means that either an error occurred or that we have broken off the check
+ * because we already know the result is going to be negative.
+ * In the latter case, data->equal is set to zero.
+ */
+static int extract_int(__isl_keep isl_union_pw_multi_aff *upma,
+ struct isl_cmp_band_data *data)
+{
+ data->first = 1;
+ data->equal = 1;
+
+ if (isl_union_pw_multi_aff_foreach_pw_multi_aff(upma,
+ &pw_multi_aff_extract_int, data) < 0) {
+ if (!data->equal)
+ return 0;
+ return -1;
+ }
+
+ return !data->first && data->equal;
+}
+
+/* Compare "b1" and "b2" based on the parent schedule of their ancestor
+ * "ancestor".
+ *
+ * If the parent of "ancestor" also has a single member, then we
+ * first try to compare the two band based on the partial schedule
+ * of this parent.
+ *
+ * Otherwise, or if the result is inconclusive, we look at the partial schedule
+ * of "ancestor" itself.
+ * In particular, we specialize the parent schedule based
+ * on the domains of the child schedules, check if both assign
+ * a single constant value and, if so, compare the two constant values.
+ * If the specialized parent schedules do not assign a constant value,
+ * then they cannot be used to order the two bands and so in this case
+ * we return 0.
+ */
+static int cmp_band_in_ancestor(__isl_keep isl_band *b1,
+ __isl_keep isl_band *b2, struct isl_cmp_band_data *data,
+ __isl_keep isl_band *ancestor)
+{
+ isl_union_pw_multi_aff *upma;
+ isl_union_set *domain;
+ int r;
+
+ if (data->r < 0)
+ return 0;
+
+ if (ancestor->parent && ancestor->parent->n == 1) {
+ r = cmp_band_in_ancestor(b1, b2, data, ancestor->parent);
+ if (data->r < 0)
+ return 0;
+ if (r)
+ return r;
+ }
+
+ upma = isl_union_pw_multi_aff_copy(b1->pma);
+ domain = isl_union_pw_multi_aff_domain(upma);
+ upma = isl_union_pw_multi_aff_copy(ancestor->pma);
+ upma = isl_union_pw_multi_aff_intersect_domain(upma, domain);
+ r = extract_int(upma, data);
+ isl_union_pw_multi_aff_free(upma);
+
+ if (r < 0)
+ data->r = -1;
+ if (r < 0 || !r)
+ return 0;
+
+ isl_int_set(data->c2, data->c1);
+
+ upma = isl_union_pw_multi_aff_copy(b2->pma);
+ domain = isl_union_pw_multi_aff_domain(upma);
+ upma = isl_union_pw_multi_aff_copy(ancestor->pma);
+ upma = isl_union_pw_multi_aff_intersect_domain(upma, domain);
+ r = extract_int(upma, data);
+ isl_union_pw_multi_aff_free(upma);
+
+ if (r < 0)
+ data->r = -1;
+ if (r < 0 || !r)
+ return 0;
+
+ return isl_int_cmp(data->c2, data->c1);
+}
+
+/* Compare "a" and "b" based on the parent schedule of their parent.
+ */
+static int cmp_band(const void *a, const void *b, void *user)
+{
+ isl_band *b1 = *(isl_band * const *) a;
+ isl_band *b2 = *(isl_band * const *) b;
+ struct isl_cmp_band_data *data = user;
+
+ return cmp_band_in_ancestor(b1, b2, data, b1->parent);
+}
+
+/* Sort the elements in "list" based on the partial schedules of its parent
+ * (and ancestors). In particular if the parent assigns constant values
+ * to the domains of the bands in "list", then the elements are sorted
+ * according to that order.
+ * This order should be a more "natural" order for the user, but otherwise
+ * shouldn't have any effect.
+ * If we would be constructing an isl_band forest directly in
+ * isl_union_set_compute_schedule then there wouldn't be any need
+ * for a reordering, since the children would be added to the list
+ * in their natural order automatically.
+ *
+ * If there is only one element in the list, then there is no need to sort
+ * anything.
+ * If the partial schedule of the parent has more than one member
+ * (or if there is no parent), then it's
+ * defnitely not assigning constant values to the different children in
+ * the list and so we wouldn't be able to use it to sort the list.
+ */
+static __isl_give isl_band_list *sort_band_list(__isl_take isl_band_list *list,
+ __isl_keep isl_band *parent)
+{
+ struct isl_cmp_band_data data;
+
+ if (!list)
+ return NULL;
+ if (list->n <= 1)
+ return list;
+ if (!parent || parent->n != 1)
+ return list;
+
+ data.r = 0;
+ isl_int_init(data.c1);
+ isl_int_init(data.c2);
+ isl_int_init(data.t);
+ isl_sort(list->p, list->n, sizeof(list->p[0]), &cmp_band, &data);
+ if (data.r < 0)
+ list = isl_band_list_free(list);
+ isl_int_clear(data.c1);
+ isl_int_clear(data.c2);
+ isl_int_clear(data.t);
+
+ return list;
+}
+
/* Construct a list of bands that start at the same position (with
* sequence number band_nr) in the schedules of the nodes that
* were active in the parent band.
free(active);
+ list = sort_band_list(list, parent);
+
return list;
}
projects / platform / upstream / isl.git / blobdiff