/*
* 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,
#include <isl_ctx_private.h>
#include <isl_map_private.h>
#include <isl_space_private.h>
+#include <isl/aff.h>
#include <isl/hash.h>
#include <isl/constraint.h>
#include <isl/schedule.h>
#include <isl_tab.h>
#include <isl_dim_map.h>
#include <isl_hmap_map_basic_set.h>
-#include <isl_qsort.h>
+#include <isl_sort.h>
#include <isl_schedule_private.h>
#include <isl_band_private.h>
#include <isl_list_private.h>
#include <isl_options_private.h>
+#include <isl_tarjan.h>
/*
* The scheduling algorithm implemented in this file was inspired by
* indicating whether the corresponding scheduling dimension results
* in zero dependence distances within its band and with respect
* to the proximity edges.
- *
- * index, min_index and on_stack are used during the SCC detection
- * index represents the order in which nodes are visited.
- * min_index is the index of the root of a (sub)component.
- * on_stack indicates whether the node is currently on the stack.
*/
struct isl_sched_node {
isl_space *dim;
int *band;
int *band_id;
int *zero;
-
- /* scc detection */
- int index;
- int min_index;
- int on_stack;
};
static int node_has_dim(const void *entry, const void *val)
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.
*
* 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
*
* 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
*
* 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;
struct isl_sched_node *node;
int n;
int maxvar;
+ int max_row;
int n_row;
int *sorted;
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;
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.
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;
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)
{
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)
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)
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++;
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);
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)
/* 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,
coef = isl_basic_set_transform_dims(coef, isl_dim_set,
isl_space_dim(dim, isl_dim_set), isl_mat_copy(node->cmap));
+ if (!coef)
+ goto error;
total = isl_basic_set_total_dim(graph->lp);
dim_map = isl_dim_map_alloc(ctx, total);
isl_space_free(dim);
return 0;
+error:
+ isl_space_free(dim);
+ return -1;
}
/* Add constraints to graph->lp that force validity for the given
coef = isl_basic_set_transform_dims(coef, isl_dim_set,
isl_space_dim(dim, isl_dim_set) + src->nvar,
isl_mat_copy(dst->cmap));
+ if (!coef)
+ goto error;
total = isl_basic_set_total_dim(graph->lp);
dim_map = isl_dim_map_alloc(ctx, total);
coef->n_eq, coef->n_ineq);
graph->lp = isl_basic_set_add_constraints_dim_map(graph->lp,
coef, dim_map);
+ if (!graph->lp)
+ goto error;
isl_space_free(dim);
edge->end = graph->lp->n_ineq;
return 0;
+error:
+ isl_space_free(dim);
+ return -1;
}
/* Add constraints to graph->lp that bound the dependence distance for the given
coef = isl_basic_set_transform_dims(coef, isl_dim_set,
isl_space_dim(dim, isl_dim_set), isl_mat_copy(node->cmap));
+ if (!coef)
+ goto error;
nparam = isl_space_dim(node->dim, isl_dim_param);
total = isl_basic_set_total_dim(graph->lp);
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
coef = isl_basic_set_transform_dims(coef, isl_dim_set,
isl_space_dim(dim, isl_dim_set) + src->nvar,
isl_mat_copy(dst->cmap));
+ if (!coef)
+ goto error;
nparam = isl_space_dim(src->dim, isl_dim_param);
total = isl_basic_set_total_dim(graph->lp);
isl_space_free(dim);
return 0;
+error:
+ isl_space_free(dim);
+ return -1;
}
static int add_all_validity_constraints(struct isl_sched_graph *graph)
/* 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)
*/
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);
/* 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;
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;
}
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);
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]) &&
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);
}
/* 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];
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;
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);
int r, b;
int *band_end, *band_id, *zero;
+ sched->node[i].sched =
+ node_extract_schedule_multi_aff(&graph->node[i]);
+ if (!sched->node[i].sched)
+ goto error;
+
+ sched->node[i].n_band = graph->n_band;
+ if (graph->n_band == 0)
+ continue;
+
band_end = isl_alloc_array(ctx, int, graph->n_band);
band_id = isl_alloc_array(ctx, int, graph->n_band);
zero = isl_alloc_array(ctx, int, graph->n_total_row);
- sched->node[i].sched = node_extract_schedule(&graph->node[i]);
sched->node[i].band_end = band_end;
sched->node[i].band_id = band_id;
sched->node[i].zero = zero;
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) {
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;
src->n++;
}
+ dst->max_row = src->max_row;
dst->n_total_row = src->n_total_row;
dst->n_band = src->n_band;
int data, int wcc)
{
struct isl_sched_graph split = { 0 };
+ int t;
if (graph_alloc(ctx, &split, n, n_edge) < 0)
goto error;
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;
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;
struct isl_sched_node *node = edge->src;
coef = intra_coefficients(graph, map);
+ if (!coef)
+ return -1;
dim = isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef)));
struct isl_sched_node *dst = edge->dst;
coef = inter_coefficients(graph, map);
+ if (!coef)
+ return -1;
dim = isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef)));
return 0;
}
-/* Add constraints to graph->lp that force all dependences
+/* 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)
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;
/* 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;
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;
}
}
* - 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)
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);
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);
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)
{
"unable to carry dependences", return -1);
}
+ if (is_any_trivial(graph, sol)) {
+ isl_vec_free(sol);
+ if (graph->scc > 1)
+ return compute_component_schedule(ctx, graph);
+ isl_die(ctx, isl_error_unknown,
+ "unable to construct non-trivial solution", return -1);
+ }
+
if (update_schedule(graph, sol, 0, 0) < 0)
return -1;
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;
}
{
int force_zero = 0;
- if (detect_sccs(graph) < 0)
+ if (detect_sccs(ctx, graph) < 0)
+ return -1;
+ if (sort_sccs(graph) < 0)
return -1;
- sort_sccs(graph);
if (compute_maxvar(graph) < 0)
return -1;
/* Add a row to the schedules that separates the SCCs and move
* to the next band.
*/
-static int split_on_scc(struct isl_sched_graph *graph)
+static int split_on_scc(isl_ctx *ctx, struct isl_sched_graph *graph)
{
int i;
+ if (graph->n_total_row >= graph->max_row)
+ isl_die(ctx, isl_error_internal,
+ "too many schedule rows", return -1);
+
for (i = 0; i < graph->n; ++i) {
struct isl_sched_node *node = &graph->node[i];
int row = isl_mat_rows(node->sched);
int n_total_row, orig_total_row;
int n_band, orig_band;
- if (ctx->opt->schedule_fuse == ISL_SCHEDULE_FUSE_MIN)
- split_on_scc(graph);
+ if (ctx->opt->schedule_fuse == ISL_SCHEDULE_FUSE_MIN ||
+ ctx->opt->schedule_separate_components)
+ if (split_on_scc(ctx, graph) < 0)
+ return -1;
n_total_row = 0;
orig_total_row = graph->n_total_row;
static int compute_schedule(isl_ctx *ctx, struct isl_sched_graph *graph)
{
if (ctx->opt->schedule_fuse == ISL_SCHEDULE_FUSE_MIN) {
- if (detect_sccs(graph) < 0)
+ if (detect_sccs(ctx, graph) < 0)
return -1;
} else {
- if (detect_wccs(graph) < 0)
+ if (detect_wccs(ctx, graph) < 0)
return -1;
}
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));
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)
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);
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;
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;
}
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;
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;
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);
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))