X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=isl_schedule.c;h=9760c626b78d61a5e16e3b78c2528b31dfe754e2;hb=de51a9bc4da5dd3f1f9f57c2362da6f9752c44e0;hp=66c0ed527e80e16dd649d3279b40a6971cfbeecc;hpb=f600853f2f7dd332a98d1a4ca58d30567d36e04a;p=platform%2Fupstream%2Fisl.git diff --git a/isl_schedule.c b/isl_schedule.c index 66c0ed5..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, @@ -10,7 +10,8 @@ #include #include -#include +#include +#include #include #include #include @@ -20,7 +21,12 @@ #include #include #include -#include +#include +#include +#include +#include +#include +#include /* * The scheduling algorithm implemented in this file was inspired by @@ -29,32 +35,6 @@ */ -/* The schedule for an individual domain, plus information about the bands. - * In particular, we keep track of the number of bands and for each - * band, the starting position of the next band. The first band starts at - * position 0. - */ -struct isl_schedule_node { - isl_map *sched; - int n_band; - int *band_end; -}; - -/* Information about the computed schedule. - * n is the number of nodes/domains/statements. - * n_band is the maximal number of bands. - * n_total_row is the number of coordinates of the schedule. - * dim contains a description of the parameters. - */ -struct isl_schedule { - int n; - int n_band; - int n_total_row; - isl_dim *dim; - - struct isl_schedule_node node[1]; -}; - /* Internal information about a node that is used during the construction * of a schedule. * dim represents the space in which the domain lives @@ -75,15 +55,17 @@ struct isl_schedule { * * scc is the index of SCC (or WCC) this node belongs to * - * band contains the band index for each of the rows of the schedule - * - * 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. + * band contains the band index for each of the rows of the schedule. + * band_id is used to differentiate between separate bands at the same + * level within the same parent band, i.e., bands that are separated + * by the parent band or bands that are independent of each other. + * zero contains a boolean for each of the rows of the schedule, + * indicating whether the corresponding scheduling dimension results + * in zero dependence distances within its band and with respect + * to the proximity edges. */ struct isl_sched_node { - isl_dim *dim; + isl_space *dim; isl_mat *sched; isl_map *sched_map; int rank; @@ -95,19 +77,16 @@ struct isl_sched_node { int scc; int *band; - - /* scc detection */ - int index; - int min_index; - int on_stack; + int *band_id; + int *zero; }; static int node_has_dim(const void *entry, const void *val) { struct isl_sched_node *node = (struct isl_sched_node *)entry; - isl_dim *dim = (isl_dim *)val; + isl_space *dim = (isl_space *)val; - return isl_dim_equal(node->dim, dim); + return isl_space_is_equal(node->dim, dim); } /* An edge in the dependence graph. An edge may be used to @@ -137,6 +116,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. * @@ -148,6 +134,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 @@ -161,10 +148,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,11 +165,7 @@ struct isl_sched_edge { * 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; @@ -188,6 +174,7 @@ struct isl_sched_graph { struct isl_sched_node *node; int n; int maxvar; + int max_row; int n_row; int *sorted; @@ -200,7 +187,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; @@ -210,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. @@ -231,7 +215,7 @@ static int graph_init_table(isl_ctx *ctx, struct isl_sched_graph *graph) struct isl_hash_table_entry *entry; uint32_t hash; - hash = isl_dim_get_hash(graph->node[i].dim); + hash = isl_space_get_hash(graph->node[i].dim); entry = isl_hash_table_find(ctx, graph->node_table, hash, &node_has_dim, graph->node[i].dim, 1); @@ -247,12 +231,12 @@ static int graph_init_table(isl_ctx *ctx, struct isl_sched_graph *graph) * or NULL if there is no such node. */ static struct isl_sched_node *graph_find_node(isl_ctx *ctx, - struct isl_sched_graph *graph, __isl_keep isl_dim *dim) + struct isl_sched_graph *graph, __isl_keep isl_space *dim) { struct isl_hash_table_entry *entry; uint32_t hash; - hash = isl_dim_get_hash(dim); + hash = isl_space_get_hash(dim); entry = isl_hash_table_find(ctx, graph->node_table, hash, &node_has_dim, dim, 0); @@ -267,60 +251,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_dim_get_ctx(src->dim); - struct isl_hash_table_entry *entry; + isl_ctx *ctx = isl_space_get_ctx(src->dim); 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; @@ -328,6 +347,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) { @@ -338,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) @@ -363,12 +446,15 @@ static void graph_free(isl_ctx *ctx, struct isl_sched_graph *graph) isl_hmap_map_basic_set_free(ctx, graph->inter_hmap); for (i = 0; i < graph->n; ++i) { - isl_dim_free(graph->node[i].dim); + isl_space_free(graph->node[i].dim); isl_mat_free(graph->node[i].sched); isl_map_free(graph->node[i].sched_map); isl_mat_free(graph->node[i].cmap); - if (graph->root) + if (graph->root) { free(graph->node[i].band); + free(graph->node[i].band_id); + free(graph->node[i].zero); + } } free(graph->node); free(graph->sorted); @@ -376,28 +462,65 @@ 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); - 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) { int nvar, nparam; isl_ctx *ctx; - isl_dim *dim; + isl_space *dim; isl_mat *sched; struct isl_sched_graph *graph = user; - int *band; + int *band, *band_id, *zero; ctx = isl_set_get_ctx(set); - dim = isl_set_get_dim(set); + dim = isl_set_get_space(set); isl_set_free(set); - nvar = isl_dim_size(dim, isl_dim_set); - nparam = isl_dim_size(dim, isl_dim_param); + nvar = isl_space_dim(dim, isl_dim_set); + nparam = isl_space_dim(dim, isl_dim_param); if (!ctx->opt->schedule_parametric) nparam = 0; sched = isl_mat_alloc(ctx, 0, 1 + nparam + nvar); @@ -406,38 +529,48 @@ 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->max_row); + graph->node[graph->n].band_id = band_id; + zero = isl_calloc_array(ctx, int, graph->max_row); + graph->node[graph->n].zero = zero; graph->n++; - if (!sched || !band) + if (!sched || !band || !band_id || !zero) return -1; 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_dim *dim; + isl_space *dim; + struct isl_sched_edge *edge; + int is_equal; - dim = isl_dim_domain(isl_map_get_dim(map)); + dim = isl_space_domain(isl_map_get_space(map)); src = graph_find_node(ctx, graph, dim); - isl_dim_free(dim); - dim = isl_dim_range(isl_map_get_dim(map)); + isl_space_free(dim); + dim = isl_space_range(isl_map_get_space(map)); dst = graph_find_node(ctx, graph, dim); - isl_dim_free(dim); + isl_space_free(dim); if (!src || !dst) { isl_map_free(map); @@ -447,138 +580,107 @@ 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. +/* 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) +static int node_follows_weak(int i, int j, void *user) { - return graph_has_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 - * in the dependence graph (only validity edges). - * If directed is not set, we consider the graph to be undirected and - * we effectively compute the (weakly) connected components. +/* Check whether there is a validity dependence from node[j] to node[i], + * forcing node[i] to follow node[j]. */ -static int detect_sccs_tarjan(struct isl_sched_graph *g, int i, int directed) +static int node_follows_strong(int i, int j, void *user) { - 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; - - for (j = g->n - 1; j >= 0; --j) { - int f; - - 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]); - if (f < 0) - return -1; - if (!f && !directed) { - f = node_follows(g, &g->node[j], &g->node[i]); - if (f < 0) - return -1; - } - if (!f) - continue; - if (g->node[j].index < 0) { - detect_sccs_tarjan(g, j, directed); - 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; - } - - 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++; + struct isl_sched_graph *graph = user; - return 0; + return graph_has_validity_edge(graph, &graph->node[j], &graph->node[i]); } -static int detect_ccs(struct isl_sched_graph *graph, int directed) +/* 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_ccs(isl_ctx *ctx, struct isl_sched_graph *graph, int weak) { - int i; + int i, n; + struct isl_tarjan_graph *g = NULL; - graph->index = 0; - graph->sp = 0; - graph->scc = 0; - for (i = graph->n - 1; i >= 0; --i) - graph->node[i].index = -1; + g = isl_tarjan_graph_init(ctx, graph->n, + weak ? &node_follows_weak : &node_follows_strong, graph); + if (!g) + return -1; - for (i = graph->n - 1; i >= 0; --i) { - if (graph->node[i].index >= 0) - continue; - if (detect_sccs_tarjan(graph, i, directed) < 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; + } + ++i; + graph->scc++; } + isl_tarjan_graph_free(g); + return 0; } /* 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, 1); + 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, 0); + return detect_ccs(ctx, graph, 1); } static int cmp_scc(const void *a, const void *b, void *data) @@ -592,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, @@ -681,33 +783,38 @@ static int add_intra_validity_constraints(struct isl_sched_graph *graph, unsigned total; isl_map *map = isl_map_copy(edge->map); isl_ctx *ctx = isl_map_get_ctx(map); - isl_dim *dim; + isl_space *dim; isl_dim_map *dim_map; isl_basic_set *coef; struct isl_sched_node *node = edge->src; coef = intra_coefficients(graph, map); - dim = isl_dim_domain(isl_dim_unwrap(isl_basic_set_get_dim(coef))); + dim = isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef))); coef = isl_basic_set_transform_dims(coef, isl_dim_set, - isl_dim_size(dim, isl_dim_set), isl_mat_copy(node->cmap)); + 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); isl_dim_map_range(dim_map, node->start + 2 * node->nparam + 1, 2, - isl_dim_size(dim, isl_dim_set), 1, + isl_space_dim(dim, isl_dim_set), 1, node->nvar, -1); isl_dim_map_range(dim_map, node->start + 2 * node->nparam + 2, 2, - isl_dim_size(dim, isl_dim_set), 1, + isl_space_dim(dim, isl_dim_set), 1, node->nvar, 1); graph->lp = isl_basic_set_extend_constraints(graph->lp, coef->n_eq, coef->n_ineq); graph->lp = isl_basic_set_add_constraints_dim_map(graph->lp, coef, dim_map); - isl_dim_free(dim); + isl_space_free(dim); return 0; +error: + isl_space_free(dim); + return -1; } /* Add constraints to graph->lp that force validity for the given @@ -734,7 +841,7 @@ static int add_inter_validity_constraints(struct isl_sched_graph *graph, unsigned total; isl_map *map = isl_map_copy(edge->map); isl_ctx *ctx = isl_map_get_ctx(map); - isl_dim *dim; + isl_space *dim; isl_dim_map *dim_map; isl_basic_set *coef; struct isl_sched_node *src = edge->src; @@ -742,13 +849,15 @@ static int add_inter_validity_constraints(struct isl_sched_graph *graph, coef = inter_coefficients(graph, map); - dim = isl_dim_domain(isl_dim_unwrap(isl_basic_set_get_dim(coef))); + dim = isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef))); coef = isl_basic_set_transform_dims(coef, isl_dim_set, - isl_dim_size(dim, isl_dim_set), isl_mat_copy(src->cmap)); + isl_space_dim(dim, isl_dim_set), isl_mat_copy(src->cmap)); coef = isl_basic_set_transform_dims(coef, isl_dim_set, - isl_dim_size(dim, isl_dim_set) + src->nvar, + 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); @@ -757,20 +866,20 @@ static int add_inter_validity_constraints(struct isl_sched_graph *graph, isl_dim_map_range(dim_map, dst->start + 1, 2, 1, 1, dst->nparam, -1); isl_dim_map_range(dim_map, dst->start + 2, 2, 1, 1, dst->nparam, 1); isl_dim_map_range(dim_map, dst->start + 2 * dst->nparam + 1, 2, - isl_dim_size(dim, isl_dim_set) + src->nvar, 1, + isl_space_dim(dim, isl_dim_set) + src->nvar, 1, dst->nvar, -1); isl_dim_map_range(dim_map, dst->start + 2 * dst->nparam + 2, 2, - isl_dim_size(dim, isl_dim_set) + src->nvar, 1, + isl_space_dim(dim, isl_dim_set) + src->nvar, 1, dst->nvar, 1); isl_dim_map_range(dim_map, src->start, 0, 0, 0, 1, -1); isl_dim_map_range(dim_map, src->start + 1, 2, 1, 1, src->nparam, 1); isl_dim_map_range(dim_map, src->start + 2, 2, 1, 1, src->nparam, -1); isl_dim_map_range(dim_map, src->start + 2 * src->nparam + 1, 2, - isl_dim_size(dim, isl_dim_set), 1, + isl_space_dim(dim, isl_dim_set), 1, src->nvar, 1); isl_dim_map_range(dim_map, src->start + 2 * src->nparam + 2, 2, - isl_dim_size(dim, isl_dim_set), 1, + isl_space_dim(dim, isl_dim_set), 1, src->nvar, -1); edge->start = graph->lp->n_ineq; @@ -778,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); - isl_dim_free(dim); + 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 @@ -820,37 +934,42 @@ static int add_intra_proximity_constraints(struct isl_sched_graph *graph, unsigned nparam; isl_map *map = isl_map_copy(edge->map); isl_ctx *ctx = isl_map_get_ctx(map); - isl_dim *dim; + isl_space *dim; isl_dim_map *dim_map; isl_basic_set *coef; struct isl_sched_node *node = edge->src; coef = intra_coefficients(graph, map); - dim = isl_dim_domain(isl_dim_unwrap(isl_basic_set_get_dim(coef))); + dim = isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef))); coef = isl_basic_set_transform_dims(coef, isl_dim_set, - isl_dim_size(dim, isl_dim_set), isl_mat_copy(node->cmap)); + isl_space_dim(dim, isl_dim_set), isl_mat_copy(node->cmap)); + if (!coef) + goto error; - nparam = isl_dim_size(node->dim, isl_dim_param); + nparam = isl_space_dim(node->dim, isl_dim_param); total = isl_basic_set_total_dim(graph->lp); dim_map = isl_dim_map_alloc(ctx, total); isl_dim_map_range(dim_map, 1, 0, 0, 0, 1, 1); isl_dim_map_range(dim_map, 4, 2, 1, 1, nparam, -1); isl_dim_map_range(dim_map, 5, 2, 1, 1, nparam, 1); isl_dim_map_range(dim_map, node->start + 2 * node->nparam + 1, 2, - isl_dim_size(dim, isl_dim_set), 1, + isl_space_dim(dim, isl_dim_set), 1, node->nvar, s); isl_dim_map_range(dim_map, node->start + 2 * node->nparam + 2, 2, - isl_dim_size(dim, isl_dim_set), 1, + isl_space_dim(dim, isl_dim_set), 1, node->nvar, -s); graph->lp = isl_basic_set_extend_constraints(graph->lp, coef->n_eq, coef->n_ineq); graph->lp = isl_basic_set_add_constraints_dim_map(graph->lp, coef, dim_map); - isl_dim_free(dim); + 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 @@ -895,7 +1014,7 @@ static int add_inter_proximity_constraints(struct isl_sched_graph *graph, unsigned nparam; isl_map *map = isl_map_copy(edge->map); isl_ctx *ctx = isl_map_get_ctx(map); - isl_dim *dim; + isl_space *dim; isl_dim_map *dim_map; isl_basic_set *coef; struct isl_sched_node *src = edge->src; @@ -903,15 +1022,17 @@ static int add_inter_proximity_constraints(struct isl_sched_graph *graph, coef = inter_coefficients(graph, map); - dim = isl_dim_domain(isl_dim_unwrap(isl_basic_set_get_dim(coef))); + dim = isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef))); coef = isl_basic_set_transform_dims(coef, isl_dim_set, - isl_dim_size(dim, isl_dim_set), isl_mat_copy(src->cmap)); + isl_space_dim(dim, isl_dim_set), isl_mat_copy(src->cmap)); coef = isl_basic_set_transform_dims(coef, isl_dim_set, - isl_dim_size(dim, isl_dim_set) + src->nvar, + isl_space_dim(dim, isl_dim_set) + src->nvar, isl_mat_copy(dst->cmap)); + if (!coef) + goto error; - nparam = isl_dim_size(src->dim, isl_dim_param); + nparam = isl_space_dim(src->dim, isl_dim_param); total = isl_basic_set_total_dim(graph->lp); dim_map = isl_dim_map_alloc(ctx, total); @@ -923,29 +1044,32 @@ static int add_inter_proximity_constraints(struct isl_sched_graph *graph, isl_dim_map_range(dim_map, dst->start + 1, 2, 1, 1, dst->nparam, s); isl_dim_map_range(dim_map, dst->start + 2, 2, 1, 1, dst->nparam, -s); isl_dim_map_range(dim_map, dst->start + 2 * dst->nparam + 1, 2, - isl_dim_size(dim, isl_dim_set) + src->nvar, 1, + isl_space_dim(dim, isl_dim_set) + src->nvar, 1, dst->nvar, s); isl_dim_map_range(dim_map, dst->start + 2 * dst->nparam + 2, 2, - isl_dim_size(dim, isl_dim_set) + src->nvar, 1, + isl_space_dim(dim, isl_dim_set) + src->nvar, 1, dst->nvar, -s); isl_dim_map_range(dim_map, src->start, 0, 0, 0, 1, s); isl_dim_map_range(dim_map, src->start + 1, 2, 1, 1, src->nparam, -s); isl_dim_map_range(dim_map, src->start + 2, 2, 1, 1, src->nparam, s); isl_dim_map_range(dim_map, src->start + 2 * src->nparam + 1, 2, - isl_dim_size(dim, isl_dim_set), 1, + isl_space_dim(dim, isl_dim_set), 1, src->nvar, -s); isl_dim_map_range(dim_map, src->start + 2 * src->nparam + 2, 2, - isl_dim_size(dim, isl_dim_set), 1, + isl_space_dim(dim, isl_dim_set), 1, src->nvar, s); graph->lp = isl_basic_set_extend_constraints(graph->lp, coef->n_eq, coef->n_ineq); graph->lp = isl_basic_set_add_constraints_dim_map(graph->lp, coef, dim_map); - isl_dim_free(dim); + isl_space_free(dim); return 0; +error: + isl_space_free(dim); + return -1; } static int add_all_validity_constraints(struct isl_sched_graph *graph) @@ -1047,33 +1171,96 @@ static int node_update_cmap(struct isl_sched_node *node) } /* Count the number of equality and inequality constraints - * that will be added. If once is set, then we count + * that will be added for the given map. + * 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) * proximity -> 2 (lower and upper bound) */ +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 carry) +{ + isl_basic_set *coef; + 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); + else + coef = inter_coefficients(graph, map); + if (!coef) + return -1; + *n_eq += f * coef->n_eq; + *n_ineq += f * coef->n_ineq; + isl_basic_set_free(coef); + + return 0; +} + +/* Count the number of equality and inequality constraints + * that will be added to the main lp problem. + * 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; - isl_basic_set *coef; *n_eq = *n_ineq = 0; for (i = 0; i < graph->n_edge; ++i) { struct isl_sched_edge *edge= &graph->edge[i]; isl_map *map = isl_map_copy(edge->map); - int f = once ? 1 : edge->proximity ? 2 : 1; - if (edge->src == edge->dst) - coef = intra_coefficients(graph, map); - else - coef = inter_coefficients(graph, map); - if (!coef) + if (count_map_constraints(graph, edge, map, + n_eq, n_ineq, 0) < 0) return -1; - *n_eq += f * coef->n_eq; - *n_ineq += f * coef->n_ineq; - isl_basic_set_free(coef); + } + + return 0; +} + +/* Add constraints that bound the values of the variable and parameter + * coefficients of the schedule. + * + * The maximal value of the coefficients is defined by the option + * 'schedule_max_coefficient'. + */ +static int add_bound_coefficient_constraints(isl_ctx *ctx, + struct isl_sched_graph *graph) +{ + int i, j, k; + int max_coefficient; + int total; + + max_coefficient = ctx->opt->schedule_max_coefficient; + + if (max_coefficient == -1) + return 0; + + total = isl_basic_set_total_dim(graph->lp); + + for (i = 0; i < graph->n; ++i) { + struct isl_sched_node *node = &graph->node[i]; + for (j = 0; j < 2 * node->nparam + 2 * node->nvar; ++j) { + int dim; + k = isl_basic_set_alloc_inequality(graph->lp); + if (k < 0) + return -1; + dim = 1 + node->start + 1 + j; + isl_seq_clr(graph->lp->ineq[k], 1 + total); + isl_int_set_si(graph->lp->ineq[k][dim], -1); + isl_int_set_si(graph->lp->ineq[k][0], max_coefficient); + } } return 0; @@ -1109,20 +1296,29 @@ static int count_constraints(struct isl_sched_graph *graph, * * The constraints are those from the edges plus two or three equalities * to express the sums. + * + * If force_zero is set, then we add equalities to ensure that + * the sum of the m_n coefficients and m_0 are both zero. */ -static int setup_lp(isl_ctx *ctx, struct isl_sched_graph *graph) +static int setup_lp(isl_ctx *ctx, struct isl_sched_graph *graph, + int force_zero) { int i, j; int k; unsigned nparam; unsigned total; - isl_dim *dim; + isl_space *dim; int parametric; int param_pos; int n_eq, n_ineq; + int max_constant_term; + int max_coefficient; + + max_constant_term = ctx->opt->schedule_max_constant_term; + max_coefficient = ctx->opt->schedule_max_coefficient; parametric = ctx->opt->schedule_parametric; - nparam = isl_dim_size(graph->node[0].dim, isl_dim_param); + nparam = isl_space_dim(graph->node[0].dim, isl_dim_param); param_pos = 4; total = param_pos + 2 * nparam; for (i = 0; i < graph->n; ++i) { @@ -1133,22 +1329,38 @@ 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_dim_set_alloc(ctx, 0, total); + dim = isl_space_set_alloc(ctx, 0, total); isl_basic_set_free(graph->lp); - n_eq += 2 + parametric; - graph->lp = isl_basic_set_alloc_dim(dim, 0, n_eq, n_ineq); + n_eq += 2 + parametric + force_zero; + if (max_constant_term != -1) + n_ineq += graph->n; + if (max_coefficient != -1) + for (i = 0; i < graph->n; ++i) + n_ineq += 2 * graph->node[i].nparam + + 2 * graph->node[i].nvar; + + graph->lp = isl_basic_set_alloc_space(dim, 0, n_eq, n_ineq); k = isl_basic_set_alloc_equality(graph->lp); if (k < 0) return -1; isl_seq_clr(graph->lp->eq[k], 1 + total); - isl_int_set_si(graph->lp->eq[k][1], -1); + if (!force_zero) + isl_int_set_si(graph->lp->eq[k][1], -1); for (i = 0; i < 2 * nparam; ++i) isl_int_set_si(graph->lp->eq[k][1 + param_pos + i], 1); + if (force_zero) { + k = isl_basic_set_alloc_equality(graph->lp); + if (k < 0) + return -1; + isl_seq_clr(graph->lp->eq[k], 1 + total); + isl_int_set_si(graph->lp->eq[k][2], -1); + } + if (parametric) { k = isl_basic_set_alloc_equality(graph->lp); if (k < 0) @@ -1176,6 +1388,19 @@ static int setup_lp(isl_ctx *ctx, struct isl_sched_graph *graph) isl_int_set_si(graph->lp->eq[k][pos + j], 1); } + if (max_constant_term != -1) + for (i = 0; i < graph->n; ++i) { + struct isl_sched_node *node = &graph->node[i]; + k = isl_basic_set_alloc_inequality(graph->lp); + if (k < 0) + return -1; + isl_seq_clr(graph->lp->ineq[k], 1 + total); + isl_int_set_si(graph->lp->ineq[k][1 + node->start], -1); + isl_int_set_si(graph->lp->ineq[k][0], max_constant_term); + } + + if (add_bound_coefficient_constraints(ctx, graph) < 0) + return -1; if (add_all_validity_constraints(graph) < 0) return -1; if (add_all_proximity_constraints(graph) < 0) @@ -1275,11 +1500,17 @@ static __isl_give isl_vec *solve_lp(struct isl_sched_graph *graph) * t_i_x such that c_i_x = Q t_i_x and Q is equal to node->cmap. * In this case, we then also need to perform this multiplication * to obtain the values of c_i_x. + * + * If check_zero is set, then the first two coordinates of sol are + * assumed to correspond to the dependence distance. If these two + * coordinates are zero, then the corresponding scheduling dimension + * is marked as being zero distance. */ static int update_schedule(struct isl_sched_graph *graph, - __isl_take isl_vec *sol, int use_cmap) + __isl_take isl_vec *sol, int use_cmap, int check_zero) { int i, j; + int zero = 0; isl_vec *csol = NULL; if (!sol) @@ -1287,6 +1518,13 @@ 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]) && + isl_int_is_zero(sol->el[2]); for (i = 0; i < graph->n; ++i) { struct isl_sched_node *node = &graph->node[i]; @@ -1324,6 +1562,7 @@ static int update_schedule(struct isl_sched_graph *graph, node->sched = isl_mat_set_element(node->sched, row, 1 + node->nparam + j, csol->el[j]); node->band[graph->n_total_row] = graph->n_band; + node->zero[graph->n_total_row] = zero; } isl_vec_free(sol); isl_vec_free(csol); @@ -1338,56 +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_dim *dim; - isl_basic_map *bmap; - isl_constraint *c; + isl_space *space; + isl_local_space *ls; + 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_dim_from_domain(isl_dim_copy(node->dim)); - dim = isl_dim_add(dim, isl_dim_out, nrow); - bmap = isl_basic_map_universe(isl_dim_copy(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_dim_copy(dim)); - 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_dim_free(dim); + isl_local_space_free(ls); + + 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); + } - node->sched_map = isl_map_from_basic_map(bmap); return isl_map_copy(node->sched_map); } @@ -1411,12 +1659,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]; @@ -1424,19 +1672,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; @@ -1448,7 +1685,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) @@ -1464,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); @@ -1495,7 +1736,7 @@ static int sort_statements(isl_ctx *ctx, struct isl_sched_graph *graph) * in graph and with parameters specified by dim. */ static __isl_give isl_schedule *extract_schedule(struct isl_sched_graph *graph, - __isl_take isl_dim *dim) + __isl_take isl_space *dim) { int i; isl_ctx *ctx; @@ -1504,28 +1745,43 @@ static __isl_give isl_schedule *extract_schedule(struct isl_sched_graph *graph, if (!dim) return NULL; - ctx = isl_dim_get_ctx(dim); + ctx = isl_space_get_ctx(dim); sched = isl_calloc(ctx, struct isl_schedule, sizeof(struct isl_schedule) + (graph->n - 1) * sizeof(struct isl_schedule_node)); if (!sched) goto error; + sched->ref = 1; sched->n = graph->n; sched->n_band = graph->n_band; sched->n_total_row = graph->n_total_row; for (i = 0; i < sched->n; ++i) { int r, b; - int *band_end; + int *band_end, *band_id, *zero; - band_end = isl_alloc_array(ctx, int, graph->n_band); - if (!band_end) + sched->node[i].sched = + node_extract_schedule_multi_aff(&graph->node[i]); + if (!sched->node[i].sched) goto error; - sched->node[i].sched = node_extract_schedule(&graph->node[i]); - sched->node[i].band_end = band_end; - for (r = b = 0; r < graph->n_total_row; ++r) { + 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].band_end = band_end; + sched->node[i].band_id = band_id; + sched->node[i].zero = zero; + if (!band_end || !band_id || !zero) + goto error; + + for (r = 0; r < graph->n_total_row; ++r) + zero[r] = graph->node[i].zero[r]; + for (r = b = 0; r < graph->n_total_row; ++r) { if (graph->node[i].band[r] == b) continue; band_end[b++] = r; @@ -1535,13 +1791,15 @@ static __isl_give isl_schedule *extract_schedule(struct isl_sched_graph *graph, if (r == graph->n_total_row) band_end[b++] = r; sched->node[i].n_band = b; + for (--b; b >= 0; --b) + band_id[b] = graph->node[i].band_id[b]; } sched->dim = dim; return sched; error: - isl_dim_free(dim); + isl_space_free(dim); isl_schedule_free(sched); return NULL; } @@ -1558,13 +1816,15 @@ static int copy_nodes(struct isl_sched_graph *dst, struct isl_sched_graph *src, for (i = 0; i < src->n; ++i) { if (!node_pred(&src->node[i], data)) continue; - dst->node[dst->n].dim = isl_dim_copy(src->node[i].dim); + dst->node[dst->n].dim = isl_space_copy(src->node[i].dim); dst->node[dst->n].nvar = src->node[i].nvar; dst->node[dst->n].nparam = src->node[i].nparam; dst->node[dst->n].sched = isl_mat_copy(src->node[i].sched); dst->node[dst->n].sched_map = isl_map_copy(src->node[i].sched_map); dst->node[dst->n].band = src->node[i].band; + dst->node[dst->n].band_id = src->node[i].band_id; + dst->node[dst->n].zero = src->node[i].zero; dst->n++; } @@ -1573,17 +1833,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; @@ -1591,16 +1856,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; @@ -1628,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; @@ -1680,6 +1962,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; @@ -1687,11 +1970,14 @@ 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.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; @@ -1725,9 +2011,9 @@ static int node_scc_at_least(struct isl_sched_node *node, int scc) return node->scc >= scc; } -static int edge_src_scc_exactly(struct isl_sched_edge *edge, int scc) +static int edge_scc_exactly(struct isl_sched_edge *edge, int scc) { - return edge->src->scc == scc; + return edge->src->scc == scc && edge->dst->scc == scc; } static int edge_dst_scc_at_most(struct isl_sched_edge *edge, int scc) @@ -1777,6 +2063,14 @@ static int pad_schedule(struct isl_sched_graph *graph) * It would be possible to reuse them as the first rows in the next * band, but recomputing them may result in better rows as we are looking * at a smaller part of the dependence graph. + * compute_split_schedule is only called when no zero-distance schedule row + * could be found on the entire graph, so we wark the splitting row as + * non zero-distance. + * + * The band_id of the second group is set to n, where n is the number + * of nodes in the first group. This ensures that the band_ids over + * the two groups remain disjoint, even if either or both of the two + * groups contain independent components. */ static int compute_split_schedule(isl_ctx *ctx, struct isl_sched_graph *graph) { @@ -1785,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; @@ -1812,6 +2110,7 @@ static int compute_split_schedule(isl_ctx *ctx, struct isl_sched_graph *graph) node->sched = isl_mat_set_element_si(node->sched, row, j, 0); node->band[graph->n_total_row] = graph->n_band; + node->zero[graph->n_total_row] = 0; } e1 = e2 = 0; @@ -1825,6 +2124,12 @@ static int compute_split_schedule(isl_ctx *ctx, struct isl_sched_graph *graph) graph->n_total_row++; next_band(graph); + for (i = 0; i < graph->n; ++i) { + struct isl_sched_node *node = &graph->node[i]; + if (node->scc > graph->src_scc) + node->band_id[graph->n_band] = n; + } + orig_total_row = graph->n_total_row; orig_band = graph->n_band; if (compute_sub_schedule(ctx, graph, n, e1, @@ -1859,9 +2164,10 @@ static int compute_next_band(isl_ctx *ctx, struct isl_sched_graph *graph) return compute_schedule(ctx, graph); } -/* Add constraints to graph->lp that force the dependence of edge i - * to be respected and attempt to carry it, where edge i is one from - * a node j to itself. +/* Add constraints to graph->lp that force the dependence "map" (which + * is part of the dependence relation of "edge") + * to be respected and attempt to carry it, where the edge is one from + * a node j to itself. "pos" is the sequence number of the given map. * That is, add constraints that enforce * * (c_j_0 + c_j_n n + c_j_x y) - (c_j_0 + c_j_n n + c_j_x x) @@ -1873,42 +2179,44 @@ static int compute_next_band(isl_ctx *ctx, struct isl_sched_graph *graph) * with each coefficient in c_j_x represented as a pair of non-negative * coefficients. */ -static int add_intra_constraints(struct isl_sched_graph *graph, int i) +static int add_intra_constraints(struct isl_sched_graph *graph, + struct isl_sched_edge *edge, __isl_take isl_map *map, int pos) { unsigned total; - struct isl_sched_edge *edge= &graph->edge[i]; - isl_map *map = isl_map_copy(edge->map); isl_ctx *ctx = isl_map_get_ctx(map); - isl_dim *dim; + isl_space *dim; isl_dim_map *dim_map; isl_basic_set *coef; struct isl_sched_node *node = edge->src; coef = intra_coefficients(graph, map); + if (!coef) + return -1; - dim = isl_dim_domain(isl_dim_unwrap(isl_basic_set_get_dim(coef))); + dim = isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef))); total = isl_basic_set_total_dim(graph->lp); dim_map = isl_dim_map_alloc(ctx, total); - isl_dim_map_range(dim_map, 3 + i, 0, 0, 0, 1, -1); + isl_dim_map_range(dim_map, 3 + pos, 0, 0, 0, 1, -1); isl_dim_map_range(dim_map, node->start + 2 * node->nparam + 1, 2, - isl_dim_size(dim, isl_dim_set), 1, + isl_space_dim(dim, isl_dim_set), 1, node->nvar, -1); isl_dim_map_range(dim_map, node->start + 2 * node->nparam + 2, 2, - isl_dim_size(dim, isl_dim_set), 1, + isl_space_dim(dim, isl_dim_set), 1, node->nvar, 1); graph->lp = isl_basic_set_extend_constraints(graph->lp, coef->n_eq, coef->n_ineq); graph->lp = isl_basic_set_add_constraints_dim_map(graph->lp, coef, dim_map); - isl_dim_free(dim); + isl_space_free(dim); return 0; } -/* Add constraints to graph->lp that force the dependence of edge i - * to be respected and attempt to carry it, where edge i is one from - * node j to node k. +/* Add constraints to graph->lp that force the dependence "map" (which + * is part of the dependence relation of "edge") + * to be respected and attempt to carry it, where the edge is one from + * node j to node k. "pos" is the sequence number of the given map. * That is, add constraints that enforce * * (c_k_0 + c_k_n n + c_k_x y) - (c_j_0 + c_j_n n + c_j_x x) >= e_i @@ -1920,71 +2228,115 @@ static int add_intra_constraints(struct isl_sched_graph *graph, int i) * with each coefficient (except e_i, c_k_0 and c_j_0) * represented as a pair of non-negative coefficients. */ -static int add_inter_constraints(struct isl_sched_graph *graph, int i) +static int add_inter_constraints(struct isl_sched_graph *graph, + struct isl_sched_edge *edge, __isl_take isl_map *map, int pos) { unsigned total; - struct isl_sched_edge *edge= &graph->edge[i]; - isl_map *map = isl_map_copy(edge->map); isl_ctx *ctx = isl_map_get_ctx(map); - isl_dim *dim; + isl_space *dim; isl_dim_map *dim_map; isl_basic_set *coef; struct isl_sched_node *src = edge->src; struct isl_sched_node *dst = edge->dst; coef = inter_coefficients(graph, map); + if (!coef) + return -1; - dim = isl_dim_domain(isl_dim_unwrap(isl_basic_set_get_dim(coef))); + dim = isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef))); total = isl_basic_set_total_dim(graph->lp); dim_map = isl_dim_map_alloc(ctx, total); - isl_dim_map_range(dim_map, 3 + i, 0, 0, 0, 1, -1); + isl_dim_map_range(dim_map, 3 + pos, 0, 0, 0, 1, -1); isl_dim_map_range(dim_map, dst->start, 0, 0, 0, 1, 1); isl_dim_map_range(dim_map, dst->start + 1, 2, 1, 1, dst->nparam, -1); isl_dim_map_range(dim_map, dst->start + 2, 2, 1, 1, dst->nparam, 1); isl_dim_map_range(dim_map, dst->start + 2 * dst->nparam + 1, 2, - isl_dim_size(dim, isl_dim_set) + src->nvar, 1, + isl_space_dim(dim, isl_dim_set) + src->nvar, 1, dst->nvar, -1); isl_dim_map_range(dim_map, dst->start + 2 * dst->nparam + 2, 2, - isl_dim_size(dim, isl_dim_set) + src->nvar, 1, + isl_space_dim(dim, isl_dim_set) + src->nvar, 1, dst->nvar, 1); isl_dim_map_range(dim_map, src->start, 0, 0, 0, 1, -1); isl_dim_map_range(dim_map, src->start + 1, 2, 1, 1, src->nparam, 1); isl_dim_map_range(dim_map, src->start + 2, 2, 1, 1, src->nparam, -1); isl_dim_map_range(dim_map, src->start + 2 * src->nparam + 1, 2, - isl_dim_size(dim, isl_dim_set), 1, + isl_space_dim(dim, isl_dim_set), 1, src->nvar, 1); isl_dim_map_range(dim_map, src->start + 2 * src->nparam + 2, 2, - isl_dim_size(dim, isl_dim_set), 1, + isl_space_dim(dim, isl_dim_set), 1, src->nvar, -1); graph->lp = isl_basic_set_extend_constraints(graph->lp, coef->n_eq, coef->n_ineq); graph->lp = isl_basic_set_add_constraints_dim_map(graph->lp, coef, dim_map); - isl_dim_free(dim); + isl_space_free(dim); 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) { - int i; + int i, j; + int pos; + pos = 0; for (i = 0; i < graph->n_edge; ++i) { struct isl_sched_edge *edge= &graph->edge[i]; - if (edge->src == edge->dst && - add_intra_constraints(graph, i) < 0) - return -1; - if (edge->src != edge->dst && - add_inter_constraints(graph, i) < 0) - return -1; + + if (!edge->validity) + continue; + + for (j = 0; j < edge->map->n; ++j) { + isl_basic_map *bmap; + isl_map *map; + + bmap = isl_basic_map_copy(edge->map->p[j]); + map = isl_map_from_basic_map(bmap); + + if (edge->src == edge->dst && + add_intra_constraints(graph, edge, map, pos) < 0) + return -1; + if (edge->src != edge->dst && + add_inter_constraints(graph, edge, map, pos) < 0) + return -1; + ++pos; + } + } + + return 0; +} + +/* Count the number of equality and inequality constraints + * that will be added to the carry_lp problem. + * We count each edge exactly once. + */ +static int count_all_constraints(struct isl_sched_graph *graph, + int *n_eq, int *n_ineq) +{ + int i, j; + + *n_eq = *n_ineq = 0; + for (i = 0; i < graph->n_edge; ++i) { + struct isl_sched_edge *edge= &graph->edge[i]; + for (j = 0; j < edge->map->n; ++j) { + isl_basic_map *bmap; + isl_map *map; + + bmap = isl_basic_map_copy(edge->map->p[j]); + map = isl_map_from_basic_map(bmap); + + if (count_map_constraints(graph, edge, map, + n_eq, n_ineq, 1) < 0) + return -1; + } } return 0; @@ -1996,6 +2348,11 @@ static int add_all_constraints(struct isl_sched_graph *graph) * from below by e_i, with 0 <= e_i <= 1 and then maximize the sum * of all e_i's. Dependence with e_i = 0 in the solution are simply * respected, while those with e_i > 0 (in practice e_i = 1) are carried. + * Note that if the dependence relation is a union of basic maps, + * then we have to consider each basic map individually as it may only + * be possible to carry the dependences expressed by some of those + * basic maps and not all off them. + * Below, we consider each of those basic maps as a separate "edge". * * All variables of the LP are non-negative. The actual coefficients * may be negative, so each coefficient is represented as the difference @@ -2014,41 +2371,46 @@ static int add_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) { int i, j; int k; - isl_dim *dim; + isl_space *dim; unsigned total; int n_eq, n_ineq; + int n_edge; - total = 3 + graph->n_edge; + n_edge = 0; + for (i = 0; i < graph->n_edge; ++i) + n_edge += graph->edge[i].map->n; + + total = 3 + n_edge; for (i = 0; i < graph->n; ++i) { struct isl_sched_node *node = &graph->node[graph->sorted[i]]; node->start = total; total += 1 + 2 * (node->nparam + node->nvar); } - if (count_constraints(graph, &n_eq, &n_ineq, 1) < 0) + if (count_all_constraints(graph, &n_eq, &n_ineq) < 0) return -1; - dim = isl_dim_set_alloc(ctx, 0, total); + dim = isl_space_set_alloc(ctx, 0, total); isl_basic_set_free(graph->lp); n_eq += 3; - n_ineq += graph->n_edge; - graph->lp = isl_basic_set_alloc_dim(dim, 0, n_eq, n_ineq); + n_ineq += n_edge; + graph->lp = isl_basic_set_alloc_space(dim, 0, n_eq, n_ineq); graph->lp = isl_basic_set_set_rational(graph->lp); k = isl_basic_set_alloc_equality(graph->lp); if (k < 0) return -1; isl_seq_clr(graph->lp->eq[k], 1 + total); - isl_int_set_si(graph->lp->eq[k][0], -graph->n_edge); + isl_int_set_si(graph->lp->eq[k][0], -n_edge); isl_int_set_si(graph->lp->eq[k][1], 1); - for (i = 0; i < graph->n_edge; ++i) + for (i = 0; i < n_edge; ++i) isl_int_set_si(graph->lp->eq[k][4 + i], 1); k = isl_basic_set_alloc_equality(graph->lp); @@ -2076,7 +2438,7 @@ static int setup_carry_lp(isl_ctx *ctx, struct isl_sched_graph *graph) isl_int_set_si(graph->lp->eq[k][pos + j], 1); } - for (i = 0; i < graph->n_edge; ++i) { + for (i = 0; i < n_edge; ++i) { k = isl_basic_set_alloc_inequality(graph->lp); if (k < 0) return -1; @@ -2091,14 +2453,148 @@ static int setup_carry_lp(isl_ctx *ctx, struct isl_sched_graph *graph) return 0; } +/* If the schedule_split_scaled option is set and if the linear + * parts of the scheduling rows for all nodes in the graphs have + * non-trivial common divisor, then split off the constant term + * from the linear part. + * The constant term is then placed in a separate band and + * the linear part is reduced. + */ +static int split_scaled(isl_ctx *ctx, struct isl_sched_graph *graph) +{ + int i; + int row; + isl_int gcd, gcd_i; + + if (!ctx->opt->schedule_split_scaled) + return 0; + 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); + + isl_int_set_si(gcd, 0); + + row = isl_mat_rows(graph->node[0].sched) - 1; + + for (i = 0; i < graph->n; ++i) { + struct isl_sched_node *node = &graph->node[i]; + int cols = isl_mat_cols(node->sched); + + isl_seq_gcd(node->sched->row[row] + 1, cols - 1, &gcd_i); + isl_int_gcd(gcd, gcd, gcd_i); + } + + isl_int_clear(gcd_i); + + if (isl_int_cmp_si(gcd, 1) <= 0) { + isl_int_clear(gcd); + return 0; + } + + next_band(graph); + + for (i = 0; i < graph->n; ++i) { + struct isl_sched_node *node = &graph->node[i]; + + isl_map_free(node->sched_map); + node->sched_map = NULL; + node->sched = isl_mat_add_zero_rows(node->sched, 1); + if (!node->sched) + goto error; + isl_int_fdiv_r(node->sched->row[row + 1][0], + node->sched->row[row][0], gcd); + isl_int_fdiv_q(node->sched->row[row][0], + node->sched->row[row][0], gcd); + isl_int_mul(node->sched->row[row][0], + node->sched->row[row][0], gcd); + node->sched = isl_mat_scale_down_row(node->sched, row, gcd); + if (!node->sched) + goto error; + node->band[graph->n_total_row] = graph->n_band; + } + + graph->n_total_row++; + + isl_int_clear(gcd); + return 0; +error: + isl_int_clear(gcd); + 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) { + int i; + int n_edge; isl_vec *sol; isl_basic_set *lp; + n_edge = 0; + for (i = 0; i < graph->n_edge; ++i) + n_edge += graph->edge[i].map->n; + if (setup_carry_lp(ctx, graph) < 0) return -1; @@ -2113,18 +2609,79 @@ static int carry_dependences(isl_ctx *ctx, struct isl_sched_graph *graph) "error in schedule construction", return -1); } - if (isl_int_cmp_si(sol->el[1], graph->n_edge) >= 0) { + 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 (update_schedule(graph, sol, 0) < 0) + 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; + + if (split_scaled(ctx, graph) < 0) return -1; return compute_next_band(ctx, 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) { + 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; +} + +/* Should we apply a Feautrier step? + * That is, did the user request the Feautrier algorithm and are + * there any validity dependences (left)? + */ +static int need_feautrier_step(isl_ctx *ctx, struct isl_sched_graph *graph) +{ + if (ctx->opt->schedule_algorithm != ISL_SCHEDULE_ALGORITHM_FEAUTRIER) + return 0; + + return has_validity_edges(graph); +} + +/* Compute a schedule for a connected dependence graph using Feautrier's + * multi-dimensional scheduling algorithm. + * The original algorithm is described in [1]. + * The main idea is to minimize the number of scheduling dimensions, by + * trying to satisfy as many dependences as possible per scheduling dimension. + * + * [1] P. Feautrier, Some Efficient Solutions to the Affine Scheduling + * Problem, Part II: Multi-Dimensional Time. + * In Intl. Journal of Parallel Programming, 1992. + */ +static int compute_schedule_wcc_feautrier(isl_ctx *ctx, + struct isl_sched_graph *graph) +{ + return carry_dependences(ctx, graph); +} + /* Compute a schedule for a connected dependence graph. * We try to find a sequence of as many schedule rows as possible that result * in non-negative dependence distances (independent of the previous rows @@ -2137,39 +2694,61 @@ static int carry_dependences(isl_ctx *ctx, struct isl_sched_graph *graph) * - try to carry as many dependences as possible and continue with the next * band * + * If Feautrier's algorithm is selected, we first recursively try to satisfy + * as many validity dependences as possible. When all validity dependences + * are satisfied we extend the schedule to a full-dimensional schedule. + * * If we manage to complete the schedule, we finish off by topologically * sorting the statements based on the remaining dependences. + * + * If ctx->opt->schedule_outer_zero_distance is set, then we force the + * outermost dimension in the current band to be zero distance. If this + * turns out to be impossible, we fall back on the general scheme above + * and try to carry as many dependences as possible. */ static int compute_schedule_wcc(isl_ctx *ctx, struct isl_sched_graph *graph) { - if (detect_sccs(graph) < 0) + int force_zero = 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; + if (need_feautrier_step(ctx, graph)) + return compute_schedule_wcc_feautrier(ctx, graph); + + if (ctx->opt->schedule_outer_zero_distance) + force_zero = 1; + while (graph->n_row < graph->maxvar) { isl_vec *sol; graph->src_scc = -1; graph->dst_scc = -1; - if (setup_lp(ctx, graph) < 0) + if (setup_lp(ctx, graph, force_zero) < 0) return -1; sol = solve_lp(graph); if (!sol) return -1; if (sol->size == 0) { isl_vec_free(sol); + if (!ctx->opt->schedule_maximize_band_depth && + graph->n_total_row > graph->band_start) + return compute_next_band(ctx, graph); if (graph->src_scc >= 0) return compute_split_schedule(ctx, graph); if (graph->n_total_row > graph->band_start) return compute_next_band(ctx, graph); return carry_dependences(ctx, graph); } - if (update_schedule(graph, sol, 1) < 0) + if (update_schedule(graph, sol, 1, 1) < 0) return -1; + force_zero = 0; } if (graph->n_total_row > graph->band_start) @@ -2177,8 +2756,45 @@ static int compute_schedule_wcc(isl_ctx *ctx, struct isl_sched_graph *graph) return sort_statements(ctx, graph); } +/* Add a row to the schedules that separates the SCCs and move + * to the next band. + */ +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); + + isl_map_free(node->sched_map); + node->sched_map = NULL; + node->sched = isl_mat_add_zero_rows(node->sched, 1); + node->sched = isl_mat_set_element_si(node->sched, row, 0, + node->scc); + if (!node->sched) + return -1; + node->band[graph->n_total_row] = graph->n_band; + } + + graph->n_total_row++; + next_band(graph); + + return 0; +} + /* Compute a schedule for each component (identified by node->scc) * of the dependence graph separately and then combine the results. + * Depending on the setting of schedule_fuse, a component may be + * either weakly or strongly connected. + * + * The band_id is adjusted such that each component has a separate id. + * Note that the band_id may have already been set to a value different + * from zero by compute_split_schedule. */ static int compute_component_schedule(isl_ctx *ctx, struct isl_sched_graph *graph) @@ -2188,10 +2804,17 @@ 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 || + 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; n_band = 0; orig_band = graph->n_band; + for (i = 0; i < graph->n; ++i) + graph->node[i].band_id[graph->n_band] += graph->node[i].scc; for (wcc = 0; wcc < graph->scc; ++wcc) { n = 0; for (i = 0; i < graph->n; ++i) @@ -2199,12 +2822,13 @@ static int compute_component_schedule(isl_ctx *ctx, n++; n_edge = 0; for (i = 0; i < graph->n_edge; ++i) - if (graph->edge[i].src->scc == wcc) + if (graph->edge[i].src->scc == wcc && + graph->edge[i].dst->scc == wcc) n_edge++; if (compute_sub_schedule(ctx, graph, n, n_edge, &node_scc_exactly, - &edge_src_scc_exactly, wcc, 1) < 0) + &edge_scc_exactly, wcc, 1) < 0) return -1; if (graph->n_total_row > n_total_row) n_total_row = graph->n_total_row; @@ -2222,12 +2846,20 @@ static int compute_component_schedule(isl_ctx *ctx, /* Compute a schedule for the given dependence graph. * We first check if the graph is connected (through validity dependences) - * and if so compute a schedule for each component separately. + * and, if not, compute a schedule for each component separately. + * If schedule_fuse is set to minimal fusion, then we check for strongly + * connected components instead and compute a separate schedule for + * each such strongly connected component. */ static int compute_schedule(isl_ctx *ctx, struct isl_sched_graph *graph) { - if (detect_wccs(graph) < 0) - return -1; + if (ctx->opt->schedule_fuse == ISL_SCHEDULE_FUSE_MIN) { + if (detect_sccs(ctx, graph) < 0) + return -1; + } else { + if (detect_wccs(ctx, graph) < 0) + return -1; + } if (graph->scc > 1) return compute_component_schedule(ctx, graph); @@ -2236,8 +2868,12 @@ static int compute_schedule(isl_ctx *ctx, struct isl_sched_graph *graph) } /* Compute a schedule for the given union of domains that respects - * all the validity dependences and tries to minimize the dependence - * distances over the proximity dependences. + * all the validity dependences. + * If the default isl scheduling algorithm is used, it tries to minimize + * the dependence distances over the proximity dependences. + * If Feautrier's scheduling algorithm is used, the proximity dependence + * distances are only minimized during the extension to a full-dimensional + * schedule. */ __isl_give isl_schedule *isl_union_set_compute_schedule( __isl_take isl_union_set *domain, @@ -2245,16 +2881,17 @@ __isl_give isl_schedule *isl_union_set_compute_schedule( __isl_take isl_union_map *proximity) { isl_ctx *ctx = isl_union_set_get_ctx(domain); - isl_dim *dim; + 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_dim(validity)); + isl_union_map_get_space(validity)); domain = isl_union_set_align_params(domain, - isl_union_map_get_dim(proximity)); - dim = isl_union_set_get_dim(domain); - validity = isl_union_map_align_params(validity, isl_dim_copy(dim)); + isl_union_map_get_space(proximity)); + dim = isl_union_set_get_space(domain); + validity = isl_union_map_align_params(validity, isl_space_copy(dim)); proximity = isl_union_map_align_params(proximity, dim); if (!domain) @@ -2266,25 +2903,32 @@ __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) goto error; empty: - sched = extract_schedule(&graph, isl_union_set_get_dim(domain)); + sched = extract_schedule(&graph, isl_union_set_get_space(domain)); graph_free(ctx, &graph); isl_union_set_free(domain); @@ -2305,15 +2949,105 @@ void *isl_schedule_free(__isl_take isl_schedule *sched) int i; if (!sched) return NULL; + + if (--sched->ref > 0) + 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); } - isl_dim_free(sched->dim); + isl_space_free(sched->dim); + isl_band_list_free(sched->band_forest); free(sched); return NULL; } +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; @@ -2322,51 +3056,315 @@ __isl_give isl_union_map *isl_schedule_get_map(__isl_keep isl_schedule *sched) if (!sched) return NULL; - umap = isl_union_map_empty(isl_dim_copy(sched->dim)); - for (i = 0; i < sched->n; ++i) - umap = isl_union_map_add_map(umap, - isl_map_copy(sched->node[i].sched)); + 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) { + 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; } -int isl_schedule_n_band(__isl_keep isl_schedule *sched) +static __isl_give isl_band_list *construct_band_list( + __isl_keep isl_schedule *schedule, __isl_keep isl_band *parent, + int band_nr, int *parent_active, int n_active); + +/* Construct an isl_band structure for the band in the given schedule + * with sequence number band_nr for the n_active nodes marked by active. + * If the nodes don't have a band with the given sequence number, + * then a band without members is created. + * + * 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. + */ +static __isl_give isl_band *construct_band(__isl_keep isl_schedule *schedule, + __isl_keep isl_band *parent, + int band_nr, int *active, int n_active) { - return sched ? sched->n_band : 0; + int i, j; + isl_ctx *ctx = isl_schedule_get_ctx(schedule); + isl_band *band; + unsigned start, end; + + band = isl_band_alloc(ctx); + if (!band) + return NULL; + + band->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; + + if (i >= schedule->n) + isl_die(ctx, isl_error_internal, + "band without active statements", goto error); + + start = band_nr ? schedule->node[i].band_end[band_nr - 1] : 0; + end = band_nr < schedule->node[i].n_band ? + schedule->node[i].band_end[band_nr] : start; + band->n = end - start; + + band->zero = isl_alloc_array(ctx, int, band->n); + if (!band->zero) + goto error; + + for (j = 0; j < band->n; ++j) + band->zero[j] = schedule->node[i].zero[start + j]; + + band->pma = isl_union_pw_multi_aff_empty(isl_space_copy(schedule->dim)); + for (i = 0; i < schedule->n; ++i) { + isl_multi_aff *ma; + isl_pw_multi_aff *pma; + unsigned n_out; + + if (!active[i]) + continue; + + 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->pma) + goto error; + + return band; +error: + isl_band_free(band); + return NULL; } -/* Construct a mapping that maps each domain to the band in its schedule - * with the specified band index. Note that bands with the same index - * but for different domains do not need to be related. +/* 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. + * + * A separate isl_band structure is created for each band_id + * and for each node that does not have a band with sequence + * number band_nr. In the latter case, a band without members + * is created. + * This ensures that if a band has any children, then each node + * that was active in the band is active in exactly one of the children. */ -__isl_give isl_union_map *isl_schedule_get_band(__isl_keep isl_schedule *sched, - unsigned band) +static __isl_give isl_band_list *construct_band_list( + __isl_keep isl_schedule *schedule, __isl_keep isl_band *parent, + int band_nr, int *parent_active, int n_active) { - int i; - isl_union_map *umap; + int i, j; + isl_ctx *ctx = isl_schedule_get_ctx(schedule); + int *active; + int n_band; + isl_band_list *list; - if (!sched) + n_band = 0; + for (i = 0; i < n_active; ++i) { + for (j = 0; j < schedule->n; ++j) { + if (!parent_active[j]) + continue; + if (schedule->node[j].n_band <= band_nr) + continue; + if (schedule->node[j].band_id[band_nr] == i) { + n_band++; + break; + } + } + } + for (j = 0; j < schedule->n; ++j) + if (schedule->node[j].n_band <= band_nr) + n_band++; + + if (n_band == 1) { + isl_band *band; + list = isl_band_list_alloc(ctx, n_band); + band = construct_band(schedule, parent, band_nr, + parent_active, n_active); + return isl_band_list_add(list, band); + } + + active = isl_alloc_array(ctx, int, schedule->n); + if (!active) return NULL; - umap = isl_union_map_empty(isl_dim_copy(sched->dim)); - for (i = 0; i < sched->n; ++i) { - int start, end; - isl_map *map; + list = isl_band_list_alloc(ctx, n_band); + + for (i = 0; i < n_active; ++i) { + int n = 0; + isl_band *band; + + for (j = 0; j < schedule->n; ++j) { + active[j] = parent_active[j] && + schedule->node[j].n_band > band_nr && + schedule->node[j].band_id[band_nr] == i; + if (active[j]) + n++; + } + if (n == 0) + continue; - if (band >= sched->node[i].n_band) + band = construct_band(schedule, parent, band_nr, active, n); + + list = isl_band_list_add(list, band); + } + for (i = 0; i < schedule->n; ++i) { + isl_band *band; + if (!parent_active[i]) + continue; + if (schedule->node[i].n_band > band_nr) continue; + for (j = 0; j < schedule->n; ++j) + active[j] = j == i; + band = construct_band(schedule, parent, band_nr, active, 1); + list = isl_band_list_add(list, band); + } + + free(active); + + return list; +} + +/* Construct a band forest representation of the schedule and + * return the list of roots. + */ +static __isl_give isl_band_list *construct_forest( + __isl_keep isl_schedule *schedule) +{ + int i; + isl_ctx *ctx = isl_schedule_get_ctx(schedule); + isl_band_list *forest; + int *active; - start = band > 0 ? sched->node[i].band_end[band - 1] : 0; - end = sched->node[i].band_end[band]; + active = isl_alloc_array(ctx, int, schedule->n); + if (!active) + return NULL; + + for (i = 0; i < schedule->n; ++i) + active[i] = 1; + + forest = construct_band_list(schedule, NULL, 0, active, schedule->n); + + free(active); + + return forest; +} + +/* Return the roots of a band forest representation of the schedule. + */ +__isl_give isl_band_list *isl_schedule_get_band_forest( + __isl_keep isl_schedule *schedule) +{ + if (!schedule) + return NULL; + if (!schedule->band_forest) + schedule->band_forest = construct_forest(schedule); + 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); + +static __isl_give isl_printer *print_band(__isl_take isl_printer *p, + __isl_keep isl_band *band) +{ + isl_band_list *children; + + p = isl_printer_start_line(p); + p = isl_printer_print_union_pw_multi_aff(p, band->pma); + p = isl_printer_end_line(p); + + if (!isl_band_has_children(band)) + return p; - map = isl_map_copy(sched->node[i].sched); + children = isl_band_get_children(band); - map = isl_map_project_out(map, isl_dim_out, end, - sched->n_total_row - end); - map = isl_map_project_out(map, isl_dim_out, 0, start); + p = isl_printer_indent(p, 4); + p = print_band_list(p, children); + p = isl_printer_indent(p, -4); + + isl_band_list_free(children); + + return p; +} - umap = isl_union_map_add_map(umap, map); +static __isl_give isl_printer *print_band_list(__isl_take isl_printer *p, + __isl_keep isl_band_list *list) +{ + int i, n; + + n = isl_band_list_n_band(list); + for (i = 0; i < n; ++i) { + isl_band *band; + band = isl_band_list_get_band(list, i); + p = print_band(p, band); + isl_band_free(band); } - return umap; + return p; +} + +__isl_give isl_printer *isl_printer_print_schedule(__isl_take isl_printer *p, + __isl_keep isl_schedule *schedule) +{ + isl_band_list *forest; + + forest = isl_schedule_get_band_forest(schedule); + + p = print_band_list(p, forest); + + isl_band_list_free(forest); + + return p; +} + +void isl_schedule_dump(__isl_keep isl_schedule *schedule) +{ + isl_printer *printer; + + if (!schedule) + return; + + printer = isl_printer_to_file(isl_schedule_get_ctx(schedule), stderr); + printer = isl_printer_print_schedule(printer, schedule); + + isl_printer_free(printer); }