X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=isl_schedule.c;h=9760c626b78d61a5e16e3b78c2528b31dfe754e2;hb=de51a9bc4da5dd3f1f9f57c2362da6f9752c44e0;hp=ea53db85c8ce149e05b325e95b3a45832ef21396;hpb=63af6a66233bd2bd8fc82b3aa68b81450d1f2081;p=platform%2Fupstream%2Fisl.git diff --git a/isl_schedule.c b/isl_schedule.c index ea53db8..9760c62 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, @@ -26,6 +26,7 @@ #include #include #include +#include /* * The scheduling algorithm implemented in this file was inspired by @@ -62,11 +63,6 @@ * indicating whether the corresponding scheduling dimension results * in zero dependence distances within its band and with respect * to the proximity edges. - * - * index, min_index and on_stack are used during the SCC detection - * index represents the order in which nodes are visited. - * min_index is the index of the root of a (sub)component. - * on_stack indicates whether the node is currently on the stack. */ struct isl_sched_node { isl_space *dim; @@ -83,11 +79,6 @@ struct isl_sched_node { int *band; int *band_id; int *zero; - - /* scc detection */ - int index; - int min_index; - int on_stack; }; static int node_has_dim(const void *entry, const void *val) @@ -174,11 +165,7 @@ enum isl_edge_type { * src_scc and dst_scc are the source and sink SCCs of an edge with * conflicting constraints * - * scc, sp, index and stack are used during the detection of SCCs - * scc is the number of the next SCC - * stack contains the nodes on the path from the root to the current node - * sp is the stack pointer - * index is the index of the last node visited + * scc represents the number of components */ struct isl_sched_graph { isl_hmap_map_basic_set *intra_hmap; @@ -211,11 +198,7 @@ struct isl_sched_graph { int src_scc; int dst_scc; - /* scc detection */ int scc; - int sp; - int index; - int *stack; }; /* Initialize node_table based on the list of nodes. @@ -440,15 +423,13 @@ static int graph_alloc(isl_ctx *ctx, struct isl_sched_graph *graph, graph->node = isl_calloc_array(ctx, struct isl_sched_node, graph->n); graph->sorted = isl_calloc_array(ctx, int, graph->n); graph->region = isl_alloc_array(ctx, struct isl_region, graph->n); - graph->stack = isl_alloc_array(ctx, int, graph->n); graph->edge = isl_calloc_array(ctx, struct isl_sched_edge, graph->n_edge); graph->intra_hmap = isl_hmap_map_basic_set_alloc(ctx, 2 * n_edge); graph->inter_hmap = isl_hmap_map_basic_set_alloc(ctx, 2 * n_edge); - if (!graph->node || !graph->region || !graph->stack || !graph->edge || - !graph->sorted) + if (!graph->node || !graph->region || !graph->edge || !graph->sorted) return -1; for(i = 0; i < graph->n; ++i) @@ -481,7 +462,6 @@ static void graph_free(isl_ctx *ctx, struct isl_sched_graph *graph) isl_map_free(graph->edge[i].map); free(graph->edge); free(graph->region); - free(graph->stack); for (i = 0; i <= isl_edge_last; ++i) isl_hash_table_free(ctx, graph->edge_table[i]); isl_hash_table_free(ctx, graph->node_table); @@ -629,92 +609,60 @@ static int extract_edge(__isl_take isl_map *map, void *user) return graph_edge_table_add(ctx, graph, data->type, edge); } -/* Check whether there is a validity dependence from src to dst, - * forcing dst to follow src (if weak is not set). - * If weak is set, then check if there is any dependence from src to dst. +/* Check whether there is any dependence from node[j] to node[i] + * or from node[i] to node[j]. */ -static int node_follows(struct isl_sched_graph *graph, - struct isl_sched_node *dst, struct isl_sched_node *src, int weak) +static int node_follows_weak(int i, int j, void *user) { - if (weak) - return graph_has_any_edge(graph, src, dst); - else - return graph_has_validity_edge(graph, src, dst); + int f; + struct isl_sched_graph *graph = user; + + f = graph_has_any_edge(graph, &graph->node[j], &graph->node[i]); + if (f < 0 || f) + return f; + return graph_has_any_edge(graph, &graph->node[i], &graph->node[j]); +} + +/* Check whether there is a validity dependence from node[j] to node[i], + * forcing node[i] to follow node[j]. + */ +static int node_follows_strong(int i, int j, void *user) +{ + struct isl_sched_graph *graph = user; + + return graph_has_validity_edge(graph, &graph->node[j], &graph->node[i]); } -/* Perform Tarjan's algorithm for computing the strongly connected components +/* Use Tarjan's algorithm for computing the strongly connected components * in the dependence graph (only validity edges). * If weak is set, we consider the graph to be undirected and * we effectively compute the (weakly) connected components. * Additionally, we also consider other edges when weak is set. */ -static int detect_sccs_tarjan(struct isl_sched_graph *g, int i, int weak) +static int detect_ccs(isl_ctx *ctx, struct isl_sched_graph *graph, int weak) { - int j; - - g->node[i].index = g->index; - g->node[i].min_index = g->index; - g->node[i].on_stack = 1; - g->index++; - g->stack[g->sp++] = i; + int i, n; + struct isl_tarjan_graph *g = NULL; - for (j = g->n - 1; j >= 0; --j) { - int f; + g = isl_tarjan_graph_init(ctx, graph->n, + weak ? &node_follows_weak : &node_follows_strong, graph); + if (!g) + return -1; - if (j == i) - continue; - if (g->node[j].index >= 0 && - (!g->node[j].on_stack || - g->node[j].index > g->node[i].min_index)) - continue; - - f = node_follows(g, &g->node[i], &g->node[j], weak); - if (f < 0) - return -1; - if (!f && weak) { - f = node_follows(g, &g->node[j], &g->node[i], weak); - if (f < 0) - return -1; + graph->scc = 0; + i = 0; + n = graph->n; + while (n) { + while (g->order[i] != -1) { + graph->node[g->order[i]].scc = graph->scc; + --n; + ++i; } - if (!f) - continue; - if (g->node[j].index < 0) { - detect_sccs_tarjan(g, j, weak); - if (g->node[j].min_index < g->node[i].min_index) - g->node[i].min_index = g->node[j].min_index; - } else if (g->node[j].index < g->node[i].min_index) - g->node[i].min_index = g->node[j].index; + ++i; + graph->scc++; } - if (g->node[i].index != g->node[i].min_index) - return 0; - - do { - j = g->stack[--g->sp]; - g->node[j].on_stack = 0; - g->node[j].scc = g->scc; - } while (j != i); - g->scc++; - - return 0; -} - -static int detect_ccs(struct isl_sched_graph *graph, int weak) -{ - int i; - - graph->index = 0; - graph->sp = 0; - graph->scc = 0; - for (i = graph->n - 1; i >= 0; --i) - graph->node[i].index = -1; - - for (i = graph->n - 1; i >= 0; --i) { - if (graph->node[i].index >= 0) - continue; - if (detect_sccs_tarjan(graph, i, weak) < 0) - return -1; - } + isl_tarjan_graph_free(g); return 0; } @@ -722,17 +670,17 @@ static int detect_ccs(struct isl_sched_graph *graph, int weak) /* Apply Tarjan's algorithm to detect the strongly connected components * in the dependence graph. */ -static int detect_sccs(struct isl_sched_graph *graph) +static int detect_sccs(isl_ctx *ctx, struct isl_sched_graph *graph) { - return detect_ccs(graph, 0); + return detect_ccs(ctx, graph, 0); } /* Apply Tarjan's algorithm to detect the (weakly) connected components * in the dependence graph. */ -static int detect_wccs(struct isl_sched_graph *graph) +static int detect_wccs(isl_ctx *ctx, struct isl_sched_graph *graph) { - return detect_ccs(graph, 1); + return detect_ccs(ctx, graph, 1); } static int cmp_scc(const void *a, const void *b, void *data) @@ -846,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); @@ -862,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 @@ -903,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); @@ -932,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 @@ -985,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); @@ -1005,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 @@ -1064,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); @@ -1100,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) @@ -1548,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]) && @@ -1728,9 +1701,13 @@ static int sort_statements(isl_ctx *ctx, struct isl_sched_graph *graph) if (graph->n_edge == 0) return 0; - if (detect_sccs(graph) < 0) + 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); @@ -1784,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; @@ -1925,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; @@ -1992,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; @@ -2093,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; @@ -2200,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))); @@ -2248,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))); @@ -2477,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); @@ -2530,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) { @@ -2558,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; @@ -2650,7 +2710,7 @@ static int compute_schedule_wcc(isl_ctx *ctx, struct isl_sched_graph *graph) { int force_zero = 0; - if (detect_sccs(graph) < 0) + if (detect_sccs(ctx, graph) < 0) return -1; if (sort_sccs(graph) < 0) return -1; @@ -2699,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); @@ -2742,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; @@ -2789,10 +2854,10 @@ static int compute_component_schedule(isl_ctx *ctx, static int compute_schedule(isl_ctx *ctx, struct isl_sched_graph *graph) { if (ctx->opt->schedule_fuse == ISL_SCHEDULE_FUSE_MIN) { - if (detect_sccs(graph) < 0) + if (detect_sccs(ctx, graph) < 0) return -1; } else { - if (detect_wccs(graph) < 0) + if (detect_wccs(ctx, graph) < 0) return -1; } @@ -2905,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) { @@ -2918,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) {