X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=isl_schedule.c;h=9760c626b78d61a5e16e3b78c2528b31dfe754e2;hb=de51a9bc4da5dd3f1f9f57c2362da6f9752c44e0;hp=dc9e19f684f74ce3f563b97f7e4923dbac7ee745;hpb=056289f285e62c52cc59ee826172e4d3092ef3fe;p=platform%2Fupstream%2Fisl.git diff --git a/isl_schedule.c b/isl_schedule.c index dc9e19f..9760c62 100644 --- a/isl_schedule.c +++ b/isl_schedule.c @@ -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) { @@ -2506,12 +2609,21 @@ 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; @@ -2647,10 +2759,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 +2806,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; @@ -2853,10 +2970,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) { @@ -2866,8 +3056,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) {