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

source code of polly/lib/External/isl/isl_scheduler_scc.c