X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=isl_schedule.c;h=51e9dc0554696db6c425fd68ea5848cd5b8066dd;hb=3961a579833bebbcd7192f4f4fa5464937b6562a;hp=8a6cb804ae045525b70fd5d30e5044f74cf91f87;hpb=bde2ea2094179a3fc97b4fb9ddf2b17691f58622;p=platform%2Fupstream%2Fisl.git

diff --git a/isl_schedule.c b/isl_schedule.c
index 8a6cb80..51e9dc0 100644
--- a/isl_schedule.c
+++ b/isl_schedule.c
@@ -1,7 +1,7 @@
 /*
  * Copyright 2011      INRIA Saclay
  *
- * Use of this software is governed by the GNU LGPLv2.1 license
+ * 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,
@@ -794,6 +794,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 +812,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 +856,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 +887,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 +945,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 +967,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 +1029,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 +1067,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)
@@ -1496,6 +1518,9 @@ static int update_schedule(struct isl_sched_graph *graph,
 	if (sol->size == 0)
 		isl_die(sol->ctx, isl_error_internal,
 			"no solution found", goto error);
+	if (graph->n_total_row >= graph->max_row)
+		isl_die(sol->ctx, isl_error_internal,
+			"too many schedule rows", goto error);
 
 	if (check_zero)
 		zero = isl_int_is_zero(sol->el[1]) &&
@@ -1679,6 +1704,10 @@ static int sort_statements(isl_ctx *ctx, struct isl_sched_graph *graph)
 	if (detect_sccs(ctx, graph) < 0)
 		return -1;
 
+	if (graph->n_total_row >= graph->max_row)
+		isl_die(ctx, isl_error_internal,
+			"too many schedule rows", return -1);
+
 	for (i = 0; i < graph->n; ++i) {
 		struct isl_sched_node *node = &graph->node[i];
 		int row = isl_mat_rows(node->sched);
@@ -1732,11 +1761,18 @@ static __isl_give isl_schedule *extract_schedule(struct isl_sched_graph *graph,
 		int r, b;
 		int *band_end, *band_id, *zero;
 
+		sched->node[i].sched =
+			node_extract_schedule_multi_aff(&graph->node[i]);
+		if (!sched->node[i].sched)
+			goto error;
+
+		sched->node[i].n_band = graph->n_band;
+		if (graph->n_band == 0)
+			continue;
+
 		band_end = isl_alloc_array(ctx, int, graph->n_band);
 		band_id = isl_alloc_array(ctx, int, graph->n_band);
 		zero = isl_alloc_array(ctx, int, graph->n_total_row);
-		sched->node[i].sched =
-			node_extract_schedule_multi_aff(&graph->node[i]);
 		sched->node[i].band_end = band_end;
 		sched->node[i].band_id = band_id;
 		sched->node[i].zero = zero;
@@ -1873,6 +1909,7 @@ static int copy_schedule(struct isl_sched_graph *dst,
 		src->n++;
 	}
 
+	dst->max_row = src->max_row;
 	dst->n_total_row = src->n_total_row;
 	dst->n_band = src->n_band;
 
@@ -1940,6 +1977,7 @@ static int compute_sub_schedule(isl_ctx *ctx,
 	if (copy_edges(ctx, &split, graph, edge_pred, data) < 0)
 		goto error;
 	split.n_row = graph->n_row;
+	split.max_row = graph->max_row;
 	split.n_total_row = graph->n_total_row;
 	split.n_band = graph->n_band;
 	split.band_start = graph->band_start;
@@ -2041,6 +2079,10 @@ static int compute_split_schedule(isl_ctx *ctx, struct isl_sched_graph *graph)
 	int n_band, orig_band;
 	int drop;
 
+	if (graph->n_total_row >= graph->max_row)
+		isl_die(ctx, isl_error_internal,
+			"too many schedule rows", return -1);
+
 	drop = graph->n_total_row - graph->band_start;
 	graph->n_total_row -= drop;
 	graph->n_row -= drop;
@@ -2148,6 +2190,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)));
 
@@ -2196,6 +2240,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)));
 
@@ -2425,6 +2471,10 @@ static int split_scaled(isl_ctx *ctx, struct isl_sched_graph *graph)
 	if (graph->n <= 1)
 		return 0;
 
+	if (graph->n_total_row >= graph->max_row)
+		isl_die(ctx, isl_error_internal,
+			"too many schedule rows", return -1);
+
 	isl_int_init(gcd);
 	isl_int_init(gcd_i);
 
@@ -2478,8 +2528,61 @@ error:
 	return -1;
 }
 
+static int compute_component_schedule(isl_ctx *ctx,
+	struct isl_sched_graph *graph);
+
+/* Is the schedule row "sol" trivial on node "node"?
+ * That is, is the solution zero on the dimensions orthogonal to
+ * the previously found solutions?
+ * Each coefficient is represented as the difference between
+ * two non-negative values in "sol".  The coefficient is then
+ * zero if those two values are equal to each other.
+ */
+static int is_trivial(struct isl_sched_node *node, __isl_keep isl_vec *sol)
+{
+	int i;
+	int pos;
+	int len;
+
+	pos = 1 + node->start + 1 + 2 * (node->nparam + node->rank);
+	len = 2 * (node->nvar - node->rank);
+
+	if (len == 0)
+		return 0;
+
+	for (i = 0; i < len; i += 2)
+		if (isl_int_ne(sol->el[pos + i], sol->el[pos + i + 1]))
+			return 0;
+
+	return 1;
+}
+
+/* Is the schedule row "sol" trivial on any node where it should
+ * not be trivial?
+ */
+static int is_any_trivial(struct isl_sched_graph *graph,
+	__isl_keep isl_vec *sol)
+{
+	int i;
+
+	for (i = 0; i < graph->n; ++i) {
+		struct isl_sched_node *node = &graph->node[i];
+
+		if (!needs_row(graph, node))
+			continue;
+		if (is_trivial(node, sol))
+			return 1;
+	}
+
+	return 0;
+}
+
 /* Construct a schedule row for each node such that as many dependences
  * as possible are carried and then continue with the next band.
+ *
+ * If the computed schedule row turns out to be trivial on one or
+ * more nodes where it should not be trivial, then we throw it away
+ * and try again on each component separately.
  */
 static int carry_dependences(isl_ctx *ctx, struct isl_sched_graph *graph)
 {
@@ -2512,6 +2615,14 @@ static int carry_dependences(isl_ctx *ctx, struct isl_sched_graph *graph)
 			"unable to carry dependences", return -1);
 	}
 
+	if (is_any_trivial(graph, sol)) {
+		isl_vec_free(sol);
+		if (graph->scc > 1)
+			return compute_component_schedule(ctx, graph);
+		isl_die(ctx, isl_error_unknown,
+			"unable to construct non-trivial solution", return -1);
+	}
+
 	if (update_schedule(graph, sol, 0, 0) < 0)
 		return -1;
 
@@ -2647,10 +2758,14 @@ static int compute_schedule_wcc(isl_ctx *ctx, struct isl_sched_graph *graph)
 /* Add a row to the schedules that separates the SCCs and move
  * to the next band.
  */
-static int split_on_scc(struct isl_sched_graph *graph)
+static int split_on_scc(isl_ctx *ctx, struct isl_sched_graph *graph)
 {
 	int i;
 
+	if (graph->n_total_row >= graph->max_row)
+		isl_die(ctx, isl_error_internal,
+			"too many schedule rows", return -1);
+
 	for (i = 0; i < graph->n; ++i) {
 		struct isl_sched_node *node = &graph->node[i];
 		int row = isl_mat_rows(node->sched);
@@ -2690,7 +2805,8 @@ static int compute_component_schedule(isl_ctx *ctx,
 
 	if (ctx->opt->schedule_fuse == ISL_SCHEDULE_FUSE_MIN ||
 	    ctx->opt->schedule_separate_components)
-		split_on_scc(graph);
+		if (split_on_scc(ctx, graph) < 0)
+			return -1;
 
 	n_total_row = 0;
 	orig_total_row = graph->n_total_row;