X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;ds=sidebyside;f=isl_schedule.c;h=add0fa03e3fdac35ca1667663eb2aa3ef6ff25a7;hb=67e1125d372e65eb6f317c195bc83fda55872663;hp=fae08f45a16366924c35b5950fe6daea5dcce76b;hpb=747237f4a946ad88d45822eb281dc70665b81a76;p=platform%2Fupstream%2Fisl.git diff --git a/isl_schedule.c b/isl_schedule.c index fae08f4..add0fa0 100644 --- a/isl_schedule.c +++ b/isl_schedule.c @@ -11,6 +11,7 @@ #include #include #include +#include #include #include #include @@ -124,6 +125,13 @@ struct isl_sched_edge { int end; }; +enum isl_edge_type { + isl_edge_validity = 0, + isl_edge_first = isl_edge_validity, + isl_edge_proximity, + isl_edge_last = isl_edge_proximity +}; + /* Internal information about the dependence graph used during * the construction of the schedule. * @@ -135,6 +143,7 @@ struct isl_sched_edge { * 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 @@ -148,10 +157,13 @@ struct isl_sched_edge { * * n_edge is the number of edges * edge is the list of edges + * max_edge contains the maximal number of edges of each type; + * in particular, it contains the number of edges in the inital graph. * edge_table contains pointers into the edge array, hashed on the source - * and sink spaces; the table only contains edges that represent - * validity constraints (and that may or may not also represent proximity - * constraints) + * and sink spaces; there is one such table for each type; + * a given edge may be referenced from more than one table + * if the corresponding relation appears in more than of the + * sets of dependences * * node_table contains pointers into the node array, hashed on the space * @@ -175,6 +187,7 @@ struct isl_sched_graph { struct isl_sched_node *node; int n; int maxvar; + int max_row; int n_row; int *sorted; @@ -187,7 +200,8 @@ struct isl_sched_graph { struct isl_sched_edge *edge; int n_edge; - struct isl_hash_table *edge_table; + int max_edge[isl_edge_last + 1]; + struct isl_hash_table *edge_table[isl_edge_last + 1]; struct isl_hash_table *node_table; struct isl_region *region; @@ -254,60 +268,95 @@ static int edge_has_src_and_dst(const void *entry, const void *val) return edge->src == temp->src && edge->dst == temp->dst; } -/* Initialize edge_table based on the list of edges. - * Only edges with validity set are added to the table. +/* Add the given edge to graph->edge_table[type]. */ -static int graph_init_edge_table(isl_ctx *ctx, struct isl_sched_graph *graph) +static int graph_edge_table_add(isl_ctx *ctx, struct isl_sched_graph *graph, + enum isl_edge_type type, struct isl_sched_edge *edge) { - int i; + struct isl_hash_table_entry *entry; + uint32_t hash; - graph->edge_table = isl_hash_table_alloc(ctx, graph->n_edge); - if (!graph->edge_table) + hash = isl_hash_init(); + hash = isl_hash_builtin(hash, edge->src); + hash = isl_hash_builtin(hash, edge->dst); + entry = isl_hash_table_find(ctx, graph->edge_table[type], hash, + &edge_has_src_and_dst, edge, 1); + if (!entry) return -1; + entry->data = edge; - for (i = 0; i < graph->n_edge; ++i) { - struct isl_hash_table_entry *entry; - uint32_t hash; + return 0; +} - if (!graph->edge[i].validity) - continue; +/* Allocate the edge_tables based on the maximal number of edges of + * each type. + */ +static int graph_init_edge_tables(isl_ctx *ctx, struct isl_sched_graph *graph) +{ + int i; - hash = isl_hash_init(); - hash = isl_hash_builtin(hash, graph->edge[i].src); - hash = isl_hash_builtin(hash, graph->edge[i].dst); - entry = isl_hash_table_find(ctx, graph->edge_table, hash, - &edge_has_src_and_dst, - &graph->edge[i], 1); - if (!entry) + for (i = 0; i <= isl_edge_last; ++i) { + graph->edge_table[i] = isl_hash_table_alloc(ctx, + graph->max_edge[i]); + if (!graph->edge_table[i]) return -1; - entry->data = &graph->edge[i]; } return 0; } -/* Check whether the dependence graph has a (validity) edge - * between the given two nodes. +/* If graph->edge_table[type] contains an edge from the given source + * to the given destination, then return the hash table entry of this edge. + * Otherwise, return NULL. */ -static int graph_has_edge(struct isl_sched_graph *graph, +static struct isl_hash_table_entry *graph_find_edge_entry( + struct isl_sched_graph *graph, + enum isl_edge_type type, struct isl_sched_node *src, struct isl_sched_node *dst) { isl_ctx *ctx = isl_space_get_ctx(src->dim); - struct isl_hash_table_entry *entry; uint32_t hash; struct isl_sched_edge temp = { .src = src, .dst = dst }; - struct isl_sched_edge *edge; - int empty; hash = isl_hash_init(); hash = isl_hash_builtin(hash, temp.src); hash = isl_hash_builtin(hash, temp.dst); - entry = isl_hash_table_find(ctx, graph->edge_table, hash, + return isl_hash_table_find(ctx, graph->edge_table[type], hash, &edge_has_src_and_dst, &temp, 0); +} + + +/* If graph->edge_table[type] contains an edge from the given source + * to the given destination, then return this edge. + * Otherwise, return NULL. + */ +static struct isl_sched_edge *graph_find_edge(struct isl_sched_graph *graph, + enum isl_edge_type type, + struct isl_sched_node *src, struct isl_sched_node *dst) +{ + struct isl_hash_table_entry *entry; + + entry = graph_find_edge_entry(graph, type, src, dst); if (!entry) + return NULL; + + return entry->data; +} + +/* Check whether the dependence graph has an edge of the give type + * between the given two nodes. + */ +static int graph_has_edge(struct isl_sched_graph *graph, + enum isl_edge_type type, + struct isl_sched_node *src, struct isl_sched_node *dst) +{ + struct isl_sched_edge *edge; + int empty; + + edge = graph_find_edge(graph, type, src, dst); + if (!edge) return 0; - edge = entry->data; empty = isl_map_plain_is_empty(edge->map); if (empty < 0) return -1; @@ -315,6 +364,72 @@ static int graph_has_edge(struct isl_sched_graph *graph, return !empty; } +/* If there is an edge from the given source to the given destination + * of any type then return this edge. + * Otherwise, return NULL. + */ +static struct isl_sched_edge *graph_find_any_edge(struct isl_sched_graph *graph, + struct isl_sched_node *src, struct isl_sched_node *dst) +{ + enum isl_edge_type i; + struct isl_sched_edge *edge; + + for (i = isl_edge_first; i <= isl_edge_last; ++i) { + edge = graph_find_edge(graph, i, src, dst); + if (edge) + return edge; + } + + return NULL; +} + +/* Remove the given edge from all the edge_tables that refer to it. + */ +static void graph_remove_edge(struct isl_sched_graph *graph, + struct isl_sched_edge *edge) +{ + isl_ctx *ctx = isl_map_get_ctx(edge->map); + enum isl_edge_type 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); + if (!entry) + continue; + if (entry->data != edge) + continue; + isl_hash_table_remove(ctx, graph->edge_table[i], entry); + } +} + +/* Check whether the dependence graph has any edge + * between the given two nodes. + */ +static int graph_has_any_edge(struct isl_sched_graph *graph, + struct isl_sched_node *src, struct isl_sched_node *dst) +{ + enum isl_edge_type i; + int r; + + for (i = isl_edge_first; i <= isl_edge_last; ++i) { + r = graph_has_edge(graph, i, src, dst); + if (r < 0 || r) + return r; + } + + return r; +} + +/* Check whether the dependence graph has a validity edge + * between the given two nodes. + */ +static int graph_has_validity_edge(struct isl_sched_graph *graph, + struct isl_sched_node *src, struct isl_sched_node *dst) +{ + return graph_has_edge(graph, isl_edge_validity, src, dst); +} + static int graph_alloc(isl_ctx *ctx, struct isl_sched_graph *graph, int n_node, int n_edge) { @@ -367,11 +482,49 @@ static void graph_free(isl_ctx *ctx, struct isl_sched_graph *graph) free(graph->edge); free(graph->region); free(graph->stack); - isl_hash_table_free(ctx, graph->edge_table); + 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) @@ -396,11 +549,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++; @@ -410,21 +563,27 @@ static int extract_node(__isl_take isl_set *set, void *user) return 0; } -/* Add a new edge to the graph based on the given map. - * Edges are first extracted from the validity dependences, - * from which the edge_table is constructed. - * Afterwards, the proximity dependences are added. If a proximity - * dependence relation happens to be identical to one of the - * validity dependence relations added before, then we don't create - * a new edge, but instead mark the original edge as also representing - * a proximity dependence. +struct isl_extract_edge_data { + enum isl_edge_type type; + struct isl_sched_graph *graph; +}; + +/* Add a new edge to the graph based on the given map + * and add it to data->graph->edge_table[data->type]. + * If a dependence relation of a given type happens to be identical + * to one of the dependence relations of a type that was added before, + * then we don't create a new edge, but instead mark the original edge + * as also representing a dependence of the current type. */ static int extract_edge(__isl_take isl_map *map, void *user) { isl_ctx *ctx = isl_map_get_ctx(map); - struct isl_sched_graph *graph = user; + struct isl_extract_edge_data *data = user; + struct isl_sched_graph *graph = data->graph; struct isl_sched_node *src, *dst; isl_space *dim; + struct isl_sched_edge *edge; + int is_equal; dim = isl_space_domain(isl_map_get_space(map)); src = graph_find_node(ctx, graph, dim); @@ -441,54 +600,55 @@ static int extract_edge(__isl_take isl_map *map, void *user) graph->edge[graph->n_edge].src = src; graph->edge[graph->n_edge].dst = dst; graph->edge[graph->n_edge].map = map; - graph->edge[graph->n_edge].validity = !graph->edge_table; - graph->edge[graph->n_edge].proximity = !!graph->edge_table; + if (data->type == isl_edge_validity) { + graph->edge[graph->n_edge].validity = 1; + graph->edge[graph->n_edge].proximity = 0; + } + if (data->type == isl_edge_proximity) { + graph->edge[graph->n_edge].validity = 0; + graph->edge[graph->n_edge].proximity = 1; + } graph->n_edge++; - if (graph->edge_table) { - uint32_t hash; - struct isl_hash_table_entry *entry; - struct isl_sched_edge *edge; - int is_equal; - - hash = isl_hash_init(); - hash = isl_hash_builtin(hash, src); - hash = isl_hash_builtin(hash, dst); - entry = isl_hash_table_find(ctx, graph->edge_table, hash, - &edge_has_src_and_dst, - &graph->edge[graph->n_edge - 1], 0); - if (!entry) - return 0; - edge = entry->data; - is_equal = isl_map_plain_is_equal(map, edge->map); - if (is_equal < 0) - return -1; - if (!is_equal) - return 0; + edge = graph_find_any_edge(graph, src, dst); + if (!edge) + return graph_edge_table_add(ctx, graph, data->type, + &graph->edge[graph->n_edge - 1]); + is_equal = isl_map_plain_is_equal(map, edge->map); + if (is_equal < 0) + return -1; + if (!is_equal) + return graph_edge_table_add(ctx, graph, data->type, + &graph->edge[graph->n_edge - 1]); - graph->n_edge--; - edge->proximity = 1; - isl_map_free(map); - } + graph->n_edge--; + edge->validity |= graph->edge[graph->n_edge].validity; + edge->proximity |= graph->edge[graph->n_edge].proximity; + isl_map_free(map); - return 0; + 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. + * 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. */ static int node_follows(struct isl_sched_graph *graph, - struct isl_sched_node *dst, struct isl_sched_node *src) + struct isl_sched_node *dst, struct isl_sched_node *src, int weak) { - return graph_has_edge(graph, src, dst); + if (weak) + return graph_has_any_edge(graph, src, dst); + else + return graph_has_validity_edge(graph, src, dst); } /* Perform Tarjan's algorithm for computing the strongly connected components * in the dependence graph (only validity edges). - * If directed is not set, we consider the graph to be undirected and + * 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 directed) +static int detect_sccs_tarjan(struct isl_sched_graph *g, int i, int weak) { int j; @@ -508,18 +668,18 @@ static int detect_sccs_tarjan(struct isl_sched_graph *g, int i, int directed) g->node[j].index > g->node[i].min_index)) continue; - f = node_follows(g, &g->node[i], &g->node[j]); + f = node_follows(g, &g->node[i], &g->node[j], weak); if (f < 0) return -1; - if (!f && !directed) { - f = node_follows(g, &g->node[j], &g->node[i]); + if (!f && weak) { + f = node_follows(g, &g->node[j], &g->node[i], weak); if (f < 0) return -1; } if (!f) continue; if (g->node[j].index < 0) { - detect_sccs_tarjan(g, j, directed); + 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) @@ -539,7 +699,7 @@ static int detect_sccs_tarjan(struct isl_sched_graph *g, int i, int directed) return 0; } -static int detect_ccs(struct isl_sched_graph *graph, int directed) +static int detect_ccs(struct isl_sched_graph *graph, int weak) { int i; @@ -552,7 +712,7 @@ static int detect_ccs(struct isl_sched_graph *graph, int directed) for (i = graph->n - 1; i >= 0; --i) { if (graph->node[i].index >= 0) continue; - if (detect_sccs_tarjan(graph, i, directed) < 0) + if (detect_sccs_tarjan(graph, i, weak) < 0) return -1; } @@ -564,7 +724,7 @@ static int detect_ccs(struct isl_sched_graph *graph, int directed) */ static int detect_sccs(struct isl_sched_graph *graph) { - return detect_ccs(graph, 1); + return detect_ccs(graph, 0); } /* Apply Tarjan's algorithm to detect the (weakly) connected components @@ -572,7 +732,7 @@ static int detect_sccs(struct isl_sched_graph *graph) */ static int detect_wccs(struct isl_sched_graph *graph) { - return detect_ccs(graph, 0); + return detect_ccs(graph, 1); } static int cmp_scc(const void *a, const void *b, void *data) @@ -1042,7 +1202,8 @@ static int node_update_cmap(struct isl_sched_node *node) /* Count the number of equality and inequality constraints * that will be added for the given map. - * If once is set, then we count + * If carry is set, then we are counting the number of (validity) + * constraints that will be added in setup_carry_lp and we count * each edge exactly once. Otherwise, we count as follows * validity -> 1 (>= 0) * validity+proximity -> 2 (>= 0 and upper bound) @@ -1050,10 +1211,15 @@ static int node_update_cmap(struct isl_sched_node *node) */ static int count_map_constraints(struct isl_sched_graph *graph, struct isl_sched_edge *edge, __isl_take isl_map *map, - int *n_eq, int *n_ineq, int once) + int *n_eq, int *n_ineq, int carry) { isl_basic_set *coef; - int f = once ? 1 : edge->proximity ? 2 : 1; + int f = carry ? 1 : edge->proximity ? 2 : 1; + + if (carry && !edge->validity) { + isl_map_free(map); + return 0; + } if (edge->src == edge->dst) coef = intra_coefficients(graph, map); @@ -1070,14 +1236,13 @@ static int count_map_constraints(struct isl_sched_graph *graph, /* Count the number of equality and inequality constraints * that will be added to the main lp problem. - * If once is set, then we count - * each edge exactly once. Otherwise, we count as follows + * We count as follows * validity -> 1 (>= 0) * validity+proximity -> 2 (>= 0 and upper bound) * proximity -> 2 (lower and upper bound) */ static int count_constraints(struct isl_sched_graph *graph, - int *n_eq, int *n_ineq, int once) + int *n_eq, int *n_ineq) { int i; @@ -1087,7 +1252,7 @@ static int count_constraints(struct isl_sched_graph *graph, isl_map *map = isl_map_copy(edge->map); if (count_map_constraints(graph, edge, map, - n_eq, n_ineq, once) < 0) + n_eq, n_ineq, 0) < 0) return -1; } @@ -1194,7 +1359,7 @@ static int setup_lp(isl_ctx *ctx, struct isl_sched_graph *graph, total += 1 + 2 * (node->nparam + node->nvar); } - if (count_constraints(graph, &n_eq, &n_ineq, 0) < 0) + if (count_constraints(graph, &n_eq, &n_ineq) < 0) return -1; dim = isl_space_set_alloc(ctx, 0, total); @@ -1439,58 +1604,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); } @@ -1514,12 +1686,12 @@ static __isl_give isl_map *specialize(__isl_take isl_map *map, /* Update the dependence relations of all edges based on the current schedule. * If a dependence is carried completely by the current schedule, then - * it is removed and edge_table is updated accordingly. + * it is removed from the edge_tables. It is kept in the list of edges + * as otherwise all edge_tables would have to be recomputed. */ static int update_edges(isl_ctx *ctx, struct isl_sched_graph *graph) { int i; - int reset_table = 0; for (i = graph->n_edge - 1; i >= 0; --i) { struct isl_sched_edge *edge = &graph->edge[i]; @@ -1527,19 +1699,8 @@ static int update_edges(isl_ctx *ctx, struct isl_sched_graph *graph) if (!edge->map) return -1; - if (isl_map_plain_is_empty(edge->map)) { - reset_table = 1; - isl_map_free(edge->map); - if (i != graph->n_edge - 1) - graph->edge[i] = graph->edge[graph->n_edge - 1]; - graph->n_edge--; - } - } - - if (reset_table) { - isl_hash_table_free(ctx, graph->edge_table); - graph->edge_table = NULL; - return graph_init_edge_table(ctx, graph); + if (isl_map_plain_is_empty(edge->map)) + graph_remove_edge(graph, edge); } return 0; @@ -1551,7 +1712,7 @@ static void next_band(struct isl_sched_graph *graph) graph->n_band++; } -/* Topologically sort statements mapped to same schedule iteration +/* Topologically sort statements mapped to the same schedule iteration * and add a row to the schedule corresponding to this order. */ static int sort_statements(isl_ctx *ctx, struct isl_sched_graph *graph) @@ -1626,7 +1787,8 @@ static __isl_give isl_schedule *extract_schedule(struct isl_sched_graph *graph, 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].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; @@ -1687,17 +1849,22 @@ static int copy_nodes(struct isl_sched_graph *dst, struct isl_sched_graph *src, /* Copy non-empty edges that satisfy edge_pred from the src dependence graph * to the dst dependence graph. + * If the source or destination node of the edge is not in the destination + * graph, then it must be a backward proximity edge and it should simply + * be ignored. */ static int copy_edges(isl_ctx *ctx, struct isl_sched_graph *dst, struct isl_sched_graph *src, int (*edge_pred)(struct isl_sched_edge *edge, int data), int data) { int i; + enum isl_edge_type t; dst->n_edge = 0; for (i = 0; i < src->n_edge; ++i) { struct isl_sched_edge *edge = &src->edge[i]; isl_map *map; + struct isl_sched_node *dst_src, *dst_dst; if (!edge_pred(edge, data)) continue; @@ -1705,16 +1872,32 @@ static int copy_edges(isl_ctx *ctx, struct isl_sched_graph *dst, if (isl_map_plain_is_empty(edge->map)) continue; + dst_src = graph_find_node(ctx, dst, edge->src->dim); + dst_dst = graph_find_node(ctx, dst, edge->dst->dim); + if (!dst_src || !dst_dst) { + if (edge->validity) + isl_die(ctx, isl_error_internal, + "backward validity edge", return -1); + continue; + } + map = isl_map_copy(edge->map); - dst->edge[dst->n_edge].src = - graph_find_node(ctx, dst, edge->src->dim); - dst->edge[dst->n_edge].dst = - graph_find_node(ctx, dst, edge->dst->dim); + dst->edge[dst->n_edge].src = dst_src; + dst->edge[dst->n_edge].dst = dst_dst; dst->edge[dst->n_edge].map = map; dst->edge[dst->n_edge].validity = edge->validity; dst->edge[dst->n_edge].proximity = edge->proximity; dst->n_edge++; + + for (t = isl_edge_first; t <= isl_edge_last; ++t) { + if (edge != + graph_find_edge(src, t, edge->src, edge->dst)) + continue; + if (graph_edge_table_add(ctx, dst, t, + &dst->edge[dst->n_edge - 1]) < 0) + return -1; + } } return 0; @@ -1794,6 +1977,7 @@ static int compute_sub_schedule(isl_ctx *ctx, int data, int wcc) { struct isl_sched_graph split = { 0 }; + int t; if (graph_alloc(ctx, &split, n, n_edge) < 0) goto error; @@ -1801,9 +1985,11 @@ static int compute_sub_schedule(isl_ctx *ctx, goto error; if (graph_init_table(ctx, &split) < 0) goto error; - if (copy_edges(ctx, &split, graph, edge_pred, data) < 0) + for (t = 0; t <= isl_edge_last; ++t) + split.max_edge[t] = graph->max_edge[t]; + if (graph_init_edge_tables(ctx, &split) < 0) goto error; - if (graph_init_edge_table(ctx, &split) < 0) + if (copy_edges(ctx, &split, graph, edge_pred, data) < 0) goto error; split.n_row = graph->n_row; split.n_total_row = graph->n_total_row; @@ -2099,8 +2285,8 @@ static int add_inter_constraints(struct isl_sched_graph *graph, return 0; } -/* Add constraints to graph->lp that force all dependence - * to be respected and attempt to carry it. +/* Add constraints to graph->lp that force all validity dependences + * to be respected and attempt to carry them. */ static int add_all_constraints(struct isl_sched_graph *graph) { @@ -2110,6 +2296,10 @@ static int add_all_constraints(struct isl_sched_graph *graph) pos = 0; for (i = 0; i < graph->n_edge; ++i) { struct isl_sched_edge *edge= &graph->edge[i]; + + if (!edge->validity) + continue; + for (j = 0; j < edge->map->n; ++j) { isl_basic_map *bmap; isl_map *map; @@ -2132,14 +2322,10 @@ static int add_all_constraints(struct isl_sched_graph *graph) /* Count the number of equality and inequality constraints * that will be added to the carry_lp problem. - * If once is set, then we count - * each edge exactly once. Otherwise, we count as follows - * validity -> 1 (>= 0) - * validity+proximity -> 2 (>= 0 and upper bound) - * proximity -> 2 (lower and upper bound) + * We count each edge exactly once. */ static int count_all_constraints(struct isl_sched_graph *graph, - int *n_eq, int *n_ineq, int once) + int *n_eq, int *n_ineq) { int i, j; @@ -2154,7 +2340,7 @@ static int count_all_constraints(struct isl_sched_graph *graph, map = isl_map_from_basic_map(bmap); if (count_map_constraints(graph, edge, map, - n_eq, n_ineq, once) < 0) + n_eq, n_ineq, 1) < 0) return -1; } } @@ -2191,7 +2377,7 @@ static int count_all_constraints(struct isl_sched_graph *graph, * - positive and negative parts of c_i_n (if parametric) * - positive and negative parts of c_i_x * - * The constraints are those from the edges plus three equalities + * The constraints are those from the (validity) edges plus three equalities * to express the sums and n_edge inequalities to express e_i <= 1. */ static int setup_carry_lp(isl_ctx *ctx, struct isl_sched_graph *graph) @@ -2214,7 +2400,7 @@ static int setup_carry_lp(isl_ctx *ctx, struct isl_sched_graph *graph) total += 1 + 2 * (node->nparam + node->nvar); } - if (count_all_constraints(graph, &n_eq, &n_ineq, 1) < 0) + if (count_all_constraints(graph, &n_eq, &n_ineq) < 0) return -1; dim = isl_space_set_alloc(ctx, 0, total); @@ -2387,15 +2573,23 @@ static int carry_dependences(isl_ctx *ctx, struct isl_sched_graph *graph) return compute_next_band(ctx, graph); } -/* Are there any validity edges in the graph? +/* Are there any (non-empty) validity edges in the graph? */ static int has_validity_edges(struct isl_sched_graph *graph) { int i; - for (i = 0; i < graph->n_edge; ++i) + for (i = 0; i < graph->n_edge; ++i) { + int empty; + + empty = isl_map_plain_is_empty(graph->edge[i].map); + if (empty < 0) + return -1; + if (empty) + continue; if (graph->edge[i].validity) return 1; + } return 0; } @@ -2545,7 +2739,8 @@ 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) + if (ctx->opt->schedule_fuse == ISL_SCHEDULE_FUSE_MIN || + ctx->opt->schedule_separate_components) split_on_scc(graph); n_total_row = 0; @@ -2623,6 +2818,7 @@ __isl_give isl_schedule *isl_union_set_compute_schedule( isl_space *dim; struct isl_sched_graph graph = { 0 }; isl_schedule *sched; + struct isl_extract_edge_data data; domain = isl_union_set_align_params(domain, isl_union_map_get_space(validity)); @@ -2641,18 +2837,25 @@ __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) goto error; if (graph_init_table(ctx, &graph) < 0) goto error; - graph.n_edge = 0; - if (isl_union_map_foreach_map(validity, &extract_edge, &graph) < 0) + graph.max_edge[isl_edge_validity] = isl_union_map_n_map(validity); + graph.max_edge[isl_edge_proximity] = isl_union_map_n_map(proximity); + if (graph_init_edge_tables(ctx, &graph) < 0) goto error; - if (graph_init_edge_table(ctx, &graph) < 0) + graph.n_edge = 0; + data.graph = &graph; + data.type = isl_edge_validity; + if (isl_union_map_foreach_map(validity, &extract_edge, &data) < 0) goto error; - if (isl_union_map_foreach_map(proximity, &extract_edge, &graph) < 0) + data.type = isl_edge_proximity; + if (isl_union_map_foreach_map(proximity, &extract_edge, &data) < 0) goto error; if (compute_schedule(ctx, &graph) < 0) @@ -2685,7 +2888,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); @@ -2701,6 +2904,11 @@ isl_ctx *isl_schedule_get_ctx(__isl_keep isl_schedule *schedule) return schedule ? isl_space_get_ctx(schedule->dim) : NULL; } +/* 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. + */ __isl_give isl_union_map *isl_schedule_get_map(__isl_keep isl_schedule *sched) { int i; @@ -2709,10 +2917,16 @@ __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); + 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; } @@ -2739,11 +2953,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; @@ -2778,22 +2991,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; @@ -2926,6 +3141,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); @@ -2935,7 +3168,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))