1210 lines · c
1/*2 * Copyright 2021 Sven Verdoolaege3 *4 * Use of this software is governed by the MIT license5 *6 * Written by Sven Verdoolaege7 */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 determined21 * by c->scc_cluster[i]. The nodes in this cluster all have22 * 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 be28 * a subset of those in "graph".29 * "graph_scc" maps the local index of an SCC in this isl_scc_graph30 * 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 SCC35 * in the component.36 * The index of this first SCC is always smaller than or equal37 * to the index of the SCC itself.38 * This field is initialized by isl_scc_graph_init_component and39 * used by detect_components.40 * During construction, "component" may also contain the index41 * of some other SCC in the component, but then it is necessarily42 * smaller than the index of the current SCC and the first SCC43 * can be reached by recursively looking up "component".44 * "size" contains the number of elements in the components45 * indexed by a component sequence number.46 *47 * "pos" is used locally inside isl_scc_graph_sort_components48 * to store the position of the next SCC within a component.49 * It is also used inside isl_scc_graph_sub to map50 * 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 original54 * topological order is preserved.55 *56 * "edge_table" contains "n" edge tables, one for each SCC57 * in this isl_scc_graph. Each table contains the local indices58 * of the SCCs that depend on this SCC. These local indices59 * 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 edge89 * 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, "%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, ", ");118 fprintf(stderr, "%d", scc_graph->graph_scc[i]);119 }120 fprintf(stderr, "\n");121 for (i = 0; i < scc_graph->n; ++i) {122 isl_hash_table_foreach(ctx, scc_graph->edge_table[i],123 &print_edge, &scc_graph->graph_scc[i]);124 }125 fprintf(stderr, "\n");126 for (i = 0; i < scc_graph->n; ++i) {127 isl_hash_table_foreach(ctx, scc_graph->reverse_edge_table[i],128 &print_edge, &scc_graph->graph_scc[i]);129 }130 fprintf(stderr, "\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, 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 scc_graph->reverse_edge_table[i]);152 }153 154 free(scc_graph->graph_scc);155 free(scc_graph->component);156 free(scc_graph->size);157 free(scc_graph->pos);158 free(scc_graph->sorted);159 free(scc_graph->edge_table);160 free(scc_graph->reverse_edge_table);161 isl_ctx_deref(scc_graph->ctx);162 free(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 entry169 * 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" corresponding178 * 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 entry186 * 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_none196 * if there is no such edge.197 *198 * The destination of the edge is encoded as a pointer199 * 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, dst);212 return isl_hash_table_find(ctx, edge_table[src], hash,213 &is_scc_node, val, reserve);214}215 216/* Remove the edge between the SCCs with local indices "src" and217 * "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 empty222 * 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, scc_graph->edge_table,231 src, dst, 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, scc_graph->edge_table[src], 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 corresponding256 * 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(data->scc_graph, 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(scc_graph->ctx, scc_graph->edge_table[i],297 &extract_dst, &data) < 0)298 goto error;299 if (isl_sort(next, n_next, sizeof(int), &cmp_int, NULL) < 0)300 goto error;301 return next;302error:303 free(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 SCC323 * 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(data->scc_graph, *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 one346 * 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(edge_table[pos]);359 pos = isl_scc_graph_local_index(data->scc_graph, 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, edge_table[pos],372 &recurse_foreach_reachable, 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, data->src, pos);387 return isl_bool_not(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 reached395 * 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 reached398 * from such a node for which there is also an edge from "i"399 * then this edge can be removed because this node can also400 * 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 considered403 * 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, next[j]) < 0)432 break;433 free(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" and442 * "dst" in "scc_graph".443 *444 * If the edge already appeared in the table, then it is simply overwritten445 * 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, 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->src462 * 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(data->scc_graph, *entry);470 return isl_scc_graph_add_edge(data->scc_graph,471 data->scc_graph->reverse_edge_table, dst, data->src);472}473 474/* Add an (inverse) edge to scc_graph->reverse_edge_table475 * 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, scc_graph->edge_table[data.src],490 &add_reverse, &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 between497 * 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 global501 * 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, 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, 2);554 scc_graph->reverse_edge_table[i] = isl_hash_table_alloc(ctx, 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 determined565 * by c->scc_cluster[i]. The nodes in this cluster all have566 * their "scc" field set to i.567 *568 * The initial isl_scc_graph has as many SCCs as "graph" and569 * their local indices are the same as their indices in "graph".570 *571 * Add edges between different SCCs for each (conditional) validity edge572 * between nodes in those SCCs, remove transitive edges and573 * 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, 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, graph->edge_table[isl_edge_validity],589 &add_scc_edge, scc_graph) < 0)590 return isl_scc_graph_free(scc_graph);591 if (isl_hash_table_foreach(ctx,592 graph->edge_table[isl_edge_conditional_validity],593 &add_scc_edge, 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 edges607 * 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 edge616 * 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 components619 * in the region handled by detect_components, but there may620 * be edges to nodes outside this region.621 * The components therefore need to be initialized for all nodes622 * 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(data->scc_graph, *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(sub, sub->edge_table, sub_src, sub_dst);639}640 641/* Construct a subgraph of "scc_graph" for the components642 * consisting of the "n" SCCs with local indices in "pos".643 * These SCCs have the same value in scc_graph->component and644 * this value is different from that of any other SCC.645 *646 * The forward edges with source and destination in the component647 * are copied from "scc_graph".648 * The local index in the subgraph corresponding to a local index649 * 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, scc_graph->graph, 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, scc_graph->edge_table[pos[i]],679 ©_edge, &data) < 0)680 return isl_scc_graph_free(sub);681 }682 683 sub = isl_scc_graph_add_reverse_edges(sub);684 685 return sub;686}687 688/* Return a union of universe domains corresponding to the nodes689 * 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(scc_graph->ctx, scc_graph->graph,695 scc_graph->graph_scc[pos]);696}697 698/* Construct a filter corresponding to a sequence of "n" local SCC indices699 * determined by successive calls to "el",700 * add this filter to "list" and701 * 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(scc_graph->ctx);712 for (i = 0; i < n; ++i)713 dom = isl_union_set_union(dom,714 isl_scc_graph_extract_local_scc(scc_graph, el(i, user)));715 716 return isl_union_set_list_add(list, dom);717}718 719/* add_scc_seq callback that, on successive calls, returns a sequence720 * 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 indices730 * 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, &offset, &first, n, list);737}738 739/* add_scc_seq callback that, on successive calls, returns the sequence740 * 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 indices750 * 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, &at, seq, n, list);757}758 759/* Extract out a list of filters for a sequence node that splits760 * 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, and765 * 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(scc_graph->ctx, 3);774 if (pos > 0)775 filters = isl_scc_graph_add_scc_seq(scc_graph, 0, pos, filters);776 dom = isl_scc_graph_extract_local_scc(scc_graph, pos);777 filters = isl_union_set_list_add(filters, dom);778 if (pos + 1 < scc_graph->n)779 filters = isl_scc_graph_add_scc_seq(scc_graph,780 pos + 1, scc_graph->n - (pos + 1), filters);781 return filters;782}783 784/* Call isl_schedule_node_compute_finish_band on the cluster785 * corresponding to the SCC with local index "pos".786 *787 * First obtain the corresponding SCC index in scc_graph->graph and788 * 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 &c->cluster[cluster], 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 clusters804 * in scc_graph->c and update "node" to arrange for them to be executed805 * 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(scc_graph->ctx, scc_graph->n);815 for (i = 0; i < scc_graph->n; ++i) {816 dom = isl_scc_graph_extract_local_scc(scc_graph, i);817 filters = isl_union_set_list_add(filters, 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, i, 0);824 node = isl_scc_graph_finish_band(scc_graph, node, i);825 node = isl_schedule_node_grandparent(node);826 }827 828 return node;829}830 831/* Recursively call isl_scc_graph_decompose on a subgraph832 * 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 and836 * 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[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(sub, node);850 isl_scc_graph_free(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 split859 * also needs to be assigned a component because the components860 * 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" and871 * 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 nothing885 * 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 entire889 * component now (eventually) points to the other component.890 * Otherwise, the earlier parts of the component still need891 * 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 already895 * 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, b, a);906 else907 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 components924 * of data->src and the node represented by "entry", provided925 * 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(data->scc_graph, *entry);933 if (dst >= data->end)934 return isl_stat_ok;935 936 isl_scc_graph_merge_src_dst(data->scc_graph, data->src, dst);937 938 return isl_stat_ok;939}940 941/* Merge components of the "n" SCCs starting at "first" that are connected942 * 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, scc_graph->edge_table[data.src],956 &merge_src_dst, &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" according964 * to component, store them in scc_graph->sorted and965 * 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 within968 * 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 component972 * points to the first SCC in the component, whereas973 * before this function is called, some SCCs may only point974 * to some other SCC in the component with a smaller index.975 *976 * Internally, the sizes of the components are first stored977 * at indices corresponding to the first SCC in the component.978 * They are subsequently moved into consecutive positions979 * while reordering the local indices.980 * This reordering is performed by first determining the position981 * of the first SCC in each component and982 * then putting the "n" local indices in the right position983 * according to the component, preserving the topological order984 * 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 else1003 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 up1023 * the graph into "n_component" components.1024 * "first" is the initial position in "scc_graph" where information1025 * about the components is stored.1026 * In particular, the first "n_component" entries of scc_graph->size1027 * 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_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 &sorted[sum], n, filters);1049 sum += n;1050 }1051 1052 return filters;1053}1054 1055/* Detect components in the subgraph consisting of the "n" SCCs1056 * with local index starting at "first" and further decompose them,1057 * calling isl_schedule_node_compute_finish_band on each1058 * of the corresponding clusters.1059 *1060 * If there is only one SCC, then isl_schedule_node_compute_finish_band1061 * can be called directly.1062 * Otherwise, determine the components and rearrange the local indices1063 * according to component, but preserving the topological order within1064 * each component, in scc_graph->sorted. The sizes of the components1065 * are stored in scc_graph->size.1066 * If there is only one component, it can be further decomposed1067 * directly by a call to recurse().1068 * Otherwise, introduce a set node separating the components and1069 * 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, 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, &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, i, 0);1101 node = recurse(scc_graph, &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 each1113 * 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, child, 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 number1130 * of edges. Splitting the graph on such an SCC has the highest chance1131 * 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 clusters1158 * in scc_graph->c and update "node" to arrange for them to be executed1159 * in an order possibly involving set nodes that generalizes1160 * the topological order determined by the scc fields of the nodes1161 * 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 and1165 * 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, and1169 * the SCCs after the selected SCC.1170 * The first and last part (if they exist) are decomposed recursively and1171 * 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, 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, 0, split, node, i++);1199 node = isl_schedule_node_grandchild(node, i++, 0);1200 node = isl_scc_graph_finish_band(scc_graph, node, split);1201 node = isl_schedule_node_grandparent(node);1202 if (split + 1 < scc_graph->n)1203 node = detect_components_at(scc_graph,1204 split + 1, scc_graph->n - (split + 1), node, i++);1205 1206 node = isl_schedule_node_sequence_splice_children(node);1207 1208 return node;1209}1210