84 	struct isl_scc_graph *scc_graph;  member
106 void isl_scc_graph_dump(struct isl_scc_graph *scc_graph)  in isl_scc_graph_dump()  argument
111 	if (!scc_graph)  in isl_scc_graph_dump()
114 	ctx = scc_graph->ctx;  in isl_scc_graph_dump()
115 	for (i = 0; i < scc_graph->n; ++i) {  in isl_scc_graph_dump()
118 		fprintf(stderr, "%d", scc_graph->graph_scc[i]);  in isl_scc_graph_dump()
121 	for (i = 0; i < scc_graph->n; ++i) {  in isl_scc_graph_dump()
122 		isl_hash_table_foreach(ctx, scc_graph->edge_table[i],  in isl_scc_graph_dump()
123 			&print_edge, &scc_graph->graph_scc[i]);  in isl_scc_graph_dump()
126 	for (i = 0; i < scc_graph->n; ++i) {  in isl_scc_graph_dump()
127 		isl_hash_table_foreach(ctx, scc_graph->reverse_edge_table[i],  in isl_scc_graph_dump()
128 			&print_edge, &scc_graph->graph_scc[i]);  in isl_scc_graph_dump()
135 struct isl_scc_graph *isl_scc_graph_free(struct isl_scc_graph *scc_graph)  in isl_scc_graph_free()  argument
140 	if (!scc_graph)  in isl_scc_graph_free()
143 	ctx = scc_graph->ctx;  in isl_scc_graph_free()
144 	if (scc_graph->edge_table) {  in isl_scc_graph_free()
145 		for (i = 0; i < scc_graph->n; ++i)  in isl_scc_graph_free()
146 			isl_hash_table_free(ctx, scc_graph->edge_table[i]);  in isl_scc_graph_free()
148 	if (scc_graph->reverse_edge_table) {  in isl_scc_graph_free()
149 		for (i = 0; i < scc_graph->n; ++i)  in isl_scc_graph_free()
151 					    scc_graph->reverse_edge_table[i]);  in isl_scc_graph_free()
154 	free(scc_graph->graph_scc);  in isl_scc_graph_free()
155 	free(scc_graph->component);  in isl_scc_graph_free()
156 	free(scc_graph->size);  in isl_scc_graph_free()
157 	free(scc_graph->pos);  in isl_scc_graph_free()
158 	free(scc_graph->sorted);  in isl_scc_graph_free()
159 	free(scc_graph->edge_table);  in isl_scc_graph_free()
160 	free(scc_graph->reverse_edge_table);  in isl_scc_graph_free()
161 	isl_ctx_deref(scc_graph->ctx);  in isl_scc_graph_free()
162 	free(scc_graph);  in isl_scc_graph_free()
171 static void *isl_scc_graph_encode_local_index(struct isl_scc_graph *scc_graph,  in isl_scc_graph_encode_local_index()  argument
174 	return &scc_graph->graph_scc[pos];  in isl_scc_graph_encode_local_index()
180 static int isl_scc_graph_local_index(struct isl_scc_graph *scc_graph, int *data)  in isl_scc_graph_local_index()  argument
182 	return data - &scc_graph->graph_scc[0];  in isl_scc_graph_local_index()
202 	struct isl_scc_graph *scc_graph, struct isl_hash_table **edge_table,  in isl_scc_graph_find_edge()  argument
209 	ctx = scc_graph->ctx;  in isl_scc_graph_find_edge()
211 	val = isl_scc_graph_encode_local_index(scc_graph, dst);  in isl_scc_graph_find_edge()
224 static isl_bool isl_scc_graph_remove_edge(struct isl_scc_graph *scc_graph,  in isl_scc_graph_remove_edge()  argument
230 	edge_entry = isl_scc_graph_find_edge(scc_graph, scc_graph->edge_table,  in isl_scc_graph_remove_edge()
237 	ctx = scc_graph->ctx;  in isl_scc_graph_remove_edge()
238 	isl_hash_table_remove(ctx, scc_graph->edge_table[src], edge_entry);  in isl_scc_graph_remove_edge()
250 	struct isl_scc_graph *scc_graph;  member
263 	data->next[data->n++] = isl_scc_graph_local_index(data->scc_graph, dst);  in extract_dst()
283 static int *next_nodes(struct isl_scc_graph *scc_graph, int i)  in next_nodes()  argument
289 	n_next = scc_graph->edge_table[i]->n;  in next_nodes()
290 	next = isl_alloc_array(scc_graph->ctx, int, n_next);  in next_nodes()
293 	data.scc_graph = scc_graph;  in next_nodes()
296 	if (isl_hash_table_foreach(scc_graph->ctx, scc_graph->edge_table[i],  in next_nodes()
314 	struct isl_scc_graph *scc_graph;  member
332 	pos = isl_scc_graph_local_index(data->scc_graph, *entry);  in recurse_foreach_reachable()
352 	struct isl_hash_table **edge_table = data->scc_graph->edge_table;  in foreach_reachable()
359 		pos = isl_scc_graph_local_index(data->scc_graph, entry->data);  in foreach_reachable()
370 	ctx = data->scc_graph->ctx;  in foreach_reachable()
383 	struct isl_scc_graph *scc_graph = data->scc_graph;  in elim_or_next()  local
386 	removed = isl_scc_graph_remove_edge(scc_graph, data->src, pos);  in elim_or_next()
407 	struct isl_scc_graph *scc_graph)  in isl_scc_graph_reduce()  argument
411 		.scc_graph = scc_graph,  in isl_scc_graph_reduce()
417 	elim_data.scc_graph = scc_graph;  in isl_scc_graph_reduce()
418 	for (i = scc_graph->n - 3; i >= 0; --i) {  in isl_scc_graph_reduce()
422 		n_next = scc_graph->edge_table[i]->n;  in isl_scc_graph_reduce()
425 		next = next_nodes(scc_graph, i);  in isl_scc_graph_reduce()
427 			return isl_scc_graph_free(scc_graph);  in isl_scc_graph_reduce()
435 			return isl_scc_graph_free(scc_graph);  in isl_scc_graph_reduce()
438 	return scc_graph;  in isl_scc_graph_reduce()
447 static isl_stat isl_scc_graph_add_edge(struct isl_scc_graph *scc_graph,  in isl_scc_graph_add_edge()  argument
453 		isl_scc_graph_find_edge(scc_graph, edge_table, src, dst, 1);  in isl_scc_graph_add_edge()
456 	edge_entry->data = &scc_graph->graph_scc[dst];  in isl_scc_graph_add_edge()
469 	dst = isl_scc_graph_local_index(data->scc_graph, *entry);  in add_reverse()
470 	return isl_scc_graph_add_edge(data->scc_graph,  in add_reverse()
471 			data->scc_graph->reverse_edge_table, dst, data->src);  in add_reverse()
478 	struct isl_scc_graph *scc_graph)  in isl_scc_graph_add_reverse_edges()  argument
483 	if (!scc_graph)  in isl_scc_graph_add_reverse_edges()
486 	ctx = scc_graph->ctx;  in isl_scc_graph_add_reverse_edges()
487 	data.scc_graph = scc_graph;  in isl_scc_graph_add_reverse_edges()
488 	for (data.src = 0; data.src < scc_graph->n; ++data.src) {  in isl_scc_graph_add_reverse_edges()
489 		if (isl_hash_table_foreach(ctx, scc_graph->edge_table[data.src],  in isl_scc_graph_add_reverse_edges()
491 			return isl_scc_graph_free(scc_graph);  in isl_scc_graph_add_reverse_edges()
493 	return scc_graph;  in isl_scc_graph_add_reverse_edges()
506 	struct isl_scc_graph *scc_graph = user;  in add_scc_edge()  local
513 	return isl_scc_graph_add_edge(scc_graph, scc_graph->edge_table,  in add_scc_edge()
526 	struct isl_scc_graph *scc_graph;  in isl_scc_graph_alloc()  local
528 	scc_graph = isl_alloc_type(ctx, struct isl_scc_graph);  in isl_scc_graph_alloc()
529 	if (!scc_graph)  in isl_scc_graph_alloc()
532 	scc_graph->ctx = ctx;  in isl_scc_graph_alloc()
534 	scc_graph->graph = graph;  in isl_scc_graph_alloc()
535 	scc_graph->c = c;  in isl_scc_graph_alloc()
537 	scc_graph->n = n;  in isl_scc_graph_alloc()
538 	scc_graph->graph_scc = isl_alloc_array(ctx, int, n);  in isl_scc_graph_alloc()
539 	scc_graph->component = isl_alloc_array(ctx, int, n);  in isl_scc_graph_alloc()
540 	scc_graph->size = isl_alloc_array(ctx, int, n);  in isl_scc_graph_alloc()
541 	scc_graph->pos = isl_alloc_array(ctx, int, n);  in isl_scc_graph_alloc()
542 	scc_graph->sorted = isl_alloc_array(ctx, int, n);  in isl_scc_graph_alloc()
543 	scc_graph->edge_table =  in isl_scc_graph_alloc()
545 	scc_graph->reverse_edge_table =  in isl_scc_graph_alloc()
547 	if (!scc_graph->graph_scc || !scc_graph->component ||  in isl_scc_graph_alloc()
548 	    !scc_graph->size || !scc_graph->pos || !scc_graph->sorted ||  in isl_scc_graph_alloc()
549 	    !scc_graph->edge_table || !scc_graph->reverse_edge_table)  in isl_scc_graph_alloc()
550 		return isl_scc_graph_free(scc_graph);  in isl_scc_graph_alloc()
553 		scc_graph->edge_table[i] = isl_hash_table_alloc(ctx, 2);  in isl_scc_graph_alloc()
554 		scc_graph->reverse_edge_table[i] = isl_hash_table_alloc(ctx, 2);  in isl_scc_graph_alloc()
555 		if (!scc_graph->edge_table[i] ||  in isl_scc_graph_alloc()
556 		    !scc_graph->reverse_edge_table[i])  in isl_scc_graph_alloc()
557 			return isl_scc_graph_free(scc_graph);  in isl_scc_graph_alloc()
560 	return scc_graph;  in isl_scc_graph_alloc()
579 	struct isl_scc_graph *scc_graph;  in isl_scc_graph_from_sched_graph()  local
581 	scc_graph = isl_scc_graph_alloc(ctx, graph->scc, graph, c);  in isl_scc_graph_from_sched_graph()
582 	if (!scc_graph)  in isl_scc_graph_from_sched_graph()
586 		scc_graph->graph_scc[i] = i;  in isl_scc_graph_from_sched_graph()
589 					&add_scc_edge, scc_graph) < 0)  in isl_scc_graph_from_sched_graph()
590 		return isl_scc_graph_free(scc_graph);  in isl_scc_graph_from_sched_graph()
593 			    &add_scc_edge, scc_graph) < 0)  in isl_scc_graph_from_sched_graph()
594 		return isl_scc_graph_free(scc_graph);  in isl_scc_graph_from_sched_graph()
596 	scc_graph = isl_scc_graph_reduce(scc_graph);  in isl_scc_graph_from_sched_graph()
597 	scc_graph = isl_scc_graph_add_reverse_edges(scc_graph);  in isl_scc_graph_from_sched_graph()
599 	return scc_graph;  in isl_scc_graph_from_sched_graph()
610 	struct isl_scc_graph *scc_graph;  member
627 	struct isl_scc_graph *scc_graph = data->scc_graph;  in copy_edge()  local
631 	dst = isl_scc_graph_local_index(data->scc_graph, *entry);  in copy_edge()
632 	if (scc_graph->component[dst] != scc_graph->component[data->src])  in copy_edge()
635 	sub_src = scc_graph->pos[data->src];  in copy_edge()
636 	sub_dst = scc_graph->pos[dst];  in copy_edge()
652 static struct isl_scc_graph *isl_scc_graph_sub(struct isl_scc_graph *scc_graph,  in isl_scc_graph_sub()  argument
660 	if (!scc_graph)  in isl_scc_graph_sub()
663 	ctx = scc_graph->ctx;  in isl_scc_graph_sub()
664 	sub = isl_scc_graph_alloc(ctx, n, scc_graph->graph, scc_graph->c);  in isl_scc_graph_sub()
669 		sub->graph_scc[i] = scc_graph->graph_scc[pos[i]];  in isl_scc_graph_sub()
672 		scc_graph->pos[pos[i]] = i;  in isl_scc_graph_sub()
674 	data.scc_graph = scc_graph;  in isl_scc_graph_sub()
678 		if (isl_hash_table_foreach(ctx, scc_graph->edge_table[pos[i]],  in isl_scc_graph_sub()
692 	struct isl_scc_graph *scc_graph, int pos)  in isl_scc_graph_extract_local_scc()  argument
694 	return isl_sched_graph_extract_scc(scc_graph->ctx, scc_graph->graph,  in isl_scc_graph_extract_local_scc()
695 					scc_graph->graph_scc[pos]);  in isl_scc_graph_extract_local_scc()
704 	struct isl_scc_graph *scc_graph,  in add_scc_seq()  argument
711 	dom = isl_union_set_empty_ctx(scc_graph->ctx);  in add_scc_seq()
714 		    isl_scc_graph_extract_local_scc(scc_graph, el(i, user)));  in add_scc_seq()
733 	struct isl_scc_graph *scc_graph, int first, int n,  in isl_scc_graph_add_scc_seq()  argument
736 	return add_scc_seq(scc_graph, &offset, &first, n, list);  in isl_scc_graph_add_scc_seq()
753 	struct isl_scc_graph *scc_graph, int *seq, int n,  in isl_scc_graph_add_scc_indirect_seq()  argument
756 	return add_scc_seq(scc_graph, &at, seq, n, list);  in isl_scc_graph_add_scc_indirect_seq()
768 	struct isl_scc_graph *scc_graph, int pos)  in extract_split_scc()  argument
773 	filters = isl_union_set_list_alloc(scc_graph->ctx, 3);  in extract_split_scc()
775 		filters = isl_scc_graph_add_scc_seq(scc_graph, 0, pos, filters);  in extract_split_scc()
776 	dom = isl_scc_graph_extract_local_scc(scc_graph, pos);  in extract_split_scc()
778 	if (pos + 1 < scc_graph->n)  in extract_split_scc()
779 		filters = isl_scc_graph_add_scc_seq(scc_graph,  in extract_split_scc()
780 				pos + 1, scc_graph->n - (pos + 1), filters);  in extract_split_scc()
791 	struct isl_scc_graph *scc_graph, __isl_take isl_schedule_node *node,  in isl_scc_graph_finish_band()  argument
794 	struct isl_clustering *c = scc_graph->c;  in isl_scc_graph_finish_band()
797 	cluster = c->scc_cluster[scc_graph->graph_scc[pos]];  in isl_scc_graph_finish_band()
808 	struct isl_scc_graph *scc_graph, __isl_take isl_schedule_node *node)  in isl_scc_graph_chain()  argument
814 	filters = isl_union_set_list_alloc(scc_graph->ctx, scc_graph->n);  in isl_scc_graph_chain()
815 	for (i = 0; i < scc_graph->n; ++i) {  in isl_scc_graph_chain()
816 		dom = isl_scc_graph_extract_local_scc(scc_graph, i);  in isl_scc_graph_chain()
822 	for (i = 0; i < scc_graph->n; ++i) {  in isl_scc_graph_chain()
824 		node = isl_scc_graph_finish_band(scc_graph, node, i);  in isl_scc_graph_chain()
838 static __isl_give isl_schedule_node *recurse(struct isl_scc_graph *scc_graph,  in recurse()  argument
844 		return isl_scc_graph_finish_band(scc_graph, node, pos[0]);  in recurse()
846 	sub = isl_scc_graph_sub(scc_graph, pos, n);  in recurse()
862 static void isl_scc_graph_init_component(struct isl_scc_graph *scc_graph)  in isl_scc_graph_init_component()  argument
866 	for (i = 0; i < scc_graph->n; ++i)  in isl_scc_graph_init_component()
867 		scc_graph->component[i] = i;  in isl_scc_graph_init_component()
898 static void isl_scc_graph_merge_src_dst(struct isl_scc_graph *scc_graph,  in isl_scc_graph_merge_src_dst()  argument
901 	int *component = scc_graph->component;  in isl_scc_graph_merge_src_dst()
918 	struct isl_scc_graph *scc_graph;  member
932 	dst = isl_scc_graph_local_index(data->scc_graph, *entry);  in merge_src_dst()
936 	isl_scc_graph_merge_src_dst(data->scc_graph, data->src, dst);  in merge_src_dst()
944 static isl_stat isl_scc_graph_merge_components(struct isl_scc_graph *scc_graph,  in isl_scc_graph_merge_components()  argument
949 	isl_ctx *ctx = scc_graph->ctx;  in isl_scc_graph_merge_components()
951 	data.scc_graph = scc_graph;  in isl_scc_graph_merge_components()
955 		if (isl_hash_table_foreach(ctx, scc_graph->edge_table[data.src],  in isl_scc_graph_merge_components()
986 static int isl_scc_graph_sort_components(struct isl_scc_graph *scc_graph,  in isl_scc_graph_sort_components()  argument
991 	int *component = scc_graph->component;  in isl_scc_graph_sort_components()
992 	int *size = scc_graph->size;  in isl_scc_graph_sort_components()
993 	int *pos = scc_graph->pos;  in isl_scc_graph_sort_components()
994 	int *sorted = scc_graph->sorted;  in isl_scc_graph_sort_components()
1032 	struct isl_scc_graph *scc_graph, int first, int n_component)  in extract_components()  argument
1036 	int *size = scc_graph->size;  in extract_components()
1037 	int *sorted = scc_graph->sorted;  in extract_components()
1038 	isl_ctx *ctx = scc_graph->ctx;  in extract_components()
1047 		filters = isl_scc_graph_add_scc_indirect_seq(scc_graph,  in extract_components()
1072 	struct isl_scc_graph *scc_graph, int first, int n,  in detect_components()  argument
1076 	int *size = scc_graph->size;  in detect_components()
1077 	int *sorted = scc_graph->sorted;  in detect_components()
1083 		return isl_scc_graph_finish_band(scc_graph, node, first);  in detect_components()
1085 	if (isl_scc_graph_merge_components(scc_graph, first, n) < 0)  in detect_components()
1088 	n_component = isl_scc_graph_sort_components(scc_graph, first, n);  in detect_components()
1090 		return recurse(scc_graph, &sorted[first], n, node);  in detect_components()
1092 	filters = extract_components(scc_graph, first, n_component);  in detect_components()
1101 		node = recurse(scc_graph, &sorted[sum], n, node);  in detect_components()
1116 	struct isl_scc_graph *scc_graph, int first, int n,  in detect_components_at()  argument
1120 	node = detect_components(scc_graph, first, n, node);  in detect_components_at()
1135 static int best_split(struct isl_scc_graph *scc_graph)  in best_split()  argument
1138 	int split = scc_graph->n;  in best_split()
1141 	for (i = 0; i < scc_graph->n; ++i) {  in best_split()
1144 		n_fwd = scc_graph->edge_table[i]->n;  in best_split()
1145 		n_bwd = scc_graph->reverse_edge_table[i]->n;  in best_split()
1177 	struct isl_scc_graph *scc_graph, __isl_take isl_schedule_node *node)  in isl_scc_graph_decompose()  argument
1183 	if (!scc_graph)  in isl_scc_graph_decompose()
1186 	split = best_split(scc_graph);  in isl_scc_graph_decompose()
1188 	if (split == scc_graph->n)  in isl_scc_graph_decompose()
1189 		return isl_scc_graph_chain(scc_graph, node);  in isl_scc_graph_decompose()
1191 	filters = extract_split_scc(scc_graph, split);  in isl_scc_graph_decompose()
1194 	isl_scc_graph_init_component(scc_graph);  in isl_scc_graph_decompose()
1198 		node = detect_components_at(scc_graph, 0, split, node, i++);  in isl_scc_graph_decompose()
1200 	node = isl_scc_graph_finish_band(scc_graph, node, split);  in isl_scc_graph_decompose()
1202 	if (split + 1 < scc_graph->n)  in isl_scc_graph_decompose()
1203 		node = detect_components_at(scc_graph,  in isl_scc_graph_decompose()
1204 			    split + 1, scc_graph->n - (split + 1), node, i++);  in isl_scc_graph_decompose()