brintos / llvm-project-archived public Read only

1/*2 * Copyright 2010-2011 INRIA Saclay3 * Copyright 2013-2014 Ecole Normale Superieure4 * Copyright 2014      INRIA Rocquencourt5 * Copyright 2016-2017 Sven Verdoolaege6 *7 * Use of this software is governed by the MIT license8 *9 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,10 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,11 * 91893 Orsay, France 12 * and Inria Paris - Rocquencourt, Domaine de Voluceau - Rocquencourt,13 * B.P. 105 - 78153 Le Chesnay, France14 */15 16#include <isl_map_private.h>17#include <isl_union_map_private.h>18#include <isl/ctx.h>19#include <isl/hash.h>20#include <isl_aff_private.h>21#include <isl/map.h>22#include <isl/set.h>23#include <isl_space_private.h>24#include <isl/union_set.h>25#include <isl_maybe_map.h>26#include <isl_id_private.h>27 28#include <bset_from_bmap.c>29#include <set_to_map.c>30#include <set_from_map.c>31#include <uset_to_umap.c>32#include <uset_from_umap.c>33#include <set_list_from_map_list_inl.c>34 35#undef TYPE36#define TYPE	isl_union_map37static38#include "has_single_reference_templ.c"39static40#include "check_single_reference_templ.c"41 42/* Return the number of parameters of "umap", where "type"43 * is required to be set to isl_dim_param.44 */45isl_size isl_union_map_dim(__isl_keep isl_union_map *umap,46	enum isl_dim_type type)47{48	if (!umap)49		return isl_size_error;50 51	if (type != isl_dim_param)52		isl_die(isl_union_map_get_ctx(umap), isl_error_invalid,53			"can only reference parameters", return isl_size_error);54 55	return isl_space_dim(umap->dim, type);56}57 58/* Return the number of parameters of "uset", where "type"59 * is required to be set to isl_dim_param.60 */61isl_size isl_union_set_dim(__isl_keep isl_union_set *uset,62	enum isl_dim_type type)63{64	return isl_union_map_dim(uset, type);65}66 67/* Return the id of the specified dimension.68 */69__isl_give isl_id *isl_union_map_get_dim_id(__isl_keep isl_union_map *umap,70	enum isl_dim_type type, unsigned pos)71{72	if (!umap)73		return NULL;74 75	if (type != isl_dim_param)76		isl_die(isl_union_map_get_ctx(umap), isl_error_invalid,77			"can only reference parameters", return NULL);78 79	return isl_space_get_dim_id(umap->dim, type, pos);80}81 82/* Is this union set a parameter domain?83 */84isl_bool isl_union_set_is_params(__isl_keep isl_union_set *uset)85{86	isl_set *set;87	isl_bool params;88 89	if (!uset)90		return isl_bool_error;91	if (uset->table.n != 1)92		return isl_bool_false;93 94	set = isl_set_from_union_set(isl_union_set_copy(uset));95	params = isl_set_is_params(set);96	isl_set_free(set);97	return params;98}99 100/* Is this union map actually a parameter domain?101 * Users should never call this function.  Outside of isl,102 * a union map can never be a parameter domain.103 */104isl_bool isl_union_map_is_params(__isl_keep isl_union_map *umap)105{106	return isl_union_set_is_params(uset_from_umap(umap));107}108 109static __isl_give isl_union_map *isl_union_map_alloc(110	__isl_take isl_space *space, int size)111{112	isl_union_map *umap;113 114	space = isl_space_params(space);115	if (!space)116		return NULL;117 118	umap = isl_calloc_type(space->ctx, isl_union_map);119	if (!umap) {120		isl_space_free(space);121		return NULL;122	}123 124	umap->ref = 1;125	umap->dim = space;126	if (isl_hash_table_init(space->ctx, &umap->table, size) < 0)127		return isl_union_map_free(umap);128 129	return umap;130}131 132/* Create an empty union map without specifying any parameters.133 */134__isl_give isl_union_map *isl_union_map_empty_ctx(isl_ctx *ctx)135{136	return isl_union_map_empty_space(isl_space_unit(ctx));137}138 139__isl_give isl_union_map *isl_union_map_empty_space(__isl_take isl_space *space)140{141	return isl_union_map_alloc(space, 16);142}143 144/* This is an alternative name for the function above.145 */146__isl_give isl_union_map *isl_union_map_empty(__isl_take isl_space *space)147{148	return isl_union_map_empty_space(space);149}150 151/* Create an empty union set without specifying any parameters.152 */153__isl_give isl_union_set *isl_union_set_empty_ctx(isl_ctx *ctx)154{155	return uset_from_umap(isl_union_map_empty_ctx(ctx));156}157 158__isl_give isl_union_set *isl_union_set_empty_space(__isl_take isl_space *space)159{160	return uset_from_umap(isl_union_map_empty_space(space));161}162 163/* This is an alternative name for the function above.164 */165__isl_give isl_union_set *isl_union_set_empty(__isl_take isl_space *space)166{167	return isl_union_set_empty_space(space);168}169 170isl_ctx *isl_union_map_get_ctx(__isl_keep isl_union_map *umap)171{172	return umap ? umap->dim->ctx : NULL;173}174 175isl_ctx *isl_union_set_get_ctx(__isl_keep isl_union_set *uset)176{177	return uset ? uset->dim->ctx : NULL;178}179 180/* Return the space of "umap".181 */182__isl_keep isl_space *isl_union_map_peek_space(__isl_keep isl_union_map *umap)183{184	return umap ? umap->dim : NULL;185}186 187/* Return the space of "uset".188 */189__isl_keep isl_space *isl_union_set_peek_space(__isl_keep isl_union_set *uset)190{191	return isl_union_map_peek_space(uset_to_umap(uset));192}193 194__isl_give isl_space *isl_union_map_get_space(__isl_keep isl_union_map *umap)195{196	return isl_space_copy(isl_union_map_peek_space(umap));197}198 199/* Return the position of the parameter with the given name200 * in "umap".201 * Return -1 if no such dimension can be found.202 */203int isl_union_map_find_dim_by_name(__isl_keep isl_union_map *umap,204	enum isl_dim_type type, const char *name)205{206	if (!umap)207		return -1;208	return isl_space_find_dim_by_name(umap->dim, type, name);209}210 211/* Return the position of the parameter with id "id" in "umap".212 * Return -1 if no such dimension can be found.213 */214static int isl_union_map_find_dim_by_id(__isl_keep isl_union_map *umap,215	enum isl_dim_type type, __isl_keep isl_id *id)216{217	isl_space *space;218 219	space = isl_union_map_peek_space(umap);220	return isl_space_find_dim_by_id(space, type, id);221}222 223__isl_give isl_space *isl_union_set_get_space(__isl_keep isl_union_set *uset)224{225	return isl_union_map_get_space(uset);226}227 228static isl_stat free_umap_entry(void **entry, void *user)229{230	isl_map *map = *entry;231	isl_map_free(map);232	return isl_stat_ok;233}234 235static isl_stat add_map(__isl_take isl_map *map, void *user)236{237	isl_union_map **umap = (isl_union_map **)user;238 239	*umap = isl_union_map_add_map(*umap, map);240 241	return isl_stat_ok;242}243 244__isl_give isl_union_map *isl_union_map_dup(__isl_keep isl_union_map *umap)245{246	isl_union_map *dup;247 248	if (!umap)249		return NULL;250 251	dup = isl_union_map_empty(isl_space_copy(umap->dim));252	if (isl_union_map_foreach_map(umap, &add_map, &dup) < 0)253		goto error;254	return dup;255error:256	isl_union_map_free(dup);257	return NULL;258}259 260__isl_give isl_union_map *isl_union_map_cow(__isl_take isl_union_map *umap)261{262	if (!umap)263		return NULL;264 265	if (umap->ref == 1)266		return umap;267	umap->ref--;268	return isl_union_map_dup(umap);269}270 271struct isl_union_align {272	isl_reordering *exp;273	isl_union_map *res;274};275 276static isl_stat align_entry(void **entry, void *user)277{278	isl_map *map = *entry;279	isl_reordering *exp;280	struct isl_union_align *data = user;281 282	exp = isl_reordering_extend_space(isl_reordering_copy(data->exp),283				    isl_map_get_space(map));284 285	data->res = isl_union_map_add_map(data->res,286					isl_map_realign(isl_map_copy(map), exp));287 288	return isl_stat_ok;289}290 291/* Align the parameters of umap along those of model.292 * The result has the parameters of model first, in the same order293 * as they appear in model, followed by any remaining parameters of294 * umap that do not appear in model.295 */296__isl_give isl_union_map *isl_union_map_align_params(297	__isl_take isl_union_map *umap, __isl_take isl_space *model)298{299	struct isl_union_align data = { NULL, NULL };300	isl_space *space;301	isl_bool equal_params;302 303	space = isl_union_map_peek_space(umap);304	equal_params = isl_space_has_equal_params(space, model);305	if (equal_params < 0)306		goto error;307	if (equal_params) {308		isl_space_free(model);309		return umap;310	}311 312	data.exp = isl_parameter_alignment_reordering(space, model);313	if (!data.exp)314		goto error;315 316	data.res = isl_union_map_alloc(isl_reordering_get_space(data.exp),317					umap->table.n);318	if (isl_hash_table_foreach(isl_union_map_get_ctx(umap), &umap->table,319					&align_entry, &data) < 0)320		goto error;321 322	isl_reordering_free(data.exp);323	isl_union_map_free(umap);324	isl_space_free(model);325	return data.res;326error:327	isl_reordering_free(data.exp);328	isl_union_map_free(umap);329	isl_union_map_free(data.res);330	isl_space_free(model);331	return NULL;332}333 334__isl_give isl_union_set *isl_union_set_align_params(335	__isl_take isl_union_set *uset, __isl_take isl_space *model)336{337	return isl_union_map_align_params(uset, model);338}339 340__isl_give isl_union_map *isl_union_map_union(__isl_take isl_union_map *umap1,341	__isl_take isl_union_map *umap2)342{343	umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2));344	umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1));345 346	umap1 = isl_union_map_cow(umap1);347 348	if (!umap1 || !umap2)349		goto error;350 351	if (isl_union_map_foreach_map(umap2, &add_map, &umap1) < 0)352		goto error;353 354	isl_union_map_free(umap2);355 356	return umap1;357error:358	isl_union_map_free(umap1);359	isl_union_map_free(umap2);360	return NULL;361}362 363__isl_give isl_union_set *isl_union_set_union(__isl_take isl_union_set *uset1,364	__isl_take isl_union_set *uset2)365{366	return isl_union_map_union(uset1, uset2);367}368 369__isl_give isl_union_map *isl_union_map_copy(__isl_keep isl_union_map *umap)370{371	if (!umap)372		return NULL;373 374	umap->ref++;375	return umap;376}377 378__isl_give isl_union_set *isl_union_set_copy(__isl_keep isl_union_set *uset)379{380	return isl_union_map_copy(uset);381}382 383__isl_null isl_union_map *isl_union_map_free(__isl_take isl_union_map *umap)384{385	if (!umap)386		return NULL;387 388	if (--umap->ref > 0)389		return NULL;390 391	isl_hash_table_foreach(umap->dim->ctx, &umap->table,392			       &free_umap_entry, NULL);393	isl_hash_table_clear(&umap->table);394	isl_space_free(umap->dim);395	free(umap);396	return NULL;397}398 399__isl_null isl_union_set *isl_union_set_free(__isl_take isl_union_set *uset)400{401	return isl_union_map_free(uset);402}403 404/* Do "umap" and "space" have the same parameters?405 */406isl_bool isl_union_map_space_has_equal_params(__isl_keep isl_union_map *umap,407	__isl_keep isl_space *space)408{409	isl_space *umap_space;410 411	umap_space = isl_union_map_peek_space(umap);412	return isl_space_has_equal_params(umap_space, space);413}414 415/* Do "uset" and "space" have the same parameters?416 */417isl_bool isl_union_set_space_has_equal_params(__isl_keep isl_union_set *uset,418	__isl_keep isl_space *space)419{420	return isl_union_map_space_has_equal_params(uset_to_umap(uset), space);421}422 423/* Is the space of the map at "entry" equal to "space", ignoring parameters?424 */425static isl_bool has_space_tuples(const void *entry, const void *val)426{427	isl_map *map = (isl_map *)entry;428	isl_space *space = (isl_space *) val;429 430	return isl_map_has_space_tuples(map, space);431}432 433/* Find the entry in "umap" with space "space" (ignoring parameters),434 * returning isl_hash_table_entry_none if no such entry appears in "umap" and435 * NULL on error.436 * If "reserve" is set, then an entry is created if it does437 * not exist already.  Since this modifies the hash table in-place,438 * this means "umap" must have a single reference when "reserve" is set.439 */440static struct isl_hash_table_entry *isl_union_map_find_entry(441	__isl_keep isl_union_map *umap, __isl_keep isl_space *space,442	int reserve)443{444	uint32_t hash;445 446	if (!umap || !space)447		return NULL;448	if (reserve && isl_union_map_check_single_reference(umap) < 0)449		return NULL;450 451	hash = isl_space_get_tuple_hash(space);452	return isl_hash_table_find(isl_union_map_get_ctx(umap), &umap->table,453				    hash, &has_space_tuples, space, reserve);454}455 456/* Find the entry in "uset" with space "space" (ignoring parameters),457 * returning isl_hash_table_entry_none if no such entry appears in "uset" and458 * NULL on error.459 * If "reserve" is set, then an entry is created if it does460 * not exist already.  In this case, a NULL return indicates an error.461 */462struct isl_hash_table_entry *isl_union_set_find_entry(463	__isl_keep isl_union_set *uset, __isl_keep isl_space *space,464	int reserve)465{466	return isl_union_map_find_entry(uset_to_umap(uset), space, reserve);467}468 469__isl_give isl_union_map *isl_union_map_add_map(__isl_take isl_union_map *umap,470	__isl_take isl_map *map)471{472	struct isl_hash_table_entry *entry;473	isl_bool aligned;474	isl_space *space;475 476	if (!map || !umap)477		goto error;478 479	if (isl_map_plain_is_empty(map)) {480		isl_map_free(map);481		return umap;482	}483 484	aligned = isl_map_space_has_equal_params(map, umap->dim);485	if (aligned < 0)486		goto error;487	if (!aligned) {488		umap = isl_union_map_align_params(umap, isl_map_get_space(map));489		map = isl_map_align_params(map, isl_union_map_get_space(umap));490	}491 492	umap = isl_union_map_cow(umap);493 494	space = isl_map_peek_space(map);495	entry = isl_union_map_find_entry(umap, space, 1);496	if (!entry)497		goto error;498 499	if (!entry->data)500		entry->data = map;501	else {502		entry->data = isl_map_union(entry->data, isl_map_copy(map));503		if (!entry->data)504			goto error;505		isl_map_free(map);506	}507 508	return umap;509error:510	isl_map_free(map);511	isl_union_map_free(umap);512	return NULL;513}514 515__isl_give isl_union_set *isl_union_set_add_set(__isl_take isl_union_set *uset,516	__isl_take isl_set *set)517{518	return isl_union_map_add_map(uset, set_to_map(set));519}520 521__isl_give isl_union_map *isl_union_map_from_map(__isl_take isl_map *map)522{523	isl_space *space;524	isl_union_map *umap;525 526	if (!map)527		return NULL;528 529	space = isl_map_get_space(map);530	space = isl_space_params(space);531	umap = isl_union_map_empty(space);532	umap = isl_union_map_add_map(umap, map);533 534	return umap;535}536 537/* This function performs the same operation as isl_union_map_from_map,538 * but is considered as a function on an isl_map when exported.539 */540__isl_give isl_union_map *isl_map_to_union_map(__isl_take isl_map *map)541{542	return isl_union_map_from_map(map);543}544 545__isl_give isl_union_set *isl_union_set_from_set(__isl_take isl_set *set)546{547	return isl_union_map_from_map(set_to_map(set));548}549 550/* This function performs the same operation as isl_union_set_from_set,551 * but is considered as a function on an isl_set when exported.552 */553__isl_give isl_union_set *isl_set_to_union_set(__isl_take isl_set *set)554{555	return isl_union_set_from_set(set);556}557 558__isl_give isl_union_map *isl_union_map_from_basic_map(559	__isl_take isl_basic_map *bmap)560{561	return isl_union_map_from_map(isl_map_from_basic_map(bmap));562}563 564__isl_give isl_union_set *isl_union_set_from_basic_set(565	__isl_take isl_basic_set *bset)566{567	return isl_union_map_from_basic_map(bset);568}569 570struct isl_union_map_foreach_data571{572	isl_stat (*fn)(__isl_take isl_map *map, void *user);573	void *user;574};575 576static isl_stat call_on_copy(void **entry, void *user)577{578	isl_map *map = *entry;579	struct isl_union_map_foreach_data *data;580	data = (struct isl_union_map_foreach_data *)user;581 582	return data->fn(isl_map_copy(map), data->user);583}584 585isl_size isl_union_map_n_map(__isl_keep isl_union_map *umap)586{587	return umap ? umap->table.n : isl_size_error;588}589 590isl_size isl_union_set_n_set(__isl_keep isl_union_set *uset)591{592	return uset ? uset->table.n : isl_size_error;593}594 595isl_stat isl_union_map_foreach_map(__isl_keep isl_union_map *umap,596	isl_stat (*fn)(__isl_take isl_map *map, void *user), void *user)597{598	struct isl_union_map_foreach_data data = { fn, user };599 600	if (!umap)601		return isl_stat_error;602 603	return isl_hash_table_foreach(umap->dim->ctx, &umap->table,604				      &call_on_copy, &data);605}606 607/* Internal data structure for isl_union_map_every_map.608 *609 * "test" is the user-specified callback function.610 * "user" is the user-specified callback function argument.611 *612 * "failed" is initialized to 0 and set to 1 if "test" fails613 * on any map.614 */615struct isl_union_map_every_data {616	isl_bool (*test)(__isl_keep isl_map *map, void *user);617	void *user;618	int failed;619};620 621/* Call data->test on "map".622 * If this fails, then set data->failed and abort.623 */624static isl_stat call_every(void **entry, void *user)625{626	isl_map *map = *entry;627	struct isl_union_map_every_data *data = user;628	isl_bool r;629 630	r = data->test(map, data->user);631	if (r < 0)632		return isl_stat_error;633	if (r)634		return isl_stat_ok;635	data->failed = 1;636	return isl_stat_error;637}638 639/* Does "test" succeed on every map in "umap"?640 */641isl_bool isl_union_map_every_map(__isl_keep isl_union_map *umap,642	isl_bool (*test)(__isl_keep isl_map *map, void *user), void *user)643{644	struct isl_union_map_every_data data = { test, user, 0 };645	isl_stat r;646 647	if (!umap)648		return isl_bool_error;649 650	r = isl_hash_table_foreach(isl_union_map_get_ctx(umap), &umap->table,651				      &call_every, &data);652	if (r >= 0)653		return isl_bool_true;654	if (data.failed)655		return isl_bool_false;656	return isl_bool_error;657}658 659/* Add "map" to "list".660 */661static isl_stat add_list_map(__isl_take isl_map *map, void *user)662{663	isl_map_list **list = user;664 665	*list = isl_map_list_add(*list, map);666 667	if (!*list)668		return isl_stat_error;669	return isl_stat_ok;670}671 672/* Return the maps in "umap" as a list.673 *674 * First construct a list of the appropriate size and then add all the675 * elements.676 */677__isl_give isl_map_list *isl_union_map_get_map_list(678	__isl_keep isl_union_map *umap)679{680	isl_size n_maps;681	isl_ctx *ctx;682	isl_map_list *list;683 684	n_maps = isl_union_map_n_map(umap);685	if (n_maps < 0)686		return NULL;687	ctx = isl_union_map_get_ctx(umap);688	list = isl_map_list_alloc(ctx, n_maps);689 690	if (isl_union_map_foreach_map(umap, &add_list_map, &list) < 0)691		list = isl_map_list_free(list);692 693	return list;694}695 696/* Return the sets in "uset" as a list.697 */698__isl_give isl_set_list *isl_union_set_get_set_list(699	__isl_keep isl_union_set *uset)700{701	return set_list_from_map_list(702		isl_union_map_get_map_list(uset_to_umap(uset)));703}704 705/* Can "umap" be converted to an isl_map?706 * That is, does it contain elements in exactly one space?707 */708isl_bool isl_union_map_isa_map(__isl_keep isl_union_map *umap)709{710	isl_size n;711 712	n = isl_union_map_n_map(umap);713	if (n < 0)714		return isl_bool_error;715	return isl_bool_ok(n == 1);716}717 718/* Can "uset" be converted to an isl_set?719 * That is, does it contain elements in exactly one space?720 */721isl_bool isl_union_set_isa_set(__isl_keep isl_union_set *uset)722{723	return isl_union_map_isa_map(uset_to_umap(uset));724}725 726static isl_stat copy_map(void **entry, void *user)727{728	isl_map *map = *entry;729	isl_map **map_p = user;730 731	*map_p = isl_map_copy(map);732 733	return isl_stat_error;734}735 736__isl_give isl_map *isl_map_from_union_map(__isl_take isl_union_map *umap)737{738	isl_bool is_map;739	isl_ctx *ctx;740	isl_map *map = NULL;741 742	is_map = isl_union_map_isa_map(umap);743	if (is_map < 0)744		goto error;745	ctx = isl_union_map_get_ctx(umap);746	if (!is_map)747		isl_die(ctx, isl_error_invalid,748			"union map needs to contain elements in exactly "749			"one space", goto error);750 751	isl_hash_table_foreach(ctx, &umap->table, &copy_map, &map);752 753	isl_union_map_free(umap);754 755	return map;756error:757	isl_union_map_free(umap);758	return NULL;759}760 761/* This function performs the same operation as isl_map_from_union_map,762 * but is considered as a function on an isl_union_map when exported.763 */764__isl_give isl_map *isl_union_map_as_map(__isl_take isl_union_map *umap)765{766	return isl_map_from_union_map(umap);767}768 769__isl_give isl_set *isl_set_from_union_set(__isl_take isl_union_set *uset)770{771	return isl_map_from_union_map(uset);772}773 774/* This function performs the same operation as isl_set_from_union_set,775 * but is considered as a function on an isl_union_set when exported.776 */777__isl_give isl_set *isl_union_set_as_set(__isl_take isl_union_set *uset)778{779	return isl_set_from_union_set(uset);780}781 782/* Extract the map in "umap" that lives in the given space (ignoring783 * parameters).784 */785__isl_give isl_map *isl_union_map_extract_map(__isl_keep isl_union_map *umap,786	__isl_take isl_space *space)787{788	struct isl_hash_table_entry *entry;789 790	entry = isl_union_map_find_entry(umap, space, 0);791	if (!entry)792		goto error;793	if (entry == isl_hash_table_entry_none)794		return isl_map_empty(space);795	isl_space_free(space);796	return isl_map_copy(entry->data);797error:798	isl_space_free(space);799	return NULL;800}801 802__isl_give isl_set *isl_union_set_extract_set(__isl_keep isl_union_set *uset,803	__isl_take isl_space *space)804{805	return set_from_map(isl_union_map_extract_map(uset, space));806}807 808/* Check if umap contains a map in the given space (ignoring parameters).809 */810isl_bool isl_union_map_contains(__isl_keep isl_union_map *umap,811	__isl_keep isl_space *space)812{813	struct isl_hash_table_entry *entry;814 815	space = isl_space_drop_all_params(isl_space_copy(space));816	space = isl_space_align_params(space, isl_union_map_get_space(umap));817	entry = isl_union_map_find_entry(umap, space, 0);818	isl_space_free(space);819	if (!entry)820		return isl_bool_error;821	return isl_bool_ok(entry != isl_hash_table_entry_none);822}823 824isl_bool isl_union_set_contains(__isl_keep isl_union_set *uset,825	__isl_keep isl_space *space)826{827	return isl_union_map_contains(uset, space);828}829 830isl_stat isl_union_set_foreach_set(__isl_keep isl_union_set *uset,831	isl_stat (*fn)(__isl_take isl_set *set, void *user), void *user)832{833	return isl_union_map_foreach_map(uset,834		(isl_stat(*)(__isl_take isl_map *, void*))fn, user);835}836 837/* Internal data structure for isl_union_set_every_set.838 *839 * "test" is the user-specified callback function.840 * "user" is the user-specified callback function argument.841 */842struct isl_test_set_from_map_data {843	isl_bool (*test)(__isl_keep isl_set *set, void *user);844	void *user;845};846 847/* Call data->test on "map", which is part of an isl_union_set and848 * therefore known to be an isl_set.849 */850static isl_bool test_set_from_map(__isl_keep isl_map *map, void *user)851{852	struct isl_test_set_from_map_data *data = user;853 854	return data->test(set_from_map(map), data->user);855}856 857/* Does "test" succeed on every set in "uset"?858 */859isl_bool isl_union_set_every_set(__isl_keep isl_union_set *uset,860	isl_bool (*test)(__isl_keep isl_set *set, void *user), void *user)861{862	struct isl_test_set_from_map_data data = { test, user };863 864	return isl_union_map_every_map(uset_to_umap(uset),865					&test_set_from_map, &data);866}867 868struct isl_union_set_foreach_point_data {869	isl_stat (*fn)(__isl_take isl_point *pnt, void *user);870	void *user;871};872 873static isl_stat foreach_point(__isl_take isl_set *set, void *user)874{875	struct isl_union_set_foreach_point_data *data = user;876	isl_stat r;877 878	r = isl_set_foreach_point(set, data->fn, data->user);879	isl_set_free(set);880 881	return r;882}883 884isl_stat isl_union_set_foreach_point(__isl_keep isl_union_set *uset,885	isl_stat (*fn)(__isl_take isl_point *pnt, void *user), void *user)886{887	struct isl_union_set_foreach_point_data data = { fn, user };888	return isl_union_set_foreach_set(uset, &foreach_point, &data);889}890 891/* Data structure that specifies how gen_bin_op should892 * construct results from the inputs.893 *894 * If "subtract" is set, then a map in the first input is copied to the result895 * if there is no corresponding map in the second input.896 * Otherwise, a map in the first input with no corresponding map897 * in the second input is ignored.898 * If "filter" is not NULL, then it specifies which maps in the first899 * input may have a matching map in the second input.900 * In particular, it makes sure that "match_space" can be called901 * on the space of the map.902 * "match_space" specifies how to transform the space of a map903 * in the first input to the space of the corresponding map904 * in the second input.905 * "fn_map" specifies how the matching maps, one from each input,906 * should be combined to form a map in the result.907 */908struct isl_bin_op_control {909	int subtract;910	isl_bool (*filter)(__isl_keep isl_map *map);911	__isl_give isl_space *(*match_space)(__isl_take isl_space *space);912	__isl_give isl_map *(*fn_map)(__isl_take isl_map *map1,913		__isl_take isl_map *map2);914};915 916/* Internal data structure for gen_bin_op.917 * "control" specifies how the maps in the result should be constructed.918 * "umap2" is a pointer to the second argument.919 * "res" collects the results.920 */921struct isl_union_map_gen_bin_data {922	struct isl_bin_op_control *control;923	isl_union_map *umap2;924	isl_union_map *res;925};926 927/* Add a copy of "map" to "res" and return the result.928 */929static __isl_give isl_union_map *bin_add_map(__isl_take isl_union_map *res,930	__isl_keep isl_map *map)931{932	return isl_union_map_add_map(res, isl_map_copy(map));933}934 935/* Combine "map1" and "map2", add the result to "res" and return the result.936 * Check whether the result is empty before adding it to "res".937 */938static __isl_give isl_union_map *bin_add_pair(__isl_take isl_union_map *res,939	__isl_keep isl_map *map1, __isl_keep isl_map *map2,940	struct isl_union_map_gen_bin_data *data)941{942	isl_bool empty;943	isl_map *map;944 945	map = data->control->fn_map(isl_map_copy(map1), isl_map_copy(map2));946	empty = isl_map_is_empty(map);947	if (empty < 0 || empty) {948		isl_map_free(map);949		if (empty < 0)950			return isl_union_map_free(res);951		return res;952	}953	return isl_union_map_add_map(res, map);954}955 956/* Dummy match_space function that simply returns the input space.957 */958static __isl_give isl_space *identity(__isl_take isl_space *space)959{960	return space;961}962 963/* Look for the map in data->umap2 that corresponds to "map", if any.964 * Return (isl_bool_true, matching map) if there is one,965 * (isl_bool_false, NULL) if there is no matching map and966 * (isl_bool_error, NULL) on error.967 *968 * If not NULL, then data->control->filter specifies whether "map"969 * can have any matching map.  If so,970 * data->control->match_space specifies which map in data->umap2971 * corresponds to "map".972 */973static __isl_keep isl_maybe_isl_map bin_try_get_match(974	struct isl_union_map_gen_bin_data *data, __isl_keep isl_map *map)975{976	struct isl_hash_table_entry *entry2;977	isl_space *space;978	isl_maybe_isl_map res = { isl_bool_error, NULL };979 980	if (data->control->filter) {981		res.valid = data->control->filter(map);982		if (res.valid < 0 || !res.valid)983			return res;984		res.valid = isl_bool_error;985	}986 987	space = isl_map_get_space(map);988	if (data->control->match_space != &identity)989		space = data->control->match_space(space);990	entry2 = isl_union_map_find_entry(data->umap2, space, 0);991	isl_space_free(space);992	if (entry2)993		res.valid = isl_bool_ok(entry2 != isl_hash_table_entry_none);994	if (res.valid >= 0 && res.valid)995		res.value = entry2->data;996 997	return res;998}999 1000/* isl_hash_table_foreach callback for gen_bin_op.1001 * Look for the map in data->umap2 that corresponds1002 * to the map that "entry" points to, apply the binary operation and1003 * add the result to data->res.1004 *1005 * If no corresponding map can be found, then the effect depends1006 * on data->control->subtract.  If it is set, then the current map1007 * is added directly to the result.  Otherwise, it is ignored.1008 */1009static isl_stat gen_bin_entry(void **entry, void *user)1010{1011	struct isl_union_map_gen_bin_data *data = user;1012	isl_map *map = *entry;1013	isl_maybe_isl_map m;1014 1015	m = bin_try_get_match(data, map);1016	if (m.valid < 0)1017		return isl_stat_error;1018	if (!m.valid && !data->control->subtract)1019		return isl_stat_ok;1020 1021	if (!m.valid)1022		data->res = bin_add_map(data->res, map);1023	else1024		data->res = bin_add_pair(data->res, map, m.value, data);1025	if (!data->res)1026		return isl_stat_error;1027 1028	return isl_stat_ok;1029}1030 1031/* Apply a binary operation to "umap1" and "umap2" based on "control".1032 * Run over all maps in "umap1" and look for the corresponding map in "umap2"1033 * in gen_bin_entry.1034 */1035static __isl_give isl_union_map *gen_bin_op(__isl_take isl_union_map *umap1,1036	__isl_take isl_union_map *umap2, struct isl_bin_op_control *control)1037{1038	struct isl_union_map_gen_bin_data data = { control, NULL, NULL };1039 1040	umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2));1041	umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1));1042 1043	if (!umap1 || !umap2)1044		goto error;1045 1046	data.umap2 = umap2;1047	data.res = isl_union_map_alloc(isl_space_copy(umap1->dim),1048				       umap1->table.n);1049	if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table,1050				   &gen_bin_entry, &data) < 0)1051		goto error;1052 1053	isl_union_map_free(umap1);1054	isl_union_map_free(umap2);1055	return data.res;1056error:1057	isl_union_map_free(umap1);1058	isl_union_map_free(umap2);1059	isl_union_map_free(data.res);1060	return NULL;1061}1062 1063__isl_give isl_union_map *isl_union_map_subtract(1064	__isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)1065{1066	struct isl_bin_op_control control = {1067		.subtract = 1,1068		.match_space = &identity,1069		.fn_map = &isl_map_subtract,1070	};1071 1072	return gen_bin_op(umap1, umap2, &control);1073}1074 1075__isl_give isl_union_set *isl_union_set_subtract(1076	__isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)1077{1078	return isl_union_map_subtract(uset1, uset2);1079}1080 1081struct isl_union_map_gen_bin_set_data {1082	isl_set *set;1083	isl_union_map *res;1084};1085 1086static isl_stat intersect_params_entry(void **entry, void *user)1087{1088	struct isl_union_map_gen_bin_set_data *data = user;1089	isl_map *map = *entry;1090	int empty;1091 1092	map = isl_map_copy(map);1093	map = isl_map_intersect_params(map, isl_set_copy(data->set));1094 1095	empty = isl_map_is_empty(map);1096	if (empty < 0) {1097		isl_map_free(map);1098		return isl_stat_error;1099	}1100 1101	data->res = isl_union_map_add_map(data->res, map);1102 1103	return isl_stat_ok;1104}1105 1106static __isl_give isl_union_map *gen_bin_set_op(__isl_take isl_union_map *umap,1107	__isl_take isl_set *set, isl_stat (*fn)(void **, void *))1108{1109	struct isl_union_map_gen_bin_set_data data = { NULL, NULL };1110 1111	umap = isl_union_map_align_params(umap, isl_set_get_space(set));1112	set = isl_set_align_params(set, isl_union_map_get_space(umap));1113 1114	if (!umap || !set)1115		goto error;1116 1117	data.set = set;1118	data.res = isl_union_map_alloc(isl_space_copy(umap->dim),1119				       umap->table.n);1120	if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,1121				   fn, &data) < 0)1122		goto error;1123 1124	isl_union_map_free(umap);1125	isl_set_free(set);1126	return data.res;1127error:1128	isl_union_map_free(umap);1129	isl_set_free(set);1130	isl_union_map_free(data.res);1131	return NULL;1132}1133 1134/* Intersect "umap" with the parameter domain "set".1135 *1136 * If "set" does not have any constraints, then we can return immediately.1137 */1138__isl_give isl_union_map *isl_union_map_intersect_params(1139	__isl_take isl_union_map *umap, __isl_take isl_set *set)1140{1141	int is_universe;1142 1143	is_universe = isl_set_plain_is_universe(set);1144	if (is_universe < 0)1145		goto error;1146	if (is_universe) {1147		isl_set_free(set);1148		return umap;1149	}1150 1151	return gen_bin_set_op(umap, set, &intersect_params_entry);1152error:1153	isl_union_map_free(umap);1154	isl_set_free(set);1155	return NULL;1156}1157 1158__isl_give isl_union_set *isl_union_set_intersect_params(1159	__isl_take isl_union_set *uset, __isl_take isl_set *set)1160{1161	return isl_union_map_intersect_params(uset, set);1162}1163 1164static __isl_give isl_union_map *union_map_intersect_params(1165	__isl_take isl_union_map *umap, __isl_take isl_union_set *uset)1166{1167	return isl_union_map_intersect_params(umap,1168						isl_set_from_union_set(uset));1169}1170 1171static __isl_give isl_union_map *union_map_gist_params(1172	__isl_take isl_union_map *umap, __isl_take isl_union_set *uset)1173{1174	return isl_union_map_gist_params(umap, isl_set_from_union_set(uset));1175}1176 1177struct isl_union_map_match_bin_data {1178	isl_union_map *umap2;1179	isl_union_map *res;1180	__isl_give isl_map *(*fn)(__isl_take isl_map*, __isl_take isl_map*);1181};1182 1183static isl_stat match_bin_entry(void **entry, void *user)1184{1185	struct isl_union_map_match_bin_data *data = user;1186	struct isl_hash_table_entry *entry2;1187	isl_space *space;1188	isl_map *map = *entry;1189	int empty;1190 1191	space = isl_map_peek_space(map);1192	entry2 = isl_union_map_find_entry(data->umap2, space, 0);1193	if (!entry2)1194		return isl_stat_error;1195	if (entry2 == isl_hash_table_entry_none)1196		return isl_stat_ok;1197 1198	map = isl_map_copy(map);1199	map = data->fn(map, isl_map_copy(entry2->data));1200 1201	empty = isl_map_is_empty(map);1202	if (empty < 0) {1203		isl_map_free(map);1204		return isl_stat_error;1205	}1206	if (empty) {1207		isl_map_free(map);1208		return isl_stat_ok;1209	}1210 1211	data->res = isl_union_map_add_map(data->res, map);1212 1213	return isl_stat_ok;1214}1215 1216static __isl_give isl_union_map *match_bin_op(__isl_take isl_union_map *umap1,1217	__isl_take isl_union_map *umap2,1218	__isl_give isl_map *(*fn)(__isl_take isl_map*, __isl_take isl_map*))1219{1220	struct isl_union_map_match_bin_data data = { NULL, NULL, fn };1221 1222	umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2));1223	umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1));1224 1225	if (!umap1 || !umap2)1226		goto error;1227 1228	data.umap2 = umap2;1229	data.res = isl_union_map_alloc(isl_space_copy(umap1->dim),1230				       umap1->table.n);1231	if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table,1232				   &match_bin_entry, &data) < 0)1233		goto error;1234 1235	isl_union_map_free(umap1);1236	isl_union_map_free(umap2);1237	return data.res;1238error:1239	isl_union_map_free(umap1);1240	isl_union_map_free(umap2);1241	isl_union_map_free(data.res);1242	return NULL;1243}1244 1245__isl_give isl_union_map *isl_union_map_intersect(1246	__isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)1247{1248	return match_bin_op(umap1, umap2, &isl_map_intersect);1249}1250 1251/* Compute the intersection of the two union_sets.1252 * As a special case, if exactly one of the two union_sets1253 * is a parameter domain, then intersect the parameter domain1254 * of the other one with this set.1255 */1256__isl_give isl_union_set *isl_union_set_intersect(1257	__isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)1258{1259	int p1, p2;1260 1261	p1 = isl_union_set_is_params(uset1);1262	p2 = isl_union_set_is_params(uset2);1263	if (p1 < 0 || p2 < 0)1264		goto error;1265	if (!p1 && p2)1266		return union_map_intersect_params(uset1, uset2);1267	if (p1 && !p2)1268		return union_map_intersect_params(uset2, uset1);1269	return isl_union_map_intersect(uset1, uset2);1270error:1271	isl_union_set_free(uset1);1272	isl_union_set_free(uset2);1273	return NULL;1274}1275 1276static isl_stat gist_params_entry(void **entry, void *user)1277{1278	struct isl_union_map_gen_bin_set_data *data = user;1279	isl_map *map = *entry;1280	int empty;1281 1282	map = isl_map_copy(map);1283	map = isl_map_gist_params(map, isl_set_copy(data->set));1284 1285	empty = isl_map_is_empty(map);1286	if (empty < 0) {1287		isl_map_free(map);1288		return isl_stat_error;1289	}1290 1291	data->res = isl_union_map_add_map(data->res, map);1292 1293	return isl_stat_ok;1294}1295 1296__isl_give isl_union_map *isl_union_map_gist_params(1297	__isl_take isl_union_map *umap, __isl_take isl_set *set)1298{1299	return gen_bin_set_op(umap, set, &gist_params_entry);1300}1301 1302__isl_give isl_union_set *isl_union_set_gist_params(1303	__isl_take isl_union_set *uset, __isl_take isl_set *set)1304{1305	return isl_union_map_gist_params(uset, set);1306}1307 1308__isl_give isl_union_map *isl_union_map_gist(__isl_take isl_union_map *umap,1309	__isl_take isl_union_map *context)1310{1311	return match_bin_op(umap, context, &isl_map_gist);1312}1313 1314__isl_give isl_union_set *isl_union_set_gist(__isl_take isl_union_set *uset,1315	__isl_take isl_union_set *context)1316{1317	if (isl_union_set_is_params(context))1318		return union_map_gist_params(uset, context);1319	return isl_union_map_gist(uset, context);1320}1321 1322/* For each map in "umap", remove the constraints in the corresponding map1323 * of "context".1324 * Each map in "context" is assumed to consist of a single disjunct and1325 * to have explicit representations for all local variables.1326 */1327__isl_give isl_union_map *isl_union_map_plain_gist(1328	__isl_take isl_union_map *umap, __isl_take isl_union_map *context)1329{1330	return match_bin_op(umap, context, &isl_map_plain_gist);1331}1332 1333/* For each set in "uset", remove the constraints in the corresponding set1334 * of "context".1335 * Each set in "context" is assumed to consist of a single disjunct and1336 * to have explicit representations for all local variables.1337 */1338__isl_give isl_union_set *isl_union_set_plain_gist(1339	__isl_take isl_union_set *uset, __isl_take isl_union_set *context)1340{1341	return isl_union_map_plain_gist(uset, context);1342}1343 1344static __isl_give isl_map *lex_le_set(__isl_take isl_map *set1,1345	__isl_take isl_map *set2)1346{1347	return isl_set_lex_le_set(set_from_map(set1), set_from_map(set2));1348}1349 1350static __isl_give isl_map *lex_lt_set(__isl_take isl_map *set1,1351	__isl_take isl_map *set2)1352{1353	return isl_set_lex_lt_set(set_from_map(set1), set_from_map(set2));1354}1355 1356__isl_give isl_union_map *isl_union_set_lex_lt_union_set(1357	__isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)1358{1359	return match_bin_op(uset1, uset2, &lex_lt_set);1360}1361 1362__isl_give isl_union_map *isl_union_set_lex_le_union_set(1363	__isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)1364{1365	return match_bin_op(uset1, uset2, &lex_le_set);1366}1367 1368__isl_give isl_union_map *isl_union_set_lex_gt_union_set(1369	__isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)1370{1371	return isl_union_map_reverse(isl_union_set_lex_lt_union_set(uset2, uset1));1372}1373 1374__isl_give isl_union_map *isl_union_set_lex_ge_union_set(1375	__isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)1376{1377	return isl_union_map_reverse(isl_union_set_lex_le_union_set(uset2, uset1));1378}1379 1380__isl_give isl_union_map *isl_union_map_lex_gt_union_map(1381	__isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)1382{1383	return isl_union_map_reverse(isl_union_map_lex_lt_union_map(umap2, umap1));1384}1385 1386__isl_give isl_union_map *isl_union_map_lex_ge_union_map(1387	__isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)1388{1389	return isl_union_map_reverse(isl_union_map_lex_le_union_map(umap2, umap1));1390}1391 1392/* Intersect the domain of "umap" with "uset".1393 */1394static __isl_give isl_union_map *union_map_intersect_domain(1395	__isl_take isl_union_map *umap, __isl_take isl_union_set *uset)1396{1397	struct isl_bin_op_control control = {1398		.match_space = &isl_space_domain,1399		.fn_map = &isl_map_intersect_domain,1400	};1401 1402	return gen_bin_op(umap, uset, &control);1403}1404 1405/* Intersect the domain of "umap" with "uset".1406 * If "uset" is a parameters domain, then intersect the parameter1407 * domain of "umap" with this set.1408 */1409__isl_give isl_union_map *isl_union_map_intersect_domain_union_set(1410	__isl_take isl_union_map *umap, __isl_take isl_union_set *uset)1411{1412	if (isl_union_set_is_params(uset))1413		return union_map_intersect_params(umap, uset);1414	else1415		return union_map_intersect_domain(umap, uset);1416}1417 1418/* This is an alternative name for the function above.1419 */1420__isl_give isl_union_map *isl_union_map_intersect_domain(1421	__isl_take isl_union_map *umap, __isl_take isl_union_set *uset)1422{1423	return isl_union_map_intersect_domain_union_set(umap, uset);1424}1425 1426/* Remove the elements of "uset" from the domain of "umap".1427 */1428__isl_give isl_union_map *isl_union_map_subtract_domain(1429	__isl_take isl_union_map *umap, __isl_take isl_union_set *dom)1430{1431	struct isl_bin_op_control control = {1432		.subtract = 1,1433		.match_space = &isl_space_domain,1434		.fn_map = &isl_map_subtract_domain,1435	};1436 1437	return gen_bin_op(umap, dom, &control);1438}1439 1440/* Remove the elements of "uset" from the range of "umap".1441 */1442__isl_give isl_union_map *isl_union_map_subtract_range(1443	__isl_take isl_union_map *umap, __isl_take isl_union_set *dom)1444{1445	struct isl_bin_op_control control = {1446		.subtract = 1,1447		.match_space = &isl_space_range,1448		.fn_map = &isl_map_subtract_range,1449	};1450 1451	return gen_bin_op(umap, dom, &control);1452}1453 1454/* Compute the gist of "umap" with respect to the domain "uset".1455 */1456static __isl_give isl_union_map *union_map_gist_domain(1457	__isl_take isl_union_map *umap, __isl_take isl_union_set *uset)1458{1459	struct isl_bin_op_control control = {1460		.match_space = &isl_space_domain,1461		.fn_map = &isl_map_gist_domain,1462	};1463 1464	return gen_bin_op(umap, uset, &control);1465}1466 1467/* Compute the gist of "umap" with respect to the domain "uset".1468 * If "uset" is a parameters domain, then compute the gist1469 * with respect to this parameter domain.1470 */1471__isl_give isl_union_map *isl_union_map_gist_domain(1472	__isl_take isl_union_map *umap, __isl_take isl_union_set *uset)1473{1474	if (isl_union_set_is_params(uset))1475		return union_map_gist_params(umap, uset);1476	else1477		return union_map_gist_domain(umap, uset);1478}1479 1480/* Compute the gist of "umap" with respect to the range "uset".1481 */1482__isl_give isl_union_map *isl_union_map_gist_range(1483	__isl_take isl_union_map *umap, __isl_take isl_union_set *uset)1484{1485	struct isl_bin_op_control control = {1486		.match_space = &isl_space_range,1487		.fn_map = &isl_map_gist_range,1488	};1489 1490	return gen_bin_op(umap, uset, &control);1491}1492 1493__isl_give isl_union_map *isl_union_map_intersect_range_union_set(1494	__isl_take isl_union_map *umap, __isl_take isl_union_set *uset)1495{1496	struct isl_bin_op_control control = {1497		.match_space = &isl_space_range,1498		.fn_map = &isl_map_intersect_range,1499	};1500 1501	return gen_bin_op(umap, uset, &control);1502}1503 1504/* This is an alternative name for the function above.1505 */1506__isl_give isl_union_map *isl_union_map_intersect_range(1507	__isl_take isl_union_map *umap, __isl_take isl_union_set *uset)1508{1509	return isl_union_map_intersect_range_union_set(umap, uset);1510}1511 1512/* Intersect each map in "umap" in a space [A -> B] -> C1513 * with the corresponding map in "factor" in the space A -> C and1514 * collect the results.1515 */1516__isl_give isl_union_map *isl_union_map_intersect_domain_factor_domain(1517	__isl_take isl_union_map *umap, __isl_take isl_union_map *factor)1518{1519	struct isl_bin_op_control control = {1520		.filter = &isl_map_domain_is_wrapping,1521		.match_space = &isl_space_domain_factor_domain,1522		.fn_map = &isl_map_intersect_domain_factor_domain,1523	};1524 1525	return gen_bin_op(umap, factor, &control);1526}1527 1528/* Intersect each map in "umap" in a space [A -> B] -> C1529 * with the corresponding map in "factor" in the space B -> C and1530 * collect the results.1531 */1532__isl_give isl_union_map *isl_union_map_intersect_domain_factor_range(1533	__isl_take isl_union_map *umap, __isl_take isl_union_map *factor)1534{1535	struct isl_bin_op_control control = {1536		.filter = &isl_map_domain_is_wrapping,1537		.match_space = &isl_space_domain_factor_range,1538		.fn_map = &isl_map_intersect_domain_factor_range,1539	};1540 1541	return gen_bin_op(umap, factor, &control);1542}1543 1544/* Intersect each map in "umap" in a space A -> [B -> C]1545 * with the corresponding map in "factor" in the space A -> B and1546 * collect the results.1547 */1548__isl_give isl_union_map *isl_union_map_intersect_range_factor_domain(1549	__isl_take isl_union_map *umap, __isl_take isl_union_map *factor)1550{1551	struct isl_bin_op_control control = {1552		.filter = &isl_map_range_is_wrapping,1553		.match_space = &isl_space_range_factor_domain,1554		.fn_map = &isl_map_intersect_range_factor_domain,1555	};1556 1557	return gen_bin_op(umap, factor, &control);1558}1559 1560/* Intersect each map in "umap" in a space A -> [B -> C]1561 * with the corresponding map in "factor" in the space A -> C and1562 * collect the results.1563 */1564__isl_give isl_union_map *isl_union_map_intersect_range_factor_range(1565	__isl_take isl_union_map *umap, __isl_take isl_union_map *factor)1566{1567	struct isl_bin_op_control control = {1568		.filter = &isl_map_range_is_wrapping,1569		.match_space = &isl_space_range_factor_range,1570		.fn_map = &isl_map_intersect_range_factor_range,1571	};1572 1573	return gen_bin_op(umap, factor, &control);1574}1575 1576struct isl_union_map_bin_data {1577	isl_union_map *umap2;1578	isl_union_map *res;1579	isl_map *map;1580	isl_stat (*fn)(void **entry, void *user);1581};1582 1583static isl_stat apply_range_entry(void **entry, void *user)1584{1585	struct isl_union_map_bin_data *data = user;1586	isl_map *map2 = *entry;1587	isl_bool empty, match;1588 1589	match = isl_map_tuple_is_equal(data->map, isl_dim_out,1590				map2, isl_dim_in);1591	if (match < 0)1592		return isl_stat_error;1593	if (!match)1594		return isl_stat_ok;1595 1596	map2 = isl_map_apply_range(isl_map_copy(data->map), isl_map_copy(map2));1597 1598	empty = isl_map_is_empty(map2);1599	if (empty < 0) {1600		isl_map_free(map2);1601		return isl_stat_error;1602	}1603	if (empty) {1604		isl_map_free(map2);1605		return isl_stat_ok;1606	}1607 1608	data->res = isl_union_map_add_map(data->res, map2);1609 1610	return isl_stat_ok;1611}1612 1613static isl_stat bin_entry(void **entry, void *user)1614{1615	struct isl_union_map_bin_data *data = user;1616	isl_map *map = *entry;1617 1618	data->map = map;1619	if (isl_hash_table_foreach(data->umap2->dim->ctx, &data->umap2->table,1620				   data->fn, data) < 0)1621		return isl_stat_error;1622 1623	return isl_stat_ok;1624}1625 1626static __isl_give isl_union_map *bin_op(__isl_take isl_union_map *umap1,1627	__isl_take isl_union_map *umap2,1628	isl_stat (*fn)(void **entry, void *user))1629{1630	struct isl_union_map_bin_data data = { NULL, NULL, NULL, fn };1631 1632	umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2));1633	umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1));1634 1635	if (!umap1 || !umap2)1636		goto error;1637 1638	data.umap2 = umap2;1639	data.res = isl_union_map_alloc(isl_space_copy(umap1->dim),1640				       umap1->table.n);1641	if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table,1642				   &bin_entry, &data) < 0)1643		goto error;1644 1645	isl_union_map_free(umap1);1646	isl_union_map_free(umap2);1647	return data.res;1648error:1649	isl_union_map_free(umap1);1650	isl_union_map_free(umap2);1651	isl_union_map_free(data.res);1652	return NULL;1653}1654 1655/* Intersect each map in "umap" in a space [A -> B] -> C1656 * with the corresponding set in "domain" in the space A and1657 * collect the results.1658 */1659__isl_give isl_union_map *1660isl_union_map_intersect_domain_wrapped_domain_union_set(1661	__isl_take isl_union_map *umap, __isl_take isl_union_set *domain)1662{1663	struct isl_bin_op_control control = {1664		.filter = &isl_map_domain_is_wrapping,1665		.match_space = &isl_space_domain_wrapped_domain,1666		.fn_map = &isl_map_intersect_domain_wrapped_domain,1667	};1668 1669	return gen_bin_op(umap, domain, &control);1670}1671 1672/* Intersect each map in "umap" in a space A -> [B -> C]1673 * with the corresponding set in "domain" in the space B and1674 * collect the results.1675 */1676__isl_give isl_union_map *1677isl_union_map_intersect_range_wrapped_domain_union_set(1678	__isl_take isl_union_map *umap, __isl_take isl_union_set *domain)1679{1680	struct isl_bin_op_control control = {1681		.filter = &isl_map_range_is_wrapping,1682		.match_space = &isl_space_range_wrapped_domain,1683		.fn_map = &isl_map_intersect_range_wrapped_domain,1684	};1685 1686	return gen_bin_op(umap, domain, &control);1687}1688 1689__isl_give isl_union_map *isl_union_map_apply_range(1690	__isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)1691{1692	return bin_op(umap1, umap2, &apply_range_entry);1693}1694 1695__isl_give isl_union_map *isl_union_map_apply_domain(1696	__isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)1697{1698	umap1 = isl_union_map_reverse(umap1);1699	umap1 = isl_union_map_apply_range(umap1, umap2);1700	return isl_union_map_reverse(umap1);1701}1702 1703__isl_give isl_union_set *isl_union_set_apply(1704	__isl_take isl_union_set *uset, __isl_take isl_union_map *umap)1705{1706	return isl_union_map_apply_range(uset, umap);1707}1708 1709static isl_stat map_lex_lt_entry(void **entry, void *user)1710{1711	struct isl_union_map_bin_data *data = user;1712	isl_map *map2 = *entry;1713	isl_bool match;1714 1715	match = isl_map_tuple_is_equal(data->map, isl_dim_out,1716				 map2, isl_dim_out);1717	if (match < 0)1718		return isl_stat_error;1719	if (!match)1720		return isl_stat_ok;1721 1722	map2 = isl_map_lex_lt_map(isl_map_copy(data->map), isl_map_copy(map2));1723 1724	data->res = isl_union_map_add_map(data->res, map2);1725 1726	return isl_stat_ok;1727}1728 1729__isl_give isl_union_map *isl_union_map_lex_lt_union_map(1730	__isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)1731{1732	return bin_op(umap1, umap2, &map_lex_lt_entry);1733}1734 1735static isl_stat map_lex_le_entry(void **entry, void *user)1736{1737	struct isl_union_map_bin_data *data = user;1738	isl_map *map2 = *entry;1739	isl_bool match;1740 1741	match = isl_map_tuple_is_equal(data->map, isl_dim_out,1742				 map2, isl_dim_out);1743	if (match < 0)1744		return isl_stat_error;1745	if (!match)1746		return isl_stat_ok;1747 1748	map2 = isl_map_lex_le_map(isl_map_copy(data->map), isl_map_copy(map2));1749 1750	data->res = isl_union_map_add_map(data->res, map2);1751 1752	return isl_stat_ok;1753}1754 1755__isl_give isl_union_map *isl_union_map_lex_le_union_map(1756	__isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)1757{1758	return bin_op(umap1, umap2, &map_lex_le_entry);1759}1760 1761static isl_stat product_entry(void **entry, void *user)1762{1763	struct isl_union_map_bin_data *data = user;1764	isl_map *map2 = *entry;1765 1766	map2 = isl_map_product(isl_map_copy(data->map), isl_map_copy(map2));1767 1768	data->res = isl_union_map_add_map(data->res, map2);1769 1770	return isl_stat_ok;1771}1772 1773__isl_give isl_union_map *isl_union_map_product(__isl_take isl_union_map *umap1,1774	__isl_take isl_union_map *umap2)1775{1776	return bin_op(umap1, umap2, &product_entry);1777}1778 1779static isl_stat set_product_entry(void **entry, void *user)1780{1781	struct isl_union_map_bin_data *data = user;1782	isl_set *set2 = *entry;1783 1784	set2 = isl_set_product(isl_set_copy(data->map), isl_set_copy(set2));1785 1786	data->res = isl_union_set_add_set(data->res, set2);1787 1788	return isl_stat_ok;1789}1790 1791__isl_give isl_union_set *isl_union_set_product(__isl_take isl_union_set *uset1,1792	__isl_take isl_union_set *uset2)1793{1794	return bin_op(uset1, uset2, &set_product_entry);1795}1796 1797static isl_stat domain_product_entry(void **entry, void *user)1798{1799	struct isl_union_map_bin_data *data = user;1800	isl_map *map2 = *entry;1801	isl_bool match;1802 1803	match = isl_map_tuple_is_equal(data->map, isl_dim_out,1804				 map2, isl_dim_out);1805	if (match < 0)1806		return isl_stat_error;1807	if (!match)1808		return isl_stat_ok;1809 1810	map2 = isl_map_domain_product(isl_map_copy(data->map),1811				     isl_map_copy(map2));1812 1813	data->res = isl_union_map_add_map(data->res, map2);1814 1815	return isl_stat_ok;1816}1817 1818/* Given two maps A -> B and C -> D, construct a map [A -> C] -> (B * D)1819 */1820__isl_give isl_union_map *isl_union_map_domain_product(1821	__isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)1822{1823	return bin_op(umap1, umap2, &domain_product_entry);1824}1825 1826static isl_stat range_product_entry(void **entry, void *user)1827{1828	struct isl_union_map_bin_data *data = user;1829	isl_map *map2 = *entry;1830	isl_bool match;1831 1832	match = isl_map_tuple_is_equal(data->map, isl_dim_in, map2, isl_dim_in);1833	if (match < 0)1834		return isl_stat_error;1835	if (!match)1836		return isl_stat_ok;1837 1838	map2 = isl_map_range_product(isl_map_copy(data->map),1839				     isl_map_copy(map2));1840 1841	data->res = isl_union_map_add_map(data->res, map2);1842 1843	return isl_stat_ok;1844}1845 1846__isl_give isl_union_map *isl_union_map_range_product(1847	__isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)1848{1849	return bin_op(umap1, umap2, &range_product_entry);1850}1851 1852/* If data->map A -> B and "map2" C -> D have the same range space,1853 * then add (A, C) -> (B * D) to data->res.1854 */1855static isl_stat flat_domain_product_entry(void **entry, void *user)1856{1857	struct isl_union_map_bin_data *data = user;1858	isl_map *map2 = *entry;1859	isl_bool match;1860 1861	match = isl_map_tuple_is_equal(data->map, isl_dim_out,1862				 map2, isl_dim_out);1863	if (match < 0)1864		return isl_stat_error;1865	if (!match)1866		return isl_stat_ok;1867 1868	map2 = isl_map_flat_domain_product(isl_map_copy(data->map),1869					  isl_map_copy(map2));1870 1871	data->res = isl_union_map_add_map(data->res, map2);1872 1873	return isl_stat_ok;1874}1875 1876/* Given two maps A -> B and C -> D, construct a map (A, C) -> (B * D).1877 */1878__isl_give isl_union_map *isl_union_map_flat_domain_product(1879	__isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)1880{1881	return bin_op(umap1, umap2, &flat_domain_product_entry);1882}1883 1884static isl_stat flat_range_product_entry(void **entry, void *user)1885{1886	struct isl_union_map_bin_data *data = user;1887	isl_map *map2 = *entry;1888	isl_bool match;1889 1890	match = isl_map_tuple_is_equal(data->map, isl_dim_in, map2, isl_dim_in);1891	if (match < 0)1892		return isl_stat_error;1893	if (!match)1894		return isl_stat_ok;1895 1896	map2 = isl_map_flat_range_product(isl_map_copy(data->map),1897					  isl_map_copy(map2));1898 1899	data->res = isl_union_map_add_map(data->res, map2);1900 1901	return isl_stat_ok;1902}1903 1904__isl_give isl_union_map *isl_union_map_flat_range_product(1905	__isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)1906{1907	return bin_op(umap1, umap2, &flat_range_product_entry);1908}1909 1910/* Data structure that specifies how un_op should modify1911 * the maps in the union map.1912 *1913 * If "inplace" is set, then the maps in the input union map1914 * are modified in place.  This means that "fn_map" should not1915 * change the meaning of the map or that the union map only1916 * has a single reference.1917 * If "total" is set, then all maps need to be modified and1918 * the results need to live in the same space.1919 * Otherwise, a new union map is constructed to store the results.1920 * If "filter" is not NULL, then only the input maps that satisfy "filter"1921 * are taken into account.  "filter_user" is passed as the second argument1922 * to "filter".  No filter can be set if "inplace" or1923 * "total" is set.1924 * At most one of "fn_map" or "fn_map2" can be set, specifying1925 * how the maps (selected by "filter") should be transformed.1926 * If "fn_map2" is set, then "fn_map2_user" is passed as the second argument.1927 */1928struct isl_un_op_control {1929	int inplace;1930	int total;1931	isl_bool (*filter)(__isl_keep isl_map *map, void *user);1932	void *filter_user;1933	__isl_give isl_map *(*fn_map)(__isl_take isl_map *map);1934	__isl_give isl_map *(*fn_map2)(__isl_take isl_map *map, void *user);1935	void *fn_map2_user;1936};1937 1938/* Data structure for wrapping the data for un_op_filter_drop_user.1939 * "filter" is the function that is being wrapped.1940 */1941struct isl_un_op_drop_user_data {1942	isl_bool (*filter)(__isl_keep isl_map *map);1943};1944 1945/* Wrapper for isl_un_op_control filters that do not require1946 * a second argument.1947 * Simply call data->filter without the second argument.1948 */1949static isl_bool un_op_filter_drop_user(__isl_keep isl_map *map, void *user)1950{1951	struct isl_un_op_drop_user_data *data = user;1952	return data->filter(map);1953}1954 1955/* Internal data structure for "un_op".1956 * "control" specifies how the maps in the union map should be modified.1957 * "res" collects the results.1958 */1959struct isl_union_map_un_data {1960	struct isl_un_op_control *control;1961	isl_union_map *res;1962};1963 1964/* isl_hash_table_foreach callback for un_op.1965 * Handle the map that "entry" points to.1966 *1967 * If control->filter is set, then check if this map satisfies the filter.1968 * If so (or if control->filter is not set), modify the map1969 * by calling control->fn_map or control->fn_map2 (if set) and1970 * either add the result to data->res or1971 * replace the original entry by the result (if control->inplace is set).1972 */1973static isl_stat un_entry(void **entry, void *user)1974{1975	struct isl_union_map_un_data *data = user;1976	struct isl_un_op_control *control = data->control;1977	isl_map *map = *entry;1978 1979	if (control->filter) {1980		isl_bool ok;1981 1982		ok = control->filter(map, control->filter_user);1983		if (ok < 0)1984			return isl_stat_error;1985		if (!ok)1986			return isl_stat_ok;1987	}1988 1989	map = isl_map_copy(map);1990	if (control->fn_map2 != NULL)1991		map = control->fn_map2(map, control->fn_map2_user);1992	else if (control->fn_map != NULL)1993		map = control->fn_map(map);1994	if (!map)1995		return isl_stat_error;1996	if (control->inplace) {1997		isl_map_free(*entry);1998		*entry = map;1999	} else {2000		data->res = isl_union_map_add_map(data->res, map);2001		if (!data->res)2002			return isl_stat_error;2003	}2004 2005	return isl_stat_ok;2006}2007 2008/* Modify the maps in "umap" based on "control".2009 * If control->inplace is set, then modify the maps in "umap" in-place.2010 * Otherwise, create a new union map to hold the results.2011 * If control->total is set, then perform an inplace computation2012 * if "umap" is only referenced once.  Otherwise, create a new union map2013 * to store the results.2014 */2015static __isl_give isl_union_map *un_op(__isl_take isl_union_map *umap,2016	struct isl_un_op_control *control)2017{2018	struct isl_union_map_un_data data = { control };2019 2020	if (!umap)2021		return NULL;2022	if (!!control->fn_map && !!control->fn_map2)2023		isl_die(isl_union_map_get_ctx(umap), isl_error_internal,2024			"at most one mapping function can be specified",2025			return isl_union_map_free(umap));2026	if ((control->inplace || control->total) && control->filter)2027		isl_die(isl_union_map_get_ctx(umap), isl_error_invalid,2028			"inplace/total modification cannot be filtered",2029			return isl_union_map_free(umap));2030 2031	if (control->total && umap->ref == 1)2032		control->inplace = 1;2033	if (control->inplace) {2034		data.res = umap;2035	} else {2036		isl_space *space;2037 2038		space = isl_union_map_get_space(umap);2039		data.res = isl_union_map_alloc(space, umap->table.n);2040	}2041	if (isl_hash_table_foreach(isl_union_map_get_ctx(umap),2042				    &umap->table, &un_entry, &data) < 0)2043		data.res = isl_union_map_free(data.res);2044 2045	if (control->inplace)2046		return data.res;2047	isl_union_map_free(umap);2048	return data.res;2049}2050 2051__isl_give isl_union_map *isl_union_map_from_range(2052	__isl_take isl_union_set *uset)2053{2054	struct isl_un_op_control control = {2055		.fn_map = &isl_map_from_range,2056	};2057	return un_op(uset, &control);2058}2059 2060__isl_give isl_union_map *isl_union_map_from_domain(2061	__isl_take isl_union_set *uset)2062{2063	return isl_union_map_reverse(isl_union_map_from_range(uset));2064}2065 2066__isl_give isl_union_map *isl_union_map_from_domain_and_range(2067	__isl_take isl_union_set *domain, __isl_take isl_union_set *range)2068{2069	return isl_union_map_apply_range(isl_union_map_from_domain(domain),2070				         isl_union_map_from_range(range));2071}2072 2073/* Modify the maps in "umap" by applying "fn" on them.2074 * "fn" should apply to all maps in "umap" and should not modify the space.2075 */2076static __isl_give isl_union_map *total(__isl_take isl_union_map *umap,2077	__isl_give isl_map *(*fn)(__isl_take isl_map *))2078{2079	struct isl_un_op_control control = {2080		.total = 1,2081		.fn_map = fn,2082	};2083 2084	return un_op(umap, &control);2085}2086 2087/* Compute the affine hull of "map" and return the result as an isl_map.2088 */2089static __isl_give isl_map *isl_map_affine_hull_map(__isl_take isl_map *map)2090{2091	return isl_map_from_basic_map(isl_map_affine_hull(map));2092}2093 2094__isl_give isl_union_map *isl_union_map_affine_hull(2095	__isl_take isl_union_map *umap)2096{2097	return total(umap, &isl_map_affine_hull_map);2098}2099 2100__isl_give isl_union_set *isl_union_set_affine_hull(2101	__isl_take isl_union_set *uset)2102{2103	return isl_union_map_affine_hull(uset);2104}2105 2106/* Wrapper around isl_set_combined_lineality_space2107 * that returns the combined lineality space in the form of an isl_set2108 * instead of an isl_basic_set.2109 */2110static __isl_give isl_set *combined_lineality_space(__isl_take isl_set *set)2111{2112	return isl_set_from_basic_set(isl_set_combined_lineality_space(set));2113}2114 2115/* For each set in "uset", compute the (linear) hull2116 * of the lineality spaces of its basic sets and2117 * collect and return the results.2118 */2119__isl_give isl_union_set *isl_union_set_combined_lineality_space(2120	__isl_take isl_union_set *uset)2121{2122	struct isl_un_op_control control = {2123		.fn_map = &combined_lineality_space,2124	};2125	return un_op(uset, &control);2126}2127 2128/* Compute the polyhedral hull of "map" and return the result as an isl_map.2129 */2130static __isl_give isl_map *isl_map_polyhedral_hull_map(__isl_take isl_map *map)2131{2132	return isl_map_from_basic_map(isl_map_polyhedral_hull(map));2133}2134 2135__isl_give isl_union_map *isl_union_map_polyhedral_hull(2136	__isl_take isl_union_map *umap)2137{2138	return total(umap, &isl_map_polyhedral_hull_map);2139}2140 2141__isl_give isl_union_set *isl_union_set_polyhedral_hull(2142	__isl_take isl_union_set *uset)2143{2144	return isl_union_map_polyhedral_hull(uset);2145}2146 2147/* Compute a superset of the convex hull of "map" that is described2148 * by only translates of the constraints in the constituents of "map" and2149 * return the result as an isl_map.2150 */2151static __isl_give isl_map *isl_map_simple_hull_map(__isl_take isl_map *map)2152{2153	return isl_map_from_basic_map(isl_map_simple_hull(map));2154}2155 2156__isl_give isl_union_map *isl_union_map_simple_hull(2157	__isl_take isl_union_map *umap)2158{2159	return total(umap, &isl_map_simple_hull_map);2160}2161 2162__isl_give isl_union_set *isl_union_set_simple_hull(2163	__isl_take isl_union_set *uset)2164{2165	return isl_union_map_simple_hull(uset);2166}2167 2168static __isl_give isl_union_map *inplace(__isl_take isl_union_map *umap,2169	__isl_give isl_map *(*fn)(__isl_take isl_map *))2170{2171	struct isl_un_op_control control = {2172		.inplace = 1,2173		.fn_map = fn,2174	};2175 2176	return un_op(umap, &control);2177}2178 2179/* Remove redundant constraints in each of the basic maps of "umap".2180 * Since removing redundant constraints does not change the meaning2181 * or the space, the operation can be performed in-place.2182 */2183__isl_give isl_union_map *isl_union_map_remove_redundancies(2184	__isl_take isl_union_map *umap)2185{2186	return inplace(umap, &isl_map_remove_redundancies);2187}2188 2189/* Remove redundant constraints in each of the basic sets of "uset".2190 */2191__isl_give isl_union_set *isl_union_set_remove_redundancies(2192	__isl_take isl_union_set *uset)2193{2194	return isl_union_map_remove_redundancies(uset);2195}2196 2197__isl_give isl_union_map *isl_union_map_coalesce(2198	__isl_take isl_union_map *umap)2199{2200	return inplace(umap, &isl_map_coalesce);2201}2202 2203__isl_give isl_union_set *isl_union_set_coalesce(2204	__isl_take isl_union_set *uset)2205{2206	return isl_union_map_coalesce(uset);2207}2208 2209__isl_give isl_union_map *isl_union_map_detect_equalities(2210	__isl_take isl_union_map *umap)2211{2212	return inplace(umap, &isl_map_detect_equalities);2213}2214 2215__isl_give isl_union_set *isl_union_set_detect_equalities(2216	__isl_take isl_union_set *uset)2217{2218	return isl_union_map_detect_equalities(uset);2219}2220 2221__isl_give isl_union_map *isl_union_map_compute_divs(2222	__isl_take isl_union_map *umap)2223{2224	return inplace(umap, &isl_map_compute_divs);2225}2226 2227__isl_give isl_union_set *isl_union_set_compute_divs(2228	__isl_take isl_union_set *uset)2229{2230	return isl_union_map_compute_divs(uset);2231}2232 2233__isl_give isl_union_map *isl_union_map_lexmin(2234	__isl_take isl_union_map *umap)2235{2236	return total(umap, &isl_map_lexmin);2237}2238 2239__isl_give isl_union_set *isl_union_set_lexmin(2240	__isl_take isl_union_set *uset)2241{2242	return isl_union_map_lexmin(uset);2243}2244 2245__isl_give isl_union_map *isl_union_map_lexmax(2246	__isl_take isl_union_map *umap)2247{2248	return total(umap, &isl_map_lexmax);2249}2250 2251__isl_give isl_union_set *isl_union_set_lexmax(2252	__isl_take isl_union_set *uset)2253{2254	return isl_union_map_lexmax(uset);2255}2256 2257/* Return the universe in the space of "map".2258 */2259static __isl_give isl_map *universe(__isl_take isl_map *map)2260{2261	isl_space *space;2262 2263	space = isl_map_get_space(map);2264	isl_map_free(map);2265	return isl_map_universe(space);2266}2267 2268__isl_give isl_union_map *isl_union_map_universe(__isl_take isl_union_map *umap)2269{2270	struct isl_un_op_control control = {2271		.fn_map = &universe,2272	};2273	return un_op(umap, &control);2274}2275 2276__isl_give isl_union_set *isl_union_set_universe(__isl_take isl_union_set *uset)2277{2278	return isl_union_map_universe(uset);2279}2280 2281__isl_give isl_union_map *isl_union_map_reverse(__isl_take isl_union_map *umap)2282{2283	struct isl_un_op_control control = {2284		.fn_map = &isl_map_reverse,2285	};2286	return un_op(umap, &control);2287}2288 2289/* Given a union map, take the maps of the form A -> (B -> C) and2290 * return the union of the corresponding maps A -> (C -> B).2291 */2292__isl_give isl_union_map *isl_union_map_range_reverse(2293	__isl_take isl_union_map *umap)2294{2295	struct isl_un_op_drop_user_data data = { &isl_map_range_is_wrapping };2296	struct isl_un_op_control control = {2297		.filter = &un_op_filter_drop_user,2298		.filter_user = &data,2299		.fn_map = &isl_map_range_reverse,2300	};2301	return un_op(umap, &control);2302}2303 2304/* Compute the parameter domain of the given union map.2305 */2306__isl_give isl_set *isl_union_map_params(__isl_take isl_union_map *umap)2307{2308	struct isl_un_op_control control = {2309		.fn_map = &isl_map_params,2310	};2311	int empty;2312 2313	empty = isl_union_map_is_empty(umap);2314	if (empty < 0)2315		goto error;2316	if (empty) {2317		isl_space *space;2318		space = isl_union_map_get_space(umap);2319		isl_union_map_free(umap);2320		return isl_set_empty(space);2321	}2322	return isl_set_from_union_set(un_op(umap, &control));2323error:2324	isl_union_map_free(umap);2325	return NULL;2326}2327 2328/* Compute the parameter domain of the given union set.2329 */2330__isl_give isl_set *isl_union_set_params(__isl_take isl_union_set *uset)2331{2332	return isl_union_map_params(uset);2333}2334 2335__isl_give isl_union_set *isl_union_map_domain(__isl_take isl_union_map *umap)2336{2337	struct isl_un_op_control control = {2338		.fn_map = &isl_map_domain,2339	};2340	return un_op(umap, &control);2341}2342 2343__isl_give isl_union_set *isl_union_map_range(__isl_take isl_union_map *umap)2344{2345	struct isl_un_op_control control = {2346		.fn_map = &isl_map_range,2347	};2348	return un_op(umap, &control);2349}2350 2351__isl_give isl_union_map *isl_union_map_domain_map(2352	__isl_take isl_union_map *umap)2353{2354	struct isl_un_op_control control = {2355		.fn_map = &isl_map_domain_map,2356	};2357	return un_op(umap, &control);2358}2359 2360/* Construct an isl_pw_multi_aff that maps "map" to its domain and2361 * add the result to "res".2362 */2363static isl_stat domain_map_upma(__isl_take isl_map *map, void *user)2364{2365	isl_union_pw_multi_aff **res = user;2366	isl_multi_aff *ma;2367	isl_pw_multi_aff *pma;2368 2369	ma = isl_multi_aff_domain_map(isl_map_get_space(map));2370	pma = isl_pw_multi_aff_alloc(isl_map_wrap(map), ma);2371	*res = isl_union_pw_multi_aff_add_pw_multi_aff(*res, pma);2372 2373	return *res ? isl_stat_ok : isl_stat_error;2374 2375}2376 2377/* Return an isl_union_pw_multi_aff that maps a wrapped copy of "umap"2378 * to its domain.2379 */2380__isl_give isl_union_pw_multi_aff *isl_union_map_domain_map_union_pw_multi_aff(2381	__isl_take isl_union_map *umap)2382{2383	isl_union_pw_multi_aff *res;2384 2385	res = isl_union_pw_multi_aff_empty(isl_union_map_get_space(umap));2386	if (isl_union_map_foreach_map(umap, &domain_map_upma, &res) < 0)2387		res = isl_union_pw_multi_aff_free(res);2388 2389	isl_union_map_free(umap);2390	return res;2391}2392 2393__isl_give isl_union_map *isl_union_map_range_map(2394	__isl_take isl_union_map *umap)2395{2396	struct isl_un_op_control control = {2397		.fn_map = &isl_map_range_map,2398	};2399	return un_op(umap, &control);2400}2401 2402/* Given a collection of wrapped maps of the form A[B -> C],2403 * return the collection of maps A[B -> C] -> B.2404 */2405__isl_give isl_union_map *isl_union_set_wrapped_domain_map(2406	__isl_take isl_union_set *uset)2407{2408	struct isl_un_op_drop_user_data data = { &isl_set_is_wrapping };2409	struct isl_un_op_control control = {2410		.filter = &un_op_filter_drop_user,2411		.filter_user = &data,2412		.fn_map = &isl_set_wrapped_domain_map,2413	};2414	return un_op(uset, &control);2415}2416 2417/* Does "map" relate elements from the same space?2418 */2419static isl_bool equal_tuples(__isl_keep isl_map *map, void *user)2420{2421	return isl_map_tuple_is_equal(map, isl_dim_in, map, isl_dim_out);2422}2423 2424__isl_give isl_union_set *isl_union_map_deltas(__isl_take isl_union_map *umap)2425{2426	struct isl_un_op_control control = {2427		.filter = &equal_tuples,2428		.fn_map = &isl_map_deltas,2429	};2430	return un_op(umap, &control);2431}2432 2433__isl_give isl_union_map *isl_union_map_deltas_map(2434	__isl_take isl_union_map *umap)2435{2436	struct isl_un_op_control control = {2437		.filter = &equal_tuples,2438		.fn_map = &isl_map_deltas_map,2439	};2440	return un_op(umap, &control);2441}2442 2443__isl_give isl_union_map *isl_union_set_identity(__isl_take isl_union_set *uset)2444{2445	struct isl_un_op_control control = {2446		.fn_map = &isl_set_identity,2447	};2448	return un_op(uset, &control);2449}2450 2451/* Construct an identity isl_pw_multi_aff on "set" and add it to *res.2452 */2453static isl_stat identity_upma(__isl_take isl_set *set, void *user)2454{2455	isl_union_pw_multi_aff **res = user;2456	isl_space *space;2457	isl_pw_multi_aff *pma;2458 2459	space = isl_space_map_from_set(isl_set_get_space(set));2460	pma = isl_pw_multi_aff_identity(space);2461	pma = isl_pw_multi_aff_intersect_domain(pma, set);2462	*res = isl_union_pw_multi_aff_add_pw_multi_aff(*res, pma);2463 2464	return *res ? isl_stat_ok : isl_stat_error;2465}2466 2467/* Return an identity function on "uset" in the form2468 * of an isl_union_pw_multi_aff.2469 */2470__isl_give isl_union_pw_multi_aff *isl_union_set_identity_union_pw_multi_aff(2471	__isl_take isl_union_set *uset)2472{2473	isl_union_pw_multi_aff *res;2474 2475	res = isl_union_pw_multi_aff_empty(isl_union_set_get_space(uset));2476	if (isl_union_set_foreach_set(uset, &identity_upma, &res) < 0)2477		res = isl_union_pw_multi_aff_free(res);2478 2479	isl_union_set_free(uset);2480	return res;2481}2482 2483/* For each map in "umap" of the form [A -> B] -> C,2484 * construct the map A -> C and collect the results.2485 */2486__isl_give isl_union_map *isl_union_map_domain_factor_domain(2487	__isl_take isl_union_map *umap)2488{2489	struct isl_un_op_drop_user_data data = { &isl_map_domain_is_wrapping };2490	struct isl_un_op_control control = {2491		.filter = &un_op_filter_drop_user,2492		.filter_user = &data,2493		.fn_map = &isl_map_domain_factor_domain,2494	};2495	return un_op(umap, &control);2496}2497 2498/* For each map in "umap" of the form [A -> B] -> C,2499 * construct the map B -> C and collect the results.2500 */2501__isl_give isl_union_map *isl_union_map_domain_factor_range(2502	__isl_take isl_union_map *umap)2503{2504	struct isl_un_op_drop_user_data data = { &isl_map_domain_is_wrapping };2505	struct isl_un_op_control control = {2506		.filter = &un_op_filter_drop_user,2507		.filter_user = &data,2508		.fn_map = &isl_map_domain_factor_range,2509	};2510	return un_op(umap, &control);2511}2512 2513/* For each map in "umap" of the form A -> [B -> C],2514 * construct the map A -> B and collect the results.2515 */2516__isl_give isl_union_map *isl_union_map_range_factor_domain(2517	__isl_take isl_union_map *umap)2518{2519	struct isl_un_op_drop_user_data data = { &isl_map_range_is_wrapping };2520	struct isl_un_op_control control = {2521		.filter = &un_op_filter_drop_user,2522		.filter_user = &data,2523		.fn_map = &isl_map_range_factor_domain,2524	};2525	return un_op(umap, &control);2526}2527 2528/* For each map in "umap" of the form A -> [B -> C],2529 * construct the map A -> C and collect the results.2530 */2531__isl_give isl_union_map *isl_union_map_range_factor_range(2532	__isl_take isl_union_map *umap)2533{2534	struct isl_un_op_drop_user_data data = { &isl_map_range_is_wrapping };2535	struct isl_un_op_control control = {2536		.filter = &un_op_filter_drop_user,2537		.filter_user = &data,2538		.fn_map = &isl_map_range_factor_range,2539	};2540	return un_op(umap, &control);2541}2542 2543/* For each map in "umap" of the form [A -> B] -> [C -> D],2544 * construct the map A -> C and collect the results.2545 */2546__isl_give isl_union_map *isl_union_map_factor_domain(2547	__isl_take isl_union_map *umap)2548{2549	struct isl_un_op_drop_user_data data = { &isl_map_is_product };2550	struct isl_un_op_control control = {2551		.filter = &un_op_filter_drop_user,2552		.filter_user = &data,2553		.fn_map = &isl_map_factor_domain,2554	};2555	return un_op(umap, &control);2556}2557 2558/* For each map in "umap" of the form [A -> B] -> [C -> D],2559 * construct the map B -> D and collect the results.2560 */2561__isl_give isl_union_map *isl_union_map_factor_range(2562	__isl_take isl_union_map *umap)2563{2564	struct isl_un_op_drop_user_data data = { &isl_map_is_product };2565	struct isl_un_op_control control = {2566		.filter = &un_op_filter_drop_user,2567		.filter_user = &data,2568		.fn_map = &isl_map_factor_range,2569	};2570	return un_op(umap, &control);2571}2572 2573__isl_give isl_union_map *isl_union_set_unwrap(__isl_take isl_union_set *uset)2574{2575	struct isl_un_op_drop_user_data data = { &isl_set_is_wrapping };2576	struct isl_un_op_control control = {2577		.filter = &un_op_filter_drop_user,2578		.filter_user = &data,2579		.fn_map = &isl_set_unwrap,2580	};2581	return un_op(uset, &control);2582}2583 2584__isl_give isl_union_set *isl_union_map_wrap(__isl_take isl_union_map *umap)2585{2586	struct isl_un_op_control control = {2587		.fn_map = &isl_map_wrap,2588	};2589	return un_op(umap, &control);2590}2591 2592struct isl_union_map_is_subset_data {2593	isl_union_map *umap2;2594	isl_bool is_subset;2595};2596 2597static isl_stat is_subset_entry(void **entry, void *user)2598{2599	struct isl_union_map_is_subset_data *data = user;2600	struct isl_hash_table_entry *entry2;2601	isl_space *space;2602	isl_map *map = *entry;2603 2604	space = isl_map_peek_space(map);2605	entry2 = isl_union_map_find_entry(data->umap2, space, 0);2606	if (!entry2)2607		return isl_stat_error;2608	if (entry2 == isl_hash_table_entry_none) {2609		int empty = isl_map_is_empty(map);2610		if (empty < 0)2611			return isl_stat_error;2612		if (empty)2613			return isl_stat_ok;2614		data->is_subset = isl_bool_false;2615		return isl_stat_error;2616	}2617 2618	data->is_subset = isl_map_is_subset(map, entry2->data);2619	if (data->is_subset < 0 || !data->is_subset)2620		return isl_stat_error;2621 2622	return isl_stat_ok;2623}2624 2625isl_bool isl_union_map_is_subset(__isl_keep isl_union_map *umap1,2626	__isl_keep isl_union_map *umap2)2627{2628	struct isl_union_map_is_subset_data data = { NULL, isl_bool_true };2629 2630	if (!umap1 || !umap2)2631		return isl_bool_error;2632 2633	data.umap2 = umap2;2634	if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table,2635				   &is_subset_entry, &data) < 0 &&2636	    data.is_subset)2637		return isl_bool_error;2638 2639	return data.is_subset;2640}2641 2642isl_bool isl_union_set_is_subset(__isl_keep isl_union_set *uset1,2643	__isl_keep isl_union_set *uset2)2644{2645	return isl_union_map_is_subset(uset1, uset2);2646}2647 2648isl_bool isl_union_map_is_equal(__isl_keep isl_union_map *umap1,2649	__isl_keep isl_union_map *umap2)2650{2651	isl_bool is_subset;2652 2653	if (!umap1 || !umap2)2654		return isl_bool_error;2655	is_subset = isl_union_map_is_subset(umap1, umap2);2656	if (is_subset != isl_bool_true)2657		return is_subset;2658	is_subset = isl_union_map_is_subset(umap2, umap1);2659	return is_subset;2660}2661 2662isl_bool isl_union_set_is_equal(__isl_keep isl_union_set *uset1,2663	__isl_keep isl_union_set *uset2)2664{2665	return isl_union_map_is_equal(uset1, uset2);2666}2667 2668isl_bool isl_union_map_is_strict_subset(__isl_keep isl_union_map *umap1,2669	__isl_keep isl_union_map *umap2)2670{2671	isl_bool is_subset;2672 2673	if (!umap1 || !umap2)2674		return isl_bool_error;2675	is_subset = isl_union_map_is_subset(umap1, umap2);2676	if (is_subset != isl_bool_true)2677		return is_subset;2678	is_subset = isl_union_map_is_subset(umap2, umap1);2679	return isl_bool_not(is_subset);2680}2681 2682isl_bool isl_union_set_is_strict_subset(__isl_keep isl_union_set *uset1,2683	__isl_keep isl_union_set *uset2)2684{2685	return isl_union_map_is_strict_subset(uset1, uset2);2686}2687 2688/* Internal data structure for isl_union_map_is_disjoint.2689 * umap2 is the union map with which we are comparing.2690 * is_disjoint is initialized to 1 and is set to 0 as soon2691 * as the union maps turn out not to be disjoint.2692 */2693struct isl_union_map_is_disjoint_data {2694	isl_union_map *umap2;2695	isl_bool is_disjoint;2696};2697 2698/* Check if "map" is disjoint from data->umap2 and abort2699 * the search if it is not.2700 */2701static isl_stat is_disjoint_entry(void **entry, void *user)2702{2703	struct isl_union_map_is_disjoint_data *data = user;2704	struct isl_hash_table_entry *entry2;2705	isl_space *space;2706	isl_map *map = *entry;2707 2708	space = isl_map_peek_space(map);2709	entry2 = isl_union_map_find_entry(data->umap2, space, 0);2710	if (!entry2)2711		return isl_stat_error;2712	if (entry2 == isl_hash_table_entry_none)2713		return isl_stat_ok;2714 2715	data->is_disjoint = isl_map_is_disjoint(map, entry2->data);2716	if (data->is_disjoint < 0 || !data->is_disjoint)2717		return isl_stat_error;2718 2719	return isl_stat_ok;2720}2721 2722/* Are "umap1" and "umap2" disjoint?2723 */2724isl_bool isl_union_map_is_disjoint(__isl_keep isl_union_map *umap1,2725	__isl_keep isl_union_map *umap2)2726{2727	struct isl_union_map_is_disjoint_data data = { NULL, isl_bool_true };2728 2729	umap1 = isl_union_map_copy(umap1);2730	umap2 = isl_union_map_copy(umap2);2731	umap1 = isl_union_map_align_params(umap1,2732						isl_union_map_get_space(umap2));2733	umap2 = isl_union_map_align_params(umap2,2734						isl_union_map_get_space(umap1));2735 2736	if (!umap1 || !umap2)2737		goto error;2738 2739	data.umap2 = umap2;2740	if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table,2741				   &is_disjoint_entry, &data) < 0 &&2742	    data.is_disjoint)2743		goto error;2744 2745	isl_union_map_free(umap1);2746	isl_union_map_free(umap2);2747 2748	return data.is_disjoint;2749error:2750	isl_union_map_free(umap1);2751	isl_union_map_free(umap2);2752	return isl_bool_error;2753}2754 2755/* Are "uset1" and "uset2" disjoint?2756 */2757isl_bool isl_union_set_is_disjoint(__isl_keep isl_union_set *uset1,2758	__isl_keep isl_union_set *uset2)2759{2760	return isl_union_map_is_disjoint(uset1, uset2);2761}2762 2763static isl_stat sample_entry(void **entry, void *user)2764{2765	isl_basic_map **sample = (isl_basic_map **)user;2766	isl_map *map = *entry;2767 2768	*sample = isl_map_sample(isl_map_copy(map));2769	if (!*sample)2770		return isl_stat_error;2771	if (!isl_basic_map_plain_is_empty(*sample))2772		return isl_stat_error;2773	return isl_stat_ok;2774}2775 2776__isl_give isl_basic_map *isl_union_map_sample(__isl_take isl_union_map *umap)2777{2778	isl_basic_map *sample = NULL;2779 2780	if (!umap)2781		return NULL;2782 2783	if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,2784				   &sample_entry, &sample) < 0 &&2785	    !sample)2786		goto error;2787 2788	if (!sample)2789		sample = isl_basic_map_empty(isl_union_map_get_space(umap));2790 2791	isl_union_map_free(umap);2792 2793	return sample;2794error:2795	isl_union_map_free(umap);2796	return NULL;2797}2798 2799__isl_give isl_basic_set *isl_union_set_sample(__isl_take isl_union_set *uset)2800{2801	return bset_from_bmap(isl_union_map_sample(uset));2802}2803 2804/* Return an element in "uset" in the form of an isl_point.2805 * Return a void isl_point if "uset" is empty.2806 */2807__isl_give isl_point *isl_union_set_sample_point(__isl_take isl_union_set *uset)2808{2809	return isl_basic_set_sample_point(isl_union_set_sample(uset));2810}2811 2812struct isl_forall_data {2813	isl_bool res;2814	isl_bool (*fn)(__isl_keep isl_map *map);2815};2816 2817static isl_stat forall_entry(void **entry, void *user)2818{2819	struct isl_forall_data *data = user;2820	isl_map *map = *entry;2821 2822	data->res = data->fn(map);2823	if (data->res < 0)2824		return isl_stat_error;2825 2826	if (!data->res)2827		return isl_stat_error;2828 2829	return isl_stat_ok;2830}2831 2832static isl_bool union_map_forall(__isl_keep isl_union_map *umap,2833	isl_bool (*fn)(__isl_keep isl_map *map))2834{2835	struct isl_forall_data data = { isl_bool_true, fn };2836 2837	if (!umap)2838		return isl_bool_error;2839 2840	if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,2841				   &forall_entry, &data) < 0 && data.res)2842		return isl_bool_error;2843 2844	return data.res;2845}2846 2847struct isl_forall_user_data {2848	isl_bool res;2849	isl_bool (*fn)(__isl_keep isl_map *map, void *user);2850	void *user;2851};2852 2853static isl_stat forall_user_entry(void **entry, void *user)2854{2855	struct isl_forall_user_data *data = user;2856	isl_map *map = *entry;2857 2858	data->res = data->fn(map, data->user);2859	if (data->res < 0)2860		return isl_stat_error;2861 2862	if (!data->res)2863		return isl_stat_error;2864 2865	return isl_stat_ok;2866}2867 2868/* Check if fn(map, user) returns true for all maps "map" in umap.2869 */2870static isl_bool union_map_forall_user(__isl_keep isl_union_map *umap,2871	isl_bool (*fn)(__isl_keep isl_map *map, void *user), void *user)2872{2873	struct isl_forall_user_data data = { isl_bool_true, fn, user };2874 2875	if (!umap)2876		return isl_bool_error;2877 2878	if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,2879				   &forall_user_entry, &data) < 0 && data.res)2880		return isl_bool_error;2881 2882	return data.res;2883}2884 2885/* Is "umap" obviously empty?2886 */2887isl_bool isl_union_map_plain_is_empty(__isl_keep isl_union_map *umap)2888{2889	isl_size n;2890 2891	n = isl_union_map_n_map(umap);2892	if (n < 0)2893		return isl_bool_error;2894	return n == 0;2895}2896 2897isl_bool isl_union_map_is_empty(__isl_keep isl_union_map *umap)2898{2899	return union_map_forall(umap, &isl_map_is_empty);2900}2901 2902isl_bool isl_union_set_is_empty(__isl_keep isl_union_set *uset)2903{2904	return isl_union_map_is_empty(uset);2905}2906 2907static isl_bool is_subset_of_identity(__isl_keep isl_map *map)2908{2909	isl_bool is_subset;2910	isl_space *space;2911	isl_map *id;2912	isl_bool match;2913 2914	match = isl_map_tuple_is_equal(map, isl_dim_in, map, isl_dim_out);2915	if (match < 0)2916		return isl_bool_error;2917	if (!match)2918		return isl_bool_false;2919 2920	space = isl_map_get_space(map);2921	id = isl_map_identity(space);2922 2923	is_subset = isl_map_is_subset(map, id);2924 2925	isl_map_free(id);2926 2927	return is_subset;2928}2929 2930/* Given an isl_union_map that consists of a single map, check2931 * if it is single-valued.2932 */2933static isl_bool single_map_is_single_valued(__isl_keep isl_union_map *umap)2934{2935	isl_map *map;2936	isl_bool sv;2937 2938	umap = isl_union_map_copy(umap);2939	map = isl_map_from_union_map(umap);2940	sv = isl_map_is_single_valued(map);2941	isl_map_free(map);2942 2943	return sv;2944}2945 2946/* Internal data structure for single_valued_on_domain.2947 *2948 * "umap" is the union map to be tested.2949 * "sv" is set to 1 as long as "umap" may still be single-valued.2950 */2951struct isl_union_map_is_sv_data {2952	isl_union_map *umap;2953	isl_bool sv;2954};2955 2956/* Check if the data->umap is single-valued on "set".2957 *2958 * If data->umap consists of a single map on "set", then test it2959 * as an isl_map.2960 *2961 * Otherwise, compute2962 *2963 *	M \circ M^-12964 *2965 * check if the result is a subset of the identity mapping and2966 * store the result in data->sv.2967 *2968 * Terminate as soon as data->umap has been determined not to2969 * be single-valued.2970 */2971static isl_stat single_valued_on_domain(__isl_take isl_set *set, void *user)2972{2973	struct isl_union_map_is_sv_data *data = user;2974	isl_union_map *umap, *test;2975	isl_size n;2976 2977	umap = isl_union_map_copy(data->umap);2978	umap = isl_union_map_intersect_domain(umap,2979						isl_union_set_from_set(set));2980 2981	n = isl_union_map_n_map(umap);2982	if (n < 0) {2983		data->sv = isl_bool_error;2984	} else if (n == 1) {2985		data->sv = single_map_is_single_valued(umap);2986		isl_union_map_free(umap);2987	} else {2988		test = isl_union_map_reverse(isl_union_map_copy(umap));2989		test = isl_union_map_apply_range(test, umap);2990 2991		data->sv = union_map_forall(test, &is_subset_of_identity);2992 2993		isl_union_map_free(test);2994	}2995 2996	if (data->sv < 0 || !data->sv)2997		return isl_stat_error;2998	return isl_stat_ok;2999}3000 3001/* Check if the given map is single-valued.3002 *3003 * If the union map consists of a single map, then test it as an isl_map.3004 * Otherwise, check if the union map is single-valued on each of its3005 * domain spaces.3006 */3007isl_bool isl_union_map_is_single_valued(__isl_keep isl_union_map *umap)3008{3009	isl_union_map *universe;3010	isl_union_set *domain;3011	struct isl_union_map_is_sv_data data;3012	isl_size n;3013 3014	n = isl_union_map_n_map(umap);3015	if (n < 0)3016		return isl_bool_error;3017	if (n == 1)3018		return single_map_is_single_valued(umap);3019 3020	universe = isl_union_map_universe(isl_union_map_copy(umap));3021	domain = isl_union_map_domain(universe);3022 3023	data.sv = isl_bool_true;3024	data.umap = umap;3025	if (isl_union_set_foreach_set(domain,3026			    &single_valued_on_domain, &data) < 0 && data.sv)3027		data.sv = isl_bool_error;3028	isl_union_set_free(domain);3029 3030	return data.sv;3031}3032 3033isl_bool isl_union_map_is_injective(__isl_keep isl_union_map *umap)3034{3035	isl_bool in;3036 3037	umap = isl_union_map_copy(umap);3038	umap = isl_union_map_reverse(umap);3039	in = isl_union_map_is_single_valued(umap);3040	isl_union_map_free(umap);3041 3042	return in;3043}3044 3045/* Is "map" obviously not an identity relation because3046 * it maps elements from one space to another space?3047 * Update *non_identity accordingly.3048 *3049 * In particular, if the domain and range spaces are the same,3050 * then the map is not considered to obviously not be an identity relation.3051 * Otherwise, the map is considered to obviously not be an identity relation3052 * if it is is non-empty.3053 *3054 * If "map" is determined to obviously not be an identity relation,3055 * then the search is aborted.3056 */3057static isl_stat map_plain_is_not_identity(__isl_take isl_map *map, void *user)3058{3059	isl_bool *non_identity = user;3060	isl_bool equal;3061 3062	equal = isl_map_tuple_is_equal(map, isl_dim_in, map, isl_dim_out);3063	if (equal >= 0 && !equal)3064		*non_identity = isl_bool_not(isl_map_is_empty(map));3065	else3066		*non_identity = isl_bool_not(equal);3067	isl_map_free(map);3068 3069	if (*non_identity < 0 || *non_identity)3070		return isl_stat_error;3071 3072	return isl_stat_ok;3073}3074 3075/* Is "umap" obviously not an identity relation because3076 * it maps elements from one space to another space?3077 *3078 * As soon as a map has been found that maps elements to a different space,3079 * non_identity is changed and the search is aborted.3080 */3081static isl_bool isl_union_map_plain_is_not_identity(3082	__isl_keep isl_union_map *umap)3083{3084	isl_bool non_identity;3085 3086	non_identity = isl_bool_false;3087	if (isl_union_map_foreach_map(umap, &map_plain_is_not_identity,3088					&non_identity) < 0 &&3089	    non_identity == isl_bool_false)3090		return isl_bool_error;3091 3092	return non_identity;3093}3094 3095/* Does "map" only map elements to themselves?3096 * Update *identity accordingly.3097 *3098 * If "map" is determined not to be an identity relation,3099 * then the search is aborted.3100 */3101static isl_stat map_is_identity(__isl_take isl_map *map, void *user)3102{3103	isl_bool *identity = user;3104 3105	*identity = isl_map_is_identity(map);3106	isl_map_free(map);3107 3108	if (*identity < 0 || !*identity)3109		return isl_stat_error;3110 3111	return isl_stat_ok;3112}3113 3114/* Does "umap" only map elements to themselves?3115 *3116 * First check if there are any maps that map elements to different spaces.3117 * If not, then check that all the maps (between identical spaces)3118 * are identity relations.3119 */3120isl_bool isl_union_map_is_identity(__isl_keep isl_union_map *umap)3121{3122	isl_bool non_identity;3123	isl_bool identity;3124 3125	non_identity = isl_union_map_plain_is_not_identity(umap);3126	if (non_identity < 0 || non_identity)3127		return isl_bool_not(non_identity);3128 3129	identity = isl_bool_true;3130	if (isl_union_map_foreach_map(umap, &map_is_identity, &identity) < 0 &&3131	    identity == isl_bool_true)3132		return isl_bool_error;3133 3134	return identity;3135}3136 3137/* Represents a map that has a fixed value (v) for one of its3138 * range dimensions.3139 * The map in this structure is not reference counted, so it3140 * is only valid while the isl_union_map from which it was3141 * obtained is still alive.3142 */3143struct isl_fixed_map {3144	isl_int v;3145	isl_map *map;3146};3147 3148static struct isl_fixed_map *alloc_isl_fixed_map_array(isl_ctx *ctx,3149	int n)3150{3151	int i;3152	struct isl_fixed_map *v;3153 3154	v = isl_calloc_array(ctx, struct isl_fixed_map, n);3155	if (!v)3156		return NULL;3157	for (i = 0; i < n; ++i)3158		isl_int_init(v[i].v);3159	return v;3160}3161 3162static void free_isl_fixed_map_array(struct isl_fixed_map *v, int n)3163{3164	int i;3165 3166	if (!v)3167		return;3168	for (i = 0; i < n; ++i)3169		isl_int_clear(v[i].v);3170	free(v);3171}3172 3173/* Compare the "v" field of two isl_fixed_map structs.3174 */3175static int qsort_fixed_map_cmp(const void *p1, const void *p2)3176{3177	const struct isl_fixed_map *e1 = (const struct isl_fixed_map *) p1;3178	const struct isl_fixed_map *e2 = (const struct isl_fixed_map *) p2;3179 3180	return isl_int_cmp(e1->v, e2->v);3181}3182 3183/* Internal data structure used while checking whether all maps3184 * in a union_map have a fixed value for a given output dimension.3185 * v is the list of maps, with the fixed value for the dimension3186 * n is the number of maps considered so far3187 * pos is the output dimension under investigation3188 */3189struct isl_fixed_dim_data {3190	struct isl_fixed_map *v;3191	int n;3192	int pos;3193};3194 3195static isl_bool fixed_at_pos(__isl_keep isl_map *map, void *user)3196{3197	struct isl_fixed_dim_data *data = user;3198 3199	data->v[data->n].map = map;3200	return isl_map_plain_is_fixed(map, isl_dim_out, data->pos,3201				      &data->v[data->n++].v);3202}3203 3204static isl_bool plain_injective_on_range(__isl_take isl_union_map *umap,3205	int first, int n_range);3206 3207/* Given a list of the maps, with their fixed values at output dimension "pos",3208 * check whether the ranges of the maps form an obvious partition.3209 *3210 * We first sort the maps according to their fixed values.3211 * If all maps have a different value, then we know the ranges form3212 * a partition.3213 * Otherwise, we collect the maps with the same fixed value and3214 * check whether each such collection is obviously injective3215 * based on later dimensions.3216 */3217static int separates(struct isl_fixed_map *v, int n,3218	__isl_take isl_space *space, int pos, int n_range)3219{3220	int i;3221 3222	if (!v)3223		goto error;3224 3225	qsort(v, n, sizeof(*v), &qsort_fixed_map_cmp);3226 3227	for (i = 0; i + 1 < n; ++i) {3228		int j, k;3229		isl_union_map *part;3230		int injective;3231 3232		for (j = i + 1; j < n; ++j)3233			if (isl_int_ne(v[i].v, v[j].v))3234				break;3235 3236		if (j == i + 1)3237			continue;3238 3239		part = isl_union_map_alloc(isl_space_copy(space), j - i);3240		for (k = i; k < j; ++k)3241			part = isl_union_map_add_map(part,3242						     isl_map_copy(v[k].map));3243 3244		injective = plain_injective_on_range(part, pos + 1, n_range);3245		if (injective < 0)3246			goto error;3247		if (!injective)3248			break;3249 3250		i = j - 1;3251	}3252 3253	isl_space_free(space);3254	free_isl_fixed_map_array(v, n);3255	return i + 1 >= n;3256error:3257	isl_space_free(space);3258	free_isl_fixed_map_array(v, n);3259	return -1;3260}3261 3262/* Check whether the maps in umap have obviously distinct ranges.3263 * In particular, check for an output dimension in the range3264 * [first,n_range) for which all maps have a fixed value3265 * and then check if these values, possibly along with fixed values3266 * at later dimensions, entail distinct ranges.3267 */3268static isl_bool plain_injective_on_range(__isl_take isl_union_map *umap,3269	int first, int n_range)3270{3271	isl_ctx *ctx;3272	isl_size n;3273	struct isl_fixed_dim_data data = { NULL };3274 3275	ctx = isl_union_map_get_ctx(umap);3276 3277	n = isl_union_map_n_map(umap);3278	if (n < 0)3279		goto error;3280 3281	if (n <= 1) {3282		isl_union_map_free(umap);3283		return isl_bool_true;3284	}3285 3286	if (first >= n_range) {3287		isl_union_map_free(umap);3288		return isl_bool_false;3289	}3290 3291	data.v = alloc_isl_fixed_map_array(ctx, n);3292	if (!data.v)3293		goto error;3294 3295	for (data.pos = first; data.pos < n_range; ++data.pos) {3296		isl_bool fixed;3297		int injective;3298		isl_space *space;3299 3300		data.n = 0;3301		fixed = union_map_forall_user(umap, &fixed_at_pos, &data);3302		if (fixed < 0)3303			goto error;3304		if (!fixed)3305			continue;3306		space = isl_union_map_get_space(umap);3307		injective = separates(data.v, n, space, data.pos, n_range);3308		isl_union_map_free(umap);3309		return injective;3310	}3311 3312	free_isl_fixed_map_array(data.v, n);3313	isl_union_map_free(umap);3314 3315	return isl_bool_false;3316error:3317	free_isl_fixed_map_array(data.v, n);3318	isl_union_map_free(umap);3319	return isl_bool_error;3320}3321 3322/* Check whether the maps in umap that map to subsets of "ran"3323 * have obviously distinct ranges.3324 */3325static isl_bool plain_injective_on_range_wrap(__isl_keep isl_set *ran,3326	void *user)3327{3328	isl_size dim;3329	isl_union_map *umap = user;3330 3331	dim = isl_set_dim(ran, isl_dim_set);3332	if (dim < 0)3333		return isl_bool_error;3334 3335	umap = isl_union_map_copy(umap);3336	umap = isl_union_map_intersect_range(umap,3337			isl_union_set_from_set(isl_set_copy(ran)));3338	return plain_injective_on_range(umap, 0, dim);3339}3340 3341/* Check if the given union_map is obviously injective.3342 *3343 * In particular, we first check if all individual maps are obviously3344 * injective and then check if all the ranges of these maps are3345 * obviously disjoint.3346 */3347isl_bool isl_union_map_plain_is_injective(__isl_keep isl_union_map *umap)3348{3349	isl_bool in;3350	isl_union_map *univ;3351	isl_union_set *ran;3352 3353	in = union_map_forall(umap, &isl_map_plain_is_injective);3354	if (in < 0)3355		return isl_bool_error;3356	if (!in)3357		return isl_bool_false;3358 3359	univ = isl_union_map_universe(isl_union_map_copy(umap));3360	ran = isl_union_map_range(univ);3361 3362	in = union_map_forall_user(ran, &plain_injective_on_range_wrap, umap);3363 3364	isl_union_set_free(ran);3365 3366	return in;3367}3368 3369isl_bool isl_union_map_is_bijective(__isl_keep isl_union_map *umap)3370{3371	isl_bool sv;3372 3373	sv = isl_union_map_is_single_valued(umap);3374	if (sv < 0 || !sv)3375		return sv;3376 3377	return isl_union_map_is_injective(umap);3378}3379 3380__isl_give isl_union_map *isl_union_map_zip(__isl_take isl_union_map *umap)3381{3382	struct isl_un_op_drop_user_data data = { &isl_map_can_zip };3383	struct isl_un_op_control control = {3384		.filter = &un_op_filter_drop_user,3385		.filter_user = &data,3386		.fn_map = &isl_map_zip,3387	};3388	return un_op(umap, &control);3389}3390 3391/* Given a union map, take the maps of the form A -> (B -> C) and3392 * return the union of the corresponding maps (A -> B) -> C.3393 */3394__isl_give isl_union_map *isl_union_map_uncurry(__isl_take isl_union_map *umap)3395{3396	struct isl_un_op_drop_user_data data = { &isl_map_can_uncurry };3397	struct isl_un_op_control control = {3398		.filter = &un_op_filter_drop_user,3399		.filter_user = &data,3400		.fn_map = &isl_map_uncurry,3401	};3402	return un_op(umap, &control);3403}3404 3405/* Given a union map, take the maps of the form (A -> B) -> C and3406 * return the union of the corresponding maps A -> (B -> C).3407 */3408__isl_give isl_union_map *isl_union_map_curry(__isl_take isl_union_map *umap)3409{3410	struct isl_un_op_drop_user_data data = { &isl_map_can_curry };3411	struct isl_un_op_control control = {3412		.filter = &un_op_filter_drop_user,3413		.filter_user = &data,3414		.fn_map = &isl_map_curry,3415	};3416	return un_op(umap, &control);3417}3418 3419/* Given a union map, take the maps of the form A -> ((B -> C) -> D) and3420 * return the union of the corresponding maps A -> (B -> (C -> D)).3421 */3422__isl_give isl_union_map *isl_union_map_range_curry(3423	__isl_take isl_union_map *umap)3424{3425	struct isl_un_op_drop_user_data data = { &isl_map_can_range_curry };3426	struct isl_un_op_control control = {3427		.filter = &un_op_filter_drop_user,3428		.filter_user = &data,3429		.fn_map = &isl_map_range_curry,3430	};3431	return un_op(umap, &control);3432}3433 3434__isl_give isl_union_set *isl_union_set_lift(__isl_take isl_union_set *uset)3435{3436	struct isl_un_op_control control = {3437		.fn_map = &isl_set_lift,3438	};3439	return un_op(uset, &control);3440}3441 3442static isl_stat coefficients_entry(void **entry, void *user)3443{3444	isl_set *set = *entry;3445	isl_union_set **res = user;3446 3447	set = isl_set_copy(set);3448	set = isl_set_from_basic_set(isl_set_coefficients(set));3449	*res = isl_union_set_add_set(*res, set);3450 3451	return isl_stat_ok;3452}3453 3454__isl_give isl_union_set *isl_union_set_coefficients(3455	__isl_take isl_union_set *uset)3456{3457	isl_ctx *ctx;3458	isl_space *space;3459	isl_union_set *res;3460 3461	if (!uset)3462		return NULL;3463 3464	ctx = isl_union_set_get_ctx(uset);3465	space = isl_space_set_alloc(ctx, 0, 0);3466	res = isl_union_map_alloc(space, uset->table.n);3467	if (isl_hash_table_foreach(uset->dim->ctx, &uset->table,3468				   &coefficients_entry, &res) < 0)3469		goto error;3470 3471	isl_union_set_free(uset);3472	return res;3473error:3474	isl_union_set_free(uset);3475	isl_union_set_free(res);3476	return NULL;3477}3478 3479static isl_stat solutions_entry(void **entry, void *user)3480{3481	isl_set *set = *entry;3482	isl_union_set **res = user;3483 3484	set = isl_set_copy(set);3485	set = isl_set_from_basic_set(isl_set_solutions(set));3486	if (!*res)3487		*res = isl_union_set_from_set(set);3488	else3489		*res = isl_union_set_add_set(*res, set);3490 3491	if (!*res)3492		return isl_stat_error;3493 3494	return isl_stat_ok;3495}3496 3497__isl_give isl_union_set *isl_union_set_solutions(3498	__isl_take isl_union_set *uset)3499{3500	isl_union_set *res = NULL;3501 3502	if (!uset)3503		return NULL;3504 3505	if (uset->table.n == 0) {3506		res = isl_union_set_empty(isl_union_set_get_space(uset));3507		isl_union_set_free(uset);3508		return res;3509	}3510 3511	if (isl_hash_table_foreach(uset->dim->ctx, &uset->table,3512				   &solutions_entry, &res) < 0)3513		goto error;3514 3515	isl_union_set_free(uset);3516	return res;3517error:3518	isl_union_set_free(uset);3519	isl_union_set_free(res);3520	return NULL;3521}3522 3523/* Is the domain space of "map" equal to "space"?3524 */3525static int domain_match(__isl_keep isl_map *map, __isl_keep isl_space *space)3526{3527	return isl_map_space_tuple_is_equal(map, isl_dim_in,3528					space, isl_dim_out);3529}3530 3531/* Is the range space of "map" equal to "space"?3532 */3533static int range_match(__isl_keep isl_map *map, __isl_keep isl_space *space)3534{3535	return isl_map_space_tuple_is_equal(map, isl_dim_out,3536					space, isl_dim_out);3537}3538 3539/* Is the set space of "map" equal to "space"?3540 */3541static int set_match(__isl_keep isl_map *map, __isl_keep isl_space *space)3542{3543	return isl_map_space_tuple_is_equal(map, isl_dim_set,3544					space, isl_dim_out);3545}3546 3547/* Internal data structure for preimage_pw_multi_aff.3548 *3549 * "pma" is the function under which the preimage should be taken.3550 * "space" is the space of "pma".3551 * "res" collects the results.3552 * "fn" computes the preimage for a given map.3553 * "match" returns true if "fn" can be called.3554 */3555struct isl_union_map_preimage_data {3556	isl_space *space;3557	isl_pw_multi_aff *pma;3558	isl_union_map *res;3559	int (*match)(__isl_keep isl_map *map, __isl_keep isl_space *space);3560	__isl_give isl_map *(*fn)(__isl_take isl_map *map,3561		__isl_take isl_pw_multi_aff *pma);3562};3563 3564/* Call data->fn to compute the preimage of the domain or range of *entry3565 * under the function represented by data->pma, provided the domain/range3566 * space of *entry matches the target space of data->pma3567 * (as given by data->match), and add the result to data->res.3568 */3569static isl_stat preimage_entry(void **entry, void *user)3570{3571	int m;3572	isl_map *map = *entry;3573	struct isl_union_map_preimage_data *data = user;3574	isl_bool empty;3575 3576	m = data->match(map, data->space);3577	if (m < 0)3578		return isl_stat_error;3579	if (!m)3580		return isl_stat_ok;3581 3582	map = isl_map_copy(map);3583	map = data->fn(map, isl_pw_multi_aff_copy(data->pma));3584 3585	empty = isl_map_is_empty(map);3586	if (empty < 0 || empty) {3587		isl_map_free(map);3588		return empty < 0 ? isl_stat_error : isl_stat_ok;3589	}3590 3591	data->res = isl_union_map_add_map(data->res, map);3592 3593	return isl_stat_ok;3594}3595 3596/* Compute the preimage of the domain or range of "umap" under the function3597 * represented by "pma".3598 * In other words, plug in "pma" in the domain or range of "umap".3599 * The function "fn" performs the actual preimage computation on a map,3600 * while "match" determines to which maps the function should be applied.3601 */3602static __isl_give isl_union_map *preimage_pw_multi_aff(3603	__isl_take isl_union_map *umap, __isl_take isl_pw_multi_aff *pma,3604	int (*match)(__isl_keep isl_map *map, __isl_keep isl_space *space),3605	__isl_give isl_map *(*fn)(__isl_take isl_map *map,3606		__isl_take isl_pw_multi_aff *pma))3607{3608	isl_ctx *ctx;3609	isl_space *space;3610	struct isl_union_map_preimage_data data;3611 3612	umap = isl_union_map_align_params(umap,3613					    isl_pw_multi_aff_get_space(pma));3614	pma = isl_pw_multi_aff_align_params(pma, isl_union_map_get_space(umap));3615 3616	if (!umap || !pma)3617		goto error;3618 3619	ctx = isl_union_map_get_ctx(umap);3620	space = isl_union_map_get_space(umap);3621	data.space = isl_pw_multi_aff_get_space(pma);3622	data.pma = pma;3623	data.res = isl_union_map_alloc(space, umap->table.n);3624	data.match = match;3625	data.fn = fn;3626	if (isl_hash_table_foreach(ctx, &umap->table, &preimage_entry,3627					&data) < 0)3628		data.res = isl_union_map_free(data.res);3629 3630	isl_space_free(data.space);3631	isl_union_map_free(umap);3632	isl_pw_multi_aff_free(pma);3633	return data.res;3634error:3635	isl_union_map_free(umap);3636	isl_pw_multi_aff_free(pma);3637	return NULL;3638}3639 3640/* Compute the preimage of the domain of "umap" under the function3641 * represented by "pma".3642 * In other words, plug in "pma" in the domain of "umap".3643 * The result contains maps that live in the same spaces as the maps of "umap"3644 * with domain space equal to the target space of "pma",3645 * except that the domain has been replaced by the domain space of "pma".3646 */3647__isl_give isl_union_map *isl_union_map_preimage_domain_pw_multi_aff(3648	__isl_take isl_union_map *umap, __isl_take isl_pw_multi_aff *pma)3649{3650	return preimage_pw_multi_aff(umap, pma, &domain_match,3651					&isl_map_preimage_domain_pw_multi_aff);3652}3653 3654/* Compute the preimage of the range of "umap" under the function3655 * represented by "pma".3656 * In other words, plug in "pma" in the range of "umap".3657 * The result contains maps that live in the same spaces as the maps of "umap"3658 * with range space equal to the target space of "pma",3659 * except that the range has been replaced by the domain space of "pma".3660 */3661__isl_give isl_union_map *isl_union_map_preimage_range_pw_multi_aff(3662	__isl_take isl_union_map *umap, __isl_take isl_pw_multi_aff *pma)3663{3664	return preimage_pw_multi_aff(umap, pma, &range_match,3665					&isl_map_preimage_range_pw_multi_aff);3666}3667 3668/* Compute the preimage of "uset" under the function represented by "pma".3669 * In other words, plug in "pma" in "uset".3670 * The result contains sets that live in the same spaces as the sets of "uset"3671 * with space equal to the target space of "pma",3672 * except that the space has been replaced by the domain space of "pma".3673 */3674__isl_give isl_union_set *isl_union_set_preimage_pw_multi_aff(3675	__isl_take isl_union_set *uset, __isl_take isl_pw_multi_aff *pma)3676{3677	return preimage_pw_multi_aff(uset, pma, &set_match,3678					&isl_set_preimage_pw_multi_aff);3679}3680 3681/* Compute the preimage of the domain of "umap" under the function3682 * represented by "ma".3683 * In other words, plug in "ma" in the domain of "umap".3684 * The result contains maps that live in the same spaces as the maps of "umap"3685 * with domain space equal to the target space of "ma",3686 * except that the domain has been replaced by the domain space of "ma".3687 */3688__isl_give isl_union_map *isl_union_map_preimage_domain_multi_aff(3689	__isl_take isl_union_map *umap, __isl_take isl_multi_aff *ma)3690{3691	return isl_union_map_preimage_domain_pw_multi_aff(umap,3692					isl_pw_multi_aff_from_multi_aff(ma));3693}3694 3695/* Compute the preimage of the range of "umap" under the function3696 * represented by "ma".3697 * In other words, plug in "ma" in the range of "umap".3698 * The result contains maps that live in the same spaces as the maps of "umap"3699 * with range space equal to the target space of "ma",3700 * except that the range has been replaced by the domain space of "ma".3701 */3702__isl_give isl_union_map *isl_union_map_preimage_range_multi_aff(3703	__isl_take isl_union_map *umap, __isl_take isl_multi_aff *ma)3704{3705	return isl_union_map_preimage_range_pw_multi_aff(umap,3706					isl_pw_multi_aff_from_multi_aff(ma));3707}3708 3709/* Compute the preimage of "uset" under the function represented by "ma".3710 * In other words, plug in "ma" in "uset".3711 * The result contains sets that live in the same spaces as the sets of "uset"3712 * with space equal to the target space of "ma",3713 * except that the space has been replaced by the domain space of "ma".3714 */3715__isl_give isl_union_map *isl_union_set_preimage_multi_aff(3716	__isl_take isl_union_set *uset, __isl_take isl_multi_aff *ma)3717{3718	return isl_union_set_preimage_pw_multi_aff(uset,3719					isl_pw_multi_aff_from_multi_aff(ma));3720}3721 3722/* Internal data structure for preimage_multi_pw_aff.3723 *3724 * "mpa" is the function under which the preimage should be taken.3725 * "space" is the space of "mpa".3726 * "res" collects the results.3727 * "fn" computes the preimage for a given map.3728 * "match" returns true if "fn" can be called.3729 */3730struct isl_union_map_preimage_mpa_data {3731	isl_space *space;3732	isl_multi_pw_aff *mpa;3733	isl_union_map *res;3734	int (*match)(__isl_keep isl_map *map, __isl_keep isl_space *space);3735	__isl_give isl_map *(*fn)(__isl_take isl_map *map,3736		__isl_take isl_multi_pw_aff *mpa);3737};3738 3739/* Call data->fn to compute the preimage of the domain or range of *entry3740 * under the function represented by data->mpa, provided the domain/range3741 * space of *entry matches the target space of data->mpa3742 * (as given by data->match), and add the result to data->res.3743 */3744static isl_stat preimage_mpa_entry(void **entry, void *user)3745{3746	int m;3747	isl_map *map = *entry;3748	struct isl_union_map_preimage_mpa_data *data = user;3749	isl_bool empty;3750 3751	m = data->match(map, data->space);3752	if (m < 0)3753		return isl_stat_error;3754	if (!m)3755		return isl_stat_ok;3756 3757	map = isl_map_copy(map);3758	map = data->fn(map, isl_multi_pw_aff_copy(data->mpa));3759 3760	empty = isl_map_is_empty(map);3761	if (empty < 0 || empty) {3762		isl_map_free(map);3763		return empty < 0 ? isl_stat_error : isl_stat_ok;3764	}3765 3766	data->res = isl_union_map_add_map(data->res, map);3767 3768	return isl_stat_ok;3769}3770 3771/* Compute the preimage of the domain or range of "umap" under the function3772 * represented by "mpa".3773 * In other words, plug in "mpa" in the domain or range of "umap".3774 * The function "fn" performs the actual preimage computation on a map,3775 * while "match" determines to which maps the function should be applied.3776 */3777static __isl_give isl_union_map *preimage_multi_pw_aff(3778	__isl_take isl_union_map *umap, __isl_take isl_multi_pw_aff *mpa,3779	int (*match)(__isl_keep isl_map *map, __isl_keep isl_space *space),3780	__isl_give isl_map *(*fn)(__isl_take isl_map *map,3781		__isl_take isl_multi_pw_aff *mpa))3782{3783	isl_ctx *ctx;3784	isl_space *space;3785	struct isl_union_map_preimage_mpa_data data;3786 3787	umap = isl_union_map_align_params(umap,3788					    isl_multi_pw_aff_get_space(mpa));3789	mpa = isl_multi_pw_aff_align_params(mpa, isl_union_map_get_space(umap));3790 3791	if (!umap || !mpa)3792		goto error;3793 3794	ctx = isl_union_map_get_ctx(umap);3795	space = isl_union_map_get_space(umap);3796	data.space = isl_multi_pw_aff_get_space(mpa);3797	data.mpa = mpa;3798	data.res = isl_union_map_alloc(space, umap->table.n);3799	data.match = match;3800	data.fn = fn;3801	if (isl_hash_table_foreach(ctx, &umap->table, &preimage_mpa_entry,3802					&data) < 0)3803		data.res = isl_union_map_free(data.res);3804 3805	isl_space_free(data.space);3806	isl_union_map_free(umap);3807	isl_multi_pw_aff_free(mpa);3808	return data.res;3809error:3810	isl_union_map_free(umap);3811	isl_multi_pw_aff_free(mpa);3812	return NULL;3813}3814 3815/* Compute the preimage of the domain of "umap" under the function3816 * represented by "mpa".3817 * In other words, plug in "mpa" in the domain of "umap".3818 * The result contains maps that live in the same spaces as the maps of "umap"3819 * with domain space equal to the target space of "mpa",3820 * except that the domain has been replaced by the domain space of "mpa".3821 */3822__isl_give isl_union_map *isl_union_map_preimage_domain_multi_pw_aff(3823	__isl_take isl_union_map *umap, __isl_take isl_multi_pw_aff *mpa)3824{3825	return preimage_multi_pw_aff(umap, mpa, &domain_match,3826					&isl_map_preimage_domain_multi_pw_aff);3827}3828 3829/* Internal data structure for preimage_upma.3830 *3831 * "umap" is the map of which the preimage should be computed.3832 * "res" collects the results.3833 * "fn" computes the preimage for a given piecewise multi-affine function.3834 */3835struct isl_union_map_preimage_upma_data {3836	isl_union_map *umap;3837	isl_union_map *res;3838	__isl_give isl_union_map *(*fn)(__isl_take isl_union_map *umap,3839		__isl_take isl_pw_multi_aff *pma);3840};3841 3842/* Call data->fn to compute the preimage of the domain or range of data->umap3843 * under the function represented by pma and add the result to data->res.3844 */3845static isl_stat preimage_upma(__isl_take isl_pw_multi_aff *pma, void *user)3846{3847	struct isl_union_map_preimage_upma_data *data = user;3848	isl_union_map *umap;3849 3850	umap = isl_union_map_copy(data->umap);3851	umap = data->fn(umap, pma);3852	data->res = isl_union_map_union(data->res, umap);3853 3854	return data->res ? isl_stat_ok : isl_stat_error;3855}3856 3857/* Compute the preimage of the domain or range of "umap" under the function3858 * represented by "upma".3859 * In other words, plug in "upma" in the domain or range of "umap".3860 * The function "fn" performs the actual preimage computation3861 * on a piecewise multi-affine function.3862 */3863static __isl_give isl_union_map *preimage_union_pw_multi_aff(3864	__isl_take isl_union_map *umap,3865	__isl_take isl_union_pw_multi_aff *upma,3866	__isl_give isl_union_map *(*fn)(__isl_take isl_union_map *umap,3867		__isl_take isl_pw_multi_aff *pma))3868{3869	struct isl_union_map_preimage_upma_data data;3870 3871	data.umap = umap;3872	data.res = isl_union_map_empty(isl_union_map_get_space(umap));3873	data.fn = fn;3874	if (isl_union_pw_multi_aff_foreach_pw_multi_aff(upma,3875						    &preimage_upma, &data) < 0)3876		data.res = isl_union_map_free(data.res);3877 3878	isl_union_map_free(umap);3879	isl_union_pw_multi_aff_free(upma);3880 3881	return data.res;3882}3883 3884/* Compute the preimage of the domain of "umap" under the function3885 * represented by "upma".3886 * In other words, plug in "upma" in the domain of "umap".3887 * The result contains maps that live in the same spaces as the maps of "umap"3888 * with domain space equal to one of the target spaces of "upma",3889 * except that the domain has been replaced by one of the domain spaces that3890 * correspond to that target space of "upma".3891 */3892__isl_give isl_union_map *isl_union_map_preimage_domain_union_pw_multi_aff(3893	__isl_take isl_union_map *umap,3894	__isl_take isl_union_pw_multi_aff *upma)3895{3896	return preimage_union_pw_multi_aff(umap, upma,3897				&isl_union_map_preimage_domain_pw_multi_aff);3898}3899 3900/* Compute the preimage of the range of "umap" under the function3901 * represented by "upma".3902 * In other words, plug in "upma" in the range of "umap".3903 * The result contains maps that live in the same spaces as the maps of "umap"3904 * with range space equal to one of the target spaces of "upma",3905 * except that the range has been replaced by one of the domain spaces that3906 * correspond to that target space of "upma".3907 */3908__isl_give isl_union_map *isl_union_map_preimage_range_union_pw_multi_aff(3909	__isl_take isl_union_map *umap,3910	__isl_take isl_union_pw_multi_aff *upma)3911{3912	return preimage_union_pw_multi_aff(umap, upma,3913				&isl_union_map_preimage_range_pw_multi_aff);3914}3915 3916/* Compute the preimage of "uset" under the function represented by "upma".3917 * In other words, plug in "upma" in the range of "uset".3918 * The result contains sets that live in the same spaces as the sets of "uset"3919 * with space equal to one of the target spaces of "upma",3920 * except that the space has been replaced by one of the domain spaces that3921 * correspond to that target space of "upma".3922 */3923__isl_give isl_union_set *isl_union_set_preimage_union_pw_multi_aff(3924	__isl_take isl_union_set *uset,3925	__isl_take isl_union_pw_multi_aff *upma)3926{3927	return preimage_union_pw_multi_aff(uset, upma,3928					&isl_union_set_preimage_pw_multi_aff);3929}3930 3931/* Reset the user pointer on all identifiers of parameters and tuples3932 * of the spaces of "umap".3933 */3934__isl_give isl_union_map *isl_union_map_reset_user(3935	__isl_take isl_union_map *umap)3936{3937	umap = isl_union_map_cow(umap);3938	if (!umap)3939		return NULL;3940	umap->dim = isl_space_reset_user(umap->dim);3941	if (!umap->dim)3942		return isl_union_map_free(umap);3943	return total(umap, &isl_map_reset_user);3944}3945 3946/* Reset the user pointer on all identifiers of parameters and tuples3947 * of the spaces of "uset".3948 */3949__isl_give isl_union_set *isl_union_set_reset_user(3950	__isl_take isl_union_set *uset)3951{3952	return isl_union_map_reset_user(uset);3953}3954 3955/* Remove all existentially quantified variables and integer divisions3956 * from "umap" using Fourier-Motzkin elimination.3957 */3958__isl_give isl_union_map *isl_union_map_remove_divs(3959	__isl_take isl_union_map *umap)3960{3961	return total(umap, &isl_map_remove_divs);3962}3963 3964/* Remove all existentially quantified variables and integer divisions3965 * from "uset" using Fourier-Motzkin elimination.3966 */3967__isl_give isl_union_set *isl_union_set_remove_divs(3968	__isl_take isl_union_set *uset)3969{3970	return isl_union_map_remove_divs(uset);3971}3972 3973/* Internal data structure for isl_union_map_project_out.3974 * "type", "first" and "n" are the arguments for the isl_map_project_out3975 * call.3976 * "res" collects the results.3977 */3978struct isl_union_map_project_out_data {3979	enum isl_dim_type type;3980	unsigned first;3981	unsigned n;3982 3983	isl_union_map *res;3984};3985 3986/* Turn the data->n dimensions of type data->type, starting at data->first3987 * into existentially quantified variables and add the result to data->res.3988 */3989static isl_stat project_out(__isl_take isl_map *map, void *user)3990{3991	struct isl_union_map_project_out_data *data = user;3992 3993	map = isl_map_project_out(map, data->type, data->first, data->n);3994	data->res = isl_union_map_add_map(data->res, map);3995 3996	return isl_stat_ok;3997}3998 3999/* Turn the "n" dimensions of type "type", starting at "first"4000 * into existentially quantified variables.4001 * Since the space of an isl_union_map only contains parameters,4002 * type is required to be equal to isl_dim_param.4003 */4004__isl_give isl_union_map *isl_union_map_project_out(4005	__isl_take isl_union_map *umap,4006	enum isl_dim_type type, unsigned first, unsigned n)4007{4008	isl_space *space;4009	struct isl_union_map_project_out_data data = { type, first, n };4010 4011	if (!umap)4012		return NULL;4013 4014	if (type != isl_dim_param)4015		isl_die(isl_union_map_get_ctx(umap), isl_error_invalid,4016			"can only project out parameters",4017			return isl_union_map_free(umap));4018 4019	space = isl_union_map_get_space(umap);4020	space = isl_space_drop_dims(space, type, first, n);4021	data.res = isl_union_map_empty(space);4022	if (isl_union_map_foreach_map(umap, &project_out, &data) < 0)4023		data.res = isl_union_map_free(data.res);4024 4025	isl_union_map_free(umap);4026 4027	return data.res;4028}4029 4030#undef TYPE4031#define TYPE	isl_union_map4032#include "isl_project_out_all_params_templ.c"4033#include "isl_project_out_param_templ.c"4034 4035/* Turn the "n" dimensions of type "type", starting at "first"4036 * into existentially quantified variables.4037 * Since the space of an isl_union_set only contains parameters,4038 * "type" is required to be equal to isl_dim_param.4039 */4040__isl_give isl_union_set *isl_union_set_project_out(4041	__isl_take isl_union_set *uset,4042	enum isl_dim_type type, unsigned first, unsigned n)4043{4044	return isl_union_map_project_out(uset, type, first, n);4045}4046 4047/* Project out all parameters from "uset" by existentially quantifying4048 * over them.4049 */4050__isl_give isl_union_set *isl_union_set_project_out_all_params(4051	__isl_take isl_union_set *uset)4052{4053	return uset_from_umap(4054		    isl_union_map_project_out_all_params(uset_to_umap(uset)));4055}4056 4057/* Internal data structure for isl_union_map_involves_dims.4058 * "first" and "n" are the arguments for the isl_map_involves_dims calls.4059 */4060struct isl_union_map_involves_dims_data {4061	unsigned first;4062	unsigned n;4063};4064 4065/* Does "map" _not_ involve the data->n parameters starting at data->first?4066 */4067static isl_bool map_excludes(__isl_keep isl_map *map, void *user)4068{4069	struct isl_union_map_involves_dims_data *data = user;4070	isl_bool involves;4071 4072	involves = isl_map_involves_dims(map,4073					isl_dim_param, data->first, data->n);4074	return isl_bool_not(involves);4075}4076 4077/* Does "umap" involve any of the n parameters starting at first?4078 * "type" is required to be set to isl_dim_param.4079 *4080 * "umap" involves any of those parameters if any of its maps4081 * involve the parameters.  In other words, "umap" does not4082 * involve any of the parameters if all its maps to not4083 * involve the parameters.4084 */4085isl_bool isl_union_map_involves_dims(__isl_keep isl_union_map *umap,4086	enum isl_dim_type type, unsigned first, unsigned n)4087{4088	struct isl_union_map_involves_dims_data data = { first, n };4089	isl_bool excludes;4090 4091	if (type != isl_dim_param)4092		isl_die(isl_union_map_get_ctx(umap), isl_error_invalid,4093			"can only reference parameters", return isl_bool_error);4094 4095	excludes = union_map_forall_user(umap, &map_excludes, &data);4096 4097	return isl_bool_not(excludes);4098}4099 4100/* Internal data structure for isl_union_map_reset_range_space.4101 * "range" is the space from which to set the range space.4102 * "res" collects the results.4103 */4104struct isl_union_map_reset_range_space_data {4105	isl_space *range;4106	isl_union_map *res;4107};4108 4109/* Replace the range space of "map" by the range space of data->range and4110 * add the result to data->res.4111 */4112static isl_stat reset_range_space(__isl_take isl_map *map, void *user)4113{4114	struct isl_union_map_reset_range_space_data *data = user;4115	isl_space *space;4116 4117	space = isl_map_get_space(map);4118	space = isl_space_domain(space);4119	space = isl_space_extend_domain_with_range(space,4120						isl_space_copy(data->range));4121	map = isl_map_reset_space(map, space);4122	data->res = isl_union_map_add_map(data->res, map);4123 4124	return data->res ? isl_stat_ok : isl_stat_error;4125}4126 4127/* Replace the range space of all the maps in "umap" by4128 * the range space of "space".4129 *4130 * This assumes that all maps have the same output dimension.4131 * This function should therefore not be made publicly available.4132 *4133 * Since the spaces of the maps change, so do their hash value.4134 * We therefore need to create a new isl_union_map.4135 */4136__isl_give isl_union_map *isl_union_map_reset_range_space(4137	__isl_take isl_union_map *umap, __isl_take isl_space *space)4138{4139	struct isl_union_map_reset_range_space_data data = { space };4140 4141	data.res = isl_union_map_empty(isl_union_map_get_space(umap));4142	if (isl_union_map_foreach_map(umap, &reset_range_space, &data) < 0)4143		data.res = isl_union_map_free(data.res);4144 4145	isl_space_free(space);4146	isl_union_map_free(umap);4147	return data.res;4148}4149 4150/* Check that "umap" and "space" have the same number of parameters.4151 */4152static isl_stat check_union_map_space_equal_dim(__isl_keep isl_union_map *umap,4153	__isl_keep isl_space *space)4154{4155	isl_size dim1, dim2;4156 4157	dim1 = isl_union_map_dim(umap, isl_dim_param);4158	dim2 = isl_space_dim(space, isl_dim_param);4159	if (dim1 < 0 || dim2 < 0)4160		return isl_stat_error;4161	if (dim1 == dim2)4162		return isl_stat_ok;4163	isl_die(isl_union_map_get_ctx(umap), isl_error_invalid,4164		"number of parameters does not match", return isl_stat_error);4165}4166 4167/* Internal data structure for isl_union_map_reset_equal_dim_space.4168 * "space" is the target space.4169 * "res" collects the results.4170 */4171struct isl_union_map_reset_params_data {4172	isl_space *space;4173	isl_union_map *res;4174};4175 4176/* Replace the parameters of "map" by those of data->space and4177 * add the result to data->res.4178 */4179static isl_stat reset_params(__isl_take isl_map *map, void *user)4180{4181	struct isl_union_map_reset_params_data *data = user;4182	isl_space *space;4183 4184	space = isl_map_get_space(map);4185	space = isl_space_replace_params(space, data->space);4186	map = isl_map_reset_equal_dim_space(map, space);4187	data->res = isl_union_map_add_map(data->res, map);4188 4189	return data->res ? isl_stat_ok : isl_stat_error;4190}4191 4192/* Replace the space of "umap" by "space", without modifying4193 * the dimension of "umap", i.e., the number of parameters of "umap".4194 *4195 * Since the hash values of the maps in the union map depend4196 * on the parameters, a new union map needs to be constructed.4197 */4198__isl_give isl_union_map *isl_union_map_reset_equal_dim_space(4199	__isl_take isl_union_map *umap, __isl_take isl_space *space)4200{4201	struct isl_union_map_reset_params_data data = { space };4202	isl_bool equal;4203	isl_space *umap_space;4204 4205	umap_space = isl_union_map_peek_space(umap);4206	equal = isl_space_is_equal(umap_space, space);4207	if (equal < 0)4208		goto error;4209	if (equal) {4210		isl_space_free(space);4211		return umap;4212	}4213	if (check_union_map_space_equal_dim(umap, space) < 0)4214		goto error;4215 4216	data.res = isl_union_map_empty(isl_space_copy(space));4217	if (isl_union_map_foreach_map(umap, &reset_params, &data) < 0)4218		data.res = isl_union_map_free(data.res);4219 4220	isl_space_free(space);4221	isl_union_map_free(umap);4222	return data.res;4223error:4224	isl_union_map_free(umap);4225	isl_space_free(space);4226	return NULL;4227}4228 4229/* Internal data structure for isl_union_map_order_at_multi_union_pw_aff.4230 * "mupa" is the function from which the isl_multi_pw_affs are extracted.4231 * "order" is applied to the extracted isl_multi_pw_affs that correspond4232 * to the domain and the range of each map.4233 * "res" collects the results.4234 */4235struct isl_union_order_at_data {4236	isl_multi_union_pw_aff *mupa;4237	__isl_give isl_map *(*order)(__isl_take isl_multi_pw_aff *mpa1,4238		__isl_take isl_multi_pw_aff *mpa2);4239	isl_union_map *res;4240};4241 4242/* Intersect "map" with the result of applying data->order to4243 * the functions in data->mupa that apply to the domain and the range4244 * of "map" and add the result to data->res.4245 */4246static isl_stat order_at(__isl_take isl_map *map, void *user)4247{4248	struct isl_union_order_at_data *data = user;4249	isl_space *space;4250	isl_multi_pw_aff *mpa1, *mpa2;4251	isl_map *order;4252 4253	space = isl_space_domain(isl_map_get_space(map));4254	mpa1 = isl_multi_union_pw_aff_extract_multi_pw_aff(data->mupa, space);4255	space = isl_space_range(isl_map_get_space(map));4256	mpa2 = isl_multi_union_pw_aff_extract_multi_pw_aff(data->mupa, space);4257	order = data->order(mpa1, mpa2);4258	map = isl_map_intersect(map, order);4259	data->res = isl_union_map_add_map(data->res, map);4260 4261	return data->res ? isl_stat_ok : isl_stat_error;4262}4263 4264/* If "mupa" has a non-trivial explicit domain, then intersect4265 * domain and range of "umap" with this explicit domain.4266 * If the explicit domain only describes constraints on the parameters,4267 * then the intersection only needs to be performed once.4268 */4269static __isl_give isl_union_map *intersect_explicit_domain(4270	__isl_take isl_union_map *umap, __isl_keep isl_multi_union_pw_aff *mupa)4271{4272	isl_bool non_trivial, is_params;4273	isl_union_set *dom;4274 4275	non_trivial = isl_multi_union_pw_aff_has_non_trivial_domain(mupa);4276	if (non_trivial < 0)4277		return isl_union_map_free(umap);4278	if (!non_trivial)4279		return umap;4280	mupa = isl_multi_union_pw_aff_copy(mupa);4281	dom = isl_multi_union_pw_aff_domain(mupa);4282	is_params = isl_union_set_is_params(dom);4283	if (is_params < 0) {4284		isl_union_set_free(dom);4285		return isl_union_map_free(umap);4286	}4287	if (is_params) {4288		isl_set *set;4289 4290		set = isl_union_set_params(dom);4291		umap = isl_union_map_intersect_params(umap, set);4292		return umap;4293	}4294	umap = isl_union_map_intersect_domain(umap, isl_union_set_copy(dom));4295	umap = isl_union_map_intersect_range(umap, dom);4296	return umap;4297}4298 4299/* Intersect each map in "umap" with the result of calling "order"4300 * on the functions is "mupa" that apply to the domain and the range4301 * of the map.4302 */4303static __isl_give isl_union_map *isl_union_map_order_at_multi_union_pw_aff(4304	__isl_take isl_union_map *umap, __isl_take isl_multi_union_pw_aff *mupa,4305	__isl_give isl_map *(*order)(__isl_take isl_multi_pw_aff *mpa1,4306		__isl_take isl_multi_pw_aff *mpa2))4307{4308	struct isl_union_order_at_data data;4309 4310	umap = isl_union_map_align_params(umap,4311				isl_multi_union_pw_aff_get_space(mupa));4312	mupa = isl_multi_union_pw_aff_align_params(mupa,4313				isl_union_map_get_space(umap));4314	umap = intersect_explicit_domain(umap, mupa);4315	data.mupa = mupa;4316	data.order = order;4317	data.res = isl_union_map_empty(isl_union_map_get_space(umap));4318	if (isl_union_map_foreach_map(umap, &order_at, &data) < 0)4319		data.res = isl_union_map_free(data.res);4320 4321	isl_multi_union_pw_aff_free(mupa);4322	isl_union_map_free(umap);4323	return data.res;4324}4325 4326/* Return the subset of "umap" where the domain and the range4327 * have equal "mupa" values.4328 */4329__isl_give isl_union_map *isl_union_map_eq_at_multi_union_pw_aff(4330	__isl_take isl_union_map *umap,4331	__isl_take isl_multi_union_pw_aff *mupa)4332{4333	return isl_union_map_order_at_multi_union_pw_aff(umap, mupa,4334						&isl_multi_pw_aff_eq_map);4335}4336 4337#undef ORDER4338#define ORDER		le4339#include "isl_union_map_lex_templ.c"4340 4341#undef ORDER4342#define ORDER		lt4343#include "isl_union_map_lex_templ.c"4344 4345#undef ORDER4346#define ORDER		ge4347#include "isl_union_map_lex_templ.c"4348 4349#undef ORDER4350#define ORDER		gt4351#include "isl_union_map_lex_templ.c"4352 4353/* Return the union of the elements in the list "list".4354 */4355__isl_give isl_union_set *isl_union_set_list_union(4356	__isl_take isl_union_set_list *list)4357{4358	int i;4359	isl_size n;4360	isl_ctx *ctx;4361	isl_space *space;4362	isl_union_set *res;4363 4364	n = isl_union_set_list_n_union_set(list);4365	if (n < 0)4366		goto error;4367 4368	ctx = isl_union_set_list_get_ctx(list);4369	space = isl_space_params_alloc(ctx, 0);4370	res = isl_union_set_empty(space);4371 4372	for (i = 0; i < n; ++i) {4373		isl_union_set *uset_i;4374 4375		uset_i = isl_union_set_list_get_union_set(list, i);4376		res = isl_union_set_union(res, uset_i);4377	}4378 4379	isl_union_set_list_free(list);4380	return res;4381error:4382	isl_union_set_list_free(list);4383	return NULL;4384}4385 4386/* Update *hash with the hash value of "map".4387 */4388static isl_stat add_hash(__isl_take isl_map *map, void *user)4389{4390	uint32_t *hash = user;4391	uint32_t map_hash;4392 4393	map_hash = isl_map_get_hash(map);4394	isl_hash_hash(*hash, map_hash);4395 4396	isl_map_free(map);4397	return isl_stat_ok;4398}4399 4400/* Return a hash value that digests "umap".4401 */4402uint32_t isl_union_map_get_hash(__isl_keep isl_union_map *umap)4403{4404	uint32_t hash;4405 4406	if (!umap)4407		return 0;4408 4409	hash = isl_hash_init();4410	if (isl_union_map_foreach_map(umap, &add_hash, &hash) < 0)4411		return 0;4412 4413	return hash;4414}4415 4416/* Return a hash value that digests "uset".4417 */4418uint32_t isl_union_set_get_hash(__isl_keep isl_union_set *uset)4419{4420	return isl_union_map_get_hash(uset);4421}4422 4423/* Add the number of basic sets in "set" to "n".4424 */4425static isl_stat add_n(__isl_take isl_set *set, void *user)4426{4427	int *n = user;4428	isl_size set_n;4429 4430	set_n = isl_set_n_basic_set(set);4431	*n += set_n;4432	isl_set_free(set);4433 4434	return set_n < 0 ? isl_stat_error : isl_stat_ok;4435}4436 4437/* Return the total number of basic sets in "uset".4438 */4439int isl_union_set_n_basic_set(__isl_keep isl_union_set *uset)4440{4441	int n = 0;4442 4443	if (isl_union_set_foreach_set(uset, &add_n, &n) < 0)4444		return -1;4445 4446	return n;4447}4448 4449/* Add the basic sets in "set" to "list".4450 */4451static isl_stat add_list(__isl_take isl_set *set, void *user)4452{4453	isl_basic_set_list **list = user;4454	isl_basic_set_list *list_i;4455 4456	list_i = isl_set_get_basic_set_list(set);4457	*list = isl_basic_set_list_concat(*list, list_i);4458	isl_set_free(set);4459 4460	if (!*list)4461		return isl_stat_error;4462	return isl_stat_ok;4463}4464 4465/* Return a list containing all the basic sets in "uset".4466 *4467 * First construct a list of the appropriate size and4468 * then add all the elements.4469 */4470__isl_give isl_basic_set_list *isl_union_set_get_basic_set_list(4471	__isl_keep isl_union_set *uset)4472{4473	int n;4474	isl_ctx *ctx;4475	isl_basic_set_list *list;4476 4477	if (!uset)4478		return NULL;4479	ctx = isl_union_set_get_ctx(uset);4480	n = isl_union_set_n_basic_set(uset);4481	if (n < 0)4482		return NULL;4483	list = isl_basic_set_list_alloc(ctx, n);4484	if (isl_union_set_foreach_set(uset, &add_list, &list) < 0)4485		list = isl_basic_set_list_free(list);4486 4487	return list;4488}4489 4490/* Internal data structure for isl_union_map_remove_map_if.4491 * "fn" and "user" are the arguments to isl_union_map_remove_map_if.4492 */4493struct isl_union_map_remove_map_if_data {4494	isl_bool (*fn)(__isl_keep isl_map *map, void *user);4495	void *user;4496};4497 4498/* isl_un_op_control filter that negates the result of data->fn4499 * called on "map".4500 */4501static isl_bool not(__isl_keep isl_map *map, void *user)4502{4503	struct isl_union_map_remove_map_if_data *data = user;4504 4505	return isl_bool_not(data->fn(map, data->user));4506}4507 4508/* Dummy isl_un_op_control transformation callback that4509 * simply returns the input.4510 */4511static __isl_give isl_map *map_id(__isl_take isl_map *map)4512{4513	return map;4514}4515 4516/* Call "fn" on every map in "umap" and remove those maps4517 * for which the callback returns true.4518 *4519 * Use un_op to keep only those maps that are not filtered out,4520 * applying an identity transformation on them.4521 */4522__isl_give isl_union_map *isl_union_map_remove_map_if(4523	__isl_take isl_union_map *umap,4524	isl_bool (*fn)(__isl_keep isl_map *map, void *user), void *user)4525{4526	struct isl_union_map_remove_map_if_data data = { fn, user };4527	struct isl_un_op_control control = {4528		.filter = &not,4529		.filter_user = &data,4530		.fn_map = &map_id,4531	};4532	return un_op(umap, &control);4533}4534 4535/* Does "map" have "space" as domain (ignoring parameters)?4536 */4537static isl_bool has_domain_space_tuples(__isl_keep isl_map *map, void *user)4538{4539	isl_space *space = user;4540 4541	return isl_space_has_domain_tuples(space, isl_map_peek_space(map));4542}4543 4544/* Does "map" have "space" as range (ignoring parameters)?4545 */4546static isl_bool has_range_space_tuples(__isl_keep isl_map *map, void *user)4547{4548	isl_space *space = user;4549 4550	return isl_space_has_range_tuples(space, isl_map_peek_space(map));4551}4552 4553/* Wrapper around isl_map_bind_range for use as a un_op callback.4554 */4555static __isl_give isl_map *bind_range(__isl_take isl_map *map, void *user)4556{4557	isl_multi_id *tuple = user;4558 4559	return isl_map_bind_range(map, isl_multi_id_copy(tuple));4560}4561 4562/* Bind the output dimensions of "umap" to parameters with identifiers4563 * specified by "tuple", living in the range space of "umap",4564 * for those maps that have a matching range space.4565 */4566__isl_give isl_union_set *isl_union_map_bind_range(4567	__isl_take isl_union_map *umap, __isl_take isl_multi_id *tuple)4568{4569	struct isl_un_op_control control = {4570		.filter = &has_range_space_tuples,4571		.filter_user = isl_multi_id_peek_space(tuple),4572		.fn_map2 = &bind_range,4573		.fn_map2_user = tuple,4574	};4575	isl_union_set *bound;4576 4577	bound = uset_from_umap(un_op(umap, &control));4578	isl_multi_id_free(tuple);4579	return bound;4580}4581 4582/* Only keep those elements in "umap" that have a domain in "space".4583 */4584__isl_give isl_union_map *isl_union_map_intersect_domain_space(4585	__isl_take isl_union_map *umap, __isl_take isl_space *space)4586{4587	struct isl_un_op_control control = {4588		.filter = &has_domain_space_tuples,4589		.filter_user = space,4590	};4591 4592	umap = un_op(umap, &control);4593	isl_space_free(space);4594	return umap;4595}4596 4597/* Only keep those elements in "umap" that have a range in "space".4598 */4599__isl_give isl_union_map *isl_union_map_intersect_range_space(4600	__isl_take isl_union_map *umap, __isl_take isl_space *space)4601{4602	struct isl_un_op_control control = {4603		.filter = &has_range_space_tuples,4604		.filter_user = space,4605	};4606 4607	umap = un_op(umap, &control);4608	isl_space_free(space);4609	return umap;4610}4611