X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=isl_schedule.c;h=9760c626b78d61a5e16e3b78c2528b31dfe754e2;hb=de51a9bc4da5dd3f1f9f57c2362da6f9752c44e0;hp=f14fbd95b7881a91f652672bd9cb724be673011b;hpb=d07eed3bf4d0e290118588ca80997a8035eaeb21;p=platform%2Fupstream%2Fisl.git

diff --git a/isl_schedule.c b/isl_schedule.c
index f14fbd9..9760c62 100644
--- a/isl_schedule.c
+++ b/isl_schedule.c
@@ -1,7 +1,7 @@
 /*
  * Copyright 2011      INRIA Saclay
  *
- * Use of this software is governed by the GNU LGPLv2.1 license
+ * Use of this software is governed by the MIT license
  *
  * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
  * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
@@ -11,6 +11,7 @@
 #include <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>
@@ -20,10 +21,12 @@
 #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
@@ -60,11 +63,6 @@
  * indicating whether the corresponding scheduling dimension results
  * in zero dependence distances within its band and with respect
  * to the proximity edges.
- *
- * index, min_index and on_stack are used during the SCC detection
- * index represents the order in which nodes are visited.
- * min_index is the index of the root of a (sub)component.
- * on_stack indicates whether the node is currently on the stack.
  */
 struct isl_sched_node {
 	isl_space *dim;
@@ -81,11 +79,6 @@ struct isl_sched_node {
 	int	*band;
 	int	*band_id;
 	int	*zero;
-
-	/* scc detection */
-	int	 index;
-	int	 min_index;
-	int	 on_stack;
 };
 
 static int node_has_dim(const void *entry, const void *val)
@@ -123,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.
  *
@@ -134,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
@@ -147,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
  *
@@ -161,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;
@@ -174,6 +174,7 @@ struct isl_sched_graph {
 	struct isl_sched_node *node;
 	int n;
 	int maxvar;
+	int max_row;
 	int n_row;
 
 	int *sorted;
@@ -186,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;
@@ -196,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.
@@ -253,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_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;
@@ -314,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)
 {
@@ -324,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)
@@ -365,12 +462,49 @@ static void graph_free(isl_ctx *ctx, struct isl_sched_graph *graph)
 		isl_map_free(graph->edge[i].map);
 	free(graph->edge);
 	free(graph->region);
-	free(graph->stack);
-	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)
@@ -395,11 +529,11 @@ static int extract_node(__isl_take isl_set *set, void *user)
 	graph->node[graph->n].nparam = nparam;
 	graph->node[graph->n].sched = sched;
 	graph->node[graph->n].sched_map = NULL;
-	band = isl_alloc_array(ctx, int, graph->n_edge + nvar);
+	band = isl_alloc_array(ctx, int, graph->max_row);
 	graph->node[graph->n].band = band;
-	band_id = isl_calloc_array(ctx, int, graph->n_edge + nvar);
+	band_id = isl_calloc_array(ctx, int, graph->max_row);
 	graph->node[graph->n].band_id = band_id;
-	zero = isl_calloc_array(ctx, int, graph->n_edge + nvar);
+	zero = isl_calloc_array(ctx, int, graph->max_row);
 	graph->node[graph->n].zero = zero;
 	graph->n++;
 
@@ -409,21 +543,27 @@ static int extract_node(__isl_take isl_set *set, void *user)
 	return 0;
 }
 
-/* Add a new edge to the graph based on the given map.
- * Edges are first extracted from the validity dependences,
- * from which the edge_table is constructed.
- * Afterwards, the proximity dependences are added.  If a proximity
- * dependence relation happens to be identical to one of the
- * validity dependence relations added before, then we don't create
- * a new edge, but instead mark the original edge as also representing
- * a proximity dependence.
+struct isl_extract_edge_data {
+	enum isl_edge_type type;
+	struct isl_sched_graph *graph;
+};
+
+/* Add a new edge to the graph based on the given map
+ * and add it to data->graph->edge_table[data->type].
+ * If a dependence relation of a given type happens to be identical
+ * to one of the dependence relations of a type that was added before,
+ * then we don't create a new edge, but instead mark the original edge
+ * as also representing a dependence of the current type.
  */
 static int extract_edge(__isl_take isl_map *map, void *user)
 {
 	isl_ctx *ctx = isl_map_get_ctx(map);
-	struct isl_sched_graph *graph = user;
+	struct isl_extract_edge_data *data = user;
+	struct isl_sched_graph *graph = data->graph;
 	struct isl_sched_node *src, *dst;
 	isl_space *dim;
+	struct isl_sched_edge *edge;
+	int is_equal;
 
 	dim = isl_space_domain(isl_map_get_space(map));
 	src = graph_find_node(ctx, graph, dim);
@@ -440,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)
@@ -585,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,
@@ -685,6 +794,8 @@ static int add_intra_validity_constraints(struct isl_sched_graph *graph,
 
 	coef = isl_basic_set_transform_dims(coef, isl_dim_set,
 		    isl_space_dim(dim, isl_dim_set), isl_mat_copy(node->cmap));
+	if (!coef)
+		goto error;
 
 	total = isl_basic_set_total_dim(graph->lp);
 	dim_map = isl_dim_map_alloc(ctx, total);
@@ -701,6 +812,9 @@ static int add_intra_validity_constraints(struct isl_sched_graph *graph,
 	isl_space_free(dim);
 
 	return 0;
+error:
+	isl_space_free(dim);
+	return -1;
 }
 
 /* Add constraints to graph->lp that force validity for the given
@@ -742,6 +856,8 @@ static int add_inter_validity_constraints(struct isl_sched_graph *graph,
 	coef = isl_basic_set_transform_dims(coef, isl_dim_set,
 		    isl_space_dim(dim, isl_dim_set) + src->nvar,
 		    isl_mat_copy(dst->cmap));
+	if (!coef)
+		goto error;
 
 	total = isl_basic_set_total_dim(graph->lp);
 	dim_map = isl_dim_map_alloc(ctx, total);
@@ -771,10 +887,15 @@ static int add_inter_validity_constraints(struct isl_sched_graph *graph,
 			coef->n_eq, coef->n_ineq);
 	graph->lp = isl_basic_set_add_constraints_dim_map(graph->lp,
 							   coef, dim_map);
+	if (!graph->lp)
+		goto error;
 	isl_space_free(dim);
 	edge->end = graph->lp->n_ineq;
 
 	return 0;
+error:
+	isl_space_free(dim);
+	return -1;
 }
 
 /* Add constraints to graph->lp that bound the dependence distance for the given
@@ -824,6 +945,8 @@ static int add_intra_proximity_constraints(struct isl_sched_graph *graph,
 
 	coef = isl_basic_set_transform_dims(coef, isl_dim_set,
 		    isl_space_dim(dim, isl_dim_set), isl_mat_copy(node->cmap));
+	if (!coef)
+		goto error;
 
 	nparam = isl_space_dim(node->dim, isl_dim_param);
 	total = isl_basic_set_total_dim(graph->lp);
@@ -844,6 +967,9 @@ static int add_intra_proximity_constraints(struct isl_sched_graph *graph,
 	isl_space_free(dim);
 
 	return 0;
+error:
+	isl_space_free(dim);
+	return -1;
 }
 
 /* Add constraints to graph->lp that bound the dependence distance for the given
@@ -903,6 +1029,8 @@ static int add_inter_proximity_constraints(struct isl_sched_graph *graph,
 	coef = isl_basic_set_transform_dims(coef, isl_dim_set,
 		    isl_space_dim(dim, isl_dim_set) + src->nvar,
 		    isl_mat_copy(dst->cmap));
+	if (!coef)
+		goto error;
 
 	nparam = isl_space_dim(src->dim, isl_dim_param);
 	total = isl_basic_set_total_dim(graph->lp);
@@ -939,6 +1067,9 @@ static int add_inter_proximity_constraints(struct isl_sched_graph *graph,
 	isl_space_free(dim);
 
 	return 0;
+error:
+	isl_space_free(dim);
+	return -1;
 }
 
 static int add_all_validity_constraints(struct isl_sched_graph *graph)
@@ -1041,7 +1172,8 @@ static int node_update_cmap(struct isl_sched_node *node)
 
 /* Count the number of equality and inequality constraints
  * that will be added for the given map.
- * If once is set, then we count
+ * If carry is set, then we are counting the number of (validity)
+ * constraints that will be added in setup_carry_lp and we count
  * each edge exactly once.  Otherwise, we count as follows
  * validity		-> 1 (>= 0)
  * validity+proximity	-> 2 (>= 0 and upper bound)
@@ -1049,10 +1181,15 @@ static int node_update_cmap(struct isl_sched_node *node)
  */
 static int count_map_constraints(struct isl_sched_graph *graph,
 	struct isl_sched_edge *edge, __isl_take isl_map *map,
-	int *n_eq, int *n_ineq, int once)
+	int *n_eq, int *n_ineq, int carry)
 {
 	isl_basic_set *coef;
-	int f = once ? 1 : edge->proximity ? 2 : 1;
+	int f = carry ? 1 : edge->proximity ? 2 : 1;
+
+	if (carry && !edge->validity) {
+		isl_map_free(map);
+		return 0;
+	}
 
 	if (edge->src == edge->dst)
 		coef = intra_coefficients(graph, map);
@@ -1069,14 +1206,13 @@ static int count_map_constraints(struct isl_sched_graph *graph,
 
 /* Count the number of equality and inequality constraints
  * that will be added to the main lp problem.
- * If once is set, then we count
- * each edge exactly once.  Otherwise, we count as follows
+ * We count as follows
  * validity		-> 1 (>= 0)
  * validity+proximity	-> 2 (>= 0 and upper bound)
  * proximity		-> 2 (lower and upper bound)
  */
 static int count_constraints(struct isl_sched_graph *graph,
-	int *n_eq, int *n_ineq, int once)
+	int *n_eq, int *n_ineq)
 {
 	int i;
 
@@ -1086,13 +1222,50 @@ static int count_constraints(struct isl_sched_graph *graph,
 		isl_map *map = isl_map_copy(edge->map);
 
 		if (count_map_constraints(graph, edge, map,
-					  n_eq, n_ineq, once) < 0)
+					  n_eq, n_ineq, 0) < 0)
 			return -1;
 	}
 
 	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;
+}
+
 /* Construct an ILP problem for finding schedule coefficients
  * that result in non-negative, but small dependence distances
  * over all dependences.
@@ -1138,6 +1311,11 @@ static int setup_lp(isl_ctx *ctx, struct isl_sched_graph *graph,
 	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_space_dim(graph->node[0].dim, isl_dim_param);
@@ -1151,12 +1329,19 @@ static int setup_lp(isl_ctx *ctx, struct isl_sched_graph *graph,
 		total += 1 + 2 * (node->nparam + node->nvar);
 	}
 
-	if (count_constraints(graph, &n_eq, &n_ineq, 0) < 0)
+	if (count_constraints(graph, &n_eq, &n_ineq) < 0)
 		return -1;
 
 	dim = isl_space_set_alloc(ctx, 0, total);
 	isl_basic_set_free(graph->lp);
 	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);
@@ -1203,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)
@@ -1320,6 +1518,9 @@ static int update_schedule(struct isl_sched_graph *graph,
 	if (sol->size == 0)
 		isl_die(sol->ctx, isl_error_internal,
 			"no solution found", goto error);
+	if (graph->n_total_row >= graph->max_row)
+		isl_die(sol->ctx, isl_error_internal,
+			"too many schedule rows", goto error);
 
 	if (check_zero)
 		zero = isl_int_is_zero(sol->el[1]) &&
@@ -1376,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_space *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_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));
+	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_space_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_space_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);
 }
 
@@ -1449,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];
@@ -1462,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;
@@ -1486,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)
@@ -1502,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);
@@ -1558,10 +1761,18 @@ static __isl_give isl_schedule *extract_schedule(struct isl_sched_graph *graph,
 		int r, b;
 		int *band_end, *band_id, *zero;
 
+		sched->node[i].sched =
+			node_extract_schedule_multi_aff(&graph->node[i]);
+		if (!sched->node[i].sched)
+			goto error;
+
+		sched->node[i].n_band = graph->n_band;
+		if (graph->n_band == 0)
+			continue;
+
 		band_end = isl_alloc_array(ctx, int, graph->n_band);
 		band_id = isl_alloc_array(ctx, int, graph->n_band);
 		zero = isl_alloc_array(ctx, int, graph->n_total_row);
-		sched->node[i].sched = node_extract_schedule(&graph->node[i]);
 		sched->node[i].band_end = band_end;
 		sched->node[i].band_id = band_id;
 		sched->node[i].zero = zero;
@@ -1622,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;
@@ -1640,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;
@@ -1677,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;
 
@@ -1729,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;
@@ -1736,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;
@@ -1774,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)
@@ -1826,6 +2063,9 @@ 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
@@ -1839,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;
@@ -1866,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;
@@ -1945,6 +2190,8 @@ static int add_intra_constraints(struct isl_sched_graph *graph,
 	struct isl_sched_node *node = edge->src;
 
 	coef = intra_coefficients(graph, map);
+	if (!coef)
+		return -1;
 
 	dim = isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef)));
 
@@ -1993,6 +2240,8 @@ static int add_inter_constraints(struct isl_sched_graph *graph,
 	struct isl_sched_node *dst = edge->dst;
 
 	coef = inter_coefficients(graph, map);
+	if (!coef)
+		return -1;
 
 	dim = isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef)));
 
@@ -2030,8 +2279,8 @@ static int add_inter_constraints(struct isl_sched_graph *graph,
 	return 0;
 }
 
-/* Add constraints to graph->lp that force all dependence
- * to be respected and attempt to carry it.
+/* Add constraints to graph->lp that force all validity dependences
+ * to be respected and attempt to carry them.
  */
 static int add_all_constraints(struct isl_sched_graph *graph)
 {
@@ -2041,6 +2290,10 @@ static int add_all_constraints(struct isl_sched_graph *graph)
 	pos = 0;
 	for (i = 0; i < graph->n_edge; ++i) {
 		struct isl_sched_edge *edge= &graph->edge[i];
+
+		if (!edge->validity)
+			continue;
+
 		for (j = 0; j < edge->map->n; ++j) {
 			isl_basic_map *bmap;
 			isl_map *map;
@@ -2063,14 +2316,10 @@ static int add_all_constraints(struct isl_sched_graph *graph)
 
 /* Count the number of equality and inequality constraints
  * that will be added to the carry_lp problem.
- * If once is set, then we count
- * each edge exactly once.  Otherwise, we count as follows
- * validity		-> 1 (>= 0)
- * validity+proximity	-> 2 (>= 0 and upper bound)
- * proximity		-> 2 (lower and upper bound)
+ * We count each edge exactly once.
  */
 static int count_all_constraints(struct isl_sched_graph *graph,
-	int *n_eq, int *n_ineq, int once)
+	int *n_eq, int *n_ineq)
 {
 	int i, j;
 
@@ -2085,7 +2334,7 @@ static int count_all_constraints(struct isl_sched_graph *graph,
 			map = isl_map_from_basic_map(bmap);
 
 			if (count_map_constraints(graph, edge, map,
-						  n_eq, n_ineq, once) < 0)
+						  n_eq, n_ineq, 1) < 0)
 				    return -1;
 		}
 	}
@@ -2122,7 +2371,7 @@ static int count_all_constraints(struct isl_sched_graph *graph,
  *		- positive and negative parts of c_i_n (if parametric)
  *		- positive and negative parts of c_i_x
  *
- * The constraints are those from the edges plus three equalities
+ * The constraints are those from the (validity) edges plus three equalities
  * to express the sums and n_edge inequalities to express e_i <= 1.
  */
 static int setup_carry_lp(isl_ctx *ctx, struct isl_sched_graph *graph)
@@ -2145,7 +2394,7 @@ static int setup_carry_lp(isl_ctx *ctx, struct isl_sched_graph *graph)
 		total += 1 + 2 * (node->nparam + node->nvar);
 	}
 
-	if (count_all_constraints(graph, &n_eq, &n_ineq, 1) < 0)
+	if (count_all_constraints(graph, &n_eq, &n_ineq) < 0)
 		return -1;
 
 	dim = isl_space_set_alloc(ctx, 0, total);
@@ -2204,40 +2453,49 @@ static int setup_carry_lp(isl_ctx *ctx, struct isl_sched_graph *graph)
 	return 0;
 }
 
-/* If the schedule_split_parallel option is set and if the linear
- * parts of the scheduling rows for all nodes in the graphs are the same,
- * then split off the constant term from the linear part.
+/* 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 simplified.
+ * the linear part is reduced.
  */
-static int split_parallel(isl_ctx *ctx, struct isl_sched_graph *graph)
+static int split_scaled(isl_ctx *ctx, struct isl_sched_graph *graph)
 {
 	int i;
-	int equal = 1;
-	int row, cols;
-	struct isl_sched_node *node0;
+	int row;
+	isl_int gcd, gcd_i;
 
-	if (!ctx->opt->schedule_split_parallel)
+	if (!ctx->opt->schedule_split_scaled)
 		return 0;
 	if (graph->n <= 1)
 		return 0;
 
-	node0 = &graph->node[0];
-	row = isl_mat_rows(node0->sched) - 1;
-	cols = isl_mat_cols(node0->sched);
-	for (i = 1; i < graph->n; ++i) {
+	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);
 
-		if (!isl_seq_eq(node0->sched->row[row] + 1,
-				node->sched->row[row] + 1, cols - 1))
-			return 0;
-		if (equal &&
-		    isl_int_ne(node0->sched->row[row][0],
-			       node->sched->row[row][0]))
-			equal = 0;
+		isl_seq_gcd(node->sched->row[row] + 1, cols - 1, &gcd_i);
+		isl_int_gcd(gcd, gcd, gcd_i);
 	}
-	if (equal)
+
+	isl_int_clear(gcd_i);
+
+	if (isl_int_cmp_si(gcd, 1) <= 0) {
+		isl_int_clear(gcd);
 		return 0;
+	}
 
 	next_band(graph);
 
@@ -2248,23 +2506,83 @@ static int split_parallel(isl_ctx *ctx, struct isl_sched_graph *graph)
 		node->sched_map = NULL;
 		node->sched = isl_mat_add_zero_rows(node->sched, 1);
 		if (!node->sched)
-			return -1;
-		isl_int_set(node->sched->row[row + 1][0],
-			    node->sched->row[row][0]);
-		isl_int_set_si(node->sched->row[row][0], 0);
-		node->sched = isl_mat_normalize_row(node->sched, row);
+			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)
-			return -1;
+			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)
 {
@@ -2291,21 +2609,79 @@ static int carry_dependences(isl_ctx *ctx, struct isl_sched_graph *graph)
 			"error in schedule construction", return -1);
 	}
 
+	isl_int_divexact(sol->el[1], sol->el[1], sol->el[0]);
 	if (isl_int_cmp_si(sol->el[1], n_edge) >= 0) {
 		isl_vec_free(sol);
 		isl_die(ctx, isl_error_unknown,
 			"unable to carry dependences", return -1);
 	}
 
+	if (is_any_trivial(graph, sol)) {
+		isl_vec_free(sol);
+		if (graph->scc > 1)
+			return compute_component_schedule(ctx, graph);
+		isl_die(ctx, isl_error_unknown,
+			"unable to construct non-trivial solution", return -1);
+	}
+
 	if (update_schedule(graph, sol, 0, 0) < 0)
 		return -1;
 
-	if (split_parallel(ctx, graph) < 0)
+	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
@@ -2318,6 +2694,10 @@ 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.
  *
@@ -2330,13 +2710,17 @@ static int compute_schedule_wcc(isl_ctx *ctx, struct isl_sched_graph *graph)
 {
 	int force_zero = 0;
 
-	if (detect_sccs(graph) < 0)
+	if (detect_sccs(ctx, graph) < 0)
+		return -1;
+	if (sort_sccs(graph) < 0)
 		return -1;
-	sort_sccs(graph);
 
 	if (compute_maxvar(graph) < 0)
 		return -1;
 
+	if (need_feautrier_step(ctx, graph))
+		return compute_schedule_wcc_feautrier(ctx, graph);
+
 	if (ctx->opt->schedule_outer_zero_distance)
 		force_zero = 1;
 
@@ -2372,8 +2756,41 @@ 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
@@ -2387,6 +2804,11 @@ 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;
@@ -2400,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;
@@ -2423,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);
@@ -2437,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,
@@ -2449,6 +2884,7 @@ __isl_give isl_schedule *isl_union_set_compute_schedule(
 	isl_space *dim;
 	struct isl_sched_graph graph = { 0 };
 	isl_schedule *sched;
+	struct isl_extract_edge_data data;
 
 	domain = isl_union_set_align_params(domain,
 					    isl_union_map_get_space(validity));
@@ -2467,18 +2903,25 @@ __isl_give isl_schedule *isl_union_set_compute_schedule(
 	if (graph_alloc(ctx, &graph, graph.n,
 	    isl_union_map_n_map(validity) + isl_union_map_n_map(proximity)) < 0)
 		goto error;
+	if (compute_max_row(&graph, domain) < 0)
+		goto error;
 	graph.root = 1;
 	graph.n = 0;
 	if (isl_union_set_foreach_set(domain, &extract_node, &graph) < 0)
 		goto error;
 	if (graph_init_table(ctx, &graph) < 0)
 		goto error;
-	graph.n_edge = 0;
-	if (isl_union_map_foreach_map(validity, &extract_edge, &graph) < 0)
+	graph.max_edge[isl_edge_validity] = isl_union_map_n_map(validity);
+	graph.max_edge[isl_edge_proximity] = isl_union_map_n_map(proximity);
+	if (graph_init_edge_tables(ctx, &graph) < 0)
 		goto error;
-	if (graph_init_edge_table(ctx, &graph) < 0)
+	graph.n_edge = 0;
+	data.graph = &graph;
+	data.type = isl_edge_validity;
+	if (isl_union_map_foreach_map(validity, &extract_edge, &data) < 0)
 		goto error;
-	if (isl_union_map_foreach_map(proximity, &extract_edge, &graph) < 0)
+	data.type = isl_edge_proximity;
+	if (isl_union_map_foreach_map(proximity, &extract_edge, &data) < 0)
 		goto error;
 
 	if (compute_schedule(ctx, &graph) < 0)
@@ -2511,7 +2954,7 @@ void *isl_schedule_free(__isl_take isl_schedule *sched)
 		return NULL;
 
 	for (i = 0; i < sched->n; ++i) {
-		isl_map_free(sched->node[i].sched);
+		isl_multi_aff_free(sched->node[i].sched);
 		free(sched->node[i].band_end);
 		free(sched->node[i].band_id);
 		free(sched->node[i].zero);
@@ -2527,6 +2970,84 @@ isl_ctx *isl_schedule_get_ctx(__isl_keep isl_schedule *schedule)
 	return schedule ? isl_space_get_ctx(schedule->dim) : NULL;
 }
 
+/* Set max_out to the maximal number of output dimensions over
+ * all maps.
+ */
+static int update_max_out(__isl_take isl_map *map, void *user)
+{
+	int *max_out = user;
+	int n_out = isl_map_dim(map, isl_dim_out);
+
+	if (n_out > *max_out)
+		*max_out = n_out;
+
+	isl_map_free(map);
+	return 0;
+}
+
+/* Internal data structure for map_pad_range.
+ *
+ * "max_out" is the maximal schedule dimension.
+ * "res" collects the results.
+ */
+struct isl_pad_schedule_map_data {
+	int max_out;
+	isl_union_map *res;
+};
+
+/* Pad the range of the given map with zeros to data->max_out and
+ * then add the result to data->res.
+ */
+static int map_pad_range(__isl_take isl_map *map, void *user)
+{
+	struct isl_pad_schedule_map_data *data = user;
+	int i;
+	int n_out = isl_map_dim(map, isl_dim_out);
+
+	map = isl_map_add_dims(map, isl_dim_out, data->max_out - n_out);
+	for (i = n_out; i < data->max_out; ++i)
+		map = isl_map_fix_si(map, isl_dim_out, i, 0);
+
+	data->res = isl_union_map_add_map(data->res, map);
+	if (!data->res)
+		return -1;
+
+	return 0;
+}
+
+/* Pad the ranges of the maps in the union map with zeros such they all have
+ * the same dimension.
+ */
+static __isl_give isl_union_map *pad_schedule_map(
+	__isl_take isl_union_map *umap)
+{
+	struct isl_pad_schedule_map_data data;
+
+	if (!umap)
+		return NULL;
+	if (isl_union_map_n_map(umap) <= 1)
+		return umap;
+
+	data.max_out = 0;
+	if (isl_union_map_foreach_map(umap, &update_max_out, &data.max_out) < 0)
+		return isl_union_map_free(umap);
+
+	data.res = isl_union_map_empty(isl_union_map_get_space(umap));
+	if (isl_union_map_foreach_map(umap, &map_pad_range, &data) < 0)
+		data.res = isl_union_map_free(data.res);
+
+	isl_union_map_free(umap);
+	return data.res;
+}
+
+/* Return an isl_union_map of the schedule.  If we have already constructed
+ * a band forest, then this band forest may have been modified so we need
+ * to extract the isl_union_map from the forest rather than from
+ * the originally computed schedule.  This reconstructed schedule map
+ * then needs to be padded with zeros to unify the schedule space
+ * since the result of isl_band_list_get_suffix_schedule may not have
+ * a unified schedule space.
+ */
 __isl_give isl_union_map *isl_schedule_get_map(__isl_keep isl_schedule *sched)
 {
 	int i;
@@ -2535,10 +3056,18 @@ __isl_give isl_union_map *isl_schedule_get_map(__isl_keep isl_schedule *sched)
 	if (!sched)
 		return NULL;
 
+	if (sched->band_forest) {
+		umap = isl_band_list_get_suffix_schedule(sched->band_forest);
+		return pad_schedule_map(umap);
+	}
+
 	umap = isl_union_map_empty(isl_space_copy(sched->dim));
-	for (i = 0; i < sched->n; ++i)
-		umap = isl_union_map_add_map(umap,
-					    isl_map_copy(sched->node[i].sched));
+	for (i = 0; i < sched->n; ++i) {
+		isl_multi_aff *ma;
+
+		ma = isl_multi_aff_copy(sched->node[i].sched);
+		umap = isl_union_map_add_map(umap, isl_map_from_multi_aff(ma));
+	}
 
 	return umap;
 }
@@ -2565,11 +3094,10 @@ static __isl_give isl_band *construct_band(__isl_keep isl_schedule *schedule,
 	isl_band *band;
 	unsigned start, end;
 
-	band = isl_calloc_type(ctx, isl_band);
+	band = isl_band_alloc(ctx);
 	if (!band)
 		return NULL;
 
-	band->ref = 1;
 	band->schedule = schedule;
 	band->parent = parent;
 
@@ -2604,22 +3132,24 @@ static __isl_give isl_band *construct_band(__isl_keep isl_schedule *schedule,
 	for (j = 0; j < band->n; ++j)
 		band->zero[j] = schedule->node[i].zero[start + j];
 
-	band->map = isl_union_map_empty(isl_space_copy(schedule->dim));
+	band->pma = isl_union_pw_multi_aff_empty(isl_space_copy(schedule->dim));
 	for (i = 0; i < schedule->n; ++i) {
-		isl_map *map;
+		isl_multi_aff *ma;
+		isl_pw_multi_aff *pma;
 		unsigned n_out;
 
 		if (!active[i])
 			continue;
 
-		map = isl_map_copy(schedule->node[i].sched);
-		n_out = isl_map_dim(map, isl_dim_out);
-		map = isl_map_project_out(map, isl_dim_out, end, n_out - end);
-		map = isl_map_project_out(map, isl_dim_out, 0, start);
-		band->map = isl_union_map_union(band->map,
-						isl_union_map_from_map(map));
+		ma = isl_multi_aff_copy(schedule->node[i].sched);
+		n_out = isl_multi_aff_dim(ma, isl_dim_out);
+		ma = isl_multi_aff_drop_dims(ma, isl_dim_out, end, n_out - end);
+		ma = isl_multi_aff_drop_dims(ma, isl_dim_out, 0, start);
+		pma = isl_pw_multi_aff_from_multi_aff(ma);
+		band->pma = isl_union_pw_multi_aff_add_pw_multi_aff(band->pma,
+								    pma);
 	}
-	if (!band->map)
+	if (!band->pma)
 		goto error;
 
 	return band;
@@ -2752,6 +3282,24 @@ __isl_give isl_band_list *isl_schedule_get_band_forest(
 	return isl_band_list_dup(schedule->band_forest);
 }
 
+/* Call "fn" on each band in the schedule in depth-first post-order.
+ */
+int isl_schedule_foreach_band(__isl_keep isl_schedule *sched,
+	int (*fn)(__isl_keep isl_band *band, void *user), void *user)
+{
+	int r;
+	isl_band_list *forest;
+
+	if (!sched)
+		return -1;
+
+	forest = isl_schedule_get_band_forest(sched);
+	r = isl_band_list_foreach_band(forest, fn, user);
+	isl_band_list_free(forest);
+
+	return r;
+}
+
 static __isl_give isl_printer *print_band_list(__isl_take isl_printer *p,
 	__isl_keep isl_band_list *list);
 
@@ -2761,7 +3309,7 @@ static __isl_give isl_printer *print_band(__isl_take isl_printer *p,
 	isl_band_list *children;
 
 	p = isl_printer_start_line(p);
-	p = isl_printer_print_union_map(p, band->map);
+	p = isl_printer_print_union_pw_multi_aff(p, band->pma);
 	p = isl_printer_end_line(p);
 
 	if (!isl_band_has_children(band))