1*a749e09eSMichael Kruse /*
2*a749e09eSMichael Kruse * Copyright 2021 Sven Verdoolaege
3*a749e09eSMichael Kruse *
4*a749e09eSMichael Kruse * Use of this software is governed by the MIT license
5*a749e09eSMichael Kruse *
6*a749e09eSMichael Kruse * Written by Sven Verdoolaege
7*a749e09eSMichael Kruse */
8*a749e09eSMichael Kruse
9*a749e09eSMichael Kruse #include <stdio.h>
10*a749e09eSMichael Kruse
11*a749e09eSMichael Kruse #include <isl/ctx.h>
12*a749e09eSMichael Kruse #include <isl/schedule_node.h>
13*a749e09eSMichael Kruse #include <isl/union_set.h>
14*a749e09eSMichael Kruse
15*a749e09eSMichael Kruse #include "isl_hash_private.h"
16*a749e09eSMichael Kruse #include "isl_scheduler_scc.h"
17*a749e09eSMichael Kruse #include "isl_sort.h"
18*a749e09eSMichael Kruse
19*a749e09eSMichael Kruse /* Internal data structure for ordering the SCCs of "graph",
20*a749e09eSMichael Kruse * where each SCC i consists of the single cluster determined
21*a749e09eSMichael Kruse * by c->scc_cluster[i]. The nodes in this cluster all have
22*a749e09eSMichael Kruse * their "scc" field set to i.
23*a749e09eSMichael Kruse *
24*a749e09eSMichael Kruse * "graph" is the original schedule graph.
25*a749e09eSMichael Kruse * "c" contains the clustering information.
26*a749e09eSMichael Kruse *
27*a749e09eSMichael Kruse * "n" is the number of SCCs in the isl_scc_graph, which may be
28*a749e09eSMichael Kruse * a subset of those in "graph".
29*a749e09eSMichael Kruse * "graph_scc" maps the local index of an SCC in this isl_scc_graph
30*a749e09eSMichael Kruse * to the corresponding index in "graph", i.e, the index of c->scc_cluster.
31*a749e09eSMichael Kruse * The entries of "graph_scc" are kept in topological order.
32*a749e09eSMichael Kruse *
33*a749e09eSMichael Kruse * "component" contains the component to which an SCC belongs,
34*a749e09eSMichael Kruse * where the component is represented by the index of the first SCC
35*a749e09eSMichael Kruse * in the component.
36*a749e09eSMichael Kruse * The index of this first SCC is always smaller than or equal
37*a749e09eSMichael Kruse * to the index of the SCC itself.
38*a749e09eSMichael Kruse * This field is initialized by isl_scc_graph_init_component and
39*a749e09eSMichael Kruse * used by detect_components.
40*a749e09eSMichael Kruse * During construction, "component" may also contain the index
41*a749e09eSMichael Kruse * of some other SCC in the component, but then it is necessarily
42*a749e09eSMichael Kruse * smaller than the index of the current SCC and the first SCC
43*a749e09eSMichael Kruse * can be reached by recursively looking up "component".
44*a749e09eSMichael Kruse * "size" contains the number of elements in the components
45*a749e09eSMichael Kruse * indexed by a component sequence number.
46*a749e09eSMichael Kruse *
47*a749e09eSMichael Kruse * "pos" is used locally inside isl_scc_graph_sort_components
48*a749e09eSMichael Kruse * to store the position of the next SCC within a component.
49*a749e09eSMichael Kruse * It is also used inside isl_scc_graph_sub to map
50*a749e09eSMichael Kruse * the position in the original graph to the position in the subgraph.
51*a749e09eSMichael Kruse *
52*a749e09eSMichael Kruse * "sorted" contains the (possibly) reordered local indices,
53*a749e09eSMichael Kruse * sorted per component. Within each component, the original
54*a749e09eSMichael Kruse * topological order is preserved.
55*a749e09eSMichael Kruse *
56*a749e09eSMichael Kruse * "edge_table" contains "n" edge tables, one for each SCC
57*a749e09eSMichael Kruse * in this isl_scc_graph. Each table contains the local indices
58*a749e09eSMichael Kruse * of the SCCs that depend on this SCC. These local indices
59*a749e09eSMichael Kruse * are encoded as pointers to the corresponding entry in "graph_scc".
60*a749e09eSMichael Kruse * The value stored at that location is the global SCC index.
61*a749e09eSMichael Kruse * "reverse_edge_table" contains the inverse edges.
62*a749e09eSMichael Kruse */
63*a749e09eSMichael Kruse struct isl_scc_graph {
64*a749e09eSMichael Kruse isl_ctx *ctx;
65*a749e09eSMichael Kruse struct isl_sched_graph *graph;
66*a749e09eSMichael Kruse struct isl_clustering *c;
67*a749e09eSMichael Kruse
68*a749e09eSMichael Kruse int n;
69*a749e09eSMichael Kruse int *graph_scc;
70*a749e09eSMichael Kruse int *component;
71*a749e09eSMichael Kruse int *size;
72*a749e09eSMichael Kruse int *pos;
73*a749e09eSMichael Kruse int *sorted;
74*a749e09eSMichael Kruse struct isl_hash_table **edge_table;
75*a749e09eSMichael Kruse struct isl_hash_table **reverse_edge_table;
76*a749e09eSMichael Kruse };
77*a749e09eSMichael Kruse
78*a749e09eSMichael Kruse /* The source SCC of a collection of edges.
79*a749e09eSMichael Kruse *
80*a749e09eSMichael Kruse * "scc_graph" is the SCC graph containing the edges.
81*a749e09eSMichael Kruse * "src" is the local index of the source SCC.
82*a749e09eSMichael Kruse */
83*a749e09eSMichael Kruse struct isl_edge_src {
84*a749e09eSMichael Kruse struct isl_scc_graph *scc_graph;
85*a749e09eSMichael Kruse int src;
86*a749e09eSMichael Kruse };
87*a749e09eSMichael Kruse
88*a749e09eSMichael Kruse /* isl_hash_table_foreach callback for printing an edge
89*a749e09eSMichael Kruse * between "src" and the node identified by "entry".
90*a749e09eSMichael Kruse * The edge is printed in terms of the global SCC indices.
91*a749e09eSMichael Kruse */
print_edge(void ** entry,void * user)92*a749e09eSMichael Kruse static isl_stat print_edge(void **entry, void *user)
93*a749e09eSMichael Kruse {
94*a749e09eSMichael Kruse int *dst = *entry;
95*a749e09eSMichael Kruse int *src = user;
96*a749e09eSMichael Kruse
97*a749e09eSMichael Kruse fprintf(stderr, "%d -> %d; ", *src, *dst);
98*a749e09eSMichael Kruse
99*a749e09eSMichael Kruse return isl_stat_ok;
100*a749e09eSMichael Kruse }
101*a749e09eSMichael Kruse
102*a749e09eSMichael Kruse /* Print some debugging information about "scc_graph".
103*a749e09eSMichael Kruse *
104*a749e09eSMichael Kruse * In particular, print the nodes and the edges (both forward and backward).
105*a749e09eSMichael Kruse */
isl_scc_graph_dump(struct isl_scc_graph * scc_graph)106*a749e09eSMichael Kruse void isl_scc_graph_dump(struct isl_scc_graph *scc_graph)
107*a749e09eSMichael Kruse {
108*a749e09eSMichael Kruse int i;
109*a749e09eSMichael Kruse isl_ctx *ctx;
110*a749e09eSMichael Kruse
111*a749e09eSMichael Kruse if (!scc_graph)
112*a749e09eSMichael Kruse return;
113*a749e09eSMichael Kruse
114*a749e09eSMichael Kruse ctx = scc_graph->ctx;
115*a749e09eSMichael Kruse for (i = 0; i < scc_graph->n; ++i) {
116*a749e09eSMichael Kruse if (i)
117*a749e09eSMichael Kruse fprintf(stderr, ", ");
118*a749e09eSMichael Kruse fprintf(stderr, "%d", scc_graph->graph_scc[i]);
119*a749e09eSMichael Kruse }
120*a749e09eSMichael Kruse fprintf(stderr, "\n");
121*a749e09eSMichael Kruse for (i = 0; i < scc_graph->n; ++i) {
122*a749e09eSMichael Kruse isl_hash_table_foreach(ctx, scc_graph->edge_table[i],
123*a749e09eSMichael Kruse &print_edge, &scc_graph->graph_scc[i]);
124*a749e09eSMichael Kruse }
125*a749e09eSMichael Kruse fprintf(stderr, "\n");
126*a749e09eSMichael Kruse for (i = 0; i < scc_graph->n; ++i) {
127*a749e09eSMichael Kruse isl_hash_table_foreach(ctx, scc_graph->reverse_edge_table[i],
128*a749e09eSMichael Kruse &print_edge, &scc_graph->graph_scc[i]);
129*a749e09eSMichael Kruse }
130*a749e09eSMichael Kruse fprintf(stderr, "\n");
131*a749e09eSMichael Kruse }
132*a749e09eSMichael Kruse
133*a749e09eSMichael Kruse /* Free all memory allocated for "scc_graph" and return NULL.
134*a749e09eSMichael Kruse */
isl_scc_graph_free(struct isl_scc_graph * scc_graph)135*a749e09eSMichael Kruse struct isl_scc_graph *isl_scc_graph_free(struct isl_scc_graph *scc_graph)
136*a749e09eSMichael Kruse {
137*a749e09eSMichael Kruse int i;
138*a749e09eSMichael Kruse isl_ctx *ctx;
139*a749e09eSMichael Kruse
140*a749e09eSMichael Kruse if (!scc_graph)
141*a749e09eSMichael Kruse return NULL;
142*a749e09eSMichael Kruse
143*a749e09eSMichael Kruse ctx = scc_graph->ctx;
144*a749e09eSMichael Kruse if (scc_graph->edge_table) {
145*a749e09eSMichael Kruse for (i = 0; i < scc_graph->n; ++i)
146*a749e09eSMichael Kruse isl_hash_table_free(ctx, scc_graph->edge_table[i]);
147*a749e09eSMichael Kruse }
148*a749e09eSMichael Kruse if (scc_graph->reverse_edge_table) {
149*a749e09eSMichael Kruse for (i = 0; i < scc_graph->n; ++i)
150*a749e09eSMichael Kruse isl_hash_table_free(ctx,
151*a749e09eSMichael Kruse scc_graph->reverse_edge_table[i]);
152*a749e09eSMichael Kruse }
153*a749e09eSMichael Kruse
154*a749e09eSMichael Kruse free(scc_graph->graph_scc);
155*a749e09eSMichael Kruse free(scc_graph->component);
156*a749e09eSMichael Kruse free(scc_graph->size);
157*a749e09eSMichael Kruse free(scc_graph->pos);
158*a749e09eSMichael Kruse free(scc_graph->sorted);
159*a749e09eSMichael Kruse free(scc_graph->edge_table);
160*a749e09eSMichael Kruse free(scc_graph->reverse_edge_table);
161*a749e09eSMichael Kruse isl_ctx_deref(scc_graph->ctx);
162*a749e09eSMichael Kruse free(scc_graph);
163*a749e09eSMichael Kruse return NULL;
164*a749e09eSMichael Kruse }
165*a749e09eSMichael Kruse
166*a749e09eSMichael Kruse /* Return an encoding of the local SCC index "pos" in "scc_graph"
167*a749e09eSMichael Kruse * as a pointer.
168*a749e09eSMichael Kruse * In particular, return a pointer to the corresponding entry
169*a749e09eSMichael Kruse * in scc_graph->graph_scc.
170*a749e09eSMichael Kruse */
isl_scc_graph_encode_local_index(struct isl_scc_graph * scc_graph,int pos)171*a749e09eSMichael Kruse static void *isl_scc_graph_encode_local_index(struct isl_scc_graph *scc_graph,
172*a749e09eSMichael Kruse int pos)
173*a749e09eSMichael Kruse {
174*a749e09eSMichael Kruse return &scc_graph->graph_scc[pos];
175*a749e09eSMichael Kruse }
176*a749e09eSMichael Kruse
177*a749e09eSMichael Kruse /* Return the local SCC index in "scc_graph" corresponding
178*a749e09eSMichael Kruse * to the "data" encoding in the edge table.
179*a749e09eSMichael Kruse */
isl_scc_graph_local_index(struct isl_scc_graph * scc_graph,int * data)180*a749e09eSMichael Kruse static int isl_scc_graph_local_index(struct isl_scc_graph *scc_graph, int *data)
181*a749e09eSMichael Kruse {
182*a749e09eSMichael Kruse return data - &scc_graph->graph_scc[0];
183*a749e09eSMichael Kruse }
184*a749e09eSMichael Kruse
185*a749e09eSMichael Kruse /* isl_hash_table_find callback to check whether the given entry
186*a749e09eSMichael Kruse * refers to an SCC encoded as "val".
187*a749e09eSMichael Kruse */
is_scc_node(const void * entry,const void * val)188*a749e09eSMichael Kruse static isl_bool is_scc_node(const void *entry, const void *val)
189*a749e09eSMichael Kruse {
190*a749e09eSMichael Kruse return entry == val;
191*a749e09eSMichael Kruse }
192*a749e09eSMichael Kruse
193*a749e09eSMichael Kruse /* Return the edge from local SCC index "src" to local SCC index "dst"
194*a749e09eSMichael Kruse * in "edge_table" of "scc_graph", creating one if "reserve" is set.
195*a749e09eSMichael Kruse * If "reserve" is not set, then return isl_hash_table_entry_none
196*a749e09eSMichael Kruse * if there is no such edge.
197*a749e09eSMichael Kruse *
198*a749e09eSMichael Kruse * The destination of the edge is encoded as a pointer
199*a749e09eSMichael Kruse * to the corresponding entry in scc_graph->graph_scc.
200*a749e09eSMichael Kruse */
isl_scc_graph_find_edge(struct isl_scc_graph * scc_graph,struct isl_hash_table ** edge_table,int src,int dst,int reserve)201*a749e09eSMichael Kruse struct isl_hash_table_entry *isl_scc_graph_find_edge(
202*a749e09eSMichael Kruse struct isl_scc_graph *scc_graph, struct isl_hash_table **edge_table,
203*a749e09eSMichael Kruse int src, int dst, int reserve)
204*a749e09eSMichael Kruse {
205*a749e09eSMichael Kruse isl_ctx *ctx;
206*a749e09eSMichael Kruse uint32_t hash;
207*a749e09eSMichael Kruse void *val;
208*a749e09eSMichael Kruse
209*a749e09eSMichael Kruse ctx = scc_graph->ctx;
210*a749e09eSMichael Kruse hash = isl_hash_builtin(isl_hash_init(), dst);
211*a749e09eSMichael Kruse val = isl_scc_graph_encode_local_index(scc_graph, dst);
212*a749e09eSMichael Kruse return isl_hash_table_find(ctx, edge_table[src], hash,
213*a749e09eSMichael Kruse &is_scc_node, val, reserve);
214*a749e09eSMichael Kruse }
215*a749e09eSMichael Kruse
216*a749e09eSMichael Kruse /* Remove the edge between the SCCs with local indices "src" and
217*a749e09eSMichael Kruse * "dst" in "scc_graph", if it exits.
218*a749e09eSMichael Kruse * Return isl_bool_true if this is the case.
219*a749e09eSMichael Kruse *
220*a749e09eSMichael Kruse * The edge is only removed from scc_graph->edge_table.
221*a749e09eSMichael Kruse * scc_graph->reverse_edge_table is assumed to be empty
222*a749e09eSMichael Kruse * when this function is called.
223*a749e09eSMichael Kruse */
isl_scc_graph_remove_edge(struct isl_scc_graph * scc_graph,int src,int dst)224*a749e09eSMichael Kruse static isl_bool isl_scc_graph_remove_edge(struct isl_scc_graph *scc_graph,
225*a749e09eSMichael Kruse int src, int dst)
226*a749e09eSMichael Kruse {
227*a749e09eSMichael Kruse isl_ctx *ctx;
228*a749e09eSMichael Kruse struct isl_hash_table_entry *edge_entry;
229*a749e09eSMichael Kruse
230*a749e09eSMichael Kruse edge_entry = isl_scc_graph_find_edge(scc_graph, scc_graph->edge_table,
231*a749e09eSMichael Kruse src, dst, 0);
232*a749e09eSMichael Kruse if (edge_entry == isl_hash_table_entry_none)
233*a749e09eSMichael Kruse return isl_bool_false;
234*a749e09eSMichael Kruse if (!edge_entry)
235*a749e09eSMichael Kruse return isl_bool_error;
236*a749e09eSMichael Kruse
237*a749e09eSMichael Kruse ctx = scc_graph->ctx;
238*a749e09eSMichael Kruse isl_hash_table_remove(ctx, scc_graph->edge_table[src], edge_entry);
239*a749e09eSMichael Kruse
240*a749e09eSMichael Kruse return isl_bool_true;
241*a749e09eSMichael Kruse }
242*a749e09eSMichael Kruse
243*a749e09eSMichael Kruse /* Internal data structure used by next_nodes.
244*a749e09eSMichael Kruse *
245*a749e09eSMichael Kruse * "scc_graph" is the SCC graph.
246*a749e09eSMichael Kruse * "next" collects the next nodes.
247*a749e09eSMichael Kruse * "n" is the number of next nodes already collected.
248*a749e09eSMichael Kruse */
249*a749e09eSMichael Kruse struct isl_extract_dst_data {
250*a749e09eSMichael Kruse struct isl_scc_graph *scc_graph;
251*a749e09eSMichael Kruse int *next;
252*a749e09eSMichael Kruse int n;
253*a749e09eSMichael Kruse };
254*a749e09eSMichael Kruse
255*a749e09eSMichael Kruse /* Given an entry in the edge table, add the corresponding
256*a749e09eSMichael Kruse * target local SCC index to data->next.
257*a749e09eSMichael Kruse */
extract_dst(void ** entry,void * user)258*a749e09eSMichael Kruse static isl_stat extract_dst(void **entry, void *user)
259*a749e09eSMichael Kruse {
260*a749e09eSMichael Kruse int *dst = *entry;
261*a749e09eSMichael Kruse struct isl_extract_dst_data *data = user;
262*a749e09eSMichael Kruse
263*a749e09eSMichael Kruse data->next[data->n++] = isl_scc_graph_local_index(data->scc_graph, dst);
264*a749e09eSMichael Kruse
265*a749e09eSMichael Kruse return isl_stat_ok;
266*a749e09eSMichael Kruse }
267*a749e09eSMichael Kruse
268*a749e09eSMichael Kruse /* isl_sort callback for sorting integers in increasing order.
269*a749e09eSMichael Kruse */
cmp_int(const void * a,const void * b,void * data)270*a749e09eSMichael Kruse static int cmp_int(const void *a, const void *b, void *data)
271*a749e09eSMichael Kruse {
272*a749e09eSMichael Kruse const int *i1 = a;
273*a749e09eSMichael Kruse const int *i2 = b;
274*a749e09eSMichael Kruse
275*a749e09eSMichael Kruse return *i1 - *i2;
276*a749e09eSMichael Kruse }
277*a749e09eSMichael Kruse
278*a749e09eSMichael Kruse /* Return the local indices of the SCCs in "scc_graph"
279*a749e09eSMichael Kruse * for which there is an edge from the SCC with local index "i".
280*a749e09eSMichael Kruse * The indices are returned in increasing order,
281*a749e09eSMichael Kruse * i.e., in the original topological order.
282*a749e09eSMichael Kruse */
next_nodes(struct isl_scc_graph * scc_graph,int i)283*a749e09eSMichael Kruse static int *next_nodes(struct isl_scc_graph *scc_graph, int i)
284*a749e09eSMichael Kruse {
285*a749e09eSMichael Kruse struct isl_extract_dst_data data;
286*a749e09eSMichael Kruse int n_next;
287*a749e09eSMichael Kruse int *next;
288*a749e09eSMichael Kruse
289*a749e09eSMichael Kruse n_next = scc_graph->edge_table[i]->n;
290*a749e09eSMichael Kruse next = isl_alloc_array(scc_graph->ctx, int, n_next);
291*a749e09eSMichael Kruse if (!next)
292*a749e09eSMichael Kruse return NULL;
293*a749e09eSMichael Kruse data.scc_graph = scc_graph;
294*a749e09eSMichael Kruse data.next = next;
295*a749e09eSMichael Kruse data.n = 0;
296*a749e09eSMichael Kruse if (isl_hash_table_foreach(scc_graph->ctx, scc_graph->edge_table[i],
297*a749e09eSMichael Kruse &extract_dst, &data) < 0)
298*a749e09eSMichael Kruse goto error;
299*a749e09eSMichael Kruse if (isl_sort(next, n_next, sizeof(int), &cmp_int, NULL) < 0)
300*a749e09eSMichael Kruse goto error;
301*a749e09eSMichael Kruse return next;
302*a749e09eSMichael Kruse error:
303*a749e09eSMichael Kruse free(next);
304*a749e09eSMichael Kruse return NULL;
305*a749e09eSMichael Kruse }
306*a749e09eSMichael Kruse
307*a749e09eSMichael Kruse /* Internal data structure for foreach_reachable.
308*a749e09eSMichael Kruse *
309*a749e09eSMichael Kruse * "scc_graph" is the SCC graph being visited.
310*a749e09eSMichael Kruse * "fn" is the function that needs to be called on each reachable node.
311*a749e09eSMichael Kruse * "user" is the user argument to "fn".
312*a749e09eSMichael Kruse */
313*a749e09eSMichael Kruse struct isl_foreach_reachable_data {
314*a749e09eSMichael Kruse struct isl_scc_graph *scc_graph;
315*a749e09eSMichael Kruse isl_bool (*fn)(int pos, void *user);
316*a749e09eSMichael Kruse void *user;
317*a749e09eSMichael Kruse };
318*a749e09eSMichael Kruse
319*a749e09eSMichael Kruse static isl_stat foreach_reachable(struct isl_foreach_reachable_data *data,
320*a749e09eSMichael Kruse int pos);
321*a749e09eSMichael Kruse
322*a749e09eSMichael Kruse /* isl_hash_table_foreach callback for calling data->fn on each SCC
323*a749e09eSMichael Kruse * reachable from the SCC encoded in "entry",
324*a749e09eSMichael Kruse * continuing from an SCC as long as data->fn returns isl_bool_true.
325*a749e09eSMichael Kruse */
recurse_foreach_reachable(void ** entry,void * user)326*a749e09eSMichael Kruse static isl_stat recurse_foreach_reachable(void **entry, void *user)
327*a749e09eSMichael Kruse {
328*a749e09eSMichael Kruse struct isl_foreach_reachable_data *data = user;
329*a749e09eSMichael Kruse int pos;
330*a749e09eSMichael Kruse isl_bool more;
331*a749e09eSMichael Kruse
332*a749e09eSMichael Kruse pos = isl_scc_graph_local_index(data->scc_graph, *entry);
333*a749e09eSMichael Kruse more = data->fn(pos, data->user);
334*a749e09eSMichael Kruse if (more < 0)
335*a749e09eSMichael Kruse return isl_stat_error;
336*a749e09eSMichael Kruse if (!more)
337*a749e09eSMichael Kruse return isl_stat_ok;
338*a749e09eSMichael Kruse
339*a749e09eSMichael Kruse return foreach_reachable(data, pos);
340*a749e09eSMichael Kruse }
341*a749e09eSMichael Kruse
342*a749e09eSMichael Kruse /* Call data->fn on each SCC reachable from the SCC with local index "pos",
343*a749e09eSMichael Kruse * continuing from an SCC as long as data->fn returns isl_bool_true.
344*a749e09eSMichael Kruse *
345*a749e09eSMichael Kruse * Handle chains directly and recurse when an SCC has more than one
346*a749e09eSMichael Kruse * outgoing edge.
347*a749e09eSMichael Kruse */
foreach_reachable(struct isl_foreach_reachable_data * data,int pos)348*a749e09eSMichael Kruse static isl_stat foreach_reachable(struct isl_foreach_reachable_data *data,
349*a749e09eSMichael Kruse int pos)
350*a749e09eSMichael Kruse {
351*a749e09eSMichael Kruse isl_ctx *ctx;
352*a749e09eSMichael Kruse struct isl_hash_table **edge_table = data->scc_graph->edge_table;
353*a749e09eSMichael Kruse
354*a749e09eSMichael Kruse while (edge_table[pos]->n == 1) {
355*a749e09eSMichael Kruse struct isl_hash_table_entry *entry;
356*a749e09eSMichael Kruse isl_bool more;
357*a749e09eSMichael Kruse
358*a749e09eSMichael Kruse entry = isl_hash_table_first(edge_table[pos]);
359*a749e09eSMichael Kruse pos = isl_scc_graph_local_index(data->scc_graph, entry->data);
360*a749e09eSMichael Kruse more = data->fn(pos, data->user);
361*a749e09eSMichael Kruse if (more < 0)
362*a749e09eSMichael Kruse return isl_stat_error;
363*a749e09eSMichael Kruse if (!more)
364*a749e09eSMichael Kruse return isl_stat_ok;
365*a749e09eSMichael Kruse }
366*a749e09eSMichael Kruse
367*a749e09eSMichael Kruse if (edge_table[pos]->n == 0)
368*a749e09eSMichael Kruse return isl_stat_ok;
369*a749e09eSMichael Kruse
370*a749e09eSMichael Kruse ctx = data->scc_graph->ctx;
371*a749e09eSMichael Kruse return isl_hash_table_foreach(ctx, edge_table[pos],
372*a749e09eSMichael Kruse &recurse_foreach_reachable, data);
373*a749e09eSMichael Kruse }
374*a749e09eSMichael Kruse
375*a749e09eSMichael Kruse /* If there is an edge from data->src to "pos", then remove it.
376*a749e09eSMichael Kruse * Return isl_bool_true if descendants of "pos" still need to be considered.
377*a749e09eSMichael Kruse *
378*a749e09eSMichael Kruse * Descendants only need to be considered if no edge is removed.
379*a749e09eSMichael Kruse */
elim_or_next(int pos,void * user)380*a749e09eSMichael Kruse static isl_bool elim_or_next(int pos, void *user)
381*a749e09eSMichael Kruse {
382*a749e09eSMichael Kruse struct isl_edge_src *data = user;
383*a749e09eSMichael Kruse struct isl_scc_graph *scc_graph = data->scc_graph;
384*a749e09eSMichael Kruse isl_bool removed;
385*a749e09eSMichael Kruse
386*a749e09eSMichael Kruse removed = isl_scc_graph_remove_edge(scc_graph, data->src, pos);
387*a749e09eSMichael Kruse return isl_bool_not(removed);
388*a749e09eSMichael Kruse }
389*a749e09eSMichael Kruse
390*a749e09eSMichael Kruse /* Remove transitive edges from "scc_graph".
391*a749e09eSMichael Kruse *
392*a749e09eSMichael Kruse * Consider the SCC nodes "i" in reverse topological order.
393*a749e09eSMichael Kruse * If there is more than one edge emanating from a node,
394*a749e09eSMichael Kruse * then eliminate the edges to those nodes that can also be reached
395*a749e09eSMichael Kruse * through an edge to a node with a smaller index.
396*a749e09eSMichael Kruse * In particular, consider all but the last next nodes "next[j]"
397*a749e09eSMichael Kruse * in reverse topological order. If any node "k" can be reached
398*a749e09eSMichael Kruse * from such a node for which there is also an edge from "i"
399*a749e09eSMichael Kruse * then this edge can be removed because this node can also
400*a749e09eSMichael Kruse * be reached from "i" through the edge to "next[j]".
401*a749e09eSMichael Kruse * If such an edge is removed, then any further descendant of "k"
402*a749e09eSMichael Kruse * does not need to be considered since these were already considered
403*a749e09eSMichael Kruse * for a previous "next[j]" equal to "k", or "k" is the last next node,
404*a749e09eSMichael Kruse * in which case there is no further node with an edge from "i".
405*a749e09eSMichael Kruse */
isl_scc_graph_reduce(struct isl_scc_graph * scc_graph)406*a749e09eSMichael Kruse static struct isl_scc_graph *isl_scc_graph_reduce(
407*a749e09eSMichael Kruse struct isl_scc_graph *scc_graph)
408*a749e09eSMichael Kruse {
409*a749e09eSMichael Kruse struct isl_edge_src elim_data;
410*a749e09eSMichael Kruse struct isl_foreach_reachable_data data = {
411*a749e09eSMichael Kruse .scc_graph = scc_graph,
412*a749e09eSMichael Kruse .fn = &elim_or_next,
413*a749e09eSMichael Kruse .user = &elim_data,
414*a749e09eSMichael Kruse };
415*a749e09eSMichael Kruse int i, j;
416*a749e09eSMichael Kruse
417*a749e09eSMichael Kruse elim_data.scc_graph = scc_graph;
418*a749e09eSMichael Kruse for (i = scc_graph->n - 3; i >= 0; --i) {
419*a749e09eSMichael Kruse int *next;
420*a749e09eSMichael Kruse int n_next;
421*a749e09eSMichael Kruse
422*a749e09eSMichael Kruse n_next = scc_graph->edge_table[i]->n;
423*a749e09eSMichael Kruse if (n_next <= 1)
424*a749e09eSMichael Kruse continue;
425*a749e09eSMichael Kruse next = next_nodes(scc_graph, i);
426*a749e09eSMichael Kruse if (!next)
427*a749e09eSMichael Kruse return isl_scc_graph_free(scc_graph);
428*a749e09eSMichael Kruse
429*a749e09eSMichael Kruse elim_data.src = i;
430*a749e09eSMichael Kruse for (j = n_next - 2; j >= 0; --j)
431*a749e09eSMichael Kruse if (foreach_reachable(&data, next[j]) < 0)
432*a749e09eSMichael Kruse break;
433*a749e09eSMichael Kruse free(next);
434*a749e09eSMichael Kruse if (j >= 0)
435*a749e09eSMichael Kruse return isl_scc_graph_free(scc_graph);
436*a749e09eSMichael Kruse }
437*a749e09eSMichael Kruse
438*a749e09eSMichael Kruse return scc_graph;
439*a749e09eSMichael Kruse }
440*a749e09eSMichael Kruse
441*a749e09eSMichael Kruse /* Add an edge to "edge_table" between the SCCs with local indices "src" and
442*a749e09eSMichael Kruse * "dst" in "scc_graph".
443*a749e09eSMichael Kruse *
444*a749e09eSMichael Kruse * If the edge already appeared in the table, then it is simply overwritten
445*a749e09eSMichael Kruse * with the same information.
446*a749e09eSMichael Kruse */
isl_scc_graph_add_edge(struct isl_scc_graph * scc_graph,struct isl_hash_table ** edge_table,int src,int dst)447*a749e09eSMichael Kruse static isl_stat isl_scc_graph_add_edge(struct isl_scc_graph *scc_graph,
448*a749e09eSMichael Kruse struct isl_hash_table **edge_table, int src, int dst)
449*a749e09eSMichael Kruse {
450*a749e09eSMichael Kruse struct isl_hash_table_entry *edge_entry;
451*a749e09eSMichael Kruse
452*a749e09eSMichael Kruse edge_entry =
453*a749e09eSMichael Kruse isl_scc_graph_find_edge(scc_graph, edge_table, src, dst, 1);
454*a749e09eSMichael Kruse if (!edge_entry)
455*a749e09eSMichael Kruse return isl_stat_error;
456*a749e09eSMichael Kruse edge_entry->data = &scc_graph->graph_scc[dst];
457*a749e09eSMichael Kruse
458*a749e09eSMichael Kruse return isl_stat_ok;
459*a749e09eSMichael Kruse }
460*a749e09eSMichael Kruse
461*a749e09eSMichael Kruse /* Add an edge from "dst" to data->src
462*a749e09eSMichael Kruse * to data->scc_graph->reverse_edge_table.
463*a749e09eSMichael Kruse */
add_reverse(void ** entry,void * user)464*a749e09eSMichael Kruse static isl_stat add_reverse(void **entry, void *user)
465*a749e09eSMichael Kruse {
466*a749e09eSMichael Kruse struct isl_edge_src *data = user;
467*a749e09eSMichael Kruse int dst;
468*a749e09eSMichael Kruse
469*a749e09eSMichael Kruse dst = isl_scc_graph_local_index(data->scc_graph, *entry);
470*a749e09eSMichael Kruse return isl_scc_graph_add_edge(data->scc_graph,
471*a749e09eSMichael Kruse data->scc_graph->reverse_edge_table, dst, data->src);
472*a749e09eSMichael Kruse }
473*a749e09eSMichael Kruse
474*a749e09eSMichael Kruse /* Add an (inverse) edge to scc_graph->reverse_edge_table
475*a749e09eSMichael Kruse * for each edge in scc_graph->edge_table.
476*a749e09eSMichael Kruse */
isl_scc_graph_add_reverse_edges(struct isl_scc_graph * scc_graph)477*a749e09eSMichael Kruse static struct isl_scc_graph *isl_scc_graph_add_reverse_edges(
478*a749e09eSMichael Kruse struct isl_scc_graph *scc_graph)
479*a749e09eSMichael Kruse {
480*a749e09eSMichael Kruse struct isl_edge_src data;
481*a749e09eSMichael Kruse isl_ctx *ctx;
482*a749e09eSMichael Kruse
483*a749e09eSMichael Kruse if (!scc_graph)
484*a749e09eSMichael Kruse return NULL;
485*a749e09eSMichael Kruse
486*a749e09eSMichael Kruse ctx = scc_graph->ctx;
487*a749e09eSMichael Kruse data.scc_graph = scc_graph;
488*a749e09eSMichael Kruse for (data.src = 0; data.src < scc_graph->n; ++data.src) {
489*a749e09eSMichael Kruse if (isl_hash_table_foreach(ctx, scc_graph->edge_table[data.src],
490*a749e09eSMichael Kruse &add_reverse, &data) < 0)
491*a749e09eSMichael Kruse return isl_scc_graph_free(scc_graph);
492*a749e09eSMichael Kruse }
493*a749e09eSMichael Kruse return scc_graph;
494*a749e09eSMichael Kruse }
495*a749e09eSMichael Kruse
496*a749e09eSMichael Kruse /* Given an edge in the schedule graph, add an edge between
497*a749e09eSMichael Kruse * the corresponding SCCs in "scc_graph", if they are distinct.
498*a749e09eSMichael Kruse *
499*a749e09eSMichael Kruse * This function is used to create edges in the original isl_scc_graph.
500*a749e09eSMichael Kruse * where the local SCC indices are equal to the corresponding global
501*a749e09eSMichael Kruse * indices.
502*a749e09eSMichael Kruse */
add_scc_edge(void ** entry,void * user)503*a749e09eSMichael Kruse static isl_stat add_scc_edge(void **entry, void *user)
504*a749e09eSMichael Kruse {
505*a749e09eSMichael Kruse struct isl_sched_edge *edge = *entry;
506*a749e09eSMichael Kruse struct isl_scc_graph *scc_graph = user;
507*a749e09eSMichael Kruse int src = edge->src->scc;
508*a749e09eSMichael Kruse int dst = edge->dst->scc;
509*a749e09eSMichael Kruse
510*a749e09eSMichael Kruse if (src == dst)
511*a749e09eSMichael Kruse return isl_stat_ok;
512*a749e09eSMichael Kruse
513*a749e09eSMichael Kruse return isl_scc_graph_add_edge(scc_graph, scc_graph->edge_table,
514*a749e09eSMichael Kruse src, dst);
515*a749e09eSMichael Kruse }
516*a749e09eSMichael Kruse
517*a749e09eSMichael Kruse /* Allocate an isl_scc_graph for ordering "n" SCCs of "graph"
518*a749e09eSMichael Kruse * with clustering information in "c".
519*a749e09eSMichael Kruse *
520*a749e09eSMichael Kruse * The caller still needs to fill in the edges.
521*a749e09eSMichael Kruse */
isl_scc_graph_alloc(isl_ctx * ctx,int n,struct isl_sched_graph * graph,struct isl_clustering * c)522*a749e09eSMichael Kruse static struct isl_scc_graph *isl_scc_graph_alloc(isl_ctx *ctx, int n,
523*a749e09eSMichael Kruse struct isl_sched_graph *graph, struct isl_clustering *c)
524*a749e09eSMichael Kruse {
525*a749e09eSMichael Kruse int i;
526*a749e09eSMichael Kruse struct isl_scc_graph *scc_graph;
527*a749e09eSMichael Kruse
528*a749e09eSMichael Kruse scc_graph = isl_alloc_type(ctx, struct isl_scc_graph);
529*a749e09eSMichael Kruse if (!scc_graph)
530*a749e09eSMichael Kruse return NULL;
531*a749e09eSMichael Kruse
532*a749e09eSMichael Kruse scc_graph->ctx = ctx;
533*a749e09eSMichael Kruse isl_ctx_ref(ctx);
534*a749e09eSMichael Kruse scc_graph->graph = graph;
535*a749e09eSMichael Kruse scc_graph->c = c;
536*a749e09eSMichael Kruse
537*a749e09eSMichael Kruse scc_graph->n = n;
538*a749e09eSMichael Kruse scc_graph->graph_scc = isl_alloc_array(ctx, int, n);
539*a749e09eSMichael Kruse scc_graph->component = isl_alloc_array(ctx, int, n);
540*a749e09eSMichael Kruse scc_graph->size = isl_alloc_array(ctx, int, n);
541*a749e09eSMichael Kruse scc_graph->pos = isl_alloc_array(ctx, int, n);
542*a749e09eSMichael Kruse scc_graph->sorted = isl_alloc_array(ctx, int, n);
543*a749e09eSMichael Kruse scc_graph->edge_table =
544*a749e09eSMichael Kruse isl_calloc_array(ctx, struct isl_hash_table *, n);
545*a749e09eSMichael Kruse scc_graph->reverse_edge_table =
546*a749e09eSMichael Kruse isl_calloc_array(ctx, struct isl_hash_table *, n);
547*a749e09eSMichael Kruse if (!scc_graph->graph_scc || !scc_graph->component ||
548*a749e09eSMichael Kruse !scc_graph->size || !scc_graph->pos || !scc_graph->sorted ||
549*a749e09eSMichael Kruse !scc_graph->edge_table || !scc_graph->reverse_edge_table)
550*a749e09eSMichael Kruse return isl_scc_graph_free(scc_graph);
551*a749e09eSMichael Kruse
552*a749e09eSMichael Kruse for (i = 0; i < n; ++i) {
553*a749e09eSMichael Kruse scc_graph->edge_table[i] = isl_hash_table_alloc(ctx, 2);
554*a749e09eSMichael Kruse scc_graph->reverse_edge_table[i] = isl_hash_table_alloc(ctx, 2);
555*a749e09eSMichael Kruse if (!scc_graph->edge_table[i] ||
556*a749e09eSMichael Kruse !scc_graph->reverse_edge_table[i])
557*a749e09eSMichael Kruse return isl_scc_graph_free(scc_graph);
558*a749e09eSMichael Kruse }
559*a749e09eSMichael Kruse
560*a749e09eSMichael Kruse return scc_graph;
561*a749e09eSMichael Kruse }
562*a749e09eSMichael Kruse
563*a749e09eSMichael Kruse /* Construct an isl_scc_graph for ordering the SCCs of "graph",
564*a749e09eSMichael Kruse * where each SCC i consists of the single cluster determined
565*a749e09eSMichael Kruse * by c->scc_cluster[i]. The nodes in this cluster all have
566*a749e09eSMichael Kruse * their "scc" field set to i.
567*a749e09eSMichael Kruse *
568*a749e09eSMichael Kruse * The initial isl_scc_graph has as many SCCs as "graph" and
569*a749e09eSMichael Kruse * their local indices are the same as their indices in "graph".
570*a749e09eSMichael Kruse *
571*a749e09eSMichael Kruse * Add edges between different SCCs for each (conditional) validity edge
572*a749e09eSMichael Kruse * between nodes in those SCCs, remove transitive edges and
573*a749e09eSMichael Kruse * construct the inverse edges from the remaining forward edges.
574*a749e09eSMichael Kruse */
isl_scc_graph_from_sched_graph(isl_ctx * ctx,struct isl_sched_graph * graph,struct isl_clustering * c)575*a749e09eSMichael Kruse struct isl_scc_graph *isl_scc_graph_from_sched_graph(isl_ctx *ctx,
576*a749e09eSMichael Kruse struct isl_sched_graph *graph, struct isl_clustering *c)
577*a749e09eSMichael Kruse {
578*a749e09eSMichael Kruse int i;
579*a749e09eSMichael Kruse struct isl_scc_graph *scc_graph;
580*a749e09eSMichael Kruse
581*a749e09eSMichael Kruse scc_graph = isl_scc_graph_alloc(ctx, graph->scc, graph, c);
582*a749e09eSMichael Kruse if (!scc_graph)
583*a749e09eSMichael Kruse return NULL;
584*a749e09eSMichael Kruse
585*a749e09eSMichael Kruse for (i = 0; i < graph->scc; ++i)
586*a749e09eSMichael Kruse scc_graph->graph_scc[i] = i;
587*a749e09eSMichael Kruse
588*a749e09eSMichael Kruse if (isl_hash_table_foreach(ctx, graph->edge_table[isl_edge_validity],
589*a749e09eSMichael Kruse &add_scc_edge, scc_graph) < 0)
590*a749e09eSMichael Kruse return isl_scc_graph_free(scc_graph);
591*a749e09eSMichael Kruse if (isl_hash_table_foreach(ctx,
592*a749e09eSMichael Kruse graph->edge_table[isl_edge_conditional_validity],
593*a749e09eSMichael Kruse &add_scc_edge, scc_graph) < 0)
594*a749e09eSMichael Kruse return isl_scc_graph_free(scc_graph);
595*a749e09eSMichael Kruse
596*a749e09eSMichael Kruse scc_graph = isl_scc_graph_reduce(scc_graph);
597*a749e09eSMichael Kruse scc_graph = isl_scc_graph_add_reverse_edges(scc_graph);
598*a749e09eSMichael Kruse
599*a749e09eSMichael Kruse return scc_graph;
600*a749e09eSMichael Kruse }
601*a749e09eSMichael Kruse
602*a749e09eSMichael Kruse /* Internal data structure for copy_edge.
603*a749e09eSMichael Kruse *
604*a749e09eSMichael Kruse * "scc_graph" is the original graph.
605*a749e09eSMichael Kruse * "sub" is the subgraph to which edges are being copied.
606*a749e09eSMichael Kruse * "src" is the local index in "scc_graph" of the source of the edges
607*a749e09eSMichael Kruse * currently being copied.
608*a749e09eSMichael Kruse */
609*a749e09eSMichael Kruse struct isl_copy_edge_data {
610*a749e09eSMichael Kruse struct isl_scc_graph *scc_graph;
611*a749e09eSMichael Kruse struct isl_scc_graph *sub;
612*a749e09eSMichael Kruse int src;
613*a749e09eSMichael Kruse };
614*a749e09eSMichael Kruse
615*a749e09eSMichael Kruse /* isl_hash_table_foreach callback for copying the edge
616*a749e09eSMichael Kruse * from data->src to the node identified by "entry"
617*a749e09eSMichael Kruse * to data->sub, provided the two nodes belong to the same component.
618*a749e09eSMichael Kruse * Note that by construction, there are no edges between different components
619*a749e09eSMichael Kruse * in the region handled by detect_components, but there may
620*a749e09eSMichael Kruse * be edges to nodes outside this region.
621*a749e09eSMichael Kruse * The components therefore need to be initialized for all nodes
622*a749e09eSMichael Kruse * in isl_scc_graph_init_component.
623*a749e09eSMichael Kruse */
copy_edge(void ** entry,void * user)624*a749e09eSMichael Kruse static isl_stat copy_edge(void **entry, void *user)
625*a749e09eSMichael Kruse {
626*a749e09eSMichael Kruse struct isl_copy_edge_data *data = user;
627*a749e09eSMichael Kruse struct isl_scc_graph *scc_graph = data->scc_graph;
628*a749e09eSMichael Kruse struct isl_scc_graph *sub = data->sub;
629*a749e09eSMichael Kruse int dst, sub_dst, sub_src;
630*a749e09eSMichael Kruse
631*a749e09eSMichael Kruse dst = isl_scc_graph_local_index(data->scc_graph, *entry);
632*a749e09eSMichael Kruse if (scc_graph->component[dst] != scc_graph->component[data->src])
633*a749e09eSMichael Kruse return isl_stat_ok;
634*a749e09eSMichael Kruse
635*a749e09eSMichael Kruse sub_src = scc_graph->pos[data->src];
636*a749e09eSMichael Kruse sub_dst = scc_graph->pos[dst];
637*a749e09eSMichael Kruse
638*a749e09eSMichael Kruse return isl_scc_graph_add_edge(sub, sub->edge_table, sub_src, sub_dst);
639*a749e09eSMichael Kruse }
640*a749e09eSMichael Kruse
641*a749e09eSMichael Kruse /* Construct a subgraph of "scc_graph" for the components
642*a749e09eSMichael Kruse * consisting of the "n" SCCs with local indices in "pos".
643*a749e09eSMichael Kruse * These SCCs have the same value in scc_graph->component and
644*a749e09eSMichael Kruse * this value is different from that of any other SCC.
645*a749e09eSMichael Kruse *
646*a749e09eSMichael Kruse * The forward edges with source and destination in the component
647*a749e09eSMichael Kruse * are copied from "scc_graph".
648*a749e09eSMichael Kruse * The local index in the subgraph corresponding to a local index
649*a749e09eSMichael Kruse * in "scc_graph" is stored in scc_graph->pos for use by copy_edge().
650*a749e09eSMichael Kruse * The inverse edges are constructed directly from the forward edges.
651*a749e09eSMichael Kruse */
isl_scc_graph_sub(struct isl_scc_graph * scc_graph,int * pos,int n)652*a749e09eSMichael Kruse static struct isl_scc_graph *isl_scc_graph_sub(struct isl_scc_graph *scc_graph,
653*a749e09eSMichael Kruse int *pos, int n)
654*a749e09eSMichael Kruse {
655*a749e09eSMichael Kruse int i;
656*a749e09eSMichael Kruse isl_ctx *ctx;
657*a749e09eSMichael Kruse struct isl_scc_graph *sub;
658*a749e09eSMichael Kruse struct isl_copy_edge_data data;
659*a749e09eSMichael Kruse
660*a749e09eSMichael Kruse if (!scc_graph)
661*a749e09eSMichael Kruse return NULL;
662*a749e09eSMichael Kruse
663*a749e09eSMichael Kruse ctx = scc_graph->ctx;
664*a749e09eSMichael Kruse sub = isl_scc_graph_alloc(ctx, n, scc_graph->graph, scc_graph->c);
665*a749e09eSMichael Kruse if (!sub)
666*a749e09eSMichael Kruse return sub;
667*a749e09eSMichael Kruse
668*a749e09eSMichael Kruse for (i = 0; i < n; ++i)
669*a749e09eSMichael Kruse sub->graph_scc[i] = scc_graph->graph_scc[pos[i]];
670*a749e09eSMichael Kruse
671*a749e09eSMichael Kruse for (i = 0; i < n; ++i)
672*a749e09eSMichael Kruse scc_graph->pos[pos[i]] = i;
673*a749e09eSMichael Kruse
674*a749e09eSMichael Kruse data.scc_graph = scc_graph;
675*a749e09eSMichael Kruse data.sub = sub;
676*a749e09eSMichael Kruse for (i = 0; i < n; ++i) {
677*a749e09eSMichael Kruse data.src = pos[i];
678*a749e09eSMichael Kruse if (isl_hash_table_foreach(ctx, scc_graph->edge_table[pos[i]],
679*a749e09eSMichael Kruse ©_edge, &data) < 0)
680*a749e09eSMichael Kruse return isl_scc_graph_free(sub);
681*a749e09eSMichael Kruse }
682*a749e09eSMichael Kruse
683*a749e09eSMichael Kruse sub = isl_scc_graph_add_reverse_edges(sub);
684*a749e09eSMichael Kruse
685*a749e09eSMichael Kruse return sub;
686*a749e09eSMichael Kruse }
687*a749e09eSMichael Kruse
688*a749e09eSMichael Kruse /* Return a union of universe domains corresponding to the nodes
689*a749e09eSMichael Kruse * in the SCC with local index "pos".
690*a749e09eSMichael Kruse */
isl_scc_graph_extract_local_scc(struct isl_scc_graph * scc_graph,int pos)691*a749e09eSMichael Kruse static __isl_give isl_union_set *isl_scc_graph_extract_local_scc(
692*a749e09eSMichael Kruse struct isl_scc_graph *scc_graph, int pos)
693*a749e09eSMichael Kruse {
694*a749e09eSMichael Kruse return isl_sched_graph_extract_scc(scc_graph->ctx, scc_graph->graph,
695*a749e09eSMichael Kruse scc_graph->graph_scc[pos]);
696*a749e09eSMichael Kruse }
697*a749e09eSMichael Kruse
698*a749e09eSMichael Kruse /* Construct a filter corresponding to a sequence of "n" local SCC indices
699*a749e09eSMichael Kruse * determined by successive calls to "el",
700*a749e09eSMichael Kruse * add this filter to "list" and
701*a749e09eSMichael Kruse * return the result.
702*a749e09eSMichael Kruse */
add_scc_seq(struct isl_scc_graph * scc_graph,int (* el)(int i,void * user),void * user,int n,__isl_take isl_union_set_list * list)703*a749e09eSMichael Kruse static __isl_give isl_union_set_list *add_scc_seq(
704*a749e09eSMichael Kruse struct isl_scc_graph *scc_graph,
705*a749e09eSMichael Kruse int (*el)(int i, void *user), void *user, int n,
706*a749e09eSMichael Kruse __isl_take isl_union_set_list *list)
707*a749e09eSMichael Kruse {
708*a749e09eSMichael Kruse int i;
709*a749e09eSMichael Kruse isl_union_set *dom;
710*a749e09eSMichael Kruse
711*a749e09eSMichael Kruse dom = isl_union_set_empty_ctx(scc_graph->ctx);
712*a749e09eSMichael Kruse for (i = 0; i < n; ++i)
713*a749e09eSMichael Kruse dom = isl_union_set_union(dom,
714*a749e09eSMichael Kruse isl_scc_graph_extract_local_scc(scc_graph, el(i, user)));
715*a749e09eSMichael Kruse
716*a749e09eSMichael Kruse return isl_union_set_list_add(list, dom);
717*a749e09eSMichael Kruse }
718*a749e09eSMichael Kruse
719*a749e09eSMichael Kruse /* add_scc_seq callback that, on successive calls, returns a sequence
720*a749e09eSMichael Kruse * of local SCC indices starting at "first".
721*a749e09eSMichael Kruse */
offset(int i,void * user)722*a749e09eSMichael Kruse static int offset(int i, void *user)
723*a749e09eSMichael Kruse {
724*a749e09eSMichael Kruse int *first = user;
725*a749e09eSMichael Kruse
726*a749e09eSMichael Kruse return *first + i;
727*a749e09eSMichael Kruse }
728*a749e09eSMichael Kruse
729*a749e09eSMichael Kruse /* Construct a filter corresponding to a sequence of "n" local SCC indices
730*a749e09eSMichael Kruse * starting at "first", add this filter to "list" and return the result.
731*a749e09eSMichael Kruse */
isl_scc_graph_add_scc_seq(struct isl_scc_graph * scc_graph,int first,int n,__isl_take isl_union_set_list * list)732*a749e09eSMichael Kruse static __isl_give isl_union_set_list *isl_scc_graph_add_scc_seq(
733*a749e09eSMichael Kruse struct isl_scc_graph *scc_graph, int first, int n,
734*a749e09eSMichael Kruse __isl_take isl_union_set_list *list)
735*a749e09eSMichael Kruse {
736*a749e09eSMichael Kruse return add_scc_seq(scc_graph, &offset, &first, n, list);
737*a749e09eSMichael Kruse }
738*a749e09eSMichael Kruse
739*a749e09eSMichael Kruse /* add_scc_seq callback that, on successive calls, returns the sequence
740*a749e09eSMichael Kruse * of local SCC indices in "seq".
741*a749e09eSMichael Kruse */
at(int i,void * user)742*a749e09eSMichael Kruse static int at(int i, void *user)
743*a749e09eSMichael Kruse {
744*a749e09eSMichael Kruse int *seq = user;
745*a749e09eSMichael Kruse
746*a749e09eSMichael Kruse return seq[i];
747*a749e09eSMichael Kruse }
748*a749e09eSMichael Kruse
749*a749e09eSMichael Kruse /* Construct a filter corresponding to the sequence of "n" local SCC indices
750*a749e09eSMichael Kruse * stored in "seq", add this filter to "list" and return the result.
751*a749e09eSMichael Kruse */
isl_scc_graph_add_scc_indirect_seq(struct isl_scc_graph * scc_graph,int * seq,int n,__isl_take isl_union_set_list * list)752*a749e09eSMichael Kruse static __isl_give isl_union_set_list *isl_scc_graph_add_scc_indirect_seq(
753*a749e09eSMichael Kruse struct isl_scc_graph *scc_graph, int *seq, int n,
754*a749e09eSMichael Kruse __isl_take isl_union_set_list *list)
755*a749e09eSMichael Kruse {
756*a749e09eSMichael Kruse return add_scc_seq(scc_graph, &at, seq, n, list);
757*a749e09eSMichael Kruse }
758*a749e09eSMichael Kruse
759*a749e09eSMichael Kruse /* Extract out a list of filters for a sequence node that splits
760*a749e09eSMichael Kruse * the graph along the SCC with local index "pos".
761*a749e09eSMichael Kruse *
762*a749e09eSMichael Kruse * The list contains (at most) three elements,
763*a749e09eSMichael Kruse * the SCCs before "pos" (in the topological order),
764*a749e09eSMichael Kruse * "pos" itself, and
765*a749e09eSMichael Kruse * the SCCs after "pos".
766*a749e09eSMichael Kruse */
extract_split_scc(struct isl_scc_graph * scc_graph,int pos)767*a749e09eSMichael Kruse static __isl_give isl_union_set_list *extract_split_scc(
768*a749e09eSMichael Kruse struct isl_scc_graph *scc_graph, int pos)
769*a749e09eSMichael Kruse {
770*a749e09eSMichael Kruse isl_union_set *dom;
771*a749e09eSMichael Kruse isl_union_set_list *filters;
772*a749e09eSMichael Kruse
773*a749e09eSMichael Kruse filters = isl_union_set_list_alloc(scc_graph->ctx, 3);
774*a749e09eSMichael Kruse if (pos > 0)
775*a749e09eSMichael Kruse filters = isl_scc_graph_add_scc_seq(scc_graph, 0, pos, filters);
776*a749e09eSMichael Kruse dom = isl_scc_graph_extract_local_scc(scc_graph, pos);
777*a749e09eSMichael Kruse filters = isl_union_set_list_add(filters, dom);
778*a749e09eSMichael Kruse if (pos + 1 < scc_graph->n)
779*a749e09eSMichael Kruse filters = isl_scc_graph_add_scc_seq(scc_graph,
780*a749e09eSMichael Kruse pos + 1, scc_graph->n - (pos + 1), filters);
781*a749e09eSMichael Kruse return filters;
782*a749e09eSMichael Kruse }
783*a749e09eSMichael Kruse
784*a749e09eSMichael Kruse /* Call isl_schedule_node_compute_finish_band on the cluster
785*a749e09eSMichael Kruse * corresponding to the SCC with local index "pos".
786*a749e09eSMichael Kruse *
787*a749e09eSMichael Kruse * First obtain the corresponding SCC index in scc_graph->graph and
788*a749e09eSMichael Kruse * then obtain the corresponding cluster.
789*a749e09eSMichael Kruse */
isl_scc_graph_finish_band(struct isl_scc_graph * scc_graph,__isl_take isl_schedule_node * node,int pos)790*a749e09eSMichael Kruse static __isl_give isl_schedule_node *isl_scc_graph_finish_band(
791*a749e09eSMichael Kruse struct isl_scc_graph *scc_graph, __isl_take isl_schedule_node *node,
792*a749e09eSMichael Kruse int pos)
793*a749e09eSMichael Kruse {
794*a749e09eSMichael Kruse struct isl_clustering *c = scc_graph->c;
795*a749e09eSMichael Kruse int cluster;
796*a749e09eSMichael Kruse
797*a749e09eSMichael Kruse cluster = c->scc_cluster[scc_graph->graph_scc[pos]];
798*a749e09eSMichael Kruse return isl_schedule_node_compute_finish_band(node,
799*a749e09eSMichael Kruse &c->cluster[cluster], 0);
800*a749e09eSMichael Kruse }
801*a749e09eSMichael Kruse
802*a749e09eSMichael Kruse /* Given that the SCCs in "scc_graph" form a chain,
803*a749e09eSMichael Kruse * call isl_schedule_node_compute_finish_band on each of the clusters
804*a749e09eSMichael Kruse * in scc_graph->c and update "node" to arrange for them to be executed
805*a749e09eSMichael Kruse * in topological order.
806*a749e09eSMichael Kruse */
isl_scc_graph_chain(struct isl_scc_graph * scc_graph,__isl_take isl_schedule_node * node)807*a749e09eSMichael Kruse static __isl_give isl_schedule_node *isl_scc_graph_chain(
808*a749e09eSMichael Kruse struct isl_scc_graph *scc_graph, __isl_take isl_schedule_node *node)
809*a749e09eSMichael Kruse {
810*a749e09eSMichael Kruse int i;
811*a749e09eSMichael Kruse isl_union_set *dom;
812*a749e09eSMichael Kruse isl_union_set_list *filters;
813*a749e09eSMichael Kruse
814*a749e09eSMichael Kruse filters = isl_union_set_list_alloc(scc_graph->ctx, scc_graph->n);
815*a749e09eSMichael Kruse for (i = 0; i < scc_graph->n; ++i) {
816*a749e09eSMichael Kruse dom = isl_scc_graph_extract_local_scc(scc_graph, i);
817*a749e09eSMichael Kruse filters = isl_union_set_list_add(filters, dom);
818*a749e09eSMichael Kruse }
819*a749e09eSMichael Kruse
820*a749e09eSMichael Kruse node = isl_schedule_node_insert_sequence(node, filters);
821*a749e09eSMichael Kruse
822*a749e09eSMichael Kruse for (i = 0; i < scc_graph->n; ++i) {
823*a749e09eSMichael Kruse node = isl_schedule_node_grandchild(node, i, 0);
824*a749e09eSMichael Kruse node = isl_scc_graph_finish_band(scc_graph, node, i);
825*a749e09eSMichael Kruse node = isl_schedule_node_grandparent(node);
826*a749e09eSMichael Kruse }
827*a749e09eSMichael Kruse
828*a749e09eSMichael Kruse return node;
829*a749e09eSMichael Kruse }
830*a749e09eSMichael Kruse
831*a749e09eSMichael Kruse /* Recursively call isl_scc_graph_decompose on a subgraph
832*a749e09eSMichael Kruse * consisting of the "n" SCCs with local indices in "pos".
833*a749e09eSMichael Kruse *
834*a749e09eSMichael Kruse * If this component contains only a single SCC,
835*a749e09eSMichael Kruse * then there is no need for a further recursion and
836*a749e09eSMichael Kruse * isl_schedule_node_compute_finish_band can be called directly.
837*a749e09eSMichael Kruse */
recurse(struct isl_scc_graph * scc_graph,int * pos,int n,__isl_take isl_schedule_node * node)838*a749e09eSMichael Kruse static __isl_give isl_schedule_node *recurse(struct isl_scc_graph *scc_graph,
839*a749e09eSMichael Kruse int *pos, int n, __isl_take isl_schedule_node *node)
840*a749e09eSMichael Kruse {
841*a749e09eSMichael Kruse struct isl_scc_graph *sub;
842*a749e09eSMichael Kruse
843*a749e09eSMichael Kruse if (n == 1)
844*a749e09eSMichael Kruse return isl_scc_graph_finish_band(scc_graph, node, pos[0]);
845*a749e09eSMichael Kruse
846*a749e09eSMichael Kruse sub = isl_scc_graph_sub(scc_graph, pos, n);
847*a749e09eSMichael Kruse if (!sub)
848*a749e09eSMichael Kruse return isl_schedule_node_free(node);
849*a749e09eSMichael Kruse node = isl_scc_graph_decompose(sub, node);
850*a749e09eSMichael Kruse isl_scc_graph_free(sub);
851*a749e09eSMichael Kruse
852*a749e09eSMichael Kruse return node;
853*a749e09eSMichael Kruse }
854*a749e09eSMichael Kruse
855*a749e09eSMichael Kruse /* Initialize the component field of "scc_graph".
856*a749e09eSMichael Kruse * Initially, each SCC belongs to its own single-element component.
857*a749e09eSMichael Kruse *
858*a749e09eSMichael Kruse * Note that the SCC on which isl_scc_graph_decompose performs a split
859*a749e09eSMichael Kruse * also needs to be assigned a component because the components
860*a749e09eSMichael Kruse * are also used in copy_edge to extract a subgraph.
861*a749e09eSMichael Kruse */
isl_scc_graph_init_component(struct isl_scc_graph * scc_graph)862*a749e09eSMichael Kruse static void isl_scc_graph_init_component(struct isl_scc_graph *scc_graph)
863*a749e09eSMichael Kruse {
864*a749e09eSMichael Kruse int i;
865*a749e09eSMichael Kruse
866*a749e09eSMichael Kruse for (i = 0; i < scc_graph->n; ++i)
867*a749e09eSMichael Kruse scc_graph->component[i] = i;
868*a749e09eSMichael Kruse }
869*a749e09eSMichael Kruse
870*a749e09eSMichael Kruse /* Set the component of "a" to be the same as that of "b" and
871*a749e09eSMichael Kruse * return the original component of "a".
872*a749e09eSMichael Kruse */
assign(int * component,int a,int b)873*a749e09eSMichael Kruse static int assign(int *component, int a, int b)
874*a749e09eSMichael Kruse {
875*a749e09eSMichael Kruse int t;
876*a749e09eSMichael Kruse
877*a749e09eSMichael Kruse t = component[a];
878*a749e09eSMichael Kruse component[a] = component[b];
879*a749e09eSMichael Kruse return t;
880*a749e09eSMichael Kruse }
881*a749e09eSMichael Kruse
882*a749e09eSMichael Kruse /* Merge the components containing the SCCs with indices "a" and "b".
883*a749e09eSMichael Kruse *
884*a749e09eSMichael Kruse * If "a" and "b" already belong to the same component, then nothing
885*a749e09eSMichael Kruse * needs to be done.
886*a749e09eSMichael Kruse * Otherwise, make sure both point to the same component.
887*a749e09eSMichael Kruse * In particular, use the SCC in the component entries with the smallest index.
888*a749e09eSMichael Kruse * If the other SCC was the first of its component then the entire
889*a749e09eSMichael Kruse * component now (eventually) points to the other component.
890*a749e09eSMichael Kruse * Otherwise, the earlier parts of the component still need
891*a749e09eSMichael Kruse * to be merged with the other component.
892*a749e09eSMichael Kruse *
893*a749e09eSMichael Kruse * At each stage, either a or b is replaced by either a or b itself,
894*a749e09eSMichael Kruse * in which case the merging terminates because a and b already
895*a749e09eSMichael Kruse * point to the same component, or an SCC index with a smaller value.
896*a749e09eSMichael Kruse * This ensures the merging terminates at some point.
897*a749e09eSMichael Kruse */
isl_scc_graph_merge_src_dst(struct isl_scc_graph * scc_graph,int a,int b)898*a749e09eSMichael Kruse static void isl_scc_graph_merge_src_dst(struct isl_scc_graph *scc_graph,
899*a749e09eSMichael Kruse int a, int b)
900*a749e09eSMichael Kruse {
901*a749e09eSMichael Kruse int *component = scc_graph->component;
902*a749e09eSMichael Kruse
903*a749e09eSMichael Kruse while (component[a] != component[b]) {
904*a749e09eSMichael Kruse if (component[a] < component[b])
905*a749e09eSMichael Kruse b = assign(component, b, a);
906*a749e09eSMichael Kruse else
907*a749e09eSMichael Kruse a = assign(component, a, b);
908*a749e09eSMichael Kruse }
909*a749e09eSMichael Kruse }
910*a749e09eSMichael Kruse
911*a749e09eSMichael Kruse /* Internal data structure for isl_scc_graph_merge_components.
912*a749e09eSMichael Kruse *
913*a749e09eSMichael Kruse * "scc_graph" is the SCC graph containing the edges.
914*a749e09eSMichael Kruse * "src" is the local index of the source SCC.
915*a749e09eSMichael Kruse * "end" is the local index beyond the sequence being considered.
916*a749e09eSMichael Kruse */
917*a749e09eSMichael Kruse struct isl_merge_src_dst_data {
918*a749e09eSMichael Kruse struct isl_scc_graph *scc_graph;
919*a749e09eSMichael Kruse int src;
920*a749e09eSMichael Kruse int end;
921*a749e09eSMichael Kruse };
922*a749e09eSMichael Kruse
923*a749e09eSMichael Kruse /* isl_hash_table_foreach callback for merging the components
924*a749e09eSMichael Kruse * of data->src and the node represented by "entry", provided
925*a749e09eSMichael Kruse * it is within the sequence being considered.
926*a749e09eSMichael Kruse */
merge_src_dst(void ** entry,void * user)927*a749e09eSMichael Kruse static isl_stat merge_src_dst(void **entry, void *user)
928*a749e09eSMichael Kruse {
929*a749e09eSMichael Kruse struct isl_merge_src_dst_data *data = user;
930*a749e09eSMichael Kruse int dst;
931*a749e09eSMichael Kruse
932*a749e09eSMichael Kruse dst = isl_scc_graph_local_index(data->scc_graph, *entry);
933*a749e09eSMichael Kruse if (dst >= data->end)
934*a749e09eSMichael Kruse return isl_stat_ok;
935*a749e09eSMichael Kruse
936*a749e09eSMichael Kruse isl_scc_graph_merge_src_dst(data->scc_graph, data->src, dst);
937*a749e09eSMichael Kruse
938*a749e09eSMichael Kruse return isl_stat_ok;
939*a749e09eSMichael Kruse }
940*a749e09eSMichael Kruse
941*a749e09eSMichael Kruse /* Merge components of the "n" SCCs starting at "first" that are connected
942*a749e09eSMichael Kruse * by an edge.
943*a749e09eSMichael Kruse */
isl_scc_graph_merge_components(struct isl_scc_graph * scc_graph,int first,int n)944*a749e09eSMichael Kruse static isl_stat isl_scc_graph_merge_components(struct isl_scc_graph *scc_graph,
945*a749e09eSMichael Kruse int first, int n)
946*a749e09eSMichael Kruse {
947*a749e09eSMichael Kruse int i;
948*a749e09eSMichael Kruse struct isl_merge_src_dst_data data;
949*a749e09eSMichael Kruse isl_ctx *ctx = scc_graph->ctx;
950*a749e09eSMichael Kruse
951*a749e09eSMichael Kruse data.scc_graph = scc_graph;
952*a749e09eSMichael Kruse data.end = first + n;
953*a749e09eSMichael Kruse for (i = 0; i < n; ++i) {
954*a749e09eSMichael Kruse data.src = first + i;
955*a749e09eSMichael Kruse if (isl_hash_table_foreach(ctx, scc_graph->edge_table[data.src],
956*a749e09eSMichael Kruse &merge_src_dst, &data) < 0)
957*a749e09eSMichael Kruse return isl_stat_error;
958*a749e09eSMichael Kruse }
959*a749e09eSMichael Kruse
960*a749e09eSMichael Kruse return isl_stat_ok;
961*a749e09eSMichael Kruse }
962*a749e09eSMichael Kruse
963*a749e09eSMichael Kruse /* Sort the "n" local SCC indices starting at "first" according
964*a749e09eSMichael Kruse * to component, store them in scc_graph->sorted and
965*a749e09eSMichael Kruse * return the number of components.
966*a749e09eSMichael Kruse * The sizes of the components are stored in scc_graph->size.
967*a749e09eSMichael Kruse * Only positions starting at "first" are used within
968*a749e09eSMichael Kruse * scc_graph->sorted and scc_graph->size.
969*a749e09eSMichael Kruse *
970*a749e09eSMichael Kruse * The representation of the components is first normalized.
971*a749e09eSMichael Kruse * The normalization ensures that each SCC in a component
972*a749e09eSMichael Kruse * points to the first SCC in the component, whereas
973*a749e09eSMichael Kruse * before this function is called, some SCCs may only point
974*a749e09eSMichael Kruse * to some other SCC in the component with a smaller index.
975*a749e09eSMichael Kruse *
976*a749e09eSMichael Kruse * Internally, the sizes of the components are first stored
977*a749e09eSMichael Kruse * at indices corresponding to the first SCC in the component.
978*a749e09eSMichael Kruse * They are subsequently moved into consecutive positions
979*a749e09eSMichael Kruse * while reordering the local indices.
980*a749e09eSMichael Kruse * This reordering is performed by first determining the position
981*a749e09eSMichael Kruse * of the first SCC in each component and
982*a749e09eSMichael Kruse * then putting the "n" local indices in the right position
983*a749e09eSMichael Kruse * according to the component, preserving the topological order
984*a749e09eSMichael Kruse * within each component.
985*a749e09eSMichael Kruse */
isl_scc_graph_sort_components(struct isl_scc_graph * scc_graph,int first,int n)986*a749e09eSMichael Kruse static int isl_scc_graph_sort_components(struct isl_scc_graph *scc_graph,
987*a749e09eSMichael Kruse int first, int n)
988*a749e09eSMichael Kruse {
989*a749e09eSMichael Kruse int i, j;
990*a749e09eSMichael Kruse int sum;
991*a749e09eSMichael Kruse int *component = scc_graph->component;
992*a749e09eSMichael Kruse int *size = scc_graph->size;
993*a749e09eSMichael Kruse int *pos = scc_graph->pos;
994*a749e09eSMichael Kruse int *sorted = scc_graph->sorted;
995*a749e09eSMichael Kruse int n_component;
996*a749e09eSMichael Kruse
997*a749e09eSMichael Kruse n_component = 0;
998*a749e09eSMichael Kruse for (i = 0; i < n; ++i) {
999*a749e09eSMichael Kruse size[first + i] = 0;
1000*a749e09eSMichael Kruse if (component[first + i] == first + i)
1001*a749e09eSMichael Kruse n_component++;
1002*a749e09eSMichael Kruse else
1003*a749e09eSMichael Kruse component[first + i] = component[component[first + i]];
1004*a749e09eSMichael Kruse size[component[first + i]]++;
1005*a749e09eSMichael Kruse }
1006*a749e09eSMichael Kruse
1007*a749e09eSMichael Kruse sum = first;
1008*a749e09eSMichael Kruse i = 0;
1009*a749e09eSMichael Kruse for (j = 0; j < n_component; ++j) {
1010*a749e09eSMichael Kruse while (size[first + i] == 0)
1011*a749e09eSMichael Kruse ++i;
1012*a749e09eSMichael Kruse pos[first + i] = sum;
1013*a749e09eSMichael Kruse sum += size[first + i];
1014*a749e09eSMichael Kruse size[first + j] = size[first + i++];
1015*a749e09eSMichael Kruse }
1016*a749e09eSMichael Kruse for (i = 0; i < n; ++i)
1017*a749e09eSMichael Kruse sorted[pos[component[first + i]]++] = first + i;
1018*a749e09eSMichael Kruse
1019*a749e09eSMichael Kruse return n_component;
1020*a749e09eSMichael Kruse }
1021*a749e09eSMichael Kruse
1022*a749e09eSMichael Kruse /* Extract out a list of filters for a set node that splits up
1023*a749e09eSMichael Kruse * the graph into "n_component" components.
1024*a749e09eSMichael Kruse * "first" is the initial position in "scc_graph" where information
1025*a749e09eSMichael Kruse * about the components is stored.
1026*a749e09eSMichael Kruse * In particular, the first "n_component" entries of scc_graph->size
1027*a749e09eSMichael Kruse * at this position contain the number of SCCs in each component.
1028*a749e09eSMichael Kruse * The entries of scc_graph->sorted starting at "first"
1029*a749e09eSMichael Kruse * contain the local indices of the SCC in those components.
1030*a749e09eSMichael Kruse */
extract_components(struct isl_scc_graph * scc_graph,int first,int n_component)1031*a749e09eSMichael Kruse static __isl_give isl_union_set_list *extract_components(
1032*a749e09eSMichael Kruse struct isl_scc_graph *scc_graph, int first, int n_component)
1033*a749e09eSMichael Kruse {
1034*a749e09eSMichael Kruse int i;
1035*a749e09eSMichael Kruse int sum;
1036*a749e09eSMichael Kruse int *size = scc_graph->size;
1037*a749e09eSMichael Kruse int *sorted = scc_graph->sorted;
1038*a749e09eSMichael Kruse isl_ctx *ctx = scc_graph->ctx;
1039*a749e09eSMichael Kruse isl_union_set_list *filters;
1040*a749e09eSMichael Kruse
1041*a749e09eSMichael Kruse filters = isl_union_set_list_alloc(ctx, n_component);
1042*a749e09eSMichael Kruse sum = first;
1043*a749e09eSMichael Kruse for (i = 0; i < n_component; ++i) {
1044*a749e09eSMichael Kruse int n;
1045*a749e09eSMichael Kruse
1046*a749e09eSMichael Kruse n = size[first + i];
1047*a749e09eSMichael Kruse filters = isl_scc_graph_add_scc_indirect_seq(scc_graph,
1048*a749e09eSMichael Kruse &sorted[sum], n, filters);
1049*a749e09eSMichael Kruse sum += n;
1050*a749e09eSMichael Kruse }
1051*a749e09eSMichael Kruse
1052*a749e09eSMichael Kruse return filters;
1053*a749e09eSMichael Kruse }
1054*a749e09eSMichael Kruse
1055*a749e09eSMichael Kruse /* Detect components in the subgraph consisting of the "n" SCCs
1056*a749e09eSMichael Kruse * with local index starting at "first" and further decompose them,
1057*a749e09eSMichael Kruse * calling isl_schedule_node_compute_finish_band on each
1058*a749e09eSMichael Kruse * of the corresponding clusters.
1059*a749e09eSMichael Kruse *
1060*a749e09eSMichael Kruse * If there is only one SCC, then isl_schedule_node_compute_finish_band
1061*a749e09eSMichael Kruse * can be called directly.
1062*a749e09eSMichael Kruse * Otherwise, determine the components and rearrange the local indices
1063*a749e09eSMichael Kruse * according to component, but preserving the topological order within
1064*a749e09eSMichael Kruse * each component, in scc_graph->sorted. The sizes of the components
1065*a749e09eSMichael Kruse * are stored in scc_graph->size.
1066*a749e09eSMichael Kruse * If there is only one component, it can be further decomposed
1067*a749e09eSMichael Kruse * directly by a call to recurse().
1068*a749e09eSMichael Kruse * Otherwise, introduce a set node separating the components and
1069*a749e09eSMichael Kruse * call recurse() on each component separately.
1070*a749e09eSMichael Kruse */
detect_components(struct isl_scc_graph * scc_graph,int first,int n,__isl_take isl_schedule_node * node)1071*a749e09eSMichael Kruse static __isl_give isl_schedule_node *detect_components(
1072*a749e09eSMichael Kruse struct isl_scc_graph *scc_graph, int first, int n,
1073*a749e09eSMichael Kruse __isl_take isl_schedule_node *node)
1074*a749e09eSMichael Kruse {
1075*a749e09eSMichael Kruse int i;
1076*a749e09eSMichael Kruse int *size = scc_graph->size;
1077*a749e09eSMichael Kruse int *sorted = scc_graph->sorted;
1078*a749e09eSMichael Kruse int n_component;
1079*a749e09eSMichael Kruse int sum;
1080*a749e09eSMichael Kruse isl_union_set_list *filters;
1081*a749e09eSMichael Kruse
1082*a749e09eSMichael Kruse if (n == 1)
1083*a749e09eSMichael Kruse return isl_scc_graph_finish_band(scc_graph, node, first);
1084*a749e09eSMichael Kruse
1085*a749e09eSMichael Kruse if (isl_scc_graph_merge_components(scc_graph, first, n) < 0)
1086*a749e09eSMichael Kruse return isl_schedule_node_free(node);
1087*a749e09eSMichael Kruse
1088*a749e09eSMichael Kruse n_component = isl_scc_graph_sort_components(scc_graph, first, n);
1089*a749e09eSMichael Kruse if (n_component == 1)
1090*a749e09eSMichael Kruse return recurse(scc_graph, &sorted[first], n, node);
1091*a749e09eSMichael Kruse
1092*a749e09eSMichael Kruse filters = extract_components(scc_graph, first, n_component);
1093*a749e09eSMichael Kruse node = isl_schedule_node_insert_set(node, filters);
1094*a749e09eSMichael Kruse
1095*a749e09eSMichael Kruse sum = first;
1096*a749e09eSMichael Kruse for (i = 0; i < n_component; ++i) {
1097*a749e09eSMichael Kruse int n;
1098*a749e09eSMichael Kruse
1099*a749e09eSMichael Kruse n = size[first + i];
1100*a749e09eSMichael Kruse node = isl_schedule_node_grandchild(node, i, 0);
1101*a749e09eSMichael Kruse node = recurse(scc_graph, &sorted[sum], n, node);
1102*a749e09eSMichael Kruse node = isl_schedule_node_grandparent(node);
1103*a749e09eSMichael Kruse sum += n;
1104*a749e09eSMichael Kruse }
1105*a749e09eSMichael Kruse
1106*a749e09eSMichael Kruse return node;
1107*a749e09eSMichael Kruse }
1108*a749e09eSMichael Kruse
1109*a749e09eSMichael Kruse /* Given a sequence node "node", where the filter at position "child"
1110*a749e09eSMichael Kruse * represents the "n" SCCs with local index starting at "first",
1111*a749e09eSMichael Kruse * detect components in this subgraph and further decompose them,
1112*a749e09eSMichael Kruse * calling isl_schedule_node_compute_finish_band on each
1113*a749e09eSMichael Kruse * of the corresponding clusters.
1114*a749e09eSMichael Kruse */
detect_components_at(struct isl_scc_graph * scc_graph,int first,int n,__isl_take isl_schedule_node * node,int child)1115*a749e09eSMichael Kruse static __isl_give isl_schedule_node *detect_components_at(
1116*a749e09eSMichael Kruse struct isl_scc_graph *scc_graph, int first, int n,
1117*a749e09eSMichael Kruse __isl_take isl_schedule_node *node, int child)
1118*a749e09eSMichael Kruse {
1119*a749e09eSMichael Kruse node = isl_schedule_node_grandchild(node, child, 0);
1120*a749e09eSMichael Kruse node = detect_components(scc_graph, first, n, node);
1121*a749e09eSMichael Kruse node = isl_schedule_node_grandparent(node);
1122*a749e09eSMichael Kruse
1123*a749e09eSMichael Kruse return node;
1124*a749e09eSMichael Kruse }
1125*a749e09eSMichael Kruse
1126*a749e09eSMichael Kruse /* Return the local index of an SCC on which to split "scc_graph".
1127*a749e09eSMichael Kruse * Return scc_graph->n if no suitable split SCC can be found.
1128*a749e09eSMichael Kruse *
1129*a749e09eSMichael Kruse * In particular, look for an SCC that is involved in the largest number
1130*a749e09eSMichael Kruse * of edges. Splitting the graph on such an SCC has the highest chance
1131*a749e09eSMichael Kruse * of exposing independent SCCs in the remaining part(s).
1132*a749e09eSMichael Kruse * There is no point in splitting a chain of nodes,
1133*a749e09eSMichael Kruse * so return scc_graph->n if the entire graph forms a chain.
1134*a749e09eSMichael Kruse */
best_split(struct isl_scc_graph * scc_graph)1135*a749e09eSMichael Kruse static int best_split(struct isl_scc_graph *scc_graph)
1136*a749e09eSMichael Kruse {
1137*a749e09eSMichael Kruse int i;
1138*a749e09eSMichael Kruse int split = scc_graph->n;
1139*a749e09eSMichael Kruse int split_score = -1;
1140*a749e09eSMichael Kruse
1141*a749e09eSMichael Kruse for (i = 0; i < scc_graph->n; ++i) {
1142*a749e09eSMichael Kruse int n_fwd, n_bwd;
1143*a749e09eSMichael Kruse
1144*a749e09eSMichael Kruse n_fwd = scc_graph->edge_table[i]->n;
1145*a749e09eSMichael Kruse n_bwd = scc_graph->reverse_edge_table[i]->n;
1146*a749e09eSMichael Kruse if (n_fwd <= 1 && n_bwd <= 1)
1147*a749e09eSMichael Kruse continue;
1148*a749e09eSMichael Kruse if (split_score >= n_fwd + n_bwd)
1149*a749e09eSMichael Kruse continue;
1150*a749e09eSMichael Kruse split = i;
1151*a749e09eSMichael Kruse split_score = n_fwd + n_bwd;
1152*a749e09eSMichael Kruse }
1153*a749e09eSMichael Kruse
1154*a749e09eSMichael Kruse return split;
1155*a749e09eSMichael Kruse }
1156*a749e09eSMichael Kruse
1157*a749e09eSMichael Kruse /* Call isl_schedule_node_compute_finish_band on each of the clusters
1158*a749e09eSMichael Kruse * in scc_graph->c and update "node" to arrange for them to be executed
1159*a749e09eSMichael Kruse * in an order possibly involving set nodes that generalizes
1160*a749e09eSMichael Kruse * the topological order determined by the scc fields of the nodes
1161*a749e09eSMichael Kruse * in scc_graph->graph.
1162*a749e09eSMichael Kruse *
1163*a749e09eSMichael Kruse * First try and find a suitable SCC on which to split the graph.
1164*a749e09eSMichael Kruse * If no such SCC can be found then the graph forms a chain and
1165*a749e09eSMichael Kruse * it is handled as such.
1166*a749e09eSMichael Kruse * Otherwise, break up the graph into (at most) three parts,
1167*a749e09eSMichael Kruse * the SCCs before the selected SCC (in the topological order),
1168*a749e09eSMichael Kruse * the selected SCC itself, and
1169*a749e09eSMichael Kruse * the SCCs after the selected SCC.
1170*a749e09eSMichael Kruse * The first and last part (if they exist) are decomposed recursively and
1171*a749e09eSMichael Kruse * the three parts are combined in a sequence.
1172*a749e09eSMichael Kruse *
1173*a749e09eSMichael Kruse * Since the outermost node of the recursive pieces may also be a sequence,
1174*a749e09eSMichael Kruse * these potential sequence nodes are spliced into the top-level sequence node.
1175*a749e09eSMichael Kruse */
isl_scc_graph_decompose(struct isl_scc_graph * scc_graph,__isl_take isl_schedule_node * node)1176*a749e09eSMichael Kruse __isl_give isl_schedule_node *isl_scc_graph_decompose(
1177*a749e09eSMichael Kruse struct isl_scc_graph *scc_graph, __isl_take isl_schedule_node *node)
1178*a749e09eSMichael Kruse {
1179*a749e09eSMichael Kruse int i;
1180*a749e09eSMichael Kruse int split;
1181*a749e09eSMichael Kruse isl_union_set_list *filters;
1182*a749e09eSMichael Kruse
1183*a749e09eSMichael Kruse if (!scc_graph)
1184*a749e09eSMichael Kruse return isl_schedule_node_free(node);
1185*a749e09eSMichael Kruse
1186*a749e09eSMichael Kruse split = best_split(scc_graph);
1187*a749e09eSMichael Kruse
1188*a749e09eSMichael Kruse if (split == scc_graph->n)
1189*a749e09eSMichael Kruse return isl_scc_graph_chain(scc_graph, node);
1190*a749e09eSMichael Kruse
1191*a749e09eSMichael Kruse filters = extract_split_scc(scc_graph, split);
1192*a749e09eSMichael Kruse node = isl_schedule_node_insert_sequence(node, filters);
1193*a749e09eSMichael Kruse
1194*a749e09eSMichael Kruse isl_scc_graph_init_component(scc_graph);
1195*a749e09eSMichael Kruse
1196*a749e09eSMichael Kruse i = 0;
1197*a749e09eSMichael Kruse if (split > 0)
1198*a749e09eSMichael Kruse node = detect_components_at(scc_graph, 0, split, node, i++);
1199*a749e09eSMichael Kruse node = isl_schedule_node_grandchild(node, i++, 0);
1200*a749e09eSMichael Kruse node = isl_scc_graph_finish_band(scc_graph, node, split);
1201*a749e09eSMichael Kruse node = isl_schedule_node_grandparent(node);
1202*a749e09eSMichael Kruse if (split + 1 < scc_graph->n)
1203*a749e09eSMichael Kruse node = detect_components_at(scc_graph,
1204*a749e09eSMichael Kruse split + 1, scc_graph->n - (split + 1), node, i++);
1205*a749e09eSMichael Kruse
1206*a749e09eSMichael Kruse node = isl_schedule_node_sequence_splice_children(node);
1207*a749e09eSMichael Kruse
1208*a749e09eSMichael Kruse return node;
1209*a749e09eSMichael Kruse }
1210