218 	struct isl_access_info *acc;  in isl_access_info_alloc()  local
226 	acc = isl_calloc(ctx, struct isl_access_info,  in isl_access_info_alloc()
229 	if (!acc)  in isl_access_info_alloc()
232 	acc->sink.map = sink;  in isl_access_info_alloc()
233 	acc->sink.data = sink_user;  in isl_access_info_alloc()
234 	acc->level_before = fn;  in isl_access_info_alloc()
235 	acc->max_source = max_source;  in isl_access_info_alloc()
236 	acc->n_must = 0;  in isl_access_info_alloc()
237 	acc->n_may = 0;  in isl_access_info_alloc()
239 	return acc;  in isl_access_info_alloc()
248 	__isl_take isl_access_info *acc)  in isl_access_info_free()  argument
252 	if (!acc)  in isl_access_info_free()
254 	isl_map_free(acc->domain_map);  in isl_access_info_free()
255 	isl_map_free(acc->sink.map);  in isl_access_info_free()
256 	for (i = 0; i < acc->n_must + acc->n_may; ++i)  in isl_access_info_free()
257 		isl_map_free(acc->source[i].map);  in isl_access_info_free()
258 	free(acc);  in isl_access_info_free()
262 isl_ctx *isl_access_info_get_ctx(__isl_keep isl_access_info *acc)  in isl_access_info_get_ctx()  argument
264 	return acc ? isl_map_get_ctx(acc->sink.map) : NULL;  in isl_access_info_get_ctx()
268 	__isl_take isl_access_info *acc, isl_access_restrict fn, void *user)  in isl_access_info_set_restrict()  argument
270 	if (!acc)  in isl_access_info_set_restrict()
272 	acc->restrict_fn = fn;  in isl_access_info_set_restrict()
273 	acc->restrict_user = user;  in isl_access_info_set_restrict()
274 	return acc;  in isl_access_info_set_restrict()
284 	__isl_take isl_access_info *acc, __isl_take isl_map *source,  in isl_access_info_add_source()  argument
289 	if (!acc)  in isl_access_info_add_source()
291 	ctx = isl_map_get_ctx(acc->sink.map);  in isl_access_info_add_source()
292 	isl_assert(ctx, acc->n_must + acc->n_may < acc->max_source, goto error);  in isl_access_info_add_source()
295 		if (acc->n_may)  in isl_access_info_add_source()
296 			acc->source[acc->n_must + acc->n_may] =  in isl_access_info_add_source()
297 				acc->source[acc->n_must];  in isl_access_info_add_source()
298 		acc->source[acc->n_must].map = source;  in isl_access_info_add_source()
299 		acc->source[acc->n_must].data = source_user;  in isl_access_info_add_source()
300 		acc->source[acc->n_must].must = 1;  in isl_access_info_add_source()
301 		acc->n_must++;  in isl_access_info_add_source()
303 		acc->source[acc->n_must + acc->n_may].map = source;  in isl_access_info_add_source()
304 		acc->source[acc->n_must + acc->n_may].data = source_user;  in isl_access_info_add_source()
305 		acc->source[acc->n_must + acc->n_may].must = 0;  in isl_access_info_add_source()
306 		acc->n_may++;  in isl_access_info_add_source()
309 	return acc;  in isl_access_info_add_source()
312 	isl_access_info_free(acc);  in isl_access_info_add_source()
342 	isl_access_info *acc = sort_info->access_info;  in access_sort_cmp()  local
353 	level1 = acc->level_before(i1->data, i2->data);  in access_sort_cmp()
359 	level2 = acc->level_before(i2->data, i1->data);  in access_sort_cmp()
376 	__isl_take isl_access_info *acc)  in isl_access_info_sort_sources()  argument
380 	sort_info.access_info = acc;  in isl_access_info_sort_sources()
383 	if (!acc)  in isl_access_info_sort_sources()
385 	if (acc->n_must <= 1)  in isl_access_info_sort_sources()
386 		return acc;  in isl_access_info_sort_sources()
388 	if (isl_sort(acc->source, acc->n_must, sizeof(struct isl_labeled_map),  in isl_access_info_sort_sources()
390 		return isl_access_info_free(acc);  in isl_access_info_sort_sources()
392 		return isl_access_info_free(acc);  in isl_access_info_sort_sources()
394 	return acc;  in isl_access_info_sort_sources()
430 static __isl_give isl_flow *isl_flow_alloc(__isl_keep isl_access_info *acc)  in isl_flow_alloc()  argument
436 	if (!acc)  in isl_flow_alloc()
439 	ctx = isl_map_get_ctx(acc->sink.map);  in isl_flow_alloc()
444 	n = 2 * acc->n_must + acc->n_may;  in isl_flow_alloc()
450 	for (i = 0; i < acc->n_must; ++i) {  in isl_flow_alloc()
453 			isl_map_get_space(acc->source[i].map),  in isl_flow_alloc()
454 			isl_space_reverse(isl_map_get_space(acc->sink.map)));  in isl_flow_alloc()
457 		dep->dep[2 * i].data = acc->source[i].data;  in isl_flow_alloc()
458 		dep->dep[2 * i + 1].data = acc->source[i].data;  in isl_flow_alloc()
464 	for (i = acc->n_must; i < acc->n_must + acc->n_may; ++i) {  in isl_flow_alloc()
467 			isl_map_get_space(acc->source[i].map),  in isl_flow_alloc()
468 			isl_space_reverse(isl_map_get_space(acc->sink.map)));  in isl_flow_alloc()
469 		dep->dep[acc->n_must + i].map = isl_map_empty(space);  in isl_flow_alloc()
470 		dep->dep[acc->n_must + i].data = acc->source[i].data;  in isl_flow_alloc()
471 		dep->dep[acc->n_must + i].must = 0;  in isl_flow_alloc()
472 		if (!dep->dep[acc->n_must + i].map)  in isl_flow_alloc()
581 	__isl_keep isl_access_info *acc, __isl_take isl_map *dep,  in restricted_partial_lexmax()  argument
590 	if (!acc->restrict_fn)  in restricted_partial_lexmax()
595 					    isl_map_copy(acc->domain_map));  in restricted_partial_lexmax()
597 	sink_domain = isl_set_apply(sink_domain, isl_map_copy(acc->domain_map));  in restricted_partial_lexmax()
598 	restr = acc->restrict_fn(source_map, sink_domain,  in restricted_partial_lexmax()
599 				acc->source[source].data, acc->restrict_user);  in restricted_partial_lexmax()
609 				isl_map_reverse(isl_map_copy(acc->domain_map)));  in restricted_partial_lexmax()
636 static struct isl_map *last_source(struct isl_access_info *acc,   in last_source()  argument
646 	read_map = isl_map_copy(acc->sink.map);  in last_source()
647 	write_map = isl_map_copy(acc->source[j].map);  in last_source()
652 	result = restricted_partial_lexmax(acc, dep_map, j, set_C, empty);  in last_source()
664 static struct isl_map *last_later_source(struct isl_access_info *acc,  in last_later_source()  argument
680 	read_map = isl_map_copy(acc->sink.map);  in last_later_source()
681 	write_map = isl_map_copy(acc->source[k].map);  in last_later_source()
685 	space = space_align_and_join(isl_map_get_space(acc->source[k].map),  in last_later_source()
686 		    isl_space_reverse(isl_map_get_space(acc->source[j].map)));  in last_later_source()
693 	result = restricted_partial_lexmax(acc, dep_map, k, set_C, empty);  in last_later_source()
731 static isl_stat intermediate_sources(__isl_keep isl_access_info *acc,  in intermediate_sources()  argument
735 	isl_size n_in = isl_map_dim(acc->source[j].map, isl_dim_in);  in intermediate_sources()
745 		plevel = acc->level_before(acc->source[k].data, acc->sink.data);  in intermediate_sources()
751 		plevel2 = acc->level_before(acc->source[j].data,  in intermediate_sources()
752 						acc->source[k].data);  in intermediate_sources()
765 			T = last_later_source(acc, copy, j, sink_level, k,  in intermediate_sources()
783 static __isl_give isl_map *all_sources(__isl_keep isl_access_info *acc,  in all_sources()  argument
791 	read_map = isl_map_copy(acc->sink.map);  in all_sources()
793 	write_map = isl_map_copy(acc->source[acc->n_must + j].map);  in all_sources()
808 static __isl_give isl_map *all_later_sources(__isl_keep isl_access_info *acc,  in all_later_sources()  argument
821 	read_map = isl_map_copy(acc->sink.map);  in all_later_sources()
823 	write_map = isl_map_copy(acc->source[acc->n_must + j].map);  in all_later_sources()
828 		    acc->source[acc->n_must + j].map),  in all_later_sources()
829 		    isl_space_reverse(isl_map_get_space(acc->source[k].map)));  in all_later_sources()
847 	__isl_keep isl_access_info *acc, __isl_take isl_map *map,  in all_intermediate_sources()  argument
852 	isl_size n_in = isl_map_dim(acc->source[acc->n_must + j].map,  in all_intermediate_sources()
858 	for (k = 0; k < acc->n_must; ++k) {  in all_intermediate_sources()
865 		plevel = acc->level_before(acc->source[k].data,  in all_intermediate_sources()
866 					acc->source[acc->n_must + j].data);  in all_intermediate_sources()
879 			T = all_later_sources(acc, copy, j, sink_level, k, level);  in all_intermediate_sources()
883 			T = all_later_sources(acc, copy, j, sink_level, k, level);  in all_intermediate_sources()
920 static __isl_give isl_map *coscheduled_source(__isl_keep isl_access_info *acc,  in coscheduled_source()  argument
935 	read_map = isl_map_copy(acc->sink.map);  in coscheduled_source()
937 	write_map = isl_map_copy(acc->source[pos].map);  in coscheduled_source()
985 static __isl_give isl_flow *handle_coscheduled(__isl_keep isl_access_info *acc,  in handle_coscheduled()  argument
991 	if (!acc->coscheduled)  in handle_coscheduled()
993 	for (i = acc->n_must - 1; i >= 0; --i) {  in handle_coscheduled()
1004 			coscheduled = acc->coscheduled(acc->source[i].data,  in handle_coscheduled()
1005 							acc->source[j].data);  in handle_coscheduled()
1012 			depth = acc->level_before(acc->source[i].data,  in handle_coscheduled()
1013 						acc->source[j].data) / 2;  in handle_coscheduled()
1014 			map = coscheduled_source(acc, must_rel[i], j, depth);  in handle_coscheduled()
1020 		for (j = 0; j < acc->n_may; ++j) {  in handle_coscheduled()
1025 			pos = acc->n_must + j;  in handle_coscheduled()
1026 			coscheduled = acc->coscheduled(acc->source[i].data,  in handle_coscheduled()
1027 							acc->source[pos].data);  in handle_coscheduled()
1034 			depth = acc->level_before(acc->source[i].data,  in handle_coscheduled()
1035 						acc->source[pos].data) / 2;  in handle_coscheduled()
1036 			map = coscheduled_source(acc, must_rel[i], pos, depth);  in handle_coscheduled()
1038 			pos = 2 * acc->n_must + j;  in handle_coscheduled()
1057 	__isl_keep isl_access_info *acc)  in compute_mem_based_dependences()  argument
1064 	res = isl_flow_alloc(acc);  in compute_mem_based_dependences()
1068 	mustdo = isl_map_domain(isl_map_copy(acc->sink.map));  in compute_mem_based_dependences()
1071 	for (i = 0; i < acc->n_may; ++i) {  in compute_mem_based_dependences()
1078 		plevel = acc->level_before(acc->source[i].data, acc->sink.data);  in compute_mem_based_dependences()
1090 		dep = isl_map_apply_range(isl_map_copy(acc->source[i].map),  in compute_mem_based_dependences()
1091 			isl_map_reverse(isl_map_copy(acc->sink.map)));  in compute_mem_based_dependences()
1150 	__isl_keep isl_access_info *acc)  in compute_val_based_dependences()  argument
1162 	if (!acc)  in compute_val_based_dependences()
1165 	res = isl_flow_alloc(acc);  in compute_val_based_dependences()
1168 	ctx = isl_map_get_ctx(acc->sink.map);  in compute_val_based_dependences()
1170 	n_in = isl_map_dim(acc->sink.map, isl_dim_in);  in compute_val_based_dependences()
1174 	mustdo = isl_map_domain(isl_map_copy(acc->sink.map));  in compute_val_based_dependences()
1181 	must_rel = isl_calloc_array(ctx, struct isl_map *, acc->n_must);  in compute_val_based_dependences()
1182 	may_rel = isl_calloc_array(ctx, struct isl_map *, acc->n_must);  in compute_val_based_dependences()
1187 		for (j = acc->n_must-1; j >=0; --j) {  in compute_val_based_dependences()
1194 		for (j = acc->n_must - 1; j >= 0; --j) {  in compute_val_based_dependences()
1199 			plevel = acc->level_before(acc->source[j].data,  in compute_val_based_dependences()
1200 						     acc->sink.data);  in compute_val_based_dependences()
1206 			T = last_source(acc, mustdo, j, level, &rest);  in compute_val_based_dependences()
1210 			if (intermediate_sources(acc, must_rel, j, level) < 0)  in compute_val_based_dependences()
1213 			T = last_source(acc, maydo, j, level, &rest);  in compute_val_based_dependences()
1217 			if (intermediate_sources(acc, may_rel, j, level) < 0)  in compute_val_based_dependences()
1227 			plevel = acc->level_before(acc->source[j].data,  in compute_val_based_dependences()
1228 						     acc->sink.data);  in compute_val_based_dependences()
1234 			if (intermediate_sources(acc, must_rel, j, level) < 0)  in compute_val_based_dependences()
1236 			if (intermediate_sources(acc, may_rel, j, level) < 0)  in compute_val_based_dependences()
1240 		res = handle_coscheduled(acc, must_rel, may_rel, res);  in compute_val_based_dependences()
1244 		for (j = 0; j < acc->n_may; ++j) {  in compute_val_based_dependences()
1249 			plevel = acc->level_before(acc->source[acc->n_must + j].data,  in compute_val_based_dependences()
1250 						     acc->sink.data);  in compute_val_based_dependences()
1256 			T = all_sources(acc, isl_set_copy(maydo), j, level);  in compute_val_based_dependences()
1257 			res->dep[2 * acc->n_must + j].map =  in compute_val_based_dependences()
1258 			    isl_map_union(res->dep[2 * acc->n_must + j].map, T);  in compute_val_based_dependences()
1259 			T = all_sources(acc, isl_set_copy(mustdo), j, level);  in compute_val_based_dependences()
1261 			res->dep[2 * acc->n_must + j].map =  in compute_val_based_dependences()
1262 			    isl_map_union(res->dep[2 * acc->n_must + j].map, T);  in compute_val_based_dependences()
1266 			T = res->dep[2 * acc->n_must + j].map;  in compute_val_based_dependences()
1267 			T = all_intermediate_sources(acc, T, must_rel, may_rel,  in compute_val_based_dependences()
1269 			res->dep[2 * acc->n_must + j].map = T;  in compute_val_based_dependences()
1272 		for (j = acc->n_must - 1; j >= 0; --j) {  in compute_val_based_dependences()
1294 		for (j = 0; j < acc->n_must; ++j)  in compute_val_based_dependences()
1297 		for (j = 0; j < acc->n_must; ++j)  in compute_val_based_dependences()
1325 	__isl_take isl_access_info *acc)  in access_info_compute_flow_core()  argument
1329 	if (!acc)  in access_info_compute_flow_core()
1332 	acc->sink.map = isl_map_range_map(acc->sink.map);  in access_info_compute_flow_core()
1333 	if (!acc->sink.map)  in access_info_compute_flow_core()
1336 	if (acc->n_must == 0)  in access_info_compute_flow_core()
1337 		res = compute_mem_based_dependences(acc);  in access_info_compute_flow_core()
1339 		acc = isl_access_info_sort_sources(acc);  in access_info_compute_flow_core()
1340 		res = compute_val_based_dependences(acc);  in access_info_compute_flow_core()
1342 	acc = isl_access_info_free(acc);  in access_info_compute_flow_core()
1349 	isl_access_info_free(acc);  in access_info_compute_flow_core()
1371 __isl_give isl_flow *isl_access_info_compute_flow(__isl_take isl_access_info *acc)  in isl_access_info_compute_flow()  argument
1376 	if (!acc)  in isl_access_info_compute_flow()
1379 	acc->domain_map = isl_map_domain_map(isl_map_copy(acc->sink.map));  in isl_access_info_compute_flow()
1380 	res = access_info_compute_flow_core(acc);  in isl_access_info_compute_flow()