xref: /llvm-project/polly/lib/External/isl/isl_coalesce.c (revision a749e09e184b2b0b6dde71af01c82dd427b3e3e2)
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 
status_in(isl_int * ineq,struct isl_tab * tab)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  */
eq_status_in(__isl_keep isl_basic_map * bmap_i,struct isl_tab * tab_j)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_i, 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(bmap_i->eq[k], bmap_i->eq[k], 1+dim);
85 			eq[2 * k + l] = status_in(bmap_i->eq[k], tab_j);
86 			if (eq[2 * k + l] == STATUS_ERROR)
87 				goto error;
88 		}
89 	}
90 
91 	return eq;
92 error:
93 	free(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  */
ineq_status_in(__isl_keep isl_basic_map * bmap_i,struct isl_tab * tab_i,struct isl_tab * tab_j)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_i, n_eq + k)) {
113 			ineq[k] = STATUS_REDUNDANT;
114 			continue;
115 		}
116 		ineq[k] = status_in(bmap_i->ineq[k], 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(ineq);
126 	return NULL;
127 }
128 
any(int * con,unsigned len,int status)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  */
find(int * con,unsigned len,int status)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 
count(int * con,unsigned len,int status)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 
all(int * con,unsigned len,int status)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  */
any_eq(struct isl_coalesce_info * info,int status)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(info->bmap);
217 	return any(info->eq, 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  */
any_ineq(struct isl_coalesce_info * info,int status)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(info->bmap);
229 	return any(info->ineq, 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  */
find_eq(struct isl_coalesce_info * info,int status)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(info->bmap);
244 	return find(info->eq, 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  */
find_ineq(struct isl_coalesce_info * info,int status)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(info->bmap);
257 	return find(info->ineq, 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  */
count_eq(struct isl_coalesce_info * info,int status)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(info->bmap);
269 	return count(info->eq, 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  */
count_ineq(struct isl_coalesce_info * info,int status)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(info->bmap);
281 	return count(info->ineq, 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  */
all_valid_or_cut(struct isl_coalesce_info * info)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  */
coalesce_info_set_hull_hash(struct isl_coalesce_info * info)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(info->bmap);
324 	hull = isl_basic_map_plain_affine_hull(hull);
325 	n_div = isl_basic_map_dim(hull, isl_dim_div);
326 	if (n_div < 0)
327 		hull = isl_basic_map_free(hull);
328 	hull = isl_basic_map_drop_constraints_involving_dims(hull,
329 							isl_dim_div, 0, n_div);
330 	info->hull_hash = isl_basic_map_get_hash(hull);
331 	isl_basic_map_free(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  */
clear_coalesce_info(int n,struct isl_coalesce_info * info)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(info[i].bmap);
348 		isl_tab_free(info[i].tab);
349 	}
350 
351 	free(info);
352 }
353 
354 /* Clear the memory associated to "info".
355  */
clear(struct isl_coalesce_info * info)356 static void clear(struct isl_coalesce_info *info)
357 {
358 	info->bmap = isl_basic_map_free(info->bmap);
359 	isl_tab_free(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  */
drop(struct isl_coalesce_info * info)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  */
exchange(struct isl_coalesce_info * info1,struct isl_coalesce_info * info2)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  */
invert_change(enum isl_change change)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  */
add_valid_constraints(__isl_take isl_basic_map * bmap,struct isl_coalesce_info * info,unsigned len)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(bmap->eq[l], 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(bmap->ineq[l], 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(bmap->ineq[l], 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(bmap->ineq[l], 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  */
number_of_constraints_increases(int i,int j,struct isl_coalesce_info * info,__isl_keep isl_basic_map * bmap,struct isl_tab * tab)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, 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  */
fuse(int i,int j,struct isl_coalesce_info * info,__isl_keep isl_mat * extra,int detect_equalities,int check_number)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(info[i].bmap, 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(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(isl_space_copy(info[i].bmap->dim),
530 		    info[i].bmap->n_div, n_eq, n_eq + n_ineq + extra_rows);
531 	fused = add_valid_constraints(fused, &info[i], 1 + total);
532 	fused = add_valid_constraints(fused, &info[j], 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(fused);
541 		if (l < 0)
542 			goto error;
543 		if (isl_seq_eq(info[i].bmap->div[k], info[j].bmap->div[k],
544 				1 + 1 + total)) {
545 			isl_seq_cpy(fused->div[l], info[i].bmap->div[k],
546 				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(fused);
555 		if (l < 0)
556 			goto error;
557 		isl_seq_cpy(fused->ineq[l], extra->row[k], 1 + total);
558 	}
559 
560 	if (detect_equalities)
561 		fused = isl_basic_map_detect_inequality_pairs(fused, NULL);
562 	fused = isl_basic_map_gauss(fused, NULL);
563 	if (simplify || info[j].simplify) {
564 		fused = isl_basic_map_simplify(fused);
565 		info[i].simplify = 0;
566 	} else if (extra_rows > 0) {
567 		fused = isl_basic_map_eliminate_pure_unit_divs(fused);
568 	}
569 	fused = isl_basic_map_finalize(fused);
570 
571 	fused_tab = isl_tab_from_basic_map(fused, 0);
572 	if (isl_tab_detect_redundant(fused_tab) < 0)
573 		goto error;
574 
575 	if (check_number &&
576 	    number_of_constraints_increases(i, j, info, fused, fused_tab)) {
577 		isl_tab_free(fused_tab);
578 		isl_basic_map_free(fused);
579 		return isl_change_none;
580 	}
581 
582 	clear(&info[i]);
583 	info[i].bmap = fused;
584 	info[i].tab = fused_tab;
585 	info[i].modified = 1;
586 	drop(&info[j]);
587 
588 	return isl_change_fuse;
589 error:
590 	isl_tab_free(fused_tab);
591 	isl_basic_map_free(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  */
check_facets(int i,int j,struct isl_coalesce_info * info)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(info[i].tab);
632 	if (isl_tab_mark_rational(info[i].tab) < 0)
633 		return isl_change_error;
634 	snap2 = isl_tab_snap(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(info[i].tab, 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(info[j].bmap->ineq[l], 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(info[i].tab, 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(info[i].tab, snap) < 0)
659 			return isl_change_error;
660 		return isl_change_none;
661 	}
662 	return fuse(i, j, info, NULL, 0, 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  */
contains(struct isl_coalesce_info * info,struct isl_tab * tab)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, 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(bmap->eq[k], bmap->eq[k], 1 + dim);
683 		stat = status_in(bmap->eq[k], tab);
684 		isl_seq_neg(bmap->eq[k], bmap->eq[k], 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(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(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  */
is_adj_ineq_extension_with_wraps(int i,int j,int k,struct isl_coalesce_info * info,__isl_keep isl_mat * extra)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(info[i].bmap, 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(info[i].bmap);
773 	n_ineq_j = isl_basic_map_n_inequality(info[j].bmap);
774 	n_extra = isl_mat_rows(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(info[i].tab, 1 + n_ineq_j + n_extra) < 0)
779 		return isl_change_error;
780 
781 	snap = isl_tab_snap(info[i].tab);
782 
783 	if (isl_tab_unrestrict(info[i].tab, n_eq_i + k) < 0)
784 		return isl_change_error;
785 
786 	isl_seq_neg(info[i].bmap->ineq[k], info[i].bmap->ineq[k], 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(info[i].tab, info[i].bmap->ineq[k]);
789 	isl_seq_neg(info[i].bmap->ineq[k], info[i].bmap->ineq[k], 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(info[i].tab, 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(info[i].tab, extra->row[k]) < 0)
802 			return isl_change_error;
803 	}
804 	if (isl_tab_detect_constants(info[i].tab) < 0)
805 		return isl_change_error;
806 
807 	super = contains(&info[j], info[i].tab);
808 	if (super < 0)
809 		return isl_change_error;
810 	if (super)
811 		return fuse(i, j, info, extra, 0, 0);
812 
813 	if (isl_tab_rollback(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  */
not_unique_unit_row(__isl_keep isl_mat * T,int row)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(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(T->row[row] + 1 + i + 1, 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  */
is_affected(__isl_keep isl_basic_map * bmap,int ineq,int * affected,int total)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  */
try_tightening(struct isl_coalesce_info * info,int ineq,__isl_take isl_vec * v)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(v);
903 	isl_seq_gcd(v->el + 1, v->size - 1, &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(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(info->tab, 1) < 0)
918 		return isl_vec_free(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(info->tab, 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(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  */
tighten_on_relaxed_facet(struct isl_coalesce_info * info,int n,int * relaxed,int l)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(info->bmap);
982 	total = isl_basic_map_dim(info->bmap, 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, info->bmap->ineq, k, 1, 0, 1 + total);
987 	T = isl_mat_variable_compression(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(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, 1 + i);
1002 
1003 	for (i = 0; i < info->bmap->n_ineq; ++i) {
1004 		isl_bool handle;
1005 		if (any(relaxed, n, i))
1006 			continue;
1007 		if (info->ineq[i] == STATUS_REDUNDANT)
1008 			continue;
1009 		handle = is_affected(info->bmap, i, affected, total);
1010 		if (handle < 0)
1011 			goto error;
1012 		if (!handle)
1013 			continue;
1014 		v = isl_vec_alloc(ctx, 1 + total);
1015 		if (!v)
1016 			goto error;
1017 		isl_seq_cpy(v->el, info->bmap->ineq[i], 1 + total);
1018 		v = isl_vec_mat_product(v, isl_mat_copy(T));
1019 		v = try_tightening(info, i, v);
1020 		isl_vec_free(v);
1021 		if (!v)
1022 			goto error;
1023 	}
1024 
1025 	isl_mat_free(T);
1026 	free(affected);
1027 	return isl_stat_ok;
1028 error:
1029 	isl_mat_free(T);
1030 	free(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  */
extend(int i,int j,int n,int * relax,struct isl_coalesce_info * info)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(info[i].bmap);
1052 	total = isl_basic_map_dim(info[i].bmap, 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(info[i].bmap->div[l],
1057 				info[j].bmap->div[l], 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[j]);
1067 	info[i].modified = 1;
1068 	if (j < i)
1069 		exchange(&info[i], &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  */
is_relaxed_extension(int i,int j,int n,int * relax,struct isl_coalesce_info * info)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(info[i].tab, n_eq + relax[l]))
1127 			return isl_change_none;
1128 
1129 	snap = isl_tab_snap(info[i].tab);
1130 	for (l = 0; l < n; ++l)
1131 		if (isl_tab_relax(info[i].tab, n_eq + relax[l]) < 0)
1132 			return isl_change_error;
1133 	for (l = 0; l < n; ++l) {
1134 		if (!isl_tab_is_redundant(info[i].tab, n_eq + relax[l]))
1135 			continue;
1136 		if (isl_tab_rollback(info[i].tab, snap) < 0)
1137 			return isl_change_error;
1138 		return isl_change_none;
1139 	}
1140 	snap2 = isl_tab_snap(info[i].tab);
1141 	for (l = 0; l < n; ++l) {
1142 		if (isl_tab_rollback(info[i].tab, snap2) < 0)
1143 			return isl_change_error;
1144 		if (isl_tab_select_facet(info[i].tab, n_eq + relax[l]) < 0)
1145 			return isl_change_error;
1146 		if (tighten_on_relaxed_facet(&info[i], n, relax, l) < 0)
1147 			return isl_change_error;
1148 		super = contains(&info[j], info[i].tab);
1149 		if (super < 0)
1150 			return isl_change_error;
1151 		if (super)
1152 			continue;
1153 		if (isl_tab_rollback(info[i].tab, snap) < 0)
1154 			return isl_change_error;
1155 		return isl_change_none;
1156 	}
1157 
1158 	if (isl_tab_rollback(info[i].tab, 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  */
wraps_update_max(struct isl_wraps * wraps,struct isl_coalesce_info * info)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(info->bmap, 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(info->bmap->eq[k] + 1, total, &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(info->bmap->ineq[k] + 1, total, &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  */
wraps_init(struct isl_wraps * wraps,__isl_take isl_mat * mat,struct isl_coalesce_info * info,int i,int j)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[i]) < 0)
1240 		return isl_stat_error;
1241 	if (wraps_update_max(wraps, &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  */
wraps_free(struct isl_wraps * wraps)1249 static void wraps_free(struct isl_wraps *wraps)
1250 {
1251 	isl_mat_free(wraps->mat);
1252 	if (wraps->bound)
1253 		isl_int_clear(wraps->max);
1254 }
1255 
1256 /* Mark the wrapping as failed.
1257  */
wraps_mark_failed(struct isl_wraps * wraps)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  */
allow_wrap(struct isl_wraps * wraps,int row)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  */
add_wrap(struct isl_wraps * wraps,int w,isl_int * bound,isl_int * ineq,unsigned len,__isl_keep isl_set * set,int negate)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(wraps->mat->row[w], bound, len);
1295 	if (negate) {
1296 		isl_seq_neg(wraps->mat->row[w + 1], ineq, len);
1297 		ineq = wraps->mat->row[w + 1];
1298 	}
1299 	if (!isl_set_wrap_facet(set, wraps->mat->row[w], ineq))
1300 		return -1;
1301 	if (isl_seq_eq(wraps->mat->row[w], bound, len))
1302 		return 0;
1303 	if (!allow_wrap(wraps, 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  */
add_selected_wraps(struct isl_wraps * wraps,struct isl_coalesce_info * info,isl_int * bound,__isl_keep isl_set * set,int add_valid)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, 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(bound, bmap->ineq[l], len))
1363 			continue;
1364 		if (isl_seq_eq(bound, bmap->ineq[l], len))
1365 			continue;
1366 		if (isl_tab_is_redundant(info->tab, bmap->n_eq + l))
1367 			continue;
1368 
1369 		added = add_wrap(wraps, w, bound, bmap->ineq[l], len, set, 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(bound, bmap->eq[l], len))
1379 			continue;
1380 		if (isl_seq_eq(bound, 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, bmap->eq[l], len,
1387 					set, !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  */
add_wraps(struct isl_wraps * wraps,struct isl_coalesce_info * info,isl_int * bound,__isl_keep isl_set * set)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, 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  */
check_wraps(struct isl_wraps * wraps,int first,struct isl_tab * tab,int keep)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, 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(wraps->mat, i, 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  */
set_from_updated_bmap(__isl_keep isl_basic_map * bmap,struct isl_tab * tab)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  */
has_redundant_cuts(struct isl_coalesce_info * info)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(info->bmap);
1492 	n_ineq = isl_basic_map_n_inequality(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(info->tab, 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  */
add_selected_wraps_around_facet(struct isl_wraps * wraps,struct isl_coalesce_info * info,int k,isl_int * bound,__isl_keep isl_set * set,int add_valid)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(info->bmap, isl_dim_all);
1546 
1547 	if (total < 0)
1548 		return isl_stat_error;
1549 
1550 	snap = isl_tab_snap(info->tab);
1551 
1552 	if (isl_tab_select_facet(info->tab, info->bmap->n_eq + k) < 0)
1553 		return isl_stat_error;
1554 	if (isl_tab_detect_redundant(info->tab) < 0)
1555 		return isl_stat_error;
1556 	if (info->tab->empty) {
1557 		if (isl_tab_rollback(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(bound, info->bmap->ineq[k], 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(info->tab, snap) < 0)
1576 		return isl_stat_error;
1577 	if (nowrap)
1578 		return wraps_mark_failed(wraps);
1579 	if (check_wraps(wraps, n, info->tab, 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  */
add_wraps_around_facet(struct isl_wraps * wraps,struct isl_coalesce_info * info,int k,isl_int * bound,__isl_keep isl_set * set)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, 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  */
add_valid_wraps_around_facet(struct isl_wraps * wraps,struct isl_coalesce_info * info,int k,isl_int * bound,__isl_keep isl_set * set)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, 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  */
is_adj_ineq_extension(int i,int j,struct isl_coalesce_info * info)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[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(info[i].bmap, isl_dim_all);
1648 	n_eq_i = isl_basic_map_n_equality(info[i].bmap);
1649 	n_ineq_i = isl_basic_map_n_inequality(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(info[j].bmap, info[j].tab);
1654 	ctx = isl_basic_map_get_ctx(info[i].bmap);
1655 	bound = isl_vec_alloc(ctx, 1 + total);
1656 	mat = isl_mat_alloc(ctx, 2 * n_eq_i + n_ineq_i, 1 + total);
1657 	if (wraps_init(&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, &info[i], k, bound->el, set_j);
1662 	if (r < 0)
1663 		goto error;
1664 
1665 	change = is_adj_ineq_extension_with_wraps(i, j, k, info, wraps.mat);
1666 
1667 	wraps_free(&wraps);
1668 	isl_vec_free(bound);
1669 	isl_set_free(set_j);
1670 
1671 	return change;
1672 error:
1673 	wraps_free(&wraps);
1674 	isl_vec_free(bound);
1675 	isl_set_free(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  */
check_adj_ineq(int i,int j,struct isl_coalesce_info * info)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[i], STATUS_ADJ_INEQ);
1717 	count_j = count_ineq(&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[i], STATUS_CUT) || any_ineq(&info[i], STATUS_CUT);
1723 	cut_j = any_eq(&info[j], STATUS_CUT) || any_ineq(&info[j], STATUS_CUT);
1724 
1725 	if (!cut_i && !cut_j && count_i == 1 && count_j == 1)
1726 		return fuse(i, j, info, NULL, 0, 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(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  */
can_wrap_in_facet(int i,int j,int k,struct isl_coalesce_info * info,int wrap_facet)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(info[i].bmap, isl_dim_all);
1769 
1770 	if (total < 0)
1771 		return isl_change_error;
1772 	set_i = set_from_updated_bmap(info[i].bmap, info[i].tab);
1773 	set_j = set_from_updated_bmap(info[j].bmap, info[j].tab);
1774 	ctx = isl_basic_map_get_ctx(info[i].bmap);
1775 	mat = isl_mat_alloc(ctx, 2 * (info[i].bmap->n_eq + info[j].bmap->n_eq) +
1776 				    info[i].bmap->n_ineq + info[j].bmap->n_ineq,
1777 				    1 + total);
1778 	if (wraps_init(&wraps, mat, info, i, j) < 0)
1779 		goto error;
1780 	bound = isl_vec_alloc(ctx, 1 + total);
1781 	if (!set_i || !set_j || !bound)
1782 		goto error;
1783 
1784 	isl_seq_cpy(bound->el, info[i].bmap->ineq[k], 1 + total);
1785 	isl_int_add_ui(bound->el[0], bound->el[0], 1);
1786 	isl_seq_normalize(ctx, bound->el, 1 + total);
1787 
1788 	isl_seq_cpy(wraps.mat->row[0], bound->el, 1 + total);
1789 	wraps.mat->n_row = 1;
1790 
1791 	if (add_wraps(&wraps, &info[j], bound->el, 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, &info[i], k,
1798 					    bound->el, set_j) < 0)
1799 			goto error;
1800 		if (wraps.failed)
1801 			goto unbounded;
1802 	}
1803 
1804 	change = fuse(i, j, info, wraps.mat, 0, 0);
1805 
1806 unbounded:
1807 	wraps_free(&wraps);
1808 
1809 	isl_set_free(set_i);
1810 	isl_set_free(set_j);
1811 
1812 	isl_vec_free(bound);
1813 
1814 	return change;
1815 error:
1816 	wraps_free(&wraps);
1817 	isl_vec_free(bound);
1818 	isl_set_free(set_i);
1819 	isl_set_free(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  */
wrap_in_facet(struct isl_wraps * wraps,int w,struct isl_coalesce_info * info_j,__isl_keep isl_set * set_i,struct isl_tab_undo * snap)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(info_j->tab, wraps->mat->row[w]) < 0)
1850 		return isl_stat_error;
1851 	if (isl_tab_detect_redundant(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_j, wraps->mat->row[w], set_i) < 0)
1857 		return isl_stat_error;
1858 
1859 	if (isl_tab_rollback(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  */
try_wrap_in_facets(int i,int j,struct isl_coalesce_info * info,struct isl_wraps * wraps,__isl_keep isl_set * set_i)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(info[i].bmap, isl_dim_all);
1891 	if (total < 0)
1892 		return isl_change_error;
1893 
1894 	snap = isl_tab_snap(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(wraps->mat->row[w],
1903 					    info[i].bmap->eq[k], 1 + total);
1904 			else
1905 				isl_seq_cpy(wraps->mat->row[w],
1906 					    info[i].bmap->eq[k], 1 + total);
1907 			if (wrap_in_facet(wraps, w, &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(wraps->mat->row[w],
1920 			    info[i].bmap->ineq[k], 1 + total);
1921 		if (wrap_in_facet(wraps, w, &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, wraps->mat, 0, 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  */
wrap_in_facets(int i,int j,int n,struct isl_coalesce_info * info)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(info[i].bmap, isl_dim_all);
1951 	int max_wrap;
1952 
1953 	if (total < 0)
1954 		return isl_change_error;
1955 	if (isl_tab_extend_cons(info[j].tab, 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(info[i].bmap, info[i].tab);
1962 	ctx = isl_basic_map_get_ctx(info[i].bmap);
1963 	mat = isl_mat_alloc(ctx, max_wrap, 1 + total);
1964 	if (wraps_init(&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, set_i);
1970 
1971 	wraps_free(&wraps);
1972 	isl_set_free(set_i);
1973 
1974 	return change;
1975 error:
1976 	wraps_free(&wraps);
1977 	isl_set_free(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  */
type_of_relaxed(struct isl_tab * tab,isl_int * ineq)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  */
can_wrap_in_set(int i,int j,struct isl_coalesce_info * info)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[i], STATUS_CUT) + count_ineq(&info[i], STATUS_CUT);
2066 	if (n == 0)
2067 		return isl_change_none;
2068 
2069 	total = isl_basic_map_dim(info[i].bmap, 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(info[i].bmap->eq[k],
2081 					    info[i].bmap->eq[k], 1 + total);
2082 			type = type_of_relaxed(info[j].tab,
2083 					    info[i].bmap->eq[k]);
2084 			if (l == 0)
2085 				isl_seq_neg(info[i].bmap->eq[k],
2086 					    info[i].bmap->eq[k], 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(info[j].tab, 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  */
check_wrap(int i,int j,struct isl_coalesce_info * info)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(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  */
all_cut_by_one(int i,int j,struct isl_coalesce_info * info,int * list)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(info[j].tab, 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  */
check_single_adj_eq(int i,int j,struct isl_coalesce_info * info)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[i], STATUS_CUT);
2180 
2181 	k = find_ineq(&info[i], STATUS_ADJ_EQ);
2182 
2183 	if (n_cut > 0) {
2184 		ctx = isl_basic_map_get_ctx(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, 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, 1 + n_cut, relax, info);
2198 	if (n_cut > 0)
2199 		free(relax);
2200 	if (change != isl_change_none)
2201 		return change;
2202 
2203 	change = can_wrap_in_facet(i, j, k, info, 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  */
check_adj_eq(int i,int j,struct isl_coalesce_info * info)2218 static enum isl_change check_adj_eq(int i, int j,
2219 	struct isl_coalesce_info *info)
2220 {
2221 	if (any_eq(&info[i], STATUS_ADJ_INEQ) &&
2222 	    any_eq(&info[j], STATUS_ADJ_INEQ))
2223 		/* ADJ EQ TOO MANY */
2224 		return isl_change_none;
2225 
2226 	if (any_eq(&info[i], STATUS_ADJ_INEQ))
2227 		return check_adj_eq(j, i, info);
2228 
2229 	/* j has an equality adjacent to an inequality in i */
2230 
2231 	if (count_ineq(&info[i], STATUS_ADJ_EQ) != 1) {
2232 		if (all_valid_or_cut(&info[i]))
2233 			return can_wrap_in_set(i, j, info);
2234 		return isl_change_none;
2235 	}
2236 	if (any_eq(&info[i], STATUS_CUT))
2237 		return isl_change_none;
2238 	if (any_ineq(&info[j], STATUS_ADJ_EQ) ||
2239 	    any_ineq(&info[i], STATUS_ADJ_INEQ) ||
2240 	    any_ineq(&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  */
check_ineq_adj_eq(int i,int j,struct isl_coalesce_info * info)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[i], STATUS_CUT))
2265 		return isl_change_none;
2266 	if (any_ineq(&info[i], STATUS_CUT))
2267 		return isl_change_none;
2268 	if (any_ineq(&info[i], STATUS_ADJ_INEQ))
2269 		return isl_change_none;
2270 	if (count_ineq(&info[i], STATUS_ADJ_EQ) != 1)
2271 		return isl_change_none;
2272 
2273 	k = find_ineq(&info[i], STATUS_ADJ_EQ);
2274 
2275 	return can_wrap_in_facet(i, j, k, info, 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  */
check_eq_adj_eq(int i,int j,struct isl_coalesce_info * info)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(info[i].bmap, isl_dim_all);
2309 
2310 	if (total < 0)
2311 		return isl_change_error;
2312 	if (count_eq(&info[i], STATUS_ADJ_EQ) != 1)
2313 		detect_equalities = 1;
2314 
2315 	k = find_eq(&info[i], STATUS_ADJ_EQ);
2316 
2317 	set_i = set_from_updated_bmap(info[i].bmap, info[i].tab);
2318 	set_j = set_from_updated_bmap(info[j].bmap, info[j].tab);
2319 	ctx = isl_basic_map_get_ctx(info[i].bmap);
2320 	mat = isl_mat_alloc(ctx, 2 * (info[i].bmap->n_eq + info[j].bmap->n_eq) +
2321 				    info[i].bmap->n_ineq + info[j].bmap->n_ineq,
2322 				    1 + total);
2323 	if (wraps_init(&wraps, mat, info, i, j) < 0)
2324 		goto error;
2325 	bound = isl_vec_alloc(ctx, 1 + total);
2326 	if (!set_i || !set_j || !bound)
2327 		goto error;
2328 
2329 	if (k % 2 == 0)
2330 		isl_seq_neg(bound->el, info[i].bmap->eq[k / 2], 1 + total);
2331 	else
2332 		isl_seq_cpy(bound->el, info[i].bmap->eq[k / 2], 1 + total);
2333 	isl_int_add_ui(bound->el[0], bound->el[0], 1);
2334 
2335 	isl_seq_cpy(wraps.mat->row[0], bound->el, 1 + total);
2336 	wraps.mat->n_row = 1;
2337 
2338 	if (add_wraps(&wraps, &info[j], bound->el, 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(bound->el, bound->el, 1 + total);
2345 
2346 	isl_seq_cpy(wraps.mat->row[wraps.mat->n_row], bound->el, 1 + total);
2347 	wraps.mat->n_row++;
2348 
2349 	if (add_wraps(&wraps, &info[i], bound->el, set_j) < 0)
2350 		goto error;
2351 	if (wraps.failed)
2352 		goto unbounded;
2353 
2354 	change = fuse(i, j, info, wraps.mat, detect_equalities, 0);
2355 
2356 	if (0) {
2357 error:		change = isl_change_error;
2358 	}
2359 unbounded:
2360 
2361 	wraps_free(&wraps);
2362 	isl_set_free(set_i);
2363 	isl_set_free(set_j);
2364 	isl_vec_free(bound);
2365 
2366 	return change;
2367 }
2368 
2369 /* Initialize the "eq" and "ineq" fields of "info".
2370  */
init_status(struct isl_coalesce_info * info)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  */
set_eq_status_in(struct isl_coalesce_info * info,struct isl_tab * tab)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(info->bmap, 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  */
set_ineq_status_in(struct isl_coalesce_info * info,struct isl_tab * tab)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(info->bmap, info->tab, 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  */
clear_status(struct isl_coalesce_info * info)2405 static void clear_status(struct isl_coalesce_info *info)
2406 {
2407 	free(info->eq);
2408 	free(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  */
all_ineq_valid_or_single_adj_ineq(struct isl_coalesce_info * info)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  */
separating_equality(int i,int j,struct isl_coalesce_info * info)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(info[j].eq, 2 * info[j].bmap->n_eq, STATUS_VALID) &&
2453 	    all_ineq_valid_or_single_adj_ineq(&info[j]))
2454 		change = is_adj_ineq_extension(j, i, info);
2455 
2456 	clear_status(&info[i]);
2457 	clear_status(&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  */
coalesce_local_pair_reuse(int i,int j,struct isl_coalesce_info * info)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[i], info[j].tab);
2553 	if (info[i].bmap->n_ineq && !info[i].ineq)
2554 		goto error;
2555 	if (any_ineq(&info[i], STATUS_ERROR))
2556 		goto error;
2557 	if (any_ineq(&info[i], STATUS_SEPARATE))
2558 		goto done;
2559 
2560 	set_ineq_status_in(&info[j], info[i].tab);
2561 	if (info[j].bmap->n_ineq && !info[j].ineq)
2562 		goto error;
2563 	if (any_ineq(&info[j], STATUS_ERROR))
2564 		goto error;
2565 	if (any_ineq(&info[j], STATUS_SEPARATE))
2566 		goto done;
2567 
2568 	set_eq_status_in(&info[i], info[j].tab);
2569 	if (info[i].bmap->n_eq && !info[i].eq)
2570 		goto error;
2571 	if (any_eq(&info[i], STATUS_ERROR))
2572 		goto error;
2573 
2574 	set_eq_status_in(&info[j], info[i].tab);
2575 	if (info[j].bmap->n_eq && !info[j].eq)
2576 		goto error;
2577 	if (any_eq(&info[j], STATUS_ERROR))
2578 		goto error;
2579 
2580 	if (any_eq(&info[i], STATUS_SEPARATE))
2581 		return separating_equality(i, j, info);
2582 	if (any_eq(&info[j], STATUS_SEPARATE))
2583 		return separating_equality(j, i, info);
2584 
2585 	if (all(info[i].eq, 2 * info[i].bmap->n_eq, STATUS_VALID) &&
2586 	    all(info[i].ineq, info[i].bmap->n_ineq, STATUS_VALID)) {
2587 		drop(&info[j]);
2588 		change = isl_change_drop_second;
2589 	} else if (all(info[j].eq, 2 * info[j].bmap->n_eq, STATUS_VALID) &&
2590 		   all(info[j].ineq, info[j].bmap->n_ineq, STATUS_VALID)) {
2591 		drop(&info[i]);
2592 		change = isl_change_drop_first;
2593 	} else if (any_eq(&info[i], STATUS_ADJ_EQ)) {
2594 		change = check_eq_adj_eq(i, j, info);
2595 	} else if (any_eq(&info[j], STATUS_ADJ_EQ)) {
2596 		change = check_eq_adj_eq(j, i, info);
2597 	} else if (any_eq(&info[i], STATUS_ADJ_INEQ) ||
2598 		   any_eq(&info[j], STATUS_ADJ_INEQ)) {
2599 		change = check_adj_eq(i, j, info);
2600 	} else if (any_ineq(&info[i], STATUS_ADJ_EQ)) {
2601 		change = check_ineq_adj_eq(i, j, info);
2602 	} else if (any_ineq(&info[j], STATUS_ADJ_EQ)) {
2603 		change = check_ineq_adj_eq(j, i, info);
2604 	} else if (any_ineq(&info[i], STATUS_ADJ_INEQ) ||
2605 		   any_ineq(&info[j], STATUS_ADJ_INEQ)) {
2606 		change = check_adj_ineq(i, j, info);
2607 	} else {
2608 		if (!any_eq(&info[i], STATUS_CUT) &&
2609 		    !any_eq(&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[i]);
2617 	clear_status(&info[j]);
2618 	return change;
2619 error:
2620 	clear_status(&info[i]);
2621 	clear_status(&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  */
coalesce_local_pair(int i,int j,struct isl_coalesce_info * info)2632 static enum isl_change coalesce_local_pair(int i, int j,
2633 	struct isl_coalesce_info *info)
2634 {
2635 	init_status(&info[i]);
2636 	init_status(&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  */
shift_div(struct isl_coalesce_info * info,int div,isl_int shift)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(info->bmap, div, 0, shift);
2657 	if (!info->bmap)
2658 		return isl_stat_error;
2659 
2660 	total = isl_basic_map_dim(info->bmap, isl_dim_all);
2661 	n_div = isl_basic_map_dim(info->bmap, 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(info->tab, 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  */
normalize_stride_div(struct isl_coalesce_info * info,int div)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(info->bmap, isl_dim_div,
2708 							div, &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(c, div);
2716 	isl_int_init(shift);
2717 	isl_int_init(stride);
2718 	isl_constraint_get_constant(c, &shift);
2719 	isl_constraint_get_coefficient(c, isl_dim_div, div, &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 							    info->bmap, div, 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  */
harmonize_stride_divs(struct isl_coalesce_info * info1,struct isl_coalesce_info * info2)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(info1->bmap, 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(info1->bmap, i);
2761 		if (known >= 0 && known)
2762 			known = isl_basic_map_div_is_known(info2->bmap, 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 					    info1->bmap, i, info2->bmap, i);
2769 		if (harmonize < 0)
2770 			return isl_stat_error;
2771 		if (!harmonize)
2772 			continue;
2773 		if (normalize_stride_div(info1, i) < 0)
2774 			return isl_stat_error;
2775 		if (normalize_stride_div(info2, 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  */
shift_if_cst_int(struct isl_coalesce_info * info,int div,__isl_keep isl_aff * shift)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(shift);
2804 	if (cst < 0 || !cst)
2805 		return cst < 0 ? isl_stat_error : isl_stat_ok;
2806 
2807 	c = isl_aff_get_constant_val(shift);
2808 	cst = isl_val_is_int(c);
2809 	if (cst >= 0 && cst)
2810 		cst = isl_bool_not(isl_val_is_zero(c));
2811 	if (cst < 0 || !cst) {
2812 		isl_val_free(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(c, &d);
2818 	if (r >= 0)
2819 		r = shift_div(info, div, d);
2820 	isl_int_clear(d);
2821 
2822 	isl_val_free(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  */
harmonize_divs_with_hulls(struct isl_coalesce_info * info1,struct isl_coalesce_info * info2,__isl_keep isl_basic_set * eq1,__isl_keep isl_basic_set * eq2)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(info1->bmap, isl_dim_all);
2869 	if (total < 0)
2870 		return isl_stat_error;
2871 	ls1 = isl_local_space_wrap(isl_basic_map_get_local_space(info1->bmap));
2872 	ls2 = isl_local_space_wrap(isl_basic_map_get_local_space(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(ls1, i) ||
2878 		    !isl_local_space_div_is_known(ls2, 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(info1->bmap->div[i] + 1,
2883 				info2->bmap->div[i] + 1, 1 + total))
2884 			continue;
2885 		div1 = isl_local_space_get_div(ls1, i);
2886 		div2 = isl_local_space_get_div(ls2, i);
2887 		div1 = isl_aff_substitute_equalities(div1,
2888 						    isl_basic_set_copy(eq2));
2889 		div2 = isl_aff_substitute_equalities(div2,
2890 						    isl_basic_set_copy(eq1));
2891 		div2 = isl_aff_sub(div2, div1);
2892 		r = shift_if_cst_int(info1, i, div2);
2893 		isl_aff_free(div2);
2894 		if (r < 0)
2895 			break;
2896 	}
2897 	isl_local_space_free(ls1);
2898 	isl_local_space_free(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  */
harmonize_divs(struct isl_coalesce_info * info1,struct isl_coalesce_info * info2)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(info1->bmap);
2948 	bmap2 = isl_basic_map_copy(info2->bmap);
2949 	eq1 = isl_basic_map_wrap(isl_basic_map_plain_affine_hull(bmap1));
2950 	eq2 = isl_basic_map_wrap(isl_basic_map_plain_affine_hull(bmap2));
2951 	equal = isl_basic_set_plain_is_equal(eq1, 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(eq1);
2959 	isl_basic_set_free(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  */
same_divs(__isl_keep isl_basic_map * bmap1,__isl_keep isl_basic_map * bmap2)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(bmap1);
2985 	if (known < 0 || !known)
2986 		return known;
2987 	known = isl_basic_map_divs_known(bmap2);
2988 	if (known < 0 || !known)
2989 		return known;
2990 
2991 	total = isl_basic_map_dim(bmap1, 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(bmap1->div[i], bmap2->div[i], 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  */
copy_ineq(struct isl_tab * tab,__isl_keep isl_basic_map * bmap)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, 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  */
fix_constant_divs(struct isl_coalesce_info * info,int n,struct isl_expanded * expanded)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(info->bmap, isl_dim_div) - 1;
3067 	ineq = isl_vec_alloc(isl_tab_get_ctx(info->tab), 1 + info->tab->n_var);
3068 	if (!ineq)
3069 		return isl_stat_error;
3070 	isl_seq_clr(ineq->el + 1, 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 						info->bmap, 0, 2);
3076 			info->bmap = isl_basic_map_add_div_constraints(
3077 					info->bmap, 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(info->bmap,
3082 								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(info->bmap,
3086 								ineq->el);
3087 			isl_int_set_si(ineq->el[1 + expanded[i].pos], 0);
3088 		}
3089 		if (copy_ineq(info->tab, info->bmap) < 0)
3090 			break;
3091 		if (expanded[i].cst &&
3092 		    isl_tab_select_facet(info->tab, info->tab->n_con - 1) < 0)
3093 			break;
3094 	}
3095 
3096 	isl_vec_free(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  */
tab_insert_divs(struct isl_coalesce_info * info,int n,struct isl_expanded * expanded,__isl_take isl_basic_map * bmap)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(info->tab, n) < 0)
3150 		goto error;
3151 	if (isl_tab_extend_cons(info->tab, 2 * n) < 0)
3152 		goto error;
3153 
3154 	for (i = 0; i < n; ++i) {
3155 		if (isl_tab_insert_var(info->tab, expanded[i].pos) < 0)
3156 			goto error;
3157 	}
3158 
3159 	snap = isl_tab_snap(info->tab);
3160 
3161 	n_ineq = info->tab->n_con - info->tab->n_eq;
3162 	if (copy_ineq(info->tab, bmap) < 0)
3163 		goto error;
3164 
3165 	isl_basic_map_free(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(info->tab,
3171 					    expanded[i].pos, &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(info->tab, snap) < 0)
3180 			return isl_stat_error;
3181 		info->bmap = isl_basic_map_cow(info->bmap);
3182 		info->bmap = isl_basic_map_free_inequality(info->bmap, 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(info->tab, 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  */
expand_tab(struct isl_coalesce_info * info,int * exp,__isl_take isl_basic_map * bmap)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, isl_dim_all);
3226 	n_div = isl_basic_map_dim(bmap, 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, extra_var, expanded, bmap);
3252 
3253 	for (k = 0; k < extra_var; ++k)
3254 		isl_int_clear(expanded[k].val);
3255 	free(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  */
coalesce_expand_tab_divs(__isl_take isl_basic_map * bmap,int i,int j,struct isl_coalesce_info * info,__isl_keep isl_mat * div,int * exp)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(info[j].bmap);
3303 	if (known < 0 || !known) {
3304 		clear_status(&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(info[i].bmap);
3310 	snap = isl_tab_snap(info[i].tab);
3311 	if (expand_tab(&info[i], exp, bmap) < 0)
3312 		change = isl_change_error;
3313 
3314 	init_status(&info[j]);
3315 	if (change == isl_change_none)
3316 		change = coalesce_local_pair_reuse(i, j, info);
3317 	else
3318 		clear_status(&info[i]);
3319 	if (change != isl_change_none && change != isl_change_drop_second) {
3320 		isl_basic_map_free(bmap_i);
3321 	} else {
3322 		isl_basic_map_free(info[i].bmap);
3323 		info[i].bmap = bmap_i;
3324 
3325 		if (isl_tab_rollback(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  */
coalesce_with_expanded_divs(__isl_keep isl_basic_map * bmap,int i,int j,struct isl_coalesce_info * info,__isl_keep isl_mat * div,int * exp)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_i);
3365 	bmap = isl_basic_map_copy(bmap);
3366 	bmap = isl_basic_map_expand_divs(bmap, isl_mat_copy(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, info[j].tab);
3374 	if (bmap->n_eq && !info_i->eq)
3375 		goto error;
3376 	if (any_eq(info_i, STATUS_ERROR))
3377 		goto error;
3378 	if (any_eq(info_i, STATUS_SEPARATE))
3379 		goto done;
3380 
3381 	info_i->ineq = ineq_status_in(bmap, NULL, info[j].tab);
3382 	if (bmap->n_ineq && !info_i->ineq)
3383 		goto error;
3384 	if (any_ineq(info_i, STATUS_ERROR))
3385 		goto error;
3386 	if (any_ineq(info_i, STATUS_SEPARATE))
3387 		goto done;
3388 
3389 	if (all(info_i->eq, 2 * bmap->n_eq, STATUS_VALID) &&
3390 	    all(info_i->ineq, bmap->n_ineq, STATUS_VALID)) {
3391 		drop(&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_i);
3401 	return change;
3402 error:
3403 	isl_basic_map_free(bmap);
3404 	clear_status(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  */
coalesce_after_aligning_divs(__isl_keep isl_basic_map * bmap_i,int i,int j,struct isl_coalesce_info * info)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_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_i);
3444 
3445 	div_i = isl_basic_map_get_divs(bmap_i);
3446 	div_j = isl_basic_map_get_divs(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(div_i, 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_i,
3462 							i, j, info, div, exp1);
3463 	else
3464 		change = isl_change_none;
3465 
3466 	isl_mat_free(div);
3467 
3468 	isl_mat_free(div_i);
3469 	isl_mat_free(div_j);
3470 
3471 	free(exp2);
3472 	free(exp1);
3473 
3474 	return change;
3475 error:
3476 	isl_mat_free(div_i);
3477 	isl_mat_free(div_j);
3478 	free(exp1);
3479 	free(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  */
coalesce_subset_with_equalities(int i,int j,struct isl_coalesce_info * info)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(info[i].bmap);
3513 	hull_i = isl_basic_map_plain_affine_hull(hull_i);
3514 	hull_j = isl_basic_map_copy(info[j].bmap);
3515 	hull_j = isl_basic_map_plain_affine_hull(hull_j);
3516 
3517 	hull_j = isl_basic_map_intersect(hull_j, isl_basic_map_copy(hull_i));
3518 	equal = isl_basic_map_plain_is_equal(hull_i, hull_j);
3519 	empty = isl_basic_map_plain_is_empty(hull_j);
3520 	isl_basic_map_free(hull_i);
3521 
3522 	if (equal < 0 || equal || empty < 0 || empty) {
3523 		isl_basic_map_free(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(info[i].bmap);
3530 	bmap_i = isl_basic_map_intersect(bmap_i, 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_i);
3536 		return isl_change_none;
3537 	}
3538 
3539 	change = coalesce_after_aligning_divs(bmap_i, -1, j, info);
3540 
3541 	isl_basic_map_free(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  */
coalesce_divs(int i,int j,struct isl_coalesce_info * info)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(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(info[j].bmap, 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(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  */
has_nested_div(__isl_keep isl_basic_map * bmap)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, isl_dim_all);
3596 	n_div = isl_basic_map_dim(bmap, 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(bmap->div[i] + 2 + total,
3603 					    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  */
set_up_substitutions(__isl_keep isl_basic_map * bmap_i,__isl_keep isl_basic_map * bmap_j,__isl_take isl_basic_map * hull)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_i, isl_dim_div);
3635 	n_div_j = isl_basic_map_dim(bmap_j, isl_dim_div);
3636 	total = isl_basic_map_dim(bmap_i, 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(hull);
3641 	total -= n_div_i;
3642 
3643 	ls = isl_basic_map_get_local_space(bmap_i);
3644 	ls = isl_local_space_wrap(ls);
3645 	wrap_hull = isl_basic_map_wrap(hull);
3646 
3647 	aff_nan = isl_aff_nan_on_domain(isl_local_space_copy(ls));
3648 	list = isl_aff_list_alloc(ctx, 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(bmap_i, i, bmap_j, j,
3657 						    0, 2 + total)) {
3658 			++j;
3659 			list = isl_aff_list_add(list, isl_aff_copy(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, i);
3666 		aff = isl_aff_substitute_equalities(aff,
3667 						isl_basic_set_copy(wrap_hull));
3668 		aff = isl_aff_floor(aff);
3669 		n_div = isl_aff_dim(aff, 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, aff);
3678 	}
3679 
3680 	isl_aff_free(aff_nan);
3681 	isl_local_space_free(ls);
3682 	isl_basic_set_free(wrap_hull);
3683 
3684 	return list;
3685 error:
3686 	isl_aff_free(aff_nan);
3687 	isl_local_space_free(ls);
3688 	isl_basic_set_free(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  */
add_sub_vars(struct isl_coalesce_info * info,__isl_keep isl_aff_list * list,int dim,int extra_var)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(info->bmap);
3716 	info->bmap = isl_basic_map_extend(info->bmap, extra_var, 0, 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, 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(info->tab, dim + i) < 0)
3733 			return isl_stat_error;
3734 		d = isl_basic_map_alloc_div(info->bmap);
3735 		if (d < 0)
3736 			return isl_stat_error;
3737 		info->bmap = isl_basic_map_mark_div_unknown(info->bmap, d);
3738 		for (j = d; j > i; --j)
3739 			info->bmap = isl_basic_map_swap_div(info->bmap,
3740 							    j - 1, 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  */
add_sub_equalities(struct isl_tab * tab,__isl_keep isl_aff_list * list,int dim)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, 1 + dim + n);
3771 	if (!sub)
3772 		return isl_stat_error;
3773 	isl_seq_clr(sub->el + 1 + dim, n);
3774 
3775 	for (i = 0; i < n; ++i) {
3776 		aff = isl_aff_list_get_aff(list, 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(sub->el, aff->v->el + 1, 1 + dim);
3784 		isl_int_neg(sub->el[1 + dim + i], aff->v->el[0]);
3785 		if (isl_tab_add_eq(tab, 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(sub);
3792 	return isl_stat_ok;
3793 error:
3794 	isl_aff_free(aff);
3795 	isl_vec_free(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  */
add_subs(struct isl_coalesce_info * info,__isl_keep isl_aff_list * list,int dim)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(info->tab, extra_var) < 0)
3820 		return isl_stat_error;
3821 	if (isl_tab_extend_cons(info->tab, 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(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  */
coalesce_with_subs(int i,int j,struct isl_coalesce_info * info,__isl_keep isl_aff_list * list)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(info[j].bmap);
3851 	snap = isl_tab_snap(info[j].tab);
3852 
3853 	dim = isl_basic_map_dim(bmap_j, isl_dim_all);
3854 	n_div = isl_basic_map_dim(bmap_j, isl_dim_div);
3855 	if (dim < 0 || n_div < 0)
3856 		goto error;
3857 	dim -= n_div;
3858 	if (add_subs(&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_j);
3864 	} else {
3865 		isl_basic_map_free(info[j].bmap);
3866 		info[j].bmap = bmap_j;
3867 
3868 		if (isl_tab_rollback(info[j].tab, snap) < 0)
3869 			return isl_change_error;
3870 	}
3871 
3872 	return change;
3873 error:
3874 	isl_basic_map_free(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  */
check_coalesce_into_eq(int i,int j,struct isl_coalesce_info * info)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(info[i].bmap, isl_dim_div);
3902 	n_div_j = isl_basic_map_dim(info[j].bmap, 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(info[i].bmap);
3911 	hull_i = isl_basic_map_plain_affine_hull(hull_i);
3912 	hull_j = isl_basic_map_copy(info[j].bmap);
3913 	hull_j = isl_basic_map_plain_affine_hull(hull_j);
3914 
3915 	hull_j = isl_basic_map_intersect(hull_j, isl_basic_map_copy(hull_i));
3916 	equal = isl_basic_map_plain_is_equal(hull_i, hull_j);
3917 	empty = isl_basic_map_plain_is_empty(hull_j);
3918 	isl_basic_map_free(hull_i);
3919 
3920 	if (equal < 0 || empty < 0)
3921 		goto error;
3922 	if (equal || empty) {
3923 		isl_basic_map_free(hull_j);
3924 		return isl_change_none;
3925 	}
3926 
3927 	list = set_up_substitutions(info[i].bmap, info[j].bmap, 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(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  */
check_coalesce_eq(int i,int j,struct isl_coalesce_info * info)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(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(info[j].bmap);
3963 	if (known < 0 || !known)
3964 		return known < 0 ? isl_change_error : isl_change_none;
3965 	nested = has_nested_div(info[i].bmap);
3966 	if (nested < 0 || nested)
3967 		return nested < 0 ? isl_change_error : isl_change_none;
3968 	nested = has_nested_div(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(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  */
coalesce_pair(int i,int j,struct isl_coalesce_info * info)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(&info[i], &info[j]) < 0)
4011 		return isl_change_error;
4012 	same = same_divs(info[i].bmap, 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(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  */
isl_max(int a,int b)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  */
coalesce_range(isl_ctx * ctx,struct isl_coalesce_info * info,int start1,int end1,int start2,int end2)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(i + 1, 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  */
coalesce(isl_ctx * ctx,int n,struct isl_coalesce_info * info)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, start, end, start, end) < 0)
4109 			return -1;
4110 		if (coalesce_range(ctx, info, start, end, end, 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  */
update_basic_maps(__isl_take isl_map * map,int n,struct isl_coalesce_info * info)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(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(info[i].bmap,
4147 							info[i].tab);
4148 		info[i].bmap = isl_basic_map_gauss(info[i].bmap, NULL);
4149 		if (info[i].simplify)
4150 			info[i].bmap = isl_basic_map_simplify(info[i].bmap);
4151 		info[i].bmap = isl_basic_map_finalize(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(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  */
isl_map_coalesce(__isl_take isl_map * map)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(map->p[i]);
4220 		if (!map->p[i])
4221 			goto error;
4222 		info[i].bmap = isl_basic_map_copy(map->p[i]);
4223 		info[i].tab = isl_tab_from_basic_map(info[i].bmap, 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(info[i].tab) < 0)
4228 				goto error;
4229 		info[i].bmap = isl_tab_make_equalities_explicit(info[i].tab,
4230 								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(info[i].tab) < 0)
4235 				goto error;
4236 		if (coalesce_info_set_hull_hash(&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[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  */
isl_set_coalesce(__isl_take isl_set * set)4261 __isl_give isl_set *isl_set_coalesce(__isl_take isl_set *set)
4262 {
4263 	return set_from_map(isl_map_coalesce(set_to_map(set)));
4264 }
4265