X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=isl_schedule.c;h=032b6377d9523ec0e2921de95192c3d2daa7a98e;hb=296aafbbff2f2e0c06dff9d58ca5ce22d22999b3;hp=ce334a77f687fb19122b9504f4831c461808cb89;hpb=ace4762b6575201448368b5f9a51e95eb8e65012;p=platform%2Fupstream%2Fisl.git

diff --git a/isl_schedule.c b/isl_schedule.c
index ce334a7..032b637 100644
--- a/isl_schedule.c
+++ b/isl_schedule.c
@@ -1,11 +1,13 @@
 /*
  * 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>
@@ -326,7 +328,7 @@ static struct isl_sched_edge *graph_find_edge(struct isl_sched_graph *graph,
 	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,
@@ -794,6 +796,8 @@ static int add_intra_validity_constraints(struct isl_sched_graph *graph,
 
 	coef = isl_basic_set_transform_dims(coef, isl_dim_set,
 		    isl_space_dim(dim, isl_dim_set), isl_mat_copy(node->cmap));
+	if (!coef)
+		goto error;
 
 	total = isl_basic_set_total_dim(graph->lp);
 	dim_map = isl_dim_map_alloc(ctx, total);
@@ -810,6 +814,9 @@ static int add_intra_validity_constraints(struct isl_sched_graph *graph,
 	isl_space_free(dim);
 
 	return 0;
+error:
+	isl_space_free(dim);
+	return -1;
 }
 
 /* Add constraints to graph->lp that force validity for the given
@@ -851,6 +858,8 @@ static int add_inter_validity_constraints(struct isl_sched_graph *graph,
 	coef = isl_basic_set_transform_dims(coef, isl_dim_set,
 		    isl_space_dim(dim, isl_dim_set) + src->nvar,
 		    isl_mat_copy(dst->cmap));
+	if (!coef)
+		goto error;
 
 	total = isl_basic_set_total_dim(graph->lp);
 	dim_map = isl_dim_map_alloc(ctx, total);
@@ -880,10 +889,15 @@ static int add_inter_validity_constraints(struct isl_sched_graph *graph,
 			coef->n_eq, coef->n_ineq);
 	graph->lp = isl_basic_set_add_constraints_dim_map(graph->lp,
 							   coef, dim_map);
+	if (!graph->lp)
+		goto error;
 	isl_space_free(dim);
 	edge->end = graph->lp->n_ineq;
 
 	return 0;
+error:
+	isl_space_free(dim);
+	return -1;
 }
 
 /* Add constraints to graph->lp that bound the dependence distance for the given
@@ -933,6 +947,8 @@ static int add_intra_proximity_constraints(struct isl_sched_graph *graph,
 
 	coef = isl_basic_set_transform_dims(coef, isl_dim_set,
 		    isl_space_dim(dim, isl_dim_set), isl_mat_copy(node->cmap));
+	if (!coef)
+		goto error;
 
 	nparam = isl_space_dim(node->dim, isl_dim_param);
 	total = isl_basic_set_total_dim(graph->lp);
@@ -953,6 +969,9 @@ static int add_intra_proximity_constraints(struct isl_sched_graph *graph,
 	isl_space_free(dim);
 
 	return 0;
+error:
+	isl_space_free(dim);
+	return -1;
 }
 
 /* Add constraints to graph->lp that bound the dependence distance for the given
@@ -1012,6 +1031,8 @@ static int add_inter_proximity_constraints(struct isl_sched_graph *graph,
 	coef = isl_basic_set_transform_dims(coef, isl_dim_set,
 		    isl_space_dim(dim, isl_dim_set) + src->nvar,
 		    isl_mat_copy(dst->cmap));
+	if (!coef)
+		goto error;
 
 	nparam = isl_space_dim(src->dim, isl_dim_param);
 	total = isl_basic_set_total_dim(graph->lp);
@@ -1048,6 +1069,9 @@ static int add_inter_proximity_constraints(struct isl_sched_graph *graph,
 	isl_space_free(dim);
 
 	return 0;
+error:
+	isl_space_free(dim);
+	return -1;
 }
 
 static int add_all_validity_constraints(struct isl_sched_graph *graph)
@@ -2168,6 +2192,8 @@ static int add_intra_constraints(struct isl_sched_graph *graph,
 	struct isl_sched_node *node = edge->src;
 
 	coef = intra_coefficients(graph, map);
+	if (!coef)
+		return -1;
 
 	dim = isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef)));
 
@@ -2216,6 +2242,8 @@ static int add_inter_constraints(struct isl_sched_graph *graph,
 	struct isl_sched_node *dst = edge->dst;
 
 	coef = inter_coefficients(graph, map);
+	if (!coef)
+		return -1;
 
 	dim = isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef)));
 
@@ -2943,10 +2971,83 @@ isl_ctx *isl_schedule_get_ctx(__isl_keep isl_schedule *schedule)
 	return schedule ? isl_space_get_ctx(schedule->dim) : NULL;
 }
 
+/* Set max_out to the maximal number of output dimensions over
+ * all maps.
+ */
+static int update_max_out(__isl_take isl_map *map, void *user)
+{
+	int *max_out = user;
+	int n_out = isl_map_dim(map, isl_dim_out);
+
+	if (n_out > *max_out)
+		*max_out = n_out;
+
+	isl_map_free(map);
+	return 0;
+}
+
+/* Internal data structure for map_pad_range.
+ *
+ * "max_out" is the maximal schedule dimension.
+ * "res" collects the results.
+ */
+struct isl_pad_schedule_map_data {
+	int max_out;
+	isl_union_map *res;
+};
+
+/* Pad the range of the given map with zeros to data->max_out and
+ * then add the result to data->res.
+ */
+static int map_pad_range(__isl_take isl_map *map, void *user)
+{
+	struct isl_pad_schedule_map_data *data = user;
+	int i;
+	int n_out = isl_map_dim(map, isl_dim_out);
+
+	map = isl_map_add_dims(map, isl_dim_out, data->max_out - n_out);
+	for (i = n_out; i < data->max_out; ++i)
+		map = isl_map_fix_si(map, isl_dim_out, i, 0);
+
+	data->res = isl_union_map_add_map(data->res, map);
+	if (!data->res)
+		return -1;
+
+	return 0;
+}
+
+/* Pad the ranges of the maps in the union map with zeros such they all have
+ * the same dimension.
+ */
+static __isl_give isl_union_map *pad_schedule_map(
+	__isl_take isl_union_map *umap)
+{
+	struct isl_pad_schedule_map_data data;
+
+	if (!umap)
+		return NULL;
+	if (isl_union_map_n_map(umap) <= 1)
+		return umap;
+
+	data.max_out = 0;
+	if (isl_union_map_foreach_map(umap, &update_max_out, &data.max_out) < 0)
+		return isl_union_map_free(umap);
+
+	data.res = isl_union_map_empty(isl_union_map_get_space(umap));
+	if (isl_union_map_foreach_map(umap, &map_pad_range, &data) < 0)
+		data.res = isl_union_map_free(data.res);
+
+	isl_union_map_free(umap);
+	return data.res;
+}
+
 /* Return an isl_union_map of the schedule.  If we have already constructed
  * a band forest, then this band forest may have been modified so we need
  * to extract the isl_union_map from the forest rather than from
- * the originally computed schedule.
+ * the originally computed schedule.  This reconstructed schedule map
+ * then needs to be padded with zeros to unify the schedule space
+ * since the result of isl_band_list_get_suffix_schedule may not have
+ * a unified schedule space.
  */
 __isl_give isl_union_map *isl_schedule_get_map(__isl_keep isl_schedule *sched)
 {
@@ -2956,8 +3057,10 @@ __isl_give isl_union_map *isl_schedule_get_map(__isl_keep isl_schedule *sched)
 	if (!sched)
 		return NULL;
 
-	if (sched->band_forest)
-		return isl_band_list_get_suffix_schedule(sched->band_forest);
+	if (sched->band_forest) {
+		umap = isl_band_list_get_suffix_schedule(sched->band_forest);
+		return pad_schedule_map(umap);
+	}
 
 	umap = isl_union_map_empty(isl_space_copy(sched->dim));
 	for (i = 0; i < sched->n; ++i) {
@@ -2982,6 +3085,10 @@ static __isl_give isl_band_list *construct_band_list(
  * 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,
@@ -3000,17 +3107,6 @@ static __isl_give isl_band *construct_band(__isl_keep isl_schedule *schedule,
 	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;
 
@@ -3050,12 +3146,245 @@ static __isl_give isl_band *construct_band(__isl_keep isl_schedule *schedule,
 	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.
@@ -3140,6 +3469,8 @@ static __isl_give isl_band_list *construct_band_list(
 
 	free(active);
 
+	list = sort_band_list(list, parent);
+
 	return list;
 }