Lines Matching refs:graph
21 /* Initialize the clustering data structure "c" from "graph".
23 * In particular, allocate memory, extract the SCCs from "graph"
30 struct isl_sched_graph *graph)
34 c->n = graph->scc;
45 if (isl_sched_graph_extract_sub_graph(ctx, graph,
80 /* Should we refrain from merging the cluster in "graph" with
84 static int bad_cluster(struct isl_sched_graph *graph)
86 return graph->n_row < graph->maxvar &&
87 graph->n_total_row == graph->band_start;
99 /* Return the index of an edge in "graph" that can be used to merge
101 * Return graph->n_edge if no such edge can be found.
114 static int find_proximity(struct isl_sched_graph *graph,
117 int i, best = graph->n_edge, best_dist, best_weight;
119 for (i = 0; i < graph->n_edge; ++i) {
120 struct isl_sched_edge *edge = &graph->edge[i];
139 if (best < graph->n_edge) {
155 * "graph" is the dependence graph in which a strongly connected
161 struct isl_sched_graph *graph;
179 struct isl_sched_graph *graph = data->graph;
186 if (scc_cluster[graph->node[i].scc] == scc_cluster[graph->node[j].scc])
189 return isl_sched_graph_has_validity_edge(graph, &graph->node[j],
190 &graph->node[i]);
194 * connected by the edge in "graph" with index "edge", or to any
215 static isl_stat mark_merge_sccs(isl_ctx *ctx, struct isl_sched_graph *graph,
225 data.graph = graph;
227 data.src = graph->edge[edge].src - graph->node;
228 data.dst = graph->edge[edge].dst - graph->node;
230 g = isl_tarjan_graph_component(ctx, graph->n, data.dst,
245 int scc = graph->node[g->order[i]].scc;
289 /* Collect the domain of the graph for merging clusters.
296 struct isl_sched_graph *graph, struct isl_clustering *c)
305 for (i = 0; i < graph->scc; ++i) {
323 struct isl_sched_graph *graph, struct isl_clustering *c)
331 for (i = 0; i < graph->scc; ++i) {
471 * to "sc" corresponding to all edges in "graph" between nodes that
475 struct isl_sched_graph *graph, int *scc_in_merge,
481 for (i = 0; i < graph->n_edge; ++i) {
482 struct isl_sched_edge *edge = &graph->edge[i];
494 /* Construct a dependence graph for scheduling clusters with respect
496 * In particular, the nodes of the graph correspond to the schedule
501 * by transforming the edges in "graph" to the domain.
502 * Then initialize a dependence graph for scheduling from these
505 static isl_stat init_merge_graph(isl_ctx *ctx, struct isl_sched_graph *graph,
513 domain = collect_domain(ctx, graph, c);
517 cluster_map = collect_cluster_map(ctx, graph, c);
518 sc = collect_constraints(graph, c->scc_in_merge, cluster_map, sc);
649 /* Return the number of coincident dimensions in the current band of "graph",
650 * where the nodes of "graph" are assumed to be scheduled by a single band.
652 static int get_n_coincident(struct isl_sched_graph *graph)
656 for (i = graph->band_start; i < graph->n_total_row; ++i)
657 if (!graph->node[0].coincident[i])
660 return i - graph->band_start;
813 /* Does the edge "edge" from "graph" have bounded dependence distances
814 * in the merged graph "merge_graph" of a selection of clusters in "c"?
840 struct isl_sched_graph *graph, struct isl_clustering *c,
862 n_slack -= graph->max_weight + 1;
885 edge->weight -= graph->max_weight + 1;
898 * "graph" is the original dependence graph, while "c" records
908 struct isl_sched_graph *graph, struct isl_clustering *c,
913 for (i = 0; i < graph->n_edge; ++i) {
914 struct isl_sched_edge *edge = &graph->edge[i];
926 bounded = has_bounded_distances(ctx, edge, graph, c,
937 * "graph" is the original dependence graph, while "c" records
953 static isl_bool ok_to_merge(isl_ctx *ctx, struct isl_sched_graph *graph,
971 return ok_to_merge_proximity(ctx, graph, c, merge_graph);
1015 * schedule of the nodes in "graph".
1024 static isl_stat transform(isl_ctx *ctx, struct isl_sched_graph *graph,
1031 start = graph->band_start;
1032 n = graph->n_total_row - start;
1037 for (i = 0; i < graph->n; ++i) {
1038 struct isl_sched_node *node = &graph->node[i];
1050 graph->n_total_row -= n;
1051 graph->n_row -= n;
1052 graph->n_total_row += n_new;
1053 graph->n_row += n_new;
1102 * Construct a dependence graph with a space for each cluster and
1105 * Construct a cluster schedule in this cluster dependence graph and
1130 static isl_bool try_merge(isl_ctx *ctx, struct isl_sched_graph *graph,
1136 if (init_merge_graph(ctx, graph, c, &merge_graph) < 0)
1145 merged = ok_to_merge(ctx, graph, c, &merge_graph);
1169 static int any_no_merge(struct isl_sched_graph *graph, int *scc_in_merge,
1174 for (i = 0; i < graph->n_edge; ++i) {
1175 struct isl_sched_edge *edge = &graph->edge[i];
1184 merge_edge->weight -= graph->max_weight + 1;
1192 /* Merge the two clusters in "c" connected by the edge in "graph"
1211 struct isl_sched_graph *graph, int edge, struct isl_clustering *c)
1214 int edge_weight = graph->edge[edge].weight;
1216 if (mark_merge_sccs(ctx, graph, edge, c) < 0)
1219 if (any_no_merge(graph, c->scc_in_merge, &graph->edge[edge]))
1222 merged = try_merge(ctx, graph, c);
1225 if (!merged && edge_weight == graph->edge[edge].weight)
1226 graph->edge[edge].no_merge = 1;
1247 * Both nodes have been derived from the same node in a common parent graph.
1249 * in the parent graph, there is no need to also swap this field.
1272 * is assumed to be same as the order in the original "graph".
1277 static isl_stat copy_partial(struct isl_sched_graph *graph,
1286 for (i = 0; i < graph->n; ++i) {
1290 if (graph->node[i].cluster != pos)
1292 s = graph->node[i].scc;
1309 struct isl_sched_graph *graph = user;
1311 if (graph->node[i].cluster == graph->node[j].cluster)
1313 return isl_sched_graph_has_validity_edge(graph, &graph->node[j],
1314 &graph->node[i]);
1317 /* Extract the merged clusters of SCCs in "graph", sort them, and
1332 static isl_stat extract_clusters(isl_ctx *ctx, struct isl_sched_graph *graph,
1337 for (i = 0; i < graph->n; ++i)
1338 graph->node[i].cluster = c->scc_cluster[graph->node[i].scc];
1340 for (i = 0; i < graph->scc; ++i) {
1343 if (isl_sched_graph_extract_sub_graph(ctx, graph,
1349 if (copy_partial(graph, c, i) < 0)
1353 if (isl_sched_graph_detect_ccs(ctx, graph,
1356 for (i = 0; i < graph->n; ++i)
1357 c->scc_cluster[graph->node[i].scc] = graph->node[i].cluster;
1362 /* Compute weights on the proximity edges of "graph" that can
1367 * Store the maximum of the computed weights in graph->max_weight.
1378 static isl_stat compute_weights(struct isl_sched_graph *graph,
1383 graph->max_weight = 0;
1385 for (i = 0; i < graph->n_edge; ++i) {
1386 struct isl_sched_edge *edge = &graph->edge[i];
1429 if (edge->weight > graph->max_weight)
1430 graph->max_weight = edge->weight;
1439 * determined by the scc fields of the nodes in "graph".
1441 * Note that at this stage, there are graph->scc clusters and
1446 * using this graph.
1449 __isl_take isl_schedule_node *node, struct isl_sched_graph *graph,
1457 scc_graph = isl_scc_graph_from_sched_graph(ctx, graph, c);
1466 * fields of the nodes in "graph".
1471 * the SCC at position 0 in the original graph and is therefore also
1484 __isl_take isl_schedule_node *node, struct isl_sched_graph *graph,
1491 if (graph->scc == 1)
1494 if (graph->scc > 2)
1495 return finish_bands_decompose(node, graph, c);
1499 filters = isl_sched_graph_extract_sccs(ctx, graph);
1502 for (i = 0; i < graph->scc; ++i) {
1513 /* Compute a schedule for a connected dependence graph by first considering
1514 * each strongly connected component (SCC) in the graph separately and then
1531 __isl_take isl_schedule_node *node, struct isl_sched_graph *graph)
1539 if (clustering_init(ctx, &c, graph) < 0)
1542 if (compute_weights(graph, &c) < 0)
1546 i = find_proximity(graph, &c);
1549 if (i >= graph->n_edge)
1551 if (merge_clusters_along_edge(ctx, graph, i, &c) < 0)
1555 if (extract_clusters(ctx, graph, &c) < 0)
1558 graph, &c);
Indexes created Mon Oct 19 00:25:19 UTC 2026