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