1	/*
2	* Copyright 2008-2009 Katholieke Universiteit Leuven
3	* Copyright 2010 INRIA Saclay
4	* Copyright 2012-2013 Ecole Normale Superieure
5	* Copyright 2014 INRIA Rocquencourt
6	* Copyright 2016 INRIA Paris
7	* Copyright 2020 Cerebras Systems
8	*
9	* Use of this software is governed by the MIT license
10	*
11	* Written by Sven Verdoolaege, K.U.Leuven, Departement
12	* Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
13	* and INRIA Saclay - Ile-de-France, Parc Club Orsay Universite,
14	* ZAC des vignes, 4 rue Jacques Monod, 91893 Orsay, France
15	* and Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
16	* and Inria Paris - Rocquencourt, Domaine de Voluceau - Rocquencourt,
17	* B.P. 105 - 78153 Le Chesnay, France
18	* and Centre de Recherche Inria de Paris, 2 rue Simone Iff - Voie DQ12,
19	* CS 42112, 75589 Paris Cedex 12, France
20	* and Cerebras Systems, 175 S San Antonio Rd, Los Altos, CA, USA
21	*/
22
23	#include <isl_ctx_private.h>
24	#include "isl_map_private.h"
25	#include <isl_seq.h>
26	#include <isl/options.h>
27	#include "isl_tab.h"
28	#include <isl_mat_private.h>
29	#include <isl_local_space_private.h>
30	#include <isl_val_private.h>
31	#include <isl_vec_private.h>
32	#include <isl_aff_private.h>
33	#include <isl_equalities.h>
34	#include <isl_constraint_private.h>
35
36	#include <set_to_map.c>
37	#include <set_from_map.c>
38
39	#define STATUS_ERROR -1
40	#define STATUS_REDUNDANT 1
41	#define STATUS_VALID 2
42	#define STATUS_SEPARATE 3
43	#define STATUS_CUT 4
44	#define STATUS_ADJ_EQ 5
45	#define STATUS_ADJ_INEQ 6
46
47	static int status_in(isl_int *ineq, struct isl_tab *tab)
48	{
49	enum isl_ineq_type type = isl_tab_ineq_type(tab, ineq);
50	switch (type) {
51	default:
52	case isl_ineq_error: return STATUS_ERROR;
53	case isl_ineq_redundant: return STATUS_VALID;
54	case isl_ineq_separate: return STATUS_SEPARATE;
55	case isl_ineq_cut: return STATUS_CUT;
56	case isl_ineq_adj_eq: return STATUS_ADJ_EQ;
57	case isl_ineq_adj_ineq: return STATUS_ADJ_INEQ;
58	}
59	}
60
61	/* Compute the position of the equalities of basic map "bmap_i"
62	* with respect to the basic map represented by "tab_j".
63	* The resulting array has twice as many entries as the number
64	* of equalities corresponding to the two inequalities to which
65	* each equality corresponds.
66	*/
67	static int *eq_status_in(__isl_keep isl_basic_map *bmap_i,
68	struct isl_tab *tab_j)
69	{
70	int k, l;
71	int *eq;
72	isl_size dim;
73
74	dim = isl_basic_map_dim(bmap: bmap_i, type: isl_dim_all);
75	if (dim < 0)
76	return NULL;
77
78	eq = isl_calloc_array(bmap_i->ctx, int, 2 * bmap_i->n_eq);
79	if (!eq)
80	return NULL;
81
82	for (k = 0; k < bmap_i->n_eq; ++k) {
83	for (l = 0; l < 2; ++l) {
84	isl_seq_neg(dst: bmap_i->eq[k], src: bmap_i->eq[k], len: 1+dim);
85	eq[2 * k + l] = status_in(ineq: bmap_i->eq[k], tab: tab_j);
86	if (eq[2 * k + l] == STATUS_ERROR)
87	goto error;
88	}
89	}
90
91	return eq;
92	error:
93	free(ptr: eq);
94	return NULL;
95	}
96
97	/* Compute the position of the inequalities of basic map "bmap_i"
98	* (also represented by "tab_i", if not NULL) with respect to the basic map
99	* represented by "tab_j".
100	*/
101	static int *ineq_status_in(__isl_keep isl_basic_map *bmap_i,
102	struct isl_tab *tab_i, struct isl_tab *tab_j)
103	{
104	int k;
105	unsigned n_eq = bmap_i->n_eq;
106	int *ineq = isl_calloc_array(bmap_i->ctx, int, bmap_i->n_ineq);
107
108	if (!ineq)
109	return NULL;
110
111	for (k = 0; k < bmap_i->n_ineq; ++k) {
112	if (tab_i && isl_tab_is_redundant(tab: tab_i, con: n_eq + k)) {
113	ineq[k] = STATUS_REDUNDANT;
114	continue;
115	}
116	ineq[k] = status_in(ineq: bmap_i->ineq[k], tab: tab_j);
117	if (ineq[k] == STATUS_ERROR)
118	goto error;
119	if (ineq[k] == STATUS_SEPARATE)
120	break;
121	}
122
123	return ineq;
124	error:
125	free(ptr: ineq);
126	return NULL;
127	}
128
129	static int any(int *con, unsigned len, int status)
130	{
131	int i;
132
133	for (i = 0; i < len ; ++i)
134	if (con[i] == status)
135	return 1;
136	return 0;
137	}
138
139	/* Return the first position of "status" in the list "con" of length "len".
140	* Return -1 if there is no such entry.
141	*/
142	static int find(int *con, unsigned len, int status)
143	{
144	int i;
145
146	for (i = 0; i < len ; ++i)
147	if (con[i] == status)
148	return i;
149	return -1;
150	}
151
152	static int count(int *con, unsigned len, int status)
153	{
154	int i;
155	int c = 0;
156
157	for (i = 0; i < len ; ++i)
158	if (con[i] == status)
159	c++;
160	return c;
161	}
162
163	static int all(int *con, unsigned len, int status)
164	{
165	int i;
166
167	for (i = 0; i < len ; ++i) {
168	if (con[i] == STATUS_REDUNDANT)
169	continue;
170	if (con[i] != status)
171	return 0;
172	}
173	return 1;
174	}
175
176	/* Internal information associated to a basic map in a map
177	* that is to be coalesced by isl_map_coalesce.
178	*
179	* "bmap" is the basic map itself (or NULL if "removed" is set)
180	* "tab" is the corresponding tableau (or NULL if "removed" is set)
181	* "hull_hash" identifies the affine space in which "bmap" lives.
182	* "modified" is set if this basic map may not be identical
183	* to any of the basic maps in the input.
184	* "removed" is set if this basic map has been removed from the map
185	* "simplify" is set if this basic map may have some unknown integer
186	* divisions that were not present in the input basic maps. The basic
187	* map should then be simplified such that we may be able to find
188	* a definition among the constraints.
189	*
190	* "eq" and "ineq" are only set if we are currently trying to coalesce
191	* this basic map with another basic map, in which case they represent
192	* the position of the inequalities of this basic map with respect to
193	* the other basic map. The number of elements in the "eq" array
194	* is twice the number of equalities in the "bmap", corresponding
195	* to the two inequalities that make up each equality.
196	*/
197	struct isl_coalesce_info {
198	isl_basic_map *bmap;
199	struct isl_tab *tab;
200	uint32_t hull_hash;
201	int modified;
202	int removed;
203	int simplify;
204	int *eq;
205	int *ineq;
206	};
207
208	/* Is there any (half of an) equality constraint in the description
209	* of the basic map represented by "info" that
210	* has position "status" with respect to the other basic map?
211	*/
212	static int any_eq(struct isl_coalesce_info *info, int status)
213	{
214	isl_size n_eq;
215
216	n_eq = isl_basic_map_n_equality(bmap: info->bmap);
217	return any(con: info->eq, len: 2 * n_eq, status);
218	}
219
220	/* Is there any inequality constraint in the description
221	* of the basic map represented by "info" that
222	* has position "status" with respect to the other basic map?
223	*/
224	static int any_ineq(struct isl_coalesce_info *info, int status)
225	{
226	isl_size n_ineq;
227
228	n_ineq = isl_basic_map_n_inequality(bmap: info->bmap);
229	return any(con: info->ineq, len: n_ineq, status);
230	}
231
232	/* Return the position of the first half on an equality constraint
233	* in the description of the basic map represented by "info" that
234	* has position "status" with respect to the other basic map.
235	* The returned value is twice the position of the equality constraint
236	* plus zero for the negative half and plus one for the positive half.
237	* Return -1 if there is no such entry.
238	*/
239	static int find_eq(struct isl_coalesce_info *info, int status)
240	{
241	isl_size n_eq;
242
243	n_eq = isl_basic_map_n_equality(bmap: info->bmap);
244	return find(con: info->eq, len: 2 * n_eq, status);
245	}
246
247	/* Return the position of the first inequality constraint in the description
248	* of the basic map represented by "info" that
249	* has position "status" with respect to the other basic map.
250	* Return -1 if there is no such entry.
251	*/
252	static int find_ineq(struct isl_coalesce_info *info, int status)
253	{
254	isl_size n_ineq;
255
256	n_ineq = isl_basic_map_n_inequality(bmap: info->bmap);
257	return find(con: info->ineq, len: n_ineq, status);
258	}
259
260	/* Return the number of (halves of) equality constraints in the description
261	* of the basic map represented by "info" that
262	* have position "status" with respect to the other basic map.
263	*/
264	static int count_eq(struct isl_coalesce_info *info, int status)
265	{
266	isl_size n_eq;
267
268	n_eq = isl_basic_map_n_equality(bmap: info->bmap);
269	return count(con: info->eq, len: 2 * n_eq, status);
270	}
271
272	/* Return the number of inequality constraints in the description
273	* of the basic map represented by "info" that
274	* have position "status" with respect to the other basic map.
275	*/
276	static int count_ineq(struct isl_coalesce_info *info, int status)
277	{
278	isl_size n_ineq;
279
280	n_ineq = isl_basic_map_n_inequality(bmap: info->bmap);
281	return count(con: info->ineq, len: n_ineq, status);
282	}
283
284	/* Are all non-redundant constraints of the basic map represented by "info"
285	* either valid or cut constraints with respect to the other basic map?
286	*/
287	static int all_valid_or_cut(struct isl_coalesce_info *info)
288	{
289	int i;
290
291	for (i = 0; i < 2 * info->bmap->n_eq; ++i) {
292	if (info->eq[i] == STATUS_REDUNDANT)
293	continue;
294	if (info->eq[i] == STATUS_VALID)
295	continue;
296	if (info->eq[i] == STATUS_CUT)
297	continue;
298	return 0;
299	}
300
301	for (i = 0; i < info->bmap->n_ineq; ++i) {
302	if (info->ineq[i] == STATUS_REDUNDANT)
303	continue;
304	if (info->ineq[i] == STATUS_VALID)
305	continue;
306	if (info->ineq[i] == STATUS_CUT)
307	continue;
308	return 0;
309	}
310
311	return 1;
312	}
313
314	/* Compute the hash of the (apparent) affine hull of info->bmap (with
315	* the existentially quantified variables removed) and store it
316	* in info->hash.
317	*/
318	static int coalesce_info_set_hull_hash(struct isl_coalesce_info *info)
319	{
320	isl_basic_map *hull;
321	isl_size n_div;
322
323	hull = isl_basic_map_copy(bmap: info->bmap);
324	hull = isl_basic_map_plain_affine_hull(bmap: hull);
325	n_div = isl_basic_map_dim(bmap: hull, type: isl_dim_div);
326	if (n_div < 0)
327	hull = isl_basic_map_free(bmap: hull);
328	hull = isl_basic_map_drop_constraints_involving_dims(bmap: hull,
329	type: isl_dim_div, first: 0, n: n_div);
330	info->hull_hash = isl_basic_map_get_hash(bmap: hull);
331	isl_basic_map_free(bmap: hull);
332
333	return hull ? 0 : -1;
334	}
335
336	/* Free all the allocated memory in an array
337	* of "n" isl_coalesce_info elements.
338	*/
339	static void clear_coalesce_info(int n, struct isl_coalesce_info *info)
340	{
341	int i;
342
343	if (!info)
344	return;
345
346	for (i = 0; i < n; ++i) {
347	isl_basic_map_free(bmap: info[i].bmap);
348	isl_tab_free(tab: info[i].tab);
349	}
350
351	free(ptr: info);
352	}
353
354	/* Clear the memory associated to "info".
355	*/
356	static void clear(struct isl_coalesce_info *info)
357	{
358	info->bmap = isl_basic_map_free(bmap: info->bmap);
359	isl_tab_free(tab: info->tab);
360	info->tab = NULL;
361	}
362
363	/* Drop the basic map represented by "info".
364	* That is, clear the memory associated to the entry and
365	* mark it as having been removed.
366	*/
367	static void drop(struct isl_coalesce_info *info)
368	{
369	clear(info);
370	info->removed = 1;
371	}
372
373	/* Exchange the information in "info1" with that in "info2".
374	*/
375	static void exchange(struct isl_coalesce_info *info1,
376	struct isl_coalesce_info *info2)
377	{
378	struct isl_coalesce_info info;
379
380	info = *info1;
381	*info1 = *info2;
382	*info2 = info;
383	}
384
385	/* This type represents the kind of change that has been performed
386	* while trying to coalesce two basic maps.
387	*
388	* isl_change_none: nothing was changed
389	* isl_change_drop_first: the first basic map was removed
390	* isl_change_drop_second: the second basic map was removed
391	* isl_change_fuse: the two basic maps were replaced by a new basic map.
392	*/
393	enum isl_change {
394	isl_change_error = -1,
395	isl_change_none = 0,
396	isl_change_drop_first,
397	isl_change_drop_second,
398	isl_change_fuse,
399	};
400
401	/* Update "change" based on an interchange of the first and the second
402	* basic map. That is, interchange isl_change_drop_first and
403	* isl_change_drop_second.
404	*/
405	static enum isl_change invert_change(enum isl_change change)
406	{
407	switch (change) {
408	case isl_change_error:
409	return isl_change_error;
410	case isl_change_none:
411	return isl_change_none;
412	case isl_change_drop_first:
413	return isl_change_drop_second;
414	case isl_change_drop_second:
415	return isl_change_drop_first;
416	case isl_change_fuse:
417	return isl_change_fuse;
418	}
419
420	return isl_change_error;
421	}
422
423	/* Add the valid constraints of the basic map represented by "info"
424	* to "bmap". "len" is the size of the constraints.
425	* If only one of the pair of inequalities that make up an equality
426	* is valid, then add that inequality.
427	*/
428	static __isl_give isl_basic_map *add_valid_constraints(
429	__isl_take isl_basic_map *bmap, struct isl_coalesce_info *info,
430	unsigned len)
431	{
432	int k, l;
433
434	if (!bmap)
435	return NULL;
436
437	for (k = 0; k < info->bmap->n_eq; ++k) {
438	if (info->eq[2 * k] == STATUS_VALID &&
439	info->eq[2 * k + 1] == STATUS_VALID) {
440	l = isl_basic_map_alloc_equality(bmap);
441	if (l < 0)
442	return isl_basic_map_free(bmap);
443	isl_seq_cpy(dst: bmap->eq[l], src: info->bmap->eq[k], len);
444	} else if (info->eq[2 * k] == STATUS_VALID) {
445	l = isl_basic_map_alloc_inequality(bmap);
446	if (l < 0)
447	return isl_basic_map_free(bmap);
448	isl_seq_neg(dst: bmap->ineq[l], src: info->bmap->eq[k], len);
449	} else if (info->eq[2 * k + 1] == STATUS_VALID) {
450	l = isl_basic_map_alloc_inequality(bmap);
451	if (l < 0)
452	return isl_basic_map_free(bmap);
453	isl_seq_cpy(dst: bmap->ineq[l], src: info->bmap->eq[k], len);
454	}
455	}
456
457	for (k = 0; k < info->bmap->n_ineq; ++k) {
458	if (info->ineq[k] != STATUS_VALID)
459	continue;
460	l = isl_basic_map_alloc_inequality(bmap);
461	if (l < 0)
462	return isl_basic_map_free(bmap);
463	isl_seq_cpy(dst: bmap->ineq[l], src: info->bmap->ineq[k], len);
464	}
465
466	return bmap;
467	}
468
469	/* Is "bmap" defined by a number of (non-redundant) constraints that
470	* is greater than the number of constraints of basic maps i and j combined?
471	* Equalities are counted as two inequalities.
472	*/
473	static int number_of_constraints_increases(int i, int j,
474	struct isl_coalesce_info *info,
475	__isl_keep isl_basic_map *bmap, struct isl_tab *tab)
476	{
477	int k, n_old, n_new;
478
479	n_old = 2 * info[i].bmap->n_eq + info[i].bmap->n_ineq;
480	n_old += 2 * info[j].bmap->n_eq + info[j].bmap->n_ineq;
481
482	n_new = 2 * bmap->n_eq;
483	for (k = 0; k < bmap->n_ineq; ++k)
484	if (!isl_tab_is_redundant(tab, con: bmap->n_eq + k))
485	++n_new;
486
487	return n_new > n_old;
488	}
489
490	/* Replace the pair of basic maps i and j by the basic map bounded
491	* by the valid constraints in both basic maps and the constraints
492	* in extra (if not NULL).
493	* Place the fused basic map in the position that is the smallest of i and j.
494	*
495	* If "detect_equalities" is set, then look for equalities encoded
496	* as pairs of inequalities.
497	* If "check_number" is set, then the original basic maps are only
498	* replaced if the total number of constraints does not increase.
499	* While the number of integer divisions in the two basic maps
500	* is assumed to be the same, the actual definitions may be different.
501	* We only copy the definition from one of the basic maps if it is
502	* the same as that of the other basic map. Otherwise, we mark
503	* the integer division as unknown and simplify the basic map
504	* in an attempt to recover the integer division definition.
505	* If any extra constraints get introduced, then these may
506	* involve integer divisions with a unit coefficient.
507	* Eliminate those that do not appear with any other coefficient
508	* in other constraints, to ensure they get eliminated completely,
509	* improving the chances of further coalescing.
510	*/
511	static enum isl_change fuse(int i, int j, struct isl_coalesce_info *info,
512	__isl_keep isl_mat *extra, int detect_equalities, int check_number)
513	{
514	int k, l;
515	struct isl_basic_map *fused = NULL;
516	struct isl_tab *fused_tab = NULL;
517	isl_size total = isl_basic_map_dim(bmap: info[i].bmap, type: isl_dim_all);
518	unsigned extra_rows = extra ? extra->n_row : 0;
519	unsigned n_eq, n_ineq;
520	int simplify = 0;
521
522	if (total < 0)
523	return isl_change_error;
524	if (j < i)
525	return fuse(i: j, j: i, info, extra, detect_equalities, check_number);
526
527	n_eq = info[i].bmap->n_eq + info[j].bmap->n_eq;
528	n_ineq = info[i].bmap->n_ineq + info[j].bmap->n_ineq;
529	fused = isl_basic_map_alloc_space(space: isl_space_copy(space: info[i].bmap->dim),
530	extra: info[i].bmap->n_div, n_eq, n_ineq: n_eq + n_ineq + extra_rows);
531	fused = add_valid_constraints(bmap: fused, info: &info[i], len: 1 + total);
532	fused = add_valid_constraints(bmap: fused, info: &info[j], len: 1 + total);
533	if (!fused)
534	goto error;
535	if (ISL_F_ISSET(info[i].bmap, ISL_BASIC_MAP_RATIONAL) &&
536	ISL_F_ISSET(info[j].bmap, ISL_BASIC_MAP_RATIONAL))
537	ISL_F_SET(fused, ISL_BASIC_MAP_RATIONAL);
538
539	for (k = 0; k < info[i].bmap->n_div; ++k) {
540	int l = isl_basic_map_alloc_div(bmap: fused);
541	if (l < 0)
542	goto error;
543	if (isl_seq_eq(p1: info[i].bmap->div[k], p2: info[j].bmap->div[k],
544	len: 1 + 1 + total)) {
545	isl_seq_cpy(dst: fused->div[l], src: info[i].bmap->div[k],
546	len: 1 + 1 + total);
547	} else {
548	isl_int_set_si(fused->div[l][0], 0);
549	simplify = 1;
550	}
551	}
552
553	for (k = 0; k < extra_rows; ++k) {
554	l = isl_basic_map_alloc_inequality(bmap: fused);
555	if (l < 0)
556	goto error;
557	isl_seq_cpy(dst: fused->ineq[l], src: extra->row[k], len: 1 + total);
558	}
559
560	if (detect_equalities)
561	fused = isl_basic_map_detect_inequality_pairs(bmap: fused, NULL);
562	fused = isl_basic_map_gauss(bmap: fused, NULL);
563	if (simplify || info[j].simplify) {
564	fused = isl_basic_map_simplify(bmap: fused);
565	info[i].simplify = 0;
566	} else if (extra_rows > 0) {
567	fused = isl_basic_map_eliminate_pure_unit_divs(bmap: fused);
568	}
569	fused = isl_basic_map_finalize(bmap: fused);
570
571	fused_tab = isl_tab_from_basic_map(bmap: fused, track: 0);
572	if (isl_tab_detect_redundant(tab: fused_tab) < 0)
573	goto error;
574
575	if (check_number &&
576	number_of_constraints_increases(i, j, info, bmap: fused, tab: fused_tab)) {
577	isl_tab_free(tab: fused_tab);
578	isl_basic_map_free(bmap: fused);
579	return isl_change_none;
580	}
581
582	clear(info: &info[i]);
583	info[i].bmap = fused;
584	info[i].tab = fused_tab;
585	info[i].modified = 1;
586	drop(info: &info[j]);
587
588	return isl_change_fuse;
589	error:
590	isl_tab_free(tab: fused_tab);
591	isl_basic_map_free(bmap: fused);
592	return isl_change_error;
593	}
594
595	/* Given a pair of basic maps i and j such that all constraints are either
596	* "valid" or "cut", check if the facets corresponding to the "cut"
597	* constraints of i lie entirely within basic map j.
598	* If so, replace the pair by the basic map consisting of the valid
599	* constraints in both basic maps.
600	* Checking whether the facet lies entirely within basic map j
601	* is performed by checking whether the constraints of basic map j
602	* are valid for the facet. These tests are performed on a rational
603	* tableau to avoid the theoretical possibility that a constraint
604	* that was considered to be a cut constraint for the entire basic map i
605	* happens to be considered to be a valid constraint for the facet,
606	* even though it cuts off the same rational points.
607	*
608	* To see that we are not introducing any extra points, call the
609	* two basic maps A and B and the resulting map U and let x
610	* be an element of U \setminus ( A \cup B ).
611	* A line connecting x with an element of A \cup B meets a facet F
612	* of either A or B. Assume it is a facet of B and let c_1 be
613	* the corresponding facet constraint. We have c_1(x) < 0 and
614	* so c_1 is a cut constraint. This implies that there is some
615	* (possibly rational) point x' satisfying the constraints of A
616	* and the opposite of c_1 as otherwise c_1 would have been marked
617	* valid for A. The line connecting x and x' meets a facet of A
618	* in a (possibly rational) point that also violates c_1, but this
619	* is impossible since all cut constraints of B are valid for all
620	* cut facets of A.
621	* In case F is a facet of A rather than B, then we can apply the
622	* above reasoning to find a facet of B separating x from A \cup B first.
623	*/
624	static enum isl_change check_facets(int i, int j,
625	struct isl_coalesce_info *info)
626	{
627	int k, l;
628	struct isl_tab_undo *snap, *snap2;
629	unsigned n_eq = info[i].bmap->n_eq;
630
631	snap = isl_tab_snap(tab: info[i].tab);
632	if (isl_tab_mark_rational(tab: info[i].tab) < 0)
633	return isl_change_error;
634	snap2 = isl_tab_snap(tab: info[i].tab);
635
636	for (k = 0; k < info[i].bmap->n_ineq; ++k) {
637	if (info[i].ineq[k] != STATUS_CUT)
638	continue;
639	if (isl_tab_select_facet(tab: info[i].tab, con: n_eq + k) < 0)
640	return isl_change_error;
641	for (l = 0; l < info[j].bmap->n_ineq; ++l) {
642	int stat;
643	if (info[j].ineq[l] != STATUS_CUT)
644	continue;
645	stat = status_in(ineq: info[j].bmap->ineq[l], tab: info[i].tab);
646	if (stat < 0)
647	return isl_change_error;
648	if (stat != STATUS_VALID)
649	break;
650	}
651	if (isl_tab_rollback(tab: info[i].tab, snap: snap2) < 0)
652	return isl_change_error;
653	if (l < info[j].bmap->n_ineq)
654	break;
655	}
656
657	if (k < info[i].bmap->n_ineq) {
658	if (isl_tab_rollback(tab: info[i].tab, snap) < 0)
659	return isl_change_error;
660	return isl_change_none;
661	}
662	return fuse(i, j, info, NULL, detect_equalities: 0, check_number: 0);
663	}
664
665	/* Check if info->bmap contains the basic map represented
666	* by the tableau "tab".
667	* For each equality, we check both the constraint itself
668	* (as an inequality) and its negation. Make sure the
669	* equality is returned to its original state before returning.
670	*/
671	static isl_bool contains(struct isl_coalesce_info *info, struct isl_tab *tab)
672	{
673	int k;
674	isl_size dim;
675	isl_basic_map *bmap = info->bmap;
676
677	dim = isl_basic_map_dim(bmap, type: isl_dim_all);
678	if (dim < 0)
679	return isl_bool_error;
680	for (k = 0; k < bmap->n_eq; ++k) {
681	int stat;
682	isl_seq_neg(dst: bmap->eq[k], src: bmap->eq[k], len: 1 + dim);
683	stat = status_in(ineq: bmap->eq[k], tab);
684	isl_seq_neg(dst: bmap->eq[k], src: bmap->eq[k], len: 1 + dim);
685	if (stat < 0)
686	return isl_bool_error;
687	if (stat != STATUS_VALID)
688	return isl_bool_false;
689	stat = status_in(ineq: bmap->eq[k], tab);
690	if (stat < 0)
691	return isl_bool_error;
692	if (stat != STATUS_VALID)
693	return isl_bool_false;
694	}
695
696	for (k = 0; k < bmap->n_ineq; ++k) {
697	int stat;
698	if (info->ineq[k] == STATUS_REDUNDANT)
699	continue;
700	stat = status_in(ineq: bmap->ineq[k], tab);
701	if (stat < 0)
702	return isl_bool_error;
703	if (stat != STATUS_VALID)
704	return isl_bool_false;
705	}
706	return isl_bool_true;
707	}
708
709	/* Basic map "i" has an inequality "k" that is adjacent
710	* to some inequality of basic map "j". All the other inequalities
711	* are valid for "j".
712	* If not NULL, then "extra" contains extra wrapping constraints that are valid
713	* for both "i" and "j".
714	* Check if basic map "j" forms an extension of basic map "i",
715	* taking into account the extra constraints, if any.
716	*
717	* Note that this function is only called if some of the equalities or
718	* inequalities of basic map "j" do cut basic map "i". The function is
719	* correct even if there are no such cut constraints, but in that case
720	* the additional checks performed by this function are overkill.
721	*
722	* In particular, we replace constraint k, say f >= 0, by constraint
723	* f <= -1, add the inequalities of "j" that are valid for "i",
724	* as well as the "extra" constraints, if any,
725	* and check if the result is a subset of basic map "j".
726	* To improve the chances of the subset relation being detected,
727	* any variable that only attains a single integer value
728	* in the tableau of "i" is first fixed to that value.
729	* If the result is a subset, then we know that this result is exactly equal
730	* to basic map "j" since all its constraints are valid for basic map "j".
731	* By combining the valid constraints of "i" (all equalities and all
732	* inequalities except "k"), the valid constraints of "j" and
733	* the "extra" constraints, if any, we therefore
734	* obtain a basic map that is equal to their union.
735	* In this case, there is no need to perform a rollback of the tableau
736	* since it is going to be destroyed in fuse().
737	*
738	*
739	* |\__ |\__
740	* | \__ | \__
741	* | \_ => | \__
742	* |_______| _ |_________\
743	*
744	*
745	* |\ |\
746	* | \ | \
747	* | \ | \
748	* | | | \
749	* | ||\ => | \
750	* | || \ | \
751	* | || | | |
752	* |__||_/ |_____/
753	*
754	*
755	* _______ _______
756	* | | __ | \__
757	* | ||__| => | __|
758	* |_______| |_______/
759	*/
760	static enum isl_change is_adj_ineq_extension_with_wraps(int i, int j, int k,
761	struct isl_coalesce_info *info, __isl_keep isl_mat *extra)
762	{
763	struct isl_tab_undo *snap;
764	isl_size n_eq_i, n_ineq_j, n_extra;
765	isl_size total = isl_basic_map_dim(bmap: info[i].bmap, type: isl_dim_all);
766	isl_stat r;
767	isl_bool super;
768
769	if (total < 0)
770	return isl_change_error;
771
772	n_eq_i = isl_basic_map_n_equality(bmap: info[i].bmap);
773	n_ineq_j = isl_basic_map_n_inequality(bmap: info[j].bmap);
774	n_extra = isl_mat_rows(mat: extra);
775	if (n_eq_i < 0 || n_ineq_j < 0 || n_extra < 0)
776	return isl_change_error;
777
778	if (isl_tab_extend_cons(tab: info[i].tab, n_new: 1 + n_ineq_j + n_extra) < 0)
779	return isl_change_error;
780
781	snap = isl_tab_snap(tab: info[i].tab);
782
783	if (isl_tab_unrestrict(tab: info[i].tab, con: n_eq_i + k) < 0)
784	return isl_change_error;
785
786	isl_seq_neg(dst: info[i].bmap->ineq[k], src: info[i].bmap->ineq[k], len: 1 + total);
787	isl_int_sub_ui(info[i].bmap->ineq[k][0], info[i].bmap->ineq[k][0], 1);
788	r = isl_tab_add_ineq(tab: info[i].tab, ineq: info[i].bmap->ineq[k]);
789	isl_seq_neg(dst: info[i].bmap->ineq[k], src: info[i].bmap->ineq[k], len: 1 + total);
790	isl_int_sub_ui(info[i].bmap->ineq[k][0], info[i].bmap->ineq[k][0], 1);
791	if (r < 0)
792	return isl_change_error;
793
794	for (k = 0; k < n_ineq_j; ++k) {
795	if (info[j].ineq[k] != STATUS_VALID)
796	continue;
797	if (isl_tab_add_ineq(tab: info[i].tab, ineq: info[j].bmap->ineq[k]) < 0)
798	return isl_change_error;
799	}
800	for (k = 0; k < n_extra; ++k) {
801	if (isl_tab_add_ineq(tab: info[i].tab, ineq: extra->row[k]) < 0)
802	return isl_change_error;
803	}
804	if (isl_tab_detect_constants(tab: info[i].tab) < 0)
805	return isl_change_error;
806
807	super = contains(info: &info[j], tab: info[i].tab);
808	if (super < 0)
809	return isl_change_error;
810	if (super)
811	return fuse(i, j, info, extra, detect_equalities: 0, check_number: 0);
812
813	if (isl_tab_rollback(tab: info[i].tab, snap) < 0)
814	return isl_change_error;
815
816	return isl_change_none;
817	}
818
819	/* Given an affine transformation matrix "T", does row "row" represent
820	* anything other than a unit vector (possibly shifted by a constant)
821	* that is not involved in any of the other rows?
822	*
823	* That is, if a constraint involves the variable corresponding to
824	* the row, then could its preimage by "T" have any coefficients
825	* that are different from those in the original constraint?
826	*/
827	static int not_unique_unit_row(__isl_keep isl_mat *T, int row)
828	{
829	int i, j;
830	int len = T->n_col - 1;
831
832	i = isl_seq_first_non_zero(p: T->row[row] + 1, len);
833	if (i < 0)
834	return 1;
835	if (!isl_int_is_one(T->row[row][1 + i]) &&
836	!isl_int_is_negone(T->row[row][1 + i]))
837	return 1;
838
839	j = isl_seq_first_non_zero(p: T->row[row] + 1 + i + 1, len: len - (i + 1));
840	if (j >= 0)
841	return 1;
842
843	for (j = 1; j < T->n_row; ++j) {
844	if (j == row)
845	continue;
846	if (!isl_int_is_zero(T->row[j][1 + i]))
847	return 1;
848	}
849
850	return 0;
851	}
852
853	/* Does inequality constraint "ineq" of "bmap" involve any of
854	* the variables marked in "affected"?
855	* "total" is the total number of variables, i.e., the number
856	* of entries in "affected".
857	*/
858	static isl_bool is_affected(__isl_keep isl_basic_map *bmap, int ineq,
859	int *affected, int total)
860	{
861	int i;
862
863	for (i = 0; i < total; ++i) {
864	if (!affected[i])
865	continue;
866	if (!isl_int_is_zero(bmap->ineq[ineq][1 + i]))
867	return isl_bool_true;
868	}
869
870	return isl_bool_false;
871	}
872
873	/* Given the compressed version of inequality constraint "ineq"
874	* of info->bmap in "v", check if the constraint can be tightened,
875	* where the compression is based on an equality constraint valid
876	* for info->tab.
877	* If so, add the tightened version of the inequality constraint
878	* to info->tab. "v" may be modified by this function.
879	*
880	* That is, if the compressed constraint is of the form
881	*
882	* m f() + c >= 0
883	*
884	* with 0 < c < m, then it is equivalent to
885	*
886	* f() >= 0
887	*
888	* This means that c can also be subtracted from the original,
889	* uncompressed constraint without affecting the integer points
890	* in info->tab. Add this tightened constraint as an extra row
891	* to info->tab to make this information explicitly available.
892	*/
893	static __isl_give isl_vec *try_tightening(struct isl_coalesce_info *info,
894	int ineq, __isl_take isl_vec *v)
895	{
896	isl_ctx *ctx;
897	isl_stat r;
898
899	if (!v)
900	return NULL;
901
902	ctx = isl_vec_get_ctx(vec: v);
903	isl_seq_gcd(p: v->el + 1, len: v->size - 1, gcd: &ctx->normalize_gcd);
904	if (isl_int_is_zero(ctx->normalize_gcd) ||
905	isl_int_is_one(ctx->normalize_gcd)) {
906	return v;
907	}
908
909	v = isl_vec_cow(vec: v);
910	if (!v)
911	return NULL;
912
913	isl_int_fdiv_r(v->el[0], v->el[0], ctx->normalize_gcd);
914	if (isl_int_is_zero(v->el[0]))
915	return v;
916
917	if (isl_tab_extend_cons(tab: info->tab, n_new: 1) < 0)
918	return isl_vec_free(vec: v);
919
920	isl_int_sub(info->bmap->ineq[ineq][0],
921	info->bmap->ineq[ineq][0], v->el[0]);
922	r = isl_tab_add_ineq(tab: info->tab, ineq: info->bmap->ineq[ineq]);
923	isl_int_add(info->bmap->ineq[ineq][0],
924	info->bmap->ineq[ineq][0], v->el[0]);
925
926	if (r < 0)
927	return isl_vec_free(vec: v);
928
929	return v;
930	}
931
932	/* Tighten the (non-redundant) constraints on the facet represented
933	* by info->tab.
934	* In particular, on input, info->tab represents the result
935	* of relaxing the "n" inequality constraints of info->bmap in "relaxed"
936	* by one, i.e., replacing f_i >= 0 by f_i + 1 >= 0, and then
937	* replacing the one at index "l" by the corresponding equality,
938	* i.e., f_k + 1 = 0, with k = relaxed[l].
939	*
940	* Compute a variable compression from the equality constraint f_k + 1 = 0
941	* and use it to tighten the other constraints of info->bmap
942	* (that is, all constraints that have not been relaxed),
943	* updating info->tab (and leaving info->bmap untouched).
944	* The compression handles essentially two cases, one where a variable
945	* is assigned a fixed value and can therefore be eliminated, and one
946	* where one variable is a shifted multiple of some other variable and
947	* can therefore be replaced by that multiple.
948	* Gaussian elimination would also work for the first case, but for
949	* the second case, the effectiveness would depend on the order
950	* of the variables.
951	* After compression, some of the constraints may have coefficients
952	* with a common divisor. If this divisor does not divide the constant
953	* term, then the constraint can be tightened.
954	* The tightening is performed on the tableau info->tab by introducing
955	* extra (temporary) constraints.
956	*
957	* Only constraints that are possibly affected by the compression are
958	* considered. In particular, if the constraint only involves variables
959	* that are directly mapped to a distinct set of other variables, then
960	* no common divisor can be introduced and no tightening can occur.
961	*
962	* It is important to only consider the non-redundant constraints
963	* since the facet constraint has been relaxed prior to the call
964	* to this function, meaning that the constraints that were redundant
965	* prior to the relaxation may no longer be redundant.
966	* These constraints will be ignored in the fused result, so
967	* the fusion detection should not exploit them.
968	*/
969	static isl_stat tighten_on_relaxed_facet(struct isl_coalesce_info *info,
970	int n, int *relaxed, int l)
971	{
972	isl_size total;
973	isl_ctx *ctx;
974	isl_vec *v = NULL;
975	isl_mat *T;
976	int i;
977	int k;
978	int *affected;
979
980	k = relaxed[l];
981	ctx = isl_basic_map_get_ctx(bmap: info->bmap);
982	total = isl_basic_map_dim(bmap: info->bmap, type: isl_dim_all);
983	if (total < 0)
984	return isl_stat_error;
985	isl_int_add_ui(info->bmap->ineq[k][0], info->bmap->ineq[k][0], 1);
986	T = isl_mat_sub_alloc6(ctx, row: info->bmap->ineq, first_row: k, n_row: 1, first_col: 0, n_col: 1 + total);
987	T = isl_mat_variable_compression(B: T, NULL);
988	isl_int_sub_ui(info->bmap->ineq[k][0], info->bmap->ineq[k][0], 1);
989	if (!T)
990	return isl_stat_error;
991	if (T->n_col == 0) {
992	isl_mat_free(mat: T);
993	return isl_stat_ok;
994	}
995
996	affected = isl_alloc_array(ctx, int, total);
997	if (!affected)
998	goto error;
999
1000	for (i = 0; i < total; ++i)
1001	affected[i] = not_unique_unit_row(T, row: 1 + i);
1002
1003	for (i = 0; i < info->bmap->n_ineq; ++i) {
1004	isl_bool handle;
1005	if (any(con: relaxed, len: n, status: i))
1006	continue;
1007	if (info->ineq[i] == STATUS_REDUNDANT)
1008	continue;
1009	handle = is_affected(bmap: info->bmap, ineq: i, affected, total);
1010	if (handle < 0)
1011	goto error;
1012	if (!handle)
1013	continue;
1014	v = isl_vec_alloc(ctx, size: 1 + total);
1015	if (!v)
1016	goto error;
1017	isl_seq_cpy(dst: v->el, src: info->bmap->ineq[i], len: 1 + total);
1018	v = isl_vec_mat_product(vec: v, mat: isl_mat_copy(mat: T));
1019	v = try_tightening(info, ineq: i, v);
1020	isl_vec_free(vec: v);
1021	if (!v)
1022	goto error;
1023	}
1024
1025	isl_mat_free(mat: T);
1026	free(ptr: affected);
1027	return isl_stat_ok;
1028	error:
1029	isl_mat_free(mat: T);
1030	free(ptr: affected);
1031	return isl_stat_error;
1032	}
1033
1034	/* Replace the basic maps "i" and "j" by an extension of "i"
1035	* along the "n" inequality constraints in "relax" by one.
1036	* The tableau info[i].tab has already been extended.
1037	* Extend info[i].bmap accordingly by relaxing all constraints in "relax"
1038	* by one.
1039	* Each integer division that does not have exactly the same
1040	* definition in "i" and "j" is marked unknown and the basic map
1041	* is scheduled to be simplified in an attempt to recover
1042	* the integer division definition.
1043	* Place the extension in the position that is the smallest of i and j.
1044	*/
1045	static enum isl_change extend(int i, int j, int n, int *relax,
1046	struct isl_coalesce_info *info)
1047	{
1048	int l;
1049	isl_size total;
1050
1051	info[i].bmap = isl_basic_map_cow(bmap: info[i].bmap);
1052	total = isl_basic_map_dim(bmap: info[i].bmap, type: isl_dim_all);
1053	if (total < 0)
1054	return isl_change_error;
1055	for (l = 0; l < info[i].bmap->n_div; ++l)
1056	if (!isl_seq_eq(p1: info[i].bmap->div[l],
1057	p2: info[j].bmap->div[l], len: 1 + 1 + total)) {
1058	isl_int_set_si(info[i].bmap->div[l][0], 0);
1059	info[i].simplify = 1;
1060	}
1061	for (l = 0; l < n; ++l)
1062	isl_int_add_ui(info[i].bmap->ineq[relax[l]][0],
1063	info[i].bmap->ineq[relax[l]][0], 1);
1064	ISL_F_CLR(info[i].bmap, ISL_BASIC_MAP_NO_REDUNDANT);
1065	ISL_F_SET(info[i].bmap, ISL_BASIC_MAP_FINAL);
1066	drop(info: &info[j]);
1067	info[i].modified = 1;
1068	if (j < i)
1069	exchange(info1: &info[i], info2: &info[j]);
1070	return isl_change_fuse;
1071	}
1072
1073	/* Basic map "i" has "n" inequality constraints (collected in "relax")
1074	* that are such that they include basic map "j" if they are relaxed
1075	* by one. All the other inequalities are valid for "j".
1076	* Check if basic map "j" forms an extension of basic map "i".
1077	*
1078	* In particular, relax the constraints in "relax", compute the corresponding
1079	* facets one by one and check whether each of these is included
1080	* in the other basic map.
1081	* Before testing for inclusion, the constraints on each facet
1082	* are tightened to increase the chance of an inclusion being detected.
1083	* (Adding the valid constraints of "j" to the tableau of "i", as is done
1084	* in is_adj_ineq_extension, may further increase those chances, but this
1085	* is not currently done.)
1086	* If each facet is included, we know that relaxing the constraints extends
1087	* the basic map with exactly the other basic map (we already know that this
1088	* other basic map is included in the extension, because all other
1089	* inequality constraints are valid of "j") and we can replace the
1090	* two basic maps by this extension.
1091	*
1092	* If any of the relaxed constraints turn out to be redundant, then bail out.
1093	* isl_tab_select_facet refuses to handle such constraints. It may be
1094	* possible to handle them anyway by making a distinction between
1095	* redundant constraints with a corresponding facet that still intersects
1096	* the set (allowing isl_tab_select_facet to handle them) and
1097	* those where the facet does not intersect the set (which can be ignored
1098	* because the empty facet is trivially included in the other disjunct).
1099	* However, relaxed constraints that turn out to be redundant should
1100	* be fairly rare and no such instance has been reported where
1101	* coalescing would be successful.
1102	* ____ _____
1103	* / || / |
1104	* / || / |
1105	* \ || => \ |
1106	* \ || \ |
1107	* \___|| \____|
1108	*
1109	*
1110	* \ |\
1111	* |\\ | \
1112	* | \\ | \
1113	* | | => | /
1114	* | / | /
1115	* |/ |/
1116	*/
1117	static enum isl_change is_relaxed_extension(int i, int j, int n, int *relax,
1118	struct isl_coalesce_info *info)
1119	{
1120	int l;
1121	isl_bool super;
1122	struct isl_tab_undo *snap, *snap2;
1123	unsigned n_eq = info[i].bmap->n_eq;
1124
1125	for (l = 0; l < n; ++l)
1126	if (isl_tab_is_equality(tab: info[i].tab, con: n_eq + relax[l]))
1127	return isl_change_none;
1128
1129	snap = isl_tab_snap(tab: info[i].tab);
1130	for (l = 0; l < n; ++l)
1131	if (isl_tab_relax(tab: info[i].tab, con: n_eq + relax[l]) < 0)
1132	return isl_change_error;
1133	for (l = 0; l < n; ++l) {
1134	if (!isl_tab_is_redundant(tab: info[i].tab, con: n_eq + relax[l]))
1135	continue;
1136	if (isl_tab_rollback(tab: info[i].tab, snap) < 0)
1137	return isl_change_error;
1138	return isl_change_none;
1139	}
1140	snap2 = isl_tab_snap(tab: info[i].tab);
1141	for (l = 0; l < n; ++l) {
1142	if (isl_tab_rollback(tab: info[i].tab, snap: snap2) < 0)
1143	return isl_change_error;
1144	if (isl_tab_select_facet(tab: info[i].tab, con: n_eq + relax[l]) < 0)
1145	return isl_change_error;
1146	if (tighten_on_relaxed_facet(info: &info[i], n, relaxed: relax, l) < 0)
1147	return isl_change_error;
1148	super = contains(info: &info[j], tab: info[i].tab);
1149	if (super < 0)
1150	return isl_change_error;
1151	if (super)
1152	continue;
1153	if (isl_tab_rollback(tab: info[i].tab, snap) < 0)
1154	return isl_change_error;
1155	return isl_change_none;
1156	}
1157
1158	if (isl_tab_rollback(tab: info[i].tab, snap: snap2) < 0)
1159	return isl_change_error;
1160	return extend(i, j, n, relax, info);
1161	}
1162
1163	/* Data structure that keeps track of the wrapping constraints
1164	* and of information to bound the coefficients of those constraints.
1165	*
1166	* "failed" is set if wrapping has failed.
1167	* bound is set if we want to apply a bound on the coefficients
1168	* mat contains the wrapping constraints
1169	* max is the bound on the coefficients (if bound is set)
1170	*/
1171	struct isl_wraps {
1172	int failed;
1173	int bound;
1174	isl_mat *mat;
1175	isl_int max;
1176	};
1177
1178	/* Update wraps->max to be greater than or equal to the coefficients
1179	* in the equalities and inequalities of info->bmap that can be removed
1180	* if we end up applying wrapping.
1181	*/
1182	static isl_stat wraps_update_max(struct isl_wraps *wraps,
1183	struct isl_coalesce_info *info)
1184	{
1185	int k;
1186	isl_int max_k;
1187	isl_size total = isl_basic_map_dim(bmap: info->bmap, type: isl_dim_all);
1188
1189	if (total < 0)
1190	return isl_stat_error;
1191	isl_int_init(max_k);
1192
1193	for (k = 0; k < info->bmap->n_eq; ++k) {
1194	if (info->eq[2 * k] == STATUS_VALID &&
1195	info->eq[2 * k + 1] == STATUS_VALID)
1196	continue;
1197	isl_seq_abs_max(p: info->bmap->eq[k] + 1, len: total, max: &max_k);
1198	if (isl_int_abs_gt(max_k, wraps->max))
1199	isl_int_set(wraps->max, max_k);
1200	}
1201
1202	for (k = 0; k < info->bmap->n_ineq; ++k) {
1203	if (info->ineq[k] == STATUS_VALID ||
1204	info->ineq[k] == STATUS_REDUNDANT)
1205	continue;
1206	isl_seq_abs_max(p: info->bmap->ineq[k] + 1, len: total, max: &max_k);
1207	if (isl_int_abs_gt(max_k, wraps->max))
1208	isl_int_set(wraps->max, max_k);
1209	}
1210
1211	isl_int_clear(max_k);
1212
1213	return isl_stat_ok;
1214	}
1215
1216	/* Initialize the isl_wraps data structure.
1217	* If we want to bound the coefficients of the wrapping constraints,
1218	* we set wraps->max to the largest coefficient
1219	* in the equalities and inequalities that can be removed if we end up
1220	* applying wrapping.
1221	*/
1222	static isl_stat wraps_init(struct isl_wraps *wraps, __isl_take isl_mat *mat,
1223	struct isl_coalesce_info *info, int i, int j)
1224	{
1225	isl_ctx *ctx;
1226
1227	wraps->failed = 0;
1228	wraps->bound = 0;
1229	wraps->mat = mat;
1230	if (!mat)
1231	return isl_stat_error;
1232	wraps->mat->n_row = 0;
1233	ctx = isl_mat_get_ctx(mat);
1234	wraps->bound = isl_options_get_coalesce_bounded_wrapping(ctx);
1235	if (!wraps->bound)
1236	return isl_stat_ok;
1237	isl_int_init(wraps->max);
1238	isl_int_set_si(wraps->max, 0);
1239	if (wraps_update_max(wraps, info: &info[i]) < 0)
1240	return isl_stat_error;
1241	if (wraps_update_max(wraps, info: &info[j]) < 0)
1242	return isl_stat_error;
1243
1244	return isl_stat_ok;
1245	}
1246
1247	/* Free the contents of the isl_wraps data structure.
1248	*/
1249	static void wraps_free(struct isl_wraps *wraps)
1250	{
1251	isl_mat_free(mat: wraps->mat);
1252	if (wraps->bound)
1253	isl_int_clear(wraps->max);
1254	}
1255
1256	/* Mark the wrapping as failed.
1257	*/
1258	static isl_stat wraps_mark_failed(struct isl_wraps *wraps)
1259	{
1260	wraps->failed = 1;
1261	return isl_stat_ok;
1262	}
1263
1264	/* Is the wrapping constraint in row "row" allowed?
1265	*
1266	* If wraps->bound is set, we check that none of the coefficients
1267	* is greater than wraps->max.
1268	*/
1269	static int allow_wrap(struct isl_wraps *wraps, int row)
1270	{
1271	int i;
1272
1273	if (!wraps->bound)
1274	return 1;
1275
1276	for (i = 1; i < wraps->mat->n_col; ++i)
1277	if (isl_int_abs_gt(wraps->mat->row[row][i], wraps->max))
1278	return 0;
1279
1280	return 1;
1281	}
1282
1283	/* Wrap "ineq" (or its opposite if "negate" is set) around "bound"
1284	* to include "set" and add the result in position "w" of "wraps".
1285	* "len" is the total number of coefficients in "bound" and "ineq".
1286	* Return 1 on success, 0 on failure and -1 on error.
1287	* Wrapping can fail if the result of wrapping is equal to "bound"
1288	* or if we want to bound the sizes of the coefficients and
1289	* the wrapped constraint does not satisfy this bound.
1290	*/
1291	static int add_wrap(struct isl_wraps *wraps, int w, isl_int *bound,
1292	isl_int *ineq, unsigned len, __isl_keep isl_set *set, int negate)
1293	{
1294	isl_seq_cpy(dst: wraps->mat->row[w], src: bound, len);
1295	if (negate) {
1296	isl_seq_neg(dst: wraps->mat->row[w + 1], src: ineq, len);
1297	ineq = wraps->mat->row[w + 1];
1298	}
1299	if (!isl_set_wrap_facet(set, facet: wraps->mat->row[w], ridge: ineq))
1300	return -1;
1301	if (isl_seq_eq(p1: wraps->mat->row[w], p2: bound, len))
1302	return 0;
1303	if (!allow_wrap(wraps, row: w))
1304	return 0;
1305	return 1;
1306	}
1307
1308	/* This function has two modes of operations.
1309	*
1310	* If "add_valid" is set, then all the constraints of info->bmap
1311	* (except the opposite of "bound") are valid for the other basic map.
1312	* In this case, attempts are made to wrap some of these valid constraints
1313	* to more tightly fit around "set". Only successful wrappings are recorded
1314	* and failed wrappings are ignored.
1315	*
1316	* If "add_valid" is not set, then some of the constraints of info->bmap
1317	* are not valid for the other basic map, and only those are considered
1318	* for wrapping. In this case all attempted wrappings need to succeed.
1319	* Otherwise "wraps" is marked as failed.
1320	* Note that the constraints that are valid for the other basic map
1321	* will be added to the combined basic map by default, so there is
1322	* no need to wrap them.
1323	* The caller wrap_in_facets even relies on this function not wrapping
1324	* any constraints that are already valid.
1325	*
1326	* Only consider constraints that are not redundant (as determined
1327	* by info->tab) and that are valid or invalid depending on "add_valid".
1328	* Wrap each constraint around "bound" such that it includes the whole
1329	* set "set" and append the resulting constraint to "wraps".
1330	* "wraps" is assumed to have been pre-allocated to the appropriate size.
1331	* wraps->n_row is the number of actual wrapped constraints that have
1332	* been added.
1333	* If any of the wrapping problems results in a constraint that is
1334	* identical to "bound", then this means that "set" is unbounded in such
1335	* a way that no wrapping is possible.
1336	* Similarly, if we want to bound the coefficients of the wrapping
1337	* constraints and a newly added wrapping constraint does not
1338	* satisfy the bound, then the wrapping is considered to have failed.
1339	* Note though that "wraps" is only marked failed if "add_valid" is not set.
1340	*/
1341	static isl_stat add_selected_wraps(struct isl_wraps *wraps,
1342	struct isl_coalesce_info *info, isl_int *bound, __isl_keep isl_set *set,
1343	int add_valid)
1344	{
1345	int l, m;
1346	int w;
1347	int added;
1348	isl_basic_map *bmap = info->bmap;
1349	isl_size total = isl_basic_map_dim(bmap, type: isl_dim_all);
1350	unsigned len = 1 + total;
1351
1352	if (total < 0)
1353	return isl_stat_error;
1354
1355	w = wraps->mat->n_row;
1356
1357	for (l = 0; l < bmap->n_ineq; ++l) {
1358	int is_valid = info->ineq[l] == STATUS_VALID;
1359	if ((!add_valid && is_valid) ||
1360	info->ineq[l] == STATUS_REDUNDANT)
1361	continue;
1362	if (isl_seq_is_neg(p1: bound, p2: bmap->ineq[l], len))
1363	continue;
1364	if (isl_seq_eq(p1: bound, p2: bmap->ineq[l], len))
1365	continue;
1366	if (isl_tab_is_redundant(tab: info->tab, con: bmap->n_eq + l))
1367	continue;
1368
1369	added = add_wrap(wraps, w, bound, ineq: bmap->ineq[l], len, set, negate: 0);
1370	if (added < 0)
1371	return isl_stat_error;
1372	if (!added && !is_valid)
1373	goto unbounded;
1374	if (added)
1375	++w;
1376	}
1377	for (l = 0; l < bmap->n_eq; ++l) {
1378	if (isl_seq_is_neg(p1: bound, p2: bmap->eq[l], len))
1379	continue;
1380	if (isl_seq_eq(p1: bound, p2: bmap->eq[l], len))
1381	continue;
1382
1383	for (m = 0; m < 2; ++m) {
1384	if (info->eq[2 * l + m] == STATUS_VALID)
1385	continue;
1386	added = add_wrap(wraps, w, bound, ineq: bmap->eq[l], len,
1387	set, negate: !m);
1388	if (added < 0)
1389	return isl_stat_error;
1390	if (!added)
1391	goto unbounded;
1392	++w;
1393	}
1394	}
1395
1396	wraps->mat->n_row = w;
1397	return isl_stat_ok;
1398	unbounded:
1399	return wraps_mark_failed(wraps);
1400	}
1401
1402	/* For each constraint in info->bmap that is not redundant (as determined
1403	* by info->tab) and that is not a valid constraint for the other basic map,
1404	* wrap the constraint around "bound" such that it includes the whole
1405	* set "set" and append the resulting constraint to "wraps".
1406	* Note that the constraints that are valid for the other basic map
1407	* will be added to the combined basic map by default, so there is
1408	* no need to wrap them.
1409	* The caller wrap_in_facets even relies on this function not wrapping
1410	* any constraints that are already valid.
1411	* "wraps" is assumed to have been pre-allocated to the appropriate size.
1412	* wraps->n_row is the number of actual wrapped constraints that have
1413	* been added.
1414	* If any of the wrapping problems results in a constraint that is
1415	* identical to "bound", then this means that "set" is unbounded in such
1416	* a way that no wrapping is possible. If this happens then "wraps"
1417	* is marked as failed.
1418	* Similarly, if we want to bound the coefficients of the wrapping
1419	* constraints and a newly added wrapping constraint does not
1420	* satisfy the bound, then "wraps" is also marked as failed.
1421	*/
1422	static isl_stat add_wraps(struct isl_wraps *wraps,
1423	struct isl_coalesce_info *info, isl_int *bound, __isl_keep isl_set *set)
1424	{
1425	return add_selected_wraps(wraps, info, bound, set, add_valid: 0);
1426	}
1427
1428	/* Check if the constraints in "wraps" from "first" until the last
1429	* are all valid for the basic set represented by "tab",
1430	* dropping the invalid constraints if "keep" is set and
1431	* marking the wrapping as failed if "keep" is not set and
1432	* any constraint turns out to be invalid.
1433	*/
1434	static isl_stat check_wraps(struct isl_wraps *wraps, int first,
1435	struct isl_tab *tab, int keep)
1436	{
1437	int i;
1438
1439	for (i = wraps->mat->n_row - 1; i >= first; --i) {
1440	enum isl_ineq_type type;
1441	type = isl_tab_ineq_type(tab, ineq: wraps->mat->row[i]);
1442	if (type == isl_ineq_error)
1443	return isl_stat_error;
1444	if (type == isl_ineq_redundant)
1445	continue;
1446	if (!keep)
1447	return wraps_mark_failed(wraps);
1448	wraps->mat = isl_mat_drop_rows(mat: wraps->mat, row: i, n: 1);
1449	if (!wraps->mat)
1450	return isl_stat_error;
1451	}
1452
1453	return isl_stat_ok;
1454	}
1455
1456	/* Return a set that corresponds to the non-redundant constraints
1457	* (as recorded in tab) of bmap.
1458	*
1459	* It's important to remove the redundant constraints as some
1460	* of the other constraints may have been modified after the
1461	* constraints were marked redundant.
1462	* In particular, a constraint may have been relaxed.
1463	* Redundant constraints are ignored when a constraint is relaxed
1464	* and should therefore continue to be ignored ever after.
1465	* Otherwise, the relaxation might be thwarted by some of
1466	* these constraints.
1467	*
1468	* Update the underlying set to ensure that the dimension doesn't change.
1469	* Otherwise the integer divisions could get dropped if the tab
1470	* turns out to be empty.
1471	*/
1472	static __isl_give isl_set *set_from_updated_bmap(__isl_keep isl_basic_map *bmap,
1473	struct isl_tab *tab)
1474	{
1475	isl_basic_set *bset;
1476
1477	bmap = isl_basic_map_copy(bmap);
1478	bset = isl_basic_map_underlying_set(bmap);
1479	bset = isl_basic_set_cow(bset);
1480	bset = isl_basic_set_update_from_tab(bset, tab);
1481	return isl_set_from_basic_set(bset);
1482	}
1483
1484	/* Does "info" have any cut constraints that are redundant?
1485	*/
1486	static isl_bool has_redundant_cuts(struct isl_coalesce_info *info)
1487	{
1488	int l;
1489	isl_size n_eq, n_ineq;
1490
1491	n_eq = isl_basic_map_n_equality(bmap: info->bmap);
1492	n_ineq = isl_basic_map_n_inequality(bmap: info->bmap);
1493	if (n_eq < 0 || n_ineq < 0)
1494	return isl_bool_error;
1495	for (l = 0; l < n_ineq; ++l) {
1496	int red;
1497
1498	if (info->ineq[l] != STATUS_CUT)
1499	continue;
1500	red = isl_tab_is_redundant(tab: info->tab, con: n_eq + l);
1501	if (red < 0)
1502	return isl_bool_error;
1503	if (red)
1504	return isl_bool_true;
1505	}
1506
1507	return isl_bool_false;
1508	}
1509
1510	/* Wrap some constraints of info->bmap that bound the facet defined
1511	* by inequality "k" around (the opposite of) this inequality to
1512	* include "set". "bound" may be used to store the negated inequality.
1513	*
1514	* If "add_valid" is set, then all ridges are already valid and
1515	* the purpose is to wrap "set" more tightly. In this case,
1516	* wrapping doesn't fail, although it is possible that no constraint
1517	* gets wrapped.
1518	*
1519	* If "add_valid" is not set, then some of the ridges are cut constraints
1520	* and only those are wrapped around "set".
1521	*
1522	* Since the wrapped constraints are not guaranteed to contain the whole
1523	* of info->bmap, we check them in check_wraps.
1524	* If any of the wrapped constraints turn out to be invalid, then
1525	* check_wraps will mark "wraps" as failed if "add_valid" is not set.
1526	* If "add_valid" is set, then the offending constraints are
1527	* simply removed.
1528	*
1529	* If the facet turns out to be empty, then no wrapping can be performed.
1530	* This is considered a failure, unless "add_valid" is set.
1531	*
1532	* If any of the cut constraints of info->bmap turn out
1533	* to be redundant with respect to other constraints
1534	* then these will neither be wrapped nor added directly to the result.
1535	* The result may therefore not be correct.
1536	* Skip wrapping and mark "wraps" as failed in this case.
1537	*/
1538	static isl_stat add_selected_wraps_around_facet(struct isl_wraps *wraps,
1539	struct isl_coalesce_info *info, int k, isl_int *bound,
1540	__isl_keep isl_set *set, int add_valid)
1541	{
1542	isl_bool nowrap;
1543	struct isl_tab_undo *snap;
1544	int n;
1545	isl_size total = isl_basic_map_dim(bmap: info->bmap, type: isl_dim_all);
1546
1547	if (total < 0)
1548	return isl_stat_error;
1549
1550	snap = isl_tab_snap(tab: info->tab);
1551
1552	if (isl_tab_select_facet(tab: info->tab, con: info->bmap->n_eq + k) < 0)
1553	return isl_stat_error;
1554	if (isl_tab_detect_redundant(tab: info->tab) < 0)
1555	return isl_stat_error;
1556	if (info->tab->empty) {
1557	if (isl_tab_rollback(tab: info->tab, snap) < 0)
1558	return isl_stat_error;
1559	if (!add_valid)
1560	return wraps_mark_failed(wraps);
1561	return isl_stat_ok;
1562	}
1563	nowrap = has_redundant_cuts(info);
1564	if (nowrap < 0)
1565	return isl_stat_error;
1566
1567	n = wraps->mat->n_row;
1568	if (!nowrap) {
1569	isl_seq_neg(dst: bound, src: info->bmap->ineq[k], len: 1 + total);
1570
1571	if (add_selected_wraps(wraps, info, bound, set, add_valid) < 0)
1572	return isl_stat_error;
1573	}
1574
1575	if (isl_tab_rollback(tab: info->tab, snap) < 0)
1576	return isl_stat_error;
1577	if (nowrap)
1578	return wraps_mark_failed(wraps);
1579	if (check_wraps(wraps, first: n, tab: info->tab, keep: add_valid) < 0)
1580	return isl_stat_error;
1581
1582	return isl_stat_ok;
1583	}
1584
1585	/* Wrap the constraints of info->bmap that bound the facet defined
1586	* by inequality "k" around (the opposite of) this inequality to
1587	* include "set". "bound" may be used to store the negated inequality.
1588	* If any of the wrapped constraints turn out to be invalid for info->bmap
1589	* itself, then mark "wraps" as failed.
1590	*/
1591	static isl_stat add_wraps_around_facet(struct isl_wraps *wraps,
1592	struct isl_coalesce_info *info, int k, isl_int *bound,
1593	__isl_keep isl_set *set)
1594	{
1595	return add_selected_wraps_around_facet(wraps, info, k, bound, set, add_valid: 0);
1596	}
1597
1598	/* Wrap the (valid) constraints of info->bmap that bound the facet defined
1599	* by inequality "k" around (the opposite of) this inequality to
1600	* include "set" more tightly.
1601	* "bound" may be used to store the negated inequality.
1602	* Remove any wrapping constraints that turn out to be invalid
1603	* for info->bmap itself.
1604	*/
1605	static isl_stat add_valid_wraps_around_facet(struct isl_wraps *wraps,
1606	struct isl_coalesce_info *info, int k, isl_int *bound,
1607	__isl_keep isl_set *set)
1608	{
1609	return add_selected_wraps_around_facet(wraps, info, k, bound, set, add_valid: 1);
1610	}
1611
1612	/* Basic map "i" has an inequality (say "k") that is adjacent
1613	* to some inequality of basic map "j". All the other inequalities
1614	* are valid for "j".
1615	* Check if basic map "j" forms an extension of basic map "i".
1616	*
1617	* Note that this function is only called if some of the equalities or
1618	* inequalities of basic map "j" do cut basic map "i". The function is
1619	* correct even if there are no such cut constraints, but in that case
1620	* the additional checks performed by this function are overkill.
1621	*
1622	* First try and wrap the ridges of "k" around "j".
1623	* Note that those ridges are already valid for "j",
1624	* but the wrapped versions may wrap "j" more tightly,
1625	* increasing the chances of "j" being detected as an extension of "i"
1626	*/
1627	static enum isl_change is_adj_ineq_extension(int i, int j,
1628	struct isl_coalesce_info *info)
1629	{
1630	int k;
1631	enum isl_change change;
1632	isl_size total;
1633	isl_size n_eq_i, n_ineq_i;
1634	struct isl_wraps wraps;
1635	isl_ctx *ctx;
1636	isl_mat *mat;
1637	isl_vec *bound;
1638	isl_set *set_j;
1639	isl_stat r;
1640
1641	k = find_ineq(info: &info[i], STATUS_ADJ_INEQ);
1642	if (k < 0)
1643	isl_die(isl_basic_map_get_ctx(info[i].bmap), isl_error_internal,
1644	"info[i].ineq should have exactly one STATUS_ADJ_INEQ",
1645	return isl_change_error);
1646
1647	total = isl_basic_map_dim(bmap: info[i].bmap, type: isl_dim_all);
1648	n_eq_i = isl_basic_map_n_equality(bmap: info[i].bmap);
1649	n_ineq_i = isl_basic_map_n_inequality(bmap: info[i].bmap);
1650	if (total < 0 || n_eq_i < 0 || n_ineq_i < 0)
1651	return isl_change_error;
1652
1653	set_j = set_from_updated_bmap(bmap: info[j].bmap, tab: info[j].tab);
1654	ctx = isl_basic_map_get_ctx(bmap: info[i].bmap);
1655	bound = isl_vec_alloc(ctx, size: 1 + total);
1656	mat = isl_mat_alloc(ctx, n_row: 2 * n_eq_i + n_ineq_i, n_col: 1 + total);
1657	if (wraps_init(wraps: &wraps, mat, info, i, j) < 0)
1658	goto error;
1659	if (!bound || !set_j)
1660	goto error;
1661	r = add_valid_wraps_around_facet(wraps: &wraps, info: &info[i], k, bound: bound->el, set: set_j);
1662	if (r < 0)
1663	goto error;
1664
1665	change = is_adj_ineq_extension_with_wraps(i, j, k, info, extra: wraps.mat);
1666
1667	wraps_free(wraps: &wraps);
1668	isl_vec_free(vec: bound);
1669	isl_set_free(set: set_j);
1670
1671	return change;
1672	error:
1673	wraps_free(wraps: &wraps);
1674	isl_vec_free(vec: bound);
1675	isl_set_free(set: set_j);
1676	return isl_change_error;
1677	}
1678
1679	/* Both basic maps have at least one inequality with and adjacent
1680	* (but opposite) inequality in the other basic map.
1681	* Check that there are no cut constraints and that there is only
1682	* a single pair of adjacent inequalities.
1683	* If so, we can replace the pair by a single basic map described
1684	* by all but the pair of adjacent inequalities.
1685	* Any additional points introduced lie strictly between the two
1686	* adjacent hyperplanes and can therefore be integral.
1687	*
1688	* ____ _____
1689	* / ||\ / \
1690	* / || \ / \
1691	* \ || \ => \ \
1692	* \ || / \ /
1693	* \___||_/ \_____/
1694	*
1695	* The test for a single pair of adjacent inequalities is important
1696	* for avoiding the combination of two basic maps like the following
1697	*
1698	* /|
1699	* / |
1700	* /__|
1701	* _____
1702	* | |
1703	* | |
1704	* |___|
1705	*
1706	* If there are some cut constraints on one side, then we may
1707	* still be able to fuse the two basic maps, but we need to perform
1708	* some additional checks in is_adj_ineq_extension.
1709	*/
1710	static enum isl_change check_adj_ineq(int i, int j,
1711	struct isl_coalesce_info *info)
1712	{
1713	int count_i, count_j;
1714	int cut_i, cut_j;
1715
1716	count_i = count_ineq(info: &info[i], STATUS_ADJ_INEQ);
1717	count_j = count_ineq(info: &info[j], STATUS_ADJ_INEQ);
1718
1719	if (count_i != 1 && count_j != 1)
1720	return isl_change_none;
1721
1722	cut_i = any_eq(info: &info[i], STATUS_CUT) || any_ineq(info: &info[i], STATUS_CUT);
1723	cut_j = any_eq(info: &info[j], STATUS_CUT) || any_ineq(info: &info[j], STATUS_CUT);
1724
1725	if (!cut_i && !cut_j && count_i == 1 && count_j == 1)
1726	return fuse(i, j, info, NULL, detect_equalities: 0, check_number: 0);
1727
1728	if (count_i == 1 && !cut_i)
1729	return is_adj_ineq_extension(i, j, info);
1730
1731	if (count_j == 1 && !cut_j)
1732	return is_adj_ineq_extension(i: j, j: i, info);
1733
1734	return isl_change_none;
1735	}
1736
1737	/* Given a basic set i with a constraint k that is adjacent to
1738	* basic set j, check if we can wrap
1739	* both the facet corresponding to k (if "wrap_facet" is set) and basic map j
1740	* (always) around their ridges to include the other set.
1741	* If so, replace the pair of basic sets by their union.
1742	*
1743	* All constraints of i (except k) are assumed to be valid or
1744	* cut constraints for j.
1745	* Wrapping the cut constraints to include basic map j may result
1746	* in constraints that are no longer valid of basic map i
1747	* we have to check that the resulting wrapping constraints are valid for i.
1748	* If "wrap_facet" is not set, then all constraints of i (except k)
1749	* are assumed to be valid for j.
1750	* ____ _____
1751	* / | / \
1752	* / || / |
1753	* \ || => \ |
1754	* \ || \ |
1755	* \___|| \____|
1756	*
1757	*/
1758	static enum isl_change can_wrap_in_facet(int i, int j, int k,
1759	struct isl_coalesce_info *info, int wrap_facet)
1760	{
1761	enum isl_change change = isl_change_none;
1762	struct isl_wraps wraps;
1763	isl_ctx *ctx;
1764	isl_mat *mat;
1765	struct isl_set *set_i = NULL;
1766	struct isl_set *set_j = NULL;
1767	struct isl_vec *bound = NULL;
1768	isl_size total = isl_basic_map_dim(bmap: info[i].bmap, type: isl_dim_all);
1769
1770	if (total < 0)
1771	return isl_change_error;
1772	set_i = set_from_updated_bmap(bmap: info[i].bmap, tab: info[i].tab);
1773	set_j = set_from_updated_bmap(bmap: info[j].bmap, tab: info[j].tab);
1774	ctx = isl_basic_map_get_ctx(bmap: info[i].bmap);
1775	mat = isl_mat_alloc(ctx, n_row: 2 * (info[i].bmap->n_eq + info[j].bmap->n_eq) +
1776	info[i].bmap->n_ineq + info[j].bmap->n_ineq,
1777	n_col: 1 + total);
1778	if (wraps_init(wraps: &wraps, mat, info, i, j) < 0)
1779	goto error;
1780	bound = isl_vec_alloc(ctx, size: 1 + total);
1781	if (!set_i || !set_j || !bound)
1782	goto error;
1783
1784	isl_seq_cpy(dst: bound->el, src: info[i].bmap->ineq[k], len: 1 + total);
1785	isl_int_add_ui(bound->el[0], bound->el[0], 1);
1786	isl_seq_normalize(ctx, p: bound->el, len: 1 + total);
1787
1788	isl_seq_cpy(dst: wraps.mat->row[0], src: bound->el, len: 1 + total);
1789	wraps.mat->n_row = 1;
1790
1791	if (add_wraps(wraps: &wraps, info: &info[j], bound: bound->el, set: set_i) < 0)
1792	goto error;
1793	if (wraps.failed)
1794	goto unbounded;
1795
1796	if (wrap_facet) {
1797	if (add_wraps_around_facet(wraps: &wraps, info: &info[i], k,
1798	bound: bound->el, set: set_j) < 0)
1799	goto error;
1800	if (wraps.failed)
1801	goto unbounded;
1802	}
1803
1804	change = fuse(i, j, info, extra: wraps.mat, detect_equalities: 0, check_number: 0);
1805
1806	unbounded:
1807	wraps_free(wraps: &wraps);
1808
1809	isl_set_free(set: set_i);
1810	isl_set_free(set: set_j);
1811
1812	isl_vec_free(vec: bound);
1813
1814	return change;
1815	error:
1816	wraps_free(wraps: &wraps);
1817	isl_vec_free(vec: bound);
1818	isl_set_free(set: set_i);
1819	isl_set_free(set: set_j);
1820	return isl_change_error;
1821	}
1822
1823	/* Given a cut constraint t(x) >= 0 of basic map i, stored in row "w"
1824	* of wrap.mat, replace it by its relaxed version t(x) + 1 >= 0, and
1825	* add wrapping constraints to wrap.mat for all constraints
1826	* of basic map j that bound the part of basic map j that sticks out
1827	* of the cut constraint.
1828	* "set_i" is the underlying set of basic map i.
1829	* If any wrapping fails, then wraps->mat.n_row is reset to zero.
1830	*
1831	* In particular, we first intersect basic map j with t(x) + 1 = 0.
1832	* If the result is empty, then t(x) >= 0 was actually a valid constraint
1833	* (with respect to the integer points), so we add t(x) >= 0 instead.
1834	* Otherwise, we wrap the constraints of basic map j that are not
1835	* redundant in this intersection and that are not already valid
1836	* for basic map i over basic map i.
1837	* Note that it is sufficient to wrap the constraints to include
1838	* basic map i, because we will only wrap the constraints that do
1839	* not include basic map i already. The wrapped constraint will
1840	* therefore be more relaxed compared to the original constraint.
1841	* Since the original constraint is valid for basic map j, so is
1842	* the wrapped constraint.
1843	*/
1844	static isl_stat wrap_in_facet(struct isl_wraps *wraps, int w,
1845	struct isl_coalesce_info *info_j, __isl_keep isl_set *set_i,
1846	struct isl_tab_undo *snap)
1847	{
1848	isl_int_add_ui(wraps->mat->row[w][0], wraps->mat->row[w][0], 1);
1849	if (isl_tab_add_eq(tab: info_j->tab, eq: wraps->mat->row[w]) < 0)
1850	return isl_stat_error;
1851	if (isl_tab_detect_redundant(tab: info_j->tab) < 0)
1852	return isl_stat_error;
1853
1854	if (info_j->tab->empty)
1855	isl_int_sub_ui(wraps->mat->row[w][0], wraps->mat->row[w][0], 1);
1856	else if (add_wraps(wraps, info: info_j, bound: wraps->mat->row[w], set: set_i) < 0)
1857	return isl_stat_error;
1858
1859	if (isl_tab_rollback(tab: info_j->tab, snap) < 0)
1860	return isl_stat_error;
1861
1862	return isl_stat_ok;
1863	}
1864
1865	/* Given a pair of basic maps i and j such that j sticks out
1866	* of i at n cut constraints, each time by at most one,
1867	* try to compute wrapping constraints and replace the two
1868	* basic maps by a single basic map.
1869	* The other constraints of i are assumed to be valid for j.
1870	* "set_i" is the underlying set of basic map i.
1871	* "wraps" has been initialized to be of the right size.
1872	*
1873	* For each cut constraint t(x) >= 0 of i, we add the relaxed version
1874	* t(x) + 1 >= 0, along with wrapping constraints for all constraints
1875	* of basic map j that bound the part of basic map j that sticks out
1876	* of the cut constraint.
1877	*
1878	* If any wrapping fails, i.e., if we cannot wrap to touch
1879	* the union, then we give up.
1880	* Otherwise, the pair of basic maps is replaced by their union.
1881	*/
1882	static enum isl_change try_wrap_in_facets(int i, int j,
1883	struct isl_coalesce_info *info, struct isl_wraps *wraps,
1884	__isl_keep isl_set *set_i)
1885	{
1886	int k, l, w;
1887	isl_size total;
1888	struct isl_tab_undo *snap;
1889
1890	total = isl_basic_map_dim(bmap: info[i].bmap, type: isl_dim_all);
1891	if (total < 0)
1892	return isl_change_error;
1893
1894	snap = isl_tab_snap(tab: info[j].tab);
1895
1896	for (k = 0; k < info[i].bmap->n_eq; ++k) {
1897	for (l = 0; l < 2; ++l) {
1898	if (info[i].eq[2 * k + l] != STATUS_CUT)
1899	continue;
1900	w = wraps->mat->n_row++;
1901	if (l == 0)
1902	isl_seq_neg(dst: wraps->mat->row[w],
1903	src: info[i].bmap->eq[k], len: 1 + total);
1904	else
1905	isl_seq_cpy(dst: wraps->mat->row[w],
1906	src: info[i].bmap->eq[k], len: 1 + total);
1907	if (wrap_in_facet(wraps, w, info_j: &info[j], set_i, snap) < 0)
1908	return isl_change_error;
1909
1910	if (wraps->failed)
1911	return isl_change_none;
1912	}
1913	}
1914
1915	for (k = 0; k < info[i].bmap->n_ineq; ++k) {
1916	if (info[i].ineq[k] != STATUS_CUT)
1917	continue;
1918	w = wraps->mat->n_row++;
1919	isl_seq_cpy(dst: wraps->mat->row[w],
1920	src: info[i].bmap->ineq[k], len: 1 + total);
1921	if (wrap_in_facet(wraps, w, info_j: &info[j], set_i, snap) < 0)
1922	return isl_change_error;
1923
1924	if (wraps->failed)
1925	return isl_change_none;
1926	}
1927
1928	return fuse(i, j, info, extra: wraps->mat, detect_equalities: 0, check_number: 1);
1929	}
1930
1931	/* Given a pair of basic maps i and j such that j sticks out
1932	* of i at n cut constraints, each time by at most one,
1933	* try to compute wrapping constraints and replace the two
1934	* basic maps by a single basic map.
1935	* The other constraints of i are assumed to be valid for j.
1936	*
1937	* The core computation is performed by try_wrap_in_facets.
1938	* This function simply extracts an underlying set representation
1939	* of basic map i and initializes the data structure for keeping
1940	* track of wrapping constraints.
1941	*/
1942	static enum isl_change wrap_in_facets(int i, int j, int n,
1943	struct isl_coalesce_info *info)
1944	{
1945	enum isl_change change = isl_change_none;
1946	struct isl_wraps wraps;
1947	isl_ctx *ctx;
1948	isl_mat *mat;
1949	isl_set *set_i = NULL;
1950	isl_size total = isl_basic_map_dim(bmap: info[i].bmap, type: isl_dim_all);
1951	int max_wrap;
1952
1953	if (total < 0)
1954	return isl_change_error;
1955	if (isl_tab_extend_cons(tab: info[j].tab, n_new: 1) < 0)
1956	return isl_change_error;
1957
1958	max_wrap = 1 + 2 * info[j].bmap->n_eq + info[j].bmap->n_ineq;
1959	max_wrap *= n;
1960
1961	set_i = set_from_updated_bmap(bmap: info[i].bmap, tab: info[i].tab);
1962	ctx = isl_basic_map_get_ctx(bmap: info[i].bmap);
1963	mat = isl_mat_alloc(ctx, n_row: max_wrap, n_col: 1 + total);
1964	if (wraps_init(wraps: &wraps, mat, info, i, j) < 0)
1965	goto error;
1966	if (!set_i)
1967	goto error;
1968
1969	change = try_wrap_in_facets(i, j, info, wraps: &wraps, set_i);
1970
1971	wraps_free(wraps: &wraps);
1972	isl_set_free(set: set_i);
1973
1974	return change;
1975	error:
1976	wraps_free(wraps: &wraps);
1977	isl_set_free(set: set_i);
1978	return isl_change_error;
1979	}
1980
1981	/* Return the effect of inequality "ineq" on the tableau "tab",
1982	* after relaxing the constant term of "ineq" by one.
1983	*/
1984	static enum isl_ineq_type type_of_relaxed(struct isl_tab *tab, isl_int *ineq)
1985	{
1986	enum isl_ineq_type type;
1987
1988	isl_int_add_ui(ineq[0], ineq[0], 1);
1989	type = isl_tab_ineq_type(tab, ineq);
1990	isl_int_sub_ui(ineq[0], ineq[0], 1);
1991
1992	return type;
1993	}
1994
1995	/* Given two basic sets i and j,
1996	* check if relaxing all the cut constraints of i by one turns
1997	* them into valid constraint for j and check if we can wrap in
1998	* the bits that are sticking out.
1999	* If so, replace the pair by their union.
2000	*
2001	* We first check if all relaxed cut inequalities of i are valid for j
2002	* and then try to wrap in the intersections of the relaxed cut inequalities
2003	* with j.
2004	*
2005	* During this wrapping, we consider the points of j that lie at a distance
2006	* of exactly 1 from i. In particular, we ignore the points that lie in
2007	* between this lower-dimensional space and the basic map i.
2008	* We can therefore only apply this to integer maps.
2009	* ____ _____
2010	* / ___|_ / \
2011	* / | | / |
2012	* \ | | => \ |
2013	* \|____| \ |
2014	* \___| \____/
2015	*
2016	* _____ ______
2017	* | ____|_ | \
2018	* | | | | |
2019	* | | | => | |
2020	* |_| | | |
2021	* |_____| \______|
2022	*
2023	* _______
2024	* | |
2025	* | |\ |
2026	* | | \ |
2027	* | | \ |
2028	* | | \|
2029	* | | \
2030	* | |_____\
2031	* | |
2032	* |_______|
2033	*
2034	* Wrapping can fail if the result of wrapping one of the facets
2035	* around its edges does not produce any new facet constraint.
2036	* In particular, this happens when we try to wrap in unbounded sets.
2037	*
2038	* _______________________________________________________________________
2039	* |
2040	* | ___
2041	* | | |
2042	* |_| |_________________________________________________________________
2043	* |___|
2044	*
2045	* The following is not an acceptable result of coalescing the above two
2046	* sets as it includes extra integer points.
2047	* _______________________________________________________________________
2048	* |
2049	* |
2050	* |
2051	* |
2052	* \______________________________________________________________________
2053	*/
2054	static enum isl_change can_wrap_in_set(int i, int j,
2055	struct isl_coalesce_info *info)
2056	{
2057	int k, l;
2058	int n;
2059	isl_size total;
2060
2061	if (ISL_F_ISSET(info[i].bmap, ISL_BASIC_MAP_RATIONAL) ||
2062	ISL_F_ISSET(info[j].bmap, ISL_BASIC_MAP_RATIONAL))
2063	return isl_change_none;
2064
2065	n = count_eq(info: &info[i], STATUS_CUT) + count_ineq(info: &info[i], STATUS_CUT);
2066	if (n == 0)
2067	return isl_change_none;
2068
2069	total = isl_basic_map_dim(bmap: info[i].bmap, type: isl_dim_all);
2070	if (total < 0)
2071	return isl_change_error;
2072	for (k = 0; k < info[i].bmap->n_eq; ++k) {
2073	for (l = 0; l < 2; ++l) {
2074	enum isl_ineq_type type;
2075
2076	if (info[i].eq[2 * k + l] != STATUS_CUT)
2077	continue;
2078
2079	if (l == 0)
2080	isl_seq_neg(dst: info[i].bmap->eq[k],
2081	src: info[i].bmap->eq[k], len: 1 + total);
2082	type = type_of_relaxed(tab: info[j].tab,
2083	ineq: info[i].bmap->eq[k]);
2084	if (l == 0)
2085	isl_seq_neg(dst: info[i].bmap->eq[k],
2086	src: info[i].bmap->eq[k], len: 1 + total);
2087	if (type == isl_ineq_error)
2088	return isl_change_error;
2089	if (type != isl_ineq_redundant)
2090	return isl_change_none;
2091	}
2092	}
2093
2094	for (k = 0; k < info[i].bmap->n_ineq; ++k) {
2095	enum isl_ineq_type type;
2096
2097	if (info[i].ineq[k] != STATUS_CUT)
2098	continue;
2099
2100	type = type_of_relaxed(tab: info[j].tab, ineq: info[i].bmap->ineq[k]);
2101	if (type == isl_ineq_error)
2102	return isl_change_error;
2103	if (type != isl_ineq_redundant)
2104	return isl_change_none;
2105	}
2106
2107	return wrap_in_facets(i, j, n, info);
2108	}
2109
2110	/* Check if either i or j has only cut constraints that can
2111	* be used to wrap in (a facet of) the other basic set.
2112	* if so, replace the pair by their union.
2113	*/
2114	static enum isl_change check_wrap(int i, int j, struct isl_coalesce_info *info)
2115	{
2116	enum isl_change change = isl_change_none;
2117
2118	change = can_wrap_in_set(i, j, info);
2119	if (change != isl_change_none)
2120	return change;
2121
2122	change = can_wrap_in_set(i: j, j: i, info);
2123	return change;
2124	}
2125
2126	/* Check if all inequality constraints of "i" that cut "j" cease
2127	* to be cut constraints if they are relaxed by one.
2128	* If so, collect the cut constraints in "list".
2129	* The caller is responsible for allocating "list".
2130	*/
2131	static isl_bool all_cut_by_one(int i, int j, struct isl_coalesce_info *info,
2132	int *list)
2133	{
2134	int l, n;
2135
2136	n = 0;
2137	for (l = 0; l < info[i].bmap->n_ineq; ++l) {
2138	enum isl_ineq_type type;
2139
2140	if (info[i].ineq[l] != STATUS_CUT)
2141	continue;
2142	type = type_of_relaxed(tab: info[j].tab, ineq: info[i].bmap->ineq[l]);
2143	if (type == isl_ineq_error)
2144	return isl_bool_error;
2145	if (type != isl_ineq_redundant)
2146	return isl_bool_false;
2147	list[n++] = l;
2148	}
2149
2150	return isl_bool_true;
2151	}
2152
2153	/* Given two basic maps such that "j" has at least one equality constraint
2154	* that is adjacent to an inequality constraint of "i" and such that "i" has
2155	* exactly one inequality constraint that is adjacent to an equality
2156	* constraint of "j", check whether "i" can be extended to include "j" or
2157	* whether "j" can be wrapped into "i".
2158	* All remaining constraints of "i" and "j" are assumed to be valid
2159	* or cut constraints of the other basic map.
2160	* However, none of the equality constraints of "i" are cut constraints.
2161	*
2162	* If "i" has any "cut" inequality constraints, then check if relaxing
2163	* each of them by one is sufficient for them to become valid.
2164	* If so, check if the inequality constraint adjacent to an equality
2165	* constraint of "j" along with all these cut constraints
2166	* can be relaxed by one to contain exactly "j".
2167	* Otherwise, or if this fails, check if "j" can be wrapped into "i".
2168	*/
2169	static enum isl_change check_single_adj_eq(int i, int j,
2170	struct isl_coalesce_info *info)
2171	{
2172	enum isl_change change = isl_change_none;
2173	int k;
2174	int n_cut;
2175	int *relax;
2176	isl_ctx *ctx;
2177	isl_bool try_relax;
2178
2179	n_cut = count_ineq(info: &info[i], STATUS_CUT);
2180
2181	k = find_ineq(info: &info[i], STATUS_ADJ_EQ);
2182
2183	if (n_cut > 0) {
2184	ctx = isl_basic_map_get_ctx(bmap: info[i].bmap);
2185	relax = isl_calloc_array(ctx, int, 1 + n_cut);
2186	if (!relax)
2187	return isl_change_error;
2188	relax[0] = k;
2189	try_relax = all_cut_by_one(i, j, info, list: relax + 1);
2190	if (try_relax < 0)
2191	change = isl_change_error;
2192	} else {
2193	try_relax = isl_bool_true;
2194	relax = &k;
2195	}
2196	if (try_relax && change == isl_change_none)
2197	change = is_relaxed_extension(i, j, n: 1 + n_cut, relax, info);
2198	if (n_cut > 0)
2199	free(ptr: relax);
2200	if (change != isl_change_none)
2201	return change;
2202
2203	change = can_wrap_in_facet(i, j, k, info, wrap_facet: n_cut > 0);
2204
2205	return change;
2206	}
2207
2208	/* At least one of the basic maps has an equality that is adjacent
2209	* to an inequality. Make sure that only one of the basic maps has
2210	* such an equality and that the other basic map has exactly one
2211	* inequality adjacent to an equality.
2212	* If the other basic map does not have such an inequality, then
2213	* check if all its constraints are either valid or cut constraints
2214	* and, if so, try wrapping in the first map into the second.
2215	* Otherwise, try to extend one basic map with the other or
2216	* wrap one basic map in the other.
2217	*/
2218	static enum isl_change check_adj_eq(int i, int j,
2219	struct isl_coalesce_info *info)
2220	{
2221	if (any_eq(info: &info[i], STATUS_ADJ_INEQ) &&
2222	any_eq(info: &info[j], STATUS_ADJ_INEQ))
2223	/* ADJ EQ TOO MANY */
2224	return isl_change_none;
2225
2226	if (any_eq(info: &info[i], STATUS_ADJ_INEQ))
2227	return check_adj_eq(i: j, j: i, info);
2228
2229	/* j has an equality adjacent to an inequality in i */
2230
2231	if (count_ineq(info: &info[i], STATUS_ADJ_EQ) != 1) {
2232	if (all_valid_or_cut(info: &info[i]))
2233	return can_wrap_in_set(i, j, info);
2234	return isl_change_none;
2235	}
2236	if (any_eq(info: &info[i], STATUS_CUT))
2237	return isl_change_none;
2238	if (any_ineq(info: &info[j], STATUS_ADJ_EQ) ||
2239	any_ineq(info: &info[i], STATUS_ADJ_INEQ) ||
2240	any_ineq(info: &info[j], STATUS_ADJ_INEQ))
2241	/* ADJ EQ TOO MANY */
2242	return isl_change_none;
2243
2244	return check_single_adj_eq(i, j, info);
2245	}
2246
2247	/* Disjunct "j" lies on a hyperplane that is adjacent to disjunct "i".
2248	* In particular, disjunct "i" has an inequality constraint that is adjacent
2249	* to a (combination of) equality constraint(s) of disjunct "j",
2250	* but disjunct "j" has no explicit equality constraint adjacent
2251	* to an inequality constraint of disjunct "i".
2252	*
2253	* Disjunct "i" is already known not to have any equality constraints
2254	* that are adjacent to an equality or inequality constraint.
2255	* Check that, other than the inequality constraint mentioned above,
2256	* all other constraints of disjunct "i" are valid for disjunct "j".
2257	* If so, try and wrap in disjunct "j".
2258	*/
2259	static enum isl_change check_ineq_adj_eq(int i, int j,
2260	struct isl_coalesce_info *info)
2261	{
2262	int k;
2263
2264	if (any_eq(info: &info[i], STATUS_CUT))
2265	return isl_change_none;
2266	if (any_ineq(info: &info[i], STATUS_CUT))
2267	return isl_change_none;
2268	if (any_ineq(info: &info[i], STATUS_ADJ_INEQ))
2269	return isl_change_none;
2270	if (count_ineq(info: &info[i], STATUS_ADJ_EQ) != 1)
2271	return isl_change_none;
2272
2273	k = find_ineq(info: &info[i], STATUS_ADJ_EQ);
2274
2275	return can_wrap_in_facet(i, j, k, info, wrap_facet: 0);
2276	}
2277
2278	/* The two basic maps lie on adjacent hyperplanes. In particular,
2279	* basic map "i" has an equality that lies parallel to basic map "j".
2280	* Check if we can wrap the facets around the parallel hyperplanes
2281	* to include the other set.
2282	*
2283	* We perform basically the same operations as can_wrap_in_facet,
2284	* except that we don't need to select a facet of one of the sets.
2285	* _
2286	* \\ \\
2287	* \\ => \\
2288	* \ \|
2289	*
2290	* If there is more than one equality of "i" adjacent to an equality of "j",
2291	* then the result will satisfy one or more equalities that are a linear
2292	* combination of these equalities. These will be encoded as pairs
2293	* of inequalities in the wrapping constraints and need to be made
2294	* explicit.
2295	*/
2296	static enum isl_change check_eq_adj_eq(int i, int j,
2297	struct isl_coalesce_info *info)
2298	{
2299	int k;
2300	enum isl_change change = isl_change_none;
2301	int detect_equalities = 0;
2302	struct isl_wraps wraps;
2303	isl_ctx *ctx;
2304	isl_mat *mat;
2305	struct isl_set *set_i = NULL;
2306	struct isl_set *set_j = NULL;
2307	struct isl_vec *bound = NULL;
2308	isl_size total = isl_basic_map_dim(bmap: info[i].bmap, type: isl_dim_all);
2309
2310	if (total < 0)
2311	return isl_change_error;
2312	if (count_eq(info: &info[i], STATUS_ADJ_EQ) != 1)
2313	detect_equalities = 1;
2314
2315	k = find_eq(info: &info[i], STATUS_ADJ_EQ);
2316
2317	set_i = set_from_updated_bmap(bmap: info[i].bmap, tab: info[i].tab);
2318	set_j = set_from_updated_bmap(bmap: info[j].bmap, tab: info[j].tab);
2319	ctx = isl_basic_map_get_ctx(bmap: info[i].bmap);
2320	mat = isl_mat_alloc(ctx, n_row: 2 * (info[i].bmap->n_eq + info[j].bmap->n_eq) +
2321	info[i].bmap->n_ineq + info[j].bmap->n_ineq,
2322	n_col: 1 + total);
2323	if (wraps_init(wraps: &wraps, mat, info, i, j) < 0)
2324	goto error;
2325	bound = isl_vec_alloc(ctx, size: 1 + total);
2326	if (!set_i || !set_j || !bound)
2327	goto error;
2328
2329	if (k % 2 == 0)
2330	isl_seq_neg(dst: bound->el, src: info[i].bmap->eq[k / 2], len: 1 + total);
2331	else
2332	isl_seq_cpy(dst: bound->el, src: info[i].bmap->eq[k / 2], len: 1 + total);
2333	isl_int_add_ui(bound->el[0], bound->el[0], 1);
2334
2335	isl_seq_cpy(dst: wraps.mat->row[0], src: bound->el, len: 1 + total);
2336	wraps.mat->n_row = 1;
2337
2338	if (add_wraps(wraps: &wraps, info: &info[j], bound: bound->el, set: set_i) < 0)
2339	goto error;
2340	if (wraps.failed)
2341	goto unbounded;
2342
2343	isl_int_sub_ui(bound->el[0], bound->el[0], 1);
2344	isl_seq_neg(dst: bound->el, src: bound->el, len: 1 + total);
2345
2346	isl_seq_cpy(dst: wraps.mat->row[wraps.mat->n_row], src: bound->el, len: 1 + total);
2347	wraps.mat->n_row++;
2348
2349	if (add_wraps(wraps: &wraps, info: &info[i], bound: bound->el, set: set_j) < 0)
2350	goto error;
2351	if (wraps.failed)
2352	goto unbounded;
2353
2354	change = fuse(i, j, info, extra: wraps.mat, detect_equalities, check_number: 0);
2355
2356	if (0) {
2357	error: change = isl_change_error;
2358	}
2359	unbounded:
2360
2361	wraps_free(wraps: &wraps);
2362	isl_set_free(set: set_i);
2363	isl_set_free(set: set_j);
2364	isl_vec_free(vec: bound);
2365
2366	return change;
2367	}
2368
2369	/* Initialize the "eq" and "ineq" fields of "info".
2370	*/
2371	static void init_status(struct isl_coalesce_info *info)
2372	{
2373	info->eq = info->ineq = NULL;
2374	}
2375
2376	/* Set info->eq to the positions of the equalities of info->bmap
2377	* with respect to the basic map represented by "tab".
2378	* If info->eq has already been computed, then do not compute it again.
2379	*/
2380	static void set_eq_status_in(struct isl_coalesce_info *info,
2381	struct isl_tab *tab)
2382	{
2383	if (info->eq)
2384	return;
2385	info->eq = eq_status_in(bmap_i: info->bmap, tab_j: tab);
2386	}
2387
2388	/* Set info->ineq to the positions of the inequalities of info->bmap
2389	* with respect to the basic map represented by "tab".
2390	* If info->ineq has already been computed, then do not compute it again.
2391	*/
2392	static void set_ineq_status_in(struct isl_coalesce_info *info,
2393	struct isl_tab *tab)
2394	{
2395	if (info->ineq)
2396	return;
2397	info->ineq = ineq_status_in(bmap_i: info->bmap, tab_i: info->tab, tab_j: tab);
2398	}
2399
2400	/* Free the memory allocated by the "eq" and "ineq" fields of "info".
2401	* This function assumes that init_status has been called on "info" first,
2402	* after which the "eq" and "ineq" fields may or may not have been
2403	* assigned a newly allocated array.
2404	*/
2405	static void clear_status(struct isl_coalesce_info *info)
2406	{
2407	free(ptr: info->eq);
2408	free(ptr: info->ineq);
2409	}
2410
2411	/* Are all inequality constraints of the basic map represented by "info"
2412	* valid for the other basic map, except for a single constraint
2413	* that is adjacent to an inequality constraint of the other basic map?
2414	*/
2415	static int all_ineq_valid_or_single_adj_ineq(struct isl_coalesce_info *info)
2416	{
2417	int i;
2418	int k = -1;
2419
2420	for (i = 0; i < info->bmap->n_ineq; ++i) {
2421	if (info->ineq[i] == STATUS_REDUNDANT)
2422	continue;
2423	if (info->ineq[i] == STATUS_VALID)
2424	continue;
2425	if (info->ineq[i] != STATUS_ADJ_INEQ)
2426	return 0;
2427	if (k != -1)
2428	return 0;
2429	k = i;
2430	}
2431
2432	return k != -1;
2433	}
2434
2435	/* Basic map "i" has one or more equality constraints that separate it
2436	* from basic map "j". Check if it happens to be an extension
2437	* of basic map "j".
2438	* In particular, check that all constraints of "j" are valid for "i",
2439	* except for one inequality constraint that is adjacent
2440	* to an inequality constraints of "i".
2441	* If so, check for "i" being an extension of "j" by calling
2442	* is_adj_ineq_extension.
2443	*
2444	* Clean up the memory allocated for keeping track of the status
2445	* of the constraints before returning.
2446	*/
2447	static enum isl_change separating_equality(int i, int j,
2448	struct isl_coalesce_info *info)
2449	{
2450	enum isl_change change = isl_change_none;
2451
2452	if (all(con: info[j].eq, len: 2 * info[j].bmap->n_eq, STATUS_VALID) &&
2453	all_ineq_valid_or_single_adj_ineq(info: &info[j]))
2454	change = is_adj_ineq_extension(i: j, j: i, info);
2455
2456	clear_status(info: &info[i]);
2457	clear_status(info: &info[j]);
2458	return change;
2459	}
2460
2461	/* Check if the union of the given pair of basic maps
2462	* can be represented by a single basic map.
2463	* If so, replace the pair by the single basic map and return
2464	* isl_change_drop_first, isl_change_drop_second or isl_change_fuse.
2465	* Otherwise, return isl_change_none.
2466	* The two basic maps are assumed to live in the same local space.
2467	* The "eq" and "ineq" fields of info[i] and info[j] are assumed
2468	* to have been initialized by the caller, either to NULL or
2469	* to valid information.
2470	*
2471	* We first check the effect of each constraint of one basic map
2472	* on the other basic map.
2473	* The constraint may be
2474	* redundant the constraint is redundant in its own
2475	* basic map and should be ignore and removed
2476	* in the end
2477	* valid all (integer) points of the other basic map
2478	* satisfy the constraint
2479	* separate no (integer) point of the other basic map
2480	* satisfies the constraint
2481	* cut some but not all points of the other basic map
2482	* satisfy the constraint
2483	* adj_eq the given constraint is adjacent (on the outside)
2484	* to an equality of the other basic map
2485	* adj_ineq the given constraint is adjacent (on the outside)
2486	* to an inequality of the other basic map
2487	*
2488	* We consider seven cases in which we can replace the pair by a single
2489	* basic map. We ignore all "redundant" constraints.
2490	*
2491	* 1. all constraints of one basic map are valid
2492	* => the other basic map is a subset and can be removed
2493	*
2494	* 2. all constraints of both basic maps are either "valid" or "cut"
2495	* and the facets corresponding to the "cut" constraints
2496	* of one of the basic maps lies entirely inside the other basic map
2497	* => the pair can be replaced by a basic map consisting
2498	* of the valid constraints in both basic maps
2499	*
2500	* 3. there is a single pair of adjacent inequalities
2501	* (all other constraints are "valid")
2502	* => the pair can be replaced by a basic map consisting
2503	* of the valid constraints in both basic maps
2504	*
2505	* 4. one basic map has a single adjacent inequality, while the other
2506	* constraints are "valid". The other basic map has some
2507	* "cut" constraints, but replacing the adjacent inequality by
2508	* its opposite and adding the valid constraints of the other
2509	* basic map results in a subset of the other basic map
2510	* => the pair can be replaced by a basic map consisting
2511	* of the valid constraints in both basic maps
2512	*
2513	* 5. there is a single adjacent pair of an inequality and an equality,
2514	* the other constraints of the basic map containing the inequality are
2515	* "valid". Moreover, if the inequality the basic map is relaxed
2516	* and then turned into an equality, then resulting facet lies
2517	* entirely inside the other basic map
2518	* => the pair can be replaced by the basic map containing
2519	* the inequality, with the inequality relaxed.
2520	*
2521	* 6. there is a single inequality adjacent to an equality,
2522	* the other constraints of the basic map containing the inequality are
2523	* "valid". Moreover, the facets corresponding to both
2524	* the inequality and the equality can be wrapped around their
2525	* ridges to include the other basic map
2526	* => the pair can be replaced by a basic map consisting
2527	* of the valid constraints in both basic maps together
2528	* with all wrapping constraints
2529	*
2530	* 7. one of the basic maps extends beyond the other by at most one.
2531	* Moreover, the facets corresponding to the cut constraints and
2532	* the pieces of the other basic map at offset one from these cut
2533	* constraints can be wrapped around their ridges to include
2534	* the union of the two basic maps
2535	* => the pair can be replaced by a basic map consisting
2536	* of the valid constraints in both basic maps together
2537	* with all wrapping constraints
2538	*
2539	* 8. the two basic maps live in adjacent hyperplanes. In principle
2540	* such sets can always be combined through wrapping, but we impose
2541	* that there is only one such pair, to avoid overeager coalescing.
2542	*
2543	* Throughout the computation, we maintain a collection of tableaus
2544	* corresponding to the basic maps. When the basic maps are dropped
2545	* or combined, the tableaus are modified accordingly.
2546	*/
2547	static enum isl_change coalesce_local_pair_reuse(int i, int j,
2548	struct isl_coalesce_info *info)
2549	{
2550	enum isl_change change = isl_change_none;
2551
2552	set_ineq_status_in(info: &info[i], tab: info[j].tab);
2553	if (info[i].bmap->n_ineq && !info[i].ineq)
2554	goto error;
2555	if (any_ineq(info: &info[i], STATUS_ERROR))
2556	goto error;
2557	if (any_ineq(info: &info[i], STATUS_SEPARATE))
2558	goto done;
2559
2560	set_ineq_status_in(info: &info[j], tab: info[i].tab);
2561	if (info[j].bmap->n_ineq && !info[j].ineq)
2562	goto error;
2563	if (any_ineq(info: &info[j], STATUS_ERROR))
2564	goto error;
2565	if (any_ineq(info: &info[j], STATUS_SEPARATE))
2566	goto done;
2567
2568	set_eq_status_in(info: &info[i], tab: info[j].tab);
2569	if (info[i].bmap->n_eq && !info[i].eq)
2570	goto error;
2571	if (any_eq(info: &info[i], STATUS_ERROR))
2572	goto error;
2573
2574	set_eq_status_in(info: &info[j], tab: info[i].tab);
2575	if (info[j].bmap->n_eq && !info[j].eq)
2576	goto error;
2577	if (any_eq(info: &info[j], STATUS_ERROR))
2578	goto error;
2579
2580	if (any_eq(info: &info[i], STATUS_SEPARATE))
2581	return separating_equality(i, j, info);
2582	if (any_eq(info: &info[j], STATUS_SEPARATE))
2583	return separating_equality(i: j, j: i, info);
2584
2585	if (all(con: info[i].eq, len: 2 * info[i].bmap->n_eq, STATUS_VALID) &&
2586	all(con: info[i].ineq, len: info[i].bmap->n_ineq, STATUS_VALID)) {
2587	drop(info: &info[j]);
2588	change = isl_change_drop_second;
2589	} else if (all(con: info[j].eq, len: 2 * info[j].bmap->n_eq, STATUS_VALID) &&
2590	all(con: info[j].ineq, len: info[j].bmap->n_ineq, STATUS_VALID)) {
2591	drop(info: &info[i]);
2592	change = isl_change_drop_first;
2593	} else if (any_eq(info: &info[i], STATUS_ADJ_EQ)) {
2594	change = check_eq_adj_eq(i, j, info);
2595	} else if (any_eq(info: &info[j], STATUS_ADJ_EQ)) {
2596	change = check_eq_adj_eq(i: j, j: i, info);
2597	} else if (any_eq(info: &info[i], STATUS_ADJ_INEQ) ||
2598	any_eq(info: &info[j], STATUS_ADJ_INEQ)) {
2599	change = check_adj_eq(i, j, info);
2600	} else if (any_ineq(info: &info[i], STATUS_ADJ_EQ)) {
2601	change = check_ineq_adj_eq(i, j, info);
2602	} else if (any_ineq(info: &info[j], STATUS_ADJ_EQ)) {
2603	change = check_ineq_adj_eq(i: j, j: i, info);
2604	} else if (any_ineq(info: &info[i], STATUS_ADJ_INEQ) ||
2605	any_ineq(info: &info[j], STATUS_ADJ_INEQ)) {
2606	change = check_adj_ineq(i, j, info);
2607	} else {
2608	if (!any_eq(info: &info[i], STATUS_CUT) &&
2609	!any_eq(info: &info[j], STATUS_CUT))
2610	change = check_facets(i, j, info);
2611	if (change == isl_change_none)
2612	change = check_wrap(i, j, info);
2613	}
2614
2615	done:
2616	clear_status(info: &info[i]);
2617	clear_status(info: &info[j]);
2618	return change;
2619	error:
2620	clear_status(info: &info[i]);
2621	clear_status(info: &info[j]);
2622	return isl_change_error;
2623	}
2624
2625	/* Check if the union of the given pair of basic maps
2626	* can be represented by a single basic map.
2627	* If so, replace the pair by the single basic map and return
2628	* isl_change_drop_first, isl_change_drop_second or isl_change_fuse.
2629	* Otherwise, return isl_change_none.
2630	* The two basic maps are assumed to live in the same local space.
2631	*/
2632	static enum isl_change coalesce_local_pair(int i, int j,
2633	struct isl_coalesce_info *info)
2634	{
2635	init_status(info: &info[i]);
2636	init_status(info: &info[j]);
2637	return coalesce_local_pair_reuse(i, j, info);
2638	}
2639
2640	/* Shift the integer division at position "div" of the basic map
2641	* represented by "info" by "shift".
2642	*
2643	* That is, if the integer division has the form
2644	*
2645	* floor(f(x)/d)
2646	*
2647	* then replace it by
2648	*
2649	* floor((f(x) + shift * d)/d) - shift
2650	*/
2651	static isl_stat shift_div(struct isl_coalesce_info *info, int div,
2652	isl_int shift)
2653	{
2654	isl_size total, n_div;
2655
2656	info->bmap = isl_basic_map_shift_div(bmap: info->bmap, div, pos: 0, shift);
2657	if (!info->bmap)
2658	return isl_stat_error;
2659
2660	total = isl_basic_map_dim(bmap: info->bmap, type: isl_dim_all);
2661	n_div = isl_basic_map_dim(bmap: info->bmap, type: isl_dim_div);
2662	if (total < 0 || n_div < 0)
2663	return isl_stat_error;
2664	total -= n_div;
2665	if (isl_tab_shift_var(tab: info->tab, pos: total + div, shift) < 0)
2666	return isl_stat_error;
2667
2668	return isl_stat_ok;
2669	}
2670
2671	/* If the integer division at position "div" is defined by an equality,
2672	* i.e., a stride constraint, then change the integer division expression
2673	* to have a constant term equal to zero.
2674	*
2675	* Let the equality constraint be
2676	*
2677	* c + f + m a = 0
2678	*
2679	* The integer division expression is then typically of the form
2680	*
2681	* a = floor((-f - c')/m)
2682	*
2683	* The integer division is first shifted by t = floor(c/m),
2684	* turning the equality constraint into
2685	*
2686	* c - m floor(c/m) + f + m a' = 0
2687	*
2688	* i.e.,
2689	*
2690	* (c mod m) + f + m a' = 0
2691	*
2692	* That is,
2693	*
2694	* a' = (-f - (c mod m))/m = floor((-f)/m)
2695	*
2696	* because a' is an integer and 0 <= (c mod m) < m.
2697	* The constant term of a' can therefore be zeroed out,
2698	* but only if the integer division expression is of the expected form.
2699	*/
2700	static isl_stat normalize_stride_div(struct isl_coalesce_info *info, int div)
2701	{
2702	isl_bool defined, valid;
2703	isl_stat r;
2704	isl_constraint *c;
2705	isl_int shift, stride;
2706
2707	defined = isl_basic_map_has_defining_equality(bmap: info->bmap, type: isl_dim_div,
2708	pos: div, c: &c);
2709	if (defined < 0)
2710	return isl_stat_error;
2711	if (!defined)
2712	return isl_stat_ok;
2713	if (!c)
2714	return isl_stat_error;
2715	valid = isl_constraint_is_div_equality(constraint: c, div);
2716	isl_int_init(shift);
2717	isl_int_init(stride);
2718	isl_constraint_get_constant(constraint: c, v: &shift);
2719	isl_constraint_get_coefficient(constraint: c, type: isl_dim_div, pos: div, v: &stride);
2720	isl_int_fdiv_q(shift, shift, stride);
2721	r = shift_div(info, div, shift);
2722	isl_int_clear(stride);
2723	isl_int_clear(shift);
2724	isl_constraint_free(c);
2725	if (r < 0 || valid < 0)
2726	return isl_stat_error;
2727	if (!valid)
2728	return isl_stat_ok;
2729	info->bmap = isl_basic_map_set_div_expr_constant_num_si_inplace(
2730	bmap: info->bmap, div, value: 0);
2731	if (!info->bmap)
2732	return isl_stat_error;
2733	return isl_stat_ok;
2734	}
2735
2736	/* The basic maps represented by "info1" and "info2" are known
2737	* to have the same number of integer divisions.
2738	* Check if pairs of integer divisions are equal to each other
2739	* despite the fact that they differ by a rational constant.
2740	*
2741	* In particular, look for any pair of integer divisions that
2742	* only differ in their constant terms.
2743	* If either of these integer divisions is defined
2744	* by stride constraints, then modify it to have a zero constant term.
2745	* If both are defined by stride constraints then in the end they will have
2746	* the same (zero) constant term.
2747	*/
2748	static isl_stat harmonize_stride_divs(struct isl_coalesce_info *info1,
2749	struct isl_coalesce_info *info2)
2750	{
2751	int i;
2752	isl_size n;
2753
2754	n = isl_basic_map_dim(bmap: info1->bmap, type: isl_dim_div);
2755	if (n < 0)
2756	return isl_stat_error;
2757	for (i = 0; i < n; ++i) {
2758	isl_bool known, harmonize;
2759
2760	known = isl_basic_map_div_is_known(bmap: info1->bmap, div: i);
2761	if (known >= 0 && known)
2762	known = isl_basic_map_div_is_known(bmap: info2->bmap, div: i);
2763	if (known < 0)
2764	return isl_stat_error;
2765	if (!known)
2766	continue;
2767	harmonize = isl_basic_map_equal_div_expr_except_constant(
2768	bmap1: info1->bmap, pos1: i, bmap2: info2->bmap, pos2: i);
2769	if (harmonize < 0)
2770	return isl_stat_error;
2771	if (!harmonize)
2772	continue;
2773	if (normalize_stride_div(info: info1, div: i) < 0)
2774	return isl_stat_error;
2775	if (normalize_stride_div(info: info2, div: i) < 0)
2776	return isl_stat_error;
2777	}
2778
2779	return isl_stat_ok;
2780	}
2781
2782	/* If "shift" is an integer constant, then shift the integer division
2783	* at position "div" of the basic map represented by "info" by "shift".
2784	* If "shift" is not an integer constant, then do nothing.
2785	* If "shift" is equal to zero, then no shift needs to be performed either.
2786	*
2787	* That is, if the integer division has the form
2788	*
2789	* floor(f(x)/d)
2790	*
2791	* then replace it by
2792	*
2793	* floor((f(x) + shift * d)/d) - shift
2794	*/
2795	static isl_stat shift_if_cst_int(struct isl_coalesce_info *info, int div,
2796	__isl_keep isl_aff *shift)
2797	{
2798	isl_bool cst;
2799	isl_stat r;
2800	isl_int d;
2801	isl_val *c;
2802
2803	cst = isl_aff_is_cst(aff: shift);
2804	if (cst < 0 || !cst)
2805	return cst < 0 ? isl_stat_error : isl_stat_ok;
2806
2807	c = isl_aff_get_constant_val(aff: shift);
2808	cst = isl_val_is_int(v: c);
2809	if (cst >= 0 && cst)
2810	cst = isl_bool_not(b: isl_val_is_zero(v: c));
2811	if (cst < 0 || !cst) {
2812	isl_val_free(v: c);
2813	return cst < 0 ? isl_stat_error : isl_stat_ok;
2814	}
2815
2816	isl_int_init(d);
2817	r = isl_val_get_num_isl_int(v: c, n: &d);
2818	if (r >= 0)
2819	r = shift_div(info, div, shift: d);
2820	isl_int_clear(d);
2821
2822	isl_val_free(v: c);
2823
2824	return r;
2825	}
2826
2827	/* Check if some of the divs in the basic map represented by "info1"
2828	* are shifts of the corresponding divs in the basic map represented
2829	* by "info2", taking into account the equality constraints "eq1" of "info1"
2830	* and "eq2" of "info2". If so, align them with those of "info2".
2831	* "info1" and "info2" are assumed to have the same number
2832	* of integer divisions.
2833	*
2834	* An integer division is considered to be a shift of another integer
2835	* division if, after simplification with respect to the equality
2836	* constraints of the other basic map, one is equal to the other
2837	* plus a constant.
2838	*
2839	* In particular, for each pair of integer divisions, if both are known,
2840	* have the same denominator and are not already equal to each other,
2841	* simplify each with respect to the equality constraints
2842	* of the other basic map. If the difference is an integer constant,
2843	* then move this difference outside.
2844	* That is, if, after simplification, one integer division is of the form
2845	*
2846	* floor((f(x) + c_1)/d)
2847	*
2848	* while the other is of the form
2849	*
2850	* floor((f(x) + c_2)/d)
2851	*
2852	* and n = (c_2 - c_1)/d is an integer, then replace the first
2853	* integer division by
2854	*
2855	* floor((f_1(x) + c_1 + n * d)/d) - n,
2856	*
2857	* where floor((f_1(x) + c_1 + n * d)/d) = floor((f2(x) + c_2)/d)
2858	* after simplification with respect to the equality constraints.
2859	*/
2860	static isl_stat harmonize_divs_with_hulls(struct isl_coalesce_info *info1,
2861	struct isl_coalesce_info *info2, __isl_keep isl_basic_set *eq1,
2862	__isl_keep isl_basic_set *eq2)
2863	{
2864	int i;
2865	isl_size total;
2866	isl_local_space *ls1, *ls2;
2867
2868	total = isl_basic_map_dim(bmap: info1->bmap, type: isl_dim_all);
2869	if (total < 0)
2870	return isl_stat_error;
2871	ls1 = isl_local_space_wrap(ls: isl_basic_map_get_local_space(bmap: info1->bmap));
2872	ls2 = isl_local_space_wrap(ls: isl_basic_map_get_local_space(bmap: info2->bmap));
2873	for (i = 0; i < info1->bmap->n_div; ++i) {
2874	isl_stat r;
2875	isl_aff *div1, *div2;
2876
2877	if (!isl_local_space_div_is_known(ls: ls1, div: i) ||
2878	!isl_local_space_div_is_known(ls: ls2, div: i))
2879	continue;
2880	if (isl_int_ne(info1->bmap->div[i][0], info2->bmap->div[i][0]))
2881	continue;
2882	if (isl_seq_eq(p1: info1->bmap->div[i] + 1,
2883	p2: info2->bmap->div[i] + 1, len: 1 + total))
2884	continue;
2885	div1 = isl_local_space_get_div(ls: ls1, pos: i);
2886	div2 = isl_local_space_get_div(ls: ls2, pos: i);
2887	div1 = isl_aff_substitute_equalities(aff: div1,
2888	eq: isl_basic_set_copy(bset: eq2));
2889	div2 = isl_aff_substitute_equalities(aff: div2,
2890	eq: isl_basic_set_copy(bset: eq1));
2891	div2 = isl_aff_sub(aff1: div2, aff2: div1);
2892	r = shift_if_cst_int(info: info1, div: i, shift: div2);
2893	isl_aff_free(aff: div2);
2894	if (r < 0)
2895	break;
2896	}
2897	isl_local_space_free(ls: ls1);
2898	isl_local_space_free(ls: ls2);
2899
2900	if (i < info1->bmap->n_div)
2901	return isl_stat_error;
2902	return isl_stat_ok;
2903	}
2904
2905	/* Check if some of the divs in the basic map represented by "info1"
2906	* are shifts of the corresponding divs in the basic map represented
2907	* by "info2". If so, align them with those of "info2".
2908	* Only do this if "info1" and "info2" have the same number
2909	* of integer divisions.
2910	*
2911	* An integer division is considered to be a shift of another integer
2912	* division if, after simplification with respect to the equality
2913	* constraints of the other basic map, one is equal to the other
2914	* plus a constant.
2915	*
2916	* First check if pairs of integer divisions are equal to each other
2917	* despite the fact that they differ by a rational constant.
2918	* If so, try and arrange for them to have the same constant term.
2919	*
2920	* Then, extract the equality constraints and continue with
2921	* harmonize_divs_with_hulls.
2922	*
2923	* If the equality constraints of both basic maps are the same,
2924	* then there is no need to perform any shifting since
2925	* the coefficients of the integer divisions should have been
2926	* reduced in the same way.
2927	*/
2928	static isl_stat harmonize_divs(struct isl_coalesce_info *info1,
2929	struct isl_coalesce_info *info2)
2930	{
2931	isl_bool equal;
2932	isl_basic_map *bmap1, *bmap2;
2933	isl_basic_set *eq1, *eq2;
2934	isl_stat r;
2935
2936	if (!info1->bmap || !info2->bmap)
2937	return isl_stat_error;
2938
2939	if (info1->bmap->n_div != info2->bmap->n_div)
2940	return isl_stat_ok;
2941	if (info1->bmap->n_div == 0)
2942	return isl_stat_ok;
2943
2944	if (harmonize_stride_divs(info1, info2) < 0)
2945	return isl_stat_error;
2946
2947	bmap1 = isl_basic_map_copy(bmap: info1->bmap);
2948	bmap2 = isl_basic_map_copy(bmap: info2->bmap);
2949	eq1 = isl_basic_map_wrap(bmap: isl_basic_map_plain_affine_hull(bmap: bmap1));
2950	eq2 = isl_basic_map_wrap(bmap: isl_basic_map_plain_affine_hull(bmap: bmap2));
2951	equal = isl_basic_set_plain_is_equal(bset1: eq1, bset2: eq2);
2952	if (equal < 0)
2953	r = isl_stat_error;
2954	else if (equal)
2955	r = isl_stat_ok;
2956	else
2957	r = harmonize_divs_with_hulls(info1, info2, eq1, eq2);
2958	isl_basic_set_free(bset: eq1);
2959	isl_basic_set_free(bset: eq2);
2960
2961	return r;
2962	}
2963
2964	/* Do the two basic maps live in the same local space, i.e.,
2965	* do they have the same (known) divs?
2966	* If either basic map has any unknown divs, then we can only assume
2967	* that they do not live in the same local space.
2968	*/
2969	static isl_bool same_divs(__isl_keep isl_basic_map *bmap1,
2970	__isl_keep isl_basic_map *bmap2)
2971	{
2972	int i;
2973	isl_bool known;
2974	isl_size total;
2975
2976	if (!bmap1 || !bmap2)
2977	return isl_bool_error;
2978	if (bmap1->n_div != bmap2->n_div)
2979	return isl_bool_false;
2980
2981	if (bmap1->n_div == 0)
2982	return isl_bool_true;
2983
2984	known = isl_basic_map_divs_known(bmap: bmap1);
2985	if (known < 0 || !known)
2986	return known;
2987	known = isl_basic_map_divs_known(bmap: bmap2);
2988	if (known < 0 || !known)
2989	return known;
2990
2991	total = isl_basic_map_dim(bmap: bmap1, type: isl_dim_all);
2992	if (total < 0)
2993	return isl_bool_error;
2994	for (i = 0; i < bmap1->n_div; ++i)
2995	if (!isl_seq_eq(p1: bmap1->div[i], p2: bmap2->div[i], len: 2 + total))
2996	return isl_bool_false;
2997
2998	return isl_bool_true;
2999	}
3000
3001	/* Assuming that "tab" contains the equality constraints and
3002	* the initial inequality constraints of "bmap", copy the remaining
3003	* inequality constraints of "bmap" to "Tab".
3004	*/
3005	static isl_stat copy_ineq(struct isl_tab *tab, __isl_keep isl_basic_map *bmap)
3006	{
3007	int i, n_ineq;
3008
3009	if (!bmap)
3010	return isl_stat_error;
3011
3012	n_ineq = tab->n_con - tab->n_eq;
3013	for (i = n_ineq; i < bmap->n_ineq; ++i)
3014	if (isl_tab_add_ineq(tab, ineq: bmap->ineq[i]) < 0)
3015	return isl_stat_error;
3016
3017	return isl_stat_ok;
3018	}
3019
3020	/* Description of an integer division that is added
3021	* during an expansion.
3022	* "pos" is the position of the corresponding variable.
3023	* "cst" indicates whether this integer division has a fixed value.
3024	* "val" contains the fixed value, if the value is fixed.
3025	*/
3026	struct isl_expanded {
3027	int pos;
3028	isl_bool cst;
3029	isl_int val;
3030	};
3031
3032	/* For each of the "n" integer division variables "expanded",
3033	* if the variable has a fixed value, then add two inequality
3034	* constraints expressing the fixed value.
3035	* Otherwise, add the corresponding div constraints.
3036	* The caller is responsible for removing the div constraints
3037	* that it added for all these "n" integer divisions.
3038	*
3039	* The div constraints and the pair of inequality constraints
3040	* forcing the fixed value cannot both be added for a given variable
3041	* as the combination may render some of the original constraints redundant.
3042	* These would then be ignored during the coalescing detection,
3043	* while they could remain in the fused result.
3044	*
3045	* The two added inequality constraints are
3046	*
3047	* -a + v >= 0
3048	* a - v >= 0
3049	*
3050	* with "a" the variable and "v" its fixed value.
3051	* The facet corresponding to one of these two constraints is selected
3052	* in the tableau to ensure that the pair of inequality constraints
3053	* is treated as an equality constraint.
3054	*
3055	* The information in info->ineq is thrown away because it was
3056	* computed in terms of div constraints, while some of those
3057	* have now been replaced by these pairs of inequality constraints.
3058	*/
3059	static isl_stat fix_constant_divs(struct isl_coalesce_info *info,
3060	int n, struct isl_expanded *expanded)
3061	{
3062	unsigned o_div;
3063	int i;
3064	isl_vec *ineq;
3065
3066	o_div = isl_basic_map_offset(bmap: info->bmap, type: isl_dim_div) - 1;
3067	ineq = isl_vec_alloc(ctx: isl_tab_get_ctx(tab: info->tab), size: 1 + info->tab->n_var);
3068	if (!ineq)
3069	return isl_stat_error;
3070	isl_seq_clr(p: ineq->el + 1, len: info->tab->n_var);
3071
3072	for (i = 0; i < n; ++i) {
3073	if (!expanded[i].cst) {
3074	info->bmap = isl_basic_map_extend_constraints(
3075	base: info->bmap, n_eq: 0, n_ineq: 2);
3076	info->bmap = isl_basic_map_add_div_constraints(
3077	bmap: info->bmap, div: expanded[i].pos - o_div);
3078	} else {
3079	isl_int_set_si(ineq->el[1 + expanded[i].pos], -1);
3080	isl_int_set(ineq->el[0], expanded[i].val);
3081	info->bmap = isl_basic_map_add_ineq(bmap: info->bmap,
3082	ineq: ineq->el);
3083	isl_int_set_si(ineq->el[1 + expanded[i].pos], 1);
3084	isl_int_neg(ineq->el[0], expanded[i].val);
3085	info->bmap = isl_basic_map_add_ineq(bmap: info->bmap,
3086	ineq: ineq->el);
3087	isl_int_set_si(ineq->el[1 + expanded[i].pos], 0);
3088	}
3089	if (copy_ineq(tab: info->tab, bmap: info->bmap) < 0)
3090	break;
3091	if (expanded[i].cst &&
3092	isl_tab_select_facet(tab: info->tab, con: info->tab->n_con - 1) < 0)
3093	break;
3094	}
3095
3096	isl_vec_free(vec: ineq);
3097
3098	clear_status(info);
3099	init_status(info);
3100
3101	return i < n ? isl_stat_error : isl_stat_ok;
3102	}
3103
3104	/* Insert the "n" integer division variables "expanded"
3105	* into info->tab and info->bmap and
3106	* update info->ineq with respect to the redundant constraints
3107	* in the resulting tableau.
3108	* "bmap" contains the result of this insertion in info->bmap,
3109	* while info->bmap is the original version
3110	* of "bmap", i.e., the one that corresponds to the current
3111	* state of info->tab. The number of constraints in info->bmap
3112	* is assumed to be the same as the number of constraints
3113	* in info->tab. This is required to be able to detect
3114	* the extra constraints in "bmap".
3115	*
3116	* In particular, introduce extra variables corresponding
3117	* to the extra integer divisions and add the div constraints
3118	* that were added to "bmap" after info->tab was created
3119	* from info->bmap.
3120	* Furthermore, check if these extra integer divisions happen
3121	* to attain a fixed integer value in info->tab.
3122	* If so, replace the corresponding div constraints by pairs
3123	* of inequality constraints that fix these
3124	* integer divisions to their single integer values.
3125	* Replace info->bmap by "bmap" to match the changes to info->tab.
3126	* info->ineq was computed without a tableau and therefore
3127	* does not take into account the redundant constraints
3128	* in the tableau. Mark them here.
3129	* There is no need to check the newly added div constraints
3130	* since they cannot be redundant.
3131	* The redundancy check is not performed when constants have been discovered
3132	* since info->ineq is completely thrown away in this case.
3133	*/
3134	static isl_stat tab_insert_divs(struct isl_coalesce_info *info,
3135	int n, struct isl_expanded *expanded, __isl_take isl_basic_map *bmap)
3136	{
3137	int i, n_ineq;
3138	unsigned n_eq;
3139	struct isl_tab_undo *snap;
3140	int any;
3141
3142	if (!bmap)
3143	return isl_stat_error;
3144	if (info->bmap->n_eq + info->bmap->n_ineq != info->tab->n_con)
3145	isl_die(isl_basic_map_get_ctx(bmap), isl_error_internal,
3146	"original tableau does not correspond "
3147	"to original basic map", goto error);
3148
3149	if (isl_tab_extend_vars(tab: info->tab, n_new: n) < 0)
3150	goto error;
3151	if (isl_tab_extend_cons(tab: info->tab, n_new: 2 * n) < 0)
3152	goto error;
3153
3154	for (i = 0; i < n; ++i) {
3155	if (isl_tab_insert_var(tab: info->tab, pos: expanded[i].pos) < 0)
3156	goto error;
3157	}
3158
3159	snap = isl_tab_snap(tab: info->tab);
3160
3161	n_ineq = info->tab->n_con - info->tab->n_eq;
3162	if (copy_ineq(tab: info->tab, bmap) < 0)
3163	goto error;
3164
3165	isl_basic_map_free(bmap: info->bmap);
3166	info->bmap = bmap;
3167
3168	any = 0;
3169	for (i = 0; i < n; ++i) {
3170	expanded[i].cst = isl_tab_is_constant(tab: info->tab,
3171	var: expanded[i].pos, value: &expanded[i].val);
3172	if (expanded[i].cst < 0)
3173	return isl_stat_error;
3174	if (expanded[i].cst)
3175	any = 1;
3176	}
3177
3178	if (any) {
3179	if (isl_tab_rollback(tab: info->tab, snap) < 0)
3180	return isl_stat_error;
3181	info->bmap = isl_basic_map_cow(bmap: info->bmap);
3182	info->bmap = isl_basic_map_free_inequality(bmap: info->bmap, n: 2 * n);
3183	if (!info->bmap)
3184	return isl_stat_error;
3185
3186	return fix_constant_divs(info, n, expanded);
3187	}
3188
3189	n_eq = info->bmap->n_eq;
3190	for (i = 0; i < n_ineq; ++i) {
3191	if (isl_tab_is_redundant(tab: info->tab, con: n_eq + i))
3192	info->ineq[i] = STATUS_REDUNDANT;
3193	}
3194
3195	return isl_stat_ok;
3196	error:
3197	isl_basic_map_free(bmap);
3198	return isl_stat_error;
3199	}
3200
3201	/* Expand info->tab and info->bmap in the same way "bmap" was expanded
3202	* in isl_basic_map_expand_divs using the expansion "exp" and
3203	* update info->ineq with respect to the redundant constraints
3204	* in the resulting tableau. info->bmap is the original version
3205	* of "bmap", i.e., the one that corresponds to the current
3206	* state of info->tab. The number of constraints in info->bmap
3207	* is assumed to be the same as the number of constraints
3208	* in info->tab. This is required to be able to detect
3209	* the extra constraints in "bmap".
3210	*
3211	* Extract the positions where extra local variables are introduced
3212	* from "exp" and call tab_insert_divs.
3213	*/
3214	static isl_stat expand_tab(struct isl_coalesce_info *info, int *exp,
3215	__isl_take isl_basic_map *bmap)
3216	{
3217	isl_ctx *ctx;
3218	struct isl_expanded *expanded;
3219	int i, j, k, n;
3220	int extra_var;
3221	isl_size total, n_div;
3222	unsigned pos;
3223	isl_stat r;
3224
3225	total = isl_basic_map_dim(bmap, type: isl_dim_all);
3226	n_div = isl_basic_map_dim(bmap, type: isl_dim_div);
3227	if (total < 0 || n_div < 0)
3228	return isl_stat_error;
3229	pos = total - n_div;
3230	extra_var = total - info->tab->n_var;
3231	n = n_div - extra_var;
3232
3233	ctx = isl_basic_map_get_ctx(bmap);
3234	expanded = isl_calloc_array(ctx, struct isl_expanded, extra_var);
3235	if (extra_var && !expanded)
3236	goto error;
3237
3238	i = 0;
3239	k = 0;
3240	for (j = 0; j < n_div; ++j) {
3241	if (i < n && exp[i] == j) {
3242	++i;
3243	continue;
3244	}
3245	expanded[k++].pos = pos + j;
3246	}
3247
3248	for (k = 0; k < extra_var; ++k)
3249	isl_int_init(expanded[k].val);
3250
3251	r = tab_insert_divs(info, n: extra_var, expanded, bmap);
3252
3253	for (k = 0; k < extra_var; ++k)
3254	isl_int_clear(expanded[k].val);
3255	free(ptr: expanded);
3256
3257	return r;
3258	error:
3259	isl_basic_map_free(bmap);
3260	return isl_stat_error;
3261	}
3262
3263	/* Check if the union of the basic maps represented by info[i] and info[j]
3264	* can be represented by a single basic map,
3265	* after expanding the divs of info[i] to match those of info[j].
3266	* If so, replace the pair by the single basic map and return
3267	* isl_change_drop_first, isl_change_drop_second or isl_change_fuse.
3268	* Otherwise, return isl_change_none.
3269	*
3270	* The caller has already checked for info[j] being a subset of info[i].
3271	* If some of the divs of info[j] are unknown, then the expanded info[i]
3272	* will not have the corresponding div constraints. The other patterns
3273	* therefore cannot apply. Skip the computation in this case.
3274	*
3275	* The expansion is performed using the divs "div" and expansion "exp"
3276	* computed by the caller.
3277	* info[i].bmap has already been expanded and the result is passed in
3278	* as "bmap".
3279	* The "eq" and "ineq" fields of info[i] reflect the status of
3280	* the constraints of the expanded "bmap" with respect to info[j].tab.
3281	* However, inequality constraints that are redundant in info[i].tab
3282	* have not yet been marked as such because no tableau was available.
3283	*
3284	* Replace info[i].bmap by "bmap" and expand info[i].tab as well,
3285	* updating info[i].ineq with respect to the redundant constraints.
3286	* Then try and coalesce the expanded info[i] with info[j],
3287	* reusing the information in info[i].eq and info[i].ineq.
3288	* If this does not result in any coalescing or if it results in info[j]
3289	* getting dropped (which should not happen in practice, since the case
3290	* of info[j] being a subset of info[i] has already been checked by
3291	* the caller), then revert info[i] to its original state.
3292	*/
3293	static enum isl_change coalesce_expand_tab_divs(__isl_take isl_basic_map *bmap,
3294	int i, int j, struct isl_coalesce_info *info, __isl_keep isl_mat *div,
3295	int *exp)
3296	{
3297	isl_bool known;
3298	isl_basic_map *bmap_i;
3299	struct isl_tab_undo *snap;
3300	enum isl_change change = isl_change_none;
3301
3302	known = isl_basic_map_divs_known(bmap: info[j].bmap);
3303	if (known < 0 || !known) {
3304	clear_status(info: &info[i]);
3305	isl_basic_map_free(bmap);
3306	return known < 0 ? isl_change_error : isl_change_none;
3307	}
3308
3309	bmap_i = isl_basic_map_copy(bmap: info[i].bmap);
3310	snap = isl_tab_snap(tab: info[i].tab);
3311	if (expand_tab(info: &info[i], exp, bmap) < 0)
3312	change = isl_change_error;
3313
3314	init_status(info: &info[j]);
3315	if (change == isl_change_none)
3316	change = coalesce_local_pair_reuse(i, j, info);
3317	else
3318	clear_status(info: &info[i]);
3319	if (change != isl_change_none && change != isl_change_drop_second) {
3320	isl_basic_map_free(bmap: bmap_i);
3321	} else {
3322	isl_basic_map_free(bmap: info[i].bmap);
3323	info[i].bmap = bmap_i;
3324
3325	if (isl_tab_rollback(tab: info[i].tab, snap) < 0)
3326	change = isl_change_error;
3327	}
3328
3329	return change;
3330	}
3331
3332	/* Check if the union of "bmap" and the basic map represented by info[j]
3333	* can be represented by a single basic map,
3334	* after expanding the divs of "bmap" to match those of info[j].
3335	* If so, replace the pair by the single basic map and return
3336	* isl_change_drop_first, isl_change_drop_second or isl_change_fuse.
3337	* Otherwise, return isl_change_none.
3338	*
3339	* In particular, check if the expanded "bmap" contains the basic map
3340	* represented by the tableau info[j].tab.
3341	* The expansion is performed using the divs "div" and expansion "exp"
3342	* computed by the caller.
3343	* Then we check if all constraints of the expanded "bmap" are valid for
3344	* info[j].tab.
3345	*
3346	* If "i" is not equal to -1, then "bmap" is equal to info[i].bmap.
3347	* In this case, the positions of the constraints of info[i].bmap
3348	* with respect to the basic map represented by info[j] are stored
3349	* in info[i].
3350	*
3351	* If the expanded "bmap" does not contain the basic map
3352	* represented by the tableau info[j].tab and if "i" is not -1,
3353	* i.e., if the original "bmap" is info[i].bmap, then expand info[i].tab
3354	* as well and check if that results in coalescing.
3355	*/
3356	static enum isl_change coalesce_with_expanded_divs(
3357	__isl_keep isl_basic_map *bmap, int i, int j,
3358	struct isl_coalesce_info *info, __isl_keep isl_mat *div, int *exp)
3359	{
3360	enum isl_change change = isl_change_none;
3361	struct isl_coalesce_info info_local, *info_i;
3362
3363	info_i = i >= 0 ? &info[i] : &info_local;
3364	init_status(info: info_i);
3365	bmap = isl_basic_map_copy(bmap);
3366	bmap = isl_basic_map_expand_divs(bmap, div: isl_mat_copy(mat: div), exp);
3367	bmap = isl_basic_map_mark_final(bmap);
3368
3369	if (!bmap)
3370	goto error;
3371
3372	info_local.bmap = bmap;
3373	info_i->eq = eq_status_in(bmap_i: bmap, tab_j: info[j].tab);
3374	if (bmap->n_eq && !info_i->eq)
3375	goto error;
3376	if (any_eq(info: info_i, STATUS_ERROR))
3377	goto error;
3378	if (any_eq(info: info_i, STATUS_SEPARATE))
3379	goto done;
3380
3381	info_i->ineq = ineq_status_in(bmap_i: bmap, NULL, tab_j: info[j].tab);
3382	if (bmap->n_ineq && !info_i->ineq)
3383	goto error;
3384	if (any_ineq(info: info_i, STATUS_ERROR))
3385	goto error;
3386	if (any_ineq(info: info_i, STATUS_SEPARATE))
3387	goto done;
3388
3389	if (all(con: info_i->eq, len: 2 * bmap->n_eq, STATUS_VALID) &&
3390	all(con: info_i->ineq, len: bmap->n_ineq, STATUS_VALID)) {
3391	drop(info: &info[j]);
3392	change = isl_change_drop_second;
3393	}
3394
3395	if (change == isl_change_none && i != -1)
3396	return coalesce_expand_tab_divs(bmap, i, j, info, div, exp);
3397
3398	done:
3399	isl_basic_map_free(bmap);
3400	clear_status(info: info_i);
3401	return change;
3402	error:
3403	isl_basic_map_free(bmap);
3404	clear_status(info: info_i);
3405	return isl_change_error;
3406	}
3407
3408	/* Check if the union of "bmap_i" and the basic map represented by info[j]
3409	* can be represented by a single basic map,
3410	* after aligning the divs of "bmap_i" to match those of info[j].
3411	* If so, replace the pair by the single basic map and return
3412	* isl_change_drop_first, isl_change_drop_second or isl_change_fuse.
3413	* Otherwise, return isl_change_none.
3414	*
3415	* In particular, check if "bmap_i" contains the basic map represented by
3416	* info[j] after aligning the divs of "bmap_i" to those of info[j].
3417	* Note that this can only succeed if the number of divs of "bmap_i"
3418	* is smaller than (or equal to) the number of divs of info[j].
3419	*
3420	* We first check if the divs of "bmap_i" are all known and form a subset
3421	* of those of info[j].bmap. If so, we pass control over to
3422	* coalesce_with_expanded_divs.
3423	*
3424	* If "i" is not equal to -1, then "bmap" is equal to info[i].bmap.
3425	*/
3426	static enum isl_change coalesce_after_aligning_divs(
3427	__isl_keep isl_basic_map *bmap_i, int i, int j,
3428	struct isl_coalesce_info *info)
3429	{
3430	isl_bool known;
3431	isl_mat *div_i, *div_j, *div;
3432	int *exp1 = NULL;
3433	int *exp2 = NULL;
3434	isl_ctx *ctx;
3435	enum isl_change change;
3436
3437	known = isl_basic_map_divs_known(bmap: bmap_i);
3438	if (known < 0)
3439	return isl_change_error;
3440	if (!known)
3441	return isl_change_none;
3442
3443	ctx = isl_basic_map_get_ctx(bmap: bmap_i);
3444
3445	div_i = isl_basic_map_get_divs(bmap: bmap_i);
3446	div_j = isl_basic_map_get_divs(bmap: info[j].bmap);
3447
3448	if (!div_i || !div_j)
3449	goto error;
3450
3451	exp1 = isl_alloc_array(ctx, int, div_i->n_row);
3452	exp2 = isl_alloc_array(ctx, int, div_j->n_row);
3453	if ((div_i->n_row && !exp1) || (div_j->n_row && !exp2))
3454	goto error;
3455
3456	div = isl_merge_divs(div1: div_i, div2: div_j, exp1, exp2);
3457	if (!div)
3458	goto error;
3459
3460	if (div->n_row == div_j->n_row)
3461	change = coalesce_with_expanded_divs(bmap: bmap_i,
3462	i, j, info, div, exp: exp1);
3463	else
3464	change = isl_change_none;
3465
3466	isl_mat_free(mat: div);
3467
3468	isl_mat_free(mat: div_i);
3469	isl_mat_free(mat: div_j);
3470
3471	free(ptr: exp2);
3472	free(ptr: exp1);
3473
3474	return change;
3475	error:
3476	isl_mat_free(mat: div_i);
3477	isl_mat_free(mat: div_j);
3478	free(ptr: exp1);
3479	free(ptr: exp2);
3480	return isl_change_error;
3481	}
3482
3483	/* Check if basic map "j" is a subset of basic map "i" after
3484	* exploiting the extra equalities of "j" to simplify the divs of "i".
3485	* If so, remove basic map "j" and return isl_change_drop_second.
3486	*
3487	* If "j" does not have any equalities or if they are the same
3488	* as those of "i", then we cannot exploit them to simplify the divs.
3489	* Similarly, if there are no divs in "i", then they cannot be simplified.
3490	* If, on the other hand, the affine hulls of "i" and "j" do not intersect,
3491	* then "j" cannot be a subset of "i".
3492	*
3493	* Otherwise, we intersect "i" with the affine hull of "j" and then
3494	* check if "j" is a subset of the result after aligning the divs.
3495	* If so, then "j" is definitely a subset of "i" and can be removed.
3496	* Note that if after intersection with the affine hull of "j".
3497	* "i" still has more divs than "j", then there is no way we can
3498	* align the divs of "i" to those of "j".
3499	*/
3500	static enum isl_change coalesce_subset_with_equalities(int i, int j,
3501	struct isl_coalesce_info *info)
3502	{
3503	isl_basic_map *hull_i, *hull_j, *bmap_i;
3504	int equal, empty;
3505	enum isl_change change;
3506
3507	if (info[j].bmap->n_eq == 0)
3508	return isl_change_none;
3509	if (info[i].bmap->n_div == 0)
3510	return isl_change_none;
3511
3512	hull_i = isl_basic_map_copy(bmap: info[i].bmap);
3513	hull_i = isl_basic_map_plain_affine_hull(bmap: hull_i);
3514	hull_j = isl_basic_map_copy(bmap: info[j].bmap);
3515	hull_j = isl_basic_map_plain_affine_hull(bmap: hull_j);
3516
3517	hull_j = isl_basic_map_intersect(bmap1: hull_j, bmap2: isl_basic_map_copy(bmap: hull_i));
3518	equal = isl_basic_map_plain_is_equal(bmap1: hull_i, bmap2: hull_j);
3519	empty = isl_basic_map_plain_is_empty(bmap: hull_j);
3520	isl_basic_map_free(bmap: hull_i);
3521
3522	if (equal < 0 || equal || empty < 0 || empty) {
3523	isl_basic_map_free(bmap: hull_j);
3524	if (equal < 0 || empty < 0)
3525	return isl_change_error;
3526	return isl_change_none;
3527	}
3528
3529	bmap_i = isl_basic_map_copy(bmap: info[i].bmap);
3530	bmap_i = isl_basic_map_intersect(bmap1: bmap_i, bmap2: hull_j);
3531	if (!bmap_i)
3532	return isl_change_error;
3533
3534	if (bmap_i->n_div > info[j].bmap->n_div) {
3535	isl_basic_map_free(bmap: bmap_i);
3536	return isl_change_none;
3537	}
3538
3539	change = coalesce_after_aligning_divs(bmap_i, i: -1, j, info);
3540
3541	isl_basic_map_free(bmap: bmap_i);
3542
3543	return change;
3544	}
3545
3546	/* Check if the union of the basic maps represented by info[i] and info[j]
3547	* can be represented by a single basic map, by aligning or equating
3548	* their integer divisions.
3549	* If so, replace the pair by the single basic map and return
3550	* isl_change_drop_first, isl_change_drop_second or isl_change_fuse.
3551	* Otherwise, return isl_change_none.
3552	*
3553	* Note that we only perform any test if the number of divs is different
3554	* in the two basic maps. In case the number of divs is the same,
3555	* we have already established that the divs are different
3556	* in the two basic maps.
3557	* In particular, if the number of divs of basic map i is smaller than
3558	* the number of divs of basic map j, then we check if j is a subset of i
3559	* and vice versa.
3560	*/
3561	static enum isl_change coalesce_divs(int i, int j,
3562	struct isl_coalesce_info *info)
3563	{
3564	enum isl_change change = isl_change_none;
3565
3566	if (info[i].bmap->n_div < info[j].bmap->n_div)
3567	change = coalesce_after_aligning_divs(bmap_i: info[i].bmap, i, j, info);
3568	if (change != isl_change_none)
3569	return change;
3570
3571	if (info[j].bmap->n_div < info[i].bmap->n_div)
3572	change = coalesce_after_aligning_divs(bmap_i: info[j].bmap, i: j, j: i, info);
3573	if (change != isl_change_none)
3574	return invert_change(change);
3575
3576	change = coalesce_subset_with_equalities(i, j, info);
3577	if (change != isl_change_none)
3578	return change;
3579
3580	change = coalesce_subset_with_equalities(i: j, j: i, info);
3581	if (change != isl_change_none)
3582	return invert_change(change);
3583
3584	return isl_change_none;
3585	}
3586
3587	/* Does "bmap" involve any divs that themselves refer to divs?
3588	*/
3589	static isl_bool has_nested_div(__isl_keep isl_basic_map *bmap)
3590	{
3591	int i;
3592	isl_size total;
3593	isl_size n_div;
3594
3595	total = isl_basic_map_dim(bmap, type: isl_dim_all);
3596	n_div = isl_basic_map_dim(bmap, type: isl_dim_div);
3597	if (total < 0 || n_div < 0)
3598	return isl_bool_error;
3599	total -= n_div;
3600
3601	for (i = 0; i < n_div; ++i)
3602	if (isl_seq_first_non_zero(p: bmap->div[i] + 2 + total,
3603	len: n_div) != -1)
3604	return isl_bool_true;
3605
3606	return isl_bool_false;
3607	}
3608
3609	/* Return a list of affine expressions, one for each integer division
3610	* in "bmap_i". For each integer division that also appears in "bmap_j",
3611	* the affine expression is set to NaN. The number of NaNs in the list
3612	* is equal to the number of integer divisions in "bmap_j".
3613	* For the other integer divisions of "bmap_i", the corresponding
3614	* element in the list is a purely affine expression equal to the integer
3615	* division in "hull".
3616	* If no such list can be constructed, then the number of elements
3617	* in the returned list is smaller than the number of integer divisions
3618	* in "bmap_i".
3619	* The integer division of "bmap_i" and "bmap_j" are assumed to be known and
3620	* not contain any nested divs.
3621	*/
3622	static __isl_give isl_aff_list *set_up_substitutions(
3623	__isl_keep isl_basic_map *bmap_i, __isl_keep isl_basic_map *bmap_j,
3624	__isl_take isl_basic_map *hull)
3625	{
3626	isl_size n_div_i, n_div_j, total;
3627	isl_ctx *ctx;
3628	isl_local_space *ls;
3629	isl_basic_set *wrap_hull;
3630	isl_aff *aff_nan;
3631	isl_aff_list *list;
3632	int i, j;
3633
3634	n_div_i = isl_basic_map_dim(bmap: bmap_i, type: isl_dim_div);
3635	n_div_j = isl_basic_map_dim(bmap: bmap_j, type: isl_dim_div);
3636	total = isl_basic_map_dim(bmap: bmap_i, type: isl_dim_all);
3637	if (!hull || n_div_i < 0 || n_div_j < 0 || total < 0)
3638	return NULL;
3639
3640	ctx = isl_basic_map_get_ctx(bmap: hull);
3641	total -= n_div_i;
3642
3643	ls = isl_basic_map_get_local_space(bmap: bmap_i);
3644	ls = isl_local_space_wrap(ls);
3645	wrap_hull = isl_basic_map_wrap(bmap: hull);
3646
3647	aff_nan = isl_aff_nan_on_domain(ls: isl_local_space_copy(ls));
3648	list = isl_aff_list_alloc(ctx, n: n_div_i);
3649
3650	j = 0;
3651	for (i = 0; i < n_div_i; ++i) {
3652	isl_aff *aff;
3653	isl_size n_div;
3654
3655	if (j < n_div_j &&
3656	isl_basic_map_equal_div_expr_part(bmap1: bmap_i, pos1: i, bmap2: bmap_j, pos2: j,
3657	first: 0, n: 2 + total)) {
3658	++j;
3659	list = isl_aff_list_add(list, el: isl_aff_copy(aff: aff_nan));
3660	continue;
3661	}
3662	if (n_div_i - i <= n_div_j - j)
3663	break;
3664
3665	aff = isl_local_space_get_div(ls, pos: i);
3666	aff = isl_aff_substitute_equalities(aff,
3667	eq: isl_basic_set_copy(bset: wrap_hull));
3668	aff = isl_aff_floor(aff);
3669	n_div = isl_aff_dim(aff, type: isl_dim_div);
3670	if (n_div < 0)
3671	goto error;
3672	if (n_div != 0) {
3673	isl_aff_free(aff);
3674	break;
3675	}
3676
3677	list = isl_aff_list_add(list, el: aff);
3678	}
3679
3680	isl_aff_free(aff: aff_nan);
3681	isl_local_space_free(ls);
3682	isl_basic_set_free(bset: wrap_hull);
3683
3684	return list;
3685	error:
3686	isl_aff_free(aff: aff_nan);
3687	isl_local_space_free(ls);
3688	isl_basic_set_free(bset: wrap_hull);
3689	isl_aff_list_free(list);
3690	return NULL;
3691	}
3692
3693	/* Add variables to info->bmap and info->tab corresponding to the elements
3694	* in "list" that are not set to NaN.
3695	* "extra_var" is the number of these elements.
3696	* "dim" is the offset in the variables of "tab" where we should
3697	* start considering the elements in "list".
3698	* When this function returns, the total number of variables in "tab"
3699	* is equal to "dim" plus the number of elements in "list".
3700	*
3701	* The newly added existentially quantified variables are not given
3702	* an explicit representation because the corresponding div constraints
3703	* do not appear in info->bmap. These constraints are not added
3704	* to info->bmap because for internal consistency, they would need to
3705	* be added to info->tab as well, where they could combine with the equality
3706	* that is added later to result in constraints that do not hold
3707	* in the original input.
3708	*/
3709	static isl_stat add_sub_vars(struct isl_coalesce_info *info,
3710	__isl_keep isl_aff_list *list, int dim, int extra_var)
3711	{
3712	int i, j, d;
3713	isl_size n;
3714
3715	info->bmap = isl_basic_map_cow(bmap: info->bmap);
3716	info->bmap = isl_basic_map_extend(base: info->bmap, extra: extra_var, n_eq: 0, n_ineq: 0);
3717	n = isl_aff_list_n_aff(list);
3718	if (!info->bmap || n < 0)
3719	return isl_stat_error;
3720	for (i = 0; i < n; ++i) {
3721	int is_nan;
3722	isl_aff *aff;
3723
3724	aff = isl_aff_list_get_aff(list, index: i);
3725	is_nan = isl_aff_is_nan(aff);
3726	isl_aff_free(aff);
3727	if (is_nan < 0)
3728	return isl_stat_error;
3729	if (is_nan)
3730	continue;
3731
3732	if (isl_tab_insert_var(tab: info->tab, pos: dim + i) < 0)
3733	return isl_stat_error;
3734	d = isl_basic_map_alloc_div(bmap: info->bmap);
3735	if (d < 0)
3736	return isl_stat_error;
3737	info->bmap = isl_basic_map_mark_div_unknown(bmap: info->bmap, div: d);
3738	for (j = d; j > i; --j)
3739	info->bmap = isl_basic_map_swap_div(bmap: info->bmap,
3740	a: j - 1, b: j);
3741	if (!info->bmap)
3742	return isl_stat_error;
3743	}
3744
3745	return isl_stat_ok;
3746	}
3747
3748	/* For each element in "list" that is not set to NaN, fix the corresponding
3749	* variable in "tab" to the purely affine expression defined by the element.
3750	* "dim" is the offset in the variables of "tab" where we should
3751	* start considering the elements in "list".
3752	*
3753	* This function assumes that a sufficient number of rows and
3754	* elements in the constraint array are available in the tableau.
3755	*/
3756	static isl_stat add_sub_equalities(struct isl_tab *tab,
3757	__isl_keep isl_aff_list *list, int dim)
3758	{
3759	int i;
3760	isl_size n;
3761	isl_ctx *ctx;
3762	isl_vec *sub;
3763	isl_aff *aff;
3764
3765	n = isl_aff_list_n_aff(list);
3766	if (n < 0)
3767	return isl_stat_error;
3768
3769	ctx = isl_tab_get_ctx(tab);
3770	sub = isl_vec_alloc(ctx, size: 1 + dim + n);
3771	if (!sub)
3772	return isl_stat_error;
3773	isl_seq_clr(p: sub->el + 1 + dim, len: n);
3774
3775	for (i = 0; i < n; ++i) {
3776	aff = isl_aff_list_get_aff(list, index: i);
3777	if (!aff)
3778	goto error;
3779	if (isl_aff_is_nan(aff)) {
3780	isl_aff_free(aff);
3781	continue;
3782	}
3783	isl_seq_cpy(dst: sub->el, src: aff->v->el + 1, len: 1 + dim);
3784	isl_int_neg(sub->el[1 + dim + i], aff->v->el[0]);
3785	if (isl_tab_add_eq(tab, eq: sub->el) < 0)
3786	goto error;
3787	isl_int_set_si(sub->el[1 + dim + i], 0);
3788	isl_aff_free(aff);
3789	}
3790
3791	isl_vec_free(vec: sub);
3792	return isl_stat_ok;
3793	error:
3794	isl_aff_free(aff);
3795	isl_vec_free(vec: sub);
3796	return isl_stat_error;
3797	}
3798
3799	/* Add variables to info->tab and info->bmap corresponding to the elements
3800	* in "list" that are not set to NaN. The value of the added variable
3801	* in info->tab is fixed to the purely affine expression defined by the element.
3802	* "dim" is the offset in the variables of info->tab where we should
3803	* start considering the elements in "list".
3804	* When this function returns, the total number of variables in info->tab
3805	* is equal to "dim" plus the number of elements in "list".
3806	*/
3807	static isl_stat add_subs(struct isl_coalesce_info *info,
3808	__isl_keep isl_aff_list *list, int dim)
3809	{
3810	int extra_var;
3811	isl_size n;
3812
3813	n = isl_aff_list_n_aff(list);
3814	if (n < 0)
3815	return isl_stat_error;
3816
3817	extra_var = n - (info->tab->n_var - dim);
3818
3819	if (isl_tab_extend_vars(tab: info->tab, n_new: extra_var) < 0)
3820	return isl_stat_error;
3821	if (isl_tab_extend_cons(tab: info->tab, n_new: 2 * extra_var) < 0)
3822	return isl_stat_error;
3823	if (add_sub_vars(info, list, dim, extra_var) < 0)
3824	return isl_stat_error;
3825
3826	return add_sub_equalities(tab: info->tab, list, dim);
3827	}
3828
3829	/* Coalesce basic map "j" into basic map "i" after adding the extra integer
3830	* divisions in "i" but not in "j" to basic map "j", with values
3831	* specified by "list". The total number of elements in "list"
3832	* is equal to the number of integer divisions in "i", while the number
3833	* of NaN elements in the list is equal to the number of integer divisions
3834	* in "j".
3835	*
3836	* If no coalescing can be performed, then we need to revert basic map "j"
3837	* to its original state. We do the same if basic map "i" gets dropped
3838	* during the coalescing, even though this should not happen in practice
3839	* since we have already checked for "j" being a subset of "i"
3840	* before we reach this stage.
3841	*/
3842	static enum isl_change coalesce_with_subs(int i, int j,
3843	struct isl_coalesce_info *info, __isl_keep isl_aff_list *list)
3844	{
3845	isl_basic_map *bmap_j;
3846	struct isl_tab_undo *snap;
3847	isl_size dim, n_div;
3848	enum isl_change change;
3849
3850	bmap_j = isl_basic_map_copy(bmap: info[j].bmap);
3851	snap = isl_tab_snap(tab: info[j].tab);
3852
3853	dim = isl_basic_map_dim(bmap: bmap_j, type: isl_dim_all);
3854	n_div = isl_basic_map_dim(bmap: bmap_j, type: isl_dim_div);
3855	if (dim < 0 || n_div < 0)
3856	goto error;
3857	dim -= n_div;
3858	if (add_subs(info: &info[j], list, dim) < 0)
3859	goto error;
3860
3861	change = coalesce_local_pair(i, j, info);
3862	if (change != isl_change_none && change != isl_change_drop_first) {
3863	isl_basic_map_free(bmap: bmap_j);
3864	} else {
3865	isl_basic_map_free(bmap: info[j].bmap);
3866	info[j].bmap = bmap_j;
3867
3868	if (isl_tab_rollback(tab: info[j].tab, snap) < 0)
3869	return isl_change_error;
3870	}
3871
3872	return change;
3873	error:
3874	isl_basic_map_free(bmap: bmap_j);
3875	return isl_change_error;
3876	}
3877
3878	/* Check if we can coalesce basic map "j" into basic map "i" after copying
3879	* those extra integer divisions in "i" that can be simplified away
3880	* using the extra equalities in "j".
3881	* All divs are assumed to be known and not contain any nested divs.
3882	*
3883	* We first check if there are any extra equalities in "j" that we
3884	* can exploit. Then we check if every integer division in "i"
3885	* either already appears in "j" or can be simplified using the
3886	* extra equalities to a purely affine expression.
3887	* If these tests succeed, then we try to coalesce the two basic maps
3888	* by introducing extra dimensions in "j" corresponding to
3889	* the extra integer divisions "i" fixed to the corresponding
3890	* purely affine expression.
3891	*/
3892	static enum isl_change check_coalesce_into_eq(int i, int j,
3893	struct isl_coalesce_info *info)
3894	{
3895	isl_size n_div_i, n_div_j, n;
3896	isl_basic_map *hull_i, *hull_j;
3897	isl_bool equal, empty;
3898	isl_aff_list *list;
3899	enum isl_change change;
3900
3901	n_div_i = isl_basic_map_dim(bmap: info[i].bmap, type: isl_dim_div);
3902	n_div_j = isl_basic_map_dim(bmap: info[j].bmap, type: isl_dim_div);
3903	if (n_div_i < 0 || n_div_j < 0)
3904	return isl_change_error;
3905	if (n_div_i <= n_div_j)
3906	return isl_change_none;
3907	if (info[j].bmap->n_eq == 0)
3908	return isl_change_none;
3909
3910	hull_i = isl_basic_map_copy(bmap: info[i].bmap);
3911	hull_i = isl_basic_map_plain_affine_hull(bmap: hull_i);
3912	hull_j = isl_basic_map_copy(bmap: info[j].bmap);
3913	hull_j = isl_basic_map_plain_affine_hull(bmap: hull_j);
3914
3915	hull_j = isl_basic_map_intersect(bmap1: hull_j, bmap2: isl_basic_map_copy(bmap: hull_i));
3916	equal = isl_basic_map_plain_is_equal(bmap1: hull_i, bmap2: hull_j);
3917	empty = isl_basic_map_plain_is_empty(bmap: hull_j);
3918	isl_basic_map_free(bmap: hull_i);
3919
3920	if (equal < 0 || empty < 0)
3921	goto error;
3922	if (equal || empty) {
3923	isl_basic_map_free(bmap: hull_j);
3924	return isl_change_none;
3925	}
3926
3927	list = set_up_substitutions(bmap_i: info[i].bmap, bmap_j: info[j].bmap, hull: hull_j);
3928	if (!list)
3929	return isl_change_error;
3930	n = isl_aff_list_n_aff(list);
3931	if (n < 0)
3932	change = isl_change_error;
3933	else if (n < n_div_i)
3934	change = isl_change_none;
3935	else
3936	change = coalesce_with_subs(i, j, info, list);
3937
3938	isl_aff_list_free(list);
3939
3940	return change;
3941	error:
3942	isl_basic_map_free(bmap: hull_j);
3943	return isl_change_error;
3944	}
3945
3946	/* Check if we can coalesce basic maps "i" and "j" after copying
3947	* those extra integer divisions in one of the basic maps that can
3948	* be simplified away using the extra equalities in the other basic map.
3949	* We require all divs to be known in both basic maps.
3950	* Furthermore, to simplify the comparison of div expressions,
3951	* we do not allow any nested integer divisions.
3952	*/
3953	static enum isl_change check_coalesce_eq(int i, int j,
3954	struct isl_coalesce_info *info)
3955	{
3956	isl_bool known, nested;
3957	enum isl_change change;
3958
3959	known = isl_basic_map_divs_known(bmap: info[i].bmap);
3960	if (known < 0 || !known)
3961	return known < 0 ? isl_change_error : isl_change_none;
3962	known = isl_basic_map_divs_known(bmap: info[j].bmap);
3963	if (known < 0 || !known)
3964	return known < 0 ? isl_change_error : isl_change_none;
3965	nested = has_nested_div(bmap: info[i].bmap);
3966	if (nested < 0 || nested)
3967	return nested < 0 ? isl_change_error : isl_change_none;
3968	nested = has_nested_div(bmap: info[j].bmap);
3969	if (nested < 0 || nested)
3970	return nested < 0 ? isl_change_error : isl_change_none;
3971
3972	change = check_coalesce_into_eq(i, j, info);
3973	if (change != isl_change_none)
3974	return change;
3975	change = check_coalesce_into_eq(i: j, j: i, info);
3976	if (change != isl_change_none)
3977	return invert_change(change);
3978
3979	return isl_change_none;
3980	}
3981
3982	/* Check if the union of the given pair of basic maps
3983	* can be represented by a single basic map.
3984	* If so, replace the pair by the single basic map and return
3985	* isl_change_drop_first, isl_change_drop_second or isl_change_fuse.
3986	* Otherwise, return isl_change_none.
3987	*
3988	* We first check if the two basic maps live in the same local space,
3989	* after aligning the divs that differ by only an integer constant.
3990	* If so, we do the complete check. Otherwise, we check if they have
3991	* the same number of integer divisions and can be coalesced, if one is
3992	* an obvious subset of the other or if the extra integer divisions
3993	* of one basic map can be simplified away using the extra equalities
3994	* of the other basic map.
3995	*
3996	* Note that trying to coalesce pairs of disjuncts with the same
3997	* number, but different local variables may drop the explicit
3998	* representation of some of these local variables.
3999	* This operation is therefore not performed when
4000	* the "coalesce_preserve_locals" option is set.
4001	*/
4002	static enum isl_change coalesce_pair(int i, int j,
4003	struct isl_coalesce_info *info)
4004	{
4005	int preserve;
4006	isl_bool same;
4007	enum isl_change change;
4008	isl_ctx *ctx;
4009
4010	if (harmonize_divs(info1: &info[i], info2: &info[j]) < 0)
4011	return isl_change_error;
4012	same = same_divs(bmap1: info[i].bmap, bmap2: info[j].bmap);
4013	if (same < 0)
4014	return isl_change_error;
4015	if (same)
4016	return coalesce_local_pair(i, j, info);
4017
4018	ctx = isl_basic_map_get_ctx(bmap: info[i].bmap);
4019	preserve = isl_options_get_coalesce_preserve_locals(ctx);
4020	if (!preserve && info[i].bmap->n_div == info[j].bmap->n_div) {
4021	change = coalesce_local_pair(i, j, info);
4022	if (change != isl_change_none)
4023	return change;
4024	}
4025
4026	change = coalesce_divs(i, j, info);
4027	if (change != isl_change_none)
4028	return change;
4029
4030	return check_coalesce_eq(i, j, info);
4031	}
4032
4033	/* Return the maximum of "a" and "b".
4034	*/
4035	static int isl_max(int a, int b)
4036	{
4037	return a > b ? a : b;
4038	}
4039
4040	/* Pairwise coalesce the basic maps in the range [start1, end1[ of "info"
4041	* with those in the range [start2, end2[, skipping basic maps
4042	* that have been removed (either before or within this function).
4043	*
4044	* For each basic map i in the first range, we check if it can be coalesced
4045	* with respect to any previously considered basic map j in the second range.
4046	* If i gets dropped (because it was a subset of some j), then
4047	* we can move on to the next basic map.
4048	* If j gets dropped, we need to continue checking against the other
4049	* previously considered basic maps.
4050	* If the two basic maps got fused, then we recheck the fused basic map
4051	* against the previously considered basic maps, starting at i + 1
4052	* (even if start2 is greater than i + 1).
4053	*/
4054	static int coalesce_range(isl_ctx *ctx, struct isl_coalesce_info *info,
4055	int start1, int end1, int start2, int end2)
4056	{
4057	int i, j;
4058
4059	for (i = end1 - 1; i >= start1; --i) {
4060	if (info[i].removed)
4061	continue;
4062	for (j = isl_max(a: i + 1, b: start2); j < end2; ++j) {
4063	enum isl_change changed;
4064
4065	if (info[j].removed)
4066	continue;
4067	if (info[i].removed)
4068	isl_die(ctx, isl_error_internal,
4069	"basic map unexpectedly removed",
4070	return -1);
4071	changed = coalesce_pair(i, j, info);
4072	switch (changed) {
4073	case isl_change_error:
4074	return -1;
4075	case isl_change_none:
4076	case isl_change_drop_second:
4077	continue;
4078	case isl_change_drop_first:
4079	j = end2;
4080	break;
4081	case isl_change_fuse:
4082	j = i;
4083	break;
4084	}
4085	}
4086	}
4087
4088	return 0;
4089	}
4090
4091	/* Pairwise coalesce the basic maps described by the "n" elements of "info".
4092	*
4093	* We consider groups of basic maps that live in the same apparent
4094	* affine hull and we first coalesce within such a group before we
4095	* coalesce the elements in the group with elements of previously
4096	* considered groups. If a fuse happens during the second phase,
4097	* then we also reconsider the elements within the group.
4098	*/
4099	static int coalesce(isl_ctx *ctx, int n, struct isl_coalesce_info *info)
4100	{
4101	int start, end;
4102
4103	for (end = n; end > 0; end = start) {
4104	start = end - 1;
4105	while (start >= 1 &&
4106	info[start - 1].hull_hash == info[start].hull_hash)
4107	start--;
4108	if (coalesce_range(ctx, info, start1: start, end1: end, start2: start, end2: end) < 0)
4109	return -1;
4110	if (coalesce_range(ctx, info, start1: start, end1: end, start2: end, end2: n) < 0)
4111	return -1;
4112	}
4113
4114	return 0;
4115	}
4116
4117	/* Update the basic maps in "map" based on the information in "info".
4118	* In particular, remove the basic maps that have been marked removed and
4119	* update the others based on the information in the corresponding tableau.
4120	* Since we detected implicit equalities without calling
4121	* isl_basic_map_gauss, we need to do it now.
4122	* Also call isl_basic_map_simplify if we may have lost the definition
4123	* of one or more integer divisions.
4124	* If a basic map is still equal to the one from which the corresponding "info"
4125	* entry was created, then redundant constraint and
4126	* implicit equality constraint detection have been performed
4127	* on the corresponding tableau and the basic map can be marked as such.
4128	*/
4129	static __isl_give isl_map *update_basic_maps(__isl_take isl_map *map,
4130	int n, struct isl_coalesce_info *info)
4131	{
4132	int i;
4133
4134	if (!map)
4135	return NULL;
4136
4137	for (i = n - 1; i >= 0; --i) {
4138	if (info[i].removed) {
4139	isl_basic_map_free(bmap: map->p[i]);
4140	if (i != map->n - 1)
4141	map->p[i] = map->p[map->n - 1];
4142	map->n--;
4143	continue;
4144	}
4145
4146	info[i].bmap = isl_basic_map_update_from_tab(bmap: info[i].bmap,
4147	tab: info[i].tab);
4148	info[i].bmap = isl_basic_map_gauss(bmap: info[i].bmap, NULL);
4149	if (info[i].simplify)
4150	info[i].bmap = isl_basic_map_simplify(bmap: info[i].bmap);
4151	info[i].bmap = isl_basic_map_finalize(bmap: info[i].bmap);
4152	if (!info[i].bmap)
4153	return isl_map_free(map);
4154	if (!info[i].modified) {
4155	ISL_F_SET(info[i].bmap, ISL_BASIC_MAP_NO_IMPLICIT);
4156	ISL_F_SET(info[i].bmap, ISL_BASIC_MAP_NO_REDUNDANT);
4157	}
4158	isl_basic_map_free(bmap: map->p[i]);
4159	map->p[i] = info[i].bmap;
4160	info[i].bmap = NULL;
4161	}
4162
4163	return map;
4164	}
4165
4166	/* For each pair of basic maps in the map, check if the union of the two
4167	* can be represented by a single basic map.
4168	* If so, replace the pair by the single basic map and start over.
4169	*
4170	* We factor out any (hidden) common factor from the constraint
4171	* coefficients to improve the detection of adjacent constraints.
4172	* Note that this function does not call isl_basic_map_gauss,
4173	* but it does make sure that only a single copy of the basic map
4174	* is affected. This means that isl_basic_map_gauss may have
4175	* to be called at the end of the computation (in update_basic_maps)
4176	* on this single copy to ensure that
4177	* the basic maps are not left in an unexpected state.
4178	*
4179	* Since we are constructing the tableaus of the basic maps anyway,
4180	* we exploit them to detect implicit equalities and redundant constraints.
4181	* This also helps the coalescing as it can ignore the redundant constraints.
4182	* In order to avoid confusion, we make all implicit equalities explicit
4183	* in the basic maps. If the basic map only has a single reference
4184	* (this happens in particular if it was modified by
4185	* isl_basic_map_reduce_coefficients), then isl_basic_map_gauss
4186	* does not get called on the result. The call to
4187	* isl_basic_map_gauss in update_basic_maps resolves this as well.
4188	* For each basic map, we also compute the hash of the apparent affine hull
4189	* for use in coalesce.
4190	*/
4191	__isl_give isl_map *isl_map_coalesce(__isl_take isl_map *map)
4192	{
4193	int i;
4194	unsigned n;
4195	isl_ctx *ctx;
4196	struct isl_coalesce_info *info = NULL;
4197
4198	map = isl_map_remove_empty_parts(map);
4199	if (!map)
4200	return NULL;
4201
4202	if (map->n <= 1)
4203	return map;
4204
4205	ctx = isl_map_get_ctx(map);
4206	map = isl_map_sort_divs(map);
4207	map = isl_map_cow(map);
4208
4209	if (!map)
4210	return NULL;
4211
4212	n = map->n;
4213
4214	info = isl_calloc_array(map->ctx, struct isl_coalesce_info, n);
4215	if (!info)
4216	goto error;
4217
4218	for (i = 0; i < map->n; ++i) {
4219	map->p[i] = isl_basic_map_reduce_coefficients(bmap: map->p[i]);
4220	if (!map->p[i])
4221	goto error;
4222	info[i].bmap = isl_basic_map_copy(bmap: map->p[i]);
4223	info[i].tab = isl_tab_from_basic_map(bmap: info[i].bmap, track: 0);
4224	if (!info[i].tab)
4225	goto error;
4226	if (!ISL_F_ISSET(info[i].bmap, ISL_BASIC_MAP_NO_IMPLICIT))
4227	if (isl_tab_detect_implicit_equalities(tab: info[i].tab) < 0)
4228	goto error;
4229	info[i].bmap = isl_tab_make_equalities_explicit(tab: info[i].tab,
4230	bmap: info[i].bmap);
4231	if (!info[i].bmap)
4232	goto error;
4233	if (!ISL_F_ISSET(info[i].bmap, ISL_BASIC_MAP_NO_REDUNDANT))
4234	if (isl_tab_detect_redundant(tab: info[i].tab) < 0)
4235	goto error;
4236	if (coalesce_info_set_hull_hash(info: &info[i]) < 0)
4237	goto error;
4238	}
4239	for (i = map->n - 1; i >= 0; --i)
4240	if (info[i].tab->empty)
4241	drop(info: &info[i]);
4242
4243	if (coalesce(ctx, n, info) < 0)
4244	goto error;
4245
4246	map = update_basic_maps(map, n, info);
4247
4248	clear_coalesce_info(n, info);
4249
4250	return map;
4251	error:
4252	clear_coalesce_info(n, info);
4253	isl_map_free(map);
4254	return NULL;
4255	}
4256
4257	/* For each pair of basic sets in the set, check if the union of the two
4258	* can be represented by a single basic set.
4259	* If so, replace the pair by the single basic set and start over.
4260	*/
4261	__isl_give isl_set *isl_set_coalesce(__isl_take isl_set *set)
4262	{
4263	return set_from_map(isl_map_coalesce(map: set_to_map(set)));
4264	}
4265