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);
isl_space_free(dim);
return 0;
+error:
+ isl_space_free(dim);
+ return -1;
}
/* Add constraints to graph->lp that force validity for the given
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);
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
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);
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
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);
isl_space_free(dim);
return 0;
+error:
+ isl_space_free(dim);
+ return -1;
}
static int add_all_validity_constraints(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]) &&
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);
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;
src->n++;
}
+ dst->max_row = src->max_row;
dst->n_total_row = src->n_total_row;
dst->n_band = src->n_band;
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;
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;
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)));
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)));
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);
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)
{
"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,
"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;
/* 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);
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;
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)
{
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) {
projects / platform / upstream / isl.git / blobdiff