rename isl_basic_set_add to isl_basic_set_add_dims

[platform/upstream/isl.git] / isl_schedule.c

diff --git a/isl_schedule.c b/isl_schedule.c
index f2c3c89..ce334a7 100644 (file)
--- a/isl_schedule.c
+++ b/isl_schedule.c
@@ -1496,6 +1496,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 +1682,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);
@@ -1880,6 +1887,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;
 
@@ -1947,6 +1955,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;
@@ -2048,6 +2057,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;
@@ -2432,6 +2445,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);
 
@@ -2485,8 +2502,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)
 {
@@ -2519,6 +2589,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;
 
@@ -2654,10 +2732,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);
@@ -2697,7 +2779,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;