X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=isl_schedule.c;h=9760c626b78d61a5e16e3b78c2528b31dfe754e2;hb=de51a9bc4da5dd3f1f9f57c2362da6f9752c44e0;hp=7837295306418228163b0b6598f3a1c7e3566e7e;hpb=b36d4b0b4b4369960f64780aea0ba335241e9519;p=platform%2Fupstream%2Fisl.git diff --git a/isl_schedule.c b/isl_schedule.c index 7837295..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, @@ -11,6 +11,7 @@ #include #include #include +#include #include #include #include @@ -20,11 +21,12 @@ #include #include #include -#include +#include #include #include #include #include +#include /* * The scheduling algorithm implemented in this file was inspired by @@ -61,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; @@ -82,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) @@ -126,6 +118,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 }; @@ -141,6 +134,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 @@ -171,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; @@ -184,6 +174,7 @@ struct isl_sched_graph { struct isl_sched_node *node; int n; int maxvar; + int max_row; int n_row; int *sorted; @@ -207,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. @@ -367,10 +354,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; @@ -385,9 +372,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); @@ -405,10 +392,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; @@ -436,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) @@ -477,13 +462,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) @@ -508,11 +529,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++; @@ -588,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]); } -/* 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; } @@ -681,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) @@ -705,9 +694,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, @@ -805,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); @@ -821,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 @@ -862,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); @@ -891,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 @@ -944,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); @@ -964,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 @@ -1023,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); @@ -1059,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) @@ -1507,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]) && @@ -1563,58 +1577,65 @@ error: return -1; } -/* Convert node->sched into a map and return this map. - * We simply add equality constraints that express each output variable - * as the affine combination of parameters and input variables specified - * by the schedule matrix. - * - * The result is cached in node->sched_map, which needs to be released - * whenever node->sched is updated. +/* Convert node->sched into a multi_aff and return this multi_aff. */ -static __isl_give isl_map *node_extract_schedule(struct isl_sched_node *node) +static __isl_give isl_multi_aff *node_extract_schedule_multi_aff( + struct isl_sched_node *node) { int i, j; - isl_space *dim; + isl_space *space; isl_local_space *ls; - isl_basic_map *bmap; - isl_constraint *c; + isl_aff *aff; + isl_multi_aff *ma; int nrow, ncol; isl_int v; - if (node->sched_map) - return isl_map_copy(node->sched_map); - nrow = isl_mat_rows(node->sched); ncol = isl_mat_cols(node->sched) - 1; - dim = isl_space_from_domain(isl_space_copy(node->dim)); - dim = isl_space_add_dims(dim, isl_dim_out, nrow); - bmap = isl_basic_map_universe(isl_space_copy(dim)); - ls = isl_local_space_from_space(dim); + space = isl_space_from_domain(isl_space_copy(node->dim)); + space = isl_space_add_dims(space, isl_dim_out, nrow); + ma = isl_multi_aff_zero(space); + ls = isl_local_space_from_space(isl_space_copy(node->dim)); isl_int_init(v); for (i = 0; i < nrow; ++i) { - c = isl_equality_alloc(isl_local_space_copy(ls)); - isl_constraint_set_coefficient_si(c, isl_dim_out, i, -1); + aff = isl_aff_zero_on_domain(isl_local_space_copy(ls)); isl_mat_get_element(node->sched, i, 0, &v); - isl_constraint_set_constant(c, v); + aff = isl_aff_set_constant(aff, v); for (j = 0; j < node->nparam; ++j) { isl_mat_get_element(node->sched, i, 1 + j, &v); - isl_constraint_set_coefficient(c, isl_dim_param, j, v); + aff = isl_aff_set_coefficient(aff, isl_dim_param, j, v); } for (j = 0; j < node->nvar; ++j) { isl_mat_get_element(node->sched, i, 1 + node->nparam + j, &v); - isl_constraint_set_coefficient(c, isl_dim_in, j, v); + aff = isl_aff_set_coefficient(aff, isl_dim_in, j, v); } - bmap = isl_basic_map_add_constraint(bmap, c); + ma = isl_multi_aff_set_aff(ma, i, aff); } isl_int_clear(v); isl_local_space_free(ls); - node->sched_map = isl_map_from_basic_map(bmap); + return ma; +} + +/* Convert node->sched into a map and return this map. + * + * The result is cached in node->sched_map, which needs to be released + * whenever node->sched is updated. + */ +static __isl_give isl_map *node_extract_schedule(struct isl_sched_node *node) +{ + if (!node->sched_map) { + isl_multi_aff *ma; + + ma = node_extract_schedule_multi_aff(node); + node->sched_map = isl_map_from_multi_aff(ma); + } + return isl_map_copy(node->sched_map); } @@ -1680,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); @@ -1736,10 +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(&graph->node[i]); sched->node[i].band_end = band_end; sched->node[i].band_id = band_id; sched->node[i].zero = zero; @@ -1809,7 +1842,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) { @@ -1841,7 +1874,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; @@ -1876,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; @@ -1943,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; @@ -2044,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; @@ -2151,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))); @@ -2199,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))); @@ -2428,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); @@ -2481,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) { @@ -2509,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; @@ -2601,9 +2710,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; @@ -2649,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,8 +2804,10 @@ static int compute_component_schedule(isl_ctx *ctx, int n_total_row, orig_total_row; int n_band, orig_band; - if (ctx->opt->schedule_fuse == ISL_SCHEDULE_FUSE_MIN) - split_on_scc(graph); + if (ctx->opt->schedule_fuse == ISL_SCHEDULE_FUSE_MIN || + ctx->opt->schedule_separate_components) + if (split_on_scc(ctx, graph) < 0) + return -1; n_total_row = 0; orig_total_row = graph->n_total_row; @@ -2738,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; } @@ -2787,6 +2903,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) @@ -2836,7 +2954,7 @@ void *isl_schedule_free(__isl_take isl_schedule *sched) return NULL; for (i = 0; i < sched->n; ++i) { - isl_map_free(sched->node[i].sched); + isl_multi_aff_free(sched->node[i].sched); free(sched->node[i].band_end); free(sched->node[i].band_id); free(sched->node[i].zero); @@ -2852,6 +2970,84 @@ 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. 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) { int i; @@ -2860,10 +3056,18 @@ __isl_give isl_union_map *isl_schedule_get_map(__isl_keep isl_schedule *sched) if (!sched) return NULL; + 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) - umap = isl_union_map_add_map(umap, - isl_map_copy(sched->node[i].sched)); + for (i = 0; i < sched->n; ++i) { + isl_multi_aff *ma; + + ma = isl_multi_aff_copy(sched->node[i].sched); + umap = isl_union_map_add_map(umap, isl_map_from_multi_aff(ma)); + } return umap; } @@ -2890,11 +3094,10 @@ static __isl_give isl_band *construct_band(__isl_keep isl_schedule *schedule, isl_band *band; unsigned start, end; - band = isl_calloc_type(ctx, isl_band); + band = isl_band_alloc(ctx); if (!band) return NULL; - band->ref = 1; band->schedule = schedule; band->parent = parent; @@ -2929,22 +3132,24 @@ static __isl_give isl_band *construct_band(__isl_keep isl_schedule *schedule, for (j = 0; j < band->n; ++j) band->zero[j] = schedule->node[i].zero[start + j]; - band->map = isl_union_map_empty(isl_space_copy(schedule->dim)); + band->pma = isl_union_pw_multi_aff_empty(isl_space_copy(schedule->dim)); for (i = 0; i < schedule->n; ++i) { - isl_map *map; + isl_multi_aff *ma; + isl_pw_multi_aff *pma; unsigned n_out; if (!active[i]) continue; - map = isl_map_copy(schedule->node[i].sched); - n_out = isl_map_dim(map, isl_dim_out); - map = isl_map_project_out(map, isl_dim_out, end, n_out - end); - map = isl_map_project_out(map, isl_dim_out, 0, start); - band->map = isl_union_map_union(band->map, - isl_union_map_from_map(map)); + ma = isl_multi_aff_copy(schedule->node[i].sched); + n_out = isl_multi_aff_dim(ma, isl_dim_out); + ma = isl_multi_aff_drop_dims(ma, isl_dim_out, end, n_out - end); + ma = isl_multi_aff_drop_dims(ma, isl_dim_out, 0, start); + pma = isl_pw_multi_aff_from_multi_aff(ma); + band->pma = isl_union_pw_multi_aff_add_pw_multi_aff(band->pma, + pma); } - if (!band->map) + if (!band->pma) goto error; return band; @@ -3077,6 +3282,24 @@ __isl_give isl_band_list *isl_schedule_get_band_forest( return isl_band_list_dup(schedule->band_forest); } +/* Call "fn" on each band in the schedule in depth-first post-order. + */ +int isl_schedule_foreach_band(__isl_keep isl_schedule *sched, + int (*fn)(__isl_keep isl_band *band, void *user), void *user) +{ + int r; + isl_band_list *forest; + + if (!sched) + return -1; + + forest = isl_schedule_get_band_forest(sched); + r = isl_band_list_foreach_band(forest, fn, user); + isl_band_list_free(forest); + + return r; +} + static __isl_give isl_printer *print_band_list(__isl_take isl_printer *p, __isl_keep isl_band_list *list); @@ -3086,7 +3309,7 @@ static __isl_give isl_printer *print_band(__isl_take isl_printer *p, isl_band_list *children; p = isl_printer_start_line(p); - p = isl_printer_print_union_map(p, band->map); + p = isl_printer_print_union_pw_multi_aff(p, band->pma); p = isl_printer_end_line(p); if (!isl_band_has_children(band))