From bde2ea2094179a3fc97b4fb9ddf2b17691f58622 Mon Sep 17 00:00:00 2001 From: Sven Verdoolaege Date: Thu, 1 Mar 2012 17:27:17 +0100 Subject: [PATCH] extract common implementation of Tarjan's algorithm We had two nearly identical implementations in isl_schedule.c and isl_transitive_closure.c. Signed-off-by: Sven Verdoolaege --- Makefile.am | 2 + isl_schedule.c | 152 +++++++++++--------------------- isl_tarjan.c | 132 ++++++++++++++++++++++++++++ isl_tarjan.h | 40 +++++++++ isl_transitive_closure.c | 224 ++++++++++------------------------------------- 5 files changed, 269 insertions(+), 281 deletions(-) create mode 100644 isl_tarjan.c create mode 100644 isl_tarjan.h diff --git a/Makefile.am b/Makefile.am index e1f26b3..ec76af6 100644 --- a/Makefile.am +++ b/Makefile.am @@ -122,6 +122,8 @@ libisl_la_SOURCES = \ isl_tab.c \ isl_tab.h \ isl_tab_pip.c \ + isl_tarjan.c \ + isl_tarjan.h \ isl_transitive_closure.c \ isl_union_map.c \ isl_union_map_private.h \ diff --git a/isl_schedule.c b/isl_schedule.c index ea53db8..8a6cb80 100644 --- a/isl_schedule.c +++ b/isl_schedule.c @@ -26,6 +26,7 @@ #include #include #include +#include /* * The scheduling algorithm implemented in this file was inspired by @@ -62,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; @@ -83,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) @@ -174,11 +165,7 @@ enum isl_edge_type { * 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; @@ -211,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. @@ -440,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) @@ -481,7 +462,6 @@ 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); 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); @@ -629,92 +609,60 @@ static int extract_edge(__isl_take isl_map *map, void *user) 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 (if weak is not set). - * If weak is set, then check if there is any dependence from src to dst. +/* 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, int weak) +static int node_follows_weak(int i, int j, void *user) { - if (weak) - return graph_has_any_edge(graph, src, dst); - else - return graph_has_validity_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]); +} + +/* Check whether there is a validity dependence from node[j] to node[i], + * forcing node[i] to follow node[j]. + */ +static int node_follows_strong(int i, int j, void *user) +{ + struct isl_sched_graph *graph = user; + + return graph_has_validity_edge(graph, &graph->node[j], &graph->node[i]); } -/* Perform Tarjan's algorithm for computing the strongly connected components +/* 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_sccs_tarjan(struct isl_sched_graph *g, int i, int weak) +static int detect_ccs(isl_ctx *ctx, struct isl_sched_graph *graph, int weak) { - 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; + int i, n; + struct isl_tarjan_graph *g = NULL; - for (j = g->n - 1; j >= 0; --j) { - int f; + g = isl_tarjan_graph_init(ctx, graph->n, + weak ? &node_follows_weak : &node_follows_strong, graph); + if (!g) + return -1; - 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], weak); - if (f < 0) - return -1; - if (!f && weak) { - f = node_follows(g, &g->node[j], &g->node[i], weak); - if (f < 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; } - if (!f) - continue; - if (g->node[j].index < 0) { - detect_sccs_tarjan(g, j, weak); - if (g->node[j].min_index < g->node[i].min_index) - g->node[i].min_index = g->node[j].min_index; - } else if (g->node[j].index < g->node[i].min_index) - g->node[i].min_index = g->node[j].index; + ++i; + graph->scc++; } - 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++; - - return 0; -} - -static int detect_ccs(struct isl_sched_graph *graph, int weak) -{ - int i; - - graph->index = 0; - graph->sp = 0; - graph->scc = 0; - for (i = graph->n - 1; i >= 0; --i) - graph->node[i].index = -1; - - for (i = graph->n - 1; i >= 0; --i) { - if (graph->node[i].index >= 0) - continue; - if (detect_sccs_tarjan(graph, i, weak) < 0) - return -1; - } + isl_tarjan_graph_free(g); return 0; } @@ -722,17 +670,17 @@ static int detect_ccs(struct isl_sched_graph *graph, int weak) /* 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, 0); + 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, 1); + return detect_ccs(ctx, graph, 1); } static int cmp_scc(const void *a, const void *b, void *data) @@ -1728,7 +1676,7 @@ 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; for (i = 0; i < graph->n; ++i) { @@ -2650,7 +2598,7 @@ 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; @@ -2789,10 +2737,10 @@ static int compute_component_schedule(isl_ctx *ctx, 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; } diff --git a/isl_tarjan.c b/isl_tarjan.c new file mode 100644 index 0000000..847b83b --- /dev/null +++ b/isl_tarjan.c @@ -0,0 +1,132 @@ +/* + * Copyright 2010-2011 INRIA Saclay + * Copyright 2012 Ecole Normale Superieure + * + * Use of this software is governed by the GNU LGPLv2.1 license + * + * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France, + * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod, + * 91893 Orsay, France + * and Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France + */ + +#include +#include +#include + +void isl_tarjan_graph_free(struct isl_tarjan_graph *g) +{ + if (!g) + return; + free(g->node); + free(g->stack); + free(g->order); + free(g); +} + +static struct isl_tarjan_graph *isl_tarjan_graph_alloc(isl_ctx *ctx, int len) +{ + struct isl_tarjan_graph *g; + int i; + + g = isl_calloc_type(ctx, struct isl_tarjan_graph); + if (!g) + return NULL; + g->len = len; + g->node = isl_alloc_array(ctx, struct isl_tarjan_node, len); + if (!g->node) + goto error; + for (i = 0; i < len; ++i) + g->node[i].index = -1; + g->stack = isl_alloc_array(ctx, int, len); + if (!g->stack) + goto error; + g->order = isl_alloc_array(ctx, int, 2 * len); + if (!g->order) + goto error; + + g->sp = 0; + g->index = 0; + g->op = 0; + + return g; +error: + isl_tarjan_graph_free(g); + return NULL; +} + +/* Perform Tarjan's algorithm for computing the strongly connected components + * in the graph with g->len nodes and with edges defined by "follows". + */ +static int isl_tarjan_components(struct isl_tarjan_graph *g, int i, + int (*follows)(int i, int j, void *user), 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->len - 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 = follows(i, j, user); + if (f < 0) + return -1; + if (!f) + continue; + + if (g->node[j].index < 0) { + isl_tarjan_components(g, j, follows, user); + 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->order[g->op++] = j; + } while (j != i); + g->order[g->op++] = -1; + + return 0; +} + +/* Decompose the graph with "len" nodes and edges defined by "follows" + * into strongly connected components. + */ +struct isl_tarjan_graph *isl_tarjan_graph_init(isl_ctx *ctx, int len, + int (*follows)(int i, int j, void *user), void *user) +{ + int i; + struct isl_tarjan_graph *g = NULL; + + g = isl_tarjan_graph_alloc(ctx, len); + if (!g) + return NULL; + for (i = len - 1; i >= 0; --i) { + if (g->node[i].index >= 0) + continue; + if (isl_tarjan_components(g, i, follows, user) < 0) + goto error; + } + + return g; +error: + isl_tarjan_graph_free(g); + return NULL; +} diff --git a/isl_tarjan.h b/isl_tarjan.h new file mode 100644 index 0000000..0767d09 --- /dev/null +++ b/isl_tarjan.h @@ -0,0 +1,40 @@ +#ifndef ISL_TARJAN_H +#define ISL_TARJAN_H + +/* Structure for representing the nodes in the graph being traversed + * using Tarjan's algorithm. + * 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_tarjan_node { + int index; + int min_index; + int on_stack; +}; + +/* Structure for representing the graph being traversed + * using Tarjan's algorithm. + * len is the number of nodes + * node is an array of nodes + * 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 + * order contains the elements of the components separated by -1 + * op represents the current position in order + */ +struct isl_tarjan_graph { + int len; + struct isl_tarjan_node *node; + int *stack; + int sp; + int index; + int *order; + int op; +}; + +struct isl_tarjan_graph *isl_tarjan_graph_init(isl_ctx *ctx, int len, + int (*follows)(int i, int j, void *user), void *user); +void isl_tarjan_graph_free(struct isl_tarjan_graph *g); + +#endif diff --git a/isl_transitive_closure.c b/isl_transitive_closure.c index 59cb8bd..c92b245 100644 --- a/isl_transitive_closure.c +++ b/isl_transitive_closure.c @@ -17,6 +17,7 @@ #include #include #include +#include int isl_map_is_transitively_closed(__isl_keep isl_map *map) { @@ -1720,87 +1721,21 @@ error: return NULL; } -/* Structure for representing the nodes in the graph being traversed - * using Tarjan's algorithm. - * 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 basic_map_sort_node { - int index; - int min_index; - int on_stack; -}; -/* Structure for representing the graph being traversed - * using Tarjan's algorithm. - * len is the number of nodes - * node is an array of nodes - * 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 - * order contains the elements of the components separated by -1 - * op represents the current position in order +/* Structure for representing the nodes of the graph of which + * strongly connected components are being computed. * + * list contains the actual nodes * check_closed is set if we may have used the fact that * a pair of basic maps can be interchanged */ -struct basic_map_sort { - int len; - struct basic_map_sort_node *node; - int *stack; - int sp; - int index; - int *order; - int op; +struct isl_tc_follows_data { + isl_basic_map **list; int check_closed; }; -static void basic_map_sort_free(struct basic_map_sort *s) -{ - if (!s) - return; - free(s->node); - free(s->stack); - free(s->order); - free(s); -} - -static struct basic_map_sort *basic_map_sort_alloc(struct isl_ctx *ctx, int len) -{ - struct basic_map_sort *s; - int i; - - s = isl_calloc_type(ctx, struct basic_map_sort); - if (!s) - return NULL; - s->len = len; - s->node = isl_alloc_array(ctx, struct basic_map_sort_node, len); - if (!s->node) - goto error; - for (i = 0; i < len; ++i) - s->node[i].index = -1; - s->stack = isl_alloc_array(ctx, int, len); - if (!s->stack) - goto error; - s->order = isl_alloc_array(ctx, int, 2 * len); - if (!s->order) - goto error; - - s->sp = 0; - s->index = 0; - s->op = 0; - - s->check_closed = 0; - - return s; -error: - basic_map_sort_free(s); - return NULL; -} - /* Check whether in the computation of the transitive closure - * "bmap1" (R_1) should follow (or be part of the same component as) - * "bmap2" (R_2). + * "list[i]" (R_1) should follow (or be part of the same component as) + * "list[j]" (R_2). * * That is check whether * @@ -1816,20 +1751,21 @@ error: * *check_closed is set if the subset relation holds while * R_1 \circ R_2 is not empty. */ -static int basic_map_follows(__isl_keep isl_basic_map *bmap1, - __isl_keep isl_basic_map *bmap2, int *check_closed) +static int basic_map_follows(int i, int j, void *user) { + struct isl_tc_follows_data *data = user; struct isl_map *map12 = NULL; struct isl_map *map21 = NULL; int subset; - if (!isl_space_tuple_match(bmap1->dim, isl_dim_in, bmap2->dim, isl_dim_out)) + if (!isl_space_tuple_match(data->list[i]->dim, isl_dim_in, + data->list[j]->dim, isl_dim_out)) return 0; map21 = isl_map_from_basic_map( isl_basic_map_apply_range( - isl_basic_map_copy(bmap2), - isl_basic_map_copy(bmap1))); + isl_basic_map_copy(data->list[j]), + isl_basic_map_copy(data->list[i]))); subset = isl_map_is_empty(map21); if (subset < 0) goto error; @@ -1838,16 +1774,18 @@ static int basic_map_follows(__isl_keep isl_basic_map *bmap1, return 0; } - if (!isl_space_tuple_match(bmap1->dim, isl_dim_in, bmap1->dim, isl_dim_out) || - !isl_space_tuple_match(bmap2->dim, isl_dim_in, bmap2->dim, isl_dim_out)) { + if (!isl_space_tuple_match(data->list[i]->dim, isl_dim_in, + data->list[i]->dim, isl_dim_out) || + !isl_space_tuple_match(data->list[j]->dim, isl_dim_in, + data->list[j]->dim, isl_dim_out)) { isl_map_free(map21); return 1; } map12 = isl_map_from_basic_map( isl_basic_map_apply_range( - isl_basic_map_copy(bmap1), - isl_basic_map_copy(bmap2))); + isl_basic_map_copy(data->list[i]), + isl_basic_map_copy(data->list[j]))); subset = isl_map_is_subset(map21, map12); @@ -1855,7 +1793,7 @@ static int basic_map_follows(__isl_keep isl_basic_map *bmap1, isl_map_free(map21); if (subset) - *check_closed = 1; + data->check_closed = 1; return subset < 0 ? -1 : !subset; error: @@ -1863,84 +1801,6 @@ error: return -1; } -/* Perform Tarjan's algorithm for computing the strongly connected components - * in the graph with the disjuncts of "map" as vertices and with an - * edge between any pair of disjuncts such that the first has - * to be applied after the second. - */ -static int power_components_tarjan(struct basic_map_sort *s, - __isl_keep isl_basic_map **list, int i) -{ - int j; - - s->node[i].index = s->index; - s->node[i].min_index = s->index; - s->node[i].on_stack = 1; - s->index++; - s->stack[s->sp++] = i; - - for (j = s->len - 1; j >= 0; --j) { - int f; - - if (j == i) - continue; - if (s->node[j].index >= 0 && - (!s->node[j].on_stack || - s->node[j].index > s->node[i].min_index)) - continue; - - f = basic_map_follows(list[i], list[j], &s->check_closed); - if (f < 0) - return -1; - if (!f) - continue; - - if (s->node[j].index < 0) { - power_components_tarjan(s, list, j); - if (s->node[j].min_index < s->node[i].min_index) - s->node[i].min_index = s->node[j].min_index; - } else if (s->node[j].index < s->node[i].min_index) - s->node[i].min_index = s->node[j].index; - } - - if (s->node[i].index != s->node[i].min_index) - return 0; - - do { - j = s->stack[--s->sp]; - s->node[j].on_stack = 0; - s->order[s->op++] = j; - } while (j != i); - s->order[s->op++] = -1; - - return 0; -} - -/* Decompose the "len" basic relations in "list" into strongly connected - * components. - */ -static struct basic_map_sort *basic_map_sort_init(isl_ctx *ctx, int len, - __isl_keep isl_basic_map **list) -{ - int i; - struct basic_map_sort *s = NULL; - - s = basic_map_sort_alloc(ctx, len); - if (!s) - return NULL; - for (i = len - 1; i >= 0; --i) { - if (s->node[i].index >= 0) - continue; - if (power_components_tarjan(s, list, i) < 0) - goto error; - } - - return s; -error: - basic_map_sort_free(s); - return NULL; -} - /* Given a union of basic maps R = \cup_i R_i \subseteq D \times D * and a dimension specification (Z^{n+1} -> Z^{n+1}), * construct a map that is an overapproximation of the map @@ -1979,7 +1839,8 @@ static __isl_give isl_map *construct_power_components(__isl_take isl_space *dim, { int i, n, c; struct isl_map *path = NULL; - struct basic_map_sort *s = NULL; + struct isl_tc_follows_data data; + struct isl_tarjan_graph *g = NULL; int *orig_exact; int local_exact; @@ -1988,12 +1849,14 @@ static __isl_give isl_map *construct_power_components(__isl_take isl_space *dim, if (map->n <= 1) return floyd_warshall(dim, map, exact, project); - s = basic_map_sort_init(map->ctx, map->n, map->p); - if (!s) + data.list = map->p; + data.check_closed = 0; + g = isl_tarjan_graph_init(map->ctx, map->n, &basic_map_follows, &data); + if (!g) goto error; orig_exact = exact; - if (s->check_closed && !exact) + if (data.check_closed && !exact) exact = &local_exact; c = 0; @@ -2008,9 +1871,9 @@ static __isl_give isl_map *construct_power_components(__isl_take isl_space *dim, struct isl_map *comp; isl_map *path_comp, *path_comb; comp = isl_map_alloc_space(isl_map_get_space(map), n, 0); - while (s->order[i] != -1) { + while (g->order[i] != -1) { comp = isl_map_add_basic_map(comp, - isl_basic_map_copy(map->p[s->order[i]])); + isl_basic_map_copy(map->p[g->order[i]])); --n; ++i; } @@ -2026,25 +1889,25 @@ static __isl_give isl_map *construct_power_components(__isl_take isl_space *dim, ++c; } - if (c > 1 && s->check_closed && !*exact) { + if (c > 1 && data.check_closed && !*exact) { int closed; closed = isl_map_is_transitively_closed(path); if (closed < 0) goto error; if (!closed) { - basic_map_sort_free(s); + isl_tarjan_graph_free(g); isl_map_free(path); return floyd_warshall(dim, map, orig_exact, project); } } - basic_map_sort_free(s); + isl_tarjan_graph_free(g); isl_space_free(dim); return path; error: - basic_map_sort_free(s); + isl_tarjan_graph_free(g); isl_space_free(dim); isl_map_free(path); return NULL; @@ -2908,7 +2771,8 @@ static __isl_give isl_union_map *union_components( isl_basic_map **list; isl_basic_map **next; isl_union_map *path = NULL; - struct basic_map_sort *s = NULL; + struct isl_tc_follows_data data; + struct isl_tarjan_graph *g = NULL; int c, l; int recheck = 0; @@ -2928,8 +2792,10 @@ static __isl_give isl_union_map *union_components( if (isl_union_map_foreach_map(umap, collect_basic_map, &next) < 0) goto error; - s = basic_map_sort_init(ctx, n, list); - if (!s) + data.list = list; + data.check_closed = 0; + g = isl_tarjan_graph_init(ctx, n, &basic_map_follows, &data); + if (!g) goto error; c = 0; @@ -2940,10 +2806,10 @@ static __isl_give isl_union_map *union_components( isl_union_map *comp; isl_union_map *path_comp, *path_comb; comp = isl_union_map_empty(isl_union_map_get_space(umap)); - while (s->order[i] != -1) { + while (g->order[i] != -1) { comp = isl_union_map_add_map(comp, isl_map_from_basic_map( - isl_basic_map_copy(list[s->order[i]]))); + isl_basic_map_copy(list[g->order[i]]))); --l; ++i; } @@ -2956,7 +2822,7 @@ static __isl_give isl_union_map *union_components( ++c; } - if (c > 1 && s->check_closed && !*exact) { + if (c > 1 && data.check_closed && !*exact) { int closed; closed = isl_union_map_is_transitively_closed(path); @@ -2965,7 +2831,7 @@ static __isl_give isl_union_map *union_components( recheck = !closed; } - basic_map_sort_free(s); + isl_tarjan_graph_free(g); for (i = 0; i < n; ++i) isl_basic_map_free(list[i]); @@ -2980,7 +2846,7 @@ static __isl_give isl_union_map *union_components( return path; error: - basic_map_sort_free(s); + isl_tarjan_graph_free(g); if (list) { for (i = 0; i < n; ++i) isl_basic_map_free(list[i]); -- 2.7.4