Català-Valencià – Catalan中文 – Chinese (Simplified)中文 – Chinese (Traditional)Česky – CzechDansk – DanishNederlands – DutchEnglish – EnglishSuomi – FinnishFrançais – FrenchDeutsch – Germanעברית – Hebrewहिंदी – HindiMagyar – HungarianBahasa Indonesia – IndonesianItaliano – Italian日本語 – Japanese한국어 – KoreanМакедонски – Macedonianमराठी – MarathiNorsk – NorwegianPolski – PolishPortuguês – PortuguesePortuguês – Portuguese (Brazil)Русский – RussianSlovenčina – SlovakSlovenščina – SlovenianEspañol – SpanishSvenska – SwedishTürkçe – TurkishУкраїнська – UkrainianOëzbekcha – Uzbek

nexmon – Blame information for rev 1

Rev	Author	Line No.	Line
1	office	1	/*
		2	* Copyright 2011 INRIA Saclay
		3	* Copyright 2011 Sven Verdoolaege
		4	* Copyright 2012 Ecole Normale Superieure
		5	*
		6	* Use of this software is governed by the GNU LGPLv2.1 license
		7	*
		8	* Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
		9	* Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
		10	* 91893 Orsay, France
		11	* and Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
		12	*/
		13
		14	#include <isl_ctx_private.h>
		15	#define ISL_DIM_H
		16	#include <isl_map_private.h>
		17	#include <isl_union_map_private.h>
		18	#include <isl_aff_private.h>
		19	#include <isl_space_private.h>
		20	#include <isl_local_space_private.h>
		21	#include <isl_mat_private.h>
		22	#include <isl_list_private.h>
		23	#include <isl/constraint.h>
		24	#include <isl/seq.h>
		25	#include <isl/set.h>
		26	#include <isl_config.h>
		27
		28	__isl_give isl_aff *isl_aff_alloc_vec(__isl_take isl_local_space *ls,
		29	__isl_take isl_vec *v)
		30	{
		31	isl_aff *aff;
		32
		33	if (!ls || !v)
		34	goto error;
		35
		36	aff = isl_calloc_type(v->ctx, struct isl_aff);
		37	if (!aff)
		38	goto error;
		39
		40	aff->ref = 1;
		41	aff->ls = ls;
		42	aff->v = v;
		43
		44	return aff;
		45	error:
		46	isl_local_space_free(ls);
		47	isl_vec_free(v);
		48	return NULL;
		49	}
		50
		51	__isl_give isl_aff *isl_aff_alloc(__isl_take isl_local_space *ls)
		52	{
		53	isl_ctx *ctx;
		54	isl_vec *v;
		55	unsigned total;
		56
		57	if (!ls)
		58	return NULL;
		59
		60	ctx = isl_local_space_get_ctx(ls);
		61	if (!isl_local_space_divs_known(ls))
		62	isl_die(ctx, isl_error_invalid, "local space has unknown divs",
		63	goto error);
		64	if (!isl_local_space_is_set(ls))
		65	isl_die(ctx, isl_error_invalid,
		66	"domain of affine expression should be a set",
		67	goto error);
		68
		69	total = isl_local_space_dim(ls, isl_dim_all);
		70	v = isl_vec_alloc(ctx, 1 + 1 + total);
		71	return isl_aff_alloc_vec(ls, v);
		72	error:
		73	isl_local_space_free(ls);
		74	return NULL;
		75	}
		76
		77	__isl_give isl_aff *isl_aff_zero_on_domain(__isl_take isl_local_space *ls)
		78	{
		79	isl_aff *aff;
		80
		81	aff = isl_aff_alloc(ls);
		82	if (!aff)
		83	return NULL;
		84
		85	isl_int_set_si(aff->v->el[0], 1);
		86	isl_seq_clr(aff->v->el + 1, aff->v->size - 1);
		87
		88	return aff;
		89	}
		90
		91	__isl_give isl_aff *isl_aff_copy(__isl_keep isl_aff *aff)
		92	{
		93	if (!aff)
		94	return NULL;
		95
		96	aff->ref++;
		97	return aff;
		98	}
		99
		100	__isl_give isl_aff *isl_aff_dup(__isl_keep isl_aff *aff)
		101	{
		102	if (!aff)
		103	return NULL;
		104
		105	return isl_aff_alloc_vec(isl_local_space_copy(aff->ls),
		106	isl_vec_copy(aff->v));
		107	}
		108
		109	__isl_give isl_aff *isl_aff_cow(__isl_take isl_aff *aff)
		110	{
		111	if (!aff)
		112	return NULL;
		113
		114	if (aff->ref == 1)
		115	return aff;
		116	aff->ref--;
		117	return isl_aff_dup(aff);
		118	}
		119
		120	void *isl_aff_free(__isl_take isl_aff *aff)
		121	{
		122	if (!aff)
		123	return NULL;
		124
		125	if (--aff->ref > 0)
		126	return NULL;
		127
		128	isl_local_space_free(aff->ls);
		129	isl_vec_free(aff->v);
		130
		131	free(aff);
		132
		133	return NULL;
		134	}
		135
		136	isl_ctx *isl_aff_get_ctx(__isl_keep isl_aff *aff)
		137	{
		138	return aff ? isl_local_space_get_ctx(aff->ls) : NULL;
		139	}
		140
		141	/* Externally, an isl_aff has a map space, but internally, the
		142	* ls field corresponds to the domain of that space.
		143	*/
		144	int isl_aff_dim(__isl_keep isl_aff *aff, enum isl_dim_type type)
		145	{
		146	if (!aff)
		147	return 0;
		148	if (type == isl_dim_out)
		149	return 1;
		150	if (type == isl_dim_in)
		151	type = isl_dim_set;
		152	return isl_local_space_dim(aff->ls, type);
		153	}
		154
		155	__isl_give isl_space *isl_aff_get_domain_space(__isl_keep isl_aff *aff)
		156	{
		157	return aff ? isl_local_space_get_space(aff->ls) : NULL;
		158	}
		159
		160	__isl_give isl_space *isl_aff_get_space(__isl_keep isl_aff *aff)
		161	{
		162	isl_space *space;
		163	if (!aff)
		164	return NULL;
		165	space = isl_local_space_get_space(aff->ls);
		166	space = isl_space_from_domain(space);
		167	space = isl_space_add_dims(space, isl_dim_out, 1);
		168	return space;
		169	}
		170
		171	__isl_give isl_local_space *isl_aff_get_domain_local_space(
		172	__isl_keep isl_aff *aff)
		173	{
		174	return aff ? isl_local_space_copy(aff->ls) : NULL;
		175	}
		176
		177	__isl_give isl_local_space *isl_aff_get_local_space(__isl_keep isl_aff *aff)
		178	{
		179	isl_local_space *ls;
		180	if (!aff)
		181	return NULL;
		182	ls = isl_local_space_copy(aff->ls);
		183	ls = isl_local_space_from_domain(ls);
		184	ls = isl_local_space_add_dims(ls, isl_dim_out, 1);
		185	return ls;
		186	}
		187
		188	/* Externally, an isl_aff has a map space, but internally, the
		189	* ls field corresponds to the domain of that space.
		190	*/
		191	const char *isl_aff_get_dim_name(__isl_keep isl_aff *aff,
		192	enum isl_dim_type type, unsigned pos)
		193	{
		194	if (!aff)
		195	return NULL;
		196	if (type == isl_dim_out)
		197	return NULL;
		198	if (type == isl_dim_in)
		199	type = isl_dim_set;
		200	return isl_local_space_get_dim_name(aff->ls, type, pos);
		201	}
		202
		203	__isl_give isl_aff *isl_aff_reset_domain_space(__isl_take isl_aff *aff,
		204	__isl_take isl_space *dim)
		205	{
		206	aff = isl_aff_cow(aff);
		207	if (!aff || !dim)
		208	goto error;
		209
		210	aff->ls = isl_local_space_reset_space(aff->ls, dim);
		211	if (!aff->ls)
		212	return isl_aff_free(aff);
		213
		214	return aff;
		215	error:
		216	isl_aff_free(aff);
		217	isl_space_free(dim);
		218	return NULL;
		219	}
		220
		221	/* Reset the space of "aff". This function is called from isl_pw_templ.c
		222	* and doesn't know if the space of an element object is represented
		223	* directly or through its domain. It therefore passes along both.
		224	*/
		225	__isl_give isl_aff *isl_aff_reset_space_and_domain(__isl_take isl_aff *aff,
		226	__isl_take isl_space *space, __isl_take isl_space *domain)
		227	{
		228	isl_space_free(space);
		229	return isl_aff_reset_domain_space(aff, domain);
		230	}
		231
		232	/* Reorder the coefficients of the affine expression based
		233	* on the given reodering.
		234	* The reordering r is assumed to have been extended with the local
		235	* variables.
		236	*/
		237	static __isl_give isl_vec *vec_reorder(__isl_take isl_vec *vec,
		238	__isl_take isl_reordering *r, int n_div)
		239	{
		240	isl_vec *res;
		241	int i;
		242
		243	if (!vec || !r)
		244	goto error;
		245
		246	res = isl_vec_alloc(vec->ctx,
		247	2 + isl_space_dim(r->dim, isl_dim_all) + n_div);
		248	isl_seq_cpy(res->el, vec->el, 2);
		249	isl_seq_clr(res->el + 2, res->size - 2);
		250	for (i = 0; i < r->len; ++i)
		251	isl_int_set(res->el[2 + r->pos[i]], vec->el[2 + i]);
		252
		253	isl_reordering_free(r);
		254	isl_vec_free(vec);
		255	return res;
		256	error:
		257	isl_vec_free(vec);
		258	isl_reordering_free(r);
		259	return NULL;
		260	}
		261
		262	/* Reorder the dimensions of the domain of "aff" according
		263	* to the given reordering.
		264	*/
		265	__isl_give isl_aff *isl_aff_realign_domain(__isl_take isl_aff *aff,
		266	__isl_take isl_reordering *r)
		267	{
		268	aff = isl_aff_cow(aff);
		269	if (!aff)
		270	goto error;
		271
		272	r = isl_reordering_extend(r, aff->ls->div->n_row);
		273	aff->v = vec_reorder(aff->v, isl_reordering_copy(r),
		274	aff->ls->div->n_row);
		275	aff->ls = isl_local_space_realign(aff->ls, r);
		276
		277	if (!aff->v || !aff->ls)
		278	return isl_aff_free(aff);
		279
		280	return aff;
		281	error:
		282	isl_aff_free(aff);
		283	isl_reordering_free(r);
		284	return NULL;
		285	}
		286
		287	__isl_give isl_aff *isl_aff_align_params(__isl_take isl_aff *aff,
		288	__isl_take isl_space *model)
		289	{
		290	if (!aff || !model)
		291	goto error;
		292
		293	if (!isl_space_match(aff->ls->dim, isl_dim_param,
		294	model, isl_dim_param)) {
		295	isl_reordering *exp;
		296
		297	model = isl_space_drop_dims(model, isl_dim_in,
		298	0, isl_space_dim(model, isl_dim_in));
		299	model = isl_space_drop_dims(model, isl_dim_out,
		300	0, isl_space_dim(model, isl_dim_out));
		301	exp = isl_parameter_alignment_reordering(aff->ls->dim, model);
		302	exp = isl_reordering_extend_space(exp,
		303	isl_aff_get_domain_space(aff));
		304	aff = isl_aff_realign_domain(aff, exp);
		305	}
		306
		307	isl_space_free(model);
		308	return aff;
		309	error:
		310	isl_space_free(model);
		311	isl_aff_free(aff);
		312	return NULL;
		313	}
		314
		315	int isl_aff_plain_is_zero(__isl_keep isl_aff *aff)
		316	{
		317	if (!aff)
		318	return -1;
		319
		320	return isl_seq_first_non_zero(aff->v->el + 1, aff->v->size - 1) < 0;
		321	}
		322
		323	int isl_aff_plain_is_equal(__isl_keep isl_aff *aff1, __isl_keep isl_aff *aff2)
		324	{
		325	int equal;
		326
		327	if (!aff1 || !aff2)
		328	return -1;
		329
		330	equal = isl_local_space_is_equal(aff1->ls, aff2->ls);
		331	if (equal < 0 || !equal)
		332	return equal;
		333
		334	return isl_vec_is_equal(aff1->v, aff2->v);
		335	}
		336
		337	int isl_aff_get_denominator(__isl_keep isl_aff *aff, isl_int *v)
		338	{
		339	if (!aff)
		340	return -1;
		341	isl_int_set(*v, aff->v->el[0]);
		342	return 0;
		343	}
		344
		345	int isl_aff_get_constant(__isl_keep isl_aff *aff, isl_int *v)
		346	{
		347	if (!aff)
		348	return -1;
		349	isl_int_set(*v, aff->v->el[1]);
		350	return 0;
		351	}
		352
		353	int isl_aff_get_coefficient(__isl_keep isl_aff *aff,
		354	enum isl_dim_type type, int pos, isl_int *v)
		355	{
		356	if (!aff)
		357	return -1;
		358
		359	if (type == isl_dim_out)
		360	isl_die(aff->v->ctx, isl_error_invalid,
		361	"output/set dimension does not have a coefficient",
		362	return -1);
		363	if (type == isl_dim_in)
		364	type = isl_dim_set;
		365
		366	if (pos >= isl_local_space_dim(aff->ls, type))
		367	isl_die(aff->v->ctx, isl_error_invalid,
		368	"position out of bounds", return -1);
		369
		370	pos += isl_local_space_offset(aff->ls, type);
		371	isl_int_set(*v, aff->v->el[1 + pos]);
		372
		373	return 0;
		374	}
		375
		376	__isl_give isl_aff *isl_aff_set_denominator(__isl_take isl_aff *aff, isl_int v)
		377	{
		378	aff = isl_aff_cow(aff);
		379	if (!aff)
		380	return NULL;
		381
		382	aff->v = isl_vec_cow(aff->v);
		383	if (!aff->v)
		384	return isl_aff_free(aff);
		385
		386	isl_int_set(aff->v->el[0], v);
		387
		388	return aff;
		389	}
		390
		391	__isl_give isl_aff *isl_aff_set_constant(__isl_take isl_aff *aff, isl_int v)
		392	{
		393	aff = isl_aff_cow(aff);
		394	if (!aff)
		395	return NULL;
		396
		397	aff->v = isl_vec_cow(aff->v);
		398	if (!aff->v)
		399	return isl_aff_free(aff);
		400
		401	isl_int_set(aff->v->el[1], v);
		402
		403	return aff;
		404	}
		405
		406	__isl_give isl_aff *isl_aff_add_constant(__isl_take isl_aff *aff, isl_int v)
		407	{
		408	if (isl_int_is_zero(v))
		409	return aff;
		410
		411	aff = isl_aff_cow(aff);
		412	if (!aff)
		413	return NULL;
		414
		415	aff->v = isl_vec_cow(aff->v);
		416	if (!aff->v)
		417	return isl_aff_free(aff);
		418
		419	isl_int_addmul(aff->v->el[1], aff->v->el[0], v);
		420
		421	return aff;
		422	}
		423
		424	__isl_give isl_aff *isl_aff_add_constant_si(__isl_take isl_aff *aff, int v)
		425	{
		426	isl_int t;
		427
		428	isl_int_init(t);
		429	isl_int_set_si(t, v);
		430	aff = isl_aff_add_constant(aff, t);
		431	isl_int_clear(t);
		432
		433	return aff;
		434	}
		435
		436	__isl_give isl_aff *isl_aff_set_constant_si(__isl_take isl_aff *aff, int v)
		437	{
		438	aff = isl_aff_cow(aff);
		439	if (!aff)
		440	return NULL;
		441
		442	aff->v = isl_vec_cow(aff->v);
		443	if (!aff->v)
		444	return isl_aff_free(aff);
		445
		446	isl_int_set_si(aff->v->el[1], v);
		447
		448	return aff;
		449	}
		450
		451	__isl_give isl_aff *isl_aff_set_coefficient(__isl_take isl_aff *aff,
		452	enum isl_dim_type type, int pos, isl_int v)
		453	{
		454	if (!aff)
		455	return NULL;
		456
		457	if (type == isl_dim_out)
		458	isl_die(aff->v->ctx, isl_error_invalid,
		459	"output/set dimension does not have a coefficient",
		460	return isl_aff_free(aff));
		461	if (type == isl_dim_in)
		462	type = isl_dim_set;
		463
		464	if (pos >= isl_local_space_dim(aff->ls, type))
		465	isl_die(aff->v->ctx, isl_error_invalid,
		466	"position out of bounds", return isl_aff_free(aff));
		467
		468	aff = isl_aff_cow(aff);
		469	if (!aff)
		470	return NULL;
		471
		472	aff->v = isl_vec_cow(aff->v);
		473	if (!aff->v)
		474	return isl_aff_free(aff);
		475
		476	pos += isl_local_space_offset(aff->ls, type);
		477	isl_int_set(aff->v->el[1 + pos], v);
		478
		479	return aff;
		480	}
		481
		482	__isl_give isl_aff *isl_aff_set_coefficient_si(__isl_take isl_aff *aff,
		483	enum isl_dim_type type, int pos, int v)
		484	{
		485	if (!aff)
		486	return NULL;
		487
		488	if (type == isl_dim_out)
		489	isl_die(aff->v->ctx, isl_error_invalid,
		490	"output/set dimension does not have a coefficient",
		491	return isl_aff_free(aff));
		492	if (type == isl_dim_in)
		493	type = isl_dim_set;
		494
		495	if (pos >= isl_local_space_dim(aff->ls, type))
		496	isl_die(aff->v->ctx, isl_error_invalid,
		497	"position out of bounds", return isl_aff_free(aff));
		498
		499	aff = isl_aff_cow(aff);
		500	if (!aff)
		501	return NULL;
		502
		503	aff->v = isl_vec_cow(aff->v);
		504	if (!aff->v)
		505	return isl_aff_free(aff);
		506
		507	pos += isl_local_space_offset(aff->ls, type);
		508	isl_int_set_si(aff->v->el[1 + pos], v);
		509
		510	return aff;
		511	}
		512
		513	__isl_give isl_aff *isl_aff_add_coefficient(__isl_take isl_aff *aff,
		514	enum isl_dim_type type, int pos, isl_int v)
		515	{
		516	if (!aff)
		517	return NULL;
		518
		519	if (type == isl_dim_out)
		520	isl_die(aff->v->ctx, isl_error_invalid,
		521	"output/set dimension does not have a coefficient",
		522	return isl_aff_free(aff));
		523	if (type == isl_dim_in)
		524	type = isl_dim_set;
		525
		526	if (pos >= isl_local_space_dim(aff->ls, type))
		527	isl_die(aff->v->ctx, isl_error_invalid,
		528	"position out of bounds", return isl_aff_free(aff));
		529
		530	aff = isl_aff_cow(aff);
		531	if (!aff)
		532	return NULL;
		533
		534	aff->v = isl_vec_cow(aff->v);
		535	if (!aff->v)
		536	return isl_aff_free(aff);
		537
		538	pos += isl_local_space_offset(aff->ls, type);
		539	isl_int_addmul(aff->v->el[1 + pos], aff->v->el[0], v);
		540
		541	return aff;
		542	}
		543
		544	__isl_give isl_aff *isl_aff_add_coefficient_si(__isl_take isl_aff *aff,
		545	enum isl_dim_type type, int pos, int v)
		546	{
		547	isl_int t;
		548
		549	isl_int_init(t);
		550	isl_int_set_si(t, v);
		551	aff = isl_aff_add_coefficient(aff, type, pos, t);
		552	isl_int_clear(t);
		553
		554	return aff;
		555	}
		556
		557	__isl_give isl_aff *isl_aff_get_div(__isl_keep isl_aff *aff, int pos)
		558	{
		559	if (!aff)
		560	return NULL;
		561
		562	return isl_local_space_get_div(aff->ls, pos);
		563	}
		564
		565	__isl_give isl_aff *isl_aff_neg(__isl_take isl_aff *aff)
		566	{
		567	aff = isl_aff_cow(aff);
		568	if (!aff)
		569	return NULL;
		570	aff->v = isl_vec_cow(aff->v);
		571	if (!aff->v)
		572	return isl_aff_free(aff);
		573
		574	isl_seq_neg(aff->v->el + 1, aff->v->el + 1, aff->v->size - 1);
		575
		576	return aff;
		577	}
		578
		579	/* Remove divs from the local space that do not appear in the affine
		580	* expression.
		581	* We currently only remove divs at the end.
		582	* Some intermediate divs may also not appear directly in the affine
		583	* expression, but we would also need to check that no other divs are
		584	* defined in terms of them.
		585	*/
		586	__isl_give isl_aff *isl_aff_remove_unused_divs( __isl_take isl_aff *aff)
		587	{
		588	int pos;
		589	int off;
		590	int n;
		591
		592	if (!aff)
		593	return NULL;
		594
		595	n = isl_local_space_dim(aff->ls, isl_dim_div);
		596	off = isl_local_space_offset(aff->ls, isl_dim_div);
		597
		598	pos = isl_seq_last_non_zero(aff->v->el + 1 + off, n) + 1;
		599	if (pos == n)
		600	return aff;
		601
		602	aff = isl_aff_cow(aff);
		603	if (!aff)
		604	return NULL;
		605
		606	aff->ls = isl_local_space_drop_dims(aff->ls, isl_dim_div, pos, n - pos);
		607	aff->v = isl_vec_drop_els(aff->v, 1 + off + pos, n - pos);
		608	if (!aff->ls || !aff->v)
		609	return isl_aff_free(aff);
		610
		611	return aff;
		612	}
		613
		614	__isl_give isl_aff *isl_aff_normalize(__isl_take isl_aff *aff)
		615	{
		616	if (!aff)
		617	return NULL;
		618	aff->v = isl_vec_normalize(aff->v);
		619	if (!aff->v)
		620	return isl_aff_free(aff);
		621	aff = isl_aff_remove_unused_divs(aff);
		622	return aff;
		623	}
		624
		625	/* Given f, return floor(f).
		626	* If f is an integer expression, then just return f.
		627	* If f is a constant, then return the constant floor(f).
		628	* Otherwise, if f = g/m, write g = q m + r,
		629	* create a new div d = [r/m] and return the expression q + d.
		630	* The coefficients in r are taken to lie between -m/2 and m/2.
		631	*/
		632	__isl_give isl_aff *isl_aff_floor(__isl_take isl_aff *aff)
		633	{
		634	int i;
		635	int size;
		636	isl_ctx *ctx;
		637	isl_vec *div;
		638
		639	if (!aff)
		640	return NULL;
		641
		642	if (isl_int_is_one(aff->v->el[0]))
		643	return aff;
		644
		645	aff = isl_aff_cow(aff);
		646	if (!aff)
		647	return NULL;
		648
		649	aff->v = isl_vec_cow(aff->v);
		650	if (!aff->v)
		651	return isl_aff_free(aff);
		652
		653	if (isl_aff_is_cst(aff)) {
		654	isl_int_fdiv_q(aff->v->el[1], aff->v->el[1], aff->v->el[0]);
		655	isl_int_set_si(aff->v->el[0], 1);
		656	return aff;
		657	}
		658
		659	div = isl_vec_copy(aff->v);
		660	div = isl_vec_cow(div);
		661	if (!div)
		662	return isl_aff_free(aff);
		663
		664	ctx = isl_aff_get_ctx(aff);
		665	isl_int_fdiv_q(aff->v->el[0], aff->v->el[0], ctx->two);
		666	for (i = 1; i < aff->v->size; ++i) {
		667	isl_int_fdiv_r(div->el[i], div->el[i], div->el[0]);
		668	isl_int_fdiv_q(aff->v->el[i], aff->v->el[i], div->el[0]);
		669	if (isl_int_gt(div->el[i], aff->v->el[0])) {
		670	isl_int_sub(div->el[i], div->el[i], div->el[0]);
		671	isl_int_add_ui(aff->v->el[i], aff->v->el[i], 1);
		672	}
		673	}
		674
		675	aff->ls = isl_local_space_add_div(aff->ls, div);
		676	if (!aff->ls)
		677	return isl_aff_free(aff);
		678
		679	size = aff->v->size;
		680	aff->v = isl_vec_extend(aff->v, size + 1);
		681	if (!aff->v)
		682	return isl_aff_free(aff);
		683	isl_int_set_si(aff->v->el[0], 1);
		684	isl_int_set_si(aff->v->el[size], 1);
		685
		686	return aff;
		687	}
		688
		689	/* Compute
		690	*
		691	* aff mod m = aff - m * floor(aff/m)
		692	*/
		693	__isl_give isl_aff *isl_aff_mod(__isl_take isl_aff *aff, isl_int m)
		694	{
		695	isl_aff *res;
		696
		697	res = isl_aff_copy(aff);
		698	aff = isl_aff_scale_down(aff, m);
		699	aff = isl_aff_floor(aff);
		700	aff = isl_aff_scale(aff, m);
		701	res = isl_aff_sub(res, aff);
		702
		703	return res;
		704	}
		705
		706	/* Compute
		707	*
		708	* pwaff mod m = pwaff - m * floor(pwaff/m)
		709	*/
		710	__isl_give isl_pw_aff *isl_pw_aff_mod(__isl_take isl_pw_aff *pwaff, isl_int m)
		711	{
		712	isl_pw_aff *res;
		713
		714	res = isl_pw_aff_copy(pwaff);
		715	pwaff = isl_pw_aff_scale_down(pwaff, m);
		716	pwaff = isl_pw_aff_floor(pwaff);
		717	pwaff = isl_pw_aff_scale(pwaff, m);
		718	res = isl_pw_aff_sub(res, pwaff);
		719
		720	return res;
		721	}
		722
		723	/* Given f, return ceil(f).
		724	* If f is an integer expression, then just return f.
		725	* Otherwise, create a new div d = [-f] and return the expression -d.
		726	*/
		727	__isl_give isl_aff *isl_aff_ceil(__isl_take isl_aff *aff)
		728	{
		729	if (!aff)
		730	return NULL;
		731
		732	if (isl_int_is_one(aff->v->el[0]))
		733	return aff;
		734
		735	aff = isl_aff_neg(aff);
		736	aff = isl_aff_floor(aff);
		737	aff = isl_aff_neg(aff);
		738
		739	return aff;
		740	}
		741
		742	/* Apply the expansion computed by isl_merge_divs.
		743	* The expansion itself is given by "exp" while the resulting
		744	* list of divs is given by "div".
		745	*/
		746	__isl_give isl_aff *isl_aff_expand_divs( __isl_take isl_aff *aff,
		747	__isl_take isl_mat *div, int *exp)
		748	{
		749	int i, j;
		750	int old_n_div;
		751	int new_n_div;
		752	int offset;
		753
		754	aff = isl_aff_cow(aff);
		755	if (!aff || !div)
		756	goto error;
		757
		758	old_n_div = isl_local_space_dim(aff->ls, isl_dim_div);
		759	new_n_div = isl_mat_rows(div);
		760	if (new_n_div < old_n_div)
		761	isl_die(isl_mat_get_ctx(div), isl_error_invalid,
		762	"not an expansion", goto error);
		763
		764	aff->v = isl_vec_extend(aff->v, aff->v->size + new_n_div - old_n_div);
		765	if (!aff->v)
		766	goto error;
		767
		768	offset = 1 + isl_local_space_offset(aff->ls, isl_dim_div);
		769	j = old_n_div - 1;
		770	for (i = new_n_div - 1; i >= 0; --i) {
		771	if (j >= 0 && exp[j] == i) {
		772	if (i != j)
		773	isl_int_swap(aff->v->el[offset + i],
		774	aff->v->el[offset + j]);
		775	j--;
		776	} else
		777	isl_int_set_si(aff->v->el[offset + i], 0);
		778	}
		779
		780	aff->ls = isl_local_space_replace_divs(aff->ls, isl_mat_copy(div));
		781	if (!aff->ls)
		782	goto error;
		783	isl_mat_free(div);
		784	return aff;
		785	error:
		786	isl_aff_free(aff);
		787	isl_mat_free(div);
		788	return NULL;
		789	}
		790
		791	/* Add two affine expressions that live in the same local space.
		792	*/
		793	static __isl_give isl_aff *add_expanded(__isl_take isl_aff *aff1,
		794	__isl_take isl_aff *aff2)
		795	{
		796	isl_int gcd, f;
		797
		798	aff1 = isl_aff_cow(aff1);
		799	if (!aff1 || !aff2)
		800	goto error;
		801
		802	aff1->v = isl_vec_cow(aff1->v);
		803	if (!aff1->v)
		804	goto error;
		805
		806	isl_int_init(gcd);
		807	isl_int_init(f);
		808	isl_int_gcd(gcd, aff1->v->el[0], aff2->v->el[0]);
		809	isl_int_divexact(f, aff2->v->el[0], gcd);
		810	isl_seq_scale(aff1->v->el + 1, aff1->v->el + 1, f, aff1->v->size - 1);
		811	isl_int_divexact(f, aff1->v->el[0], gcd);
		812	isl_seq_addmul(aff1->v->el + 1, f, aff2->v->el + 1, aff1->v->size - 1);
		813	isl_int_divexact(f, aff2->v->el[0], gcd);
		814	isl_int_mul(aff1->v->el[0], aff1->v->el[0], f);
		815	isl_int_clear(f);
		816	isl_int_clear(gcd);
		817
		818	isl_aff_free(aff2);
		819	return aff1;
		820	error:
		821	isl_aff_free(aff1);
		822	isl_aff_free(aff2);
		823	return NULL;
		824	}
		825
		826	__isl_give isl_aff *isl_aff_add(__isl_take isl_aff *aff1,
		827	__isl_take isl_aff *aff2)
		828	{
		829	isl_ctx *ctx;
		830	int *exp1 = NULL;
		831	int *exp2 = NULL;
		832	isl_mat *div;
		833
		834	if (!aff1 || !aff2)
		835	goto error;
		836
		837	ctx = isl_aff_get_ctx(aff1);
		838	if (!isl_space_is_equal(aff1->ls->dim, aff2->ls->dim))
		839	isl_die(ctx, isl_error_invalid,
		840	"spaces don't match", goto error);
		841
		842	if (aff1->ls->div->n_row == 0 && aff2->ls->div->n_row == 0)
		843	return add_expanded(aff1, aff2);
		844
		845	exp1 = isl_alloc_array(ctx, int, aff1->ls->div->n_row);
		846	exp2 = isl_alloc_array(ctx, int, aff2->ls->div->n_row);
		847	if (!exp1 || !exp2)
		848	goto error;
		849
		850	div = isl_merge_divs(aff1->ls->div, aff2->ls->div, exp1, exp2);
		851	aff1 = isl_aff_expand_divs(aff1, isl_mat_copy(div), exp1);
		852	aff2 = isl_aff_expand_divs(aff2, div, exp2);
		853	free(exp1);
		854	free(exp2);
		855
		856	return add_expanded(aff1, aff2);
		857	error:
		858	free(exp1);
		859	free(exp2);
		860	isl_aff_free(aff1);
		861	isl_aff_free(aff2);
		862	return NULL;
		863	}
		864
		865	__isl_give isl_aff *isl_aff_sub(__isl_take isl_aff *aff1,
		866	__isl_take isl_aff *aff2)
		867	{
		868	return isl_aff_add(aff1, isl_aff_neg(aff2));
		869	}
		870
		871	__isl_give isl_aff *isl_aff_scale(__isl_take isl_aff *aff, isl_int f)
		872	{
		873	isl_int gcd;
		874
		875	if (isl_int_is_one(f))
		876	return aff;
		877
		878	aff = isl_aff_cow(aff);
		879	if (!aff)
		880	return NULL;
		881	aff->v = isl_vec_cow(aff->v);
		882	if (!aff->v)
		883	return isl_aff_free(aff);
		884
		885	isl_int_init(gcd);
		886	isl_int_gcd(gcd, aff->v->el[0], f);
		887	isl_int_divexact(aff->v->el[0], aff->v->el[0], gcd);
		888	isl_int_divexact(gcd, f, gcd);
		889	isl_seq_scale(aff->v->el + 1, aff->v->el + 1, gcd, aff->v->size - 1);
		890	isl_int_clear(gcd);
		891
		892	return aff;
		893	}
		894
		895	__isl_give isl_aff *isl_aff_scale_down(__isl_take isl_aff *aff, isl_int f)
		896	{
		897	isl_int gcd;
		898
		899	if (isl_int_is_one(f))
		900	return aff;
		901
		902	aff = isl_aff_cow(aff);
		903	if (!aff)
		904	return NULL;
		905	aff->v = isl_vec_cow(aff->v);
		906	if (!aff->v)
		907	return isl_aff_free(aff);
		908
		909	isl_int_init(gcd);
		910	isl_seq_gcd(aff->v->el + 1, aff->v->size - 1, &gcd);
		911	isl_int_gcd(gcd, gcd, f);
		912	isl_seq_scale_down(aff->v->el + 1, aff->v->el + 1, gcd, aff->v->size - 1);
		913	isl_int_divexact(gcd, f, gcd);
		914	isl_int_mul(aff->v->el[0], aff->v->el[0], gcd);
		915	isl_int_clear(gcd);
		916
		917	return aff;
		918	}
		919
		920	__isl_give isl_aff *isl_aff_scale_down_ui(__isl_take isl_aff *aff, unsigned f)
		921	{
		922	isl_int v;
		923
		924	if (f == 1)
		925	return aff;
		926
		927	isl_int_init(v);
		928	isl_int_set_ui(v, f);
		929	aff = isl_aff_scale_down(aff, v);
		930	isl_int_clear(v);
		931
		932	return aff;
		933	}
		934
		935	__isl_give isl_aff *isl_aff_set_dim_name(__isl_take isl_aff *aff,
		936	enum isl_dim_type type, unsigned pos, const char *s)
		937	{
		938	aff = isl_aff_cow(aff);
		939	if (!aff)
		940	return NULL;
		941	if (type == isl_dim_out)
		942	isl_die(aff->v->ctx, isl_error_invalid,
		943	"cannot set name of output/set dimension",
		944	return isl_aff_free(aff));
		945	if (type == isl_dim_in)
		946	type = isl_dim_set;
		947	aff->ls = isl_local_space_set_dim_name(aff->ls, type, pos, s);
		948	if (!aff->ls)
		949	return isl_aff_free(aff);
		950
		951	return aff;
		952	}
		953
		954	__isl_give isl_aff *isl_aff_set_dim_id(__isl_take isl_aff *aff,
		955	enum isl_dim_type type, unsigned pos, __isl_take isl_id *id)
		956	{
		957	aff = isl_aff_cow(aff);
		958	if (!aff)
		959	return isl_id_free(id);
		960	if (type == isl_dim_out)
		961	isl_die(aff->v->ctx, isl_error_invalid,
		962	"cannot set name of output/set dimension",
		963	goto error);
		964	if (type == isl_dim_in)
		965	type = isl_dim_set;
		966	aff->ls = isl_local_space_set_dim_id(aff->ls, type, pos, id);
		967	if (!aff->ls)
		968	return isl_aff_free(aff);
		969
		970	return aff;
		971	error:
		972	isl_id_free(id);
		973	isl_aff_free(aff);
		974	return NULL;
		975	}
		976
		977	/* Exploit the equalities in "eq" to simplify the affine expression
		978	* and the expressions of the integer divisions in the local space.
		979	* The integer divisions in this local space are assumed to appear
		980	* as regular dimensions in "eq".
		981	*/
		982	static __isl_give isl_aff *isl_aff_substitute_equalities_lifted(
		983	__isl_take isl_aff *aff, __isl_take isl_basic_set *eq)
		984	{
		985	int i, j;
		986	unsigned total;
		987	unsigned n_div;
		988
		989	if (!eq)
		990	goto error;
		991	if (eq->n_eq == 0) {
		992	isl_basic_set_free(eq);
		993	return aff;
		994	}
		995
		996	aff = isl_aff_cow(aff);
		997	if (!aff)
		998	goto error;
		999
		1000	aff->ls = isl_local_space_substitute_equalities(aff->ls,
		1001	isl_basic_set_copy(eq));
		1002	if (!aff->ls)
		1003	goto error;
		1004
		1005	total = 1 + isl_space_dim(eq->dim, isl_dim_all);
		1006	n_div = eq->n_div;
		1007	for (i = 0; i < eq->n_eq; ++i) {
		1008	j = isl_seq_last_non_zero(eq->eq[i], total + n_div);
		1009	if (j < 0 || j == 0 || j >= total)
		1010	continue;
		1011
		1012	isl_seq_elim(aff->v->el + 1, eq->eq[i], j, total,
		1013	&aff->v->el[0]);
		1014	}
		1015
		1016	isl_basic_set_free(eq);
		1017	aff = isl_aff_normalize(aff);
		1018	return aff;
		1019	error:
		1020	isl_basic_set_free(eq);
		1021	isl_aff_free(aff);
		1022	return NULL;
		1023	}
		1024
		1025	/* Exploit the equalities in "eq" to simplify the affine expression
		1026	* and the expressions of the integer divisions in the local space.
		1027	*/
		1028	static __isl_give isl_aff *isl_aff_substitute_equalities(
		1029	__isl_take isl_aff *aff, __isl_take isl_basic_set *eq)
		1030	{
		1031	int n_div;
		1032
		1033	if (!aff || !eq)
		1034	goto error;
		1035	n_div = isl_local_space_dim(aff->ls, isl_dim_div);
		1036	if (n_div > 0)
		1037	eq = isl_basic_set_add(eq, isl_dim_set, n_div);
		1038	return isl_aff_substitute_equalities_lifted(aff, eq);
		1039	error:
		1040	isl_basic_set_free(eq);
		1041	isl_aff_free(aff);
		1042	return NULL;
		1043	}
		1044
		1045	/* Look for equalities among the variables shared by context and aff
		1046	* and the integer divisions of aff, if any.
		1047	* The equalities are then used to eliminate coefficients and/or integer
		1048	* divisions from aff.
		1049	*/
		1050	__isl_give isl_aff *isl_aff_gist(__isl_take isl_aff *aff,
		1051	__isl_take isl_set *context)
		1052	{
		1053	isl_basic_set *hull;
		1054	int n_div;
		1055
		1056	if (!aff)
		1057	goto error;
		1058	n_div = isl_local_space_dim(aff->ls, isl_dim_div);
		1059	if (n_div > 0) {
		1060	isl_basic_set *bset;
		1061	isl_local_space *ls;
		1062	context = isl_set_add_dims(context, isl_dim_set, n_div);
		1063	ls = isl_aff_get_domain_local_space(aff);
		1064	bset = isl_basic_set_from_local_space(ls);
		1065	bset = isl_basic_set_lift(bset);
		1066	bset = isl_basic_set_flatten(bset);
		1067	context = isl_set_intersect(context,
		1068	isl_set_from_basic_set(bset));
		1069	}
		1070
		1071	hull = isl_set_affine_hull(context);
		1072	return isl_aff_substitute_equalities_lifted(aff, hull);
		1073	error:
		1074	isl_aff_free(aff);
		1075	isl_set_free(context);
		1076	return NULL;
		1077	}
		1078
		1079	__isl_give isl_aff *isl_aff_gist_params(__isl_take isl_aff *aff,
		1080	__isl_take isl_set *context)
		1081	{
		1082	isl_set *dom_context = isl_set_universe(isl_aff_get_domain_space(aff));
		1083	dom_context = isl_set_intersect_params(dom_context, context);
		1084	return isl_aff_gist(aff, dom_context);
		1085	}
		1086
		1087	/* Return a basic set containing those elements in the space
		1088	* of aff where it is non-negative.
		1089	*/
		1090	__isl_give isl_basic_set *isl_aff_nonneg_basic_set(__isl_take isl_aff *aff)
		1091	{
		1092	isl_constraint *ineq;
		1093	isl_basic_set *bset;
		1094
		1095	ineq = isl_inequality_from_aff(aff);
		1096
		1097	bset = isl_basic_set_from_constraint(ineq);
		1098	bset = isl_basic_set_simplify(bset);
		1099	return bset;
		1100	}
		1101
		1102	/* Return a basic set containing those elements in the space
		1103	* of aff where it is zero.
		1104	*/
		1105	__isl_give isl_basic_set *isl_aff_zero_basic_set(__isl_take isl_aff *aff)
		1106	{
		1107	isl_constraint *ineq;
		1108	isl_basic_set *bset;
		1109
		1110	ineq = isl_equality_from_aff(aff);
		1111
		1112	bset = isl_basic_set_from_constraint(ineq);
		1113	bset = isl_basic_set_simplify(bset);
		1114	return bset;
		1115	}
		1116
		1117	/* Return a basic set containing those elements in the shared space
		1118	* of aff1 and aff2 where aff1 is greater than or equal to aff2.
		1119	*/
		1120	__isl_give isl_basic_set *isl_aff_ge_basic_set(__isl_take isl_aff *aff1,
		1121	__isl_take isl_aff *aff2)
		1122	{
		1123	aff1 = isl_aff_sub(aff1, aff2);
		1124
		1125	return isl_aff_nonneg_basic_set(aff1);
		1126	}
		1127
		1128	/* Return a basic set containing those elements in the shared space
		1129	* of aff1 and aff2 where aff1 is smaller than or equal to aff2.
		1130	*/
		1131	__isl_give isl_basic_set *isl_aff_le_basic_set(__isl_take isl_aff *aff1,
		1132	__isl_take isl_aff *aff2)
		1133	{
		1134	return isl_aff_ge_basic_set(aff2, aff1);
		1135	}
		1136
		1137	__isl_give isl_aff *isl_aff_add_on_domain(__isl_keep isl_set *dom,
		1138	__isl_take isl_aff *aff1, __isl_take isl_aff *aff2)
		1139	{
		1140	aff1 = isl_aff_add(aff1, aff2);
		1141	aff1 = isl_aff_gist(aff1, isl_set_copy(dom));
		1142	return aff1;
		1143	}
		1144
		1145	int isl_aff_is_empty(__isl_keep isl_aff *aff)
		1146	{
		1147	if (!aff)
		1148	return -1;
		1149
		1150	return 0;
		1151	}
		1152
		1153	/* Check whether the given affine expression has non-zero coefficient
		1154	* for any dimension in the given range or if any of these dimensions
		1155	* appear with non-zero coefficients in any of the integer divisions
		1156	* involved in the affine expression.
		1157	*/
		1158	int isl_aff_involves_dims(__isl_keep isl_aff *aff,
		1159	enum isl_dim_type type, unsigned first, unsigned n)
		1160	{
		1161	int i;
		1162	isl_ctx *ctx;
		1163	int *active = NULL;
		1164	int involves = 0;
		1165
		1166	if (!aff)
		1167	return -1;
		1168	if (n == 0)
		1169	return 0;
		1170
		1171	ctx = isl_aff_get_ctx(aff);
		1172	if (first + n > isl_aff_dim(aff, type))
		1173	isl_die(ctx, isl_error_invalid,
		1174	"range out of bounds", return -1);
		1175
		1176	active = isl_local_space_get_active(aff->ls, aff->v->el + 2);
		1177	if (!active)
		1178	goto error;
		1179
		1180	first += isl_local_space_offset(aff->ls, type) - 1;
		1181	for (i = 0; i < n; ++i)
		1182	if (active[first + i]) {
		1183	involves = 1;
		1184	break;
		1185	}
		1186
		1187	free(active);
		1188
		1189	return involves;
		1190	error:
		1191	free(active);
		1192	return -1;
		1193	}
		1194
		1195	__isl_give isl_aff *isl_aff_drop_dims(__isl_take isl_aff *aff,
		1196	enum isl_dim_type type, unsigned first, unsigned n)
		1197	{
		1198	isl_ctx *ctx;
		1199
		1200	if (!aff)
		1201	return NULL;
		1202	if (type == isl_dim_out)
		1203	isl_die(aff->v->ctx, isl_error_invalid,
		1204	"cannot drop output/set dimension",
		1205	return isl_aff_free(aff));
		1206	if (type == isl_dim_in)
		1207	type = isl_dim_set;
		1208	if (n == 0 && !isl_local_space_is_named_or_nested(aff->ls, type))
		1209	return aff;
		1210
		1211	ctx = isl_aff_get_ctx(aff);
		1212	if (first + n > isl_local_space_dim(aff->ls, type))
		1213	isl_die(ctx, isl_error_invalid, "range out of bounds",
		1214	return isl_aff_free(aff));
		1215
		1216	aff = isl_aff_cow(aff);
		1217	if (!aff)
		1218	return NULL;
		1219
		1220	aff->ls = isl_local_space_drop_dims(aff->ls, type, first, n);
		1221	if (!aff->ls)
		1222	return isl_aff_free(aff);
		1223
		1224	first += 1 + isl_local_space_offset(aff->ls, type);
		1225	aff->v = isl_vec_drop_els(aff->v, first, n);
		1226	if (!aff->v)
		1227	return isl_aff_free(aff);
		1228
		1229	return aff;
		1230	}
		1231
		1232	/* Project the domain of the affine expression onto its parameter space.
		1233	* The affine expression may not involve any of the domain dimensions.
		1234	*/
		1235	__isl_give isl_aff *isl_aff_project_domain_on_params(__isl_take isl_aff *aff)
		1236	{
		1237	isl_space *space;
		1238	unsigned n;
		1239	int involves;
		1240
		1241	n = isl_aff_dim(aff, isl_dim_in);
		1242	involves = isl_aff_involves_dims(aff, isl_dim_in, 0, n);
		1243	if (involves < 0)
		1244	return isl_aff_free(aff);
		1245	if (involves)
		1246	isl_die(isl_aff_get_ctx(aff), isl_error_invalid,
		1247	"affine expression involves some of the domain dimensions",
		1248	return isl_aff_free(aff));
		1249	aff = isl_aff_drop_dims(aff, isl_dim_in, 0, n);
		1250	space = isl_aff_get_domain_space(aff);
		1251	space = isl_space_params(space);
		1252	aff = isl_aff_reset_domain_space(aff, space);
		1253	return aff;
		1254	}
		1255
		1256	__isl_give isl_aff *isl_aff_insert_dims(__isl_take isl_aff *aff,
		1257	enum isl_dim_type type, unsigned first, unsigned n)
		1258	{
		1259	isl_ctx *ctx;
		1260
		1261	if (!aff)
		1262	return NULL;
		1263	if (type == isl_dim_out)
		1264	isl_die(aff->v->ctx, isl_error_invalid,
		1265	"cannot insert output/set dimensions",
		1266	return isl_aff_free(aff));
		1267	if (type == isl_dim_in)
		1268	type = isl_dim_set;
		1269	if (n == 0 && !isl_local_space_is_named_or_nested(aff->ls, type))
		1270	return aff;
		1271
		1272	ctx = isl_aff_get_ctx(aff);
		1273	if (first > isl_local_space_dim(aff->ls, type))
		1274	isl_die(ctx, isl_error_invalid, "position out of bounds",
		1275	return isl_aff_free(aff));
		1276
		1277	aff = isl_aff_cow(aff);
		1278	if (!aff)
		1279	return NULL;
		1280
		1281	aff->ls = isl_local_space_insert_dims(aff->ls, type, first, n);
		1282	if (!aff->ls)
		1283	return isl_aff_free(aff);
		1284
		1285	first += 1 + isl_local_space_offset(aff->ls, type);
		1286	aff->v = isl_vec_insert_zero_els(aff->v, first, n);
		1287	if (!aff->v)
		1288	return isl_aff_free(aff);
		1289
		1290	return aff;
		1291	}
		1292
		1293	__isl_give isl_aff *isl_aff_add_dims(__isl_take isl_aff *aff,
		1294	enum isl_dim_type type, unsigned n)
		1295	{
		1296	unsigned pos;
		1297
		1298	pos = isl_aff_dim(aff, type);
		1299
		1300	return isl_aff_insert_dims(aff, type, pos, n);
		1301	}
		1302
		1303	__isl_give isl_pw_aff *isl_pw_aff_add_dims(__isl_take isl_pw_aff *pwaff,
		1304	enum isl_dim_type type, unsigned n)
		1305	{
		1306	unsigned pos;
		1307
		1308	pos = isl_pw_aff_dim(pwaff, type);
		1309
		1310	return isl_pw_aff_insert_dims(pwaff, type, pos, n);
		1311	}
		1312
		1313	__isl_give isl_pw_aff *isl_pw_aff_from_aff(__isl_take isl_aff *aff)
		1314	{
		1315	isl_set *dom = isl_set_universe(isl_aff_get_domain_space(aff));
		1316	return isl_pw_aff_alloc(dom, aff);
		1317	}
		1318
		1319	#undef PW
		1320	#define PW isl_pw_aff
		1321	#undef EL
		1322	#define EL isl_aff
		1323	#undef EL_IS_ZERO
		1324	#define EL_IS_ZERO is_empty
		1325	#undef ZERO
		1326	#define ZERO empty
		1327	#undef IS_ZERO
		1328	#define IS_ZERO is_empty
		1329	#undef FIELD
		1330	#define FIELD aff
		1331	#undef DEFAULT_IS_ZERO
		1332	#define DEFAULT_IS_ZERO 0
		1333
		1334	#define NO_EVAL
		1335	#define NO_OPT
		1336	#define NO_MOVE_DIMS
		1337	#define NO_LIFT
		1338	#define NO_MORPH
		1339
		1340	#include <isl_pw_templ.c>
		1341
		1342	static __isl_give isl_set *align_params_pw_pw_set_and(
		1343	__isl_take isl_pw_aff *pwaff1, __isl_take isl_pw_aff *pwaff2,
		1344	__isl_give isl_set *(*fn)(__isl_take isl_pw_aff *pwaff1,
		1345	__isl_take isl_pw_aff *pwaff2))
		1346	{
		1347	if (!pwaff1 || !pwaff2)
		1348	goto error;
		1349	if (isl_space_match(pwaff1->dim, isl_dim_param,
		1350	pwaff2->dim, isl_dim_param))
		1351	return fn(pwaff1, pwaff2);
		1352	if (!isl_space_has_named_params(pwaff1->dim) ||
		1353	!isl_space_has_named_params(pwaff2->dim))
		1354	isl_die(isl_pw_aff_get_ctx(pwaff1), isl_error_invalid,
		1355	"unaligned unnamed parameters", goto error);
		1356	pwaff1 = isl_pw_aff_align_params(pwaff1, isl_pw_aff_get_space(pwaff2));
		1357	pwaff2 = isl_pw_aff_align_params(pwaff2, isl_pw_aff_get_space(pwaff1));
		1358	return fn(pwaff1, pwaff2);
		1359	error:
		1360	isl_pw_aff_free(pwaff1);
		1361	isl_pw_aff_free(pwaff2);
		1362	return NULL;
		1363	}
		1364
		1365	/* Compute a piecewise quasi-affine expression with a domain that
		1366	* is the union of those of pwaff1 and pwaff2 and such that on each
		1367	* cell, the quasi-affine expression is the better (according to cmp)
		1368	* of those of pwaff1 and pwaff2. If only one of pwaff1 or pwaff2
		1369	* is defined on a given cell, then the associated expression
		1370	* is the defined one.
		1371	*/
		1372	static __isl_give isl_pw_aff *pw_aff_union_opt(__isl_take isl_pw_aff *pwaff1,
		1373	__isl_take isl_pw_aff *pwaff2,
		1374	__isl_give isl_basic_set *(*cmp)(__isl_take isl_aff *aff1,
		1375	__isl_take isl_aff *aff2))
		1376	{
		1377	int i, j, n;
		1378	isl_pw_aff *res;
		1379	isl_ctx *ctx;
		1380	isl_set *set;
		1381
		1382	if (!pwaff1 || !pwaff2)
		1383	goto error;
		1384
		1385	ctx = isl_space_get_ctx(pwaff1->dim);
		1386	if (!isl_space_is_equal(pwaff1->dim, pwaff2->dim))
		1387	isl_die(ctx, isl_error_invalid,
		1388	"arguments should live in same space", goto error);
		1389
		1390	if (isl_pw_aff_is_empty(pwaff1)) {
		1391	isl_pw_aff_free(pwaff1);
		1392	return pwaff2;
		1393	}
		1394
		1395	if (isl_pw_aff_is_empty(pwaff2)) {
		1396	isl_pw_aff_free(pwaff2);
		1397	return pwaff1;
		1398	}
		1399
		1400	n = 2 * (pwaff1->n + 1) * (pwaff2->n + 1);
		1401	res = isl_pw_aff_alloc_size(isl_space_copy(pwaff1->dim), n);
		1402
		1403	for (i = 0; i < pwaff1->n; ++i) {
		1404	set = isl_set_copy(pwaff1->p[i].set);
		1405	for (j = 0; j < pwaff2->n; ++j) {
		1406	struct isl_set *common;
		1407	isl_set *better;
		1408
		1409	common = isl_set_intersect(
		1410	isl_set_copy(pwaff1->p[i].set),
		1411	isl_set_copy(pwaff2->p[j].set));
		1412	better = isl_set_from_basic_set(cmp(
		1413	isl_aff_copy(pwaff2->p[j].aff),
		1414	isl_aff_copy(pwaff1->p[i].aff)));
		1415	better = isl_set_intersect(common, better);
		1416	if (isl_set_plain_is_empty(better)) {
		1417	isl_set_free(better);
		1418	continue;
		1419	}
		1420	set = isl_set_subtract(set, isl_set_copy(better));
		1421
		1422	res = isl_pw_aff_add_piece(res, better,
		1423	isl_aff_copy(pwaff2->p[j].aff));
		1424	}
		1425	res = isl_pw_aff_add_piece(res, set,
		1426	isl_aff_copy(pwaff1->p[i].aff));
		1427	}
		1428
		1429	for (j = 0; j < pwaff2->n; ++j) {
		1430	set = isl_set_copy(pwaff2->p[j].set);
		1431	for (i = 0; i < pwaff1->n; ++i)
		1432	set = isl_set_subtract(set,
		1433	isl_set_copy(pwaff1->p[i].set));
		1434	res = isl_pw_aff_add_piece(res, set,
		1435	isl_aff_copy(pwaff2->p[j].aff));
		1436	}
		1437
		1438	isl_pw_aff_free(pwaff1);
		1439	isl_pw_aff_free(pwaff2);
		1440
		1441	return res;
		1442	error:
		1443	isl_pw_aff_free(pwaff1);
		1444	isl_pw_aff_free(pwaff2);
		1445	return NULL;
		1446	}
		1447
		1448	/* Compute a piecewise quasi-affine expression with a domain that
		1449	* is the union of those of pwaff1 and pwaff2 and such that on each
		1450	* cell, the quasi-affine expression is the maximum of those of pwaff1
		1451	* and pwaff2. If only one of pwaff1 or pwaff2 is defined on a given
		1452	* cell, then the associated expression is the defined one.
		1453	*/
		1454	static __isl_give isl_pw_aff *pw_aff_union_max(__isl_take isl_pw_aff *pwaff1,
		1455	__isl_take isl_pw_aff *pwaff2)
		1456	{
		1457	return pw_aff_union_opt(pwaff1, pwaff2, &isl_aff_ge_basic_set);
		1458	}
		1459
		1460	__isl_give isl_pw_aff *isl_pw_aff_union_max(__isl_take isl_pw_aff *pwaff1,
		1461	__isl_take isl_pw_aff *pwaff2)
		1462	{
		1463	return isl_pw_aff_align_params_pw_pw_and(pwaff1, pwaff2,
		1464	&pw_aff_union_max);
		1465	}
		1466
		1467	/* Compute a piecewise quasi-affine expression with a domain that
		1468	* is the union of those of pwaff1 and pwaff2 and such that on each
		1469	* cell, the quasi-affine expression is the minimum of those of pwaff1
		1470	* and pwaff2. If only one of pwaff1 or pwaff2 is defined on a given
		1471	* cell, then the associated expression is the defined one.
		1472	*/
		1473	static __isl_give isl_pw_aff *pw_aff_union_min(__isl_take isl_pw_aff *pwaff1,
		1474	__isl_take isl_pw_aff *pwaff2)
		1475	{
		1476	return pw_aff_union_opt(pwaff1, pwaff2, &isl_aff_le_basic_set);
		1477	}
		1478
		1479	__isl_give isl_pw_aff *isl_pw_aff_union_min(__isl_take isl_pw_aff *pwaff1,
		1480	__isl_take isl_pw_aff *pwaff2)
		1481	{
		1482	return isl_pw_aff_align_params_pw_pw_and(pwaff1, pwaff2,
		1483	&pw_aff_union_min);
		1484	}
		1485
		1486	__isl_give isl_pw_aff *isl_pw_aff_union_opt(__isl_take isl_pw_aff *pwaff1,
		1487	__isl_take isl_pw_aff *pwaff2, int max)
		1488	{
		1489	if (max)
		1490	return isl_pw_aff_union_max(pwaff1, pwaff2);
		1491	else
		1492	return isl_pw_aff_union_min(pwaff1, pwaff2);
		1493	}
		1494
		1495	/* Construct a map with as domain the domain of pwaff and
		1496	* one-dimensional range corresponding to the affine expressions.
		1497	*/
		1498	static __isl_give isl_map *map_from_pw_aff(__isl_take isl_pw_aff *pwaff)
		1499	{
		1500	int i;
		1501	isl_space *dim;
		1502	isl_map *map;
		1503
		1504	if (!pwaff)
		1505	return NULL;
		1506
		1507	dim = isl_pw_aff_get_space(pwaff);
		1508	map = isl_map_empty(dim);
		1509
		1510	for (i = 0; i < pwaff->n; ++i) {
		1511	isl_basic_map *bmap;
		1512	isl_map *map_i;
		1513
		1514	bmap = isl_basic_map_from_aff(isl_aff_copy(pwaff->p[i].aff));
		1515	map_i = isl_map_from_basic_map(bmap);
		1516	map_i = isl_map_intersect_domain(map_i,
		1517	isl_set_copy(pwaff->p[i].set));
		1518	map = isl_map_union_disjoint(map, map_i);
		1519	}
		1520
		1521	isl_pw_aff_free(pwaff);
		1522
		1523	return map;
		1524	}
		1525
		1526	/* Construct a map with as domain the domain of pwaff and
		1527	* one-dimensional range corresponding to the affine expressions.
		1528	*/
		1529	__isl_give isl_map *isl_map_from_pw_aff(__isl_take isl_pw_aff *pwaff)
		1530	{
		1531	if (!pwaff)
		1532	return NULL;
		1533	if (isl_space_is_set(pwaff->dim))
		1534	isl_die(isl_pw_aff_get_ctx(pwaff), isl_error_invalid,
		1535	"space of input is not a map",
		1536	return isl_pw_aff_free(pwaff));
		1537	return map_from_pw_aff(pwaff);
		1538	}
		1539
		1540	/* Construct a one-dimensional set with as parameter domain
		1541	* the domain of pwaff and the single set dimension
		1542	* corresponding to the affine expressions.
		1543	*/
		1544	__isl_give isl_set *isl_set_from_pw_aff(__isl_take isl_pw_aff *pwaff)
		1545	{
		1546	if (!pwaff)
		1547	return NULL;
		1548	if (!isl_space_is_set(pwaff->dim))
		1549	isl_die(isl_pw_aff_get_ctx(pwaff), isl_error_invalid,
		1550	"space of input is not a set",
		1551	return isl_pw_aff_free(pwaff));
		1552	return map_from_pw_aff(pwaff);
		1553	}
		1554
		1555	/* Return a set containing those elements in the domain
		1556	* of pwaff where it is non-negative.
		1557	*/
		1558	__isl_give isl_set *isl_pw_aff_nonneg_set(__isl_take isl_pw_aff *pwaff)
		1559	{
		1560	int i;
		1561	isl_set *set;
		1562
		1563	if (!pwaff)
		1564	return NULL;
		1565
		1566	set = isl_set_empty(isl_pw_aff_get_domain_space(pwaff));
		1567
		1568	for (i = 0; i < pwaff->n; ++i) {
		1569	isl_basic_set *bset;
		1570	isl_set *set_i;
		1571
		1572	bset = isl_aff_nonneg_basic_set(isl_aff_copy(pwaff->p[i].aff));
		1573	set_i = isl_set_from_basic_set(bset);
		1574	set_i = isl_set_intersect(set_i, isl_set_copy(pwaff->p[i].set));
		1575	set = isl_set_union_disjoint(set, set_i);
		1576	}
		1577
		1578	isl_pw_aff_free(pwaff);
		1579
		1580	return set;
		1581	}
		1582
		1583	/* Return a set containing those elements in the domain
		1584	* of pwaff where it is zero (if complement is 0) or not zero
		1585	* (if complement is 1).
		1586	*/
		1587	static __isl_give isl_set *pw_aff_zero_set(__isl_take isl_pw_aff *pwaff,
		1588	int complement)
		1589	{
		1590	int i;
		1591	isl_set *set;
		1592
		1593	if (!pwaff)
		1594	return NULL;
		1595
		1596	set = isl_set_empty(isl_pw_aff_get_domain_space(pwaff));
		1597
		1598	for (i = 0; i < pwaff->n; ++i) {
		1599	isl_basic_set *bset;
		1600	isl_set *set_i, *zero;
		1601
		1602	bset = isl_aff_zero_basic_set(isl_aff_copy(pwaff->p[i].aff));
		1603	zero = isl_set_from_basic_set(bset);
		1604	set_i = isl_set_copy(pwaff->p[i].set);
		1605	if (complement)
		1606	set_i = isl_set_subtract(set_i, zero);
		1607	else
		1608	set_i = isl_set_intersect(set_i, zero);
		1609	set = isl_set_union_disjoint(set, set_i);
		1610	}
		1611
		1612	isl_pw_aff_free(pwaff);
		1613
		1614	return set;
		1615	}
		1616
		1617	/* Return a set containing those elements in the domain
		1618	* of pwaff where it is zero.
		1619	*/
		1620	__isl_give isl_set *isl_pw_aff_zero_set(__isl_take isl_pw_aff *pwaff)
		1621	{
		1622	return pw_aff_zero_set(pwaff, 0);
		1623	}
		1624
		1625	/* Return a set containing those elements in the domain
		1626	* of pwaff where it is not zero.
		1627	*/
		1628	__isl_give isl_set *isl_pw_aff_non_zero_set(__isl_take isl_pw_aff *pwaff)
		1629	{
		1630	return pw_aff_zero_set(pwaff, 1);
		1631	}
		1632
		1633	/* Return a set containing those elements in the shared domain
		1634	* of pwaff1 and pwaff2 where pwaff1 is greater than (or equal) to pwaff2.
		1635	*
		1636	* We compute the difference on the shared domain and then construct
		1637	* the set of values where this difference is non-negative.
		1638	* If strict is set, we first subtract 1 from the difference.
		1639	* If equal is set, we only return the elements where pwaff1 and pwaff2
		1640	* are equal.
		1641	*/
		1642	static __isl_give isl_set *pw_aff_gte_set(__isl_take isl_pw_aff *pwaff1,
		1643	__isl_take isl_pw_aff *pwaff2, int strict, int equal)
		1644	{
		1645	isl_set *set1, *set2;
		1646
		1647	set1 = isl_pw_aff_domain(isl_pw_aff_copy(pwaff1));
		1648	set2 = isl_pw_aff_domain(isl_pw_aff_copy(pwaff2));
		1649	set1 = isl_set_intersect(set1, set2);
		1650	pwaff1 = isl_pw_aff_intersect_domain(pwaff1, isl_set_copy(set1));
		1651	pwaff2 = isl_pw_aff_intersect_domain(pwaff2, isl_set_copy(set1));
		1652	pwaff1 = isl_pw_aff_add(pwaff1, isl_pw_aff_neg(pwaff2));
		1653
		1654	if (strict) {
		1655	isl_space *dim = isl_set_get_space(set1);
		1656	isl_aff *aff;
		1657	aff = isl_aff_zero_on_domain(isl_local_space_from_space(dim));
		1658	aff = isl_aff_add_constant_si(aff, -1);
		1659	pwaff1 = isl_pw_aff_add(pwaff1, isl_pw_aff_alloc(set1, aff));
		1660	} else
		1661	isl_set_free(set1);
		1662
		1663	if (equal)
		1664	return isl_pw_aff_zero_set(pwaff1);
		1665	return isl_pw_aff_nonneg_set(pwaff1);
		1666	}
		1667
		1668	/* Return a set containing those elements in the shared domain
		1669	* of pwaff1 and pwaff2 where pwaff1 is equal to pwaff2.
		1670	*/
		1671	static __isl_give isl_set *pw_aff_eq_set(__isl_take isl_pw_aff *pwaff1,
		1672	__isl_take isl_pw_aff *pwaff2)
		1673	{
		1674	return pw_aff_gte_set(pwaff1, pwaff2, 0, 1);
		1675	}
		1676
		1677	__isl_give isl_set *isl_pw_aff_eq_set(__isl_take isl_pw_aff *pwaff1,
		1678	__isl_take isl_pw_aff *pwaff2)
		1679	{
		1680	return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_eq_set);
		1681	}
		1682
		1683	/* Return a set containing those elements in the shared domain
		1684	* of pwaff1 and pwaff2 where pwaff1 is greater than or equal to pwaff2.
		1685	*/
		1686	static __isl_give isl_set *pw_aff_ge_set(__isl_take isl_pw_aff *pwaff1,
		1687	__isl_take isl_pw_aff *pwaff2)
		1688	{
		1689	return pw_aff_gte_set(pwaff1, pwaff2, 0, 0);
		1690	}
		1691
		1692	__isl_give isl_set *isl_pw_aff_ge_set(__isl_take isl_pw_aff *pwaff1,
		1693	__isl_take isl_pw_aff *pwaff2)
		1694	{
		1695	return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_ge_set);
		1696	}
		1697
		1698	/* Return a set containing those elements in the shared domain
		1699	* of pwaff1 and pwaff2 where pwaff1 is strictly greater than pwaff2.
		1700	*/
		1701	static __isl_give isl_set *pw_aff_gt_set(__isl_take isl_pw_aff *pwaff1,
		1702	__isl_take isl_pw_aff *pwaff2)
		1703	{
		1704	return pw_aff_gte_set(pwaff1, pwaff2, 1, 0);
		1705	}
		1706
		1707	__isl_give isl_set *isl_pw_aff_gt_set(__isl_take isl_pw_aff *pwaff1,
		1708	__isl_take isl_pw_aff *pwaff2)
		1709	{
		1710	return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_gt_set);
		1711	}
		1712
		1713	__isl_give isl_set *isl_pw_aff_le_set(__isl_take isl_pw_aff *pwaff1,
		1714	__isl_take isl_pw_aff *pwaff2)
		1715	{
		1716	return isl_pw_aff_ge_set(pwaff2, pwaff1);
		1717	}
		1718
		1719	__isl_give isl_set *isl_pw_aff_lt_set(__isl_take isl_pw_aff *pwaff1,
		1720	__isl_take isl_pw_aff *pwaff2)
		1721	{
		1722	return isl_pw_aff_gt_set(pwaff2, pwaff1);
		1723	}
		1724
		1725	/* Return a set containing those elements in the shared domain
		1726	* of the elements of list1 and list2 where each element in list1
		1727	* has the relation specified by "fn" with each element in list2.
		1728	*/
		1729	static __isl_give isl_set *pw_aff_list_set(__isl_take isl_pw_aff_list *list1,
		1730	__isl_take isl_pw_aff_list *list2,
		1731	__isl_give isl_set *(*fn)(__isl_take isl_pw_aff *pwaff1,
		1732	__isl_take isl_pw_aff *pwaff2))
		1733	{
		1734	int i, j;
		1735	isl_ctx *ctx;
		1736	isl_set *set;
		1737
		1738	if (!list1 || !list2)
		1739	goto error;
		1740
		1741	ctx = isl_pw_aff_list_get_ctx(list1);
		1742	if (list1->n < 1 || list2->n < 1)
		1743	isl_die(ctx, isl_error_invalid,
		1744	"list should contain at least one element", goto error);
		1745
		1746	set = isl_set_universe(isl_pw_aff_get_domain_space(list1->p[0]));
		1747	for (i = 0; i < list1->n; ++i)
		1748	for (j = 0; j < list2->n; ++j) {
		1749	isl_set *set_ij;
		1750
		1751	set_ij = fn(isl_pw_aff_copy(list1->p[i]),
		1752	isl_pw_aff_copy(list2->p[j]));
		1753	set = isl_set_intersect(set, set_ij);
		1754	}
		1755
		1756	isl_pw_aff_list_free(list1);
		1757	isl_pw_aff_list_free(list2);
		1758	return set;
		1759	error:
		1760	isl_pw_aff_list_free(list1);
		1761	isl_pw_aff_list_free(list2);
		1762	return NULL;
		1763	}
		1764
		1765	/* Return a set containing those elements in the shared domain
		1766	* of the elements of list1 and list2 where each element in list1
		1767	* is equal to each element in list2.
		1768	*/
		1769	__isl_give isl_set *isl_pw_aff_list_eq_set(__isl_take isl_pw_aff_list *list1,
		1770	__isl_take isl_pw_aff_list *list2)
		1771	{
		1772	return pw_aff_list_set(list1, list2, &isl_pw_aff_eq_set);
		1773	}
		1774
		1775	__isl_give isl_set *isl_pw_aff_list_ne_set(__isl_take isl_pw_aff_list *list1,
		1776	__isl_take isl_pw_aff_list *list2)
		1777	{
		1778	return pw_aff_list_set(list1, list2, &isl_pw_aff_ne_set);
		1779	}
		1780
		1781	/* Return a set containing those elements in the shared domain
		1782	* of the elements of list1 and list2 where each element in list1
		1783	* is less than or equal to each element in list2.
		1784	*/
		1785	__isl_give isl_set *isl_pw_aff_list_le_set(__isl_take isl_pw_aff_list *list1,
		1786	__isl_take isl_pw_aff_list *list2)
		1787	{
		1788	return pw_aff_list_set(list1, list2, &isl_pw_aff_le_set);
		1789	}
		1790
		1791	__isl_give isl_set *isl_pw_aff_list_lt_set(__isl_take isl_pw_aff_list *list1,
		1792	__isl_take isl_pw_aff_list *list2)
		1793	{
		1794	return pw_aff_list_set(list1, list2, &isl_pw_aff_lt_set);
		1795	}
		1796
		1797	__isl_give isl_set *isl_pw_aff_list_ge_set(__isl_take isl_pw_aff_list *list1,
		1798	__isl_take isl_pw_aff_list *list2)
		1799	{
		1800	return pw_aff_list_set(list1, list2, &isl_pw_aff_ge_set);
		1801	}
		1802
		1803	__isl_give isl_set *isl_pw_aff_list_gt_set(__isl_take isl_pw_aff_list *list1,
		1804	__isl_take isl_pw_aff_list *list2)
		1805	{
		1806	return pw_aff_list_set(list1, list2, &isl_pw_aff_gt_set);
		1807	}
		1808
		1809
		1810	/* Return a set containing those elements in the shared domain
		1811	* of pwaff1 and pwaff2 where pwaff1 is not equal to pwaff2.
		1812	*/
		1813	static __isl_give isl_set *pw_aff_ne_set(__isl_take isl_pw_aff *pwaff1,
		1814	__isl_take isl_pw_aff *pwaff2)
		1815	{
		1816	isl_set *set_lt, *set_gt;
		1817
		1818	set_lt = isl_pw_aff_lt_set(isl_pw_aff_copy(pwaff1),
		1819	isl_pw_aff_copy(pwaff2));
		1820	set_gt = isl_pw_aff_gt_set(pwaff1, pwaff2);
		1821	return isl_set_union_disjoint(set_lt, set_gt);
		1822	}
		1823
		1824	__isl_give isl_set *isl_pw_aff_ne_set(__isl_take isl_pw_aff *pwaff1,
		1825	__isl_take isl_pw_aff *pwaff2)
		1826	{
		1827	return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_ne_set);
		1828	}
		1829
		1830	__isl_give isl_pw_aff *isl_pw_aff_scale_down(__isl_take isl_pw_aff *pwaff,
		1831	isl_int v)
		1832	{
		1833	int i;
		1834
		1835	if (isl_int_is_one(v))
		1836	return pwaff;
		1837	if (!isl_int_is_pos(v))
		1838	isl_die(isl_pw_aff_get_ctx(pwaff), isl_error_invalid,
		1839	"factor needs to be positive",
		1840	return isl_pw_aff_free(pwaff));
		1841	pwaff = isl_pw_aff_cow(pwaff);
		1842	if (!pwaff)
		1843	return NULL;
		1844	if (pwaff->n == 0)
		1845	return pwaff;
		1846
		1847	for (i = 0; i < pwaff->n; ++i) {
		1848	pwaff->p[i].aff = isl_aff_scale_down(pwaff->p[i].aff, v);
		1849	if (!pwaff->p[i].aff)
		1850	return isl_pw_aff_free(pwaff);
		1851	}
		1852
		1853	return pwaff;
		1854	}
		1855
		1856	__isl_give isl_pw_aff *isl_pw_aff_floor(__isl_take isl_pw_aff *pwaff)
		1857	{
		1858	int i;
		1859
		1860	pwaff = isl_pw_aff_cow(pwaff);
		1861	if (!pwaff)
		1862	return NULL;
		1863	if (pwaff->n == 0)
		1864	return pwaff;
		1865
		1866	for (i = 0; i < pwaff->n; ++i) {
		1867	pwaff->p[i].aff = isl_aff_floor(pwaff->p[i].aff);
		1868	if (!pwaff->p[i].aff)
		1869	return isl_pw_aff_free(pwaff);
		1870	}
		1871
		1872	return pwaff;
		1873	}
		1874
		1875	__isl_give isl_pw_aff *isl_pw_aff_ceil(__isl_take isl_pw_aff *pwaff)
		1876	{
		1877	int i;
		1878
		1879	pwaff = isl_pw_aff_cow(pwaff);
		1880	if (!pwaff)
		1881	return NULL;
		1882	if (pwaff->n == 0)
		1883	return pwaff;
		1884
		1885	for (i = 0; i < pwaff->n; ++i) {
		1886	pwaff->p[i].aff = isl_aff_ceil(pwaff->p[i].aff);
		1887	if (!pwaff->p[i].aff)
		1888	return isl_pw_aff_free(pwaff);
		1889	}
		1890
		1891	return pwaff;
		1892	}
		1893
		1894	/* Assuming that "cond1" and "cond2" are disjoint,
		1895	* return an affine expression that is equal to pwaff1 on cond1
		1896	* and to pwaff2 on cond2.
		1897	*/
		1898	static __isl_give isl_pw_aff *isl_pw_aff_select(
		1899	__isl_take isl_set *cond1, __isl_take isl_pw_aff *pwaff1,
		1900	__isl_take isl_set *cond2, __isl_take isl_pw_aff *pwaff2)
		1901	{
		1902	pwaff1 = isl_pw_aff_intersect_domain(pwaff1, cond1);
		1903	pwaff2 = isl_pw_aff_intersect_domain(pwaff2, cond2);
		1904
		1905	return isl_pw_aff_add_disjoint(pwaff1, pwaff2);
		1906	}
		1907
		1908	/* Return an affine expression that is equal to pwaff_true for elements
		1909	* where "cond" is non-zero and to pwaff_false for elements where "cond"
		1910	* is zero.
		1911	* That is, return cond ? pwaff_true : pwaff_false;
		1912	*/
		1913	__isl_give isl_pw_aff *isl_pw_aff_cond(__isl_take isl_pw_aff *cond,
		1914	__isl_take isl_pw_aff *pwaff_true, __isl_take isl_pw_aff *pwaff_false)
		1915	{
		1916	isl_set *cond_true, *cond_false;
		1917
		1918	cond_true = isl_pw_aff_non_zero_set(isl_pw_aff_copy(cond));
		1919	cond_false = isl_pw_aff_zero_set(cond);
		1920	return isl_pw_aff_select(cond_true, pwaff_true,
		1921	cond_false, pwaff_false);
		1922	}
		1923
		1924	int isl_aff_is_cst(__isl_keep isl_aff *aff)
		1925	{
		1926	if (!aff)
		1927	return -1;
		1928
		1929	return isl_seq_first_non_zero(aff->v->el + 2, aff->v->size - 2) == -1;
		1930	}
		1931
		1932	/* Check whether pwaff is a piecewise constant.
		1933	*/
		1934	int isl_pw_aff_is_cst(__isl_keep isl_pw_aff *pwaff)
		1935	{
		1936	int i;
		1937
		1938	if (!pwaff)
		1939	return -1;
		1940
		1941	for (i = 0; i < pwaff->n; ++i) {
		1942	int is_cst = isl_aff_is_cst(pwaff->p[i].aff);
		1943	if (is_cst < 0 || !is_cst)
		1944	return is_cst;
		1945	}
		1946
		1947	return 1;
		1948	}
		1949
		1950	__isl_give isl_aff *isl_aff_mul(__isl_take isl_aff *aff1,
		1951	__isl_take isl_aff *aff2)
		1952	{
		1953	if (!isl_aff_is_cst(aff2) && isl_aff_is_cst(aff1))
		1954	return isl_aff_mul(aff2, aff1);
		1955
		1956	if (!isl_aff_is_cst(aff2))
		1957	isl_die(isl_aff_get_ctx(aff1), isl_error_invalid,
		1958	"at least one affine expression should be constant",
		1959	goto error);
		1960
		1961	aff1 = isl_aff_cow(aff1);
		1962	if (!aff1 || !aff2)
		1963	goto error;
		1964
		1965	aff1 = isl_aff_scale(aff1, aff2->v->el[1]);
		1966	aff1 = isl_aff_scale_down(aff1, aff2->v->el[0]);
		1967
		1968	isl_aff_free(aff2);
		1969	return aff1;
		1970	error:
		1971	isl_aff_free(aff1);
		1972	isl_aff_free(aff2);
		1973	return NULL;
		1974	}
		1975
		1976	static __isl_give isl_pw_aff *pw_aff_add(__isl_take isl_pw_aff *pwaff1,
		1977	__isl_take isl_pw_aff *pwaff2)
		1978	{
		1979	return isl_pw_aff_on_shared_domain(pwaff1, pwaff2, &isl_aff_add);
		1980	}
		1981
		1982	__isl_give isl_pw_aff *isl_pw_aff_add(__isl_take isl_pw_aff *pwaff1,
		1983	__isl_take isl_pw_aff *pwaff2)
		1984	{
		1985	return isl_pw_aff_align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_add);
		1986	}
		1987
		1988	__isl_give isl_pw_aff *isl_pw_aff_union_add(__isl_take isl_pw_aff *pwaff1,
		1989	__isl_take isl_pw_aff *pwaff2)
		1990	{
		1991	return isl_pw_aff_union_add_(pwaff1, pwaff2);
		1992	}
		1993
		1994	static __isl_give isl_pw_aff *pw_aff_mul(__isl_take isl_pw_aff *pwaff1,
		1995	__isl_take isl_pw_aff *pwaff2)
		1996	{
		1997	return isl_pw_aff_on_shared_domain(pwaff1, pwaff2, &isl_aff_mul);
		1998	}
		1999
		2000	__isl_give isl_pw_aff *isl_pw_aff_mul(__isl_take isl_pw_aff *pwaff1,
		2001	__isl_take isl_pw_aff *pwaff2)
		2002	{
		2003	return isl_pw_aff_align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_mul);
		2004	}
		2005
		2006	static __isl_give isl_pw_aff *pw_aff_min(__isl_take isl_pw_aff *pwaff1,
		2007	__isl_take isl_pw_aff *pwaff2)
		2008	{
		2009	isl_set *le;
		2010	isl_set *dom;
		2011
		2012	dom = isl_set_intersect(isl_pw_aff_domain(isl_pw_aff_copy(pwaff1)),
		2013	isl_pw_aff_domain(isl_pw_aff_copy(pwaff2)));
		2014	le = isl_pw_aff_le_set(isl_pw_aff_copy(pwaff1),
		2015	isl_pw_aff_copy(pwaff2));
		2016	dom = isl_set_subtract(dom, isl_set_copy(le));
		2017	return isl_pw_aff_select(le, pwaff1, dom, pwaff2);
		2018	}
		2019
		2020	__isl_give isl_pw_aff *isl_pw_aff_min(__isl_take isl_pw_aff *pwaff1,
		2021	__isl_take isl_pw_aff *pwaff2)
		2022	{
		2023	return isl_pw_aff_align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_min);
		2024	}
		2025
		2026	static __isl_give isl_pw_aff *pw_aff_max(__isl_take isl_pw_aff *pwaff1,
		2027	__isl_take isl_pw_aff *pwaff2)
		2028	{
		2029	isl_set *ge;
		2030	isl_set *dom;
		2031
		2032	dom = isl_set_intersect(isl_pw_aff_domain(isl_pw_aff_copy(pwaff1)),
		2033	isl_pw_aff_domain(isl_pw_aff_copy(pwaff2)));
		2034	ge = isl_pw_aff_ge_set(isl_pw_aff_copy(pwaff1),
		2035	isl_pw_aff_copy(pwaff2));
		2036	dom = isl_set_subtract(dom, isl_set_copy(ge));
		2037	return isl_pw_aff_select(ge, pwaff1, dom, pwaff2);
		2038	}
		2039
		2040	__isl_give isl_pw_aff *isl_pw_aff_max(__isl_take isl_pw_aff *pwaff1,
		2041	__isl_take isl_pw_aff *pwaff2)
		2042	{
		2043	return isl_pw_aff_align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_max);
		2044	}
		2045
		2046	static __isl_give isl_pw_aff *pw_aff_list_reduce(
		2047	__isl_take isl_pw_aff_list *list,
		2048	__isl_give isl_pw_aff *(*fn)(__isl_take isl_pw_aff *pwaff1,
		2049	__isl_take isl_pw_aff *pwaff2))
		2050	{
		2051	int i;
		2052	isl_ctx *ctx;
		2053	isl_pw_aff *res;
		2054
		2055	if (!list)
		2056	return NULL;
		2057
		2058	ctx = isl_pw_aff_list_get_ctx(list);
		2059	if (list->n < 1)
		2060	isl_die(ctx, isl_error_invalid,
		2061	"list should contain at least one element",
		2062	return isl_pw_aff_list_free(list));
		2063
		2064	res = isl_pw_aff_copy(list->p[0]);
		2065	for (i = 1; i < list->n; ++i)
		2066	res = fn(res, isl_pw_aff_copy(list->p[i]));
		2067
		2068	isl_pw_aff_list_free(list);
		2069	return res;
		2070	}
		2071
		2072	/* Return an isl_pw_aff that maps each element in the intersection of the
		2073	* domains of the elements of list to the minimal corresponding affine
		2074	* expression.
		2075	*/
		2076	__isl_give isl_pw_aff *isl_pw_aff_list_min(__isl_take isl_pw_aff_list *list)
		2077	{
		2078	return pw_aff_list_reduce(list, &isl_pw_aff_min);
		2079	}
		2080
		2081	/* Return an isl_pw_aff that maps each element in the intersection of the
		2082	* domains of the elements of list to the maximal corresponding affine
		2083	* expression.
		2084	*/
		2085	__isl_give isl_pw_aff *isl_pw_aff_list_max(__isl_take isl_pw_aff_list *list)
		2086	{
		2087	return pw_aff_list_reduce(list, &isl_pw_aff_max);
		2088	}
		2089
		2090	#undef BASE
		2091	#define BASE aff
		2092
		2093	#include <isl_multi_templ.c>
		2094
		2095	/* Construct an isl_multi_aff in the given space with value zero in
		2096	* each of the output dimensions.
		2097	*/
		2098	__isl_give isl_multi_aff *isl_multi_aff_zero(__isl_take isl_space *space)
		2099	{
		2100	int n;
		2101	isl_multi_aff *ma;
		2102
		2103	if (!space)
		2104	return NULL;
		2105
		2106	n = isl_space_dim(space , isl_dim_out);
		2107	ma = isl_multi_aff_alloc(isl_space_copy(space));
		2108
		2109	if (!n)
		2110	isl_space_free(space);
		2111	else {
		2112	int i;
		2113	isl_local_space *ls;
		2114	isl_aff *aff;
		2115
		2116	space = isl_space_domain(space);
		2117	ls = isl_local_space_from_space(space);
		2118	aff = isl_aff_zero_on_domain(ls);
		2119
		2120	for (i = 0; i < n; ++i)
		2121	ma = isl_multi_aff_set_aff(ma, i, isl_aff_copy(aff));
		2122
		2123	isl_aff_free(aff);
		2124	}
		2125
		2126	return ma;
		2127	}
		2128
		2129	/* Create an isl_pw_multi_aff with the given isl_multi_aff on a universe
		2130	* domain.
		2131	*/
		2132	__isl_give isl_pw_multi_aff *isl_pw_multi_aff_from_multi_aff(
		2133	__isl_take isl_multi_aff *ma)
		2134	{
		2135	isl_set *dom = isl_set_universe(isl_multi_aff_get_domain_space(ma));
		2136	return isl_pw_multi_aff_alloc(dom, ma);
		2137	}
		2138
		2139	__isl_give isl_multi_aff *isl_multi_aff_add(__isl_take isl_multi_aff *maff1,
		2140	__isl_take isl_multi_aff *maff2)
		2141	{
		2142	int i;
		2143	isl_ctx *ctx;
		2144
		2145	maff1 = isl_multi_aff_cow(maff1);
		2146	if (!maff1 || !maff2)
		2147	goto error;
		2148
		2149	ctx = isl_multi_aff_get_ctx(maff1);
		2150	if (!isl_space_is_equal(maff1->space, maff2->space))
		2151	isl_die(ctx, isl_error_invalid,
		2152	"spaces don't match", goto error);
		2153
		2154	for (i = 0; i < maff1->n; ++i) {
		2155	maff1->p[i] = isl_aff_add(maff1->p[i],
		2156	isl_aff_copy(maff2->p[i]));
		2157	if (!maff1->p[i])
		2158	goto error;
		2159	}
		2160
		2161	isl_multi_aff_free(maff2);
		2162	return maff1;
		2163	error:
		2164	isl_multi_aff_free(maff1);
		2165	isl_multi_aff_free(maff2);
		2166	return NULL;
		2167	}
		2168
		2169	/* Exploit the equalities in "eq" to simplify the affine expressions.
		2170	*/
		2171	static __isl_give isl_multi_aff *isl_multi_aff_substitute_equalities(
		2172	__isl_take isl_multi_aff *maff, __isl_take isl_basic_set *eq)
		2173	{
		2174	int i;
		2175
		2176	maff = isl_multi_aff_cow(maff);
		2177	if (!maff || !eq)
		2178	goto error;
		2179
		2180	for (i = 0; i < maff->n; ++i) {
		2181	maff->p[i] = isl_aff_substitute_equalities(maff->p[i],
		2182	isl_basic_set_copy(eq));
		2183	if (!maff->p[i])
		2184	goto error;
		2185	}
		2186
		2187	isl_basic_set_free(eq);
		2188	return maff;
		2189	error:
		2190	isl_basic_set_free(eq);
		2191	isl_multi_aff_free(maff);
		2192	return NULL;
		2193	}
		2194
		2195	__isl_give isl_multi_aff *isl_multi_aff_scale(__isl_take isl_multi_aff *maff,
		2196	isl_int f)
		2197	{
		2198	int i;
		2199
		2200	maff = isl_multi_aff_cow(maff);
		2201	if (!maff)
		2202	return NULL;
		2203
		2204	for (i = 0; i < maff->n; ++i) {
		2205	maff->p[i] = isl_aff_scale(maff->p[i], f);
		2206	if (!maff->p[i])
		2207	return isl_multi_aff_free(maff);
		2208	}
		2209
		2210	return maff;
		2211	}
		2212
		2213	__isl_give isl_multi_aff *isl_multi_aff_add_on_domain(__isl_keep isl_set *dom,
		2214	__isl_take isl_multi_aff *maff1, __isl_take isl_multi_aff *maff2)
		2215	{
		2216	maff1 = isl_multi_aff_add(maff1, maff2);
		2217	maff1 = isl_multi_aff_gist(maff1, isl_set_copy(dom));
		2218	return maff1;
		2219	}
		2220
		2221	int isl_multi_aff_is_empty(__isl_keep isl_multi_aff *maff)
		2222	{
		2223	if (!maff)
		2224	return -1;
		2225
		2226	return 0;
		2227	}
		2228
		2229	int isl_multi_aff_plain_is_equal(__isl_keep isl_multi_aff *maff1,
		2230	__isl_keep isl_multi_aff *maff2)
		2231	{
		2232	int i;
		2233	int equal;
		2234
		2235	if (!maff1 || !maff2)
		2236	return -1;
		2237	if (maff1->n != maff2->n)
		2238	return 0;
		2239	equal = isl_space_is_equal(maff1->space, maff2->space);
		2240	if (equal < 0 || !equal)
		2241	return equal;
		2242
		2243	for (i = 0; i < maff1->n; ++i) {
		2244	equal = isl_aff_plain_is_equal(maff1->p[i], maff2->p[i]);
		2245	if (equal < 0 || !equal)
		2246	return equal;
		2247	}
		2248
		2249	return 1;
		2250	}
		2251
		2252	__isl_give isl_multi_aff *isl_multi_aff_set_dim_name(
		2253	__isl_take isl_multi_aff *maff,
		2254	enum isl_dim_type type, unsigned pos, const char *s)
		2255	{
		2256	int i;
		2257
		2258	maff = isl_multi_aff_cow(maff);
		2259	if (!maff)
		2260	return NULL;
		2261
		2262	maff->space = isl_space_set_dim_name(maff->space, type, pos, s);
		2263	if (!maff->space)
		2264	return isl_multi_aff_free(maff);
		2265	for (i = 0; i < maff->n; ++i) {
		2266	maff->p[i] = isl_aff_set_dim_name(maff->p[i], type, pos, s);
		2267	if (!maff->p[i])
		2268	return isl_multi_aff_free(maff);
		2269	}
		2270
		2271	return maff;
		2272	}
		2273
		2274	__isl_give isl_multi_aff *isl_multi_aff_drop_dims(__isl_take isl_multi_aff *maff,
		2275	enum isl_dim_type type, unsigned first, unsigned n)
		2276	{
		2277	int i;
		2278
		2279	maff = isl_multi_aff_cow(maff);
		2280	if (!maff)
		2281	return NULL;
		2282
		2283	maff->space = isl_space_drop_dims(maff->space, type, first, n);
		2284	if (!maff->space)
		2285	return isl_multi_aff_free(maff);
		2286
		2287	if (type == isl_dim_out) {
		2288	for (i = 0; i < n; ++i)
		2289	isl_aff_free(maff->p[first + i]);
		2290	for (i = first; i + n < maff->n; ++i)
		2291	maff->p[i] = maff->p[i + n];
		2292	maff->n -= n;
		2293	return maff;
		2294	}
		2295
		2296	for (i = 0; i < maff->n; ++i) {
		2297	maff->p[i] = isl_aff_drop_dims(maff->p[i], type, first, n);
		2298	if (!maff->p[i])
		2299	return isl_multi_aff_free(maff);
		2300	}
		2301
		2302	return maff;
		2303	}
		2304
		2305	#undef PW
		2306	#define PW isl_pw_multi_aff
		2307	#undef EL
		2308	#define EL isl_multi_aff
		2309	#undef EL_IS_ZERO
		2310	#define EL_IS_ZERO is_empty
		2311	#undef ZERO
		2312	#define ZERO empty
		2313	#undef IS_ZERO
		2314	#define IS_ZERO is_empty
		2315	#undef FIELD
		2316	#define FIELD maff
		2317	#undef DEFAULT_IS_ZERO
		2318	#define DEFAULT_IS_ZERO 0
		2319
		2320	#define NO_NEG
		2321	#define NO_EVAL
		2322	#define NO_OPT
		2323	#define NO_INVOLVES_DIMS
		2324	#define NO_MOVE_DIMS
		2325	#define NO_INSERT_DIMS
		2326	#define NO_LIFT
		2327	#define NO_MORPH
		2328
		2329	#include <isl_pw_templ.c>
		2330
		2331	#undef UNION
		2332	#define UNION isl_union_pw_multi_aff
		2333	#undef PART
		2334	#define PART isl_pw_multi_aff
		2335	#undef PARTS
		2336	#define PARTS pw_multi_aff
		2337	#define ALIGN_DOMAIN
		2338
		2339	#define NO_EVAL
		2340
		2341	#include <isl_union_templ.c>
		2342
		2343	static __isl_give isl_pw_multi_aff *pw_multi_aff_add(
		2344	__isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2)
		2345	{
		2346	return isl_pw_multi_aff_on_shared_domain(pma1, pma2,
		2347	&isl_multi_aff_add);
		2348	}
		2349
		2350	__isl_give isl_pw_multi_aff *isl_pw_multi_aff_add(
		2351	__isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2)
		2352	{
		2353	return isl_pw_multi_aff_align_params_pw_pw_and(pma1, pma2,
		2354	&pw_multi_aff_add);
		2355	}
		2356
		2357	__isl_give isl_pw_multi_aff *isl_pw_multi_aff_union_add(
		2358	__isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2)
		2359	{
		2360	return isl_pw_multi_aff_union_add_(pma1, pma2);
		2361	}
		2362
		2363	/* Construct a map mapping the domain of the piecewise multi-affine expression
		2364	* to its range, with each dimension in the range equated to the
		2365	* corresponding affine expression on its cell.
		2366	*/
		2367	__isl_give isl_map *isl_map_from_pw_multi_aff(__isl_take isl_pw_multi_aff *pma)
		2368	{
		2369	int i;
		2370	isl_map *map;
		2371
		2372	if (!pma)
		2373	return NULL;
		2374
		2375	map = isl_map_empty(isl_pw_multi_aff_get_space(pma));
		2376
		2377	for (i = 0; i < pma->n; ++i) {
		2378	isl_multi_aff *maff;
		2379	isl_basic_map *bmap;
		2380	isl_map *map_i;
		2381
		2382	maff = isl_multi_aff_copy(pma->p[i].maff);
		2383	bmap = isl_basic_map_from_multi_aff(maff);
		2384	map_i = isl_map_from_basic_map(bmap);
		2385	map_i = isl_map_intersect_domain(map_i,
		2386	isl_set_copy(pma->p[i].set));
		2387	map = isl_map_union_disjoint(map, map_i);
		2388	}
		2389
		2390	isl_pw_multi_aff_free(pma);
		2391	return map;
		2392	}
		2393
		2394	__isl_give isl_set *isl_set_from_pw_multi_aff(__isl_take isl_pw_multi_aff *pma)
		2395	{
		2396	if (!isl_space_is_set(pma->dim))
		2397	isl_die(isl_pw_multi_aff_get_ctx(pma), isl_error_invalid,
		2398	"isl_pw_multi_aff cannot be converted into an isl_set",
		2399	return isl_pw_multi_aff_free(pma));
		2400
		2401	return isl_map_from_pw_multi_aff(pma);
		2402	}
		2403
		2404	/* Given a basic map with a single output dimension that is defined
		2405	* in terms of the parameters and input dimensions using an equality,
		2406	* extract an isl_aff that expresses the output dimension in terms
		2407	* of the parameters and input dimensions.
		2408	*
		2409	* Since some applications expect the result of isl_pw_multi_aff_from_map
		2410	* to only contain integer affine expressions, we compute the floor
		2411	* of the expression before returning.
		2412	*
		2413	* This function shares some similarities with
		2414	* isl_basic_map_has_defining_equality and isl_constraint_get_bound.
		2415	*/
		2416	static __isl_give isl_aff *extract_isl_aff_from_basic_map(
		2417	__isl_take isl_basic_map *bmap)
		2418	{
		2419	int i;
		2420	unsigned offset;
		2421	unsigned total;
		2422	isl_local_space *ls;
		2423	isl_aff *aff;
		2424
		2425	if (!bmap)
		2426	return NULL;
		2427	if (isl_basic_map_dim(bmap, isl_dim_out) != 1)
		2428	isl_die(isl_basic_map_get_ctx(bmap), isl_error_invalid,
		2429	"basic map should have a single output dimension",
		2430	goto error);
		2431	offset = isl_basic_map_offset(bmap, isl_dim_out);
		2432	total = isl_basic_map_total_dim(bmap);
		2433	for (i = 0; i < bmap->n_eq; ++i) {
		2434	if (isl_int_is_zero(bmap->eq[i][offset]))
		2435	continue;
		2436	if (isl_seq_first_non_zero(bmap->eq[i] + offset + 1,
		2437	1 + total - (offset + 1)) != -1)
		2438	continue;
		2439	break;
		2440	}
		2441	if (i >= bmap->n_eq)
		2442	isl_die(isl_basic_map_get_ctx(bmap), isl_error_invalid,
		2443	"unable to find suitable equality", goto error);
		2444	ls = isl_basic_map_get_local_space(bmap);
		2445	aff = isl_aff_alloc(isl_local_space_domain(ls));
		2446	if (!aff)
		2447	goto error;
		2448	if (isl_int_is_neg(bmap->eq[i][offset]))
		2449	isl_seq_cpy(aff->v->el + 1, bmap->eq[i], offset);
		2450	else
		2451	isl_seq_neg(aff->v->el + 1, bmap->eq[i], offset);
		2452	isl_seq_clr(aff->v->el + 1 + offset, aff->v->size - (1 + offset));
		2453	isl_int_abs(aff->v->el[0], bmap->eq[i][offset]);
		2454	isl_basic_map_free(bmap);
		2455
		2456	aff = isl_aff_remove_unused_divs(aff);
		2457	aff = isl_aff_floor(aff);
		2458	return aff;
		2459	error:
		2460	isl_basic_map_free(bmap);
		2461	return NULL;
		2462	}
		2463
		2464	/* Given a basic map where each output dimension is defined
		2465	* in terms of the parameters and input dimensions using an equality,
		2466	* extract an isl_multi_aff that expresses the output dimensions in terms
		2467	* of the parameters and input dimensions.
		2468	*/
		2469	static __isl_give isl_multi_aff *extract_isl_multi_aff_from_basic_map(
		2470	__isl_take isl_basic_map *bmap)
		2471	{
		2472	int i;
		2473	unsigned n_out;
		2474	isl_multi_aff *ma;
		2475
		2476	if (!bmap)
		2477	return NULL;
		2478
		2479	ma = isl_multi_aff_alloc(isl_basic_map_get_space(bmap));
		2480	n_out = isl_basic_map_dim(bmap, isl_dim_out);
		2481
		2482	for (i = 0; i < n_out; ++i) {
		2483	isl_basic_map *bmap_i;
		2484	isl_aff *aff;
		2485
		2486	bmap_i = isl_basic_map_copy(bmap);
		2487	bmap_i = isl_basic_map_project_out(bmap_i, isl_dim_out,
		2488	i + 1, n_out - (1 + i));
		2489	bmap_i = isl_basic_map_project_out(bmap_i, isl_dim_out, 0, i);
		2490	aff = extract_isl_aff_from_basic_map(bmap_i);
		2491	ma = isl_multi_aff_set_aff(ma, i, aff);
		2492	}
		2493
		2494	isl_basic_map_free(bmap);
		2495
		2496	return ma;
		2497	}
		2498
		2499	/* Create an isl_pw_multi_aff that is equivalent to
		2500	* isl_map_intersect_domain(isl_map_from_basic_map(bmap), domain).
		2501	* The given basic map is such that each output dimension is defined
		2502	* in terms of the parameters and input dimensions using an equality.
		2503	*/
		2504	static __isl_give isl_pw_multi_aff *plain_pw_multi_aff_from_map(
		2505	__isl_take isl_set *domain, __isl_take isl_basic_map *bmap)
		2506	{
		2507	isl_multi_aff *ma;
		2508
		2509	ma = extract_isl_multi_aff_from_basic_map(bmap);
		2510	return isl_pw_multi_aff_alloc(domain, ma);
		2511	}
		2512
		2513	/* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map.
		2514	* This obivously only works if the input "map" is single-valued.
		2515	* If so, we compute the lexicographic minimum of the image in the form
		2516	* of an isl_pw_multi_aff. Since the image is unique, it is equal
		2517	* to its lexicographic minimum.
		2518	* If the input is not single-valued, we produce an error.
		2519	*
		2520	* As a special case, we first check if all output dimensions are uniquely
		2521	* defined in terms of the parameters and input dimensions over the entire
		2522	* domain. If so, we extract the desired isl_pw_multi_aff directly
		2523	* from the affine hull of "map" and its domain.
		2524	*/
		2525	__isl_give isl_pw_multi_aff *isl_pw_multi_aff_from_map(__isl_take isl_map *map)
		2526	{
		2527	int i;
		2528	int sv;
		2529	isl_pw_multi_aff *pma;
		2530	isl_basic_map *hull;
		2531
		2532	if (!map)
		2533	return NULL;
		2534
		2535	hull = isl_map_affine_hull(isl_map_copy(map));
		2536	sv = isl_basic_map_plain_is_single_valued(hull);
		2537	if (sv >= 0 && sv)
		2538	return plain_pw_multi_aff_from_map(isl_map_domain(map), hull);
		2539	isl_basic_map_free(hull);
		2540	if (sv < 0)
		2541	goto error;
		2542
		2543	sv = isl_map_is_single_valued(map);
		2544	if (sv < 0)
		2545	goto error;
		2546	if (!sv)
		2547	isl_die(isl_map_get_ctx(map), isl_error_invalid,
		2548	"map is not single-valued", goto error);
		2549	map = isl_map_make_disjoint(map);
		2550	if (!map)
		2551	return NULL;
		2552
		2553	pma = isl_pw_multi_aff_empty(isl_map_get_space(map));
		2554
		2555	for (i = 0; i < map->n; ++i) {
		2556	isl_pw_multi_aff *pma_i;
		2557	isl_basic_map *bmap;
		2558	bmap = isl_basic_map_copy(map->p[i]);
		2559	pma_i = isl_basic_map_lexmin_pw_multi_aff(bmap);
		2560	pma = isl_pw_multi_aff_add_disjoint(pma, pma_i);
		2561	}
		2562
		2563	isl_map_free(map);
		2564	return pma;
		2565	error:
		2566	isl_map_free(map);
		2567	return NULL;
		2568	}
		2569
		2570	__isl_give isl_pw_multi_aff *isl_pw_multi_aff_from_set(__isl_take isl_set *set)
		2571	{
		2572	return isl_pw_multi_aff_from_map(set);
		2573	}
		2574
		2575	/* Return the piecewise affine expression "set ? 1 : 0".
		2576	*/
		2577	__isl_give isl_pw_aff *isl_set_indicator_function(__isl_take isl_set *set)
		2578	{
		2579	isl_pw_aff *pa;
		2580	isl_space *space = isl_set_get_space(set);
		2581	isl_local_space *ls = isl_local_space_from_space(space);
		2582	isl_aff *zero = isl_aff_zero_on_domain(isl_local_space_copy(ls));
		2583	isl_aff *one = isl_aff_zero_on_domain(ls);
		2584
		2585	one = isl_aff_add_constant_si(one, 1);
		2586	pa = isl_pw_aff_alloc(isl_set_copy(set), one);
		2587	set = isl_set_complement(set);
		2588	pa = isl_pw_aff_add_disjoint(pa, isl_pw_aff_alloc(set, zero));
		2589
		2590	return pa;
		2591	}
		2592
		2593	/* Plug in "subs" for dimension "type", "pos" of "aff".
		2594	*
		2595	* Let i be the dimension to replace and let "subs" be of the form
		2596	*
		2597	* f/d
		2598	*
		2599	* and "aff" of the form
		2600	*
		2601	* (a i + g)/m
		2602	*
		2603	* The result is
		2604	*
		2605	* floor((a f + d g')/(m d))
		2606	*
		2607	* where g' is the result of plugging in "subs" in each of the integer
		2608	* divisions in g.
		2609	*/
		2610	__isl_give isl_aff *isl_aff_substitute(__isl_take isl_aff *aff,
		2611	enum isl_dim_type type, unsigned pos, __isl_keep isl_aff *subs)
		2612	{
		2613	isl_ctx *ctx;
		2614	isl_int v;
		2615
		2616	aff = isl_aff_cow(aff);
		2617	if (!aff || !subs)
		2618	return isl_aff_free(aff);
		2619
		2620	ctx = isl_aff_get_ctx(aff);
		2621	if (!isl_space_is_equal(aff->ls->dim, subs->ls->dim))
		2622	isl_die(ctx, isl_error_invalid,
		2623	"spaces don't match", return isl_aff_free(aff));
		2624	if (isl_local_space_dim(subs->ls, isl_dim_div) != 0)
		2625	isl_die(ctx, isl_error_unsupported,
		2626	"cannot handle divs yet", return isl_aff_free(aff));
		2627
		2628	aff->ls = isl_local_space_substitute(aff->ls, type, pos, subs);
		2629	if (!aff->ls)
		2630	return isl_aff_free(aff);
		2631
		2632	aff->v = isl_vec_cow(aff->v);
		2633	if (!aff->v)
		2634	return isl_aff_free(aff);
		2635
		2636	pos += isl_local_space_offset(aff->ls, type);
		2637
		2638	isl_int_init(v);
		2639	isl_int_set(v, aff->v->el[1 + pos]);
		2640	isl_int_set_si(aff->v->el[1 + pos], 0);
		2641	isl_seq_combine(aff->v->el + 1, subs->v->el[0], aff->v->el + 1,
		2642	v, subs->v->el + 1, subs->v->size - 1);
		2643	isl_int_mul(aff->v->el[0], aff->v->el[0], subs->v->el[0]);
		2644	isl_int_clear(v);
		2645
		2646	return aff;
		2647	}
		2648
		2649	/* Plug in "subs" for dimension "type", "pos" in each of the affine
		2650	* expressions in "maff".
		2651	*/
		2652	__isl_give isl_multi_aff *isl_multi_aff_substitute(
		2653	__isl_take isl_multi_aff *maff, enum isl_dim_type type, unsigned pos,
		2654	__isl_keep isl_aff *subs)
		2655	{
		2656	int i;
		2657
		2658	maff = isl_multi_aff_cow(maff);
		2659	if (!maff || !subs)
		2660	return isl_multi_aff_free(maff);
		2661
		2662	if (type == isl_dim_in)
		2663	type = isl_dim_set;
		2664
		2665	for (i = 0; i < maff->n; ++i) {
		2666	maff->p[i] = isl_aff_substitute(maff->p[i], type, pos, subs);
		2667	if (!maff->p[i])
		2668	return isl_multi_aff_free(maff);
		2669	}
		2670
		2671	return maff;
		2672	}
		2673
		2674	/* Plug in "subs" for dimension "type", "pos" of "pma".
		2675	*
		2676	* pma is of the form
		2677	*
		2678	* A_i(v) -> M_i(v)
		2679	*
		2680	* while subs is of the form
		2681	*
		2682	* v' = B_j(v) -> S_j
		2683	*
		2684	* Each pair i,j such that C_ij = A_i \cap B_i is non-empty
		2685	* has a contribution in the result, in particular
		2686	*
		2687	* C_ij(S_j) -> M_i(S_j)
		2688	*
		2689	* Note that plugging in S_j in C_ij may also result in an empty set
		2690	* and this contribution should simply be discarded.
		2691	*/
		2692	__isl_give isl_pw_multi_aff *isl_pw_multi_aff_substitute(
		2693	__isl_take isl_pw_multi_aff *pma, enum isl_dim_type type, unsigned pos,
		2694	__isl_keep isl_pw_aff *subs)
		2695	{
		2696	int i, j, n;
		2697	isl_pw_multi_aff *res;
		2698
		2699	if (!pma || !subs)
		2700	return isl_pw_multi_aff_free(pma);
		2701
		2702	n = pma->n * subs->n;
		2703	res = isl_pw_multi_aff_alloc_size(isl_space_copy(pma->dim), n);
		2704
		2705	for (i = 0; i < pma->n; ++i) {
		2706	for (j = 0; j < subs->n; ++j) {
		2707	isl_set *common;
		2708	isl_multi_aff *res_ij;
		2709	common = isl_set_intersect(
		2710	isl_set_copy(pma->p[i].set),
		2711	isl_set_copy(subs->p[j].set));
		2712	common = isl_set_substitute(common,
		2713	type, pos, subs->p[j].aff);
		2714	if (isl_set_plain_is_empty(common)) {
		2715	isl_set_free(common);
		2716	continue;
		2717	}
		2718
		2719	res_ij = isl_multi_aff_substitute(
		2720	isl_multi_aff_copy(pma->p[i].maff),
		2721	type, pos, subs->p[j].aff);
		2722
		2723	res = isl_pw_multi_aff_add_piece(res, common, res_ij);
		2724	}
		2725	}
		2726
		2727	isl_pw_multi_aff_free(pma);
		2728	return res;
		2729	}
		2730
		2731	/* Extend the local space of "dst" to include the divs
		2732	* in the local space of "src".
		2733	*/
		2734	__isl_give isl_aff *isl_aff_align_divs(__isl_take isl_aff *dst,
		2735	__isl_keep isl_aff *src)
		2736	{
		2737	isl_ctx *ctx;
		2738	int *exp1 = NULL;
		2739	int *exp2 = NULL;
		2740	isl_mat *div;
		2741
		2742	if (!src || !dst)
		2743	return isl_aff_free(dst);
		2744
		2745	ctx = isl_aff_get_ctx(src);
		2746	if (!isl_space_is_equal(src->ls->dim, dst->ls->dim))
		2747	isl_die(ctx, isl_error_invalid,
		2748	"spaces don't match", goto error);
		2749
		2750	if (src->ls->div->n_row == 0)
		2751	return dst;
		2752
		2753	exp1 = isl_alloc_array(ctx, int, src->ls->div->n_row);
		2754	exp2 = isl_alloc_array(ctx, int, dst->ls->div->n_row);
		2755	if (!exp1 || !exp2)
		2756	goto error;
		2757
		2758	div = isl_merge_divs(src->ls->div, dst->ls->div, exp1, exp2);
		2759	dst = isl_aff_expand_divs(dst, div, exp2);
		2760	free(exp1);
		2761	free(exp2);
		2762
		2763	return dst;
		2764	error:
		2765	free(exp1);
		2766	free(exp2);
		2767	return isl_aff_free(dst);
		2768	}
		2769
		2770	/* Adjust the local spaces of the affine expressions in "maff"
		2771	* such that they all have the save divs.
		2772	*/
		2773	__isl_give isl_multi_aff *isl_multi_aff_align_divs(
		2774	__isl_take isl_multi_aff *maff)
		2775	{
		2776	int i;
		2777
		2778	if (!maff)
		2779	return NULL;
		2780	if (maff->n == 0)
		2781	return maff;
		2782	maff = isl_multi_aff_cow(maff);
		2783	if (!maff)
		2784	return NULL;
		2785
		2786	for (i = 1; i < maff->n; ++i)
		2787	maff->p[0] = isl_aff_align_divs(maff->p[0], maff->p[i]);
		2788	for (i = 1; i < maff->n; ++i) {
		2789	maff->p[i] = isl_aff_align_divs(maff->p[i], maff->p[0]);
		2790	if (!maff->p[i])
		2791	return isl_multi_aff_free(maff);
		2792	}
		2793
		2794	return maff;
		2795	}
		2796
		2797	__isl_give isl_aff *isl_aff_lift(__isl_take isl_aff *aff)
		2798	{
		2799	aff = isl_aff_cow(aff);
		2800	if (!aff)
		2801	return NULL;
		2802
		2803	aff->ls = isl_local_space_lift(aff->ls);
		2804	if (!aff->ls)
		2805	return isl_aff_free(aff);
		2806
		2807	return aff;
		2808	}
		2809
		2810	/* Lift "maff" to a space with extra dimensions such that the result
		2811	* has no more existentially quantified variables.
		2812	* If "ls" is not NULL, then *ls is assigned the local space that lies
		2813	* at the basis of the lifting applied to "maff".
		2814	*/
		2815	__isl_give isl_multi_aff *isl_multi_aff_lift(__isl_take isl_multi_aff *maff,
		2816	__isl_give isl_local_space **ls)
		2817	{
		2818	int i;
		2819	isl_space *space;
		2820	unsigned n_div;
		2821
		2822	if (ls)
		2823	*ls = NULL;
		2824
		2825	if (!maff)
		2826	return NULL;
		2827
		2828	if (maff->n == 0) {
		2829	if (ls) {
		2830	isl_space *space = isl_multi_aff_get_domain_space(maff);
		2831	*ls = isl_local_space_from_space(space);
		2832	if (!*ls)
		2833	return isl_multi_aff_free(maff);
		2834	}
		2835	return maff;
		2836	}
		2837
		2838	maff = isl_multi_aff_cow(maff);
		2839	maff = isl_multi_aff_align_divs(maff);
		2840	if (!maff)
		2841	return NULL;
		2842
		2843	n_div = isl_aff_dim(maff->p[0], isl_dim_div);
		2844	space = isl_multi_aff_get_space(maff);
		2845	space = isl_space_lift(isl_space_domain(space), n_div);
		2846	space = isl_space_extend_domain_with_range(space,
		2847	isl_multi_aff_get_space(maff));
		2848	if (!space)
		2849	return isl_multi_aff_free(maff);
		2850	isl_space_free(maff->space);
		2851	maff->space = space;
		2852
		2853	if (ls) {
		2854	*ls = isl_aff_get_domain_local_space(maff->p[0]);
		2855	if (!*ls)
		2856	return isl_multi_aff_free(maff);
		2857	}
		2858
		2859	for (i = 0; i < maff->n; ++i) {
		2860	maff->p[i] = isl_aff_lift(maff->p[i]);
		2861	if (!maff->p[i])
		2862	goto error;
		2863	}
		2864
		2865	return maff;
		2866	error:
		2867	if (ls)
		2868	isl_local_space_free(*ls);
		2869	return isl_multi_aff_free(maff);
		2870	}
		2871
		2872
		2873	/* Extract an isl_pw_aff corresponding to output dimension "pos" of "pma".
		2874	*/
		2875	__isl_give isl_pw_aff *isl_pw_multi_aff_get_pw_aff(
		2876	__isl_keep isl_pw_multi_aff *pma, int pos)
		2877	{
		2878	int i;
		2879	int n_out;
		2880	isl_space *space;
		2881	isl_pw_aff *pa;
		2882
		2883	if (!pma)
		2884	return NULL;
		2885
		2886	n_out = isl_pw_multi_aff_dim(pma, isl_dim_out);
		2887	if (pos < 0 || pos >= n_out)
		2888	isl_die(isl_pw_multi_aff_get_ctx(pma), isl_error_invalid,
		2889	"index out of bounds", return NULL);
		2890
		2891	space = isl_pw_multi_aff_get_space(pma);
		2892	space = isl_space_drop_dims(space, isl_dim_out,
		2893	pos + 1, n_out - pos - 1);
		2894	space = isl_space_drop_dims(space, isl_dim_out, 0, pos);
		2895
		2896	pa = isl_pw_aff_alloc_size(space, pma->n);
		2897	for (i = 0; i < pma->n; ++i) {
		2898	isl_aff *aff;
		2899	aff = isl_multi_aff_get_aff(pma->p[i].maff, pos);
		2900	pa = isl_pw_aff_add_piece(pa, isl_set_copy(pma->p[i].set), aff);
		2901	}
		2902
		2903	return pa;
		2904	}
		2905
		2906	/* Return an isl_pw_multi_aff with the given "set" as domain and
		2907	* an unnamed zero-dimensional range.
		2908	*/
		2909	__isl_give isl_pw_multi_aff *isl_pw_multi_aff_from_domain(
		2910	__isl_take isl_set *set)
		2911	{
		2912	isl_multi_aff *ma;
		2913	isl_space *space;
		2914
		2915	space = isl_set_get_space(set);
		2916	space = isl_space_from_domain(space);
		2917	ma = isl_multi_aff_zero(space);
		2918	return isl_pw_multi_aff_alloc(set, ma);
		2919	}
		2920
		2921	/* Add an isl_pw_multi_aff with the given "set" as domain and
		2922	* an unnamed zero-dimensional range to *user.
		2923	*/
		2924	static int add_pw_multi_aff_from_domain(__isl_take isl_set *set, void *user)
		2925	{
		2926	isl_union_pw_multi_aff **upma = user;
		2927	isl_pw_multi_aff *pma;
		2928
		2929	pma = isl_pw_multi_aff_from_domain(set);
		2930	*upma = isl_union_pw_multi_aff_add_pw_multi_aff(*upma, pma);
		2931
		2932	return 0;
		2933	}
		2934
		2935	/* Return an isl_union_pw_multi_aff with the given "uset" as domain and
		2936	* an unnamed zero-dimensional range.
		2937	*/
		2938	__isl_give isl_union_pw_multi_aff *isl_union_pw_multi_aff_from_domain(
		2939	__isl_take isl_union_set *uset)
		2940	{
		2941	isl_space *space;
		2942	isl_union_pw_multi_aff *upma;
		2943
		2944	if (!uset)
		2945	return NULL;
		2946
		2947	space = isl_union_set_get_space(uset);
		2948	upma = isl_union_pw_multi_aff_empty(space);
		2949
		2950	if (isl_union_set_foreach_set(uset,
		2951	&add_pw_multi_aff_from_domain, &upma) < 0)
		2952	goto error;
		2953
		2954	isl_union_set_free(uset);
		2955	return upma;
		2956	error:
		2957	isl_union_set_free(uset);
		2958	isl_union_pw_multi_aff_free(upma);
		2959	return NULL;
		2960	}
		2961
		2962	/* Convert "pma" to an isl_map and add it to *umap.
		2963	*/
		2964	static int map_from_pw_multi_aff(__isl_take isl_pw_multi_aff *pma, void *user)
		2965	{
		2966	isl_union_map **umap = user;
		2967	isl_map *map;
		2968
		2969	map = isl_map_from_pw_multi_aff(pma);
		2970	*umap = isl_union_map_add_map(*umap, map);
		2971
		2972	return 0;
		2973	}
		2974
		2975	/* Construct a union map mapping the domain of the union
		2976	* piecewise multi-affine expression to its range, with each dimension
		2977	* in the range equated to the corresponding affine expression on its cell.
		2978	*/
		2979	__isl_give isl_union_map *isl_union_map_from_union_pw_multi_aff(
		2980	__isl_take isl_union_pw_multi_aff *upma)
		2981	{
		2982	isl_space *space;
		2983	isl_union_map *umap;
		2984
		2985	if (!upma)
		2986	return NULL;
		2987
		2988	space = isl_union_pw_multi_aff_get_space(upma);
		2989	umap = isl_union_map_empty(space);
		2990
		2991	if (isl_union_pw_multi_aff_foreach_pw_multi_aff(upma,
		2992	&map_from_pw_multi_aff, &umap) < 0)
		2993	goto error;
		2994
		2995	isl_union_pw_multi_aff_free(upma);
		2996	return umap;
		2997	error:
		2998	isl_union_pw_multi_aff_free(upma);
		2999	isl_union_map_free(umap);
		3000	return NULL;
		3001	}
		3002
		3003	/* Local data for bin_entry and the callback "fn".
		3004	*/
		3005	struct isl_union_pw_multi_aff_bin_data {
		3006	isl_union_pw_multi_aff *upma2;
		3007	isl_union_pw_multi_aff *res;
		3008	isl_pw_multi_aff *pma;
		3009	int (*fn)(void **entry, void *user);
		3010	};
		3011
		3012	/* Given an isl_pw_multi_aff from upma1, store it in data->pma
		3013	* and call data->fn for each isl_pw_multi_aff in data->upma2.
		3014	*/
		3015	static int bin_entry(void **entry, void *user)
		3016	{
		3017	struct isl_union_pw_multi_aff_bin_data *data = user;
		3018	isl_pw_multi_aff *pma = *entry;
		3019
		3020	data->pma = pma;
		3021	if (isl_hash_table_foreach(data->upma2->dim->ctx, &data->upma2->table,
		3022	data->fn, data) < 0)
		3023	return -1;
		3024
		3025	return 0;
		3026	}
		3027
		3028	/* Call "fn" on each pair of isl_pw_multi_affs in "upma1" and "upma2".
		3029	* The isl_pw_multi_aff from upma1 is stored in data->pma (where data is
		3030	* passed as user field) and the isl_pw_multi_aff from upma2 is available
		3031	* as *entry. The callback should adjust data->res if desired.
		3032	*/
		3033	static __isl_give isl_union_pw_multi_aff *bin_op(
		3034	__isl_take isl_union_pw_multi_aff *upma1,
		3035	__isl_take isl_union_pw_multi_aff *upma2,
		3036	int (*fn)(void **entry, void *user))
		3037	{
		3038	isl_space *space;
		3039	struct isl_union_pw_multi_aff_bin_data data = { NULL, NULL, NULL, fn };
		3040
		3041	space = isl_union_pw_multi_aff_get_space(upma2);
		3042	upma1 = isl_union_pw_multi_aff_align_params(upma1, space);
		3043	space = isl_union_pw_multi_aff_get_space(upma1);
		3044	upma2 = isl_union_pw_multi_aff_align_params(upma2, space);
		3045
		3046	if (!upma1 || !upma2)
		3047	goto error;
		3048
		3049	data.upma2 = upma2;
		3050	data.res = isl_union_pw_multi_aff_alloc(isl_space_copy(upma1->dim),
		3051	upma1->table.n);
		3052	if (isl_hash_table_foreach(upma1->dim->ctx, &upma1->table,
		3053	&bin_entry, &data) < 0)
		3054	goto error;
		3055
		3056	isl_union_pw_multi_aff_free(upma1);
		3057	isl_union_pw_multi_aff_free(upma2);
		3058	return data.res;
		3059	error:
		3060	isl_union_pw_multi_aff_free(upma1);
		3061	isl_union_pw_multi_aff_free(upma2);
		3062	isl_union_pw_multi_aff_free(data.res);
		3063	return NULL;
		3064	}
		3065
		3066	/* Given two isl_multi_affs A -> B and C -> D,
		3067	* construct an isl_multi_aff (A * C) -> (B, D).
		3068	*/
		3069	__isl_give isl_multi_aff *isl_multi_aff_flat_range_product(
		3070	__isl_take isl_multi_aff *ma1, __isl_take isl_multi_aff *ma2)
		3071	{
		3072	int i, n1, n2;
		3073	isl_aff *aff;
		3074	isl_space *space;
		3075	isl_multi_aff *res;
		3076
		3077	if (!ma1 || !ma2)
		3078	goto error;
		3079
		3080	space = isl_space_range_product(isl_multi_aff_get_space(ma1),
		3081	isl_multi_aff_get_space(ma2));
		3082	space = isl_space_flatten_range(space);
		3083	res = isl_multi_aff_alloc(space);
		3084
		3085	n1 = isl_multi_aff_dim(ma1, isl_dim_out);
		3086	n2 = isl_multi_aff_dim(ma2, isl_dim_out);
		3087
		3088	for (i = 0; i < n1; ++i) {
		3089	aff = isl_multi_aff_get_aff(ma1, i);
		3090	res = isl_multi_aff_set_aff(res, i, aff);
		3091	}
		3092
		3093	for (i = 0; i < n2; ++i) {
		3094	aff = isl_multi_aff_get_aff(ma2, i);
		3095	res = isl_multi_aff_set_aff(res, n1 + i, aff);
		3096	}
		3097
		3098	isl_multi_aff_free(ma1);
		3099	isl_multi_aff_free(ma2);
		3100	return res;
		3101	error:
		3102	isl_multi_aff_free(ma1);
		3103	isl_multi_aff_free(ma2);
		3104	return NULL;
		3105	}
		3106
		3107	/* Given two aligned isl_pw_multi_affs A -> B and C -> D,
		3108	* construct an isl_pw_multi_aff (A * C) -> (B, D).
		3109	*/
		3110	static __isl_give isl_pw_multi_aff *pw_multi_aff_flat_range_product(
		3111	__isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2)
		3112	{
		3113	isl_space *space;
		3114
		3115	space = isl_space_range_product(isl_pw_multi_aff_get_space(pma1),
		3116	isl_pw_multi_aff_get_space(pma2));
		3117	space = isl_space_flatten_range(space);
		3118	return isl_pw_multi_aff_on_shared_domain_in(pma1, pma2, space,
		3119	&isl_multi_aff_flat_range_product);
		3120	}
		3121
		3122	/* Given two isl_pw_multi_affs A -> B and C -> D,
		3123	* construct an isl_pw_multi_aff (A * C) -> (B, D).
		3124	*/
		3125	__isl_give isl_pw_multi_aff *isl_pw_multi_aff_flat_range_product(
		3126	__isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2)
		3127	{
		3128	return isl_pw_multi_aff_align_params_pw_pw_and(pma1, pma2,
		3129	&pw_multi_aff_flat_range_product);
		3130	}
		3131
		3132	/* If data->pma and *entry have the same domain space, then compute
		3133	* their flat range product and the result to data->res.
		3134	*/
		3135	static int flat_range_product_entry(void **entry, void *user)
		3136	{
		3137	struct isl_union_pw_multi_aff_bin_data *data = user;
		3138	isl_pw_multi_aff *pma2 = *entry;
		3139
		3140	if (!isl_space_tuple_match(data->pma->dim, isl_dim_in,
		3141	pma2->dim, isl_dim_in))
		3142	return 0;
		3143
		3144	pma2 = isl_pw_multi_aff_flat_range_product(
		3145	isl_pw_multi_aff_copy(data->pma),
		3146	isl_pw_multi_aff_copy(pma2));
		3147
		3148	data->res = isl_union_pw_multi_aff_add_pw_multi_aff(data->res, pma2);
		3149
		3150	return 0;
		3151	}
		3152
		3153	/* Given two isl_union_pw_multi_affs A -> B and C -> D,
		3154	* construct an isl_union_pw_multi_aff (A * C) -> (B, D).
		3155	*/
		3156	__isl_give isl_union_pw_multi_aff *isl_union_pw_multi_aff_flat_range_product(
		3157	__isl_take isl_union_pw_multi_aff *upma1,
		3158	__isl_take isl_union_pw_multi_aff *upma2)
		3159	{
		3160	return bin_op(upma1, upma2, &flat_range_product_entry);
		3161	}