return edge->src == temp->src && edge->dst == temp->dst;
}
+/* Add the given edge to graph->edge_table if it is a validity edge.
+ */
+static int graph_edge_table_add(isl_ctx *ctx, struct isl_sched_graph *graph,
+ struct isl_sched_edge *edge)
+{
+ struct isl_hash_table_entry *entry;
+ uint32_t hash;
+
+ if (!edge->validity)
+ return 0;
+
+ 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, hash,
+ &edge_has_src_and_dst, edge, 1);
+ if (!entry)
+ return -1;
+ entry->data = edge;
+
+ return 0;
+}
+
/* Initialize edge_table based on the list of edges.
* Only edges with validity set are added to the table.
*/
if (!graph->edge_table)
return -1;
- for (i = 0; i < graph->n_edge; ++i) {
- struct isl_hash_table_entry *entry;
- uint32_t hash;
-
- if (!graph->edge[i].validity)
- continue;
-
- 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 < graph->n_edge; ++i)
+ if (graph_edge_table_add(ctx, graph, &graph->edge[i]) < 0)
return -1;
- entry->data = &graph->edge[i];
- }
return 0;
}
/* 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);
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)
/* 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,
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;
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;
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)
{
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);
projects / platform / upstream / isl.git / blobdiff