X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=isl_schedule.c;h=9e6e617b79ebaad66709131f0333a20989e0f9f1;hb=db282322bea9eb89e9141849a430c32fcb94ad58;hp=f9443540ca9e6b83de6340e5aceaa8c89550fbad;hpb=5b898f1e08d13ea4cbd90b149df11f5a8e4b7844;p=platform%2Fupstream%2Fisl.git diff --git a/isl_schedule.c b/isl_schedule.c index f944354..9e6e617 100644 --- a/isl_schedule.c +++ b/isl_schedule.c @@ -1,11 +1,13 @@ /* * Copyright 2011 INRIA Saclay + * Copyright 2012-2013 Ecole Normale Superieure * - * 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, * 91893 Orsay, France + * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France */ #include @@ -21,11 +23,12 @@ #include #include #include -#include +#include #include #include #include #include +#include /* * The scheduling algorithm implemented in this file was inspired by @@ -62,11 +65,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 +81,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) @@ -127,6 +120,7 @@ struct isl_sched_edge { enum isl_edge_type { isl_edge_validity = 0, + isl_edge_first = isl_edge_validity, isl_edge_proximity, isl_edge_last = isl_edge_proximity }; @@ -142,6 +136,7 @@ enum isl_edge_type { * n is the number of nodes * node is the list of nodes * maxvar is the maximal number of variables over all nodes + * max_row is the allocated number of rows in the schedule * n_row is the current (maximal) number of linearly independent * rows in the node schedules * n_total_row is the current number of rows in the node schedules @@ -172,11 +167,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; @@ -185,6 +176,7 @@ struct isl_sched_graph { struct isl_sched_node *node; int n; int maxvar; + int max_row; int n_row; int *sorted; @@ -208,11 +200,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. @@ -340,7 +328,7 @@ static struct isl_sched_edge *graph_find_edge(struct isl_sched_graph *graph, return entry->data; } -/* Check whether the dependence graph has an edge of the give type +/* Check whether the dependence graph has an edge of the given type * between the given two nodes. */ static int graph_has_edge(struct isl_sched_graph *graph, @@ -368,10 +356,10 @@ static int graph_has_edge(struct isl_sched_graph *graph, static struct isl_sched_edge *graph_find_any_edge(struct isl_sched_graph *graph, struct isl_sched_node *src, struct isl_sched_node *dst) { - int i; + enum isl_edge_type i; struct isl_sched_edge *edge; - for (i = 0; i <= isl_edge_last; ++i) { + for (i = isl_edge_first; i <= isl_edge_last; ++i) { edge = graph_find_edge(graph, i, src, dst); if (edge) return edge; @@ -386,9 +374,9 @@ static void graph_remove_edge(struct isl_sched_graph *graph, struct isl_sched_edge *edge) { isl_ctx *ctx = isl_map_get_ctx(edge->map); - int i; + enum isl_edge_type i; - for (i = 0; i <= isl_edge_last; ++i) { + for (i = isl_edge_first; i <= isl_edge_last; ++i) { struct isl_hash_table_entry *entry; entry = graph_find_edge_entry(graph, i, edge->src, edge->dst); @@ -406,10 +394,10 @@ static void graph_remove_edge(struct isl_sched_graph *graph, static int graph_has_any_edge(struct isl_sched_graph *graph, struct isl_sched_node *src, struct isl_sched_node *dst) { - int i; + enum isl_edge_type i; int r; - for (i = 0; i <= isl_edge_last; ++i) { + for (i = isl_edge_first; i <= isl_edge_last; ++i) { r = graph_has_edge(graph, i, src, dst); if (r < 0 || r) return r; @@ -437,15 +425,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) @@ -478,13 +464,49 @@ 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); isl_basic_set_free(graph->lp); } +/* For each "set" on which this function is called, increment + * graph->n by one and update graph->maxvar. + */ +static int init_n_maxvar(__isl_take isl_set *set, void *user) +{ + struct isl_sched_graph *graph = user; + int nvar = isl_set_dim(set, isl_dim_set); + + graph->n++; + if (nvar > graph->maxvar) + graph->maxvar = nvar; + + isl_set_free(set); + + return 0; +} + +/* Compute the number of rows that should be allocated for the schedule. + * The graph can be split at most "n - 1" times, there can be at most + * two rows for each dimension in the iteration domains (in particular, + * we usually have one row, but it may be split by split_scaled), + * and there can be one extra row for ordering the statements. + * Note that if we have actually split "n - 1" times, then no ordering + * is needed, so in principle we could use "graph->n + 2 * graph->maxvar - 1". + */ +static int compute_max_row(struct isl_sched_graph *graph, + __isl_keep isl_union_set *domain) +{ + graph->n = 0; + graph->maxvar = 0; + if (isl_union_set_foreach_set(domain, &init_n_maxvar, graph) < 0) + return -1; + graph->max_row = graph->n + 2 * graph->maxvar; + + return 0; +} + /* Add a new node to the graph representing the given set. */ static int extract_node(__isl_take isl_set *set, void *user) @@ -509,11 +531,11 @@ static int extract_node(__isl_take isl_set *set, void *user) graph->node[graph->n].nparam = nparam; graph->node[graph->n].sched = sched; graph->node[graph->n].sched_map = NULL; - band = isl_alloc_array(ctx, int, graph->n_edge + nvar); + band = isl_alloc_array(ctx, int, graph->max_row); graph->node[graph->n].band = band; - band_id = isl_calloc_array(ctx, int, graph->n_edge + nvar); + band_id = isl_calloc_array(ctx, int, graph->max_row); graph->node[graph->n].band_id = band_id; - zero = isl_calloc_array(ctx, int, graph->n_edge + nvar); + zero = isl_calloc_array(ctx, int, graph->max_row); graph->node[graph->n].zero = zero; graph->n++; @@ -589,92 +611,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]); } -/* Perform Tarjan's algorithm for computing the strongly connected components +/* 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]); +} + +/* 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; } @@ -682,17 +672,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) @@ -706,9 +696,9 @@ static int cmp_scc(const void *a, const void *b, void *data) /* Sort the elements of graph->sorted according to the corresponding SCCs. */ -static void sort_sccs(struct isl_sched_graph *graph) +static int sort_sccs(struct isl_sched_graph *graph) { - isl_quicksort(graph->sorted, graph->n, sizeof(int), &cmp_scc, graph); + return isl_sort(graph->sorted, graph->n, sizeof(int), &cmp_scc, graph); } /* Given a dependence relation R from a node to itself, @@ -806,6 +796,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); @@ -822,6 +814,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 @@ -863,6 +858,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); @@ -892,10 +889,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 @@ -945,6 +947,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); @@ -965,6 +969,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 @@ -1024,6 +1031,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); @@ -1060,6 +1069,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) @@ -1508,6 +1520,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]) && @@ -1688,9 +1703,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); @@ -1744,11 +1763,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; @@ -1818,7 +1844,7 @@ static int copy_edges(isl_ctx *ctx, struct isl_sched_graph *dst, int (*edge_pred)(struct isl_sched_edge *edge, int data), int data) { int i; - int t; + enum isl_edge_type t; dst->n_edge = 0; for (i = 0; i < src->n_edge; ++i) { @@ -1850,7 +1876,7 @@ static int copy_edges(isl_ctx *ctx, struct isl_sched_graph *dst, dst->edge[dst->n_edge].proximity = edge->proximity; dst->n_edge++; - for (t = 0; t <= isl_edge_last; ++t) { + for (t = isl_edge_first; t <= isl_edge_last; ++t) { if (edge != graph_find_edge(src, t, edge->src, edge->dst)) continue; @@ -1885,6 +1911,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; @@ -1952,6 +1979,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; @@ -2053,6 +2081,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; @@ -2160,6 +2192,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))); @@ -2208,6 +2242,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))); @@ -2437,6 +2473,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); @@ -2490,8 +2530,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) { @@ -2524,6 +2617,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; @@ -2610,9 +2711,10 @@ 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; - sort_sccs(graph); if (compute_maxvar(graph) < 0) return -1; @@ -2658,10 +2760,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); @@ -2701,7 +2807,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; @@ -2748,10 +2855,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; } @@ -2797,6 +2904,8 @@ __isl_give isl_schedule *isl_union_set_compute_schedule( if (graph_alloc(ctx, &graph, graph.n, isl_union_map_n_map(validity) + isl_union_map_n_map(proximity)) < 0) goto error; + if (compute_max_row(&graph, domain) < 0) + goto error; graph.root = 1; graph.n = 0; if (isl_union_set_foreach_set(domain, &extract_node, &graph) < 0) @@ -2901,6 +3010,10 @@ static __isl_give isl_band_list *construct_band_list( * Because of the way the schedule is constructed, we know that * the position of the band inside the schedule of a node is the same * for all active nodes. + * + * The partial schedule for the band is created before the children + * are created to that construct_band_list can refer to the partial + * schedule of the parent. */ static __isl_give isl_band *construct_band(__isl_keep isl_schedule *schedule, __isl_keep isl_band *parent, @@ -2919,17 +3032,6 @@ static __isl_give isl_band *construct_band(__isl_keep isl_schedule *schedule, band->parent = parent; for (i = 0; i < schedule->n; ++i) - if (active[i] && schedule->node[i].n_band > band_nr + 1) - break; - - if (i < schedule->n) { - band->children = construct_band_list(schedule, band, - band_nr + 1, active, n_active); - if (!band->children) - goto error; - } - - for (i = 0; i < schedule->n; ++i) if (active[i]) break; @@ -2969,12 +3071,244 @@ static __isl_give isl_band *construct_band(__isl_keep isl_schedule *schedule, if (!band->pma) goto error; + for (i = 0; i < schedule->n; ++i) + if (active[i] && schedule->node[i].n_band > band_nr + 1) + break; + + if (i < schedule->n) { + band->children = construct_band_list(schedule, band, + band_nr + 1, active, n_active); + if (!band->children) + goto error; + } + return band; error: isl_band_free(band); return NULL; } +/* Internal data structure used inside cmp_band and pw_multi_aff_extract_int. + * + * r is set to a negative value if anything goes wrong. + * + * c1 stores the result of extract_int. + * c2 is a temporary value used inside cmp_band_in_ancestor. + * t is a temporary value used inside extract_int. + * + * first and equal are used inside extract_int. + * first is set if we are looking at the first isl_multi_aff inside + * the isl_union_pw_multi_aff. + * equal is set if all the isl_multi_affs have been equal so far. + */ +struct isl_cmp_band_data { + int r; + + int first; + int equal; + + isl_int t; + isl_int c1; + isl_int c2; +}; + +/* Check if "ma" assigns a constant value. + * Note that this function is only called on isl_multi_affs + * with a single output dimension. + * + * If "ma" assigns a constant value then we compare it to data->c1 + * or assign it to data->c1 if this is the first isl_multi_aff we consider. + * If "ma" does not assign a constant value or if it assigns a value + * that is different from data->c1, then we set data->equal to zero + * and terminate the check. + */ +static int multi_aff_extract_int(__isl_take isl_set *set, + __isl_take isl_multi_aff *ma, void *user) +{ + isl_aff *aff; + struct isl_cmp_band_data *data = user; + + aff = isl_multi_aff_get_aff(ma, 0); + data->r = isl_aff_is_cst(aff); + if (data->r >= 0 && data->r) { + isl_aff_get_constant(aff, &data->t); + if (data->first) { + isl_int_set(data->c1, data->t); + data->first = 0; + } else if (!isl_int_eq(data->c1, data->t)) + data->equal = 0; + } else if (data->r >= 0 && !data->r) + data->equal = 0; + + isl_aff_free(aff); + isl_set_free(set); + isl_multi_aff_free(ma); + + if (data->r < 0) + return -1; + if (!data->equal) + return -1; + return 0; +} + +/* This function is called for each isl_pw_multi_aff in + * the isl_union_pw_multi_aff checked by extract_int. + * Check all the isl_multi_affs inside "pma". + */ +static int pw_multi_aff_extract_int(__isl_take isl_pw_multi_aff *pma, + void *user) +{ + int r; + + r = isl_pw_multi_aff_foreach_piece(pma, &multi_aff_extract_int, user); + isl_pw_multi_aff_free(pma); + + return r; +} + +/* Check if "upma" assigns a single constant value to its domain. + * If so, return 1 and store the result in data->c1. + * If not, return 0. + * + * A negative return value from isl_union_pw_multi_aff_foreach_pw_multi_aff + * means that either an error occurred or that we have broken off the check + * because we already know the result is going to be negative. + * In the latter case, data->equal is set to zero. + */ +static int extract_int(__isl_keep isl_union_pw_multi_aff *upma, + struct isl_cmp_band_data *data) +{ + data->first = 1; + data->equal = 1; + + if (isl_union_pw_multi_aff_foreach_pw_multi_aff(upma, + &pw_multi_aff_extract_int, data) < 0) { + if (!data->equal) + return 0; + return -1; + } + + return !data->first && data->equal; +} + +/* Compare "b1" and "b2" based on the parent schedule of their ancestor + * "ancestor". + * + * If the parent of "ancestor" also has a single member, then we + * first try to compare the two band based on the partial schedule + * of this parent. + * + * Otherwise, or if the result is inconclusive, we look at the partial schedule + * of "ancestor" itself. + * In particular, we specialize the parent schedule based + * on the domains of the child schedules, check if both assign + * a single constant value and, if so, compare the two constant values. + * If the specialized parent schedules do not assign a constant value, + * then they cannot be used to order the two bands and so in this case + * we return 0. + */ +static int cmp_band_in_ancestor(__isl_keep isl_band *b1, + __isl_keep isl_band *b2, struct isl_cmp_band_data *data, + __isl_keep isl_band *ancestor) +{ + isl_union_pw_multi_aff *upma; + isl_union_set *domain; + int r; + + if (data->r < 0) + return 0; + + if (ancestor->parent && ancestor->parent->n == 1) { + r = cmp_band_in_ancestor(b1, b2, data, ancestor->parent); + if (data->r < 0) + return 0; + if (r) + return r; + } + + upma = isl_union_pw_multi_aff_copy(b1->pma); + domain = isl_union_pw_multi_aff_domain(upma); + upma = isl_union_pw_multi_aff_copy(ancestor->pma); + upma = isl_union_pw_multi_aff_intersect_domain(upma, domain); + r = extract_int(upma, data); + isl_union_pw_multi_aff_free(upma); + + if (r < 0) + data->r = -1; + if (r < 0 || !r) + return 0; + + isl_int_set(data->c2, data->c1); + + upma = isl_union_pw_multi_aff_copy(b2->pma); + domain = isl_union_pw_multi_aff_domain(upma); + upma = isl_union_pw_multi_aff_copy(ancestor->pma); + upma = isl_union_pw_multi_aff_intersect_domain(upma, domain); + r = extract_int(upma, data); + isl_union_pw_multi_aff_free(upma); + + if (r < 0) + data->r = -1; + if (r < 0 || !r) + return 0; + + return isl_int_cmp(data->c2, data->c1); +} + +/* Compare "a" and "b" based on the parent schedule of their parent. + */ +static int cmp_band(const void *a, const void *b, void *user) +{ + isl_band *b1 = *(isl_band * const *) a; + isl_band *b2 = *(isl_band * const *) b; + struct isl_cmp_band_data *data = user; + + return cmp_band_in_ancestor(b1, b2, data, b1->parent); +} + +/* Sort the elements in "list" based on the partial schedules of its parent + * (and ancestors). In particular if the parent assigns constant values + * to the domains of the bands in "list", then the elements are sorted + * according to that order. + * This order should be a more "natural" order for the user, but otherwise + * shouldn't have any effect. + * If we would be constructing an isl_band forest directly in + * isl_union_set_compute_schedule then there wouldn't be any need + * for a reordering, since the children would be added to the list + * in their natural order automatically. + * + * If there is only one element in the list, then there is no need to sort + * anything. + * If partial schedule of the parent has more than one member, then it's + * defnitely not assigning constant values to the different children in + * the list and so we wouldn't be able to use it to sort the list. + */ +static __isl_give isl_band_list *sort_band_list(__isl_take isl_band_list *list, + __isl_keep isl_band *parent) +{ + struct isl_cmp_band_data data; + + if (!list) + return NULL; + if (list->n <= 1) + return list; + if (parent->n != 1) + return list; + + data.r = 0; + isl_int_init(data.c1); + isl_int_init(data.c2); + isl_int_init(data.t); + isl_sort(list->p, list->n, sizeof(list->p[0]), &cmp_band, &data); + if (data.r < 0) + list = isl_band_list_free(list); + isl_int_clear(data.c1); + isl_int_clear(data.c2); + isl_int_clear(data.t); + + return list; +} + /* Construct a list of bands that start at the same position (with * sequence number band_nr) in the schedules of the nodes that * were active in the parent band. @@ -3059,6 +3393,8 @@ static __isl_give isl_band_list *construct_band_list( free(active); + list = sort_band_list(list, parent); + return list; }